Coverage Report

Created: 2025-06-22 08:04

/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 output 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_enc_window low,
57
0
                                unsigned rng) {
58
0
  int d;
59
0
  int c;
60
0
  int s;
61
0
  if (enc->error) return;
62
0
  c = enc->cnt;
63
0
  assert(rng <= 65535U);
64
  /*The number of leading zeros in the 16-bit binary representation of rng.*/
65
0
  d = 16 - OD_ILOG_NZ(rng);
66
0
  s = c + d;
67
68
  /* We flush every time "low" cannot safely and efficiently accommodate any
69
     more data. Overall, c must not exceed 63 at the time of byte flush out. To
70
     facilitate this, "s" cannot exceed 56-bits because we have to keep 1 byte
71
     for carry. Also, we need to subtract 16 because we want to keep room for
72
     the next symbol worth "d"-bits (max 15). An alternate condition would be if
73
     (e < d), where e = number of leading zeros in "low", indicating there is
74
     not enough rooom to accommodate "rng" worth of "d"-bits in "low". However,
75
     this approach needs additional computations: (i) compute "e", (ii) push
76
     the leading 0x00's as a special case.
77
  */
78
0
  if (s >= 40) {  // 56 - 16
79
0
    unsigned char *out = enc->buf;
80
0
    uint32_t storage = enc->storage;
81
0
    uint32_t offs = enc->offs;
82
0
    if (offs + 8 > storage) {
83
0
      storage = 2 * storage + 8;
84
0
      out = (unsigned char *)realloc(out, sizeof(*out) * storage);
85
0
      if (out == NULL) {
86
0
        enc->error = -1;
87
0
        return;
88
0
      }
89
0
      enc->buf = out;
90
0
      enc->storage = storage;
91
0
    }
92
    // Need to add 1 byte here since enc->cnt always counts 1 byte less
93
    // (enc->cnt = -9) to ensure correct operation
94
0
    uint8_t num_bytes_ready = (s >> 3) + 1;
95
96
    // Update "c" to contain the number of non-ready bits in "low". Since "low"
97
    // has 64-bit capacity, we need to add the (64 - 40) cushion bits and take
98
    // off the number of ready bits.
99
0
    c += 24 - (num_bytes_ready << 3);
100
101
    // Prepare "output" and update "low"
102
0
    uint64_t output = low >> c;
103
0
    low = low & (((uint64_t)1 << c) - 1);
104
105
    // Prepare data and carry mask
106
0
    uint64_t mask = (uint64_t)1 << (num_bytes_ready << 3);
107
0
    uint64_t carry = output & mask;
108
109
0
    mask = mask - 0x01;
110
0
    output = output & mask;
111
112
    // Write data in a single operation
113
0
    write_enc_data_to_out_buf(out, offs, output, carry, &enc->offs,
114
0
                              num_bytes_ready);
115
116
    // Update state of the encoder: enc->cnt to contain the number of residual
117
    // bits
118
0
    s = c + d - 24;
119
0
  }
120
0
  enc->low = low << d;
121
0
  enc->rng = rng << d;
122
0
  enc->cnt = s;
123
0
}
124
125
/*Initializes the encoder.
126
  size: The initial size of the buffer, in bytes.*/
127
0
void od_ec_enc_init(od_ec_enc *enc, uint32_t size) {
128
0
  od_ec_enc_reset(enc);
129
0
  enc->buf = (unsigned char *)malloc(sizeof(*enc->buf) * size);
130
0
  enc->storage = size;
131
0
  if (size > 0 && enc->buf == NULL) {
132
0
    enc->storage = 0;
133
0
    enc->error = -1;
134
0
  }
135
0
}
136
137
/*Reinitializes the encoder.*/
138
0
void od_ec_enc_reset(od_ec_enc *enc) {
139
0
  enc->offs = 0;
140
0
  enc->low = 0;
141
0
  enc->rng = 0x8000;
142
  /*This is initialized to -9 so that it crosses zero after we've accumulated
143
     one byte + one carry bit.*/
144
0
  enc->cnt = -9;
145
0
  enc->error = 0;
146
#if OD_MEASURE_EC_OVERHEAD
147
  enc->entropy = 0;
148
  enc->nb_symbols = 0;
149
#endif
150
0
}
151
152
/*Frees the buffers used by the encoder.*/
153
0
void od_ec_enc_clear(od_ec_enc *enc) { free(enc->buf); }
154
155
/*Encodes a symbol given its frequency in Q15.
156
  fl: CDF_PROB_TOP minus the cumulative frequency of all symbols that come
157
  before the one to be encoded.
158
  fh: CDF_PROB_TOP minus the cumulative frequency of all symbols up to and
159
  including the one to be encoded.*/
160
static void od_ec_encode_q15(od_ec_enc *enc, unsigned fl, unsigned fh, int s,
161
0
                             int nsyms) {
162
0
  od_ec_enc_window l;
163
0
  unsigned r;
164
0
  unsigned u;
165
0
  unsigned v;
166
0
  l = enc->low;
167
0
  r = enc->rng;
168
0
  assert(32768U <= r);
169
0
  assert(fh <= fl);
170
0
  assert(fl <= 32768U);
171
0
  assert(7 - EC_PROB_SHIFT >= 0);
172
0
  const int N = nsyms - 1;
173
0
  if (fl < CDF_PROB_TOP) {
174
0
    u = ((r >> 8) * (uint32_t)(fl >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)) +
175
0
        EC_MIN_PROB * (N - (s - 1));
176
0
    v = ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)) +
177
0
        EC_MIN_PROB * (N - (s + 0));
178
0
    l += r - u;
179
0
    r = u - v;
180
0
  } else {
181
0
    r -= ((r >> 8) * (uint32_t)(fh >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT)) +
182
0
         EC_MIN_PROB * (N - (s + 0));
183
0
  }
184
0
  od_ec_enc_normalize(enc, l, r);
185
#if OD_MEASURE_EC_OVERHEAD
186
  enc->entropy -= OD_LOG2((double)(OD_ICDF(fh) - OD_ICDF(fl)) / CDF_PROB_TOP.);
187
  enc->nb_symbols++;
188
#endif
189
0
}
190
191
/*Encode a single binary value.
192
  val: The value to encode (0 or 1).
193
  f: The probability that the val is one, scaled by 32768.*/
194
0
void od_ec_encode_bool_q15(od_ec_enc *enc, int val, unsigned f) {
195
0
  od_ec_enc_window l;
196
0
  unsigned r;
197
0
  unsigned v;
198
0
  assert(0 < f);
199
0
  assert(f < 32768U);
200
0
  l = enc->low;
201
0
  r = enc->rng;
202
0
  assert(32768U <= r);
203
0
  v = ((r >> 8) * (uint32_t)(f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT));
204
0
  v += EC_MIN_PROB;
205
0
  if (val) l += r - v;
206
0
  r = val ? v : r - v;
207
0
  od_ec_enc_normalize(enc, l, r);
208
#if OD_MEASURE_EC_OVERHEAD
209
  enc->entropy -= OD_LOG2((double)(val ? f : (32768 - f)) / 32768.);
210
  enc->nb_symbols++;
211
#endif
212
0
}
213
214
/*Encodes a symbol given a cumulative distribution function (CDF) table in Q15.
215
  s: The index of the symbol to encode.
216
  icdf: 32768 minus the CDF, such that symbol s falls in the range
217
         [s > 0 ? (32768 - icdf[s - 1]) : 0, 32768 - icdf[s]).
218
        The values must be monotonically decreasing, and icdf[nsyms - 1] must
219
         be 0.
220
  nsyms: The number of symbols in the alphabet.
221
         This should be at most 16.*/
222
void od_ec_encode_cdf_q15(od_ec_enc *enc, int s, const uint16_t *icdf,
223
0
                          int nsyms) {
224
0
  (void)nsyms;
225
0
  assert(s >= 0);
226
0
  assert(s < nsyms);
227
0
  assert(icdf[nsyms - 1] == OD_ICDF(CDF_PROB_TOP));
228
0
  od_ec_encode_q15(enc, s > 0 ? icdf[s - 1] : OD_ICDF(0), icdf[s], s, nsyms);
229
0
}
230
231
#if OD_MEASURE_EC_OVERHEAD
232
#include <stdio.h>
233
#endif
234
235
/*Indicates that there are no more symbols to encode.
236
  All remaining output bytes are flushed to the output buffer.
237
  od_ec_enc_reset() should be called before using the encoder again.
238
  bytes: Returns the size of the encoded data in the returned buffer.
239
  Return: A pointer to the start of the final buffer, or NULL if there was an
240
           encoding error.*/
241
0
unsigned char *od_ec_enc_done(od_ec_enc *enc, uint32_t *nbytes) {
242
0
  unsigned char *out;
243
0
  uint32_t storage;
244
0
  uint32_t offs;
245
0
  od_ec_enc_window m;
246
0
  od_ec_enc_window e;
247
0
  od_ec_enc_window l;
248
0
  int c;
249
0
  int s;
250
0
  if (enc->error) return NULL;
251
#if OD_MEASURE_EC_OVERHEAD
252
  {
253
    uint32_t tell;
254
    /* Don't count the 1 bit we lose to raw bits as overhead. */
255
    tell = od_ec_enc_tell(enc) - 1;
256
    fprintf(stderr, "overhead: %f%%\n",
257
            100 * (tell - enc->entropy) / enc->entropy);
258
    fprintf(stderr, "efficiency: %f bits/symbol\n",
259
            (double)tell / enc->nb_symbols);
260
  }
261
#endif
262
263
0
  l = enc->low;
264
0
  c = enc->cnt;
265
0
  s = 10;
266
0
  m = 0x3FFF;
267
0
  e = ((l + m) & ~m) | (m + 1);
268
0
  s += c;
269
0
  offs = enc->offs;
270
271
  /*Make sure there's enough room for the entropy-coded bits.*/
272
0
  out = enc->buf;
273
0
  storage = enc->storage;
274
0
  const int s_bits = (s + 7) >> 3;
275
0
  int b = OD_MAXI(s_bits, 0);
276
0
  if (offs + b > storage) {
277
0
    storage = offs + b;
278
0
    out = (unsigned char *)realloc(out, sizeof(*out) * storage);
279
0
    if (out == NULL) {
280
0
      enc->error = -1;
281
0
      return NULL;
282
0
    }
283
0
    enc->buf = out;
284
0
    enc->storage = storage;
285
0
  }
286
287
  /*We output the minimum number of bits that ensures that the symbols encoded
288
     thus far will be decoded correctly regardless of the bits that follow.*/
289
0
  if (s > 0) {
290
0
    uint64_t n;
291
0
    n = ((uint64_t)1 << (c + 16)) - 1;
292
0
    do {
293
0
      assert(offs < storage);
294
0
      uint16_t val = (uint16_t)(e >> (c + 16));
295
0
      out[offs] = (unsigned char)(val & 0x00FF);
296
0
      if (val & 0x0100) {
297
0
        assert(offs > 0);
298
0
        propagate_carry_bwd(out, offs - 1);
299
0
      }
300
0
      offs++;
301
302
0
      e &= n;
303
0
      s -= 8;
304
0
      c -= 8;
305
0
      n >>= 8;
306
0
    } while (s > 0);
307
0
  }
308
0
  *nbytes = offs;
309
310
0
  return out;
311
0
}
312
313
/*Returns the number of bits "used" by the encoded symbols so far.
314
  This same number can be computed in either the encoder or the decoder, and is
315
   suitable for making coding decisions.
316
  Warning: The value returned by this function can decrease compared to an
317
   earlier call, even after encoding more data, if there is an encoding error
318
   (i.e., a failure to allocate enough space for the output buffer).
319
  Return: The number of bits.
320
          This will always be slightly larger than the exact value (e.g., all
321
           rounding error is in the positive direction).*/
322
0
int od_ec_enc_tell(const od_ec_enc *enc) {
323
  /*The 10 here counteracts the offset of -9 baked into cnt, and adds 1 extra
324
     bit, which we reserve for terminating the stream.*/
325
0
  return (enc->cnt + 10) + enc->offs * 8;
326
0
}
327
328
/*Returns the number of bits "used" by the encoded symbols so far.
329
  This same number can be computed in either the encoder or the decoder, and is
330
   suitable for making coding decisions.
331
  Warning: The value returned by this function can decrease compared to an
332
   earlier call, even after encoding more data, if there is an encoding error
333
   (i.e., a failure to allocate enough space for the output buffer).
334
  Return: The number of bits scaled by 2**OD_BITRES.
335
          This will always be slightly larger than the exact value (e.g., all
336
           rounding error is in the positive direction).*/
337
0
uint32_t od_ec_enc_tell_frac(const od_ec_enc *enc) {
338
0
  return od_ec_tell_frac(od_ec_enc_tell(enc), enc->rng);
339
0
}