Skip to content

Instantly share code, notes, and snippets.

@jstedfast

jstedfast/base64-benchmarks.c

Last active March 18, 2022 02:38
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save jstedfast/fbce0821c34ad5b3f19e767683528f4a to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save jstedfast/fbce0821c34ad5b3f19e767683528f4a to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. jstedfast revised this gist Mar 18, 2022. 1 changed file with 6 additions and 7 deletions.
    13 changes: 6 additions & 7 deletions base64-benchmarks.c
    View file
    Original file line number Diff line number Diff line change
    @@ -386,24 +386,22 @@ mk_base64_decode_step (const unsigned char *inbuf, size_t inlen, unsigned char *
    saved = (saved << 6) | rank;
    n++;

    if (c == '=') {
    eof = 1;
    break;
    }

    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 > 2) {
    eq = 5 - n;
    if (n > 1) {
    eq = 4 - n;
    //printf ("eq = %d, outlen = %ld\n", eq, (outptr - outbuf));
    while (n < 4) {
    saved <<= 6;
    @@ -537,6 +535,7 @@ int main (int argc, char **argv)
    }

    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;
  2. jstedfast revised this gist Mar 9, 2022. 1 changed file with 2 additions and 48 deletions.
    50 changes: 2 additions & 48 deletions base64-benchmarks.c
    View file
    Original file line number Diff line number Diff line change
    @@ -365,51 +365,6 @@ mk_base64_encode_close (const unsigned char *inbuf, size_t inlen, unsigned char

    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 *previous;
    unsigned char c, rank;
    int n;

    previous = (unsigned char *) state;
    n = (saved >> 24) & 0xFF;

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

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

    if (n == 4) {
    //if (previous[0] != '=') {
    *outptr++ = saved >> 16;
    if (previous[1] != '=') {
    *outptr++ = saved >> 8;
    if (previous[2] != '=')
    *outptr++ = saved;
    }
    //}

    saved = 0;
    n = 0;
    }
    }
    }

    /* save state */
    *save = (n << 24) | (saved & 0x00FFFFFF);

    return (size_t) (outptr - outbuf);
    }

    #if 1
    size_t
    mk2_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;
    @@ -469,7 +424,6 @@ mk2_base64_decode_step (const unsigned char *inbuf, size_t inlen, unsigned char

    return (size_t) (outptr - outbuf);
    }
    #endif

    int main (int argc, char **argv)
    {
    @@ -588,7 +542,7 @@ int main (int argc, char **argv)
    int state = 0;
    size_t x;

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

    if (i == 0) {
    if (x != nread)
    @@ -609,7 +563,7 @@ int main (int argc, char **argv)
    uint64_t usec;

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

    seconds = ZenTimerElapsed (&timer, &usec);
  3. jstedfast created this gist Mar 9, 2022.
    634 changes: 634 additions & 0 deletions base64-benchmarks.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,634 @@
    #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 *previous;
    unsigned char c, rank;
    int n;

    previous = (unsigned char *) state;
    n = (saved >> 24) & 0xFF;

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

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

    if (n == 4) {
    //if (previous[0] != '=') {
    *outptr++ = saved >> 16;
    if (previous[1] != '=') {
    *outptr++ = saved >> 8;
    if (previous[2] != '=')
    *outptr++ = saved;
    }
    //}

    saved = 0;
    n = 0;
    }
    }
    }

    /* save state */
    *save = (n << 24) | (saved & 0x00FFFFFF);

    return (size_t) (outptr - outbuf);
    }

    #if 1
    size_t
    mk2_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 (c == '=') {
    eof = 1;
    break;
    }

    if (n == 4) {
    *outptr++ = saved >> 16;
    *outptr++ = saved >> 8;
    *outptr++ = saved;
    saved = 0;
    n = 0;
    }
    }
    }

    if (eof) {
    if (n > 2) {
    eq = 5 - 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);
    }
    #endif

    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");
    for (i = 0; i < 3; i++) {
    unsigned int save = 0;
    int state = 0;
    size_t x;

    x = mk2_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);
    mk2_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;
    }