path: root/contrib/libs/hyperscan/src/fdr/teddy_runtime_common.h

/*
 * Copyright (c) 2016-2020, 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 Teddy literal matcher: common runtime procedures.
 */

#ifndef TEDDY_RUNTIME_COMMON_H_
#define TEDDY_RUNTIME_COMMON_H_

#include "fdr_confirm.h"
#include "fdr_confirm_runtime.h"
#include "ue2common.h"
#include "util/bitutils.h"
#include "util/simd_utils.h"
#include "util/uniform_ops.h"

extern const u8 ALIGN_DIRECTIVE p_mask_arr[17][32];
#if defined(HAVE_AVX2)
extern const u8 ALIGN_AVX_DIRECTIVE p_mask_arr256[33][64];
#endif

#if defined(HAVE_AVX512VBMI)
static const u8 ALIGN_DIRECTIVE p_sh_mask_arr[80] = {
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
    0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
    0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27, 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
    0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f
};
#endif

#ifdef ARCH_64_BIT
#define TEDDY_CONF_TYPE u64a
#define TEDDY_FIND_AND_CLEAR_LSB(conf) findAndClearLSB_64(conf)
#else
#define TEDDY_CONF_TYPE u32
#define TEDDY_FIND_AND_CLEAR_LSB(conf) findAndClearLSB_32(conf)
#endif

#define CHECK_HWLM_TERMINATE_MATCHING                                       \
do {                                                                        \
    if (unlikely(control == HWLM_TERMINATE_MATCHING)) {                     \
        return HWLM_TERMINATED;                                             \
    }                                                                       \
} while (0);

#define CHECK_FLOOD                                                         \
do {                                                                        \
    if (unlikely(ptr > tryFloodDetect)) {                                   \
        tryFloodDetect = floodDetect(fdr, a, &ptr, tryFloodDetect,          \
                                     &floodBackoff, &control, iterBytes);   \
        CHECK_HWLM_TERMINATE_MATCHING;                                      \
    }                                                                       \
} while (0);

/*
 * \brief Copy a block of [0,15] bytes efficiently.
 *
 * This function is a workaround intended to stop some compilers from
 * synthesizing a memcpy function call out of the copy of a small number of
 * bytes that we do in vectoredLoad128.
 */
static really_inline
void copyRuntBlock128(u8 *dst, const u8 *src, size_t len) {
    switch (len) {
    case 0:
        break;
    case 1:
        *dst = *src;
        break;
    case 2:
        unaligned_store_u16(dst, unaligned_load_u16(src));
        break;
    case 3:
        unaligned_store_u16(dst, unaligned_load_u16(src));
        dst[2] = src[2];
        break;
    case 4:
        unaligned_store_u32(dst, unaligned_load_u32(src));
        break;
    case 5:
    case 6:
    case 7:
        /* Perform copy with two overlapping 4-byte chunks. */
        unaligned_store_u32(dst + len - 4, unaligned_load_u32(src + len - 4));
        unaligned_store_u32(dst, unaligned_load_u32(src));
        break;
    case 8:
        unaligned_store_u64a(dst, unaligned_load_u64a(src));
        break;
    default:
        /* Perform copy with two overlapping 8-byte chunks. */
        assert(len < 16);
        unaligned_store_u64a(dst + len - 8, unaligned_load_u64a(src + len - 8));
        unaligned_store_u64a(dst, unaligned_load_u64a(src));
        break;
    }
}

// Note: p_mask is an output param that initialises a poison mask.
//       *p_mask = load128(p_mask_arr[n] + 16 - m) means:
//       m byte 0xff in the beginning, followed by n byte 0x00,
//       then followed by the rest bytes 0xff.
// ptr >= lo:
//     no history.
//     for end/short zone, ptr==lo and start_offset==0
//     for start zone, see below
//          lo         ptr                      hi           hi
//          |----------|-------|----------------|............|
//          -start     0       -start+offset    MIN(avail,16)
// p_mask              ffff..ff0000...........00ffff..........
// ptr < lo:
//     only start zone.
//             history
//          ptr        lo                       hi           hi
//          |----------|-------|----------------|............|
//          0          start   start+offset     end(<=16)
// p_mask   ffff.....ffffff..ff0000...........00ffff..........
static really_inline
m128 vectoredLoad128(m128 *p_mask, const u8 *ptr, const size_t start_offset,
                     const u8 *lo, const u8 *hi,
                     const u8 *buf_history, size_t len_history,
                     const u32 nMasks) {
    union {
        u8 val8[16];
        m128 val128;
    } u;
    u.val128 = zeroes128();

    uintptr_t copy_start;
    uintptr_t copy_len;

    if (ptr >= lo) { // short/end/start zone
        uintptr_t start = (uintptr_t)(ptr - lo);
        uintptr_t avail = (uintptr_t)(hi - ptr);
        if (avail >= 16) {
            assert(start_offset - start <= 16);
            *p_mask = loadu128(p_mask_arr[16 - start_offset + start]
                               + 16 - start_offset + start);
            return loadu128(ptr);
        }
        assert(start_offset - start <= avail);
        *p_mask = loadu128(p_mask_arr[avail - start_offset + start]
                           + 16 - start_offset + start);
        copy_start = 0;
        copy_len = avail;
    } else { // start zone
        uintptr_t need = MIN((uintptr_t)(lo - ptr),
                             MIN(len_history, nMasks - 1));
        uintptr_t start = (uintptr_t)(lo - ptr);
        uintptr_t i;
        for (i = start - need; i < start; i++) {
            u.val8[i] = buf_history[len_history - (start - i)];
        }
        uintptr_t end = MIN(16, (uintptr_t)(hi - ptr));
        assert(start + start_offset <= end);
        *p_mask = loadu128(p_mask_arr[end - start - start_offset]
                           + 16 - start - start_offset);
        copy_start = start;
        copy_len = end - start;
    }

    // Runt block from the buffer.
    copyRuntBlock128(&u.val8[copy_start], &ptr[copy_start], copy_len);

    return u.val128;
}

#if defined(HAVE_AVX2)
/*
 * \brief Copy a block of [0,31] bytes efficiently.
 *
 * This function is a workaround intended to stop some compilers from
 * synthesizing a memcpy function call out of the copy of a small number of
 * bytes that we do in vectoredLoad256.
 */
static really_inline
void copyRuntBlock256(u8 *dst, const u8 *src, size_t len) {
    switch (len) {
    case 0:
        break;
    case 1:
        *dst = *src;
        break;
    case 2:
        unaligned_store_u16(dst, unaligned_load_u16(src));
        break;
    case 3:
        unaligned_store_u16(dst, unaligned_load_u16(src));
        dst[2] = src[2];
        break;
    case 4:
        unaligned_store_u32(dst, unaligned_load_u32(src));
        break;
    case 5:
    case 6:
    case 7:
        /* Perform copy with two overlapping 4-byte chunks. */
        unaligned_store_u32(dst + len - 4, unaligned_load_u32(src + len - 4));
        unaligned_store_u32(dst, unaligned_load_u32(src));
        break;
    case 8:
        unaligned_store_u64a(dst, unaligned_load_u64a(src));
        break;
    case 9:
    case 10:
    case 11:
    case 12:
    case 13:
    case 14:
    case 15:
        /* Perform copy with two overlapping 8-byte chunks. */
        unaligned_store_u64a(dst + len - 8, unaligned_load_u64a(src + len - 8));
        unaligned_store_u64a(dst, unaligned_load_u64a(src));
        break;
    case 16:
        storeu128(dst, loadu128(src));
        break;
    default:
        /* Perform copy with two overlapping 16-byte chunks. */
        assert(len < 32);
        storeu128(dst + len - 16, loadu128(src + len - 16));
        storeu128(dst, loadu128(src));
        break;
    }
}

// Note: p_mask is an output param that initialises a poison mask.
//       *p_mask = load256(p_mask_arr256[n] + 32 - m) means:
//       m byte 0xff in the beginning, followed by n byte 0x00,
//       then followed by the rest bytes 0xff.
// ptr >= lo:
//     no history.
//     for end/short zone, ptr==lo and start_offset==0
//     for start zone, see below
//          lo         ptr                      hi           hi
//          |----------|-------|----------------|............|
//          -start     0       -start+offset    MIN(avail,32)
// p_mask              ffff..ff0000...........00ffff..........
// ptr < lo:
//     only start zone.
//             history
//          ptr        lo                       hi           hi
//          |----------|-------|----------------|............|
//          0          start   start+offset     end(<=32)
// p_mask   ffff.....ffffff..ff0000...........00ffff..........
static really_inline
m256 vectoredLoad256(m256 *p_mask, const u8 *ptr, const size_t start_offset,
                     const u8 *lo, const u8 *hi,
                     const u8 *buf_history, size_t len_history,
                     const u32 nMasks) {
    union {
        u8 val8[32];
        m256 val256;
    } u;
    u.val256 = zeroes256();

    uintptr_t copy_start;
    uintptr_t copy_len;

    if (ptr >= lo) { // short/end/start zone
        uintptr_t start = (uintptr_t)(ptr - lo);
        uintptr_t avail = (uintptr_t)(hi - ptr);
        if (avail >= 32) {
            assert(start_offset - start <= 32);
            *p_mask = loadu256(p_mask_arr256[32 - start_offset + start]
                               + 32 - start_offset + start);
            return loadu256(ptr);
        }
        assert(start_offset - start <= avail);
        *p_mask = loadu256(p_mask_arr256[avail - start_offset + start]
                           + 32 - start_offset + start);
        copy_start = 0;
        copy_len = avail;
    } else { //start zone
        uintptr_t need = MIN((uintptr_t)(lo - ptr),
                             MIN(len_history, nMasks - 1));
        uintptr_t start = (uintptr_t)(lo - ptr);
        uintptr_t i;
        for (i = start - need; i < start; i++) {
            u.val8[i] = buf_history[len_history - (start - i)];
        }
        uintptr_t end = MIN(32, (uintptr_t)(hi - ptr));
        assert(start + start_offset <= end);
        *p_mask = loadu256(p_mask_arr256[end - start - start_offset]
                           + 32 - start - start_offset);
        copy_start = start;
        copy_len = end - start;
    }

    // Runt block from the buffer.
    copyRuntBlock256(&u.val8[copy_start], &ptr[copy_start], copy_len);

    return u.val256;
}
#endif // HAVE_AVX2

#if defined(HAVE_AVX512)
// Note: p_mask is an output param that initialises a poison mask.
//       u64a k = ones_u64a << n' >> m'; // m' < n'
//       *p_mask = set_mask_m512(~k);
//       means p_mask is consist of:
//       (n' - m') poison bytes "0xff" at the beginning,
//       followed by (64 - n') valid bytes "0x00",
//       then followed by the rest m' poison bytes "0xff".
// ptr >= lo:
//     no history.
//     for end/short zone, ptr==lo and start_offset==0
//     for start zone, see below
//          lo         ptr                      hi           hi
//          |----------|-------|----------------|............|
//          -start     0       -start+offset    MIN(avail,64)
// p_mask              ffff..ff0000...........00ffff..........
// ptr < lo:
//     only start zone.
//             history
//          ptr        lo                       hi           hi
//          |----------|-------|----------------|............|
//          0          start   start+offset     end(<=64)
// p_mask   ffff.....ffffff..ff0000...........00ffff..........
static really_inline
m512 vectoredLoad512(m512 *p_mask, const u8 *ptr, const size_t start_offset,
                     const u8 *lo, const u8 *hi, const u8 *hbuf, size_t hlen,
                     const u32 nMasks) {
    m512 val;

    uintptr_t copy_start;
    uintptr_t copy_len;

    if (ptr >= lo) { // short/end/start zone
        uintptr_t start = (uintptr_t)(ptr - lo);
        uintptr_t avail = (uintptr_t)(hi - ptr);
        if (avail >= 64) {
            assert(start_offset - start <= 64);
            u64a k = ones_u64a << (start_offset - start);
            *p_mask = set_mask_m512(~k);
            return loadu512(ptr);
        }
        assert(start_offset - start <= avail);
        u64a k = ones_u64a << (64 - avail + start_offset - start)
                           >> (64 - avail);
        *p_mask = set_mask_m512(~k);
        copy_start = 0;
        copy_len = avail;
    } else { //start zone
        uintptr_t need = MIN((uintptr_t)(lo - ptr),
                             MIN(hlen, nMasks - 1));
        uintptr_t start = (uintptr_t)(lo - ptr);
        u64a j = 0x7fffffffffffffffULL >> (63 - need) << (start - need);
        val = loadu_maskz_m512(j, &hbuf[hlen - start]);
        uintptr_t end = MIN(64, (uintptr_t)(hi - ptr));
        assert(start + start_offset <= end);
        u64a k = ones_u64a << (64 - end + start + start_offset) >> (64 - end);
        *p_mask = set_mask_m512(~k);
        copy_start = start;
        copy_len = end - start;
    }

    assert(copy_len < 64);
    assert(copy_len > 0);
    u64a j = ones_u64a >> (64 - copy_len) << copy_start;
    val = loadu_mask_m512(val, j, ptr);

    return val;
}
#endif // HAVE_AVX512

static really_inline
u64a getConfVal(const struct FDR_Runtime_Args *a, const u8 *ptr, u32 byte,
                UNUSED CautionReason reason) {
    u64a confVal = 0;
    const u8 *buf = a->buf;
    size_t len = a->len;
    const u8 *confirm_loc = ptr + byte - 7;
#if defined(HAVE_AVX512VBMI)
    if (likely(confirm_loc >= buf)) {
#else
    if (likely(reason == NOT_CAUTIOUS || confirm_loc >= buf)) {
#endif
        confVal = lv_u64a(confirm_loc, buf, buf + len);
    } else { // r == VECTORING, confirm_loc < buf
        u64a histBytes = a->histBytes;
        confVal = lv_u64a_ce(confirm_loc, buf, buf + len);
        // stitch together confVal and history
        u32 overhang = buf - confirm_loc;
        histBytes >>= 64 - (overhang * 8);
        confVal |= histBytes;
    }
    return confVal;
}

static really_inline
void do_confWithBit_teddy(TEDDY_CONF_TYPE *conf, u8 bucket, u8 offset,
                          const u32 *confBase, CautionReason reason,
                          const struct FDR_Runtime_Args *a, const u8 *ptr,
                          hwlmcb_rv_t *control, u32 *last_match) {
    do  {
        u32 bit = TEDDY_FIND_AND_CLEAR_LSB(conf);
        u32 byte = bit / bucket + offset;
        u32 idx  = bit % bucket;
        u32 cf = confBase[idx];
        if (!cf) {
            continue;
        }
        const struct FDRConfirm *fdrc = (const struct FDRConfirm *)
                                        ((const u8 *)confBase + cf);
        if (!(fdrc->groups & *control)) {
            continue;
        }
        u64a tmp = 0;
        u64a confVal = getConfVal(a, ptr, byte, reason);
        confWithBit(fdrc, a, ptr - a->buf + byte, control,
                    last_match, confVal, &tmp, 0);
    } while (unlikely(*conf));
}

static really_inline
const m128 *getMaskBase(const struct Teddy *teddy) {
    return (const m128 *)((const u8 *)teddy + ROUNDUP_CL(sizeof(struct Teddy)));
}

static really_inline
const u64a *getReinforcedMaskBase(const struct Teddy *teddy, u8 numMask) {
    return (const u64a *)((const u8 *)getMaskBase(teddy)
                          + ROUNDUP_CL(2 * numMask * sizeof(m128)));
}

static really_inline
const u32 *getConfBase(const struct Teddy *teddy) {
    return (const u32 *)((const u8 *)teddy + teddy->confOffset);
}

#endif /* TEDDY_RUNTIME_COMMON_H_ */