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