C Base128 Function

Question

What C function do I use to encode/decode a number in LEB128 format? I could not find any simple documentation or examples.

Answer 1

It might interest some readers why LEB128 would be useful. It provides a kind of compression for representing numbers if most of the time the magnitude of the numbers are relatively small. Even on random input, on average it will use 5 out of 8 bytes to represent a 64 bit number (although worst case, it will use 10 bytes).

Below are implementations to encode and decode unsigned 64 bit numbers. I'll leave the signed version as an exercise for the interested reader.

size_t fwrite_uleb128 (FILE *out, uint64_t x) {
    unsigned char buf[10];
    size_t bytes = 0;
    do {
        buf[bytes] = x & 0x7fU;
        if (x >>= 7) buf[bytes] |= 0x80U;
        ++bytes;
    } while (x);
    return fwrite(buf, bytes, 1, out);
}

size_t fread_uleb128 (FILE *in, uint64_t *x) {
    unsigned char buf;
    size_t bytes = 0;
    while (fread(&buf, 1, 1, in)) {
        if (bytes == 0) *x = 0;
        *x |= (buf & 0x7fULL) << (7 * bytes++);
        if (!(buf & 0x80U)) break;
    }
    return !!bytes;
}

Answer 2

From the wikipedia:

A signed number is represented similarly, except that the two's complement number is sign extended up to a multiple of 7 bits (ensuring that the most significant bit is zero for a positive number and one for a negative number). Then the number is broken into groups as for the unsigned encoding.

do {
  byte = low order 7 bits of value;
  value >>= 7;
  if (value != 0) /* more bytes to come */
    set high order bit of byte;
  emit byte;
} while (value != 0);