1	/*
2	* Copyright (c) Przemyslaw Skibinski, Yann Collet, Facebook, Inc.
3	* All rights reserved.
4	*
5	* This source code is licensed under both the BSD-style license (found in the
6	* LICENSE file in the root directory of this source tree) and the GPLv2 (found
7	* in the COPYING file in the root directory of this source tree).
8	* You may select, at your option, one of the above-listed licenses.
9	*/
10
11	#include "zstd_compress_internal.h"
12	#include "hist.h"
13	#include "zstd_opt.h"
14
15
16	#define ZSTD_LITFREQ_ADD 2 /* scaling factor for litFreq, so that frequencies adapt faster to new stats */
17	#define ZSTD_MAX_PRICE (1<<30)
18
19	#define ZSTD_PREDEF_THRESHOLD 1024 /* if srcSize < ZSTD_PREDEF_THRESHOLD, symbols' cost is assumed static, directly determined by pre-defined distributions */
20
21
22	/*-*************************************
23	* Price functions for optimal parser
24	***************************************/
25
26	#if 0 /* approximation at bit level (for tests) */
27	# define BITCOST_ACCURACY 0
28	# define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
29	# define WEIGHT(stat, opt) ((void)opt, ZSTD_bitWeight(stat))
30	#elif 0 /* fractional bit accuracy (for tests) */
31	# define BITCOST_ACCURACY 8
32	# define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
33	# define WEIGHT(stat,opt) ((void)opt, ZSTD_fracWeight(stat))
34	#else /* opt==approx, ultra==accurate */
35	# define BITCOST_ACCURACY 8
36	# define BITCOST_MULTIPLIER (1 << BITCOST_ACCURACY)
37	# define WEIGHT(stat,opt) (opt ? ZSTD_fracWeight(stat) : ZSTD_bitWeight(stat))
38	#endif
39
40	MEM_STATIC U32 ZSTD_bitWeight(U32 stat)
41	{
42	return (ZSTD_highbit32(val: stat+1) * BITCOST_MULTIPLIER);
43	}
44
45	MEM_STATIC U32 ZSTD_fracWeight(U32 rawStat)
46	{
47	U32 const stat = rawStat + 1;
48	U32 const hb = ZSTD_highbit32(val: stat);
49	U32 const BWeight = hb * BITCOST_MULTIPLIER;
50	U32 const FWeight = (stat << BITCOST_ACCURACY) >> hb;
51	U32 const weight = BWeight + FWeight;
52	assert(hb + BITCOST_ACCURACY < 31);
53	return weight;
54	}
55
56	#if (DEBUGLEVEL>=2)
57	/* debugging function,
58	* @return price in bytes as fractional value
59	* for debug messages only */
60	MEM_STATIC double ZSTD_fCost(U32 price)
61	{
62	return (double)price / (BITCOST_MULTIPLIER*8);
63	}
64	#endif
65
66	static int ZSTD_compressedLiterals(optState_t const* const optPtr)
67	{
68	return optPtr->literalCompressionMode != ZSTD_ps_disable;
69	}
70
71	static void ZSTD_setBasePrices(optState_t* optPtr, int optLevel)
72	{
73	if (ZSTD_compressedLiterals(optPtr))
74	optPtr->litSumBasePrice = WEIGHT(optPtr->litSum, optLevel);
75	optPtr->litLengthSumBasePrice = WEIGHT(optPtr->litLengthSum, optLevel);
76	optPtr->matchLengthSumBasePrice = WEIGHT(optPtr->matchLengthSum, optLevel);
77	optPtr->offCodeSumBasePrice = WEIGHT(optPtr->offCodeSum, optLevel);
78	}
79
80
81	static U32 sum_u32(const unsigned table[], size_t nbElts)
82	{
83	size_t n;
84	U32 total = 0;
85	for (n=0; n<nbElts; n++) {
86	total += table[n];
87	}
88	return total;
89	}
90
91	static U32 ZSTD_downscaleStats(unsigned* table, U32 lastEltIndex, U32 shift)
92	{
93	U32 s, sum=0;
94	DEBUGLOG(5, "ZSTD_downscaleStats (nbElts=%u, shift=%u)", (unsigned)lastEltIndex+1, (unsigned)shift);
95	assert(shift < 30);
96	for (s=0; s<lastEltIndex+1; s++) {
97	table[s] = 1 + (table[s] >> shift);
98	sum += table[s];
99	}
100	return sum;
101	}
102
103	/* ZSTD_scaleStats() :
104	* reduce all elements in table is sum too large
105	* return the resulting sum of elements */
106	static U32 ZSTD_scaleStats(unsigned* table, U32 lastEltIndex, U32 logTarget)
107	{
108	U32 const prevsum = sum_u32(table, nbElts: lastEltIndex+1);
109	U32 const factor = prevsum >> logTarget;
110	DEBUGLOG(5, "ZSTD_scaleStats (nbElts=%u, target=%u)", (unsigned)lastEltIndex+1, (unsigned)logTarget);
111	assert(logTarget < 30);
112	if (factor <= 1) return prevsum;
113	return ZSTD_downscaleStats(table, lastEltIndex, shift: ZSTD_highbit32(val: factor));
114	}
115
116	/* ZSTD_rescaleFreqs() :
117	* if first block (detected by optPtr->litLengthSum == 0) : init statistics
118	* take hints from dictionary if there is one
119	* and init from zero if there is none,
120	* using src for literals stats, and baseline stats for sequence symbols
121	* otherwise downscale existing stats, to be used as seed for next block.
122	*/
123	static void
124	ZSTD_rescaleFreqs(optState_t* const optPtr,
125	const BYTE* const src, size_t const srcSize,
126	int const optLevel)
127	{
128	int const compressedLiterals = ZSTD_compressedLiterals(optPtr);
129	DEBUGLOG(5, "ZSTD_rescaleFreqs (srcSize=%u)", (unsigned)srcSize);
130	optPtr->priceType = zop_dynamic;
131
132	if (optPtr->litLengthSum == 0) { /* first block : init */
133	if (srcSize <= ZSTD_PREDEF_THRESHOLD) { /* heuristic */
134	DEBUGLOG(5, "(srcSize <= ZSTD_PREDEF_THRESHOLD) => zop_predef");
135	optPtr->priceType = zop_predef;
136	}
137
138	assert(optPtr->symbolCosts != NULL);
139	if (optPtr->symbolCosts->huf.repeatMode == HUF_repeat_valid) {
140	/* huffman table presumed generated by dictionary */
141	optPtr->priceType = zop_dynamic;
142
143	if (compressedLiterals) {
144	unsigned lit;
145	assert(optPtr->litFreq != NULL);
146	optPtr->litSum = 0;
147	for (lit=0; lit<=MaxLit; lit++) {
148	U32 const scaleLog = 11; /* scale to 2K */
149	U32 const bitCost = HUF_getNbBitsFromCTable(symbolTable: optPtr->symbolCosts->huf.CTable, symbolValue: lit);
150	assert(bitCost <= scaleLog);
151	optPtr->litFreq[lit] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
152	optPtr->litSum += optPtr->litFreq[lit];
153	} }
154
155	{ unsigned ll;
156	FSE_CState_t llstate;
157	FSE_initCState(statePtr: &llstate, ct: optPtr->symbolCosts->fse.litlengthCTable);
158	optPtr->litLengthSum = 0;
159	for (ll=0; ll<=MaxLL; ll++) {
160	U32 const scaleLog = 10; /* scale to 1K */
161	U32 const bitCost = FSE_getMaxNbBits(symbolTTPtr: llstate.symbolTT, symbolValue: ll);
162	assert(bitCost < scaleLog);
163	optPtr->litLengthFreq[ll] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
164	optPtr->litLengthSum += optPtr->litLengthFreq[ll];
165	} }
166
167	{ unsigned ml;
168	FSE_CState_t mlstate;
169	FSE_initCState(statePtr: &mlstate, ct: optPtr->symbolCosts->fse.matchlengthCTable);
170	optPtr->matchLengthSum = 0;
171	for (ml=0; ml<=MaxML; ml++) {
172	U32 const scaleLog = 10;
173	U32 const bitCost = FSE_getMaxNbBits(symbolTTPtr: mlstate.symbolTT, symbolValue: ml);
174	assert(bitCost < scaleLog);
175	optPtr->matchLengthFreq[ml] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
176	optPtr->matchLengthSum += optPtr->matchLengthFreq[ml];
177	} }
178
179	{ unsigned of;
180	FSE_CState_t ofstate;
181	FSE_initCState(statePtr: &ofstate, ct: optPtr->symbolCosts->fse.offcodeCTable);
182	optPtr->offCodeSum = 0;
183	for (of=0; of<=MaxOff; of++) {
184	U32 const scaleLog = 10;
185	U32 const bitCost = FSE_getMaxNbBits(symbolTTPtr: ofstate.symbolTT, symbolValue: of);
186	assert(bitCost < scaleLog);
187	optPtr->offCodeFreq[of] = bitCost ? 1 << (scaleLog-bitCost) : 1 /*minimum to calculate cost*/;
188	optPtr->offCodeSum += optPtr->offCodeFreq[of];
189	} }
190
191	} else { /* not a dictionary */
192
193	assert(optPtr->litFreq != NULL);
194	if (compressedLiterals) {
195	unsigned lit = MaxLit;
196	HIST_count_simple(count: optPtr->litFreq, maxSymbolValuePtr: &lit, src, srcSize); /* use raw first block to init statistics */
197	optPtr->litSum = ZSTD_downscaleStats(table: optPtr->litFreq, MaxLit, shift: 8);
198	}
199
200	{ unsigned const baseLLfreqs[MaxLL+1] = {
201	4, 2, 1, 1, 1, 1, 1, 1,
202	1, 1, 1, 1, 1, 1, 1, 1,
203	1, 1, 1, 1, 1, 1, 1, 1,
204	1, 1, 1, 1, 1, 1, 1, 1,
205	1, 1, 1, 1
206	};
207	ZSTD_memcpy(optPtr->litLengthFreq, baseLLfreqs, sizeof(baseLLfreqs));
208	optPtr->litLengthSum = sum_u32(table: baseLLfreqs, MaxLL+1);
209	}
210
211	{ unsigned ml;
212	for (ml=0; ml<=MaxML; ml++)
213	optPtr->matchLengthFreq[ml] = 1;
214	}
215	optPtr->matchLengthSum = MaxML+1;
216
217	{ unsigned const baseOFCfreqs[MaxOff+1] = {
218	6, 2, 1, 1, 2, 3, 4, 4,
219	4, 3, 2, 1, 1, 1, 1, 1,
220	1, 1, 1, 1, 1, 1, 1, 1,
221	1, 1, 1, 1, 1, 1, 1, 1
222	};
223	ZSTD_memcpy(optPtr->offCodeFreq, baseOFCfreqs, sizeof(baseOFCfreqs));
224	optPtr->offCodeSum = sum_u32(table: baseOFCfreqs, MaxOff+1);
225	}
226
227
228	}
229
230	} else { /* new block : re-use previous statistics, scaled down */
231
232	if (compressedLiterals)
233	optPtr->litSum = ZSTD_scaleStats(table: optPtr->litFreq, MaxLit, logTarget: 12);
234	optPtr->litLengthSum = ZSTD_scaleStats(table: optPtr->litLengthFreq, MaxLL, logTarget: 11);
235	optPtr->matchLengthSum = ZSTD_scaleStats(table: optPtr->matchLengthFreq, MaxML, logTarget: 11);
236	optPtr->offCodeSum = ZSTD_scaleStats(table: optPtr->offCodeFreq, MaxOff, logTarget: 11);
237	}
238
239	ZSTD_setBasePrices(optPtr, optLevel);
240	}
241
242	/* ZSTD_rawLiteralsCost() :
243	* price of literals (only) in specified segment (which length can be 0).
244	* does not include price of literalLength symbol */
245	static U32 ZSTD_rawLiteralsCost(const BYTE* const literals, U32 const litLength,
246	const optState_t* const optPtr,
247	int optLevel)
248	{
249	if (litLength == 0) return 0;
250
251	if (!ZSTD_compressedLiterals(optPtr))
252	return (litLength << 3) * BITCOST_MULTIPLIER; /* Uncompressed - 8 bytes per literal. */
253
254	if (optPtr->priceType == zop_predef)
255	return (litLength*6) * BITCOST_MULTIPLIER; /* 6 bit per literal - no statistic used */
256
257	/* dynamic statistics */
258	{ U32 price = litLength * optPtr->litSumBasePrice;
259	U32 u;
260	for (u=0; u < litLength; u++) {
261	assert(WEIGHT(optPtr->litFreq[literals[u]], optLevel) <= optPtr->litSumBasePrice); /* literal cost should never be negative */
262	price -= WEIGHT(optPtr->litFreq[literals[u]], optLevel);
263	}
264	return price;
265	}
266	}
267
268	/* ZSTD_litLengthPrice() :
269	* cost of literalLength symbol */
270	static U32 ZSTD_litLengthPrice(U32 const litLength, const optState_t* const optPtr, int optLevel)
271	{
272	assert(litLength <= ZSTD_BLOCKSIZE_MAX);
273	if (optPtr->priceType == zop_predef)
274	return WEIGHT(litLength, optLevel);
275	/* We can't compute the litLength price for sizes >= ZSTD_BLOCKSIZE_MAX
276	* because it isn't representable in the zstd format. So instead just
277	* call it 1 bit more than ZSTD_BLOCKSIZE_MAX - 1. In this case the block
278	* would be all literals.
279	*/
280	if (litLength == ZSTD_BLOCKSIZE_MAX)
281	return BITCOST_MULTIPLIER + ZSTD_litLengthPrice(ZSTD_BLOCKSIZE_MAX - 1, optPtr, optLevel);
282
283	/* dynamic statistics */
284	{ U32 const llCode = ZSTD_LLcode(litLength);
285	return (LL_bits[llCode] * BITCOST_MULTIPLIER)
286	+ optPtr->litLengthSumBasePrice
287	- WEIGHT(optPtr->litLengthFreq[llCode], optLevel);
288	}
289	}
290
291	/* ZSTD_getMatchPrice() :
292	* Provides the cost of the match part (offset + matchLength) of a sequence
293	* Must be combined with ZSTD_fullLiteralsCost() to get the full cost of a sequence.
294	* @offcode : expects a scale where 0,1,2 are repcodes 1-3, and 3+ are real_offsets+2
295	* @optLevel: when <2, favors small offset for decompression speed (improved cache efficiency)
296	*/
297	FORCE_INLINE_TEMPLATE U32
298	ZSTD_getMatchPrice(U32 const offcode,
299	U32 const matchLength,
300	const optState_t* const optPtr,
301	int const optLevel)
302	{
303	U32 price;
304	U32 const offCode = ZSTD_highbit32(STORED_TO_OFFBASE(offcode));
305	U32 const mlBase = matchLength - MINMATCH;
306	assert(matchLength >= MINMATCH);
307
308	if (optPtr->priceType == zop_predef) /* fixed scheme, do not use statistics */
309	return WEIGHT(mlBase, optLevel) + ((16 + offCode) * BITCOST_MULTIPLIER);
310
311	/* dynamic statistics */
312	price = (offCode * BITCOST_MULTIPLIER) + (optPtr->offCodeSumBasePrice - WEIGHT(optPtr->offCodeFreq[offCode], optLevel));
313	if ((optLevel<2) /*static*/ && offCode >= 20)
314	price += (offCode-19)*2 * BITCOST_MULTIPLIER; /* handicap for long distance offsets, favor decompression speed */
315
316	/* match Length */
317	{ U32 const mlCode = ZSTD_MLcode(mlBase);
318	price += (ML_bits[mlCode] * BITCOST_MULTIPLIER) + (optPtr->matchLengthSumBasePrice - WEIGHT(optPtr->matchLengthFreq[mlCode], optLevel));
319	}
320
321	price += BITCOST_MULTIPLIER / 5; /* heuristic : make matches a bit more costly to favor less sequences -> faster decompression speed */
322
323	DEBUGLOG(8, "ZSTD_getMatchPrice(ml:%u) = %u", matchLength, price);
324	return price;
325	}
326
327	/* ZSTD_updateStats() :
328	* assumption : literals + litLengtn <= iend */
329	static void ZSTD_updateStats(optState_t* const optPtr,
330	U32 litLength, const BYTE* literals,
331	U32 offsetCode, U32 matchLength)
332	{
333	/* literals */
334	if (ZSTD_compressedLiterals(optPtr)) {
335	U32 u;
336	for (u=0; u < litLength; u++)
337	optPtr->litFreq[literals[u]] += ZSTD_LITFREQ_ADD;
338	optPtr->litSum += litLength*ZSTD_LITFREQ_ADD;
339	}
340
341	/* literal Length */
342	{ U32 const llCode = ZSTD_LLcode(litLength);
343	optPtr->litLengthFreq[llCode]++;
344	optPtr->litLengthSum++;
345	}
346
347	/* offset code : expected to follow storeSeq() numeric representation */
348	{ U32 const offCode = ZSTD_highbit32(STORED_TO_OFFBASE(offsetCode));
349	assert(offCode <= MaxOff);
350	optPtr->offCodeFreq[offCode]++;
351	optPtr->offCodeSum++;
352	}
353
354	/* match Length */
355	{ U32 const mlBase = matchLength - MINMATCH;
356	U32 const mlCode = ZSTD_MLcode(mlBase);
357	optPtr->matchLengthFreq[mlCode]++;
358	optPtr->matchLengthSum++;
359	}
360	}
361
362
363	/* ZSTD_readMINMATCH() :
364	* function safe only for comparisons
365	* assumption : memPtr must be at least 4 bytes before end of buffer */
366	MEM_STATIC U32 ZSTD_readMINMATCH(const void* memPtr, U32 length)
367	{
368	switch (length)
369	{
370	default :
371	case 4 : return MEM_read32(memPtr);
372	case 3 : if (MEM_isLittleEndian())
373	return MEM_read32(memPtr)<<8;
374	else
375	return MEM_read32(memPtr)>>8;
376	}
377	}
378
379
380	/* Update hashTable3 up to ip (excluded)
381	Assumption : always within prefix (i.e. not within extDict) */
382	static U32 ZSTD_insertAndFindFirstIndexHash3 (const ZSTD_matchState_t* ms,
383	U32* nextToUpdate3,
384	const BYTE* const ip)
385	{
386	U32* const hashTable3 = ms->hashTable3;
387	U32 const hashLog3 = ms->hashLog3;
388	const BYTE* const base = ms->window.base;
389	U32 idx = *nextToUpdate3;
390	U32 const target = (U32)(ip - base);
391	size_t const hash3 = ZSTD_hash3Ptr(ptr: ip, h: hashLog3);
392	assert(hashLog3 > 0);
393
394	while(idx < target) {
395	hashTable3[ZSTD_hash3Ptr(ptr: base+idx, h: hashLog3)] = idx;
396	idx++;
397	}
398
399	*nextToUpdate3 = target;
400	return hashTable3[hash3];
401	}
402
403
404	/*-*************************************
405	* Binary Tree search
406	***************************************/
407	/* ZSTD_insertBt1() : add one or multiple positions to tree.
408	* @param ip assumed <= iend-8 .
409	* @param target The target of ZSTD_updateTree_internal() - we are filling to this position
410	* @return : nb of positions added */
411	static U32 ZSTD_insertBt1(
412	const ZSTD_matchState_t* ms,
413	const BYTE* const ip, const BYTE* const iend,
414	U32 const target,
415	U32 const mls, const int extDict)
416	{
417	const ZSTD_compressionParameters* const cParams = &ms->cParams;
418	U32* const hashTable = ms->hashTable;
419	U32 const hashLog = cParams->hashLog;
420	size_t const h = ZSTD_hashPtr(p: ip, hBits: hashLog, mls);
421	U32* const bt = ms->chainTable;
422	U32 const btLog = cParams->chainLog - 1;
423	U32 const btMask = (1 << btLog) - 1;
424	U32 matchIndex = hashTable[h];
425	size_t commonLengthSmaller=0, commonLengthLarger=0;
426	const BYTE* const base = ms->window.base;
427	const BYTE* const dictBase = ms->window.dictBase;
428	const U32 dictLimit = ms->window.dictLimit;
429	const BYTE* const dictEnd = dictBase + dictLimit;
430	const BYTE* const prefixStart = base + dictLimit;
431	const BYTE* match;
432	const U32 curr = (U32)(ip-base);
433	const U32 btLow = btMask >= curr ? 0 : curr - btMask;
434	U32* smallerPtr = bt + 2*(curr&btMask);
435	U32* largerPtr = smallerPtr + 1;
436	U32 dummy32; /* to be nullified at the end */
437	/* windowLow is based on target because
438	* we only need positions that will be in the window at the end of the tree update.
439	*/
440	U32 const windowLow = ZSTD_getLowestMatchIndex(ms, curr: target, windowLog: cParams->windowLog);
441	U32 matchEndIdx = curr+8+1;
442	size_t bestLength = 8;
443	U32 nbCompares = 1U << cParams->searchLog;
444	#ifdef ZSTD_C_PREDICT
445	U32 predictedSmall = *(bt + 2*((curr-1)&btMask) + 0);
446	U32 predictedLarge = *(bt + 2*((curr-1)&btMask) + 1);
447	predictedSmall += (predictedSmall>0);
448	predictedLarge += (predictedLarge>0);
449	#endif /* ZSTD_C_PREDICT */
450
451	DEBUGLOG(8, "ZSTD_insertBt1 (%u)", curr);
452
453	assert(curr <= target);
454	assert(ip <= iend-8); /* required for h calculation */
455	hashTable[h] = curr; /* Update Hash Table */
456
457	assert(windowLow > 0);
458	for (; nbCompares && (matchIndex >= windowLow); --nbCompares) {
459	U32* const nextPtr = bt + 2*(matchIndex & btMask);
460	size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
461	assert(matchIndex < curr);
462
463	#ifdef ZSTD_C_PREDICT /* note : can create issues when hlog small <= 11 */
464	const U32* predictPtr = bt + 2*((matchIndex-1) & btMask); /* written this way, as bt is a roll buffer */
465	if (matchIndex == predictedSmall) {
466	/* no need to check length, result known */
467	*smallerPtr = matchIndex;
468	if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
469	smallerPtr = nextPtr+1; /* new "smaller" => larger of match */
470	matchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
471	predictedSmall = predictPtr[1] + (predictPtr[1]>0);
472	continue;
473	}
474	if (matchIndex == predictedLarge) {
475	*largerPtr = matchIndex;
476	if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
477	largerPtr = nextPtr;
478	matchIndex = nextPtr[0];
479	predictedLarge = predictPtr[0] + (predictPtr[0]>0);
480	continue;
481	}
482	#endif
483
484	if (!extDict || (matchIndex+matchLength >= dictLimit)) {
485	assert(matchIndex+matchLength >= dictLimit); /* might be wrong if actually extDict */
486	match = base + matchIndex;
487	matchLength += ZSTD_count(pIn: ip+matchLength, pMatch: match+matchLength, pInLimit: iend);
488	} else {
489	match = dictBase + matchIndex;
490	matchLength += ZSTD_count_2segments(ip: ip+matchLength, match: match+matchLength, iEnd: iend, mEnd: dictEnd, iStart: prefixStart);
491	if (matchIndex+matchLength >= dictLimit)
492	match = base + matchIndex; /* to prepare for next usage of match[matchLength] */
493	}
494
495	if (matchLength > bestLength) {
496	bestLength = matchLength;
497	if (matchLength > matchEndIdx - matchIndex)
498	matchEndIdx = matchIndex + (U32)matchLength;
499	}
500
501	if (ip+matchLength == iend) { /* equal : no way to know if inf or sup */
502	break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt tree */
503	}
504
505	if (match[matchLength] < ip[matchLength]) { /* necessarily within buffer */
506	/* match is smaller than current */
507	*smallerPtr = matchIndex; /* update smaller idx */
508	commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
509	if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop searching */
510	smallerPtr = nextPtr+1; /* new "candidate" => larger than match, which was smaller than target */
511	matchIndex = nextPtr[1]; /* new matchIndex, larger than previous and closer to current */
512	} else {
513	/* match is larger than current */
514	*largerPtr = matchIndex;
515	commonLengthLarger = matchLength;
516	if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop searching */
517	largerPtr = nextPtr;
518	matchIndex = nextPtr[0];
519	} }
520
521	*smallerPtr = *largerPtr = 0;
522	{ U32 positions = 0;
523	if (bestLength > 384) positions = MIN(192, (U32)(bestLength - 384)); /* speed optimization */
524	assert(matchEndIdx > curr + 8);
525	return MAX(positions, matchEndIdx - (curr + 8));
526	}
527	}
528
529	FORCE_INLINE_TEMPLATE
530	void ZSTD_updateTree_internal(
531	ZSTD_matchState_t* ms,
532	const BYTE* const ip, const BYTE* const iend,
533	const U32 mls, const ZSTD_dictMode_e dictMode)
534	{
535	const BYTE* const base = ms->window.base;
536	U32 const target = (U32)(ip - base);
537	U32 idx = ms->nextToUpdate;
538	DEBUGLOG(6, "ZSTD_updateTree_internal, from %u to %u (dictMode:%u)",
539	idx, target, dictMode);
540
541	while(idx < target) {
542	U32 const forward = ZSTD_insertBt1(ms, ip: base+idx, iend, target, mls, extDict: dictMode == ZSTD_extDict);
543	assert(idx < (U32)(idx + forward));
544	idx += forward;
545	}
546	assert((size_t)(ip - base) <= (size_t)(U32)(-1));
547	assert((size_t)(iend - base) <= (size_t)(U32)(-1));
548	ms->nextToUpdate = target;
549	}
550
551	void ZSTD_updateTree(ZSTD_matchState_t* ms, const BYTE* ip, const BYTE* iend) {
552	ZSTD_updateTree_internal(ms, ip, iend, mls: ms->cParams.minMatch, dictMode: ZSTD_noDict);
553	}
554
555	FORCE_INLINE_TEMPLATE
556	U32 ZSTD_insertBtAndGetAllMatches (
557	ZSTD_match_t* matches, /* store result (found matches) in this table (presumed large enough) */
558	ZSTD_matchState_t* ms,
559	U32* nextToUpdate3,
560	const BYTE* const ip, const BYTE* const iLimit, const ZSTD_dictMode_e dictMode,
561	const U32 rep[ZSTD_REP_NUM],
562	U32 const ll0, /* tells if associated literal length is 0 or not. This value must be 0 or 1 */
563	const U32 lengthToBeat,
564	U32 const mls /* template */)
565	{
566	const ZSTD_compressionParameters* const cParams = &ms->cParams;
567	U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1);
568	const BYTE* const base = ms->window.base;
569	U32 const curr = (U32)(ip-base);
570	U32 const hashLog = cParams->hashLog;
571	U32 const minMatch = (mls==3) ? 3 : 4;
572	U32* const hashTable = ms->hashTable;
573	size_t const h = ZSTD_hashPtr(p: ip, hBits: hashLog, mls);
574	U32 matchIndex = hashTable[h];
575	U32* const bt = ms->chainTable;
576	U32 const btLog = cParams->chainLog - 1;
577	U32 const btMask= (1U << btLog) - 1;
578	size_t commonLengthSmaller=0, commonLengthLarger=0;
579	const BYTE* const dictBase = ms->window.dictBase;
580	U32 const dictLimit = ms->window.dictLimit;
581	const BYTE* const dictEnd = dictBase + dictLimit;
582	const BYTE* const prefixStart = base + dictLimit;
583	U32 const btLow = (btMask >= curr) ? 0 : curr - btMask;
584	U32 const windowLow = ZSTD_getLowestMatchIndex(ms, curr, windowLog: cParams->windowLog);
585	U32 const matchLow = windowLow ? windowLow : 1;
586	U32* smallerPtr = bt + 2*(curr&btMask);
587	U32* largerPtr = bt + 2*(curr&btMask) + 1;
588	U32 matchEndIdx = curr+8+1; /* farthest referenced position of any match => detects repetitive patterns */
589	U32 dummy32; /* to be nullified at the end */
590	U32 mnum = 0;
591	U32 nbCompares = 1U << cParams->searchLog;
592
593	const ZSTD_matchState_t* dms = dictMode == ZSTD_dictMatchState ? ms->dictMatchState : NULL;
594	const ZSTD_compressionParameters* const dmsCParams =
595	dictMode == ZSTD_dictMatchState ? &dms->cParams : NULL;
596	const BYTE* const dmsBase = dictMode == ZSTD_dictMatchState ? dms->window.base : NULL;
597	const BYTE* const dmsEnd = dictMode == ZSTD_dictMatchState ? dms->window.nextSrc : NULL;
598	U32 const dmsHighLimit = dictMode == ZSTD_dictMatchState ? (U32)(dmsEnd - dmsBase) : 0;
599	U32 const dmsLowLimit = dictMode == ZSTD_dictMatchState ? dms->window.lowLimit : 0;
600	U32 const dmsIndexDelta = dictMode == ZSTD_dictMatchState ? windowLow - dmsHighLimit : 0;
601	U32 const dmsHashLog = dictMode == ZSTD_dictMatchState ? dmsCParams->hashLog : hashLog;
602	U32 const dmsBtLog = dictMode == ZSTD_dictMatchState ? dmsCParams->chainLog - 1 : btLog;
603	U32 const dmsBtMask = dictMode == ZSTD_dictMatchState ? (1U << dmsBtLog) - 1 : 0;
604	U32 const dmsBtLow = dictMode == ZSTD_dictMatchState && dmsBtMask < dmsHighLimit - dmsLowLimit ? dmsHighLimit - dmsBtMask : dmsLowLimit;
605
606	size_t bestLength = lengthToBeat-1;
607	DEBUGLOG(8, "ZSTD_insertBtAndGetAllMatches: current=%u", curr);
608
609	/* check repCode */
610	assert(ll0 <= 1); /* necessarily 1 or 0 */
611	{ U32 const lastR = ZSTD_REP_NUM + ll0;
612	U32 repCode;
613	for (repCode = ll0; repCode < lastR; repCode++) {
614	U32 const repOffset = (repCode==ZSTD_REP_NUM) ? (rep[0] - 1) : rep[repCode];
615	U32 const repIndex = curr - repOffset;
616	U32 repLen = 0;
617	assert(curr >= dictLimit);
618	if (repOffset-1 /* intentional overflow, discards 0 and -1 */ < curr-dictLimit) { /* equivalent to `curr > repIndex >= dictLimit` */
619	/* We must validate the repcode offset because when we're using a dictionary the
620	* valid offset range shrinks when the dictionary goes out of bounds.
621	*/
622	if ((repIndex >= windowLow) & (ZSTD_readMINMATCH(memPtr: ip, length: minMatch) == ZSTD_readMINMATCH(memPtr: ip - repOffset, length: minMatch))) {
623	repLen = (U32)ZSTD_count(pIn: ip+minMatch, pMatch: ip+minMatch-repOffset, pInLimit: iLimit) + minMatch;
624	}
625	} else { /* repIndex < dictLimit || repIndex >= curr */
626	const BYTE* const repMatch = dictMode == ZSTD_dictMatchState ?
627	dmsBase + repIndex - dmsIndexDelta :
628	dictBase + repIndex;
629	assert(curr >= windowLow);
630	if ( dictMode == ZSTD_extDict
631	&& ( ((repOffset-1) /*intentional overflow*/ < curr - windowLow) /* equivalent to `curr > repIndex >= windowLow` */
632	& (((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */)
633	&& (ZSTD_readMINMATCH(memPtr: ip, length: minMatch) == ZSTD_readMINMATCH(memPtr: repMatch, length: minMatch)) ) {
634	repLen = (U32)ZSTD_count_2segments(ip: ip+minMatch, match: repMatch+minMatch, iEnd: iLimit, mEnd: dictEnd, iStart: prefixStart) + minMatch;
635	}
636	if (dictMode == ZSTD_dictMatchState
637	&& ( ((repOffset-1) /*intentional overflow*/ < curr - (dmsLowLimit + dmsIndexDelta)) /* equivalent to `curr > repIndex >= dmsLowLimit` */
638	& ((U32)((dictLimit-1) - repIndex) >= 3) ) /* intentional overflow : do not test positions overlapping 2 memory segments */
639	&& (ZSTD_readMINMATCH(memPtr: ip, length: minMatch) == ZSTD_readMINMATCH(memPtr: repMatch, length: minMatch)) ) {
640	repLen = (U32)ZSTD_count_2segments(ip: ip+minMatch, match: repMatch+minMatch, iEnd: iLimit, mEnd: dmsEnd, iStart: prefixStart) + minMatch;
641	} }
642	/* save longer solution */
643	if (repLen > bestLength) {
644	DEBUGLOG(8, "found repCode %u (ll0:%u, offset:%u) of length %u",
645	repCode, ll0, repOffset, repLen);
646	bestLength = repLen;
647	matches[mnum].off = STORE_REPCODE(repCode - ll0 + 1); /* expect value between 1 and 3 */
648	matches[mnum].len = (U32)repLen;
649	mnum++;
650	if ( (repLen > sufficient_len)
651	| (ip+repLen == iLimit) ) { /* best possible */
652	return mnum;
653	} } } }
654
655	/* HC3 match finder */
656	if ((mls == 3) /*static*/ && (bestLength < mls)) {
657	U32 const matchIndex3 = ZSTD_insertAndFindFirstIndexHash3(ms, nextToUpdate3, ip);
658	if ((matchIndex3 >= matchLow)
659	& (curr - matchIndex3 < (1<<18)) /*heuristic : longer distance likely too expensive*/ ) {
660	size_t mlen;
661	if ((dictMode == ZSTD_noDict) /*static*/ || (dictMode == ZSTD_dictMatchState) /*static*/ || (matchIndex3 >= dictLimit)) {
662	const BYTE* const match = base + matchIndex3;
663	mlen = ZSTD_count(pIn: ip, pMatch: match, pInLimit: iLimit);
664	} else {
665	const BYTE* const match = dictBase + matchIndex3;
666	mlen = ZSTD_count_2segments(ip, match, iEnd: iLimit, mEnd: dictEnd, iStart: prefixStart);
667	}
668
669	/* save best solution */
670	if (mlen >= mls /* == 3 > bestLength */) {
671	DEBUGLOG(8, "found small match with hlog3, of length %u",
672	(U32)mlen);
673	bestLength = mlen;
674	assert(curr > matchIndex3);
675	assert(mnum==0); /* no prior solution */
676	matches[0].off = STORE_OFFSET(curr - matchIndex3);
677	matches[0].len = (U32)mlen;
678	mnum = 1;
679	if ( (mlen > sufficient_len) |
680	(ip+mlen == iLimit) ) { /* best possible length */
681	ms->nextToUpdate = curr+1; /* skip insertion */
682	return 1;
683	} } }
684	/* no dictMatchState lookup: dicts don't have a populated HC3 table */
685	} /* if (mls == 3) */
686
687	hashTable[h] = curr; /* Update Hash Table */
688
689	for (; nbCompares && (matchIndex >= matchLow); --nbCompares) {
690	U32* const nextPtr = bt + 2*(matchIndex & btMask);
691	const BYTE* match;
692	size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
693	assert(curr > matchIndex);
694
695	if ((dictMode == ZSTD_noDict) || (dictMode == ZSTD_dictMatchState) || (matchIndex+matchLength >= dictLimit)) {
696	assert(matchIndex+matchLength >= dictLimit); /* ensure the condition is correct when !extDict */
697	match = base + matchIndex;
698	if (matchIndex >= dictLimit) assert(memcmp(match, ip, matchLength) == 0); /* ensure early section of match is equal as expected */
699	matchLength += ZSTD_count(pIn: ip+matchLength, pMatch: match+matchLength, pInLimit: iLimit);
700	} else {
701	match = dictBase + matchIndex;
702	assert(memcmp(match, ip, matchLength) == 0); /* ensure early section of match is equal as expected */
703	matchLength += ZSTD_count_2segments(ip: ip+matchLength, match: match+matchLength, iEnd: iLimit, mEnd: dictEnd, iStart: prefixStart);
704	if (matchIndex+matchLength >= dictLimit)
705	match = base + matchIndex; /* prepare for match[matchLength] read */
706	}
707
708	if (matchLength > bestLength) {
709	DEBUGLOG(8, "found match of length %u at distance %u (offCode=%u)",
710	(U32)matchLength, curr - matchIndex, STORE_OFFSET(curr - matchIndex));
711	assert(matchEndIdx > matchIndex);
712	if (matchLength > matchEndIdx - matchIndex)
713	matchEndIdx = matchIndex + (U32)matchLength;
714	bestLength = matchLength;
715	matches[mnum].off = STORE_OFFSET(curr - matchIndex);
716	matches[mnum].len = (U32)matchLength;
717	mnum++;
718	if ( (matchLength > ZSTD_OPT_NUM)
719	| (ip+matchLength == iLimit) /* equal : no way to know if inf or sup */) {
720	if (dictMode == ZSTD_dictMatchState) nbCompares = 0; /* break should also skip searching dms */
721	break; /* drop, to preserve bt consistency (miss a little bit of compression) */
722	} }
723
724	if (match[matchLength] < ip[matchLength]) {
725	/* match smaller than current */
726	*smallerPtr = matchIndex; /* update smaller idx */
727	commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
728	if (matchIndex <= btLow) { smallerPtr=&dummy32; break; } /* beyond tree size, stop the search */
729	smallerPtr = nextPtr+1; /* new candidate => larger than match, which was smaller than current */
730	matchIndex = nextPtr[1]; /* new matchIndex, larger than previous, closer to current */
731	} else {
732	*largerPtr = matchIndex;
733	commonLengthLarger = matchLength;
734	if (matchIndex <= btLow) { largerPtr=&dummy32; break; } /* beyond tree size, stop the search */
735	largerPtr = nextPtr;
736	matchIndex = nextPtr[0];
737	} }
738
739	*smallerPtr = *largerPtr = 0;
740
741	assert(nbCompares <= (1U << ZSTD_SEARCHLOG_MAX)); /* Check we haven't underflowed. */
742	if (dictMode == ZSTD_dictMatchState && nbCompares) {
743	size_t const dmsH = ZSTD_hashPtr(p: ip, hBits: dmsHashLog, mls);
744	U32 dictMatchIndex = dms->hashTable[dmsH];
745	const U32* const dmsBt = dms->chainTable;
746	commonLengthSmaller = commonLengthLarger = 0;
747	for (; nbCompares && (dictMatchIndex > dmsLowLimit); --nbCompares) {
748	const U32* const nextPtr = dmsBt + 2*(dictMatchIndex & dmsBtMask);
749	size_t matchLength = MIN(commonLengthSmaller, commonLengthLarger); /* guaranteed minimum nb of common bytes */
750	const BYTE* match = dmsBase + dictMatchIndex;
751	matchLength += ZSTD_count_2segments(ip: ip+matchLength, match: match+matchLength, iEnd: iLimit, mEnd: dmsEnd, iStart: prefixStart);
752	if (dictMatchIndex+matchLength >= dmsHighLimit)
753	match = base + dictMatchIndex + dmsIndexDelta; /* to prepare for next usage of match[matchLength] */
754
755	if (matchLength > bestLength) {
756	matchIndex = dictMatchIndex + dmsIndexDelta;
757	DEBUGLOG(8, "found dms match of length %u at distance %u (offCode=%u)",
758	(U32)matchLength, curr - matchIndex, STORE_OFFSET(curr - matchIndex));
759	if (matchLength > matchEndIdx - matchIndex)
760	matchEndIdx = matchIndex + (U32)matchLength;
761	bestLength = matchLength;
762	matches[mnum].off = STORE_OFFSET(curr - matchIndex);
763	matches[mnum].len = (U32)matchLength;
764	mnum++;
765	if ( (matchLength > ZSTD_OPT_NUM)
766	| (ip+matchLength == iLimit) /* equal : no way to know if inf or sup */) {
767	break; /* drop, to guarantee consistency (miss a little bit of compression) */
768	} }
769
770	if (dictMatchIndex <= dmsBtLow) { break; } /* beyond tree size, stop the search */
771	if (match[matchLength] < ip[matchLength]) {
772	commonLengthSmaller = matchLength; /* all smaller will now have at least this guaranteed common length */
773	dictMatchIndex = nextPtr[1]; /* new matchIndex larger than previous (closer to current) */
774	} else {
775	/* match is larger than current */
776	commonLengthLarger = matchLength;
777	dictMatchIndex = nextPtr[0];
778	} } } /* if (dictMode == ZSTD_dictMatchState) */
779
780	assert(matchEndIdx > curr+8);
781	ms->nextToUpdate = matchEndIdx - 8; /* skip repetitive patterns */
782	return mnum;
783	}
784
785	typedef U32 (*ZSTD_getAllMatchesFn)(
786	ZSTD_match_t*,
787	ZSTD_matchState_t*,
788	U32*,
789	const BYTE*,
790	const BYTE*,
791	const U32 rep[ZSTD_REP_NUM],
792	U32 const ll0,
793	U32 const lengthToBeat);
794
795	FORCE_INLINE_TEMPLATE U32 ZSTD_btGetAllMatches_internal(
796	ZSTD_match_t* matches,
797	ZSTD_matchState_t* ms,
798	U32* nextToUpdate3,
799	const BYTE* ip,
800	const BYTE* const iHighLimit,
801	const U32 rep[ZSTD_REP_NUM],
802	U32 const ll0,
803	U32 const lengthToBeat,
804	const ZSTD_dictMode_e dictMode,
805	const U32 mls)
806	{
807	assert(BOUNDED(3, ms->cParams.minMatch, 6) == mls);
808	DEBUGLOG(8, "ZSTD_BtGetAllMatches(dictMode=%d, mls=%u)", (int)dictMode, mls);
809	if (ip < ms->window.base + ms->nextToUpdate)
810	return 0; /* skipped area */
811	ZSTD_updateTree_internal(ms, ip, iend: iHighLimit, mls, dictMode);
812	return ZSTD_insertBtAndGetAllMatches(matches, ms, nextToUpdate3, ip, iLimit: iHighLimit, dictMode, rep, ll0, lengthToBeat, mls);
813	}
814
815	#define ZSTD_BT_GET_ALL_MATCHES_FN(dictMode, mls) ZSTD_btGetAllMatches_##dictMode##_##mls
816
817	#define GEN_ZSTD_BT_GET_ALL_MATCHES_(dictMode, mls) \
818	static U32 ZSTD_BT_GET_ALL_MATCHES_FN(dictMode, mls)( \
819	ZSTD_match_t* matches, \
820	ZSTD_matchState_t* ms, \
821	U32* nextToUpdate3, \
822	const BYTE* ip, \
823	const BYTE* const iHighLimit, \
824	const U32 rep[ZSTD_REP_NUM], \
825	U32 const ll0, \
826	U32 const lengthToBeat) \
827	{ \
828	return ZSTD_btGetAllMatches_internal( \
829	matches, ms, nextToUpdate3, ip, iHighLimit, \
830	rep, ll0, lengthToBeat, ZSTD_##dictMode, mls); \
831	}
832
833	#define GEN_ZSTD_BT_GET_ALL_MATCHES(dictMode) \
834	GEN_ZSTD_BT_GET_ALL_MATCHES_(dictMode, 3) \
835	GEN_ZSTD_BT_GET_ALL_MATCHES_(dictMode, 4) \
836	GEN_ZSTD_BT_GET_ALL_MATCHES_(dictMode, 5) \
837	GEN_ZSTD_BT_GET_ALL_MATCHES_(dictMode, 6)
838
839	GEN_ZSTD_BT_GET_ALL_MATCHES(noDict)
840	GEN_ZSTD_BT_GET_ALL_MATCHES(extDict)
841	GEN_ZSTD_BT_GET_ALL_MATCHES(dictMatchState)
842
843	#define ZSTD_BT_GET_ALL_MATCHES_ARRAY(dictMode) \
844	{ \
845	ZSTD_BT_GET_ALL_MATCHES_FN(dictMode, 3), \
846	ZSTD_BT_GET_ALL_MATCHES_FN(dictMode, 4), \
847	ZSTD_BT_GET_ALL_MATCHES_FN(dictMode, 5), \
848	ZSTD_BT_GET_ALL_MATCHES_FN(dictMode, 6) \
849	}
850
851	static ZSTD_getAllMatchesFn
852	ZSTD_selectBtGetAllMatches(ZSTD_matchState_t const* ms, ZSTD_dictMode_e const dictMode)
853	{
854	ZSTD_getAllMatchesFn const getAllMatchesFns[3][4] = {
855	ZSTD_BT_GET_ALL_MATCHES_ARRAY(noDict),
856	ZSTD_BT_GET_ALL_MATCHES_ARRAY(extDict),
857	ZSTD_BT_GET_ALL_MATCHES_ARRAY(dictMatchState)
858	};
859	U32 const mls = BOUNDED(3, ms->cParams.minMatch, 6);
860	assert((U32)dictMode < 3);
861	assert(mls - 3 < 4);
862	return getAllMatchesFns[(int)dictMode][mls - 3];
863	}
864
865	/* ***********************
866	* LDM helper functions *
867	*************************/
868
869	/* Struct containing info needed to make decision about ldm inclusion */
870	typedef struct {
871	rawSeqStore_t seqStore; /* External match candidates store for this block */
872	U32 startPosInBlock; /* Start position of the current match candidate */
873	U32 endPosInBlock; /* End position of the current match candidate */
874	U32 offset; /* Offset of the match candidate */
875	} ZSTD_optLdm_t;
876
877	/* ZSTD_optLdm_skipRawSeqStoreBytes():
878	* Moves forward in @rawSeqStore by @nbBytes,
879	* which will update the fields 'pos' and 'posInSequence'.
880	*/
881	static void ZSTD_optLdm_skipRawSeqStoreBytes(rawSeqStore_t* rawSeqStore, size_t nbBytes)
882	{
883	U32 currPos = (U32)(rawSeqStore->posInSequence + nbBytes);
884	while (currPos && rawSeqStore->pos < rawSeqStore->size) {
885	rawSeq currSeq = rawSeqStore->seq[rawSeqStore->pos];
886	if (currPos >= currSeq.litLength + currSeq.matchLength) {
887	currPos -= currSeq.litLength + currSeq.matchLength;
888	rawSeqStore->pos++;
889	} else {
890	rawSeqStore->posInSequence = currPos;
891	break;
892	}
893	}
894	if (currPos == 0 || rawSeqStore->pos == rawSeqStore->size) {
895	rawSeqStore->posInSequence = 0;
896	}
897	}
898
899	/* ZSTD_opt_getNextMatchAndUpdateSeqStore():
900	* Calculates the beginning and end of the next match in the current block.
901	* Updates 'pos' and 'posInSequence' of the ldmSeqStore.
902	*/
903	static void
904	ZSTD_opt_getNextMatchAndUpdateSeqStore(ZSTD_optLdm_t* optLdm, U32 currPosInBlock,
905	U32 blockBytesRemaining)
906	{
907	rawSeq currSeq;
908	U32 currBlockEndPos;
909	U32 literalsBytesRemaining;
910	U32 matchBytesRemaining;
911
912	/* Setting match end position to MAX to ensure we never use an LDM during this block */
913	if (optLdm->seqStore.size == 0 || optLdm->seqStore.pos >= optLdm->seqStore.size) {
914	optLdm->startPosInBlock = UINT_MAX;
915	optLdm->endPosInBlock = UINT_MAX;
916	return;
917	}
918	/* Calculate appropriate bytes left in matchLength and litLength
919	* after adjusting based on ldmSeqStore->posInSequence */
920	currSeq = optLdm->seqStore.seq[optLdm->seqStore.pos];
921	assert(optLdm->seqStore.posInSequence <= currSeq.litLength + currSeq.matchLength);
922	currBlockEndPos = currPosInBlock + blockBytesRemaining;
923	literalsBytesRemaining = (optLdm->seqStore.posInSequence < currSeq.litLength) ?
924	currSeq.litLength - (U32)optLdm->seqStore.posInSequence :
925	0;
926	matchBytesRemaining = (literalsBytesRemaining == 0) ?
927	currSeq.matchLength - ((U32)optLdm->seqStore.posInSequence - currSeq.litLength) :
928	currSeq.matchLength;
929
930	/* If there are more literal bytes than bytes remaining in block, no ldm is possible */
931	if (literalsBytesRemaining >= blockBytesRemaining) {
932	optLdm->startPosInBlock = UINT_MAX;
933	optLdm->endPosInBlock = UINT_MAX;
934	ZSTD_optLdm_skipRawSeqStoreBytes(rawSeqStore: &optLdm->seqStore, nbBytes: blockBytesRemaining);
935	return;
936	}
937
938	/* Matches may be < MINMATCH by this process. In that case, we will reject them
939	when we are deciding whether or not to add the ldm */
940	optLdm->startPosInBlock = currPosInBlock + literalsBytesRemaining;
941	optLdm->endPosInBlock = optLdm->startPosInBlock + matchBytesRemaining;
942	optLdm->offset = currSeq.offset;
943
944	if (optLdm->endPosInBlock > currBlockEndPos) {
945	/* Match ends after the block ends, we can't use the whole match */
946	optLdm->endPosInBlock = currBlockEndPos;
947	ZSTD_optLdm_skipRawSeqStoreBytes(rawSeqStore: &optLdm->seqStore, nbBytes: currBlockEndPos - currPosInBlock);
948	} else {
949	/* Consume nb of bytes equal to size of sequence left */
950	ZSTD_optLdm_skipRawSeqStoreBytes(rawSeqStore: &optLdm->seqStore, nbBytes: literalsBytesRemaining + matchBytesRemaining);
951	}
952	}
953
954	/* ZSTD_optLdm_maybeAddMatch():
955	* Adds a match if it's long enough,
956	* based on it's 'matchStartPosInBlock' and 'matchEndPosInBlock',
957	* into 'matches'. Maintains the correct ordering of 'matches'.
958	*/
959	static void ZSTD_optLdm_maybeAddMatch(ZSTD_match_t* matches, U32* nbMatches,
960	const ZSTD_optLdm_t* optLdm, U32 currPosInBlock)
961	{
962	U32 const posDiff = currPosInBlock - optLdm->startPosInBlock;
963	/* Note: ZSTD_match_t actually contains offCode and matchLength (before subtracting MINMATCH) */
964	U32 const candidateMatchLength = optLdm->endPosInBlock - optLdm->startPosInBlock - posDiff;
965
966	/* Ensure that current block position is not outside of the match */
967	if (currPosInBlock < optLdm->startPosInBlock
968	|| currPosInBlock >= optLdm->endPosInBlock
969	|| candidateMatchLength < MINMATCH) {
970	return;
971	}
972
973	if (*nbMatches == 0 || ((candidateMatchLength > matches[*nbMatches-1].len) && *nbMatches < ZSTD_OPT_NUM)) {
974	U32 const candidateOffCode = STORE_OFFSET(optLdm->offset);
975	DEBUGLOG(6, "ZSTD_optLdm_maybeAddMatch(): Adding ldm candidate match (offCode: %u matchLength %u) at block position=%u",
976	candidateOffCode, candidateMatchLength, currPosInBlock);
977	matches[*nbMatches].len = candidateMatchLength;
978	matches[*nbMatches].off = candidateOffCode;
979	(*nbMatches)++;
980	}
981	}
982
983	/* ZSTD_optLdm_processMatchCandidate():
984	* Wrapper function to update ldm seq store and call ldm functions as necessary.
985	*/
986	static void
987	ZSTD_optLdm_processMatchCandidate(ZSTD_optLdm_t* optLdm,
988	ZSTD_match_t* matches, U32* nbMatches,
989	U32 currPosInBlock, U32 remainingBytes)
990	{
991	if (optLdm->seqStore.size == 0 || optLdm->seqStore.pos >= optLdm->seqStore.size) {
992	return;
993	}
994
995	if (currPosInBlock >= optLdm->endPosInBlock) {
996	if (currPosInBlock > optLdm->endPosInBlock) {
997	/* The position at which ZSTD_optLdm_processMatchCandidate() is called is not necessarily
998	* at the end of a match from the ldm seq store, and will often be some bytes
999	* over beyond matchEndPosInBlock. As such, we need to correct for these "overshoots"
1000	*/
1001	U32 const posOvershoot = currPosInBlock - optLdm->endPosInBlock;
1002	ZSTD_optLdm_skipRawSeqStoreBytes(rawSeqStore: &optLdm->seqStore, nbBytes: posOvershoot);
1003	}
1004	ZSTD_opt_getNextMatchAndUpdateSeqStore(optLdm, currPosInBlock, blockBytesRemaining: remainingBytes);
1005	}
1006	ZSTD_optLdm_maybeAddMatch(matches, nbMatches, optLdm, currPosInBlock);
1007	}
1008
1009
1010	/*-*******************************
1011	* Optimal parser
1012	*********************************/
1013
1014	static U32 ZSTD_totalLen(ZSTD_optimal_t sol)
1015	{
1016	return sol.litlen + sol.mlen;
1017	}
1018
1019	#if 0 /* debug */
1020
1021	static void
1022	listStats(const U32* table, int lastEltID)
1023	{
1024	int const nbElts = lastEltID + 1;
1025	int enb;
1026	for (enb=0; enb < nbElts; enb++) {
1027	(void)table;
1028	/* RAWLOG(2, "%3i:%3i, ", enb, table[enb]); */
1029	RAWLOG(2, "%4i,", table[enb]);
1030	}
1031	RAWLOG(2, " \n");
1032	}
1033
1034	#endif
1035
1036	FORCE_INLINE_TEMPLATE size_t
1037	ZSTD_compressBlock_opt_generic(ZSTD_matchState_t* ms,
1038	seqStore_t* seqStore,
1039	U32 rep[ZSTD_REP_NUM],
1040	const void* src, size_t srcSize,
1041	const int optLevel,
1042	const ZSTD_dictMode_e dictMode)
1043	{
1044	optState_t* const optStatePtr = &ms->opt;
1045	const BYTE* const istart = (const BYTE*)src;
1046	const BYTE* ip = istart;
1047	const BYTE* anchor = istart;
1048	const BYTE* const iend = istart + srcSize;
1049	const BYTE* const ilimit = iend - 8;
1050	const BYTE* const base = ms->window.base;
1051	const BYTE* const prefixStart = base + ms->window.dictLimit;
1052	const ZSTD_compressionParameters* const cParams = &ms->cParams;
1053
1054	ZSTD_getAllMatchesFn getAllMatches = ZSTD_selectBtGetAllMatches(ms, dictMode);
1055
1056	U32 const sufficient_len = MIN(cParams->targetLength, ZSTD_OPT_NUM -1);
1057	U32 const minMatch = (cParams->minMatch == 3) ? 3 : 4;
1058	U32 nextToUpdate3 = ms->nextToUpdate;
1059
1060	ZSTD_optimal_t* const opt = optStatePtr->priceTable;
1061	ZSTD_match_t* const matches = optStatePtr->matchTable;
1062	ZSTD_optimal_t lastSequence;
1063	ZSTD_optLdm_t optLdm;
1064
1065	optLdm.seqStore = ms->ldmSeqStore ? *ms->ldmSeqStore : kNullRawSeqStore;
1066	optLdm.endPosInBlock = optLdm.startPosInBlock = optLdm.offset = 0;
1067	ZSTD_opt_getNextMatchAndUpdateSeqStore(optLdm: &optLdm, currPosInBlock: (U32)(ip-istart), blockBytesRemaining: (U32)(iend-ip));
1068
1069	/* init */
1070	DEBUGLOG(5, "ZSTD_compressBlock_opt_generic: current=%u, prefix=%u, nextToUpdate=%u",
1071	(U32)(ip - base), ms->window.dictLimit, ms->nextToUpdate);
1072	assert(optLevel <= 2);
1073	ZSTD_rescaleFreqs(optPtr: optStatePtr, src: (const BYTE*)src, srcSize, optLevel);
1074	ip += (ip==prefixStart);
1075
1076	/* Match Loop */
1077	while (ip < ilimit) {
1078	U32 cur, last_pos = 0;
1079
1080	/* find first match */
1081	{ U32 const litlen = (U32)(ip - anchor);
1082	U32 const ll0 = !litlen;
1083	U32 nbMatches = getAllMatches(matches, ms, &nextToUpdate3, ip, iend, rep, ll0, minMatch);
1084	ZSTD_optLdm_processMatchCandidate(optLdm: &optLdm, matches, nbMatches: &nbMatches,
1085	currPosInBlock: (U32)(ip-istart), remainingBytes: (U32)(iend - ip));
1086	if (!nbMatches) { ip++; continue; }
1087
1088	/* initialize opt[0] */
1089	{ U32 i ; for (i=0; i<ZSTD_REP_NUM; i++) opt[0].rep[i] = rep[i]; }
1090	opt[0].mlen = 0; /* means is_a_literal */
1091	opt[0].litlen = litlen;
1092	/* We don't need to include the actual price of the literals because
1093	* it is static for the duration of the forward pass, and is included
1094	* in every price. We include the literal length to avoid negative
1095	* prices when we subtract the previous literal length.
1096	*/
1097	opt[0].price = (int)ZSTD_litLengthPrice(litLength: litlen, optPtr: optStatePtr, optLevel);
1098
1099	/* large match -> immediate encoding */
1100	{ U32 const maxML = matches[nbMatches-1].len;
1101	U32 const maxOffcode = matches[nbMatches-1].off;
1102	DEBUGLOG(6, "found %u matches of maxLength=%u and maxOffCode=%u at cPos=%u => start new series",
1103	nbMatches, maxML, maxOffcode, (U32)(ip-prefixStart));
1104
1105	if (maxML > sufficient_len) {
1106	lastSequence.litlen = litlen;
1107	lastSequence.mlen = maxML;
1108	lastSequence.off = maxOffcode;
1109	DEBUGLOG(6, "large match (%u>%u), immediate encoding",
1110	maxML, sufficient_len);
1111	cur = 0;
1112	last_pos = ZSTD_totalLen(sol: lastSequence);
1113	goto _shortestPath;
1114	} }
1115
1116	/* set prices for first matches starting position == 0 */
1117	assert(opt[0].price >= 0);
1118	{ U32 const literalsPrice = (U32)opt[0].price + ZSTD_litLengthPrice(litLength: 0, optPtr: optStatePtr, optLevel);
1119	U32 pos;
1120	U32 matchNb;
1121	for (pos = 1; pos < minMatch; pos++) {
1122	opt[pos].price = ZSTD_MAX_PRICE; /* mlen, litlen and price will be fixed during forward scanning */
1123	}
1124	for (matchNb = 0; matchNb < nbMatches; matchNb++) {
1125	U32 const offcode = matches[matchNb].off;
1126	U32 const end = matches[matchNb].len;
1127	for ( ; pos <= end ; pos++ ) {
1128	U32 const matchPrice = ZSTD_getMatchPrice(offcode, matchLength: pos, optPtr: optStatePtr, optLevel);
1129	U32 const sequencePrice = literalsPrice + matchPrice;
1130	DEBUGLOG(7, "rPos:%u => set initial price : %.2f",
1131	pos, ZSTD_fCost(sequencePrice));
1132	opt[pos].mlen = pos;
1133	opt[pos].off = offcode;
1134	opt[pos].litlen = litlen;
1135	opt[pos].price = (int)sequencePrice;
1136	} }
1137	last_pos = pos-1;
1138	}
1139	}
1140
1141	/* check further positions */
1142	for (cur = 1; cur <= last_pos; cur++) {
1143	const BYTE* const inr = ip + cur;
1144	assert(cur < ZSTD_OPT_NUM);
1145	DEBUGLOG(7, "cPos:%zi==rPos:%u", inr-istart, cur)
1146
1147	/* Fix current position with one literal if cheaper */
1148	{ U32 const litlen = (opt[cur-1].mlen == 0) ? opt[cur-1].litlen + 1 : 1;
1149	int const price = opt[cur-1].price
1150	+ (int)ZSTD_rawLiteralsCost(literals: ip+cur-1, litLength: 1, optPtr: optStatePtr, optLevel)
1151	+ (int)ZSTD_litLengthPrice(litLength: litlen, optPtr: optStatePtr, optLevel)
1152	- (int)ZSTD_litLengthPrice(litLength: litlen-1, optPtr: optStatePtr, optLevel);
1153	assert(price < 1000000000); /* overflow check */
1154	if (price <= opt[cur].price) {
1155	DEBUGLOG(7, "cPos:%zi==rPos:%u : better price (%.2f<=%.2f) using literal (ll==%u) (hist:%u,%u,%u)",
1156	inr-istart, cur, ZSTD_fCost(price), ZSTD_fCost(opt[cur].price), litlen,
1157	opt[cur-1].rep[0], opt[cur-1].rep[1], opt[cur-1].rep[2]);
1158	opt[cur].mlen = 0;
1159	opt[cur].off = 0;
1160	opt[cur].litlen = litlen;
1161	opt[cur].price = price;
1162	} else {
1163	DEBUGLOG(7, "cPos:%zi==rPos:%u : literal would cost more (%.2f>%.2f) (hist:%u,%u,%u)",
1164	inr-istart, cur, ZSTD_fCost(price), ZSTD_fCost(opt[cur].price),
1165	opt[cur].rep[0], opt[cur].rep[1], opt[cur].rep[2]);
1166	}
1167	}
1168
1169	/* Set the repcodes of the current position. We must do it here
1170	* because we rely on the repcodes of the 2nd to last sequence being
1171	* correct to set the next chunks repcodes during the backward
1172	* traversal.
1173	*/
1174	ZSTD_STATIC_ASSERT(sizeof(opt[cur].rep) == sizeof(repcodes_t));
1175	assert(cur >= opt[cur].mlen);
1176	if (opt[cur].mlen != 0) {
1177	U32 const prev = cur - opt[cur].mlen;
1178	repcodes_t const newReps = ZSTD_newRep(rep: opt[prev].rep, offBase_minus1: opt[cur].off, ll0: opt[cur].litlen==0);
1179	ZSTD_memcpy(opt[cur].rep, &newReps, sizeof(repcodes_t));
1180	} else {
1181	ZSTD_memcpy(opt[cur].rep, opt[cur - 1].rep, sizeof(repcodes_t));
1182	}
1183
1184	/* last match must start at a minimum distance of 8 from oend */
1185	if (inr > ilimit) continue;
1186
1187	if (cur == last_pos) break;
1188
1189	if ( (optLevel==0) /*static_test*/
1190	&& (opt[cur+1].price <= opt[cur].price + (BITCOST_MULTIPLIER/2)) ) {
1191	DEBUGLOG(7, "move to next rPos:%u : price is <=", cur+1);
1192	continue; /* skip unpromising positions; about ~+6% speed, -0.01 ratio */
1193	}
1194
1195	assert(opt[cur].price >= 0);
1196	{ U32 const ll0 = (opt[cur].mlen != 0);
1197	U32 const litlen = (opt[cur].mlen == 0) ? opt[cur].litlen : 0;
1198	U32 const previousPrice = (U32)opt[cur].price;
1199	U32 const basePrice = previousPrice + ZSTD_litLengthPrice(litLength: 0, optPtr: optStatePtr, optLevel);
1200	U32 nbMatches = getAllMatches(matches, ms, &nextToUpdate3, inr, iend, opt[cur].rep, ll0, minMatch);
1201	U32 matchNb;
1202
1203	ZSTD_optLdm_processMatchCandidate(optLdm: &optLdm, matches, nbMatches: &nbMatches,
1204	currPosInBlock: (U32)(inr-istart), remainingBytes: (U32)(iend-inr));
1205
1206	if (!nbMatches) {
1207	DEBUGLOG(7, "rPos:%u : no match found", cur);
1208	continue;
1209	}
1210
1211	{ U32 const maxML = matches[nbMatches-1].len;
1212	DEBUGLOG(7, "cPos:%zi==rPos:%u, found %u matches, of maxLength=%u",
1213	inr-istart, cur, nbMatches, maxML);
1214
1215	if ( (maxML > sufficient_len)
1216	|| (cur + maxML >= ZSTD_OPT_NUM) ) {
1217	lastSequence.mlen = maxML;
1218	lastSequence.off = matches[nbMatches-1].off;
1219	lastSequence.litlen = litlen;
1220	cur -= (opt[cur].mlen==0) ? opt[cur].litlen : 0; /* last sequence is actually only literals, fix cur to last match - note : may underflow, in which case, it's first sequence, and it's okay */
1221	last_pos = cur + ZSTD_totalLen(sol: lastSequence);
1222	if (cur > ZSTD_OPT_NUM) cur = 0; /* underflow => first match */
1223	goto _shortestPath;
1224	} }
1225
1226	/* set prices using matches found at position == cur */
1227	for (matchNb = 0; matchNb < nbMatches; matchNb++) {
1228	U32 const offset = matches[matchNb].off;
1229	U32 const lastML = matches[matchNb].len;
1230	U32 const startML = (matchNb>0) ? matches[matchNb-1].len+1 : minMatch;
1231	U32 mlen;
1232
1233	DEBUGLOG(7, "testing match %u => offCode=%4u, mlen=%2u, llen=%2u",
1234	matchNb, matches[matchNb].off, lastML, litlen);
1235
1236	for (mlen = lastML; mlen >= startML; mlen--) { /* scan downward */
1237	U32 const pos = cur + mlen;
1238	int const price = (int)basePrice + (int)ZSTD_getMatchPrice(offcode: offset, matchLength: mlen, optPtr: optStatePtr, optLevel);
1239
1240	if ((pos > last_pos) || (price < opt[pos].price)) {
1241	DEBUGLOG(7, "rPos:%u (ml=%2u) => new better price (%.2f<%.2f)",
1242	pos, mlen, ZSTD_fCost(price), ZSTD_fCost(opt[pos].price));
1243	while (last_pos < pos) { opt[last_pos+1].price = ZSTD_MAX_PRICE; last_pos++; } /* fill empty positions */
1244	opt[pos].mlen = mlen;
1245	opt[pos].off = offset;
1246	opt[pos].litlen = litlen;
1247	opt[pos].price = price;
1248	} else {
1249	DEBUGLOG(7, "rPos:%u (ml=%2u) => new price is worse (%.2f>=%.2f)",
1250	pos, mlen, ZSTD_fCost(price), ZSTD_fCost(opt[pos].price));
1251	if (optLevel==0) break; /* early update abort; gets ~+10% speed for about -0.01 ratio loss */
1252	}
1253	} } }
1254	} /* for (cur = 1; cur <= last_pos; cur++) */
1255
1256	lastSequence = opt[last_pos];
1257	cur = last_pos > ZSTD_totalLen(sol: lastSequence) ? last_pos - ZSTD_totalLen(sol: lastSequence) : 0; /* single sequence, and it starts before `ip` */
1258	assert(cur < ZSTD_OPT_NUM); /* control overflow*/
1259
1260	_shortestPath: /* cur, last_pos, best_mlen, best_off have to be set */
1261	assert(opt[0].mlen == 0);
1262
1263	/* Set the next chunk's repcodes based on the repcodes of the beginning
1264	* of the last match, and the last sequence. This avoids us having to
1265	* update them while traversing the sequences.
1266	*/
1267	if (lastSequence.mlen != 0) {
1268	repcodes_t const reps = ZSTD_newRep(rep: opt[cur].rep, offBase_minus1: lastSequence.off, ll0: lastSequence.litlen==0);
1269	ZSTD_memcpy(rep, &reps, sizeof(reps));
1270	} else {
1271	ZSTD_memcpy(rep, opt[cur].rep, sizeof(repcodes_t));
1272	}
1273
1274	{ U32 const storeEnd = cur + 1;
1275	U32 storeStart = storeEnd;
1276	U32 seqPos = cur;
1277
1278	DEBUGLOG(6, "start reverse traversal (last_pos:%u, cur:%u)",
1279	last_pos, cur); (void)last_pos;
1280	assert(storeEnd < ZSTD_OPT_NUM);
1281	DEBUGLOG(6, "last sequence copied into pos=%u (llen=%u,mlen=%u,ofc=%u)",
1282	storeEnd, lastSequence.litlen, lastSequence.mlen, lastSequence.off);
1283	opt[storeEnd] = lastSequence;
1284	while (seqPos > 0) {
1285	U32 const backDist = ZSTD_totalLen(sol: opt[seqPos]);
1286	storeStart--;
1287	DEBUGLOG(6, "sequence from rPos=%u copied into pos=%u (llen=%u,mlen=%u,ofc=%u)",
1288	seqPos, storeStart, opt[seqPos].litlen, opt[seqPos].mlen, opt[seqPos].off);
1289	opt[storeStart] = opt[seqPos];
1290	seqPos = (seqPos > backDist) ? seqPos - backDist : 0;
1291	}
1292
1293	/* save sequences */
1294	DEBUGLOG(6, "sending selected sequences into seqStore")
1295	{ U32 storePos;
1296	for (storePos=storeStart; storePos <= storeEnd; storePos++) {
1297	U32 const llen = opt[storePos].litlen;
1298	U32 const mlen = opt[storePos].mlen;
1299	U32 const offCode = opt[storePos].off;
1300	U32 const advance = llen + mlen;
1301	DEBUGLOG(6, "considering seq starting at %zi, llen=%u, mlen=%u",
1302	anchor - istart, (unsigned)llen, (unsigned)mlen);
1303
1304	if (mlen==0) { /* only literals => must be last "sequence", actually starting a new stream of sequences */
1305	assert(storePos == storeEnd); /* must be last sequence */
1306	ip = anchor + llen; /* last "sequence" is a bunch of literals => don't progress anchor */
1307	continue; /* will finish */
1308	}
1309
1310	assert(anchor + llen <= iend);
1311	ZSTD_updateStats(optPtr: optStatePtr, litLength: llen, literals: anchor, offsetCode: offCode, matchLength: mlen);
1312	ZSTD_storeSeq(seqStorePtr: seqStore, litLength: llen, literals: anchor, litLimit: iend, offBase_minus1: offCode, matchLength: mlen);
1313	anchor += advance;
1314	ip = anchor;
1315	} }
1316	ZSTD_setBasePrices(optPtr: optStatePtr, optLevel);
1317	}
1318	} /* while (ip < ilimit) */
1319
1320	/* Return the last literals size */
1321	return (size_t)(iend - anchor);
1322	}
1323
1324	static size_t ZSTD_compressBlock_opt0(
1325	ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1326	const void* src, size_t srcSize, const ZSTD_dictMode_e dictMode)
1327	{
1328	return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, optLevel: 0 /* optLevel */, dictMode);
1329	}
1330
1331	static size_t ZSTD_compressBlock_opt2(
1332	ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1333	const void* src, size_t srcSize, const ZSTD_dictMode_e dictMode)
1334	{
1335	return ZSTD_compressBlock_opt_generic(ms, seqStore, rep, src, srcSize, optLevel: 2 /* optLevel */, dictMode);
1336	}
1337
1338	size_t ZSTD_compressBlock_btopt(
1339	ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1340	const void* src, size_t srcSize)
1341	{
1342	DEBUGLOG(5, "ZSTD_compressBlock_btopt");
1343	return ZSTD_compressBlock_opt0(ms, seqStore, rep, src, srcSize, dictMode: ZSTD_noDict);
1344	}
1345
1346
1347
1348
1349	/* ZSTD_initStats_ultra():
1350	* make a first compression pass, just to seed stats with more accurate starting values.
1351	* only works on first block, with no dictionary and no ldm.
1352	* this function cannot error, hence its contract must be respected.
1353	*/
1354	static void
1355	ZSTD_initStats_ultra(ZSTD_matchState_t* ms,
1356	seqStore_t* seqStore,
1357	U32 rep[ZSTD_REP_NUM],
1358	const void* src, size_t srcSize)
1359	{
1360	U32 tmpRep[ZSTD_REP_NUM]; /* updated rep codes will sink here */
1361	ZSTD_memcpy(tmpRep, rep, sizeof(tmpRep));
1362
1363	DEBUGLOG(4, "ZSTD_initStats_ultra (srcSize=%zu)", srcSize);
1364	assert(ms->opt.litLengthSum == 0); /* first block */
1365	assert(seqStore->sequences == seqStore->sequencesStart); /* no ldm */
1366	assert(ms->window.dictLimit == ms->window.lowLimit); /* no dictionary */
1367	assert(ms->window.dictLimit - ms->nextToUpdate <= 1); /* no prefix (note: intentional overflow, defined as 2-complement) */
1368
1369	ZSTD_compressBlock_opt2(ms, seqStore, rep: tmpRep, src, srcSize, dictMode: ZSTD_noDict); /* generate stats into ms->opt*/
1370
1371	/* invalidate first scan from history */
1372	ZSTD_resetSeqStore(ssPtr: seqStore);
1373	ms->window.base -= srcSize;
1374	ms->window.dictLimit += (U32)srcSize;
1375	ms->window.lowLimit = ms->window.dictLimit;
1376	ms->nextToUpdate = ms->window.dictLimit;
1377
1378	}
1379
1380	size_t ZSTD_compressBlock_btultra(
1381	ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1382	const void* src, size_t srcSize)
1383	{
1384	DEBUGLOG(5, "ZSTD_compressBlock_btultra (srcSize=%zu)", srcSize);
1385	return ZSTD_compressBlock_opt2(ms, seqStore, rep, src, srcSize, dictMode: ZSTD_noDict);
1386	}
1387
1388	size_t ZSTD_compressBlock_btultra2(
1389	ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1390	const void* src, size_t srcSize)
1391	{
1392	U32 const curr = (U32)((const BYTE*)src - ms->window.base);
1393	DEBUGLOG(5, "ZSTD_compressBlock_btultra2 (srcSize=%zu)", srcSize);
1394
1395	/* 2-pass strategy:
1396	* this strategy makes a first pass over first block to collect statistics
1397	* and seed next round's statistics with it.
1398	* After 1st pass, function forgets everything, and starts a new block.
1399	* Consequently, this can only work if no data has been previously loaded in tables,
1400	* aka, no dictionary, no prefix, no ldm preprocessing.
1401	* The compression ratio gain is generally small (~0.5% on first block),
1402	* the cost is 2x cpu time on first block. */
1403	assert(srcSize <= ZSTD_BLOCKSIZE_MAX);
1404	if ( (ms->opt.litLengthSum==0) /* first block */
1405	&& (seqStore->sequences == seqStore->sequencesStart) /* no ldm */
1406	&& (ms->window.dictLimit == ms->window.lowLimit) /* no dictionary */
1407	&& (curr == ms->window.dictLimit) /* start of frame, nothing already loaded nor skipped */
1408	&& (srcSize > ZSTD_PREDEF_THRESHOLD)
1409	) {
1410	ZSTD_initStats_ultra(ms, seqStore, rep, src, srcSize);
1411	}
1412
1413	return ZSTD_compressBlock_opt2(ms, seqStore, rep, src, srcSize, dictMode: ZSTD_noDict);
1414	}
1415
1416	size_t ZSTD_compressBlock_btopt_dictMatchState(
1417	ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1418	const void* src, size_t srcSize)
1419	{
1420	return ZSTD_compressBlock_opt0(ms, seqStore, rep, src, srcSize, dictMode: ZSTD_dictMatchState);
1421	}
1422
1423	size_t ZSTD_compressBlock_btultra_dictMatchState(
1424	ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1425	const void* src, size_t srcSize)
1426	{
1427	return ZSTD_compressBlock_opt2(ms, seqStore, rep, src, srcSize, dictMode: ZSTD_dictMatchState);
1428	}
1429
1430	size_t ZSTD_compressBlock_btopt_extDict(
1431	ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1432	const void* src, size_t srcSize)
1433	{
1434	return ZSTD_compressBlock_opt0(ms, seqStore, rep, src, srcSize, dictMode: ZSTD_extDict);
1435	}
1436
1437	size_t ZSTD_compressBlock_btultra_extDict(
1438	ZSTD_matchState_t* ms, seqStore_t* seqStore, U32 rep[ZSTD_REP_NUM],
1439	const void* src, size_t srcSize)
1440	{
1441	return ZSTD_compressBlock_opt2(ms, seqStore, rep, src, srcSize, dictMode: ZSTD_extDict);
1442	}
1443
1444	/* note : no btultra2 variant for extDict nor dictMatchState,
1445	* because btultra2 is not meant to work with dictionaries
1446	* and is only specific for the first block (no prefix) */
1447