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