blob: f4a13d60787ac99ee558391ab80981ad329a1f63 [file] [log] [blame]
/*
* 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;
}