blob: 6bce4e87d4ff69e780440fd6970b44eb4a970b5d [file] [log] [blame]
khenaidoo7d3c5582021-08-11 18:09:44 -04001// 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
6package huff0
7
8import "fmt"
9
10// bitWriter will write bits.
11// First bit will be LSB of the first byte of output.
12type bitWriter struct {
13 bitContainer uint64
14 nBits uint8
15 out []byte
16}
17
18// bitMask16 is bitmasks. Has extra to avoid bounds check.
19var 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.
29func (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.
36func (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.
43func (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.
56func (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.
77func (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.
90func (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.
172func (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.
186func (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.
197func (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.
206func (b *bitWriter) reset(out []byte) {
207 b.bitContainer = 0
208 b.nBits = 0
209 b.out = out
210}