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