Page 1 of 4 123 ... LastLast
Results 1 to 10 of 34

Thread: Beginners Programming Challenge 22

  1. #1
    Join Date
    Nov 2009
    Location
    The Netherlands
    Beans
    239
    Distro
    Ubuntu 12.04 Precise Pangolin

    Beginners Programming Challenge 22

    With this challenge i'm going to try to get people to do some bit-fiddling, which means you will need to know how to use (at least some of)
    the bitwise operators, and you will have to know something about how data is represented in your computer. At the same time i tried to come up with
    a challenge that is still quite beginner friendly and that shouldn't take too much time.

    The Challenge
    To create a program that can encode data to base64. Read the link for an explanation.

    ubuntu by default comes with the base64 command, so testing your code should be easy, make sure to test with input of different sizes.

    Note: I realize that it is possible to do this without using any of the bitwise operators. Unless your programming language of choice doesn't
    support them, try to show that you know how to use them.

    Extra points are for programs that can also decode and wrap the output lines (basically the same options the base64 programs has too) and
    programs that support other, similar encodings like Base58, Base32 and Ascii85.

    Judging
    As usual judgement is based on if your code works and how readable it is. Another point of judgement will be how well your code works with (very)
    large files.

  2. #2
    Join Date
    Nov 2005
    Location
    Bordeaux, France
    Beans
    11,292
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginners Programming Challenge 22

    Obligatory Haskell. Yes, I know I'm not really a beginner, but no one ever does Haskell in those challenges anyway (and besides, I was a beginner at doing binary I/O and using the bitwise operators in Haskell ). If you were going to do it, don't read this code.

    Code:
    import Data.Bits
    import Data.Char
    import System.Environment
    import System.IO
    
    -- Converts an Int between 0 and 63 to its representation in base64
    base64Chr :: Int -> Char
    
    -- Encodes the input String to base64
    base64Enc :: String -> String
    
    -- Writes the string passed in argument to the standard input, wrapping it
    -- in lines of n characters
    printBase64 :: String -> Int -> IO ()
    
    base64Chr n = if n < 0 -- Invalid
                     then '#'
                  else if n < 26 -- Uppercase alpha
                     then chr (ord 'A' + n)
                  else if n < 52 -- Lowercase alpha
                     then chr (ord 'a' + n - 26)
                  else if n < 62 -- Digit
                     then chr (ord '0' + n - 52)
                  else if n == 62
                     then '+'
                  else if n == 63
                     then '/'
                  else '#' -- Invalid
    
    
    -- Empty string
    base64Enc []    = []
    
    -- One-character string
    base64Enc [i1]  = [o1, o2, '=', '=']
                      where o1 = base64Chr (shiftR (ord i1) 2)
                            o2 = base64Chr (shiftL (ord i1 .&. 3) 4)
    
    -- Two-character string
    base64Enc [i1, i2] = [o1, o2, o3, '=']
                         where o1 = base64Chr (shiftR (ord i1) 2)
                               o2 = base64Chr ((shiftL (ord i1 .&. 3) 4) .|.
                                               (shiftR (ord i2) 4))
                               o3 = base64Chr (shiftL (ord i2 .&. 15) 2)
    
    -- Default (three or more character)
    base64Enc s = [o1, o2, o3, o4] ++ base64Enc (drop 3 s)
                  where o1 = base64Chr (shiftR (ord i1) 2)
                        o2 = base64Chr ((shiftL (ord i1 .&. 3) 4) .|.
                                        (shiftR (ord i2) 4))
                        o3 = base64Chr ((shiftL (ord i2 .&. 15) 2) .|.
                                        (shiftR (ord i3) 6))
                        o4 = base64Chr (ord i3 .&. 63)
                        [i1, i2, i3] = take 3 s
    
    
    printBase64 [] _ = putStr ""
    printBase64 s n  = do putStrLn (take n s)
                          printBase64 (drop n s) n
    
    main = do args <- getArgs
              if null args || (args !! 0) == "-"
                 -- Read from standard input
                 then do hSetBinaryMode stdin True
                         s <- getContents
                         printBase64 (base64Enc s) 76
    
                 -- Read from file
                 else do ifile <- openBinaryFile (args !! 0) ReadMode
                         s <- hGetContents ifile
                         printBase64 (base64Enc s) 76
                         hClose ifile
    Save as base64.hs and compile with

    Code:
    ghc --make base64.hs
    Supports reading from a file and from standard input. If called with one argument, the argument is the name of the fileto read, or - to read from standard input. If no argument, reads from standard input. Wrapping length is hardcoded at 76 characters (default in base64 from the GNU coreutils). No error handling for file errors (e.g. non-existent or non-readable file), the Haskell runtime will print an informative error message anyway.

    Gives the same result as base64, though performance is much less good on large files:

    Code:
    firas@aoba ~ % ls -lh /boot/initrd.img-2.6.38-11-generic 
    -rw-r--r-- 1 root root 19M 2011-08-13 00:51 /boot/initrd.img-2.6.38-11-generic
    firas@aoba ~ % time base64 /boot/initrd.img-2.6.38-11-generic > test1.txt 
    base64 /boot/initrd.img-2.6.38-11-generic > test1.txt  0.10s user 0.30s system 92% cpu 0.434 total
    firas@aoba ~ % time ./base64 /boot/initrd.img-2.6.38-11-generic > test2.txt
    ./base64 /boot/initrd.img-2.6.38-11-generic > test2.txt  11.39s user 0.90s system 99% cpu 12.317 total
    firas@aoba ~ % diff test1.txt test2.txt 
    firas@aoba ~ %
    Last edited by Bachstelze; August 19th, 2011 at 06:49 AM.
    「明後日の夕方には帰ってるからね。」


  3. #3
    Join Date
    Nov 2005
    Location
    Bordeaux, France
    Beans
    11,292
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginners Programming Challenge 22

    Or how about some assembly?

    main.c:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define OUTPUT_LINE_LENGTH 76
    #define INPUT_LINE_LENGTH  (((OUTPUT_LINE_LENGTH)*3)/4)
    
    void usage(char*);
    int base64enc(char*, unsigned char*, int);
    
    void usage(char *s)
    {
            fprintf(stderr, "Usage: %s [FILE]\n"
                            "If FILE is omitted or -, reads from the standard "
                            "input.\n", s);
            exit(EXIT_FAILURE);
    }
    
    int main(int argc, char **argv)
    {
            if (argc > 2) {
                    usage(argv[0]);
            }
    
            unsigned char ibuf[INPUT_LINE_LENGTH];
            char obuf[OUTPUT_LINE_LENGTH+1]; /* +1 for terminating null */
    
            FILE *ifile;
            if (argc == 1 || strcmp(argv[1], "-") == 0) {
                    ifile = stdin;
            } else {
                    ifile = fopen(argv[1], "r");
                    if (ifile == NULL) {
                            perror("Could not open input file");
                            exit(EXIT_FAILURE);
                    }
            }
    
            for (;;) {
                    int bytes_read = fread(ibuf, 1, INPUT_LINE_LENGTH, ifile);
                    if (bytes_read == 0) {
                            break;
                    }
                    int bytes_written = base64enc(obuf, ibuf, bytes_read);
                    obuf[bytes_written] = '\0';
                    puts(obuf);
            }
            fclose(ifile);
    }
    base64enc.S
    Code:
    .data
    charmap:
            .long 0x44434241
            .long 0x48474645
            .long 0x4c4b4a49
            .long 0x504f4e4d
            .long 0x54535251
            .long 0x58575655
            .long 0x62615a59
            .long 0x66656463
            .long 0x6a696867
            .long 0x6e6d6c6b
            .long 0x7271706f
            .long 0x76757473
            .long 0x7a797877
            .long 0x33323130
            .long 0x37363534
            .long 0x2f2b3938
    
    .text
    .globl base64enc
            .type base64enc, @function
    
    base64enc:
    
    pushl   %ebp
    movl    %esp, %ebp
    
    # Callee-save registers
    pushl   %ebx
    pushl   %edi
    pushl   %esi
    
    # ebp-4 will be our temporary buffer
    subl    $4, %esp
    
    # eax is the return value, which is the number of bytes written to
    # the output buffer.  Initialise it at 0.
    movl    $0, %eax
    
    # ecx is the number of bytes left to be read. It is the third parameter
    # to the function, so we fetch it from ebp+16.
    movl    16(%ebp), %ecx
    
    # edi is the address of the input buffer
    movl    12(%ebp), %edi
    
    # esi is the address of the output buffer
    movl    8(%ebp), %esi
    
    # If %ecx is already non-positive, don't enter the loop at all.
    andl    %ecx, %ecx
    jle     endmainloop
    
    mainloop:
    addl    $4, %eax
    movzbl  (%edi), %edx
    movl    $0, %ebx
    
    # More than one character?
    cmpl    $1, %ecx
    jle     nomorethanone
    movzbl  1(%edi), %ebx
    nomorethanone:
    movb    %bl, -4(%ebp)
    
    # First base64 character
    shrl    $2, %edx
    movzbl  charmap(%edx), %edx
    movb    %dl, (%esi)
    
    # Second base64 character
    movzbl  (%edi), %edx
    andl    $3, %edx
    shll    $4, %edx
    shrl    $4, %ebx
    orl     %ebx, %edx
    movzbl  charmap(%edx), %ebx
    movb    %bl, 1(%esi)
    
    # More than one character? (Yes, we must do the test twice.)
    cmpl    $1, %ecx
    jne     morethanone
    movw    $0x3d3d, 2(%esi)
    jmp     endmainloop
    morethanone:
    
    movzbl  -4(%ebp), %edx
    movl    $0, %ebx
    
    # More than two characters?
    cmpl    $2, %ecx
    jle     nomorethantwo
    movzbl  2(%edi), %ebx
    nomorethantwo:
    movb    %bl, -4(%ebp)
    
    # Third base64 character
    andl    $15, %edx
    shll    $2, %edx
    shrl    $6, %ebx
    orl     %ebx, %edx
    movzbl  charmap(%edx), %edx
    movb    %dl, 2(%esi)
    
    # More than two characters? (Yes, again.)
    cmpl    $2, %ecx
    jne     morethantwo
    movb    $0x3d, 3(%esi)
    jmp     endmainloop
    morethantwo:
    
    # Fourth base64 character
    movzbl  -4(%ebp), %edx
    andl    $63, %edx
    movzbl  charmap(%edx), %edx
    movb    %dl, 3(%esi)
    
    # Increment everything
    addl    $3, %edi
    addl    $4, %esi
    subl    $3, %ecx
    
    # Exit?
    andl    %ecx, %ecx
    jg      mainloop
    
    endmainloop:
    
    # Clean-up
    addl    $4, %esp
    popl    %esi
    popl    %edi
    popl    %ebx
    popl    %ebp
    ret
    
    .size   base64enc, .-base64enc
    And this Makefile:

    Code:
    CC=gcc
    CFLAGS=-m32 -std=c99 -pedantic -Wall -Werror
    ifdef DEBUG
    	CFLAGS+=-g
    endif
    ASFLAGS=-m32
    OBJECTS=main.o base64enc.o
    OUTFILE=base64
    
    $(OUTFILE): $(OBJECTS)
    	$(CC) $(CFLAGS) -o $@ $+
    
    clean:
    	rm -f $(OUTFILE) $(OBJECTS)
    Performance is comparable to base64 from coreutils:

    Code:
    firas@aoba base64 % make
    gcc -m32 -std=c99 -pedantic -Wall -Werror   -c -o main.o main.c
    gcc -m32   -c -o base64enc.o base64enc.S
    gcc -m32 -std=c99 -pedantic -Wall -Werror -o base64 main.o base64enc.o
    firas@aoba base64 % time base64 /boot/initrd.img-2.6.38-11-generic > test1.txt 
    base64 /boot/initrd.img-2.6.38-11-generic > test1.txt  0.05s user 0.36s system 98% cpu 0.417 total
    firas@aoba base64 % time ./base64 /boot/initrd.img-2.6.38-11-generic > test2.txt 
    ./base64 /boot/initrd.img-2.6.38-11-generic > test2.txt  0.15s user 0.35s system 90% cpu 0.550 total
    firas@aoba base64 % diff test1.txt test2.txt 
    firas@aoba base64 %
    I'm going to try and do it in MIPS assembly when I get my hands on my MIPS machine too. (Or maybe I should do a decoder...)
    Last edited by Bachstelze; August 19th, 2011 at 08:46 AM.
    「明後日の夕方には帰ってるからね。」


  4. #4
    Join Date
    Nov 2009
    Location
    The Netherlands
    Beans
    239
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginners Programming Challenge 22

    For some reason as doesn't recognize -m32 on my system, any ideas why this would be? its a 64bit system. It seems to work if i use `gcc -m32 base64enc.s main.c`' though.
    Good commenting btw. This problem was actually one of the first i tried when i started learning assembly 2 years ago and when i read back my old code i have trouble understanding what happens. It probably has something to do with my lack of commenting

  5. #5
    Join Date
    Nov 2005
    Location
    Bordeaux, France
    Beans
    11,292
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginners Programming Challenge 22

    Quote Originally Posted by ziekfiguur View Post
    For some reason as doesn't recognize -m32 on my system, any ideas why this would be? its a 64bit system. It seems to work if i use `gcc -m32 base64enc.s main.c`' though.
    I'm on 64bit too, and it works fine. Do you get an error message?
    「明後日の夕方には帰ってるからね。」


  6. #6
    Join Date
    Nov 2009
    Location
    The Netherlands
    Beans
    239
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginners Programming Challenge 22

    This is what i get:
    Code:
    $ make
    as -m32  -o base64enc.o base64enc.s
    as: unrecognized option '-m32'
    make: *** [base64enc.o] Error 1
    So, if everyone else wants to try Bachstelzes code, if you get this error you can just use:
    Code:
    $ gcc -m32 -pedantic -Wall -Werror -std=c99 base64enc.s main.c
    Edit: I just realized, i named the file base64enc.s instead of base64enc.S (note the capital S) I think when you use .S make doesn't realize it's a assembly file and still calls gcc instead of as, seeing that in your post make also uses gcc to build base64enc.S
    Last edited by ziekfiguur; August 19th, 2011 at 06:34 PM.

  7. #7
    Join Date
    Nov 2005
    Location
    Bordeaux, France
    Beans
    11,292
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginners Programming Challenge 22

    Quote Originally Posted by ziekfiguur View Post
    Edit: I just realized, i named the file base64enc.s instead of base64enc.S (note the capital S) I think when you use .S make doesn't realize it's a assembly file and still calls gcc instead of as, seeing that in your post make also uses gcc to build base64enc.S
    Good catch. I didn't give the extension much thought. Apparently .S is for assembly that is supposed to be preprocessed with cpp yielding a .s, and .s for assembly which is to be assembled directly. So my guess is that since I had a .S, make realized it would have to both preprocess and assemble, and used gcc as a "shortcut" to perform both steps in one command.
    「明後日の夕方には帰ってるからね。」


  8. #8
    Join Date
    May 2009
    Beans
    522

    Re: Beginners Programming Challenge 22

    I'm not a beginner, but I just thought I would show off the "magic" of python. So don't judge this.

    Code:
    import base64
    
    data = raw_input("Enter data to encode\n")
    
    print base64.b64encode(data)
    
    data = raw_input("Enter encoded data to decode\n")
    
    print base64.b64decode(data)
    base16 and base32 are equally trivial.


  9. #9
    Join Date
    Nov 2005
    Location
    Bordeaux, France
    Beans
    11,292
    Distro
    Ubuntu 12.04 Precise Pangolin

    Re: Beginners Programming Challenge 22

    Oh, so impressive. I think I'm going to faint over how awesome that is.
    「明後日の夕方には帰ってるからね。」


  10. #10
    Join Date
    Nov 2007
    Location
    London, England
    Beans
    6,350
    Distro
    Xubuntu Development Release

    Re: Beginners Programming Challenge 22

    Oi! You just broke my sarcasmometer! Bent the needle right round!

Page 1 of 4 123 ... LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •