15899162844

Committed 26 Jun 2025 10:14AM UTC coverage: 71.088% (+0.004%) from 71.084%

Build # 15899162844

Build Type

Pull #12623

github

Committed by

web-flow

Commit Message

Merge c704a8392 into f5cb024d4

Pull Request Pull Request #12623: gdal raster overview add: add a --overview-src option

Run Details

209 of 244 new or added lines in 5 files covered. (85.66%)

96 existing lines in 44 files now uncovered.

574014 of 807474 relevant lines covered (71.09%)

250815.03 hits per line

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

88.38

/third_party/LercLib/BitStuffer2.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 <cassert>
#include "Defines.h"
#include "BitStuffer2.h"

using namespace std;
USING_NAMESPACE_LERC

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

// if you change Encode(...) / Decode(...), don't forget to update ComputeNumBytesNeeded(...)

bool BitStuffer2::EncodeSimple(Byte** ppByte, const vector<unsigned int>& dataVec, int lerc2Version) const
{
  if (!ppByte || dataVec.empty())
    return false;

  unsigned int maxElem = *max_element(dataVec.begin(), dataVec.end());
  int numBits = 0;
  while ((numBits < 32) && (maxElem >> numBits))
    numBits++;

  if (numBits >= 32)
    return false;

  Byte numBitsByte = (Byte)numBits;
  unsigned int numElements = (unsigned int)dataVec.size();
  unsigned int numUInts = (numElements * numBits + 31) / 32;

  // use the upper 2 bits to encode the type used for numElements: Byte, ushort, or uint
  int n = NumBytesUInt(numElements);
  int bits67 = (n == 4) ? 0 : 3 - n;
  numBitsByte |= bits67 << 6;

  // bit5 = 0 means simple mode

  **ppByte = numBitsByte;
  (*ppByte)++;

  if (!EncodeUInt(ppByte, numElements, n))
    return false;

  if (numUInts > 0)    // numBits can be 0, then we only write the header
  {
    if (lerc2Version >= 3)
      BitStuff(ppByte, dataVec, numBits);
    else
      BitStuff_Before_Lerc2v3(ppByte, dataVec, numBits);
  }

  return true;
}

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

bool BitStuffer2::EncodeLut(Byte** ppByte, const vector<pair<unsigned int, unsigned int> >& sortedDataVec, int lerc2Version) const
{
  if (!ppByte || sortedDataVec.empty())
    return false;

  if (sortedDataVec[0].first != 0)    // corresponds to min
    return false;

  // collect the different values for the lut
  unsigned int numElem = (unsigned int)sortedDataVec.size();
  unsigned int indexLut = 0;

  m_tmpLutVec.resize(0);    // omit the 0 throughout that corresponds to min
  m_tmpIndexVec.assign(numElem, 0);

  for (unsigned int i = 1; i < numElem; i++)
  {
    unsigned int prev = sortedDataVec[i - 1].first;
    m_tmpIndexVec[sortedDataVec[i - 1].second] = indexLut;

    if (sortedDataVec[i].first != prev)
    {
      m_tmpLutVec.push_back(sortedDataVec[i].first);
      indexLut++;
    }
  }
  m_tmpIndexVec[sortedDataVec[numElem - 1].second] = indexLut;    // don't forget the last one

  // write first 2 data elements same as simple, but bit5 set to 1
  unsigned int maxElem = m_tmpLutVec.back();
  int numBits = 0;
  while ((numBits < 32) && (maxElem >> numBits))
    numBits++;

  if (numBits >= 32)
    return false;

  Byte numBitsByte = (Byte)numBits;

  // use the upper 2 bits to encode the type used for numElem: byte, ushort, or uint
  int n = NumBytesUInt(numElem);
  int bits67 = (n == 4) ? 0 : 3 - n;
  numBitsByte |= bits67 << 6;

  numBitsByte |= (1 << 5);    // bit 5 = 1 means lut mode

  **ppByte = numBitsByte;
  (*ppByte)++;

  if (!EncodeUInt(ppByte, numElem, n))    // numElements = numIndexes to lut
    return false;

  unsigned int nLut = (unsigned int)m_tmpLutVec.size();
  if (nLut < 1 || nLut >= 255)
    return false;

  **ppByte = (Byte)nLut + 1;    // size of lut, incl the 0
  (*ppByte)++;

  if (lerc2Version >= 3)
    BitStuff(ppByte, m_tmpLutVec, numBits);    // lut
  else
    BitStuff_Before_Lerc2v3(ppByte, m_tmpLutVec, numBits);

  int nBitsLut = 0;
  while (nLut >> nBitsLut)    // indexes are in [0 .. nLut]
    nBitsLut++;

  if (lerc2Version >= 3)
    BitStuff(ppByte, m_tmpIndexVec, nBitsLut);    // indexes
  else
    BitStuff_Before_Lerc2v3(ppByte, m_tmpIndexVec, nBitsLut);

  return true;
}

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

// if you change Encode(...) / Decode(...), don't forget to update ComputeNumBytesNeeded(...)

bool BitStuffer2::Decode(const Byte** ppByte, size_t& nBytesRemaining, vector<unsigned int>& dataVec, size_t maxElementCount, int lerc2Version) const
{
  if (!ppByte || nBytesRemaining < 1)
    return false;

  Byte numBitsByte = **ppByte;
  (*ppByte)++;
  nBytesRemaining--;

  int bits67 = numBitsByte >> 6;
  int nb = (bits67 == 0) ? 4 : 3 - bits67;

  bool doLut = (numBitsByte & (1 << 5)) ? true : false;    // bit 5
  numBitsByte &= 31;    // bits 0-4;
  int numBits = numBitsByte;

  unsigned int numElements = 0;
  if (!DecodeUInt(ppByte, nBytesRemaining, numElements, nb))
    return false;
  if (numElements > maxElementCount)
    return false;

  if (!doLut)
  {
    if (numBits > 0)    // numBits can be 0
    {
      if (lerc2Version >= 3)
      {
        if (!BitUnStuff(ppByte, nBytesRemaining, dataVec, numElements, numBits))
          return false;
      }
      else
      {
        if (!BitUnStuff_Before_Lerc2v3(ppByte, nBytesRemaining, dataVec, numElements, numBits))
          return false;
      }
    }
  }
  else
  {
    if (numBits == 0)  // fail gracefully in case of corrupted blob for old version <= 2 which had no checksum
      return false;
    if (nBytesRemaining < 1)
      return false;

    Byte nLutByte = **ppByte;
    (*ppByte)++;
    nBytesRemaining--;

    int nLut = nLutByte - 1;

    // unstuff lut w/o the 0
    if (lerc2Version >= 3)
    {
      if (!BitUnStuff(ppByte, nBytesRemaining, m_tmpLutVec, nLut, numBits))
        return false;
    }
    else
    {
      if (!BitUnStuff_Before_Lerc2v3(ppByte, nBytesRemaining, m_tmpLutVec, nLut, numBits))
        return false;
    }

    int nBitsLut = 0;
    while (nLut >> nBitsLut)
      nBitsLut++;
    if (nBitsLut == 0)
      return false;

    if (lerc2Version >= 3)
    {
      // unstuff indexes
      if (!BitUnStuff(ppByte, nBytesRemaining, dataVec, numElements, nBitsLut))
        return false;

      // replace indexes by values
#if defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wnull-dereference"
#endif
      m_tmpLutVec.insert(m_tmpLutVec.begin(), 0);    // put back in the 0
#if defined(__GNUC__)
#pragma GCC diagnostic pop
#endif
      for (unsigned int i = 0; i < numElements; i++)
      {
#ifdef GDAL_COMPILATION
        if (dataVec[i] >= m_tmpLutVec.size())
          return false;
#endif
        dataVec[i] = m_tmpLutVec[dataVec[i]];
      }
    }
    else
    {
      // unstuff indexes
      if (!BitUnStuff_Before_Lerc2v3(ppByte, nBytesRemaining, dataVec, numElements, nBitsLut))
        return false;

      // replace indexes by values
#if defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wnull-dereference"
#endif
      m_tmpLutVec.insert(m_tmpLutVec.begin(), 0);    // put back in the 0
#if defined(__GNUC__)
#pragma GCC diagnostic pop
#endif
      for (unsigned int i = 0; i < numElements; i++)
      {
        if (dataVec[i] >= m_tmpLutVec.size())
          return false;

        dataVec[i] = m_tmpLutVec[dataVec[i]];
      }
    }
  }

  return true;
}

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

unsigned int BitStuffer2::ComputeNumBytesNeededLut(const vector<pair<unsigned int, unsigned int> >& sortedDataVec, bool& doLut)
{
  unsigned int maxElem = sortedDataVec.back().first;
  unsigned int numElem = (unsigned int)sortedDataVec.size();

  int numBits = 0;
  while ((numBits < 32) && (maxElem >> numBits))
    numBits++;
  unsigned int numBytes = 1 + NumBytesUInt(numElem) + ((numElem * numBits + 7) >> 3);

  // go through and count how often the value changes
  int nLut = 0;
  for (unsigned int i = 1; i < numElem; i++)
    if (sortedDataVec[i].first != sortedDataVec[i - 1].first)
      nLut++;

  int nBitsLut = 0;
  while (nLut >> nBitsLut)
    nBitsLut++;

  unsigned int numBitsTotalLut = nLut * numBits;    // num bits w/o the 0
  unsigned int numBytesLut = 1 + NumBytesUInt(numElem) + 1 + ((numBitsTotalLut + 7) >> 3) + ((numElem * nBitsLut + 7) >> 3);

  doLut = numBytesLut < numBytes;
  return min(numBytesLut, numBytes);
}

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

void BitStuffer2::BitStuff_Before_Lerc2v3(Byte** ppByte, const vector<unsigned int>& dataVec, int numBits)
{
  unsigned int numElements = (unsigned int)dataVec.size();
  unsigned int numUInts = (numElements * numBits + 31) / 32;
  unsigned int numBytes = numUInts * sizeof(unsigned int);
  unsigned int* arr = (unsigned int*)(*ppByte);

  memset(arr, 0, numBytes);

  // do the stuffing
  const unsigned int* srcPtr = &dataVec[0];
  unsigned int* dstPtr = arr;
  int bitPos = 0;

  for (unsigned int i = 0; i < numElements; i++)
  {
    if (32 - bitPos >= numBits)
    {
      unsigned int dstValue;
      memcpy(&dstValue, dstPtr, sizeof(unsigned int));
      dstValue |= (*srcPtr++) << (32 - bitPos - numBits);
      memcpy(dstPtr, &dstValue, sizeof(unsigned int));
      bitPos += numBits;
      if (bitPos == 32)    // shift >= 32 is undefined
      {
        bitPos = 0;
        dstPtr++;
      }
    }
    else
    {
      unsigned int dstValue;
      int n = numBits - (32 - bitPos);
      memcpy(&dstValue, dstPtr, sizeof(unsigned int));
      dstValue |= (*srcPtr) >> n;
      memcpy(dstPtr, &dstValue, sizeof(unsigned int));
      dstPtr++;
      memcpy(&dstValue, dstPtr, sizeof(unsigned int));
      dstValue |= (*srcPtr++) << (32 - n);
      memcpy(dstPtr, &dstValue, sizeof(unsigned int));
      bitPos = n;
    }
  }

  // save the 0-3 bytes not used in the last UInt
  unsigned int numBytesNotNeeded = NumTailBytesNotNeeded(numElements, numBits);
  unsigned int n = numBytesNotNeeded;
  for (; n; --n)
  {
    unsigned int dstValue;
    memcpy(&dstValue, dstPtr, sizeof(unsigned int));
    dstValue >>= 8;
    memcpy(dstPtr, &dstValue, sizeof(unsigned int));
  }

  *ppByte += numBytes - numBytesNotNeeded;
}

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

bool BitStuffer2::BitUnStuff_Before_Lerc2v3(const Byte** ppByte, size_t& nBytesRemaining,
    vector<unsigned int>& dataVec, unsigned int numElements, int numBits) const
{
  if (numElements == 0 || numBits >= 32)
    return false;
  unsigned long long numUIntsLL = ((unsigned long long)numElements * numBits + 31) / 32;
  unsigned long long numBytesLL = numUIntsLL * sizeof(unsigned int);
  size_t numBytes = (size_t)numBytesLL; // could theoretically overflow on 32 bit system
  size_t numUInts = (size_t)numUIntsLL;
  unsigned int ntbnn = NumTailBytesNotNeeded(numElements, numBits);
  if (numBytes != numBytesLL || nBytesRemaining + ntbnn < numBytes)
    return false;

  try
  {
    dataVec.resize(numElements, 0);    // init with 0
    m_tmpBitStuffVec.resize(numUInts);
  }
  catch( const std::exception& )
  {
    return false;
  }

  m_tmpBitStuffVec[numUInts - 1] = 0;    // set last uint to 0

  unsigned int nBytesToCopy = (numElements * numBits + 7) / 8;
  memcpy(&m_tmpBitStuffVec[0], *ppByte, nBytesToCopy);

  unsigned int* pLastULong = &m_tmpBitStuffVec[numUInts - 1];
  while (ntbnn)
  {
    -- ntbnn;
    *pLastULong <<= 8;
  }

  unsigned int* srcPtr = &m_tmpBitStuffVec[0];
  unsigned int* dstPtr = &dataVec[0];
  int bitPos = 0;

  for (unsigned int i = 0; i < numElements; i++)
  {
    if (32 - bitPos >= numBits)
    {
      unsigned int val;
      memcpy(&val, srcPtr, sizeof(unsigned int));
      unsigned int n = val << bitPos;
      *dstPtr++ = n >> (32 - numBits);
      bitPos += numBits;

      if (bitPos == 32)    // shift >= 32 is undefined
      {
        bitPos = 0;
        srcPtr++;
      }
    }
    else
    {
      unsigned int val;
      memcpy(&val, srcPtr, sizeof(unsigned int));
      srcPtr++;
      unsigned int n = val << bitPos;
      *dstPtr = n >> (32 - numBits);
      bitPos -= (32 - numBits);
      memcpy(&val, srcPtr, sizeof(unsigned int));
      *dstPtr++ |= val >> (32 - bitPos);
    }
  }

  *ppByte += nBytesToCopy;
  nBytesRemaining -= nBytesToCopy;

  return true;
}

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

// starting with version Lerc2v3: integer >> into local uint buffer, plus final memcpy

void BitStuffer2::BitStuff(Byte** ppByte, const vector<unsigned int>& dataVec, int numBits) const
{
  unsigned int numElements = (unsigned int)dataVec.size();
  unsigned int numUInts = (numElements * numBits + 31) / 32;
  unsigned int numBytes = numUInts * sizeof(unsigned int);

  m_tmpBitStuffVec.resize(numUInts);
  unsigned int* dstPtr = &m_tmpBitStuffVec[0];

  memset(dstPtr, 0, numBytes);

  // do the stuffing
  const unsigned int* srcPtr = &dataVec[0];
  int bitPos = 0;
  assert(numBits <= 32); // to avoid coverity warning about large shift a bit later, when doing (*srcPtr++) >> (32 - bitPos)

  for (unsigned int i = 0; i < numElements; i++)
  {
    if (32 - bitPos >= numBits)
    {
      *dstPtr |= (*srcPtr++) << bitPos;
      bitPos += numBits;
      if (bitPos == 32)    // shift >= 32 is undefined
      {
        dstPtr++;
        bitPos = 0;
      }
    }
    else
    {
      *dstPtr++ |= (*srcPtr) << bitPos;
      *dstPtr |= (*srcPtr++) >> (32 - bitPos);
      bitPos += numBits - 32;
    }
  }

  // copy the bytes to the outgoing byte stream
  size_t numBytesUsed = numBytes - NumTailBytesNotNeeded(numElements, numBits);
#ifdef CSA_BUILD
  assert( numElements );
#endif
  memcpy(*ppByte, m_tmpBitStuffVec.data(), numBytesUsed);

  *ppByte += numBytesUsed;
}

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

bool BitStuffer2::BitUnStuff(const Byte** ppByte, size_t& nBytesRemaining, vector<unsigned int>& dataVec,
  unsigned int numElements, int numBits) const
{
  if (numElements == 0 || numBits >= 32)
    return false;
  unsigned long long numUIntsLL = ((unsigned long long)numElements * numBits + 31) / 32;
  unsigned long long numBytesLL = numUIntsLL * sizeof(unsigned int);
  size_t numBytes = (size_t)numBytesLL; // could theoretically overflow on 32 bit system
  if (numBytes != numBytesLL)
    return false;
  size_t numUInts = (size_t)numUIntsLL;

  // copy the bytes from the incoming byte stream
  const size_t numBytesUsed = numBytes - NumTailBytesNotNeeded(numElements, numBits);

  if (nBytesRemaining < numBytesUsed)
    return false;

  try
  {
    dataVec.resize(numElements);
  }
  catch( const std::exception& )
  {
    return false;
  }

  try
  {
    m_tmpBitStuffVec.resize(numUInts);
  }
  catch( const std::exception& )
  {
    return false;
  }

  m_tmpBitStuffVec[numUInts - 1] = 0;    // set last uint to 0

  memcpy(&m_tmpBitStuffVec[0], *ppByte, numBytesUsed);

  // do the un-stuffing
  unsigned int* srcPtr = &m_tmpBitStuffVec[0];
  unsigned int* dstPtr = &dataVec[0];
  int bitPos = 0;
  int nb = 32 - numBits;

  for (unsigned int i = 0; i < numElements; i++)
  {
    if (nb - bitPos >= 0)
    {
      *dstPtr++ = ((*srcPtr) << (nb - bitPos)) >> nb;
      bitPos += numBits;
      if (bitPos == 32)    // shift >= 32 is undefined
      {
        srcPtr++;
        bitPos = 0;
      }
    }
    else
    {
      *dstPtr = (*srcPtr++) >> bitPos;
      *dstPtr++ |= ((*srcPtr) << (64 - numBits - bitPos)) >> nb;
      bitPos -= nb;
    }
  }

  *ppByte += numBytesUsed;
  nBytesRemaining -= numBytesUsed;
  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 <cassert>
26	#include "Defines.h"
27	#include "BitStuffer2.h"
28
29	using namespace std;
30	USING_NAMESPACE_LERC
31
32	// -------------------------------------------------------------------------- ;
33
34	// if you change Encode(...) / Decode(...), don't forget to update ComputeNumBytesNeeded(...)
35
36	bool BitStuffer2::EncodeSimple(Byte** ppByte, const vector<unsigned int>& dataVec, int lerc2Version) const	42,549✔
37	{
38	if (!ppByte \|\| dataVec.empty())	42,549✔
39	return false;	×
40
41	unsigned int maxElem = *max_element(dataVec.begin(), dataVec.end());	42,549✔
42	int numBits = 0;	42,549✔
43	while ((numBits < 32) && (maxElem >> numBits))	150,067✔
44	numBits++;	107,518✔
45
46	if (numBits >= 32)	42,549✔
47	return false;	×
48
49	Byte numBitsByte = (Byte)numBits;	42,549✔
50	unsigned int numElements = (unsigned int)dataVec.size();	42,549✔
51	unsigned int numUInts = (numElements * numBits + 31) / 32;	42,549✔
52
53	// use the upper 2 bits to encode the type used for numElements: Byte, ushort, or uint
54	int n = NumBytesUInt(numElements);	42,549✔
55	int bits67 = (n == 4) ? 0 : 3 - n;	42,549✔
56	numBitsByte \|= bits67 << 6;	42,549✔
57
58	// bit5 = 0 means simple mode
59
60	**ppByte = numBitsByte;	42,549✔
61	(*ppByte)++;	42,549✔
62
63	if (!EncodeUInt(ppByte, numElements, n))	42,549✔
64	return false;	×
65
66	if (numUInts > 0) // numBits can be 0, then we only write the header	42,549✔
67	{
68	if (lerc2Version >= 3)	42,549✔
69	BitStuff(ppByte, dataVec, numBits);	18,287✔
70	else
71	BitStuff_Before_Lerc2v3(ppByte, dataVec, numBits);	24,262✔
72	}
73
74	return true;	42,549✔
75	}
76
77	// -------------------------------------------------------------------------- ;
78
79	bool BitStuffer2::EncodeLut(Byte** ppByte, const vector<pair<unsigned int, unsigned int> >& sortedDataVec, int lerc2Version) const	220,916✔
80	{
81	if (!ppByte \|\| sortedDataVec.empty())	220,916✔
82	return false;	×
83
84	if (sortedDataVec[0].first != 0) // corresponds to min	220,916✔
85	return false;	×
86
87	// collect the different values for the lut
88	unsigned int numElem = (unsigned int)sortedDataVec.size();	220,916✔
89	unsigned int indexLut = 0;	220,916✔
90
91	m_tmpLutVec.resize(0); // omit the 0 throughout that corresponds to min	220,916✔
92	m_tmpIndexVec.assign(numElem, 0);	220,916✔
93
94	for (unsigned int i = 1; i < numElem; i++)	14,708,400✔
95	{
96	unsigned int prev = sortedDataVec[i - 1].first;	14,487,500✔
97	m_tmpIndexVec[sortedDataVec[i - 1].second] = indexLut;	14,487,500✔
98
99	if (sortedDataVec[i].first != prev)	14,487,500✔
100	{
101	m_tmpLutVec.push_back(sortedDataVec[i].first);	320,862✔
102	indexLut++;	320,862✔
103	}
104	}
105	m_tmpIndexVec[sortedDataVec[numElem - 1].second] = indexLut; // don't forget the last one	220,916✔
106
107	// write first 2 data elements same as simple, but bit5 set to 1
108	unsigned int maxElem = m_tmpLutVec.back();	220,916✔
109	int numBits = 0;	220,916✔
110	while ((numBits < 32) && (maxElem >> numBits))	1,182,940✔
111	numBits++;	962,025✔
112
113	if (numBits >= 32)	220,916✔
114	return false;	×
115
116	Byte numBitsByte = (Byte)numBits;	220,916✔
117
118	// use the upper 2 bits to encode the type used for numElem: byte, ushort, or uint
119	int n = NumBytesUInt(numElem);	220,916✔
120	int bits67 = (n == 4) ? 0 : 3 - n;	220,916✔
121	numBitsByte \|= bits67 << 6;	220,916✔
122
123	numBitsByte \|= (1 << 5); // bit 5 = 1 means lut mode	220,916✔
124
125	**ppByte = numBitsByte;	220,916✔
126	(*ppByte)++;	220,916✔
127
128	if (!EncodeUInt(ppByte, numElem, n)) // numElements = numIndexes to lut	220,916✔
129	return false;	×
130
131	unsigned int nLut = (unsigned int)m_tmpLutVec.size();	220,916✔
132	if (nLut < 1 \|\| nLut >= 255)	220,916✔
133	return false;	×
134
135	**ppByte = (Byte)nLut + 1; // size of lut, incl the 0	220,916✔
136	(*ppByte)++;	220,916✔
137
138	if (lerc2Version >= 3)	220,916✔
139	BitStuff(ppByte, m_tmpLutVec, numBits); // lut	1,112✔
140	else
141	BitStuff_Before_Lerc2v3(ppByte, m_tmpLutVec, numBits);	219,804✔
142
143	int nBitsLut = 0;	220,916✔
144	while (nLut >> nBitsLut) // indexes are in [0 .. nLut]	496,289✔
145	nBitsLut++;	275,373✔
146
147	if (lerc2Version >= 3)	220,916✔
148	BitStuff(ppByte, m_tmpIndexVec, nBitsLut); // indexes	1,112✔
149	else
150	BitStuff_Before_Lerc2v3(ppByte, m_tmpIndexVec, nBitsLut);	219,804✔
151
152	return true;	220,916✔
153	}
154
155	// -------------------------------------------------------------------------- ;
156
157	// if you change Encode(...) / Decode(...), don't forget to update ComputeNumBytesNeeded(...)
158
159	bool BitStuffer2::Decode(const Byte** ppByte, size_t& nBytesRemaining, vector<unsigned int>& dataVec, size_t maxElementCount, int lerc2Version) const	116,861✔
160	{
161	if (!ppByte \|\| nBytesRemaining < 1)	116,861✔
UNCOV 162	return false;	×
163
164	Byte numBitsByte = **ppByte;	116,862✔
165	(*ppByte)++;	116,862✔
166	nBytesRemaining--;	116,862✔
167
168	int bits67 = numBitsByte >> 6;	116,862✔
169	int nb = (bits67 == 0) ? 4 : 3 - bits67;	116,862✔
170
171	bool doLut = (numBitsByte & (1 << 5)) ? true : false; // bit 5	116,862✔
172	numBitsByte &= 31; // bits 0-4;	116,862✔
173	int numBits = numBitsByte;	116,862✔
174
175	unsigned int numElements = 0;	116,862✔
176	if (!DecodeUInt(ppByte, nBytesRemaining, numElements, nb))	116,862✔
177	return false;	×
178	if (numElements > maxElementCount)	116,862✔
179	return false;	×
180
181	if (!doLut)	116,862✔
182	{
183	if (numBits > 0) // numBits can be 0	40,386✔
184	{
185	if (lerc2Version >= 3)	40,386✔
186	{
187	if (!BitUnStuff(ppByte, nBytesRemaining, dataVec, numElements, numBits))	32,178✔
188	return false;	×
189	}
190	else
191	{
192	if (!BitUnStuff_Before_Lerc2v3(ppByte, nBytesRemaining, dataVec, numElements, numBits))	8,208✔
193	return false;	×
194	}
195	}
196	}
197	else
198	{
199	if (numBits == 0) // fail gracefully in case of corrupted blob for old version <= 2 which had no checksum	76,476✔
200	return false;	×
201	if (nBytesRemaining < 1)	76,476✔
202	return false;	×
203
204	Byte nLutByte = **ppByte;	76,476✔
205	(*ppByte)++;	76,476✔
206	nBytesRemaining--;	76,476✔
207
208	int nLut = nLutByte - 1;	76,476✔
209
210	// unstuff lut w/o the 0
211	if (lerc2Version >= 3)	76,476✔
212	{
213	if (!BitUnStuff(ppByte, nBytesRemaining, m_tmpLutVec, nLut, numBits))	2,494✔
214	return false;	×
215	}
216	else
217	{
218	if (!BitUnStuff_Before_Lerc2v3(ppByte, nBytesRemaining, m_tmpLutVec, nLut, numBits))	73,982✔
219	return false;	×
220	}
221
222	int nBitsLut = 0;	76,476✔
223	while (nLut >> nBitsLut)	176,155✔
224	nBitsLut++;	99,679✔
225	if (nBitsLut == 0)	76,476✔
226	return false;	×
227
228	if (lerc2Version >= 3)	76,476✔
229	{
230	// unstuff indexes
231	if (!BitUnStuff(ppByte, nBytesRemaining, dataVec, numElements, nBitsLut))	2,494✔
232	return false;	×
233
234	// replace indexes by values
235	#if defined(__GNUC__)
236	#pragma GCC diagnostic push
237	#pragma GCC diagnostic ignored "-Wnull-dereference"
238	#endif
239	m_tmpLutVec.insert(m_tmpLutVec.begin(), 0); // put back in the 0	2,494✔
240	#if defined(__GNUC__)
241	#pragma GCC diagnostic pop
242	#endif
243	for (unsigned int i = 0; i < numElements; i++)	157,081✔
244	{
245	#ifdef GDAL_COMPILATION
246	if (dataVec[i] >= m_tmpLutVec.size())	154,343✔
247	return false;	×
248	#endif
249	dataVec[i] = m_tmpLutVec[dataVec[i]];	154,595✔
250	}
251	}
252	else
253	{
254	// unstuff indexes
255	if (!BitUnStuff_Before_Lerc2v3(ppByte, nBytesRemaining, dataVec, numElements, nBitsLut))	73,982✔
256	return false;	×
257
258	// replace indexes by values
259	#if defined(__GNUC__)
260	#pragma GCC diagnostic push
261	#pragma GCC diagnostic ignored "-Wnull-dereference"
262	#endif
263	m_tmpLutVec.insert(m_tmpLutVec.begin(), 0); // put back in the 0	73,982✔
264	#if defined(__GNUC__)
265	#pragma GCC diagnostic pop
266	#endif
267	for (unsigned int i = 0; i < numElements; i++)	4,992,710✔
268	{
269	if (dataVec[i] >= m_tmpLutVec.size())	4,918,980✔
270	return false;	×
271
272	dataVec[i] = m_tmpLutVec[dataVec[i]];	4,918,980✔
273	}
274	}
275	}
276
277	return true;	116,862✔
278	}
279
280	// -------------------------------------------------------------------------- ;
281
282	unsigned int BitStuffer2::ComputeNumBytesNeededLut(const vector<pair<unsigned int, unsigned int> >& sortedDataVec, bool& doLut)	709,569✔
283	{
284	unsigned int maxElem = sortedDataVec.back().first;	709,569✔
285	unsigned int numElem = (unsigned int)sortedDataVec.size();	709,569✔
286
287	int numBits = 0;	709,569✔
288	while ((numBits < 32) && (maxElem >> numBits))	3,591,790✔
289	numBits++;	2,882,220✔
290	unsigned int numBytes = 1 + NumBytesUInt(numElem) + ((numElem * numBits + 7) >> 3);	709,569✔
291
292	// go through and count how often the value changes
293	int nLut = 0;	709,569✔
294	for (unsigned int i = 1; i < numElem; i++)	71,172,000✔
295	if (sortedDataVec[i].first != sortedDataVec[i - 1].first)	70,462,500✔
296	nLut++;	1,145,300✔
297
298	int nBitsLut = 0;	709,569✔
299	while (nLut >> nBitsLut)	1,655,040✔
300	nBitsLut++;	945,475✔
301
302	unsigned int numBitsTotalLut = nLut * numBits; // num bits w/o the 0	709,569✔
303	unsigned int numBytesLut = 1 + NumBytesUInt(numElem) + 1 + ((numBitsTotalLut + 7) >> 3) + ((numElem * nBitsLut + 7) >> 3);	709,569✔
304
305	doLut = numBytesLut < numBytes;	709,569✔
306	return min(numBytesLut, numBytes);	709,569✔
307	}
308
309	// -------------------------------------------------------------------------- ;
310	// -------------------------------------------------------------------------- ;
311
312	void BitStuffer2::BitStuff_Before_Lerc2v3(Byte** ppByte, const vector<unsigned int>& dataVec, int numBits)	463,870✔
313	{
314	unsigned int numElements = (unsigned int)dataVec.size();	463,870✔
315	unsigned int numUInts = (numElements * numBits + 31) / 32;	463,870✔
316	unsigned int numBytes = numUInts * sizeof(unsigned int);	463,870✔
317	unsigned int* arr = (unsigned int)(ppByte);	463,870✔
318
319	memset(arr, 0, numBytes);	463,870✔
320
321	// do the stuffing
322	const unsigned int* srcPtr = &dataVec[0];	463,870✔
323	unsigned int* dstPtr = arr;	463,870✔
324	int bitPos = 0;	463,870✔
325
326	for (unsigned int i = 0; i < numElements; i++)	17,363,600✔
327	{
328	if (32 - bitPos >= numBits)	16,899,800✔
329	{
330	unsigned int dstValue;
331	memcpy(&dstValue, dstPtr, sizeof(unsigned int));	16,897,100✔
332	dstValue \|= (*srcPtr++) << (32 - bitPos - numBits);	16,897,100✔
333	memcpy(dstPtr, &dstValue, sizeof(unsigned int));	16,897,100✔
334	bitPos += numBits;	16,897,100✔
335	if (bitPos == 32) // shift >= 32 is undefined	16,897,100✔
336	{
337	bitPos = 0;	641,691✔
338	dstPtr++;	641,691✔
339	}
340	}
341	else
342	{
343	unsigned int dstValue;
344	int n = numBits - (32 - bitPos);	2,634✔
345	memcpy(&dstValue, dstPtr, sizeof(unsigned int));	2,634✔
346	dstValue \|= (*srcPtr) >> n;	2,634✔
347	memcpy(dstPtr, &dstValue, sizeof(unsigned int));	2,634✔
348	dstPtr++;	2,634✔
349	memcpy(&dstValue, dstPtr, sizeof(unsigned int));	2,634✔
350	dstValue \|= (*srcPtr++) << (32 - n);	2,634✔
351	memcpy(dstPtr, &dstValue, sizeof(unsigned int));	2,634✔
352	bitPos = n;	2,634✔
353	}
354	}
355
356	// save the 0-3 bytes not used in the last UInt
357	unsigned int numBytesNotNeeded = NumTailBytesNotNeeded(numElements, numBits);	463,870✔
358	unsigned int n = numBytesNotNeeded;	463,870✔
359	for (; n; --n)	1,060,330✔
360	{
361	unsigned int dstValue;
362	memcpy(&dstValue, dstPtr, sizeof(unsigned int));	596,462✔
363	dstValue >>= 8;	596,462✔
364	memcpy(dstPtr, &dstValue, sizeof(unsigned int));	596,462✔
365	}
366
367	*ppByte += numBytes - numBytesNotNeeded;	463,870✔
368	}	463,870✔
369
370	// -------------------------------------------------------------------------- ;
371
372	bool BitStuffer2::BitUnStuff_Before_Lerc2v3(const Byte** ppByte, size_t& nBytesRemaining,	156,172✔
373	vector<unsigned int>& dataVec, unsigned int numElements, int numBits) const
374	{
375	if (numElements == 0 \|\| numBits >= 32)	156,172✔
376	return false;	×
377	unsigned long long numUIntsLL = ((unsigned long long)numElements * numBits + 31) / 32;	156,172✔
378	unsigned long long numBytesLL = numUIntsLL * sizeof(unsigned int);	156,172✔
379	size_t numBytes = (size_t)numBytesLL; // could theoretically overflow on 32 bit system	156,172✔
380	size_t numUInts = (size_t)numUIntsLL;	156,172✔
381	unsigned int ntbnn = NumTailBytesNotNeeded(numElements, numBits);	156,172✔
382	if (numBytes != numBytesLL \|\| nBytesRemaining + ntbnn < numBytes)	156,172✔
383	return false;	×
384
385	try
386	{
387	dataVec.resize(numElements, 0); // init with 0	156,172✔
388	m_tmpBitStuffVec.resize(numUInts);	156,172✔
389	}
390	catch( const std::exception& )	×
391	{
392	return false;	×
393	}
394
395	m_tmpBitStuffVec[numUInts - 1] = 0; // set last uint to 0	156,172✔
396
397	unsigned int nBytesToCopy = (numElements * numBits + 7) / 8;	156,172✔
398	memcpy(&m_tmpBitStuffVec[0], *ppByte, nBytesToCopy);	156,172✔
399
400	unsigned int* pLastULong = &m_tmpBitStuffVec[numUInts - 1];	156,172✔
401	while (ntbnn)	356,374✔
402	{
403	-- ntbnn;	200,202✔
404	*pLastULong <<= 8;	200,202✔
405	}
406
407	unsigned int* srcPtr = &m_tmpBitStuffVec[0];	156,172✔
408	unsigned int* dstPtr = &dataVec[0];	156,172✔
409	int bitPos = 0;	156,172✔
410
411	for (unsigned int i = 0; i < numElements; i++)	5,855,250✔
412	{
413	if (32 - bitPos >= numBits)	5,699,080✔
414	{
415	unsigned int val;
416	memcpy(&val, srcPtr, sizeof(unsigned int));	5,697,570✔
417	unsigned int n = val << bitPos;	5,697,570✔
418	*dstPtr++ = n >> (32 - numBits);	5,697,570✔
419	bitPos += numBits;	5,697,570✔
420
421	if (bitPos == 32) // shift >= 32 is undefined	5,697,570✔
422	{
423	bitPos = 0;	216,619✔
424	srcPtr++;	216,619✔
425	}
426	}
427	else
428	{
429	unsigned int val;
430	memcpy(&val, srcPtr, sizeof(unsigned int));	1,511✔
431	srcPtr++;	1,511✔
432	unsigned int n = val << bitPos;	1,511✔
433	*dstPtr = n >> (32 - numBits);	1,511✔
434	bitPos -= (32 - numBits);	1,511✔
435	memcpy(&val, srcPtr, sizeof(unsigned int));	1,511✔
436	*dstPtr++ \|= val >> (32 - bitPos);	1,511✔
437	}
438	}
439
440	*ppByte += nBytesToCopy;	156,172✔
441	nBytesRemaining -= nBytesToCopy;	156,172✔
442
443	return true;	156,172✔
444	}
445
446	// -------------------------------------------------------------------------- ;
447
448	// starting with version Lerc2v3: integer >> into local uint buffer, plus final memcpy
449
450	void BitStuffer2::BitStuff(Byte** ppByte, const vector<unsigned int>& dataVec, int numBits) const	20,511✔
451	{
452	unsigned int numElements = (unsigned int)dataVec.size();	20,511✔
453	unsigned int numUInts = (numElements * numBits + 31) / 32;	20,511✔
454	unsigned int numBytes = numUInts * sizeof(unsigned int);	20,511✔
455
456	m_tmpBitStuffVec.resize(numUInts);	20,511✔
457	unsigned int* dstPtr = &m_tmpBitStuffVec[0];	20,511✔
458
459	memset(dstPtr, 0, numBytes);	20,511✔
460
461	// do the stuffing
462	const unsigned int* srcPtr = &dataVec[0];	20,511✔
463	int bitPos = 0;	20,511✔
464	assert(numBits <= 32); // to avoid coverity warning about large shift a bit later, when doing (*srcPtr++) >> (32 - bitPos)	20,511✔
465
466	for (unsigned int i = 0; i < numElements; i++)	1,354,360✔
467	{
468	if (32 - bitPos >= numBits)	1,333,850✔
469	{
470	dstPtr \|= (srcPtr++) << bitPos;	1,253,970✔
471	bitPos += numBits;	1,253,970✔
472	if (bitPos == 32) // shift >= 32 is undefined	1,253,970✔
473	{
474	dstPtr++;	97,956✔
475	bitPos = 0;	97,956✔
476	}
477	}
478	else
479	{
480	dstPtr++ \|= (srcPtr) << bitPos;	79,880✔
481	dstPtr \|= (srcPtr++) >> (32 - bitPos);	79,880✔
482	bitPos += numBits - 32;	79,880✔
483	}
484	}
485
486	// copy the bytes to the outgoing byte stream
487	size_t numBytesUsed = numBytes - NumTailBytesNotNeeded(numElements, numBits);	20,511✔
488	#ifdef CSA_BUILD
489	assert( numElements );
490	#endif
491	memcpy(*ppByte, m_tmpBitStuffVec.data(), numBytesUsed);	20,511✔
492
493	*ppByte += numBytesUsed;	20,511✔
494	}	20,511✔
495
496	// -------------------------------------------------------------------------- ;
497
498	bool BitStuffer2::BitUnStuff(const Byte** ppByte, size_t& nBytesRemaining, vector<unsigned int>& dataVec,	37,165✔
499	unsigned int numElements, int numBits) const
500	{
501	if (numElements == 0 \|\| numBits >= 32)	37,165✔
UNCOV 502	return false;	×
503	unsigned long long numUIntsLL = ((unsigned long long)numElements * numBits + 31) / 32;	37,165✔
504	unsigned long long numBytesLL = numUIntsLL * sizeof(unsigned int);	37,165✔
505	size_t numBytes = (size_t)numBytesLL; // could theoretically overflow on 32 bit system	37,165✔
506	if (numBytes != numBytesLL)	37,165✔
507	return false;	×
508	size_t numUInts = (size_t)numUIntsLL;	37,165✔
509
510	// copy the bytes from the incoming byte stream
511	const size_t numBytesUsed = numBytes - NumTailBytesNotNeeded(numElements, numBits);	37,165✔
512
513	if (nBytesRemaining < numBytesUsed)	37,165✔
514	return false;	×
515
516	try
517	{
518	dataVec.resize(numElements);	37,165✔
519	}
520	catch( const std::exception& )	×
521	{
522	return false;	×
523	}
524
525	try
526	{
527	m_tmpBitStuffVec.resize(numUInts);	37,164✔
528	}
529	catch( const std::exception& )	×
530	{
531	return false;	×
532	}
533
534	m_tmpBitStuffVec[numUInts - 1] = 0; // set last uint to 0	37,165✔
535
536	memcpy(&m_tmpBitStuffVec[0], *ppByte, numBytesUsed);	37,163✔
537
538	// do the un-stuffing
539	unsigned int* srcPtr = &m_tmpBitStuffVec[0];	37,163✔
540	unsigned int* dstPtr = &dataVec[0];	37,166✔
541	int bitPos = 0;	37,164✔
542	int nb = 32 - numBits;	37,164✔
543
544	for (unsigned int i = 0; i < numElements; i++)	2,328,240✔
545	{
546	if (nb - bitPos >= 0)	2,291,070✔
547	{
548	dstPtr++ = ((srcPtr) << (nb - bitPos)) >> nb;	2,163,960✔
549	bitPos += numBits;	2,163,960✔
550	if (bitPos == 32) // shift >= 32 is undefined	2,163,960✔
551	{
552	srcPtr++;	175,984✔
553	bitPos = 0;	175,984✔
554	}
555	}
556	else
557	{
558	dstPtr = (srcPtr++) >> bitPos;	127,112✔
559	dstPtr++ \|= ((srcPtr) << (64 - numBits - bitPos)) >> nb;	127,112✔
560	bitPos -= nb;	127,112✔
561	}
562	}
563
564	*ppByte += numBytesUsed;	37,164✔
565	nBytesRemaining -= numBytesUsed;	37,164✔
566	return true;	37,164✔
567	}
568
569	// -------------------------------------------------------------------------- ;
570

OSGeo / gdal / 15899162844

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