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