Allow all even frame sizes, change the selection of number of short MDCTs per frame...
[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 12
108 static const int band_allocation[BARK_BANDS*BITALLOC_SIZE] = 
109    {  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,
110       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,
111       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,
112       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,
113       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,
114       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,
115       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,
116       5,  5,  5,  5,  5,  5,  5,  6,  6,  6,  8,  8, 10, 12, 12, 11, 11, 17, 12, 15, 15, 20, 18, 10,  1,
117       8,  7,  7,  7,  7,  7,  8,  8,  9, 10, 11, 12, 14, 17, 18, 21, 22, 27, 29, 39, 37, 38, 40, 35,  1,
118       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,
119       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,
120      12, 12, 12, 12, 12, 13, 15, 18, 22, 30, 32, 35, 40, 45, 55, 62, 66, 70, 85, 90, 92, 92, 92, 92, 92,
121    };
122 #endif
123
124 static celt_int16_t *compute_ebands(celt_int32_t Fs, int frame_size, int *nbEBands)
125 {
126    celt_int16_t *eBands;
127    int i, res, min_width, lin, low, high;
128    res = (Fs+frame_size)/(2*frame_size);
129    min_width = MIN_BINS*res;
130    /*printf ("min_width = %d\n", min_width);*/
131
132    /* Find where the linear part ends (i.e. where the spacing is more than min_width */
133    for (lin=0;lin<BARK_BANDS;lin++)
134       if (bark_freq[lin+1]-bark_freq[lin] >= min_width)
135          break;
136    
137    /*printf ("lin = %d (%d Hz)\n", lin, bark_freq[lin]);*/
138    low = ((bark_freq[lin]/res)+(MIN_BINS-1))/MIN_BINS;
139    high = BARK_BANDS-lin;
140    *nbEBands = low+high;
141    eBands = celt_alloc(sizeof(celt_int16_t)*(*nbEBands+2));
142    
143    /* Linear spacing (min_width) */
144    for (i=0;i<low;i++)
145       eBands[i] = MIN_BINS*i;
146    /* Spacing follows critical bands */
147    for (i=0;i<high;i++)
148       eBands[i+low] = (bark_freq[lin+i]+res/2)/res;
149    /* Enforce the minimum spacing at the boundary */
150    for (i=0;i<*nbEBands;i++)
151       if (eBands[i] < MIN_BINS*i)
152          eBands[i] = MIN_BINS*i;
153    eBands[*nbEBands] = (bark_freq[BARK_BANDS]+res/2)/res;
154    eBands[*nbEBands+1] = frame_size;
155    if (eBands[*nbEBands] > eBands[*nbEBands+1])
156       eBands[*nbEBands] = eBands[*nbEBands+1];
157    
158    /* FIXME: Remove last band if too small */
159    /*for (i=0;i<*nbEBands+2;i++)
160       printf("%d ", eBands[i]);
161    printf ("\n");
162    exit(1);*/
163    return eBands;
164 }
165
166 static void compute_pbands(CELTMode *mode, int res)
167 {
168    int i;
169    celt_int16_t *pBands;
170    pBands=celt_alloc(sizeof(celt_int16_t)*(PBANDS+2));
171    mode->nbPBands = PBANDS;
172    for (i=0;i<PBANDS+1;i++)
173    {
174       pBands[i] = (pitch_freq[i]+res/2)/res;
175       if (pBands[i] < mode->eBands[i])
176          pBands[i] = mode->eBands[i];
177    }
178    pBands[PBANDS+1] = mode->eBands[mode->nbEBands+1];
179    for (i=1;i<mode->nbPBands+1;i++)
180    {
181       int j;
182       for (j=0;j<mode->nbEBands;j++)
183          if (mode->eBands[j] <= pBands[i] && mode->eBands[j+1] > pBands[i])
184             break;
185       /*printf ("%d %d\n", i, j);*/
186       if (mode->eBands[j] != pBands[i])
187       {
188          if (pBands[i]-mode->eBands[j] < mode->eBands[j+1]-pBands[i] && 
189              mode->eBands[j] != pBands[i-1])
190             pBands[i] = mode->eBands[j];
191          else
192             pBands[i] = mode->eBands[j+1];
193       }
194    }
195    /*for (i=0;i<mode->nbPBands+2;i++)
196       printf("%d ", pBands[i]);
197    printf ("\n");*/
198    mode->pBands = pBands;
199    mode->pitchEnd = pBands[PBANDS];
200 }
201
202 static void compute_allocation_table(CELTMode *mode, int res)
203 {
204    int i, j, eband;
205    celt_int16_t *allocVectors, *allocEnergy;
206    const int C = CHANNELS(mode);
207
208    mode->nbAllocVectors = BITALLOC_SIZE;
209    allocVectors = celt_alloc(sizeof(celt_int16_t)*(BITALLOC_SIZE*mode->nbEBands));
210    allocEnergy = celt_alloc(sizeof(celt_int16_t)*(mode->nbAllocVectors*(mode->nbEBands+1)));
211    /* Compute per-codec-band allocation from per-critical-band matrix */
212    for (i=0;i<BITALLOC_SIZE;i++)
213    {
214       eband = 0;
215       for (j=0;j<BARK_BANDS;j++)
216       {
217          int edge, low;
218          celt_int32_t alloc;
219          edge = mode->eBands[eband+1]*res;
220          alloc = band_allocation[i*BARK_BANDS+j];
221          alloc = alloc*C*mode->mdctSize/256;
222          if (edge < bark_freq[j+1])
223          {
224             int num, den;
225             num = alloc * (edge-bark_freq[j]);
226             den = bark_freq[j+1]-bark_freq[j];
227             low = (num+den/2)/den;
228             allocVectors[i*mode->nbEBands+eband] += low;
229             eband++;
230             allocVectors[i*mode->nbEBands+eband] += alloc-low;
231          } else {
232             allocVectors[i*mode->nbEBands+eband] += alloc;
233          }
234       }
235    }
236    /* Compute fine energy resolution and update the pulse allocation table to subtract that */
237    for (i=0;i<mode->nbAllocVectors;i++)
238    {
239       int sum = 0;
240       for (j=0;j<mode->nbEBands;j++)
241       {
242          int ebits;
243          int min_bits=0;
244          if (allocVectors[i*mode->nbEBands+j] > 0)
245             min_bits = 1;
246          ebits = IMAX(min_bits , allocVectors[i*mode->nbEBands+j] / (C*(mode->eBands[j+1]-mode->eBands[j])));
247          if (ebits>7)
248             ebits=7;
249          /* The bits used for fine allocation can't be used for pulses */
250          /* However, we give two "free" bits to all modes to compensate for the fact that some energy
251             resolution is needed regardless of the frame size. */
252          if (ebits>1)
253             allocVectors[i*mode->nbEBands+j] -= C*(ebits-2);
254          if (allocVectors[i*mode->nbEBands+j] < 0)
255             allocVectors[i*mode->nbEBands+j] = 0;
256          sum += ebits;
257          allocEnergy[i*(mode->nbEBands+1)+j] = ebits;
258       }
259       allocEnergy[i*(mode->nbEBands+1)+mode->nbEBands] = sum;
260    }
261    mode->energy_alloc = allocEnergy;
262    mode->allocVectors = allocVectors;
263 }
264
265 #endif /* STATIC_MODES */
266
267 CELTMode *celt_mode_create(celt_int32_t Fs, int channels, int frame_size, int *error)
268 {
269    int i;
270 #ifdef STDIN_TUNING
271    scanf("%d ", &MIN_BINS);
272    scanf("%d ", &BITALLOC_SIZE);
273    band_allocation = celt_alloc(sizeof(int)*BARK_BANDS*BITALLOC_SIZE);
274    for (i=0;i<BARK_BANDS*BITALLOC_SIZE;i++)
275    {
276       scanf("%d ", band_allocation+i);
277    }
278 #endif
279 #ifdef STATIC_MODES
280    const CELTMode *m = NULL;
281    CELTMode *mode=NULL;
282    ALLOC_STACK;
283    for (i=0;i<TOTAL_MODES;i++)
284    {
285       if (Fs == static_mode_list[i]->Fs &&
286           channels == static_mode_list[i]->nbChannels &&
287           frame_size == static_mode_list[i]->mdctSize &&
288           lookahead == static_mode_list[i]->overlap)
289       {
290          m = static_mode_list[i];
291          break;
292       }
293    }
294    if (m == NULL)
295    {
296       celt_warning("Mode not included as part of the static modes");
297       if (error)
298          *error = CELT_BAD_ARG;
299       return NULL;
300    }
301    mode = (CELTMode*)celt_alloc(sizeof(CELTMode));
302    CELT_COPY(mode, m, 1);
303 #else
304    int res;
305    CELTMode *mode;
306    celt_word16_t *window;
307    ALLOC_STACK;
308
309    /* The good thing here is that permutation of the arguments will automatically be invalid */
310    
311    if (Fs < 32000 || Fs > 64000)
312    {
313       celt_warning("Sampling rate must be between 32 kHz and 64 kHz");
314       if (error)
315          *error = CELT_BAD_ARG;
316       return NULL;
317    }
318    if (channels < 0 || channels > 2)
319    {
320       celt_warning("Only mono and stereo supported");
321       if (error)
322          *error = CELT_BAD_ARG;
323       return NULL;
324    }
325    if (frame_size < 64 || frame_size > 512 || frame_size%2!=0)
326    {
327       celt_warning("Only even frame sizes between 64 and 512 are supported");
328       if (error)
329          *error = CELT_BAD_ARG;
330       return NULL;
331    }
332    res = (Fs+frame_size)/(2*frame_size);
333    
334    mode = celt_alloc(sizeof(CELTMode));
335    mode->Fs = Fs;
336    mode->mdctSize = frame_size;
337    mode->nbChannels = channels;
338    mode->eBands = compute_ebands(Fs, frame_size, &mode->nbEBands);
339    compute_pbands(mode, res);
340    mode->ePredCoef = QCONST16(.8f,15);
341
342    if (frame_size > 384 && (frame_size%8)==0)
343    {
344      mode->nbShortMdcts = 4;
345    } else if (frame_size > 384 && (frame_size%10)==0)
346    {
347      mode->nbShortMdcts = 5;
348    } else if (frame_size > 256 && (frame_size%6)==0)
349    {
350      mode->nbShortMdcts = 3;
351    } else if (frame_size > 256 && (frame_size%8)==0)
352    {
353      mode->nbShortMdcts = 4;
354    } else if (frame_size > 64 && (frame_size%4)==0)
355    {
356      mode->nbShortMdcts = 2;
357    } else if (frame_size > 128 && (frame_size%6)==0)
358    {
359      mode->nbShortMdcts = 3;
360    } else
361    {
362      mode->nbShortMdcts = 1;
363    }
364
365    if (mode->nbShortMdcts > 1)
366       mode->overlap = ((frame_size/mode->nbShortMdcts)>>2)<<2; /* Overlap must be divisible by 4 */
367    else
368       mode->overlap = (frame_size>>3)<<2;
369
370    compute_allocation_table(mode, res);
371    /*printf ("%d bands\n", mode->nbEBands);*/
372    
373    window = (celt_word16_t*)celt_alloc(mode->overlap*sizeof(celt_word16_t));
374
375 #ifndef FIXED_POINT
376    for (i=0;i<mode->overlap;i++)
377       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
378 #else
379    for (i=0;i<mode->overlap;i++)
380       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)));
381 #endif
382    mode->window = window;
383
384    mode->bits = (const celt_int16_t **)compute_alloc_cache(mode, 1);
385
386    mode->bits_stereo = NULL;
387 #ifndef SHORTCUTS
388    psydecay_init(&mode->psy, MAX_PERIOD/2, mode->Fs);
389 #endif
390    
391    mode->marker_start = MODEVALID;
392    mode->marker_end = MODEVALID;
393 #endif /* !STATIC_MODES */
394    mdct_init(&mode->mdct, 2*mode->mdctSize);
395    mode->fft = pitch_state_alloc(MAX_PERIOD);
396
397    mode->shortMdctSize = mode->mdctSize/mode->nbShortMdcts;
398    mdct_init(&mode->shortMdct, 2*mode->shortMdctSize);
399    mode->shortWindow = mode->window;
400
401    mode->prob = quant_prob_alloc(mode);
402    
403    if (mode->nbChannels>=2)
404       mode->bits_stereo = (const celt_int16_t **)compute_alloc_cache(mode, mode->nbChannels);
405
406    if (error)
407       *error = CELT_OK;
408    return mode;
409 }
410
411 void celt_mode_destroy(CELTMode *mode)
412 {
413 #ifndef STATIC_MODES
414    int i;
415    const celt_int16_t *prevPtr = NULL;
416    for (i=0;i<mode->nbEBands;i++)
417    {
418       if (mode->bits[i] != prevPtr)
419       {
420          prevPtr = mode->bits[i];
421          celt_free((int*)mode->bits[i]);
422       }
423    }
424    celt_free((int**)mode->bits);
425    if (check_mode(mode) != CELT_OK)
426       return;
427    celt_free((int*)mode->eBands);
428    celt_free((int*)mode->pBands);
429    celt_free((int*)mode->allocVectors);
430    
431    celt_free((celt_word16_t*)mode->window);
432
433    mode->marker_start = MODEFREED;
434    mode->marker_end = MODEFREED;
435 #ifndef SHORTCUTS
436    psydecay_clear(&mode->psy);
437 #endif
438 #endif
439    mdct_clear(&mode->mdct);
440    mdct_clear(&mode->shortMdct);
441    pitch_state_free(mode->fft);
442    quant_prob_free(mode->prob);
443    celt_free((celt_int16_t *)mode->energy_alloc);
444    celt_free((CELTMode *)mode);
445 }
446
447 int check_mode(const CELTMode *mode)
448 {
449    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
450       return CELT_OK;
451    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
452       celt_warning("Using a mode that has already been freed");
453    else
454       celt_warning("This is not a valid CELT mode");
455    return CELT_INVALID_MODE;
456 }