Add hostTools from https://github.com/Noltari/cfe_bcm63xx

1 files changed, 502 insertions, 0 deletions

diff --git a/hostTools/lzma/compress/BinTreeMain.h b/hostTools/lzma/compress/BinTreeMain.h
new file mode 100644
index 0000000..f452a94
--- /dev/null
+++ b/hostTools/lzma/compress/BinTreeMain.h
@@ -0,0 +1,502 @@
+#include "CRC.h"
+
+namespace BT_NAMESPACE {
+
+#ifdef HASH_ARRAY_2
+  static const UINT32 kHash2Size = 1 << 10;
+  #ifdef HASH_ARRAY_3
+    static const UINT32 kNumHashDirectBytes = 0;
+    static const UINT32 kNumHashBytes = 4;
+    static const UINT32 kHash3Size = 1 << 18;
+    #ifdef HASH_BIG
+    static const UINT32 kHashSize = 1 << 23;
+    #else
+    static const UINT32 kHashSize = 1 << 20;
+    #endif
+  #else
+    static const UINT32 kNumHashDirectBytes = 3;
+    static const UINT32 kNumHashBytes = 3;
+    static const UINT32 kHashSize = 1 << (8 * kNumHashBytes);
+  #endif
+#else
+  #ifdef HASH_ZIP 
+    static const UINT32 kNumHashDirectBytes = 0;
+    static const UINT32 kNumHashBytes = 3;
+    static const UINT32 kHashSize = 1 << 16;
+  #else
+    static const UINT32 kNumHashDirectBytes = 2;
+    static const UINT32 kNumHashBytes = 2;
+    static const UINT32 kHashSize = 1 << (8 * kNumHashBytes);
+  #endif
+#endif
+
+CInTree::CInTree():
+  #ifdef HASH_ARRAY_2
+  m_Hash2(0),
+  #ifdef HASH_ARRAY_3
+  m_Hash3(0),
+  #endif
+  #endif
+  m_Hash(0),
+  m_Base(0),
+  m_CutValue(0xFF)
+{
+}
+
+void CInTree::FreeMemory()
+{
+  if (m_Base != 0)
+	delete [] m_Base;
+  if (m_Hash != 0)
+	delete [] m_Hash;
+  m_Base = 0;
+  m_Hash = 0;
+  CIn::Free();
+}
+
+CInTree::~CInTree()
+{ 
+  FreeMemory();
+}
+
+HRESULT CInTree::Create(UINT32 aSizeHistory, UINT32 aKeepAddBufferBefore, 
+    UINT32 aMatchMaxLen, UINT32 aKeepAddBufferAfter, UINT32 aSizeReserv)
+{
+  FreeMemory();
+    CIn::Create(aSizeHistory + aKeepAddBufferBefore, 
+      aMatchMaxLen + aKeepAddBufferAfter, aSizeReserv);
+    
+    if (m_BlockSize + 256 > kMaxValForNormalize)
+      return E_INVALIDARG;
+    
+    m_HistorySize = aSizeHistory;
+    m_MatchMaxLen = aMatchMaxLen;
+    
+    
+    UINT32 aSize = kHashSize;
+    #ifdef HASH_ARRAY_2
+    aSize += kHash2Size;
+    #ifdef HASH_ARRAY_3
+    aSize += kHash3Size;
+    #endif
+    #endif
+    
+    m_Base = new CPair[m_BlockSize + 1];
+    if (m_Base == 0)
+	return E_OUTOFMEMORY;
+    m_Hash = new CIndex[aSize + 1];
+    if (m_Hash == 0)
+	return E_OUTOFMEMORY;
+    
+    #ifdef HASH_ARRAY_2
+    m_Hash2 = &m_Hash[kHashSize]; 
+    #ifdef HASH_ARRAY_3
+    m_Hash3 = &m_Hash2[kHash2Size]; 
+    #endif
+    #endif
+    return S_OK;
+}
+
+static const UINT32 kEmptyHashValue = 0;
+
+HRESULT CInTree::Init(ISequentialInStream *aStream)
+{
+  RETURN_IF_NOT_S_OK(CIn::Init(aStream));
+  unsigned i;
+  for(i = 0; i < kHashSize; i++)
+    m_Hash[i] = kEmptyHashValue;
+
+  #ifdef HASH_ARRAY_2
+  for(i = 0; i < kHash2Size; i++)
+    m_Hash2[i] = kEmptyHashValue;
+  #ifdef HASH_ARRAY_3
+  for(i = 0; i < kHash3Size; i++)
+    m_Hash3[i] = kEmptyHashValue;
+  #endif
+  #endif
+
+  m_Son = m_Base;
+
+  ReduceOffsets(0 - 1);
+  return S_OK;
+}
+
+
+#ifdef HASH_ARRAY_2
+#ifdef HASH_ARRAY_3
+inline UINT32 Hash(const BYTE *aPointer, UINT32 &aHash2Value, UINT32 &aHash3Value)
+{
+  UINT32 aTemp = CCRC::m_Table[aPointer[0]] ^ aPointer[1];
+  aHash2Value = aTemp & (kHash2Size - 1);
+  aHash3Value = (aTemp ^ (UINT32(aPointer[2]) << 8)) & (kHash3Size - 1);
+  return (aTemp ^ (UINT32(aPointer[2]) << 8) ^ (CCRC::m_Table[aPointer[3]] << 5)) & 
+      (kHashSize - 1);
+}
+#else // no HASH_ARRAY_3
+inline UINT32 Hash(const BYTE *aPointer, UINT32 &aHash2Value)
+{
+  aHash2Value = (CCRC::m_Table[aPointer[0]] ^ aPointer[1]) & (kHash2Size - 1);
+  return (*((const UINT32 *)aPointer)) & 0xFFFFFF;
+}
+#endif // HASH_ARRAY_3
+#else // no HASH_ARRAY_2
+#ifdef HASH_ZIP 
+inline UINT32 Hash(const BYTE *aPointer)
+{
+  return ((UINT32(aPointer[0]) << 8) ^ 
+      CCRC::m_Table[aPointer[1]] ^ aPointer[2]) & (kHashSize - 1);
+}
+#else // no HASH_ZIP 
+inline UINT32 Hash(const BYTE *aPointer)
+{
+  return aPointer[0] ^ (UINT32(aPointer[1]) << 8);
+}
+#endif // HASH_ZIP
+#endif // HASH_ARRAY_2
+
+UINT32 CInTree::GetLongestMatch(UINT32 *aDistances)
+{
+  UINT32 aCurrentLimit;
+  if (m_Pos + m_MatchMaxLen <= m_StreamPos)
+    aCurrentLimit = m_MatchMaxLen;
+  else
+  {
+    aCurrentLimit = m_StreamPos - m_Pos;
+    if(aCurrentLimit < kNumHashBytes)
+      return 0; 
+  }
+
+  UINT32 aMatchMinPos = (m_Pos > m_HistorySize) ? (m_Pos - m_HistorySize) : 1;
+  BYTE *aCur = m_Buffer + m_Pos;
+  
+  UINT32 aMatchHashLenMax = 0;
+
+  #ifdef HASH_ARRAY_2
+  UINT32 aHash2Value;
+  #ifdef HASH_ARRAY_3
+  UINT32 aHash3Value;
+  UINT32 aHashValue = Hash(aCur, aHash2Value, aHash3Value);
+  #else
+  UINT32 aHashValue = Hash(aCur, aHash2Value);
+  #endif
+  #else
+  UINT32 aHashValue = Hash(aCur);
+  #endif
+
+  UINT32 aCurMatch = m_Hash[aHashValue];
+  #ifdef HASH_ARRAY_2
+  UINT32 aCurMatch2 = m_Hash2[aHash2Value];
+  #ifdef HASH_ARRAY_3
+  UINT32 aCurMatch3 = m_Hash3[aHash3Value];
+  #endif
+  m_Hash2[aHash2Value] = m_Pos;
+  bool aMatchLen2Exist = false;
+  UINT32 aLen2Distance = 0;
+  if(aCurMatch2 >= aMatchMinPos)
+  {
+    if (m_Buffer[aCurMatch2] == aCur[0])
+    {
+      aLen2Distance = m_Pos - aCurMatch2 - 1;
+      aMatchHashLenMax = 2;
+      aMatchLen2Exist = true;
+    }
+  }
+
+  #ifdef HASH_ARRAY_3
+  m_Hash3[aHash3Value] = m_Pos;
+  UINT32 aMatchLen3Exist = false;
+  UINT32 aLen3Distance = 0;
+  if(aCurMatch3 >= aMatchMinPos)
+  {
+    if (m_Buffer[aCurMatch3] == aCur[0])
+    {
+      aLen3Distance = m_Pos - aCurMatch3 - 1;
+      aMatchHashLenMax = 3;
+      aMatchLen3Exist = true;
+      if (aMatchLen2Exist)
+      {
+        if (aLen3Distance < aLen2Distance)
+          aLen2Distance = aLen3Distance;
+      }
+      else
+      {
+        aLen2Distance = aLen3Distance;
+        aMatchLen2Exist = true;
+      }
+    }
+  }
+  #endif
+  #endif
+
+  m_Hash[aHashValue] = m_Pos;
+  if(aCurMatch < aMatchMinPos)
+  {
+    m_Son[m_Pos].Left = kEmptyHashValue; 
+    m_Son[m_Pos].Right = kEmptyHashValue; 
+
+    #ifdef HASH_ARRAY_2
+    aDistances[2] = aLen2Distance;
+    #ifdef HASH_ARRAY_3
+    aDistances[3] = aLen3Distance;
+    #endif
+    #endif
+
+    return aMatchHashLenMax;
+  }
+  CIndex *aPtrLeft = &m_Son[m_Pos].Right;
+  CIndex *aPtrRight = &m_Son[m_Pos].Left;
+
+  UINT32 aMax, aMinSameLeft, aMinSameRight, aMinSame;
+  aMax = aMinSameLeft = aMinSameRight = aMinSame = kNumHashDirectBytes;
+
+  #ifdef HASH_ARRAY_2
+  #ifndef HASH_ARRAY_3
+    if (aMatchLen2Exist)
+      aDistances[2] = aLen2Distance;
+    else
+      if (kNumHashDirectBytes >= 2)
+        aDistances[2] = m_Pos - aCurMatch - 1;
+  #endif
+  #endif
+
+  aDistances[aMax] = m_Pos - aCurMatch - 1;
+  
+  for(UINT32 aCount = m_CutValue; aCount > 0; aCount--)
+  {
+    BYTE *pby1 = m_Buffer + aCurMatch;
+    // CIndex aLeft = m_Son[aCurMatch].Left; // it's prefetch
+    UINT32 aCurrentLen;
+    for(aCurrentLen = aMinSame; aCurrentLen < aCurrentLimit; aCurrentLen++/*, dwComps++*/)
+      if (pby1[aCurrentLen] != aCur[aCurrentLen])
+        break;
+    while (aCurrentLen > aMax)
+      aDistances[++aMax] = m_Pos - aCurMatch - 1;
+    if (aCurrentLen != aCurrentLimit)
+    {
+      if (pby1[aCurrentLen] < aCur[aCurrentLen])
+      {
+        *aPtrRight = aCurMatch;
+        aPtrRight = &m_Son[aCurMatch].Right;
+        aCurMatch = m_Son[aCurMatch].Right;
+        if(aCurrentLen > aMinSameLeft)
+        {
+          aMinSameLeft = aCurrentLen;
+          aMinSame = MyMin(aMinSameLeft, aMinSameRight);
+        }
+      }
+      else
+      {
+        *aPtrLeft = aCurMatch;
+        aPtrLeft = &m_Son[aCurMatch].Left;
+        // aCurMatch = aLeft;
+        aCurMatch = m_Son[aCurMatch].Left;
+        if(aCurrentLen > aMinSameRight)
+        {
+          aMinSameRight = aCurrentLen;
+          aMinSame = MyMin(aMinSameLeft, aMinSameRight);
+        }
+      }
+    }
+    else
+    {
+      if(aCurrentLen < m_MatchMaxLen)
+      {
+        *aPtrLeft = aCurMatch;
+        aPtrLeft = &m_Son[aCurMatch].Left;
+        aCurMatch = m_Son[aCurMatch].Left;
+        if(aCurrentLen > aMinSameRight)
+        {
+          aMinSameRight = aCurrentLen;
+          aMinSame = MyMin(aMinSameLeft, aMinSameRight);
+        }
+      }
+      else
+      {
+        *aPtrLeft = m_Son[aCurMatch].Right;
+        *aPtrRight = m_Son[aCurMatch].Left;
+
+        #ifdef HASH_ARRAY_2
+        if (aMatchLen2Exist && aLen2Distance < aDistances[2])
+          aDistances[2] = aLen2Distance;
+        #ifdef HASH_ARRAY_3
+        if (aMatchLen3Exist && aLen3Distance < aDistances[3])
+          aDistances[3] = aLen3Distance;
+        #endif
+        #endif
+
+        return aMax;
+      }
+    }
+    if(aCurMatch < aMatchMinPos)
+      break;
+  }
+  *aPtrLeft = kEmptyHashValue;
+  *aPtrRight = kEmptyHashValue;
+  #ifdef HASH_ARRAY_2
+  if (aMatchLen2Exist)
+  {
+    if (aMax < 2)
+    {
+      aDistances[2] = aLen2Distance;
+      aMax = 2;
+    }
+    else if (aLen2Distance < aDistances[2])
+      aDistances[2] = aLen2Distance;
+  }
+  #ifdef HASH_ARRAY_3
+  if (aMatchLen3Exist)
+  {
+    if (aMax < 3)
+    {
+      aDistances[3] = aLen3Distance;
+      aMax = 3;
+    }
+    else if (aLen3Distance < aDistances[3])
+      aDistances[3] = aLen3Distance;
+  }
+  #endif
+  #endif
+  return aMax;
+}
+
+void CInTree::DummyLongestMatch()
+{
+  UINT32 aCurrentLimit;
+  if (m_Pos + m_MatchMaxLen <= m_StreamPos)
+    aCurrentLimit = m_MatchMaxLen;
+  else
+  {
+    aCurrentLimit = m_StreamPos - m_Pos;
+    if(aCurrentLimit < kNumHashBytes)
+      return; 
+  }
+  UINT32 aMatchMinPos = (m_Pos > m_HistorySize) ? (m_Pos - m_HistorySize) : 1;
+  BYTE *aCur = m_Buffer + m_Pos;
+  
+  #ifdef HASH_ARRAY_2
+  UINT32 aHash2Value;
+  #ifdef HASH_ARRAY_3
+  UINT32 aHash3Value;
+  UINT32 aHashValue = Hash(aCur, aHash2Value, aHash3Value);
+  m_Hash3[aHash3Value] = m_Pos;
+  #else
+  UINT32 aHashValue = Hash(aCur, aHash2Value);
+  #endif
+  m_Hash2[aHash2Value] = m_Pos;
+  #else
+  UINT32 aHashValue = Hash(aCur);
+  #endif
+
+  UINT32 aCurMatch = m_Hash[aHashValue];
+  m_Hash[aHashValue] = m_Pos;
+  if(aCurMatch < aMatchMinPos)
+  {
+    m_Son[m_Pos].Left = kEmptyHashValue; 
+    m_Son[m_Pos].Right = kEmptyHashValue; 
+    return;
+  }
+  CIndex *aPtrLeft = &m_Son[m_Pos].Right;
+  CIndex *aPtrRight = &m_Son[m_Pos].Left;
+
+  UINT32 aMax, aMinSameLeft, aMinSameRight, aMinSame;
+  aMax = aMinSameLeft = aMinSameRight = aMinSame = kNumHashDirectBytes;
+  for(UINT32 aCount = m_CutValue; aCount > 0; aCount--)
+  {
+    BYTE *pby1 = m_Buffer + aCurMatch;
+    // CIndex aLeft = m_Son[aCurMatch].Left; // it's prefetch
+    UINT32 aCurrentLen;
+    for(aCurrentLen = aMinSame; aCurrentLen < aCurrentLimit; aCurrentLen++/*, dwComps++*/)
+      if (pby1[aCurrentLen] != aCur[aCurrentLen])
+        break;
+    if (aCurrentLen != aCurrentLimit)
+    {
+      if (pby1[aCurrentLen] < aCur[aCurrentLen])
+      {
+        *aPtrRight = aCurMatch;
+        aPtrRight = &m_Son[aCurMatch].Right;
+        aCurMatch = m_Son[aCurMatch].Right;
+        if(aCurrentLen > aMinSameLeft)
+        {
+          aMinSameLeft = aCurrentLen;
+          aMinSame = MyMin(aMinSameLeft, aMinSameRight);
+        }
+      }
+      else 
+      {
+        *aPtrLeft = aCurMatch;
+        aPtrLeft = &m_Son[aCurMatch].Left;
+        aCurMatch = m_Son[aCurMatch].Left;
+        // aCurMatch = aLeft;
+        if(aCurrentLen > aMinSameRight)
+        {
+          aMinSameRight = aCurrentLen;
+          aMinSame = MyMin(aMinSameLeft, aMinSameRight);
+        }
+      }
+    }
+    else
+    {
+      if(aCurrentLen < m_MatchMaxLen)
+      {
+        *aPtrLeft = aCurMatch;
+        aPtrLeft = &m_Son[aCurMatch].Left;
+        aCurMatch = m_Son[aCurMatch].Left;
+        if(aCurrentLen > aMinSameRight)
+        {
+          aMinSameRight = aCurrentLen;
+          aMinSame = MyMin(aMinSameLeft, aMinSameRight);
+        }
+      }
+      else
+      {
+        *aPtrLeft = m_Son[aCurMatch].Right;
+        *aPtrRight = m_Son[aCurMatch].Left;
+        return;
+      }
+    }
+    if(aCurMatch < aMatchMinPos)
+      break;
+  }
+  *aPtrLeft = kEmptyHashValue;
+  *aPtrRight = kEmptyHashValue;
+}
+
+void CInTree::AfterMoveBlock()
+{
+  UINT32 aNumBytesToMove = m_HistorySize * sizeof(CPair);
+  UINT32 aSpecOffset = ((m_Son + m_Pos) - m_Base) - m_HistorySize;
+  memmove(m_Base, m_Base + aSpecOffset, aNumBytesToMove);
+  m_Son -= aSpecOffset;
+}
+
+void CInTree::NormalizeLinks(CIndex *anArray, UINT32 aNumItems, UINT32 aSubValue)
+{
+  for (UINT32 i = 0; i < aNumItems; i++)
+  {
+    UINT32 aValue = anArray[i];
+    if (aValue <= aSubValue)
+      aValue = kEmptyHashValue;
+    else
+      aValue -= aSubValue;
+    anArray[i] = aValue;
+  }
+}
+
+void CInTree::Normalize()
+{
+  UINT32 aStartItem = m_Pos - m_HistorySize;
+  UINT32 aSubValue = aStartItem - 1;
+  NormalizeLinks((CIndex *)(m_Son + aStartItem), m_HistorySize * 2, aSubValue);
+  NormalizeLinks(m_Hash, kHashSize, aSubValue);
+
+  #ifdef HASH_ARRAY_2
+  NormalizeLinks(m_Hash2, kHash2Size, aSubValue);
+  #ifdef HASH_ARRAY_3
+  NormalizeLinks(m_Hash3, kHash3Size, aSubValue);
+  #endif
+  #endif
+
+  ReduceOffsets(aSubValue);
+}
+ 
+}