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 */
WebRtcIsac_EncHistMulti(Bitstr * streamdata,const int * data,const uint16_t ** cdf,const int N)18 void 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 */
WebRtcIsac_DecHistBisectMulti(int * data,Bitstr * streamdata,const uint16_t ** cdf,const uint16_t * cdf_size,const int N)85 int 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 */
WebRtcIsac_DecHistOneStepMulti(int * data,Bitstr * streamdata,const uint16_t ** cdf,const uint16_t * init_index,const int N)193 int 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