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]);
155 void insert(
const std::string &x) { append((
const uint8_t*)x.c_str(), x.size()); }
156 void insert(uint64_t x) { append((uint8_t*)&x,
sizeof x); }
157 void insert(
const uint8_t *x,
size_t size) { append(x, size); }
158 void insert(
const std::vector<uint8_t> &v) { append(v.data(), v.size()); }
161 while (stream.good()) {
162 stream.read(buf,
sizeof buf);
163 append((
const uint8_t*)buf, stream.gcount());
174 virtual void append(
const uint8_t *message,
size_t messageSize) = 0;
177 static std::string toString(
const Digest&);
183 std::string toString();
189 void print(std::ostream&);
200 virtual boost::shared_ptr<Hasher> create()
const = 0;
233 HasherFactory::Instance().registerMaker(hashType,
this);
240 virtual boost::shared_ptr<Hasher>
create()
const
243 boost::shared_ptr<Hasher> hashPtr(hasher);
269 void registerMaker(
const std::string& hashType,
IHasherMaker* createHasherPtr);
278 boost::shared_ptr<Hasher> createHasher(
const std::string& hashType)
const;
289 std::map<std::string, IHasherMaker* > hashMakers;
298 template<
int hashAlgorithmId>
300 #ifdef ROSE_HAVE_LIBGCRYPT
306 #ifdef ROSE_HAVE_LIBGCRYPT
307 if (gcry_md_open(&md_, hashAlgorithmId, 0) != GPG_ERR_NO_ERROR)
308 throw Exception(
"cannot initialize libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
310 throw Exception(
"ROSE was not configured with libgcrypt");
315 #ifdef ROSE_HAVE_LIBGCRYPT
316 if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
317 throw Exception(
"cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
319 throw Exception(
"ROSE was not configured with libgcrypt");
324 #ifdef ROSE_HAVE_LIBGCRYPT
330 #ifdef ROSE_HAVE_LIBGCRYPT
332 if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
333 throw Exception(
"cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
335 throw Exception(
"ROSE was not configured with libgcrypt");
340 #ifdef ROSE_HAVE_LIBGCRYPT
347 if (digest_.empty()) {
348 #ifdef ROSE_HAVE_LIBGCRYPT
350 digest_.resize(gcry_md_get_algo_dlen(hashAlgorithmId), 0);
351 uint8_t *d = gcry_md_read(md_, hashAlgorithmId);
353 memcpy(&digest_[0], d, digest_.size());
355 ASSERT_not_reachable(
"ROSE was not configured with libgcrypt");
361 void append(
const uint8_t *message,
size_t messageSize) {
362 ASSERT_require(message || 0==messageSize);
363 #ifdef ROSE_HAVE_LIBGCRYPT
364 if (!digest_.empty())
365 throw Exception(
"cannot append after returning digest");
367 gcry_md_write(md_, message, messageSize);
369 ASSERT_not_reachable(
"ROSE was not configured with libgcrypt");
374 #ifdef ROSE_HAVE_LIBGCRYPT
375 typedef HasherGcrypt<GCRY_MD_MD5>
HasherMd5;
376 typedef HasherGcrypt<GCRY_MD_SHA1>
HasherSha1;
381 #else // the template argument for the following unimplemented hashers is arbitrary and they can all be the same
396 HasherFnv(): partial_(0xcbf29ce484222325ull) {}
397 const Digest& digest()
override;
398 void append(
const uint8_t *message,
size_t messageSize)
override;
399 uint64_t partial()
const {
return partial_; }
406 static const uint32_t roundConstants_[64];
408 size_t processedBytes_;
409 std::vector<uint8_t> leftoverBytes_;
412 void clear()
override;
413 const Digest& digest()
override;
414 void append(
const uint8_t *message,
size_t messageSize)
override;
416 uint8_t messageByte(
size_t index,
const uint8_t *message,
size_t messageSize);
417 bool getNextChunk(
const uint8_t* &message ,
size_t &messageSize , uint32_t words[16] );
418 void accumulateChunk(
const uint32_t chunk[16]);
424 template<
class T,
class U>
425 std::vector<std::pair<T, U> >
426 zip(
const std::vector<T> &first,
const std::vector<U> &second) {
427 size_t retvalSize = std::min(first.size(), second.size());
428 std::vector<std::pair<T, U> > retval;
429 retval.reserve(retvalSize);
430 for (
size_t i = 0; i < retvalSize; ++i)
431 retval.push_back(std::pair<T, U>(first[i], second[i]));
436 template<
class T,
class U>
437 std::pair<std::vector<T>, std::vector<U> >
438 unzip(
const std::vector<std::pair<T, U> > &pairs) {
439 std::pair<std::vector<T>, std::vector<U> > retval;
440 retval.first.reserve(pairs.size());
441 retval.second.reserve(pairs.size());
442 for (
size_t i = 0; i < pairs.size(); ++i) {
443 retval.first.push_back(pairs[i].first);
444 retval.second.push_back(pairs[i].second);