Variable Length Integer

vli.c

// VARIABLE LENGTH INTEGER encode and decode functions
// Aidan Dodds (c) 2017

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>

#if defined(_MSC_VER)
#define restrict __restrict
#endif

// LSByte emitted first variable length integer
void vli_write(uint64_t in, uint8_t* restrict out);
void vli_read(const uint8_t* restrict in, uint64_t* restrict out);

// MSByte emitted first variable length integer
void vli_write_alt(uint64_t in, uint8_t* restrict out);
void vli_read_alt(const uint8_t* restrict in, uint64_t* restrict out);

enum {
    e_EMASK = 0x00, // MSB mask for end of VLI
    e_CMASK = 0x80, // MSB mask for continuation of VLI
};

void vli_write(uint64_t in, uint8_t* restrict out)
{
    for (;;) {
        const uint8_t mask = (in <= 0x7f) ? e_EMASK : e_CMASK;
        const uint8_t data = (in & 0x7f);
        *(out++) = (data | mask);
        in >>= 7;
        if (mask == e_EMASK) {
            break;
        }
    }
}

void vli_read(const uint8_t* restrict in, uint64_t* restrict out)
{
    uint64_t accum = 0;
    uint64_t shl = 0;
    for (;;) {
        const uint64_t c = *(in++);
        accum |= ((uint64_t)(c & 0x7full)) << shl;
        if ((c & e_CMASK) == 0) {
            break;
        }
        shl += 7;
    }
    *out = accum;
}

void vli_write_alt(uint64_t in, uint8_t* restrict out)
{
    uint64_t accum = in;
    uint32_t places = 1;
    for (; accum > 0x7f; ++places) {
        accum >>= 7;
    }
    for (; places--;) {
        const uint8_t bits = (in >> (7 * places)) & 0x7f;
        *(out++) = (places ? e_CMASK : e_EMASK) | bits;
    }
}

void vli_read_alt(const uint8_t* restrict in, uint64_t* restrict out)
{
    uint64_t accum = 0;
    for (;;) {
        const uint64_t c = *(in++);
        accum = (accum << 7) | (c & 0x7f);
        if ((c & e_CMASK) == 0) {
            break;
        }
    }
    *out = accum;
}

static uint64_t rand64()
{
    static uint64_t x = 0x12345;
    x ^= x >> 12;
    x ^= x << 25;
    x ^= x >> 27;
    return x * 0x2545F4914F6CDD1D;
}

int main()
{
    uint8_t temp[32] = { 0 };
    for (uint64_t i = 0; i < 0xfffffffull; ++i) {
        const uint64_t in = rand64() >> (rand64() % 63);
        uint64_t out = 0;

        vli_write(in, temp);
        vli_read(temp, &out);
        assert(out == in);

        vli_write_alt(in, temp);
        vli_read_alt(temp, &out);
        assert(out == in);
    }
    return 0;
}