开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Internet/网络编程 > 代理服务器 > 查看源码
regex.c
资源名称：socks5.zip　[点击查看]
上传用户：sddyfurun
上传日期：2007-01-04
资源大小：525k
文件大小：17k
源码类别：

代理服务器

开发平台：

Unix_Linux

regex.c：源码内容
  1. #include <pmachine.h>
  3. #ifndef HAVE_RE_COMP
  4. /*
  5.  * These routines are BSD regex(3)/ed(1) compatible regular-expression
  6.  * routines written by Ozan S. Yigit, Computer Science, York University.
  7.  * Parts of the code that are not needed by Prospero have been removed,
  8.  * but most of the accompanying information has been left intact. 
  9.  * This file is to be included on those operating systems that do not
  10.  * support re_comp and re_exec.
  11.  */
  13. /*
  14.  * regex - Regular expression pattern matching
  15.  *         and replacement
  16.  *
  17.  * by:  Ozan S. Yigit (oz@nexus.yorku.ca)
  18.  * Dept. of Computing Services
  19.  *      York University
  20.  *
  21.  * These routines are the PUBLIC DOMAIN equivalents 
  22.  * of regex routines as found in 4.nBSD UN*X, with minor
  23.  * extensions.
  24.  *
  25.  * Modification history:
  26.  *
  27.  * $Log: regex.c,v $
  28.  * Revision 1.4  1996/04/25 20:06:29  blob
  29.  * Added const's so that it will compile on OSs that have const in the prototype in
  30.  * unistd.h
  31.  *
  32.  * Revision 1.3  1996/04/11  06:52:27  blob
  33.  * *** empty log message ***
  34.  *
  35.  * Revision 1.2  1996/04/11  06:51:34  blob
  36.  * Cleaned up warnings...
  37.  *
  38.  * Revision 1.1.1.2  1996/03/14  22:06:31  blob
  39.  * Try 1000000...
  40.  *
  41.  * Revision 1.1.1.1  1996/03/13  20:34:40  blob
  42.  * Initial Socks5 Beta import.
  43.  *
  44.  * Revision 1.1  1991/11/20  02:32:13  brendan
  45.  * entered into RCS
  46.  *
  47.  * Revision 1.1  1991/11/20  02:32:13  brendan
  48.  * entered into RCS
  49.  *
  50.  * Revision 1.3  89/04/01  14:18:09  oz
  51.  * Change all references to a dfa: this is actually an nfa.
  52.  * 
  53.  * Revision 1.2  88/08/28  15:36:04  oz
  54.  * Use a complement bitmap to represent NCL.
  55.  * This removes the need to have seperate 
  56.  * code in the pmatch case block - it is 
  57.  * just CCL code now.
  58.  * 
  59.  * Use the actual CCL code in the CLO
  60.  * section of pmatch. No need for a recursive
  61.  * pmatch call.
  62.  * 
  63.  * Use a bitmap table to set char bits in an
  64.  * 8-bit chunk.
  65.  * 
  66.  * Routines:
  67.  *      re_comp:        compile a regular expression into
  68.  *                      a NFA.
  69.  *
  70.  * char *re_comp(s)
  71.  * char *s;
  72.  *
  73.  *      re_exec:        execute the NFA to match a pattern.
  74.  *
  75.  * int re_exec(s)
  76.  * char *s;
  77.  *
  78.  * Regular Expressions:
  79.  *
  80.  *      [1]     char    matches itself, unless it is a special
  81.  *                      character (metachar): .  [ ] * + ^ $
  82.  *
  83.  *      [2]     .       matches any character.
  84.  *
  85.  *      [3]            matches the character following it, except
  86.  * when followed by a left or right round bracket,
  87.  * a digit 1 to 9 or a left or right angle bracket. 
  88.  * (see [7], [8] and [9])
  89.  * It is used as an escape character for all 
  90.  * other meta-characters, and itself. When used
  91.  * in a set ([4]), it is treated as an ordinary
  92.  * character.
  93.  *
  94.  *      [4]     [set]   matches one of the characters in the set.
  95.  *                      If the first character in the set is "^",
  96.  *                      it matches a character NOT in the set, i.e. 
  97.  * complements the set. A shorthand S-E is 
  98.  * used to specify a set of characters S upto 
  99.  * E, inclusive. The special characters "]" and 
  100.  * "-" have no special meaning if they appear 
  101.  * as the first chars in the set.
  102.  *                      examples:        match:
  103.  *
  104.  *                              [a-z]    any lowercase alpha
  105.  *
  106.  *                              [^]-]    any char except ] and -
  107.  *
  108.  *                              [^A-Z]   any char except uppercase
  109.  *                                       alpha
  110.  *
  111.  *                              [a-zA-Z] any alpha
  112.  *
  113.  *      [5]     *       any regular expression form [1] to [4], followed by
  114.  *                      closure char (*) matches zero or more matches of
  115.  *                      that form.
  116.  *
  117.  *      [6]     +       same as [5], except it matches one or more.
  118.  *
  119.  *      [7]             a regular expression in the form [1] to [10], enclosed
  120.  *                      as (form) matches what form matches. The enclosure
  121.  *                      creates a set of tags, used for [8] and for
  122.  *                      pattern substution. The tagged forms are numbered
  123.  * starting from 1.
  124.  *
  125.  *      [8]             a  followed by a digit 1 to 9 matches whatever a
  126.  *                      previously tagged regular expression ([7]) matched.
  127.  *
  128.  * [9] < a regular expression starting with a < construct
  129.  * > and/or ending with a > construct, restricts the
  130.  * pattern matching to the beginning of a word, and/or
  131.  * the end of a word. A word is defined to be a character
  132.  * string beginning and/or ending with the characters
  133.  * A-Z a-z 0-9 and _. It must also be preceded and/or
  134.  * followed by any character outside those mentioned.
  135.  *
  136.  *      [10]            a composite regular expression xy where x and y
  137.  *                      are in the form [1] to [10] matches the longest
  138.  *                      match of x followed by a match for y.
  139.  *
  140.  *      [11] ^ a regular expression starting with a ^ character
  141.  * $ and/or ending with a $ character, restricts the
  142.  *                      pattern matching to the beginning of the line,
  143.  *                      or the end of line. [anchors] Elsewhere in the
  144.  * pattern, ^ and $ are treated as ordinary characters.
  145.  *
  146.  *
  147.  * Acknowledgements:
  148.  *
  149.  * HCR's Hugh Redelmeier has been most helpful in various
  150.  * stages of development. He convinced me to include BOW
  151.  * and EOW constructs, originally invented by Rob Pike at
  152.  * the University of Toronto.
  153.  *
  154.  * References:
  155.  *              Software tools Kernighan & Plauger
  156.  *              Software tools in Pascal        Kernighan & Plauger
  157.  *              Grep [rsx-11 C dist]            David Conroy
  158.  * ed - text editor Un*x Programmer's Manual
  159.  * Advanced editing on Un*x B. W. Kernighan
  160.  * regexp routines Henry Spencer
  161.  *
  162.  * Notes:
  163.  *
  164.  * This implementation uses a bit-set representation for character
  165.  * classes for speed and compactness. Each character is represented 
  166.  * by one bit in a 128-bit block. Thus, CCL always takes a 
  167.  * constant 16 bytes in the internal nfa, and re_exec does a single
  168.  * bit comparison to locate the character in the set.
  169.  *
  170.  * Examples:
  171.  *
  172.  * pattern: foo*.*
  173.  * compile: CHR f CHR o CLO CHR o END CLO ANY END END
  174.  * matches: fo foo fooo foobar fobar foxx ...
  175.  *
  176.  * pattern: fo[ob]a[rz]
  177.  * compile: CHR f CHR o CCL bitset CHR a CCL bitset END
  178.  * matches: fobar fooar fobaz fooaz
  179.  *
  180.  * pattern: foo\+
  181.  * compile: CHR f CHR o CHR o CHR  CLO CHR  END END
  182.  * matches: foo foo\ foo\  ...
  183.  *
  184.  * pattern: (foo)[1-3]1 (same as foo[1-3]foo)
  185.  * compile: BOT 1 CHR f CHR o CHR o EOT 1 CCL bitset REF 1 END
  186.  * matches: foo1foo foo2foo foo3foo
  187.  *
  188.  * pattern: (fo.*)-1
  189.  * compile: BOT 1 CHR f CHR o CLO ANY END EOT 1 CHR - REF 1 END
  190.  * matches: foo-foo fo-fo fob-fob foobar-foobar ...
  191.  * 
  192.  */
  194. #define MAXNFA  1024
  195. #define MAXTAG  10
  197. #define OKP     1
  198. #define NOP     0
  200. #define CHR     1
  201. #define ANY     2
  202. #define CCL     3
  203. #define BOL     4
  204. #define EOL     5
  205. #define BOT     6
  206. #define EOT     7
  207. #define BOW 8
  208. #define EOW 9
  209. #define REF     10
  210. #define CLO     11
  212. #define END     0
  214. /*
  215.  * The following defines are not meant
  216.  * to be changeable. They are for readability
  217.  * only.
  218.  *
  219.  */
  220. #define MAXCHR 128
  221. #define CHRBIT 8
  222. #define BITBLK MAXCHR/CHRBIT
  223. #define BLKIND 0170
  224. #define BITIND 07
  226. #define ASCIIB 0177
  228. typedef /*unsigned*/ char CHAR;
  230. static int  tagstk[MAXTAG];             /* subpat tag stack..*/
  231. static CHAR nfa[MAXNFA]; /* automaton..       */
  232. static int  sta = NOP;                /* status of lastpat */
  234. static CHAR bittab[BITBLK]; /* bit table for CCL */
  235. /* pre-set bits...   */
  236. static CHAR bitarr[] = {1,2,4,8,16,32,64,128};
  238. static int internal_error;
  240. static void
  241. chset(c)
  242. register CHAR c;
  243. {
  244. bittab[((c) & BLKIND) >> 3] |= bitarr[(c) & BITIND];
  245. }
  247. #define badpat(x) return (*nfa = END, x)
  248. #define store(x) *mp++ = x
  249.  
  250. char *   
  251. re_comp(pat)
  252. const char *pat;
  253. {
  254. register const char *p;               /* pattern pointer   */
  255. register CHAR *mp = nfa;        /* nfa pointer       */
  256. register CHAR *lp;              /* saved pointer..   */
  257. register CHAR *sp = nfa;        /* another one..     */
  259. register int tagi = 0;          /* tag stack index   */
  260. register int tagc = 1;          /* actual tag count  */
  262. register int n;
  263. register CHAR mask; /* xor mask -CCL/NCL */
  264. int c1, c2;
  266. if (!pat || !*pat)
  267. if (sta)
  268. return 0;
  269. else
  270. badpat("No previous regular expression");
  271. sta = NOP;
  273. for (p = pat; *p; p++) {
  274. lp = mp;
  275. switch(*p) {
  277. case '.':               /* match any char..  */
  278. store(ANY);
  279. break;
  281. case '^':               /* match beginning.. */
  282. if (p == pat)
  283. store(BOL);
  284. else {
  285. store(CHR);
  286. store(*p);
  287. }
  288. break;
  290. case '$':               /* match endofline.. */
  291. if (!*(p+1))
  292. store(EOL);
  293. else {
  294. store(CHR);
  295. store(*p);
  296. }
  297. break;
  299. case '[':               /* match char class..*/
  300. store(CCL);
  302. if (*++p == '^') {
  303. mask = 0377;
  304. p++;
  305. }
  306. else
  307. mask = 0;
  309. if (*p == '-') /* real dash */
  310. chset(*p++);
  311. if (*p == ']') /* real brac */
  312. chset(*p++);
  313. while (*p && *p != ']') {
  314. if (*p == '-' && *(p+1) && *(p+1) != ']') {
  315. p++;
  316. c1 = *(p-2) + 1;
  317. c2 = *p++;
  318. while (c1 <= c2)
  319. chset(c1++);
  320. }
  321. #ifdef EXTEND
  322. else if (*p == '\' && *(p+1)) {
  323. p++;
  324. chset(*p++);
  325. }
  326. #endif
  327. else
  328. chset(*p++);
  329. }
  330. if (!*p)
  331. badpat("Missing ]");
  333. for (n = 0; n < BITBLK; bittab[n++] = (char) 0)
  334. store(mask ^ bittab[n]);
  336. break;
  338. case '*':               /* match 0 or more.. */
  339. case '+':               /* match 1 or more.. */
  340. if (p == pat)
  341. badpat("Empty closure");
  342. lp = sp; /* previous opcode */
  343. if (*lp == CLO) /* equivalence..   */
  344. break;
  345. switch(*lp) {
  347. case BOL:
  348. case BOT:
  349. case EOT:
  350. case BOW:
  351. case EOW:
  352. case REF:
  353. badpat("Illegal closure");
  354. default:
  355. break;
  356. }
  358. if (*p == '+')
  359. for (sp = mp; lp < sp; lp++)
  360. store(*lp);
  362. store(END);
  363. store(END);
  364. sp = mp;
  365. while (--mp > lp)
  366. *mp = mp[-1];
  367. store(CLO);
  368. mp = sp;
  369. break;
  371. case '\':              /* tags, backrefs .. */
  372. switch(*++p) {
  374. case '(':
  375. if (tagc < MAXTAG) {
  376. tagstk[++tagi] = tagc;
  377. store(BOT);
  378. store(tagc++);
  379. }
  380. else
  381. badpat("Too many \(\) pairs");
  382. break;
  383. case ')':
  384. if (*sp == BOT)
  385. badpat("Null pattern inside \(\)");
  386. if (tagi > 0) {
  387. store(EOT);
  388. store(tagstk[tagi--]);
  389. }
  390. else
  391. badpat("Unmatched \)");
  392. break;
  393. case '<':
  394. store(BOW);
  395. break;
  396. case '>':
  397. if (*sp == BOW)
  398. badpat("Null pattern inside \<\>");
  399. store(EOW);
  400. break;
  401. case '1':
  402. case '2':
  403. case '3':
  404. case '4':
  405. case '5':
  406. case '6':
  407. case '7':
  408. case '8':
  409. case '9':
  410. n = *p-'0';
  411. if (tagi > 0 && tagstk[tagi] == n)
  412. badpat("Cyclical reference");
  413. if (tagc > n) {
  414. store(REF);
  415. store(n);
  416. }
  417. else
  418. badpat("Undetermined reference");
  419. break;
  420. #ifdef EXTEND
  421. case 'b':
  422. store(CHR);
  423. store('b');
  424. break;
  425. case 'n':
  426. store(CHR);
  427. store('n');
  428. break;
  429. case 'f':
  430. store(CHR);
  431. store('f');
  432. break;
  433. case 'r':
  434. store(CHR);
  435. store('r');
  436. break;
  437. case 't':
  438. store(CHR);
  439. store('t');
  440. break;
  441. #endif
  442. default:
  443. store(CHR);
  444. store(*p);
  445. }
  446. break;
  448. default :               /* an ordinary char  */
  449. store(CHR);
  450. store(*p);
  451. break;
  452. }
  453. sp = lp;
  454. }
  455. if (tagi > 0)
  456. badpat("Unmatched \(");
  457. store(END);
  458. sta = OKP;
  459. return 0;
  460. }
  463. static const char *bol;
  464. static const char *bopat[MAXTAG];
  465. static const char *eopat[MAXTAG];
  466. static const char *pmatch P((const char *, CHAR *));
  468. /*
  469.  * re_exec:
  470.  *  execute nfa to find a match.
  471.  *
  472.  * special cases: (nfa[0])
  473.  * BOL
  474.  * Match only once, starting from the
  475.  * beginning.
  476.  * CHR
  477.  * First locate the character without
  478.  * calling pmatch, and if found, call
  479.  * pmatch for the remaining string.
  480.  * END
  481.  * re_comp failed, poor luser did not
  482.  * check for it. Fail fast.
  483.  *
  484.  * If a match is found, bopat[0] and eopat[0] are set
  485.  * to the beginning and the end of the matched fragment,
  486.  * respectively.
  487.  *
  488.  */
  490. int
  491. re_exec(lp)
  492. register const char *lp;
  493. {
  494. register char c;
  495. register const char *ep = 0;
  496. register CHAR *ap = nfa;
  498. bol = lp;
  500. bopat[0] = 0;
  501. bopat[1] = 0;
  502. bopat[2] = 0;
  503. bopat[3] = 0;
  504. bopat[4] = 0;
  505. bopat[5] = 0;
  506. bopat[6] = 0;
  507. bopat[7] = 0;
  508. bopat[8] = 0;
  509. bopat[9] = 0;
  511. switch(*ap) {
  513. case BOL: /* anchored: match from BOL only */
  514. ep = pmatch(lp,ap);
  515. break;
  516. case CHR: /* ordinary char: locate it fast */
  517. c = *(ap+1);
  518. while (*lp && *lp != c)
  519. lp++;
  520. if (!*lp) /* if EOS, fail, else fall thru. */
  521. return 0;
  522. default: /* regular matching all the way. */
  523. while (*lp) {
  524. if ((ep = pmatch(lp,ap)))
  525. break;
  526. lp++;
  527. }
  528. break;
  529. case END: /* munged automaton. fail always */
  530. return 0;
  531. }
  532. if (!ep)
  533. return 0;
  535. if (internal_error)
  536. return -1;
  538. bopat[0] = lp;
  539. eopat[0] = ep;
  540. return 1;
  541. }
  543. /* 
  544.  * pmatch: 
  545.  * internal routine for the hard part
  546.  *
  547.  *  This code is mostly snarfed from an early
  548.  *  grep written by David Conroy. The backref and
  549.  *  tag stuff, and various other mods are by oZ.
  550.  *
  551.  * special cases: (nfa[n], nfa[n+1])
  552.  * CLO ANY
  553.  * We KNOW ".*" will match ANYTHING
  554.  * upto the end of line. Thus, go to
  555.  * the end of line straight, without
  556.  * calling pmatch recursively. As in
  557.  * the other closure cases, the remaining
  558.  * pattern must be matched by moving
  559.  * backwards on the string recursively,
  560.  * to find a match for xy (x is ".*" and 
  561.  * y is the remaining pattern) where
  562.  * the match satisfies the LONGEST match
  563.  * for x followed by a match for y.
  564.  * CLO CHR
  565.  * We can again scan the string forward
  566.  * for the single char without recursion, 
  567.  * and at the point of failure, we execute 
  568.  * the remaining nfa recursively, as
  569.  * described above.
  570.  *
  571.  * At the end of a successful match, bopat[n] and eopat[n]
  572.  * are set to the beginning and end of subpatterns matched
  573.  * by tagged expressions (n = 1 to 9).
  574.  *
  575.  */
  577. /*
  578.  * character classification table for word boundary
  579.  * operators BOW and EOW. the reason for not using 
  580.  * ctype macros is that we can let the user add into 
  581.  * our own table. see re_modw. This table is not in
  582.  * the bitset form, since we may wish to extend it
  583.  * in the future for other character classifications. 
  584.  *
  585.  * TRUE for 0-9 A-Z a-z _
  586.  */
  587. static char chrtyp[MAXCHR] = {
  588. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  589. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  590. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  591. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
  592. 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 
  593. 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 
  594. 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 
  595. 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  596. 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  597. 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 
  598. 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  599. 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
  600. 1, 1, 1, 0, 0, 0, 0, 0
  601. };
  603. #define inascii(x) (0177&(x))
  604. #define iswordc(x)  chrtyp[inascii(x)]
  605. #define isinset(x,y)  ((x)[((y)&BLKIND)>>3] & bitarr[(y)&BITIND])
  607. /*
  608.  * skip values for CLO XXX to skip past the closure
  609.  *
  610.  */
  612. #define ANYSKIP 2  /* [CLO] ANY END ...      */
  613. #define CHRSKIP 3 /* [CLO] CHR chr END ...     */
  614. #define CCLSKIP 18 /* [CLO] CCL 16bytes END ... */
  616. static const char *
  617. pmatch(lp, ap)
  618. register const char *lp;
  619. register CHAR *ap;
  620. {
  621. register int op, c, n;
  622. register const char *e; /* extra pointer for CLO */
  623. register const char *bp; /* beginning of subpat.. */
  624. register const char *ep; /* ending of subpat..  */
  625. const char *are; /* to save the line ptr. */
  627. while ((op = *ap++) != END)
  628. switch(op) {
  630. case CHR:
  631. if (*lp++ != *ap++)
  632. return 0;
  633. break;
  634. case ANY:
  635. if (!*lp++)
  636. return 0;
  637. break;
  638. case CCL:
  639. c = *lp++;
  640. if (!isinset(ap,c))
  641. return 0;
  642. ap += BITBLK;
  643. break;
  644. case BOL:
  645. if (lp != bol)
  646. return 0;
  647. break;
  648. case EOL:
  649. if (*lp)
  650. return 0;
  651. break;
  652. case BOT:
  653. bopat[(int)(*ap++)] = lp;
  654. break;
  655. case EOT:
  656. eopat[(int)(*ap++)] = lp;
  657. break;
  658.   case BOW:
  659. if ((lp!=bol && iswordc(lp[-1])) || !iswordc(*lp))
  660. return 0;
  661. break;
  662. case EOW:
  663. if (lp==bol || !iswordc(lp[-1]) || iswordc(*lp))
  664. return 0;
  665. break;
  666. case REF:
  667. n = *ap++;
  668. bp = bopat[n];
  669. ep = eopat[n];
  670. while (bp < ep)
  671. if (*bp++ != *lp++)
  672. return 0;
  673. break;
  674. case CLO:
  675. are = lp;
  676. switch(*ap) {
  678. case ANY:
  679. while (*lp)
  680. lp++;
  681. n = ANYSKIP;
  682. break;
  683. case CHR:
  684. c = *(ap+1);
  685. while (*lp && c == *lp)
  686. lp++;
  687. n = CHRSKIP;
  688. break;
  689. case CCL:
  690. while ((c = *lp) && isinset(ap+1,c))
  691. lp++;
  692. n = CCLSKIP;
  693. break;
  694. default:
  695. internal_error++;
  696. return 0;
  697. }
  699. ap += n;
  701. while (lp >= are) {
  702.     if ((e = pmatch(lp, ap)))
  703. return e;
  704. --lp;
  705. }
  706. return 0;
  707. default:
  708. internal_error++;
  709. return 0;
  710. }
  711. return lp;
  712. }
  713. #endif /* Need regex libraries? Compile to nothing if not.  */