1//! Effectively a stack of u1 values implemented using ArrayList(u8).
2
3const BitStack = @This();
4
5const std = @import("std");
6const Allocator = std.mem.Allocator;
7const ArrayList = std.array_list.Managed;
8
9bytes: std.array_list.Managed(u8),
10bit_len: usize = 0,
11
12pub fn init(allocator: Allocator) @This() {
13 return .{
14 .bytes = std.array_list.Managed(u8).init(allocator),
15 };
16}
17
18pub fn deinit(self: *@This()) void {
19 self.bytes.deinit();
20 self.* = undefined;
21}
22
23pub fn ensureTotalCapacity(self: *@This(), bit_capacity: usize) Allocator.Error!void {
24 const byte_capacity = (bit_capacity + 7) >> 3;
25 try self.bytes.ensureTotalCapacity(byte_capacity);
26}
27
28pub fn push(self: *@This(), b: u1) Allocator.Error!void {
29 const byte_index = self.bit_len >> 3;
30 if (self.bytes.items.len <= byte_index) {
31 try self.bytes.append(0);
32 }
33
34 pushWithStateAssumeCapacity(self.bytes.items, &self.bit_len, b);
35}
36
37pub fn peek(self: *const @This()) u1 {
38 return peekWithState(self.bytes.items, self.bit_len);
39}
40
41pub fn pop(self: *@This()) u1 {
42 return popWithState(self.bytes.items, &self.bit_len);
43}
44
45/// Standalone function for working with a fixed-size buffer.
46pub fn pushWithStateAssumeCapacity(buf: []u8, bit_len: *usize, b: u1) void {
47 const byte_index = bit_len.* >> 3;
48 const bit_index = @as(u3, @intCast(bit_len.* & 7));
49
50 buf[byte_index] &= ~(@as(u8, 1) << bit_index);
51 buf[byte_index] |= @as(u8, b) << bit_index;
52
53 bit_len.* += 1;
54}
55
56/// Standalone function for working with a fixed-size buffer.
57pub fn peekWithState(buf: []const u8, bit_len: usize) u1 {
58 const byte_index = (bit_len - 1) >> 3;
59 const bit_index = @as(u3, @intCast((bit_len - 1) & 7));
60 return @as(u1, @intCast((buf[byte_index] >> bit_index) & 1));
61}
62
63/// Standalone function for working with a fixed-size buffer.
64pub fn popWithState(buf: []const u8, bit_len: *usize) u1 {
65 const b = peekWithState(buf, bit_len.*);
66 bit_len.* -= 1;
67 return b;
68}
69
70const testing = std.testing;
71test BitStack {
72 var stack = BitStack.init(testing.allocator);
73 defer stack.deinit();
74
75 try stack.push(1);
76 try stack.push(0);
77 try stack.push(0);
78 try stack.push(1);
79
80 try testing.expectEqual(@as(u1, 1), stack.peek());
81 try testing.expectEqual(@as(u1, 1), stack.pop());
82 try testing.expectEqual(@as(u1, 0), stack.peek());
83 try testing.expectEqual(@as(u1, 0), stack.pop());
84 try testing.expectEqual(@as(u1, 0), stack.pop());
85 try testing.expectEqual(@as(u1, 1), stack.pop());
86}