Bit I/O and universal codes: make the state visible

A coder returns meaningful bits; a byte container adds padding. Confusing these two lengths is a framing bug. This pack uses MSB-first packing consistently: the first stream bit occupies byte bit 7. This convention is local to the pack; real formats can choose other conventions.

Write across a byte boundary

Keep complete bytes, a pending byte cur, and a count used from 0 through 7. To append bit b, set cur |= (b&1) << (7-used), increment used, and flush/reset at eight. WriteBits(value,n) visits positions n-1 down through zero; higher bits of value are ignored.

Write three bits of 5, then seven bits of 75:

Event	Meaningful stream	Complete bytes	Pending byte / used
WriteBits(5,3)	101	none	10100000 / 3
First five bits of 75	10110010	10110010	00000000 / 0
Full second call	1011001011	10110010	11000000 / 2

Concatenation gives 10110010 (b2) for the complete byte. The final output is b2 c0. Tracking positions catches an off-by-one before a matching buggy reader can hide it.

Bytes() returns a copy, including a zero-padded snapshot of any pending byte. It must not flush or mutate the logical writer state. Calling it after three bits and then writing more continues in that same pending byte. Changing the returned slice must not change later snapshots.

Read and distinguish exhaustion from zero

Keep (byteIndex,used). A bit is (data[byteIndex] >> (7-used)) & 1; advance the cursor after reading it. Accumulate n bits with value=(value<<1)|bit. A zero bit with ok=true is data; ok=false means physical exhaustion.

A reader given b2 c0 sees all 16 physical bits, including six padding zeros. The generic reader has no original logical length. A caller must know a count, decode one self-delimiting value, or recognize an end symbol. Do not stop at the first zero: zero is valid data. The exercise does not require restoring the cursor after an unsuccessful multi-bit read.

Derive gamma and delta for one integer

For positive n, let L be its binary length. Gamma writes L-1 zeros followed by all L bits of n. The leading zeros tell the decoder exactly how many suffix bits to read after the first one.

For n=10, binary is 1010, L=4. Gamma is 000|1010, seven bits, padded as 00010100 (14). Decoding counts three zeros, starts value at 1, and consumes 010: values 2, 5, 10.

Delta encodes L with gamma, then appends only n's lower L-1 bits. For n=10, gamma(4) is 00100; append 010, yielding 00100010 (22). Here delta is longer than gamma. Delta reduces asymptotic overhead for large numbers; it does not always win.

gamma length = 2L - 1
delta length = L + 2*floor(log2 L)

For n=1 both codes are a single one bit (80 after padding). Zero is outside their input domain. When decoding into uint64, reject gamma prefixes longer than 63 zeros and delta lengths greater than 64 before shifting: otherwise an invalid large integer can wrap into an apparently valid small value.

This exercise decodes one codeword and requires all remaining bits to be zero. Padding has no separate count; extra complete zero bytes are therefore indistinguishable from longer padding. A sequence format would need a count or another framing rule, and should decode several codewords from one shared bit cursor instead of concatenating independently padded byte arrays.

Test a convention, not just inversion

Independent bytes for gamma(10)=14 and delta(10)=22 catch shared bit-order bugs. Also check reads crossing bytes, repeated snapshots, n=1, the largest uint64, truncated suffixes, and a trailing one after a complete codeword. Round trips are useful but cannot establish interoperability when both sides share the same error.

Reconstruct it

1. Write 4 bits of 10 and 5 bits of 19. Which two bytes result?
2. How many bits does gamma use for 31? Delta?
3. Is an all-zero byte a valid gamma codeword?

Model answers

1. 1010|10011 becomes a9 80.
2. L=5: gamma uses 9; delta uses 5+2*2=9.
3. No. It never supplies the one that terminates the prefix.

Implement Bitstream I/O and Elias codes. The precise padding and error rules are exercise contracts; the next module consumes these bit operations without redefining them.