removed useless comments
[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
138    /* Find the number of critical bands supported by our sampling rate */
139    for (nBark=1;nBark<BARK_BANDS;nBark++)
140     if (bark_freq[nBark+1]*2 >= Fs)
141        break;
142
143    /* Find where the linear part ends (i.e. where the spacing is more than min_width */
144    for (lin=0;lin<nBark;lin++)
145       if (bark_freq[lin+1]-bark_freq[lin] >= min_width)
146          break;
147    
148    low = ((bark_freq[lin]/res)+(MIN_BINS-1))/MIN_BINS;
149    high = nBark-lin;
150    *nbEBands = low+high;
151    eBands = celt_alloc(sizeof(celt_int16_t)*(*nbEBands+2));
152    
153    if (eBands==NULL)
154       return NULL;
155    
156    /* Linear spacing (min_width) */
157    for (i=0;i<low;i++)
158       eBands[i] = MIN_BINS*i;
159    /* Spacing follows critical bands */
160    for (i=0;i<high;i++)
161       eBands[i+low] = (bark_freq[lin+i]+res/2)/res;
162    /* Enforce the minimum spacing at the boundary */
163    for (i=0;i<*nbEBands;i++)
164       if (eBands[i] < MIN_BINS*i)
165          eBands[i] = MIN_BINS*i;
166    eBands[*nbEBands] = (bark_freq[nBark]+res/2)/res;
167    eBands[*nbEBands+1] = frame_size;
168    if (eBands[*nbEBands] > eBands[*nbEBands+1])
169       eBands[*nbEBands] = eBands[*nbEBands+1];
170    
171    /* FIXME: Remove last band if too small */
172    return eBands;
173 }
174
175 static void compute_pbands(CELTMode *mode, int res)
176 {
177    int i;
178    celt_int16_t *pBands;
179    pBands=celt_alloc(sizeof(celt_int16_t)*(PBANDS+2));
180    mode->pBands = pBands;
181    if (pBands==NULL)
182      return;
183    mode->nbPBands = PBANDS;
184    for (i=0;i<PBANDS+1;i++)
185    {
186       pBands[i] = (pitch_freq[i]+res/2)/res;
187       if (pBands[i] < mode->eBands[i])
188          pBands[i] = mode->eBands[i];
189    }
190    pBands[PBANDS+1] = mode->eBands[mode->nbEBands+1];
191    for (i=1;i<mode->nbPBands+1;i++)
192    {
193       int j;
194       for (j=0;j<mode->nbEBands;j++)
195          if (mode->eBands[j] <= pBands[i] && mode->eBands[j+1] > pBands[i])
196             break;
197       if (mode->eBands[j] != pBands[i])
198       {
199          if (pBands[i]-mode->eBands[j] < mode->eBands[j+1]-pBands[i] && 
200              mode->eBands[j] != pBands[i-1])
201             pBands[i] = mode->eBands[j];
202          else
203             pBands[i] = mode->eBands[j+1];
204       }
205    }
206    mode->pitchEnd = pBands[PBANDS];
207 }
208
209 static void compute_allocation_table(CELTMode *mode, int res)
210 {
211    int i, j, nBark;
212    celt_int16_t *allocVectors;
213    const int C = CHANNELS(mode);
214
215    /* Find the number of critical bands supported by our sampling rate */
216    for (nBark=1;nBark<BARK_BANDS;nBark++)
217     if (bark_freq[nBark+1]*2 >= mode->Fs)
218        break;
219
220    mode->nbAllocVectors = BITALLOC_SIZE;
221    allocVectors = celt_alloc(sizeof(celt_int16_t)*(BITALLOC_SIZE*mode->nbEBands));
222    if (allocVectors==NULL)
223       return;
224    /* Compute per-codec-band allocation from per-critical-band matrix */
225    for (i=0;i<BITALLOC_SIZE;i++)
226    {
227       celt_int32_t current = 0;
228       int eband = 0;
229       for (j=0;j<nBark;j++)
230       {
231          int edge, low;
232          celt_int32_t alloc;
233          edge = mode->eBands[eband+1]*res;
234          alloc = band_allocation[i*BARK_BANDS+j];
235          alloc = alloc*C*mode->mdctSize;
236          if (edge < bark_freq[j+1])
237          {
238             int num, den;
239             num = alloc * (edge-bark_freq[j]);
240             den = bark_freq[j+1]-bark_freq[j];
241             low = (num+den/2)/den;
242             allocVectors[i*mode->nbEBands+eband] = (current+low+128)/256;
243             current=0;
244             eband++;
245             current += alloc-low;
246          } else {
247             current += alloc;
248          }   
249       }
250       allocVectors[i*mode->nbEBands+eband] = (current+128)/256;
251    }
252    mode->allocVectors = allocVectors;
253 }
254
255 #endif /* STATIC_MODES */
256
257 CELTMode *celt_mode_create(celt_int32_t Fs, int channels, int frame_size, int *error)
258 {
259    int i;
260 #ifdef STDIN_TUNING
261    scanf("%d ", &MIN_BINS);
262    scanf("%d ", &BITALLOC_SIZE);
263    band_allocation = celt_alloc(sizeof(int)*BARK_BANDS*BITALLOC_SIZE);
264    for (i=0;i<BARK_BANDS*BITALLOC_SIZE;i++)
265    {
266       scanf("%d ", band_allocation+i);
267    }
268 #endif
269 #ifdef STATIC_MODES
270    const CELTMode *m = NULL;
271    CELTMode *mode=NULL;
272    ALLOC_STACK;
273 #if !defined(VAR_ARRAYS) && !defined(USE_ALLOCA)
274    if (global_stack==NULL)
275    {
276       celt_free(global_stack);
277       goto failure;
278    }
279 #endif 
280    for (i=0;i<TOTAL_MODES;i++)
281    {
282       if (Fs == static_mode_list[i]->Fs &&
283           channels == static_mode_list[i]->nbChannels &&
284           frame_size == static_mode_list[i]->mdctSize)
285       {
286          m = static_mode_list[i];
287          break;
288       }
289    }
290    if (m == NULL)
291    {
292       celt_warning("Mode not included as part of the static modes");
293       if (error)
294          *error = CELT_BAD_ARG;
295       return NULL;
296    }
297    mode = (CELTMode*)celt_alloc(sizeof(CELTMode));
298    if (mode==NULL)
299       goto failure;
300    CELT_COPY(mode, m, 1);
301    mode->marker_start = MODEPARTIAL;
302 #else
303    int res;
304    CELTMode *mode=NULL;
305    celt_word16_t *window;
306    ALLOC_STACK;
307 #if !defined(VAR_ARRAYS) && !defined(USE_ALLOCA)
308    if (global_stack==NULL)
309    {
310       celt_free(global_stack);
311       goto failure;
312    }
313 #endif 
314
315    /* The good thing here is that permutation of the arguments will automatically be invalid */
316    
317    if (Fs < 32000 || Fs > 96000)
318    {
319       celt_warning("Sampling rate must be between 32 kHz and 96 kHz");
320       if (error)
321          *error = CELT_BAD_ARG;
322       return NULL;
323    }
324    if (channels < 0 || channels > 2)
325    {
326       celt_warning("Only mono and stereo supported");
327       if (error)
328          *error = CELT_BAD_ARG;
329       return NULL;
330    }
331    if (frame_size < 64 || frame_size > 512 || frame_size%2!=0)
332    {
333       celt_warning("Only even frame sizes from 64 to 512 are supported");
334       if (error)
335          *error = CELT_BAD_ARG;
336       return NULL;
337    }
338    res = (Fs+frame_size)/(2*frame_size);
339    
340    mode = celt_alloc(sizeof(CELTMode));
341    if (mode==NULL)
342       goto failure;
343    mode->marker_start = MODEPARTIAL;
344    mode->Fs = Fs;
345    mode->mdctSize = frame_size;
346    mode->nbChannels = channels;
347    mode->eBands = compute_ebands(Fs, frame_size, &mode->nbEBands);
348    if (mode->eBands==NULL)
349       goto failure;
350    compute_pbands(mode, res);
351    if (mode->pBands==NULL)
352       goto failure;
353    mode->ePredCoef = QCONST16(.8f,15);
354
355    if (frame_size > 384 && (frame_size%8)==0)
356    {
357      mode->nbShortMdcts = 4;
358    } else if (frame_size > 384 && (frame_size%10)==0)
359    {
360      mode->nbShortMdcts = 5;
361    } else if (frame_size > 256 && (frame_size%6)==0)
362    {
363      mode->nbShortMdcts = 3;
364    } else if (frame_size > 256 && (frame_size%8)==0)
365    {
366      mode->nbShortMdcts = 4;
367    } else if (frame_size > 64 && (frame_size%4)==0)
368    {
369      mode->nbShortMdcts = 2;
370    } else if (frame_size > 128 && (frame_size%6)==0)
371    {
372      mode->nbShortMdcts = 3;
373    } else
374    {
375      mode->nbShortMdcts = 1;
376    }
377
378    /* Overlap must be divisible by 4 */
379    if (mode->nbShortMdcts > 1)
380       mode->overlap = ((frame_size/mode->nbShortMdcts)>>2)<<2; 
381    else
382       mode->overlap = (frame_size>>3)<<2;
383
384    compute_allocation_table(mode, res);
385    if (mode->allocVectors==NULL)
386       goto failure;
387    
388    window = (celt_word16_t*)celt_alloc(mode->overlap*sizeof(celt_word16_t));
389    if (window==NULL)
390       goto failure;
391
392 #ifndef FIXED_POINT
393    for (i=0;i<mode->overlap;i++)
394       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
395 #else
396    for (i=0;i<mode->overlap;i++)
397       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)));
398 #endif
399    mode->window = window;
400
401    mode->bits = (const celt_int16_t **)compute_alloc_cache(mode, 1);
402    if (mode->bits==NULL)
403       goto failure;
404
405 #ifndef SHORTCUTS
406    psydecay_init(&mode->psy, MAX_PERIOD/2, mode->Fs);
407    if (mode->psy.decayR==NULL)
408       goto failure;
409 #endif
410    
411 #endif /* !STATIC_MODES */
412
413 #ifdef DISABLE_STEREO
414    if (channels > 1)
415    {
416       celt_warning("Stereo support was disable from this build");
417       if (error)
418          *error = CELT_BAD_ARG;
419       return NULL;
420    }
421 #endif
422
423    mdct_init(&mode->mdct, 2*mode->mdctSize);
424    mode->fft = pitch_state_alloc(MAX_PERIOD);
425
426    mode->shortMdctSize = mode->mdctSize/mode->nbShortMdcts;
427    mdct_init(&mode->shortMdct, 2*mode->shortMdctSize);
428    mode->shortWindow = mode->window;
429    mode->prob = quant_prob_alloc(mode);
430    if ((mode->mdct.trig==NULL) || (mode->mdct.kfft==NULL) || (mode->fft==NULL) ||
431        (mode->shortMdct.trig==NULL) || (mode->shortMdct.kfft==NULL) || (mode->prob==NULL))
432      goto failure;
433
434    mode->marker_start = MODEVALID;
435    mode->marker_end   = MODEVALID;
436    if (error)
437       *error = CELT_OK;
438    return mode;
439 failure: 
440    if (error)
441       *error = CELT_INVALID_MODE;
442    if (mode!=NULL)
443       celt_mode_destroy(mode);
444    return NULL;
445 }
446
447 void celt_mode_destroy(CELTMode *mode)
448 {
449    int i;
450    const celt_int16_t *prevPtr = NULL;
451    if (mode == NULL)
452    {
453       celt_warning("NULL passed to celt_mode_destroy");
454       return;
455    }
456
457    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
458    {
459       celt_warning("Freeing a mode which has already been freed"); 
460       return;
461    }
462
463    if (mode->marker_start != MODEVALID && mode->marker_start != MODEPARTIAL)
464    {
465       celt_warning("This is not a valid CELT mode structure");
466       return;  
467    }
468    mode->marker_start = MODEFREED;
469 #ifndef STATIC_MODES
470    if (mode->bits!=NULL)
471    {
472       for (i=0;i<mode->nbEBands;i++)
473       {
474          if (mode->bits[i] != prevPtr)
475          {
476             prevPtr = mode->bits[i];
477             celt_free((int*)mode->bits[i]);
478           }
479       }
480    }   
481    celt_free((int**)mode->bits);
482    celt_free((int*)mode->eBands);
483    celt_free((int*)mode->pBands);
484    celt_free((int*)mode->allocVectors);
485    
486    celt_free((celt_word16_t*)mode->window);
487
488 #ifndef SHORTCUTS
489    psydecay_clear(&mode->psy);
490 #endif
491 #endif
492    mdct_clear(&mode->mdct);
493    mdct_clear(&mode->shortMdct);
494    pitch_state_free(mode->fft);
495    quant_prob_free(mode->prob);
496    mode->marker_end = MODEFREED;
497    celt_free((CELTMode *)mode);
498 }
499
500 int check_mode(const CELTMode *mode)
501 {
502    if (mode==NULL)
503       return CELT_INVALID_MODE;
504    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
505       return CELT_OK;
506    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
507       celt_warning("Using a mode that has already been freed");
508    else
509       celt_warning("This is not a valid CELT mode");
510    return CELT_INVALID_MODE;
511 }