File tree Expand file tree Collapse file tree
Expand file tree Collapse file tree Original file line number Diff line number Diff 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
Original file line number Diff line number Diff 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+
3970func TestBuildCTableNilCount (t * testing.T ) {
4071 var s Scratch
4172 if err := s .BuildCTable (nil ); err == nil {
You can’t perform that action at this time.
0 commit comments