Fix misleading comments about ec_{enc|dec}_tell()
[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 band_allocation[] = {
102     /* 0 200 400 600 800  1k 1.2 1.4 1.6  2k 2.4 2.8 3.2  4k 4.8 5.6 6.8  8k 9.6 12k 15.6 */
103       10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
104       10,  3,  8,  2,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
105       10,  6,  8,  6,  5,  4,  3,  2,  7, 10, 11,  9,  7,  3,  1,  0,  0,  0,  0,  0,  0,
106       10, 10, 14, 11, 10,  8,  6,  5, 10, 12, 13, 11,  8,  4,  2,  1,  0,  0,  0,  0,  0,
107       13, 10, 17, 16, 14, 12, 10,  8, 12, 14, 14, 12,  9,  5,  3,  2,  2,  1,  0,  0,  0,
108       17, 21, 23, 26, 24, 20, 17, 16, 17, 18, 16, 14, 11,  6,  3,  2,  2,  1,  1,  0,  0,
109       21, 21, 36, 32, 28, 24, 23, 23, 22, 18, 18, 14, 11,  7,  5,  5,  5,  3,  3,  0,  0,
110       31, 35, 40, 32, 30, 28, 26, 26, 25, 24, 19, 15, 15, 13,  9,  9,  8,  7,  5,  2,  0,
111       42, 46, 46, 37, 35, 34, 33, 32, 34, 35, 32, 31, 27, 24, 23, 23, 18, 14, 11,  7,  0,
112       46, 49, 46, 46, 42, 43, 44, 47, 50, 52, 51, 48, 39, 32, 27, 24, 22, 19, 17, 11,  5,
113       53, 53, 49, 48, 55, 66, 71, 71, 71, 65, 64, 64, 56, 47, 41, 37, 31, 24, 20, 16, 10,
114       60, 64, 74, 74, 87,103,106,102,101,100,101, 95, 80, 69, 63, 55, 47, 36, 26, 21, 15,
115 };
116
117 static celt_int16 *compute_ebands(celt_int32 Fs, int frame_size, int res, int *nbEBands)
118 {
119    celt_int16 *eBands;
120    int i, lin, low, high, nBark, offset=0;
121
122    if (Fs == 400*(celt_int32)frame_size && Fs >= 40000)
123    {
124       *nbEBands = sizeof(eband5ms)/sizeof(eband5ms[0])-1;
125       eBands = celt_alloc(sizeof(celt_int16)*(*nbEBands+2));
126       for (i=0;i<*nbEBands+2;i++)
127          eBands[i] = eband5ms[i];
128       eBands[*nbEBands+1] = frame_size;
129       return eBands;
130    }
131    /* Find the number of critical bands supported by our sampling rate */
132    for (nBark=1;nBark<BARK_BANDS;nBark++)
133     if (bark_freq[nBark+1]*2 >= Fs)
134        break;
135
136    /* Find where the linear part ends (i.e. where the spacing is more than min_width */
137    for (lin=0;lin<nBark;lin++)
138       if (bark_freq[lin+1]-bark_freq[lin] >= res)
139          break;
140
141    low = (bark_freq[lin]+res/2)/res;
142    high = nBark-lin;
143    *nbEBands = low+high;
144    eBands = celt_alloc(sizeof(celt_int16)*(*nbEBands+2));
145    
146    if (eBands==NULL)
147       return NULL;
148    
149    /* Linear spacing (min_width) */
150    for (i=0;i<low;i++)
151       eBands[i] = i;
152    if (low>0)
153       offset = eBands[low-1]*res - bark_freq[lin-1];
154    /* Spacing follows critical bands */
155    for (i=0;i<high;i++)
156    {
157       int target = bark_freq[lin+i];
158       eBands[i+low] = (target+(offset+res)/2)/res;
159       offset = eBands[i+low]*res - target;
160    }
161    /* Enforce the minimum spacing at the boundary */
162    for (i=0;i<*nbEBands;i++)
163       if (eBands[i] < i)
164          eBands[i] = i;
165    eBands[*nbEBands] = (bark_freq[nBark]+res/2)/res;
166    eBands[*nbEBands+1] = frame_size;
167    if (eBands[*nbEBands] > eBands[*nbEBands+1])
168       eBands[*nbEBands] = eBands[*nbEBands+1];
169    for (i=1;i<*nbEBands-1;i++)
170    {
171       if (eBands[i+1]-eBands[i] < eBands[i]-eBands[i-1])
172       {
173          eBands[i] -= (2*eBands[i]-eBands[i-1]-eBands[i+1])/2;
174       }
175    }
176    /*for (i=0;i<=*nbEBands+1;i++)
177       printf ("%d ", eBands[i]);
178    printf ("\n");
179    exit(1);*/
180    /* FIXME: Remove last band if too small */
181    return eBands;
182 }
183
184 static void compute_allocation_table(CELTMode *mode, int res)
185 {
186    int i, j;
187    unsigned char *allocVectors;
188    int maxBands = sizeof(eband5ms)/sizeof(eband5ms[0])-1;
189
190    mode->nbAllocVectors = BITALLOC_SIZE;
191    allocVectors = celt_alloc(sizeof(unsigned char)*(BITALLOC_SIZE*mode->nbEBands));
192    if (allocVectors==NULL)
193       return;
194
195    /* Check for standard mode */
196    if (mode->Fs == 400*(celt_int32)mode->shortMdctSize && mode->Fs >= 40000)
197    {
198       for (i=0;i<BITALLOC_SIZE*mode->nbEBands;i++)
199          allocVectors[i] = band_allocation[i];
200       mode->allocVectors = allocVectors;
201       return;
202    }
203    /* If not the standard mode, interpolate */
204
205    /* Compute per-codec-band allocation from per-critical-band matrix */
206    for (i=0;i<BITALLOC_SIZE;i++)
207    {
208       celt_int32 current = 0;
209       int eband = 0;
210       /* We may be looping over too many bands, but eband will stop being
211          incremented once we reach the last band */
212       for (j=0;j<maxBands;j++)
213       {
214          int edge, low, high;
215          celt_int32 alloc;
216          alloc = band_allocation[i*maxBands + j]*(mode->eBands[eband+1]-mode->eBands[eband])<<4;
217          low = eband5ms[j]*200;
218          high = eband5ms[j+1]*200;
219          edge = mode->eBands[eband+1]*res;
220          while (edge <= high && eband < mode->nbEBands)
221          {
222             celt_int32 num;
223             int den, bits;
224             int N = (mode->eBands[eband+1]-mode->eBands[eband]);
225             num = alloc * (edge-low);
226             den = high-low;
227             /* Divide with rounding */
228             bits = (2*num+den)/(2*den);
229             allocVectors[i*mode->nbEBands+eband] = (2*(current+bits)+(N<<4))/(2*N<<4);
230             /* Remove the part of the band we just allocated */
231             low = edge;
232             alloc -= bits;
233
234             /* Move to next eband */
235             current = 0;
236             eband++;
237             edge = mode->eBands[eband+1]*res;
238          }
239          current += alloc;
240       }
241       if (eband < mode->nbEBands)
242       {
243          int N = (mode->eBands[eband+1]-mode->eBands[eband]);
244          allocVectors[i*mode->nbEBands+eband] = (2*current+(N<<4))/(2*N<<4);
245       }
246    }
247    /*printf ("\n");
248    for (i=0;i<BITALLOC_SIZE;i++)
249    {
250       for (j=0;j<mode->nbEBands;j++)
251          printf ("%d ", allocVectors[i*mode->nbEBands+j]);
252       printf ("\n");
253    }
254    exit(0);*/
255
256    mode->allocVectors = allocVectors;
257 }
258
259 #endif /* STATIC_MODES */
260
261 CELTMode *celt_mode_create(celt_int32 Fs, int frame_size, int *error)
262 {
263    int i;
264 #ifdef STDIN_TUNING
265    scanf("%d ", &MIN_BINS);
266    scanf("%d ", &BITALLOC_SIZE);
267    band_allocation = celt_alloc(sizeof(int)*BARK_BANDS*BITALLOC_SIZE);
268    for (i=0;i<BARK_BANDS*BITALLOC_SIZE;i++)
269    {
270       scanf("%d ", band_allocation+i);
271    }
272 #endif
273 #ifdef STATIC_MODES
274    const CELTMode *m = NULL;
275    CELTMode *mode=NULL;
276    ALLOC_STACK;
277 #if !defined(VAR_ARRAYS) && !defined(USE_ALLOCA)
278    if (global_stack==NULL)
279       goto failure;
280 #endif 
281    for (i=0;i<TOTAL_MODES;i++)
282    {
283       if (Fs == static_mode_list[i]->Fs &&
284           frame_size == static_mode_list[i]->shortMdctSize*static_mode_list[i]->nbShortMdcts)
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->bits = mode->_bits+1;
302    mode->marker_start = MODEPARTIAL;
303 #else
304    int res;
305    CELTMode *mode=NULL;
306    celt_word16 *window;
307    celt_int16 *logN;
308    ALLOC_STACK;
309 #if !defined(VAR_ARRAYS) && !defined(USE_ALLOCA)
310    if (global_stack==NULL)
311       goto failure;
312 #endif 
313
314    /* The good thing here is that permutation of the arguments will automatically be invalid */
315    
316    if (Fs < 32000 || Fs > 96000)
317    {
318       celt_warning("Sampling rate must be between 32 kHz and 96 kHz");
319       if (error)
320          *error = CELT_BAD_ARG;
321       return NULL;
322    }
323    if (frame_size < 64 || frame_size > 1024 || frame_size%2!=0)
324    {
325       celt_warning("Only even frame sizes from 64 to 1024 are supported");
326       if (error)
327          *error = CELT_BAD_ARG;
328       return NULL;
329    }
330    
331    mode = celt_alloc(sizeof(CELTMode));
332    if (mode==NULL)
333       goto failure;
334    mode->marker_start = MODEPARTIAL;
335    mode->Fs = Fs;
336    mode->ePredCoef = QCONST16(.8f,15);
337
338    if (frame_size >= 640 && (frame_size%16)==0)
339    {
340      mode->nbShortMdcts = 8;
341    } else if (frame_size >= 320 && (frame_size%8)==0)
342    {
343      mode->nbShortMdcts = 4;
344    } else if (frame_size >= 160 && (frame_size%4)==0)
345    {
346      mode->nbShortMdcts = 2;
347    } else
348    {
349      mode->nbShortMdcts = 1;
350    }
351
352    mode->shortMdctSize = frame_size/mode->nbShortMdcts;
353    res = (mode->Fs+mode->shortMdctSize)/(2*mode->shortMdctSize);
354
355    mode->eBands = compute_ebands(Fs, mode->shortMdctSize, res, &mode->nbEBands);
356    if (mode->eBands==NULL)
357       goto failure;
358
359    mode->pitchEnd = 4000*(celt_int32)mode->shortMdctSize/Fs;
360    
361    /* Overlap must be divisible by 4 */
362    if (mode->nbShortMdcts > 1)
363       mode->overlap = (mode->shortMdctSize>>2)<<2;
364    else
365       mode->overlap = (frame_size>>3)<<2;
366
367
368    compute_allocation_table(mode, res);
369    if (mode->allocVectors==NULL)
370       goto failure;
371    
372    window = (celt_word16*)celt_alloc(mode->overlap*sizeof(celt_word16));
373    if (window==NULL)
374       goto failure;
375
376 #ifndef FIXED_POINT
377    for (i=0;i<mode->overlap;i++)
378       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
379 #else
380    for (i=0;i<mode->overlap;i++)
381       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))));
382 #endif
383    mode->window = window;
384
385    mode->bits = mode->_bits+1;
386    for (i=0;(1<<i)<=mode->nbShortMdcts;i++)
387    {
388       mode->bits[i] = (const celt_int16 **)compute_alloc_cache(mode, 1<<i);
389       if (mode->bits[i]==NULL)
390          goto failure;
391    }
392    mode->bits[-1] = (const celt_int16 **)compute_alloc_cache(mode, 0);
393    if (mode->bits[-1]==NULL)
394       goto failure;
395
396    logN = (celt_int16*)celt_alloc(mode->nbEBands*sizeof(celt_int16));
397    if (logN==NULL)
398       goto failure;
399
400    for (i=0;i<mode->nbEBands;i++)
401       logN[i] = log2_frac(mode->eBands[i+1]-mode->eBands[i], BITRES);
402    mode->logN = logN;
403 #endif /* !STATIC_MODES */
404
405    for (i=0;(1<<i)<=mode->nbShortMdcts;i++)
406    {
407       clt_mdct_init(&mode->mdct[i], 2*mode->shortMdctSize<<i);
408       if ((mode->mdct[i].trig==NULL)
409 #ifndef ENABLE_TI_DSPLIB55
410            || (mode->mdct[i].kfft==NULL)
411 #endif
412       )
413         goto failure;
414    }
415    mode->prob = quant_prob_alloc(mode);
416    if (mode->prob==NULL)
417      goto failure;
418
419    mode->marker_start = MODEVALID;
420    mode->marker_end   = MODEVALID;
421    if (error)
422       *error = CELT_OK;
423    return mode;
424 failure: 
425    if (error)
426       *error = CELT_INVALID_MODE;
427    if (mode!=NULL)
428       celt_mode_destroy(mode);
429    return NULL;
430 }
431
432 void celt_mode_destroy(CELTMode *mode)
433 {
434    int i, m;
435    const celt_int16 *prevPtr = NULL;
436    if (mode == NULL)
437    {
438       celt_warning("NULL passed to celt_mode_destroy");
439       return;
440    }
441
442    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
443    {
444       celt_warning("Freeing a mode which has already been freed"); 
445       return;
446    }
447
448    if (mode->marker_start != MODEVALID && mode->marker_start != MODEPARTIAL)
449    {
450       celt_warning("This is not a valid CELT mode structure");
451       return;  
452    }
453    mode->marker_start = MODEFREED;
454 #ifndef STATIC_MODES
455    for (m=0;(1<<m)<=mode->nbShortMdcts;m++)
456    {
457       if (mode->bits[m]!=NULL)
458       {
459          for (i=0;i<mode->nbEBands;i++)
460          {
461             if (mode->bits[m][i] != prevPtr)
462             {
463                prevPtr = mode->bits[m][i];
464                celt_free((int*)mode->bits[m][i]);
465             }
466          }
467       }
468       celt_free((celt_int16**)mode->bits[m]);
469    }
470    if (mode->bits[-1]!=NULL)
471    {
472       for (i=0;i<mode->nbEBands;i++)
473       {
474          if (mode->bits[-1][i] != prevPtr)
475          {
476             prevPtr = mode->bits[-1][i];
477             celt_free((int*)mode->bits[-1][i]);
478          }
479       }
480    }
481    celt_free((celt_int16**)mode->bits[-1]);
482
483    celt_free((celt_int16*)mode->eBands);
484    celt_free((celt_int16*)mode->allocVectors);
485    
486    celt_free((celt_word16*)mode->window);
487    celt_free((celt_int16*)mode->logN);
488
489 #endif
490    for (i=0;(1<<i)<=mode->nbShortMdcts;i++)
491       clt_mdct_clear(&mode->mdct[i]);
492
493    quant_prob_free(mode->prob);
494    mode->marker_end = MODEFREED;
495    celt_free((CELTMode *)mode);
496 }
497
498 int check_mode(const CELTMode *mode)
499 {
500    if (mode==NULL)
501       return CELT_INVALID_MODE;
502    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
503       return CELT_OK;
504    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
505       celt_warning("Using a mode that has already been freed");
506    else
507       celt_warning("This is not a valid CELT mode");
508    return CELT_INVALID_MODE;
509 }