056d67aae8063f548bf300bf2261ae710e768e11
[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 /* Defining 25 critical bands for the full 0-20 kHz audio bandwidth
86    Taken from http://ccrma.stanford.edu/~jos/bbt/Bark_Frequency_Scale.html */
87 #define BARK_BANDS 25
88 static const celt_int16_t bark_freq[BARK_BANDS+1] = {
89       0,   100,   200,   300,   400,
90     510,   630,   770,   920,  1080,
91    1270,  1480,  1720,  2000,  2320,
92    2700,  3150,  3700,  4400,  5300,
93    6400,  7700,  9500, 12000, 15500,
94   20000};
95
96 /* This allocation table is per critical band. When creating a mode, the bits get added together 
97    into the codec bands, which are sometimes larger than one critical band at low frequency */
98
99 #ifdef STDIN_TUNING
100 int BITALLOC_SIZE;
101 int *band_allocation;
102 #else
103 #define BITALLOC_SIZE 12
104 static const int band_allocation[BARK_BANDS*BITALLOC_SIZE] = 
105    /* 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  */
106    {  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*/
107       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*/
108       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*/
109       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*/
110       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*/
111       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*/
112       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*/
113       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*/
114       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*/
115       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*/
116       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*/
117       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*/
118    };
119 #endif
120
121 static celt_int16_t *compute_ebands(celt_int32_t Fs, int frame_size, int nbShortMdcts, int *nbEBands)
122 {
123    int min_bins = 3;
124    celt_int16_t *eBands;
125    int i, res, min_width, lin, low, high, nBark, offset=0;
126
127    /*if (min_bins < nbShortMdcts)
128       min_bins = nbShortMdcts;*/
129    res = (Fs+frame_size)/(2*frame_size);
130    min_width = min_bins*res;
131
132    /* Find the number of critical bands supported by our sampling rate */
133    for (nBark=1;nBark<BARK_BANDS;nBark++)
134     if (bark_freq[nBark+1]*2 >= Fs)
135        break;
136
137    /* Find where the linear part ends (i.e. where the spacing is more than min_width */
138    for (lin=0;lin<nBark;lin++)
139       if (bark_freq[lin+1]-bark_freq[lin] >= min_width)
140          break;
141    
142    low = ((bark_freq[lin]/res)+(min_bins-1))/min_bins;
143    high = nBark-lin;
144    *nbEBands = low+high;
145    eBands = celt_alloc(sizeof(celt_int16_t)*(*nbEBands+2));
146    
147    if (eBands==NULL)
148       return NULL;
149    
150    /* Linear spacing (min_width) */
151    for (i=0;i<low;i++)
152       eBands[i] = min_bins*i;
153    /* Spacing follows critical bands */
154    for (i=0;i<high;i++)
155    {
156       int target = bark_freq[lin+i];
157       eBands[i+low] = (2*target+offset+res)/(2*res);
158       offset = eBands[i+low]*res - target;
159    }
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;
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] -= (2*eBands[i]-eBands[i-1]-eBands[i+1]+1)/2;
173       }
174    }
175    /*for (i=0;i<*nbEBands+1;i++)
176       printf ("%d ", eBands[i]);
177    printf ("\n");
178    exit(1);*/
179    /* FIXME: Remove last band if too small */
180    return eBands;
181 }
182
183 static void compute_allocation_table(CELTMode *mode, int res)
184 {
185    int i, j, nBark;
186    celt_int16_t *allocVectors;
187
188    /* Find the number of critical bands supported by our sampling rate */
189    for (nBark=1;nBark<BARK_BANDS;nBark++)
190     if (bark_freq[nBark+1]*2 >= mode->Fs)
191        break;
192
193    mode->nbAllocVectors = BITALLOC_SIZE;
194    allocVectors = celt_alloc(sizeof(celt_int16_t)*(BITALLOC_SIZE*mode->nbEBands));
195    if (allocVectors==NULL)
196       return;
197    /* Compute per-codec-band allocation from per-critical-band matrix */
198    for (i=0;i<BITALLOC_SIZE;i++)
199    {
200       celt_int32_t current = 0;
201       int eband = 0;
202       for (j=0;j<nBark;j++)
203       {
204          int edge, low;
205          celt_int32_t alloc;
206          edge = mode->eBands[eband+1]*res;
207          alloc = mode->mdctSize*band_allocation[i*BARK_BANDS+j];
208          if (edge < bark_freq[j+1])
209          {
210             int num, den;
211             num = alloc * (edge-bark_freq[j]);
212             den = bark_freq[j+1]-bark_freq[j];
213             low = (num+den/2)/den;
214             allocVectors[i*mode->nbEBands+eband] = (current+low+128)/256;
215             current=0;
216             eband++;
217             current += alloc-low;
218          } else {
219             current += alloc;
220          }   
221       }
222       allocVectors[i*mode->nbEBands+eband] = (current+128)/256;
223    }
224    mode->allocVectors = allocVectors;
225 }
226
227 #endif /* STATIC_MODES */
228
229 CELTMode *celt_mode_create(celt_int32_t Fs, int channels, int frame_size, int *error)
230 {
231    int i;
232 #ifdef STDIN_TUNING
233    scanf("%d ", &MIN_BINS);
234    scanf("%d ", &BITALLOC_SIZE);
235    band_allocation = celt_alloc(sizeof(int)*BARK_BANDS*BITALLOC_SIZE);
236    for (i=0;i<BARK_BANDS*BITALLOC_SIZE;i++)
237    {
238       scanf("%d ", band_allocation+i);
239    }
240 #endif
241 #ifdef STATIC_MODES
242    const CELTMode *m = NULL;
243    CELTMode *mode=NULL;
244    ALLOC_STACK;
245 #if !defined(VAR_ARRAYS) && !defined(USE_ALLOCA)
246    if (global_stack==NULL)
247    {
248       celt_free(global_stack);
249       goto failure;
250    }
251 #endif 
252    for (i=0;i<TOTAL_MODES;i++)
253    {
254       if (Fs == static_mode_list[i]->Fs &&
255           channels == static_mode_list[i]->nbChannels &&
256           frame_size == static_mode_list[i]->mdctSize)
257       {
258          m = static_mode_list[i];
259          break;
260       }
261    }
262    if (m == NULL)
263    {
264       celt_warning("Mode not included as part of the static modes");
265       if (error)
266          *error = CELT_BAD_ARG;
267       return NULL;
268    }
269    mode = (CELTMode*)celt_alloc(sizeof(CELTMode));
270    if (mode==NULL)
271       goto failure;
272    CELT_COPY(mode, m, 1);
273    mode->marker_start = MODEPARTIAL;
274 #else
275    int res;
276    CELTMode *mode=NULL;
277    celt_word16_t *window;
278    ALLOC_STACK;
279 #if !defined(VAR_ARRAYS) && !defined(USE_ALLOCA)
280    if (global_stack==NULL)
281    {
282       celt_free(global_stack);
283       goto failure;
284    }
285 #endif 
286
287    /* The good thing here is that permutation of the arguments will automatically be invalid */
288    
289    if (Fs < 32000 || Fs > 96000)
290    {
291       celt_warning("Sampling rate must be between 32 kHz and 96 kHz");
292       if (error)
293          *error = CELT_BAD_ARG;
294       return NULL;
295    }
296    if (channels < 0 || channels > 2)
297    {
298       celt_warning("Only mono and stereo supported");
299       if (error)
300          *error = CELT_BAD_ARG;
301       return NULL;
302    }
303    if (frame_size < 64 || frame_size > 1024 || frame_size%2!=0)
304    {
305       celt_warning("Only even frame sizes from 64 to 1024 are supported");
306       if (error)
307          *error = CELT_BAD_ARG;
308       return NULL;
309    }
310    res = (Fs+frame_size)/(2*frame_size);
311    
312    mode = celt_alloc(sizeof(CELTMode));
313    if (mode==NULL)
314       goto failure;
315    mode->marker_start = MODEPARTIAL;
316    mode->Fs = Fs;
317    mode->mdctSize = frame_size;
318    mode->nbChannels = channels;
319    mode->ePredCoef = QCONST16(.8f,15);
320
321    if (frame_size > 640 && (frame_size%16)==0)
322    {
323      mode->nbShortMdcts = 8;
324    } else if (frame_size > 384 && (frame_size%8)==0)
325    {
326      mode->nbShortMdcts = 4;
327    } else if (frame_size > 384 && (frame_size%10)==0)
328    {
329      mode->nbShortMdcts = 5;
330    } else if (frame_size > 256 && (frame_size%6)==0)
331    {
332      mode->nbShortMdcts = 3;
333    } else if (frame_size > 256 && (frame_size%8)==0)
334    {
335      mode->nbShortMdcts = 4;
336    } else if (frame_size > 64 && (frame_size%4)==0)
337    {
338      mode->nbShortMdcts = 2;
339    } else if (frame_size > 128 && (frame_size%6)==0)
340    {
341      mode->nbShortMdcts = 3;
342    } else
343    {
344      mode->nbShortMdcts = 1;
345    }
346
347    mode->eBands = compute_ebands(Fs, frame_size, mode->nbShortMdcts, &mode->nbEBands);
348    if (mode->eBands==NULL)
349       goto failure;
350
351    mode->pitchEnd = 4000*(celt_int32_t)frame_size/Fs;
352    
353    /* Overlap must be divisible by 4 */
354    if (mode->nbShortMdcts > 1)
355       mode->overlap = ((frame_size/mode->nbShortMdcts)>>2)<<2; 
356    else
357       mode->overlap = (frame_size>>3)<<2;
358
359    compute_allocation_table(mode, res);
360    if (mode->allocVectors==NULL)
361       goto failure;
362    
363    window = (celt_word16_t*)celt_alloc(mode->overlap*sizeof(celt_word16_t));
364    if (window==NULL)
365       goto failure;
366
367 #ifndef FIXED_POINT
368    for (i=0;i<mode->overlap;i++)
369       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
370 #else
371    for (i=0;i<mode->overlap;i++)
372       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)));
373 #endif
374    mode->window = window;
375
376    mode->bits = (const celt_int16_t **)compute_alloc_cache(mode, 1);
377    if (mode->bits==NULL)
378       goto failure;
379
380 #ifndef SHORTCUTS
381    psydecay_init(&mode->psy, MAX_PERIOD/2, mode->Fs);
382    if (mode->psy.decayR==NULL)
383       goto failure;
384 #endif
385    
386 #endif /* !STATIC_MODES */
387
388 #ifdef DISABLE_STEREO
389    if (channels > 1)
390    {
391       celt_warning("Stereo support was disable from this build");
392       if (error)
393          *error = CELT_BAD_ARG;
394       return NULL;
395    }
396 #endif
397
398    mdct_init(&mode->mdct, 2*mode->mdctSize);
399    mode->fft = pitch_state_alloc(MAX_PERIOD);
400
401    mode->shortMdctSize = mode->mdctSize/mode->nbShortMdcts;
402    mdct_init(&mode->shortMdct, 2*mode->shortMdctSize);
403    mode->shortWindow = mode->window;
404    mode->prob = quant_prob_alloc(mode);
405    if ((mode->mdct.trig==NULL) || (mode->shortMdct.trig==NULL)
406 #ifndef ENABLE_TI_DSPLIB55
407         || (mode->mdct.kfft==NULL) || (mode->fft==NULL) || (mode->shortMdct.kfft==NULL)
408 #endif
409         || (mode->prob==NULL))
410      goto failure;
411
412    mode->marker_start = MODEVALID;
413    mode->marker_end   = MODEVALID;
414    if (error)
415       *error = CELT_OK;
416    return mode;
417 failure: 
418    if (error)
419       *error = CELT_INVALID_MODE;
420    if (mode!=NULL)
421       celt_mode_destroy(mode);
422    return NULL;
423 }
424
425 void celt_mode_destroy(CELTMode *mode)
426 {
427    int i;
428    const celt_int16_t *prevPtr = NULL;
429    if (mode == NULL)
430    {
431       celt_warning("NULL passed to celt_mode_destroy");
432       return;
433    }
434
435    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
436    {
437       celt_warning("Freeing a mode which has already been freed"); 
438       return;
439    }
440
441    if (mode->marker_start != MODEVALID && mode->marker_start != MODEPARTIAL)
442    {
443       celt_warning("This is not a valid CELT mode structure");
444       return;  
445    }
446    mode->marker_start = MODEFREED;
447 #ifndef STATIC_MODES
448    if (mode->bits!=NULL)
449    {
450       for (i=0;i<mode->nbEBands;i++)
451       {
452          if (mode->bits[i] != prevPtr)
453          {
454             prevPtr = mode->bits[i];
455             celt_free((int*)mode->bits[i]);
456           }
457       }
458    }   
459    celt_free((int**)mode->bits);
460    celt_free((int*)mode->eBands);
461    celt_free((int*)mode->allocVectors);
462    
463    celt_free((celt_word16_t*)mode->window);
464
465 #ifndef SHORTCUTS
466    psydecay_clear(&mode->psy);
467 #endif
468 #endif
469    mdct_clear(&mode->mdct);
470    mdct_clear(&mode->shortMdct);
471    pitch_state_free(mode->fft);
472    quant_prob_free(mode->prob);
473    mode->marker_end = MODEFREED;
474    celt_free((CELTMode *)mode);
475 }
476
477 int check_mode(const CELTMode *mode)
478 {
479    if (mode==NULL)
480       return CELT_INVALID_MODE;
481    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
482       return CELT_OK;
483    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
484       celt_warning("Using a mode that has already been freed");
485    else
486       celt_warning("This is not a valid CELT mode");
487    return CELT_INVALID_MODE;
488 }