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