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