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