1 // Aleth: Ethereum C++ client, tools and libraries.
2 // Copyright 2014-2019 Aleth Authors.
3 // Licensed under the GNU General Public License, Version 3.
4
5 #include "TrieCommon.h"
6 #include "SHA3.h"
7
8 namespace dev
9 {
10
11 h256 const EmptyTrie = sha3(rlp(""));
12
13 /*
14 * Hex-prefix Notation. First nibble has flags: oddness = 2^0 & termination = 2^1
15 * NOTE: the "termination marker" and "leaf-node" specifier are completely equivalent.
16 * [0,0,1,2,3,4,5] 0x10012345
17 * [0,1,2,3,4,5] 0x00012345
18 * [1,2,3,4,5] 0x112345
19 * [0,0,1,2,3,4] 0x00001234
20 * [0,1,2,3,4] 0x101234
21 * [1,2,3,4] 0x001234
22 * [0,0,1,2,3,4,5,T] 0x30012345
23 * [0,0,1,2,3,4,T] 0x20001234
24 * [0,1,2,3,4,5,T] 0x20012345
25 * [1,2,3,4,5,T] 0x312345
26 * [1,2,3,4,T] 0x201234
27 */
28
hexPrefixEncode(bytes const & _hexVector,bool _leaf,int _begin,int _end)29 std::string hexPrefixEncode(bytes const& _hexVector, bool _leaf, int _begin, int _end)
30 {
31 unsigned begin = _begin;
32 unsigned end = _end < 0 ? _hexVector.size() + 1 + _end : _end;
33 bool odd = ((end - begin) % 2) != 0;
34
35 std::string ret(1, ((_leaf ? 2 : 0) | (odd ? 1 : 0)) * 16);
36 if (odd)
37 {
38 ret[0] |= _hexVector[begin];
39 ++begin;
40 }
41 for (unsigned i = begin; i < end; i += 2)
42 ret += _hexVector[i] * 16 + _hexVector[i + 1];
43 return ret;
44 }
45
hexPrefixEncode(bytesConstRef _data,bool _leaf,int _beginNibble,int _endNibble,unsigned _offset)46 std::string hexPrefixEncode(bytesConstRef _data, bool _leaf, int _beginNibble, int _endNibble, unsigned _offset)
47 {
48 unsigned begin = _beginNibble + _offset;
49 unsigned end = (_endNibble < 0 ? ((int)(_data.size() * 2 - _offset) + 1) + _endNibble : _endNibble) + _offset;
50 bool odd = (end - begin) & 1;
51
52 std::string ret(1, ((_leaf ? 2 : 0) | (odd ? 1 : 0)) * 16);
53 ret.reserve((end - begin) / 2 + 1);
54
55 unsigned d = odd ? 1 : 2;
56 for (auto i = begin; i < end; ++i, ++d)
57 {
58 byte n = nibble(_data, i);
59 if (d & 1) // odd
60 ret.back() |= n; // or the nibble onto the back
61 else
62 ret.push_back(n << 4); // push the nibble on to the back << 4
63 }
64 return ret;
65 }
66
hexPrefixEncode(bytesConstRef _d1,unsigned _o1,bytesConstRef _d2,unsigned _o2,bool _leaf)67 std::string hexPrefixEncode(bytesConstRef _d1, unsigned _o1, bytesConstRef _d2, unsigned _o2, bool _leaf)
68 {
69 unsigned begin1 = _o1;
70 unsigned end1 = _d1.size() * 2;
71 unsigned begin2 = _o2;
72 unsigned end2 = _d2.size() * 2;
73
74 bool odd = (end1 - begin1 + end2 - begin2) & 1;
75
76 std::string ret(1, ((_leaf ? 2 : 0) | (odd ? 1 : 0)) * 16);
77 ret.reserve((end1 - begin1 + end2 - begin2) / 2 + 1);
78
79 unsigned d = odd ? 1 : 2;
80 for (auto i = begin1; i < end1; ++i, ++d)
81 {
82 byte n = nibble(_d1, i);
83 if (d & 1) // odd
84 ret.back() |= n; // or the nibble onto the back
85 else
86 ret.push_back(n << 4); // push the nibble on to the back << 4
87 }
88 for (auto i = begin2; i < end2; ++i, ++d)
89 {
90 byte n = nibble(_d2, i);
91 if (d & 1) // odd
92 ret.back() |= n; // or the nibble onto the back
93 else
94 ret.push_back(n << 4); // push the nibble on to the back << 4
95 }
96 return ret;
97 }
98
uniqueInUse(RLP const & _orig,byte except)99 byte uniqueInUse(RLP const& _orig, byte except)
100 {
101 byte used = 255;
102 for (unsigned i = 0; i < 17; ++i)
103 if (i != except && !_orig[i].isEmpty())
104 {
105 if (used == 255)
106 used = (byte)i;
107 else
108 return 255;
109 }
110 return used;
111 }
112
113 }
114