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