path: root/contrib/libs/hyperscan/src/hwlm/noodle_engine.c

/*
 * 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.
 */

/** \file
 * \brief Noodle literal matcher: runtime.
 */
#include "hwlm.h"
#include "noodle_engine.h"
#include "noodle_internal.h"
#include "scratch.h" 
#include "ue2common.h"
#include "util/arch.h" 
#include "util/bitutils.h"
#include "util/compare.h"
#include "util/intrinsics.h" 
#include "util/join.h" 
#include "util/masked_move.h"
#include "util/partial_store.h" 
#include "util/simd_utils.h"

#include <ctype.h>
#include <stdbool.h>
#include <string.h>

/** \brief Noodle runtime context. */
struct cb_info {
    HWLMCallback cb; //!< callback function called on match
    u32 id; //!< ID to pass to callback on match
    struct hs_scratch *scratch; //!< scratch to pass to callback 
    size_t offsetAdj; //!< used in streaming mode
};

#if defined(HAVE_AVX512) 
#define CHUNKSIZE 64 
#define MASK_TYPE m512 
#define Z_BITS 64 
#define Z_TYPE u64a 
#elif defined(HAVE_AVX2) 
#define CHUNKSIZE 32 
#define MASK_TYPE m256 
#define Z_BITS 32 
#define Z_TYPE u32 
#else 
#define CHUNKSIZE 16 
#define MASK_TYPE m128 
#define Z_BITS 32 
#define Z_TYPE u32 
#endif 
 
 
#define RETURN_IF_TERMINATED(x)                                                \
    {                                                                          \
        if ((x) == HWLM_TERMINATED) {                                          \
            return HWLM_TERMINATED;                                            \
        }                                                                      \
    }

#define SINGLE_ZSCAN()                                                         \
    do {                                                                       \
        while (unlikely(z)) {                                                  \
            Z_TYPE pos = JOIN(findAndClearLSB_, Z_BITS)(&z);                   \ 
            size_t matchPos = d - buf + pos;                                   \
            DEBUG_PRINTF("match pos %zu\n", matchPos);                         \ 
            hwlmcb_rv_t rv = final(n, buf, len, 1, cbi, matchPos);             \ 
            RETURN_IF_TERMINATED(rv);                                          \
        }                                                                      \
    } while (0)

#define DOUBLE_ZSCAN()                                                         \
    do {                                                                       \
        while (unlikely(z)) {                                                  \
            Z_TYPE pos = JOIN(findAndClearLSB_, Z_BITS)(&z);                   \ 
            size_t matchPos = d - buf + pos - 1;                               \
            DEBUG_PRINTF("match pos %zu\n", matchPos);                         \ 
            hwlmcb_rv_t rv = final(n, buf, len, 0, cbi, matchPos);             \ 
            RETURN_IF_TERMINATED(rv);                                          \
        }                                                                      \
    } while (0)

static really_inline
u8 caseClear8(u8 x, bool noCase) {
    return (u8)(noCase ? (x & (u8)0xdf) : x);
}

// Make sure the rest of the string is there. The single character scanner
// is used only for single chars with case insensitivity used correctly,
// so it can go straight to the callback if we get this far.
static really_inline
hwlm_error_t final(const struct noodTable *n, const u8 *buf, UNUSED size_t len, 
                   char single, const struct cb_info *cbi, size_t pos) { 
    if (single) { 
        if (n->msk_len == 1) { 
            goto match; 
        }
    }
    assert(len >= n->msk_len); 
    u64a v = 
        partial_load_u64a(buf + pos + n->key_offset - n->msk_len, n->msk_len); 
    DEBUG_PRINTF("v %016llx msk %016llx cmp %016llx\n", v, n->msk, n->cmp); 
    if ((v & n->msk) != n->cmp) { 
        /* mask didn't match */ 
        return HWLM_SUCCESS; 
    } 
 
match: 
    pos -= cbi->offsetAdj; 
    DEBUG_PRINTF("match @ %zu\n", pos + n->key_offset); 
    hwlmcb_rv_t rv = cbi->cb(pos + n->key_offset - 1, cbi->id, cbi->scratch); 
    if (rv == HWLM_TERMINATE_MATCHING) {
        return HWLM_TERMINATED;
    }
    return HWLM_SUCCESS;
}

#if defined(HAVE_AVX512) 
#define CHUNKSIZE 64 
#define MASK_TYPE m512 
#include "noodle_engine_avx512.c" 
#elif defined(HAVE_AVX2) 
#define CHUNKSIZE 32
#define MASK_TYPE m256
#include "noodle_engine_avx2.c"
#else
#define CHUNKSIZE 16
#define MASK_TYPE m128
#include "noodle_engine_sse.c"
#endif

static really_inline
hwlm_error_t scanSingleMain(const struct noodTable *n, const u8 *buf, 
                            size_t len, size_t start, bool noCase, 
                            const struct cb_info *cbi) { 

    const MASK_TYPE mask1 = getMask(n->key0, noCase); 
    const MASK_TYPE caseMask = getCaseMask();

    size_t offset = start + n->msk_len - 1; 
    size_t end = len; 
    assert(offset < end); 
 
#if !defined(HAVE_AVX512) 
    hwlm_error_t rv; 
 
    if (end - offset < CHUNKSIZE) { 
        rv = scanSingleShort(n, buf, len, noCase, caseMask, mask1, cbi, offset, 
                             end); 
        return rv;
    }

    if (end - offset == CHUNKSIZE) { 
        rv = scanSingleUnaligned(n, buf, len, offset, noCase, caseMask, mask1, 
                                 cbi, offset, end); 
        return rv;
    }

    uintptr_t data = (uintptr_t)buf;
    uintptr_t s2Start = ROUNDUP_N(data + offset, CHUNKSIZE) - data; 
    uintptr_t last = data + end;
    uintptr_t s2End = ROUNDDOWN_N(last, CHUNKSIZE) - data;
    uintptr_t s3Start = end - CHUNKSIZE; 

    if (offset != s2Start) { 
        // first scan out to the fast scan starting point
        DEBUG_PRINTF("stage 1: -> %zu\n", s2Start);
        rv = scanSingleUnaligned(n, buf, len, offset, noCase, caseMask, mask1, 
                                 cbi, offset, s2Start); 
        RETURN_IF_TERMINATED(rv);
    }

    if (likely(s2Start != s2End)) {
        // scan as far as we can, bounded by the last point this key can
        // possibly match
        DEBUG_PRINTF("fast: ~ %zu -> %zu\n", s2Start, s2End);
        rv = scanSingleFast(n, buf, len, noCase, caseMask, mask1, cbi, s2Start, 
                            s2End); 
        RETURN_IF_TERMINATED(rv);
    }

    // if we are done bail out
    if (s2End == len) { 
        return HWLM_SUCCESS;
    }

    DEBUG_PRINTF("stage 3: %zu -> %zu\n", s2End, len); 
    rv = scanSingleUnaligned(n, buf, len, s3Start, noCase, caseMask, mask1, cbi, 
                             s2End, len); 

    return rv;
#else // HAVE_AVX512 
    return scanSingle512(n, buf, len, noCase, caseMask, mask1, cbi, offset, 
                         end); 
#endif 
}

static really_inline
hwlm_error_t scanDoubleMain(const struct noodTable *n, const u8 *buf, 
                            size_t len, size_t start, bool noCase, 
                            const struct cb_info *cbi) {
    // we stop scanning for the key-fragment when the rest of the key can't
    // possibly fit in the remaining buffer
    size_t end = len - n->key_offset + 2; 

    // the first place the key can match 
    size_t offset = start + n->msk_len - n->key_offset; 
 
    const MASK_TYPE caseMask = getCaseMask();
    const MASK_TYPE mask1 = getMask(n->key0, noCase); 
    const MASK_TYPE mask2 = getMask(n->key1, noCase); 

#if !defined(HAVE_AVX512) 
    hwlm_error_t rv; 
 
    if (end - offset < CHUNKSIZE) { 
        rv = scanDoubleShort(n, buf, len, noCase, caseMask, mask1, mask2, cbi, 
                             offset, end); 
        return rv;
    }
    if (end - offset == CHUNKSIZE) { 
        rv = scanDoubleUnaligned(n, buf, len, offset, noCase, caseMask, mask1, 
                                 mask2, cbi, offset, end); 
        return rv;
    }

    uintptr_t data = (uintptr_t)buf;
    uintptr_t s2Start = ROUNDUP_N(data + offset, CHUNKSIZE) - data; 
    uintptr_t s1End = s2Start + 1;
    uintptr_t last = data + end;
    uintptr_t s2End = ROUNDDOWN_N(last, CHUNKSIZE) - data;
    uintptr_t s3Start = end - CHUNKSIZE;
    uintptr_t off = offset; 

    if (s2Start != off) { 
        // first scan out to the fast scan starting point plus one char past to
        // catch the key on the overlap
        DEBUG_PRINTF("stage 1: %zu -> %zu\n", off, s2Start); 
        rv = scanDoubleUnaligned(n, buf, len, offset, noCase, caseMask, mask1, 
                                 mask2, cbi, off, s1End); 
        RETURN_IF_TERMINATED(rv);
    }
    off = s1End;

    if (s2Start >= end) {
        DEBUG_PRINTF("s2 == mL %zu\n", end);
        return HWLM_SUCCESS;
    }

    if (likely(s2Start != s2End)) {
        // scan as far as we can, bounded by the last point this key can
        // possibly match
        DEBUG_PRINTF("fast: ~ %zu -> %zu\n", s2Start, s3Start);
        rv = scanDoubleFast(n, buf, len, noCase, caseMask, mask1, mask2, cbi, 
                            s2Start, s2End); 
        RETURN_IF_TERMINATED(rv);
        off = s2End;
    }

    // if there isn't enough data left to match the key, bail out
    if (s2End == end) {
        return HWLM_SUCCESS;
    }

    DEBUG_PRINTF("stage 3: %zu -> %zu\n", s3Start, end);
    rv = scanDoubleUnaligned(n, buf, len, s3Start, noCase, caseMask, mask1, 
                             mask2, cbi, off, end); 

    return rv;
#else // AVX512 
    return scanDouble512(n, buf, len, noCase, caseMask, mask1, mask2, cbi, 
                         offset, end); 
#endif // AVX512 
}


static really_inline
hwlm_error_t scanSingleNoCase(const struct noodTable *n, const u8 *buf, 
                              size_t len, size_t start, 
                              const struct cb_info *cbi) {
    return scanSingleMain(n, buf, len, start, 1, cbi); 
}

static really_inline
hwlm_error_t scanSingleCase(const struct noodTable *n, const u8 *buf, 
                            size_t len, size_t start, 
                            const struct cb_info *cbi) {
    return scanSingleMain(n, buf, len, start, 0, cbi); 
}

// Single-character specialisation, used when keyLen = 1
static really_inline
hwlm_error_t scanSingle(const struct noodTable *n, const u8 *buf, size_t len, 
                        size_t start, bool noCase, const struct cb_info *cbi) { 
    if (!ourisalpha(n->key0)) { 
        noCase = 0; // force noCase off if we don't have an alphabetic char
    }

    // kinda ugly, but this forces constant propagation
    if (noCase) {
        return scanSingleNoCase(n, buf, len, start, cbi); 
    } else {
        return scanSingleCase(n, buf, len, start, cbi); 
    }
}


static really_inline
hwlm_error_t scanDoubleNoCase(const struct noodTable *n, const u8 *buf, 
                              size_t len, size_t start, 
                              const struct cb_info *cbi) {
    return scanDoubleMain(n, buf, len, start, 1, cbi); 
}

static really_inline
hwlm_error_t scanDoubleCase(const struct noodTable *n, const u8 *buf, 
                            size_t len, size_t start, 
                            const struct cb_info *cbi) {
    return scanDoubleMain(n, buf, len, start, 0, cbi); 
}


static really_inline
hwlm_error_t scanDouble(const struct noodTable *n, const u8 *buf, size_t len, 
                        size_t start, bool noCase, const struct cb_info *cbi) { 
    // kinda ugly, but this forces constant propagation
    if (noCase) {
        return scanDoubleNoCase(n, buf, len, start, cbi); 
    } else {
        return scanDoubleCase(n, buf, len, start, cbi); 
    }
}

// main entry point for the scan code
static really_inline
hwlm_error_t scan(const struct noodTable *n, const u8 *buf, size_t len, 
                  size_t start, char single, bool noCase, 
                  const struct cb_info *cbi) { 
    if (len - start < n->msk_len) { 
        // can't find string of length keyLen in a shorter buffer
        return HWLM_SUCCESS;
    }

    if (single) { 
        return scanSingle(n, buf, len, start, noCase, cbi); 
    } else {
        return scanDouble(n, buf, len, start, noCase, cbi); 
    }
}

/** \brief Block-mode scanner. */
hwlm_error_t noodExec(const struct noodTable *n, const u8 *buf, size_t len,
                      size_t start, HWLMCallback cb, 
                      struct hs_scratch *scratch) { 
    assert(n && buf);

    struct cb_info cbi = {cb, n->id, scratch, 0}; 
    DEBUG_PRINTF("nood scan of %zu bytes for %*s @ %p\n", len, n->msk_len, 
                 (const char *)&n->cmp, buf); 
 
    return scan(n, buf, len, start, n->single, n->nocase, &cbi); 
}

/** \brief Streaming-mode scanner. */
hwlm_error_t noodExecStreaming(const struct noodTable *n, const u8 *hbuf,
                               size_t hlen, const u8 *buf, size_t len,
                               HWLMCallback cb, struct hs_scratch *scratch) { 
    assert(n);

    if (len + hlen < n->msk_len) { 
        DEBUG_PRINTF("not enough bytes for a match\n"); 
        return HWLM_SUCCESS; 
    } 

    struct cb_info cbi = {cb, n->id, scratch, 0}; 
    DEBUG_PRINTF("nood scan of %zu bytes (%zu hlen) for %*s @ %p\n", len, hlen, 
                 n->msk_len, (const char *)&n->cmp, buf); 
 
    if (hlen && n->msk_len > 1) { 
        /* 
         * we have history, so build up a buffer from enough of the history 
         * buffer plus what we've been given to scan. Since this is relatively 
         * short, just check against msk+cmp per byte offset for matches. 
         */ 
        assert(hbuf);
        u8 ALIGN_DIRECTIVE temp_buf[HWLM_LITERAL_MAX_LEN * 2]; 
        memset(temp_buf, 0, sizeof(temp_buf)); 

        assert(n->msk_len); 
        size_t tl1 = MIN((size_t)n->msk_len - 1, hlen); 
        size_t tl2 = MIN((size_t)n->msk_len - 1, len); 

        assert(tl1 + tl2 <= sizeof(temp_buf)); 
        assert(tl1 + tl2 >= n->msk_len); 
        assert(tl1 <= sizeof(u64a)); 
        assert(tl2 <= sizeof(u64a)); 
        DEBUG_PRINTF("using %zu bytes of hist and %zu bytes of buf\n", tl1, tl2); 
 
        unaligned_store_u64a(temp_buf, 
                             partial_load_u64a(hbuf + hlen - tl1, tl1)); 
        unaligned_store_u64a(temp_buf + tl1, partial_load_u64a(buf, tl2)); 
 
        for (size_t i = 0; i <= tl1 + tl2 - n->msk_len; i++) { 
            u64a v = unaligned_load_u64a(temp_buf + i); 
            if ((v & n->msk) == n->cmp) { 
                size_t m_end = -tl1 + i + n->msk_len - 1; 
                DEBUG_PRINTF("match @ %zu (i %zu)\n", m_end, i); 
                hwlmcb_rv_t rv = cb(m_end, n->id, scratch); 
                if (rv == HWLM_TERMINATE_MATCHING) { 
                    return HWLM_TERMINATED; 
                } 
            } 
        }
    }

    assert(buf);

    cbi.offsetAdj = 0;
    return scan(n, buf, len, 0, n->single, n->nocase, &cbi); 
}