ROSE  0.9.11.42
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=(size_t)(-1))
56 {
57  if ((size_t)(-1)==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=(size_t)(-1), size_t limit=(size_t)(-1))
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()) {
185  stream.read(buf, sizeof buf);
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 
214  static boost::shared_ptr<Hasher> createHasher(const std::string& inType);
215 
216 };
217 
223 template<int hashAlgorithmId>
224 class HasherGcrypt: public Hasher {
225 #ifdef ROSE_HAVE_LIBGCRYPT
226  gcry_md_hd_t md_;
227 #endif
228 
229 public:
230  HasherGcrypt() {
231  #ifdef ROSE_HAVE_LIBGCRYPT
232  if (gcry_md_open(&md_, hashAlgorithmId, 0) != GPG_ERR_NO_ERROR)
233  throw Exception("cannot initialize libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
234  #else
235  throw Exception("ROSE was not configured with libgcrypt");
236  #endif
237  }
238 
239  HasherGcrypt(const HasherGcrypt &other) {
240  #ifdef ROSE_HAVE_LIBGCRYPT
241  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
242  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
243  #else
244  throw Exception("ROSE was not configured with libgcrypt");
245  #endif
246  }
247 
248  ~HasherGcrypt() {
249  #ifdef ROSE_HAVE_LIBGCRYPT
250  gcry_md_close(md_);
251  #endif
252  }
253 
254  HasherGcrypt& operator=(const HasherGcrypt &other) {
255  #ifdef ROSE_HAVE_LIBGCRYPT
256  gcry_md_close(md_);
257  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
258  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
259  #else
260  throw Exception("ROSE was not configured with libgcrypt");
261  #endif
262  }
263 
264  void clear() {
265  #ifdef ROSE_HAVE_LIBGCRYPT
266  gcry_md_reset(md_);
267  #endif
268  Hasher::clear();
269  }
270 
271  const Digest& digest() {
272  if (digest_.empty()) {
273  #ifdef ROSE_HAVE_LIBGCRYPT
274  gcry_md_final(md_);
275  digest_.resize(gcry_md_get_algo_dlen(hashAlgorithmId), 0);
276  uint8_t *d = gcry_md_read(md_, hashAlgorithmId);
277  ASSERT_not_null(d);
278  memcpy(&digest_[0], d, digest_.size());
279  #else
280  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
281  #endif
282  }
283  return Hasher::digest();
284  }
285 
286  void append(const uint8_t *message, size_t messageSize) {
287  ASSERT_require(message || 0==messageSize);
288  #ifdef ROSE_HAVE_LIBGCRYPT
289  if (!digest_.empty())
290  throw Exception("cannot append after returning digest");
291  if (messageSize > 0)
292  gcry_md_write(md_, message, messageSize);
293  #else
294  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
295  #endif
296  }
297 };
298 
299 #ifdef ROSE_HAVE_LIBGCRYPT
300 typedef HasherGcrypt<GCRY_MD_MD5> HasherMd5;
301 typedef HasherGcrypt<GCRY_MD_SHA1> HasherSha1;
302 typedef HasherGcrypt<GCRY_MD_SHA256> HasherSha256;
303 typedef HasherGcrypt<GCRY_MD_SHA384> HasherSha384;
304 typedef HasherGcrypt<GCRY_MD_SHA512> HasherSha512;
305 typedef HasherGcrypt<GCRY_MD_CRC32> HasherCrc32;
306 #else // the template argument for the following unimplemented hashers is arbitrary and they can all be the same
313 #endif
314 
315 
316 
318 class ROSE_DLL_API HasherFnv: public Hasher {
319  uint64_t partial_;
320 public:
321  HasherFnv(): partial_(0xcbf29ce484222325ull) {}
322  const Digest& digest() ROSE_OVERRIDE;
323  void append(const uint8_t *message, size_t messageSize) ROSE_OVERRIDE;
324  uint64_t partial() const { return partial_; }
325 };
326 
330 class ROSE_DLL_API HasherSha256Builtin: public Hasher {
331  static const uint32_t roundConstants_[64]; // statically-generated constants for the algorithm
332  uint32_t state_[8]; // 256 bits of state information
333  size_t processedBytes_; // number of message bytes hashed (excludes padding)
334  std::vector<uint8_t> leftoverBytes_; // message bytes inserted but not yet hashed
335 public:
337  void clear() ROSE_OVERRIDE;
338  const Digest& digest() ROSE_OVERRIDE;
339  void append(const uint8_t *message, size_t messageSize) ROSE_OVERRIDE;
340 private:
341  uint8_t messageByte(size_t index, const uint8_t *message, size_t messageSize);
342  bool getNextChunk(const uint8_t* &message /*in,out*/, size_t &messageSize /*in,out*/, uint32_t words[16] /*out*/);
343  void accumulateChunk(const uint32_t chunk[16]);
344 };
345 
349 template<class T, class U>
350 std::vector<std::pair<T, U> >
351 zip(const std::vector<T> &first, const std::vector<U> &second) {
352  size_t retvalSize = std::min(first.size(), second.size());
353  std::vector<std::pair<T, U> > retval;
354  retval.reserve(retvalSize);
355  for (size_t i = 0; i < retvalSize; ++i)
356  retval.push_back(std::pair<T, U>(first[i], second[i]));
357  return retval;
358 }
359 
361 template<class T, class U>
362 std::pair<std::vector<T>, std::vector<U> >
363 unzip(const std::vector<std::pair<T, U> > &pairs) {
364  std::pair<std::vector<T>, std::vector<U> > retval;
365  retval.first.reserve(pairs.size());
366  retval.second.reserve(pairs.size());
367  for (size_t i = 0; i < pairs.size(); ++i) {
368  retval.first.push_back(pairs[i].first);
369  retval.second.push_back(pairs[i].second);
370  }
371  return retval;
372 }
373 
374 } // namespace
375 } // namespace
376 
378 
380 ROSE_DLL_API std::ostream& operator<<(std::ostream&, Rose::Combinatorics::Hasher&);
381 
382 #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.
size_t fastRandomIndex(size_t n)
Thread-safe random number generator.
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.
Main namespace for the ROSE library.
HasherGcrypt< 0 > HasherSha1
SHA1 hasher.
ROSE_DLL_API bool flip_coin()
Simulate flipping a coin.
void shuffle(std::vector< T > &vector, size_t nitems=(size_t)(-1), size_t limit=(size_t)(-1))
Shuffle the values of a vector.
Definition: Combinatorics.h:76
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.
void insert(std::istream &stream)
Insert data into the digest.
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.
const Digest & digest()
Return the digest.
Base class for all ROSE exceptions.
Definition: RoseException.h:9
HasherGcrypt< 0 > HasherSha512
SHA-512 hasher.