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 WebRtc_Word16 * data,const WebRtc_UWord16 ** cdf,const WebRtc_Word16 lenData)35 int WebRtcIsacfix_EncHistMulti(Bitstr_enc *streamData,
36 const WebRtc_Word16 *data,
37 const WebRtc_UWord16 **cdf,
38 const WebRtc_Word16 lenData)
39 {
40 WebRtc_UWord32 W_lower;
41 WebRtc_UWord32 W_upper;
42 WebRtc_UWord32 W_upper_LSB;
43 WebRtc_UWord32 W_upper_MSB;
44 WebRtc_UWord16 *streamPtr;
45 WebRtc_UWord16 negCarry;
46 WebRtc_UWord16 *maxStreamPtr;
47 WebRtc_UWord16 *streamPtrCarry;
48 WebRtc_UWord32 cdfLo;
49 WebRtc_UWord32 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 = (WebRtc_UWord32) *(*cdf + (WebRtc_UWord32)*data);
64 cdfHi = (WebRtc_UWord32) *(*cdf++ + (WebRtc_UWord32)*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 += WEBRTC_SPL_UMUL_RSFT16(W_upper_LSB, cdfLo);
71 W_upper = WEBRTC_SPL_UMUL(W_upper_MSB, cdfHi);
72 W_upper += WEBRTC_SPL_UMUL_RSFT16(W_upper_LSB, cdfHi);
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++ += (WebRtc_UWord16) WEBRTC_SPL_RSHIFT_W32(streamData->streamval, 24);
107 streamData->full = 1;
108 } else {
109 *streamPtr = (WebRtc_UWord16) 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 */
WebRtcIsacfix_DecHistBisectMulti(WebRtc_Word16 * data,Bitstr_dec * streamData,const WebRtc_UWord16 ** cdf,const WebRtc_UWord16 * cdfSize,const WebRtc_Word16 lenData)148 WebRtc_Word16 WebRtcIsacfix_DecHistBisectMulti(WebRtc_Word16 *data,
149 Bitstr_dec *streamData,
150 const WebRtc_UWord16 **cdf,
151 const WebRtc_UWord16 *cdfSize,
152 const WebRtc_Word16 lenData)
153 {
154 WebRtc_UWord32 W_lower = 0;
155 WebRtc_UWord32 W_upper;
156 WebRtc_UWord32 W_tmp;
157 WebRtc_UWord32 W_upper_LSB;
158 WebRtc_UWord32 W_upper_MSB;
159 WebRtc_UWord32 streamval;
160 const WebRtc_UWord16 *streamPtr;
161 const WebRtc_UWord16 *cdfPtr;
162 WebRtc_Word16 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((WebRtc_UWord32)*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 += WEBRTC_SPL_UMUL_32_16_RSFT16(W_upper_LSB, *cdfPtr);
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 */
WebRtcIsacfix_DecHistOneStepMulti(WebRtc_Word16 * data,Bitstr_dec * streamData,const WebRtc_UWord16 ** cdf,const WebRtc_UWord16 * initIndex,const WebRtc_Word16 lenData)285 WebRtc_Word16 WebRtcIsacfix_DecHistOneStepMulti(WebRtc_Word16 *data,
286 Bitstr_dec *streamData,
287 const WebRtc_UWord16 **cdf,
288 const WebRtc_UWord16 *initIndex,
289 const WebRtc_Word16 lenData)
290 {
291 WebRtc_UWord32 W_lower;
292 WebRtc_UWord32 W_upper;
293 WebRtc_UWord32 W_tmp;
294 WebRtc_UWord32 W_upper_LSB;
295 WebRtc_UWord32 W_upper_MSB;
296 WebRtc_UWord32 streamval;
297 const WebRtc_UWord16 *streamPtr;
298 const WebRtc_UWord16 *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 += WEBRTC_SPL_UMUL_32_16_RSFT16(W_upper_LSB, *cdfPtr);
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 += WEBRTC_SPL_UMUL_32_16_RSFT16(W_upper_LSB, *cdfPtr);
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 += WEBRTC_SPL_UMUL_32_16_RSFT16(W_upper_LSB, *cdfPtr);
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