Beginners Programming Challenge 22

[ziekfiguur]

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.

[Bachstelze]

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.

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

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:

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 ~ %

[Bachstelze]

Or how about some assembly?

main.c:

#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

.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:

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:

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...)

[ziekfiguur]

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

[Bachstelze]

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?

[ziekfiguur]

This is what i get:

$ 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:

$ 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

[Bachstelze]

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.

[unknownPoster]

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

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.

[Bachstelze]

Oh, so impressive. I think I'm going to faint over how awesome that is.

[The Cog]

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