forked from blender/blender
Aras Pranckevicius
3f0b9e4a58
Update from version 4.65 (2009) to latest 23.01 (2023). LZMA is only used for pointcache "Heavy" compression option. With updated SDK, testing in a 100k particle system point cache (Windows/Ryzen5950X), average times to read or write a cached frame: - Read a bit faster, 24.3 -> 23.2ms - Write/bake about 2x faster, 237 -> 103ms Pull Request: blender/blender#118433
1718 lines
42 KiB
C
1718 lines
42 KiB
C
/* LzFind.c -- Match finder for LZ algorithms
|
|
2023-03-14 : Igor Pavlov : Public domain */
|
|
|
|
#include "Precomp.h"
|
|
|
|
#include <string.h>
|
|
// #include <stdio.h>
|
|
|
|
#include "CpuArch.h"
|
|
#include "LzFind.h"
|
|
#include "LzHash.h"
|
|
|
|
#define kBlockMoveAlign (1 << 7) // alignment for memmove()
|
|
#define kBlockSizeAlign (1 << 16) // alignment for block allocation
|
|
#define kBlockSizeReserveMin (1 << 24) // it's 1/256 from 4 GB dictinary
|
|
|
|
#define kEmptyHashValue 0
|
|
|
|
#define kMaxValForNormalize ((UInt32)0)
|
|
// #define kMaxValForNormalize ((UInt32)(1 << 20) + 0xfff) // for debug
|
|
|
|
// #define kNormalizeAlign (1 << 7) // alignment for speculated accesses
|
|
|
|
#define GET_AVAIL_BYTES(p) \
|
|
Inline_MatchFinder_GetNumAvailableBytes(p)
|
|
|
|
|
|
// #define kFix5HashSize (kHash2Size + kHash3Size + kHash4Size)
|
|
#define kFix5HashSize kFix4HashSize
|
|
|
|
/*
|
|
HASH2_CALC:
|
|
if (hv) match, then cur[0] and cur[1] also match
|
|
*/
|
|
#define HASH2_CALC hv = GetUi16(cur);
|
|
|
|
// (crc[0 ... 255] & 0xFF) provides one-to-one correspondence to [0 ... 255]
|
|
|
|
/*
|
|
HASH3_CALC:
|
|
if (cur[0]) and (h2) match, then cur[1] also match
|
|
if (cur[0]) and (hv) match, then cur[1] and cur[2] also match
|
|
*/
|
|
#define HASH3_CALC { \
|
|
UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
|
|
h2 = temp & (kHash2Size - 1); \
|
|
hv = (temp ^ ((UInt32)cur[2] << 8)) & p->hashMask; }
|
|
|
|
#define HASH4_CALC { \
|
|
UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
|
|
h2 = temp & (kHash2Size - 1); \
|
|
temp ^= ((UInt32)cur[2] << 8); \
|
|
h3 = temp & (kHash3Size - 1); \
|
|
hv = (temp ^ (p->crc[cur[3]] << kLzHash_CrcShift_1)) & p->hashMask; }
|
|
|
|
#define HASH5_CALC { \
|
|
UInt32 temp = p->crc[cur[0]] ^ cur[1]; \
|
|
h2 = temp & (kHash2Size - 1); \
|
|
temp ^= ((UInt32)cur[2] << 8); \
|
|
h3 = temp & (kHash3Size - 1); \
|
|
temp ^= (p->crc[cur[3]] << kLzHash_CrcShift_1); \
|
|
/* h4 = temp & p->hash4Mask; */ /* (kHash4Size - 1); */ \
|
|
hv = (temp ^ (p->crc[cur[4]] << kLzHash_CrcShift_2)) & p->hashMask; }
|
|
|
|
#define HASH_ZIP_CALC hv = ((cur[2] | ((UInt32)cur[0] << 8)) ^ p->crc[cur[1]]) & 0xFFFF;
|
|
|
|
|
|
static void LzInWindow_Free(CMatchFinder *p, ISzAllocPtr alloc)
|
|
{
|
|
// if (!p->directInput)
|
|
{
|
|
ISzAlloc_Free(alloc, p->bufBase);
|
|
p->bufBase = NULL;
|
|
}
|
|
}
|
|
|
|
|
|
static int LzInWindow_Create2(CMatchFinder *p, UInt32 blockSize, ISzAllocPtr alloc)
|
|
{
|
|
if (blockSize == 0)
|
|
return 0;
|
|
if (!p->bufBase || p->blockSize != blockSize)
|
|
{
|
|
// size_t blockSizeT;
|
|
LzInWindow_Free(p, alloc);
|
|
p->blockSize = blockSize;
|
|
// blockSizeT = blockSize;
|
|
|
|
// printf("\nblockSize = 0x%x\n", blockSize);
|
|
/*
|
|
#if defined _WIN64
|
|
// we can allocate 4GiB, but still use UInt32 for (p->blockSize)
|
|
// we use UInt32 type for (p->blockSize), because
|
|
// we don't want to wrap over 4 GiB,
|
|
// when we use (p->streamPos - p->pos) that is UInt32.
|
|
if (blockSize >= (UInt32)0 - (UInt32)kBlockSizeAlign)
|
|
{
|
|
blockSizeT = ((size_t)1 << 32);
|
|
printf("\nchanged to blockSizeT = 4GiB\n");
|
|
}
|
|
#endif
|
|
*/
|
|
|
|
p->bufBase = (Byte *)ISzAlloc_Alloc(alloc, blockSize);
|
|
// printf("\nbufferBase = %p\n", p->bufBase);
|
|
// return 0; // for debug
|
|
}
|
|
return (p->bufBase != NULL);
|
|
}
|
|
|
|
static const Byte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p) { return p->buffer; }
|
|
|
|
static UInt32 MatchFinder_GetNumAvailableBytes(CMatchFinder *p) { return GET_AVAIL_BYTES(p); }
|
|
|
|
|
|
Z7_NO_INLINE
|
|
static void MatchFinder_ReadBlock(CMatchFinder *p)
|
|
{
|
|
if (p->streamEndWasReached || p->result != SZ_OK)
|
|
return;
|
|
|
|
/* We use (p->streamPos - p->pos) value.
|
|
(p->streamPos < p->pos) is allowed. */
|
|
|
|
if (p->directInput)
|
|
{
|
|
UInt32 curSize = 0xFFFFFFFF - GET_AVAIL_BYTES(p);
|
|
if (curSize > p->directInputRem)
|
|
curSize = (UInt32)p->directInputRem;
|
|
p->streamPos += curSize;
|
|
p->directInputRem -= curSize;
|
|
if (p->directInputRem == 0)
|
|
p->streamEndWasReached = 1;
|
|
return;
|
|
}
|
|
|
|
for (;;)
|
|
{
|
|
const Byte *dest = p->buffer + GET_AVAIL_BYTES(p);
|
|
size_t size = (size_t)(p->bufBase + p->blockSize - dest);
|
|
if (size == 0)
|
|
{
|
|
/* we call ReadBlock() after NeedMove() and MoveBlock().
|
|
NeedMove() and MoveBlock() povide more than (keepSizeAfter)
|
|
to the end of (blockSize).
|
|
So we don't execute this branch in normal code flow.
|
|
We can go here, if we will call ReadBlock() before NeedMove(), MoveBlock().
|
|
*/
|
|
// p->result = SZ_ERROR_FAIL; // we can show error here
|
|
return;
|
|
}
|
|
|
|
// #define kRead 3
|
|
// if (size > kRead) size = kRead; // for debug
|
|
|
|
/*
|
|
// we need cast (Byte *)dest.
|
|
#ifdef __clang__
|
|
#pragma GCC diagnostic ignored "-Wcast-qual"
|
|
#endif
|
|
*/
|
|
p->result = ISeqInStream_Read(p->stream,
|
|
p->bufBase + (dest - p->bufBase), &size);
|
|
if (p->result != SZ_OK)
|
|
return;
|
|
if (size == 0)
|
|
{
|
|
p->streamEndWasReached = 1;
|
|
return;
|
|
}
|
|
p->streamPos += (UInt32)size;
|
|
if (GET_AVAIL_BYTES(p) > p->keepSizeAfter)
|
|
return;
|
|
/* here and in another (p->keepSizeAfter) checks we keep on 1 byte more than was requested by Create() function
|
|
(GET_AVAIL_BYTES(p) >= p->keepSizeAfter) - minimal required size */
|
|
}
|
|
|
|
// on exit: (p->result != SZ_OK || p->streamEndWasReached || GET_AVAIL_BYTES(p) > p->keepSizeAfter)
|
|
}
|
|
|
|
|
|
|
|
Z7_NO_INLINE
|
|
void MatchFinder_MoveBlock(CMatchFinder *p)
|
|
{
|
|
const size_t offset = (size_t)(p->buffer - p->bufBase) - p->keepSizeBefore;
|
|
const size_t keepBefore = (offset & (kBlockMoveAlign - 1)) + p->keepSizeBefore;
|
|
p->buffer = p->bufBase + keepBefore;
|
|
memmove(p->bufBase,
|
|
p->bufBase + (offset & ~((size_t)kBlockMoveAlign - 1)),
|
|
keepBefore + (size_t)GET_AVAIL_BYTES(p));
|
|
}
|
|
|
|
/* We call MoveBlock() before ReadBlock().
|
|
So MoveBlock() can be wasteful operation, if the whole input data
|
|
can fit in current block even without calling MoveBlock().
|
|
in important case where (dataSize <= historySize)
|
|
condition (p->blockSize > dataSize + p->keepSizeAfter) is met
|
|
So there is no MoveBlock() in that case case.
|
|
*/
|
|
|
|
int MatchFinder_NeedMove(CMatchFinder *p)
|
|
{
|
|
if (p->directInput)
|
|
return 0;
|
|
if (p->streamEndWasReached || p->result != SZ_OK)
|
|
return 0;
|
|
return ((size_t)(p->bufBase + p->blockSize - p->buffer) <= p->keepSizeAfter);
|
|
}
|
|
|
|
void MatchFinder_ReadIfRequired(CMatchFinder *p)
|
|
{
|
|
if (p->keepSizeAfter >= GET_AVAIL_BYTES(p))
|
|
MatchFinder_ReadBlock(p);
|
|
}
|
|
|
|
|
|
|
|
static void MatchFinder_SetDefaultSettings(CMatchFinder *p)
|
|
{
|
|
p->cutValue = 32;
|
|
p->btMode = 1;
|
|
p->numHashBytes = 4;
|
|
p->numHashBytes_Min = 2;
|
|
p->numHashOutBits = 0;
|
|
p->bigHash = 0;
|
|
}
|
|
|
|
#define kCrcPoly 0xEDB88320
|
|
|
|
void MatchFinder_Construct(CMatchFinder *p)
|
|
{
|
|
unsigned i;
|
|
p->buffer = NULL;
|
|
p->bufBase = NULL;
|
|
p->directInput = 0;
|
|
p->stream = NULL;
|
|
p->hash = NULL;
|
|
p->expectedDataSize = (UInt64)(Int64)-1;
|
|
MatchFinder_SetDefaultSettings(p);
|
|
|
|
for (i = 0; i < 256; i++)
|
|
{
|
|
UInt32 r = (UInt32)i;
|
|
unsigned j;
|
|
for (j = 0; j < 8; j++)
|
|
r = (r >> 1) ^ (kCrcPoly & ((UInt32)0 - (r & 1)));
|
|
p->crc[i] = r;
|
|
}
|
|
}
|
|
|
|
#undef kCrcPoly
|
|
|
|
static void MatchFinder_FreeThisClassMemory(CMatchFinder *p, ISzAllocPtr alloc)
|
|
{
|
|
ISzAlloc_Free(alloc, p->hash);
|
|
p->hash = NULL;
|
|
}
|
|
|
|
void MatchFinder_Free(CMatchFinder *p, ISzAllocPtr alloc)
|
|
{
|
|
MatchFinder_FreeThisClassMemory(p, alloc);
|
|
LzInWindow_Free(p, alloc);
|
|
}
|
|
|
|
static CLzRef* AllocRefs(size_t num, ISzAllocPtr alloc)
|
|
{
|
|
const size_t sizeInBytes = (size_t)num * sizeof(CLzRef);
|
|
if (sizeInBytes / sizeof(CLzRef) != num)
|
|
return NULL;
|
|
return (CLzRef *)ISzAlloc_Alloc(alloc, sizeInBytes);
|
|
}
|
|
|
|
#if (kBlockSizeReserveMin < kBlockSizeAlign * 2)
|
|
#error Stop_Compiling_Bad_Reserve
|
|
#endif
|
|
|
|
|
|
|
|
static UInt32 GetBlockSize(CMatchFinder *p, UInt32 historySize)
|
|
{
|
|
UInt32 blockSize = (p->keepSizeBefore + p->keepSizeAfter);
|
|
/*
|
|
if (historySize > kMaxHistorySize)
|
|
return 0;
|
|
*/
|
|
// printf("\nhistorySize == 0x%x\n", historySize);
|
|
|
|
if (p->keepSizeBefore < historySize || blockSize < p->keepSizeBefore) // if 32-bit overflow
|
|
return 0;
|
|
|
|
{
|
|
const UInt32 kBlockSizeMax = (UInt32)0 - (UInt32)kBlockSizeAlign;
|
|
const UInt32 rem = kBlockSizeMax - blockSize;
|
|
const UInt32 reserve = (blockSize >> (blockSize < ((UInt32)1 << 30) ? 1 : 2))
|
|
+ (1 << 12) + kBlockMoveAlign + kBlockSizeAlign; // do not overflow 32-bit here
|
|
if (blockSize >= kBlockSizeMax
|
|
|| rem < kBlockSizeReserveMin) // we reject settings that will be slow
|
|
return 0;
|
|
if (reserve >= rem)
|
|
blockSize = kBlockSizeMax;
|
|
else
|
|
{
|
|
blockSize += reserve;
|
|
blockSize &= ~(UInt32)(kBlockSizeAlign - 1);
|
|
}
|
|
}
|
|
// printf("\n LzFind_blockSize = %x\n", blockSize);
|
|
// printf("\n LzFind_blockSize = %d\n", blockSize >> 20);
|
|
return blockSize;
|
|
}
|
|
|
|
|
|
// input is historySize
|
|
static UInt32 MatchFinder_GetHashMask2(CMatchFinder *p, UInt32 hs)
|
|
{
|
|
if (p->numHashBytes == 2)
|
|
return (1 << 16) - 1;
|
|
if (hs != 0)
|
|
hs--;
|
|
hs |= (hs >> 1);
|
|
hs |= (hs >> 2);
|
|
hs |= (hs >> 4);
|
|
hs |= (hs >> 8);
|
|
// we propagated 16 bits in (hs). Low 16 bits must be set later
|
|
if (hs >= (1 << 24))
|
|
{
|
|
if (p->numHashBytes == 3)
|
|
hs = (1 << 24) - 1;
|
|
/* if (bigHash) mode, GetHeads4b() in LzFindMt.c needs (hs >= ((1 << 24) - 1))) */
|
|
}
|
|
// (hash_size >= (1 << 16)) : Required for (numHashBytes > 2)
|
|
hs |= (1 << 16) - 1; /* don't change it! */
|
|
// bt5: we adjust the size with recommended minimum size
|
|
if (p->numHashBytes >= 5)
|
|
hs |= (256 << kLzHash_CrcShift_2) - 1;
|
|
return hs;
|
|
}
|
|
|
|
// input is historySize
|
|
static UInt32 MatchFinder_GetHashMask(CMatchFinder *p, UInt32 hs)
|
|
{
|
|
if (p->numHashBytes == 2)
|
|
return (1 << 16) - 1;
|
|
if (hs != 0)
|
|
hs--;
|
|
hs |= (hs >> 1);
|
|
hs |= (hs >> 2);
|
|
hs |= (hs >> 4);
|
|
hs |= (hs >> 8);
|
|
// we propagated 16 bits in (hs). Low 16 bits must be set later
|
|
hs >>= 1;
|
|
if (hs >= (1 << 24))
|
|
{
|
|
if (p->numHashBytes == 3)
|
|
hs = (1 << 24) - 1;
|
|
else
|
|
hs >>= 1;
|
|
/* if (bigHash) mode, GetHeads4b() in LzFindMt.c needs (hs >= ((1 << 24) - 1))) */
|
|
}
|
|
// (hash_size >= (1 << 16)) : Required for (numHashBytes > 2)
|
|
hs |= (1 << 16) - 1; /* don't change it! */
|
|
// bt5: we adjust the size with recommended minimum size
|
|
if (p->numHashBytes >= 5)
|
|
hs |= (256 << kLzHash_CrcShift_2) - 1;
|
|
return hs;
|
|
}
|
|
|
|
|
|
int MatchFinder_Create(CMatchFinder *p, UInt32 historySize,
|
|
UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter,
|
|
ISzAllocPtr alloc)
|
|
{
|
|
/* we need one additional byte in (p->keepSizeBefore),
|
|
since we use MoveBlock() after (p->pos++) and before dictionary using */
|
|
// keepAddBufferBefore = (UInt32)0xFFFFFFFF - (1 << 22); // for debug
|
|
p->keepSizeBefore = historySize + keepAddBufferBefore + 1;
|
|
|
|
keepAddBufferAfter += matchMaxLen;
|
|
/* we need (p->keepSizeAfter >= p->numHashBytes) */
|
|
if (keepAddBufferAfter < p->numHashBytes)
|
|
keepAddBufferAfter = p->numHashBytes;
|
|
// keepAddBufferAfter -= 2; // for debug
|
|
p->keepSizeAfter = keepAddBufferAfter;
|
|
|
|
if (p->directInput)
|
|
p->blockSize = 0;
|
|
if (p->directInput || LzInWindow_Create2(p, GetBlockSize(p, historySize), alloc))
|
|
{
|
|
size_t hashSizeSum;
|
|
{
|
|
UInt32 hs;
|
|
UInt32 hsCur;
|
|
|
|
if (p->numHashOutBits != 0)
|
|
{
|
|
unsigned numBits = p->numHashOutBits;
|
|
const unsigned nbMax =
|
|
(p->numHashBytes == 2 ? 16 :
|
|
(p->numHashBytes == 3 ? 24 : 32));
|
|
if (numBits > nbMax)
|
|
numBits = nbMax;
|
|
if (numBits >= 32)
|
|
hs = (UInt32)0 - 1;
|
|
else
|
|
hs = ((UInt32)1 << numBits) - 1;
|
|
// (hash_size >= (1 << 16)) : Required for (numHashBytes > 2)
|
|
hs |= (1 << 16) - 1; /* don't change it! */
|
|
if (p->numHashBytes >= 5)
|
|
hs |= (256 << kLzHash_CrcShift_2) - 1;
|
|
{
|
|
const UInt32 hs2 = MatchFinder_GetHashMask2(p, historySize);
|
|
if (hs > hs2)
|
|
hs = hs2;
|
|
}
|
|
hsCur = hs;
|
|
if (p->expectedDataSize < historySize)
|
|
{
|
|
const UInt32 hs2 = MatchFinder_GetHashMask2(p, (UInt32)p->expectedDataSize);
|
|
if (hsCur > hs2)
|
|
hsCur = hs2;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
hs = MatchFinder_GetHashMask(p, historySize);
|
|
hsCur = hs;
|
|
if (p->expectedDataSize < historySize)
|
|
{
|
|
hsCur = MatchFinder_GetHashMask(p, (UInt32)p->expectedDataSize);
|
|
if (hsCur > hs) // is it possible?
|
|
hsCur = hs;
|
|
}
|
|
}
|
|
|
|
p->hashMask = hsCur;
|
|
|
|
hashSizeSum = hs;
|
|
hashSizeSum++;
|
|
if (hashSizeSum < hs)
|
|
return 0;
|
|
{
|
|
UInt32 fixedHashSize = 0;
|
|
if (p->numHashBytes > 2 && p->numHashBytes_Min <= 2) fixedHashSize += kHash2Size;
|
|
if (p->numHashBytes > 3 && p->numHashBytes_Min <= 3) fixedHashSize += kHash3Size;
|
|
// if (p->numHashBytes > 4) p->fixedHashSize += hs4; // kHash4Size;
|
|
hashSizeSum += fixedHashSize;
|
|
p->fixedHashSize = fixedHashSize;
|
|
}
|
|
}
|
|
|
|
p->matchMaxLen = matchMaxLen;
|
|
|
|
{
|
|
size_t newSize;
|
|
size_t numSons;
|
|
const UInt32 newCyclicBufferSize = historySize + 1; // do not change it
|
|
p->historySize = historySize;
|
|
p->cyclicBufferSize = newCyclicBufferSize; // it must be = (historySize + 1)
|
|
|
|
numSons = newCyclicBufferSize;
|
|
if (p->btMode)
|
|
numSons <<= 1;
|
|
newSize = hashSizeSum + numSons;
|
|
|
|
if (numSons < newCyclicBufferSize || newSize < numSons)
|
|
return 0;
|
|
|
|
// aligned size is not required here, but it can be better for some loops
|
|
#define NUM_REFS_ALIGN_MASK 0xF
|
|
newSize = (newSize + NUM_REFS_ALIGN_MASK) & ~(size_t)NUM_REFS_ALIGN_MASK;
|
|
|
|
// 22.02: we don't reallocate buffer, if old size is enough
|
|
if (p->hash && p->numRefs >= newSize)
|
|
return 1;
|
|
|
|
MatchFinder_FreeThisClassMemory(p, alloc);
|
|
p->numRefs = newSize;
|
|
p->hash = AllocRefs(newSize, alloc);
|
|
|
|
if (p->hash)
|
|
{
|
|
p->son = p->hash + hashSizeSum;
|
|
return 1;
|
|
}
|
|
}
|
|
}
|
|
|
|
MatchFinder_Free(p, alloc);
|
|
return 0;
|
|
}
|
|
|
|
|
|
static void MatchFinder_SetLimits(CMatchFinder *p)
|
|
{
|
|
UInt32 k;
|
|
UInt32 n = kMaxValForNormalize - p->pos;
|
|
if (n == 0)
|
|
n = (UInt32)(Int32)-1; // we allow (pos == 0) at start even with (kMaxValForNormalize == 0)
|
|
|
|
k = p->cyclicBufferSize - p->cyclicBufferPos;
|
|
if (k < n)
|
|
n = k;
|
|
|
|
k = GET_AVAIL_BYTES(p);
|
|
{
|
|
const UInt32 ksa = p->keepSizeAfter;
|
|
UInt32 mm = p->matchMaxLen;
|
|
if (k > ksa)
|
|
k -= ksa; // we must limit exactly to keepSizeAfter for ReadBlock
|
|
else if (k >= mm)
|
|
{
|
|
// the limitation for (p->lenLimit) update
|
|
k -= mm; // optimization : to reduce the number of checks
|
|
k++;
|
|
// k = 1; // non-optimized version : for debug
|
|
}
|
|
else
|
|
{
|
|
mm = k;
|
|
if (k != 0)
|
|
k = 1;
|
|
}
|
|
p->lenLimit = mm;
|
|
}
|
|
if (k < n)
|
|
n = k;
|
|
|
|
p->posLimit = p->pos + n;
|
|
}
|
|
|
|
|
|
void MatchFinder_Init_LowHash(CMatchFinder *p)
|
|
{
|
|
size_t i;
|
|
CLzRef *items = p->hash;
|
|
const size_t numItems = p->fixedHashSize;
|
|
for (i = 0; i < numItems; i++)
|
|
items[i] = kEmptyHashValue;
|
|
}
|
|
|
|
|
|
void MatchFinder_Init_HighHash(CMatchFinder *p)
|
|
{
|
|
size_t i;
|
|
CLzRef *items = p->hash + p->fixedHashSize;
|
|
const size_t numItems = (size_t)p->hashMask + 1;
|
|
for (i = 0; i < numItems; i++)
|
|
items[i] = kEmptyHashValue;
|
|
}
|
|
|
|
|
|
void MatchFinder_Init_4(CMatchFinder *p)
|
|
{
|
|
if (!p->directInput)
|
|
p->buffer = p->bufBase;
|
|
{
|
|
/* kEmptyHashValue = 0 (Zero) is used in hash tables as NO-VALUE marker.
|
|
the code in CMatchFinderMt expects (pos = 1) */
|
|
p->pos =
|
|
p->streamPos =
|
|
1; // it's smallest optimal value. do not change it
|
|
// 0; // for debug
|
|
}
|
|
p->result = SZ_OK;
|
|
p->streamEndWasReached = 0;
|
|
}
|
|
|
|
|
|
// (CYC_TO_POS_OFFSET == 0) is expected by some optimized code
|
|
#define CYC_TO_POS_OFFSET 0
|
|
// #define CYC_TO_POS_OFFSET 1 // for debug
|
|
|
|
void MatchFinder_Init(CMatchFinder *p)
|
|
{
|
|
MatchFinder_Init_HighHash(p);
|
|
MatchFinder_Init_LowHash(p);
|
|
MatchFinder_Init_4(p);
|
|
// if (readData)
|
|
MatchFinder_ReadBlock(p);
|
|
|
|
/* if we init (cyclicBufferPos = pos), then we can use one variable
|
|
instead of both (cyclicBufferPos) and (pos) : only before (cyclicBufferPos) wrapping */
|
|
p->cyclicBufferPos = (p->pos - CYC_TO_POS_OFFSET); // init with relation to (pos)
|
|
// p->cyclicBufferPos = 0; // smallest value
|
|
// p->son[0] = p->son[1] = 0; // unused: we can init skipped record for speculated accesses.
|
|
MatchFinder_SetLimits(p);
|
|
}
|
|
|
|
|
|
|
|
#ifdef MY_CPU_X86_OR_AMD64
|
|
#if defined(__clang__) && (__clang_major__ >= 4) \
|
|
|| defined(Z7_GCC_VERSION) && (Z7_GCC_VERSION >= 40701)
|
|
// || defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 1900)
|
|
|
|
#define USE_LZFIND_SATUR_SUB_128
|
|
#define USE_LZFIND_SATUR_SUB_256
|
|
#define LZFIND_ATTRIB_SSE41 __attribute__((__target__("sse4.1")))
|
|
#define LZFIND_ATTRIB_AVX2 __attribute__((__target__("avx2")))
|
|
#elif defined(_MSC_VER)
|
|
#if (_MSC_VER >= 1600)
|
|
#define USE_LZFIND_SATUR_SUB_128
|
|
#endif
|
|
#if (_MSC_VER >= 1900)
|
|
#define USE_LZFIND_SATUR_SUB_256
|
|
#endif
|
|
#endif
|
|
|
|
// #elif defined(MY_CPU_ARM_OR_ARM64)
|
|
#elif defined(MY_CPU_ARM64)
|
|
|
|
#if defined(__clang__) && (__clang_major__ >= 8) \
|
|
|| defined(__GNUC__) && (__GNUC__ >= 8)
|
|
#define USE_LZFIND_SATUR_SUB_128
|
|
#ifdef MY_CPU_ARM64
|
|
// #define LZFIND_ATTRIB_SSE41 __attribute__((__target__("")))
|
|
#else
|
|
// #define LZFIND_ATTRIB_SSE41 __attribute__((__target__("fpu=crypto-neon-fp-armv8")))
|
|
#endif
|
|
|
|
#elif defined(_MSC_VER)
|
|
#if (_MSC_VER >= 1910)
|
|
#define USE_LZFIND_SATUR_SUB_128
|
|
#endif
|
|
#endif
|
|
|
|
#if defined(_MSC_VER) && defined(MY_CPU_ARM64)
|
|
#include <arm64_neon.h>
|
|
#else
|
|
#include <arm_neon.h>
|
|
#endif
|
|
|
|
#endif
|
|
|
|
|
|
#ifdef USE_LZFIND_SATUR_SUB_128
|
|
|
|
// #define Z7_SHOW_HW_STATUS
|
|
|
|
#ifdef Z7_SHOW_HW_STATUS
|
|
#include <stdio.h>
|
|
#define PRF(x) x
|
|
PRF(;)
|
|
#else
|
|
#define PRF(x)
|
|
#endif
|
|
|
|
|
|
#ifdef MY_CPU_ARM_OR_ARM64
|
|
|
|
#ifdef MY_CPU_ARM64
|
|
// #define FORCE_LZFIND_SATUR_SUB_128
|
|
#endif
|
|
typedef uint32x4_t LzFind_v128;
|
|
#define SASUB_128_V(v, s) \
|
|
vsubq_u32(vmaxq_u32(v, s), s)
|
|
|
|
#else // MY_CPU_ARM_OR_ARM64
|
|
|
|
#include <smmintrin.h> // sse4.1
|
|
|
|
typedef __m128i LzFind_v128;
|
|
// SSE 4.1
|
|
#define SASUB_128_V(v, s) \
|
|
_mm_sub_epi32(_mm_max_epu32(v, s), s)
|
|
|
|
#endif // MY_CPU_ARM_OR_ARM64
|
|
|
|
|
|
#define SASUB_128(i) \
|
|
*( LzFind_v128 *)( void *)(items + (i) * 4) = SASUB_128_V( \
|
|
*(const LzFind_v128 *)(const void *)(items + (i) * 4), sub2);
|
|
|
|
|
|
Z7_NO_INLINE
|
|
static
|
|
#ifdef LZFIND_ATTRIB_SSE41
|
|
LZFIND_ATTRIB_SSE41
|
|
#endif
|
|
void
|
|
Z7_FASTCALL
|
|
LzFind_SaturSub_128(UInt32 subValue, CLzRef *items, const CLzRef *lim)
|
|
{
|
|
const LzFind_v128 sub2 =
|
|
#ifdef MY_CPU_ARM_OR_ARM64
|
|
vdupq_n_u32(subValue);
|
|
#else
|
|
_mm_set_epi32((Int32)subValue, (Int32)subValue, (Int32)subValue, (Int32)subValue);
|
|
#endif
|
|
Z7_PRAGMA_OPT_DISABLE_LOOP_UNROLL_VECTORIZE
|
|
do
|
|
{
|
|
SASUB_128(0) SASUB_128(1) items += 2 * 4;
|
|
SASUB_128(0) SASUB_128(1) items += 2 * 4;
|
|
}
|
|
while (items != lim);
|
|
}
|
|
|
|
|
|
|
|
#ifdef USE_LZFIND_SATUR_SUB_256
|
|
|
|
#include <immintrin.h> // avx
|
|
/*
|
|
clang :immintrin.h uses
|
|
#if !(defined(_MSC_VER) || defined(__SCE__)) || __has_feature(modules) || \
|
|
defined(__AVX2__)
|
|
#include <avx2intrin.h>
|
|
#endif
|
|
so we need <avxintrin.h> for clang-cl */
|
|
|
|
#if defined(__clang__)
|
|
#include <avxintrin.h>
|
|
#include <avx2intrin.h>
|
|
#endif
|
|
|
|
// AVX2:
|
|
#define SASUB_256(i) \
|
|
*( __m256i *)( void *)(items + (i) * 8) = \
|
|
_mm256_sub_epi32(_mm256_max_epu32( \
|
|
*(const __m256i *)(const void *)(items + (i) * 8), sub2), sub2);
|
|
|
|
Z7_NO_INLINE
|
|
static
|
|
#ifdef LZFIND_ATTRIB_AVX2
|
|
LZFIND_ATTRIB_AVX2
|
|
#endif
|
|
void
|
|
Z7_FASTCALL
|
|
LzFind_SaturSub_256(UInt32 subValue, CLzRef *items, const CLzRef *lim)
|
|
{
|
|
const __m256i sub2 = _mm256_set_epi32(
|
|
(Int32)subValue, (Int32)subValue, (Int32)subValue, (Int32)subValue,
|
|
(Int32)subValue, (Int32)subValue, (Int32)subValue, (Int32)subValue);
|
|
Z7_PRAGMA_OPT_DISABLE_LOOP_UNROLL_VECTORIZE
|
|
do
|
|
{
|
|
SASUB_256(0) SASUB_256(1) items += 2 * 8;
|
|
SASUB_256(0) SASUB_256(1) items += 2 * 8;
|
|
}
|
|
while (items != lim);
|
|
}
|
|
#endif // USE_LZFIND_SATUR_SUB_256
|
|
|
|
#ifndef FORCE_LZFIND_SATUR_SUB_128
|
|
typedef void (Z7_FASTCALL *LZFIND_SATUR_SUB_CODE_FUNC)(
|
|
UInt32 subValue, CLzRef *items, const CLzRef *lim);
|
|
static LZFIND_SATUR_SUB_CODE_FUNC g_LzFind_SaturSub;
|
|
#endif // FORCE_LZFIND_SATUR_SUB_128
|
|
|
|
#endif // USE_LZFIND_SATUR_SUB_128
|
|
|
|
|
|
// kEmptyHashValue must be zero
|
|
// #define SASUB_32(i) { UInt32 v = items[i]; UInt32 m = v - subValue; if (v < subValue) m = kEmptyHashValue; items[i] = m; }
|
|
#define SASUB_32(i) { UInt32 v = items[i]; if (v < subValue) v = subValue; items[i] = v - subValue; }
|
|
|
|
#ifdef FORCE_LZFIND_SATUR_SUB_128
|
|
|
|
#define DEFAULT_SaturSub LzFind_SaturSub_128
|
|
|
|
#else
|
|
|
|
#define DEFAULT_SaturSub LzFind_SaturSub_32
|
|
|
|
Z7_NO_INLINE
|
|
static
|
|
void
|
|
Z7_FASTCALL
|
|
LzFind_SaturSub_32(UInt32 subValue, CLzRef *items, const CLzRef *lim)
|
|
{
|
|
Z7_PRAGMA_OPT_DISABLE_LOOP_UNROLL_VECTORIZE
|
|
do
|
|
{
|
|
SASUB_32(0) SASUB_32(1) items += 2;
|
|
SASUB_32(0) SASUB_32(1) items += 2;
|
|
SASUB_32(0) SASUB_32(1) items += 2;
|
|
SASUB_32(0) SASUB_32(1) items += 2;
|
|
}
|
|
while (items != lim);
|
|
}
|
|
|
|
#endif
|
|
|
|
|
|
Z7_NO_INLINE
|
|
void MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, size_t numItems)
|
|
{
|
|
#define LZFIND_NORM_ALIGN_BLOCK_SIZE (1 << 7)
|
|
Z7_PRAGMA_OPT_DISABLE_LOOP_UNROLL_VECTORIZE
|
|
for (; numItems != 0 && ((unsigned)(ptrdiff_t)items & (LZFIND_NORM_ALIGN_BLOCK_SIZE - 1)) != 0; numItems--)
|
|
{
|
|
SASUB_32(0)
|
|
items++;
|
|
}
|
|
{
|
|
const size_t k_Align_Mask = (LZFIND_NORM_ALIGN_BLOCK_SIZE / 4 - 1);
|
|
CLzRef *lim = items + (numItems & ~(size_t)k_Align_Mask);
|
|
numItems &= k_Align_Mask;
|
|
if (items != lim)
|
|
{
|
|
#if defined(USE_LZFIND_SATUR_SUB_128) && !defined(FORCE_LZFIND_SATUR_SUB_128)
|
|
if (g_LzFind_SaturSub)
|
|
g_LzFind_SaturSub(subValue, items, lim);
|
|
else
|
|
#endif
|
|
DEFAULT_SaturSub(subValue, items, lim);
|
|
}
|
|
items = lim;
|
|
}
|
|
Z7_PRAGMA_OPT_DISABLE_LOOP_UNROLL_VECTORIZE
|
|
for (; numItems != 0; numItems--)
|
|
{
|
|
SASUB_32(0)
|
|
items++;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
// call MatchFinder_CheckLimits() only after (p->pos++) update
|
|
|
|
Z7_NO_INLINE
|
|
static void MatchFinder_CheckLimits(CMatchFinder *p)
|
|
{
|
|
if (// !p->streamEndWasReached && p->result == SZ_OK &&
|
|
p->keepSizeAfter == GET_AVAIL_BYTES(p))
|
|
{
|
|
// we try to read only in exact state (p->keepSizeAfter == GET_AVAIL_BYTES(p))
|
|
if (MatchFinder_NeedMove(p))
|
|
MatchFinder_MoveBlock(p);
|
|
MatchFinder_ReadBlock(p);
|
|
}
|
|
|
|
if (p->pos == kMaxValForNormalize)
|
|
if (GET_AVAIL_BYTES(p) >= p->numHashBytes) // optional optimization for last bytes of data.
|
|
/*
|
|
if we disable normalization for last bytes of data, and
|
|
if (data_size == 4 GiB), we don't call wastfull normalization,
|
|
but (pos) will be wrapped over Zero (0) in that case.
|
|
And we cannot resume later to normal operation
|
|
*/
|
|
{
|
|
// MatchFinder_Normalize(p);
|
|
/* after normalization we need (p->pos >= p->historySize + 1); */
|
|
/* we can reduce subValue to aligned value, if want to keep alignment
|
|
of (p->pos) and (p->buffer) for speculated accesses. */
|
|
const UInt32 subValue = (p->pos - p->historySize - 1) /* & ~(UInt32)(kNormalizeAlign - 1) */;
|
|
// const UInt32 subValue = (1 << 15); // for debug
|
|
// printf("\nMatchFinder_Normalize() subValue == 0x%x\n", subValue);
|
|
MatchFinder_REDUCE_OFFSETS(p, subValue)
|
|
MatchFinder_Normalize3(subValue, p->hash, (size_t)p->hashMask + 1 + p->fixedHashSize);
|
|
{
|
|
size_t numSonRefs = p->cyclicBufferSize;
|
|
if (p->btMode)
|
|
numSonRefs <<= 1;
|
|
MatchFinder_Normalize3(subValue, p->son, numSonRefs);
|
|
}
|
|
}
|
|
|
|
if (p->cyclicBufferPos == p->cyclicBufferSize)
|
|
p->cyclicBufferPos = 0;
|
|
|
|
MatchFinder_SetLimits(p);
|
|
}
|
|
|
|
|
|
/*
|
|
(lenLimit > maxLen)
|
|
*/
|
|
Z7_FORCE_INLINE
|
|
static UInt32 * Hc_GetMatchesSpec(size_t lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
|
|
size_t _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
|
|
UInt32 *d, unsigned maxLen)
|
|
{
|
|
/*
|
|
son[_cyclicBufferPos] = curMatch;
|
|
for (;;)
|
|
{
|
|
UInt32 delta = pos - curMatch;
|
|
if (cutValue-- == 0 || delta >= _cyclicBufferSize)
|
|
return d;
|
|
{
|
|
const Byte *pb = cur - delta;
|
|
curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
|
|
if (pb[maxLen] == cur[maxLen] && *pb == *cur)
|
|
{
|
|
UInt32 len = 0;
|
|
while (++len != lenLimit)
|
|
if (pb[len] != cur[len])
|
|
break;
|
|
if (maxLen < len)
|
|
{
|
|
maxLen = len;
|
|
*d++ = len;
|
|
*d++ = delta - 1;
|
|
if (len == lenLimit)
|
|
return d;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
*/
|
|
|
|
const Byte *lim = cur + lenLimit;
|
|
son[_cyclicBufferPos] = curMatch;
|
|
|
|
do
|
|
{
|
|
UInt32 delta;
|
|
|
|
if (curMatch == 0)
|
|
break;
|
|
// if (curMatch2 >= curMatch) return NULL;
|
|
delta = pos - curMatch;
|
|
if (delta >= _cyclicBufferSize)
|
|
break;
|
|
{
|
|
ptrdiff_t diff;
|
|
curMatch = son[_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)];
|
|
diff = (ptrdiff_t)0 - (ptrdiff_t)delta;
|
|
if (cur[maxLen] == cur[(ptrdiff_t)maxLen + diff])
|
|
{
|
|
const Byte *c = cur;
|
|
while (*c == c[diff])
|
|
{
|
|
if (++c == lim)
|
|
{
|
|
d[0] = (UInt32)(lim - cur);
|
|
d[1] = delta - 1;
|
|
return d + 2;
|
|
}
|
|
}
|
|
{
|
|
const unsigned len = (unsigned)(c - cur);
|
|
if (maxLen < len)
|
|
{
|
|
maxLen = len;
|
|
d[0] = (UInt32)len;
|
|
d[1] = delta - 1;
|
|
d += 2;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
while (--cutValue);
|
|
|
|
return d;
|
|
}
|
|
|
|
|
|
Z7_FORCE_INLINE
|
|
UInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
|
|
size_t _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue,
|
|
UInt32 *d, UInt32 maxLen)
|
|
{
|
|
CLzRef *ptr0 = son + ((size_t)_cyclicBufferPos << 1) + 1;
|
|
CLzRef *ptr1 = son + ((size_t)_cyclicBufferPos << 1);
|
|
unsigned len0 = 0, len1 = 0;
|
|
|
|
UInt32 cmCheck;
|
|
|
|
// if (curMatch >= pos) { *ptr0 = *ptr1 = kEmptyHashValue; return NULL; }
|
|
|
|
cmCheck = (UInt32)(pos - _cyclicBufferSize);
|
|
if ((UInt32)pos <= _cyclicBufferSize)
|
|
cmCheck = 0;
|
|
|
|
if (cmCheck < curMatch)
|
|
do
|
|
{
|
|
const UInt32 delta = pos - curMatch;
|
|
{
|
|
CLzRef *pair = son + ((size_t)(_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
|
|
const Byte *pb = cur - delta;
|
|
unsigned len = (len0 < len1 ? len0 : len1);
|
|
const UInt32 pair0 = pair[0];
|
|
if (pb[len] == cur[len])
|
|
{
|
|
if (++len != lenLimit && pb[len] == cur[len])
|
|
while (++len != lenLimit)
|
|
if (pb[len] != cur[len])
|
|
break;
|
|
if (maxLen < len)
|
|
{
|
|
maxLen = (UInt32)len;
|
|
*d++ = (UInt32)len;
|
|
*d++ = delta - 1;
|
|
if (len == lenLimit)
|
|
{
|
|
*ptr1 = pair0;
|
|
*ptr0 = pair[1];
|
|
return d;
|
|
}
|
|
}
|
|
}
|
|
if (pb[len] < cur[len])
|
|
{
|
|
*ptr1 = curMatch;
|
|
// const UInt32 curMatch2 = pair[1];
|
|
// if (curMatch2 >= curMatch) { *ptr0 = *ptr1 = kEmptyHashValue; return NULL; }
|
|
// curMatch = curMatch2;
|
|
curMatch = pair[1];
|
|
ptr1 = pair + 1;
|
|
len1 = len;
|
|
}
|
|
else
|
|
{
|
|
*ptr0 = curMatch;
|
|
curMatch = pair[0];
|
|
ptr0 = pair;
|
|
len0 = len;
|
|
}
|
|
}
|
|
}
|
|
while(--cutValue && cmCheck < curMatch);
|
|
|
|
*ptr0 = *ptr1 = kEmptyHashValue;
|
|
return d;
|
|
}
|
|
|
|
|
|
static void SkipMatchesSpec(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *cur, CLzRef *son,
|
|
size_t _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 cutValue)
|
|
{
|
|
CLzRef *ptr0 = son + ((size_t)_cyclicBufferPos << 1) + 1;
|
|
CLzRef *ptr1 = son + ((size_t)_cyclicBufferPos << 1);
|
|
unsigned len0 = 0, len1 = 0;
|
|
|
|
UInt32 cmCheck;
|
|
|
|
cmCheck = (UInt32)(pos - _cyclicBufferSize);
|
|
if ((UInt32)pos <= _cyclicBufferSize)
|
|
cmCheck = 0;
|
|
|
|
if (// curMatch >= pos || // failure
|
|
cmCheck < curMatch)
|
|
do
|
|
{
|
|
const UInt32 delta = pos - curMatch;
|
|
{
|
|
CLzRef *pair = son + ((size_t)(_cyclicBufferPos - delta + ((delta > _cyclicBufferPos) ? _cyclicBufferSize : 0)) << 1);
|
|
const Byte *pb = cur - delta;
|
|
unsigned len = (len0 < len1 ? len0 : len1);
|
|
if (pb[len] == cur[len])
|
|
{
|
|
while (++len != lenLimit)
|
|
if (pb[len] != cur[len])
|
|
break;
|
|
{
|
|
if (len == lenLimit)
|
|
{
|
|
*ptr1 = pair[0];
|
|
*ptr0 = pair[1];
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
if (pb[len] < cur[len])
|
|
{
|
|
*ptr1 = curMatch;
|
|
curMatch = pair[1];
|
|
ptr1 = pair + 1;
|
|
len1 = len;
|
|
}
|
|
else
|
|
{
|
|
*ptr0 = curMatch;
|
|
curMatch = pair[0];
|
|
ptr0 = pair;
|
|
len0 = len;
|
|
}
|
|
}
|
|
}
|
|
while(--cutValue && cmCheck < curMatch);
|
|
|
|
*ptr0 = *ptr1 = kEmptyHashValue;
|
|
return;
|
|
}
|
|
|
|
|
|
#define MOVE_POS \
|
|
++p->cyclicBufferPos; \
|
|
p->buffer++; \
|
|
{ const UInt32 pos1 = p->pos + 1; p->pos = pos1; if (pos1 == p->posLimit) MatchFinder_CheckLimits(p); }
|
|
|
|
#define MOVE_POS_RET MOVE_POS return distances;
|
|
|
|
Z7_NO_INLINE
|
|
static void MatchFinder_MovePos(CMatchFinder *p)
|
|
{
|
|
/* we go here at the end of stream data, when (avail < num_hash_bytes)
|
|
We don't update sons[cyclicBufferPos << btMode].
|
|
So (sons) record will contain junk. And we cannot resume match searching
|
|
to normal operation, even if we will provide more input data in buffer.
|
|
p->sons[p->cyclicBufferPos << p->btMode] = 0; // kEmptyHashValue
|
|
if (p->btMode)
|
|
p->sons[(p->cyclicBufferPos << p->btMode) + 1] = 0; // kEmptyHashValue
|
|
*/
|
|
MOVE_POS
|
|
}
|
|
|
|
#define GET_MATCHES_HEADER2(minLen, ret_op) \
|
|
unsigned lenLimit; UInt32 hv; const Byte *cur; UInt32 curMatch; \
|
|
lenLimit = (unsigned)p->lenLimit; { if (lenLimit < minLen) { MatchFinder_MovePos(p); ret_op; }} \
|
|
cur = p->buffer;
|
|
|
|
#define GET_MATCHES_HEADER(minLen) GET_MATCHES_HEADER2(minLen, return distances)
|
|
#define SKIP_HEADER(minLen) do { GET_MATCHES_HEADER2(minLen, continue)
|
|
|
|
#define MF_PARAMS(p) lenLimit, curMatch, p->pos, p->buffer, p->son, p->cyclicBufferPos, p->cyclicBufferSize, p->cutValue
|
|
|
|
#define SKIP_FOOTER SkipMatchesSpec(MF_PARAMS(p)); MOVE_POS } while (--num);
|
|
|
|
#define GET_MATCHES_FOOTER_BASE(_maxLen_, func) \
|
|
distances = func(MF_PARAMS(p), \
|
|
distances, (UInt32)_maxLen_); MOVE_POS_RET
|
|
|
|
#define GET_MATCHES_FOOTER_BT(_maxLen_) \
|
|
GET_MATCHES_FOOTER_BASE(_maxLen_, GetMatchesSpec1)
|
|
|
|
#define GET_MATCHES_FOOTER_HC(_maxLen_) \
|
|
GET_MATCHES_FOOTER_BASE(_maxLen_, Hc_GetMatchesSpec)
|
|
|
|
|
|
|
|
#define UPDATE_maxLen { \
|
|
const ptrdiff_t diff = (ptrdiff_t)0 - (ptrdiff_t)d2; \
|
|
const Byte *c = cur + maxLen; \
|
|
const Byte *lim = cur + lenLimit; \
|
|
for (; c != lim; c++) if (*(c + diff) != *c) break; \
|
|
maxLen = (unsigned)(c - cur); }
|
|
|
|
static UInt32* Bt2_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
|
|
{
|
|
GET_MATCHES_HEADER(2)
|
|
HASH2_CALC
|
|
curMatch = p->hash[hv];
|
|
p->hash[hv] = p->pos;
|
|
GET_MATCHES_FOOTER_BT(1)
|
|
}
|
|
|
|
UInt32* Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
|
|
{
|
|
GET_MATCHES_HEADER(3)
|
|
HASH_ZIP_CALC
|
|
curMatch = p->hash[hv];
|
|
p->hash[hv] = p->pos;
|
|
GET_MATCHES_FOOTER_BT(2)
|
|
}
|
|
|
|
|
|
#define SET_mmm \
|
|
mmm = p->cyclicBufferSize; \
|
|
if (pos < mmm) \
|
|
mmm = pos;
|
|
|
|
|
|
static UInt32* Bt3_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
|
|
{
|
|
UInt32 mmm;
|
|
UInt32 h2, d2, pos;
|
|
unsigned maxLen;
|
|
UInt32 *hash;
|
|
GET_MATCHES_HEADER(3)
|
|
|
|
HASH3_CALC
|
|
|
|
hash = p->hash;
|
|
pos = p->pos;
|
|
|
|
d2 = pos - hash[h2];
|
|
|
|
curMatch = (hash + kFix3HashSize)[hv];
|
|
|
|
hash[h2] = pos;
|
|
(hash + kFix3HashSize)[hv] = pos;
|
|
|
|
SET_mmm
|
|
|
|
maxLen = 2;
|
|
|
|
if (d2 < mmm && *(cur - d2) == *cur)
|
|
{
|
|
UPDATE_maxLen
|
|
distances[0] = (UInt32)maxLen;
|
|
distances[1] = d2 - 1;
|
|
distances += 2;
|
|
if (maxLen == lenLimit)
|
|
{
|
|
SkipMatchesSpec(MF_PARAMS(p));
|
|
MOVE_POS_RET
|
|
}
|
|
}
|
|
|
|
GET_MATCHES_FOOTER_BT(maxLen)
|
|
}
|
|
|
|
|
|
static UInt32* Bt4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
|
|
{
|
|
UInt32 mmm;
|
|
UInt32 h2, h3, d2, d3, pos;
|
|
unsigned maxLen;
|
|
UInt32 *hash;
|
|
GET_MATCHES_HEADER(4)
|
|
|
|
HASH4_CALC
|
|
|
|
hash = p->hash;
|
|
pos = p->pos;
|
|
|
|
d2 = pos - hash [h2];
|
|
d3 = pos - (hash + kFix3HashSize)[h3];
|
|
curMatch = (hash + kFix4HashSize)[hv];
|
|
|
|
hash [h2] = pos;
|
|
(hash + kFix3HashSize)[h3] = pos;
|
|
(hash + kFix4HashSize)[hv] = pos;
|
|
|
|
SET_mmm
|
|
|
|
maxLen = 3;
|
|
|
|
for (;;)
|
|
{
|
|
if (d2 < mmm && *(cur - d2) == *cur)
|
|
{
|
|
distances[0] = 2;
|
|
distances[1] = d2 - 1;
|
|
distances += 2;
|
|
if (*(cur - d2 + 2) == cur[2])
|
|
{
|
|
// distances[-2] = 3;
|
|
}
|
|
else if (d3 < mmm && *(cur - d3) == *cur)
|
|
{
|
|
d2 = d3;
|
|
distances[1] = d3 - 1;
|
|
distances += 2;
|
|
}
|
|
else
|
|
break;
|
|
}
|
|
else if (d3 < mmm && *(cur - d3) == *cur)
|
|
{
|
|
d2 = d3;
|
|
distances[1] = d3 - 1;
|
|
distances += 2;
|
|
}
|
|
else
|
|
break;
|
|
|
|
UPDATE_maxLen
|
|
distances[-2] = (UInt32)maxLen;
|
|
if (maxLen == lenLimit)
|
|
{
|
|
SkipMatchesSpec(MF_PARAMS(p));
|
|
MOVE_POS_RET
|
|
}
|
|
break;
|
|
}
|
|
|
|
GET_MATCHES_FOOTER_BT(maxLen)
|
|
}
|
|
|
|
|
|
static UInt32* Bt5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
|
|
{
|
|
UInt32 mmm;
|
|
UInt32 h2, h3, d2, d3, maxLen, pos;
|
|
UInt32 *hash;
|
|
GET_MATCHES_HEADER(5)
|
|
|
|
HASH5_CALC
|
|
|
|
hash = p->hash;
|
|
pos = p->pos;
|
|
|
|
d2 = pos - hash [h2];
|
|
d3 = pos - (hash + kFix3HashSize)[h3];
|
|
// d4 = pos - (hash + kFix4HashSize)[h4];
|
|
|
|
curMatch = (hash + kFix5HashSize)[hv];
|
|
|
|
hash [h2] = pos;
|
|
(hash + kFix3HashSize)[h3] = pos;
|
|
// (hash + kFix4HashSize)[h4] = pos;
|
|
(hash + kFix5HashSize)[hv] = pos;
|
|
|
|
SET_mmm
|
|
|
|
maxLen = 4;
|
|
|
|
for (;;)
|
|
{
|
|
if (d2 < mmm && *(cur - d2) == *cur)
|
|
{
|
|
distances[0] = 2;
|
|
distances[1] = d2 - 1;
|
|
distances += 2;
|
|
if (*(cur - d2 + 2) == cur[2])
|
|
{
|
|
}
|
|
else if (d3 < mmm && *(cur - d3) == *cur)
|
|
{
|
|
distances[1] = d3 - 1;
|
|
distances += 2;
|
|
d2 = d3;
|
|
}
|
|
else
|
|
break;
|
|
}
|
|
else if (d3 < mmm && *(cur - d3) == *cur)
|
|
{
|
|
distances[1] = d3 - 1;
|
|
distances += 2;
|
|
d2 = d3;
|
|
}
|
|
else
|
|
break;
|
|
|
|
distances[-2] = 3;
|
|
if (*(cur - d2 + 3) != cur[3])
|
|
break;
|
|
UPDATE_maxLen
|
|
distances[-2] = (UInt32)maxLen;
|
|
if (maxLen == lenLimit)
|
|
{
|
|
SkipMatchesSpec(MF_PARAMS(p));
|
|
MOVE_POS_RET
|
|
}
|
|
break;
|
|
}
|
|
|
|
GET_MATCHES_FOOTER_BT(maxLen)
|
|
}
|
|
|
|
|
|
static UInt32* Hc4_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
|
|
{
|
|
UInt32 mmm;
|
|
UInt32 h2, h3, d2, d3, pos;
|
|
unsigned maxLen;
|
|
UInt32 *hash;
|
|
GET_MATCHES_HEADER(4)
|
|
|
|
HASH4_CALC
|
|
|
|
hash = p->hash;
|
|
pos = p->pos;
|
|
|
|
d2 = pos - hash [h2];
|
|
d3 = pos - (hash + kFix3HashSize)[h3];
|
|
curMatch = (hash + kFix4HashSize)[hv];
|
|
|
|
hash [h2] = pos;
|
|
(hash + kFix3HashSize)[h3] = pos;
|
|
(hash + kFix4HashSize)[hv] = pos;
|
|
|
|
SET_mmm
|
|
|
|
maxLen = 3;
|
|
|
|
for (;;)
|
|
{
|
|
if (d2 < mmm && *(cur - d2) == *cur)
|
|
{
|
|
distances[0] = 2;
|
|
distances[1] = d2 - 1;
|
|
distances += 2;
|
|
if (*(cur - d2 + 2) == cur[2])
|
|
{
|
|
// distances[-2] = 3;
|
|
}
|
|
else if (d3 < mmm && *(cur - d3) == *cur)
|
|
{
|
|
d2 = d3;
|
|
distances[1] = d3 - 1;
|
|
distances += 2;
|
|
}
|
|
else
|
|
break;
|
|
}
|
|
else if (d3 < mmm && *(cur - d3) == *cur)
|
|
{
|
|
d2 = d3;
|
|
distances[1] = d3 - 1;
|
|
distances += 2;
|
|
}
|
|
else
|
|
break;
|
|
|
|
UPDATE_maxLen
|
|
distances[-2] = (UInt32)maxLen;
|
|
if (maxLen == lenLimit)
|
|
{
|
|
p->son[p->cyclicBufferPos] = curMatch;
|
|
MOVE_POS_RET
|
|
}
|
|
break;
|
|
}
|
|
|
|
GET_MATCHES_FOOTER_HC(maxLen)
|
|
}
|
|
|
|
|
|
static UInt32 * Hc5_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
|
|
{
|
|
UInt32 mmm;
|
|
UInt32 h2, h3, d2, d3, maxLen, pos;
|
|
UInt32 *hash;
|
|
GET_MATCHES_HEADER(5)
|
|
|
|
HASH5_CALC
|
|
|
|
hash = p->hash;
|
|
pos = p->pos;
|
|
|
|
d2 = pos - hash [h2];
|
|
d3 = pos - (hash + kFix3HashSize)[h3];
|
|
// d4 = pos - (hash + kFix4HashSize)[h4];
|
|
|
|
curMatch = (hash + kFix5HashSize)[hv];
|
|
|
|
hash [h2] = pos;
|
|
(hash + kFix3HashSize)[h3] = pos;
|
|
// (hash + kFix4HashSize)[h4] = pos;
|
|
(hash + kFix5HashSize)[hv] = pos;
|
|
|
|
SET_mmm
|
|
|
|
maxLen = 4;
|
|
|
|
for (;;)
|
|
{
|
|
if (d2 < mmm && *(cur - d2) == *cur)
|
|
{
|
|
distances[0] = 2;
|
|
distances[1] = d2 - 1;
|
|
distances += 2;
|
|
if (*(cur - d2 + 2) == cur[2])
|
|
{
|
|
}
|
|
else if (d3 < mmm && *(cur - d3) == *cur)
|
|
{
|
|
distances[1] = d3 - 1;
|
|
distances += 2;
|
|
d2 = d3;
|
|
}
|
|
else
|
|
break;
|
|
}
|
|
else if (d3 < mmm && *(cur - d3) == *cur)
|
|
{
|
|
distances[1] = d3 - 1;
|
|
distances += 2;
|
|
d2 = d3;
|
|
}
|
|
else
|
|
break;
|
|
|
|
distances[-2] = 3;
|
|
if (*(cur - d2 + 3) != cur[3])
|
|
break;
|
|
UPDATE_maxLen
|
|
distances[-2] = maxLen;
|
|
if (maxLen == lenLimit)
|
|
{
|
|
p->son[p->cyclicBufferPos] = curMatch;
|
|
MOVE_POS_RET
|
|
}
|
|
break;
|
|
}
|
|
|
|
GET_MATCHES_FOOTER_HC(maxLen)
|
|
}
|
|
|
|
|
|
UInt32* Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances)
|
|
{
|
|
GET_MATCHES_HEADER(3)
|
|
HASH_ZIP_CALC
|
|
curMatch = p->hash[hv];
|
|
p->hash[hv] = p->pos;
|
|
GET_MATCHES_FOOTER_HC(2)
|
|
}
|
|
|
|
|
|
static void Bt2_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
|
|
{
|
|
SKIP_HEADER(2)
|
|
{
|
|
HASH2_CALC
|
|
curMatch = p->hash[hv];
|
|
p->hash[hv] = p->pos;
|
|
}
|
|
SKIP_FOOTER
|
|
}
|
|
|
|
void Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
|
|
{
|
|
SKIP_HEADER(3)
|
|
{
|
|
HASH_ZIP_CALC
|
|
curMatch = p->hash[hv];
|
|
p->hash[hv] = p->pos;
|
|
}
|
|
SKIP_FOOTER
|
|
}
|
|
|
|
static void Bt3_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
|
|
{
|
|
SKIP_HEADER(3)
|
|
{
|
|
UInt32 h2;
|
|
UInt32 *hash;
|
|
HASH3_CALC
|
|
hash = p->hash;
|
|
curMatch = (hash + kFix3HashSize)[hv];
|
|
hash[h2] =
|
|
(hash + kFix3HashSize)[hv] = p->pos;
|
|
}
|
|
SKIP_FOOTER
|
|
}
|
|
|
|
static void Bt4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
|
|
{
|
|
SKIP_HEADER(4)
|
|
{
|
|
UInt32 h2, h3;
|
|
UInt32 *hash;
|
|
HASH4_CALC
|
|
hash = p->hash;
|
|
curMatch = (hash + kFix4HashSize)[hv];
|
|
hash [h2] =
|
|
(hash + kFix3HashSize)[h3] =
|
|
(hash + kFix4HashSize)[hv] = p->pos;
|
|
}
|
|
SKIP_FOOTER
|
|
}
|
|
|
|
static void Bt5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
|
|
{
|
|
SKIP_HEADER(5)
|
|
{
|
|
UInt32 h2, h3;
|
|
UInt32 *hash;
|
|
HASH5_CALC
|
|
hash = p->hash;
|
|
curMatch = (hash + kFix5HashSize)[hv];
|
|
hash [h2] =
|
|
(hash + kFix3HashSize)[h3] =
|
|
// (hash + kFix4HashSize)[h4] =
|
|
(hash + kFix5HashSize)[hv] = p->pos;
|
|
}
|
|
SKIP_FOOTER
|
|
}
|
|
|
|
|
|
#define HC_SKIP_HEADER(minLen) \
|
|
do { if (p->lenLimit < minLen) { MatchFinder_MovePos(p); num--; continue; } { \
|
|
const Byte *cur; \
|
|
UInt32 *hash; \
|
|
UInt32 *son; \
|
|
UInt32 pos = p->pos; \
|
|
UInt32 num2 = num; \
|
|
/* (p->pos == p->posLimit) is not allowed here !!! */ \
|
|
{ const UInt32 rem = p->posLimit - pos; if (num2 > rem) num2 = rem; } \
|
|
num -= num2; \
|
|
{ const UInt32 cycPos = p->cyclicBufferPos; \
|
|
son = p->son + cycPos; \
|
|
p->cyclicBufferPos = cycPos + num2; } \
|
|
cur = p->buffer; \
|
|
hash = p->hash; \
|
|
do { \
|
|
UInt32 curMatch; \
|
|
UInt32 hv;
|
|
|
|
|
|
#define HC_SKIP_FOOTER \
|
|
cur++; pos++; *son++ = curMatch; \
|
|
} while (--num2); \
|
|
p->buffer = cur; \
|
|
p->pos = pos; \
|
|
if (pos == p->posLimit) MatchFinder_CheckLimits(p); \
|
|
}} while(num); \
|
|
|
|
|
|
static void Hc4_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
|
|
{
|
|
HC_SKIP_HEADER(4)
|
|
|
|
UInt32 h2, h3;
|
|
HASH4_CALC
|
|
curMatch = (hash + kFix4HashSize)[hv];
|
|
hash [h2] =
|
|
(hash + kFix3HashSize)[h3] =
|
|
(hash + kFix4HashSize)[hv] = pos;
|
|
|
|
HC_SKIP_FOOTER
|
|
}
|
|
|
|
|
|
static void Hc5_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
|
|
{
|
|
HC_SKIP_HEADER(5)
|
|
|
|
UInt32 h2, h3;
|
|
HASH5_CALC
|
|
curMatch = (hash + kFix5HashSize)[hv];
|
|
hash [h2] =
|
|
(hash + kFix3HashSize)[h3] =
|
|
// (hash + kFix4HashSize)[h4] =
|
|
(hash + kFix5HashSize)[hv] = pos;
|
|
|
|
HC_SKIP_FOOTER
|
|
}
|
|
|
|
|
|
void Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num)
|
|
{
|
|
HC_SKIP_HEADER(3)
|
|
|
|
HASH_ZIP_CALC
|
|
curMatch = hash[hv];
|
|
hash[hv] = pos;
|
|
|
|
HC_SKIP_FOOTER
|
|
}
|
|
|
|
|
|
void MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder2 *vTable)
|
|
{
|
|
vTable->Init = (Mf_Init_Func)MatchFinder_Init;
|
|
vTable->GetNumAvailableBytes = (Mf_GetNumAvailableBytes_Func)MatchFinder_GetNumAvailableBytes;
|
|
vTable->GetPointerToCurrentPos = (Mf_GetPointerToCurrentPos_Func)MatchFinder_GetPointerToCurrentPos;
|
|
if (!p->btMode)
|
|
{
|
|
if (p->numHashBytes <= 4)
|
|
{
|
|
vTable->GetMatches = (Mf_GetMatches_Func)Hc4_MatchFinder_GetMatches;
|
|
vTable->Skip = (Mf_Skip_Func)Hc4_MatchFinder_Skip;
|
|
}
|
|
else
|
|
{
|
|
vTable->GetMatches = (Mf_GetMatches_Func)Hc5_MatchFinder_GetMatches;
|
|
vTable->Skip = (Mf_Skip_Func)Hc5_MatchFinder_Skip;
|
|
}
|
|
}
|
|
else if (p->numHashBytes == 2)
|
|
{
|
|
vTable->GetMatches = (Mf_GetMatches_Func)Bt2_MatchFinder_GetMatches;
|
|
vTable->Skip = (Mf_Skip_Func)Bt2_MatchFinder_Skip;
|
|
}
|
|
else if (p->numHashBytes == 3)
|
|
{
|
|
vTable->GetMatches = (Mf_GetMatches_Func)Bt3_MatchFinder_GetMatches;
|
|
vTable->Skip = (Mf_Skip_Func)Bt3_MatchFinder_Skip;
|
|
}
|
|
else if (p->numHashBytes == 4)
|
|
{
|
|
vTable->GetMatches = (Mf_GetMatches_Func)Bt4_MatchFinder_GetMatches;
|
|
vTable->Skip = (Mf_Skip_Func)Bt4_MatchFinder_Skip;
|
|
}
|
|
else
|
|
{
|
|
vTable->GetMatches = (Mf_GetMatches_Func)Bt5_MatchFinder_GetMatches;
|
|
vTable->Skip = (Mf_Skip_Func)Bt5_MatchFinder_Skip;
|
|
}
|
|
}
|
|
|
|
|
|
|
|
void LzFindPrepare(void)
|
|
{
|
|
#ifndef FORCE_LZFIND_SATUR_SUB_128
|
|
#ifdef USE_LZFIND_SATUR_SUB_128
|
|
LZFIND_SATUR_SUB_CODE_FUNC f = NULL;
|
|
#ifdef MY_CPU_ARM_OR_ARM64
|
|
{
|
|
if (CPU_IsSupported_NEON())
|
|
{
|
|
// #pragma message ("=== LzFind NEON")
|
|
PRF(printf("\n=== LzFind NEON\n"));
|
|
f = LzFind_SaturSub_128;
|
|
}
|
|
// f = 0; // for debug
|
|
}
|
|
#else // MY_CPU_ARM_OR_ARM64
|
|
if (CPU_IsSupported_SSE41())
|
|
{
|
|
// #pragma message ("=== LzFind SSE41")
|
|
PRF(printf("\n=== LzFind SSE41\n"));
|
|
f = LzFind_SaturSub_128;
|
|
|
|
#ifdef USE_LZFIND_SATUR_SUB_256
|
|
if (CPU_IsSupported_AVX2())
|
|
{
|
|
// #pragma message ("=== LzFind AVX2")
|
|
PRF(printf("\n=== LzFind AVX2\n"));
|
|
f = LzFind_SaturSub_256;
|
|
}
|
|
#endif
|
|
}
|
|
#endif // MY_CPU_ARM_OR_ARM64
|
|
g_LzFind_SaturSub = f;
|
|
#endif // USE_LZFIND_SATUR_SUB_128
|
|
#endif // FORCE_LZFIND_SATUR_SUB_128
|
|
}
|
|
|
|
|
|
#undef MOVE_POS
|
|
#undef MOVE_POS_RET
|
|
#undef PRF
|