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
|
// Copyright (c) 2010, Andrei Vieru. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
package lzma
type rangeBitTreeCoder struct {
models []uint16 // length(models) is at most 1<<8
numBitLevels uint32 // min 2; max 8
}
func newRangeBitTreeCoder(numBitLevels uint32) *rangeBitTreeCoder {
return &rangeBitTreeCoder{
numBitLevels: numBitLevels,
models: initBitModels(1 << numBitLevels),
}
}
func (rc *rangeBitTreeCoder) decode(rd *rangeDecoder) (res uint32) {
res = 1
for bitIndex := rc.numBitLevels; bitIndex != 0; bitIndex-- {
bit := rd.decodeBit(rc.models, res)
res = res<<1 + bit
}
res -= 1 << rc.numBitLevels
return
}
func (rc *rangeBitTreeCoder) reverseDecode(rd *rangeDecoder) (res uint32) {
index := uint32(1)
res = 0
for bitIndex := uint32(0); bitIndex < rc.numBitLevels; bitIndex++ {
bit := rd.decodeBit(rc.models, index)
index <<= 1
index += bit
res |= bit << bitIndex
}
return
}
func reverseDecodeIndex(rd *rangeDecoder, models []uint16, startIndex, numBitModels uint32) (res uint32) {
index := uint32(1)
res = 0
for bitIndex := uint32(0); bitIndex < numBitModels; bitIndex++ {
bit := rd.decodeBit(models, startIndex+index)
index <<= 1
index += bit
res |= bit << bitIndex
}
return
}
func (rc *rangeBitTreeCoder) encode(re *rangeEncoder, symbol uint32) {
m := uint32(1)
for bitIndex := rc.numBitLevels; bitIndex != 0; {
bitIndex--
bit := (symbol >> bitIndex) & 1
re.encode(rc.models, m, bit)
m = m<<1 | bit
}
}
func (rc *rangeBitTreeCoder) reverseEncode(re *rangeEncoder, symbol uint32) {
m := uint32(1)
for i := uint32(0); i < rc.numBitLevels; i++ {
bit := symbol & 1
re.encode(rc.models, m, bit)
m = m<<1 | bit
symbol >>= 1
}
}
func (rc *rangeBitTreeCoder) getPrice(symbol uint32) (res uint32) {
res = 0
m := uint32(1)
for bitIndex := rc.numBitLevels; bitIndex != 0; {
bitIndex--
bit := (symbol >> bitIndex) & 1
res += getPrice(rc.models[m], bit)
m = m<<1 + bit
}
return
}
func (rc *rangeBitTreeCoder) reverseGetPrice(symbol uint32) (res uint32) {
res = 0
m := uint32(1)
for i := rc.numBitLevels; i != 0; i-- {
bit := symbol & 1
symbol >>= 1
res += getPrice(rc.models[m], bit)
m = m<<1 | bit
}
return
}
func reverseGetPriceIndex(models []uint16, startIndex, numBitLevels, symbol uint32) (res uint32) {
res = 0
m := uint32(1)
for i := numBitLevels; i != 0; i-- {
bit := symbol & 1
symbol >>= 1
res += getPrice(models[startIndex+m], bit)
m = m<<1 | bit
}
return
}
func reverseEncodeIndex(re *rangeEncoder, models []uint16, startIndex, numBitLevels, symbol uint32) {
m := uint32(1)
for i := uint32(0); i < numBitLevels; i++ {
bit := symbol & 1
re.encode(models, startIndex+m, bit)
m = m<<1 | bit
symbol >>= 1
}
}
|
