Coverage Report

Created: 2022-08-24 06:17

/src/aom/aom_dsp/entenc.c
Line
Count
Source (jump to first uncovered line)
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
937k
                                unsigned rng) {
58
937k
  int d;
59
937k
  int c;
60
937k
  int s;
61
937k
  c = enc->cnt;
62
937k
  assert(rng <= 65535U);
63
  /*The number of leading zeros in the 16-bit binary representation of rng.*/
64
937k
  d = 16 - OD_ILOG_NZ(rng);
65
937k
  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
937k
  if (s >= 0) {
72
21.6k
    uint16_t *buf;
73
21.6k
    uint32_t storage;
74
21.6k
    uint32_t offs;
75
21.6k
    unsigned m;
76
21.6k
    buf = enc->precarry_buf;
77
21.6k
    storage = enc->precarry_storage;
78
21.6k
    offs = enc->offs;
79
21.6k
    if (offs + 2 > storage) {
80
0
      storage = 2 * storage + 2;
81
0
      buf = (uint16_t *)realloc(buf, sizeof(*buf) * storage);
82
0
      if (buf == NULL) {
83
0
        enc->error = -1;
84
0
        enc->offs = 0;
85
0
        return;
86
0
      }
87
0
      enc->precarry_buf = buf;
88
0
      enc->precarry_storage = storage;
89
0
    }
90
21.6k
    c += 16;
91
21.6k
    m = (1 << c) - 1;
92
21.6k
    if (s >= 8) {
93
0
      assert(offs < storage);
94
0
      buf[offs++] = (uint16_t)(low >> c);
95
0
      low &= m;
96
0
      c -= 8;
97
0
      m >>= 8;
98
0
    }
99
21.6k
    assert(offs < storage);
100
21.6k
    buf[offs++] = (uint16_t)(low >> c);
101
21.6k
    s = c + d - 24;
102
21.6k
    low &= m;
103
21.6k
    enc->offs = offs;
104
21.6k
  }
105
937k
  enc->low = low << d;
106
937k
  enc->rng = rng << d;
107
937k
  enc->cnt = s;
108
937k
}
109
110
/*Initializes the encoder.
111
  size: The initial size of the buffer, in bytes.*/
112
1.26k
void od_ec_enc_init(od_ec_enc *enc, uint32_t size) {
113
1.26k
  od_ec_enc_reset(enc);
114
1.26k
  enc->buf = (unsigned char *)malloc(sizeof(*enc->buf) * size);
115
1.26k
  enc->storage = size;
116
1.26k
  if (size > 0 && enc->buf == NULL) {
117
0
    enc->storage = 0;
118
0
    enc->error = -1;
119
0
  }
120
1.26k
  enc->precarry_buf = (uint16_t *)malloc(sizeof(*enc->precarry_buf) * size);
121
1.26k
  enc->precarry_storage = size;
122
1.26k
  if (size > 0 && enc->precarry_buf == NULL) {
123
0
    enc->precarry_storage = 0;
124
0
    enc->error = -1;
125
0
  }
126
1.26k
}
127
128
/*Reinitializes the encoder.*/
129
1.26k
void od_ec_enc_reset(od_ec_enc *enc) {
130
1.26k
  enc->offs = 0;
131
1.26k
  enc->low = 0;
132
1.26k
  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
1.26k
  enc->cnt = -9;
136
1.26k
  enc->error = 0;
137
#if OD_MEASURE_EC_OVERHEAD
138
  enc->entropy = 0;
139
  enc->nb_symbols = 0;
140
#endif
141
1.26k
}
142
143
/*Frees the buffers used by the encoder.*/
144
1.26k
void od_ec_enc_clear(od_ec_enc *enc) {
145
1.26k
  free(enc->precarry_buf);
146
1.26k
  free(enc->buf);
147
1.26k
}
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
882k
                             int nsyms) {
158
882k
  od_ec_window l;
159
882k
  unsigned r;
160
882k
  unsigned u;
161
882k
  unsigned v;
162
882k
  l = enc->low;
163
882k
  r = enc->rng;
164
882k
  assert(32768U <= r);
165
882k
  assert(fh <= fl);
166
882k
  assert(fl <= 32768U);
167
882k
  assert(7 - EC_PROB_SHIFT - CDF_SHIFT >= 0);
168
882k
  const int N = nsyms - 1;
169
882k
  if (fl < CDF_PROB_TOP) {
170
820k
    u = ((r >> 8) * (uint32_t)(fl >> EC_PROB_SHIFT) >>
171
820k
         (7 - EC_PROB_SHIFT - CDF_SHIFT)) +
172
820k
        EC_MIN_PROB * (N - (s - 1));
173
820k
    v = ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >>
174
820k
         (7 - EC_PROB_SHIFT - CDF_SHIFT)) +
175
820k
        EC_MIN_PROB * (N - (s + 0));
176
820k
    l += r - u;
177
820k
    r = u - v;
178
820k
  } else {
179
61.9k
    r -= ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >>
180
61.9k
          (7 - EC_PROB_SHIFT - CDF_SHIFT)) +
181
61.9k
         EC_MIN_PROB * (N - (s + 0));
182
61.9k
  }
183
882k
  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
882k
}
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
54.4k
void od_ec_encode_bool_q15(od_ec_enc *enc, int val, unsigned f) {
194
54.4k
  od_ec_window l;
195
54.4k
  unsigned r;
196
54.4k
  unsigned v;
197
54.4k
  assert(0 < f);
198
54.4k
  assert(f < 32768U);
199
54.4k
  l = enc->low;
200
54.4k
  r = enc->rng;
201
54.4k
  assert(32768U <= r);
202
54.4k
  v = ((r >> 8) * (uint32_t)(f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT));
203
54.4k
  v += EC_MIN_PROB;
204
54.4k
  if (val) l += r - v;
205
54.4k
  r = val ? v : r - v;
206
54.4k
  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
54.4k
}
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
882k
                          int nsyms) {
223
882k
  (void)nsyms;
224
882k
  assert(s >= 0);
225
882k
  assert(s < nsyms);
226
882k
  assert(icdf[nsyms - 1] == OD_ICDF(CDF_PROB_TOP));
227
882k
  od_ec_encode_q15(enc, s > 0 ? icdf[s - 1] : OD_ICDF(0), icdf[s], s, nsyms);
228
882k
}
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
0
void od_ec_enc_patch_initial_bits(od_ec_enc *enc, unsigned val, int nbits) {
245
0
  int shift;
246
0
  unsigned mask;
247
0
  assert(nbits >= 0);
248
0
  assert(nbits <= 8);
249
0
  assert(val < 1U << nbits);
250
0
  shift = 8 - nbits;
251
0
  mask = ((1U << nbits) - 1) << shift;
252
0
  if (enc->offs > 0) {
253
    /*The first byte has been finalized.*/
254
0
    enc->precarry_buf[0] =
255
0
        (uint16_t)((enc->precarry_buf[0] & ~mask) | val << shift);
256
0
  } else if (9 + enc->cnt + (enc->rng == 0x8000) > nbits) {
257
    /*The first byte has yet to be output.*/
258
0
    enc->low = (enc->low & ~((od_ec_window)mask << (16 + enc->cnt))) |
259
0
               (od_ec_window)val << (16 + enc->cnt + shift);
260
0
  } else {
261
    /*The encoder hasn't even encoded _nbits of data yet.*/
262
0
    enc->error = -1;
263
0
  }
264
0
}
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
1.26k
unsigned char *od_ec_enc_done(od_ec_enc *enc, uint32_t *nbytes) {
277
1.26k
  unsigned char *out;
278
1.26k
  uint32_t storage;
279
1.26k
  uint16_t *buf;
280
1.26k
  uint32_t offs;
281
1.26k
  od_ec_window m;
282
1.26k
  od_ec_window e;
283
1.26k
  od_ec_window l;
284
1.26k
  int c;
285
1.26k
  int s;
286
1.26k
  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
1.26k
  l = enc->low;
301
1.26k
  c = enc->cnt;
302
1.26k
  s = 10;
303
1.26k
  m = 0x3FFF;
304
1.26k
  e = ((l + m) & ~m) | (m + 1);
305
1.26k
  s += c;
306
1.26k
  offs = enc->offs;
307
1.26k
  buf = enc->precarry_buf;
308
1.26k
  if (s > 0) {
309
1.26k
    unsigned n;
310
1.26k
    storage = enc->precarry_storage;
311
1.26k
    if (offs + ((s + 7) >> 3) > storage) {
312
0
      storage = storage * 2 + ((s + 7) >> 3);
313
0
      buf = (uint16_t *)realloc(buf, sizeof(*buf) * storage);
314
0
      if (buf == NULL) {
315
0
        enc->error = -1;
316
0
        return NULL;
317
0
      }
318
0
      enc->precarry_buf = buf;
319
0
      enc->precarry_storage = storage;
320
0
    }
321
1.26k
    n = (1 << (c + 16)) - 1;
322
1.43k
    do {
323
1.43k
      assert(offs < storage);
324
1.43k
      buf[offs++] = (uint16_t)(e >> (c + 16));
325
1.43k
      e &= n;
326
1.43k
      s -= 8;
327
1.43k
      c -= 8;
328
1.43k
      n >>= 8;
329
1.43k
    } while (s > 0);
330
1.26k
  }
331
  /*Make sure there's enough room for the entropy-coded bits.*/
332
1.26k
  out = enc->buf;
333
1.26k
  storage = enc->storage;
334
1.26k
  c = OD_MAXI((s + 7) >> 3, 0);
335
1.26k
  if (offs + c > storage) {
336
0
    storage = offs + c;
337
0
    out = (unsigned char *)realloc(out, sizeof(*out) * storage);
338
0
    if (out == NULL) {
339
0
      enc->error = -1;
340
0
      return NULL;
341
0
    }
342
0
    enc->buf = out;
343
0
    enc->storage = storage;
344
0
  }
345
1.26k
  *nbytes = offs;
346
  /*Perform carry propagation.*/
347
1.26k
  assert(offs <= storage);
348
1.26k
  out = out + storage - offs;
349
1.26k
  c = 0;
350
24.3k
  while (offs > 0) {
351
23.1k
    offs--;
352
23.1k
    c = buf[offs] + c;
353
23.1k
    out[offs] = (unsigned char)c;
354
23.1k
    c >>= 8;
355
23.1k
  }
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
1.26k
  return out;
363
1.26k
}
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
24.8k
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
24.8k
  return (enc->cnt + 10) + enc->offs * 8;
378
24.8k
}
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
0
uint32_t od_ec_enc_tell_frac(const od_ec_enc *enc) {
390
0
  return od_ec_tell_frac(od_ec_enc_tell(enc), enc->rng);
391
0
}
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
0
void od_ec_enc_checkpoint(od_ec_enc *dst, const od_ec_enc *src) {
398
0
  OD_COPY(dst, src, 1);
399
0
}
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
0
void od_ec_enc_rollback(od_ec_enc *dst, const od_ec_enc *src) {
408
0
  unsigned char *buf;
409
0
  uint32_t storage;
410
0
  uint16_t *precarry_buf;
411
0
  uint32_t precarry_storage;
412
0
  assert(dst->storage >= src->storage);
413
0
  assert(dst->precarry_storage >= src->precarry_storage);
414
0
  buf = dst->buf;
415
0
  storage = dst->storage;
416
0
  precarry_buf = dst->precarry_buf;
417
0
  precarry_storage = dst->precarry_storage;
418
0
  OD_COPY(dst, src, 1);
419
0
  dst->buf = buf;
420
0
  dst->storage = storage;
421
0
  dst->precarry_buf = precarry_buf;
422
0
  dst->precarry_storage = precarry_storage;
423
0
}