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