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 */ 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 = WEBRTC_SPL_RSHIFT_W32(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 = WEBRTC_SPL_LSHIFT_W32(W_upper, 8); 105 if (streamData->full == 0) { 106 *streamPtr++ += (uint16_t) WEBRTC_SPL_RSHIFT_W32(streamData->streamval, 24); 107 streamData->full = 1; 108 } else { 109 *streamPtr = (uint16_t) 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 */ 148 int16_t WebRtcIsacfix_DecHistBisectMulti(int16_t *data, 149 Bitstr_dec *streamData, 150 const uint16_t **cdf, 151 const uint16_t *cdfSize, 152 const int16_t lenData) 153 { 154 uint32_t W_lower = 0; 155 uint32_t W_upper; 156 uint32_t W_tmp; 157 uint32_t W_upper_LSB; 158 uint32_t W_upper_MSB; 159 uint32_t streamval; 160 const uint16_t *streamPtr; 161 const uint16_t *cdfPtr; 162 int16_t 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((uint32_t)*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 += (W_upper_LSB * (*cdfPtr)) >> 16; 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 */ 285 int16_t WebRtcIsacfix_DecHistOneStepMulti(int16_t *data, 286 Bitstr_dec *streamData, 287 const uint16_t **cdf, 288 const uint16_t *initIndex, 289 const int16_t lenData) 290 { 291 uint32_t W_lower; 292 uint32_t W_upper; 293 uint32_t W_tmp; 294 uint32_t W_upper_LSB; 295 uint32_t W_upper_MSB; 296 uint32_t streamval; 297 const uint16_t *streamPtr; 298 const uint16_t *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 += (W_upper_LSB * (*cdfPtr)) >> 16; 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 += (W_upper_LSB * (*cdfPtr)) >> 16; 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 += (W_upper_LSB * (*cdfPtr)) >> 16; 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
