msac.c (7252B)
1 /* 2 * Copyright © 2018, VideoLAN and dav1d authors 3 * Copyright © 2018, Two Orioles, LLC 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 9 * 1. Redistributions of source code must retain the above copyright notice, this 10 * list of conditions and the following disclaimer. 11 * 12 * 2. Redistributions in binary form must reproduce the above copyright notice, 13 * this list of conditions and the following disclaimer in the documentation 14 * and/or other materials provided with the distribution. 15 * 16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 19 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR 20 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 */ 27 28 #include "config.h" 29 30 #include <limits.h> 31 32 #include "common/intops.h" 33 34 #include "src/msac.h" 35 36 #define EC_PROB_SHIFT 6 37 #define EC_MIN_PROB 4 // must be <= (1<<EC_PROB_SHIFT)/16 38 39 #define EC_WIN_SIZE (sizeof(ec_win) << 3) 40 41 static inline void ctx_refill(MsacContext *const s) { 42 const uint8_t *buf_pos = s->buf_pos; 43 const uint8_t *buf_end = s->buf_end; 44 int c = EC_WIN_SIZE - s->cnt - 24; 45 ec_win dif = s->dif; 46 do { 47 if (buf_pos >= buf_end) { 48 // set remaining bits to 1; 49 dif |= ~(~(ec_win)0xff << c); 50 break; 51 } 52 dif |= (ec_win)(*buf_pos++ ^ 0xff) << c; 53 c -= 8; 54 } while (c >= 0); 55 s->dif = dif; 56 s->cnt = EC_WIN_SIZE - c - 24; 57 s->buf_pos = buf_pos; 58 } 59 60 int dav1d_msac_decode_subexp(MsacContext *const s, const int ref, 61 const int n, unsigned k) 62 { 63 assert(n >> k == 8); 64 65 unsigned a = 0; 66 if (dav1d_msac_decode_bool_equi(s)) { 67 if (dav1d_msac_decode_bool_equi(s)) 68 k += dav1d_msac_decode_bool_equi(s) + 1; 69 a = 1 << k; 70 } 71 const unsigned v = dav1d_msac_decode_bools(s, k) + a; 72 return ref * 2 <= n ? inv_recenter(ref, v) : 73 n - 1 - inv_recenter(n - 1 - ref, v); 74 } 75 76 #if !(HAVE_ASM && TRIM_DSP_FUNCTIONS && ( \ 77 ARCH_AARCH64 || \ 78 (ARCH_ARM && (defined(__ARM_NEON) || defined(__APPLE__) || defined(_WIN32))) \ 79 )) 80 /* Takes updated dif and range values, renormalizes them so that 81 * 32768 <= rng < 65536 (reading more bytes from the stream into dif if 82 * necessary), and stores them back in the decoder context. 83 * dif: The new value of dif. 84 * rng: The new value of the range. */ 85 static inline void ctx_norm(MsacContext *const s, const ec_win dif, 86 const unsigned rng) 87 { 88 const int d = 15 ^ (31 ^ clz(rng)); 89 const int cnt = s->cnt; 90 assert(rng <= 65535U); 91 s->dif = dif << d; 92 s->rng = rng << d; 93 s->cnt = cnt - d; 94 // unsigned compare avoids redundant refills at eob 95 if ((unsigned)cnt < (unsigned)d) 96 ctx_refill(s); 97 } 98 99 unsigned dav1d_msac_decode_bool_equi_c(MsacContext *const s) { 100 const unsigned r = s->rng; 101 ec_win dif = s->dif; 102 assert((dif >> (EC_WIN_SIZE - 16)) < r); 103 // When the probability is 1/2, f = 16384 >> EC_PROB_SHIFT = 256 and we can 104 // replace the multiply with a simple shift. 105 unsigned v = ((r >> 8) << 7) + EC_MIN_PROB; 106 const ec_win vw = (ec_win)v << (EC_WIN_SIZE - 16); 107 const unsigned ret = dif >= vw; 108 dif -= ret * vw; 109 v += ret * (r - 2 * v); 110 ctx_norm(s, dif, v); 111 return !ret; 112 } 113 114 /* Decode a single binary value. 115 * f: The probability that the bit is one 116 * Return: The value decoded (0 or 1). */ 117 unsigned dav1d_msac_decode_bool_c(MsacContext *const s, const unsigned f) { 118 const unsigned r = s->rng; 119 ec_win dif = s->dif; 120 assert((dif >> (EC_WIN_SIZE - 16)) < r); 121 unsigned v = ((r >> 8) * (f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)) + EC_MIN_PROB; 122 const ec_win vw = (ec_win)v << (EC_WIN_SIZE - 16); 123 const unsigned ret = dif >= vw; 124 dif -= ret * vw; 125 v += ret * (r - 2 * v); 126 ctx_norm(s, dif, v); 127 return !ret; 128 } 129 130 /* Decodes a symbol given an inverse cumulative distribution function (CDF) 131 * table in Q15. */ 132 unsigned dav1d_msac_decode_symbol_adapt_c(MsacContext *const s, 133 uint16_t *const cdf, 134 const size_t n_symbols) 135 { 136 const unsigned c = s->dif >> (EC_WIN_SIZE - 16), r = s->rng >> 8; 137 unsigned u, v = s->rng, val = -1; 138 139 assert(n_symbols <= 15); 140 assert(cdf[n_symbols] <= 32); 141 142 do { 143 val++; 144 u = v; 145 v = r * (cdf[val] >> EC_PROB_SHIFT); 146 v >>= 7 - EC_PROB_SHIFT; 147 v += EC_MIN_PROB * ((unsigned)n_symbols - val); 148 } while (c < v); 149 150 assert(u <= s->rng); 151 152 ctx_norm(s, s->dif - ((ec_win)v << (EC_WIN_SIZE - 16)), u - v); 153 154 if (s->allow_update_cdf) { 155 const unsigned count = cdf[n_symbols]; 156 const unsigned rate = 4 + (count >> 4) + (n_symbols > 2); 157 unsigned i; 158 for (i = 0; i < val; i++) 159 cdf[i] += (32768 - cdf[i]) >> rate; 160 for (; i < n_symbols; i++) 161 cdf[i] -= cdf[i] >> rate; 162 cdf[n_symbols] = count + (count < 32); 163 } 164 165 return val; 166 } 167 168 unsigned dav1d_msac_decode_bool_adapt_c(MsacContext *const s, 169 uint16_t *const cdf) 170 { 171 const unsigned bit = dav1d_msac_decode_bool(s, *cdf); 172 173 if (s->allow_update_cdf) { 174 // update_cdf() specialized for boolean CDFs 175 const unsigned count = cdf[1]; 176 const int rate = 4 + (count >> 4); 177 if (bit) 178 cdf[0] += (32768 - cdf[0]) >> rate; 179 else 180 cdf[0] -= cdf[0] >> rate; 181 cdf[1] = count + (count < 32); 182 } 183 184 return bit; 185 } 186 187 unsigned dav1d_msac_decode_hi_tok_c(MsacContext *const s, uint16_t *const cdf) { 188 unsigned tok_br = dav1d_msac_decode_symbol_adapt4(s, cdf, 3); 189 unsigned tok = 3 + tok_br; 190 if (tok_br == 3) { 191 tok_br = dav1d_msac_decode_symbol_adapt4(s, cdf, 3); 192 tok = 6 + tok_br; 193 if (tok_br == 3) { 194 tok_br = dav1d_msac_decode_symbol_adapt4(s, cdf, 3); 195 tok = 9 + tok_br; 196 if (tok_br == 3) 197 tok = 12 + dav1d_msac_decode_symbol_adapt4(s, cdf, 3); 198 } 199 } 200 return tok; 201 } 202 #endif 203 204 void dav1d_msac_init(MsacContext *const s, const uint8_t *const data, 205 const size_t sz, const int disable_cdf_update_flag) 206 { 207 s->buf_pos = data; 208 s->buf_end = data + sz; 209 s->dif = 0; 210 s->rng = 0x8000; 211 s->cnt = -15; 212 s->allow_update_cdf = !disable_cdf_update_flag; 213 ctx_refill(s); 214 215 #if ARCH_X86_64 && HAVE_ASM 216 s->symbol_adapt16 = dav1d_msac_decode_symbol_adapt_c; 217 218 msac_init_x86(s); 219 #endif 220 }