goat3d: dad392c710df libs/openctm/liblzma/LzFind.c

goat3d

view libs/openctm/liblzma/LzFind.c @ 54:dad392c710df

added copyright headers and license files + readme

author	John Tsiombikas <nuclear@member.fsf.org>
date	Thu, 17 Apr 2014 08:50:36 +0300
parents
children

line source

1 /* LzFind.c -- Match finder for LZ algorithms

2 2008-10-04 : Igor Pavlov : Public domain */

4 #include <string.h>

6 #include "LzFind.h"

7 #include "LzHash.h"

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)

15 #define kStartMaxLen 3

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 }

26 /* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */

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 }

45 Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }

46 Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 index) { return p->buffer[index]; }

48 UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }

50 void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)

51 {

52 p->posLimit -= subValue;

53 p->pos -= subValue;

54 p->streamPos -= subValue;

55 }

57 static void MatchFinder_ReadBlock(CMatchFinder *p)

58 {

59 if (p->streamEndWasReached || p->result != SZ_OK)

60 return;

61 for (;;)

62 {

63 Byte *dest = p->buffer + (p->streamPos - p->pos);

64 size_t size = (p->bufferBase + p->blockSize - dest);

65 if (size == 0)

66 return;

67 p->result = p->stream->Read(p->stream, dest, &size);

68 if (p->result != SZ_OK)

69 return;

70 if (size == 0)

71 {

72 p->streamEndWasReached = 1;

73 return;

74 }

75 p->streamPos += (UInt32)size;

76 if (p->streamPos - p->pos > p->keepSizeAfter)

77 return;

78 }

79 }

81 void MatchFinder_MoveBlock(CMatchFinder *p)

82 {

83 memmove(p->bufferBase,

84 p->buffer - p->keepSizeBefore,

85 (size_t)(p->streamPos - p->pos + p->keepSizeBefore));

86 p->buffer = p->bufferBase + p->keepSizeBefore;

87 }

89 int MatchFinder_NeedMove(CMatchFinder *p)

90 {

91 /* if (p->streamEndWasReached) return 0; */

92 return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);

93 }

95 void MatchFinder_ReadIfRequired(CMatchFinder *p)

96 {

97 if (p->streamEndWasReached)

98 return;

99 if (p->keepSizeAfter >= p->streamPos - p->pos)

100 MatchFinder_ReadBlock(p);

101 }

102

103 static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)

104 {

105 if (MatchFinder_NeedMove(p))

106 MatchFinder_MoveBlock(p);

107 MatchFinder_ReadBlock(p);

108 }

109

110 static void MatchFinder_SetDefaultSettings(CMatchFinder *p)

111 {

112 p->cutValue = 32;

113 p->btMode = 1;

114 p->numHashBytes = 4;

115 /* p->skipModeBits = 0; */

116 p->directInput = 0;

117 p->bigHash = 0;

118 }

119

120 #define kCrcPoly 0xEDB88320

121

122 void MatchFinder_Construct(CMatchFinder *p)

123 {

124 UInt32 i;

125 p->bufferBase = 0;

126 p->directInput = 0;

127 p->hash = 0;

128 MatchFinder_SetDefaultSettings(p);

129

130 for (i = 0; i < 256; i++)

131 {

132 UInt32 r = i;

133 int j;

134 for (j = 0; j < 8; j++)

135 r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));

136 p->crc[i] = r;

137 }

138 }

139

140 static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAlloc *alloc)

141 {

142 alloc->Free(alloc, p->hash);

143 p->hash = 0;

144 }

145

146 void MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc)

147 {

148 MatchFinder_FreeThisClassMemory(p, alloc);

149 LzInWindow_Free(p, alloc);

150 }

151

152 static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)

153 {

154 size_t sizeInBytes = (size_t)num * sizeof(CLzRef);

155 if (sizeInBytes / sizeof(CLzRef) != num)

156 return 0;

157 return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);

158 }

159

160 int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,

161 UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,

162 ISzAlloc *alloc)

163 {

164 UInt32 sizeReserv;

165 if (historySize > kMaxHistorySize)

166 {

167 MatchFinder_Free(p, alloc);

168 return 0;

169 }

170 sizeReserv = historySize >> 1;

171 if (historySize > ((UInt32)2 << 30))

172 sizeReserv = historySize >> 2;

173 sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);

174

175 p->keepSizeBefore = historySize + keepAddBufferBefore + 1;

176 p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;

177 /* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */

178 if (LzInWindow_Create(p, sizeReserv, alloc))

179 {

180 UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1;

181 UInt32 hs;

182 p->matchMaxLen = matchMaxLen;

183 {

184 p->fixedHashSize = 0;

185 if (p->numHashBytes == 2)

186 hs = (1 << 16) - 1;

187 else

188 {

189 hs = historySize - 1;

190 hs |= (hs >> 1);

191 hs |= (hs >> 2);

192 hs |= (hs >> 4);

193 hs |= (hs >> 8);

194 hs >>= 1;

195 /* hs >>= p->skipModeBits; */

196 hs |= 0xFFFF; /* don't change it! It's required for Deflate */

197 if (hs > (1 << 24))

198 {

199 if (p->numHashBytes == 3)

200 hs = (1 << 24) - 1;

201 else

202 hs >>= 1;

203 }

204 }

205 p->hashMask = hs;

206 hs++;

207 if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;

208 if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;

209 if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;

210 hs += p->fixedHashSize;

211 }

212

213 {

214 UInt32 prevSize = p->hashSizeSum + p->numSons;

215 UInt32 newSize;

216 p->historySize = historySize;

217 p->hashSizeSum = hs;

218 p->cyclicBufferSize = newCyclicBufferSize;

219 p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);

220 newSize = p->hashSizeSum + p->numSons;

221 if (p->hash != 0 && prevSize == newSize)

222 return 1;

223 MatchFinder_FreeThisClassMemory(p, alloc);

224 p->hash = AllocRefs(newSize, alloc);

225 if (p->hash != 0)

226 {

227 p->son = p->hash + p->hashSizeSum;

228 return 1;

229 }

230 }

231 }

232 MatchFinder_Free(p, alloc);

233 return 0;

234 }

235

236 static void MatchFinder_SetLimits(CMatchFinder *p)

237 {

238 UInt32 limit = kMaxValForNormalize - p->pos;

239 UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;

240 if (limit2 < limit)

241 limit = limit2;

242 limit2 = p->streamPos - p->pos;

243 if (limit2 <= p->keepSizeAfter)

244 {

245 if (limit2 > 0)

246 limit2 = 1;

247 }

248 else

249 limit2 -= p->keepSizeAfter;

250 if (limit2 < limit)

251 limit = limit2;

252 {

253 UInt32 lenLimit = p->streamPos - p->pos;

254 if (lenLimit > p->matchMaxLen)

255 lenLimit = p->matchMaxLen;

256 p->lenLimit = lenLimit;

257 }

258 p->posLimit = p->pos + limit;

259 }

260

261 void MatchFinder_Init(CMatchFinder *p)

262 {

263 UInt32 i;

264 for (i = 0; i < p->hashSizeSum; i++)

265 p->hash[i] = kEmptyHashValue;

266 p->cyclicBufferPos = 0;

267 p->buffer = p->bufferBase;

268 p->pos = p->streamPos = p->cyclicBufferSize;

269 p->result = SZ_OK;

270 p->streamEndWasReached = 0;

271 MatchFinder_ReadBlock(p);

272 MatchFinder_SetLimits(p);

273 }

274

275 static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)

276 {

277 return (p->pos - p->historySize - 1) & kNormalizeMask;

278 }

279

280 void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)

281 {

282 UInt32 i;

283 for (i = 0; i < numItems; i++)

284 {

285 UInt32 value = items[i];

286 if (value <= subValue)

287 value = kEmptyHashValue;

288 else

289 value -= subValue;

290 items[i] = value;

291 }

292 }

293

294 static void MatchFinder_Normalize(CMatchFinder *p)

295 {

296 UInt32 subValue = MatchFinder_GetSubValue(p);

297 MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);

298 MatchFinder_ReduceOffsets(p, subValue);

299 }

300

301 static void MatchFinder_CheckLimits(CMatchFinder *p)

302 {

303 if (p->pos == kMaxValForNormalize)

304 MatchFinder_Normalize(p);

305 if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)

306 MatchFinder_CheckAndMoveAndRead(p);

307 if (p->cyclicBufferPos == p->cyclicBufferSize)

308 p->cyclicBufferPos = 0;

309 MatchFinder_SetLimits(p);

310 }

311

312 static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,

313 UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,

314 UInt32 *distances, UInt32 maxLen)

315 {

316 son[_cyclicBufferPos] = curMatch;

317 for (;;)

318 {

319 UInt32 delta = pos - curMatch;

320 if (cutValue-- == 0 || delta >= _cyclicBufferSize)

321 return distances;

322 {

323 const Byte *pb = cur - delta;

324 curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];

325 if (pb[maxLen] == cur[maxLen] && *pb == *cur)

326 {

327 UInt32 len = 0;

328 while (++len != lenLimit)

329 if (pb[len] != cur[len])

330 break;

331 if (maxLen < len)

332 {

333 *distances++ = maxLen = len;

334 *distances++ = delta - 1;

335 if (len == lenLimit)

336 return distances;

337 }

338 }

339 }

340 }

341 }

342

343 UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,

344 UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,

345 UInt32 *distances, UInt32 maxLen)

346 {

347 CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;

348 CLzRef *ptr1 = son + (_cyclicBufferPos << 1);

349 UInt32 len0 = 0, len1 = 0;

350 for (;;)

351 {

352 UInt32 delta = pos - curMatch;

353 if (cutValue-- == 0 || delta >= _cyclicBufferSize)

354 {

355 *ptr0 = *ptr1 = kEmptyHashValue;

356 return distances;

357 }

358 {

359 CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);

360 const Byte *pb = cur - delta;

361 UInt32 len = (len0 < len1 ? len0 : len1);

362 if (pb[len] == cur[len])

363 {

364 if (++len != lenLimit && pb[len] == cur[len])

365 while (++len != lenLimit)

366 if (pb[len] != cur[len])

367 break;

368 if (maxLen < len)

369 {

370 *distances++ = maxLen = len;

371 *distances++ = delta - 1;

372 if (len == lenLimit)

373 {

374 *ptr1 = pair[0];

375 *ptr0 = pair[1];

376 return distances;

377 }

378 }

379 }

380 if (pb[len] < cur[len])

381 {

382 *ptr1 = curMatch;

383 ptr1 = pair + 1;

384 curMatch = *ptr1;

385 len1 = len;

386 }

387 else

388 {

389 *ptr0 = curMatch;

390 ptr0 = pair;

391 curMatch = *ptr0;

392 len0 = len;

393 }

394 }

395 }

396 }

397

398 static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,

399 UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)

400 {

401 CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;

402 CLzRef *ptr1 = son + (_cyclicBufferPos << 1);

403 UInt32 len0 = 0, len1 = 0;

404 for (;;)

405 {

406 UInt32 delta = pos - curMatch;

407 if (cutValue-- == 0 || delta >= _cyclicBufferSize)

408 {

409 *ptr0 = *ptr1 = kEmptyHashValue;

410 return;

411 }

412 {

413 CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);

414 const Byte *pb = cur - delta;

415 UInt32 len = (len0 < len1 ? len0 : len1);

416 if (pb[len] == cur[len])

417 {

418 while (++len != lenLimit)

419 if (pb[len] != cur[len])

420 break;

421 {

422 if (len == lenLimit)

423 {

424 *ptr1 = pair[0];

425 *ptr0 = pair[1];

426 return;

427 }

428 }

429 }

430 if (pb[len] < cur[len])

431 {

432 *ptr1 = curMatch;

433 ptr1 = pair + 1;

434 curMatch = *ptr1;

435 len1 = len;

436 }

437 else

438 {

439 *ptr0 = curMatch;

440 ptr0 = pair;

441 curMatch = *ptr0;

442 len0 = len;

443 }

444 }

445 }

446 }

447

448 #define MOVE_POS \

449 ++p->cyclicBufferPos; \

450 p->buffer++; \

451 if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);

452

453 #define MOVE_POS_RET MOVE_POS return offset;

454

455 static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }

456

457 #define GET_MATCHES_HEADER2(minLen, ret_op) \

458 UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \

459 lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \

460 cur = p->buffer;

461

462 #define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)

463 #define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue)

464

465 #define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue

466

467 #define GET_MATCHES_FOOTER(offset, maxLen) \

468 offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \

469 distances + offset, maxLen) - distances); MOVE_POS_RET;

470

471 #define SKIP_FOOTER \

472 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;

473

474 static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

475 {

476 UInt32 offset;

477 GET_MATCHES_HEADER(2)

478 HASH2_CALC;

479 curMatch = p->hash[hashValue];

480 p->hash[hashValue] = p->pos;

481 offset = 0;

482 GET_MATCHES_FOOTER(offset, 1)

483 }

484

485 UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

486 {

487 UInt32 offset;

488 GET_MATCHES_HEADER(3)

489 HASH_ZIP_CALC;

490 curMatch = p->hash[hashValue];

491 p->hash[hashValue] = p->pos;

492 offset = 0;

493 GET_MATCHES_FOOTER(offset, 2)

494 }

495

496 static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

497 {

498 UInt32 hash2Value, delta2, maxLen, offset;

499 GET_MATCHES_HEADER(3)

500

501 HASH3_CALC;

502

503 delta2 = p->pos - p->hash[hash2Value];

504 curMatch = p->hash[kFix3HashSize + hashValue];

505

506 p->hash[hash2Value] =

507 p->hash[kFix3HashSize + hashValue] = p->pos;

508

509

510 maxLen = 2;

511 offset = 0;

512 if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)

513 {

514 for (; maxLen != lenLimit; maxLen++)

515 if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])

516 break;

517 distances[0] = maxLen;

518 distances[1] = delta2 - 1;

519 offset = 2;

520 if (maxLen == lenLimit)

521 {

522 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));

523 MOVE_POS_RET;

524 }

525 }

526 GET_MATCHES_FOOTER(offset, maxLen)

527 }

528

529 static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

530 {

531 UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;

532 GET_MATCHES_HEADER(4)

533

534 HASH4_CALC;

535

536 delta2 = p->pos - p->hash[ hash2Value];

537 delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];

538 curMatch = p->hash[kFix4HashSize + hashValue];

539

540 p->hash[ hash2Value] =

541 p->hash[kFix3HashSize + hash3Value] =

542 p->hash[kFix4HashSize + hashValue] = p->pos;

543

544 maxLen = 1;

545 offset = 0;

546 if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)

547 {

548 distances[0] = maxLen = 2;

549 distances[1] = delta2 - 1;

550 offset = 2;

551 }

552 if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)

553 {

554 maxLen = 3;

555 distances[offset + 1] = delta3 - 1;

556 offset += 2;

557 delta2 = delta3;

558 }

559 if (offset != 0)

560 {

561 for (; maxLen != lenLimit; maxLen++)

562 if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])

563 break;

564 distances[offset - 2] = maxLen;

565 if (maxLen == lenLimit)

566 {

567 SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));

568 MOVE_POS_RET;

569 }

570 }

571 if (maxLen < 3)

572 maxLen = 3;

573 GET_MATCHES_FOOTER(offset, maxLen)

574 }

575

576 static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

577 {

578 UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;

579 GET_MATCHES_HEADER(4)

580

581 HASH4_CALC;

582

583 delta2 = p->pos - p->hash[ hash2Value];

584 delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];

585 curMatch = p->hash[kFix4HashSize + hashValue];

586

587 p->hash[ hash2Value] =

588 p->hash[kFix3HashSize + hash3Value] =

589 p->hash[kFix4HashSize + hashValue] = p->pos;

590

591 maxLen = 1;

592 offset = 0;

593 if (delta2 < p->cyclicBufferSize && *(cur - delta2) == *cur)

594 {

595 distances[0] = maxLen = 2;

596 distances[1] = delta2 - 1;

597 offset = 2;

598 }

599 if (delta2 != delta3 && delta3 < p->cyclicBufferSize && *(cur - delta3) == *cur)

600 {

601 maxLen = 3;

602 distances[offset + 1] = delta3 - 1;

603 offset += 2;

604 delta2 = delta3;

605 }

606 if (offset != 0)

607 {

608 for (; maxLen != lenLimit; maxLen++)

609 if (cur[(ptrdiff_t)maxLen - delta2] != cur[maxLen])

610 break;

611 distances[offset - 2] = maxLen;

612 if (maxLen == lenLimit)

613 {

614 p->son[p->cyclicBufferPos] = curMatch;

615 MOVE_POS_RET;

616 }

617 }

618 if (maxLen < 3)

619 maxLen = 3;

620 offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),

621 distances + offset, maxLen) - (distances));

622 MOVE_POS_RET

623 }

624

625 UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)

626 {

627 UInt32 offset;

628 GET_MATCHES_HEADER(3)

629 HASH_ZIP_CALC;

630 curMatch = p->hash[hashValue];

631 p->hash[hashValue] = p->pos;

632 offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),

633 distances, 2) - (distances));

634 MOVE_POS_RET

635 }

636

637 static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

638 {

639 do

640 {

641 SKIP_HEADER(2)

642 HASH2_CALC;

643 curMatch = p->hash[hashValue];

644 p->hash[hashValue] = p->pos;

645 SKIP_FOOTER

646 }

647 while (--num != 0);

648 }

649

650 void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

651 {

652 do

653 {

654 SKIP_HEADER(3)

655 HASH_ZIP_CALC;

656 curMatch = p->hash[hashValue];

657 p->hash[hashValue] = p->pos;

658 SKIP_FOOTER

659 }

660 while (--num != 0);

661 }

662

663 static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

664 {

665 do

666 {

667 UInt32 hash2Value;

668 SKIP_HEADER(3)

669 HASH3_CALC;

670 curMatch = p->hash[kFix3HashSize + hashValue];

671 p->hash[hash2Value] =

672 p->hash[kFix3HashSize + hashValue] = p->pos;

673 SKIP_FOOTER

674 }

675 while (--num != 0);

676 }

677

678 static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

679 {

680 do

681 {

682 UInt32 hash2Value, hash3Value;

683 SKIP_HEADER(4)

684 HASH4_CALC;

685 curMatch = p->hash[kFix4HashSize + hashValue];

686 p->hash[ hash2Value] =

687 p->hash[kFix3HashSize + hash3Value] = p->pos;

688 p->hash[kFix4HashSize + hashValue] = p->pos;

689 SKIP_FOOTER

690 }

691 while (--num != 0);

692 }

693

694 static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

695 {

696 do

697 {

698 UInt32 hash2Value, hash3Value;

699 SKIP_HEADER(4)

700 HASH4_CALC;

701 curMatch = p->hash[kFix4HashSize + hashValue];

702 p->hash[ hash2Value] =

703 p->hash[kFix3HashSize + hash3Value] =

704 p->hash[kFix4HashSize + hashValue] = p->pos;

705 p->son[p->cyclicBufferPos] = curMatch;

706 MOVE_POS

707 }

708 while (--num != 0);

709 }

710

711 void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)

712 {

713 do

714 {

715 SKIP_HEADER(3)

716 HASH_ZIP_CALC;

717 curMatch = p->hash[hashValue];

718 p->hash[hashValue] = p->pos;

719 p->son[p->cyclicBufferPos] = curMatch;

720 MOVE_POS

721 }

722 while (--num != 0);

723 }

724

725 void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable)

726 {

727 vTable->Init = (Mf_Init_Func)MatchFinder_Init;

728 vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;

729 vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;

730 vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;

731 if (!p->btMode)

732 {

733 vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;

734 vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;

735 }

736 else if (p->numHashBytes == 2)

737 {

738 vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;

739 vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;

740 }

741 else if (p->numHashBytes == 3)

742 {

743 vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;

744 vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;

745 }

746 else

747 {

748 vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;

749 vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;

750 }

751 }