openMSX
TigerTree.cc
Go to the documentation of this file.
1#include "TigerTree.hh"
2#include "tiger.hh"
3#include "Math.hh"
4#include "MemBuffer.hh"
5#include "ranges.hh"
6#include "ScopedAssign.hh"
7#include <cassert>
8#include <map>
9#include <span>
10
11namespace openmsx {
12
14{
17 size_t numNodes;
18 time_t time = -1;
20};
21// Typically contains 0 or 1 element, and only rarely 2 or more. But we need
22// the address of existing elements to remain stable when new elements are
23// inserted. So still use std::map instead of std::vector.
24static std::map<std::pair<size_t, std::string>, TTCacheEntry> ttCache;
25
26[[nodiscard]] static constexpr size_t calcNumNodes(size_t dataSize)
27{
28 auto numBlocks = (dataSize + TigerTree::BLOCK_SIZE - 1) / TigerTree::BLOCK_SIZE;
29 return (numBlocks == 0) ? 1 : 2 * numBlocks - 1;
30}
31
32[[nodiscard]] static TTCacheEntry& getCacheEntry(
33 TTData& data, size_t dataSize, const std::string& name)
34{
35 auto& result = ttCache[std::pair(dataSize, name)];
36 if (!data.isCacheStillValid(result.time)) { // note: has side effect
37 size_t numNodes = calcNumNodes(dataSize);
38 result.hash .resize(numNodes);
39 result.valid.resize(numNodes);
40 result.numNodes = numNodes;
41 ranges::fill(std::span{result.valid.data(), numNodes}, false); // all invalid
42 result.numNodesValid = 0;
43 }
44 return result;
45}
46
47TigerTree::TigerTree(TTData& data_, size_t dataSize_, const std::string& name)
48 : data(data_)
49 , dataSize(dataSize_)
50 , entry(getCacheEntry(data, dataSize, name))
51{
52}
53
54const TigerHash& TigerTree::calcHash(const std::function<void(size_t, size_t)>& progressCallback)
55{
56 return calcHash(getTop(), progressCallback);
57}
58
59void TigerTree::notifyChange(size_t offset, size_t len, time_t time)
60{
61 entry.time = time;
62
63 assert((offset + len) <= dataSize);
64 if (len == 0) return;
65
66 if (entry.valid[getTop().n]) {
67 entry.valid[getTop().n] = false; // set sentinel
68 entry.numNodesValid--;
69 }
70 auto first = offset / BLOCK_SIZE;
71 auto last = (offset + len - 1) / BLOCK_SIZE;
72 assert(first <= last); // requires len != 0
73 do {
74 auto node = getLeaf(first);
75 while (entry.valid[node.n]) {
76 entry.valid[node.n] = false;
77 entry.numNodesValid--;
78 node = getParent(node);
79 }
80 } while (++first <= last);
81}
82
83const TigerHash& TigerTree::calcHash(Node node, const std::function<void(size_t, size_t)>& progressCallback)
84{
85 auto n = node.n;
86 if (!entry.valid[n]) {
87 if (n & 1) {
88 // interior node
89 auto left = getLeftChild (node);
90 auto right = getRightChild(node);
91 const auto& h1 = calcHash(left, progressCallback);
92 const auto& h2 = calcHash(right, progressCallback);
93 tiger_int(h1, h2, entry.hash[n]);
94 } else {
95 // leaf node
96 size_t b = n * (BLOCK_SIZE / 2);
97 size_t l = dataSize - b;
98
99 if (l >= BLOCK_SIZE) {
100 auto* d = data.getData(b, BLOCK_SIZE);
101 tiger_leaf(std::span{d, BLOCK_SIZE}, entry.hash[n]);
102 } else {
103 // partial last block
104 auto* d = data.getData(b, l);
105 auto sa = ScopedAssign(d[-1], uint8_t(0));
106 tiger(std::span{d - 1, l + 1}, entry.hash[n]);
107 }
108 }
109 entry.valid[n] = true;
110 entry.numNodesValid++;
111 if (progressCallback) {
112 progressCallback(entry.numNodesValid, entry.numNodes);
113 }
114 }
115 return entry.hash[n];
116}
117
118
119// The TigerTree::nodes member variable stores a linearized binary tree. The
120// linearization is done like in this example:
121//
122// 7 (level = 8)
123// ----/ \---- .
124// 3 11 (level = 4)
125// / \ / \ .
126// 1 5 9 | (level = 2)
127// / \ / \ / \ | .
128// 0 2 4 6 8 10 12 (level = 1)
129//
130// All leaf nodes are given even node values (0, 2, 4, .., 12). Leaf nodes have
131// level=1. At the next level (level=2) leaf nodes are pair-wise combined in
132// internal nodes. So nodes 0 and 2 are combined in node 1, 4+6->5 and 8+10->9.
133// Leaf-node 12 cannot be paired (there is no leaf-node 14), so there's no
134// corresponding node at level=2. The next level is level=4 (level values
135// double for each higher level). At level=4 node 3 is the combination of 1 and
136// 5 and 9+12->11. Note that 11 is a combination of two nodes from a different
137// (lower) level. And finally, node 7 at level=8 combines 3+11.
138//
139// The following methods navigate in this tree.
140
141TigerTree::Node TigerTree::getTop() const
142{
143 auto n = Math::floodRight(entry.numNodes / 2);
144 return {n, n + 1};
145}
146
147TigerTree::Node TigerTree::getLeaf(size_t block) const
148{
149 assert((2 * block) < entry.numNodes);
150 return {2 * block, 1};
151}
152
153TigerTree::Node TigerTree::getParent(Node node) const
154{
155 assert(node.n < entry.numNodes);
156 do {
157 node.n = (node.n & ~(2 * node.l)) + node.l;
158 node.l *= 2;
159 } while (node.n >= entry.numNodes);
160 return node;
161}
162
163TigerTree::Node TigerTree::getLeftChild(Node node) const
164{
165 assert(node.n < entry.numNodes);
166 assert(node.l > 1);
167 node.l /= 2;
168 node.n -= node.l;
169 return node;
170}
171
172TigerTree::Node TigerTree::getRightChild(Node node) const
173{
174 assert(node.n < entry.numNodes);
175 while (true) {
176 assert(node.l > 1);
177 node.l /= 2;
178 auto r = node.n + node.l;
179 if (r < entry.numNodes) return {r, node.l};
180 }
181}
182
183} // namespace openmsx
Assign new value to some variable and restore the original value when this object goes out of scope.
Definition: ScopedAssign.hh:8
This class manages the lifetime of a block of memory.
Definition: MemBuffer.hh:29
The TigerTree class will query the to-be-hashed data via this abstract interface.
Definition: TigerTree.hh:44
const TigerHash & calcHash(const std::function< void(size_t, size_t)> &progressCallback)
Calculate the hash value.
Definition: TigerTree.cc:54
TigerTree(TTData &data, size_t dataSize, const std::string &name)
Create TigerTree calculator for the given (abstract) data block of given size.
Definition: TigerTree.cc:47
void notifyChange(size_t offset, size_t len, time_t time)
Inform this calculator about changes in the input data.
Definition: TigerTree.cc:59
static constexpr size_t BLOCK_SIZE
Definition: TigerTree.hh:75
constexpr auto floodRight(std::unsigned_integral auto x) noexcept
Returns the smallest number of the form 2^n-1 that is greater or equal to the given number.
Definition: Math.hh:31
This file implemented 3 utility functions:
Definition: Autofire.cc:9
void tiger(std::span< const uint8_t > input, TigerHash &result)
Generic function to calculate a tiger-hash.
Definition: tiger.cc:680
void tiger_int(const TigerHash &h0, const TigerHash &h1, TigerHash &result)
Use for tiger-tree internal node hash calculations.
Definition: tiger.cc:711
void tiger_leaf(std::span< uint8_t > data, TigerHash &result)
Use for tiger-tree leaf node hash calculations.
Definition: tiger.cc:731
constexpr void fill(ForwardRange &&range, const T &value)
Definition: ranges.hh:287
MemBuffer< TigerHash > hash
Definition: TigerTree.cc:15
MemBuffer< bool > valid
Definition: TigerTree.cc:16
This struct represents the result of a tiger-hash.
Definition: tiger.hh:30