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 */
WebRtcIsacfix_EncHistMulti(Bitstr_enc * streamData,const int16_t * data,const uint16_t ** cdf,const int16_t lenData)35 int 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 = 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 <<= 8;
105 if (streamData->full == 0) {
106 *streamPtr++ += (uint16_t)(streamData->streamval >> 24);
107 streamData->full = 1;
108 } else {
109 *streamPtr = (uint16_t)((streamData->streamval >> 24) << 8);
110 streamData->full = 0;
111 }
112
113 if( streamPtr > maxStreamPtr ) {
114 return -ISAC_DISALLOWED_BITSTREAM_LENGTH;
115 }
116 streamData->streamval <<= 8;
117 }
118 }
119
120 /* calculate new stream_index */
121 streamData->stream_index = streamPtr - streamData->stream;
122 streamData->W_upper = W_upper;
123
124 return 0;
125 }
126
127
128 /****************************************************************************
129 * WebRtcIsacfix_DecHistBisectMulti(...)
130 *
131 * Function to decode more symbols from the arithmetic bytestream, using
132 * method of bisection cdf tables should be of size 2^k-1 (which corresponds
133 * to an alphabet size of 2^k-2)
134 *
135 * Input:
136 * - streamData : in-/output struct containing bitstream
137 * - cdf : array of cdf arrays
138 * - cdfSize : array of cdf table sizes+1 (power of two: 2^k)
139 * - lenData : data vector length
140 *
141 * Output:
142 * - data : data vector
143 *
144 * Return value : number of bytes in the stream
145 * <0 if error detected
146 */
WebRtcIsacfix_DecHistBisectMulti(int16_t * data,Bitstr_dec * streamData,const uint16_t ** cdf,const uint16_t * cdfSize,const int16_t lenData)147 int16_t WebRtcIsacfix_DecHistBisectMulti(int16_t *data,
148 Bitstr_dec *streamData,
149 const uint16_t **cdf,
150 const uint16_t *cdfSize,
151 const int16_t lenData)
152 {
153 uint32_t W_lower = 0;
154 uint32_t W_upper;
155 uint32_t W_tmp;
156 uint32_t W_upper_LSB;
157 uint32_t W_upper_MSB;
158 uint32_t streamval;
159 const uint16_t *streamPtr;
160 const uint16_t *cdfPtr;
161 int16_t sizeTmp;
162 int k;
163
164
165 streamPtr = streamData->stream + streamData->stream_index;
166 W_upper = streamData->W_upper;
167
168 /* Error check: should not be possible in normal operation */
169 if (W_upper == 0) {
170 return -2;
171 }
172
173 /* first time decoder is called for this stream */
174 if (streamData->stream_index == 0)
175 {
176 /* read first word from bytestream */
177 streamval = (uint32_t)*streamPtr++ << 16;
178 streamval |= *streamPtr++;
179 } else {
180 streamval = streamData->streamval;
181 }
182
183 for (k = lenData; k > 0; k--)
184 {
185 /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
186 W_upper_LSB = W_upper & 0x0000FFFF;
187 W_upper_MSB = W_upper >> 16;
188
189 /* start halfway the cdf range */
190 sizeTmp = *cdfSize++ / 2;
191 cdfPtr = *cdf + (sizeTmp - 1);
192
193 /* method of bisection */
194 for ( ;; )
195 {
196 W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
197 W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
198 sizeTmp /= 2;
199 if (sizeTmp == 0) {
200 break;
201 }
202
203 if (streamval > W_tmp)
204 {
205 W_lower = W_tmp;
206 cdfPtr += sizeTmp;
207 } else {
208 W_upper = W_tmp;
209 cdfPtr -= sizeTmp;
210 }
211 }
212 if (streamval > W_tmp)
213 {
214 W_lower = W_tmp;
215 *data++ = cdfPtr - *cdf++;
216 } else {
217 W_upper = W_tmp;
218 *data++ = cdfPtr - *cdf++ - 1;
219 }
220
221 /* shift interval to start at zero */
222 W_upper -= ++W_lower;
223
224 /* add integer to bitstream */
225 streamval -= W_lower;
226
227 /* renormalize interval and update streamval */
228 /* W_upper < 2^24 */
229 while ( !(W_upper & 0xFF000000) )
230 {
231 /* read next byte from stream */
232 if (streamData->full == 0) {
233 streamval = (streamval << 8) | (*streamPtr++ & 0x00FF);
234 streamData->full = 1;
235 } else {
236 streamval = (streamval << 8) | (*streamPtr >> 8);
237 streamData->full = 0;
238 }
239 W_upper <<= 8;
240 }
241
242
243 /* Error check: should not be possible in normal operation */
244 if (W_upper == 0) {
245 return -2;
246 }
247
248 }
249
250 streamData->stream_index = streamPtr - streamData->stream;
251 streamData->W_upper = W_upper;
252 streamData->streamval = streamval;
253
254 if ( W_upper > 0x01FFFFFF ) {
255 return (streamData->stream_index*2 - 3 + !streamData->full);
256 } else {
257 return (streamData->stream_index*2 - 2 + !streamData->full);
258 }
259 }
260
261
262 /****************************************************************************
263 * WebRtcIsacfix_DecHistOneStepMulti(...)
264 *
265 * Function to decode more symbols from the arithmetic bytestream, taking
266 * single step up or down at a time.
267 * cdf tables can be of arbitrary size, but large tables may take a lot of
268 * iterations.
269 *
270 * Input:
271 * - streamData : in-/output struct containing bitstream
272 * - cdf : array of cdf arrays
273 * - initIndex : vector of initial cdf table search entries
274 * - lenData : data vector length
275 *
276 * Output:
277 * - data : data vector
278 *
279 * Return value : number of bytes in original stream
280 * <0 if error detected
281 */
WebRtcIsacfix_DecHistOneStepMulti(int16_t * data,Bitstr_dec * streamData,const uint16_t ** cdf,const uint16_t * initIndex,const int16_t lenData)282 int16_t WebRtcIsacfix_DecHistOneStepMulti(int16_t *data,
283 Bitstr_dec *streamData,
284 const uint16_t **cdf,
285 const uint16_t *initIndex,
286 const int16_t lenData)
287 {
288 uint32_t W_lower;
289 uint32_t W_upper;
290 uint32_t W_tmp;
291 uint32_t W_upper_LSB;
292 uint32_t W_upper_MSB;
293 uint32_t streamval;
294 const uint16_t *streamPtr;
295 const uint16_t *cdfPtr;
296 int k;
297
298
299 streamPtr = streamData->stream + streamData->stream_index;
300 W_upper = streamData->W_upper;
301 /* Error check: Should not be possible in normal operation */
302 if (W_upper == 0) {
303 return -2;
304 }
305
306 /* Check if it is the first time decoder is called for this stream */
307 if (streamData->stream_index == 0)
308 {
309 /* read first word from bytestream */
310 streamval = (uint32_t)(*streamPtr++) << 16;
311 streamval |= *streamPtr++;
312 } else {
313 streamval = streamData->streamval;
314 }
315
316 for (k = lenData; k > 0; k--)
317 {
318 /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
319 W_upper_LSB = W_upper & 0x0000FFFF;
320 W_upper_MSB = WEBRTC_SPL_RSHIFT_U32(W_upper, 16);
321
322 /* start at the specified table entry */
323 cdfPtr = *cdf + (*initIndex++);
324 W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
325 W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
326
327 if (streamval > W_tmp)
328 {
329 for ( ;; )
330 {
331 W_lower = W_tmp;
332
333 /* range check */
334 if (cdfPtr[0] == 65535) {
335 return -3;
336 }
337
338 W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *++cdfPtr);
339 W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
340
341 if (streamval <= W_tmp) {
342 break;
343 }
344 }
345 W_upper = W_tmp;
346 *data++ = cdfPtr - *cdf++ - 1;
347 } else {
348 for ( ;; )
349 {
350 W_upper = W_tmp;
351 --cdfPtr;
352
353 /* range check */
354 if (cdfPtr < *cdf) {
355 return -3;
356 }
357
358 W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
359 W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
360
361 if (streamval > W_tmp) {
362 break;
363 }
364 }
365 W_lower = W_tmp;
366 *data++ = cdfPtr - *cdf++;
367 }
368
369 /* shift interval to start at zero */
370 W_upper -= ++W_lower;
371
372 /* add integer to bitstream */
373 streamval -= W_lower;
374
375 /* renormalize interval and update streamval */
376 /* W_upper < 2^24 */
377 while ( !(W_upper & 0xFF000000) )
378 {
379 /* read next byte from stream */
380 if (streamData->full == 0) {
381 streamval = (streamval << 8) | (*streamPtr++ & 0x00FF);
382 streamData->full = 1;
383 } else {
384 streamval = (streamval << 8) | (*streamPtr >> 8);
385 streamData->full = 0;
386 }
387 W_upper <<= 8;
388 }
389 }
390
391 streamData->stream_index = streamPtr - streamData->stream;
392 streamData->W_upper = W_upper;
393 streamData->streamval = streamval;
394
395 /* find number of bytes in original stream (determined by current interval width) */
396 if ( W_upper > 0x01FFFFFF ) {
397 return (streamData->stream_index*2 - 3 + !streamData->full);
398 } else {
399 return (streamData->stream_index*2 - 2 + !streamData->full);
400 }
401 }
402