1#ifndef JNGEN_INCLUDE_RNDS_INL_H2#error File "rnds_inl.h" must not be included directly.3#include "../rnds.h" // for completion emgine4#endif56namespace jngen {78namespace detail {910int popcount(long long x) {11    int res = 0;12    while (x) {13        ++res;14        x &= x-1;15    }16    return res;17}1819int trailingZeroes(long long x) {20    int res = 0;21    ENSURE(x != 0);22    while (!(x&1)) {23        ++res;24        x >>= 1;25    }26    return res;27}2829std::string parseAllowedChars(std::string pattern) {30    std::string result;31    pattern += "\0\0";32    for (size_t i = 0; i < pattern.length(); ++i) {33        if (pattern[i] == '-') {34            result += '-';35        } else if (pattern[i+1] == '-' && pattern[i+2] != '\0') {36            for (char c = pattern[i]; c <= pattern[i+2]; ++c) {37                result += c;38            }39            i += 2;40        } else {41            result += pattern[i];42        }43    }44    std::sort(result.begin(), result.end());45    return result;46}4748std::vector<std::string> extendAntiHash(49        const std::vector<std::string>& chars,50        HashBase base,51        int count)52{53    ENSURE(count == 2, "Count != 2 is not supported (yet)");5455    size_t baseLength = chars[0].size();56    for (const auto& s: chars) {57        ensure(s.size() == baseLength);58    }5960    long long mod = base.first;61    long long p = base.second;6263    long long pPower = 1;64    for (size_t i = 0; i != baseLength; ++i) {65        pPower = (pPower * p) % mod;66    }6768    std::vector<long long> charHashes;69    for (const auto& s: chars) {70        long long hash = 0;71        for (char c: s) {72            hash = (hash * p + c) % mod;73        }74        charHashes.push_back(hash);75    }7677    auto computeHash = [&charHashes, mod, pPower](const std::vector<int>& a) {78        long long hash = 0;79        for (int x: a) {80            hash = (hash * pPower + charHashes[x]) % mod;81        }82        return hash;83    };8485    // This bounds were achieved empirically and should be justified.86    int needForMatch;87    if (count == 2) {88        needForMatch = 5 * pow(double(mod), 0.5);89    } else {90        ENSURE(false, "Only count = 2 is supported yet");91    }9293    int length = 2;94    double wordCount = pow(double(chars.size()), double(length));9596    while (true) {97        ++length;98        wordCount *= chars.size();99        if (wordCount < needForMatch) {100            continue;101        }102103        std::vector<std::pair<long long, Array>> words;104        std::map<long long, int> hashCount;105        std::set<Array> used;106107        for (int i = 0; i < needForMatch; ++i) {108            Array w = Array::random(length, chars.size());109            if (used.count(w)) {110                --i;111                continue;112            }113            used.insert(w);114            long long hash = computeHash(w);115            words.emplace_back(hash, w);116            if (++hashCount[hash] == count) {117                std::vector<std::string> result;118                for (const auto& kv: words) {119                    if (kv.first == hash) {120                        std::string word;121                        for (int c: kv.second) {122                            word += chars[c];123                        }124                        result.push_back(word);125                    }126                }127                return result;128            }129        }130    }131}132133StringPair minimalAntiHashTest(134        std::vector<HashBase> bases,135        const std::string allowedChars)136{137    for (auto base: bases) {138        ensure(base.first >= 0, "0 < MOD must hold");139        ensure(140            base.first <= (long long)(2e9),141            "Modules larger than 2'000'000'000 are not supported yet");142        ensure(143            0 < base.second && base.second < base.first,144            "0 <= P < MOD must hold");145    }146147    std::vector<int> counts;148    if (bases.size() == 1) {149        counts = {2};150    } else if (bases.size() == 2) {151        counts = {2, 2};152    } else {153        counts.assign(bases.size(), 2);154    }155156    std::vector<std::string> cur;157    for (char c: allowedChars) {158        cur.emplace_back(1, c);159    }160161    for (size_t i = 0; i != bases.size(); ++i) {162        cur = extendAntiHash(cur, bases[i], counts[i]);163        ensure(static_cast<int>(cur.size()) == counts[i],164            "Cannot generate long enough pair with same hash");165    }166167    return {cur[0], cur[1]};168}169170} // namespace detail171172173std::string StringRandom::random(int len, const std::string& alphabet) {174    checkLargeParameter(len);175    std::string chars = detail::parseAllowedChars(alphabet);176    std::string res;177    res.reserve(len);178    for (int i = 0; i < len; ++i) {179        res += choice(chars);180    }181    return res;182}183184std::string StringRandom::thueMorse(int len, char first, char second) {185    ensure(len >= 0);186    checkLargeParameter(len);187    std::string res(len, ' ');188    for (int i = 0; i < len; ++i) {189        res[i] = detail::popcount(i)%2 == 0 ? first : second;190    }191    return res;192}193194std::string StringRandom::abacaba(int len, char first) {195    ensure(len >= 0);196    checkLargeParameter(len);197    std::string res(len, ' ');198    for (int i = 0; i < len; ++i) {199        res[i] = first + detail::trailingZeroes(~i);200    }201    return res;202}203204StringPair StringRandom::antiHash(205        const std::vector<HashBase>& bases,206        const std::string& alphabet,207        int length)208{209    checkLargeParameter(length);210    std::string allowedChars = detail::parseAllowedChars(alphabet);211    StringPair result = detail::minimalAntiHashTest(bases, allowedChars);212213    if (length == -1) {214        return result;215    }216217    ensure(218        static_cast<int>(result.first.length()) <= length,219        "Cannot generate enough long anti-hash test");220221    int extraLength = length - result.first.length();222    int leftSize = rnd.next(0, extraLength);223224    std::string left = rnd.next(format("[%s]{%d}", alphabet.c_str(), leftSize));225    std::string right =226        rnd.next(format("[%s]{%d}", alphabet.c_str(), extraLength - leftSize));227228    return {229        left + result.first + right,230        left + result.second + right231    };232}233234} // namespace jngen