Completely removed the old allocation table.
[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_LOOKAHEAD:
65          *value = mode->overlap;
66          break;
67       case CELT_GET_BITSTREAM_VERSION:
68          *value = CELT_BITSTREAM_VERSION;
69          break;
70       case CELT_GET_SAMPLE_RATE:
71          *value = mode->Fs;
72          break;
73       default:
74          return CELT_UNIMPLEMENTED;
75    }
76    return CELT_OK;
77 }
78
79 #ifndef STATIC_MODES
80
81 /* Defining 25 critical bands for the full 0-20 kHz audio bandwidth
82    Taken from http://ccrma.stanford.edu/~jos/bbt/Bark_Frequency_Scale.html */
83 #define BARK_BANDS 25
84 static const celt_int16 bark_freq[BARK_BANDS+1] = {
85       0,   100,   200,   300,   400,
86     510,   630,   770,   920,  1080,
87    1270,  1480,  1720,  2000,  2320,
88    2700,  3150,  3700,  4400,  5300,
89    6400,  7700,  9500, 12000, 15500,
90   20000};
91
92 /* This allocation table is per critical band. When creating a mode, the bits get added together 
93    into the codec bands, which are sometimes larger than one critical band at low frequency */
94
95 #define BITALLOC_SIZE 12
96
97 static const celt_int16 eband5ms[] = {
98        0,  1,  2,  3,  4,  5,  6,  7,  8, 10, 12, 14, 16, 20, 24, 28, 34, 40, 48, 60, 78, 100
99 };
100
101 static const unsigned char alloc_5ms[] = {
102       10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
103       10,  3,  8,  2,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
104       10,  6,  8,  6,  5,  4,  3,  2,  7, 10, 11,  9,  7,  3,  1,  0,  0,  0,  0,  0,  0,
105       10, 10, 14, 11, 10,  8,  6,  5, 10, 12, 13, 11,  8,  4,  2,  1,  0,  0,  0,  0,  0,
106       13, 10, 17, 16, 14, 12, 10,  8, 12, 14, 14, 12,  9,  5,  3,  2,  2,  1,  0,  0,  0,
107       17, 21, 23, 26, 24, 20, 17, 16, 17, 18, 16, 14, 11,  6,  3,  2,  2,  1,  1,  0,  0,
108       21, 21, 36, 32, 28, 24, 23, 23, 22, 18, 18, 14, 11,  7,  5,  5,  5,  3,  3,  0,  0,
109       31, 35, 40, 32, 30, 28, 26, 26, 25, 24, 19, 15, 15, 13,  9,  9,  8,  7,  5,  2,  0,
110       42, 46, 46, 37, 35, 34, 33, 32, 34, 35, 32, 31, 27, 24, 23, 23, 18, 14, 11,  7,  0,
111       46, 49, 46, 46, 42, 43, 44, 47, 50, 52, 51, 48, 39, 32, 27, 24, 22, 19, 17, 11,  5,
112       53, 53, 49, 48, 55, 66, 71, 71, 71, 65, 64, 64, 56, 47, 41, 37, 31, 24, 20, 16, 10,
113       60, 64, 74, 74, 87,103,106,102,101,100,101, 95, 80, 69, 63, 55, 47, 36, 26, 21, 15,
114 };
115
116 static celt_int16 *compute_ebands(celt_int32 Fs, int frame_size, int res, int *nbEBands)
117 {
118    celt_int16 *eBands;
119    int i, lin, low, high, nBark, offset=0;
120
121    if (Fs == 400*(celt_int32)frame_size && Fs >= 40000)
122    {
123       *nbEBands = sizeof(eband5ms)/sizeof(eband5ms[0])-1;
124       eBands = celt_alloc(sizeof(celt_int16)*(*nbEBands+2));
125       for (i=0;i<*nbEBands+2;i++)
126          eBands[i] = eband5ms[i];
127       eBands[*nbEBands+1] = frame_size;
128       return eBands;
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] >= res)
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)
184 {
185    int i, j, nBark;
186    unsigned char *allocVectors;
187    int maxBands = sizeof(eband5ms)/sizeof(eband5ms[0])-1;
188
189    mode->nbAllocVectors = BITALLOC_SIZE;
190    allocVectors = celt_alloc(sizeof(unsigned char)*(BITALLOC_SIZE*mode->nbEBands));
191    if (allocVectors==NULL)
192       return;
193
194    /* Check for standard mode */
195    if (mode->Fs == 400*(celt_int32)mode->shortMdctSize && mode->Fs >= 40000)
196    {
197       for (i=0;i<BITALLOC_SIZE*mode->nbEBands;i++)
198          allocVectors[i] = alloc_5ms[i];
199       mode->allocVectors = allocVectors;
200       return;
201    }
202
203    /* If not the standard mode, interpolate */
204
205    /* Find the number of critical bands supported by our sampling rate */
206    for (nBark=1;nBark<maxBands;nBark++)
207     if (eband5ms[j+1]*400 >= mode->Fs)
208        break;
209
210    /* Compute per-codec-band allocation from per-critical-band matrix */
211    for (i=0;i<BITALLOC_SIZE;i++)
212    {
213       celt_int32 current = 0;
214       int eband = 0;
215       for (j=0;j<nBark;j++)
216       {
217          int edge, low, high;
218          celt_int32 alloc;
219          alloc = alloc_5ms[i*maxBands + j]*(mode->eBands[eband+1]-mode->eBands[eband])<<4;
220          low = eband5ms[j]*200;
221          high = eband5ms[j+1]*200;
222          edge = mode->eBands[eband+1]*res;
223          while (edge <= high && eband < mode->nbEBands)
224          {
225             celt_int32 num;
226             int den, bits;
227             int N = (mode->eBands[eband+1]-mode->eBands[eband]);
228             num = alloc * (edge-low);
229             den = high-low;
230             /* Divide with rounding */
231             bits = (2*num+den)/(2*den);
232             allocVectors[i*mode->nbEBands+eband] = (2*(current+bits)+(N<<4))/(2*N<<4);
233             /* Remove the part of the band we just allocated */
234             low = edge;
235             alloc -= bits;
236
237             /* Move to next eband */
238             current = 0;
239             eband++;
240             edge = mode->eBands[eband+1]*res;
241          }
242          current += alloc;
243       }
244       if (eband < mode->nbEBands)
245       {
246          int N = (mode->eBands[eband+1]-mode->eBands[eband]);
247          allocVectors[i*mode->nbEBands+eband] = (2*current+(N<<4))/(2*N<<4);
248       }
249    }
250    /*printf ("\n");
251    for (i=0;i<BITALLOC_SIZE;i++)
252    {
253       for (j=0;j<mode->nbEBands;j++)
254          printf ("%d ", allocVectors[i*mode->nbEBands+j]);
255       printf ("\n");
256    }
257    exit(0);*/
258
259    mode->allocVectors = allocVectors;
260 }
261
262 #endif /* STATIC_MODES */
263
264 CELTMode *celt_mode_create(celt_int32 Fs, 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           frame_size == static_mode_list[i]->mdctSize)
291       {
292          m = static_mode_list[i];
293          break;
294       }
295    }
296    if (m == NULL)
297    {
298       celt_warning("Mode not included as part of the static modes");
299       if (error)
300          *error = CELT_BAD_ARG;
301       return NULL;
302    }
303    mode = (CELTMode*)celt_alloc(sizeof(CELTMode));
304    if (mode==NULL)
305       goto failure;
306    CELT_COPY(mode, m, 1);
307    mode->marker_start = MODEPARTIAL;
308 #else
309    int res;
310    CELTMode *mode=NULL;
311    celt_word16 *window;
312    celt_int16 *logN;
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 (frame_size < 64 || frame_size > 1024 || frame_size%2!=0)
332    {
333       celt_warning("Only even frame sizes from 64 to 1024 are supported");
334       if (error)
335          *error = CELT_BAD_ARG;
336       return NULL;
337    }
338    
339    mode = celt_alloc(sizeof(CELTMode));
340    if (mode==NULL)
341       goto failure;
342    mode->marker_start = MODEPARTIAL;
343    mode->Fs = Fs;
344    mode->mdctSize = frame_size;
345    mode->ePredCoef = QCONST16(.8f,15);
346
347    if (frame_size >= 640 && (frame_size%16)==0)
348    {
349      mode->nbShortMdcts = 8;
350    } else if (frame_size >= 320 && (frame_size%8)==0)
351    {
352      mode->nbShortMdcts = 4;
353    } else if (frame_size >= 160 && (frame_size%4)==0)
354    {
355      mode->nbShortMdcts = 2;
356    } else
357    {
358      mode->nbShortMdcts = 1;
359    }
360
361    mode->shortMdctSize = mode->mdctSize/mode->nbShortMdcts;
362    res = (mode->Fs+mode->shortMdctSize)/(2*mode->shortMdctSize);
363
364    mode->eBands = compute_ebands(Fs, mode->shortMdctSize, res, &mode->nbEBands);
365    if (mode->eBands==NULL)
366       goto failure;
367
368    mode->pitchEnd = 4000*(celt_int32)mode->shortMdctSize/Fs;
369    
370    /* Overlap must be divisible by 4 */
371    if (mode->nbShortMdcts > 1)
372       mode->overlap = (mode->shortMdctSize>>2)<<2;
373    else
374       mode->overlap = (frame_size>>3)<<2;
375
376
377    compute_allocation_table(mode, res);
378    if (mode->allocVectors==NULL)
379       goto failure;
380    
381    window = (celt_word16*)celt_alloc(mode->overlap*sizeof(celt_word16));
382    if (window==NULL)
383       goto failure;
384
385 #ifndef FIXED_POINT
386    for (i=0;i<mode->overlap;i++)
387       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
388 #else
389    for (i=0;i<mode->overlap;i++)
390       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))));
391 #endif
392    mode->window = window;
393
394    mode->bits = mode->_bits+1;
395    for (i=0;(1<<i)<=mode->nbShortMdcts;i++)
396    {
397       mode->bits[i] = (const celt_int16 **)compute_alloc_cache(mode, 1<<i);
398       if (mode->bits[i]==NULL)
399          goto failure;
400    }
401    mode->bits[-1] = (const celt_int16 **)compute_alloc_cache(mode, 0);
402    if (mode->bits[-1]==NULL)
403       goto failure;
404
405    logN = (celt_int16*)celt_alloc(mode->nbEBands*sizeof(celt_int16));
406    if (logN==NULL)
407       goto failure;
408
409    for (i=0;i<mode->nbEBands;i++)
410       logN[i] = log2_frac(mode->eBands[i+1]-mode->eBands[i], BITRES);
411    mode->logN = logN;
412 #endif /* !STATIC_MODES */
413
414    for (i=0;(1<<i)<=mode->nbShortMdcts;i++)
415    {
416       clt_mdct_init(&mode->mdct[i], 2*mode->shortMdctSize<<i);
417       if ((mode->mdct[i].trig==NULL)
418 #ifndef ENABLE_TI_DSPLIB55
419            || (mode->mdct[i].kfft==NULL)
420 #endif
421       )
422         goto failure;
423    }
424    mode->prob = quant_prob_alloc(mode);
425    if (mode->prob==NULL)
426      goto failure;
427
428    mode->marker_start = MODEVALID;
429    mode->marker_end   = MODEVALID;
430    if (error)
431       *error = CELT_OK;
432    return mode;
433 failure: 
434    if (error)
435       *error = CELT_INVALID_MODE;
436    if (mode!=NULL)
437       celt_mode_destroy(mode);
438    return NULL;
439 }
440
441 void celt_mode_destroy(CELTMode *mode)
442 {
443    int i, m;
444    const celt_int16 *prevPtr = NULL;
445    if (mode == NULL)
446    {
447       celt_warning("NULL passed to celt_mode_destroy");
448       return;
449    }
450
451    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
452    {
453       celt_warning("Freeing a mode which has already been freed"); 
454       return;
455    }
456
457    if (mode->marker_start != MODEVALID && mode->marker_start != MODEPARTIAL)
458    {
459       celt_warning("This is not a valid CELT mode structure");
460       return;  
461    }
462    mode->marker_start = MODEFREED;
463 #ifndef STATIC_MODES
464    for (m=0;(1<<m)<=mode->nbShortMdcts;m++)
465    {
466       if (mode->bits[m]!=NULL)
467       {
468          for (i=0;i<mode->nbEBands;i++)
469          {
470             if (mode->bits[m][i] != prevPtr)
471             {
472                prevPtr = mode->bits[m][i];
473                celt_free((int*)mode->bits[m][i]);
474             }
475          }
476       }
477       celt_free((celt_int16**)mode->bits[m]);
478    }
479    if (mode->bits[-1]!=NULL)
480    {
481       for (i=0;i<mode->nbEBands;i++)
482       {
483          if (mode->bits[-1][i] != prevPtr)
484          {
485             prevPtr = mode->bits[-1][i];
486             celt_free((int*)mode->bits[-1][i]);
487          }
488       }
489    }
490    celt_free((celt_int16**)mode->bits[-1]);
491
492    celt_free((celt_int16*)mode->eBands);
493    celt_free((celt_int16*)mode->allocVectors);
494    
495    celt_free((celt_word16*)mode->window);
496    celt_free((celt_int16*)mode->logN);
497
498 #endif
499    for (i=0;(1<<i)<=mode->nbShortMdcts;i++)
500       clt_mdct_clear(&mode->mdct[i]);
501
502    quant_prob_free(mode->prob);
503    mode->marker_end = MODEFREED;
504    celt_free((CELTMode *)mode);
505 }
506
507 int check_mode(const CELTMode *mode)
508 {
509    if (mode==NULL)
510       return CELT_INVALID_MODE;
511    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
512       return CELT_OK;
513    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
514       celt_warning("Using a mode that has already been freed");
515    else
516       celt_warning("This is not a valid CELT mode");
517    return CELT_INVALID_MODE;
518 }