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