Adds a fuzzing mode that causes the encoder to make random decisions
[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    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20    A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR
21    CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
24    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
25    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
26    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30 #ifdef HAVE_CONFIG_H
31 #include "config.h"
32 #endif
33
34 #include "celt.h"
35 #include "modes.h"
36 #include "rate.h"
37 #include "os_support.h"
38 #include "stack_alloc.h"
39 #include "quant_bands.h"
40
41 static const opus_int16 eband5ms[] = {
42 /*0  200 400 600 800  1k 1.2 1.4 1.6  2k 2.4 2.8 3.2  4k 4.8 5.6 6.8  8k 9.6 12k 15.6 */
43   0,  1,  2,  3,  4,  5,  6,  7,  8, 10, 12, 14, 16, 20, 24, 28, 34, 40, 48, 60, 78, 100
44 };
45
46 /* Alternate tuning (partially derived from Vorbis) */
47 #define BITALLOC_SIZE 11
48 /* Bit allocation table in units of 1/32 bit/sample (0.1875 dB SNR) */
49 static const unsigned char band_allocation[] = {
50 /*0  200 400 600 800  1k 1.2 1.4 1.6  2k 2.4 2.8 3.2  4k 4.8 5.6 6.8  8k 9.6 12k 15.6 */
51   0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
52  90, 80, 75, 69, 63, 56, 49, 40, 34, 29, 20, 18, 10,  0,  0,  0,  0,  0,  0,  0,  0,
53 110,100, 90, 84, 78, 71, 65, 58, 51, 45, 39, 32, 26, 20, 12,  0,  0,  0,  0,  0,  0,
54 118,110,103, 93, 86, 80, 75, 70, 65, 59, 53, 47, 40, 31, 23, 15,  4,  0,  0,  0,  0,
55 126,119,112,104, 95, 89, 83, 78, 72, 66, 60, 54, 47, 39, 32, 25, 17, 12,  1,  0,  0,
56 134,127,120,114,103, 97, 91, 85, 78, 72, 66, 60, 54, 47, 41, 35, 29, 23, 16, 10,  1,
57 144,137,130,124,113,107,101, 95, 88, 82, 76, 70, 64, 57, 51, 45, 39, 33, 26, 15,  1,
58 152,145,138,132,123,117,111,105, 98, 92, 86, 80, 74, 67, 61, 55, 49, 43, 36, 20,  1,
59 162,155,148,142,133,127,121,115,108,102, 96, 90, 84, 77, 71, 65, 59, 53, 46, 30,  1,
60 172,165,158,152,143,137,131,125,118,112,106,100, 94, 87, 81, 75, 69, 63, 56, 45, 20,
61 200,200,200,200,200,200,200,200,198,193,188,183,178,173,168,163,158,153,148,129,104,
62 };
63
64 #ifndef CUSTOM_MODES_ONLY
65  #ifdef FIXED_POINT
66   #include "static_modes_fixed.h"
67  #else
68   #include "static_modes_float.h"
69  #endif
70 #endif /* CUSTOM_MODES_ONLY */
71
72 #ifndef M_PI
73 #define M_PI 3.141592653
74 #endif
75
76 #ifdef CUSTOM_MODES
77
78 /* Defining 25 critical bands for the full 0-20 kHz audio bandwidth
79    Taken from http://ccrma.stanford.edu/~jos/bbt/Bark_Frequency_Scale.html */
80 #define BARK_BANDS 25
81 static const opus_int16 bark_freq[BARK_BANDS+1] = {
82       0,   100,   200,   300,   400,
83     510,   630,   770,   920,  1080,
84    1270,  1480,  1720,  2000,  2320,
85    2700,  3150,  3700,  4400,  5300,
86    6400,  7700,  9500, 12000, 15500,
87   20000};
88
89 static opus_int16 *compute_ebands(opus_int32 Fs, int frame_size, int res, int *nbEBands)
90 {
91    opus_int16 *eBands;
92    int i, j, lin, low, high, nBark, offset=0;
93
94    /* All modes that have 2.5 ms short blocks use the same definition */
95    if (Fs == 400*(opus_int32)frame_size)
96    {
97       *nbEBands = sizeof(eband5ms)/sizeof(eband5ms[0])-1;
98       eBands = celt_alloc(sizeof(opus_int16)*(*nbEBands+1));
99       for (i=0;i<*nbEBands+1;i++)
100          eBands[i] = eband5ms[i];
101       return eBands;
102    }
103    /* Find the number of critical bands supported by our sampling rate */
104    for (nBark=1;nBark<BARK_BANDS;nBark++)
105     if (bark_freq[nBark+1]*2 >= Fs)
106        break;
107
108    /* Find where the linear part ends (i.e. where the spacing is more than min_width */
109    for (lin=0;lin<nBark;lin++)
110       if (bark_freq[lin+1]-bark_freq[lin] >= res)
111          break;
112
113    low = (bark_freq[lin]+res/2)/res;
114    high = nBark-lin;
115    *nbEBands = low+high;
116    eBands = celt_alloc(sizeof(opus_int16)*(*nbEBands+2));
117
118    if (eBands==NULL)
119       return NULL;
120
121    /* Linear spacing (min_width) */
122    for (i=0;i<low;i++)
123       eBands[i] = i;
124    if (low>0)
125       offset = eBands[low-1]*res - bark_freq[lin-1];
126    /* Spacing follows critical bands */
127    for (i=0;i<high;i++)
128    {
129       int target = bark_freq[lin+i];
130       /* Round to an even value */
131       eBands[i+low] = (target+offset/2+res)/(2*res)*2;
132       offset = eBands[i+low]*res - target;
133    }
134    /* Enforce the minimum spacing at the boundary */
135    for (i=0;i<*nbEBands;i++)
136       if (eBands[i] < i)
137          eBands[i] = i;
138    /* Round to an even value */
139    eBands[*nbEBands] = (bark_freq[nBark]+res)/(2*res)*2;
140    if (eBands[*nbEBands] > frame_size)
141       eBands[*nbEBands] = frame_size;
142    for (i=1;i<*nbEBands-1;i++)
143    {
144       if (eBands[i+1]-eBands[i] < eBands[i]-eBands[i-1])
145       {
146          eBands[i] -= (2*eBands[i]-eBands[i-1]-eBands[i+1])/2;
147       }
148    }
149    /* Remove any empty bands. */
150    for (i=j=0;i<*nbEBands;i++)
151       if(eBands[i+1]>eBands[j])
152          eBands[++j]=eBands[i+1];
153    *nbEBands=j;
154
155    for (i=1;i<*nbEBands;i++)
156    {
157       /* Every band must be smaller than the last band. */
158       celt_assert(eBands[i]-eBands[i-1]<=eBands[*nbEBands]-eBands[*nbEBands-1]);
159       /* Each band must be no larger than twice the size of the previous one. */
160       celt_assert(eBands[i+1]-eBands[i]<=2*(eBands[i]-eBands[i-1]));
161    }
162
163    return eBands;
164 }
165
166 static void compute_allocation_table(CELTMode *mode)
167 {
168    int i, j;
169    unsigned char *allocVectors;
170    int maxBands = sizeof(eband5ms)/sizeof(eband5ms[0])-1;
171
172    mode->nbAllocVectors = BITALLOC_SIZE;
173    allocVectors = celt_alloc(sizeof(unsigned char)*(BITALLOC_SIZE*mode->nbEBands));
174    if (allocVectors==NULL)
175       return;
176
177    /* Check for standard mode */
178    if (mode->Fs == 400*(opus_int32)mode->shortMdctSize)
179    {
180       for (i=0;i<BITALLOC_SIZE*mode->nbEBands;i++)
181          allocVectors[i] = band_allocation[i];
182       mode->allocVectors = allocVectors;
183       return;
184    }
185    /* If not the standard mode, interpolate */
186    /* Compute per-codec-band allocation from per-critical-band matrix */
187    for (i=0;i<BITALLOC_SIZE;i++)
188    {
189       for (j=0;j<mode->nbEBands;j++)
190       {
191          int k;
192          for (k=0;k<maxBands;k++)
193          {
194             if (400*(opus_int32)eband5ms[k] > mode->eBands[j]*(opus_int32)mode->Fs/mode->shortMdctSize)
195                break;
196          }
197          if (k>maxBands-1)
198             allocVectors[i*mode->nbEBands+j] = band_allocation[i*maxBands + maxBands-1];
199          else {
200             opus_int32 a0, a1;
201             a1 = mode->eBands[j]*(opus_int32)mode->Fs/mode->shortMdctSize - 400*(opus_int32)eband5ms[k-1];
202             a0 = 400*(opus_int32)eband5ms[k] - mode->eBands[j]*(opus_int32)mode->Fs/mode->shortMdctSize;
203             allocVectors[i*mode->nbEBands+j] = (a0*band_allocation[i*maxBands+k-1]
204                                              + a1*band_allocation[i*maxBands+k])/(a0+a1);
205          }
206       }
207    }
208
209    /*printf ("\n");
210    for (i=0;i<BITALLOC_SIZE;i++)
211    {
212       for (j=0;j<mode->nbEBands;j++)
213          printf ("%d ", allocVectors[i*mode->nbEBands+j]);
214       printf ("\n");
215    }
216    exit(0);*/
217
218    mode->allocVectors = allocVectors;
219 }
220
221 #endif /* CUSTOM_MODES */
222
223 CELTMode *celt_mode_create(opus_int32 Fs, int frame_size, int *error)
224 {
225    int i;
226 #ifdef CUSTOM_MODES
227    CELTMode *mode=NULL;
228    int res;
229    opus_val16 *window;
230    opus_int16 *logN;
231    int LM;
232    ALLOC_STACK;
233 #if !defined(VAR_ARRAYS) && !defined(USE_ALLOCA)
234    if (global_stack==NULL)
235       goto failure;
236 #endif
237 #endif
238
239 #ifndef CUSTOM_MODES_ONLY
240    for (i=0;i<TOTAL_MODES;i++)
241    {
242       int j;
243       for (j=0;j<4;j++)
244       {
245          if (Fs == static_mode_list[i]->Fs &&
246                (frame_size<<j) == static_mode_list[i]->shortMdctSize*static_mode_list[i]->nbShortMdcts)
247          {
248             if (error)
249                *error = CELT_OK;
250             return (CELTMode*)static_mode_list[i];
251          }
252       }
253    }
254 #endif /* CUSTOM_MODES_ONLY */
255
256 #ifndef CUSTOM_MODES
257    if (error)
258       *error = CELT_BAD_ARG;
259    return NULL;
260 #else
261
262    /* The good thing here is that permutation of the arguments will automatically be invalid */
263
264    if (Fs < 8000 || Fs > 96000)
265    {
266       if (error)
267          *error = CELT_BAD_ARG;
268       return NULL;
269    }
270    if (frame_size < 40 || frame_size > 1024 || frame_size%2!=0)
271    {
272       if (error)
273          *error = CELT_BAD_ARG;
274       return NULL;
275    }
276    /* Frames of less than 1ms are not supported. */
277    if ((opus_int32)frame_size*1000 < Fs)
278    {
279       if (error)
280          *error = CELT_BAD_ARG;
281       return NULL;
282    }
283
284    if ((opus_int32)frame_size*75 >= Fs && (frame_size%16)==0)
285    {
286      LM = 3;
287    } else if ((opus_int32)frame_size*150 >= Fs && (frame_size%8)==0)
288    {
289      LM = 2;
290    } else if ((opus_int32)frame_size*300 >= Fs && (frame_size%4)==0)
291    {
292      LM = 1;
293    } else
294    {
295      LM = 0;
296    }
297
298    /* Shorts longer than 3.3ms are not supported. */
299    if ((opus_int32)(frame_size>>LM)*300 > Fs)
300    {
301       if (error)
302          *error = CELT_BAD_ARG;
303       return NULL;
304    }
305
306    mode = celt_alloc(sizeof(CELTMode));
307    if (mode==NULL)
308       goto failure;
309    mode->Fs = Fs;
310
311    /* Pre/de-emphasis depends on sampling rate. The "standard" pre-emphasis
312       is defined as A(z) = 1 - 0.85*z^-1 at 48 kHz. Other rates should
313       approximate that. */
314    if(Fs < 12000) /* 8 kHz */
315    {
316       mode->preemph[0] =  QCONST16(0.3500061035f, 15);
317       mode->preemph[1] = -QCONST16(0.1799926758f, 15);
318       mode->preemph[2] =  QCONST16(0.2719968125f, SIG_SHIFT); /* exact 1/preemph[3] */
319       mode->preemph[3] =  QCONST16(3.6765136719f, 13);
320    } else if(Fs < 24000) /* 16 kHz */
321    {
322       mode->preemph[0] =  QCONST16(0.6000061035f, 15);
323       mode->preemph[1] = -QCONST16(0.1799926758f, 15);
324       mode->preemph[2] =  QCONST16(0.4424998650f, SIG_SHIFT); /* exact 1/preemph[3] */
325       mode->preemph[3] =  QCONST16(2.2598876953f, 13);
326    } else if(Fs < 40000) /* 32 kHz */
327    {
328       mode->preemph[0] =  QCONST16(0.7799987793f, 15);
329       mode->preemph[1] = -QCONST16(0.1000061035f, 15);
330       mode->preemph[2] =  QCONST16(0.7499771125f, SIG_SHIFT); /* exact 1/preemph[3] */
331       mode->preemph[3] =  QCONST16(1.3333740234f, 13);
332    } else /* 48 kHz */
333    {
334       mode->preemph[0] =  QCONST16(0.8500061035f, 15);
335       mode->preemph[1] =  QCONST16(0.0f, 15);
336       mode->preemph[2] =  QCONST16(1.f, SIG_SHIFT);
337       mode->preemph[3] =  QCONST16(1.f, 13);
338    }
339
340    mode->maxLM = LM;
341    mode->nbShortMdcts = 1<<LM;
342    mode->shortMdctSize = frame_size/mode->nbShortMdcts;
343    res = (mode->Fs+mode->shortMdctSize)/(2*mode->shortMdctSize);
344
345    mode->eBands = compute_ebands(Fs, mode->shortMdctSize, res, &mode->nbEBands);
346    if (mode->eBands==NULL)
347       goto failure;
348
349    mode->effEBands = mode->nbEBands;
350    while (mode->eBands[mode->effEBands] > mode->shortMdctSize)
351       mode->effEBands--;
352
353    /* Overlap must be divisible by 4 */
354    mode->overlap = ((mode->shortMdctSize>>2)<<2);
355
356    compute_allocation_table(mode);
357    if (mode->allocVectors==NULL)
358       goto failure;
359
360    window = (opus_val16*)celt_alloc(mode->overlap*sizeof(opus_val16));
361    if (window==NULL)
362       goto failure;
363
364 #ifndef FIXED_POINT
365    for (i=0;i<mode->overlap;i++)
366       window[i] = Q15ONE*sin(.5*M_PI* sin(.5*M_PI*(i+.5)/mode->overlap) * sin(.5*M_PI*(i+.5)/mode->overlap));
367 #else
368    for (i=0;i<mode->overlap;i++)
369       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))));
370 #endif
371    mode->window = window;
372
373    logN = (opus_int16*)celt_alloc(mode->nbEBands*sizeof(opus_int16));
374    if (logN==NULL)
375       goto failure;
376
377    for (i=0;i<mode->nbEBands;i++)
378       logN[i] = log2_frac(mode->eBands[i+1]-mode->eBands[i], BITRES);
379    mode->logN = logN;
380
381    compute_pulse_cache(mode, mode->maxLM);
382
383    if (clt_mdct_init(&mode->mdct, 2*mode->shortMdctSize*mode->nbShortMdcts,
384            mode->maxLM) == 0)
385       goto failure;
386
387    if (error)
388       *error = CELT_OK;
389
390    return mode;
391 failure:
392    if (error)
393       *error = CELT_ALLOC_FAIL;
394    if (mode!=NULL)
395       celt_mode_destroy(mode);
396    return NULL;
397 #endif /* !CUSTOM_MODES */
398 }
399
400 void celt_mode_destroy(CELTMode *mode)
401 {
402 #ifdef CUSTOM_MODES
403    int i;
404    if (mode == NULL)
405       return;
406 #ifndef CUSTOM_MODES_ONLY
407    for (i=0;i<TOTAL_MODES;i++)
408    {
409       if (mode == static_mode_list[i])
410       {
411          return;
412       }
413    }
414 #endif /* CUSTOM_MODES_ONLY */
415    celt_free((opus_int16*)mode->eBands);
416    celt_free((opus_int16*)mode->allocVectors);
417
418    celt_free((opus_val16*)mode->window);
419    celt_free((opus_int16*)mode->logN);
420
421    celt_free((opus_int16*)mode->cache.index);
422    celt_free((unsigned char*)mode->cache.bits);
423    celt_free((unsigned char*)mode->cache.caps);
424    clt_mdct_clear(&mode->mdct);
425
426    celt_free((CELTMode *)mode);
427 #endif
428 }