| /*Daala video codec |
| Copyright (c) 2001-2012 Daala project contributors. All rights reserved. |
| |
| Redistribution and use in source and binary forms, with or without |
| modification, are permitted provided that the following conditions are met: |
| |
| - Redistributions of source code must retain the above copyright notice, this |
| list of conditions and the following disclaimer. |
| |
| - Redistributions in binary form must reproduce the above copyright notice, |
| this list of conditions and the following disclaimer in the documentation |
| and/or other materials provided with the distribution. |
| |
| THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" |
| AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
| IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
| DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE |
| FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
| DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR |
| SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER |
| CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, |
| OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.*/ |
| |
| #ifdef HAVE_CONFIG_H |
| #include "./config.h" |
| #endif |
| |
| #include "aom_dsp/entcode.h" |
| |
| /*CDFs for uniform probability distributions of small sizes (2 through 16, |
| inclusive).*/ |
| const uint16_t OD_UNIFORM_CDFS_Q15[135] = { |
| 16384, 32768, 10923, 21845, 32768, 8192, 16384, 24576, 32768, 6554, 13107, |
| 19661, 26214, 32768, 5461, 10923, 16384, 21845, 27307, 32768, 4681, 9362, |
| 14043, 18725, 23406, 28087, 32768, 4096, 8192, 12288, 16384, 20480, 24576, |
| 28672, 32768, 3641, 7282, 10923, 14564, 18204, 21845, 25486, 29127, 32768, |
| 3277, 6554, 9830, 13107, 16384, 19661, 22938, 26214, 29491, 32768, 2979, |
| 5958, 8937, 11916, 14895, 17873, 20852, 23831, 26810, 29789, 32768, 2731, |
| 5461, 8192, 10923, 13653, 16384, 19115, 21845, 24576, 27307, 30037, 32768, |
| 2521, 5041, 7562, 10082, 12603, 15124, 17644, 20165, 22686, 25206, 27727, |
| 30247, 32768, 2341, 4681, 7022, 9362, 11703, 14043, 16384, 18725, 21065, |
| 23406, 25746, 28087, 30427, 32768, 2185, 4369, 6554, 8738, 10923, 13107, |
| 15292, 17476, 19661, 21845, 24030, 26214, 28399, 30583, 32768, 2048, 4096, |
| 6144, 8192, 10240, 12288, 14336, 16384, 18432, 20480, 22528, 24576, 26624, |
| 28672, 30720, 32768 |
| }; |
| |
| /*Given the current total integer number of bits used and the current value of |
| rng, computes the fraction number of bits used to OD_BITRES precision. |
| This is used by od_ec_enc_tell_frac() and od_ec_dec_tell_frac(). |
| nbits_total: The number of whole bits currently used, i.e., the value |
| returned by od_ec_enc_tell() or od_ec_dec_tell(). |
| rng: The current value of rng from either the encoder or decoder state. |
| Return: The number of bits scaled by 2**OD_BITRES. |
| This will always be slightly larger than the exact value (e.g., all |
| rounding error is in the positive direction).*/ |
| uint32_t od_ec_tell_frac(uint32_t nbits_total, uint32_t rng) { |
| uint32_t nbits; |
| int l; |
| int i; |
| /*To handle the non-integral number of bits still left in the encoder/decoder |
| state, we compute the worst-case number of bits of val that must be |
| encoded to ensure that the value is inside the range for any possible |
| subsequent bits. |
| The computation here is independent of val itself (the decoder does not |
| even track that value), even though the real number of bits used after |
| od_ec_enc_done() may be 1 smaller if rng is a power of two and the |
| corresponding trailing bits of val are all zeros. |
| If we did try to track that special case, then coding a value with a |
| probability of 1/(1 << n) might sometimes appear to use more than n bits. |
| This may help explain the surprising result that a newly initialized |
| encoder or decoder claims to have used 1 bit.*/ |
| nbits = nbits_total << OD_BITRES; |
| l = 0; |
| for (i = OD_BITRES; i-- > 0;) { |
| int b; |
| rng = rng * rng >> 15; |
| b = (int)(rng >> 16); |
| l = l << 1 | b; |
| rng >>= b; |
| } |
| return nbits - l; |
| } |