release/src-rt-6.x/linux/linux-2.6/scripts/squashfs/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 namespace BT_NAMESPACE {
   8
   9 #ifdef HASH_ARRAY_2
  10   static const UInt32 kHash2Size = 1 << 10;
  11   #ifdef HASH_ARRAY_3
  12     static const UInt32 kNumHashDirectBytes = 0;
  13     static const UInt32 kNumHashBytes = 4;
  14     static const UInt32 kHash3Size = 1 << 18;
  15     #ifdef HASH_BIG
  16     static const UInt32 kHashSize = 1 << 23;
  17     #else
  18     static const UInt32 kHashSize = 1 << 20;
  19     #endif
  20   #else
  21     static const UInt32 kNumHashDirectBytes = 3;
  22     static const UInt32 kNumHashBytes = 3;
  23     static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);
  24   #endif
  25 #else
  26   #ifdef HASH_ZIP
  27     static const UInt32 kNumHashDirectBytes = 0;
  28     static const UInt32 kNumHashBytes = 3;
  29     static const UInt32 kHashSize = 1 << 16;
  30   #else
  31     #define THERE_ARE_DIRECT_HASH_BYTES
  32     static const UInt32 kNumHashDirectBytes = 2;
  33     static const UInt32 kNumHashBytes = 2;
  34     static const UInt32 kHashSize = 1 << (8 * kNumHashBytes);
  35   #endif
  36 #endif
  37
  38 static const UInt32 kHashSizeSum = kHashSize
  39     #ifdef HASH_ARRAY_2
  40     + kHash2Size
  41     #ifdef HASH_ARRAY_3
  42     + kHash3Size
  43     #endif
  44     #endif
  45     ;
  46
  47 #ifdef HASH_ARRAY_2
  48 static const UInt32 kHash2Offset = kHashSize;
  49 #ifdef HASH_ARRAY_3
  50 static const UInt32 kHash3Offset = kHashSize + kHash2Size;
  51 #endif
  52 #endif
  53
  54 CMatchFinderBinTree::CMatchFinderBinTree():
  55   _hash(0),
  56   _cutValue(0xFF)
  57 {
  58 }
  59
  60 void CMatchFinderBinTree::FreeThisClassMemory()
  61 {
  62   BigFree(_hash);
  63   _hash = 0;
  64 }
  65
  66 void CMatchFinderBinTree::FreeMemory()
  67 {
  68   FreeThisClassMemory();
  69   CLZInWindow::Free();
  70 }
  71
  72 CMatchFinderBinTree::~CMatchFinderBinTree()
  73 {
  74   FreeMemory();
  75 }
  76
  77 STDMETHODIMP CMatchFinderBinTree::Create(UInt32 historySize, UInt32 keepAddBufferBefore,
  78     UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
  79 {
  80   UInt32 sizeReserv = (historySize + keepAddBufferBefore +
  81       matchMaxLen + keepAddBufferAfter) / 2 + 256;
  82   if (CLZInWindow::Create(historySize + keepAddBufferBefore,
  83       matchMaxLen + keepAddBufferAfter, sizeReserv))
  84   {
  85     if (historySize + 256 > kMaxValForNormalize)
  86     {
  87       FreeMemory();
  88       return E_INVALIDARG;
  89     }
  90     _matchMaxLen = matchMaxLen;
  91     UInt32 newCyclicBufferSize = historySize + 1;
  92     if (_hash != 0 && newCyclicBufferSize == _cyclicBufferSize)
  93       return S_OK;
  94     FreeThisClassMemory();
  95     _cyclicBufferSize = newCyclicBufferSize; // don't change it
  96     _hash = (CIndex *)BigAlloc((kHashSizeSum + _cyclicBufferSize * 2) * sizeof(CIndex));
  97     if (_hash != 0)
  98       return S_OK;
  99   }
 100   FreeMemory();
 101   return E_OUTOFMEMORY;
 102 }
 103
 104 static const UInt32 kEmptyHashValue = 0;
 105
 106 STDMETHODIMP CMatchFinderBinTree::Init(ISequentialInStream *stream)
 107 {
 108   RINOK(CLZInWindow::Init(stream));
 109   for(UInt32 i = 0; i < kHashSizeSum; i++)
 110     _hash[i] = kEmptyHashValue;
 111   _cyclicBufferPos = 0;
 112   ReduceOffsets(-1);
 113   return S_OK;
 114 }
 115
 116 STDMETHODIMP_(void) CMatchFinderBinTree::ReleaseStream()
 117 {
 118   // ReleaseStream();
 119 }
 120
 121 #ifdef HASH_ARRAY_2
 122 #ifdef HASH_ARRAY_3
 123 inline UInt32 Hash(const Byte *pointer, UInt32 &hash2Value, UInt32 &hash3Value)
 124 {
 125   UInt32 temp = CCRC::Table[pointer[0]] ^ pointer[1];
 126   hash2Value = temp & (kHash2Size - 1);
 127   hash3Value = (temp ^ (UInt32(pointer[2]) << 8)) & (kHash3Size - 1);
 128   return (temp ^ (UInt32(pointer[2]) << 8) ^ (CCRC::Table[pointer[3]] << 5)) &
 129       (kHashSize - 1);
 130 }
 131 #else // no HASH_ARRAY_3
 132 inline UInt32 Hash(const Byte *pointer, UInt32 &hash2Value)
 133 {
 134   hash2Value = (CCRC::Table[pointer[0]] ^ pointer[1]) & (kHash2Size - 1);
 135   return ((UInt32(pointer[0]) << 16)) | ((UInt32(pointer[1]) << 8)) | pointer[2];
 136 }
 137 #endif // HASH_ARRAY_3
 138 #else // no HASH_ARRAY_2
 139 #ifdef HASH_ZIP
 140 inline UInt32 Hash(const Byte *pointer)
 141 {
 142   return ((UInt32(pointer[0]) << 8) ^
 143       CCRC::Table[pointer[1]] ^ pointer[2]) & (kHashSize - 1);
 144 }
 145 #else // no HASH_ZIP
 146 inline UInt32 Hash(const Byte *pointer)
 147 {
 148   return pointer[0] ^ (UInt32(pointer[1]) << 8);
 149 }
 150 #endif // HASH_ZIP
 151 #endif // HASH_ARRAY_2
 152
 153 STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetLongestMatch(UInt32 *distances)
 154 {
 155   UInt32 lenLimit;
 156   if (_pos + _matchMaxLen <= _streamPos)
 157     lenLimit = _matchMaxLen;
 158   else
 159   {
 160     lenLimit = _streamPos - _pos;
 161     if(lenLimit < kNumHashBytes)
 162       return 0;
 163   }
 164
 165   UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
 166   Byte *cur = _buffer + _pos;
 167
 168   UInt32 maxLen = 0;
 169
 170   #ifdef HASH_ARRAY_2
 171   UInt32 hash2Value;
 172   #ifdef HASH_ARRAY_3
 173   UInt32 hash3Value;
 174   UInt32 hashValue = Hash(cur, hash2Value, hash3Value);
 175   #else
 176   UInt32 hashValue = Hash(cur, hash2Value);
 177   #endif
 178   #else
 179   UInt32 hashValue = Hash(cur);
 180   #endif
 181
 182   UInt32 curMatch = _hash[hashValue];
 183   #ifdef HASH_ARRAY_2
 184   UInt32 curMatch2 = _hash[kHash2Offset + hash2Value];
 185   #ifdef HASH_ARRAY_3
 186   UInt32 curMatch3 = _hash[kHash3Offset + hash3Value];
 187   #endif
 188   _hash[kHash2Offset + hash2Value] = _pos;
 189   distances[2] = 0xFFFFFFFF;
 190   if(curMatch2 > matchMinPos)
 191     if (_buffer[curMatch2] == cur[0])
 192     {
 193       distances[2] = _pos - curMatch2 - 1;
 194       maxLen = 2;
 195     }
 196
 197   #ifdef HASH_ARRAY_3
 198   _hash[kHash3Offset + hash3Value] = _pos;
 199   distances[3] = 0xFFFFFFFF;
 200   if(curMatch3 > matchMinPos)
 201     if (_buffer[curMatch3] == cur[0])
 202     {
 203       distances[3] = _pos - curMatch3 - 1;
 204       maxLen = 3;
 205     }
 206   #endif
 207   #endif
 208
 209   _hash[hashValue] = _pos;
 210
 211   CIndex *son = _hash + kHashSizeSum;
 212   CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1;
 213   CIndex *ptr1 = son + (_cyclicBufferPos << 1);
 214
 215   distances[kNumHashBytes] = 0xFFFFFFFF;
 216
 217   #ifdef THERE_ARE_DIRECT_HASH_BYTES
 218   if (lenLimit == kNumHashDirectBytes)
 219   {
 220     if(curMatch > matchMinPos)
 221       while (maxLen < kNumHashDirectBytes)
 222         distances[++maxLen] = _pos - curMatch - 1;
 223     // We don't need tree in this case
 224   }
 225   else
 226   #endif
 227   {
 228     UInt32 len0, len1;
 229     len0 = len1 = kNumHashDirectBytes;
 230     UInt32 count = _cutValue;
 231     while(true)
 232     {
 233       if(curMatch <= matchMinPos || count-- == 0)
 234       {
 235         *ptr0 = kEmptyHashValue;
 236         *ptr1 = kEmptyHashValue;
 237         break;
 238       }
 239       Byte *pb = _buffer + curMatch;
 240       UInt32 len = MyMin(len0, len1);
 241       do
 242       {
 243         if (pb[len] != cur[len])
 244           break;
 245       }
 246       while(++len != lenLimit);
 247
 248       UInt32 delta = _pos - curMatch;
 249       while (maxLen < len)
 250         distances[++maxLen] = delta - 1;
 251
 252       UInt32 cyclicPos = (delta <= _cyclicBufferPos) ?
 253           (_cyclicBufferPos - delta):
 254           (_cyclicBufferPos - delta + _cyclicBufferSize);
 255       CIndex *pair = son + (cyclicPos << 1);
 256
 257       if (len != lenLimit)
 258       {
 259         if (pb[len] < cur[len])
 260         {
 261           *ptr1 = curMatch;
 262           ptr1 = pair + 1;
 263           curMatch = *ptr1;
 264           len1 = len;
 265         }
 266         else
 267         {
 268           *ptr0 = curMatch;
 269           ptr0 = pair;
 270           curMatch = *ptr0;
 271           len0 = len;
 272         }
 273       }
 274       else
 275       {
 276         *ptr1 = pair[0];
 277         *ptr0 = pair[1];
 278         break;
 279       }
 280     }
 281   }
 282   #ifdef HASH_ARRAY_2
 283   #ifdef HASH_ARRAY_3
 284   if (distances[4] < distances[3])
 285     distances[3] = distances[4];
 286   #endif
 287   if (distances[3] < distances[2])
 288     distances[2] = distances[3];
 289   #endif
 290   return maxLen;
 291 }
 292
 293 STDMETHODIMP_(void) CMatchFinderBinTree::DummyLongestMatch()
 294 {
 295   UInt32 lenLimit;
 296   if (_pos + _matchMaxLen <= _streamPos)
 297     lenLimit = _matchMaxLen;
 298   else
 299   {
 300     lenLimit = _streamPos - _pos;
 301     if(lenLimit < kNumHashBytes)
 302       return;
 303   }
 304   UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
 305   Byte *cur = _buffer + _pos;
 306
 307   #ifdef HASH_ARRAY_2
 308   UInt32 hash2Value;
 309   #ifdef HASH_ARRAY_3
 310   UInt32 hash3Value;
 311   UInt32 hashValue = Hash(cur, hash2Value, hash3Value);
 312   _hash[kHash3Offset + hash3Value] = _pos;
 313   #else
 314   UInt32 hashValue = Hash(cur, hash2Value);
 315   #endif
 316   _hash[kHash2Offset + hash2Value] = _pos;
 317   #else
 318   UInt32 hashValue = Hash(cur);
 319   #endif
 320
 321   UInt32 curMatch = _hash[hashValue];
 322   _hash[hashValue] = _pos;
 323
 324   CIndex *son = _hash + kHashSizeSum;
 325   CIndex *ptr0 = son + (_cyclicBufferPos << 1) + 1;
 326   CIndex *ptr1 = son + (_cyclicBufferPos << 1);
 327
 328   #ifdef THERE_ARE_DIRECT_HASH_BYTES
 329   if (lenLimit != kNumHashDirectBytes)
 330   #endif
 331   {
 332     UInt32 len0, len1;
 333     len0 = len1 = kNumHashDirectBytes;
 334     UInt32 count = _cutValue;
 335     while(true)
 336     {
 337       if(curMatch <= matchMinPos || count-- == 0)
 338         break;
 339       Byte *pb = _buffer + curMatch;
 340       UInt32 len = MyMin(len0, len1);
 341       do
 342       {
 343         if (pb[len] != cur[len])
 344           break;
 345       }
 346       while(++len != lenLimit);
 347
 348       UInt32 delta = _pos - curMatch;
 349       UInt32 cyclicPos = (delta <= _cyclicBufferPos) ?
 350         (_cyclicBufferPos - delta):
 351       (_cyclicBufferPos - delta + _cyclicBufferSize);
 352       CIndex *pair = son + (cyclicPos << 1);
 353
 354       if (len != lenLimit)
 355       {
 356         if (pb[len] < cur[len])
 357         {
 358           *ptr1 = curMatch;
 359           ptr1 = pair + 1;
 360           curMatch = *ptr1;
 361           len1 = len;
 362         }
 363         else
 364         {
 365           *ptr0 = curMatch;
 366           ptr0 = pair;
 367           curMatch = *ptr0;
 368           len0 = len;
 369         }
 370       }
 371       else
 372       {
 373         *ptr1 = pair[0];
 374         *ptr0 = pair[1];
 375         return;
 376       }
 377     }
 378   }
 379   *ptr0 = kEmptyHashValue;
 380   *ptr1 = kEmptyHashValue;
 381 }
 382
 383 void CMatchFinderBinTree::Normalize()
 384 {
 385   UInt32 subValue = _pos - _cyclicBufferSize;
 386   CIndex *items = _hash;
 387   UInt32 numItems = (kHashSizeSum + _cyclicBufferSize * 2);
 388   for (UInt32 i = 0; i < numItems; i++)
 389   {
 390     UInt32 value = items[i];
 391     if (value <= subValue)
 392       value = kEmptyHashValue;
 393     else
 394       value -= subValue;
 395     items[i] = value;
 396   }
 397   ReduceOffsets(subValue);
 398 }
 399
 400 STDMETHODIMP CMatchFinderBinTree::MovePos()
 401 {
 402   if (++_cyclicBufferPos == _cyclicBufferSize)
 403     _cyclicBufferPos = 0;
 404   RINOK(CLZInWindow::MovePos());
 405   if (_pos == kMaxValForNormalize)
 406     Normalize();
 407   return S_OK;
 408 }
 409
 410 STDMETHODIMP_(Byte) CMatchFinderBinTree::GetIndexByte(Int32 index)
 411   { return CLZInWindow::GetIndexByte(index); }
 412
 413 STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetMatchLen(Int32 index,
 414     UInt32 back, UInt32 limit)
 415   { return CLZInWindow::GetMatchLen(index, back, limit); }
 416
 417 STDMETHODIMP_(UInt32) CMatchFinderBinTree::GetNumAvailableBytes()
 418   { return CLZInWindow::GetNumAvailableBytes(); }
 419
 420 STDMETHODIMP_(const Byte *) CMatchFinderBinTree::GetPointerToCurrentPos()
 421   { return CLZInWindow::GetPointerToCurrentPos(); }
 422
 423 // IMatchFinderSetCallback
 424 STDMETHODIMP CMatchFinderBinTree::SetCallback(IMatchFinderCallback *callback)
 425 {
 426   m_Callback = callback;
 427   return S_OK;
 428 }
 429
 430 void CMatchFinderBinTree::BeforeMoveBlock()
 431 {
 432   if (m_Callback)
 433     m_Callback->BeforeChangingBufferPos();
 434   CLZInWindow::BeforeMoveBlock();
 435 }
 436
 437 void CMatchFinderBinTree::AfterMoveBlock()
 438 {
 439   if (m_Callback)
 440     m_Callback->AfterChangingBufferPos();
 441   CLZInWindow::AfterMoveBlock();
 442 }
 443
 444 }