path: root/contrib/libs/hyperscan/src/fdr/fdr_confirm_compile.cpp

/* 
 * Copyright (c) 2015-2019, 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. 
 */ 
 
#include "fdr_internal.h" 
#include "fdr_compile_internal.h" 
#include "fdr_confirm.h" 
#include "engine_description.h" 
#include "teddy_engine_description.h" 
#include "ue2common.h" 
#include "util/alloc.h" 
#include "util/bitutils.h" 
#include "util/compare.h" 
#include "util/container.h"
#include "util/verify_types.h" 
 
#include <algorithm> 
#include <cstring> 
#include <set> 
 
using namespace std; 
 
namespace ue2 { 
 
using BC2CONF = map<BucketIndex, bytecode_ptr<FDRConfirm>>;
 
static 
u64a make_u64a_mask(const vector<u8> &v) { 
    assert(v.size() <= sizeof(u64a)); 
    if (v.size() > sizeof(u64a)) { 
        throw std::exception(); 
    } 
 
    u64a mask = 0; 
    size_t vlen = v.size(); 
    size_t len = std::min(vlen, sizeof(mask)); 
    unsigned char *m = (unsigned char *)&mask; 
    memcpy(m + sizeof(mask) - len, &v[vlen - len], len); 
    return mask; 
} 
 
/** 
 * Build a temporary vector of LitInfo structures (without the corresponding 
 * pointers to the actual strings; these cannot be laid out yet). These 
 * stay in 1:1 correspondence with the lits[] vector as that's the only 
 * place we have to obtain our full strings. 
 */ 
static 
void fillLitInfo(const vector<hwlmLiteral> &lits, vector<LitInfo> &tmpLitInfo, 
                 CONF_TYPE &andmsk) { 
    const CONF_TYPE all_ones = ~(u64a)0; 
    andmsk = all_ones; // fill in with 'and' of all literal masks 
 
    for (LiteralIndex i = 0; i < lits.size(); i++) { 
        const hwlmLiteral &lit = lits[i]; 
        LitInfo &info = tmpLitInfo[i]; 
        memset(&info, 0, sizeof(info)); 
        info.id = lit.id; 
        u8 flags = 0;
        if (lit.noruns) { 
            flags |= FDR_LIT_FLAG_NOREPEAT;
        } 
        info.flags = flags; 
        info.size = verify_u8(max(lit.msk.size(), lit.s.size()));
        info.groups = lit.groups; 
 
        // these are built up assuming a LE machine 
        CONF_TYPE msk = all_ones; 
        CONF_TYPE val = 0; 
        for (u32 j = 0; j < sizeof(CONF_TYPE); j++) { 
            u32 shiftLoc = (sizeof(CONF_TYPE) - j - 1) * 8; 
            if (j >= lit.s.size()) { 
                msk &= ~((CONF_TYPE)0xff << shiftLoc); 
            } else { 
                u8 c = lit.s[lit.s.size() - j - 1]; 
                if (lit.nocase && ourisalpha(c)) { 
                    msk &= ~((CONF_TYPE)CASE_BIT << shiftLoc); 
                    val |= (CONF_TYPE)(c & CASE_CLEAR) << shiftLoc; 
                } else { 
                    val |= (CONF_TYPE)c << shiftLoc; 
                } 
            } 
        } 
 
        info.v = val; 
        info.msk = msk; 
        if (!lit.msk.empty()) { 
            u64a l_msk = make_u64a_mask(lit.msk); 
            u64a l_cmp = make_u64a_mask(lit.cmp); 
 
            // test for consistency - if there's intersection, then v and msk 
            // values must line up 
            UNUSED u64a intersection = l_msk & info.msk; 
            assert((info.v & intersection) == (l_cmp & intersection)); 
 
            // incorporate lit.msk, lit.cmp into v and msk 
            info.msk |= l_msk; 
            info.v |= l_cmp; 
        } 
 
        andmsk &= info.msk; 
    } 
} 
 
//#define FDR_CONFIRM_DUMP 1 
 
static 
bytecode_ptr<FDRConfirm> getFDRConfirm(const vector<hwlmLiteral> &lits,
                                       bool make_small) {
    // Every literal must fit within CONF_TYPE.
    assert(all_of_in(lits, [](const hwlmLiteral &lit) {
        return lit.s.size() <= sizeof(CONF_TYPE);
    }));

    vector<LitInfo> tmpLitInfo(lits.size()); 
    CONF_TYPE andmsk; 
    fillLitInfo(lits, tmpLitInfo, andmsk); 
 
#ifdef FDR_CONFIRM_DUMP 
    printf("-------------------\n"); 
#endif 
 
    // just magic numbers and crude measures for now 
    u32 nBits; 
    if (make_small) { 
        nBits = min(10U, lg2(lits.size()) + 1); 
    } else { 
        nBits = lg2(lits.size()) + 4;
    } 
 
    CONF_TYPE mult = (CONF_TYPE)0x0b4e0ef37bc32127ULL; 
 
    // we can walk the vector and assign elements from the vectors to a 
    // map by hash value 
    map<u32, vector<LiteralIndex> > res2lits; 
    hwlm_group_t gm = 0; 
    for (LiteralIndex i = 0; i < lits.size(); i++) { 
        LitInfo & li = tmpLitInfo[i]; 
        u32 hash = CONF_HASH_CALL(li.v, andmsk, mult, nBits); 
        DEBUG_PRINTF("%016llx --> %u\n", li.v, hash); 
        res2lits[hash].push_back(i); 
        gm |= li.groups; 
    } 
 
#ifdef FDR_CONFIRM_DUMP 
    // print out the literals reversed - makes it easier to line up analyses 
    // that are end-offset based 
    for (const auto &m : res2lits) {
        const u32 &hash = m.first;
        const vector<LiteralIndex> &vlidx = m.second;
        if (vlidx.size() <= 1) {
            continue;
        }
        printf("%x -> %zu literals\n", hash, vlidx.size());
        size_t min_len = lits[vlidx.front()].s.size();

        vector<set<u8>> vsl; // contains the set of chars at each location
                             // reversed from the end

        for (const auto &litIdx : vlidx) {
            const auto &lit = lits[litIdx];
            if (lit.s.size() > vsl.size()) {
                vsl.resize(lit.s.size());
            } 
            for (size_t j = lit.s.size(); j != 0; j--) {
                vsl[lit.s.size() - j].insert(lit.s[j - 1]);
            }
            min_len = min(min_len, lit.s.size());
        }
        printf("common     ");
        for (size_t j = 0; j < min_len; j++) {
            if (vsl[j].size() == 1) {
                printf("%02x", *vsl[j].begin());
            } else {
                printf("__");
            }
        }
        printf("\n");
        for (const auto &litIdx : vlidx) {
            const auto &lit = lits[litIdx];
            printf("%8x  %c", lit.id, lit.nocase ? '!' : ' ');
            for (size_t j = lit.s.size(); j != 0; j--) {
                size_t dist_from_end = lit.s.size() - j;
                if (dist_from_end < min_len && vsl[dist_from_end].size() == 1) {
                    printf("__");
                } else { 
                    printf("%02x", lit.s[j - 1]);
                } 
            } 
            printf("\n"); 
        } 
        size_t total_compares = 0;
        for (const auto &v : vsl) {
            total_compares += v.size();
        }
        size_t total_string_size = 0;
        for (const auto &litIdx : vlidx) {
            const auto &lit = lits[litIdx];
            total_string_size += lit.s.size();
        }
        printf("Total compare load: %zu Total string size: %zu\n\n",
               total_compares, total_string_size);
    } 
#endif 
 
    const size_t bitsToLitIndexSize = (1U << nBits) * sizeof(u32); 
 
    // this size can now be a worst-case as we can always be a bit smaller 
    size_t size = ROUNDUP_N(sizeof(FDRConfirm), alignof(u32)) + 
                  ROUNDUP_N(bitsToLitIndexSize, alignof(LitInfo)) + 
                  sizeof(LitInfo) * lits.size();
    size = ROUNDUP_N(size, alignof(FDRConfirm)); 
 
    auto fdrc = make_zeroed_bytecode_ptr<FDRConfirm>(size);
    assert(fdrc); // otherwise would have thrown std::bad_alloc 
 
    fdrc->andmsk = andmsk; 
    fdrc->mult = mult; 
    fdrc->nBits = nBits;
 
    fdrc->groups = gm; 
 
    // After the FDRConfirm, we have the lit index array. 
    u8 *fdrc_base = (u8 *)fdrc.get();
    u8 *ptr = fdrc_base + sizeof(*fdrc); 
    ptr = ROUNDUP_PTR(ptr, alignof(u32)); 
    u32 *bitsToLitIndex = (u32 *)ptr; 
    ptr += bitsToLitIndexSize; 
 
    // After the lit index array, we have the LitInfo structures themselves, 
    // which vary in size (as each may have a variable-length string after it). 
    ptr = ROUNDUP_PTR(ptr, alignof(LitInfo)); 
 
    // Walk the map by hash value assigning indexes and laying out the 
    // elements (and their associated string confirm material) in memory. 
    for (const auto &m : res2lits) {
        const u32 hash = m.first;
        const vector<LiteralIndex> &vlidx = m.second;
        bitsToLitIndex[hash] = verify_u32(ptr - fdrc_base);
        for (auto i = vlidx.begin(), e = vlidx.end(); i != e; ++i) {
            LiteralIndex litIdx = *i;
 
            // Write LitInfo header. 
            LitInfo &finalLI = *(LitInfo *)ptr; 
            finalLI = tmpLitInfo[litIdx]; 
 
            ptr += sizeof(LitInfo); // String starts directly after LitInfo. 
            assert(lits[litIdx].s.size() <= sizeof(CONF_TYPE));
            if (next(i) == e) {
                finalLI.next = 0;
            } else { 
                finalLI.next = 1;
            } 
        } 
        assert((size_t)(ptr - fdrc_base) <= size); 
    } 
 
    // Return actual used size, not worst-case size. Must be rounded up to 
    // FDRConfirm alignment so that the caller can lay out a sequence of these. 
    size_t actual_size = ROUNDUP_N((size_t)(ptr - fdrc_base), 
                                   alignof(FDRConfirm)); 
    assert(actual_size <= size); 
    fdrc.shrink(actual_size);

    return fdrc;
} 
 
bytecode_ptr<u8>
setupFullConfs(const vector<hwlmLiteral> &lits,
               const EngineDescription &eng,
               const map<BucketIndex, vector<LiteralIndex>> &bucketToLits,
               bool make_small) {
    unique_ptr<TeddyEngineDescription> teddyDescr = 
        getTeddyDescription(eng.getID()); 
 
    BC2CONF bc2Conf;
    u32 totalConfirmSize = 0; 
    for (BucketIndex b = 0; b < eng.getNumBuckets(); b++) { 
        if (contains(bucketToLits, b)) {
            vector<hwlmLiteral> vl;
            for (const LiteralIndex &lit_idx : bucketToLits.at(b)) {
                vl.push_back(lits[lit_idx]);
            } 
 
            DEBUG_PRINTF("b %d sz %zu\n", b, vl.size());
            auto fc = getFDRConfirm(vl, make_small);
            totalConfirmSize += fc.size();
            bc2Conf.emplace(b, move(fc));
        } 
    } 
 
    u32 nBuckets = eng.getNumBuckets(); 
    u32 totalConfSwitchSize = ROUNDUP_CL(nBuckets * sizeof(u32));
    u32 totalSize = totalConfSwitchSize + totalConfirmSize;
 
    auto buf = make_zeroed_bytecode_ptr<u8>(totalSize, 64);
    assert(buf); // otherwise would have thrown std::bad_alloc 
 
    u32 *confBase = (u32 *)buf.get();
    u8 *ptr = buf.get() + totalConfSwitchSize;
    assert(ISALIGNED_CL(ptr));
 
    for (const auto &m : bc2Conf) {
        const BucketIndex &idx = m.first;
        const bytecode_ptr<FDRConfirm> &p = m.second;
        // confirm offset is relative to the base of this structure, now 
        u32 confirm_offset = verify_u32(ptr - buf.get());
        memcpy(ptr, p.get(), p.size());
        ptr += p.size();
        confBase[idx] = confirm_offset; 
    } 

    return buf;
} 
 
} // namespace ue2