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_routinslogist.c
13 *
14 * This C file contains arithmetic encode and decode logistic
15 *
16 */
17
18 #include "arith_routins.h"
19
20
21 /* Tables for piecewise linear cdf functions: y = k*x */
22
23 /* x Points for function piecewise() in Q15 */
24 static const WebRtc_Word32 kHistEdges[51] = {
25 -327680, -314573, -301466, -288359, -275252, -262144, -249037, -235930, -222823, -209716,
26 -196608, -183501, -170394, -157287, -144180, -131072, -117965, -104858, -91751, -78644,
27 -65536, -52429, -39322, -26215, -13108, 0, 13107, 26214, 39321, 52428,
28 65536, 78643, 91750, 104857, 117964, 131072, 144179, 157286, 170393, 183500,
29 196608, 209715, 222822, 235929, 249036, 262144, 275251, 288358, 301465, 314572,
30 327680
31 };
32
33
34 /* k Points for function piecewise() in Q0 */
35 static const WebRtc_UWord16 kCdfSlope[51] = {
36 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
37 5, 5, 13, 23, 47, 87, 154, 315, 700, 1088,
38 2471, 6064, 14221, 21463, 36634, 36924, 19750, 13270, 5806, 2312,
39 1095, 660, 316, 145, 86, 41, 32, 5, 5, 5,
40 5, 5, 5, 5, 5, 5, 5, 5, 5, 2,
41 0
42 };
43
44 /* y Points for function piecewise() in Q0 */
45 static const WebRtc_UWord16 kCdfLogistic[51] = {
46 0, 2, 4, 6, 8, 10, 12, 14, 16, 18,
47 20, 22, 24, 29, 38, 57, 92, 153, 279, 559,
48 994, 1983, 4408, 10097, 18682, 33336, 48105, 56005, 61313, 63636,
49 64560, 64998, 65262, 65389, 65447, 65481, 65497, 65510, 65512, 65514,
50 65516, 65518, 65520, 65522, 65524, 65526, 65528, 65530, 65532, 65534,
51 65535
52 };
53
54
55 /****************************************************************************
56 * WebRtcIsacfix_Piecewise(...)
57 *
58 * Piecewise linear function
59 *
60 * Input:
61 * - xinQ15 : input value x in Q15
62 *
63 * Return value : korresponding y-value in Q0
64 */
65
66
WebRtcIsacfix_Piecewise(WebRtc_Word32 xinQ15)67 static __inline WebRtc_UWord16 WebRtcIsacfix_Piecewise(WebRtc_Word32 xinQ15) {
68 WebRtc_Word32 ind;
69 WebRtc_Word32 qtmp1;
70 WebRtc_UWord16 qtmp2;
71
72 /* Find index for x-value */
73 qtmp1 = WEBRTC_SPL_SAT(kHistEdges[50],xinQ15,kHistEdges[0]);
74 ind = WEBRTC_SPL_MUL(5, qtmp1 - kHistEdges[0]);
75 ind = WEBRTC_SPL_RSHIFT_W32(ind, 16);
76
77 /* Calculate corresponding y-value ans return*/
78 qtmp1 = qtmp1 - kHistEdges[ind];
79 qtmp2 = (WebRtc_UWord16)WEBRTC_SPL_RSHIFT_U32(
80 WEBRTC_SPL_UMUL_32_16(qtmp1,kCdfSlope[ind]), 15);
81 return (kCdfLogistic[ind] + qtmp2);
82 }
83
84 /****************************************************************************
85 * WebRtcIsacfix_EncLogisticMulti2(...)
86 *
87 * Arithmetic coding of spectrum.
88 *
89 * Input:
90 * - streamData : in-/output struct containing bitstream
91 * - dataQ7 : data vector in Q7
92 * - envQ8 : side info vector defining the width of the pdf
93 * in Q8
94 * - lenData : data vector length
95 *
96 * Return value : 0 if ok,
97 * <0 otherwise.
98 */
WebRtcIsacfix_EncLogisticMulti2(Bitstr_enc * streamData,WebRtc_Word16 * dataQ7,const WebRtc_UWord16 * envQ8,const WebRtc_Word16 lenData)99 int WebRtcIsacfix_EncLogisticMulti2(Bitstr_enc *streamData,
100 WebRtc_Word16 *dataQ7,
101 const WebRtc_UWord16 *envQ8,
102 const WebRtc_Word16 lenData)
103 {
104 WebRtc_UWord32 W_lower;
105 WebRtc_UWord32 W_upper;
106 WebRtc_UWord16 W_upper_LSB;
107 WebRtc_UWord16 W_upper_MSB;
108 WebRtc_UWord16 *streamPtr;
109 WebRtc_UWord16 *maxStreamPtr;
110 WebRtc_UWord16 *streamPtrCarry;
111 WebRtc_UWord16 negcarry;
112 WebRtc_UWord32 cdfLo;
113 WebRtc_UWord32 cdfHi;
114 int k;
115
116 /* point to beginning of stream buffer
117 * and set maximum streamPtr value */
118 streamPtr = streamData->stream + streamData->stream_index;
119 maxStreamPtr = streamData->stream + STREAM_MAXW16_60MS - 1;
120 W_upper = streamData->W_upper;
121
122 for (k = 0; k < lenData; k++)
123 {
124 /* compute cdf_lower and cdf_upper by evaluating the
125 * WebRtcIsacfix_Piecewise linear cdf */
126 cdfLo = WebRtcIsacfix_Piecewise(WEBRTC_SPL_MUL_16_U16(*dataQ7 - 64, *envQ8));
127 cdfHi = WebRtcIsacfix_Piecewise(WEBRTC_SPL_MUL_16_U16(*dataQ7 + 64, *envQ8));
128
129 /* test and clip if probability gets too small */
130 while ((cdfLo + 1) >= cdfHi) {
131 /* clip */
132 if (*dataQ7 > 0) {
133 *dataQ7 -= 128;
134 cdfHi = cdfLo;
135 cdfLo = WebRtcIsacfix_Piecewise(
136 WEBRTC_SPL_MUL_16_U16(*dataQ7 - 64, *envQ8));
137 } else {
138 *dataQ7 += 128;
139 cdfLo = cdfHi;
140 cdfHi = WebRtcIsacfix_Piecewise(
141 WEBRTC_SPL_MUL_16_U16(*dataQ7 + 64, *envQ8));
142 }
143 }
144
145 dataQ7++;
146 /* increment only once per 4 iterations */
147 envQ8 += (k & 1) & (k >> 1);
148
149
150 /* update interval */
151 W_upper_LSB = (WebRtc_UWord16)W_upper;
152 W_upper_MSB = (WebRtc_UWord16)WEBRTC_SPL_RSHIFT_U32(W_upper, 16);
153 W_lower = WEBRTC_SPL_UMUL_32_16(cdfLo, W_upper_MSB);
154 W_lower += WEBRTC_SPL_UMUL_32_16_RSFT16(cdfLo, W_upper_LSB);
155 W_upper = WEBRTC_SPL_UMUL_32_16(cdfHi, W_upper_MSB);
156 W_upper += WEBRTC_SPL_UMUL_32_16_RSFT16(cdfHi, W_upper_LSB);
157
158 /* shift interval such that it begins at zero */
159 W_upper -= ++W_lower;
160
161 /* add integer to bitstream */
162 streamData->streamval += W_lower;
163
164 /* handle carry */
165 if (streamData->streamval < W_lower)
166 {
167 /* propagate carry */
168 streamPtrCarry = streamPtr;
169 if (streamData->full == 0) {
170 negcarry = *streamPtrCarry;
171 negcarry += 0x0100;
172 *streamPtrCarry = negcarry;
173 while (!(negcarry))
174 {
175 negcarry = *--streamPtrCarry;
176 negcarry++;
177 *streamPtrCarry = negcarry;
178 }
179 } else {
180 while (!(++(*--streamPtrCarry)));
181 }
182 }
183
184 /* renormalize interval, store most significant byte of streamval and update streamval
185 * W_upper < 2^24 */
186 while ( !(W_upper & 0xFF000000) )
187 {
188 W_upper = WEBRTC_SPL_LSHIFT_U32(W_upper, 8);
189 if (streamData->full == 0) {
190 *streamPtr++ += (WebRtc_UWord16) WEBRTC_SPL_RSHIFT_U32(
191 streamData->streamval, 24);
192 streamData->full = 1;
193 } else {
194 *streamPtr = (WebRtc_UWord16) WEBRTC_SPL_LSHIFT_U32(
195 WEBRTC_SPL_RSHIFT_U32(streamData->streamval, 24), 8);
196 streamData->full = 0;
197 }
198
199 if( streamPtr > maxStreamPtr )
200 return -ISAC_DISALLOWED_BITSTREAM_LENGTH;
201
202 streamData->streamval = WEBRTC_SPL_LSHIFT_U32(streamData->streamval, 8);
203 }
204 }
205
206 /* calculate new stream_index */
207 streamData->stream_index = streamPtr - streamData->stream;
208 streamData->W_upper = W_upper;
209
210 return 0;
211 }
212
213
214 /****************************************************************************
215 * WebRtcIsacfix_DecLogisticMulti2(...)
216 *
217 * Arithmetic decoding of spectrum.
218 *
219 * Input:
220 * - streamData : in-/output struct containing bitstream
221 * - envQ8 : side info vector defining the width of the pdf
222 * in Q8
223 * - lenData : data vector length
224 *
225 * Input/Output:
226 * - dataQ7 : input: dither vector, output: data vector
227 *
228 * Return value : number of bytes in the stream so far
229 * -1 if error detected
230 */
WebRtcIsacfix_DecLogisticMulti2(WebRtc_Word16 * dataQ7,Bitstr_dec * streamData,const WebRtc_Word32 * envQ8,const WebRtc_Word16 lenData)231 WebRtc_Word16 WebRtcIsacfix_DecLogisticMulti2(WebRtc_Word16 *dataQ7,
232 Bitstr_dec *streamData,
233 const WebRtc_Word32 *envQ8,
234 const WebRtc_Word16 lenData)
235 {
236 WebRtc_UWord32 W_lower;
237 WebRtc_UWord32 W_upper;
238 WebRtc_UWord32 W_tmp;
239 WebRtc_UWord16 W_upper_LSB;
240 WebRtc_UWord16 W_upper_MSB;
241 WebRtc_UWord32 streamVal;
242 WebRtc_UWord16 cdfTmp;
243 WebRtc_Word32 res;
244 WebRtc_Word32 inSqrt;
245 WebRtc_Word32 newRes;
246 const WebRtc_UWord16 *streamPtr;
247 WebRtc_Word16 candQ7;
248 WebRtc_Word16 envCount;
249 WebRtc_UWord16 tmpARSpecQ8 = 0;
250 int k, i;
251
252
253 /* point to beginning of stream buffer */
254 streamPtr = streamData->stream + streamData->stream_index;
255 W_upper = streamData->W_upper;
256
257 /* Check if it is first time decoder is called for this stream */
258 if (streamData->stream_index == 0)
259 {
260 /* read first word from bytestream */
261 streamVal = WEBRTC_SPL_LSHIFT_U32(*streamPtr++, 16);
262 streamVal |= *streamPtr++;
263
264 } else {
265 streamVal = streamData->streamval;
266 }
267
268
269 res = WEBRTC_SPL_LSHIFT_W32((WebRtc_Word32)1,
270 WEBRTC_SPL_RSHIFT_W16(WebRtcSpl_GetSizeInBits(envQ8[0]), 1));
271 envCount = 0;
272
273 /* code assumes lenData%4 == 0 */
274 for (k = 0; k < lenData; k += 4)
275 {
276 int k4;
277
278 /* convert to magnitude spectrum, by doing square-roots (modified from SPLIB) */
279 inSqrt = envQ8[envCount];
280 i = 10;
281
282 /* For safty reasons */
283 if (inSqrt < 0)
284 inSqrt=-inSqrt;
285
286 newRes = WEBRTC_SPL_RSHIFT_W32(WEBRTC_SPL_DIV(inSqrt, res) + res, 1);
287 do
288 {
289 res = newRes;
290 newRes = WEBRTC_SPL_RSHIFT_W32(WEBRTC_SPL_DIV(inSqrt, res) + res, 1);
291 } while (newRes != res && i-- > 0);
292
293 tmpARSpecQ8 = (WebRtc_UWord16)newRes;
294
295 for(k4 = 0; k4 < 4; k4++)
296 {
297 /* find the integer *data for which streamVal lies in [W_lower+1, W_upper] */
298 W_upper_LSB = (WebRtc_UWord16) (W_upper & 0x0000FFFF);
299 W_upper_MSB = (WebRtc_UWord16) WEBRTC_SPL_RSHIFT_U32(W_upper, 16);
300
301 /* find first candidate by inverting the logistic cdf
302 * Input dither value collected from io-stream */
303 candQ7 = - *dataQ7 + 64;
304 cdfTmp = WebRtcIsacfix_Piecewise(WEBRTC_SPL_MUL_16_U16(candQ7, tmpARSpecQ8));
305
306 W_tmp = WEBRTC_SPL_UMUL_16_16(cdfTmp, W_upper_MSB);
307 W_tmp += WEBRTC_SPL_UMUL_16_16_RSFT16(cdfTmp, W_upper_LSB);
308
309 if (streamVal > W_tmp)
310 {
311 W_lower = W_tmp;
312 candQ7 += 128;
313 cdfTmp = WebRtcIsacfix_Piecewise(WEBRTC_SPL_MUL_16_U16(candQ7, tmpARSpecQ8));
314
315 W_tmp = WEBRTC_SPL_UMUL_16_16(cdfTmp, W_upper_MSB);
316 W_tmp += WEBRTC_SPL_UMUL_16_16_RSFT16(cdfTmp, W_upper_LSB);
317
318 while (streamVal > W_tmp)
319 {
320 W_lower = W_tmp;
321 candQ7 += 128;
322 cdfTmp = WebRtcIsacfix_Piecewise(
323 WEBRTC_SPL_MUL_16_U16(candQ7, tmpARSpecQ8));
324
325 W_tmp = WEBRTC_SPL_UMUL_16_16(cdfTmp, W_upper_MSB);
326 W_tmp += WEBRTC_SPL_UMUL_16_16_RSFT16(cdfTmp, W_upper_LSB);
327
328 /* error check */
329 if (W_lower == W_tmp) {
330 return -1;
331 }
332 }
333 W_upper = W_tmp;
334
335 /* Output value put in dataQ7: another sample decoded */
336 *dataQ7 = candQ7 - 64;
337 }
338 else
339 {
340 W_upper = W_tmp;
341 candQ7 -= 128;
342 cdfTmp = WebRtcIsacfix_Piecewise(WEBRTC_SPL_MUL_16_U16(candQ7, tmpARSpecQ8));
343
344 W_tmp = WEBRTC_SPL_UMUL_16_16(cdfTmp, W_upper_MSB);
345 W_tmp += WEBRTC_SPL_UMUL_16_16_RSFT16(cdfTmp, W_upper_LSB);
346
347 while ( !(streamVal > W_tmp) )
348 {
349 W_upper = W_tmp;
350 candQ7 -= 128;
351 cdfTmp = WebRtcIsacfix_Piecewise(
352 WEBRTC_SPL_MUL_16_U16(candQ7, tmpARSpecQ8));
353
354 W_tmp = WEBRTC_SPL_UMUL_16_16(cdfTmp, W_upper_MSB);
355 W_tmp += WEBRTC_SPL_UMUL_16_16_RSFT16(cdfTmp, W_upper_LSB);
356
357 /* error check */
358 if (W_upper == W_tmp){
359 return -1;
360 }
361 }
362 W_lower = W_tmp;
363
364 /* Output value put in dataQ7: another sample decoded */
365 *dataQ7 = candQ7 + 64;
366 }
367
368 dataQ7++;
369
370 /* shift interval to start at zero */
371 W_upper -= ++W_lower;
372
373 /* add integer to bitstream */
374 streamVal -= W_lower;
375
376 /* renormalize interval and update streamVal
377 * W_upper < 2^24 */
378 while ( !(W_upper & 0xFF000000) )
379 {
380 /* read next byte from stream */
381 if (streamData->full == 0) {
382 streamVal = WEBRTC_SPL_LSHIFT_W32(streamVal, 8) | (*streamPtr++ & 0x00FF);
383 streamData->full = 1;
384 } else {
385 streamVal = WEBRTC_SPL_LSHIFT_W32(streamVal, 8) |
386 WEBRTC_SPL_RSHIFT_U16(*streamPtr, 8);
387 streamData->full = 0;
388 }
389 W_upper = WEBRTC_SPL_LSHIFT_W32(W_upper, 8);
390 }
391 }
392 envCount++;
393 }
394
395 streamData->stream_index = streamPtr - streamData->stream;
396 streamData->W_upper = W_upper;
397 streamData->streamval = streamVal;
398
399 /* find number of bytes in original stream (determined by current interval width) */
400 if ( W_upper > 0x01FFFFFF )
401 return (streamData->stream_index*2 - 3 + !streamData->full);
402 else
403 return (streamData->stream_index*2 - 2 + !streamData->full);
404 }
405