Combinatorics.h

#ifndef ROSE_Combinatorics_H
#define ROSE_Combinatorics_H
 
#include <rosePublicConfig.h>
 
#include <Rose/Constants.h>
#include <ROSE_UNUSED.h>
 
#include <boost/shared_ptr.hpp>
 
#include <algorithm>
#include <cassert>
#include <istream>
#include <list>
#include <ostream>
#include <Rose/Exception.h>
#include <Sawyer/Assert.h>
#include <Sawyer/Synchronization.h>
#include <stdexcept>
#include <stdint.h>
#include <string>
#include <vector>
 
#ifdef ROSE_HAVE_LIBGCRYPT
#include <gcrypt.h>
#endif
 
namespace Rose {
 
namespace Combinatorics {
 
template<typename T>
static T
factorial(T n)
{
    T retval = 1;
    while (n>1) {
        T next = retval * n--;
        assert(next>retval); // overflow
        retval = next;
    }
    return retval;
}
 
ROSE_DLL_API bool flip_coin();
 
template<typename T>
static void
permute(std::vector<T> &values/*in,out*/, uint64_t pn, size_t sz = UNLIMITED)
{
    if (UNLIMITED == sz)
        sz = values.size();
    assert(sz<=values.size());
    assert(pn<factorial(sz));
    for (size_t i=0; i<sz; ++i) {
        uint64_t radix = sz - i;
        uint64_t idx = pn % radix;
        std::swap(values[i+idx], values[i]);
        pn /= radix;
    }
}
 
template<typename T>
void
shuffle(std::vector<T> &vector, size_t nitems = UNLIMITED, size_t limit = UNLIMITED)
{
    nitems = std::min(nitems, vector.size());
    limit = std::min(limit, nitems);
 
    for (size_t i=0; i<limit; ++i) {
        size_t j = Sawyer::fastRandomIndex(nitems);
        std::swap(vector[i], vector[j]);
    }
}
 
template<class T>
void
reorder(std::vector<T> &values, const std::vector<size_t> &remap) {
    assert(values.size() == remap.size());
 
    // O(n) implementation using a temporary vector. Alternatively, we could use an O(n^2) algorithm that uses constant space.
    std::vector<T> old = values;
    for (size_t i = 0; i < old.size(); ++i)
        values[i] = old[remap[i]];
}
 
ROSE_DLL_API std::string toBase62String(uint64_t num);
 
ROSE_DLL_API uint64_t fromBase62String(const std::string& base62);
 
class ROSE_DLL_API Hasher {
public:
    typedef std::vector<uint8_t> Digest;
 
    class Exception: public Rose::Exception {
    public:
        Exception(const std::string &mesg): Rose::Exception(mesg) {}
        ~Exception() throw () {}
    };
    
protected:
    Digest digest_;
 
public:
    virtual ~Hasher() {}
 
    virtual void clear() { digest_ = Digest(); }
 
    virtual const Digest& digest() { return digest_; }
 
    void insert(const std::string &x) { append((const uint8_t*)x.c_str(), x.size()); }
    void insert(uint64_t x) { append((uint8_t*)&x, sizeof x); }
    void insert(const uint8_t *x, size_t size) { append(x, size); }
    void insert(const std::vector<uint8_t> &v) { append(v.data(), v.size()); }
    void insert(std::istream &stream) {
        char buf[4096];                                 // multiple of 64
        while (stream.good()) {
            stream.read(buf, sizeof buf);
            append((const uint8_t*)buf, stream.gcount());
        }
        if (!stream.eof())
            throw Hasher::Exception("failed to read data from file");
    }
    virtual void append(const uint8_t *message, size_t messageSize) = 0;
 
    static std::string toString(const Digest&);
 
    std::string toString();
 
    uint64_t make64Bits();
    uint64_t make64Bits(const Digest&);
    void print(std::ostream&);
 
    class IHasherMaker
    {
    public:
        virtual boost::shared_ptr<Hasher> create() const = 0;
        virtual ~IHasherMaker() {}
    };
    
    template<typename T>
    class HasherMaker : public IHasherMaker
    {
    public:
        HasherMaker(const std::string& hashType)
        {
            HasherFactory::Instance().registerMaker(hashType, this);
        }
 
        virtual boost::shared_ptr<Hasher> create() const
        {
            T* hasher = new T;
            boost::shared_ptr<Hasher> hashPtr(hasher);
            return hashPtr;
        }
        
    };
 
    class HasherFactory
    {
    public:
    static HasherFactory& Instance();
        
    void registerMaker(const std::string& hashType, IHasherMaker* createHasherPtr);
        
    boost::shared_ptr<Hasher> createHasher(const std::string& hashType) const;
        
    private:
        HasherFactory() {}
        
        HasherFactory(const HasherFactory& other); 
        HasherFactory& operator=(const HasherFactory& other);
        
        std::map<std::string, IHasherMaker* > hashMakers;
    };
};
 
template<int hashAlgorithmId>
class HasherGcrypt: public Hasher {
#ifdef ROSE_HAVE_LIBGCRYPT
    gcry_md_hd_t md_;
#endif
 
public:
    HasherGcrypt() {
      #ifdef ROSE_HAVE_LIBGCRYPT
        if (gcry_md_open(&md_, hashAlgorithmId, 0) != GPG_ERR_NO_ERROR)
            throw Exception("cannot initialize libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
      #else
        throw Exception("ROSE was not configured with libgcrypt");
      #endif
    }
 
    HasherGcrypt(const HasherGcrypt &other) {
      #ifdef ROSE_HAVE_LIBGCRYPT
        if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
            throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
      #else
        ROSE_UNUSED(other);
        throw Exception("ROSE was not configured with libgcrypt");
      #endif
    }
 
    ~HasherGcrypt() {
      #ifdef ROSE_HAVE_LIBGCRYPT
        gcry_md_close(md_);
      #endif
    }
 
    HasherGcrypt& operator=(const HasherGcrypt &other) {
      #ifdef ROSE_HAVE_LIBGCRYPT
        gcry_md_close(md_);
        if (gcry_md_copy(&md_, other.md_) != GPG_ERR_NO_ERROR)
            throw Exception("cannot copy libgcrypt hash " + std::string(gcry_md_algo_name(hashAlgorithmId)));
      #else
        ROSE_UNUSED(other);
        throw Exception("ROSE was not configured with libgcrypt");
      #endif
    }
    
    void clear() {
      #ifdef ROSE_HAVE_LIBGCRYPT
        gcry_md_reset(md_);
      #endif
        Hasher::clear();
    }
 
    const Digest& digest() {
        if (digest_.empty()) {
          #ifdef ROSE_HAVE_LIBGCRYPT
            gcry_md_final(md_);
            digest_.resize(gcry_md_get_algo_dlen(hashAlgorithmId), 0);
            uint8_t *d = gcry_md_read(md_, hashAlgorithmId);
            ASSERT_not_null(d);
            memcpy(&digest_[0], d, digest_.size());
          #else
            ASSERT_not_reachable("ROSE was not configured with libgcrypt");
          #endif
        }
        return Hasher::digest();
    }
 
    void append(const uint8_t *message, size_t messageSize) {
        ASSERT_require(message || 0==messageSize);
      #ifdef ROSE_HAVE_LIBGCRYPT
        if (!digest_.empty())
            throw Exception("cannot append after returning digest");
        if (messageSize > 0)
            gcry_md_write(md_, message, messageSize);
      #else
        ASSERT_not_reachable("ROSE was not configured with libgcrypt");
      #endif
    }
};
 
#ifdef ROSE_HAVE_LIBGCRYPT
typedef HasherGcrypt<GCRY_MD_MD5> HasherMd5;            
typedef HasherGcrypt<GCRY_MD_SHA1> HasherSha1;          
typedef HasherGcrypt<GCRY_MD_SHA256> HasherSha256;      
typedef HasherGcrypt<GCRY_MD_SHA384> HasherSha384;      
typedef HasherGcrypt<GCRY_MD_SHA512> HasherSha512;      
typedef HasherGcrypt<GCRY_MD_CRC32> HasherCrc32;        
#else // the template argument for the following unimplemented hashers is arbitrary and they can all be the same
typedef HasherGcrypt<0> HasherMd5;                      
typedef HasherGcrypt<0> HasherSha1;                     
typedef HasherGcrypt<0> HasherSha256;                   
typedef HasherGcrypt<0> HasherSha384;                   
typedef HasherGcrypt<0> HasherSha512;                   
typedef HasherGcrypt<0> HasherCrc32;                    
#endif
 
 
 
class ROSE_DLL_API HasherFnv: public Hasher {
    uint64_t partial_;
public:
    HasherFnv(): partial_(0xcbf29ce484222325ull) {}
    const Digest& digest() override;
    void append(const uint8_t *message, size_t messageSize) override;
    uint64_t partial() const { return partial_; }
};
 
class ROSE_DLL_API HasherSha256Builtin: public Hasher {
    static const uint32_t roundConstants_[64];          // statically-generated constants for the algorithm
    uint32_t state_[8];                                 // 256 bits of state information
    size_t processedBytes_;                             // number of message bytes hashed (excludes padding)
    std::vector<uint8_t> leftoverBytes_;                // message bytes inserted but not yet hashed
public:
    HasherSha256Builtin();
    void clear() override;
    const Digest& digest() override;
    void append(const uint8_t *message, size_t messageSize) override;
private:
    uint8_t messageByte(size_t index, const uint8_t *message, size_t messageSize);
    bool getNextChunk(const uint8_t* &message /*in,out*/, size_t &messageSize /*in,out*/, uint32_t words[16] /*out*/);
    void accumulateChunk(const uint32_t chunk[16]);
};
 
template<class T, class U>
std::vector<std::pair<T, U> >
zip(const std::vector<T> &first, const std::vector<U> &second) {
    size_t retvalSize = std::min(first.size(), second.size());
    std::vector<std::pair<T, U> > retval;
    retval.reserve(retvalSize);
    for (size_t i = 0; i < retvalSize; ++i)
        retval.push_back(std::pair<T, U>(first[i], second[i]));
    return retval;
}
 
template<class T, class U>
std::pair<std::vector<T>, std::vector<U> >
unzip(const std::vector<std::pair<T, U> > &pairs) {
    std::pair<std::vector<T>, std::vector<U> > retval;
    retval.first.reserve(pairs.size());
    retval.second.reserve(pairs.size());
    for (size_t i = 0; i < pairs.size(); ++i) {
        retval.first.push_back(pairs[i].first);
        retval.second.push_back(pairs[i].second);
    }
    return retval;
}
 
} // namespace
} // namespace
 
 
ROSE_DLL_API std::ostream& operator<<(std::ostream&, Rose::Combinatorics::Hasher&);
 
#endif