ROSE  0.11.96.11
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 
119 class ROSE_DLL_API Hasher {
120 public:
125  typedef std::vector<uint8_t> Digest;
126 
128  class Exception: public Rose::Exception {
129  public:
131  Exception(const std::string &mesg): Rose::Exception(mesg) {}
132  ~Exception() throw () {}
133  };
134 
135 protected:
136  Digest digest_;
137 
138 public:
139  virtual ~Hasher() {}
140 
142  virtual void clear() { digest_ = Digest(); }
143 
148  virtual const Digest& digest() { return digest_; }
149 
155  void insert(const std::string &x) { append((const uint8_t*)x.c_str(), x.size()); }
156  void insert(uint64_t x) { append((uint8_t*)&x, sizeof x); }
157  void insert(const uint8_t *x, size_t size) { append(x, size); }
158  void insert(const std::vector<uint8_t> &v) { append(v.data(), v.size()); }
159  void insert(std::istream &stream) {
160  char buf[4096]; // multiple of 64
161  while (stream.good()) {
162  stream.read(buf, sizeof buf);
163  append((const uint8_t*)buf, stream.gcount());
164  }
165  if (!stream.eof())
166  throw Hasher::Exception("failed to read data from file");
167  }
174  virtual void append(const uint8_t *message, size_t messageSize) = 0;
175 
177  static std::string toString(const Digest&);
178 
183  std::string toString();
184 
189  void print(std::ostream&);
190 
198  {
199  public:
200  virtual boost::shared_ptr<Hasher> create() const = 0;
201  virtual ~IHasherMaker() {}
202  };
203 
219  template<typename T>
220  class HasherMaker : public IHasherMaker
221  {
222  public:
231  HasherMaker(const std::string& hashType)
232  {
233  HasherFactory::Instance().registerMaker(hashType, this);
234  }
235 
240  virtual boost::shared_ptr<Hasher> create() const
241  {
242  T* hasher = new T;
243  boost::shared_ptr<Hasher> hashPtr(hasher);
244  return hashPtr;
245  }
246 
247  };
248 
261  {
262  public:
265  static HasherFactory& Instance();
266 
269  void registerMaker(const std::string& hashType, IHasherMaker* createHasherPtr);
270 
278  boost::shared_ptr<Hasher> createHasher(const std::string& hashType) const;
279 
280  private:
281  HasherFactory() {}
282 
284  HasherFactory(const HasherFactory& other);
286  HasherFactory& operator=(const HasherFactory& other);
287 
289  std::map<std::string, IHasherMaker* > hashMakers;
290  };
291 };
292 
298 template<int hashAlgorithmId>
299 class HasherGcrypt: public Hasher {
300 #ifdef ROSE_HAVE_LIBGCRYPT
301  gcry_md_hd_t md_;
302 #endif
303 
304 public:
305  HasherGcrypt() {
306  #ifdef ROSE_HAVE_LIBGCRYPT
307  if (gcry_md_open(&md_, hashAlgorithmId, 0) != GPG_ERR_NO_ERROR)
308  throw Exception("cannot initialize libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
309  #else
310  throw Exception("ROSE was not configured with libgcrypt");
311  #endif
312  }
313 
314  HasherGcrypt(const HasherGcrypt &other) {
315  #ifdef ROSE_HAVE_LIBGCRYPT
316  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
317  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
318  #else
319  throw Exception("ROSE was not configured with libgcrypt");
320  #endif
321  }
322 
323  ~HasherGcrypt() {
324  #ifdef ROSE_HAVE_LIBGCRYPT
325  gcry_md_close(md_);
326  #endif
327  }
328 
329  HasherGcrypt& operator=(const HasherGcrypt &other) {
330  #ifdef ROSE_HAVE_LIBGCRYPT
331  gcry_md_close(md_);
332  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
333  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
334  #else
335  throw Exception("ROSE was not configured with libgcrypt");
336  #endif
337  }
338 
339  void clear() {
340  #ifdef ROSE_HAVE_LIBGCRYPT
341  gcry_md_reset(md_);
342  #endif
343  Hasher::clear();
344  }
345 
346  const Digest& digest() {
347  if (digest_.empty()) {
348  #ifdef ROSE_HAVE_LIBGCRYPT
349  gcry_md_final(md_);
350  digest_.resize(gcry_md_get_algo_dlen(hashAlgorithmId), 0);
351  uint8_t *d = gcry_md_read(md_, hashAlgorithmId);
352  ASSERT_not_null(d);
353  memcpy(&digest_[0], d, digest_.size());
354  #else
355  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
356  #endif
357  }
358  return Hasher::digest();
359  }
360 
361  void append(const uint8_t *message, size_t messageSize) {
362  ASSERT_require(message || 0==messageSize);
363  #ifdef ROSE_HAVE_LIBGCRYPT
364  if (!digest_.empty())
365  throw Exception("cannot append after returning digest");
366  if (messageSize > 0)
367  gcry_md_write(md_, message, messageSize);
368  #else
369  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
370  #endif
371  }
372 };
373 
374 #ifdef ROSE_HAVE_LIBGCRYPT
375 typedef HasherGcrypt<GCRY_MD_MD5> HasherMd5;
376 typedef HasherGcrypt<GCRY_MD_SHA1> HasherSha1;
377 typedef HasherGcrypt<GCRY_MD_SHA256> HasherSha256;
378 typedef HasherGcrypt<GCRY_MD_SHA384> HasherSha384;
379 typedef HasherGcrypt<GCRY_MD_SHA512> HasherSha512;
380 typedef HasherGcrypt<GCRY_MD_CRC32> HasherCrc32;
381 #else // the template argument for the following unimplemented hashers is arbitrary and they can all be the same
388 #endif
389 
390 
391 
393 class ROSE_DLL_API HasherFnv: public Hasher {
394  uint64_t partial_;
395 public:
396  HasherFnv(): partial_(0xcbf29ce484222325ull) {}
397  const Digest& digest() override;
398  void append(const uint8_t *message, size_t messageSize) override;
399  uint64_t partial() const { return partial_; }
400 };
401 
405 class ROSE_DLL_API HasherSha256Builtin: public Hasher {
406  static const uint32_t roundConstants_[64]; // statically-generated constants for the algorithm
407  uint32_t state_[8]; // 256 bits of state information
408  size_t processedBytes_; // number of message bytes hashed (excludes padding)
409  std::vector<uint8_t> leftoverBytes_; // message bytes inserted but not yet hashed
410 public:
412  void clear() override;
413  const Digest& digest() override;
414  void append(const uint8_t *message, size_t messageSize) override;
415 private:
416  uint8_t messageByte(size_t index, const uint8_t *message, size_t messageSize);
417  bool getNextChunk(const uint8_t* &message /*in,out*/, size_t &messageSize /*in,out*/, uint32_t words[16] /*out*/);
418  void accumulateChunk(const uint32_t chunk[16]);
419 };
420 
424 template<class T, class U>
425 std::vector<std::pair<T, U> >
426 zip(const std::vector<T> &first, const std::vector<U> &second) {
427  size_t retvalSize = std::min(first.size(), second.size());
428  std::vector<std::pair<T, U> > retval;
429  retval.reserve(retvalSize);
430  for (size_t i = 0; i < retvalSize; ++i)
431  retval.push_back(std::pair<T, U>(first[i], second[i]));
432  return retval;
433 }
434 
436 template<class T, class U>
437 std::pair<std::vector<T>, std::vector<U> >
438 unzip(const std::vector<std::pair<T, U> > &pairs) {
439  std::pair<std::vector<T>, std::vector<U> > retval;
440  retval.first.reserve(pairs.size());
441  retval.second.reserve(pairs.size());
442  for (size_t i = 0; i < pairs.size(); ++i) {
443  retval.first.push_back(pairs[i].first);
444  retval.second.push_back(pairs[i].second);
445  }
446  return retval;
447 }
448 
449 } // namespace
450 } // namespace
451 
453 
455 ROSE_DLL_API std::ostream& operator<<(std::ostream&, Rose::Combinatorics::Hasher&);
456 
457 #endif
Rose::Combinatorics::HasherCrc32
HasherGcrypt< 0 > HasherCrc32
ISO 3309 hasher.
Definition: Combinatorics.h:387
Rose::Combinatorics::Hasher::HasherMaker::create
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.
Definition: Combinatorics.h:240
Rose::Combinatorics::Hasher::Exception
Exceptions for hashing.
Definition: Combinatorics.h:128
Rose::Combinatorics::HasherFnv
Fowler-Noll-Vo hashing using the Hasher interface.
Definition: Combinatorics.h:393
Rose::Exception
Base class for all ROSE exceptions.
Definition: Rose/Exception.h:9
Rose::Combinatorics::HasherGcrypt::clear
void clear()
Reset the hasher to its initial state.
Definition: Combinatorics.h:339
Rose::Combinatorics::Hasher::clear
virtual void clear()
Reset the hasher to its initial state.
Definition: Combinatorics.h:142
Rose::Combinatorics::Hasher::insert
void insert(const std::string &x)
Insert data into the digest.
Definition: Combinatorics.h:155
Rose::Combinatorics::HasherSha512
HasherGcrypt< 0 > HasherSha512
SHA-512 hasher.
Definition: Combinatorics.h:386
Rose::Combinatorics::HasherMd5
HasherGcrypt< 0 > HasherMd5
MD5 hasher.
Definition: Combinatorics.h:382
Rose::Combinatorics::HasherSha256Builtin
Built-in SHA-256 hasher.
Definition: Combinatorics.h:405
Rose::Combinatorics::HasherSha256
HasherGcrypt< 0 > HasherSha256
SHA-256 hasher.
Definition: Combinatorics.h:384
Sawyer::fastRandomIndex
size_t fastRandomIndex(size_t n, size_t seed=0)
Thread-safe random number generator.
Rose::Combinatorics::HasherGcrypt
Hasher for any libgcrypt hash algorithm.
Definition: Combinatorics.h:299
Rose::Combinatorics::unzip
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.
Definition: Combinatorics.h:438
Rose::Combinatorics::Hasher
Hash interface.
Definition: Combinatorics.h:119
Rose::Combinatorics::zip
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.
Definition: Combinatorics.h:426
Rose::Combinatorics::Hasher::insert
void insert(const uint8_t *x, size_t size)
Insert data into the digest.
Definition: Combinatorics.h:157
Rose::Combinatorics::Hasher::HasherMaker
Templated to create any Hasher and register it with HasherFactory.
Definition: Combinatorics.h:220
Rose::Combinatorics::Hasher::Digest
std::vector< uint8_t > Digest
The digest of the input message.
Definition: Combinatorics.h:125
Rose::Combinatorics::Hasher::digest
virtual const Digest & digest()
Return the digest.
Definition: Combinatorics.h:148
Rose::Combinatorics::Hasher::HasherMaker::HasherMaker
HasherMaker(const std::string &hashType)
Creates a HasherMaker and registers it with HasherFactory.
Definition: Combinatorics.h:231
Rose::Combinatorics::Hasher::insert
void insert(std::istream &stream)
Insert data into the digest.
Definition: Combinatorics.h:159
Rose::Combinatorics::Hasher::insert
void insert(const std::vector< uint8_t > &v)
Insert data into the digest.
Definition: Combinatorics.h:158
Rose::Combinatorics::HasherSha384
HasherGcrypt< 0 > HasherSha384
SHA-384 hasher.
Definition: Combinatorics.h:385
Rose
Main namespace for the ROSE library.
Definition: BinaryTutorial.dox:3
Rose::Combinatorics::Hasher::IHasherMaker
Common subclass all the classes that construct Hashers (for the HasherFactory)
Definition: Combinatorics.h:197
Rose::UNLIMITED
const size_t UNLIMITED(static_cast< size_t >(-1))
Effictively unlimited size.
Rose::Combinatorics::HasherGcrypt::digest
const Digest & digest()
Return the digest.
Definition: Combinatorics.h:346
Rose::Combinatorics::Hasher::insert
void insert(uint64_t x)
Insert data into the digest.
Definition: Combinatorics.h:156
Rose::Combinatorics::HasherGcrypt::append
void append(const uint8_t *message, size_t messageSize)
Insert data into the digest.
Definition: Combinatorics.h:361
Rose::Combinatorics::HasherSha1
HasherGcrypt< 0 > HasherSha1
SHA1 hasher.
Definition: Combinatorics.h:383
Rose::Combinatorics::Hasher::HasherFactory
HasherFactory is a singleton that creates and returns Hashers by name.
Definition: Combinatorics.h:260
Rose::Combinatorics::shuffle
void shuffle(std::vector< T > &vector, size_t nitems=UNLIMITED, size_t limit=UNLIMITED)
Shuffle the values of a vector.
Definition: Combinatorics.h:75
Rose::Combinatorics::Hasher::Exception::Exception
Exception(const std::string &mesg)
Constructor.
Definition: Combinatorics.h:131
Rose::Combinatorics::flip_coin
ROSE_DLL_API bool flip_coin()
Simulate flipping a coin.