OpenVDB  10.0.1
GridChecksum.h
Go to the documentation of this file.
1 // Copyright Contributors to the OpenVDB Project
2 // SPDX-License-Identifier: MPL-2.0
3 
4 /*!
5  \file GridChecksum.h
6 
7  \author Ken Museth
8 
9  \brief Computes a pair of 32bit checksums, og a Grid, by means of Cyclic Redundancy Check (CRC)
10 
11  \details A CRC32 is the 32 bit remainder, or residue, of binary division of a message, by a polynomial.
12 */
13 
14 #ifndef NANOVDB_GRIDCHECKSUM_H_HAS_BEEN_INCLUDED
15 #define NANOVDB_GRIDCHECKSUM_H_HAS_BEEN_INCLUDED
16 
17 #include <algorithm>// for std::generate
18 #include <array>
19 #include <vector>
20 #include <cstdint>
21 #include <cstddef>// offsetof macro
22 #include <numeric>
23 #include <type_traits>
24 
25 #include "../NanoVDB.h"
26 #include "GridHandle.h"
27 #include "ForEach.h"
28 #include "NodeManager.h"
29 
30 namespace nanovdb {
31 
32 /// @brief List of different modes for computing for a checksum
33 enum class ChecksumMode : uint32_t { Disable = 0,// no computation
34  Partial = 1,// fast but approximate
35  Full = 2,// slow but accurate
36  Default = 1,// defaults to Partial
37  End = 3 };// marks the end of the enum list
38 
39 /// @brief Return the (2 x CRC32) checksum of the specified @a grid
40 ///
41 /// @param grid Grid from which the checksum is computed.
42 /// @param mode Defines the mode of computation for the checksum.
43 template <typename ValueT>
44 uint64_t checksum(const NanoGrid<ValueT> &grid, ChecksumMode mode = ChecksumMode::Default);
45 
46 /// @brief Return true if the checksum of the @a grid matches the expected
47 /// value already encoded into the grid's meta data.
48 ///
49 /// @param grid Grid whose checksum is validated.
50 /// @param mode Defines the mode of computation for the checksum.
51 template <typename ValueT>
53 
54 /// @brief Updates the checksum of a grid
55 ///
56 /// @param grid Grid whose checksum will be updated.
57 /// @param mode Defines the mode of computation for the checksum.
58 template <typename ValueT>
60 
61 /// @brief Return the CRC32 checksum of the raw @a data of @a size
62 /// @param data The beginning of the raw data.
63 /// @param size Size of the data to bytes!
64 inline std::uint_fast32_t crc32(const void *data, size_t size);
65 
66 /// @brief Return the CRC32 checksum of the content pointed to be the iterator
67 /// @param begin Beginning of the iterator range
68 /// @param end End of the iterator range (exclusive)
69 /// @warning The dereference of the iterator must be convertible to a uint8_t
70 template <typename IterT>
71 std::uint_fast32_t crc32(IterT begin, IterT end);
72 
73 /// @brief Class that computes the Cyclic Redundancy Check (CRC)
74 class CRC32
75 {
76  using ByteT = std::uint_fast8_t;
77  using HashT = std::uint_fast32_t;
78  HashT mChecksum;
79 
80  static std::array<HashT, 256> INIT()
81  {
82  HashT n = 0;
83  auto kernel = [&n]()->HashT{
84  HashT checksum = n++;
85  for (int i = 0; i < 8; ++i) checksum = (checksum >> 1) ^ ((checksum & 0x1u) ? HashT{0xEDB88320uL} : 0);
86  return checksum;
87  };
88  std::array<HashT, 256> LUT{};
89  std::generate(LUT.begin(), LUT.end(), kernel);
90  return LUT;// move semantic should prevent a deep copy
91  }
92 
93 public:
94 
95  static const HashT EMPTY = ~HashT{0} & HashT{0xFFFFFFFFuL};// All bits are on
96 
97  CRC32() : mChecksum(EMPTY) {}
98 
99  void reset() { mChecksum = EMPTY; }
100 
101  HashT checksum() const { return HashT{0xFFFFFFFFuL} & ~mChecksum; }
102 
103  template <typename IterT>
104  void operator()(IterT begin, IterT end)
105  {
106  static const auto LUT = INIT();// scoped static initialization is thread-safe since C++11
107  auto kernel = [](HashT checksum, ByteT value){return LUT[(checksum ^ value) & 0xFFu] ^ (checksum >> 8);};
108  mChecksum = std::accumulate(begin, end, mChecksum, kernel);
109  }
110 
111  void operator()(const void *data, size_t byteSize)
112  {
113  const ByteT *begin = static_cast<const ByteT*>(data);
114  this->operator()<const ByteT*>(begin, begin + byteSize);
115  }
116 
117  template <typename T>
118  void operator()(const T &data) {(*this)(&data, sizeof(T));}
119 };// CRC32
120 
121 inline std::uint_fast32_t crc32(const void *data, size_t byteSize)
122 {
123  CRC32 crc;
124  crc(data, byteSize);
125  return crc.checksum();
126 }
127 
128 template <typename IterT>
129 inline std::uint_fast32_t crc32(IterT begin, IterT end)
130 {
131  CRC32 crc;
132  crc(begin, end);
133  return crc.checksum();
134 }
135 
136 /// @brief Class that encapsulates two CRC32 checksums, one for the Grid, Tree and Root node meta data
137 /// and one for the remaining grid nodes.
139 {
140  union {uint32_t mCRC[2]; uint64_t mChecksum; };
141 
142 public:
143 
144  static const uint64_t EMPTY = (static_cast<uint64_t>(CRC32::EMPTY) << 32) | static_cast<uint64_t>(CRC32::EMPTY);
145 
147 
148  GridChecksum(uint32_t head, uint32_t tail) : mCRC{head, tail} {}
149 
150  GridChecksum(uint64_t checksum, ChecksumMode mode = ChecksumMode::Full) : mChecksum{mode == ChecksumMode::Disable ? EMPTY : checksum}
151  {
152  if (mode == ChecksumMode::Partial) mCRC[1] = CRC32::EMPTY;
153  }
154 
155  uint64_t checksum() const { return mChecksum; }
156 
157  uint32_t crc32(int i) const {assert(i==0 || i==1); return mCRC[i]; }
158 
159  bool isFull() const { return mCRC[0] != CRC32::EMPTY && mCRC[1] != CRC32::EMPTY; }
160 
161  bool isEmpty() const { return mChecksum == EMPTY; }
162 
164  {
165  return mChecksum == EMPTY ? ChecksumMode::Disable :
167  }
168 
169  template <typename ValueT>
170  void operator()(const NanoGrid<ValueT> &grid, ChecksumMode mode = ChecksumMode::Full);
171 
172  bool operator==(const GridChecksum &rhs) const {return mChecksum == rhs.mChecksum;}
173  bool operator!=(const GridChecksum &rhs) const {return mChecksum != rhs.mChecksum;}
174 };// GridChecksum
175 
176 // [GridData][TreeData]---[RootData][ROOT TILES...]---[NodeData<5>]---[NodeData<4>]---[LeafData<3>]---[BLINDMETA...]---[BLIND0]---[BLIND1]---etc.
177 template <typename ValueT>
179 {
180  // Validate the assumed memory layout
181 #if 1
183  NANOVDB_ASSERT(NANOVDB_OFFSETOF(GridData, mChecksum) == 8);
184  NANOVDB_ASSERT(NANOVDB_OFFSETOF(GridData, mVersion) == 16);
185 #else// the static asserts below generate compiler warnings
186  static_assert(offsetof(GridData, mMagic) == 0, "Unexpected offset to magic number");
187  static_assert(offsetof(GridData, mChecksum) == 8, "Unexpected offset to checksum");
188  static_assert(offsetof(GridData, mVersion) == 16, "Unexpected offset to version number");
189 #endif
190  static const size_t offset = 16;
191 
192  mChecksum = EMPTY;
193 
194  if (mode == ChecksumMode::Disable) return;
195 
196  const auto &tree = grid.tree();
197  const auto &root = tree.root();
198  CRC32 crc;
199 
200  // process Grid + Tree + Root but exclude mMagic and mChecksum
201  const uint8_t *begin = reinterpret_cast<const uint8_t*>(&grid);
202  const uint8_t *end = begin + grid.memUsage() + tree.memUsage() + root.memUsage();
203  crc(begin + offset, end);
204 
205  mCRC[0] = crc.checksum();
206 
207  if (mode == ChecksumMode::Partial || tree.isEmpty()) return;
208 
209  auto nodeMgrHandle = createNodeManager(grid);
210  auto *nodeMgr = nodeMgrHandle.template mgr<ValueT>();
211  assert(isValid(nodeMgr));
212  const auto nodeCount = tree.nodeCount(0) + tree.nodeCount(1) + tree.nodeCount(2);
213  std::vector<std::uint_fast32_t> checksums(nodeCount, 0);
214 
215  // process upper internal nodes
216  auto kernel2 = [&](const Range1D &r) {
217  CRC32 local;
218  std::uint_fast32_t *p = checksums.data() + r.begin();
219  for (auto i = r.begin(); i != r.end(); ++i) {
220  const auto &node = nodeMgr->upper(static_cast<uint32_t>(i));
221  local(node);
222  *p++ = local.checksum();
223  local.reset();
224  }
225  };
226 
227  // process lower internal nodes
228  auto kernel1 = [&](const Range1D &r) {
229  CRC32 local;
230  std::uint_fast32_t *p = checksums.data() + r.begin() + tree.nodeCount(2);
231  for (auto i = r.begin(); i != r.end(); ++i) {
232  const auto &node = nodeMgr->lower(static_cast<uint32_t>(i));
233  local(node);
234  *p++ = local.checksum();
235  local.reset();
236  }
237  };
238 
239  // process leaf nodes
240  auto kernel0 = [&](const Range1D &r) {
241  CRC32 local;
242  std::uint_fast32_t *p = checksums.data() + r.begin() + tree.nodeCount(1) + tree.nodeCount(2);
243  for (auto i = r.begin(); i != r.end(); ++i) {
244  const auto &leaf = nodeMgr->leaf(static_cast<uint32_t>(i));
245  local(leaf);
246  *p++ = local.checksum();
247  local.reset();
248  }
249  };
250 
251  forEach(0, tree.nodeCount(2), 1, kernel2);
252  forEach(0, tree.nodeCount(1), 1, kernel1);
253  forEach(0, tree.nodeCount(0), 8, kernel0);
254 
255  crc.reset();
256  crc(checksums.data(), sizeof(std::uint_fast32_t)*checksums.size() );
257  mCRC[1] = crc.checksum();
258 }// GridChecksum::operator()
259 
260 template <typename ValueT>
261 uint64_t checksum(const NanoGrid<ValueT> &grid, ChecksumMode mode)
262 {
263  GridChecksum cs;
264  cs(grid, mode);
265  return cs.checksum();
266 }
267 
268 template <typename ValueT>
270 {
271  GridChecksum cs1(grid.checksum(), mode), cs2;
272  cs2(grid, cs1.mode() );
273  return cs1 == cs2;
274 }
275 
276 template <typename ValueT>
278 {
279  GridChecksum cs;
280  cs(grid, mode);
281  grid.data()->mChecksum = cs.checksum();
282 }
283 
284 } // namespace nanovdb
285 
286 #endif // NANOVDB_GRIDCHECKSUM_H_HAS_BEEN_INCLUDED
Highest level of the data structure. Contains a tree and a world->index transform (that currently onl...
Definition: NanoVDB.h:2555
Class that computes the Cyclic Redundancy Check (CRC)
Definition: GridChecksum.h:74
#define NANOVDB_OFFSETOF(CLASS, MEMBER)
Definition: NanoVDB.h:206
std::uint_fast32_t crc32(const void *data, size_t size)
Return the CRC32 checksum of the raw data of size.
Definition: GridChecksum.h:121
A unified wrapper for tbb::parallel_for and a naive std::thread fallback.
ChecksumMode
List of different modes for computing for a checksum.
Definition: GridChecksum.h:33
Defines two classes, a GridRegister the defines the value type (e.g. Double, Float etc) of a NanoVDB ...
Class that encapsulates two CRC32 checksums, one for the Grid, Tree and Root node meta data and one f...
Definition: GridChecksum.h:138
void operator()(const NanoGrid< ValueT > &grid, ChecksumMode mode=ChecksumMode::Full)
Definition: GridChecksum.h:178
const TreeT & tree() const
Return a const reference to the tree.
Definition: NanoVDB.h:2598
void forEach(RangeT range, const FuncT &func)
simple wrapper for tbb::parallel_for with a naive std fallback
Definition: ForEach.h:40
bool operator!=(const GridChecksum &rhs) const
Definition: GridChecksum.h:173
HashT checksum() const
Definition: GridChecksum.h:101
Definition: NanoVDB.h:208
bool operator==(const GridChecksum &rhs) const
Definition: GridChecksum.h:172
uint64_t checksum(const NanoGrid< ValueT > &grid, ChecksumMode mode=ChecksumMode::Default)
Return the (2 x CRC32) checksum of the specified grid.
Definition: GridChecksum.h:261
static const HashT EMPTY
Definition: GridChecksum.h:95
uint64_t mChecksum
Definition: GridChecksum.h:140
GridChecksum(uint32_t head, uint32_t tail)
Definition: GridChecksum.h:148
Definition: Range.h:28
ValueT value
Definition: GridBuilder.h:1290
bool isEmpty() const
Definition: GridChecksum.h:161
void updateChecksum(NanoGrid< ValueT > &grid, ChecksumMode mode=ChecksumMode::Default)
Updates the checksum of a grid.
Definition: GridChecksum.h:277
bool isFull() const
Definition: GridChecksum.h:159
bool validateChecksum(const NanoGrid< ValueT > &grid, ChecksumMode mode=ChecksumMode::Default)
Return true if the checksum of the grid matches the expected value already encoded into the grid&#39;s me...
Definition: GridChecksum.h:269
DataType * data()
Definition: NanoVDB.h:2575
uint32_t crc32(int i) const
Definition: GridChecksum.h:157
#define NANOVDB_ASSERT(x)
Definition: NanoVDB.h:173
void operator()(const T &data)
Definition: GridChecksum.h:118
PromoteType< ValueT >::Highest accumulate(const PointDataTreeT &points, const std::string &attribute, const FilterT &filter=NullFilter())
Evaluates the total value of a point attribute.
Definition: PointStatistics.h:729
CRC32()
Definition: GridChecksum.h:97
uint64_t checksum() const
Return checksum of the grid buffer.
Definition: NanoVDB.h:2715
void operator()(const void *data, size_t byteSize)
Definition: GridChecksum.h:111
Struct with all the member data of the Grid (useful during serialization of an openvdb grid) ...
Definition: NanoVDB.h:2431
GridChecksum(uint64_t checksum, ChecksumMode mode=ChecksumMode::Full)
Definition: GridChecksum.h:150
NodeManagerHandle< BufferT > createNodeManager(const NanoGrid< BuildT > &grid, const BufferT &buffer=BufferT())
brief Construct a NodeManager and return its handle
Definition: NodeManager.h:289
static uint64_t memUsage()
Return memory usage in bytes for this class only.
Definition: NanoVDB.h:2580
void reset()
Definition: GridChecksum.h:99
GridChecksum()
Definition: GridChecksum.h:146
static bool isValid(const void *p)
return true if the specified pointer is aligned and not NULL
Definition: NanoVDB.h:504
ChecksumMode mode() const
Definition: GridChecksum.h:163
void operator()(IterT begin, IterT end)
Definition: GridChecksum.h:104
uint64_t checksum() const
Definition: GridChecksum.h:155