base64-benchmarks.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/uio.h>
#include <unistd.h>
#include <fcntl.h>

#define HAVE_STDINT_H 1
#define ENABLE_ZENTIMER 1
#include "zentimer.h"

#define d(x)

/**
 * GMIME_BASE64_ENCODE_LEN:
 * @x: Length of the input data to encode
 *
 * Calculates the maximum number of bytes needed to base64 encode the
 * full input buffer of length @x.
 *
 * Returns: the number of output bytes needed to base64 encode an input
 * buffer of size @x.
 **/
#define GMIME_BASE64_ENCODE_LEN(x) ((size_t) (((((x) + 2) / 57) * 77) + 77))

static char base64_alphabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

static unsigned char base64_rank[256] = {
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255, 62,255,255,255, 63,
	 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,255,255,255,  0,255,255,
	255,  0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14,
	 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,255,255,255,255,255,
	255, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
	 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
	255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,
};

/* do incremental base64 (de/en)coding */
size_t base64_decode_step (const unsigned char *inbuf, size_t inlen, unsigned char *outbuf, int *state, unsigned int *save);
size_t base64_encode_step (const unsigned char *inbuf, size_t inlen, unsigned char *outbuf, int *state, unsigned int *save);
size_t base64_encode_close (const unsigned char *inbuf, size_t inlen, unsigned char *outbuf, int *state, unsigned int *save);

/**
 * base64_encode_close:
 * @inbuf: input buffer
 * @inlen: input buffer length
 * @outbuf: output buffer
 * @state: holds the number of bits that are stored in @save
 * @save: leftover bits that have not yet been encoded
 *
 * Base64 encodes the input stream to the output stream. Call this
 * when finished encoding data with base64_encode_step()
 * to flush off the last little bit.
 *
 * Returns: the number of bytes encoded.
 **/
size_t
base64_encode_close (const unsigned char *inbuf, size_t inlen, unsigned char *outbuf, int *state, unsigned int *save)
{
	unsigned char *outptr = outbuf;
	int c1, c2;
	
	if (inlen > 0)
		outptr += base64_encode_step (inbuf, inlen, outptr, state, save);
	
	c1 = ((unsigned char *)save)[1];
	c2 = ((unsigned char *)save)[2];
	
	switch (((unsigned char *)save)[0]) {
	case 2:
		outptr[2] = base64_alphabet [(c2 & 0x0f) << 2];
		goto skip;
	case 1:
		outptr[2] = '=';
	skip:
		outptr[0] = base64_alphabet [c1 >> 2];
		outptr[1] = base64_alphabet [c2 >> 4 | ((c1 & 0x3) << 4)];
		outptr[3] = '=';
		outptr += 4;
		break;
	}
	
	*outptr++ = '\n';
	
	*save = 0;
	*state = 0;
	
	return (outptr - outbuf);
}


/**
 * base64_encode_step:
 * @inbuf: input buffer
 * @inlen: input buffer length
 * @outbuf: output buffer
 * @state: holds the number of bits that are stored in @save
 * @save: leftover bits that have not yet been encoded
 *
 * Base64 encodes a chunk of data. Performs an 'encode step', only
 * encodes blocks of 3 characters to the output at a time, saves
 * left-over state in state and save (initialize to 0 on first
 * invocation).
 *
 * Returns: the number of bytes encoded.
 **/
size_t
base64_encode_step (const unsigned char *inbuf, size_t inlen, unsigned char *outbuf, int *state, unsigned int *save)
{
	register const unsigned char *inptr;
	register unsigned char *outptr;
	
	if (inlen == 0)
		return 0;
	
	outptr = outbuf;
	inptr = inbuf;
	
	if (inlen + ((unsigned char *)save)[0] > 2) {
		const unsigned char *inend = inbuf + inlen - 2;
		register int c1 = 0, c2 = 0, c3 = 0;
		register int already;
		
		already = *state;
		
		switch (((char *)save)[0]) {
		case 1:	c1 = ((unsigned char *)save)[1]; goto skip1;
		case 2:	c1 = ((unsigned char *)save)[1];
			c2 = ((unsigned char *)save)[2]; goto skip2;
		}
		
		/* yes, we jump into the loop, no i'm not going to change it, its beautiful! */
		while (inptr < inend) {
			c1 = *inptr++;
		skip1:
			c2 = *inptr++;
		skip2:
			c3 = *inptr++;
			*outptr++ = base64_alphabet [c1 >> 2];
			*outptr++ = base64_alphabet [(c2 >> 4) | ((c1 & 0x3) << 4)];
			*outptr++ = base64_alphabet [((c2 & 0x0f) << 2) | (c3 >> 6)];
			*outptr++ = base64_alphabet [c3 & 0x3f];
			/* this is a bit ugly ... */
			if ((++already) >= 19) {
				*outptr++ = '\n';
				already = 0;
			}
		}
		
		((unsigned char *)save)[0] = 0;
		inlen = 2 - (inptr - inend);
		*state = already;
	}
	
	d(printf ("state = %d, inlen = %d\n", (int)((char *)save)[0], inlen));
	
	if (inlen > 0) {
		register char *saveout;
		
		/* points to the slot for the next char to save */
		saveout = & (((char *)save)[1]) + ((char *)save)[0];
		
		/* inlen can only be 0, 1 or 2 */
		switch (inlen) {
		case 2:	*saveout++ = *inptr++;
		case 1:	*saveout++ = *inptr++;
		}
		((char *)save)[0] += (char) inlen;
	}
	
	d(printf ("mode = %d\nc1 = %c\nc2 = %c\n",
		  (int)((char *)save)[0],
		  (int)((char *)save)[1],
		  (int)((char *)save)[2]));
	
	return (outptr - outbuf);
}


/**
 * base64_decode_step:
 * @inbuf: input buffer
 * @inlen: input buffer length
 * @outbuf: output buffer
 * @state: holds the number of bits that are stored in @save
 * @save: leftover bits that have not yet been decoded
 *
 * Decodes a chunk of base64 encoded data.
 *
 * Returns: the number of bytes decoded (which have been dumped in
 * @outbuf).
 **/
size_t
base64_decode_step (const unsigned char *inbuf, size_t inlen, unsigned char *outbuf, int *state, unsigned int *save)
{
	register const unsigned char *inptr;
	register unsigned char *outptr;
	const unsigned char *inend;
	register unsigned int saved;
	unsigned char last[2];
	unsigned char c, rank;
	int n;
	
	inend = inbuf + inlen;
	outptr = outbuf;
	inptr = inbuf;
	
	saved = *save;
	n = *state;
	
	if (n < 0) {
		last[0] = '=';
		n = -n;
	} else {
		last[0] = '\0';
	}
	
	last[1] = '\0';
	
	/* convert 4 base64 bytes to 3 normal bytes */
	while (inptr < inend) {
		rank = base64_rank[(c = *inptr++)];
		if (rank != 0xff) {
			saved = (saved << 6) | rank;
			last[1] = last[0];
			last[0] = c;
			n++;
			if (n == 4) {
				*outptr++ = saved >> 16;
				if (last[1] != '=')
					*outptr++ = saved >> 8;
				if (last[0] != '=')
					*outptr++ = saved;
				n = 0;
			}
		}
	}
	
	*state = last[0] == '=' ? -n : n;
	*save = saved;
	
	return (outptr - outbuf);
}

size_t
mk_base64_encode_step (const unsigned char *inbuf, size_t inlen, unsigned char *outbuf, int *state, unsigned int *save)
{
	register const unsigned char *inptr;
	register unsigned char *outptr;
	register int quartets;
	unsigned char *saved;
	size_t remaining;

	if (inlen == 0)
		return 0;

	saved = (unsigned char *) save;
	quartets = *state;
	outptr = outbuf;
	inptr = inbuf;

	if (inlen + *saved > 2) {
		const unsigned char *inend = inbuf + inlen - 2;
		register int c1, c2, c3;

		c1 = *saved < 1 ? *inptr++ : saved[1];
		c2 = *saved < 2 ? *inptr++ : saved[2];
		c3 = *inptr++;

	  loop:
		// encode our triplet into a quartet
		*outptr++ = base64_alphabet[c1 >> 2];
		*outptr++ = base64_alphabet[(c2 >> 4) | ((c1 & 0x3) << 4)];
		*outptr++ = base64_alphabet[((c2 & 0x0f) << 2) | (c3 >> 6)];
		*outptr++ = base64_alphabet[c3 & 0x3f];

		// encode 19 quartets per line
		if ((++quartets) >= 19) {
			*outptr++ = '\n';
			quartets = 0;
		}

		if (inptr >= inend)
			goto loop_exit;

		c1 = *inptr++;
		c2 = *inptr++;
		c3 = *inptr++;
		goto loop;

	  loop_exit:
		remaining = 2 - (size_t) (inptr - inend);
		*save = 0;
	} else {
		remaining = inlen;
	}

	if (remaining > 0) {
		// At this point, saved can only be 0 or 1.
		if (*saved == 0) {
			// We can have up to 2 remaining input bytes.
			saved[0] = (unsigned char) remaining;
			saved[1] = *inptr++;
			if (remaining == 2)
				saved[2] = *inptr;
			else
				saved[2] = 0;
		} else {
			// We have 1 remaining input byte.
			saved[2] = *inptr;
			saved[0] = 2;
		}
	}

	*state = quartets;

	return (size_t) (outptr - outbuf);
}

size_t
mk_base64_encode_close (const unsigned char *inbuf, size_t inlen, unsigned char *outbuf, int *state, unsigned int *save)
{
	register unsigned char *outptr = outbuf;
	register int quartets;
	unsigned char *saved;

	if (inlen > 0)
		outptr += mk_base64_encode_step (inbuf, inlen, outbuf, state, save);

	saved = (unsigned char *) save;
	quartets = *state;

	if (*saved > 0) {
		int c1 = saved[1];
		int c2 = saved[2];

		*outptr++ = base64_alphabet[c1 >> 2];
		*outptr++ = base64_alphabet[c2 >> 4 | ((c1 & 0x3) << 4)];
		if (saved[0] == 2)
			*outptr++ = base64_alphabet[(c2 & 0x0f) << 2];
		else
			*outptr++ = '=';
		*outptr++ = '=';
		quartets++;
	}

	if (quartets > 0)
		*outptr++ = '\n';

	*state = 0;
	*save = 0;

	return (size_t) (outptr - outbuf);
}

size_t
mk_base64_decode_step (const unsigned char *inbuf, size_t inlen, unsigned char *outbuf, int *state, unsigned int *save)
{
	register const unsigned char *inptr = inbuf;
	const unsigned char *inend = inptr + inlen;
	unsigned char *outptr = outbuf;
	unsigned int saved = *save;
	unsigned char c, rank;
	int n, eq, eof = 0;

	n = *state;

	if (n == -1)
		return 0;

	/* decode every quartet into a triplet */
	while (inptr < inend) {
		rank = base64_rank[(c = *inptr++)];

		if (rank != 0xFF) {
			saved = (saved << 6) | rank;
			n++;

			if (n == 4) {
				*outptr++ = saved >> 16;
				*outptr++ = saved >> 8;
				*outptr++ = saved;
				saved = 0;
				n = 0;
			}
		} else if (c == '=') {
			eof = 1;
			break;
		}
	}

	if (eof) {
		if (n > 1) {
			eq = 4 - n;
			//printf ("eq = %d, outlen = %ld\n", eq, (outptr - outbuf));
			while (n < 4) {
				saved <<= 6;
				n++;
			}

			*outptr++ = saved >> 16;
			if (eq < 2)
				*outptr++ = saved >> 8;
		}

		n = -1;
	}

	/* save state */
	*save = saved;
	*state = n;

	return (size_t) (outptr - outbuf);
}

int main (int argc, char **argv)
{
	uint64_t oldenc = 0, newenc = 0, olddec = 0, newdec = 0;
	unsigned char *input, *output;
	struct stat info;
	size_t sz, nread = 0;
	ssize_t n;
	int i, fd;

	if (argc <= 1)
		return 0;

	if ((fd = open (argv[1], O_RDONLY, 0644)) == -1)
		return -1;

	if (fstat (fd, &info) == -1) {
		close (fd);
		return -1;
	}

	input = malloc (info.st_size);

	do {
		if ((n = read (fd, input + nread, 4096)) <= 0)
			break;

		nread += n;
	} while (nread < info.st_size);

	close (fd);

	output = malloc (GMIME_BASE64_ENCODE_LEN(nread));

	printf ("Pre-warming the cache for GMime's old base64 encoder...\n");
	for (i = 0; i < 3; i++) {
		unsigned int save = 0;
		int state = 0;

		base64_encode_close (input, nread, output, &state, &save);
	}

	printf ("\nBenchmarking GMime's old base64 encoder...\n");
	for (i = 0; i < 10; i++) {
		ztimer_t timer = ZTIMER_INITIALIZER;
		unsigned int save = 0;
		double seconds;
		int state = 0;
		uint64_t usec;

		ZenTimerStart (&timer);
		base64_encode_close (input, nread, output, &state, &save);
		ZenTimerStop (&timer);

		seconds = ZenTimerElapsed (&timer, &usec);
		oldenc += usec;

		printf ("GMime's old base64 encoder took %.6f seconds\n", seconds);
	}

	printf ("\nPre-warming the cache for GMime's new base64 encoder...\n");
	for (i = 0; i < 3; i++) {
		unsigned int save = 0;
		int state = 0;

		sz = mk_base64_encode_close (input, nread, output, &state, &save);
	}

	printf ("\nBenchmarking GMime's new base64 encoder...\n");
	for (i = 0; i < 10; i++) {
		ztimer_t timer = ZTIMER_INITIALIZER;
		unsigned int save = 0;
		double seconds;
		int state = 0;
		uint64_t usec;

		ZenTimerStart (&timer);
		mk_base64_encode_close (input, nread, output, &state, &save);
		ZenTimerStop (&timer);

		seconds = ZenTimerElapsed (&timer, &usec);
		newenc += usec;
		
		printf ("GMime's new base64 encoder took %.6f seconds\n", seconds);
	}

	printf ("\nPre-warming the cache for GMime's old base64 decoder...\n");
	for (i = 0; i < 3; i++) {
		unsigned int save = 0;
		int state = 0;

		base64_decode_step (output, sz, input, &state, &save);
	}

	printf ("\nBenchmarking GMime's old base64 decoder...\n");
	for (i = 0; i < 10; i++) {
		ztimer_t timer = ZTIMER_INITIALIZER;
		unsigned int save = 0;
		double seconds;
		int state = 0;
		uint64_t usec;

		ZenTimerStart (&timer);
		base64_decode_step (output, sz, input, &state, &save);
		ZenTimerStop (&timer);

		seconds = ZenTimerElapsed (&timer, &usec);
		olddec += usec;

		printf ("GMime's old base64 decoder took %.6f seconds\n", seconds);
	}

	printf ("\nPre-warming the cache for GMime's new base64 decoder...\n");
	base64_rank['='] = 0xFF;
	for (i = 0; i < 3; i++) {
		unsigned int save = 0;
		int state = 0;
		size_t x;

		x = mk_base64_decode_step (output, sz, input, &state, &save);

		if (i == 0) {
			if (x != nread)
				printf ("uh oh! output not the same length! %ld != %ld", x, nread);
			
			fd = open ("base64.out", O_RDWR | O_CREAT | O_TRUNC, 0644);
			write (fd, input, x);
			close (fd);
		}
	}

	printf ("\nBenchmarking GMime's new base64 decoder...\n");
	for (i = 0; i < 10; i++) {
		ztimer_t timer = ZTIMER_INITIALIZER;
		unsigned int save = 0;
		double seconds;
		int state = 0;
		uint64_t usec;

		ZenTimerStart (&timer);
		mk_base64_decode_step (output, sz, input, &state, &save);
		ZenTimerStop (&timer);

		seconds = ZenTimerElapsed (&timer, &usec);
		newdec += usec;

		printf ("GMime's old base64 decoder took %.6f seconds\n", seconds);
	}

	free (input);
	free (output);

	printf ("\n");
	printf ("\n");
	printf (" Description | Total seconds | Average runtime |\n");
	printf ("-------------|---------------|-----------------|\n");
	printf (" old encoder |  %.6fs    |  %.6fs      |\n", oldenc / (double) ZTIME_USEC_PER_SEC, (oldenc / (double) ZTIME_USEC_PER_SEC) / 10);
	printf (" new encoder |  %.6fs    |  %.6fs      |\n", newenc / (double) ZTIME_USEC_PER_SEC, (newenc / (double) ZTIME_USEC_PER_SEC) / 10);
	printf (" old decoder |  %.6fs    |  %.6fs      |\n", olddec / (double) ZTIME_USEC_PER_SEC, (olddec / (double) ZTIME_USEC_PER_SEC) / 10);
	printf (" new decoder |  %.6fs    |  %.6fs      |\n", newdec / (double) ZTIME_USEC_PER_SEC, (newdec / (double) ZTIME_USEC_PER_SEC) / 10);

	return 0;
}