payloads/bayou/util/pbuilder/lzma/C/7zip/Compress/LZ/BinTree/BinTreeMain.h

   1 // BinTreeMain.h
   2
   3 #include "../../../../Common/Defs.h"
   4 #include "../../../../Common/CRC.h"
   5 #include "../../../../Common/Alloc.h"
   6
   7 #include "BinTree.h"
   8
   9 // #include <xmmintrin.h>
  10 // It's for prefetch
  11 // But prefetch doesn't give big gain in K8.
  12
  13 namespace BT_NAMESPACE {
  14
  15 #ifdef HASH_ARRAY_2
  16   static const UInt32 kHash2Size = 1 << 10;
  17   #define kNumHashDirectBytes 0
  18   #ifdef HASH_ARRAY_3
  19     static const UInt32 kNumHashBytes = 4;
  20     static const UInt32 kHash3Size = 1 << 16;
  21   #else
  22     static const UInt32 kNumHashBytes = 3;
  23   #endif
  24   static const UInt32 kHashSize = 0;
  25   static const UInt32 kMinMatchCheck = kNumHashBytes;
  26   static const UInt32 kStartMaxLen = 1;
  27 #else
  28   #ifdef HASH_ZIP
  29     #define kNumHashDirectBytes 0
  30     static const UInt32 kNumHashBytes = 3;
  31     static const UInt32 kHashSize = 1 << 16;
  32     static const UInt32 kMinMatchCheck = kNumHashBytes;
  33     static const UInt32 kStartMaxLen = 1;
  34   #else
  35     #define kNumHashDirectBytes 2
  36     static const UInt32 kNumHashBytes = 2;
  37     static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);
  38     static const UInt32 kMinMatchCheck = kNumHashBytes + 1;
  39     static const UInt32 kStartMaxLen = 1;
  40   #endif
  41 #endif
  42
  43 #ifdef HASH_ARRAY_2
  44 #ifdef HASH_ARRAY_3
  45 static const UInt32 kHash3Offset = kHash2Size;
  46 #endif
  47 #endif
  48
  49 static const UInt32 kFixHashSize = 0
  50     #ifdef HASH_ARRAY_2
  51     + kHash2Size
  52     #ifdef HASH_ARRAY_3
  53     + kHash3Size
  54     #endif
  55     #endif
  56     ;
  57
  58 CMatchFinder::CMatchFinder():
  59   _hash(0)
  60 {
  61 }
  62
  63 void CMatchFinder::FreeThisClassMemory()
  64 {
  65   BigFree(_hash);
  66   _hash = 0;
  67 }
  68
  69 void CMatchFinder::FreeMemory()
  70 {
  71   FreeThisClassMemory();
  72   CLZInWindow::Free();
  73 }
  74
  75 CMatchFinder::~CMatchFinder()
  76 {
  77   FreeMemory();
  78 }
  79
  80 STDMETHODIMP CMatchFinder::Create(UInt32 historySize, UInt32 keepAddBufferBefore,
  81     UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
  82 {
  83   if (historySize > kMaxValForNormalize - 256)
  84   {
  85     FreeMemory();
  86     return E_INVALIDARG;
  87   }
  88   _cutValue =
  89   #ifdef _HASH_CHAIN
  90     8 + (matchMaxLen >> 2);
  91   #else
  92     16 + (matchMaxLen >> 1);
  93   #endif
  94   UInt32 sizeReserv = (historySize + keepAddBufferBefore +
  95       matchMaxLen + keepAddBufferAfter) / 2 + 256;
  96   if (CLZInWindow::Create(historySize + keepAddBufferBefore,
  97       matchMaxLen + keepAddBufferAfter, sizeReserv))
  98   {
  99     _matchMaxLen = matchMaxLen;
 100     UInt32 newCyclicBufferSize = historySize + 1;
 101     if (_hash != 0 && newCyclicBufferSize == _cyclicBufferSize)
 102       return S_OK;
 103     FreeThisClassMemory();
 104     _cyclicBufferSize = newCyclicBufferSize; // don't change it
 105
 106     UInt32 hs = kHashSize;
 107
 108     #ifdef HASH_ARRAY_2
 109     hs = historySize - 1;
 110     hs |= (hs >> 1);
 111     hs |= (hs >> 2);
 112     hs |= (hs >> 4);
 113     hs |= (hs >> 8);
 114     hs >>= 1;
 115     hs |= 0xFFFF;
 116     if (hs > (1 << 24))
 117     {
 118       #ifdef HASH_ARRAY_3
 119       hs >>= 1;
 120       #else
 121       hs = (1 << 24) - 1;
 122       #endif
 123     }
 124     _hashMask = hs;
 125     hs++;
 126     #endif
 127     _hashSizeSum = hs + kFixHashSize;
 128     UInt32 numItems = _hashSizeSum + _cyclicBufferSize
 129     #ifndef _HASH_CHAIN
 130      * 2
 131     #endif
 132     ;
 133     size_t sizeInBytes = (size_t)numItems * sizeof(CIndex);
 134     if (sizeInBytes / sizeof(CIndex) != numItems)
 135       return E_OUTOFMEMORY;
 136     _hash = (CIndex *)BigAlloc(sizeInBytes);
 137     _son = _hash + _hashSizeSum;
 138     if (_hash != 0)
 139       return S_OK;
 140   }
 141   FreeMemory();
 142   return E_OUTOFMEMORY;
 143 }
 144
 145 static const UInt32 kEmptyHashValue = 0;
 146
 147 STDMETHODIMP CMatchFinder::SetStream(ISequentialInStream *stream)
 148 {
 149   CLZInWindow::SetStream(stream);
 150   return S_OK;
 151 }
 152
 153 STDMETHODIMP CMatchFinder::Init()
 154 {
 155   RINOK(CLZInWindow::Init());
 156   for(UInt32 i = 0; i < _hashSizeSum; i++)
 157     _hash[i] = kEmptyHashValue;
 158   _cyclicBufferPos = 0;
 159   ReduceOffsets(-1);
 160   return S_OK;
 161 }
 162
 163 STDMETHODIMP_(void) CMatchFinder::ReleaseStream()
 164 {
 165   // ReleaseStream();
 166 }
 167
 168 #ifdef HASH_ARRAY_2
 169 #ifdef HASH_ARRAY_3
 170
 171 #define HASH_CALC { \
 172   UInt32 temp = CCRC::Table[cur[0]] ^ cur[1]; \
 173   hash2Value = temp & (kHash2Size - 1); \
 174   hash3Value = (temp ^ (UInt32(cur[2]) << 8)) & (kHash3Size - 1); \
 175   hashValue = (temp ^ (UInt32(cur[2]) << 8) ^ (CCRC::Table[cur[3]] << 5)) & _hashMask; }
 176
 177 #else // no HASH_ARRAY_3
 178 #define HASH_CALC { \
 179   UInt32 temp = CCRC::Table[cur[0]] ^ cur[1]; \
 180   hash2Value = temp & (kHash2Size - 1); \
 181   hashValue = (temp ^ (UInt32(cur[2]) << 8)) & _hashMask; }
 182 #endif // HASH_ARRAY_3
 183 #else // no HASH_ARRAY_2
 184 #ifdef HASH_ZIP
 185 inline UInt32 Hash(const Byte *pointer)
 186 {
 187   return ((UInt32(pointer[0]) << 8) ^ CCRC::Table[pointer[1]] ^ pointer[2]) & (kHashSize - 1);
 188 }
 189 #else // no HASH_ZIP
 190 inline UInt32 Hash(const Byte *pointer)
 191 {
 192   return pointer[0] ^ (UInt32(pointer[1]) << 8);
 193 }
 194 #endif // HASH_ZIP
 195 #endif // HASH_ARRAY_2
 196
 197 STDMETHODIMP CMatchFinder::GetMatches(UInt32 *distances)
 198 {
 199   UInt32 lenLimit;
 200   if (_pos + _matchMaxLen <= _streamPos)
 201     lenLimit = _matchMaxLen;
 202   else
 203   {
 204     lenLimit = _streamPos - _pos;
 205     if(lenLimit < kMinMatchCheck)
 206     {
 207       distances[0] = 0;
 208       return MovePos();
 209     }
 210   }
 211
 212   int offset = 1;
 213
 214   UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
 215   const Byte *cur = _buffer + _pos;
 216
 217   UInt32 maxLen = kStartMaxLen; // to avoid items for len < hashSize;
 218
 219   #ifdef HASH_ARRAY_2
 220   UInt32 hash2Value;
 221   #ifdef HASH_ARRAY_3
 222   UInt32 hash3Value;
 223   #endif
 224   UInt32 hashValue;
 225   HASH_CALC;
 226   #else
 227   UInt32 hashValue = Hash(cur);
 228   #endif
 229
 230   UInt32 curMatch = _hash[kFixHashSize + hashValue];
 231   #ifdef HASH_ARRAY_2
 232   UInt32 curMatch2 = _hash[hash2Value];
 233   #ifdef HASH_ARRAY_3
 234   UInt32 curMatch3 = _hash[kHash3Offset + hash3Value];
 235   #endif
 236   _hash[hash2Value] = _pos;
 237   if(curMatch2 > matchMinPos)
 238     if (_buffer[curMatch2] == cur[0])
 239     {
 240       distances[offset++] = maxLen = 2;
 241       distances[offset++] = _pos - curMatch2 - 1;
 242     }
 243
 244   #ifdef HASH_ARRAY_3
 245   _hash[kHash3Offset + hash3Value] = _pos;
 246   if(curMatch3 > matchMinPos)
 247     if (_buffer[curMatch3] == cur[0])
 248     {
 249       if (curMatch3 == curMatch2)
 250         offset -= 2;
 251       distances[offset++] = maxLen = 3;
 252       distances[offset++] = _pos - curMatch3 - 1;
 253       curMatch2 = curMatch3;
 254     }
 255   #endif
 256   if (offset != 1 && curMatch2 == curMatch)
 257   {
 258     offset -= 2;
 259     maxLen = kStartMaxLen;
 260   }
 261   #endif
 262
 263   _hash[kFixHashSize + hashValue] = _pos;
 264
 265   CIndex *son = _son;
 266
 267   #ifdef _HASH_CHAIN
 268   son[_cyclicBufferPos] = curMatch;
 269   #else
 270   CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1;
 271   CIndex *ptr1 = son + (_cyclicBufferPos << 1);
 272
 273   UInt32 len0, len1;
 274   len0 = len1 = kNumHashDirectBytes;
 275   #endif
 276
 277   #if kNumHashDirectBytes != 0
 278   if(curMatch > matchMinPos)
 279   {
 280     if (_buffer[curMatch + kNumHashDirectBytes] != cur[kNumHashDirectBytes])
 281     {
 282       distances[offset++] = maxLen = kNumHashDirectBytes;
 283       distances[offset++] = _pos - curMatch - 1;
 284     }
 285   }
 286   #endif
 287   UInt32 count = _cutValue;
 288   while(true)
 289   {
 290     if(curMatch <= matchMinPos || count-- == 0)
 291     {
 292       #ifndef _HASH_CHAIN
 293       *ptr0 = *ptr1 = kEmptyHashValue;
 294       #endif
 295       break;
 296     }
 297     UInt32 delta = _pos - curMatch;
 298     UInt32 cyclicPos = (delta <= _cyclicBufferPos) ?
 299         (_cyclicBufferPos - delta):
 300         (_cyclicBufferPos - delta + _cyclicBufferSize);
 301     CIndex *pair = son +
 302     #ifdef _HASH_CHAIN
 303       cyclicPos;
 304     #else
 305       (cyclicPos << 1);
 306     #endif
 307
 308     // _mm_prefetch((const char *)pair, _MM_HINT_T0);
 309
 310     const Byte *pb = _buffer + curMatch;
 311     UInt32 len =
 312     #ifdef _HASH_CHAIN
 313     kNumHashDirectBytes;
 314     if (pb[maxLen] == cur[maxLen])
 315     #else
 316     MyMin(len0, len1);
 317     #endif
 318     if (pb[len] == cur[len])
 319     {
 320       while(++len != lenLimit)
 321         if (pb[len] != cur[len])
 322           break;
 323       if (maxLen < len)
 324       {
 325         distances[offset++] = maxLen = len;
 326         distances[offset++] = delta - 1;
 327         if (len == lenLimit)
 328         {
 329           #ifndef _HASH_CHAIN
 330           *ptr1 = pair[0];
 331           *ptr0 = pair[1];
 332           #endif
 333           break;
 334         }
 335       }
 336     }
 337     #ifdef _HASH_CHAIN
 338     curMatch = *pair;
 339     #else
 340     if (pb[len] < cur[len])
 341     {
 342       *ptr1 = curMatch;
 343       ptr1 = pair + 1;
 344       curMatch = *ptr1;
 345       len1 = len;
 346     }
 347     else
 348     {
 349       *ptr0 = curMatch;
 350       ptr0 = pair;
 351       curMatch = *ptr0;
 352       len0 = len;
 353     }
 354     #endif
 355   }
 356   distances[0] = offset - 1;
 357   if (++_cyclicBufferPos == _cyclicBufferSize)
 358     _cyclicBufferPos = 0;
 359   RINOK(CLZInWindow::MovePos());
 360   if (_pos == kMaxValForNormalize)
 361     Normalize();
 362   return S_OK;
 363 }
 364
 365 STDMETHODIMP CMatchFinder::Skip(UInt32 num)
 366 {
 367   do
 368   {
 369   #ifdef _HASH_CHAIN
 370   if (_streamPos - _pos < kNumHashBytes)
 371   {
 372     RINOK(MovePos());
 373     continue;
 374   }
 375   #else
 376   UInt32 lenLimit;
 377   if (_pos + _matchMaxLen <= _streamPos)
 378     lenLimit = _matchMaxLen;
 379   else
 380   {
 381     lenLimit = _streamPos - _pos;
 382     if(lenLimit < kMinMatchCheck)
 383     {
 384       RINOK(MovePos());
 385       continue;
 386     }
 387   }
 388   UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
 389   #endif
 390   const Byte *cur = _buffer + _pos;
 391
 392   #ifdef HASH_ARRAY_2
 393   UInt32 hash2Value;
 394   #ifdef HASH_ARRAY_3
 395   UInt32 hash3Value;
 396   UInt32 hashValue;
 397   HASH_CALC;
 398   _hash[kHash3Offset + hash3Value] = _pos;
 399   #else
 400   UInt32 hashValue;
 401   HASH_CALC;
 402   #endif
 403   _hash[hash2Value] = _pos;
 404   #else
 405   UInt32 hashValue = Hash(cur);
 406   #endif
 407
 408   UInt32 curMatch = _hash[kFixHashSize + hashValue];
 409   _hash[kFixHashSize + hashValue] = _pos;
 410
 411   #ifdef _HASH_CHAIN
 412   _son[_cyclicBufferPos] = curMatch;
 413   #else
 414   CIndex *son = _son;
 415   CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1;
 416   CIndex *ptr1 = son + (_cyclicBufferPos << 1);
 417
 418   UInt32 len0, len1;
 419   len0 = len1 = kNumHashDirectBytes;
 420   UInt32 count = _cutValue;
 421   while(true)
 422   {
 423     if(curMatch <= matchMinPos || count-- == 0)
 424     {
 425       *ptr0 = *ptr1 = kEmptyHashValue;
 426       break;
 427     }
 428
 429     UInt32 delta = _pos - curMatch;
 430     UInt32 cyclicPos = (delta <= _cyclicBufferPos) ?
 431       (_cyclicBufferPos - delta):
 432       (_cyclicBufferPos - delta + _cyclicBufferSize);
 433     CIndex *pair = son + (cyclicPos << 1);
 434
 435     // _mm_prefetch((const char *)pair, _MM_HINT_T0);
 436
 437     const Byte *pb = _buffer + curMatch;
 438     UInt32 len = MyMin(len0, len1);
 439
 440     if (pb[len] == cur[len])
 441     {
 442       while(++len != lenLimit)
 443         if (pb[len] != cur[len])
 444           break;
 445       if (len == lenLimit)
 446       {
 447         *ptr1 = pair[0];
 448         *ptr0 = pair[1];
 449         break;
 450       }
 451     }
 452     if (pb[len] < cur[len])
 453     {
 454       *ptr1 = curMatch;
 455       ptr1 = pair + 1;
 456       curMatch = *ptr1;
 457       len1 = len;
 458     }
 459     else
 460     {
 461       *ptr0 = curMatch;
 462       ptr0 = pair;
 463       curMatch = *ptr0;
 464       len0 = len;
 465     }
 466   }
 467   #endif
 468   if (++_cyclicBufferPos == _cyclicBufferSize)
 469     _cyclicBufferPos = 0;
 470   RINOK(CLZInWindow::MovePos());
 471   if (_pos == kMaxValForNormalize)
 472     Normalize();
 473   }
 474   while(--num != 0);
 475   return S_OK;
 476 }
 477
 478 void CMatchFinder::Normalize()
 479 {
 480   UInt32 subValue = _pos - _cyclicBufferSize;
 481   CIndex *items = _hash;
 482   UInt32 numItems = (_hashSizeSum + _cyclicBufferSize
 483     #ifndef _HASH_CHAIN
 484      * 2
 485     #endif
 486     );
 487   for (UInt32 i = 0; i < numItems; i++)
 488   {
 489     UInt32 value = items[i];
 490     if (value <= subValue)
 491       value = kEmptyHashValue;
 492     else
 493       value -= subValue;
 494     items[i] = value;
 495   }
 496   ReduceOffsets(subValue);
 497 }
 498
 499 HRESULT CMatchFinder::MovePos()
 500 {
 501   if (++_cyclicBufferPos == _cyclicBufferSize)
 502     _cyclicBufferPos = 0;
 503   RINOK(CLZInWindow::MovePos());
 504   if (_pos == kMaxValForNormalize)
 505     Normalize();
 506   return S_OK;
 507 }
 508
 509 STDMETHODIMP_(Byte) CMatchFinder::GetIndexByte(Int32 index)
 510   { return CLZInWindow::GetIndexByte(index); }
 511
 512 STDMETHODIMP_(UInt32) CMatchFinder::GetMatchLen(Int32 index,
 513     UInt32 back, UInt32 limit)
 514   { return CLZInWindow::GetMatchLen(index, back, limit); }
 515
 516 STDMETHODIMP_(UInt32) CMatchFinder::GetNumAvailableBytes()
 517   { return CLZInWindow::GetNumAvailableBytes(); }
 518
 519 STDMETHODIMP_(const Byte *) CMatchFinder::GetPointerToCurrentPos()
 520   { return CLZInWindow::GetPointerToCurrentPos(); }
 521
 522 STDMETHODIMP_(Int32) CMatchFinder::NeedChangeBufferPos(UInt32 numCheckBytes)
 523   { return CLZInWindow::NeedMove(numCheckBytes) ? 1: 0; }
 524
 525 STDMETHODIMP_(void) CMatchFinder::ChangeBufferPos()
 526   { CLZInWindow::MoveBlock();}
 527
 528 #undef HASH_CALC
 529 #undef kNumHashDirectBytes
 530
 531 }