Relicensing under the simplified (2-clause) BSD license
[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    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 FOUNDATION OR
20    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 Q6 */
44 static 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 Q6 and converted back to float */
53 static const celt_word16 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 celt_word16 pred_coef[4] = {29440, 26112, 21248, 16384};
64 static const celt_word16 beta_coef[4] = {30147, 22282, 12124, 6554};
65 static const celt_word16 beta_intra = 4915;
66 #else
67 static const celt_word16 pred_coef[4] = {29440/32768., 26112/32768., 21248/32768., 16384/32768.};
68 static const celt_word16 beta_coef[4] = {30147/32768., 22282/32768., 12124/32768., 6554/32768.};
69 static const celt_word16 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 int intra_decision(const celt_word16 *eBands, celt_word16 *oldEBands, int start, int end, int len, int C)
143 {
144    int c, i;
145    celt_word32 dist = 0;
146    c=0; do {
147       for (i=start;i<end;i++)
148       {
149          celt_word16 d = SHR16(SUB16(eBands[i+c*len], oldEBands[i+c*len]),2);
150          dist = MAC16_16(dist, d,d);
151       }
152    } while (++c<C);
153    return SHR32(dist,2*DB_SHIFT-4) > 2*C*(end-start);
154 }
155
156 static int quant_coarse_energy_impl(const CELTMode *m, int start, int end,
157       const celt_word16 *eBands, celt_word16 *oldEBands,
158       ec_int32 budget, ec_int32 tell,
159       const unsigned char *prob_model, celt_word16 *error, ec_enc *enc,
160       int _C, int LM, int intra, celt_word16 max_decay)
161 {
162    const int C = CHANNELS(_C);
163    int i, c;
164    int badness = 0;
165    celt_word32 prev[2] = {0,0};
166    celt_word16 coef;
167    celt_word16 beta;
168
169    if (tell+3 <= budget)
170       ec_enc_bit_logp(enc, intra, 3);
171    if (intra)
172    {
173       coef = 0;
174       beta = beta_intra;
175    } else {
176       beta = beta_coef[LM];
177       coef = pred_coef[LM];
178    }
179
180    /* Encode at a fixed coarse resolution */
181    for (i=start;i<end;i++)
182    {
183       c=0;
184       do {
185          int bits_left;
186          int qi, qi0;
187          celt_word32 q;
188          celt_word16 x;
189          celt_word32 f, tmp;
190          celt_word16 oldE;
191          celt_word16 decay_bound;
192          x = eBands[i+c*m->nbEBands];
193          oldE = MAX16(-QCONST16(9.f,DB_SHIFT), oldEBands[i+c*m->nbEBands]);
194 #ifdef FIXED_POINT
195          f = SHL32(EXTEND32(x),7) - PSHR32(MULT16_16(coef,oldE), 8) - prev[c];
196          /* Rounding to nearest integer here is really important! */
197          qi = (f+QCONST32(.5f,DB_SHIFT+7))>>(DB_SHIFT+7);
198          decay_bound = EXTRACT16(MAX32(-QCONST16(28.f,DB_SHIFT),
199                SUB32((celt_word32)oldEBands[i+c*m->nbEBands],max_decay)));
200 #else
201          f = x-coef*oldE-prev[c];
202          /* Rounding to nearest integer here is really important! */
203          qi = (int)floor(.5f+f);
204          decay_bound = MAX16(-QCONST16(28.f,DB_SHIFT), oldEBands[i+c*m->nbEBands]) - max_decay;
205 #endif
206          /* Prevent the energy from going down too quickly (e.g. for bands
207             that have just one bin) */
208          if (qi < 0 && x < decay_bound)
209          {
210             qi += (int)SHR16(SUB16(decay_bound,x), DB_SHIFT);
211             if (qi > 0)
212                qi = 0;
213          }
214          qi0 = qi;
215          /* If we don't have enough bits to encode all the energy, just assume
216              something safe. */
217          tell = ec_tell(enc);
218          bits_left = budget-tell-3*C*(end-i);
219          if (i!=start && bits_left < 30)
220          {
221             if (bits_left < 24)
222                qi = IMIN(1, qi);
223             if (bits_left < 16)
224                qi = IMAX(-1, qi);
225          }
226          if (budget-tell >= 15)
227          {
228             int pi;
229             pi = 2*IMIN(i,20);
230             ec_laplace_encode(enc, &qi,
231                   prob_model[pi]<<7, prob_model[pi+1]<<6);
232          }
233          else if(budget-tell >= 2)
234          {
235             qi = IMAX(-1, IMIN(qi, 1));
236             ec_enc_icdf(enc, 2*qi^-(qi<0), small_energy_icdf, 2);
237          }
238          else if(budget-tell >= 1)
239          {
240             qi = IMIN(0, qi);
241             ec_enc_bit_logp(enc, -qi, 1);
242          }
243          else
244             qi = -1;
245          error[i+c*m->nbEBands] = PSHR32(f,7) - SHL16(qi,DB_SHIFT);
246          badness += abs(qi0-qi);
247          q = SHL32(EXTEND32(qi),DB_SHIFT);
248          
249          tmp = PSHR32(MULT16_16(coef,oldE),8) + prev[c] + SHL32(q,7);
250 #ifdef FIXED_POINT
251          tmp = MAX32(-QCONST32(28.f, DB_SHIFT+7), tmp);
252 #endif
253          oldEBands[i+c*m->nbEBands] = PSHR32(tmp, 7);
254          prev[c] = prev[c] + SHL32(q,7) - MULT16_16(beta,PSHR32(q,8));
255       } while (++c < C);
256    }
257    return badness;
258 }
259
260 void quant_coarse_energy(const CELTMode *m, int start, int end, int effEnd,
261       const celt_word16 *eBands, celt_word16 *oldEBands, ec_uint32 budget,
262       celt_word16 *error, ec_enc *enc, int _C, int LM, int nbAvailableBytes,
263       int force_intra, int *delayedIntra, int two_pass)
264 {
265    const int C = CHANNELS(_C);
266    int intra;
267    celt_word16 max_decay;
268    VARDECL(celt_word16, oldEBands_intra);
269    VARDECL(celt_word16, error_intra);
270    ec_enc enc_start_state;
271    ec_uint32 tell;
272    int badness1=0;
273    SAVE_STACK;
274
275    intra = force_intra || (*delayedIntra && nbAvailableBytes > end*C);
276    if (/*shortBlocks || */intra_decision(eBands, oldEBands, start, effEnd, m->nbEBands, C))
277       *delayedIntra = 1;
278    else
279       *delayedIntra = 0;
280
281    tell = ec_tell(enc);
282    if (tell+3 > budget)
283       two_pass = intra = 0;
284
285    /* Encode the global flags using a simple probability model
286       (first symbols in the stream) */
287
288 #ifdef FIXED_POINT
289       max_decay = MIN32(QCONST16(16.f,DB_SHIFT), SHL32(EXTEND32(nbAvailableBytes),DB_SHIFT-3));
290 #else
291    max_decay = MIN32(16.f, .125f*nbAvailableBytes);
292 #endif
293
294    enc_start_state = *enc;
295
296    ALLOC(oldEBands_intra, C*m->nbEBands, celt_word16);
297    ALLOC(error_intra, C*m->nbEBands, celt_word16);
298    CELT_COPY(oldEBands_intra, oldEBands, C*end);
299
300    if (two_pass || intra)
301    {
302       badness1 = quant_coarse_energy_impl(m, start, end, eBands, oldEBands_intra, budget,
303             tell, e_prob_model[LM][1], error_intra, enc, C, LM, 1, max_decay);
304    }
305
306    if (!intra)
307    {
308       ec_enc enc_intra_state;
309       int tell_intra;
310       ec_uint32 nstart_bytes;
311       ec_uint32 nintra_bytes;
312       int badness2;
313       VARDECL(unsigned char, intra_bits);
314
315       tell_intra = ec_tell_frac(enc);
316
317       enc_intra_state = *enc;
318
319       nstart_bytes = ec_range_bytes(&enc_start_state);
320       nintra_bytes = ec_range_bytes(&enc_intra_state);
321       ALLOC(intra_bits, nintra_bytes-nstart_bytes, unsigned char);
322       /* Copy bits from intra bit-stream */
323       CELT_COPY(intra_bits,
324             ec_get_buffer(&enc_intra_state) + nstart_bytes,
325             nintra_bytes - nstart_bytes);
326
327       *enc = enc_start_state;
328
329       badness2 = quant_coarse_energy_impl(m, start, end, eBands, oldEBands, budget,
330             tell, e_prob_model[LM][intra], error, enc, C, LM, 0, max_decay);
331
332       if (two_pass && (badness1 < badness2 || (badness1 == badness2 && ec_tell_frac(enc) > tell_intra)))
333       {
334          *enc = enc_intra_state;
335          /* Copy intra bits to bit-stream */
336          CELT_COPY(ec_get_buffer(&enc_intra_state) + nstart_bytes,
337                intra_bits, nintra_bytes - nstart_bytes);
338          CELT_COPY(oldEBands, oldEBands_intra, C*end);
339          CELT_COPY(error, error_intra, C*end);
340       }
341    } else {
342       CELT_COPY(oldEBands, oldEBands_intra, C*end);
343       CELT_COPY(error, error_intra, C*end);
344    }
345    RESTORE_STACK;
346 }
347
348 void quant_fine_energy(const CELTMode *m, int start, int end, celt_word16 *oldEBands, celt_word16 *error, int *fine_quant, ec_enc *enc, int _C)
349 {
350    int i, c;
351    const int C = CHANNELS(_C);
352
353    /* Encode finer resolution */
354    for (i=start;i<end;i++)
355    {
356       celt_int16 frac = 1<<fine_quant[i];
357       if (fine_quant[i] <= 0)
358          continue;
359       c=0;
360       do {
361          int q2;
362          celt_word16 offset;
363 #ifdef FIXED_POINT
364          /* Has to be without rounding */
365          q2 = (error[i+c*m->nbEBands]+QCONST16(.5f,DB_SHIFT))>>(DB_SHIFT-fine_quant[i]);
366 #else
367          q2 = (int)floor((error[i+c*m->nbEBands]+.5f)*frac);
368 #endif
369          if (q2 > frac-1)
370             q2 = frac-1;
371          if (q2<0)
372             q2 = 0;
373          ec_enc_bits(enc, q2, fine_quant[i]);
374 #ifdef FIXED_POINT
375          offset = SUB16(SHR32(SHL32(EXTEND32(q2),DB_SHIFT)+QCONST16(.5f,DB_SHIFT),fine_quant[i]),QCONST16(.5f,DB_SHIFT));
376 #else
377          offset = (q2+.5f)*(1<<(14-fine_quant[i]))*(1.f/16384) - .5f;
378 #endif
379          oldEBands[i+c*m->nbEBands] += offset;
380          error[i+c*m->nbEBands] -= offset;
381          /*printf ("%f ", error[i] - offset);*/
382       } while (++c < C);
383    }
384 }
385
386 void quant_energy_finalise(const CELTMode *m, int start, int end, celt_word16 *oldEBands, celt_word16 *error, int *fine_quant, int *fine_priority, int bits_left, ec_enc *enc, int _C)
387 {
388    int i, prio, c;
389    const int C = CHANNELS(_C);
390
391    /* Use up the remaining bits */
392    for (prio=0;prio<2;prio++)
393    {
394       for (i=start;i<end && bits_left>=C ;i++)
395       {
396          if (fine_quant[i] >= MAX_FINE_BITS || fine_priority[i]!=prio)
397             continue;
398          c=0;
399          do {
400             int q2;
401             celt_word16 offset;
402             q2 = error[i+c*m->nbEBands]<0 ? 0 : 1;
403             ec_enc_bits(enc, q2, 1);
404 #ifdef FIXED_POINT
405             offset = SHR16(SHL16(q2,DB_SHIFT)-QCONST16(.5f,DB_SHIFT),fine_quant[i]+1);
406 #else
407             offset = (q2-.5f)*(1<<(14-fine_quant[i]-1))*(1.f/16384);
408 #endif
409             oldEBands[i+c*m->nbEBands] += offset;
410             bits_left--;
411          } while (++c < C);
412       }
413    }
414 }
415
416 void unquant_coarse_energy(const CELTMode *m, int start, int end, celt_word16 *oldEBands, int intra, ec_dec *dec, int _C, int LM)
417 {
418    const unsigned char *prob_model = e_prob_model[LM][intra];
419    int i, c;
420    celt_word32 prev[2] = {0, 0};
421    celt_word16 coef;
422    celt_word16 beta;
423    const int C = CHANNELS(_C);
424    ec_int32 budget;
425    ec_int32 tell;
426
427
428    if (intra)
429    {
430       coef = 0;
431       beta = beta_intra;
432    } else {
433       beta = beta_coef[LM];
434       coef = pred_coef[LM];
435    }
436
437    budget = dec->storage*8;
438
439    /* Decode at a fixed coarse resolution */
440    for (i=start;i<end;i++)
441    {
442       c=0;
443       do {
444          int qi;
445          celt_word32 q;
446          celt_word32 tmp;
447          tell = ec_tell(dec);
448          if(budget-tell>=15)
449          {
450             int pi;
451             pi = 2*IMIN(i,20);
452             qi = ec_laplace_decode(dec,
453                   prob_model[pi]<<7, prob_model[pi+1]<<6);
454          }
455          else if(budget-tell>=2)
456          {
457             qi = ec_dec_icdf(dec, small_energy_icdf, 2);
458             qi = (qi>>1)^-(qi&1);
459          }
460          else if(budget-tell>=1)
461          {
462             qi = -ec_dec_bit_logp(dec, 1);
463          }
464          else
465             qi = -1;
466          q = SHL32(EXTEND32(qi),DB_SHIFT);
467
468          oldEBands[i+c*m->nbEBands] = MAX16(-QCONST16(9.f,DB_SHIFT), oldEBands[i+c*m->nbEBands]);
469          tmp = PSHR32(MULT16_16(coef,oldEBands[i+c*m->nbEBands]),8) + prev[c] + SHL32(q,7);
470 #ifdef FIXED_POINT
471          tmp = MAX32(-QCONST32(28.f, DB_SHIFT+7), tmp);
472 #endif
473          oldEBands[i+c*m->nbEBands] = PSHR32(tmp, 7);
474          prev[c] = prev[c] + SHL32(q,7) - MULT16_16(beta,PSHR32(q,8));
475       } while (++c < C);
476    }
477 }
478
479 void unquant_fine_energy(const CELTMode *m, int start, int end, celt_word16 *oldEBands, int *fine_quant, ec_dec *dec, int _C)
480 {
481    int i, c;
482    const int C = CHANNELS(_C);
483    /* Decode finer resolution */
484    for (i=start;i<end;i++)
485    {
486       if (fine_quant[i] <= 0)
487          continue;
488       c=0; 
489       do {
490          int q2;
491          celt_word16 offset;
492          q2 = ec_dec_bits(dec, fine_quant[i]);
493 #ifdef FIXED_POINT
494          offset = SUB16(SHR32(SHL32(EXTEND32(q2),DB_SHIFT)+QCONST16(.5f,DB_SHIFT),fine_quant[i]),QCONST16(.5f,DB_SHIFT));
495 #else
496          offset = (q2+.5f)*(1<<(14-fine_quant[i]))*(1.f/16384) - .5f;
497 #endif
498          oldEBands[i+c*m->nbEBands] += offset;
499       } while (++c < C);
500    }
501 }
502
503 void unquant_energy_finalise(const CELTMode *m, int start, int end, celt_word16 *oldEBands, int *fine_quant,  int *fine_priority, int bits_left, ec_dec *dec, int _C)
504 {
505    int i, prio, c;
506    const int C = CHANNELS(_C);
507
508    /* Use up the remaining bits */
509    for (prio=0;prio<2;prio++)
510    {
511       for (i=start;i<end && bits_left>=C ;i++)
512       {
513          if (fine_quant[i] >= MAX_FINE_BITS || fine_priority[i]!=prio)
514             continue;
515          c=0;
516          do {
517             int q2;
518             celt_word16 offset;
519             q2 = ec_dec_bits(dec, 1);
520 #ifdef FIXED_POINT
521             offset = SHR16(SHL16(q2,DB_SHIFT)-QCONST16(.5f,DB_SHIFT),fine_quant[i]+1);
522 #else
523             offset = (q2-.5f)*(1<<(14-fine_quant[i]-1))*(1.f/16384);
524 #endif
525             oldEBands[i+c*m->nbEBands] += offset;
526             bits_left--;
527          } while (++c < C);
528       }
529    }
530 }
531
532 void log2Amp(const CELTMode *m, int start, int end,
533       celt_ener *eBands, celt_word16 *oldEBands, int _C)
534 {
535    int c, i;
536    const int C = CHANNELS(_C);
537    c=0;
538    do {
539       for (i=0;i<start;i++)
540          eBands[i+c*m->nbEBands] = 0;
541       for (;i<end;i++)
542       {
543          celt_word16 lg = ADD16(oldEBands[i+c*m->nbEBands],
544                          SHL16((celt_word16)eMeans[i],6));
545          eBands[i+c*m->nbEBands] = PSHR32(celt_exp2(lg),4);
546       }
547       for (;i<m->nbEBands;i++)
548          eBands[i+c*m->nbEBands] = 0;
549    } while (++c < C);
550 }
551
552 void amp2Log2(const CELTMode *m, int effEnd, int end,
553       celt_ener *bandE, celt_word16 *bandLogE, int _C)
554 {
555    int c, i;
556    const int C = CHANNELS(_C);
557    c=0;
558    do {
559       for (i=0;i<effEnd;i++)
560          bandLogE[i+c*m->nbEBands] =
561                celt_log2(SHL32(bandE[i+c*m->nbEBands],2))
562                - SHL16((celt_word16)eMeans[i],6);
563       for (i=effEnd;i<end;i++)
564          bandLogE[c*m->nbEBands+i] = -QCONST16(14.f,DB_SHIFT);
565    } while (++c < C);
566 }