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