src/third_party/webrtc/modules/audio_coding/codecs/isac/fix/source/arith_routines_logist.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_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 }