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 <map>
6 #include <cstring>
7 #include <cassert>
8 
9 namespace openmsx {
10 
12 {
15  size_t numNodes;
16  time_t time = -1;
17  size_t numNodesValid;
18 };
19 // Typically contains 0 or 1 element, and only rarely 2 or more. But we need
20 // the address of existing elements to remain stable when new elements are
21 // inserted. So still use std::map instead of std::vector.
22 static std::map<std::pair<size_t, std::string>, TTCacheEntry> ttCache;
23 
24 [[nodiscard]] static constexpr size_t calcNumNodes(size_t dataSize)
25 {
26  auto numBlocks = (dataSize + TigerTree::BLOCK_SIZE - 1) / TigerTree::BLOCK_SIZE;
27  return (numBlocks == 0) ? 1 : 2 * numBlocks - 1;
28 }
29 
30 [[nodiscard]] static TTCacheEntry& getCacheEntry(
31  TTData& data, size_t dataSize, const std::string& name)
32 {
33  auto& result = ttCache[std::pair(dataSize, name)];
34  if (!data.isCacheStillValid(result.time)) { // note: has side effect
35  size_t numNodes = calcNumNodes(dataSize);
36  result.hash .resize(numNodes);
37  result.valid.resize(numNodes);
38  result.numNodes = numNodes;
39  memset(result.valid.data(), 0, numNodes); // all invalid
40  result.numNodesValid = 0;
41  }
42  return result;
43 }
44 
45 TigerTree::TigerTree(TTData& data_, size_t dataSize_, const std::string& name)
46  : data(data_)
47  , dataSize(dataSize_)
48  , entry(getCacheEntry(data, dataSize, name))
49 {
50 }
51 
52 const TigerHash& TigerTree::calcHash(const std::function<void(size_t, size_t)>& progressCallback)
53 {
54  return calcHash(getTop(), progressCallback);
55 }
56 
57 void TigerTree::notifyChange(size_t offset, size_t len, time_t time)
58 {
59  entry.time = time;
60 
61  assert((offset + len) <= dataSize);
62  if (len == 0) return;
63 
64  if (entry.valid[getTop().n]) {
65  entry.valid[getTop().n] = false; // set sentinel
66  entry.numNodesValid--;
67  }
68  auto first = offset / BLOCK_SIZE;
69  auto last = (offset + len - 1) / BLOCK_SIZE;
70  assert(first <= last); // requires len != 0
71  do {
72  auto node = getLeaf(first);
73  while (entry.valid[node.n]) {
74  entry.valid[node.n] = false;
75  entry.numNodesValid--;
76  node = getParent(node);
77  }
78  } while (++first <= last);
79 }
80 
81 const TigerHash& TigerTree::calcHash(Node node, const std::function<void(size_t, size_t)>& progressCallback)
82 {
83  auto n = node.n;
84  if (!entry.valid[n]) {
85  if (n & 1) {
86  // interior node
87  auto left = getLeftChild (node);
88  auto right = getRightChild(node);
89  const auto& h1 = calcHash(left, progressCallback);
90  const auto& h2 = calcHash(right, progressCallback);
91  tiger_int(h1, h2, entry.hash[n]);
92  } else {
93  // leaf node
94  size_t b = n * (BLOCK_SIZE / 2);
95  size_t l = dataSize - b;
96 
97  if (l >= BLOCK_SIZE) {
98  auto* d = data.getData(b, BLOCK_SIZE);
99  tiger_leaf(d, entry.hash[n]);
100  } else {
101  // partial last block
102  auto* d = data.getData(b, l);
103  auto backup = d[-1];
104  d[-1] = 0;
105  tiger(d - 1, l + 1, entry.hash[n]);
106  d[-1] = backup;
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 
141 TigerTree::Node TigerTree::getTop() const
142 {
143  auto n = Math::floodRight(entry.numNodes / 2);
144  return {n, n + 1};
145 }
146 
147 TigerTree::Node TigerTree::getLeaf(size_t block) const
148 {
149  assert((2 * block) < entry.numNodes);
150  return {2 * block, 1};
151 }
152 
153 TigerTree::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 
163 TigerTree::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 
172 TigerTree::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
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:52
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:45
void notifyChange(size_t offset, size_t len, time_t time)
Inform this calculator about changes in the input data.
Definition: TigerTree.cc:57
static constexpr size_t BLOCK_SIZE
Definition: TigerTree.hh:75
constexpr T floodRight(T x) noexcept
Returns the smallest number of the form 2^n-1 that is greater or equal to the given number.
Definition: Math.hh:69
This file implemented 3 utility functions:
Definition: Autofire.cc:9
void tiger(const uint8_t *str, size_t length, TigerHash &result)
Generic function to calculate a tiger-hash.
Definition: tiger.cc:675
void tiger_int(const TigerHash &h0, const TigerHash &h1, TigerHash &result)
Use for tiger-tree internal node hash calculations.
Definition: tiger.cc:713
void tiger_leaf(uint8_t data[1024], TigerHash &result)
Use for tiger-tree leaf node hash calculations.
Definition: tiger.cc:733
MemBuffer< TigerHash > hash
Definition: TigerTree.cc:13
MemBuffer< bool > valid
Definition: TigerTree.cc:14
This struct represents the result of a tiger-hash.
Definition: tiger.hh:28