OXYGENHUB
◆ main openmsx / src / utils / TigerTree.hh
3.7 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
1 
/** Incremental Tiger-tree-hash (tth) calculation.
2 
 *
3 
 * This code is based on code from the tigertree project
4 
 *    https://sourceforge.net/projects/tigertree/
5 
 *
6 
 * The main difference is that the original code can only perform a one-shot
7 
 * tth calculation while this code (also) allows incremental tth calculations.
8 
 * When the input data changes, incremental calculation allows to only redo
9 
 * part of the full calculation, so it can be much faster.
10 
 *
11 
 * Here's the copyright notice of the original code (even though the code is
12 
 * almost completely rewritten):
13 
 *
14 
 *     Copyright (C) 2001 Bitzi (aka Bitcollider) Inc. and Gordon Mohr
15 
 *     Released into the public domain by same; permission is explicitly
16 
 *     granted to copy, modify, and use freely.
17 
 *
18 
 *     THE WORK IS PROVIDED "AS IS," AND COMES WITH ABSOLUTELY NO WARRANTY,
19 
 *     EXPRESS OR IMPLIED, TO THE EXTENT PERMITTED BY APPLICABLE LAW,
20 
 *     INCLUDING BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY
21 
 *     OR FITNESS FOR A PARTICULAR PURPOSE.
22 
 *
23 
 *     (PD) 2001 The Bitzi Corporation
24 
 *     Please see file COPYING or http://bitzi.com/publicdomain
25 
 *     for more info.
26 
 */
27
28 
#ifndef TIGERTREE_HH
29 
#define TIGERTREE_HH
30
31 
#include <cstdint>
32 
#include <ctime>
33 
#include <functional>
34 
#include <string>
35
36 
namespace openmsx {
37
38 
struct TigerHash;
39
40 
/** The TigerTree class will query the to-be-hashed data via this abstract
41 
  * interface. This allows to e.g. fetch the data from a file.
42 
  */
43 
class TTData
44 
{
45 
public:
46 
	/** Return the requested portion of the to-be-hashed data block.
47 
	 * Special requirement: it should be allowed to temporarily overwrite
48 
	 * the byte one position before the returned pointer.
49 
	 */
50 
	[[nodiscard]] virtual uint8_t* getData(size_t offset, size_t size) = 0;
51
52 
	/** Because TTH calculation of a large file takes some time (a few
53 
	  * 1/10s for a hard disk image) we try to cache previous calculations.
54 
	  * This method makes sure we don't wrongly reuse the data. E.g. after
55 
	  * it has been modified (by openmsx or even externally).
56 
	  *
57 
	  * Note that the current implementation of the caching is only
58 
	  * suited for files. Refactor this if we ever need some different.
59 
	  */
60 
	[[nodiscard]] virtual bool isCacheStillValid(time_t& time) = 0;
61
62 
protected:
63 
	~TTData() = default;
64 
};
65
66 
struct TTCacheEntry;
67
68 
/** Calculate a tiger-tree-hash.
69 
 * Calculation can be done incrementally, so recalculating the hash after a
70 
 * (small) modification of the input is efficient.
71 
 */
72 
class TigerTree
73 
{
74 
public:
75 
	static constexpr size_t BLOCK_SIZE = 1024;
76
77 
	/** Create TigerTree calculator for the given (abstract) data block
78 
	 * of given size.
79 
	 */
80 
	TigerTree(TTData& data, size_t dataSize, const std::string& name);
81
82 
	/** Calculate the hash value.
83 
	 */
84 
	[[nodiscard]] const TigerHash& calcHash(const std::function<void(size_t, size_t)>& progressCallback);
85
86 
	/** Inform this calculator about changes in the input data. This is
87 
	 * used to (not) skip re-calculations on future calcHash() calls. So
88 
	 * it's crucial this calculator is informed about  _all_ changes in
89 
	 * the input.
90 
	 */
91 
	void notifyChange(size_t offset, size_t len, time_t time);
92
93 
private:
94 
	// functions to navigate in binary tree
95 
	struct Node {
96 
		Node(size_t n_, size_t l_) : n(n_), l(l_) {}
97 
		size_t n; // node number
98 
		size_t l; // level number
99 
	};
100 
	[[nodiscard]] Node getTop() const;
101 
	[[nodiscard]] Node getLeaf(size_t block) const;
102 
	[[nodiscard]] Node getParent(Node node) const;
103 
	[[nodiscard]] Node getLeftChild(Node node) const;
104 
	[[nodiscard]] Node getRightChild(Node node) const;
105
106 
	[[nodiscard]] const TigerHash& calcHash(Node node, const std::function<void(size_t, size_t)>& progressCallback);
107
108 
private:
109 
	TTData& data;
110 
	const size_t dataSize;
111 
	TTCacheEntry& entry;
112 
};
113
114 
} // namespace openmsx
115
116 
#endif