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