ROSE  0.9.10.69
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 <list>
10 #include <ostream>
11 #include <rose_override.h>
12 #include <Sawyer/Assert.h>
13 #include <stdexcept>
14 #include <stdint.h>
15 #include <string>
16 #include <vector>
17 
18 #ifdef ROSE_HAVE_LIBGCRYPT
19 #include <gcrypt.h>
20 #endif
21 
22 namespace Rose {
23 
25 namespace Combinatorics {
26 
28 template<typename T>
29 static T
30 factorial(T n)
31 {
32  T retval = 1;
33  while (n>1) {
34  T next = retval * n--;
35  assert(next>retval); // overflow
36  retval = next;
37  }
38  return retval;
39 }
40 
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 
70 template<typename T>
71 void
72 shuffle(std::vector<T> &vector, size_t nitems=(size_t)(-1), size_t limit=(size_t)(-1), LinearCongruentialGenerator *lcg=NULL)
73 {
74  static LinearCongruentialGenerator my_lcg;
75  if (!lcg)
76  lcg = &my_lcg;
77  nitems = std::min(nitems, vector.size());
78  limit = std::min(limit, nitems);
79 
80  for (size_t i=0; i<limit; ++i)
81  std::swap(vector[i], vector[lcg->next()%nitems]);
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); }
185  virtual void append(const uint8_t *message, size_t messageSize) = 0;
186 
188  static std::string toString(const Digest&);
189 
194  std::string toString();
195 
200  void print(std::ostream&);
201 };
202 
208 template<int hashAlgorithmId>
209 class HasherGcrypt: public Hasher {
210 #ifdef ROSE_HAVE_LIBGCRYPT
211  gcry_md_hd_t md_;
212 #endif
213 
214 public:
215  HasherGcrypt() {
216  #ifdef ROSE_HAVE_LIBGCRYPT
217  if (gcry_md_open(&md_, hashAlgorithmId, 0) != GPG_ERR_NO_ERROR)
218  throw Exception("cannot initialize libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
219  #else
220  throw Exception("ROSE was not configured with libgcrypt");
221  #endif
222  }
223 
224  HasherGcrypt(const HasherGcrypt &other) {
225  #ifdef ROSE_HAVE_LIBGCRYPT
226  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
227  throw Exception("cannot copy 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() {
234  #ifdef ROSE_HAVE_LIBGCRYPT
235  gcry_md_close(md_);
236  #endif
237  }
238 
239  HasherGcrypt& operator=(const HasherGcrypt &other) {
240  #ifdef ROSE_HAVE_LIBGCRYPT
241  gcry_md_close(md_);
242  if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
243  throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
244  #else
245  throw Exception("ROSE was not configured with libgcrypt");
246  #endif
247  }
248 
249  void clear() {
250  #ifdef ROSE_HAVE_LIBGCRYPT
251  gcry_md_reset(md_);
252  #endif
253  Hasher::clear();
254  }
255 
256  const Digest& digest() {
257  if (digest_.empty()) {
258  #ifdef ROSE_HAVE_LIBGCRYPT
259  gcry_md_final(md_);
260  digest_.resize(gcry_md_get_algo_dlen(hashAlgorithmId), 0);
261  uint8_t *d = gcry_md_read(md_, hashAlgorithmId);
262  ASSERT_not_null(d);
263  memcpy(&digest_[0], d, digest_.size());
264  #else
265  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
266  #endif
267  }
268  return Hasher::digest();
269  }
270 
271  void append(const uint8_t *message, size_t messageSize) {
272  ASSERT_require(message || 0==messageSize);
273  #ifdef ROSE_HAVE_LIBGCRYPT
274  if (!digest_.empty())
275  throw Exception("cannot append after returning digest");
276  if (messageSize > 0)
277  gcry_md_write(md_, message, messageSize);
278  #else
279  ASSERT_not_reachable("ROSE was not configured with libgcrypt");
280  #endif
281  }
282 };
283 
284 #ifdef ROSE_HAVE_LIBGCRYPT
285 typedef HasherGcrypt<GCRY_MD_MD5> HasherMd5;
286 typedef HasherGcrypt<GCRY_MD_SHA1> HasherSha1;
287 typedef HasherGcrypt<GCRY_MD_SHA256> HasherSha256;
288 typedef HasherGcrypt<GCRY_MD_SHA384> HasherSha384;
289 typedef HasherGcrypt<GCRY_MD_SHA512> HasherSha512;
290 typedef HasherGcrypt<GCRY_MD_CRC32> HasherCrc32;
291 #else
292 typedef HasherGcrypt<0> HasherMd5; // the template argument is arbitrary and they can all be the same
293 typedef HasherGcrypt<0> HasherSha1;
294 typedef HasherGcrypt<0> HasherSha256;
295 typedef HasherGcrypt<0> HasherSha384;
296 typedef HasherGcrypt<0> HasherSha512;
297 typedef HasherGcrypt<0> HasherCrc32;
298 #endif
299 
301 class ROSE_DLL_API HasherFnv: public Hasher {
302  uint64_t partial_;
303 public:
304  HasherFnv(): partial_(0xcbf29ce484222325ull) {}
305  const Digest& digest() ROSE_OVERRIDE;
306  void append(const uint8_t *message, size_t messageSize);
307  uint64_t partial() const { return partial_; }
308 };
309 
313 template<class T, class U>
314 std::vector<std::pair<T, U> >
315 zip(const std::vector<T> &first, const std::vector<U> &second) {
316  size_t retvalSize = std::min(first.size(), second.size());
317  std::vector<std::pair<T, U> > retval;
318  retval.reserve(retvalSize);
319  for (size_t i = 0; i < retvalSize; ++i)
320  retval.push_back(std::pair<T, U>(first[i], second[i]));
321  return retval;
322 }
323 
325 template<class T, class U>
326 std::pair<std::vector<T>, std::vector<U> >
327 unzip(const std::vector<std::pair<T, U> > &pairs) {
328  std::pair<std::vector<T>, std::vector<U> > retval;
329  retval.first.reserve(pairs.size());
330  retval.second.reserve(pairs.size());
331  for (size_t i = 0; i < pairs.size(); ++i) {
332  retval.first.push_back(pairs[i].first);
333  retval.second.push_back(pairs[i].second);
334  }
335  return retval;
336 }
337 
338 } // namespace
339 } // namespace
340 
342 
344 ROSE_DLL_API std::ostream& operator<<(std::ostream&, Rose::Combinatorics::Hasher&);
345 
346 #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.
Main namespace for the ROSE library.
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.
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:72
Linear congruential generator.
const Digest & digest()
Return the digest.