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

annotate contrib/python-zstandard/zstd/compress/zstd_lazy.c @ 42070:675775c33ab6

zstandard: vendor python-zstandard 0.11 The upstream source distribution from PyPI was extracted. Unwanted files were removed. The clang-format ignore list was updated to reflect the new source of files. The project contains a vendored copy of zstandard 1.3.8. The old version was 1.3.6. This should result in some minor performance wins. test-check-py3-compat.t was updated to reflect now-passing tests on Python 3.8. Some HTTP tests were updated to reflect new zstd compression output. # no-check-commit because 3rd party code has different style guidelines Differential Revision: https://phab.mercurial-scm.org/D6199

author	Gregory Szorc <gregory.szorc@gmail.com>
date	Thu, 04 Apr 2019 17:34:43 -0700
parents	73fef626dae3
children	69de49c4e39c

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 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	86 U32 const windowLow = ms->window.lowLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	87
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	88 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	89 current, dictLimit, windowLow);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	90 assert(current >= btLow);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	91 assert(ip < iend); /* condition for ZSTD_count */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	92
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	93 while (nbCompares-- && (matchIndex > windowLow)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	94 U32* const nextPtr = bt + 2*(matchIndex & btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	95 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	96 assert(matchIndex < current);
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	97 /* note : all candidates are now supposed sorted,
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	98 * 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	99 * 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	100
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	101 if ( (dictMode != ZSTD_extDict)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	102 \|\| (matchIndex+matchLength >= dictLimit) /* both in current segment*/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	103 \|\| (current < dictLimit) /* both in extDict */) {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	104 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	105 \|\| (matchIndex+matchLength >= dictLimit)) ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	106 base : dictBase;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	107 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	108 \|\| (current < dictLimit) );
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	109 match = mBase + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	110 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	111 } else {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	112 match = dictBase + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	113 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	114 if (matchIndex+matchLength >= dictLimit)
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	115 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	116 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	117
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	118 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	119 current, matchIndex, (U32)matchLength);
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 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	122 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	123 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	124
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	125 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	126 /* match is smaller than current */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	127 smallerPtr = matchIndex; / update smaller idx */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	128 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	129 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	130 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	131 matchIndex, btLow, nextPtr[1]);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	132 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	133 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	134 } else {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	135 /* match is larger than current */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	136 *largerPtr = matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	137 commonLengthLarger = matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	138 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	139 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	140 matchIndex, btLow, nextPtr[0]);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	141 largerPtr = nextPtr;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	142 matchIndex = nextPtr[0];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	143 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	144
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	145 smallerPtr = largerPtr = 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
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	149 static size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	150 ZSTD_DUBT_findBetterDictMatch (
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	151 ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	152 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	153 size_t* offsetPtr,
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	154 size_t bestLength,
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	155 U32 nbCompares,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	156 U32 const mls,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	157 const ZSTD_dictMode_e dictMode)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	158 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	159 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	160 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	161 const U32 * const dictHashTable = dms->hashTable;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	162 U32 const hashLog = dmsCParams->hashLog;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	163 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	164 U32 dictMatchIndex = dictHashTable[h];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	165
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	166 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	167 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	168 U32 const current = (U32)(ip-base);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	169 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	170 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	171 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	172 U32 const dictLowLimit = dms->window.lowLimit;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	173 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	174
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	175 U32* const dictBt = dms->chainTable;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	176 U32 const btLog = dmsCParams->chainLog - 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	177 U32 const btMask = (1 << btLog) - 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	178 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	179
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	180 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	181
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	182 (void)dictMode;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	183 assert(dictMode == ZSTD_dictMatchState);
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 while (nbCompares-- && (dictMatchIndex > dictLowLimit)) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	186 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	187 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	188 const BYTE* match = dictBase + dictMatchIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	189 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	190 if (dictMatchIndex+matchLength >= dictHighLimit)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	191 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	192
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	193 if (matchLength > bestLength) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	194 U32 matchIndex = dictMatchIndex + dictIndexDelta;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	195 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	196 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	197 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	198 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	199 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	200 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	201 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	202 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	203 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	204
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	205 if (match[matchLength] < ip[matchLength]) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	206 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	207 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	208 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	209 } else {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	210 /* match is larger than current */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	211 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	212 commonLengthLarger = matchLength;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	213 dictMatchIndex = nextPtr[0];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	214 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	215 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	216
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	217 if (bestLength >= MINMATCH) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	218 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	219 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	220 current, (U32)bestLength, (U32)*offsetPtr, mIndex);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	221 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	222 return bestLength;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	223
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
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 static size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	228 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	229 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	230 size_t* offsetPtr,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	231 U32 const mls,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	232 const ZSTD_dictMode_e dictMode)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	233 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	234 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	235 U32* const hashTable = ms->hashTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	236 U32 const hashLog = cParams->hashLog;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	237 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	238 U32 matchIndex = hashTable[h];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	239
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	240 const BYTE* const base = ms->window.base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	241 U32 const current = (U32)(ip-base);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	242 U32 const windowLow = ms->window.lowLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	243
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	244 U32* const bt = ms->chainTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	245 U32 const btLog = cParams->chainLog - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	246 U32 const btMask = (1 << btLog) - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	247 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	248 U32 const unsortLimit = MAX(btLow, windowLow);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	249
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	250 U32* nextCandidate = bt + 2*(matchIndex&btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	251 U32* unsortedMark = bt + 2*(matchIndex&btMask) + 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	252 U32 nbCompares = 1U << cParams->searchLog;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	253 U32 nbCandidates = nbCompares;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	254 U32 previousCandidate = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	255
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	256 DEBUGLOG(7, "ZSTD_DUBT_findBestMatch (%u) ", current);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	257 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	258
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	259 /* reach end of unsorted candidates list */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	260 while ( (matchIndex > unsortLimit)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	261 && (*unsortedMark == ZSTD_DUBT_UNSORTED_MARK)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	262 && (nbCandidates > 1) ) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	263 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	264 matchIndex);
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	265 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	266 previousCandidate = matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	267 matchIndex = *nextCandidate;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	268 nextCandidate = bt + 2*(matchIndex&btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	269 unsortedMark = bt + 2*(matchIndex&btMask) + 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	270 nbCandidates --;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	271 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	272
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	273 /* 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	274 * 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	275 if ( (matchIndex > unsortLimit)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	276 && (*unsortedMark==ZSTD_DUBT_UNSORTED_MARK) ) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	277 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	278 matchIndex);
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	279 nextCandidate = unsortedMark = 0;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	280 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	281
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	282 /* batch sort stacked candidates */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	283 matchIndex = previousCandidate;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	284 while (matchIndex) { /* will end on matchIndex == 0 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	285 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	286 U32 const nextCandidateIdx = *nextCandidateIdxPtr;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	287 ZSTD_insertDUBT1(ms, matchIndex, iend,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	288 nbCandidates, unsortLimit, dictMode);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	289 matchIndex = nextCandidateIdx;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	290 nbCandidates++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	291 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	292
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	293 /* find longest match */
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	294 { size_t commonLengthSmaller = 0, commonLengthLarger = 0;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	295 const BYTE* const dictBase = ms->window.dictBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	296 const U32 dictLimit = ms->window.dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	297 const BYTE* const dictEnd = dictBase + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	298 const BYTE* const prefixStart = base + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	299 U32* smallerPtr = bt + 2*(current&btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	300 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	301 U32 matchEndIdx = current + 8 + 1;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	302 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	303 size_t bestLength = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	304
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	305 matchIndex = hashTable[h];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	306 hashTable[h] = current; /* Update Hash Table */
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 while (nbCompares-- && (matchIndex > windowLow)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	309 U32* const nextPtr = bt + 2*(matchIndex & btMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	310 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	311 const BYTE* match;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	312
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	313 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	314 match = base + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	315 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	316 } else {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	317 match = dictBase + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	318 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	319 if (matchIndex+matchLength >= dictLimit)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	320 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	321 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	322
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	323 if (matchLength > bestLength) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	324 if (matchLength > matchEndIdx - matchIndex)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	325 matchEndIdx = matchIndex + (U32)matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	326 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	327 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	328 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	329 if (dictMode == ZSTD_dictMatchState) {
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	330 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	331 * further in this loop, make sure we
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	332 * skip checking in the dictionary. */
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	333 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	334 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	335 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	336 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	337
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	338 if (match[matchLength] < ip[matchLength]) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	339 /* match is smaller than current */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	340 smallerPtr = matchIndex; / update smaller idx */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	341 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	342 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	343 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	344 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	345 } else {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	346 /* match is larger than current */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	347 *largerPtr = matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	348 commonLengthLarger = matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	349 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	350 largerPtr = nextPtr;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	351 matchIndex = nextPtr[0];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	352 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	353
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	354 smallerPtr = largerPtr = 0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	355
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	356 if (dictMode == ZSTD_dictMatchState && nbCompares) {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	357 bestLength = ZSTD_DUBT_findBetterDictMatch(
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	358 ms, ip, iend,
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	359 offsetPtr, bestLength, nbCompares,
675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	360 mls, dictMode);
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	361 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	362
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	363 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	364 ms->nextToUpdate = matchEndIdx - 8; /* skip repetitive patterns */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	365 if (bestLength >= MINMATCH) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	366 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	367 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	368 current, (U32)bestLength, (U32)*offsetPtr, mIndex);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	369 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	370 return bestLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	371 }
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
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 /** 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	376 FORCE_INLINE_TEMPLATE size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	377 ZSTD_BtFindBestMatch( ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	378 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	379 size_t* offsetPtr,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	380 const U32 mls /* template */,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	381 const ZSTD_dictMode_e dictMode)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	382 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	383 DEBUGLOG(7, "ZSTD_BtFindBestMatch");
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	384 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	385 ZSTD_updateDUBT(ms, ip, iLimit, mls);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	386 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	387 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	388
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	389
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	390 static size_t
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	391 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	392 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	393 size_t* offsetPtr)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	394 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	395 switch(ms->cParams.minMatch)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	396 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	397 default : /* includes case 3 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	398 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	399 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	400 case 7 :
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	401 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	402 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	403 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	404
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	405
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	406 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	407 ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	408 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	409 size_t* offsetPtr)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	410 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	411 switch(ms->cParams.minMatch)
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	412 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	413 default : /* includes case 3 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	414 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	415 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	416 case 7 :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	417 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	418 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	419 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	420
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	421
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	422 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	423 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	424 const BYTE* ip, const BYTE* const iLimit,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	425 size_t* offsetPtr)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	426 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	427 switch(ms->cParams.minMatch)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	428 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	429 default : /* includes case 3 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	430 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	431 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	432 case 7 :
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	433 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	434 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	435 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	436
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 * Hash Chain
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	441 ***********************************/
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	442 #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	443
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	444 /* Update chains up to ip (excluded)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	445 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	446 static U32 ZSTD_insertAndFindFirstIndex_internal(
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	447 ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	448 const ZSTD_compressionParameters* const cParams,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	449 const BYTE* ip, U32 const mls)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	450 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	451 U32* const hashTable = ms->hashTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	452 const U32 hashLog = cParams->hashLog;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	453 U32* const chainTable = ms->chainTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	454 const U32 chainMask = (1 << cParams->chainLog) - 1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	455 const BYTE* const base = ms->window.base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	456 const U32 target = (U32)(ip - base);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	457 U32 idx = ms->nextToUpdate;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	458
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	459 while(idx < target) { /* catch up */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	460 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	461 NEXT_IN_CHAIN(idx, chainMask) = hashTable[h];
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	462 hashTable[h] = idx;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	463 idx++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	464 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	465
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	466 ms->nextToUpdate = target;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	467 return hashTable[ZSTD_hashPtr(ip, hashLog, mls)];
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
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	470 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	471 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	472 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	473 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	474
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	475
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	476 /* 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	477 FORCE_INLINE_TEMPLATE
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	478 size_t ZSTD_HcFindBestMatch_generic (
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	479 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	480 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	481 size_t* offsetPtr,
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	482 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	483 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	484 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	485 U32* const chainTable = ms->chainTable;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	486 const U32 chainSize = (1 << cParams->chainLog);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	487 const U32 chainMask = chainSize-1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	488 const BYTE* const base = ms->window.base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	489 const BYTE* const dictBase = ms->window.dictBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	490 const U32 dictLimit = ms->window.dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	491 const BYTE* const prefixStart = base + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	492 const BYTE* const dictEnd = dictBase + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	493 const U32 lowLimit = ms->window.lowLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	494 const U32 current = (U32)(ip-base);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	495 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	496 U32 nbAttempts = 1U << cParams->searchLog;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	497 size_t ml=4-1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	498
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	499 /* HC4 match finder */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	500 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	501
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	502 for ( ; (matchIndex>lowLimit) & (nbAttempts>0) ; nbAttempts--) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	503 size_t currentMl=0;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	504 if ((dictMode != ZSTD_extDict) \|\| matchIndex >= dictLimit) {
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	505 const BYTE* const match = base + matchIndex;
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	506 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	507 if (match[ml] == ip[ml]) /* potentially better */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	508 currentMl = ZSTD_count(ip, match, iLimit);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	509 } else {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	510 const BYTE* const match = dictBase + matchIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	511 assert(match+4 <= dictEnd);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	512 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	513 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	514 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	515
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	516 /* save best solution */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	517 if (currentMl > ml) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	518 ml = currentMl;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	519 *offsetPtr = current - matchIndex + ZSTD_REP_MOVE;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	520 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	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 if (matchIndex <= minChain) break;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	524 matchIndex = NEXT_IN_CHAIN(matchIndex, chainMask);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	525 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	526
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	527 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	528 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	529 const U32* const dmsChainTable = dms->chainTable;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	530 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	531 const U32 dmsChainMask = dmsChainSize - 1;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	532 const U32 dmsLowestIndex = dms->window.dictLimit;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	533 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	534 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	535 const U32 dmsSize = (U32)(dmsEnd - dmsBase);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	536 const U32 dmsIndexDelta = dictLimit - dmsSize;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	537 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	538
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	539 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	540
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	541 for ( ; (matchIndex>dmsLowestIndex) & (nbAttempts>0) ; nbAttempts--) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	542 size_t currentMl=0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	543 const BYTE* const match = dmsBase + matchIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	544 assert(match+4 <= dmsEnd);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	545 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	546 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	547
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	548 /* save best solution */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	549 if (currentMl > ml) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	550 ml = currentMl;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	551 *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	552 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	553 }
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 if (matchIndex <= dmsMinChain) break;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	556 matchIndex = dmsChainTable[matchIndex & dmsChainMask];
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	557 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	558 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	559
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	560 return ml;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	561 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	562
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	563
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	564 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	565 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	566 const BYTE* ip, const BYTE* const iLimit,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	567 size_t* offsetPtr)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	568 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	569 switch(ms->cParams.minMatch)
37495 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 default : /* includes case 3 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	572 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	573 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	574 case 7 :
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	575 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	576 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	577 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	578
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	579
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	580 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	581 ZSTD_matchState_t* ms,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	582 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	583 size_t* offsetPtr)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	584 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	585 switch(ms->cParams.minMatch)
40121 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 default : /* includes case 3 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	588 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	589 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	590 case 7 :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	591 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	592 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	593 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	594
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	595
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	596 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	597 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	598 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	599 size_t* offsetPtr)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	600 {
42070 675775c33ab6 zstandard: vendor python-zstandard 0.11 Gregory Szorc <gregory.szorc@gmail.com> parents: 40121 diff changeset	601 switch(ms->cParams.minMatch)
37495 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 default : /* includes case 3 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	604 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	605 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	606 case 7 :
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	607 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	608 }
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
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	611
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	612 /* *******************************
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	613 * Common parser - lazy strategy
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	614 *********************************/
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	615 FORCE_INLINE_TEMPLATE
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	616 size_t ZSTD_compressBlock_lazy_generic(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	617 ZSTD_matchState_t* ms, seqStore_t* seqStore,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	618 U32 rep[ZSTD_REP_NUM],
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	619 const void* src, size_t srcSize,
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	620 const U32 searchMethod, const U32 depth,
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	621 ZSTD_dictMode_e const dictMode)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	622 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	623 const BYTE* const istart = (const BYTE*)src;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	624 const BYTE* ip = istart;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	625 const BYTE* anchor = istart;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	626 const BYTE* const iend = istart + srcSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	627 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	628 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	629 const U32 prefixLowestIndex = ms->window.dictLimit;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	630 const BYTE* const prefixLowest = base + prefixLowestIndex;
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 typedef size_t (*searchMax_f)(
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	633 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	634 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	635 searchMax_f const searchMax = dictMode == ZSTD_dictMatchState ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	636 (searchMethod ? ZSTD_BtFindBestMatch_dictMatchState_selectMLS : ZSTD_HcFindBestMatch_dictMatchState_selectMLS) :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	637 (searchMethod ? ZSTD_BtFindBestMatch_selectMLS : ZSTD_HcFindBestMatch_selectMLS);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	638 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	639
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	640 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	641 const U32 dictLowestIndex = dictMode == ZSTD_dictMatchState ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	642 dms->window.dictLimit : 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	643 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	644 dms->window.base : NULL;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	645 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	646 dictBase + dictLowestIndex : NULL;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	647 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	648 dms->window.nextSrc : NULL;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	649 const U32 dictIndexDelta = dictMode == ZSTD_dictMatchState ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	650 prefixLowestIndex - (U32)(dictEnd - dictBase) :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	651 0;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	652 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	653
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	654 /* init */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	655 ip += (dictAndPrefixLength == 0);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	656 ms->nextToUpdate3 = ms->nextToUpdate;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	657 if (dictMode == ZSTD_noDict) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	658 U32 const maxRep = (U32)(ip - prefixLowest);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	659 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	660 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	661 }
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	662 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	663 /* 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	664 * disabling. */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	665 assert(offset_1 <= dictAndPrefixLength);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	666 assert(offset_2 <= dictAndPrefixLength);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	667 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	668
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	669 /* Match Loop */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	670 while (ip < ilimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	671 size_t matchLength=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	672 size_t offset=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	673 const BYTE* start=ip+1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	674
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	675 /* check repCode */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	676 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	677 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	678 const BYTE* repMatch = (dictMode == ZSTD_dictMatchState
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	679 && repIndex < prefixLowestIndex) ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	680 dictBase + (repIndex - dictIndexDelta) :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	681 base + repIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	682 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	683 && (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	684 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	685 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	686 if (depth==0) goto _storeSequence;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	687 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	688 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	689 if ( dictMode == ZSTD_noDict
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	690 && ((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	691 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	692 if (depth==0) goto _storeSequence;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	693 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	694
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	695 /* first search (depth 0) */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	696 { size_t offsetFound = 999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	697 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	698 if (ml2 > matchLength)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	699 matchLength = ml2, start = ip, offset=offsetFound;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	700 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	701
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	702 if (matchLength < 4) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	703 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	704 continue;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	705 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	706
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	707 /* 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	708 if (depth>=1)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	709 while (ip<ilimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	710 ip ++;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	711 if ( (dictMode == ZSTD_noDict)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	712 && (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	713 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	714 int const gain2 = (int)(mlRep * 3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	715 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	716 if ((mlRep >= 4) && (gain2 > gain1))
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	717 matchLength = mlRep, offset = 0, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	718 }
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	719 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	720 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	721 const BYTE* repMatch = repIndex < prefixLowestIndex ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	722 dictBase + (repIndex - dictIndexDelta) :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	723 base + repIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	724 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	725 && (MEM_read32(repMatch) == MEM_read32(ip)) ) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	726 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	727 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	728 int const gain2 = (int)(mlRep * 3);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	729 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	730 if ((mlRep >= 4) && (gain2 > gain1))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	731 matchLength = mlRep, offset = 0, start = ip;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	732 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	733 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	734 { size_t offset2=999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	735 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	736 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	737 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	738 if ((ml2 >= 4) && (gain2 > gain1)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	739 matchLength = ml2, offset = offset2, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	740 continue; /* search a better one */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	741 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	742
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	743 /* let's find an even better one */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	744 if ((depth==2) && (ip<ilimit)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	745 ip ++;
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	746 if ( (dictMode == ZSTD_noDict)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	747 && (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	748 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	749 int const gain2 = (int)(mlRep * 4);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	750 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	751 if ((mlRep >= 4) && (gain2 > gain1))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	752 matchLength = mlRep, offset = 0, start = ip;
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	753 }
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	754 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	755 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	756 const BYTE* repMatch = repIndex < prefixLowestIndex ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	757 dictBase + (repIndex - dictIndexDelta) :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	758 base + repIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	759 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	760 && (MEM_read32(repMatch) == MEM_read32(ip)) ) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	761 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	762 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	763 int const gain2 = (int)(mlRep * 4);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	764 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	765 if ((mlRep >= 4) && (gain2 > gain1))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	766 matchLength = mlRep, offset = 0, start = ip;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	767 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	768 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	769 { size_t offset2=999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	770 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	771 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	772 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	773 if ((ml2 >= 4) && (gain2 > gain1)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	774 matchLength = ml2, offset = offset2, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	775 continue;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	776 } } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	777 break; /* nothing found : store previous solution */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	778 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	779
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	780 /* NOTE:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	781 * 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	782 * (-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	783 * overflows the pointer, which is undefined behavior.
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	784 */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	785 /* catch up */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	786 if (offset) {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	787 if (dictMode == ZSTD_noDict) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	788 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	789 && (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	790 { start--; matchLength++; }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	791 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	792 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	793 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	794 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	795 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	796 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	797 }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	798 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	799 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	800 /* store sequence */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	801 _storeSequence:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	802 { size_t const litLength = start - anchor;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	803 ZSTD_storeSeq(seqStore, litLength, anchor, (U32)offset, matchLength-MINMATCH);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	804 anchor = ip = start + matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	805 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	806
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	807 /* check immediate repcode */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	808 if (dictMode == ZSTD_dictMatchState) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	809 while (ip <= ilimit) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	810 U32 const current2 = (U32)(ip-base);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	811 U32 const repIndex = current2 - offset_2;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	812 const BYTE* repMatch = dictMode == ZSTD_dictMatchState
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	813 && repIndex < prefixLowestIndex ?
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	814 dictBase - dictIndexDelta + repIndex :
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	815 base + repIndex;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	816 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	817 && (MEM_read32(repMatch) == MEM_read32(ip)) ) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	818 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	819 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	820 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap offset_2 <=> offset_1 */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	821 ZSTD_storeSeq(seqStore, 0, anchor, 0, matchLength-MINMATCH);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	822 ip += matchLength;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	823 anchor = ip;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	824 continue;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	825 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	826 break;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	827 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	828 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	829
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	830 if (dictMode == ZSTD_noDict) {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	831 while ( ((ip <= ilimit) & (offset_2>0))
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	832 && (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	833 /* store sequence */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	834 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	835 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap repcodes */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	836 ZSTD_storeSeq(seqStore, 0, anchor, 0, matchLength-MINMATCH);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	837 ip += matchLength;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	838 anchor = ip;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	839 continue; /* faster when present ... (?) */
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	840 } } }
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	841
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	842 /* Save reps for next block */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	843 rep[0] = offset_1 ? offset_1 : savedOffset;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	844 rep[1] = offset_2 ? offset_2 : savedOffset;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	845
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	846 /* Return the last literals size */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	847 return iend - anchor;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	848 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	849
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	850
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	851 size_t ZSTD_compressBlock_btlazy2(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	852 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	853 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	854 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	855 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 1, 2, ZSTD_noDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	856 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	857
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	858 size_t ZSTD_compressBlock_lazy2(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	859 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	860 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	861 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	862 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 2, ZSTD_noDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	863 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	864
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	865 size_t ZSTD_compressBlock_lazy(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	866 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	867 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	868 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	869 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 1, ZSTD_noDict);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	870 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	871
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	872 size_t ZSTD_compressBlock_greedy(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	873 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	874 void const* src, size_t srcSize)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	875 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	876 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 0, ZSTD_noDict);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	877 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	878
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	879 size_t ZSTD_compressBlock_btlazy2_dictMatchState(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	880 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	881 void const* src, size_t srcSize)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	882 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	883 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 1, 2, ZSTD_dictMatchState);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	884 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	885
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	886 size_t ZSTD_compressBlock_lazy2_dictMatchState(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	887 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	888 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	889 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	890 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 2, ZSTD_dictMatchState);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	891 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	892
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	893 size_t ZSTD_compressBlock_lazy_dictMatchState(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	894 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	895 void const* src, size_t srcSize)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	896 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	897 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 1, ZSTD_dictMatchState);
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	898 }
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	899
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	900 size_t ZSTD_compressBlock_greedy_dictMatchState(
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	901 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	902 void const* src, size_t srcSize)
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	903 {
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	904 return ZSTD_compressBlock_lazy_generic(ms, seqStore, rep, src, srcSize, 0, 0, ZSTD_dictMatchState);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	905 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	906
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	907
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	908 FORCE_INLINE_TEMPLATE
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	909 size_t ZSTD_compressBlock_lazy_extDict_generic(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	910 ZSTD_matchState_t* ms, seqStore_t* seqStore,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	911 U32 rep[ZSTD_REP_NUM],
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	912 const void* src, size_t srcSize,
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	913 const U32 searchMethod, const U32 depth)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	914 {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	915 const BYTE* const istart = (const BYTE*)src;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	916 const BYTE* ip = istart;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	917 const BYTE* anchor = istart;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	918 const BYTE* const iend = istart + srcSize;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	919 const BYTE* const ilimit = iend - 8;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	920 const BYTE* const base = ms->window.base;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	921 const U32 dictLimit = ms->window.dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	922 const U32 lowestIndex = ms->window.lowLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	923 const BYTE* const prefixStart = base + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	924 const BYTE* const dictBase = ms->window.dictBase;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	925 const BYTE* const dictEnd = dictBase + dictLimit;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	926 const BYTE* const dictStart = dictBase + lowestIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	927
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	928 typedef size_t (*searchMax_f)(
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	929 ZSTD_matchState_t* ms,
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	930 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	931 searchMax_f searchMax = searchMethod ? 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	932
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	933 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	934
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	935 /* init */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	936 ms->nextToUpdate3 = ms->nextToUpdate;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	937 ip += (ip == prefixStart);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	938
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	939 /* Match Loop */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	940 while (ip < ilimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	941 size_t matchLength=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	942 size_t offset=0;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	943 const BYTE* start=ip+1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	944 U32 current = (U32)(ip-base);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	945
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	946 /* check repCode */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	947 { 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	948 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	949 const BYTE* const repMatch = repBase + repIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	950 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	951 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	952 /* repcode detected we should take it */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	953 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	954 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	955 if (depth==0) goto _storeSequence;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	956 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	957
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	958 /* first search (depth 0) */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	959 { size_t offsetFound = 999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	960 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	961 if (ml2 > matchLength)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	962 matchLength = ml2, start = ip, offset=offsetFound;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	963 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	964
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	965 if (matchLength < 4) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	966 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	967 continue;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	968 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	969
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	970 /* 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	971 if (depth>=1)
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	972 while (ip<ilimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	973 ip ++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	974 current++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	975 /* check repCode */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	976 if (offset) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	977 const U32 repIndex = (U32)(current - offset_1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	978 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	979 const BYTE* const repMatch = repBase + repIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	980 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	981 if (MEM_read32(ip) == MEM_read32(repMatch)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	982 /* repcode detected */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	983 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	984 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	985 int const gain2 = (int)(repLength * 3);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	986 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	987 if ((repLength >= 4) && (gain2 > gain1))
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	988 matchLength = repLength, offset = 0, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	989 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	990
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	991 /* search match, depth 1 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	992 { size_t offset2=999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	993 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	994 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	995 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	996 if ((ml2 >= 4) && (gain2 > gain1)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	997 matchLength = ml2, offset = offset2, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	998 continue; /* search a better one */
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
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1001 /* let's find an even better one */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1002 if ((depth==2) && (ip<ilimit)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1003 ip ++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1004 current++;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1005 /* check repCode */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1006 if (offset) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1007 const U32 repIndex = (U32)(current - offset_1);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1008 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	1009 const BYTE* const repMatch = repBase + repIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1010 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	1011 if (MEM_read32(ip) == MEM_read32(repMatch)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1012 /* repcode detected */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1013 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	1014 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	1015 int const gain2 = (int)(repLength * 4);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1016 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	1017 if ((repLength >= 4) && (gain2 > gain1))
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1018 matchLength = repLength, offset = 0, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1019 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1020
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1021 /* search match, depth 2 */
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1022 { size_t offset2=999999999;
73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1023 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	1024 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	1025 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	1026 if ((ml2 >= 4) && (gain2 > gain1)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1027 matchLength = ml2, offset = offset2, start = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1028 continue;
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 break; /* nothing found : store previous solution */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1031 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1032
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1033 /* catch up */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1034 if (offset) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1035 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	1036 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	1037 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	1038 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	1039 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	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 /* store sequence */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1043 _storeSequence:
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1044 { size_t const litLength = start - anchor;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1045 ZSTD_storeSeq(seqStore, litLength, anchor, (U32)offset, matchLength-MINMATCH);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1046 anchor = ip = start + matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1047 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1048
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1049 /* check immediate repcode */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1050 while (ip <= ilimit) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1051 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	1052 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	1053 const BYTE* const repMatch = repBase + repIndex;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1054 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	1055 if (MEM_read32(ip) == MEM_read32(repMatch)) {
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1056 /* repcode detected we should take it */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1057 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	1058 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	1059 offset = offset_2; offset_2 = offset_1; offset_1 = (U32)offset; /* swap offset history */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1060 ZSTD_storeSeq(seqStore, 0, anchor, 0, matchLength-MINMATCH);
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1061 ip += matchLength;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1062 anchor = ip;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1063 continue; /* faster when present ... (?) */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1064 }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1065 break;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1066 } }
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1067
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1068 /* Save reps for next block */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1069 rep[0] = offset_1;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1070 rep[1] = offset_2;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1071
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1072 /* Return the last literals size */
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1073 return iend - anchor;
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1074 }
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 size_t ZSTD_compressBlock_greedy_extDict(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1078 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	1079 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1080 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1081 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 0, 0);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1082 }
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 size_t ZSTD_compressBlock_lazy_extDict(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1085 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	1086 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1087
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1088 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1089 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 0, 1);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1090 }
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 size_t ZSTD_compressBlock_lazy2_extDict(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1093 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	1094 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1095
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1096 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1097 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 0, 2);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1098 }
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 size_t ZSTD_compressBlock_btlazy2_extDict(
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1101 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	1102 void const* src, size_t srcSize)
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1103
b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1104 {
40121 73fef626dae3 zstandard: vendor python-zstandard 0.10.1 Gregory Szorc <gregory.szorc@gmail.com> parents: 37495 diff changeset	1105 return ZSTD_compressBlock_lazy_extDict_generic(ms, seqStore, rep, src, srcSize, 1, 2);
37495 b1fb341d8a61 zstandard: vendor python-zstandard 0.9.0 Gregory Szorc <gregory.szorc@gmail.com> parents: diff changeset	1106 }

Mercurial > public > mercurial-scm > hg

annotate contrib/python-zstandard/zstd/compress/zstd_lazy.c @ 42070:675775c33ab6