13836648005

Committed 13 Mar 2025 02:09PM UTC coverage: 70.436% (-0.01%) from 70.446%

Build # 13836648005

Build Type

push

github

Committed by

web-flow

Commit Message

New Transform type: Homography (#11949)

Add new transform type, Homography.
Add functions to compute homography from a list of GCPs.
Add functions to serialize and deserialize a homography
Automatically select homography transfrom when there are 4 or 5 GCPs present.

Fixes #11940

Run Details

231 of 274 new or added lines in 2 files covered. (84.31%)

16257 existing lines in 42 files now uncovered.

553736 of 786159 relevant lines covered (70.44%)

221595.72 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

88.64

/third_party/LercLib/Huffman.cpp

/*
Copyright 2015 Esri

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.

A local copy of the license and additional notices are located with the
source distribution at:

http://github.com/Esri/lerc/

Contributors:  Thomas Maurer
*/

#include <algorithm>
#include <queue>
#include "Defines.h"
#include "Huffman.h"
#include "BitStuffer2.h"

using namespace std;
USING_NAMESPACE_LERC

// -------------------------------------------------------------------------- ;

bool Huffman::ComputeCodes(const vector<int>& histo)
{
  if (histo.empty() || histo.size() >= m_maxHistoSize)
    return false;

  priority_queue<Node, vector<Node>, less<Node> > pq;

  int numNodes = 0;

  int size = (int)histo.size();
  for (int i = 0; i < size; i++)    // add all leaf nodes
    if (histo[i] > 0)
      pq.push(Node((short)i, histo[i]));

  if (pq.size() < 2)    // histo has only 0 or 1 bin that is not empty; quit Huffman and give it to Lerc
    return false;

  while (pq.size() > 1)    // build the Huffman tree
  {
    Node* child0 = new Node(pq.top());
    numNodes++;
    pq.pop();
    Node* child1 = new Node(pq.top());
    numNodes++;
    pq.pop();
    pq.push(Node(child0, child1));
  }

  m_codeTable.resize(size);
  std::fill(m_codeTable.begin(), m_codeTable.end(),
    std::pair<unsigned short, unsigned int>((short)0, 0));

  if (!pq.top().TreeToLUT(0, 0, m_codeTable))    // fill the LUT
    return false;

  //pq.top().FreeTree(numNodes);    // Linux compiler complains
  Node nodeNonConst = pq.top();
  nodeNonConst.FreeTree(numNodes);    // free all the nodes

  if (numNodes != 0)    // check the ref count
    return false;

  if (!ConvertCodesToCanonical())
    return false;

  return true;
}

// -------------------------------------------------------------------------- ;

bool Huffman::ComputeCompressedSize(const std::vector<int>& histo, int& numBytes, double& avgBpp) const
{
  if (histo.empty() || histo.size() >= m_maxHistoSize)
    return false;

  numBytes = 0;
  if (!ComputeNumBytesCodeTable(numBytes))    // header and code table
    return false;

  int numBits = 0, numElem = 0;
  int size = (int)histo.size();
  for (int i = 0; i < size; i++)
    if (histo[i] > 0)
    {
      numBits += histo[i] * m_codeTable[i].first;
      numElem += histo[i];
    }

  if (numElem == 0)
    return false;

  int numUInts = ((((numBits + 7) >> 3) + 3) >> 2) + 1;    // add one more as the decode LUT can read ahead
  numBytes += 4 * numUInts;    // data huffman coded
  avgBpp = 8 * numBytes / (double)numElem;

  return true;
}

// -------------------------------------------------------------------------- ;

bool Huffman::SetCodes(const vector<pair<unsigned short, unsigned int> >& codeTable)
{
  if (codeTable.empty() || codeTable.size() >= m_maxHistoSize)
    return false;

  m_codeTable = codeTable;
  return true;
}

// -------------------------------------------------------------------------- ;

bool Huffman::WriteCodeTable(Byte** ppByte, int lerc2Version) const
{
  if (!ppByte)
    return false;

  int i0, i1, maxLen;
  if (!GetRange(i0, i1, maxLen))
    return false;

  int size = (int)m_codeTable.size();
  vector<unsigned int> dataVec(i1 - i0, 0);

  for (int i = i0; i < i1; i++)
  {
    int k = GetIndexWrapAround(i, size);
    dataVec[i - i0] = m_codeTable[k].first;
  }

  // header
  vector<int> intVec;
  intVec.push_back(4);    // huffman version; 4 guarantees canonical codes
  intVec.push_back(size);
  intVec.push_back(i0);   // code range
  intVec.push_back(i1);

  Byte* ptr = *ppByte;

  size_t len = intVec.size() * sizeof(int);
  memcpy(ptr, &intVec[0], len);
  ptr += len;

  BitStuffer2 bitStuffer2;
  if (!bitStuffer2.EncodeSimple(&ptr, dataVec, lerc2Version))    // code lengths, bit stuffed
    return false;

  if (!BitStuffCodes(&ptr, i0, i1))    // variable length codes, bit stuffed
    return false;

  *ppByte = ptr;
  return true;
}

// -------------------------------------------------------------------------- ;

bool Huffman::ReadCodeTable(const Byte** ppByte, size_t& nBytesRemainingInOut, int lerc2Version)
{
  if (!ppByte || !(*ppByte))
    return false;

  const Byte* ptr = *ppByte;
  size_t nBytesRemaining = nBytesRemainingInOut;

  vector<int> intVec(4, 0);
  size_t len = intVec.size() * sizeof(int);

  if (nBytesRemaining < len)
    return false;

  memcpy(&intVec[0], ptr, len);
  ptr += len;
  nBytesRemaining -= len;

  int version = intVec[0];

  if (version < 2)    // allow forward compatibility; for updates that break old decoders increase Lerc2 version number;
    return false;

  const int size = intVec[1];
  const int i0 = intVec[2];
  const int i1 = intVec[3];

  if (i0 >= i1 || i0 < 0 || size < 0 || size > (int)m_maxHistoSize)
    return false;

  if (GetIndexWrapAround(i0, size) >= size || GetIndexWrapAround(i1 - 1, size) >= size)
    return false;

  try
  {
    vector<unsigned int> dataVec(i1 - i0, 0);
    BitStuffer2 bitStuffer2;
    if (!bitStuffer2.Decode(&ptr, nBytesRemaining, dataVec, dataVec.size(), lerc2Version))    // unstuff the code lengths
      return false;

    if (dataVec.size() != static_cast<size_t>(i1 - i0))
      return false;

    m_codeTable.resize(size);
    std::fill(m_codeTable.begin(), m_codeTable.end(),
      std::pair<unsigned short, unsigned int>((short)0, 0));

    for (int i = i0; i < i1; i++)
    {
      int k = GetIndexWrapAround(i, size);
      m_codeTable[k].first = (unsigned short)dataVec[i - i0];
    }

    if (!BitUnStuffCodes(&ptr, nBytesRemaining, i0, i1))    // unstuff the codes
      return false;

    *ppByte = ptr;
    nBytesRemainingInOut = nBytesRemaining;
    return true;
  }
  catch (std::exception&)
  {
    return false;
  }
}

// -------------------------------------------------------------------------- ;

bool Huffman::BuildTreeFromCodes(int& numBitsLUT)
{
  int i0 = 0, i1 = 0, maxLen = 0;
  if (!GetRange(i0, i1, maxLen))
    return false;

  // build decode LUT using max of 12 bits
  int size = (int)m_codeTable.size();
  int minNumZeroBits = 32;

  bool bNeedTree = maxLen > m_maxNumBitsLUT;
  numBitsLUT = min(maxLen, m_maxNumBitsLUT);

  int sizeLUT = 1 << numBitsLUT;

  m_decodeLUT.clear();
  m_decodeLUT.assign((size_t)sizeLUT, pair<short, short>((short)-1, (short)-1));

  for (int i = i0; i < i1; i++)
  {
    int k = GetIndexWrapAround(i, size);
    int len = m_codeTable[k].first;

    if (len == 0)
      continue;

    unsigned int code = m_codeTable[k].second;

    if (len <= numBitsLUT)
    {
      code <<= (numBitsLUT - len);
      unsigned int numEntries = 1 << (numBitsLUT - len);

      for (unsigned int j = 0; j < numEntries; j++)
      {
        auto& entry = m_decodeLUT[code | j];
        entry.first = (short)len;    // add the duplicates
        entry.second = (short)k;    // add the duplicates
      }
    }
    else    // for the codes too long for the LUT, count how many leading bits are 0
    {
      int shift = 1;
      while (code >>= 1) shift++;    // large canonical codes start with zero's
      minNumZeroBits = min(minNumZeroBits, len - shift);
    }
  }

  m_numBitsToSkipInTree = bNeedTree? minNumZeroBits : 0;

  if (!bNeedTree)    // decode LUT covers it all, no tree needed
    return true;

  //m_numBitsToSkipInTree = 0;    // to disable skipping the 0 bits

  ClearTree();  // if there

  Node emptyNode((short)-1, 0);
  m_root = new Node(emptyNode);

  for (int i = i0; i < i1; i++)
  {
    int k = GetIndexWrapAround(i, size);
    int len = m_codeTable[k].first;

    if (len > 0 && len > numBitsLUT)    // add only codes not in the decode LUT
    {
      unsigned int code = m_codeTable[k].second;
      Node* node = m_root;
      int j = len - m_numBitsToSkipInTree;    // reduce len by number of leading 0 bits from above

      while (--j >= 0)    // go over the bits
      {
        if (code & (1 << j))
        {
          if (!node->child1)
            node->child1 = new Node(emptyNode);

          node = node->child1;
        }
        else
        {
          if (!node->child0)
            node->child0 = new Node(emptyNode);

          node = node->child0;
        }

        if (j == 0)    // last bit, leaf node
          node->value = (short)k;    // set the value
      }
    }
  }

  return true;
}

// -------------------------------------------------------------------------- ;

void Huffman::Clear()
{
  m_codeTable.clear();
  m_decodeLUT.clear();
  ClearTree();
}

// -------------------------------------------------------------------------- ;

void Huffman::ClearTree()
{
  if (m_root)
  {
    int n = 0;
    m_root->FreeTree(n);
    delete m_root;
    m_root = nullptr;
  }
}

// -------------------------------------------------------------------------- ;
// -------------------------------------------------------------------------- ;

bool Huffman::ComputeNumBytesCodeTable(int& numBytes) const
{
  int i0, i1, maxLen;
  if (!GetRange(i0, i1, maxLen))
    return false;

  int size = (int)m_codeTable.size();
  int sum = 0;
  for (int i = i0; i < i1; i++)
  {
    int k = GetIndexWrapAround(i, size);
    sum += m_codeTable[k].first;
  }

  numBytes = 4 * sizeof(int);    // version, size, first bin, (last + 1) bin

  BitStuffer2 bitStuffer2;
  numBytes += bitStuffer2.ComputeNumBytesNeededSimple((unsigned int)(i1 - i0), (unsigned int)maxLen);    // code lengths
  int numUInts = (((sum + 7) >> 3) + 3) >> 2;
  numBytes += 4 * numUInts;    // byte array with the codes bit stuffed

  return true;
}

// -------------------------------------------------------------------------- ;

bool Huffman::GetRange(int& i0, int& i1, int& maxCodeLength) const
{
  if (m_codeTable.empty() || m_codeTable.size() >= m_maxHistoSize)
    return false;

  // first, check for peak somewhere in the middle with 0 stretches left and right
  int size = (int)m_codeTable.size();
  {
    int i = 0;
    while (i < size && m_codeTable[i].first == 0) i++;
    i0 = i;
    i = size - 1;
    while (i >= 0 && m_codeTable[i].first == 0) i--;
    i1 = i + 1;    // exclusive
  }

  if (i1 <= i0)
    return false;

  // second, cover the common case that the peak is close to 0
  pair<int, int> segm(0, 0);
  int j = 0;
  while (j < size)    // find the largest stretch of 0's, if any
  {
    while (j < size && m_codeTable[j].first > 0) j++;
    int k0 = j;
    while (j < size && m_codeTable[j].first == 0) j++;
    int k1 = j;

    if (k1 - k0 > segm.second)
      segm = pair<int, int>(k0, k1 - k0);
  }

  if (size - segm.second < i1 - i0)
  {
    i0 = segm.first + segm.second;
    i1 = segm.first + size;    // do wrap around
  }

  if (i1 <= i0)
    return false;

  int maxLen = 0;
  for (int i = i0; i < i1; i++)
  {
    int k = GetIndexWrapAround(i, size);
    int len = m_codeTable[k].first;
    maxLen = max(maxLen, len);
  }

  if (maxLen <= 0 || maxLen > 32)
    return false;

  maxCodeLength = maxLen;
  return true;
}

// -------------------------------------------------------------------------- ;

bool Huffman::BitStuffCodes(Byte** ppByte, int i0, int i1) const
{
  if (!ppByte)
    return false;

  unsigned int* arr = (unsigned int*)(*ppByte);
  unsigned int* dstPtr = arr;
  int size = (int)m_codeTable.size();
  int bitPos = 0;

  for (int i = i0; i < i1; i++)
  {
    int k = GetIndexWrapAround(i, size);
    int len = m_codeTable[k].first;
    if (len > 0)
    {
      unsigned int val = m_codeTable[k].second;
      if (32 - bitPos >= len)
      {
        if (bitPos == 0)
          *dstPtr = 0;

        *dstPtr |= val << (32 - bitPos - len);
        bitPos += len;
        if (bitPos == 32)
        {
          bitPos = 0;
          dstPtr++;
        }
      }
      else
      {
        bitPos += len - 32;
        *dstPtr++ |= val >> bitPos;    // bitPos > 0
        *dstPtr = val << (32 - bitPos);
      }
    }
  }

  size_t numUInts = dstPtr - arr + (bitPos > 0 ? 1 : 0);
  *ppByte += numUInts * sizeof(unsigned int);
  return true;
}

// -------------------------------------------------------------------------- ;

bool Huffman::BitUnStuffCodes(const Byte** ppByte, size_t& nBytesRemainingInOut, int i0, int i1)
{
  if (!ppByte || !(*ppByte))
    return false;

  size_t nBytesRemaining = nBytesRemainingInOut;

  const unsigned int* arr = (const unsigned int*)(*ppByte);
  const unsigned int* srcPtr = arr;
  const size_t sizeUInt = sizeof(*srcPtr);

  int size = (int)m_codeTable.size();
  int bitPos = 0;

  for (int i = i0; i < i1; i++)
  {
    int k = GetIndexWrapAround(i, size);
    int len = m_codeTable[k].first;
    if (len > 0)
    {
      if (nBytesRemaining < sizeUInt || len > 32)
        return false;

      m_codeTable[k].second = ((*srcPtr) << bitPos) >> (32 - len);

      if (32 - bitPos >= len)
      {
        bitPos += len;
        if (bitPos == 32)
        {
          bitPos = 0;
          srcPtr++;
          nBytesRemaining -= sizeUInt;
        }
      }
      else
      {
        bitPos += len - 32;
        srcPtr++;
        nBytesRemaining -= sizeUInt;

        if (nBytesRemaining < sizeUInt)
          return false;

        m_codeTable[k].second |= (*srcPtr) >> (32 - bitPos);    // bitPos > 0
      }
    }
  }

  size_t numUInts = srcPtr - arr + (bitPos > 0 ? 1 : 0);
  size_t len = numUInts * sizeUInt;

  if (nBytesRemainingInOut < len)
    return false;

  *ppByte += len;
  nBytesRemainingInOut -= len;

  if (nBytesRemaining != nBytesRemainingInOut && nBytesRemaining != nBytesRemainingInOut + sizeUInt)    // the real check
    return false;

  return true;
}

// -------------------------------------------------------------------------- ;

//struct MyLargerThanOp
//{
//  inline bool operator() (const pair<int, unsigned int>& p0,
//                          const pair<int, unsigned int>& p1)  { return p0.first > p1.first; }
//};

// -------------------------------------------------------------------------- ;

bool Huffman::ConvertCodesToCanonical()
{
  // from the non canonical code book, create an array to be sorted in descending order:
  //   codeLength * tableSize - index

  unsigned int tableSize = (unsigned int)m_codeTable.size();
  if (tableSize == 0)
    return true;
  vector<pair<int, unsigned int> > sortVec(tableSize, pair<int, unsigned int>(0, 0));
  //memset(&sortVec[0], 0, tableSize * sizeof(pair<int, unsigned int>));

  for (unsigned int i = 0; i < tableSize; i++)
    if (m_codeTable[i].first > 0)
      sortVec[i] = pair<int, unsigned int>(m_codeTable[i].first * tableSize - i, i);

  // sort descending
  //std::sort(sortVec.begin(), sortVec.end(), MyLargerThanOp());

  std::sort(sortVec.begin(), sortVec.end(),
    [](const pair<int, unsigned int>& p0,
       const pair<int, unsigned int>& p1) { return p0.first > p1.first; });

  // create canonical codes and assign to orig code table
  unsigned int index = sortVec[0].second;
  unsigned short codeLen = m_codeTable[index].first;    // max code length for this table
  unsigned int i = 0, codeCanonical = 0;

  while (i < tableSize && sortVec[i].first > 0)
  {
    index = sortVec[i++].second;
    short delta = codeLen - m_codeTable[index].first;  // difference of 2 consecutive code lengths, >= 0 as sorted
    codeCanonical >>= delta;
    codeLen -= delta;
    m_codeTable[index].second = codeCanonical++;
  }

  return true;
}

// -------------------------------------------------------------------------- ;

1	/*
2	Copyright 2015 Esri
3
4	Licensed under the Apache License, Version 2.0 (the "License");
5	you may not use this file except in compliance with the License.
6	You may obtain a copy of the License at
7
8	http://www.apache.org/licenses/LICENSE-2.0
9
10	Unless required by applicable law or agreed to in writing, software
11	distributed under the License is distributed on an "AS IS" BASIS,
12	WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13	See the License for the specific language governing permissions and
14	limitations under the License.
15
16	A local copy of the license and additional notices are located with the
17	source distribution at:
18
19	http://github.com/Esri/lerc/
20
21	Contributors: Thomas Maurer
22	*/
23
24	#include <algorithm>
25	#include <queue>
26	#include "Defines.h"
27	#include "Huffman.h"
28	#include "BitStuffer2.h"
29
30	using namespace std;
31	USING_NAMESPACE_LERC
32
33	// -------------------------------------------------------------------------- ;
34
35	bool Huffman::ComputeCodes(const vector<int>& histo)	3,531✔
36	{
37	if (histo.empty() \|\| histo.size() >= m_maxHistoSize)	3,531✔
38	return false;	×
39
40	priority_queue<Node, vector<Node>, less<Node> > pq;	7,062✔
41
42	int numNodes = 0;	3,531✔
43
44	int size = (int)histo.size();	3,531✔
45	for (int i = 0; i < size; i++) // add all leaf nodes	907,443✔
46	if (histo[i] > 0)	903,912✔
47	pq.push(Node((short)i, histo[i]));	124,193✔
48
49	if (pq.size() < 2) // histo has only 0 or 1 bin that is not empty; quit Huffman and give it to Lerc	3,531✔
50	return false;	×
51
52	while (pq.size() > 1) // build the Huffman tree	124,197✔
53	{
54	Node* child0 = new Node(pq.top());	120,666✔
55	numNodes++;	120,666✔
56	pq.pop();	120,666✔
57	Node* child1 = new Node(pq.top());	120,665✔
58	numNodes++;	120,666✔
59	pq.pop();	120,666✔
60	pq.push(Node(child0, child1));	120,666✔
61	}
62
63	m_codeTable.resize(size);	3,531✔
64	std::fill(m_codeTable.begin(), m_codeTable.end(),	3,531✔
65	std::pair<unsigned short, unsigned int>((short)0, 0));	3,531✔
66
67	if (!pq.top().TreeToLUT(0, 0, m_codeTable)) // fill the LUT	3,531✔
68	return false;	×
69
70	//pq.top().FreeTree(numNodes); // Linux compiler complains
71	Node nodeNonConst = pq.top();	3,531✔
72	nodeNonConst.FreeTree(numNodes); // free all the nodes	3,531✔
73
74	if (numNodes != 0) // check the ref count	3,531✔
75	return false;	×
76
77	if (!ConvertCodesToCanonical())	3,531✔
78	return false;	×
79
80	return true;	3,531✔
81	}
82
83	// -------------------------------------------------------------------------- ;
84
85	bool Huffman::ComputeCompressedSize(const std::vector<int>& histo, int& numBytes, double& avgBpp) const	3,531✔
86	{
87	if (histo.empty() \|\| histo.size() >= m_maxHistoSize)	3,531✔
88	return false;	×
89
90	numBytes = 0;	3,531✔
91	if (!ComputeNumBytesCodeTable(numBytes)) // header and code table	3,531✔
92	return false;	×
93
94	int numBits = 0, numElem = 0;	3,531✔
95	int size = (int)histo.size();	3,531✔
96	for (int i = 0; i < size; i++)	907,399✔
97	if (histo[i] > 0)	903,868✔
98	{
99	numBits += histo[i] * m_codeTable[i].first;	124,169✔
100	numElem += histo[i];	124,169✔
101	}
102
103	if (numElem == 0)	3,531✔
104	return false;	×
105
106	int numUInts = ((((numBits + 7) >> 3) + 3) >> 2) + 1; // add one more as the decode LUT can read ahead	3,531✔
107	numBytes += 4 * numUInts; // data huffman coded	3,531✔
108	avgBpp = 8 * numBytes / (double)numElem;	3,531✔
109
110	return true;	3,531✔
111	}
112
113	// -------------------------------------------------------------------------- ;
114
115	bool Huffman::SetCodes(const vector<pair<unsigned short, unsigned int> >& codeTable)	640✔
116	{
117	if (codeTable.empty() \|\| codeTable.size() >= m_maxHistoSize)	640✔
118	return false;	×
119
120	m_codeTable = codeTable;	640✔
121	return true;	640✔
122	}
123
124	// -------------------------------------------------------------------------- ;
125
126	bool Huffman::WriteCodeTable(Byte** ppByte, int lerc2Version) const	640✔
127	{
128	if (!ppByte)	640✔
129	return false;	×
130
131	int i0, i1, maxLen;
132	if (!GetRange(i0, i1, maxLen))	640✔
133	return false;	×
134
135	int size = (int)m_codeTable.size();	640✔
136	vector<unsigned int> dataVec(i1 - i0, 0);	1,280✔
137
138	for (int i = i0; i < i1; i++)	96,762✔
139	{
140	int k = GetIndexWrapAround(i, size);	96,122✔
141	dataVec[i - i0] = m_codeTable[k].first;	96,122✔
142	}
143
144	// header
145	vector<int> intVec;	1,280✔
146	intVec.push_back(4); // huffman version; 4 guarantees canonical codes	640✔
147	intVec.push_back(size);	640✔
148	intVec.push_back(i0); // code range	640✔
149	intVec.push_back(i1);	640✔
150
151	Byte* ptr = *ppByte;	640✔
152
153	size_t len = intVec.size() * sizeof(int);	640✔
154	memcpy(ptr, &intVec[0], len);	640✔
155	ptr += len;	640✔
156
157	BitStuffer2 bitStuffer2;	1,280✔
158	if (!bitStuffer2.EncodeSimple(&ptr, dataVec, lerc2Version)) // code lengths, bit stuffed	640✔
159	return false;	×
160
161	if (!BitStuffCodes(&ptr, i0, i1)) // variable length codes, bit stuffed	640✔
162	return false;	×
163
164	*ppByte = ptr;	640✔
165	return true;	640✔
166	}
167
168	// -------------------------------------------------------------------------- ;
169
170	bool Huffman::ReadCodeTable(const Byte** ppByte, size_t& nBytesRemainingInOut, int lerc2Version)	515✔
171	{
172	if (!ppByte \|\| !(*ppByte))	515✔
UNCOV 173	return false;	×
174
175	const Byte* ptr = *ppByte;	515✔
176	size_t nBytesRemaining = nBytesRemainingInOut;	515✔
177
178	vector<int> intVec(4, 0);	1,030✔
179	size_t len = intVec.size() * sizeof(int);	515✔
180
181	if (nBytesRemaining < len)	515✔
182	return false;	×
183
184	memcpy(&intVec[0], ptr, len);	515✔
185	ptr += len;	515✔
186	nBytesRemaining -= len;	515✔
187
188	int version = intVec[0];	515✔
189
190	if (version < 2) // allow forward compatibility; for updates that break old decoders increase Lerc2 version number;	515✔
191	return false;	×
192
193	const int size = intVec[1];	515✔
194	const int i0 = intVec[2];	515✔
195	const int i1 = intVec[3];	515✔
196
197	if (i0 >= i1 \|\| i0 < 0 \|\| size < 0 \|\| size > (int)m_maxHistoSize)	515✔
198	return false;	×
199
200	if (GetIndexWrapAround(i0, size) >= size \|\| GetIndexWrapAround(i1 - 1, size) >= size)	515✔
201	return false;	×
202
203	try
204	{
205	vector<unsigned int> dataVec(i1 - i0, 0);	1,030✔
206	BitStuffer2 bitStuffer2;	1,030✔
207	if (!bitStuffer2.Decode(&ptr, nBytesRemaining, dataVec, dataVec.size(), lerc2Version)) // unstuff the code lengths	515✔
208	return false;	×
209
210	if (dataVec.size() != static_cast<size_t>(i1 - i0))	515✔
211	return false;	×
212
213	m_codeTable.resize(size);	515✔
214	std::fill(m_codeTable.begin(), m_codeTable.end(),	515✔
215	std::pair<unsigned short, unsigned int>((short)0, 0));	515✔
216
217	for (int i = i0; i < i1; i++)	96,587✔
218	{
219	int k = GetIndexWrapAround(i, size);	96,072✔
220	m_codeTable[k].first = (unsigned short)dataVec[i - i0];	96,062✔
221	}
222
223	if (!BitUnStuffCodes(&ptr, nBytesRemaining, i0, i1)) // unstuff the codes	515✔
224	return false;	×
225
226	*ppByte = ptr;	515✔
227	nBytesRemainingInOut = nBytesRemaining;	515✔
228	return true;	515✔
229	}
230	catch (std::exception&)	×
231	{
232	return false;	×
233	}
234	}
235
236	// -------------------------------------------------------------------------- ;
237
238	bool Huffman::BuildTreeFromCodes(int& numBitsLUT)	515✔
239	{
240	int i0 = 0, i1 = 0, maxLen = 0;	515✔
241	if (!GetRange(i0, i1, maxLen))	515✔
242	return false;	×
243
244	// build decode LUT using max of 12 bits
245	int size = (int)m_codeTable.size();	515✔
246	int minNumZeroBits = 32;	515✔
247
248	bool bNeedTree = maxLen > m_maxNumBitsLUT;	515✔
249	numBitsLUT = min(maxLen, m_maxNumBitsLUT);	515✔
250
251	int sizeLUT = 1 << numBitsLUT;	515✔
252
253	m_decodeLUT.clear();	515✔
254	m_decodeLUT.assign((size_t)sizeLUT, pair<short, short>((short)-1, (short)-1));	515✔
255
256	for (int i = i0; i < i1; i++)	96,715✔
257	{
258	int k = GetIndexWrapAround(i, size);	96,200✔
259	int len = m_codeTable[k].first;	96,199✔
260
261	if (len == 0)	96,200✔
262	continue;	64,435✔
263
264	unsigned int code = m_codeTable[k].second;	31,765✔
265
266	if (len <= numBitsLUT)	31,766✔
267	{
268	code <<= (numBitsLUT - len);	30,607✔
269	unsigned int numEntries = 1 << (numBitsLUT - len);	30,607✔
270
271	for (unsigned int j = 0; j < numEntries; j++)	684,573✔
272	{
273	auto& entry = m_decodeLUT[code \| j];	654,064✔
274	entry.first = (short)len; // add the duplicates	653,966✔
275	entry.second = (short)k; // add the duplicates	653,966✔
276	}
277	}
278	else // for the codes too long for the LUT, count how many leading bits are 0
279	{
280	int shift = 1;	1,159✔
281	while (code >>= 1) shift++; // large canonical codes start with zero's	4,833✔
282	minNumZeroBits = min(minNumZeroBits, len - shift);	1,159✔
283	}
284	}
285
286	m_numBitsToSkipInTree = bNeedTree? minNumZeroBits : 0;	515✔
287
288	if (!bNeedTree) // decode LUT covers it all, no tree needed	515✔
289	return true;	474✔
290
291	//m_numBitsToSkipInTree = 0; // to disable skipping the 0 bits
292
293	ClearTree(); // if there	41✔
294
295	Node emptyNode((short)-1, 0);	41✔
296	m_root = new Node(emptyNode);	41✔
297
298	for (int i = i0; i < i1; i++)	10,183✔
299	{
300	int k = GetIndexWrapAround(i, size);	10,142✔
301	int len = m_codeTable[k].first;	10,142✔
302
303	if (len > 0 && len > numBitsLUT) // add only codes not in the decode LUT	10,142✔
304	{
305	unsigned int code = m_codeTable[k].second;	1,159✔
306	Node* node = m_root;	1,159✔
307	int j = len - m_numBitsToSkipInTree; // reduce len by number of leading 0 bits from above	1,159✔
308
309	while (--j >= 0) // go over the bits	7,527✔
310	{
311	if (code & (1 << j))	6,368✔
312	{
313	if (!node->child1)	2,795✔
314	node->child1 = new Node(emptyNode);	1,118✔
315
316	node = node->child1;	2,795✔
317	}
318	else
319	{
320	if (!node->child0)	3,573✔
321	node->child0 = new Node(emptyNode);	1,168✔
322
323	node = node->child0;	3,573✔
324	}
325
326	if (j == 0) // last bit, leaf node	6,368✔
327	node->value = (short)k; // set the value	1,159✔
328	}
329	}
330	}
331
332	return true;	41✔
333	}
334
335	// -------------------------------------------------------------------------- ;
336
337	void Huffman::Clear()	7,809✔
338	{
339	m_codeTable.clear();	7,809✔
340	m_decodeLUT.clear();	7,809✔
341	ClearTree();	7,809✔
342	}	7,809✔
343
344	// -------------------------------------------------------------------------- ;
345
346	void Huffman::ClearTree()	7,850✔
347	{
348	if (m_root)	7,850✔
349	{
350	int n = 0;	41✔
351	m_root->FreeTree(n);	41✔
352	delete m_root;	41✔
353	m_root = nullptr;	41✔
354	}
355	}	7,850✔
356
357	// -------------------------------------------------------------------------- ;
358	// -------------------------------------------------------------------------- ;
359
360	bool Huffman::ComputeNumBytesCodeTable(int& numBytes) const	3,531✔
361	{
362	int i0, i1, maxLen;
363	if (!GetRange(i0, i1, maxLen))	3,531✔
364	return false;	×
365
366	int size = (int)m_codeTable.size();	3,531✔
367	int sum = 0;	3,531✔
368	for (int i = i0; i < i1; i++)	464,771✔
369	{
370	int k = GetIndexWrapAround(i, size);	461,240✔
371	sum += m_codeTable[k].first;	461,239✔
372	}
373
374	numBytes = 4 * sizeof(int); // version, size, first bin, (last + 1) bin	3,531✔
375
376	BitStuffer2 bitStuffer2;	3,531✔
377	numBytes += bitStuffer2.ComputeNumBytesNeededSimple((unsigned int)(i1 - i0), (unsigned int)maxLen); // code lengths	3,531✔
378	int numUInts = (((sum + 7) >> 3) + 3) >> 2;	3,531✔
379	numBytes += 4 * numUInts; // byte array with the codes bit stuffed	3,531✔
380
381	return true;	3,531✔
382	}
383
384	// -------------------------------------------------------------------------- ;
385
386	bool Huffman::GetRange(int& i0, int& i1, int& maxCodeLength) const	4,686✔
387	{
388	if (m_codeTable.empty() \|\| m_codeTable.size() >= m_maxHistoSize)	4,686✔
389	return false;	×
390
391	// first, check for peak somewhere in the middle with 0 stretches left and right
392	int size = (int)m_codeTable.size();	4,686✔
393	{
394	int i = 0;	4,686✔
395	while (i < size && m_codeTable[i].first == 0) i++;	8,093✔
396	i0 = i;	4,686✔
397	i = size - 1;	4,686✔
398	while (i >= 0 && m_codeTable[i].first == 0) i--;	30,637✔
399	i1 = i + 1; // exclusive	4,686✔
400	}
401
402	if (i1 <= i0)	4,686✔
403	return false;	×
404
405	// second, cover the common case that the peak is close to 0
406	pair<int, int> segm(0, 0);	4,686✔
407	int j = 0;	4,686✔
408	while (j < size) // find the largest stretch of 0's, if any	85,356✔
409	{
410	while (j < size && m_codeTable[j].first > 0) j++;	264,333✔
411	int k0 = j;	80,664✔
412	while (j < size && m_codeTable[j].first == 0) j++;	1,096,490✔
413	int k1 = j;	80,662✔
414
415	if (k1 - k0 > segm.second)	80,662✔
416	segm = pair<int, int>(k0, k1 - k0);	17,599✔
417	}
418
419	if (size - segm.second < i1 - i0)	4,686✔
420	{
421	i0 = segm.first + segm.second;	4,312✔
422	i1 = segm.first + size; // do wrap around	4,312✔
423	}
424
425	if (i1 <= i0)	4,686✔
426	return false;	×
427
428	int maxLen = 0;	4,686✔
429	for (int i = i0; i < i1; i++)	658,115✔
430	{
431	int k = GetIndexWrapAround(i, size);	653,429✔
432	int len = m_codeTable[k].first;	653,423✔
433	maxLen = max(maxLen, len);	653,429✔
434	}
435
436	if (maxLen <= 0 \|\| maxLen > 32)	4,686✔
437	return false;	×
438
439	maxCodeLength = maxLen;	4,686✔
440	return true;	4,686✔
441	}
442
443	// -------------------------------------------------------------------------- ;
444
445	bool Huffman::BitStuffCodes(Byte** ppByte, int i0, int i1) const	640✔
446	{
447	if (!ppByte)	640✔
448	return false;	×
449
450	unsigned int* arr = (unsigned int)(ppByte);	640✔
451	unsigned int* dstPtr = arr;	640✔
452	int size = (int)m_codeTable.size();	640✔
453	int bitPos = 0;	640✔
454
455	for (int i = i0; i < i1; i++)	96,762✔
456	{
457	int k = GetIndexWrapAround(i, size);	96,122✔
458	int len = m_codeTable[k].first;	96,122✔
459	if (len > 0)	96,122✔
460	{
461	unsigned int val = m_codeTable[k].second;	27,743✔
462	if (32 - bitPos >= len)	27,743✔
463	{
464	if (bitPos == 0)	22,449✔
465	*dstPtr = 0;	1,382✔
466
467	*dstPtr \|= val << (32 - bitPos - len);	22,449✔
468	bitPos += len;	22,449✔
469	if (bitPos == 32)	22,449✔
470	{
471	bitPos = 0;	760✔
472	dstPtr++;	760✔
473	}
474	}
475	else
476	{
477	bitPos += len - 32;	5,294✔
478	*dstPtr++ \|= val >> bitPos; // bitPos > 0	5,294✔
479	*dstPtr = val << (32 - bitPos);	5,294✔
480	}
481	}
482	}
483
484	size_t numUInts = dstPtr - arr + (bitPos > 0 ? 1 : 0);	640✔
485	ppByte += numUInts sizeof(unsigned int);	640✔
486	return true;	640✔
487	}
488
489	// -------------------------------------------------------------------------- ;
490
491	bool Huffman::BitUnStuffCodes(const Byte** ppByte, size_t& nBytesRemainingInOut, int i0, int i1)	515✔
492	{
493	if (!ppByte \|\| !(*ppByte))	515✔
494	return false;	×
495
496	size_t nBytesRemaining = nBytesRemainingInOut;	515✔
497
498	const unsigned int* arr = (const unsigned int)(ppByte);	515✔
499	const unsigned int* srcPtr = arr;	515✔
500	const size_t sizeUInt = sizeof(*srcPtr);	515✔
501
502	int size = (int)m_codeTable.size();	515✔
503	int bitPos = 0;	515✔
504
505	for (int i = i0; i < i1; i++)	96,623✔
506	{
507	int k = GetIndexWrapAround(i, size);	96,108✔
508	int len = m_codeTable[k].first;	96,107✔
509	if (len > 0)	96,101✔
510	{
511	if (nBytesRemaining < sizeUInt \|\| len > 32)	31,725✔
512	return false;	×
513
514	m_codeTable[k].second = ((*srcPtr) << bitPos) >> (32 - len);	31,725✔
515
516	if (32 - bitPos >= len)	31,732✔
517	{
518	bitPos += len;	24,988✔
519	if (bitPos == 32)	24,988✔
520	{
521	bitPos = 0;	870✔
522	srcPtr++;	870✔
523	nBytesRemaining -= sizeUInt;	870✔
524	}
525	}
526	else
527	{
528	bitPos += len - 32;	6,744✔
529	srcPtr++;	6,744✔
530	nBytesRemaining -= sizeUInt;	6,744✔
531
532	if (nBytesRemaining < sizeUInt)	6,744✔
533	return false;	×
534
535	m_codeTable[k].second \|= (*srcPtr) >> (32 - bitPos); // bitPos > 0	6,744✔
536	}
537	}
538	}
539
540	size_t numUInts = srcPtr - arr + (bitPos > 0 ? 1 : 0);	515✔
541	size_t len = numUInts * sizeUInt;	515✔
542
543	if (nBytesRemainingInOut < len)	515✔
544	return false;	×
545
546	*ppByte += len;	515✔
547	nBytesRemainingInOut -= len;	515✔
548
549	if (nBytesRemaining != nBytesRemainingInOut && nBytesRemaining != nBytesRemainingInOut + sizeUInt) // the real check	515✔
550	return false;	×
551
552	return true;	515✔
553	}
554
555	// -------------------------------------------------------------------------- ;
556
557	//struct MyLargerThanOp
558	//{
559	// inline bool operator() (const pair<int, unsigned int>& p0,
560	// const pair<int, unsigned int>& p1) { return p0.first > p1.first; }
561	//};
562
563	// -------------------------------------------------------------------------- ;
564
565	bool Huffman::ConvertCodesToCanonical()	3,531✔
566	{
567	// from the non canonical code book, create an array to be sorted in descending order:
568	// codeLength * tableSize - index
569
570	unsigned int tableSize = (unsigned int)m_codeTable.size();	3,531✔
571	if (tableSize == 0)	3,531✔
572	return true;	×
573	vector<pair<int, unsigned int> > sortVec(tableSize, pair<int, unsigned int>(0, 0));	3,531✔
574	//memset(&sortVec[0], 0, tableSize * sizeof(pair<int, unsigned int>));
575
576	for (unsigned int i = 0; i < tableSize; i++)	907,415✔
577	if (m_codeTable[i].first > 0)	903,884✔
578	sortVec[i] = pair<int, unsigned int>(m_codeTable[i].first * tableSize - i, i);	124,168✔
579
580	// sort descending
581	//std::sort(sortVec.begin(), sortVec.end(), MyLargerThanOp());
582
583	std::sort(sortVec.begin(), sortVec.end(),	3,531✔
584	[](const pair<int, unsigned int>& p0,	5,733,700✔
585	const pair<int, unsigned int>& p1) { return p0.first > p1.first; });	5,733,700✔
586
587	// create canonical codes and assign to orig code table
588	unsigned int index = sortVec[0].second;	3,531✔
589	unsigned short codeLen = m_codeTable[index].first; // max code length for this table	3,531✔
590	unsigned int i = 0, codeCanonical = 0;	3,531✔
591
592	while (i < tableSize && sortVec[i].first > 0)	127,693✔
593	{
594	index = sortVec[i++].second;	124,161✔
595	short delta = codeLen - m_codeTable[index].first; // difference of 2 consecutive code lengths, >= 0 as sorted	124,159✔
596	codeCanonical >>= delta;	124,158✔
597	codeLen -= delta;	124,158✔
598	m_codeTable[index].second = codeCanonical++;	124,158✔
599	}
600
601	return true;	3,536✔
602	}
603
604	// -------------------------------------------------------------------------- ;

OSGeo / gdal / 13836648005

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous