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 #include "settings.h" 12 #include "arith_routines.h" 13 14 15 /* 16 * code symbols into arithmetic bytestream 17 */ 18 void WebRtcIsac_EncHistMulti(Bitstr *streamdata, /* in-/output struct containing bitstream */ 19 const int *data, /* input: data vector */ 20 const uint16_t **cdf, /* input: array of cdf arrays */ 21 const int N) /* input: data vector length */ 22 { 23 uint32_t W_lower, W_upper; 24 uint32_t W_upper_LSB, W_upper_MSB; 25 uint8_t *stream_ptr; 26 uint8_t *stream_ptr_carry; 27 uint32_t cdf_lo, cdf_hi; 28 int k; 29 30 31 /* point to beginning of stream buffer */ 32 stream_ptr = streamdata->stream + streamdata->stream_index; 33 W_upper = streamdata->W_upper; 34 35 for (k=N; k>0; k--) 36 { 37 /* fetch cdf_lower and cdf_upper from cdf tables */ 38 cdf_lo = (uint32_t) *(*cdf + *data); 39 cdf_hi = (uint32_t) *(*cdf++ + *data++ + 1); 40 41 /* update interval */ 42 W_upper_LSB = W_upper & 0x0000FFFF; 43 W_upper_MSB = W_upper >> 16; 44 W_lower = W_upper_MSB * cdf_lo; 45 W_lower += (W_upper_LSB * cdf_lo) >> 16; 46 W_upper = W_upper_MSB * cdf_hi; 47 W_upper += (W_upper_LSB * cdf_hi) >> 16; 48 49 /* shift interval such that it begins at zero */ 50 W_upper -= ++W_lower; 51 52 /* add integer to bitstream */ 53 streamdata->streamval += W_lower; 54 55 /* handle carry */ 56 if (streamdata->streamval < W_lower) 57 { 58 /* propagate carry */ 59 stream_ptr_carry = stream_ptr; 60 while (!(++(*--stream_ptr_carry))); 61 } 62 63 /* renormalize interval, store most significant byte of streamval and update streamval */ 64 while ( !(W_upper & 0xFF000000) ) /* W_upper < 2^24 */ 65 { 66 W_upper <<= 8; 67 *stream_ptr++ = (uint8_t) (streamdata->streamval >> 24); 68 streamdata->streamval <<= 8; 69 } 70 } 71 72 /* calculate new stream_index */ 73 streamdata->stream_index = (int)(stream_ptr - streamdata->stream); 74 streamdata->W_upper = W_upper; 75 76 return; 77 } 78 79 80 81 /* 82 * function to decode more symbols from the arithmetic bytestream, using method of bisection 83 * cdf tables should be of size 2^k-1 (which corresponds to an alphabet size of 2^k-2) 84 */ 85 int WebRtcIsac_DecHistBisectMulti(int *data, /* output: data vector */ 86 Bitstr *streamdata, /* in-/output struct containing bitstream */ 87 const uint16_t **cdf, /* input: array of cdf arrays */ 88 const uint16_t *cdf_size, /* input: array of cdf table sizes+1 (power of two: 2^k) */ 89 const int N) /* input: data vector length */ 90 { 91 uint32_t W_lower, W_upper; 92 uint32_t W_tmp; 93 uint32_t W_upper_LSB, W_upper_MSB; 94 uint32_t streamval; 95 const uint8_t *stream_ptr; 96 const uint16_t *cdf_ptr; 97 int size_tmp; 98 int k; 99 100 W_lower = 0; //to remove warning -DH 101 stream_ptr = streamdata->stream + streamdata->stream_index; 102 W_upper = streamdata->W_upper; 103 if (W_upper == 0) 104 /* Should not be possible in normal operation */ 105 return -2; 106 107 if (streamdata->stream_index == 0) /* first time decoder is called for this stream */ 108 { 109 /* read first word from bytestream */ 110 streamval = *stream_ptr << 24; 111 streamval |= *++stream_ptr << 16; 112 streamval |= *++stream_ptr << 8; 113 streamval |= *++stream_ptr; 114 } else { 115 streamval = streamdata->streamval; 116 } 117 118 for (k=N; k>0; k--) 119 { 120 /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */ 121 W_upper_LSB = W_upper & 0x0000FFFF; 122 W_upper_MSB = W_upper >> 16; 123 124 /* start halfway the cdf range */ 125 size_tmp = *cdf_size++ >> 1; 126 cdf_ptr = *cdf + (size_tmp - 1); 127 128 /* method of bisection */ 129 for ( ;; ) 130 { 131 W_tmp = W_upper_MSB * *cdf_ptr; 132 W_tmp += (W_upper_LSB * *cdf_ptr) >> 16; 133 size_tmp >>= 1; 134 if (size_tmp == 0) break; 135 if (streamval > W_tmp) 136 { 137 W_lower = W_tmp; 138 cdf_ptr += size_tmp; 139 } else { 140 W_upper = W_tmp; 141 cdf_ptr -= size_tmp; 142 } 143 } 144 if (streamval > W_tmp) 145 { 146 W_lower = W_tmp; 147 *data++ = (int)(cdf_ptr - *cdf++); 148 } else { 149 W_upper = W_tmp; 150 *data++ = (int)(cdf_ptr - *cdf++ - 1); 151 } 152 153 /* shift interval to start at zero */ 154 W_upper -= ++W_lower; 155 156 /* add integer to bitstream */ 157 streamval -= W_lower; 158 159 /* renormalize interval and update streamval */ 160 while ( !(W_upper & 0xFF000000) ) /* W_upper < 2^24 */ 161 { 162 /* read next byte from stream */ 163 streamval = (streamval << 8) | *++stream_ptr; 164 W_upper <<= 8; 165 } 166 167 if (W_upper == 0) 168 /* Should not be possible in normal operation */ 169 return -2; 170 171 172 } 173 174 streamdata->stream_index = (int)(stream_ptr - streamdata->stream); 175 streamdata->W_upper = W_upper; 176 streamdata->streamval = streamval; 177 178 179 /* find number of bytes in original stream (determined by current interval width) */ 180 if ( W_upper > 0x01FFFFFF ) 181 return streamdata->stream_index - 2; 182 else 183 return streamdata->stream_index - 1; 184 } 185 186 187 188 /* 189 * function to decode more symbols from the arithmetic bytestream, taking single step up or 190 * down at a time 191 * cdf tables can be of arbitrary size, but large tables may take a lot of iterations 192 */ 193 int WebRtcIsac_DecHistOneStepMulti(int *data, /* output: data vector */ 194 Bitstr *streamdata, /* in-/output struct containing bitstream */ 195 const uint16_t **cdf, /* input: array of cdf arrays */ 196 const uint16_t *init_index, /* input: vector of initial cdf table search entries */ 197 const int N) /* input: data vector length */ 198 { 199 uint32_t W_lower, W_upper; 200 uint32_t W_tmp; 201 uint32_t W_upper_LSB, W_upper_MSB; 202 uint32_t streamval; 203 const uint8_t *stream_ptr; 204 const uint16_t *cdf_ptr; 205 int k; 206 207 208 stream_ptr = streamdata->stream + streamdata->stream_index; 209 W_upper = streamdata->W_upper; 210 if (W_upper == 0) 211 /* Should not be possible in normal operation */ 212 return -2; 213 214 if (streamdata->stream_index == 0) /* first time decoder is called for this stream */ 215 { 216 /* read first word from bytestream */ 217 streamval = *stream_ptr << 24; 218 streamval |= *++stream_ptr << 16; 219 streamval |= *++stream_ptr << 8; 220 streamval |= *++stream_ptr; 221 } else { 222 streamval = streamdata->streamval; 223 } 224 225 226 for (k=N; k>0; k--) 227 { 228 /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */ 229 W_upper_LSB = W_upper & 0x0000FFFF; 230 W_upper_MSB = W_upper >> 16; 231 232 /* start at the specified table entry */ 233 cdf_ptr = *cdf + (*init_index++); 234 W_tmp = W_upper_MSB * *cdf_ptr; 235 W_tmp += (W_upper_LSB * *cdf_ptr) >> 16; 236 if (streamval > W_tmp) 237 { 238 for ( ;; ) 239 { 240 W_lower = W_tmp; 241 if (cdf_ptr[0]==65535) 242 /* range check */ 243 return -3; 244 W_tmp = W_upper_MSB * *++cdf_ptr; 245 W_tmp += (W_upper_LSB * *cdf_ptr) >> 16; 246 if (streamval <= W_tmp) break; 247 } 248 W_upper = W_tmp; 249 *data++ = (int)(cdf_ptr - *cdf++ - 1); 250 } else { 251 for ( ;; ) 252 { 253 W_upper = W_tmp; 254 --cdf_ptr; 255 if (cdf_ptr<*cdf) { 256 /* range check */ 257 return -3; 258 } 259 W_tmp = W_upper_MSB * *cdf_ptr; 260 W_tmp += (W_upper_LSB * *cdf_ptr) >> 16; 261 if (streamval > W_tmp) break; 262 } 263 W_lower = W_tmp; 264 *data++ = (int)(cdf_ptr - *cdf++); 265 } 266 267 /* shift interval to start at zero */ 268 W_upper -= ++W_lower; 269 /* add integer to bitstream */ 270 streamval -= W_lower; 271 272 /* renormalize interval and update streamval */ 273 while ( !(W_upper & 0xFF000000) ) /* W_upper < 2^24 */ 274 { 275 /* read next byte from stream */ 276 streamval = (streamval << 8) | *++stream_ptr; 277 W_upper <<= 8; 278 } 279 } 280 281 streamdata->stream_index = (int)(stream_ptr - streamdata->stream); 282 streamdata->W_upper = W_upper; 283 streamdata->streamval = streamval; 284 285 286 /* find number of bytes in original stream (determined by current interval width) */ 287 if ( W_upper > 0x01FFFFFF ) 288 return streamdata->stream_index - 2; 289 else 290 return streamdata->stream_index - 1; 291 } 292
