text:
/*
 * Copyright (c) 2015-2017, Intel Corporation
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 *  * Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 *  * Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *  * Neither the name of Intel Corporation nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef AARCH64
#include "config.h"

#include "ue2common.h"
#include "grey.h"
#include "fdr/fdr.h"
#include "fdr/fdr_compile.h"
#include "fdr/fdr_compile_internal.h"
#include "fdr/fdr_engine_description.h"
#include "fdr/teddy_compile.h"
#include "fdr/teddy_engine_description.h"
#include "hwlm/hwlm_internal.h"
#include "util/alloc.h"

#include "database.h"
#include "scratch.h"
#include "gtest/gtest.h"

#include <algorithm>
#include <array>
#include <cmath>
#include <fstream>
#include <boost/random.hpp>

using namespace std;
using namespace testing;
using namespace ue2;

#define NO_TEDDY_FAIL_ALLOWED 0

#if(NO_TEDDY_FAIL_ALLOWED)
#define CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint) ASSERT_TRUE(fdr != nullptr)
#else
#define CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint)                                 \
    {                                                                          \
        auto descr = getTeddyDescription(hint);                                \
        if (descr && fdr == nullptr) {                                         \
            return; /* cannot build Teddy for this set of literals */          \
        } else {                                                               \
            ASSERT_TRUE(fdr != nullptr);                                       \
        }                                                                      \
    }
#endif

namespace {

struct match {
    size_t end;
    u32 id;
    match(size_t end_in, u32 id_in)
        : end(end_in), id(id_in) {}
    bool operator==(const match &b) const {
        return end == b.end && id == b.id;
    }
    bool operator<(const match &b) const {
        return tie(id, end) < tie(b.id, b.end);
    }
    match operator+(size_t adj) {
        return match(end + adj, id);
    }
};

vector<match> matches;

extern "C" {

static
hwlmcb_rv_t decentCallback(size_t end, u32 id,
                           UNUSED struct hs_scratch *scratch) {
    DEBUG_PRINTF("match @%zu : %u\n", end, id);

    matches.push_back(match(end, id));
    return HWLM_CONTINUE_MATCHING;
}

static
hwlmcb_rv_t decentCallbackT(size_t end, u32 id,
                            UNUSED struct hs_scratch *scratch) {
    matches.push_back(match(end, id));
    return HWLM_TERMINATE_MATCHING;
}

} // extern "C"

} // namespace

static
vector<u32> getValidFdrEngines() {
    const auto target = get_current_target();

    vector<u32> ret;

    vector<FDREngineDescription> fdr_descriptions;
    getFdrDescriptions(&fdr_descriptions);
    for (const FDREngineDescription &d : fdr_descriptions) {
        if (d.isValidOnTarget(target)) {
            ret.push_back(d.getID());
        }
    }

    vector<TeddyEngineDescription> teddy_descriptions;
    getTeddyDescriptions(&teddy_descriptions);
    for (const TeddyEngineDescription &d : teddy_descriptions) {
        if (d.isValidOnTarget(target)) {
            ret.push_back(d.getID());
        }
    }

    return ret;
}

static
bytecode_ptr<FDR> buildFDREngineHinted(std::vector<hwlmLiteral> &lits,
                                       bool make_small, u32 hint,
                                       const target_t &target,
                                       const Grey &grey) {
    auto proto = fdrBuildProtoHinted(HWLM_ENGINE_FDR, lits, make_small, hint,
                                     target, grey);
    if (!proto) {
        return nullptr;
    }
    return fdrBuildTable(*proto, grey);
}

static
bytecode_ptr<FDR> buildFDREngine(std::vector<hwlmLiteral> &lits,
                                 bool make_small, const target_t &target,
                                 const Grey &grey) {
    auto proto = fdrBuildProto(HWLM_ENGINE_FDR, lits, make_small, target, grey);
    if (!proto) {
        return nullptr;
    }
    return fdrBuildTable(*proto, grey);
}

class FDRp : public TestWithParam<u32> {
};

TEST_P(FDRp, Simple) {
    const u32 hint = GetParam();
    SCOPED_TRACE(hint);

    const char data[] = "mnopqrabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ12345678901234567890mnopqr";

    vector<hwlmLiteral> lits;
    lits.push_back(hwlmLiteral("mnopqr", 0, 0));

    auto fdr = buildFDREngineHinted(lits, false, hint, get_current_target(),
                                    Grey());
    CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;
    fdrExec(fdr.get(), (const u8 *)data, sizeof(data), 0, decentCallback,
            &scratch, HWLM_ALL_GROUPS);

    ASSERT_EQ(3U, matches.size());
    EXPECT_EQ(match(5, 0), matches[0]);
    EXPECT_EQ(match(23, 0), matches[1]);
    EXPECT_EQ(match(83, 0), matches[2]);
    matches.clear();
}

TEST_P(FDRp, SimpleSingle) {
    const u32 hint = GetParam();
    SCOPED_TRACE(hint);

    const char data[] = "mnopqrabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ12345678901234567890m0m";

    vector<hwlmLiteral> lits;
    lits.push_back(hwlmLiteral("m", 0, 0));

    auto fdr = buildFDREngineHinted(lits, false, hint, get_current_target(),
                                    Grey());
    CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;
    fdrExec(fdr.get(), (const u8 *)data, sizeof(data) - 1 /* skip nul */, 0,
            decentCallback, &scratch, HWLM_ALL_GROUPS);

    ASSERT_EQ(4U, matches.size());
    EXPECT_EQ(match(0, 0), matches[0]);
    EXPECT_EQ(match(18, 0), matches[1]);
    EXPECT_EQ(match(78, 0), matches[2]);
    EXPECT_EQ(match(80, 0), matches[3]);
    matches.clear();
}

TEST_P(FDRp, MultiLocation) {
    const u32 hint = GetParam();
    SCOPED_TRACE(hint);

    vector<hwlmLiteral> lits;
    lits.push_back(hwlmLiteral("abc", 0, 1));

    auto fdr = buildFDREngineHinted(lits, false, hint, get_current_target(),
                                    Grey());
    CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

    const u32 testSize = 128;

    vector<u8> data(testSize, 0);

    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;
    for (u32 i = 0; i < testSize - 3; i++) {
        memcpy(data.data() + i, "abc", 3);
        fdrExec(fdr.get(), data.data(), testSize, 0, decentCallback, &scratch,
                HWLM_ALL_GROUPS);
        ASSERT_EQ(1U, matches.size());
        EXPECT_EQ(match(i + 2, 1), matches[0]);
        memset(data.data() + i, 0, 3);
        matches.clear();
    }
}

TEST_P(FDRp, NoRepeat1) {
    const u32 hint = GetParam();
    SCOPED_TRACE(hint);

    const char data[] = "mnopqrabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ12345678901234567890m0m";

    vector<hwlmLiteral> lits
        = { hwlmLiteral("m", 0, 1, 0, HWLM_ALL_GROUPS, {}, {}) };

    auto fdr = buildFDREngineHinted(lits, false, hint, get_current_target(),
                                    Grey());
    CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;
    fdrExec(fdr.get(), (const u8 *)data, sizeof(data) - 1 /* skip nul */, 0,
            decentCallback, &scratch, HWLM_ALL_GROUPS);

    ASSERT_EQ(1U, matches.size());
    EXPECT_EQ(match(0, 0), matches[0]);
    matches.clear();
}

TEST_P(FDRp, NoRepeat2) {
    const u32 hint = GetParam();
    SCOPED_TRACE(hint);

    const char data[] = "mnopqrabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ12345678901234567890m0m";

    vector<hwlmLiteral> lits
        = { hwlmLiteral("m", 0, 1, 0, HWLM_ALL_GROUPS, {}, {}),
            hwlmLiteral("A", 0, 42) };

    auto fdr = buildFDREngineHinted(lits, false, hint, get_current_target(),
                                    Grey());
    CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;
    fdrExec(fdr.get(), (const u8 *)data, sizeof(data) - 1 /* skip nul */, 0,
            decentCallback, &scratch, HWLM_ALL_GROUPS);

    ASSERT_EQ(3U, matches.size());
    EXPECT_EQ(match(0, 0), matches[0]);
    EXPECT_EQ(match(78, 0), matches[2]);
    matches.clear();
}

TEST_P(FDRp, NoRepeat3) {
    const u32 hint = GetParam();
    SCOPED_TRACE(hint);

    const char data[] = "mnopqrabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ12345678901234567890m0m";

    vector<hwlmLiteral> lits
        = { hwlmLiteral("90m", 0, 1, 0, HWLM_ALL_GROUPS, {}, {}),
            hwlmLiteral("zA", 0, 1, 0, HWLM_ALL_GROUPS, {}, {}) };

    auto fdr = buildFDREngineHinted(lits, false, hint, get_current_target(),
                                    Grey());
    CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;
    fdrExec(fdr.get(), (const u8 *)data, sizeof(data) - 1 /* skip nul */, 0,
            decentCallback, &scratch, HWLM_ALL_GROUPS);

    ASSERT_EQ(1U, matches.size());
    EXPECT_EQ(match(32, 0), matches[0]);
    matches.clear();
}

/**
 * \brief Helper function wrapping the FDR streaming call that ensures it is
 * always safe to read 16 bytes before the end of the history buffer.
 */
static
hwlm_error_t safeExecStreaming(const FDR *fdr, const u8 *hbuf, size_t hlen,
                               const u8 *buf, size_t len, size_t start,
                               HWLMCallback cb, hwlm_group_t groups) {
    array<u8, 16> wrapped_history = {{'0', '1', '2', '3', '4', '5', '6', '7',
                                      '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'}};
    if (hlen < 16) {
        u8 *new_hbuf = wrapped_history.data() + 16 - hlen;
        memcpy(new_hbuf, hbuf, hlen);
        hbuf = new_hbuf;
    }
    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;
    return fdrExecStreaming(fdr, hbuf, hlen, buf, len, start, cb, &scratch,
                            groups);
}

TEST_P(FDRp, SmallStreaming) {
    const u32 hint = GetParam();
    SCOPED_TRACE(hint);

    vector<hwlmLiteral> lits = {hwlmLiteral("a", 1, 1),
                                hwlmLiteral("aardvark", 0, 10)};

    auto fdr = buildFDREngineHinted(lits, false, hint, get_current_target(),
                                    Grey());
    CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

    vector<match> expected;
    expected.push_back(match(0, 1));
    expected.push_back(match(1, 1));
    expected.push_back(match(2, 1));

    safeExecStreaming(fdr.get(), (const u8 *)"", 0, (const u8 *)"aaar", 4, 0,
                      decentCallback, HWLM_ALL_GROUPS);
    for (u32 i = 0; i < MIN(expected.size(), matches.size()); i++) {
        EXPECT_EQ(expected[i], matches[i]);
    }
    ASSERT_TRUE(expected.size() == matches.size());
    expected.clear();
    matches.clear();

    expected.push_back(match(6, 1));
    expected.push_back(match(8, 10));

    safeExecStreaming(fdr.get(), (const u8 *)"aaar", 4, (const u8 *)"dvark", 5,
                      0, decentCallback, HWLM_ALL_GROUPS);

    for (u32 i = 0; i < MIN(expected.size(), matches.size()); i++) {
        EXPECT_EQ(expected[i], matches[i] + 4);
    }
    ASSERT_EQ(expected.size(), matches.size());
    matches.clear();
}

TEST_P(FDRp, SmallStreaming2) {
    const u32 hint = GetParam();
    SCOPED_TRACE(hint);

    vector<hwlmLiteral> lits = {hwlmLiteral("a", 1, 1),
                                hwlmLiteral("kk", 1, 2),
                                hwlmLiteral("aardvark", 0, 10)};

    auto fdr = buildFDREngineHinted(lits, false, hint, get_current_target(),
                                    Grey());
    CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

    vector<match> expected;
    expected.push_back(match(6,1));
    expected.push_back(match(7,1));
    expected.push_back(match(11,1));
    expected.push_back(match(13,10));
    expected.push_back(match(14,2));
    expected.push_back(match(15,2));

    safeExecStreaming(fdr.get(), (const u8 *)"foobar", 6,
                      (const u8 *)"aardvarkkk", 10, 0, decentCallback,
                      HWLM_ALL_GROUPS);

    for (u32 i = 0; i < MIN(expected.size(), matches.size()); i++) {
        EXPECT_EQ(expected[i], matches[i] + 6);
    }
    ASSERT_EQ(expected.size(), matches.size());
    matches.clear();
}

TEST_P(FDRp, moveByteStream) {
    const u32 hint = GetParam();
    SCOPED_TRACE(hint);
    const char data[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ12345678901234567890";
    size_t data_len = strlen(data);

    vector<hwlmLiteral> lits;
    lits.push_back(hwlmLiteral("mnopqr", 0, 0));

    auto fdrTable0 = buildFDREngineHinted(lits, false, hint,
                                          get_current_target(), Grey());
    CHECK_WITH_TEDDY_OK_TO_FAIL(fdrTable0, hint);

    size_t size = fdrSize(fdrTable0.get());

    auto fdrTable = make_bytecode_ptr<FDR>(size, 64);
    EXPECT_NE(nullptr, fdrTable);

    memcpy(fdrTable.get(), fdrTable0.get(), size);

    //  bugger up original
    for (size_t i = 0 ; i < size; i++) {
        ((char *)fdrTable0.get())[i] = (i % 2) ? 0xCA : 0xFE;
    }

    // check matches
    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;

    hwlm_error_t fdrStatus = fdrExec(fdrTable.get(), (const u8 *)data,
                                     data_len, 0, decentCallback, &scratch,
                                     HWLM_ALL_GROUPS);
    ASSERT_EQ(0, fdrStatus);

    ASSERT_EQ(1U, matches.size());
    EXPECT_EQ(match(17, 0), matches[0]);
    matches.clear();
}

TEST_P(FDRp, Stream1) {
    const u32 hint = GetParam();
    SCOPED_TRACE(hint);
    const char data1[] = "fffffffffffffffff";
    const char data2[] = "ffffuuuuuuuuuuuuu";
    size_t data_len1 = strlen(data1);
    size_t data_len2 = strlen(data2);
    hwlm_error_t fdrStatus = 1;

    vector<hwlmLiteral> lits;
    lits.push_back(hwlmLiteral("f", 0, 0));
    lits.push_back(hwlmLiteral("literal", 0, 1));

    auto fdr = buildFDREngineHinted(lits, false, hint, get_current_target(),
                                    Grey());
    CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

    // check matches

    fdrStatus = safeExecStreaming(fdr.get(), (const u8 *)data1, data_len1,
                                  (const u8 *)data2, data_len2, 0,
                                  decentCallback, HWLM_ALL_GROUPS);
    ASSERT_EQ(0, fdrStatus);

    ASSERT_EQ(4U, matches.size());
    for (size_t i = 0; i < matches.size(); i++) {
        EXPECT_EQ(match(i, 0), matches[i]);
    }
    matches.clear();
}

INSTANTIATE_TEST_CASE_P(FDR, FDRp, ValuesIn(getValidFdrEngines()));

typedef struct {
    string pattern;
    unsigned char alien; // character not present in pattern
} pattern_alien_t;

// gtest helper
void PrintTo(const pattern_alien_t &t, ::std::ostream *os) {
    *os << "(" << t.pattern << ", " << t.alien << ")";
}

class FDRpp : public TestWithParam<tuple<u32, pattern_alien_t>> {};

// This test will check if matcher detects properly literals at the beginning
// and at the end of unaligned buffer. It will check as well that match does
// not happen if literal is partially (from 1 character up to full literal
// length) is out of searched buffer - "too early" and "too late" conditions
TEST_P(FDRpp, AlignAndTooEarly) {
    const size_t buf_alignment = 32;
    // Buffer should be big enough to hold two instances of matching literals
    // (up to 64 bytes each) and room for offset (up to 32 bytes)
    const size_t data_len = 5 * buf_alignment;

    const u32 hint = get<0>(GetParam());
    SCOPED_TRACE(hint);

    // pattern which is used to generate literals of variable size - from 1 to 8
    const string &pattern = get<1>(GetParam()).pattern;
    const size_t patLen = pattern.size();
    const unsigned char alien = get<1>(GetParam()).alien;

    // allocate aligned buffer
    auto dataBufAligned = shared_ptr<char>(
        (char *)aligned_malloc_internal(data_len, buf_alignment),
        aligned_free_internal);

    vector<hwlmLiteral> lits;
    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;
    for (size_t litLen = 1; litLen <= patLen; litLen++) {

        // building literal from pattern substring of variable length 1-patLen
        lits.push_back(hwlmLiteral(string(pattern, 0, litLen), 0, 0));
        auto fdr = buildFDREngineHinted(lits, false, hint, get_current_target(),
                                        Grey());
        CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

        // check with buffer offset from aligned start from 0 to 31
        for (size_t i = 0; i < buf_alignment; i++) {
            // fill the whole buffer with 'alien' character
            memset(dataBufAligned.get(), alien, data_len);
            // put the matching substring to the beginning of unaligned buffer
            memcpy(dataBufAligned.get() + i, pattern.data(), litLen);
            // put the matching substring to the end of unaligned buffer
            memcpy(dataBufAligned.get() + i + 4 * buf_alignment - litLen,
                        pattern.data(), litLen);

            for (size_t j = 0; j <= litLen; j++) {
                hwlm_error_t fdrStatus = fdrExec(fdr.get(),
                        (const u8 *)dataBufAligned.get() + i + j,
                        4 * buf_alignment - j * 2, 0, decentCallback,
                        &scratch, HWLM_ALL_GROUPS);
                ASSERT_EQ(0, fdrStatus);
                // j == 0 means that start and end matches are entirely within
                // searched buffer. Otherwise they are out of buffer boundaries
                // by j number of bytes - "too early" or "too late" conditions
                // j == litLen means that matches are completely put of searched buffer
                if (j == 0) {
                    // we should get two and only two matches - at the beginning and
                    // at the end of unaligned buffer
                    ASSERT_EQ(2U, matches.size());
                    ASSERT_EQ(match(litLen - 1, 0), matches[0]);
                    ASSERT_EQ(match(4 * buf_alignment - 1, 0), matches[1]);
                    matches.clear();
                } else {
                    // "Too early" / "too late" condition - should not match anything
                    ASSERT_EQ(0U, matches.size());
                }
            }
        }
        lits.clear();
    }
}

static const pattern_alien_t test_pattern[] = {
        {"abaabaaa", 'x'},
        {"zzzyyzyz", (unsigned char)'\x99'},
        {"abcdef l", '\0'}
};

INSTANTIATE_TEST_CASE_P(FDR, FDRpp, Combine(ValuesIn(getValidFdrEngines()),
                                            ValuesIn(test_pattern)));

// This test generates an exhaustive set of short input buffers of length from
// 1 to 6 (1092 buffers) and 2750 buffers of length from 7 to >64 constructed
// from arbitrary set of short buffers. All buffers contain 3 characters from
// the alphabet given as a parameter to the test.
// Then it generates an exhaustive set of literals of length from 1 to 8
// containing first two characters from the same alphabet (510 literals)
// Literals are grouped by 32 to run search on each and every buffer.
// All resulting matches are checked.

// Fibonacci sequence is used to generate arbitrary buffers
unsigned long long fib (int n) {
    unsigned long long fib0 = 1, fib1 = 1, fib2 = 1;
    for (int i = 0; i < n; i++) {
        fib2 = fib1 + fib0;
        fib0 = fib1;
        fib1 = fib2;
    }
    return fib2;
}

class FDRpa : public TestWithParam<tuple<u32, array<unsigned char, 3>>> {};

TEST_P(FDRpa, ShortWritings) {
    const u32 hint = get<0>(GetParam());
    SCOPED_TRACE(hint);
    vector<string> bufs;

    // create exhaustive buffer set for up to 6 literals:

    const array<unsigned char, 3> &alphabet = get<1>(GetParam());

    for (int len = 1; len <= 6; len++) {
        for (int j = 0; j < (int)pow((double)3, len); j++) {
            string s;
            for (int k = 0; k < len; k++) {
                s += alphabet[(j / (int)pow((double)3, k) % 3)];
            }
            bufs.push_back(s);
        }
    }
    size_t buflen = bufs.size();

    // create arbitrary buffers from exhaustive set of previously generated 'short'

    for (int len = 7; len < 64; len++) {
        for (int i = 0; i < 10; i++) {
            string s;
            for(int j = 0; (int)s.size() < len; j++) {
                s += bufs[fib(i * 5 + j + (len - 6) * 10) % buflen];
            }
            bufs.push_back(s);
        }
    }

    // generate exhaustive set of literals of length from 1 to 8
    vector<string> pats;
    for (int len = 1; len <= 8; len++) {
        for (int j = 0; j < (int)pow((double)2, len); j++) {
            string s;
            for (int k = 0; k < len; k++) {
                s += alphabet[(j >> k) & 1];
            }
            pats.push_back(s);
        }
    }

    // run the literal matching through all generated literals
    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;
    for (size_t patIdx = 0; patIdx < pats.size();) {
        // group them in the sets of 32
        vector<hwlmLiteral> testSigs;
        for(int i = 0; i < 32 && patIdx < pats.size(); i++, patIdx++) {
            testSigs.push_back(hwlmLiteral(pats[patIdx], false, patIdx));
        }

        auto fdr = buildFDREngineHinted(testSigs, false, hint,
                                        get_current_target(), Grey());

        CHECK_WITH_TEDDY_OK_TO_FAIL(fdr, hint);

        // run the literal matching for the prepared set of 32 literals
        // on each generated buffer
        for (size_t bufIdx = 0; bufIdx < bufs.size(); bufIdx++) {
            const string &buf = bufs[bufIdx];
            size_t bufLen = buf.size();

            hwlm_error_t fdrStatus = fdrExec(fdr.get(), (const u8 *)buf.data(),
                        bufLen, 0, decentCallback, &scratch, HWLM_ALL_GROUPS);
            ASSERT_EQ(0, fdrStatus);

            // build the set of expected matches using standard
            // stl::string::compare() function
            vector<match> expMatches;
            for (size_t pIdx = 0; pIdx < testSigs.size(); pIdx++) {

                const string &pat = testSigs[pIdx].s;
                size_t patLen = pat.size();

                for (int j = 0; j <= (int)bufLen - (int)patLen; j++) {
                    if (!buf.compare(j, patLen, pat)) {
                        expMatches.push_back(match(j + patLen - 1,
                                                testSigs[pIdx].id));
                    }
                }
            }
            // compare the set obtained matches against expected ones
            sort(expMatches.begin(), expMatches.end());
            sort(matches.begin(), matches.end());
            ASSERT_EQ(expMatches, matches);
            matches.clear();
        }
    }
}

static const array<unsigned char, 3> test_alphabet[] = {
    { { 'a', 'b', 'x' } },
    { { 'x', 'y', 'z' } },
    { { '\0', 'A', '\x20' } },
    { { 'a', '\x20', (unsigned char)'\x99' } }
};

INSTANTIATE_TEST_CASE_P(FDR, FDRpa, Combine(ValuesIn(getValidFdrEngines()),
                                            ValuesIn(test_alphabet)));

TEST(FDR, FDRTermS) {
    const char data1[] = "fffffffffffffffff";
    const char data2[] = "ffffuuuuuuuuuuuuu";
    size_t data_len1 = strlen(data1);
    size_t data_len2 = strlen(data2);
    hwlm_error_t fdrStatus = 0;

    vector<hwlmLiteral> lits;
    lits.push_back(hwlmLiteral("f", 0, 0));
    lits.push_back(hwlmLiteral("ff", 0, 1));

    auto fdr = buildFDREngine(lits, false, get_current_target(), Grey());
    ASSERT_TRUE(fdr != nullptr);

    // check matches

    fdrStatus = safeExecStreaming(fdr.get(), (const u8 *)data1, data_len1,
                                  (const u8 *)data2, data_len2, 0,
                                  decentCallbackT, HWLM_ALL_GROUPS);
    ASSERT_EQ(HWLM_TERMINATED, fdrStatus);

    ASSERT_EQ(1U, matches.size());
    matches.clear();
}

TEST(FDR, FDRTermB) {
    const char data1[] = "fffffffffffffffff";
    size_t data_len1 = strlen(data1);
    hwlm_error_t fdrStatus = 0;

    vector<hwlmLiteral> lits;
    lits.push_back(hwlmLiteral("f", 0, 0));
    lits.push_back(hwlmLiteral("ff", 0, 1));

    auto fdr = buildFDREngine(lits, false, get_current_target(), Grey());
    ASSERT_TRUE(fdr != nullptr);

    // check matches
    struct hs_scratch scratch;
    scratch.fdr_conf = NULL;

    fdrStatus = fdrExec(fdr.get(), (const u8 *)data1, data_len1,
                        0, decentCallbackT, &scratch, HWLM_ALL_GROUPS);
    ASSERT_EQ(HWLM_TERMINATED, fdrStatus);

    ASSERT_EQ(1U, matches.size());
    matches.clear();
}
#endif

max_stars_repo_name: MarvellEmbeddedProcessors/hyperscan

max_issues_repo_name: MarvellEmbeddedProcessors/hyperscan

max_forks_repo_name: MarvellEmbeddedProcessors/hyperscan


text:
//  Copyright (c) 2013 Jeroen Habraken
//
//  Distributed under the Boost Software License, Version 1.0. (See accompanying
//  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

#ifndef HPX_COMPONENTS_SECURITY_SERVER_SIGNATURE_HPP
#define HPX_COMPONENTS_SECURITY_SERVER_SIGNATURE_HPP

#include <hpx/hpx_fwd.hpp>
#include <hpx/runtime/serialization/serialize.hpp>
#include <hpx/runtime/serialization/array.hpp>
#include <hpx/traits/is_bitwise_serializable.hpp>

#include <boost/array.hpp>
#include <boost/io/ios_state.hpp>

#include <sodium.h>

namespace hpx { namespace components { namespace security
{
#if defined(_MSC_VER)
#  pragma pack(push, 1)
#endif

    class signature
    {
    public:
        signature()
        {
            std::fill(bytes_.begin(), bytes_.end(), 0);
        }

        friend std::ostream & operator<<(std::ostream & os,
                                         signature const & signature)
        {
            boost::io::ios_flags_saver ifs(os);

            os << "<signature \"";

            for (std::size_t i = 0; i < crypto_sign_BYTES; ++i)
            {
                os << std::hex
                   << std::nouppercase
                   << std::setfill('0')
                   << std::setw(2)
                   << static_cast<unsigned int>(signature.bytes_[i]);
            }

            return os << "\">";
        }

    private:
        friend class hpx::serialization::access;

        template <typename Archive>
        void serialize(Archive & ar, const unsigned int)
        {
            ar & bytes_;
        }

        boost::array<
            unsigned char, crypto_sign_BYTES
        > bytes_;
    };

#if defined(_MSC_VER)
#  pragma pack(pop)
#endif
}}}

namespace hpx { namespace traits
{
    template <>
    struct is_bitwise_serializable<
            hpx::components::security::signature>
       : mpl::true_
    {};
}}

#endif

ext: hpp

max_stars_repo_name: kempj/hpx

max_issues_repo_name: kempj/hpx

max_forks_repo_name: kempj/hpx


text:
#pragma once

#include <VFSPP/core.hpp>

#include <boost/unordered_map.hpp>

#include <boost/filesystem/path.hpp>

namespace vfspp
{
	namespace util
	{
		template<class InType, class OutType = InType>
		OutType normalizePath(const InType& inPath, bool lowerCase = false)
		{
			OutType outPath(inPath);

			boost::trim(outPath);

			boost::trim_if(outPath, boost::is_any_of(DirectorySeparatorStr));

			if (lowerCase)
			{
				boost::to_lower(outPath);
			}

			return outPath;
		}

		inline string_type normalizePath(const char* inPath, bool lowerCase = false)
		{
			return normalizePath<const char*, string_type>(inPath, lowerCase);
		}

		int modeToOperation(int mode);

		template<typename DataType>
		class VFSPP_EXPORT ArchiveFileSystem : public IFileSystem
		{
		public:
			ArchiveFileSystem(const boost::filesystem::path& filePathIn) : filePath(filePathIn) {}

			virtual ~ArchiveFileSystem() {}

			virtual IFileSystemEntry* getRootEntry() = 0;

			virtual int supportedOperations() const = 0;

			virtual string_type getName() const { return filePath.string(); }

		protected:
			typedef DataType data_type;

			boost::filesystem::path filePath;

			std::vector<data_type> fileData;
			boost::unordered_map<string_type, size_t> fileIndexes;

			void addFileData(const string_type& path, const data_type& data)
			{
				fileData.push_back(data);
				fileIndexes.insert(std::make_pair(path, fileData.size() - 1));
			}

			data_type getFileData(const string_type& path) const
			{
				if (path.length() == 0)
				{
					// Special case: The root entry is always a directory
					data_type data;
					data.type = DIRECTORY;

					return data;
				}

				boost::unordered_map<string_type, size_t>::const_iterator iter = fileIndexes.find(path);

				if (iter == fileIndexes.end())
				{
					return data_type();
				}
				else
				{
					return fileData[iter->second];
				}
			}
		};
	}
}

max_stars_repo_name: asarium/vfspp

max_issues_repo_name: asarium/vfspp

max_forks_repo_name: asarium/vfspp


text:
// Copyright 2015-2018 Hans Dembinski
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt
// or copy at http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_HISTOGRAM_DETAIL_META_HPP
#define BOOST_HISTOGRAM_DETAIL_META_HPP

/* Most of the histogram code is generic and works for any number of axes. Buffers with a
 * fixed maximum capacity are used in some places, which have a size equal to the rank of
 * a histogram. The buffers are statically allocated to improve performance, which means
 * that they need a preset maximum capacity. 32 seems like a safe upper limit for the rank
 * (you can nevertheless increase it here if necessary): the simplest non-trivial axis has
 * 2 bins; even if counters are used which need only a byte of storage per bin, this still
 * corresponds to 4 GB of storage.
 */
#ifndef BOOST_HISTOGRAM_DETAIL_AXES_LIMIT
#define BOOST_HISTOGRAM_DETAIL_AXES_LIMIT 32
#endif

#include <boost/config/workaround.hpp>
#if BOOST_WORKAROUND(BOOST_GCC, >= 60000)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wnoexcept-type"
#endif
#include <boost/callable_traits/args.hpp>
#include <boost/callable_traits/return_type.hpp>
#if BOOST_WORKAROUND(BOOST_GCC, >= 60000)
#pragma GCC diagnostic pop
#endif
#include <array>
#include <boost/histogram/fwd.hpp>
#include <boost/mp11/algorithm.hpp>
#include <boost/mp11/function.hpp>
#include <boost/mp11/integer_sequence.hpp>
#include <boost/mp11/list.hpp>
#include <boost/mp11/utility.hpp>
#include <functional>
#include <iterator>
#include <limits>
#include <tuple>
#include <type_traits>

namespace boost {
namespace histogram {
namespace detail {

template <class T>
using remove_cvref_t = std::remove_cv_t<std::remove_reference_t<T>>;

template <class T, class U>
using convert_integer = mp11::mp_if<std::is_integral<remove_cvref_t<T>>, U, T>;

// to be replaced by official version from mp11
template <class E, template <class...> class F, class... Ts>
using mp_eval_or = mp11::mp_eval_if_c<!(mp11::mp_valid<F, Ts...>::value), E, F, Ts...>;

template <class T1, class T2>
using copy_qualifiers = mp11::mp_if<
    std::is_rvalue_reference<T1>, T2&&,
    mp11::mp_if<std::is_lvalue_reference<T1>,
                mp11::mp_if<std::is_const<typename std::remove_reference<T1>::type>,
                            const T2&, T2&>,
                mp11::mp_if<std::is_const<T1>, const T2, T2>>>;

template <class L>
using mp_last = mp11::mp_at_c<L, (mp11::mp_size<L>::value - 1)>;

template <class T, class Args = boost::callable_traits::args_t<T>>
using args_type =
    mp11::mp_if<std::is_member_function_pointer<T>, mp11::mp_pop_front<Args>, Args>;

template <class T, std::size_t N = 0>
using arg_type = typename mp11::mp_at_c<args_type<T>, N>;

template <class T>
using return_type = typename boost::callable_traits::return_type<T>::type;

template <class F, class V,
          class T = copy_qualifiers<V, mp11::mp_first<remove_cvref_t<V>>>>
using visitor_return_type = decltype(std::declval<F>()(std::declval<T>()));

template <bool B, typename T, typename F, typename... Ts>
constexpr decltype(auto) static_if_c(T&& t, F&& f, Ts&&... ts) {
  return std::get<(B ? 0 : 1)>(std::forward_as_tuple(
      std::forward<T>(t), std::forward<F>(f)))(std::forward<Ts>(ts)...);
}

template <typename B, typename... Ts>
constexpr decltype(auto) static_if(Ts&&... ts) {
  return static_if_c<B::value>(std::forward<Ts>(ts)...);
}

template <typename T>
constexpr T lowest() {
  return std::numeric_limits<T>::lowest();
}

template <>
constexpr double lowest() {
  return -std::numeric_limits<double>::infinity();
}

template <>
constexpr float lowest() {
  return -std::numeric_limits<float>::infinity();
}

template <typename T>
constexpr T highest() {
  return std::numeric_limits<T>::max();
}

template <>
constexpr double highest() {
  return std::numeric_limits<double>::infinity();
}

template <>
constexpr float highest() {
  return std::numeric_limits<float>::infinity();
}

template <std::size_t I, class T, std::size_t... N>
decltype(auto) tuple_slice_impl(T&& t, mp11::index_sequence<N...>) {
  return std::forward_as_tuple(std::get<(N + I)>(std::forward<T>(t))...);
}

template <std::size_t I, std::size_t N, class T>
decltype(auto) tuple_slice(T&& t) {
  static_assert(I + N <= mp11::mp_size<remove_cvref_t<T>>::value,
                "I and N must describe a slice");
  return tuple_slice_impl<I>(std::forward<T>(t), mp11::make_index_sequence<N>{});
}

#define BOOST_HISTOGRAM_DETECT(name, cond)   \
  template <class T, class = decltype(cond)> \
  struct name##_impl {};                     \
  template <class T>                         \
  using name = typename mp11::mp_valid<name##_impl, T>

#define BOOST_HISTOGRAM_DETECT_BINARY(name, cond)     \
  template <class T, class U, class = decltype(cond)> \
  struct name##_impl {};                              \
  template <class T, class U = T>                     \
  using name = typename mp11::mp_valid<name##_impl, T, U>

BOOST_HISTOGRAM_DETECT(has_method_metadata, (std::declval<T&>().metadata()));

// resize has two overloads, trying to get pmf in this case always fails
BOOST_HISTOGRAM_DETECT(has_method_resize, (std::declval<T&>().resize(0)));

BOOST_HISTOGRAM_DETECT(has_method_size, &T::size);

BOOST_HISTOGRAM_DETECT(has_method_clear, &T::clear);

BOOST_HISTOGRAM_DETECT(has_method_lower, &T::lower);

BOOST_HISTOGRAM_DETECT(has_method_value, &T::value);

BOOST_HISTOGRAM_DETECT(has_method_update, (&T::update));

BOOST_HISTOGRAM_DETECT(has_method_reset, (std::declval<T>().reset(0)));

template <typename T>
using get_value_method_return_type_impl = decltype(std::declval<T&>().value(0));

template <typename T, typename R>
using has_method_value_with_convertible_return_type =
    typename std::is_convertible<mp_eval_or<void, get_value_method_return_type_impl, T>,
                                 R>::type;

BOOST_HISTOGRAM_DETECT(has_method_options, (&T::options));

BOOST_HISTOGRAM_DETECT(has_allocator, &T::get_allocator);

BOOST_HISTOGRAM_DETECT(is_indexable, (std::declval<T&>()[0]));

BOOST_HISTOGRAM_DETECT(is_transform, (&T::forward, &T::inverse));

BOOST_HISTOGRAM_DETECT(is_indexable_container,
                       (std::declval<T>()[0], &T::size, std::begin(std::declval<T>()),
                        std::end(std::declval<T>())));

BOOST_HISTOGRAM_DETECT(is_vector_like,
                       (std::declval<T>()[0], &T::size, std::declval<T>().resize(0),
                        std::begin(std::declval<T>()), std::end(std::declval<T>())));

BOOST_HISTOGRAM_DETECT(is_array_like,
                       (std::declval<T>()[0], &T::size, std::tuple_size<T>::value,
                        std::begin(std::declval<T>()), std::end(std::declval<T>())));

BOOST_HISTOGRAM_DETECT(is_map_like,
                       (std::declval<typename T::key_type>(),
                        std::declval<typename T::mapped_type>(),
                        std::begin(std::declval<T>()), std::end(std::declval<T>())));

// ok: is_axis is false for axis::variant, operator() is templated
BOOST_HISTOGRAM_DETECT(is_axis, (&T::size, &T::index));

BOOST_HISTOGRAM_DETECT(is_iterable,
                       (std::begin(std::declval<T&>()), std::end(std::declval<T&>())));

BOOST_HISTOGRAM_DETECT(is_iterator,
                       (typename std::iterator_traits<T>::iterator_category()));

BOOST_HISTOGRAM_DETECT(is_streamable,
                       (std::declval<std::ostream&>() << std::declval<T&>()));

BOOST_HISTOGRAM_DETECT(is_incrementable, (++std::declval<T&>()));

BOOST_HISTOGRAM_DETECT(has_operator_preincrement, (++std::declval<T&>()));

BOOST_HISTOGRAM_DETECT_BINARY(has_operator_equal,
                              (std::declval<const T&>() == std::declval<const U&>()));

BOOST_HISTOGRAM_DETECT_BINARY(has_operator_radd,
                              (std::declval<T&>() += std::declval<U&>()));

BOOST_HISTOGRAM_DETECT_BINARY(has_operator_rsub,
                              (std::declval<T&>() -= std::declval<U&>()));

BOOST_HISTOGRAM_DETECT_BINARY(has_operator_rmul,
                              (std::declval<T&>() *= std::declval<U&>()));

BOOST_HISTOGRAM_DETECT_BINARY(has_operator_rdiv,
                              (std::declval<T&>() /= std::declval<U&>()));

template <typename T>
using is_storage =
    mp11::mp_bool<(is_indexable_container<T>::value && has_method_reset<T>::value)>;

template <typename T>
struct is_tuple_impl : std::false_type {};

template <typename... Ts>
struct is_tuple_impl<std::tuple<Ts...>> : std::true_type {};

template <typename T>
using is_tuple = typename is_tuple_impl<T>::type;

template <typename T>
struct is_axis_variant_impl : std::false_type {};

template <typename... Ts>
struct is_axis_variant_impl<axis::variant<Ts...>> : std::true_type {};

template <typename T>
using is_axis_variant = typename is_axis_variant_impl<T>::type;

template <typename T>
using is_any_axis = mp11::mp_or<is_axis<T>, is_axis_variant<T>>;

template <typename T>
using is_sequence_of_axis = mp11::mp_and<is_iterable<T>, is_axis<mp11::mp_first<T>>>;

template <typename T>
using is_sequence_of_axis_variant =
    mp11::mp_and<is_iterable<T>, is_axis_variant<mp11::mp_first<T>>>;

template <typename T>
using is_sequence_of_any_axis =
    mp11::mp_and<is_iterable<T>, is_any_axis<mp11::mp_first<T>>>;

template <typename T>
struct is_weight_impl : std::false_type {};

template <typename T>
struct is_weight_impl<weight_type<T>> : std::true_type {};

template <typename T>
using is_weight = is_weight_impl<remove_cvref_t<T>>;

template <typename T>
struct is_sample_impl : std::false_type {};

template <typename T>
struct is_sample_impl<sample_type<T>> : std::true_type {};

template <typename T>
using is_sample = is_sample_impl<remove_cvref_t<T>>;

// poor-mans concept checks
template <class T, class = std::enable_if_t<is_iterator<remove_cvref_t<T>>::value>>
struct requires_iterator {};

template <class T, class = std::enable_if_t<is_iterable<remove_cvref_t<T>>::value>>
struct requires_iterable {};

template <class T, class = std::enable_if_t<is_axis<remove_cvref_t<T>>::value>>
struct requires_axis {};

template <class T, class = std::enable_if_t<is_any_axis<remove_cvref_t<T>>::value>>
struct requires_any_axis {};

template <class T,
          class = std::enable_if_t<is_sequence_of_axis<remove_cvref_t<T>>::value>>
struct requires_sequence_of_axis {};

template <class T,
          class = std::enable_if_t<is_sequence_of_axis_variant<remove_cvref_t<T>>::value>>
struct requires_sequence_of_axis_variant {};

template <class T,
          class = std::enable_if_t<is_sequence_of_any_axis<remove_cvref_t<T>>::value>>
struct requires_sequence_of_any_axis {};

template <class T,
          class = std::enable_if_t<is_any_axis<mp11::mp_first<remove_cvref_t<T>>>::value>>
struct requires_axes {};

template <class T, class U, class = std::enable_if_t<std::is_convertible<T, U>::value>>
struct requires_convertible {};

template <class T>
auto make_default(const T& t) {
  return static_if<has_allocator<T>>([](const auto& t) { return T(t.get_allocator()); },
                                     [](const auto&) { return T(); }, t);
}

template <class T>
using tuple_size_t = typename std::tuple_size<T>::type;

template <class T>
constexpr std::size_t get_size_impl(std::true_type, const T&) noexcept {
  return std::tuple_size<T>::value;
}

template <class T>
std::size_t get_size_impl(std::false_type, const T& t) noexcept {
  using std::begin;
  using std::end;
  return static_cast<std::size_t>(std::distance(begin(t), end(t)));
}

template <class T>
std::size_t get_size(const T& t) noexcept {
  return get_size_impl(mp11::mp_valid<tuple_size_t, T>(), t);
}

template <class T>
using buffer_size =
    mp_eval_or<std::integral_constant<std::size_t, BOOST_HISTOGRAM_DETAIL_AXES_LIMIT>,
               tuple_size_t, T>;

template <class T, std::size_t N>
class sub_array : public std::array<T, N> {
public:
  explicit sub_array(std::size_t s) : size_(s) {}
  sub_array(std::size_t s, T value) : size_(s) { std::array<T, N>::fill(value); }

  // need to override both versions of std::array
  auto end() noexcept { return std::array<T, N>::begin() + size_; }
  auto end() const noexcept { return std::array<T, N>::begin() + size_; }

  auto size() const noexcept { return size_; }

private:
  std::size_t size_ = N;
};

template <class U, class T>
using stack_buffer = sub_array<U, buffer_size<T>::value>;

template <class U, class T, class... Ts>
auto make_stack_buffer(const T& t, Ts&&... ts) {
  return stack_buffer<U, T>(get_size(t), std::forward<Ts>(ts)...);
}

template <class T>
constexpr bool relaxed_equal(const T& a, const T& b) noexcept {
  return static_if<has_operator_equal<T>>(
      [](const auto& a, const auto& b) { return a == b; },
      [](const auto&, const auto&) { return true; }, a, b);
}

template <class T>
using get_scale_type_helper = typename T::value_type;

template <class T>
using get_scale_type = mp_eval_or<T, detail::get_scale_type_helper, T>;

struct one_unit {};

template <class T>
T operator*(T&& t, const one_unit&) {
  return std::forward<T>(t);
}

template <class T>
T operator/(T&& t, const one_unit&) {
  return std::forward<T>(t);
}

template <class T>
using get_unit_type_helper = typename T::unit_type;

template <class T>
using get_unit_type = mp_eval_or<one_unit, detail::get_unit_type_helper, T>;

template <class T, class R = get_scale_type<T>>
R get_scale(const T& t) {
  return t / get_unit_type<T>();
}

template <class T, class Default>
using replace_default = mp11::mp_if<std::is_same<T, use_default>, Default, T>;

template <class T, class U>
using is_convertible_helper =
    mp11::mp_apply<mp11::mp_all, mp11::mp_transform<std::is_convertible, T, U>>;

template <class T, class U>
using is_convertible = mp_eval_or<std::false_type, is_convertible_helper, T, U>;

template <class T>
auto make_unsigned_impl(std::true_type, const T t) noexcept {
  return static_cast<typename std::make_unsigned<T>::type>(t);
}

template <class T>
auto make_unsigned_impl(std::false_type, const T t) noexcept {
  return t;
}

template <class T>
auto make_unsigned(const T t) noexcept {
  return make_unsigned_impl(std::is_integral<T>{}, t);
}

} // namespace detail
} // namespace histogram
} // namespace boost

#endif

max_stars_repo_name: Netis/packet-agent

max_issues_repo_name: Netis/packet-agent

max_forks_repo_name: Netis/packet-agent


text:
#pragma once

#include <cassert>
#include <iostream>
#include <algorithm>
#include <numeric>

#include <boost/archive/binary_iarchive.hpp>
#include <boost/archive/binary_oarchive.hpp>
#include <boost/serialization/vector.hpp>

#include <common/error.hpp>

#include <tensor/index.hpp>
#include <tensor/tensor.hpp>

namespace Construction {
	namespace Tensor {

		class IsNoPermutationException : public Exception {
		public:
			IsNoPermutationException(const std::string& error) : Exception(error) { }
			IsNoPermutationException() : Exception("The given combination is no permutation") {}
		};

		class BinaryPermutation {
		public:
			BinaryPermutation() = default;

			BinaryPermutation(unsigned a, unsigned b) : a(a), b(b) { }
			BinaryPermutation(const BinaryPermutation& other)
				: a(other.a), b(other.b) { }
		public:
			bool operator==(const BinaryPermutation& other) const {
				return a == other.a && b == other.b;
			}

			bool operator!=(const BinaryPermutation& other) const {
				return a != other.a || b != other.b;
			}
		public:
			Indices operator()(const Indices& indices) const {
				assert(a > 0 && b > 0 && indices.Size() >= a && indices.Size() >= b);

				Indices result;

				for (unsigned i=0; i < indices.Size(); ++i) {
					if (i == a-1) result.Insert(indices[b-1]);
					else if (i == b-1) result.Insert(indices[a-1]);
					else result.Insert(indices[i]);
				}

				return result;
			}

			std::vector<int> operator()(std::vector<int> list) const {
				assert(a > 0 && b > 0 && list.size() >= a && list.size() >= b);

				std::vector<int> result;

				for (unsigned i=0; i < list.size(); ++i) {
					if (i == a-1) result.push_back(list[b-1]);
					else if (i == b-1) result.push_back(list[a-1]);
					else result.push_back(list[i]);
				}

				return result;
			}

			template<typename... Args>
			std::vector<int> operator()(Args... args) const {
				return (*this)({ args... });
			}

			/*Tensor operator()(const Tensor& tensor) const {
				return Tensor
			}*/
		public:
			friend std::ostream& operator<<(std::ostream& os, const BinaryPermutation& permutation) {
				os << "(" << permutation.a << " <-> " << permutation.b << ")";
				return os;
			}
		private:
			friend class boost::serialization::access;

			template<class Archive>
			void serialize(Archive& ar, const unsigned int version) {
				ar & a;
				ar & b;
			}
		private:
			unsigned a;
			unsigned b;
		};

		/**
			\class Permutation

			Allows arbitrary permutation of an index combination
		 */
		class Permutation {
		public:
			Permutation() = default;

			Permutation(unsigned a, unsigned b) {
				this->permute.emplace_back(BinaryPermutation(a,b));
			}

			Permutation(const BinaryPermutation& permute) {
				this->permute.push_back(permute);
			}

			Permutation(std::vector<BinaryPermutation> permute)
				: permute(permute) { }

			// Copy constructor
			Permutation(const Permutation& other)
				: permute(other.permute) { }
		public:
			/*Permutation& operator=(std::vector<BinaryPermutation> permute) {
				this->permute = permute;
				return *this;
			}*/

			Permutation& operator=(const Permutation& other) {
				permute = other.permute;
				return *this;
			}

			Permutation& operator=(Permutation&& other) {
				permute = std::move(other.permute);
				return *this;
			}
		public:
			void Insert(const BinaryPermutation& p) {
				permute.push_back(p);
			}

			void Insert(unsigned a, unsigned b) {
				permute.emplace_back(BinaryPermutation(a,b));
			}
 		public:
			Indices operator()(const Indices& indices) const {
				Indices result = indices;
				for (auto& p : permute) {
					result = p(result);
				}
				return result;
			}

			std::vector<int> operator()(const std::vector<int>& indices) const {
				std::vector<int> result = indices;
				for (auto& p : permute) {
					result = p(result);
				}
				return result;
			}

			template<typename... Args>
			std::vector<unsigned> operator()(Args... args) const {
				return (*this)({args...});
			}
		public:
			bool IsEven() const {
				return permute.size() % 2 == 0;
			}

			bool IsOdd() const {
				return permute.size() % 2 != 0;
			}

			int Sign() const {
				return IsOdd() ? -1 : 1;
			}
		public:
			/**
				\brief A cyclic permutation of the indices

				{abcd} => {bcda}
			 */
			static Indices Cyclic(const Indices& indices) {
				Permutation p;
				for (int i=1; i<indices.Size(); i++) {
					p.Insert(i, i+1);
				}
				return p(indices);
			}

			static std::vector<int> Cyclic(const std::vector<int>& indices) {
				Permutation p;
				for (int i=1; i<indices.size(); i++) {
					p.Insert(i, i+1);
				}
				return p(indices);
			}

			template<typename... Args>
			static std::vector<int> Cyclic(Args... args) {
				return Cyclic({ args... });
			}

			/**
				Returns a permutation to get from an index combination to another

			 */
			static Permutation From(const Indices& indices, const Indices& to) {
				if (!indices.IsPermutationOf(to)) {
					throw IsNoPermutationException();
				}

				// Clone the vector
				auto vec = indices;

				int pos = 0;
				Permutation result;

				for (int i=0; i<indices.Size(); ++i) {
					auto current = vec[pos];
					auto id = std::find(to.begin(), to.end(), current) - to.begin();

					if (id == pos) {
						pos++;
						continue;
					}

					result.Insert(pos + 1, id + 1);

					// Do the switch
					std::iter_swap(vec.begin() + pos, vec.begin() + id);
				}

				return result;
			}

			static Permutation From(const std::vector<int>& indices, const std::vector<int>& to) {
				if (!Indices::IsPermutationOf(indices, to)) {
					throw IsNoPermutationException();
				}

				// Clone the vector
				auto vec = indices;

				int pos = 0;
				Permutation result;

				for (int i=0; i<indices.size(); ++i) {
					auto current = vec[pos];
					auto id = std::find(to.begin(), to.end(), current) - to.begin();

					if (id == pos) {
						pos++;
						continue;
					}

					result.Insert(pos + 1, id + 1);

					// Do the switch
					std::iter_swap(vec.begin() + pos, vec.begin() + id);
				}

				return result;
			}

			static Permutation From(const std::vector<unsigned>& indices, const std::vector<unsigned>& to) {
				if (!Indices::IsPermutationOf(indices, to)) {
					throw IsNoPermutationException();
				}

				// Clone the vector
				auto vec = indices;

				int pos = 0;
				Permutation result;

				for (int i=0; i<indices.size(); ++i) {
					auto current = vec[pos];
					auto id = std::find(to.begin(), to.end(), current) - to.begin();

					if (id == pos) {
						pos++;
						continue;
					}

					result.Insert(pos + 1, id + 1);

					// Do the switch
					std::iter_swap(vec.begin() + pos, vec.begin() + id);
				}

				return result;
			}

            static Permutation From(Indices indices, std::map<Index, Index> transformation) {
                Permutation result;

                for (unsigned i=0; i<indices.Size(); ++i) {
                    auto it = transformation.find(indices[i]);
                    if (it == transformation.end()) throw IsNoPermutationException();

                    unsigned pos=0;
                    bool found=false;
                    for (unsigned j=0; j<indices.Size(); ++j) {
                        if (it->second == indices[j]) { pos = j; found=true; break; }
                    }

                    if (!found) throw IsNoPermutationException();

                    result.Insert({ i+1, pos+1 });
                }

                return result;
            }

            inline static Indices Shuffle(Indices indices, std::map<Index, Index> transformation) {
                return From(indices, transformation)(indices);
            }
		public:
			friend std::ostream& operator<<(std::ostream& os, const Permutation& permutation) {
				os << "[";
				for (int i=0; i<permutation.permute.size(); i++) {
					os << permutation.permute[i];
					if (i !=permutation.permute.size()-1) os << ", ";
				}
				os << "]";
				return os;
			}
		private:
			friend class boost::serialization::access;

			template<class Archive>
			void serialize(Archive& ar, const unsigned int version) {
				ar & permute;
			}
		private:
			std::vector<BinaryPermutation> permute;
		};

	}
}

max_stars_repo_name: constructivegravity/construct

max_issues_repo_name: constructivegravity/construct

max_forks_repo_name: constructivegravity/construct


text:
/*
	This file is part of solidity.

	solidity is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	solidity is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
*/
/**
 * @date 2017
 * Unit tests for the Yul function inliner.
 */

#include <test/libyul/Common.h>

#include <libyul/optimiser/ExpressionInliner.h>
#include <libyul/optimiser/InlinableExpressionFunctionFinder.h>
#include <libyul/optimiser/FullInliner.h>
#include <libyul/optimiser/FunctionHoister.h>
#include <libyul/optimiser/FunctionGrouper.h>
#include <libyul/AsmPrinter.h>

#include <boost/test/unit_test.hpp>

#include <boost/range/adaptors.hpp>
#include <boost/algorithm/string/join.hpp>

using namespace std;
using namespace solidity;
using namespace solidity::util;
using namespace solidity::yul;
using namespace solidity::yul::test;

namespace
{
string inlinableFunctions(string const& _source)
{
	auto ast = disambiguate(_source);

	InlinableExpressionFunctionFinder funFinder;
	funFinder(ast);

	vector<string> functionNames;
	for (auto const& f: funFinder.inlinableFunctions())
		functionNames.emplace_back(f.first.str());
	return boost::algorithm::join(functionNames, ",");
}

}

BOOST_AUTO_TEST_SUITE(YulInlinableFunctionFilter)

BOOST_AUTO_TEST_CASE(smoke_test)
{
	BOOST_CHECK_EQUAL(inlinableFunctions("{ }"), "");
}

BOOST_AUTO_TEST_CASE(simple)
{
	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := 2:u256 } }"), "f");
	BOOST_CHECK_EQUAL(inlinableFunctions("{"
		"function g(a:u256) -> b:u256 { b := a }"
		"function f() -> x:u256 { x := g(2:u256) }"
	"}"), "g,f");
}

BOOST_AUTO_TEST_CASE(simple_inside_structures)
{
	BOOST_CHECK_EQUAL(inlinableFunctions("{"
		"switch 2:u256 "
		"case 2:u256 {"
			"function g(a:u256) -> b:u256 { b := a }"
			"function f() -> x:u256 { x := g(2:u256) }"
		"}"
	"}"), "g,f");
	BOOST_CHECK_EQUAL(inlinableFunctions("{"
		"function g(a:u256) -> b:u256 { b := a }"
		"for {"
		"} true {"
			"function f() -> x:u256 { x := g(2:u256) }"
		"}"
		"{"
			"function h() -> y:u256 { y := 2:u256 }"
		"}"
	"}"), "h,g,f");
}

BOOST_AUTO_TEST_CASE(negative)
{
	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { } }"), "");
	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := 2:u256 {} } }"), "");
	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := f() } }"), "");
	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256 { x := x } }"), "");
	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f() -> x:u256, y:u256 { x := 2:u256 } }"), "");
  BOOST_CHECK_EQUAL(inlinableFunctions(
    "{ function g() -> x:u256, y:u256 {} function f(y:u256) -> x:u256 { x,y := g() } }"), "");
	BOOST_CHECK_EQUAL(inlinableFunctions("{ function f(y:u256) -> x:u256 { y := 2:u256 } }"), "");
}

BOOST_AUTO_TEST_SUITE_END()

ext: cpp

max_stars_repo_name: MrChico/solidity

max_issues_repo_name: MrChico/solidity

max_forks_repo_name: MrChico/solidity


text:
#include <string>
#include <boost/format.hpp>

using namespace std;

namespace disasm {
	namespace vector {
		string decode_vector_register(uint16_t _reg) {
			uint16_t cleaned = _reg & 0x03ff; // only 10 bits, be certain
			string rv;
			uint8_t x, y;
			uint8_t isV = (cleaned & 0x0040);
			switch (isV) {
			case 0: // H[XY](y, ??)
				rv += "H";
				x = 0;
				y = (cleaned & 0x003f);
				break;
			case 1: //  V[XY](y, ??+x)
				rv += "V";
				x = (cleaned & 0x000f);
				y = ((cleaned & 0x0030) << 4);
				break;
			}

			uint8_t xy = (cleaned & 0x03c0) >> 6;

			if (xy == 12 || xy == 13) rv += "Y";
			else if (xy >= 8 && xy <= 11) rv += "X";
			else if (xy == 14) return string( "-" );
			rv += "(";
			rv += std::to_string(y);
			rv += ", ";

			uint8_t szm = (cleaned & 0x0380) >> 7;
			switch (szm) {
			case 0:
			case 1:
			case 2:
			case 3:
				rv += std::to_string(szm * 16);
				break;
			case 4:
				rv += "0";
				break;
			case 5:
				rv += "32";
				break;
			case 6:
				rv += "0";
				break;
			case 7:
			default:
				// Hermans docs break down here and are incomplete
				rv += "???";
				break;
			}

			if (isV) rv += " + " + std::to_string(x);
			rv += ")";

			return rv;
		}
	}
}

max_stars_repo_name: dshadowwolf/vciv-disassembler

max_issues_repo_name: dshadowwolf/vciv-disassembler

max_forks_repo_name: dshadowwolf/vciv-disassembler


text:
// Copyright 2014 Jonathan Graehl-http://graehl.org/
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
/** \file

  heap of indices (or pointers) where distance (priority, lowest = at top by
  default), location in heap, etc. are stored in external property maps (usually
  separate arrays).

  you can update(), or push_or_update() the priority unlike vanilla binary-heap w/
  std::pop_heap etc.

  by default, d=4-ary min-heap (faster than 2-ary depending on key size, due to cache locality)

  TODO: it might be worth trying priority+index together in heap data structure
  for even more locality (these are almost always used together when maintaining
  heap invariant by moving nodes up or down). location should still be external
  since it's less frequently updated

  'min-heap' means first distance is at top() - (smallest w/ the default, std::less)

  TODO: C++11, this heap move assign things you add to it (TODO: investigate
  template / std::forward to support both move and non-?)
 */

#ifndef GRAEHL_SHARED__D_ARY_HEAP_HPP
#define GRAEHL_SHARED__D_ARY_HEAP_HPP
#pragma once

#include <graehl/shared/cpp11.hpp>
#ifndef GRAEHL_DEBUG_D_ARY_HEAP
#define GRAEHL_DEBUG_D_ARY_HEAP 0
#endif
#if GRAEHL_DEBUG_D_ARY_HEAP
#include <graehl/shared/ifdbg.hpp>
#include <graehl/shared/show.hpp>
#define DDARY(x) x
DECLARE_DBG_LEVEL(DDARY)
#else
#ifndef EIFDBG
#define EIFDBG(ch, l, e)
#endif
#define DDARY(x)
#endif

#include <boost/property_map/property_map.hpp>
#include <boost/smart_ptr/shared_array.hpp>
#include <cstddef>
#include <functional>
#include <memory>
#include <string>

#ifdef _MSC_VER
#undef min
#endif

#define GRAEHL_D_ARY_APPEND_ALWAYS_PUSH 1
// heapify (0) is untested.  0 means switch between push and heapify depending
// on size (cache effects, existing items vs. # appended ones)

#define GRAEHL_D_ARY_TRACK_OUT_OF_HEAP 0
// set to 1 to slightly speed up contains(), if you are willing to preinit loc
// map to GRAEHL_D_ARY_HEAP_NULL_INDEX-but should work fine with 0 because we avoid
// false positives by checking key at that location.

#define GRAEHL_D_ARY_VERIFY_HEAP 0
#if !defined(NDEBUG) && GRAEHL_D_ARY_VERIFY_HEAP
#undef GRAEHL_D_ARY_VERIFY_HEAP
#define GRAEHL_D_ARY_VERIFY_HEAP 0
// VERY slow if enabled
#endif

#undef GRAEHL_D_ARY_HEAP_NULL_INDEX
#define GRAEHL_D_ARY_HEAP_NULL_INDEX (-1)
// you may init location map to this for GRAEHL_D_ARY_TRACK_OUT_OF_HEAP (optional), or for push_or_update

#ifndef GRAEHL_D_ARY_HEAP_CACHE_ALIGN_ROOT
#define GRAEHL_D_ARY_HEAP_CACHE_ALIGN_ROOT 0
#endif

#if GRAEHL_D_ARY_HEAP_CACHE_ALIGN_ROOT
#include <graehl/shared/aligned_allocator.hpp>
#define GRAEHL_D_ARY_DEFAULT_CONTAINER(T, ARITY) std::vector<T, graehl::aligned_allocator<T, ARITY>>
#else
#define GRAEHL_D_ARY_DEFAULT_CONTAINER(T, ARITY) std::vector<T>
#endif

namespace graehl {

template <class Key, class Index = unsigned>
struct no_index_in_heap {};
template <class Key, class Index>
Index get(no_index_in_heap<Key, Index> const&, Key const& k) {
  std::abort();
  return 0;
}
template <class Key, class Index, class Index2>
void put(no_index_in_heap<Key, Index> const&, Key const&, Index2 i) {
}

template <class Key, class Distance>
struct deref_distance {};
template <class Key, class Distance>
Distance get(deref_distance<Key, Distance> const&, Key const& k) {
  return *k;
}
template <class Key, class Distance>
void put(deref_distance<Key, Distance> const&, Key const&, Distance t) {
  std::abort();
}

template <class K>
struct identity_distance {
  typedef K key_type;
  typedef K value_type;
  typedef K const& reference;
  typedef boost::readable_property_map_tag category;
  K const& operator[](K const& key) const { return key; }
};
template <class K>
K const& get(identity_distance<K>, K const& key) {
  return key;
}
}

namespace boost {
template <class PMap>
struct property_traits;
template <class Key, class Index>
struct property_traits<graehl::no_index_in_heap<Key, Index>> {
  typedef boost::writable_property_map_tag category;
  typedef Key key_type;
  typedef Index value_type;
};
template <class Key, class Distance>
struct property_traits<graehl::deref_distance<Key, Distance>> {
  typedef boost::writable_property_map_tag category;
  typedef Key key_type;
  typedef Distance value_type;
};
}

namespace graehl {
static const std::size_t OPTIMAL_HEAP_ARITY
    = 2;  // boost docs claimed 4 was optimal for dijkstra. TODO: validate that

/* adapted from boost/graph/detail/d_ary_heap.hpp

  local modifications:

  clear, heapify, append range/container, Size type template arg, reserve constructor arg

  hole+move rather than swap.  note: swap would be more efficient for heavyweight keys, until move ctors exist

  don't set locmap to -1 when removing from heap (waste of time)

  indices start at 0, not 1:
  // unlike arity=2 case, you don't gain anything by having indices start at 1, with 0-based child indices
  // root @1, A=2, children indices m= {0,1}: parent(i)=i/2, child(i, m)=2*i+m
  // root @0: parent(i)=(i-1)/A child(i, n)=i*A+n+1-can't improve on this except child(i, m)=i*A+m
  (integer division, a/b=floor(a/b), so (i-1)/A = ceil(i/A)-1, or greatest int less than (i/A))

  actually, no need to adjust child index, since child is called only once and inline

  e.g. for A=3 gorn address in tree -> index

  () = root -> 0
  (1) -> 1
  (2) -> 2
  (3) (A) -> 3
  (1,1) -> (1*A+1) = 4
  (1,2) -> (1*A+2) = 5
  (1,3) -> (1*A+3) = 6
  (2,1) -> (2*A+1) = 7
  etc.

//TODO: block-align siblings!  assume data[0] is 16 or 32-byte aligned ... then we want root @ index
(blocksize-1).  see http://www.lamarca.org/anthony/pubs/heaps.pdf pg8.  for pow2(e.g. 4)-ary heap, it may be
reasonable to  use root @index A-1.  however, suppose the key size is not padded to a power of 2 (e.g. 12
bytes), then we would need internal gaps at times.  would want to use compile const template based inlineable
alignment math for this?  possibly use a container like vector that lets you specify padding relative to some
address multiple for v[0].

 optimal D: see http://www.lamarca.org/anthony/pubs/heaps.pdf pg 9.  depedns on relative cost of swap,
compare, but in all cases except swap=free, 2 is worse than 3-4.  for expensive swap (3x compare), 4 still as
good as 5.  so just use 4.  boost benchmarking djikstra agrees; 4 is best.

 cache-aligned 4-heap speedup over regular 2-heap is 10-80% (for huge heaps, the speedup is more)

 splay/skew heaps are worse than 2heap or aligned 4heap in practice.

 //TODO: switch from heapify (Floyd's method) to repeated push past some size limit (in bytes) due to cache
effect -
 #define GRAEHL_D_ARY_BYTES_OUT_OF_CACHE 0x1000000

 //TODO: assuming locmap is an lvalue pmap, we can be more efficient.  on the other hand, if it's an intrusive
property map to an interned mutable object, there's no difference in performance, and that's what i'm going to
do in my first uses.  plus, if keys are indices and the map is a vector, it's barely any overhead.

 */

//
//=======================================================================
// Copyright 2009 Trustees of Indiana University
// Authors: Jeremiah J. Willcock, Andrew Lumsdaine
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
//

#include <boost/shared_array.hpp>
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

// D-ary heap using an indirect compare operator (use identity_property_map
// as DistanceMap to get a direct compare operator).  This heap appears to be
// commonly used for Dijkstra's algorithm for its good practical performance
// on some platforms; asymptotically, it's not optimal; it has an O(lg N) decrease-key
// operation, which is (amortized) constant time on a relaxed heap or fibonacci heap.  The
// implementation is mostly based on the binary heap page on Wikipedia and
// online sources that state that the operations are the same for d-ary
// heaps.  This code is not based on the old Boost d-ary heap code.
//
// - d_ary_heap_indirect is a model of UpdatableQueue as is needed for
//   dijkstra_shortest_paths.
//
// - Value must model Assignable.
// - Arity must be at least 2 (optimal value appears to be 4, both in my and
//   third-party experiments).
// - IndexInHeapMap must be a ReadWritePropertyMap from Value to
//   Container::size_type (to store the index of each stored value within the
//   heap for decrease-key aka update).
// - DistanceMap must be a ReadablePropertyMap from Value to something
//   (typedef'ed as distance_type).
// - Compare must be a BinaryPredicate used as a less-than operator on
//   distance_type.
// - Container must be a random-access, contiguous container (in practice,
//   the operations used probably require that it is std::vector<Value>).
//
template <class Value, std::size_t Arity, class DistanceMap = identity_distance<Value>,
          class IndexInHeapPropertyMap = no_index_in_heap<Value, unsigned>,
          class Better = std::less<typename boost::property_traits<DistanceMap>::value_type>,
          class Container = GRAEHL_D_ARY_DEFAULT_CONTAINER(Value, Arity), class Size = unsigned,
          class Equal = std::equal_to<Value>>
class d_ary_heap_indirect {

 public:
#if GRAEHL_CPP11
  // TODO: use perfect forwarding of universal reftype args
  typedef Value&& MoveableValueRef;
#define GRAEHL_D_ARY_FORWARD_REF(x) std::forward<Value>(x)
// TODO: replace more (MoveableValueRef)x by this
#else
  typedef Value const& MoveableValueRef;
#define GRAEHL_D_ARY_FORWARD_REF(x) x
#endif
  typedef Container container_type;
  typedef Size size_type;
  typedef Value value_type;
  typedef typename Container::const_iterator const_iterator;
  typedef const_iterator iterator;
  // The distances being compared using better and that are stored in the
  // distance map
  typedef typename boost::property_traits<DistanceMap>::value_type distance_type;
  d_ary_heap_indirect(DistanceMap const& distance = DistanceMap(),
                      IndexInHeapPropertyMap const& index_in_heap = IndexInHeapPropertyMap(),
                      Better const& better = Better(), size_type container_reserve = 1024,
                      Equal const& equal = Equal())
      : better(better), data(), distance(distance), index_in_heap(index_in_heap), equal(equal) {
    if (container_reserve) data.reserve(container_reserve);
  }
  /* Implicit copy constructor */
  /* Implicit assignment operator */

  template <class C>
  void append_heapify(C const& c) {
    data.reserve(data.size() + c.size());
    append_heapify(c.begin(), c.end());
  }

  template <class I>
  void append_heapify(I begin, I end) {
    std::size_t s = data.size();
    data.insert(data.end(), begin, end);
    set_index_in_heap(s);  // allows contains() and heapify() to function properly
    heapify();
  }

  template <class C>
  void append_push(C const& c) {
    data.reserve(data.size() + c.size());
    append_push(c.begin(), c.end());
  }

  // past some threshold, this should be faster than append_heapify.  also, if there are many existing
  // elements it will be faster.
  template <class I>
  void append_push(I begin, I end) {
    for (; begin != end; ++begin) push(*begin);
  }

  template <class C>
  void append(C const& c) {
    if (GRAEHL_D_ARY_APPEND_ALWAYS_PUSH || data.size() >= c.size() / 2)
      append_push(c);
    else
      append_heapify(c);
  }

  // past some threshold, this should be faster than append_heapify.  also, if there are many existing
  // elements it will be faster.
  template <class I>
  void append(I begin, I end) {
    if (GRAEHL_D_ARY_APPEND_ALWAYS_PUSH || data.size() >= 0x10000)
      append_push(begin, end);
    else
      append_heapify(begin, end);
  }

  /**
     doesn't maintain heap property for you. so unless you added in sorted order, you must call
     finish_adding() after
  */
  template <class V>
  void add_unsorted(V const& v) {
    put(index_in_heap, v, data.size());  // allows contains() and heapify() to function properly
    data.push_back(v);
  }

#if GRAEHL_CPP11
  template <class... Args>
  void emplace_unsorted(Args&&... args) {
    Size i = data.size();
    data.emplace_back(std::forward<Args>(args)...);
    put(index_in_heap, data.back(), i);
  }
#else
  template <class V>
  void emplace_unsorted(V const& v) {
    Size i = data.size();
    data.push_back(v);
    put(index_in_heap, data.back(), i);
  }
#endif

  /// call after all add/emplace_unsorted done, unless you already
  void finish_adding() { heapify(); }

  // for debugging, please
  size_type loc(Value const& v) const { return get(index_in_heap, v); }

  // call heapify yourself after.
  // could allow mutation of data directly, e.g. push_back 1 at a time - but then they could forget to
  // heapify()

  // from bottom of heap tree up, turn that subtree into a heap by adjusting the root down
  // for n=size, array elements indexed by floor(n/2) + 1, floor(n/2) + 2, ... , n are all leaves for the
  // tree, thus each is an one-element heap already
  // warning: this is many fewer instructions but, at some point (when heap doesn't fit in Lx cache) it will
  // become slower than repeated push().
  void set_index_in_heap(std::size_t i = 0) {
    for (std::size_t e = data.size(); i < e; ++i) {
      // cppcheck-suppress unusedScopedObject
      put(index_in_heap, data[i], i);
    }
  }

  /*
The basic building block of "heapify" is a simple procedure which I'd
call "preserve_heap_property_down". It looks at a node that is not a leaf, and among
that non-leaf node and its two children, which is largest. Then it
swap that largest node to the top, so that the node becomes the
largest among the three---satisfy the "heap property". Clearly,
constant time.

To heapify the whole tree, we will heapify it from the bottom (so
"bottom up"). Heapifying a node at the "bottom" (i.e., next to a
leaf) is trivial; heapifying a node that is not bottom might cause the
heap property of nodes below to be violated. In that case we will
have to heapify the node below as well, which might cause a node one
more level below to violate heap property. So to heapify a node at
level n, we might need to call preserve_heap_property_down (height-1) times.

Now we show that a whole run of heapify of a tree with n=2^k-1 nodes
will never call preserve_heap_property_down more than n times. We do it by finding a
way to charge the calls to preserve_heap_property_down so that each node is never
charged more than once. Note that we simplify things by always
considering full binary trees (otherwise, the claim has to be a bit
more complicated).

Let's consider the bottom layer. To heapify a node with two children,
we need one call to preserve_heap_property_down. It is charged to left leaf. So we
have this:

After heapify O
/ \
X O

where O shows a node that is not charged yet, and X show a node which
is already charged. Once all the next-to-bottom nodes have been
heapified, we start to heapify the next-to-next-to-bottom nodes.
Before heapifying a node there, we have

Before heapify O
_/ \_
O O
/ \ / \
X O X O

To heapify this node, we might need two calls to preserve_heap_property_down. We
charge these two calls to the two uncharged nodes of the left subtree.
So we get:

After heapify O
_/ \_
X O
/ \ / \
X X X O

So none of the nodes is charged more than once, and we still have some
left for the next level, where before heapify the picture is:

Before heapify O
____/ \____
O O
_/ \_ _/ \_
X O X O
/ \ / \ / \ / \
X X X O X X X O

Heapifying at this level requires at most 3 calls to preserve_heap_property_down,
which are charged again to the left branch. So after that we get

After heapify O
____/ \____
X O
_/ \_ _/ \_
X X X O
/ \ / \ / \ / \
X X X X X X X O

We note a pattern: the path towards the right-most leaf is never
charged. When heapifying a level, one of the branches will always
have enough uncharged nodes to pay for the "expensive" heapify at the
top, while the other branch will still be uncharged to keep the
pattern. So this pattern is maintained until the end of the heapify
procedure, making the number of steps to be at most n-k = 2^k-k-1.
This is definitely linear to n.
   */
  void heapify() {
    EIFDBG(DDARY, 1, SHOWM1(DDARY, "heapify", data.size()));
    for (size_type i = parent(data.size());
         i > 0;) {  // starting from parent of last node, ending at first child of root (i==1)
      --i;
      EIFDBG(DDARY, 2, SHOWM1(DDARY, "heapify", i));
      preserve_heap_property_down(i);
    }
    verify_heap();
  }

  void reserve(size_type s) { data.reserve(s); }

  size_type size() const { return data.size(); }

  bool empty() const { return data.empty(); }

  const_iterator begin() const { return data.begin(); }

  const_iterator end() const { return data.end(); }

  void clear() {
#if GRAEHL_D_ARY_TRACK_OUT_OF_HEAP
    using boost::put;
    for (typename Container::iterator i = data.begin(), e = data.end(); i != e; ++i)
      put(index_in_heap, *i, (size_type)GRAEHL_D_ARY_HEAP_NULL_INDEX);
#endif
    data.clear();
  }

/**
   you must have put v's distance in the DistanceMap before pushing
*/
#if GRAEHL_CPP11
  template <class Univ>
  void push(Univ&& v)
#else
  void push(MoveableValueRef v)
#endif
  {
    size_type index = data.size();
    if (index) {
#if GRAEHL_CPP11
      data.emplace_back();
#else
      data.push_back(Value());  // (hoping default construct is cheap, construct-copy inline)
#endif
      preserve_heap_property_up(GRAEHL_D_ARY_FORWARD_REF(v), index, get(distance, v));
      // we don't have to recopy v, or init index_in_heap
      verify_heap();
    } else {
      put(index_in_heap, v, 0);
#if GRAEHL_CPP11
      data.emplace_back(GRAEHL_D_ARY_FORWARD_REF(v));
#else
      data.push_back(v);  // (hoping default construct is cheap, construct-copy inline)
#endif
    }
  }

  Value& top() { return data[0]; }

  Value const& top() const { return data[0]; }

  Value& front() { return data[0]; }

  Value const& front() const { return data[0]; }

  /**
     as with top(), take care not to invalidate heap property or item<->location map
  */
  Value& operator[](size_type i) { return data[i]; }

  Value const& operator[](size_type i) const { return data[i]; }

  void pop() {
    using boost::put;
    if (GRAEHL_D_ARY_TRACK_OUT_OF_HEAP) put(index_in_heap, data[0], (size_type)GRAEHL_D_ARY_HEAP_NULL_INDEX);
    size_type sz = data.size();
    if (sz == 1)
      data.pop_back();
    else {
      put(index_in_heap, data[0] = (MoveableValueRef)data.back(), 0);
      data.pop_back();
      preserve_heap_property_down();
      verify_heap();
    }
  }

// This function assumes the key has been improved
// (distance has become smaller, so it may need to rise toward top().
// i.e. decrease-key in a min-heap
#if GRAEHL_CPP11
  template <class Univ>
  void update(Univ&& v)
#else
  void update(MoveableValueRef v)
#endif
  {
    using boost::get;
    size_type index = get(index_in_heap, v);
    assert(index <= data.size());
    preserve_heap_property_up(GRAEHL_D_ARY_FORWARD_REF(v), index, get(distance, v));
    verify_heap();
  }

  distance_type best(distance_type null = 0) const { return empty() ? null : get(distance, data[0]); }
  distance_type second_best(distance_type null = 0) const {
    if (data.size() < 2) return null;
    int m = std::min(data.size(), Arity + 1);
    distance_type b = get(distance, data[1]);
    for (int i = 2; i < m; ++i) {
      distance_type d = get(distance, data[i]);
      if (better(d, b)) b = d;
    }
    return b;
  }

#ifdef __clang__
#pragma clang diagnostic ignored "-Wtautological-compare"
#endif

  bool contains(Value const& v, size_type i) const {
    if (GRAEHL_D_ARY_TRACK_OUT_OF_HEAP) return i != (size_type)GRAEHL_D_ARY_HEAP_NULL_INDEX;
    size_type sz = data.size();
    EIFDBG(DDARY, 2, SHOWM2(DDARY, "d_ary_heap contains", i, data.size()));
    return i >= 0 && i < sz && equal(v, data[i]);
    // note: size_type may be signed (don't recommend it, though) - thus i>=0
    // check to catch uninit. data
  }

  bool contains(Value const& v) const {
    using boost::get;
    return contains(v, get(index_in_heap, v));
  }

/** insert if not present, else update (update means *improve* (move closer to top) only) as in best-first
 * search*/
#if GRAEHL_CPP11
  template <class Univ>
  void push_or_update(Univ&& v)
#else
  void push_or_update(Value const& v)
#endif
  {
    using boost::get;
    size_type index = get(index_in_heap, v);
    if (contains(v, index))
      preserve_heap_property_up(GRAEHL_D_ARY_FORWARD_REF(v), index, get(distance, v));
    else
      push(GRAEHL_D_ARY_FORWARD_REF(v));
  }

 private:
  Better better;
  Container data;
  DistanceMap distance;
  IndexInHeapPropertyMap index_in_heap;
  Equal equal;

  // Get the parent of a given node in the heap
  static inline size_type parent(size_type index) { return (index - 1) / Arity; }

  // Get the child_idx'th child of a given node; 0 <= child_idx < Arity
  static inline size_type child(size_type index, std::size_t child_idx) {
    return index * Arity + child_idx + 1;
  }

  // Swap two elements in the heap by index, updating index_in_heap
  void swap_heap_elements(size_type index_a, size_type index_b) {
    assert(index_a != index_b);
    Value& willb = data[index_a];
    Value& willa = data[index_b];
    using std::swap;
    swap(willb, willa);
    put(index_in_heap, willa, index_a);
    put(index_in_heap, willb, index_b);
  }

  void move_heap_element(MoveableValueRef v, size_type ito) {
    using boost::put;
    put(index_in_heap, data[ito] = (MoveableValueRef)v, ito);
  }

  // Verify that the array forms a heap; commented out by default
  void verify_heap() const {
// This is a very expensive test so it should be disabled even when
// NDEBUG is not defined
#if GRAEHL_D_ARY_VERIFY_HEAP
    using boost::get;
    for (size_t i = 1; i < data.size(); ++i) {
      if (better(get(distance, data[i]), get(distance, data[parent(i)]))) {
        assert(!"Element is smaller than its parent");
      }
      if (get(index_in_heap, data[i]) != i) {
        assert(!"Element is where its index_in_heap doesn't say it is.");
      }
    }
#endif
  }

  // we have a copy of the key, so we don't need to do that stupid find # of levels to move then move.  we act
  // as though data[index]=currently_being_moved, but in fact it's an uninitialized "hole", which we fill at
  // the very end
  void preserve_heap_property_up(MoveableValueRef currently_being_moved, size_type index) {
    using boost::get;
    preserve_heap_property_up(GRAEHL_D_ARY_FORWARD_REF(currently_being_moved), index,
                              get(distance, currently_being_moved));
  }

  /**
     disabled because distance map may not be writable. would need traits to enable
  */
  /*
  void preserve_heap_property_up_set_dist(MoveableValueRef currently_being_moved, distance_type
  dbetter) {
    using boost::get;
    using boost::put;
    put(distance, currently_being_moved, dbetter);
    preserve_heap_property_up(currently_being_moved, get(index_in_heap, currently_being_moved), dbetter);
    verify_heap();
  }
  */

  /// put(index_in_heap, data[index] = currently_being_moved, index); preserve_heap_property_up(index);
  void preserve_heap_property_up(MoveableValueRef move_to_index_first, size_type index,
                                 distance_type move_to_index_first_dist) {
    using boost::put;
    using boost::get;
    assert(get(distance, move_to_index_first) == move_to_index_first_dist);
    for (;;) {
      if (index == 0) break;  // Stop at root - but still need to assign move_to_index_first to posn 0
      size_type parent_index = parent(index);
      Value& parent_value = data[parent_index];
      if (better(move_to_index_first_dist, get(distance, parent_value))) {
        put(index_in_heap, data[index] = (MoveableValueRef)parent_value, index);
        index = parent_index;
      } else {
        break;  // Heap property satisfied
      }
    }
    // finish "swap chain" by filling hole w/ move_to_index_first
    put(index_in_heap, data[index] = (MoveableValueRef)move_to_index_first, index);
  }

  // Starting at a node, move up the tree swapping elements to preserve the
  // heap property.  doesn't actually use swap; uses hole
  void preserve_heap_property_up(size_type index) {
    using boost::get;
    if (index == 0) return;  // Do nothing on root
    Value& vali = data[index];
    size_type parent_index = parent(index);
    distance_type disti = get(distance, vali);
    Value& valparent = data[parent_index];
    if (better(disti, get(distance, valparent))) {
      Value copyi(vali);
      put(index_in_heap, data[index] = (MoveableValueRef)valparent, index);
      preserve_heap_property_up((MoveableValueRef)copyi, parent_index, disti);
    }
    return;
    verify_heap();
  }

  /// \return 0 if currently_being_moved is better than all children of parent_index else position of child
  /// that should move to parent_index (best child). heap_size should == data.size() (caching)
  size_type which_child_down(size_type parent_index, distance_type parent_dist, Value* heap_ptr,
                             size_type heap_size) {
    size_type first_child_index = child(parent_index, 0);
    size_type smallest_child_index = 0;
    distance_type d;
    for (size_type i = first_child_index, e = std::min(first_child_index + Arity, heap_size); i < e; ++i)
      if (better(d = get(distance, heap_ptr[i]), parent_dist)) {
        smallest_child_index = i;
        parent_dist = d;
      }
    return smallest_child_index;
  }

#undef GRAEHL_D_ARY_MAYBE_IMPROVE_CHILD_I
#define GRAEHL_D_ARY_MAYBE_IMPROVE_CHILD_I                   \
  do {                                                       \
    distance_type i_dist = get(distance, child_base_ptr[i]); \
    if (better(i_dist, smallest_child_dist)) {               \
      smallest_child_index = i;                              \
      smallest_child_dist = i_dist;                          \
    }                                                        \
  } while (0)
/** From the root, swap elements (each one with its smallest child) if there
   are any parent-child pairs that violate the heap property.  v is placed at
   data[i], but then pushed down (note: data[i] won't be read explicitly; it
   will instead be overwritten by percolation).  this also means that v must
   be a copy of data[i] if it was already at i.  e.g. v=data.back(), i=0,
   sz=data.size()-1 for pop(), implicitly swapping data[i], data.back(), and
   doing data.pop_back(), then adjusting from 0 down w/ swaps.  updates
   index_in_heap for v. on first call currently_being_moved must have been at
   index.  .
*/
#if GRAEHL_CPP11
  template <class Univ>
#endif
  void preserve_heap_property_down(
#if GRAEHL_CPP11
      Univ&& move_to_index_first,
#else
      MoveableValueRef move_to_index_first,
#endif
      size_type index, size_type heap_size) {
    using boost::put;
    //// hole at index - move_to_index_first to be put here when we find the final hole spot
    EIFDBG(DDARY, 4, SHOWM3(DDARY, "preserve_heap_property_down impl", index, move_to_index_first, heap_size));
    using boost::get;
    distance_type move_down_dist = get(distance, move_to_index_first);
    Value* data_ptr = &data[0];
    for (;;) {
      size_type first_child_index = child(index, 0);
      if (first_child_index >= heap_size) {
        put(index_in_heap, data[index] = (MoveableValueRef)move_to_index_first, index);
        break;
      }
      Value* child_base_ptr
          = data_ptr + first_child_index;  // using index of first_child_index+smallest_child_index because we
      // hope optimizer will be smart enough to const-unroll a loop below
      // if we do this.  i think the optimizer would have gotten it even
      // without our help (i.e. store root-relative index)

      // begin find best child index/distance
      size_type smallest_child_index
          = 0;  // don't add to base first_child_index every time we update which is smallest.
      distance_type smallest_child_dist = get(distance, child_base_ptr[smallest_child_index]);
      if (first_child_index + Arity <= heap_size) {
        // avoid repeated heap_size boundcheck (should test if this is really a speedup - instruction cache
        // tradeoff - could use upperbound = min(Arity, heap_size-first_child_index) instead.  but this
        // optimizes to a fixed number of iterations (compile time known) so probably worth it
        for (size_type i = 1; i < Arity; ++i) {
          GRAEHL_D_ARY_MAYBE_IMPROVE_CHILD_I;
        }
      } else {
        for (size_type i = 1, e = heap_size - first_child_index; i < e; ++i) {
          GRAEHL_D_ARY_MAYBE_IMPROVE_CHILD_I;
        }
      }
      // end: know best child

      if (better(smallest_child_dist, move_down_dist)) {
        put(index_in_heap, data[index] = (MoveableValueRef)child_base_ptr[smallest_child_index], index);
        // instead of swapping, move.
        // move_heap_element((MoveableValueRef)child_base_ptr[smallest_child_index], index);  // move up
        index = first_child_index + smallest_child_index;  // descend - hole is now here
      } else {
        put(index_in_heap, data[index] = (MoveableValueRef)move_to_index_first, index);
        break;
        // move_heap_element((MoveableValueRef)move_to_index_first, index);  // finish "swap chain" by
        // filling hole
      }
    }
    verify_heap();
  }

  void preserve_heap_property_down(size_type i) {
    EIFDBG(DDARY, 3, SHOWM3(DDARY, "preserve_heap_property_down", i, data[i], data.size()));
    Value copyi(data[i]);  // TODO: we should only copy if heap property isn't already present. or give up and
    // just use swap for this (see usage from heapify)
    preserve_heap_property_down((MoveableValueRef)copyi, i, data.size());
  }

 public:
  /**
     if you modify top() and might need to move element down since it's no longer the least.
  */
  void adjust_top() { this->preserve_heap_property_down(); }

  // moves what's at root downwards if needed
  void preserve_heap_property_down() {
    assert(!data.empty());
    Value* v0 = &data[0];
    distance_type d0 = get(distance, *v0);
    size_type n = data.size();
    if (n > Arity) {
      size_type swapi = 0;
      for (size_type i = 1; i <= Arity; ++i) {
        distance_type di = get(distance, v0[i]);
        if (better(di, d0)) {
          d0 = di;
          swapi = i;
        }
      }
      if (swapi) {
        Value copy0(*v0);
        using boost::put;
        Value& vs = v0[swapi];
        put(index_in_heap, data[0] = (MoveableValueRef)vs, 0);
        preserve_heap_property_down((MoveableValueRef)copy0, swapi, n);
      }
    } else if (n > 1) {
      size_type swapi = 0;
      for (size_type i = 1; i < n; ++i) {
        distance_type di = get(distance, v0[i]);
        if (better(di, d0)) {
          d0 = di;
          swapi = i;
        }
      }
      if (swapi) swap_heap_elements(swapi, 0);
    }
    verify_heap();
  }
};

}

#endif

max_stars_repo_name: graehl/carmel

max_issues_repo_name: graehl/carmel

max_forks_repo_name: graehl/carmel


text:
/*!
 * @file
 * Contains unit tests for the various right fold implementations.
 *
 *
 * @copyright Louis Dionne 2014
 * Distributed under the Boost Software License, Version 1.0.
 *         (See accompanying file LICENSE.md or copy at
 *             http://www.boost.org/LICENSE_1_0.txt)
 */

#include <boost/mpl11/detail/right_folds/until_naive.hpp>
#include <boost/mpl11/detail/right_folds/variadic_naive.hpp>
#include <boost/mpl11/detail/right_folds/variadic_unrolled.hpp>

#include <boost/mpl11/detail/test/foldr.hpp>
#include <boost/mpl11/list.hpp>

using namespace boost::mpl11;

template <typename f, typename z, typename ...xs>
using variadic_naive = detail::right_folds::variadic_naive<
    f::type::template apply, z, xs...
>;

template <typename f, typename z, typename ...xs>
using variadic_unrolled = detail::right_folds::variadic_unrolled<
    f::type::template apply, z, xs...
>;

template <typename f, typename z, typename ...xs>
using until_naive = detail::right_folds::until_naive<
    is_empty, f::type::template apply, z, list<xs...>
>;

struct tests
    : detail::test_foldr<variadic_naive>
    , detail::test_foldr<variadic_unrolled>

    , detail::test_foldr<until_naive>
{ };

int main() { }


text:
/* --------------------------------------------------------------------------
*
* (C) Copyright …
*
* ---------------------------------------------------------------------------
*/

/*!
 * @file Transform3DMatConvertersTest.cpp
 * @date 20/02/2018
 * @author Alessandro Bianco
 */

/*!
 * @addtogroup CommonTests
 *
 * Testing conversion from cv Matrix to Transform3D and viceversa.
 *
 *
 * @{
 */

/* --------------------------------------------------------------------------
 *
 * Includes
 *
 * --------------------------------------------------------------------------
 */
#include <catch.hpp>
#include <Converters/Transform3DToMatConverter.hpp>
#include <Converters/MatToTransform3DConverter.hpp>
#include <Types/CPP/Pose.hpp>
#include <Errors/Assert.hpp>
#include <boost/smart_ptr.hpp>
#include <Eigen/Geometry>

using namespace Converters;
using namespace PoseWrapper;
const double EPSILON = 0.000000001;

TEST_CASE( "Mat to Transform 3D and Back", "[MatToTransform]" )
	{
	MatToTransform3DConverter firstConverter;
	Transform3DToMatConverter secondConverter;

	Eigen::Matrix4f inputTransform;
	Eigen::Quaternionf inputRotation(std::cos(M_PI/2), std::sin(M_PI/2), std::sin(M_PI/2)/2, std::sin(M_PI/2)*2);
	Eigen::Matrix3f eigenRotationMatrix = inputRotation.normalized().toRotationMatrix();
	inputTransform << 	eigenRotationMatrix(0,0), eigenRotationMatrix(0,1), eigenRotationMatrix(0,2), 0.3,
				eigenRotationMatrix(1,0), eigenRotationMatrix(1,1), eigenRotationMatrix(1,2), 0.4,
				eigenRotationMatrix(2,0), eigenRotationMatrix(2,1), eigenRotationMatrix(2,2), 0.6,
				0, 0, 0, 1;

	cv::Mat cvInputTransform(3, 4, CV_32FC1);
	for(unsigned row = 0; row<3; row++)
		{
		for(unsigned column = 0; column < 4; column++)
			{
			cvInputTransform.at<float>(row, column) = inputTransform(row, column);
			}
		}

	Transform3DSharedConstPtr asnTransform3D = firstConverter.ConvertShared(cvInputTransform);
	REQUIRE( GetXPosition(*asnTransform3D) < inputTransform(0, 3) + EPSILON );
	REQUIRE( GetXPosition(*asnTransform3D) > inputTransform(0, 3) - EPSILON );
	REQUIRE( GetYPosition(*asnTransform3D) < inputTransform(1, 3) + EPSILON );
	REQUIRE( GetYPosition(*asnTransform3D) > inputTransform(1, 3) - EPSILON );
	REQUIRE( GetZPosition(*asnTransform3D) < inputTransform(2, 3) + EPSILON );
	REQUIRE( GetZPosition(*asnTransform3D) > inputTransform(2, 3) - EPSILON );
	REQUIRE( GetXOrientation(*asnTransform3D) < inputRotation.normalized().x() + EPSILON );
	REQUIRE( GetXOrientation(*asnTransform3D) > inputRotation.normalized().x() - EPSILON );
	REQUIRE( GetYOrientation(*asnTransform3D) < inputRotation.normalized().y() + EPSILON );
	REQUIRE( GetYOrientation(*asnTransform3D) > inputRotation.normalized().y() - EPSILON );
	REQUIRE( GetZOrientation(*asnTransform3D) < inputRotation.normalized().z() + EPSILON );
	REQUIRE( GetZOrientation(*asnTransform3D) > inputRotation.normalized().z() - EPSILON );
	REQUIRE( GetWOrientation(*asnTransform3D) < inputRotation.normalized().w() + EPSILON );
	REQUIRE( GetWOrientation(*asnTransform3D) > inputRotation.normalized().w() - EPSILON );

	cv::Mat outputTransform = secondConverter.ConvertShared(asnTransform3D);
	for(unsigned rowIndex = 0; rowIndex < 3; rowIndex++)
		{
		for(unsigned columnIndex = 0; columnIndex < 4; columnIndex++)
			{
			REQUIRE(outputTransform.at<float>(rowIndex, columnIndex) < inputTransform(rowIndex, columnIndex) + EPSILON);
			REQUIRE(outputTransform.at<float>(rowIndex, columnIndex) > inputTransform(rowIndex, columnIndex) - EPSILON);
			}
		}

	asnTransform3D.reset();
	}

TEST_CASE( "Transform3D to Mat and Back", "[Transform3DToMat]" )
	{
	MatToTransform3DConverter firstConverter;
	Transform3DToMatConverter secondConverter;

	Eigen::Matrix4f inputTransform;
	Eigen::Quaternionf inputRotation(std::cos(M_PI/2), std::sin(M_PI/2), std::sin(M_PI/2)/2, std::sin(M_PI/2)*2);
	Eigen::Matrix3f eigenRotationMatrix = inputRotation.normalized().toRotationMatrix();
	inputTransform << 	eigenRotationMatrix(0,0), eigenRotationMatrix(0,1), eigenRotationMatrix(0,2), 0.3,
				eigenRotationMatrix(1,0), eigenRotationMatrix(1,1), eigenRotationMatrix(1,2), 0.4,
				eigenRotationMatrix(2,0), eigenRotationMatrix(2,1), eigenRotationMatrix(2,2), 0.6,
				0, 0, 0, 1;

	cv::Mat cvInputTransform(3, 4, CV_32FC1);
	for(unsigned row = 0; row<3; row++)
		{
		for(unsigned column = 0; column < 4; column++)
			{
			cvInputTransform.at<float>(row, column) = inputTransform(row, column);
			}
		}

	Transform3DSharedConstPtr asnTransform3D = firstConverter.ConvertShared(cvInputTransform);
	cv::Mat intermediateTransform = secondConverter.ConvertShared(asnTransform3D);
	Transform3DSharedConstPtr outputTransform = firstConverter.ConvertShared(intermediateTransform);

	REQUIRE( GetXPosition(*asnTransform3D) < GetXPosition(*outputTransform) + EPSILON );
	REQUIRE( GetXPosition(*asnTransform3D) > GetXPosition(*outputTransform) - EPSILON );
	REQUIRE( GetYPosition(*asnTransform3D) < GetYPosition(*outputTransform) + EPSILON );
	REQUIRE( GetYPosition(*asnTransform3D) > GetYPosition(*outputTransform) - EPSILON );
	REQUIRE( GetZPosition(*asnTransform3D) < GetZPosition(*outputTransform) + EPSILON );
	REQUIRE( GetZPosition(*asnTransform3D) > GetZPosition(*outputTransform) - EPSILON );
	REQUIRE( GetXOrientation(*asnTransform3D) < GetXOrientation(*outputTransform) + EPSILON );
	REQUIRE( GetXOrientation(*asnTransform3D) > GetXOrientation(*outputTransform) - EPSILON );
	REQUIRE( GetYOrientation(*asnTransform3D) < GetYOrientation(*outputTransform) + EPSILON );
	REQUIRE( GetYOrientation(*asnTransform3D) > GetYOrientation(*outputTransform) - EPSILON );
	REQUIRE( GetZOrientation(*asnTransform3D) < GetZOrientation(*outputTransform) + EPSILON );
	REQUIRE( GetZOrientation(*asnTransform3D) > GetZOrientation(*outputTransform) - EPSILON );
	REQUIRE( GetWOrientation(*asnTransform3D) < GetWOrientation(*outputTransform) + EPSILON );
	REQUIRE( GetWOrientation(*asnTransform3D) > GetWOrientation(*outputTransform) - EPSILON );

	asnTransform3D.reset();
	outputTransform.reset();
	}

TEST_CASE("Bad Transform conversion 1 (Mat)", "[Bad Transform 1]")
	{
	MatToTransform3DConverter firstConverter;

	Eigen::Matrix4f inputTransform;
	inputTransform << 0.3, 0.2, 0.1, 0.4, 0.3, 0.2, 0.1, 0.1, 0.5, 0.3, 0.2, 0.1, 1, 0, 0, 1;

	cv::Mat cvInputTransform(3, 4, CV_32FC1);
	for(unsigned row = 0; row<3; row++)
		{
		for(unsigned column = 0; column < 4; column++)
			{
			cvInputTransform.at<float>(row, column) = inputTransform(row, column);
			}
		}

	REQUIRE_THROWS( firstConverter.ConvertShared(cvInputTransform) );
	}

TEST_CASE("Bad Transform conversion 2 (Mat)", "[Bad Transform 2]")
	{
	MatToTransform3DConverter firstConverter;

	Eigen::Matrix4f inputTransform;
	inputTransform << 0.3, 0.2, 0.1, 0.4, 0.3, 0.2, 0.1, 0.1, 0.5, 0.3, 0.2, 0.1, 0, 0, 0, 1;

	cv::Mat cvInputTransform(3, 4, CV_32FC1);
	for(unsigned row = 0; row<3; row++)
		{
		for(unsigned column = 0; column < 4; column++)
			{
			cvInputTransform.at<float>(row, column) = inputTransform(row, column);
			}
		}

	REQUIRE_THROWS( firstConverter.ConvertShared(cvInputTransform) );
	}