vcs.maemo.org Git - physicsfs/blob - lzma/Java/SevenZip/Compression/LZ/BinTree.java

   1 // LZ.BinTree
   2
   3 package SevenZip.Compression.LZ;
   4 import java.io.IOException;
   5
   6
   7 public class BinTree extends InWindow
   8 {
   9         int _cyclicBufferPos;
  10         int _cyclicBufferSize = 0;
  11         int _matchMaxLen;
  12
  13         int[] _son;
  14         int[] _hash;
  15
  16         int _cutValue = 0xFF;
  17         int _hashMask;
  18         int _hashSizeSum = 0;
  19
  20         boolean HASH_ARRAY = true;
  21
  22         static final int kHash2Size = 1 << 10;
  23         static final int kHash3Size = 1 << 16;
  24         static final int kBT2HashSize = 1 << 16;
  25         static final int kStartMaxLen = 1;
  26         static final int kHash3Offset = kHash2Size;
  27         static final int kEmptyHashValue = 0;
  28         static final int kMaxValForNormalize = (1 << 30) - 1;
  29
  30         int kNumHashDirectBytes = 0;
  31         int kMinMatchCheck = 4;
  32         int 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
  52
  53
  54         public void Init() throws IOException
  55         {
  56                 super.Init();
  57                 for (int i = 0; i < _hashSizeSum; i++)
  58                         _hash[i] = kEmptyHashValue;
  59                 _cyclicBufferPos = 0;
  60                 ReduceOffsets(-1);
  61         }
  62
  63         public void MovePos() throws IOException
  64         {
  65                 if (++_cyclicBufferPos >= _cyclicBufferSize)
  66                         _cyclicBufferPos = 0;
  67                 super.MovePos();
  68                 if (_pos == kMaxValForNormalize)
  69                         Normalize();
  70         }
  71
  72
  73
  74
  75
  76
  77
  78
  79         public boolean Create(int historySize, int keepAddBufferBefore,
  80                         int matchMaxLen, int keepAddBufferAfter)
  81         {
  82                 if (historySize > kMaxValForNormalize - 256)
  83                         return false;
  84                 _cutValue = 16 + (matchMaxLen >> 1);
  85
  86                 int windowReservSize = (historySize + keepAddBufferBefore +
  87                                 matchMaxLen + keepAddBufferAfter) / 2 + 256;
  88
  89                 super.Create(historySize + keepAddBufferBefore, matchMaxLen + keepAddBufferAfter, windowReservSize);
  90
  91                 _matchMaxLen = matchMaxLen;
  92
  93                 int cyclicBufferSize = historySize + 1;
  94                 if (_cyclicBufferSize != cyclicBufferSize)
  95                         _son = new int[(_cyclicBufferSize = cyclicBufferSize) * 2];
  96
  97                 int 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 int [_hashSizeSum = hs];
 116                 return true;
 117         }
 118         public int GetMatches(int[] distances) throws IOException
 119         {
 120                 int 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                 int offset = 0;
 134                 int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
 135                 int cur = _bufferOffset + _pos;
 136                 int maxLen = kStartMaxLen; // to avoid items for len < hashSize;
 137                 int hashValue, hash2Value = 0, hash3Value = 0;
 138
 139                 if (HASH_ARRAY)
 140                 {
 141                         int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF);
 142                         hash2Value = temp & (kHash2Size - 1);
 143                         temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8);
 144                         hash3Value = temp & (kHash3Size - 1);
 145                         hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask;
 146                 }
 147                 else
 148                         hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8));
 149
 150                 int curMatch = _hash[kFixHashSize + hashValue];
 151                 if (HASH_ARRAY)
 152                 {
 153                         int curMatch2 = _hash[hash2Value];
 154                         int 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                 int ptr0 = (_cyclicBufferPos << 1) + 1;
 182                 int ptr1 = (_cyclicBufferPos << 1);
 183
 184                 int 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                 int count = _cutValue;
 201
 202                 while (true)
 203                 {
 204                         if (curMatch <= matchMinPos || count-- == 0)
 205                         {
 206                                 _son[ptr0] = _son[ptr1] = kEmptyHashValue;
 207                                 break;
 208                         }
 209                         int delta = _pos - curMatch;
 210                         int cyclicPos = ((delta <= _cyclicBufferPos) ?
 211                                 (_cyclicBufferPos - delta) :
 212                                 (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
 213
 214                         int pby1 = _bufferOffset + curMatch;
 215                         int 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] & 0xFF) < (_bufferBase[cur + len] & 0xFF))
 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(int num) throws IOException
 253         {
 254                 do
 255                 {
 256                         int 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                         int matchMinPos = (_pos > _cyclicBufferSize) ? (_pos - _cyclicBufferSize) : 0;
 270                         int cur = _bufferOffset + _pos;
 271
 272                         int hashValue;
 273
 274                         if (HASH_ARRAY)
 275                         {
 276                                 int temp = CrcTable[_bufferBase[cur] & 0xFF] ^ (_bufferBase[cur + 1] & 0xFF);
 277                                 int hash2Value = temp & (kHash2Size - 1);
 278                                 _hash[hash2Value] = _pos;
 279                                 temp ^= ((int)(_bufferBase[cur + 2] & 0xFF) << 8);
 280                                 int hash3Value = temp & (kHash3Size - 1);
 281                                 _hash[kHash3Offset + hash3Value] = _pos;
 282                                 hashValue = (temp ^ (CrcTable[_bufferBase[cur + 3] & 0xFF] << 5)) & _hashMask;
 283                         }
 284                         else
 285                                 hashValue = ((_bufferBase[cur] & 0xFF) ^ ((int)(_bufferBase[cur + 1] & 0xFF) << 8));
 286
 287                         int curMatch = _hash[kFixHashSize + hashValue];
 288                         _hash[kFixHashSize + hashValue] = _pos;
 289
 290                         int ptr0 = (_cyclicBufferPos << 1) + 1;
 291                         int ptr1 = (_cyclicBufferPos << 1);
 292
 293                         int len0, len1;
 294                         len0 = len1 = kNumHashDirectBytes;
 295
 296                         int count = _cutValue;
 297                         while (true)
 298                         {
 299                                 if (curMatch <= matchMinPos || count-- == 0)
 300                                 {
 301                                         _son[ptr0] = _son[ptr1] = kEmptyHashValue;
 302                                         break;
 303                                 }
 304
 305                                 int delta = _pos - curMatch;
 306                                 int cyclicPos = ((delta <= _cyclicBufferPos) ?
 307                                         (_cyclicBufferPos - delta) :
 308                                         (_cyclicBufferPos - delta + _cyclicBufferSize)) << 1;
 309
 310                                 int pby1 = _bufferOffset + curMatch;
 311                                 int 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] & 0xFF) < (_bufferBase[cur + len] & 0xFF))
 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(int[] items, int numItems, int subValue)
 345         {
 346                 for (int i = 0; i < numItems; i++)
 347                 {
 348                         int 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                 int subValue = _pos - _cyclicBufferSize;
 360                 NormalizeLinks(_son, _cyclicBufferSize * 2, subValue);
 361                 NormalizeLinks(_hash, _hashSizeSum, subValue);
 362                 ReduceOffsets(subValue);
 363         }
 364
 365         public void SetCutValue(int cutValue) { _cutValue = cutValue; }
 366
 367         private static final int[] CrcTable = new int[256];
 368
 369         static
 370         {
 371                 for (int i = 0; i < 256; i++)
 372                 {
 373                         int r = i;
 374                         for (int j = 0; j < 8; j++)
 375                                 if ((r & 1) != 0)
 376                                         r = (r >>> 1) ^ 0xEDB88320;
 377                                 else
 378                                         r >>>= 1;
 379                         CrcTable[i] = r;
 380                 }
 381         }
 382 }