1 /****************************************************************************** 2 * 3 * Copyright 2021 Google, Inc. 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 */ 216 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 */ 224 static inline void lc3_put_bits(struct lc3_bits *bits, unsigned v, int n) 225 { 226 struct lc3_bits_accu *accu = &bits->accu; 227 228 if (accu->n + n <= LC3_ACCU_BITS) { 229 accu->v |= v << accu->n; 230 accu->n += n; 231 } else { 232 lc3_put_bits_generic(bits, v, n); 233 } 234 } 235 236 /** 237 * Get a bit 238 */ 239 static inline int lc3_get_bit(lc3_bits_t *bits) 240 { 241 return lc3_get_bits(bits, 1); 242 } 243 244 /** 245 * Get from 1 to 32 bits 246 */ 247 static inline unsigned lc3_get_bits(struct lc3_bits *bits, int n) 248 { 249 struct lc3_bits_accu *accu = &bits->accu; 250 251 if (accu->n + n <= LC3_ACCU_BITS) { 252 int v = (accu->v >> accu->n) & ((1u << n) - 1); 253 return (accu->n += n), v; 254 } 255 else { 256 return lc3_get_bits_generic(bits, n); 257 } 258 } 259 260 /** 261 * Put arithmetic coder symbol 262 */ 263 static inline void lc3_put_symbol( 264 struct lc3_bits *bits, const struct lc3_ac_model *model, unsigned s) 265 { 266 const struct lc3_ac_symbol *symbols = model->s; 267 struct lc3_bits_ac *ac = &bits->ac; 268 unsigned range = ac->range >> 10; 269 270 ac->low += range * symbols[s].low; 271 ac->range = range * symbols[s].range; 272 273 ac->carry |= ac->low >> 24; 274 ac->low &= 0xffffff; 275 276 if (ac->range < 0x10000) 277 lc3_ac_write_renorm(bits); 278 } 279 280 /** 281 * Get arithmetic coder symbol 282 */ 283 static inline unsigned lc3_get_symbol( 284 lc3_bits_t *bits, const struct lc3_ac_model *model) 285 { 286 const struct lc3_ac_symbol *symbols = model->s; 287 struct lc3_bits_ac *ac = &bits->ac; 288 289 unsigned range = (ac->range >> 10) & 0xffff; 290 291 ac->error |= (ac->low >= (range << 10)); 292 if (ac->error) 293 ac->low = 0; 294 295 int s = 16; 296 297 if (ac->low < range * symbols[s].low) { 298 s >>= 1; 299 s -= ac->low < range * symbols[s].low ? 4 : -4; 300 s -= ac->low < range * symbols[s].low ? 2 : -2; 301 s -= ac->low < range * symbols[s].low ? 1 : -1; 302 s -= ac->low < range * symbols[s].low; 303 } 304 305 ac->low -= range * symbols[s].low; 306 ac->range = range * symbols[s].range; 307 308 if (ac->range < 0x10000) 309 lc3_ac_read_renorm(bits); 310 311 return s; 312 } 313 314 #endif /* __LC3_BITS_H */ 315