Re-introducing the successive rotations as a way to control low-bitrate
[opus.git] / libcelt / modes.c
1 /* (C) 2007-2009 Jean-Marc Valin, CSIRO
2    (C) 2008 Gregory Maxwell */
3 /*
4    Redistribution and use in source and binary forms, with or without
5    modification, are permitted provided that the following conditions
6    are met:
7    
8    - Redistributions of source code must retain the above copyright
9    notice, this list of conditions and the following disclaimer.
10    
11    - Redistributions in binary form must reproduce the above copyright
12    notice, this list of conditions and the following disclaimer in the
13    documentation and/or other materials provided with the distribution.
14    
15    - Neither the name of the Xiph.org Foundation nor the names of its
16    contributors may be used to endorse or promote products derived from
17    this software without specific prior written permission.
18    
19    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22    A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
23    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
24    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
25    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
26    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
27    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
28    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
29    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 #ifdef HAVE_CONFIG_H
33 #include "config.h"
34 #endif
35
36 #include "celt.h"
37 #include "modes.h"
38 #include "rate.h"
39 #include "os_support.h"
40 #include "stack_alloc.h"
41 #include "quant_bands.h"
42
43 #ifdef STATIC_MODES
44 #include "static_modes.c"
45 #endif
46
47 #define MODEVALID   0xa110ca7e
48 #define MODEPARTIAL 0x7eca10a1
49 #define MODEFREED   0xb10cf8ee
50
51 #ifndef M_PI
52 #define M_PI 3.141592653
53 #endif
54
55
56 int celt_mode_info(const CELTMode *mode, int request, celt_int32_t *value)
57 {
58    if (check_mode(mode) != CELT_OK)
59       return CELT_INVALID_MODE;
60    switch (request)
61    {
62       case CELT_GET_FRAME_SIZE:
63          *value = mode->mdctSize;
64          break;
65       case CELT_GET_LOOKAHEAD:
66          *value = mode->overlap;
67          break;
68       case CELT_GET_NB_CHANNELS:
69          *value = mode->nbChannels;
70          break;
71       case CELT_GET_BITSTREAM_VERSION:
72          *value = CELT_BITSTREAM_VERSION;
73          break;
74       case CELT_GET_SAMPLE_RATE:
75          *value = mode->Fs;
76          break;
77       default:
78          return CELT_UNIMPLEMENTED;
79    }
80    return CELT_OK;
81 }
82
83 #ifndef STATIC_MODES
84
85 #define PBANDS 8
86
87 /* Defining 25 critical bands for the full 0-20 kHz audio bandwidth
88    Taken from http://ccrma.stanford.edu/~jos/bbt/Bark_Frequency_Scale.html */
89 #define BARK_BANDS 25
90 static const celt_int16_t bark_freq[BARK_BANDS+1] = {
91       0,   100,   200,   300,   400,
92     510,   630,   770,   920,  1080,
93    1270,  1480,  1720,  2000,  2320,
94    2700,  3150,  3700,  4400,  5300,
95    6400,  7700,  9500, 12000, 15500,
96   20000};
97
98 static const celt_int16_t pitch_freq[PBANDS+1] ={0, 345, 689, 1034, 1378, 2067, 3273, 5340, 6374};
99
100 /* This allocation table is per critical band. When creating a mode, the bits get added together 
101    into the codec bands, which are sometimes larger than one critical band at low frequency */
102
103 #ifdef STDIN_TUNING
104 int BITALLOC_SIZE;
105 int *band_allocation;
106 #else
107 #define BITALLOC_SIZE 12
108 static const int band_allocation[BARK_BANDS*BITALLOC_SIZE] = 
109    /* 0 100 200 300 400 510 630 770 920 1k  1.2 1.5 1.7 2k  2.3 2.7 3.1 3.7 4.4 5.3 6.4 7.7 9.5 12k 15k  */
110    {  4,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /*0*/
111       2,  2,  1,  1,  2,  2,  1,  1,  1,  1,  1,  1,  1,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, /*1*/
112       2,  2,  2,  1,  2,  2,  2,  2,  2,  2,  2,  2,  4,  5,  7,  7,  7,  5,  4,  0,  0,  0,  0,  0,  0, /*2*/
113       2,  2,  2,  2,  3,  3,  3,  3,  3,  3,  3,  3,  5,  6,  8,  8,  8,  6,  5,  4,  0,  0,  0,  0,  0, /*3*/
114       3,  2,  2,  2,  3,  4,  4,  4,  4,  4,  4,  4,  6,  7,  9,  9,  9,  7,  6,  5,  5,  5,  0,  0,  0, /*4*/
115       3,  3,  3,  4,  4,  5,  6,  6,  6,  6,  6,  7,  7,  9, 10, 10, 10,  9,  6,  5,  5,  5,  5,  1,  0, /*5*/
116       4,  3,  3,  4,  6,  7,  7,  7,  7,  7,  8,  9,  9,  9, 11, 10, 10,  9,  9,  8, 11, 10, 10,  1,  0, /*6*/
117       5,  5,  5,  6,  7,  7,  7,  7,  8,  8,  9, 10, 10, 12, 12, 11, 11, 17, 12, 15, 15, 20, 18, 10,  1, /*7*/
118       6,  7,  7,  7,  8,  8,  8,  8,  9, 10, 11, 12, 14, 17, 18, 21, 22, 27, 29, 39, 37, 38, 40, 35,  1, /*8*/
119       7,  7,  7,  8,  8,  8, 10, 10, 10, 13, 14, 18, 20, 24, 28, 32, 32, 35, 38, 38, 42, 50, 59, 54, 31, /*9*/
120       8,  8,  8,  8,  8,  9, 10, 12, 14, 20, 22, 25, 28, 30, 35, 42, 46, 50, 55, 60, 62, 62, 72, 82, 62, /*10*/
121       9,  9,  9, 10, 12, 13, 15, 18, 22, 30, 32, 35, 40, 45, 55, 62, 66, 70, 85, 90, 92, 92, 92,102, 92, /*11*/
122    };
123 #endif
124
125 static celt_int16_t *compute_ebands(celt_int32_t Fs, int frame_size, int nbShortMdcts, int *nbEBands)
126 {
127    int min_bins = 2;
128    celt_int16_t *eBands;
129    int i, res, min_width, lin, low, high, nBark;
130
131    if (min_bins < nbShortMdcts)
132       min_bins = nbShortMdcts;
133    res = (Fs+frame_size)/(2*frame_size);
134    min_width = min_bins*res;
135
136    /* Find the number of critical bands supported by our sampling rate */
137    for (nBark=1;nBark<BARK_BANDS;nBark++)
138     if (bark_freq[nBark+1]*2 >= Fs)
139        break;
140
141    /* Find where the linear part ends (i.e. where the spacing is more than min_width */
142    for (lin=0;lin<nBark;lin++)
143       if (bark_freq[lin+1]-bark_freq[lin] >= min_width)
144          break;
145    
146    low = ((bark_freq[lin]/res)+(min_bins-1))/min_bins;
147    high = nBark-lin;
148    *nbEBands = low+high;
149    eBands = celt_alloc(sizeof(celt_int16_t)*(*nbEBands+2));
150    
151    if (eBands==NULL)
152       return NULL;
153    
154    /* Linear spacing (min_width) */
155    for (i=0;i<low;i++)
156       eBands[i] = min_bins*i;
157    /* Spacing follows critical bands */
158    for (i=0;i<high;i++)
159       eBands[i+low] = (bark_freq[lin+i]+res/2)/res/nbShortMdcts*nbShortMdcts;
160    /* Enforce the minimum spacing at the boundary */
161    for (i=0;i<*nbEBands;i++)
162       if (eBands[i] < min_bins*i)
163          eBands[i] = min_bins*i;
164    eBands[*nbEBands] = (bark_freq[nBark]+res/2)/res/nbShortMdcts*nbShortMdcts;
165    eBands[*nbEBands+1] = frame_size;
166    if (eBands[*nbEBands] > eBands[*nbEBands+1])
167       eBands[*nbEBands] = eBands[*nbEBands+1];
168    for (i=1;i<*nbEBands-1;i++)
169    {
170       if (eBands[i+1]-eBands[i] < eBands[i]-eBands[i-1])
171       {
172          eBands[i] -= min_bins;
173       }
174    }
175    /*for (i=0;i<*nbEBands+1;i++)
176       printf ("%d ", eBands[i]);
177    printf ("\n");*/
178    /* FIXME: Remove last band if too small */
179    return eBands;
180 }
181
182 static void compute_pbands(CELTMode *mode, int res)
183 {
184    int i;
185    celt_int16_t *pBands;
186    pBands=celt_alloc(sizeof(celt_int16_t)*(PBANDS+2));
187    mode->pBands = pBands;
188    if (pBands==NULL)
189      return;
190    mode->nbPBands = PBANDS;
191    for (i=0;i<PBANDS+1;i++)
192    {
193       pBands[i] = (pitch_freq[i]+res/2)/res;
194       if (pBands[i] < mode->eBands[i])
195          pBands[i] = mode->eBands[i];
196    }
197    pBands[PBANDS+1] = mode->eBands[mode->nbEBands+1];
198    for (i=1;i<mode->nbPBands+1;i++)
199    {
200       int j;
201       for (j=0;j<mode->nbEBands;j++)
202          if (mode->eBands[j] <= pBands[i] && mode->eBands[j+1] > pBands[i])
203             break;
204       if (mode->eBands[j] != pBands[i])
205       {
206          if (pBands[i]-mode->eBands[j] < mode->eBands[j+1]-pBands[i] && 
207              mode->eBands[j] != pBands[i-1])
208             pBands[i] = mode->eBands[j];
209          else
210             pBands[i] = mode->eBands[j+1];
211       }
212    }
213    mode->pitchEnd = pBands[PBANDS];
214 }
215
216 static void compute_allocation_table(CELTMode *mode, int res)
217 {
218    int i, j, nBark;
219    celt_int16_t *allocVectors;
220    const int C = CHANNELS(mode);
221
222    /* Find the number of critical bands supported by our sampling rate */
223    for (nBark=1;nBark<BARK_BANDS;nBark++)
224     if (bark_freq[nBark+1]*2 >= mode->Fs)
225        break;
226
227    mode->nbAllocVectors = BITALLOC_SIZE;
228    allocVectors = celt_alloc(sizeof(celt_int16_t)*(BITALLOC_SIZE*mode->nbEBands));
229    if (allocVectors==NULL)
230       return;
231    /* Compute per-codec-band allocation from per-critical-band matrix */
232    for (i=0;i<BITALLOC_SIZE;i++)
233    {
234       celt_int32_t current = 0;
235       int eband = 0;
236       for (j=0;j<nBark;j++)
237       {
238          int edge, low;
239          celt_int32_t alloc;
240          edge = mode->eBands[eband+1]*res;
241          alloc = band_allocation[i*BARK_BANDS+j];
242          alloc = alloc*C*mode->mdctSize;
243          if (edge < bark_freq[j+1])
244          {
245             int num, den;
246             num = alloc * (edge-bark_freq[j]);
247             den = bark_freq[j+1]-bark_freq[j];
248             low = (num+den/2)/den;
249             allocVectors[i*mode->nbEBands+eband] = (current+low+128)/256;
250             current=0;
251             eband++;
252             current += alloc-low;
253          } else {
254             current += alloc;
255          }   
256       }
257       allocVectors[i*mode->nbEBands+eband] = (current+128)/256;
258    }
259    mode->allocVectors = allocVectors;
260 }
261
262 #endif /* STATIC_MODES */
263
264 CELTMode *celt_mode_create(celt_int32_t Fs, int channels, int frame_size, int *error)
265 {
266    int i;
267 #ifdef STDIN_TUNING
268    scanf("%d ", &MIN_BINS);
269    scanf("%d ", &BITALLOC_SIZE);
270    band_allocation = celt_alloc(sizeof(int)*BARK_BANDS*BITALLOC_SIZE);
271    for (i=0;i<BARK_BANDS*BITALLOC_SIZE;i++)
272    {
273       scanf("%d ", band_allocation+i);
274    }
275 #endif
276 #ifdef STATIC_MODES
277    const CELTMode *m = NULL;
278    CELTMode *mode=NULL;
279    ALLOC_STACK;
280 #if !defined(VAR_ARRAYS) && !defined(USE_ALLOCA)
281    if (global_stack==NULL)
282    {
283       celt_free(global_stack);
284       goto failure;
285    }
286 #endif 
287    for (i=0;i<TOTAL_MODES;i++)
288    {
289       if (Fs == static_mode_list[i]->Fs &&
290           channels == static_mode_list[i]->nbChannels &&
291           frame_size == static_mode_list[i]->mdctSize)
292       {
293          m = static_mode_list[i];
294          break;
295       }
296    }
297    if (m == NULL)
298    {
299       celt_warning("Mode not included as part of the static modes");
300       if (error)
301          *error = CELT_BAD_ARG;
302       return NULL;
303    }
304    mode = (CELTMode*)celt_alloc(sizeof(CELTMode));
305    if (mode==NULL)
306       goto failure;
307    CELT_COPY(mode, m, 1);
308    mode->marker_start = MODEPARTIAL;
309 #else
310    int res;
311    CELTMode *mode=NULL;
312    celt_word16_t *window;
313    ALLOC_STACK;
314 #if !defined(VAR_ARRAYS) && !defined(USE_ALLOCA)
315    if (global_stack==NULL)
316    {
317       celt_free(global_stack);
318       goto failure;
319    }
320 #endif 
321
322    /* The good thing here is that permutation of the arguments will automatically be invalid */
323    
324    if (Fs < 32000 || Fs > 96000)
325    {
326       celt_warning("Sampling rate must be between 32 kHz and 96 kHz");
327       if (error)
328          *error = CELT_BAD_ARG;
329       return NULL;
330    }
331    if (channels < 0 || channels > 2)
332    {
333       celt_warning("Only mono and stereo supported");
334       if (error)
335          *error = CELT_BAD_ARG;
336       return NULL;
337    }
338    if (frame_size < 64 || frame_size > 1024 || frame_size%2!=0)
339    {
340       celt_warning("Only even frame sizes from 64 to 1024 are supported");
341       if (error)
342          *error = CELT_BAD_ARG;
343       return NULL;
344    }
345    res = (Fs+frame_size)/(2*frame_size);
346    
347    mode = celt_alloc(sizeof(CELTMode));
348    if (mode==NULL)
349       goto failure;
350    mode->marker_start = MODEPARTIAL;
351    mode->Fs = Fs;
352    mode->mdctSize = frame_size;
353    mode->nbChannels = channels;
354    mode->ePredCoef = QCONST16(.8f,15);
355
356    if (frame_size > 640 && (frame_size%16)==0)
357    {
358      mode->nbShortMdcts = 8;
359    } else if (frame_size > 384 && (frame_size%8)==0)
360    {
361      mode->nbShortMdcts = 4;
362    } else if (frame_size > 384 && (frame_size%10)==0)
363    {
364      mode->nbShortMdcts = 5;
365    } else if (frame_size > 256 && (frame_size%6)==0)
366    {
367      mode->nbShortMdcts = 3;
368    } else if (frame_size > 256 && (frame_size%8)==0)
369    {
370      mode->nbShortMdcts = 4;
371    } else if (frame_size > 64 && (frame_size%4)==0)
372    {
373      mode->nbShortMdcts = 2;
374    } else if (frame_size > 128 && (frame_size%6)==0)
375    {
376      mode->nbShortMdcts = 3;
377    } else
378    {
379      mode->nbShortMdcts = 1;
380    }
381
382    mode->eBands = compute_ebands(Fs, frame_size, mode->nbShortMdcts, &mode->nbEBands);
383    if (mode->eBands==NULL)
384       goto failure;
385    compute_pbands(mode, res);
386    if (mode->pBands==NULL)
387       goto failure;
388
389    /* Overlap must be divisible by 4 */
390    if (mode->nbShortMdcts > 1)
391       mode->overlap = ((frame_size/mode->nbShortMdcts)>>2)<<2; 
392    else
393       mode->overlap = (frame_size>>3)<<2;
394
395    compute_allocation_table(mode, res);
396    if (mode->allocVectors==NULL)
397       goto failure;
398    
399    window = (celt_word16_t*)celt_alloc(mode->overlap*sizeof(celt_word16_t));
400    if (window==NULL)
401       goto failure;
402
403 #ifndef FIXED_POINT
404    for (i=0;i<mode->overlap;i++)
405       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
406 #else
407    for (i=0;i<mode->overlap;i++)
408       window[i] = MIN32(32767,32768.*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap)));
409 #endif
410    mode->window = window;
411
412    mode->bits = (const celt_int16_t **)compute_alloc_cache(mode, 1);
413    if (mode->bits==NULL)
414       goto failure;
415
416 #ifndef SHORTCUTS
417    psydecay_init(&mode->psy, MAX_PERIOD/2, mode->Fs);
418    if (mode->psy.decayR==NULL)
419       goto failure;
420 #endif
421    
422 #endif /* !STATIC_MODES */
423
424 #ifdef DISABLE_STEREO
425    if (channels > 1)
426    {
427       celt_warning("Stereo support was disable from this build");
428       if (error)
429          *error = CELT_BAD_ARG;
430       return NULL;
431    }
432 #endif
433
434    mdct_init(&mode->mdct, 2*mode->mdctSize);
435    mode->fft = pitch_state_alloc(MAX_PERIOD);
436
437    mode->shortMdctSize = mode->mdctSize/mode->nbShortMdcts;
438    mdct_init(&mode->shortMdct, 2*mode->shortMdctSize);
439    mode->shortWindow = mode->window;
440    mode->prob = quant_prob_alloc(mode);
441    if ((mode->mdct.trig==NULL) || (mode->shortMdct.trig==NULL)
442 #ifndef ENABLE_TI_DSPLIB55
443         || (mode->mdct.kfft==NULL) || (mode->fft==NULL) || (mode->shortMdct.kfft==NULL)
444 #endif
445         || (mode->prob==NULL))
446      goto failure;
447
448    mode->marker_start = MODEVALID;
449    mode->marker_end   = MODEVALID;
450    if (error)
451       *error = CELT_OK;
452    return mode;
453 failure: 
454    if (error)
455       *error = CELT_INVALID_MODE;
456    if (mode!=NULL)
457       celt_mode_destroy(mode);
458    return NULL;
459 }
460
461 void celt_mode_destroy(CELTMode *mode)
462 {
463    int i;
464    const celt_int16_t *prevPtr = NULL;
465    if (mode == NULL)
466    {
467       celt_warning("NULL passed to celt_mode_destroy");
468       return;
469    }
470
471    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
472    {
473       celt_warning("Freeing a mode which has already been freed"); 
474       return;
475    }
476
477    if (mode->marker_start != MODEVALID && mode->marker_start != MODEPARTIAL)
478    {
479       celt_warning("This is not a valid CELT mode structure");
480       return;  
481    }
482    mode->marker_start = MODEFREED;
483 #ifndef STATIC_MODES
484    if (mode->bits!=NULL)
485    {
486       for (i=0;i<mode->nbEBands;i++)
487       {
488          if (mode->bits[i] != prevPtr)
489          {
490             prevPtr = mode->bits[i];
491             celt_free((int*)mode->bits[i]);
492           }
493       }
494    }   
495    celt_free((int**)mode->bits);
496    celt_free((int*)mode->eBands);
497    celt_free((int*)mode->pBands);
498    celt_free((int*)mode->allocVectors);
499    
500    celt_free((celt_word16_t*)mode->window);
501
502 #ifndef SHORTCUTS
503    psydecay_clear(&mode->psy);
504 #endif
505 #endif
506    mdct_clear(&mode->mdct);
507    mdct_clear(&mode->shortMdct);
508    pitch_state_free(mode->fft);
509    quant_prob_free(mode->prob);
510    mode->marker_end = MODEFREED;
511    celt_free((CELTMode *)mode);
512 }
513
514 int check_mode(const CELTMode *mode)
515 {
516    if (mode==NULL)
517       return CELT_INVALID_MODE;
518    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
519       return CELT_OK;
520    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
521       celt_warning("Using a mode that has already been freed");
522    else
523       celt_warning("This is not a valid CELT mode");
524    return CELT_INVALID_MODE;
525 }