Update SILK code using the CELT range coder
[opus.git] / src_common / 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 #define MAX_SIZE 10000\r
31 \r
32 /* Range encoder for one symbol */\r
33 void SKP_Silk_range_encoder(\r
34     SKP_Silk_range_coder_state      *psRC,              /* I/O  compressor data structure                   */\r
35     const SKP_int                   data,               /* I    uncompressed data                           */\r
36     const SKP_uint16                prob[]              /* I    cumulative density functions                */\r
37 )\r
38 {\r
39     SKP_uint32 low_Q16, high_Q16;\r
40 \r
41     if( psRC->error ) {\r
42         return;\r
43     }\r
44     low_Q16  = prob[ data ];\r
45     high_Q16 = prob[ data + 1 ];\r
46     \r
47 #ifdef SAVE_ALL_INTERNAL_DATA\r
48     DEBUG_STORE_DATA( enc_l.dat, &low_Q16,  sizeof(SKP_uint32) );\r
49     DEBUG_STORE_DATA( enc_h.dat, &high_Q16, sizeof(SKP_uint32) );\r
50     DEBUG_STORE_DATA( enc.dat,   &data,     sizeof(SKP_int) );\r
51 #endif\r
52 \r
53     if( prob[ 2 ] == 65535 ) {\r
54         /* Instead of detection, we could add a separate function and call when we know that input is a bit */\r
55         ec_enc_bit_prob( &psRC->range_enc_celt_state, data, 65536 - prob[ 1 ] );\r
56     } else {\r
57         ec_encode_bin( &psRC->range_enc_celt_state, low_Q16, high_Q16, 16 );\r
58     }\r
59 }\r
60 \r
61 /* Range encoder for one symbol, with uniform PDF*/\r
62 void SKP_Silk_range_encode_uniform(\r
63     SKP_Silk_range_coder_state      *psRC,              /* I/O  compressor data structure                   */\r
64     const SKP_int                   data,               /* I    uncompressed data                           */\r
65     const SKP_int                   N                   /* I    number of possible outcomes                 */\r
66 )\r
67 {\r
68     SKP_int i;\r
69     SKP_uint16 delta, prob[ MAX_SIZE + 1 ];\r
70 \r
71     SKP_assert( N < MAX_SIZE );\r
72 \r
73     delta = ( SKP_uint16 )SKP_DIV32_16( 65535, N );\r
74     prob[ 0 ] = 0;\r
75     for( i = 0; i < N - 1; i++ ) {\r
76         prob[ i + 1 ] = prob[ i ] + delta;\r
77     }\r
78     prob[ N ] = 65535;\r
79 \r
80     SKP_Silk_range_encoder( psRC, data, prob );\r
81 }\r
82 \r
83 /* Range encoder for multiple symbols */\r
84 void SKP_Silk_range_encoder_multi(\r
85     SKP_Silk_range_coder_state      *psRC,              /* I/O  compressor data structure                   */\r
86     const SKP_int                   data[],             /* I    uncompressed data    [nSymbols]             */\r
87     const SKP_uint16 * const        prob[],             /* I    cumulative density functions                */\r
88     const SKP_int                   nSymbols            /* I    number of data symbols                      */\r
89 )\r
90 {\r
91     SKP_int k;\r
92     for( k = 0; k < nSymbols; k++ ) {\r
93         SKP_Silk_range_encoder( psRC, data[ k ], prob[ k ] );\r
94     }\r
95 }\r
96 \r
97 /* Range decoder for one symbol */\r
98 void SKP_Silk_range_decoder(\r
99     SKP_int                         data[],             /* O    uncompressed data                           */\r
100     SKP_Silk_range_coder_state      *psRC,              /* I/O  compressor data structure                   */\r
101     const SKP_uint16                prob[],             /* I    cumulative density function                 */\r
102     SKP_int                         probIx              /* I    initial (middle) entry of cdf               */\r
103 )\r
104 {\r
105     SKP_uint32 low_Q16, high_Q16;\r
106 \r
107     SKP_uint32 low_Q16_returned;\r
108     SKP_int    temp;\r
109 \r
110     if( psRC->error ) {\r
111         /* Set output to zero */\r
112         *data = 0;\r
113         return;\r
114     }\r
115 \r
116     if( prob[ 2 ] == 65535 ) {\r
117         /* Instead of detection, we could add a separate function and call when we know that output is a bit */\r
118         *data = ec_dec_bit_prob( &psRC->range_dec_celt_state, 65536 - prob[ 1 ] );\r
119     } else {\r
120         low_Q16_returned = ec_decode_bin( &psRC->range_dec_celt_state, 16 );\r
121     }\r
122 \r
123     /* OPTIMIZE ME WITH BI-SECTION */\r
124     if( prob[ 2 ] != 65535 ) {\r
125 #if 1\r
126         temp = 0;\r
127         while( low_Q16_returned >= prob[ ++temp ] ) {}\r
128         *data = temp - 1;\r
129 #else\r
130         temp = probIx;\r
131         if( low_Q16_returned >= prob[ temp ] ){\r
132             while( low_Q16_returned >= prob[ temp ] ) {\r
133                 temp++;\r
134             }\r
135             temp = temp - 1;\r
136         } else {\r
137             /* search down */\r
138             while( low_Q16_returned < prob[ temp ] ) {\r
139                 temp--;\r
140             }\r
141         }\r
142         *data = temp;\r
143 #endif\r
144 \r
145         low_Q16  = prob[ *data ];\r
146         high_Q16 = prob[ *data + 1 ];\r
147 \r
148 #ifdef SAVE_ALL_INTERNAL_DATA\r
149         DEBUG_STORE_DATA( dec_lr.dat, &low_Q16_returned,  sizeof( SKP_uint32 ) );\r
150         DEBUG_STORE_DATA( dec_l.dat,  &low_Q16,           sizeof( SKP_uint32 ) );\r
151         DEBUG_STORE_DATA( dec_h.dat,  &high_Q16,          sizeof( SKP_uint32 ) );\r
152 #endif  \r
153         ec_dec_update( &psRC->range_dec_celt_state, low_Q16, high_Q16,( 1 << 16 ) );\r
154     }\r
155 #ifdef SAVE_ALL_INTERNAL_DATA\r
156     DEBUG_STORE_DATA( dec.dat, data, sizeof( SKP_int ) );\r
157 #endif\r
158 }\r
159 \r
160 /* Range decoder for one symbol, with uniform PDF*/\r
161 void SKP_Silk_range_decode_uniform(\r
162     SKP_int                         data[],             /* O    uncompressed data                           */\r
163     SKP_Silk_range_coder_state      *psRC,              /* I/O  compressor data structure                   */\r
164     const SKP_int                   N                   /* I    number of possible outcomes                 */\r
165 )\r
166 {\r
167     SKP_int i;\r
168     SKP_uint16 delta, prob[ MAX_SIZE + 1 ];\r
169 \r
170     SKP_assert( N < MAX_SIZE );\r
171 \r
172     delta = ( SKP_uint16 )SKP_DIV32_16( 65535, N );\r
173     prob[ 0 ] = 0;\r
174     for( i = 0; i < N - 1; i++ ) {\r
175         prob[ i + 1 ] = prob[ i ] + delta;\r
176     }\r
177     prob[ N ] = 65535;\r
178 \r
179     SKP_Silk_range_decoder( data, psRC, prob, ( N >> 1 ) );\r
180 }\r
181 \r
182 /* Range decoder for multiple symbols */\r
183 void SKP_Silk_range_decoder_multi(\r
184     SKP_int                         data[],             /* O    uncompressed data                [nSymbols] */\r
185     SKP_Silk_range_coder_state      *psRC,              /* I/O  compressor data structure                   */\r
186     const SKP_uint16 * const        prob[],             /* I    cumulative density functions                */\r
187     const SKP_int                   probStartIx[],      /* I    initial (middle) entries of cdfs [nSymbols] */\r
188     const SKP_int                   nSymbols            /* I    number of data symbols                      */\r
189 )\r
190 {\r
191     SKP_int k;\r
192     for( k = 0; k < nSymbols; k++ ) {\r
193         SKP_Silk_range_decoder( &data[ k ], psRC, prob[ k ], probStartIx[ k ] );\r
194     }\r
195 }\r
196 \r
197 /* Initialize range encoder */\r
198 void SKP_Silk_range_enc_init(\r
199     SKP_Silk_range_coder_state      *psRC               /* O    compressor data structure                   */\r
200 )\r
201 {\r
202     psRC->error        = 0;\r
203 }\r
204 \r
205 /* Initialize range decoder */\r
206 void SKP_Silk_range_dec_init(\r
207     SKP_Silk_range_coder_state      *psRC,              /* O    compressor data structure                   */\r
208     const SKP_uint8                 buffer[],           /* I    buffer for compressed data [bufferLength]   */\r
209     const SKP_int32                 bufferLength        /* I    buffer length (in bytes)                    */\r
210 )\r
211 {\r
212     /* check input */\r
213     if( bufferLength > MAX_ARITHM_BYTES ) {\r
214         psRC->error = RANGE_CODER_DEC_PAYLOAD_TOO_LONG;\r
215         return;\r
216     }\r
217     /* Initialize structure */\r
218     /* Copy to internal buffer */\r
219     SKP_memcpy( psRC->buffer, buffer, bufferLength * sizeof( SKP_uint8 ) ); \r
220     psRC->bufferLength = bufferLength;\r
221     psRC->bufferIx = 0;\r
222     psRC->base_Q32 = \r
223         SKP_LSHIFT_uint( ( SKP_uint32 )buffer[ 0 ], 24 ) | \r
224         SKP_LSHIFT_uint( ( SKP_uint32 )buffer[ 1 ], 16 ) | \r
225         SKP_LSHIFT_uint( ( SKP_uint32 )buffer[ 2 ],  8 ) | \r
226                          ( SKP_uint32 )buffer[ 3 ];\r
227     psRC->range_Q16 = 0x0000FFFF;\r
228     psRC->error     = 0;\r
229 }\r
230 \r
231 /* Determine length of bitstream */\r
232 SKP_int SKP_Silk_range_encoder_get_length(              /* O    returns number of BITS in stream            */\r
233     SKP_Silk_range_coder_state          *psRC,          /* I    compressed data structure                   */\r
234     SKP_int                             *nBytes         /* O    number of BYTES in stream                   */\r
235 )\r
236 {\r
237     SKP_int nBits;\r
238 \r
239     /* Get number of bits in bitstream */\r
240     nBits = ec_enc_tell( &psRC->range_enc_celt_state, 0 );\r
241 \r
242     /* Round up to an integer number of bytes */\r
243     *nBytes = SKP_RSHIFT( nBits + 7, 3 );\r
244 \r
245     /* Return number of bits in bitstream */\r
246     return nBits;\r
247 }\r
248 \r
249 /* Determine length of bitstream */\r
250 SKP_int SKP_Silk_range_decoder_get_length(              /* O    returns number of BITS in stream            */\r
251     SKP_Silk_range_coder_state          *psRC,          /* I    compressed data structure                   */\r
252     SKP_int                             *nBytes         /* O    number of BYTES in stream                   */\r
253 )\r
254 {\r
255     SKP_int nBits;\r
256 \r
257     /* Get number of bits in bitstream */\r
258     nBits = ec_dec_tell( &psRC->range_dec_celt_state, 0 );\r
259 \r
260     /* Round up to an integer number of bytes */\r
261     *nBytes = SKP_RSHIFT( nBits + 7, 3 );\r
262 \r
263     /* Return number of bits in bitstream */\r
264     return nBits;\r
265 }\r
266 \r
267 /* Check that any remaining bits in the last byte are set to 1 */\r
268 void SKP_Silk_range_coder_check_after_decoding(\r
269     SKP_Silk_range_coder_state      *psRC               /* I/O  compressed data structure                   */\r
270 )\r
271 {\r
272     SKP_int bits_in_stream, nBytes, mask;\r
273 \r
274     bits_in_stream = SKP_Silk_range_decoder_get_length( psRC, &nBytes );\r
275 \r
276     /* Make sure not to read beyond buffer */\r
277     if( nBytes - 1 >= psRC->range_dec_celt_state.buf->storage ) {\r
278         psRC->error = RANGE_CODER_DECODER_CHECK_FAILED;\r
279         return;\r
280     }\r
281 \r
282     /* Test any remaining bits in last byte */\r
283     if( bits_in_stream & 7 ) {\r
284         mask = SKP_RSHIFT( 0xFF, bits_in_stream & 7 );\r
285         if( ( psRC->range_dec_celt_state.buf->buf[ nBytes - 1 ] & mask ) != mask ) {\r
286             psRC->error = RANGE_CODER_DECODER_CHECK_FAILED;\r
287             return;\r
288         }\r
289     }\r
290 }\r