/*
 *  Copyright (c) 2011 The WebRTC project authors. All Rights Reserved.
 *
 *  Use of this source code is governed by a BSD-style license
 *  that can be found in the LICENSE file in the root of the source
 *  tree. An additional intellectual property rights grant can be found
 *  in the file PATENTS.  All contributing project authors may
 *  be found in the AUTHORS file in the root of the source tree.
 */

/*
 * arith_routinshist.c
 *
 * This C file contains arithmetic encoding and decoding.
 *
 */

#include "arith_routins.h"


/****************************************************************************
 * WebRtcIsacfix_EncHistMulti(...)
 *
 * Encode the histogram interval
 *
 * Input:
 *      - streamData        : in-/output struct containing bitstream
 *      - data              : data vector
 *      - cdf               : array of cdf arrays
 *      - lenData           : data vector length
 *
 * Return value             : 0 if ok
 *                            <0 if error detected
 */
int WebRtcIsacfix_EncHistMulti(Bitstr_enc *streamData,
                              const WebRtc_Word16 *data,
                              const WebRtc_UWord16 **cdf,
                              const WebRtc_Word16 lenData)
{
  WebRtc_UWord32 W_lower;
  WebRtc_UWord32 W_upper;
  WebRtc_UWord32 W_upper_LSB;
  WebRtc_UWord32 W_upper_MSB;
  WebRtc_UWord16 *streamPtr;
  WebRtc_UWord16 negCarry;
  WebRtc_UWord16 *maxStreamPtr;
  WebRtc_UWord16 *streamPtrCarry;
  WebRtc_UWord32 cdfLo;
  WebRtc_UWord32 cdfHi;
  int k;


  /* point to beginning of stream buffer
   * and set maximum streamPtr value */
  streamPtr = streamData->stream + streamData->stream_index;
  maxStreamPtr = streamData->stream + STREAM_MAXW16_60MS - 1;

  W_upper = streamData->W_upper;

  for (k = lenData; k > 0; k--)
  {
    /* fetch cdf_lower and cdf_upper from cdf tables */
    cdfLo = (WebRtc_UWord32) *(*cdf + (WebRtc_UWord32)*data);
    cdfHi = (WebRtc_UWord32) *(*cdf++ + (WebRtc_UWord32)*data++ + 1);

    /* update interval */
    W_upper_LSB = W_upper & 0x0000FFFF;
    W_upper_MSB = WEBRTC_SPL_RSHIFT_W32(W_upper, 16);
    W_lower = WEBRTC_SPL_UMUL(W_upper_MSB, cdfLo);
    W_lower += WEBRTC_SPL_UMUL_RSFT16(W_upper_LSB, cdfLo);
    W_upper = WEBRTC_SPL_UMUL(W_upper_MSB, cdfHi);
    W_upper += WEBRTC_SPL_UMUL_RSFT16(W_upper_LSB, cdfHi);

    /* shift interval such that it begins at zero */
    W_upper -= ++W_lower;

    /* add integer to bitstream */
    streamData->streamval += W_lower;

    /* handle carry */
    if (streamData->streamval < W_lower)
    {
      /* propagate carry */
      streamPtrCarry = streamPtr;
      if (streamData->full == 0) {
        negCarry = *streamPtrCarry;
        negCarry += 0x0100;
        *streamPtrCarry = negCarry;
        while (!(negCarry))
        {
          negCarry = *--streamPtrCarry;
          negCarry++;
          *streamPtrCarry = negCarry;
        }
      } else {
        while ( !(++(*--streamPtrCarry)) );
      }
    }

    /* renormalize interval, store most significant byte of streamval and update streamval
     * W_upper < 2^24 */
    while ( !(W_upper & 0xFF000000) )
    {
      W_upper = WEBRTC_SPL_LSHIFT_W32(W_upper, 8);
      if (streamData->full == 0) {
        *streamPtr++ += (WebRtc_UWord16) WEBRTC_SPL_RSHIFT_W32(streamData->streamval, 24);
        streamData->full = 1;
      } else {
        *streamPtr = (WebRtc_UWord16) WEBRTC_SPL_LSHIFT_W32(
            WEBRTC_SPL_RSHIFT_W32(streamData->streamval, 24), 8);
        streamData->full = 0;
      }

      if( streamPtr > maxStreamPtr ) {
        return -ISAC_DISALLOWED_BITSTREAM_LENGTH;
      }
      streamData->streamval = WEBRTC_SPL_LSHIFT_W32(streamData->streamval, 8);
    }
  }

  /* calculate new stream_index */
  streamData->stream_index = streamPtr - streamData->stream;
  streamData->W_upper = W_upper;

  return 0;
}


/****************************************************************************
 * WebRtcIsacfix_DecHistBisectMulti(...)
 *
 * Function to decode more symbols from the arithmetic bytestream, using
 * method of bisection cdf tables should be of size 2^k-1 (which corresponds
 * to an alphabet size of 2^k-2)
 *
 * Input:
 *      - streamData        : in-/output struct containing bitstream
 *      - cdf               : array of cdf arrays
 *      - cdfSize           : array of cdf table sizes+1 (power of two: 2^k)
 *      - lenData           : data vector length
 *
 * Output:
 *      - data              : data vector
 *
 * Return value             : number of bytes in the stream
 *                            <0 if error detected
 */
WebRtc_Word16 WebRtcIsacfix_DecHistBisectMulti(WebRtc_Word16 *data,
                                              Bitstr_dec *streamData,
                                              const WebRtc_UWord16 **cdf,
                                              const WebRtc_UWord16 *cdfSize,
                                              const WebRtc_Word16 lenData)
{
  WebRtc_UWord32    W_lower = 0;
  WebRtc_UWord32    W_upper;
  WebRtc_UWord32    W_tmp;
  WebRtc_UWord32    W_upper_LSB;
  WebRtc_UWord32    W_upper_MSB;
  WebRtc_UWord32    streamval;
  const WebRtc_UWord16 *streamPtr;
  const WebRtc_UWord16 *cdfPtr;
  WebRtc_Word16     sizeTmp;
  int             k;


  streamPtr = streamData->stream + streamData->stream_index;
  W_upper = streamData->W_upper;

  /* Error check: should not be possible in normal operation */
  if (W_upper == 0) {
    return -2;
  }

  /* first time decoder is called for this stream */
  if (streamData->stream_index == 0)
  {
    /* read first word from bytestream */
    streamval = WEBRTC_SPL_LSHIFT_W32((WebRtc_UWord32)*streamPtr++, 16);
    streamval |= *streamPtr++;
  } else {
    streamval = streamData->streamval;
  }

  for (k = lenData; k > 0; k--)
  {
    /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
    W_upper_LSB = W_upper & 0x0000FFFF;
    W_upper_MSB = WEBRTC_SPL_RSHIFT_W32(W_upper, 16);

    /* start halfway the cdf range */
    sizeTmp = WEBRTC_SPL_RSHIFT_W16(*cdfSize++, 1);
    cdfPtr = *cdf + (sizeTmp - 1);

    /* method of bisection */
    for ( ;; )
    {
      W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
      W_tmp += WEBRTC_SPL_UMUL_32_16_RSFT16(W_upper_LSB, *cdfPtr);
      sizeTmp = WEBRTC_SPL_RSHIFT_W16(sizeTmp, 1);
      if (sizeTmp == 0) {
        break;
      }

      if (streamval > W_tmp)
      {
        W_lower = W_tmp;
        cdfPtr += sizeTmp;
      } else {
        W_upper = W_tmp;
        cdfPtr -= sizeTmp;
      }
    }
    if (streamval > W_tmp)
    {
      W_lower = W_tmp;
      *data++ = cdfPtr - *cdf++;
    } else {
      W_upper = W_tmp;
      *data++ = cdfPtr - *cdf++ - 1;
    }

    /* shift interval to start at zero */
    W_upper -= ++W_lower;

    /* add integer to bitstream */
    streamval -= W_lower;

    /* renormalize interval and update streamval */
    /* W_upper < 2^24 */
    while ( !(W_upper & 0xFF000000) )
    {
      /* read next byte from stream */
      if (streamData->full == 0) {
        streamval = WEBRTC_SPL_LSHIFT_W32(streamval, 8) |
            (*streamPtr++ & 0x00FF);
        streamData->full = 1;
      } else {
        streamval = WEBRTC_SPL_LSHIFT_W32(streamval, 8) |
            WEBRTC_SPL_RSHIFT_W16(*streamPtr, 8);
        streamData->full = 0;
      }
      W_upper = WEBRTC_SPL_LSHIFT_W32(W_upper, 8);
    }


    /* Error check: should not be possible in normal operation */
    if (W_upper == 0) {
      return -2;
    }

  }

  streamData->stream_index = streamPtr - streamData->stream;
  streamData->W_upper = W_upper;
  streamData->streamval = streamval;

  if ( W_upper > 0x01FFFFFF ) {
    return (streamData->stream_index*2 - 3 + !streamData->full);
  } else {
    return (streamData->stream_index*2 - 2 + !streamData->full);
  }
}


/****************************************************************************
 * WebRtcIsacfix_DecHistOneStepMulti(...)
 *
 * Function to decode more symbols from the arithmetic bytestream, taking
 * single step up or down at a time.
 * cdf tables can be of arbitrary size, but large tables may take a lot of
 * iterations.
 *
 * Input:
 *      - streamData        : in-/output struct containing bitstream
 *      - cdf               : array of cdf arrays
 *      - initIndex         : vector of initial cdf table search entries
 *      - lenData           : data vector length
 *
 * Output:
 *      - data              : data vector
 *
 * Return value             : number of bytes in original stream
 *                            <0 if error detected
 */
WebRtc_Word16 WebRtcIsacfix_DecHistOneStepMulti(WebRtc_Word16 *data,
                                               Bitstr_dec *streamData,
                                               const WebRtc_UWord16 **cdf,
                                               const WebRtc_UWord16 *initIndex,
                                               const WebRtc_Word16 lenData)
{
  WebRtc_UWord32    W_lower;
  WebRtc_UWord32    W_upper;
  WebRtc_UWord32    W_tmp;
  WebRtc_UWord32    W_upper_LSB;
  WebRtc_UWord32    W_upper_MSB;
  WebRtc_UWord32    streamval;
  const WebRtc_UWord16 *streamPtr;
  const WebRtc_UWord16 *cdfPtr;
  int             k;


  streamPtr = streamData->stream + streamData->stream_index;
  W_upper = streamData->W_upper;
  /* Error check: Should not be possible in normal operation */
  if (W_upper == 0) {
    return -2;
  }

  /* Check if it is the first time decoder is called for this stream */
  if (streamData->stream_index == 0)
  {
    /* read first word from bytestream */
    streamval = WEBRTC_SPL_LSHIFT_U32(*streamPtr++, 16);
    streamval |= *streamPtr++;
  } else {
    streamval = streamData->streamval;
  }

  for (k = lenData; k > 0; k--)
  {
    /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
    W_upper_LSB = W_upper & 0x0000FFFF;
    W_upper_MSB = WEBRTC_SPL_RSHIFT_U32(W_upper, 16);

    /* start at the specified table entry */
    cdfPtr = *cdf + (*initIndex++);
    W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
    W_tmp += WEBRTC_SPL_UMUL_32_16_RSFT16(W_upper_LSB, *cdfPtr);

    if (streamval > W_tmp)
    {
      for ( ;; )
      {
        W_lower = W_tmp;

        /* range check */
        if (cdfPtr[0] == 65535) {
          return -3;
        }

        W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *++cdfPtr);
        W_tmp += WEBRTC_SPL_UMUL_32_16_RSFT16(W_upper_LSB, *cdfPtr);

        if (streamval <= W_tmp) {
          break;
        }
      }
      W_upper = W_tmp;
      *data++ = cdfPtr - *cdf++ - 1;
    } else {
      for ( ;; )
      {
        W_upper = W_tmp;
        --cdfPtr;

        /* range check */
        if (cdfPtr < *cdf) {
          return -3;
        }

        W_tmp = WEBRTC_SPL_UMUL_32_16(W_upper_MSB, *cdfPtr);
        W_tmp += WEBRTC_SPL_UMUL_32_16_RSFT16(W_upper_LSB, *cdfPtr);

        if (streamval > W_tmp) {
          break;
        }
      }
      W_lower = W_tmp;
      *data++ = cdfPtr - *cdf++;
    }

    /* shift interval to start at zero */
    W_upper -= ++W_lower;

    /* add integer to bitstream */
    streamval -= W_lower;

    /* renormalize interval and update streamval */
    /* W_upper < 2^24 */
    while ( !(W_upper & 0xFF000000) )
    {
      /* read next byte from stream */
      if (streamData->full == 0) {
        streamval = WEBRTC_SPL_LSHIFT_W32(streamval, 8) | (*streamPtr++ & 0x00FF);
        streamData->full = 1;
      } else {
        streamval = WEBRTC_SPL_LSHIFT_W32(streamval, 8) | (*streamPtr >> 8);
        streamData->full = 0;
      }
      W_upper = WEBRTC_SPL_LSHIFT_W32(W_upper, 8);
    }
  }

  streamData->stream_index = streamPtr - streamData->stream;
  streamData->W_upper = W_upper;
  streamData->streamval = streamval;

  /* find number of bytes in original stream (determined by current interval width) */
  if ( W_upper > 0x01FFFFFF ) {
    return (streamData->stream_index*2 - 3 + !streamData->full);
  } else {
    return (streamData->stream_index*2 - 2 + !streamData->full);
  }
}