C++ Distributed Hash Table
infohash.h
1 /*
2  * Copyright (C) 2014-2017 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 
26 #ifndef _WIN32
27 #include <netinet/in.h>
28 #include <netdb.h>
29 #ifdef __ANDROID__
30 typedef uint16_t in_port_t;
31 #endif
32 #else
33 #include <iso646.h>
34 #include <ws2tcpip.h>
35 typedef uint16_t sa_family_t;
36 typedef uint16_t in_port_t;
37 #endif
38 
39 #include <iostream>
40 #include <iomanip>
41 #include <array>
42 #include <vector>
43 #include <algorithm>
44 #include <stdexcept>
45 #include <sstream>
46 #include <cstring>
47 
48 namespace dht {
49 
50 using byte = uint8_t;
51 
52 namespace crypto {
53  OPENDHT_PUBLIC void hash(const uint8_t* data, size_t data_length, uint8_t* hash, size_t hash_length);
54 }
55 
61 template <size_t N>
62 class OPENDHT_PUBLIC Hash {
63 public:
64  using T = std::array<uint8_t, N>;
65  typedef typename T::iterator iterator;
66  typedef typename T::const_iterator const_iterator;
67 
68  Hash () {
69  data_.fill(0);
70  }
71  Hash (const uint8_t* h, size_t data_len) {
72  if (data_len < N)
73  data_.fill(0);
74  else
75  std::copy_n(h, N, data_.begin());
76  }
82  explicit Hash(const std::string& hex);
83 
84  Hash(const msgpack::object& o) {
85  msgpack_unpack(o);
86  }
87 
88  size_t size() const { return data_.size(); }
89  const uint8_t* data() const { return data_.data(); }
90  uint8_t* data() { return data_.data(); }
91  iterator begin() { return data_.begin(); }
92  const_iterator cbegin() const { return data_.cbegin(); }
93  iterator end() { return data_.end(); }
94  const_iterator cend() const { return data_.cend(); }
95 
96  bool operator==(const Hash& h) const {
97  auto a = reinterpret_cast<const uint32_t*>(data_.data());
98  auto b = reinterpret_cast<const uint32_t*>(h.data_.data());
99  constexpr unsigned n = N / sizeof(uint32_t);
100  for (unsigned i=0; i < n; i++)
101  if (a[i] != b[i])
102  return false;
103  return true;
104  }
105  bool operator!=(const Hash& h) const { return !(*this == h); }
106 
107  bool operator<(const Hash& o) const {
108  for(unsigned i = 0; i < N; i++) {
109  if(data_[i] != o.data_[i])
110  return data_[i] < o.data_[i];
111  }
112  return false;
113  }
114 
115  explicit operator bool() const {
116  auto a = reinterpret_cast<const uint32_t*>(data_.data());
117  auto b = reinterpret_cast<const uint32_t*>(data_.data() + N);
118  for (; a != b; a++) {
119  if (*a)
120  return true;
121  }
122  return false;
123  }
124 
125  uint8_t& operator[](size_t index) { return data_[index]; }
126  const uint8_t& operator[](size_t index) const { return data_[index]; }
127 
132  inline int lowbit() const {
133  int i, j;
134  for(i = N-1; i >= 0; i--)
135  if(data_[i] != 0)
136  break;
137  if(i < 0)
138  return -1;
139  for(j = 7; j >= 0; j--)
140  if((data_[i] & (0x80 >> j)) != 0)
141  break;
142  return 8 * i + j;
143  }
144 
149  static inline int cmp(const Hash& id1, const Hash& id2) {
150  return std::memcmp(id1.data_.data(), id2.data_.data(), N);
151  }
152 
154  static inline unsigned
155  commonBits(const Hash& id1, const Hash& id2)
156  {
157  unsigned i, j;
158  uint8_t x;
159  for(i = 0; i < N; i++) {
160  if(id1.data_[i] != id2.data_[i])
161  break;
162  }
163 
164  if(i == N)
165  return 8*N;
166 
167  x = id1.data_[i] ^ id2.data_[i];
168 
169  j = 0;
170  while((x & 0x80) == 0) {
171  x <<= 1;
172  j++;
173  }
174 
175  return 8 * i + j;
176  }
177 
179  int
180  xorCmp(const Hash& id1, const Hash& id2) const
181  {
182  for(unsigned i = 0; i < N; i++) {
183  uint8_t xor1, xor2;
184  if(id1.data_[i] == id2.data_[i])
185  continue;
186  xor1 = id1.data_[i] ^ data_[i];
187  xor2 = id2.data_[i] ^ data_[i];
188  if(xor1 < xor2)
189  return -1;
190  else
191  return 1;
192  }
193  return 0;
194  }
195 
196  bool
197  getBit(unsigned nbit) const
198  {
199  auto& num = *(data_.cbegin()+(nbit/8));
200  unsigned bit = 7 - (nbit % 8);
201  return (num >> bit) & 1;
202  }
203 
204  void
205  setBit(unsigned nbit, bool b)
206  {
207  auto& num = data_[nbit/8];
208  unsigned bit = 7 - (nbit % 8);
209  num ^= (-b ^ num) & (1 << bit);
210  }
211 
212  double toFloat() const {
213  using D = size_t;
214  double v = 0.;
215  for (size_t i = 0; i < std::min<size_t>(N, sizeof(D)-1); i++)
216  v += *(data_.cbegin()+i) / (double)((D)1 << 8*(i+1));
217  return v;
218  }
219 
220  static inline Hash get(const std::string& data) {
221  return get((const uint8_t*)data.data(), data.size());
222  }
223 
224  static inline Hash get(const std::vector<uint8_t>& data) {
225  return get(data.data(), data.size());
226  }
227 
231  static Hash get(const uint8_t* data, size_t data_len)
232  {
233  Hash ret;
234  crypto::hash(data, data_len, ret.data(), N);
235  return ret;
236  }
237 
238  static Hash getRandom();
239 
240  template <size_t M>
241  OPENDHT_PUBLIC friend std::ostream& operator<< (std::ostream& s, const Hash<M>& h);
242 
243  template <size_t M>
244  OPENDHT_PUBLIC friend std::istream& operator>> (std::istream& s, Hash<M>& h);
245 
246  const char* to_c_str() const;
247 
248  std::string toString() const;
249 
250  template <typename Packer>
251  void msgpack_pack(Packer& pk) const
252  {
253  pk.pack_bin(N);
254  pk.pack_bin_body((char*)data_.data(), N);
255  }
256 
257  void msgpack_unpack(msgpack::object o) {
258  if (o.type != msgpack::type::BIN or o.via.bin.size != N)
259  throw msgpack::type_error();
260  std::copy_n(o.via.bin.ptr, N, data_.data());
261  }
262 private:
263  T data_;
264  void fromString(const char*);
265 };
266 
267 #define HASH_LEN 20u
268 using InfoHash = Hash<HASH_LEN>;
269 using h256 = Hash<32>;
270 using PkId = h256;
271 
272 template <size_t N>
273 std::ostream& operator<< (std::ostream& s, const Hash<N>& h)
274 {
275  s.write(h.to_c_str(), N*2);
276  return s;
277 }
278 
279 template <size_t N>
280 std::istream& operator>> (std::istream& s, Hash<N>& h)
281 {
282  std::array<char, h.size()*2> dat;
283  s.exceptions(std::istream::eofbit | std::istream::failbit);
284  s.read(&(*dat.begin()), dat.size());
285  fromString(dat.data());
286  return s;
287 }
288 
289 template <size_t N>
290 Hash<N>::Hash(const std::string& hex) {
291  if (hex.size() < 2*N)
292  data_.fill(0);
293  else
294  fromString(hex.c_str());
295 }
296 
297 template <size_t N>
298 void
299 Hash<N>::fromString(const char* in) {
300  auto hex2bin = [](char c) -> uint8_t {
301  if (c >= 'a' and c <= 'f') return 10 + c - 'a';
302  else if (c >= 'A' and c <= 'F') return 10 + c - 'A';
303  else if (c >= '0' and c <= '9') return c - '0';
304  else throw std::domain_error("not an hex character");
305  };
306  try {
307  for (size_t i=0; i<N; i++)
308  data_[i] = (hex2bin(in[2*i]) << 4) | hex2bin(in[2*i+1]);
309  } catch (const std::domain_error&) {
310  data_.fill(0);
311  }
312 }
313 
314 template <size_t N>
315 Hash<N>
316 Hash<N>::getRandom()
317 {
318  Hash h;
319  crypto::random_device rdev;
320  std::uniform_int_distribution<uint32_t> rand_int;
321  auto a = reinterpret_cast<uint32_t*>(h.data());
322  auto b = reinterpret_cast<uint32_t*>(h.data() + h.size());
323  std::generate(a, b, std::bind(rand_int, std::ref(rdev)));
324  return h;
325 }
326 
327 struct HexMap : public std::array<std::array<char, 2>, 256> {
328  HexMap() {
329  for (size_t i=0; i<size(); i++) {
330  auto& e = (*this)[i];
331  e[0] = hex_digits[(i >> 4) & 0x0F];
332  e[1] = hex_digits[i & 0x0F];
333  }
334  }
335 private:
336  static constexpr const char* hex_digits = "0123456789abcdef";
337 };
338 
339 OPENDHT_PUBLIC extern const HexMap hex_map;
340 
341 template <size_t N>
342 const char*
343 Hash<N>::to_c_str() const
344 {
345  thread_local std::array<char, N*2+1> buf;
346  for (size_t i=0; i<N; i++) {
347  auto b = buf.data()+i*2;
348  const auto& m = hex_map[data_[i]];
349  *((uint16_t*)b) = *((uint16_t*)&m);
350  }
351  return buf.data();
352 }
353 
354 template <size_t N>
355 std::string
356 Hash<N>::toString() const
357 {
358  return std::string(to_c_str(), N*2);
359 }
360 
361 const InfoHash zeroes {};
362 
363 struct OPENDHT_PUBLIC NodeExport {
364  InfoHash id;
365  sockaddr_storage ss;
366  socklen_t sslen;
367 
368  template <typename Packer>
369  void msgpack_pack(Packer& pk) const
370  {
371  pk.pack_map(2);
372  pk.pack(std::string("id"));
373  pk.pack(id);
374  pk.pack(std::string("addr"));
375  pk.pack_bin(sslen);
376  pk.pack_bin_body((char*)&ss, sslen);
377  }
378 
379  void msgpack_unpack(msgpack::object o);
380 
381  OPENDHT_PUBLIC friend std::ostream& operator<< (std::ostream& s, const NodeExport& h);
382 };
383 
384 }
OPENDHT_PUBLIC Blob hash(const Blob &data, size_t hash_length=512/8)
int lowbit() const
Definition: infohash.h:132
static int cmp(const Hash &id1, const Hash &id2)
Definition: infohash.h:149
static unsigned commonBits(const Hash &id1, const Hash &id2)
Definition: infohash.h:155
int xorCmp(const Hash &id1, const Hash &id2) const
Definition: infohash.h:180
Definition: callbacks.h:34