Skip to content

Commit e9c2e56

Browse files
authored
huff0: Allow building table from oversized histogram. (#1156)
A histogram of a block larger than max block size could cause huff0 to panic. Scale table down on BuildCTable.
1 parent ecdb779 commit e9c2e56

2 files changed

Lines changed: 63 additions & 0 deletions

File tree

‎huff0/build_table.go‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,38 @@ func (s *Scratch) BuildCTable(count *[256]uint32) error {
4444
if symLen < 2 || maxCount == total {
4545
return ErrUseRLE
4646
}
47+
// huff0's internal rank table assumes total ≤ BlockSizeMax (it uses
48+
// highBit32(count+1) + 1 as a rank index into a fixed-size array).
49+
// Histograms summed across multiple blocks can exceed that; scale the
50+
// counts down preserving the distribution. Non-zero entries round up so
51+
// rare symbols stay representable.
52+
if total > BlockSizeMax {
53+
shift := uint(0)
54+
for total>>shift > BlockSizeMax {
55+
shift++
56+
}
57+
round := uint32(1<<shift) - 1
58+
var newTotal, newMax int
59+
for i, v := range s.count {
60+
if v == 0 {
61+
continue
62+
}
63+
scaled := (v + round) >> shift
64+
if scaled == 0 {
65+
scaled = 1
66+
}
67+
s.count[i] = scaled
68+
newTotal += int(scaled)
69+
if int(scaled) > newMax {
70+
newMax = int(scaled)
71+
}
72+
}
73+
total = newTotal
74+
maxCount = newMax
75+
if maxCount == total {
76+
return ErrUseRLE
77+
}
78+
}
4779
s.symbolLen = symLen
4880
s.maxCount = maxCount
4981
s.srcLen = total

‎huff0/build_table_test.go‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,37 @@ func TestBuildCTableEmpty(t *testing.T) {
3636
}
3737
}
3838

39+
// TestBuildCTableOversizedTotal exercises histograms that sum to more than
40+
// huff0's internal BlockSizeMax — the case that arises when summing the
41+
// per-block histograms of a multi-block bitmap. Without scaling, huffSort
42+
// places nodes at out-of-range rank indices and buildCTable panics on a
43+
// negative index.
44+
func TestBuildCTableOversizedTotal(t *testing.T) {
45+
var count [256]uint32
46+
// 4 MB of one dominant symbol, plus a handful of rare singletons.
47+
count[0] = 4 << 20
48+
count[1] = 2
49+
count[2] = 1
50+
count[128] = 1
51+
count[255] = 3
52+
var s Scratch
53+
if err := s.BuildCTable(&count); err != nil {
54+
t.Fatalf("BuildCTable: %v", err)
55+
}
56+
if len(s.prevTable) == 0 {
57+
t.Fatalf("prevTable not installed")
58+
}
59+
// Every originally non-zero symbol must be representable.
60+
for i, v := range count {
61+
if v == 0 {
62+
continue
63+
}
64+
if i >= len(s.prevTable) || s.prevTable[i].nBits == 0 {
65+
t.Fatalf("symbol %d lost during scaling", i)
66+
}
67+
}
68+
}
69+
3970
func TestBuildCTableNilCount(t *testing.T) {
4071
var s Scratch
4172
if err := s.BuildCTable(nil); err == nil {

0 commit comments

Comments
 (0)