summaryrefslogtreecommitdiffstats
path: root/third_party/aom/aom_dsp/entenc.c
blob: 591e0ad214b69ae0b28509cc3c8ea87dff5698eb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
/*
 * Copyright (c) 2001-2016, Alliance for Open Media. All rights reserved
 *
 * This source code is subject to the terms of the BSD 2 Clause License and
 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
 * was not distributed with this source code in the LICENSE file, you can
 * obtain it at www.aomedia.org/license/software. If the Alliance for Open
 * Media Patent License 1.0 was not distributed with this source code in the
 * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
 */

#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include "aom_dsp/entenc.h"
#include "aom_dsp/prob.h"

#if OD_MEASURE_EC_OVERHEAD
#if !defined(M_LOG2E)
#define M_LOG2E (1.4426950408889634073599246810019)
#endif
#define OD_LOG2(x) (M_LOG2E * log(x))
#endif  // OD_MEASURE_EC_OVERHEAD

/*A range encoder.
  See entdec.c and the references for implementation details \cite{Mar79,MNW98}.

  @INPROCEEDINGS{Mar79,
   author="Martin, G.N.N.",
   title="Range encoding: an algorithm for removing redundancy from a digitised
    message",
   booktitle="Video \& Data Recording Conference",
   year=1979,
   address="Southampton",
   month=Jul,
   URL="http://www.compressconsult.com/rangecoder/rngcod.pdf.gz"
  }
  @ARTICLE{MNW98,
   author="Alistair Moffat and Radford Neal and Ian H. Witten",
   title="Arithmetic Coding Revisited",
   journal="{ACM} Transactions on Information Systems",
   year=1998,
   volume=16,
   number=3,
   pages="256--294",
   month=Jul,
   URL="http://researchcommons.waikato.ac.nz/bitstream/handle/10289/78/content.pdf"
  }*/

/*Takes updated low and range values, renormalizes them so that
   32768 <= rng < 65536 (flushing bytes from low to the output buffer if
   necessary), and stores them back in the encoder context.
  low: The new value of low.
  rng: The new value of the range.*/
static void od_ec_enc_normalize(od_ec_enc *enc, od_ec_enc_window low,
                                unsigned rng) {
  int d;
  int c;
  int s;
  if (enc->error) return;
  c = enc->cnt;
  assert(rng <= 65535U);
  /*The number of leading zeros in the 16-bit binary representation of rng.*/
  d = 16 - OD_ILOG_NZ(rng);
  s = c + d;

  /* We flush every time "low" cannot safely and efficiently accommodate any
     more data. Overall, c must not exceed 63 at the time of byte flush out. To
     facilitate this, "s" cannot exceed 56-bits because we have to keep 1 byte
     for carry. Also, we need to subtract 16 because we want to keep room for
     the next symbol worth "d"-bits (max 15). An alternate condition would be if
     (e < d), where e = number of leading zeros in "low", indicating there is
     not enough rooom to accommodate "rng" worth of "d"-bits in "low". However,
     this approach needs additional computations: (i) compute "e", (ii) push
     the leading 0x00's as a special case.
  */
  if (s >= 40) {  // 56 - 16
    unsigned char *out = enc->buf;
    uint32_t storage = enc->storage;
    uint32_t offs = enc->offs;
    if (offs + 8 > storage) {
      storage = 2 * storage + 8;
      out = (unsigned char *)realloc(out, sizeof(*out) * storage);
      if (out == NULL) {
        enc->error = -1;
        return;
      }
      enc->buf = out;
      enc->storage = storage;
    }
    // Need to add 1 byte here since enc->cnt always counts 1 byte less
    // (enc->cnt = -9) to ensure correct operation
    uint8_t num_bytes_ready = (s >> 3) + 1;

    // Update "c" to contain the number of non-ready bits in "low". Since "low"
    // has 64-bit capacity, we need to add the (64 - 40) cushion bits and take
    // off the number of ready bits.
    c += 24 - (num_bytes_ready << 3);

    // Prepare "output" and update "low"
    uint64_t output = low >> c;
    low = low & (((uint64_t)1 << c) - 1);

    // Prepare data and carry mask
    uint64_t mask = (uint64_t)1 << (num_bytes_ready << 3);
    uint64_t carry = output & mask;

    mask = mask - 0x01;
    output = output & mask;

    // Write data in a single operation
    write_enc_data_to_out_buf(out, offs, output, carry, &enc->offs,
                              num_bytes_ready);

    // Update state of the encoder: enc->cnt to contain the number of residual
    // bits
    s = c + d - 24;
  }
  enc->low = low << d;
  enc->rng = rng << d;
  enc->cnt = s;
}

/*Initializes the encoder.
  size: The initial size of the buffer, in bytes.*/
void od_ec_enc_init(od_ec_enc *enc, uint32_t size) {
  od_ec_enc_reset(enc);
  enc->buf = (unsigned char *)malloc(sizeof(*enc->buf) * size);
  enc->storage = size;
  if (size > 0 && enc->buf == NULL) {
    enc->storage = 0;
    enc->error = -1;
  }
}

/*Reinitializes the encoder.*/
void od_ec_enc_reset(od_ec_enc *enc) {
  enc->offs = 0;
  enc->low = 0;
  enc->rng = 0x8000;
  /*This is initialized to -9 so that it crosses zero after we've accumulated
     one byte + one carry bit.*/
  enc->cnt = -9;
  enc->error = 0;
#if OD_MEASURE_EC_OVERHEAD
  enc->entropy = 0;
  enc->nb_symbols = 0;
#endif
}

/*Frees the buffers used by the encoder.*/
void od_ec_enc_clear(od_ec_enc *enc) { free(enc->buf); }

/*Encodes a symbol given its frequency in Q15.
  fl: CDF_PROB_TOP minus the cumulative frequency of all symbols that come
  before the one to be encoded.
  fh: CDF_PROB_TOP minus the cumulative frequency of all symbols up to and
  including the one to be encoded.*/
static void od_ec_encode_q15(od_ec_enc *enc, unsigned fl, unsigned fh, int s,
                             int nsyms) {
  od_ec_enc_window l;
  unsigned r;
  unsigned u;
  unsigned v;
  l = enc->low;
  r = enc->rng;
  assert(32768U <= r);
  assert(fh <= fl);
  assert(fl <= 32768U);
  assert(7 - EC_PROB_SHIFT >= 0);
  const int N = nsyms - 1;
  if (fl < CDF_PROB_TOP) {
    u = ((r >> 8) * (uint32_t)(fl >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)) +
        EC_MIN_PROB * (N - (s - 1));
    v = ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)) +
        EC_MIN_PROB * (N - (s + 0));
    l += r - u;
    r = u - v;
  } else {
    r -= ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)) +
         EC_MIN_PROB * (N - (s + 0));
  }
  od_ec_enc_normalize(enc, l, r);
#if OD_MEASURE_EC_OVERHEAD
  enc->entropy -= OD_LOG2((double)(OD_ICDF(fh) - OD_ICDF(fl)) / CDF_PROB_TOP.);
  enc->nb_symbols++;
#endif
}

/*Encode a single binary value.
  val: The value to encode (0 or 1).
  f: The probability that the val is one, scaled by 32768.*/
void od_ec_encode_bool_q15(od_ec_enc *enc, int val, unsigned f) {
  od_ec_enc_window l;
  unsigned r;
  unsigned v;
  assert(0 < f);
  assert(f < 32768U);
  l = enc->low;
  r = enc->rng;
  assert(32768U <= r);
  v = ((r >> 8) * (uint32_t)(f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT));
  v += EC_MIN_PROB;
  if (val) l += r - v;
  r = val ? v : r - v;
  od_ec_enc_normalize(enc, l, r);
#if OD_MEASURE_EC_OVERHEAD
  enc->entropy -= OD_LOG2((double)(val ? f : (32768 - f)) / 32768.);
  enc->nb_symbols++;
#endif
}

/*Encodes a symbol given a cumulative distribution function (CDF) table in Q15.
  s: The index of the symbol to encode.
  icdf: 32768 minus the CDF, such that symbol s falls in the range
         [s > 0 ? (32768 - icdf[s - 1]) : 0, 32768 - icdf[s]).
        The values must be monotonically decreasing, and icdf[nsyms - 1] must
         be 0.
  nsyms: The number of symbols in the alphabet.
         This should be at most 16.*/
void od_ec_encode_cdf_q15(od_ec_enc *enc, int s, const uint16_t *icdf,
                          int nsyms) {
  (void)nsyms;
  assert(s >= 0);
  assert(s < nsyms);
  assert(icdf[nsyms - 1] == OD_ICDF(CDF_PROB_TOP));
  od_ec_encode_q15(enc, s > 0 ? icdf[s - 1] : OD_ICDF(0), icdf[s], s, nsyms);
}

/*Overwrites a few bits at the very start of an existing stream, after they
   have already been encoded.
  This makes it possible to have a few flags up front, where it is easy for
   decoders to access them without parsing the whole stream, even if their
   values are not determined until late in the encoding process, without having
   to buffer all the intermediate symbols in the encoder.
  In order for this to work, at least nbits bits must have already been encoded
   using probabilities that are an exact power of two.
  The encoder can verify the number of encoded bits is sufficient, but cannot
   check this latter condition.
  val: The bits to encode (in the least nbits significant bits).
       They will be decoded in order from most-significant to least.
  nbits: The number of bits to overwrite.
         This must be no more than 8.*/
void od_ec_enc_patch_initial_bits(od_ec_enc *enc, unsigned val, int nbits) {
  int shift;
  unsigned mask;
  assert(nbits >= 0);
  assert(nbits <= 8);
  assert(val < 1U << nbits);
  shift = 8 - nbits;
  mask = ((1U << nbits) - 1) << shift;
  if (enc->offs > 0) {
    /*The first byte has been finalized.*/
    enc->buf[0] = (unsigned char)((enc->buf[0] & ~mask) | val << shift);
  } else if (9 + enc->cnt + (enc->rng == 0x8000) > nbits) {
    /*The first byte has yet to be output.*/
    enc->low = (enc->low & ~((od_ec_enc_window)mask << (16 + enc->cnt))) |
               (od_ec_enc_window)val << (16 + enc->cnt + shift);
  } else {
    /*The encoder hasn't even encoded _nbits of data yet.*/
    enc->error = -1;
  }
}

#if OD_MEASURE_EC_OVERHEAD
#include <stdio.h>
#endif

/*Indicates that there are no more symbols to encode.
  All remaining output bytes are flushed to the output buffer.
  od_ec_enc_reset() should be called before using the encoder again.
  bytes: Returns the size of the encoded data in the returned buffer.
  Return: A pointer to the start of the final buffer, or NULL if there was an
           encoding error.*/
unsigned char *od_ec_enc_done(od_ec_enc *enc, uint32_t *nbytes) {
  unsigned char *out;
  uint32_t storage;
  uint32_t offs;
  od_ec_enc_window m;
  od_ec_enc_window e;
  od_ec_enc_window l;
  int c;
  int s;
  if (enc->error) return NULL;
#if OD_MEASURE_EC_OVERHEAD
  {
    uint32_t tell;
    /* Don't count the 1 bit we lose to raw bits as overhead. */
    tell = od_ec_enc_tell(enc) - 1;
    fprintf(stderr, "overhead: %f%%\n",
            100 * (tell - enc->entropy) / enc->entropy);
    fprintf(stderr, "efficiency: %f bits/symbol\n",
            (double)tell / enc->nb_symbols);
  }
#endif

  l = enc->low;
  c = enc->cnt;
  s = 10;
  m = 0x3FFF;
  e = ((l + m) & ~m) | (m + 1);
  s += c;
  offs = enc->offs;

  /*Make sure there's enough room for the entropy-coded bits.*/
  out = enc->buf;
  storage = enc->storage;
  const int s_bits = (s + 7) >> 3;
  int b = OD_MAXI(s_bits, 0);
  if (offs + b > storage) {
    storage = offs + b;
    out = (unsigned char *)realloc(out, sizeof(*out) * storage);
    if (out == NULL) {
      enc->error = -1;
      return NULL;
    }
    enc->buf = out;
    enc->storage = storage;
  }

  /*We output the minimum number of bits that ensures that the symbols encoded
     thus far will be decoded correctly regardless of the bits that follow.*/
  if (s > 0) {
    uint64_t n;
    n = ((uint64_t)1 << (c + 16)) - 1;
    do {
      assert(offs < storage);
      uint16_t val = (uint16_t)(e >> (c + 16));
      out[offs] = (unsigned char)(val & 0x00FF);
      if (val & 0x0100) {
        assert(offs > 0);
        propagate_carry_bwd(out, offs - 1);
      }
      offs++;

      e &= n;
      s -= 8;
      c -= 8;
      n >>= 8;
    } while (s > 0);
  }
  *nbytes = offs;

  return out;
}

/*Returns the number of bits "used" by the encoded symbols so far.
  This same number can be computed in either the encoder or the decoder, and is
   suitable for making coding decisions.
  Warning: The value returned by this function can decrease compared to an
   earlier call, even after encoding more data, if there is an encoding error
   (i.e., a failure to allocate enough space for the output buffer).
  Return: The number of bits.
          This will always be slightly larger than the exact value (e.g., all
           rounding error is in the positive direction).*/
int od_ec_enc_tell(const od_ec_enc *enc) {
  /*The 10 here counteracts the offset of -9 baked into cnt, and adds 1 extra
     bit, which we reserve for terminating the stream.*/
  return (enc->cnt + 10) + enc->offs * 8;
}

/*Returns the number of bits "used" by the encoded symbols so far.
  This same number can be computed in either the encoder or the decoder, and is
   suitable for making coding decisions.
  Warning: The value returned by this function can decrease compared to an
   earlier call, even after encoding more data, if there is an encoding error
   (i.e., a failure to allocate enough space for the output buffer).
  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_enc_tell_frac(const od_ec_enc *enc) {
  return od_ec_tell_frac(od_ec_enc_tell(enc), enc->rng);
}