/* Copyright (C) 2013-2014 Open Information Security Foundation

 *

 * You can copy, redistribute or modify this Program under the terms of

 * the GNU General Public License version 2 as published by the Free

 * Software Foundation.

 *

 * This program 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

 * version 2 along with this program; if not, write to the Free Software

 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA

 * 02110-1301, USA.

 */

/**

 * \file

 *

 * \author Ken Steele <suricata@tilera.com>

 * \author Anoop Saldanha <anoopsaldanha@gmail.com>

 *

 *         Aho-corasick MPM optimized for the Tilera Tile-Gx architecture.

 *

 *         Efficient String Matching: An Aid to Bibliographic Search

 *         Alfred V. Aho and Margaret J. Corasick

 *

 *         - Started with util-mpm-ac.c:

 *             - Uses the delta table for calculating transitions,

 *               instead of having separate goto and failure

 *               transitions.

 *             - If we cross 2 ** 16 states, we use 4 bytes in the

 *               transition table to hold each state, otherwise we use

 *               2 bytes.

 *             - This version of the MPM is heavy on memory, but it

 *               performs well.  If you can fit the ruleset with this

 *               mpm on your box without hitting swap, this is the MPM

 *               to go for.

 *

 *         - Added these optimizations:

 *             - Compress the input alphabet from 256 characters down

 *               to the actual characters used in the patterns, plus

 *               one character for all the unused characters.

 *             - Reduce the size of the delta table so that each state

 *               is the smallest power of two that is larger than the

 *               size of the compressed alphabet.

 *             - Specialized the search function based on state count

 *               (small for 8-bit large for 16-bit) and the size of

 *               the alphabet, so that it is constant inside the

 *               function for better optimization.

 *

 * \todo - Do a proper analysis of our existing MPMs and suggest a good

 *         one based on the pattern distribution and the expected

 *         traffic(say http).

 *       - Irrespective of whether we cross 2 ** 16 states or

 *         not,shift to using uint32_t for state type, so that we can

 *         integrate it's status as a final state or not in the

 *         topmost byte.  We are already doing it if state_count is >

 *         2 ** 16.

 *       - Test case-sensitive patterns if they have any ascii chars.

 *         If they don't treat them as nocase.

 *       - Reorder the compressed alphabet to put the most common characters

 *         first.

 */

#include "suricata-common.h"

#include "suricata.h"

#include "detect.h"

#include "detect-parse.h"

#include "detect-engine.h"

#include "detect-engine-build.h"

#include "conf.h"

#include "util-debug.h"

#include "util-unittest.h"

#include "util-unittest-helper.h"

#include "util-memcmp.h"

#include "util-memcpy.h"

#include "util-validate.h"

#include "util-mpm-ac-ks.h"

#include "util-mpm-ac-queue.h"

#if __BYTE_ORDER == __LITTLE_ENDIAN

void SCACTileInitCtx(MpmCtx *);

void SCACTileInitThreadCtx(MpmCtx *, MpmThreadCtx *);

void SCACTileDestroyCtx(MpmCtx *);

void SCACTileDestroyThreadCtx(MpmCtx *, MpmThreadCtx *);

int SCACTileAddPatternCI(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t,

                         uint32_t, SigIntId, uint8_t);

int SCACTileAddPatternCS(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t,

                         uint32_t, SigIntId, uint8_t);

int SCACTilePreparePatterns(MpmCtx *mpm_ctx);

uint32_t SCACTileSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx,

                        PrefilterRuleStore *pmq, const uint8_t *buf,

                        uint32_t buflen);

void SCACTilePrintInfo(MpmCtx *mpm_ctx);

void SCACTilePrintSearchStats(MpmThreadCtx *mpm_thread_ctx);

void SCACTileRegisterTests(void);

uint32_t SCACTileSearchLarge(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                             PrefilterRuleStore *pmq,

                             const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchSmall256(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                                PrefilterRuleStore *pmq,

                                const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchSmall128(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                                PrefilterRuleStore *pmq,

                                const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchSmall64(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                               PrefilterRuleStore *pmq,

                               const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchSmall32(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                               PrefilterRuleStore *pmq,

                               const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchSmall16(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                               PrefilterRuleStore *pmq,

                               const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchSmall8(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                              PrefilterRuleStore *pmq,

                              const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchTiny256(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                               PrefilterRuleStore *pmq,

                               const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchTiny128(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                               PrefilterRuleStore *pmq,

                               const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchTiny64(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                              PrefilterRuleStore *pmq,

                              const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchTiny32(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                              PrefilterRuleStore *pmq,

                              const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchTiny16(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                              PrefilterRuleStore *pmq,

                              const uint8_t *buf, uint32_t buflen);

uint32_t SCACTileSearchTiny8(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,

                             PrefilterRuleStore *pmq,

                             const uint8_t *buf, uint32_t buflen);

static void SCACTileDestroyInitCtx(MpmCtx *mpm_ctx);

/* a placeholder to denote a failure transition in the goto table */

#define SC_AC_TILE_FAIL (-1)

/**

 * \internal

 * \brief Initialize the AC context with user specified conf parameters.  We

 *        aren't retrieving anything for AC conf now, but we will certainly

 *        need it, when we customize AC.

 */

static void SCACTileGetConfig(void)

{

}

/**

 * \internal

 * \brief Count the occurrences of each character in the pattern and

 * accumulate into a histogram. Really only used to detect unused

 * characters, so could just set to 1 instead of counting.

 */

static inline void SCACTileHistogramAlphabet(SCACTileCtx *ctx,

                                             MpmPattern *p)

{

    for (int i = 0; i < p->len; i++) {

        ctx->alpha_hist[p->ci[i]]++;

    }

}

/* Use Alphabet Histogram to create compressed alphabet.

 */

static void SCACTileInitTranslateTable(SCACTileCtx *ctx)

{

    /* Count the number of ASCII values actually appearing in any

     * pattern.  Create compressed mapping table with unused

     * characters mapping to zero.

     */

    for (int i = 0; i < 256; i++) {

        /* Move all upper case counts to lower case */

        if (i >= 'A' && i <= 'Z') {

            ctx->alpha_hist[i - 'A' + 'a'] += ctx->alpha_hist[i];

            ctx->alpha_hist[i] = 0;

        }

        if (ctx->alpha_hist[i]) {

            ctx->alphabet_size++;

            DEBUG_VALIDATE_BUG_ON(ctx->alphabet_size > UINT8_MAX);

            ctx->translate_table[i] = (uint8_t)ctx->alphabet_size;

        } else

            ctx->translate_table[i] = 0;

    }

    /* Fix up translation table for uppercase */

    for (int i = 'A'; i <= 'Z'; i++)

        ctx->translate_table[i] = ctx->translate_table[i - 'A' + 'a'];

    SCLogDebug("  Alphabet size %d", ctx->alphabet_size);

    /* Round alphabet size up to next power-of-two Leave one extra

     * space For the unused-characters = 0 mapping.

     */

    ctx->alphabet_size += 1; /* Extra space for unused-character */

    if (ctx->alphabet_size  <= 8) {

        ctx->alphabet_storage = 8;

    } else if (ctx->alphabet_size  <= 16) {

        ctx->alphabet_storage = 16;

    } else if (ctx->alphabet_size  <= 32) {

        ctx->alphabet_storage = 32;

    } else if (ctx->alphabet_size <= 64) {

        ctx->alphabet_storage = 64;

    } else if (ctx->alphabet_size <= 128) {

        ctx->alphabet_storage = 128;

    } else

        ctx->alphabet_storage = 256;

}

static void SCACTileReallocOutputTable(SCACTileCtx *ctx, int new_state_count)

{

    /* reallocate space in the output table for the new state */

    size_t size = ctx->allocated_state_count * sizeof(SCACTileOutputTable);

    void *ptmp = SCRealloc(ctx->output_table, size);

    if (ptmp == NULL) {

        SCFree(ctx->output_table);

        ctx->output_table = NULL;

        FatalError("Error allocating memory");

    }

    ctx->output_table = ptmp;

}

static void SCACTileReallocState(SCACTileCtx *ctx, int new_state_count)

{

    /* reallocate space in the goto table to include a new state */

    size_t size = ctx->allocated_state_count * sizeof(int32_t) * 256;

    void *ptmp = SCRealloc(ctx->goto_table, size);

    if (ptmp == NULL) {

        SCFree(ctx->goto_table);

        ctx->goto_table = NULL;

        FatalError("Error allocating memory");

    }

    ctx->goto_table = ptmp;

    SCACTileReallocOutputTable(ctx, new_state_count);

}

/**

 * \internal

 * \brief Initialize a new state in the goto and output tables.

 *

 * \param mpm_ctx Pointer to the mpm context.

 *

 * \retval The state id, of the newly created state.

 */

static inline int SCACTileInitNewState(MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    int aa = 0;

    /* Exponentially increase the allocated space when needed. */

    if (ctx->allocated_state_count < ctx->state_count + 1) {

        if (ctx->allocated_state_count == 0)

            ctx->allocated_state_count = 256;

        else

            ctx->allocated_state_count *= 2;

        SCACTileReallocState(ctx, ctx->allocated_state_count);

    }

    /* set all transitions for the newly assigned state as FAIL transitions */

    for (aa = 0; aa < ctx->alphabet_size; aa++) {

        ctx->goto_table[ctx->state_count][aa] = SC_AC_TILE_FAIL;

    }

    memset(ctx->output_table + ctx->state_count, 0,

           sizeof(SCACTileOutputTable));

    return ctx->state_count++;

}

/**

 * \internal

 * \brief Adds a pid to the output table for a state.

 *

 * \param state   The state to whose output table we should add the pid.

 * \param pid     The pattern id to add.

 * \param mpm_ctx Pointer to the mpm context.

 */

static void SCACTileSetOutputState(int32_t state, MpmPatternIndex pindex, MpmCtx *mpm_ctx)

{

    void *ptmp;

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    SCACTileOutputTable *output_state = &ctx->output_table[state];

    uint32_t i = 0;

    /* Don't add the pattern more than once to the same state. */

    for (i = 0; i < output_state->no_of_entries; i++) {

        if (output_state->patterns[i] == pindex)

            return;

    }

    /* Increase the size of the array of pids for this state and add

     * the new pid. */

    output_state->no_of_entries++;

    ptmp = SCRealloc(output_state->patterns,

                     output_state->no_of_entries * sizeof(MpmPatternIndex));

    if (ptmp == NULL) {

        SCFree(output_state->patterns);

        output_state->patterns = NULL;

        FatalError("Error allocating memory");

    }

    output_state->patterns = ptmp;

    output_state->patterns[output_state->no_of_entries - 1] = pindex;

}

/**

 * \brief Helper function used by SCACTileCreateGotoTable.  Adds a

 *        pattern to the goto table.

 *

 * \param pattern     Pointer to the pattern.

 * \param pattern_len Pattern length.

 * \param pid         The pattern id, that corresponds to this pattern.  We

 *                    need it to updated the output table for this pattern.

 * \param mpm_ctx     Pointer to the mpm context.

 */

static void SCACTileEnter(uint8_t *pattern, uint16_t pattern_len,

                          MpmPatternIndex pindex, MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    int32_t state = 0;

    int32_t newstate = 0;

    int i = 0;

    int p = 0;

    int tc;

    /* Walk down the trie till we have a match for the pattern prefix */

    state = 0;

    for (i = 0; i < pattern_len; i++) {

        tc = ctx->translate_table[pattern[i]];

        if (ctx->goto_table[state][tc] == SC_AC_TILE_FAIL)

            break;

        state = ctx->goto_table[state][tc];

    }

    /* Add the non-matching pattern suffix to the trie, from the last state

     * we left off */

    for (p = i; p < pattern_len; p++) {

        newstate = SCACTileInitNewState(mpm_ctx);

        tc = ctx->translate_table[pattern[p]];

        ctx->goto_table[state][tc] = newstate;

        state = newstate;

    }

    /* Add this pattern id, to the output table of the last state, where the

     * pattern ends in the trie */

    SCACTileSetOutputState(state, pindex, mpm_ctx);

}

/**

 * \internal

 * \brief Create the goto table.

 *

 * \param mpm_ctx Pointer to the mpm context.

 */

static void SCACTileCreateGotoTable(MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    uint32_t i = 0;

    /* add each pattern to create the goto table */

    for (i = 0; i < mpm_ctx->pattern_cnt; i++) {

        SCACTileEnter(ctx->parray[i]->ci, ctx->parray[i]->len,

                      i, mpm_ctx);

    }

    int aa = 0;

    for (aa = 0; aa < ctx->alphabet_size; aa++) {

        if (ctx->goto_table[0][aa] == SC_AC_TILE_FAIL) {

            ctx->goto_table[0][aa] = 0;

        }

    }

}

/**

 * \internal

 * \brief Club the output data from 2 states and store it in the 1st state.

 *        dst_state_data = {dst_state_data} UNION {src_state_data}

 *

 * \param dst_state First state(also the destination) for the union operation.

 * \param src_state Second state for the union operation.

 * \param mpm_ctx Pointer to the mpm context.

 */

static void SCACTileClubOutputStates(int32_t dst_state,

                                     int32_t src_state,

                                     MpmCtx *mpm_ctx)

{

    void *ptmp;

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    uint32_t i = 0;

    uint32_t j = 0;

    SCACTileOutputTable *output_dst_state = &ctx->output_table[dst_state];

    SCACTileOutputTable *output_src_state = &ctx->output_table[src_state];

    for (i = 0; i < output_src_state->no_of_entries; i++) {

        for (j = 0; j < output_dst_state->no_of_entries; j++) {

            if (output_src_state->patterns[i] == output_dst_state->patterns[j]) {

                break;

            }

        }

        if (j == output_dst_state->no_of_entries) {

            output_dst_state->no_of_entries++;

            ptmp = SCRealloc(output_dst_state->patterns,

                             (output_dst_state->no_of_entries * sizeof(uint32_t)));

            if (ptmp == NULL) {

                SCFree(output_dst_state->patterns);

                output_dst_state->patterns = NULL;

                FatalError("Error allocating memory");

            }

            output_dst_state->patterns = ptmp;

            output_dst_state->patterns[output_dst_state->no_of_entries - 1] =

                output_src_state->patterns[i];

        }

    }

}

/**

 * \internal

 * \brief Create the failure table.

 *

 * \param mpm_ctx Pointer to the mpm context.

 */

static void SCACTileCreateFailureTable(MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    int aa = 0;

    int32_t state = 0;

    int32_t r_state = 0;

    StateQueue *q = SCACStateQueueAlloc();

    /* Allocate space for the failure table.  A failure entry in the table for

     * every state(SCACTileCtx->state_count) */

    ctx->failure_table = SCMalloc(ctx->state_count * sizeof(int32_t));

    if (ctx->failure_table == NULL) {

        FatalError("Error allocating memory");

    }

    memset(ctx->failure_table, 0, ctx->state_count * sizeof(int32_t));

    /* Add the failure transitions for the 0th state, and add every non-fail

     * transition from the 0th state to the queue for further processing

     * of failure states */

    for (aa = 0; aa < ctx->alphabet_size; aa++) {

        int32_t temp_state = ctx->goto_table[0][aa];

        if (temp_state != 0) {

            SCACEnqueue(q, temp_state);

            ctx->failure_table[temp_state] = 0;

        }

    }

    while (!SCACStateQueueIsEmpty(q)) {

        /* pick up every state from the queue and add failure transitions */

        r_state = SCACDequeue(q);

        for (aa = 0; aa < ctx->alphabet_size; aa++) {

            int32_t temp_state = ctx->goto_table[r_state][aa];

            if (temp_state == SC_AC_TILE_FAIL)

                continue;

            SCACEnqueue(q, temp_state);

            state = ctx->failure_table[r_state];

            while(ctx->goto_table[state][aa] == SC_AC_TILE_FAIL)

                state = ctx->failure_table[state];

            ctx->failure_table[temp_state] = ctx->goto_table[state][aa];

            SCACTileClubOutputStates(temp_state, ctx->failure_table[temp_state],

                                     mpm_ctx);

        }

    }

    SCACStateQueueFree(q);

}

/*

 * Set the next state for 1 byte next-state.

 */

static void SCACTileSetState1Byte(SCACTileCtx *ctx, int state, int aa,

                                  int next_state, int outputs)

{

    uint8_t *state_table = (uint8_t*)ctx->state_table;

    DEBUG_VALIDATE_BUG_ON(next_state < 0 || next_state > UINT8_MAX);

    uint8_t encoded_next_state = (uint8_t)next_state;

    if (next_state == SC_AC_TILE_FAIL) {

        FatalError("Error FAIL state in output");

    }

    if (outputs == 0)

        encoded_next_state |= (1 << 7);

    state_table[state * ctx->alphabet_storage + aa] = encoded_next_state;

}

/*

 * Set the next state for 2 byte next-state.

 */

static void SCACTileSetState2Bytes(SCACTileCtx *ctx, int state, int aa,

                                   int next_state, int outputs)

{

    uint16_t *state_table = (uint16_t*)ctx->state_table;

    DEBUG_VALIDATE_BUG_ON(next_state < 0 || next_state > UINT16_MAX);

    uint16_t encoded_next_state = (uint16_t)next_state;

    if (next_state == SC_AC_TILE_FAIL) {

        FatalError("Error FAIL state in output");

    }

    if (outputs == 0)

        encoded_next_state |= (1 << 15);

    state_table[state * ctx->alphabet_storage + aa] = encoded_next_state;

}

/*

 * Set the next state for 4 byte next-state.

 */

static void SCACTileSetState4Bytes(SCACTileCtx *ctx, int state, int aa,

                                   int next_state, int outputs)

{

    uint32_t *state_table = (uint32_t*)ctx->state_table;

    uint32_t encoded_next_state = next_state;

    if (next_state == SC_AC_TILE_FAIL) {

        FatalError("Error FAIL state in output");

    }

    if (outputs == 0)

        encoded_next_state |= (1UL << 31);

    state_table[state * ctx->alphabet_storage + aa] = encoded_next_state;

}

/**

 * \internal

 * \brief Create the delta table.

 *

 * \param mpm_ctx Pointer to the mpm context.

 */

static inline void SCACTileCreateDeltaTable(MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    int aa = 0;

    int32_t r_state = 0;

    if (ctx->state_count < 32767) {

        if (ctx->state_count < 128) {

            ctx->bytes_per_state = 1;

            ctx->SetNextState = SCACTileSetState1Byte;

            switch(ctx->alphabet_storage) {

            case 8:

                ctx->Search = SCACTileSearchTiny8;

                break;

            case 16:

                ctx->Search = SCACTileSearchTiny16;

                break;

            case 32:

                ctx->Search = SCACTileSearchTiny32;

                break;

            case 64:

                ctx->Search = SCACTileSearchTiny64;

                break;

            case 128:

                ctx->Search = SCACTileSearchTiny128;

                break;

            default:

                ctx->Search = SCACTileSearchTiny256;

            }

        } else {

            /* 16-bit state needed */

            ctx->bytes_per_state = 2;

            ctx->SetNextState = SCACTileSetState2Bytes;

            switch(ctx->alphabet_storage) {

            case 8:

                ctx->Search = SCACTileSearchSmall8;

                break;

            case 16:

                ctx->Search = SCACTileSearchSmall16;

                break;

            case 32:

                ctx->Search = SCACTileSearchSmall32;

                break;

            case 64:

                ctx->Search = SCACTileSearchSmall64;

                break;

            case 128:

                ctx->Search = SCACTileSearchSmall128;

                break;

            default:

                ctx->Search = SCACTileSearchSmall256;

            }

        }

    } else {

        /* 32-bit next state */

        ctx->Search = SCACTileSearchLarge;

        ctx->bytes_per_state = 4;

        ctx->SetNextState = SCACTileSetState4Bytes;

        ctx->alphabet_storage = 256; /* Change? */

    }

    StateQueue *q = SCACStateQueueAlloc();

    for (aa = 0; aa < ctx->alphabet_size; aa++) {

        int temp_state = ctx->goto_table[0][aa];

        if (temp_state != 0)

            SCACEnqueue(q, temp_state);

    }

    while (!SCACStateQueueIsEmpty(q)) {

        r_state = SCACDequeue(q);

        for (aa = 0; aa < ctx->alphabet_size; aa++) {

            int temp_state = ctx->goto_table[r_state][aa];

            if (temp_state != SC_AC_TILE_FAIL) {

                SCACEnqueue(q, temp_state);

            } else {

                int f_state = ctx->failure_table[r_state];

                ctx->goto_table[r_state][aa] = ctx->goto_table[f_state][aa];

            }

        }

    }

    SCACStateQueueFree(q);

}

static void SCACTileClubOutputStatePresenceWithDeltaTable(MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    int aa = 0;

    uint32_t state = 0;

    /* Allocate next-state table. */

    int size = ctx->state_count * ctx->bytes_per_state * ctx->alphabet_storage;

    void *state_table = SCMalloc(size);

    if (unlikely(state_table == NULL)) {

        FatalError("Error allocating memory");

    }

    memset(state_table, 0, size);

    ctx->state_table = state_table;

    mpm_ctx->memory_cnt++;

    mpm_ctx->memory_size += size;

    SCLogDebug("Delta Table size %d,  alphabet: %d, %d-byte states: %d",

              size, ctx->alphabet_size, ctx->bytes_per_state, ctx->state_count);

    /* Copy next state from Goto table, which is 32 bits and encode it into the next

     * state table, which can be 1, 2 or 4 bytes each and include if there is an

     * output.

     */

    for (state = 0; state < ctx->state_count; state++) {

        for (aa = 0; aa < ctx->alphabet_size; aa++) {

            int next_state = ctx->goto_table[state][aa];

            int next_state_outputs = ctx->output_table[next_state].no_of_entries;

            ctx->SetNextState(ctx, state, aa, next_state, next_state_outputs);

        }

    }

}

static inline void SCACTileInsertCaseSensitiveEntriesForPatterns(MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    uint32_t state = 0;

    uint32_t k = 0;

    for (state = 0; state < ctx->state_count; state++) {

        if (ctx->output_table[state].no_of_entries == 0)

            continue;

        for (k = 0; k < ctx->output_table[state].no_of_entries; k++) {

            if (ctx->pattern_list[ctx->output_table[state].patterns[k]].cs != NULL) {

              /* TODO - Find better way to store this. */

                ctx->output_table[state].patterns[k] &= 0x0FFFFFFF;

                ctx->output_table[state].patterns[k] |= (uint32_t)1 << 31;

            }

        }

    }

}

#if 0

static void SCACTilePrintDeltaTable(MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    int i = 0, j = 0;

    printf("##############Delta Table##############\n");

    for (i = 0; i < ctx->state_count; i++) {

        printf("%d: \n", i);

        for (j = 0; j < ctx->alphabet_size; j++) {

            if (SCACTileGetDelta(i, j, mpm_ctx) != 0) {

                printf("  %c -> %d\n", j, SCACTileGetDelta(i, j, mpm_ctx));

            }

        }

    }

}

#endif

/**

 * \brief Process the patterns and prepare the state table.

 *

 * \param mpm_ctx Pointer to the mpm context.

 */

static void SCACTilePrepareStateTable(MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    /* Create Alphabet compression and Lower Case translation table. */

    SCACTileInitTranslateTable(ctx);

    /* create the 0th state in the goto table and output_table */

    SCACTileInitNewState(mpm_ctx);

    /* create the goto table */

    SCACTileCreateGotoTable(mpm_ctx);

    /* create the failure table */

    SCACTileCreateFailureTable(mpm_ctx);

    /* create the final state(delta) table */

    SCACTileCreateDeltaTable(mpm_ctx);

    /* club the output state presence with delta transition entries */

    SCACTileClubOutputStatePresenceWithDeltaTable(mpm_ctx);

    /* club nocase entries */

    SCACTileInsertCaseSensitiveEntriesForPatterns(mpm_ctx);

#if 0

    SCACTilePrintDeltaTable(mpm_ctx);

#endif

    /* we don't need these anymore */

    SCFree(ctx->goto_table);

    ctx->goto_table = NULL;

    SCFree(ctx->failure_table);

    ctx->failure_table = NULL;

}

/**

 * \brief Process Internal AC MPM tables to create the Search Context

 *

 * The search context is only the data needed to search the MPM.

 *

 * \param mpm_ctx Pointer to the mpm context.

 */

static void SCACTilePrepareSearch(MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    SCACTileCtx *ctx = search_ctx->init_ctx;

    /* Resize the output table to be only as big as its final size. */

    SCACTileReallocOutputTable(ctx, ctx->state_count);

    search_ctx->Search = ctx->Search;

    memcpy(search_ctx->translate_table, ctx->translate_table, sizeof(ctx->translate_table));

    /* Move the state table from the Init context */

    search_ctx->state_table = ctx->state_table;

    ctx->state_table = NULL; /* So that it won't get freed twice. */

    /* Move the output_table from the Init context to the Search Context */

    /* TODO: Could be made more compact */

    search_ctx->output_table = ctx->output_table;

    ctx->output_table = NULL;

    search_ctx->state_count = ctx->state_count;

    search_ctx->pattern_list = ctx->pattern_list;

    ctx->pattern_list = NULL;

    search_ctx->pattern_cnt = mpm_ctx->pattern_cnt;

    /* One bit per pattern, rounded up to the next byte size. */

    search_ctx->mpm_bitarray_size = (mpm_ctx->pattern_cnt + 7) / 8;

    /* Can now free the Initialization data */

    SCACTileDestroyInitCtx(mpm_ctx);

}

/**

 * \brief Process the patterns added to the mpm, and create the internal tables.

 *

 * \param mpm_ctx Pointer to the mpm context.

 */

int SCACTilePreparePatterns(MpmCtx *mpm_ctx)

{

    SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;

    if (mpm_ctx->pattern_cnt == 0 || search_ctx->init_ctx == NULL) {

        SCLogDebug("no patterns supplied to this mpm_ctx");

        return 0;

    }

    SCACTileCtx *ctx = search_ctx->init_ctx;

    if (mpm_ctx->init_hash == NULL) {

        SCLogDebug("no patterns supplied to this mpm_ctx");

        return 0;

    }

    /* alloc the pattern array */

    ctx->parray = (MpmPattern **)SCMalloc(mpm_ctx->pattern_cnt *

                                               sizeof(MpmPattern *));

    if (ctx->parray == NULL)

        goto error;

    memset(ctx->parray, 0, mpm_ctx->pattern_cnt * sizeof(MpmPattern *));

    /* populate it with the patterns in the hash */

    uint32_t i = 0, p = 0;

    for (i = 0; i < MPM_INIT_HASH_SIZE; i++) {

        MpmPattern *node = mpm_ctx->init_hash[i], *nnode = NULL;

        while(node != NULL) {

            nnode = node->next;

            node->next = NULL;

            ctx->parray[p++] = node;

            SCACTileHistogramAlphabet(ctx, node);

            node = nnode;

        }

    }

    /* we no longer need the hash, so free it's memory */

    SCFree(mpm_ctx->init_hash);

    mpm_ctx->init_hash = NULL;

    /* Handle case patterns by storing a copy of the pattern to compare

     * to each possible match (no-case).

     *

     * Allocate the memory for the array and each of the strings as one block.

     */

    size_t string_space_needed = 0;

    for (i = 0; i < mpm_ctx->pattern_cnt; i++) {

        if (!(ctx->parray[i]->flags & MPM_PATTERN_FLAG_NOCASE)) {

            /* Round up to next 8 byte aligned length */

            uint32_t space = ((ctx->parray[i]->len + 7) / 8) * 8;

            string_space_needed += space;

        }

    }

    size_t pattern_list_size = mpm_ctx->pattern_cnt * sizeof(SCACTilePatternList);

    size_t mem_size = string_space_needed + pattern_list_size;

    void *mem_block = SCCalloc(1, mem_size);

    if (mem_block == NULL) {

        FatalError("Error allocating memory");

    }

    mpm_ctx->memory_cnt++;

    mpm_ctx->memory_size += mem_size;

    /* Split the allocated block into pattern list array and string space. */

    ctx->pattern_list = mem_block;

    uint8_t *string_space = mem_block + pattern_list_size;

    /* Now make the copies of the no-case strings. */

    for (i = 0; i < mpm_ctx->pattern_cnt; i++) {

        if (!(ctx->parray[i]->flags & MPM_PATTERN_FLAG_NOCASE)) {

            uint16_t len = ctx->parray[i]->len;

            uint32_t space = ((len + 7) / 8) * 8;

            memcpy(string_space, ctx->parray[i]->original_pat, len);

            ctx->pattern_list[i].cs = string_space;

            ctx->pattern_list[i].patlen = len;

            string_space += space;

        }

        ctx->pattern_list[i].offset = ctx->parray[i]->offset;

        ctx->pattern_list[i].depth = ctx->parray[i]->depth;

        ctx->pattern_list[i].pid = ctx->parray[i]->id;

        /* ACPatternList now owns this memory */

        ctx->pattern_list[i].sids_size = ctx->parray[i]->sids_size;

        ctx->pattern_list[i].sids = ctx->parray[i]->sids;

        ctx->parray[i]->sids = NULL;

        ctx->parray[i]->sids_size = 0;

    }

    /* prepare the state table required by AC */

    SCACTilePrepareStateTable(mpm_ctx);

    /* Convert to the Search Context structure */

    SCACTilePrepareSearch(mpm_ctx);

    return 0;

error:

    return -1;

}

/**

 * \brief Init the mpm thread context.

 *

 * \param mpm_ctx        Pointer to the mpm context.

 * \param mpm_thread_ctx Pointer to the mpm thread context.

 */

void SCACTileInitThreadCtx(MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)

{

    memset(mpm_thread_ctx, 0, sizeof(MpmThreadCtx));

    mpm_thread_ctx->ctx = SCMalloc(sizeof(SCACTileThreadCtx));

    if (mpm_thread_ctx->ctx == NULL) {

        exit(EXIT_FAILURE);

    }

    memset(mpm_thread_ctx->ctx, 0, sizeof(SCACTileThreadCtx));

    mpm_thread_ctx->memory_cnt++;

    mpm_thread_ctx->memory_size += sizeof(SCACTileThreadCtx);

}

/**

 * \brief Initialize the AC context.

 *

 * \param mpm_ctx       Mpm context.

 */