1 #ifndef ROSE_Combinatorics_H
2 #define ROSE_Combinatorics_H
4 #include <rosePublicConfig.h>
6 #include <boost/shared_ptr.hpp>
13 #include <Rose/Exception.h>
14 #include <Sawyer/Assert.h>
15 #include <Sawyer/Synchronization.h>
21 #ifdef ROSE_HAVE_LIBGCRYPT
28 namespace Combinatorics {
37 T next = retval * n--;
54 permute(std::vector<T> &values, uint64_t pn,
size_t sz =
UNLIMITED)
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]);
77 nitems = std::min(nitems, vector.size());
78 limit = std::min(limit, nitems);
80 for (
size_t i=0; i<limit; ++i) {
82 std::swap(vector[i], vector[j]);
113 reorder(std::vector<T> &values,
const std::vector<size_t> &remap) {
114 assert(values.size() == remap.size());
117 std::vector<T> old = values;
118 for (
size_t i = 0; i < old.size(); ++i)
119 values[i] = old[remap[i]];
178 virtual void clear() { digest_ = Digest(); }
184 virtual const Digest&
digest() {
return digest_; }
191 void insert(
const std::string &x) { append((
const uint8_t*)x.c_str(), x.size()); }
192 void insert(uint64_t x) { append((uint8_t*)&x,
sizeof x); }
193 void insert(
const uint8_t *x,
size_t size) { append(x, size); }
194 void insert(
const std::vector<uint8_t> &v) { append(v.data(), v.size()); }
197 while (stream.good()) {
198 stream.read(buf,
sizeof buf);
199 append((
const uint8_t*)buf, stream.gcount());
210 virtual void append(
const uint8_t *message,
size_t messageSize) = 0;
213 static std::string toString(
const Digest&);
219 std::string toString();
225 void print(std::ostream&);
236 virtual boost::shared_ptr<Hasher> create()
const = 0;
269 HasherFactory::Instance().registerMaker(hashType,
this);
276 virtual boost::shared_ptr<Hasher>
create()
const
279 boost::shared_ptr<Hasher> hashPtr(hasher);
305 void registerMaker(
const std::string& hashType,
IHasherMaker* createHasherPtr);
314 boost::shared_ptr<Hasher> createHasher(
const std::string& hashType)
const;
325 std::map<std::string, IHasherMaker* > hashMakers;
334 template<
int hashAlgorithmId>
336 #ifdef ROSE_HAVE_LIBGCRYPT
342 #ifdef ROSE_HAVE_LIBGCRYPT
343 if (gcry_md_open(&md_, hashAlgorithmId, 0) != GPG_ERR_NO_ERROR)
344 throw Exception(
"cannot initialize libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
346 throw Exception(
"ROSE was not configured with libgcrypt");
351 #ifdef ROSE_HAVE_LIBGCRYPT
352 if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
353 throw Exception(
"cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
355 throw Exception(
"ROSE was not configured with libgcrypt");
360 #ifdef ROSE_HAVE_LIBGCRYPT
366 #ifdef ROSE_HAVE_LIBGCRYPT
368 if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
369 throw Exception(
"cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
371 throw Exception(
"ROSE was not configured with libgcrypt");
376 #ifdef ROSE_HAVE_LIBGCRYPT
383 if (digest_.empty()) {
384 #ifdef ROSE_HAVE_LIBGCRYPT
386 digest_.resize(gcry_md_get_algo_dlen(hashAlgorithmId), 0);
387 uint8_t *d = gcry_md_read(md_, hashAlgorithmId);
389 memcpy(&digest_[0], d, digest_.size());
391 ASSERT_not_reachable(
"ROSE was not configured with libgcrypt");
397 void append(
const uint8_t *message,
size_t messageSize) {
398 ASSERT_require(message || 0==messageSize);
399 #ifdef ROSE_HAVE_LIBGCRYPT
400 if (!digest_.empty())
401 throw Exception(
"cannot append after returning digest");
403 gcry_md_write(md_, message, messageSize);
405 ASSERT_not_reachable(
"ROSE was not configured with libgcrypt");
410 #ifdef ROSE_HAVE_LIBGCRYPT
411 typedef HasherGcrypt<GCRY_MD_MD5>
HasherMd5;
412 typedef HasherGcrypt<GCRY_MD_SHA1>
HasherSha1;
417 #else // the template argument for the following unimplemented hashers is arbitrary and they can all be the same
432 HasherFnv(): partial_(0xcbf29ce484222325ull) {}
433 const Digest& digest()
override;
434 void append(
const uint8_t *message,
size_t messageSize)
override;
435 uint64_t partial()
const {
return partial_; }
442 static const uint32_t roundConstants_[64];
444 size_t processedBytes_;
445 std::vector<uint8_t> leftoverBytes_;
448 void clear()
override;
449 const Digest& digest()
override;
450 void append(
const uint8_t *message,
size_t messageSize)
override;
452 uint8_t messageByte(
size_t index,
const uint8_t *message,
size_t messageSize);
453 bool getNextChunk(
const uint8_t* &message ,
size_t &messageSize , uint32_t words[16] );
454 void accumulateChunk(
const uint32_t chunk[16]);
460 template<
class T,
class U>
461 std::vector<std::pair<T, U> >
462 zip(
const std::vector<T> &first,
const std::vector<U> &second) {
463 size_t retvalSize = std::min(first.size(), second.size());
464 std::vector<std::pair<T, U> > retval;
465 retval.reserve(retvalSize);
466 for (
size_t i = 0; i < retvalSize; ++i)
467 retval.push_back(std::pair<T, U>(first[i], second[i]));
472 template<
class T,
class U>
473 std::pair<std::vector<T>, std::vector<U> >
474 unzip(
const std::vector<std::pair<T, U> > &pairs) {
475 std::pair<std::vector<T>, std::vector<U> > retval;
476 retval.first.reserve(pairs.size());
477 retval.second.reserve(pairs.size());
478 for (
size_t i = 0; i < pairs.size(); ++i) {
479 retval.first.push_back(pairs[i].first);
480 retval.second.push_back(pairs[i].second);
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.
HasherGcrypt< 0 > HasherSha384
SHA-384 hasher.
void shuffle(std::vector< T > &vector, size_t nitems=UNLIMITED, size_t limit=UNLIMITED)
Shuffle the values of a vector.
Main namespace for the ROSE library.
const size_t UNLIMITED(static_cast< size_t >(-1))
Effictively unlimited size.
HasherGcrypt< 0 > HasherSha1
SHA1 hasher.
Common subclass all the classes that construct Hashers (for the HasherFactory)
ROSE_DLL_API bool flip_coin()
Simulate flipping a coin.
void insert(const std::vector< uint8_t > &v)
Insert data into the digest.
size_t fastRandomIndex(size_t n, size_t seed=0)
Thread-safe random number generator.
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.
Templated to create any Hasher and register it with HasherFactory.
void reorder(std::vector< T > &values, const std::vector< size_t > &remap)
Reorder the values of one vector according to another.
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...
void insert(std::istream &stream)
Insert data into the digest.
HasherMaker(const std::string &hashType)
Creates a HasherMaker and registers it with HasherFactory.
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.
HasherFactory is a singleton that creates and returns Hashers by name.
const Digest & digest()
Return the digest.
Base class for all ROSE exceptions.
HasherGcrypt< 0 > HasherSha512
SHA-512 hasher.