suricata
util-mpm-ac-bs.c
Go to the documentation of this file.
1 /* Copyright (C) 2007-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 Anoop Saldanha <anoopsaldanha@gmail.com>
22  *
23  * First iteration of aho-corasick MPM from -
24  *
25  * Efficient String Matching: An Aid to Bibliographic Search
26  * Alfred V. Aho and Margaret J. Corasick
27  *
28  * - Uses the delta table for calculating transitions, instead of having
29  * separate goto and failure transitions.
30  * - If we cross 2 ** 16 states, we use 4 bytes in the transition table
31  * to hold each state, otherwise we use 2 bytes.
32  * - This version of the MPM is heavy on memory, but it performs well.
33  * If you can fit the ruleset with this mpm on your box without hitting
34  * swap, this is the MPM to go for.
35  *
36  * \todo - Do a proper analyis of our existing MPMs and suggest a good one based
37  * on the pattern distribution and the expected traffic(say http).
38  * - Tried out loop unrolling without any perf increase. Need to dig deeper.
39  * - Irrespective of whether we cross 2 ** 16 states or not,shift to using
40  * uint32_t for state type, so that we can integrate it's status as a
41  * final state or not in the topmost byte. We are already doing it if
42  * state_count is > 2 ** 16.
43  * - Test case-senstive patterns if they have any ascii chars. If they
44  * don't treat them as nocase.
45  * - Carry out other optimizations we are working on. hashes, compression.
46  */
47 
48 #include "suricata-common.h"
49 #include "suricata.h"
50 
51 #include "detect.h"
52 #include "detect-parse.h"
53 #include "detect-engine.h"
54 #include "util-mpm-ac-bs.h"
55 
56 #include "conf.h"
57 #include "util-debug.h"
58 #include "util-unittest.h"
59 #include "util-unittest-helper.h"
60 #include "util-memcmp.h"
61 #include "util-memcpy.h"
62 
63 void SCACBSInitCtx(MpmCtx *);
65 void SCACBSDestroyCtx(MpmCtx *);
67 int SCACBSAddPatternCI(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t,
68  uint32_t, SigIntId, uint8_t);
69 int SCACBSAddPatternCS(MpmCtx *, uint8_t *, uint16_t, uint16_t, uint16_t,
70  uint32_t, SigIntId, uint8_t);
71 int SCACBSPreparePatterns(MpmCtx *mpm_ctx);
72 uint32_t SCACBSSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx,
73  PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen);
74 void SCACBSPrintInfo(MpmCtx *mpm_ctx);
75 void SCACBSPrintSearchStats(MpmThreadCtx *mpm_thread_ctx);
76 void SCACBSRegisterTests(void);
77 
78 /* a placeholder to denote a failure transition in the goto table */
79 #define SC_AC_BS_FAIL (-1)
80 
81 #define STATE_QUEUE_CONTAINER_SIZE 65536
82 
83 /**
84  * \brief Helper structure used by AC during state table creation
85  */
86 typedef struct StateQueue_ {
88  int top;
89  int bot;
90 } StateQueue;
91 
92 /**
93  * \brief Register the aho-corasick mpm.
94  */
95 void MpmACBSRegister(void)
96 {
97  mpm_table[MPM_AC_BS].name = "ac-bs";
109 
110  return;
111 }
112 
113 /**
114  * \internal
115  * \brief Initialize the AC context with user specified conf parameters. We
116  * aren't retrieving anything for AC conf now, but we will certainly
117  * need it, when we customize AC.
118  */
119 static void SCACBSGetConfig(void)
120 {
121  //ConfNode *ac_conf;
122  //const char *hash_val = NULL;
123 
124  //ConfNode *pm = ConfGetNode("pattern-matcher");
125 
126  return;
127 }
128 
129 /**
130  * \internal
131  * \brief Initialize a new state in the goto and output tables.
132  *
133  * \param mpm_ctx Pointer to the mpm context.
134  *
135  * \retval The state id, of the newly created state.
136  */
137 static inline int SCACBSInitNewState(MpmCtx *mpm_ctx)
138 {
139  void *ptmp;
140  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
141  int ascii_code = 0;
142  int size = 0;
143 
144  /* reallocate space in the goto table to include a new state */
145  size = (ctx->state_count + 1) * ctx->single_state_size;
146  ptmp = SCRealloc(ctx->goto_table, size);
147  if (ptmp == NULL) {
148  SCFree(ctx->goto_table);
149  ctx->goto_table = NULL;
150  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
151  exit(EXIT_FAILURE);
152  }
153  ctx->goto_table = ptmp;
154 
155  /* set all transitions for the newly assigned state as FAIL transitions */
156  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
157  ctx->goto_table[ctx->state_count][ascii_code] = SC_AC_BS_FAIL;
158  }
159 
160  /* reallocate space in the output table for the new state */
161  size = (ctx->state_count + 1) * sizeof(SCACBSOutputTable);
162  ptmp = SCRealloc(ctx->output_table, size);
163  if (ptmp == NULL) {
164  SCFree(ctx->output_table);
165  ctx->output_table = NULL;
166  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
167  exit(EXIT_FAILURE);
168  }
169  ctx->output_table = ptmp;
170 
171  memset(ctx->output_table + ctx->state_count, 0, sizeof(SCACBSOutputTable));
172 
173  /* \todo using it temporarily now during dev, since I have restricted
174  * state var in SCACBSCtx->state_table to uint16_t. */
175  //if (ctx->state_count > 65536) {
176  // printf("state count exceeded\n");
177  // exit(EXIT_FAILURE);
178  //}
179 
180  return ctx->state_count++;
181 }
182 
183 /**
184  * \internal
185  * \brief Adds a pid to the output table for a state.
186  *
187  * \param state The state to whose output table we should add the pid.
188  * \param pid The pattern id to add.
189  * \param mpm_ctx Pointer to the mpm context.
190  */
191 static void SCACBSSetOutputState(int32_t state, uint32_t pid, MpmCtx *mpm_ctx)
192 {
193  void *ptmp;
194  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
195  SCACBSOutputTable *output_state = &ctx->output_table[state];
196  uint32_t i = 0;
197 
198  for (i = 0; i < output_state->no_of_entries; i++) {
199  if (output_state->pids[i] == pid)
200  return;
201  }
202 
203  output_state->no_of_entries++;
204  ptmp = SCRealloc(output_state->pids,
205  output_state->no_of_entries * sizeof(uint32_t));
206  if (ptmp == NULL) {
207  SCFree(output_state->pids);
208  output_state->pids = NULL;
209  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
210  exit(EXIT_FAILURE);
211  }
212  output_state->pids = ptmp;
213 
214  output_state->pids[output_state->no_of_entries - 1] = pid;
215 
216  return;
217 }
218 
219 /**
220  * \brief Helper function used by SCACBSCreateGotoTable. Adds a pattern to the
221  * goto table.
222  *
223  * \param pattern Pointer to the pattern.
224  * \param pattern_len Pattern length.
225  * \param pid The pattern id, that corresponds to this pattern. We
226  * need it to updated the output table for this pattern.
227  * \param mpm_ctx Pointer to the mpm context.
228  */
229 static inline void SCACBSEnter(uint8_t *pattern, uint16_t pattern_len, uint32_t pid,
230  MpmCtx *mpm_ctx)
231 {
232  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
233  int32_t state = 0;
234  int32_t newstate = 0;
235  int i = 0;
236  int p = 0;
237 
238  /* walk down the trie till we have a match for the pattern prefix */
239  state = 0;
240  for (i = 0; i < pattern_len; i++) {
241  if (ctx->goto_table[state][pattern[i]] != SC_AC_BS_FAIL) {
242  state = ctx->goto_table[state][pattern[i]];
243  } else {
244  break;
245  }
246  }
247 
248  /* add the non-matching pattern suffix to the trie, from the last state
249  * we left off */
250  for (p = i; p < pattern_len; p++) {
251  newstate = SCACBSInitNewState(mpm_ctx);
252  ctx->goto_table[state][pattern[p]] = newstate;
253  state = newstate;
254  }
255 
256  /* add this pattern id, to the output table of the last state, where the
257  * pattern ends in the trie */
258  SCACBSSetOutputState(state, pid, mpm_ctx);
259 
260  return;
261 }
262 
263 /**
264  * \internal
265  * \brief Create the goto table.
266  *
267  * \param mpm_ctx Pointer to the mpm context.
268  */
269 static inline void SCACBSCreateGotoTable(MpmCtx *mpm_ctx)
270 {
271  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
272  uint32_t i = 0;
273 
274  /* add each pattern to create the goto table */
275  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
276  SCACBSEnter(ctx->parray[i]->ci, ctx->parray[i]->len,
277  ctx->parray[i]->id, mpm_ctx);
278  }
279 
280  int ascii_code = 0;
281  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
282  if (ctx->goto_table[0][ascii_code] == SC_AC_BS_FAIL) {
283  ctx->goto_table[0][ascii_code] = 0;
284  }
285  }
286 
287  return;
288 }
289 
290 static inline int SCACBSStateQueueIsEmpty(StateQueue *q)
291 {
292  if (q->top == q->bot)
293  return 1;
294  else
295  return 0;
296 }
297 
298 static inline void SCACBSEnqueue(StateQueue *q, int32_t state)
299 {
300  int i = 0;
301 
302  /*if we already have this */
303  for (i = q->bot; i < q->top; i++) {
304  if (q->store[i] == state)
305  return;
306  }
307 
308  q->store[q->top++] = state;
309 
311  q->top = 0;
312 
313  if (q->top == q->bot) {
314  SCLogCritical(SC_ERR_AHO_CORASICK, "Just ran out of space in the queue. "
315  "Fatal Error. Exiting. Please file a bug report on this");
316  exit(EXIT_FAILURE);
317  }
318 
319  return;
320 }
321 
322 static inline int32_t SCACBSDequeue(StateQueue *q)
323 {
325  q->bot = 0;
326 
327  if (q->bot == q->top) {
328  SCLogCritical(SC_ERR_AHO_CORASICK, "StateQueue behaving weirdly. "
329  "Fatal Error. Exiting. Please file a bug report on this");
330  exit(EXIT_FAILURE);
331  }
332 
333  return q->store[q->bot++];
334 }
335 
336 /*
337 #define SCACBSStateQueueIsEmpty(q) (((q)->top == (q)->bot) ? 1 : 0)
338 
339 #define SCACBSEnqueue(q, state) do { \
340  int i = 0; \
341  \
342  for (i = (q)->bot; i < (q)->top; i++) { \
343  if ((q)->store[i] == state) \
344  return; \
345  } \
346  \
347  (q)->store[(q)->top++] = state; \
348  \
349  if ((q)->top == STATE_QUEUE_CONTAINER_SIZE) \
350  (q)->top = 0; \
351  \
352  if ((q)->top == (q)->bot) { \
353  SCLogCritical(SC_ERR_AHO_CORASICK, "Just ran out of space in the queue. " \
354  "Fatal Error. Exiting. Please file a bug report on this"); \
355  exit(EXIT_FAILURE); \
356  } \
357  } while (0)
358 
359 #define SCACBSDequeue(q) ( (((q)->bot == STATE_QUEUE_CONTAINER_SIZE)? ((q)->bot = 0): 0), \
360  (((q)->bot == (q)->top) ? \
361  (printf("StateQueue behaving " \
362  "weirdly. Fatal Error. Exiting. Please " \
363  "file a bug report on this"), \
364  exit(EXIT_FAILURE)) : 0), \
365  (q)->store[(q)->bot++]) \
366 */
367 
368 /**
369  * \internal
370  * \brief Club the output data from 2 states and store it in the 1st state.
371  * dst_state_data = {dst_state_data} UNION {src_state_data}
372  *
373  * \param dst_state First state(also the destination) for the union operation.
374  * \param src_state Second state for the union operation.
375  * \param mpm_ctx Pointer to the mpm context.
376  */
377 static inline void SCACBSClubOutputStates(int32_t dst_state, int32_t src_state,
378  MpmCtx *mpm_ctx)
379 {
380  void *ptmp;
381  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
382  uint32_t i = 0;
383  uint32_t j = 0;
384 
385  SCACBSOutputTable *output_dst_state = &ctx->output_table[dst_state];
386  SCACBSOutputTable *output_src_state = &ctx->output_table[src_state];
387 
388  for (i = 0; i < output_src_state->no_of_entries; i++) {
389  for (j = 0; j < output_dst_state->no_of_entries; j++) {
390  if (output_src_state->pids[i] == output_dst_state->pids[j]) {
391  break;
392  }
393  }
394  if (j == output_dst_state->no_of_entries) {
395  output_dst_state->no_of_entries++;
396 
397  ptmp = SCRealloc(output_dst_state->pids,
398  (output_dst_state->no_of_entries * sizeof(uint32_t)));
399  if (ptmp == NULL) {
400  SCFree(output_dst_state->pids);
401  output_dst_state->pids = NULL;
402  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
403  exit(EXIT_FAILURE);
404  }
405  else {
406  output_dst_state->pids = ptmp;
407  }
408 
409  output_dst_state->pids[output_dst_state->no_of_entries - 1] =
410  output_src_state->pids[i];
411  }
412  }
413 
414  return;
415 }
416 
417 /**
418  * \internal
419  * \brief Create the failure table.
420  *
421  * \param mpm_ctx Pointer to the mpm context.
422  */
423 static inline void SCACBSCreateFailureTable(MpmCtx *mpm_ctx)
424 {
425  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
426  int ascii_code = 0;
427  int32_t state = 0;
428  int32_t r_state = 0;
429 
430  StateQueue q;
431  memset(&q, 0, sizeof(StateQueue));
432 
433  /* allot space for the failure table. A failure entry in the table for
434  * every state(SCACBSCtx->state_count) */
435  ctx->failure_table = SCMalloc(ctx->state_count * sizeof(int32_t));
436  if (ctx->failure_table == NULL) {
437  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
438  exit(EXIT_FAILURE);
439  }
440  memset(ctx->failure_table, 0, ctx->state_count * sizeof(int32_t));
441 
442  /* add the failure transitions for the 0th state, and add every non-fail
443  * transition from the 0th state to the queue for further processing
444  * of failure states */
445  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
446  int32_t temp_state = ctx->goto_table[0][ascii_code];
447  if (temp_state != 0) {
448  SCACBSEnqueue(&q, temp_state);
449  ctx->failure_table[temp_state] = 0;
450  }
451  }
452 
453  while (!SCACBSStateQueueIsEmpty(&q)) {
454  /* pick up every state from the queue and add failure transitions */
455  r_state = SCACBSDequeue(&q);
456  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
457  int32_t temp_state = ctx->goto_table[r_state][ascii_code];
458  if (temp_state == SC_AC_BS_FAIL)
459  continue;
460  SCACBSEnqueue(&q, temp_state);
461  state = ctx->failure_table[r_state];
462 
463  while(ctx->goto_table[state][ascii_code] == SC_AC_BS_FAIL)
464  state = ctx->failure_table[state];
465  ctx->failure_table[temp_state] = ctx->goto_table[state][ascii_code];
466  SCACBSClubOutputStates(temp_state, ctx->failure_table[temp_state],
467  mpm_ctx);
468  }
469  }
470 
471  return;
472 }
473 
474 /**
475  * \internal
476  * \brief Create the delta table.
477  *
478  * \param mpm_ctx Pointer to the mpm context.
479  */
480 static inline void SCACBSCreateDeltaTable(MpmCtx *mpm_ctx)
481 {
482  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
483  int ascii_code = 0;
484  int32_t r_state = 0;
485 
486  if (ctx->state_count < 32767) {
487  ctx->state_table_u16 = SCMalloc(ctx->state_count *
488  sizeof(SC_AC_BS_STATE_TYPE_U16) * 256);
489  if (ctx->state_table_u16 == NULL) {
490  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
491  exit(EXIT_FAILURE);
492  }
493  memset(ctx->state_table_u16, 0,
494  ctx->state_count * sizeof(SC_AC_BS_STATE_TYPE_U16) * 256);
495 
496  mpm_ctx->memory_cnt++;
497  mpm_ctx->memory_size += (ctx->state_count *
498  sizeof(SC_AC_BS_STATE_TYPE_U16) * 256);
499 
500  StateQueue q;
501  memset(&q, 0, sizeof(StateQueue));
502 
503  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
504  SC_AC_BS_STATE_TYPE_U16 temp_state = ctx->goto_table[0][ascii_code];
505  ctx->state_table_u16[0][ascii_code] = temp_state;
506  if (temp_state != 0)
507  SCACBSEnqueue(&q, temp_state);
508  }
509 
510  while (!SCACBSStateQueueIsEmpty(&q)) {
511  r_state = SCACBSDequeue(&q);
512 
513  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
514  int32_t temp_state = ctx->goto_table[r_state][ascii_code];
515  if (temp_state != SC_AC_BS_FAIL) {
516  SCACBSEnqueue(&q, temp_state);
517  ctx->state_table_u16[r_state][ascii_code] = temp_state;
518  } else {
519  ctx->state_table_u16[r_state][ascii_code] =
520  ctx->state_table_u16[ctx->failure_table[r_state]][ascii_code];
521  }
522  }
523  }
524  } else {
525  /* create space for the state table. We could have used the existing goto
526  * table, but since we have it set to hold 32 bit state values, we will create
527  * a new state table here of type SC_AC_BS_STATE_TYPE(current set to uint16_t) */
528  ctx->state_table_u32 = SCMalloc(ctx->state_count *
529  sizeof(SC_AC_BS_STATE_TYPE_U32) * 256);
530  if (ctx->state_table_u32 == NULL) {
531  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
532  exit(EXIT_FAILURE);
533  }
534  memset(ctx->state_table_u32, 0,
535  ctx->state_count * sizeof(SC_AC_BS_STATE_TYPE_U32) * 256);
536 
537  mpm_ctx->memory_cnt++;
538  mpm_ctx->memory_size += (ctx->state_count *
539  sizeof(SC_AC_BS_STATE_TYPE_U32) * 256);
540 
541  StateQueue q;
542  memset(&q, 0, sizeof(StateQueue));
543 
544  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
545  SC_AC_BS_STATE_TYPE_U32 temp_state = ctx->goto_table[0][ascii_code];
546  ctx->state_table_u32[0][ascii_code] = temp_state;
547  if (temp_state != 0)
548  SCACBSEnqueue(&q, temp_state);
549  }
550 
551  while (!SCACBSStateQueueIsEmpty(&q)) {
552  r_state = SCACBSDequeue(&q);
553 
554  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
555  int32_t temp_state = ctx->goto_table[r_state][ascii_code];
556  if (temp_state != SC_AC_BS_FAIL) {
557  SCACBSEnqueue(&q, temp_state);
558  ctx->state_table_u32[r_state][ascii_code] = temp_state;
559  } else {
560  ctx->state_table_u32[r_state][ascii_code] =
561  ctx->state_table_u32[ctx->failure_table[r_state]][ascii_code];
562  }
563  }
564  }
565  }
566 
567  return;
568 }
569 
570 static inline void SCACBSClubOutputStatePresenceWithDeltaTable(MpmCtx *mpm_ctx)
571 {
572  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
573  int ascii_code = 0;
574  uint32_t state = 0;
575  uint32_t temp_state = 0;
576 
577  if (ctx->state_count < 32767) {
578  for (state = 0; state < ctx->state_count; state++) {
579  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
580  temp_state = ctx->state_table_u16[state & 0x7FFF][ascii_code];
581  if (ctx->output_table[temp_state & 0x7FFF].no_of_entries != 0)
582  ctx->state_table_u16[state & 0x7FFF][ascii_code] |= (1 << 15);
583  }
584  }
585  } else {
586  for (state = 0; state < ctx->state_count; state++) {
587  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
588  temp_state = ctx->state_table_u32[state & 0x00FFFFFF][ascii_code];
589  if (ctx->output_table[temp_state & 0x00FFFFFF].no_of_entries != 0)
590  ctx->state_table_u32[state & 0x00FFFFFF][ascii_code] |= (1 << 24);
591  }
592  }
593  }
594 
595  return;
596 }
597 
598 static inline void SCACBSInsertCaseSensitiveEntriesForPatterns(MpmCtx *mpm_ctx)
599 {
600  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
601  uint32_t state = 0;
602  uint32_t k = 0;
603 
604  for (state = 0; state < ctx->state_count; state++) {
605  if (ctx->output_table[state].no_of_entries == 0)
606  continue;
607 
608  for (k = 0; k < ctx->output_table[state].no_of_entries; k++) {
609  if (ctx->pid_pat_list[ctx->output_table[state].pids[k]].cs != NULL) {
610  ctx->output_table[state].pids[k] &= 0x0000FFFF;
611  ctx->output_table[state].pids[k] |= 1 << 16;
612  }
613  }
614  }
615 
616  return;
617 }
618 
619 #if 0
620 static void SCACBSPrintDeltaTable(MpmCtx *mpm_ctx)
621 {
622  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
623  int i = 0, j = 0;
624 
625  printf("##############Delta Table##############\n");
626  for (i = 0; i < ctx->state_count; i++) {
627  printf("%d: \n", i);
628  for (j = 0; j < 256; j++) {
629  if (SCACBSGetDelta(i, j, mpm_ctx) != 0) {
630  printf(" %c -> %d\n", j, SCACBSGetDelta(i, j, mpm_ctx));
631  }
632  }
633  }
634 
635  return;
636 }
637 #endif
638 
639 static inline int SCACBSZeroTransitionPresent(SCACBSCtx *ctx, uint32_t state)
640 {
641  if (state == 0)
642  return 1;
643 
644  if (ctx->state_count < 32767) {
645  int ascii;
646  for (ascii = 0; ascii < 256; ascii++) {
647  if ((ctx->state_table_u16[0][ascii] & 0x7fff) == (state & 0x7fff)) {
648  return 1;
649  }
650  }
651 
652  return 0;
653  } else {
654  int ascii;
655  for (ascii = 0; ascii < 256; ascii++) {
656  if ((ctx->state_table_u32[0][ascii] & 0x00FFFFFF) ==
657  (state & 0x00FFFFFF)) {
658  return 1;
659  }
660  }
661 
662  return 0;
663  }
664 }
665 
666 /**
667  * \internal
668  * \brief Creates a new goto table structure(throw out all the failure
669  * transitions), to hold the existing goto table.
670  *
671  * \param mpm_ctx Pointer to the mpm context.
672  */
673 static inline void SCACBSCreateModDeltaTable(MpmCtx *mpm_ctx)
674 {
675  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
676 
677  if (ctx->state_count < 32767) {
678  int size = 0;
679  uint32_t state;
680 
681  for (state = 1; state < ctx->state_count; state++) {
682  int ascii_code;
683  int k = 0;
684  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
685  uint32_t temp_state = ctx->state_table_u16[state][ascii_code];
686  if (SCACBSZeroTransitionPresent(ctx, temp_state))
687  continue;
688  k++;
689  }
690  size += sizeof(uint16_t) * k * 2;
691  }
692 
693  /* Let us use uint16_t for all. That way we don//'t have to worry about
694  * alignment. Technically 8 bits is all we need to store ascii codes,
695  * but by avoiding it, we save a lot of time on handling alignment */
696  size += (ctx->state_count * sizeof(SC_AC_BS_STATE_TYPE_U16) +
697  256 * sizeof(SC_AC_BS_STATE_TYPE_U16) * 1);
698  ctx->state_table_mod = SCMalloc(size);
699  if (ctx->state_table_mod == NULL) {
700  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
701  exit(EXIT_FAILURE);
702  }
703  memset(ctx->state_table_mod, 0, size);
704 
705  mpm_ctx->memory_cnt++;
706  mpm_ctx->memory_size += size;
707 
708  /* buffer to hold pointers in the buffer, so that a state can use it
709  * directly to access its state data */
710  ctx->state_table_mod_pointers = SCMalloc(ctx->state_count * sizeof(uint8_t *));
711  if (ctx->state_table_mod_pointers == NULL) {
712  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
713  exit(EXIT_FAILURE);
714  }
715  memset(ctx->state_table_mod_pointers, 0,
716  ctx->state_count * sizeof(uint8_t *));
717 
718  SC_AC_BS_STATE_TYPE_U16 temp_states[256];
719  uint16_t *curr_loc = (uint16_t *)ctx->state_table_mod;
720  uint16_t *no_of_entries = NULL;
721  uint16_t *ascii_codes = NULL;
722  uint16_t ascii_code = 0;
723  uint16_t k = 0;
724  for (state = 0; state < ctx->state_count; state++) {
725  /* store the starting location in the buffer for this state */
726  ctx->state_table_mod_pointers[state] = (uint8_t *)curr_loc;
727  no_of_entries = curr_loc++;
728  ascii_codes = curr_loc;
729  k = 0;
730  /* store all states that have non 0 transitions in the temp buffer */
731  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
732  uint32_t temp_state = ctx->state_table_u16[state][ascii_code];
733  if (state != 0 && SCACBSZeroTransitionPresent(ctx, temp_state))
734  continue;
735 
736  ascii_codes[k] = ascii_code;
737  temp_states[k] = ctx->state_table_u16[state][ascii_code];
738  k++;
739  }
740  /* if we have any non 0 transitions from our previous for search,
741  * store the acii codes as well the corresponding states */
742  if (k > 0) {
743  no_of_entries[0] = k;
744  if (state != 0)
745  curr_loc += k;
746  memcpy(curr_loc, temp_states, k * sizeof(SC_AC_BS_STATE_TYPE_U16));
747  curr_loc += k;
748  }
749  }
750 
751  /* > 33766 */
752  } else {
753  int size = 0;
754  uint32_t state;
755  for (state = 1; state < ctx->state_count; state++) {
756  int ascii_code;
757  int k = 0;
758  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
759  uint32_t temp_state = ctx->state_table_u32[state][ascii_code];
760  if (SCACBSZeroTransitionPresent(ctx, temp_state))
761  continue;
762  k++;
763  }
764  size += sizeof(uint32_t) * k * 2;
765  }
766 
767  /* Let us use uint32_t for all. That way we don//'t have to worry about
768  * alignment. Technically 8 bits is all we need to store ascii codes,
769  * but by avoiding it, we save a lot of time on handling alignment */
770  size += (ctx->state_count * sizeof(SC_AC_BS_STATE_TYPE_U32) +
771  256 * sizeof(SC_AC_BS_STATE_TYPE_U32) * 1);
772  ctx->state_table_mod = SCMalloc(size);
773  if (ctx->state_table_mod == NULL) {
774  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
775  exit(EXIT_FAILURE);
776  }
777  memset(ctx->state_table_mod, 0, size);
778 
779  mpm_ctx->memory_cnt++;
780  mpm_ctx->memory_size += size;
781 
782  /* buffer to hold pointers in the buffer, so that a state can use it
783  * directly to access its state data */
784  ctx->state_table_mod_pointers = SCMalloc(ctx->state_count * sizeof(uint8_t *));
785  if (ctx->state_table_mod_pointers == NULL) {
786  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
787  exit(EXIT_FAILURE);
788  }
789  memset(ctx->state_table_mod_pointers, 0,
790  ctx->state_count * sizeof(uint8_t *));
791 
792  SC_AC_BS_STATE_TYPE_U32 temp_states[256];
793  uint32_t *curr_loc = (uint32_t *)ctx->state_table_mod;
794  uint32_t *no_of_entries = NULL;
795  uint32_t *ascii_codes = NULL;
796  uint32_t ascii_code = 0;
797  uint32_t k = 0;
798  for (state = 0; state < ctx->state_count; state++) {
799  /* store the starting location in the buffer for this state */
800  ctx->state_table_mod_pointers[state] = (uint8_t *)curr_loc;
801  no_of_entries = curr_loc++;
802  ascii_codes = curr_loc;
803  k = 0;
804  /* store all states that have non 0 transitions in the temp buffer */
805  for (ascii_code = 0; ascii_code < 256; ascii_code++) {
806  uint32_t temp_state = ctx->state_table_u32[state][ascii_code];
807  if (state != 0 && SCACBSZeroTransitionPresent(ctx, temp_state))
808  continue;
809 
810  ascii_codes[k] = ascii_code;
811  temp_states[k] = ctx->state_table_u32[state][ascii_code];
812  k++;
813  }
814  /* if we have any non 0 transitions from our previous for search,
815  * store the acii codes as well the corresponding states */
816  if (k > 0) {
817  no_of_entries[0] = k;
818  if (state != 0)
819  curr_loc += k;
820  memcpy(curr_loc, temp_states, k * sizeof(SC_AC_BS_STATE_TYPE_U32));
821  curr_loc += k;
822  }
823  }
824 
825  }
826 
827  return;
828 }
829 
830 /**
831  * \brief Process the patterns and prepare the state table.
832  *
833  * \param mpm_ctx Pointer to the mpm context.
834  */
835 static inline void SCACBSPrepareStateTable(MpmCtx *mpm_ctx)
836 {
837  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
838 
839  /* create the 0th state in the goto table and output_table */
840  SCACBSInitNewState(mpm_ctx);
841 
842  /* create the goto table */
843  SCACBSCreateGotoTable(mpm_ctx);
844  /* create the failure table */
845  SCACBSCreateFailureTable(mpm_ctx);
846  /* create the final state(delta) table */
847  SCACBSCreateDeltaTable(mpm_ctx);
848  /* club the output state presence with delta transition entries */
849  SCACBSClubOutputStatePresenceWithDeltaTable(mpm_ctx);
850  /* create the modified table */
851  SCACBSCreateModDeltaTable(mpm_ctx);
852 
853  /* club nocase entries */
854  SCACBSInsertCaseSensitiveEntriesForPatterns(mpm_ctx);
855 
856 // int state = 0;
857 // for (state = 0; state < ctx->state_count; state++) {
858 // int i = 0;
859 // for (i = 0; i < 256; i++) {
860 // if (ctx->state_table_u16[state][i] != 0) {
861 // printf("%d-%d-%d\n", state, i, ctx->state_table_u16[state][i] & 0x7fff) ;
862 // }
863 // }
864 // }
865 
866 #if 0
867  SCACBSPrintDeltaTable(mpm_ctx);
868 #endif
869 
870  /* we don't need these anymore */
871  SCFree(ctx->goto_table);
872  ctx->goto_table = NULL;
873  SCFree(ctx->failure_table);
874  ctx->failure_table = NULL;
875  SCFree(ctx->state_table_u16);
876  ctx->state_table_u16 = NULL;
877  SCFree(ctx->state_table_u32);
878  ctx->state_table_u32 = NULL;
879 
880  return;
881 }
882 
883 /**
884  * \brief Process the patterns added to the mpm, and create the internal tables.
885  *
886  * \param mpm_ctx Pointer to the mpm context.
887  */
889 {
890  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
891 
892  if (mpm_ctx->pattern_cnt == 0 || mpm_ctx->init_hash == NULL) {
893  SCLogDebug("no patterns supplied to this mpm_ctx");
894  return 0;
895  }
896 
897  /* alloc the pattern array */
898  ctx->parray = (MpmPattern **)SCMalloc(mpm_ctx->pattern_cnt *
899  sizeof(MpmPattern *));
900  if (ctx->parray == NULL)
901  goto error;
902  memset(ctx->parray, 0, mpm_ctx->pattern_cnt * sizeof(MpmPattern *));
903  mpm_ctx->memory_cnt++;
904  mpm_ctx->memory_size += (mpm_ctx->pattern_cnt * sizeof(MpmPattern *));
905 
906  /* populate it with the patterns in the hash */
907  uint32_t i = 0, p = 0;
908  for (i = 0; i < MPM_INIT_HASH_SIZE; i++) {
909  MpmPattern *node = mpm_ctx->init_hash[i], *nnode = NULL;
910  while(node != NULL) {
911  nnode = node->next;
912  node->next = NULL;
913  ctx->parray[p++] = node;
914  node = nnode;
915  }
916  }
917 
918  /* we no longer need the hash, so free it's memory */
919  SCFree(mpm_ctx->init_hash);
920  mpm_ctx->init_hash = NULL;
921 
922  /* the memory consumed by a single state in our goto table */
923  ctx->single_state_size = sizeof(int32_t) * 256;
924 
925  /* handle no case patterns */
926  ctx->pid_pat_list = SCMalloc((mpm_ctx->max_pat_id + 1)* sizeof(SCACBSPatternList));
927  if (ctx->pid_pat_list == NULL) {
928  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
929  exit(EXIT_FAILURE);
930  }
931  memset(ctx->pid_pat_list, 0, (mpm_ctx->max_pat_id + 1) * sizeof(SCACBSPatternList));
932 
933  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
934  if (!(ctx->parray[i]->flags & MPM_PATTERN_FLAG_NOCASE)) {
935  ctx->pid_pat_list[ctx->parray[i]->id].cs = SCMalloc(ctx->parray[i]->len);
936  if (ctx->pid_pat_list[ctx->parray[i]->id].cs == NULL) {
937  SCLogError(SC_ERR_MEM_ALLOC, "Error allocating memory");
938  exit(EXIT_FAILURE);
939  }
940  memcpy(ctx->pid_pat_list[ctx->parray[i]->id].cs,
941  ctx->parray[i]->original_pat, ctx->parray[i]->len);
942  ctx->pid_pat_list[ctx->parray[i]->id].patlen = ctx->parray[i]->len;
943  }
944 
945  /* ACPatternList now owns this memory */
946  ctx->pid_pat_list[ctx->parray[i]->id].sids_size = ctx->parray[i]->sids_size;
947  ctx->pid_pat_list[ctx->parray[i]->id].sids = ctx->parray[i]->sids;
948  }
949 
950  /* prepare the state table required by AC */
951  SCACBSPrepareStateTable(mpm_ctx);
952 
953  /* free all the stored patterns. Should save us a good 100-200 mbs */
954  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
955  if (ctx->parray[i] != NULL) {
956  MpmFreePattern(mpm_ctx, ctx->parray[i]);
957  }
958  }
959  SCFree(ctx->parray);
960  ctx->parray = NULL;
961  mpm_ctx->memory_cnt--;
962  mpm_ctx->memory_size -= (mpm_ctx->pattern_cnt * sizeof(MpmPattern *));
963 
964  ctx->pattern_id_bitarray_size = (mpm_ctx->max_pat_id / 8) + 1;
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  * \param matchsize We don't need this.
978  */
979 void SCACBSInitThreadCtx(MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)
980 {
981  memset(mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
982 
983  mpm_thread_ctx->ctx = SCMalloc(sizeof(SCACBSThreadCtx));
984  if (mpm_thread_ctx->ctx == NULL) {
985  exit(EXIT_FAILURE);
986  }
987  memset(mpm_thread_ctx->ctx, 0, sizeof(SCACBSThreadCtx));
988  mpm_thread_ctx->memory_cnt++;
989  mpm_thread_ctx->memory_size += sizeof(SCACBSThreadCtx);
990 
991  return;
992 }
993 
994 /**
995  * \brief Initialize the AC context.
996  *
997  * \param mpm_ctx Mpm context.
998  */
999 void SCACBSInitCtx(MpmCtx *mpm_ctx)
1000 {
1001  if (mpm_ctx->ctx != NULL)
1002  return;
1003 
1004  mpm_ctx->ctx = SCMalloc(sizeof(SCACBSCtx));
1005  if (mpm_ctx->ctx == NULL) {
1006  exit(EXIT_FAILURE);
1007  }
1008  memset(mpm_ctx->ctx, 0, sizeof(SCACBSCtx));
1009 
1010  mpm_ctx->memory_cnt++;
1011  mpm_ctx->memory_size += sizeof(SCACBSCtx);
1012 
1013  /* initialize the hash we use to speed up pattern insertions */
1014  mpm_ctx->init_hash = SCMalloc(sizeof(MpmPattern *) * MPM_INIT_HASH_SIZE);
1015  if (mpm_ctx->init_hash == NULL) {
1016  exit(EXIT_FAILURE);
1017  }
1018  memset(mpm_ctx->init_hash, 0, sizeof(MpmPattern *) * MPM_INIT_HASH_SIZE);
1019 
1020  /* get conf values for AC from our yaml file. We have no conf values for
1021  * now. We will certainly need this, as we develop the algo */
1022  SCACBSGetConfig();
1023 
1024  SCReturn;
1025 }
1026 
1027 /**
1028  * \brief Destroy the mpm thread context.
1029  *
1030  * \param mpm_ctx Pointer to the mpm context.
1031  * \param mpm_thread_ctx Pointer to the mpm thread context.
1032  */
1033 void SCACBSDestroyThreadCtx(MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx)
1034 {
1035  SCACBSPrintSearchStats(mpm_thread_ctx);
1036 
1037  if (mpm_thread_ctx->ctx != NULL) {
1038  SCFree(mpm_thread_ctx->ctx);
1039  mpm_thread_ctx->ctx = NULL;
1040  mpm_thread_ctx->memory_cnt--;
1041  mpm_thread_ctx->memory_size -= sizeof(SCACBSThreadCtx);
1042  }
1043 
1044  return;
1045 }
1046 
1047 /**
1048  * \brief Destroy the mpm context.
1049  *
1050  * \param mpm_ctx Pointer to the mpm context.
1051  */
1052 void SCACBSDestroyCtx(MpmCtx *mpm_ctx)
1053 {
1054  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
1055  if (ctx == NULL)
1056  return;
1057 
1058  if (mpm_ctx->init_hash != NULL) {
1059  SCFree(mpm_ctx->init_hash);
1060  mpm_ctx->init_hash = NULL;
1061  mpm_ctx->memory_cnt--;
1062  mpm_ctx->memory_size -= (MPM_INIT_HASH_SIZE * sizeof(MpmPattern *));
1063  }
1064 
1065  if (ctx->parray != NULL) {
1066  uint32_t i;
1067  for (i = 0; i < mpm_ctx->pattern_cnt; i++) {
1068  if (ctx->parray[i] != NULL) {
1069  MpmFreePattern(mpm_ctx, ctx->parray[i]);
1070  }
1071  }
1072 
1073  SCFree(ctx->parray);
1074  ctx->parray = NULL;
1075  mpm_ctx->memory_cnt--;
1076  mpm_ctx->memory_size -= (mpm_ctx->pattern_cnt * sizeof(MpmPattern *));
1077  }
1078 
1079  if (ctx->state_table_u16 != NULL) {
1080  SCFree(ctx->state_table_u16);
1081  ctx->state_table_u16 = NULL;
1082 
1083  mpm_ctx->memory_cnt++;
1084  mpm_ctx->memory_size -= (ctx->state_count *
1085  sizeof(SC_AC_BS_STATE_TYPE_U16) * 256);
1086  } else if (ctx->state_table_u32 != NULL) {
1087  SCFree(ctx->state_table_u32);
1088  ctx->state_table_u32 = NULL;
1089 
1090  mpm_ctx->memory_cnt++;
1091  mpm_ctx->memory_size -= (ctx->state_count *
1092  sizeof(SC_AC_BS_STATE_TYPE_U32) * 256);
1093  }
1094 
1095  if (ctx->output_table != NULL) {
1096  uint32_t state_count;
1097  for (state_count = 0; state_count < ctx->state_count; state_count++) {
1098  if (ctx->output_table[state_count].pids != NULL) {
1099  SCFree(ctx->output_table[state_count].pids);
1100  }
1101  }
1102  SCFree(ctx->output_table);
1103  }
1104 
1105  if (ctx->pid_pat_list != NULL) {
1106  uint32_t i;
1107  for (i = 0; i < (mpm_ctx->max_pat_id + 1); i++) {
1108  if (ctx->pid_pat_list[i].cs != NULL)
1109  SCFree(ctx->pid_pat_list[i].cs);
1110  if (ctx->pid_pat_list[i].sids != NULL)
1111  SCFree(ctx->pid_pat_list[i].sids);
1112  }
1113  SCFree(ctx->pid_pat_list);
1114  }
1115 
1116  if (ctx->state_table_mod != NULL) {
1117  SCFree(ctx->state_table_mod);
1118  ctx->state_table_mod = NULL;
1119  }
1120 
1121  if (ctx->state_table_mod_pointers != NULL) {
1123  ctx->state_table_mod_pointers = NULL;
1124  }
1125 
1126  SCFree(mpm_ctx->ctx);
1127  mpm_ctx->memory_cnt--;
1128  mpm_ctx->memory_size -= sizeof(SCACBSCtx);
1129 
1130  return;
1131 }
1132 
1133 /**
1134  * \brief The aho corasick search function.
1135  *
1136  * \param mpm_ctx Pointer to the mpm context.
1137  * \param mpm_thread_ctx Pointer to the mpm thread context.
1138  * \param pmq Pointer to the Pattern Matcher Queue to hold
1139  * search matches.
1140  * \param buf Buffer to be searched.
1141  * \param buflen Buffer length.
1142  *
1143  * \retval matches Match count.
1144  */
1145 uint32_t SCACBSSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx,
1146  PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
1147 {
1148  const SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
1149  uint32_t i = 0;
1150  int matches = 0;
1151  uint8_t buf_local;
1152 
1153  /* \todo tried loop unrolling with register var, with no perf increase. Need
1154  * to dig deeper */
1155  /* \todo Change it for stateful MPM. Supply the state using mpm_thread_ctx */
1156  SCACBSPatternList *pid_pat_list = ctx->pid_pat_list;
1157 
1158  uint8_t bitarray[ctx->pattern_id_bitarray_size];
1159  memset(bitarray, 0, ctx->pattern_id_bitarray_size);
1160 
1161  if (ctx->state_count < 32767) {
1162  register SC_AC_BS_STATE_TYPE_U16 state = 0;
1163  uint16_t no_of_entries;
1164  uint16_t *ascii_codes;
1165  uint16_t **state_table_mod_pointers = (uint16_t **)ctx->state_table_mod_pointers;
1166  uint16_t *zero_state = state_table_mod_pointers[0] + 1;
1167 
1168  for (i = 0; i < buflen; i++) {
1169  if (state == 0) {
1170  state = zero_state[u8_tolower(buf[i])];
1171  } else {
1172  no_of_entries = *(state_table_mod_pointers[state & 0x7FFF]);
1173  if (no_of_entries == 1) {
1174  ascii_codes = state_table_mod_pointers[state & 0x7FFF] + 1;
1175  buf_local = u8_tolower(buf[i]);
1176  if (buf_local == ascii_codes[0]) {
1177  state = *(ascii_codes + no_of_entries);;
1178  } else {
1179  state = zero_state[buf_local];
1180  }
1181  } else {
1182  if (no_of_entries == 0) {
1183  state = zero_state[u8_tolower(buf[i])];
1184  goto match_u16;
1185  }
1186  buf_local = u8_tolower(buf[i]);
1187  ascii_codes = state_table_mod_pointers[state & 0x7FFF] + 1;
1188  int low = 0;
1189  int high = no_of_entries;
1190  int mid;
1191  while (low <= high) {
1192  mid = (low + high) / 2;
1193  if (ascii_codes[mid] == buf_local) {
1194  state = ((ascii_codes + no_of_entries))[mid];
1195  goto match_u16;
1196  } else if (ascii_codes[mid] < buf_local) {
1197  low = mid + 1;
1198  } else {
1199  high = mid - 1;
1200  }
1201  } /* while */
1202  state = zero_state[buf_local];
1203  } /* else - if (no_of_entires == 1) */
1204  }
1205 
1206  match_u16:
1207  if (state & 0x8000) {
1208  uint32_t nentries = ctx->output_table[state & 0x7FFF].no_of_entries;
1209  uint32_t *pids = ctx->output_table[state & 0x7FFF].pids;
1210  uint32_t k;
1211  for (k = 0; k < nentries; k++) {
1212  if (pids[k] & 0xFFFF0000) {
1213  uint32_t lower_pid = pids[k] & 0x0000FFFF;
1214  if (SCMemcmp(pid_pat_list[lower_pid].cs,
1215  buf + i - pid_pat_list[lower_pid].patlen + 1,
1216  pid_pat_list[lower_pid].patlen) != 0) {
1217  /* inside loop */
1218  continue;
1219  }
1220  if (bitarray[(lower_pid) / 8] & (1 << ((lower_pid) % 8))) {
1221  ;
1222  } else {
1223  bitarray[(lower_pid) / 8] |= (1 << ((lower_pid) % 8));
1224  PrefilterAddSids(pmq, pid_pat_list[lower_pid].sids,
1225  pid_pat_list[lower_pid].sids_size);
1226  }
1227  matches++;
1228  } else {
1229  if (bitarray[pids[k] / 8] & (1 << (pids[k] % 8))) {
1230  ;
1231  } else {
1232  bitarray[pids[k] / 8] |= (1 << (pids[k] % 8));
1233  PrefilterAddSids(pmq, pid_pat_list[pids[k]].sids,
1234  pid_pat_list[pids[k]].sids_size);
1235  }
1236  matches++;
1237  }
1238  //loop1:
1239  //;
1240  }
1241  }
1242  } /* for (i = 0; i < buflen; i++) */
1243 
1244  } else {
1245  register SC_AC_BS_STATE_TYPE_U32 state = 0;
1246  uint32_t no_of_entries;
1247  uint32_t *ascii_codes;
1248  uint32_t **state_table_mod_pointers = (uint32_t **)ctx->state_table_mod_pointers;
1249  uint32_t *zero_state = state_table_mod_pointers[0] + 1;
1250 
1251  for (i = 0; i < buflen; i++) {
1252  if (state == 0) {
1253  state = zero_state[u8_tolower(buf[i])];
1254  } else {
1255  no_of_entries = *(state_table_mod_pointers[state & 0x00FFFFFF]);
1256  if (no_of_entries == 1) {
1257  ascii_codes = state_table_mod_pointers[state & 0x00FFFFFF] + 1;
1258  buf_local = u8_tolower(buf[i]);
1259  if (buf_local == ascii_codes[0]) {
1260  state = *(ascii_codes + no_of_entries);;
1261  } else {
1262  state = zero_state[buf_local];;
1263  }
1264  } else {
1265  if (no_of_entries == 0) {
1266  state = zero_state[u8_tolower(buf[i])];
1267  goto match_u32;
1268  }
1269  buf_local = u8_tolower(buf[i]);
1270  ascii_codes = state_table_mod_pointers[state & 0x00FFFFFF] + 1;
1271  int low = 0;
1272  int high = no_of_entries;
1273  int mid;
1274  while (low <= high) {
1275  mid = (low + high) / 2;
1276  if (ascii_codes[mid] == buf_local) {
1277  state = ((ascii_codes + no_of_entries))[mid];
1278  goto match_u32;
1279  } else if (ascii_codes[mid] < buf_local) {
1280  low = mid + 1;
1281  } else {
1282  high = mid - 1;
1283  }
1284  } /* while */
1285  state = zero_state[buf_local];
1286  } /* else - if (no_of_entires == 1) */
1287  }
1288 
1289  match_u32:
1290  if (state & 0xFF000000) {
1291  uint32_t nentries = ctx->output_table[state & 0x00FFFFFF].no_of_entries;
1292  uint32_t *pids = ctx->output_table[state & 0x00FFFFFF].pids;
1293  uint32_t k;
1294  for (k = 0; k < nentries; k++) {
1295  if (pids[k] & 0xFFFF0000) {
1296  uint32_t lower_pid = pids[k] & 0x0000FFFF;
1297  if (SCMemcmp(pid_pat_list[lower_pid].cs,
1298  buf + i - pid_pat_list[lower_pid].patlen + 1,
1299  pid_pat_list[lower_pid].patlen) != 0) {
1300  /* inside loop */
1301  continue;
1302  }
1303  if (bitarray[(lower_pid) / 8] & (1 << ((lower_pid) % 8))) {
1304  ;
1305  } else {
1306  bitarray[(lower_pid) / 8] |= (1 << ((lower_pid) % 8));
1307  PrefilterAddSids(pmq, pid_pat_list[lower_pid].sids,
1308  pid_pat_list[lower_pid].sids_size);
1309  }
1310  matches++;
1311  } else {
1312  if (bitarray[pids[k] / 8] & (1 << (pids[k] % 8))) {
1313  ;
1314  } else {
1315  bitarray[pids[k] / 8] |= (1 << (pids[k] % 8));
1316  PrefilterAddSids(pmq, pid_pat_list[pids[k]].sids,
1317  pid_pat_list[pids[k]].sids_size);
1318  }
1319  matches++;
1320  }
1321  //loop1:
1322  //;
1323  }
1324  }
1325  } /* for (i = 0; i < buflen; i++) */
1326  }
1327 
1328  return matches;
1329 }
1330 
1331 /**
1332  * \brief Add a case insensitive pattern. Although we have different calls for
1333  * adding case sensitive and insensitive patterns, we make a single call
1334  * for either case. No special treatment for either case.
1335  *
1336  * \param mpm_ctx Pointer to the mpm context.
1337  * \param pat The pattern to add.
1338  * \param patnen The pattern length.
1339  * \param offset Ignored.
1340  * \param depth Ignored.
1341  * \param pid The pattern id.
1342  * \param sid Ignored.
1343  * \param flags Flags associated with this pattern.
1344  *
1345  * \retval 0 On success.
1346  * \retval -1 On failure.
1347  */
1348 int SCACBSAddPatternCI(MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen,
1349  uint16_t offset, uint16_t depth, uint32_t pid,
1350  SigIntId sid, uint8_t flags)
1351 {
1352  flags |= MPM_PATTERN_FLAG_NOCASE;
1353  return MpmAddPattern(mpm_ctx, pat, patlen, offset, depth, pid, sid, flags);
1354 }
1355 
1356 /**
1357  * \brief Add a case sensitive pattern. Although we have different calls for
1358  * adding case sensitive and insensitive patterns, we make a single call
1359  * for either case. No special treatment for either case.
1360  *
1361  * \param mpm_ctx Pointer to the mpm context.
1362  * \param pat The pattern to add.
1363  * \param patnen The pattern length.
1364  * \param offset Ignored.
1365  * \param depth Ignored.
1366  * \param pid The pattern id.
1367  * \param sid Ignored.
1368  * \param flags Flags associated with this pattern.
1369  *
1370  * \retval 0 On success.
1371  * \retval -1 On failure.
1372  */
1373 int SCACBSAddPatternCS(MpmCtx *mpm_ctx, uint8_t *pat, uint16_t patlen,
1374  uint16_t offset, uint16_t depth, uint32_t pid,
1375  SigIntId sid, uint8_t flags)
1376 {
1377  return MpmAddPattern(mpm_ctx, pat, patlen, offset, depth, pid, sid, flags);
1378 }
1379 
1381 {
1382 
1383 #ifdef SC_AC_BS_COUNTERS
1384  SCACBSThreadCtx *ctx = (SCACBSThreadCtx *)mpm_thread_ctx->ctx;
1385  printf("AC Thread Search stats (ctx %p)\n", ctx);
1386  printf("Total calls: %" PRIu32 "\n", ctx->total_calls);
1387  printf("Total matches: %" PRIu64 "\n", ctx->total_matches);
1388 #endif /* SC_AC_BS_COUNTERS */
1389 
1390  return;
1391 }
1392 
1393 void SCACBSPrintInfo(MpmCtx *mpm_ctx)
1394 {
1395  SCACBSCtx *ctx = (SCACBSCtx *)mpm_ctx->ctx;
1396 
1397  printf("MPM AC Information:\n");
1398  printf("Memory allocs: %" PRIu32 "\n", mpm_ctx->memory_cnt);
1399  printf("Memory alloced: %" PRIu32 "\n", mpm_ctx->memory_size);
1400  printf(" Sizeof:\n");
1401  printf(" MpmCtx %" PRIuMAX "\n", (uintmax_t)sizeof(MpmCtx));
1402  printf(" SCACBSCtx: %" PRIuMAX "\n", (uintmax_t)sizeof(SCACBSCtx));
1403  printf(" MpmPattern %" PRIuMAX "\n", (uintmax_t)sizeof(MpmPattern));
1404  printf(" MpmPattern %" PRIuMAX "\n", (uintmax_t)sizeof(MpmPattern));
1405  printf("Unique Patterns: %" PRIu32 "\n", mpm_ctx->pattern_cnt);
1406  printf("Smallest: %" PRIu32 "\n", mpm_ctx->minlen);
1407  printf("Largest: %" PRIu32 "\n", mpm_ctx->maxlen);
1408  printf("Total states in the state table: %" PRIu32 "\n", ctx->state_count);
1409  printf("\n");
1410 
1411  return;
1412 }
1413 
1414 /*************************************Unittests********************************/
1415 
1416 #ifdef UNITTESTS
1417 
1418 static int SCACBSTest01(void)
1419 {
1420  int result = 0;
1421  MpmCtx mpm_ctx;
1422  MpmThreadCtx mpm_thread_ctx;
1423  PrefilterRuleStore pmq;
1424 
1425  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1426  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1427  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1428  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1429 
1430  /* 1 match */
1431  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1432  PmqSetup(&pmq);
1433 
1434  SCACBSPreparePatterns(&mpm_ctx);
1435 
1436  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1437 
1438  uint32_t cnt = SCACBSSearch(&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  SCACBSDestroyCtx(&mpm_ctx);
1447  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1448  PmqFree(&pmq);
1449  return result;
1450 }
1451 
1452 static int SCACBSTest02(void)
1453 {
1454  int result = 0;
1455  MpmCtx mpm_ctx;
1456  MpmThreadCtx mpm_thread_ctx;
1457  PrefilterRuleStore pmq;
1458 
1459  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1460  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1461  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1462  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1463 
1464  /* 1 match */
1465  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abce", 4, 0, 0, 0, 0, 0);
1466  PmqSetup(&pmq);
1467 
1468  SCACBSPreparePatterns(&mpm_ctx);
1469 
1470  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1471  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1472  (uint8_t *)buf, strlen(buf));
1473 
1474  if (cnt == 0)
1475  result = 1;
1476  else
1477  printf("0 != %" PRIu32 " ",cnt);
1478 
1479  SCACBSDestroyCtx(&mpm_ctx);
1480  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1481  PmqFree(&pmq);
1482  return result;
1483 }
1484 
1485 static int SCACBSTest03(void)
1486 {
1487  int result = 0;
1488  MpmCtx mpm_ctx;
1489  MpmThreadCtx mpm_thread_ctx;
1490  PrefilterRuleStore pmq;
1491 
1492  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1493  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1494  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1495  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1496 
1497  /* 1 match */
1498  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1499  /* 1 match */
1500  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"bcde", 4, 0, 0, 1, 0, 0);
1501  /* 1 match */
1502  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"fghj", 4, 0, 0, 2, 0, 0);
1503  PmqSetup(&pmq);
1504 
1505  SCACBSPreparePatterns(&mpm_ctx);
1506 
1507  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1508  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1509  (uint8_t *)buf, strlen(buf));
1510 
1511  if (cnt == 3)
1512  result = 1;
1513  else
1514  printf("3 != %" PRIu32 " ",cnt);
1515 
1516  SCACBSDestroyCtx(&mpm_ctx);
1517  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1518  PmqFree(&pmq);
1519  return result;
1520 }
1521 
1522 static int SCACBSTest04(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_BS);
1532  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1533 
1534  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1535  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"bcdegh", 6, 0, 0, 1, 0, 0);
1536  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"fghjxyz", 7, 0, 0, 2, 0, 0);
1537  PmqSetup(&pmq);
1538 
1539  SCACBSPreparePatterns(&mpm_ctx);
1540 
1541  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1542  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1543  (uint8_t *)buf, strlen(buf));
1544 
1545  if (cnt == 1)
1546  result = 1;
1547  else
1548  printf("1 != %" PRIu32 " ",cnt);
1549 
1550  SCACBSDestroyCtx(&mpm_ctx);
1551  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1552  PmqFree(&pmq);
1553  return result;
1554 }
1555 
1556 static int SCACBSTest05(void)
1557 {
1558  int result = 0;
1559  MpmCtx mpm_ctx;
1560  MpmThreadCtx mpm_thread_ctx;
1561  PrefilterRuleStore pmq;
1562 
1563  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1564  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1565  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1566  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1567 
1568  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"ABCD", 4, 0, 0, 0, 0, 0);
1569  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"bCdEfG", 6, 0, 0, 1, 0, 0);
1570  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"fghJikl", 7, 0, 0, 2, 0, 0);
1571  PmqSetup(&pmq);
1572 
1573  SCACBSPreparePatterns(&mpm_ctx);
1574 
1575  const char *buf = "abcdefghjiklmnopqrstuvwxyz";
1576  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1577  (uint8_t *)buf, strlen(buf));
1578 
1579  if (cnt == 3)
1580  result = 1;
1581  else
1582  printf("3 != %" PRIu32 " ",cnt);
1583 
1584  SCACBSDestroyCtx(&mpm_ctx);
1585  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1586  PmqFree(&pmq);
1587  return result;
1588 }
1589 
1590 static int SCACBSTest06(void)
1591 {
1592  int result = 0;
1593  MpmCtx mpm_ctx;
1594  MpmThreadCtx mpm_thread_ctx;
1595  PrefilterRuleStore pmq;
1596 
1597  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1598  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1599  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1600  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1601 
1602  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1603  PmqSetup(&pmq);
1604 
1605  SCACBSPreparePatterns(&mpm_ctx);
1606 
1607  const char *buf = "abcd";
1608  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1609  (uint8_t *)buf, strlen(buf));
1610 
1611  if (cnt == 1)
1612  result = 1;
1613  else
1614  printf("1 != %" PRIu32 " ",cnt);
1615 
1616  SCACBSDestroyCtx(&mpm_ctx);
1617  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1618  PmqFree(&pmq);
1619  return result;
1620 }
1621 
1622 static int SCACBSTest07(void)
1623 {
1624  int result = 0;
1625  MpmCtx mpm_ctx;
1626  MpmThreadCtx mpm_thread_ctx;
1627  PrefilterRuleStore pmq;
1628 
1629  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1630  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1631  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1632  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1633 
1634  /* should match 30 times */
1635  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"A", 1, 0, 0, 0, 0, 0);
1636  /* should match 29 times */
1637  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 1, 0, 0);
1638  /* should match 28 times */
1639  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAA", 3, 0, 0, 2, 0, 0);
1640  /* 26 */
1641  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAA", 5, 0, 0, 3, 0, 0);
1642  /* 21 */
1643  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAAAAAAA", 10, 0, 0, 4, 0, 0);
1644  /* 1 */
1645  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA",
1646  30, 0, 0, 5, 0, 0);
1647  PmqSetup(&pmq);
1648  /* total matches: 135 */
1649 
1650  SCACBSPreparePatterns(&mpm_ctx);
1651 
1652  const char *buf = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
1653  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1654  (uint8_t *)buf, strlen(buf));
1655 
1656  if (cnt == 135)
1657  result = 1;
1658  else
1659  printf("135 != %" PRIu32 " ",cnt);
1660 
1661  SCACBSDestroyCtx(&mpm_ctx);
1662  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1663  PmqFree(&pmq);
1664  return result;
1665 }
1666 
1667 static int SCACBSTest08(void)
1668 {
1669  int result = 0;
1670  MpmCtx mpm_ctx;
1671  MpmThreadCtx mpm_thread_ctx;
1672  PrefilterRuleStore pmq;
1673 
1674  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1675  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1676  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1677  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1678 
1679  /* 1 match */
1680  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
1681  PmqSetup(&pmq);
1682 
1683  SCACBSPreparePatterns(&mpm_ctx);
1684 
1685  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1686  (uint8_t *)"a", 1);
1687 
1688  if (cnt == 0)
1689  result = 1;
1690  else
1691  printf("0 != %" PRIu32 " ",cnt);
1692 
1693  SCACBSDestroyCtx(&mpm_ctx);
1694  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1695  PmqFree(&pmq);
1696  return result;
1697 }
1698 
1699 static int SCACBSTest09(void)
1700 {
1701  int result = 0;
1702  MpmCtx mpm_ctx;
1703  MpmThreadCtx mpm_thread_ctx;
1704  PrefilterRuleStore pmq;
1705 
1706  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1707  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1708  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1709  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1710 
1711  /* 1 match */
1712  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"ab", 2, 0, 0, 0, 0, 0);
1713  PmqSetup(&pmq);
1714 
1715  SCACBSPreparePatterns(&mpm_ctx);
1716 
1717  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1718  (uint8_t *)"ab", 2);
1719 
1720  if (cnt == 1)
1721  result = 1;
1722  else
1723  printf("1 != %" PRIu32 " ",cnt);
1724 
1725  SCACBSDestroyCtx(&mpm_ctx);
1726  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1727  PmqFree(&pmq);
1728  return result;
1729 }
1730 
1731 static int SCACBSTest10(void)
1732 {
1733  int result = 0;
1734  MpmCtx mpm_ctx;
1735  MpmThreadCtx mpm_thread_ctx;
1736  PrefilterRuleStore pmq;
1737 
1738  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1739  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1740  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1741  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1742 
1743  /* 1 match */
1744  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcdefgh", 8, 0, 0, 0, 0, 0);
1745  PmqSetup(&pmq);
1746 
1747  SCACBSPreparePatterns(&mpm_ctx);
1748 
1749  const char *buf = "01234567890123456789012345678901234567890123456789"
1750  "01234567890123456789012345678901234567890123456789"
1751  "abcdefgh"
1752  "01234567890123456789012345678901234567890123456789"
1753  "01234567890123456789012345678901234567890123456789";
1754  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1755  (uint8_t *)buf, strlen(buf));
1756 
1757  if (cnt == 1)
1758  result = 1;
1759  else
1760  printf("1 != %" PRIu32 " ",cnt);
1761 
1762  SCACBSDestroyCtx(&mpm_ctx);
1763  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1764  PmqFree(&pmq);
1765  return result;
1766 }
1767 
1768 static int SCACBSTest11(void)
1769 {
1770  int result = 0;
1771  MpmCtx mpm_ctx;
1772  MpmThreadCtx mpm_thread_ctx;
1773  PrefilterRuleStore pmq;
1774 
1775  memset(&mpm_ctx, 0, sizeof(MpmCtx));
1776  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1777  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1778  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1779 
1780  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"he", 2, 0, 0, 1, 0, 0) == -1)
1781  goto end;
1782  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"she", 3, 0, 0, 2, 0, 0) == -1)
1783  goto end;
1784  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"his", 3, 0, 0, 3, 0, 0) == -1)
1785  goto end;
1786  if (MpmAddPatternCS(&mpm_ctx, (uint8_t *)"hers", 4, 0, 0, 4, 0, 0) == -1)
1787  goto end;
1788  PmqSetup(&pmq);
1789 
1790  if (SCACBSPreparePatterns(&mpm_ctx) == -1)
1791  goto end;
1792 
1793  result = 1;
1794 
1795  const char *buf = "he";
1796  result &= (SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1797  strlen(buf)) == 1);
1798  buf = "she";
1799  result &= (SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1800  strlen(buf)) == 2);
1801  buf = "his";
1802  result &= (SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1803  strlen(buf)) == 1);
1804  buf = "hers";
1805  result &= (SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq, (uint8_t *)buf,
1806  strlen(buf)) == 2);
1807 
1808  end:
1809  SCACBSDestroyCtx(&mpm_ctx);
1810  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1811  PmqFree(&pmq);
1812  return result;
1813 }
1814 
1815 static int SCACBSTest12(void)
1816 {
1817  int result = 0;
1818  MpmCtx mpm_ctx;
1819  MpmThreadCtx mpm_thread_ctx;
1820  PrefilterRuleStore pmq;
1821 
1822  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1823  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1824  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1825  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1826 
1827  /* 1 match */
1828  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"wxyz", 4, 0, 0, 0, 0, 0);
1829  /* 1 match */
1830  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"vwxyz", 5, 0, 0, 1, 0, 0);
1831  PmqSetup(&pmq);
1832 
1833  SCACBSPreparePatterns(&mpm_ctx);
1834 
1835  const char *buf = "abcdefghijklmnopqrstuvwxyz";
1836  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1837  (uint8_t *)buf, strlen(buf));
1838 
1839  if (cnt == 2)
1840  result = 1;
1841  else
1842  printf("2 != %" PRIu32 " ",cnt);
1843 
1844  SCACBSDestroyCtx(&mpm_ctx);
1845  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1846  PmqFree(&pmq);
1847  return result;
1848 }
1849 
1850 static int SCACBSTest13(void)
1851 {
1852  int result = 0;
1853  MpmCtx mpm_ctx;
1854  MpmThreadCtx mpm_thread_ctx;
1855  PrefilterRuleStore pmq;
1856 
1857  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1858  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1859  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1860  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1861 
1862  /* 1 match */
1863  const char *pat = "abcdefghijklmnopqrstuvwxyzABCD";
1864  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, strlen(pat), 0, 0, 0, 0, 0);
1865  PmqSetup(&pmq);
1866 
1867  SCACBSPreparePatterns(&mpm_ctx);
1868 
1869  const char *buf = "abcdefghijklmnopqrstuvwxyzABCD";
1870  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1871  (uint8_t *)buf, strlen(buf));
1872 
1873  if (cnt == 1)
1874  result = 1;
1875  else
1876  printf("1 != %" PRIu32 " ",cnt);
1877 
1878  SCACBSDestroyCtx(&mpm_ctx);
1879  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1880  PmqFree(&pmq);
1881  return result;
1882 }
1883 
1884 static int SCACBSTest14(void)
1885 {
1886  int result = 0;
1887  MpmCtx mpm_ctx;
1888  MpmThreadCtx mpm_thread_ctx;
1889  PrefilterRuleStore pmq;
1890 
1891  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1892  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1893  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1894  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1895 
1896  /* 1 match */
1897  const char *pat = "abcdefghijklmnopqrstuvwxyzABCDE";
1898  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, strlen(pat), 0, 0, 0, 0, 0);
1899  PmqSetup(&pmq);
1900 
1901  SCACBSPreparePatterns(&mpm_ctx);
1902 
1903  const char *buf = "abcdefghijklmnopqrstuvwxyzABCDE";
1904  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1905  (uint8_t *)buf, strlen(buf));
1906 
1907  if (cnt == 1)
1908  result = 1;
1909  else
1910  printf("1 != %" PRIu32 " ",cnt);
1911 
1912  SCACBSDestroyCtx(&mpm_ctx);
1913  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1914  PmqFree(&pmq);
1915  return result;
1916 }
1917 
1918 static int SCACBSTest15(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_BS);
1928  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1929 
1930  /* 1 match */
1931  const char *pat = "abcdefghijklmnopqrstuvwxyzABCDEF";
1932  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, strlen(pat), 0, 0, 0, 0, 0);
1933  PmqSetup(&pmq);
1934 
1935  SCACBSPreparePatterns(&mpm_ctx);
1936 
1937  const char *buf = "abcdefghijklmnopqrstuvwxyzABCDEF";
1938  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1939  (uint8_t *)buf, strlen(buf));
1940 
1941  if (cnt == 1)
1942  result = 1;
1943  else
1944  printf("1 != %" PRIu32 " ",cnt);
1945 
1946  SCACBSDestroyCtx(&mpm_ctx);
1947  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1948  PmqFree(&pmq);
1949  return result;
1950 }
1951 
1952 static int SCACBSTest16(void)
1953 {
1954  int result = 0;
1955  MpmCtx mpm_ctx;
1956  MpmThreadCtx mpm_thread_ctx;
1957  PrefilterRuleStore pmq;
1958 
1959  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1960  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1961  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1962  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1963 
1964  /* 1 match */
1965  const char *pat = "abcdefghijklmnopqrstuvwxyzABC";
1966  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, strlen(pat), 0, 0, 0, 0, 0);
1967  PmqSetup(&pmq);
1968 
1969  SCACBSPreparePatterns(&mpm_ctx);
1970 
1971  const char *buf = "abcdefghijklmnopqrstuvwxyzABC";
1972  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
1973  (uint8_t *)buf, strlen(buf));
1974 
1975  if (cnt == 1)
1976  result = 1;
1977  else
1978  printf("1 != %" PRIu32 " ",cnt);
1979 
1980  SCACBSDestroyCtx(&mpm_ctx);
1981  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1982  PmqFree(&pmq);
1983  return result;
1984 }
1985 
1986 static int SCACBSTest17(void)
1987 {
1988  int result = 0;
1989  MpmCtx mpm_ctx;
1990  MpmThreadCtx mpm_thread_ctx;
1991  PrefilterRuleStore pmq;
1992 
1993  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
1994  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
1995  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
1996  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
1997 
1998  /* 1 match */
1999  const char *pat = "abcdefghijklmnopqrstuvwxyzAB";
2000  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, strlen(pat), 0, 0, 0, 0, 0);
2001  PmqSetup(&pmq);
2002 
2003  SCACBSPreparePatterns(&mpm_ctx);
2004 
2005  const char *buf = "abcdefghijklmnopqrstuvwxyzAB";
2006  uint32_t cnt = SCACBSSearch(&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  SCACBSDestroyCtx(&mpm_ctx);
2015  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2016  PmqFree(&pmq);
2017  return result;
2018 }
2019 
2020 static int SCACBSTest18(void)
2021 {
2022  int result = 0;
2023  MpmCtx mpm_ctx;
2024  MpmThreadCtx mpm_thread_ctx;
2025  PrefilterRuleStore pmq;
2026 
2027  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2028  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2029  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2030  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2031 
2032  /* 1 match */
2033  const char *pat = "abcde""fghij""klmno""pqrst""uvwxy""z";
2034  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, strlen(pat), 0, 0, 0, 0, 0);
2035  PmqSetup(&pmq);
2036 
2037  SCACBSPreparePatterns(&mpm_ctx);
2038 
2039  const char *buf = "abcde""fghij""klmno""pqrst""uvwxy""z";
2040  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2041  (uint8_t *)buf, strlen(buf));
2042 
2043  if (cnt == 1)
2044  result = 1;
2045  else
2046  printf("1 != %" PRIu32 " ",cnt);
2047 
2048  SCACBSDestroyCtx(&mpm_ctx);
2049  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2050  PmqFree(&pmq);
2051  return result;
2052 }
2053 
2054 static int SCACBSTest19(void)
2055 {
2056  int result = 0;
2057  MpmCtx mpm_ctx;
2058  MpmThreadCtx mpm_thread_ctx;
2059  PrefilterRuleStore pmq;
2060 
2061  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2062  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2063  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2064  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2065 
2066  /* 1 */
2067  const char *pat = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
2068  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, strlen(pat), 0, 0, 0, 0, 0);
2069  PmqSetup(&pmq);
2070 
2071  SCACBSPreparePatterns(&mpm_ctx);
2072 
2073  const char *buf = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
2074  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2075  (uint8_t *)buf, strlen(buf));
2076 
2077  if (cnt == 1)
2078  result = 1;
2079  else
2080  printf("1 != %" PRIu32 " ",cnt);
2081 
2082  SCACBSDestroyCtx(&mpm_ctx);
2083  PmqFree(&pmq);
2084  return result;
2085 }
2086 
2087 static int SCACBSTest20(void)
2088 {
2089  int result = 0;
2090  MpmCtx mpm_ctx;
2091  MpmThreadCtx mpm_thread_ctx;
2092  PrefilterRuleStore pmq;
2093 
2094  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2095  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2096  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2097  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2098 
2099  /* 1 */
2100  const char *pat = "AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AA";
2101  MpmAddPatternCS(&mpm_ctx, (uint8_t *)pat, strlen(pat), 0, 0, 0, 0, 0);
2102  PmqSetup(&pmq);
2103 
2104  SCACBSPreparePatterns(&mpm_ctx);
2105 
2106  const char *buf = "AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AAAAA""AA";
2107  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2108  (uint8_t *)buf, strlen(buf));
2109 
2110  if (cnt == 1)
2111  result = 1;
2112  else
2113  printf("1 != %" PRIu32 " ",cnt);
2114 
2115  SCACBSDestroyCtx(&mpm_ctx);
2116  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2117  PmqFree(&pmq);
2118  return result;
2119 }
2120 
2121 static int SCACBSTest21(void)
2122 {
2123  int result = 0;
2124  MpmCtx mpm_ctx;
2125  MpmThreadCtx mpm_thread_ctx;
2126  PrefilterRuleStore pmq;
2127 
2128  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2129  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2130  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2131  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2132 
2133  /* 1 */
2134  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2135  PmqSetup(&pmq);
2136 
2137  SCACBSPreparePatterns(&mpm_ctx);
2138 
2139  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2140  (uint8_t *)"AA", 2);
2141 
2142  if (cnt == 1)
2143  result = 1;
2144  else
2145  printf("1 != %" PRIu32 " ",cnt);
2146 
2147  SCACBSDestroyCtx(&mpm_ctx);
2148  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2149  PmqFree(&pmq);
2150  return result;
2151 }
2152 
2153 static int SCACBSTest22(void)
2154 {
2155  int result = 0;
2156  MpmCtx mpm_ctx;
2157  MpmThreadCtx mpm_thread_ctx;
2158  PrefilterRuleStore pmq;
2159 
2160  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2161  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2162  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2163  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2164 
2165  /* 1 match */
2166  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcd", 4, 0, 0, 0, 0, 0);
2167  /* 1 match */
2168  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcde", 5, 0, 0, 1, 0, 0);
2169  PmqSetup(&pmq);
2170 
2171  SCACBSPreparePatterns(&mpm_ctx);
2172 
2173  const char *buf = "abcdefghijklmnopqrstuvwxyz";
2174  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2175  (uint8_t *)buf, strlen(buf));
2176 
2177  if (cnt == 2)
2178  result = 1;
2179  else
2180  printf("2 != %" PRIu32 " ",cnt);
2181 
2182  SCACBSDestroyCtx(&mpm_ctx);
2183  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2184  PmqFree(&pmq);
2185  return result;
2186 }
2187 
2188 static int SCACBSTest23(void)
2189 {
2190  int result = 0;
2191  MpmCtx mpm_ctx;
2192  MpmThreadCtx mpm_thread_ctx;
2193  PrefilterRuleStore pmq;
2194 
2195  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2196  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2197  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2198  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2199 
2200  /* 1 */
2201  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2202  PmqSetup(&pmq);
2203 
2204  SCACBSPreparePatterns(&mpm_ctx);
2205 
2206  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2207  (uint8_t *)"aa", 2);
2208 
2209  if (cnt == 0)
2210  result = 1;
2211  else
2212  printf("1 != %" PRIu32 " ",cnt);
2213 
2214  SCACBSDestroyCtx(&mpm_ctx);
2215  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2216  PmqFree(&pmq);
2217  return result;
2218 }
2219 
2220 static int SCACBSTest24(void)
2221 {
2222  int result = 0;
2223  MpmCtx mpm_ctx;
2224  MpmThreadCtx mpm_thread_ctx;
2225  PrefilterRuleStore pmq;
2226 
2227  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2228  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2229  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2230  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2231 
2232  /* 1 */
2233  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"AA", 2, 0, 0, 0, 0, 0);
2234  PmqSetup(&pmq);
2235 
2236  SCACBSPreparePatterns(&mpm_ctx);
2237 
2238  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2239  (uint8_t *)"aa", 2);
2240 
2241  if (cnt == 1)
2242  result = 1;
2243  else
2244  printf("1 != %" PRIu32 " ",cnt);
2245 
2246  SCACBSDestroyCtx(&mpm_ctx);
2247  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2248  PmqFree(&pmq);
2249  return result;
2250 }
2251 
2252 static int SCACBSTest25(void)
2253 {
2254  int result = 0;
2255  MpmCtx mpm_ctx;
2256  MpmThreadCtx mpm_thread_ctx;
2257  PrefilterRuleStore pmq;
2258 
2259  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2260  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2261  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2262  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2263 
2264  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"ABCD", 4, 0, 0, 0, 0, 0);
2265  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"bCdEfG", 6, 0, 0, 1, 0, 0);
2266  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"fghiJkl", 7, 0, 0, 2, 0, 0);
2267  PmqSetup(&pmq);
2268 
2269  SCACBSPreparePatterns(&mpm_ctx);
2270 
2271  const char *buf = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
2272  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2273  (uint8_t *)buf, strlen(buf));
2274 
2275  if (cnt == 3)
2276  result = 1;
2277  else
2278  printf("3 != %" PRIu32 " ",cnt);
2279 
2280  SCACBSDestroyCtx(&mpm_ctx);
2281  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2282  PmqFree(&pmq);
2283  return result;
2284 }
2285 
2286 static int SCACBSTest26(void)
2287 {
2288  int result = 0;
2289  MpmCtx mpm_ctx;
2290  MpmThreadCtx mpm_thread_ctx;
2291  PrefilterRuleStore pmq;
2292 
2293  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2294  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2295  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2296  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2297 
2298  MpmAddPatternCI(&mpm_ctx, (uint8_t *)"Works", 5, 0, 0, 0, 0, 0);
2299  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"Works", 5, 0, 0, 1, 0, 0);
2300  PmqSetup(&pmq);
2301 
2302  SCACBSPreparePatterns(&mpm_ctx);
2303 
2304  const char *buf = "works";
2305  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2306  (uint8_t *)buf, strlen(buf));
2307 
2308  if (cnt == 1)
2309  result = 1;
2310  else
2311  printf("3 != %" PRIu32 " ",cnt);
2312 
2313  SCACBSDestroyCtx(&mpm_ctx);
2314  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2315  PmqFree(&pmq);
2316  return result;
2317 }
2318 
2319 static int SCACBSTest27(void)
2320 {
2321  int result = 0;
2322  MpmCtx mpm_ctx;
2323  MpmThreadCtx mpm_thread_ctx;
2324  PrefilterRuleStore pmq;
2325 
2326  memset(&mpm_ctx, 0, sizeof(MpmCtx));
2327  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2328  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2329  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2330 
2331  /* 0 match */
2332  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"ONE", 3, 0, 0, 0, 0, 0);
2333  PmqSetup(&pmq);
2334 
2335  SCACBSPreparePatterns(&mpm_ctx);
2336 
2337  const char *buf = "tone";
2338  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2339  (uint8_t *)buf, strlen(buf));
2340 
2341  if (cnt == 0)
2342  result = 1;
2343  else
2344  printf("0 != %" PRIu32 " ",cnt);
2345 
2346  SCACBSDestroyCtx(&mpm_ctx);
2347  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2348  PmqFree(&pmq);
2349  return result;
2350 }
2351 
2352 static int SCACBSTest28(void)
2353 {
2354  int result = 0;
2355  MpmCtx mpm_ctx;
2356  MpmThreadCtx mpm_thread_ctx;
2357  PrefilterRuleStore pmq;
2358 
2359  memset(&mpm_ctx, 0, sizeof(MpmCtx));
2360  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2361  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2362  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2363 
2364  /* 0 match */
2365  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"one", 3, 0, 0, 0, 0, 0);
2366  PmqSetup(&pmq);
2367 
2368  SCACBSPreparePatterns(&mpm_ctx);
2369 
2370  const char *buf = "tONE";
2371  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2372  (uint8_t *)buf, strlen(buf));
2373 
2374  if (cnt == 0)
2375  result = 1;
2376  else
2377  printf("0 != %" PRIu32 " ",cnt);
2378 
2379  SCACBSDestroyCtx(&mpm_ctx);
2380  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2381  PmqFree(&pmq);
2382  return result;
2383 }
2384 
2385 static int SCACBSTest29(void)
2386 {
2387  int result = 0;
2388  MpmCtx mpm_ctx;
2389  MpmThreadCtx mpm_thread_ctx;
2390  PrefilterRuleStore pmq;
2391 
2392  memset(&mpm_ctx, 0x00, sizeof(MpmCtx));
2393  memset(&mpm_thread_ctx, 0, sizeof(MpmThreadCtx));
2394  MpmInitCtx(&mpm_ctx, MPM_AC_BS);
2395  SCACBSInitThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2396 
2397  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"abcde", 5, 0, 0, 0, 0, 0);
2398  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"bcdef", 5, 0, 0, 1, 0, 0);
2399  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"cdefg", 5, 0, 0, 3, 0, 0);
2400  MpmAddPatternCS(&mpm_ctx, (uint8_t *)"defgh", 5, 0, 0, 4, 0, 0);
2401  PmqSetup(&pmq);
2402 
2403  SCACBSPreparePatterns(&mpm_ctx);
2404 
2405  const char *buf = "abcdefgh";
2406  uint32_t cnt = SCACBSSearch(&mpm_ctx, &mpm_thread_ctx, &pmq,
2407  (uint8_t *)buf, strlen(buf));
2408 
2409  if (cnt == 4)
2410  result = 1;
2411  else
2412  printf("3 != %" PRIu32 " ",cnt);
2413 
2414  SCACBSDestroyCtx(&mpm_ctx);
2415  SCACBSDestroyThreadCtx(&mpm_ctx, &mpm_thread_ctx);
2416  PmqFree(&pmq);
2417  return result;
2418 }
2419 
2420 static int SCACBSTest30(void)
2421 {
2422  uint8_t *buf = (uint8_t *)"onetwothreefourfivesixseveneightnine";
2423  uint16_t buflen = strlen((char *)buf);
2424  Packet *p = NULL;
2425  ThreadVars th_v;
2426  DetectEngineThreadCtx *det_ctx = NULL;
2427  int result = 0;
2428 
2429  memset(&th_v, 0, sizeof(th_v));
2430  p = UTHBuildPacket(buf, buflen, IPPROTO_TCP);
2431 
2433  if (de_ctx == NULL)
2434  goto end;
2435  de_ctx->mpm_matcher = MPM_AC_BS;
2436 
2437  de_ctx->flags |= DE_QUIET;
2438 
2439  de_ctx->sig_list = SigInit(de_ctx, "alert tcp any any -> any any "
2440  "(content:\"onetwothreefourfivesixseveneightnine\"; sid:1;)");
2441  if (de_ctx->sig_list == NULL)
2442  goto end;
2443  de_ctx->sig_list->next = SigInit(de_ctx, "alert tcp any any -> any any "
2444  "(content:\"onetwothreefourfivesixseveneightnine\"; fast_pattern:3,3; sid:2;)");
2445  if (de_ctx->sig_list->next == NULL)
2446  goto end;
2447 
2448  SigGroupBuild(de_ctx);
2449  DetectEngineThreadCtxInit(&th_v, (void *)de_ctx, (void *)&det_ctx);
2450 
2451  SigMatchSignatures(&th_v, de_ctx, det_ctx, p);
2452  if (PacketAlertCheck(p, 1) != 1) {
2453  printf("if (PacketAlertCheck(p, 1) != 1) failure\n");
2454  goto end;
2455  }
2456  if (PacketAlertCheck(p, 2) != 1) {
2457  printf("if (PacketAlertCheck(p, 1) != 2) failure\n");
2458  goto end;
2459  }
2460 
2461  result = 1;
2462 end:
2463  if (de_ctx != NULL) {
2464  SigGroupCleanup(de_ctx);
2465  SigCleanSignatures(de_ctx);
2466 
2467  DetectEngineThreadCtxDeinit(&th_v, (void *)det_ctx);
2468  DetectEngineCtxFree(de_ctx);
2469  }
2470 
2471  UTHFreePackets(&p, 1);
2472  return result;
2473 }
2474 
2475 #endif /* UNITTESTS */
2476 
2478 {
2479 
2480 #ifdef UNITTESTS
2481  UtRegisterTest("SCACBSTest01", SCACBSTest01);
2482  UtRegisterTest("SCACBSTest02", SCACBSTest02);
2483  UtRegisterTest("SCACBSTest03", SCACBSTest03);
2484  UtRegisterTest("SCACBSTest04", SCACBSTest04);
2485  UtRegisterTest("SCACBSTest05", SCACBSTest05);
2486  UtRegisterTest("SCACBSTest06", SCACBSTest06);
2487  UtRegisterTest("SCACBSTest07", SCACBSTest07);
2488  UtRegisterTest("SCACBSTest08", SCACBSTest08);
2489  UtRegisterTest("SCACBSTest09", SCACBSTest09);
2490  UtRegisterTest("SCACBSTest10", SCACBSTest10);
2491  UtRegisterTest("SCACBSTest11", SCACBSTest11);
2492  UtRegisterTest("SCACBSTest12", SCACBSTest12);
2493  UtRegisterTest("SCACBSTest13", SCACBSTest13);
2494  UtRegisterTest("SCACBSTest14", SCACBSTest14);
2495  UtRegisterTest("SCACBSTest15", SCACBSTest15);
2496  UtRegisterTest("SCACBSTest16", SCACBSTest16);
2497  UtRegisterTest("SCACBSTest17", SCACBSTest17);
2498  UtRegisterTest("SCACBSTest18", SCACBSTest18);
2499  UtRegisterTest("SCACBSTest19", SCACBSTest19);
2500  UtRegisterTest("SCACBSTest20", SCACBSTest20);
2501  UtRegisterTest("SCACBSTest21", SCACBSTest21);
2502  UtRegisterTest("SCACBSTest22", SCACBSTest22);
2503  UtRegisterTest("SCACBSTest23", SCACBSTest23);
2504  UtRegisterTest("SCACBSTest24", SCACBSTest24);
2505  UtRegisterTest("SCACBSTest25", SCACBSTest25);
2506  UtRegisterTest("SCACBSTest26", SCACBSTest26);
2507  UtRegisterTest("SCACBSTest27", SCACBSTest27);
2508  UtRegisterTest("SCACBSTest28", SCACBSTest28);
2509  UtRegisterTest("SCACBSTest29", SCACBSTest29);
2510  UtRegisterTest("SCACBSTest30", SCACBSTest30);
2511 #endif
2512 
2513  return;
2514 }
uint16_t flags
#define SCMemcmp(a, b, c)
Definition: util-memcmp.h:490
MpmPattern ** parray
#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:310
uint16_t minlen
Definition: util-mpm.h:95
void(* PrintCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:159
uint64_t total_matches
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:93
void MpmFreePattern(MpmCtx *mpm_ctx, MpmPattern *p)
Definition: util-mpm.c:418
int PmqSetup(PrefilterRuleStore *)
Setup a pmq.
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:124
void(* InitCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:139
int32_t(* goto_table)[256]
void(* RegisterUnittests)(void)
Definition: util-mpm.h:161
Signature * sig_list
Definition: detect.h:726
uint64_t offset
void SigCleanSignatures(DetectEngineCtx *de_ctx)
void(* DestroyThreadCtx)(struct MpmCtx_ *, struct MpmThreadCtx_ *)
Definition: util-mpm.h:142
uint16_t single_state_size
uint32_t memory_cnt
Definition: util-mpm.h:98
TmEcode DetectEngineThreadCtxInit(ThreadVars *, void *, void **)
initialize thread specific detection engine context
uint8_t ** state_table_mod_pointers
struct SCACBSCtx_ SCACBSCtx
uint32_t memory_size
Definition: util-mpm.h:50
struct MpmPattern_ * next
Definition: util-mpm.h:79
main detection engine ctx
Definition: detect.h:720
#define STATE_QUEUE_CONTAINER_SIZE
TmEcode DetectEngineThreadCtxDeinit(ThreadVars *, void *)
void PmqFree(PrefilterRuleStore *)
Cleanup and free a Pmq.
void SCACBSDestroyCtx(MpmCtx *)
Destroy the mpm context.
#define SC_AC_BS_STATE_TYPE_U32
int SCACBSPreparePatterns(MpmCtx *mpm_ctx)
Process the patterns added to the mpm, and create the internal tables.
#define DE_QUIET
Definition: detect.h:298
#define SC_AC_BS_FAIL
int(* Prepare)(struct MpmCtx_ *)
Definition: util-mpm.h:157
void(* PrintThreadCtx)(struct MpmThreadCtx_ *)
Definition: util-mpm.h:160
SigIntId * sids
Definition: util-mpm.h:77
#define u8_tolower(c)
Definition: suricata.h:176
SC_AC_BS_STATE_TYPE_U32(* state_table_u32)[256]
uint8_t flags
Definition: detect.h:721
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:496
void SCACBSPrintInfo(MpmCtx *mpm_ctx)
int32_t * failure_table
#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.
uint16_t mpm_matcher
Definition: detect.h:769
void UtRegisterTest(const char *name, int(*TestFn)(void))
Register unit test.
void SigMatchSignatures(ThreadVars *th_v, DetectEngineCtx *de_ctx, DetectEngineThreadCtx *det_ctx, Packet *p)
wrapper for old tests
Definition: detect.c:1752
SC_AC_BS_STATE_TYPE_U16(* state_table_u16)[256]
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.
uint32_t state_count
void(* DestroyCtx)(struct MpmCtx_ *)
Definition: util-mpm.h:141
int SigGroupCleanup(DetectEngineCtx *de_ctx)
struct Signature_ * next
Definition: detect.h:563
uint32_t id
Definition: util-mpm.h:73
#define SCRealloc(x, a)
Definition: util-mem.h:190
SCACBSPatternList * pid_pat_list
int SCACBSAddPatternCI(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...
struct SCACBSThreadCtx_ SCACBSThreadCtx
uint32_t memory_size
Definition: util-mpm.h:99
uint32_t memory_cnt
Definition: util-mpm.h:49
uint32_t SCACBSSearch(const MpmCtx *mpm_ctx, MpmThreadCtx *mpm_thread_ctx, PrefilterRuleStore *pmq, const uint8_t *buf, uint32_t buflen)
The aho corasick search function.
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:174
int SCACBSAddPatternCS(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...
void(* InitThreadCtx)(struct MpmCtx_ *, struct MpmThreadCtx_ *)
Definition: util-mpm.h:140
void SCACBSPrintSearchStats(MpmThreadCtx *mpm_thread_ctx)
uint16_t maxlen
Definition: util-mpm.h:96
void MpmInitCtx(MpmCtx *mpm_ctx, uint16_t matcher)
Definition: util-mpm.c:261
MpmTableElmt mpm_table[MPM_TABLE_SIZE]
Definition: util-mpm.h:165
#define SCFree(a)
Definition: util-mem.h:236
SCACBSOutputTable * output_table
int32_t store[STATE_QUEUE_CONTAINER_SIZE]
void MpmACBSRegister(void)
Register the aho-corasick mpm.
MpmPattern ** init_hash
Definition: util-mpm.h:104
structure for storing potential rule matches
uint32_t sids_size
Definition: util-mpm.h:76
uint8_t flags
Definition: util-mpm.h:58
uint32_t max_pat_id
Definition: util-mpm.h:101
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:319
void SCACBSInitCtx(MpmCtx *)
Initialize the AC context.
#define SC_AC_BS_STATE_TYPE_U16
uint32_t(* Search)(const struct MpmCtx_ *, struct MpmThreadCtx_ *, PrefilterRuleStore *, const uint8_t *, uint32_t)
Definition: util-mpm.h:158
#define SCReturn
Definition: util-debug.h:339
void SCACBSRegisterTests(void)
Per thread variable structure.
Definition: threadvars.h:57
const char * name
Definition: util-mpm.h:138
void * ctx
Definition: util-mpm.h:83
void SCACBSInitThreadCtx(MpmCtx *, MpmThreadCtx *)
Init the mpm thread context.
uint8_t * ci
Definition: util-mpm.h:71
uint16_t len
Definition: util-mpm.h:56
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:156
#define SigIntId
uint32_t total_calls
int(* AddPattern)(struct MpmCtx_ *, uint8_t *, uint16_t, uint16_t, uint16_t, uint32_t, SigIntId, uint8_t)
Definition: util-mpm.h:155
void SCACBSDestroyThreadCtx(MpmCtx *, MpmThreadCtx *)
Destroy the mpm thread context.
struct StateQueue_ StateQueue
Helper structure used by AC during state table creation.
uint32_t pattern_id_bitarray_size
uint8_t * original_pat
Definition: util-mpm.h:67
DetectEngineCtx * DetectEngineCtxInit(void)
uint8_t * state_table_mod
void * ctx
Definition: util-mpm.h:47