repo sync | baa3858 | 2013-07-26 17:53:31 -0700 | [diff] [blame] | 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 *alloc)
|
| 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[index]; }
|
| 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) ? _cyclicBufferSize : 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 Byte *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 > _cyclicBufferPos) ? _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 > _cyclicBufferPos) ? _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->cyclicBufferSize, 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) == *cur)
|
| 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) == *cur)
|
| 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_GetNumAvailableBytes;
|
| 740 | vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
|
| 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 | }
|