OpenVDB  9.1.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 most 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 };// CRC32
117 
118 inline std::uint_fast32_t crc32(const void *data, size_t byteSize)
119 {
120  CRC32 crc;
121  crc(data, byteSize);
122  return crc.checksum();
123 }
124 
125 template <typename IterT>
126 inline std::uint_fast32_t crc32(IterT begin, IterT end)
127 {
128  CRC32 crc;
129  crc(begin, end);
130  return crc.checksum();
131 }
132 
133 /// @brief Class that encapsulates two CRC32 checksums, one for the Grid, Tree and Root node meta data
134 /// and one for the remaining grid nodes.
136 {
137  union {uint32_t mCRC[2]; uint64_t mChecksum; };
138 
139 public:
140 
141  static const uint64_t EMPTY = (static_cast<uint64_t>(CRC32::EMPTY) << 32) | static_cast<uint64_t>(CRC32::EMPTY);
142 
144 
145  GridChecksum(uint32_t head, uint32_t tail) : mCRC{head, tail} {}
146 
147  GridChecksum(uint64_t checksum, ChecksumMode mode = ChecksumMode::Full) : mChecksum{mode == ChecksumMode::Disable ? EMPTY : checksum}
148  {
149  if (mode == ChecksumMode::Partial) mCRC[1] = CRC32::EMPTY;
150  }
151 
152  uint64_t checksum() const { return mChecksum; }
153 
154  uint32_t crc32(int i) const {assert(i==0 || i==1); return mCRC[i]; }
155 
156  bool isFull() const { return mCRC[0] != CRC32::EMPTY && mCRC[1] != CRC32::EMPTY; }
157 
158  bool isEmpty() const { return mChecksum == EMPTY; }
159 
161  {
162  return mChecksum == EMPTY ? ChecksumMode::Disable :
164  }
165 
166  template <typename ValueT>
167  void operator()(const NanoGrid<ValueT> &grid, ChecksumMode mode = ChecksumMode::Full);
168 
169  bool operator==(const GridChecksum &rhs) const {return mChecksum == rhs.mChecksum;}
170  bool operator!=(const GridChecksum &rhs) const {return mChecksum != rhs.mChecksum;}
171 };// GridChecksum
172 
173 // [GridData][TreeData]---[RootData][ROOT TILES...]---[NodeData<5>]---[NodeData<4>]---[LeafData<3>]---[BLINDMETA...]---[BLIND0]---[BLIND1]---etc.
174 template <typename ValueT>
176 {
177  // Validate the assumed memory layout
178 #if 1
180  NANOVDB_ASSERT(NANOVDB_OFFSETOF(GridData, mChecksum) == 8);
181  NANOVDB_ASSERT(NANOVDB_OFFSETOF(GridData, mVersion) == 16);
182 #else// the static asserts below generate compiler warnings
183  static_assert(offsetof(GridData, mMagic) == 0, "Unexpected offset to magic number");
184  static_assert(offsetof(GridData, mChecksum) == 8, "Unexpected offset to checksum");
185  static_assert(offsetof(GridData, mVersion) == 16, "Unexpected offset to version number");
186 #endif
187  static const size_t offset = 16;
188 
189  mChecksum = EMPTY;
190 
191  if (mode == ChecksumMode::Disable) return;
192 
193  const auto &tree = grid.tree();
194  const auto &root = tree.root();
195  CRC32 crc;
196 
197  // process Grid + Tree + Root but exclude mMagic and mChecksum
198  const uint8_t *begin = reinterpret_cast<const uint8_t*>(&grid);
199  const uint8_t *end = begin + grid.memUsage() + tree.memUsage() + root.memUsage();
200  crc(begin + offset, end);
201 
202  mCRC[0] = crc.checksum();
203 
204  if (mode == ChecksumMode::Partial || tree.isEmpty()) return;
205 
206  auto mgr = createNodeMgr(grid);
207  const auto nodeCount = tree.nodeCount(0) + tree.nodeCount(1) + tree.nodeCount(2);
208  std::vector<std::uint_fast32_t> checksums(nodeCount, 0);
209 
210  // process upper internal nodes
211  auto kernel2 = [&](const Range1D &r) {
212  CRC32 local;
213  std::uint_fast32_t *p = checksums.data() + r.begin();
214  for (auto i = r.begin(); i != r.end(); ++i) {
215  const auto *node = mgr.upper(static_cast<uint32_t>(i));
216  local(node, sizeof(*node) );
217  *p++ = local.checksum();
218  local.reset();
219  }
220  };
221 
222  // process lower internal nodes
223  auto kernel1 = [&](const Range1D &r) {
224  CRC32 local;
225  std::uint_fast32_t *p = checksums.data() + r.begin() + tree.nodeCount(2);
226  for (auto i = r.begin(); i != r.end(); ++i) {
227  const auto *node = mgr.lower(static_cast<uint32_t>(i));
228  local(node, sizeof(*node) );
229  *p++ = local.checksum();
230  local.reset();
231  }
232  };
233 
234  // process leaf nodes
235  auto kernel0 = [&](const Range1D &r) {
236  CRC32 local;
237  std::uint_fast32_t *p = checksums.data() + r.begin() + tree.nodeCount(1) + tree.nodeCount(2);
238  for (auto i = r.begin(); i != r.end(); ++i) {
239  const auto *leaf = mgr.leaf(static_cast<uint32_t>(i));
240  local(leaf, sizeof(*leaf) );
241  *p++ = local.checksum();
242  local.reset();
243  }
244  };
245 
246  forEach(0, tree.nodeCount(2), 1, kernel2);
247  forEach(0, tree.nodeCount(1), 1, kernel1);
248  forEach(0, tree.nodeCount(0), 8, kernel0);
249 
250  crc.reset();
251  crc(checksums.data(), sizeof(std::uint_fast32_t)*checksums.size() );
252  mCRC[1] = crc.checksum();
253 }// GridChecksum::operator()
254 
255 template <typename ValueT>
256 uint64_t checksum(const NanoGrid<ValueT> &grid, ChecksumMode mode)
257 {
258  GridChecksum cs;
259  cs(grid, mode);
260  return cs.checksum();
261 }
262 
263 template <typename ValueT>
265 {
266  GridChecksum cs1(grid.checksum(), mode), cs2;
267  cs2(grid, cs1.mode() );
268  return cs1 == cs2;
269 }
270 
271 template <typename ValueT>
273 {
274  GridChecksum cs;
275  cs(grid, mode);
276  grid.data()->mChecksum = cs.checksum();
277 }
278 
279 } // namespace nanovdb
280 
281 #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:2308
Class that computes the Cyclic Redundancy Check (CRC)
Definition: GridChecksum.h:74
#define NANOVDB_OFFSETOF(CLASS, MEMBER)
Definition: NanoVDB.h:182
std::uint_fast32_t crc32(const void *data, size_t size)
Return the CRC32 checksum of the raw data of size.
Definition: GridChecksum.h:118
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 ...
NodeManager< GridT > createNodeMgr(GridT &grid)
creates a NodeManager from a grid. Move semantics is used.
Definition: NodeManager.h:252
Class that encapsulates two CRC32 checksums, one for the Grid, Tree and Root node meta data and one f...
Definition: GridChecksum.h:135
void operator()(const NanoGrid< ValueT > &grid, ChecksumMode mode=ChecksumMode::Full)
Definition: GridChecksum.h:175
const TreeT & tree() const
Return a const reference to the tree.
Definition: NanoVDB.h:2345
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:170
HashT checksum() const
Definition: GridChecksum.h:101
Definition: NanoVDB.h:184
bool operator==(const GridChecksum &rhs) const
Definition: GridChecksum.h:169
uint64_t checksum(const NanoGrid< ValueT > &grid, ChecksumMode mode=ChecksumMode::Default)
Return the (2 x CRC32) checksum of the specified grid.
Definition: GridChecksum.h:256
static const HashT EMPTY
Definition: GridChecksum.h:95
uint64_t mChecksum
Definition: GridChecksum.h:137
GridChecksum(uint32_t head, uint32_t tail)
Definition: GridChecksum.h:145
Definition: Range.h:28
ValueT value
Definition: GridBuilder.h:1287
bool isEmpty() const
Definition: GridChecksum.h:158
void updateChecksum(NanoGrid< ValueT > &grid, ChecksumMode mode=ChecksumMode::Default)
Updates the checksum of a grid.
Definition: GridChecksum.h:272
bool isFull() const
Definition: GridChecksum.h:156
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:264
DataType * data()
Definition: NanoVDB.h:2328
uint32_t crc32(int i) const
Definition: GridChecksum.h:154
#define NANOVDB_ASSERT(x)
Definition: NanoVDB.h:149
CRC32()
Definition: GridChecksum.h:97
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
uint64_t checksum() const
Return checksum of the grid buffer.
Definition: NanoVDB.h:2460
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:2185
GridChecksum(uint64_t checksum, ChecksumMode mode=ChecksumMode::Full)
Definition: GridChecksum.h:147
static uint64_t memUsage()
Return memory usage in bytes for this class only.
Definition: NanoVDB.h:2333
void reset()
Definition: GridChecksum.h:99
GridChecksum()
Definition: GridChecksum.h:143
ChecksumMode mode() const
Definition: GridChecksum.h:160
void operator()(IterT begin, IterT end)
Definition: GridChecksum.h:104
uint64_t checksum() const
Definition: GridChecksum.h:152