entdec.c (9431B)
1 /* 2 * Copyright (c) 2001-2016, Alliance for Open Media. All rights reserved. 3 * 4 * This source code is subject to the terms of the BSD 2 Clause License and 5 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License 6 * was not distributed with this source code in the LICENSE file, you can 7 * obtain it at www.aomedia.org/license/software. If the Alliance for Open 8 * Media Patent License 1.0 was not distributed with this source code in the 9 * PATENTS file, you can obtain it at www.aomedia.org/license/patent. 10 */ 11 12 #include <assert.h> 13 #include "aom_dsp/entdec.h" 14 #include "aom_dsp/prob.h" 15 16 /*A range decoder. 17 This is an entropy decoder based upon \cite{Mar79}, which is itself a 18 rediscovery of the FIFO arithmetic code introduced by \cite{Pas76}. 19 It is very similar to arithmetic encoding, except that encoding is done with 20 digits in any base, instead of with bits, and so it is faster when using 21 larger bases (i.e.: a byte). 22 The author claims an average waste of $\frac{1}{2}\log_b(2b)$ bits, where $b$ 23 is the base, longer than the theoretical optimum, but to my knowledge there 24 is no published justification for this claim. 25 This only seems true when using near-infinite precision arithmetic so that 26 the process is carried out with no rounding errors. 27 28 An excellent description of implementation details is available at 29 http://www.arturocampos.com/ac_range.html 30 A recent work \cite{MNW98} which proposes several changes to arithmetic 31 encoding for efficiency actually re-discovers many of the principles 32 behind range encoding, and presents a good theoretical analysis of them. 33 34 End of stream is handled by writing out the smallest number of bits that 35 ensures that the stream will be correctly decoded regardless of the value of 36 any subsequent bits. 37 od_ec_dec_tell() can be used to determine how many bits were needed to decode 38 all the symbols thus far; other data can be packed in the remaining bits of 39 the input buffer. 40 @PHDTHESIS{Pas76, 41 author="Richard Clark Pasco", 42 title="Source coding algorithms for fast data compression", 43 school="Dept. of Electrical Engineering, Stanford University", 44 address="Stanford, CA", 45 month=May, 46 year=1976, 47 URL="http://www.richpasco.org/scaffdc.pdf" 48 } 49 @INPROCEEDINGS{Mar79, 50 author="Martin, G.N.N.", 51 title="Range encoding: an algorithm for removing redundancy from a digitised 52 message", 53 booktitle="Video & Data Recording Conference", 54 year=1979, 55 address="Southampton", 56 month=Jul, 57 URL="http://www.compressconsult.com/rangecoder/rngcod.pdf.gz" 58 } 59 @ARTICLE{MNW98, 60 author="Alistair Moffat and Radford Neal and Ian H. Witten", 61 title="Arithmetic Coding Revisited", 62 journal="{ACM} Transactions on Information Systems", 63 year=1998, 64 volume=16, 65 number=3, 66 pages="256--294", 67 month=Jul, 68 URL="http://researchcommons.waikato.ac.nz/bitstream/handle/10289/78/content.pdf" 69 }*/ 70 71 /*This is meant to be a large, positive constant that can still be efficiently 72 loaded as an immediate (on platforms like ARM, for example). 73 Even relatively modest values like 100 would work fine.*/ 74 #define OD_EC_LOTS_OF_BITS (0x4000) 75 76 /*The return value of od_ec_dec_tell does not change across an od_ec_dec_refill 77 call.*/ 78 static void od_ec_dec_refill(od_ec_dec *dec) { 79 int s; 80 od_ec_window dif; 81 int16_t cnt; 82 const unsigned char *bptr; 83 const unsigned char *end; 84 dif = dec->dif; 85 cnt = dec->cnt; 86 bptr = dec->bptr; 87 end = dec->end; 88 s = OD_EC_WINDOW_SIZE - 9 - (cnt + 15); 89 for (; s >= 0 && bptr < end; s -= 8, bptr++) { 90 /*Each time a byte is inserted into the window (dif), bptr advances and cnt 91 is incremented by 8, so the total number of consumed bits (the return 92 value of od_ec_dec_tell) does not change.*/ 93 assert(s <= OD_EC_WINDOW_SIZE - 8); 94 dif ^= (od_ec_window)bptr[0] << s; 95 cnt += 8; 96 } 97 if (bptr >= end) { 98 /*We've reached the end of the buffer. It is perfectly valid for us to need 99 to fill the window with additional bits past the end of the buffer (and 100 this happens in normal operation). These bits should all just be taken 101 as zero. But we cannot increment bptr past 'end' (this is undefined 102 behavior), so we start to increment dec->tell_offs. We also don't want 103 to keep testing bptr against 'end', so we set cnt to OD_EC_LOTS_OF_BITS 104 and adjust dec->tell_offs so that the total number of unconsumed bits in 105 the window (dec->cnt - dec->tell_offs) does not change. This effectively 106 puts lots of zero bits into the window, and means we won't try to refill 107 it from the buffer for a very long time (at which point we'll put lots 108 of zero bits into the window again).*/ 109 dec->tell_offs += OD_EC_LOTS_OF_BITS - cnt; 110 cnt = OD_EC_LOTS_OF_BITS; 111 } 112 dec->dif = dif; 113 dec->cnt = cnt; 114 dec->bptr = bptr; 115 } 116 117 /*Takes updated dif and range values, renormalizes them so that 118 32768 <= rng < 65536 (reading more bytes from the stream into dif if 119 necessary), and stores them back in the decoder context. 120 dif: The new value of dif. 121 rng: The new value of the range. 122 ret: The value to return. 123 Return: ret. 124 This allows the compiler to jump to this function via a tail-call.*/ 125 static int od_ec_dec_normalize(od_ec_dec *dec, od_ec_window dif, unsigned rng, 126 int ret) { 127 int d; 128 assert(rng <= 65535U); 129 /*The number of leading zeros in the 16-bit binary representation of rng.*/ 130 d = 16 - OD_ILOG_NZ(rng); 131 /*d bits in dec->dif are consumed.*/ 132 dec->cnt -= d; 133 /*This is equivalent to shifting in 1's instead of 0's.*/ 134 dec->dif = ((dif + 1) << d) - 1; 135 dec->rng = rng << d; 136 if (dec->cnt < 0) od_ec_dec_refill(dec); 137 return ret; 138 } 139 140 /*Initializes the decoder. 141 buf: The input buffer to use. 142 storage: The size in bytes of the input buffer.*/ 143 void od_ec_dec_init(od_ec_dec *dec, const unsigned char *buf, 144 uint32_t storage) { 145 dec->buf = buf; 146 dec->tell_offs = 10 - (OD_EC_WINDOW_SIZE - 8); 147 dec->end = buf + storage; 148 dec->bptr = buf; 149 dec->dif = ((od_ec_window)1 << (OD_EC_WINDOW_SIZE - 1)) - 1; 150 dec->rng = 0x8000; 151 dec->cnt = -15; 152 od_ec_dec_refill(dec); 153 } 154 155 /*Decode a single binary value. 156 f: The probability that the bit is one, scaled by 32768. 157 Return: The value decoded (0 or 1).*/ 158 int od_ec_decode_bool_q15(od_ec_dec *dec, unsigned f) { 159 od_ec_window dif; 160 od_ec_window vw; 161 unsigned r; 162 unsigned r_new; 163 unsigned v; 164 int ret; 165 assert(0 < f); 166 assert(f < 32768U); 167 dif = dec->dif; 168 r = dec->rng; 169 assert(dif >> (OD_EC_WINDOW_SIZE - 16) < r); 170 assert(32768U <= r); 171 v = ((r >> 8) * (uint32_t)(f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)); 172 v += EC_MIN_PROB; 173 vw = (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16); 174 ret = 1; 175 r_new = v; 176 if (dif >= vw) { 177 r_new = r - v; 178 dif -= vw; 179 ret = 0; 180 } 181 return od_ec_dec_normalize(dec, dif, r_new, ret); 182 } 183 184 /*Decodes a symbol given an inverse cumulative distribution function (CDF) 185 table in Q15. 186 icdf: CDF_PROB_TOP minus the CDF, such that symbol s falls in the range 187 [s > 0 ? (CDF_PROB_TOP - icdf[s - 1]) : 0, CDF_PROB_TOP - icdf[s]). 188 The values must be monotonically non-increasing, and icdf[nsyms - 1] 189 must be 0. 190 nsyms: The number of symbols in the alphabet. 191 This should be at most 16. 192 Return: The decoded symbol s.*/ 193 int od_ec_decode_cdf_q15(od_ec_dec *dec, const uint16_t *icdf, int nsyms) { 194 od_ec_window dif; 195 unsigned r; 196 unsigned c; 197 unsigned u; 198 unsigned v; 199 int ret; 200 (void)nsyms; 201 dif = dec->dif; 202 r = dec->rng; 203 const int N = nsyms - 1; 204 205 assert(dif >> (OD_EC_WINDOW_SIZE - 16) < r); 206 assert(icdf[nsyms - 1] == OD_ICDF(CDF_PROB_TOP)); 207 assert(32768U <= r); 208 assert(7 - EC_PROB_SHIFT >= 0); 209 c = (unsigned)(dif >> (OD_EC_WINDOW_SIZE - 16)); 210 v = r; 211 ret = -1; 212 do { 213 u = v; 214 v = ((r >> 8) * (uint32_t)(icdf[++ret] >> EC_PROB_SHIFT) >> 215 (7 - EC_PROB_SHIFT)); 216 v += EC_MIN_PROB * (N - ret); 217 } while (c < v); 218 assert(v < u); 219 assert(u <= r); 220 r = u - v; 221 dif -= (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16); 222 return od_ec_dec_normalize(dec, dif, r, ret); 223 } 224 225 /*Returns the number of bits "used" by the decoded symbols so far. 226 This same number can be computed in either the encoder or the decoder, and is 227 suitable for making coding decisions. 228 Return: The number of bits. 229 This will always be slightly larger than the exact value (e.g., all 230 rounding error is in the positive direction).*/ 231 int od_ec_dec_tell(const od_ec_dec *dec) { 232 /*There is a window of bits stored in dec->dif. The difference 233 (dec->bptr - dec->buf) tells us how many bytes have been read into this 234 window. The difference (dec->cnt - dec->tell_offs) tells us how many of 235 the bits in that window remain unconsumed.*/ 236 return (int)((dec->bptr - dec->buf) * 8 - dec->cnt + dec->tell_offs); 237 } 238 239 /*Returns the number of bits "used" by the decoded symbols so far. 240 This same number can be computed in either the encoder or the decoder, and is 241 suitable for making coding decisions. 242 Return: The number of bits scaled by 2**OD_BITRES. 243 This will always be slightly larger than the exact value (e.g., all 244 rounding error is in the positive direction).*/ 245 uint32_t od_ec_dec_tell_frac(const od_ec_dec *dec) { 246 return od_ec_tell_frac(od_ec_dec_tell(dec), dec->rng); 247 }