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 */ 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 */ 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 */ 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 */ 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 */ 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 */ 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