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