Initial Skype commit taken from FreeSwitch, which got it from the IETF draft.
[opus.git] / src / SKP_Silk_range_coder.c
1 /***********************************************************************\r
2 Copyright (c) 2006-2010, Skype Limited. All rights reserved. \r
3 Redistribution and use in source and binary forms, with or without \r
4 modification, (subject to the limitations in the disclaimer below) \r
5 are permitted provided that the following conditions are met:\r
6 - Redistributions of source code must retain the above copyright notice,\r
7 this list of conditions and the following disclaimer.\r
8 - Redistributions in binary form must reproduce the above copyright \r
9 notice, this list of conditions and the following disclaimer in the \r
10 documentation and/or other materials provided with the distribution.\r
11 - Neither the name of Skype Limited, nor the names of specific \r
12 contributors, may be used to endorse or promote products derived from \r
13 this software without specific prior written permission.\r
14 NO EXPRESS OR IMPLIED LICENSES TO ANY PARTY'S PATENT RIGHTS ARE GRANTED \r
15 BY THIS LICENSE. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND \r
16 CONTRIBUTORS ''AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,\r
17 BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND \r
18 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE \r
19 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, \r
20 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\r
21 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF \r
22 USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON \r
23 ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT \r
24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE \r
25 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\r
26 ***********************************************************************/\r
27 \r
28 #include "SKP_Silk_main.h"\r
29 \r
30 /* Range encoder for one symbol */\r
31 void SKP_Silk_range_encoder(\r
32     SKP_Silk_range_coder_state      *psRC,              /* I/O  compressor data structure                   */\r
33     const SKP_int                   data,               /* I    uncompressed data                           */\r
34     const SKP_uint16                prob[]              /* I    cumulative density functions                */\r
35 )\r
36 {\r
37     SKP_uint32 low_Q16, high_Q16;\r
38     SKP_uint32 base_tmp, range_Q32;\r
39 \r
40     /* Copy structure data */\r
41     SKP_uint32 base_Q32  = psRC->base_Q32;\r
42     SKP_uint32 range_Q16 = psRC->range_Q16;\r
43     SKP_int32  bufferIx  = psRC->bufferIx;\r
44     SKP_uint8  *buffer   = psRC->buffer;\r
45 \r
46     if( psRC->error ) {\r
47         return;\r
48     }\r
49 \r
50     /* Update interval */\r
51     low_Q16  = prob[ data ];\r
52     high_Q16 = prob[ data + 1 ];\r
53     base_tmp = base_Q32; /* save current base, to test for carry */\r
54     base_Q32 += SKP_MUL_uint( range_Q16, low_Q16 );\r
55     range_Q32 = SKP_MUL_uint( range_Q16, high_Q16 - low_Q16 );\r
56 \r
57     /* Check for carry */\r
58     if( base_Q32 < base_tmp ) {\r
59         /* Propagate carry in buffer */\r
60         SKP_int bufferIx_tmp = bufferIx;\r
61         while( ( ++buffer[ --bufferIx_tmp ] ) == 0 );\r
62     }\r
63 \r
64     /* Check normalization */\r
65     if( range_Q32 & 0xFF000000 ) {\r
66         /* No normalization */\r
67         range_Q16 = SKP_RSHIFT_uint( range_Q32, 16 );\r
68     } else {\r
69         if( range_Q32 & 0xFFFF0000 ) {\r
70             /* Normalization of 8 bits shift */\r
71             range_Q16 = SKP_RSHIFT_uint( range_Q32, 8 );\r
72         } else {\r
73             /* Normalization of 16 bits shift */\r
74             range_Q16 = range_Q32;\r
75             /* Make sure not to write beyond buffer */\r
76             if( bufferIx >= psRC->bufferLength ) {\r
77                 psRC->error = RANGE_CODER_WRITE_BEYOND_BUFFER;\r
78                 return;\r
79             }\r
80             /* Write one byte to buffer */\r
81             buffer[ bufferIx++ ] = (SKP_uint8)( SKP_RSHIFT_uint( base_Q32, 24 ) );\r
82             base_Q32 = SKP_LSHIFT_ovflw( base_Q32, 8 );\r
83         }\r
84         /* Make sure not to write beyond buffer */\r
85         if( bufferIx >= psRC->bufferLength ) {\r
86             psRC->error = RANGE_CODER_WRITE_BEYOND_BUFFER;\r
87             return;\r
88         }\r
89         /* Write one byte to buffer */\r
90         buffer[ bufferIx++ ] = (SKP_uint8)( SKP_RSHIFT_uint( base_Q32, 24 ) );\r
91         base_Q32 = SKP_LSHIFT_ovflw( base_Q32, 8 );\r
92     }\r
93 \r
94     /* Copy structure data back */\r
95     psRC->base_Q32  = base_Q32;\r
96     psRC->range_Q16 = range_Q16;\r
97     psRC->bufferIx  = bufferIx;\r
98 }\r
99 \r
100 /* Range encoder for multiple symbols */\r
101 void SKP_Silk_range_encoder_multi(\r
102     SKP_Silk_range_coder_state      *psRC,              /* I/O  compressor data structure                   */\r
103     const SKP_int                   data[],             /* I    uncompressed data    [nSymbols]             */\r
104     const SKP_uint16 * const        prob[],             /* I    cumulative density functions                */\r
105     const SKP_int                   nSymbols            /* I    number of data symbols                      */\r
106 )\r
107 {\r
108     SKP_int k;\r
109     for( k = 0; k < nSymbols; k++ ) {\r
110         SKP_Silk_range_encoder( psRC, data[ k ], prob[ k ] );\r
111     }\r
112 }\r
113 \r
114 /* Range decoder for one symbol */\r
115 void SKP_Silk_range_decoder(\r
116     SKP_int                         data[],             /* O    uncompressed data                           */\r
117     SKP_Silk_range_coder_state      *psRC,              /* I/O  compressor data structure                   */\r
118     const SKP_uint16                prob[],             /* I    cumulative density function                 */\r
119     SKP_int                         probIx              /* I    initial (middle) entry of cdf               */\r
120 )\r
121 {\r
122     SKP_uint32 low_Q16, high_Q16;\r
123     SKP_uint32 base_tmp, range_Q32;\r
124 \r
125     /* Copy structure data */\r
126     SKP_uint32 base_Q32  = psRC->base_Q32;\r
127     SKP_uint32 range_Q16 = psRC->range_Q16;\r
128     SKP_int32  bufferIx  = psRC->bufferIx;\r
129     SKP_uint8  *buffer   = &psRC->buffer[ 4 ];\r
130 \r
131     if( psRC->error ) {\r
132         /* Set output to zero */\r
133         *data = 0;\r
134         return;\r
135     }\r
136 \r
137     high_Q16 = prob[ probIx ];\r
138     base_tmp = SKP_MUL_uint( range_Q16, high_Q16 );\r
139     if( base_tmp > base_Q32 ) {\r
140         while( 1 ) {\r
141             low_Q16 = prob[ --probIx ];\r
142             base_tmp = SKP_MUL_uint( range_Q16, low_Q16 );\r
143             if( base_tmp <= base_Q32 ) {\r
144                 break;\r
145             }\r
146             high_Q16 = low_Q16;\r
147             /* Test for out of range */\r
148             if( high_Q16 == 0 ) {\r
149                 psRC->error = RANGE_CODER_CDF_OUT_OF_RANGE;\r
150                 /* Set output to zero */\r
151                 *data = 0;\r
152                 return;\r
153             }\r
154         }\r
155     } else {\r
156         while( 1 ) {\r
157             low_Q16  = high_Q16;\r
158             high_Q16 = prob[ ++probIx ];\r
159             base_tmp = SKP_MUL_uint( range_Q16, high_Q16 );\r
160             if( base_tmp > base_Q32 ) {\r
161                 probIx--;\r
162                 break;\r
163             }\r
164             /* Test for out of range */\r
165             if( high_Q16 == 0xFFFF ) {\r
166                 psRC->error = RANGE_CODER_CDF_OUT_OF_RANGE;\r
167                 /* Set output to zero */\r
168                 *data = 0;\r
169                 return;\r
170             }\r
171         }\r
172     }\r
173     *data = probIx;\r
174     base_Q32 -= SKP_MUL_uint( range_Q16, low_Q16 );\r
175     range_Q32 = SKP_MUL_uint( range_Q16, high_Q16 - low_Q16 );\r
176 \r
177     /* Check normalization */\r
178     if( range_Q32 & 0xFF000000 ) {\r
179         /* No normalization */\r
180         range_Q16 = SKP_RSHIFT_uint( range_Q32, 16 );\r
181     } else {\r
182         if( range_Q32 & 0xFFFF0000 ) {\r
183             /* Normalization of 8 bits shift */\r
184             range_Q16 = SKP_RSHIFT_uint( range_Q32, 8 );\r
185             /* Check for errors */\r
186             if( SKP_RSHIFT_uint( base_Q32, 24 ) ) {\r
187                 psRC->error = RANGE_CODER_NORMALIZATION_FAILED;\r
188                 /* Set output to zero */\r
189                 *data = 0;\r
190                 return;\r
191             }\r
192         } else {\r
193             /* Normalization of 16 bits shift */\r
194             range_Q16 = range_Q32;\r
195             /* Check for errors */\r
196             if( SKP_RSHIFT( base_Q32, 16 ) ) {\r
197                 psRC->error = RANGE_CODER_NORMALIZATION_FAILED;\r
198                 /* Set output to zero */\r
199                 *data = 0;\r
200                 return;\r
201             }\r
202             /* Update base */\r
203             base_Q32 = SKP_LSHIFT_uint( base_Q32, 8 );\r
204             /* Make sure not to read beyond buffer */\r
205             if( bufferIx < psRC->bufferLength ) {\r
206                 /* Read one byte from buffer */\r
207                 base_Q32 |= (SKP_uint32)buffer[ bufferIx++ ];\r
208             }\r
209         }\r
210         /* Update base */\r
211         base_Q32 = SKP_LSHIFT_uint( base_Q32, 8 );\r
212         /* Make sure not to read beyond buffer */\r
213         if( bufferIx < psRC->bufferLength ) {\r
214             /* Read one byte from buffer */\r
215             base_Q32 |= (SKP_uint32)buffer[ bufferIx++ ];\r
216         }\r
217     }\r
218 \r
219     /* Check for zero interval length */\r
220     if( range_Q16 == 0 ) {\r
221         psRC->error = RANGE_CODER_ZERO_INTERVAL_WIDTH;\r
222         /* Set output to zero */\r
223         *data = 0;\r
224         return;\r
225     }\r
226 \r
227     /* Copy structure data back */\r
228     psRC->base_Q32  = base_Q32;\r
229     psRC->range_Q16 = range_Q16;\r
230     psRC->bufferIx  = bufferIx;\r
231 }\r
232 \r
233 /* Range decoder for multiple symbols */\r
234 void SKP_Silk_range_decoder_multi(\r
235     SKP_int                         data[],             /* O    uncompressed data                [nSymbols] */\r
236     SKP_Silk_range_coder_state      *psRC,              /* I/O  compressor data structure                   */\r
237     const SKP_uint16 * const        prob[],             /* I    cumulative density functions                */\r
238     const SKP_int                   probStartIx[],      /* I    initial (middle) entries of cdfs [nSymbols] */\r
239     const SKP_int                   nSymbols            /* I    number of data symbols                      */\r
240 )\r
241 {\r
242     SKP_int k;\r
243     for( k = 0; k < nSymbols; k++ ) {\r
244         SKP_Silk_range_decoder( &data[ k ], psRC, prob[ k ], probStartIx[ k ] );\r
245     }\r
246 }\r
247 \r
248 /* Initialize range encoder */\r
249 void SKP_Silk_range_enc_init(\r
250     SKP_Silk_range_coder_state      *psRC               /* O    compressor data structure                   */\r
251 )\r
252 {\r
253     /* Initialize structure */\r
254     psRC->bufferLength = MAX_ARITHM_BYTES;\r
255     psRC->range_Q16    = 0x0000FFFF;\r
256     psRC->bufferIx     = 0;\r
257     psRC->base_Q32     = 0;\r
258     psRC->error        = 0;\r
259 }\r
260 \r
261 /* Initialize range decoder */\r
262 void SKP_Silk_range_dec_init(\r
263     SKP_Silk_range_coder_state      *psRC,              /* O    compressor data structure                   */\r
264     const SKP_uint8                 buffer[],           /* I    buffer for compressed data [bufferLength]   */\r
265     const SKP_int32                 bufferLength        /* I    buffer length (in bytes)                    */\r
266 )\r
267 {\r
268     /* check input */\r
269     if( bufferLength > MAX_ARITHM_BYTES ) {\r
270         psRC->error = RANGE_CODER_DEC_PAYLOAD_TOO_LONG;\r
271         return;\r
272     }\r
273     /* Initialize structure */\r
274     /* Copy to internal buffer */\r
275     SKP_memcpy( psRC->buffer, buffer, bufferLength * sizeof( SKP_uint8 ) ); \r
276     psRC->bufferLength = bufferLength;\r
277     psRC->bufferIx = 0;\r
278     psRC->base_Q32 = \r
279         SKP_LSHIFT_uint( (SKP_uint32)buffer[ 0 ], 24 ) | \r
280         SKP_LSHIFT_uint( (SKP_uint32)buffer[ 1 ], 16 ) | \r
281         SKP_LSHIFT_uint( (SKP_uint32)buffer[ 2 ],  8 ) | \r
282                          (SKP_uint32)buffer[ 3 ];\r
283     psRC->range_Q16 = 0x0000FFFF;\r
284     psRC->error     = 0;\r
285 }\r
286 \r
287 /* Determine length of bitstream */\r
288 SKP_int SKP_Silk_range_coder_get_length(                /* O    returns number of BITS in stream            */\r
289     const SKP_Silk_range_coder_state    *psRC,          /* I    compressed data structure                   */\r
290     SKP_int                             *nBytes         /* O    number of BYTES in stream                   */\r
291 )\r
292 {\r
293     SKP_int nBits;\r
294 \r
295     /* Number of additional bits (1..9) required to be stored to stream */\r
296     nBits = SKP_LSHIFT( psRC->bufferIx, 3 ) + SKP_Silk_CLZ32( psRC->range_Q16 - 1 ) - 14;\r
297 \r
298     *nBytes = SKP_RSHIFT( nBits + 7, 3 );\r
299 \r
300     /* Return number of bits in bitstream */\r
301     return nBits;\r
302 }\r
303 \r
304 /* Write shortest uniquely decodable stream to buffer, and determine its length */\r
305 void SKP_Silk_range_enc_wrap_up(\r
306     SKP_Silk_range_coder_state      *psRC               /* I/O  compressed data structure                   */\r
307 )\r
308 {\r
309     SKP_int bufferIx_tmp, bits_to_store, bits_in_stream, nBytes, mask;\r
310     SKP_uint32 base_Q24;\r
311 \r
312     /* Lower limit of interval, shifted 8 bits to the right */\r
313     base_Q24 = SKP_RSHIFT_uint( psRC->base_Q32, 8 );\r
314 \r
315     bits_in_stream = SKP_Silk_range_coder_get_length( psRC, &nBytes );\r
316 \r
317     /* Number of additional bits (1..9) required to be stored to stream */\r
318     bits_to_store = bits_in_stream - SKP_LSHIFT( psRC->bufferIx, 3 );\r
319     /* Round up to required resolution */\r
320     base_Q24 += SKP_RSHIFT_uint(  0x00800000, bits_to_store - 1 );\r
321     base_Q24 &= SKP_LSHIFT_ovflw( 0xFFFFFFFF, 24 - bits_to_store );\r
322 \r
323     /* Check for carry */\r
324     if( base_Q24 & 0x01000000 ) {\r
325         /* Propagate carry in buffer */\r
326         bufferIx_tmp = psRC->bufferIx;\r
327         while( ( ++( psRC->buffer[ --bufferIx_tmp ] ) ) == 0 );\r
328     }\r
329 \r
330     /* Store to stream, making sure not to write beyond buffer */\r
331     if( psRC->bufferIx < psRC->bufferLength ) {\r
332         psRC->buffer[ psRC->bufferIx++ ] = (SKP_uint8)SKP_RSHIFT_uint( base_Q24, 16 );\r
333         if( bits_to_store > 8 ) {\r
334             if( psRC->bufferIx < psRC->bufferLength ) {\r
335                 psRC->buffer[ psRC->bufferIx++ ] = (SKP_uint8)SKP_RSHIFT_uint( base_Q24, 8 );\r
336             }\r
337         }\r
338     }\r
339 \r
340     /* Fill up any remaining bits in the last byte with 1s */\r
341     if( bits_in_stream & 7 ) {\r
342         mask = SKP_RSHIFT( 0xFF, bits_in_stream & 7 );\r
343         if( nBytes - 1 < psRC->bufferLength ) {\r
344             psRC->buffer[ nBytes - 1 ] |= mask;\r
345         }\r
346     }\r
347 }\r
348 \r
349 /* Check that any remaining bits in the last byte are set to 1 */\r
350 void SKP_Silk_range_coder_check_after_decoding(\r
351     SKP_Silk_range_coder_state      *psRC               /* I/O  compressed data structure                   */\r
352 )\r
353 {\r
354     SKP_int bits_in_stream, nBytes, mask;\r
355 \r
356     bits_in_stream = SKP_Silk_range_coder_get_length( psRC, &nBytes );\r
357 \r
358     /* Make sure not to read beyond buffer */\r
359     if( nBytes - 1 >= psRC->bufferLength ) {\r
360         psRC->error = RANGE_CODER_DECODER_CHECK_FAILED;\r
361         return;\r
362     }\r
363 \r
364     /* Test any remaining bits in last byte */\r
365     if( bits_in_stream & 7 ) {\r
366         mask = SKP_RSHIFT( 0xFF, bits_in_stream & 7 );\r
367         if( ( psRC->buffer[ nBytes - 1 ] & mask ) != mask ) {\r
368             psRC->error = RANGE_CODER_DECODER_CHECK_FAILED;\r
369             return;\r
370         }\r
371     }\r
372 }\r