The Tor Browser: modules/libbz2/src/decompress.c@129ffea94266 (annotated)

modules/libbz2/src/decompress.c@129ffea94266 (annotated)

modules/libbz2/src/decompress.c

Sat, 03 Jan 2015 20:18:00 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Sat, 03 Jan 2015 20:18:00 +0100
branch: TOR_BUG_3246
changeset 7: 129ffea94266
permissions: -rw-r--r--

Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.

 /*-------------------------------------------------------------*/
 /*--- Decompression machinery                               ---*/
 /*---                                          decompress.c ---*/
 /*-------------------------------------------------------------*/
 /* ------------------------------------------------------------------
    This file is part of bzip2/libbzip2, a program and library for
    lossless, block-sorting data compression.
    bzip2/libbzip2 version 1.0.4 of 20 December 2006
    Copyright (C) 1996-2006 Julian Seward <jseward@bzip.org>
    Please read the WARNING, DISCLAIMER and PATENTS sections in the
    README file.
    This program is released under the terms of the license contained
    in the file LICENSE.
    ------------------------------------------------------------------ */
 #include "bzlib_private.h"
 /*---------------------------------------------------*/
 static
 void makeMaps_d ( DState* s )
 {
    Int32 i;
    s->nInUse = 0;
    for (i = 0; i < 256; i++)
       if (s->inUse[i]) {
          s->seqToUnseq[s->nInUse] = i;
          s->nInUse++;
       }
 }
 /*---------------------------------------------------*/
 #define RETURN(rrr)                               \
    { retVal = rrr; goto save_state_and_return; };
 #define GET_BITS(lll,vvv,nnn)                     \
    case lll: s->state = lll;                      \
    while (True) {                                 \
       if (s->bsLive >= nnn) {                     \
          UInt32 v;                                \
          v = (s->bsBuff >>                        \
              (s->bsLive-nnn)) & ((1 << nnn)-1);   \
          s->bsLive -= nnn;                        \
          vvv = v;                                 \
          break;                                   \
       }                                           \
       if (s->strm->avail_in == 0) RETURN(BZ_OK);  \
       s->bsBuff                                   \
          = (s->bsBuff << 8) |                     \
            ((UInt32)                              \
               (*((UChar*)(s->strm->next_in))));   \
       s->bsLive += 8;                             \
       s->strm->next_in++;                         \
       s->strm->avail_in--;                        \
       s->strm->total_in_lo32++;                   \
       if (s->strm->total_in_lo32 == 0)            \
          s->strm->total_in_hi32++;                \
    }
 #define GET_UCHAR(lll,uuu)                        \
    GET_BITS(lll,uuu,8)
 #define GET_BIT(lll,uuu)                          \
    GET_BITS(lll,uuu,1)
 /*---------------------------------------------------*/
 #define GET_MTF_VAL(label1,label2,lval)           \
 {                                                 \
    if (groupPos == 0) {                           \
       groupNo++;                                  \
       if (groupNo >= nSelectors)                  \
          RETURN(BZ_DATA_ERROR);                   \
       groupPos = BZ_G_SIZE;                       \
       gSel = s->selector[groupNo];                \
       gMinlen = s->minLens[gSel];                 \
       gLimit = &(s->limit[gSel][0]);              \
       gPerm = &(s->perm[gSel][0]);                \
       gBase = &(s->base[gSel][0]);                \
    }                                              \
    groupPos--;                                    \
    zn = gMinlen;                                  \
    GET_BITS(label1, zvec, zn);                    \
    while (1) {                                    \
       if (zn > 20 /* the longest code */)         \
          RETURN(BZ_DATA_ERROR);                   \
       if (zvec <= gLimit[zn]) break;              \
       zn++;                                       \
       GET_BIT(label2, zj);                        \
       zvec = (zvec << 1) | zj;                    \
    };                                             \
    if (zvec - gBase[zn] < 0                       \
        || zvec - gBase[zn] >= BZ_MAX_ALPHA_SIZE)  \
       RETURN(BZ_DATA_ERROR);                      \
    lval = gPerm[zvec - gBase[zn]];                \
 }
 /*---------------------------------------------------*/
 Int32 BZ2_decompress ( DState* s )
 {
    UChar      uc;
    Int32      retVal;
    Int32      minLen, maxLen;
    bz_stream* strm = s->strm;
    /* stuff that needs to be saved/restored */
    Int32  i;
    Int32  j;
    Int32  t;
    Int32  alphaSize;
    Int32  nGroups;
    Int32  nSelectors;
    Int32  EOB;
    Int32  groupNo;
    Int32  groupPos;
    Int32  nextSym;
    Int32  nblockMAX;
    Int32  nblock;
    Int32  es;
    Int32  N;
    Int32  curr;
    Int32  zt;
    Int32  zn;
    Int32  zvec;
    Int32  zj;
    Int32  gSel;
    Int32  gMinlen;
    Int32* gLimit;
    Int32* gBase;
    Int32* gPerm;
    if (s->state == BZ_X_MAGIC_1) {
       /*initialise the save area*/
       s->save_i           = 0;
       s->save_j           = 0;
       s->save_t           = 0;
       s->save_alphaSize   = 0;
       s->save_nGroups     = 0;
       s->save_nSelectors  = 0;
       s->save_EOB         = 0;
       s->save_groupNo     = 0;
       s->save_groupPos    = 0;
       s->save_nextSym     = 0;
       s->save_nblockMAX   = 0;
       s->save_nblock      = 0;
       s->save_es          = 0;
       s->save_N           = 0;
       s->save_curr        = 0;
       s->save_zt          = 0;
       s->save_zn          = 0;
       s->save_zvec        = 0;
       s->save_zj          = 0;
       s->save_gSel        = 0;
       s->save_gMinlen     = 0;
       s->save_gLimit      = NULL;
       s->save_gBase       = NULL;
       s->save_gPerm       = NULL;
    }
    /*restore from the save area*/
    i           = s->save_i;
    j           = s->save_j;
    t           = s->save_t;
    alphaSize   = s->save_alphaSize;
    nGroups     = s->save_nGroups;
    nSelectors  = s->save_nSelectors;
    EOB         = s->save_EOB;
    groupNo     = s->save_groupNo;
    groupPos    = s->save_groupPos;
    nextSym     = s->save_nextSym;
    nblockMAX   = s->save_nblockMAX;
    nblock      = s->save_nblock;
    es          = s->save_es;
    N           = s->save_N;
    curr        = s->save_curr;
    zt          = s->save_zt;
    zn          = s->save_zn;
    zvec        = s->save_zvec;
    zj          = s->save_zj;
    gSel        = s->save_gSel;
    gMinlen     = s->save_gMinlen;
    gLimit      = s->save_gLimit;
    gBase       = s->save_gBase;
    gPerm       = s->save_gPerm;
    retVal = BZ_OK;
    switch (s->state) {
       GET_UCHAR(BZ_X_MAGIC_1, uc);
       if (uc != BZ_HDR_B) RETURN(BZ_DATA_ERROR_MAGIC);
       GET_UCHAR(BZ_X_MAGIC_2, uc);
       if (uc != BZ_HDR_Z) RETURN(BZ_DATA_ERROR_MAGIC);
       GET_UCHAR(BZ_X_MAGIC_3, uc)
       if (uc != BZ_HDR_h) RETURN(BZ_DATA_ERROR_MAGIC);
       GET_BITS(BZ_X_MAGIC_4, s->blockSize100k, 8)
       if (s->blockSize100k < (BZ_HDR_0 + 1) ||
           s->blockSize100k > (BZ_HDR_0 + 9)) RETURN(BZ_DATA_ERROR_MAGIC);
       s->blockSize100k -= BZ_HDR_0;
       if (s->smallDecompress) {
          s->ll16 = BZALLOC( s->blockSize100k * 100000 * sizeof(UInt16) );
          s->ll4  = BZALLOC(
                       ((1 + s->blockSize100k * 100000) >> 1) * sizeof(UChar)
                    );
          if (s->ll16 == NULL || s->ll4 == NULL) RETURN(BZ_MEM_ERROR);
       } else {
          s->tt  = BZALLOC( s->blockSize100k * 100000 * sizeof(Int32) );
          if (s->tt == NULL) RETURN(BZ_MEM_ERROR);
       }
       GET_UCHAR(BZ_X_BLKHDR_1, uc);
       if (uc == 0x17) goto endhdr_2;
       if (uc != 0x31) RETURN(BZ_DATA_ERROR);
       GET_UCHAR(BZ_X_BLKHDR_2, uc);
       if (uc != 0x41) RETURN(BZ_DATA_ERROR);
       GET_UCHAR(BZ_X_BLKHDR_3, uc);
       if (uc != 0x59) RETURN(BZ_DATA_ERROR);
       GET_UCHAR(BZ_X_BLKHDR_4, uc);
       if (uc != 0x26) RETURN(BZ_DATA_ERROR);
       GET_UCHAR(BZ_X_BLKHDR_5, uc);
       if (uc != 0x53) RETURN(BZ_DATA_ERROR);
       GET_UCHAR(BZ_X_BLKHDR_6, uc);
       if (uc != 0x59) RETURN(BZ_DATA_ERROR);
       s->currBlockNo++;
       if (s->verbosity >= 2)
          VPrintf1 ( "\n    [%d: huff+mtf ", s->currBlockNo );
       s->storedBlockCRC = 0;
       GET_UCHAR(BZ_X_BCRC_1, uc);
       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
       GET_UCHAR(BZ_X_BCRC_2, uc);
       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
       GET_UCHAR(BZ_X_BCRC_3, uc);
       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
       GET_UCHAR(BZ_X_BCRC_4, uc);
       s->storedBlockCRC = (s->storedBlockCRC << 8) | ((UInt32)uc);
       GET_BITS(BZ_X_RANDBIT, s->blockRandomised, 1);
       s->origPtr = 0;
       GET_UCHAR(BZ_X_ORIGPTR_1, uc);
       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
       GET_UCHAR(BZ_X_ORIGPTR_2, uc);
       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
       GET_UCHAR(BZ_X_ORIGPTR_3, uc);
       s->origPtr = (s->origPtr << 8) | ((Int32)uc);
       if (s->origPtr < 0)
          RETURN(BZ_DATA_ERROR);
       if (s->origPtr > 10 + 100000*s->blockSize100k)
          RETURN(BZ_DATA_ERROR);
       /*--- Receive the mapping table ---*/
       for (i = 0; i < 16; i++) {
          GET_BIT(BZ_X_MAPPING_1, uc);
          if (uc == 1)
             s->inUse16[i] = True; else
             s->inUse16[i] = False;
       }
       for (i = 0; i < 256; i++) s->inUse[i] = False;
       for (i = 0; i < 16; i++)
          if (s->inUse16[i])
             for (j = 0; j < 16; j++) {
                GET_BIT(BZ_X_MAPPING_2, uc);
                if (uc == 1) s->inUse[i * 16 + j] = True;
             }
       makeMaps_d ( s );
       if (s->nInUse == 0) RETURN(BZ_DATA_ERROR);
       alphaSize = s->nInUse+2;
       /*--- Now the selectors ---*/
       GET_BITS(BZ_X_SELECTOR_1, nGroups, 3);
       if (nGroups < 2 || nGroups > 6) RETURN(BZ_DATA_ERROR);
       GET_BITS(BZ_X_SELECTOR_2, nSelectors, 15);
       if (nSelectors < 1) RETURN(BZ_DATA_ERROR);
       for (i = 0; i < nSelectors; i++) {
          j = 0;
          while (True) {
             GET_BIT(BZ_X_SELECTOR_3, uc);
             if (uc == 0) break;
             j++;
             if (j >= nGroups) RETURN(BZ_DATA_ERROR);
          }
          s->selectorMtf[i] = j;
       }
       /*--- Undo the MTF values for the selectors. ---*/
       {
          UChar pos[BZ_N_GROUPS], tmp, v;
          for (v = 0; v < nGroups; v++) pos[v] = v;
          for (i = 0; i < nSelectors; i++) {
             v = s->selectorMtf[i];
             tmp = pos[v];
             while (v > 0) { pos[v] = pos[v-1]; v--; }
             pos[0] = tmp;
             s->selector[i] = tmp;
          }
       }
       /*--- Now the coding tables ---*/
       for (t = 0; t < nGroups; t++) {
          GET_BITS(BZ_X_CODING_1, curr, 5);
          for (i = 0; i < alphaSize; i++) {
             while (True) {
                if (curr < 1 || curr > 20) RETURN(BZ_DATA_ERROR);
                GET_BIT(BZ_X_CODING_2, uc);
                if (uc == 0) break;
                GET_BIT(BZ_X_CODING_3, uc);
                if (uc == 0) curr++; else curr--;
             }
             s->len[t][i] = curr;
          }
       }
       /*--- Create the Huffman decoding tables ---*/
       for (t = 0; t < nGroups; t++) {
          minLen = 32;
          maxLen = 0;
          for (i = 0; i < alphaSize; i++) {
             if (s->len[t][i] > maxLen) maxLen = s->len[t][i];
             if (s->len[t][i] < minLen) minLen = s->len[t][i];
          }
          BZ2_hbCreateDecodeTables (
             &(s->limit[t][0]),
             &(s->base[t][0]),
             &(s->perm[t][0]),
             &(s->len[t][0]),
             minLen, maxLen, alphaSize
          );
          s->minLens[t] = minLen;
       }
       /*--- Now the MTF values ---*/
       EOB      = s->nInUse+1;
       nblockMAX = 100000 * s->blockSize100k;
       groupNo  = -1;
       groupPos = 0;
       for (i = 0; i <= 255; i++) s->unzftab[i] = 0;
       /*-- MTF init --*/
       {
          Int32 ii, jj, kk;
          kk = MTFA_SIZE-1;
          for (ii = 256 / MTFL_SIZE - 1; ii >= 0; ii--) {
             for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
                s->mtfa[kk] = (UChar)(ii * MTFL_SIZE + jj);
                kk--;
             }
             s->mtfbase[ii] = kk + 1;
          }
       }
       /*-- end MTF init --*/
       nblock = 0;
       GET_MTF_VAL(BZ_X_MTF_1, BZ_X_MTF_2, nextSym);
       while (True) {
          if (nextSym == EOB) break;
          if (nextSym == BZ_RUNA || nextSym == BZ_RUNB) {
             es = -1;
             N = 1;
             do {
                if (nextSym == BZ_RUNA) es = es + (0+1) * N; else
                if (nextSym == BZ_RUNB) es = es + (1+1) * N;
                N = N * 2;
                GET_MTF_VAL(BZ_X_MTF_3, BZ_X_MTF_4, nextSym);
             }
                while (nextSym == BZ_RUNA || nextSym == BZ_RUNB);
             es++;
             uc = s->seqToUnseq[ s->mtfa[s->mtfbase[0]] ];
             s->unzftab[uc] += es;
             if (s->smallDecompress)
                while (es > 0) {
                   if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
                   s->ll16[nblock] = (UInt16)uc;
                   nblock++;
                   es--;
                }
             else
                while (es > 0) {
                   if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
                   s->tt[nblock] = (UInt32)uc;
                   nblock++;
                   es--;
                };
             continue;
          } else {
             if (nblock >= nblockMAX) RETURN(BZ_DATA_ERROR);
             /*-- uc = MTF ( nextSym-1 ) --*/
             {
                Int32 ii, jj, kk, pp, lno, off;
                UInt32 nn;
                nn = (UInt32)(nextSym - 1);
                if (nn < MTFL_SIZE) {
                   /* avoid general-case expense */
                   pp = s->mtfbase[0];
                   uc = s->mtfa[pp+nn];
                   while (nn > 3) {
                      Int32 z = pp+nn;
                      s->mtfa[(z)  ] = s->mtfa[(z)-1];
                      s->mtfa[(z)-1] = s->mtfa[(z)-2];
                      s->mtfa[(z)-2] = s->mtfa[(z)-3];
                      s->mtfa[(z)-3] = s->mtfa[(z)-4];
                      nn -= 4;
                   }
                   while (nn > 0) {
                      s->mtfa[(pp+nn)] = s->mtfa[(pp+nn)-1]; nn--;
                   };
                   s->mtfa[pp] = uc;
                } else {
                   /* general case */
                   lno = nn / MTFL_SIZE;
                   off = nn % MTFL_SIZE;
                   pp = s->mtfbase[lno] + off;
                   uc = s->mtfa[pp];
                   while (pp > s->mtfbase[lno]) {
                      s->mtfa[pp] = s->mtfa[pp-1]; pp--;
                   };
                   s->mtfbase[lno]++;
                   while (lno > 0) {
                      s->mtfbase[lno]--;
                      s->mtfa[s->mtfbase[lno]]
                         = s->mtfa[s->mtfbase[lno-1] + MTFL_SIZE - 1];
                      lno--;
                   }
                   s->mtfbase[0]--;
                   s->mtfa[s->mtfbase[0]] = uc;
                   if (s->mtfbase[0] == 0) {
                      kk = MTFA_SIZE-1;
                      for (ii = 256 / MTFL_SIZE-1; ii >= 0; ii--) {
                         for (jj = MTFL_SIZE-1; jj >= 0; jj--) {
                            s->mtfa[kk] = s->mtfa[s->mtfbase[ii] + jj];
                            kk--;
                         }
                         s->mtfbase[ii] = kk + 1;
                      }
                   }
                }
             }
             /*-- end uc = MTF ( nextSym-1 ) --*/
             s->unzftab[s->seqToUnseq[uc]]++;
             if (s->smallDecompress)
                s->ll16[nblock] = (UInt16)(s->seqToUnseq[uc]); else
                s->tt[nblock]   = (UInt32)(s->seqToUnseq[uc]);
             nblock++;
             GET_MTF_VAL(BZ_X_MTF_5, BZ_X_MTF_6, nextSym);
             continue;
          }
       }
       /* Now we know what nblock is, we can do a better sanity
          check on s->origPtr.
       */
       if (s->origPtr < 0 || s->origPtr >= nblock)
          RETURN(BZ_DATA_ERROR);
       /*-- Set up cftab to facilitate generation of T^(-1) --*/
       s->cftab[0] = 0;
       for (i = 1; i <= 256; i++) s->cftab[i] = s->unzftab[i-1];
       for (i = 1; i <= 256; i++) s->cftab[i] += s->cftab[i-1];
       for (i = 0; i <= 256; i++) {
          if (s->cftab[i] < 0 || s->cftab[i] > nblock) {
             /* s->cftab[i] can legitimately be == nblock */
             RETURN(BZ_DATA_ERROR);
          }
       }
       s->state_out_len = 0;
       s->state_out_ch  = 0;
       BZ_INITIALISE_CRC ( s->calculatedBlockCRC );
       s->state = BZ_X_OUTPUT;
       if (s->verbosity >= 2) VPrintf0 ( "rt+rld" );
       if (s->smallDecompress) {
          /*-- Make a copy of cftab, used in generation of T --*/
          for (i = 0; i <= 256; i++) s->cftabCopy[i] = s->cftab[i];
          /*-- compute the T vector --*/
          for (i = 0; i < nblock; i++) {
             uc = (UChar)(s->ll16[i]);
             SET_LL(i, s->cftabCopy[uc]);
             s->cftabCopy[uc]++;
          }
          /*-- Compute T^(-1) by pointer reversal on T --*/
          i = s->origPtr;
          j = GET_LL(i);
          do {
             Int32 tmp = GET_LL(j);
             SET_LL(j, i);
             i = j;
             j = tmp;
          }
             while (i != s->origPtr);
          s->tPos = s->origPtr;
          s->nblock_used = 0;
          if (s->blockRandomised) {
             BZ_RAND_INIT_MASK;
             BZ_GET_SMALL(s->k0); s->nblock_used++;
             BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
          } else {
             BZ_GET_SMALL(s->k0); s->nblock_used++;
          }
       } else {
          /*-- compute the T^(-1) vector --*/
          for (i = 0; i < nblock; i++) {
             uc = (UChar)(s->tt[i] & 0xff);
             s->tt[s->cftab[uc]] |= (i << 8);
             s->cftab[uc]++;
          }
          s->tPos = s->tt[s->origPtr] >> 8;
          s->nblock_used = 0;
          if (s->blockRandomised) {
             BZ_RAND_INIT_MASK;
             BZ_GET_FAST(s->k0); s->nblock_used++;
             BZ_RAND_UPD_MASK; s->k0 ^= BZ_RAND_MASK;
          } else {
             BZ_GET_FAST(s->k0); s->nblock_used++;
          }
       }
       RETURN(BZ_OK);
     endhdr_2:
       GET_UCHAR(BZ_X_ENDHDR_2, uc);
       if (uc != 0x72) RETURN(BZ_DATA_ERROR);
       GET_UCHAR(BZ_X_ENDHDR_3, uc);
       if (uc != 0x45) RETURN(BZ_DATA_ERROR);
       GET_UCHAR(BZ_X_ENDHDR_4, uc);
       if (uc != 0x38) RETURN(BZ_DATA_ERROR);
       GET_UCHAR(BZ_X_ENDHDR_5, uc);
       if (uc != 0x50) RETURN(BZ_DATA_ERROR);
       GET_UCHAR(BZ_X_ENDHDR_6, uc);
       if (uc != 0x90) RETURN(BZ_DATA_ERROR);
       s->storedCombinedCRC = 0;
       GET_UCHAR(BZ_X_CCRC_1, uc);
       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
       GET_UCHAR(BZ_X_CCRC_2, uc);
       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
       GET_UCHAR(BZ_X_CCRC_3, uc);
       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
       GET_UCHAR(BZ_X_CCRC_4, uc);
       s->storedCombinedCRC = (s->storedCombinedCRC << 8) | ((UInt32)uc);
       s->state = BZ_X_IDLE;
       RETURN(BZ_STREAM_END);
       default: AssertH ( False, 4001 );
    }
    AssertH ( False, 4002 );
    save_state_and_return:
    s->save_i           = i;
    s->save_j           = j;
    s->save_t           = t;
    s->save_alphaSize   = alphaSize;
    s->save_nGroups     = nGroups;
    s->save_nSelectors  = nSelectors;
    s->save_EOB         = EOB;
    s->save_groupNo     = groupNo;
    s->save_groupPos    = groupPos;
    s->save_nextSym     = nextSym;
    s->save_nblockMAX   = nblockMAX;
    s->save_nblock      = nblock;
    s->save_es          = es;
    s->save_N           = N;
    s->save_curr        = curr;
    s->save_zt          = zt;
    s->save_zn          = zn;
    s->save_zvec        = zvec;
    s->save_zj          = zj;
    s->save_gSel        = gSel;
    s->save_gMinlen     = gMinlen;
    s->save_gLimit      = gLimit;
    s->save_gBase       = gBase;
    s->save_gPerm       = gPerm;
    return retVal;
 }
 /*-------------------------------------------------------------*/
 /*--- end                                      decompress.c ---*/
 /*-------------------------------------------------------------*/

The Tor Browser / annotate

modules/libbz2/src/decompress.c@129ffea94266 (annotated)

modules/libbz2/src/decompress.c