[ tor-browser ].git.dasho

LzFind.c (25920B)
      1 /* LzFind.c -- Match finder for LZ algorithms
      2 2017-06-10 : Igor Pavlov : Public domain */
      3 
      4 #include "Precomp.h"
      5 
      6 #include <string.h>
      7 
      8 #include "LzFind.h"
      9 #include "LzHash.h"
     10 
     11 #define kEmptyHashValue 0
     12 #define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
     13 #define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
     14 #define kNormalizeMask (~(UInt32)(kNormalizeStepMin - 1))
     15 #define kMaxHistorySize ((UInt32)7 << 29)
     16 
     17 #define kStartMaxLen 3
     18 
     19 static void LzInWindow_Free(CMatchFinder *p, ISzAllocPtr alloc)
     20 {
     21  if (!p->directInput)
     22  {
     23    ISzAlloc_Free(alloc, p->bufferBase);
     24    p->bufferBase = NULL;
     25  }
     26 }
     27 
     28 /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
     29 
     30 static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAllocPtr alloc)
     31 {
     32  UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
     33  if (p->directInput)
     34  {
     35    p->blockSize = blockSize;
     36    return 1;
     37  }
     38  if (!p->bufferBase || p->blockSize != blockSize)
     39  {
     40    LzInWindow_Free(p, alloc);
     41    p->blockSize = blockSize;
     42    p->bufferBase = (Byte *)ISzAlloc_Alloc(alloc, (size_t)blockSize);
     43  }
     44  return (p->bufferBase != NULL);
     45 }
     46 
     47 Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
     48 
     49 UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
     50 
     51 void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
     52 {
     53  p->posLimit -= subValue;
     54  p->pos -= subValue;
     55  p->streamPos -= subValue;
     56 }
     57 
     58 static void MatchFinder_ReadBlock(CMatchFinder *p)
     59 {
     60  if (p->streamEndWasReached || p->result != SZ_OK)
     61    return;
     62 
     63  /* We use (p->streamPos - p->pos) value. (p->streamPos < p->pos) is allowed. */
     64 
     65  if (p->directInput)
     66  {
     67    UInt32 curSize = 0xFFFFFFFF - (p->streamPos - p->pos);
     68    if (curSize > p->directInputRem)
     69      curSize = (UInt32)p->directInputRem;
     70    p->directInputRem -= curSize;
     71    p->streamPos += curSize;
     72    if (p->directInputRem == 0)
     73      p->streamEndWasReached = 1;
     74    return;
     75  }
     76  
     77  for (;;)
     78  {
     79    Byte *dest = p->buffer + (p->streamPos - p->pos);
     80    size_t size = (p->bufferBase + p->blockSize - dest);
     81    if (size == 0)
     82      return;
     83 
     84    p->result = ISeqInStream_Read(p->stream, dest, &size);
     85    if (p->result != SZ_OK)
     86      return;
     87    if (size == 0)
     88    {
     89      p->streamEndWasReached = 1;
     90      return;
     91    }
     92    p->streamPos += (UInt32)size;
     93    if (p->streamPos - p->pos > p->keepSizeAfter)
     94      return;
     95  }
     96 }
     97 
     98 void MatchFinder_MoveBlock(CMatchFinder *p)
     99 {
    100  memmove(p->bufferBase,
    101      p->buffer - p->keepSizeBefore,
    102      (size_t)(p->streamPos - p->pos) + p->keepSizeBefore);
    103  p->buffer = p->bufferBase + p->keepSizeBefore;
    104 }
    105 
    106 int MatchFinder_NeedMove(CMatchFinder *p)
    107 {
    108  if (p->directInput)
    109    return 0;
    110  /* if (p->streamEndWasReached) return 0; */
    111  return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
    112 }
    113 
    114 void MatchFinder_ReadIfRequired(CMatchFinder *p)
    115 {
    116  if (p->streamEndWasReached)
    117    return;
    118  if (p->keepSizeAfter >= p->streamPos - p->pos)
    119    MatchFinder_ReadBlock(p);
    120 }
    121 
    122 static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)
    123 {
    124  if (MatchFinder_NeedMove(p))
    125    MatchFinder_MoveBlock(p);
    126  MatchFinder_ReadBlock(p);
    127 }
    128 
    129 static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
    130 {
    131  p->cutValue = 32;
    132  p->btMode = 1;
    133  p->numHashBytes = 4;
    134  p->bigHash = 0;
    135 }
    136 
    137 #define kCrcPoly 0xEDB88320
    138 
    139 void MatchFinder_Construct(CMatchFinder *p)
    140 {
    141  UInt32 i;
    142  p->bufferBase = NULL;
    143  p->directInput = 0;
    144  p->hash = NULL;
    145  p->expectedDataSize = (UInt64)(Int64)-1;
    146  MatchFinder_SetDefaultSettings(p);
    147 
    148  for (i = 0; i < 256; i++)
    149  {
    150    UInt32 r = i;
    151    unsigned j;
    152    for (j = 0; j < 8; j++)
    153      r = (r >> 1) ^ (kCrcPoly & ((UInt32)0 - (r & 1)));
    154    p->crc[i] = r;
    155  }
    156 }
    157 
    158 static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAllocPtr alloc)
    159 {
    160  ISzAlloc_Free(alloc, p->hash);
    161  p->hash = NULL;
    162 }
    163 
    164 void MatchFinder_Free(CMatchFinder *p, ISzAllocPtr alloc)
    165 {
    166  MatchFinder_FreeThisClassMemory(p, alloc);
    167  LzInWindow_Free(p, alloc);
    168 }
    169 
    170 static CLzRef* AllocRefs(size_t num, ISzAllocPtr alloc)
    171 {
    172  size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
    173  if (sizeInBytes / sizeof(CLzRef) != num)
    174    return NULL;
    175  return (CLzRef *)ISzAlloc_Alloc(alloc, sizeInBytes);
    176 }
    177 
    178 int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
    179    UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
    180    ISzAllocPtr alloc)
    181 {
    182  UInt32 sizeReserv;
    183  
    184  if (historySize > kMaxHistorySize)
    185  {
    186    MatchFinder_Free(p, alloc);
    187    return 0;
    188  }
    189  
    190  sizeReserv = historySize >> 1;
    191       if (historySize >= ((UInt32)3 << 30)) sizeReserv = historySize >> 3;
    192  else if (historySize >= ((UInt32)2 << 30)) sizeReserv = historySize >> 2;
    193  
    194  sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
    195 
    196  p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
    197  p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
    198  
    199  /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
    200  
    201  if (LzInWindow_Create(p, sizeReserv, alloc))
    202  {
    203    UInt32 newCyclicBufferSize = historySize + 1;
    204    UInt32 hs;
    205    p->matchMaxLen = matchMaxLen;
    206    {
    207      p->fixedHashSize = 0;
    208      if (p->numHashBytes == 2)
    209        hs = (1 << 16) - 1;
    210      else
    211      {
    212        hs = historySize;
    213        if (hs > p->expectedDataSize)
    214          hs = (UInt32)p->expectedDataSize;
    215        if (hs != 0)
    216          hs--;
    217        hs |= (hs >> 1);
    218        hs |= (hs >> 2);
    219        hs |= (hs >> 4);
    220        hs |= (hs >> 8);
    221        hs >>= 1;
    222        hs |= 0xFFFF; /* don't change it! It's required for Deflate */
    223        if (hs > (1 << 24))
    224        {
    225          if (p->numHashBytes == 3)
    226            hs = (1 << 24) - 1;
    227          else
    228            hs >>= 1;
    229          /* if (bigHash) mode, GetHeads4b() in LzFindMt.c needs (hs >= ((1 << 24) - 1))) */
    230        }
    231      }
    232      p->hashMask = hs;
    233      hs++;
    234      if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
    235      if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
    236      if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
    237      hs += p->fixedHashSize;
    238    }
    239 
    240    {
    241      size_t newSize;
    242      size_t numSons;
    243      p->historySize = historySize;
    244      p->hashSizeSum = hs;
    245      p->cyclicBufferSize = newCyclicBufferSize;
    246      
    247      numSons = newCyclicBufferSize;
    248      if (p->btMode)
    249        numSons <<= 1;
    250      newSize = hs + numSons;
    251 
    252      if (p->hash && p->numRefs == newSize)
    253        return 1;
    254      
    255      MatchFinder_FreeThisClassMemory(p, alloc);
    256      p->numRefs = newSize;
    257      p->hash = AllocRefs(newSize, alloc);
    258      
    259      if (p->hash)
    260      {
    261        p->son = p->hash + p->hashSizeSum;
    262        return 1;
    263      }
    264    }
    265  }
    266 
    267  MatchFinder_Free(p, alloc);
    268  return 0;
    269 }
    270 
    271 static void MatchFinder_SetLimits(CMatchFinder *p)
    272 {
    273  UInt32 limit = kMaxValForNormalize - p->pos;
    274  UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
    275  
    276  if (limit2 < limit)
    277    limit = limit2;
    278  limit2 = p->streamPos - p->pos;
    279  
    280  if (limit2 <= p->keepSizeAfter)
    281  {
    282    if (limit2 > 0)
    283      limit2 = 1;
    284  }
    285  else
    286    limit2 -= p->keepSizeAfter;
    287  
    288  if (limit2 < limit)
    289    limit = limit2;
    290  
    291  {
    292    UInt32 lenLimit = p->streamPos - p->pos;
    293    if (lenLimit > p->matchMaxLen)
    294      lenLimit = p->matchMaxLen;
    295    p->lenLimit = lenLimit;
    296  }
    297  p->posLimit = p->pos + limit;
    298 }
    299 
    300 
    301 void MatchFinder_Init_LowHash(CMatchFinder *p)
    302 {
    303  size_t i;
    304  CLzRef *items = p->hash;
    305  size_t numItems = p->fixedHashSize;
    306  for (i = 0; i < numItems; i++)
    307    items[i] = kEmptyHashValue;
    308 }
    309 
    310 
    311 void MatchFinder_Init_HighHash(CMatchFinder *p)
    312 {
    313  size_t i;
    314  CLzRef *items = p->hash + p->fixedHashSize;
    315  size_t numItems = (size_t)p->hashMask + 1;
    316  for (i = 0; i < numItems; i++)
    317    items[i] = kEmptyHashValue;
    318 }
    319 
    320 
    321 void MatchFinder_Init_3(CMatchFinder *p, int readData)
    322 {
    323  p->cyclicBufferPos = 0;
    324  p->buffer = p->bufferBase;
    325  p->pos =
    326  p->streamPos = p->cyclicBufferSize;
    327  p->result = SZ_OK;
    328  p->streamEndWasReached = 0;
    329  
    330  if (readData)
    331    MatchFinder_ReadBlock(p);
    332  
    333  MatchFinder_SetLimits(p);
    334 }
    335 
    336 
    337 void MatchFinder_Init(CMatchFinder *p)
    338 {
    339  MatchFinder_Init_HighHash(p);
    340  MatchFinder_Init_LowHash(p);
    341  MatchFinder_Init_3(p, True);
    342 }
    343 
    344  
    345 static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
    346 {
    347  return (p->pos - p->historySize - 1) & kNormalizeMask;
    348 }
    349 
    350 void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, size_t numItems)
    351 {
    352  size_t i;
    353  for (i = 0; i < numItems; i++)
    354  {
    355    UInt32 value = items[i];
    356    if (value <= subValue)
    357      value = kEmptyHashValue;
    358    else
    359      value -= subValue;
    360    items[i] = value;
    361  }
    362 }
    363 
    364 static void MatchFinder_Normalize(CMatchFinder *p)
    365 {
    366  UInt32 subValue = MatchFinder_GetSubValue(p);
    367  MatchFinder_Normalize3(subValue, p->hash, p->numRefs);
    368  MatchFinder_ReduceOffsets(p, subValue);
    369 }
    370 
    371 static void MatchFinder_CheckLimits(CMatchFinder *p)
    372 {
    373  if (p->pos == kMaxValForNormalize)
    374    MatchFinder_Normalize(p);
    375  if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
    376    MatchFinder_CheckAndMoveAndRead(p);
    377  if (p->cyclicBufferPos == p->cyclicBufferSize)
    378    p->cyclicBufferPos = 0;
    379  MatchFinder_SetLimits(p);
    380 }
    381 
    382 static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
    383    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
    384    UInt32 *distances, UInt32 maxLen)
    385 {
    386  son[_cyclicBufferPos] = curMatch;
    387  for (;;)
    388  {
    389    UInt32 delta = pos - curMatch;
    390    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
    391      return distances;
    392    {
    393      const Byte *pb = cur - delta;
    394      curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
    395      if (pb[maxLen] == cur[maxLen] && *pb == *cur)
    396      {
    397        UInt32 len = 0;
    398        while (++len != lenLimit)
    399          if (pb[len] != cur[len])
    400            break;
    401        if (maxLen < len)
    402        {
    403          *distances++ = maxLen = len;
    404          *distances++ = delta - 1;
    405          if (len == lenLimit)
    406            return distances;
    407        }
    408      }
    409    }
    410  }
    411 }
    412 
    413 UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
    414    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
    415    UInt32 *distances, UInt32 maxLen)
    416 {
    417  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
    418  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
    419  UInt32 len0 = 0, len1 = 0;
    420  for (;;)
    421  {
    422    UInt32 delta = pos - curMatch;
    423    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
    424    {
    425      *ptr0 = *ptr1 = kEmptyHashValue;
    426      return distances;
    427    }
    428    {
    429      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
    430      const Byte *pb = cur - delta;
    431      UInt32 len = (len0 < len1 ? len0 : len1);
    432      if (pb[len] == cur[len])
    433      {
    434        if (++len != lenLimit && pb[len] == cur[len])
    435          while (++len != lenLimit)
    436            if (pb[len] != cur[len])
    437              break;
    438        if (maxLen < len)
    439        {
    440          *distances++ = maxLen = len;
    441          *distances++ = delta - 1;
    442          if (len == lenLimit)
    443          {
    444            *ptr1 = pair[0];
    445            *ptr0 = pair[1];
    446            return distances;
    447          }
    448        }
    449      }
    450      if (pb[len] < cur[len])
    451      {
    452        *ptr1 = curMatch;
    453        ptr1 = pair + 1;
    454        curMatch = *ptr1;
    455        len1 = len;
    456      }
    457      else
    458      {
    459        *ptr0 = curMatch;
    460        ptr0 = pair;
    461        curMatch = *ptr0;
    462        len0 = len;
    463      }
    464    }
    465  }
    466 }
    467 
    468 static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
    469    UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
    470 {
    471  CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
    472  CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
    473  UInt32 len0 = 0, len1 = 0;
    474  for (;;)
    475  {
    476    UInt32 delta = pos - curMatch;
    477    if (cutValue-- == 0 || delta >= _cyclicBufferSize)
    478    {
    479      *ptr0 = *ptr1 = kEmptyHashValue;
    480      return;
    481    }
    482    {
    483      CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
    484      const Byte *pb = cur - delta;
    485      UInt32 len = (len0 < len1 ? len0 : len1);
    486      if (pb[len] == cur[len])
    487      {
    488        while (++len != lenLimit)
    489          if (pb[len] != cur[len])
    490            break;
    491        {
    492          if (len == lenLimit)
    493          {
    494            *ptr1 = pair[0];
    495            *ptr0 = pair[1];
    496            return;
    497          }
    498        }
    499      }
    500      if (pb[len] < cur[len])
    501      {
    502        *ptr1 = curMatch;
    503        ptr1 = pair + 1;
    504        curMatch = *ptr1;
    505        len1 = len;
    506      }
    507      else
    508      {
    509        *ptr0 = curMatch;
    510        ptr0 = pair;
    511        curMatch = *ptr0;
    512        len0 = len;
    513      }
    514    }
    515  }
    516 }
    517 
    518 #define MOVE_POS \
    519  ++p->cyclicBufferPos; \
    520  p->buffer++; \
    521  if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
    522 
    523 #define MOVE_POS_RET MOVE_POS return offset;
    524 
    525 static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
    526 
    527 #define GET_MATCHES_HEADER2(minLen, ret_op) \
    528  UInt32 lenLimit; UInt32 hv; const Byte *cur; UInt32 curMatch; \
    529  lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
    530  cur = p->buffer;
    531 
    532 #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
    533 #define SKIP_HEADER(minLen)        GET_MATCHES_HEADER2(minLen, continue)
    534 
    535 #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
    536 
    537 #define GET_MATCHES_FOOTER(offset, maxLen) \
    538  offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
    539  distances + offset, maxLen) - distances); MOVE_POS_RET;
    540 
    541 #define SKIP_FOOTER \
    542  SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
    543 
    544 #define UPDATE_maxLen { \
    545    ptrdiff_t diff = (ptrdiff_t)0 - d2; \
    546    const Byte *c = cur + maxLen; \
    547    const Byte *lim = cur + lenLimit; \
    548    for (; c != lim; c++) if (*(c + diff) != *c) break; \
    549    maxLen = (UInt32)(c - cur); }
    550 
    551 static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
    552 {
    553  UInt32 offset;
    554  GET_MATCHES_HEADER(2)
    555  HASH2_CALC;
    556  curMatch = p->hash[hv];
    557  p->hash[hv] = p->pos;
    558  offset = 0;
    559  GET_MATCHES_FOOTER(offset, 1)
    560 }
    561 
    562 UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
    563 {
    564  UInt32 offset;
    565  GET_MATCHES_HEADER(3)
    566  HASH_ZIP_CALC;
    567  curMatch = p->hash[hv];
    568  p->hash[hv] = p->pos;
    569  offset = 0;
    570  GET_MATCHES_FOOTER(offset, 2)
    571 }
    572 
    573 static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
    574 {
    575  UInt32 h2, d2, maxLen, offset, pos;
    576  UInt32 *hash;
    577  GET_MATCHES_HEADER(3)
    578 
    579  HASH3_CALC;
    580 
    581  hash = p->hash;
    582  pos = p->pos;
    583 
    584  d2 = pos - hash[h2];
    585 
    586  curMatch = (hash + kFix3HashSize)[hv];
    587  
    588  hash[h2] = pos;
    589  (hash + kFix3HashSize)[hv] = pos;
    590 
    591  maxLen = 2;
    592  offset = 0;
    593 
    594  if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
    595  {
    596    UPDATE_maxLen
    597    distances[0] = maxLen;
    598    distances[1] = d2 - 1;
    599    offset = 2;
    600    if (maxLen == lenLimit)
    601    {
    602      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
    603      MOVE_POS_RET;
    604    }
    605  }
    606  
    607  GET_MATCHES_FOOTER(offset, maxLen)
    608 }
    609 
    610 static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
    611 {
    612  UInt32 h2, h3, d2, d3, maxLen, offset, pos;
    613  UInt32 *hash;
    614  GET_MATCHES_HEADER(4)
    615 
    616  HASH4_CALC;
    617 
    618  hash = p->hash;
    619  pos = p->pos;
    620 
    621  d2 = pos - hash[                h2];
    622  d3 = pos - (hash + kFix3HashSize)[h3];
    623 
    624  curMatch = (hash + kFix4HashSize)[hv];
    625 
    626  hash[                h2] = pos;
    627  (hash + kFix3HashSize)[h3] = pos;
    628  (hash + kFix4HashSize)[hv] = pos;
    629 
    630  maxLen = 0;
    631  offset = 0;
    632  
    633  if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
    634  {
    635    distances[0] = maxLen = 2;
    636    distances[1] = d2 - 1;
    637    offset = 2;
    638  }
    639  
    640  if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
    641  {
    642    maxLen = 3;
    643    distances[(size_t)offset + 1] = d3 - 1;
    644    offset += 2;
    645    d2 = d3;
    646  }
    647  
    648  if (offset != 0)
    649  {
    650    UPDATE_maxLen
    651    distances[(size_t)offset - 2] = maxLen;
    652    if (maxLen == lenLimit)
    653    {
    654      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
    655      MOVE_POS_RET;
    656    }
    657  }
    658  
    659  if (maxLen < 3)
    660    maxLen = 3;
    661  
    662  GET_MATCHES_FOOTER(offset, maxLen)
    663 }
    664 
    665 /*
    666 static UInt32 Bt5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
    667 {
    668  UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos;
    669  UInt32 *hash;
    670  GET_MATCHES_HEADER(5)
    671 
    672  HASH5_CALC;
    673 
    674  hash = p->hash;
    675  pos = p->pos;
    676 
    677  d2 = pos - hash[                h2];
    678  d3 = pos - (hash + kFix3HashSize)[h3];
    679  d4 = pos - (hash + kFix4HashSize)[h4];
    680 
    681  curMatch = (hash + kFix5HashSize)[hv];
    682 
    683  hash[                h2] = pos;
    684  (hash + kFix3HashSize)[h3] = pos;
    685  (hash + kFix4HashSize)[h4] = pos;
    686  (hash + kFix5HashSize)[hv] = pos;
    687 
    688  maxLen = 0;
    689  offset = 0;
    690 
    691  if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
    692  {
    693    distances[0] = maxLen = 2;
    694    distances[1] = d2 - 1;
    695    offset = 2;
    696    if (*(cur - d2 + 2) == cur[2])
    697      distances[0] = maxLen = 3;
    698    else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
    699    {
    700      distances[2] = maxLen = 3;
    701      distances[3] = d3 - 1;
    702      offset = 4;
    703      d2 = d3;
    704    }
    705  }
    706  else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
    707  {
    708    distances[0] = maxLen = 3;
    709    distances[1] = d3 - 1;
    710    offset = 2;
    711    d2 = d3;
    712  }
    713  
    714  if (d2 != d4 && d4 < p->cyclicBufferSize
    715      && *(cur - d4) == *cur
    716      && *(cur - d4 + 3) == *(cur + 3))
    717  {
    718    maxLen = 4;
    719    distances[(size_t)offset + 1] = d4 - 1;
    720    offset += 2;
    721    d2 = d4;
    722  }
    723  
    724  if (offset != 0)
    725  {
    726    UPDATE_maxLen
    727    distances[(size_t)offset - 2] = maxLen;
    728    if (maxLen == lenLimit)
    729    {
    730      SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
    731      MOVE_POS_RET;
    732    }
    733  }
    734 
    735  if (maxLen < 4)
    736    maxLen = 4;
    737  
    738  GET_MATCHES_FOOTER(offset, maxLen)
    739 }
    740 */
    741 
    742 static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
    743 {
    744  UInt32 h2, h3, d2, d3, maxLen, offset, pos;
    745  UInt32 *hash;
    746  GET_MATCHES_HEADER(4)
    747 
    748  HASH4_CALC;
    749 
    750  hash = p->hash;
    751  pos = p->pos;
    752  
    753  d2 = pos - hash[                h2];
    754  d3 = pos - (hash + kFix3HashSize)[h3];
    755  
    756  curMatch = (hash + kFix4HashSize)[hv];
    757 
    758  hash[                h2] = pos;
    759  (hash + kFix3HashSize)[h3] = pos;
    760  (hash + kFix4HashSize)[hv] = pos;
    761 
    762  maxLen = 0;
    763  offset = 0;
    764 
    765  if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
    766  {
    767    distances[0] = maxLen = 2;
    768    distances[1] = d2 - 1;
    769    offset = 2;
    770  }
    771  
    772  if (d2 != d3 && d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
    773  {
    774    maxLen = 3;
    775    distances[(size_t)offset + 1] = d3 - 1;
    776    offset += 2;
    777    d2 = d3;
    778  }
    779  
    780  if (offset != 0)
    781  {
    782    UPDATE_maxLen
    783    distances[(size_t)offset - 2] = maxLen;
    784    if (maxLen == lenLimit)
    785    {
    786      p->son[p->cyclicBufferPos] = curMatch;
    787      MOVE_POS_RET;
    788    }
    789  }
    790  
    791  if (maxLen < 3)
    792    maxLen = 3;
    793 
    794  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
    795      distances + offset, maxLen) - (distances));
    796  MOVE_POS_RET
    797 }
    798 
    799 /*
    800 static UInt32 Hc5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
    801 {
    802  UInt32 h2, h3, h4, d2, d3, d4, maxLen, offset, pos
    803  UInt32 *hash;
    804  GET_MATCHES_HEADER(5)
    805 
    806  HASH5_CALC;
    807 
    808  hash = p->hash;
    809  pos = p->pos;
    810  
    811  d2 = pos - hash[                h2];
    812  d3 = pos - (hash + kFix3HashSize)[h3];
    813  d4 = pos - (hash + kFix4HashSize)[h4];
    814 
    815  curMatch = (hash + kFix5HashSize)[hv];
    816 
    817  hash[                h2] = pos;
    818  (hash + kFix3HashSize)[h3] = pos;
    819  (hash + kFix4HashSize)[h4] = pos;
    820  (hash + kFix5HashSize)[hv] = pos;
    821 
    822  maxLen = 0;
    823  offset = 0;
    824 
    825  if (d2 < p->cyclicBufferSize && *(cur - d2) == *cur)
    826  {
    827    distances[0] = maxLen = 2;
    828    distances[1] = d2 - 1;
    829    offset = 2;
    830    if (*(cur - d2 + 2) == cur[2])
    831      distances[0] = maxLen = 3;
    832    else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
    833    {
    834      distances[2] = maxLen = 3;
    835      distances[3] = d3 - 1;
    836      offset = 4;
    837      d2 = d3;
    838    }
    839  }
    840  else if (d3 < p->cyclicBufferSize && *(cur - d3) == *cur)
    841  {
    842    distances[0] = maxLen = 3;
    843    distances[1] = d3 - 1;
    844    offset = 2;
    845    d2 = d3;
    846  }
    847  
    848  if (d2 != d4 && d4 < p->cyclicBufferSize
    849      && *(cur - d4) == *cur
    850      && *(cur - d4 + 3) == *(cur + 3))
    851  {
    852    maxLen = 4;
    853    distances[(size_t)offset + 1] = d4 - 1;
    854    offset += 2;
    855    d2 = d4;
    856  }
    857  
    858  if (offset != 0)
    859  {
    860    UPDATE_maxLen
    861    distances[(size_t)offset - 2] = maxLen;
    862    if (maxLen == lenLimit)
    863    {
    864      p->son[p->cyclicBufferPos] = curMatch;
    865      MOVE_POS_RET;
    866    }
    867  }
    868  
    869  if (maxLen < 4)
    870    maxLen = 4;
    871 
    872  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
    873      distances + offset, maxLen) - (distances));
    874  MOVE_POS_RET
    875 }
    876 */
    877 
    878 UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
    879 {
    880  UInt32 offset;
    881  GET_MATCHES_HEADER(3)
    882  HASH_ZIP_CALC;
    883  curMatch = p->hash[hv];
    884  p->hash[hv] = p->pos;
    885  offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
    886      distances, 2) - (distances));
    887  MOVE_POS_RET
    888 }
    889 
    890 static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
    891 {
    892  do
    893  {
    894    SKIP_HEADER(2)
    895    HASH2_CALC;
    896    curMatch = p->hash[hv];
    897    p->hash[hv] = p->pos;
    898    SKIP_FOOTER
    899  }
    900  while (--num != 0);
    901 }
    902 
    903 void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
    904 {
    905  do
    906  {
    907    SKIP_HEADER(3)
    908    HASH_ZIP_CALC;
    909    curMatch = p->hash[hv];
    910    p->hash[hv] = p->pos;
    911    SKIP_FOOTER
    912  }
    913  while (--num != 0);
    914 }
    915 
    916 static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
    917 {
    918  do
    919  {
    920    UInt32 h2;
    921    UInt32 *hash;
    922    SKIP_HEADER(3)
    923    HASH3_CALC;
    924    hash = p->hash;
    925    curMatch = (hash + kFix3HashSize)[hv];
    926    hash[h2] =
    927    (hash + kFix3HashSize)[hv] = p->pos;
    928    SKIP_FOOTER
    929  }
    930  while (--num != 0);
    931 }
    932 
    933 static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
    934 {
    935  do
    936  {
    937    UInt32 h2, h3;
    938    UInt32 *hash;
    939    SKIP_HEADER(4)
    940    HASH4_CALC;
    941    hash = p->hash;
    942    curMatch = (hash + kFix4HashSize)[hv];
    943    hash[                h2] =
    944    (hash + kFix3HashSize)[h3] =
    945    (hash + kFix4HashSize)[hv] = p->pos;
    946    SKIP_FOOTER
    947  }
    948  while (--num != 0);
    949 }
    950 
    951 /*
    952 static void Bt5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
    953 {
    954  do
    955  {
    956    UInt32 h2, h3, h4;
    957    UInt32 *hash;
    958    SKIP_HEADER(5)
    959    HASH5_CALC;
    960    hash = p->hash;
    961    curMatch = (hash + kFix5HashSize)[hv];
    962    hash[                h2] =
    963    (hash + kFix3HashSize)[h3] =
    964    (hash + kFix4HashSize)[h4] =
    965    (hash + kFix5HashSize)[hv] = p->pos;
    966    SKIP_FOOTER
    967  }
    968  while (--num != 0);
    969 }
    970 */
    971 
    972 static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
    973 {
    974  do
    975  {
    976    UInt32 h2, h3;
    977    UInt32 *hash;
    978    SKIP_HEADER(4)
    979    HASH4_CALC;
    980    hash = p->hash;
    981    curMatch = (hash + kFix4HashSize)[hv];
    982    hash[                h2] =
    983    (hash + kFix3HashSize)[h3] =
    984    (hash + kFix4HashSize)[hv] = p->pos;
    985    p->son[p->cyclicBufferPos] = curMatch;
    986    MOVE_POS
    987  }
    988  while (--num != 0);
    989 }
    990 
    991 /*
    992 static void Hc5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
    993 {
    994  do
    995  {
    996    UInt32 h2, h3, h4;
    997    UInt32 *hash;
    998    SKIP_HEADER(5)
    999    HASH5_CALC;
   1000    hash = p->hash;
   1001    curMatch = hash + kFix5HashSize)[hv];
   1002    hash[                h2] =
   1003    (hash + kFix3HashSize)[h3] =
   1004    (hash + kFix4HashSize)[h4] =
   1005    (hash + kFix5HashSize)[hv] = p->pos;
   1006    p->son[p->cyclicBufferPos] = curMatch;
   1007    MOVE_POS
   1008  }
   1009  while (--num != 0);
   1010 }
   1011 */
   1012 
   1013 void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
   1014 {
   1015  do
   1016  {
   1017    SKIP_HEADER(3)
   1018    HASH_ZIP_CALC;
   1019    curMatch = p->hash[hv];
   1020    p->hash[hv] = p->pos;
   1021    p->son[p->cyclicBufferPos] = curMatch;
   1022    MOVE_POS
   1023  }
   1024  while (--num != 0);
   1025 }
   1026 
   1027 void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
   1028 {
   1029  vTable->Init = (Mf_Init_Func)MatchFinder_Init;
   1030  vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
   1031  vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
   1032  if (!p->btMode)
   1033  {
   1034    /* if (p->numHashBytes <= 4) */
   1035    {
   1036      vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
   1037      vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
   1038    }
   1039    /*
   1040    else
   1041    {
   1042      vTable->GetMatches = (Mf_GetMatches_Func)Hc5_MatchFinder_GetMatches;
   1043      vTable->Skip = (Mf_Skip_Func)Hc5_MatchFinder_Skip;
   1044    }
   1045    */
   1046  }
   1047  else if (p->numHashBytes == 2)
   1048  {
   1049    vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
   1050    vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
   1051  }
   1052  else if (p->numHashBytes == 3)
   1053  {
   1054    vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
   1055    vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
   1056  }
   1057  else /* if (p->numHashBytes == 4) */
   1058  {
   1059    vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
   1060    vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
   1061  }
   1062  /*
   1063  else
   1064  {
   1065    vTable->GetMatches = (Mf_GetMatches_Func)Bt5_MatchFinder_GetMatches;
   1066    vTable->Skip = (Mf_Skip_Func)Bt5_MatchFinder_Skip;
   1067  }
   1068  */
   1069 }
	tor-browser The Tor Browser
	git clone https://git.dasho.dev/tor-browser.git
	Log \| Files \| Refs \| README \| LICENSE