huffman_test.gno
5.75 Kb · 181 lines
1package huffman
2
3import (
4 "strings"
5 "testing"
6
7 "gno.land/p/nt/uassert/v0"
8)
9
10// "abracadabra" is the worked example: five symbols, frequencies 5/2/2/1/1,
11// and one optimal length vector (a=1, the other four=3) that no tie-break can
12// change. The canonical codes below are therefore the only correct answer.
13func TestCanonicalTableAbracadabra(t *testing.T) {
14 codes, err := Table("abracadabra")
15 uassert.NoError(t, err)
16 uassert.Equal(t, 5, len(codes))
17
18 wantSymbols := "abcdr"
19 wantBits := []string{"0", "100", "101", "110", "111"}
20 for i, want := range wantBits {
21 uassert.Equal(t, string(wantSymbols[i]), string(codes[i].Symbol))
22 uassert.Equal(t, want, codes[i].String())
23 }
24}
25
26// The table is sorted by (length, symbol), which is what makes it a header a
27// decoder can rebuild from the lengths alone.
28func TestTableIsSortedByLengthThenSymbol(t *testing.T) {
29 codes, err := Table("the quick brown fox jumps over the lazy dog")
30 uassert.NoError(t, err)
31 uassert.True(t, len(codes) > 20, "expected one code per distinct byte")
32 for i := 1; i < len(codes); i++ {
33 prev, cur := codes[i-1], codes[i]
34 ok := prev.Len < cur.Len || (prev.Len == cur.Len && prev.Symbol < cur.Symbol)
35 uassert.True(t, ok, "table out of order")
36 }
37}
38
39func TestEncodeBitStream(t *testing.T) {
40 enc, err := Encode("abracadabra")
41 uassert.NoError(t, err)
42 // 5*1 + 2*3 + 2*3 + 1*3 + 1*3 = 23 bits, against 88 raw.
43 uassert.Equal(t, 23, enc.NBits)
44 uassert.Equal(t, 11, enc.Size)
45 uassert.Equal(t, 3, len(enc.Data)) // 23 bits -> 3 bytes, 1 bit of padding
46 uassert.Equal(t, "01001110101011001001110", enc.BitString())
47}
48
49func TestRoundTrip(t *testing.T) {
50 cases := []string{
51 "a",
52 "aa",
53 "ab",
54 "abracadabra",
55 "hello world",
56 "the quick brown fox jumps over the lazy dog",
57 strings.Repeat("x", 1000),
58 strings.Repeat("ab", 500),
59 "\x00\x01\x02\xff\xfe",
60 }
61 for _, in := range cases {
62 enc, err := Encode(in)
63 uassert.NoError(t, err)
64 got, err := enc.Decode()
65 uassert.NoError(t, err)
66 uassert.Equal(t, in, got)
67 }
68}
69
70// Every byte value exactly once: 256 symbols at equal frequency, so every code
71// is 8 bits long and the encoding saves nothing. The flat case has to work
72// before the skewed one means anything.
73func TestAllByteValues(t *testing.T) {
74 var b strings.Builder
75 for i := 0; i < 256; i++ {
76 b.WriteByte(byte(i))
77 }
78 in := b.String()
79 enc, err := Encode(in)
80 uassert.NoError(t, err)
81 uassert.Equal(t, 256, len(enc.Codes))
82 uassert.Equal(t, 2048, enc.NBits)
83 for _, c := range enc.Codes {
84 uassert.Equal(t, 8, c.Len)
85 }
86 got, err := enc.Decode()
87 uassert.NoError(t, err)
88 uassert.Equal(t, in, got)
89}
90
91// A one-symbol alphabet has no sibling to pair its leaf with. The code is one
92// bit long and the Kraft sum is 1/2, the only incomplete code this package
93// emits.
94func TestSingleSymbol(t *testing.T) {
95 enc, err := Encode("aaaaa")
96 uassert.NoError(t, err)
97 uassert.Equal(t, 1, len(enc.Codes))
98 uassert.Equal(t, 1, enc.Codes[0].Len)
99 uassert.Equal(t, 5, enc.NBits)
100 uassert.Equal(t, "00000", enc.BitString())
101 got, err := enc.Decode()
102 uassert.NoError(t, err)
103 uassert.Equal(t, "aaaaa", got)
104}
105
106func TestEmptyInput(t *testing.T) {
107 _, err := Encode("")
108 uassert.ErrorIs(t, err, ErrEmpty)
109 _, err = Table("")
110 uassert.ErrorIs(t, err, ErrEmpty)
111}
112
113func TestTooLong(t *testing.T) {
114 _, err := Encode(strings.Repeat("a", MaxLen+1))
115 uassert.ErrorIs(t, err, ErrTooLong)
116}
117
118// Decode rebuilds the canonical codes from the lengths it is handed and
119// refuses a payload whose own Bits disagree, because a decoder that trusts
120// both fields returns a different string than the one that was encoded.
121func TestDecodeRejectsCorruptPayloads(t *testing.T) {
122 good, err := Encode("abracadabra")
123 uassert.NoError(t, err)
124
125 cases := []struct {
126 name string
127 mutate func(e *Encoded)
128 }{
129 {"no codes", func(e *Encoded) { e.Codes = nil }},
130 {"zero length", func(e *Encoded) { e.Codes[0].Len = 0 }},
131 {"bits disagree with the canonical table", func(e *Encoded) { e.Codes[1].Bits = 7 }},
132 {"table out of order", func(e *Encoded) { e.Codes[0], e.Codes[1] = e.Codes[1], e.Codes[0] }},
133 {"duplicate symbol", func(e *Encoded) { e.Codes[2].Symbol = e.Codes[1].Symbol }},
134 {"duplicate symbol at another length", func(e *Encoded) { e.Codes[1].Symbol = e.Codes[0].Symbol }},
135 {"more bits than data", func(e *Encoded) { e.NBits = len(e.Data)*8 + 1 }},
136 {"truncated stream", func(e *Encoded) { e.NBits = 2 }},
137 {"size disagrees", func(e *Encoded) { e.Size = 3 }},
138 {"incomplete code", func(e *Encoded) { e.Codes = e.Codes[:4] }},
139 {"empty payload", func(e *Encoded) { e.NBits, e.Size = 0, 0 }},
140 {"padding bits are not zero", func(e *Encoded) { e.Data[len(e.Data)-1] |= 1 }},
141 }
142 for _, c := range cases {
143 e := &Encoded{
144 Codes: append([]Code(nil), good.Codes...),
145 Data: append([]byte(nil), good.Data...),
146 NBits: good.NBits,
147 Size: good.Size,
148 }
149 c.mutate(e)
150 _, err := e.Decode()
151 uassert.ErrorIs(t, err, ErrCorrupt, c.name)
152 }
153}
154
155// Same input, same table, every time: a Render built on this cannot reshuffle
156// between two identical calls.
157func TestDeterministic(t *testing.T) {
158 a, err := Encode("mississippi")
159 uassert.NoError(t, err)
160 b, err := Encode("mississippi")
161 uassert.NoError(t, err)
162 uassert.Equal(t, a.NBits, b.NBits)
163 uassert.Equal(t, a.BitString(), b.BitString())
164 uassert.Equal(t, len(a.Codes), len(b.Codes))
165 for i := range a.Codes {
166 uassert.Equal(t, a.Codes[i].String(), b.Codes[i].String())
167 }
168}
169
170// The skew is the whole point: a frequency-flat input saves little, a skewed
171// one saves most of its bits.
172func TestSaved(t *testing.T) {
173 flat, err := Encode("abcd")
174 uassert.NoError(t, err)
175 uassert.Equal(t, 8, flat.NBits) // four 2-bit codes
176 uassert.Equal(t, 24, flat.Saved())
177
178 skewed, err := Encode(strings.Repeat("a", 60) + "bcd")
179 uassert.NoError(t, err)
180 uassert.True(t, skewed.Saved() > 400, "a skewed input must save most of its bits")
181}
