Loading...
Searching...
No Matches
GridChecksum.h
Go to the documentation of this file.
// Copyright Contributors to the OpenVDB Project
// SPDX-License-Identifier: MPL-2.0
/*!
\file GridChecksum.h
\author Ken Museth
\brief Computes a pair of 32bit checksums, og a Grid, by means of Cyclic Redundancy Check (CRC)
\details A CRC32 is the 32 bit remainder, or residue, of binary division of a message, by a polynomial.
*/
#ifndef NANOVDB_GRIDCHECKSUM_H_HAS_BEEN_INCLUDED
#define NANOVDB_GRIDCHECKSUM_H_HAS_BEEN_INCLUDED
#include <algorithm>// for std::generate
#include <array>
#include <vector>
#include <cstdint>
#include <cstddef>// offsetof macro
#include <numeric>
#include <type_traits>
#include "../NanoVDB.h"
#include "GridHandle.h"
#include "ForEach.h"
#include "NodeManager.h"
namespace nanovdb {
/// @brief List of different modes for computing for a checksum
enum class ChecksumMode : uint32_t { Disable = 0,// no computation
Partial = 1,// fast but approximate
Full = 2,// slow but accurate
Default = 1,// defaults to Partial
End = 3 };// marks the end of the enum list
/// @brief Return the (2 x CRC32) checksum of the specified @a grid
///
/// @param grid Grid from which the checksum is computed.
/// @param mode Defines the mode of computation for the checksum.
template <typename ValueT>
uint64_t checksum(const NanoGrid<ValueT> &grid, ChecksumMode mode = ChecksumMode::Default);
/// @brief Return true if the checksum of the @a grid matches the expected
/// value already encoded into the grid's meta data.
///
/// @param grid Grid whose checksum is validated.
/// @param mode Defines the mode of computation for the checksum.
template <typename ValueT>
bool validateChecksum(const NanoGrid<ValueT> &grid, ChecksumMode mode = ChecksumMode::Default);
/// @brief Updates the checksum of a grid
///
/// @param grid Grid whose checksum will be updated.
/// @param mode Defines the mode of computation for the checksum.
template <typename ValueT>
void updateChecksum(NanoGrid<ValueT> &grid, ChecksumMode mode = ChecksumMode::Default);
/// @brief Return the CRC32 checksum of the raw @a data of @a size
/// @param data The beginning of the raw data.
/// @param size Size of the data to bytes!
inline std::uint_fast32_t crc32(const void *data, size_t size);
/// @brief Return the CRC32 checksum of the content pointed to be the iterator
/// @param begin Beginning of the iterator range
/// @param end End of the iterator range (exclusive)
/// @warning The dereference of the iterator must be convertible to a uint8_t
template <typename IterT>
std::uint_fast32_t crc32(IterT begin, IterT end);
/// @brief Class that computes the Cyclic Redundancy Check (CRC)
class CRC32
{
using ByteT = std::uint_fast8_t;
using HashT = std::uint_fast32_t;
HashT mChecksum;
static std::array<HashT, 256> INIT()
{
HashT n = 0;
auto kernel = [&n]()->HashT{
HashT checksum = n++;
for (int i = 0; i < 8; ++i) checksum = (checksum >> 1) ^ ((checksum & 0x1u) ? HashT{0xEDB88320uL} : 0);
return checksum;
};
std::array<HashT, 256> LUT{};
std::generate(LUT.begin(), LUT.end(), kernel);
return LUT;// move semantic should prevent a deep copy
}
public:
static const HashT EMPTY = ~HashT{0} & HashT{0xFFFFFFFFuL};// All bits are on
CRC32() : mChecksum(EMPTY) {}
void reset() { mChecksum = EMPTY; }
HashT checksum() const { return HashT{0xFFFFFFFFuL} & ~mChecksum; }
template <typename IterT>
void operator()(IterT begin, IterT end)
{
static const auto LUT = INIT();// scoped static initialization is thread-safe since C++11
auto kernel = [](HashT checksum, ByteT value){return LUT[(checksum ^ value) & 0xFFu] ^ (checksum >> 8);};
mChecksum = std::accumulate(begin, end, mChecksum, kernel);
}
void operator()(const void *data, size_t byteSize)
{
const ByteT *begin = static_cast<const ByteT*>(data);
this->operator()<const ByteT*>(begin, begin + byteSize);
}
template <typename T>
void operator()(const T &data) {(*this)(&data, sizeof(T));}
};// CRC32
inline std::uint_fast32_t crc32(const void *data, size_t byteSize)
{
CRC32 crc;
crc(data, byteSize);
return crc.checksum();
}
template <typename IterT>
inline std::uint_fast32_t crc32(IterT begin, IterT end)
{
CRC32 crc;
crc(begin, end);
return crc.checksum();
}
/// @brief Class that encapsulates two CRC32 checksums, one for the Grid, Tree and Root node meta data
/// and one for the remaining grid nodes.
class GridChecksum
{
union {uint32_t mCRC[2]; uint64_t mChecksum; };
public:
static const uint64_t EMPTY = (static_cast<uint64_t>(CRC32::EMPTY) << 32) | static_cast<uint64_t>(CRC32::EMPTY);
GridChecksum() : mCRC{CRC32::EMPTY, CRC32::EMPTY} {}
GridChecksum(uint32_t head, uint32_t tail) : mCRC{head, tail} {}
GridChecksum(uint64_t checksum, ChecksumMode mode = ChecksumMode::Full) : mChecksum{mode == ChecksumMode::Disable ? EMPTY : checksum}
{
if (mode == ChecksumMode::Partial) mCRC[1] = CRC32::EMPTY;
}
uint64_t checksum() const { return mChecksum; }
uint32_t crc32(int i) const {assert(i==0 || i==1); return mCRC[i]; }
bool isFull() const { return mCRC[0] != CRC32::EMPTY && mCRC[1] != CRC32::EMPTY; }
bool isEmpty() const { return mChecksum == EMPTY; }
ChecksumMode mode() const
{
return mChecksum == EMPTY ? ChecksumMode::Disable :
mCRC[1] == CRC32::EMPTY ? ChecksumMode::Partial : ChecksumMode::Full;
}
template <typename ValueT>
void operator()(const NanoGrid<ValueT> &grid, ChecksumMode mode = ChecksumMode::Full);
bool operator==(const GridChecksum &rhs) const {return mChecksum == rhs.mChecksum;}
bool operator!=(const GridChecksum &rhs) const {return mChecksum != rhs.mChecksum;}
};// GridChecksum
// [GridData][TreeData]---[RootData][ROOT TILES...]---[NodeData<5>]---[NodeData<4>]---[LeafData<3>]---[BLINDMETA...]---[BLIND0]---[BLIND1]---etc.
template <typename ValueT>
void GridChecksum::operator()(const NanoGrid<ValueT> &grid, ChecksumMode mode)
{
// Validate the assumed memory layout
#if 1
NANOVDB_ASSERT(NANOVDB_OFFSETOF(GridData, mMagic) == 0);
NANOVDB_ASSERT(NANOVDB_OFFSETOF(GridData, mChecksum) == 8);
NANOVDB_ASSERT(NANOVDB_OFFSETOF(GridData, mVersion) == 16);
#else// the static asserts below generate compiler warnings
static_assert(offsetof(GridData, mMagic) == 0, "Unexpected offset to magic number");
static_assert(offsetof(GridData, mChecksum) == 8, "Unexpected offset to checksum");
static_assert(offsetof(GridData, mVersion) == 16, "Unexpected offset to version number");
#endif
static const size_t offset = 16;
mChecksum = EMPTY;
if (mode == ChecksumMode::Disable) return;
const auto &tree = grid.tree();
const auto &root = tree.root();
CRC32 crc;
// process Grid + Tree + Root but exclude mMagic and mChecksum
const uint8_t *begin = reinterpret_cast<const uint8_t*>(&grid);
const uint8_t *end = begin + grid.memUsage() + tree.memUsage() + root.memUsage();
crc(begin + offset, end);
mCRC[0] = crc.checksum();
if (mode == ChecksumMode::Partial || tree.isEmpty()) return;
auto nodeMgrHandle = createNodeManager(grid);
auto *nodeMgr = nodeMgrHandle.template mgr<ValueT>();
assert(isValid(nodeMgr));
const auto nodeCount = tree.nodeCount(0) + tree.nodeCount(1) + tree.nodeCount(2);
std::vector<std::uint_fast32_t> checksums(nodeCount, 0);
// process upper internal nodes
auto kernel2 = [&](const Range1D &r) {
CRC32 local;
std::uint_fast32_t *p = checksums.data() + r.begin();
for (auto i = r.begin(); i != r.end(); ++i) {
const auto &node = nodeMgr->upper(static_cast<uint32_t>(i));
local(node);
*p++ = local.checksum();
local.reset();
}
};
// process lower internal nodes
auto kernel1 = [&](const Range1D &r) {
CRC32 local;
std::uint_fast32_t *p = checksums.data() + r.begin() + tree.nodeCount(2);
for (auto i = r.begin(); i != r.end(); ++i) {
const auto &node = nodeMgr->lower(static_cast<uint32_t>(i));
local(node);
*p++ = local.checksum();
local.reset();
}
};
// process leaf nodes
auto kernel0 = [&](const Range1D &r) {
CRC32 local;
std::uint_fast32_t *p = checksums.data() + r.begin() + tree.nodeCount(1) + tree.nodeCount(2);
for (auto i = r.begin(); i != r.end(); ++i) {
const auto &leaf = nodeMgr->leaf(static_cast<uint32_t>(i));
local(leaf);
*p++ = local.checksum();
local.reset();
}
};
forEach(0, tree.nodeCount(2), 1, kernel2);
forEach(0, tree.nodeCount(1), 1, kernel1);
forEach(0, tree.nodeCount(0), 8, kernel0);
crc.reset();
crc(checksums.data(), sizeof(std::uint_fast32_t)*checksums.size() );
mCRC[1] = crc.checksum();
}// GridChecksum::operator()
template <typename ValueT>
uint64_t checksum(const NanoGrid<ValueT> &grid, ChecksumMode mode)
{
GridChecksum cs;
cs(grid, mode);
return cs.checksum();
}
template <typename ValueT>
bool validateChecksum(const NanoGrid<ValueT> &grid, ChecksumMode mode)
{
GridChecksum cs1(grid.checksum(), mode), cs2;
cs2(grid, cs1.mode() );
return cs1 == cs2;
}
template <typename ValueT>
void updateChecksum(NanoGrid<ValueT> &grid, ChecksumMode mode)
{
GridChecksum cs;
cs(grid, mode);
grid.data()->mChecksum = cs.checksum();
}
} // namespace nanovdb
#endif // NANOVDB_GRIDCHECKSUM_H_HAS_BEEN_INCLUDED
ForEach.h
A unified wrapper for tbb::parallel_for and a naive std::thread fallback.
value
ValueT value
Definition GridBuilder.h:1290
GridHandle.h
Defines two classes, a GridRegister the defines the value type (e.g. Double, Float etc) of a NanoVDB ...
NanoVDB.h
Implements a light-weight self-contained VDB data-structure in a single file! In other words,...
NANOVDB_ASSERT
#define NANOVDB_ASSERT(x)
Definition NanoVDB.h:173
NANOVDB_OFFSETOF
#define NANOVDB_OFFSETOF(CLASS, MEMBER)
Definition NanoVDB.h:206
nanovdb::CRC32
Class that computes the Cyclic Redundancy Check (CRC).
Definition GridChecksum.h:75
nanovdb::CRC32::EMPTY
static const HashT EMPTY
Definition GridChecksum.h:95
nanovdb::CRC32::operator()
void operator()(const void *data, size_t byteSize)
Definition GridChecksum.h:111
nanovdb::CRC32::operator()
void operator()(IterT begin, IterT end)
Definition GridChecksum.h:104
nanovdb::CRC32::operator()
void operator()(const T &data)
Definition GridChecksum.h:118
nanovdb::CRC32::checksum
HashT checksum() const
Definition GridChecksum.h:101
nanovdb::CRC32::reset
void reset()
Definition GridChecksum.h:99
nanovdb::CRC32::CRC32
CRC32()
Definition GridChecksum.h:97
nanovdb::GridChecksum
Class that encapsulates two CRC32 checksums, one for the Grid, Tree and Root node meta data and one f...
Definition GridChecksum.h:139
nanovdb::GridChecksum::mode
ChecksumMode mode() const
Definition GridChecksum.h:163
nanovdb::GridChecksum::mCRC
uint32_t mCRC[2]
Definition GridChecksum.h:140
nanovdb::GridChecksum::GridChecksum
GridChecksum(uint64_t checksum, ChecksumMode mode=ChecksumMode::Full)
Definition GridChecksum.h:150
nanovdb::GridChecksum::GridChecksum
GridChecksum(uint32_t head, uint32_t tail)
Definition GridChecksum.h:148
nanovdb::GridChecksum::GridChecksum
GridChecksum()
Definition GridChecksum.h:146
nanovdb::GridChecksum::crc32
uint32_t crc32(int i) const
Definition GridChecksum.h:157
nanovdb::GridChecksum::checksum
uint64_t checksum() const
Definition GridChecksum.h:155
nanovdb::GridChecksum::operator()
void operator()(const NanoGrid< ValueT > &grid, ChecksumMode mode=ChecksumMode::Full)
Definition GridChecksum.h:178
nanovdb::GridChecksum::mChecksum
uint64_t mChecksum
Definition GridChecksum.h:140
nanovdb::GridChecksum::operator==
bool operator==(const GridChecksum &rhs) const
Definition GridChecksum.h:172
nanovdb::GridChecksum::EMPTY
static const uint64_t EMPTY
Definition GridChecksum.h:144
nanovdb::GridChecksum::isEmpty
bool isEmpty() const
Definition GridChecksum.h:161
nanovdb::GridChecksum::operator!=
bool operator!=(const GridChecksum &rhs) const
Definition GridChecksum.h:173
nanovdb::GridChecksum::isFull
bool isFull() const
Definition GridChecksum.h:159
nanovdb::Grid::data
DataType * data()
Definition NanoVDB.h:2575
nanovdb::Grid::checksum
uint64_t checksum() const
Return checksum of the grid buffer.
Definition NanoVDB.h:2715
nanovdb::Grid::tree
const TreeT & tree() const
Return a const reference to the tree.
Definition NanoVDB.h:2598
nanovdb::Grid::memUsage
static uint64_t memUsage()
Return memory usage in bytes for this class only.
Definition NanoVDB.h:2580
nanovdb
Definition NanoVDB.h:208
nanovdb::NanoGrid
Grid< NanoTree< BuildT > > NanoGrid
Definition NanoVDB.h:4563
nanovdb::checksum
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
nanovdb::GridType::End
@ End
Definition NanoVDB.h:263
nanovdb::validateChecksum
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's me...
Definition GridChecksum.h:269
nanovdb::crc32
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
nanovdb::updateChecksum
void updateChecksum(NanoGrid< ValueT > &grid, ChecksumMode mode=ChecksumMode::Default)
Updates the checksum of a grid.
Definition GridChecksum.h:277
nanovdb::ChecksumMode
ChecksumMode
List of different modes for computing for a checksum.
Definition GridChecksum.h:33
nanovdb::ChecksumMode::Partial
@ Partial
Definition GridChecksum.h:34
nanovdb::ChecksumMode::Default
@ Default
Definition GridChecksum.h:36
nanovdb::ChecksumMode::Full
@ Full
Definition GridChecksum.h:35
nanovdb::ChecksumMode::Disable
@ Disable
Definition GridChecksum.h:33
nanovdb::forEach
void forEach(RangeT range, const FuncT &func)
simple wrapper for tbb::parallel_for with a naive std fallback
Definition ForEach.h:40
nanovdb::createNodeManager
NodeManagerHandle< BufferT > createNodeManager(const NanoGrid< BuildT > &grid, const BufferT &buffer=BufferT())
brief Construct a NodeManager and return its handle
Definition NodeManager.h:289
nanovdb::Range1D
Range< 1, size_t > Range1D
Definition Range.h:30
nanovdb::isValid
static bool isValid(const void *p)
return true if the specified pointer is aligned and not NULL
Definition NanoVDB.h:504
NodeManager.h
This class allows for sequential access to nodes in a NanoVDB tree on both the host and device.
nanovdb::GridData
Struct with all the member data of the Grid (useful during serialization of an openvdb grid).
Definition NanoVDB.h:2432