1/*
2 *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
3 *
4 *  Use of this source code is governed by a BSD-style license
5 *  that can be found in the LICENSE file in the root of the source
6 *  tree. An additional intellectual property rights grant can be found
7 *  in the file PATENTS.  All contributing project authors may
8 *  be found in the AUTHORS file in the root of the source tree.
9 */
10
11/*
12 * arith_routinshist.c
13 *
14 * This C file contains arithmetic encoding and decoding.
15 *
16 */
17
18#include "arith_routins.h"
19
20
21/****************************************************************************
22 * WebRtcIsacfix_EncHistMulti(...)
23 *
24 * Encode the histogram interval
25 *
26 * Input:
27 *      - streamData        : in-/output struct containing bitstream
28 *      - data              : data vector
29 *      - cdf               : array of cdf arrays
30 *      - lenData           : data vector length
31 *
32 * Return value             : 0 if ok
33 *                            <0 if error detected
34 */
35int WebRtcIsacfix_EncHistMulti(Bitstr_enc *streamData,
36                               const int16_t *data,
37                               const uint16_t **cdf,
38                               const int16_t lenData)
39{
40  uint32_t W_lower;
41  uint32_t W_upper;
42  uint32_t W_upper_LSB;
43  uint32_t W_upper_MSB;
44  uint16_t *streamPtr;
45  uint16_t negCarry;
46  uint16_t *maxStreamPtr;
47  uint16_t *streamPtrCarry;
48  uint32_t cdfLo;
49  uint32_t cdfHi;
50  int k;
51
52
53  /* point to beginning of stream buffer
54   * and set maximum streamPtr value */
55  streamPtr = streamData->stream + streamData->stream_index;
56  maxStreamPtr = streamData->stream + STREAM_MAXW16_60MS - 1;
57
58  W_upper = streamData->W_upper;
59
60  for (k = lenData; k > 0; k--)
61  {
62    /* fetch cdf_lower and cdf_upper from cdf tables */
63    cdfLo = (uint32_t) *(*cdf + (uint32_t)*data);
64    cdfHi = (uint32_t) *(*cdf++ + (uint32_t)*data++ + 1);
65
66    /* update interval */
67    W_upper_LSB = W_upper & 0x0000FFFF;
68    W_upper_MSB = WEBRTC_SPL_RSHIFT_W32(W_upper, 16);
69    W_lower = WEBRTC_SPL_UMUL(W_upper_MSB, cdfLo);
70    W_lower += ((W_upper_LSB * cdfLo) >> 16);
71    W_upper = WEBRTC_SPL_UMUL(W_upper_MSB, cdfHi);
72    W_upper += ((W_upper_LSB * cdfHi) >> 16);
73
74    /* shift interval such that it begins at zero */
75    W_upper -= ++W_lower;
76
77    /* add integer to bitstream */
78    streamData->streamval += W_lower;
79
80    /* handle carry */
81    if (streamData->streamval < W_lower)
82    {
83      /* propagate carry */
84      streamPtrCarry = streamPtr;
85      if (streamData->full == 0) {
86        negCarry = *streamPtrCarry;
87        negCarry += 0x0100;
88        *streamPtrCarry = negCarry;
89        while (!(negCarry))
90        {
91          negCarry = *--streamPtrCarry;
92          negCarry++;
93          *streamPtrCarry = negCarry;
94        }
95      } else {
96        while ( !(++(*--streamPtrCarry)) );
97      }
98    }
99
100    /* renormalize interval, store most significant byte of streamval and update streamval
101     * W_upper < 2^24 */
102    while ( !(W_upper & 0xFF000000) )
103    {
104      W_upper = WEBRTC_SPL_LSHIFT_W32(W_upper, 8);
105      if (streamData->full == 0) {
106        *streamPtr++ += (uint16_t) WEBRTC_SPL_RSHIFT_W32(streamData->streamval, 24);
107        streamData->full = 1;
108      } else {
109        *streamPtr = (uint16_t) WEBRTC_SPL_LSHIFT_W32(
110            WEBRTC_SPL_RSHIFT_W32(streamData->streamval, 24), 8);
111        streamData->full = 0;
112      }
113
114      if( streamPtr > maxStreamPtr ) {
115        return -ISAC_DISALLOWED_BITSTREAM_LENGTH;
116      }
117      streamData->streamval = WEBRTC_SPL_LSHIFT_W32(streamData->streamval, 8);
118    }
119  }
120
121  /* calculate new stream_index */
122  streamData->stream_index = streamPtr - streamData->stream;
123  streamData->W_upper = W_upper;
124
125  return 0;
126}
127
128
129/****************************************************************************
130 * WebRtcIsacfix_DecHistBisectMulti(...)
131 *
132 * Function to decode more symbols from the arithmetic bytestream, using
133 * method of bisection cdf tables should be of size 2^k-1 (which corresponds
134 * to an alphabet size of 2^k-2)
135 *
136 * Input:
137 *      - streamData        : in-/output struct containing bitstream
138 *      - cdf               : array of cdf arrays
139 *      - cdfSize           : array of cdf table sizes+1 (power of two: 2^k)
140 *      - lenData           : data vector length
141 *
142 * Output:
143 *      - data              : data vector
144 *
145 * Return value             : number of bytes in the stream
146 *                            <0 if error detected
147 */
148int16_t WebRtcIsacfix_DecHistBisectMulti(int16_t *data,
149                                         Bitstr_dec *streamData,
150                                         const uint16_t **cdf,
151                                         const uint16_t *cdfSize,
152                                         const int16_t lenData)
153{
154  uint32_t    W_lower = 0;
155  uint32_t    W_upper;
156  uint32_t    W_tmp;
157  uint32_t    W_upper_LSB;
158  uint32_t    W_upper_MSB;
159  uint32_t    streamval;
160  const uint16_t *streamPtr;
161  const uint16_t *cdfPtr;
162  int16_t     sizeTmp;
163  int             k;
164
165
166  streamPtr = streamData->stream + streamData->stream_index;
167  W_upper = streamData->W_upper;
168
169  /* Error check: should not be possible in normal operation */
170  if (W_upper == 0) {
171    return -2;
172  }
173
174  /* first time decoder is called for this stream */
175  if (streamData->stream_index == 0)
176  {
177    /* read first word from bytestream */
178    streamval = WEBRTC_SPL_LSHIFT_W32((uint32_t)*streamPtr++, 16);
179    streamval |= *streamPtr++;
180  } else {
181    streamval = streamData->streamval;
182  }
183
184  for (k = lenData; k > 0; k--)
185  {
186    /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
187    W_upper_LSB = W_upper & 0x0000FFFF;
188    W_upper_MSB = WEBRTC_SPL_RSHIFT_W32(W_upper, 16);
189
190    /* start halfway the cdf range */
191    sizeTmp = WEBRTC_SPL_RSHIFT_W16(*cdfSize++, 1);
192    cdfPtr = *cdf + (sizeTmp - 1);
193
194    /* method of bisection */
195    for ( ;; )
196    {
197      W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
198      W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
199      sizeTmp = WEBRTC_SPL_RSHIFT_W16(sizeTmp, 1);
200      if (sizeTmp == 0) {
201        break;
202      }
203
204      if (streamval > W_tmp)
205      {
206        W_lower = W_tmp;
207        cdfPtr += sizeTmp;
208      } else {
209        W_upper = W_tmp;
210        cdfPtr -= sizeTmp;
211      }
212    }
213    if (streamval > W_tmp)
214    {
215      W_lower = W_tmp;
216      *data++ = cdfPtr - *cdf++;
217    } else {
218      W_upper = W_tmp;
219      *data++ = cdfPtr - *cdf++ - 1;
220    }
221
222    /* shift interval to start at zero */
223    W_upper -= ++W_lower;
224
225    /* add integer to bitstream */
226    streamval -= W_lower;
227
228    /* renormalize interval and update streamval */
229    /* W_upper < 2^24 */
230    while ( !(W_upper & 0xFF000000) )
231    {
232      /* read next byte from stream */
233      if (streamData->full == 0) {
234        streamval = WEBRTC_SPL_LSHIFT_W32(streamval, 8) |
235            (*streamPtr++ & 0x00FF);
236        streamData->full = 1;
237      } else {
238        streamval = WEBRTC_SPL_LSHIFT_W32(streamval, 8) |
239            WEBRTC_SPL_RSHIFT_W16(*streamPtr, 8);
240        streamData->full = 0;
241      }
242      W_upper = WEBRTC_SPL_LSHIFT_W32(W_upper, 8);
243    }
244
245
246    /* Error check: should not be possible in normal operation */
247    if (W_upper == 0) {
248      return -2;
249    }
250
251  }
252
253  streamData->stream_index = streamPtr - streamData->stream;
254  streamData->W_upper = W_upper;
255  streamData->streamval = streamval;
256
257  if ( W_upper > 0x01FFFFFF ) {
258    return (streamData->stream_index*2 - 3 + !streamData->full);
259  } else {
260    return (streamData->stream_index*2 - 2 + !streamData->full);
261  }
262}
263
264
265/****************************************************************************
266 * WebRtcIsacfix_DecHistOneStepMulti(...)
267 *
268 * Function to decode more symbols from the arithmetic bytestream, taking
269 * single step up or down at a time.
270 * cdf tables can be of arbitrary size, but large tables may take a lot of
271 * iterations.
272 *
273 * Input:
274 *      - streamData        : in-/output struct containing bitstream
275 *      - cdf               : array of cdf arrays
276 *      - initIndex         : vector of initial cdf table search entries
277 *      - lenData           : data vector length
278 *
279 * Output:
280 *      - data              : data vector
281 *
282 * Return value             : number of bytes in original stream
283 *                            <0 if error detected
284 */
285int16_t WebRtcIsacfix_DecHistOneStepMulti(int16_t *data,
286                                          Bitstr_dec *streamData,
287                                          const uint16_t **cdf,
288                                          const uint16_t *initIndex,
289                                          const int16_t lenData)
290{
291  uint32_t    W_lower;
292  uint32_t    W_upper;
293  uint32_t    W_tmp;
294  uint32_t    W_upper_LSB;
295  uint32_t    W_upper_MSB;
296  uint32_t    streamval;
297  const uint16_t *streamPtr;
298  const uint16_t *cdfPtr;
299  int             k;
300
301
302  streamPtr = streamData->stream + streamData->stream_index;
303  W_upper = streamData->W_upper;
304  /* Error check: Should not be possible in normal operation */
305  if (W_upper == 0) {
306    return -2;
307  }
308
309  /* Check if it is the first time decoder is called for this stream */
310  if (streamData->stream_index == 0)
311  {
312    /* read first word from bytestream */
313    streamval = WEBRTC_SPL_LSHIFT_U32(*streamPtr++, 16);
314    streamval |= *streamPtr++;
315  } else {
316    streamval = streamData->streamval;
317  }
318
319  for (k = lenData; k > 0; k--)
320  {
321    /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
322    W_upper_LSB = W_upper & 0x0000FFFF;
323    W_upper_MSB = WEBRTC_SPL_RSHIFT_U32(W_upper, 16);
324
325    /* start at the specified table entry */
326    cdfPtr = *cdf + (*initIndex++);
327    W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
328    W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
329
330    if (streamval > W_tmp)
331    {
332      for ( ;; )
333      {
334        W_lower = W_tmp;
335
336        /* range check */
337        if (cdfPtr[0] == 65535) {
338          return -3;
339        }
340
341        W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *++cdfPtr);
342        W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
343
344        if (streamval <= W_tmp) {
345          break;
346        }
347      }
348      W_upper = W_tmp;
349      *data++ = cdfPtr - *cdf++ - 1;
350    } else {
351      for ( ;; )
352      {
353        W_upper = W_tmp;
354        --cdfPtr;
355
356        /* range check */
357        if (cdfPtr < *cdf) {
358          return -3;
359        }
360
361        W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
362        W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
363
364        if (streamval > W_tmp) {
365          break;
366        }
367      }
368      W_lower = W_tmp;
369      *data++ = cdfPtr - *cdf++;
370    }
371
372    /* shift interval to start at zero */
373    W_upper -= ++W_lower;
374
375    /* add integer to bitstream */
376    streamval -= W_lower;
377
378    /* renormalize interval and update streamval */
379    /* W_upper < 2^24 */
380    while ( !(W_upper & 0xFF000000) )
381    {
382      /* read next byte from stream */
383      if (streamData->full == 0) {
384        streamval = WEBRTC_SPL_LSHIFT_W32(streamval, 8) | (*streamPtr++ & 0x00FF);
385        streamData->full = 1;
386      } else {
387        streamval = WEBRTC_SPL_LSHIFT_W32(streamval, 8) | (*streamPtr >> 8);
388        streamData->full = 0;
389      }
390      W_upper = WEBRTC_SPL_LSHIFT_W32(W_upper, 8);
391    }
392  }
393
394  streamData->stream_index = streamPtr - streamData->stream;
395  streamData->W_upper = W_upper;
396  streamData->streamval = streamval;
397
398  /* find number of bytes in original stream (determined by current interval width) */
399  if ( W_upper > 0x01FFFFFF ) {
400    return (streamData->stream_index*2 - 3 + !streamData->full);
401  } else {
402    return (streamData->stream_index*2 - 2 + !streamData->full);
403  }
404}
405