Index: user/gabor/tre-integration/contrib/tre/lib/hashtable.c =================================================================== --- user/gabor/tre-integration/contrib/tre/lib/hashtable.c (revision 225587) +++ user/gabor/tre-integration/contrib/tre/lib/hashtable.c (revision 225588) @@ -1,265 +1,264 @@ /*- * Copyright (C) 2011 Gabor Kovesdan * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include +#include #include #include #include "hashtable.h" #include "tre-internal.h" - /* * Return a 32-bit hash of the given buffer. The init * value should be 0, or the previous hash value to extend * the previous hash. */ static uint32_t hash32_buf(const void *buf, size_t len, uint32_t hash) { const unsigned char *p = buf; while (len--) hash = HASHSTEP(hash, *p++); return hash; } /* * Initializes a hash table that can hold table_size number of entries, * each of which has a key of key_size bytes and a value of value_size * bytes. On successful allocation returns a pointer to the hash table. * Otherwise, returns NULL and sets errno to indicate the error. */ hashtable *hashtable_init(size_t table_size, size_t key_size, size_t value_size) { hashtable *tbl; - DPRINT(("hashtable_init: table_size %lu, key_size %lu, value_size %lu\n", - (unsigned long)table_size, (unsigned long)key_size, - (unsigned long)value_size)); + DPRINT(("hashtable_init: table_size %zu, key_size %zu, value_size %zu\n", + table_size, key_size, value_size)); tbl = malloc(sizeof(hashtable)); if (tbl == NULL) goto mem1; tbl->entries = calloc(sizeof(hashtable_entry *), table_size); if (tbl->entries == NULL) goto mem2; tbl->table_size = table_size; tbl->usage = 0; tbl->key_size = key_size; tbl->value_size = value_size; return (tbl); mem2: free(tbl); mem1: DPRINT(("hashtable_init: allocation failed\n")); errno = ENOMEM; return (NULL); } /* * Places the key-value pair to the hashtable tbl. * Returns: * HASH_OK: if the key was not present in the hash table yet * but the kay-value pair has been successfully added. * HASH_UPDATED: if the value for the key has been updated with the * new value. * HASH_FULL: if the hash table is full and the entry could not * be added. * HASH_FAIL: if an error has occurred and errno has been set to * indicate the error. */ int hashtable_put(hashtable *tbl, const void *key, const void *value) { uint32_t hash = 0; if (tbl->table_size == tbl->usage) { DPRINT(("hashtable_put: hashtable is full\n")); return (HASH_FULL); } hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size; - DPRINT(("hashtable_put: calculated hash %lu\n", hash)); + DPRINT(("hashtable_put: calculated hash %" PRIu32 "\n", hash)); /* * On hash collision entries are inserted at the next free space, * so we have to increase the index until we either find an entry * with the same key (and update it) or we find a free space. */ for(;;) { if (tbl->entries[hash] == NULL) break; else if (memcmp(tbl->entries[hash]->key, key, tbl->key_size) == 0) { memcpy(tbl->entries[hash]->value, value, tbl->value_size); - DPRINT(("hashtable_put: effective location is %lu, " - "entry updated\n", hash)); + DPRINT(("hashtable_put: effective location is %" PRIu32 + ", entry updated\n", hash)); return (HASH_UPDATED); } if (++hash == tbl->table_size) hash = 0; } - DPRINT(("hashtable_put: effective location is %lu\n", hash)); + DPRINT(("hashtable_put: effective location is %" PRIu32 "\n", hash)); tbl->entries[hash] = malloc(sizeof(hashtable_entry)); if (tbl->entries[hash] == NULL) { errno = ENOMEM; goto mem1; } tbl->entries[hash]->key = malloc(tbl->key_size); if (tbl->entries[hash]->key == NULL) { errno = ENOMEM; goto mem2; } tbl->entries[hash]->value = malloc(tbl->value_size); if (tbl->entries[hash]->value == NULL) { errno = ENOMEM; goto mem3; } memcpy(tbl->entries[hash]->key, key, tbl->key_size); memcpy(tbl->entries[hash]->value, value, tbl->value_size); tbl->usage++; DPRINT(("hashtable_put: entry successfully inserted\n")); return (HASH_OK); mem3: free(tbl->entries[hash]->key); mem2: free(tbl->entries[hash]); mem1: DPRINT(("hashtable_put: insertion failed\n")); return (HASH_FAIL); } static hashtable_entry **hashtable_lookup(const hashtable *tbl, const void *key) { uint32_t hash = 0; hash = hash32_buf(key, tbl->key_size, hash) % tbl->table_size; for (;;) { if (tbl->entries[hash] == NULL) return (NULL); else if (memcmp(key, tbl->entries[hash]->key, tbl->key_size) == 0) { - DPRINT(("hashtable_lookup: entry found at location %lu\n", hash)); + DPRINT(("hashtable_lookup: entry found at location %" PRIu32 "\n", hash)); return (&tbl->entries[hash]); } if (++hash == tbl->table_size) hash = 0; } } /* * Retrieves the value for key from the hash table tbl and places * it to the space indicated by the value argument. * Returns HASH_OK if the value has been found and retrieved or * HASH_NOTFOUND otherwise. */ int hashtable_get(hashtable *tbl, const void *key, void *value) { hashtable_entry **entry; entry = hashtable_lookup(tbl, key); if (entry == NULL) { DPRINT(("hashtable_get: entry is not available in the hashtable\n")); return (HASH_NOTFOUND); } memcpy(value, (*entry)->value, tbl->value_size); DPRINT(("hashtable_get: entry successfully copied into output buffer\n")); return (HASH_OK); } /* * Removes the entry with the specifified key from the hash table * tbl. Returns HASH_OK if the entry has been found and removed * or HASH_NOTFOUND otherwise. */ int hashtable_remove(hashtable *tbl, const void *key) { hashtable_entry **entry; entry = hashtable_lookup(tbl, key); if (entry == NULL) { DPRINT(("hashtable_remove: entry is not available in the hashtable\n")); return (HASH_NOTFOUND); } free((*entry)->key); free((*entry)->value); free(*entry); *entry = NULL; tbl->usage--; DPRINT(("hashtable_remove: entry successfully removed\n")); return (HASH_OK); } /* * Frees the resources associated with the hash table tbl. */ void hashtable_free(hashtable *tbl) { if (tbl == NULL) return; for (unsigned int i = 0; i < tbl->table_size; i++) if ((tbl->entries[i] != NULL)) { free(tbl->entries[i]->key); free(tbl->entries[i]->value); } free(tbl->entries); DPRINT(("hashtable_free: resources are successfully freed\n")); } Index: user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c =================================================================== --- user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c (revision 225587) +++ user/gabor/tre-integration/contrib/tre/lib/tre-fastmatch.c (revision 225588) @@ -1,913 +1,1054 @@ /*- * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav * Copyright (C) 2008-2011 Gabor Kovesdan * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #ifdef HAVE_CONFIG_H #include #endif /* HAVE_CONFIG_H */ #include #include #include #include #include #include #ifdef TRE_WCHAR #include #include #endif #include "hashtable.h" #include "tre-fastmatch.h" #include "tre-internal.h" #include "xmalloc.h" static int fastcmp(const void *, const bool *, const void *, size_t, tre_str_type_t, bool, bool); +/* + * Clean up if pattern compilation fails. + */ #define FAIL_COMP(errcode) \ { \ if (fg->pattern) \ xfree(fg->pattern); \ if (fg->wpattern) \ xfree(fg->wpattern); \ if (fg->qsBc_table) \ hashtable_free(fg->qsBc_table); \ fg = NULL; \ return errcode; \ } /* * Skips n characters in the input string and assigns the start * address to startptr. Note: as per IEEE Std 1003.1-2008 * matching is based on bit pattern not character representations * so we can handle MB strings as byte sequences just like * SB strings. */ #define SKIP_CHARS(n) \ switch (type) \ { \ case STR_WIDE: \ startptr = str_wide + n; \ break; \ default: \ startptr = str_byte + n; \ } /* * Converts the wide string pattern to SB/MB string and stores * it in fg->pattern. Sets fg->len to the byte length of the * converted string. */ #define STORE_MBS_PAT \ { \ size_t siz; \ \ siz = wcstombs(NULL, fg->wpattern, 0); \ if (siz == (size_t)-1) \ return REG_BADPAT; \ fg->len = siz; \ fg->pattern = xmalloc(siz + 1); \ if (fg->pattern == NULL) \ return REG_ESPACE; \ wcstombs(fg->pattern, fg->wpattern, siz); \ fg->pattern[siz] = '\0'; \ } \ /* * Compares the pattern to the input string at the position * stored in startptr. */ #define COMPARE \ switch (type) \ { \ case STR_WIDE: \ mismatch = fastcmp(fg->wpattern, fg->wescmap, startptr, \ fg->wlen, type, \ fg->icase, fg->newline); \ break; \ default: \ mismatch = fastcmp(fg->pattern, fg->escmap, startptr, \ fg->len, type, \ fg->icase, fg->newline); \ } \ #define IS_OUT_OF_BOUNDS \ - ((type == STR_WIDE) ? ((j + fg->wlen) > len) : ((j + fg->len) > len)) + ((!fg->reversed \ + ? ((type == STR_WIDE) ? ((j + fg->wlen) > len) \ + : ((j + fg->len) > len)) \ + : (j < 0))) /* * Checks whether the new position after shifting in the input string * is out of the bounds and break out from the loop if so. */ #define CHECKBOUNDS \ if (IS_OUT_OF_BOUNDS) \ break; \ /* * Shifts in the input string after a mismatch. The position of the * mismatch is stored in the mismatch variable. */ #define SHIFT \ CHECKBOUNDS; \ \ { \ - int bc = 0, gs = 0, ts, r = -1; \ + int r = -1; \ + unsigned int bc = 0, gs = 0, ts; \ \ switch (type) \ { \ case STR_WIDE: \ if (!fg->hasdot) \ { \ - if (u != 0 && mismatch == fg->wlen - 1 - shift) \ + if (u != 0 && (unsigned)mismatch == fg->wlen - 1 - shift) \ mismatch -= u; \ v = fg->wlen - 1 - mismatch; \ r = hashtable_get(fg->qsBc_table, \ - &((tre_char_t *)startptr)[mismatch + 1], &bc); \ + &str_wide[!fg->reversed ? (size_t)j + fg->wlen \ + : (size_t)j - 1], &bc); \ gs = fg->bmGs[mismatch]; \ } \ bc = (r == HASH_OK) ? bc : fg->defBc; \ DPRINT(("tre_fast_match: mismatch on character %lc, " \ "BC %d, GS %d\n", \ - ((tre_char_t *)startptr)[mismatch + 1], bc, gs)); \ + ((const tre_char_t *)startptr)[mismatch + 1], \ + bc, gs)); \ break; \ default: \ if (!fg->hasdot) \ { \ - if (u != 0 && mismatch == fg->len - 1 - shift) \ + if (u != 0 && (unsigned)mismatch == fg->len - 1 - shift) \ mismatch -= u; \ v = fg->len - 1 - mismatch; \ gs = fg->sbmGs[mismatch]; \ } \ - bc = fg->qsBc[((unsigned char *)startptr)[mismatch + 1]]; \ + bc = fg->qsBc[((const unsigned char *)str_byte) \ + [!fg->reversed ? (size_t)j + fg->len \ + : (size_t)j - 1]]; \ DPRINT(("tre_fast_match: mismatch on character %c, " \ "BC %d, GS %d\n", \ - ((unsigned char *)startptr)[mismatch + 1], bc, gs)); \ + ((const unsigned char *)startptr)[mismatch + 1], \ + bc, gs)); \ } \ if (fg->hasdot) \ shift = bc; \ else \ { \ - ts = u - v; \ + ts = ((long)u - v < 0) ? 0 : (u - v); \ shift = MAX(ts, bc); \ shift = MAX(shift, gs); \ if (shift == gs) \ u = MIN((type == STR_WIDE ? fg->wlen : fg->len) - shift, v); \ else \ { \ if (ts < bc) \ shift = MAX(shift, u + 1); \ u = 0; \ } \ } \ - DPRINT(("tre_fast_match: shifting %d characters\n", shift)); \ - j += shift; \ + DPRINT(("tre_fast_match: shifting %u characters\n", shift)); \ + j = !fg->reversed ? j + shift : j - shift; \ } /* * Normal Quick Search would require a shift based on the position the * next character after the comparison is within the pattern. With * wildcards, the position of the last dot effects the maximum shift * distance. * The closer to the end the wild card is the slower the search. * * Examples: * Pattern Max shift * ------- --------- * this 5 * .his 4 * t.is 3 * th.s 2 * thi. 1 */ /* * Fills in the bad character shift array for SB/MB strings. */ #define FILL_QSBC \ + if (fg->reversed) \ + { \ + _FILL_QSBC_REVERSED \ + } \ + else \ + { \ + _FILL_QSBC \ + } + +#define _FILL_QSBC \ for (unsigned int i = 0; i <= UCHAR_MAX; i++) \ - fg->qsBc[i] = fg->len - fg->hasdot; \ - for (int i = fg->hasdot + 1; i < fg->len; i++) \ + fg->qsBc[i] = fg->len - hasdot; \ + for (unsigned int i = hasdot + 1; i < fg->len; i++) \ { \ fg->qsBc[(unsigned char)fg->pattern[i]] = fg->len - i; \ - DPRINT(("BC shift for char %c is %d\n", fg->pattern[i], \ + DPRINT(("BC shift for char %c is %zu\n", fg->pattern[i], \ fg->len - i)); \ if (fg->icase) \ + { \ + char c = islower((unsigned char)fg->pattern[i]) ? \ + toupper((unsigned char)fg->pattern[i]) : \ + tolower((unsigned char)fg->pattern[i]); \ + fg->qsBc[(unsigned char)c] = fg->len - i; \ + DPRINT(("BC shift for char %c is %zu\n", c, fg->len - i)); \ + } \ + } + +#define _FILL_QSBC_REVERSED \ + for (unsigned int i = 0; i <= UCHAR_MAX; i++) \ + fg->qsBc[i] = firstdot + 1; \ + for (int i = firstdot - 1; i >= 0; i--) \ + { \ + fg->qsBc[(unsigned char)fg->pattern[i]] = i + 1; \ + DPRINT(("Reverse BC shift for char %c is %d\n", fg->pattern[i], \ + i + 1)); \ + if (fg->icase) \ { \ char c = islower((unsigned char)fg->pattern[i]) ? \ toupper((unsigned char)fg->pattern[i]) : \ tolower((unsigned char)fg->pattern[i]); \ - fg->qsBc[(unsigned char)c] = fg->len - i; \ - DPRINT(("BC shift for char %c is %d\n", c, fg->len - i)); \ + fg->qsBc[(unsigned char)c] = i + 1; \ + DPRINT(("Reverse BC shift for char %c is %d\n", c, i + 1)); \ } \ } /* * Fills in the bad character shifts into a hastable for wide strings. * With wide characters it is not possible any more to use a normal * array because there are too many characters and we could not * provide enough memory. Fortunately, we only have to store distinct * values for so many characters as the number of distinct characters * in the pattern, so we can store them in a hashtable and store a * default shift value for the rest. */ #define FILL_QSBC_WIDE \ + if (fg->reversed) \ + { \ + _FILL_QSBC_WIDE_REVERSED \ + } \ + else \ + { \ + _FILL_QSBC_WIDE \ + } + +#define _FILL_QSBC_WIDE \ /* Adjust the shift based on location of the last dot ('.'). */ \ - fg->defBc = fg->wlen - fg->hasdot; \ + fg->defBc = fg->wlen - whasdot; \ \ /* Preprocess pattern. */ \ fg->qsBc_table = hashtable_init(fg->wlen * (fg->icase ? 8 : 4), \ sizeof(tre_char_t), sizeof(int)); \ if (!fg->qsBc_table) \ FAIL_COMP(REG_ESPACE); \ - for (unsigned int i = fg->hasdot + 1; i < fg->wlen; i++) \ + for (unsigned int i = whasdot + 1; i < fg->wlen; i++) \ { \ int k = fg->wlen - i; \ int r; \ \ r = hashtable_put(fg->qsBc_table, &fg->wpattern[i], &k); \ if ((r == HASH_FAIL) || (r == HASH_FULL)) \ FAIL_COMP(REG_ESPACE); \ DPRINT(("BC shift for wide char %lc is %d\n", fg->wpattern[i], \ - fg->wlen - i)); \ + k)); \ if (fg->icase) \ { \ tre_char_t wc = iswlower(fg->wpattern[i]) ? \ towupper(fg->wpattern[i]) : towlower(fg->wpattern[i]); \ r = hashtable_put(fg->qsBc_table, &wc, &k); \ if ((r == HASH_FAIL) || (r == HASH_FULL)) \ FAIL_COMP(REG_ESPACE); \ - DPRINT(("BC shift for wide char %lc is %d\n", wc, \ - fg->wlen - i)); \ + DPRINT(("BC shift for wide char %lc is %d\n", wc, k)); \ } \ } -#ifdef TRE_DEBUG +#define _FILL_QSBC_WIDE_REVERSED \ + /* Adjust the shift based on location of the last dot ('.'). */ \ + fg->defBc = (size_t)wfirstdot; \ + \ + /* Preprocess pattern. */ \ + fg->qsBc_table = hashtable_init(fg->wlen * (fg->icase ? 8 : 4), \ + sizeof(tre_char_t), sizeof(int)); \ + if (!fg->qsBc_table) \ + FAIL_COMP(REG_ESPACE); \ + for (int i = wfirstdot - 1; i >= 0; i--) \ + { \ + int k = i + 1; \ + int r; \ + \ + r = hashtable_put(fg->qsBc_table, &fg->wpattern[i], &k); \ + if ((r == HASH_FAIL) || (r == HASH_FULL)) \ + FAIL_COMP(REG_ESPACE); \ + DPRINT(("Reverse BC shift for wide char %lc is %d\n", \ + fg->wpattern[i], k)); \ + if (fg->icase) \ + { \ + tre_char_t wc = iswlower(fg->wpattern[i]) ? \ + towupper(fg->wpattern[i]) : towlower(fg->wpattern[i]); \ + r = hashtable_put(fg->qsBc_table, &wc, &k); \ + if ((r == HASH_FAIL) || (r == HASH_FULL)) \ + FAIL_COMP(REG_ESPACE); \ + DPRINT(("Reverse BC shift for wide char %lc is %d\n", wc, k));\ + } \ + } + +#ifdef _GREP_DEBUG #define DPRINT_BMGS(len, fmt_str, sh) \ - for (int i = 0; i < len; i++) \ + for (unsigned int i = 0; i < len; i++) \ DPRINT((fmt_str, i, sh[i])); #else #define DPRINT_BMGS(len, fmt_str, sh) \ do { } while(/*CONSTCOND*/0) #endif /* * Fills in the good suffix table for SB/MB strings. */ #define FILL_BMGS \ if (!fg->hasdot) \ { \ fg->sbmGs = xmalloc(fg->len * sizeof(int)); \ if (!fg->sbmGs) \ return REG_ESPACE; \ if (fg->len == 1) \ fg->sbmGs[0] = 1; \ else \ _FILL_BMGS(fg->sbmGs, fg->pattern, fg->len, false); \ DPRINT_BMGS(fg->len, "GS shift for pos %d is %d\n", fg->sbmGs); \ } /* * Fills in the good suffix table for wide strings. */ #define FILL_BMGS_WIDE \ if (!fg->hasdot) \ { \ fg->bmGs = xmalloc(fg->wlen * sizeof(int)); \ if (!fg->bmGs) \ return REG_ESPACE; \ if (fg->wlen == 1) \ fg->bmGs[0] = 1; \ else \ _FILL_BMGS(fg->bmGs, fg->wpattern, fg->wlen, true); \ DPRINT_BMGS(fg->wlen, "GS shift (wide) for pos %d is %d\n", \ fg->bmGs); \ } #define _FILL_BMGS(arr, pat, plen, wide) \ { \ char *p; \ tre_char_t *wp; \ \ if (wide) \ { \ if (fg->icase) \ { \ wp = xmalloc(plen * sizeof(tre_char_t)); \ if (wp == NULL) \ return REG_ESPACE; \ - for (int i = 0; i < plen; i++) \ + for (unsigned int i = 0; i < plen; i++) \ wp[i] = towlower(pat[i]); \ _CALC_BMGS(arr, wp, plen); \ xfree(wp); \ } \ else \ _CALC_BMGS(arr, pat, plen); \ } \ else \ { \ if (fg->icase) \ { \ p = xmalloc(plen); \ if (p == NULL) \ return REG_ESPACE; \ - for (int i = 0; i < plen; i++) \ + for (unsigned int i = 0; i < plen; i++) \ p[i] = tolower(pat[i]); \ _CALC_BMGS(arr, p, plen); \ xfree(p); \ } \ else \ _CALC_BMGS(arr, pat, plen); \ } \ } #define _CALC_BMGS(arr, pat, plen) \ { \ - int f, g; \ + int f = 0, g; \ \ int *suff = xmalloc(plen * sizeof(int)); \ if (suff == NULL) \ return REG_ESPACE; \ \ suff[plen - 1] = plen; \ g = plen - 1; \ for (int i = plen - 2; i >= 0; i--) \ { \ if (i > g && suff[i + plen - 1 - f] < i - g) \ suff[i] = suff[i + plen - 1 - f]; \ else \ { \ if (i < g) \ g = i; \ f = i; \ while (g >= 0 && pat[g] == pat[g + plen - 1 - f]) \ g--; \ suff[i] = f - g; \ } \ } \ \ - for (int i = 0; i < plen; i++) \ + for (unsigned int i = 0; i < plen; i++) \ arr[i] = plen; \ g = 0; \ for (int i = plen - 1; i >= 0; i--) \ if (suff[i] == i + 1) \ - for(; g < plen - 1 - i; g++) \ + for(; (unsigned long)g < plen - 1 - i; g++) \ if (arr[g] == plen) \ arr[g] = plen - 1 - i; \ - for (int i = 0; i <= plen - 2; i++) \ + for (unsigned int i = 0; i <= plen - 2; i++) \ arr[plen - 1 - suff[i]] = plen - 1 - i; \ \ xfree(suff); \ } /* * Copies the pattern pat having lenght n to p and stores * the size in l. */ #define SAVE_PATTERN(src, srclen, dst, dstlen) \ dstlen = srclen; \ - if (dstlen == 0) \ - dst = TRE_CHAR(""); \ - else \ - { \ - dst = xmalloc((dstlen + 1) * sizeof(tre_char_t)); \ - if (dst == NULL) \ - return REG_ESPACE; \ - memcpy(dst, src, dstlen * sizeof(tre_char_t)); \ - dst[dstlen] = TRE_CHAR('\0'); \ - } + dst = xmalloc((dstlen + 1) * sizeof(tre_char_t)); \ + if (dst == NULL) \ + return REG_ESPACE; \ + if (dstlen > 0) \ + memcpy(dst, src, dstlen * sizeof(tre_char_t)); \ + dst[dstlen] = TRE_CHAR('\0'); /* * Initializes pattern compiling. */ #define INIT_COMP \ /* Initialize. */ \ memset(fg, 0, sizeof(*fg)); \ fg->icase = (cflags & REG_ICASE); \ fg->word = (cflags & REG_WORD); \ fg->newline = (cflags & REG_NEWLINE); \ fg->nosub = (cflags & REG_NOSUB); \ \ - if (n == 0) \ - { \ - fg->matchall = true; \ - fg->pattern = ""; \ - fg->wpattern = TRE_CHAR(""); \ - DPRINT(("Matching every input\n")); \ - return REG_OK; \ - } \ - \ /* Cannot handle REG_ICASE with MB string */ \ if (fg->icase && (TRE_MB_CUR_MAX > 1)) \ { \ DPRINT(("Cannot use fast matcher for MBS with REG_ICASE\n")); \ return REG_BADPAT; \ } /* + * Checks whether we have a 0-length pattern that will match + * anything. If literal is set to false, the EOL anchor is also + * taken into account. + */ +#define CHECK_MATCHALL(literal) \ + if (!literal && n == 1 && pat[0] == TRE_CHAR('$')) \ + { \ + n--; \ + fg->eol = true; \ + } \ + \ + if (n == 0) \ + { \ + fg->matchall = true; \ + fg->pattern = xmalloc(sizeof(char)); \ + if (!fg->pattern) \ + FAIL_COMP(REG_ESPACE); \ + fg->pattern[0] = '\0'; \ + fg->wpattern = xmalloc(sizeof(tre_char_t)); \ + if (!fg->wpattern) \ + FAIL_COMP(REG_ESPACE); \ + fg->wpattern[0] = TRE_CHAR('\0'); \ + DPRINT(("Matching every input\n")); \ + return REG_OK; \ + } + +/* * Returns: REG_OK on success, error code otherwise */ int tre_compile_literal(fastmatch_t *fg, const tre_char_t *pat, size_t n, int cflags) { + size_t hasdot = 0, whasdot = 0; + ssize_t firstdot = -1, wfirstdot = -1; + INIT_COMP; + CHECK_MATCHALL(true); + /* Cannot handle word boundaries with MB string */ if (fg->word && (TRE_MB_CUR_MAX > 1)) return REG_BADPAT; #ifdef TRE_WCHAR SAVE_PATTERN(pat, n, fg->wpattern, fg->wlen); STORE_MBS_PAT; #else SAVE_PATTERN(pat, n, fg->pattern, fg->len); #endif - DPRINT(("tre_compile_literal: pattern: %s, len %u, icase: %c, word: %c, " + DPRINT(("tre_compile_literal: pattern: %s, len %zu, icase: %c, word: %c, " "newline %c\n", fg->pattern, fg->len, fg->icase ? 'y' : 'n', fg->word ? 'y' : 'n', fg->newline ? 'y' : 'n')); FILL_QSBC; FILL_BMGS; #ifdef TRE_WCHAR FILL_QSBC_WIDE; FILL_BMGS_WIDE; #endif return REG_OK; } /* * Returns: REG_OK on success, error code otherwise */ int tre_compile_fast(fastmatch_t *fg, const tre_char_t *pat, size_t n, int cflags) { tre_char_t *tmp; - size_t pos = 0; + size_t pos = 0, hasdot = 0, whasdot = 0;; + ssize_t firstdot = -1, wfirstdot = -1; bool escaped = false; bool *_escmap = NULL; INIT_COMP; /* Remove beginning-of-line character ('^'). */ if (pat[0] == TRE_CHAR('^')) { fg->bol = true; n--; pat++; } + CHECK_MATCHALL(false); + /* Handle word-boundary matching when GNU extensions are enabled */ if ((cflags & REG_GNU) && (n >= 14) && (memcmp(pat, TRE_CHAR("[[:<:]]"), 7 * sizeof(tre_char_t)) == 0) && (memcmp(pat + n - 7, TRE_CHAR("[[:>:]]"), 7 * sizeof(tre_char_t)) == 0)) { n -= 14; pat += 7; fg->word = true; } /* Cannot handle word boundaries with MB string */ if (fg->word && (TRE_MB_CUR_MAX > 1)) return REG_BADPAT; tmp = xmalloc((n + 1) * sizeof(tre_char_t)); if (tmp == NULL) return REG_ESPACE; +/* Copies the char into the stored pattern and skips to the next char. */ #define STORE_CHAR \ do \ { \ tmp[pos++] = pat[i]; \ escaped = false; \ continue; \ } while (0) - for (int i = 0; i < n; i++) + /* Traverse the input pattern for processing */ + for (unsigned int i = 0; i < n; i++) { switch (pat[i]) { case TRE_CHAR('\\'): if (escaped) STORE_CHAR; else escaped = true; continue; case TRE_CHAR('['): if (escaped) STORE_CHAR; else goto badpat; continue; case TRE_CHAR('*'): if (escaped || (!(cflags & REG_EXTENDED) && (i == 0))) STORE_CHAR; else goto badpat; continue; case TRE_CHAR('+'): case TRE_CHAR('?'): if ((cflags & REG_EXTENDED) && (i == 0)) continue; else if ((cflags & REG_EXTENDED) ^ !escaped) STORE_CHAR; else goto badpat; continue; case TRE_CHAR('.'): if (escaped) { if (!_escmap) _escmap = xmalloc(n * sizeof(bool)); if (!_escmap) { xfree(tmp); return REG_ESPACE; } _escmap[i] = true; STORE_CHAR; } else { - fg->hasdot = i; + whasdot = i; + if (wfirstdot == -1) + wfirstdot = i; STORE_CHAR; } continue; case TRE_CHAR('^'): STORE_CHAR; continue; case TRE_CHAR('$'): if (!escaped && (i == n - 1)) fg->eol = true; else STORE_CHAR; continue; case TRE_CHAR('('): if ((cflags & REG_EXTENDED) ^ escaped) goto badpat; else STORE_CHAR; continue; case TRE_CHAR('{'): if (!(cflags & REG_EXTENDED) ^ escaped) STORE_CHAR; else if (!(cflags & REG_EXTENDED) && (i == 0)) STORE_CHAR; else if ((cflags & REG_EXTENDED) && (i == 0)) continue; else goto badpat; continue; case TRE_CHAR('|'): if ((cflags & REG_EXTENDED) ^ escaped) goto badpat; else STORE_CHAR; continue; default: if (escaped) goto badpat; else STORE_CHAR; continue; } continue; badpat: xfree(tmp); + DPRINT(("tre_compile_fast: compilation of pattern failed, falling" + "back to NFA\n")); return REG_BADPAT; } + fg->hasdot = whasdot; + /* * The pattern has been processed and copied to tmp as a literal string * with escapes, anchors (^$) and the word boundary match character * classes stripped out. */ #ifdef TRE_WCHAR SAVE_PATTERN(tmp, pos, fg->wpattern, fg->wlen); fg->wescmap = _escmap; STORE_MBS_PAT; - if (fg->wescmap != NULL) - { - bool escaped = false; - fg->escmap = xmalloc(fg->len * sizeof(bool)); - if (!fg->escmap) + /* + * The position of dots and escaped dots is different in the MB string + * than in to the wide string so traverse the converted string, as well, + * to store these positions. + */ + if (fg->hasdot || (fg->wescmap != NULL)) + { + if (fg->wescmap != NULL) { - tre_free_fast(fg); - return REG_ESPACE; + fg->escmap = xmalloc(fg->len * sizeof(bool)); + if (!fg->escmap) + { + tre_free_fast(fg); + return REG_ESPACE; + } } - for (int i = 0; i < fg->len; i++) + escaped = false; + for (unsigned int i = 0; i < fg->len; i++) if (fg->pattern[i] == '\\') - escaped = ! escaped; + escaped = !escaped; else if (fg->pattern[i] == '.' && escaped) { fg->escmap[i] = true; escaped = false; } + else if (fg->pattern[i] == '.' && !escaped) + { + hasdot = i; + if (firstdot == -1) + firstdot = i; + } else escaped = false; } #else SAVE_PATTERN(tmp, pos, fg->pattern, fg->len); fg->escmap = _escmap; #endif xfree(tmp); - DPRINT(("tre_compile_fast: pattern: %s, len %u, bol %c, eol %c, " + DPRINT(("tre_compile_fast: pattern: %s, len %zu, bol %c, eol %c, " "icase: %c, word: %c, newline %c\n", fg->pattern, fg->len, fg->bol ? 'y' : 'n', fg->eol ? 'y' : 'n', fg->icase ? 'y' : 'n', fg->word ? 'y' : 'n', fg->newline ? 'y' : 'n')); + /* Check whether reverse QS algorithm is more efficient */ + if ((wfirstdot > -1) && (fg->wlen - whasdot + 1 < (size_t)wfirstdot) && + fg->nosub) + { + fg->reversed = true; + DPRINT(("tre_compile_fast: using reverse QS algorithm\n")); + } + FILL_QSBC; FILL_BMGS; #ifdef TRE_WCHAR FILL_QSBC_WIDE; FILL_BMGS_WIDE; #endif return REG_OK; } #define _SHIFT_ONE \ { \ shift = 1; \ - j += shift; \ + j = !fg->reversed ? j + shift : j - shift; \ continue; \ } #define _BBOUND_COND \ ((type == STR_WIDE) ? \ ((j == 0) || !(tre_isalnum(str_wide[j - 1]) || \ (str_wide[j - 1] == TRE_CHAR('_')))) : \ ((j == 0) || !(tre_isalnum(str_byte[j - 1]) || \ (str_byte[j - 1] == '_')))) #define _EBOUND_COND \ ((type == STR_WIDE) ? \ ((j + fg->wlen == len) || !(tre_isalnum(str_wide[j + fg->wlen]) || \ (str_wide[j + fg->wlen] == TRE_CHAR('_')))) : \ ((j + fg->len == len) || !(tre_isalnum(str_byte[j + fg->len]) || \ (str_byte[j + fg->len] == '_')))) /* * Condition to check whether the match on position j is on a * word boundary. */ #define IS_ON_WORD_BOUNDARY \ (_BBOUND_COND && _EBOUND_COND) /* * Checks word boundary and shifts one if match is not on a * boundary. */ #define CHECK_WORD_BOUNDARY \ if (!IS_ON_WORD_BOUNDARY) \ _SHIFT_ONE; #define _BOL_COND \ - ((j == 0) || ((type == STR_WIDE) ? tre_isspace(str_wide[j - 1]) : \ - isspace(str_byte[j - 1]))) + ((j == 0) || ((type == STR_WIDE) ? (str_wide[j - 1] == TRE_CHAR('\n'))\ + : (str_byte[j - 1] == '\n'))) /* * Checks BOL anchor and shifts one if match is not on a * boundary. */ #define CHECK_BOL_ANCHOR \ if (!_BOL_COND) \ _SHIFT_ONE; #define _EOL_COND \ - ((type == STR_WIDE) ? \ - ((j + fg->wlen == len) || tre_isspace(str_wide[j + fg->wlen])) : \ - ((j + fg->len == len) || isspace(str_byte[j + fg->wlen]))) + ((type == STR_WIDE) \ + ? ((j + fg->wlen == len) || \ + (str_wide[j + fg->wlen] == TRE_CHAR('\n'))) \ + : ((j + fg->len == len) || (str_byte[j + fg->wlen] == '\n'))) /* * Checks EOL anchor and shifts one if match is not on a * boundary. */ #define CHECK_EOL_ANCHOR \ if (!_EOL_COND) \ _SHIFT_ONE; /* * Executes matching of the precompiled pattern on the input string. * Returns REG_OK or REG_NOMATCH depending on if we find a match or not. */ int tre_match_fast(const fastmatch_t *fg, const void *data, size_t len, - tre_str_type_t type, int nmatch, regmatch_t pmatch[], int eflags) + tre_str_type_t type, int nmatch __unused, regmatch_t pmatch[], int eflags) { - unsigned int j = 0; + unsigned int shift, u = 0, v = 0; + ssize_t j = 0; int ret = REG_NOMATCH; - int mismatch, shift, u = 0, v; + int mismatch; const char *str_byte = data; const void *startptr = NULL; const tre_char_t *str_wide = data; /* Calculate length if unspecified. */ if (len == (size_t)-1) switch (type) { case STR_WIDE: len = tre_strlen(str_wide); break; default: len = strlen(str_byte); break; } + /* Shortcut for empty pattern */ if (fg->matchall) { if (!fg->nosub) { pmatch[0].rm_so = 0; pmatch[0].rm_eo = len; } - return REG_OK; + if (fg->bol && fg->eol) + return (len == 0) ? REG_OK : REG_NOMATCH; + else + return REG_OK; } /* No point in going farther if we do not have enough data. */ switch (type) { case STR_WIDE: if (len < fg->wlen) return ret; shift = fg->wlen; break; default: if (len < fg->len) return ret; shift = fg->len; } /* * REG_NOTBOL means not anchoring ^ to the beginning of the line, so we * can shift one because there can't be a match at the beginning. */ if (fg->bol && (eflags & REG_NOTBOL)) j = 1; /* * Like above, we cannot have a match at the very end when anchoring to * the end and REG_NOTEOL is specified. */ if (fg->eol && (eflags & REG_NOTEOL)) len--; + + if (fg->reversed) + j = len - (type == STR_WIDE ? fg->wlen : fg->len); + /* Only try once at the beginning or ending of the line. */ if ((fg->bol || fg->eol) && !fg->newline && !(eflags & REG_NOTBOL) && !(eflags & REG_NOTEOL)) { /* Simple text comparison. */ if (!((fg->bol && fg->eol) && (type == STR_WIDE ? (len != fg->wlen) : (len != fg->len)))) { /* Determine where in data to start search at. */ j = fg->eol ? len - (type == STR_WIDE ? fg->wlen : fg->len) : 0; SKIP_CHARS(j); COMPARE; if (mismatch == REG_OK) { if (fg->word && !IS_ON_WORD_BOUNDARY) return ret; if (!fg->nosub) { pmatch[0].rm_so = j; pmatch[0].rm_eo = j + (type == STR_WIDE ? fg->wlen : fg->len); } return REG_OK; } } } else { /* Quick Search / Turbo Boyer-Moore algorithm. */ do { SKIP_CHARS(j); COMPARE; if (mismatch == REG_OK) { if (fg->word) CHECK_WORD_BOUNDARY; if (fg->bol) CHECK_BOL_ANCHOR; if (fg->eol) CHECK_EOL_ANCHOR; if (!fg->nosub) { pmatch[0].rm_so = j; pmatch[0].rm_eo = j + ((type == STR_WIDE) ? fg->wlen : fg->len); } return REG_OK; } else if (mismatch > 0) return mismatch; mismatch = -mismatch - 1; SHIFT; } while (!IS_OUT_OF_BOUNDS); } return ret; } /* * Frees the resources that were allocated when the pattern was compiled. */ void tre_free_fast(fastmatch_t *fg) { DPRINT(("tre_fast_free: freeing structures for pattern %s\n", fg->pattern)); #ifdef TRE_WCHAR hashtable_free(fg->qsBc_table); if (!fg->hasdot) xfree(fg->bmGs); if (fg->wescmap) xfree(fg->wescmap); xfree(fg->wpattern); #endif if (!fg->hasdot) xfree(fg->sbmGs); if (fg->escmap) xfree(fg->escmap); xfree(fg->pattern); } /* * Returns: -(i + 1) on failure (position that it failed with minus sign) * error code on error * REG_OK on success */ static inline int fastcmp(const void *pat, const bool *escmap, const void *data, size_t len, tre_str_type_t type, bool icase, bool newline) { const char *str_byte = data; const char *pat_byte = pat; int ret = REG_OK; const tre_char_t *str_wide = data; const tre_char_t *pat_wide = pat; /* Compare the pattern and the input char-by-char from the last position. */ for (int i = len - 1; i >= 0; i--) { switch (type) { case STR_WIDE: /* Check dot */ if (pat_wide[i] == TRE_CHAR('.') && (!escmap || !escmap[i]) && (!newline || (str_wide[i] != TRE_CHAR('\n')))) continue; /* Compare */ if (icase ? (towlower(pat_wide[i]) == towlower(str_wide[i])) : (pat_wide[i] == str_wide[i])) continue; break; default: /* Check dot */ if (pat_byte[i] == '.' && (!escmap || !escmap[i]) && (!newline || (str_byte[i] != '\n'))) continue; /* Compare */ if (icase ? (tolower(pat_byte[i]) == tolower(str_byte[i])) : (pat_byte[i] == str_byte[i])) continue; } DPRINT(("fastcmp: mismatch at position %d\n", i)); ret = -(i + 1); break; } return ret; }