ROSE  0.11.52.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 <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]);
65  pn /= radix;
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 
120 class ROSE_DLL_API Hasher {
121 public:
126  typedef std::vector<uint8_t> Digest;
127 
129  class Exception: public Rose::Exception {
130  public:
132  Exception(const std::string &mesg): Rose::Exception(mesg) {}
133  ~Exception() throw () {}
134  };
135 
136 protected:
137  Digest digest_;
138 
139 public:
140  virtual ~Hasher() {}
141 
143  virtual void clear() { digest_ = Digest(); }
144 
149  virtual const Digest& digest() { return digest_; }
150 
156  void insert(const std::string &x) { append((const uint8_t*)x.c_str(), x.size()); }
157  void insert(uint64_t x) { append((uint8_t*)&x, sizeof x); }
158  void insert(const uint8_t *x, size_t size) { append(x, size); }
159  void insert(const std::vector<uint8_t> &v) { append(v.data(), v.size()); }
160  void insert(std::istream &stream) {
161  char buf[4096]; // multiple of 64
162  while (stream.good()) {
163  stream.read(buf, sizeof buf);
164  append((const uint8_t*)buf, stream.gcount());
165  }
166  if (!stream.eof())
167  throw Hasher::Exception("failed to read data from file");
168  }
175  virtual void append(const uint8_t *message, size_t messageSize) = 0;
176 
178  static std::string toString(const Digest&);
179 
184  std::string toString();
185 
190  void print(std::ostream&);
191 
199  {
200  public:
201  virtual boost::shared_ptr<Hasher> create() const = 0;
202  virtual ~IHasherMaker() {}
203  };
204 
220  template<typename T>
221  class HasherMaker : public IHasherMaker
222  {
223  public:
232  HasherMaker(const std::string& hashType)
233  {
234  HasherFactory::Instance().registerMaker(hashType, this);
235  }
236 
241  virtual boost::shared_ptr<Hasher> create() const
242  {
243  T* hasher = new T;
244  boost::shared_ptr<Hasher> hashPtr(hasher);
245  return hashPtr;
246  }
247 
248  };
249 
262  {
263  public:
266  static HasherFactory& Instance();
267 
270  void registerMaker(const std::string& hashType, IHasherMaker* createHasherPtr);
271 
279  boost::shared_ptr<Hasher> createHasher(const std::string& hashType) const;
280 
281  private:
282  HasherFactory() {}
283 
285  HasherFactory(const HasherFactory& other);
287  HasherFactory& operator=(const HasherFactory& other);
288 
290  std::map<std::string, IHasherMaker* > hashMakers;
291  };
292 };
293 
299 template<int hashAlgorithmId>
300 class HasherGcrypt: public Hasher {
301 #ifdef ROSE_HAVE_LIBGCRYPT
302  gcry_md_hd_t md_;
303 #endif
304 
305 public:
306  HasherGcrypt() {
307  #ifdef ROSE_HAVE_LIBGCRYPT
308  if (gcry_md_open(&md_, hashAlgorithmId, 0) != GPG_ERR_NO_ERROR)
309  throw Exception("cannot initialize libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
310  #else
311  throw Exception("ROSE was not configured with libgcrypt");
312  #endif
313  }
314 
315  HasherGcrypt(const HasherGcrypt &other) {
316  #ifdef ROSE_HAVE_LIBGCRYPT
317  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
318  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
319  #else
320  throw Exception("ROSE was not configured with libgcrypt");
321  #endif
322  }
323 
324  ~HasherGcrypt() {
325  #ifdef ROSE_HAVE_LIBGCRYPT
326  gcry_md_close(md_);
327  #endif
328  }
329 
330  HasherGcrypt& operator=(const HasherGcrypt &other) {
331  #ifdef ROSE_HAVE_LIBGCRYPT
332  gcry_md_close(md_);
333  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
334  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
335  #else
336  throw Exception("ROSE was not configured with libgcrypt");
337  #endif
338  }
339 
340  void clear() {
341  #ifdef ROSE_HAVE_LIBGCRYPT
342  gcry_md_reset(md_);
343  #endif
344  Hasher::clear();
345  }
346 
347  const Digest& digest() {
348  if (digest_.empty()) {
349  #ifdef ROSE_HAVE_LIBGCRYPT
350  gcry_md_final(md_);
351  digest_.resize(gcry_md_get_algo_dlen(hashAlgorithmId), 0);
352  uint8_t *d = gcry_md_read(md_, hashAlgorithmId);
353  ASSERT_not_null(d);
354  memcpy(&digest_[0], d, digest_.size());
355  #else
356  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
357  #endif
358  }
359  return Hasher::digest();
360  }
361 
362  void append(const uint8_t *message, size_t messageSize) {
363  ASSERT_require(message || 0==messageSize);
364  #ifdef ROSE_HAVE_LIBGCRYPT
365  if (!digest_.empty())
366  throw Exception("cannot append after returning digest");
367  if (messageSize > 0)
368  gcry_md_write(md_, message, messageSize);
369  #else
370  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
371  #endif
372  }
373 };
374 
375 #ifdef ROSE_HAVE_LIBGCRYPT
376 typedef HasherGcrypt<GCRY_MD_MD5> HasherMd5;
377 typedef HasherGcrypt<GCRY_MD_SHA1> HasherSha1;
378 typedef HasherGcrypt<GCRY_MD_SHA256> HasherSha256;
379 typedef HasherGcrypt<GCRY_MD_SHA384> HasherSha384;
380 typedef HasherGcrypt<GCRY_MD_SHA512> HasherSha512;
381 typedef HasherGcrypt<GCRY_MD_CRC32> HasherCrc32;
382 #else // the template argument for the following unimplemented hashers is arbitrary and they can all be the same
389 #endif
390 
391 
392 
394 class ROSE_DLL_API HasherFnv: public Hasher {
395  uint64_t partial_;
396 public:
397  HasherFnv(): partial_(0xcbf29ce484222325ull) {}
398  const Digest& digest() ROSE_OVERRIDE;
399  void append(const uint8_t *message, size_t messageSize) ROSE_OVERRIDE;
400  uint64_t partial() const { return partial_; }
401 };
402 
406 class ROSE_DLL_API HasherSha256Builtin: public Hasher {
407  static const uint32_t roundConstants_[64]; // statically-generated constants for the algorithm
408  uint32_t state_[8]; // 256 bits of state information
409  size_t processedBytes_; // number of message bytes hashed (excludes padding)
410  std::vector<uint8_t> leftoverBytes_; // message bytes inserted but not yet hashed
411 public:
413  void clear() ROSE_OVERRIDE;
414  const Digest& digest() ROSE_OVERRIDE;
415  void append(const uint8_t *message, size_t messageSize) ROSE_OVERRIDE;
416 private:
417  uint8_t messageByte(size_t index, const uint8_t *message, size_t messageSize);
418  bool getNextChunk(const uint8_t* &message /*in,out*/, size_t &messageSize /*in,out*/, uint32_t words[16] /*out*/);
419  void accumulateChunk(const uint32_t chunk[16]);
420 };
421 
425 template<class T, class U>
426 std::vector<std::pair<T, U> >
427 zip(const std::vector<T> &first, const std::vector<U> &second) {
428  size_t retvalSize = std::min(first.size(), second.size());
429  std::vector<std::pair<T, U> > retval;
430  retval.reserve(retvalSize);
431  for (size_t i = 0; i < retvalSize; ++i)
432  retval.push_back(std::pair<T, U>(first[i], second[i]));
433  return retval;
434 }
435 
437 template<class T, class U>
438 std::pair<std::vector<T>, std::vector<U> >
439 unzip(const std::vector<std::pair<T, U> > &pairs) {
440  std::pair<std::vector<T>, std::vector<U> > retval;
441  retval.first.reserve(pairs.size());
442  retval.second.reserve(pairs.size());
443  for (size_t i = 0; i < pairs.size(); ++i) {
444  retval.first.push_back(pairs[i].first);
445  retval.second.push_back(pairs[i].second);
446  }
447  return retval;
448 }
449 
450 } // namespace
451 } // namespace
452 
454 
456 ROSE_DLL_API std::ostream& operator<<(std::ostream&, Rose::Combinatorics::Hasher&);
457 
458 #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.
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.
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.