mercurial-scm/hg: contrib/python-zstandard/zstd/compress/zstd

annotate contrib/python-zstandard/zstd/compress/zstd_lazy.c @ 45625:c11099cc1de4

log: map --removed to walkopts.force_changelog_traversal This is the flag to forcibly enable the slowpath. I'm not sure if the slowpath parameter should be merged with this flag, so let's keep it as an immutable flag for now. I'll add another flag to support "grep --all-files". These two will be the flags which aren't directly mapped from the command-line options.

author	Yuya Nishihara <yuya@tcha.org>
date	Sat, 12 Sep 2020 21:54:58 +0900
parents	de7838053207
children

rev	line source
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1 /*
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	2 * Copyright (c) 2016-present, Yann Collet, Facebook, Inc.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	3 * All rights reserved.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	4 *
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	5 * This source code is licensed under both the BSD-style license (found in the
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	6 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	7 * in the COPYING file in the root directory of this source tree).
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	8 * You may select, at your option, one of the above-listed licenses.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	9 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	10
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	11 #include "zstd_compress_internal.h"
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	12 #include "zstd_lazy.h"
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	13
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	14
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	15 /-************************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	16 * Binary Tree search
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	17 ***************************************/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	18
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	19 static void
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	20 ZSTD_updateDUBT(ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	21 const BYTE* ip, const BYTE* iend,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	22 U32 mls)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	23 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	24 const ZSTD_compressionParameters* const cParams = &ms->cParams;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	25 U32* const hashTable = ms->hashTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	26 U32 const hashLog = cParams->hashLog;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	27
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	28 U32* const bt = ms->chainTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	29 U32 const btLog = cParams->chainLog - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	30 U32 const btMask = (1 << btLog) - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	31
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	32 const BYTE* const base = ms->window.base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	33 U32 const target = (U32)(ip - base);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	34 U32 idx = ms->nextToUpdate;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	35
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	36 if (idx != target)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	37 DEBUGLOG(7, "ZSTD_updateDUBT, from %u to %u (dictLimit:%u)",
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	38 idx, target, ms->window.dictLimit);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	39 assert(ip + 8 <= iend); /* condition for ZSTD_hashPtr */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	40 (void)iend;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	41
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	42 assert(idx >= ms->window.dictLimit); /* condition for valid base+idx */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	43 for ( ; idx < target ; idx++) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	44 size_t const h = ZSTD_hashPtr(base + idx, hashLog, mls); /* assumption : ip + 8 <= iend */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	45 U32 const matchIndex = hashTable[h];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	46
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	47 U32* const nextCandidatePtr = bt + 2*(idx&btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	48 U32* const sortMarkPtr = nextCandidatePtr + 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	49
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	50 DEBUGLOG(8, "ZSTD_updateDUBT: insert %u", idx);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	51 hashTable[h] = idx; /* Update Hash Table */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	52 nextCandidatePtr = matchIndex; / update BT like a chain */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	53 *sortMarkPtr = ZSTD_DUBT_UNSORTED_MARK;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	54 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	55 ms->nextToUpdate = target;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	56 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	57
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	58
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	59 /** ZSTD_insertDUBT1() :
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	60 * sort one already inserted but unsorted position
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	61 * assumption : current >= btlow == (current - btmask)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	62 * doesn't fail */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	63 static void
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	64 ZSTD_insertDUBT1(ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	65 U32 current, const BYTE* inputEnd,
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	66 U32 nbCompares, U32 btLow,
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	67 const ZSTD_dictMode_e dictMode)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	68 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	69 const ZSTD_compressionParameters* const cParams = &ms->cParams;
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	70 U32* const bt = ms->chainTable;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	71 U32 const btLog = cParams->chainLog - 1;
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	72 U32 const btMask = (1 << btLog) - 1;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	73 size_t commonLengthSmaller=0, commonLengthLarger=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	74 const BYTE* const base = ms->window.base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	75 const BYTE* const dictBase = ms->window.dictBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	76 const U32 dictLimit = ms->window.dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	77 const BYTE* const ip = (current>=dictLimit) ? base + current : dictBase + current;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	78 const BYTE* const iend = (current>=dictLimit) ? inputEnd : dictBase + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	79 const BYTE* const dictEnd = dictBase + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	80 const BYTE* const prefixStart = base + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	81 const BYTE* match;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	82 U32* smallerPtr = bt + 2*(current&btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	83 U32* largerPtr = smallerPtr + 1;
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	84 U32 matchIndex = smallerPtr; / this candidate is unsorted : next sorted candidate is reached through smallerPtr, while largerPtr contains previous unsorted candidate (which is already saved and can be overwritten) */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	85 U32 dummy32; /* to be nullified at the end */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	86 U32 const windowValid = ms->window.lowLimit;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	87 U32 const maxDistance = 1U << cParams->windowLog;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	88 U32 const windowLow = (current - windowValid > maxDistance) ? current - maxDistance : windowValid;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	89
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	90
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	91 DEBUGLOG(8, "ZSTD_insertDUBT1(%u) (dictLimit=%u, lowLimit=%u)",
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	92 current, dictLimit, windowLow);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	93 assert(current >= btLow);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	94 assert(ip < iend); /* condition for ZSTD_count */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	95
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	96 while (nbCompares-- && (matchIndex > windowLow)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	97 U32* const nextPtr = bt + 2*(matchIndex & btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	98 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	99 assert(matchIndex < current);
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	100 /* note : all candidates are now supposed sorted,
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	101 * but it's still possible to have nextPtr[1] == ZSTD_DUBT_UNSORTED_MARK
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	102 * when a real index has the same value as ZSTD_DUBT_UNSORTED_MARK */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	103
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	104 if ( (dictMode != ZSTD_extDict)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	105 \|\| (matchIndex+matchLength >= dictLimit) /* both in current segment*/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	106 \|\| (current < dictLimit) /* both in extDict */) {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	107 const BYTE* const mBase = ( (dictMode != ZSTD_extDict)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	108 \|\| (matchIndex+matchLength >= dictLimit)) ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	109 base : dictBase;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	110 assert( (matchIndex+matchLength >= dictLimit) /* might be wrong if extDict is incorrectly set to 0 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	111 \|\| (current < dictLimit) );
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	112 match = mBase + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	113 matchLength += ZSTD_count(ip+matchLength, match+matchLength, iend);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	114 } else {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	115 match = dictBase + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	116 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	117 if (matchIndex+matchLength >= dictLimit)
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	118 match = base + matchIndex; /* preparation for next read of match[matchLength] */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	119 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	120
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	121 DEBUGLOG(8, "ZSTD_insertDUBT1: comparing %u with %u : found %u common bytes ",
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	122 current, matchIndex, (U32)matchLength);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	123
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	124 if (ip+matchLength == iend) { /* equal : no way to know if inf or sup */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	125 break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt tree */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	126 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	127
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	128 if (match[matchLength] < ip[matchLength]) { /* necessarily within buffer */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	129 /* match is smaller than current */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	130 smallerPtr = matchIndex; / update smaller idx */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	131 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	132 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop searching */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	133 DEBUGLOG(8, "ZSTD_insertDUBT1: %u (>btLow=%u) is smaller : next => %u",
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	134 matchIndex, btLow, nextPtr[1]);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	135 smallerPtr = nextPtr+1; /* new "candidate" => larger than match, which was smaller than target */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	136 matchIndex = nextPtr[1]; /* new matchIndex, larger than previous and closer to current */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	137 } else {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	138 /* match is larger than current */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	139 *largerPtr = matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	140 commonLengthLarger = matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	141 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop searching */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	142 DEBUGLOG(8, "ZSTD_insertDUBT1: %u (>btLow=%u) is larger => %u",
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	143 matchIndex, btLow, nextPtr[0]);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	144 largerPtr = nextPtr;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	145 matchIndex = nextPtr[0];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	146 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	147
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	148 smallerPtr = largerPtr = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	149 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	150
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	151
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	152 static size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	153 ZSTD_DUBT_findBetterDictMatch (
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	154 ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	155 const BYTE* const ip, const BYTE* const iend,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	156 size_t* offsetPtr,
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	157 size_t bestLength,
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	158 U32 nbCompares,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	159 U32 const mls,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	160 const ZSTD_dictMode_e dictMode)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	161 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	162 const ZSTD_matchState_t * const dms = ms->dictMatchState;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	163 const ZSTD_compressionParameters* const dmsCParams = &dms->cParams;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	164 const U32 * const dictHashTable = dms->hashTable;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	165 U32 const hashLog = dmsCParams->hashLog;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	166 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	167 U32 dictMatchIndex = dictHashTable[h];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	168
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	169 const BYTE* const base = ms->window.base;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	170 const BYTE* const prefixStart = base + ms->window.dictLimit;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	171 U32 const current = (U32)(ip-base);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	172 const BYTE* const dictBase = dms->window.base;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	173 const BYTE* const dictEnd = dms->window.nextSrc;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	174 U32 const dictHighLimit = (U32)(dms->window.nextSrc - dms->window.base);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	175 U32 const dictLowLimit = dms->window.lowLimit;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	176 U32 const dictIndexDelta = ms->window.lowLimit - dictHighLimit;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	177
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	178 U32* const dictBt = dms->chainTable;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	179 U32 const btLog = dmsCParams->chainLog - 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	180 U32 const btMask = (1 << btLog) - 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	181 U32 const btLow = (btMask >= dictHighLimit - dictLowLimit) ? dictLowLimit : dictHighLimit - btMask;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	182
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	183 size_t commonLengthSmaller=0, commonLengthLarger=0;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	184
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	185 (void)dictMode;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	186 assert(dictMode == ZSTD_dictMatchState);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	187
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	188 while (nbCompares-- && (dictMatchIndex > dictLowLimit)) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	189 U32* const nextPtr = dictBt + 2*(dictMatchIndex & btMask);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	190 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	191 const BYTE* match = dictBase + dictMatchIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	192 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	193 if (dictMatchIndex+matchLength >= dictHighLimit)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	194 match = base + dictMatchIndex + dictIndexDelta; /* to prepare for next usage of match[matchLength] */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	195
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	196 if (matchLength > bestLength) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	197 U32 matchIndex = dictMatchIndex + dictIndexDelta;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	198 if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit32(current-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) ) {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	199 DEBUGLOG(9, "ZSTD_DUBT_findBetterDictMatch(%u) : found better match length %u -> %u and offsetCode %u -> %u (dictMatchIndex %u, matchIndex %u)",
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	200 current, (U32)bestLength, (U32)matchLength, (U32)*offsetPtr, ZSTD_REP_MOVE + current - matchIndex, dictMatchIndex, matchIndex);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	201 bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + current - matchIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	202 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	203 if (ip+matchLength == iend) { /* reached end of input : ip[matchLength] is not valid, no way to know if it's larger or smaller than match */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	204 break; /* drop, to guarantee consistency (miss a little bit of compression) */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	205 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	206 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	207
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	208 if (match[matchLength] < ip[matchLength]) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	209 if (dictMatchIndex <= btLow) { break; } /* beyond tree size, stop the search */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	210 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	211 dictMatchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	212 } else {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	213 /* match is larger than current */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	214 if (dictMatchIndex <= btLow) { break; } /* beyond tree size, stop the search */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	215 commonLengthLarger = matchLength;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	216 dictMatchIndex = nextPtr[0];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	217 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	218 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	219
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	220 if (bestLength >= MINMATCH) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	221 U32 const mIndex = current - ((U32)*offsetPtr - ZSTD_REP_MOVE); (void)mIndex;
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	222 DEBUGLOG(8, "ZSTD_DUBT_findBetterDictMatch(%u) : found match of length %u and offsetCode %u (pos %u)",
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	223 current, (U32)bestLength, (U32)*offsetPtr, mIndex);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	224 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	225 return bestLength;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	226
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	227 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	228
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	229
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	230 static size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	231 ZSTD_DUBT_findBestMatch(ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	232 const BYTE* const ip, const BYTE* const iend,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	233 size_t* offsetPtr,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	234 U32 const mls,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	235 const ZSTD_dictMode_e dictMode)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	236 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	237 const ZSTD_compressionParameters* const cParams = &ms->cParams;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	238 U32* const hashTable = ms->hashTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	239 U32 const hashLog = cParams->hashLog;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	240 size_t const h = ZSTD_hashPtr(ip, hashLog, mls);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	241 U32 matchIndex = hashTable[h];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	242
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	243 const BYTE* const base = ms->window.base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	244 U32 const current = (U32)(ip-base);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	245 U32 const windowLow = ZSTD_getLowestMatchIndex(ms, current, cParams->windowLog);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	246
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	247 U32* const bt = ms->chainTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	248 U32 const btLog = cParams->chainLog - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	249 U32 const btMask = (1 << btLog) - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	250 U32 const btLow = (btMask >= current) ? 0 : current - btMask;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	251 U32 const unsortLimit = MAX(btLow, windowLow);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	252
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	253 U32* nextCandidate = bt + 2*(matchIndex&btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	254 U32* unsortedMark = bt + 2*(matchIndex&btMask) + 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	255 U32 nbCompares = 1U << cParams->searchLog;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	256 U32 nbCandidates = nbCompares;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	257 U32 previousCandidate = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	258
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	259 DEBUGLOG(7, "ZSTD_DUBT_findBestMatch (%u) ", current);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	260 assert(ip <= iend-8); /* required for h calculation */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	261
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	262 /* reach end of unsorted candidates list */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	263 while ( (matchIndex > unsortLimit)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	264 && (*unsortedMark == ZSTD_DUBT_UNSORTED_MARK)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	265 && (nbCandidates > 1) ) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	266 DEBUGLOG(8, "ZSTD_DUBT_findBestMatch: candidate %u is unsorted",
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	267 matchIndex);
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	268 unsortedMark = previousCandidate; / the unsortedMark becomes a reversed chain, to move up back to original position */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	269 previousCandidate = matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	270 matchIndex = *nextCandidate;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	271 nextCandidate = bt + 2*(matchIndex&btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	272 unsortedMark = bt + 2*(matchIndex&btMask) + 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	273 nbCandidates --;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	274 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	275
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	276 /* nullify last candidate if it's still unsorted
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	277 * simplification, detrimental to compression ratio, beneficial for speed */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	278 if ( (matchIndex > unsortLimit)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	279 && (*unsortedMark==ZSTD_DUBT_UNSORTED_MARK) ) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	280 DEBUGLOG(7, "ZSTD_DUBT_findBestMatch: nullify last unsorted candidate %u",
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	281 matchIndex);
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	282 nextCandidate = unsortedMark = 0;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	283 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	284
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	285 /* batch sort stacked candidates */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	286 matchIndex = previousCandidate;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	287 while (matchIndex) { /* will end on matchIndex == 0 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	288 U32* const nextCandidateIdxPtr = bt + 2*(matchIndex&btMask) + 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	289 U32 const nextCandidateIdx = *nextCandidateIdxPtr;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	290 ZSTD_insertDUBT1(ms, matchIndex, iend,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	291 nbCandidates, unsortLimit, dictMode);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	292 matchIndex = nextCandidateIdx;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	293 nbCandidates++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	294 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	295
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	296 /* find longest match */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	297 { size_t commonLengthSmaller = 0, commonLengthLarger = 0;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	298 const BYTE* const dictBase = ms->window.dictBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	299 const U32 dictLimit = ms->window.dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	300 const BYTE* const dictEnd = dictBase + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	301 const BYTE* const prefixStart = base + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	302 U32* smallerPtr = bt + 2*(current&btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	303 U32* largerPtr = bt + 2*(current&btMask) + 1;
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	304 U32 matchEndIdx = current + 8 + 1;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	305 U32 dummy32; /* to be nullified at the end */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	306 size_t bestLength = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	307
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	308 matchIndex = hashTable[h];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	309 hashTable[h] = current; /* Update Hash Table */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	310
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	311 while (nbCompares-- && (matchIndex > windowLow)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	312 U32* const nextPtr = bt + 2*(matchIndex & btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	313 size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	314 const BYTE* match;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	315
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	316 if ((dictMode != ZSTD_extDict) \|\| (matchIndex+matchLength >= dictLimit)) {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	317 match = base + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	318 matchLength += ZSTD_count(ip+matchLength, match+matchLength, iend);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	319 } else {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	320 match = dictBase + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	321 matchLength += ZSTD_count_2segments(ip+matchLength, match+matchLength, iend, dictEnd, prefixStart);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	322 if (matchIndex+matchLength >= dictLimit)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	323 match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	324 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	325
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	326 if (matchLength > bestLength) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	327 if (matchLength > matchEndIdx - matchIndex)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	328 matchEndIdx = matchIndex + (U32)matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	329 if ( (4*(int)(matchLength-bestLength)) > (int)(ZSTD_highbit32(current-matchIndex+1) - ZSTD_highbit32((U32)offsetPtr[0]+1)) )
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	330 bestLength = matchLength, *offsetPtr = ZSTD_REP_MOVE + current - matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	331 if (ip+matchLength == iend) { /* equal : no way to know if inf or sup */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	332 if (dictMode == ZSTD_dictMatchState) {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	333 nbCompares = 0; /* in addition to avoiding checking any
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	334 * further in this loop, make sure we
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	335 * skip checking in the dictionary. */
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	336 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	337 break; /* drop, to guarantee consistency (miss a little bit of compression) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	338 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	339 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	340
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	341 if (match[matchLength] < ip[matchLength]) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	342 /* match is smaller than current */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	343 smallerPtr = matchIndex; / update smaller idx */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	344 commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	345 if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	346 smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	347 matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	348 } else {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	349 /* match is larger than current */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	350 *largerPtr = matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	351 commonLengthLarger = matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	352 if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	353 largerPtr = nextPtr;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	354 matchIndex = nextPtr[0];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	355 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	356
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	357 smallerPtr = largerPtr = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	358
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	359 if (dictMode == ZSTD_dictMatchState && nbCompares) {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	360 bestLength = ZSTD_DUBT_findBetterDictMatch(
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	361 ms, ip, iend,
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	362 offsetPtr, bestLength, nbCompares,
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	363 mls, dictMode);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	364 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	365
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	366 assert(matchEndIdx > current+8); /* ensure nextToUpdate is increased */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	367 ms->nextToUpdate = matchEndIdx - 8; /* skip repetitive patterns */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	368 if (bestLength >= MINMATCH) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	369 U32 const mIndex = current - ((U32)*offsetPtr - ZSTD_REP_MOVE); (void)mIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	370 DEBUGLOG(8, "ZSTD_DUBT_findBestMatch(%u) : found match of length %u and offsetCode %u (pos %u)",
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	371 current, (U32)bestLength, (U32)*offsetPtr, mIndex);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	372 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	373 return bestLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	374 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	375 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	376
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	377
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	378 /** ZSTD_BtFindBestMatch() : Tree updater, providing best match */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	379 FORCE_INLINE_TEMPLATE size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	380 ZSTD_BtFindBestMatch( ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	381 const BYTE* const ip, const BYTE* const iLimit,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	382 size_t* offsetPtr,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	383 const U32 mls /* template */,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	384 const ZSTD_dictMode_e dictMode)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	385 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	386 DEBUGLOG(7, "ZSTD_BtFindBestMatch");
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	387 if (ip < ms->window.base + ms->nextToUpdate) return 0; /* skipped area */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	388 ZSTD_updateDUBT(ms, ip, iLimit, mls);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	389 return ZSTD_DUBT_findBestMatch(ms, ip, iLimit, offsetPtr, mls, dictMode);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	390 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	391
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	392
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	393 static size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	394 ZSTD_BtFindBestMatch_selectMLS ( ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	395 const BYTE* ip, const BYTE* const iLimit,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	396 size_t* offsetPtr)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	397 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	398 switch(ms->cParams.minMatch)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	399 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	400 default : /* includes case 3 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	401 case 4 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 4, ZSTD_noDict);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	402 case 5 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 5, ZSTD_noDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	403 case 7 :
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	404 case 6 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 6, ZSTD_noDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	405 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	406 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	407
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	408
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	409 static size_t ZSTD_BtFindBestMatch_dictMatchState_selectMLS (
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	410 ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	411 const BYTE* ip, const BYTE* const iLimit,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	412 size_t* offsetPtr)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	413 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	414 switch(ms->cParams.minMatch)
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	415 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	416 default : /* includes case 3 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	417 case 4 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 4, ZSTD_dictMatchState);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	418 case 5 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 5, ZSTD_dictMatchState);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	419 case 7 :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	420 case 6 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 6, ZSTD_dictMatchState);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	421 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	422 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	423
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	424
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	425 static size_t ZSTD_BtFindBestMatch_extDict_selectMLS (
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	426 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	427 const BYTE* ip, const BYTE* const iLimit,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	428 size_t* offsetPtr)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	429 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	430 switch(ms->cParams.minMatch)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	431 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	432 default : /* includes case 3 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	433 case 4 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 4, ZSTD_extDict);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	434 case 5 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 5, ZSTD_extDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	435 case 7 :
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	436 case 6 : return ZSTD_BtFindBestMatch(ms, ip, iLimit, offsetPtr, 6, ZSTD_extDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	437 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	438 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	439
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	440
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	441
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	442 /* *********************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	443 * Hash Chain
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	444 ***********************************/
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	445 #define NEXT_IN_CHAIN(d, mask) chainTable[(d) & (mask)]
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	446
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	447 /* Update chains up to ip (excluded)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	448 Assumption : always within prefix (i.e. not within extDict) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	449 static U32 ZSTD_insertAndFindFirstIndex_internal(
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	450 ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	451 const ZSTD_compressionParameters* const cParams,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	452 const BYTE* ip, U32 const mls)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	453 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	454 U32* const hashTable = ms->hashTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	455 const U32 hashLog = cParams->hashLog;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	456 U32* const chainTable = ms->chainTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	457 const U32 chainMask = (1 << cParams->chainLog) - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	458 const BYTE* const base = ms->window.base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	459 const U32 target = (U32)(ip - base);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	460 U32 idx = ms->nextToUpdate;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	461
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	462 while(idx < target) { /* catch up */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	463 size_t const h = ZSTD_hashPtr(base+idx, hashLog, mls);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	464 NEXT_IN_CHAIN(idx, chainMask) = hashTable[h];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	465 hashTable[h] = idx;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	466 idx++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	467 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	468
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	469 ms->nextToUpdate = target;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	470 return hashTable[ZSTD_hashPtr(ip, hashLog, mls)];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	471 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	472
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	473 U32 ZSTD_insertAndFindFirstIndex(ZSTD_matchState_t* ms, const BYTE* ip) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	474 const ZSTD_compressionParameters* const cParams = &ms->cParams;
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	475 return ZSTD_insertAndFindFirstIndex_internal(ms, cParams, ip, ms->cParams.minMatch);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	476 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	477
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	478
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	479 /* inlining is important to hardwire a hot branch (template emulation) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	480 FORCE_INLINE_TEMPLATE
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	481 size_t ZSTD_HcFindBestMatch_generic (
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	482 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	483 const BYTE* const ip, const BYTE* const iLimit,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	484 size_t* offsetPtr,
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	485 const U32 mls, const ZSTD_dictMode_e dictMode)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	486 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	487 const ZSTD_compressionParameters* const cParams = &ms->cParams;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	488 U32* const chainTable = ms->chainTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	489 const U32 chainSize = (1 << cParams->chainLog);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	490 const U32 chainMask = chainSize-1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	491 const BYTE* const base = ms->window.base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	492 const BYTE* const dictBase = ms->window.dictBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	493 const U32 dictLimit = ms->window.dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	494 const BYTE* const prefixStart = base + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	495 const BYTE* const dictEnd = dictBase + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	496 const U32 current = (U32)(ip-base);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	497 const U32 maxDistance = 1U << cParams->windowLog;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	498 const U32 lowestValid = ms->window.lowLimit;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	499 const U32 withinMaxDistance = (current - lowestValid > maxDistance) ? current - maxDistance : lowestValid;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	500 const U32 isDictionary = (ms->loadedDictEnd != 0);
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	501 const U32 lowLimit = isDictionary ? lowestValid : withinMaxDistance;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	502 const U32 minChain = current > chainSize ? current - chainSize : 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	503 U32 nbAttempts = 1U << cParams->searchLog;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	504 size_t ml=4-1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	505
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	506 /* HC4 match finder */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	507 U32 matchIndex = ZSTD_insertAndFindFirstIndex_internal(ms, cParams, ip, mls);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	508
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	509 for ( ; (matchIndex>lowLimit) & (nbAttempts>0) ; nbAttempts--) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	510 size_t currentMl=0;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	511 if ((dictMode != ZSTD_extDict) \|\| matchIndex >= dictLimit) {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	512 const BYTE* const match = base + matchIndex;
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	513 assert(matchIndex >= dictLimit); /* ensures this is true if dictMode != ZSTD_extDict */
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	514 if (match[ml] == ip[ml]) /* potentially better */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	515 currentMl = ZSTD_count(ip, match, iLimit);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	516 } else {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	517 const BYTE* const match = dictBase + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	518 assert(match+4 <= dictEnd);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	519 if (MEM_read32(match) == MEM_read32(ip)) /* assumption : matchIndex <= dictLimit-4 (by table construction) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	520 currentMl = ZSTD_count_2segments(ip+4, match+4, iLimit, dictEnd, prefixStart) + 4;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	521 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	522
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	523 /* save best solution */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	524 if (currentMl > ml) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	525 ml = currentMl;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	526 *offsetPtr = current - matchIndex + ZSTD_REP_MOVE;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	527 if (ip+currentMl == iLimit) break; /* best possible, avoids read overflow on next attempt */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	528 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	529
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	530 if (matchIndex <= minChain) break;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	531 matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	532 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	533
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	534 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	535 const ZSTD_matchState_t* const dms = ms->dictMatchState;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	536 const U32* const dmsChainTable = dms->chainTable;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	537 const U32 dmsChainSize = (1 << dms->cParams.chainLog);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	538 const U32 dmsChainMask = dmsChainSize - 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	539 const U32 dmsLowestIndex = dms->window.dictLimit;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	540 const BYTE* const dmsBase = dms->window.base;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	541 const BYTE* const dmsEnd = dms->window.nextSrc;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	542 const U32 dmsSize = (U32)(dmsEnd - dmsBase);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	543 const U32 dmsIndexDelta = dictLimit - dmsSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	544 const U32 dmsMinChain = dmsSize > dmsChainSize ? dmsSize - dmsChainSize : 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	545
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	546 matchIndex = dms->hashTable[ZSTD_hashPtr(ip, dms->cParams.hashLog, mls)];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	547
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	548 for ( ; (matchIndex>dmsLowestIndex) & (nbAttempts>0) ; nbAttempts--) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	549 size_t currentMl=0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	550 const BYTE* const match = dmsBase + matchIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	551 assert(match+4 <= dmsEnd);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	552 if (MEM_read32(match) == MEM_read32(ip)) /* assumption : matchIndex <= dictLimit-4 (by table construction) */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	553 currentMl = ZSTD_count_2segments(ip+4, match+4, iLimit, dmsEnd, prefixStart) + 4;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	554
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	555 /* save best solution */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	556 if (currentMl > ml) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	557 ml = currentMl;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	558 *offsetPtr = current - (matchIndex + dmsIndexDelta) + ZSTD_REP_MOVE;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	559 if (ip+currentMl == iLimit) break; /* best possible, avoids read overflow on next attempt */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	560 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	561
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	562 if (matchIndex <= dmsMinChain) break;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	563 matchIndex = dmsChainTable[matchIndex & dmsChainMask];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	564 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	565 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	566
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	567 return ml;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	568 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	569
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	570
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	571 FORCE_INLINE_TEMPLATE size_t ZSTD_HcFindBestMatch_selectMLS (
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	572 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	573 const BYTE* ip, const BYTE* const iLimit,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	574 size_t* offsetPtr)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	575 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	576 switch(ms->cParams.minMatch)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	577 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	578 default : /* includes case 3 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	579 case 4 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 4, ZSTD_noDict);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	580 case 5 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 5, ZSTD_noDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	581 case 7 :
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	582 case 6 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 6, ZSTD_noDict);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	583 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	584 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	585
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	586
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	587 static size_t ZSTD_HcFindBestMatch_dictMatchState_selectMLS (
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	588 ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	589 const BYTE* ip, const BYTE* const iLimit,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	590 size_t* offsetPtr)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	591 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	592 switch(ms->cParams.minMatch)
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	593 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	594 default : /* includes case 3 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	595 case 4 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 4, ZSTD_dictMatchState);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	596 case 5 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 5, ZSTD_dictMatchState);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	597 case 7 :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	598 case 6 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 6, ZSTD_dictMatchState);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	599 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	600 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	601
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	602
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	603 FORCE_INLINE_TEMPLATE size_t ZSTD_HcFindBestMatch_extDict_selectMLS (
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	604 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	605 const BYTE* ip, const BYTE* const iLimit,
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	606 size_t* offsetPtr)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	607 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	608 switch(ms->cParams.minMatch)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	609 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	610 default : /* includes case 3 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	611 case 4 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 4, ZSTD_extDict);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	612 case 5 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 5, ZSTD_extDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	613 case 7 :
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	614 case 6 : return ZSTD_HcFindBestMatch_generic(ms, ip, iLimit, offsetPtr, 6, ZSTD_extDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	615 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	616 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	617
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	618
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	619 /* *******************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	620 * Common parser - lazy strategy
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	621 *********************************/
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	622 typedef enum { search_hashChain, search_binaryTree } searchMethod_e;
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	623
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	624 FORCE_INLINE_TEMPLATE size_t
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	625 ZSTD_compressBlock_lazy_generic(
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	626 ZSTD_matchState_t* ms, seqStore_t* seqStore,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	627 U32 rep[ZSTD_REP_NUM],
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	628 const void* src, size_t srcSize,
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	629 const searchMethod_e searchMethod, const U32 depth,
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	630 ZSTD_dictMode_e const dictMode)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	631 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	632 const BYTE* const istart = (const BYTE*)src;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	633 const BYTE* ip = istart;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	634 const BYTE* anchor = istart;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	635 const BYTE* const iend = istart + srcSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	636 const BYTE* const ilimit = iend - 8;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	637 const BYTE* const base = ms->window.base;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	638 const U32 prefixLowestIndex = ms->window.dictLimit;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	639 const BYTE* const prefixLowest = base + prefixLowestIndex;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	640
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	641 typedef size_t (*searchMax_f)(
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	642 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	643 const BYTE* ip, const BYTE* iLimit, size_t* offsetPtr);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	644 searchMax_f const searchMax = dictMode == ZSTD_dictMatchState ?
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	645 (searchMethod==search_binaryTree ? ZSTD_BtFindBestMatch_dictMatchState_selectMLS
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	646 : ZSTD_HcFindBestMatch_dictMatchState_selectMLS) :
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	647 (searchMethod==search_binaryTree ? ZSTD_BtFindBestMatch_selectMLS
69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	648 : ZSTD_HcFindBestMatch_selectMLS);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	649 U32 offset_1 = rep[0], offset_2 = rep[1], savedOffset=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	650
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	651 const ZSTD_matchState_t* const dms = ms->dictMatchState;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	652 const U32 dictLowestIndex = dictMode == ZSTD_dictMatchState ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	653 dms->window.dictLimit : 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	654 const BYTE* const dictBase = dictMode == ZSTD_dictMatchState ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	655 dms->window.base : NULL;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	656 const BYTE* const dictLowest = dictMode == ZSTD_dictMatchState ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	657 dictBase + dictLowestIndex : NULL;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	658 const BYTE* const dictEnd = dictMode == ZSTD_dictMatchState ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	659 dms->window.nextSrc : NULL;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	660 const U32 dictIndexDelta = dictMode == ZSTD_dictMatchState ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	661 prefixLowestIndex - (U32)(dictEnd - dictBase) :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	662 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	663 const U32 dictAndPrefixLength = (U32)(ip - prefixLowest + dictEnd - dictLowest);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	664
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	665 /* init */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	666 ip += (dictAndPrefixLength == 0);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	667 if (dictMode == ZSTD_noDict) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	668 U32 const maxRep = (U32)(ip - prefixLowest);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	669 if (offset_2 > maxRep) savedOffset = offset_2, offset_2 = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	670 if (offset_1 > maxRep) savedOffset = offset_1, offset_1 = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	671 }
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	672 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	673 /* dictMatchState repCode checks don't currently handle repCode == 0
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	674 * disabling. */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	675 assert(offset_1 <= dictAndPrefixLength);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	676 assert(offset_2 <= dictAndPrefixLength);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	677 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	678
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	679 /* Match Loop */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	680 while (ip < ilimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	681 size_t matchLength=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	682 size_t offset=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	683 const BYTE* start=ip+1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	684
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	685 /* check repCode */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	686 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	687 const U32 repIndex = (U32)(ip - base) + 1 - offset_1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	688 const BYTE* repMatch = (dictMode == ZSTD_dictMatchState
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	689 && repIndex < prefixLowestIndex) ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	690 dictBase + (repIndex - dictIndexDelta) :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	691 base + repIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	692 if (((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	693 && (MEM_read32(repMatch) == MEM_read32(ip+1)) ) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	694 const BYTE* repMatchEnd = repIndex < prefixLowestIndex ? dictEnd : iend;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	695 matchLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	696 if (depth==0) goto _storeSequence;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	697 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	698 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	699 if ( dictMode == ZSTD_noDict
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	700 && ((offset_1 > 0) & (MEM_read32(ip+1-offset_1) == MEM_read32(ip+1)))) {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	701 matchLength = ZSTD_count(ip+1+4, ip+1+4-offset_1, iend) + 4;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	702 if (depth==0) goto _storeSequence;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	703 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	704
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	705 /* first search (depth 0) */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	706 { size_t offsetFound = 999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	707 size_t const ml2 = searchMax(ms, ip, iend, &offsetFound);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	708 if (ml2 > matchLength)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	709 matchLength = ml2, start = ip, offset=offsetFound;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	710 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	711
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	712 if (matchLength < 4) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	713 ip += ((ip-anchor) >> kSearchStrength) + 1; /* jump faster over incompressible sections */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	714 continue;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	715 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	716
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	717 /* let's try to find a better solution */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	718 if (depth>=1)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	719 while (ip<ilimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	720 ip ++;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	721 if ( (dictMode == ZSTD_noDict)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	722 && (offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	723 size_t const mlRep = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	724 int const gain2 = (int)(mlRep * 3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	725 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	726 if ((mlRep >= 4) && (gain2 > gain1))
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	727 matchLength = mlRep, offset = 0, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	728 }
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	729 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	730 const U32 repIndex = (U32)(ip - base) - offset_1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	731 const BYTE* repMatch = repIndex < prefixLowestIndex ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	732 dictBase + (repIndex - dictIndexDelta) :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	733 base + repIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	734 if (((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	735 && (MEM_read32(repMatch) == MEM_read32(ip)) ) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	736 const BYTE* repMatchEnd = repIndex < prefixLowestIndex ? dictEnd : iend;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	737 size_t const mlRep = ZSTD_count_2segments(ip+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	738 int const gain2 = (int)(mlRep * 3);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	739 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	740 if ((mlRep >= 4) && (gain2 > gain1))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	741 matchLength = mlRep, offset = 0, start = ip;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	742 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	743 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	744 { size_t offset2=999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	745 size_t const ml2 = searchMax(ms, ip, iend, &offset2);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	746 int const gain2 = (int)(ml24 - ZSTD_highbit32((U32)offset2+1)); / raw approx */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	747 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	748 if ((ml2 >= 4) && (gain2 > gain1)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	749 matchLength = ml2, offset = offset2, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	750 continue; /* search a better one */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	751 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	752
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	753 /* let's find an even better one */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	754 if ((depth==2) && (ip<ilimit)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	755 ip ++;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	756 if ( (dictMode == ZSTD_noDict)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	757 && (offset) && ((offset_1>0) & (MEM_read32(ip) == MEM_read32(ip - offset_1)))) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	758 size_t const mlRep = ZSTD_count(ip+4, ip+4-offset_1, iend) + 4;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	759 int const gain2 = (int)(mlRep * 4);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	760 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	761 if ((mlRep >= 4) && (gain2 > gain1))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	762 matchLength = mlRep, offset = 0, start = ip;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	763 }
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	764 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	765 const U32 repIndex = (U32)(ip - base) - offset_1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	766 const BYTE* repMatch = repIndex < prefixLowestIndex ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	767 dictBase + (repIndex - dictIndexDelta) :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	768 base + repIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	769 if (((U32)((prefixLowestIndex-1) - repIndex) >= 3 /* intentional underflow */)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	770 && (MEM_read32(repMatch) == MEM_read32(ip)) ) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	771 const BYTE* repMatchEnd = repIndex < prefixLowestIndex ? dictEnd : iend;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	772 size_t const mlRep = ZSTD_count_2segments(ip+4, repMatch+4, iend, repMatchEnd, prefixLowest) + 4;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	773 int const gain2 = (int)(mlRep * 4);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	774 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	775 if ((mlRep >= 4) && (gain2 > gain1))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	776 matchLength = mlRep, offset = 0, start = ip;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	777 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	778 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	779 { size_t offset2=999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	780 size_t const ml2 = searchMax(ms, ip, iend, &offset2);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	781 int const gain2 = (int)(ml24 - ZSTD_highbit32((U32)offset2+1)); / raw approx */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	782 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	783 if ((ml2 >= 4) && (gain2 > gain1)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	784 matchLength = ml2, offset = offset2, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	785 continue;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	786 } } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	787 break; /* nothing found : store previous solution */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	788 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	789
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	790 /* NOTE:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	791 * start[-offset+ZSTD_REP_MOVE-1] is undefined behavior.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	792 * (-offset+ZSTD_REP_MOVE-1) is unsigned, and is added to start, which
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	793 * overflows the pointer, which is undefined behavior.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	794 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	795 /* catch up */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	796 if (offset) {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	797 if (dictMode == ZSTD_noDict) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	798 while ( ((start > anchor) & (start - (offset-ZSTD_REP_MOVE) > prefixLowest))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	799 && (start[-1] == (start-(offset-ZSTD_REP_MOVE))[-1]) ) /* only search for offset within prefix */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	800 { start--; matchLength++; }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	801 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	802 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	803 U32 const matchIndex = (U32)((start-base) - (offset - ZSTD_REP_MOVE));
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	804 const BYTE* match = (matchIndex < prefixLowestIndex) ? dictBase + matchIndex - dictIndexDelta : base + matchIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	805 const BYTE* const mStart = (matchIndex < prefixLowestIndex) ? dictLowest : prefixLowest;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	806 while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLength++; } /* catch up */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	807 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	808 offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	809 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	810 /* store sequence */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	811 _storeSequence:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	812 { size_t const litLength = start - anchor;
43994 de7838053207 zstandard: vendor python-zstandard 0.13.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 42937 diff changeset	813 ZSTD_storeSeq(seqStore, litLength, anchor, iend, (U32)offset, matchLength-MINMATCH);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	814 anchor = ip = start + matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	815 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	816
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	817 /* check immediate repcode */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	818 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	819 while (ip <= ilimit) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	820 U32 const current2 = (U32)(ip-base);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	821 U32 const repIndex = current2 - offset_2;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	822 const BYTE* repMatch = dictMode == ZSTD_dictMatchState
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	823 && repIndex < prefixLowestIndex ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	824 dictBase - dictIndexDelta + repIndex :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	825 base + repIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	826 if ( ((U32)((prefixLowestIndex-1) - (U32)repIndex) >= 3 /* intentional overflow */)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	827 && (MEM_read32(repMatch) == MEM_read32(ip)) ) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	828 const BYTE* const repEnd2 = repIndex < prefixLowestIndex ? dictEnd : iend;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	829 matchLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd2, prefixLowest) + 4;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	830 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap offset_2 <=> offset_1 */
43994 de7838053207 zstandard: vendor python-zstandard 0.13.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 42937 diff changeset	831 ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, matchLength-MINMATCH);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	832 ip += matchLength;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	833 anchor = ip;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	834 continue;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	835 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	836 break;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	837 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	838 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	839
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	840 if (dictMode == ZSTD_noDict) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	841 while ( ((ip <= ilimit) & (offset_2>0))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	842 && (MEM_read32(ip) == MEM_read32(ip - offset_2)) ) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	843 /* store sequence */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	844 matchLength = ZSTD_count(ip+4, ip+4-offset_2, iend) + 4;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	845 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap repcodes */
43994 de7838053207 zstandard: vendor python-zstandard 0.13.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 42937 diff changeset	846 ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, matchLength-MINMATCH);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	847 ip += matchLength;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	848 anchor = ip;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	849 continue; /* faster when present ... (?) */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	850 } } }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	851
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	852 /* Save reps for next block */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	853 rep[0] = offset_1 ? offset_1 : savedOffset;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	854 rep[1] = offset_2 ? offset_2 : savedOffset;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	855
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	856 /* Return the last literals size */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	857 return (size_t)(iend - anchor);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	858 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	859
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	860
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	861 size_t ZSTD_compressBlock_btlazy2(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	862 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	863 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	864 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	865 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_binaryTree, 2, ZSTD_noDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	866 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	867
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	868 size_t ZSTD_compressBlock_lazy2(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	869 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	870 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	871 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	872 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 2, ZSTD_noDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	873 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	874
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	875 size_t ZSTD_compressBlock_lazy(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	876 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	877 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	878 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	879 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 1, ZSTD_noDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	880 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	881
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	882 size_t ZSTD_compressBlock_greedy(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	883 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	884 void const* src, size_t srcSize)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	885 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	886 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 0, ZSTD_noDict);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	887 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	888
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	889 size_t ZSTD_compressBlock_btlazy2_dictMatchState(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	890 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	891 void const* src, size_t srcSize)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	892 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	893 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_binaryTree, 2, ZSTD_dictMatchState);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	894 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	895
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	896 size_t ZSTD_compressBlock_lazy2_dictMatchState(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	897 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	898 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	899 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	900 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 2, ZSTD_dictMatchState);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	901 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	902
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	903 size_t ZSTD_compressBlock_lazy_dictMatchState(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	904 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	905 void const* src, size_t srcSize)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	906 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	907 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 1, ZSTD_dictMatchState);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	908 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	909
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	910 size_t ZSTD_compressBlock_greedy_dictMatchState(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	911 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	912 void const* src, size_t srcSize)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	913 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	914 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 0, ZSTD_dictMatchState);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	915 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	916
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	917
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	918 FORCE_INLINE_TEMPLATE
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	919 size_t ZSTD_compressBlock_lazy_extDict_generic(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	920 ZSTD_matchState_t* ms, seqStore_t* seqStore,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	921 U32 rep[ZSTD_REP_NUM],
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	922 const void* src, size_t srcSize,
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	923 const searchMethod_e searchMethod, const U32 depth)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	924 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	925 const BYTE* const istart = (const BYTE*)src;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	926 const BYTE* ip = istart;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	927 const BYTE* anchor = istart;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	928 const BYTE* const iend = istart + srcSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	929 const BYTE* const ilimit = iend - 8;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	930 const BYTE* const base = ms->window.base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	931 const U32 dictLimit = ms->window.dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	932 const U32 lowestIndex = ms->window.lowLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	933 const BYTE* const prefixStart = base + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	934 const BYTE* const dictBase = ms->window.dictBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	935 const BYTE* const dictEnd = dictBase + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	936 const BYTE* const dictStart = dictBase + lowestIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	937
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	938 typedef size_t (*searchMax_f)(
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	939 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	940 const BYTE* ip, const BYTE* iLimit, size_t* offsetPtr);
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	941 searchMax_f searchMax = searchMethod==search_binaryTree ? ZSTD_BtFindBestMatch_extDict_selectMLS : ZSTD_HcFindBestMatch_extDict_selectMLS;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	942
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	943 U32 offset_1 = rep[0], offset_2 = rep[1];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	944
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	945 /* init */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	946 ip += (ip == prefixStart);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	947
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	948 /* Match Loop */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	949 while (ip < ilimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	950 size_t matchLength=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	951 size_t offset=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	952 const BYTE* start=ip+1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	953 U32 current = (U32)(ip-base);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	954
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	955 /* check repCode */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	956 { const U32 repIndex = (U32)(current+1 - offset_1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	957 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	958 const BYTE* const repMatch = repBase + repIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	959 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	960 if (MEM_read32(ip+1) == MEM_read32(repMatch)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	961 /* repcode detected we should take it */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	962 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	963 matchLength = ZSTD_count_2segments(ip+1+4, repMatch+4, iend, repEnd, prefixStart) + 4;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	964 if (depth==0) goto _storeSequence;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	965 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	966
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	967 /* first search (depth 0) */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	968 { size_t offsetFound = 999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	969 size_t const ml2 = searchMax(ms, ip, iend, &offsetFound);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	970 if (ml2 > matchLength)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	971 matchLength = ml2, start = ip, offset=offsetFound;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	972 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	973
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	974 if (matchLength < 4) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	975 ip += ((ip-anchor) >> kSearchStrength) + 1; /* jump faster over incompressible sections */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	976 continue;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	977 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	978
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	979 /* let's try to find a better solution */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	980 if (depth>=1)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	981 while (ip<ilimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	982 ip ++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	983 current++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	984 /* check repCode */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	985 if (offset) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	986 const U32 repIndex = (U32)(current - offset_1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	987 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	988 const BYTE* const repMatch = repBase + repIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	989 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	990 if (MEM_read32(ip) == MEM_read32(repMatch)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	991 /* repcode detected */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	992 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	993 size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	994 int const gain2 = (int)(repLength * 3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	995 int const gain1 = (int)(matchLength*3 - ZSTD_highbit32((U32)offset+1) + 1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	996 if ((repLength >= 4) && (gain2 > gain1))
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	997 matchLength = repLength, offset = 0, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	998 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	999
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1000 /* search match, depth 1 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1001 { size_t offset2=999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1002 size_t const ml2 = searchMax(ms, ip, iend, &offset2);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1003 int const gain2 = (int)(ml24 - ZSTD_highbit32((U32)offset2+1)); / raw approx */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1004 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 4);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1005 if ((ml2 >= 4) && (gain2 > gain1)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1006 matchLength = ml2, offset = offset2, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1007 continue; /* search a better one */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1008 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1009
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1010 /* let's find an even better one */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1011 if ((depth==2) && (ip<ilimit)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1012 ip ++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1013 current++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1014 /* check repCode */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1015 if (offset) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1016 const U32 repIndex = (U32)(current - offset_1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1017 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1018 const BYTE* const repMatch = repBase + repIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1019 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1020 if (MEM_read32(ip) == MEM_read32(repMatch)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1021 /* repcode detected */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1022 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1023 size_t const repLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1024 int const gain2 = (int)(repLength * 4);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1025 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1026 if ((repLength >= 4) && (gain2 > gain1))
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1027 matchLength = repLength, offset = 0, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1028 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1029
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1030 /* search match, depth 2 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1031 { size_t offset2=999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1032 size_t const ml2 = searchMax(ms, ip, iend, &offset2);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1033 int const gain2 = (int)(ml24 - ZSTD_highbit32((U32)offset2+1)); / raw approx */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1034 int const gain1 = (int)(matchLength*4 - ZSTD_highbit32((U32)offset+1) + 7);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1035 if ((ml2 >= 4) && (gain2 > gain1)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1036 matchLength = ml2, offset = offset2, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1037 continue;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1038 } } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1039 break; /* nothing found : store previous solution */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1040 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1041
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1042 /* catch up */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1043 if (offset) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1044 U32 const matchIndex = (U32)((start-base) - (offset - ZSTD_REP_MOVE));
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1045 const BYTE* match = (matchIndex < dictLimit) ? dictBase + matchIndex : base + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1046 const BYTE* const mStart = (matchIndex < dictLimit) ? dictStart : prefixStart;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1047 while ((start>anchor) && (match>mStart) && (start[-1] == match[-1])) { start--; match--; matchLength++; } /* catch up */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1048 offset_2 = offset_1; offset_1 = (U32)(offset - ZSTD_REP_MOVE);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1049 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1050
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1051 /* store sequence */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1052 _storeSequence:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1053 { size_t const litLength = start - anchor;
43994 de7838053207 zstandard: vendor python-zstandard 0.13.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 42937 diff changeset	1054 ZSTD_storeSeq(seqStore, litLength, anchor, iend, (U32)offset, matchLength-MINMATCH);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1055 anchor = ip = start + matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1056 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1057
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1058 /* check immediate repcode */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1059 while (ip <= ilimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1060 const U32 repIndex = (U32)((ip-base) - offset_2);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1061 const BYTE* const repBase = repIndex < dictLimit ? dictBase : base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1062 const BYTE* const repMatch = repBase + repIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1063 if (((U32)((dictLimit-1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1064 if (MEM_read32(ip) == MEM_read32(repMatch)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1065 /* repcode detected we should take it */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1066 const BYTE* const repEnd = repIndex < dictLimit ? dictEnd : iend;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1067 matchLength = ZSTD_count_2segments(ip+4, repMatch+4, iend, repEnd, prefixStart) + 4;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1068 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap offset history */
43994 de7838053207 zstandard: vendor python-zstandard 0.13.0 Gregory Szorc <gregory.szorc@gmail.com> parents: 42937 diff changeset	1069 ZSTD_storeSeq(seqStore, 0, anchor, iend, 0, matchLength-MINMATCH);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1070 ip += matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1071 anchor = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1072 continue; /* faster when present ... (?) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1073 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1074 break;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1075 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1076
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1077 /* Save reps for next block */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1078 rep[0] = offset_1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1079 rep[1] = offset_2;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1080
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1081 /* Return the last literals size */
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	1082 return (size_t)(iend - anchor);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1083 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1084
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1085
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1086 size_t ZSTD_compressBlock_greedy_extDict(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1087 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1088 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1089 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	1090 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 0);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1091 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1092
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1093 size_t ZSTD_compressBlock_lazy_extDict(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1094 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1095 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1096
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1097 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	1098 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 1);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1099 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1100
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1101 size_t ZSTD_compressBlock_lazy2_extDict(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1102 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1103 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1104
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1105 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	1106 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_hashChain, 2);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1107 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1108
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1109 size_t ZSTD_compressBlock_btlazy2_extDict(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1110 ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1111 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1112
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1113 {
42937 69de49c4e39c zstandard: vendor python-zstandard 0.12 Gregory Szorc <gregory.szorc@gmail.com> parents: 42070 diff changeset	1114 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, search_binaryTree, 2);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1115 }

Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/compress/zstd_lazy.c @ 45625:c11099cc1de4