Home | History | Annotate | Download | only in celt
      1 /* Copyright (c) 2007-2008 CSIRO
      2    Copyright (c) 2007-2009 Xiph.Org Foundation
      3    Written by Jean-Marc Valin */
      4 /*
      5    Redistribution and use in source and binary forms, with or without
      6    modification, are permitted provided that the following conditions
      7    are met:
      8 
      9    - Redistributions of source code must retain the above copyright
     10    notice, this list of conditions and the following disclaimer.
     11 
     12    - Redistributions in binary form must reproduce the above copyright
     13    notice, this list of conditions and the following disclaimer in the
     14    documentation and/or other materials provided with the distribution.
     15 
     16    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17    ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19    A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
     20    OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
     21    EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
     22    PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
     23    PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
     24    LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
     25    NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
     26    SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 */
     28 
     29 #ifdef HAVE_CONFIG_H
     30 #include "config.h"
     31 #endif
     32 
     33 #include <math.h>
     34 #include "modes.h"
     35 #include "cwrs.h"
     36 #include "arch.h"
     37 #include "os_support.h"
     38 
     39 #include "entcode.h"
     40 #include "rate.h"
     41 
     42 static const unsigned char LOG2_FRAC_TABLE[24]={
     43    0,
     44    8,13,
     45   16,19,21,23,
     46   24,26,27,28,29,30,31,32,
     47   32,33,34,34,35,36,36,37,37
     48 };
     49 
     50 #ifdef CUSTOM_MODES
     51 
     52 /*Determines if V(N,K) fits in a 32-bit unsigned integer.
     53   N and K are themselves limited to 15 bits.*/
     54 static int fits_in32(int _n, int _k)
     55 {
     56    static const opus_int16 maxN[15] = {
     57       32767, 32767, 32767, 1476, 283, 109,  60,  40,
     58        29,  24,  20,  18,  16,  14,  13};
     59    static const opus_int16 maxK[15] = {
     60       32767, 32767, 32767, 32767, 1172, 238,  95,  53,
     61        36,  27,  22,  18,  16,  15,  13};
     62    if (_n>=14)
     63    {
     64       if (_k>=14)
     65          return 0;
     66       else
     67          return _n <= maxN[_k];
     68    } else {
     69       return _k <= maxK[_n];
     70    }
     71 }
     72 
     73 void compute_pulse_cache(CELTMode *m, int LM)
     74 {
     75    int C;
     76    int i;
     77    int j;
     78    int curr=0;
     79    int nbEntries=0;
     80    int entryN[100], entryK[100], entryI[100];
     81    const opus_int16 *eBands = m->eBands;
     82    PulseCache *cache = &m->cache;
     83    opus_int16 *cindex;
     84    unsigned char *bits;
     85    unsigned char *cap;
     86 
     87    cindex = (opus_int16 *)opus_alloc(sizeof(cache->index[0])*m->nbEBands*(LM+2));
     88    cache->index = cindex;
     89 
     90    /* Scan for all unique band sizes */
     91    for (i=0;i<=LM+1;i++)
     92    {
     93       for (j=0;j<m->nbEBands;j++)
     94       {
     95          int k;
     96          int N = (eBands[j+1]-eBands[j])<<i>>1;
     97          cindex[i*m->nbEBands+j] = -1;
     98          /* Find other bands that have the same size */
     99          for (k=0;k<=i;k++)
    100          {
    101             int n;
    102             for (n=0;n<m->nbEBands && (k!=i || n<j);n++)
    103             {
    104                if (N == (eBands[n+1]-eBands[n])<<k>>1)
    105                {
    106                   cindex[i*m->nbEBands+j] = cindex[k*m->nbEBands+n];
    107                   break;
    108                }
    109             }
    110          }
    111          if (cache->index[i*m->nbEBands+j] == -1 && N!=0)
    112          {
    113             int K;
    114             entryN[nbEntries] = N;
    115             K = 0;
    116             while (fits_in32(N,get_pulses(K+1)) && K<MAX_PSEUDO)
    117                K++;
    118             entryK[nbEntries] = K;
    119             cindex[i*m->nbEBands+j] = curr;
    120             entryI[nbEntries] = curr;
    121 
    122             curr += K+1;
    123             nbEntries++;
    124          }
    125       }
    126    }
    127    bits = (unsigned char *)opus_alloc(sizeof(unsigned char)*curr);
    128    cache->bits = bits;
    129    cache->size = curr;
    130    /* Compute the cache for all unique sizes */
    131    for (i=0;i<nbEntries;i++)
    132    {
    133       unsigned char *ptr = bits+entryI[i];
    134       opus_int16 tmp[MAX_PULSES+1];
    135       get_required_bits(tmp, entryN[i], get_pulses(entryK[i]), BITRES);
    136       for (j=1;j<=entryK[i];j++)
    137          ptr[j] = tmp[get_pulses(j)]-1;
    138       ptr[0] = entryK[i];
    139    }
    140 
    141    /* Compute the maximum rate for each band at which we'll reliably use as
    142        many bits as we ask for. */
    143    cache->caps = cap = (unsigned char *)opus_alloc(sizeof(cache->caps[0])*(LM+1)*2*m->nbEBands);
    144    for (i=0;i<=LM;i++)
    145    {
    146       for (C=1;C<=2;C++)
    147       {
    148          for (j=0;j<m->nbEBands;j++)
    149          {
    150             int N0;
    151             int max_bits;
    152             N0 = m->eBands[j+1]-m->eBands[j];
    153             /* N=1 bands only have a sign bit and fine bits. */
    154             if (N0<<i == 1)
    155                max_bits = C*(1+MAX_FINE_BITS)<<BITRES;
    156             else
    157             {
    158                const unsigned char *pcache;
    159                opus_int32           num;
    160                opus_int32           den;
    161                int                  LM0;
    162                int                  N;
    163                int                  offset;
    164                int                  ndof;
    165                int                  qb;
    166                int                  k;
    167                LM0 = 0;
    168                /* Even-sized bands bigger than N=2 can be split one more time.
    169                   As of commit 44203907 all bands >1 are even, including custom modes.*/
    170                if (N0 > 2)
    171                {
    172                   N0>>=1;
    173                   LM0--;
    174                }
    175                /* N0=1 bands can't be split down to N<2. */
    176                else if (N0 <= 1)
    177                {
    178                   LM0=IMIN(i,1);
    179                   N0<<=LM0;
    180                }
    181                /* Compute the cost for the lowest-level PVQ of a fully split
    182                    band. */
    183                pcache = bits + cindex[(LM0+1)*m->nbEBands+j];
    184                max_bits = pcache[pcache[0]]+1;
    185                /* Add in the cost of coding regular splits. */
    186                N = N0;
    187                for(k=0;k<i-LM0;k++){
    188                   max_bits <<= 1;
    189                   /* Offset the number of qtheta bits by log2(N)/2
    190                       + QTHETA_OFFSET compared to their "fair share" of
    191                       total/N */
    192                   offset = ((m->logN[j]+((LM0+k)<<BITRES))>>1)-QTHETA_OFFSET;
    193                   /* The number of qtheta bits we'll allocate if the remainder
    194                       is to be max_bits.
    195                      The average measured cost for theta is 0.89701 times qb,
    196                       approximated here as 459/512. */
    197                   num=459*(opus_int32)((2*N-1)*offset+max_bits);
    198                   den=((opus_int32)(2*N-1)<<9)-459;
    199                   qb = IMIN((num+(den>>1))/den, 57);
    200                   celt_assert(qb >= 0);
    201                   max_bits += qb;
    202                   N <<= 1;
    203                }
    204                /* Add in the cost of a stereo split, if necessary. */
    205                if (C==2)
    206                {
    207                   max_bits <<= 1;
    208                   offset = ((m->logN[j]+(i<<BITRES))>>1)-(N==2?QTHETA_OFFSET_TWOPHASE:QTHETA_OFFSET);
    209                   ndof = 2*N-1-(N==2);
    210                   /* The average measured cost for theta with the step PDF is
    211                       0.95164 times qb, approximated here as 487/512. */
    212                   num = (N==2?512:487)*(opus_int32)(max_bits+ndof*offset);
    213                   den = ((opus_int32)ndof<<9)-(N==2?512:487);
    214                   qb = IMIN((num+(den>>1))/den, (N==2?64:61));
    215                   celt_assert(qb >= 0);
    216                   max_bits += qb;
    217                }
    218                /* Add the fine bits we'll use. */
    219                /* Compensate for the extra DoF in stereo */
    220                ndof = C*N + ((C==2 && N>2) ? 1 : 0);
    221                /* Offset the number of fine bits by log2(N)/2 + FINE_OFFSET
    222                    compared to their "fair share" of total/N */
    223                offset = ((m->logN[j] + (i<<BITRES))>>1)-FINE_OFFSET;
    224                /* N=2 is the only point that doesn't match the curve */
    225                if (N==2)
    226                   offset += 1<<BITRES>>2;
    227                /* The number of fine bits we'll allocate if the remainder is
    228                    to be max_bits. */
    229                num = max_bits+ndof*offset;
    230                den = (ndof-1)<<BITRES;
    231                qb = IMIN((num+(den>>1))/den, MAX_FINE_BITS);
    232                celt_assert(qb >= 0);
    233                max_bits += C*qb<<BITRES;
    234             }
    235             max_bits = (4*max_bits/(C*((m->eBands[j+1]-m->eBands[j])<<i)))-64;
    236             celt_assert(max_bits >= 0);
    237             celt_assert(max_bits < 256);
    238             *cap++ = (unsigned char)max_bits;
    239          }
    240       }
    241    }
    242 }
    243 
    244 #endif /* CUSTOM_MODES */
    245 
    246 #define ALLOC_STEPS 6
    247 
    248 static OPUS_INLINE int interp_bits2pulses(const CELTMode *m, int start, int end, int skip_start,
    249       const int *bits1, const int *bits2, const int *thresh, const int *cap, opus_int32 total, opus_int32 *_balance,
    250       int skip_rsv, int *intensity, int intensity_rsv, int *dual_stereo, int dual_stereo_rsv, int *bits,
    251       int *ebits, int *fine_priority, int C, int LM, ec_ctx *ec, int encode, int prev, int signalBandwidth)
    252 {
    253    opus_int32 psum;
    254    int lo, hi;
    255    int i, j;
    256    int logM;
    257    int stereo;
    258    int codedBands=-1;
    259    int alloc_floor;
    260    opus_int32 left, percoeff;
    261    int done;
    262    opus_int32 balance;
    263    SAVE_STACK;
    264 
    265    alloc_floor = C<<BITRES;
    266    stereo = C>1;
    267 
    268    logM = LM<<BITRES;
    269    lo = 0;
    270    hi = 1<<ALLOC_STEPS;
    271    for (i=0;i<ALLOC_STEPS;i++)
    272    {
    273       int mid = (lo+hi)>>1;
    274       psum = 0;
    275       done = 0;
    276       for (j=end;j-->start;)
    277       {
    278          int tmp = bits1[j] + (mid*(opus_int32)bits2[j]>>ALLOC_STEPS);
    279          if (tmp >= thresh[j] || done)
    280          {
    281             done = 1;
    282             /* Don't allocate more than we can actually use */
    283             psum += IMIN(tmp, cap[j]);
    284          } else {
    285             if (tmp >= alloc_floor)
    286                psum += alloc_floor;
    287          }
    288       }
    289       if (psum > total)
    290          hi = mid;
    291       else
    292          lo = mid;
    293    }
    294    psum = 0;
    295    /*printf ("interp bisection gave %d\n", lo);*/
    296    done = 0;
    297    for (j=end;j-->start;)
    298    {
    299       int tmp = bits1[j] + (lo*bits2[j]>>ALLOC_STEPS);
    300       if (tmp < thresh[j] && !done)
    301       {
    302          if (tmp >= alloc_floor)
    303             tmp = alloc_floor;
    304          else
    305             tmp = 0;
    306       } else
    307          done = 1;
    308       /* Don't allocate more than we can actually use */
    309       tmp = IMIN(tmp, cap[j]);
    310       bits[j] = tmp;
    311       psum += tmp;
    312    }
    313 
    314    /* Decide which bands to skip, working backwards from the end. */
    315    for (codedBands=end;;codedBands--)
    316    {
    317       int band_width;
    318       int band_bits;
    319       int rem;
    320       j = codedBands-1;
    321       /* Never skip the first band, nor a band that has been boosted by
    322           dynalloc.
    323          In the first case, we'd be coding a bit to signal we're going to waste
    324           all the other bits.
    325          In the second case, we'd be coding a bit to redistribute all the bits
    326           we just signaled should be cocentrated in this band. */
    327       if (j<=skip_start)
    328       {
    329          /* Give the bit we reserved to end skipping back. */
    330          total += skip_rsv;
    331          break;
    332       }
    333       /*Figure out how many left-over bits we would be adding to this band.
    334         This can include bits we've stolen back from higher, skipped bands.*/
    335       left = total-psum;
    336       percoeff = left/(m->eBands[codedBands]-m->eBands[start]);
    337       left -= (m->eBands[codedBands]-m->eBands[start])*percoeff;
    338       rem = IMAX(left-(m->eBands[j]-m->eBands[start]),0);
    339       band_width = m->eBands[codedBands]-m->eBands[j];
    340       band_bits = (int)(bits[j] + percoeff*band_width + rem);
    341       /*Only code a skip decision if we're above the threshold for this band.
    342         Otherwise it is force-skipped.
    343         This ensures that we have enough bits to code the skip flag.*/
    344       if (band_bits >= IMAX(thresh[j], alloc_floor+(1<<BITRES)))
    345       {
    346          if (encode)
    347          {
    348             /*This if() block is the only part of the allocation function that
    349                is not a mandatory part of the bitstream: any bands we choose to
    350                skip here must be explicitly signaled.*/
    351             /*Choose a threshold with some hysteresis to keep bands from
    352                fluctuating in and out.*/
    353 #ifdef FUZZING
    354             if ((rand()&0x1) == 0)
    355 #else
    356             if (codedBands<=start+2 || (band_bits > ((j<prev?7:9)*band_width<<LM<<BITRES)>>4 && j<=signalBandwidth))
    357 #endif
    358             {
    359                ec_enc_bit_logp(ec, 1, 1);
    360                break;
    361             }
    362             ec_enc_bit_logp(ec, 0, 1);
    363          } else if (ec_dec_bit_logp(ec, 1)) {
    364             break;
    365          }
    366          /*We used a bit to skip this band.*/
    367          psum += 1<<BITRES;
    368          band_bits -= 1<<BITRES;
    369       }
    370       /*Reclaim the bits originally allocated to this band.*/
    371       psum -= bits[j]+intensity_rsv;
    372       if (intensity_rsv > 0)
    373          intensity_rsv = LOG2_FRAC_TABLE[j-start];
    374       psum += intensity_rsv;
    375       if (band_bits >= alloc_floor)
    376       {
    377          /*If we have enough for a fine energy bit per channel, use it.*/
    378          psum += alloc_floor;
    379          bits[j] = alloc_floor;
    380       } else {
    381          /*Otherwise this band gets nothing at all.*/
    382          bits[j] = 0;
    383       }
    384    }
    385 
    386    celt_assert(codedBands > start);
    387    /* Code the intensity and dual stereo parameters. */
    388    if (intensity_rsv > 0)
    389    {
    390       if (encode)
    391       {
    392          *intensity = IMIN(*intensity, codedBands);
    393          ec_enc_uint(ec, *intensity-start, codedBands+1-start);
    394       }
    395       else
    396          *intensity = start+ec_dec_uint(ec, codedBands+1-start);
    397    }
    398    else
    399       *intensity = 0;
    400    if (*intensity <= start)
    401    {
    402       total += dual_stereo_rsv;
    403       dual_stereo_rsv = 0;
    404    }
    405    if (dual_stereo_rsv > 0)
    406    {
    407       if (encode)
    408          ec_enc_bit_logp(ec, *dual_stereo, 1);
    409       else
    410          *dual_stereo = ec_dec_bit_logp(ec, 1);
    411    }
    412    else
    413       *dual_stereo = 0;
    414 
    415    /* Allocate the remaining bits */
    416    left = total-psum;
    417    percoeff = left/(m->eBands[codedBands]-m->eBands[start]);
    418    left -= (m->eBands[codedBands]-m->eBands[start])*percoeff;
    419    for (j=start;j<codedBands;j++)
    420       bits[j] += ((int)percoeff*(m->eBands[j+1]-m->eBands[j]));
    421    for (j=start;j<codedBands;j++)
    422    {
    423       int tmp = (int)IMIN(left, m->eBands[j+1]-m->eBands[j]);
    424       bits[j] += tmp;
    425       left -= tmp;
    426    }
    427    /*for (j=0;j<end;j++)printf("%d ", bits[j]);printf("\n");*/
    428 
    429    balance = 0;
    430    for (j=start;j<codedBands;j++)
    431    {
    432       int N0, N, den;
    433       int offset;
    434       int NClogN;
    435       opus_int32 excess, bit;
    436 
    437       celt_assert(bits[j] >= 0);
    438       N0 = m->eBands[j+1]-m->eBands[j];
    439       N=N0<<LM;
    440       bit = (opus_int32)bits[j]+balance;
    441 
    442       if (N>1)
    443       {
    444          excess = MAX32(bit-cap[j],0);
    445          bits[j] = bit-excess;
    446 
    447          /* Compensate for the extra DoF in stereo */
    448          den=(C*N+ ((C==2 && N>2 && !*dual_stereo && j<*intensity) ? 1 : 0));
    449 
    450          NClogN = den*(m->logN[j] + logM);
    451 
    452          /* Offset for the number of fine bits by log2(N)/2 + FINE_OFFSET
    453             compared to their "fair share" of total/N */
    454          offset = (NClogN>>1)-den*FINE_OFFSET;
    455 
    456          /* N=2 is the only point that doesn't match the curve */
    457          if (N==2)
    458             offset += den<<BITRES>>2;
    459 
    460          /* Changing the offset for allocating the second and third
    461              fine energy bit */
    462          if (bits[j] + offset < den*2<<BITRES)
    463             offset += NClogN>>2;
    464          else if (bits[j] + offset < den*3<<BITRES)
    465             offset += NClogN>>3;
    466 
    467          /* Divide with rounding */
    468          ebits[j] = IMAX(0, (bits[j] + offset + (den<<(BITRES-1))) / (den<<BITRES));
    469 
    470          /* Make sure not to bust */
    471          if (C*ebits[j] > (bits[j]>>BITRES))
    472             ebits[j] = bits[j] >> stereo >> BITRES;
    473 
    474          /* More than that is useless because that's about as far as PVQ can go */
    475          ebits[j] = IMIN(ebits[j], MAX_FINE_BITS);
    476 
    477          /* If we rounded down or capped this band, make it a candidate for the
    478              final fine energy pass */
    479          fine_priority[j] = ebits[j]*(den<<BITRES) >= bits[j]+offset;
    480 
    481          /* Remove the allocated fine bits; the rest are assigned to PVQ */
    482          bits[j] -= C*ebits[j]<<BITRES;
    483 
    484       } else {
    485          /* For N=1, all bits go to fine energy except for a single sign bit */
    486          excess = MAX32(0,bit-(C<<BITRES));
    487          bits[j] = bit-excess;
    488          ebits[j] = 0;
    489          fine_priority[j] = 1;
    490       }
    491 
    492       /* Fine energy can't take advantage of the re-balancing in
    493           quant_all_bands().
    494          Instead, do the re-balancing here.*/
    495       if(excess > 0)
    496       {
    497          int extra_fine;
    498          int extra_bits;
    499          extra_fine = IMIN(excess>>(stereo+BITRES),MAX_FINE_BITS-ebits[j]);
    500          ebits[j] += extra_fine;
    501          extra_bits = extra_fine*C<<BITRES;
    502          fine_priority[j] = extra_bits >= excess-balance;
    503          excess -= extra_bits;
    504       }
    505       balance = excess;
    506 
    507       celt_assert(bits[j] >= 0);
    508       celt_assert(ebits[j] >= 0);
    509    }
    510    /* Save any remaining bits over the cap for the rebalancing in
    511        quant_all_bands(). */
    512    *_balance = balance;
    513 
    514    /* The skipped bands use all their bits for fine energy. */
    515    for (;j<end;j++)
    516    {
    517       ebits[j] = bits[j] >> stereo >> BITRES;
    518       celt_assert(C*ebits[j]<<BITRES == bits[j]);
    519       bits[j] = 0;
    520       fine_priority[j] = ebits[j]<1;
    521    }
    522    RESTORE_STACK;
    523    return codedBands;
    524 }
    525 
    526 int compute_allocation(const CELTMode *m, int start, int end, const int *offsets, const int *cap, int alloc_trim, int *intensity, int *dual_stereo,
    527       opus_int32 total, opus_int32 *balance, int *pulses, int *ebits, int *fine_priority, int C, int LM, ec_ctx *ec, int encode, int prev, int signalBandwidth)
    528 {
    529    int lo, hi, len, j;
    530    int codedBands;
    531    int skip_start;
    532    int skip_rsv;
    533    int intensity_rsv;
    534    int dual_stereo_rsv;
    535    VARDECL(int, bits1);
    536    VARDECL(int, bits2);
    537    VARDECL(int, thresh);
    538    VARDECL(int, trim_offset);
    539    SAVE_STACK;
    540 
    541    total = IMAX(total, 0);
    542    len = m->nbEBands;
    543    skip_start = start;
    544    /* Reserve a bit to signal the end of manually skipped bands. */
    545    skip_rsv = total >= 1<<BITRES ? 1<<BITRES : 0;
    546    total -= skip_rsv;
    547    /* Reserve bits for the intensity and dual stereo parameters. */
    548    intensity_rsv = dual_stereo_rsv = 0;
    549    if (C==2)
    550    {
    551       intensity_rsv = LOG2_FRAC_TABLE[end-start];
    552       if (intensity_rsv>total)
    553          intensity_rsv = 0;
    554       else
    555       {
    556          total -= intensity_rsv;
    557          dual_stereo_rsv = total>=1<<BITRES ? 1<<BITRES : 0;
    558          total -= dual_stereo_rsv;
    559       }
    560    }
    561    ALLOC(bits1, len, int);
    562    ALLOC(bits2, len, int);
    563    ALLOC(thresh, len, int);
    564    ALLOC(trim_offset, len, int);
    565 
    566    for (j=start;j<end;j++)
    567    {
    568       /* Below this threshold, we're sure not to allocate any PVQ bits */
    569       thresh[j] = IMAX((C)<<BITRES, (3*(m->eBands[j+1]-m->eBands[j])<<LM<<BITRES)>>4);
    570       /* Tilt of the allocation curve */
    571       trim_offset[j] = C*(m->eBands[j+1]-m->eBands[j])*(alloc_trim-5-LM)*(end-j-1)
    572             *(1<<(LM+BITRES))>>6;
    573       /* Giving less resolution to single-coefficient bands because they get
    574          more benefit from having one coarse value per coefficient*/
    575       if ((m->eBands[j+1]-m->eBands[j])<<LM==1)
    576          trim_offset[j] -= C<<BITRES;
    577    }
    578    lo = 1;
    579    hi = m->nbAllocVectors - 1;
    580    do
    581    {
    582       int done = 0;
    583       int psum = 0;
    584       int mid = (lo+hi) >> 1;
    585       for (j=end;j-->start;)
    586       {
    587          int bitsj;
    588          int N = m->eBands[j+1]-m->eBands[j];
    589          bitsj = C*N*m->allocVectors[mid*len+j]<<LM>>2;
    590          if (bitsj > 0)
    591             bitsj = IMAX(0, bitsj + trim_offset[j]);
    592          bitsj += offsets[j];
    593          if (bitsj >= thresh[j] || done)
    594          {
    595             done = 1;
    596             /* Don't allocate more than we can actually use */
    597             psum += IMIN(bitsj, cap[j]);
    598          } else {
    599             if (bitsj >= C<<BITRES)
    600                psum += C<<BITRES;
    601          }
    602       }
    603       if (psum > total)
    604          hi = mid - 1;
    605       else
    606          lo = mid + 1;
    607       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
    608    }
    609    while (lo <= hi);
    610    hi = lo--;
    611    /*printf ("interp between %d and %d\n", lo, hi);*/
    612    for (j=start;j<end;j++)
    613    {
    614       int bits1j, bits2j;
    615       int N = m->eBands[j+1]-m->eBands[j];
    616       bits1j = C*N*m->allocVectors[lo*len+j]<<LM>>2;
    617       bits2j = hi>=m->nbAllocVectors ?
    618             cap[j] : C*N*m->allocVectors[hi*len+j]<<LM>>2;
    619       if (bits1j > 0)
    620          bits1j = IMAX(0, bits1j + trim_offset[j]);
    621       if (bits2j > 0)
    622          bits2j = IMAX(0, bits2j + trim_offset[j]);
    623       if (lo > 0)
    624          bits1j += offsets[j];
    625       bits2j += offsets[j];
    626       if (offsets[j]>0)
    627          skip_start = j;
    628       bits2j = IMAX(0,bits2j-bits1j);
    629       bits1[j] = bits1j;
    630       bits2[j] = bits2j;
    631    }
    632    codedBands = interp_bits2pulses(m, start, end, skip_start, bits1, bits2, thresh, cap,
    633          total, balance, skip_rsv, intensity, intensity_rsv, dual_stereo, dual_stereo_rsv,
    634          pulses, ebits, fine_priority, C, LM, ec, encode, prev, signalBandwidth);
    635    RESTORE_STACK;
    636    return codedBands;
    637 }
    638 
    639