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 #include "bits.h" 20 #include "common.h" 21 22 23 /* ---------------------------------------------------------------------------- 24 * Common 25 * -------------------------------------------------------------------------- */ 26 27 static inline int ac_get(struct lc3_bits_buffer *); 28 static inline void accu_load(struct lc3_bits_accu *, struct lc3_bits_buffer *); 29 30 /** 31 * Arithmetic coder return range bits 32 * ac Arithmetic coder 33 * return 1 + log2(ac->range) 34 */ 35 static int ac_get_range_bits(const struct lc3_bits_ac *ac) 36 { 37 int nbits = 0; 38 39 for (unsigned r = ac->range; r; r >>= 1, nbits++); 40 41 return nbits; 42 } 43 44 /** 45 * Arithmetic coder return pending bits 46 * ac Arithmetic coder 47 * return Pending bits 48 */ 49 static int ac_get_pending_bits(const struct lc3_bits_ac *ac) 50 { 51 return 26 - ac_get_range_bits(ac) + 52 ((ac->cache >= 0) + ac->carry_count) * 8; 53 } 54 55 /** 56 * Return number of bits left in the bitstream 57 * bits Bitstream context 58 * return >= 0: Number of bits left < 0: Overflow 59 */ 60 static int get_bits_left(const struct lc3_bits *bits) 61 { 62 const struct lc3_bits_buffer *buffer = &bits->buffer; 63 const struct lc3_bits_accu *accu = &bits->accu; 64 const struct lc3_bits_ac *ac = &bits->ac; 65 66 uintptr_t end = (uintptr_t)buffer->p_bw + 67 (bits->mode == LC3_BITS_MODE_READ ? LC3_ACCU_BITS/8 : 0); 68 69 uintptr_t start = (uintptr_t)buffer->p_fw - 70 (bits->mode == LC3_BITS_MODE_READ ? LC3_AC_BITS/8 : 0); 71 72 int n = end > start ? (int)(end - start) : -(int)(start - end); 73 74 return 8 * n - (accu->n + accu->nover + ac_get_pending_bits(ac)); 75 } 76 77 /** 78 * Setup bitstream writing 79 */ 80 void lc3_setup_bits(struct lc3_bits *bits, 81 enum lc3_bits_mode mode, void *buffer, int len) 82 { 83 *bits = (struct lc3_bits){ 84 .mode = mode, 85 .accu = { 86 .n = mode == LC3_BITS_MODE_READ ? LC3_ACCU_BITS : 0, 87 }, 88 .ac = { 89 .range = 0xffffff, 90 .cache = -1 91 }, 92 .buffer = { 93 .start = (uint8_t *)buffer, .end = (uint8_t *)buffer + len, 94 .p_fw = (uint8_t *)buffer, .p_bw = (uint8_t *)buffer + len, 95 } 96 }; 97 98 if (mode == LC3_BITS_MODE_READ) { 99 struct lc3_bits_ac *ac = &bits->ac; 100 struct lc3_bits_accu *accu = &bits->accu; 101 struct lc3_bits_buffer *buffer = &bits->buffer; 102 103 ac->low = ac_get(buffer) << 16; 104 ac->low |= ac_get(buffer) << 8; 105 ac->low |= ac_get(buffer); 106 107 accu_load(accu, buffer); 108 } 109 } 110 111 /** 112 * Return number of bits left in the bitstream 113 */ 114 int lc3_get_bits_left(const struct lc3_bits *bits) 115 { 116 return LC3_MAX(get_bits_left(bits), 0); 117 } 118 119 /** 120 * Return number of bits left in the bitstream 121 */ 122 int lc3_check_bits(const struct lc3_bits *bits) 123 { 124 const struct lc3_bits_ac *ac = &bits->ac; 125 126 return -(get_bits_left(bits) < 0 || ac->error); 127 } 128 129 130 /* ---------------------------------------------------------------------------- 131 * Writing 132 * -------------------------------------------------------------------------- */ 133 134 /** 135 * Flush the bits accumulator 136 * accu Bitstream accumulator 137 * buffer Bitstream buffer 138 */ 139 static inline void accu_flush( 140 struct lc3_bits_accu *accu, struct lc3_bits_buffer *buffer) 141 { 142 int nbytes = LC3_MIN(accu->n >> 3, 143 LC3_MAX(buffer->p_bw - buffer->p_fw, 0)); 144 145 accu->n -= 8 * nbytes; 146 147 for ( ; nbytes; accu->v >>= 8, nbytes--) 148 *(--buffer->p_bw) = accu->v & 0xff; 149 150 if (accu->n >= 8) 151 accu->n = 0; 152 } 153 154 /** 155 * Arithmetic coder put byte 156 * buffer Bitstream buffer 157 * byte Byte to output 158 */ 159 static inline void ac_put(struct lc3_bits_buffer *buffer, int byte) 160 { 161 if (buffer->p_fw < buffer->end) 162 *(buffer->p_fw++) = byte; 163 } 164 165 /** 166 * Arithmetic coder range shift 167 * ac Arithmetic coder 168 * buffer Bitstream buffer 169 */ 170 LC3_HOT static inline void ac_shift( 171 struct lc3_bits_ac *ac, struct lc3_bits_buffer *buffer) 172 { 173 if (ac->low < 0xff0000 || ac->carry) 174 { 175 if (ac->cache >= 0) 176 ac_put(buffer, ac->cache + ac->carry); 177 178 for ( ; ac->carry_count > 0; ac->carry_count--) 179 ac_put(buffer, ac->carry ? 0x00 : 0xff); 180 181 ac->cache = ac->low >> 16; 182 ac->carry = 0; 183 } 184 else 185 ac->carry_count++; 186 187 ac->low = (ac->low << 8) & 0xffffff; 188 } 189 190 /** 191 * Arithmetic coder termination 192 * ac Arithmetic coder 193 * buffer Bitstream buffer 194 * end_val/nbits End value and count of bits to terminate (1 to 8) 195 */ 196 static void ac_terminate(struct lc3_bits_ac *ac, 197 struct lc3_bits_buffer *buffer) 198 { 199 int nbits = 25 - ac_get_range_bits(ac); 200 unsigned mask = 0xffffff >> nbits; 201 unsigned val = ac->low + mask; 202 unsigned high = ac->low + ac->range; 203 204 bool over_val = val >> 24; 205 bool over_high = high >> 24; 206 207 val = (val & 0xffffff) & ~mask; 208 high = (high & 0xffffff); 209 210 if (over_val == over_high) { 211 212 if (val + mask >= high) { 213 nbits++; 214 mask >>= 1; 215 val = ((ac->low + mask) & 0xffffff) & ~mask; 216 } 217 218 ac->carry |= val < ac->low; 219 } 220 221 ac->low = val; 222 223 for (; nbits > 8; nbits -= 8) 224 ac_shift(ac, buffer); 225 ac_shift(ac, buffer); 226 227 int end_val = ac->cache >> (8 - nbits); 228 229 if (ac->carry_count) { 230 ac_put(buffer, ac->cache); 231 for ( ; ac->carry_count > 1; ac->carry_count--) 232 ac_put(buffer, 0xff); 233 234 end_val = nbits < 8 ? 0 : 0xff; 235 } 236 237 if (buffer->p_fw < buffer->end) { 238 *buffer->p_fw &= 0xff >> nbits; 239 *buffer->p_fw |= end_val << (8 - nbits); 240 } 241 } 242 243 /** 244 * Flush and terminate bitstream 245 */ 246 void lc3_flush_bits(struct lc3_bits *bits) 247 { 248 struct lc3_bits_ac *ac = &bits->ac; 249 struct lc3_bits_accu *accu = &bits->accu; 250 struct lc3_bits_buffer *buffer = &bits->buffer; 251 252 int nleft = buffer->p_bw - buffer->p_fw; 253 for (int n = 8 * nleft - accu->n; n > 0; n -= 32) 254 lc3_put_bits(bits, 0, LC3_MIN(n, 32)); 255 256 accu_flush(accu, buffer); 257 258 ac_terminate(ac, buffer); 259 } 260 261 /** 262 * Write from 1 to 32 bits, 263 * exceeding the capacity of the accumulator 264 */ 265 LC3_HOT void lc3_put_bits_generic(struct lc3_bits *bits, unsigned v, int n) 266 { 267 struct lc3_bits_accu *accu = &bits->accu; 268 269 /* --- Fulfill accumulator and flush -- */ 270 271 int n1 = LC3_MIN(LC3_ACCU_BITS - accu->n, n); 272 if (n1) { 273 accu->v |= v << accu->n; 274 accu->n = LC3_ACCU_BITS; 275 } 276 277 accu_flush(accu, &bits->buffer); 278 279 /* --- Accumulate remaining bits -- */ 280 281 accu->v = v >> n1; 282 accu->n = n - n1; 283 } 284 285 /** 286 * Arithmetic coder renormalization 287 */ 288 LC3_HOT void lc3_ac_write_renorm(struct lc3_bits *bits) 289 { 290 struct lc3_bits_ac *ac = &bits->ac; 291 292 for ( ; ac->range < 0x10000; ac->range <<= 8) 293 ac_shift(ac, &bits->buffer); 294 } 295 296 297 /* ---------------------------------------------------------------------------- 298 * Reading 299 * -------------------------------------------------------------------------- */ 300 301 /** 302 * Arithmetic coder get byte 303 * buffer Bitstream buffer 304 * return Byte read, 0 on overflow 305 */ 306 static inline int ac_get(struct lc3_bits_buffer *buffer) 307 { 308 return buffer->p_fw < buffer->end ? *(buffer->p_fw++) : 0; 309 } 310 311 /** 312 * Load the accumulator 313 * accu Bitstream accumulator 314 * buffer Bitstream buffer 315 */ 316 static inline void accu_load(struct lc3_bits_accu *accu, 317 struct lc3_bits_buffer *buffer) 318 { 319 int nbytes = LC3_MIN(accu->n >> 3, buffer->p_bw - buffer->start); 320 321 accu->n -= 8 * nbytes; 322 323 for ( ; nbytes; nbytes--) { 324 accu->v >>= 8; 325 accu->v |= (unsigned)*(--buffer->p_bw) << (LC3_ACCU_BITS - 8); 326 } 327 328 if (accu->n >= 8) { 329 accu->nover = LC3_MIN(accu->nover + accu->n, LC3_ACCU_BITS); 330 accu->v >>= accu->n; 331 accu->n = 0; 332 } 333 } 334 335 /** 336 * Read from 1 to 32 bits, 337 * exceeding the capacity of the accumulator 338 */ 339 LC3_HOT unsigned lc3_get_bits_generic(struct lc3_bits *bits, int n) 340 { 341 struct lc3_bits_accu *accu = &bits->accu; 342 struct lc3_bits_buffer *buffer = &bits->buffer; 343 344 /* --- Fulfill accumulator and read -- */ 345 346 accu_load(accu, buffer); 347 348 int n1 = LC3_MIN(LC3_ACCU_BITS - accu->n, n); 349 unsigned v = (accu->v >> accu->n) & ((1u << n1) - 1); 350 accu->n += n1; 351 352 /* --- Second round --- */ 353 354 int n2 = n - n1; 355 356 if (n2) { 357 accu_load(accu, buffer); 358 359 v |= ((accu->v >> accu->n) & ((1u << n2) - 1)) << n1; 360 accu->n += n2; 361 } 362 363 return v; 364 } 365 366 /** 367 * Arithmetic coder renormalization 368 */ 369 LC3_HOT void lc3_ac_read_renorm(struct lc3_bits *bits) 370 { 371 struct lc3_bits_ac *ac = &bits->ac; 372 373 for ( ; ac->range < 0x10000; ac->range <<= 8) 374 ac->low = ((ac->low << 8) | ac_get(&bits->buffer)) & 0xffffff; 375 } 376