Reducing the size of the pulses->bits cache by restricting the number of pulses
[opus.git] / libcelt / rate.c
1 /* (C) 2007-2009 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    int error = 0;
52    celt_int16_t **bits;
53    const celt_int16_t *eBands = m->eBands;
54
55    bits = celt_alloc(m->nbEBands*sizeof(celt_int16_t*));
56    if (bits==NULL)
57      return NULL;
58         
59    prevN = -1;
60    for (i=0;i<m->nbEBands;i++)
61    {
62       int N = C*(eBands[i+1]-eBands[i]);
63       if (N == prevN && eBands[i] < m->pitchEnd)
64       {
65          bits[i] = bits[i-1];
66       } else {
67          bits[i] = celt_alloc(MAX_PSEUDO*sizeof(celt_int16_t));
68          if (bits[i]!=NULL) {
69             int j;
70             celt_int16_t tmp[MAX_PULSES];
71             get_required_bits(tmp, N, MAX_PULSES, BITRES);
72             for (j=0;j<MAX_PSEUDO;j++)
73                bits[i][j] = tmp[get_pulses(j)];
74          } else {
75             error=1;
76          }
77          prevN = N;
78       }
79    }
80    if (error)
81    {
82       const celt_int16_t *prevPtr = NULL;
83       if (bits!=NULL)
84       {
85          for (i=0;i<m->nbEBands;i++)
86          {
87             if (bits[i] != prevPtr)
88             {
89                prevPtr = bits[i];
90                celt_free((int*)bits[i]);
91             }
92          }
93       free(bits);
94       bits=NULL;
95       }   
96    }
97    return bits;
98 }
99
100 #endif /* !STATIC_MODES */
101
102
103
104 static void interp_bits2pulses(const CELTMode *m, int *bits1, int *bits2, int total, int *bits, int *ebits, int *fine_priority, int len)
105 {
106    int psum;
107    int lo, hi;
108    int j;
109    const int C = CHANNELS(m);
110    SAVE_STACK;
111    lo = 0;
112    hi = 1<<BITRES;
113    while (hi-lo != 1)
114    {
115       int mid = (lo+hi)>>1;
116       psum = 0;
117       for (j=0;j<len;j++)
118          psum += ((1<<BITRES)-mid)*bits1[j] + mid*bits2[j];
119       if (psum > (total<<BITRES))
120          hi = mid;
121       else
122          lo = mid;
123    }
124    psum = 0;
125    /*printf ("interp bisection gave %d\n", lo);*/
126    for (j=0;j<len;j++)
127    {
128       bits[j] = ((1<<BITRES)-lo)*bits1[j] + lo*bits2[j];
129       psum += bits[j];
130    }
131    /* Allocate the remaining bits */
132    {
133       int left, perband;
134       left = (total<<BITRES)-psum;
135       perband = left/len;
136       for (j=0;j<len;j++)
137          bits[j] += perband;
138       left = left-len*perband;
139       for (j=0;j<left;j++)
140          bits[j]++;
141    }
142    for (j=0;j<len;j++)
143    {
144       int N, d;
145       int offset;
146
147       N=m->eBands[j+1]-m->eBands[j]; 
148       d=C*N<<BITRES; 
149       offset = 50 - log2_frac(N, 4);
150       /* Offset for the number of fine bits compared to their "fair share" of total/N */
151       offset = bits[j]-offset*N*C;
152       if (offset < 0)
153          offset = 0;
154       ebits[j] = (2*offset+d)/(2*d);
155       fine_priority[j] = ebits[j]*d >= offset;
156
157       /* Make sure not to bust */
158       if (C*ebits[j] > (bits[j]>>BITRES))
159          ebits[j] = bits[j]/C >> BITRES;
160
161       if (ebits[j]>7)
162          ebits[j]=7;
163       /* The bits used for fine allocation can't be used for pulses */
164       bits[j] -= C*ebits[j]<<BITRES;
165       if (bits[j] < 0)
166          bits[j] = 0;
167    }
168    RESTORE_STACK;
169 }
170
171 void compute_allocation(const CELTMode *m, int *offsets, int total, int *pulses, int *ebits, int *fine_priority)
172 {
173    int lo, hi, len, j;
174    VARDECL(int, bits1);
175    VARDECL(int, bits2);
176    SAVE_STACK;
177    
178    len = m->nbEBands;
179    ALLOC(bits1, len, int);
180    ALLOC(bits2, len, int);
181
182    lo = 0;
183    hi = m->nbAllocVectors - 1;
184    while (hi-lo != 1)
185    {
186       int psum = 0;
187       int mid = (lo+hi) >> 1;
188       for (j=0;j<len;j++)
189       {
190          bits1[j] = (m->allocVectors[mid*len+j] + offsets[j])<<BITRES;
191          if (bits1[j] < 0)
192             bits1[j] = 0;
193          psum += bits1[j];
194          /*printf ("%d ", bits[j]);*/
195       }
196       /*printf ("\n");*/
197       if (psum > (total<<BITRES))
198          hi = mid;
199       else
200          lo = mid;
201       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
202    }
203    /*printf ("interp between %d and %d\n", lo, hi);*/
204    for (j=0;j<len;j++)
205    {
206       bits1[j] = m->allocVectors[lo*len+j] + offsets[j];
207       bits2[j] = m->allocVectors[hi*len+j] + offsets[j];
208       if (bits1[j] < 0)
209          bits1[j] = 0;
210       if (bits2[j] < 0)
211          bits2[j] = 0;
212    }
213    interp_bits2pulses(m, bits1, bits2, total, pulses, ebits, fine_priority, len);
214    RESTORE_STACK;
215 }
216