aom_dsp/entenc.c

   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 <stdlib.h>
  13 #include <string.h>
  14 #include <math.h>
  15 #include <assert.h>
  16 #include "aom_dsp/entenc.h"
  17 #include "aom_dsp/prob.h"
  18
  19 #if OD_MEASURE_EC_OVERHEAD
  20 #if !defined(M_LOG2E)
  21 #define M_LOG2E (1.4426950408889634073599246810019)
  22 #endif
  23 #define OD_LOG2(x) (M_LOG2E * log(x))
  24 #endif  // OD_MEASURE_EC_OVERHEAD
  25
  26 /*A range encoder.
  27   See entdec.c and the references for implementation details \cite{Mar79,MNW98}.
  28
  29   @INPROCEEDINGS{Mar79,
  30    author="Martin, G.N.N.",
  31    title="Range encoding: an algorithm for removing redundancy from a digitised
  32     message",
  33    booktitle="Video \& Data Recording Conference",
  34    year=1979,
  35    address="Southampton",
  36    month=Jul,
  37    URL="http://www.compressconsult.com/rangecoder/rngcod.pdf.gz"
  38   }
  39   @ARTICLE{MNW98,
  40    author="Alistair Moffat and Radford Neal and Ian H. Witten",
  41    title="Arithmetic Coding Revisited",
  42    journal="{ACM} Transactions on Information Systems",
  43    year=1998,
  44    volume=16,
  45    number=3,
  46    pages="256--294",
  47    month=Jul,
  48    URL="http://researchcommons.waikato.ac.nz/bitstream/handle/10289/78/content.pdf"
  49   }*/
  50
  51 /*Takes updated low and range values, renormalizes them so that
  52    32768 <= rng < 65536 (flushing bytes from low to the pre-carry buffer if
  53    necessary), and stores them back in the encoder context.
  54   low: The new value of low.
  55   rng: The new value of the range.*/
  56 static void od_ec_enc_normalize(od_ec_enc *enc, od_ec_window low,
  57                                 unsigned rng) {
  58   int d;
  59   int c;
  60   int s;
  61   c = enc->cnt;
  62   assert(rng <= 65535U);
  63   /*The number of leading zeros in the 16-bit binary representation of rng.*/
  64   d = 16 - OD_ILOG_NZ(rng);
  65   s = c + d;
  66   /*TODO: Right now we flush every time we have at least one byte available.
  67     Instead we should use an od_ec_window and flush right before we're about to
  68      shift bits off the end of the window.
  69     For a 32-bit window this is about the same amount of work, but for a 64-bit
  70      window it should be a fair win.*/
  71   if (s >= 0) {
  72     uint16_t *buf;
  73     uint32_t storage;
  74     uint32_t offs;
  75     unsigned m;
  76     buf = enc->precarry_buf;
  77     storage = enc->precarry_storage;
  78     offs = enc->offs;
  79     if (offs + 2 > storage) {
  80       storage = 2 * storage + 2;
  81       buf = (uint16_t *)realloc(buf, sizeof(*buf) * storage);
  82       if (buf == NULL) {
  83         enc->error = -1;
  84         enc->offs = 0;
  85         return;
  86       }
  87       enc->precarry_buf = buf;
  88       enc->precarry_storage = storage;
  89     }
  90     c += 16;
  91     m = (1 << c) - 1;
  92     if (s >= 8) {
  93       assert(offs < storage);
  94       buf[offs++] = (uint16_t)(low >> c);
  95       low &= m;
  96       c -= 8;
  97       m >>= 8;
  98     }
  99     assert(offs < storage);
 100     buf[offs++] = (uint16_t)(low >> c);
 101     s = c + d - 24;
 102     low &= m;
 103     enc->offs = offs;
 104   }
 105   enc->low = low << d;
 106   enc->rng = rng << d;
 107   enc->cnt = s;
 108 }
 109
 110 /*Initializes the encoder.
 111   size: The initial size of the buffer, in bytes.*/
 112 void od_ec_enc_init(od_ec_enc *enc, uint32_t size) {
 113   od_ec_enc_reset(enc);
 114   enc->buf = (unsigned char *)malloc(sizeof(*enc->buf) * size);
 115   enc->storage = size;
 116   if (size > 0 && enc->buf == NULL) {
 117     enc->storage = 0;
 118     enc->error = -1;
 119   }
 120   enc->precarry_buf = (uint16_t *)malloc(sizeof(*enc->precarry_buf) * size);
 121   enc->precarry_storage = size;
 122   if (size > 0 && enc->precarry_buf == NULL) {
 123     enc->precarry_storage = 0;
 124     enc->error = -1;
 125   }
 126 }
 127
 128 /*Reinitializes the encoder.*/
 129 void od_ec_enc_reset(od_ec_enc *enc) {
 130   enc->offs = 0;
 131   enc->low = 0;
 132   enc->rng = 0x8000;
 133   /*This is initialized to -9 so that it crosses zero after we've accumulated
 134      one byte + one carry bit.*/
 135   enc->cnt = -9;
 136   enc->error = 0;
 137 #if OD_MEASURE_EC_OVERHEAD
 138   enc->entropy = 0;
 139   enc->nb_symbols = 0;
 140 #endif
 141 }
 142
 143 /*Frees the buffers used by the encoder.*/
 144 void od_ec_enc_clear(od_ec_enc *enc) {
 145   free(enc->precarry_buf);
 146   free(enc->buf);
 147 }
 148
 149 /*Encodes a symbol given its frequency in Q15.
 150   fl: CDF_PROB_TOP minus the cumulative frequency of all symbols that come
 151   before the
 152        one to be encoded.
 153   fh: CDF_PROB_TOP minus the cumulative frequency of all symbols up to and
 154   including
 155        the one to be encoded.*/
 156 static void od_ec_encode_q15(od_ec_enc *enc, unsigned fl, unsigned fh, int s,
 157                              int nsyms) {
 158   od_ec_window l;
 159   unsigned r;
 160   unsigned u;
 161   unsigned v;
 162   l = enc->low;
 163   r = enc->rng;
 164   assert(32768U <= r);
 165   assert(fh <= fl);
 166   assert(fl <= 32768U);
 167   assert(7 - EC_PROB_SHIFT - CDF_SHIFT >= 0);
 168   const int N = nsyms - 1;
 169   if (fl < CDF_PROB_TOP) {
 170     u = ((r >> 8) * (uint32_t)(fl >> EC_PROB_SHIFT) >>
 171          (7 - EC_PROB_SHIFT - CDF_SHIFT)) +
 172         EC_MIN_PROB * (N - (s - 1));
 173     v = ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >>
 174          (7 - EC_PROB_SHIFT - CDF_SHIFT)) +
 175         EC_MIN_PROB * (N - (s + 0));
 176     l += r - u;
 177     r = u - v;
 178   } else {
 179     r -= ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >>
 180           (7 - EC_PROB_SHIFT - CDF_SHIFT)) +
 181          EC_MIN_PROB * (N - (s + 0));
 182   }
 183   od_ec_enc_normalize(enc, l, r);
 184 #if OD_MEASURE_EC_OVERHEAD
 185   enc->entropy -= OD_LOG2((double)(OD_ICDF(fh) - OD_ICDF(fl)) / CDF_PROB_TOP.);
 186   enc->nb_symbols++;
 187 #endif
 188 }
 189
 190 /*Encode a single binary value.
 191   val: The value to encode (0 or 1).
 192   f: The probability that the val is one, scaled by 32768.*/
 193 void od_ec_encode_bool_q15(od_ec_enc *enc, int val, unsigned f) {
 194   od_ec_window l;
 195   unsigned r;
 196   unsigned v;
 197   assert(0 < f);
 198   assert(f < 32768U);
 199   l = enc->low;
 200   r = enc->rng;
 201   assert(32768U <= r);
 202   v = ((r >> 8) * (uint32_t)(f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT));
 203   v += EC_MIN_PROB;
 204   if (val) l += r - v;
 205   r = val ? v : r - v;
 206   od_ec_enc_normalize(enc, l, r);
 207 #if OD_MEASURE_EC_OVERHEAD
 208   enc->entropy -= OD_LOG2((double)(val ? f : (32768 - f)) / 32768.);
 209   enc->nb_symbols++;
 210 #endif
 211 }
 212
 213 /*Encodes a symbol given a cumulative distribution function (CDF) table in Q15.
 214   s: The index of the symbol to encode.
 215   icdf: 32768 minus the CDF, such that symbol s falls in the range
 216          [s > 0 ? (32768 - icdf[s - 1]) : 0, 32768 - icdf[s]).
 217         The values must be monotonically decreasing, and icdf[nsyms - 1] must
 218          be 0.
 219   nsyms: The number of symbols in the alphabet.
 220          This should be at most 16.*/
 221 void od_ec_encode_cdf_q15(od_ec_enc *enc, int s, const uint16_t *icdf,
 222                           int nsyms) {
 223   (void)nsyms;
 224   assert(s >= 0);
 225   assert(s < nsyms);
 226   assert(icdf[nsyms - 1] == OD_ICDF(CDF_PROB_TOP));
 227   od_ec_encode_q15(enc, s > 0 ? icdf[s - 1] : OD_ICDF(0), icdf[s], s, nsyms);
 228 }
 229
 230 /*Overwrites a few bits at the very start of an existing stream, after they
 231    have already been encoded.
 232   This makes it possible to have a few flags up front, where it is easy for
 233    decoders to access them without parsing the whole stream, even if their
 234    values are not determined until late in the encoding process, without having
 235    to buffer all the intermediate symbols in the encoder.
 236   In order for this to work, at least nbits bits must have already been encoded
 237    using probabilities that are an exact power of two.
 238   The encoder can verify the number of encoded bits is sufficient, but cannot
 239    check this latter condition.
 240   val: The bits to encode (in the least nbits significant bits).
 241        They will be decoded in order from most-significant to least.
 242   nbits: The number of bits to overwrite.
 243          This must be no more than 8.*/
 244 void od_ec_enc_patch_initial_bits(od_ec_enc *enc, unsigned val, int nbits) {
 245   int shift;
 246   unsigned mask;
 247   assert(nbits >= 0);
 248   assert(nbits <= 8);
 249   assert(val < 1U << nbits);
 250   shift = 8 - nbits;
 251   mask = ((1U << nbits) - 1) << shift;
 252   if (enc->offs > 0) {
 253     /*The first byte has been finalized.*/
 254     enc->precarry_buf[0] =
 255         (uint16_t)((enc->precarry_buf[0] & ~mask) | val << shift);
 256   } else if (9 + enc->cnt + (enc->rng == 0x8000) > nbits) {
 257     /*The first byte has yet to be output.*/
 258     enc->low = (enc->low & ~((od_ec_window)mask << (16 + enc->cnt))) |
 259                (od_ec_window)val << (16 + enc->cnt + shift);
 260   } else {
 261     /*The encoder hasn't even encoded _nbits of data yet.*/
 262     enc->error = -1;
 263   }
 264 }
 265
 266 #if OD_MEASURE_EC_OVERHEAD
 267 #include <stdio.h>
 268 #endif
 269
 270 /*Indicates that there are no more symbols to encode.
 271   All remaining output bytes are flushed to the output buffer.
 272   od_ec_enc_reset() should be called before using the encoder again.
 273   bytes: Returns the size of the encoded data in the returned buffer.
 274   Return: A pointer to the start of the final buffer, or NULL if there was an
 275            encoding error.*/
 276 unsigned char *od_ec_enc_done(od_ec_enc *enc, uint32_t *nbytes) {
 277   unsigned char *out;
 278   uint32_t storage;
 279   uint16_t *buf;
 280   uint32_t offs;
 281   od_ec_window m;
 282   od_ec_window e;
 283   od_ec_window l;
 284   int c;
 285   int s;
 286   if (enc->error) return NULL;
 287 #if OD_MEASURE_EC_OVERHEAD
 288   {
 289     uint32_t tell;
 290     /* Don't count the 1 bit we lose to raw bits as overhead. */
 291     tell = od_ec_enc_tell(enc) - 1;
 292     fprintf(stderr, "overhead: %f%%\n",
 293             100 * (tell - enc->entropy) / enc->entropy);
 294     fprintf(stderr, "efficiency: %f bits/symbol\n",
 295             (double)tell / enc->nb_symbols);
 296   }
 297 #endif
 298   /*We output the minimum number of bits that ensures that the symbols encoded
 299      thus far will be decoded correctly regardless of the bits that follow.*/
 300   l = enc->low;
 301   c = enc->cnt;
 302   s = 10;
 303   m = 0x3FFF;
 304   e = ((l + m) & ~m) | (m + 1);
 305   s += c;
 306   offs = enc->offs;
 307   buf = enc->precarry_buf;
 308   if (s > 0) {
 309     unsigned n;
 310     storage = enc->precarry_storage;
 311     if (offs + ((s + 7) >> 3) > storage) {
 312       storage = storage * 2 + ((s + 7) >> 3);
 313       buf = (uint16_t *)realloc(buf, sizeof(*buf) * storage);
 314       if (buf == NULL) {
 315         enc->error = -1;
 316         return NULL;
 317       }
 318       enc->precarry_buf = buf;
 319       enc->precarry_storage = storage;
 320     }
 321     n = (1 << (c + 16)) - 1;
 322     do {
 323       assert(offs < storage);
 324       buf[offs++] = (uint16_t)(e >> (c + 16));
 325       e &= n;
 326       s -= 8;
 327       c -= 8;
 328       n >>= 8;
 329     } while (s > 0);
 330   }
 331   /*Make sure there's enough room for the entropy-coded bits.*/
 332   out = enc->buf;
 333   storage = enc->storage;
 334   c = OD_MAXI((s + 7) >> 3, 0);
 335   if (offs + c > storage) {
 336     storage = offs + c;
 337     out = (unsigned char *)realloc(out, sizeof(*out) * storage);
 338     if (out == NULL) {
 339       enc->error = -1;
 340       return NULL;
 341     }
 342     enc->buf = out;
 343     enc->storage = storage;
 344   }
 345   *nbytes = offs;
 346   /*Perform carry propagation.*/
 347   assert(offs <= storage);
 348   out = out + storage - offs;
 349   c = 0;
 350   while (offs > 0) {
 351     offs--;
 352     c = buf[offs] + c;
 353     out[offs] = (unsigned char)c;
 354     c >>= 8;
 355   }
 356   /*Note: Unless there's an allocation error, if you keep encoding into the
 357      current buffer and call this function again later, everything will work
 358      just fine (you won't get a new packet out, but you will get a single
 359      buffer with the new data appended to the old).
 360     However, this function is O(N) where N is the amount of data coded so far,
 361      so calling it more than once for a given packet is a bad idea.*/
 362   return out;
 363 }
 364
 365 /*Returns the number of bits "used" by the encoded symbols so far.
 366   This same number can be computed in either the encoder or the decoder, and is
 367    suitable for making coding decisions.
 368   Warning: The value returned by this function can decrease compared to an
 369    earlier call, even after encoding more data, if there is an encoding error
 370    (i.e., a failure to allocate enough space for the output buffer).
 371   Return: The number of bits.
 372           This will always be slightly larger than the exact value (e.g., all
 373            rounding error is in the positive direction).*/
 374 int od_ec_enc_tell(const od_ec_enc *enc) {
 375   /*The 10 here counteracts the offset of -9 baked into cnt, and adds 1 extra
 376      bit, which we reserve for terminating the stream.*/
 377   return (enc->cnt + 10) + enc->offs * 8;
 378 }
 379
 380 /*Returns the number of bits "used" by the encoded symbols so far.
 381   This same number can be computed in either the encoder or the decoder, and is
 382    suitable for making coding decisions.
 383   Warning: The value returned by this function can decrease compared to an
 384    earlier call, even after encoding more data, if there is an encoding error
 385    (i.e., a failure to allocate enough space for the output buffer).
 386   Return: The number of bits scaled by 2**OD_BITRES.
 387           This will always be slightly larger than the exact value (e.g., all
 388            rounding error is in the positive direction).*/
 389 uint32_t od_ec_enc_tell_frac(const od_ec_enc *enc) {
 390   return od_ec_tell_frac(od_ec_enc_tell(enc), enc->rng);
 391 }
 392
 393 /*Saves a entropy coder checkpoint to dst.
 394   This allows an encoder to reverse a series of entropy coder
 395    decisions if it decides that the information would have been
 396    better coded some other way.*/
 397 void od_ec_enc_checkpoint(od_ec_enc *dst, const od_ec_enc *src) {
 398   OD_COPY(dst, src, 1);
 399 }
 400
 401 /*Restores an entropy coder checkpoint saved by od_ec_enc_checkpoint.
 402   This can only be used to restore from checkpoints earlier in the target
 403    state's history: you can not switch backwards and forwards or otherwise
 404    switch to a state which isn't a casual ancestor of the current state.
 405   Restore is also incompatible with patching the initial bits, as the
 406    changes will remain in the restored version.*/
 407 void od_ec_enc_rollback(od_ec_enc *dst, const od_ec_enc *src) {
 408   unsigned char *buf;
 409   uint32_t storage;
 410   uint16_t *precarry_buf;
 411   uint32_t precarry_storage;
 412   assert(dst->storage >= src->storage);
 413   assert(dst->precarry_storage >= src->precarry_storage);
 414   buf = dst->buf;
 415   storage = dst->storage;
 416   precarry_buf = dst->precarry_buf;
 417   precarry_storage = dst->precarry_storage;
 418   OD_COPY(dst, src, 1);
 419   dst->buf = buf;
 420   dst->storage = storage;
 421   dst->precarry_buf = precarry_buf;
 422   dst->precarry_storage = precarry_storage;
 423 }