4 ms·

Can you please explain how you'd use "bijective numeration" specifically? What do you think has to be changed or added to your proposal: 7 bits -> 0xxxxxxx

• KMag 11y ago
  For a bijective base: 7 bits -> Decode 0xxxxxxx and add 0 (unchanged) 14 bits -> Decode 10xxxxxx xxxxxxxx and add 0x80 21 bits -> Decode 110xxxxx xxxxxxxx xxxxxxxx and add 0x4080 In a non-bijective base vs a bijective base: 7 bits encode 0 to 2&7 - 1 vs. 0 to 2^7 -1 14 bits encode 0 to 2^14 - 1 vs. 2^7 to 2^14 + 2^7 - 1 21 bits encode 0 to 2^21 - 1 vs. 2^14 + 2^7 to 2^21 + 2^14 + 2^7 - 1 ... In the bijective decoding routine, you need to special-case the maximum length case to check for numeric overflow.
  • deleted 11y ago
    [deleted]
  • deleted 11y ago
    [deleted]
• KMag 11y ago
  A real implementation would probably be switch-driven, but I whipped up a terse implementation for a big-endian bijective encoder to go with my other comment (tested, but test code omitted): int varint_u64_encode(uint8_t** start, const uint8_t* limit, uint64_t value) { uint64_t offset; uint8_t* position; int bytes; for (bytes = 1, offset = 0x80; value >= offset && bytes < 9; ++bytes) { offset = (offset << 7 ) | 0x80; } position = *start; value -= ( offset >> 7 ) ^ 1; if (position + bytes > limit) {return 0; /* not enough space */} *position = (((uint8_t)0xFF) << (9-bytes)) | (uint8_t)(value >> ((bytes-1) * 8 )); for (++position; --bytes > 0; ++position) { *position = (uint8_t) (value >> ((bytes-1) * 8)); } *start = position; return 1; } int varint_u64_decode(const uint8_t** start, const uint8_t* limit, uint64_t* result) { uint64_t value; uint64_t offset; const uint8_t* position; int bytes; uint8_t mask; position = *start; offset = 0; for(bytes=1, mask = 0x80; (mask & *position) == mask && bytes < 9; ++bytes) { mask = 0x80 | (mask >> 1); offset = (offset << 7) | 0x80; } if (position + bytes > limit) { return 0; /* not enough space */} value = (~mask) & *position; ++ position; for(; --bytes > 0; ++position) { value = (value << 8) + *position; } value += offset; if (bytes == 9 && value < (1uLL << 56)) {return 0; /* overflow, non-canonical encoding */ } *result = value; *start = position; return 1; }