Coverage Report

Created: 2022-08-24 06:17

/src/aom/aom_dsp/entdec.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 <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
3.40k
#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
4.11M
static void od_ec_dec_refill(od_ec_dec *dec) {
79
4.11M
  int s;
80
4.11M
  od_ec_window dif;
81
4.11M
  int16_t cnt;
82
4.11M
  const unsigned char *bptr;
83
4.11M
  const unsigned char *end;
84
4.11M
  dif = dec->dif;
85
4.11M
  cnt = dec->cnt;
86
4.11M
  bptr = dec->bptr;
87
4.11M
  end = dec->end;
88
4.11M
  s = OD_EC_WINDOW_SIZE - 9 - (cnt + 15);
89
12.3M
  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
8.24M
    assert(s <= OD_EC_WINDOW_SIZE - 8);
94
8.24M
    dif ^= (od_ec_window)bptr[0] << s;
95
8.24M
    cnt += 8;
96
8.24M
  }
97
4.11M
  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
1.70k
    dec->tell_offs += OD_EC_LOTS_OF_BITS - cnt;
110
1.70k
    cnt = OD_EC_LOTS_OF_BITS;
111
1.70k
  }
112
4.11M
  dec->dif = dif;
113
4.11M
  dec->cnt = cnt;
114
4.11M
  dec->bptr = bptr;
115
4.11M
}
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
64.8M
                               int ret) {
127
64.8M
  int d;
128
64.8M
  assert(rng <= 65535U);
129
  /*The number of leading zeros in the 16-bit binary representation of rng.*/
130
64.8M
  d = 16 - OD_ILOG_NZ(rng);
131
  /*d bits in dec->dif are consumed.*/
132
64.8M
  dec->cnt -= d;
133
  /*This is equivalent to shifting in 1's instead of 0's.*/
134
64.8M
  dec->dif = ((dif + 1) << d) - 1;
135
64.8M
  dec->rng = rng << d;
136
64.8M
  if (dec->cnt < 0) od_ec_dec_refill(dec);
137
64.8M
  return ret;
138
64.8M
}
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
1.96k
                    uint32_t storage) {
145
1.96k
  dec->buf = buf;
146
1.96k
  dec->tell_offs = 10 - (OD_EC_WINDOW_SIZE - 8);
147
1.96k
  dec->end = buf + storage;
148
1.96k
  dec->bptr = buf;
149
1.96k
  dec->dif = ((od_ec_window)1 << (OD_EC_WINDOW_SIZE - 1)) - 1;
150
1.96k
  dec->rng = 0x8000;
151
1.96k
  dec->cnt = -15;
152
1.96k
  od_ec_dec_refill(dec);
153
1.96k
}
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
12.9M
int od_ec_decode_bool_q15(od_ec_dec *dec, unsigned f) {
159
12.9M
  od_ec_window dif;
160
12.9M
  od_ec_window vw;
161
12.9M
  unsigned r;
162
12.9M
  unsigned r_new;
163
12.9M
  unsigned v;
164
12.9M
  int ret;
165
12.9M
  assert(0 < f);
166
12.9M
  assert(f < 32768U);
167
12.9M
  dif = dec->dif;
168
12.9M
  r = dec->rng;
169
12.9M
  assert(dif >> (OD_EC_WINDOW_SIZE - 16) < r);
170
12.9M
  assert(32768U <= r);
171
12.9M
  v = ((r >> 8) * (uint32_t)(f >> EC_PROB_SHIFT) >> (7 - EC_PROB_SHIFT));
172
12.9M
  v += EC_MIN_PROB;
173
12.9M
  vw = (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16);
174
12.9M
  ret = 1;
175
12.9M
  r_new = v;
176
12.9M
  if (dif >= vw) {
177
6.42M
    r_new = r - v;
178
6.42M
    dif -= vw;
179
6.42M
    ret = 0;
180
6.42M
  }
181
12.9M
  return od_ec_dec_normalize(dec, dif, r_new, ret);
182
12.9M
}
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
51.8M
int od_ec_decode_cdf_q15(od_ec_dec *dec, const uint16_t *icdf, int nsyms) {
194
51.8M
  od_ec_window dif;
195
51.8M
  unsigned r;
196
51.8M
  unsigned c;
197
51.8M
  unsigned u;
198
51.8M
  unsigned v;
199
51.8M
  int ret;
200
51.8M
  (void)nsyms;
201
51.8M
  dif = dec->dif;
202
51.8M
  r = dec->rng;
203
51.8M
  const int N = nsyms - 1;
204
205
51.8M
  assert(dif >> (OD_EC_WINDOW_SIZE - 16) < r);
206
51.8M
  assert(icdf[nsyms - 1] == OD_ICDF(CDF_PROB_TOP));
207
51.8M
  assert(32768U <= r);
208
51.8M
  assert(7 - EC_PROB_SHIFT - CDF_SHIFT >= 0);
209
51.8M
  c = (unsigned)(dif >> (OD_EC_WINDOW_SIZE - 16));
210
51.8M
  v = r;
211
51.8M
  ret = -1;
212
185M
  do {
213
185M
    u = v;
214
185M
    v = ((r >> 8) * (uint32_t)(icdf[++ret] >> EC_PROB_SHIFT) >>
215
185M
         (7 - EC_PROB_SHIFT - CDF_SHIFT));
216
185M
    v += EC_MIN_PROB * (N - ret);
217
185M
  } while (c < v);
218
51.8M
  assert(v < u);
219
51.8M
  assert(u <= r);
220
51.8M
  r = u - v;
221
51.8M
  dif -= (od_ec_window)v << (OD_EC_WINDOW_SIZE - 16);
222
51.8M
  return od_ec_dec_normalize(dec, dif, r, ret);
223
51.8M
}
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
420k
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
420k
  return (int)((dec->bptr - dec->buf) * 8 - dec->cnt + dec->tell_offs);
237
420k
}
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
0
uint32_t od_ec_dec_tell_frac(const od_ec_dec *dec) {
246
0
  return od_ec_tell_frac(od_ec_dec_tell(dec), dec->rng);
247
0
}