Removing original freq-domain pitch code
[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    ALLOC_STACK;
277 #if !defined(VAR_ARRAYS) && !defined(USE_ALLOCA)
278    if (global_stack==NULL)
279    {
280       celt_free(global_stack);
281       goto failure;
282    }
283 #endif 
284
285    /* The good thing here is that permutation of the arguments will automatically be invalid */
286    
287    if (Fs < 32000 || Fs > 96000)
288    {
289       celt_warning("Sampling rate must be between 32 kHz and 96 kHz");
290       if (error)
291          *error = CELT_BAD_ARG;
292       return NULL;
293    }
294    if (frame_size < 64 || frame_size > 1024 || frame_size%2!=0)
295    {
296       celt_warning("Only even frame sizes from 64 to 1024 are supported");
297       if (error)
298          *error = CELT_BAD_ARG;
299       return NULL;
300    }
301    res = (Fs+frame_size)/(2*frame_size);
302    
303    mode = celt_alloc(sizeof(CELTMode));
304    if (mode==NULL)
305       goto failure;
306    mode->marker_start = MODEPARTIAL;
307    mode->Fs = Fs;
308    mode->mdctSize = frame_size;
309    mode->ePredCoef = QCONST16(.8f,15);
310
311    if (frame_size > 640 && (frame_size%16)==0)
312    {
313      mode->nbShortMdcts = 8;
314    } else if (frame_size > 384 && (frame_size%8)==0)
315    {
316      mode->nbShortMdcts = 4;
317    } else if (frame_size > 384 && (frame_size%10)==0)
318    {
319      mode->nbShortMdcts = 5;
320    } else if (frame_size > 256 && (frame_size%6)==0)
321    {
322      mode->nbShortMdcts = 3;
323    } else if (frame_size > 256 && (frame_size%8)==0)
324    {
325      mode->nbShortMdcts = 4;
326    } else if (frame_size > 64 && (frame_size%4)==0)
327    {
328      mode->nbShortMdcts = 2;
329    } else if (frame_size > 128 && (frame_size%6)==0)
330    {
331      mode->nbShortMdcts = 3;
332    } else
333    {
334      mode->nbShortMdcts = 1;
335    }
336
337    mode->eBands = compute_ebands(Fs, frame_size, mode->nbShortMdcts, &mode->nbEBands);
338    if (mode->eBands==NULL)
339       goto failure;
340
341    mode->pitchEnd = 4000*(celt_int32)frame_size/Fs;
342    
343    /* Overlap must be divisible by 4 */
344    if (mode->nbShortMdcts > 1)
345       mode->overlap = ((frame_size/mode->nbShortMdcts)>>2)<<2; 
346    else
347       mode->overlap = (frame_size>>3)<<2;
348
349    compute_allocation_table(mode, res);
350    if (mode->allocVectors==NULL)
351       goto failure;
352    
353    window = (celt_word16*)celt_alloc(mode->overlap*sizeof(celt_word16));
354    if (window==NULL)
355       goto failure;
356
357 #ifndef FIXED_POINT
358    for (i=0;i<mode->overlap;i++)
359       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
360 #else
361    for (i=0;i<mode->overlap;i++)
362       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)));
363 #endif
364    mode->window = window;
365
366    mode->bits = (const celt_int16 **)compute_alloc_cache(mode, 1);
367    if (mode->bits==NULL)
368       goto failure;
369
370 #endif /* !STATIC_MODES */
371
372    mdct_init(&mode->mdct, 2*mode->mdctSize);
373
374    mode->shortMdctSize = mode->mdctSize/mode->nbShortMdcts;
375    mdct_init(&mode->shortMdct, 2*mode->shortMdctSize);
376    mode->shortWindow = mode->window;
377    mode->prob = quant_prob_alloc(mode);
378    if ((mode->mdct.trig==NULL) || (mode->shortMdct.trig==NULL)
379 #ifndef ENABLE_TI_DSPLIB55
380         || (mode->mdct.kfft==NULL) || (mode->shortMdct.kfft==NULL)
381 #endif
382         || (mode->prob==NULL))
383      goto failure;
384
385    mode->marker_start = MODEVALID;
386    mode->marker_end   = MODEVALID;
387    if (error)
388       *error = CELT_OK;
389    return mode;
390 failure: 
391    if (error)
392       *error = CELT_INVALID_MODE;
393    if (mode!=NULL)
394       celt_mode_destroy(mode);
395    return NULL;
396 }
397
398 void celt_mode_destroy(CELTMode *mode)
399 {
400    int i;
401    const celt_int16 *prevPtr = NULL;
402    if (mode == NULL)
403    {
404       celt_warning("NULL passed to celt_mode_destroy");
405       return;
406    }
407
408    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
409    {
410       celt_warning("Freeing a mode which has already been freed"); 
411       return;
412    }
413
414    if (mode->marker_start != MODEVALID && mode->marker_start != MODEPARTIAL)
415    {
416       celt_warning("This is not a valid CELT mode structure");
417       return;  
418    }
419    mode->marker_start = MODEFREED;
420 #ifndef STATIC_MODES
421    if (mode->bits!=NULL)
422    {
423       for (i=0;i<mode->nbEBands;i++)
424       {
425          if (mode->bits[i] != prevPtr)
426          {
427             prevPtr = mode->bits[i];
428             celt_free((int*)mode->bits[i]);
429           }
430       }
431    }   
432    celt_free((int**)mode->bits);
433    celt_free((int*)mode->eBands);
434    celt_free((int*)mode->allocVectors);
435    
436    celt_free((celt_word16*)mode->window);
437
438 #endif
439    mdct_clear(&mode->mdct);
440    mdct_clear(&mode->shortMdct);
441    quant_prob_free(mode->prob);
442    mode->marker_end = MODEFREED;
443    celt_free((CELTMode *)mode);
444 }
445
446 int check_mode(const CELTMode *mode)
447 {
448    if (mode==NULL)
449       return CELT_INVALID_MODE;
450    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
451       return CELT_OK;
452    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
453       celt_warning("Using a mode that has already been freed");
454    else
455       celt_warning("This is not a valid CELT mode");
456    return CELT_INVALID_MODE;
457 }