1 /******************************************************************************
2 *
3 * Copyright 2022 Google LLC
4 *
5 * Licensed under the Apache License, Version 2.0 (the "License");
6 * you may not use this file except in compliance with the License.
7 * You may obtain a copy of the License at:
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 *
17 ******************************************************************************/
18
19 /**
20 * The bitstream is written by the 2 ends of the buffer :
21 *
22 * - Arthmetic coder put bits while increasing memory addresses
23 * in the buffer (forward)
24 *
25 * - Plain bits are puts starting the end of the buffer, with memeory
26 * addresses decreasing (backward)
27 *
28 * .---------------------------------------------------.
29 * | > > > > > > > > > > : : < < < < < < < < < |
30 * '---------------------------------------------------'
31 * |---------------------> - - - - - - - - - - - - - ->|
32 * |< - - - <-------------------|
33 * Arithmetic coding Plain bits
34 * `lc3_put_symbol()` `lc3_put_bits()`
35 *
36 * - The forward writing is protected against buffer overflow, it cannot
37 * write after the buffer, but can overwrite plain bits previously
38 * written in the buffer.
39 *
40 * - The backward writing is protected against overwrite of the arithmetic
41 * coder bitstream. In such way, the backward bitstream is always limited
42 * by the aritmetic coder bitstream, and can be overwritten by him.
43 *
44 * .---------------------------------------------------.
45 * | > > > > > > > > > > : : < < < < < < < < < |
46 * '---------------------------------------------------'
47 * |---------------------> - - - - - - - - - - - - - ->|
48 * |< - - - - - - - - - - - - - - <-------------------|
49 * Arithmetic coding Plain bits
50 * `lc3_get_symbol()` `lc3_get_bits()`
51 *
52 * - Reading is limited to read of the complementary end of the buffer.
53 *
54 * - The procedure `lc3_check_bits()` returns indication that read has been
55 * made crossing the other bit plane.
56 *
57 */
58
59 #ifndef __LC3_BITS_H
60 #define __LC3_BITS_H
61
62 #include "common.h"
63
64
65 /**
66 * Bitstream mode
67 */
68
69 enum lc3_bits_mode {
70 LC3_BITS_MODE_READ,
71 LC3_BITS_MODE_WRITE,
72 };
73
74 /**
75 * Arithmetic coder symbol interval
76 * The model split the interval in 17 symbols
77 */
78
79 struct lc3_ac_symbol {
80 uint16_t low : 16;
81 uint16_t range : 16;
82 };
83
84 struct lc3_ac_model {
85 struct lc3_ac_symbol s[17];
86 };
87
88 /**
89 * Bitstream context
90 */
91
92 #define LC3_ACCU_BITS (int)(8 * sizeof(unsigned))
93
94 struct lc3_bits_accu {
95 unsigned v;
96 int n, nover;
97 };
98
99 #define LC3_AC_BITS (int)(24)
100
101 struct lc3_bits_ac {
102 unsigned low, range;
103 int cache, carry, carry_count;
104 bool error;
105 };
106
107 struct lc3_bits_buffer {
108 const uint8_t *start, *end;
109 uint8_t *p_fw, *p_bw;
110 };
111
112 typedef struct lc3_bits {
113 enum lc3_bits_mode mode;
114 struct lc3_bits_ac ac;
115 struct lc3_bits_accu accu;
116 struct lc3_bits_buffer buffer;
117 } lc3_bits_t;
118
119
120 /**
121 * Setup bitstream reading/writing
122 * bits Bitstream context
123 * mode Either READ or WRITE mode
124 * buffer, len Output buffer and length (in bytes)
125 */
126 void lc3_setup_bits(lc3_bits_t *bits,
127 enum lc3_bits_mode mode, void *buffer, int len);
128
129 /**
130 * Return number of bits left in the bitstream
131 * bits Bitstream context
132 * return Number of bits left
133 */
134 int lc3_get_bits_left(const lc3_bits_t *bits);
135
136 /**
137 * Check if error occured on bitstream reading/writing
138 * bits Bitstream context
139 * return 0: Ok -1: Bitstream overflow or AC reading error
140 */
141 int lc3_check_bits(const lc3_bits_t *bits);
142
143 /**
144 * Put a bit
145 * bits Bitstream context
146 * v Bit value, 0 or 1
147 */
148 static inline void lc3_put_bit(lc3_bits_t *bits, int v);
149
150 /**
151 * Put from 1 to 32 bits
152 * bits Bitstream context
153 * v, n Value, in range 0 to 2^n - 1, and bits count (1 to 32)
154 */
155 static inline void lc3_put_bits(lc3_bits_t *bits, unsigned v, int n);
156
157 /**
158 * Put arithmetic coder symbol
159 * bits Bitstream context
160 * model, s Model distribution and symbol value
161 */
162 static inline void lc3_put_symbol(lc3_bits_t *bits,
163 const struct lc3_ac_model *model, unsigned s);
164
165 /**
166 * Flush and terminate bitstream writing
167 * bits Bitstream context
168 */
169 void lc3_flush_bits(lc3_bits_t *bits);
170
171 /**
172 * Get a bit
173 * bits Bitstream context
174 */
175 static inline int lc3_get_bit(lc3_bits_t *bits);
176
177 /**
178 * Get from 1 to 32 bits
179 * bits Bitstream context
180 * n Number of bits to read (1 to 32)
181 * return The value read
182 */
183 static inline unsigned lc3_get_bits(lc3_bits_t *bits, int n);
184
185 /**
186 * Get arithmetic coder symbol
187 * bits Bitstream context
188 * model Model distribution
189 * return The value read
190 */
191 static inline unsigned lc3_get_symbol(lc3_bits_t *bits,
192 const struct lc3_ac_model *model);
193
194
195
196 /* ----------------------------------------------------------------------------
197 * Inline implementations
198 * -------------------------------------------------------------------------- */
199
200 void lc3_put_bits_generic(lc3_bits_t *bits, unsigned v, int n);
201 unsigned lc3_get_bits_generic(struct lc3_bits *bits, int n);
202
203 void lc3_ac_read_renorm(lc3_bits_t *bits);
204 void lc3_ac_write_renorm(lc3_bits_t *bits);
205
206
207 /**
208 * Put a bit
209 */
lc3_put_bit(lc3_bits_t * bits,int v)210 LC3_HOT static inline void lc3_put_bit(lc3_bits_t *bits, int v)
211 {
212 lc3_put_bits(bits, v, 1);
213 }
214
215 /**
216 * Put from 1 to 32 bits
217 */
lc3_put_bits(struct lc3_bits * bits,unsigned v,int n)218 LC3_HOT static inline void lc3_put_bits(
219 struct lc3_bits *bits, unsigned v, int n)
220 {
221 struct lc3_bits_accu *accu = &bits->accu;
222
223 if (accu->n + n <= LC3_ACCU_BITS) {
224 accu->v |= v << accu->n;
225 accu->n += n;
226 } else {
227 lc3_put_bits_generic(bits, v, n);
228 }
229 }
230
231 /**
232 * Get a bit
233 */
lc3_get_bit(lc3_bits_t * bits)234 LC3_HOT static inline int lc3_get_bit(lc3_bits_t *bits)
235 {
236 return lc3_get_bits(bits, 1);
237 }
238
239 /**
240 * Get from 1 to 32 bits
241 */
lc3_get_bits(struct lc3_bits * bits,int n)242 LC3_HOT static inline unsigned lc3_get_bits(struct lc3_bits *bits, int n)
243 {
244 struct lc3_bits_accu *accu = &bits->accu;
245
246 if (accu->n + n <= LC3_ACCU_BITS) {
247 int v = (accu->v >> accu->n) & ((1u << n) - 1);
248 return (accu->n += n), v;
249 }
250 else {
251 return lc3_get_bits_generic(bits, n);
252 }
253 }
254
255 /**
256 * Put arithmetic coder symbol
257 */
lc3_put_symbol(struct lc3_bits * bits,const struct lc3_ac_model * model,unsigned s)258 LC3_HOT static inline void lc3_put_symbol(
259 struct lc3_bits *bits, const struct lc3_ac_model *model, unsigned s)
260 {
261 const struct lc3_ac_symbol *symbols = model->s;
262 struct lc3_bits_ac *ac = &bits->ac;
263 unsigned range = ac->range >> 10;
264
265 ac->low += range * symbols[s].low;
266 ac->range = range * symbols[s].range;
267
268 ac->carry |= ac->low >> 24;
269 ac->low &= 0xffffff;
270
271 if (ac->range < 0x10000)
272 lc3_ac_write_renorm(bits);
273 }
274
275 /**
276 * Get arithmetic coder symbol
277 */
lc3_get_symbol(lc3_bits_t * bits,const struct lc3_ac_model * model)278 LC3_HOT static inline unsigned lc3_get_symbol(
279 lc3_bits_t *bits, const struct lc3_ac_model *model)
280 {
281 const struct lc3_ac_symbol *symbols = model->s;
282 struct lc3_bits_ac *ac = &bits->ac;
283
284 unsigned range = (ac->range >> 10) & 0xffff;
285
286 ac->error |= (ac->low >= (range << 10));
287 if (ac->error)
288 ac->low = 0;
289
290 int s = 16;
291
292 if (ac->low < range * symbols[s].low) {
293 s >>= 1;
294 s -= ac->low < range * symbols[s].low ? 4 : -4;
295 s -= ac->low < range * symbols[s].low ? 2 : -2;
296 s -= ac->low < range * symbols[s].low ? 1 : -1;
297 s -= ac->low < range * symbols[s].low;
298 }
299
300 ac->low -= range * symbols[s].low;
301 ac->range = range * symbols[s].range;
302
303 if (ac->range < 0x10000)
304 lc3_ac_read_renorm(bits);
305
306 return s;
307 }
308
309 #endif /* __LC3_BITS_H */
310
