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