path: root/contrib/libs/hyperscan/src/fdr/fdr.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.
 */

#include "fdr.h"
#include "fdr_confirm.h" 
#include "fdr_confirm_runtime.h" 
#include "fdr_internal.h"
#include "fdr_loadval.h" 
#include "flood_runtime.h" 
#include "scratch.h" 
#include "teddy.h" 
#include "teddy_internal.h"
#include "util/arch.h" 
#include "util/simd_utils.h" 
#include "util/uniform_ops.h" 

/** \brief number of bytes processed in each iteration */ 
#define ITER_BYTES          16 

/** \brief total zone buffer size */ 
#define ZONE_TOTAL_SIZE     64 

/** \brief maximum number of allowed zones */ 
#define ZONE_MAX            3 
 
/** \brief zone information. 
 * 
 * Zone represents a region of data to scan in FDR. 
 * 
 * The incoming buffer is to split in multiple zones to ensure two properties: 
 * 1: that we can read 8? bytes behind to generate a hash safely 
 * 2: that we can read the 3 byte after the current byte (domain > 8) 
 */ 
struct zone { 
    /** \brief copied buffer, used only when it is a boundary zone. */ 
    u8 ALIGN_CL_DIRECTIVE buf[ZONE_TOTAL_SIZE]; 
 
    /** \brief shift amount for fdr state to avoid unwanted match. */ 
    u8 shift; 
 
    /** \brief if boundary zone, start points into the zone buffer after the 
     * pre-padding. Otherwise, points to the main buffer, appropriately. */ 
    const u8 *start; 
 
    /** \brief if boundary zone, end points to the end of zone. Otherwise, 
     * pointer to the main buffer, appropriately. */ 
    const u8 *end; 
 
    /** \brief the amount to adjust to go from a pointer in the zones region 
     * (between start and end) to a pointer in the original data buffer. */ 
    ptrdiff_t zone_pointer_adjust; 
 
    /** \brief firstFloodDetect from FDR_Runtime_Args for non-boundary zones, 
     * otherwise end of the zone buf. floodPtr always points inside the same 
     * buffer as the start pointe. */ 
    const u8 *floodPtr; 
}; 
 
static 
const ALIGN_CL_DIRECTIVE u8 zone_or_mask[ITER_BYTES+1][ITER_BYTES] = { 
    { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 
      0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 
      0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 
      0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 
      0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 
      0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 
      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00, 0x00 }, 
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 
      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00 }, 
    { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } 
}; 
 
/* compilers don't reliably synthesize the 32-bit ANDN instruction here, 
 * so we force its generation. 
 */ 
static really_inline 
u64a andn(const u32 a, const u8 *b) { 
    u64a r; 
#if defined(HAVE_BMI) && !defined(NO_ASM) 
    __asm__ ("andn\t%2,%1,%k0" : "=r"(r) : "r"(a), "m"(*(const u32 *)b)); 
#else 
    r = unaligned_load_u32(b) & ~a; 
#endif 
    return r; 
} 
 
/* generates an initial state mask based on the last byte-ish of history rather 
 * than being all accepting. If there is no history to consider, the state is 
 * generated based on the minimum length of each bucket in order to prevent 
 * confirms. 
 */ 
static really_inline 
m128 getInitState(const struct FDR *fdr, u8 len_history, const u64a *ft, 
                  const struct zone *z) { 
    m128 s; 
    if (len_history) { 
        /* +1: the zones ensure that we can read the byte at z->end */ 
        u32 tmp = lv_u16(z->start + z->shift - 1, z->buf, z->end + 1); 
        tmp &= fdr->domainMask; 
        s = load_m128_from_u64a(ft + tmp); 
        s = rshiftbyte_m128(s, 1); 
    } else { 
        s = fdr->start; 
    } 
    return s; 
} 
 
static really_inline 
void get_conf_stride_1(const u8 *itPtr, UNUSED const u8 *start_ptr, 
                       UNUSED const u8 *end_ptr, u32 domain_mask_flipped, 
                       const u64a *ft, u64a *conf0, u64a *conf8, m128 *s) { 
    /* +1: the zones ensure that we can read the byte at z->end */ 
    assert(itPtr >= start_ptr && itPtr + ITER_BYTES <= end_ptr); 
    u64a reach0 = andn(domain_mask_flipped, itPtr); 
    u64a reach1 = andn(domain_mask_flipped, itPtr + 1); 
    u64a reach2 = andn(domain_mask_flipped, itPtr + 2); 
    u64a reach3 = andn(domain_mask_flipped, itPtr + 3); 
 
    m128 st0 = load_m128_from_u64a(ft + reach0); 
    m128 st1 = load_m128_from_u64a(ft + reach1); 
    m128 st2 = load_m128_from_u64a(ft + reach2); 
    m128 st3 = load_m128_from_u64a(ft + reach3); 
 
    u64a reach4 = andn(domain_mask_flipped, itPtr + 4); 
    u64a reach5 = andn(domain_mask_flipped, itPtr + 5); 
    u64a reach6 = andn(domain_mask_flipped, itPtr + 6); 
    u64a reach7 = andn(domain_mask_flipped, itPtr + 7); 
 
    m128 st4 = load_m128_from_u64a(ft + reach4); 
    m128 st5 = load_m128_from_u64a(ft + reach5); 
    m128 st6 = load_m128_from_u64a(ft + reach6); 
    m128 st7 = load_m128_from_u64a(ft + reach7); 
 
    st1 = lshiftbyte_m128(st1, 1); 
    st2 = lshiftbyte_m128(st2, 2); 
    st3 = lshiftbyte_m128(st3, 3); 
    st4 = lshiftbyte_m128(st4, 4); 
    st5 = lshiftbyte_m128(st5, 5); 
    st6 = lshiftbyte_m128(st6, 6); 
    st7 = lshiftbyte_m128(st7, 7); 
 
    st0 = or128(st0, st1); 
    st2 = or128(st2, st3); 
    st4 = or128(st4, st5); 
    st6 = or128(st6, st7); 
    st0 = or128(st0, st2); 
    st4 = or128(st4, st6); 
    st0 = or128(st0, st4); 
    *s = or128(*s, st0); 
 
    *conf0 = movq(*s); 
    *s = rshiftbyte_m128(*s, 8); 
    *conf0 ^= ~0ULL; 
 
    u64a reach8 = andn(domain_mask_flipped, itPtr + 8); 
    u64a reach9 = andn(domain_mask_flipped, itPtr + 9); 
    u64a reach10 = andn(domain_mask_flipped, itPtr + 10); 
    u64a reach11 = andn(domain_mask_flipped, itPtr + 11); 
 
    m128 st8 = load_m128_from_u64a(ft + reach8); 
    m128 st9 = load_m128_from_u64a(ft + reach9); 
    m128 st10 = load_m128_from_u64a(ft + reach10); 
    m128 st11 = load_m128_from_u64a(ft + reach11); 
 
    u64a reach12 = andn(domain_mask_flipped, itPtr + 12); 
    u64a reach13 = andn(domain_mask_flipped, itPtr + 13); 
    u64a reach14 = andn(domain_mask_flipped, itPtr + 14); 
    u64a reach15 = andn(domain_mask_flipped, itPtr + 15); 
 
    m128 st12 = load_m128_from_u64a(ft + reach12); 
    m128 st13 = load_m128_from_u64a(ft + reach13); 
    m128 st14 = load_m128_from_u64a(ft + reach14); 
    m128 st15 = load_m128_from_u64a(ft + reach15); 
 
    st9 = lshiftbyte_m128(st9, 1); 
    st10 = lshiftbyte_m128(st10, 2); 
    st11 = lshiftbyte_m128(st11, 3); 
    st12 = lshiftbyte_m128(st12, 4); 
    st13 = lshiftbyte_m128(st13, 5); 
    st14 = lshiftbyte_m128(st14, 6); 
    st15 = lshiftbyte_m128(st15, 7); 
 
    st8 = or128(st8, st9); 
    st10 = or128(st10, st11); 
    st12 = or128(st12, st13); 
    st14 = or128(st14, st15); 
    st8 = or128(st8, st10); 
    st12 = or128(st12, st14); 
    st8 = or128(st8, st12); 
    *s = or128(*s, st8); 
 
    *conf8 = movq(*s); 
    *s = rshiftbyte_m128(*s, 8); 
    *conf8 ^= ~0ULL; 
} 
 
static really_inline 
void get_conf_stride_2(const u8 *itPtr, UNUSED const u8 *start_ptr, 
                       UNUSED const u8 *end_ptr, u32 domain_mask_flipped, 
                       const u64a *ft, u64a *conf0, u64a *conf8, m128 *s) { 
    assert(itPtr >= start_ptr && itPtr + ITER_BYTES <= end_ptr); 
    u64a reach0 = andn(domain_mask_flipped, itPtr); 
    u64a reach2 = andn(domain_mask_flipped, itPtr + 2); 
    u64a reach4 = andn(domain_mask_flipped, itPtr + 4); 
    u64a reach6 = andn(domain_mask_flipped, itPtr + 6); 
 
    m128 st0 = load_m128_from_u64a(ft + reach0); 
    m128 st2 = load_m128_from_u64a(ft + reach2); 
    m128 st4 = load_m128_from_u64a(ft + reach4); 
    m128 st6 = load_m128_from_u64a(ft + reach6); 
 
    u64a reach8 = andn(domain_mask_flipped, itPtr + 8); 
    u64a reach10 = andn(domain_mask_flipped, itPtr + 10); 
    u64a reach12 = andn(domain_mask_flipped, itPtr + 12); 
    u64a reach14 = andn(domain_mask_flipped, itPtr + 14); 
 
    m128 st8 = load_m128_from_u64a(ft + reach8); 
    m128 st10 = load_m128_from_u64a(ft + reach10); 
    m128 st12 = load_m128_from_u64a(ft + reach12); 
    m128 st14 = load_m128_from_u64a(ft + reach14); 
 
    st2  = lshiftbyte_m128(st2, 2); 
    st4  = lshiftbyte_m128(st4, 4); 
    st6  = lshiftbyte_m128(st6, 6); 
 
    *s = or128(*s, st0); 
    *s = or128(*s, st2); 
    *s = or128(*s, st4); 
    *s = or128(*s, st6); 
 
    *conf0 = movq(*s); 
    *s = rshiftbyte_m128(*s, 8); 
    *conf0 ^= ~0ULL; 
 
    st10 = lshiftbyte_m128(st10, 2); 
    st12 = lshiftbyte_m128(st12, 4); 
    st14 = lshiftbyte_m128(st14, 6); 
 
    *s = or128(*s, st8); 
    *s = or128(*s, st10); 
    *s = or128(*s, st12); 
    *s = or128(*s, st14); 
 
    *conf8 = movq(*s); 
    *s = rshiftbyte_m128(*s, 8); 
    *conf8 ^= ~0ULL; 
} 
 
static really_inline 
void get_conf_stride_4(const u8 *itPtr, UNUSED const u8 *start_ptr, 
                       UNUSED const u8 *end_ptr, u32 domain_mask_flipped, 
                       const u64a *ft, u64a *conf0, u64a *conf8, m128 *s) { 
    assert(itPtr >= start_ptr && itPtr + ITER_BYTES <= end_ptr); 
    u64a reach0 = andn(domain_mask_flipped, itPtr); 
    u64a reach4 = andn(domain_mask_flipped, itPtr + 4); 
    u64a reach8 = andn(domain_mask_flipped, itPtr + 8); 
    u64a reach12 = andn(domain_mask_flipped, itPtr + 12); 
 
    m128 st0 = load_m128_from_u64a(ft + reach0); 
    m128 st4 = load_m128_from_u64a(ft + reach4); 
    m128 st8 = load_m128_from_u64a(ft + reach8); 
    m128 st12 = load_m128_from_u64a(ft + reach12); 
 
    st4 = lshiftbyte_m128(st4, 4); 
    st12 = lshiftbyte_m128(st12, 4); 
 
    *s = or128(*s, st0); 
    *s = or128(*s, st4); 
    *conf0 = movq(*s); 
    *s = rshiftbyte_m128(*s, 8); 
    *conf0 ^= ~0ULL; 
 
    *s = or128(*s, st8); 
    *s = or128(*s, st12); 
    *conf8 = movq(*s); 
    *s = rshiftbyte_m128(*s, 8); 
    *conf8 ^= ~0ULL; 
} 
 
static really_inline 
void do_confirm_fdr(u64a *conf, u8 offset, hwlmcb_rv_t *control, 
                    const u32 *confBase, const struct FDR_Runtime_Args *a, 
                    const u8 *ptr, u32 *last_match_id, struct zone *z) { 
    const u8 bucket = 8; 
 
    if (likely(!*conf)) { 
        return; 
    } 
 
    /* ptr is currently referring to a location in the zone's buffer, we also 
     * need a pointer in the original, main buffer for the final string compare. 
     */ 
    const u8 *ptr_main = (const u8 *)((uintptr_t)ptr + z->zone_pointer_adjust); 
 
    const u8 *confLoc = ptr; 
 
    do  { 
        u32 bit = findAndClearLSB_64(conf); 
        u32 byte = bit / bucket + offset; 
        u32 bitRem = bit % bucket; 
        u32 idx = bitRem; 
        u32 cf = confBase[idx]; 
        if (!cf) { 
            continue; 
        } 
        const struct FDRConfirm *fdrc = (const struct FDRConfirm *) 
                                        ((const u8 *)confBase + cf); 
        if (!(fdrc->groups & *control)) { 
            continue; 
        } 
        u64a confVal = unaligned_load_u64a(confLoc + byte - sizeof(u64a) + 1); 
        confWithBit(fdrc, a, ptr_main - a->buf + byte, control, 
                    last_match_id, confVal, conf, bit); 
    } while (unlikely(!!*conf)); 
} 
 
static really_inline 
void dumpZoneInfo(UNUSED struct zone *z, UNUSED size_t zone_id) { 
#ifdef DEBUG 
    DEBUG_PRINTF("zone: zone=%zu, bufPtr=%p\n", zone_id, z->buf); 
    DEBUG_PRINTF("zone: startPtr=%p, endPtr=%p, shift=%u\n", 
                 z->start, z->end, z->shift); 
    DEBUG_PRINTF("zone: zone_pointer_adjust=%zd, floodPtr=%p\n", 
                 z->zone_pointer_adjust, z->floodPtr); 
    DEBUG_PRINTF("zone buf:"); 
    for (size_t i = 0; i < ZONE_TOTAL_SIZE; i++) { 
        if (i % 8 == 0) { 
            printf("_"); 
        } 
        if (z->buf[i]) { 
            printf("%02x", z->buf[i]); 
        } else { 
            printf(".."); 
        } 
    } 
    printf("\n"); 
#endif 
}; 
 
/** 
 * \brief Updates attributes for non-boundary region zone. 
 */ 
static really_inline 
void createMainZone(const u8 *flood, const u8 *begin, const u8 *end, 
                    struct zone *z) { 
    z->zone_pointer_adjust = 0; /* zone buffer is the main buffer */ 
    z->start = begin; 
    z->end = end; 
    z->floodPtr = flood; 
    z->shift = 0; 
} 
 
/** 
 * \brief Create zone for short cases (<= ITER_BYTES). 
 * 
 * For this case we need to copy everything into the zone's internal buffer. 
 * 
 * We need to ensure that we run over real data if it exists (in history or 
 * before zone begin). We also need to ensure 8 bytes before any data being 
 * matched can be read (to perform a conf hash). 
 * 
 * We also need to ensure that the data at z->end can be read. 
 * 
 * Hence, the zone consists of: 
 *     16 bytes of history, 
 *     1 - 24 bytes of data form the buffer (ending at end), 
 *     1 byte of final padding 
 */ 
static really_inline 
void createShortZone(const u8 *buf, const u8 *hend, const u8 *begin, 
                     const u8 *end, struct zone *z) { 
    /* the floodPtr for BOUNDARY zones are maximum of end of zone buf to avoid 
     * the checks in boundary zone. */ 
    z->floodPtr = z->buf + ZONE_TOTAL_SIZE; 
 
    ptrdiff_t z_len = end - begin; 
    assert(z_len > 0); 
    assert(z_len <= ITER_BYTES); 
 
    z->shift = ITER_BYTES - z_len; /* ignore bytes outside region specified */ 
 
    static const size_t ZONE_SHORT_DATA_OFFSET = 16; /* after history */ 
 
    /* we are guaranteed to always have 16 initialised bytes at the end of 
     * the history buffer (they may be garbage coming from the stream state 
     * preceding hbuf, but bytes that don't correspond to actual history 
     * shouldn't affect computations). */ 
    *(m128 *)z->buf = loadu128(hend - sizeof(m128)); 
 
    /* The amount of data we have to copy from main buffer. */ 
    size_t copy_len = MIN((size_t)(end - buf), 
                          ITER_BYTES + sizeof(CONF_TYPE)); 
 
    u8 *zone_data = z->buf + ZONE_SHORT_DATA_OFFSET; 
    switch (copy_len) { 
    case 1: 
        *zone_data = *(end - 1); 
        break; 
    case 2: 
        *(u16 *)zone_data = unaligned_load_u16(end - 2); 
        break; 
    case 3: 
        *(u16 *)zone_data = unaligned_load_u16(end - 3); 
        *(zone_data + 2) = *(end - 1); 
        break; 
    case 4: 
        *(u32 *)zone_data = unaligned_load_u32(end - 4); 
        break; 
    case 5: 
    case 6: 
    case 7: 
        /* perform copy with 2 overlapping 4-byte chunks from buf. */ 
        *(u32 *)zone_data = unaligned_load_u32(end - copy_len); 
        unaligned_store_u32(zone_data + copy_len - sizeof(u32), 
                            unaligned_load_u32(end - sizeof(u32))); 
        break; 
    case 8: 
        *(u64a *)zone_data = unaligned_load_u64a(end - 8); 
        break; 
    case 9: 
    case 10: 
    case 11: 
    case 12: 
    case 13: 
    case 14: 
    case 15: 
        /* perform copy with 2 overlapping 8-byte chunks from buf. */ 
        *(u64a *)zone_data = unaligned_load_u64a(end - copy_len); 
        unaligned_store_u64a(zone_data + copy_len - sizeof(u64a), 
                             unaligned_load_u64a(end - sizeof(u64a))); 
        break; 
    case 16: 
        /* copy 16-bytes from buf. */ 
        *(m128 *)zone_data = loadu128(end - 16); 
        break; 
    default: 
        assert(copy_len <= sizeof(m128) + sizeof(u64a)); 
 
        /* perform copy with (potentially overlapping) 8-byte and 16-byte chunks. 
         */ 
        *(u64a *)zone_data = unaligned_load_u64a(end - copy_len); 
        storeu128(zone_data + copy_len - sizeof(m128), 
                  loadu128(end - sizeof(m128))); 
        break; 
    } 
 
    /* set the start and end location of the zone buf 
     * to be scanned */ 
    u8 *z_end = z->buf + ZONE_SHORT_DATA_OFFSET + copy_len; 
    assert(ZONE_SHORT_DATA_OFFSET + copy_len >= ITER_BYTES); 
 
    /* copy the post-padding byte; this is required for domain > 8 due to 
     * overhang */ 
    assert(ZONE_SHORT_DATA_OFFSET + copy_len + 3 < 64); 
    *z_end = 0; 
 
    z->end = z_end; 
    z->start = z_end - ITER_BYTES; 
    z->zone_pointer_adjust = (ptrdiff_t)((uintptr_t)end - (uintptr_t)z_end); 
    assert(z->start + z->shift == z_end - z_len); 
} 
 
/** 
 * \brief Create a zone for the start region. 
 * 
 * This function requires that there is > ITER_BYTES of data in the buffer to 
 * scan. The start zone itself is always responsible for scanning exactly 
 * ITER_BYTES of data - there are no warmup/junk bytes scanned. 
 * 
 * This zone ensures that the byte at z->end can be read and corresponds to 
 * the next byte of data. 
 * 
 * 8 bytes of history data are provided before z->start to allow proper hash 
 * generation in streaming mode. If buf != begin, upto 8 bytes of data 
 * prior to begin is also provided. 
 * 
 * Although we are not interested in bare literals which start before begin 
 * if buf != begin, lookarounds associated with the literal may require 
 * the data prior to begin for hash purposes. 
 */ 
static really_inline 
void createStartZone(const u8 *buf, const u8 *hend, const u8 *begin, 
                     struct zone *z) { 
    assert(ITER_BYTES == sizeof(m128)); 
    assert(sizeof(CONF_TYPE) == 8); 
    static const size_t ZONE_START_BEGIN = sizeof(CONF_TYPE); 
 
    const u8 *end = begin + ITER_BYTES; 
 
    /* set floodPtr to the end of zone buf to avoid checks in start zone */ 
    z->floodPtr = z->buf + ZONE_TOTAL_SIZE; 
 
    z->shift = 0; /* we are processing ITER_BYTES of real data */ 
 
    /* we are guaranteed to always have 16 initialised bytes at the end of the 
     * history buffer (they may be garbage coming from the stream state 
     * preceding hbuf, but bytes that don't correspond to actual history 
     * shouldn't affect computations). However, for start zones, history is only 
     * required for conf hash purposes so we only need 8 bytes */ 
    unaligned_store_u64a(z->buf, unaligned_load_u64a(hend - sizeof(u64a))); 
 
    /* The amount of data we have to copy from main buffer. */ 
    size_t copy_len = MIN((size_t)(end - buf), 
                          ITER_BYTES + sizeof(CONF_TYPE)); 
    assert(copy_len >= 16); 
 
    /* copy the post-padding byte; this is required for domain > 8 due to 
     * overhang. The start requires that there is data after the zone so it 
     * it safe to dereference end */ 
    z->buf[ZONE_START_BEGIN + copy_len] = *end; 
 
    /* set the start and end location of the zone buf to be scanned */ 
    u8 *z_end = z->buf + ZONE_START_BEGIN + copy_len; 
    z->end = z_end; 
    z->start = z_end - ITER_BYTES; 
 
    /* copy the first 8 bytes of the valid region */ 
    unaligned_store_u64a(z->buf + ZONE_START_BEGIN, 
                         unaligned_load_u64a(end - copy_len)); 
 
    /* copy the last 16 bytes, may overlap with the previous 8 byte write */ 
    storeu128(z_end - sizeof(m128), loadu128(end - sizeof(m128))); 
 
    z->zone_pointer_adjust = (ptrdiff_t)((uintptr_t)end - (uintptr_t)z_end); 
 
    assert(ZONE_START_BEGIN + copy_len + 3 < 64); 
} 
 
/** 
 * \brief Create a zone for the end region. 
 * 
 * This function requires that there is > ITER_BYTES of data in the buffer to 
 * scan. The end zone is responsible for a scanning the <= ITER_BYTES rump of 
 * data and optional ITER_BYTES. The main zone cannot handle the last 3 bytes 
 * of the buffer. The end zone is required to handle an optional full 
 * ITER_BYTES from main zone when there are less than 3 bytes to scan. The 
 * main zone size is reduced by ITER_BYTES in this case. 
 * 
 * This zone ensures that the byte at z->end can be read by filling it with a 
 * padding character. 
 * 
 * Upto 8 bytes of data prior to begin is also provided for the purposes of 
 * generating hashes. History is not copied, as all locations which require 
 * history for generating a hash are the responsiblity of the start zone. 
 */ 
static really_inline 
void createEndZone(const u8 *buf, const u8 *begin, const u8 *end, 
                   struct zone *z) { 
    /* the floodPtr for BOUNDARY zones are maximum of end of zone buf to avoid 
     * the checks in boundary zone. */ 
    z->floodPtr = z->buf + ZONE_TOTAL_SIZE; 
 
    ptrdiff_t z_len = end - begin; 
    assert(z_len > 0); 
    size_t iter_bytes_second = 0; 
    size_t z_len_first = z_len; 
    if (z_len > ITER_BYTES) { 
        z_len_first = z_len - ITER_BYTES; 
        iter_bytes_second = ITER_BYTES; 
    } 
    z->shift = ITER_BYTES - z_len_first; 
 
    const u8 *end_first = end - iter_bytes_second; 
    /* The amount of data we have to copy from main buffer for the 
     * first iteration. */ 
    size_t copy_len_first = MIN((size_t)(end_first - buf), 
                                ITER_BYTES + sizeof(CONF_TYPE)); 
    assert(copy_len_first >= 16); 
 
    size_t total_copy_len = copy_len_first + iter_bytes_second; 
    assert(total_copy_len + 3 < 64); 
 
    /* copy the post-padding byte; this is required for domain > 8 due to 
     * overhang */ 
    z->buf[total_copy_len] = 0; 
 
    /* set the start and end location of the zone buf 
     * to be scanned */ 
    u8 *z_end = z->buf + total_copy_len; 
    z->end = z_end; 
    z->start = z_end - ITER_BYTES - iter_bytes_second; 
    assert(z->start + z->shift == z_end - z_len); 
 
    u8 *z_end_first = z_end - iter_bytes_second; 
    /* copy the first 8 bytes of the valid region */ 
    unaligned_store_u64a(z->buf, 
                         unaligned_load_u64a(end_first - copy_len_first)); 
 
    /* copy the last 16 bytes, may overlap with the previous 8 byte write */ 
    storeu128(z_end_first - sizeof(m128), loadu128(end_first - sizeof(m128))); 
    if (iter_bytes_second) { 
        storeu128(z_end - sizeof(m128), loadu128(end - sizeof(m128))); 
    } 
 
    z->zone_pointer_adjust = (ptrdiff_t)((uintptr_t)end - (uintptr_t)z_end); 
} 
 
/** 
 * \brief Prepare zones. 
 * 
 * This function prepares zones with actual buffer and some padded bytes. 
 * The actual ITER_BYTES bytes in zone is preceded by main buf and/or 
 * history buf and succeeded by padded bytes possibly from main buf, 
 * if available. 
 */ 
static really_inline 
size_t prepareZones(const u8 *buf, size_t len, const u8 *hend, 
                    size_t start, const u8 *flood, struct zone *zoneArr) { 
    const u8 *ptr = buf + start; 
    size_t remaining = len - start; 
 
    if (remaining <= ITER_BYTES) { 
        /* enough bytes to make only one zone */ 
        createShortZone(buf, hend, ptr, buf + len, &zoneArr[0]); 
        return 1; 
    } 
 
    /* enough bytes to make more than one zone */ 
 
    size_t numZone = 0; 
    createStartZone(buf, hend, ptr, &zoneArr[numZone++]); 
    ptr += ITER_BYTES; 
 
    assert(ptr < buf + len); 
 
    /* find maximum buffer location that the main zone can scan 
     * - must be a multiple of ITER_BYTES, and 
     * - cannot contain the last 3 bytes (due to 3 bytes read behind the 
         end of buffer in FDR main loop) 
     */ 
    const u8 *main_end = buf + start + ROUNDDOWN_N(len - start - 3, ITER_BYTES); 
 
    /* create a zone if multiple of ITER_BYTES are found */ 
    if (main_end > ptr) { 
        createMainZone(flood, ptr, main_end, &zoneArr[numZone++]); 
        ptr = main_end; 
    } 
    /* create a zone with rest of the data from the main buffer */ 
    createEndZone(buf, ptr, buf + len, &zoneArr[numZone++]); 
    return numZone; 
} 
 
#define INVALID_MATCH_ID (~0U) 
 
#define FDR_MAIN_LOOP(zz, s, get_conf_fn)                                   \ 
    do {                                                                    \ 
        const u8 *tryFloodDetect = zz->floodPtr;                            \ 
        const u8 *start_ptr = zz->start;                                    \ 
        const u8 *end_ptr = zz->end;                                        \ 
                                                                            \ 
        for (const u8 *itPtr = start_ptr; itPtr + ITER_BYTES <= end_ptr;    \ 
            itPtr += ITER_BYTES) {                                          \ 
            if (unlikely(itPtr > tryFloodDetect)) {                         \ 
                tryFloodDetect = floodDetect(fdr, a, &itPtr, tryFloodDetect,\ 
                                             &floodBackoff, &control,       \ 
                                             ITER_BYTES);                   \ 
                if (unlikely(control == HWLM_TERMINATE_MATCHING)) {         \ 
                    return HWLM_TERMINATED;                                 \ 
                }                                                           \ 
            }                                                               \ 
            __builtin_prefetch(itPtr + ITER_BYTES);                         \ 
            u64a conf0;                                                     \ 
            u64a conf8;                                                     \ 
            get_conf_fn(itPtr, start_ptr, end_ptr, domain_mask_flipped,     \ 
                        ft, &conf0, &conf8, &s);                            \ 
            do_confirm_fdr(&conf0, 0, &control, confBase, a, itPtr,         \ 
                           &last_match_id, zz);                             \ 
            do_confirm_fdr(&conf8, 8, &control, confBase, a, itPtr,         \ 
                           &last_match_id, zz);                             \ 
            if (unlikely(control == HWLM_TERMINATE_MATCHING)) {             \ 
                return HWLM_TERMINATED;                                     \ 
            }                                                               \ 
        } /* end for loop */                                                \ 
    } while (0)                                                             \ 
 
static never_inline 
hwlm_error_t fdr_engine_exec(const struct FDR *fdr, 
                             const struct FDR_Runtime_Args *a, 
                             hwlm_group_t control) { 
    assert(ISALIGNED_CL(fdr)); 
 
    u32 floodBackoff = FLOOD_BACKOFF_START; 
    u32 last_match_id = INVALID_MATCH_ID; 
    u32 domain_mask_flipped = ~fdr->domainMask; 
    u8 stride = fdr->stride; 
    const u64a *ft = 
        (const u64a *)((const u8 *)fdr + ROUNDUP_CL(sizeof(struct FDR))); 
    assert(ISALIGNED_CL(ft)); 
    const u32 *confBase = (const u32 *)((const u8 *)fdr + fdr->confOffset); 
    assert(ISALIGNED_CL(confBase)); 
    struct zone zones[ZONE_MAX]; 
    assert(fdr->domain > 8 && fdr->domain < 16); 
 
    size_t numZone = prepareZones(a->buf, a->len, 
                                  a->buf_history + a->len_history, 
                                  a->start_offset, a->firstFloodDetect, zones); 
    assert(numZone <= ZONE_MAX); 
    m128 state = getInitState(fdr, a->len_history, ft, &zones[0]); 
 
    for (size_t curZone = 0; curZone < numZone; curZone++) { 
        struct zone *z = &zones[curZone]; 
        dumpZoneInfo(z, curZone); 
 
        /* When a zone contains less data than is processed in an iteration 
         * of FDR_MAIN_LOOP(), we need to scan over some extra data. 
         * 
         * We have chosen to scan this extra data at the start of the 
         * iteration. The extra data is either data we have already scanned or 
         * garbage (if it is earlier than offset 0), 
         * 
         * As a result we need to shift the incoming state back so that it will 
         * properly line up with the data being scanned. 
         * 
         * We also need to forbid reporting any matches in the data being 
         * rescanned as they have already been reported (or are over garbage but 
         * later stages should also provide that safety guarantee). 
         */ 
 
        u8 shift = z->shift; 
 
        state = variable_byte_shift_m128(state, shift); 
 
        state = or128(state, load128(zone_or_mask[shift])); 
 
        switch (stride) { 
        case 1: 
            FDR_MAIN_LOOP(z, state, get_conf_stride_1); 
            break; 
        case 2: 
            FDR_MAIN_LOOP(z, state, get_conf_stride_2); 
            break; 
        case 4: 
            FDR_MAIN_LOOP(z, state, get_conf_stride_4); 
            break; 
        default: 
            break; 
        } 
    } 
 
    return HWLM_SUCCESS; 
} 
 
#if defined(HAVE_AVX2) 
#define ONLY_AVX2(func) func 
#else 
#define ONLY_AVX2(func) NULL 
#endif 
 
typedef hwlm_error_t (*FDRFUNCTYPE)(const struct FDR *fdr, 
                                    const struct FDR_Runtime_Args *a, 
                                    hwlm_group_t control); 
 
static const FDRFUNCTYPE funcs[] = { 
    fdr_engine_exec, 
    NULL, /* old: fast teddy */ 
    NULL, /* old: fast teddy */ 
    ONLY_AVX2(fdr_exec_fat_teddy_msks1), 
    ONLY_AVX2(fdr_exec_fat_teddy_msks1_pck), 
    ONLY_AVX2(fdr_exec_fat_teddy_msks2), 
    ONLY_AVX2(fdr_exec_fat_teddy_msks2_pck), 
    ONLY_AVX2(fdr_exec_fat_teddy_msks3), 
    ONLY_AVX2(fdr_exec_fat_teddy_msks3_pck), 
    ONLY_AVX2(fdr_exec_fat_teddy_msks4), 
    ONLY_AVX2(fdr_exec_fat_teddy_msks4_pck), 
    fdr_exec_teddy_msks1, 
    fdr_exec_teddy_msks1_pck, 
    fdr_exec_teddy_msks2, 
    fdr_exec_teddy_msks2_pck, 
    fdr_exec_teddy_msks3, 
    fdr_exec_teddy_msks3_pck, 
    fdr_exec_teddy_msks4, 
    fdr_exec_teddy_msks4_pck, 
}; 
 
#define FAKE_HISTORY_SIZE 16
static const u8 fake_history[FAKE_HISTORY_SIZE];

hwlm_error_t fdrExec(const struct FDR *fdr, const u8 *buf, size_t len, 
                     size_t start, HWLMCallback cb, 
                     struct hs_scratch *scratch, hwlm_group_t groups) { 
    // We guarantee (for safezone construction) that it is safe to read 16 
    // bytes before the end of the history buffer. 
    const u8 *hbuf = fake_history + FAKE_HISTORY_SIZE; 

    const struct FDR_Runtime_Args a = {
        buf,
        len,
        hbuf, 
        0,
        start,
        cb,
        scratch, 
        nextFloodDetect(buf, len, FLOOD_BACKOFF_START),
        0
    };
    if (unlikely(a.start_offset >= a.len)) {
        return HWLM_SUCCESS;
    } else {
        assert(funcs[fdr->engineID]);
        return funcs[fdr->engineID](fdr, &a, groups); 
    }
}

hwlm_error_t fdrExecStreaming(const struct FDR *fdr, const u8 *hbuf,
                              size_t hlen, const u8 *buf, size_t len,
                              size_t start, HWLMCallback cb, 
                              struct hs_scratch *scratch, 
                              hwlm_group_t groups) { 
    struct FDR_Runtime_Args a = {
        buf,
        len,
        hbuf,
        hlen,
        start,
        cb,
        scratch, 
        nextFloodDetect(buf, len, FLOOD_BACKOFF_START),
        /* we are guaranteed to always have 16 initialised bytes at the end of 
         * the history buffer (they may be garbage). */ 
        hbuf ? unaligned_load_u64a(hbuf + hlen - sizeof(u64a)) : (u64a)0 
    };

    hwlm_error_t ret;
    if (unlikely(a.start_offset >= a.len)) {
        ret = HWLM_SUCCESS;
    } else {
        assert(funcs[fdr->engineID]);
        ret = funcs[fdr->engineID](fdr, &a, groups); 
    }

    return ret;
}