/*
 *  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.
 */

#include "settings.h"
#include "arith_routines.h"


/*
 * code symbols into arithmetic bytestream
 */
void WebRtcIsac_EncHistMulti(Bitstr *streamdata, /* in-/output struct containing bitstream */
                             const int *data,  /* input: data vector */
                             const WebRtc_UWord16 **cdf, /* input: array of cdf arrays */
                             const int N)   /* input: data vector length */
{
  WebRtc_UWord32 W_lower, W_upper;
  WebRtc_UWord32 W_upper_LSB, W_upper_MSB;
  WebRtc_UWord8 *stream_ptr;
  WebRtc_UWord8 *stream_ptr_carry;
  WebRtc_UWord32 cdf_lo, cdf_hi;
  int k;


  /* point to beginning of stream buffer */
  stream_ptr = streamdata->stream + streamdata->stream_index;
  W_upper = streamdata->W_upper;

  for (k=N; k>0; k--)
  {
    /* fetch cdf_lower and cdf_upper from cdf tables */
    cdf_lo = (WebRtc_UWord32) *(*cdf + *data);
    cdf_hi = (WebRtc_UWord32) *(*cdf++ + *data++ + 1);

    /* update interval */
    W_upper_LSB = W_upper & 0x0000FFFF;
    W_upper_MSB = W_upper >> 16;
    W_lower = W_upper_MSB * cdf_lo;
    W_lower += (W_upper_LSB * cdf_lo) >> 16;
    W_upper = W_upper_MSB * cdf_hi;
    W_upper += (W_upper_LSB * cdf_hi) >> 16;

    /* 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 */
      stream_ptr_carry = stream_ptr;
      while (!(++(*--stream_ptr_carry)));
    }

    /* renormalize interval, store most significant byte of streamval and update streamval */
    while ( !(W_upper & 0xFF000000) )      /* W_upper < 2^24 */
    {
      W_upper <<= 8;
      *stream_ptr++ = (WebRtc_UWord8) (streamdata->streamval >> 24);
      streamdata->streamval <<= 8;
    }
  }

  /* calculate new stream_index */
  streamdata->stream_index = (int)(stream_ptr - streamdata->stream);
  streamdata->W_upper = W_upper;

  return;
}


/*
 * 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)
 */
int WebRtcIsac_DecHistBisectMulti(int *data,     /* output: data vector */
                                  Bitstr *streamdata,   /* in-/output struct containing bitstream */
                                  const WebRtc_UWord16 **cdf,  /* input: array of cdf arrays */
                                  const WebRtc_UWord16 *cdf_size, /* input: array of cdf table sizes+1 (power of two: 2^k) */
                                  const int N)    /* input: data vector length */
{
  WebRtc_UWord32    W_lower, W_upper;
  WebRtc_UWord32    W_tmp;
  WebRtc_UWord32    W_upper_LSB, W_upper_MSB;
  WebRtc_UWord32    streamval;
  const   WebRtc_UWord8 *stream_ptr;
  const   WebRtc_UWord16 *cdf_ptr;
  int     size_tmp;
  int     k;

  W_lower = 0; //to remove warning -DH
  stream_ptr = streamdata->stream + streamdata->stream_index;
  W_upper = streamdata->W_upper;
  if (W_upper == 0)
    /* Should not be possible in normal operation */
    return -2;

  if (streamdata->stream_index == 0)   /* first time decoder is called for this stream */
  {
    /* read first word from bytestream */
    streamval = *stream_ptr << 24;
    streamval |= *++stream_ptr << 16;
    streamval |= *++stream_ptr << 8;
    streamval |= *++stream_ptr;
  } else {
    streamval = streamdata->streamval;
  }

  for (k=N; 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 = W_upper >> 16;

    /* start halfway the cdf range */
    size_tmp = *cdf_size++ >> 1;
    cdf_ptr = *cdf + (size_tmp - 1);

    /* method of bisection */
    for ( ;; )
    {
      W_tmp = W_upper_MSB * *cdf_ptr;
      W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
      size_tmp >>= 1;
      if (size_tmp == 0) break;
      if (streamval > W_tmp)
      {
        W_lower = W_tmp;
        cdf_ptr += size_tmp;
      } else {
        W_upper = W_tmp;
        cdf_ptr -= size_tmp;
      }
    }
    if (streamval > W_tmp)
    {
      W_lower = W_tmp;
      *data++ = (int)(cdf_ptr - *cdf++);
    } else {
      W_upper = W_tmp;
      *data++ = (int)(cdf_ptr - *cdf++ - 1);
    }

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

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

    /* renormalize interval and update streamval */
    while ( !(W_upper & 0xFF000000) )    /* W_upper < 2^24 */
    {
      /* read next byte from stream */
      streamval = (streamval << 8) | *++stream_ptr;
      W_upper <<= 8;
    }

    if (W_upper == 0)
      /* Should not be possible in normal operation */
      return -2;


  }

  streamdata->stream_index = (int)(stream_ptr - 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;
  else
    return streamdata->stream_index - 1;
}


/*
 * 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
 */
int WebRtcIsac_DecHistOneStepMulti(int *data,        /* output: data vector */
                                   Bitstr *streamdata,      /* in-/output struct containing bitstream */
                                   const WebRtc_UWord16 **cdf,   /* input: array of cdf arrays */
                                   const WebRtc_UWord16 *init_index, /* input: vector of initial cdf table search entries */
                                   const int N)     /* input: data vector length */
{
  WebRtc_UWord32    W_lower, W_upper;
  WebRtc_UWord32    W_tmp;
  WebRtc_UWord32    W_upper_LSB, W_upper_MSB;
  WebRtc_UWord32    streamval;
  const   WebRtc_UWord8 *stream_ptr;
  const   WebRtc_UWord16 *cdf_ptr;
  int     k;


  stream_ptr = streamdata->stream + streamdata->stream_index;
  W_upper = streamdata->W_upper;
  if (W_upper == 0)
    /* Should not be possible in normal operation */
    return -2;

  if (streamdata->stream_index == 0)   /* first time decoder is called for this stream */
  {
    /* read first word from bytestream */
    streamval = *stream_ptr << 24;
    streamval |= *++stream_ptr << 16;
    streamval |= *++stream_ptr << 8;
    streamval |= *++stream_ptr;
  } else {
    streamval = streamdata->streamval;
  }


  for (k=N; 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 = W_upper >> 16;

    /* start at the specified table entry */
    cdf_ptr = *cdf + (*init_index++);
    W_tmp = W_upper_MSB * *cdf_ptr;
    W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
    if (streamval > W_tmp)
    {
      for ( ;; )
      {
        W_lower = W_tmp;
        if (cdf_ptr[0]==65535)
          /* range check */
          return -3;
        W_tmp = W_upper_MSB * *++cdf_ptr;
        W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
        if (streamval <= W_tmp) break;
      }
      W_upper = W_tmp;
      *data++ = (int)(cdf_ptr - *cdf++ - 1);
    } else {
      for ( ;; )
      {
        W_upper = W_tmp;
        --cdf_ptr;
        if (cdf_ptr<*cdf) {
          /* range check */
          return -3;
        }
        W_tmp = W_upper_MSB * *cdf_ptr;
        W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
        if (streamval > W_tmp) break;
      }
      W_lower = W_tmp;
      *data++ = (int)(cdf_ptr - *cdf++);
    }

    /* shift interval to start at zero */
    W_upper -= ++W_lower;
    /* add integer to bitstream */
    streamval -= W_lower;

    /* renormalize interval and update streamval */
    while ( !(W_upper & 0xFF000000) )    /* W_upper < 2^24 */
    {
      /* read next byte from stream */
      streamval = (streamval << 8) | *++stream_ptr;
      W_upper <<= 8;
    }
  }

  streamdata->stream_index = (int)(stream_ptr - 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;
  else
    return streamdata->stream_index - 1;
}