/* * 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 uint16_t **cdf, /* input: array of cdf arrays */ const int N) /* input: data vector length */ { uint32_t W_lower, W_upper; uint32_t W_upper_LSB, W_upper_MSB; uint8_t *stream_ptr; uint8_t *stream_ptr_carry; uint32_t 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 = (uint32_t) *(*cdf + *data); cdf_hi = (uint32_t) *(*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++ = (uint8_t) (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 uint16_t **cdf, /* input: array of cdf arrays */ const uint16_t *cdf_size, /* input: array of cdf table sizes+1 (power of two: 2^k) */ const int N) /* input: data vector length */ { uint32_t W_lower, W_upper; uint32_t W_tmp; uint32_t W_upper_LSB, W_upper_MSB; uint32_t streamval; const uint8_t *stream_ptr; const uint16_t *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 uint16_t **cdf, /* input: array of cdf arrays */ const uint16_t *init_index, /* input: vector of initial cdf table search entries */ const int N) /* input: data vector length */ { uint32_t W_lower, W_upper; uint32_t W_tmp; uint32_t W_upper_LSB, W_upper_MSB; uint32_t streamval; const uint8_t *stream_ptr; const uint16_t *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; }