My Project 3.2.0
C++ Distributed Hash Table
Loading...
Searching...
No Matches
infohash.h
1/*
2 * Copyright (C) 2014-2023 Savoir-faire Linux Inc.
3 * Author : Adrien Béraud <adrien.beraud@savoirfairelinux.com>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <https://www.gnu.org/licenses/>.
17 */
18
19#pragma once
20
21#include "def.h"
22#include "rng.h"
23
24#include <msgpack.hpp>
25#include <fmt/core.h>
26
27#ifndef _WIN32
28#include <netinet/in.h>
29#include <netdb.h>
30#ifdef __ANDROID__
31typedef uint16_t in_port_t;
32#endif
33#else
34#include <iso646.h>
35#include <ws2tcpip.h>
36typedef uint16_t sa_family_t;
37typedef uint16_t in_port_t;
38#endif
39
40#include <iostream>
41#include <iomanip>
42#include <array>
43#include <vector>
44#include <string_view>
45#include <algorithm>
46#include <stdexcept>
47#include <sstream>
48
49#include <cstring>
50#include <cstddef>
51
52namespace dht {
53
54using byte = uint8_t;
55
56namespace crypto {
57 OPENDHT_PUBLIC void hash(const uint8_t* data, size_t data_length, uint8_t* hash, size_t hash_length);
58}
59
65template <size_t N>
66class OPENDHT_PUBLIC Hash {
67public:
68 using T = std::array<uint8_t, N>;
69 typedef typename T::iterator iterator;
70 typedef typename T::const_iterator const_iterator;
71
72 Hash() noexcept {
73 data_.fill(0);
74 }
75 Hash(const uint8_t* h, size_t data_len) {
76 if (data_len < N)
77 data_.fill(0);
78 else
79 std::copy_n(h, N, data_.begin());
80 }
86 explicit Hash(std::string_view hex) {
87 if (hex.size() < 2*N)
88 data_.fill(0);
89 else
90 fromString(hex.data());
91 }
92
93 Hash(const msgpack::object& o) {
94 msgpack_unpack(o);
95 }
96
97 static constexpr size_t size() noexcept { return N; }
98 const uint8_t* data() const { return data_.data(); }
99 uint8_t* data() { return data_.data(); }
100 iterator begin() { return data_.begin(); }
101 const_iterator cbegin() const { return data_.cbegin(); }
102 iterator end() { return data_.end(); }
103 const_iterator cend() const { return data_.cend(); }
104
105 static constexpr inline Hash zero() noexcept { return Hash{}; }
106
107 bool operator==(const Hash& h) const {
108 return data_ == h.data_;
109 }
110 bool operator!=(const Hash& h) const { return !(*this == h); }
111
112 bool operator<(const Hash& o) const {
113 for(unsigned i = 0; i < N; i++) {
114 if(data_[i] != o.data_[i])
115 return data_[i] < o.data_[i];
116 }
117 return false;
118 }
119
120 Hash operator^(const Hash& o) const {
121 Hash result;
122 for(auto i = 0u; i < N; i++) {
123 result[i] = data_[i] ^ o.data_[i];
124 }
125 return result;
126 }
127
128 explicit operator bool() const {
129 auto a = reinterpret_cast<const uint32_t*>(data_.data());
130 auto b = reinterpret_cast<const uint32_t*>(data_.data() + N);
131 for (; a != b; a++) {
132 if (*a)
133 return true;
134 }
135 return false;
136 }
137
138 uint8_t& operator[](size_t index) { return data_[index]; }
139 const uint8_t& operator[](size_t index) const { return data_[index]; }
140
145 inline int lowbit() const {
146 int i, j;
147 for(i = N-1; i >= 0; i--)
148 if(data_[i] != 0)
149 break;
150 if(i < 0)
151 return -1;
152 for(j = 7; j >= 0; j--)
153 if((data_[i] & (0x80 >> j)) != 0)
154 break;
155 return 8 * i + j;
156 }
157
158 static inline int cmp(const Hash& id1, const Hash& id2) {
159 return std::memcmp(id1.data_.data(), id2.data_.data(), N);
160 }
161
163 static inline unsigned
164 commonBits(const Hash& id1, const Hash& id2)
165 {
166 unsigned i, j;
167 uint8_t x;
168 for(i = 0; i < N; i++) {
169 if(id1.data_[i] != id2.data_[i])
170 break;
171 }
172
173 if(i == N)
174 return 8*N;
175
176 x = id1.data_[i] ^ id2.data_[i];
177
178 j = 0;
179 while((x & 0x80) == 0) {
180 x <<= 1;
181 j++;
182 }
183
184 return 8 * i + j;
185 }
186
188 int
189 xorCmp(const Hash& id1, const Hash& id2) const
190 {
191 for (unsigned i = 0; i < N; i++) {
192 if(id1.data_[i] == id2.data_[i])
193 continue;
194 uint8_t xor1 = id1.data_[i] ^ data_[i];
195 uint8_t xor2 = id2.data_[i] ^ data_[i];
196 return (xor1 < xor2) ? -1 : 1;
197 }
198 return 0;
199 }
200
201 bool
202 getBit(unsigned nbit) const
203 {
204 auto& num = *(data_.cbegin()+(nbit/8));
205 unsigned bit = 7 - (nbit % 8);
206 return (num >> bit) & 1;
207 }
208
209 void
210 setBit(unsigned nbit, bool b)
211 {
212 auto& num = data_[nbit/8];
213 unsigned bit = 7 - (nbit % 8);
214 num ^= (-b ^ num) & (1 << bit);
215 }
216
217 double toFloat() const {
218 using D = size_t;
219 double v = 0.;
220 for (size_t i = 0; i < std::min<size_t>(N, sizeof(D)-1); i++)
221 v += *(data_.cbegin()+i) / (double)((D)1 << 8*(i+1));
222 return v;
223 }
224
225 static inline Hash get(std::string_view data) {
226 return get((const uint8_t*)data.data(), data.size());
227 }
228
229 static inline Hash get(const std::vector<uint8_t>& data) {
230 return get(data.data(), data.size());
231 }
232
233 template <size_t H>
234 static Hash get(const Hash<H>& o) {
235 return get(o.data(), o.size());
236 }
237
241 static Hash get(const uint8_t* data, size_t data_len)
242 {
243 Hash ret;
244 crypto::hash(data, data_len, ret.data(), N);
245 return ret;
246 }
247
248 static Hash getRandom();
249
250 template <typename Rd>
251 static Hash getRandom(Rd&);
252
253 template <size_t M>
254 OPENDHT_PUBLIC friend std::ostream& operator<< (std::ostream& s, const Hash<M>& h);
255
256 template <size_t M>
257 OPENDHT_PUBLIC friend std::istream& operator>> (std::istream& s, Hash<M>& h);
258
260 std::string_view to_view() const { return std::string_view(to_c_str(), N*2); }
261 const char* to_c_str() const;
262
263 std::string toString() const;
264
265 template <typename Packer>
266 void msgpack_pack(Packer& pk) const
267 {
268 pk.pack_bin(N);
269 pk.pack_bin_body((char*)data_.data(), N);
270 }
271
272 void msgpack_unpack(msgpack::object o) {
273 if (o.type != msgpack::type::BIN or o.via.bin.size != N)
274 throw msgpack::type_error();
275 std::copy_n(o.via.bin.ptr, N, data_.data());
276 }
277private:
278 T data_;
279 void fromString(const char*);
280};
281
282#define HASH_LEN 20u
283using InfoHash = Hash<HASH_LEN>;
284using h256 = Hash<32>;
285using PkId = h256;
286
287template <size_t N>
288std::ostream& operator<< (std::ostream& s, const Hash<N>& h)
289{
290 s.write(h.to_c_str(), N*2);
291 return s;
292}
293
294template <size_t N>
295std::istream& operator>> (std::istream& s, Hash<N>& h)
296{
297 std::array<char, h.size()*2> dat;
298 s.exceptions(std::istream::eofbit | std::istream::failbit);
299 s.read(&(*dat.begin()), dat.size());
300 fromString(dat.data());
301 return s;
302}
303
304template <size_t N>
305void
306Hash<N>::fromString(const char* in) {
307 auto hex2bin = [](char c) -> uint8_t {
308 if (c >= 'a' and c <= 'f') return 10 + c - 'a';
309 else if (c >= 'A' and c <= 'F') return 10 + c - 'A';
310 else if (c >= '0' and c <= '9') return c - '0';
311 else throw std::domain_error("not an hex character");
312 };
313 try {
314 for (size_t i=0; i<N; i++)
315 data_[i] = (hex2bin(in[2*i]) << 4) | hex2bin(in[2*i+1]);
316 } catch (const std::domain_error&) {
317 data_.fill(0);
318 }
319}
320
321template <size_t N>
323Hash<N>::getRandom()
324{
325 Hash h;
326 std::random_device rdev;
327 std::uniform_int_distribution<uint32_t> rand_int;
328 auto a = reinterpret_cast<uint32_t*>(h.data());
329 auto b = reinterpret_cast<uint32_t*>(h.data() + h.size());
330 std::generate(a, b, std::bind(rand_int, std::ref(rdev)));
331 return h;
332}
333
334template <size_t N>
335template <typename Rd>
337Hash<N>::getRandom(Rd& rdev)
338{
339 Hash h;
340 std::uniform_int_distribution<uint32_t> rand_int;
341 auto a = reinterpret_cast<uint32_t*>(h.data());
342 auto b = reinterpret_cast<uint32_t*>(h.data() + h.size());
343 std::generate(a, b, std::bind(rand_int, std::ref(rdev)));
344 return h;
345}
346
347struct alignas(std::max_align_t) HexMap : public std::array<std::array<char, 2>, 256> {
348 HexMap() {
349 for (size_t i=0; i<size(); i++) {
350 auto& e = (*this)[i];
351 e[0] = hex_digits[(i >> 4) & 0x0F];
352 e[1] = hex_digits[i & 0x0F];
353 }
354 }
355private:
356 static constexpr const char* hex_digits = "0123456789abcdef";
357};
358
359OPENDHT_PUBLIC extern const HexMap hex_map;
360
361inline std::string
362toHex(const uint8_t* data, size_t size) {
363 std::string ret(size * 2, '\0');
364 for (size_t i=0; i<size; i++) {
365 auto b = ret.data()+i*2;
366 const auto& m = hex_map[data[i]];
367 *((uint16_t*)b) = *((uint16_t*)&m);
368 }
369 return ret;
370}
371
372inline std::string
373toHex(const std::vector<uint8_t>& data) {
374 return toHex(data.data(), data.size());
375}
376
377template <size_t N>
378const char*
379Hash<N>::to_c_str() const
380{
381 alignas(std::max_align_t) thread_local std::array<char, N*2+1> buf;
382 for (size_t i=0; i<N; i++) {
383 auto b = buf.data()+i*2;
384 const auto& m = hex_map[data_[i]];
385 *((uint16_t*)b) = *((uint16_t*)&m);
386 }
387 return buf.data();
388}
389
390template <size_t N>
391std::string
392Hash<N>::toString() const
393{
394 return std::string(to_c_str(), N*2);
395}
396
397}
398
399template <size_t N>
400struct fmt::formatter<dht::Hash<N>>: formatter<string_view> {
401 constexpr auto format(const dht::Hash<N>& c, format_context& ctx) const {
402 return formatter<string_view>::format(c.to_view(), ctx);
403 }
404};
static unsigned commonBits(const Hash &id1, const Hash &id2)
Definition infohash.h:164
Hash(std::string_view hex)
Definition infohash.h:86
static Hash get(const uint8_t *data, size_t data_len)
Definition infohash.h:241
int lowbit() const
Definition infohash.h:145
std::string_view to_view() const
Definition infohash.h:260
int xorCmp(const Hash &id1, const Hash &id2) const
Definition infohash.h:189
OPENDHT_PUBLIC Blob hash(const Blob &data, size_t hash_length=512/8)