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