src/third_party/webrtc/modules/audio_coding/codecs/isac/fix/source/arith_routines_hist.c

   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 = 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)(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 = WEBRTC_SPL_LSHIFT_W32(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  */
 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 = WEBRTC_SPL_LSHIFT_W32((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 = WEBRTC_SPL_LSHIFT_W32(streamval, 8) |
 234             (*streamPtr++ & 0x00FF);
 235         streamData->full = 1;
 236       } else {
 237         streamval = (streamval << 8) | (*streamPtr >> 8);
 238         streamData->full = 0;
 239       }
 240       W_upper = WEBRTC_SPL_LSHIFT_W32(W_upper, 8);
 241     }
 242
 243
 244     /* Error check: should not be possible in normal operation */
 245     if (W_upper == 0) {
 246       return -2;
 247     }
 248
 249   }
 250
 251   streamData->stream_index = streamPtr - streamData->stream;
 252   streamData->W_upper = W_upper;
 253   streamData->streamval = streamval;
 254
 255   if ( W_upper > 0x01FFFFFF ) {
 256     return (streamData->stream_index*2 - 3 + !streamData->full);
 257   } else {
 258     return (streamData->stream_index*2 - 2 + !streamData->full);
 259   }
 260 }
 261
 262
 263 /****************************************************************************
 264  * WebRtcIsacfix_DecHistOneStepMulti(...)
 265  *
 266  * Function to decode more symbols from the arithmetic bytestream, taking
 267  * single step up or down at a time.
 268  * cdf tables can be of arbitrary size, but large tables may take a lot of
 269  * iterations.
 270  *
 271  * Input:
 272  *      - streamData        : in-/output struct containing bitstream
 273  *      - cdf               : array of cdf arrays
 274  *      - initIndex         : vector of initial cdf table search entries
 275  *      - lenData           : data vector length
 276  *
 277  * Output:
 278  *      - data              : data vector
 279  *
 280  * Return value             : number of bytes in original stream
 281  *                            <0 if error detected
 282  */
 283 int16_t WebRtcIsacfix_DecHistOneStepMulti(int16_t *data,
 284                                           Bitstr_dec *streamData,
 285                                           const uint16_t **cdf,
 286                                           const uint16_t *initIndex,
 287                                           const int16_t lenData)
 288 {
 289   uint32_t    W_lower;
 290   uint32_t    W_upper;
 291   uint32_t    W_tmp;
 292   uint32_t    W_upper_LSB;
 293   uint32_t    W_upper_MSB;
 294   uint32_t    streamval;
 295   const uint16_t *streamPtr;
 296   const uint16_t *cdfPtr;
 297   int             k;
 298
 299
 300   streamPtr = streamData->stream + streamData->stream_index;
 301   W_upper = streamData->W_upper;
 302   /* Error check: Should not be possible in normal operation */
 303   if (W_upper == 0) {
 304     return -2;
 305   }
 306
 307   /* Check if it is the first time decoder is called for this stream */
 308   if (streamData->stream_index == 0)
 309   {
 310     /* read first word from bytestream */
 311     streamval = (uint32_t)(*streamPtr++) << 16;
 312     streamval |= *streamPtr++;
 313   } else {
 314     streamval = streamData->streamval;
 315   }
 316
 317   for (k = lenData; k > 0; k--)
 318   {
 319     /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
 320     W_upper_LSB = W_upper & 0x0000FFFF;
 321     W_upper_MSB = WEBRTC_SPL_RSHIFT_U32(W_upper, 16);
 322
 323     /* start at the specified table entry */
 324     cdfPtr = *cdf + (*initIndex++);
 325     W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
 326     W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
 327
 328     if (streamval > W_tmp)
 329     {
 330       for ( ;; )
 331       {
 332         W_lower = W_tmp;
 333
 334         /* range check */
 335         if (cdfPtr[0] == 65535) {
 336           return -3;
 337         }
 338
 339         W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *++cdfPtr);
 340         W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
 341
 342         if (streamval <= W_tmp) {
 343           break;
 344         }
 345       }
 346       W_upper = W_tmp;
 347       *data++ = cdfPtr - *cdf++ - 1;
 348     } else {
 349       for ( ;; )
 350       {
 351         W_upper = W_tmp;
 352         --cdfPtr;
 353
 354         /* range check */
 355         if (cdfPtr < *cdf) {
 356           return -3;
 357         }
 358
 359         W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
 360         W_tmp += (W_upper_LSB * (*cdfPtr)) >> 16;
 361
 362         if (streamval > W_tmp) {
 363           break;
 364         }
 365       }
 366       W_lower = W_tmp;
 367       *data++ = cdfPtr - *cdf++;
 368     }
 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) | (*streamPtr >> 8);
 386         streamData->full = 0;
 387       }
 388       W_upper = WEBRTC_SPL_LSHIFT_W32(W_upper, 8);
 389     }
 390   }
 391
 392   streamData->stream_index = streamPtr - streamData->stream;
 393   streamData->W_upper = W_upper;
 394   streamData->streamval = streamval;
 395
 396   /* find number of bytes in original stream (determined by current interval width) */
 397   if ( W_upper > 0x01FFFFFF ) {
 398     return (streamData->stream_index*2 - 3 + !streamData->full);
 399   } else {
 400     return (streamData->stream_index*2 - 2 + !streamData->full);
 401   }
 402 }