License for the kiss-fft headers
[opus.git] / libcelt / rate.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 <math.h>
37 #include "modes.h"
38 #include "cwrs.h"
39 #include "arch.h"
40 #include "os_support.h"
41
42 #include "entcode.h"
43 #include "rate.h"
44
45
46 #ifndef STATIC_MODES
47
48 celt_int16_t **compute_alloc_cache(CELTMode *m, int C)
49 {
50    int i, prevN;
51    celt_int16_t **bits;
52    const celt_int16_t *eBands = m->eBands;
53
54    bits = celt_alloc(m->nbEBands*sizeof(celt_int16_t*));
55    
56    prevN = -1;
57    for (i=0;i<m->nbEBands;i++)
58    {
59       int N = C*(eBands[i+1]-eBands[i]);
60       if (N == prevN && eBands[i] < m->pitchEnd)
61       {
62          bits[i] = bits[i-1];
63       } else {
64          bits[i] = celt_alloc(MAX_PULSES*sizeof(celt_int16_t));
65          get_required_bits(bits[i], N, MAX_PULSES, BITRES);
66          prevN = N;
67       }
68    }
69    return bits;
70 }
71
72 #endif /* !STATIC_MODES */
73
74
75
76 static int interp_bits2pulses(const CELTMode *m, int *bits1, int *bits2, int *ebits1, int *ebits2, int total, int *bits, int *ebits, int len)
77 {
78    int esum, psum;
79    int lo, hi;
80    int j;
81    const int C = CHANNELS(m);
82    SAVE_STACK;
83    lo = 0;
84    hi = 1<<BITRES;
85    while (hi-lo != 1)
86    {
87       int mid = (lo+hi)>>1;
88       psum = 0;
89       esum = 0;
90       for (j=0;j<len;j++)
91       {
92          esum += (((1<<BITRES)-mid)*ebits1[j] + mid*ebits2[j] + (1<<(BITRES-1)))>>BITRES;
93          psum += ((1<<BITRES)-mid)*bits1[j] + mid*bits2[j];
94       }
95       if (psum > (total-C*esum)<<BITRES)
96          hi = mid;
97       else
98          lo = mid;
99    }
100    esum = 0;
101    psum = 0;
102    /*printf ("interp bisection gave %d\n", lo);*/
103    for (j=0;j<len;j++)
104    {
105       ebits[j] = (((1<<BITRES)-lo)*ebits1[j] + lo*ebits2[j] + (1<<(BITRES-1)))>>BITRES;
106       esum += ebits[j];
107    }
108    for (j=0;j<len;j++)
109    {
110       bits[j] = ((1<<BITRES)-lo)*bits1[j] + lo*bits2[j];
111       psum += bits[j];
112    }
113    /* Allocate the remaining bits */
114    {
115       int left, perband;
116       left = ((total-C*esum)<<BITRES)-psum;
117       perband = left/len;
118       for (j=0;j<len;j++)
119          bits[j] += perband;
120       left = left-len*perband;
121       for (j=0;j<left;j++)
122          bits[j]++;
123    }
124    RESTORE_STACK;
125    return (total-C*esum)<<BITRES;
126 }
127
128 void compute_allocation(const CELTMode *m, int *offsets, const int *stereo_mode, int total, int *pulses, int *ebits)
129 {
130    int lo, hi, len, j;
131    int remaining_bits;
132    VARDECL(int, bits1);
133    VARDECL(int, bits2);
134    VARDECL(int, ebits1);
135    VARDECL(int, ebits2);
136    const int C = CHANNELS(m);
137    SAVE_STACK;
138    
139    len = m->nbEBands;
140    ALLOC(bits1, len, int);
141    ALLOC(bits2, len, int);
142    ALLOC(ebits1, len, int);
143    ALLOC(ebits2, len, int);
144
145    lo = 0;
146    hi = m->nbAllocVectors - 1;
147    while (hi-lo != 1)
148    {
149       int psum = 0;
150       int mid = (lo+hi) >> 1;
151       for (j=0;j<len;j++)
152       {
153          bits1[j] = (m->allocVectors[mid*len+j] + offsets[j])<<BITRES;
154          if (bits1[j] < 0)
155             bits1[j] = 0;
156          psum += bits1[j];
157          /*printf ("%d ", bits[j]);*/
158       }
159       /*printf ("\n");*/
160       if (psum > (total-C*m->energy_alloc[mid*(len+1)+len])<<BITRES)
161          hi = mid;
162       else
163          lo = mid;
164       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
165    }
166    /*printf ("interp between %d and %d\n", lo, hi);*/
167    for (j=0;j<len;j++)
168    {
169       ebits1[j] = m->energy_alloc[lo*(len+1)+j];
170       ebits2[j] = m->energy_alloc[hi*(len+1)+j];
171       bits1[j] = m->allocVectors[lo*len+j] + offsets[j];
172       bits2[j] = m->allocVectors[hi*len+j] + offsets[j];
173       if (bits1[j] < 0)
174          bits1[j] = 0;
175       if (bits2[j] < 0)
176          bits2[j] = 0;
177    }
178    remaining_bits = interp_bits2pulses(m, bits1, bits2, ebits1, ebits2, total, pulses, ebits, len);
179    RESTORE_STACK;
180 }
181