some tuning to fine energy allocation and prevent it from going above 7 bits
[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,  4,  4,  5,  5,  5,  5,  6,  6,  8,  8, 10, 12, 15, 15, 13, 12, 12, 12, 18, 18, 16, 10,  1,
117       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,
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    return eBands;
163 }
164
165 static void compute_pbands(CELTMode *mode, int res)
166 {
167    int i;
168    celt_int16_t *pBands;
169    pBands=celt_alloc(sizeof(celt_int16_t)*(PBANDS+2));
170    mode->nbPBands = PBANDS;
171    for (i=0;i<PBANDS+1;i++)
172    {
173       pBands[i] = (pitch_freq[i]+res/2)/res;
174       if (pBands[i] < mode->eBands[i])
175          pBands[i] = mode->eBands[i];
176    }
177    pBands[PBANDS+1] = mode->eBands[mode->nbEBands+1];
178    for (i=1;i<mode->nbPBands+1;i++)
179    {
180       int j;
181       for (j=0;j<mode->nbEBands;j++)
182          if (mode->eBands[j] <= pBands[i] && mode->eBands[j+1] > pBands[i])
183             break;
184       /*printf ("%d %d\n", i, j);*/
185       if (mode->eBands[j] != pBands[i])
186       {
187          if (pBands[i]-mode->eBands[j] < mode->eBands[j+1]-pBands[i] && 
188              mode->eBands[j] != pBands[i-1])
189             pBands[i] = mode->eBands[j];
190          else
191             pBands[i] = mode->eBands[j+1];
192       }
193    }
194    /*for (i=0;i<mode->nbPBands+2;i++)
195       printf("%d ", pBands[i]);
196    printf ("\n");*/
197    mode->pBands = pBands;
198    mode->pitchEnd = pBands[PBANDS];
199 }
200
201 static void compute_allocation_table(CELTMode *mode, int res)
202 {
203    int i, j, eband;
204    celt_int16_t *allocVectors, *allocEnergy;
205    const int C = CHANNELS(mode);
206
207    mode->nbAllocVectors = BITALLOC_SIZE;
208    allocVectors = celt_alloc(sizeof(celt_int16_t)*(BITALLOC_SIZE*mode->nbEBands));
209    allocEnergy = celt_alloc(sizeof(celt_int16_t)*(mode->nbAllocVectors*(mode->nbEBands+1)));
210    /* Compute per-codec-band allocation from per-critical-band matrix */
211    for (i=0;i<BITALLOC_SIZE;i++)
212    {
213       eband = 0;
214       for (j=0;j<BARK_BANDS;j++)
215       {
216          int edge, low;
217          celt_int32_t alloc;
218          edge = mode->eBands[eband+1]*res;
219          alloc = band_allocation[i*BARK_BANDS+j];
220          alloc = alloc*C*mode->mdctSize/256;
221          if (edge < bark_freq[j+1])
222          {
223             int num, den;
224             num = alloc * (edge-bark_freq[j]);
225             den = bark_freq[j+1]-bark_freq[j];
226             low = (num+den/2)/den;
227             allocVectors[i*mode->nbEBands+eband] += low;
228             eband++;
229             allocVectors[i*mode->nbEBands+eband] += alloc-low;
230          } else {
231             allocVectors[i*mode->nbEBands+eband] += alloc;
232          }
233       }
234    }
235    /* Compute fine energy resolution and update the pulse allocation table to subtract that */
236    for (i=0;i<mode->nbAllocVectors;i++)
237    {
238       int sum = 0;
239       for (j=0;j<mode->nbEBands;j++)
240       {
241          int ebits;
242          int min_bits=0;
243          if (allocVectors[i*mode->nbEBands+j] > 0)
244             min_bits = 1;
245          ebits = min_bits + allocVectors[i*mode->nbEBands+j] / (C*(mode->eBands[j+1]-mode->eBands[j]));
246          if (ebits>7)
247             ebits=7;
248          /* The bits used for fine allocation can't be used for pulses */
249          /* However, we give two "free" bits to all modes to compensate for the fact that some energy
250             resolution is needed regardless of the frame size. */
251          if (ebits>1)
252             allocVectors[i*mode->nbEBands+j] -= C*(ebits-2);
253          if (allocVectors[i*mode->nbEBands+j] < 0)
254             allocVectors[i*mode->nbEBands+j] = 0;
255          sum += ebits;
256          allocEnergy[i*(mode->nbEBands+1)+j] = ebits;
257       }
258       allocEnergy[i*(mode->nbEBands+1)+mode->nbEBands] = sum;
259    }
260    mode->energy_alloc = allocEnergy;
261    mode->allocVectors = allocVectors;
262 }
263
264 #endif /* STATIC_MODES */
265
266 CELTMode *celt_mode_create(celt_int32_t Fs, int channels, int frame_size, int *error)
267 {
268    int i;
269 #ifdef STDIN_TUNING
270    scanf("%d ", &MIN_BINS);
271    scanf("%d ", &BITALLOC_SIZE);
272    band_allocation = celt_alloc(sizeof(int)*BARK_BANDS*BITALLOC_SIZE);
273    for (i=0;i<BARK_BANDS*BITALLOC_SIZE;i++)
274    {
275       scanf("%d ", band_allocation+i);
276    }
277 #endif
278 #ifdef STATIC_MODES
279    const CELTMode *m = NULL;
280    CELTMode *mode=NULL;
281    ALLOC_STACK;
282    for (i=0;i<TOTAL_MODES;i++)
283    {
284       if (Fs == static_mode_list[i]->Fs &&
285           channels == static_mode_list[i]->nbChannels &&
286           frame_size == static_mode_list[i]->mdctSize &&
287           lookahead == static_mode_list[i]->overlap)
288       {
289          m = static_mode_list[i];
290          break;
291       }
292    }
293    if (m == NULL)
294    {
295       celt_warning("Mode not included as part of the static modes");
296       if (error)
297          *error = CELT_BAD_ARG;
298       return NULL;
299    }
300    mode = (CELTMode*)celt_alloc(sizeof(CELTMode));
301    CELT_COPY(mode, m, 1);
302 #else
303    int res;
304    CELTMode *mode;
305    celt_word16_t *window;
306    ALLOC_STACK;
307
308    /* The good thing here is that permutation of the arguments will automatically be invalid */
309    
310    if (Fs < 32000 || Fs > 64000)
311    {
312       celt_warning("Sampling rate must be between 32 kHz and 64 kHz");
313       if (error)
314          *error = CELT_BAD_ARG;
315       return NULL;
316    }
317    if (channels < 0 || channels > 2)
318    {
319       celt_warning("Only mono and stereo supported");
320       if (error)
321          *error = CELT_BAD_ARG;
322       return NULL;
323    }
324    if (frame_size < 64 || frame_size > 512 || frame_size%2!=0)
325    {
326       celt_warning("Only even frame sizes between 64 and 512 are supported");
327       if (error)
328          *error = CELT_BAD_ARG;
329       return NULL;
330    }
331    res = (Fs+frame_size)/(2*frame_size);
332    
333    mode = celt_alloc(sizeof(CELTMode));
334    mode->Fs = Fs;
335    mode->mdctSize = frame_size;
336    mode->nbChannels = channels;
337    mode->eBands = compute_ebands(Fs, frame_size, &mode->nbEBands);
338    compute_pbands(mode, res);
339    mode->ePredCoef = QCONST16(.8f,15);
340    
341    if (frame_size <= 64)
342    {
343       mode->nbShortMdcts = 1;
344    } else if (frame_size <= 256)
345    {
346       mode->nbShortMdcts = 2;
347    } else if (frame_size <= 384)
348    {
349       mode->nbShortMdcts = 3;
350    } else {
351       mode->nbShortMdcts = 4;
352    }
353    if (mode->nbShortMdcts > 1)
354       mode->overlap = frame_size/mode->nbShortMdcts;
355    else
356       mode->overlap = frame_size/2;
357    
358    compute_allocation_table(mode, res);
359    /*printf ("%d bands\n", mode->nbEBands);*/
360    
361    window = (celt_word16_t*)celt_alloc(mode->overlap*sizeof(celt_word16_t));
362
363 #ifndef FIXED_POINT
364    for (i=0;i<mode->overlap;i++)
365       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
366 #else
367    for (i=0;i<mode->overlap;i++)
368       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)));
369 #endif
370    mode->window = window;
371
372    mode->bits = (const celt_int16_t **)compute_alloc_cache(mode, 1);
373
374    mode->bits_stereo = NULL;
375 #ifndef SHORTCUTS
376    psydecay_init(&mode->psy, MAX_PERIOD/2, mode->Fs);
377 #endif
378    
379    mode->marker_start = MODEVALID;
380    mode->marker_end = MODEVALID;
381 #endif /* !STATIC_MODES */
382    mdct_init(&mode->mdct, 2*mode->mdctSize);
383    mode->fft = pitch_state_alloc(MAX_PERIOD);
384
385    mode->shortMdctSize = mode->mdctSize/mode->nbShortMdcts;
386    mdct_init(&mode->shortMdct, 2*mode->shortMdctSize);
387    mode->shortWindow = mode->window;
388
389    mode->prob = quant_prob_alloc(mode);
390    
391    if (mode->nbChannels>=2)
392       mode->bits_stereo = (const celt_int16_t **)compute_alloc_cache(mode, mode->nbChannels);
393
394    if (error)
395       *error = CELT_OK;
396    return mode;
397 }
398
399 void celt_mode_destroy(CELTMode *mode)
400 {
401 #ifndef STATIC_MODES
402    int i;
403    const celt_int16_t *prevPtr = NULL;
404    for (i=0;i<mode->nbEBands;i++)
405    {
406       if (mode->bits[i] != prevPtr)
407       {
408          prevPtr = mode->bits[i];
409          celt_free((int*)mode->bits[i]);
410       }
411    }
412    celt_free((int**)mode->bits);
413    if (check_mode(mode) != CELT_OK)
414       return;
415    celt_free((int*)mode->eBands);
416    celt_free((int*)mode->pBands);
417    celt_free((int*)mode->allocVectors);
418    
419    celt_free((celt_word16_t*)mode->window);
420
421    mode->marker_start = MODEFREED;
422    mode->marker_end = MODEFREED;
423 #ifndef SHORTCUTS
424    psydecay_clear(&mode->psy);
425 #endif
426 #endif
427    mdct_clear(&mode->mdct);
428    pitch_state_free(mode->fft);
429    quant_prob_free(mode->prob);
430    celt_free((celt_int16_t *)mode->energy_alloc);
431    celt_free((CELTMode *)mode);
432 }
433
434 int check_mode(const CELTMode *mode)
435 {
436    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
437       return CELT_OK;
438    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
439       celt_warning("Using a mode that has already been freed");
440    else
441       celt_warning("This is not a valid CELT mode");
442    return CELT_INVALID_MODE;
443 }