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(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:
629  break;
630  case 16:
632  break;
633  case 32:
635  break;
636  case 64:
638  break;
639  case 128:
641  break;
642  default:
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:
653  break;
654  case 16:
656  break;
657  case 32:
659  break;
660  case 64:
662  break;
663  case 128:
665  break;
666  default:
668  }
669  }
670  } else {
671  /* 32-bit next state */
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_ctx Pointer to the mpm context.
863  */
865 {
866  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
867 
868  if (mpm_ctx->pattern_cnt == 0 || search_ctx->init_ctx == NULL) {
869  SCLogDebug("no patterns supplied to this mpm_ctx");
870  return 0;
871  }
872  SCACTileCtx *ctx = search_ctx->init_ctx;
873  if (mpm_ctx->init_hash == NULL) {
874  SCLogDebug("no patterns supplied to this mpm_ctx");
875  return 0;
876  }
877 
878  /* alloc the pattern array */
879  ctx->parray = (MpmPattern **)SCCalloc(mpm_ctx->pattern_cnt, sizeof(MpmPattern *));
880  if (ctx->parray == NULL)
881  goto error;
882 
883  /* populate it with the patterns in the hash */
884  uint32_t i = 0, p = 0;
885  for (i = 0; i < MPM_INIT_HASH_SIZE; i++) {
886  MpmPattern *node = mpm_ctx->init_hash[i], *nnode = NULL;
887  while(node != NULL) {
888  nnode = node->next;
889  node->next = NULL;
890  ctx->parray[p++] = node;
891  SCACTileHistogramAlphabet(ctx, node);
892  node = nnode;
893  }
894  }
895 
896  /* we no longer need the hash, so free it's memory */
897  SCFree(mpm_ctx->init_hash);
898  mpm_ctx->init_hash = NULL;
899 
900  /* Handle case patterns by storing a copy of the pattern to compare
901  * to each possible match (no-case).
902  *
903  * Allocate the memory for the array and each of the strings as one block.
904  */
905  size_t string_space_needed = 0;
906  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
907  if (!(ctx->parray[i]->flags & MPM_PATTERN_FLAG_NOCASE)) {
908  /* Round up to next 8 byte aligned length */
909  uint32_t space = ((ctx->parray[i]->len + 7) / 8) * 8;
910  string_space_needed += space;
911  }
912  }
913 
914  size_t pattern_list_size = mpm_ctx->pattern_cnt * sizeof(SCACTilePatternList);
915  size_t mem_size = string_space_needed + pattern_list_size;
916  void *mem_block = SCCalloc(1, mem_size);
917  if (mem_block == NULL) {
918  FatalError("Error allocating memory");
919  }
920  mpm_ctx->memory_cnt++;
921  mpm_ctx->memory_size += mem_size;
922  /* Split the allocated block into pattern list array and string space. */
923  ctx->pattern_list = mem_block;
924  uint8_t *string_space = mem_block + pattern_list_size;
925 
926  /* Now make the copies of the no-case strings. */
927  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
928  if (!(ctx->parray[i]->flags & MPM_PATTERN_FLAG_NOCASE)) {
929  uint16_t len = ctx->parray[i]->len;
930  uint32_t space = ((len + 7) / 8) * 8;
931  memcpy(string_space, ctx->parray[i]->original_pat, len);
932  ctx->pattern_list[i].cs = string_space;
933  ctx->pattern_list[i].patlen = len;
934  string_space += space;
935  }
936  ctx->pattern_list[i].offset = ctx->parray[i]->offset;
937  ctx->pattern_list[i].depth = ctx->parray[i]->depth;
938  ctx->pattern_list[i].pid = ctx->parray[i]->id;
939 
940  /* ACPatternList now owns this memory */
941  ctx->pattern_list[i].sids_size = ctx->parray[i]->sids_size;
942  ctx->pattern_list[i].sids = ctx->parray[i]->sids;
943  ctx->parray[i]->sids = NULL;
944  ctx->parray[i]->sids_size = 0;
945  }
946 
947  /* prepare the state table required by AC */
948  SCACTilePrepareStateTable(mpm_ctx);
949 
950  /* Convert to the Search Context structure */
951  SCACTilePrepareSearch(mpm_ctx);
952 
953  return 0;
954 
955 error:
956  return -1;
957 }
958 
959 /**
960  * \brief Initialize the AC context.
961  *
962  * \param mpm_ctx Mpm context.
963  */
964 void SCACTileInitCtx(MpmCtx *mpm_ctx)
965 {
966  if (mpm_ctx->ctx != NULL)
967  return;
968 
969  /* Search Context */
970  mpm_ctx->ctx = SCCalloc(1, sizeof(SCACTileSearchCtx));
971  if (mpm_ctx->ctx == NULL) {
972  exit(EXIT_FAILURE);
973  }
974 
975  mpm_ctx->memory_cnt++;
976  mpm_ctx->memory_size += sizeof(SCACTileSearchCtx);
977 
978  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
979 
980  /* MPM Creation context */
981  search_ctx->init_ctx = SCCalloc(1, sizeof(SCACTileCtx));
982  if (search_ctx->init_ctx == NULL) {
983  exit(EXIT_FAILURE);
984  }
985 
986  mpm_ctx->memory_cnt++;
987  mpm_ctx->memory_size += sizeof(SCACTileCtx);
988 
989  /* initialize the hash we use to speed up pattern insertions */
990  mpm_ctx->init_hash = SCCalloc(MPM_INIT_HASH_SIZE, sizeof(MpmPattern *));
991  if (mpm_ctx->init_hash == NULL) {
992  exit(EXIT_FAILURE);
993  }
994 
995  /* get conf values for AC from our yaml file. We have no conf values for
996  * now. We will certainly need this, as we develop the algo */
997  SCACTileGetConfig();
998 }
999 
1000 static void SCACTileDestroyInitCtx(MpmCtx *mpm_ctx)
1001 {
1002  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
1003  SCACTileCtx *ctx = search_ctx->init_ctx;
1004 
1005  if (ctx == NULL)
1006  return;
1007 
1008  if (mpm_ctx->init_hash != NULL) {
1009  SCFree(mpm_ctx->init_hash);
1010  mpm_ctx->init_hash = NULL;
1011  }
1012 
1013  if (ctx->parray != NULL) {
1014  uint32_t i;
1015  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
1016  if (ctx->parray[i] != NULL) {
1017  MpmFreePattern(mpm_ctx, ctx->parray[i]);
1018  }
1019  }
1020 
1021  SCFree(ctx->parray);
1022  ctx->parray = NULL;
1023  }
1024 
1025  if (ctx->state_table != NULL) {
1026  SCFree(ctx->state_table);
1027 
1028  mpm_ctx->memory_cnt--;
1029  mpm_ctx->memory_size -= (ctx->state_count *
1030  ctx->bytes_per_state * ctx->alphabet_storage);
1031  }
1032 
1033  if (ctx->output_table != NULL) {
1034  uint32_t state;
1035  for (state = 0; state < ctx->state_count; state++) {
1036  if (ctx->output_table[state].patterns != NULL) {
1037  SCFree(ctx->output_table[state].patterns);
1038  }
1039  }
1040  SCFree(ctx->output_table);
1041  }
1042 
1043  if (ctx->pattern_list != NULL) {
1044  uint32_t i;
1045  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
1046  if (ctx->pattern_list[i].cs != NULL)
1047  SCFree(ctx->pattern_list[i].cs);
1048  if (ctx->pattern_list[i].sids != NULL)
1049  SCFree(ctx->pattern_list[i].sids);
1050  }
1051  SCFree(ctx->pattern_list);
1052  }
1053 
1054  SCFree(ctx);
1055  search_ctx->init_ctx = NULL;
1056  mpm_ctx->memory_cnt--;
1057  mpm_ctx->memory_size -= sizeof(SCACTileCtx);
1058 }
1059 
1060 /**
1061  * \brief Destroy the mpm context.
1062  *
1063  * \param mpm_ctx Pointer to the mpm context.
1064  */
1066 {
1067  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
1068  if (search_ctx == NULL)
1069  return;
1070 
1071  /* Destroy Initialization data */
1072  SCACTileDestroyInitCtx(mpm_ctx);
1073 
1074  /* Free Search tables */
1075  SCFree(search_ctx->state_table);
1076 
1077  if (search_ctx->pattern_list != NULL) {
1078  uint32_t i;
1079  for (i = 0; i < search_ctx->pattern_cnt; i++) {
1080  if (search_ctx->pattern_list[i].sids != NULL)
1081  SCFree(search_ctx->pattern_list[i].sids);
1082  }
1083  SCFree(search_ctx->pattern_list);
1084  }
1085 
1086  if (search_ctx->output_table != NULL) {
1087  uint32_t state;
1088  for (state = 0; state < search_ctx->state_count; state++) {
1089  if (search_ctx->output_table[state].patterns != NULL) {
1090  SCFree(search_ctx->output_table[state].patterns);
1091  }
1092  }
1093  SCFree(search_ctx->output_table);
1094  }
1095 
1096  SCFree(search_ctx);
1097  mpm_ctx->ctx = NULL;
1098 
1099  mpm_ctx->memory_cnt--;
1100  mpm_ctx->memory_size -= sizeof(SCACTileSearchCtx);
1101 }
1102 
1103 /*
1104  * Heavily optimized pattern matching routine for TILE-Gx.
1105  */
1106 
1107 #define SCHECK(x) ((x) > 0)
1108 #define BUF_TYPE int32_t
1109 // Extract byte N=0,1,2,3 from x
1110 #define BYTE0(x) (((x) & 0x000000ff) >> 0)
1111 #define BYTE1(x) (((x) & 0x0000ff00) >> 8)
1112 #define BYTE2(x) (((x) & 0x00ff0000) >> 16)
1113 #define BYTE3(x) (((x) & 0xff000000) >> 24)
1114 #define EXTRA 4 // need 4 extra bytes to avoid OOB reads
1116 static int CheckMatch(const SCACTileSearchCtx *ctx, PrefilterRuleStore *pmq,
1117  const uint8_t *buf, uint32_t buflen,
1118  uint16_t state, int i, int matches,
1119  uint8_t *mpm_bitarray)
1120 {
1121  const SCACTilePatternList *pattern_list = ctx->pattern_list;
1122  const uint8_t *buf_offset = buf + i + 1; // Lift out of loop
1123  uint32_t no_of_entries = ctx->output_table[state].no_of_entries;
1124  MpmPatternIndex *patterns = ctx->output_table[state].patterns;
1125  uint32_t k;
1126 
1127  for (k = 0; k < no_of_entries; k++) {
1128  MpmPatternIndex pindex = patterns[k] & 0x0FFFFFFF;
1129  if (mpm_bitarray[pindex / 8] & (1 << (pindex % 8))) {
1130  /* Pattern already seen by this MPM. */
1131  continue;
1132  }
1133  const SCACTilePatternList *pat = &pattern_list[pindex];
1134  const int offset = i - pat->patlen + 1;
1135  if (offset < (int)pat->offset || (pat->depth && i > pat->depth))
1136  continue;
1137 
1138  /* Double check case-sensitive match now. */
1139  if (patterns[k] >> 31) {
1140  const uint16_t patlen = pat->patlen;
1141  if (SCMemcmp(pat->cs, buf_offset - patlen, patlen) != 0) {
1142  /* Case-sensitive match failed. */
1143  continue;
1144  }
1145  }
1146  /* New match found */
1147  mpm_bitarray[pindex / 8] |= (1 << (pindex % 8));
1148 
1149  /* Always add the Signature IDs, since they could be different in the current MPM
1150  * than in a previous MPM on the same PMQ when finding the same pattern.
1151  */
1152  PrefilterAddSids(pmq, pattern_list[pindex].sids,
1153  pattern_list[pindex].sids_size);
1154  matches++;
1155  }
1156 
1157  return matches;
1158 }
1159 
1160 /**
1161  * \brief The aho corasick search function.
1162  *
1163  * \param mpm_ctx Pointer to the mpm context.
1164  * \param mpm_thread_ctx Pointer to the mpm thread context.
1165  * \param pmq Pointer to the Pattern Matcher Queue to hold
1166  * search matches.
1167  * \param buf Buffer to be searched.
1168  * \param buflen Buffer length.
1169  *
1170  * \retval matches Match count.
1171  */
1172 uint32_t SCACTileSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx,
1173  PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
1174 {
1175  const SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
1176 
1177  if (buflen == 0)
1178  return 0;
1179 
1180  /* Context specific matching function. */
1181  return search_ctx->Search(search_ctx, mpm_thread_ctx, pmq, buf, buflen);
1182 }
1183 
1184 /* This function handles (ctx->state_count >= 32767) */
1185 uint32_t SCACTileSearchLarge(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx,
1186  PrefilterRuleStore *pmq,
1187  const uint8_t *buf, uint32_t buflen)
1188 {
1189  uint32_t i = 0;
1190  int matches = 0;
1191 
1192  uint8_t mpm_bitarray[ctx->mpm_bitarray_size];
1193  memset(mpm_bitarray, 0, ctx->mpm_bitarray_size);
1194 
1195  const uint8_t* restrict xlate = ctx->translate_table;
1196  register int state = 0;
1197  int32_t (*state_table_u32)[256] = ctx->state_table;
1198  for (i = 0; i < buflen; i++) {
1199  state = state_table_u32[state & 0x00FFFFFF][xlate[buf[i]]];
1200  if (SCHECK(state)) {
1201  DEBUG_VALIDATE_BUG_ON(state < 0 || state > UINT16_MAX);
1202  matches = CheckMatch(ctx, pmq, buf, buflen, (uint16_t)state, i, matches, mpm_bitarray);
1203  }
1204  } /* for (i = 0; i < buflen; i++) */
1205 
1206  return matches;
1207 }
1208 
1209 /*
1210  * Search with Alphabet size of 256 and 16-bit next-state entries.
1211  * Next state entry has MSB as "match" and 15 LSB bits as next-state index.
1212  */
1213 // y = 1<<log_mult * (x & (1<<width -1))
1214 #define SINDEX_INTERNAL(y, x, log_mult, width) \
1215  ((1<<log_mult) * (x & ((1<<width) - 1)))
1216 
1217 /* Type of next_state */
1218 #define STYPE int16_t
1219 #define SLOAD(x) *(STYPE * restrict)(x)
1221 #define FUNC_NAME SCACTileSearchSmall256
1222 // y = 256 * (x & 0x7FFF)
1223 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 8, 15)
1224 #include "util-mpm-ac-ks-small.c"
1225 
1226 /* Search with Alphabet size of 128 */
1227 #undef FUNC_NAME
1228 #undef SINDEX
1229 #define FUNC_NAME SCACTileSearchSmall128
1230 // y = 128 * (x & 0x7FFF)
1231 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 7, 15)
1232 #include "util-mpm-ac-ks-small.c"
1233 
1234 /* Search with Alphabet size of 64 */
1235 #undef FUNC_NAME
1236 #undef SINDEX
1237 #define FUNC_NAME SCACTileSearchSmall64
1238 // y = 64 * (x & 0x7FFF)
1239 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 6, 15)
1240 #include "util-mpm-ac-ks-small.c"
1241 
1242 /* Search with Alphabet size of 32 */
1243 #undef FUNC_NAME
1244 #undef SINDEX
1245 #define FUNC_NAME SCACTileSearchSmall32
1246 // y = 32 * (x & 0x7FFF)
1247 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 5, 15)
1248 #include "util-mpm-ac-ks-small.c"
1249 
1250 /* Search with Alphabet size of 16 */
1251 #undef FUNC_NAME
1252 #undef SINDEX
1253 #define FUNC_NAME SCACTileSearchSmall16
1254 // y = 16 * (x & 0x7FFF)
1255 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 4, 15)
1256 #include "util-mpm-ac-ks-small.c"
1257 
1258 /* Search with Alphabet size of 8 */
1259 #undef FUNC_NAME
1260 #undef SINDEX
1261 #define FUNC_NAME SCACTileSearchSmall8
1262 // y = 8 * (x & 0x7FFF)
1263 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 3, 15)
1264 #include "util-mpm-ac-ks-small.c"
1265 
1266 /*
1267  * Search with Alphabet size of 256 and 8-bit next-state entries.
1268  * Next state entry has MSB as "match" and 15 LSB bits as next-state index.
1269  */
1270 #undef STYPE
1271 #define STYPE int8_t
1273 #undef FUNC_NAME
1274 #undef SINDEX
1275 #define FUNC_NAME SCACTileSearchTiny256
1276 // y = 256 * (x & 0x7F)
1277 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 8, 7)
1278 #include "util-mpm-ac-ks-small.c"
1279 
1280 /* Search with Alphabet size of 128 */
1281 #undef FUNC_NAME
1282 #undef SINDEX
1283 #define FUNC_NAME SCACTileSearchTiny128
1284 // y = 128 * (x & 0x7F)
1285 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 7, 7)
1286 #include "util-mpm-ac-ks-small.c"
1287 
1288 /* Search with Alphabet size of 64 */
1289 #undef FUNC_NAME
1290 #undef SINDEX
1291 #define FUNC_NAME SCACTileSearchTiny64
1292 // y = 64 * (x & 0x7F)
1293 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 6, 7)
1294 #include "util-mpm-ac-ks-small.c"
1295 
1296 /* Search with Alphabet size of 32 */
1297 #undef FUNC_NAME
1298 #undef SINDEX
1299 #define FUNC_NAME SCACTileSearchTiny32
1300 // y = 32 * (x & 0x7F)
1301 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 5, 7)
1302 #include "util-mpm-ac-ks-small.c"
1303 
1304 /* Search with Alphabet size of 16 */
1305 #undef FUNC_NAME
1306 #undef SINDEX
1307 #define FUNC_NAME SCACTileSearchTiny16
1308 // y = 16 * (x & 0x7F)
1309 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 4, 7)
1310 #include "util-mpm-ac-ks-small.c"
1311 
1312 /* Search with Alphabet size of 8 */
1313 #undef FUNC_NAME
1314 #undef SINDEX
1315 #define FUNC_NAME SCACTileSearchTiny8
1316 // y = 8 * (x & 0x7F)
1317 #define SINDEX(y,x) SINDEX_INTERNAL(y, x, 3, 7)
1319 
1320 
1321 /**
1322  * \brief Add a case insensitive pattern. Although we have different calls for
1323  * adding case sensitive and insensitive patterns, we make a single call
1324  * for either case. No special treatment for either case.
1325  *
1326  * \param mpm_ctx Pointer to the mpm context.
1327  * \param pat The pattern to add.
1328  * \param patnen The pattern length.
1329  * \param offset Ignored.
1330  * \param depth Ignored.
1331  * \param pid The pattern id.
1332  * \param sid Ignored.
1333  * \param flags Flags associated with this pattern.
1334  *
1335  * \retval 0 On success.
1336  * \retval -1 On failure.
1337  */
1338 int SCACTileAddPatternCI(MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen,
1339  uint16_t offset, uint16_t depth, uint32_t pid,
1340  SigIntId sid, uint8_t flags)
1341 {
1343  return MpmAddPattern(mpm_ctx, pat, patlen, offset, depth,
1344  pid, sid, flags);
1345 }
1346 
1347 /**
1348  * \brief Add a case sensitive pattern. Although we have different calls for
1349  * adding case sensitive and insensitive patterns, we make a single call
1350  * for either case. No special treatment for either case.
1351  *
1352  * \param mpm_ctx Pointer to the mpm context.
1353  * \param pat The pattern to add.
1354  * \param patnen The pattern length.
1355  * \param offset Ignored.
1356  * \param depth Ignored.
1357  * \param pid The pattern id.
1358  * \param sid Ignored.
1359  * \param flags Flags associated with this pattern.
1360  *
1361  * \retval 0 On success.
1362  * \retval -1 On failure.
1363  */
1364 int SCACTileAddPatternCS(MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen,
1365  uint16_t offset, uint16_t depth, uint32_t pid,
1366  SigIntId sid, uint8_t flags)
1367 {
1368  return MpmAddPattern(mpm_ctx, pat, patlen, offset, depth,
1369  pid, sid, flags);
1370 }
1371 
1373 {
1374  SCACTileSearchCtx *search_ctx = (SCACTileSearchCtx *)mpm_ctx->ctx;
1375  SCACTileCtx *ctx = search_ctx->init_ctx;
1376 
1377  printf("MPM AC Information:\n");
1378  printf("Memory allocs: %" PRIu32 "\n", mpm_ctx->memory_cnt);
1379  printf("Memory alloced: %" PRIu32 "\n", mpm_ctx->memory_size);
1380  printf(" Sizeof:\n");
1381  printf(" MpmCtx %" PRIuMAX "\n", (uintmax_t)sizeof(MpmCtx));
1382  printf(" SCACTileCtx: %" PRIuMAX "\n", (uintmax_t)sizeof(SCACTileCtx));
1383  printf(" MpmPattern %" PRIuMAX "\n", (uintmax_t)sizeof(MpmPattern));
1384  printf(" MpmPattern %" PRIuMAX "\n", (uintmax_t)sizeof(MpmPattern));
1385  printf("Unique Patterns: %" PRIu32 "\n", mpm_ctx->pattern_cnt);
1386  printf("Smallest: %" PRIu32 "\n", mpm_ctx->minlen);
1387  printf("Largest: %" PRIu32 "\n", mpm_ctx->maxlen);
1388  printf("Total states in the state table: %u\n", ctx->state_count);
1389  printf("\n");
1390 }
1391 
1392 /************************** Mpm Registration ***************************/
1393 
1394 /**
1395  * \brief Register the aho-corasick mpm 'ks' originally developed by
1396  * Ken Steele for Tilera Tile-Gx processor.
1397  */
1399 {
1400  mpm_table[MPM_AC_KS].name = "ac-ks";
1408 #ifdef UNITTESTS
1409  mpm_table[MPM_AC_KS].RegisterUnittests = SCACTileRegisterTests;
1410 #endif
1411 }
1412 
1413 
1414 /*************************************Unittests********************************/
1415 
1416 #ifdef UNITTESTS
1417 #include "detect-engine-alert.h"
1418 
1419 static int SCACTileTest01(void)
1420 {
1421  int result = 0;
1422  MpmCtx mpm_ctx;
1423  MpmThreadCtx mpm_thread_ctx;
1424  PrefilterRuleStore pmq;
1425 
1426  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1427  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1428  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1429 
1430  /* 1 match */
1431  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1432  PmqSetup(&pmq);
1433 
1434  SCACTilePreparePatterns(&mpm_ctx);
1435 
1436  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1437 
1438  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1439  (uint8_t *)buf, strlen(buf));
1440 
1441  if (cnt == 1)
1442  result = 1;
1443  else
1444  printf("1 != %" PRIu32 " ",cnt);
1445 
1446  SCACTileDestroyCtx(&mpm_ctx);
1447  PmqFree(&pmq);
1448  return result;
1449 }
1450 
1451 static int SCACTileTest02(void)
1452 {
1453  int result = 0;
1454  MpmCtx mpm_ctx;
1455  MpmThreadCtx mpm_thread_ctx;
1456  PrefilterRuleStore pmq;
1457 
1458  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1459  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1460  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1461 
1462  /* 1 match */
1463  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abce", 4, 0, 0, 0, 0, 0);
1464  PmqSetup(&pmq);
1465 
1466  SCACTilePreparePatterns(&mpm_ctx);
1467 
1468  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1469  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1470  (uint8_t *)buf, strlen(buf));
1471 
1472  if (cnt == 0)
1473  result = 1;
1474  else
1475  printf("0 != %" PRIu32 " ",cnt);
1476 
1477  SCACTileDestroyCtx(&mpm_ctx);
1478  PmqFree(&pmq);
1479  return result;
1480 }
1481 
1482 static int SCACTileTest03(void)
1483 {
1484  int result = 0;
1485  MpmCtx mpm_ctx;
1486  MpmThreadCtx mpm_thread_ctx;
1487  PrefilterRuleStore pmq;
1488 
1489  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1490  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1491  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1492 
1493  /* 1 match */
1494  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1495  /* 1 match */
1496  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"bcde", 4, 0, 0, 1, 0, 0);
1497  /* 1 match */
1498  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"fghj", 4, 0, 0, 2, 0, 0);
1499  PmqSetup(&pmq);
1500 
1501  SCACTilePreparePatterns(&mpm_ctx);
1502 
1503  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1504  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1505  (uint8_t *)buf, strlen(buf));
1506 
1507  if (cnt == 3)
1508  result = 1;
1509  else
1510  printf("3 != %" PRIu32 " ",cnt);
1511 
1512  SCACTileDestroyCtx(&mpm_ctx);
1513  PmqFree(&pmq);
1514  return result;
1515 }
1516 
1517 static int SCACTileTest04(void)
1518 {
1519  int result = 0;
1520  MpmCtx mpm_ctx;
1521  MpmThreadCtx mpm_thread_ctx;
1522  PrefilterRuleStore pmq;
1523 
1524  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1525  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1526  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1527 
1528  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1529  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"bcdegh", 6, 0, 0, 1, 0, 0);
1530  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"fghjxyz", 7, 0, 0, 2, 0, 0);
1531  PmqSetup(&pmq);
1532 
1533  SCACTilePreparePatterns(&mpm_ctx);
1534 
1535  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1536  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1537  (uint8_t *)buf, strlen(buf));
1538 
1539  if (cnt == 1)
1540  result = 1;
1541  else
1542  printf("1 != %" PRIu32 " ",cnt);
1543 
1544  SCACTileDestroyCtx(&mpm_ctx);
1545  PmqFree(&pmq);
1546  return result;
1547 }
1548 
1549 static int SCACTileTest05(void)
1550 {
1551  int result = 0;
1552  MpmCtx mpm_ctx;
1553  MpmThreadCtx mpm_thread_ctx;
1554  PrefilterRuleStore pmq;
1555 
1556  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1557  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1558  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1559 
1560  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"ABCD", 4, 0, 0, 0, 0, 0);
1561  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"bCdEfG", 6, 0, 0, 1, 0, 0);
1562  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"fghJikl", 7, 0, 0, 2, 0, 0);
1563  PmqSetup(&pmq);
1564 
1565  SCACTilePreparePatterns(&mpm_ctx);
1566 
1567  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1568  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1569  (uint8_t *)buf, strlen(buf));
1570 
1571  if (cnt == 3)
1572  result = 1;
1573  else
1574  printf("3 != %" PRIu32 " ",cnt);
1575 
1576  SCACTileDestroyCtx(&mpm_ctx);
1577  PmqFree(&pmq);
1578  return result;
1579 }
1580 
1581 static int SCACTileTest06(void)
1582 {
1583  int result = 0;
1584  MpmCtx mpm_ctx;
1585  MpmThreadCtx mpm_thread_ctx;
1586  PrefilterRuleStore pmq;
1587 
1588  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1589  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1590  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1591 
1592  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1593  PmqSetup(&pmq);
1594 
1595  SCACTilePreparePatterns(&mpm_ctx);
1596 
1597  const char *buf = "abcd";
1598  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1599  (uint8_t *)buf, strlen(buf));
1600 
1601  if (cnt == 1)
1602  result = 1;
1603  else
1604  printf("1 != %" PRIu32 " ",cnt);
1605 
1606  SCACTileDestroyCtx(&mpm_ctx);
1607  PmqFree(&pmq);
1608  return result;
1609 }
1610 
1611 static int SCACTileTest07(void)
1612 {
1613  MpmCtx mpm_ctx;
1614  MpmThreadCtx mpm_thread_ctx;
1615  PrefilterRuleStore pmq;
1616 
1617  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1618  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1619  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1620 
1621  /* should match 30 times */
1622  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"A", 1, 0, 0, 0, 0, 0);
1623  /* should match 29 times */
1624  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 1, 0, 0);
1625  /* should match 28 times */
1626  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAA", 3, 0, 0, 2, 0, 0);
1627  /* 26 */
1628  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAA", 5, 0, 0, 3, 0, 0);
1629  /* 21 */
1630  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAAAAAAA", 10, 0, 0, 4, 0, 0);
1631  /* 1 */
1632  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
1633  30, 0, 0, 5, 0, 0);
1634  PmqSetup(&pmq);
1635  /* total matches: 135: 6 unique */
1636 
1637  SCACTilePreparePatterns(&mpm_ctx);
1638 
1639  const char *buf = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
1640  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1641  (uint8_t *)buf, strlen(buf));
1642  FAIL_IF_NOT(cnt == 6);
1643 
1644  SCACTileDestroyCtx(&mpm_ctx);
1645  PmqFree(&pmq);
1646  PASS;
1647 }
1648 
1649 static int SCACTileTest08(void)
1650 {
1651  int result = 0;
1652  MpmCtx mpm_ctx;
1653  MpmThreadCtx mpm_thread_ctx;
1654  PrefilterRuleStore pmq;
1655 
1656  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1657  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1658  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1659 
1660  /* 1 match */
1661  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1662  PmqSetup(&pmq);
1663 
1664  SCACTilePreparePatterns(&mpm_ctx);
1665 
1666  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1667  (uint8_t *)"a", 1);
1668 
1669  if (cnt == 0)
1670  result = 1;
1671  else
1672  printf("0 != %" PRIu32 " ",cnt);
1673 
1674  SCACTileDestroyCtx(&mpm_ctx);
1675  PmqFree(&pmq);
1676  return result;
1677 }
1678 
1679 static int SCACTileTest09(void)
1680 {
1681  int result = 0;
1682  MpmCtx mpm_ctx;
1683  MpmThreadCtx mpm_thread_ctx;
1684  PrefilterRuleStore pmq;
1685 
1686  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1687  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1688  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1689 
1690  /* 1 match */
1691  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"ab", 2, 0, 0, 0, 0, 0);
1692  PmqSetup(&pmq);
1693 
1694  SCACTilePreparePatterns(&mpm_ctx);
1695 
1696  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1697  (uint8_t *)"ab", 2);
1698 
1699  if (cnt == 1)
1700  result = 1;
1701  else
1702  printf("1 != %" PRIu32 " ",cnt);
1703 
1704  SCACTileDestroyCtx(&mpm_ctx);
1705  PmqFree(&pmq);
1706  return result;
1707 }
1708 
1709 static int SCACTileTest10(void)
1710 {
1711  int result = 0;
1712  MpmCtx mpm_ctx;
1713  MpmThreadCtx mpm_thread_ctx;
1714  PrefilterRuleStore pmq;
1715 
1716  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1717  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1718  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1719 
1720  /* 1 match */
1721  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcdefgh", 8, 0, 0, 0, 0, 0);
1722  PmqSetup(&pmq);
1723 
1724  SCACTilePreparePatterns(&mpm_ctx);
1725 
1726  const char *buf = "01234567890123456789012345678901234567890123456789"
1727  "01234567890123456789012345678901234567890123456789"
1728  "abcdefgh"
1729  "01234567890123456789012345678901234567890123456789"
1730  "01234567890123456789012345678901234567890123456789";
1731  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1732  (uint8_t *)buf, strlen(buf));
1733 
1734  if (cnt == 1)
1735  result = 1;
1736  else
1737  printf("1 != %" PRIu32 " ",cnt);
1738 
1739  SCACTileDestroyCtx(&mpm_ctx);
1740  PmqFree(&pmq);
1741  return result;
1742 }
1743 
1744 static int SCACTileTest11(void)
1745 {
1746  int result = 0;
1747  MpmCtx mpm_ctx;
1748  MpmThreadCtx mpm_thread_ctx;
1749  PrefilterRuleStore pmq;
1750 
1751  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1752  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1753  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1754 
1755  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"he", 2, 0, 0, 1, 0, 0) == -1)
1756  goto end;
1757  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"she", 3, 0, 0, 2, 0, 0) == -1)
1758  goto end;
1759  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"his", 3, 0, 0, 3, 0, 0) == -1)
1760  goto end;
1761  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"hers", 4, 0, 0, 4, 0, 0) == -1)
1762  goto end;
1763  PmqSetup(&pmq);
1764 
1765  if (SCACTilePreparePatterns(&mpm_ctx) == -1)
1766  goto end;
1767 
1768  result = 1;
1769 
1770  const char *buf = "he";
1771  result &= (SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1772  strlen(buf)) == 1);
1773  buf = "she";
1774  result &= (SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1775  strlen(buf)) == 2);
1776  buf = "his";
1777  result &= (SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1778  strlen(buf)) == 1);
1779  buf = "hers";
1780  result &= (SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1781  strlen(buf)) == 2);
1782 
1783  end:
1784  SCACTileDestroyCtx(&mpm_ctx);
1785  PmqFree(&pmq);
1786  return result;
1787 }
1788 
1789 static int SCACTileTest12(void)
1790 {
1791  int result = 0;
1792  MpmCtx mpm_ctx;
1793  MpmThreadCtx mpm_thread_ctx;
1794  PrefilterRuleStore pmq;
1795 
1796  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1797  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1798  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1799 
1800  /* 1 match */
1801  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"wxyz", 4, 0, 0, 0, 0, 0);
1802  /* 1 match */
1803  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"vwxyz", 5, 0, 0, 1, 0, 0);
1804  PmqSetup(&pmq);
1805 
1806  SCACTilePreparePatterns(&mpm_ctx);
1807 
1808  const char *buf = "abcdefghijklmnopqrstuvwxyz";
1809  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1810  (uint8_t *)buf, strlen(buf));
1811 
1812  if (cnt == 2)
1813  result = 1;
1814  else
1815  printf("2 != %" PRIu32 " ",cnt);
1816 
1817  SCACTileDestroyCtx(&mpm_ctx);
1818  PmqFree(&pmq);
1819  return result;
1820 }
1821 
1822 static int SCACTileTest13(void)
1823 {
1824  int result = 0;
1825  MpmCtx mpm_ctx;
1826  MpmThreadCtx mpm_thread_ctx;
1827  PrefilterRuleStore pmq;
1828 
1829  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1830  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1831  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1832 
1833  /* 1 match */
1834  const char pat[] = "abcdefghijklmnopqrstuvwxyzABCD";
1835  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1836  PmqSetup(&pmq);
1837 
1838  SCACTilePreparePatterns(&mpm_ctx);
1839 
1840  const char *buf = "abcdefghijklmnopqrstuvwxyzABCD";
1841  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1842  (uint8_t *)buf, strlen(buf));
1843 
1844  if (cnt == 1)
1845  result = 1;
1846  else
1847  printf("1 != %" PRIu32 " ",cnt);
1848 
1849  SCACTileDestroyCtx(&mpm_ctx);
1850  PmqFree(&pmq);
1851  return result;
1852 }
1853 
1854 static int SCACTileTest14(void)
1855 {
1856  int result = 0;
1857  MpmCtx mpm_ctx;
1858  MpmThreadCtx mpm_thread_ctx;
1859  PrefilterRuleStore pmq;
1860 
1861  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1862  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1863  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1864 
1865  /* 1 match */
1866  const char pat[] = "abcdefghijklmnopqrstuvwxyzABCDE";
1867  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1868  PmqSetup(&pmq);
1869 
1870  SCACTilePreparePatterns(&mpm_ctx);
1871 
1872  const char *buf = "abcdefghijklmnopqrstuvwxyzABCDE";
1873  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1874  (uint8_t *)buf, strlen(buf));
1875 
1876  if (cnt == 1)
1877  result = 1;
1878  else
1879  printf("1 != %" PRIu32 " ",cnt);
1880 
1881  SCACTileDestroyCtx(&mpm_ctx);
1882  PmqFree(&pmq);
1883  return result;
1884 }
1885 
1886 static int SCACTileTest15(void)
1887 {
1888  int result = 0;
1889  MpmCtx mpm_ctx;
1890  MpmThreadCtx mpm_thread_ctx;
1891  PrefilterRuleStore pmq;
1892 
1893  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1894  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1895  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1896 
1897  /* 1 match */
1898  const char pat[] = "abcdefghijklmnopqrstuvwxyzABCDEF";
1899  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1900  PmqSetup(&pmq);
1901 
1902  SCACTilePreparePatterns(&mpm_ctx);
1903 
1904  const char *buf = "abcdefghijklmnopqrstuvwxyzABCDEF";
1905  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1906  (uint8_t *)buf, strlen(buf));
1907 
1908  if (cnt == 1)
1909  result = 1;
1910  else
1911  printf("1 != %" PRIu32 " ",cnt);
1912 
1913  SCACTileDestroyCtx(&mpm_ctx);
1914  PmqFree(&pmq);
1915  return result;
1916 }
1917 
1918 static int SCACTileTest16(void)
1919 {
1920  int result = 0;
1921  MpmCtx mpm_ctx;
1922  MpmThreadCtx mpm_thread_ctx;
1923  PrefilterRuleStore pmq;
1924 
1925  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1926  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1927  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1928 
1929  /* 1 match */
1930  const char pat[] = "abcdefghijklmnopqrstuvwxyzABC";
1931  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1932  PmqSetup(&pmq);
1933 
1934  SCACTilePreparePatterns(&mpm_ctx);
1935 
1936  const char *buf = "abcdefghijklmnopqrstuvwxyzABC";
1937  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1938  (uint8_t *)buf, strlen(buf));
1939 
1940  if (cnt == 1)
1941  result = 1;
1942  else
1943  printf("1 != %" PRIu32 " ",cnt);
1944 
1945  SCACTileDestroyCtx(&mpm_ctx);
1946  PmqFree(&pmq);
1947  return result;
1948 }
1949 
1950 static int SCACTileTest17(void)
1951 {
1952  int result = 0;
1953  MpmCtx mpm_ctx;
1954  MpmThreadCtx mpm_thread_ctx;
1955  PrefilterRuleStore pmq;
1956 
1957  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1958  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1959  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1960 
1961  /* 1 match */
1962  const char pat[] = "abcdefghijklmnopqrstuvwxyzAB";
1963  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
1964  PmqSetup(&pmq);
1965 
1966  SCACTilePreparePatterns(&mpm_ctx);
1967 
1968  const char *buf = "abcdefghijklmnopqrstuvwxyzAB";
1969  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1970  (uint8_t *)buf, strlen(buf));
1971 
1972  if (cnt == 1)
1973  result = 1;
1974  else
1975  printf("1 != %" PRIu32 " ",cnt);
1976 
1977  SCACTileDestroyCtx(&mpm_ctx);
1978  PmqFree(&pmq);
1979  return result;
1980 }
1981 
1982 static int SCACTileTest18(void)
1983 {
1984  int result = 0;
1985  MpmCtx mpm_ctx;
1986  MpmThreadCtx mpm_thread_ctx;
1987  PrefilterRuleStore pmq;
1988 
1989  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1990  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1991  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
1992 
1993  /* 1 match */
1994  const char pat[] = "abcde"
1995  "fghij"
1996  "klmno"
1997  "pqrst"
1998  "uvwxy"
1999  "z";
2000  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
2001  PmqSetup(&pmq);
2002 
2003  SCACTilePreparePatterns(&mpm_ctx);
2004 
2005  const char *buf = "abcde""fghij""klmno""pqrst""uvwxy""z";
2006  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2007  (uint8_t *)buf, strlen(buf));
2008 
2009  if (cnt == 1)
2010  result = 1;
2011  else
2012  printf("1 != %" PRIu32 " ",cnt);
2013 
2014  SCACTileDestroyCtx(&mpm_ctx);
2015  PmqFree(&pmq);
2016  return result;
2017 }
2018 
2019 static int SCACTileTest19(void)
2020 {
2021  int result = 0;
2022  MpmCtx mpm_ctx;
2023  MpmThreadCtx mpm_thread_ctx;
2024  PrefilterRuleStore pmq;
2025 
2026  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2027  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2028  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2029 
2030  /* 1 */
2031  const char pat[] = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
2032  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
2033  PmqSetup(&pmq);
2034 
2035  SCACTilePreparePatterns(&mpm_ctx);
2036 
2037  const char *buf = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
2038  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2039  (uint8_t *)buf, strlen(buf));
2040 
2041  if (cnt == 1)
2042  result = 1;
2043  else
2044  printf("1 != %" PRIu32 " ",cnt);
2045 
2046  SCACTileDestroyCtx(&mpm_ctx);
2047  PmqFree(&pmq);
2048  return result;
2049 }
2050 
2051 static int SCACTileTest20(void)
2052 {
2053  int result = 0;
2054  MpmCtx mpm_ctx;
2055  MpmThreadCtx mpm_thread_ctx;
2056  PrefilterRuleStore pmq;
2057 
2058  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2059  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2060  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2061 
2062  /* 1 */
2063  const char pat[] = "AAAAA"
2064  "AAAAA"
2065  "AAAAA"
2066  "AAAAA"
2067  "AAAAA"
2068  "AAAAA"
2069  "AA";
2070  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, sizeof(pat) - 1, 0, 0, 0, 0, 0);
2071  PmqSetup(&pmq);
2072 
2073  SCACTilePreparePatterns(&mpm_ctx);
2074 
2075  const char *buf = "AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AA";
2076  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2077  (uint8_t *)buf, strlen(buf));
2078 
2079  if (cnt == 1)
2080  result = 1;
2081  else
2082  printf("1 != %" PRIu32 " ",cnt);
2083 
2084  SCACTileDestroyCtx(&mpm_ctx);
2085  PmqFree(&pmq);
2086  return result;
2087 }
2088 
2089 static int SCACTileTest21(void)
2090 {
2091  int result = 0;
2092  MpmCtx mpm_ctx;
2093  MpmThreadCtx mpm_thread_ctx;
2094  PrefilterRuleStore pmq;
2095 
2096  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2097  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2098  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2099 
2100  /* 1 */
2101  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2102  PmqSetup(&pmq);
2103 
2104  SCACTilePreparePatterns(&mpm_ctx);
2105 
2106  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2107  (uint8_t *)"AA", 2);
2108 
2109  if (cnt == 1)
2110  result = 1;
2111  else
2112  printf("1 != %" PRIu32 " ",cnt);
2113 
2114  SCACTileDestroyCtx(&mpm_ctx);
2115  PmqFree(&pmq);
2116  return result;
2117 }
2118 
2119 static int SCACTileTest22(void)
2120 {
2121  int result = 0;
2122  MpmCtx mpm_ctx;
2123  MpmThreadCtx mpm_thread_ctx;
2124  PrefilterRuleStore pmq;
2125 
2126  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2127  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2128  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2129 
2130  /* 1 match */
2131  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
2132  /* 1 match */
2133  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcde", 5, 0, 0, 1, 0, 0);
2134  PmqSetup(&pmq);
2135 
2136  SCACTilePreparePatterns(&mpm_ctx);
2137 
2138  const char *buf = "abcdefghijklmnopqrstuvwxyz";
2139  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2140  (uint8_t *)buf, strlen(buf));
2141 
2142  if (cnt == 2)
2143  result = 1;
2144  else
2145  printf("2 != %" PRIu32 " ",cnt);
2146 
2147  SCACTileDestroyCtx(&mpm_ctx);
2148  PmqFree(&pmq);
2149  return result;
2150 }
2151 
2152 static int SCACTileTest23(void)
2153 {
2154  int result = 0;
2155  MpmCtx mpm_ctx;
2156  MpmThreadCtx mpm_thread_ctx;
2157  PrefilterRuleStore pmq;
2158 
2159  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2160  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2161  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2162 
2163  /* 1 */
2164  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2165  PmqSetup(&pmq);
2166 
2167  SCACTilePreparePatterns(&mpm_ctx);
2168 
2169  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2170  (uint8_t *)"aa", 2);
2171 
2172  if (cnt == 0)
2173  result = 1;
2174  else
2175  printf("1 != %" PRIu32 " ",cnt);
2176 
2177  SCACTileDestroyCtx(&mpm_ctx);
2178  PmqFree(&pmq);
2179  return result;
2180 }
2181 
2182 static int SCACTileTest24(void)
2183 {
2184  int result = 0;
2185  MpmCtx mpm_ctx;
2186  MpmThreadCtx mpm_thread_ctx;
2187  PrefilterRuleStore pmq;
2188 
2189  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2190  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2191  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2192 
2193  /* 1 */
2194  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2195  PmqSetup(&pmq);
2196 
2197  SCACTilePreparePatterns(&mpm_ctx);
2198 
2199  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2200  (uint8_t *)"aa", 2);
2201 
2202  if (cnt == 1)
2203  result = 1;
2204  else
2205  printf("1 != %" PRIu32 " ",cnt);
2206 
2207  SCACTileDestroyCtx(&mpm_ctx);
2208  PmqFree(&pmq);
2209  return result;
2210 }
2211 
2212 static int SCACTileTest25(void)
2213 {
2214  int result = 0;
2215  MpmCtx mpm_ctx;
2216  MpmThreadCtx mpm_thread_ctx;
2217  PrefilterRuleStore pmq;
2218 
2219  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2220  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2221  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2222 
2223  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"ABCD", 4, 0, 0, 0, 0, 0);
2224  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"bCdEfG", 6, 0, 0, 1, 0, 0);
2225  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"fghiJkl", 7, 0, 0, 2, 0, 0);
2226  PmqSetup(&pmq);
2227 
2228  SCACTilePreparePatterns(&mpm_ctx);
2229 
2230  const char *buf = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2231  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2232  (uint8_t *)buf, strlen(buf));
2233 
2234  if (cnt == 3)
2235  result = 1;
2236  else
2237  printf("3 != %" PRIu32 " ",cnt);
2238 
2239  SCACTileDestroyCtx(&mpm_ctx);
2240  PmqFree(&pmq);
2241  return result;
2242 }
2243 
2244 static int SCACTileTest26(void)
2245 {
2246  int result = 0;
2247  MpmCtx mpm_ctx;
2248  MpmThreadCtx mpm_thread_ctx;
2249  PrefilterRuleStore pmq;
2250 
2251  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2252  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2253  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2254 
2255  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"Works", 5, 0, 0, 0, 0, 0);
2256  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"Works", 5, 0, 0, 1, 0, 0);
2257  PmqSetup(&pmq);
2258 
2259  SCACTilePreparePatterns(&mpm_ctx);
2260 
2261  const char *buf = "works";
2262  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2263  (uint8_t *)buf, strlen(buf));
2264 
2265  if (cnt == 1)
2266  result = 1;
2267  else
2268  printf("3 != %" PRIu32 " ",cnt);
2269 
2270  SCACTileDestroyCtx(&mpm_ctx);
2271  PmqFree(&pmq);
2272  return result;
2273 }
2274 
2275 static int SCACTileTest27(void)
2276 {
2277  int result = 0;
2278  MpmCtx mpm_ctx;
2279  MpmThreadCtx mpm_thread_ctx;
2280  PrefilterRuleStore pmq;
2281 
2282  memset(&mpm_ctx, 0, sizeof(MpmCtx));
2283  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2284  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2285 
2286  /* 0 match */
2287  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"ONE", 3, 0, 0, 0, 0, 0);
2288  PmqSetup(&pmq);
2289 
2290  SCACTilePreparePatterns(&mpm_ctx);
2291 
2292  const char *buf = "tone";
2293  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2294  (uint8_t *)buf, strlen(buf));
2295 
2296  if (cnt == 0)
2297  result = 1;
2298  else
2299  printf("0 != %" PRIu32 " ",cnt);
2300 
2301  SCACTileDestroyCtx(&mpm_ctx);
2302  PmqFree(&pmq);
2303  return result;
2304 }
2305 
2306 static int SCACTileTest28(void)
2307 {
2308  int result = 0;
2309  MpmCtx mpm_ctx;
2310  MpmThreadCtx mpm_thread_ctx;
2311  PrefilterRuleStore pmq;
2312 
2313  memset(&mpm_ctx, 0, sizeof(MpmCtx));
2314  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2315  MpmInitCtx(&mpm_ctx, MPM_AC_KS);
2316 
2317  /* 0 match */
2318  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"one", 3, 0, 0, 0, 0, 0);
2319  PmqSetup(&pmq);
2320 
2321  SCACTilePreparePatterns(&mpm_ctx);
2322 
2323  const char *buf = "tONE";
2324  uint32_t cnt = SCACTileSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2325  (uint8_t *)buf, strlen(buf));
2326 
2327  if (cnt == 0)
2328  result = 1;
2329  else
2330  printf("0 != %" PRIu32 " ",cnt);
2331 
2332  SCACTileDestroyCtx(&mpm_ctx);
2333  PmqFree(&pmq);
2334  return result;
2335 }
2336 
2337 static int SCACTileTest29(void)
2338 {
2339  uint8_t buf[] = "onetwothreefourfivesixseveneightnine";
2340  uint16_t buflen = sizeof(buf) - 1;
2341  Packet *p = NULL;
2342  ThreadVars th_v;
2343  DetectEngineThreadCtx *det_ctx = NULL;
2344  int result = 0;
2345 
2346  memset(&th_v, 0, sizeof(th_v));
2347  p = UTHBuildPacket(buf, buflen, IPPROTO_TCP);
2348 
2350  if (de_ctx == NULL)
2351  goto end;
2352 
2353  de_ctx->flags |= DE_QUIET;
2354 
2355  de_ctx->sig_list = SigInit(de_ctx, "alert tcp any any -> any any "
2356  "(content:\"onetwothreefourfivesixseveneightnine\"; sid:1;)");
2357  if (de_ctx->sig_list == NULL)
2358  goto end;
2359  de_ctx->sig_list->next = SigInit(de_ctx, "alert tcp any any -> any any "
2360  "(content:\"onetwothreefourfivesixseveneightnine\"; fast_pattern:3,3; sid:2;)");
2361  if (de_ctx->sig_list->next == NULL)
2362  goto end;
2363 
2365  DetectEngineThreadCtxInit(&th_v, (void *)de_ctx, (void *)&det_ctx);
2366 
2367  SigMatchSignatures(&th_v, de_ctx, det_ctx, p);
2368  if (PacketAlertCheck(p, 1) != 1) {
2369  printf("if (PacketAlertCheck(p, 1) != 1) failure\n");
2370  goto end;
2371  }
2372  if (PacketAlertCheck(p, 2) != 1) {
2373  printf("if (PacketAlertCheck(p, 1) != 2) failure\n");
2374  goto end;
2375  }
2376 
2377  result = 1;
2378 end:
2379  if (de_ctx != NULL) {
2382 
2383  DetectEngineThreadCtxDeinit(&th_v, (void *)det_ctx);
2385  }
2386 
2387  UTHFreePackets(&p, 1);
2388  return result;
2389 }
2390 
2391 void SCACTileRegisterTests(void)
2392 {
2393  UtRegisterTest("SCACTileTest01", SCACTileTest01);
2394  UtRegisterTest("SCACTileTest02", SCACTileTest02);
2395  UtRegisterTest("SCACTileTest03", SCACTileTest03);
2396  UtRegisterTest("SCACTileTest04", SCACTileTest04);
2397  UtRegisterTest("SCACTileTest05", SCACTileTest05);
2398  UtRegisterTest("SCACTileTest06", SCACTileTest06);
2399  UtRegisterTest("SCACTileTest07", SCACTileTest07);
2400  UtRegisterTest("SCACTileTest08", SCACTileTest08);
2401  UtRegisterTest("SCACTileTest09", SCACTileTest09);
2402  UtRegisterTest("SCACTileTest10", SCACTileTest10);
2403  UtRegisterTest("SCACTileTest11", SCACTileTest11);
2404  UtRegisterTest("SCACTileTest12", SCACTileTest12);
2405  UtRegisterTest("SCACTileTest13", SCACTileTest13);
2406  UtRegisterTest("SCACTileTest14", SCACTileTest14);
2407  UtRegisterTest("SCACTileTest15", SCACTileTest15);
2408  UtRegisterTest("SCACTileTest16", SCACTileTest16);
2409  UtRegisterTest("SCACTileTest17", SCACTileTest17);
2410  UtRegisterTest("SCACTileTest18", SCACTileTest18);
2411  UtRegisterTest("SCACTileTest19", SCACTileTest19);
2412  UtRegisterTest("SCACTileTest20", SCACTileTest20);
2413  UtRegisterTest("SCACTileTest21", SCACTileTest21);
2414  UtRegisterTest("SCACTileTest22", SCACTileTest22);
2415  UtRegisterTest("SCACTileTest23", SCACTileTest23);
2416  UtRegisterTest("SCACTileTest24", SCACTileTest24);
2417  UtRegisterTest("SCACTileTest25", SCACTileTest25);
2418  UtRegisterTest("SCACTileTest26", SCACTileTest26);
2419  UtRegisterTest("SCACTileTest27", SCACTileTest27);
2420  UtRegisterTest("SCACTileTest28", SCACTileTest28);
2421  UtRegisterTest("SCACTileTest29", SCACTileTest29);
2422 }
2423 #endif
2424 
2425 #else /* we're big endian */
2426 
2427 void MpmACTileRegister(void)
2428 {
2429  /* no-op on big endian */
2430 }
2431 
2432 #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
SCACTileCtx_::Search
uint32_t(* Search)(const struct SCACTileSearchCtx_ *ctx, struct MpmThreadCtx_ *, PrefilterRuleStore *, const uint8_t *, uint32_t)
Definition: util-mpm-ac-ks.h:69
SCACTileCtx_::allocated_state_count
uint32_t allocated_state_count
Definition: util-mpm-ac-ks.h:96
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
MpmFreePattern
void MpmFreePattern(MpmCtx *mpm_ctx, MpmPattern *p)
Definition: util-mpm.c:357
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:142
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
SCACTileCtx_::pattern_list
SCACTilePatternList * pattern_list
Definition: util-mpm-ac-ks.h:81
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
SCACTilePatternList_::offset
uint16_t offset
Definition: util-mpm-ac-ks.h:33
DetectEngineCtx_
main detection engine ctx
Definition: detect.h:835
util-memcpy.h
MpmCtx_::memory_size
uint32_t memory_size
Definition: util-mpm.h:103
DetectEngineCtxFree
void DetectEngineCtxFree(DetectEngineCtx *)
Free a DetectEngineCtx::
Definition: detect-engine.c:2580
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:160
SCACTileOutputTable_::no_of_entries
uint32_t no_of_entries
Definition: util-mpm-ac-ks.h:48
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:320
MpmCtx_::maxlen
uint16_t maxlen
Definition: util-mpm.h:100
MpmTableElmt_::AddPattern
int(* AddPattern)(struct MpmCtx_ *, uint8_t *, uint16_t, uint16_t, uint16_t, uint32_t, SigIntId, uint8_t)
Definition: util-mpm.h:159
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:338
SigMatchSignatures
void SigMatchSignatures(ThreadVars *tv, DetectEngineCtx *de_ctx, DetectEngineThreadCtx *det_ctx, Packet *p)
wrapper for old tests
Definition: detect.c:1882
StateQueue
struct StateQueue_ StateQueue
Helper structure used by AC during state table creation.
SigCleanSignatures
void SigCleanSignatures(DetectEngineCtx *de_ctx)
Definition: detect-engine-build.c:53
MpmPattern_::original_pat
uint8_t * original_pat
Definition: util-mpm.h:67
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:143
util-unittest.h
SCACTileCtx_::goto_table
int32_t(* goto_table)[256]
Definition: util-mpm-ac-ks.h:90
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
MpmPattern_::flags
uint8_t flags
Definition: util-mpm.h:58
SCHECK
#define SCHECK(x)
Definition: util-mpm-ac-ks.c:1107
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:210
Signature_::next
struct Signature_ * next
Definition: detect.h:664
MpmTableElmt_::PrintCtx
void(* PrintCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:164
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:17
DetectEngineThreadCtx_
Definition: detect.h:1091
SCACTileSearchCtx_::mpm_bitarray_size
uint32_t mpm_bitarray_size
Definition: util-mpm-ac-ks.h:136
MpmPattern_::id
uint32_t id
Definition: util-mpm.h:73
SCACTileSearchSmall8
uint32_t SCACTileSearchSmall8(const SCACTileSearchCtx *ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
SCACTileCtx_::state_count
uint32_t state_count
Definition: util-mpm-ac-ks.h:94
SCACTileOutputTable_::patterns
MpmPatternIndex * patterns
Definition: util-mpm-ac-ks.h:46
detect.h
ThreadVars_
Per thread variable structure.
Definition: threadvars.h:57
SCACTilePatternList
struct SCACTilePatternList_ SCACTilePatternList
util-mpm-ac-ks-small.c
SCACTilePreparePatterns
int SCACTilePreparePatterns(MpmCtx *mpm_ctx)
Process the patterns added to the mpm, and create the internal tables.
Definition: util-mpm-ac-ks.c:864
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:1172
SigInit
Signature * SigInit(DetectEngineCtx *de_ctx, const char *sigstr)
Parses a signature and adds it to the Detection Engine Context.
Definition: detect-parse.c:2314
MpmCtx_::minlen
uint16_t minlen
Definition: util-mpm.h:99
SCACTileSearchCtx_::init_ctx
SCACTileCtx * init_ctx
Definition: util-mpm-ac-ks.h:144
SigGroupCleanup
int SigGroupCleanup(DetectEngineCtx *de_ctx)
Definition: detect-engine-build.c:2017
MpmPattern_::sids_size
uint32_t sids_size
Definition: util-mpm.h:76
Packet_
Definition: decode.h:430
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)
SCACTilePatternList_::pid
uint32_t pid
Definition: util-mpm-ac-ks.h:37
MpmTableElmt_::Prepare
int(* Prepare)(struct MpmCtx_ *)
Definition: util-mpm.h:161
SCACTilePatternList_::sids
SigIntId * sids
Definition: util-mpm-ac-ks.h:41
StateQueue_::bot
int bot
Definition: util-mpm-ac-ks.c:158
SCACTileCtx_::alpha_hist
uint32_t alpha_hist[256]
Definition: util-mpm-ac-ks.h:98
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:163
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:250
SCACTilePrintInfo
void SCACTilePrintInfo(MpmCtx *mpm_ctx)
Definition: util-mpm-ac-ks.c:1372
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)
SCACTileCtx_::bytes_per_state
uint8_t bytes_per_state
Definition: util-mpm-ac-ks.h:107
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:1398
SCACTileCtx_::alphabet_storage
uint16_t alphabet_storage
Definition: util-mpm-ac-ks.h:104
MPM_AC_KS
@ MPM_AC_KS
Definition: util-mpm.h:37
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:1948
MpmPattern_::ci
uint8_t * ci
Definition: util-mpm.h:71
SCACTileCtx_::SetNextState
void(* SetNextState)(struct SCACTileCtx_ *ctx, int state, int aa, int new_state, int outputs)
Definition: util-mpm-ac-ks.h:75
SCRealloc
#define SCRealloc(ptr, sz)
Definition: util-mem.h:50
MPM_PATTERN_FLAG_NOCASE
#define MPM_PATTERN_FLAG_NOCASE
Definition: util-mpm.h:132
cnt
uint32_t cnt
Definition: tmqh-packetpool.h:7
SCACTileCtx_::translate_table
uint8_t translate_table[256]
Definition: util-mpm-ac-ks.h:57
DetectEngineThreadCtxInit
TmEcode DetectEngineThreadCtxInit(ThreadVars *, void *, void **)
initialize thread specific detection engine context
Definition: detect-engine.c:3291
flags
uint8_t flags
Definition: decode-gre.h:0
SCACTilePatternList_::depth
uint16_t depth
Definition: util-mpm-ac-ks.h:34
suricata-common.h
DetectEngineThreadCtxDeinit
TmEcode DetectEngineThreadCtxDeinit(ThreadVars *, void *)
Definition: detect-engine.c:3501
SCACTileCtx_::state_table
void * state_table
Definition: util-mpm-ac-ks.h:62
MpmCtx_::pattern_cnt
uint32_t pattern_cnt
Definition: util-mpm.h:97
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:1338
MpmPattern_::offset
uint16_t offset
Definition: util-mpm.h:61
FatalError
#define FatalError(...)
Definition: util-debug.h:502
DetectEngineCtx_::sig_list
Signature * sig_list
Definition: detect.h:843
util-validate.h
SCACTileCtx
struct SCACTileCtx_ SCACTileCtx
MpmPattern_::sids
SigIntId * sids
Definition: util-mpm.h:77
MpmPattern_::depth
uint16_t depth
Definition: util-mpm.h:64
SCACTileCtx_
Definition: util-mpm-ac-ks.h:54
SCACTilePatternList_
Definition: util-mpm-ac-ks.h:29
MpmTableElmt_::DestroyCtx
void(* DestroyCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:145
SCFree
#define SCFree(p)
Definition: util-mem.h:61
detect-parse.h
MpmCtx_::memory_cnt
uint32_t memory_cnt
Definition: util-mpm.h:102
MpmCtx_::init_hash
MpmPattern ** init_hash
Definition: util-mpm.h:108
SCACTileInitCtx
void SCACTileInitCtx(MpmCtx *)
Initialize the AC context.
Definition: util-mpm-ac-ks.c:964
MpmPattern_::len
uint16_t len
Definition: util-mpm.h:56
DetectEngineCtxInit
DetectEngineCtx * DetectEngineCtxInit(void)
Definition: detect-engine.c:2541
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:1185
SCACTileDestroyCtx
void SCACTileDestroyCtx(MpmCtx *)
Destroy the mpm context.
Definition: util-mpm-ac-ks.c:1065
suricata.h
SCACTileCtx_::parray
MpmPattern ** parray
Definition: util-mpm-ac-ks.h:85
PmqFree
void PmqFree(PrefilterRuleStore *pmq)
Cleanup and free a Pmq.
Definition: util-prefilter.c:126
SCACTilePatternList_::sids_size
uint32_t sids_size
Definition: util-mpm-ac-ks.h:40
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:439
DetectEngineCtx_::flags
uint8_t flags
Definition: detect.h:837
MpmCtx_
Definition: util-mpm.h:88
SigIntId
#define SigIntId
Definition: suricata-common.h:315
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:89
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:259
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:1364
SCMemcmp
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:290
SCACTileCtx_::failure_table
int32_t * failure_table
Definition: util-mpm-ac-ks.h:91
DEBUG_VALIDATE_BUG_ON
#define DEBUG_VALIDATE_BUG_ON(exp)
Definition: util-validate.h:104
SCACTileCtx_::output_table
SCACTileOutputTable * output_table
Definition: util-mpm-ac-ks.h:79
MpmTableElmt_::RegisterUnittests
void(* RegisterUnittests)(void)
Definition: util-mpm.h:167
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
SCACTileCtx_::alphabet_size
uint16_t alphabet_size
Definition: util-mpm-ac-ks.h:100
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:469