Variable-sized integer encoding (32-bit)

varint.c

#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

size_t varint_size(uint32_t value) {
    return value < 0x80 ? 1 :
           value < 0x4000 ? 2 :
           value < 0x200000 ? 3 :
           value < 0x10000000 ? 4 : 5;
}

size_t varint_size_fast(uint32_t value) {
    return (31 - __builtin_clz(value | 1)) / 7 + 1;
}

uint8_t *varint_write(uint32_t value, uint8_t *pout) {
    for (int i = 0; i < 5; i++) {
        uint8_t outv = value & 0x7f;
        value >>= 7;
        if (!value) {
            *pout++ = outv;
            break;
        }
        *pout++ = outv | 0x80;
    }
    return pout;
}

uint32_t varint_read(uint8_t *pin) {
    uint32_t value = 0;
    for (uint32_t shift = 0; shift <= 7*4; shift += 7) {
        uint32_t inv = *pin++;
        value |= (inv & 0x7f) << shift;
        if ((inv & 0x80) == 0) break;
    }
    return value;
}

int main() {
    // exhaustive test, takes a few of minutes to run
    uint32_t value = 0;
    do {
        uint8_t buf[5];
        memset(buf, 0, sizeof(buf));
        assert(varint_write(value, buf) == buf + varint_size(value));
        assert(varint_read(buf) == value);
        assert(varint_size_fast(value) == varint_size(value));
    } while (++value != 0);
    return 0;
}