cubefs

1
// Copyright 2018 Klaus Post. All rights reserved.
2
// Use of this source code is governed by a BSD-style
3
// license that can be found in the LICENSE file.
4
// Based on work Copyright (c) 2013, Yann Collet, released under BSD License.
5

6
package huff0
7

8
import "fmt"
9

10
// bitWriter will write bits.
11
// First bit will be LSB of the first byte of output.
12
type bitWriter struct {
13
	bitContainer uint64
14
	nBits        uint8
15
	out          []byte
16
}
17

18
// bitMask16 is bitmasks. Has extra to avoid bounds check.
19
var bitMask16 = [32]uint16{
20
	0, 1, 3, 7, 0xF, 0x1F,
21
	0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF,
22
	0xFFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF, 0xFFFF,
23
	0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF, 0xFFFF,
24
	0xFFFF, 0xFFFF} /* up to 16 bits */
25

26
// addBits16NC will add up to 16 bits.
27
// It will not check if there is space for them,
28
// so the caller must ensure that it has flushed recently.
29
func (b *bitWriter) addBits16NC(value uint16, bits uint8) {
30
	b.bitContainer |= uint64(value&bitMask16[bits&31]) << (b.nBits & 63)
31
	b.nBits += bits
32
}
33

34
// addBits16Clean will add up to 16 bits. value may not contain more set bits than indicated.
35
// It will not check if there is space for them, so the caller must ensure that it has flushed recently.
36
func (b *bitWriter) addBits16Clean(value uint16, bits uint8) {
37
	b.bitContainer |= uint64(value) << (b.nBits & 63)
38
	b.nBits += bits
39
}
40

41
// encSymbol will add up to 16 bits. value may not contain more set bits than indicated.
42
// It will not check if there is space for them, so the caller must ensure that it has flushed recently.
43
func (b *bitWriter) encSymbol(ct cTable, symbol byte) {
44
	enc := ct[symbol]
45
	b.bitContainer |= uint64(enc.val) << (b.nBits & 63)
46
	if false {
47
		if enc.nBits == 0 {
48
			panic("nbits 0")
49
		}
50
	}
51
	b.nBits += enc.nBits
52
}
53

54
// encTwoSymbols will add up to 32 bits. value may not contain more set bits than indicated.
55
// It will not check if there is space for them, so the caller must ensure that it has flushed recently.
56
func (b *bitWriter) encTwoSymbols(ct cTable, av, bv byte) {
57
	encA := ct[av]
58
	encB := ct[bv]
59
	sh := b.nBits & 63
60
	combined := uint64(encA.val) | (uint64(encB.val) << (encA.nBits & 63))
61
	b.bitContainer |= combined << sh
62
	if false {
63
		if encA.nBits == 0 {
64
			panic("nbitsA 0")
65
		}
66
		if encB.nBits == 0 {
67
			panic("nbitsB 0")
68
		}
69
	}
70
	b.nBits += encA.nBits + encB.nBits
71
}
72

73
// addBits16ZeroNC will add up to 16 bits.
74
// It will not check if there is space for them,
75
// so the caller must ensure that it has flushed recently.
76
// This is fastest if bits can be zero.
77
func (b *bitWriter) addBits16ZeroNC(value uint16, bits uint8) {
78
	if bits == 0 {
79
		return
80
	}
81
	value <<= (16 - bits) & 15
82
	value >>= (16 - bits) & 15
83
	b.bitContainer |= uint64(value) << (b.nBits & 63)
84
	b.nBits += bits
85
}
86

87
// flush will flush all pending full bytes.
88
// There will be at least 56 bits available for writing when this has been called.
89
// Using flush32 is faster, but leaves less space for writing.
90
func (b *bitWriter) flush() {
91
	v := b.nBits >> 3
92
	switch v {
93
	case 0:
94
		return
95
	case 1:
96
		b.out = append(b.out,
97
			byte(b.bitContainer),
98
		)
99
		b.bitContainer >>= 1 << 3
100
	case 2:
101
		b.out = append(b.out,
102
			byte(b.bitContainer),
103
			byte(b.bitContainer>>8),
104
		)
105
		b.bitContainer >>= 2 << 3
106
	case 3:
107
		b.out = append(b.out,
108
			byte(b.bitContainer),
109
			byte(b.bitContainer>>8),
110
			byte(b.bitContainer>>16),
111
		)
112
		b.bitContainer >>= 3 << 3
113
	case 4:
114
		b.out = append(b.out,
115
			byte(b.bitContainer),
116
			byte(b.bitContainer>>8),
117
			byte(b.bitContainer>>16),
118
			byte(b.bitContainer>>24),
119
		)
120
		b.bitContainer >>= 4 << 3
121
	case 5:
122
		b.out = append(b.out,
123
			byte(b.bitContainer),
124
			byte(b.bitContainer>>8),
125
			byte(b.bitContainer>>16),
126
			byte(b.bitContainer>>24),
127
			byte(b.bitContainer>>32),
128
		)
129
		b.bitContainer >>= 5 << 3
130
	case 6:
131
		b.out = append(b.out,
132
			byte(b.bitContainer),
133
			byte(b.bitContainer>>8),
134
			byte(b.bitContainer>>16),
135
			byte(b.bitContainer>>24),
136
			byte(b.bitContainer>>32),
137
			byte(b.bitContainer>>40),
138
		)
139
		b.bitContainer >>= 6 << 3
140
	case 7:
141
		b.out = append(b.out,
142
			byte(b.bitContainer),
143
			byte(b.bitContainer>>8),
144
			byte(b.bitContainer>>16),
145
			byte(b.bitContainer>>24),
146
			byte(b.bitContainer>>32),
147
			byte(b.bitContainer>>40),
148
			byte(b.bitContainer>>48),
149
		)
150
		b.bitContainer >>= 7 << 3
151
	case 8:
152
		b.out = append(b.out,
153
			byte(b.bitContainer),
154
			byte(b.bitContainer>>8),
155
			byte(b.bitContainer>>16),
156
			byte(b.bitContainer>>24),
157
			byte(b.bitContainer>>32),
158
			byte(b.bitContainer>>40),
159
			byte(b.bitContainer>>48),
160
			byte(b.bitContainer>>56),
161
		)
162
		b.bitContainer = 0
163
		b.nBits = 0
164
		return
165
	default:
166
		panic(fmt.Errorf("bits (%d) > 64", b.nBits))
167
	}
168
	b.nBits &= 7
169
}
170

171
// flush32 will flush out, so there are at least 32 bits available for writing.
172
func (b *bitWriter) flush32() {
173
	if b.nBits < 32 {
174
		return
175
	}
176
	b.out = append(b.out,
177
		byte(b.bitContainer),
178
		byte(b.bitContainer>>8),
179
		byte(b.bitContainer>>16),
180
		byte(b.bitContainer>>24))
181
	b.nBits -= 32
182
	b.bitContainer >>= 32
183
}
184

185
// flushAlign will flush remaining full bytes and align to next byte boundary.
186
func (b *bitWriter) flushAlign() {
187
	nbBytes := (b.nBits + 7) >> 3
188
	for i := uint8(0); i < nbBytes; i++ {
189
		b.out = append(b.out, byte(b.bitContainer>>(i*8)))
190
	}
191
	b.nBits = 0
192
	b.bitContainer = 0
193
}
194

195
// close will write the alignment bit and write the final byte(s)
196
// to the output.
197
func (b *bitWriter) close() error {
198
	// End mark
199
	b.addBits16Clean(1, 1)
200
	// flush until next byte.
201
	b.flushAlign()
202
	return nil
203
}
204

205
// reset and continue writing by appending to out.
206
func (b *bitWriter) reset(out []byte) {
207
	b.bitContainer = 0
208
	b.nBits = 0
209
	b.out = out
210
}
211