Reverse Variable-length Bit-strings for Zig.

RVlBs.zig

/// Reverse Variable-length Bit-strings
///
/// Marshal and unmarshal an integer into a reverse bit-string;
/// that is, written out right-to-left (in cardinality of memory space).
fn ReverseVariableLengthInteger(comptime rbitsint: type) type {
    return struct {
        /// Maximum space needed to store an rbitsint
        pub const maxLen: usize = (rbitsint.bit_count + 6) / 7;

        /// Return the buffer size required to hold an rbitsint value bit-string
        /// representation.
        pub fn size(x: rbitsint) usize {
            if (x == 0) return 1;
            const bits_needed = rbitsint.bit_count - @clz(x);
            return (bits_needed + 6) / 7;
        }

        /// Stores the bit value representation of an rbitsint integer across buf,
        /// starting from the end, preserving the highest bit of each unsigned char
        /// in buf for use as a delimiter. Returns the last part of buf (lowest
        /// unsigned char *) that was written to. If compact is set this will be the
        /// part that holds the highest order bit of size (equal or greater than
        /// buf), otherwise buf.
        pub fn put(buf: []u8, _x: rbitsint, compact: bool) []u8 {
            var x = _x;
            var j = buf.len;
            var last = j - 1;

            // Iterate backwards, storing 7 bits in each byte
            // The highest bit serves as a continuation marker
            while (j > 0) {
                j -= 1;
                const data = @truncate(u7, x);
                buf[j] = data;
                if (data > 0) {
                    last = j;
                }
                x >>= 7;
            }
            if (!compact)
                last = 0;

            // Tag our terminal byte
            buf[last] |= (1 << 7);

            return buf[last..];
        }

        pub fn get(end_pointer: [*]const u8, start: *[*]const u8) usize {
            // Beginning from *end_pointer, work backwards reconstructing the value of an
            // rbitsint integer. Stop when the highest order bit of *end_pointer is set, which
            // should have been previously preserved as a marker. Return the
            // reconstructed value, setting *end to the last position used of end_pointer.
            const full_potential_buf = (end_pointer - maxLen)[0..maxLen];
            var r: rbitsint = 0;
            var j: std.math.IntFittingRange(0, (maxLen - 1) * 7) = 0;
            while (true) : (j += 1) {
                const byte = full_potential_buf[maxLen - j - 1];
                const is_last = (byte & (1 << 7)) != 0; // high bit is continuation bit
                const data = @truncate(u7, byte);
                r |= rbitsint(data) << (j * 7);
                if (is_last)
                    break;
            }

            start.* = full_potential_buf[maxLen - j - 1 ..].ptr;

            return r;
        }
    };
}

test "ReverseVariableLengthInteger" {
    testing.expectEqual(usize(1), ReverseVariableLengthInteger(u1).maxLen);
    testing.expectEqual(usize(1), ReverseVariableLengthInteger(u7).maxLen);
    testing.expectEqual(usize(2), ReverseVariableLengthInteger(u8).maxLen);
    testing.expectEqual(usize(2), ReverseVariableLengthInteger(u9).maxLen);
    testing.expectEqual(usize(2), ReverseVariableLengthInteger(u14).maxLen);
    testing.expectEqual(usize(3), ReverseVariableLengthInteger(u15).maxLen);
    testing.expectEqual(usize(10), ReverseVariableLengthInteger(u64).maxLen);

    const rVLI = ReverseVariableLengthInteger(usize);
    testing.expectEqual(usize(1), rVLI.size(0));
    testing.expectEqual(usize(1), rVLI.size(1));
    testing.expectEqual(usize(1), rVLI.size(50));
    testing.expectEqual(usize(1), rVLI.size(127));
    testing.expectEqual(usize(2), rVLI.size(128));
    testing.expectEqual(usize(2), rVLI.size(256));
    testing.expectEqual(usize(2), rVLI.size(16383));
    testing.expectEqual(usize(3), rVLI.size(16384));
    testing.expectEqual(usize(3), rVLI.size(16385));

    for ([]usize{0, 100, maxInt(usize)}) |testValue| for ([]bool{true, false}) |compact| {
        var buf: [rVLI.maxLen]u8 = undefined;
        const slice = rVLI.put(&buf, testValue, compact);
        var start: [*]u8 = undefined;
        testing.expectEqual(usize(testValue), rVLI.get(buf[0..buf.len].ptr + buf.len, &start));
        testing.expectEqual(slice.ptr, start);
    };
}