Changeset View
Changeset View
Standalone View
Standalone View
src/dht/key.cpp
Context not available. | |||||
22 | #include <stdlib.h> | 22 | #include <stdlib.h> | ||
---|---|---|---|---|---|
23 | #include <algorithm> | 23 | #include <algorithm> | ||
24 | #include <util/constants.h> | 24 | #include <util/constants.h> | ||
25 | #include <endian.h> | ||||
25 | 26 | | |||
26 | using namespace bt; | 27 | using namespace bt; | ||
27 | 28 | | |||
Context not available. | |||||
35 | { | 36 | { | ||
36 | } | 37 | } | ||
37 | 38 | | |||
38 | Key::Key(const Uint8* d) : bt::SHA1Hash(d) | 39 | Key::Key(const bt::Uint8* d) : bt::SHA1Hash(d) | ||
39 | { | 40 | { | ||
40 | } | 41 | } | ||
41 | 42 | | |||
42 | Key::Key(const QByteArray & ba) | 43 | Key::Key(const QByteArray & ba) | ||
43 | { | 44 | { | ||
44 | for (int i = 0;i < 20 && i < ba.size();i++) | 45 | memcpy(hash, ba.data(), std::min(20, ba.size())); | ||
45 | hash[i] = ba[i]; | | |||
46 | } | 46 | } | ||
47 | 47 | | |||
48 | Key::~Key() | 48 | Key::~Key() | ||
Context not available. | |||||
60 | 60 | | |||
61 | bool Key::operator < (const Key & other) const | 61 | bool Key::operator < (const Key & other) const | ||
62 | { | 62 | { | ||
63 | for (int i = 0;i < 20;i++) | 63 | return memcmp(hash, other.hash, 20) < 0; | ||
64 | { | | |||
65 | if (hash[i] < other.hash[i]) | | |||
66 | return true; | | |||
67 | else if (hash[i] > other.hash[i]) | | |||
68 | return false; | | |||
69 | } | | |||
70 | return false; | | |||
71 | } | 64 | } | ||
72 | 65 | | |||
73 | bool Key::operator <= (const Key & other) const | 66 | bool Key::operator <= (const Key & other) const | ||
74 | { | 67 | { | ||
75 | return operator < (other) || operator == (other); | 68 | return memcmp(hash, other.hash, 20) <= 0; | ||
76 | } | 69 | } | ||
77 | 70 | | |||
78 | bool Key::operator > (const Key & other) const | 71 | bool Key::operator > (const Key & other) const | ||
79 | { | 72 | { | ||
80 | for (int i = 0;i < 20;i++) | 73 | return memcmp(hash, other.hash, 20) > 0; | ||
81 | { | | |||
82 | if (hash[i] < other.hash[i]) | | |||
83 | return false; | | |||
84 | else if (hash[i] > other.hash[i]) | | |||
85 | return true; | | |||
86 | } | | |||
87 | return false; | | |||
88 | } | 74 | } | ||
89 | 75 | | |||
90 | bool Key::operator >= (const Key & other) const | 76 | bool Key::operator >= (const Key & other) const | ||
91 | { | 77 | { | ||
92 | return operator > (other) || operator == (other); | 78 | return memcmp(hash, other.hash, 20) >= 0; | ||
93 | } | 79 | } | ||
94 | 80 | | |||
95 | Key operator + (const dht::Key& a, const dht::Key& b) | 81 | Key operator + (const dht::Key& a, const dht::Key& b) | ||
96 | { | 82 | { | ||
97 | bt::Uint8 result[20]; | 83 | dht::Key result; | ||
98 | bool carry = false; | 84 | bt::Uint64 sum = 0; | ||
99 | const bt::Uint8* ad = a.getData(); | 85 | | ||
100 | const bt::Uint8* bd = b.getData(); | 86 | for (int i = 4; i >= 0; i--) { | ||
101 | for (int i = 19;i >= 0;i--) | 87 | sum += (bt::Uint64) htobe32(a.hash[i]) + htobe32(b.hash[i]); | ||
102 | { | 88 | result.hash[i] = htobe32(sum & 0xFFFFFFFF); | ||
103 | unsigned int r = ad[i] + bd[i] + (carry ? 1 : 0); | 89 | sum = sum >> 32; | ||
104 | if (r > 255) | | |||
105 | { | | |||
106 | result[i] = r & 0xFF; | | |||
107 | carry = true; | | |||
108 | } | | |||
109 | else | | |||
110 | { | | |||
111 | result[i] = r; | | |||
112 | carry = false; | | |||
113 | } | | |||
114 | } | 90 | } | ||
115 | 91 | | |||
116 | return dht::Key(result); | 92 | return result; | ||
117 | } | 93 | } | ||
118 | 94 | | |||
119 | Key operator + (const Key & a, bt::Uint8 value) | 95 | Key operator + (const Key & a, bt::Uint8 value) | ||
120 | { | 96 | { | ||
121 | bt::Uint8 b[20]; | 97 | dht::Key result(a); | ||
122 | memset(b, 0, 20); | 98 | | ||
123 | b[19] = value; | 99 | bt::Uint64 sum = value; | ||
124 | return a + Key(b); | 100 | for (int i = 4; i >= 0 && sum != 0; i--) { | ||
101 | sum += htobe32(result.hash[i]); | ||||
102 | result.hash[i] = htobe32(sum & 0xFFFFFFFF); | ||||
103 | sum = sum >> 32; | ||||
104 | } | ||||
105 | | ||||
106 | return result; | ||||
125 | } | 107 | } | ||
126 | 108 | | |||
127 | Key Key::operator / (int value) const | 109 | Key Key::operator / (int value) const | ||
128 | { | 110 | { | ||
129 | bt::Uint8 result[20]; | 111 | dht::Key result; | ||
130 | bt::Uint8 remainder = 0; | 112 | bt::Uint64 remainder = 0; | ||
131 | 113 | | |||
132 | for (int i = 0; i < 20; i++) | 114 | for (int i = 0; i < 5; i++) { | ||
133 | { | 115 | const bt::Uint32 h = htobe32(hash[i]); | ||
134 | bt::Uint8 d = (hash[i] + (remainder << 8)) / value; | 116 | result.hash[i] = htobe32( ( h + remainder) / value ); | ||
135 | remainder = (hash[i] + (remainder << 8)) % value; | 117 | remainder = ((h + remainder) % value) << 32; | ||
136 | result[i] = d; | | |||
137 | } | 118 | } | ||
138 | 119 | | |||
139 | return dht::Key(result); | 120 | return result; | ||
140 | } | 121 | } | ||
141 | 122 | | |||
142 | 123 | | |||
Context not available. | |||||
149 | { | 130 | { | ||
150 | srand(time(0)); | 131 | srand(time(0)); | ||
151 | Key k; | 132 | Key k; | ||
152 | for (int i = 0;i < 20;i++) | 133 | Uint16* h = (Uint16*) k.hash; | ||
134 | for (int i = 0; i < 10; i++) | ||||
153 | { | 135 | { | ||
154 | k.hash[i] = (Uint8)rand() % 0xFF; | 136 | h[i] = std::rand() & 0xFFFF; // rand() between 0 and only 2^31 | ||
155 | } | 137 | } | ||
156 | return k; | 138 | return k; | ||
157 | } | 139 | } | ||
158 | 140 | | |||
159 | Key operator - (const Key & a, const Key & b) | 141 | Key operator - (const Key & a, const Key & b) | ||
160 | { | 142 | { | ||
161 | bt::Uint8 result[20]; | 143 | dht::Key result; | ||
162 | bool carry = false; | 144 | bt::Uint32 carry = 0; | ||
163 | const bt::Uint8* ad = a.getData(); | 145 | for (int i = 4; i >= 0; i--) | ||
164 | const bt::Uint8* bd = b.getData(); | | |||
165 | for (int i = 19;i >= 0;i--) | | |||
166 | { | 146 | { | ||
167 | if (ad[i] >= bd[i]) | 147 | const bt::Uint32 a32 = htobe32(a.hash[i]); | ||
148 | const bt::Uint32 b32 = htobe32(b.hash[i]); | ||||
149 | if (a32 >= (( bt::Uint64)b32 + carry) ) | ||||
168 | { | 150 | { | ||
169 | result[i] = ad[i] - bd[i]; | 151 | result.hash[i] = htobe32(a32 - b32 - carry); | ||
170 | if (carry) | 152 | carry = 0; | ||
171 | { | 153 | } else { | ||
172 | if (result[i] == 0) | 154 | const bt::Uint64 max = 0xFFFFFFFF + 1; | ||
173 | { | 155 | result.hash[i] = htobe32( (bt::Uint32) (max - (b32 - a32) - carry) ); | ||
174 | result[i] = 0xFF; | 156 | carry = 1; | ||
175 | carry = true; | | |||
176 | } | | |||
177 | else | | |||
178 | { | | |||
179 | result[i] -= 1; | | |||
180 | carry = false; | | |||
181 | } | | |||
182 | } | | |||
183 | } | | |||
184 | else | | |||
185 | { | | |||
186 | result[i] = 256 - (bd[i] - ad[i]); | | |||
187 | if (carry) | | |||
188 | result[i] -= 1; | | |||
189 | carry = true; | | |||
190 | } | 157 | } | ||
191 | } | 158 | } | ||
192 | 159 | | |||
193 | return dht::Key(result); | 160 | return result; | ||
194 | } | 161 | } | ||
195 | 162 | | |||
196 | Key Key::mid(const dht::Key& a, const dht::Key& b) | 163 | Key Key::mid(const dht::Key& a, const dht::Key& b) | ||
Context not available. | |||||
200 | else | 167 | else | ||
201 | return b + (a - b) / 2; | 168 | return b + (a - b) / 2; | ||
202 | } | 169 | } | ||
170 | | ||||
171 | #define rep4(v) v, v, v, v | ||||
172 | #define rep20(v) rep4(v), rep4(v), rep4(v), rep4(v), rep4(v) | ||||
173 | const bt::Uint8 val_max[20] = {rep20(0xFF)}; | ||||
174 | const bt::Uint8 val_min[20] = {rep20(0x00)}; | ||||
203 | 175 | | |||
204 | Key Key::max() | 176 | Key Key::max() | ||
205 | { | 177 | { | ||
206 | bt::Uint8 result[20]; | 178 | return Key(val_max); | ||
207 | std::fill(result, result + 20, 0xFF); | | |||
208 | return Key(result); | | |||
209 | } | 179 | } | ||
210 | 180 | | |||
211 | Key Key::min() | 181 | Key Key::min() | ||
212 | { | 182 | { | ||
213 | bt::Uint8 result[20]; | 183 | return Key(val_min); | ||
214 | std::fill(result, result + 20, 0x0); | | |||
215 | return Key(result); | | |||
216 | } | 184 | } | ||
217 | 185 | | |||
218 | 186 | | |||
Context not available. |