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