Automatically choosing the overlap based on the frame size.
[opus.git] / libcelt / modes.c
1 /* (C) 2007-2008 Jean-Marc Valin, CSIRO
2 */
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 MODEFREED 0xb10cf8ee
49
50 #ifndef M_PI
51 #define M_PI 3.141592653
52 #endif
53
54
55 int celt_mode_info(const CELTMode *mode, int request, celt_int32_t *value)
56 {
57    switch (request)
58    {
59       case CELT_GET_FRAME_SIZE:
60          *value = mode->mdctSize;
61          break;
62       case CELT_GET_LOOKAHEAD:
63          *value = mode->overlap;
64          break;
65       case CELT_GET_NB_CHANNELS:
66          *value = mode->nbChannels;
67          break;
68       case CELT_GET_BITSTREAM_VERSION:
69          *value = CELT_BITSTREAM_VERSION;
70          break;
71       default:
72          return CELT_BAD_ARG;
73    }
74    return CELT_OK;
75 }
76
77 #ifndef STATIC_MODES
78
79 #define PBANDS 8
80
81 #ifdef STDIN_TUNING
82 int MIN_BINS;
83 #else
84 #define MIN_BINS 3
85 #endif
86
87 /* Defining 25 critical bands for the full 0-20 kHz audio bandwidth
88    Taken from http://ccrma.stanford.edu/~jos/bbt/Bark_Frequency_Scale.html */
89 #define BARK_BANDS 25
90 static const celt_int16_t bark_freq[BARK_BANDS+1] = {
91       0,   100,   200,   300,   400,
92     510,   630,   770,   920,  1080,
93    1270,  1480,  1720,  2000,  2320,
94    2700,  3150,  3700,  4400,  5300,
95    6400,  7700,  9500, 12000, 15500,
96   20000};
97
98 static const celt_int16_t pitch_freq[PBANDS+1] ={0, 345, 689, 1034, 1378, 2067, 3273, 5340, 6374};
99
100 /* This allocation table is per critical band. When creating a mode, the bits get added together 
101    into the codec bands, which are sometimes larger than one critical band at low frequency */
102
103 #ifdef STDIN_TUNING
104 int BITALLOC_SIZE;
105 int *band_allocation;
106 #else
107 #define BITALLOC_SIZE 10
108 static const int band_allocation[BARK_BANDS*BITALLOC_SIZE] = 
109    {  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,
110       2,  2,  2,  1,  2,  2,  2,  2,  2,  1,  2,  2,  4,  5,  7,  7,  7,  5,  4,  0,  0,  0,  0,  0,  0,
111       2,  2,  2,  2,  3,  2,  2,  2,  2,  2,  3,  3,  5,  6,  8,  8,  8,  6,  5,  4,  0,  0,  0,  0,  0,
112       3,  2,  2,  2,  3,  3,  2,  3,  2,  3,  4,  4,  6,  7,  9,  9,  9,  7,  6,  5,  5,  5,  0,  0,  0,
113       3,  3,  2,  2,  3,  3,  3,  3,  3,  4,  4,  5,  7,  9, 10, 10, 10,  9,  6,  5,  5,  5,  5,  1,  0,
114       4,  3,  3,  3,  3,  3,  3,  3,  4,  4,  6,  7,  7,  9, 11, 10, 10,  9,  9,  8, 11, 10, 10,  1,  1,
115       5,  5,  4,  4,  5,  5,  5,  5,  6,  6,  8,  8, 10, 12, 15, 15, 13, 12, 12, 12, 18, 18, 16, 10,  1,
116       6,  6,  6,  6,  6,  6,  7,  7,  9,  9, 11, 12, 13, 18, 22, 23, 24, 25, 28, 30, 35, 35, 35, 35, 15,
117       7,  7,  7,  7,  7,  7, 10, 10, 10, 13, 14, 18, 20, 24, 28, 32, 32, 35, 38, 38, 42, 50, 59, 54, 31,
118       8,  8,  8,  8,  8,  9, 10, 12, 14, 20, 22, 25, 28, 30, 35, 42, 46, 50, 55, 60, 62, 62, 62, 62, 62,
119 };
120 #endif
121
122 static celt_int16_t *compute_ebands(celt_int32_t Fs, int frame_size, int *nbEBands)
123 {
124    celt_int16_t *eBands;
125    int i, res, min_width, lin, low, high;
126    res = (Fs+frame_size)/(2*frame_size);
127    min_width = MIN_BINS*res;
128    /*printf ("min_width = %d\n", min_width);*/
129
130    /* Find where the linear part ends (i.e. where the spacing is more than min_width */
131    for (lin=0;lin<BARK_BANDS;lin++)
132       if (bark_freq[lin+1]-bark_freq[lin] >= min_width)
133          break;
134    
135    /*printf ("lin = %d (%d Hz)\n", lin, bark_freq[lin]);*/
136    low = ((bark_freq[lin]/res)+(MIN_BINS-1))/MIN_BINS;
137    high = BARK_BANDS-lin;
138    *nbEBands = low+high;
139    eBands = celt_alloc(sizeof(celt_int16_t)*(*nbEBands+2));
140    
141    /* Linear spacing (min_width) */
142    for (i=0;i<low;i++)
143       eBands[i] = MIN_BINS*i;
144    /* Spacing follows critical bands */
145    for (i=0;i<high;i++)
146       eBands[i+low] = (bark_freq[lin+i]+res/2)/res;
147    /* Enforce the minimum spacing at the boundary */
148    for (i=0;i<*nbEBands;i++)
149       if (eBands[i] < MIN_BINS*i)
150          eBands[i] = MIN_BINS*i;
151    eBands[*nbEBands] = (bark_freq[BARK_BANDS]+res/2)/res;
152    eBands[*nbEBands+1] = frame_size;
153    if (eBands[*nbEBands] > eBands[*nbEBands+1])
154       eBands[*nbEBands] = eBands[*nbEBands+1];
155    
156    /* FIXME: Remove last band if too small */
157    /*for (i=0;i<*nbEBands+2;i++)
158       printf("%d ", eBands[i]);
159    printf ("\n");*/
160    return eBands;
161 }
162
163 static void compute_pbands(CELTMode *mode, int res)
164 {
165    int i;
166    celt_int16_t *pBands;
167    pBands=celt_alloc(sizeof(celt_int16_t)*(PBANDS+2));
168    mode->nbPBands = PBANDS;
169    for (i=0;i<PBANDS+1;i++)
170    {
171       pBands[i] = (pitch_freq[i]+res/2)/res;
172       if (pBands[i] < mode->eBands[i])
173          pBands[i] = mode->eBands[i];
174    }
175    pBands[PBANDS+1] = mode->eBands[mode->nbEBands+1];
176    for (i=1;i<mode->nbPBands+1;i++)
177    {
178       int j;
179       for (j=0;j<mode->nbEBands;j++)
180          if (mode->eBands[j] <= pBands[i] && mode->eBands[j+1] > pBands[i])
181             break;
182       /*printf ("%d %d\n", i, j);*/
183       if (mode->eBands[j] != pBands[i])
184       {
185          if (pBands[i]-mode->eBands[j] < mode->eBands[j+1]-pBands[i] && 
186              mode->eBands[j] != pBands[i-1])
187             pBands[i] = mode->eBands[j];
188          else
189             pBands[i] = mode->eBands[j+1];
190       }
191    }
192    /*for (i=0;i<mode->nbPBands+2;i++)
193       printf("%d ", pBands[i]);
194    printf ("\n");*/
195    mode->pBands = pBands;
196    mode->pitchEnd = pBands[PBANDS];
197 }
198
199 static void compute_allocation_table(CELTMode *mode, int res)
200 {
201    int i, j, eband;
202    celt_int16_t *allocVectors;
203    
204    mode->nbAllocVectors = BITALLOC_SIZE;
205    allocVectors = celt_alloc(sizeof(celt_int16_t)*(BITALLOC_SIZE*mode->nbEBands));
206    for (i=0;i<BITALLOC_SIZE;i++)
207    {
208       eband = 0;
209       for (j=0;j<BARK_BANDS;j++)
210       {
211          int edge, low, alloc;
212          edge = mode->eBands[eband+1]*res;
213          alloc = band_allocation[i*BARK_BANDS+j];
214          if (mode->nbChannels == 2)
215             alloc += alloc/2;
216          if (edge < bark_freq[j+1])
217          {
218             int num, den;
219             num = alloc * (edge-bark_freq[j]);
220             den = bark_freq[j+1]-bark_freq[j];
221             low = (num+den/2)/den;
222             allocVectors[i*mode->nbEBands+eband] += low;
223             eband++;
224             allocVectors[i*mode->nbEBands+eband] += alloc-low;
225          } else {
226             allocVectors[i*mode->nbEBands+eband] += alloc;
227          }
228       }
229    }
230    /*for (i=0;i<BITALLOC_SIZE;i++)
231    {
232       for (j=0;j<mode->nbEBands;j++)
233          printf ("%2d ", allocVectors[i*mode->nbEBands+j]);
234       printf ("\n");
235    }*/
236    mode->allocVectors = allocVectors;
237 }
238
239 #endif /* STATIC_MODES */
240
241 static void compute_energy_allocation_table(CELTMode *mode)
242 {
243    int i, j;
244    celt_int16_t *alloc;
245    
246    alloc = celt_alloc(sizeof(celt_int16_t)*(mode->nbAllocVectors*(mode->nbEBands+1)));
247    for (i=0;i<mode->nbAllocVectors;i++)
248    {
249       int sum = 0;
250       int min_bits = 1;
251       if (mode->allocVectors[i*mode->nbEBands]>12)
252          min_bits = 2;
253       if (mode->allocVectors[i*mode->nbEBands]>24)
254          min_bits = 3;
255       for (j=0;j<mode->nbEBands;j++)
256       {
257          alloc[i*(mode->nbEBands+1)+j] = mode->allocVectors[i*mode->nbEBands+j]
258                                          / (mode->eBands[j+1]-mode->eBands[j]-1);
259          if (alloc[i*(mode->nbEBands+1)+j]<min_bits)
260             alloc[i*(mode->nbEBands+1)+j] = min_bits;
261          if (alloc[i*(mode->nbEBands+1)+j]>7)
262             alloc[i*(mode->nbEBands+1)+j] = 7;
263          sum += alloc[i*(mode->nbEBands+1)+j];
264          /*printf ("%d ", alloc[i*(mode->nbEBands+1)+j]);*/
265          /*printf ("%f ", mode->allocVectors[i*mode->nbEBands+j]*1.f/(mode->eBands[j+1]-mode->eBands[j]-1));*/
266       }
267       alloc[i*(mode->nbEBands+1)+mode->nbEBands] = sum;
268       /*printf ("\n");*/
269    }
270    mode->energy_alloc = alloc;
271 }
272
273 CELTMode *celt_mode_create(celt_int32_t Fs, int channels, int frame_size, int *error)
274 {
275    int i;
276 #ifdef STDIN_TUNING
277    scanf("%d ", &MIN_BINS);
278    scanf("%d ", &BITALLOC_SIZE);
279    band_allocation = celt_alloc(sizeof(int)*BARK_BANDS*BITALLOC_SIZE);
280    for (i=0;i<BARK_BANDS*BITALLOC_SIZE;i++)
281    {
282       scanf("%d ", band_allocation+i);
283    }
284 #endif
285 #ifdef STATIC_MODES
286    const CELTMode *m = NULL;
287    CELTMode *mode=NULL;
288    ALLOC_STACK;
289    for (i=0;i<TOTAL_MODES;i++)
290    {
291       if (Fs == static_mode_list[i]->Fs &&
292           channels == static_mode_list[i]->nbChannels &&
293           frame_size == static_mode_list[i]->mdctSize &&
294           lookahead == static_mode_list[i]->overlap)
295       {
296          m = static_mode_list[i];
297          break;
298       }
299    }
300    if (m == NULL)
301    {
302       celt_warning("Mode not included as part of the static modes");
303       if (error)
304          *error = CELT_BAD_ARG;
305       return NULL;
306    }
307    mode = (CELTMode*)celt_alloc(sizeof(CELTMode));
308    CELT_COPY(mode, m, 1);
309 #else
310    int res;
311    CELTMode *mode;
312    celt_word16_t *window;
313    ALLOC_STACK;
314
315    /* The good thing here is that permutation of the arguments will automatically be invalid */
316    
317    if (Fs < 32000 || Fs > 64000)
318    {
319       celt_warning("Sampling rate must be between 32 kHz and 64 kHz");
320       if (error)
321          *error = CELT_BAD_ARG;
322       return NULL;
323    }
324    if (channels < 0 || channels > 2)
325    {
326       celt_warning("Only mono and stereo supported");
327       if (error)
328          *error = CELT_BAD_ARG;
329       return NULL;
330    }
331    if (frame_size < 64 || frame_size > 512 || frame_size%2!=0)
332    {
333       celt_warning("Only even frame sizes between 64 and 512 are supported");
334       if (error)
335          *error = CELT_BAD_ARG;
336       return NULL;
337    }
338    res = (Fs+frame_size)/(2*frame_size);
339    
340    mode = celt_alloc(sizeof(CELTMode));
341    mode->Fs = Fs;
342    mode->mdctSize = frame_size;
343    mode->nbChannels = channels;
344    mode->eBands = compute_ebands(Fs, frame_size, &mode->nbEBands);
345    compute_pbands(mode, res);
346    mode->ePredCoef = QCONST16(.8f,15);
347    
348    if (frame_size <= 64)
349    {
350       mode->nbShortMdcts = 1;
351    } else if (frame_size <= 256)
352    {
353       mode->nbShortMdcts = 2;
354    } else if (frame_size <= 384)
355    {
356       mode->nbShortMdcts = 3;
357    } else {
358       mode->nbShortMdcts = 4;
359    }
360    if (mode->nbShortMdcts > 1)
361       mode->overlap = frame_size/mode->nbShortMdcts;
362    else
363       mode->overlap = frame_size/2;
364    
365    compute_allocation_table(mode, res);
366    /*printf ("%d bands\n", mode->nbEBands);*/
367    
368    window = (celt_word16_t*)celt_alloc(mode->overlap*sizeof(celt_word16_t));
369
370 #ifndef FIXED_POINT
371    for (i=0;i<mode->overlap;i++)
372       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
373 #else
374    for (i=0;i<mode->overlap;i++)
375       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)));
376 #endif
377    mode->window = window;
378
379    mode->bits = (const celt_int16_t **)compute_alloc_cache(mode, 1);
380
381    mode->bits_stereo = NULL;
382 #ifndef SHORTCUTS
383    psydecay_init(&mode->psy, MAX_PERIOD/2, mode->Fs);
384 #endif
385    
386    mode->marker_start = MODEVALID;
387    mode->marker_end = MODEVALID;
388 #endif /* !STATIC_MODES */
389    mdct_init(&mode->mdct, 2*mode->mdctSize);
390    mode->fft = pitch_state_alloc(MAX_PERIOD);
391
392    mode->shortMdctSize = mode->mdctSize/mode->nbShortMdcts;
393    mdct_init(&mode->shortMdct, 2*mode->shortMdctSize);
394    mode->shortWindow = mode->window;
395
396    mode->prob = quant_prob_alloc(mode);
397    compute_energy_allocation_table(mode);
398    
399    if (mode->nbChannels>=2)
400       mode->bits_stereo = (const celt_int16_t **)compute_alloc_cache(mode, mode->nbChannels);
401
402    if (error)
403       *error = CELT_OK;
404    return mode;
405 }
406
407 void celt_mode_destroy(CELTMode *mode)
408 {
409 #ifndef STATIC_MODES
410    int i;
411    const celt_int16_t *prevPtr = NULL;
412    for (i=0;i<mode->nbEBands;i++)
413    {
414       if (mode->bits[i] != prevPtr)
415       {
416          prevPtr = mode->bits[i];
417          celt_free((int*)mode->bits[i]);
418       }
419    }
420    celt_free((int**)mode->bits);
421    if (check_mode(mode) != CELT_OK)
422       return;
423    celt_free((int*)mode->eBands);
424    celt_free((int*)mode->pBands);
425    celt_free((int*)mode->allocVectors);
426    
427    celt_free((celt_word16_t*)mode->window);
428
429    mode->marker_start = MODEFREED;
430    mode->marker_end = MODEFREED;
431 #ifndef SHORTCUTS
432    psydecay_clear(&mode->psy);
433 #endif
434 #endif
435    mdct_clear(&mode->mdct);
436    pitch_state_free(mode->fft);
437    quant_prob_free(mode->prob);
438    celt_free((celt_int16_t *)mode->energy_alloc);
439    celt_free((CELTMode *)mode);
440 }
441
442 int check_mode(const CELTMode *mode)
443 {
444    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
445       return CELT_OK;
446    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
447       celt_warning("Using a mode that has already been freed");
448    else
449       celt_warning("This is not a valid CELT mode");
450    return CELT_INVALID_MODE;
451 }