regex.c - openbcm - Git mirror of https://github.com/Broadcom-Network-Switching-Software/OpenBCM

regex.c (121240B)
      1 /*
      2  * 
      3  * This license is set out in https://raw.githubusercontent.com/Broadcom-Network-Switching-Software/OpenBCM/master/Legal/LICENSE file.
      4  * 
      5  * Copyright 2007-2019 Broadcom Inc. All rights reserved.
      6  *
      7  * File:       bregex.c
      8  * Purpose:    Regex compiler
      9  */
     10 
     11 #if 0
     12 #define STANDALONE_MODE 1
     13 #endif
     14 
     15 #ifdef STANDALONE_MODE
     16 #define INCLUDE_REGEX
     17 #else
     18 #define BROADCOM_SDK
     19 #endif
     20 
     21 #define START_ANCHOR_CHAR '^'
     22 
     23 #define BITMASK_IS_SET(mask, bit)  (mask[bit / WORDS2BITS(1)] &   (1 << (bit % WORDS2BITS(1))))
     24 #define BITMASK_SET(mask, bit)      mask[bit / WORDS2BITS(1)] |=  (1 << (bit % WORDS2BITS(1)))
     25 #define BITMASK_UNSET(mask, bit)    mask[bit / WORDS2BITS(1)] &= ~(1 << (bit % WORDS2BITS(1)))
     26 
     27 #define OPTIMIZE_PATTERN    1
     28 #define DFA_STATE_BLOCK_SIZE    1024
     29 #define NFA_BLOCK_SIZE          16300
     30 #define NFA_STATE_BLOCK_SIZE    1000
     31 #define REGEX_MAX_DFA_STATES    100000 
     32 #define REGEX_MAX_MEM_USAGE     100000000 /* 100MB */ 
     33 #define REGEX_MAX_TIMEOUT       1800 * 1000000 /* 30 Mins */ 
     34 #define NFA_STACK_SIZE          4096 
     35 
     36 /*
     37  * Enable DFA minimization after computation of DFA from NFA. This is 
     38  * highly recommeneded as it leads to compressing/optimizing the DFA
     39  * to in most cases to 2-4% of the orginal DFA.
     40  */
     41 #define DFA_MINIMIZE            1
     42 
     43 /*
     44  * Disable nextline character to not be matched when '.' Dot character
     45  * is encountered in the regex pattern.
     46  */
     47 #define OPT_DONT_MATCH_NL_ON_DOT    0
     48 
     49 #ifdef BROADCOM_SDK
     50 /* Enabling the dump of final DFA. */
     51 #define ENABLE_FINAL_DFA_DUMP   0
     52 
     53 /* Enable the dump of inverted DFA before minimization step. */
     54 #define ENABLE_INVERTED_DFA_DUMP 0
     55 
     56 /* Enable the dump of DFA before minimization step. */
     57 #define ENABLE_DFA_DUMP_BEFORE_MINIMIZATION 0
     58 
     59 /* enable the dump of DFA states as the list of NFA state list. */
     60 #define DUMP_DFA_STATE          0
     61 
     62 /* dump the symbol classes that represent the pattern. */
     63 #define DUMP_SYMBOL_CLASSES     0
     64 
     65 #define ENABLE_NFA_DUMP         0
     66 
     67 /* dump regular expression in postfix format */
     68 #define ENABLE_POST_DUMP        0
     69 
     70 #else
     71 
     72 /* Enabling the dump of final DFA. */
     73 #define ENABLE_FINAL_DFA_DUMP                   0
     74 
     75 /* Enable the dump of inverted DFA before minimization step. */
     76 #define ENABLE_INVERTED_DFA_DUMP                0
     77 
     78 /* Enable the dump of DFA before minimization step. */
     79 #define ENABLE_DFA_DUMP_BEFORE_MINIMIZATION     0
     80 
     81 /* enable the dump of DFA states as the list of NFA state list. */
     82 #define DUMP_DFA_STATE                          0
     83 
     84 /* dump the symbol classes that represent the pattern. */
     85 #define DUMP_SYMBOL_CLASSES                     0
     86 
     87 #define ENABLE_NFA_DUMP                         0
     88 
     89 /* dump regular expression in postfix format */
     90 #define ENABLE_POST_DUMP        0
     91 
     92 #endif
     93 
     94 #if defined(INCLUDE_REGEX)
     95 
     96 #include <shared/bsl.h>
     97 
     98 #include <assert.h>
     99 
    100 #ifdef BROADCOM_SDK
    101 #include <soc/defs.h>
    102 #include <soc/util.h>
    103 #include <shared/alloc.h>
    104 #include <shared/util.h>
    105 #include <sal/core/libc.h>
    106 #include <sal/core/sync.h>
    107 #include <sal/appl/io.h>
    108 #include <bcm/error.h>
    109 #include <bcm_int/regex_api.h>
    110 #define RE_SAL_TOI(s1,base) sal_ctoi((s1),NULL)
    111 #define RE_SAL_ITOA(s1,u,base)  sal_itoa((s1),u,base,0,0)
    112 #define RE_SAL_DPRINT(args)  LOG_INFO(BSL_LS_BCM_REGEX, args)
    113 
    114 #else
    115 
    116 #include <stdlib.h>
    117 #include <string.h>
    118 #include <stdio.h>
    119 
    120 #include "regex_api.h"
    121 
    122 #define MEM_PROFILE     0
    123 
    124 #if MEM_PROFILE==1
    125 #define sal_alloc(s,t)  re_alloc_wrap((s),(t))
    126 #define sal_free(p)   re_free_wrap((p))
    127 #else
    128 #define sal_alloc(s,t)  malloc((s))
    129 #define sal_free(p)   free((p))
    130 #endif
    131 
    132 #define sal_strcpy(s1,s2) strcpy((s1),(s2))
    133 #define RE_SAL_TOI(s1,base) strtol((s1),NULL, (base))
    134 #define RE_SAL_ITOA(s1,u,base)  itoa(u,(s1),(base))
    135 #define RE_SAL_DPRINT(p)   printf p
    136 #define _shr_sort(a,b,s,n)    qsort((void*)(a),(b),(s),(n))
    137 #define sal_strlen   strlen
    138 #define sal_memset   memset
    139 #define sal_memcpy   memcpy
    140 #define sal_strdup   strdup
    141 #define sal_memcmp   memcmp
    142 
    143 #if MEM_PROFILE==1
    144 
    145 static int peak_alloc = 0;
    146 static int total_alloc = 0;
    147 
    148 typedef struct _mem_profile_s {
    149     struct _mem_profile_s *next;
    150     void *buf;
    151     char loc[32];
    152     int size;
    153 } _mem_profile_t;
    154 
    155 static _mem_profile_t *alloc_list = NULL;
    156 
    157 static void *re_alloc_wrap(int size, char *tag)
    158 {
    159     void *b;
    160     _mem_profile_t *mp;
    161 
    162     b = malloc(size+sizeof(_mem_profile_t));
    163     if (b) {
    164          mp = (_mem_profile_t*)b;
    165          mp->size = size;
    166          mp->next = alloc_list;
    167          alloc_list = mp;
    168          sal_strcpy(mp->loc, tag);
    169          mp->buf = b + sizeof(_mem_profile_t);
    170          b += sizeof(_mem_profile_t);
    171          total_alloc += size;
    172          if (total_alloc > peak_alloc) {
    173             peak_alloc = total_alloc;
    174          }
    175     }
    176     return b;
    177 }
    178 
    179 static void re_free_wrap(void *b)
    180 {
    181     _mem_profile_t **p = &alloc_list, *tmp;
    182 
    183     while(*p) {
    184         if (b == (*p)->buf) {
    185             tmp = *p;
    186             *p = tmp->next;
    187             total_alloc -= tmp->size;
    188             free(tmp);
    189             break;
    190         } else {
    191             p = &(*p)->next;
    192         }
    193     }
    194     return;
    195 }
    196 
    197 static void re_dump_mem_leak(void)
    198 {
    199     int total = 0;
    200     _mem_profile_t *mp = alloc_list;
    201 
    202     while(mp) {
    203         total += mp->size;
    204         RE_SAL_DPRINT(("leak at :%s\n", mp->loc));
    205         mp = mp->next;
    206     }
    207 
    208     RE_SAL_DPRINT(("Total memory leak : %d bytes\n", total));
    209     if (peak_alloc > 0x100000) {
    210         RE_SAL_DPRINT(("Total Peak alloc  : %d MB \n", peak_alloc/0x100000));
    211     } else {
    212         RE_SAL_DPRINT(("Total Peak alloc  : %d KB\n", peak_alloc/1024));
    213     }
    214     return;
    215 }
    216 
    217 #endif /* MEM_PROFILE */
    218 
    219 #endif
    220 
    221 typedef struct re_wc {
    222     /*
    223     If ctrl indicates a meta-character, then c is an actual
    224     character.  However, if ctrl indicates data, then c is
    225     actually a character class, not a character
    226     */
    227     unsigned  char ctrl;
    228     unsigned  char c;
    229 } re_wc;
    230 
    231 #define POST_EN_DATA    0x01
    232 #define POST_EN_META    0x02
    233 
    234 #define POST_ENTRY(p)   *(p)
    235 
    236 #define POST_EN_IS_META(p)  ((p)->ctrl == POST_EN_META)
    237 
    238 #define WSTR_DATA_VALID(pws)  \
    239     (((pws)->ctrl == POST_EN_META) && ((pws)->c == '\0') ? 0 : 1)
    240 
    241 #define WSTR_GET_DATA(pws)  (pws)->c
    242 
    243 #define WSTR_GET_DATA_AT_OFF(pws, off)  WSTR_GET_DATA((pws)+(off))
    244 
    245 #define WSTR_PTR_INC(pws,i)   (pws) += (i)
    246 
    247 static int wstrlen(re_wc *wstring)
    248 {
    249     int i = 0;
    250 
    251     while(WSTR_DATA_VALID(wstring)) {
    252         i++;
    253         WSTR_PTR_INC(wstring,1);
    254     }
    255     return i;
    256 }
    257 
    258 static void add_data_cmn(char c, re_wc **o, int *offset, int *pmax,
    259                           unsigned char dtype) 
    260 {
    261     re_wc *tmp, *pwc; 
    262     int  max = *pmax, current_size, new_size;
    263 
    264     if (*offset == max) {
    265         current_size = max * sizeof(re_wc);
    266         new_size = max*2*sizeof(re_wc);
    267         tmp = sal_alloc(new_size,"re_wc1");
    268         sal_memset(tmp, 0, current_size);
    269         sal_memcpy(tmp, *o, current_size);
    270         sal_free(*o);
    271         *o = tmp;
    272         *pmax = max * 2;
    273     }
    274 
    275     /* first add the data type and then data */
    276     pwc = *o + *offset;
    277     pwc->ctrl = dtype;
    278     pwc->c = c;
    279     *offset = *offset + 1;
    280     return;
    281 }
    282 
    283 #define ADD_DATA(c, po, of, m)  \
    284         add_data_cmn((c), (po), (of), (m), POST_EN_DATA)
    285 
    286 #define ADD_META_DATA(c, po, of, m)  \
    287         add_data_cmn((c), (po), (of), (m), POST_EN_META)
    288 
    289 static int is_metachar(char c)
    290 {
    291     if ((c == '(') || (c == '.') || (c == ')') || (c == '+') || 
    292         (c == '*') || (c == '|') || (c == '{') || (c == '}') ||
    293         (c == '?') || (c == '\\')) {
    294         return 1;
    295     }
    296     return 0;
    297 }
    298 
    299 #define INFINITE -1
    300 
    301 static int parse_digit_from_range(re_wc **pb, char *mc)
    302 {
    303     /* re_wc *s; */
    304     re_wc *b;
    305     int   d, ti = 0;
    306     char  tmp[12];
    307 
    308     b = *pb;
    309     WSTR_PTR_INC(b, 1);
    310 
    311     /* skip whitespaces */
    312     while (WSTR_DATA_VALID(b) && 
    313            ((WSTR_GET_DATA(b) < '0') || (WSTR_GET_DATA(b) > '9')) && 
    314            (WSTR_GET_DATA(b) != ',') && (WSTR_GET_DATA(b) != '}')) {
    315         WSTR_PTR_INC(b,1);
    316     }
    317 
    318     /* s = b;*/
    319     while (WSTR_DATA_VALID(b) && 
    320             ((WSTR_GET_DATA(b) >= '0') && (WSTR_GET_DATA(b) <= '9'))) {
    321         tmp[ti++] = WSTR_GET_DATA(b);
    322         WSTR_PTR_INC(b,1);
    323     }
    324     tmp[ti] = '\0';
    325 
    326     if (ti > 0) {
    327         d = RE_SAL_TOI(tmp,10);
    328     } else {
    329         d = INFINITE;
    330     }
    331 
    332     /* eat everything upto sep */
    333     *mc = '\0';
    334     while (WSTR_DATA_VALID(b) && 
    335             (WSTR_GET_DATA(b) != ',') && (WSTR_GET_DATA(b) != '}')) {
    336         WSTR_PTR_INC(b,1);
    337     }
    338     *mc = WSTR_GET_DATA(b);
    339     *pb = b;
    340     return d;
    341 }
    342 
    343 static char *classed="dDwWsSnrt.";
    344 
    345 typedef struct re_class_info {
    346     char        c;
    347     re_wc       *exp;
    348     int         (*make_class_str)(int);
    349     unsigned int  flags;
    350 } re_class_info;
    351 
    352 static const unsigned int digit_tbl[] = {
    353         0x00000000, 
    354         0x03ff0000, 
    355         0x00000000, 
    356         0x00000000, 
    357         0x00000000, 
    358         0x00000000, 
    359         0x00000000, 
    360         0x00000000
    361 };
    362 
    363 static const unsigned int wtbl[] = {
    364         0x00000000, 
    365         0x00000000, 
    366         0x07fffffe, 
    367         0x07fffffe, 
    368         0x00000000, 
    369         0x00000000, 
    370         0x00000000, 
    371         0x00000000
    372 };
    373 
    374 static const unsigned int spacetbl[] = {
    375         0x00003e00, 
    376         0x00000001, 
    377         0x00000000, 
    378         0x00000000, 
    379         0x00000000, 
    380         0x00000000, 
    381         0x00000000, 
    382         0x00000000
    383 };
    384 
    385 static const unsigned int isupper[] = {
    386         0x00000000, 
    387         0x00000000, 
    388         0x07fffffe, 
    389         0x00000000, 
    390         0x00000000, 
    391         0x00000000, 
    392         0x00000000, 
    393         0x00000000
    394 };
    395 
    396 static const unsigned int islower[] = {
    397         0x00000000, 
    398         0x00000000, 
    399         0x00000000, 
    400         0x07fffffe, 
    401         0x00000000, 
    402         0x00000000, 
    403         0x00000000, 
    404         0x00000000
    405 };
    406 
    407 static const unsigned int isprintable[] = {
    408         0x00000000,
    409         0xffffffff,
    410         0xffffffff,
    411         0x7fffffff,
    412         0x00000000,
    413         0x00000000,
    414         0x00000000,
    415         0x00000000
    416 };
    417 
    418 #if (DUMP_SYMBOL_CLASSES == 1) || (ENABLE_FINAL_DFA_DUMP == 1) || (ENABLE_POST_DUMP == 1)
    419 static int printable(unsigned char c)
    420 {
    421     if (isprintable[c/32] & (1 << (c % 32))) {
    422         return 1;
    423     }
    424     return 0;
    425 }
    426 #endif
    427 
    428 static int re_tolower(int c)
    429 {
    430     c = c & 0xff;
    431 
    432     return (isupper[c/32] & (1 << (c%32))) ? c + 32 : c;
    433 }
    434 
    435 static int re_toupper(int c)
    436 {
    437     c = c & 0xff;
    438 
    439     return (islower[c/32] & (1 << (c%32))) ? c - 32 : c;
    440 }
    441 
    442 static int re_isdigit(int c)
    443 {
    444     c = c & 0xff;
    445     return (digit_tbl[c/32] & (1 << (c%32))) ? 1 : 0;
    446 }
    447 
    448 static int iswordc(int c)
    449 {
    450     c = c & 0xff;
    451     return (wtbl[c/32] & (1 << (c%32))) ? 1 : 0;
    452 }
    453 
    454 static int re_isspace(int c)
    455 {
    456     c = c & 0xff;
    457     return (spacetbl[c/32] & (1 << (c%32))) ? 1 : 0;
    458 }
    459 
    460 
    461 static int isnextline(int i)
    462 {
    463     if (i == 0xa) {
    464         return 1;
    465     }
    466     return 0;
    467 }
    468 static int isreturn(int i)
    469 {
    470     if (i == 0xd) {
    471         return 1;
    472     }
    473     return 0;
    474 }
    475 static int istab(int i)
    476 {
    477     if (i == 0x9) {
    478         return 1;
    479     }
    480     return 0;
    481 }
    482 
    483 static int dot(int i)
    484 {
    485 #if OPT_DONT_MATCH_NL_ON_DOT == 1
    486     if (i == 0xa) {
    487         return 0;
    488     }
    489 #endif
    490     return 1;
    491 }
    492 
    493 static re_class_info class_info[] = {
    494     /* \d class */
    495     {
    496         'd', NULL, re_isdigit, 1
    497     },
    498     /* \D class */
    499     {
    500         'D', NULL, re_isdigit, 0
    501     },
    502     /* \w class */
    503     {
    504         'w', NULL, iswordc, 1
    505     },
    506     /* \W class */
    507     {
    508         'W', NULL, iswordc, 0
    509     },
    510     /* \s class */
    511     {
    512         's', NULL, re_isspace, 1
    513     },
    514     /* \s class */
    515     {
    516         'S', NULL, re_isspace, 0
    517     },
    518     {
    519         'n', NULL, isnextline, 1
    520     },
    521     {
    522         'r', NULL, isreturn, 1
    523     },
    524     {
    525         't', NULL, istab, 1
    526     },
    527     {
    528         '.', NULL, dot, 1
    529     },
    530 };
    531 
    532 static re_wc *get_class_bitmap(char c, unsigned int *bitmap)
    533 {
    534     int idx, r;
    535     char *pc = classed;
    536     re_class_info *pclass_info;
    537     int i;
    538 
    539     while(*pc && (*pc != c)) {
    540         pc++;
    541     }
    542     if (!*pc) {
    543         RE_SAL_DPRINT(("Failed to find class info : %c\n", c));
    544         return NULL;
    545     }
    546     idx = pc - classed;
    547     pclass_info = &class_info[idx];
    548 
    549     for (i = 0; i < 8; i++) {
    550         bitmap[i] = 0;
    551     }
    552 
    553     for (i = 0; i < REGEX_MAX_CHARACTER_CLASSES; i++) {
    554         r = !!pclass_info->make_class_str(i);
    555         if (r == pclass_info->flags) {
    556             bitmap[i/32] |= (1 << (i % 32));
    557         }
    558     }
    559         /*RE_SAL_DPRINT(("string for class %c : %s\n", c, s)); */
    560     return 0;
    561 }
    562 
    563 static int _regex_decode_hex(char *pre, unsigned int *val)
    564 {
    565     char tmp[5], *re = pre;
    566     int d;
    567 
    568     tmp[0] = '0';
    569     tmp[1] = 'x';
    570     tmp[2] = *re;
    571     tmp[3] = *(re+1);
    572     tmp[4] = '\0';
    573     d = RE_SAL_TOI(tmp,16);
    574     *val = (unsigned int ) d;
    575     return 0;
    576 }
    577 
    578 static int 
    579 re_make_char_class_bitmap(char **pre, unsigned int *bitmap, int ignore_neg,
    580                         unsigned int re_flag)
    581 {
    582     unsigned int lc = 0, tc, d;
    583     int  esc = 0, neg = 0;
    584     int i, range = 0, j, oct[4];
    585     int lcuc = (re_flag & BCM_TR3_REGEX_CFLAG_EXPAND_LCUC) ? 1 : 0;
    586     char *re = *pre, *start;
    587     char bitmap_tmp[32];
    588 
    589     if (*re++ != '[') {
    590         return -1;
    591     }
    592     start = re;
    593     if (*re == '^') {
    594         if (!ignore_neg) {
    595             neg = 1;
    596         }
    597         re++;
    598         start = re;
    599     }
    600 
    601     sal_memset(bitmap, 0, sizeof(unsigned int)*8);
    602     sal_memset(bitmap_tmp, 0, 32);
    603 
    604     for(; *re && !(*re == ']' && !esc); re++) {
    605         if ((*re == '-') && !esc && (re != start)) {
    606             range = 1;
    607             continue;
    608         }
    609         if (!esc && (*re == '\\')) {
    610             esc = 0;
    611             switch(*(re+1)) {
    612                 case 'n':
    613                     tc = 0xa;
    614                     re++;
    615                 break;
    616                 case 'r':
    617                     tc = 0xd;
    618                     re++;
    619                 break;
    620                 case 't':
    621                     tc = 9;
    622                     re++;
    623                 break;
    624                 case 'u':
    625                     re += 2; 
    626                 case 'x':
    627                     re += 1;
    628                     if (_regex_decode_hex(re+1, &d)) {
    629                         return -1;
    630                     }
    631                     re += 2;
    632                     tc = d;
    633                     break;
    634                 default:
    635                     if ((*re >= '0') && (*re <= '9')) {
    636                         /* octal */
    637                         j = 0;
    638                         while (*re && (*re >= '0') && (*re <= '9') && (j < 2)) {
    639                             oct[j++] = *re++;
    640                         }
    641                         re--;
    642                         tc = 0;
    643                         while(j > 0) {
    644                             tc = (tc*8) + (oct[j-1] - '0');
    645                             j--;
    646                         }
    647                     } else {
    648                         esc = 1;
    649                     }
    650                 break;
    651             }
    652             if (esc) {
    653                 continue;
    654             }
    655         } else {
    656             tc = *re;
    657         }
    658         if (!range) {
    659             lc = tc;
    660         }
    661         /* add range from lc to *re */
    662         for (i=lc; i<=tc;i++) {
    663             bitmap_tmp[i/8] |= 1 << (i % 8);
    664         }
    665         esc = 0;
    666         range = 0;
    667     }
    668     *pre = re;
    669 
    670     for (i = 0; i < REGEX_MAX_CHARACTER_CLASSES; i++) {
    671         if (!!(bitmap_tmp[i/8] & (1 << (i % 8))) == neg) {
    672             continue;
    673         }
    674         bitmap[i/32] |= 1 << (i % 32);
    675         if (lcuc && (wtbl[i/32] & (1 << (i % 32)))) {
    676             tc = i + ((i >= 'a') ? -32 : 32 );
    677             bitmap[tc/32] |= 1 << (tc % 32);
    678         }
    679     }
    680     return 0;
    681 }
    682 
    683 #ifndef REGEX_DEBUG_STACK
    684 
    685 #define DEFINE_STACK(nt,t)    \
    686 struct stack_of_##nt {    \
    687     t    *pstack;  \
    688     t    *stack;   \
    689 };
    690 
    691 #define DECLARE_STACK(nt)   struct stack_of_##nt
    692 
    693 #define STACK_INIT(s,size,sn)  \
    694     (s)->pstack = (s)->stack = sal_alloc(sizeof(*(s)->stack)*size, (sn))
    695 
    696 #define STACK_RESET(s)  (s)->pstack = (s)->stack
    697 
    698 #define STACK_VALID(s)  ((s)->stack ? 1 : 0)
    699 
    700 #define STACK_DEINIT(s)     if ((s)->stack) sal_free((s)->stack)
    701 
    702 #define STACK_PUSH(s,p)     *(s)->pstack++ = (p)
    703 
    704 #define STACK_POP(s)      *--(s)->pstack
    705 
    706 #define STACK_EMPTY(s) ((s)->pstack == (s)->stack)
    707 
    708 #else
    709 
    710 #define DEFINE_STACK(nt,t)                      \
    711     struct stack_of_##nt {                      \
    712         t    *stack;                            \
    713         int   size;                             \
    714         int   top;                              \
    715         int   high;                             \
    716     }
    717 
    718 #define DECLARE_STACK(nt)   struct stack_of_##nt
    719 
    720 #define STACK_INIT(s, sz, sn)                                           \
    721     do {                                                                \
    722         (s)->stack = sal_alloc(sizeof(*(s)->stack) * sz, (sn));         \
    723         if ((s)->stack != NULL) {                                       \
    724             (s)->size = sz;                                             \
    725             (s)->top = 0;                                               \
    726             (s)->high = 0;                                              \
    727         }                                                               \
    728     } while (0)
    729 
    730 #define STACK_RESET(s)          \
    731     assert(NULL != (s)->stack); \
    732     (s)->top = 0
    733 
    734 #define STACK_VALID(s)  (NULL != (s)->stack ? 1 : 0)
    735 
    736 #define STACK_DEINIT(s)                         \
    737     if (NULL != (s)->stack) {                   \
    738         sal_free((s)->stack);                   \
    739     }
    740 
    741 #define STACK_PUSH(s,p)           \
    742     assert(NULL != (s)->stack);   \
    743     assert((s)->size > (s)->top); \
    744     (s)->stack[(s)->top] = (p);   \
    745     (s)->top++;                   \
    746     if ((s)->top > (s)->high) {   \
    747         (s)->high = (s)->top;     \
    748     }
    749 
    750 #define STACK_POP(s)                            \
    751     ({                                          \
    752         assert(NULL != (s)->stack);             \
    753         assert((s)->top > 0);                   \
    754         (s)->top--;                             \
    755         (s)->stack[(s)->top];                   \
    756     })
    757 
    758 #define STACK_EMPTY(s) (0 == (s)->top)
    759 
    760 #endif  /* REGEX_DEBUG_STACK */
    761 
    762 typedef struct re_transition_group_s {
    763     int num_transitions;
    764     unsigned int transition_map[8];
    765 } re_transition_group;
    766 
    767 typedef struct re_transition_class_s {
    768     int             id;
    769     int             num_transitions;
    770     unsigned int    transition_map[8];
    771 } re_transition_class;
    772 
    773 typedef struct re_membuf_blk_s {
    774     void    *buf;
    775     int     size;
    776     int     free_offset;
    777     int     unit_size;
    778     struct  re_membuf_blk_s *next;
    779 } re_membuf_blk_t;
    780 
    781 struct re_dfa_state_t;
    782 
    783 typedef struct avn_s {
    784     int balance;
    785     struct re_dfa_state_t *data;
    786     struct avn_s *ds[2];
    787 } avn_t;
    788 
    789 typedef struct re_dfa_state_t re_dfa_state_t;
    790 typedef struct re_dfa_t
    791 {
    792     re_dfa_state_t **states;
    793     int num_states;
    794     int size;
    795     re_transition_class *class_array;
    796     int num_classes;
    797     re_membuf_blk_t *nbuf;
    798     re_membuf_blk_t *avbuf;
    799     avn_t   *avtree;
    800 } re_dfa_t;
    801 
    802 /*
    803  * Represents an NFA state plus zero or one or two arrows exiting.
    804  * if c == Match, no arrows out; matching state.
    805  * If c == Split, unlabeled arrows to out and out1 (if != NULL).
    806  * If c < 256, labeled arrow with character c to out.
    807  */
    808 enum
    809 {
    810     Split = 256,
    811     Match = 257
    812 };
    813 
    814 typedef struct re_nfa_state_t re_nfa_state_t;
    815 struct re_nfa_state_t
    816 {
    817     int class;
    818     re_nfa_state_t *out;
    819     re_nfa_state_t *out1;
    820     int       id;
    821     int lastlist;
    822 };
    823 
    824 #define RE_NFA_STATES(l)        (l)->state_map
    825 
    826 #define RE_NFA_LIST_LENGTH(l)   (l)->num_states
    827 
    828 #define RE_NFA_STATE_IN_LIST(l,i) (l)->state_map[(i)]
    829 
    830 DEFINE_STACK(nfa_states, re_nfa_state_t *);
    831 
    832 static int state_map_byte_size;
    833 
    834 typedef struct re_nfa_list_t
    835 {
    836     int num_states;
    837     unsigned int *state_map;
    838 } re_nfa_list_t;
    839 
    840 #define NFA_SMAP_BYTE_SIZE(n)    ((n)->state_map_byte_size)
    841 
    842 #define NFA_SMAP_WORD_SIZE(n)    (((n)->num_states+31)/32)
    843 
    844 #define NFA_LIST_RESET(nfa,l)   \
    845 {   \
    846     (l)->num_states = 0; \
    847     sal_memset((l)->state_map, 0, NFA_SMAP_BYTE_SIZE(nfa)); \
    848 }
    849 
    850 typedef struct re_nfa_t {
    851     re_nfa_state_t *root_state;
    852     int             state_map_byte_size;
    853     re_nfa_state_t **state_map;
    854     unsigned int    *class_map[REGEX_MAX_CHARACTER_CLASSES];
    855     int num_states;
    856     int state_map_size;
    857     re_membuf_blk_t *nbuf;
    858     DECLARE_STACK(nfa_states) *stk;
    859 } re_nfa_t;
    860 
    861 static int nfa_free(re_nfa_t *ns);
    862 
    863 static re_membuf_blk_t* 
    864 _alloc_membuf_block(re_membuf_blk_t **plist, int count, int unit_size)
    865 {
    866     int size;
    867     re_membuf_blk_t *pb;
    868 
    869     size = sizeof(re_membuf_blk_t) + (unit_size * count);
    870     pb = sal_alloc(size,"membuf");
    871     sal_memset(pb, 0, size);
    872     pb->buf = (void*) (pb+1);
    873     pb->free_offset = 0;
    874     pb->unit_size = unit_size;
    875     pb->size = count;
    876     
    877     pb->next = *plist;
    878     *plist = pb;
    879     return pb;
    880 }
    881 
    882 static void *
    883 _alloc_space_for_nfa_state_list(re_dfa_t *pdfa, int llen)
    884 {
    885     int alloc;
    886     re_membuf_blk_t *pb;
    887     void *b;
    888 
    889     pb = pdfa->nbuf;
    890     alloc = ((pb == NULL) || ((pb->size - (pb->free_offset+1)) < llen));
    891     if (alloc) {
    892         pb = _alloc_membuf_block(&pdfa->nbuf, 
    893                                  NFA_BLOCK_SIZE, sizeof(unsigned int));
    894     }
    895 
    896     b = pb->buf + sizeof(unsigned int)*pb->free_offset;
    897     pb->free_offset += llen;
    898     return b;
    899 }
    900 
    901 static avn_t*
    902 _alloc_space_for_avltree_nodes(re_dfa_t *pdfa, int count, int llen)
    903 {
    904     int alloc;
    905     re_membuf_blk_t *pb;
    906     avn_t *b;
    907 
    908     pb = pdfa->avbuf;
    909     alloc = ((pb == NULL) || ((pb->size - (pb->free_offset+1)) < llen));
    910     if (alloc) {
    911         pb = _alloc_membuf_block(&pdfa->avbuf, count, sizeof(avn_t));
    912     }
    913 
    914     b = pb->buf + sizeof(avn_t)*pb->free_offset;
    915     pb->free_offset += llen;
    916     return b;
    917 }
    918 
    919 static re_nfa_state_t*
    920 _alloc_space_for_nfa_nodes(re_nfa_t *pnfa, int count, int llen)
    921 {
    922     int alloc;
    923     re_membuf_blk_t *pb;
    924     re_nfa_state_t *b;
    925 
    926     pb = pnfa->nbuf;
    927     alloc = ((pb == NULL) || ((pb->size - (pb->free_offset+1)) < llen));
    928     if (alloc) {
    929         pb = _alloc_membuf_block(&pnfa->nbuf, count, sizeof(re_nfa_state_t));
    930     }
    931 
    932     b = pb->buf + sizeof(re_nfa_state_t)*pb->free_offset;
    933     pb->free_offset += llen;
    934     return b;
    935 }
    936 
    937 static void _free_buf_blocks(re_membuf_blk_t *nb)
    938 {
    939     re_membuf_blk_t *t;
    940 
    941     while(nb) {
    942         t = nb->next;
    943         sal_free(nb);
    944         nb = t;
    945     }
    946 }
    947 
    948 static int listid;
    949 
    950 /*
    951  * Represents a DFA state: a cached NFA state list.
    952  */
    953 struct re_dfa_state_t
    954 {
    955     re_nfa_list_t l;
    956     unsigned int flags;
    957     int     *transition_list;
    958 };
    959 
    960 #define RE_DFA_STATE_ARCS(d)    (d)->transition_list
    961 
    962 /*
    963  * In order to conserve space, flags field is encoded and contains the
    964  * following in encoded fashion.
    965  *   - state_id
    966  *   - final
    967  *   - marked
    968  *   ..
    969  */
    970 #define RE_DFA_STATEID(d)       ((d)->flags & 0x7ffff)
    971 #define RE_DFA_SET_STATEID(d,s)  \
    972                 (d)->flags = ((d)->flags & 0xfff80000) | ((s) & 0x7ffff)
    973 
    974 #define RE_DFA_IS_FINAL(d)      ((((d)->flags >> 19) & 0x1ff) > 0)
    975 #define RE_DFA_FINAL(d)         (((d)->flags >> 19) & 0x1ff)
    976 #define RE_DFA_SET_FINAL(d,m)   \
    977             (d)->flags = ((d)->flags & 0xf007ffff) | (((m) & 0x1ff) << 19)
    978 
    979 #define RE_DFA_IS_MARKED(d)      (((d)->flags >> 28) & 0x1)
    980 #define RE_DFA_SET_MARKED(d,m)     \
    981              (d)->flags = ((d)->flags & 0xefffffff) | (((m) & 0x1) << 28)
    982 
    983 #define RE_DFA_IS_ADDED_TO_LIST(d)  (((d)->flags >> 29) & 0x1)
    984 #define RE_DFA_ADD_TO_LIST(d)   (d)->flags |= (1 << 29)
    985 
    986 #define RE_DFA_SET_BLOCK_MSTR(d) (d)->flags |= (1 << 30)
    987 
    988 #define RE_CONNECT_DFA_STATES(d1,d2,c) (d1)->transition_list[(c)] = RE_DFA_STATEID(d2)
    989 
    990 #define DFA_BLOCK_SIZE  1024
    991 
    992 unsigned int mem_cou;
    993 
    994 static re_dfa_state_t* _alloc_dfa_state_block(re_dfa_state_t**tbl,
    995                                               int num_classes)
    996 {
    997     re_dfa_state_t *ps;
    998     int *transition_list = NULL, szs, szt, i, count;
    999 
   1000     count = DFA_BLOCK_SIZE;
   1001     szs = sizeof(re_dfa_state_t)*count;
   1002     ps = sal_alloc(szs,"dfasb");
   1003     if (!ps) {
   1004         goto error;
   1005     }
   1006     mem_cou += szs;
   1007     /* allocate transition list and attach to states */
   1008     szt = sizeof(int)*count*num_classes;
   1009     transition_list = sal_alloc(szt,"dfalst");
   1010     if (!transition_list) {
   1011         goto error;
   1012     }
   1013     mem_cou += szt;
   1014     sal_memset(ps, 0, szs);
   1015     sal_memset(transition_list, 0xff, szt);
   1016 
   1017     for (i = 0; i < count; i++) {
   1018         tbl[i] = &ps[i];
   1019         ps[i].transition_list = transition_list;
   1020         transition_list += num_classes;
   1021     }
   1022 
   1023     RE_DFA_SET_BLOCK_MSTR(&ps[0]);
   1024 
   1025     return ps;
   1026 
   1027 error:
   1028     if (ps) {
   1029         sal_free(ps);
   1030     }
   1031 
   1032     if (transition_list) {
   1033         sal_free(transition_list);
   1034     }
   1035     return NULL;
   1036 }
   1037 
   1038 static re_transition_group *_add_to_transition_group_list(re_transition_group **top, int top_size, re_transition_group *this)
   1039 {
   1040     re_transition_group *new_grp, *ptmp;
   1041     int matched = 0, i, j, off;
   1042 
   1043     off = -1;
   1044     for (i = 0; i < top_size; i++) {
   1045         ptmp = top[i]; 
   1046         if (ptmp == NULL) {
   1047             if (off == -1) {
   1048                 off = i;
   1049             }
   1050             continue;
   1051         }
   1052         matched = 1;
   1053         /* compare the tr group */
   1054         for (j = 0; j < 8; j++) {
   1055             if (this->transition_map[j] != ptmp->transition_map[j]) {
   1056                 matched = 0;
   1057                 break;
   1058             }
   1059         }
   1060         if (matched) {
   1061             break;
   1062         }
   1063     }
   1064 
   1065     if (!matched) {
   1066         assert((off >= 0) && (off < top_size));
   1067         new_grp = sal_alloc(sizeof(re_transition_group),"trgrp");
   1068         sal_memcpy(new_grp, this, sizeof(re_transition_group));
   1069         top[off] = new_grp;
   1070     }
   1071     return 0;
   1072 }
   1073 
   1074 #define RE_RESET_TRANSITION_MAP(ptr) sal_memset((ptr), 0, sizeof(re_transition_group))
   1075 
   1076 #define RE_ADD_TRANSITION_TO_GROUP(ptr,tr)                                \
   1077 {                                                               \
   1078     if (((ptr)->transition_map[(tr)/32] & (1 << ((tr) % 32))) == 0) {    \
   1079         (ptr)->num_transitions++;                                        \
   1080         (ptr)->transition_map[(tr)/32] |= (1 << ((tr) % 32));            \
   1081     }                                                           \
   1082 }
   1083 
   1084 #if 0
   1085 static int
   1086 sort_transition_group(void *a, void *b)
   1087 {
   1088     re_transition_group *pa, *pb;
   1089     pa = *((re_transition_group**) a);
   1090     pb = *((re_transition_group**) b);
   1091     return pa->num_transitions - pb->num_transitions;
   1092 }
   1093 #endif
   1094 
   1095 static int
   1096 sort_transition_class(void *a, void *b)
   1097 {
   1098     re_transition_class *pa, *pb;
   1099     int ma, mb, i, j;
   1100 
   1101     pa = (re_transition_class*) a;
   1102     pb = (re_transition_class*) b;
   1103     
   1104     ma = -1;
   1105     for (i = 0; i < 8; i++) {
   1106         if (pa->transition_map[i] == 0) {
   1107             continue;
   1108         }
   1109         for (j = 0; j < 32; j++) {
   1110             if (pa->transition_map[i] & (1 << (j % 32))) {
   1111                 ma = (i*32) + j;
   1112                 break;
   1113             }
   1114         }
   1115         if (ma >= 0) {
   1116             break;
   1117         }
   1118     }
   1119     mb = -1;
   1120     for (i = 0; i < 8; i++) {
   1121         if (pb->transition_map[i] == 0) {
   1122             continue;
   1123         }
   1124         for (j = 0; j < 32; j++) {
   1125             if (pb->transition_map[i] & (1 << (j % 32))) {
   1126                 mb = (i*32) + j;
   1127                 break;
   1128             }
   1129         }
   1130         if (mb >= 0) {
   1131             break;
   1132         }
   1133     }
   1134     return ma - mb;
   1135 }
   1136 
   1137 static int _regex_add_token_one_char(re_transition_group **top, int top_size, unsigned char c)
   1138 {
   1139     re_transition_group curmap;
   1140 
   1141     RE_RESET_TRANSITION_MAP(&curmap);
   1142     RE_ADD_TRANSITION_TO_GROUP(&curmap, c);
   1143     _add_to_transition_group_list(top, top_size, &curmap);
   1144     return 0;
   1145 }
   1146 
   1147 static int _regex_add_token_multi(re_transition_group **top, int top_size, unsigned int *bitmap)
   1148 {
   1149     re_transition_group curmap;
   1150     int i;
   1151 
   1152     RE_RESET_TRANSITION_MAP(&curmap);
   1153     for (i = 0; i < REGEX_MAX_CHARACTER_CLASSES; i++) {
   1154         if (bitmap[i/32] & (1 << (i % 32))) {
   1155             RE_ADD_TRANSITION_TO_GROUP(&curmap, i);
   1156         }
   1157     }
   1158     _add_to_transition_group_list(top, top_size, &curmap);
   1159     return 0;
   1160 }
   1161 
   1162 static int 
   1163 re_add_single_class(re_transition_class *pclass_array, int num_classes, unsigned int c,
   1164                                   re_wc **o, int *used, int *size)
   1165 {
   1166     int i, class_id;
   1167 
   1168     for (i = 0; i < num_classes; i++) {
   1169         #if 0
   1170         if (pclass_array[i].num_transitions != 1) {
   1171             continue;
   1172         }
   1173         #endif
   1174         if (pclass_array[i].transition_map[c/32] & (1 << (c % 32))) {
   1175             class_id = pclass_array[i].id;
   1176             if (is_metachar(class_id)) {
   1177                 ADD_DATA('\\', o, used, size);
   1178             }
   1179             ADD_DATA(class_id, o, used, size);
   1180             return 0;
   1181         }
   1182     }
   1183     return -1;
   1184 }
   1185 
   1186 static int 
   1187 re_add_multi_class(re_transition_class *pclass_array, int num_classes,
   1188                       unsigned int *bitmap, re_wc **o, int *used, int *size)
   1189 {
   1190     int i, j, class_id, first = 1, matched;
   1191 
   1192     ADD_DATA('(', o, used, size);
   1193     for (i = 0; i < num_classes; i++) {
   1194         for (j = 0; j < 8; j++) {
   1195             matched = 0;
   1196             if (pclass_array[i].transition_map[j] & (bitmap[j])) {
   1197                 matched = 1;
   1198             }
   1199             if (matched) {
   1200                 class_id = pclass_array[i].id;
   1201                 if (!first) {
   1202                     ADD_DATA('|', o, used, size);
   1203                 }
   1204                 if (is_metachar(class_id)) {
   1205                     ADD_DATA('\\', o, used, size);
   1206                 }
   1207                 ADD_DATA(class_id, o, used, size);
   1208                 first = 0;
   1209                 break;
   1210             }
   1211         }
   1212     }
   1213     ADD_DATA(')', o, used, size);
   1214     return 0;
   1215 }
   1216 
   1217 #ifdef OPTIMIZE_PATTERN
   1218 /*
   1219  * Optimize the patterns. Some of the optimizations are:
   1220  *  remove trailing .*
   1221  */
   1222 static int
   1223 re_optimize_patterns(char **patterns, int num_pattern)
   1224 {
   1225     int p, esc = 0;
   1226     char *mark = NULL, *re;
   1227     return 0;
   1228     for(p=0; p <num_pattern; p++) {
   1229         re = patterns[p];
   1230         while(*re) {
   1231             if (*re == '\\') {
   1232                 esc = !!esc;
   1233             } else if (!esc && (*re == '.')) {
   1234                 if (*(re + 1) == '+') {
   1235                     re++;
   1236                     mark = re;
   1237                     re++;
   1238                 } else if (*(re+1) == '*') {
   1239                     mark = re;
   1240                     re++;
   1241                 }
   1242             } else {
   1243                 mark = NULL;
   1244             }
   1245             re++;
   1246         }
   1247         if (mark) {
   1248             *mark = '\0';
   1249         }
   1250     }
   1251     return 0;
   1252 }
   1253 #endif /* OPTIMIZE_PATTERN */
   1254 
   1255 static int
   1256 re_case_adjust(char **patterns, int num_pattern, unsigned int *re_flags)
   1257 {
   1258     int pi, esc = 0,remap=0;
   1259     char *re;
   1260     unsigned int u;
   1261     char buf[5];
   1262 
   1263     for (pi = 0; pi < num_pattern; pi++) {
   1264         if ((re_flags[pi] & (BCM_TR3_REGEX_CFLAG_EXPAND_UC |
   1265                        BCM_TR3_REGEX_CFLAG_EXPAND_LC)) == 0) {
   1266             continue;
   1267         }
   1268         re = patterns[pi];
   1269         while(*re) {
   1270             if (*re == '\\') {
   1271                 esc = !esc;
   1272                 re++;
   1273                 continue;
   1274             }
   1275             if (esc) {
   1276                 switch(*re) {
   1277                     case 'x':
   1278                     case 'X':
   1279                         if (_regex_decode_hex(re+1, &u)) {
   1280                             return -1;
   1281                         }
   1282                         if (re_flags[pi] & BCM_TR3_REGEX_CFLAG_EXPAND_UC) {
   1283                             if ((u >= 97) && (u <= 122)) {
   1284                                 u = u - 32;
   1285                                 remap=1;
   1286                             }
   1287                         } else if (re_flags[pi] & BCM_TR3_REGEX_CFLAG_EXPAND_LC) {
   1288                             if ((u >= 65) && (u <= 90)) {
   1289                                 u = u + 32;
   1290                                 remap=1;
   1291                             }
   1292                         }
   1293                         if(remap)
   1294                         {
   1295                             sal_memset(buf,0,sizeof(buf));
   1296                             RE_SAL_ITOA(buf,u,16);
   1297                             *(re+1) = *buf;
   1298                             *(re+2) = *(buf+1);
   1299                             remap=0;
   1300                         }    
   1301                         re += 3;
   1302                         break;
   1303                     default:
   1304                         re++;
   1305                         break;
   1306                 }
   1307                 esc = 0;
   1308                 continue;
   1309             }
   1310             if (re_flags[pi] & BCM_TR3_REGEX_CFLAG_EXPAND_UC) {
   1311                 if ((*re >= 97) && (*re <= 122)) {
   1312                     *re = *re - 32;
   1313                 }
   1314             } else if (re_flags[pi] & BCM_TR3_REGEX_CFLAG_EXPAND_LC) {
   1315                 if ((*re >= 65) && (*re <= 90)) {
   1316                     *re = *re + 32;
   1317                 }
   1318             }
   1319             re++;
   1320         }
   1321     }
   1322     return 0;
   1323 }
   1324 
   1325 /*
   1326  * decompose the transitions into unique classes. The idea is to
   1327  * extract the least common individual transitions which can 
   1328  * be uniquely represented. Say for example if the pattern
   1329  * is /abc/, it can be represented by character a, b and c. But if
   1330  * the pattern is /a.c/, in this case '.' will be represented as
   1331  * (\0|\1|\2|...\254|\255), it not only makes the pattern big, also
   1332  * the possible symbols in the patterns are 256. Whereas this can be 
   1333  * represented as 3 symbols, ie. S1 ==> {a}, S2 ==> {b} and 
   1334  *  S3 =={anything not a and b}, so we can now represent the same pattern
   1335  * /a.c/ as /S1(S1|S2|S3)S2/ which makes the symbol table size just 3
   1336  * instead of 256.
   1337  */
   1338 static int
   1339 re_make_symbol_classes_from_pattern(char **patterns, int num_pattern, 
   1340                             unsigned int *re_flag,
   1341                                     re_transition_class **pclass_array, int *num_classes)
   1342 {
   1343     int   cl_num = 0, i, j, k, count, p, esc = 0, rv = 0;
   1344     unsigned int bitmap[REGEX_MAX_CHARACTER_CLASS_WORDS], oct[4], u;
   1345     re_transition_group **transition_list;
   1346     re_transition_class *class_array = NULL, *class;
   1347     char *re;
   1348 #if DUMP_SYMBOL_CLASSES == 1
   1349     int lc = -1;
   1350 #endif
   1351     int first_unused;
   1352     int transition_list_max;
   1353     int patterns_length = 0;
   1354 
   1355     for (p = 0; p < num_pattern; p++) {
   1356         patterns_length += sal_strlen(patterns[p]);
   1357     }
   1358     /*
   1359      * This calculates the maximum number of classes that can be coded in the patterns.
   1360      * There are 9 classes that are signified by a backslash followed by a letter (see
   1361      * below).  Each of those are use two characters.  Other character classes (ranges)
   1362      * take, at a minimum, two characters for an opening and closing square bracket, two
   1363      * characters for the beginning and ending values and one character for the dash for a
   1364      * total of five characters.  Add to this the single character classes to get a safe
   1365      * maximum.
   1366      *
   1367      * Note that these classes are later condensed into the minimum number of classes
   1368      * required which can be, at most, REGEX_MAX_CHARACTER_CLASSES.
   1369      */
   1370 #define NUM_2CHAR_CLASSES 9
   1371 #define RANGE_SIZE        5
   1372     transition_list_max = ((patterns_length - NUM_2CHAR_CLASSES * 2) / RANGE_SIZE) + NUM_2CHAR_CLASSES + REGEX_MAX_CHARACTER_CLASSES;
   1373     transition_list = sal_alloc(transition_list_max * sizeof(transition_list[0]), "transition_list");
   1374    
   1375     sal_memset(transition_list, 0, transition_list_max * sizeof(transition_list[0]));
   1376 
   1377     for(p=0; p <num_pattern; p++) {
   1378         re = patterns[p];
   1379         while(*re) {
   1380             switch(*re) {
   1381                 case '\\':
   1382                     if (!esc) {
   1383                         esc = 1;
   1384                     } else {
   1385                         _regex_add_token_one_char(transition_list, transition_list_max, *re);
   1386                         esc = 0;
   1387                     }
   1388                     break;
   1389                 case '[':
   1390                     if (esc) {
   1391                         _regex_add_token_one_char(transition_list, transition_list_max, *re);
   1392                         esc = 0;
   1393                     } else {
   1394                         re_make_char_class_bitmap(&re, bitmap, 1,
   1395                                                 re_flag ? re_flag[p] : 0);
   1396                         _regex_add_token_multi(transition_list, transition_list_max, bitmap);
   1397                     }
   1398                     break;
   1399                 case '{':
   1400                     if (esc) {
   1401                         _regex_add_token_one_char(transition_list, transition_list_max, *re);
   1402                         esc = 0;
   1403                     } else {
   1404                         while (*re != '}') {
   1405                             re++;
   1406                         }
   1407                     }
   1408                     break;
   1409                 default:
   1410                     if (!esc) {
   1411                         if (!((*re == '(') || (*re == ')') || 
   1412                              (*re == '|') || (*re == '*') || (*re == '+'))) {
   1413                             if (*re == '.') {
   1414                                 #if 0
   1415                                 get_class_bitmap(*re, bitmap);
   1416                                 _regex_add_token_multi(transition_list, transition_list_max, bitmap);
   1417                                 #endif
   1418                             } else {
   1419                                 if ((re_flag) && 
   1420                                     (re_flag[p] & BCM_TR3_REGEX_CFLAG_EXPAND_LCUC) &&
   1421                                     (re_tolower(*re) != re_toupper(*re))) {
   1422                                     _regex_add_token_one_char(transition_list, transition_list_max, re_tolower(*re));
   1423                                     _regex_add_token_one_char(transition_list, transition_list_max, re_toupper(*re));
   1424                                 } else {
   1425                                     _regex_add_token_one_char(transition_list, transition_list_max, *re);
   1426                                 }
   1427                             }
   1428                         }
   1429                     } else {
   1430                         switch(*re) {
   1431                             case 'd':
   1432                             case 'D':
   1433                             case 'w':
   1434                             case 'W':
   1435                             case 's':
   1436                             case 'S':
   1437                             case 'n':
   1438                             case 'r':
   1439                             case 't':
   1440                                 get_class_bitmap(*re, bitmap);
   1441                                 _regex_add_token_multi(transition_list, transition_list_max, bitmap);
   1442                                 break;
   1443                             case 'u':
   1444                                 re += 2;
   1445                             case 'x':
   1446                                 if (_regex_decode_hex(re+1, &u)) {
   1447                                     rv = -1;
   1448                                     goto fail;
   1449                                 }
   1450                                 re += 2;
   1451                                 _regex_add_token_one_char(transition_list, transition_list_max, (char)u);
   1452                                 break;
   1453                             default:
   1454                                 if ((*re >= '0') && (*re <= '9')) {
   1455                                     /* octal */
   1456                                     j = 0;
   1457                                     while (*re && (*re >= '0') && (*re <= '9') && (j < 2)) {
   1458                                         oct[j++] = *re++;
   1459                                     }
   1460                                     re--;
   1461                                     i = 0;
   1462                                     while(j > 0) {
   1463                                         i = (i*8) + (oct[j-1] - '0');
   1464                                         j--;
   1465                                     }
   1466                                     _regex_add_token_one_char(transition_list, transition_list_max, i);
   1467                                 } else {
   1468                                     _regex_add_token_one_char(transition_list, transition_list_max, *re);
   1469                                 }
   1470                                 break;
   1471                         }
   1472                         esc = 0;
   1473                     }
   1474                     break;
   1475             }
   1476             re++;
   1477         }
   1478     }
   1479 
   1480 #if OPT_DONT_MATCH_NL_ON_DOT == 1
   1481     _regex_add_token_one_char(transition_list, transition_list_max, 0xa);
   1482 #endif
   1483 
   1484     sal_memset(bitmap, 0xff, sizeof(bitmap));
   1485     for (i = 0; (NULL != transition_list[i]) && (i < transition_list_max); i++) {
   1486         for (j = 0; j < 8; j++) {
   1487             bitmap[j] &= ~transition_list[i]->transition_map[j];
   1488         }
   1489     }
   1490 
   1491     /* Now add a transition for all characters not already in a transition. */
   1492     for (j = 0; j < COUNTOF(bitmap); j++) {
   1493         if (bitmap[j]) {
   1494             _regex_add_token_multi(transition_list, transition_list_max, bitmap);
   1495             break;
   1496         }
   1497     }
   1498 
   1499     /* Put characters that are listed in more than one class in their own class.  This
   1500      * should result in each character appearing in at most one class. */
   1501     for (i = 0; i < REGEX_MAX_CHARACTER_CLASSES; i++) {
   1502         /* k counts the number of classes in which a character is found. */
   1503         k = 0;
   1504         for (j = 0; j < transition_list_max; j++) {
   1505             if (transition_list[j] == NULL) {
   1506                 continue;
   1507             }
   1508             if (BITMASK_IS_SET(transition_list[j]->transition_map, i)) {
   1509                 k++;
   1510             }
   1511             /* If a character is in more than one class, no need to search for more
   1512              * classes.  It will definitely be moved to a new class.  Proceed to the code
   1513              * that removes this character from all classes. */
   1514             if (k >= 2) {
   1515                 break;
   1516             }
   1517         }
   1518         if (k >= 2) {
   1519             for (j = 0; j < transition_list_max; j++) {
   1520                 if (transition_list[j] == NULL) {
   1521                     continue;
   1522                 }
   1523                 if (BITMASK_IS_SET(transition_list[j]->transition_map, i)) {
   1524                     /* if this was the last character in the class, delete the class. */
   1525                     if (transition_list[j]->num_transitions == 1) {
   1526                         sal_free(transition_list[j]);
   1527                         transition_list[j] =  NULL;
   1528                     } else {
   1529                         BITMASK_UNSET(transition_list[j]->transition_map, i);
   1530                         transition_list[j]->num_transitions--;
   1531                     }
   1532                 }
   1533             }
   1534             /* Now create a new class with only this character. */
   1535             _regex_add_token_one_char(transition_list, transition_list_max, i);
   1536         }
   1537     }
   1538 
   1539     /* This variable holds the index of the first unused entry in transition_list.  Initialize to
   1540      * an invalid index. */
   1541     first_unused = -1;
   1542     /* Compact and remove any null class pointers and count the number of classes. */
   1543     for (count = 0, i = 0; i < transition_list_max; i++) {
   1544         if (NULL == transition_list[i]) {
   1545             if (first_unused < 0) {
   1546                 first_unused = i;
   1547             }
   1548         } else {
   1549             if (first_unused >= 0) {
   1550                 transition_list[first_unused] = transition_list[i];
   1551                 transition_list[i] = NULL;
   1552                 for (j = first_unused; j <= i; j++) {
   1553                     if (NULL == transition_list[j]) {
   1554                         first_unused = j;
   1555                         break;
   1556                     }
   1557                 }
   1558         }
   1559             count++;
   1560         }
   1561     }
   1562 
   1563     class_array = sal_alloc(sizeof(class_array[0]) * REGEX_MAX_CHARACTER_CLASSES, "class_array");
   1564     sal_memset(class_array, 0, sizeof(class_array[0]) * REGEX_MAX_CHARACTER_CLASSES);
   1565     cl_num = 0;
   1566     for (i = 0; i < count; i++) {
   1567         assert(NULL != transition_list[i]);
   1568         class = &class_array[cl_num];
   1569         class->num_transitions = 0;
   1570         for (j = 0; j < REGEX_MAX_CHARACTER_CLASSES; j++) {
   1571             if (BITMASK_IS_SET(transition_list[i]->transition_map, j)) {
   1572                 BITMASK_SET(class->transition_map, j);
   1573                 class->num_transitions++;
   1574             }
   1575         }
   1576         if (class->num_transitions) {
   1577             cl_num++;
   1578         }
   1579     }
   1580 
   1581     _shr_sort(class_array, count, sizeof(re_transition_class), sort_transition_class);
   1582 
   1583     for (i = 0; i < cl_num; i++) {
   1584         class_array[i].id = i;
   1585     }
   1586 
   1587 #if DUMP_SYMBOL_CLASSES == 1
   1588     RE_SAL_DPRINT(("\n\nNumber of classes: %d: \n", cl_num));
   1589     for (i = 0; i < cl_num; i++) {
   1590         class = &class_array[i];
   1591         lc = -1;
   1592         RE_SAL_DPRINT(("\nClass %d: ", class->id));
   1593         for (j = 0; j < REGEX_MAX_CHARACTER_CLASSES; j++) {
   1594             if (BITMASK_IS_SET(class->transition_map, j)) {
   1595                 if (lc == -1) {
   1596                     lc = j;
   1597                 }
   1598             } else {
   1599                 if (lc >= 0) {
   1600                     RE_SAL_DPRINT(("["));
   1601                     if (printable(lc)) {
   1602                         RE_SAL_DPRINT(("%c", lc));
   1603                     } else {
   1604                         RE_SAL_DPRINT(("\\%d", lc));
   1605                     }
   1606                     RE_SAL_DPRINT(("-"));
   1607                     if (printable(j - 1)) {
   1608                         RE_SAL_DPRINT(("%c", j - 1));
   1609                     } else {
   1610                         RE_SAL_DPRINT(("\\%d", j - 1));
   1611                     }
   1612                     RE_SAL_DPRINT(("]"));
   1613                     lc = -1;
   1614                 }
   1615             }
   1616         }
   1617         if (lc >= 0)  {
   1618             if (printable(lc)) {
   1619                 RE_SAL_DPRINT(("[%c", lc));
   1620             } else {
   1621                 RE_SAL_DPRINT(("[\\%d", lc));
   1622             }
   1623             RE_SAL_DPRINT(("-\\255]"));
   1624         }
   1625         RE_SAL_DPRINT(("\n"));
   1626         
   1627     }
   1628 #endif
   1629    
   1630     *pclass_array = class_array;
   1631     *num_classes  = cl_num;
   1632 
   1633 fail:
   1634     /* free up transition_lists */
   1635     if (transition_list) {
   1636         for (i = 0; i < transition_list_max; i++) {
   1637             if (transition_list[i]) {
   1638                 sal_free(transition_list[i]);
   1639         }
   1640     }
   1641         sal_free(transition_list);
   1642     }
   1643     if (rv) {
   1644         *num_classes = 0;
   1645         *pclass_array = NULL;
   1646         sal_free(class_array);
   1647     }
   1648     return rv;
   1649 }
   1650 
   1651 #if ENABLE_POST_DUMP==1
   1652 static void dump_post(re_wc *postfix, int detail)
   1653 {
   1654     re_wc *p;
   1655 
   1656     RE_SAL_DPRINT(("\n-------Postfix for re\n\n"));
   1657     for (p = postfix; WSTR_DATA_VALID(p); WSTR_PTR_INC(p, 1)) {
   1658         RE_SAL_DPRINT(("%s%d:", POST_EN_IS_META(p) ? "m" : "c", p->c));
   1659     }
   1660     RE_SAL_DPRINT(("\n"));
   1661     for(p=postfix; WSTR_DATA_VALID(p); WSTR_PTR_INC(p,1)) {
   1662         if (POST_EN_IS_META(p)) {
   1663             if (printable(p->c)) {
   1664                 RE_SAL_DPRINT(("%c", p->c));
   1665             }
   1666             else
   1667             {
   1668                 RE_SAL_DPRINT(("[m%d]", p->c));
   1669             }
   1670         } else {
   1671             RE_SAL_DPRINT(("[%d]", p->c));
   1672         }
   1673     }
   1674     RE_SAL_DPRINT(("\n"));
   1675 }
   1676 #endif
   1677 
   1678 static re_wc* 
   1679 re_convert_tokens_to_class(char *re, unsigned int re_flag, 
   1680                                 re_transition_class *pclass_array, int num_classes)
   1681 {
   1682     re_wc *output_wchar;
   1683     int   re_length, used = 0, esc = 0, mod_re_length = 0, c;
   1684     unsigned int d;
   1685     int oct[4], j;
   1686     unsigned int bitmap[8];
   1687 
   1688     re_length = sal_strlen(re);
   1689     if (!re_length) {
   1690         return NULL;
   1691     }
   1692 
   1693     /* 
   1694      * each character uses 2 bytes, since \0 is valid data, so inorder to
   1695      * distinguish end of string with \0, we store metadata and character.
   1696      */
   1697     mod_re_length = re_length + 1;
   1698     if (0 == (re_flag & BCM_TR3_REGEX_CFLAG_ANCHORED)) {
   1699         mod_re_length += 2;
   1700     }
   1701     output_wchar = sal_alloc(mod_re_length * sizeof(re_wc), "re2class");
   1702     used = 0;
   1703 
   1704     /* If the RE is not anchored at the beginning of the packet, then insert an atom that
   1705      * will match anything (.*) to begin the RE. */
   1706     if (0 == (re_flag & BCM_TR3_REGEX_CFLAG_ANCHORED)) {
   1707         get_class_bitmap('.', bitmap);
   1708         if (re_add_multi_class(pclass_array, num_classes,
   1709                                bitmap, &output_wchar, &used, &mod_re_length)) {
   1710             RE_SAL_DPRINT(("\n-------Error re_add_multi_class '.'\n\n"));
   1711             goto fail;
   1712         }
   1713         ADD_DATA('*', &output_wchar, &used, &mod_re_length);
   1714     }
   1715 
   1716     while(*re) {
   1717         switch(*re) {
   1718             case '\\':
   1719                 if (!esc) {
   1720                     esc = 1;
   1721                 } else {
   1722                     if (re_add_single_class(pclass_array, num_classes, *re,
   1723                                                         &output_wchar, &used, &mod_re_length)) {
   1724                         RE_SAL_DPRINT(("\n-------Error re_add_single_class '\'\n\n"));
   1725                         goto fail;
   1726                     }
   1727                     esc = 0;
   1728                 }
   1729                 break;
   1730             case '[':
   1731                 if (esc) {
   1732                     esc = 0;
   1733                     if (re_add_single_class(pclass_array, num_classes,
   1734                                                 *re, &output_wchar, &used, &mod_re_length)) {
   1735                         RE_SAL_DPRINT(("\n-------Error re_add_single_class '['\n\n"));
   1736                         goto fail;
   1737                     }
   1738                 } else {
   1739                     re_make_char_class_bitmap(&re, bitmap, 0, re_flag ? re_flag : 0);
   1740                     if (re_add_multi_class(pclass_array, num_classes,
   1741                                             bitmap, &output_wchar, &used, &mod_re_length)) {
   1742                         RE_SAL_DPRINT(("\n-------Error re_add_multi_class '['\n\n"));
   1743                         goto fail;
   1744                     }
   1745                 }
   1746                 break;
   1747             case '{':
   1748                 if (esc) {
   1749                     esc = 0;
   1750                     if (re_add_single_class(pclass_array, num_classes,
   1751                                                 *re, &output_wchar, &used, &mod_re_length)) {
   1752                         RE_SAL_DPRINT(("\n-------Error re_add_single_class '{'\n\n"));
   1753                         goto fail;
   1754                     }
   1755                 } else {
   1756                     do {
   1757                         ADD_DATA(*re, &output_wchar, &used, &mod_re_length);
   1758                     } while (*re++ != '}');
   1759                     continue;
   1760                 }
   1761                 break;
   1762             default:
   1763                 if (!esc) {
   1764                     if (*re == '.') {
   1765                         get_class_bitmap(*re, bitmap);
   1766                         if (re_add_multi_class(pclass_array, num_classes,
   1767                                                 bitmap, &output_wchar, &used, &mod_re_length)) {
   1768                             RE_SAL_DPRINT(("\n-------Error re_add_multi_class default '.'\n\n"));
   1769                             goto fail;
   1770                         }
   1771                     } else {
   1772                         if (is_metachar(*re)) {
   1773                             ADD_DATA(*re, &output_wchar, &used, &mod_re_length);
   1774                         } else {
   1775                             if ((re_flag & BCM_TR3_REGEX_CFLAG_EXPAND_LCUC) &&
   1776                                 (re_tolower(*re) != re_toupper(*re))) {
   1777                                 ADD_DATA('(', &output_wchar, &used, &mod_re_length);
   1778                                 if (re_add_single_class(pclass_array, num_classes,
   1779                                                  re_tolower(*re), &output_wchar, &used, &mod_re_length)) {
   1780                                     RE_SAL_DPRINT(("\n-------Error re_add_single_class meta '{'\n\n"));
   1781                                     goto fail;
   1782                                 }
   1783                                 ADD_DATA('|', &output_wchar, &used, &mod_re_length);
   1784                                 if (re_add_single_class(pclass_array, num_classes,
   1785                                                   re_toupper(*re), &output_wchar, &used, &mod_re_length)) {
   1786                                     RE_SAL_DPRINT(("\n-------Error re_add_single_class meta '|'\n\n"));
   1787                                     goto fail;
   1788                                 }
   1789                                 ADD_DATA(')', &output_wchar, &used, &mod_re_length);
   1790                             } else {
   1791                                 if (re_add_single_class(pclass_array, num_classes,
   1792                                                             *re, &output_wchar, &used, &mod_re_length)) {
   1793                                     RE_SAL_DPRINT(("\n-------Error re_add_single_class meta '}'\n\n"));
   1794                                     goto fail;
   1795                                 }
   1796                             }
   1797                         }
   1798                     }
   1799                 } else {
   1800                     switch(*re) {
   1801                         case 'd':
   1802                         case 'D':
   1803                         case 'w':
   1804                         case 'W':
   1805                         case 's':
   1806                         case 'S':
   1807                         case 'n':
   1808                         case 'r':
   1809                         case 't':
   1810                             get_class_bitmap(*re, bitmap);
   1811                             if (re_add_multi_class(pclass_array, num_classes,
   1812                                                         bitmap, &output_wchar, &used, &mod_re_length)) {
   1813                                 RE_SAL_DPRINT(("\n-------Error re_add_multi_class special 'dDwWsSnrt'\n\n"));
   1814                                 goto fail;
   1815                             }
   1816                             break;
   1817                         case 'u':
   1818                             re += 2; /* ?? */
   1819                         case 'x':
   1820                             if (_regex_decode_hex(re+1, &d)) {
   1821                                 goto fail;
   1822                             }
   1823                             re += 2;
   1824                             if (re_add_single_class(pclass_array, num_classes, d,
   1825                                                 &output_wchar, &used, &mod_re_length)) {
   1826                                 RE_SAL_DPRINT(("\n-------Error re_add_single_class 'x'\n\n"));
   1827                                 goto fail;
   1828                             }
   1829                             break;
   1830                         default:
   1831                             c = *re;
   1832                             if ((*re >= '0') && (*re <= '9')) {
   1833                                 /* octal */
   1834                                 j = 0;
   1835                                 while (*re && (*re >= '0') && (*re <= '9') && (j < 2)) {
   1836                                     oct[j++] = *re++;
   1837                                 }
   1838                                 re--;
   1839                                 c = 0;
   1840                                 while(j > 0) {
   1841                                     c = (c*8) + (oct[j-1] - '0');
   1842                                     j--;
   1843                                 }
   1844                             }
   1845                             if (re_add_single_class(pclass_array, num_classes,
   1846                                                     c, &output_wchar, &used, &mod_re_length)) {
   1847                                 RE_SAL_DPRINT(("\n-------Error re_add_single_class default\n\n"));
   1848                                 goto fail;
   1849                             }
   1850                             break;
   1851                     }
   1852                     esc = 0;
   1853                 }
   1854                 break;
   1855         }
   1856         re++;
   1857     }
   1858 
   1859     ADD_META_DATA('\0', &output_wchar, &used, &mod_re_length);
   1860 
   1861 #if ENABLE_POST_DUMP==1
   1862     RE_SAL_DPRINT(("\nchar re\n"));
   1863     dump_post(output_wchar, 1);
   1864 #endif
   1865 
   1866     return output_wchar;
   1867 
   1868 fail:
   1869     sal_free(output_wchar);
   1870     return NULL;
   1871 }
   1872 
   1873 static re_wc * re_preprocess(re_wc *re)
   1874 {
   1875     int   min, max;
   1876     int   l, used = 0, esc = 0, m, c, j, skip;
   1877     char  mc;
   1878     int   toklen = 0, star;
   1879     int    ts[100], stackp, curtok_off = 0;
   1880     re_wc *curtok = NULL, *o;
   1881 
   1882 #define pusht(off) ts[stackp++] = (off)
   1883 #define popt() (stackp == 0) ? -1 : ts[--stackp]
   1884 
   1885     stackp = 0;
   1886 
   1887     l = wstrlen(re);
   1888     if (!l) {
   1889         return NULL;
   1890     }
   1891     
   1892     m = l+1;
   1893     o = sal_alloc(m*sizeof(re_wc),"repreprocess");
   1894     used = 0;
   1895 
   1896     while(WSTR_DATA_VALID(re)) {
   1897         /* make sure we have enough room */
   1898         switch(WSTR_GET_DATA(re)) {
   1899             case '{':
   1900                 if (esc) {
   1901                     ADD_DATA(WSTR_GET_DATA(re), &o, &used, &m);
   1902                 } else {
   1903                     #if 0
   1904                     if (!curtok) {
   1905                         goto FAIL;
   1906                     }
   1907                     #endif
   1908                     if (toklen <= 0) {
   1909                         goto FAIL;
   1910                     }
   1911                     /* decode min, max */
   1912                     min = parse_digit_from_range(&re, &mc);
   1913                     if (min == INFINITE) {
   1914                         goto FAIL;
   1915                     } else if (mc == '}') {
   1916                         max = min;
   1917                     } else {
   1918                         max = parse_digit_from_range(&re, &mc);
   1919                     }
   1920                     skip = 1;
   1921 
   1922                     /* repeat the previous token */
   1923                     if (min) {
   1924                         /* since token is already put in output once, do it min-1*/
   1925                         for (c = 0; c < min; c++) {
   1926                             if (skip) {
   1927                                 skip--;
   1928                                 continue;
   1929                             }
   1930                             j = 0;
   1931                             while (j < toklen) {
   1932                                 curtok = o + curtok_off;
   1933                                 ADD_DATA(WSTR_GET_DATA_AT_OFF(curtok,j), 
   1934                                                             &o, &used, &m);
   1935                                 j++;
   1936                             }
   1937                         }
   1938                     }
   1939                     star = 0;
   1940                     if (max == INFINITE) {
   1941                         max = 1;
   1942                         star = 1;
   1943                     } else {
   1944                         max -= min;
   1945                     }
   1946                     if (max > 0) {
   1947                         for (c = 0; c < max; c++) {
   1948                             if (skip == 0) {
   1949                                 j = 0;
   1950                                 while (j < toklen) {
   1951                                     curtok = o + curtok_off;
   1952                                     ADD_DATA(WSTR_GET_DATA_AT_OFF(curtok,j), 
   1953                                              &o, &used, &m);
   1954                                     j++;
   1955                                 }
   1956                             } else {
   1957                                 skip--;
   1958                             }
   1959                             ADD_DATA(star ? '*' : '?', &o, &used, &m);
   1960                         }
   1961                     } 
   1962                     curtok = NULL;
   1963                     toklen = 0;
   1964                 }
   1965                 break;
   1966 
   1967             case '(':
   1968                 pusht(used);
   1969                 ADD_DATA(WSTR_GET_DATA(re), &o, &used, &m);
   1970                 break;
   1971 
   1972             case ')':
   1973                 ADD_DATA(WSTR_GET_DATA(re), &o, &used, &m);
   1974                 curtok_off = popt();
   1975                 toklen = used - curtok_off;
   1976                 break;
   1977 
   1978             case '\\':
   1979                 curtok_off = used;
   1980                 ADD_DATA(WSTR_GET_DATA(re), &o, &used, &m);
   1981                 WSTR_PTR_INC(re,1);
   1982                 ADD_DATA(WSTR_GET_DATA(re), &o, &used, &m);
   1983                 toklen = 2;
   1984                 break;
   1985 
   1986             default:
   1987                 curtok_off = used;
   1988                 toklen = 1;
   1989                 ADD_DATA(WSTR_GET_DATA(re), &o, &used, &m);
   1990                 break;
   1991         }
   1992         WSTR_PTR_INC(re,1);
   1993     }
   1994     ADD_META_DATA('\0', &o, &used, &m);
   1995     return o;
   1996 FAIL:
   1997     sal_free(o);
   1998     return NULL;
   1999 }
   2000 
   2001 #define REPOST_STK_SIZE 100
   2002 static re_wc* re2post(re_wc *re)
   2003 {
   2004     int nalt, natom, lmc = 0;
   2005     int      size, used = 0;
   2006     re_wc *dst, *post; /* *start */
   2007     struct {
   2008         int nalt;
   2009         int natom;
   2010     } paren[REPOST_STK_SIZE], *p;
   2011 
   2012     if (!re) {
   2013         return NULL;
   2014     }
   2015     /* start = re; */
   2016     p = paren;
   2017     size = wstrlen(re) * 4;
   2018     post = dst = sal_alloc(sizeof(re_wc)*size,"re2post");
   2019     nalt = 0;
   2020     natom = 0;
   2021     for(; WSTR_DATA_VALID(re); WSTR_PTR_INC(re,1)) {
   2022         switch(WSTR_GET_DATA(re)) {
   2023             case '(':
   2024                 if (natom > 1) {
   2025                     --natom;
   2026                     ADD_META_DATA('.', &dst, &used, &size);
   2027                 }
   2028                 if (p >= paren+REPOST_STK_SIZE) {
   2029                     RE_SAL_DPRINT(("paren stack full..\n"));
   2030                     goto fail;
   2031                 }
   2032                 p->nalt = nalt;
   2033                 p->natom = natom;
   2034                 p++;
   2035                 nalt = 0;
   2036                 natom = 0;
   2037                 lmc = 0;
   2038                 break;
   2039             case '|':
   2040                 if (natom == 0) {
   2041                     RE_SAL_DPRINT(("No atoms to connect..\n"));
   2042                     goto fail;
   2043                 }
   2044                 while(--natom > 0) {
   2045                     ADD_META_DATA('.', &dst, &used, &size);
   2046                 }
   2047                 nalt++;
   2048                 lmc = 0;
   2049                 break;
   2050             case ')':
   2051                 if (p == paren) {
   2052                     RE_SAL_DPRINT(("point to paren to and yet paren found..\n"));
   2053                     goto fail;
   2054                 }
   2055                 if (natom == 0) {
   2056                     RE_SAL_DPRINT(("No atom in ) case....\n"));
   2057                     return NULL;
   2058                 }
   2059                 while(--natom > 0) {
   2060                     ADD_META_DATA('.', &dst, &used, &size);
   2061                 }
   2062                 for(; nalt > 0; nalt--) {
   2063                     ADD_META_DATA('|', &dst, &used, &size);
   2064                 }
   2065                 --p;
   2066                 nalt = p->nalt;
   2067                 natom = p->natom;
   2068                 natom++;
   2069                 lmc = 0;
   2070                 break;
   2071             case '*':
   2072             case '+':
   2073             case '?':
   2074                 if (lmc) {
   2075                     RE_SAL_DPRINT(("error: meta char without atoms\n"));
   2076                     goto fail;
   2077                 }
   2078                 if (natom == 0) {
   2079                     RE_SAL_DPRINT(("No atom in + or * or ? case....\n"));
   2080                     goto fail;
   2081                 }
   2082                 ADD_META_DATA(WSTR_GET_DATA(re), &dst, &used, &size);
   2083                 lmc = 1;
   2084                 break;
   2085             default:
   2086                 lmc = 0;
   2087                 if (natom > 1) {
   2088                     --natom;
   2089                     ADD_META_DATA('.', &dst, &used, &size);
   2090                 }
   2091                 if (WSTR_GET_DATA(re) == '\\') {
   2092                     WSTR_PTR_INC(re,1);
   2093                 }
   2094                 ADD_DATA(WSTR_GET_DATA(re), &dst, &used, &size);
   2095                 natom++;
   2096                 break;
   2097         }
   2098     }
   2099     if (p != paren) {
   2100         return NULL;
   2101     }
   2102     while(--natom > 0) {
   2103         ADD_META_DATA('.', &dst, &used, &size);
   2104     }
   2105     for(; nalt > 0; nalt--) {
   2106         ADD_META_DATA('|', &dst, &used, &size);
   2107     }
   2108     ADD_META_DATA('\0', &dst, &used, &size);
   2109 
   2110 #if ENABLE_POST_DUMP==1
   2111     dump_post(post, 1);
   2112 #endif
   2113 
   2114     return post;
   2115     
   2116 fail:
   2117     sal_free(dst);
   2118     return NULL;
   2119 }
   2120 
   2121 
   2122 /* Allocate and initialize re_nfa_state_t */
   2123 re_nfa_state_t*
   2124 new_nfa_state(re_nfa_t *pnfa, int class, re_nfa_state_t *out, re_nfa_state_t *out1)
   2125 {
   2126     re_nfa_state_t *state, **prev;
   2127     int size;
   2128 
   2129     if (pnfa->state_map_size == pnfa->num_states) {
   2130         prev = pnfa->state_map;
   2131         size = sizeof(re_nfa_state_t*)*(pnfa->state_map_size+NFA_STATE_BLOCK_SIZE);
   2132         pnfa->state_map = sal_alloc(size,"nfa_stpp");
   2133         sal_memset(pnfa->state_map, 0, size);
   2134         if (prev) {
   2135             sal_memcpy(pnfa->state_map, prev,
   2136                             sizeof(re_nfa_state_t*)*pnfa->state_map_size);
   2137             sal_free(prev);
   2138         }
   2139 
   2140         pnfa->state_map_size += NFA_STATE_BLOCK_SIZE;
   2141     }
   2142 
   2143 
   2144     /* alloc new block for NFA states if full */
   2145     state = _alloc_space_for_nfa_nodes(pnfa, DFA_STATE_BLOCK_SIZE, 1);
   2146     
   2147     state->lastlist = 0;
   2148     state->class = class;
   2149     state->out = out;
   2150     state->out1 = out1;
   2151     state->id = pnfa->num_states++;
   2152     pnfa->state_map[state->id] = state;
   2153     return state;
   2154 }
   2155 
   2156 typedef struct re_nfa_frag_t re_nfa_frag_t;
   2157 typedef union re_nfa_ptrl_t re_nfa_ptrl_t;
   2158 struct re_nfa_frag_t
   2159 {
   2160     re_nfa_state_t *start;
   2161     re_nfa_ptrl_t *out;
   2162 };
   2163 
   2164 DEFINE_STACK(frag, re_nfa_frag_t);
   2165 
   2166 /* Initialize re_nfa_frag_t struct. */
   2167 static re_nfa_frag_t frag(re_nfa_state_t *start, re_nfa_ptrl_t *out)
   2168 {
   2169     re_nfa_frag_t n = { start, out };
   2170     return n;
   2171 }
   2172 
   2173 /*
   2174  * Since the out pointers in the list are always 
   2175  * uninitialized, we use the pointers themselves
   2176  * as storage for the Ptrlists.
   2177  */
   2178 union re_nfa_ptrl_t
   2179 {
   2180     re_nfa_ptrl_t *next;
   2181     re_nfa_state_t *s;
   2182 };
   2183 
   2184 /* Create singleton list containing just outp. */
   2185 static re_nfa_ptrl_t* list1(re_nfa_state_t **outp)
   2186 {
   2187     re_nfa_ptrl_t *l;
   2188 
   2189     l = (re_nfa_ptrl_t*)outp;
   2190     l->next = NULL;
   2191     return l;
   2192 }
   2193 
   2194 /* Patch the list of states at out to point to start. */
   2195 static void patch(re_nfa_ptrl_t *l, re_nfa_state_t *s)
   2196 {
   2197     re_nfa_ptrl_t *next;
   2198 
   2199     for(; l; l=next) {
   2200         next = l->next;
   2201         l->s = s;
   2202     }
   2203 }
   2204 
   2205 /* Join the two lists l1 and l2, returning the combination. */
   2206 static re_nfa_ptrl_t* ptrl_append(re_nfa_ptrl_t *l1, re_nfa_ptrl_t *l2)
   2207 {
   2208     re_nfa_ptrl_t *oldl1;
   2209 
   2210     oldl1 = l1;
   2211     while(l1->next) {
   2212         l1 = l1->next;
   2213     }
   2214     l1->next = l2;
   2215     return oldl1;
   2216 }
   2217 
   2218 static re_nfa_state_t* post2nfa(re_nfa_t *pnfa, re_wc *postfix, int match_idx)
   2219 {
   2220     re_wc *p;
   2221     re_nfa_frag_t e1, e2, e;
   2222     re_nfa_state_t *s;
   2223     re_nfa_state_t *matchstate;
   2224     DECLARE_STACK(frag) fstack;
   2225 
   2226     if (postfix == NULL) {
   2227         return NULL;
   2228     }
   2229 
   2230     STACK_INIT(&fstack, 1024, "post_stk");
   2231 
   2232     if (!STACK_VALID(&fstack)) {
   2233         return NULL;
   2234     }
   2235 
   2236 #define push(s) STACK_PUSH(&fstack,s)
   2237 #define pop()   STACK_POP(&fstack)
   2238 #define validate_stack if (STACK_EMPTY(&fstack)) break
   2239  
   2240     for(p=postfix; WSTR_DATA_VALID(p); WSTR_PTR_INC(p,1)) {
   2241         if (POST_EN_IS_META(p)) {
   2242             switch(p->c) {
   2243                 case '.':	/* catenate */
   2244                     validate_stack; 
   2245                     e2 = pop();
   2246                     validate_stack; 
   2247                     e1 = pop();
   2248                     patch(e1.out, e2.start);
   2249                     push(frag(e1.start, e2.out));
   2250                     break;
   2251                 case '|':	/* alternate */
   2252                     validate_stack; 
   2253                     e2 = pop();
   2254                     validate_stack; 
   2255                     e1 = pop();
   2256                     s = new_nfa_state(pnfa, Split, e1.start, e2.start);
   2257                     push(frag(s, ptrl_append(e1.out, e2.out)));
   2258                     break;
   2259                 case '?':	/* zero or one */
   2260                     validate_stack; 
   2261                     e = pop();
   2262                     s = new_nfa_state(pnfa, Split, e.start, NULL);
   2263                     push(frag(s, ptrl_append(e.out, list1(&s->out1))));
   2264                     break;
   2265                 case '*':	/* zero or more */
   2266                     validate_stack; 
   2267                     e = pop();
   2268                     s = new_nfa_state(pnfa, Split, e.start, NULL);
   2269                     patch(e.out, s);
   2270                     push(frag(s, list1(&s->out1)));
   2271                     break;
   2272                 case '+':	/* one or more */
   2273                     validate_stack; 
   2274                     e = pop();
   2275                     s = new_nfa_state(pnfa, Split, e.start, NULL);
   2276                     patch(e.out, s);
   2277                     push(frag(e.start, list1(&s->out1)));
   2278                     break;
   2279             }
   2280         } else {
   2281             s = new_nfa_state(pnfa, p->c, NULL, NULL);
   2282             push(frag(s, list1(&s->out)));
   2283         }
   2284     }
   2285 
   2286     e = pop();
   2287     if (!STACK_EMPTY(&fstack))  {
   2288         
   2289         return NULL;
   2290     }
   2291     STACK_DEINIT(&fstack);
   2292 
   2293     matchstate = new_nfa_state(pnfa, Match + match_idx, NULL, NULL);
   2294     patch(e.out, matchstate);
   2295     return e.start;
   2296 #undef pop
   2297 #undef push
   2298 }
   2299 
   2300 static void all_states_connected_by_epsilon(re_nfa_t *nfa,
   2301                             re_nfa_list_t *l, re_nfa_state_t *s);
   2302 static void step(re_nfa_t *nfa, re_nfa_list_t*, int, re_nfa_list_t*);
   2303 
   2304 /* Compute initial state list */
   2305 static re_nfa_list_t* closure_0(re_nfa_t *nfa, re_nfa_state_t *start, 
   2306                                 re_nfa_list_t *l)
   2307 {
   2308     listid++;
   2309     NFA_LIST_RESET(nfa, l);
   2310     all_states_connected_by_epsilon(nfa, l, start);
   2311     return l;
   2312 }
   2313 
   2314 static void all_states_connected_by_epsilon(re_nfa_t *nfa, 
   2315                                 re_nfa_list_t *nlist, re_nfa_state_t *s)
   2316 {
   2317     DECLARE_STACK(nfa_states) *stk;
   2318 
   2319     stk = nfa->stk;
   2320 
   2321     STACK_RESET(stk);
   2322     STACK_PUSH(stk, s);
   2323 
   2324     while(!STACK_EMPTY(stk)) {
   2325         s = STACK_POP(stk);
   2326         if (s->lastlist == listid) {
   2327             continue;
   2328         }
   2329 
   2330         if (s->class == Split) {
   2331             STACK_PUSH(stk, s->out);
   2332             STACK_PUSH(stk, s->out1);
   2333             continue;
   2334         }
   2335         s->lastlist = listid;
   2336         nlist->state_map[s->id/32] |= (1 << (s->id % 32));
   2337         nlist->num_states++;
   2338     }
   2339 }
   2340 
   2341 static void step(re_nfa_t *nfa, re_nfa_list_t *clist, 
   2342                     int c, re_nfa_list_t *nlist)
   2343 {
   2344     int i, j, word_size;
   2345     re_nfa_state_t *s;
   2346     unsigned int val, *cmap;
   2347 
   2348     listid++;
   2349     NFA_LIST_RESET(nfa, nlist);
   2350 
   2351     cmap = nfa->class_map[c];
   2352     word_size = NFA_SMAP_WORD_SIZE(nfa);
   2353     for (i=0; i<word_size; i++) {
   2354         val = cmap[i] & clist->state_map[i];
   2355         for (j = 0; val && (j < 32); j++) {
   2356             if ((val & (1 << j)) == 0) {
   2357                 continue;
   2358             }
   2359             val &= ~(1 << j);
   2360             s = nfa->state_map[(i*32)+j];
   2361             all_states_connected_by_epsilon(nfa, nlist, s->out);
   2362         }
   2363     }
   2364 }
   2365 
   2366 /* Compare lists: first by length, then by members. */
   2367 static int
   2368 listcmp(re_nfa_list_t *l1, re_nfa_list_t *l2)
   2369 {
   2370     int i;
   2371 
   2372     if (l1->num_states < l2->num_states) {
   2373         return -1;
   2374     }
   2375     if (l1->num_states > l2->num_states) {
   2376         return 1;
   2377     }
   2378 
   2379     i = sal_memcmp(l1->state_map, l2->state_map, state_map_byte_size);
   2380     i = (i < 0) ? -1 : ((i > 0) ? 1 : 0);
   2381     return i;
   2382 }
   2383 
   2384 static re_dfa_state_t* 
   2385 _lookup_dfa_from_cache(re_dfa_t *pdfa, re_nfa_list_t *l)
   2386 {
   2387     int i;
   2388     avn_t *node;
   2389 
   2390     node = pdfa->avtree;
   2391     while(node) {
   2392         i = listcmp(&node->data->l, l);
   2393         if (i == 0) {
   2394             return node->data;
   2395         } else {
   2396             node = (i < 0) ? node->ds[1] : node->ds[0];
   2397         }
   2398     }
   2399     return NULL;
   2400 }
   2401 
   2402 static avn_t *rotate_single(avn_t *root, int dir)
   2403 {
   2404     avn_t *save = root->ds[!dir];
   2405     root->ds[!dir] = save->ds[dir];
   2406     save->ds[dir] = root;
   2407     return save;
   2408 }
   2409 
   2410 static avn_t *rotate_double (avn_t *root, int dir)
   2411 {
   2412     avn_t *save = root->ds[!dir]->ds[dir];
   2413 
   2414     root->ds[!dir]->ds[dir] = save->ds[!dir];
   2415     save->ds[!dir] = root->ds[!dir];
   2416     root->ds[!dir] = save;
   2417 
   2418     save = root->ds[!dir];
   2419     root->ds[!dir] = save->ds[dir];
   2420     save->ds[dir] = root;
   2421 
   2422     return save;
   2423 }
   2424 
   2425 static avn_t *
   2426 _add_dfa_state_to_cache(avn_t *root, avn_t *newen, 
   2427                         re_dfa_state_t* d, int *done)
   2428 {
   2429     int dir, bal, diff;
   2430     avn_t *n, *nn;
   2431 
   2432     if (!root) {
   2433         newen->balance = 0;
   2434         newen->data = d;
   2435         newen->ds[0] = newen->ds[1] = NULL;
   2436         return newen;
   2437     } else {
   2438         diff = listcmp(&root->data->l, &d->l);
   2439         if (diff == 0) {
   2440             return root;
   2441         }
   2442         dir = (diff < 0);
   2443         root->ds[dir] = _add_dfa_state_to_cache(root->ds[dir], newen, d, done);
   2444         if ( !*done ) {
   2445             root->balance += (dir == 0) ? -1 : +1;
   2446             if (root->balance == 0) {
   2447                 *done = 1;
   2448             } else if ((root->balance > 1) || (root->balance < -1)) {
   2449                 n = root->ds[dir];
   2450                 bal = (dir == 0) ? -1 : 1;
   2451                 if ( n->balance == bal ) {
   2452                     root->balance = n->balance = 0;
   2453                     root = rotate_single(root, !dir);
   2454                 }
   2455                 else { 
   2456                     n = root->ds[dir];
   2457                     nn = n->ds[!dir];
   2458 
   2459                     if (nn->balance == 0) {
   2460                         root->balance = n->balance = 0;
   2461                     } else if (nn->balance == bal) {
   2462                         root->balance = -bal;
   2463                         n->balance = 0;
   2464                     } else {
   2465                         root->balance = 0;
   2466                         n->balance = bal;
   2467                     }
   2468 
   2469                     nn->balance = 0;
   2470                     root = rotate_double(root, !dir );
   2471                 }
   2472                 *done = 1;
   2473             }
   2474         }
   2475     }
   2476     return root;
   2477 }
   2478 
   2479 
   2480 /*
   2481  * Return the cached re_dfa_state_t for list l,
   2482  * creating a new one if needed.
   2483  */
   2484 static int state_id = 0;
   2485 
   2486 static re_dfa_state_t* 
   2487 new_dfa_state(re_nfa_list_t *l, int num_classes, re_dfa_t *pdfa, re_nfa_t *nfa)
   2488 {
   2489     int size, done;
   2490     re_dfa_state_t *d, **prev;
   2491     avn_t *avn;
   2492 
   2493     /* lookup dfa state (list of nfa states) in cache if exist. */
   2494     d = _lookup_dfa_from_cache(pdfa, l);
   2495     if (d) {
   2496         return d;
   2497     }
   2498 
   2499     /* DFA states are stored as an array. If the number of entries
   2500      * in the array is equal to array size, grow the array */
   2501     if (pdfa->num_states == pdfa->size) {
   2502         if(pdfa->num_states >= REGEX_MAX_DFA_STATES) {
   2503             /* Stop */ 
   2504             return NULL;
   2505         }
   2506         prev = pdfa->states;
   2507         size = sizeof(re_dfa_state_t*)*(pdfa->size+DFA_BLOCK_SIZE);
   2508         pdfa->states = sal_alloc(size,"dfa_stpp");
   2509         if(! pdfa->states) {
   2510             pdfa->states = prev;
   2511             return NULL;
   2512         }
   2513         mem_cou += size;
   2514         if (prev) {
   2515             sal_memcpy(pdfa->states, prev, sizeof(re_dfa_state_t*)*pdfa->size);
   2516             sal_free(prev);
   2517         }
   2518 
   2519         /* Alloc dfa state block */
   2520         if (!_alloc_dfa_state_block(pdfa->states + pdfa->size, num_classes)) {
   2521             return NULL;
   2522         }
   2523         pdfa->size += DFA_BLOCK_SIZE;
   2524     }
   2525 
   2526     d = pdfa->states[pdfa->num_states];
   2527     d->l.state_map = _alloc_space_for_nfa_state_list(pdfa, NFA_SMAP_WORD_SIZE(nfa));
   2528     mem_cou += NFA_SMAP_WORD_SIZE(nfa);
   2529     sal_memcpy(d->l.state_map, l->state_map, NFA_SMAP_BYTE_SIZE(nfa));
   2530     d->l.num_states = RE_NFA_LIST_LENGTH(l);
   2531 
   2532     /* alloc space for avl node */
   2533     avn = _alloc_space_for_avltree_nodes(pdfa, DFA_BLOCK_SIZE, 1);
   2534     mem_cou += DFA_BLOCK_SIZE;
   2535     done = 0;
   2536     pdfa->avtree = _add_dfa_state_to_cache(pdfa->avtree, avn, d, &done);
   2537 
   2538     return d;
   2539 }
   2540 
   2541 static re_dfa_state_t* 
   2542 next_dfa_state_on_transition(re_dfa_state_t *d, int c, re_nfa_list_t *l1, 
   2543                              int num_classes, re_dfa_t *pdfa, re_nfa_t *nfa)
   2544 {
   2545     step(nfa, &d->l, c, l1);
   2546     return new_dfa_state(l1, num_classes, pdfa, nfa);
   2547 }
   2548 
   2549 static int add_state_to_dfa(re_dfa_t *pdfa, re_dfa_state_t *d)
   2550 {
   2551 #if DUMP_DFA_STATE == 1
   2552     int num_states = 0;
   2553 #endif
   2554 
   2555     /* check if already exist */
   2556     if (RE_DFA_IS_ADDED_TO_LIST(d)) {
   2557         return 0;
   2558     }
   2559     RE_DFA_SET_STATEID(d, pdfa->num_states);
   2560     RE_DFA_ADD_TO_LIST(d);
   2561 
   2562 #if DUMP_DFA_STATE == 1
   2563     {
   2564         int k, l, word_size;
   2565         word_size = state_map_byte_size / sizeof(unsigned int);
   2566         RE_SAL_DPRINT(("DFA State %d represents nfa states:\n", pdfa->num_states));
   2567         for (k = 0; k < word_size; k++) {
   2568             if (d->l.state_map[k] == 0) {
   2569                 continue;
   2570             }
   2571             for (l = 0; l < 32; l++) {
   2572                 if (d->l.state_map[k] & (1 << l)) {
   2573                     num_states++;
   2574                     RE_SAL_DPRINT((" %d,", (k*32)+l));
   2575                 }
   2576             }
   2577         }
   2578         RE_SAL_DPRINT(("\n"));
   2579         RE_SAL_DPRINT(("DFA State %d represents %d nfa states total\n\n", pdfa->num_states, num_states));
   2580     }
   2581 #endif
   2582     pdfa->num_states++;
   2583     return 0;
   2584 }
   2585 
   2586 static re_dfa_state_t*
   2587 get_next_unmarked_dstate(re_dfa_t *l, int skip)
   2588 {
   2589     int ii;
   2590     re_dfa_state_t *d;
   2591 
   2592     if (skip < 0) {
   2593         skip = 0;
   2594     }
   2595 
   2596     for (ii = skip; ii < l->num_states; ii++) {
   2597         d = l->states[ii];
   2598         if(!d) {
   2599             return NULL;
   2600         }
   2601         if (!RE_DFA_IS_MARKED(d)) {
   2602             return d;
   2603         }
   2604     }
   2605     return NULL;
   2606 }
   2607 
   2608 static int get_transition_list(re_nfa_t *nfa, re_dfa_state_t *d, 
   2609                                 unsigned char *transition_list, int *ntr)
   2610 {
   2611     re_nfa_state_t *s;
   2612     int     c, i, j, word_size, ctr;
   2613     unsigned int val;
   2614     unsigned int transition_map[8];
   2615 
   2616     ctr = *ntr = 0;
   2617     sal_memset(transition_map, 0, sizeof(unsigned int)*8);
   2618 
   2619     word_size = NFA_SMAP_WORD_SIZE(nfa);
   2620     for (i=0; i<word_size; i++) {
   2621         if (d->l.state_map[i] == 0) {
   2622             continue;
   2623         }
   2624         val = d->l.state_map[i];
   2625         for (j = 0; val && (j < 32); j++) {
   2626             if ((val & (1 << j)) == 0) {
   2627                 continue;
   2628             }
   2629             val &= ~(1 << j);
   2630             s = nfa->state_map[(i*32)+j];
   2631             if (s->class >= Match) {
   2632                 continue;
   2633             }
   2634             c = s->class & 0xff;
   2635             if ((transition_map[c/32] & (1 << (c % 32))) == 0) {
   2636                 transition_list[ctr++] = c;
   2637                 transition_map[c/32] |= (1 << (c % 32));
   2638             }
   2639         }
   2640     }
   2641     *ntr = ctr; 
   2642     return 0;
   2643 }
   2644 
   2645 static int dfa_free(re_dfa_t *l);
   2646 
   2647 static int nfa_to_dfa(re_nfa_t *nfa, re_dfa_t *pdfa, int num_classes)
   2648 {
   2649     re_dfa_state_t *d, *d1;
   2650     re_nfa_state_t *s;
   2651     int     i, k, l, c, word_size, byte_size, from = 0, rv = REGEX_ERROR_NONE, ntr, match_id;
   2652     unsigned int val;
   2653     re_nfa_list_t l1 = { 0, NULL };
   2654     re_nfa_list_t l2 = { 0, NULL };
   2655     unsigned char transition_list[REGEX_MAX_CHARACTER_CLASSES];
   2656     DECLARE_STACK(nfa_states) nfa_stk;
   2657     int running_divisor = 0;
   2658     soc_timeout_t timeout;
   2659 #if DUMP_DFA_STATE == 1
   2660     int *nlist = NULL, nc;
   2661 #endif
   2662 
   2663     mem_cou=0;
   2664     listid = 0;
   2665 
   2666     byte_size = NFA_SMAP_BYTE_SIZE(nfa);
   2667     l1.state_map = sal_alloc(byte_size, "tmp_l1");
   2668     if(!l1.state_map) {
   2669         rv = REGEX_ERROR_NO_MEMORY;
   2670         goto fail;
   2671     }
   2672     sal_memset(l1.state_map, 0, byte_size);
   2673     l2.state_map = sal_alloc(byte_size, "tmp_l2");
   2674     if(!l2.state_map) {
   2675         rv = REGEX_ERROR_NO_MEMORY;
   2676         goto fail;
   2677     }
   2678     sal_memset(l2.state_map, 0, byte_size);
   2679 #if DUMP_DFA_STATE == 1
   2680     nlist = sal_alloc((nfa->num_states * sizeof(int)), "dbg_nlist");
   2681     if (nlist == NULL) {
   2682         RE_SAL_DPRINT(("\nUnable to allocate NFA debug info for %d states\n", nfa->num_states));
   2683         rv = REGEX_ERROR_NO_MEMORY;
   2684         goto fail;
   2685     }
   2686 #endif
   2687 
   2688     STACK_INIT(&nfa_stk, NFA_STACK_SIZE, "nfa_stk");
   2689     nfa->stk = &nfa_stk;
   2690 
   2691     d = new_dfa_state(closure_0(nfa, nfa->root_state, &l1), num_classes, pdfa, nfa);
   2692     if (!d) {
   2693         rv = REGEX_ERROR_NO_MEMORY;
   2694         goto fail;
   2695     }
   2696 
   2697 #if DUMP_DFA_STATE == 1
   2698     RE_SAL_DPRINT(("\nDFA State representation of %d NFA states:\n", nfa->num_states));
   2699 #endif
   2700 
   2701     add_state_to_dfa(pdfa, d);
   2702 
   2703     while((d = get_next_unmarked_dstate(pdfa, from++))) {
   2704         get_transition_list(nfa, d, transition_list, &ntr);
   2705         for (i = 0; i < ntr; i++) {
   2706             c = transition_list[i];
   2707             d1 = next_dfa_state_on_transition(d, c, &l1, num_classes, pdfa, nfa);
   2708             if (!d1) {
   2709                 rv = REGEX_ERROR_EXPANSION_FAIL;
   2710                 goto fail;
   2711             }
   2712             /* Case of memory corruption */
   2713             if (mem_cou >= REGEX_MAX_MEM_USAGE) {  /* 100 MB */
   2714                 rv = REGEX_ERROR_EXPANSION_FAIL;
   2715                 goto fail;
   2716             }
   2717             /* Timeout is checked when there is change in the mem_cou 
   2718                to reduce the cycles. */ 
   2719             if ((running_divisor) != (mem_cou & 0xf00000)) {
   2720                 if (running_divisor == 0) {
   2721                     soc_timeout_init(&timeout, REGEX_MAX_TIMEOUT, 0);
   2722                 }
   2723                 running_divisor = mem_cou & 0xf00000;
   2724                 if (soc_timeout_check(&timeout)) {
   2725                     rv = REGEX_ERROR_EXPANSION_FAIL;
   2726                     goto fail;
   2727                 }
   2728             } 
   2729             add_state_to_dfa(pdfa, d1);
   2730             RE_CONNECT_DFA_STATES(d, d1, c);
   2731         }
   2732         RE_DFA_SET_MARKED(d, 1);
   2733     }
   2734     if((from-1) < pdfa->num_states) {
   2735         /* Case of stack corruption */
   2736         rv = REGEX_ERROR_EXPANSION_FAIL;
   2737         goto fail;
   2738     }
   2739 
   2740     /* update the final states distinctly to differentiate nfa fragments */
   2741     word_size = NFA_SMAP_WORD_SIZE(nfa);
   2742     for (i = 0; i < pdfa->num_states; i++) {
   2743         match_id = -1;
   2744 #if DUMP_DFA_STATE == 1
   2745         nc = 0;
   2746 #endif
   2747         d = pdfa->states[i];
   2748         for (k = 0; k < word_size; k++) {
   2749             if (d->l.state_map[k] == 0) {
   2750                 continue;
   2751             }
   2752             val = d->l.state_map[k];
   2753             for (l = 0; val && (l < 32); l++) {
   2754                 if ((d->l.state_map[k] & (1 << l)) == 0) {
   2755                     continue;
   2756                 }
   2757                 val &= ~(1 << l);
   2758 #if DUMP_DFA_STATE == 1
   2759                 if (nlist != NULL) {
   2760                 nlist[nc++] = (k*32)+l;
   2761                 }
   2762 #endif
   2763                 s = nfa->state_map[(k * 32) + l];
   2764                 if ((s->class >= Match) && (match_id == -1)) {
   2765                     RE_DFA_SET_FINAL(d, (s->class - Match + 1));
   2766                     match_id = RE_DFA_FINAL(d);
   2767                 }
   2768             }
   2769         }
   2770 #if DUMP_DFA_STATE == 1
   2771         if ((match_id != -1) && (nlist != NULL)) {
   2772             RE_SAL_DPRINT(("DFA FINAL State %d represents %d nfa states : matchid %d\n",
   2773                             i, nc, RE_DFA_FINAL(d)));
   2774             for (k = 0; k < nc; k++) {
   2775                 RE_SAL_DPRINT((" %d,", nlist[k]));
   2776             }
   2777             RE_SAL_DPRINT(("\n\n"));
   2778         }
   2779 #endif
   2780     }
   2781 
   2782 fail:
   2783     /* free up temp nfa stack */
   2784     STACK_DEINIT(&nfa_stk);
   2785     /* free up temp list */
   2786     if (l1.state_map != NULL) {
   2787         sal_free(l1.state_map);
   2788     }
   2789     if (l2.state_map != NULL) {
   2790         sal_free(l2.state_map);
   2791     }
   2792 #if DUMP_DFA_STATE == 1
   2793     if (nlist != NULL) {
   2794         sal_free(nlist);
   2795     }
   2796 #endif
   2797 
   2798     if (rv < 0) {
   2799         /* error, free up resources. */
   2800         dfa_free(pdfa);
   2801         pdfa = NULL;
   2802     }
   2803     return rv;
   2804 }
   2805 
   2806 #ifdef DFA_MINIMIZE
   2807 
   2808 typedef struct re_inv_dfa_s {
   2809     int *inv_delta;
   2810     int *inv_delta_set;
   2811 } re_inv_dfa_t;
   2812 
   2813 static int create_inverted_dfa(re_dfa_t *dfa, re_inv_dfa_t *idfa)
   2814 {
   2815     int n, c;
   2816     int lastDelta = 0, *inv_lists, *inv_list_last;
   2817     int s, i, j, t, go_on;
   2818     int rv = REGEX_ERROR_NONE;
   2819 
   2820     n = dfa->num_states + 1;
   2821     inv_lists = inv_list_last = NULL;
   2822 
   2823     idfa->inv_delta = sal_alloc(sizeof(int) * n*dfa->num_classes,"inv_delta");
   2824     if(!(idfa->inv_delta)) {
   2825         rv = REGEX_ERROR_NO_MEMORY;
   2826         goto fail;
   2827     }
   2828     sal_memset(idfa->inv_delta, 0, sizeof(int) * n*dfa->num_classes);
   2829     idfa->inv_delta_set = sal_alloc(sizeof(int) *2*n*dfa->num_classes,"inv_delta_set");
   2830     if(!(idfa->inv_delta_set)) {
   2831         rv = REGEX_ERROR_NO_MEMORY; 
   2832         goto fail;
   2833     }
   2834     sal_memset(idfa->inv_delta_set, 0, sizeof(int) *2*n*dfa->num_classes);
   2835 
   2836     lastDelta = 0;
   2837     inv_lists = sal_alloc(sizeof(int)*n,"inv_lists");
   2838     if(!inv_lists) {
   2839         rv = REGEX_ERROR_NO_MEMORY;
   2840         goto fail;
   2841     }
   2842     sal_memset(inv_lists, 0, sizeof(int)*n);
   2843     inv_list_last = sal_alloc(sizeof(int)*n,"inv_list_last");
   2844     if(!inv_list_last) {
   2845         rv = REGEX_ERROR_NO_MEMORY;
   2846         goto fail;
   2847     }
   2848     sal_memset(inv_list_last, 0, sizeof(int)*n);
   2849 
   2850 #if ENABLE_INVERTED_DFA_DUMP == 1
   2851     RE_SAL_DPRINT(("\nInverted DFA:\n"));
   2852 #endif
   2853     for (c = 0; c < dfa->num_classes; c++) {
   2854         for (s = 0; s < n; s++) {
   2855             inv_list_last[s] = -1;
   2856             idfa->inv_delta[(s*dfa->num_classes) + c] = -1;
   2857         }
   2858 
   2859         idfa->inv_delta[(0*dfa->num_classes)+c] = 0;
   2860         inv_list_last[0] = 0;
   2861 
   2862         for (s = 1; s < n; s++) {
   2863             t = dfa->states[s-1]->transition_list[c] + 1;
   2864 
   2865             if (inv_list_last[t] == -1) {
   2866 #if ENABLE_INVERTED_DFA_DUMP == 1
   2867                 RE_SAL_DPRINT(("  Class %3d, state %3d, transition %3d, inv_delta[%3d]: %3d\n",
   2868                                c, s, t-1, (t*dfa->num_classes)+c, s));
   2869 #endif
   2870                 idfa->inv_delta[(t*dfa->num_classes) + c] = s;
   2871                 inv_list_last[t] = s;
   2872             }
   2873             else {
   2874                 inv_lists[inv_list_last[t]] = s;
   2875                 inv_list_last[t] = s; 
   2876             }
   2877         }
   2878 
   2879         for (s = 0; s < n; s++) {
   2880             i = idfa->inv_delta[(s*dfa->num_classes) + c];
   2881             idfa->inv_delta[(s*dfa->num_classes) + c] = lastDelta;
   2882 #if ENABLE_INVERTED_DFA_DUMP == 1
   2883                 RE_SAL_DPRINT(("  Class %3d, state %3d, inv_delta[%3d]: %3d\n",
   2884                                c, s, (s*dfa->num_classes)+c, lastDelta));
   2885 #endif
   2886             j = inv_list_last[s];
   2887             go_on = (i != -1);
   2888             while (go_on) {
   2889                 go_on = (i != j);
   2890 #if ENABLE_INVERTED_DFA_DUMP == 1
   2891                 RE_SAL_DPRINT(("  Class %3d, state %3d, inv_delta_set[%3d]: %3d\n",
   2892                                c, s, lastDelta, i));
   2893 #endif
   2894                 idfa->inv_delta_set[lastDelta++] = i;
   2895                 i = inv_lists[i];
   2896             }
   2897             idfa->inv_delta_set[lastDelta++] = -1;
   2898         }
   2899     }
   2900  
   2901 fail:
   2902     if(inv_lists)
   2903         sal_free(inv_lists);
   2904     if(inv_list_last) 
   2905         sal_free(inv_list_last);
   2906 	/* idfa freed in calling func*/ 
   2907     return rv;
   2908 }
   2909 
   2910 static void free_inverted_dfa(re_inv_dfa_t *idfa)
   2911 {
   2912     if (idfa->inv_delta) {
   2913         sal_free(idfa->inv_delta);
   2914         idfa->inv_delta = NULL;
   2915     }
   2916     if (idfa->inv_delta_set) {
   2917         sal_free(idfa->inv_delta_set);
   2918         idfa->inv_delta_set = NULL;
   2919     }
   2920 }
   2921 
   2922 typedef struct re_dm_block_cb_s {
   2923     int *block;
   2924     int *b_forward;
   2925     int *b_backward;
   2926     int num_block;
   2927     int b0_off;
   2928     int b_max;
   2929 } re_dm_block_cb_t;
   2930 
   2931 static int create_block_list(re_dfa_t *l, re_inv_dfa_t *idfa,
   2932                              re_dm_block_cb_t *bcb)
   2933 {
   2934     int n = l->num_states + 1, s, found, t, last, b_i;
   2935 
   2936     bcb->block = sal_alloc(sizeof(int)*2*n,"blklist");
   2937     if (bcb->block == NULL) {
   2938         goto fail;
   2939     }
   2940     sal_memset(bcb->block, 0, sizeof(int)*2*n);
   2941     bcb->b_forward = sal_alloc(sizeof(int)*2*n,"bbfwd");
   2942     if (bcb->b_forward == NULL) {
   2943         goto fail;
   2944     }
   2945     sal_memset(bcb->b_forward, 0, sizeof(int)*2*n);
   2946     bcb->b_backward = sal_alloc(sizeof(int)*2*n,"bbbwd");
   2947     if (bcb->b_backward == NULL) {
   2948         goto fail;
   2949     }
   2950     sal_memset(bcb->b_backward, 0, sizeof(int)*2*n);
   2951 
   2952     bcb->num_block = n;
   2953     bcb->b0_off = n; 
   2954 
   2955     bcb->b_forward[bcb->b0_off]  = 0;
   2956     bcb->b_backward[bcb->b0_off] = 0;          
   2957     bcb->b_forward[0]   = bcb->b0_off;
   2958     bcb->b_backward[0]  = bcb->b0_off;
   2959     bcb->block[0]  = bcb->b0_off;
   2960     bcb->block[bcb->b0_off] = 1;
   2961 
   2962     for (s = 1; s < n; s++) {
   2963         int b = bcb->b0_off+1;
   2964         found = 0;
   2965         while (!found && b <= bcb->num_block) {
   2966             t = bcb->b_forward[b];
   2967 
   2968             if (RE_DFA_IS_FINAL(l->states[s-1])) {
   2969                 found = RE_DFA_IS_FINAL(l->states[t-1]) &&
   2970                     (RE_DFA_FINAL(l->states[s-1]) == RE_DFA_FINAL(l->states[t-1]));
   2971             }
   2972             else {
   2973                 found = !RE_DFA_IS_FINAL(l->states[t-1]);
   2974             }
   2975 
   2976             if (found) {
   2977                 bcb->block[s] = b;
   2978                 bcb->block[b]++;
   2979 
   2980                 last = bcb->b_backward[b];
   2981                 bcb->b_forward[last] = s;
   2982                 bcb->b_forward[s] = b;
   2983 
   2984                 bcb->b_backward[b] = s;
   2985                 bcb->b_backward[s] = last;
   2986             }
   2987 
   2988             b++;
   2989         }
   2990 
   2991         if (!found) {
   2992             bcb->block[s] = b;
   2993             bcb->block[b]++;
   2994 
   2995             bcb->b_forward[b] = s;
   2996             bcb->b_forward[s] = b;
   2997             bcb->b_backward[b] = s;
   2998             bcb->b_backward[s] = b;
   2999 
   3000             bcb->num_block++;
   3001         }
   3002     } 
   3003 
   3004     bcb->b_max = bcb->b0_off;
   3005     for (b_i = bcb->b0_off+1; b_i <= bcb->num_block; b_i++) {
   3006         if (bcb->block[bcb->b_max] < bcb->block[b_i]) {
   3007             bcb->b_max = b_i;
   3008         }
   3009     }
   3010     return REGEX_ERROR_NONE;
   3011 fail:
   3012     /* All free at calling func */
   3013     return REGEX_ERROR_NO_MEMORY; 
   3014 }
   3015 
   3016 static void free_dm_block(re_dm_block_cb_t *bcb)
   3017 {
   3018     if (bcb->block) {
   3019         sal_free(bcb->block);
   3020         bcb->block = NULL;
   3021     }
   3022     if (bcb->b_forward) {
   3023         sal_free(bcb->b_forward);
   3024         bcb->b_forward = NULL;
   3025     }
   3026     if (bcb->b_backward) {
   3027         sal_free(bcb->b_backward);
   3028         bcb->b_backward = NULL;
   3029     }
   3030 }
   3031 
   3032 static re_dfa_t * dfa_minimize(re_dfa_t *dfa_list)
   3033 {
   3034     int numStates = dfa_list->num_states, n, c;
   3035     re_dm_block_cb_t bcb;
   3036     int *l_forward, *l_backward, anchorL;
   3037     re_inv_dfa_t idfa;
   3038     int numSplit, *twin, *vsd, *vd, numd;
   3039     int s, i, j, t, last, blk_i;
   3040     int index, indexD, indexTwin, b;
   3041     int *trans, *move, amount, size;
   3042     unsigned int *kill;
   3043     int B_j, a, min_s;
   3044 
   3045     if (dfa_list->num_states == 0) {
   3046         return dfa_list;
   3047     }
   3048 
   3049 #ifndef SEARCH_FOR_MORE_MATCHES_AFTER_MATCH
   3050     /*
   3051     Eliminate transitions from final states before inverting
   3052     the DFA. (Such states can arise when there are regexes
   3053     with wildcards/ranges.)  This code assumes that only the
   3054     first match is necessary -- there will be no further
   3055     searches for "greedy" regexes/matches.  Once one of the
   3056     regexes is a match, the match ID will be returned.  For
   3057     non-anchored regexes, this can save considerable state
   3058     space. Also, all the transitions from final states are
   3059     not actually installed in the hardware anyway - what
   3060     actually gets installed are jump to idle transitions.
   3061     This code eliminates not only those extra transitions,
   3062     but also results in eliminating any states that become
   3063     non-reachable as a result of removing transitions from
   3064     final states, as those states will then be removed when
   3065     minimizing the DFA.
   3066     */
   3067 
   3068     for (i = 0; i < numStates; i++) {
   3069         if (RE_DFA_FINAL(dfa_list->states[i])) {
   3070             for (c = 0; c < dfa_list->num_classes; c++) {
   3071                 dfa_list->states[i]->transition_list[c] = -1;
   3072             }
   3073     }
   3074     }
   3075 #endif
   3076     l_forward = l_backward = twin = vsd = vd = trans = move = NULL;
   3077     kill = NULL;
   3078     n = numStates+1;
   3079 
   3080     sal_memset(&idfa, 0, sizeof(re_inv_dfa_t));
   3081     sal_memset(&bcb, 0, sizeof(re_dm_block_cb_t));
   3082     if (create_inverted_dfa(dfa_list, &idfa)) {
   3083         goto fail;
   3084     }
   3085 
   3086     /* create blocks */
   3087     if (create_block_list(dfa_list, &idfa, &bcb)) {
   3088         goto fail;
   3089     }
   3090 
   3091     l_forward = sal_alloc(sizeof(int)*((n*dfa_list->num_classes)+1),"lfwd");
   3092     if(!l_forward) {
   3093         goto fail;
   3094     }
   3095     sal_memset(l_forward, 0, sizeof(int)*((n*dfa_list->num_classes)+1));
   3096     l_backward = sal_alloc(sizeof(int)*((n*dfa_list->num_classes)+1),"lbwd");
   3097     if(!l_backward) {
   3098         goto fail;
   3099     }
   3100     sal_memset(l_backward, 0, sizeof(int)*((n*dfa_list->num_classes)+1));
   3101 
   3102     anchorL = n*dfa_list->num_classes;
   3103 
   3104     l_forward[anchorL] = anchorL;
   3105     l_backward[anchorL] = anchorL;
   3106 
   3107     blk_i = (bcb.b_max == bcb.b0_off) ? bcb.b0_off+1 : bcb.b0_off;
   3108 
   3109     index = (blk_i - bcb.b0_off)*dfa_list->num_classes;
   3110     while (index < (blk_i + 1 - bcb.b0_off)*dfa_list->num_classes) {
   3111         last = l_backward[anchorL];
   3112         l_forward[last]     = index;
   3113         l_forward[index]    = anchorL;
   3114         l_backward[index]   = last;
   3115         l_backward[anchorL] = index;
   3116         index++;
   3117     }
   3118 
   3119     while (blk_i <= bcb.num_block) {
   3120         if (blk_i != bcb.b_max) {
   3121             index = (blk_i - bcb.b0_off)*dfa_list->num_classes;
   3122             while (index < (blk_i + 1 - bcb.b0_off)*dfa_list->num_classes) {
   3123                 last = l_backward[anchorL];
   3124                 l_forward[last]     = index;
   3125                 l_forward[index]    = anchorL;
   3126                 l_backward[index]   = last;
   3127                 l_backward[anchorL] = index;
   3128                 index++;
   3129             }
   3130         }
   3131         blk_i++;
   3132     } 
   3133 
   3134     twin = sal_alloc(sizeof(int)*2*n,"twin");
   3135     if(!twin){
   3136         goto fail;
   3137     }
   3138     sal_memset(twin, 0, sizeof(int)*2*n);
   3139     vsd = sal_alloc(sizeof(int)*2*n,"vsd");
   3140     if(!vsd) {
   3141         goto fail;
   3142     }
   3143     sal_memset(vsd, 0, sizeof(int)*2*n);
   3144     vd = sal_alloc(sizeof(int)*n,"vd");
   3145     if(!vd) {
   3146         goto fail;
   3147     }
   3148     sal_memset(vd, 0, sizeof(int)*n);
   3149 
   3150     while (l_forward[anchorL] != anchorL) {
   3151         int B_j_a = l_forward[anchorL];      
   3152         l_forward[anchorL] = l_forward[B_j_a];
   3153         l_backward[l_forward[anchorL]] = anchorL;
   3154         l_forward[B_j_a] = 0;
   3155         B_j = bcb.b0_off + B_j_a / dfa_list->num_classes;
   3156         a   = B_j_a % dfa_list->num_classes;
   3157 
   3158         numd = 0;
   3159         s = bcb.b_forward[B_j];
   3160         while (s != B_j) {
   3161             t = idfa.inv_delta[(s*dfa_list->num_classes) + a];
   3162             while (idfa.inv_delta_set[t] != -1) {
   3163                 vd[numd++] = idfa.inv_delta_set[t++];
   3164             }
   3165             s = bcb.b_forward[s];
   3166         }      
   3167 
   3168         numSplit = 0;
   3169 
   3170         for (indexD = 0; indexD < numd; indexD++) {
   3171             s = vd[indexD];
   3172             blk_i = bcb.block[s];
   3173             vsd[blk_i] = -1; 
   3174             twin[blk_i] = 0;
   3175         }
   3176 
   3177         for (indexD = 0; indexD < numd; indexD++) {
   3178             s = vd[indexD];
   3179             blk_i = bcb.block[s];
   3180 
   3181             if (vsd[blk_i] < 0) {
   3182                 vsd[blk_i] = 0;
   3183                 t = bcb.b_forward[blk_i];
   3184                 while (t != blk_i && (t != 0 || bcb.block[0] == B_j) && 
   3185                        (t == 0 || bcb.block[dfa_list->states[t-1]->transition_list[a]+1] == B_j)) {
   3186                     vsd[blk_i]++;
   3187                     t = bcb.b_forward[t];
   3188                 }
   3189             }
   3190         }
   3191 
   3192         for (indexD = 0; indexD < numd; indexD++) {
   3193             s = vd[indexD];
   3194             blk_i = bcb.block[s];
   3195 
   3196             if (vsd[blk_i] != bcb.block[blk_i]) {
   3197                 int B_k = twin[blk_i];
   3198                 if (B_k == 0) { 
   3199                     B_k = ++bcb.num_block;
   3200                     bcb.b_forward[B_k] = B_k;
   3201                     bcb.b_backward[B_k] = B_k;
   3202 
   3203                     twin[blk_i] = B_k;
   3204 
   3205                     twin[numSplit++] = blk_i;
   3206                 }
   3207 
   3208                 bcb.b_forward[bcb.b_backward[s]] = bcb.b_forward[s];
   3209                 bcb.b_backward[bcb.b_forward[s]] = bcb.b_backward[s];
   3210 
   3211                 last = bcb.b_backward[B_k];
   3212                 bcb.b_forward[last] = s;
   3213                 bcb.b_forward[s] = B_k;
   3214                 bcb.b_backward[s] = last;
   3215                 bcb.b_backward[B_k] = s;
   3216 
   3217                 bcb.block[s] = B_k;
   3218                 bcb.block[B_k]++;
   3219                 bcb.block[blk_i]--;
   3220 
   3221                 vsd[blk_i]--; 
   3222             }
   3223         } 
   3224 
   3225         for (indexTwin = 0; indexTwin < numSplit; indexTwin++) {
   3226             int blk_i = twin[indexTwin];
   3227             int B_k = twin[blk_i];
   3228             for (c = 0; c < dfa_list->num_classes; c++) {
   3229                 int B_i_c = (blk_i-bcb.b0_off)*dfa_list->num_classes+c;
   3230                 int B_k_c = (B_k-bcb.b0_off)*dfa_list->num_classes+c;
   3231                 if (l_forward[B_i_c] > 0) {
   3232                     last = l_backward[anchorL];
   3233                     l_backward[anchorL] = B_k_c;
   3234                     l_forward[last] = B_k_c;
   3235                     l_backward[B_k_c] = last;
   3236                     l_forward[B_k_c] = anchorL;
   3237                 }
   3238                 else {
   3239                     if (bcb.block[blk_i] <= bcb.block[B_k]) {
   3240                         last = l_backward[anchorL];
   3241                         l_backward[anchorL] = B_i_c;
   3242                         l_forward[last] = B_i_c;
   3243                         l_backward[B_i_c] = last;
   3244                         l_forward[B_i_c] = anchorL;              
   3245                     }
   3246                     else {
   3247                         last = l_backward[anchorL];
   3248                         l_backward[anchorL] = B_k_c;
   3249                         l_forward[last] = B_k_c;
   3250                         l_backward[B_k_c] = last;
   3251                         l_forward[B_k_c] = anchorL;              
   3252                     }
   3253                 }
   3254             }
   3255         }
   3256     }
   3257 
   3258     free_inverted_dfa(&idfa);
   3259     sal_free(twin);
   3260     sal_free(vsd);
   3261     sal_free(vd);
   3262     twin = vsd = vd = NULL;
   3263 
   3264     trans = sal_alloc(sizeof(int)*numStates,"trans");
   3265     if(!trans) {
   3266         goto fail;
   3267     }
   3268     sal_memset(trans, 0, sizeof(int)*numStates);
   3269 
   3270     size = ((numStates+31)/32)*sizeof(unsigned int);
   3271     kill = sal_alloc(size,"kill");
   3272     if(!kill) {
   3273         goto fail;
   3274     }
   3275     sal_memset(kill, 0, size);
   3276 
   3277     move = sal_alloc(sizeof(int)*numStates,"move");
   3278     if(!move) {
   3279         goto fail;
   3280     }
   3281     sal_memset(move, 0, sizeof(int)*numStates);
   3282 
   3283     for (b = bcb.b0_off+1; b <= bcb.num_block; b++) {
   3284         s = bcb.b_forward[b];
   3285         min_s = s;
   3286         for (; s != b; s = bcb.b_forward[s]) {
   3287             if (min_s > s) {
   3288                 min_s = s;
   3289             }
   3290         }
   3291         min_s--; 
   3292         for (s = bcb.b_forward[b]-1; s != b-1; s = bcb.b_forward[s+1]-1) {
   3293             trans[s] = min_s;
   3294             kill[s/32] |= (s != min_s) ? (1 << (s % 32)) : 0 ;
   3295         }
   3296     }
   3297 
   3298     free_dm_block(&bcb);
   3299     
   3300     sal_free(l_forward);
   3301     sal_free(l_backward);
   3302     l_forward = l_backward = NULL;
   3303 
   3304     amount = 0;
   3305     size = ((numStates+31)/32)*sizeof(unsigned int);
   3306     for (i = 0; i < numStates; i++) {
   3307         if (kill[i/32] & (1 << (i%32))) {
   3308             amount++;
   3309         } else {
   3310             move[i] = amount;
   3311         }
   3312     }
   3313 
   3314     for (i = 0, j = 0; i < numStates; i++) {
   3315         if ((kill[i/32] & (1 << (i % 32))) == 0) {
   3316             for (c = 0; c < dfa_list->num_classes; c++) {
   3317                 if ( dfa_list->states[i]->transition_list[c] >= 0 ) {
   3318                     dfa_list->states[j]->transition_list[c]  = trans[ dfa_list->states[i]->transition_list[c] ];
   3319                     dfa_list->states[j]->transition_list[c] -= move[ dfa_list->states[j]->transition_list[c] ];
   3320                 }
   3321                 else {
   3322                     dfa_list->states[j]->transition_list[c] = dfa_list->states[i]->transition_list[c];
   3323                 }
   3324             }
   3325 
   3326             RE_DFA_SET_FINAL(dfa_list->states[j], RE_DFA_FINAL(dfa_list->states[i]));
   3327             j++;
   3328         }
   3329     }
   3330     numStates = j;
   3331 
   3332     sal_free(trans);
   3333     sal_free(kill);
   3334     sal_free(move);
   3335     trans = move = NULL;
   3336     kill = NULL;
   3337     /* free up unused states */
   3338     if (j % DFA_BLOCK_SIZE) {
   3339         j += DFA_BLOCK_SIZE - (j % DFA_BLOCK_SIZE);
   3340     }
   3341 
   3342     /*
   3343     Note, this unusual loop and free is because of the way
   3344     the transition list is allocated in blocks of
   3345     DFA_BLOCK_SIZE.
   3346     */
   3347 
   3348     for (; j < dfa_list->num_states; j += DFA_BLOCK_SIZE) {
   3349         sal_free(dfa_list->states[j]->transition_list);
   3350         sal_free(dfa_list->states[j]);
   3351     }
   3352 
   3353     dfa_list->num_states = numStates;
   3354     return dfa_list;
   3355 
   3356 fail:
   3357     free_inverted_dfa(&idfa);
   3358     free_dm_block(&bcb);
   3359     dfa_free(dfa_list);
   3360     if(l_forward) {
   3361         sal_free(l_forward); 
   3362     }
   3363     if(l_backward) {
   3364         sal_free(l_backward); 
   3365     }
   3366     if(twin) {
   3367         sal_free(twin); 
   3368     }
   3369     if(vsd) {
   3370         sal_free(vsd); 
   3371     }
   3372     if(vd) {
   3373         sal_free(vd); 
   3374     }
   3375     if(trans) {
   3376         sal_free(trans); 
   3377     }
   3378     if(move) {
   3379         sal_free(move); 
   3380     }
   3381     if(kill) {
   3382         sal_free(kill); 
   3383     }
   3384 
   3385     return NULL;
   3386 }
   3387 
   3388 #endif /* DFA_MINIMIZE */
   3389 
   3390 #if ENABLE_NFA_DUMP == 1
   3391 static void dump_nfa(re_nfa_t *nfa, re_nfa_state_t *root)
   3392 {
   3393     int i;
   3394     re_nfa_state_t *s;
   3395 
   3396     RE_SAL_DPRINT(("Entry state is : %d\n", root->id));
   3397     for (i=0; i<nfa->num_states; i++) {
   3398         s = nfa->state_map[i];
   3399         if (s->class >= Match) {
   3400             RE_SAL_DPRINT(("State [FINAL match %d] %d:\n", (s->class - Match), s->id));
   3401         } else {
   3402             RE_SAL_DPRINT(("State %d:\n", s->id));
   3403         }
   3404         if (s->class == Split) {
   3405             RE_SAL_DPRINT(("\t With epsilon to out  %3d\n", s->out->id));
   3406             RE_SAL_DPRINT(("\t With epsilon to out1 %3d\n", s->out1->id));
   3407         } else {
   3408             if (s->out) {
   3409                 RE_SAL_DPRINT(("\tWith input %3d to out  %3d\n", s->class, s->out->id));
   3410             }
   3411             if (s->out1) {
   3412                 RE_SAL_DPRINT(("\tWith input %3d to out1 %3d\n", s->class, s->out1->id));
   3413             }
   3414         }
   3415     }
   3416 }
   3417 #endif
   3418 
   3419 /*
   3420  * Create a single NFA corresponding to all the patterns.
   3421  * The function does the following:
   3422  *      - convert each pattern to class representation
   3423  *      - preprocess the pattern and expand it for example
   3424  *          \d is expanded to (0|1|2|..|8|9) etc.
   3425  *      - convert the pattern to postfix represetation. Note 
   3426  *          the postfix representation is not string but utilizes 2bytes
   3427  *          to represent the character since the pattern might have \0 in
   3428  *          between which would terminate the string.
   3429  *      - postfix representation of the pattern is then converted to NFA.
   3430  *      - All the NFA are joined together using Split (epsilon transition.)
   3431  *      - If all goes well, the final NFA is returned back to caller.
   3432  */
   3433 static int make_nfa(char **re, unsigned int *res_flags, 
   3434                     int num_pattern, re_nfa_t **ppnfa,
   3435                     re_transition_class *pclass_array, int num_classes)
   3436 {
   3437     re_wc *post;
   3438     re_nfa_state_t **sub_nfa = NULL, *n1, *n2, *s;
   3439     re_nfa_t *pnfa;
   3440     int     pattern;
   3441     re_wc   *re1, *re2;
   3442     int     rv = REGEX_ERROR_NONE, i;
   3443 
   3444     pnfa = sal_alloc(sizeof(*pnfa), "NFA");
   3445     if(!pnfa) {
   3446         rv = REGEX_ERROR_NO_MEMORY;
   3447         goto fail;
   3448     }
   3449     sal_memset(pnfa, 0, sizeof(*pnfa));
   3450 
   3451     /* 
   3452      * array to store the individual NFA strands till they are all
   3453      * combined into single final NFA.
   3454      */
   3455     sub_nfa = sal_alloc(sizeof(sub_nfa[0]) * num_pattern, "sub_nfa");
   3456     if (sub_nfa == NULL) {
   3457         rv = REGEX_ERROR_NO_MEMORY;
   3458         goto fail;
   3459     }
   3460 
   3461     for (pattern=0; pattern < num_pattern; pattern++) {
   3462         re1 = re_convert_tokens_to_class(re[pattern], 
   3463                                          res_flags ? res_flags[pattern] : 0,
   3464                                          pclass_array, num_classes);
   3465         if (!re1) {
   3466             rv = REGEX_ERROR_EXPANSION_FAIL;
   3467             RE_SAL_DPRINT(("\n-------Error %d converting tokens\n\n", rv));
   3468             goto fail;
   3469         }
   3470         re2 = re_preprocess(re1);
   3471         sal_free(re1);
   3472         if (!re2) {
   3473             rv = REGEX_ERROR_EXPANSION_FAIL;
   3474             RE_SAL_DPRINT(("\n-------Error %d re_preprocess\n\n", rv));
   3475             goto fail;
   3476         }
   3477 
   3478         post = re2post(re2);
   3479         sal_free(re2);
   3480         if (!post) {
   3481             rv = REGEX_ERROR_NO_POST;
   3482             RE_SAL_DPRINT(("\n-------Error %d re2post\n\n", rv));
   3483             goto fail;
   3484         }
   3485         sub_nfa[pattern] = post2nfa(pnfa, post, pattern);
   3486         sal_free(post);
   3487         if (sub_nfa[pattern] == NULL) {
   3488             rv = REGEX_ERROR_EXPANSION_FAIL;
   3489             RE_SAL_DPRINT(("\n-------Error %d post2nfa\n\n", rv));
   3490             goto fail;
   3491         }
   3492 #if ENABLE_NFA_DUMP == 1
   3493         RE_SAL_DPRINT(("\n-------NFA for %s\n\n", re[pattern]));
   3494         dump_nfa(pnfa, sub_nfa[pattern]);
   3495 #endif
   3496     }
   3497 
   3498     if (num_pattern == 1) {
   3499         pnfa->root_state = sub_nfa[0];
   3500     } else {
   3501         for (pattern = 0; pattern < num_pattern - 1; pattern++) {
   3502             n1 = sub_nfa[pattern];
   3503             n2 = sub_nfa[pattern+1];
   3504             sub_nfa[pattern+1] = new_nfa_state(pnfa, Split, n1, n2);
   3505         }
   3506         pnfa->root_state = sub_nfa[pattern];
   3507     }
   3508 
   3509 #if ENABLE_NFA_DUMP == 1
   3510     RE_SAL_DPRINT(("--------\n\n\n--- Final NFA ---\n\n"));
   3511     dump_nfa(pnfa, pnfa->root_state);
   3512 #endif
   3513 
   3514     /* 
   3515      * store the byte size required to represent all the states in NFA. 
   3516      * The reason to store it, the information is required in dfa 
   3517      * computation and required like millions of times, this just 
   3518      * optimizes computation a bit.
   3519      */
   3520     pnfa->state_map_byte_size = ((pnfa->num_states + 31) / 32) * sizeof(unsigned int);
   3521     state_map_byte_size = pnfa->state_map_byte_size;
   3522 
   3523     /*
   3524      * create a class map bitvector. This optimizes traversing the
   3525      * NFA of specified transation.
   3526      */
   3527     for (i = 0; i < num_classes; i++) {
   3528         pnfa->class_map[i] = sal_alloc(NFA_SMAP_BYTE_SIZE(pnfa), "nfa_class_map");
   3529         if(!(pnfa->class_map[i])) {
   3530             rv = REGEX_ERROR_NO_MEMORY;
   3531             goto fail;
   3532         }
   3533         sal_memset(pnfa->class_map[i], 0, NFA_SMAP_BYTE_SIZE(pnfa));
   3534     }
   3535 
   3536     for (i = 0; i < pnfa->num_states; i++) {
   3537         s = pnfa->state_map[i];
   3538         if (s->class > 255) {
   3539             continue;
   3540         }
   3541         if (s->class >= num_classes) {
   3542             rv = REGEX_ERROR_EXPANSION_FAIL;
   3543             RE_SAL_DPRINT(("\n-------Error %d too many classes\n\n", rv));
   3544             goto fail;
   3545         }
   3546         pnfa->class_map[s->class][s->id / 32] |= (1 << (s->id % 32));
   3547     }
   3548 
   3549 fail:
   3550     /* free sub NFA */
   3551     if (rv) {
   3552         RE_SAL_DPRINT(("\n-------Error %d creating NFA\n\n", rv));
   3553         nfa_free(pnfa);
   3554         pnfa = NULL;
   3555     }
   3556     if(sub_nfa) {
   3557         sal_free(sub_nfa);
   3558     }
   3559     *ppnfa = pnfa;
   3560     return rv;
   3561 }
   3562 
   3563 #if ENABLE_FINAL_DFA_DUMP == 1
   3564 regex_cb_error_t 
   3565 bcm_regex_dfa_dump(unsigned int flags, int match_idx, int in_state, 
   3566                            int from_c, int to_c, int to_state, 
   3567                            int num_dfa_state, void *user_data)
   3568 {
   3569     static int last_state = -1;
   3570     static int numFinal = 0;
   3571 
   3572     if (flags & DFA_TRAVERSE_START) {
   3573         last_state = -1;
   3574         numFinal = 0;
   3575         return REGEX_CB_OK;
   3576     }
   3577 
   3578     if (flags & DFA_TRAVERSE_END) {
   3579         RE_SAL_DPRINT(("\nNum FINAL states %d\n", numFinal));
   3580         return REGEX_CB_OK;
   3581     }
   3582 
   3583     /* if last state is not same as this state, insert goto IDLE state */
   3584     if (last_state != in_state) {
   3585         if (flags & DFA_STATE_FINAL) {
   3586             numFinal++;
   3587             RE_SAL_DPRINT(("\nState %d [FINAL]: Match ID %d\n",
   3588                             in_state, match_idx));
   3589         } else {
   3590             RE_SAL_DPRINT(("\nState %d:\n", in_state));
   3591         }
   3592         last_state = in_state;
   3593     }
   3594 
   3595     if ((from_c == -1) || (to_c == -1)) {
   3596         return 0;
   3597     }
   3598 
   3599     RE_SAL_DPRINT(("   %4d -> %4d ", in_state, to_state));
   3600     RE_SAL_DPRINT(("["));
   3601     RE_SAL_DPRINT(("\\%-3d", from_c));
   3602     RE_SAL_DPRINT(("-"));
   3603     RE_SAL_DPRINT(("\\%-3d", to_c));
   3604     RE_SAL_DPRINT(("]"));
   3605     if (printable(from_c) && printable(to_c)) {
   3606         RE_SAL_DPRINT((" (%2c-%-2c)", from_c, to_c));
   3607     } else if (printable(from_c)) {
   3608         RE_SAL_DPRINT((" (%2c-'')", from_c));
   3609     } else if (printable(to_c)) {
   3610         RE_SAL_DPRINT((" (''-%-2c)", to_c));
   3611     }
   3612     RE_SAL_DPRINT((";\n"));
   3613     return REGEX_CB_OK;
   3614 }
   3615 #endif
   3616 
   3617 static int dfa_free(re_dfa_t *l)
   3618 {
   3619     int i;
   3620 
   3621     if (!l) {
   3622         return 0;
   3623     }
   3624 
   3625     for (i = 0; i < l->num_states; i+= DFA_BLOCK_SIZE) {
   3626         sal_free(l->states[i]->transition_list);
   3627         sal_free(l->states[i]);
   3628     }
   3629 
   3630     sal_free(l->states);
   3631 
   3632     if (l->class_array) {
   3633         sal_free(l->class_array);
   3634     }
   3635 
   3636     _free_buf_blocks(l->nbuf);
   3637     _free_buf_blocks(l->avbuf);
   3638     
   3639     sal_free(l);
   3640     return 0;
   3641 }
   3642 
   3643 static int
   3644 make_dfa(int num_pattern, re_dfa_t **ppdfa, re_nfa_t **ppnfa, re_transition_class *class_array,
   3645          int num_classes)
   3646 {
   3647     re_dfa_t  *pdfa;
   3648     re_nfa_t  *pnfa = *ppnfa;
   3649     int rv = 0;
   3650 
   3651     pdfa = sal_alloc(sizeof(*pdfa), "DFA");
   3652     sal_memset(pdfa, 0, sizeof(*pdfa));
   3653     pdfa->size = 0;
   3654     pdfa->states = NULL;
   3655     pdfa->num_states = 0;
   3656     pdfa->class_array = class_array;
   3657     pdfa->num_classes = num_classes;
   3658 
   3659     rv = nfa_to_dfa(pnfa, pdfa, num_classes);
   3660     /* free up NFA, check rv after it */
   3661     nfa_free(pnfa);
   3662     *ppnfa = NULL;
   3663     
   3664     if (rv) {
   3665         /* pdfa freed inside nfa_to_dfa */
   3666         rv = REGEX_ERROR_NO_DFA;
   3667         goto fail;
   3668     }
   3669 
   3670 #if ENABLE_DFA_DUMP_BEFORE_MINIMIZATION == 1
   3671     RE_SAL_DPRINT(("\nTotal of %d DFA states before minimization\n", pdfa->num_states));
   3672     RE_SAL_DPRINT(("\nTotal of %d char classes before minimization\n\n", pdfa->num_classes));
   3673     if (bcm_regex_dfa_traverse(pdfa, bcm_regex_dfa_dump, NULL)) {
   3674         return -1;
   3675     }
   3676     RE_SAL_DPRINT(("-----------------------------------\n\n\n"));
   3677 #endif
   3678 
   3679 #if DFA_MINIMIZE == 1
   3680     RE_SAL_DPRINT(("\nMinimizing %d DFA states\n", pdfa->num_states));
   3681     pdfa = dfa_minimize(pdfa);
   3682     if (!pdfa) {
   3683         rv = REGEX_ERROR_NO_DFA;
   3684         goto fail;
   3685     }
   3686     RE_SAL_DPRINT(("-----------------------------------\n\n\n"));
   3687 
   3688 #if ENABLE_FINAL_DFA_DUMP == 1
   3689     RE_SAL_DPRINT(("\nTotal of %d DFA states after minimization\n", pdfa->num_states));
   3690     RE_SAL_DPRINT(("\nTotal of %d char classes after minimization\n\n", pdfa->num_classes));
   3691     RE_SAL_DPRINT(("Minimal DFA is\n"));
   3692     if (bcm_regex_dfa_traverse(pdfa, bcm_regex_dfa_dump, NULL)) {
   3693         return -1;
   3694     }
   3695 #endif
   3696 #endif
   3697     *ppdfa = pdfa;
   3698     return rv;
   3699 fail:
   3700     *ppdfa = NULL;
   3701     
   3702     return rv;
   3703 }
   3704 
   3705 static int nfa_free(re_nfa_t *nfa)
   3706 {
   3707     int i;
   3708 
   3709     if (nfa == NULL) {
   3710         return 0;
   3711     }
   3712 
   3713     for (i = 0; i < COUNTOF(nfa->class_map); i++) {
   3714         if (nfa->class_map[i]) {
   3715             sal_free(nfa->class_map[i]);
   3716             nfa->class_map[i] = NULL;
   3717         }
   3718     }
   3719 
   3720     if (nfa->state_map) {
   3721         sal_free(nfa->state_map);
   3722         nfa->state_map = NULL;
   3723     }
   3724   
   3725     _free_buf_blocks(nfa->nbuf);
   3726     nfa->nbuf = NULL;
   3727     sal_free(nfa);
   3728     nfa = NULL;
   3729     return 0;
   3730 }
   3731 
   3732 /*
   3733  * Compiles the set of patterns into a single DFA. If the ppdfa is
   3734  * not NULL, computed DFA is not freed and is preserved so that
   3735  * user/application can inspect the DFA, ie for the API layer to
   3736  * transform the DFA to device specific HW representation of the DFA.
   3737  *
   3738  * Note: This function is not reentrant.
   3739  */
   3740 int
   3741 bcm_regex_compile(char **re, unsigned int *res_flags, int num_pattern,
   3742                   unsigned int cflags, void** ppdfa)
   3743 {
   3744     int rv = REGEX_ERROR_NONE, num_classes = 0, p, ptlen;
   3745     re_dfa_t *pdfa = NULL;
   3746     re_transition_class *class_array = NULL;
   3747     re_nfa_t *pnfa = NULL;
   3748     char **nre;
   3749 
   3750     *ppdfa = NULL;
   3751 
   3752     listid = 0;
   3753     state_id = 0;
   3754 
   3755     if (num_pattern <= 0) {
   3756         return 0;
   3757     }
   3758 
   3759     nre = sal_alloc(sizeof(char*)*num_pattern,"tmp_re");
   3760     if (nre == NULL) {
   3761         return REGEX_ERROR_NO_MEMORY;
   3762     }
   3763     sal_memset(nre, 0, sizeof(char*)*num_pattern);
   3764     
   3765     for(p=0; p<num_pattern; p++) {
   3766         if (re[p] == NULL) {
   3767             continue;
   3768         }
   3769         /* If the re begins with the start anchor metacharacter, ignore that character and
   3770          * set the flag which indicates this regex is anchored at the start of the
   3771          * packet. */
   3772         if (START_ANCHOR_CHAR == re[p][0]) {
   3773             if (sal_strlen(re[p]) <= 1) {
   3774                 continue;
   3775             }
   3776             nre[p] = sal_strdup(&re[p][1]);
   3777             res_flags[p] |= BCM_TR3_REGEX_CFLAG_ANCHORED;
   3778         } else {
   3779         nre[p] = sal_strdup(re[p]);
   3780         }
   3781         if (NULL == nre[p]) {
   3782             rv = REGEX_ERROR_NO_MEMORY;
   3783             goto fail;
   3784         }
   3785         ptlen = sal_strlen(nre[p]);
   3786         if ((nre[p][ptlen - 1] == '$') && 
   3787             ((ptlen > 1) ? (nre[p][ptlen - 2] != '\\') :  1)) {
   3788             nre[p][ptlen - 1] = '\0';
   3789         }
   3790     }
   3791 
   3792 #ifdef OPTIMIZE_PATTERN
   3793     re_optimize_patterns(nre, num_pattern);
   3794 #endif
   3795 
   3796     rv = re_case_adjust(nre, num_pattern, res_flags);
   3797 
   3798     /* 
   3799      * make the classes so that we can replace the tokens with the classes.
   3800      * this reduces the number of transitions and arcs and hence 
   3801      * computational complexity.
   3802      */
   3803     rv = re_make_symbol_classes_from_pattern(nre, num_pattern, 
   3804                                              res_flags, &class_array, &num_classes);
   3805     if (rv) {
   3806         rv = REGEX_ERROR_INVALID_CLASS;
   3807         goto fail;
   3808     }
   3809 
   3810     rv = make_nfa(nre, res_flags, num_pattern, &pnfa, class_array, num_classes);
   3811     if (rv) {
   3812         sal_free(class_array);
   3813         rv = REGEX_ERROR_NO_NFA;
   3814         goto fail;
   3815     }
   3816 
   3817     if (make_dfa(num_pattern, &pdfa, &pnfa, class_array, num_classes) || !pdfa) {
   3818         rv = REGEX_ERROR_NO_DFA;
   3819         goto fail;
   3820     }
   3821 
   3822     /* return the number of DFA states */
   3823     rv = pdfa->num_states;
   3824 
   3825 fail:
   3826     for(p=0; p<num_pattern; p++) {
   3827         if (nre[p]) {
   3828             sal_free(nre[p]);
   3829         }
   3830     }
   3831     sal_free(nre);
   3832     if (pnfa) {
   3833         nfa_free(pnfa);
   3834     }
   3835     if ((rv < 0) || (!ppdfa)) {
   3836         if (pdfa) {
   3837             dfa_free(pdfa);
   3838         }
   3839         return rv;
   3840     }
   3841     *ppdfa = (void*)pdfa;
   3842 
   3843     RE_SAL_DPRINT(("\nCreated DFA with %d states\n", pdfa->num_states));
   3844 
   3845     return rv;
   3846 }
   3847 
   3848 typedef struct _re_state_compress_s {
   3849     int state_id;
   3850     unsigned int transition_map[8];
   3851     unsigned int num_ranges;
   3852     struct _re_state_compress_s *next;
   3853 } _re_state_compress;
   3854 
   3855 static _re_state_compress* 
   3856 _re_find_compress_state(_re_state_compress **h, int state_id)
   3857 {
   3858     /*
   3859     _re_state_compress *ps;
   3860     */
   3861     
   3862     while (*h && ((*h)->state_id != state_id)) {
   3863         h = &(*h)->next;
   3864     }
   3865     return *h;
   3866 }
   3867 
   3868 static int
   3869 _re_add_tr_to_compress_state(_re_state_compress **h,
   3870                              int to_state_id, unsigned int *bitmap)
   3871 {
   3872     _re_state_compress *ps;
   3873     int i;
   3874 
   3875     ps = _re_find_compress_state(h, to_state_id);
   3876     if (!ps) {
   3877         ps = sal_alloc(sizeof(_re_state_compress),"zipst");
   3878         sal_memset(ps, 0, sizeof(_re_state_compress));
   3879         /* add to list */
   3880         ps->state_id = to_state_id;
   3881         ps->next = *h;
   3882         *h = ps;
   3883     }
   3884 
   3885     for (i = 0; i < 8; i++) {
   3886         ps->transition_map[i] |= bitmap[i];
   3887     }
   3888     return 0;
   3889 }
   3890 
   3891 int bcm_regex_dfa_traverse(void *dfa, regex_dfa_state_cb compile_dfa_cb,
   3892                             void *user_data)
   3893 {
   3894     re_dfa_state_t *state;
   3895     re_dfa_t  *dfa_list = (re_dfa_t *)dfa;
   3896     unsigned flags = 0;
   3897     int c, to_state, rv = REGEX_ERROR_NONE;
   3898     int match_idx, i, j, k, lc, has_transition;
   3899     re_transition_class  *class;
   3900     _re_state_compress *dlist[8], *pd, *else_jump_destination=NULL;
   3901     int jump_count;
   3902     int jump_to_all_classes;
   3903 
   3904 
   3905     sal_memset(dlist, 0, sizeof(_re_state_compress*)*8);
   3906 
   3907     /*
   3908      * Dummy callback to indicate start of iteration. Application might do
   3909      * something specific like init or something.
   3910      */
   3911     if (compile_dfa_cb(DFA_TRAVERSE_START, -1, -1, -1, -1, -1, dfa_list->num_states, user_data)) {
   3912         return REGEX_ERROR;
   3913     }
   3914 
   3915     /*
   3916     Call user provided callback for each DFA state. compress the
   3917     transitions so as to minimize the memory requirements.
   3918 
   3919     Note that each state will originally have a transition for
   3920     each character class.  During compression, these transitions
   3921     are folded together to make a smaller number of transitions
   3922     that go to the same states.
   3923 
   3924     The optimization below reduces the number of transitions
   3925     even further.
   3926 
   3927     Note: class->transition_map really represents a map of the
   3928     different characters that are covered by the classes.
   3929 
   3930     For the future, the transition compression should be
   3931     changed to be done only once rather than for each
   3932     traversal.
   3933     */
   3934     for (i = 0; i < dfa_list->num_states; i++) {
   3935         state = dfa_list->states[i];
   3936         flags = 0;
   3937         match_idx = -1;
   3938         has_transition = 0;
   3939         jump_to_all_classes = 1;
   3940 
   3941         for (j = 0; j < dfa_list->num_classes; j++) {
   3942             if (state->transition_list[j] == -1) {
   3943                 jump_to_all_classes = 0;
   3944                 continue;
   3945             }
   3946             has_transition++;
   3947             c = j;
   3948             to_state = state->transition_list[j];
   3949             class = &dfa_list->class_array[c];
   3950 
   3951             _re_add_tr_to_compress_state(&dlist[to_state % COUNTOF(dlist)],
   3952                                          to_state, class->transition_map);
   3953         }
   3954 
   3955         /*
   3956          * dlist now contains one entry for each jump destination.  If there are jumps to
   3957          * every character class, then find the destination with the largest number of
   3958          * ranges (i.e., will have the most number of jump instructions) and replace it
   3959          * with a single jump instruction for all characters (i.e., an else clause).
   3960          */
   3961 
   3962         else_jump_destination = NULL;
   3963         if (0 != jump_to_all_classes) {
   3964             jump_count = 0;
   3965             for (j = 0; j < COUNTOF(dlist); j++) {
   3966                 pd = dlist[j];
   3967                 while (pd) {
   3968                     lc = -1;
   3969                     for (k = 0; k < REGEX_MAX_CHARACTER_CLASSES; k++) {
   3970                         if (pd->transition_map[k / WORDS2BITS(1)] & (1 << (k % WORDS2BITS(1)))) {
   3971                             if (lc == -1) {
   3972                                 pd->num_ranges++;
   3973                                 lc = k;
   3974                             }
   3975                         } else {
   3976                             lc = -1;
   3977                         }
   3978                     }
   3979                     if (pd->num_ranges > jump_count) {
   3980                         jump_count = pd->num_ranges;
   3981                         else_jump_destination = pd;
   3982                     }
   3983                     pd = pd->next;
   3984                 }
   3985             }
   3986 
   3987             /*
   3988              * A destination is found which can save at least one jump, remove it from
   3989              * the list of destinations.
   3990              */
   3991             if (jump_count > 1) {
   3992                 for (j = 0; j < COUNTOF(dlist); j++) {
   3993                     if (dlist[j] == else_jump_destination) {
   3994                         dlist[j] = else_jump_destination->next;
   3995                     } else {
   3996                         pd = dlist[j];
   3997                         while (pd) {
   3998                             if (pd->next == else_jump_destination) {
   3999                                 pd->next = else_jump_destination->next;
   4000                                 break;
   4001                             }
   4002                             pd = pd->next;
   4003                         }
   4004                     }
   4005                 }
   4006             } else {
   4007                 else_jump_destination = NULL;
   4008             }
   4009         }
   4010 
   4011         if (RE_DFA_IS_FINAL(state)) {
   4012             match_idx = RE_DFA_FINAL(state) - 1;
   4013             flags = DFA_STATE_FINAL;
   4014             if (!has_transition) {
   4015                 if (compile_dfa_cb(DFA_STATE_FINAL, 
   4016                                    match_idx, RE_DFA_STATEID(state),
   4017                                    -1, -1, -1, dfa_list->num_states, user_data)) {
   4018                     rv = REGEX_ERROR;
   4019                     goto done;
   4020                 }
   4021             }
   4022         }
   4023 
   4024         for (j = 0; j < COUNTOF(dlist); j++) {
   4025             while (dlist[j]) {
   4026                 pd = dlist[j];
   4027                 to_state = pd->state_id;
   4028                 lc = -1;
   4029                 for (k = 0; k < REGEX_MAX_CHARACTER_CLASSES; k++) {
   4030                     if (pd->transition_map[k / WORDS2BITS(1)] & (1 << (k % WORDS2BITS(1)))) {
   4031                         if (lc == -1) {
   4032                             lc = k;
   4033                         }
   4034                     } else if (lc >= 0) {
   4035                         if (compile_dfa_cb(flags, match_idx, 
   4036                                            RE_DFA_STATEID(state), lc, k-1,
   4037                                            pd->state_id, dfa_list->num_states,
   4038                                        user_data)) {
   4039                             rv = REGEX_ERROR;
   4040                             goto done;
   4041                         }
   4042                         lc = -1;
   4043                     }
   4044                 }
   4045                 if (lc >= 0)  {
   4046                     if (compile_dfa_cb(flags, match_idx, RE_DFA_STATEID(state),
   4047                                        lc, REGEX_MAX_CHARACTER_CLASSES-1, pd->state_id, dfa_list->num_states, user_data)) {
   4048                         rv = REGEX_ERROR;
   4049                         goto done;
   4050                     }
   4051                 }
   4052                 dlist[j] = pd->next;
   4053                 sal_free(pd);
   4054             }
   4055             dlist[j] = NULL;
   4056         }
   4057 
   4058         /*
   4059         If an "else" jump destination has been found, process it here.
   4060         */
   4061 
   4062         if (NULL != else_jump_destination) {
   4063             if (compile_dfa_cb(flags, match_idx, RE_DFA_STATEID(state),
   4064                                0, REGEX_MAX_CHARACTER_CLASSES - 1,
   4065                                else_jump_destination->state_id, dfa_list->num_states, user_data)) {
   4066                 rv = REGEX_ERROR;
   4067                 goto done;
   4068             }
   4069             sal_free(else_jump_destination);
   4070             else_jump_destination = NULL;
   4071         }
   4072     }
   4073 
   4074     /* indicate end of traverse, so that any house keeping can be done
   4075      * now */
   4076     compile_dfa_cb(DFA_TRAVERSE_END, -1, -1, -1, -1, -1, dfa_list->num_states, user_data);
   4077 
   4078 done:
   4079     if (NULL != else_jump_destination) {
   4080         sal_free(else_jump_destination);
   4081     }
   4082     for (i = 0; i < COUNTOF(dlist); i++) {
   4083         while(dlist[i]) {
   4084             pd = dlist[i]->next;
   4085             sal_free(dlist[i]);
   4086             dlist[i] = pd;
   4087         }
   4088     }
   4089     return rv;
   4090 }
   4091 
   4092 int bcm_regex_dfa_free(void *dfa)
   4093 {
   4094     dfa_free((re_dfa_t*)dfa);
   4095     return 0;
   4096 }
   4097 
   4098 #ifndef BROADCOM_SDK 
   4099 
   4100 int
   4101 main(int argc, char **argv)
   4102 {
   4103     int rv, num_pat = 0, i, valid, bi;
   4104     char *pc[64], tmp_re[512], c;
   4105     unsigned int re_flags[512];
   4106     unsigned int def_flags = 0 /* BCM_TR3_REGEX_CFLAG_EXPAND_LCUC */;
   4107     void *dfa;
   4108     FILE *fp;
   4109 
   4110     fp = fopen("patterns.txt", "r");
   4111 
   4112     bi = 0;
   4113     while((c = getc(fp)) != EOF) {
   4114         if ((c == '\n') || (c == '\r')) {
   4115             valid = 0;
   4116             i = 0;
   4117             while (i < bi) {
   4118                 if ((tmp_re[i] != ' ') && (tmp_re[i] != '\t')) {
   4119                     valid = 1;
   4120                     break;
   4121                 }
   4122             }
   4123             
   4124             if (valid) {
   4125                 tmp_re[bi] = '\0';
   4126                 pc[num_pat] = sal_alloc(512,"main");
   4127                 strcpy(pc[num_pat], tmp_re);
   4128                 re_flags[num_pat] = def_flags;
   4129                 num_pat++;
   4130             }
   4131             bi = 0;
   4132             continue;
   4133         }
   4134         tmp_re[bi++] = c;
   4135     }
   4136     
   4137     rv = bcm_regex_compile(pc, re_flags, num_pat, 0, &dfa);
   4138     if (rv <= 0) {
   4139         RE_SAL_DPRINT(("\n FAILED error=%d, re=%s\n", rv, argv[1]));
   4140     }
   4141 
   4142     dfa_free(dfa);
   4143 
   4144     for (i=0; i<num_pat; i++) {
   4145         sal_free(pc[i]);
   4146     }
   4147 
   4148 #if MEM_PROFILE == 1
   4149     re_dump_mem_leak();
   4150 #endif
   4151 
   4152     return 0;
   4153 }
   4154 #endif
   4155 
   4156 
   4157 #else
   4158 int regex_supported = 0;
   4159 #endif
	openbcm Git mirror of https://github.com/Broadcom-Network-Switching-Software/OpenBCM
	git clone git://git.finwo.net/mirror/broadcom/openbcm
	Log \| Files \| Refs \| README