Prevent out of bounds access to collapse_masks.
[opus.git] / libcelt / quant_bands.c
1 /* Copyright (c) 2007-2008 CSIRO
2    Copyright (c) 2007-2009 Xiph.Org Foundation
3    Written by Jean-Marc Valin */
4 /*
5    Redistribution and use in source and binary forms, with or without
6    modification, are permitted provided that the following conditions
7    are met:
8    
9    - Redistributions of source code must retain the above copyright
10    notice, this list of conditions and the following disclaimer.
11    
12    - Redistributions in binary form must reproduce the above copyright
13    notice, this list of conditions and the following disclaimer in the
14    documentation and/or other materials provided with the distribution.
15    
16    - Neither the name of the Xiph.org Foundation nor the names of its
17    contributors may be used to endorse or promote products derived from
18    this software without specific prior written permission.
19    
20    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23    A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
24    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33 #ifdef HAVE_CONFIG_H
34 #include "config.h"
35 #endif
36
37 #include "quant_bands.h"
38 #include "laplace.h"
39 #include <math.h>
40 #include "os_support.h"
41 #include "arch.h"
42 #include "mathops.h"
43 #include "stack_alloc.h"
44 #include "rate.h"
45
46 #ifdef FIXED_POINT
47 /* Mean energy in each band quantized in Q6 */
48 static const signed char eMeans[25] = {
49       103,100, 92, 85, 81,
50        77, 72, 70, 78, 75,
51        73, 71, 78, 74, 69,
52        72, 70, 74, 76, 71,
53        60, 60, 60, 60, 60
54 };
55 #else
56 /* Mean energy in each band quantized in Q6 and converted back to float */
57 static const celt_word16 eMeans[25] = {
58       6.437500f, 6.250000f, 5.750000f, 5.312500f, 5.062500f,
59       4.812500f, 4.500000f, 4.375000f, 4.875000f, 4.687500f,
60       4.562500f, 4.437500f, 4.875000f, 4.625000f, 4.312500f,
61       4.500000f, 4.375000f, 4.625000f, 4.750000f, 4.437500f,
62       3.750000f, 3.750000f, 3.750000f, 3.750000f, 3.750000f
63 };
64 #endif
65 /* prediction coefficients: 0.9, 0.8, 0.65, 0.5 */
66 #ifdef FIXED_POINT
67 static const celt_word16 pred_coef[4] = {29440, 26112, 21248, 16384};
68 static const celt_word16 beta_coef[4] = {30147, 22282, 12124, 6554};
69 #else
70 static const celt_word16 pred_coef[4] = {29440/32768., 26112/32768., 21248/32768., 16384/32768.};
71 static const celt_word16 beta_coef[4] = {30147/32768., 22282/32768., 12124/32768., 6554/32768.};
72 #endif
73
74 /*Parameters of the Laplace-like probability models used for the coarse energy.
75   There is one pair of parameters for each frame size, prediction type
76    (inter/intra), and band number.
77   The first number of each pair is the probability of 0, and the second is the
78    decay rate, both in Q8 precision.*/
79 static const unsigned char e_prob_model[4][2][42] = {
80    /*120 sample frames.*/
81    {
82       /*Inter*/
83       {
84           72, 127,  65, 129,  66, 128,  65, 128,  64, 128,  62, 128,  64, 128,
85           64, 128,  92,  78,  92,  79,  92,  78,  90,  79, 116,  41, 115,  40,
86          114,  40, 132,  26, 132,  26, 145,  17, 161,  12, 176,  10, 177,  11
87       },
88       /*Intra*/
89       {
90           24, 179,  48, 138,  54, 135,  54, 132,  53, 134,  56, 133,  55, 132,
91           55, 132,  61, 114,  70,  96,  74,  88,  75,  88,  87,  74,  89,  66,
92           91,  67, 100,  59, 108,  50, 120,  40, 122,  37,  97,  43,  78,  50
93       }
94    },
95    /*240 sample frames.*/
96    {
97       /*Inter*/
98       {
99           83,  78,  84,  81,  88,  75,  86,  74,  87,  71,  90,  73,  93,  74,
100           93,  74, 109,  40, 114,  36, 117,  34, 117,  34, 143,  17, 145,  18,
101          146,  19, 162,  12, 165,  10, 178,   7, 189,   6, 190,   8, 177,   9
102       },
103       /*Intra*/
104       {
105           23, 178,  54, 115,  63, 102,  66,  98,  69,  99,  74,  89,  71,  91,
106           73,  91,  78,  89,  86,  80,  92,  66,  93,  64, 102,  59, 103,  60,
107          104,  60, 117,  52, 123,  44, 138,  35, 133,  31,  97,  38,  77,  45
108       }
109    },
110    /*480 sample frames.*/
111    {
112       /*Inter*/
113       {
114           61,  90,  93,  60, 105,  42, 107,  41, 110,  45, 116,  38, 113,  38,
115          112,  38, 124,  26, 132,  27, 136,  19, 140,  20, 155,  14, 159,  16,
116          158,  18, 170,  13, 177,  10, 187,   8, 192,   6, 175,   9, 159,  10
117       },
118       /*Intra*/
119       {
120           21, 178,  59, 110,  71,  86,  75,  85,  84,  83,  91,  66,  88,  73,
121           87,  72,  92,  75,  98,  72, 105,  58, 107,  54, 115,  52, 114,  55,
122          112,  56, 129,  51, 132,  40, 150,  33, 140,  29,  98,  35,  77,  42
123       }
124    },
125    /*960 sample frames.*/
126    {
127       /*Inter*/
128       {
129           42, 121,  96,  66, 108,  43, 111,  40, 117,  44, 123,  32, 120,  36,
130          119,  33, 127,  33, 134,  34, 139,  21, 147,  23, 152,  20, 158,  25,
131          154,  26, 166,  21, 173,  16, 184,  13, 184,  10, 150,  13, 139,  15
132       },
133       /*Intra*/
134       {
135           22, 178,  63, 114,  74,  82,  84,  83,  92,  82, 103,  62,  96,  72,
136           96,  67, 101,  73, 107,  72, 113,  55, 118,  52, 125,  52, 118,  52,
137          117,  55, 135,  49, 137,  39, 157,  32, 145,  29,  97,  33,  77,  40
138       }
139    }
140 };
141
142 static const unsigned char small_energy_icdf[3]={2,1,0};
143
144 static int intra_decision(const celt_word16 *eBands, celt_word16 *oldEBands, int start, int end, int len, int C)
145 {
146    int c, i;
147    celt_word32 dist = 0;
148    c=0; do {
149       for (i=start;i<end;i++)
150       {
151          celt_word16 d = SHR16(SUB16(eBands[i+c*len], oldEBands[i+c*len]),2);
152          dist = MAC16_16(dist, d,d);
153       }
154    } while (++c<C);
155    return SHR32(dist,2*DB_SHIFT-4) > 2*C*(end-start);
156 }
157
158 static void quant_coarse_energy_impl(const CELTMode *m, int start, int end,
159       const celt_word16 *eBands, celt_word16 *oldEBands,
160       ec_int32 budget, ec_int32 tell,
161       const unsigned char *prob_model, celt_word16 *error, ec_enc *enc,
162       int _C, int LM, int intra, celt_word16 max_decay)
163 {
164    const int C = CHANNELS(_C);
165    int i, c;
166    celt_word32 prev[2] = {0,0};
167    celt_word16 coef;
168    celt_word16 beta;
169
170    if (tell+3 <= budget)
171       ec_enc_bit_logp(enc, intra, 3);
172    if (intra)
173    {
174       coef = 0;
175       beta = QCONST16(.15f,15);
176    } else {
177       beta = beta_coef[LM];
178       coef = pred_coef[LM];
179    }
180
181    /* Encode at a fixed coarse resolution */
182    for (i=start;i<end;i++)
183    {
184       c=0;
185       do {
186          int bits_left;
187          int qi;
188          celt_word16 q;
189          celt_word16 x;
190          celt_word32 f;
191          x = eBands[i+c*m->nbEBands];
192 #ifdef FIXED_POINT
193          f = SHL32(EXTEND32(x),15) -MULT16_16(coef,oldEBands[i+c*m->nbEBands])-prev[c];
194          /* Rounding to nearest integer here is really important! */
195          qi = (f+QCONST32(.5,DB_SHIFT+15))>>(DB_SHIFT+15);
196 #else
197          f = x-coef*oldEBands[i+c*m->nbEBands]-prev[c];
198          /* Rounding to nearest integer here is really important! */
199          qi = (int)floor(.5f+f);
200 #endif
201          /* Prevent the energy from going down too quickly (e.g. for bands
202             that have just one bin) */
203          if (qi < 0 && x < oldEBands[i+c*m->nbEBands]-max_decay)
204          {
205             qi += (int)SHR16(oldEBands[i+c*m->nbEBands]-max_decay-x, DB_SHIFT);
206             if (qi > 0)
207                qi = 0;
208          }
209          /* If we don't have enough bits to encode all the energy, just assume
210              something safe. */
211          tell = ec_enc_tell(enc, 0);
212          bits_left = budget-tell-3*C*(end-i);
213          if (i!=start && bits_left < 30)
214          {
215             if (bits_left < 24)
216                qi = IMIN(1, qi);
217             if (bits_left < 16)
218                qi = IMAX(-1, qi);
219          }
220          if (budget-tell >= 15)
221          {
222             int pi;
223             pi = 2*IMIN(i,20);
224             ec_laplace_encode(enc, &qi,
225                   prob_model[pi]<<7, prob_model[pi+1]<<6);
226          }
227          else if(budget-tell >= 2)
228          {
229             qi = IMAX(-1, IMIN(qi, 1));
230             ec_enc_icdf(enc, 2*qi^-(qi<0), small_energy_icdf, 2);
231          }
232          else if(budget-tell >= 1)
233          {
234             qi = IMIN(0, qi);
235             ec_enc_bit_logp(enc, -qi, 1);
236          }
237          else
238             qi = -1;
239          error[i+c*m->nbEBands] = PSHR32(f,15) - SHL16(qi,DB_SHIFT);
240          q = SHL16(qi,DB_SHIFT);
241          
242          oldEBands[i+c*m->nbEBands] = PSHR32(MULT16_16(coef,oldEBands[i+c*m->nbEBands]) + prev[c] + SHL32(EXTEND32(q),15), 15);
243          prev[c] = prev[c] + SHL32(EXTEND32(q),15) - MULT16_16(beta,q);
244       } while (++c < C);
245    }
246 }
247
248 void quant_coarse_energy(const CELTMode *m, int start, int end, int effEnd,
249       const celt_word16 *eBands, celt_word16 *oldEBands, ec_uint32 budget,
250       celt_word16 *error, ec_enc *enc, int _C, int LM, int nbAvailableBytes,
251       int force_intra, int *delayedIntra, int two_pass)
252 {
253    const int C = CHANNELS(_C);
254    int intra;
255    celt_word16 max_decay;
256    VARDECL(celt_word16, oldEBands_intra);
257    VARDECL(celt_word16, error_intra);
258    ec_enc enc_start_state;
259    ec_byte_buffer buf_start_state;
260    ec_uint32 tell;
261    SAVE_STACK;
262
263    intra = force_intra || (*delayedIntra && nbAvailableBytes > end*C);
264    if (/*shortBlocks || */intra_decision(eBands, oldEBands, start, effEnd, m->nbEBands, C))
265       *delayedIntra = 1;
266    else
267       *delayedIntra = 0;
268
269    tell = ec_enc_tell(enc, 0);
270    if (tell+3 > budget)
271       two_pass = intra = 0;
272
273    /* Encode the global flags using a simple probability model
274       (first symbols in the stream) */
275
276 #ifdef FIXED_POINT
277       max_decay = MIN32(QCONST16(16,DB_SHIFT), SHL32(EXTEND32(nbAvailableBytes),DB_SHIFT-3));
278 #else
279    max_decay = MIN32(16.f, .125f*nbAvailableBytes);
280 #endif
281
282    enc_start_state = *enc;
283    buf_start_state = *(enc->buf);
284
285    ALLOC(oldEBands_intra, C*m->nbEBands, celt_word16);
286    ALLOC(error_intra, C*m->nbEBands, celt_word16);
287    CELT_COPY(oldEBands_intra, oldEBands, C*end);
288
289    if (two_pass || intra)
290    {
291       quant_coarse_energy_impl(m, start, end, eBands, oldEBands_intra, budget,
292             tell, e_prob_model[LM][1], error_intra, enc, C, LM, 1, max_decay);
293    }
294
295    if (!intra)
296    {
297       ec_enc enc_intra_state;
298       ec_byte_buffer buf_intra_state;
299       int tell_intra;
300       ec_uint32 nstart_bytes;
301       ec_uint32 nintra_bytes;
302       VARDECL(unsigned char, intra_bits);
303
304       tell_intra = ec_enc_tell(enc, 3);
305
306       enc_intra_state = *enc;
307       buf_intra_state = *(enc->buf);
308
309       nstart_bytes = ec_byte_bytes(&buf_start_state);
310       nintra_bytes = ec_byte_bytes(&buf_intra_state);
311       ALLOC(intra_bits, nintra_bytes-nstart_bytes, unsigned char);
312       /* Copy bits from intra bit-stream */
313       CELT_COPY(intra_bits,
314             ec_byte_get_buffer(&buf_intra_state) + nstart_bytes,
315             nintra_bytes - nstart_bytes);
316
317       *enc = enc_start_state;
318       *(enc->buf) = buf_start_state;
319
320       quant_coarse_energy_impl(m, start, end, eBands, oldEBands, budget,
321             tell, e_prob_model[LM][intra], error, enc, C, LM, 0, max_decay);
322
323       if (two_pass && ec_enc_tell(enc, 3) > tell_intra)
324       {
325          *enc = enc_intra_state;
326          *(enc->buf) = buf_intra_state;
327          /* Copy intra bits to bit-stream */
328          CELT_COPY(ec_byte_get_buffer(&buf_intra_state) + nstart_bytes,
329                intra_bits, nintra_bytes - nstart_bytes);
330          CELT_COPY(oldEBands, oldEBands_intra, C*end);
331          CELT_COPY(error, error_intra, C*end);
332       }
333    } else {
334       CELT_COPY(oldEBands, oldEBands_intra, C*end);
335       CELT_COPY(error, error_intra, C*end);
336    }
337    RESTORE_STACK;
338 }
339
340 void quant_fine_energy(const CELTMode *m, int start, int end, celt_ener *eBands, celt_word16 *oldEBands, celt_word16 *error, int *fine_quant, ec_enc *enc, int _C)
341 {
342    int i, c;
343    const int C = CHANNELS(_C);
344
345    /* Encode finer resolution */
346    for (i=start;i<end;i++)
347    {
348       celt_int16 frac = 1<<fine_quant[i];
349       if (fine_quant[i] <= 0)
350          continue;
351       c=0;
352       do {
353          int q2;
354          celt_word16 offset;
355 #ifdef FIXED_POINT
356          /* Has to be without rounding */
357          q2 = (error[i+c*m->nbEBands]+QCONST16(.5f,DB_SHIFT))>>(DB_SHIFT-fine_quant[i]);
358 #else
359          q2 = (int)floor((error[i+c*m->nbEBands]+.5f)*frac);
360 #endif
361          if (q2 > frac-1)
362             q2 = frac-1;
363          if (q2<0)
364             q2 = 0;
365          ec_enc_bits(enc, q2, fine_quant[i]);
366 #ifdef FIXED_POINT
367          offset = SUB16(SHR32(SHL32(EXTEND32(q2),DB_SHIFT)+QCONST16(.5,DB_SHIFT),fine_quant[i]),QCONST16(.5f,DB_SHIFT));
368 #else
369          offset = (q2+.5f)*(1<<(14-fine_quant[i]))*(1.f/16384) - .5f;
370 #endif
371          oldEBands[i+c*m->nbEBands] += offset;
372          error[i+c*m->nbEBands] -= offset;
373          /*printf ("%f ", error[i] - offset);*/
374       } while (++c < C);
375    }
376 }
377
378 void quant_energy_finalise(const CELTMode *m, int start, int end, celt_ener *eBands, celt_word16 *oldEBands, celt_word16 *error, int *fine_quant, int *fine_priority, int bits_left, ec_enc *enc, int _C)
379 {
380    int i, prio, c;
381    const int C = CHANNELS(_C);
382
383    /* Use up the remaining bits */
384    for (prio=0;prio<2;prio++)
385    {
386       for (i=start;i<end && bits_left>=C ;i++)
387       {
388          if (fine_quant[i] >= MAX_FINE_BITS || fine_priority[i]!=prio)
389             continue;
390          c=0;
391          do {
392             int q2;
393             celt_word16 offset;
394             q2 = error[i+c*m->nbEBands]<0 ? 0 : 1;
395             ec_enc_bits(enc, q2, 1);
396 #ifdef FIXED_POINT
397             offset = SHR16(SHL16(q2,DB_SHIFT)-QCONST16(.5,DB_SHIFT),fine_quant[i]+1);
398 #else
399             offset = (q2-.5f)*(1<<(14-fine_quant[i]-1))*(1.f/16384);
400 #endif
401             oldEBands[i+c*m->nbEBands] += offset;
402             bits_left--;
403          } while (++c < C);
404       }
405    }
406 }
407
408 void unquant_coarse_energy(const CELTMode *m, int start, int end, celt_ener *eBands, celt_word16 *oldEBands, int intra, ec_dec *dec, int _C, int LM)
409 {
410    const unsigned char *prob_model = e_prob_model[LM][intra];
411    int i, c;
412    celt_word32 prev[2] = {0, 0};
413    celt_word16 coef;
414    celt_word16 beta;
415    const int C = CHANNELS(_C);
416    ec_int32 budget;
417    ec_int32 tell;
418
419
420    if (intra)
421    {
422       coef = 0;
423       beta = QCONST16(.15f,15);
424    } else {
425       beta = beta_coef[LM];
426       coef = pred_coef[LM];
427    }
428
429    budget = dec->buf->storage*8;
430
431    /* Decode at a fixed coarse resolution */
432    for (i=start;i<end;i++)
433    {
434       c=0;
435       do {
436          int qi;
437          celt_word16 q;
438          tell = ec_dec_tell(dec, 0);
439          if(budget-tell>=15)
440          {
441             int pi;
442             pi = 2*IMIN(i,20);
443             qi = ec_laplace_decode(dec,
444                   prob_model[pi]<<7, prob_model[pi+1]<<6);
445          }
446          else if(budget-tell>=2)
447          {
448             qi = ec_dec_icdf(dec, small_energy_icdf, 2);
449             qi = (qi>>1)^-(qi&1);
450          }
451          else if(budget-tell>=1)
452          {
453             qi = -ec_dec_bit_logp(dec, 1);
454          }
455          else
456             qi = -1;
457          q = SHL16(qi,DB_SHIFT);
458
459          oldEBands[i+c*m->nbEBands] = PSHR32(MULT16_16(coef,oldEBands[i+c*m->nbEBands]) + prev[c] + SHL32(EXTEND32(q),15), 15);
460          prev[c] = prev[c] + SHL32(EXTEND32(q),15) - MULT16_16(beta,q);
461       } while (++c < C);
462    }
463 }
464
465 void unquant_fine_energy(const CELTMode *m, int start, int end, celt_ener *eBands, celt_word16 *oldEBands, int *fine_quant, ec_dec *dec, int _C)
466 {
467    int i, c;
468    const int C = CHANNELS(_C);
469    /* Decode finer resolution */
470    for (i=start;i<end;i++)
471    {
472       if (fine_quant[i] <= 0)
473          continue;
474       c=0; 
475       do {
476          int q2;
477          celt_word16 offset;
478          q2 = ec_dec_bits(dec, fine_quant[i]);
479 #ifdef FIXED_POINT
480          offset = SUB16(SHR32(SHL32(EXTEND32(q2),DB_SHIFT)+QCONST16(.5,DB_SHIFT),fine_quant[i]),QCONST16(.5f,DB_SHIFT));
481 #else
482          offset = (q2+.5f)*(1<<(14-fine_quant[i]))*(1.f/16384) - .5f;
483 #endif
484          oldEBands[i+c*m->nbEBands] += offset;
485       } while (++c < C);
486    }
487 }
488
489 void unquant_energy_finalise(const CELTMode *m, int start, int end, celt_ener *eBands, celt_word16 *oldEBands, int *fine_quant,  int *fine_priority, int bits_left, ec_dec *dec, int _C)
490 {
491    int i, prio, c;
492    const int C = CHANNELS(_C);
493
494    /* Use up the remaining bits */
495    for (prio=0;prio<2;prio++)
496    {
497       for (i=start;i<end && bits_left>=C ;i++)
498       {
499          if (fine_quant[i] >= MAX_FINE_BITS || fine_priority[i]!=prio)
500             continue;
501          c=0;
502          do {
503             int q2;
504             celt_word16 offset;
505             q2 = ec_dec_bits(dec, 1);
506 #ifdef FIXED_POINT
507             offset = SHR16(SHL16(q2,DB_SHIFT)-QCONST16(.5,DB_SHIFT),fine_quant[i]+1);
508 #else
509             offset = (q2-.5f)*(1<<(14-fine_quant[i]-1))*(1.f/16384);
510 #endif
511             oldEBands[i+c*m->nbEBands] += offset;
512             bits_left--;
513          } while (++c < C);
514       }
515    }
516 }
517
518 void log2Amp(const CELTMode *m, int start, int end,
519       celt_ener *eBands, celt_word16 *oldEBands, int _C)
520 {
521    int c, i;
522    const int C = CHANNELS(_C);
523    c=0;
524    do {
525       for (i=start;i<m->nbEBands;i++)
526       {
527          celt_word16 lg = oldEBands[i+c*m->nbEBands]
528                         + SHL16((celt_word16)eMeans[i],6);
529          eBands[i+c*m->nbEBands] = PSHR32(celt_exp2(SHL16(lg,11-DB_SHIFT)),4);
530       }
531    } while (++c < C);
532 }
533
534 void amp2Log2(const CELTMode *m, int effEnd, int end,
535       celt_ener *bandE, celt_word16 *bandLogE, int _C)
536 {
537    int c, i;
538    const int C = CHANNELS(_C);
539    c=0;
540    do {
541       for (i=0;i<effEnd;i++)
542          bandLogE[i+c*m->nbEBands] =
543                celt_log2(SHL32(bandE[i+c*m->nbEBands],2))
544                - SHL16((celt_word16)eMeans[i],6);
545       for (i=effEnd;i<end;i++)
546          bandLogE[c*m->nbEBands+i] = -QCONST16(14.f,DB_SHIFT);
547    } while (++c < C);
548 }