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#include "settings.h"
12#include "arith_routines.h"
13
14
15/*
16 * code symbols into arithmetic bytestream
17 */
18void WebRtcIsac_EncHistMulti(Bitstr *streamdata, /* in-/output struct containing bitstream */
19                             const int *data,  /* input: data vector */
20                             const uint16_t **cdf, /* input: array of cdf arrays */
21                             const int N)   /* input: data vector length */
22{
23  uint32_t W_lower, W_upper;
24  uint32_t W_upper_LSB, W_upper_MSB;
25  uint8_t *stream_ptr;
26  uint8_t *stream_ptr_carry;
27  uint32_t cdf_lo, cdf_hi;
28  int k;
29
30
31  /* point to beginning of stream buffer */
32  stream_ptr = streamdata->stream + streamdata->stream_index;
33  W_upper = streamdata->W_upper;
34
35  for (k=N; k>0; k--)
36  {
37    /* fetch cdf_lower and cdf_upper from cdf tables */
38    cdf_lo = (uint32_t) *(*cdf + *data);
39    cdf_hi = (uint32_t) *(*cdf++ + *data++ + 1);
40
41    /* update interval */
42    W_upper_LSB = W_upper & 0x0000FFFF;
43    W_upper_MSB = W_upper >> 16;
44    W_lower = W_upper_MSB * cdf_lo;
45    W_lower += (W_upper_LSB * cdf_lo) >> 16;
46    W_upper = W_upper_MSB * cdf_hi;
47    W_upper += (W_upper_LSB * cdf_hi) >> 16;
48
49    /* shift interval such that it begins at zero */
50    W_upper -= ++W_lower;
51
52    /* add integer to bitstream */
53    streamdata->streamval += W_lower;
54
55    /* handle carry */
56    if (streamdata->streamval < W_lower)
57    {
58      /* propagate carry */
59      stream_ptr_carry = stream_ptr;
60      while (!(++(*--stream_ptr_carry)));
61    }
62
63    /* renormalize interval, store most significant byte of streamval and update streamval */
64    while ( !(W_upper & 0xFF000000) )      /* W_upper < 2^24 */
65    {
66      W_upper <<= 8;
67      *stream_ptr++ = (uint8_t) (streamdata->streamval >> 24);
68      streamdata->streamval <<= 8;
69    }
70  }
71
72  /* calculate new stream_index */
73  streamdata->stream_index = (int)(stream_ptr - streamdata->stream);
74  streamdata->W_upper = W_upper;
75
76  return;
77}
78
79
80
81/*
82 * function to decode more symbols from the arithmetic bytestream, using method of bisection
83 * cdf tables should be of size 2^k-1 (which corresponds to an alphabet size of 2^k-2)
84 */
85int WebRtcIsac_DecHistBisectMulti(int *data,     /* output: data vector */
86                                  Bitstr *streamdata,   /* in-/output struct containing bitstream */
87                                  const uint16_t **cdf,  /* input: array of cdf arrays */
88                                  const uint16_t *cdf_size, /* input: array of cdf table sizes+1 (power of two: 2^k) */
89                                  const int N)    /* input: data vector length */
90{
91  uint32_t    W_lower, W_upper;
92  uint32_t    W_tmp;
93  uint32_t    W_upper_LSB, W_upper_MSB;
94  uint32_t    streamval;
95  const   uint8_t *stream_ptr;
96  const   uint16_t *cdf_ptr;
97  int     size_tmp;
98  int     k;
99
100  W_lower = 0; //to remove warning -DH
101  stream_ptr = streamdata->stream + streamdata->stream_index;
102  W_upper = streamdata->W_upper;
103  if (W_upper == 0)
104    /* Should not be possible in normal operation */
105    return -2;
106
107  if (streamdata->stream_index == 0)   /* first time decoder is called for this stream */
108  {
109    /* read first word from bytestream */
110    streamval = *stream_ptr << 24;
111    streamval |= *++stream_ptr << 16;
112    streamval |= *++stream_ptr << 8;
113    streamval |= *++stream_ptr;
114  } else {
115    streamval = streamdata->streamval;
116  }
117
118  for (k=N; k>0; k--)
119  {
120    /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
121    W_upper_LSB = W_upper & 0x0000FFFF;
122    W_upper_MSB = W_upper >> 16;
123
124    /* start halfway the cdf range */
125    size_tmp = *cdf_size++ >> 1;
126    cdf_ptr = *cdf + (size_tmp - 1);
127
128    /* method of bisection */
129    for ( ;; )
130    {
131      W_tmp = W_upper_MSB * *cdf_ptr;
132      W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
133      size_tmp >>= 1;
134      if (size_tmp == 0) break;
135      if (streamval > W_tmp)
136      {
137        W_lower = W_tmp;
138        cdf_ptr += size_tmp;
139      } else {
140        W_upper = W_tmp;
141        cdf_ptr -= size_tmp;
142      }
143    }
144    if (streamval > W_tmp)
145    {
146      W_lower = W_tmp;
147      *data++ = (int)(cdf_ptr - *cdf++);
148    } else {
149      W_upper = W_tmp;
150      *data++ = (int)(cdf_ptr - *cdf++ - 1);
151    }
152
153    /* shift interval to start at zero */
154    W_upper -= ++W_lower;
155
156    /* add integer to bitstream */
157    streamval -= W_lower;
158
159    /* renormalize interval and update streamval */
160    while ( !(W_upper & 0xFF000000) )    /* W_upper < 2^24 */
161    {
162      /* read next byte from stream */
163      streamval = (streamval << 8) | *++stream_ptr;
164      W_upper <<= 8;
165    }
166
167    if (W_upper == 0)
168      /* Should not be possible in normal operation */
169      return -2;
170
171
172  }
173
174  streamdata->stream_index = (int)(stream_ptr - streamdata->stream);
175  streamdata->W_upper = W_upper;
176  streamdata->streamval = streamval;
177
178
179  /* find number of bytes in original stream (determined by current interval width) */
180  if ( W_upper > 0x01FFFFFF )
181    return streamdata->stream_index - 2;
182  else
183    return streamdata->stream_index - 1;
184}
185
186
187
188/*
189 * function to decode more symbols from the arithmetic bytestream, taking single step up or
190 * down at a time
191 * cdf tables can be of arbitrary size, but large tables may take a lot of iterations
192 */
193int WebRtcIsac_DecHistOneStepMulti(int *data,        /* output: data vector */
194                                   Bitstr *streamdata,      /* in-/output struct containing bitstream */
195                                   const uint16_t **cdf,   /* input: array of cdf arrays */
196                                   const uint16_t *init_index, /* input: vector of initial cdf table search entries */
197                                   const int N)     /* input: data vector length */
198{
199  uint32_t    W_lower, W_upper;
200  uint32_t    W_tmp;
201  uint32_t    W_upper_LSB, W_upper_MSB;
202  uint32_t    streamval;
203  const   uint8_t *stream_ptr;
204  const   uint16_t *cdf_ptr;
205  int     k;
206
207
208  stream_ptr = streamdata->stream + streamdata->stream_index;
209  W_upper = streamdata->W_upper;
210  if (W_upper == 0)
211    /* Should not be possible in normal operation */
212    return -2;
213
214  if (streamdata->stream_index == 0)   /* first time decoder is called for this stream */
215  {
216    /* read first word from bytestream */
217    streamval = *stream_ptr << 24;
218    streamval |= *++stream_ptr << 16;
219    streamval |= *++stream_ptr << 8;
220    streamval |= *++stream_ptr;
221  } else {
222    streamval = streamdata->streamval;
223  }
224
225
226  for (k=N; k>0; k--)
227  {
228    /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
229    W_upper_LSB = W_upper & 0x0000FFFF;
230    W_upper_MSB = W_upper >> 16;
231
232    /* start at the specified table entry */
233    cdf_ptr = *cdf + (*init_index++);
234    W_tmp = W_upper_MSB * *cdf_ptr;
235    W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
236    if (streamval > W_tmp)
237    {
238      for ( ;; )
239      {
240        W_lower = W_tmp;
241        if (cdf_ptr[0]==65535)
242          /* range check */
243          return -3;
244        W_tmp = W_upper_MSB * *++cdf_ptr;
245        W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
246        if (streamval <= W_tmp) break;
247      }
248      W_upper = W_tmp;
249      *data++ = (int)(cdf_ptr - *cdf++ - 1);
250    } else {
251      for ( ;; )
252      {
253        W_upper = W_tmp;
254        --cdf_ptr;
255        if (cdf_ptr<*cdf) {
256          /* range check */
257          return -3;
258        }
259        W_tmp = W_upper_MSB * *cdf_ptr;
260        W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
261        if (streamval > W_tmp) break;
262      }
263      W_lower = W_tmp;
264      *data++ = (int)(cdf_ptr - *cdf++);
265    }
266
267    /* shift interval to start at zero */
268    W_upper -= ++W_lower;
269    /* add integer to bitstream */
270    streamval -= W_lower;
271
272    /* renormalize interval and update streamval */
273    while ( !(W_upper & 0xFF000000) )    /* W_upper < 2^24 */
274    {
275      /* read next byte from stream */
276      streamval = (streamval << 8) | *++stream_ptr;
277      W_upper <<= 8;
278    }
279  }
280
281  streamdata->stream_index = (int)(stream_ptr - streamdata->stream);
282  streamdata->W_upper = W_upper;
283  streamdata->streamval = streamval;
284
285
286  /* find number of bytes in original stream (determined by current interval width) */
287  if ( W_upper > 0x01FFFFFF )
288    return streamdata->stream_index - 2;
289  else
290    return streamdata->stream_index - 1;
291}
292