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[CELT_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] + ((opus_int32)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 = celt_udiv(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             int depth_threshold;
    352             /*We choose a threshold with some hysteresis to keep bands from
    353                fluctuating in and out, but we try not to fold below a certain point. */
    354             if (codedBands > 17)
    355                depth_threshold = j<prev ? 7 : 9;
    356             else
    357                depth_threshold = 0;
    358 #ifdef FUZZING
    359             if ((rand()&0x1) == 0)
    360 #else
    361             if (codedBands<=start+2 || (band_bits > (depth_threshold*band_width<<LM<<BITRES)>>4 && j<=signalBandwidth))
    362 #endif
    363             {
    364                ec_enc_bit_logp(ec, 1, 1);
    365                break;
    366             }
    367             ec_enc_bit_logp(ec, 0, 1);
    368          } else if (ec_dec_bit_logp(ec, 1)) {
    369             break;
    370          }
    371          /*We used a bit to skip this band.*/
    372          psum += 1<<BITRES;
    373          band_bits -= 1<<BITRES;
    374       }
    375       /*Reclaim the bits originally allocated to this band.*/
    376       psum -= bits[j]+intensity_rsv;
    377       if (intensity_rsv > 0)
    378          intensity_rsv = LOG2_FRAC_TABLE[j-start];
    379       psum += intensity_rsv;
    380       if (band_bits >= alloc_floor)
    381       {
    382          /*If we have enough for a fine energy bit per channel, use it.*/
    383          psum += alloc_floor;
    384          bits[j] = alloc_floor;
    385       } else {
    386          /*Otherwise this band gets nothing at all.*/
    387          bits[j] = 0;
    388       }
    389    }
    390 
    391    celt_assert(codedBands > start);
    392    /* Code the intensity and dual stereo parameters. */
    393    if (intensity_rsv > 0)
    394    {
    395       if (encode)
    396       {
    397          *intensity = IMIN(*intensity, codedBands);
    398          ec_enc_uint(ec, *intensity-start, codedBands+1-start);
    399       }
    400       else
    401          *intensity = start+ec_dec_uint(ec, codedBands+1-start);
    402    }
    403    else
    404       *intensity = 0;
    405    if (*intensity <= start)
    406    {
    407       total += dual_stereo_rsv;
    408       dual_stereo_rsv = 0;
    409    }
    410    if (dual_stereo_rsv > 0)
    411    {
    412       if (encode)
    413          ec_enc_bit_logp(ec, *dual_stereo, 1);
    414       else
    415          *dual_stereo = ec_dec_bit_logp(ec, 1);
    416    }
    417    else
    418       *dual_stereo = 0;
    419 
    420    /* Allocate the remaining bits */
    421    left = total-psum;
    422    percoeff = celt_udiv(left, m->eBands[codedBands]-m->eBands[start]);
    423    left -= (m->eBands[codedBands]-m->eBands[start])*percoeff;
    424    for (j=start;j<codedBands;j++)
    425       bits[j] += ((int)percoeff*(m->eBands[j+1]-m->eBands[j]));
    426    for (j=start;j<codedBands;j++)
    427    {
    428       int tmp = (int)IMIN(left, m->eBands[j+1]-m->eBands[j]);
    429       bits[j] += tmp;
    430       left -= tmp;
    431    }
    432    /*for (j=0;j<end;j++)printf("%d ", bits[j]);printf("\n");*/
    433 
    434    balance = 0;
    435    for (j=start;j<codedBands;j++)
    436    {
    437       int N0, N, den;
    438       int offset;
    439       int NClogN;
    440       opus_int32 excess, bit;
    441 
    442       celt_assert(bits[j] >= 0);
    443       N0 = m->eBands[j+1]-m->eBands[j];
    444       N=N0<<LM;
    445       bit = (opus_int32)bits[j]+balance;
    446 
    447       if (N>1)
    448       {
    449          excess = MAX32(bit-cap[j],0);
    450          bits[j] = bit-excess;
    451 
    452          /* Compensate for the extra DoF in stereo */
    453          den=(C*N+ ((C==2 && N>2 && !*dual_stereo && j<*intensity) ? 1 : 0));
    454 
    455          NClogN = den*(m->logN[j] + logM);
    456 
    457          /* Offset for the number of fine bits by log2(N)/2 + FINE_OFFSET
    458             compared to their "fair share" of total/N */
    459          offset = (NClogN>>1)-den*FINE_OFFSET;
    460 
    461          /* N=2 is the only point that doesn't match the curve */
    462          if (N==2)
    463             offset += den<<BITRES>>2;
    464 
    465          /* Changing the offset for allocating the second and third
    466              fine energy bit */
    467          if (bits[j] + offset < den*2<<BITRES)
    468             offset += NClogN>>2;
    469          else if (bits[j] + offset < den*3<<BITRES)
    470             offset += NClogN>>3;
    471 
    472          /* Divide with rounding */
    473          ebits[j] = IMAX(0, (bits[j] + offset + (den<<(BITRES-1))));
    474          ebits[j] = celt_udiv(ebits[j], den)>>BITRES;
    475 
    476          /* Make sure not to bust */
    477          if (C*ebits[j] > (bits[j]>>BITRES))
    478             ebits[j] = bits[j] >> stereo >> BITRES;
    479 
    480          /* More than that is useless because that's about as far as PVQ can go */
    481          ebits[j] = IMIN(ebits[j], MAX_FINE_BITS);
    482 
    483          /* If we rounded down or capped this band, make it a candidate for the
    484              final fine energy pass */
    485          fine_priority[j] = ebits[j]*(den<<BITRES) >= bits[j]+offset;
    486 
    487          /* Remove the allocated fine bits; the rest are assigned to PVQ */
    488          bits[j] -= C*ebits[j]<<BITRES;
    489 
    490       } else {
    491          /* For N=1, all bits go to fine energy except for a single sign bit */
    492          excess = MAX32(0,bit-(C<<BITRES));
    493          bits[j] = bit-excess;
    494          ebits[j] = 0;
    495          fine_priority[j] = 1;
    496       }
    497 
    498       /* Fine energy can't take advantage of the re-balancing in
    499           quant_all_bands().
    500          Instead, do the re-balancing here.*/
    501       if(excess > 0)
    502       {
    503          int extra_fine;
    504          int extra_bits;
    505          extra_fine = IMIN(excess>>(stereo+BITRES),MAX_FINE_BITS-ebits[j]);
    506          ebits[j] += extra_fine;
    507          extra_bits = extra_fine*C<<BITRES;
    508          fine_priority[j] = extra_bits >= excess-balance;
    509          excess -= extra_bits;
    510       }
    511       balance = excess;
    512 
    513       celt_assert(bits[j] >= 0);
    514       celt_assert(ebits[j] >= 0);
    515    }
    516    /* Save any remaining bits over the cap for the rebalancing in
    517        quant_all_bands(). */
    518    *_balance = balance;
    519 
    520    /* The skipped bands use all their bits for fine energy. */
    521    for (;j<end;j++)
    522    {
    523       ebits[j] = bits[j] >> stereo >> BITRES;
    524       celt_assert(C*ebits[j]<<BITRES == bits[j]);
    525       bits[j] = 0;
    526       fine_priority[j] = ebits[j]<1;
    527    }
    528    RESTORE_STACK;
    529    return codedBands;
    530 }
    531 
    532 int clt_compute_allocation(const CELTMode *m, int start, int end, const int *offsets, const int *cap, int alloc_trim, int *intensity, int *dual_stereo,
    533       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)
    534 {
    535    int lo, hi, len, j;
    536    int codedBands;
    537    int skip_start;
    538    int skip_rsv;
    539    int intensity_rsv;
    540    int dual_stereo_rsv;
    541    VARDECL(int, bits1);
    542    VARDECL(int, bits2);
    543    VARDECL(int, thresh);
    544    VARDECL(int, trim_offset);
    545    SAVE_STACK;
    546 
    547    total = IMAX(total, 0);
    548    len = m->nbEBands;
    549    skip_start = start;
    550    /* Reserve a bit to signal the end of manually skipped bands. */
    551    skip_rsv = total >= 1<<BITRES ? 1<<BITRES : 0;
    552    total -= skip_rsv;
    553    /* Reserve bits for the intensity and dual stereo parameters. */
    554    intensity_rsv = dual_stereo_rsv = 0;
    555    if (C==2)
    556    {
    557       intensity_rsv = LOG2_FRAC_TABLE[end-start];
    558       if (intensity_rsv>total)
    559          intensity_rsv = 0;
    560       else
    561       {
    562          total -= intensity_rsv;
    563          dual_stereo_rsv = total>=1<<BITRES ? 1<<BITRES : 0;
    564          total -= dual_stereo_rsv;
    565       }
    566    }
    567    ALLOC(bits1, len, int);
    568    ALLOC(bits2, len, int);
    569    ALLOC(thresh, len, int);
    570    ALLOC(trim_offset, len, int);
    571 
    572    for (j=start;j<end;j++)
    573    {
    574       /* Below this threshold, we're sure not to allocate any PVQ bits */
    575       thresh[j] = IMAX((C)<<BITRES, (3*(m->eBands[j+1]-m->eBands[j])<<LM<<BITRES)>>4);
    576       /* Tilt of the allocation curve */
    577       trim_offset[j] = C*(m->eBands[j+1]-m->eBands[j])*(alloc_trim-5-LM)*(end-j-1)
    578             *(1<<(LM+BITRES))>>6;
    579       /* Giving less resolution to single-coefficient bands because they get
    580          more benefit from having one coarse value per coefficient*/
    581       if ((m->eBands[j+1]-m->eBands[j])<<LM==1)
    582          trim_offset[j] -= C<<BITRES;
    583    }
    584    lo = 1;
    585    hi = m->nbAllocVectors - 1;
    586    do
    587    {
    588       int done = 0;
    589       int psum = 0;
    590       int mid = (lo+hi) >> 1;
    591       for (j=end;j-->start;)
    592       {
    593          int bitsj;
    594          int N = m->eBands[j+1]-m->eBands[j];
    595          bitsj = C*N*m->allocVectors[mid*len+j]<<LM>>2;
    596          if (bitsj > 0)
    597             bitsj = IMAX(0, bitsj + trim_offset[j]);
    598          bitsj += offsets[j];
    599          if (bitsj >= thresh[j] || done)
    600          {
    601             done = 1;
    602             /* Don't allocate more than we can actually use */
    603             psum += IMIN(bitsj, cap[j]);
    604          } else {
    605             if (bitsj >= C<<BITRES)
    606                psum += C<<BITRES;
    607          }
    608       }
    609       if (psum > total)
    610          hi = mid - 1;
    611       else
    612          lo = mid + 1;
    613       /*printf ("lo = %d, hi = %d\n", lo, hi);*/
    614    }
    615    while (lo <= hi);
    616    hi = lo--;
    617    /*printf ("interp between %d and %d\n", lo, hi);*/
    618    for (j=start;j<end;j++)
    619    {
    620       int bits1j, bits2j;
    621       int N = m->eBands[j+1]-m->eBands[j];
    622       bits1j = C*N*m->allocVectors[lo*len+j]<<LM>>2;
    623       bits2j = hi>=m->nbAllocVectors ?
    624             cap[j] : C*N*m->allocVectors[hi*len+j]<<LM>>2;
    625       if (bits1j > 0)
    626          bits1j = IMAX(0, bits1j + trim_offset[j]);
    627       if (bits2j > 0)
    628          bits2j = IMAX(0, bits2j + trim_offset[j]);
    629       if (lo > 0)
    630          bits1j += offsets[j];
    631       bits2j += offsets[j];
    632       if (offsets[j]>0)
    633          skip_start = j;
    634       bits2j = IMAX(0,bits2j-bits1j);
    635       bits1[j] = bits1j;
    636       bits2[j] = bits2j;
    637    }
    638    codedBands = interp_bits2pulses(m, start, end, skip_start, bits1, bits2, thresh, cap,
    639          total, balance, skip_rsv, intensity, intensity_rsv, dual_stereo, dual_stereo_rsv,
    640          pulses, ebits, fine_priority, C, LM, ec, encode, prev, signalBandwidth);
    641    RESTORE_STACK;
    642    return codedBands;
    643 }
    644 
    645