File:
[ELWIX - Embedded LightWeight unIX -] /
elwix /
tools /
oldlzma /
SRC /
7zip /
Compress /
LZ /
Patricia /
Pat.h
Revision
1.1.1.1 (vendor branch):
download - view:
text,
annotated -
select for diffs -
revision graph
Tue May 14 09:04:51 2013 UTC (11 years, 5 months ago) by
misho
Branches:
misho,
elwix1_9_mips,
MAIN
CVS tags:
start,
elwix2_8,
elwix2_7,
elwix2_6,
elwix2_3,
elwix2_2,
HEAD,
ELWIX2_7,
ELWIX2_6,
ELWIX2_5,
ELWIX2_2p0
oldlzma needs for uboot
// Pat.h
// #ifndef __PATRICIA__H
// #define __PATRICIA__H
#include "../../../../Common/MyCom.h"
#include "../../../../Common/Types.h"
#include "../LZInWindow.h"
namespace PAT_NAMESPACE {
struct CNode;
typedef CNode *CNodePointer;
// #define __AUTO_REMOVE
// #define __NODE_4_BITS
// #define __NODE_3_BITS
// #define __NODE_2_BITS
// #define __NODE_2_BITS_PADDING
// #define __HASH_3
typedef UInt32 CIndex;
#ifdef __NODE_4_BITS
typedef UInt32 CIndex2;
typedef UInt32 CSameBitsType;
#else
#ifdef __NODE_3_BITS
typedef UInt32 CIndex2;
typedef UInt32 CSameBitsType;
#else
typedef UInt32 CIndex;
typedef UInt32 CSameBitsType;
typedef CIndex CIndex2;
#endif
#endif
const UInt32 kNumBitsInIndex = sizeof(CIndex) * 8;
const UInt32 kMatchStartValue = UInt32(1) << (kNumBitsInIndex - 1);
// don't change kMatchStartValue definition, since it is used in
// PatMain.h:
typedef CIndex CMatchPointer;
const UInt32 kDescendantEmptyValue = kMatchStartValue - 1;
union CDescendant
{
CIndex NodePointer;
CMatchPointer MatchPointer;
bool IsEmpty() const { return NodePointer == kDescendantEmptyValue; }
bool IsNode() const { return NodePointer < kDescendantEmptyValue; }
bool IsMatch() const { return NodePointer > kDescendantEmptyValue; }
void MakeEmpty() { NodePointer = kDescendantEmptyValue; }
};
#undef MY_BYTE_SIZE
#ifdef __NODE_4_BITS
#define MY_BYTE_SIZE 8
const UInt32 kNumSubBits = 4;
#else
#ifdef __NODE_3_BITS
#define MY_BYTE_SIZE 9
const UInt32 kNumSubBits = 3;
#else
#define MY_BYTE_SIZE 8
#ifdef __NODE_2_BITS
const UInt32 kNumSubBits = 2;
#else
const UInt32 kNumSubBits = 1;
#endif
#endif
#endif
const UInt32 kNumSubNodes = 1 << kNumSubBits;
const UInt32 kSubNodesMask = kNumSubNodes - 1;
struct CNode
{
CIndex2 LastMatch;
CSameBitsType NumSameBits;
union
{
CDescendant Descendants[kNumSubNodes];
UInt32 NextFreeNode;
};
#ifdef __NODE_2_BITS
#ifdef __NODE_2_BITS_PADDING
UInt32 Padding[2];
#endif
#endif
};
#undef kIDNumBitsByte
#undef kIDNumBitsString
#ifdef __NODE_4_BITS
#define kIDNumBitsByte 0x30
#define kIDNumBitsString TEXT("4")
#else
#ifdef __NODE_3_BITS
#define kIDNumBitsByte 0x20
#define kIDNumBitsString TEXT("3")
#else
#ifdef __NODE_2_BITS
#define kIDNumBitsByte 0x10
#define kIDNumBitsString TEXT("2")
#else
#define kIDNumBitsByte 0x00
#define kIDNumBitsString TEXT("1")
#endif
#endif
#endif
#undef kIDManualRemoveByte
#undef kIDManualRemoveString
#ifdef __AUTO_REMOVE
#define kIDManualRemoveByte 0x00
#define kIDManualRemoveString TEXT("")
#else
#define kIDManualRemoveByte 0x08
#define kIDManualRemoveString TEXT("R")
#endif
#undef kIDHash3Byte
#undef kIDHash3String
#ifdef __HASH_3
#define kIDHash3Byte 0x04
#define kIDHash3String TEXT("H")
#else
#define kIDHash3Byte 0x00
#define kIDHash3String TEXT("")
#endif
#undef kIDUse3BytesByte
#undef kIDUse3BytesString
#define kIDUse3BytesByte 0x00
#define kIDUse3BytesString TEXT("")
#undef kIDPaddingByte
#undef kIDPaddingString
#ifdef __NODE_2_BITS_PADDING
#define kIDPaddingByte 0x01
#define kIDPaddingString TEXT("P")
#else
#define kIDPaddingByte 0x00
#define kIDPaddingString TEXT("")
#endif
// #undef kIDString
// #define kIDString TEXT("Compress.MatchFinderPat") kIDNumBitsString kIDManualRemoveString kIDUse3BytesString kIDPaddingString kIDHash3String
// {23170F69-40C1-278C-01XX-0000000000}
DEFINE_GUID(PAT_CLSID,
0x23170F69, 0x40C1, 0x278C, 0x01,
kIDNumBitsByte |
kIDManualRemoveByte | kIDHash3Byte | kIDUse3BytesByte | kIDPaddingByte,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00);
// III(PAT_NAMESPACE)
class CPatricia:
public IMatchFinder,
public IMatchFinderSetCallback,
public CMyUnknownImp,
CLZInWindow
{
MY_UNKNOWN_IMP1(IMatchFinderSetCallback)
STDMETHOD(Init)(ISequentialInStream *aStream);
STDMETHOD_(void, ReleaseStream)();
STDMETHOD(MovePos)();
STDMETHOD_(Byte, GetIndexByte)(Int32 index);
STDMETHOD_(UInt32, GetMatchLen)(Int32 index, UInt32 back, UInt32 limit);
STDMETHOD_(UInt32, GetNumAvailableBytes)();
STDMETHOD(Create)(UInt32 historySize,
UInt32 keepAddBufferBefore, UInt32 matchMaxLen,
UInt32 keepAddBufferAfter);
STDMETHOD_(UInt32, GetLongestMatch)(UInt32 *distances);
STDMETHOD_(void, DummyLongestMatch)();
STDMETHOD_(const Byte *, GetPointerToCurrentPos)();
void FreeMemory();
public:
CPatricia();
~CPatricia();
UInt32 _sizeHistory;
UInt32 _matchMaxLen;
CDescendant *m_HashDescendants;
#ifdef __HASH_3
CDescendant *m_Hash2Descendants;
#endif
CNode *m_Nodes;
UInt32 m_FreeNode;
UInt32 m_FreeNodeMax;
#ifdef __AUTO_REMOVE
UInt32 m_NumUsedNodes;
UInt32 m_NumNodes;
#else
bool m_SpecialRemoveMode;
#endif
bool m_SpecialMode;
UInt32 m_NumNotChangedCycles;
UInt32 *m_TmpBacks;
CMyComPtr<IMatchFinderCallback> m_Callback;
virtual void BeforeMoveBlock();
virtual void AfterMoveBlock();
// IMatchFinderSetCallback
STDMETHOD(SetCallback)(IMatchFinderCallback *callback);
void ChangeLastMatch(UInt32 hashValue);
#ifdef __AUTO_REMOVE
void TestRemoveDescendant(CDescendant &descendant, UInt32 limitPos);
void TestRemoveNodes();
void RemoveNode(UInt32 index);
void TestRemoveAndNormalizeDescendant(CDescendant &descendant,
UInt32 limitPos, UInt32 subValue);
void TestRemoveNodesAndNormalize();
#else
void NormalizeDescendant(CDescendant &descendant, UInt32 subValue);
void Normalize();
void RemoveMatch();
#endif
private:
void AddInternalNode(CNodePointer aNode, CIndex *aNodePointerPointer,
Byte aByte, Byte aByteXOR, UInt32 aNumSameBits, UInt32 aPos)
{
while((aByteXOR & kSubNodesMask) == 0)
{
aByteXOR >>= kNumSubBits;
aByte >>= kNumSubBits;
aNumSameBits -= kNumSubBits;
}
// Insert New Node
CNodePointer aNewNode = &m_Nodes[m_FreeNode];
UInt32 aNodeIndex = *aNodePointerPointer;
*aNodePointerPointer = m_FreeNode;
m_FreeNode = aNewNode->NextFreeNode;
#ifdef __AUTO_REMOVE
m_NumUsedNodes++;
#endif
if (m_FreeNode > m_FreeNodeMax)
{
m_FreeNodeMax = m_FreeNode;
m_Nodes[m_FreeNode].NextFreeNode = m_FreeNode + 1;
}
UInt32 aBitsNew = aByte & kSubNodesMask;
UInt32 aBitsOld = (aByte ^ aByteXOR) & kSubNodesMask;
for (UInt32 i = 0; i < kNumSubNodes; i++)
aNewNode->Descendants[i].NodePointer = kDescendantEmptyValue;
aNewNode->Descendants[aBitsNew].MatchPointer = aPos + kMatchStartValue;
aNewNode->Descendants[aBitsOld].NodePointer = aNodeIndex;
aNewNode->NumSameBits = CSameBitsType(aNode->NumSameBits - aNumSameBits);
aNewNode->LastMatch = aPos;
aNode->NumSameBits = CSameBitsType(aNumSameBits - kNumSubBits);
}
void AddLeafNode(CNodePointer aNode, Byte aByte, Byte aByteXOR,
UInt32 aNumSameBits, UInt32 aPos, UInt32 aDescendantIndex)
{
for(;(aByteXOR & kSubNodesMask) == 0; aNumSameBits += kNumSubBits)
{
aByte >>= kNumSubBits;
aByteXOR >>= kNumSubBits;
}
UInt32 aNewNodeIndex = m_FreeNode;
CNodePointer aNewNode = &m_Nodes[m_FreeNode];
m_FreeNode = aNewNode->NextFreeNode;
#ifdef __AUTO_REMOVE
m_NumUsedNodes++;
#endif
if (m_FreeNode > m_FreeNodeMax)
{
m_FreeNodeMax = m_FreeNode;
m_Nodes[m_FreeNode].NextFreeNode = m_FreeNode + 1;
}
UInt32 aBitsNew = (aByte & kSubNodesMask);
UInt32 aBitsOld = (aByte ^ aByteXOR) & kSubNodesMask;
for (UInt32 i = 0; i < kNumSubNodes; i++)
aNewNode->Descendants[i].NodePointer = kDescendantEmptyValue;
aNewNode->Descendants[aBitsNew].MatchPointer = aPos + kMatchStartValue;
aNewNode->Descendants[aBitsOld].MatchPointer =
aNode->Descendants[aDescendantIndex].MatchPointer;
aNewNode->NumSameBits = CSameBitsType(aNumSameBits);
aNewNode->LastMatch = aPos;
aNode->Descendants[aDescendantIndex].NodePointer = aNewNodeIndex;
}
};
}
// #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to Pat.h CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / elwix / tools / oldlzma / SRC / 7zip / Compress / LZ / Patricia