Skip to content

Commit ecdb779

Browse files
authored
huff0: Allow building tables from histogram. (#1155)
* huff0: Allow building tables from histogram. Add interface to build tables from the histograms themselves. Adds direct method to export the current table and helpers for size reuse (also via histograms). * Check nil
1 parent 38efa45 commit ecdb779

2 files changed

Lines changed: 395 additions & 0 deletions

File tree

‎huff0/build_table.go‎

Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
package huff0
2+
3+
import "errors"
4+
5+
// BuildCTable builds a Huffman compression table from a precomputed symbol
6+
// histogram and installs it as the previous (reuse) table on s.
7+
//
8+
// After this call:
9+
// - EstimateSize/CanUseTable can probe the table against other histograms.
10+
// - Compress1X/Compress4X with Reuse = ReusePolicyMust will encode without
11+
// emitting a new table header.
12+
// - TransferCTable can hand the table to a sibling Scratch.
13+
//
14+
// count[i] is the number of occurrences of symbol i. The histogram must have
15+
// at least 2 distinct non-zero symbols; ErrUseRLE is returned for a single
16+
// symbol and an error is returned for an empty histogram.
17+
func (s *Scratch) BuildCTable(count *[256]uint32) error {
18+
if s == nil {
19+
return errors.New("huff0: BuildCTable on nil Scratch")
20+
}
21+
if count == nil {
22+
return errors.New("huff0: nil count passed to BuildCTable")
23+
}
24+
var err error
25+
s, err = s.prepare(nil)
26+
if err != nil {
27+
return err
28+
}
29+
s.count = *count
30+
var total, maxCount int
31+
var symLen uint16
32+
for i, v := range s.count {
33+
total += int(v)
34+
if int(v) > maxCount {
35+
maxCount = int(v)
36+
}
37+
if v != 0 {
38+
symLen = uint16(i) + 1
39+
}
40+
}
41+
if total == 0 {
42+
return errors.New("huff0: empty histogram")
43+
}
44+
if symLen < 2 || maxCount == total {
45+
return ErrUseRLE
46+
}
47+
s.symbolLen = symLen
48+
s.maxCount = maxCount
49+
s.srcLen = total
50+
if err := s.buildCTable(); err != nil {
51+
return err
52+
}
53+
if cap(s.prevTable) < len(s.cTable) {
54+
s.prevTable = make(cTable, 0, maxSymbolValue+1)
55+
}
56+
s.prevTable = s.prevTable[:len(s.cTable)]
57+
copy(s.prevTable, s.cTable)
58+
s.prevTableLog = s.actualTableLog
59+
// Force the next Compress* to recount from real input.
60+
s.clearCount = true
61+
s.maxCount = 0
62+
return nil
63+
}
64+
65+
// EstimateSize returns an estimated compressed payload size in bytes for the
66+
// supplied histogram using the table currently stored in prevTable. It returns
67+
// -1 when the table cannot encode every non-zero symbol of hist (i.e. when
68+
// CanUseTable would return false). The estimate excludes the table header.
69+
func (s *Scratch) EstimateSize(hist *[256]uint32) int {
70+
if s == nil || hist == nil || len(s.prevTable) == 0 {
71+
return -1
72+
}
73+
pt := s.prevTable
74+
nbBits := uint32(7)
75+
for i, v := range hist {
76+
if v == 0 {
77+
continue
78+
}
79+
if i >= len(pt) || pt[i].nBits == 0 {
80+
return -1
81+
}
82+
nbBits += uint32(pt[i].nBits) * v
83+
}
84+
return int(nbBits >> 3)
85+
}
86+
87+
// CanUseTable reports whether the table in prevTable can encode every
88+
// non-zero symbol present in hist.
89+
func (s *Scratch) CanUseTable(hist *[256]uint32) bool {
90+
if s == nil || hist == nil || len(s.prevTable) == 0 {
91+
return false
92+
}
93+
pt := s.prevTable
94+
for i, v := range hist {
95+
if v == 0 {
96+
continue
97+
}
98+
if i >= len(pt) || pt[i].nBits == 0 {
99+
return false
100+
}
101+
}
102+
return true
103+
}
104+
105+
// AppendTable serializes the table currently stored in prevTable (e.g. as
106+
// installed by BuildCTable or carried over from a previous Compress call)
107+
// into a self-delimiting zstd-style header and appends it to dst. The
108+
// returned slice can be parsed back by ReadTable.
109+
func (s *Scratch) AppendTable(dst []byte) ([]byte, error) {
110+
if s == nil || len(s.prevTable) == 0 {
111+
return dst, errors.New("huff0: AppendTable with empty table")
112+
}
113+
// cTable.write reads s.actualTableLog, s.symbolLen, s.huffWeight, s.fse
114+
// and writes into s.Out. Save/restore Out so we don't disturb in-flight
115+
// compression buffers.
116+
saveOut := s.Out
117+
saveTL := s.actualTableLog
118+
saveSL := s.symbolLen
119+
if s.fse == nil {
120+
// Lazily init in case AppendTable is called on a fresh Scratch.
121+
if _, err := s.prepare(nil); err != nil {
122+
return dst, err
123+
}
124+
saveOut = s.Out
125+
}
126+
s.Out = s.Out[:0]
127+
s.actualTableLog = s.prevTableLog
128+
s.symbolLen = uint16(len(s.prevTable))
129+
if err := s.prevTable.write(s); err != nil {
130+
s.Out, s.actualTableLog, s.symbolLen = saveOut, saveTL, saveSL
131+
return dst, err
132+
}
133+
dst = append(dst, s.Out...)
134+
s.Out, s.actualTableLog, s.symbolLen = saveOut, saveTL, saveSL
135+
return dst, nil
136+
}

‎huff0/build_table_test.go‎

Lines changed: 259 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,259 @@
1+
package huff0
2+
3+
import (
4+
"bytes"
5+
"errors"
6+
"math/rand"
7+
"testing"
8+
)
9+
10+
func TestBuildCTableSimple(t *testing.T) {
11+
var count [256]uint32
12+
count['a'] = 60
13+
count['b'] = 30
14+
count['c'] = 10
15+
var s Scratch
16+
if err := s.BuildCTable(&count); err != nil {
17+
t.Fatalf("BuildCTable: %v", err)
18+
}
19+
if len(s.prevTable) < 4 {
20+
t.Fatalf("prevTable too short: %d", len(s.prevTable))
21+
}
22+
if s.prevTable['a'].nBits == 0 || s.prevTable['b'].nBits == 0 || s.prevTable['c'].nBits == 0 {
23+
t.Fatalf("expected non-zero nBits for active symbols")
24+
}
25+
// Symbols below the active set are zero in the trimmed prevTable.
26+
if s.prevTable[0].nBits != 0 {
27+
t.Fatalf("expected zero nBits for unused symbol 0")
28+
}
29+
}
30+
31+
func TestBuildCTableEmpty(t *testing.T) {
32+
var count [256]uint32
33+
var s Scratch
34+
if err := s.BuildCTable(&count); err == nil {
35+
t.Fatalf("expected error for empty histogram")
36+
}
37+
}
38+
39+
func TestBuildCTableNilCount(t *testing.T) {
40+
var s Scratch
41+
if err := s.BuildCTable(nil); err == nil {
42+
t.Fatalf("expected error for nil count")
43+
}
44+
}
45+
46+
func TestEstimateSizeAndCanUseTableNilHist(t *testing.T) {
47+
var count [256]uint32
48+
count['a'] = 10
49+
count['b'] = 5
50+
var s Scratch
51+
if err := s.BuildCTable(&count); err != nil {
52+
t.Fatalf("BuildCTable: %v", err)
53+
}
54+
if got := s.EstimateSize(nil); got != -1 {
55+
t.Fatalf("EstimateSize(nil) = %d, want -1", got)
56+
}
57+
if s.CanUseTable(nil) {
58+
t.Fatalf("CanUseTable(nil) = true, want false")
59+
}
60+
// Also exercise the nil-receiver and unloaded-table paths so the guards
61+
// behave even before BuildCTable has installed prevTable.
62+
var empty Scratch
63+
if got := empty.EstimateSize(&count); got != -1 {
64+
t.Fatalf("EstimateSize on empty Scratch = %d, want -1", got)
65+
}
66+
if empty.CanUseTable(&count) {
67+
t.Fatalf("CanUseTable on empty Scratch = true, want false")
68+
}
69+
}
70+
71+
func TestBuildCTableSingleSymbol(t *testing.T) {
72+
var count [256]uint32
73+
count[42] = 100
74+
var s Scratch
75+
if err := s.BuildCTable(&count); !errors.Is(err, ErrUseRLE) {
76+
t.Fatalf("expected ErrUseRLE, got %v", err)
77+
}
78+
}
79+
80+
func TestBuildCTableEstimateAndCanUse(t *testing.T) {
81+
var count [256]uint32
82+
for i := range 32 {
83+
count[i] = uint32(32 - i) // skewed
84+
}
85+
var s Scratch
86+
if err := s.BuildCTable(&count); err != nil {
87+
t.Fatalf("BuildCTable: %v", err)
88+
}
89+
if !s.CanUseTable(&count) {
90+
t.Fatalf("CanUseTable: expected true for source histogram")
91+
}
92+
size := s.EstimateSize(&count)
93+
if size <= 0 {
94+
t.Fatalf("EstimateSize: expected positive, got %d", size)
95+
}
96+
var foreign [256]uint32
97+
foreign[200] = 10 // not in original
98+
if s.CanUseTable(&foreign) {
99+
t.Fatalf("CanUseTable: expected false for foreign histogram")
100+
}
101+
if s.EstimateSize(&foreign) >= 0 {
102+
t.Fatalf("EstimateSize: expected -1 for foreign histogram")
103+
}
104+
}
105+
106+
// TestBuildCTableRoundtrip builds a table from a histogram, then encodes data
107+
// with that prebuilt table (ReusePolicyMust) and verifies the decoder
108+
// reconstructs the input via the standard table-in-stream format.
109+
func TestBuildCTableRoundtrip(t *testing.T) {
110+
rng := rand.New(rand.NewSource(42))
111+
// Generate skewed input bytes (so compression yields meaningful tables).
112+
input := make([]byte, 16<<10)
113+
for i := range input {
114+
// 80% zero, 20% in [1,9]
115+
if rng.Intn(5) == 0 {
116+
input[i] = byte(1 + rng.Intn(9))
117+
}
118+
}
119+
var count [256]uint32
120+
for _, b := range input {
121+
count[b]++
122+
}
123+
124+
var src Scratch
125+
if err := src.BuildCTable(&count); err != nil {
126+
t.Fatalf("BuildCTable: %v", err)
127+
}
128+
129+
// Hand-off the prebuilt table to the encoder via prevTable + ReusePolicyMust.
130+
var enc Scratch
131+
enc.TransferCTable(&src)
132+
enc.Reuse = ReusePolicyMust
133+
134+
out, reused, err := Compress4X(input, &enc)
135+
if err != nil {
136+
t.Fatalf("Compress4X: %v", err)
137+
}
138+
if !reused {
139+
t.Fatalf("expected table reuse")
140+
}
141+
if len(enc.OutTable) != 0 {
142+
t.Fatalf("expected no table emitted on reuse, got %d bytes", len(enc.OutTable))
143+
}
144+
145+
// To verify decompression we have to ship the table to the decoder.
146+
// Encode once more without ReusePolicy to obtain the serialized table,
147+
// then concatenate that header with the reuse-only data above to mimic
148+
// a stream that starts with the table.
149+
var noReuse Scratch
150+
noReuse.Reuse = ReusePolicyNone
151+
if _, _, err := Compress4X(input, &noReuse); err != nil {
152+
t.Fatalf("Compress4X (no reuse): %v", err)
153+
}
154+
if len(noReuse.OutTable) == 0 {
155+
t.Fatalf("expected non-empty OutTable on non-reuse")
156+
}
157+
158+
// Read a decoder-side scratch from the table header.
159+
var dec Scratch
160+
dec.MaxDecodedSize = len(input)
161+
dec2, rem, err := ReadTable(noReuse.OutTable, &dec)
162+
if err != nil {
163+
t.Fatalf("ReadTable: %v", err)
164+
}
165+
if len(rem) != 0 {
166+
t.Fatalf("expected no remainder, got %d", len(rem))
167+
}
168+
169+
got, err := dec2.Decompress4X(out, len(input))
170+
if err != nil {
171+
t.Fatalf("Decompress4X: %v", err)
172+
}
173+
if !bytes.Equal(got, input) {
174+
t.Fatalf("roundtrip mismatch: got len=%d want len=%d", len(got), len(input))
175+
}
176+
}
177+
178+
// TestAppendTableRoundtrip verifies AppendTable produces a header that
179+
// ReadTable can parse, restoring an equivalent table.
180+
func TestAppendTableRoundtrip(t *testing.T) {
181+
var count [256]uint32
182+
rng := rand.New(rand.NewSource(99))
183+
for i := range 64 {
184+
count[i] = uint32(1 + rng.Intn(1000))
185+
}
186+
var src Scratch
187+
if err := src.BuildCTable(&count); err != nil {
188+
t.Fatalf("BuildCTable: %v", err)
189+
}
190+
hdr, err := src.AppendTable(nil)
191+
if err != nil {
192+
t.Fatalf("AppendTable: %v", err)
193+
}
194+
if len(hdr) == 0 {
195+
t.Fatalf("AppendTable produced empty header")
196+
}
197+
var dst Scratch
198+
_, rem, err := ReadTable(hdr, &dst)
199+
if err != nil {
200+
t.Fatalf("ReadTable: %v", err)
201+
}
202+
if len(rem) != 0 {
203+
t.Fatalf("expected no remainder, got %d bytes", len(rem))
204+
}
205+
if dst.prevTableLog != src.prevTableLog {
206+
t.Fatalf("prevTableLog mismatch: src=%d dst=%d", src.prevTableLog, dst.prevTableLog)
207+
}
208+
for i := range count {
209+
if count[i] == 0 {
210+
continue
211+
}
212+
if i >= len(dst.prevTable) || dst.prevTable[i].nBits == 0 {
213+
t.Fatalf("missing symbol %d in roundtripped table", i)
214+
}
215+
}
216+
}
217+
218+
// TestBuildCTableMatchesCompress verifies that BuildCTable followed by reuse
219+
// produces output identical to the table embedded by a regular Compress4X
220+
// call on the same input (modulo the table header).
221+
func TestBuildCTableMatchesCompress(t *testing.T) {
222+
rng := rand.New(rand.NewSource(7))
223+
input := make([]byte, 8<<10)
224+
for i := range input {
225+
input[i] = byte(rng.Intn(16))
226+
}
227+
var ref Scratch
228+
ref.Reuse = ReusePolicyNone
229+
refOut, refReused, err := Compress4X(input, &ref)
230+
if err != nil {
231+
t.Fatalf("ref Compress4X: %v", err)
232+
}
233+
if refReused {
234+
t.Fatalf("ref should not reuse")
235+
}
236+
refData := refOut[len(ref.OutTable):]
237+
238+
var count [256]uint32
239+
for _, b := range input {
240+
count[b]++
241+
}
242+
var built Scratch
243+
if err := built.BuildCTable(&count); err != nil {
244+
t.Fatalf("BuildCTable: %v", err)
245+
}
246+
var enc Scratch
247+
enc.TransferCTable(&built)
248+
enc.Reuse = ReusePolicyMust
249+
out, reused, err := Compress4X(input, &enc)
250+
if err != nil {
251+
t.Fatalf("Compress4X: %v", err)
252+
}
253+
if !reused {
254+
t.Fatalf("expected reuse")
255+
}
256+
if !bytes.Equal(out, refData) {
257+
t.Fatalf("compressed payload mismatch: built=%d ref=%d", len(out), len(refData))
258+
}
259+
}

0 commit comments

Comments
 (0)