ROSE  0.9.10.135
Combinatorics.h
1 #ifndef ROSE_Combinatorics_H
2 #define ROSE_Combinatorics_H
3 
4 #include <rosePublicConfig.h>
5 #include <LinearCongruentialGenerator.h>
6 
7 #include <algorithm>
8 #include <cassert>
9 #include <istream>
10 #include <list>
11 #include <ostream>
12 #include <rose_override.h>
13 #include <Sawyer/Assert.h>
14 #include <stdexcept>
15 #include <stdint.h>
16 #include <string>
17 #include <vector>
18 
19 #ifdef ROSE_HAVE_LIBGCRYPT
20 #include <gcrypt.h>
21 #endif
22 
23 namespace Rose {
24 
26 namespace Combinatorics {
27 
29 template<typename T>
30 static T
31 factorial(T n)
32 {
33  T retval = 1;
34  while (n>1) {
35  T next = retval * n--;
36  assert(next>retval); // overflow
37  retval = next;
38  }
39  return retval;
40 }
41 
44 ROSE_DLL_API bool flip_coin();
45 
51 template<typename T>
52 static void
53 permute(std::vector<T> &values/*in,out*/, uint64_t pn, size_t sz=(size_t)(-1))
54 {
55  if ((size_t)(-1)==sz)
56  sz = values.size();
57  assert(sz<=values.size());
58  assert(pn<factorial(sz));
59  for (size_t i=0; i<sz; ++i) {
60  uint64_t radix = sz - i;
61  uint64_t idx = pn % radix;
62  std::swap(values[i+idx], values[i]);
63  pn /= radix;
64  }
65 }
66 
71 template<typename T>
72 void
73 shuffle(std::vector<T> &vector, size_t nitems=(size_t)(-1), size_t limit=(size_t)(-1), LinearCongruentialGenerator *lcg=NULL)
74 {
75  static LinearCongruentialGenerator my_lcg;
76  if (!lcg)
77  lcg = &my_lcg;
78  nitems = std::min(nitems, vector.size());
79  limit = std::min(limit, nitems);
80 
81  for (size_t i=0; i<limit; ++i)
82  std::swap(vector[i], vector[lcg->next()%nitems]);
83 }
84 
85 // [Robb Matzke 2018-05-09]: deprecated. Use HasherSha1 instead.
86 // Compute a SHA1 digest. The returned vector will contain 20 bytes and can be converted to a string of 40 hexadecimal
87 // characters via digest_to_string(). If called when a SHA1 algorithm is not available (due to ROSE configuration) an
88 // empty vector is returned.
89 ROSE_DLL_API std::vector<uint8_t> sha1_digest(const uint8_t *data, size_t size) ROSE_DEPRECATED("use HasherSha1");
90 ROSE_DLL_API std::vector<uint8_t> sha1_digest(const std::vector<uint8_t> &data) ROSE_DEPRECATED("use HasherSha1");
91 ROSE_DLL_API std::vector<uint8_t> sha1_digest(const std::string &data) ROSE_DEPRECATED("use HasherSha1");
92 
93 // [Robb Matzke 2018-05-09]: deprecated. Use HasherFnv instead.
94 // Compute the Fowler–Noll–Vo fast string hash. This is not a cryptographic hash. Speed is marginally slower than Murmur
95 // hash, but collision rate is slightly less.
96 ROSE_DLL_API uint64_t fnv1a64_digest(const uint8_t *data, size_t size) ROSE_DEPRECATED("use HasherFnv");
97 ROSE_DLL_API uint64_t fnv1a64_digest(const std::vector<uint8_t> &data) ROSE_DEPRECATED("use HasherFnv");
98 ROSE_DLL_API uint64_t fnv1a64_digest(const std::string &data) ROSE_DEPRECATED("use HasherFnv");
99 
100 // [Robb Matzke 2018-05-09]: deprecated. Use the Hasher API instead.
101 // Converts a binary digest to a string of hexadecimal characters. The input can actually be any type of data and any
102 // length. The output will be twice as long as the input. If you're using this to convert binary data to a printable format
103 // you're doing it wrong--use StringUtility::encode_base64() instead.
104 ROSE_DLL_API std::string digest_to_string(const uint8_t *data, size_t size) ROSE_DEPRECATED("use Hasher");
105 ROSE_DLL_API std::string digest_to_string(const std::vector<uint8_t> &digest) ROSE_DEPRECATED("use Hasher");
106 ROSE_DLL_API std::string digest_to_string(const std::string &data) ROSE_DEPRECATED("use Hasher");
107 
141 class ROSE_DLL_API Hasher {
142 public:
147  typedef std::vector<uint8_t> Digest;
148 
150  class Exception: public std::runtime_error {
151  public:
153  Exception(const std::string &mesg): std::runtime_error(mesg) {}
154  ~Exception() throw () {}
155  };
156 
157 protected:
158  Digest digest_;
159 
160 public:
161  virtual ~Hasher() {}
162 
164  virtual void clear() { digest_ = Digest(); }
165 
170  virtual const Digest& digest() { return digest_; }
171 
177  void insert(const std::string &x) { append((const uint8_t*)x.c_str(), x.size()); }
178  void insert(uint64_t x) { append((uint8_t*)&x, sizeof x); }
179  void insert(const uint8_t *x, size_t size) { append(x, size); }
180  void insert(std::istream &stream) {
181  char buf[4096]; // multiple of 64
182  while (stream.good()) {
183  stream.read(buf, sizeof buf);
184  append((const uint8_t*)buf, stream.gcount());
185  }
186  if (!stream.eof())
187  throw Hasher::Exception("failed to read data from file");
188  }
195  virtual void append(const uint8_t *message, size_t messageSize) = 0;
196 
198  static std::string toString(const Digest&);
199 
204  std::string toString();
205 
210  void print(std::ostream&);
211 };
212 
218 template<int hashAlgorithmId>
219 class HasherGcrypt: public Hasher {
220 #ifdef ROSE_HAVE_LIBGCRYPT
221  gcry_md_hd_t md_;
222 #endif
223 
224 public:
225  HasherGcrypt() {
226  #ifdef ROSE_HAVE_LIBGCRYPT
227  if (gcry_md_open(&md_, hashAlgorithmId, 0) != GPG_ERR_NO_ERROR)
228  throw Exception("cannot initialize libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
229  #else
230  throw Exception("ROSE was not configured with libgcrypt");
231  #endif
232  }
233 
234  HasherGcrypt(const HasherGcrypt &other) {
235  #ifdef ROSE_HAVE_LIBGCRYPT
236  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
237  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
238  #else
239  throw Exception("ROSE was not configured with libgcrypt");
240  #endif
241  }
242 
243  ~HasherGcrypt() {
244  #ifdef ROSE_HAVE_LIBGCRYPT
245  gcry_md_close(md_);
246  #endif
247  }
248 
249  HasherGcrypt& operator=(const HasherGcrypt &other) {
250  #ifdef ROSE_HAVE_LIBGCRYPT
251  gcry_md_close(md_);
252  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
253  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
254  #else
255  throw Exception("ROSE was not configured with libgcrypt");
256  #endif
257  }
258 
259  void clear() {
260  #ifdef ROSE_HAVE_LIBGCRYPT
261  gcry_md_reset(md_);
262  #endif
263  Hasher::clear();
264  }
265 
266  const Digest& digest() {
267  if (digest_.empty()) {
268  #ifdef ROSE_HAVE_LIBGCRYPT
269  gcry_md_final(md_);
270  digest_.resize(gcry_md_get_algo_dlen(hashAlgorithmId), 0);
271  uint8_t *d = gcry_md_read(md_, hashAlgorithmId);
272  ASSERT_not_null(d);
273  memcpy(&digest_[0], d, digest_.size());
274  #else
275  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
276  #endif
277  }
278  return Hasher::digest();
279  }
280 
281  void append(const uint8_t *message, size_t messageSize) {
282  ASSERT_require(message || 0==messageSize);
283  #ifdef ROSE_HAVE_LIBGCRYPT
284  if (!digest_.empty())
285  throw Exception("cannot append after returning digest");
286  if (messageSize > 0)
287  gcry_md_write(md_, message, messageSize);
288  #else
289  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
290  #endif
291  }
292 };
293 
294 #ifdef ROSE_HAVE_LIBGCRYPT
295 typedef HasherGcrypt<GCRY_MD_MD5> HasherMd5;
296 typedef HasherGcrypt<GCRY_MD_SHA1> HasherSha1;
297 typedef HasherGcrypt<GCRY_MD_SHA256> HasherSha256;
298 typedef HasherGcrypt<GCRY_MD_SHA384> HasherSha384;
299 typedef HasherGcrypt<GCRY_MD_SHA512> HasherSha512;
300 typedef HasherGcrypt<GCRY_MD_CRC32> HasherCrc32;
301 #else // the template argument for the following unimplemented hashers is arbitrary and they can all be the same
308 #endif
309 
311 class ROSE_DLL_API HasherFnv: public Hasher {
312  uint64_t partial_;
313 public:
314  HasherFnv(): partial_(0xcbf29ce484222325ull) {}
315  const Digest& digest() ROSE_OVERRIDE;
316  void append(const uint8_t *message, size_t messageSize) ROSE_OVERRIDE;
317  uint64_t partial() const { return partial_; }
318 };
319 
323 class ROSE_DLL_API HasherSha256Builtin: public Hasher {
324  static const uint32_t roundConstants_[64]; // statically-generated constants for the algorithm
325  uint32_t state_[8]; // 256 bits of state information
326  size_t processedBytes_; // number of message bytes hashed (excludes padding)
327  std::vector<uint8_t> leftoverBytes_; // message bytes inserted but not yet hashed
328 public:
330  void clear() ROSE_OVERRIDE;
331  const Digest& digest() ROSE_OVERRIDE;
332  void append(const uint8_t *message, size_t messageSize) ROSE_OVERRIDE;
333 private:
334  uint8_t messageByte(size_t index, const uint8_t *message, size_t messageSize);
335  bool getNextChunk(const uint8_t* &message /*in,out*/, size_t &messageSize /*in,out*/, uint32_t words[16] /*out*/);
336  void accumulateChunk(const uint32_t chunk[16]);
337 };
338 
342 template<class T, class U>
343 std::vector<std::pair<T, U> >
344 zip(const std::vector<T> &first, const std::vector<U> &second) {
345  size_t retvalSize = std::min(first.size(), second.size());
346  std::vector<std::pair<T, U> > retval;
347  retval.reserve(retvalSize);
348  for (size_t i = 0; i < retvalSize; ++i)
349  retval.push_back(std::pair<T, U>(first[i], second[i]));
350  return retval;
351 }
352 
354 template<class T, class U>
355 std::pair<std::vector<T>, std::vector<U> >
356 unzip(const std::vector<std::pair<T, U> > &pairs) {
357  std::pair<std::vector<T>, std::vector<U> > retval;
358  retval.first.reserve(pairs.size());
359  retval.second.reserve(pairs.size());
360  for (size_t i = 0; i < pairs.size(); ++i) {
361  retval.first.push_back(pairs[i].first);
362  retval.second.push_back(pairs[i].second);
363  }
364  return retval;
365 }
366 
367 } // namespace
368 } // namespace
369 
371 
373 ROSE_DLL_API std::ostream& operator<<(std::ostream&, Rose::Combinatorics::Hasher&);
374 
375 #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.
STL namespace.
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 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.
void shuffle(std::vector< T > &vector, size_t nitems=(size_t)(-1), size_t limit=(size_t)(-1), LinearCongruentialGenerator *lcg=NULL)
Shuffle the values of a vector.
Definition: Combinatorics.h:73
HasherGcrypt< 0 > HasherSha256
SHA-256 hasher.
HasherGcrypt< 0 > HasherMd5
MD5 hasher.
Linear congruential generator.
const Digest & digest()
Return the digest.
HasherGcrypt< 0 > HasherSha512
SHA-512 hasher.