Something went wrong. Try again.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253//! Golomb codec implementation for encoding and decoding integers.//! Golomb coding is a lossless, variable-length encoding scheme that is optimal for geometric distributions.
const std = @import("std");
const Self = @This();
/// Golomb parameter M - determines the division point for quotient and remainderm: usize,
/// Internal bit buffer for accumulating bits during encoding/decodingbit_buffer: u8 = 0,/// Current bit position within the bit buffer (0-7)bit_idx: u8 = 0,/// Current byte position in the bufferbyte_idx: usize = 0,
/// Encodes a value using Golomb coding into the provided buffer./// Returns the number of bits written.pub fn encode( self: *Self, buffer: []u8, value: usize, opts: struct { write_padding_bits: bool = false, reset_tmp_values: bool = true, },) error{BufferTooSmall}!usize { if (self.m == 0) @panic("The Golomb parameter M must be larger than 0");
const b_m = self.bM();
const q = @divFloor(value, self.m) + 1; const b_q = bitLength(q) - 1; const r = @rem(value, self.m); const b_r = bitLength(r);
const needed_bits = b_q + b_q + 1 + b_m; const buffer_len_bits = needed_bits + self.byte_idx * 8 + self.bit_idx;
if (buffer_len_bits > buffer.len * 8) return error.BufferTooSmall;
// Write q for (0..b_q) |_| { self.writeBit(buffer, 0); } self.writeBits(buffer, q, b_q + 1);
// Write r for (0..(b_m - b_r)) |_| { self.writeBit(buffer, 0); } self.writeBits(buffer, r, b_r);
// Write padding bits if (opts.write_padding_bits) { const padding = buffer.len * 8 - buffer_len_bits;
for (0..padding) |_| { self.writeBit(buffer, 0); }
std.debug.assert(self.bit_buffer == 0); }
// Reset helper vars if (opts.reset_tmp_values) { self.reset(); }
return buffer_len_bits;}
/// Decodes a Golomb-encoded value from the buffer./// Returns the decoded value.pub fn decode( self: *Self, buffer: []const u8, opts: struct { reset_tmp_values: bool = true },) error{InvalidFormat}!usize { if (self.m == 0) @panic("The Golomb parameter M must be larger than 0");
const b_m = self.bM();
var q: usize = 0; var b_q: u8 = 0; var r: usize = 0;
// Read b_q while (self.readBit(buffer)) |bit| { if (bit == 0) { b_q += 1; } else if (bit == 1) { q = 1; break; } else { return error.InvalidFormat; } }
// Read q q <<= @as(u6, @intCast(b_q)); q |= self.readBits(buffer, b_q) catch return error.InvalidFormat; q -= 1;
// Read r r = self.readBits(buffer, b_m) catch return error.InvalidFormat;
// Reset helper vars if (opts.reset_tmp_values) { self.reset(); }
return q * self.m + r;}
/// Resets internal state variables used during encoding/decoding.pub fn reset(self: *Self) void { self.bit_buffer = 0; self.bit_idx = 0; self.byte_idx = 0;}
/// Calculates the number of bits needed to represent the remainder in Golomb coding.fn bM(self: *const Self) u8 { const b = bitLength(self.m); return if (isPowerOfTwo(self.m)) b - 1 else b;}
/// Writes a single bit to the buffer.fn writeBit(self: *Self, buffer: []u8, bit: u8) void { self.bit_buffer = (self.bit_buffer << 1) | (bit & 1); self.bit_idx += 1;
if (self.bit_idx == 8) { buffer[self.byte_idx] = self.bit_buffer; self.byte_idx += 1; self.bit_buffer = 0; self.bit_idx = 0; }}
/// Writes multiple bits from a value to the buffer.fn writeBits(self: *Self, buffer: []u8, value: usize, count: u8) void { var i = count; while (i > 0) { i -= 1; const bit = @as(u8, @intCast((value >> @as(u6, @intCast(i))) & 1)); self.writeBit(buffer, bit); }}
/// Reads a single bit from the buffer. Returns null if at end of buffer.fn readBit(self: *Self, buffer: []const u8) ?u8 { if (self.byte_idx > buffer.len) return null;
const bit = (buffer[self.byte_idx] >> @as(u3, @intCast(7 - self.bit_idx))) & 1; self.bit_idx += 1;
if (self.bit_idx == 8) { self.byte_idx += 1; self.bit_idx = 0; }
return bit;}
/// Reads multiple bits from the buffer and returns them as a value.fn readBits(self: *Self, buffer: []const u8, count: u8) !usize { var result: usize = 0;
for (0..count) |_| { const bit = self.readBit(buffer) orelse return error.OutOfBounds; result = (result << 1) | @as(usize, bit); }
return result;}
/// Calculates the number of bits required to represent a value.fn bitLength(value: anytype) u8 { return @bitSizeOf(@TypeOf(value)) - @clz(value);}
/// Checks if a value is a power of two.fn isPowerOfTwo(value: usize) bool { return (value & (value - 1)) == 0;}
test "golomb.encode val = 42, m = 8" { const testing = std.testing;
var gol = Self{ .m = 8 }; const input: usize = 42; var encoded: [1]u8 = undefined; _ = try gol.encode(&encoded, input, .{}); try testing.expectEqualSlices(u8, &.{50}, &encoded);}
test "golomb.decode val = {50}, m = 8" { const testing = std.testing;
var gol = Self{ .m = 8 }; const input = &[_]u8{50}; const decoded = try gol.decode(input, .{});
try testing.expectEqual(42, decoded);}
test "golomb.encode + decode val = 1564, m = 457" { const testing = std.testing;
var gol = Self{ .m = 457 }; const input: usize = 1564; var encoded: [2]u8 = undefined;
_ = try gol.encode( &encoded, input, .{ .write_padding_bits = true }, ); try testing.expectEqualSlices(u8, &.{ 35, 4 }, &encoded);
const decoded = try gol.decode(&encoded, .{}); try testing.expectEqual(input, decoded);}
test "golomb.encode multiple val = { 1564, 42 }, m = 457" { const testing = std.testing;
var gol = Self{ .m = 457 }; const input = [_]usize{ 1564, 42 }; var encoded: [3]u8 = undefined;
_ = try gol.encode(&encoded, input[0], .{ .reset_tmp_values = false }); _ = try gol.encode(&encoded, input[1], .{});
try testing.expectEqualSlices(u8, &.{ 35, 6, 42 }, &encoded);}
test "golomb.decode multiple val = { 35, 6, 8 }, m = 457" { const testing = std.testing;
var gol = Self{ .m = 457 }; const input = &[_]u8{ 35, 6, 42 };
const decoded1 = try gol.decode(input, .{ .reset_tmp_values = false }); try testing.expectEqual(1564, decoded1);
const decoded2 = try gol.decode(input, .{}); try testing.expectEqual(42, decoded2);}