ROSE  0.11.2.0
Combinatorics.h
1 #ifndef ROSE_Combinatorics_H
2 #define ROSE_Combinatorics_H
3
4 #include <rosePublicConfig.h>
5
6 #include <boost/shared_ptr.hpp>
7
8 #include <algorithm>
9 #include <cassert>
10 #include <istream>
11 #include <list>
12 #include <ostream>
13 #include <RoseException.h>
14 #include <rose_override.h>
15 #include <Sawyer/Assert.h>
16 #include <Sawyer/Synchronization.h>
17 #include <stdexcept>
18 #include <stdint.h>
19 #include <string>
20 #include <vector>
21
22 #ifdef ROSE_HAVE_LIBGCRYPT
23 #include <gcrypt.h>
24 #endif
25
26 namespace Rose {
27
29 namespace Combinatorics {
30
32 template<typename T>
33 static T
34 factorial(T n)
35 {
36  T retval = 1;
37  while (n>1) {
38  T next = retval * n--;
39  assert(next>retval); // overflow
40  retval = next;
41  }
42  return retval;
43 }
44
46 ROSE_DLL_API bool flip_coin();
47
53 template<typename T>
54 static void
55 permute(std::vector<T> &values/*in,out*/, uint64_t pn, size_t sz = UNLIMITED)
56 {
57  if (UNLIMITED == sz)
58  sz = values.size();
59  assert(sz<=values.size());
60  assert(pn<factorial(sz));
61  for (size_t i=0; i<sz; ++i) {
62  uint64_t radix = sz - i;
63  uint64_t idx = pn % radix;
64  std::swap(values[i+idx], values[i]);
66  }
67 }
68
74 template<typename T>
75 void
76 shuffle(std::vector<T> &vector, size_t nitems = UNLIMITED, size_t limit = UNLIMITED)
77 {
78  nitems = std::min(nitems, vector.size());
79  limit = std::min(limit, nitems);
80
81  for (size_t i=0; i<limit; ++i) {
82  size_t j = Sawyer::fastRandomIndex(nitems);
83  std::swap(vector[i], vector[j]);
84  }
85 }
86
87 // [Robb Matzke 2018-05-09]: deprecated. Use HasherSha1 instead.
88 // Compute a SHA1 digest. The returned vector will contain 20 bytes and can be converted to a string of 40 hexadecimal
89 // characters via digest_to_string(). If called when a SHA1 algorithm is not available (due to ROSE configuration) an
90 // empty vector is returned.
91 ROSE_DLL_API std::vector<uint8_t> sha1_digest(const uint8_t *data, size_t size) ROSE_DEPRECATED("use HasherSha1");
92 ROSE_DLL_API std::vector<uint8_t> sha1_digest(const std::vector<uint8_t> &data) ROSE_DEPRECATED("use HasherSha1");
93 ROSE_DLL_API std::vector<uint8_t> sha1_digest(const std::string &data) ROSE_DEPRECATED("use HasherSha1");
94
95 // [Robb Matzke 2018-05-09]: deprecated. Use HasherFnv instead.
96 // Compute the Fowler–Noll–Vo fast string hash. This is not a cryptographic hash. Speed is marginally slower than Murmur
97 // hash, but collision rate is slightly less.
98 ROSE_DLL_API uint64_t fnv1a64_digest(const uint8_t *data, size_t size) ROSE_DEPRECATED("use HasherFnv");
99 ROSE_DLL_API uint64_t fnv1a64_digest(const std::vector<uint8_t> &data) ROSE_DEPRECATED("use HasherFnv");
100 ROSE_DLL_API uint64_t fnv1a64_digest(const std::string &data) ROSE_DEPRECATED("use HasherFnv");
101
102 // [Robb Matzke 2018-05-09]: deprecated. Use the Hasher API instead.
103 // Converts a binary digest to a string of hexadecimal characters. The input can actually be any type of data and any
104 // length. The output will be twice as long as the input. If you're using this to convert binary data to a printable format
105 // you're doing it wrong--use StringUtility::encode_base64() instead.
106 ROSE_DLL_API std::string digest_to_string(const uint8_t *data, size_t size) ROSE_DEPRECATED("use Hasher");
107 ROSE_DLL_API std::string digest_to_string(const std::vector<uint8_t> &digest) ROSE_DEPRECATED("use Hasher");
108 ROSE_DLL_API std::string digest_to_string(const std::string &data) ROSE_DEPRECATED("use Hasher");
109
143 class ROSE_DLL_API Hasher {
144 public:
149  typedef std::vector<uint8_t> Digest;
150
152  class Exception: public Rose::Exception {
153  public:
155  Exception(const std::string &mesg): Rose::Exception(mesg) {}
156  ~Exception() throw () {}
157  };
158
159 protected:
160  Digest digest_;
161
162 public:
163  virtual ~Hasher() {}
164
166  virtual void clear() { digest_ = Digest(); }
167
172  virtual const Digest& digest() { return digest_; }
173
179  void insert(const std::string &x) { append((const uint8_t*)x.c_str(), x.size()); }
180  void insert(uint64_t x) { append((uint8_t*)&x, sizeof x); }
181  void insert(const uint8_t *x, size_t size) { append(x, size); }
182  void insert(std::istream &stream) {
183  char buf[4096]; // multiple of 64
184  while (stream.good()) {
186  append((const uint8_t*)buf, stream.gcount());
187  }
188  if (!stream.eof())
189  throw Hasher::Exception("failed to read data from file");
190  }
197  virtual void append(const uint8_t *message, size_t messageSize) = 0;
198
200  static std::string toString(const Digest&);
201
206  std::string toString();
207
212  void print(std::ostream&);
213
221  {
222  public:
223  virtual boost::shared_ptr<Hasher> create() const = 0;
224  virtual ~IHasherMaker() {}
225  };
226
242  template<typename T>
243  class HasherMaker : public IHasherMaker
244  {
245  public:
254  HasherMaker(const std::string& hashType)
255  {
256  HasherFactory::Instance().registerMaker(hashType, this);
257  }
258
263  virtual boost::shared_ptr<Hasher> create() const
264  {
265  T* hasher = new T;
266  boost::shared_ptr<Hasher> hashPtr(hasher);
267  return hashPtr;
268  }
269
270  };
271
284  {
285  public:
288  static HasherFactory& Instance();
289
292  void registerMaker(const std::string& hashType, IHasherMaker* createHasherPtr);
293
301  boost::shared_ptr<Hasher> createHasher(const std::string& hashType) const;
302
303  private:
304  HasherFactory() {}
305
307  HasherFactory(const HasherFactory& other);
309  HasherFactory& operator=(const HasherFactory& other);
310
312  std::map<std::string, IHasherMaker* > hashMakers;
313  };
314 };
315
321 template<int hashAlgorithmId>
322 class HasherGcrypt: public Hasher {
323 #ifdef ROSE_HAVE_LIBGCRYPT
324  gcry_md_hd_t md_;
325 #endif
326
327 public:
328  HasherGcrypt() {
329  #ifdef ROSE_HAVE_LIBGCRYPT
330  if (gcry_md_open(&md_, hashAlgorithmId, 0) != GPG_ERR_NO_ERROR)
331  throw Exception("cannot initialize libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
332  #else
333  throw Exception("ROSE was not configured with libgcrypt");
334  #endif
335  }
336
337  HasherGcrypt(const HasherGcrypt &other) {
338  #ifdef ROSE_HAVE_LIBGCRYPT
339  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
340  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
341  #else
342  throw Exception("ROSE was not configured with libgcrypt");
343  #endif
344  }
345
346  ~HasherGcrypt() {
347  #ifdef ROSE_HAVE_LIBGCRYPT
348  gcry_md_close(md_);
349  #endif
350  }
351
352  HasherGcrypt& operator=(const HasherGcrypt &other) {
353  #ifdef ROSE_HAVE_LIBGCRYPT
354  gcry_md_close(md_);
355  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
356  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
357  #else
358  throw Exception("ROSE was not configured with libgcrypt");
359  #endif
360  }
361
362  void clear() {
363  #ifdef ROSE_HAVE_LIBGCRYPT
364  gcry_md_reset(md_);
365  #endif
366  Hasher::clear();
367  }
368
369  const Digest& digest() {
370  if (digest_.empty()) {
371  #ifdef ROSE_HAVE_LIBGCRYPT
372  gcry_md_final(md_);
373  digest_.resize(gcry_md_get_algo_dlen(hashAlgorithmId), 0);
374  uint8_t *d = gcry_md_read(md_, hashAlgorithmId);
375  ASSERT_not_null(d);
376  memcpy(&digest_[0], d, digest_.size());
377  #else
378  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
379  #endif
380  }
381  return Hasher::digest();
382  }
383
384  void append(const uint8_t *message, size_t messageSize) {
385  ASSERT_require(message || 0==messageSize);
386  #ifdef ROSE_HAVE_LIBGCRYPT
387  if (!digest_.empty())
388  throw Exception("cannot append after returning digest");
389  if (messageSize > 0)
390  gcry_md_write(md_, message, messageSize);
391  #else
392  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
393  #endif
394  }
395 };
396
397 #ifdef ROSE_HAVE_LIBGCRYPT
398 typedef HasherGcrypt<GCRY_MD_MD5> HasherMd5;
399 typedef HasherGcrypt<GCRY_MD_SHA1> HasherSha1;
400 typedef HasherGcrypt<GCRY_MD_SHA256> HasherSha256;
401 typedef HasherGcrypt<GCRY_MD_SHA384> HasherSha384;
402 typedef HasherGcrypt<GCRY_MD_SHA512> HasherSha512;
403 typedef HasherGcrypt<GCRY_MD_CRC32> HasherCrc32;
404 #else // the template argument for the following unimplemented hashers is arbitrary and they can all be the same
411 #endif
412
413
414
416 class ROSE_DLL_API HasherFnv: public Hasher {
417  uint64_t partial_;
418 public:
419  HasherFnv(): partial_(0xcbf29ce484222325ull) {}
420  const Digest& digest() ROSE_OVERRIDE;
421  void append(const uint8_t *message, size_t messageSize) ROSE_OVERRIDE;
422  uint64_t partial() const { return partial_; }
423 };
424
428 class ROSE_DLL_API HasherSha256Builtin: public Hasher {
429  static const uint32_t roundConstants_[64]; // statically-generated constants for the algorithm
430  uint32_t state_[8]; // 256 bits of state information
431  size_t processedBytes_; // number of message bytes hashed (excludes padding)
432  std::vector<uint8_t> leftoverBytes_; // message bytes inserted but not yet hashed
433 public:
435  void clear() ROSE_OVERRIDE;
436  const Digest& digest() ROSE_OVERRIDE;
437  void append(const uint8_t *message, size_t messageSize) ROSE_OVERRIDE;
438 private:
439  uint8_t messageByte(size_t index, const uint8_t *message, size_t messageSize);
440  bool getNextChunk(const uint8_t* &message /*in,out*/, size_t &messageSize /*in,out*/, uint32_t words[16] /*out*/);
441  void accumulateChunk(const uint32_t chunk[16]);
442 };
443
447 template<class T, class U>
448 std::vector<std::pair<T, U> >
449 zip(const std::vector<T> &first, const std::vector<U> &second) {
450  size_t retvalSize = std::min(first.size(), second.size());
451  std::vector<std::pair<T, U> > retval;
452  retval.reserve(retvalSize);
453  for (size_t i = 0; i < retvalSize; ++i)
454  retval.push_back(std::pair<T, U>(first[i], second[i]));
455  return retval;
456 }
457
459 template<class T, class U>
460 std::pair<std::vector<T>, std::vector<U> >
461 unzip(const std::vector<std::pair<T, U> > &pairs) {
462  std::pair<std::vector<T>, std::vector<U> > retval;
463  retval.first.reserve(pairs.size());
464  retval.second.reserve(pairs.size());
465  for (size_t i = 0; i < pairs.size(); ++i) {
466  retval.first.push_back(pairs[i].first);
467  retval.second.push_back(pairs[i].second);
468  }
469  return retval;
470 }
471
472 } // namespace
473 } // namespace
474
476
478 ROSE_DLL_API std::ostream& operator<<(std::ostream&, Rose::Combinatorics::Hasher&);
479
480 #endif
Exception(const std::string &mesg)
Constructor.
std::pair< std::vector< T >, std::vector< U > > unzip(const std::vector< std::pair< T, U > > &pairs)
Convert a vector of pairs to a pair of vectors.
virtual const Digest & digest()
Return the digest.
const size_t UNLIMITED(-1)
Effictively unlimited size.
void insert(const std::string &x)
Insert data into the digest.
void clear()
Reset the hasher to its initial state.
Hasher for any libgcrypt hash algorithm.
HasherGcrypt< 0 > HasherSha384
SHA-384 hasher.
void shuffle(std::vector< T > &vector, size_t nitems=UNLIMITED, size_t limit=UNLIMITED)
Shuffle the values of a vector.
Definition: Combinatorics.h:76
Main namespace for the ROSE library.
HasherGcrypt< 0 > HasherSha1
SHA1 hasher.
Common subclass all the classes that construct Hashers (for the HasherFactory)
ROSE_DLL_API bool flip_coin()
Simulate flipping a coin.
size_t fastRandomIndex(size_t n, size_t seed=0)
void insert(uint64_t x)
Insert data into the digest.
Fowler-Noll-Vo hashing using the Hasher interface.
void append(const uint8_t *message, size_t messageSize)
Insert data into the digest.
void insert(const uint8_t *x, size_t size)
Insert data into the digest.
std::vector< uint8_t > Digest
The digest of the input message.
Templated to create any Hasher and register it with HasherFactory.
virtual boost::shared_ptr< Hasher > create() const
Creates a Hasher (the type of Hasher is determined by the template T) and returns it as a shared_ptr...
void insert(std::istream &stream)
Insert data into the digest.
HasherMaker(const std::string &hashType)
Creates a HasherMaker and registers it with HasherFactory.
HasherGcrypt< 0 > HasherCrc32
ISO 3309 hasher.
std::vector< std::pair< T, U > > zip(const std::vector< T > &first, const std::vector< U > &second)
Convert two vectors to a vector of pairs.
virtual void clear()
Reset the hasher to its initial state.
HasherGcrypt< 0 > HasherSha256
SHA-256 hasher.
HasherGcrypt< 0 > HasherMd5
MD5 hasher.
HasherFactory is a singleton that creates and returns Hashers by name.
const Digest & digest()
Return the digest.
Base class for all ROSE exceptions.
Definition: RoseException.h:9
HasherGcrypt< 0 > HasherSha512
SHA-512 hasher.