ROSE  0.11.145.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 <Rose/Exception.h>
14 #include <Sawyer/Assert.h>
15 #include <Sawyer/Synchronization.h>
16 #include <stdexcept>
17 #include <stdint.h>
18 #include <string>
19 #include <vector>
20 
21 #ifdef ROSE_HAVE_LIBGCRYPT
22 #include <gcrypt.h>
23 #endif
24 
25 namespace Rose {
26 
28 namespace Combinatorics {
29 
31 template<typename T>
32 static T
33 factorial(T n)
34 {
35  T retval = 1;
36  while (n>1) {
37  T next = retval * n--;
38  assert(next>retval); // overflow
39  retval = next;
40  }
41  return retval;
42 }
43 
45 ROSE_DLL_API bool flip_coin();
46 
52 template<typename T>
53 static void
54 permute(std::vector<T> &values/*in,out*/, uint64_t pn, size_t sz = UNLIMITED)
55 {
56  if (UNLIMITED == sz)
57  sz = values.size();
58  assert(sz<=values.size());
59  assert(pn<factorial(sz));
60  for (size_t i=0; i<sz; ++i) {
61  uint64_t radix = sz - i;
62  uint64_t idx = pn % radix;
63  std::swap(values[i+idx], values[i]);
64  pn /= radix;
65  }
66 }
67 
73 template<typename T>
74 void
75 shuffle(std::vector<T> &vector, size_t nitems = UNLIMITED, size_t limit = UNLIMITED)
76 {
77  nitems = std::min(nitems, vector.size());
78  limit = std::min(limit, nitems);
79 
80  for (size_t i=0; i<limit; ++i) {
81  size_t j = Sawyer::fastRandomIndex(nitems);
82  std::swap(vector[i], vector[j]);
83  }
84 }
85 
111 template<class T>
112 void
113 reorder(std::vector<T> &values, const std::vector<size_t> &remap) {
114  assert(values.size() == remap.size());
115 
116  // O(n) implementation using a temporary vector. Alternatively, we could use an O(n^2) algorithm that uses constant space.
117  std::vector<T> old = values;
118  for (size_t i = 0; i < old.size(); ++i)
119  values[i] = old[remap[i]];
120 }
121 
155 class ROSE_DLL_API Hasher {
156 public:
161  typedef std::vector<uint8_t> Digest;
162 
164  class Exception: public Rose::Exception {
165  public:
167  Exception(const std::string &mesg): Rose::Exception(mesg) {}
168  ~Exception() throw () {}
169  };
170 
171 protected:
172  Digest digest_;
173 
174 public:
175  virtual ~Hasher() {}
176 
178  virtual void clear() { digest_ = Digest(); }
179 
184  virtual const Digest& digest() { return digest_; }
185 
191  void insert(const std::string &x) { append((const uint8_t*)x.c_str(), x.size()); }
192  void insert(uint64_t x) { append((uint8_t*)&x, sizeof x); }
193  void insert(const uint8_t *x, size_t size) { append(x, size); }
194  void insert(const std::vector<uint8_t> &v) { append(v.data(), v.size()); }
195  void insert(std::istream &stream) {
196  char buf[4096]; // multiple of 64
197  while (stream.good()) {
198  stream.read(buf, sizeof buf);
199  append((const uint8_t*)buf, stream.gcount());
200  }
201  if (!stream.eof())
202  throw Hasher::Exception("failed to read data from file");
203  }
210  virtual void append(const uint8_t *message, size_t messageSize) = 0;
211 
213  static std::string toString(const Digest&);
214 
219  std::string toString();
220 
225  void print(std::ostream&);
226 
234  {
235  public:
236  virtual boost::shared_ptr<Hasher> create() const = 0;
237  virtual ~IHasherMaker() {}
238  };
239 
255  template<typename T>
256  class HasherMaker : public IHasherMaker
257  {
258  public:
267  HasherMaker(const std::string& hashType)
268  {
269  HasherFactory::Instance().registerMaker(hashType, this);
270  }
271 
276  virtual boost::shared_ptr<Hasher> create() const
277  {
278  T* hasher = new T;
279  boost::shared_ptr<Hasher> hashPtr(hasher);
280  return hashPtr;
281  }
282 
283  };
284 
297  {
298  public:
301  static HasherFactory& Instance();
302 
305  void registerMaker(const std::string& hashType, IHasherMaker* createHasherPtr);
306 
314  boost::shared_ptr<Hasher> createHasher(const std::string& hashType) const;
315 
316  private:
317  HasherFactory() {}
318 
320  HasherFactory(const HasherFactory& other);
322  HasherFactory& operator=(const HasherFactory& other);
323 
325  std::map<std::string, IHasherMaker* > hashMakers;
326  };
327 };
328 
334 template<int hashAlgorithmId>
335 class HasherGcrypt: public Hasher {
336 #ifdef ROSE_HAVE_LIBGCRYPT
337  gcry_md_hd_t md_;
338 #endif
339 
340 public:
341  HasherGcrypt() {
342  #ifdef ROSE_HAVE_LIBGCRYPT
343  if (gcry_md_open(&md_, hashAlgorithmId, 0) != GPG_ERR_NO_ERROR)
344  throw Exception("cannot initialize libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
345  #else
346  throw Exception("ROSE was not configured with libgcrypt");
347  #endif
348  }
349 
350  HasherGcrypt(const HasherGcrypt &other) {
351  #ifdef ROSE_HAVE_LIBGCRYPT
352  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
353  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
354  #else
355  throw Exception("ROSE was not configured with libgcrypt");
356  #endif
357  }
358 
359  ~HasherGcrypt() {
360  #ifdef ROSE_HAVE_LIBGCRYPT
361  gcry_md_close(md_);
362  #endif
363  }
364 
365  HasherGcrypt& operator=(const HasherGcrypt &other) {
366  #ifdef ROSE_HAVE_LIBGCRYPT
367  gcry_md_close(md_);
368  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
369  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
370  #else
371  throw Exception("ROSE was not configured with libgcrypt");
372  #endif
373  }
374 
375  void clear() {
376  #ifdef ROSE_HAVE_LIBGCRYPT
377  gcry_md_reset(md_);
378  #endif
379  Hasher::clear();
380  }
381 
382  const Digest& digest() {
383  if (digest_.empty()) {
384  #ifdef ROSE_HAVE_LIBGCRYPT
385  gcry_md_final(md_);
386  digest_.resize(gcry_md_get_algo_dlen(hashAlgorithmId), 0);
387  uint8_t *d = gcry_md_read(md_, hashAlgorithmId);
388  ASSERT_not_null(d);
389  memcpy(&digest_[0], d, digest_.size());
390  #else
391  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
392  #endif
393  }
394  return Hasher::digest();
395  }
396 
397  void append(const uint8_t *message, size_t messageSize) {
398  ASSERT_require(message || 0==messageSize);
399  #ifdef ROSE_HAVE_LIBGCRYPT
400  if (!digest_.empty())
401  throw Exception("cannot append after returning digest");
402  if (messageSize > 0)
403  gcry_md_write(md_, message, messageSize);
404  #else
405  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
406  #endif
407  }
408 };
409 
410 #ifdef ROSE_HAVE_LIBGCRYPT
411 typedef HasherGcrypt<GCRY_MD_MD5> HasherMd5;
412 typedef HasherGcrypt<GCRY_MD_SHA1> HasherSha1;
413 typedef HasherGcrypt<GCRY_MD_SHA256> HasherSha256;
414 typedef HasherGcrypt<GCRY_MD_SHA384> HasherSha384;
415 typedef HasherGcrypt<GCRY_MD_SHA512> HasherSha512;
416 typedef HasherGcrypt<GCRY_MD_CRC32> HasherCrc32;
417 #else // the template argument for the following unimplemented hashers is arbitrary and they can all be the same
424 #endif
425 
426 
427 
429 class ROSE_DLL_API HasherFnv: public Hasher {
430  uint64_t partial_;
431 public:
432  HasherFnv(): partial_(0xcbf29ce484222325ull) {}
433  const Digest& digest() override;
434  void append(const uint8_t *message, size_t messageSize) override;
435  uint64_t partial() const { return partial_; }
436 };
437 
441 class ROSE_DLL_API HasherSha256Builtin: public Hasher {
442  static const uint32_t roundConstants_[64]; // statically-generated constants for the algorithm
443  uint32_t state_[8]; // 256 bits of state information
444  size_t processedBytes_; // number of message bytes hashed (excludes padding)
445  std::vector<uint8_t> leftoverBytes_; // message bytes inserted but not yet hashed
446 public:
448  void clear() override;
449  const Digest& digest() override;
450  void append(const uint8_t *message, size_t messageSize) override;
451 private:
452  uint8_t messageByte(size_t index, const uint8_t *message, size_t messageSize);
453  bool getNextChunk(const uint8_t* &message /*in,out*/, size_t &messageSize /*in,out*/, uint32_t words[16] /*out*/);
454  void accumulateChunk(const uint32_t chunk[16]);
455 };
456 
460 template<class T, class U>
461 std::vector<std::pair<T, U> >
462 zip(const std::vector<T> &first, const std::vector<U> &second) {
463  size_t retvalSize = std::min(first.size(), second.size());
464  std::vector<std::pair<T, U> > retval;
465  retval.reserve(retvalSize);
466  for (size_t i = 0; i < retvalSize; ++i)
467  retval.push_back(std::pair<T, U>(first[i], second[i]));
468  return retval;
469 }
470 
472 template<class T, class U>
473 std::pair<std::vector<T>, std::vector<U> >
474 unzip(const std::vector<std::pair<T, U> > &pairs) {
475  std::pair<std::vector<T>, std::vector<U> > retval;
476  retval.first.reserve(pairs.size());
477  retval.second.reserve(pairs.size());
478  for (size_t i = 0; i < pairs.size(); ++i) {
479  retval.first.push_back(pairs[i].first);
480  retval.second.push_back(pairs[i].second);
481  }
482  return retval;
483 }
484 
485 } // namespace
486 } // namespace
487 
489 
491 ROSE_DLL_API std::ostream& operator<<(std::ostream&, Rose::Combinatorics::Hasher&);
492 
493 #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.
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:75
Main namespace for the ROSE library.
const size_t UNLIMITED(static_cast< size_t >(-1))
Effictively unlimited size.
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.
void insert(const std::vector< uint8_t > &v)
Insert data into the digest.
size_t fastRandomIndex(size_t n, size_t seed=0)
Thread-safe random number generator.
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.
void reorder(std::vector< T > &values, const std::vector< size_t > &remap)
Reorder the values of one vector according to another.
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: Rose/Exception.h:9
HasherGcrypt< 0 > HasherSha512
SHA-512 hasher.