The encoder would crash in the PVQ search if fed NaNs via the float interface. This...
[opus.git] / libcelt / rate.c
index 5e0d764..24037c0 100644 (file)
    notice, this list of conditions and the following disclaimer in the
    documentation and/or other materials provided with the distribution.
    
-   - Neither the name of the Xiph.org Foundation nor the names of its
-   contributors may be used to endorse or promote products derived from
-   this software without specific prior written permission.
-   
    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 #include "rate.h"
 
 
-#ifndef STATIC_MODES
+static const unsigned char LOG2_FRAC_TABLE[24]={
+   0,
+   8,13,
+  16,19,21,23,
+  24,26,27,28,29,30,31,32,
+  32,33,34,34,35,36,36,37,37
+};
+
+#ifdef CUSTOM_MODES
 
 /*Determines if V(N,K) fits in a 32-bit unsigned integer.
   N and K are themselves limited to 15 bits.*/
@@ -69,7 +73,9 @@ static int fits_in32(int _n, int _k)
 
 void compute_pulse_cache(CELTMode *m, int LM)
 {
+   int C;
    int i;
+   int j;
    int curr=0;
    int nbEntries=0;
    int entryN[100], entryK[100], entryI[100];
@@ -77,6 +83,7 @@ void compute_pulse_cache(CELTMode *m, int LM)
    PulseCache *cache = &m->cache;
    celt_int16 *cindex;
    unsigned char *bits;
+   unsigned char *cap;
 
    cindex = celt_alloc(sizeof(cache->index[0])*m->nbEBands*(LM+2));
    cache->index = cindex;
@@ -84,7 +91,6 @@ void compute_pulse_cache(CELTMode *m, int LM)
    /* Scan for all unique band sizes */
    for (i=0;i<=LM+1;i++)
    {
-      int j;
       for (j=0;j<m->nbEBands;j++)
       {
          int k;
@@ -125,7 +131,6 @@ void compute_pulse_cache(CELTMode *m, int LM)
    /* Compute the cache for all unique sizes */
    for (i=0;i<nbEntries;i++)
    {
-      int j;
       unsigned char *ptr = bits+entryI[i];
       celt_int16 tmp[MAX_PULSES+1];
       get_required_bits(tmp, entryN[i], get_pulses(entryK[i]), BITRES);
@@ -133,29 +138,136 @@ void compute_pulse_cache(CELTMode *m, int LM)
          ptr[j] = tmp[get_pulses(j)]-1;
       ptr[0] = entryK[i];
    }
+
+   /* Compute the maximum rate for each band at which we'll reliably use as
+       many bits as we ask for. */
+   cache->caps = cap = celt_alloc(sizeof(cache->caps[0])*(LM+1)*2*m->nbEBands);
+   for (i=0;i<=LM;i++)
+   {
+      for (C=1;C<=2;C++)
+      {
+         for (j=0;j<m->nbEBands;j++)
+         {
+            int N0;
+            int max_bits;
+            N0 = m->eBands[j+1]-m->eBands[j];
+            /* N=1 bands only have a sign bit and fine bits. */
+            if (N0<<i == 1)
+               max_bits = C*(1+MAX_FINE_BITS)<<BITRES;
+            else
+            {
+               const unsigned char *pcache;
+               celt_int32           num;
+               celt_int32           den;
+               int                  LM0;
+               int                  N;
+               int                  offset;
+               int                  ndof;
+               int                  qb;
+               int                  k;
+               LM0 = 0;
+               /* Even-sized bands bigger than N=2 can be split one more
+                   time. */
+               if (N0 > 2 && !(N0&1))
+               {
+                  N0>>=1;
+                  LM0--;
+               }
+               /* N0=1 bands can't be split down to N<2. */
+               else if (N0 <= 1)
+               {
+                  LM0=IMIN(i,1);
+                  N0<<=LM0;
+               }
+               /* Compute the cost for the lowest-level PVQ of a fully split
+                   band. */
+               pcache = bits + cindex[(LM0+1)*m->nbEBands+j];
+               max_bits = pcache[pcache[0]]+1;
+               /* Add in the cost of coding regular splits. */
+               N = N0;
+               for(k=0;k<i-LM0;k++){
+                  max_bits <<= 1;
+                  /* Offset the number of qtheta bits by log2(N)/2
+                      + QTHETA_OFFSET compared to their "fair share" of
+                      total/N */
+                  offset = (m->logN[j]+(LM0+k<<BITRES)>>1)-QTHETA_OFFSET;
+                  /* The number of qtheta bits we'll allocate if the remainder
+                      is to be max_bits.
+                     The average measured cost for theta is 0.89701 times qb,
+                      approximated here as 459/512. */
+                  num=459*(celt_int32)((2*N-1)*offset+max_bits);
+                  den=((celt_int32)(2*N-1)<<9)-459;
+                  qb = IMIN((num+(den>>1))/den, 57);
+                  celt_assert(qb >= 0);
+                  max_bits += qb;
+                  N <<= 1;
+               }
+               /* Add in the cost of a stereo split, if necessary. */
+               if (C==2)
+               {
+                  max_bits <<= 1;
+                  offset = (m->logN[j]+(i<<BITRES)>>1)-(N==2?QTHETA_OFFSET_TWOPHASE:QTHETA_OFFSET);
+                  ndof = 2*N-1-(N==2);
+                  /* The average measured cost for theta with the step PDF is
+                      0.95164 times qb, approximated here as 487/512. */
+                  num = (N==2?512:487)*(celt_int32)(max_bits+ndof*offset);
+                  den = ((celt_int32)ndof<<9)-(N==2?512:487);
+                  qb = IMIN((num+(den>>1))/den, (N==2?64:61));
+                  celt_assert(qb >= 0);
+                  max_bits += qb;
+               }
+               /* Add the fine bits we'll use. */
+               /* Compensate for the extra DoF in stereo */
+               ndof = C*N + ((C==2 && N>2) ? 1 : 0);
+               /* Offset the number of fine bits by log2(N)/2 + FINE_OFFSET
+                   compared to their "fair share" of total/N */
+               offset = (m->logN[j] + (i<<BITRES)>>1)-FINE_OFFSET;
+               /* N=2 is the only point that doesn't match the curve */
+               if (N==2)
+                  offset += 1<<BITRES>>2;
+               /* The number of fine bits we'll allocate if the remainder is
+                   to be max_bits. */
+               num = max_bits+ndof*offset;
+               den = ndof-1<<BITRES;
+               qb = IMIN((num+(den>>1))/den, MAX_FINE_BITS);
+               celt_assert(qb >= 0);
+               max_bits += C*qb<<BITRES;
+            }
+            max_bits = (4*max_bits/(C*(m->eBands[j+1]-m->eBands[j]<<i)))-64;
+            celt_assert(max_bits >= 0);
+            celt_assert(max_bits < 256);
+            *cap++ = (unsigned char)max_bits;
+         }
+      }
+   }
 }
 
-#endif /* !STATIC_MODES */
+#endif /* CUSTOM_MODES */
 
 
 #define ALLOC_STEPS 6
 
-static inline int interp_bits2pulses(const CELTMode *m, int start, int end, int *bits1, int *bits2, int total, int *bits, int *ebits, int *fine_priority, int len, int _C, int LM)
+static inline int interp_bits2pulses(const CELTMode *m, int start, int end, int skip_start,
+      const int *bits1, const int *bits2, const int *thresh, const int *cap, celt_int32 total, celt_int32 *_balance,
+      int skip_rsv, int *intensity, int intensity_rsv, int *dual_stereo, int dual_stereo_rsv, int *bits,
+      int *ebits, int *fine_priority, int _C, int LM, ec_ctx *ec, int encode, int prev)
 {
-   int psum;
+   celt_int32 psum;
    int lo, hi;
    int i, j;
    int logM;
    const int C = CHANNELS(_C);
+   int stereo;
    int codedBands=-1;
-   VARDECL(int, thresh);
+   int alloc_floor;
+   celt_int32 left, percoeff;
+   int done;
+   int balance;
    SAVE_STACK;
 
-   ALLOC(thresh, len, int);
+   alloc_floor = C<<BITRES;
+   stereo = C>1;
 
-   /* Below this threshold, we don't allocate any PVQ bits */
-   for (j=start;j<end;j++)
-      thresh[j] = 2*(C*(m->eBands[j+1]-m->eBands[j])<<LM<<BITRES)>>3;
    logM = LM<<BITRES;
    lo = 0;
    hi = 1<<ALLOC_STEPS;
@@ -163,177 +275,363 @@ static inline int interp_bits2pulses(const CELTMode *m, int start, int end, int
    {
       int mid = (lo+hi)>>1;
       psum = 0;
-      for (j=start;j<end;j++)
+      done = 0;
+      for (j=end;j-->start;)
       {
-         int tmp = bits1[j] + (mid*bits2[j]>>ALLOC_STEPS);
-         if (tmp >= thresh[j])
-            psum += tmp;
-         else if (tmp >= 1<<BITRES)
-            psum += 1<<BITRES;
+         int tmp = bits1[j] + (mid*(celt_int32)bits2[j]>>ALLOC_STEPS);
+         if (tmp >= thresh[j] || done)
+         {
+            done = 1;
+            /* Don't allocate more than we can actually use */
+            psum += IMIN(tmp, cap[j]);
+         } else {
+            if (tmp >= alloc_floor)
+               psum += alloc_floor;
+         }
       }
-      if (psum > (total<<BITRES))
+      if (psum > total)
          hi = mid;
       else
          lo = mid;
    }
    psum = 0;
    /*printf ("interp bisection gave %d\n", lo);*/
-   for (j=start;j<end;j++)
+   done = 0;
+   for (j=end;j-->start;)
    {
       int tmp = bits1[j] + (lo*bits2[j]>>ALLOC_STEPS);
-      if (tmp >= thresh[j])
+      if (tmp < thresh[j] && !done)
       {
-         bits[j] = tmp;
-         codedBands = j;
-      } else if (tmp >= 1<<BITRES)
-         bits[j] = 1<<BITRES;
-      else
+         if (tmp >= alloc_floor)
+            tmp = alloc_floor;
+         else
+            tmp = 0;
+      } else
+         done = 1;
+      /* Don't allocate more than we can actually use */
+      tmp = IMIN(tmp, cap[j]);
+      bits[j] = tmp;
+      psum += tmp;
+   }
+
+   /* Decide which bands to skip, working backwards from the end. */
+   for (codedBands=end;;codedBands--)
+   {
+      int band_width;
+      int band_bits;
+      int rem;
+      j = codedBands-1;
+      /* Never skip the first band, nor a band that has been boosted by
+          dynalloc.
+         In the first case, we'd be coding a bit to signal we're going to waste
+          all the other bits.
+         In the second case, we'd be coding a bit to redistribute all the bits
+          we just signaled should be cocentrated in this band. */
+      if (j<=skip_start)
+      {
+         /* Give the bit we reserved to end skipping back. */
+         total += skip_rsv;
+         break;
+      }
+      /*Figure out how many left-over bits we would be adding to this band.
+        This can include bits we've stolen back from higher, skipped bands.*/
+      left = total-psum;
+      percoeff = left/(m->eBands[codedBands]-m->eBands[start]);
+      left -= (m->eBands[codedBands]-m->eBands[start])*percoeff;
+      rem = IMAX(left-(m->eBands[j]-m->eBands[start]),0);
+      band_width = m->eBands[codedBands]-m->eBands[j];
+      band_bits = (int)(bits[j] + percoeff*band_width + rem);
+      /*Only code a skip decision if we're above the threshold for this band.
+        Otherwise it is force-skipped.
+        This ensures that we have enough bits to code the skip flag.*/
+      if (band_bits >= IMAX(thresh[j], alloc_floor+(1<<BITRES)))
+      {
+         if (encode)
+         {
+            /*This if() block is the only part of the allocation function that
+               is not a mandatory part of the bitstream: any bands we choose to
+               skip here must be explicitly signaled.*/
+            /*Choose a threshold with some hysteresis to keep bands from
+               fluctuating in and out.*/
+            if (band_bits > ((j<prev?7:9)*band_width<<LM<<BITRES)>>4)
+            {
+               ec_enc_bit_logp(ec, 1, 1);
+               break;
+            }
+            ec_enc_bit_logp(ec, 0, 1);
+         } else if (ec_dec_bit_logp(ec, 1)) {
+            break;
+         }
+         /*We used a bit to skip this band.*/
+         psum += 1<<BITRES;
+         band_bits -= 1<<BITRES;
+      }
+      /*Reclaim the bits originally allocated to this band.*/
+      psum -= bits[j]+intensity_rsv;
+      if (intensity_rsv > 0)
+         intensity_rsv = LOG2_FRAC_TABLE[j-start];
+      psum += intensity_rsv;
+      if (band_bits >= alloc_floor)
+      {
+         /*If we have enough for a fine energy bit per channel, use it.*/
+         psum += alloc_floor;
+         bits[j] = alloc_floor;
+      } else {
+         /*Otherwise this band gets nothing at all.*/
          bits[j] = 0;
-      psum += bits[j];
+      }
    }
-   codedBands++;
-   /* Allocate the remaining bits */
-   if (codedBands) {
-      int left, perband;
-      left = (total<<BITRES)-psum;
-      perband = left/(m->eBands[codedBands]-m->eBands[start]);
-      for (j=start;j<codedBands;j++)
-         bits[j] += perband*(m->eBands[j+1]-m->eBands[j]);
-      left = left-(m->eBands[codedBands]-m->eBands[start])*perband;
-      for (j=start;j<codedBands;j++)
+
+   celt_assert(codedBands > start);
+   /* Code the intensity and dual stereo parameters. */
+   if (intensity_rsv > 0)
+   {
+      if (encode)
       {
-         int tmp = IMIN(left, m->eBands[j+1]-m->eBands[j]);
-         bits[j] += tmp;
-         left -= tmp;
+         *intensity = IMIN(*intensity, codedBands);
+         ec_enc_uint(ec, *intensity-start, codedBands+1-start);
       }
+      else
+         *intensity = start+ec_dec_uint(ec, codedBands+1-start);
+   }
+   else
+      *intensity = 0;
+   if (*intensity <= start)
+   {
+      total += dual_stereo_rsv;
+      dual_stereo_rsv = 0;
+   }
+   if (dual_stereo_rsv > 0)
+   {
+      if (encode)
+         ec_enc_bit_logp(ec, *dual_stereo, 1);
+      else
+         *dual_stereo = ec_dec_bit_logp(ec, 1);
+   }
+   else
+      *dual_stereo = 0;
+
+   /* Allocate the remaining bits */
+   left = total-psum;
+   percoeff = left/(m->eBands[codedBands]-m->eBands[start]);
+   left -= (m->eBands[codedBands]-m->eBands[start])*percoeff;
+   for (j=start;j<codedBands;j++)
+      bits[j] += ((int)percoeff*(m->eBands[j+1]-m->eBands[j]));
+   for (j=start;j<codedBands;j++)
+   {
+      int tmp = (int)IMIN(left, m->eBands[j+1]-m->eBands[j]);
+      bits[j] += tmp;
+      left -= tmp;
    }
    /*for (j=0;j<end;j++)printf("%d ", bits[j]);printf("\n");*/
-   for (j=start;j<end;j++)
+
+   balance = 0;
+   for (j=start;j<codedBands;j++)
    {
       int N0, N, den;
       int offset;
       int NClogN;
+      int excess;
 
+      celt_assert(bits[j] >= 0);
       N0 = m->eBands[j+1]-m->eBands[j];
       N=N0<<LM;
-      NClogN = N*C*(m->logN[j] + logM);
-
-      /* Compensate for the extra DoF in stereo */
-      den=(C*N+ ((C==2 && N>2) ? 1 : 0));
-
-      /* Offset for the number of fine bits by log2(N)/2 + FINE_OFFSET
-         compared to their "fair share" of total/N */
-      offset = (NClogN>>1)-N*C*FINE_OFFSET;
-
-      /* N=2 is the only point that doesn't match the curve */
-      if (N==2)
-         offset += N*C<<BITRES>>2;
-
-      /* Changing the offset for allocating the second and third fine energy bit */
-      if (bits[j] + offset < den*2<<BITRES)
-         offset += NClogN>>2;
-      else if (bits[j] + offset < den*3<<BITRES)
-         offset += NClogN>>3;
-
-      /* Divide with rounding */
-      ebits[j] = (bits[j] + offset + (den<<(BITRES-1))) / (den<<BITRES);
-
-      /* If we rounded down, make it a candidate for final fine energy pass */
-      fine_priority[j] = ebits[j]*(den<<BITRES) >= bits[j]+offset;
-
-      /* Make sure the first bit is spent on fine energy */
-      if (ebits[j] < 1)
-         ebits[j] = 1;
-      /* For N=1, all bits go to fine energy except for a single sign bit
-         This takes precedence over giving the first bit to fine energy */
-      if (N==1)
-         ebits[j] = (bits[j]/C >> BITRES)-1;
-
-      /* Make sure not to bust */
-      if (C*ebits[j] > (bits[j]>>BITRES))
-         ebits[j] = bits[j]/C >> BITRES;
-
-      /* More than that is useless because that's about as far as PVQ can go */
-      if (ebits[j]>7)
-         ebits[j]=7;
-
-      /* The other bits are assigned to PVQ */
-      bits[j] -= C*ebits[j]<<BITRES;
-      if (bits[j] < 0)
-         bits[j] = 0;
+      bits[j] += balance;
+
+      if (N>1)
+      {
+         excess = IMAX(bits[j]-cap[j],0);
+         bits[j] -= excess;
+
+         /* Compensate for the extra DoF in stereo */
+         den=(C*N+ ((C==2 && N>2 && !*dual_stereo && j<*intensity) ? 1 : 0));
+
+         NClogN = den*(m->logN[j] + logM);
+
+         /* Offset for the number of fine bits by log2(N)/2 + FINE_OFFSET
+            compared to their "fair share" of total/N */
+         offset = (NClogN>>1)-den*FINE_OFFSET;
+
+         /* N=2 is the only point that doesn't match the curve */
+         if (N==2)
+            offset += den<<BITRES>>2;
+
+         /* Changing the offset for allocating the second and third
+             fine energy bit */
+         if (bits[j] + offset < den*2<<BITRES)
+            offset += NClogN>>2;
+         else if (bits[j] + offset < den*3<<BITRES)
+            offset += NClogN>>3;
+
+         /* Divide with rounding */
+         ebits[j] = IMAX(0, (bits[j] + offset + (den<<(BITRES-1))) / (den<<BITRES));
+
+         /* Make sure not to bust */
+         if (C*ebits[j] > (bits[j]>>BITRES))
+            ebits[j] = bits[j] >> stereo >> BITRES;
+
+         /* More than that is useless because that's about as far as PVQ can go */
+         ebits[j] = IMIN(ebits[j], MAX_FINE_BITS);
+
+         /* If we rounded down or capped this band, make it a candidate for the
+             final fine energy pass */
+         fine_priority[j] = ebits[j]*(den<<BITRES) >= bits[j]+offset;
+
+         /* Remove the allocated fine bits; the rest are assigned to PVQ */
+         bits[j] -= C*ebits[j]<<BITRES;
+
+      } else {
+         /* For N=1, all bits go to fine energy except for a single sign bit */
+         excess = IMAX(0,bits[j]-(C<<BITRES));
+         bits[j] -= excess;
+         ebits[j] = 0;
+         fine_priority[j] = 1;
+      }
+
+      /* Fine energy can't take advantage of the re-balancing in
+          quant_all_bands().
+         Instead, do the re-balancing here.*/
+      if(excess > 0)
+      {
+         int extra_fine;
+         int extra_bits;
+         extra_fine = IMIN(excess >> stereo+BITRES, MAX_FINE_BITS-ebits[j]);
+         ebits[j] += extra_fine;
+         extra_bits = extra_fine*C<<BITRES;
+         fine_priority[j] = extra_bits >= excess-balance;
+         excess -= extra_bits;
+      }
+      balance = excess;
+
+      celt_assert(bits[j] >= 0);
+      celt_assert(ebits[j] >= 0);
+   }
+   /* Save any remaining bits over the cap for the rebalancing in
+       quant_all_bands(). */
+   *_balance = balance;
+
+   /* The skipped bands use all their bits for fine energy. */
+   for (;j<end;j++)
+   {
+      ebits[j] = bits[j] >> stereo >> BITRES;
+      celt_assert(C*ebits[j]<<BITRES == bits[j]);
+      bits[j] = 0;
+      fine_priority[j] = ebits[j]<1;
    }
    RESTORE_STACK;
    return codedBands;
 }
 
-int compute_allocation(const CELTMode *m, int start, int end, int *offsets, int alloc_trim,
-      int total, int *pulses, int *ebits, int *fine_priority, int _C, int LM)
+int compute_allocation(const CELTMode *m, int start, int end, const int *offsets, const int *cap, int alloc_trim, int *intensity, int *dual_stereo,
+      celt_int32 total, celt_int32 *balance, int *pulses, int *ebits, int *fine_priority, int _C, int LM, ec_ctx *ec, int encode, int prev)
 {
    int lo, hi, len, j;
    const int C = CHANNELS(_C);
    int codedBands;
+   int skip_start;
+   int skip_rsv;
+   int intensity_rsv;
+   int dual_stereo_rsv;
    VARDECL(int, bits1);
    VARDECL(int, bits2);
    VARDECL(int, thresh);
    VARDECL(int, trim_offset);
    SAVE_STACK;
    
+   total = IMAX(total, 0);
    len = m->nbEBands;
+   skip_start = start;
+   /* Reserve a bit to signal the end of manually skipped bands. */
+   skip_rsv = total >= 1<<BITRES ? 1<<BITRES : 0;
+   total -= skip_rsv;
+   /* Reserve bits for the intensity and dual stereo parameters. */
+   intensity_rsv = dual_stereo_rsv = 0;
+   if (C==2)
+   {
+      intensity_rsv = LOG2_FRAC_TABLE[end-start];
+      if (intensity_rsv>total)
+         intensity_rsv = 0;
+      else
+      {
+         total -= intensity_rsv;
+         dual_stereo_rsv = total>=1<<BITRES ? 1<<BITRES : 0;
+         total -= dual_stereo_rsv;
+      }
+   }
    ALLOC(bits1, len, int);
    ALLOC(bits2, len, int);
    ALLOC(thresh, len, int);
    ALLOC(trim_offset, len, int);
 
-   /* Below this threshold, we don't allocate any PVQ bits */
-   for (j=start;j<end;j++)
-      thresh[j] = 2*(C*(m->eBands[j+1]-m->eBands[j])<<LM<<BITRES)>>3;
-   /* Tilt of the allocation curve */
    for (j=start;j<end;j++)
-      trim_offset[j] = C*(m->eBands[j+1]-m->eBands[j])*(alloc_trim-2-2*LM)*(m->nbEBands-j-1)
+   {
+      /* Below this threshold, we're sure not to allocate any PVQ bits */
+      thresh[j] = IMAX((C)<<BITRES, (3*(m->eBands[j+1]-m->eBands[j])<<LM<<BITRES)>>4);
+      /* Tilt of the allocation curve */
+      trim_offset[j] = C*(m->eBands[j+1]-m->eBands[j])*(alloc_trim-5-LM)*(end-j-1)
             <<(LM+BITRES)>>6;
-
-   lo = 0;
+      /* Giving less resolution to single-coefficient bands because they get
+         more benefit from having one coarse value per coefficient*/
+      if ((m->eBands[j+1]-m->eBands[j])<<LM==1)
+         trim_offset[j] -= C<<BITRES;
+   }
+   lo = 1;
    hi = m->nbAllocVectors - 1;
-   while (hi-lo != 1)
+   do
    {
+      int done = 0;
       int psum = 0;
       int mid = (lo+hi) >> 1;
-      for (j=start;j<end;j++)
+      for (j=end;j-->start;)
       {
+         int bitsj;
          int N = m->eBands[j+1]-m->eBands[j];
-         bits1[j] = C*N*m->allocVectors[mid*len+j]<<LM>>2;
-         if (bits1[j] > 0)
-            bits1[j] += trim_offset[j];
-         if (bits1[j] < 0)
-            bits1[j] = 0;
-         bits1[j] += offsets[j];
-         if (bits1[j] >= thresh[j])
-            psum += bits1[j];
-         else if (bits1[j] >= 1<<BITRES)
-            psum += 1<<BITRES;
-
-         /*printf ("%d ", bits[j]);*/
+         bitsj = C*N*m->allocVectors[mid*len+j]<<LM>>2;
+         if (bitsj > 0)
+            bitsj = IMAX(0, bitsj + trim_offset[j]);
+         bitsj += offsets[j];
+         if (bitsj >= thresh[j] || done)
+         {
+            done = 1;
+            /* Don't allocate more than we can actually use */
+            psum += IMIN(bitsj, cap[j]);
+         } else {
+            if (bitsj >= C<<BITRES)
+               psum += C<<BITRES;
+         }
       }
-      /*printf ("\n");*/
-      if (psum > (total<<BITRES))
-         hi = mid;
+      if (psum > total)
+         hi = mid - 1;
       else
-         lo = mid;
+         lo = mid + 1;
       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
    }
+   while (lo <= hi);
+   hi = lo--;
    /*printf ("interp between %d and %d\n", lo, hi);*/
    for (j=start;j<end;j++)
    {
+      int bits1j, bits2j;
       int N = m->eBands[j+1]-m->eBands[j];
-      bits1[j] = (C*N*m->allocVectors[lo*len+j]<<LM>>2);
-      bits2[j] = (C*N*m->allocVectors[hi*len+j]<<LM>>2) - bits1[j];
-      if (bits1[j] > 0)
-         bits1[j] += trim_offset[j];
-      if (bits1[j] < 0)
-         bits1[j] = 0;
-      bits1[j] += offsets[j];
+      bits1j = C*N*m->allocVectors[lo*len+j]<<LM>>2;
+      bits2j = hi>=m->nbAllocVectors ?
+            cap[j] : C*N*m->allocVectors[hi*len+j]<<LM>>2;
+      if (bits1j > 0)
+         bits1j = IMAX(0, bits1j + trim_offset[j]);
+      if (bits2j > 0)
+         bits2j = IMAX(0, bits2j + trim_offset[j]);
+      if (lo > 0)
+         bits1j += offsets[j];
+      bits2j += offsets[j];
+      if (offsets[j]>0)
+         skip_start = j;
+      bits2j = IMAX(0,bits2j-bits1j);
+      bits1[j] = bits1j;
+      bits2[j] = bits2j;
    }
-   codedBands = interp_bits2pulses(m, start, end, bits1, bits2, total, pulses, ebits, fine_priority, len, C, LM);
+   codedBands = interp_bits2pulses(m, start, end, skip_start, bits1, bits2, thresh, cap,
+         total, balance, skip_rsv, intensity, intensity_rsv, dual_stereo, dual_stereo_rsv,
+         pulses, ebits, fine_priority, C, LM, ec, encode, prev);
    RESTORE_STACK;
    return codedBands;
 }