Mercurial > vba-linux

annotate src/win32/7zip/7z/C/LzFind.c @ 1:f9f4f1b99eed

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
importing src directory
author Robert McIntyre <rlm@mit.edu>
date Sat, 03 Mar 2012 10:31:27 -0600
parents
children
rev   line source
rlm@1 1 /* LzFind.c -- Match finder for LZ algorithms
rlm@1 2 2008-10-04 : Igor Pavlov : Public domain */
rlm@1 3
rlm@1 4 #include <string.h>
rlm@1 5
rlm@1 6 #include "LzFind.h"
rlm@1 7 #include "LzHash.h"
rlm@1 8
rlm@1 9 #define kEmptyHashValue 0
rlm@1 10 #define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
rlm@1 11 #define kNormalizeStepMin (1 << 10) /* it must be power of 2 */
rlm@1 12 #define kNormalizeMask (~(kNormalizeStepMin - 1))
rlm@1 13 #define kMaxHistorySize ((UInt32)3 << 30)
rlm@1 14
rlm@1 15 #define kStartMaxLen 3
rlm@1 16
rlm@1 17 static void LzInWindow_Free(CMatchFinder *p, ISzAlloc *alloc)
rlm@1 18 {
rlm@1 19 if (!p->directInput)
rlm@1 20 {
rlm@1 21 alloc->Free(alloc, p->bufferBase);
rlm@1 22 p->bufferBase = 0;
rlm@1 23 }
rlm@1 24 }
rlm@1 25
rlm@1 26 /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
rlm@1 27
rlm@1 28 static int LzInWindow_Create(CMatchFinder *p, UInt32 keepSizeReserv, ISzAlloc *alloc)
rlm@1 29 {
rlm@1 30 UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
rlm@1 31 if (p->directInput)
rlm@1 32 {
rlm@1 33 p->blockSize = blockSize;
rlm@1 34 return 1;
rlm@1 35 }
rlm@1 36 if (p->bufferBase == 0 || p->blockSize != blockSize)
rlm@1 37 {
rlm@1 38 LzInWindow_Free(p, alloc);
rlm@1 39 p->blockSize = blockSize;
rlm@1 40 p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
rlm@1 41 }
rlm@1 42 return (p->bufferBase != 0);
rlm@1 43 }
rlm@1 44
rlm@1 45 Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
rlm@1 46 Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 index) { return p->buffer[index]; }
rlm@1 47
rlm@1 48 UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
rlm@1 49
rlm@1 50 void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
rlm@1 51 {
rlm@1 52 p->posLimit -= subValue;
rlm@1 53 p->pos -= subValue;
rlm@1 54 p->streamPos -= subValue;
rlm@1 55 }
rlm@1 56
rlm@1 57 static void MatchFinder_ReadBlock(CMatchFinder *p)
rlm@1 58 {
rlm@1 59 if (p->streamEndWasReached || p->result != SZ_OK)
rlm@1 60 return;
rlm@1 61 for (;;)
rlm@1 62 {
rlm@1 63 Byte *dest = p->buffer + (p->streamPos - p->pos);
rlm@1 64 size_t size = (p->bufferBase + p->blockSize - dest);
rlm@1 65 if (size == 0)
rlm@1 66 return;
rlm@1 67 p->result = p->stream->Read(p->stream, dest, &size);
rlm@1 68 if (p->result != SZ_OK)
rlm@1 69 return;
rlm@1 70 if (size == 0)
rlm@1 71 {
rlm@1 72 p->streamEndWasReached = 1;
rlm@1 73 return;
rlm@1 74 }
rlm@1 75 p->streamPos += (UInt32)size;
rlm@1 76 if (p->streamPos - p->pos > p->keepSizeAfter)
rlm@1 77 return;
rlm@1 78 }
rlm@1 79 }
rlm@1 80
rlm@1 81 void MatchFinder_MoveBlock(CMatchFinder *p)
rlm@1 82 {
rlm@1 83 memmove(p->bufferBase,
rlm@1 84 p->buffer - p->keepSizeBefore,
rlm@1 85 (size_t)(p->streamPos - p->pos + p->keepSizeBefore));
rlm@1 86 p->buffer = p->bufferBase + p->keepSizeBefore;
rlm@1 87 }
rlm@1 88
rlm@1 89 int MatchFinder_NeedMove(CMatchFinder *p)
rlm@1 90 {
rlm@1 91 /* if (p->streamEndWasReached) return 0; */
rlm@1 92 return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
rlm@1 93 }
rlm@1 94
rlm@1 95 void MatchFinder_ReadIfRequired(CMatchFinder *p)
rlm@1 96 {
rlm@1 97 if (p->streamEndWasReached)
rlm@1 98 return;
rlm@1 99 if (p->keepSizeAfter >= p->streamPos - p->pos)
rlm@1 100 MatchFinder_ReadBlock(p);
rlm@1 101 }
rlm@1 102
rlm@1 103 static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)
rlm@1 104 {
rlm@1 105 if (MatchFinder_NeedMove(p))
rlm@1 106 MatchFinder_MoveBlock(p);
rlm@1 107 MatchFinder_ReadBlock(p);
rlm@1 108 }
rlm@1 109
rlm@1 110 static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
rlm@1 111 {
rlm@1 112 p->cutValue = 32;
rlm@1 113 p->btMode = 1;
rlm@1 114 p->numHashBytes = 4;
rlm@1 115 /* p->skipModeBits = 0; */
rlm@1 116 p->directInput = 0;
rlm@1 117 p->bigHash = 0;
rlm@1 118 }
rlm@1 119
rlm@1 120 #define kCrcPoly 0xEDB88320
rlm@1 121
rlm@1 122 void MatchFinder_Construct(CMatchFinder *p)
rlm@1 123 {
rlm@1 124 UInt32 i;
rlm@1 125 p->bufferBase = 0;
rlm@1 126 p->directInput = 0;
rlm@1 127 p->hash = 0;
rlm@1 128 MatchFinder_SetDefaultSettings(p);
rlm@1 129
rlm@1 130 for (i = 0; i < 256; i++)
rlm@1 131 {
rlm@1 132 UInt32 r = i;
rlm@1 133 int j;
rlm@1 134 for (j = 0; j < 8; j++)
rlm@1 135 r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
rlm@1 136 p->crc[i] = r;
rlm@1 137 }
rlm@1 138 }
rlm@1 139
rlm@1 140 static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)
rlm@1 141 {
rlm@1 142 alloc->Free(alloc, p->hash);
rlm@1 143 p->hash = 0;
rlm@1 144 }
rlm@1 145
rlm@1 146 void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)
rlm@1 147 {
rlm@1 148 MatchFinder_FreeThisClassMemory(p, alloc);
rlm@1 149 LzInWindow_Free(p, alloc);
rlm@1 150 }
rlm@1 151
rlm@1 152 static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)
rlm@1 153 {
rlm@1 154 size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
rlm@1 155 if (sizeInBytes / sizeof(CLzRef) != num)
rlm@1 156 return 0;
rlm@1 157 return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
rlm@1 158 }
rlm@1 159
rlm@1 160 int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
rlm@1 161 UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
rlm@1 162 ISzAlloc *alloc)
rlm@1 163 {
rlm@1 164 UInt32 sizeReserv;
rlm@1 165 if (historySize > kMaxHistorySize)
rlm@1 166 {
rlm@1 167 MatchFinder_Free(p, alloc);
rlm@1 168 return 0;
rlm@1 169 }
rlm@1 170 sizeReserv = historySize >> 1;
rlm@1 171 if (historySize > ((UInt32)2 << 30))
rlm@1 172 sizeReserv = historySize >> 2;
rlm@1 173 sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
rlm@1 174
rlm@1 175 p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
rlm@1 176 p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
rlm@1 177 /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
rlm@1 178 if (LzInWindow_Create(p, sizeReserv, alloc))
rlm@1 179 {
rlm@1 180 UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1;
rlm@1 181 UInt32 hs;
rlm@1 182 p->matchMaxLen = matchMaxLen;
rlm@1 183 {
rlm@1 184 p->fixedHashSize = 0;
rlm@1 185 if (p->numHashBytes == 2)
rlm@1 186 hs = (1 << 16) - 1;
rlm@1 187 else
rlm@1 188 {
rlm@1 189 hs = historySize - 1;
rlm@1 190 hs |= (hs >> 1);
rlm@1 191 hs |= (hs >> 2);
rlm@1 192 hs |= (hs >> 4);
rlm@1 193 hs |= (hs >> 8);
rlm@1 194 hs >>= 1;
rlm@1 195 /* hs >>= p->skipModeBits; */
rlm@1 196 hs |= 0xFFFF; /* don't change it! It's required for Deflate */
rlm@1 197 if (hs > (1 << 24))
rlm@1 198 {
rlm@1 199 if (p->numHashBytes == 3)
rlm@1 200 hs = (1 << 24) - 1;
rlm@1 201 else
rlm@1 202 hs >>= 1;
rlm@1 203 }
rlm@1 204 }
rlm@1 205 p->hashMask = hs;
rlm@1 206 hs++;
rlm@1 207 if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
rlm@1 208 if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
rlm@1 209 if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
rlm@1 210 hs += p->fixedHashSize;
rlm@1 211 }
rlm@1 212
rlm@1 213 {
rlm@1 214 UInt32 prevSize = p->hashSizeSum + p->numSons;
rlm@1 215 UInt32 newSize;
rlm@1 216 p->historySize = historySize;
rlm@1 217 p->hashSizeSum = hs;
rlm@1 218 p->cyclicBufferSize = newCyclicBufferSize;
rlm@1 219 p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);
rlm@1 220 newSize = p->hashSizeSum + p->numSons;
rlm@1 221 if (p->hash != 0 && prevSize == newSize)
rlm@1 222 return 1;
rlm@1 223 MatchFinder_FreeThisClassMemory(p, alloc);
rlm@1 224 p->hash = AllocRefs(newSize, alloc);
rlm@1 225 if (p->hash != 0)
rlm@1 226 {
rlm@1 227 p->son = p->hash + p->hashSizeSum;
rlm@1 228 return 1;
rlm@1 229 }
rlm@1 230 }
rlm@1 231 }
rlm@1 232 MatchFinder_Free(p, alloc);
rlm@1 233 return 0;
rlm@1 234 }
rlm@1 235
rlm@1 236 static void MatchFinder_SetLimits(CMatchFinder *p)
rlm@1 237 {
rlm@1 238 UInt32 limit = kMaxValForNormalize - p->pos;
rlm@1 239 UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
rlm@1 240 if (limit2 < limit)
rlm@1 241 limit = limit2;
rlm@1 242 limit2 = p->streamPos - p->pos;
rlm@1 243 if (limit2 <= p->keepSizeAfter)
rlm@1 244 {
rlm@1 245 if (limit2 > 0)
rlm@1 246 limit2 = 1;
rlm@1 247 }
rlm@1 248 else
rlm@1 249 limit2 -= p->keepSizeAfter;
rlm@1 250 if (limit2 < limit)
rlm@1 251 limit = limit2;
rlm@1 252 {
rlm@1 253 UInt32 lenLimit = p->streamPos - p->pos;
rlm@1 254 if (lenLimit > p->matchMaxLen)
rlm@1 255 lenLimit = p->matchMaxLen;
rlm@1 256 p->lenLimit = lenLimit;
rlm@1 257 }
rlm@1 258 p->posLimit = p->pos + limit;
rlm@1 259 }
rlm@1 260
rlm@1 261 void MatchFinder_Init(CMatchFinder *p)
rlm@1 262 {
rlm@1 263 UInt32 i;
rlm@1 264 for (i = 0; i < p->hashSizeSum; i++)
rlm@1 265 p->hash[i] = kEmptyHashValue;
rlm@1 266 p->cyclicBufferPos = 0;
rlm@1 267 p->buffer = p->bufferBase;
rlm@1 268 p->pos = p->streamPos = p->cyclicBufferSize;
rlm@1 269 p->result = SZ_OK;
rlm@1 270 p->streamEndWasReached = 0;
rlm@1 271 MatchFinder_ReadBlock(p);
rlm@1 272 MatchFinder_SetLimits(p);
rlm@1 273 }
rlm@1 274
rlm@1 275 static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
rlm@1 276 {
rlm@1 277 return (p->pos - p->historySize - 1) & kNormalizeMask;
rlm@1 278 }
rlm@1 279
rlm@1 280 void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)
rlm@1 281 {
rlm@1 282 UInt32 i;
rlm@1 283 for (i = 0; i < numItems; i++)
rlm@1 284 {
rlm@1 285 UInt32 value = items[i];
rlm@1 286 if (value <= subValue)
rlm@1 287 value = kEmptyHashValue;
rlm@1 288 else
rlm@1 289 value -= subValue;
rlm@1 290 items[i] = value;
rlm@1 291 }
rlm@1 292 }
rlm@1 293
rlm@1 294 static void MatchFinder_Normalize(CMatchFinder *p)
rlm@1 295 {
rlm@1 296 UInt32 subValue = MatchFinder_GetSubValue(p);
rlm@1 297 MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);
rlm@1 298 MatchFinder_ReduceOffsets(p, subValue);
rlm@1 299 }
rlm@1 300
rlm@1 301 static void MatchFinder_CheckLimits(CMatchFinder *p)
rlm@1 302 {
rlm@1 303 if (p->pos == kMaxValForNormalize)
rlm@1 304 MatchFinder_Normalize(p);
rlm@1 305 if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
rlm@1 306 MatchFinder_CheckAndMoveAndRead(p);
rlm@1 307 if (p->cyclicBufferPos == p->cyclicBufferSize)
rlm@1 308 p->cyclicBufferPos = 0;
rlm@1 309 MatchFinder_SetLimits(p);
rlm@1 310 }
rlm@1 311
rlm@1 312 static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
rlm@1 313 UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
rlm@1 314 UInt32 *distances, UInt32 maxLen)
rlm@1 315 {
rlm@1 316 son[_cyclicBufferPos] = curMatch;
rlm@1 317 for (;;)
rlm@1 318 {
rlm@1 319 UInt32 delta = pos - curMatch;
rlm@1 320 if (cutValue-- == 0 || delta >= _cyclicBufferSize)
rlm@1 321 return distances;
rlm@1 322 {
rlm@1 323 const Byte *pb = cur - delta;
rlm@1 324 curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
rlm@1 325 if (pb[maxLen] == cur[maxLen] && *pb == *cur)
rlm@1 326 {
rlm@1 327 UInt32 len = 0;
rlm@1 328 while (++len != lenLimit)
rlm@1 329 if (pb[len] != cur[len])
rlm@1 330 break;
rlm@1 331 if (maxLen < len)
rlm@1 332 {
rlm@1 333 *distances++ = maxLen = len;
rlm@1 334 *distances++ = delta - 1;
rlm@1 335 if (len == lenLimit)
rlm@1 336 return distances;
rlm@1 337 }
rlm@1 338 }
rlm@1 339 }
rlm@1 340 }
rlm@1 341 }
rlm@1 342
rlm@1 343 UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
rlm@1 344 UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
rlm@1 345 UInt32 *distances, UInt32 maxLen)
rlm@1 346 {
rlm@1 347 CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
rlm@1 348 CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
rlm@1 349 UInt32 len0 = 0, len1 = 0;
rlm@1 350 for (;;)
rlm@1 351 {
rlm@1 352 UInt32 delta = pos - curMatch;
rlm@1 353 if (cutValue-- == 0 || delta >= _cyclicBufferSize)
rlm@1 354 {
rlm@1 355 *ptr0 = *ptr1 = kEmptyHashValue;
rlm@1 356 return distances;
rlm@1 357 }
rlm@1 358 {
rlm@1 359 CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
rlm@1 360 const Byte *pb = cur - delta;
rlm@1 361 UInt32 len = (len0 < len1 ? len0 : len1);
rlm@1 362 if (pb[len] == cur[len])
rlm@1 363 {
rlm@1 364 if (++len != lenLimit && pb[len] == cur[len])
rlm@1 365 while (++len != lenLimit)
rlm@1 366 if (pb[len] != cur[len])
rlm@1 367 break;
rlm@1 368 if (maxLen < len)
rlm@1 369 {
rlm@1 370 *distances++ = maxLen = len;
rlm@1 371 *distances++ = delta - 1;
rlm@1 372 if (len == lenLimit)
rlm@1 373 {
rlm@1 374 *ptr1 = pair[0];
rlm@1 375 *ptr0 = pair[1];
rlm@1 376 return distances;
rlm@1 377 }
rlm@1 378 }
rlm@1 379 }
rlm@1 380 if (pb[len] < cur[len])
rlm@1 381 {
rlm@1 382 *ptr1 = curMatch;
rlm@1 383 ptr1 = pair + 1;
rlm@1 384 curMatch = *ptr1;
rlm@1 385 len1 = len;
rlm@1 386 }
rlm@1 387 else
rlm@1 388 {
rlm@1 389 *ptr0 = curMatch;
rlm@1 390 ptr0 = pair;
rlm@1 391 curMatch = *ptr0;
rlm@1 392 len0 = len;
rlm@1 393 }
rlm@1 394 }
rlm@1 395 }
rlm@1 396 }
rlm@1 397
rlm@1 398 static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
rlm@1 399 UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
rlm@1 400 {
rlm@1 401 CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
rlm@1 402 CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
rlm@1 403 UInt32 len0 = 0, len1 = 0;
rlm@1 404 for (;;)
rlm@1 405 {
rlm@1 406 UInt32 delta = pos - curMatch;
rlm@1 407 if (cutValue-- == 0 || delta >= _cyclicBufferSize)
rlm@1 408 {
rlm@1 409 *ptr0 = *ptr1 = kEmptyHashValue;
rlm@1 410 return;
rlm@1 411 }
rlm@1 412 {
rlm@1 413 CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
rlm@1 414 const Byte *pb = cur - delta;
rlm@1 415 UInt32 len = (len0 < len1 ? len0 : len1);
rlm@1 416 if (pb[len] == cur[len])
rlm@1 417 {
rlm@1 418 while (++len != lenLimit)
rlm@1 419 if (pb[len] != cur[len])
rlm@1 420 break;
rlm@1 421 {
rlm@1 422 if (len == lenLimit)
rlm@1 423 {
rlm@1 424 *ptr1 = pair[0];
rlm@1 425 *ptr0 = pair[1];
rlm@1 426 return;
rlm@1 427 }
rlm@1 428 }
rlm@1 429 }
rlm@1 430 if (pb[len] < cur[len])
rlm@1 431 {
rlm@1 432 *ptr1 = curMatch;
rlm@1 433 ptr1 = pair + 1;
rlm@1 434 curMatch = *ptr1;
rlm@1 435 len1 = len;
rlm@1 436 }
rlm@1 437 else
rlm@1 438 {
rlm@1 439 *ptr0 = curMatch;
rlm@1 440 ptr0 = pair;
rlm@1 441 curMatch = *ptr0;
rlm@1 442 len0 = len;
rlm@1 443 }
rlm@1 444 }
rlm@1 445 }
rlm@1 446 }
rlm@1 447
rlm@1 448 #define MOVE_POS \
rlm@1 449 ++p->cyclicBufferPos; \
rlm@1 450 p->buffer++; \
rlm@1 451 if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
rlm@1 452
rlm@1 453 #define MOVE_POS_RET MOVE_POS return offset;
rlm@1 454
rlm@1 455 static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
rlm@1 456
rlm@1 457 #define GET_MATCHES_HEADER2(minLen, ret_op) \
rlm@1 458 UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \
rlm@1 459 lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
rlm@1 460 cur = p->buffer;
rlm@1 461
rlm@1 462 #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
rlm@1 463 #define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue)
rlm@1 464
rlm@1 465 #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
rlm@1 466
rlm@1 467 #define GET_MATCHES_FOOTER(offset, maxLen) \
rlm@1 468 offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
rlm@1 469 distances + offset, maxLen) - distances); MOVE_POS_RET;
rlm@1 470
rlm@1 471 #define SKIP_FOOTER \
rlm@1 472 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
rlm@1 473
rlm@1 474 static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
rlm@1 475 {
rlm@1 476 UInt32 offset;
rlm@1 477 GET_MATCHES_HEADER(2)
rlm@1 478 HASH2_CALC;
rlm@1 479 curMatch = p->hash[hashValue];
rlm@1 480 p->hash[hashValue] = p->pos;
rlm@1 481 offset = 0;
rlm@1 482 GET_MATCHES_FOOTER(offset, 1)
rlm@1 483 }
rlm@1 484
rlm@1 485 UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
rlm@1 486 {
rlm@1 487 UInt32 offset;
rlm@1 488 GET_MATCHES_HEADER(3)
rlm@1 489 HASH_ZIP_CALC;
rlm@1 490 curMatch = p->hash[hashValue];
rlm@1 491 p->hash[hashValue] = p->pos;
rlm@1 492 offset = 0;
rlm@1 493 GET_MATCHES_FOOTER(offset, 2)
rlm@1 494 }
rlm@1 495
rlm@1 496 static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
rlm@1 497 {
rlm@1 498 UInt32 hash2Value, delta2, maxLen, offset;
rlm@1 499 GET_MATCHES_HEADER(3)
rlm@1 500
rlm@1 501 HASH3_CALC;
rlm@1 502
rlm@1 503 delta2 = p->pos - p->hash[hash2Value];
rlm@1 504 curMatch = p->hash[kFix3HashSize + hashValue];
rlm@1 505
rlm@1 506 p->hash[hash2Value] =
rlm@1 507 p->hash[kFix3HashSize + hashValue] = p->pos;
rlm@1 508
rlm@1 509
rlm@1 510 maxLen = 2;
rlm@1 511 offset = 0;
rlm@1 512 if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
rlm@1 513 {
rlm@1 514 for (; maxLen != lenLimit; maxLen++)
rlm@1 515 if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
rlm@1 516 break;
rlm@1 517 distances[0] = maxLen;
rlm@1 518 distances[1] = delta2 - 1;
rlm@1 519 offset = 2;
rlm@1 520 if (maxLen == lenLimit)
rlm@1 521 {
rlm@1 522 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
rlm@1 523 MOVE_POS_RET;
rlm@1 524 }
rlm@1 525 }
rlm@1 526 GET_MATCHES_FOOTER(offset, maxLen)
rlm@1 527 }
rlm@1 528
rlm@1 529 static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
rlm@1 530 {
rlm@1 531 UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
rlm@1 532 GET_MATCHES_HEADER(4)
rlm@1 533
rlm@1 534 HASH4_CALC;
rlm@1 535
rlm@1 536 delta2 = p->pos - p->hash[ hash2Value];
rlm@1 537 delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
rlm@1 538 curMatch = p->hash[kFix4HashSize + hashValue];
rlm@1 539
rlm@1 540 p->hash[ hash2Value] =
rlm@1 541 p->hash[kFix3HashSize + hash3Value] =
rlm@1 542 p->hash[kFix4HashSize + hashValue] = p->pos;
rlm@1 543
rlm@1 544 maxLen = 1;
rlm@1 545 offset = 0;
rlm@1 546 if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
rlm@1 547 {
rlm@1 548 distances[0] = maxLen = 2;
rlm@1 549 distances[1] = delta2 - 1;
rlm@1 550 offset = 2;
rlm@1 551 }
rlm@1 552 if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
rlm@1 553 {
rlm@1 554 maxLen = 3;
rlm@1 555 distances[offset + 1] = delta3 - 1;
rlm@1 556 offset += 2;
rlm@1 557 delta2 = delta3;
rlm@1 558 }
rlm@1 559 if (offset != 0)
rlm@1 560 {
rlm@1 561 for (; maxLen != lenLimit; maxLen++)
rlm@1 562 if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
rlm@1 563 break;
rlm@1 564 distances[offset - 2] = maxLen;
rlm@1 565 if (maxLen == lenLimit)
rlm@1 566 {
rlm@1 567 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
rlm@1 568 MOVE_POS_RET;
rlm@1 569 }
rlm@1 570 }
rlm@1 571 if (maxLen < 3)
rlm@1 572 maxLen = 3;
rlm@1 573 GET_MATCHES_FOOTER(offset, maxLen)
rlm@1 574 }
rlm@1 575
rlm@1 576 static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
rlm@1 577 {
rlm@1 578 UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
rlm@1 579 GET_MATCHES_HEADER(4)
rlm@1 580
rlm@1 581 HASH4_CALC;
rlm@1 582
rlm@1 583 delta2 = p->pos - p->hash[ hash2Value];
rlm@1 584 delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
rlm@1 585 curMatch = p->hash[kFix4HashSize + hashValue];
rlm@1 586
rlm@1 587 p->hash[ hash2Value] =
rlm@1 588 p->hash[kFix3HashSize + hash3Value] =
rlm@1 589 p->hash[kFix4HashSize + hashValue] = p->pos;
rlm@1 590
rlm@1 591 maxLen = 1;
rlm@1 592 offset = 0;
rlm@1 593 if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)
rlm@1 594 {
rlm@1 595 distances[0] = maxLen = 2;
rlm@1 596 distances[1] = delta2 - 1;
rlm@1 597 offset = 2;
rlm@1 598 }
rlm@1 599 if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)
rlm@1 600 {
rlm@1 601 maxLen = 3;
rlm@1 602 distances[offset + 1] = delta3 - 1;
rlm@1 603 offset += 2;
rlm@1 604 delta2 = delta3;
rlm@1 605 }
rlm@1 606 if (offset != 0)
rlm@1 607 {
rlm@1 608 for (; maxLen != lenLimit; maxLen++)
rlm@1 609 if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])
rlm@1 610 break;
rlm@1 611 distances[offset - 2] = maxLen;
rlm@1 612 if (maxLen == lenLimit)
rlm@1 613 {
rlm@1 614 p->son[p->cyclicBufferPos] = curMatch;
rlm@1 615 MOVE_POS_RET;
rlm@1 616 }
rlm@1 617 }
rlm@1 618 if (maxLen < 3)
rlm@1 619 maxLen = 3;
rlm@1 620 offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
rlm@1 621 distances + offset, maxLen) - (distances));
rlm@1 622 MOVE_POS_RET
rlm@1 623 }
rlm@1 624
rlm@1 625 UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
rlm@1 626 {
rlm@1 627 UInt32 offset;
rlm@1 628 GET_MATCHES_HEADER(3)
rlm@1 629 HASH_ZIP_CALC;
rlm@1 630 curMatch = p->hash[hashValue];
rlm@1 631 p->hash[hashValue] = p->pos;
rlm@1 632 offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
rlm@1 633 distances, 2) - (distances));
rlm@1 634 MOVE_POS_RET
rlm@1 635 }
rlm@1 636
rlm@1 637 static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
rlm@1 638 {
rlm@1 639 do
rlm@1 640 {
rlm@1 641 SKIP_HEADER(2)
rlm@1 642 HASH2_CALC;
rlm@1 643 curMatch = p->hash[hashValue];
rlm@1 644 p->hash[hashValue] = p->pos;
rlm@1 645 SKIP_FOOTER
rlm@1 646 }
rlm@1 647 while (--num != 0);
rlm@1 648 }
rlm@1 649
rlm@1 650 void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
rlm@1 651 {
rlm@1 652 do
rlm@1 653 {
rlm@1 654 SKIP_HEADER(3)
rlm@1 655 HASH_ZIP_CALC;
rlm@1 656 curMatch = p->hash[hashValue];
rlm@1 657 p->hash[hashValue] = p->pos;
rlm@1 658 SKIP_FOOTER
rlm@1 659 }
rlm@1 660 while (--num != 0);
rlm@1 661 }
rlm@1 662
rlm@1 663 static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
rlm@1 664 {
rlm@1 665 do
rlm@1 666 {
rlm@1 667 UInt32 hash2Value;
rlm@1 668 SKIP_HEADER(3)
rlm@1 669 HASH3_CALC;
rlm@1 670 curMatch = p->hash[kFix3HashSize + hashValue];
rlm@1 671 p->hash[hash2Value] =
rlm@1 672 p->hash[kFix3HashSize + hashValue] = p->pos;
rlm@1 673 SKIP_FOOTER
rlm@1 674 }
rlm@1 675 while (--num != 0);
rlm@1 676 }
rlm@1 677
rlm@1 678 static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
rlm@1 679 {
rlm@1 680 do
rlm@1 681 {
rlm@1 682 UInt32 hash2Value, hash3Value;
rlm@1 683 SKIP_HEADER(4)
rlm@1 684 HASH4_CALC;
rlm@1 685 curMatch = p->hash[kFix4HashSize + hashValue];
rlm@1 686 p->hash[ hash2Value] =
rlm@1 687 p->hash[kFix3HashSize + hash3Value] = p->pos;
rlm@1 688 p->hash[kFix4HashSize + hashValue] = p->pos;
rlm@1 689 SKIP_FOOTER
rlm@1 690 }
rlm@1 691 while (--num != 0);
rlm@1 692 }
rlm@1 693
rlm@1 694 static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
rlm@1 695 {
rlm@1 696 do
rlm@1 697 {
rlm@1 698 UInt32 hash2Value, hash3Value;
rlm@1 699 SKIP_HEADER(4)
rlm@1 700 HASH4_CALC;
rlm@1 701 curMatch = p->hash[kFix4HashSize + hashValue];
rlm@1 702 p->hash[ hash2Value] =
rlm@1 703 p->hash[kFix3HashSize + hash3Value] =
rlm@1 704 p->hash[kFix4HashSize + hashValue] = p->pos;
rlm@1 705 p->son[p->cyclicBufferPos] = curMatch;
rlm@1 706 MOVE_POS
rlm@1 707 }
rlm@1 708 while (--num != 0);
rlm@1 709 }
rlm@1 710
rlm@1 711 void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
rlm@1 712 {
rlm@1 713 do
rlm@1 714 {
rlm@1 715 SKIP_HEADER(3)
rlm@1 716 HASH_ZIP_CALC;
rlm@1 717 curMatch = p->hash[hashValue];
rlm@1 718 p->hash[hashValue] = p->pos;
rlm@1 719 p->son[p->cyclicBufferPos] = curMatch;
rlm@1 720 MOVE_POS
rlm@1 721 }
rlm@1 722 while (--num != 0);
rlm@1 723 }
rlm@1 724
rlm@1 725 void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)
rlm@1 726 {
rlm@1 727 vTable->Init = (Mf_Init_Func)MatchFinder_Init;
rlm@1 728 vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;
rlm@1 729 vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
rlm@1 730 vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
rlm@1 731 if (!p->btMode)
rlm@1 732 {
rlm@1 733 vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
rlm@1 734 vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
rlm@1 735 }
rlm@1 736 else if (p->numHashBytes == 2)
rlm@1 737 {
rlm@1 738 vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
rlm@1 739 vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
rlm@1 740 }
rlm@1 741 else if (p->numHashBytes == 3)
rlm@1 742 {
rlm@1 743 vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
rlm@1 744 vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
rlm@1 745 }
rlm@1 746 else
rlm@1 747 {
rlm@1 748 vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
rlm@1 749 vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
rlm@1 750 }
rlm@1 751 }