git.maemo.org Git - physicsfs/blob - lzma/CS/7zip/Compress/LZ/LzBinTree.cs

   1 // LzBinTree.cs
   2
   3 using System;
   4
   5 namespace SevenZip.Compression.LZ
   6 {
   7         public class BinTree : InWindow, IMatchFinder
   8         {
   9                 UInt32 _cyclicBufferPos;
  10                 UInt32 _cyclicBufferSize = 0;
  11                 UInt32 _matchMaxLen;
  12
  13                 UInt32[] _son;
  14                 UInt32[] _hash;
  15
  16                 UInt32 _cutValue = 0xFF;
  17                 UInt32 _hashMask;
  18                 UInt32 _hashSizeSum = 0;
  19
  20                 bool HASH_ARRAY = true;
  21
  22                 const UInt32 kHash2Size = 1 << 10;
  23                 const UInt32 kHash3Size = 1 << 16;
  24                 const UInt32 kBT2HashSize = 1 << 16;
  25                 const UInt32 kStartMaxLen = 1;
  26                 const UInt32 kHash3Offset = kHash2Size;
  27                 const UInt32 kEmptyHashValue = 0;
  28                 const UInt32 kMaxValForNormalize = ((UInt32)1 << 31) - 1;
  29
  30                 UInt32 kNumHashDirectBytes = 0;
  31                 UInt32 kMinMatchCheck = 4;
  32                 UInt32 kFixHashSize = kHash2Size + kHash3Size;
  33
  34                 public void SetType(int numHashBytes)
  35                 {
  36                         HASH_ARRAY = (numHashBytes > 2);
  37                         if (HASH_ARRAY)
  38                         {
  39                                 kNumHashDirectBytes = 0;
  40                                 kMinMatchCheck = 4;
  41                                 kFixHashSize = kHash2Size + kHash3Size;
  42                         }
  43                         else
  44                         {
  45                                 kNumHashDirectBytes = 2;
  46                                 kMinMatchCheck = 2 + 1;
  47                                 kFixHashSize = 0;
  48                         }
  49                 }
  50
  51                 public new void SetStream(System.IO.Stream stream) { base.SetStream(stream); }
  52                 public new void ReleaseStream() { base.ReleaseStream(); }
  53
  54                 public new void Init()
  55                 {
  56                         base.Init();
  57                         for (UInt32 i = 0; i < _hashSizeSum; i++)
  58                                 _hash[i] = kEmptyHashValue;
  59                         _cyclicBufferPos = 0;
  60                         ReduceOffsets(-1);
  61                 }
  62
  63                 public new void MovePos()
  64                 {
  65                         if (++_cyclicBufferPos >= _cyclicBufferSize)
  66                                 _cyclicBufferPos = 0;
  67                         base.MovePos();
  68                         if (_pos == kMaxValForNormalize)
  69                                 Normalize();
  70                 }
  71
  72                 public new Byte GetIndexByte(Int32 index) { return base.GetIndexByte(index); }
  73
  74                 public new UInt32 GetMatchLen(Int32 index, UInt32 distance, UInt32 limit)
  75                 { return base.GetMatchLen(index, distance, limit); }
  76
  77                 public new UInt32 GetNumAvailableBytes() { return base.GetNumAvailableBytes(); }
  78
  79                 public void Create(UInt32 historySize, UInt32 keepAddBufferBefore,
  80                                 UInt32 matchMaxLen, UInt32 keepAddBufferAfter)
  81                 {
  82                         if (historySize > kMaxValForNormalize - 256)
  83                                 throw new Exception();
  84                         _cutValue = 16 + (matchMaxLen >> 1);
  85
  86                         UInt32 windowReservSize = (historySize + keepAddBufferBefore +
  87                                         matchMaxLen + keepAddBufferAfter) / 2 + 256;
  88
  89                         base.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize);
  90
  91                         _matchMaxLen = matchMaxLen;
  92
  93                         UInt32 cyclicBufferSize = historySize + 1;
  94                         if (_cyclicBufferSize != cyclicBufferSize)
  95                                 _son = new UInt32[(_cyclicBufferSize = cyclicBufferSize) * 2];
  96
  97                         UInt32 hs = kBT2HashSize;
  98
  99                         if (HASH_ARRAY)
 100                         {
 101                                 hs = historySize - 1;
 102                                 hs |= (hs >> 1);
 103                                 hs |= (hs >> 2);
 104                                 hs |= (hs >> 4);
 105                                 hs |= (hs >> 8);
 106                                 hs >>= 1;
 107                                 hs |= 0xFFFF;
 108                                 if (hs > (1 << 24))
 109                                         hs >>= 1;
 110                                 _hashMask = hs;
 111                                 hs++;
 112                                 hs += kFixHashSize;
 113                         }
 114                         if (hs != _hashSizeSum)
 115                                 _hash = new UInt32[_hashSizeSum = hs];
 116                 }
 117
 118                 public UInt32 GetMatches(UInt32[] distances)
 119                 {
 120                         UInt32 lenLimit;
 121                         if (_pos + _matchMaxLen <= _streamPos)
 122                                 lenLimit = _matchMaxLen;
 123                         else
 124                         {
 125                                 lenLimit = _streamPos - _pos;
 126                                 if (lenLimit < kMinMatchCheck)
 127                                 {
 128                                         MovePos();
 129                                         return 0;
 130                                 }
 131                         }
 132
 133                         UInt32 offset = 0;
 134                         UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
 135                         UInt32 cur = _bufferOffset + _pos;
 136                         UInt32 maxLen = kStartMaxLen; // to avoid items for len < hashSize;
 137                         UInt32 hashValue, hash2Value = 0, hash3Value = 0;
 138
 139                         if (HASH_ARRAY)
 140                         {
 141                                 UInt32 temp = CRC.Table[_bufferBase[cur]] ^ _bufferBase[cur + 1];
 142                                 hash2Value = temp & (kHash2Size - 1);
 143                                 temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8);
 144                                 hash3Value = temp & (kHash3Size - 1);
 145                                 hashValue = (temp ^ (CRC.Table[_bufferBase[cur + 3]] << 5)) & _hashMask;
 146                         }
 147                         else
 148                                 hashValue = _bufferBase[cur] ^ ((UInt32)(_bufferBase[cur + 1]) << 8);
 149
 150                         UInt32 curMatch = _hash[kFixHashSize + hashValue];
 151                         if (HASH_ARRAY)
 152                         {
 153                                 UInt32 curMatch2 = _hash[hash2Value];
 154                                 UInt32 curMatch3 = _hash[kHash3Offset + hash3Value];
 155                                 _hash[hash2Value] = _pos;
 156                                 _hash[kHash3Offset + hash3Value] = _pos;
 157                                 if (curMatch2 > matchMinPos)
 158                                         if (_bufferBase[_bufferOffset + curMatch2] == _bufferBase[cur])
 159                                         {
 160                                                 distances[offset++] = maxLen = 2;
 161                                                 distances[offset++] = _pos - curMatch2 - 1;
 162                                         }
 163                                 if (curMatch3 > matchMinPos)
 164                                         if (_bufferBase[_bufferOffset + curMatch3] == _bufferBase[cur])
 165                                         {
 166                                                 if (curMatch3 == curMatch2)
 167                                                         offset -= 2;
 168                                                 distances[offset++] = maxLen = 3;
 169                                                 distances[offset++] = _pos - curMatch3 - 1;
 170                                                 curMatch2 = curMatch3;
 171                                         }
 172                                 if (offset != 0 && curMatch2 == curMatch)
 173                                 {
 174                                         offset -= 2;
 175                                         maxLen = kStartMaxLen;
 176                                 }
 177                         }
 178
 179                         _hash[kFixHashSize + hashValue] = _pos;
 180
 181                         UInt32 ptr0 = (_cyclicBufferPos << 1) + 1;
 182                         UInt32 ptr1 = (_cyclicBufferPos << 1);
 183
 184                         UInt32 len0, len1;
 185                         len0 = len1 = kNumHashDirectBytes;
 186
 187                         if (kNumHashDirectBytes != 0)
 188                         {
 189                                 if (curMatch > matchMinPos)
 190                                 {
 191                                         if (_bufferBase[_bufferOffset + curMatch + kNumHashDirectBytes] !=
 192                                                         _bufferBase[cur + kNumHashDirectBytes])
 193                                         {
 194                                                 distances[offset++] = maxLen = kNumHashDirectBytes;
 195                                                 distances[offset++] = _pos - curMatch - 1;
 196                                         }
 197                                 }
 198                         }
 199
 200                         UInt32 count = _cutValue;
 201
 202                         while(true)
 203                         {
 204                                 if(curMatch <= matchMinPos || count-- == 0)
 205                                 {
 206                                         _son[ptr0] = _son[ptr1] = kEmptyHashValue;
 207                                         break;
 208                                 }
 209                                 UInt32 delta = _pos - curMatch;
 210                                 UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ?
 211                                                         (_cyclicBufferPos - delta) :
 212                                                         (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
 213
 214                                 UInt32 pby1 = _bufferOffset + curMatch;
 215                                 UInt32 len = Math.Min(len0, len1);
 216                                 if (_bufferBase[pby1 + len] == _bufferBase[cur + len])
 217                                 {
 218                                         while(++len != lenLimit)
 219                                                 if (_bufferBase[pby1 + len] != _bufferBase[cur + len])
 220                                                         break;
 221                                         if (maxLen < len)
 222                                         {
 223                                                 distances[offset++] = maxLen = len;
 224                                                 distances[offset++] = delta - 1;
 225                                                 if (len == lenLimit)
 226                                                 {
 227                                                         _son[ptr1] = _son[cyclicPos];
 228                                                         _son[ptr0] = _son[cyclicPos + 1];
 229                                                         break;
 230                                                 }
 231                                         }
 232                                 }
 233                                 if (_bufferBase[pby1 + len] < _bufferBase[cur + len])
 234                                 {
 235                                         _son[ptr1] = curMatch;
 236                                         ptr1 = cyclicPos + 1;
 237                                         curMatch = _son[ptr1];
 238                                         len1 = len;
 239                                 }
 240                                 else
 241                                 {
 242                                         _son[ptr0] = curMatch;
 243                                         ptr0 = cyclicPos;
 244                                         curMatch = _son[ptr0];
 245                                         len0 = len;
 246                                 }
 247                         }
 248                         MovePos();
 249                         return offset;
 250                 }
 251
 252                 public void Skip(UInt32 num)
 253                 {
 254                         do
 255                         {
 256                                 UInt32 lenLimit;
 257                                 if (_pos + _matchMaxLen <= _streamPos)
 258                                         lenLimit = _matchMaxLen;
 259                                 else
 260                                 {
 261                                         lenLimit = _streamPos - _pos;
 262                                         if (lenLimit < kMinMatchCheck)
 263                                         {
 264                                                 MovePos();
 265                                                 continue;
 266                                         }
 267                                 }
 268
 269                                 UInt32 matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
 270                                 UInt32 cur = _bufferOffset + _pos;
 271
 272                                 UInt32 hashValue;
 273
 274                                 if (HASH_ARRAY)
 275                                 {
 276                                         UInt32 temp = CRC.Table[_bufferBase[cur]] ^ _bufferBase[cur + 1];
 277                                         UInt32 hash2Value = temp & (kHash2Size - 1);
 278                                         _hash[hash2Value] = _pos;
 279                                         temp ^= ((UInt32)(_bufferBase[cur + 2]) << 8);
 280                                         UInt32 hash3Value = temp & (kHash3Size - 1);
 281                                         _hash[kHash3Offset + hash3Value] = _pos;
 282                                         hashValue = (temp ^ (CRC.Table[_bufferBase[cur + 3]] << 5)) & _hashMask;
 283                                 }
 284                                 else
 285                                         hashValue = _bufferBase[cur] ^ ((UInt32)(_bufferBase[cur + 1]) << 8);
 286
 287                                 UInt32 curMatch = _hash[kFixHashSize + hashValue];
 288                                 _hash[kFixHashSize + hashValue] = _pos;
 289
 290                                 UInt32 ptr0 = (_cyclicBufferPos << 1) + 1;
 291                                 UInt32 ptr1 = (_cyclicBufferPos << 1);
 292
 293                                 UInt32 len0, len1;
 294                                 len0 = len1 = kNumHashDirectBytes;
 295
 296                                 UInt32 count = _cutValue;
 297                                 while (true)
 298                                 {
 299                                         if (curMatch <= matchMinPos || count-- == 0)
 300                                         {
 301                                                 _son[ptr0] = _son[ptr1] = kEmptyHashValue;
 302                                                 break;
 303                                         }
 304
 305                                         UInt32 delta = _pos - curMatch;
 306                                         UInt32 cyclicPos = ((delta <= _cyclicBufferPos) ?
 307                                                                 (_cyclicBufferPos - delta) :
 308                                                                 (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
 309
 310                                         UInt32 pby1 = _bufferOffset + curMatch;
 311                                         UInt32 len = Math.Min(len0, len1);
 312                                         if (_bufferBase[pby1 + len] == _bufferBase[cur + len])
 313                                         {
 314                                                 while (++len != lenLimit)
 315                                                         if (_bufferBase[pby1 + len] != _bufferBase[cur + len])
 316                                                                 break;
 317                                                 if (len == lenLimit)
 318                                                 {
 319                                                         _son[ptr1] = _son[cyclicPos];
 320                                                         _son[ptr0] = _son[cyclicPos + 1];
 321                                                         break;
 322                                                 }
 323                                         }
 324                                         if (_bufferBase[pby1 + len] < _bufferBase[cur + len])
 325                                         {
 326                                                 _son[ptr1] = curMatch;
 327                                                 ptr1 = cyclicPos + 1;
 328                                                 curMatch = _son[ptr1];
 329                                                 len1 = len;
 330                                         }
 331                                         else
 332                                         {
 333                                                 _son[ptr0] = curMatch;
 334                                                 ptr0 = cyclicPos;
 335                                                 curMatch = _son[ptr0];
 336                                                 len0 = len;
 337                                         }
 338                                 }
 339                                 MovePos();
 340                         }
 341                         while (--num != 0);
 342                 }
 343
 344                 void NormalizeLinks(UInt32[] items, UInt32 numItems, UInt32 subValue)
 345                 {
 346                         for (UInt32 i = 0; i < numItems; i++)
 347                         {
 348                                 UInt32 value = items[i];
 349                                 if (value <= subValue)
 350                                         value = kEmptyHashValue;
 351                                 else
 352                                         value -= subValue;
 353                                 items[i] = value;
 354                         }
 355                 }
 356
 357                 void Normalize()
 358                 {
 359                         UInt32 subValue = _pos - _cyclicBufferSize;
 360                         NormalizeLinks(_son, _cyclicBufferSize * 2, subValue);
 361                         NormalizeLinks(_hash, _hashSizeSum, subValue);
 362                         ReduceOffsets((Int32)subValue);
 363                 }
 364
 365                 public void SetCutValue(UInt32 cutValue) { _cutValue = cutValue; }
 366         }
 367 }