^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /**
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) * Copyright (c) 2016-present, Przemyslaw Skibinski, Yann Collet, Facebook, Inc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) * All rights reserved.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) * This source code is licensed under the BSD-style license found in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) * LICENSE file in the root directory of https://github.com/facebook/zstd.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) * An additional grant of patent rights can be found in the PATENTS file in the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) * same directory.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) * This program is free software; you can redistribute it and/or modify it under
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) * the terms of the GNU General Public License version 2 as published by the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) * Free Software Foundation. This program is dual-licensed; you may select
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) * either version 2 of the GNU General Public License ("GPL") or BSD license
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) * ("BSD").
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) /* Note : this file is intended to be included within zstd_compress.c */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) #ifndef ZSTD_OPT_H_91842398743
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) #define ZSTD_OPT_H_91842398743
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) #define ZSTD_LITFREQ_ADD 2
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) #define ZSTD_FREQ_DIV 4
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) #define ZSTD_MAX_PRICE (1 << 30)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) /*-*************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) * Price functions for optimal parser
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) ***************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) FORCE_INLINE void ZSTD_setLog2Prices(seqStore_t *ssPtr)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) ssPtr->log2matchLengthSum = ZSTD_highbit32(ssPtr->matchLengthSum + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) ssPtr->log2litLengthSum = ZSTD_highbit32(ssPtr->litLengthSum + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) ssPtr->log2litSum = ZSTD_highbit32(ssPtr->litSum + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) ssPtr->log2offCodeSum = ZSTD_highbit32(ssPtr->offCodeSum + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) ssPtr->factor = 1 + ((ssPtr->litSum >> 5) / ssPtr->litLengthSum) + ((ssPtr->litSum << 1) / (ssPtr->litSum + ssPtr->matchSum));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) ZSTD_STATIC void ZSTD_rescaleFreqs(seqStore_t *ssPtr, const BYTE *src, size_t srcSize)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) unsigned u;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) ssPtr->cachedLiterals = NULL;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) ssPtr->cachedPrice = ssPtr->cachedLitLength = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) ssPtr->staticPrices = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) if (ssPtr->litLengthSum == 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) if (srcSize <= 1024)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) ssPtr->staticPrices = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) for (u = 0; u <= MaxLit; u++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) ssPtr->litFreq[u] = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) for (u = 0; u < srcSize; u++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) ssPtr->litFreq[src[u]]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) ssPtr->litSum = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) ssPtr->litLengthSum = MaxLL + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) ssPtr->matchLengthSum = MaxML + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) ssPtr->offCodeSum = (MaxOff + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) ssPtr->matchSum = (ZSTD_LITFREQ_ADD << Litbits);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) for (u = 0; u <= MaxLit; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) ssPtr->litFreq[u] = 1 + (ssPtr->litFreq[u] >> ZSTD_FREQ_DIV);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) ssPtr->litSum += ssPtr->litFreq[u];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) for (u = 0; u <= MaxLL; u++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) ssPtr->litLengthFreq[u] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) for (u = 0; u <= MaxML; u++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) ssPtr->matchLengthFreq[u] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69) for (u = 0; u <= MaxOff; u++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) ssPtr->offCodeFreq[u] = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) ssPtr->matchLengthSum = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) ssPtr->litLengthSum = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) ssPtr->offCodeSum = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) ssPtr->matchSum = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) ssPtr->litSum = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78) for (u = 0; u <= MaxLit; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) ssPtr->litFreq[u] = 1 + (ssPtr->litFreq[u] >> (ZSTD_FREQ_DIV + 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) ssPtr->litSum += ssPtr->litFreq[u];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) for (u = 0; u <= MaxLL; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) ssPtr->litLengthFreq[u] = 1 + (ssPtr->litLengthFreq[u] >> (ZSTD_FREQ_DIV + 1));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84) ssPtr->litLengthSum += ssPtr->litLengthFreq[u];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) for (u = 0; u <= MaxML; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87) ssPtr->matchLengthFreq[u] = 1 + (ssPtr->matchLengthFreq[u] >> ZSTD_FREQ_DIV);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) ssPtr->matchLengthSum += ssPtr->matchLengthFreq[u];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) ssPtr->matchSum += ssPtr->matchLengthFreq[u] * (u + 3);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) ssPtr->matchSum *= ZSTD_LITFREQ_ADD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) for (u = 0; u <= MaxOff; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) ssPtr->offCodeFreq[u] = 1 + (ssPtr->offCodeFreq[u] >> ZSTD_FREQ_DIV);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) ssPtr->offCodeSum += ssPtr->offCodeFreq[u];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) ZSTD_setLog2Prices(ssPtr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) FORCE_INLINE U32 ZSTD_getLiteralPrice(seqStore_t *ssPtr, U32 litLength, const BYTE *literals)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) U32 price, u;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) if (ssPtr->staticPrices)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) return ZSTD_highbit32((U32)litLength + 1) + (litLength * 6);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) if (litLength == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) return ssPtr->log2litLengthSum - ZSTD_highbit32(ssPtr->litLengthFreq[0] + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) /* literals */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112) if (ssPtr->cachedLiterals == literals) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) U32 const additional = litLength - ssPtr->cachedLitLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) const BYTE *literals2 = ssPtr->cachedLiterals + ssPtr->cachedLitLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) price = ssPtr->cachedPrice + additional * ssPtr->log2litSum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) for (u = 0; u < additional; u++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117) price -= ZSTD_highbit32(ssPtr->litFreq[literals2[u]] + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) ssPtr->cachedPrice = price;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) ssPtr->cachedLitLength = litLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) price = litLength * ssPtr->log2litSum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) for (u = 0; u < litLength; u++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123) price -= ZSTD_highbit32(ssPtr->litFreq[literals[u]] + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) if (litLength >= 12) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) ssPtr->cachedLiterals = literals;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) ssPtr->cachedPrice = price;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) ssPtr->cachedLitLength = litLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) /* literal Length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) const BYTE LL_deltaCode = 19;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) const BYTE llCode = (litLength > 63) ? (BYTE)ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) price += LL_bits[llCode] + ssPtr->log2litLengthSum - ZSTD_highbit32(ssPtr->litLengthFreq[llCode] + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) return price;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) FORCE_INLINE U32 ZSTD_getPrice(seqStore_t *seqStorePtr, U32 litLength, const BYTE *literals, U32 offset, U32 matchLength, const int ultra)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) /* offset */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) U32 price;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146) BYTE const offCode = (BYTE)ZSTD_highbit32(offset + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 148) if (seqStorePtr->staticPrices)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 149) return ZSTD_getLiteralPrice(seqStorePtr, litLength, literals) + ZSTD_highbit32((U32)matchLength + 1) + 16 + offCode;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 150)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 151) price = offCode + seqStorePtr->log2offCodeSum - ZSTD_highbit32(seqStorePtr->offCodeFreq[offCode] + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 152) if (!ultra && offCode >= 20)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 153) price += (offCode - 19) * 2;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 154)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 155) /* match Length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 156) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 157) const BYTE ML_deltaCode = 36;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 158) const BYTE mlCode = (matchLength > 127) ? (BYTE)ZSTD_highbit32(matchLength) + ML_deltaCode : ML_Code[matchLength];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 159) price += ML_bits[mlCode] + seqStorePtr->log2matchLengthSum - ZSTD_highbit32(seqStorePtr->matchLengthFreq[mlCode] + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 160) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 161)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 162) return price + ZSTD_getLiteralPrice(seqStorePtr, litLength, literals) + seqStorePtr->factor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 163) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 164)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 165) ZSTD_STATIC void ZSTD_updatePrice(seqStore_t *seqStorePtr, U32 litLength, const BYTE *literals, U32 offset, U32 matchLength)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 166) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 167) U32 u;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 168)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 169) /* literals */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 170) seqStorePtr->litSum += litLength * ZSTD_LITFREQ_ADD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 171) for (u = 0; u < litLength; u++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 172) seqStorePtr->litFreq[literals[u]] += ZSTD_LITFREQ_ADD;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 173)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 174) /* literal Length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 175) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 176) const BYTE LL_deltaCode = 19;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 177) const BYTE llCode = (litLength > 63) ? (BYTE)ZSTD_highbit32(litLength) + LL_deltaCode : LL_Code[litLength];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 178) seqStorePtr->litLengthFreq[llCode]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 179) seqStorePtr->litLengthSum++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 180) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 181)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 182) /* match offset */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 183) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 184) BYTE const offCode = (BYTE)ZSTD_highbit32(offset + 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 185) seqStorePtr->offCodeSum++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 186) seqStorePtr->offCodeFreq[offCode]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 187) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 188)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 189) /* match Length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 190) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 191) const BYTE ML_deltaCode = 36;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 192) const BYTE mlCode = (matchLength > 127) ? (BYTE)ZSTD_highbit32(matchLength) + ML_deltaCode : ML_Code[matchLength];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 193) seqStorePtr->matchLengthFreq[mlCode]++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 194) seqStorePtr->matchLengthSum++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 195) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 196)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 197) ZSTD_setLog2Prices(seqStorePtr);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 198) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 199)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 200) #define SET_PRICE(pos, mlen_, offset_, litlen_, price_) \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 201) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 202) while (last_pos < pos) { \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 203) opt[last_pos + 1].price = ZSTD_MAX_PRICE; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 204) last_pos++; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 205) } \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 206) opt[pos].mlen = mlen_; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 207) opt[pos].off = offset_; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 208) opt[pos].litlen = litlen_; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 209) opt[pos].price = price_; \
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 210) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 211)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 212) /* Update hashTable3 up to ip (excluded)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 213) Assumption : always within prefix (i.e. not within extDict) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 214) FORCE_INLINE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 215) U32 ZSTD_insertAndFindFirstIndexHash3(ZSTD_CCtx *zc, const BYTE *ip)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 216) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 217) U32 *const hashTable3 = zc->hashTable3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 218) U32 const hashLog3 = zc->hashLog3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 219) const BYTE *const base = zc->base;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 220) U32 idx = zc->nextToUpdate3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 221) const U32 target = zc->nextToUpdate3 = (U32)(ip - base);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 222) const size_t hash3 = ZSTD_hash3Ptr(ip, hashLog3);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 223)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 224) while (idx < target) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 225) hashTable3[ZSTD_hash3Ptr(base + idx, hashLog3)] = idx;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 226) idx++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 227) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 228)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 229) return hashTable3[hash3];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 230) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 231)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 232) /*-*************************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 233) * Binary Tree search
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 234) ***************************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 235) static U32 ZSTD_insertBtAndGetAllMatches(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iLimit, U32 nbCompares, const U32 mls, U32 extDict,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 236) ZSTD_match_t *matches, const U32 minMatchLen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 237) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 238) const BYTE *const base = zc->base;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 239) const U32 curr = (U32)(ip - base);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 240) const U32 hashLog = zc->params.cParams.hashLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 241) const size_t h = ZSTD_hashPtr(ip, hashLog, mls);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 242) U32 *const hashTable = zc->hashTable;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 243) U32 matchIndex = hashTable[h];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 244) U32 *const bt = zc->chainTable;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 245) const U32 btLog = zc->params.cParams.chainLog - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 246) const U32 btMask = (1U << btLog) - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 247) size_t commonLengthSmaller = 0, commonLengthLarger = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 248) const BYTE *const dictBase = zc->dictBase;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 249) const U32 dictLimit = zc->dictLimit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 250) const BYTE *const dictEnd = dictBase + dictLimit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 251) const BYTE *const prefixStart = base + dictLimit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 252) const U32 btLow = btMask >= curr ? 0 : curr - btMask;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 253) const U32 windowLow = zc->lowLimit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 254) U32 *smallerPtr = bt + 2 * (curr & btMask);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 255) U32 *largerPtr = bt + 2 * (curr & btMask) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 256) U32 matchEndIdx = curr + 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 257) U32 dummy32; /* to be nullified at the end */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 258) U32 mnum = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 259)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 260) const U32 minMatch = (mls == 3) ? 3 : 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 261) size_t bestLength = minMatchLen - 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 262)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 263) if (minMatch == 3) { /* HC3 match finder */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 264) U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3(zc, ip);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 265) if (matchIndex3 > windowLow && (curr - matchIndex3 < (1 << 18))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 266) const BYTE *match;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 267) size_t currMl = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 268) if ((!extDict) || matchIndex3 >= dictLimit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 269) match = base + matchIndex3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 270) if (match[bestLength] == ip[bestLength])
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 271) currMl = ZSTD_count(ip, match, iLimit);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 272) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 273) match = dictBase + matchIndex3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 274) if (ZSTD_readMINMATCH(match, MINMATCH) ==
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 275) ZSTD_readMINMATCH(ip, MINMATCH)) /* assumption : matchIndex3 <= dictLimit-4 (by table construction) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 276) currMl = ZSTD_count_2segments(ip + MINMATCH, match + MINMATCH, iLimit, dictEnd, prefixStart) + MINMATCH;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 277) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 278)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 279) /* save best solution */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 280) if (currMl > bestLength) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 281) bestLength = currMl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 282) matches[mnum].off = ZSTD_REP_MOVE_OPT + curr - matchIndex3;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 283) matches[mnum].len = (U32)currMl;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 284) mnum++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 285) if (currMl > ZSTD_OPT_NUM)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 286) goto update;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 287) if (ip + currMl == iLimit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 288) goto update; /* best possible, and avoid read overflow*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 289) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 290) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 291) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 292)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 293) hashTable[h] = curr; /* Update Hash Table */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 294)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 295) while (nbCompares-- && (matchIndex > windowLow)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 296) U32 *nextPtr = bt + 2 * (matchIndex & btMask);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 297) size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 298) const BYTE *match;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 299)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 300) if ((!extDict) || (matchIndex + matchLength >= dictLimit)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 301) match = base + matchIndex;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 302) if (match[matchLength] == ip[matchLength]) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 303) matchLength += ZSTD_count(ip + matchLength + 1, match + matchLength + 1, iLimit) + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 304) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 305) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 306) match = dictBase + matchIndex;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 307) matchLength += ZSTD_count_2segments(ip + matchLength, match + matchLength, iLimit, dictEnd, prefixStart);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 308) if (matchIndex + matchLength >= dictLimit)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 309) match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 310) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 311)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 312) if (matchLength > bestLength) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 313) if (matchLength > matchEndIdx - matchIndex)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 314) matchEndIdx = matchIndex + (U32)matchLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 315) bestLength = matchLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 316) matches[mnum].off = ZSTD_REP_MOVE_OPT + curr - matchIndex;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 317) matches[mnum].len = (U32)matchLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 318) mnum++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 319) if (matchLength > ZSTD_OPT_NUM)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 320) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 321) if (ip + matchLength == iLimit) /* equal : no way to know if inf or sup */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 322) break; /* drop, to guarantee consistency (miss a little bit of compression) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 323) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 324)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 325) if (match[matchLength] < ip[matchLength]) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 326) /* match is smaller than curr */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 327) *smallerPtr = matchIndex; /* update smaller idx */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 328) commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 329) if (matchIndex <= btLow) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 330) smallerPtr = &dummy32;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 331) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 332) } /* beyond tree size, stop the search */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 333) smallerPtr = nextPtr + 1; /* new "smaller" => larger of match */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 334) matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to curr) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 335) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 336) /* match is larger than curr */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 337) *largerPtr = matchIndex;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 338) commonLengthLarger = matchLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 339) if (matchIndex <= btLow) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 340) largerPtr = &dummy32;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 341) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 342) } /* beyond tree size, stop the search */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 343) largerPtr = nextPtr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 344) matchIndex = nextPtr[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 345) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 346) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 347)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 348) *smallerPtr = *largerPtr = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 349)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 350) update:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 351) zc->nextToUpdate = (matchEndIdx > curr + 8) ? matchEndIdx - 8 : curr + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 352) return mnum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 353) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 354)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 355) /** Tree updater, providing best match */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 356) static U32 ZSTD_BtGetAllMatches(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iLimit, const U32 maxNbAttempts, const U32 mls, ZSTD_match_t *matches,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 357) const U32 minMatchLen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 358) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 359) if (ip < zc->base + zc->nextToUpdate)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 360) return 0; /* skipped area */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 361) ZSTD_updateTree(zc, ip, iLimit, maxNbAttempts, mls);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 362) return ZSTD_insertBtAndGetAllMatches(zc, ip, iLimit, maxNbAttempts, mls, 0, matches, minMatchLen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 363) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 364)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 365) static U32 ZSTD_BtGetAllMatches_selectMLS(ZSTD_CCtx *zc, /* Index table will be updated */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 366) const BYTE *ip, const BYTE *const iHighLimit, const U32 maxNbAttempts, const U32 matchLengthSearch,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 367) ZSTD_match_t *matches, const U32 minMatchLen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 368) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 369) switch (matchLengthSearch) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 370) case 3: return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 3, matches, minMatchLen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 371) default:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 372) case 4: return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 4, matches, minMatchLen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 373) case 5: return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 5, matches, minMatchLen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 374) case 7:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 375) case 6: return ZSTD_BtGetAllMatches(zc, ip, iHighLimit, maxNbAttempts, 6, matches, minMatchLen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 376) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 377) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 378)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 379) /** Tree updater, providing best match */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 380) static U32 ZSTD_BtGetAllMatches_extDict(ZSTD_CCtx *zc, const BYTE *const ip, const BYTE *const iLimit, const U32 maxNbAttempts, const U32 mls,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 381) ZSTD_match_t *matches, const U32 minMatchLen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 382) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 383) if (ip < zc->base + zc->nextToUpdate)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 384) return 0; /* skipped area */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 385) ZSTD_updateTree_extDict(zc, ip, iLimit, maxNbAttempts, mls);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 386) return ZSTD_insertBtAndGetAllMatches(zc, ip, iLimit, maxNbAttempts, mls, 1, matches, minMatchLen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 387) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 388)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 389) static U32 ZSTD_BtGetAllMatches_selectMLS_extDict(ZSTD_CCtx *zc, /* Index table will be updated */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 390) const BYTE *ip, const BYTE *const iHighLimit, const U32 maxNbAttempts, const U32 matchLengthSearch,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 391) ZSTD_match_t *matches, const U32 minMatchLen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 392) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 393) switch (matchLengthSearch) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 394) case 3: return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 3, matches, minMatchLen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 395) default:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 396) case 4: return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 4, matches, minMatchLen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 397) case 5: return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 5, matches, minMatchLen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 398) case 7:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 399) case 6: return ZSTD_BtGetAllMatches_extDict(zc, ip, iHighLimit, maxNbAttempts, 6, matches, minMatchLen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 400) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 401) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 402)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 403) /*-*******************************
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 404) * Optimal parser
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 405) *********************************/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 406) FORCE_INLINE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 407) void ZSTD_compressBlock_opt_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const int ultra)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 408) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 409) seqStore_t *seqStorePtr = &(ctx->seqStore);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 410) const BYTE *const istart = (const BYTE *)src;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 411) const BYTE *ip = istart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 412) const BYTE *anchor = istart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 413) const BYTE *const iend = istart + srcSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 414) const BYTE *const ilimit = iend - 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 415) const BYTE *const base = ctx->base;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 416) const BYTE *const prefixStart = base + ctx->dictLimit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 417)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 418) const U32 maxSearches = 1U << ctx->params.cParams.searchLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 419) const U32 sufficient_len = ctx->params.cParams.targetLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 420) const U32 mls = ctx->params.cParams.searchLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 421) const U32 minMatch = (ctx->params.cParams.searchLength == 3) ? 3 : 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 422)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 423) ZSTD_optimal_t *opt = seqStorePtr->priceTable;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 424) ZSTD_match_t *matches = seqStorePtr->matchTable;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 425) const BYTE *inr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 426) U32 offset, rep[ZSTD_REP_NUM];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 427)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 428) /* init */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 429) ctx->nextToUpdate3 = ctx->nextToUpdate;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 430) ZSTD_rescaleFreqs(seqStorePtr, (const BYTE *)src, srcSize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 431) ip += (ip == prefixStart);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 432) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 433) U32 i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 434) for (i = 0; i < ZSTD_REP_NUM; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 435) rep[i] = ctx->rep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 436) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 437)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 438) /* Match Loop */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 439) while (ip < ilimit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 440) U32 cur, match_num, last_pos, litlen, price;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 441) U32 u, mlen, best_mlen, best_off, litLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 442) memset(opt, 0, sizeof(ZSTD_optimal_t));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 443) last_pos = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 444) litlen = (U32)(ip - anchor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 445)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 446) /* check repCode */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 447) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 448) U32 i, last_i = ZSTD_REP_CHECK + (ip == anchor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 449) for (i = (ip == anchor); i < last_i; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 450) const S32 repCur = (i == ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : rep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 451) if ((repCur > 0) && (repCur < (S32)(ip - prefixStart)) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 452) (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(ip - repCur, minMatch))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 453) mlen = (U32)ZSTD_count(ip + minMatch, ip + minMatch - repCur, iend) + minMatch;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 454) if (mlen > sufficient_len || mlen >= ZSTD_OPT_NUM) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 455) best_mlen = mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 456) best_off = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 457) cur = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 458) last_pos = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 459) goto _storeSequence;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 460) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 461) best_off = i - (ip == anchor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 462) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 463) price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 464) if (mlen > last_pos || price < opt[mlen].price)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 465) SET_PRICE(mlen, mlen, i, litlen, price); /* note : macro modifies last_pos */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 466) mlen--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 467) } while (mlen >= minMatch);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 468) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 469) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 470) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 471)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 472) match_num = ZSTD_BtGetAllMatches_selectMLS(ctx, ip, iend, maxSearches, mls, matches, minMatch);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 473)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 474) if (!last_pos && !match_num) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 475) ip++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 476) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 477) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 478)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 479) if (match_num && (matches[match_num - 1].len > sufficient_len || matches[match_num - 1].len >= ZSTD_OPT_NUM)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 480) best_mlen = matches[match_num - 1].len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 481) best_off = matches[match_num - 1].off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 482) cur = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 483) last_pos = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 484) goto _storeSequence;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 485) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 486)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 487) /* set prices using matches at position = 0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 488) best_mlen = (last_pos) ? last_pos : minMatch;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 489) for (u = 0; u < match_num; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 490) mlen = (u > 0) ? matches[u - 1].len + 1 : best_mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 491) best_mlen = matches[u].len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 492) while (mlen <= best_mlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 493) price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off - 1, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 494) if (mlen > last_pos || price < opt[mlen].price)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 495) SET_PRICE(mlen, mlen, matches[u].off, litlen, price); /* note : macro modifies last_pos */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 496) mlen++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 497) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 498) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 499)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 500) if (last_pos < minMatch) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 501) ip++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 502) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 503) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 504)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 505) /* initialize opt[0] */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 506) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 507) U32 i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 508) for (i = 0; i < ZSTD_REP_NUM; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 509) opt[0].rep[i] = rep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 510) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 511) opt[0].mlen = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 512) opt[0].litlen = litlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 513)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 514) /* check further positions */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 515) for (cur = 1; cur <= last_pos; cur++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 516) inr = ip + cur;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 517)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 518) if (opt[cur - 1].mlen == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 519) litlen = opt[cur - 1].litlen + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 520) if (cur > litlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 521) price = opt[cur - litlen].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr - litlen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 522) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 523) price = ZSTD_getLiteralPrice(seqStorePtr, litlen, anchor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 524) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 525) litlen = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 526) price = opt[cur - 1].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 527) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 528)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 529) if (cur > last_pos || price <= opt[cur].price)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 530) SET_PRICE(cur, 1, 0, litlen, price);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 531)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 532) if (cur == last_pos)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 533) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 534)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 535) if (inr > ilimit) /* last match must start at a minimum distance of 8 from oend */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 536) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 537)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 538) mlen = opt[cur].mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 539) if (opt[cur].off > ZSTD_REP_MOVE_OPT) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 540) opt[cur].rep[2] = opt[cur - mlen].rep[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 541) opt[cur].rep[1] = opt[cur - mlen].rep[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 542) opt[cur].rep[0] = opt[cur].off - ZSTD_REP_MOVE_OPT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 543) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 544) opt[cur].rep[2] = (opt[cur].off > 1) ? opt[cur - mlen].rep[1] : opt[cur - mlen].rep[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 545) opt[cur].rep[1] = (opt[cur].off > 0) ? opt[cur - mlen].rep[0] : opt[cur - mlen].rep[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 546) opt[cur].rep[0] =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 547) ((opt[cur].off == ZSTD_REP_MOVE_OPT) && (mlen != 1)) ? (opt[cur - mlen].rep[0] - 1) : (opt[cur - mlen].rep[opt[cur].off]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 548) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 549)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 550) best_mlen = minMatch;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 551) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 552) U32 i, last_i = ZSTD_REP_CHECK + (mlen != 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 553) for (i = (opt[cur].mlen != 1); i < last_i; i++) { /* check rep */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 554) const S32 repCur = (i == ZSTD_REP_MOVE_OPT) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 555) if ((repCur > 0) && (repCur < (S32)(inr - prefixStart)) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 556) (ZSTD_readMINMATCH(inr, minMatch) == ZSTD_readMINMATCH(inr - repCur, minMatch))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 557) mlen = (U32)ZSTD_count(inr + minMatch, inr + minMatch - repCur, iend) + minMatch;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 558)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 559) if (mlen > sufficient_len || cur + mlen >= ZSTD_OPT_NUM) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 560) best_mlen = mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 561) best_off = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 562) last_pos = cur + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 563) goto _storeSequence;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 564) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 565)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 566) best_off = i - (opt[cur].mlen != 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 567) if (mlen > best_mlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 568) best_mlen = mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 569)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 570) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 571) if (opt[cur].mlen == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 572) litlen = opt[cur].litlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 573) if (cur > litlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 574) price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr - litlen,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 575) best_off, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 576) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 577) price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 578) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 579) litlen = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 580) price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 581) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 582)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 583) if (cur + mlen > last_pos || price <= opt[cur + mlen].price)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 584) SET_PRICE(cur + mlen, mlen, i, litlen, price);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 585) mlen--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 586) } while (mlen >= minMatch);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 587) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 588) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 589) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 590)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 591) match_num = ZSTD_BtGetAllMatches_selectMLS(ctx, inr, iend, maxSearches, mls, matches, best_mlen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 592)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 593) if (match_num > 0 && (matches[match_num - 1].len > sufficient_len || cur + matches[match_num - 1].len >= ZSTD_OPT_NUM)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 594) best_mlen = matches[match_num - 1].len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 595) best_off = matches[match_num - 1].off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 596) last_pos = cur + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 597) goto _storeSequence;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 598) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 599)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 600) /* set prices using matches at position = cur */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 601) for (u = 0; u < match_num; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 602) mlen = (u > 0) ? matches[u - 1].len + 1 : best_mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 603) best_mlen = matches[u].len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 604)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 605) while (mlen <= best_mlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 606) if (opt[cur].mlen == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 607) litlen = opt[cur].litlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 608) if (cur > litlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 609) price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip + cur - litlen,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 610) matches[u].off - 1, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 611) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 612) price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off - 1, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 613) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 614) litlen = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 615) price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off - 1, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 616) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 617)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 618) if (cur + mlen > last_pos || (price < opt[cur + mlen].price))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 619) SET_PRICE(cur + mlen, mlen, matches[u].off, litlen, price);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 620)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 621) mlen++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 622) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 623) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 624) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 625)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 626) best_mlen = opt[last_pos].mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 627) best_off = opt[last_pos].off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 628) cur = last_pos - best_mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 629)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 630) /* store sequence */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 631) _storeSequence: /* cur, last_pos, best_mlen, best_off have to be set */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 632) opt[0].mlen = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 633)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 634) while (1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 635) mlen = opt[cur].mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 636) offset = opt[cur].off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 637) opt[cur].mlen = best_mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 638) opt[cur].off = best_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 639) best_mlen = mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 640) best_off = offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 641) if (mlen > cur)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 642) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 643) cur -= mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 644) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 645)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 646) for (u = 0; u <= last_pos;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 647) u += opt[u].mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 648) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 649)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 650) for (cur = 0; cur < last_pos;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 651) mlen = opt[cur].mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 652) if (mlen == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 653) ip++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 654) cur++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 655) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 656) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 657) offset = opt[cur].off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 658) cur += mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 659) litLength = (U32)(ip - anchor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 660)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 661) if (offset > ZSTD_REP_MOVE_OPT) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 662) rep[2] = rep[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 663) rep[1] = rep[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 664) rep[0] = offset - ZSTD_REP_MOVE_OPT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 665) offset--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 666) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 667) if (offset != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 668) best_off = (offset == ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : (rep[offset]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 669) if (offset != 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 670) rep[2] = rep[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 671) rep[1] = rep[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 672) rep[0] = best_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 673) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 674) if (litLength == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 675) offset--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 676) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 677)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 678) ZSTD_updatePrice(seqStorePtr, litLength, anchor, offset, mlen - MINMATCH);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 679) ZSTD_storeSeq(seqStorePtr, litLength, anchor, offset, mlen - MINMATCH);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 680) anchor = ip = ip + mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 681) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 682) } /* for (cur=0; cur < last_pos; ) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 683)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 684) /* Save reps for next block */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 685) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 686) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 687) for (i = 0; i < ZSTD_REP_NUM; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 688) ctx->repToConfirm[i] = rep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 689) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 690)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 691) /* Last Literals */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 692) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 693) size_t const lastLLSize = iend - anchor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 694) memcpy(seqStorePtr->lit, anchor, lastLLSize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 695) seqStorePtr->lit += lastLLSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 696) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 697) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 698)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 699) FORCE_INLINE
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 700) void ZSTD_compressBlock_opt_extDict_generic(ZSTD_CCtx *ctx, const void *src, size_t srcSize, const int ultra)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 701) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 702) seqStore_t *seqStorePtr = &(ctx->seqStore);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 703) const BYTE *const istart = (const BYTE *)src;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 704) const BYTE *ip = istart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 705) const BYTE *anchor = istart;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 706) const BYTE *const iend = istart + srcSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 707) const BYTE *const ilimit = iend - 8;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 708) const BYTE *const base = ctx->base;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 709) const U32 lowestIndex = ctx->lowLimit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 710) const U32 dictLimit = ctx->dictLimit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 711) const BYTE *const prefixStart = base + dictLimit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 712) const BYTE *const dictBase = ctx->dictBase;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 713) const BYTE *const dictEnd = dictBase + dictLimit;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 714)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 715) const U32 maxSearches = 1U << ctx->params.cParams.searchLog;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 716) const U32 sufficient_len = ctx->params.cParams.targetLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 717) const U32 mls = ctx->params.cParams.searchLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 718) const U32 minMatch = (ctx->params.cParams.searchLength == 3) ? 3 : 4;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 719)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 720) ZSTD_optimal_t *opt = seqStorePtr->priceTable;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 721) ZSTD_match_t *matches = seqStorePtr->matchTable;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 722) const BYTE *inr;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 723)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 724) /* init */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 725) U32 offset, rep[ZSTD_REP_NUM];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 726) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 727) U32 i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 728) for (i = 0; i < ZSTD_REP_NUM; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 729) rep[i] = ctx->rep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 730) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 731)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 732) ctx->nextToUpdate3 = ctx->nextToUpdate;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 733) ZSTD_rescaleFreqs(seqStorePtr, (const BYTE *)src, srcSize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 734) ip += (ip == prefixStart);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 735)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 736) /* Match Loop */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 737) while (ip < ilimit) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 738) U32 cur, match_num, last_pos, litlen, price;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 739) U32 u, mlen, best_mlen, best_off, litLength;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 740) U32 curr = (U32)(ip - base);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 741) memset(opt, 0, sizeof(ZSTD_optimal_t));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 742) last_pos = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 743) opt[0].litlen = (U32)(ip - anchor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 744)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 745) /* check repCode */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 746) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 747) U32 i, last_i = ZSTD_REP_CHECK + (ip == anchor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 748) for (i = (ip == anchor); i < last_i; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 749) const S32 repCur = (i == ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : rep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 750) const U32 repIndex = (U32)(curr - repCur);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 751) const BYTE *const repBase = repIndex < dictLimit ? dictBase : base;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 752) const BYTE *const repMatch = repBase + repIndex;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 753) if ((repCur > 0 && repCur <= (S32)curr) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 754) (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 755) && (ZSTD_readMINMATCH(ip, minMatch) == ZSTD_readMINMATCH(repMatch, minMatch))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 756) /* repcode detected we should take it */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 757) const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 758) mlen = (U32)ZSTD_count_2segments(ip + minMatch, repMatch + minMatch, iend, repEnd, prefixStart) + minMatch;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 759)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 760) if (mlen > sufficient_len || mlen >= ZSTD_OPT_NUM) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 761) best_mlen = mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 762) best_off = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 763) cur = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 764) last_pos = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 765) goto _storeSequence;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 766) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 767)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 768) best_off = i - (ip == anchor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 769) litlen = opt[0].litlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 770) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 771) price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 772) if (mlen > last_pos || price < opt[mlen].price)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 773) SET_PRICE(mlen, mlen, i, litlen, price); /* note : macro modifies last_pos */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 774) mlen--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 775) } while (mlen >= minMatch);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 776) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 777) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 778) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 779)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 780) match_num = ZSTD_BtGetAllMatches_selectMLS_extDict(ctx, ip, iend, maxSearches, mls, matches, minMatch); /* first search (depth 0) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 781)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 782) if (!last_pos && !match_num) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 783) ip++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 784) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 785) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 786)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 787) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 788) U32 i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 789) for (i = 0; i < ZSTD_REP_NUM; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 790) opt[0].rep[i] = rep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 791) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 792) opt[0].mlen = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 793)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 794) if (match_num && (matches[match_num - 1].len > sufficient_len || matches[match_num - 1].len >= ZSTD_OPT_NUM)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 795) best_mlen = matches[match_num - 1].len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 796) best_off = matches[match_num - 1].off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 797) cur = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 798) last_pos = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 799) goto _storeSequence;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 800) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 801)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 802) best_mlen = (last_pos) ? last_pos : minMatch;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 803)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 804) /* set prices using matches at position = 0 */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 805) for (u = 0; u < match_num; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 806) mlen = (u > 0) ? matches[u - 1].len + 1 : best_mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 807) best_mlen = matches[u].len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 808) litlen = opt[0].litlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 809) while (mlen <= best_mlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 810) price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off - 1, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 811) if (mlen > last_pos || price < opt[mlen].price)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 812) SET_PRICE(mlen, mlen, matches[u].off, litlen, price);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 813) mlen++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 814) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 815) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 816)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 817) if (last_pos < minMatch) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 818) ip++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 819) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 820) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 821)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 822) /* check further positions */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 823) for (cur = 1; cur <= last_pos; cur++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 824) inr = ip + cur;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 825)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 826) if (opt[cur - 1].mlen == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 827) litlen = opt[cur - 1].litlen + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 828) if (cur > litlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 829) price = opt[cur - litlen].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr - litlen);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 830) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 831) price = ZSTD_getLiteralPrice(seqStorePtr, litlen, anchor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 832) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 833) litlen = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 834) price = opt[cur - 1].price + ZSTD_getLiteralPrice(seqStorePtr, litlen, inr - 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 835) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 836)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 837) if (cur > last_pos || price <= opt[cur].price)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 838) SET_PRICE(cur, 1, 0, litlen, price);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 839)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 840) if (cur == last_pos)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 841) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 842)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 843) if (inr > ilimit) /* last match must start at a minimum distance of 8 from oend */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 844) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 845)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 846) mlen = opt[cur].mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 847) if (opt[cur].off > ZSTD_REP_MOVE_OPT) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 848) opt[cur].rep[2] = opt[cur - mlen].rep[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 849) opt[cur].rep[1] = opt[cur - mlen].rep[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 850) opt[cur].rep[0] = opt[cur].off - ZSTD_REP_MOVE_OPT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 851) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 852) opt[cur].rep[2] = (opt[cur].off > 1) ? opt[cur - mlen].rep[1] : opt[cur - mlen].rep[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 853) opt[cur].rep[1] = (opt[cur].off > 0) ? opt[cur - mlen].rep[0] : opt[cur - mlen].rep[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 854) opt[cur].rep[0] =
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 855) ((opt[cur].off == ZSTD_REP_MOVE_OPT) && (mlen != 1)) ? (opt[cur - mlen].rep[0] - 1) : (opt[cur - mlen].rep[opt[cur].off]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 856) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 857)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 858) best_mlen = minMatch;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 859) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 860) U32 i, last_i = ZSTD_REP_CHECK + (mlen != 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 861) for (i = (mlen != 1); i < last_i; i++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 862) const S32 repCur = (i == ZSTD_REP_MOVE_OPT) ? (opt[cur].rep[0] - 1) : opt[cur].rep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 863) const U32 repIndex = (U32)(curr + cur - repCur);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 864) const BYTE *const repBase = repIndex < dictLimit ? dictBase : base;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 865) const BYTE *const repMatch = repBase + repIndex;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 866) if ((repCur > 0 && repCur <= (S32)(curr + cur)) &&
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 867) (((U32)((dictLimit - 1) - repIndex) >= 3) & (repIndex > lowestIndex)) /* intentional overflow */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 868) && (ZSTD_readMINMATCH(inr, minMatch) == ZSTD_readMINMATCH(repMatch, minMatch))) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 869) /* repcode detected */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 870) const BYTE *const repEnd = repIndex < dictLimit ? dictEnd : iend;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 871) mlen = (U32)ZSTD_count_2segments(inr + minMatch, repMatch + minMatch, iend, repEnd, prefixStart) + minMatch;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 872)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 873) if (mlen > sufficient_len || cur + mlen >= ZSTD_OPT_NUM) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 874) best_mlen = mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 875) best_off = i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 876) last_pos = cur + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 877) goto _storeSequence;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 878) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 879)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 880) best_off = i - (opt[cur].mlen != 1);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 881) if (mlen > best_mlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 882) best_mlen = mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 883)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 884) do {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 885) if (opt[cur].mlen == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 886) litlen = opt[cur].litlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 887) if (cur > litlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 888) price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr - litlen,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 889) best_off, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 890) } else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 891) price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 892) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 893) litlen = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 894) price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 895) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 896)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 897) if (cur + mlen > last_pos || price <= opt[cur + mlen].price)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 898) SET_PRICE(cur + mlen, mlen, i, litlen, price);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 899) mlen--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 900) } while (mlen >= minMatch);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 901) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 902) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 903) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 904)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 905) match_num = ZSTD_BtGetAllMatches_selectMLS_extDict(ctx, inr, iend, maxSearches, mls, matches, minMatch);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 906)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 907) if (match_num > 0 && (matches[match_num - 1].len > sufficient_len || cur + matches[match_num - 1].len >= ZSTD_OPT_NUM)) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 908) best_mlen = matches[match_num - 1].len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 909) best_off = matches[match_num - 1].off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 910) last_pos = cur + 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 911) goto _storeSequence;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 912) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 913)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 914) /* set prices using matches at position = cur */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 915) for (u = 0; u < match_num; u++) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 916) mlen = (u > 0) ? matches[u - 1].len + 1 : best_mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 917) best_mlen = matches[u].len;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 918)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 919) while (mlen <= best_mlen) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 920) if (opt[cur].mlen == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 921) litlen = opt[cur].litlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 922) if (cur > litlen)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 923) price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip + cur - litlen,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 924) matches[u].off - 1, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 925) else
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 926) price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off - 1, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 927) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 928) litlen = 0;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 929) price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off - 1, mlen - MINMATCH, ultra);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 930) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 931)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 932) if (cur + mlen > last_pos || (price < opt[cur + mlen].price))
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 933) SET_PRICE(cur + mlen, mlen, matches[u].off, litlen, price);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 934)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 935) mlen++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 936) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 937) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 938) } /* for (cur = 1; cur <= last_pos; cur++) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 939)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 940) best_mlen = opt[last_pos].mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 941) best_off = opt[last_pos].off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 942) cur = last_pos - best_mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 943)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 944) /* store sequence */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 945) _storeSequence: /* cur, last_pos, best_mlen, best_off have to be set */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 946) opt[0].mlen = 1;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 947)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 948) while (1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 949) mlen = opt[cur].mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 950) offset = opt[cur].off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 951) opt[cur].mlen = best_mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 952) opt[cur].off = best_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 953) best_mlen = mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 954) best_off = offset;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 955) if (mlen > cur)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 956) break;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 957) cur -= mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 958) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 959)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 960) for (u = 0; u <= last_pos;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 961) u += opt[u].mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 962) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 963)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 964) for (cur = 0; cur < last_pos;) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 965) mlen = opt[cur].mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 966) if (mlen == 1) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 967) ip++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 968) cur++;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 969) continue;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 970) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 971) offset = opt[cur].off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 972) cur += mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 973) litLength = (U32)(ip - anchor);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 974)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 975) if (offset > ZSTD_REP_MOVE_OPT) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 976) rep[2] = rep[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 977) rep[1] = rep[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 978) rep[0] = offset - ZSTD_REP_MOVE_OPT;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 979) offset--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 980) } else {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 981) if (offset != 0) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 982) best_off = (offset == ZSTD_REP_MOVE_OPT) ? (rep[0] - 1) : (rep[offset]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 983) if (offset != 1)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 984) rep[2] = rep[1];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 985) rep[1] = rep[0];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 986) rep[0] = best_off;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 987) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 988)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 989) if (litLength == 0)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 990) offset--;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 991) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 992)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 993) ZSTD_updatePrice(seqStorePtr, litLength, anchor, offset, mlen - MINMATCH);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 994) ZSTD_storeSeq(seqStorePtr, litLength, anchor, offset, mlen - MINMATCH);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 995) anchor = ip = ip + mlen;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 996) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 997) } /* for (cur=0; cur < last_pos; ) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 998)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 999) /* Save reps for next block */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1000) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1001) int i;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1002) for (i = 0; i < ZSTD_REP_NUM; i++)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1003) ctx->repToConfirm[i] = rep[i];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1004) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1005)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1006) /* Last Literals */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1007) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1008) size_t lastLLSize = iend - anchor;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1009) memcpy(seqStorePtr->lit, anchor, lastLLSize);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1010) seqStorePtr->lit += lastLLSize;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1011) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1012) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1013)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1014) #endif /* ZSTD_OPT_H_91842398743 */
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags