Better bit allocation for all frame sizes that are not equal to 256.
[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;
212          celt_int32_t alloc;
213          edge = mode->eBands[eband+1]*res;
214          alloc = band_allocation[i*BARK_BANDS+j];
215          if (mode->nbChannels == 2)
216             alloc = alloc*3*mode->mdctSize/512;
217          else
218             alloc = alloc*mode->mdctSize/256;
219          if (edge < bark_freq[j+1])
220          {
221             int num, den;
222             num = alloc * (edge-bark_freq[j]);
223             den = bark_freq[j+1]-bark_freq[j];
224             low = (num+den/2)/den;
225             allocVectors[i*mode->nbEBands+eband] += low;
226             eband++;
227             allocVectors[i*mode->nbEBands+eband] += alloc-low;
228          } else {
229             allocVectors[i*mode->nbEBands+eband] += alloc;
230          }
231       }
232    }
233    /*for (i=0;i<BITALLOC_SIZE;i++)
234    {
235       for (j=0;j<mode->nbEBands;j++)
236          printf ("%2d ", allocVectors[i*mode->nbEBands+j]);
237       printf ("\n");
238    }*/
239    mode->allocVectors = allocVectors;
240 }
241
242 #endif /* STATIC_MODES */
243
244 static void compute_energy_allocation_table(CELTMode *mode)
245 {
246    int i, j;
247    celt_int16_t *alloc;
248    
249    alloc = celt_alloc(sizeof(celt_int16_t)*(mode->nbAllocVectors*(mode->nbEBands+1)));
250    for (i=0;i<mode->nbAllocVectors;i++)
251    {
252       int sum = 0;
253       int min_bits = 1;
254       if (mode->allocVectors[i*mode->nbEBands]>12)
255          min_bits = 2;
256       if (mode->allocVectors[i*mode->nbEBands]>24)
257          min_bits = 3;
258       for (j=0;j<mode->nbEBands;j++)
259       {
260          alloc[i*(mode->nbEBands+1)+j] = mode->allocVectors[i*mode->nbEBands+j]
261                                          / (mode->eBands[j+1]-mode->eBands[j]-1);
262          if (alloc[i*(mode->nbEBands+1)+j]<min_bits)
263             alloc[i*(mode->nbEBands+1)+j] = min_bits;
264          if (alloc[i*(mode->nbEBands+1)+j]>7)
265             alloc[i*(mode->nbEBands+1)+j] = 7;
266          sum += alloc[i*(mode->nbEBands+1)+j];
267          /*printf ("%d ", alloc[i*(mode->nbEBands+1)+j]);*/
268          /*printf ("%f ", mode->allocVectors[i*mode->nbEBands+j]*1.f/(mode->eBands[j+1]-mode->eBands[j]-1));*/
269       }
270       alloc[i*(mode->nbEBands+1)+mode->nbEBands] = sum;
271       /*printf ("\n");*/
272    }
273    mode->energy_alloc = alloc;
274 }
275
276 CELTMode *celt_mode_create(celt_int32_t Fs, int channels, int frame_size, int *error)
277 {
278    int i;
279 #ifdef STDIN_TUNING
280    scanf("%d ", &MIN_BINS);
281    scanf("%d ", &BITALLOC_SIZE);
282    band_allocation = celt_alloc(sizeof(int)*BARK_BANDS*BITALLOC_SIZE);
283    for (i=0;i<BARK_BANDS*BITALLOC_SIZE;i++)
284    {
285       scanf("%d ", band_allocation+i);
286    }
287 #endif
288 #ifdef STATIC_MODES
289    const CELTMode *m = NULL;
290    CELTMode *mode=NULL;
291    ALLOC_STACK;
292    for (i=0;i<TOTAL_MODES;i++)
293    {
294       if (Fs == static_mode_list[i]->Fs &&
295           channels == static_mode_list[i]->nbChannels &&
296           frame_size == static_mode_list[i]->mdctSize &&
297           lookahead == static_mode_list[i]->overlap)
298       {
299          m = static_mode_list[i];
300          break;
301       }
302    }
303    if (m == NULL)
304    {
305       celt_warning("Mode not included as part of the static modes");
306       if (error)
307          *error = CELT_BAD_ARG;
308       return NULL;
309    }
310    mode = (CELTMode*)celt_alloc(sizeof(CELTMode));
311    CELT_COPY(mode, m, 1);
312 #else
313    int res;
314    CELTMode *mode;
315    celt_word16_t *window;
316    ALLOC_STACK;
317
318    /* The good thing here is that permutation of the arguments will automatically be invalid */
319    
320    if (Fs < 32000 || Fs > 64000)
321    {
322       celt_warning("Sampling rate must be between 32 kHz and 64 kHz");
323       if (error)
324          *error = CELT_BAD_ARG;
325       return NULL;
326    }
327    if (channels < 0 || channels > 2)
328    {
329       celt_warning("Only mono and stereo supported");
330       if (error)
331          *error = CELT_BAD_ARG;
332       return NULL;
333    }
334    if (frame_size < 64 || frame_size > 512 || frame_size%2!=0)
335    {
336       celt_warning("Only even frame sizes between 64 and 512 are supported");
337       if (error)
338          *error = CELT_BAD_ARG;
339       return NULL;
340    }
341    res = (Fs+frame_size)/(2*frame_size);
342    
343    mode = celt_alloc(sizeof(CELTMode));
344    mode->Fs = Fs;
345    mode->mdctSize = frame_size;
346    mode->nbChannels = channels;
347    mode->eBands = compute_ebands(Fs, frame_size, &mode->nbEBands);
348    compute_pbands(mode, res);
349    mode->ePredCoef = QCONST16(.8f,15);
350    
351    if (frame_size <= 64)
352    {
353       mode->nbShortMdcts = 1;
354    } else if (frame_size <= 256)
355    {
356       mode->nbShortMdcts = 2;
357    } else if (frame_size <= 384)
358    {
359       mode->nbShortMdcts = 3;
360    } else {
361       mode->nbShortMdcts = 4;
362    }
363    if (mode->nbShortMdcts > 1)
364       mode->overlap = frame_size/mode->nbShortMdcts;
365    else
366       mode->overlap = frame_size/2;
367    
368    compute_allocation_table(mode, res);
369    /*printf ("%d bands\n", mode->nbEBands);*/
370    
371    window = (celt_word16_t*)celt_alloc(mode->overlap*sizeof(celt_word16_t));
372
373 #ifndef FIXED_POINT
374    for (i=0;i<mode->overlap;i++)
375       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
376 #else
377    for (i=0;i<mode->overlap;i++)
378       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)));
379 #endif
380    mode->window = window;
381
382    mode->bits = (const celt_int16_t **)compute_alloc_cache(mode, 1);
383
384    mode->bits_stereo = NULL;
385 #ifndef SHORTCUTS
386    psydecay_init(&mode->psy, MAX_PERIOD/2, mode->Fs);
387 #endif
388    
389    mode->marker_start = MODEVALID;
390    mode->marker_end = MODEVALID;
391 #endif /* !STATIC_MODES */
392    mdct_init(&mode->mdct, 2*mode->mdctSize);
393    mode->fft = pitch_state_alloc(MAX_PERIOD);
394
395    mode->shortMdctSize = mode->mdctSize/mode->nbShortMdcts;
396    mdct_init(&mode->shortMdct, 2*mode->shortMdctSize);
397    mode->shortWindow = mode->window;
398
399    mode->prob = quant_prob_alloc(mode);
400    compute_energy_allocation_table(mode);
401    
402    if (mode->nbChannels>=2)
403       mode->bits_stereo = (const celt_int16_t **)compute_alloc_cache(mode, mode->nbChannels);
404
405    if (error)
406       *error = CELT_OK;
407    return mode;
408 }
409
410 void celt_mode_destroy(CELTMode *mode)
411 {
412 #ifndef STATIC_MODES
413    int i;
414    const celt_int16_t *prevPtr = NULL;
415    for (i=0;i<mode->nbEBands;i++)
416    {
417       if (mode->bits[i] != prevPtr)
418       {
419          prevPtr = mode->bits[i];
420          celt_free((int*)mode->bits[i]);
421       }
422    }
423    celt_free((int**)mode->bits);
424    if (check_mode(mode) != CELT_OK)
425       return;
426    celt_free((int*)mode->eBands);
427    celt_free((int*)mode->pBands);
428    celt_free((int*)mode->allocVectors);
429    
430    celt_free((celt_word16_t*)mode->window);
431
432    mode->marker_start = MODEFREED;
433    mode->marker_end = MODEFREED;
434 #ifndef SHORTCUTS
435    psydecay_clear(&mode->psy);
436 #endif
437 #endif
438    mdct_clear(&mode->mdct);
439    pitch_state_free(mode->fft);
440    quant_prob_free(mode->prob);
441    celt_free((celt_int16_t *)mode->energy_alloc);
442    celt_free((CELTMode *)mode);
443 }
444
445 int check_mode(const CELTMode *mode)
446 {
447    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
448       return CELT_OK;
449    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
450       celt_warning("Using a mode that has already been freed");
451    else
452       celt_warning("This is not a valid CELT mode");
453    return CELT_INVALID_MODE;
454 }