slre.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723
  1. /*
  2. * Copyright (c) 2004-2005 Sergey Lyubka <valenok@gmail.com>
  3. * All rights reserved
  4. *
  5. * "THE BEER-WARE LICENSE" (Revision 42):
  6. * Sergey Lyubka wrote this file. As long as you retain this notice you
  7. * can do whatever you want with this stuff. If we meet some day, and you think
  8. * this stuff is worth it, you can buy me a beer in return.
  9. */
  10. /*
  11. * Downloaded Sat Nov 5 17:43:06 CET 2011 at
  12. * http://slre.sourceforge.net/1.0/slre.c
  13. */
  14. #ifdef SLRE_TEST
  15. #include <stdio.h>
  16. #include <assert.h>
  17. #include <ctype.h>
  18. #include <stdlib.h>
  19. #include <string.h>
  20. #else
  21. #include <log.h>
  22. #include <common.h>
  23. #include <linux/ctype.h>
  24. #endif /* SLRE_TEST */
  25. #include <errno.h>
  26. #include <slre.h>
  27. enum {END, BRANCH, ANY, EXACT, ANYOF, ANYBUT, OPEN, CLOSE, BOL, EOL,
  28. STAR, PLUS, STARQ, PLUSQ, QUEST, SPACE, NONSPACE, DIGIT};
  29. #ifdef SLRE_TEST
  30. static struct {
  31. const char *name;
  32. int narg;
  33. const char *flags;
  34. } opcodes[] = {
  35. {"END", 0, ""}, /* End of code block or program */
  36. {"BRANCH", 2, "oo"}, /* Alternative operator, "|" */
  37. {"ANY", 0, ""}, /* Match any character, "." */
  38. {"EXACT", 2, "d"}, /* Match exact string */
  39. {"ANYOF", 2, "D"}, /* Match any from set, "[]" */
  40. {"ANYBUT", 2, "D"}, /* Match any but from set, "[^]"*/
  41. {"OPEN ", 1, "i"}, /* Capture start, "(" */
  42. {"CLOSE", 1, "i"}, /* Capture end, ")" */
  43. {"BOL", 0, ""}, /* Beginning of string, "^" */
  44. {"EOL", 0, ""}, /* End of string, "$" */
  45. {"STAR", 1, "o"}, /* Match zero or more times "*" */
  46. {"PLUS", 1, "o"}, /* Match one or more times, "+" */
  47. {"STARQ", 1, "o"}, /* Non-greedy STAR, "*?" */
  48. {"PLUSQ", 1, "o"}, /* Non-greedy PLUS, "+?" */
  49. {"QUEST", 1, "o"}, /* Match zero or one time, "?" */
  50. {"SPACE", 0, ""}, /* Match whitespace, "\s" */
  51. {"NONSPACE", 0, ""}, /* Match non-space, "\S" */
  52. {"DIGIT", 0, ""} /* Match digit, "\d" */
  53. };
  54. #endif /* SLRE_TEST */
  55. /*
  56. * Commands and operands are all unsigned char (1 byte long). All code offsets
  57. * are relative to current address, and positive (always point forward). Data
  58. * offsets are absolute. Commands with operands:
  59. *
  60. * BRANCH offset1 offset2
  61. * Try to match the code block that follows the BRANCH instruction
  62. * (code block ends with END). If no match, try to match code block that
  63. * starts at offset1. If either of these match, jump to offset2.
  64. *
  65. * EXACT data_offset data_length
  66. * Try to match exact string. String is recorded in data section from
  67. * data_offset, and has length data_length.
  68. *
  69. * OPEN capture_number
  70. * CLOSE capture_number
  71. * If the user have passed 'struct cap' array for captures, OPEN
  72. * records the beginning of the matched substring (cap->ptr), CLOSE
  73. * sets the length (cap->len) for respective capture_number.
  74. *
  75. * STAR code_offset
  76. * PLUS code_offset
  77. * QUEST code_offset
  78. * *, +, ?, respectively. Try to gobble as much as possible from the
  79. * matched buffer, until code block that follows these instructions
  80. * matches. When the longest possible string is matched,
  81. * jump to code_offset
  82. *
  83. * STARQ, PLUSQ are non-greedy versions of STAR and PLUS.
  84. */
  85. static const char *meta_chars = "|.^$*+?()[\\";
  86. #ifdef SLRE_TEST
  87. static void
  88. print_character_set(FILE *fp, const unsigned char *p, int len)
  89. {
  90. int i;
  91. for (i = 0; i < len; i++) {
  92. if (i > 0)
  93. (void) fputc(',', fp);
  94. if (p[i] == 0) {
  95. i++;
  96. if (p[i] == 0)
  97. (void) fprintf(fp, "\\x%02x", p[i]);
  98. else
  99. (void) fprintf(fp, "%s", opcodes[p[i]].name);
  100. } else if (isprint(p[i])) {
  101. (void) fputc(p[i], fp);
  102. } else {
  103. (void) fprintf(fp, "\\x%02x", p[i]);
  104. }
  105. }
  106. }
  107. void
  108. slre_dump(const struct slre *r, FILE *fp)
  109. {
  110. int i, j, ch, op, pc;
  111. for (pc = 0; pc < r->code_size; pc++) {
  112. op = r->code[pc];
  113. (void) fprintf(fp, "%3d %s ", pc, opcodes[op].name);
  114. for (i = 0; opcodes[op].flags[i] != '\0'; i++)
  115. switch (opcodes[op].flags[i]) {
  116. case 'i':
  117. (void) fprintf(fp, "%d ", r->code[pc + 1]);
  118. pc++;
  119. break;
  120. case 'o':
  121. (void) fprintf(fp, "%d ",
  122. pc + r->code[pc + 1] - i);
  123. pc++;
  124. break;
  125. case 'D':
  126. print_character_set(fp, r->data +
  127. r->code[pc + 1], r->code[pc + 2]);
  128. pc += 2;
  129. break;
  130. case 'd':
  131. (void) fputc('"', fp);
  132. for (j = 0; j < r->code[pc + 2]; j++) {
  133. ch = r->data[r->code[pc + 1] + j];
  134. if (isprint(ch)) {
  135. (void) fputc(ch, fp);
  136. } else {
  137. (void) fprintf(fp,
  138. "\\x%02x", ch);
  139. }
  140. }
  141. (void) fputc('"', fp);
  142. pc += 2;
  143. break;
  144. }
  145. (void) fputc('\n', fp);
  146. }
  147. }
  148. #endif /* SLRE_TEST */
  149. static void
  150. set_jump_offset(struct slre *r, int pc, int offset)
  151. {
  152. assert(offset < r->code_size);
  153. if (r->code_size - offset > 0xff)
  154. r->err_str = "Jump offset is too big";
  155. else
  156. r->code[pc] = (unsigned char) (r->code_size - offset);
  157. }
  158. static void
  159. emit(struct slre *r, int code)
  160. {
  161. if (r->code_size >= (int) (sizeof(r->code) / sizeof(r->code[0])))
  162. r->err_str = "RE is too long (code overflow)";
  163. else
  164. r->code[r->code_size++] = (unsigned char) code;
  165. }
  166. static void
  167. store_char_in_data(struct slre *r, int ch)
  168. {
  169. if (r->data_size >= (int) sizeof(r->data))
  170. r->err_str = "RE is too long (data overflow)";
  171. else
  172. r->data[r->data_size++] = ch;
  173. }
  174. static void
  175. exact(struct slre *r, const char **re)
  176. {
  177. int old_data_size = r->data_size;
  178. while (**re != '\0' && (strchr(meta_chars, **re)) == NULL)
  179. store_char_in_data(r, *(*re)++);
  180. emit(r, EXACT);
  181. emit(r, old_data_size);
  182. emit(r, r->data_size - old_data_size);
  183. }
  184. static int
  185. get_escape_char(const char **re)
  186. {
  187. int res;
  188. switch (*(*re)++) {
  189. case 'n':
  190. res = '\n';
  191. break;
  192. case 'r':
  193. res = '\r';
  194. break;
  195. case 't':
  196. res = '\t';
  197. break;
  198. case '0':
  199. res = 0;
  200. break;
  201. case 'S':
  202. res = NONSPACE << 8;
  203. break;
  204. case 's':
  205. res = SPACE << 8;
  206. break;
  207. case 'd':
  208. res = DIGIT << 8;
  209. break;
  210. default:
  211. res = (*re)[-1];
  212. break;
  213. }
  214. return res;
  215. }
  216. static void
  217. anyof(struct slre *r, const char **re)
  218. {
  219. int esc, old_data_size = r->data_size, op = ANYOF;
  220. if (**re == '^') {
  221. op = ANYBUT;
  222. (*re)++;
  223. }
  224. while (**re != '\0')
  225. switch (*(*re)++) {
  226. case ']':
  227. emit(r, op);
  228. emit(r, old_data_size);
  229. emit(r, r->data_size - old_data_size);
  230. return;
  231. /* NOTREACHED */
  232. break;
  233. case '\\':
  234. esc = get_escape_char(re);
  235. if ((esc & 0xff) == 0) {
  236. store_char_in_data(r, 0);
  237. store_char_in_data(r, esc >> 8);
  238. } else {
  239. store_char_in_data(r, esc);
  240. }
  241. break;
  242. default:
  243. store_char_in_data(r, (*re)[-1]);
  244. break;
  245. }
  246. r->err_str = "No closing ']' bracket";
  247. }
  248. static void
  249. relocate(struct slre *r, int begin, int shift)
  250. {
  251. emit(r, END);
  252. memmove(r->code + begin + shift, r->code + begin, r->code_size - begin);
  253. r->code_size += shift;
  254. }
  255. static void
  256. quantifier(struct slre *r, int prev, int op)
  257. {
  258. if (r->code[prev] == EXACT && r->code[prev + 2] > 1) {
  259. r->code[prev + 2]--;
  260. emit(r, EXACT);
  261. emit(r, r->code[prev + 1] + r->code[prev + 2]);
  262. emit(r, 1);
  263. prev = r->code_size - 3;
  264. }
  265. relocate(r, prev, 2);
  266. r->code[prev] = op;
  267. set_jump_offset(r, prev + 1, prev);
  268. }
  269. static void
  270. exact_one_char(struct slre *r, int ch)
  271. {
  272. emit(r, EXACT);
  273. emit(r, r->data_size);
  274. emit(r, 1);
  275. store_char_in_data(r, ch);
  276. }
  277. static void
  278. fixup_branch(struct slre *r, int fixup)
  279. {
  280. if (fixup > 0) {
  281. emit(r, END);
  282. set_jump_offset(r, fixup, fixup - 2);
  283. }
  284. }
  285. static void
  286. compile(struct slre *r, const char **re)
  287. {
  288. int op, esc, branch_start, last_op, fixup, cap_no, level;
  289. fixup = 0;
  290. level = r->num_caps;
  291. branch_start = last_op = r->code_size;
  292. for (;;)
  293. switch (*(*re)++) {
  294. case '\0':
  295. (*re)--;
  296. return;
  297. /* NOTREACHED */
  298. break;
  299. case '^':
  300. emit(r, BOL);
  301. break;
  302. case '$':
  303. emit(r, EOL);
  304. break;
  305. case '.':
  306. last_op = r->code_size;
  307. emit(r, ANY);
  308. break;
  309. case '[':
  310. last_op = r->code_size;
  311. anyof(r, re);
  312. break;
  313. case '\\':
  314. last_op = r->code_size;
  315. esc = get_escape_char(re);
  316. if (esc & 0xff00)
  317. emit(r, esc >> 8);
  318. else
  319. exact_one_char(r, esc);
  320. break;
  321. case '(':
  322. last_op = r->code_size;
  323. cap_no = ++r->num_caps;
  324. emit(r, OPEN);
  325. emit(r, cap_no);
  326. compile(r, re);
  327. if (*(*re)++ != ')') {
  328. r->err_str = "No closing bracket";
  329. return;
  330. }
  331. emit(r, CLOSE);
  332. emit(r, cap_no);
  333. break;
  334. case ')':
  335. (*re)--;
  336. fixup_branch(r, fixup);
  337. if (level == 0) {
  338. r->err_str = "Unbalanced brackets";
  339. return;
  340. }
  341. return;
  342. /* NOTREACHED */
  343. break;
  344. case '+':
  345. case '*':
  346. op = (*re)[-1] == '*' ? STAR : PLUS;
  347. if (**re == '?') {
  348. (*re)++;
  349. op = op == STAR ? STARQ : PLUSQ;
  350. }
  351. quantifier(r, last_op, op);
  352. break;
  353. case '?':
  354. quantifier(r, last_op, QUEST);
  355. break;
  356. case '|':
  357. fixup_branch(r, fixup);
  358. relocate(r, branch_start, 3);
  359. r->code[branch_start] = BRANCH;
  360. set_jump_offset(r, branch_start + 1, branch_start);
  361. fixup = branch_start + 2;
  362. r->code[fixup] = 0xff;
  363. break;
  364. default:
  365. (*re)--;
  366. last_op = r->code_size;
  367. exact(r, re);
  368. break;
  369. }
  370. }
  371. int
  372. slre_compile(struct slre *r, const char *re)
  373. {
  374. r->err_str = NULL;
  375. r->code_size = r->data_size = r->num_caps = r->anchored = 0;
  376. if (*re == '^')
  377. r->anchored++;
  378. emit(r, OPEN); /* This will capture what matches full RE */
  379. emit(r, 0);
  380. while (*re != '\0')
  381. compile(r, &re);
  382. if (r->code[2] == BRANCH)
  383. fixup_branch(r, 4);
  384. emit(r, CLOSE);
  385. emit(r, 0);
  386. emit(r, END);
  387. return (r->err_str == NULL ? 1 : 0);
  388. }
  389. static int match(const struct slre *, int,
  390. const char *, int, int *, struct cap *);
  391. static void
  392. loop_greedy(const struct slre *r, int pc, const char *s, int len, int *ofs)
  393. {
  394. int saved_offset, matched_offset;
  395. matched_offset = *ofs;
  396. while (match(r, pc + 2, s, len, ofs, NULL)) {
  397. saved_offset = *ofs;
  398. if (match(r, pc + r->code[pc + 1], s, len, ofs, NULL))
  399. matched_offset = saved_offset;
  400. *ofs = saved_offset;
  401. }
  402. *ofs = matched_offset;
  403. }
  404. static void
  405. loop_non_greedy(const struct slre *r, int pc, const char *s, int len, int *ofs)
  406. {
  407. int saved_offset = *ofs;
  408. while (match(r, pc + 2, s, len, ofs, NULL)) {
  409. saved_offset = *ofs;
  410. if (match(r, pc + r->code[pc + 1], s, len, ofs, NULL))
  411. break;
  412. }
  413. *ofs = saved_offset;
  414. }
  415. static int
  416. is_any_of(const unsigned char *p, int len, const char *s, int *ofs)
  417. {
  418. int i, ch;
  419. ch = s[*ofs];
  420. for (i = 0; i < len; i++)
  421. if (p[i] == ch) {
  422. (*ofs)++;
  423. return 1;
  424. }
  425. return 0;
  426. }
  427. static int
  428. is_any_but(const unsigned char *p, int len, const char *s, int *ofs)
  429. {
  430. int i, ch;
  431. ch = s[*ofs];
  432. for (i = 0; i < len; i++) {
  433. if (p[i] == ch)
  434. return 0;
  435. }
  436. (*ofs)++;
  437. return 1;
  438. }
  439. static int
  440. match(const struct slre *r, int pc, const char *s, int len,
  441. int *ofs, struct cap *caps)
  442. {
  443. int n, saved_offset, res = 1;
  444. while (res && r->code[pc] != END) {
  445. assert(pc < r->code_size);
  446. assert(pc < (int) (sizeof(r->code) / sizeof(r->code[0])));
  447. switch (r->code[pc]) {
  448. case BRANCH:
  449. saved_offset = *ofs;
  450. res = match(r, pc + 3, s, len, ofs, caps);
  451. if (res == 0) {
  452. *ofs = saved_offset;
  453. res = match(r, pc + r->code[pc + 1],
  454. s, len, ofs, caps);
  455. }
  456. pc += r->code[pc + 2];
  457. break;
  458. case EXACT:
  459. res = 0;
  460. n = r->code[pc + 2]; /* String length */
  461. if (n <= len - *ofs && !memcmp(s + *ofs, r->data +
  462. r->code[pc + 1], n)) {
  463. (*ofs) += n;
  464. res = 1;
  465. }
  466. pc += 3;
  467. break;
  468. case QUEST:
  469. res = 1;
  470. saved_offset = *ofs;
  471. if (!match(r, pc + 2, s, len, ofs, caps))
  472. *ofs = saved_offset;
  473. pc += r->code[pc + 1];
  474. break;
  475. case STAR:
  476. res = 1;
  477. loop_greedy(r, pc, s, len, ofs);
  478. pc += r->code[pc + 1];
  479. break;
  480. case STARQ:
  481. res = 1;
  482. loop_non_greedy(r, pc, s, len, ofs);
  483. pc += r->code[pc + 1];
  484. break;
  485. case PLUS:
  486. res = match(r, pc + 2, s, len, ofs, caps);
  487. if (res == 0)
  488. break;
  489. loop_greedy(r, pc, s, len, ofs);
  490. pc += r->code[pc + 1];
  491. break;
  492. case PLUSQ:
  493. res = match(r, pc + 2, s, len, ofs, caps);
  494. if (res == 0)
  495. break;
  496. loop_non_greedy(r, pc, s, len, ofs);
  497. pc += r->code[pc + 1];
  498. break;
  499. case SPACE:
  500. res = 0;
  501. if (*ofs < len && isspace(((unsigned char *)s)[*ofs])) {
  502. (*ofs)++;
  503. res = 1;
  504. }
  505. pc++;
  506. break;
  507. case NONSPACE:
  508. res = 0;
  509. if (*ofs < len &&
  510. !isspace(((unsigned char *)s)[*ofs])) {
  511. (*ofs)++;
  512. res = 1;
  513. }
  514. pc++;
  515. break;
  516. case DIGIT:
  517. res = 0;
  518. if (*ofs < len && isdigit(((unsigned char *)s)[*ofs])) {
  519. (*ofs)++;
  520. res = 1;
  521. }
  522. pc++;
  523. break;
  524. case ANY:
  525. res = 0;
  526. if (*ofs < len) {
  527. (*ofs)++;
  528. res = 1;
  529. }
  530. pc++;
  531. break;
  532. case ANYOF:
  533. res = 0;
  534. if (*ofs < len)
  535. res = is_any_of(r->data + r->code[pc + 1],
  536. r->code[pc + 2], s, ofs);
  537. pc += 3;
  538. break;
  539. case ANYBUT:
  540. res = 0;
  541. if (*ofs < len)
  542. res = is_any_but(r->data + r->code[pc + 1],
  543. r->code[pc + 2], s, ofs);
  544. pc += 3;
  545. break;
  546. case BOL:
  547. res = *ofs == 0 ? 1 : 0;
  548. pc++;
  549. break;
  550. case EOL:
  551. res = *ofs == len ? 1 : 0;
  552. pc++;
  553. break;
  554. case OPEN:
  555. if (caps != NULL)
  556. caps[r->code[pc + 1]].ptr = s + *ofs;
  557. pc += 2;
  558. break;
  559. case CLOSE:
  560. if (caps != NULL)
  561. caps[r->code[pc + 1]].len = (s + *ofs) -
  562. caps[r->code[pc + 1]].ptr;
  563. pc += 2;
  564. break;
  565. case END:
  566. pc++;
  567. break;
  568. default:
  569. printf("unknown cmd (%d) at %d\n", r->code[pc], pc);
  570. assert(0);
  571. break;
  572. }
  573. }
  574. return res;
  575. }
  576. int
  577. slre_match(const struct slre *r, const char *buf, int len,
  578. struct cap *caps)
  579. {
  580. int i, ofs = 0, res = 0;
  581. if (r->anchored) {
  582. res = match(r, 0, buf, len, &ofs, caps);
  583. } else {
  584. for (i = 0; i < len && res == 0; i++) {
  585. ofs = i;
  586. res = match(r, 0, buf, len, &ofs, caps);
  587. }
  588. }
  589. return res;
  590. }
  591. #ifdef SLRE_TEST
  592. #define N_CAPS 5
  593. int main(int argc, char *argv[])
  594. {
  595. struct slre slre;
  596. struct cap caps[N_CAPS];
  597. unsigned char data[1 * 1024 * 1024];
  598. FILE *fp;
  599. int i, res, len;
  600. if (argc < 2) {
  601. fprintf(stderr, "Usage: %s 'slre' <file>\n", argv[0]);
  602. return 1;
  603. }
  604. fp = fopen(argv[2], "rb");
  605. if (fp == NULL) {
  606. fprintf(stderr, "Error: cannot open %s:%s\n",
  607. argv[2], strerror(errno));
  608. return 1;
  609. }
  610. if (!slre_compile(&slre, argv[1])) {
  611. fprintf(stderr, "Error compiling slre: %s\n", slre.err_str);
  612. return 1;
  613. }
  614. slre_dump(&slre, stderr);
  615. while (fgets(data, sizeof(data), fp) != NULL) {
  616. len = strlen(data);
  617. if ((len > 0) && (data[len-1] == '\n')) {
  618. data[len-1] = '\0';
  619. --len;
  620. }
  621. printf("Data = \"%s\"\n", data);
  622. (void) memset(caps, 0, sizeof(caps));
  623. res = slre_match(&slre, data, len, caps);
  624. printf("Result [%d]: %d\n", i, res);
  625. for (i = 0; i < N_CAPS; i++) {
  626. if (caps[i].len > 0) {
  627. printf("Substring %d: len=%d [%.*s]\n", i,
  628. caps[i].len,
  629. caps[i].len, caps[i].ptr);
  630. }
  631. }
  632. printf("----------------------------------------------------\n");
  633. }
  634. (void) fclose(fp);
  635. return 0;
  636. }
  637. #endif /* SLRE_TEST */