lib/silcutil/silcregex.c

   1 /* regexpr.c
   2  *
   3  * Author: Tatu Ylonen <ylo@ngs.fi>
   4  *
   5  * Copyright (c) 1991 Tatu Ylonen, Espoo, Finland
   6  *
   7  * Permission to use, copy, modify, distribute, and sell this software
   8  * and its documentation for any purpose is hereby granted without
   9  * fee, provided that the above copyright notice appear in all copies.
  10  * This software is provided "as is" without express or implied
  11  * warranty.
  12  *
  13  * Created: Thu Sep 26 17:14:05 1991 ylo
  14  * Last modified: Mon Nov  4 17:06:48 1991 ylo
  15  * Ported to Think C: 19 Jan 1992 guido@cwi.nl
  16  *
  17  * This code draws many ideas from the regular expression packages by
  18  * Henry Spencer of the University of Toronto and Richard Stallman of
  19  * the Free Software Foundation.
  20  *
  21  * Bugs fixed and lots of reorganization by Jeffrey C. Ollie, April
  22  * 1997 Thanks for bug reports and ideas from Andrew Kuchling, Tim
  23  * Peters, Guido van Rossum, Ka-Ping Yee, Sjoerd Mullender, and
  24  * probably one or two others that I'm forgetting.
  25  *
  26  */
  27
  28 /*
  29   The SILC Regex API and modifications by Pekka Riikonen, under the same
  30   license as the original code.  We've added the following features:
  31
  32   - RE_SYNTAX_POSIX      POSIX extended regular expression syntax
  33   - RE_REPEAT            bounded repeat a{n,m} (RE_SYNTAX_POSIX)
  34   - RE_NOTBOL            bol fails to match (conforming POSIX regex API)
  35   - RE_NOTEOL            eol fails to match (conforming POSIX regex API)
  36   - SilcStack support    compile/match without real memory allocations
  37 */
  38
  39 #include "silc.h"
  40
  41 #define RE_NREGS        128     /* number of registers available */
  42
  43 /* bit definitions for syntax */
  44 #define RE_NO_BK_PARENS         1    /* no quoting for parentheses */
  45 #define RE_NO_BK_VBAR           2    /* no quoting for vertical bar */
  46 #define RE_BK_PLUS_QM           4    /* quoting needed for + and ? */
  47 #define RE_TIGHT_VBAR           8    /* | binds tighter than ^ and $ */
  48 #define RE_NEWLINE_OR           16   /* treat newline as or */
  49 #define RE_CONTEXT_INDEP_OPS    32   /* ^$?*+ are special in all contexts */
  50 #define RE_ANSI_HEX             64   /* ansi sequences (\n etc) and \xhh */
  51 #define RE_NO_GNU_EXTENSIONS   128   /* no gnu extensions */
  52 #define RE_NOTBOL              256   /* bol fails to match */
  53 #define RE_NOTEOL              512   /* eol fails to match */
  54 #define RE_REPEAT             1024   /* bounded repeat expression */
  55
  56 /* definitions for some common regexp styles */
  57 #define RE_SYNTAX_AWK   (RE_NO_BK_PARENS|RE_NO_BK_VBAR|RE_CONTEXT_INDEP_OPS)
  58 #define RE_SYNTAX_EGREP (RE_SYNTAX_AWK|RE_NEWLINE_OR)
  59 #define RE_SYNTAX_GREP  (RE_BK_PLUS_QM|RE_NEWLINE_OR)
  60 #define RE_SYNTAX_POSIX (RE_SYNTAX_AWK|RE_REPEAT)
  61 #define RE_SYNTAX_EMACS 0
  62
  63 #define Sword       1
  64 #define Swhitespace 2
  65 #define Sdigit      4
  66 #define Soctaldigit 8
  67 #define Shexdigit   16
  68
  69 /* Registers */
  70 typedef struct re_registers {
  71   int start[RE_NREGS];          /* start offset of region */
  72   int end[RE_NREGS];            /* end offset of region */
  73 } *regexp_registers_t;
  74
  75 /* The original code blithely assumed that sizeof(short) == 2.  Not
  76  * always true.  Original instances of "(short)x" were replaced by
  77  * SHORT(x), where SHORT is #defined below.  */
  78
  79 #define SHORT(x) ((x) & 0x8000 ? (x) - 0x10000 : (x))
  80
  81 /* The stack implementation is taken from an idea by Andrew Kuchling.
  82  * It's a doubly linked list of arrays. The advantages of this over a
  83  * simple linked list are that the number of mallocs required are
  84  * reduced. It also makes it possible to statically allocate enough
  85  * space so that small patterns don't ever need to call malloc.
  86  *
  87  * The advantages over a single array is that is periodically
  88  * realloced when more space is needed is that we avoid ever copying
  89  * the stack. */
  90
  91 /* item_t is the basic stack element.  Defined as a union of
  92  * structures so that both registers, failure points, and counters can
  93  * be pushed/popped from the stack.  There's nothing built into the
  94  * item to keep track of whether a certain stack item is a register, a
  95  * failure point, or a counter. */
  96
  97 typedef union item_t
  98 {
  99   struct
 100   {
 101     int num;
 102     int level;
 103     unsigned char *start;
 104     unsigned char *end;
 105   } reg;
 106   struct
 107   {
 108     int count;
 109     int level;
 110     int phantom;
 111     unsigned char *code;
 112     unsigned char *text;
 113   } fail;
 114   struct
 115   {
 116     int num;
 117     int level;
 118     int count;
 119   } cntr;
 120 } item_t;
 121
 122 #define STACK_PAGE_SIZE 256
 123 #define NUM_REGISTERS 256
 124
 125 /* A 'page' of stack items. */
 126
 127 typedef struct item_page_t
 128 {
 129   item_t items[STACK_PAGE_SIZE];
 130   struct item_page_t *prev;
 131   struct item_page_t *next;
 132 } item_page_t;
 133
 134 typedef struct match_state
 135 {
 136   /* The number of registers that have been pushed onto the stack
 137    * since the last failure point. */
 138
 139   int count;
 140
 141   /* Used to control when registers need to be pushed onto the
 142    * stack. */
 143
 144   int level;
 145
 146   /* The number of failure points on the stack. */
 147
 148   int point;
 149
 150   /* Storage for the registers.  Each register consists of two
 151    * pointers to characters.  So register N is represented as
 152    * start[N] and end[N].  The pointers must be converted to
 153    * offsets from the beginning of the string before returning the
 154    * registers to the calling program. */
 155
 156   unsigned char *start[NUM_REGISTERS];
 157   unsigned char *end[NUM_REGISTERS];
 158
 159   /* Keeps track of whether a register has changed recently. */
 160
 161   int changed[NUM_REGISTERS];
 162
 163   /* Structure to encapsulate the stack. */
 164   struct
 165   {
 166     /* index into the current page.  If index == 0 and you need
 167      * to pop an item, move to the previous page and set index
 168      * = STACK_PAGE_SIZE - 1.  Otherwise decrement index to
 169      * push a page. If index == STACK_PAGE_SIZE and you need
 170      * to push a page move to the next page and set index =
 171      * 0. If there is no new next page, allocate a new page
 172      * and link it in. Otherwise, increment index to push a
 173      * page. */
 174
 175     int index;
 176     item_page_t *current; /* Pointer to the current page. */
 177     item_page_t first; /* First page is statically allocated. */
 178   } stack;
 179 } match_state;
 180
 181 /* Initialize a state object */
 182
 183 /* #define NEW_STATE(state) \ */
 184 /* memset(&state, 0, (void *)(&state.stack) - (void *)(&state)); \ */
 185 /* state.stack.current = &state.stack.first; \ */
 186 /* state.stack.first.prev = NULL; \ */
 187 /* state.stack.first.next = NULL; \ */
 188 /* state.stack.index = 0; \ */
 189 /* state.level = 1 */
 190
 191 #define NEW_STATE(state, nregs)                 \
 192   {                                             \
 193     int i;                                      \
 194     for (i = 0; i < nregs; i++)                 \
 195       {                                         \
 196         state.start[i] = NULL;                  \
 197         state.end[i] = NULL;                    \
 198         state.changed[i] = 0;                   \
 199       }                                         \
 200     state.stack.current = &state.stack.first;   \
 201     state.stack.first.prev = NULL;              \
 202     state.stack.first.next = NULL;              \
 203     state.stack.index = 0;                      \
 204     state.level = 1;                            \
 205     state.count = 0;                            \
 206     state.level = 0;                            \
 207     state.point = 0;                            \
 208   }
 209
 210 /* Free any memory that might have been malloc'd */
 211
 212 #define FREE_STATE(state)                                       \
 213   while(state.stack.first.next != NULL)                         \
 214     {                                                           \
 215       state.stack.current = state.stack.first.next;             \
 216       state.stack.first.next = state.stack.current->next;       \
 217       silc_sfree(bufp->rstack, state.stack.current);            \
 218     }
 219
 220 /* Discard the top 'count' stack items. */
 221
 222 #define STACK_DISCARD(stack, count, on_error)   \
 223   stack.index -= count;                         \
 224   while (stack.index < 0)                       \
 225     {                                           \
 226       if (stack.current->prev == NULL)          \
 227         on_error;                               \
 228       stack.current = stack.current->prev;      \
 229       stack.index += STACK_PAGE_SIZE;           \
 230     }
 231
 232 /* Store a pointer to the previous item on the stack. Used to pop an
 233  * item off of the stack. */
 234
 235 #define STACK_PREV(stack, top, on_error)        \
 236   if (stack.index == 0)                         \
 237     {                                           \
 238       if (stack.current->prev == NULL)          \
 239         on_error;                               \
 240       stack.current = stack.current->prev;      \
 241       stack.index = STACK_PAGE_SIZE - 1;        \
 242     }                                           \
 243   else                                          \
 244     {                                           \
 245       stack.index--;                            \
 246     }                                           \
 247   top = &(stack.current->items[stack.index])
 248
 249 /* Store a pointer to the next item on the stack. Used to push an item
 250  * on to the stack. */
 251
 252 #define STACK_NEXT(stack, top, on_error)                                \
 253   if (stack.index == STACK_PAGE_SIZE)                                   \
 254     {                                                                   \
 255       if (stack.current->next == NULL)                                  \
 256         {                                                               \
 257           stack.current->next =                                         \
 258             (item_page_t *)silc_smalloc(bufp->rstack, sizeof(item_page_t)); \
 259           if (stack.current->next == NULL)                              \
 260             on_error;                                                   \
 261           stack.current->next->prev = stack.current;                    \
 262           stack.current->next->next = NULL;                             \
 263         }                                                               \
 264       stack.current = stack.current->next;                              \
 265       stack.index = 0;                                                  \
 266     }                                                                   \
 267   top = &(stack.current->items[stack.index++])
 268
 269 /* Store a pointer to the item that is 'count' items back in the
 270  * stack. STACK_BACK(stack, top, 1, on_error) is equivalent to
 271  * STACK_TOP(stack, top, on_error).  */
 272
 273 #define STACK_BACK(stack, top, count, on_error) \
 274   {                                             \
 275     int index;                                  \
 276     item_page_t *current;                       \
 277     current = stack.current;                    \
 278     index = stack.index - (count);              \
 279     while (index < 0)                           \
 280       {                                         \
 281         if (current->prev == NULL)              \
 282           on_error;                             \
 283         current = current->prev;                \
 284         index += STACK_PAGE_SIZE;               \
 285       }                                         \
 286     top = &(current->items[index]);             \
 287   }
 288
 289 /* Store a pointer to the top item on the stack. Execute the
 290  * 'on_error' code if there are no items on the stack. */
 291
 292 #define STACK_TOP(stack, top, on_error)                         \
 293   if (stack.index == 0)                                         \
 294     {                                                           \
 295       if (stack.current->prev == NULL)                          \
 296         on_error;                                               \
 297       top = &(stack.current->prev->items[STACK_PAGE_SIZE - 1]); \
 298     }                                                           \
 299   else                                                          \
 300     {                                                           \
 301       top = &(stack.current->items[stack.index - 1]);           \
 302     }
 303
 304 /* Test to see if the stack is empty */
 305
 306 #define STACK_EMPTY(stack) ((stack.index == 0) &&               \
 307                             (stack.current->prev == NULL))
 308
 309 /* Return the start of register 'reg' */
 310
 311 #define GET_REG_START(state, reg) (state.start[reg])
 312
 313 /* Return the end of register 'reg' */
 314
 315 #define GET_REG_END(state, reg) (state.end[reg])
 316
 317 /* Set the start of register 'reg'. If the state of the register needs
 318  * saving, push it on the stack. */
 319
 320 #define SET_REG_START(state, reg, text, on_error)       \
 321   if(state.changed[reg] < state.level)                  \
 322     {                                                   \
 323       item_t *item;                                     \
 324       STACK_NEXT(state.stack, item, on_error);          \
 325       item->reg.num = reg;                              \
 326       item->reg.start = state.start[reg];               \
 327       item->reg.end = state.end[reg];                   \
 328       item->reg.level = state.changed[reg];             \
 329       state.changed[reg] = state.level;                 \
 330       state.count++;                                    \
 331     }                                                   \
 332   state.start[reg] = text
 333
 334 /* Set the end of register 'reg'. If the state of the register needs
 335  * saving, push it on the stack. */
 336
 337 #define SET_REG_END(state, reg, text, on_error) \
 338   if(state.changed[reg] < state.level)          \
 339     {                                           \
 340       item_t *item;                             \
 341       STACK_NEXT(state.stack, item, on_error);  \
 342       item->reg.num = reg;                      \
 343       item->reg.start = state.start[reg];       \
 344       item->reg.end = state.end[reg];           \
 345       item->reg.level = state.changed[reg];     \
 346       state.changed[reg] = state.level;         \
 347       state.count++;                            \
 348     }                                           \
 349   state.end[reg] = text
 350
 351 #define PUSH_FAILURE(state, xcode, xtext, on_error)     \
 352   {                                                     \
 353     item_t *item;                                       \
 354     STACK_NEXT(state.stack, item, on_error);            \
 355     item->fail.code = xcode;                            \
 356     item->fail.text = xtext;                            \
 357     item->fail.count = state.count;                     \
 358     item->fail.level = state.level;                     \
 359     item->fail.phantom = 0;                             \
 360     state.count = 0;                                    \
 361     state.level++;                                      \
 362     state.point++;                                      \
 363   }
 364
 365 /* Update the last failure point with a new position in the text. */
 366
 367 #define UPDATE_FAILURE(state, xtext, on_error)                  \
 368   {                                                             \
 369     item_t *item;                                               \
 370     STACK_BACK(state.stack, item, state.count + 1, on_error);   \
 371     if (!item->fail.phantom)                                    \
 372       {                                                         \
 373         item_t *item2;                                          \
 374         STACK_NEXT(state.stack, item2, on_error);               \
 375         item2->fail.code = item->fail.code;                     \
 376         item2->fail.text = xtext;                               \
 377         item2->fail.count = state.count;                        \
 378         item2->fail.level = state.level;                        \
 379         item2->fail.phantom = 1;                                \
 380         state.count = 0;                                        \
 381         state.level++;                                          \
 382         state.point++;                                          \
 383       }                                                         \
 384     else                                                        \
 385       {                                                         \
 386         STACK_DISCARD(state.stack, state.count, on_error);      \
 387         STACK_TOP(state.stack, item, on_error);                 \
 388         item->fail.text = xtext;                                \
 389         state.count = 0;                                        \
 390         state.level++;                                          \
 391       }                                                         \
 392   }
 393
 394 #define POP_FAILURE(state, xcode, xtext, on_empty, on_error)    \
 395   {                                                             \
 396     item_t *item;                                               \
 397     do                                                          \
 398       {                                                         \
 399         while(state.count > 0)                                  \
 400           {                                                     \
 401             STACK_PREV(state.stack, item, on_error);            \
 402             state.start[item->reg.num] = item->reg.start;       \
 403             state.end[item->reg.num] = item->reg.end;           \
 404             state.changed[item->reg.num] = item->reg.level;     \
 405             state.count--;                                      \
 406           }                                                     \
 407         STACK_PREV(state.stack, item, on_empty);                \
 408         xcode = item->fail.code;                                \
 409         xtext = item->fail.text;                                \
 410         state.count = item->fail.count;                         \
 411         state.level = item->fail.level;                         \
 412         state.point--;                                          \
 413       }                                                         \
 414     while (item->fail.text == NULL);                            \
 415   }
 416
 417 enum regexp_compiled_ops /* opcodes for compiled regexp */
 418 {
 419   Cend,                 /* end of pattern reached */
 420   Cbol,                 /* beginning of line */
 421   Ceol,                 /* end of line */
 422   Cset,                 /* character set.  Followed by 32 bytes of set. */
 423   Cexact,               /* followed by a byte to match */
 424   Canychar,             /* matches any character except newline */
 425   Cstart_memory,        /* set register start addr (followed by reg number) */
 426   Cend_memory,          /* set register end addr (followed by reg number) */
 427   Cmatch_memory,        /* match a duplicate of reg contents (regnum follows)*/
 428   Cjump,                /* followed by two bytes (lsb,msb) of displacement. */
 429   Cstar_jump,           /* will change to jump/update_failure_jump at runtime */
 430   Cfailure_jump,        /* jump to addr on failure */
 431   Cupdate_failure_jump, /* update topmost failure point and jump */
 432   Cdummy_failure_jump,  /* push a dummy failure point and jump */
 433   Cbegbuf,              /* match at beginning of buffer */
 434   Cendbuf,              /* match at end of buffer */
 435   Cwordbeg,             /* match at beginning of word */
 436   Cwordend,             /* match at end of word */
 437   Cwordbound,           /* match if at word boundary */
 438   Cnotwordbound,        /* match if not at word boundary */
 439   Csyntaxspec,          /* matches syntax code (1 byte follows) */
 440   Cnotsyntaxspec,       /* matches if syntax code does not match (1 byte foll)*/
 441   Crepeat1,
 442 };
 443
 444 enum regexp_syntax_op   /* syntax codes for plain and quoted characters */
 445 {
 446   Rend,                 /* special code for end of regexp */
 447   Rnormal,              /* normal character */
 448   Ranychar,             /* any character except newline */
 449   Rquote,               /* the quote character */
 450   Rbol,                 /* match beginning of line */
 451   Reol,                 /* match end of line */
 452   Roptional,            /* match preceding expression optionally */
 453   Rstar,                /* match preceding expr zero or more times */
 454   Rplus,                /* match preceding expr one or more times */
 455   Ror,                  /* match either of alternatives */
 456   Ropenpar,             /* opening parenthesis */
 457   Rclosepar,            /* closing parenthesis */
 458   Rmemory,              /* match memory register */
 459   Rextended_memory,     /* \vnn to match registers 10-99 */
 460   Ropenset,             /* open set.  Internal syntax hard-coded below. */
 461   /* the following are gnu extensions to "normal" regexp syntax */
 462   Rbegbuf,              /* beginning of buffer */
 463   Rendbuf,              /* end of buffer */
 464   Rwordchar,            /* word character */
 465   Rnotwordchar,         /* not word character */
 466   Rwordbeg,             /* beginning of word */
 467   Rwordend,             /* end of word */
 468   Rwordbound,           /* word bound */
 469   Rnotwordbound,        /* not word bound */
 470   Rnum_ops,
 471   Ropenrep,             /* opening bounded repeat */
 472 };
 473
 474 static int re_compile_initialized = 0;
 475 static int regexp_syntax = 0;
 476 static unsigned char regexp_plain_ops[256];
 477 static unsigned char regexp_quoted_ops[256];
 478 static unsigned char regexp_precedences[Rnum_ops];
 479 static int regexp_context_indep_ops;
 480 static int regexp_ansi_sequences;
 481
 482 #define NUM_LEVELS  5    /* number of precedence levels in use */
 483 #define MAX_NESTING 100  /* max nesting level of operators */
 484
 485 #define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)]
 486
 487 static unsigned char re_syntax_table[256];
 488
 489 void silc_re_compile_initialize(void)
 490 {
 491   int a;
 492
 493   static int syntax_table_inited = 0;
 494
 495   if (!syntax_table_inited)
 496     {
 497       syntax_table_inited = 1;
 498       memset(re_syntax_table, 0, 256);
 499       for (a = 'a'; a <= 'z'; a++)
 500         re_syntax_table[a] = Sword;
 501       for (a = 'A'; a <= 'Z'; a++)
 502         re_syntax_table[a] = Sword;
 503       for (a = '0'; a <= '9'; a++)
 504         re_syntax_table[a] = Sword | Sdigit | Shexdigit;
 505       for (a = '0'; a <= '7'; a++)
 506         re_syntax_table[a] |= Soctaldigit;
 507       for (a = 'A'; a <= 'F'; a++)
 508         re_syntax_table[a] |= Shexdigit;
 509       for (a = 'a'; a <= 'f'; a++)
 510         re_syntax_table[a] |= Shexdigit;
 511       re_syntax_table['_'] = Sword;
 512       for (a = 9; a <= 13; a++)
 513         re_syntax_table[a] = Swhitespace;
 514       re_syntax_table[' '] = Swhitespace;
 515     }
 516   re_compile_initialized = 1;
 517   for (a = 0; a < 256; a++)
 518     {
 519       regexp_plain_ops[a] = Rnormal;
 520       regexp_quoted_ops[a] = Rnormal;
 521     }
 522   for (a = '0'; a <= '9'; a++)
 523     regexp_quoted_ops[a] = Rmemory;
 524   regexp_plain_ops['\134'] = Rquote;
 525   if (regexp_syntax & RE_NO_BK_PARENS)
 526     {
 527       regexp_plain_ops['('] = Ropenpar;
 528       regexp_plain_ops[')'] = Rclosepar;
 529     }
 530   else
 531     {
 532       regexp_quoted_ops['('] = Ropenpar;
 533       regexp_quoted_ops[')'] = Rclosepar;
 534     }
 535   if (regexp_syntax & RE_NO_BK_VBAR)
 536     regexp_plain_ops['\174'] = Ror;
 537   else
 538     regexp_quoted_ops['\174'] = Ror;
 539   regexp_plain_ops['*'] = Rstar;
 540   if (regexp_syntax & RE_BK_PLUS_QM)
 541     {
 542       regexp_quoted_ops['+'] = Rplus;
 543       regexp_quoted_ops['?'] = Roptional;
 544     }
 545   else
 546     {
 547       regexp_plain_ops['+'] = Rplus;
 548       regexp_plain_ops['?'] = Roptional;
 549     }
 550   if (regexp_syntax & RE_NEWLINE_OR)
 551     regexp_plain_ops['\n'] = Ror;
 552   regexp_plain_ops['\133'] = Ropenset;
 553   regexp_plain_ops['\136'] = Rbol;
 554   regexp_plain_ops['$'] = Reol;
 555   regexp_plain_ops['.'] = Ranychar;
 556   if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS))
 557     {
 558       regexp_quoted_ops['w'] = Rwordchar;
 559       regexp_quoted_ops['W'] = Rnotwordchar;
 560       regexp_quoted_ops['<'] = Rwordbeg;
 561       regexp_quoted_ops['>'] = Rwordend;
 562       regexp_quoted_ops['b'] = Rwordbound;
 563       regexp_quoted_ops['B'] = Rnotwordbound;
 564       regexp_quoted_ops['`'] = Rbegbuf;
 565       regexp_quoted_ops['\''] = Rendbuf;
 566     }
 567   if (regexp_syntax & RE_ANSI_HEX)
 568     regexp_quoted_ops['v'] = Rextended_memory;
 569   for (a = 0; a < Rnum_ops; a++)
 570     regexp_precedences[a] = 4;
 571   if (regexp_syntax & RE_TIGHT_VBAR)
 572     {
 573       regexp_precedences[Ror] = 3;
 574       regexp_precedences[Rbol] = 2;
 575       regexp_precedences[Reol] = 2;
 576     }
 577   else
 578     {
 579       regexp_precedences[Ror] = 2;
 580       regexp_precedences[Rbol] = 3;
 581       regexp_precedences[Reol] = 3;
 582     }
 583   if (regexp_syntax & RE_REPEAT)
 584     {
 585       if (regexp_syntax & RE_NO_BK_PARENS)
 586         {
 587           regexp_plain_ops['{'] = Ropenrep;
 588         }
 589       else
 590         {
 591           regexp_quoted_ops['{'] = Ropenrep;
 592         }
 593     }
 594   regexp_precedences[Rclosepar] = 1;
 595   regexp_precedences[Rend] = 0;
 596   regexp_context_indep_ops = (regexp_syntax & RE_CONTEXT_INDEP_OPS) != 0;
 597   regexp_ansi_sequences = (regexp_syntax & RE_ANSI_HEX) != 0;
 598 }
 599
 600 int silc_re_set_syntax(int syntax)
 601 {
 602   int ret;
 603
 604   ret = regexp_syntax;
 605   regexp_syntax = syntax;
 606   silc_re_compile_initialize();
 607   return ret;
 608 }
 609
 610 static int silc_hex_char_to_decimal(int ch)
 611 {
 612   if (ch >= '0' && ch <= '9')
 613     return ch - '0';
 614   if (ch >= 'a' && ch <= 'f')
 615     return ch - 'a' + 10;
 616   if (ch >= 'A' && ch <= 'F')
 617     return ch - 'A' + 10;
 618   return 16;
 619 }
 620
 621 static int silc_re_compile_fastmap_aux(unsigned char *code, int pos,
 622                                        unsigned char *visited,
 623                                        unsigned char *can_be_null,
 624                                        unsigned char *fastmap)
 625 {
 626   int a;
 627   int b;
 628   int syntaxcode;
 629
 630   if (visited[pos])
 631     return 0;  /* we have already been here */
 632   visited[pos] = 1;
 633   for (;;)
 634     switch (code[pos++]) {
 635     case Cend:
 636       {
 637         *can_be_null = 1;
 638         return 0;
 639       }
 640     case Cbol:
 641     case Cbegbuf:
 642     case Cendbuf:
 643     case Cwordbeg:
 644     case Cwordend:
 645     case Cwordbound:
 646     case Cnotwordbound:
 647       {
 648         for (a = 0; a < 256; a++)
 649           fastmap[a] = 1;
 650         break;
 651       }
 652     case Csyntaxspec:
 653       {
 654         syntaxcode = code[pos++];
 655         for (a = 0; a < 256; a++)
 656           if (SYNTAX(a) & syntaxcode)
 657             fastmap[a] = 1;
 658         return 0;
 659       }
 660     case Cnotsyntaxspec:
 661       {
 662         syntaxcode = code[pos++];
 663         for (a = 0; a < 256; a++)
 664           if (!(SYNTAX(a) & syntaxcode) )
 665             fastmap[a] = 1;
 666         return 0;
 667       }
 668     case Ceol:
 669       {
 670         fastmap['\n'] = 1;
 671         if (*can_be_null == 0)
 672           *can_be_null = 2; /* can match null, but only at end of buffer*/
 673         return 0;
 674       }
 675     case Cset:
 676       {
 677         for (a = 0; a < 256/8; a++)
 678           if (code[pos + a] != 0)
 679             for (b = 0; b < 8; b++)
 680               if (code[pos + a] & (1 << b))
 681                 fastmap[(a << 3) + b] = 1;
 682         pos += 256/8;
 683         return 0;
 684       }
 685     case Cexact:
 686       {
 687         fastmap[(unsigned char)code[pos]] = 1;
 688         return 0;
 689       }
 690     case Canychar:
 691       {
 692         for (a = 0; a < 256; a++)
 693           if (a != '\n')
 694             fastmap[a] = 1;
 695         return 0;
 696       }
 697     case Cstart_memory:
 698     case Cend_memory:
 699       {
 700         pos++;
 701         break;
 702       }
 703     case Cmatch_memory:
 704       {
 705         for (a = 0; a < 256; a++)
 706           fastmap[a] = 1;
 707         *can_be_null = 1;
 708         return 0;
 709       }
 710     case Cjump:
 711     case Cdummy_failure_jump:
 712     case Cupdate_failure_jump:
 713     case Cstar_jump:
 714       {
 715         a = (unsigned char)code[pos++];
 716         a |= (unsigned char)code[pos++] << 8;
 717         pos += (int)SHORT(a);
 718         if (visited[pos])
 719           {
 720             /* argh... the regexp contains empty loops.  This is not
 721                good, as this may cause a failure stack overflow when
 722                matching.  Oh well. */
 723             /* this path leads nowhere; pursue other paths. */
 724             return 0;
 725           }
 726         visited[pos] = 1;
 727         break;
 728       }
 729     case Cfailure_jump:
 730       {
 731         a = (unsigned char)code[pos++];
 732         a |= (unsigned char)code[pos++] << 8;
 733         a = pos + (int)SHORT(a);
 734         return silc_re_compile_fastmap_aux(code, a, visited,
 735                                            can_be_null, fastmap);
 736       }
 737     case Crepeat1:
 738       {
 739         pos += 2;
 740         break;
 741       }
 742     default:
 743       {
 744         silc_set_errno(SILC_ERR_REGEX_OPCODE);
 745         return -1;
 746         /*NOTREACHED*/
 747       }
 748     }
 749 }
 750
 751 static int silc_re_do_compile_fastmap(unsigned char *buffer, int used, int pos,
 752                                       unsigned char *can_be_null,
 753                                       unsigned char *fastmap, SilcRegex bufp)
 754 {
 755   unsigned char small_visited[512], *visited;
 756   int ret;
 757
 758   if (used <= sizeof(small_visited))
 759     visited = small_visited;
 760   else
 761     {
 762       silc_stack_push(bufp->rstack, NULL);
 763       visited = silc_smalloc(bufp->rstack, used);
 764       if (!visited) {
 765         silc_stack_pop(bufp->rstack);
 766         return 0;
 767       }
 768     }
 769   *can_be_null = 0;
 770   memset(fastmap, 0, 256);
 771   memset(visited, 0, used);
 772   ret = silc_re_compile_fastmap_aux(buffer, pos, visited,
 773                                     can_be_null, fastmap);
 774   if (visited != small_visited) {
 775     silc_sfree(bufp->rstack, visited);
 776     silc_stack_pop(bufp->rstack);
 777   }
 778   return ret == 0;
 779 }
 780
 781 int silc_re_compile_fastmap(SilcRegex bufp)
 782 {
 783   if (!bufp->fastmap || bufp->fastmap_accurate)
 784     return 0;
 785   SILC_ASSERT(bufp->used > 0);
 786   if (!silc_re_do_compile_fastmap(bufp->buffer,
 787                                   bufp->used,
 788                                   0,
 789                                   &bufp->can_be_null,
 790                                   bufp->fastmap, bufp))
 791     return -1;
 792   if (bufp->buffer[0] == Cbol)
 793     bufp->anchor = 1;   /* begline */
 794   else {
 795     if (bufp->buffer[0] == Cbegbuf)
 796       bufp->anchor = 2; /* begbuf */
 797     else
 798       bufp->anchor = 0; /* none */
 799   }
 800   bufp->fastmap_accurate = 1;
 801   return 0;
 802 }
 803
 804 /*
 805  * star is coded as:
 806  * 1: failure_jump 2
 807  *    ... code for operand of star
 808  *    star_jump 1
 809  * 2: ... code after star
 810  *
 811  * We change the star_jump to update_failure_jump if we can determine
 812  * that it is safe to do so; otherwise we change it to an ordinary
 813  * jump.
 814  *
 815  * plus is coded as
 816  *
 817  *    jump 2
 818  * 1: failure_jump 3
 819  * 2: ... code for operand of plus
 820  *    star_jump 1
 821  * 3: ... code after plus
 822  *
 823  * For star_jump considerations this is processed identically to star.
 824  *
 825  */
 826
 827 static int silc_re_optimize_star_jump(SilcRegex bufp, unsigned char *code)
 828 {
 829   unsigned char map[256];
 830   unsigned char can_be_null;
 831   unsigned char *p1;
 832   unsigned char *p2;
 833   unsigned char ch;
 834   int a;
 835   int b;
 836   int num_instructions = 0;
 837
 838   a = (unsigned char)*code++;
 839   a |= (unsigned char)*code++ << 8;
 840   a = (int)SHORT(a);
 841
 842   p1 = code + a + 3; /* skip the failure_jump */
 843   /* Check that the jump is within the pattern */
 844   if (p1<bufp->buffer || bufp->buffer+bufp->used<p1)
 845     {
 846       silc_set_errno(SILC_ERR_OVERFLOW);
 847       return 0;
 848     }
 849
 850   SILC_ASSERT(p1[-3] == Cfailure_jump);
 851   p2 = code;
 852   /* p1 points inside loop, p2 points to after loop */
 853   if (!silc_re_do_compile_fastmap(bufp->buffer, bufp->used,
 854                                   (int)(p2 - bufp->buffer),
 855                                   &can_be_null, map, bufp))
 856     goto make_normal_jump;
 857
 858   /* If we might introduce a new update point inside the
 859    * loop, we can't optimize because then update_jump would
 860    * update a wrong failure point.  Thus we have to be
 861    * quite careful here.
 862    */
 863
 864   /* loop until we find something that consumes a character */
 865  loop_p1:
 866   num_instructions++;
 867   switch (*p1++)
 868     {
 869     case Cbol:
 870     case Ceol:
 871     case Cbegbuf:
 872     case Cendbuf:
 873     case Cwordbeg:
 874     case Cwordend:
 875     case Cwordbound:
 876     case Cnotwordbound:
 877       {
 878         goto loop_p1;
 879       }
 880     case Cstart_memory:
 881     case Cend_memory:
 882       {
 883         p1++;
 884         goto loop_p1;
 885       }
 886     case Cexact:
 887       {
 888         ch = (unsigned char)*p1++;
 889         if (map[(int)ch])
 890           goto make_normal_jump;
 891         break;
 892       }
 893     case Canychar:
 894       {
 895         for (b = 0; b < 256; b++)
 896           if (b != '\n' && map[b])
 897             goto make_normal_jump;
 898         break;
 899       }
 900     case Cset:
 901       {
 902         for (b = 0; b < 256; b++)
 903           if ((p1[b >> 3] & (1 << (b & 7))) && map[b])
 904             goto make_normal_jump;
 905         p1 += 256/8;
 906         break;
 907       }
 908     default:
 909       {
 910         goto make_normal_jump;
 911       }
 912     }
 913   /* now we know that we can't backtrack. */
 914   while (p1 != p2 - 3)
 915     {
 916       num_instructions++;
 917       switch (*p1++)
 918         {
 919         case Cend:
 920           {
 921             return 0;
 922           }
 923         case Cbol:
 924         case Ceol:
 925         case Canychar:
 926         case Cbegbuf:
 927         case Cendbuf:
 928         case Cwordbeg:
 929         case Cwordend:
 930         case Cwordbound:
 931         case Cnotwordbound:
 932           {
 933             break;
 934           }
 935         case Cset:
 936           {
 937             p1 += 256/8;
 938             break;
 939           }
 940         case Cexact:
 941         case Cstart_memory:
 942         case Cend_memory:
 943         case Cmatch_memory:
 944         case Csyntaxspec:
 945         case Cnotsyntaxspec:
 946           {
 947             p1++;
 948             break;
 949           }
 950         case Cjump:
 951         case Cstar_jump:
 952         case Cfailure_jump:
 953         case Cupdate_failure_jump:
 954         case Cdummy_failure_jump:
 955           {
 956             goto make_normal_jump;
 957           }
 958         default:
 959           {
 960             return 0;
 961           }
 962         }
 963     }
 964
 965   /* make_update_jump: */
 966   code -= 3;
 967   a += 3;  /* jump to after the Cfailure_jump */
 968   code[0] = Cupdate_failure_jump;
 969   code[1] = a & 0xff;
 970   code[2] = a >> 8;
 971   if (num_instructions > 1)
 972     return 1;
 973   SILC_ASSERT(num_instructions == 1);
 974   /* if the only instruction matches a single character, we can do
 975    * better */
 976   p1 = code + 3 + a;   /* start of sole instruction */
 977   if (*p1 == Cset || *p1 == Cexact || *p1 == Canychar ||
 978       *p1 == Csyntaxspec || *p1 == Cnotsyntaxspec)
 979     code[0] = Crepeat1;
 980   return 1;
 981
 982  make_normal_jump:
 983   code -= 3;
 984   *code = Cjump;
 985   return 1;
 986 }
 987
 988 static int silc_re_optimize(SilcRegex bufp)
 989 {
 990   unsigned char *code;
 991
 992   code = bufp->buffer;
 993
 994   while(1)
 995     {
 996       switch (*code++)
 997         {
 998         case Cend:
 999           {
1000             return 1;
1001           }
1002         case Canychar:
1003         case Cbol:
1004         case Ceol:
1005         case Cbegbuf:
1006         case Cendbuf:
1007         case Cwordbeg:
1008         case Cwordend:
1009         case Cwordbound:
1010         case Cnotwordbound:
1011           {
1012             break;
1013           }
1014         case Cset:
1015           {
1016             code += 256/8;
1017             break;
1018           }
1019         case Cexact:
1020         case Cstart_memory:
1021         case Cend_memory:
1022         case Cmatch_memory:
1023         case Csyntaxspec:
1024         case Cnotsyntaxspec:
1025           {
1026             code++;
1027             break;
1028           }
1029         case Cstar_jump:
1030           {
1031             if (!silc_re_optimize_star_jump(bufp, code))
1032               {
1033                 return 0;
1034               }
1035             /* fall through */
1036           }
1037         case Cupdate_failure_jump:
1038         case Cjump:
1039         case Cdummy_failure_jump:
1040         case Cfailure_jump:
1041         case Crepeat1:
1042           {
1043             code += 2;
1044             break;
1045           }
1046         default:
1047           {
1048             return 0;
1049           }
1050         }
1051     }
1052 }
1053
1054 #define NEXTCHAR(var)                           \
1055   {                                             \
1056     if (pos >= size)                            \
1057       goto ends_prematurely;                    \
1058     (var) = regex[pos];                         \
1059     pos++;                                      \
1060   }
1061
1062 #define ALLOC(amount)                           \
1063   {                                             \
1064     if (pattern_offset+(amount) > alloc)        \
1065       {                                         \
1066         pattern = silc_srealloc(bufp->rstack, alloc, pattern, \
1067                                 alloc + 256 + (amount));      \
1068         alloc += 256 + (amount);                \
1069         if (!pattern)                           \
1070           goto out_of_memory;                   \
1071       }                                         \
1072   }
1073
1074 #define STORE(ch) pattern[pattern_offset++] = (ch)
1075
1076 #define CURRENT_LEVEL_START (starts[starts_base + current_level])
1077
1078 #define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset
1079
1080 #define PUSH_LEVEL_STARTS \
1081   if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \
1082     starts_base += NUM_LEVELS; \
1083   else \
1084     goto too_complex \
1085
1086 #define POP_LEVEL_STARTS starts_base -= NUM_LEVELS
1087
1088 #define PUT_ADDR(offset,addr)                   \
1089   {                                             \
1090     int disp = (addr) - (offset) - 2;           \
1091     pattern[(offset)] = disp & 0xff;            \
1092     pattern[(offset)+1] = (disp>>8) & 0xff;     \
1093   }
1094
1095 #define INSERT_JUMP(pos,type,addr)              \
1096   {                                             \
1097     int a, p = (pos), t = (type), ad = (addr);  \
1098     for (a = pattern_offset - 1; a >= p; a--)   \
1099       pattern[a + 3] = pattern[a];              \
1100     pattern[p] = t;                             \
1101     PUT_ADDR(p+1,ad);                           \
1102     pattern_offset += 3;                        \
1103   }
1104
1105 #define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7))
1106
1107 #define SET_FIELDS                              \
1108   {                                             \
1109     bufp->allocated = alloc;                    \
1110     bufp->buffer = pattern;                     \
1111     bufp->used = pattern_offset;                \
1112   }
1113
1114 #define GETHEX(var)                                     \
1115   {                                                     \
1116     unsigned char gethex_ch, gethex_value;              \
1117     NEXTCHAR(gethex_ch);                                \
1118     gethex_value = silc_hex_char_to_decimal(gethex_ch); \
1119     if (gethex_value == 16)                             \
1120       goto hex_error;                                   \
1121     NEXTCHAR(gethex_ch);                                \
1122     gethex_ch = silc_hex_char_to_decimal(gethex_ch);    \
1123     if (gethex_ch == 16)                                \
1124       goto hex_error;                                   \
1125     (var) = gethex_value * 16 + gethex_ch;              \
1126   }
1127
1128 #define ANSI_TRANSLATE(ch)                      \
1129   {                                             \
1130     switch (ch)                                 \
1131       {                                         \
1132       case 'a':                                 \
1133       case 'A':                                 \
1134         {                                       \
1135           ch = 7; /* audible bell */            \
1136           break;                                \
1137         }                                       \
1138       case 'b':                                 \
1139       case 'B':                                 \
1140         {                                       \
1141           ch = 8; /* backspace */               \
1142           break;                                \
1143         }                                       \
1144       case 'f':                                 \
1145       case 'F':                                 \
1146         {                                       \
1147           ch = 12; /* form feed */              \
1148           break;                                \
1149         }                                       \
1150       case 'n':                                 \
1151       case 'N':                                 \
1152         {                                       \
1153           ch = 10; /* line feed */              \
1154           break;                                \
1155         }                                       \
1156       case 'r':                                 \
1157       case 'R':                                 \
1158         {                                       \
1159           ch = 13; /* carriage return */        \
1160           break;                                \
1161         }                                       \
1162       case 't':                                 \
1163       case 'T':                                 \
1164         {                                       \
1165           ch = 9; /* tab */                     \
1166           break;                                \
1167         }                                       \
1168       case 'v':                                 \
1169       case 'V':                                 \
1170         {                                       \
1171           ch = 11; /* vertical tab */           \
1172           break;                                \
1173         }                                       \
1174       case 'x': /* hex code */                  \
1175       case 'X':                                 \
1176         {                                       \
1177           GETHEX(ch);                           \
1178           break;                                \
1179         }                                       \
1180       default:                                  \
1181         {                                       \
1182           /* other characters passed through */ \
1183           if (translate)                        \
1184             ch = translate[(unsigned char)ch];  \
1185           break;                                \
1186         }                                       \
1187       }                                         \
1188   }
1189
1190 SilcResult silc_re_compile_pattern(unsigned char *regex, int size,
1191                                    SilcRegex bufp)
1192 {
1193   int a;
1194   int pos;
1195   int op;
1196   int current_level;
1197   int level;
1198   int opcode;
1199   int pattern_offset = 0, alloc;
1200   int starts[NUM_LEVELS * MAX_NESTING];
1201   int starts_base;
1202   int future_jumps[MAX_NESTING];
1203   int num_jumps;
1204   unsigned char ch = '\0';
1205   unsigned char *pattern;
1206   unsigned char *translate;
1207   int next_register;
1208   int paren_depth;
1209   int num_open_registers;
1210   int open_registers[RE_NREGS];
1211   int beginning_context;
1212
1213   if (!re_compile_initialized)
1214     silc_re_compile_initialize();
1215   bufp->used = 0;
1216   bufp->fastmap_accurate = 0;
1217   bufp->uses_registers = 1;
1218   bufp->num_registers = 1;
1219   translate = bufp->translate;
1220   pattern = bufp->buffer;
1221   alloc = bufp->allocated;
1222   if (alloc == 0 || pattern == NULL)
1223     {
1224       alloc = 256;
1225       pattern = silc_smalloc(bufp->rstack, alloc);
1226       if (!pattern)
1227         goto out_of_memory;
1228     }
1229   pattern_offset = 0;
1230   starts_base = 0;
1231   num_jumps = 0;
1232   current_level = 0;
1233   SET_LEVEL_START;
1234   num_open_registers = 0;
1235   next_register = 1;
1236   paren_depth = 0;
1237   beginning_context = 1;
1238   op = -1;
1239   /* we use Rend dummy to ensure that pending jumps are updated
1240      (due to low priority of Rend) before exiting the loop. */
1241   pos = 0;
1242   while (op != Rend)
1243     {
1244       if (pos >= size)
1245         op = Rend;
1246       else
1247         {
1248           NEXTCHAR(ch);
1249           if (translate)
1250             ch = translate[(unsigned char)ch];
1251           op = regexp_plain_ops[(unsigned char)ch];
1252           if (op == Rquote)
1253             {
1254               NEXTCHAR(ch);
1255               op = regexp_quoted_ops[(unsigned char)ch];
1256               if (op == Rnormal && regexp_ansi_sequences)
1257                 ANSI_TRANSLATE(ch);
1258             }
1259         }
1260       level = regexp_precedences[op];
1261       /* printf("ch='%c' op=%d level=%d current_level=%d
1262          curlevstart=%d\n", ch, op, level, current_level,
1263          CURRENT_LEVEL_START); */
1264       if (level > current_level)
1265         {
1266           for (current_level++; current_level < level; current_level++)
1267             SET_LEVEL_START;
1268           SET_LEVEL_START;
1269         }
1270       else
1271         if (level < current_level)
1272           {
1273             current_level = level;
1274             for (;num_jumps > 0 &&
1275                    future_jumps[num_jumps-1] >= CURRENT_LEVEL_START;
1276                  num_jumps--)
1277               PUT_ADDR(future_jumps[num_jumps-1], pattern_offset);
1278           }
1279       switch (op)
1280         {
1281         case Rend:
1282           {
1283             break;
1284           }
1285         case Rnormal:
1286           {
1287           normal_char:
1288             opcode = Cexact;
1289           store_opcode_and_arg: /* opcode & ch must be set */
1290             SET_LEVEL_START;
1291             ALLOC(2);
1292             STORE(opcode);
1293             STORE(ch);
1294             break;
1295           }
1296         case Ranychar:
1297           {
1298             opcode = Canychar;
1299           store_opcode:
1300             SET_LEVEL_START;
1301             ALLOC(1);
1302             STORE(opcode);
1303             break;
1304           }
1305         case Rquote:
1306           {
1307             SILC_VERIFY(op != Rquote);
1308             /*NOTREACHED*/
1309           }
1310         case Rbol:
1311           {
1312             if (!beginning_context) {
1313               if (regexp_context_indep_ops)
1314                 goto op_error;
1315               else
1316                 goto normal_char;
1317             }
1318             opcode = Cbol;
1319             goto store_opcode;
1320           }
1321         case Reol:
1322           {
1323             if (!((pos >= size) ||
1324                   ((regexp_syntax & RE_NO_BK_VBAR) ?
1325                    (regex[pos] == '\174') :
1326                    (pos+1 < size && regex[pos] == '\134' &&
1327                     regex[pos+1] == '\174')) ||
1328                   ((regexp_syntax & RE_NO_BK_PARENS)?
1329                    (regex[pos] == ')'):
1330                    (pos+1 < size && regex[pos] == '\134' &&
1331                     regex[pos+1] == ')')))) {
1332               if (regexp_context_indep_ops)
1333                 goto op_error;
1334               else
1335                 goto normal_char;
1336             }
1337             opcode = Ceol;
1338             goto store_opcode;
1339             /* NOTREACHED */
1340             break;
1341           }
1342         case Roptional:
1343           {
1344             if (beginning_context) {
1345               if (regexp_context_indep_ops)
1346                 goto op_error;
1347               else
1348                 goto normal_char;
1349             }
1350             if (CURRENT_LEVEL_START == pattern_offset)
1351               break; /* ignore empty patterns for ? */
1352             ALLOC(3);
1353             INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1354                         pattern_offset + 3);
1355             break;
1356           }
1357         case Rstar:
1358         case Rplus:
1359           {
1360             if (beginning_context) {
1361               if (regexp_context_indep_ops)
1362                 goto op_error;
1363               else
1364                 goto normal_char;
1365             }
1366             if (CURRENT_LEVEL_START == pattern_offset)
1367               break; /* ignore empty patterns for + and * */
1368           store_jump:
1369             ALLOC(9);
1370             INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1371                         pattern_offset + 6);
1372             INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START);
1373             if (op == Rplus)  /* jump over initial failure_jump */
1374               INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump,
1375                           CURRENT_LEVEL_START + 6);
1376             break;
1377           }
1378         case Ror:
1379           {
1380             ALLOC(6);
1381             INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1382                         pattern_offset + 6);
1383             if (num_jumps >= MAX_NESTING)
1384               goto too_complex;
1385             STORE(Cjump);
1386             future_jumps[num_jumps++] = pattern_offset;
1387             STORE(0);
1388             STORE(0);
1389             SET_LEVEL_START;
1390             break;
1391           }
1392         case Ropenpar:
1393           {
1394             SET_LEVEL_START;
1395             if (next_register < RE_NREGS)
1396               {
1397                 bufp->uses_registers = 1;
1398                 ALLOC(2);
1399                 STORE(Cstart_memory);
1400                 STORE(next_register);
1401                 open_registers[num_open_registers++] = next_register;
1402                 bufp->num_registers++;
1403                 next_register++;
1404               }
1405             paren_depth++;
1406             PUSH_LEVEL_STARTS;
1407             current_level = 0;
1408             SET_LEVEL_START;
1409             break;
1410           }
1411         case Rclosepar:
1412           {
1413             if (paren_depth <= 0)
1414               goto parenthesis_error;
1415             POP_LEVEL_STARTS;
1416             current_level = regexp_precedences[Ropenpar];
1417             paren_depth--;
1418             if (paren_depth < num_open_registers)
1419               {
1420                 bufp->uses_registers = 1;
1421                 ALLOC(2);
1422                 STORE(Cend_memory);
1423                 num_open_registers--;
1424                 STORE(open_registers[num_open_registers]);
1425               }
1426             break;
1427           }
1428         case Rmemory:
1429           {
1430             if (ch == '0')
1431               goto bad_match_register;
1432             SILC_ASSERT(ch >= '0' && ch <= '9');
1433             bufp->uses_registers = 1;
1434             opcode = Cmatch_memory;
1435             ch -= '0';
1436             goto store_opcode_and_arg;
1437           }
1438         case Rextended_memory:
1439           {
1440             NEXTCHAR(ch);
1441             if (ch < '0' || ch > '9')
1442               goto bad_match_register;
1443             NEXTCHAR(a);
1444             if (a < '0' || a > '9')
1445               goto bad_match_register;
1446             ch = 10 * (a - '0') + ch - '0';
1447             if (ch == 0 || ch >= RE_NREGS)
1448               goto bad_match_register;
1449             bufp->uses_registers = 1;
1450             opcode = Cmatch_memory;
1451             goto store_opcode_and_arg;
1452           }
1453         case Ropenset:
1454           {
1455             int complement;
1456             int prev;
1457             int offset;
1458             int range;
1459             int firstchar;
1460
1461             SET_LEVEL_START;
1462             ALLOC(1+256/8);
1463             STORE(Cset);
1464             offset = pattern_offset;
1465             for (a = 0; a < 256/8; a++)
1466               STORE(0);
1467             NEXTCHAR(ch);
1468             if (translate)
1469               ch = translate[(unsigned char)ch];
1470             if (ch == '\136')
1471               {
1472                 complement = 1;
1473                 NEXTCHAR(ch);
1474                 if (translate)
1475                   ch = translate[(unsigned char)ch];
1476               }
1477             else
1478               complement = 0;
1479             prev = -1;
1480             range = 0;
1481             firstchar = 1;
1482             while (ch != '\135' || firstchar)
1483               {
1484                 firstchar = 0;
1485                 if (regexp_ansi_sequences && ch == '\134')
1486                   {
1487                     NEXTCHAR(ch);
1488                     ANSI_TRANSLATE(ch);
1489                   }
1490                 if (range)
1491                   {
1492                     for (a = prev; a <= (int)ch; a++)
1493                       SETBIT(pattern, offset, a);
1494                     prev = -1;
1495                     range = 0;
1496                   }
1497                 else
1498                   if (prev != -1 && ch == '-')
1499                     range = 1;
1500                   else
1501                     {
1502                       SETBIT(pattern, offset, ch);
1503                       prev = ch;
1504                     }
1505                 NEXTCHAR(ch);
1506                 if (translate)
1507                   ch = translate[(unsigned char)ch];
1508               }
1509             if (range)
1510               SETBIT(pattern, offset, '-');
1511             if (complement)
1512               {
1513                 for (a = 0; a < 256/8; a++)
1514                   pattern[offset+a] ^= 0xff;
1515               }
1516             break;
1517           }
1518         case Ropenrep:
1519           {
1520             /* The bounded repeat syntax: a{n}, a{n,} and a{n,m}.  The first
1521                is compiled as n-1 Rnormals.  The second is compiled as n-1
1522                Rnormals and one Rplus.  The third is compiled as n-1 Rnormals
1523                and m-n Rnormals with Roptionals.  0 values have special
1524                compilation. */
1525             int min, max, i;
1526
1527             if (pos >= size)
1528               goto normal_char;         /* Consider literal */
1529
1530             /* Get the preceding atom */
1531             if (pos < 2)
1532               goto normal_char;         /* Consider literal */
1533             pos -= 2;
1534             NEXTCHAR(a);
1535             NEXTCHAR(ch);
1536
1537             /* Get min value */
1538             NEXTCHAR(ch);
1539             if (!isdigit(ch))
1540               goto normal_char;         /* Consider literal */
1541             min = ch - '0';
1542             NEXTCHAR(ch);
1543             while (isdigit(ch)) {
1544               min *= 10;
1545               min += ch - '0';
1546               NEXTCHAR(ch);
1547             }
1548
1549             if (min > 255)
1550               goto repeat_value_error;
1551
1552             if (ch == '}') {
1553               /* The a{n} case */
1554
1555               if (!min) {
1556                 /* Will not do any matching with a{0} */
1557                 pattern_offset -= 2;
1558                 break;
1559               }
1560
1561               /* Store min - 1 many Cexacts. */
1562               for (i = 0; i < min - 1; i++) {
1563                 SET_LEVEL_START;
1564                 ALLOC(2);
1565                 STORE(Cexact);
1566                 STORE((unsigned char)a);
1567               }
1568               break;
1569             }
1570
1571             if (ch == ',') {
1572               NEXTCHAR(ch);
1573
1574               if (ch == '}') {
1575                 /* The a{n,} case */
1576
1577                 if (!min) {
1578                   /* Store Rstar with a{0,} */
1579                   op = Rstar;
1580                   goto store_jump;
1581                 }
1582
1583                 /* Store min - 1 many Cexacts. */
1584                 for (i = 0; i < min - 1; i++) {
1585                   SET_LEVEL_START;
1586                   ALLOC(2);
1587                   STORE(Cexact);
1588                   STORE((unsigned char)a);
1589                 }
1590
1591                 /* Store Rplus */
1592                 op = Rplus;
1593                 goto store_jump;
1594               }
1595
1596               /* The a{n,m} case */
1597
1598               /* Get max value */
1599               if (!isdigit(ch))
1600                 goto repeat_value_error;
1601               max = ch - '0';
1602               NEXTCHAR(ch);
1603               while (isdigit(ch)) {
1604                 max *= 10;
1605                 max += ch - '0';
1606                 NEXTCHAR(ch);
1607               }
1608
1609               if (max > 255)
1610                 goto repeat_value_error;
1611               if (min > max)
1612                 goto repeat_value_error;
1613
1614               if (!min && !max) {
1615                 /* Will not do any matching with a{0,0} */
1616                 pattern_offset -= 2;
1617                 break;
1618               }
1619
1620               if (ch != '}')
1621                 goto op_error;
1622
1623               if (!min)
1624                 /* Only optional matching with a{0,m}. */
1625                 pattern_offset -= 2;
1626
1627               /* Store min - 1 many Cexacts. */
1628               for (i = 0; min && i < min - 1; i++) {
1629                 SET_LEVEL_START;
1630                 ALLOC(2);
1631                 STORE(Cexact);
1632                 STORE((unsigned char)a);
1633               }
1634
1635               /* Store max - min Cexacts and Roptionals. */
1636               for (i = 0; i < max - min; i++) {
1637                 SET_LEVEL_START;
1638                 ALLOC(2);
1639                 STORE(Cexact);
1640                 STORE((unsigned char)a);
1641                 ALLOC(3);
1642                 INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1643                             pattern_offset + 3);
1644               }
1645               break;
1646             }
1647
1648             goto op_error;
1649           }
1650         case Rbegbuf:
1651           {
1652             opcode = Cbegbuf;
1653             goto store_opcode;
1654           }
1655         case Rendbuf:
1656           {
1657             opcode = Cendbuf;
1658             goto store_opcode;
1659           }
1660         case Rwordchar:
1661           {
1662             opcode = Csyntaxspec;
1663             ch = Sword;
1664             goto store_opcode_and_arg;
1665           }
1666         case Rnotwordchar:
1667           {
1668             opcode = Cnotsyntaxspec;
1669             ch = Sword;
1670             goto store_opcode_and_arg;
1671           }
1672         case Rwordbeg:
1673           {
1674             opcode = Cwordbeg;
1675             goto store_opcode;
1676           }
1677         case Rwordend:
1678           {
1679             opcode = Cwordend;
1680             goto store_opcode;
1681           }
1682         case Rwordbound:
1683           {
1684             opcode = Cwordbound;
1685             goto store_opcode;
1686           }
1687         case Rnotwordbound:
1688           {
1689             opcode = Cnotwordbound;
1690             goto store_opcode;
1691           }
1692         default:
1693           {
1694             abort();
1695           }
1696         }
1697       beginning_context = (op == Ropenpar || op == Ror);
1698     }
1699   if (starts_base != 0)
1700     goto parenthesis_error;
1701   SILC_ASSERT(num_jumps == 0);
1702   ALLOC(1);
1703   STORE(Cend);
1704   SET_FIELDS;
1705   if (!silc_re_optimize(bufp))
1706     return SILC_ERR;
1707   return SILC_OK;
1708
1709  op_error:
1710   SET_FIELDS;
1711   return SILC_ERR_REGEX_SPECIAL;
1712
1713  bad_match_register:
1714   SET_FIELDS;
1715   return SILC_ERR_REGEX_REG;
1716
1717  hex_error:
1718   SET_FIELDS;
1719   return SILC_ERR_REGEX_HEX;
1720
1721  parenthesis_error:
1722   SET_FIELDS;
1723   return SILC_ERR_REGEX_PAREN;
1724
1725  out_of_memory:
1726   SET_FIELDS;
1727   return SILC_ERR_OUT_OF_MEMORY;
1728
1729  ends_prematurely:
1730   SET_FIELDS;
1731   return SILC_ERR_OVERFLOW;
1732
1733  too_complex:
1734   SET_FIELDS;
1735   return SILC_ERR_REGEX_TOO_COMPLEX;
1736
1737  repeat_value_error:
1738   SET_FIELDS;
1739   return SILC_ERR_REGEX_REPEAT;
1740 }
1741
1742 #undef CHARAT
1743 #undef NEXTCHAR
1744 #undef GETHEX
1745 #undef ALLOC
1746 #undef STORE
1747 #undef CURRENT_LEVEL_START
1748 #undef SET_LEVEL_START
1749 #undef PUSH_LEVEL_STARTS
1750 #undef POP_LEVEL_STARTS
1751 #undef PUT_ADDR
1752 #undef INSERT_JUMP
1753 #undef SETBIT
1754 #undef SET_FIELDS
1755
1756 #define PREFETCH if (text == textend) goto fail
1757
1758 #define NEXTCHAR(var)                           \
1759   PREFETCH;                                     \
1760   var = (unsigned char)*text++;                 \
1761   if (translate)                                \
1762     var = translate[var]
1763
1764 int silc_re_match(SilcRegex bufp, unsigned char *string, int size, int pos,
1765                   regexp_registers_t old_regs, unsigned int flags)
1766 {
1767   unsigned char *code;
1768   unsigned char *translate;
1769   unsigned char *text;
1770   unsigned char *textstart;
1771   unsigned char *textend;
1772   int a;
1773   int b;
1774   int ch;
1775   int reg;
1776   int match_end;
1777   unsigned char *regstart;
1778   unsigned char *regend;
1779   int regsize;
1780   match_state state;
1781
1782   SILC_ASSERT(pos >= 0 && size >= 0);
1783   SILC_ASSERT(pos <= size);
1784
1785   text = string + pos;
1786   textstart = string;
1787   textend = string + size;
1788
1789   code = bufp->buffer;
1790
1791   translate = bufp->translate;
1792
1793   NEW_STATE(state, bufp->num_registers);
1794
1795  continue_matching:
1796   switch (*code++)
1797     {
1798     case Cend:
1799       {
1800         match_end = text - textstart;
1801         if (old_regs)
1802           {
1803             old_regs->start[0] = pos;
1804             old_regs->end[0] = match_end;
1805             if (!bufp->uses_registers)
1806               {
1807                 for (a = 1; a < RE_NREGS; a++)
1808                   {
1809                     old_regs->start[a] = -1;
1810                     old_regs->end[a] = -1;
1811                   }
1812               }
1813             else
1814               {
1815                 for (a = 1; a < bufp->num_registers; a++)
1816                   {
1817                     if ((GET_REG_START(state, a) == NULL) ||
1818                         (GET_REG_END(state, a) == NULL))
1819                       {
1820                         old_regs->start[a] = -1;
1821                         old_regs->end[a] = -1;
1822                         continue;
1823                       }
1824                     old_regs->start[a] = GET_REG_START(state, a) - textstart;
1825                     old_regs->end[a] = GET_REG_END(state, a) - textstart;
1826                   }
1827                 for (; a < RE_NREGS; a++)
1828                   {
1829                     old_regs->start[a] = -1;
1830                     old_regs->end[a] = -1;
1831                   }
1832               }
1833           }
1834         FREE_STATE(state);
1835         return match_end - pos;
1836       }
1837     case Cbol:
1838       {
1839         if (text == textstart || text[-1] == '\n') {
1840           if (flags & RE_NOTBOL)
1841             goto fail;
1842           goto continue_matching;
1843         }
1844         goto fail;
1845       }
1846     case Ceol:
1847       {
1848         if (text == textend || *text == '\n') {
1849           if (flags & RE_NOTEOL)
1850             goto fail;
1851           goto continue_matching;
1852         }
1853         goto fail;
1854       }
1855     case Cset:
1856       {
1857         NEXTCHAR(ch);
1858         if (code[ch/8] & (1<<(ch & 7)))
1859           {
1860             code += 256/8;
1861             goto continue_matching;
1862           }
1863         goto fail;
1864       }
1865     case Cexact:
1866       {
1867         NEXTCHAR(ch);
1868         if (ch != (unsigned char)*code++)
1869           goto fail;
1870         goto continue_matching;
1871       }
1872     case Canychar:
1873       {
1874         NEXTCHAR(ch);
1875         if (ch == '\n')
1876           goto fail;
1877         goto continue_matching;
1878       }
1879     case Cstart_memory:
1880       {
1881         reg = *code++;
1882         SET_REG_START(state, reg, text, goto error);
1883         goto continue_matching;
1884       }
1885     case Cend_memory:
1886       {
1887         reg = *code++;
1888         SET_REG_END(state, reg, text, goto error);
1889         goto continue_matching;
1890       }
1891     case Cmatch_memory:
1892       {
1893         reg = *code++;
1894         regstart = GET_REG_START(state, reg);
1895         regend = GET_REG_END(state, reg);
1896         if ((regstart == NULL) || (regend == NULL))
1897           goto fail;  /* or should we just match nothing? */
1898         regsize = regend - regstart;
1899
1900         if (regsize > (textend - text))
1901           goto fail;
1902         if(translate)
1903           {
1904             for (; regstart < regend; regstart++, text++)
1905               if (translate[*regstart] != translate[*text])
1906                 goto fail;
1907           }
1908         else
1909           for (; regstart < regend; regstart++, text++)
1910             if (*regstart != *text)
1911               goto fail;
1912         goto continue_matching;
1913       }
1914     case Cupdate_failure_jump:
1915       {
1916         UPDATE_FAILURE(state, text, goto error);
1917         /* fall to next case */
1918       }
1919       /* treat Cstar_jump just like Cjump if it hasn't been optimized */
1920     case Cstar_jump:
1921     case Cjump:
1922       {
1923         a = (unsigned char)*code++;
1924         a |= (unsigned char)*code++ << 8;
1925         code += (int)SHORT(a);
1926         if (code<bufp->buffer || bufp->buffer+bufp->used<code) {
1927           silc_set_errno(SILC_ERR_OVERFLOW);
1928           FREE_STATE(state);
1929           return -2;
1930         }
1931         goto continue_matching;
1932       }
1933     case Cdummy_failure_jump:
1934       {
1935         unsigned char *failuredest;
1936
1937         a = (unsigned char)*code++;
1938         a |= (unsigned char)*code++ << 8;
1939         a = (int)SHORT(a);
1940         SILC_ASSERT(*code == Cfailure_jump);
1941         b = (unsigned char)code[1];
1942         b |= (unsigned char)code[2] << 8;
1943         failuredest = code + (int)SHORT(b) + 3;
1944         if (failuredest<bufp->buffer || bufp->buffer+bufp->used < failuredest) {
1945           silc_set_errno(SILC_ERR_OVERFLOW);
1946           FREE_STATE(state);
1947           return -2;
1948         }
1949         PUSH_FAILURE(state, failuredest, NULL, goto error);
1950         code += a;
1951         if (code<bufp->buffer || bufp->buffer+bufp->used < code) {
1952           silc_set_errno(SILC_ERR_OVERFLOW);
1953           FREE_STATE(state);
1954           return -2;
1955         }
1956         goto continue_matching;
1957       }
1958     case Cfailure_jump:
1959       {
1960         a = (unsigned char)*code++;
1961         a |= (unsigned char)*code++ << 8;
1962         a = (int)SHORT(a);
1963         if (code+a<bufp->buffer || bufp->buffer+bufp->used < code+a) {
1964           silc_set_errno(SILC_ERR_OVERFLOW);
1965           FREE_STATE(state);
1966           return -2;
1967         }
1968         PUSH_FAILURE(state, code + a, text, goto error);
1969         goto continue_matching;
1970       }
1971     case Crepeat1:
1972       {
1973         unsigned char *pinst;
1974         a = (unsigned char)*code++;
1975         a |= (unsigned char)*code++ << 8;
1976         a = (int)SHORT(a);
1977         pinst = code + a;
1978         if (pinst<bufp->buffer || bufp->buffer+bufp->used<pinst) {
1979           silc_set_errno(SILC_ERR_OVERFLOW);
1980           FREE_STATE(state);
1981           return -2;
1982         }
1983         /* pinst is sole instruction in loop, and it matches a
1984          * single character.  Since Crepeat1 was originally a
1985          * Cupdate_failure_jump, we also know that backtracking
1986          * is useless: so long as the single-character
1987          * expression matches, it must be used.  Also, in the
1988          * case of +, we've already matched one character, so +
1989          * can't fail: nothing here can cause a failure.  */
1990         switch (*pinst++)
1991           {
1992           case Cset:
1993             {
1994               if (translate)
1995                 {
1996                   while (text < textend)
1997                     {
1998                       ch = translate[(unsigned char)*text];
1999                       if (pinst[ch/8] & (1<<(ch & 7)))
2000                         text++;
2001                       else
2002                         break;
2003                     }
2004                 }
2005               else
2006                 {
2007                   while (text < textend)
2008                     {
2009                       ch = (unsigned char)*text;
2010                       if (pinst[ch/8] & (1<<(ch & 7)))
2011                         text++;
2012                       else
2013                         break;
2014                     }
2015                 }
2016               break;
2017             }
2018           case Cexact:
2019             {
2020               ch = (unsigned char)*pinst;
2021               if (translate)
2022                 {
2023                   while (text < textend &&
2024                          translate[(unsigned char)*text] == ch)
2025                     text++;
2026                 }
2027               else
2028                 {
2029                   while (text < textend && (unsigned char)*text == ch)
2030                     text++;
2031                 }
2032               break;
2033             }
2034           case Canychar:
2035             {
2036               while (text < textend && (unsigned char)*text != '\n')
2037                 text++;
2038               break;
2039             }
2040           case Csyntaxspec:
2041             {
2042               a = (unsigned char)*pinst;
2043               if (translate)
2044                 {
2045                   while (text < textend &&
2046                          (SYNTAX(translate[*text]) & a) )
2047                     text++;
2048                 }
2049               else
2050                 {
2051                   while (text < textend && (SYNTAX(*text) & a) )
2052                     text++;
2053                 }
2054               break;
2055             }
2056           case Cnotsyntaxspec:
2057             {
2058               a = (unsigned char)*pinst;
2059               if (translate)
2060                 {
2061                   while (text < textend &&
2062                          !(SYNTAX(translate[*text]) & a) )
2063                     text++;
2064                 }
2065               else
2066                 {
2067                   while (text < textend && !(SYNTAX(*text) & a) )
2068                     text++;
2069                 }
2070               break;
2071             }
2072           default:
2073             {
2074               FREE_STATE(state);
2075               silc_set_errno(SILC_ERR_REGEX_OPCODE);
2076               return -2;
2077               /*NOTREACHED*/
2078             }
2079           }
2080         /* due to the funky way + and * are compiled, the top
2081          * failure- stack entry at this point is actually a
2082          * success entry -- update it & pop it */
2083         UPDATE_FAILURE(state, text, goto error);
2084         goto fail;      /* i.e., succeed <wink/sigh> */
2085       }
2086     case Cbegbuf:
2087       {
2088         if (text == textstart)
2089           goto continue_matching;
2090         goto fail;
2091       }
2092     case Cendbuf:
2093       {
2094         if (text == textend)
2095           goto continue_matching;
2096         goto fail;
2097       }
2098     case Cwordbeg:
2099       {
2100         if (text == textend)
2101           goto fail;
2102         if (!(SYNTAX(*text) & Sword))
2103           goto fail;
2104         if (text == textstart)
2105           goto continue_matching;
2106         if (!(SYNTAX(text[-1]) & Sword))
2107           goto continue_matching;
2108         goto fail;
2109       }
2110     case Cwordend:
2111       {
2112         if (text == textstart)
2113           goto fail;
2114         if (!(SYNTAX(text[-1]) & Sword))
2115           goto fail;
2116         if (text == textend)
2117           goto continue_matching;
2118         if (!(SYNTAX(*text) & Sword))
2119           goto continue_matching;
2120         goto fail;
2121       }
2122     case Cwordbound:
2123       {
2124         /* Note: as in gnu regexp, this also matches at the
2125          * beginning and end of buffer.  */
2126
2127         if (text == textstart || text == textend)
2128           goto continue_matching;
2129         if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))
2130           goto continue_matching;
2131         goto fail;
2132       }
2133     case Cnotwordbound:
2134       {
2135         /* Note: as in gnu regexp, this never matches at the
2136          * beginning and end of buffer.  */
2137         if (text == textstart || text == textend)
2138           goto fail;
2139         if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)))
2140           goto continue_matching;
2141         goto fail;
2142       }
2143     case Csyntaxspec:
2144       {
2145         NEXTCHAR(ch);
2146         if (!(SYNTAX(ch) & (unsigned char)*code++))
2147           goto fail;
2148         goto continue_matching;
2149       }
2150     case Cnotsyntaxspec:
2151       {
2152         NEXTCHAR(ch);
2153         if (SYNTAX(ch) & (unsigned char)*code++)
2154           goto fail;
2155         goto continue_matching;
2156       }
2157     default:
2158       {
2159         FREE_STATE(state);
2160         silc_set_errno(SILC_ERR_REGEX_OPCODE);
2161         return -2;
2162         /*NOTREACHED*/
2163       }
2164     }
2165
2166   /* Using "break;" in the above switch statement is equivalent to
2167      "goto fail;" */
2168  fail:
2169   POP_FAILURE(state, code, text, goto done_matching, goto error);
2170   goto continue_matching;
2171
2172  done_matching:
2173   /*   if(translated != NULL) */
2174   /*      free(translated); */
2175   FREE_STATE(state);
2176   return -1;
2177
2178  error:
2179   /*   if (translated != NULL) */
2180   /*      free(translated); */
2181   FREE_STATE(state);
2182   return -2;
2183 }
2184
2185 #undef PREFETCH
2186 #undef NEXTCHAR
2187
2188 int silc_re_search(SilcRegex bufp, unsigned char *string, int size, int pos,
2189                    int range, regexp_registers_t regs, unsigned int flags)
2190 {
2191   unsigned char *fastmap;
2192   unsigned char *translate;
2193   unsigned char *text;
2194   unsigned char *partstart;
2195   unsigned char *partend;
2196   int dir;
2197   int ret;
2198   unsigned char anchor;
2199
2200   SILC_ASSERT(size >= 0 && pos >= 0);
2201   SILC_ASSERT(pos + range >= 0 && pos + range <= size); /* Bugfix by ylo */
2202
2203   fastmap = bufp->fastmap;
2204   translate = bufp->translate;
2205   if (fastmap && !bufp->fastmap_accurate) {
2206     if (silc_re_compile_fastmap(bufp))
2207       return -2;
2208   }
2209
2210   anchor = bufp->anchor;
2211   if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */
2212     fastmap = NULL;
2213
2214   if (range < 0)
2215     {
2216       dir = -1;
2217       range = -range;
2218     }
2219   else
2220     dir = 1;
2221
2222   if (anchor == 2) {
2223     if (pos != 0)
2224       return -1;
2225     else
2226       range = 0;
2227   }
2228
2229   for (; range >= 0; range--, pos += dir)
2230     {
2231       if (fastmap)
2232         {
2233           if (dir == 1)
2234             { /* searching forwards */
2235
2236               text = string + pos;
2237               partend = string + size;
2238               partstart = text;
2239               if (translate)
2240                 while (text != partend &&
2241                        !fastmap[(unsigned char) translate[(unsigned char)*text]])
2242                   text++;
2243               else
2244                 while (text != partend && !fastmap[(unsigned char)*text])
2245                   text++;
2246               pos += text - partstart;
2247               range -= text - partstart;
2248               if (pos == size && bufp->can_be_null == 0)
2249                 return -1;
2250             }
2251           else
2252             { /* searching backwards */
2253               text = string + pos;
2254               partstart = string + pos - range;
2255               partend = text;
2256               if (translate)
2257                 while (text != partstart &&
2258                        !fastmap[(unsigned char)
2259                                 translate[(unsigned char)*text]])
2260                   text--;
2261               else
2262                 while (text != partstart &&
2263                        !fastmap[(unsigned char)*text])
2264                   text--;
2265               pos -= partend - text;
2266               range -= partend - text;
2267             }
2268         }
2269       if (anchor == 1)
2270         { /* anchored to begline */
2271           if (pos > 0 && (string[pos - 1] != '\n'))
2272             continue;
2273         }
2274       SILC_ASSERT(pos >= 0 && pos <= size);
2275       ret = silc_re_match(bufp, string, size, pos, regs, flags);
2276       if (ret >= 0)
2277         return pos;
2278       if (ret == -2)
2279         return -2;
2280     }
2281   return -1;
2282 }
2283
2284 /****************************** SILC Regex API ******************************/
2285
2286 /* Compile regular expression */
2287
2288 SilcBool silc_regex_compile(SilcRegex regexp, const char *regex,
2289                             SilcRegexFlags flags)
2290 {
2291   SilcResult ret;
2292   int syntax = 0;
2293
2294   if (!regexp || !regex) {
2295     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2296     return FALSE;
2297   }
2298
2299   memset(regexp, 0, sizeof(*regexp));
2300
2301   /* Get global stack, if set, and create child stack. */
2302   regexp->rstack = silc_stack_get_global();
2303   if (regexp->rstack)
2304     regexp->rstack = silc_stack_alloc(512, regexp->rstack);
2305
2306   /* Set syntax */
2307   syntax |= RE_SYNTAX_POSIX;
2308   silc_re_set_syntax(syntax);
2309
2310   /* Compile */
2311   ret = silc_re_compile_pattern((char *)regex, strlen(regex), regexp);
2312   if (ret != SILC_OK)
2313     silc_set_errno(ret);
2314
2315   if (ret != SILC_OK) {
2316     silc_regex_free(regexp);
2317     regexp->rstack = NULL;
2318     regexp->buffer = NULL;
2319   }
2320
2321   return ret == SILC_OK;
2322 }
2323
2324 /* Match compiled regular expression */
2325
2326 SilcBool silc_regex_match(SilcRegex regexp, const char *string,
2327                           SilcUInt32 string_len, SilcUInt32 num_match,
2328                           SilcRegexMatch match, SilcRegexFlags flags)
2329 {
2330   struct re_registers regs;
2331   unsigned int f = 0;
2332   int ret, i;
2333
2334   if (!regexp || !string) {
2335     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2336     return FALSE;
2337   }
2338
2339   if (num_match && !match) {
2340     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2341     return FALSE;
2342   }
2343
2344   /* Internal limit for maximum number of registers */
2345   if (num_match > RE_NREGS)
2346     num_match = RE_NREGS;
2347
2348   /* Set flags */
2349   if (flags & SILC_REGEX_NOTBOL)
2350     f |= RE_NOTBOL;
2351   if (flags & SILC_REGEX_NOTEOL)
2352     f |= RE_NOTEOL;
2353
2354   /* Search */
2355   ret = silc_re_search(regexp, (char *)string, string_len, 0, string_len,
2356                        num_match ? &regs : NULL, f);
2357   if (ret < 0) {
2358     if (ret == -1)
2359       silc_set_errno(SILC_ERR_NOT_FOUND);
2360   }
2361
2362   if (ret >= 0) {
2363     /* Return matches */
2364     for (i = 0; i < num_match; i++) {
2365       match[i].start = regs.start[i];
2366       match[i].end = regs.end[i];
2367     }
2368   }
2369
2370   return ret >= 0;
2371 }
2372
2373 /* Free regex */
2374
2375 void silc_regex_free(SilcRegex regexp)
2376 {
2377   silc_sfree(regexp->rstack, regexp->buffer);
2378   silc_stack_free(regexp->rstack);
2379 }
2380
2381 /* Match string */
2382
2383 SilcBool silc_regex_va(const char *string, SilcUInt32 string_len,
2384                        const char *regex, SilcBuffer match, va_list va)
2385 {
2386   SilcRegexStruct reg;
2387   SilcRegexMatch m = NULL;
2388   SilcBuffer buf, *rets = NULL;
2389   SilcStack stack;
2390   int i, c = 0;
2391
2392   /* Compile */
2393   if (!silc_regex_compile(&reg, regex, 0))
2394     return FALSE;
2395
2396   stack = reg.rstack;
2397   silc_stack_push(stack, NULL);
2398
2399   /* Get match pointers */
2400   if (match) {
2401     rets = silc_smalloc(stack, sizeof(*rets));
2402     if (!rets) {
2403       silc_stack_pop(stack);
2404       silc_regex_free(&reg);
2405       return FALSE;
2406     }
2407     rets[c++] = match;
2408
2409     while ((buf = va_arg(va, SilcBuffer))) {
2410       rets = silc_srealloc(stack, c * sizeof(*rets),
2411                            rets, (c + 1) * sizeof(*rets));
2412       if (!rets) {
2413         silc_stack_pop(stack);
2414         silc_regex_free(&reg);
2415         return FALSE;
2416       }
2417       rets[c++] = buf;
2418     }
2419
2420     m = silc_smalloc(stack, c * sizeof(*m));
2421     if (!m) {
2422       silc_sfree(stack, rets);
2423       silc_stack_pop(stack);
2424       silc_regex_free(&reg);
2425       return FALSE;
2426     }
2427   }
2428
2429   /* Match */
2430   if (!silc_regex_match(&reg, string, string_len, c, m, 0)) {
2431     silc_sfree(stack, m);
2432     silc_sfree(stack, rets);
2433     silc_stack_pop(stack);
2434     silc_regex_free(&reg);
2435     return FALSE;
2436   }
2437
2438   /* Return matches */
2439   for (i = 0; i < c; i++) {
2440     if (m[i].start == -1)
2441       continue;
2442     silc_buffer_set(rets[i], (unsigned char *)string + m[i].start,
2443                     m[i].end - m[i].start);
2444   }
2445
2446   silc_sfree(stack, m);
2447   silc_sfree(stack, rets);
2448   silc_stack_pop(stack);
2449   silc_regex_free(&reg);
2450
2451   return TRUE;
2452 }
2453
2454 /* Match string */
2455
2456 SilcBool silc_regex(const char *string, const char *regex,
2457                     SilcBuffer match, ...)
2458 {
2459   SilcBool ret;
2460   va_list va;
2461
2462   if (!string || !regex) {
2463     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2464     return FALSE;
2465   }
2466
2467   if (match)
2468     va_start(va, match);
2469
2470   ret = silc_regex_va(string, strlen(string), regex, match, va);
2471
2472   if (match)
2473     va_end(va);
2474
2475   return ret;
2476 }
2477
2478 /* Match string */
2479
2480 SilcBool silc_regex_buffer(SilcBuffer buffer, const char *regex,
2481                            SilcBuffer match, ...)
2482 {
2483   SilcBool ret;
2484   va_list va;
2485
2486   if (!buffer || !regex) {
2487     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2488     return FALSE;
2489   }
2490
2491   if (match)
2492     va_start(va, match);
2493
2494   ret = silc_regex_va((const char *)silc_buffer_data(buffer),
2495                       silc_buffer_len(buffer), regex, match, va);
2496
2497   if (match)
2498     va_end(va);
2499
2500   return ret;
2501 }