Combinatorics.h

#ifndef ROSE_Combinatorics_H
#define ROSE_Combinatorics_H
 
#include <rosePublicConfig.h>
 
#include <Rose/Constants.h>
#include <ROSE_DEPRECATED.h>
#include <ROSE_UNUSED.h>
 
#include <algorithm>
#include <cassert>
#include <istream>
#include <list>
#include <memory>
#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(const T n) {
    T retval = 1;
    while (n>1) {
        const T next = retval * n--;
        assert(next > retval); // overflow; signed overflow is UB, so this likely doesn't work right when T is signed
        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, const 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]);
    }
}
shuffle(std::vector<T> &vector, size_t nitems = UNLIMITED, size_t limit = UNLIMITED) {…}
 
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]];
}
reorder(std::vector<T> &values, const std::vector<size_t> &remap) {…}
 
ROSE_DLL_API std::string toBase62String(uint64_t);
 
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 () {}
    };
    class Exception: public Rose::Exception {…};
    
protected:
    Digest digest_;
 
public:
    virtual ~Hasher() {}
 
    virtual void clear();
 
    virtual const Digest& digest();
 
    void insert(const std::string&);
    void insert(uint64_t);
    void insert(const uint8_t *bytes, size_t nBytes);
    void insert(const std::vector<uint8_t>&);
    void insert(std::istream&);
    virtual void append(const uint8_t *message, size_t messageSize) = 0;
 
    static std::string toString(const Digest&);
 
    std::string toString();
 
    uint64_t toU64();
    uint64_t toU64(const Digest&);
    // [Robb Matzke 2025-05-16]: deprecated; casting to another type should have "to" in the name, like "toString" above.
    uint64_t make64Bits() ROSE_DEPRECATED("use toU64");
    uint64_t make64Bits(const Digest&) ROSE_DEPRECATED("use toU64");
 
    void print(std::ostream&);
 
    class IHasherMaker {
    public:
        virtual std::shared_ptr<Hasher> create() const = 0;
        virtual ~IHasherMaker() {}
    };
    class IHasherMaker {…};
    
    template<typename T>
    class HasherMaker : public IHasherMaker {
    public:
        HasherMaker(const std::string& hashType) {
            HasherFactory::instance().registerMaker(hashType, this);
        }
        HasherMaker(const std::string& hashType) {…}
 
        virtual std::shared_ptr<Hasher> create() const {
            return std::make_shared<T>();
        }
        virtual std::shared_ptr<Hasher> create() const  {…}
    };
    class HasherMaker : public IHasherMaker {…};
 
    class HasherFactory {
    public:
        static HasherFactory& instance();
 
        // [Robb Matzke 2025-05-16]: deprecated; violates ROSE public function naming convention
        static HasherFactory& Instance() ROSE_DEPRECATED("use instance");
        
        void registerMaker(const std::string& hashType, IHasherMaker* createHasherPtr);
        
        std::shared_ptr<Hasher> createHasher(const std::string& hashType) const;
        
    private:
        HasherFactory() {}
        
        // Non-copyable
        HasherFactory(const HasherFactory&) = delete;
        HasherFactory& operator=(const HasherFactory&) = delete;
        
        // Maps keys to @ref HasherMaker
        std::map<std::string, IHasherMaker* > hashMakers;
    };
    class HasherFactory {…};
};
class ROSE_DLL_API Hasher {…};
 
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();
    }
    void 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();
    }
    const Digest& 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
    }
    void append(const uint8_t *message, size_t messageSize) {…}
};
class HasherGcrypt: public Hasher {…};
 
#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 HasherFnv: public Hasher {…};
 
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]);
};
class ROSE_DLL_API HasherSha256Builtin: public Hasher {…};
 
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;
}
zip(const std::vector<T> &first, const std::vector<U> &second) {…}
 
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;
}
unzip(const std::vector<std::pair<T, U> > &pairs) {…}
 
} // namespace
namespace Combinatorics {…}
} // namespace
 
 
ROSE_DLL_API std::ostream& operator<<(std::ostream&, Rose::Combinatorics::Hasher&);
 
#endif