suricata
util-mpm-ac-ks.c
Go to the documentation of this file.
1 /* Copyright (C) 2013-2014 Open Information Security Foundation
2  *
3  * You can copy, redistribute or modify this Program under the terms of
4  * the GNU General Public License version 2 as published by the Free
5  * Software Foundation.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * version 2 along with this program; if not, write to the Free Software
14  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
15  * 02110-1301, USA.
16  */
17 
18 /**
19  * \file
20  *
21  * \author Ken Steele <suricata@tilera.com>
22  * \author Anoop Saldanha <anoopsaldanha@gmail.com>
23  *
24  * Aho-corasick MPM optimized for the Tilera Tile-Gx architecture.
25  *
26  * Efficient String Matching: An Aid to Bibliographic Search
27  * Alfred V. Aho and Margaret J. Corasick
28  *
29  * - Started with util-mpm-ac.c:
30  * - Uses the delta table for calculating transitions,
31  * instead of having separate goto and failure
32  * transitions.
33  * - If we cross 2 ** 16 states, we use 4 bytes in the
34  * transition table to hold each state, otherwise we use
35  * 2 bytes.
36  * - This version of the MPM is heavy on memory, but it
37  * performs well. If you can fit the ruleset with this
38  * mpm on your box without hitting swap, this is the MPM
39  * to go for.
40  *
41  * - Added these optimizations:
42  * - Compress the input alphabet from 256 characters down
43  * to the actual characters used in the patterns, plus
44  * one character for all the unused characters.
45  * - Reduce the size of the delta table so that each state
46  * is the smallest power of two that is larger than the
47  * size of the compressed alphabet.
48  * - Specialized the search function based on state count
49  * (small for 8-bit large for 16-bit) and the size of
50  * the alphabet, so that it is constant inside the
51  * function for better optimization.
52  *
53  * \todo - Do a proper analysis of our existing MPMs and suggest a good
54  * one based on the pattern distribution and the expected
55  * traffic(say http).
56 
57  * - Irrespective of whether we cross 2 ** 16 states or
58  * not,shift to using uint32_t for state type, so that we can
59  * integrate it's status as a final state or not in the
60  * topmost byte. We are already doing it if state_count is >
61  * 2 ** 16.
62  * - Test case-sensitive patterns if they have any ascii chars.
63  * If they don't treat them as nocase.
64  * - Reorder the compressed alphabet to put the most common characters
65  * first.
66  */
67 
68 #include "suricata-common.h"
69 #include "suricata.h"
70 
71 #include "detect.h"
72 #include "detect-parse.h"
73 #include "detect-engine.h"
74 #include "detect-engine-build.h"
75 
76 #include "conf.h"
77 #include "util-debug.h"
78 #include "util-unittest.h"
79 #include "util-unittest-helper.h"
80 #include "util-memcmp.h"
81 #include "util-memcpy.h"
82 #include "util-validate.h"
83 #include "util-mpm-ac-ks.h"
84 
85 #if __BYTE_ORDER == __LITTLE_ENDIAN
86 
87 void SCACTileInitCtx(MpmCtx *);
89 int SCACTileAddPatternCI(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t,
90  uint32_t, SigIntId, uint8_t);
91 int SCACTileAddPatternCS(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t,
92  uint32_t, SigIntId, uint8_t);
93 int SCACTilePreparePatterns(MpmConfig *mpm_conf, MpmCtx *mpm_ctx);
94 uint32_t SCACTileSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx,
95  PrefilterRuleStore *pmq, const uint8_t *buf,
96  uint32_t buflen);
97 void SCACTilePrintInfo(MpmCtx *mpm_ctx);
98 #ifdef UNITTESTS
99 static void SCACTileRegisterTests(void);
100 #endif
101 
102 uint32_t SCACTileSearchLarge(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
103  PrefilterRuleStore *pmq,
104  const uint8_t *buf, uint32_t buflen);
105 uint32_t SCACTileSearchSmall256(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
106  PrefilterRuleStore *pmq,
107  const uint8_t *buf, uint32_t buflen);
108 uint32_t SCACTileSearchSmall128(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
109  PrefilterRuleStore *pmq,
110  const uint8_t *buf, uint32_t buflen);
111 uint32_t SCACTileSearchSmall64(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
112  PrefilterRuleStore *pmq,
113  const uint8_t *buf, uint32_t buflen);
114 uint32_t SCACTileSearchSmall32(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
115  PrefilterRuleStore *pmq,
116  const uint8_t *buf, uint32_t buflen);
117 uint32_t SCACTileSearchSmall16(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
118  PrefilterRuleStore *pmq,
119  const uint8_t *buf, uint32_t buflen);
120 uint32_t SCACTileSearchSmall8(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
121  PrefilterRuleStore *pmq,
122  const uint8_t *buf, uint32_t buflen);
123 
124 uint32_t SCACTileSearchTiny256(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
125  PrefilterRuleStore *pmq,
126  const uint8_t *buf, uint32_t buflen);
127 uint32_t SCACTileSearchTiny128(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
128  PrefilterRuleStore *pmq,
129  const uint8_t *buf, uint32_t buflen);
130 uint32_t SCACTileSearchTiny64(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
131  PrefilterRuleStore *pmq,
132  const uint8_t *buf, uint32_t buflen);
133 uint32_t SCACTileSearchTiny32(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
134  PrefilterRuleStore *pmq,
135  const uint8_t *buf, uint32_t buflen);
136 uint32_t SCACTileSearchTiny16(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
137  PrefilterRuleStore *pmq,
138  const uint8_t *buf, uint32_t buflen);
139 uint32_t SCACTileSearchTiny8(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
140  PrefilterRuleStore *pmq,
141  const uint8_t *buf, uint32_t buflen);
142 
143 
144 static void SCACTileDestroyInitCtx(MpmCtx *mpm_ctx);
145 
146 
147 /* a placeholder to denote a failure transition in the goto table */
148 #define SC_AC_TILE_FAIL (-1)
149 
150 #define STATE_QUEUE_CONTAINER_SIZE 65536
151 
152 /**
153  * \brief Helper structure used by AC during state table creation
154  */
155 typedef struct StateQueue_ {
157  int top;
158  int bot;
160 
161 /**
162  * \internal
163  * \brief Initialize the AC context with user specified conf parameters. We
164  * aren't retrieving anything for AC conf now, but we will certainly
165  * need it, when we customize AC.
166  */
167 static void SCACTileGetConfig(void)
168 {
169 }
170 
171 /**
172  * \internal
173  * \brief Count the occurrences of each character in the pattern and
174  * accumulate into a histogram. Really only used to detect unused
175  * characters, so could just set to 1 instead of counting.
176  */
177 static inline void SCACTileHistogramAlphabet(SCACTileCtx *ctx,
178  MpmPattern *p)
179 {
180  for (int i = 0; i < p->len; i++) {
181  ctx->alpha_hist[p->ci[i]]++;
182  }
183 }
184 
185 /* Use Alphabet Histogram to create compressed alphabet.
186  */
187 static void SCACTileInitTranslateTable(SCACTileCtx *ctx)
188 {
189  /* Count the number of ASCII values actually appearing in any
190  * pattern. Create compressed mapping table with unused
191  * characters mapping to zero.
192  */
193  for (int i = 0; i < 256; i++) {
194  /* Move all upper case counts to lower case */
195  if (i >= 'A' && i <= 'Z') {
196  ctx->alpha_hist[i - 'A' + 'a'] += ctx->alpha_hist[i];
197  ctx->alpha_hist[i] = 0;
198  }
199  if (ctx->alpha_hist[i]) {
200  ctx->alphabet_size++;
201  DEBUG_VALIDATE_BUG_ON(ctx->alphabet_size > UINT8_MAX);
202  ctx->translate_table[i] = (uint8_t)ctx->alphabet_size;
203  } else
204  ctx->translate_table[i] = 0;
205  }
206  /* Fix up translation table for uppercase */
207  for (int i = 'A'; i <= 'Z'; i++)
208  ctx->translate_table[i] = ctx->translate_table[i - 'A' + 'a'];
209 
210  SCLogDebug(" Alphabet size %d", ctx->alphabet_size);
211 
212  /* Round alphabet size up to next power-of-two Leave one extra
213  * space For the unused-characters = 0 mapping.
214  */
215  ctx->alphabet_size += 1; /* Extra space for unused-character */
216  if (ctx->alphabet_size <= 8) {
217  ctx->alphabet_storage = 8;
218  } else if (ctx->alphabet_size <= 16) {
219  ctx->alphabet_storage = 16;
220  } else if (ctx->alphabet_size <= 32) {
221  ctx->alphabet_storage = 32;
222  } else if (ctx->alphabet_size <= 64) {
223  ctx->alphabet_storage = 64;
224  } else if (ctx->alphabet_size <= 128) {
225  ctx->alphabet_storage = 128;
226  } else
227  ctx->alphabet_storage = 256;
228 }
229 
230 static void SCACTileReallocOutputTable(SCACTileCtx *ctx, int new_state_count)
231 {
232 
233  /* reallocate space in the output table for the new state */
234  size_t size = ctx->allocated_state_count * sizeof(SCACTileOutputTable);
235  void *ptmp = SCRealloc(ctx->output_table, size);
236  if (ptmp == NULL) {
237  SCFree(ctx->output_table);
238  ctx->output_table = NULL;
239  FatalError("Error allocating memory");
240  }
241  ctx->output_table = ptmp;
242 }
243 
244 static void SCACTileReallocState(SCACTileCtx *ctx, int new_state_count)
245 {
246  /* reallocate space in the goto table to include a new state */
247  size_t size = ctx->allocated_state_count * sizeof(int32_t) * 256;
248  void *ptmp = SCRealloc(ctx->goto_table, size);
249  if (ptmp == NULL) {
250  SCFree(ctx->goto_table);
251  ctx->goto_table = NULL;
252  FatalError("Error allocating memory");
253  }
254  ctx->goto_table = ptmp;
255 
256  SCACTileReallocOutputTable(ctx, new_state_count);
257 }
258 
259 /**
260  * \internal
261  * \brief Initialize a new state in the goto and output tables.
262  *
263  * \param mpm_ctx Pointer to the mpm context.
264  *
265  * \retval The state id, of the newly created state.
266  */
267 static inline int SCACTileInitNewState(MpmCtx *mpm_ctx)
268 {
269  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
270  SCACTileCtx *ctx = search_ctx->init_ctx;
271  int aa = 0;
272 
273  /* Exponentially increase the allocated space when needed. */
274  if (ctx->allocated_state_count < ctx->state_count + 1) {
275  if (ctx->allocated_state_count == 0)
276  ctx->allocated_state_count = 256;
277  else
278  ctx->allocated_state_count *= 2;
279 
280  SCACTileReallocState(ctx, ctx->allocated_state_count);
281  }
282 
283  /* set all transitions for the newly assigned state as FAIL transitions */
284  for (aa = 0; aa < ctx->alphabet_size; aa++) {
285  ctx->goto_table[ctx->state_count][aa] = SC_AC_TILE_FAIL;
286  }
287 
288  memset(ctx->output_table + ctx->state_count, 0,
289  sizeof(SCACTileOutputTable));
290 
291  return ctx->state_count++;
292 }
293 
294 /**
295  * \internal
296  * \brief Adds a pid to the output table for a state.
297  *
298  * \param state The state to whose output table we should add the pid.
299  * \param pid The pattern id to add.
300  * \param mpm_ctx Pointer to the mpm context.
301  */
302 static void SCACTileSetOutputState(int32_t state, MpmPatternIndex pindex, MpmCtx *mpm_ctx)
303 {
304  void *ptmp;
305  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
306  SCACTileCtx *ctx = search_ctx->init_ctx;
307 
308  SCACTileOutputTable *output_state = &ctx->output_table[state];
309  uint32_t i = 0;
310 
311  /* Don't add the pattern more than once to the same state. */
312  for (i = 0; i < output_state->no_of_entries; i++) {
313  if (output_state->patterns[i] == pindex)
314  return;
315  }
316 
317  /* Increase the size of the array of pids for this state and add
318  * the new pid. */
319  output_state->no_of_entries++;
320  ptmp = SCRealloc(output_state->patterns,
321  output_state->no_of_entries * sizeof(MpmPatternIndex));
322  if (ptmp == NULL) {
323  SCFree(output_state->patterns);
324  output_state->patterns = NULL;
325  FatalError("Error allocating memory");
326  }
327  output_state->patterns = ptmp;
328 
329  output_state->patterns[output_state->no_of_entries - 1] = pindex;
330 }
331 
332 /**
333  * \brief Helper function used by SCACTileCreateGotoTable. Adds a
334  * pattern to the goto table.
335  *
336  * \param pattern Pointer to the pattern.
337  * \param pattern_len Pattern length.
338  * \param pid The pattern id, that corresponds to this pattern. We
339  * need it to updated the output table for this pattern.
340  * \param mpm_ctx Pointer to the mpm context.
341  */
342 static void SCACTileEnter(uint8_t *pattern, uint16_t pattern_len,
343  MpmPatternIndex pindex, MpmCtx *mpm_ctx)
344 {
345  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
346  SCACTileCtx *ctx = search_ctx->init_ctx;
347 
348  int32_t state = 0;
349  int32_t newstate = 0;
350  int i = 0;
351  int p = 0;
352  int tc;
353 
354  /* Walk down the trie till we have a match for the pattern prefix */
355  state = 0;
356  for (i = 0; i < pattern_len; i++) {
357  tc = ctx->translate_table[pattern[i]];
358  if (ctx->goto_table[state][tc] == SC_AC_TILE_FAIL)
359  break;
360  state = ctx->goto_table[state][tc];
361  }
362 
363  /* Add the non-matching pattern suffix to the trie, from the last state
364  * we left off */
365  for (p = i; p < pattern_len; p++) {
366  newstate = SCACTileInitNewState(mpm_ctx);
367  tc = ctx->translate_table[pattern[p]];
368  ctx->goto_table[state][tc] = newstate;
369  state = newstate;
370  }
371 
372  /* Add this pattern id, to the output table of the last state, where the
373  * pattern ends in the trie */
374  SCACTileSetOutputState(state, pindex, mpm_ctx);
375 }
376 
377 /**
378  * \internal
379  * \brief Create the goto table.
380  *
381  * \param mpm_ctx Pointer to the mpm context.
382  */
383 static void SCACTileCreateGotoTable(MpmCtx *mpm_ctx)
384 {
385  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
386  SCACTileCtx *ctx = search_ctx->init_ctx;
387 
388  uint32_t i = 0;
389 
390  /* add each pattern to create the goto table */
391  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
392  SCACTileEnter(ctx->parray[i]->ci, ctx->parray[i]->len,
393  i, mpm_ctx);
394  }
395 
396  int aa = 0;
397  for (aa = 0; aa < ctx->alphabet_size; aa++) {
398  if (ctx->goto_table[0][aa] == SC_AC_TILE_FAIL) {
399  ctx->goto_table[0][aa] = 0;
400  }
401  }
402 }
403 
404 static inline int SCACTileStateQueueIsEmpty(StateQueue *q)
405 {
406  if (q->top == q->bot)
407  return 1;
408  else
409  return 0;
410 }
411 
412 static inline void SCACTileEnqueue(StateQueue *q, int32_t state)
413 {
414  int i = 0;
415 
416  /*if we already have this */
417  for (i = q->bot; i < q->top; i++) {
418  if (q->store[i] == state)
419  return;
420  }
421 
422  q->store[q->top++] = state;
423 
425  q->top = 0;
426 
427  if (q->top == q->bot) {
428  FatalError("Just ran out of space in the queue. "
429  "Fatal Error. Exiting. Please file a bug report on this");
430  }
431 }
432 
433 static inline int32_t SCACTileDequeue(StateQueue *q)
434 {
436  q->bot = 0;
437 
438  if (q->bot == q->top) {
439  FatalError("StateQueue behaving weirdly. "
440  "Fatal Error. Exiting. Please file a bug report on this");
441  }
442 
443  return q->store[q->bot++];
444 }
445 
446 /**
447  * \internal
448  * \brief Club the output data from 2 states and store it in the 1st state.
449  * dst_state_data = {dst_state_data} UNION {src_state_data}
450  *
451  * \param dst_state First state(also the destination) for the union operation.
452  * \param src_state Second state for the union operation.
453  * \param mpm_ctx Pointer to the mpm context.
454  */
455 static void SCACTileClubOutputStates(int32_t dst_state,
456  int32_t src_state,
457  MpmCtx *mpm_ctx)
458 {
459  void *ptmp;
460  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
461  SCACTileCtx *ctx = search_ctx->init_ctx;
462 
463  uint32_t i = 0;
464  uint32_t j = 0;
465 
466  SCACTileOutputTable *output_dst_state = &ctx->output_table[dst_state];
467  SCACTileOutputTable *output_src_state = &ctx->output_table[src_state];
468 
469  for (i = 0; i < output_src_state->no_of_entries; i++) {
470  for (j = 0; j < output_dst_state->no_of_entries; j++) {
471  if (output_src_state->patterns[i] == output_dst_state->patterns[j]) {
472  break;
473  }
474  }
475  if (j == output_dst_state->no_of_entries) {
476  output_dst_state->no_of_entries++;
477 
478  ptmp = SCRealloc(output_dst_state->patterns,
479  (output_dst_state->no_of_entries * sizeof(uint32_t)));
480  if (ptmp == NULL) {
481  SCFree(output_dst_state->patterns);
482  output_dst_state->patterns = NULL;
483  FatalError("Error allocating memory");
484  }
485  output_dst_state->patterns = ptmp;
486 
487  output_dst_state->patterns[output_dst_state->no_of_entries - 1] =
488  output_src_state->patterns[i];
489  }
490  }
491 }
492 
493 /**
494  * \internal
495  * \brief Create the failure table.
496  *
497  * \param mpm_ctx Pointer to the mpm context.
498  */
499 static void SCACTileCreateFailureTable(MpmCtx *mpm_ctx)
500 {
501  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
502  SCACTileCtx *ctx = search_ctx->init_ctx;
503 
504  int aa = 0;
505  int32_t state = 0;
506  int32_t r_state = 0;
507 
508  StateQueue q;
509  memset(&q, 0, sizeof(StateQueue));
510 
511  /* Allocate space for the failure table. A failure entry in the table for
512  * every state(SCACTileCtx->state_count) */
513  ctx->failure_table = SCCalloc(ctx->state_count, sizeof(int32_t));
514  if (ctx->failure_table == NULL) {
515  FatalError("Error allocating memory");
516  }
517 
518  /* Add the failure transitions for the 0th state, and add every non-fail
519  * transition from the 0th state to the queue for further processing
520  * of failure states */
521  for (aa = 0; aa < ctx->alphabet_size; aa++) {
522  int32_t temp_state = ctx->goto_table[0][aa];
523  if (temp_state != 0) {
524  SCACTileEnqueue(&q, temp_state);
525  ctx->failure_table[temp_state] = 0;
526  }
527  }
528 
529  while (!SCACTileStateQueueIsEmpty(&q)) {
530  /* pick up every state from the queue and add failure transitions */
531  r_state = SCACTileDequeue(&q);
532  for (aa = 0; aa < ctx->alphabet_size; aa++) {
533  int32_t temp_state = ctx->goto_table[r_state][aa];
534  if (temp_state == SC_AC_TILE_FAIL)
535  continue;
536  SCACTileEnqueue(&q, temp_state);
537  state = ctx->failure_table[r_state];
538 
539  while(ctx->goto_table[state][aa] == SC_AC_TILE_FAIL)
540  state = ctx->failure_table[state];
541  ctx->failure_table[temp_state] = ctx->goto_table[state][aa];
542  SCACTileClubOutputStates(temp_state, ctx->failure_table[temp_state],
543  mpm_ctx);
544  }
545  }
546 }
547 
548 /*
549  * Set the next state for 1 byte next-state.
550  */
551 static void SCACTileSetState1Byte(SCACTileCtx *ctx, int state, int aa,
552  int next_state, int outputs)
553 {
554  uint8_t *state_table = (uint8_t*)ctx->state_table;
555  DEBUG_VALIDATE_BUG_ON(next_state < 0 || next_state > UINT8_MAX);
556  uint8_t encoded_next_state = (uint8_t)next_state;
557 
558  if (next_state == SC_AC_TILE_FAIL) {
559  FatalError("Error FAIL state in output");
560  }
561 
562  if (outputs == 0)
563  encoded_next_state |= (1 << 7);
564 
565  state_table[state * ctx->alphabet_storage + aa] = encoded_next_state;
566 }
567 
568 /*
569  * Set the next state for 2 byte next-state.
570  */
571 static void SCACTileSetState2Bytes(SCACTileCtx *ctx, int state, int aa,
572  int next_state, int outputs)
573 {
574  uint16_t *state_table = (uint16_t*)ctx->state_table;
575  DEBUG_VALIDATE_BUG_ON(next_state < 0 || next_state > UINT16_MAX);
576  uint16_t encoded_next_state = (uint16_t)next_state;
577 
578  if (next_state == SC_AC_TILE_FAIL) {
579  FatalError("Error FAIL state in output");
580  }
581 
582  if (outputs == 0)
583  encoded_next_state |= (1 << 15);
584 
585  state_table[state * ctx->alphabet_storage + aa] = encoded_next_state;
586 }
587 
588 /*
589  * Set the next state for 4 byte next-state.
590  */
591 static void SCACTileSetState4Bytes(SCACTileCtx *ctx, int state, int aa,
592  int next_state, int outputs)
593 {
594  uint32_t *state_table = (uint32_t*)ctx->state_table;
595  uint32_t encoded_next_state = next_state;
596 
597  if (next_state == SC_AC_TILE_FAIL) {
598  FatalError("Error FAIL state in output");
599  }
600 
601  if (outputs == 0)
602  encoded_next_state |= (1UL << 31);
603 
604  state_table[state * ctx->alphabet_storage + aa] = encoded_next_state;
605 }
606 
607 /**
608  * \internal
609  * \brief Create the delta table.
610  *
611  * \param mpm_ctx Pointer to the mpm context.
612  */
613 static inline void SCACTileCreateDeltaTable(MpmCtx *mpm_ctx)
614 {
615  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
616  SCACTileCtx *ctx = search_ctx->init_ctx;
617 
618  int aa = 0;
619  int32_t r_state = 0;
620 
621  if (ctx->state_count < 32767) {
622  if (ctx->state_count < 128) {
623  ctx->bytes_per_state = 1;
624  ctx->SetNextState = SCACTileSetState1Byte;
625 
626  switch(ctx->alphabet_storage) {
627  case 8:
628  ctx->Search = SCACTileSearchTiny8;
629  break;
630  case 16:
631  ctx->Search = SCACTileSearchTiny16;
632  break;
633  case 32:
634  ctx->Search = SCACTileSearchTiny32;
635  break;
636  case 64:
637  ctx->Search = SCACTileSearchTiny64;
638  break;
639  case 128:
640  ctx->Search = SCACTileSearchTiny128;
641  break;
642  default:
643  ctx->Search = SCACTileSearchTiny256;
644  }
645  } else {
646  /* 16-bit state needed */
647  ctx->bytes_per_state = 2;
648  ctx->SetNextState = SCACTileSetState2Bytes;
649 
650  switch(ctx->alphabet_storage) {
651  case 8:
652  ctx->Search = SCACTileSearchSmall8;
653  break;
654  case 16:
655  ctx->Search = SCACTileSearchSmall16;
656  break;
657  case 32:
658  ctx->Search = SCACTileSearchSmall32;
659  break;
660  case 64:
661  ctx->Search = SCACTileSearchSmall64;
662  break;
663  case 128:
664  ctx->Search = SCACTileSearchSmall128;
665  break;
666  default:
667  ctx->Search = SCACTileSearchSmall256;
668  }
669  }
670  } else {
671  /* 32-bit next state */
672  ctx->Search = SCACTileSearchLarge;
673  ctx->bytes_per_state = 4;
674  ctx->SetNextState = SCACTileSetState4Bytes;
675 
676  ctx->alphabet_storage = 256; /* Change? */
677  }
678 
679  StateQueue q;
680  memset(&q, 0, sizeof(StateQueue));
681 
682  for (aa = 0; aa < ctx->alphabet_size; aa++) {
683  int temp_state = ctx->goto_table[0][aa];
684  if (temp_state != 0)
685  SCACTileEnqueue(&q, temp_state);
686  }
687 
688  while (!SCACTileStateQueueIsEmpty(&q)) {
689  r_state = SCACTileDequeue(&q);
690 
691  for (aa = 0; aa < ctx->alphabet_size; aa++) {
692  int temp_state = ctx->goto_table[r_state][aa];
693  if (temp_state != SC_AC_TILE_FAIL) {
694  SCACTileEnqueue(&q, temp_state);
695  } else {
696  int f_state = ctx->failure_table[r_state];
697  ctx->goto_table[r_state][aa] = ctx->goto_table[f_state][aa];
698  }
699  }
700  }
701 }
702 
703 static void SCACTileClubOutputStatePresenceWithDeltaTable(MpmCtx *mpm_ctx)
704 {
705  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
706  SCACTileCtx *ctx = search_ctx->init_ctx;
707 
708  int aa = 0;
709  uint32_t state = 0;
710 
711  /* Allocate next-state table. */
712  int size = ctx->state_count * ctx->bytes_per_state * ctx->alphabet_storage;
713  void *state_table = SCCalloc(1, size);
714  if (unlikely(state_table == NULL)) {
715  FatalError("Error allocating memory");
716  }
717  ctx->state_table = state_table;
718 
719  mpm_ctx->memory_cnt++;
720  mpm_ctx->memory_size += size;
721 
722  SCLogDebug("Delta Table size %d, alphabet: %d, %d-byte states: %d",
723  size, ctx->alphabet_size, ctx->bytes_per_state, ctx->state_count);
724 
725  /* Copy next state from Goto table, which is 32 bits and encode it into the next
726  * state table, which can be 1, 2 or 4 bytes each and include if there is an
727  * output.
728  */
729  for (state = 0; state < ctx->state_count; state++) {
730  for (aa = 0; aa < ctx->alphabet_size; aa++) {
731  int next_state = ctx->goto_table[state][aa];
732  int next_state_outputs = ctx->output_table[next_state].no_of_entries;
733  ctx->SetNextState(ctx, state, aa, next_state, next_state_outputs);
734  }
735  }
736 }
737 
738 static inline void SCACTileInsertCaseSensitiveEntriesForPatterns(MpmCtx *mpm_ctx)
739 {
740  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
741  SCACTileCtx *ctx = search_ctx->init_ctx;
742 
743  uint32_t state = 0;
744  uint32_t k = 0;
745 
746  for (state = 0; state < ctx->state_count; state++) {
747  if (ctx->output_table[state].no_of_entries == 0)
748  continue;
749 
750  for (k = 0; k < ctx->output_table[state].no_of_entries; k++) {
751  if (ctx->pattern_list[ctx->output_table[state].patterns[k]].cs != NULL) {
752  /* TODO - Find better way to store this. */
753  ctx->output_table[state].patterns[k] &= 0x0FFFFFFF;
754  ctx->output_table[state].patterns[k] |= (uint32_t)1 << 31;
755  }
756  }
757  }
758 }
759 
760 #if 0
761 static void SCACTilePrintDeltaTable(MpmCtx *mpm_ctx)
762 {
763  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
764  SCACTileCtx *ctx = search_ctx->init_ctx;
765 
766  int i = 0, j = 0;
767 
768  printf("##############Delta Table##############\n");
769  for (i = 0; i < ctx->state_count; i++) {
770  printf("%d: \n", i);
771  for (j = 0; j < ctx->alphabet_size; j++) {
772  if (SCACTileGetDelta(i, j, mpm_ctx) != 0) {
773  printf(" %c -> %d\n", j, SCACTileGetDelta(i, j, mpm_ctx));
774  }
775  }
776  }
777 }
778 #endif
779 
780 /**
781  * \brief Process the patterns and prepare the state table.
782  *
783  * \param mpm_ctx Pointer to the mpm context.
784  */
785 static void SCACTilePrepareStateTable(MpmCtx *mpm_ctx)
786 {
787  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
788  SCACTileCtx *ctx = search_ctx->init_ctx;
789 
790  /* Create Alphabet compression and Lower Case translation table. */
791  SCACTileInitTranslateTable(ctx);
792 
793  /* create the 0th state in the goto table and output_table */
794  SCACTileInitNewState(mpm_ctx);
795 
796  /* create the goto table */
797  SCACTileCreateGotoTable(mpm_ctx);
798  /* create the failure table */
799  SCACTileCreateFailureTable(mpm_ctx);
800  /* create the final state(delta) table */
801  SCACTileCreateDeltaTable(mpm_ctx);
802  /* club the output state presence with delta transition entries */
803  SCACTileClubOutputStatePresenceWithDeltaTable(mpm_ctx);
804 
805  /* club nocase entries */
806  SCACTileInsertCaseSensitiveEntriesForPatterns(mpm_ctx);
807 
808 #if 0
809  SCACTilePrintDeltaTable(mpm_ctx);
810 #endif
811 
812  /* we don't need these anymore */
813  SCFree(ctx->goto_table);
814  ctx->goto_table = NULL;
815  SCFree(ctx->failure_table);
816  ctx->failure_table = NULL;
817 }
818 
819 
820 /**
821  * \brief Process Internal AC MPM tables to create the Search Context
822  *
823  * The search context is only the data needed to search the MPM.
824  *
825  * \param mpm_ctx Pointer to the mpm context.
826  */
827 static void SCACTilePrepareSearch(MpmCtx *mpm_ctx)
828 {
829  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
830  SCACTileCtx *ctx = search_ctx->init_ctx;
831 
832  /* Resize the output table to be only as big as its final size. */
833  SCACTileReallocOutputTable(ctx, ctx->state_count);
834 
835  search_ctx->Search = ctx->Search;
836  memcpy(search_ctx->translate_table, ctx->translate_table, sizeof(ctx->translate_table));
837 
838  /* Move the state table from the Init context */
839  search_ctx->state_table = ctx->state_table;
840  ctx->state_table = NULL; /* So that it won't get freed twice. */
841 
842  /* Move the output_table from the Init context to the Search Context */
843  /* TODO: Could be made more compact */
844  search_ctx->output_table = ctx->output_table;
845  ctx->output_table = NULL;
846  search_ctx->state_count = ctx->state_count;
847 
848  search_ctx->pattern_list = ctx->pattern_list;
849  ctx->pattern_list = NULL;
850  search_ctx->pattern_cnt = mpm_ctx->pattern_cnt;
851 
852  /* One bit per pattern, rounded up to the next byte size. */
853  search_ctx->mpm_bitarray_size = (mpm_ctx->pattern_cnt + 7) / 8;
854 
855  /* Can now free the Initialization data */
856  SCACTileDestroyInitCtx(mpm_ctx);
857 }
858 
859 /**
860  * \brief Process the patterns added to the mpm, and create the internal tables.
861  *
862  * \param mpm_conf Pointer to the generic MPM matcher configuration
863  * \param mpm_ctx Pointer to the mpm context.
864  */
865 int SCACTilePreparePatterns(MpmConfig *mpm_conf, MpmCtx *mpm_ctx)
866 {
867  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
868 
869  if (mpm_ctx->pattern_cnt == 0 || search_ctx->init_ctx == NULL) {
870  SCLogDebug("no patterns supplied to this mpm_ctx");
871  return 0;
872  }
873  SCACTileCtx *ctx = search_ctx->init_ctx;
874  if (mpm_ctx->init_hash == NULL) {
875  SCLogDebug("no patterns supplied to this mpm_ctx");
876  return 0;
877  }
878 
879  /* alloc the pattern array */
880  ctx->parray = (MpmPattern **)SCCalloc(mpm_ctx->pattern_cnt, sizeof(MpmPattern *));
881  if (ctx->parray == NULL)
882  goto error;
883 
884  /* populate it with the patterns in the hash */
885  uint32_t i = 0, p = 0;
886  for (i = 0; i < MPM_INIT_HASH_SIZE; i++) {
887  MpmPattern *node = mpm_ctx->init_hash[i], *nnode = NULL;
888  while(node != NULL) {
889  nnode = node->next;
890  node->next = NULL;
891  ctx->parray[p++] = node;
892  SCACTileHistogramAlphabet(ctx, node);
893  node = nnode;
894  }
895  }
896 
897  /* we no longer need the hash, so free it's memory */
898  SCFree(mpm_ctx->init_hash);
899  mpm_ctx->init_hash = NULL;
900 
901  /* Handle case patterns by storing a copy of the pattern to compare
902  * to each possible match (no-case).
903  *
904  * Allocate the memory for the array and each of the strings as one block.
905  */
906  size_t string_space_needed = 0;
907  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
908  if (!(ctx->parray[i]->flags & MPM_PATTERN_FLAG_NOCASE)) {
909  /* Round up to next 8 byte aligned length */
910  uint32_t space = ((ctx->parray[i]->len + 7) / 8) * 8;
911  string_space_needed += space;
912  }
913  }
914 
915  size_t pattern_list_size = mpm_ctx->pattern_cnt * sizeof(SCACTilePatternList);
916  size_t mem_size = string_space_needed + pattern_list_size;
917  void *mem_block = SCCalloc(1, mem_size);
918  if (mem_block == NULL) {
919  FatalError("Error allocating memory");
920  }
921  mpm_ctx->memory_cnt++;
922  mpm_ctx->memory_size += mem_size;
923  /* Split the allocated block into pattern list array and string space. */
924  ctx->pattern_list = mem_block;
925  uint8_t *string_space = mem_block + pattern_list_size;
926 
927  /* Now make the copies of the no-case strings. */
928  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
929  if (!(ctx->parray[i]->flags & MPM_PATTERN_FLAG_NOCASE)) {
930  uint16_t len = ctx->parray[i]->len;
931  uint32_t space = ((len + 7) / 8) * 8;
932  memcpy(string_space, ctx->parray[i]->original_pat, len);
933  ctx->pattern_list[i].cs = string_space;
934  ctx->pattern_list[i].patlen = len;
935  string_space += space;
936  }
937  ctx->pattern_list[i].offset = ctx->parray[i]->offset;
938  ctx->pattern_list[i].depth = ctx->parray[i]->depth;
939  ctx->pattern_list[i].pid = ctx->parray[i]->id;
940 
941  /* ACPatternList now owns this memory */
942  ctx->pattern_list[i].sids_size = ctx->parray[i]->sids_size;
943  ctx->pattern_list[i].sids = ctx->parray[i]->sids;
944  ctx->parray[i]->sids = NULL;
945  ctx->parray[i]->sids_size = 0;
946  }
947 
948  /* prepare the state table required by AC */
949  SCACTilePrepareStateTable(mpm_ctx);
950 
951  /* Convert to the Search Context structure */
952  SCACTilePrepareSearch(mpm_ctx);
953 
954  return 0;
955 
956 error:
957  return -1;
958 }
959 
960 /**
961  * \brief Initialize the AC context.
962  *
963  * \param mpm_ctx Mpm context.
964  */
965 void SCACTileInitCtx(MpmCtx *mpm_ctx)
966 {
967  if (mpm_ctx->ctx != NULL)
968  return;
969 
970  /* Search Context */
971  mpm_ctx->ctx = SCCalloc(1, sizeof(SCACTileSearchCtx));
972  if (mpm_ctx->ctx == NULL) {
973  exit(EXIT_FAILURE);
974  }
975 
976  mpm_ctx->memory_cnt++;
977  mpm_ctx->memory_size += sizeof(SCACTileSearchCtx);
978 
979  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
980 
981  /* MPM Creation context */
982  search_ctx->init_ctx = SCCalloc(1, sizeof(SCACTileCtx));
983  if (search_ctx->init_ctx == NULL) {
984  exit(EXIT_FAILURE);
985  }
986 
987  mpm_ctx->memory_cnt++;
988  mpm_ctx->memory_size += sizeof(SCACTileCtx);
989 
990  /* initialize the hash we use to speed up pattern insertions */
991  mpm_ctx->init_hash = SCCalloc(MPM_INIT_HASH_SIZE, sizeof(MpmPattern *));
992  if (mpm_ctx->init_hash == NULL) {
993  exit(EXIT_FAILURE);
994  }
995 
996  /* get conf values for AC from our yaml file. We have no conf values for
997  * now. We will certainly need this, as we develop the algo */
998  SCACTileGetConfig();
999 }
1000 
1001 static void SCACTileDestroyInitCtx(MpmCtx *mpm_ctx)
1002 {
1003  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
1004  SCACTileCtx *ctx = search_ctx->init_ctx;
1005 
1006  if (ctx == NULL)
1007  return;
1008 
1009  if (mpm_ctx->init_hash != NULL) {
1010  SCFree(mpm_ctx->init_hash);
1011  mpm_ctx->init_hash = NULL;
1012  }
1013 
1014  if (ctx->parray != NULL) {
1015  uint32_t i;
1016  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
1017  if (ctx->parray[i] != NULL) {
1018  MpmFreePattern(mpm_ctx, ctx->parray[i]);
1019  }
1020  }
1021 
1022  SCFree(ctx->parray);
1023  ctx->parray = NULL;
1024  }
1025 
1026  if (ctx->state_table != NULL) {
1027  SCFree(ctx->state_table);
1028 
1029  mpm_ctx->memory_cnt--;
1030  mpm_ctx->memory_size -= (ctx->state_count *
1031  ctx->bytes_per_state * ctx->alphabet_storage);
1032  }
1033 
1034  if (ctx->output_table != NULL) {
1035  uint32_t state;
1036  for (state = 0; state < ctx->state_count; state++) {
1037  if (ctx->output_table[state].patterns != NULL) {
1038  SCFree(ctx->output_table[state].patterns);
1039  }
1040  }
1041  SCFree(ctx->output_table);
1042  }
1043 
1044  if (ctx->pattern_list != NULL) {
1045  uint32_t i;
1046  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
1047  if (ctx->pattern_list[i].cs != NULL)
1048  SCFree(ctx->pattern_list[i].cs);
1049  if (ctx->pattern_list[i].sids != NULL)
1050  SCFree(ctx->pattern_list[i].sids);
1051  }
1052  SCFree(ctx->pattern_list);
1053  }
1054 
1055  SCFree(ctx);
1056  search_ctx->init_ctx = NULL;
1057  mpm_ctx->memory_cnt--;
1058  mpm_ctx->memory_size -= sizeof(SCACTileCtx);
1059 }
1060 
1061 /**
1062  * \brief Destroy the mpm context.
1063  *
1064  * \param mpm_ctx Pointer to the mpm context.
1065  */
1067 {
1068  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
1069  if (search_ctx == NULL)
1070  return;
1071 
1072  /* Destroy Initialization data */
1073  SCACTileDestroyInitCtx(mpm_ctx);
1074 
1075  /* Free Search tables */
1076  SCFree(search_ctx->state_table);
1077 
1078  if (search_ctx->pattern_list != NULL) {
1079  uint32_t i;
1080  for (i = 0; i < search_ctx->pattern_cnt; i++) {
1081  if (search_ctx->pattern_list[i].sids != NULL)
1082  SCFree(search_ctx->pattern_list[i].sids);
1083  }
1084  SCFree(search_ctx->pattern_list);
1085  }
1086 
1087  if (search_ctx->output_table != NULL) {
1088  uint32_t state;
1089  for (state = 0; state < search_ctx->state_count; state++) {
1090  if (search_ctx->output_table[state].patterns != NULL) {
1091  SCFree(search_ctx->output_table[state].patterns);
1092  }
1093  }
1094  SCFree(search_ctx->output_table);
1095  }
1096 
1097  SCFree(search_ctx);
1098  mpm_ctx->ctx = NULL;
1099 
1100  mpm_ctx->memory_cnt--;
1101  mpm_ctx->memory_size -= sizeof(SCACTileSearchCtx);
1102 }
1103 
1104 /*
1105  * Heavily optimized pattern matching routine for TILE-Gx.
1106  */
1107 
1108 #define SCHECK(x) ((x) > 0)
1109 #define BUF_TYPE int32_t
1110 // Extract byte N=0,1,2,3 from x
1111 #define BYTE0(x) (((x) & 0x000000ff) >> 0)
1112 #define BYTE1(x) (((x) & 0x0000ff00) >> 8)
1113 #define BYTE2(x) (((x) & 0x00ff0000) >> 16)
1114 #define BYTE3(x) (((x) & 0xff000000) >> 24)
1115 #define EXTRA 4 // need 4 extra bytes to avoid OOB reads
1117 static int CheckMatch(const SCACTileSearchCtx *ctx, PrefilterRuleStore *pmq,
1118  const uint8_t *buf, uint32_t buflen,
1119  uint16_t state, int i, int matches,
1120  uint8_t *mpm_bitarray)
1121 {
1122  const SCACTilePatternList *pattern_list = ctx->pattern_list;
1123  const uint8_t *buf_offset = buf + i + 1; // Lift out of loop
1124  uint32_t no_of_entries = ctx->output_table[state].no_of_entries;
1125  MpmPatternIndex *patterns = ctx->output_table[state].patterns;
1126  uint32_t k;
1127 
1128  for (k = 0; k < no_of_entries; k++) {
1129  MpmPatternIndex pindex = patterns[k] & 0x0FFFFFFF;
1130  if (mpm_bitarray[pindex / 8] & (1 << (pindex % 8))) {
1131  /* Pattern already seen by this MPM. */
1132  continue;
1133  }
1134  const SCACTilePatternList *pat = &pattern_list[pindex];
1135  const int offset = i - pat->patlen + 1;
1136  if (offset < (int)pat->offset || (pat->depth && i > pat->depth))
1137  continue;
1138 
1139  /* Double check case-sensitive match now. */
1140  if (patterns[k] >> 31) {
1141  const uint16_t patlen = pat->patlen;
1142  if (SCMemcmp(pat->cs, buf_offset - patlen, patlen) != 0) {
1143  /* Case-sensitive match failed. */
1144  continue;
1145  }
1146  }
1147  /* New match found */
1148  mpm_bitarray[pindex / 8] |= (1 << (pindex % 8));
1149 
1150  /* Always add the Signature IDs, since they could be different in the current MPM
1151  * than in a previous MPM on the same PMQ when finding the same pattern.
1152  */
1153  PrefilterAddSids(pmq, pattern_list[pindex].sids,
1154  pattern_list[pindex].sids_size);
1155  matches++;
1156  }
1157 
1158  return matches;
1159 }
1160 
1161 /**
1162  * \brief The aho corasick search function.
1163  *
1164  * \param mpm_ctx Pointer to the mpm context.
1165  * \param mpm_thread_ctx Pointer to the mpm thread context.
1166  * \param pmq Pointer to the Pattern Matcher Queue to hold
1167  * search matches.
1168  * \param buf Buffer to be searched.
1169  * \param buflen Buffer length.
1170  *
1171  * \retval matches Match count.
1172  */
1173 uint32_t SCACTileSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx,
1174  PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
1175 {
1176  const SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
1177 
1178  if (buflen == 0)
1179  return 0;
1180 
1181  /* Context specific matching function. */
1182  return search_ctx->Search(search_ctx, mpm_thread_ctx, pmq, buf, buflen);
1183 }
1184 
1185 /* This function handles (ctx->state_count >= 32767) */
1186 uint32_t SCACTileSearchLarge(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
1187  PrefilterRuleStore *pmq,
1188  const uint8_t *buf, uint32_t buflen)
1189 {
1190  uint32_t i = 0;
1191  int matches = 0;
1192 
1193  uint8_t mpm_bitarray[ctx->mpm_bitarray_size];
1194  memset(mpm_bitarray, 0, ctx->mpm_bitarray_size);
1195 
1196  const uint8_t* restrict xlate = ctx->translate_table;
1197  register int state = 0;
1198  int32_t (*state_table_u32)[256] = ctx->state_table;
1199  for (i = 0; i < buflen; i++) {
1200  state = state_table_u32[state & 0x00FFFFFF][xlate[buf[i]]];
1201  if (SCHECK(state)) {
1202  DEBUG_VALIDATE_BUG_ON(state < 0 || state > UINT16_MAX);
1203  matches = CheckMatch(ctx, pmq, buf, buflen, (uint16_t)state, i, matches, mpm_bitarray);
1204  }
1205  } /* for (i = 0; i < buflen; i++) */
1206 
1207  return matches;
1208 }
1209 
1210 /*
1211  * Search with Alphabet size of 256 and 16-bit next-state entries.
1212  * Next state entry has MSB as "match" and 15 LSB bits as next-state index.
1213  */
1214 // y = 1<<log_mult * (x & (1<<width -1))
1215 #define SINDEX_INTERNAL(y, x, log_mult, width) \
1216  ((1<<log_mult) * (x & ((1<<width) - 1)))
1217 
1218 /* Type of next_state */
1219 #define STYPE int16_t
1220 #define SLOAD(x) *(STYPE * restrict)(x)
1222 #define FUNC_NAME SCACTileSearchSmall256
1223 // y = 256 * (x & 0x7FFF)
1224 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 8, 15)
1225 #include "util-mpm-ac-ks-small.c"
1226 
1227 /* Search with Alphabet size of 128 */
1228 #undef FUNC_NAME
1229 #undef SINDEX
1230 #define FUNC_NAME SCACTileSearchSmall128
1231 // y = 128 * (x & 0x7FFF)
1232 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 7, 15)
1233 #include "util-mpm-ac-ks-small.c"
1234 
1235 /* Search with Alphabet size of 64 */
1236 #undef FUNC_NAME
1237 #undef SINDEX
1238 #define FUNC_NAME SCACTileSearchSmall64
1239 // y = 64 * (x & 0x7FFF)
1240 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 6, 15)
1241 #include "util-mpm-ac-ks-small.c"
1242 
1243 /* Search with Alphabet size of 32 */
1244 #undef FUNC_NAME
1245 #undef SINDEX
1246 #define FUNC_NAME SCACTileSearchSmall32
1247 // y = 32 * (x & 0x7FFF)
1248 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 5, 15)
1249 #include "util-mpm-ac-ks-small.c"
1250 
1251 /* Search with Alphabet size of 16 */
1252 #undef FUNC_NAME
1253 #undef SINDEX
1254 #define FUNC_NAME SCACTileSearchSmall16
1255 // y = 16 * (x & 0x7FFF)
1256 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 4, 15)
1257 #include "util-mpm-ac-ks-small.c"
1258 
1259 /* Search with Alphabet size of 8 */
1260 #undef FUNC_NAME
1261 #undef SINDEX
1262 #define FUNC_NAME SCACTileSearchSmall8
1263 // y = 8 * (x & 0x7FFF)
1264 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 3, 15)
1265 #include "util-mpm-ac-ks-small.c"
1266 
1267 /*
1268  * Search with Alphabet size of 256 and 8-bit next-state entries.
1269  * Next state entry has MSB as "match" and 15 LSB bits as next-state index.
1270  */
1271 #undef STYPE
1272 #define STYPE int8_t
1274 #undef FUNC_NAME
1275 #undef SINDEX
1276 #define FUNC_NAME SCACTileSearchTiny256
1277 // y = 256 * (x & 0x7F)
1278 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 8, 7)
1279 #include "util-mpm-ac-ks-small.c"
1280 
1281 /* Search with Alphabet size of 128 */
1282 #undef FUNC_NAME
1283 #undef SINDEX
1284 #define FUNC_NAME SCACTileSearchTiny128
1285 // y = 128 * (x & 0x7F)
1286 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 7, 7)
1287 #include "util-mpm-ac-ks-small.c"
1288 
1289 /* Search with Alphabet size of 64 */
1290 #undef FUNC_NAME
1291 #undef SINDEX
1292 #define FUNC_NAME SCACTileSearchTiny64
1293 // y = 64 * (x & 0x7F)
1294 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 6, 7)
1295 #include "util-mpm-ac-ks-small.c"
1296 
1297 /* Search with Alphabet size of 32 */
1298 #undef FUNC_NAME
1299 #undef SINDEX
1300 #define FUNC_NAME SCACTileSearchTiny32
1301 // y = 32 * (x & 0x7F)
1302 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 5, 7)
1303 #include "util-mpm-ac-ks-small.c"
1304 
1305 /* Search with Alphabet size of 16 */
1306 #undef FUNC_NAME
1307 #undef SINDEX
1308 #define FUNC_NAME SCACTileSearchTiny16
1309 // y = 16 * (x & 0x7F)
1310 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 4, 7)
1311 #include "util-mpm-ac-ks-small.c"
1312 
1313 /* Search with Alphabet size of 8 */
1314 #undef FUNC_NAME
1315 #undef SINDEX
1316 #define FUNC_NAME SCACTileSearchTiny8
1317 // y = 8 * (x & 0x7F)
1318 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 3, 7)
1320 
1321 
1322 /**
1323  * \brief Add a case insensitive pattern. Although we have different calls for
1324  * adding case sensitive and insensitive patterns, we make a single call
1325  * for either case. No special treatment for either case.
1326  *
1327  * \param mpm_ctx Pointer to the mpm context.
1328  * \param pat The pattern to add.
1329  * \param patnen The pattern length.
1330  * \param offset Ignored.
1331  * \param depth Ignored.
1332  * \param pid The pattern id.
1333  * \param sid Ignored.
1334  * \param flags Flags associated with this pattern.
1335  *
1336  * \retval 0 On success.
1337  * \retval -1 On failure.
1338  */
1339 int SCACTileAddPatternCI(MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen,
1340  uint16_t offset, uint16_t depth, uint32_t pid,
1341  SigIntId sid, uint8_t flags)
1342 {
1344  return MpmAddPattern(mpm_ctx, pat, patlen, offset, depth,
1345  pid, sid, flags);
1346 }
1347 
1348 /**
1349  * \brief Add a case sensitive pattern. Although we have different calls for
1350  * adding case sensitive and insensitive patterns, we make a single call
1351  * for either case. No special treatment for either case.
1352  *
1353  * \param mpm_ctx Pointer to the mpm context.
1354  * \param pat The pattern to add.
1355  * \param patnen The pattern length.
1356  * \param offset Ignored.
1357  * \param depth Ignored.
1358  * \param pid The pattern id.
1359  * \param sid Ignored.
1360  * \param flags Flags associated with this pattern.
1361  *
1362  * \retval 0 On success.
1363  * \retval -1 On failure.
1364  */
1365 int SCACTileAddPatternCS(MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen,
1366  uint16_t offset, uint16_t depth, uint32_t pid,
1367  SigIntId sid, uint8_t flags)
1368 {
1369  return MpmAddPattern(mpm_ctx, pat, patlen, offset, depth,
1370  pid, sid, flags);
1371 }
1372 
1374 {
1375  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
1376  SCACTileCtx *ctx = search_ctx->init_ctx;
1377 
1378  printf("MPM AC Information:\n");
1379  printf("Memory allocs: %" PRIu32 "\n", mpm_ctx->memory_cnt);
1380  printf("Memory alloced: %" PRIu32 "\n", mpm_ctx->memory_size);
1381  printf(" Sizeof:\n");
1382  printf(" MpmCtx %" PRIuMAX "\n", (uintmax_t)sizeof(MpmCtx));
1383  printf(" SCACTileCtx: %" PRIuMAX "\n", (uintmax_t)sizeof(SCACTileCtx));
1384  printf(" MpmPattern %" PRIuMAX "\n", (uintmax_t)sizeof(MpmPattern));
1385  printf(" MpmPattern %" PRIuMAX "\n", (uintmax_t)sizeof(MpmPattern));
1386  printf("Unique Patterns: %" PRIu32 "\n", mpm_ctx->pattern_cnt);
1387  printf("Smallest: %" PRIu32 "\n", mpm_ctx->minlen);
1388  printf("Largest: %" PRIu32 "\n", mpm_ctx->maxlen);
1389  printf("Total states in the state table: %u\n", ctx->state_count);
1390  printf("\n");
1391 }
1392 
1393 /************************** Mpm Registration ***************************/
1394 
1395 /**
1396  * \brief Register the aho-corasick mpm 'ks' originally developed by
1397  * Ken Steele for Tilera Tile-Gx processor.
1398  */
1400 {
1401  mpm_table[MPM_AC_KS].name = "ac-ks";
1404  mpm_table[MPM_AC_KS].ConfigInit = NULL;
1413 #ifdef UNITTESTS
1414  mpm_table[MPM_AC_KS].RegisterUnittests = SCACTileRegisterTests;
1415 #endif
1417 }
1418 
1419 
1420 /*************************************Unittests********************************/
1421 
1422 #ifdef UNITTESTS
1423 #include "detect-engine-alert.h"
1424 
1425 static int SCACTileTest01(void)
1426 {
1427  int result = 0;
1428  MpmCtx mpm_ctx;
1429  MpmThreadCtx mpm_thread_ctx;
1430  PrefilterRuleStore pmq;
1431 
1432  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1433  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1434  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1435 
1436  /* 1 match */
1437  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1438  PmqSetup(&pmq);
1439 
1440  SCACTilePreparePatterns(NULL, &mpm_ctx);
1441 
1442  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1443 
1444  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1445  (uint8_t *)buf, strlen(buf));
1446 
1447  if (cnt == 1)
1448  result = 1;
1449  else
1450  printf("1 != %" PRIu32 " ",cnt);
1451 
1452  SCACTileDestroyCtx(&mpm_ctx);
1453  PmqFree(&pmq);
1454  return result;
1455 }
1456 
1457 static int SCACTileTest02(void)
1458 {
1459  int result = 0;
1460  MpmCtx mpm_ctx;
1461  MpmThreadCtx mpm_thread_ctx;
1462  PrefilterRuleStore pmq;
1463 
1464  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1465  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1466  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1467 
1468  /* 1 match */
1469  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abce", 4, 0, 0, 0, 0, 0);
1470  PmqSetup(&pmq);
1471 
1472  SCACTilePreparePatterns(NULL, &mpm_ctx);
1473 
1474  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1475  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1476  (uint8_t *)buf, strlen(buf));
1477 
1478  if (cnt == 0)
1479  result = 1;
1480  else
1481  printf("0 != %" PRIu32 " ",cnt);
1482 
1483  SCACTileDestroyCtx(&mpm_ctx);
1484  PmqFree(&pmq);
1485  return result;
1486 }
1487 
1488 static int SCACTileTest03(void)
1489 {
1490  int result = 0;
1491  MpmCtx mpm_ctx;
1492  MpmThreadCtx mpm_thread_ctx;
1493  PrefilterRuleStore pmq;
1494 
1495  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1496  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1497  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1498 
1499  /* 1 match */
1500  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1501  /* 1 match */
1502  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"bcde", 4, 0, 0, 1, 0, 0);
1503  /* 1 match */
1504  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"fghj", 4, 0, 0, 2, 0, 0);
1505  PmqSetup(&pmq);
1506 
1507  SCACTilePreparePatterns(NULL, &mpm_ctx);
1508 
1509  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1510  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1511  (uint8_t *)buf, strlen(buf));
1512 
1513  if (cnt == 3)
1514  result = 1;
1515  else
1516  printf("3 != %" PRIu32 " ",cnt);
1517 
1518  SCACTileDestroyCtx(&mpm_ctx);
1519  PmqFree(&pmq);
1520  return result;
1521 }
1522 
1523 static int SCACTileTest04(void)
1524 {
1525  int result = 0;
1526  MpmCtx mpm_ctx;
1527  MpmThreadCtx mpm_thread_ctx;
1528  PrefilterRuleStore pmq;
1529 
1530  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1531  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1532  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1533 
1534  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1535  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"bcdegh", 6, 0, 0, 1, 0, 0);
1536  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"fghjxyz", 7, 0, 0, 2, 0, 0);
1537  PmqSetup(&pmq);
1538 
1539  SCACTilePreparePatterns(NULL, &mpm_ctx);
1540 
1541  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1542  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1543  (uint8_t *)buf, strlen(buf));
1544 
1545  if (cnt == 1)
1546  result = 1;
1547  else
1548  printf("1 != %" PRIu32 " ",cnt);
1549 
1550  SCACTileDestroyCtx(&mpm_ctx);
1551  PmqFree(&pmq);
1552  return result;
1553 }
1554 
1555 static int SCACTileTest05(void)
1556 {
1557  int result = 0;
1558  MpmCtx mpm_ctx;
1559  MpmThreadCtx mpm_thread_ctx;
1560  PrefilterRuleStore pmq;
1561 
1562  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1563  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1564  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1565 
1566  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"ABCD", 4, 0, 0, 0, 0, 0);
1567  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"bCdEfG", 6, 0, 0, 1, 0, 0);
1568  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"fghJikl", 7, 0, 0, 2, 0, 0);
1569  PmqSetup(&pmq);
1570 
1571  SCACTilePreparePatterns(NULL, &mpm_ctx);
1572 
1573  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1574  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1575  (uint8_t *)buf, strlen(buf));
1576 
1577  if (cnt == 3)
1578  result = 1;
1579  else
1580  printf("3 != %" PRIu32 " ",cnt);
1581 
1582  SCACTileDestroyCtx(&mpm_ctx);
1583  PmqFree(&pmq);
1584  return result;
1585 }
1586 
1587 static int SCACTileTest06(void)
1588 {
1589  int result = 0;
1590  MpmCtx mpm_ctx;
1591  MpmThreadCtx mpm_thread_ctx;
1592  PrefilterRuleStore pmq;
1593 
1594  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1595  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1596  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1597 
1598  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1599  PmqSetup(&pmq);
1600 
1601  SCACTilePreparePatterns(NULL, &mpm_ctx);
1602 
1603  const char *buf = "abcd";
1604  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1605  (uint8_t *)buf, strlen(buf));
1606 
1607  if (cnt == 1)
1608  result = 1;
1609  else
1610  printf("1 != %" PRIu32 " ",cnt);
1611 
1612  SCACTileDestroyCtx(&mpm_ctx);
1613  PmqFree(&pmq);
1614  return result;
1615 }
1616 
1617 static int SCACTileTest07(void)
1618 {
1619  MpmCtx mpm_ctx;
1620  MpmThreadCtx mpm_thread_ctx;
1621  PrefilterRuleStore pmq;
1622 
1623  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1624  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1625  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1626 
1627  /* should match 30 times */
1628  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"A", 1, 0, 0, 0, 0, 0);
1629  /* should match 29 times */
1630  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 1, 0, 0);
1631  /* should match 28 times */
1632  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAA", 3, 0, 0, 2, 0, 0);
1633  /* 26 */
1634  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAA", 5, 0, 0, 3, 0, 0);
1635  /* 21 */
1636  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAAAAAAA", 10, 0, 0, 4, 0, 0);
1637  /* 1 */
1638  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
1639  30, 0, 0, 5, 0, 0);
1640  PmqSetup(&pmq);
1641  /* total matches: 135: 6 unique */
1642 
1643  SCACTilePreparePatterns(NULL, &mpm_ctx);
1644 
1645  const char *buf = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
1646  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1647  (uint8_t *)buf, strlen(buf));
1648  FAIL_IF_NOT(cnt == 6);
1649 
1650  SCACTileDestroyCtx(&mpm_ctx);
1651  PmqFree(&pmq);
1652  PASS;
1653 }
1654 
1655 static int SCACTileTest08(void)
1656 {
1657  int result = 0;
1658  MpmCtx mpm_ctx;
1659  MpmThreadCtx mpm_thread_ctx;
1660  PrefilterRuleStore pmq;
1661 
1662  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1663  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1664  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1665 
1666  /* 1 match */
1667  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1668  PmqSetup(&pmq);
1669 
1670  SCACTilePreparePatterns(NULL, &mpm_ctx);
1671 
1672  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1673  (uint8_t *)"a", 1);
1674 
1675  if (cnt == 0)
1676  result = 1;
1677  else
1678  printf("0 != %" PRIu32 " ",cnt);
1679 
1680  SCACTileDestroyCtx(&mpm_ctx);
1681  PmqFree(&pmq);
1682  return result;
1683 }
1684 
1685 static int SCACTileTest09(void)
1686 {
1687  int result = 0;
1688  MpmCtx mpm_ctx;
1689  MpmThreadCtx mpm_thread_ctx;
1690  PrefilterRuleStore pmq;
1691 
1692  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1693  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1694  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1695 
1696  /* 1 match */
1697  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"ab", 2, 0, 0, 0, 0, 0);
1698  PmqSetup(&pmq);
1699 
1700  SCACTilePreparePatterns(NULL, &mpm_ctx);
1701 
1702  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1703  (uint8_t *)"ab", 2);
1704 
1705  if (cnt == 1)
1706  result = 1;
1707  else
1708  printf("1 != %" PRIu32 " ",cnt);
1709 
1710  SCACTileDestroyCtx(&mpm_ctx);
1711  PmqFree(&pmq);
1712  return result;
1713 }
1714 
1715 static int SCACTileTest10(void)
1716 {
1717  int result = 0;
1718  MpmCtx mpm_ctx;
1719  MpmThreadCtx mpm_thread_ctx;
1720  PrefilterRuleStore pmq;
1721 
1722  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1723  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1724  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1725 
1726  /* 1 match */
1727  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcdefgh", 8, 0, 0, 0, 0, 0);
1728  PmqSetup(&pmq);
1729 
1730  SCACTilePreparePatterns(NULL, &mpm_ctx);
1731 
1732  const char *buf = "01234567890123456789012345678901234567890123456789"
1733  "01234567890123456789012345678901234567890123456789"
1734  "abcdefgh"
1735  "01234567890123456789012345678901234567890123456789"
1736  "01234567890123456789012345678901234567890123456789";
1737  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1738  (uint8_t *)buf, strlen(buf));
1739 
1740  if (cnt == 1)
1741  result = 1;
1742  else
1743  printf("1 != %" PRIu32 " ",cnt);
1744 
1745  SCACTileDestroyCtx(&mpm_ctx);
1746  PmqFree(&pmq);
1747  return result;
1748 }
1749 
1750 static int SCACTileTest11(void)
1751 {
1752  int result = 0;
1753  MpmCtx mpm_ctx;
1754  MpmThreadCtx mpm_thread_ctx;
1755  PrefilterRuleStore pmq;
1756 
1757  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1758  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1759  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1760 
1761  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"he", 2, 0, 0, 1, 0, 0) == -1)
1762  goto end;
1763  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"she", 3, 0, 0, 2, 0, 0) == -1)
1764  goto end;
1765  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"his", 3, 0, 0, 3, 0, 0) == -1)
1766  goto end;
1767  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"hers", 4, 0, 0, 4, 0, 0) == -1)
1768  goto end;
1769  PmqSetup(&pmq);
1770 
1771  if (SCACTilePreparePatterns(NULL, &mpm_ctx) == -1)
1772  goto end;
1773 
1774  result = 1;
1775 
1776  const char *buf = "he";
1777  result &= (SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1778  strlen(buf)) == 1);
1779  buf = "she";
1780  result &= (SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1781  strlen(buf)) == 2);
1782  buf = "his";
1783  result &= (SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1784  strlen(buf)) == 1);
1785  buf = "hers";
1786  result &= (SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1787  strlen(buf)) == 2);
1788 
1789  end:
1790  SCACTileDestroyCtx(&mpm_ctx);
1791  PmqFree(&pmq);
1792  return result;
1793 }
1794 
1795 static int SCACTileTest12(void)
1796 {
1797  int result = 0;
1798  MpmCtx mpm_ctx;
1799  MpmThreadCtx mpm_thread_ctx;
1800  PrefilterRuleStore pmq;
1801 
1802  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1803  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1804  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1805 
1806  /* 1 match */
1807  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"wxyz", 4, 0, 0, 0, 0, 0);
1808  /* 1 match */
1809  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"vwxyz", 5, 0, 0, 1, 0, 0);
1810  PmqSetup(&pmq);
1811 
1812  SCACTilePreparePatterns(NULL, &mpm_ctx);
1813 
1814  const char *buf = "abcdefghijklmnopqrstuvwxyz";
1815  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1816  (uint8_t *)buf, strlen(buf));
1817 
1818  if (cnt == 2)
1819  result = 1;
1820  else
1821  printf("2 != %" PRIu32 " ",cnt);
1822 
1823  SCACTileDestroyCtx(&mpm_ctx);
1824  PmqFree(&pmq);
1825  return result;
1826 }
1827 
1828 static int SCACTileTest13(void)
1829 {
1830  int result = 0;
1831  MpmCtx mpm_ctx;
1832  MpmThreadCtx mpm_thread_ctx;
1833  PrefilterRuleStore pmq;
1834 
1835  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1836  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1837  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1838 
1839  /* 1 match */
1840  const char pat[] = "abcdefghijklmnopqrstuvwxyzABCD";
1841  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1842  PmqSetup(&pmq);
1843 
1844  SCACTilePreparePatterns(NULL, &mpm_ctx);
1845 
1846  const char *buf = "abcdefghijklmnopqrstuvwxyzABCD";
1847  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1848  (uint8_t *)buf, strlen(buf));
1849 
1850  if (cnt == 1)
1851  result = 1;
1852  else
1853  printf("1 != %" PRIu32 " ",cnt);
1854 
1855  SCACTileDestroyCtx(&mpm_ctx);
1856  PmqFree(&pmq);
1857  return result;
1858 }
1859 
1860 static int SCACTileTest14(void)
1861 {
1862  int result = 0;
1863  MpmCtx mpm_ctx;
1864  MpmThreadCtx mpm_thread_ctx;
1865  PrefilterRuleStore pmq;
1866 
1867  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1868  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1869  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1870 
1871  /* 1 match */
1872  const char pat[] = "abcdefghijklmnopqrstuvwxyzABCDE";
1873  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1874  PmqSetup(&pmq);
1875 
1876  SCACTilePreparePatterns(NULL, &mpm_ctx);
1877 
1878  const char *buf = "abcdefghijklmnopqrstuvwxyzABCDE";
1879  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1880  (uint8_t *)buf, strlen(buf));
1881 
1882  if (cnt == 1)
1883  result = 1;
1884  else
1885  printf("1 != %" PRIu32 " ",cnt);
1886 
1887  SCACTileDestroyCtx(&mpm_ctx);
1888  PmqFree(&pmq);
1889  return result;
1890 }
1891 
1892 static int SCACTileTest15(void)
1893 {
1894  int result = 0;
1895  MpmCtx mpm_ctx;
1896  MpmThreadCtx mpm_thread_ctx;
1897  PrefilterRuleStore pmq;
1898 
1899  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1900  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1901  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1902 
1903  /* 1 match */
1904  const char pat[] = "abcdefghijklmnopqrstuvwxyzABCDEF";
1905  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1906  PmqSetup(&pmq);
1907 
1908  SCACTilePreparePatterns(NULL, &mpm_ctx);
1909 
1910  const char *buf = "abcdefghijklmnopqrstuvwxyzABCDEF";
1911  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1912  (uint8_t *)buf, strlen(buf));
1913 
1914  if (cnt == 1)
1915  result = 1;
1916  else
1917  printf("1 != %" PRIu32 " ",cnt);
1918 
1919  SCACTileDestroyCtx(&mpm_ctx);
1920  PmqFree(&pmq);
1921  return result;
1922 }
1923 
1924 static int SCACTileTest16(void)
1925 {
1926  int result = 0;
1927  MpmCtx mpm_ctx;
1928  MpmThreadCtx mpm_thread_ctx;
1929  PrefilterRuleStore pmq;
1930 
1931  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1932  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1933  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1934 
1935  /* 1 match */
1936  const char pat[] = "abcdefghijklmnopqrstuvwxyzABC";
1937  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1938  PmqSetup(&pmq);
1939 
1940  SCACTilePreparePatterns(NULL, &mpm_ctx);
1941 
1942  const char *buf = "abcdefghijklmnopqrstuvwxyzABC";
1943  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1944  (uint8_t *)buf, strlen(buf));
1945 
1946  if (cnt == 1)
1947  result = 1;
1948  else
1949  printf("1 != %" PRIu32 " ",cnt);
1950 
1951  SCACTileDestroyCtx(&mpm_ctx);
1952  PmqFree(&pmq);
1953  return result;
1954 }
1955 
1956 static int SCACTileTest17(void)
1957 {
1958  int result = 0;
1959  MpmCtx mpm_ctx;
1960  MpmThreadCtx mpm_thread_ctx;
1961  PrefilterRuleStore pmq;
1962 
1963  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1964  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1965  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1966 
1967  /* 1 match */
1968  const char pat[] = "abcdefghijklmnopqrstuvwxyzAB";
1969  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1970  PmqSetup(&pmq);
1971 
1972  SCACTilePreparePatterns(NULL, &mpm_ctx);
1973 
1974  const char *buf = "abcdefghijklmnopqrstuvwxyzAB";
1975  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1976  (uint8_t *)buf, strlen(buf));
1977 
1978  if (cnt == 1)
1979  result = 1;
1980  else
1981  printf("1 != %" PRIu32 " ",cnt);
1982 
1983  SCACTileDestroyCtx(&mpm_ctx);
1984  PmqFree(&pmq);
1985  return result;
1986 }
1987 
1988 static int SCACTileTest18(void)
1989 {
1990  int result = 0;
1991  MpmCtx mpm_ctx;
1992  MpmThreadCtx mpm_thread_ctx;
1993  PrefilterRuleStore pmq;
1994 
1995  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1996  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1997  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1998 
1999  /* 1 match */
2000  const char pat[] = "abcde"
2001  "fghij"
2002  "klmno"
2003  "pqrst"
2004  "uvwxy"
2005  "z";
2006  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
2007  PmqSetup(&pmq);
2008 
2009  SCACTilePreparePatterns(NULL, &mpm_ctx);
2010 
2011  const char *buf = "abcde""fghij""klmno""pqrst""uvwxy""z";
2012  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2013  (uint8_t *)buf, strlen(buf));
2014 
2015  if (cnt == 1)
2016  result = 1;
2017  else
2018  printf("1 != %" PRIu32 " ",cnt);
2019 
2020  SCACTileDestroyCtx(&mpm_ctx);
2021  PmqFree(&pmq);
2022  return result;
2023 }
2024 
2025 static int SCACTileTest19(void)
2026 {
2027  int result = 0;
2028  MpmCtx mpm_ctx;
2029  MpmThreadCtx mpm_thread_ctx;
2030  PrefilterRuleStore pmq;
2031 
2032  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2033  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2034  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2035 
2036  /* 1 */
2037  const char pat[] = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
2038  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
2039  PmqSetup(&pmq);
2040 
2041  SCACTilePreparePatterns(NULL, &mpm_ctx);
2042 
2043  const char *buf = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
2044  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2045  (uint8_t *)buf, strlen(buf));
2046 
2047  if (cnt == 1)
2048  result = 1;
2049  else
2050  printf("1 != %" PRIu32 " ",cnt);
2051 
2052  SCACTileDestroyCtx(&mpm_ctx);
2053  PmqFree(&pmq);
2054  return result;
2055 }
2056 
2057 static int SCACTileTest20(void)
2058 {
2059  int result = 0;
2060  MpmCtx mpm_ctx;
2061  MpmThreadCtx mpm_thread_ctx;
2062  PrefilterRuleStore pmq;
2063 
2064  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2065  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2066  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2067 
2068  /* 1 */
2069  const char pat[] = "AAAAA"
2070  "AAAAA"
2071  "AAAAA"
2072  "AAAAA"
2073  "AAAAA"
2074  "AAAAA"
2075  "AA";
2076  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
2077  PmqSetup(&pmq);
2078 
2079  SCACTilePreparePatterns(NULL, &mpm_ctx);
2080 
2081  const char *buf = "AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AA";
2082  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2083  (uint8_t *)buf, strlen(buf));
2084 
2085  if (cnt == 1)
2086  result = 1;
2087  else
2088  printf("1 != %" PRIu32 " ",cnt);
2089 
2090  SCACTileDestroyCtx(&mpm_ctx);
2091  PmqFree(&pmq);
2092  return result;
2093 }
2094 
2095 static int SCACTileTest21(void)
2096 {
2097  int result = 0;
2098  MpmCtx mpm_ctx;
2099  MpmThreadCtx mpm_thread_ctx;
2100  PrefilterRuleStore pmq;
2101 
2102  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2103  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2104  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2105 
2106  /* 1 */
2107  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2108  PmqSetup(&pmq);
2109 
2110  SCACTilePreparePatterns(NULL, &mpm_ctx);
2111 
2112  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2113  (uint8_t *)"AA", 2);
2114 
2115  if (cnt == 1)
2116  result = 1;
2117  else
2118  printf("1 != %" PRIu32 " ",cnt);
2119 
2120  SCACTileDestroyCtx(&mpm_ctx);
2121  PmqFree(&pmq);
2122  return result;
2123 }
2124 
2125 static int SCACTileTest22(void)
2126 {
2127  int result = 0;
2128  MpmCtx mpm_ctx;
2129  MpmThreadCtx mpm_thread_ctx;
2130  PrefilterRuleStore pmq;
2131 
2132  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2133  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2134  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2135 
2136  /* 1 match */
2137  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
2138  /* 1 match */
2139  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcde", 5, 0, 0, 1, 0, 0);
2140  PmqSetup(&pmq);
2141 
2142  SCACTilePreparePatterns(NULL, &mpm_ctx);
2143 
2144  const char *buf = "abcdefghijklmnopqrstuvwxyz";
2145  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2146  (uint8_t *)buf, strlen(buf));
2147 
2148  if (cnt == 2)
2149  result = 1;
2150  else
2151  printf("2 != %" PRIu32 " ",cnt);
2152 
2153  SCACTileDestroyCtx(&mpm_ctx);
2154  PmqFree(&pmq);
2155  return result;
2156 }
2157 
2158 static int SCACTileTest23(void)
2159 {
2160  int result = 0;
2161  MpmCtx mpm_ctx;
2162  MpmThreadCtx mpm_thread_ctx;
2163  PrefilterRuleStore pmq;
2164 
2165  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2166  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2167  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2168 
2169  /* 1 */
2170  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2171  PmqSetup(&pmq);
2172 
2173  SCACTilePreparePatterns(NULL, &mpm_ctx);
2174 
2175  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2176  (uint8_t *)"aa", 2);
2177 
2178  if (cnt == 0)
2179  result = 1;
2180  else
2181  printf("1 != %" PRIu32 " ",cnt);
2182 
2183  SCACTileDestroyCtx(&mpm_ctx);
2184  PmqFree(&pmq);
2185  return result;
2186 }
2187 
2188 static int SCACTileTest24(void)
2189 {
2190  int result = 0;
2191  MpmCtx mpm_ctx;
2192  MpmThreadCtx mpm_thread_ctx;
2193  PrefilterRuleStore pmq;
2194 
2195  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2196  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2197  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2198 
2199  /* 1 */
2200  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2201  PmqSetup(&pmq);
2202 
2203  SCACTilePreparePatterns(NULL, &mpm_ctx);
2204 
2205  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2206  (uint8_t *)"aa", 2);
2207 
2208  if (cnt == 1)
2209  result = 1;
2210  else
2211  printf("1 != %" PRIu32 " ",cnt);
2212 
2213  SCACTileDestroyCtx(&mpm_ctx);
2214  PmqFree(&pmq);
2215  return result;
2216 }
2217 
2218 static int SCACTileTest25(void)
2219 {
2220  int result = 0;
2221  MpmCtx mpm_ctx;
2222  MpmThreadCtx mpm_thread_ctx;
2223  PrefilterRuleStore pmq;
2224 
2225  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2226  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2227  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2228 
2229  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"ABCD", 4, 0, 0, 0, 0, 0);
2230  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"bCdEfG", 6, 0, 0, 1, 0, 0);
2231  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"fghiJkl", 7, 0, 0, 2, 0, 0);
2232  PmqSetup(&pmq);
2233 
2234  SCACTilePreparePatterns(NULL, &mpm_ctx);
2235 
2236  const char *buf = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2237  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2238  (uint8_t *)buf, strlen(buf));
2239 
2240  if (cnt == 3)
2241  result = 1;
2242  else
2243  printf("3 != %" PRIu32 " ",cnt);
2244 
2245  SCACTileDestroyCtx(&mpm_ctx);
2246  PmqFree(&pmq);
2247  return result;
2248 }
2249 
2250 static int SCACTileTest26(void)
2251 {
2252  int result = 0;
2253  MpmCtx mpm_ctx;
2254  MpmThreadCtx mpm_thread_ctx;
2255  PrefilterRuleStore pmq;
2256 
2257  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2258  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2259  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2260 
2261  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"Works", 5, 0, 0, 0, 0, 0);
2262  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"Works", 5, 0, 0, 1, 0, 0);
2263  PmqSetup(&pmq);
2264 
2265  SCACTilePreparePatterns(NULL, &mpm_ctx);
2266 
2267  const char *buf = "works";
2268  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2269  (uint8_t *)buf, strlen(buf));
2270 
2271  if (cnt == 1)
2272  result = 1;
2273  else
2274  printf("3 != %" PRIu32 " ",cnt);
2275 
2276  SCACTileDestroyCtx(&mpm_ctx);
2277  PmqFree(&pmq);
2278  return result;
2279 }
2280 
2281 static int SCACTileTest27(void)
2282 {
2283  int result = 0;
2284  MpmCtx mpm_ctx;
2285  MpmThreadCtx mpm_thread_ctx;
2286  PrefilterRuleStore pmq;
2287 
2288  memset(&mpm_ctx, 0, sizeof(MpmCtx));
2289  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2290  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2291 
2292  /* 0 match */
2293  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"ONE", 3, 0, 0, 0, 0, 0);
2294  PmqSetup(&pmq);
2295 
2296  SCACTilePreparePatterns(NULL, &mpm_ctx);
2297 
2298  const char *buf = "tone";
2299  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2300  (uint8_t *)buf, strlen(buf));
2301 
2302  if (cnt == 0)
2303  result = 1;
2304  else
2305  printf("0 != %" PRIu32 " ",cnt);
2306 
2307  SCACTileDestroyCtx(&mpm_ctx);
2308  PmqFree(&pmq);
2309  return result;
2310 }
2311 
2312 static int SCACTileTest28(void)
2313 {
2314  int result = 0;
2315  MpmCtx mpm_ctx;
2316  MpmThreadCtx mpm_thread_ctx;
2317  PrefilterRuleStore pmq;
2318 
2319  memset(&mpm_ctx, 0, sizeof(MpmCtx));
2320  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2321  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2322 
2323  /* 0 match */
2324  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"one", 3, 0, 0, 0, 0, 0);
2325  PmqSetup(&pmq);
2326 
2327  SCACTilePreparePatterns(NULL, &mpm_ctx);
2328 
2329  const char *buf = "tONE";
2330  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2331  (uint8_t *)buf, strlen(buf));
2332 
2333  if (cnt == 0)
2334  result = 1;
2335  else
2336  printf("0 != %" PRIu32 " ",cnt);
2337 
2338  SCACTileDestroyCtx(&mpm_ctx);
2339  PmqFree(&pmq);
2340  return result;
2341 }
2342 
2343 static int SCACTileTest29(void)
2344 {
2345  uint8_t buf[] = "onetwothreefourfivesixseveneightnine";
2346  uint16_t buflen = sizeof(buf) - 1;
2347  Packet *p = NULL;
2348  ThreadVars th_v;
2349  DetectEngineThreadCtx *det_ctx = NULL;
2350  int result = 0;
2351 
2352  memset(&th_v, 0, sizeof(th_v));
2353  p = UTHBuildPacket(buf, buflen, IPPROTO_TCP);
2354 
2356  if (de_ctx == NULL)
2357  goto end;
2358 
2359  de_ctx->flags |= DE_QUIET;
2360 
2361  de_ctx->sig_list = SigInit(de_ctx, "alert tcp any any -> any any "
2362  "(content:\"onetwothreefourfivesixseveneightnine\"; sid:1;)");
2363  if (de_ctx->sig_list == NULL)
2364  goto end;
2365  de_ctx->sig_list->next = SigInit(de_ctx, "alert tcp any any -> any any "
2366  "(content:\"onetwothreefourfivesixseveneightnine\"; fast_pattern:3,3; sid:2;)");
2367  if (de_ctx->sig_list->next == NULL)
2368  goto end;
2369 
2371  DetectEngineThreadCtxInit(&th_v, (void *)de_ctx, (void *)&det_ctx);
2372 
2373  SigMatchSignatures(&th_v, de_ctx, det_ctx, p);
2374  if (PacketAlertCheck(p, 1) != 1) {
2375  printf("if (PacketAlertCheck(p, 1) != 1) failure\n");
2376  goto end;
2377  }
2378  if (PacketAlertCheck(p, 2) != 1) {
2379  printf("if (PacketAlertCheck(p, 1) != 2) failure\n");
2380  goto end;
2381  }
2382 
2383  result = 1;
2384 end:
2385  if (de_ctx != NULL) {
2388 
2389  DetectEngineThreadCtxDeinit(&th_v, (void *)det_ctx);
2391  }
2392 
2393  UTHFreePackets(&p, 1);
2394  return result;
2395 }
2396 
2397 void SCACTileRegisterTests(void)
2398 {
2399  UtRegisterTest("SCACTileTest01", SCACTileTest01);
2400  UtRegisterTest("SCACTileTest02", SCACTileTest02);
2401  UtRegisterTest("SCACTileTest03", SCACTileTest03);
2402  UtRegisterTest("SCACTileTest04", SCACTileTest04);
2403  UtRegisterTest("SCACTileTest05", SCACTileTest05);
2404  UtRegisterTest("SCACTileTest06", SCACTileTest06);
2405  UtRegisterTest("SCACTileTest07", SCACTileTest07);
2406  UtRegisterTest("SCACTileTest08", SCACTileTest08);
2407  UtRegisterTest("SCACTileTest09", SCACTileTest09);
2408  UtRegisterTest("SCACTileTest10", SCACTileTest10);
2409  UtRegisterTest("SCACTileTest11", SCACTileTest11);
2410  UtRegisterTest("SCACTileTest12", SCACTileTest12);
2411  UtRegisterTest("SCACTileTest13", SCACTileTest13);
2412  UtRegisterTest("SCACTileTest14", SCACTileTest14);
2413  UtRegisterTest("SCACTileTest15", SCACTileTest15);
2414  UtRegisterTest("SCACTileTest16", SCACTileTest16);
2415  UtRegisterTest("SCACTileTest17", SCACTileTest17);
2416  UtRegisterTest("SCACTileTest18", SCACTileTest18);
2417  UtRegisterTest("SCACTileTest19", SCACTileTest19);
2418  UtRegisterTest("SCACTileTest20", SCACTileTest20);
2419  UtRegisterTest("SCACTileTest21", SCACTileTest21);
2420  UtRegisterTest("SCACTileTest22", SCACTileTest22);
2421  UtRegisterTest("SCACTileTest23", SCACTileTest23);
2422  UtRegisterTest("SCACTileTest24", SCACTileTest24);
2423  UtRegisterTest("SCACTileTest25", SCACTileTest25);
2424  UtRegisterTest("SCACTileTest26", SCACTileTest26);
2425  UtRegisterTest("SCACTileTest27", SCACTileTest27);
2426  UtRegisterTest("SCACTileTest28", SCACTileTest28);
2427  UtRegisterTest("SCACTileTest29", SCACTileTest29);
2428 }
2429 #endif
2430 
2431 #else /* we're big endian */
2432 
2433 void MpmACTileRegister(void)
2434 {
2435  /* no-op on big endian */
2436 }
2437 
2438 #endif /* little endian check */
SCACTileSearchCtx
struct SCACTileSearchCtx_ SCACTileSearchCtx
len
uint8_t len
Definition: app-layer-dnp3.h:2
detect-engine.h
SCACTileSearchCtx_
Definition: util-mpm-ac-ks.h:115
MpmPatternIndex
uint32_t MpmPatternIndex
Definition: util-mpm.h:44
offset
uint64_t offset
Definition: util-streaming-buffer.h:0
MpmThreadCtx_
Definition: util-mpm.h:46
MPM_AC_KS
@ MPM_AC_KS
Definition: util-mpm.h:37
SCACTileSearchSmall256
uint32_t SCACTileSearchSmall256(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
unlikely
#define unlikely(expr)
Definition: util-optimize.h:35
MpmFreePattern
void MpmFreePattern(MpmCtx *mpm_ctx, MpmPattern *p)
Definition: util-mpm.c:356
SCACTileSearchCtx_::Search
uint32_t(* Search)(const struct SCACTileSearchCtx_ *ctx, struct MpmThreadCtx_ *, PrefilterRuleStore *, const uint8_t *, uint32_t)
Definition: util-mpm-ac-ks.h:122
UtRegisterTest
void UtRegisterTest(const char *name, int(*TestFn)(void))
Register unit test.
Definition: util-unittest.c:103
MpmTableElmt_::name
const char * name
Definition: util-mpm.h:151
STATE_QUEUE_CONTAINER_SIZE
#define STATE_QUEUE_CONTAINER_SIZE
Definition: util-mpm-ac-ks.c:150
PrefilterRuleStore_
structure for storing potential rule matches
Definition: util-prefilter.h:34
SCLogDebug
#define SCLogDebug(...)
Definition: util-debug.h:269
util-mpm-ac-ks.h
SCACTileSearchSmall32
uint32_t SCACTileSearchSmall32(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
PacketAlertCheck
int PacketAlertCheck(Packet *p, uint32_t sid)
Check if a certain sid alerted, this is used in the test functions.
Definition: detect-engine-alert.c:141
StateQueue_
Helper structure used by AC during state table creation.
Definition: util-mpm-ac-ks.c:155
SC_AC_TILE_FAIL
#define SC_AC_TILE_FAIL
Definition: util-mpm-ac-ks.c:148
ctx
struct Thresholds ctx
SCACTilePatternList_::offset
uint16_t offset
Definition: util-mpm-ac-ks.h:33
DetectEngineCtx_
main detection engine ctx
Definition: detect.h:860
MPM_FEATURE_FLAG_OFFSET
#define MPM_FEATURE_FLAG_OFFSET
Definition: util-mpm.h:147
util-memcpy.h
MpmCtx_::memory_size
uint32_t memory_size
Definition: util-mpm.h:108
DetectEngineCtxFree
void DetectEngineCtxFree(DetectEngineCtx *)
Free a DetectEngineCtx::
Definition: detect-engine.c:2742
SCACTileSearchTiny8
uint32_t SCACTileSearchTiny8(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
SCACTileOutputTable
struct SCACTileOutputTable_ SCACTileOutputTable
MpmTableElmt_::AddPatternNocase
int(* AddPatternNocase)(struct MpmCtx_ *, uint8_t *, uint16_t, uint16_t, uint16_t, uint32_t, SigIntId, uint8_t)
Definition: util-mpm.h:173
SCACTileSearchCtx_::output_table
SCACTileOutputTable * output_table
Definition: util-mpm-ac-ks.h:132
SCACTileSearchSmall128
uint32_t SCACTileSearchSmall128(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
DE_QUIET
#define DE_QUIET
Definition: detect.h:324
MpmCtx_::maxlen
uint16_t maxlen
Definition: util-mpm.h:105
MpmTableElmt_::AddPattern
int(* AddPattern)(struct MpmCtx_ *, uint8_t *, uint16_t, uint16_t, uint16_t, uint32_t, SigIntId, uint8_t)
Definition: util-mpm.h:172
UTHBuildPacket
Packet * UTHBuildPacket(uint8_t *payload, uint16_t payload_len, uint8_t ipproto)
UTHBuildPacket is a wrapper that build packets with default ip and port fields.
Definition: util-unittest-helper.c:359
MpmTableElmt_::feature_flags
uint8_t feature_flags
Definition: util-mpm.h:183
SigMatchSignatures
void SigMatchSignatures(ThreadVars *tv, DetectEngineCtx *de_ctx, DetectEngineThreadCtx *det_ctx, Packet *p)
wrapper for old tests
Definition: detect.c:1963
StateQueue
struct StateQueue_ StateQueue
Helper structure used by AC during state table creation.
SigCleanSignatures
void SigCleanSignatures(DetectEngineCtx *de_ctx)
Definition: detect-engine-build.c:55
SCACTileSearchCtx_::pattern_cnt
uint32_t pattern_cnt
Definition: util-mpm-ac-ks.h:141
SCACTileSearchCtx_::state_table
void * state_table
Definition: util-mpm-ac-ks.h:129
MpmTableElmt_::InitCtx
void(* InitCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:152
util-unittest.h
util-unittest-helper.h
FAIL_IF_NOT
#define FAIL_IF_NOT(expr)
Fail a test if expression evaluates to false.
Definition: util-unittest.h:82
SCHECK
#define SCHECK(x)
Definition: util-mpm-ac-ks.c:1108
util-memcmp.h
SCACTileSearchCtx_::state_count
uint32_t state_count
Definition: util-mpm-ac-ks.h:139
MpmInitCtx
void MpmInitCtx(MpmCtx *mpm_ctx, uint8_t matcher)
Definition: util-mpm.c:209
Signature_::next
struct Signature_ * next
Definition: detect.h:691
MpmTableElmt_::PrintCtx
void(* PrintCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:178
SCACTileOutputTable_
Definition: util-mpm-ac-ks.h:44
util-debug.h
SCACTileSearchTiny16
uint32_t SCACTileSearchTiny16(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
PASS
#define PASS
Pass the test.
Definition: util-unittest.h:105
MpmPattern_::next
struct MpmPattern_ * next
Definition: util-mpm.h:79
de_ctx
DetectEngineCtx * de_ctx
Definition: fuzz_siginit.c:18
DetectEngineThreadCtx_
Definition: detect.h:1116
SCACTileSearchCtx_::mpm_bitarray_size
uint32_t mpm_bitarray_size
Definition: util-mpm-ac-ks.h:136
SCACTileSearchSmall8
uint32_t SCACTileSearchSmall8(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
SCACTileOutputTable_::patterns
MpmPatternIndex * patterns
Definition: util-mpm-ac-ks.h:46
detect.h
ThreadVars_
Per thread variable structure.
Definition: threadvars.h:58
SCACTilePatternList
struct SCACTilePatternList_ SCACTilePatternList
util-mpm-ac-ks-small.c
DetectEngineThreadCtxInit
TmEcode DetectEngineThreadCtxInit(ThreadVars *tv, void *initdata, void **data)
initialize thread specific detection engine context
Definition: detect-engine.c:3475
MPM_FEATURE_FLAG_DEPTH
#define MPM_FEATURE_FLAG_DEPTH
Definition: util-mpm.h:146
SCACTileSearch
uint32_t SCACTileSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
The aho corasick search function.
Definition: util-mpm-ac-ks.c:1173
SigInit
Signature * SigInit(DetectEngineCtx *de_ctx, const char *sigstr)
Parses a signature and adds it to the Detection Engine Context.
Definition: detect-parse.c:2520
MpmCtx_::minlen
uint16_t minlen
Definition: util-mpm.h:104
SCACTileSearchCtx_::init_ctx
SCACTileCtx * init_ctx
Definition: util-mpm-ac-ks.h:144
SigGroupCleanup
int SigGroupCleanup(DetectEngineCtx *de_ctx)
Definition: detect-engine-build.c:2180
Packet_
Definition: decode.h:476
detect-engine-build.h
detect-engine-alert.h
conf.h
MPM_INIT_HASH_SIZE
#define MPM_INIT_HASH_SIZE
Definition: util-mpm.h:30
SCACTileSearchTiny128
uint32_t SCACTileSearchTiny128(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
MpmTableElmt_::CacheRuleset
int(* CacheRuleset)(MpmConfig *)
Definition: util-mpm.h:175
SCACTilePreparePatterns
int SCACTilePreparePatterns(MpmConfig *mpm_conf, MpmCtx *mpm_ctx)
Process the patterns added to the mpm, and create the internal tables.
Definition: util-mpm-ac-ks.c:865
SCACTilePatternList_::sids
SigIntId * sids
Definition: util-mpm-ac-ks.h:41
StateQueue_::bot
int bot
Definition: util-mpm-ac-ks.c:158
MpmPattern_
Definition: util-mpm.h:54
MpmTableElmt_::Search
uint32_t(* Search)(const struct MpmCtx_ *, struct MpmThreadCtx_ *, PrefilterRuleStore *, const uint8_t *, uint32_t)
Definition: util-mpm.h:177
MpmAddPatternCS
int MpmAddPatternCS(struct MpmCtx_ *mpm_ctx, uint8_t *pat, uint16_t patlen, uint16_t offset, uint16_t depth, uint32_t pid, SigIntId sid, uint8_t flags)
Definition: util-mpm.c:249
SCACTilePrintInfo
void SCACTilePrintInfo(MpmCtx *mpm_ctx)
Definition: util-mpm-ac-ks.c:1373
SCACTileSearchCtx_::pattern_list
SCACTilePatternList * pattern_list
Definition: util-mpm-ac-ks.h:133
SCACTileSearchTiny64
uint32_t SCACTileSearchTiny64(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
MpmACTileRegister
void MpmACTileRegister(void)
Register the aho-corasick mpm 'ks' originally developed by Ken Steele for Tilera Tile-Gx processor.
Definition: util-mpm-ac-ks.c:1399
SCACTilePatternList_::cs
uint8_t * cs
Definition: util-mpm-ac-ks.h:30
SigGroupBuild
int SigGroupBuild(DetectEngineCtx *de_ctx)
Convert the signature list into the runtime match structure.
Definition: detect-engine-build.c:2113
MpmPattern_::ci
uint8_t * ci
Definition: util-mpm.h:71
SCRealloc
#define SCRealloc(ptr, sz)
Definition: util-mem.h:50
MPM_PATTERN_FLAG_NOCASE
#define MPM_PATTERN_FLAG_NOCASE
Definition: util-mpm.h:136
cnt
uint32_t cnt
Definition: tmqh-packetpool.h:7
flags
uint8_t flags
Definition: decode-gre.h:0
SCACTilePatternList_::depth
uint16_t depth
Definition: util-mpm-ac-ks.h:34
suricata-common.h
MpmCtx_::pattern_cnt
uint32_t pattern_cnt
Definition: util-mpm.h:102
SCACTilePatternList_::patlen
uint16_t patlen
Definition: util-mpm-ac-ks.h:31
SCACTileSearchTiny256
uint32_t SCACTileSearchTiny256(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
SCACTileAddPatternCI
int SCACTileAddPatternCI(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t, uint32_t, SigIntId, uint8_t)
Add a case insensitive pattern. Although we have different calls for adding case sensitive and insens...
Definition: util-mpm-ac-ks.c:1339
DetectEngineThreadCtxDeinit
TmEcode DetectEngineThreadCtxDeinit(ThreadVars *tv, void *data)
Definition: detect-engine.c:3702
FatalError
#define FatalError(...)
Definition: util-debug.h:502
DetectEngineCtx_::sig_list
Signature * sig_list
Definition: detect.h:869
util-validate.h
SCACTileCtx
struct SCACTileCtx_ SCACTileCtx
SCACTileCtx_
Definition: util-mpm-ac-ks.h:54
SCACTilePatternList_
Definition: util-mpm-ac-ks.h:29
MpmTableElmt_::Prepare
int(* Prepare)(MpmConfig *, struct MpmCtx_ *)
Definition: util-mpm.h:174
MpmTableElmt_::DestroyCtx
void(* DestroyCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:154
SCFree
#define SCFree(p)
Definition: util-mem.h:61
MpmConfig_
Definition: util-mpm.h:89
detect-parse.h
MpmCtx_::memory_cnt
uint32_t memory_cnt
Definition: util-mpm.h:107
MpmCtx_::init_hash
MpmPattern ** init_hash
Definition: util-mpm.h:113
SCACTileInitCtx
void SCACTileInitCtx(MpmCtx *)
Initialize the AC context.
Definition: util-mpm-ac-ks.c:965
MpmPattern_::len
uint16_t len
Definition: util-mpm.h:56
DetectEngineCtxInit
DetectEngineCtx * DetectEngineCtxInit(void)
Definition: detect-engine.c:2703
mpm_table
MpmTableElmt mpm_table[MPM_TABLE_SIZE]
Definition: util-mpm.c:47
SCACTileSearchLarge
uint32_t SCACTileSearchLarge(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
Definition: util-mpm-ac-ks.c:1186
SCACTileDestroyCtx
void SCACTileDestroyCtx(MpmCtx *)
Destroy the mpm context.
Definition: util-mpm-ac-ks.c:1066
MpmTableElmt_::ConfigDeinit
void(* ConfigDeinit)(MpmConfig **)
Definition: util-mpm.h:158
suricata.h
MpmTableElmt_::ConfigCacheDirSet
void(* ConfigCacheDirSet)(MpmConfig *, const char *dir_path)
Definition: util-mpm.h:159
PmqFree
void PmqFree(PrefilterRuleStore *pmq)
Cleanup and free a Pmq.
Definition: util-prefilter.c:126
SCACTileSearchTiny32
uint32_t SCACTileSearchTiny32(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
MpmAddPattern
int MpmAddPattern(MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen, uint16_t offset, uint16_t depth, uint32_t pid, SigIntId sid, uint8_t flags)
Definition: util-mpm.c:438
MpmTableElmt_::ConfigInit
MpmConfig *(* ConfigInit)(void)
Definition: util-mpm.h:157
DetectEngineCtx_::flags
uint8_t flags
Definition: detect.h:862
MpmCtx_
Definition: util-mpm.h:93
SigIntId
#define SigIntId
Definition: suricata-common.h:324
SCCalloc
#define SCCalloc(nm, sz)
Definition: util-mem.h:53
SCACTileSearchCtx_::translate_table
uint8_t translate_table[256]
Definition: util-mpm-ac-ks.h:126
MpmCtx_::ctx
void * ctx
Definition: util-mpm.h:94
MpmAddPatternCI
int MpmAddPatternCI(struct MpmCtx_ *mpm_ctx, uint8_t *pat, uint16_t patlen, uint16_t offset, uint16_t depth, uint32_t pid, SigIntId sid, uint8_t flags)
Definition: util-mpm.c:258
SCACTileAddPatternCS
int SCACTileAddPatternCS(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t, uint32_t, SigIntId, uint8_t)
Add a case sensitive pattern. Although we have different calls for adding case sensitive and insensit...
Definition: util-mpm-ac-ks.c:1365
SCMemcmp
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:290
DEBUG_VALIDATE_BUG_ON
#define DEBUG_VALIDATE_BUG_ON(exp)
Definition: util-validate.h:102
MpmTableElmt_::RegisterUnittests
void(* RegisterUnittests)(void)
Definition: util-mpm.h:181
PmqSetup
int PmqSetup(PrefilterRuleStore *pmq)
Setup a pmq.
Definition: util-prefilter.c:37
SCACTileSearchSmall16
uint32_t SCACTileSearchSmall16(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
SCACTileSearchSmall64
uint32_t SCACTileSearchSmall64(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
StateQueue_::top
int top
Definition: util-mpm-ac-ks.c:157
StateQueue_::store
int32_t store[STATE_QUEUE_CONTAINER_SIZE]
Definition: util-mpm-ac-ks.c:156
UTHFreePackets
void UTHFreePackets(Packet **p, int numpkts)
UTHFreePackets: function to release the allocated data from UTHBuildPacket and the packet itself.
Definition: util-unittest-helper.c:450