Line data Source code
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 0 : 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 0 : stream_ptr = streamdata->stream + streamdata->stream_index;
33 0 : W_upper = streamdata->W_upper;
34 :
35 0 : for (k=N; k>0; k--)
36 : {
37 : /* fetch cdf_lower and cdf_upper from cdf tables */
38 0 : cdf_lo = (uint32_t) *(*cdf + *data);
39 0 : cdf_hi = (uint32_t) *(*cdf++ + *data++ + 1);
40 :
41 : /* update interval */
42 0 : W_upper_LSB = W_upper & 0x0000FFFF;
43 0 : W_upper_MSB = W_upper >> 16;
44 0 : W_lower = W_upper_MSB * cdf_lo;
45 0 : W_lower += (W_upper_LSB * cdf_lo) >> 16;
46 0 : W_upper = W_upper_MSB * cdf_hi;
47 0 : W_upper += (W_upper_LSB * cdf_hi) >> 16;
48 :
49 : /* shift interval such that it begins at zero */
50 0 : W_upper -= ++W_lower;
51 :
52 : /* add integer to bitstream */
53 0 : streamdata->streamval += W_lower;
54 :
55 : /* handle carry */
56 0 : if (streamdata->streamval < W_lower)
57 : {
58 : /* propagate carry */
59 0 : stream_ptr_carry = stream_ptr;
60 0 : while (!(++(*--stream_ptr_carry)));
61 : }
62 :
63 : /* renormalize interval, store most significant byte of streamval and update streamval */
64 0 : while ( !(W_upper & 0xFF000000) ) /* W_upper < 2^24 */
65 : {
66 0 : W_upper <<= 8;
67 0 : *stream_ptr++ = (uint8_t) (streamdata->streamval >> 24);
68 0 : streamdata->streamval <<= 8;
69 : }
70 : }
71 :
72 : /* calculate new stream_index */
73 0 : streamdata->stream_index = (int)(stream_ptr - streamdata->stream);
74 0 : streamdata->W_upper = W_upper;
75 :
76 0 : 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 0 : 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 0 : W_lower = 0; //to remove warning -DH
101 0 : stream_ptr = streamdata->stream + streamdata->stream_index;
102 0 : W_upper = streamdata->W_upper;
103 0 : if (W_upper == 0)
104 : /* Should not be possible in normal operation */
105 0 : return -2;
106 :
107 0 : if (streamdata->stream_index == 0) /* first time decoder is called for this stream */
108 : {
109 : /* read first word from bytestream */
110 0 : streamval = *stream_ptr << 24;
111 0 : streamval |= *++stream_ptr << 16;
112 0 : streamval |= *++stream_ptr << 8;
113 0 : streamval |= *++stream_ptr;
114 : } else {
115 0 : streamval = streamdata->streamval;
116 : }
117 :
118 0 : for (k=N; k>0; k--)
119 : {
120 : /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
121 0 : W_upper_LSB = W_upper & 0x0000FFFF;
122 0 : W_upper_MSB = W_upper >> 16;
123 :
124 : /* start halfway the cdf range */
125 0 : size_tmp = *cdf_size++ >> 1;
126 0 : cdf_ptr = *cdf + (size_tmp - 1);
127 :
128 : /* method of bisection */
129 : for ( ;; )
130 : {
131 0 : W_tmp = W_upper_MSB * *cdf_ptr;
132 0 : W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
133 0 : size_tmp >>= 1;
134 0 : if (size_tmp == 0) break;
135 0 : if (streamval > W_tmp)
136 : {
137 0 : W_lower = W_tmp;
138 0 : cdf_ptr += size_tmp;
139 : } else {
140 0 : W_upper = W_tmp;
141 0 : cdf_ptr -= size_tmp;
142 : }
143 : }
144 0 : if (streamval > W_tmp)
145 : {
146 0 : W_lower = W_tmp;
147 0 : *data++ = (int)(cdf_ptr - *cdf++);
148 : } else {
149 0 : W_upper = W_tmp;
150 0 : *data++ = (int)(cdf_ptr - *cdf++ - 1);
151 : }
152 :
153 : /* shift interval to start at zero */
154 0 : W_upper -= ++W_lower;
155 :
156 : /* add integer to bitstream */
157 0 : streamval -= W_lower;
158 :
159 : /* renormalize interval and update streamval */
160 0 : while ( !(W_upper & 0xFF000000) ) /* W_upper < 2^24 */
161 : {
162 : /* read next byte from stream */
163 0 : streamval = (streamval << 8) | *++stream_ptr;
164 0 : W_upper <<= 8;
165 : }
166 :
167 0 : if (W_upper == 0)
168 : /* Should not be possible in normal operation */
169 0 : return -2;
170 :
171 :
172 : }
173 :
174 0 : streamdata->stream_index = (int)(stream_ptr - streamdata->stream);
175 0 : streamdata->W_upper = W_upper;
176 0 : streamdata->streamval = streamval;
177 :
178 :
179 : /* find number of bytes in original stream (determined by current interval width) */
180 0 : if ( W_upper > 0x01FFFFFF )
181 0 : return streamdata->stream_index - 2;
182 : else
183 0 : 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 0 : 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 0 : stream_ptr = streamdata->stream + streamdata->stream_index;
209 0 : W_upper = streamdata->W_upper;
210 0 : if (W_upper == 0)
211 : /* Should not be possible in normal operation */
212 0 : return -2;
213 :
214 0 : if (streamdata->stream_index == 0) /* first time decoder is called for this stream */
215 : {
216 : /* read first word from bytestream */
217 0 : streamval = (uint32_t)(*stream_ptr) << 24;
218 0 : streamval |= (uint32_t)(*++stream_ptr) << 16;
219 0 : streamval |= (uint32_t)(*++stream_ptr) << 8;
220 0 : streamval |= (uint32_t)(*++stream_ptr);
221 : } else {
222 0 : streamval = streamdata->streamval;
223 : }
224 :
225 :
226 0 : for (k=N; k>0; k--)
227 : {
228 : /* find the integer *data for which streamval lies in [W_lower+1, W_upper] */
229 0 : W_upper_LSB = W_upper & 0x0000FFFF;
230 0 : W_upper_MSB = W_upper >> 16;
231 :
232 : /* start at the specified table entry */
233 0 : cdf_ptr = *cdf + (*init_index++);
234 0 : W_tmp = W_upper_MSB * *cdf_ptr;
235 0 : W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
236 0 : if (streamval > W_tmp)
237 : {
238 : for ( ;; )
239 : {
240 0 : W_lower = W_tmp;
241 0 : if (cdf_ptr[0]==65535)
242 : /* range check */
243 0 : return -3;
244 0 : W_tmp = W_upper_MSB * *++cdf_ptr;
245 0 : W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
246 0 : if (streamval <= W_tmp) break;
247 : }
248 0 : W_upper = W_tmp;
249 0 : *data++ = (int)(cdf_ptr - *cdf++ - 1);
250 : } else {
251 : for ( ;; )
252 : {
253 0 : W_upper = W_tmp;
254 0 : --cdf_ptr;
255 0 : if (cdf_ptr<*cdf) {
256 : /* range check */
257 0 : return -3;
258 : }
259 0 : W_tmp = W_upper_MSB * *cdf_ptr;
260 0 : W_tmp += (W_upper_LSB * *cdf_ptr) >> 16;
261 0 : if (streamval > W_tmp) break;
262 : }
263 0 : W_lower = W_tmp;
264 0 : *data++ = (int)(cdf_ptr - *cdf++);
265 : }
266 :
267 : /* shift interval to start at zero */
268 0 : W_upper -= ++W_lower;
269 : /* add integer to bitstream */
270 0 : streamval -= W_lower;
271 :
272 : /* renormalize interval and update streamval */
273 0 : while ( !(W_upper & 0xFF000000) ) /* W_upper < 2^24 */
274 : {
275 : /* read next byte from stream */
276 0 : streamval = (streamval << 8) | *++stream_ptr;
277 0 : W_upper <<= 8;
278 : }
279 : }
280 :
281 0 : streamdata->stream_index = (int)(stream_ptr - streamdata->stream);
282 0 : streamdata->W_upper = W_upper;
283 0 : streamdata->streamval = streamval;
284 :
285 :
286 : /* find number of bytes in original stream (determined by current interval width) */
287 0 : if ( W_upper > 0x01FFFFFF )
288 0 : return streamdata->stream_index - 2;
289 : else
290 0 : return streamdata->stream_index - 1;
291 : }
|
