Function TestExhaustive

src/minisketch/src/test.cpp:49–123

Test properties by exhaustively decoding all 2**(bits*capacity) sketches * with specified capacity and bits. */

/** Test properties by exhaustively decoding all 2**(bits*capacity) sketches
 *  with specified capacity and bits. */
void TestExhaustive(uint32_t bits, size_t capacity) {
    auto sketches = CreateSketches(bits, capacity);
    if (sketches.empty()) return;
    auto sketches_rebuild = CreateSketches(bits, capacity);

    std::vector<unsigned char> serialized;
    std::vector<unsigned char> serialized_empty;
    std::vector<uint64_t> counts; //!< counts[i] = number of results with i elements
    std::vector<uint64_t> elements_0; //!< Result vector for elements for impl=0
    std::vector<uint64_t> elements_other; //!< Result vector for elements for other impls
    std::vector<uint64_t> elements_too_small; //!< Result vector that's too small

    counts.resize(capacity + 1);
    serialized.resize(sketches[0].GetSerializedSize());
    serialized_empty.resize(sketches[0].GetSerializedSize());

    // Iterate over all (bits)-bit sketches with (capacity) syndromes.
    for (uint64_t x = 0; (x >> (bits * capacity)) == 0; ++x) {
        // Construct the serialization.
        for (size_t i = 0; i < serialized.size(); ++i) {
            serialized[i] = (x >> (i * 8)) & 0xFF;
        }

        // Compute all the solutions
        sketches[0].Deserialize(serialized);
        elements_0.resize(64);
        bool decodable_0 = sketches[0].Decode(elements_0);
        std::sort(elements_0.begin(), elements_0.end());

        // Verify that decoding with other implementations agrees.
        for (size_t impl = 1; impl < sketches.size(); ++impl) {
            sketches[impl].Deserialize(serialized);
            elements_other.resize(64);
            bool decodable_other = sketches[impl].Decode(elements_other);
            CHECK(decodable_other == decodable_0);
            std::sort(elements_other.begin(), elements_other.end());
            CHECK(elements_other == elements_0);
        }

        // If there are solutions:
        if (decodable_0) {
            if (!elements_0.empty()) {
                // Decoding with limit one less than the number of elements should fail.
                elements_too_small.resize(elements_0.size() - 1);
                for (size_t impl = 0; impl < sketches.size(); ++impl) {
                    CHECK(!sketches[impl].Decode(elements_too_small));
                }
            }

            // Reconstruct the sketch from the solutions.
            for (size_t impl = 0; impl < sketches.size(); ++impl) {
                // Clear the sketch.
                sketches_rebuild[impl].Deserialize(serialized_empty);
                // Load all decoded elements into it.
                for (uint64_t elem : elements_0) {
                    CHECK(elem != 0);
                    CHECK(elem >> bits == 0);
                    sketches_rebuild[impl].Add(elem);