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