1c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org/* LzFind.h -- Match finder for LZ algorithms 292ae1613a125071690336a57cedd4dd9e298cf20agl@chromium.org2009-04-22 : Igor Pavlov : Public domain 392ae1613a125071690336a57cedd4dd9e298cf20agl@chromium.orgin the public domain */ 4c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 5c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#ifndef __LZ_FIND_H 6c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#define __LZ_FIND_H 7c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 8c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#include "Types.h" 9c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 10c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#ifdef __cplusplus 11c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgextern "C" { 12c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#endif 13c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 14c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgtypedef UInt32 CLzRef; 15c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 16c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgtypedef struct _CMatchFinder 17c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org{ 18c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org Byte *buffer; 19c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 pos; 20c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 posLimit; 21c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 streamPos; 22c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 lenLimit; 23c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 24c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 cyclicBufferPos; 25c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 cyclicBufferSize; /* it must be = (historySize + 1) */ 26c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 27c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 matchMaxLen; 28c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org CLzRef *hash; 29c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org CLzRef *son; 30c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 hashMask; 31c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 cutValue; 32c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 33c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org Byte *bufferBase; 34c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org ISeqInStream *stream; 35c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org int streamEndWasReached; 36c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 37c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 blockSize; 38c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 keepSizeBefore; 39c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 keepSizeAfter; 40c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 41c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 numHashBytes; 42c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org int directInput; 43c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org size_t directInputRem; 44c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org int btMode; 45c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org int bigHash; 46c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 historySize; 47c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 fixedHashSize; 48c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 hashSizeSum; 49c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 numSons; 50c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org SRes result; 51c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 crc[256]; 52c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org} CMatchFinder; 53c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 54c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#define Inline_MatchFinder_GetPointerToCurrentPos(p) ((p)->buffer) 55c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#define Inline_MatchFinder_GetIndexByte(p, index) ((p)->buffer[(Int32)(index)]) 56c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 57c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#define Inline_MatchFinder_GetNumAvailableBytes(p) ((p)->streamPos - (p)->pos) 58c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 59c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgint MatchFinder_NeedMove(CMatchFinder *p); 60c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgByte *MatchFinder_GetPointerToCurrentPos(CMatchFinder *p); 61c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgvoid MatchFinder_MoveBlock(CMatchFinder *p); 62c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgvoid MatchFinder_ReadIfRequired(CMatchFinder *p); 63c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 64c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgvoid MatchFinder_Construct(CMatchFinder *p); 65c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 66c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org/* Conditions: 67c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org historySize <= 3 GB 68c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org keepAddBufferBefore + matchMaxLen + keepAddBufferAfter < 511MB 69c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org*/ 70c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgint MatchFinder_Create(CMatchFinder *p, UInt32 historySize, 71c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 keepAddBufferBefore, UInt32 matchMaxLen, UInt32 keepAddBufferAfter, 72c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org ISzAlloc *alloc); 73c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgvoid MatchFinder_Free(CMatchFinder *p, ISzAlloc *alloc); 74c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgvoid MatchFinder_Normalize3(UInt32 subValue, CLzRef *items, UInt32 numItems); 75c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgvoid MatchFinder_ReduceOffsets(CMatchFinder *p, UInt32 subValue); 76c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 77c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgUInt32 * GetMatchesSpec1(UInt32 lenLimit, UInt32 curMatch, UInt32 pos, const Byte *buffer, CLzRef *son, 78c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 _cyclicBufferPos, UInt32 _cyclicBufferSize, UInt32 _cutValue, 79c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org UInt32 *distances, UInt32 maxLen); 80c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 81c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org/* 82c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgConditions: 83c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org Mf_GetNumAvailableBytes_Func must be called before each Mf_GetMatchLen_Func. 84c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org Mf_GetPointerToCurrentPos_Func's result must be used only before any other function 85c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org*/ 86c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 87c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgtypedef void (*Mf_Init_Func)(void *object); 88c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgtypedef Byte (*Mf_GetIndexByte_Func)(void *object, Int32 index); 89c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgtypedef UInt32 (*Mf_GetNumAvailableBytes_Func)(void *object); 90c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgtypedef const Byte * (*Mf_GetPointerToCurrentPos_Func)(void *object); 91c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgtypedef UInt32 (*Mf_GetMatches_Func)(void *object, UInt32 *distances); 92c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgtypedef void (*Mf_Skip_Func)(void *object, UInt32); 93c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 94c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgtypedef struct _IMatchFinder 95c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org{ 96c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org Mf_Init_Func Init; 97c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org Mf_GetIndexByte_Func GetIndexByte; 98c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org Mf_GetNumAvailableBytes_Func GetNumAvailableBytes; 99c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org Mf_GetPointerToCurrentPos_Func GetPointerToCurrentPos; 100c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org Mf_GetMatches_Func GetMatches; 101c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org Mf_Skip_Func Skip; 102c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org} IMatchFinder; 103c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 104c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgvoid MatchFinder_CreateVTable(CMatchFinder *p, IMatchFinder *vTable); 105c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 106c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgvoid MatchFinder_Init(CMatchFinder *p); 107c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgUInt32 Bt3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances); 108c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgUInt32 Hc3Zip_MatchFinder_GetMatches(CMatchFinder *p, UInt32 *distances); 109c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgvoid Bt3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num); 110c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.orgvoid Hc3Zip_MatchFinder_Skip(CMatchFinder *p, UInt32 num); 111c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 112c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#ifdef __cplusplus 113c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org} 114c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#endif 115c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org 116c2a937599a1ec33cd0f57649580e93ff25b22fcabashi@chromium.org#endif 117