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 = 0;
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, alen = 2;
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             if (translate)
1534               a = translate[(unsigned char)a];
1535             op = silc_regexp_plain_ops[(unsigned char)a];
1536
1537             if (op == Ranychar) {
1538               opcode = Canychar;
1539               a = 0;
1540               alen = 1;
1541             }
1542
1543             NEXTCHAR(ch);
1544
1545             /* Get min value */
1546             NEXTCHAR(ch);
1547             if (!isdigit(ch))
1548               goto normal_char;         /* Consider literal */
1549             min = ch - '0';
1550             NEXTCHAR(ch);
1551             while (isdigit(ch)) {
1552               min *= 10;
1553               min += ch - '0';
1554               NEXTCHAR(ch);
1555             }
1556
1557             if (min > 255)
1558               goto repeat_value_error;
1559
1560             if (ch == '}') {
1561               /* The a{n} case */
1562
1563               if (!min) {
1564                 /* Will not do any matching with a{0} */
1565                 pattern_offset -= 2;
1566                 break;
1567               }
1568
1569               /* Store min - 1 many Cexacts. */
1570               for (i = 0; i < min - 1; i++) {
1571                 SET_LEVEL_START;
1572                 ALLOC(alen);
1573                 STORE(opcode);
1574                 if (a)
1575                   STORE((unsigned char)a);
1576               }
1577               break;
1578             }
1579
1580             if (ch == ',') {
1581               NEXTCHAR(ch);
1582
1583               if (ch == '}') {
1584                 /* The a{n,} case */
1585
1586                 if (!min) {
1587                   /* Store Rstar with a{0,} */
1588                   op = Rstar;
1589                   goto store_jump;
1590                 }
1591
1592                 /* Store min - 1 many Cexacts. */
1593                 for (i = 0; i < min - 1; i++) {
1594                   SET_LEVEL_START;
1595                   ALLOC(alen);
1596                   STORE(opcode);
1597                   if (a)
1598                     STORE((unsigned char)a);
1599                 }
1600
1601                 /* Store Rplus */
1602                 op = Rplus;
1603                 goto store_jump;
1604               }
1605
1606               /* The a{n,m} case */
1607
1608               /* Get max value */
1609               if (!isdigit(ch))
1610                 goto repeat_value_error;
1611               max = ch - '0';
1612               NEXTCHAR(ch);
1613               while (isdigit(ch)) {
1614                 max *= 10;
1615                 max += ch - '0';
1616                 NEXTCHAR(ch);
1617               }
1618
1619               if (max > 255)
1620                 goto repeat_value_error;
1621               if (min > max)
1622                 goto repeat_value_error;
1623
1624               if (!min && !max) {
1625                 /* Will not do any matching with a{0,0} */
1626                 pattern_offset -= 2;
1627                 break;
1628               }
1629
1630               if (ch != '}')
1631                 goto op_error;
1632
1633               if (!min)
1634                 /* Only optional matching with a{0,m}. */
1635                 pattern_offset -= 2;
1636
1637               /* Store min - 1 many Cexacts. */
1638               for (i = 0; min && i < min - 1; i++) {
1639                 SET_LEVEL_START;
1640                 ALLOC(alen);
1641                 STORE(opcode);
1642                 if (a)
1643                   STORE((unsigned char)a);
1644               }
1645
1646               /* Store max - min Cexacts and Roptionals. */
1647               for (i = 0; i < max - min; i++) {
1648                 SET_LEVEL_START;
1649                 ALLOC(alen);
1650                 STORE(opcode);
1651                 if (a)
1652                   STORE((unsigned char)a);
1653                 ALLOC(3);
1654                 INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump,
1655                             pattern_offset + 3);
1656               }
1657               break;
1658             }
1659
1660             goto op_error;
1661           }
1662         case Rbegbuf:
1663           {
1664             opcode = Cbegbuf;
1665             goto store_opcode;
1666           }
1667         case Rendbuf:
1668           {
1669             opcode = Cendbuf;
1670             goto store_opcode;
1671           }
1672         case Rwordchar:
1673           {
1674             opcode = Csyntaxspec;
1675             ch = Sword;
1676             goto store_opcode_and_arg;
1677           }
1678         case Rnotwordchar:
1679           {
1680             opcode = Cnotsyntaxspec;
1681             ch = Sword;
1682             goto store_opcode_and_arg;
1683           }
1684         case Rwordbeg:
1685           {
1686             opcode = Cwordbeg;
1687             goto store_opcode;
1688           }
1689         case Rwordend:
1690           {
1691             opcode = Cwordend;
1692             goto store_opcode;
1693           }
1694         case Rwordbound:
1695           {
1696             opcode = Cwordbound;
1697             goto store_opcode;
1698           }
1699         case Rnotwordbound:
1700           {
1701             opcode = Cnotwordbound;
1702             goto store_opcode;
1703           }
1704         default:
1705           {
1706             abort();
1707           }
1708         }
1709       beginning_context = (op == Ropenpar || op == Ror);
1710     }
1711   if (starts_base != 0)
1712     goto parenthesis_error;
1713   SILC_ASSERT(num_jumps == 0);
1714   ALLOC(1);
1715   STORE(Cend);
1716   SET_FIELDS;
1717   if (!silc_re_optimize(bufp))
1718     return SILC_ERR;
1719   return SILC_OK;
1720
1721  op_error:
1722   SET_FIELDS;
1723   return SILC_ERR_REGEX_SPECIAL;
1724
1725  bad_match_register:
1726   SET_FIELDS;
1727   return SILC_ERR_REGEX_REG;
1728
1729  hex_error:
1730   SET_FIELDS;
1731   return SILC_ERR_REGEX_HEX;
1732
1733  parenthesis_error:
1734   SET_FIELDS;
1735   return SILC_ERR_REGEX_PAREN;
1736
1737  out_of_memory:
1738   SET_FIELDS;
1739   return SILC_ERR_OUT_OF_MEMORY;
1740
1741  ends_prematurely:
1742   SET_FIELDS;
1743   return SILC_ERR_OVERFLOW;
1744
1745  too_complex:
1746   SET_FIELDS;
1747   return SILC_ERR_REGEX_TOO_COMPLEX;
1748
1749  repeat_value_error:
1750   SET_FIELDS;
1751   return SILC_ERR_REGEX_REPEAT;
1752 }
1753
1754 #undef CHARAT
1755 #undef NEXTCHAR
1756 #undef GETHEX
1757 #undef ALLOC
1758 #undef STORE
1759 #undef CURRENT_LEVEL_START
1760 #undef SET_LEVEL_START
1761 #undef PUSH_LEVEL_STARTS
1762 #undef POP_LEVEL_STARTS
1763 #undef PUT_ADDR
1764 #undef INSERT_JUMP
1765 #undef SETBIT
1766 #undef SET_FIELDS
1767
1768 #define PREFETCH if (text == textend) goto fail
1769
1770 #define NEXTCHAR(var)                           \
1771   PREFETCH;                                     \
1772   var = (unsigned char)*text++;                 \
1773   if (translate)                                \
1774     var = translate[var]
1775
1776 int silc_re_match(SilcRegex bufp, unsigned char *string, int size, int pos,
1777                   regexp_registers_t old_regs, unsigned int flags)
1778 {
1779   unsigned char *code;
1780   unsigned char *translate;
1781   unsigned char *text;
1782   unsigned char *textstart;
1783   unsigned char *textend;
1784   int a;
1785   int b;
1786   int ch;
1787   int reg;
1788   int match_end;
1789   unsigned char *regstart;
1790   unsigned char *regend;
1791   int regsize;
1792   match_state state;
1793
1794   SILC_ASSERT(pos >= 0 && size >= 0);
1795   SILC_ASSERT(pos <= size);
1796
1797   text = string + pos;
1798   textstart = string;
1799   textend = string + size;
1800
1801   code = bufp->buffer;
1802
1803   translate = bufp->translate;
1804
1805   NEW_STATE(state, bufp->num_registers);
1806
1807  continue_matching:
1808   switch (*code++)
1809     {
1810     case Cend:
1811       {
1812         match_end = text - textstart;
1813         if (old_regs)
1814           {
1815             old_regs->start[0] = pos;
1816             old_regs->end[0] = match_end;
1817             if (!bufp->uses_registers)
1818               {
1819                 for (a = 1; a < RE_NREGS; a++)
1820                   {
1821                     old_regs->start[a] = -1;
1822                     old_regs->end[a] = -1;
1823                   }
1824               }
1825             else
1826               {
1827                 for (a = 1; a < bufp->num_registers; a++)
1828                   {
1829                     if ((GET_REG_START(state, a) == NULL) ||
1830                         (GET_REG_END(state, a) == NULL))
1831                       {
1832                         old_regs->start[a] = -1;
1833                         old_regs->end[a] = -1;
1834                         continue;
1835                       }
1836                     old_regs->start[a] = GET_REG_START(state, a) - textstart;
1837                     old_regs->end[a] = GET_REG_END(state, a) - textstart;
1838                   }
1839                 for (; a < RE_NREGS; a++)
1840                   {
1841                     old_regs->start[a] = -1;
1842                     old_regs->end[a] = -1;
1843                   }
1844               }
1845           }
1846         FREE_STATE(state);
1847         return match_end - pos;
1848       }
1849     case Cbol:
1850       {
1851         if (text == textstart || text[-1] == '\n') {
1852           if (flags & RE_NOTBOL)
1853             goto fail;
1854           goto continue_matching;
1855         }
1856         goto fail;
1857       }
1858     case Ceol:
1859       {
1860         if (text == textend || *text == '\n') {
1861           if (flags & RE_NOTEOL)
1862             goto fail;
1863           goto continue_matching;
1864         }
1865         goto fail;
1866       }
1867     case Cset:
1868       {
1869         NEXTCHAR(ch);
1870         if (code[ch/8] & (1<<(ch & 7)))
1871           {
1872             code += 256/8;
1873             goto continue_matching;
1874           }
1875         goto fail;
1876       }
1877     case Cexact:
1878       {
1879         NEXTCHAR(ch);
1880         if (ch != (unsigned char)*code++)
1881           goto fail;
1882         goto continue_matching;
1883       }
1884     case Canychar:
1885       {
1886         NEXTCHAR(ch);
1887         if (ch == '\n')
1888           goto fail;
1889         goto continue_matching;
1890       }
1891     case Cstart_memory:
1892       {
1893         reg = *code++;
1894         SET_REG_START(state, reg, text, goto error);
1895         goto continue_matching;
1896       }
1897     case Cend_memory:
1898       {
1899         reg = *code++;
1900         SET_REG_END(state, reg, text, goto error);
1901         goto continue_matching;
1902       }
1903     case Cmatch_memory:
1904       {
1905         reg = *code++;
1906         regstart = GET_REG_START(state, reg);
1907         regend = GET_REG_END(state, reg);
1908         if ((regstart == NULL) || (regend == NULL))
1909           goto fail;  /* or should we just match nothing? */
1910         regsize = regend - regstart;
1911
1912         if (regsize > (textend - text))
1913           goto fail;
1914         if(translate)
1915           {
1916             for (; regstart < regend; regstart++, text++)
1917               if (translate[*regstart] != translate[*text])
1918                 goto fail;
1919           }
1920         else
1921           for (; regstart < regend; regstart++, text++)
1922             if (*regstart != *text)
1923               goto fail;
1924         goto continue_matching;
1925       }
1926     case Cupdate_failure_jump:
1927       {
1928         UPDATE_FAILURE(state, text, goto error);
1929         /* fall to next case */
1930       }
1931       /* treat Cstar_jump just like Cjump if it hasn't been optimized */
1932     case Cstar_jump:
1933     case Cjump:
1934       {
1935         a = (unsigned char)*code++;
1936         a |= (unsigned char)*code++ << 8;
1937         code += (int)SHORT(a);
1938         if (code<bufp->buffer || bufp->buffer+bufp->used<code) {
1939           silc_set_errno(SILC_ERR_OVERFLOW);
1940           FREE_STATE(state);
1941           return -2;
1942         }
1943         goto continue_matching;
1944       }
1945     case Cdummy_failure_jump:
1946       {
1947         unsigned char *failuredest;
1948
1949         a = (unsigned char)*code++;
1950         a |= (unsigned char)*code++ << 8;
1951         a = (int)SHORT(a);
1952         SILC_ASSERT(*code == Cfailure_jump);
1953         b = (unsigned char)code[1];
1954         b |= (unsigned char)code[2] << 8;
1955         failuredest = code + (int)SHORT(b) + 3;
1956         if (failuredest<bufp->buffer || bufp->buffer+bufp->used < failuredest) {
1957           silc_set_errno(SILC_ERR_OVERFLOW);
1958           FREE_STATE(state);
1959           return -2;
1960         }
1961         PUSH_FAILURE(state, failuredest, NULL, goto error);
1962         code += a;
1963         if (code<bufp->buffer || bufp->buffer+bufp->used < code) {
1964           silc_set_errno(SILC_ERR_OVERFLOW);
1965           FREE_STATE(state);
1966           return -2;
1967         }
1968         goto continue_matching;
1969       }
1970     case Cfailure_jump:
1971       {
1972         a = (unsigned char)*code++;
1973         a |= (unsigned char)*code++ << 8;
1974         a = (int)SHORT(a);
1975         if (code+a<bufp->buffer || bufp->buffer+bufp->used < code+a) {
1976           silc_set_errno(SILC_ERR_OVERFLOW);
1977           FREE_STATE(state);
1978           return -2;
1979         }
1980         PUSH_FAILURE(state, code + a, text, goto error);
1981         goto continue_matching;
1982       }
1983     case Crepeat1:
1984       {
1985         unsigned char *pinst;
1986         a = (unsigned char)*code++;
1987         a |= (unsigned char)*code++ << 8;
1988         a = (int)SHORT(a);
1989         pinst = code + a;
1990         if (pinst<bufp->buffer || bufp->buffer+bufp->used<pinst) {
1991           silc_set_errno(SILC_ERR_OVERFLOW);
1992           FREE_STATE(state);
1993           return -2;
1994         }
1995         /* pinst is sole instruction in loop, and it matches a
1996          * single character.  Since Crepeat1 was originally a
1997          * Cupdate_failure_jump, we also know that backtracking
1998          * is useless: so long as the single-character
1999          * expression matches, it must be used.  Also, in the
2000          * case of +, we've already matched one character, so +
2001          * can't fail: nothing here can cause a failure.  */
2002         switch (*pinst++)
2003           {
2004           case Cset:
2005             {
2006               if (translate)
2007                 {
2008                   while (text < textend)
2009                     {
2010                       ch = translate[(unsigned char)*text];
2011                       if (pinst[ch/8] & (1<<(ch & 7)))
2012                         text++;
2013                       else
2014                         break;
2015                     }
2016                 }
2017               else
2018                 {
2019                   while (text < textend)
2020                     {
2021                       ch = (unsigned char)*text;
2022                       if (pinst[ch/8] & (1<<(ch & 7)))
2023                         text++;
2024                       else
2025                         break;
2026                     }
2027                 }
2028               break;
2029             }
2030           case Cexact:
2031             {
2032               ch = (unsigned char)*pinst;
2033               if (translate)
2034                 {
2035                   while (text < textend &&
2036                          translate[(unsigned char)*text] == ch)
2037                     text++;
2038                 }
2039               else
2040                 {
2041                   while (text < textend && (unsigned char)*text == ch)
2042                     text++;
2043                 }
2044               break;
2045             }
2046           case Canychar:
2047             {
2048               while (text < textend && (unsigned char)*text != '\n')
2049                 text++;
2050               break;
2051             }
2052           case Csyntaxspec:
2053             {
2054               a = (unsigned char)*pinst;
2055               if (translate)
2056                 {
2057                   while (text < textend &&
2058                          (SYNTAX(translate[*text]) & a) )
2059                     text++;
2060                 }
2061               else
2062                 {
2063                   while (text < textend && (SYNTAX(*text) & a) )
2064                     text++;
2065                 }
2066               break;
2067             }
2068           case Cnotsyntaxspec:
2069             {
2070               a = (unsigned char)*pinst;
2071               if (translate)
2072                 {
2073                   while (text < textend &&
2074                          !(SYNTAX(translate[*text]) & a) )
2075                     text++;
2076                 }
2077               else
2078                 {
2079                   while (text < textend && !(SYNTAX(*text) & a) )
2080                     text++;
2081                 }
2082               break;
2083             }
2084           default:
2085             {
2086               FREE_STATE(state);
2087               silc_set_errno(SILC_ERR_REGEX_OPCODE);
2088               return -2;
2089               /*NOTREACHED*/
2090             }
2091           }
2092         /* due to the funky way + and * are compiled, the top
2093          * failure- stack entry at this point is actually a
2094          * success entry -- update it & pop it */
2095         UPDATE_FAILURE(state, text, goto error);
2096         goto fail;      /* i.e., succeed <wink/sigh> */
2097       }
2098     case Cbegbuf:
2099       {
2100         if (text == textstart)
2101           goto continue_matching;
2102         goto fail;
2103       }
2104     case Cendbuf:
2105       {
2106         if (text == textend)
2107           goto continue_matching;
2108         goto fail;
2109       }
2110     case Cwordbeg:
2111       {
2112         if (text == textend)
2113           goto fail;
2114         if (!(SYNTAX(*text) & Sword))
2115           goto fail;
2116         if (text == textstart)
2117           goto continue_matching;
2118         if (!(SYNTAX(text[-1]) & Sword))
2119           goto continue_matching;
2120         goto fail;
2121       }
2122     case Cwordend:
2123       {
2124         if (text == textstart)
2125           goto fail;
2126         if (!(SYNTAX(text[-1]) & Sword))
2127           goto fail;
2128         if (text == textend)
2129           goto continue_matching;
2130         if (!(SYNTAX(*text) & Sword))
2131           goto continue_matching;
2132         goto fail;
2133       }
2134     case Cwordbound:
2135       {
2136         /* Note: as in gnu regexp, this also matches at the
2137          * beginning and end of buffer.  */
2138
2139         if (text == textstart || text == textend)
2140           goto continue_matching;
2141         if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))
2142           goto continue_matching;
2143         goto fail;
2144       }
2145     case Cnotwordbound:
2146       {
2147         /* Note: as in gnu regexp, this never matches at the
2148          * beginning and end of buffer.  */
2149         if (text == textstart || text == textend)
2150           goto fail;
2151         if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)))
2152           goto continue_matching;
2153         goto fail;
2154       }
2155     case Csyntaxspec:
2156       {
2157         NEXTCHAR(ch);
2158         if (!(SYNTAX(ch) & (unsigned char)*code++))
2159           goto fail;
2160         goto continue_matching;
2161       }
2162     case Cnotsyntaxspec:
2163       {
2164         NEXTCHAR(ch);
2165         if (SYNTAX(ch) & (unsigned char)*code++)
2166           goto fail;
2167         goto continue_matching;
2168       }
2169     default:
2170       {
2171         FREE_STATE(state);
2172         silc_set_errno(SILC_ERR_REGEX_OPCODE);
2173         return -2;
2174         /*NOTREACHED*/
2175       }
2176     }
2177
2178   /* Using "break;" in the above switch statement is equivalent to
2179      "goto fail;" */
2180  fail:
2181   POP_FAILURE(state, code, text, goto done_matching, goto error);
2182   goto continue_matching;
2183
2184  done_matching:
2185   /*   if(translated != NULL) */
2186   /*      free(translated); */
2187   FREE_STATE(state);
2188   return -1;
2189
2190  error:
2191   /*   if (translated != NULL) */
2192   /*      free(translated); */
2193   FREE_STATE(state);
2194   return -2;
2195 }
2196
2197 #undef PREFETCH
2198 #undef NEXTCHAR
2199
2200 int silc_re_search(SilcRegex bufp, unsigned char *string, int size, int pos,
2201                    int range, regexp_registers_t regs, unsigned int flags)
2202 {
2203   unsigned char *fastmap;
2204   unsigned char *translate;
2205   unsigned char *text;
2206   unsigned char *partstart;
2207   unsigned char *partend;
2208   int dir;
2209   int ret;
2210   unsigned char anchor;
2211
2212   SILC_ASSERT(size >= 0 && pos >= 0);
2213   SILC_ASSERT(pos + range >= 0 && pos + range <= size); /* Bugfix by ylo */
2214
2215   fastmap = bufp->fastmap;
2216   translate = bufp->translate;
2217   if (fastmap && !bufp->fastmap_accurate) {
2218     if (silc_re_compile_fastmap(bufp))
2219       return -2;
2220   }
2221
2222   anchor = bufp->anchor;
2223   if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */
2224     fastmap = NULL;
2225
2226   if (range < 0)
2227     {
2228       dir = -1;
2229       range = -range;
2230     }
2231   else
2232     dir = 1;
2233
2234   if (anchor == 2) {
2235     if (pos != 0)
2236       return -1;
2237     else
2238       range = 0;
2239   }
2240
2241   for (; range >= 0; range--, pos += dir)
2242     {
2243       if (fastmap)
2244         {
2245           if (dir == 1)
2246             { /* searching forwards */
2247
2248               text = string + pos;
2249               partend = string + size;
2250               partstart = text;
2251               if (translate)
2252                 while (text != partend &&
2253                        !fastmap[(unsigned char) translate[(unsigned char)*text]])
2254                   text++;
2255               else
2256                 while (text != partend && !fastmap[(unsigned char)*text])
2257                   text++;
2258               pos += text - partstart;
2259               range -= text - partstart;
2260               if (pos == size && bufp->can_be_null == 0)
2261                 return -1;
2262             }
2263           else
2264             { /* searching backwards */
2265               text = string + pos;
2266               partstart = string + pos - range;
2267               partend = text;
2268               if (translate)
2269                 while (text != partstart &&
2270                        !fastmap[(unsigned char)
2271                                 translate[(unsigned char)*text]])
2272                   text--;
2273               else
2274                 while (text != partstart &&
2275                        !fastmap[(unsigned char)*text])
2276                   text--;
2277               pos -= partend - text;
2278               range -= partend - text;
2279             }
2280         }
2281       if (anchor == 1)
2282         { /* anchored to begline */
2283           if (pos > 0 && (string[pos - 1] != '\n'))
2284             continue;
2285         }
2286       SILC_ASSERT(pos >= 0 && pos <= size);
2287       ret = silc_re_match(bufp, string, size, pos, regs, flags);
2288       if (ret >= 0)
2289         return pos;
2290       if (ret == -2)
2291         return -2;
2292     }
2293   return -1;
2294 }
2295
2296 /****************************** SILC Regex API ******************************/
2297
2298 /* Compile regular expression */
2299
2300 SilcBool silc_regex_compile(SilcRegex regexp, const char *regex,
2301                             SilcRegexFlags flags)
2302 {
2303   SilcResult ret;
2304
2305   if (!regexp || !regex) {
2306     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2307     return FALSE;
2308   }
2309
2310   memset(regexp, 0, sizeof(*regexp));
2311
2312   /* Get global stack, if set, and create child stack. */
2313   regexp->rstack = silc_stack_get_global();
2314   if (regexp->rstack)
2315     regexp->rstack = silc_stack_alloc(512, regexp->rstack);
2316
2317   /* Compile */
2318   ret = silc_re_compile_pattern((char *)regex, strlen(regex), regexp);
2319   if (ret != SILC_OK)
2320     silc_set_errno(ret);
2321
2322   if (ret != SILC_OK) {
2323     silc_regex_free(regexp);
2324     regexp->rstack = NULL;
2325     regexp->buffer = NULL;
2326   }
2327
2328   return ret == SILC_OK;
2329 }
2330
2331 /* Match compiled regular expression */
2332
2333 SilcBool silc_regex_match(SilcRegex regexp, const char *string,
2334                           SilcUInt32 string_len, SilcUInt32 num_match,
2335                           SilcRegexMatch match, SilcRegexFlags flags)
2336 {
2337   struct re_registers regs;
2338   unsigned int f = 0;
2339   int ret, i;
2340
2341   if (!regexp || !string) {
2342     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2343     return FALSE;
2344   }
2345
2346   if (num_match && !match) {
2347     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2348     return FALSE;
2349   }
2350
2351   /* Internal limit for maximum number of registers */
2352   if (num_match > RE_NREGS)
2353     num_match = RE_NREGS;
2354
2355   /* Set flags */
2356   if (flags & SILC_REGEX_NOTBOL)
2357     f |= RE_NOTBOL;
2358   if (flags & SILC_REGEX_NOTEOL)
2359     f |= RE_NOTEOL;
2360
2361   /* Search */
2362   ret = silc_re_search(regexp, (char *)string, string_len, 0, string_len,
2363                        num_match ? &regs : NULL, f);
2364   if (ret < 0) {
2365     if (ret == -1)
2366       silc_set_errno(SILC_ERR_NOT_FOUND);
2367   }
2368
2369   if (ret >= 0) {
2370     /* Return matches */
2371     for (i = 0; i < num_match; i++) {
2372       match[i].start = regs.start[i];
2373       match[i].end = regs.end[i];
2374     }
2375   }
2376
2377   return ret >= 0;
2378 }
2379
2380 /* Free regex */
2381
2382 void silc_regex_free(SilcRegex regexp)
2383 {
2384   silc_sfree(regexp->rstack, regexp->buffer);
2385   silc_stack_free(regexp->rstack);
2386 }
2387
2388 /* Match string */
2389
2390 SilcBool silc_regex_va(const char *string, SilcUInt32 string_len,
2391                        const char *regex, SilcBuffer match, va_list va)
2392 {
2393   SilcRegexStruct reg;
2394   SilcRegexMatch m = NULL;
2395   SilcBuffer buf, *rets = NULL;
2396   SilcStack stack;
2397   int i, c = 0;
2398
2399   /* Compile */
2400   if (!silc_regex_compile(&reg, regex, 0))
2401     return FALSE;
2402
2403   stack = reg.rstack;
2404   silc_stack_push(stack, NULL);
2405
2406   /* Get match pointers */
2407   if (match) {
2408     rets = silc_smalloc(stack, sizeof(*rets));
2409     if (!rets) {
2410       silc_stack_pop(stack);
2411       silc_regex_free(&reg);
2412       return FALSE;
2413     }
2414     rets[c++] = match;
2415
2416     while ((buf = va_arg(va, SilcBuffer))) {
2417       rets = silc_srealloc(stack, c * sizeof(*rets),
2418                            rets, (c + 1) * sizeof(*rets));
2419       if (!rets) {
2420         silc_stack_pop(stack);
2421         silc_regex_free(&reg);
2422         return FALSE;
2423       }
2424       rets[c++] = buf;
2425     }
2426
2427     m = silc_smalloc(stack, c * sizeof(*m));
2428     if (!m) {
2429       silc_sfree(stack, rets);
2430       silc_stack_pop(stack);
2431       silc_regex_free(&reg);
2432       return FALSE;
2433     }
2434   }
2435
2436   /* Match */
2437   if (!silc_regex_match(&reg, string, string_len, c, m, 0)) {
2438     silc_sfree(stack, m);
2439     silc_sfree(stack, rets);
2440     silc_stack_pop(stack);
2441     silc_regex_free(&reg);
2442     return FALSE;
2443   }
2444
2445   /* Return matches */
2446   for (i = 0; i < c; i++) {
2447     if (m[i].start == -1) {
2448       silc_buffer_set(rets[i], NULL, 0);
2449       continue;
2450     }
2451     silc_buffer_set(rets[i], (unsigned char *)string + m[i].start,
2452                     m[i].end - m[i].start);
2453   }
2454
2455   silc_sfree(stack, m);
2456   silc_sfree(stack, rets);
2457   silc_stack_pop(stack);
2458   silc_regex_free(&reg);
2459
2460   return TRUE;
2461 }
2462
2463 /* Match string */
2464
2465 SilcBool silc_regex(const char *string, const char *regex,
2466                     SilcBuffer match, ...)
2467 {
2468   SilcBool ret;
2469   va_list va;
2470
2471   if (!string || !regex) {
2472     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2473     return FALSE;
2474   }
2475
2476   if (match)
2477     va_start(va, match);
2478
2479   ret = silc_regex_va(string, strlen(string), regex, match, va);
2480
2481   if (match)
2482     va_end(va);
2483
2484   return ret;
2485 }
2486
2487 /* Match string */
2488
2489 SilcBool silc_regex_buffer(SilcBuffer buffer, const char *regex,
2490                            SilcBuffer match, ...)
2491 {
2492   SilcBool ret;
2493   va_list va;
2494
2495   if (!buffer || !regex) {
2496     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2497     return FALSE;
2498   }
2499
2500   if (match)
2501     va_start(va, match);
2502
2503   ret = silc_regex_va((const char *)silc_buffer_data(buffer),
2504                       silc_buffer_len(buffer), regex, match, va);
2505
2506   if (match)
2507     va_end(va);
2508
2509   return ret;
2510 }
2511
2512 /***************************** Substitution API *****************************/
2513
2514 /* Regexp to parse sed substitution command syntax */
2515 #define SILC_REGEXP_SUBST \
2516   "^(/?.+/?[^!s]|[0-9]+|\\$)?(!?s)(/)(.*[^\\])?(/)(.*[^\\])?(/)(!?.+)?"
2517
2518 /* Substitution context */
2519 typedef struct {
2520   SilcInt32 addr_number;            /* Line number to match, -1 for last line */
2521   SilcUInt32 line;                  /* Current line number */
2522   char *str_regexp;                 /* REGEXP to match */
2523   SilcBufferRegexFlags match_flags; /* Match flags */
2524   SilcBufferRegexFlags addr_flags;  /* ADDR flags */
2525   SilcBuffer rep;                   /* REPLACEMENT */
2526 } SilcSubstContext;
2527
2528 /* Function to check the ADDR match and do rest of the match and
2529    substitution. */
2530
2531 static int silc_subst_addr(SilcStack stack, SilcBuffer buffer, void *value,
2532                            void *context)
2533 {
2534   SilcSubstContext *ctx = context;
2535
2536   ctx->line++;
2537
2538   /* If NUMBER was set in ADDR, match for specific line number */
2539   if (ctx->addr_number > 0 && ctx->addr_number != ctx->line &&
2540       !(ctx->addr_flags & SILC_STR_REGEX_NOT))
2541     return 0;
2542   if (ctx->addr_number > 0 && ctx->addr_number == ctx->line &&
2543       ctx->addr_flags & SILC_STR_REGEX_NOT)
2544     return 0;
2545
2546   /* Check for last line if ADDR was '$' */
2547   if (buffer->tail != buffer->end && ctx->addr_number == -1 &&
2548       !(ctx->addr_flags & SILC_STR_REGEX_NOT))
2549     return 0;
2550   if (buffer->tail == buffer->end && ctx->addr_number == -1 &&
2551       ctx->addr_flags & SILC_STR_REGEX_NOT)
2552     return 0;
2553
2554   /* Match and replace */
2555   return silc_buffer_format(buffer,
2556                             SILC_STR_REGEX(ctx->str_regexp, ctx->match_flags),
2557                               SILC_STR_REPLACE(silc_buffer_data(ctx->rep) ?
2558                                                silc_buffer_data(ctx->rep) :
2559                                                (unsigned char *)"",
2560                                                silc_buffer_len(ctx->rep)),
2561                             SILC_STR_END, SILC_STR_END);
2562 }
2563
2564 /* Matching and substitution ala sed. */
2565
2566 SilcBool silc_subst(SilcBuffer buffer, const char *subst)
2567 {
2568   SilcSubstContext ctx;
2569   SilcBufferStruct match, addr, command, exp_start, exp, exp_end;
2570   SilcBufferStruct rep, rep_end, flags;
2571   SilcBufferRegexFlags addr_flags = 0, match_flags = 0;
2572   char *str_addr = "";
2573   int ret = -1;
2574
2575   memset(&ctx, 0, sizeof(ctx));
2576
2577   if (!buffer || !subst) {
2578     silc_set_errno(SILC_ERR_INVALID_ARGUMENT);
2579     goto out;
2580   }
2581
2582   SILC_LOG_DEBUG(("Substitution '%s'", subst));
2583
2584   /* Parse the expression syntax */
2585   if (!silc_regex(subst, SILC_REGEXP_SUBST, &match, &addr, &command,
2586                   &exp_start, &exp, &exp_end, &rep, &rep_end, &flags, NULL)) {
2587     silc_set_errno_reason(SILC_ERR_SYNTAX, "Invalid substitution expression");
2588     goto out;
2589   }
2590
2591   /* Check address syntax */
2592   if (silc_buffer_len(&addr)) {
2593     if (*silc_buffer_data(&addr) == '/') {
2594       silc_buffer_pull(&addr, 1);
2595       if (addr.tail[-1] != '/') {
2596         silc_set_errno_reason(SILC_ERR_SYNTAX,
2597                               "Invalid address syntax, missing '/'");
2598         goto out;
2599       }
2600       silc_buffer_push_tail(&addr, 1);
2601
2602       if (!silc_buffer_len(&addr)) {
2603         silc_set_errno_reason(SILC_ERR_SYNTAX,
2604                               "Invalid address syntax, missing regular "
2605                               "expression");
2606         goto out;
2607       }
2608       str_addr = silc_memdup(silc_buffer_data(&addr),
2609                              silc_buffer_len(&addr));
2610
2611     } else if (*silc_buffer_data(&addr) == '$' &&
2612                silc_buffer_len(&addr) == 1) {
2613       ctx.addr_number = -1;
2614
2615     } else if (isdigit((int)*silc_buffer_data(&addr))) {
2616       ctx.addr_number = *silc_buffer_data(&addr) - '0';
2617       silc_buffer_pull(&addr, 1);
2618       while (silc_buffer_len(&addr) &&
2619              isdigit((int)*silc_buffer_data(&addr))) {
2620         ctx.addr_number *= 10;
2621         ctx.addr_number += *silc_buffer_data(&addr) - '0';
2622         silc_buffer_pull(&addr, 1);
2623       }
2624
2625       if (silc_buffer_len(&addr)) {
2626         silc_set_errno_reason(SILC_ERR_SYNTAX,
2627                               "Invalid address syntax, not a number");
2628         goto out;
2629       }
2630
2631       if (ctx.addr_number == 0) {
2632         silc_set_errno_reason(SILC_ERR_SYNTAX,
2633                               "Invalid address syntax, line address is 0");
2634         goto out;
2635       }
2636
2637     } else {
2638       silc_set_errno_reason(SILC_ERR_SYNTAX, "Unsupported address syntax");
2639       goto out;
2640     }
2641   }
2642
2643   /* Check command syntax */
2644   if (!silc_buffer_len(&command) || silc_buffer_len(&command) > 2) {
2645     silc_set_errno_reason(SILC_ERR_SYNTAX, "Invalid commmand");
2646     goto out;
2647   }
2648   if ((silc_buffer_len(&command) == 1 &&
2649        !silc_buffer_memcmp(&command, "s", 1)) ||
2650       (silc_buffer_len(&command) == 2 &&
2651        !silc_buffer_memcmp(&command, "!s", 2))) {
2652     silc_set_errno_reason(SILC_ERR_SYNTAX, "Invalid command");
2653     goto out;
2654   }
2655   if (silc_buffer_len(&command) == 2)
2656     addr_flags |= SILC_STR_REGEX_NOT;
2657
2658   /* Check REGEXP syntax */
2659   if (!silc_buffer_len(&exp_start) ||
2660       !silc_buffer_memcmp(&exp_start, "/", 1)) {
2661     silc_set_errno_reason(SILC_ERR_SYNTAX,
2662                           "Invalid substitution syntax, missing '/'");
2663     goto out;
2664   }
2665   if (!silc_buffer_len(&exp_end) ||
2666       !silc_buffer_memcmp(&exp_end, "/", 1)) {
2667     silc_set_errno_reason(SILC_ERR_SYNTAX,
2668                           "Invalid substitution syntax, missing '/'");
2669     goto out;
2670   }
2671
2672   /* Check FLAGS syntax */
2673   if (silc_buffer_len(&flags)) {
2674     if (silc_buffer_len(&flags) > 1) {
2675       silc_set_errno_reason(SILC_ERR_SYNTAX, "Invalid flags");
2676       goto out;
2677     }
2678
2679     /* Check supported flags */
2680     if (silc_buffer_len(&flags) == 1) {
2681       if (silc_buffer_memcmp(&flags, "g", 1)) {
2682         match_flags |= SILC_STR_REGEX_ALL;
2683       } else {
2684         silc_set_errno_reason(SILC_ERR_SYNTAX, "Unsupported flag");
2685         goto out;
2686       }
2687     }
2688   }
2689
2690   /* Set flags */
2691   match_flags |= SILC_STR_REGEX_INCLUSIVE;
2692   addr_flags |= SILC_STR_REGEX_NL | SILC_STR_REGEX_NO_ADVANCE;
2693
2694   ctx.str_regexp = silc_memdup(silc_buffer_data(&exp),
2695                                silc_buffer_len(&exp));
2696   ctx.addr_flags = addr_flags;
2697   ctx.match_flags = match_flags;
2698
2699   /* Unescape escapes from REPLACEMENT */
2700   ctx.rep = silc_buffer_copy(&rep);
2701   if (!ctx.rep)
2702     goto out;
2703   if (silc_buffer_len(ctx.rep))
2704     silc_buffer_format(ctx.rep,
2705                        SILC_STR_REGEX("\\\\/", (SILC_STR_REGEX_ALL |
2706                                                 SILC_STR_REGEX_INCLUSIVE)),
2707                          SILC_STR_REPLACE("/", 1),
2708                        SILC_STR_END, SILC_STR_END);
2709
2710   /* If NUMBER or $ is specified, handle NOT flag in the silc_subst_addr */
2711   if (ctx.addr_number)
2712     addr_flags &= ~SILC_STR_REGEX_NOT;
2713
2714   SILC_LOG_DEBUG(("ADDR '%s' flags 0x%x, NUMBER %d", str_addr, addr_flags,
2715                   ctx.addr_number));
2716   SILC_LOG_DEBUG(("REGEXP '%s' flags 0x%x", ctx.str_regexp, match_flags));
2717
2718   /* Match and replace */
2719   ret = silc_buffer_format(buffer,
2720                            SILC_STR_REGEX(str_addr, addr_flags),
2721                              SILC_STR_FUNC(silc_subst_addr, NULL, &ctx),
2722                            SILC_STR_END, SILC_STR_END);
2723
2724  out:
2725   if (str_addr && strlen(str_addr))
2726     silc_free(str_addr);
2727   silc_free(ctx.str_regexp);
2728   silc_buffer_free(ctx.rep);
2729
2730   return ret >= 0 ? TRUE : FALSE;
2731 }