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

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