-
Notifications
You must be signed in to change notification settings - Fork 1
/
len_limited.go
121 lines (109 loc) · 2.91 KB
/
len_limited.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// Copyright (c) 2023, Intel Corporation.
// SPDX-License-Identifier: BSD-3-Clause
package huffman
// LenLimitedCode implements a code length limited algorithm huffman tree generator.
type LenLimitedCode struct {
counts decLitCounts
lenCounts []int
w []uint32
}
// NewLenLimitedCode creates a new LenLimitedCode instance
func NewLenLimitedCode() *LenLimitedCode {
return &LenLimitedCode{}
}
// Generate huffman tree from histogram and write tree codes into codes.
func (l *LenLimitedCode) Generate(limitedLen int, histogram []uint32, codeLens []uint32) int {
if l.counts == nil {
l.counts = make(decLitCounts, 0, len(histogram)/2)
} else {
l.counts = l.counts[:0]
}
num := 0
for i, v := range histogram {
if v != 0 {
num++
l.counts = append(l.counts, litCount{
lit: uint16(i),
count: uint16(v),
})
}
}
for i := range codeLens {
codeLens[i] = 0
}
sortDecLitCounts(l.counts)
if l.w == nil {
l.w = make([]uint32, len(l.counts), len(histogram))
} else {
l.w = l.w[:len(l.counts)]
}
for i, v := range l.counts {
l.w[i] = uint32(v.count)
}
maxLen := (&MoffatHuffmanCode{}).codeLens(l.w)
if maxLen <= uint32(limitedLen) {
for i, v := range l.w {
codeLens[l.counts[i].lit] = v
}
return num
}
for i, v := range l.w {
codeLens[l.counts[i].lit] = v
}
if l.lenCounts == nil {
l.lenCounts = make([]int, maxLen+1)
} else {
if cap(l.lenCounts) < int(maxLen+1) {
l.lenCounts = make([]int, maxLen+1)
} else {
l.lenCounts = l.lenCounts[:maxLen+1]
for i := range l.lenCounts {
l.lenCounts[i] = 0
}
}
}
for _, v := range l.w {
l.lenCounts[v]++
}
l.enforceMaxLen(l.lenCounts, limitedLen)
idx := 0
for length := 1; length <= limitedLen; length++ {
num := l.lenCounts[length]
for j := 0; j < num; j++ {
codeLens[l.counts[idx].lit] = uint32(length)
idx++
}
}
return num
}
func (l *LenLimitedCode) enforceMaxLen(lenCounts []int, maxLen int) {
// move all oversize length to the maxLen
for i := maxLen + 1; i < len(lenCounts); i++ {
lenCounts[maxLen] += lenCounts[i]
lenCounts[i] = 0
}
// Kraft-McMillan inequality
// https://en.wikipedia.org/wiki/Kraft%E2%80%93McMillan_inequality
// -> sum(2^-length[...]) == 1
// -> sum(2 ^ - length[... ]) * (2 ^ maxLength) == 1 * 2^maxLength
// -> sum(2 ^ (maxLength - length[0]) , ... 2 ^ (maxLength - length[n])) == 2 ^ maxLength
// -> sum(lengthAnum * 2 ^ (maxLength - lengthA),... maxLengthNum * 2 ^ (maxLength - maxLength)) == 2 ^ maxLength
// -> sum(lengthAnum * 2 ^ (maxLength - lengthA),... ) + maxLengthNum == 2 ^ maxLength
// try to make things meet the Kraft-McMillan inequality
total := 0
for i := 1; i <= maxLen; i++ {
total += lenCounts[i] * 1 << (maxLen - i)
}
for total != 1<<maxLen {
// move longest nodes
lenCounts[maxLen]--
for i := maxLen - 1; i > 0; i-- {
if lenCounts[i] != 0 {
lenCounts[i]--
lenCounts[i+1] += 2
break
}
}
total-- // see comments above
}
}