WebSVN – Games.Chess Giants – Blame – /engine-texel/gtb/compression/lzma/LzFind.c

Rev	Author	Line No.	Line
99	pmbaty	1	/* LzFind.c -- Match finder for LZ algorithms
		2	2008-10-04 : Igor Pavlov : Public domain */
		3
		4	#include <string.h>
		5
		6	#include "LzFind.h"
		7	#include "LzHash.h"
		8
		9	#define kEmptyHashValue 0
		10	#define kMaxValForNormalize ((UInt32)0xFFFFFFFF)
		11	#define kNormalizeStepMin (1u << 10) /* it must be power of 2 / /MAB 1u */
		12	#define kNormalizeMask (~(kNormalizeStepMin - 1))
		13	#define kMaxHistorySize ((UInt32)3 << 30)
		14
		15	#define kStartMaxLen 3
		16
		17	static void LzInWindow_Free(CMatchFinder p, ISzAlloc alloc)
		18	{
		19	if (!p->directInput)
		20	{
		21	alloc->Free(alloc, p->bufferBase);
		22	p->bufferBase = 0;
		23	}
		24	}
		25
		26	/* keepSizeBefore + keepSizeAfter + keepSizeReserv must be < 4G) */
		27
		28	static int LzInWindow_Create(CMatchFinder p, UInt32 keepSizeReserv, ISzAlloc alloc)
		29	{
		30	UInt32 blockSize = p->keepSizeBefore + p->keepSizeAfter + keepSizeReserv;
		31	if (p->directInput)
		32	{
		33	p->blockSize = blockSize;
		34	return 1;
		35	}
		36	if (p->bufferBase == 0 \|\| p->blockSize != blockSize)
		37	{
		38	LzInWindow_Free(p, alloc);
		39	p->blockSize = blockSize;
		40	p->bufferBase = (Byte *)alloc->Alloc(alloc, (size_t)blockSize);
		41	}
		42	return (p->bufferBase != 0);
		43	}
		44
		45	Byte MatchFinder_GetPointerToCurrentPos(CMatchFinder p) { return p->buffer; }
		46
		47	/MAB: static added, index replaced by idx to avoid shadowing a global variable /
		48	static
		49	Byte MatchFinder_GetIndexByte(CMatchFinder *p, Int32 idx) { return p->buffer[idx]; }
		50
		51	/MAB: static added /
		52	static
		53	UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return p->streamPos - p->pos; }
		54
		55	void MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue)
		56	{
		57	p->posLimit -= subValue;
		58	p->pos -= subValue;
		59	p->streamPos -= subValue;
		60	}
		61
		62	static void MatchFinder_ReadBlock(CMatchFinder *p)
		63	{
		64	if (p->streamEndWasReached \|\| p->result != SZ_OK)
		65	return;
		66	for (;;)
		67	{
		68	Byte *dest = p->buffer + (p->streamPos - p->pos);
		69	size_t size = (size_t)(p->bufferBase + p->blockSize - dest);
		70	if (size == 0)
		71	return;
		72	p->result = p->stream->Read(p->stream, dest, &size);
		73	if (p->result != SZ_OK)
		74	return;
		75	if (size == 0)
		76	{
		77	p->streamEndWasReached = 1;
		78	return;
		79	}
		80	p->streamPos += (UInt32)size;
		81	if (p->streamPos - p->pos > p->keepSizeAfter)
		82	return;
		83	}
		84	}
		85
		86	void MatchFinder_MoveBlock(CMatchFinder *p)
		87	{
		88	memmove(p->bufferBase,
		89	p->buffer - p->keepSizeBefore,
		90	(size_t)(p->streamPos - p->pos + p->keepSizeBefore));
		91	p->buffer = p->bufferBase + p->keepSizeBefore;
		92	}
		93
		94	int MatchFinder_NeedMove(CMatchFinder *p)
		95	{
		96	/* if (p->streamEndWasReached) return 0; */
		97	return ((size_t)(p->bufferBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
		98	}
		99
		100	void MatchFinder_ReadIfRequired(CMatchFinder *p)
		101	{
		102	if (p->streamEndWasReached)
		103	return;
		104	if (p->keepSizeAfter >= p->streamPos - p->pos)
		105	MatchFinder_ReadBlock(p);
		106	}
		107
		108	static void MatchFinder_CheckAndMoveAndRead(CMatchFinder *p)
		109	{
		110	if (MatchFinder_NeedMove(p))
		111	MatchFinder_MoveBlock(p);
		112	MatchFinder_ReadBlock(p);
		113	}
		114
		115	static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
		116	{
		117	p->cutValue = 32;
		118	p->btMode = 1;
		119	p->numHashBytes = 4;
		120	/* p->skipModeBits = 0; */
		121	p->directInput = 0;
		122	p->bigHash = 0;
		123	}
		124
		125	#define kCrcPoly 0xEDB88320
		126
		127	void MatchFinder_Construct(CMatchFinder *p)
		128	{
		129	UInt32 i;
		130	p->bufferBase = 0;
		131	p->directInput = 0;
		132	p->hash = 0;
		133	MatchFinder_SetDefaultSettings(p);
		134
		135	for (i = 0; i < 256; i++)
		136	{
		137	UInt32 r = i;
		138	int j;
		139	for (j = 0; j < 8; j++)
		140	r = (r >> 1) ^ (kCrcPoly & ~((r & 1) - 1));
		141	p->crc[i] = r;
		142	}
		143	}
		144
		145	static void MatchFinder_FreeThisClassMemory(CMatchFinder p, ISzAlloc alloc)
		146	{
		147	alloc->Free(alloc, p->hash);
		148	p->hash = 0;
		149	}
		150
		151	void MatchFinder_Free(CMatchFinder p, ISzAlloc alloc)
		152	{
		153	MatchFinder_FreeThisClassMemory(p, alloc);
		154	LzInWindow_Free(p, alloc);
		155	}
		156
		157	static CLzRef* AllocRefs(UInt32 num, ISzAlloc *alloc)
		158	{
		159	size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
		160	if (sizeInBytes / sizeof(CLzRef) != num)
		161	return 0;
		162	return (CLzRef *)alloc->Alloc(alloc, sizeInBytes);
		163	}
		164
		165	int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
		166	UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
		167	ISzAlloc *alloc)
		168	{
		169	UInt32 sizeReserv;
		170	if (historySize > kMaxHistorySize)
		171	{
		172	MatchFinder_Free(p, alloc);
		173	return 0;
		174	}
		175	sizeReserv = historySize >> 1;
		176	if (historySize > ((UInt32)2 << 30))
		177	sizeReserv = historySize >> 2;
		178	sizeReserv += (keepAddBufferBefore + matchMaxLen + keepAddBufferAfter) / 2 + (1 << 19);
		179
		180	p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
		181	p->keepSizeAfter = matchMaxLen + keepAddBufferAfter;
		182	/* we need one additional byte, since we use MoveBlock after pos++ and before dictionary using */
		183	if (LzInWindow_Create(p, sizeReserv, alloc))
		184	{
		185	UInt32 newCyclicBufferSize = (historySize /* >> p->skipModeBits */) + 1;
		186	UInt32 hs;
		187	p->matchMaxLen = matchMaxLen;
		188	{
		189	p->fixedHashSize = 0;
		190	if (p->numHashBytes == 2)
		191	hs = (1 << 16) - 1;
		192	else
		193	{
		194	hs = historySize - 1;
		195	hs \|= (hs >> 1);
		196	hs \|= (hs >> 2);
		197	hs \|= (hs >> 4);
		198	hs \|= (hs >> 8);
		199	hs >>= 1;
		200	/* hs >>= p->skipModeBits; */
		201	hs \|= 0xFFFF; /* don't change it! It's required for Deflate */
		202	if (hs > (1 << 24))
		203	{
		204	if (p->numHashBytes == 3)
		205	hs = (1 << 24) - 1;
		206	else
		207	hs >>= 1;
		208	}
		209	}
		210	p->hashMask = hs;
		211	hs++;
		212	if (p->numHashBytes > 2) p->fixedHashSize += kHash2Size;
		213	if (p->numHashBytes > 3) p->fixedHashSize += kHash3Size;
		214	if (p->numHashBytes > 4) p->fixedHashSize += kHash4Size;
		215	hs += p->fixedHashSize;
		216	}
		217
		218	{
		219	UInt32 prevSize = p->hashSizeSum + p->numSons;
		220	UInt32 newSize;
		221	p->historySize = historySize;
		222	p->hashSizeSum = hs;
		223	p->cyclicBufferSize = newCyclicBufferSize;
		224	p->numSons = (p->btMode ? newCyclicBufferSize * 2 : newCyclicBufferSize);
		225	newSize = p->hashSizeSum + p->numSons;
		226	if (p->hash != 0 && prevSize == newSize)
		227	return 1;
		228	MatchFinder_FreeThisClassMemory(p, alloc);
		229	p->hash = AllocRefs(newSize, alloc);
		230	if (p->hash != 0)
		231	{
		232	p->son = p->hash + p->hashSizeSum;
		233	return 1;
		234	}
		235	}
		236	}
		237	MatchFinder_Free(p, alloc);
		238	return 0;
		239	}
		240
		241	static void MatchFinder_SetLimits(CMatchFinder *p)
		242	{
		243	UInt32 limit = kMaxValForNormalize - p->pos;
		244	UInt32 limit2 = p->cyclicBufferSize - p->cyclicBufferPos;
		245	if (limit2 < limit)
		246	limit = limit2;
		247	limit2 = p->streamPos - p->pos;
		248	if (limit2 <= p->keepSizeAfter)
		249	{
		250	if (limit2 > 0)
		251	limit2 = 1;
		252	}
		253	else
		254	limit2 -= p->keepSizeAfter;
		255	if (limit2 < limit)
		256	limit = limit2;
		257	{
		258	UInt32 lenLimit = p->streamPos - p->pos;
		259	if (lenLimit > p->matchMaxLen)
		260	lenLimit = p->matchMaxLen;
		261	p->lenLimit = lenLimit;
		262	}
		263	p->posLimit = p->pos + limit;
		264	}
		265
		266	void MatchFinder_Init(CMatchFinder *p)
		267	{
		268	UInt32 i;
		269	for (i = 0; i < p->hashSizeSum; i++)
		270	p->hash[i] = kEmptyHashValue;
		271	p->cyclicBufferPos = 0;
		272	p->buffer = p->bufferBase;
		273	p->pos = p->streamPos = p->cyclicBufferSize;
		274	p->result = SZ_OK;
		275	p->streamEndWasReached = 0;
		276	MatchFinder_ReadBlock(p);
		277	MatchFinder_SetLimits(p);
		278	}
		279
		280	static UInt32 MatchFinder_GetSubValue(CMatchFinder *p)
		281	{
		282	return (p->pos - p->historySize - 1) & kNormalizeMask;
		283	}
		284
		285	void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems)
		286	{
		287	UInt32 i;
		288	for (i = 0; i < numItems; i++)
		289	{
		290	UInt32 value = items[i];
		291	if (value <= subValue)
		292	value = kEmptyHashValue;
		293	else
		294	value -= subValue;
		295	items[i] = value;
		296	}
		297	}
		298
		299	static void MatchFinder_Normalize(CMatchFinder *p)
		300	{
		301	UInt32 subValue = MatchFinder_GetSubValue(p);
		302	MatchFinder_Normalize3(subValue, p->hash, p->hashSizeSum + p->numSons);
		303	MatchFinder_ReduceOffsets(p, subValue);
		304	}
		305
		306	static void MatchFinder_CheckLimits(CMatchFinder *p)
		307	{
		308	if (p->pos == kMaxValForNormalize)
		309	MatchFinder_Normalize(p);
		310
		311	if (!p->streamEndWasReached && p->keepSizeAfter == p->streamPos - p->pos)
		312	MatchFinder_CheckAndMoveAndRead(p);
		313	if (p->cyclicBufferPos == p->cyclicBufferSize)
		314	p->cyclicBufferPos = 0;
		315	MatchFinder_SetLimits(p);
		316	}
		317
		318	static UInt32 * Hc_GetMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte cur, CLzRef son,
		319	UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
		320	UInt32 *distances, UInt32 maxLen)
		321	{
		322	son[_cyclicBufferPos] = curMatch;
		323	for (;;)
		324	{
		325	UInt32 delta = pos - curMatch;
		326	if (cutValue-- == 0 \|\| delta >= _cyclicBufferSize)
		327	return distances;
		328	{
		329	const Byte *pb = cur - delta;
		330	curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
		331	if (pb[maxLen] == cur[maxLen] && pb == cur)
		332	{
		333	UInt32 len = 0;
		334	while (++len != lenLimit)
		335	if (pb[len] != cur[len])
		336	break;
		337	if (maxLen < len)
		338	{
		339	*distances++ = maxLen = len;
		340	*distances++ = delta - 1;
		341	if (len == lenLimit)
		342	return distances;
		343	}
		344	}
		345	}
		346	}
		347	}
		348
		349	UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte cur, CLzRef son,
		350	UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
		351	UInt32 *distances, UInt32 maxLen)
		352	{
		353	CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
		354	CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
		355	UInt32 len0 = 0, len1 = 0;
		356	for (;;)
		357	{
		358	UInt32 delta = pos - curMatch;
		359	if (cutValue-- == 0 \|\| delta >= _cyclicBufferSize)
		360	{
		361	ptr0 = ptr1 = kEmptyHashValue;
		362	return distances;
		363	}
		364	{
		365	CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
		366	const Byte *pb = cur - delta;
		367	UInt32 len = (len0 < len1 ? len0 : len1);
		368	if (pb[len] == cur[len])
		369	{
		370	if (++len != lenLimit && pb[len] == cur[len])
		371	while (++len != lenLimit)
		372	if (pb[len] != cur[len])
		373	break;
		374	if (maxLen < len)
		375	{
		376	*distances++ = maxLen = len;
		377	*distances++ = delta - 1;
		378	if (len == lenLimit)
		379	{
		380	*ptr1 = pair[0];
		381	*ptr0 = pair[1];
		382	return distances;
		383	}
		384	}
		385	}
		386	if (pb[len] < cur[len])
		387	{
		388	*ptr1 = curMatch;
		389	ptr1 = pair + 1;
		390	curMatch = *ptr1;
		391	len1 = len;
		392	}
		393	else
		394	{
		395	*ptr0 = curMatch;
		396	ptr0 = pair;
		397	curMatch = *ptr0;
		398	len0 = len;
		399	}
		400	}
		401	}
		402	}
		403
		404	static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte cur, CLzRef son,
		405	UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
		406	{
		407	CLzRef *ptr0 = son + (_cyclicBufferPos << 1) + 1;
		408	CLzRef *ptr1 = son + (_cyclicBufferPos << 1);
		409	UInt32 len0 = 0, len1 = 0;
		410	for (;;)
		411	{
		412	UInt32 delta = pos - curMatch;
		413	if (cutValue-- == 0 \|\| delta >= _cyclicBufferSize)
		414	{
		415	ptr0 = ptr1 = kEmptyHashValue;
		416	return;
		417	}
		418	{
		419	CLzRef *pair = son + ((_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
		420	const Byte *pb = cur - delta;
		421	UInt32 len = (len0 < len1 ? len0 : len1);
		422	if (pb[len] == cur[len])
		423	{
		424	while (++len != lenLimit)
		425	if (pb[len] != cur[len])
		426	break;
		427	{
		428	if (len == lenLimit)
		429	{
		430	*ptr1 = pair[0];
		431	*ptr0 = pair[1];
		432	return;
		433	}
		434	}
		435	}
		436	if (pb[len] < cur[len])
		437	{
		438	*ptr1 = curMatch;
		439	ptr1 = pair + 1;
		440	curMatch = *ptr1;
		441	len1 = len;
		442	}
		443	else
		444	{
		445	*ptr0 = curMatch;
		446	ptr0 = pair;
		447	curMatch = *ptr0;
		448	len0 = len;
		449	}
		450	}
		451	}
		452	}
		453
		454	#define MOVE_POS \
		455	++p->cyclicBufferPos; \
		456	p->buffer++; \
		457	if (++p->pos == p->posLimit) MatchFinder_CheckLimits(p);
		458
		459	#define MOVE_POS_RET MOVE_POS return offset;
		460
		461	static void MatchFinder_MovePos(CMatchFinder *p) { MOVE_POS; }
		462
		463	#define GET_MATCHES_HEADER2(minLen, ret_op) \
		464	UInt32 lenLimit; UInt32 hashValue; const Byte *cur; UInt32 curMatch; \
		465	lenLimit = p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
		466	cur = p->buffer;
		467
		468	#define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return 0)
		469	#define SKIP_HEADER(minLen) GET_MATCHES_HEADER2(minLen, continue)
		470
		471	#define MF_PARAMS(p) p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
		472
		473	#define GET_MATCHES_FOOTER(offset, maxLen) \
		474	offset = (UInt32)(GetMatchesSpec1(lenLimit, curMatch, MF_PARAMS(p), \
		475	distances + offset, maxLen) - distances); MOVE_POS_RET;
		476
		477	#define SKIP_FOOTER \
		478	SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p)); MOVE_POS;
		479
		480	static UInt32 Bt2_MatchFinder_GetMatches(CMatchFinder p, UInt32 distances)
		481	{
		482	UInt32 offset;
		483	GET_MATCHES_HEADER(2)
		484	HASH2_CALC;
		485	curMatch = p->hash[hashValue];
		486	p->hash[hashValue] = p->pos;
		487	offset = 0;
		488	GET_MATCHES_FOOTER(offset, 1)
		489	}
		490
		491	UInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder p, UInt32 distances)
		492	{
		493	UInt32 offset;
		494	GET_MATCHES_HEADER(3)
		495	HASH_ZIP_CALC;
		496	curMatch = p->hash[hashValue];
		497	p->hash[hashValue] = p->pos;
		498	offset = 0;
		499	GET_MATCHES_FOOTER(offset, 2)
		500	}
		501
		502	static UInt32 Bt3_MatchFinder_GetMatches(CMatchFinder p, UInt32 distances)
		503	{
		504	UInt32 hash2Value, delta2, maxLen, offset;
		505	GET_MATCHES_HEADER(3)
		506
		507	HASH3_CALC;
		508
		509	delta2 = p->pos - p->hash[hash2Value];
		510	curMatch = p->hash[kFix3HashSize + hashValue];
		511
		512	p->hash[hash2Value] =
		513	p->hash[kFix3HashSize + hashValue] = p->pos;
		514
		515
		516	maxLen = 2;
		517	offset = 0;
		518	if (delta2 < p->cyclicBufferSize && (cur - delta2) == cur)
		519	{
		520	for (; maxLen != lenLimit; maxLen++)
		521	if (cur[(ptrdiff_t)maxLen - (ptrdiff_t)delta2] != cur[maxLen]) /MAB second casts (ptrdiff_t)/
		522	break;
		523	distances[0] = maxLen;
		524	distances[1] = delta2 - 1;
		525	offset = 2;
		526	if (maxLen == lenLimit)
		527	{
		528	SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
		529	MOVE_POS_RET;
		530	}
		531	}
		532	GET_MATCHES_FOOTER(offset, maxLen)
		533	}
		534
		535	static UInt32 Bt4_MatchFinder_GetMatches(CMatchFinder p, UInt32 distances)
		536	{
		537	UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
		538	GET_MATCHES_HEADER(4)
		539
		540	HASH4_CALC;
		541
		542	delta2 = p->pos - p->hash[ hash2Value];
		543	delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
		544	curMatch = p->hash[kFix4HashSize + hashValue];
		545
		546	p->hash[ hash2Value] =
		547	p->hash[kFix3HashSize + hash3Value] =
		548	p->hash[kFix4HashSize + hashValue] = p->pos;
		549
		550	maxLen = 1;
		551	offset = 0;
		552	if (delta2 < p->cyclicBufferSize && (cur - delta2) == cur)
		553	{
		554	distances[0] = maxLen = 2;
		555	distances[1] = delta2 - 1;
		556	offset = 2;
		557	}
		558	if (delta2 != delta3 && delta3 < p->cyclicBufferSize && (cur - delta3) == cur)
		559	{
		560	maxLen = 3;
		561	distances[offset + 1] = delta3 - 1;
		562	offset += 2;
		563	delta2 = delta3;
		564	}
		565	if (offset != 0)
		566	{
		567	for (; maxLen != lenLimit; maxLen++)
		568	if (cur[(ptrdiff_t)maxLen - (ptrdiff_t)delta2] != cur[maxLen]) /MAB casts second (ptrdiff_t)/
		569	break;
		570	distances[offset - 2] = maxLen;
		571	if (maxLen == lenLimit)
		572	{
		573	SkipMatchesSpec(lenLimit, curMatch, MF_PARAMS(p));
		574	MOVE_POS_RET;
		575	}
		576	}
		577	if (maxLen < 3)
		578	maxLen = 3;
		579	GET_MATCHES_FOOTER(offset, maxLen)
		580	}
		581
		582	static UInt32 Hc4_MatchFinder_GetMatches(CMatchFinder p, UInt32 distances)
		583	{
		584	UInt32 hash2Value, hash3Value, delta2, delta3, maxLen, offset;
		585	GET_MATCHES_HEADER(4)
		586
		587	HASH4_CALC;
		588
		589	delta2 = p->pos - p->hash[ hash2Value];
		590	delta3 = p->pos - p->hash[kFix3HashSize + hash3Value];
		591	curMatch = p->hash[kFix4HashSize + hashValue];
		592
		593	p->hash[ hash2Value] =
		594	p->hash[kFix3HashSize + hash3Value] =
		595	p->hash[kFix4HashSize + hashValue] = p->pos;
		596
		597	maxLen = 1;
		598	offset = 0;
		599	if (delta2 < p->cyclicBufferSize && (cur - delta2) == cur)
		600	{
		601	distances[0] = maxLen = 2;
		602	distances[1] = delta2 - 1;
		603	offset = 2;
		604	}
		605	if (delta2 != delta3 && delta3 < p->cyclicBufferSize && (cur - delta3) == cur)
		606	{
		607	maxLen = 3;
		608	distances[offset + 1] = delta3 - 1;
		609	offset += 2;
		610	delta2 = delta3;
		611	}
		612	if (offset != 0)
		613	{
		614	for (; maxLen != lenLimit; maxLen++)
		615	if (cur[(ptrdiff_t)maxLen - (ptrdiff_t)delta2] != cur[maxLen]) /MAB casts second (ptrdiff_t) /
		616	break;
		617
		618	distances[offset - 2] = maxLen;
		619	if (maxLen == lenLimit)
		620	{
		621	p->son[p->cyclicBufferPos] = curMatch;
		622	MOVE_POS_RET;
		623	}
		624	}
		625	if (maxLen < 3)
		626	maxLen = 3;
		627	offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
		628	distances + offset, maxLen) - (distances));
		629	MOVE_POS_RET
		630	}
		631
		632	UInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder p, UInt32 distances)
		633	{
		634	UInt32 offset;
		635	GET_MATCHES_HEADER(3)
		636	HASH_ZIP_CALC;
		637	curMatch = p->hash[hashValue];
		638	p->hash[hashValue] = p->pos;
		639	offset = (UInt32)(Hc_GetMatchesSpec(lenLimit, curMatch, MF_PARAMS(p),
		640	distances, 2) - (distances));
		641	MOVE_POS_RET
		642	}
		643
		644	static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
		645	{
		646	do
		647	{
		648	SKIP_HEADER(2)
		649	HASH2_CALC;
		650	curMatch = p->hash[hashValue];
		651	p->hash[hashValue] = p->pos;
		652	SKIP_FOOTER
		653	}
		654	while (--num != 0);
		655	}
		656
		657	void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
		658	{
		659	do
		660	{
		661	SKIP_HEADER(3)
		662	HASH_ZIP_CALC;
		663	curMatch = p->hash[hashValue];
		664	p->hash[hashValue] = p->pos;
		665	SKIP_FOOTER
		666	}
		667	while (--num != 0);
		668	}
		669
		670	static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
		671	{
		672	do
		673	{
		674	UInt32 hash2Value;
		675	SKIP_HEADER(3)
		676	HASH3_CALC;
		677	curMatch = p->hash[kFix3HashSize + hashValue];
		678	p->hash[hash2Value] =
		679	p->hash[kFix3HashSize + hashValue] = p->pos;
		680	SKIP_FOOTER
		681	}
		682	while (--num != 0);
		683	}
		684
		685	static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
		686	{
		687	do
		688	{
		689	UInt32 hash2Value, hash3Value;
		690	SKIP_HEADER(4)
		691	HASH4_CALC;
		692	curMatch = p->hash[kFix4HashSize + hashValue];
		693	p->hash[ hash2Value] =
		694	p->hash[kFix3HashSize + hash3Value] = p->pos;
		695	p->hash[kFix4HashSize + hashValue] = p->pos;
		696	SKIP_FOOTER
		697	}
		698	while (--num != 0);
		699	}
		700
		701	static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
		702	{
		703	do
		704	{
		705	UInt32 hash2Value, hash3Value;
		706	SKIP_HEADER(4)
		707	HASH4_CALC;
		708	curMatch = p->hash[kFix4HashSize + hashValue];
		709	p->hash[ hash2Value] =
		710	p->hash[kFix3HashSize + hash3Value] =
		711	p->hash[kFix4HashSize + hashValue] = p->pos;
		712	p->son[p->cyclicBufferPos] = curMatch;
		713	MOVE_POS
		714	}
		715	while (--num != 0);
		716	}
		717
		718	void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
		719	{
		720	do
		721	{
		722	SKIP_HEADER(3)
		723	HASH_ZIP_CALC;
		724	curMatch = p->hash[hashValue];
		725	p->hash[hashValue] = p->pos;
		726	p->son[p->cyclicBufferPos] = curMatch;
		727	MOVE_POS
		728	}
		729	while (--num != 0);
		730	}
		731
		732	void MatchFinder_CreateVTable(CMatchFinder p, IMatchFinder vTable)
		733	{
		734	vTable->Init = (Mf_Init_Func)MatchFinder_Init;
		735	vTable->GetIndexByte = (Mf_GetIndexByte_Func)MatchFinder_GetIndexByte;
		736	vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
		737	vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
		738	if (!p->btMode)
		739	{
		740	vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
		741	vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
		742	}
		743	else if (p->numHashBytes == 2)
		744	{
		745	vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
		746	vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
		747	}
		748	else if (p->numHashBytes == 3)
		749	{
		750	vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
		751	vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
		752	}
		753	else
		754	{
		755	vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
		756	vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
		757	}
		758	}

Subversion Repositories Games.Chess Giants

Games.Chess Giants/engine-texel/gtb/compression/lzma/LzFind.c – Rev 99