Fixed pitchEnd wrt to variable frame size. It should (sort of) all work now
[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_LOOKAHEAD:
65          *value = mode->overlap;
66          break;
67       case CELT_GET_BITSTREAM_VERSION:
68          *value = CELT_BITSTREAM_VERSION;
69          break;
70       case CELT_GET_SAMPLE_RATE:
71          *value = mode->Fs;
72          break;
73       default:
74          return CELT_UNIMPLEMENTED;
75    }
76    return CELT_OK;
77 }
78
79 #ifndef STATIC_MODES
80
81 /* Defining 25 critical bands for the full 0-20 kHz audio bandwidth
82    Taken from http://ccrma.stanford.edu/~jos/bbt/Bark_Frequency_Scale.html */
83 #define BARK_BANDS 25
84 static const celt_int16 bark_freq[BARK_BANDS+1] = {
85       0,   100,   200,   300,   400,
86     510,   630,   770,   920,  1080,
87    1270,  1480,  1720,  2000,  2320,
88    2700,  3150,  3700,  4400,  5300,
89    6400,  7700,  9500, 12000, 15500,
90   20000};
91
92 /* This allocation table is per critical band. When creating a mode, the bits get added together 
93    into the codec bands, which are sometimes larger than one critical band at low frequency */
94
95 #ifdef STDIN_TUNING
96 int BITALLOC_SIZE;
97 int *band_allocation;
98 #else
99 #define BITALLOC_SIZE 12
100 static const int band_allocation[BARK_BANDS*BITALLOC_SIZE] = 
101    /* 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  */
102    {  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*/
103       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*/
104       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*/
105       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*/
106       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*/
107       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*/
108       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*/
109       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*/
110       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*/
111       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*/
112       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*/
113       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*/
114    };
115 #endif
116
117 static celt_int16 *compute_ebands(celt_int32 Fs, int frame_size, int res, int *nbEBands)
118 {
119    celt_int16 *eBands;
120    int i, lin, low, high, nBark, offset=0;
121
122    /* Find the number of critical bands supported by our sampling rate */
123    for (nBark=1;nBark<BARK_BANDS;nBark++)
124     if (bark_freq[nBark+1]*2 >= Fs)
125        break;
126
127    /* Find where the linear part ends (i.e. where the spacing is more than min_width */
128    for (lin=0;lin<nBark;lin++)
129       if (bark_freq[lin+1]-bark_freq[lin] >= res)
130          break;
131
132    low = (bark_freq[lin]+res/2)/res;
133    high = nBark-lin;
134    *nbEBands = low+high;
135    eBands = celt_alloc(sizeof(celt_int16)*(*nbEBands+2));
136    
137    if (eBands==NULL)
138       return NULL;
139    
140    /* Linear spacing (min_width) */
141    for (i=0;i<low;i++)
142       eBands[i] = i;
143    if (low>0)
144       offset = eBands[low-1]*res - bark_freq[lin-1];
145    /* Spacing follows critical bands */
146    for (i=0;i<high;i++)
147    {
148       int target = bark_freq[lin+i];
149       eBands[i+low] = (target+(offset+res)/2)/res;
150       offset = eBands[i+low]*res - target;
151    }
152    /* Enforce the minimum spacing at the boundary */
153    for (i=0;i<*nbEBands;i++)
154       if (eBands[i] < i)
155          eBands[i] = i;
156    eBands[*nbEBands] = (bark_freq[nBark]+res/2)/res;
157    eBands[*nbEBands+1] = frame_size;
158    if (eBands[*nbEBands] > eBands[*nbEBands+1])
159       eBands[*nbEBands] = eBands[*nbEBands+1];
160    for (i=1;i<*nbEBands-1;i++)
161    {
162       if (eBands[i+1]-eBands[i] < eBands[i]-eBands[i-1])
163       {
164          eBands[i] -= (2*eBands[i]-eBands[i-1]-eBands[i+1])/2;
165       }
166    }
167    /*for (i=0;i<=*nbEBands+1;i++)
168       printf ("%d ", eBands[i]);
169    printf ("\n");
170    exit(1);*/
171    /* FIXME: Remove last band if too small */
172    return eBands;
173 }
174
175 static void compute_allocation_table(CELTMode *mode, int res)
176 {
177    int i, j, nBark;
178    celt_int16 *allocVectors;
179
180    /* Find the number of critical bands supported by our sampling rate */
181    for (nBark=1;nBark<BARK_BANDS;nBark++)
182     if (bark_freq[nBark+1]*2 >= mode->Fs)
183        break;
184
185    mode->nbAllocVectors = BITALLOC_SIZE;
186    allocVectors = celt_alloc(sizeof(celt_int16)*(BITALLOC_SIZE*mode->nbEBands));
187    if (allocVectors==NULL)
188       return;
189    /* Compute per-codec-band allocation from per-critical-band matrix */
190    for (i=0;i<BITALLOC_SIZE;i++)
191    {
192       celt_int32 current = 0;
193       int eband = 0;
194       for (j=0;j<nBark;j++)
195       {
196          int edge, low, high;
197          celt_int32 alloc;
198
199          alloc = mode->shortMdctSize*band_allocation[i*BARK_BANDS+j];
200          low = bark_freq[j];
201          high = bark_freq[j+1];
202
203          edge = mode->eBands[eband+1]*res;
204          while (edge <= high && eband < mode->nbEBands)
205          {
206             celt_int32 num;
207             int den, bits;
208             num = alloc * (edge-low);
209             den = high-low;
210             /* Divide with rounding */
211             bits = (2*num+den)/(2*den);
212             allocVectors[i*mode->nbEBands+eband] = (current+bits+128)>>(8-BITRES);
213             /* Remove one bit from every band -- FIXME: this is just a temporary hack*/
214             allocVectors[i*mode->nbEBands+eband] -= 1<<BITRES;
215             if (allocVectors[i*mode->nbEBands+eband]<0)
216                allocVectors[i*mode->nbEBands+eband]=0;
217             /* Remove the part of the band we just allocated */
218             low = edge;
219             alloc -= bits;
220
221             /* Move to next eband */
222             current = 0;
223             eband++;
224             edge = mode->eBands[eband+1]*res;
225          }
226          current += alloc;
227       }
228       if (eband < mode->nbEBands)
229       {
230          allocVectors[i*mode->nbEBands+eband] = (current+128)>>(8-BITRES);
231          /* Same hack as above FIXME: again */
232          allocVectors[i*mode->nbEBands+eband] -= 1<<BITRES;
233          if (allocVectors[i*mode->nbEBands+eband]<0)
234             allocVectors[i*mode->nbEBands+eband]=0;
235       }
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    
317    mode = celt_alloc(sizeof(CELTMode));
318    if (mode==NULL)
319       goto failure;
320    mode->marker_start = MODEPARTIAL;
321    mode->Fs = Fs;
322    mode->mdctSize = frame_size;
323    mode->ePredCoef = QCONST16(.8f,15);
324
325    if (frame_size >= 640 && (frame_size%16)==0)
326    {
327      mode->nbShortMdcts = 8;
328    } else if (frame_size >= 320 && (frame_size%8)==0)
329    {
330      mode->nbShortMdcts = 4;
331    } else if (frame_size >= 120 && (frame_size%4)==0)
332    {
333      mode->nbShortMdcts = 2;
334    } else
335    {
336      mode->nbShortMdcts = 1;
337    }
338
339    mode->shortMdctSize = mode->mdctSize/mode->nbShortMdcts;
340    res = (mode->Fs+mode->shortMdctSize)/(2*mode->shortMdctSize);
341
342    mode->eBands = compute_ebands(Fs, mode->shortMdctSize, res, &mode->nbEBands);
343    if (mode->eBands==NULL)
344       goto failure;
345
346    mode->pitchEnd = 4000*(celt_int32)mode->shortMdctSize/Fs;
347    
348    /* Overlap must be divisible by 4 */
349    if (mode->nbShortMdcts > 1)
350       mode->overlap = (mode->shortMdctSize>>2)<<2;
351    else
352       mode->overlap = (frame_size>>3)<<2;
353
354
355    compute_allocation_table(mode, res);
356    if (mode->allocVectors==NULL)
357       goto failure;
358    
359    window = (celt_word16*)celt_alloc(mode->overlap*sizeof(celt_word16));
360    if (window==NULL)
361       goto failure;
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,floor(.5+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    for (i=0;(1<<i)<=mode->nbShortMdcts;i++)
373       mode->bits[i] = (const celt_int16 **)compute_alloc_cache(mode, 1, 1<<i);
374    if (mode->bits==NULL)
375       goto failure;
376
377    logN = (celt_int16*)celt_alloc(mode->nbEBands*sizeof(celt_int16));
378    if (logN==NULL)
379       goto failure;
380
381    for (i=0;i<mode->nbEBands;i++)
382       logN[i] = log2_frac(mode->nbShortMdcts*(mode->eBands[i+1]-mode->eBands[i]), BITRES);
383    mode->logN = logN;
384 #endif /* !STATIC_MODES */
385
386    for (i=0;(1<<i)<=mode->nbShortMdcts;i++)
387    {
388       clt_mdct_init(&mode->mdct[i], 2*mode->shortMdctSize<<i);
389       if ((mode->mdct[i].trig==NULL)
390 #ifndef ENABLE_TI_DSPLIB55
391            || (mode->mdct[i].kfft==NULL)
392 #endif
393       )
394         goto failure;
395    }
396    mode->prob = quant_prob_alloc(mode);
397    if (mode->prob==NULL)
398      goto failure;
399
400    mode->marker_start = MODEVALID;
401    mode->marker_end   = MODEVALID;
402    if (error)
403       *error = CELT_OK;
404    return mode;
405 failure: 
406    if (error)
407       *error = CELT_INVALID_MODE;
408    if (mode!=NULL)
409       celt_mode_destroy(mode);
410    return NULL;
411 }
412
413 void celt_mode_destroy(CELTMode *mode)
414 {
415    int i, m;
416    const celt_int16 *prevPtr = NULL;
417    if (mode == NULL)
418    {
419       celt_warning("NULL passed to celt_mode_destroy");
420       return;
421    }
422
423    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
424    {
425       celt_warning("Freeing a mode which has already been freed"); 
426       return;
427    }
428
429    if (mode->marker_start != MODEVALID && mode->marker_start != MODEPARTIAL)
430    {
431       celt_warning("This is not a valid CELT mode structure");
432       return;  
433    }
434    mode->marker_start = MODEFREED;
435 #ifndef STATIC_MODES
436    for (m=0;(1<<m)<=mode->nbShortMdcts;m++)
437    {
438       if (mode->bits[m]!=NULL)
439       {
440          for (i=0;i<mode->nbEBands;i++)
441          {
442             if (mode->bits[m][i] != prevPtr)
443             {
444                prevPtr = mode->bits[m][i];
445                celt_free((int*)mode->bits[m][i]);
446             }
447          }
448       }
449       celt_free((celt_int16**)mode->bits[m]);
450    }
451    celt_free((celt_int16*)mode->eBands);
452    celt_free((celt_int16*)mode->allocVectors);
453    
454    celt_free((celt_word16*)mode->window);
455    celt_free((celt_int16*)mode->logN);
456
457 #endif
458    for (i=0;(1<<i)<=mode->nbShortMdcts;i++)
459       clt_mdct_clear(&mode->mdct[i]);
460
461    quant_prob_free(mode->prob);
462    mode->marker_end = MODEFREED;
463    celt_free((CELTMode *)mode);
464 }
465
466 int check_mode(const CELTMode *mode)
467 {
468    if (mode==NULL)
469       return CELT_INVALID_MODE;
470    if (mode->marker_start == MODEVALID && mode->marker_end == MODEVALID)
471       return CELT_OK;
472    if (mode->marker_start == MODEFREED || mode->marker_end == MODEFREED)
473       celt_warning("Using a mode that has already been freed");
474    else
475       celt_warning("This is not a valid CELT mode");
476    return CELT_INVALID_MODE;
477 }