241024.1 · fc26ea0b48da58e93e1f9fe654541877d2752c35
released 7.0
fix #426; fix #427; fix #428; fix #430; fix #432
reading declarations
@@ -34,7 +34,7 @@ Development roadmap - #1 priority is quality assurance to continue to make sure ugrep has no bugs and is reliable -- make ugrep run even faster, see [#421](https://github.com/Genivia/ugrep/issues/421)+- make ugrep run even faster, see for example [#432](https://github.com/Genivia/ugrep/issues/432), [#421](https://github.com/Genivia/ugrep/issues/421) - share [reproducible performance results](https://github.com/Genivia/ugrep-benchmarks) @@ -2596,6 +2596,16 @@ meaning; any name or string that does not contain a `:` or `,` may be used. ### Searching and displaying binary files with -U, -W, and -X + --hexdump[=[1-8][a][bch][A[NUM]][B[NUM]][C[NUM]]]+ Output matches in 1 to 8 columns of 8 hexadecimal octets. The+ default is 2 columns or 16 octets per line. Argument `a' outputs a+ `*' for all hex lines that are identical to the previous hex line,+ `b' removes all space breaks, `c' removes the character column, `h'+ removes hex spacing, `A' includes up to NUM hex lines after a+ match, `B' includes up to NUM hex lines before a match and `C'+ includes up to NUM hex lines before and after a match. Arguments+ `A', `B' and `C' are the same as options -A, -B and -C when used+ with --hexdump. See also options -U, -W and -X. -U, --ascii, --binary Disables Unicode matching for binary file matching, forcing PATTERN to match bytes, not Unicode characters. For example, -U '\xa3'@@ -2603,30 +2613,21 @@ meaning; any name or string that does not contain a `:` or `,` may be used. represented by the UTF-8 sequence C2 A3. See also --dotall. -W, --with-hex Output binary matches in hexadecimal, leaving text matches alone.- This option is equivalent to the --binary-files=with-hex option- with --hexdump=2C. To omit the matching line from the hex output,- combine option --hexdump with option -W. See also option -U.+ This option is equivalent to the --binary-files=with-hex option.+ To omit the matching line from the hex output, use both options -W+ and --hexdump. See also options -U. -X, --hex- Output matches in hexadecimal. This option is equivalent to the- --binary-files=hex option with --hexdump=2C. To omit the matching+ Output matches and matching lines in hexadecimal. This option is+ equivalent to the --binary-files=hex option. To omit the matching line from the hex output use option --hexdump. See also option -U.- --hexdump[=[1-8][a][bch][A[NUM]][B[NUM]][C[NUM]]]- Output matches in 1 to 8 columns of 8 hexadecimal octets. The- default is 2 columns or 16 octets per line. Option `a' outputs a- `*' for all hex lines that are identical to the previous hex line,- `b' removes all space breaks, `c' removes the character column, `h'- removes hex spacing, `A' includes up to NUM hex lines after the- match, `B' includes up to NUM hex lines before the match and `C'- includes up to NUM hex lines. When NUM is omitted, the matching- line is included in the output. See also options -U, -W and -X. --dotall Dot `.' in regular expressions matches anything, including newline. Note that `.*' matches all input and should not be used. Note that `--hexdump` differs from `-X` by omitting the matching line from the hex output, showing only the matching pattern using a minimal number of hex-lines. Option `-X` is the same as `--hexdump=2C` to display the matching line-as hex `C` context.+lines. Additional match context hex lines are output with the `-ABC` context+options or with `--hexdump=C3` to output 3 hex lines as context, for example. To search a file for ASCII words, displaying text lines as usual while binary content is shown in hex with `-U` and `-W`:@@ -3384,8 +3385,8 @@ option | format string (within quotes) option | format string (within quotes) ---------------- | ----------------------------- `--format-begin` | `'<grep>%~'`-`--format-open` | `' <file%[]$%[ name=]H>%~'`-`--format` | `' <match%[\"]$%[ line=\"]N%[ column=\"]K%[ offset=\"]B>%X</match>%~%u'`+`--format-open` | `' <file%["]$%[ name="]I>%~'`+`--format` | `' <match%["]$%[ line="]N%[ column="]K%[ offset="]B>%X</match>%~%u'` `--format-close` | `' </file>%~'` `--format-end` | `'</grep>%~'` @@ -3412,6 +3413,9 @@ field | output `%+` | if option `-+` or `--heading` is used: `%F` and a newline character, suppress all `%F` and `%H` afterward `%[TEXT]H` | if option `-H` is used: `TEXT`, the quoted pathname and separator, `\"` and `\\` replace `"` and `\` `%h` | the quoted file pathname, `\"` and `\\` replace `"` and `\`+`%I` | if option `-H` is used: the pathname in XML and separator+`%[TEXT]I` | if option `-H` is used: `TEXT`, the pathname as XML and separator+`%i` | the file pathnames as XML `%N` | if option `-n` is used: the line number and separator `%[TEXT]N` | if option `-n` is used: `TEXT`, the line number and separator `%n` | the line number of the match@@ -4409,14 +4413,14 @@ in markdown: --hexdump[=[1-8][a][bch][A[NUM]][B[NUM]][C[NUM]]] Output matches in 1 to 8 columns of 8 hexadecimal octets. The- default is 2 columns or 16 octets per line. Option `a' outputs a- `*' for all hex lines that are identical to the previous hex line,- `b' removes all space breaks, `c' removes the character column,- `h' removes hex spacing, `A' includes up to NUM hex lines after- the match, `B' includes up to NUM hex lines before the match and- `C' includes up to NUM hex lines. When NUM is omitted, the- matching line is included in the output. See also options -U, -W- and -X.+ default is 2 columns or 16 octets per line. Argument `a' outputs+ a `*' for all hex lines that are identical to the previous hex+ line, `b' removes all space breaks, `c' removes the character+ column, `h' removes hex spacing, `A' includes up to NUM hex lines+ after a match, `B' includes up to NUM hex lines before a match and+ `C' includes up to NUM hex lines before and after a match.+ Arguments `A', `B' and `C' are the same as options -A, -B and -C+ when used with --hexdump. See also options -U, -W and -X. --hidden, -. Search hidden files and directories.@@ -4654,13 +4658,13 @@ in markdown: -e. Press F1 or CTRL-Z to view the help screen. Press F2 or CTRL-Y to invoke a command to view or edit the file shown at the top of the screen. The command can be specified with option- --view, or defaults to environment variable PAGER when defined, or- EDITOR. Press Tab and Shift-Tab to navigate directories and to- select a file to search. Press Enter to select lines to output.- Press ALT-l for option -l to list files, ALT-n for -n, etc.- Non-option commands include ALT-] to increase context and ALT-} to- increase fuzzyness. See also options --no-confirm, --delay,- --split and --view.+ --view and defaults to environment variable PAGER when defined, or+ VISUAL or EDITOR. Press Tab or Shift-Tab to navigate directories+ and to select a file to search. Press Enter to select lines to+ output. Press ALT-l for option -l to list files, ALT-n for -n,+ etc. Non-option commands include ALT-] to increase context and+ ALT-} to increase fuzzyness. See also options --no-confirm,+ --delay, --split and --view. -q, --quiet, --silent Quiet mode: suppress all output. Only search a file until a match@@ -4703,11 +4707,12 @@ in markdown: indirectly load the specified FILE, but recursive config loading is not allowed. - --separator[=SEP], --separator-context=SEP+ --separator[=SEP], --context-separator=SEP Use SEP as field separator between file name, line number, column- number, byte offset and the matched line. The default is a colon- (`:') or a bar (`|') for multi-line pattern matches, and a dash- (`-') for ontext lines.+ number, byte offset and the matched line. The default separator+ is a colon (`:') and a bar (`|') for multi-line pattern matches,+ and a dash (`-') for context lines. See also option+ --group-separator. --split Split the -Q query TUI screen on startup.@@ -4798,9 +4803,9 @@ in markdown: -W, --with-hex Output binary matches in hexadecimal, leaving text matches alone.- This option is equivalent to the --binary-files=with-hex option- with --hexdump=2C. To omit the matching line from the hex output,- combine option --hexdump with option -W. See also option -U.+ This option is equivalent to the --binary-files=with-hex option.+ To omit the matching line from the hex output, use both options -W+ and --hexdump. See also options -U. -w, --word-regexp The PATTERN is searched for as a word, such that the matching text@@ -4814,8 +4819,8 @@ in markdown: double wide characters in the output may result in wider lines. -X, --hex- Output matches in hexadecimal. This option is equivalent to the- --binary-files=hex option with --hexdump=2C. To omit the matching+ Output matches and matching lines in hexadecimal. This option is+ equivalent to the --binary-files=hex option. To omit the matching line from the hex output use option --hexdump. See also option -U. @@ -5106,6 +5111,12 @@ in markdown: %h the quoted file pathname, \" and \\ replace " and \. + %[TEXT]I+ if option -H is used: TEXT, the pathname as XML character data and+ separator.++ %i the file pathname as XML character data.+ %[TEXT]N if option -n is used: TEXT, the line number and separator. @@ -5248,7 +5259,7 @@ in markdown: %[SEP]$ and %u are switches and do not send anything to the output. - The separator used by the %F, %H, %N, %K, %B, %S and %G fields may be+ The separator used by the %F, %H, %I, %N, %K, %B, %S and %G fields may be changed by preceding the field by %[SEP]$. When [SEP] is not provided, this reverts the separator to the default separator or the separator specified with --separator.@@ -5451,7 +5462,7 @@ in markdown: - ugrep 6.5.0 August 23, 2024 UGREP(1)+ ugrep 7.0.0 October 24, 2024 UGREP(1) 🔝 [Back to table of contents](#toc)
@@ -331,7 +331,7 @@ cat <<'END' -W, --with-hex Output binary matches in hexadecimal, leaving text matches alone. -w, --word-regexp The PATTERN is searched for as a word, such that the matching text is preceded by a non-word character and is followed by a non-word character. --width[=NUM] Truncate the output to NUM visible characters per line.--X, --hex Output matches in hexadecimal.+-X, --hex Output matches and matching lines in hexadecimal. -x, --line-regexp Select only those matches that exactly match the whole line, as if the patterns are surrounded by ^ and $. --xml Output file matches in XML. -Y, --empty Permits empty matches.
@@ -109,7 +109,7 @@ complete -c ug+ -l view -d 'Use COMMAND to view/edit a file in -Q query TUI by p complete -c ug+ -s W -l with-hex -d 'Output binary matches in hexadecimal, leaving text matches alone' complete -c ug+ -s w -l word-regexp -d 'The PATTERN is searched for as a word, such that the matching text is preceded by a non-word character and is followed by a non-word character' complete -c ug+ -l width -d 'Truncate the output to NUM visible characters per line'-complete -c ug+ -s X -l hex -d 'Output matches in hexadecimal'+complete -c ug+ -s X -l hex -d 'Output matches and matching lines in hexadecimal' complete -c ug+ -s x -l line-regexp -d 'Select only those matches that exactly match the whole line, as if the patterns are surrounded by ^ and $' complete -c ug+ -l xml -d 'Output file matches in XML' complete -c ug+ -s Y -l empty -d 'Permits empty matches'
@@ -109,7 +109,7 @@ complete -c ug -l view -d 'Use COMMAND to view/edit a file in -Q query TUI by pr complete -c ug -s W -l with-hex -d 'Output binary matches in hexadecimal, leaving text matches alone' complete -c ug -s w -l word-regexp -d 'The PATTERN is searched for as a word, such that the matching text is preceded by a non-word character and is followed by a non-word character' complete -c ug -l width -d 'Truncate the output to NUM visible characters per line'-complete -c ug -s X -l hex -d 'Output matches in hexadecimal'+complete -c ug -s X -l hex -d 'Output matches and matching lines in hexadecimal' complete -c ug -s x -l line-regexp -d 'Select only those matches that exactly match the whole line, as if the patterns are surrounded by ^ and $' complete -c ug -l xml -d 'Output file matches in XML' complete -c ug -s Y -l empty -d 'Permits empty matches'
@@ -109,7 +109,7 @@ complete -c ugrep+ -l view -d 'Use COMMAND to view/edit a file in -Q query TUI b complete -c ugrep+ -s W -l with-hex -d 'Output binary matches in hexadecimal, leaving text matches alone' complete -c ugrep+ -s w -l word-regexp -d 'The PATTERN is searched for as a word, such that the matching text is preceded by a non-word character and is followed by a non-word character' complete -c ugrep+ -l width -d 'Truncate the output to NUM visible characters per line'-complete -c ugrep+ -s X -l hex -d 'Output matches in hexadecimal'+complete -c ugrep+ -s X -l hex -d 'Output matches and matching lines in hexadecimal' complete -c ugrep+ -s x -l line-regexp -d 'Select only those matches that exactly match the whole line, as if the patterns are surrounded by ^ and $' complete -c ugrep+ -l xml -d 'Output file matches in XML' complete -c ugrep+ -s Y -l empty -d 'Permits empty matches'
@@ -109,7 +109,7 @@ complete -c ugrep -l view -d 'Use COMMAND to view/edit a file in -Q query TUI by complete -c ugrep -s W -l with-hex -d 'Output binary matches in hexadecimal, leaving text matches alone' complete -c ugrep -s w -l word-regexp -d 'The PATTERN is searched for as a word, such that the matching text is preceded by a non-word character and is followed by a non-word character' complete -c ugrep -l width -d 'Truncate the output to NUM visible characters per line'-complete -c ugrep -s X -l hex -d 'Output matches in hexadecimal'+complete -c ugrep -s X -l hex -d 'Output matches and matching lines in hexadecimal' complete -c ugrep -s x -l line-regexp -d 'Select only those matches that exactly match the whole line, as if the patterns are surrounded by ^ and $' complete -c ugrep -l xml -d 'Output file matches in XML' complete -c ugrep -s Y -l empty -d 'Permits empty matches'
@@ -116,7 +116,7 @@ $matchers{-P,--perl-regexp}'[Interpret PATTERN as a Perl regular expression usin {-W,--with-hex}'[Output binary matches in hexadecimal, leaving text matches alone]' {-w,--word-regexp}'[The PATTERN is searched for as a word, such that the matching text is preceded by a non-word character and is followed by a non-word character]' --width'[Truncate the output to NUM visible characters per line]'-{-X,--hex}'[Output matches in hexadecimal]'+{-X,--hex}'[Output matches and matching lines in hexadecimal]' {-x,--line-regexp}'[Select only those matches that exactly match the whole line, as if the patterns are surrounded by ^ and $]' --xml'[Output file matches in XML]' {-Y,--empty}'[Permits empty matches]'
@@ -116,7 +116,7 @@ $matchers{-P,--perl-regexp}'[Interpret PATTERN as a Perl regular expression usin {-W,--with-hex}'[Output binary matches in hexadecimal, leaving text matches alone]' {-w,--word-regexp}'[The PATTERN is searched for as a word, such that the matching text is preceded by a non-word character and is followed by a non-word character]' --width'[Truncate the output to NUM visible characters per line]'-{-X,--hex}'[Output matches in hexadecimal]'+{-X,--hex}'[Output matches and matching lines in hexadecimal]' {-x,--line-regexp}'[Select only those matches that exactly match the whole line, as if the patterns are surrounded by ^ and $]' --xml'[Output file matches in XML]' {-Y,--empty}'[Permits empty matches]'
@@ -116,7 +116,7 @@ $matchers{-P,--perl-regexp}'[Interpret PATTERN as a Perl regular expression usin {-W,--with-hex}'[Output binary matches in hexadecimal, leaving text matches alone]' {-w,--word-regexp}'[The PATTERN is searched for as a word, such that the matching text is preceded by a non-word character and is followed by a non-word character]' --width'[Truncate the output to NUM visible characters per line]'-{-X,--hex}'[Output matches in hexadecimal]'+{-X,--hex}'[Output matches and matching lines in hexadecimal]' {-x,--line-regexp}'[Select only those matches that exactly match the whole line, as if the patterns are surrounded by ^ and $]' --xml'[Output file matches in XML]' {-Y,--empty}'[Permits empty matches]'
@@ -116,7 +116,7 @@ $matchers{-P,--perl-regexp}'[Interpret PATTERN as a Perl regular expression usin {-W,--with-hex}'[Output binary matches in hexadecimal, leaving text matches alone]' {-w,--word-regexp}'[The PATTERN is searched for as a word, such that the matching text is preceded by a non-word character and is followed by a non-word character]' --width'[Truncate the output to NUM visible characters per line]'-{-X,--hex}'[Output matches in hexadecimal]'+{-X,--hex}'[Output matches and matching lines in hexadecimal]' {-x,--line-regexp}'[Select only those matches that exactly match the whole line, as if the patterns are surrounded by ^ and $]' --xml'[Output file matches in XML]' {-Y,--empty}'[Permits empty matches]'
@@ -1,6 +1,6 @@ #! /bin/sh # Guess values for system-dependent variables and create Makefiles.-# Generated by GNU Autoconf 2.72 for ugrep 6.5.0.+# Generated by GNU Autoconf 2.72 for ugrep 7.0.0. # # Report bugs to <https://github.com/Genivia/ugrep/issues>. #@@ -606,8 +606,8 @@ MAKEFLAGS= # Identity of this package. PACKAGE_NAME='ugrep' PACKAGE_TARNAME='ugrep'-PACKAGE_VERSION='6.5.0'-PACKAGE_STRING='ugrep 6.5.0'+PACKAGE_VERSION='7.0.0'+PACKAGE_STRING='ugrep 7.0.0' PACKAGE_BUGREPORT='https://github.com/Genivia/ugrep/issues' PACKAGE_URL='https://ugrep.com' @@ -1382,7 +1382,7 @@ if test "$ac_init_help" = "long"; then # Omit some internal or obsolete options to make the list less imposing. # This message is too long to be a string in the A/UX 3.1 sh. cat <<_ACEOF-'configure' configures ugrep 6.5.0 to adapt to many kinds of systems.+'configure' configures ugrep 7.0.0 to adapt to many kinds of systems. Usage: $0 [OPTION]... [VAR=VALUE]... @@ -1453,7 +1453,7 @@ fi if test -n "$ac_init_help"; then case $ac_init_help in- short | recursive ) echo "Configuration of ugrep 6.5.0:";;+ short | recursive ) echo "Configuration of ugrep 7.0.0:";; esac cat <<\_ACEOF @@ -1630,7 +1630,7 @@ fi test -n "$ac_init_help" && exit $ac_status if $ac_init_version; then cat <<\_ACEOF-ugrep configure 6.5.0+ugrep configure 7.0.0 generated by GNU Autoconf 2.72 Copyright (C) 2023 Free Software Foundation, Inc.@@ -2184,7 +2184,7 @@ cat >config.log <<_ACEOF This file contains any messages produced by compilers while running configure, to aid debugging if configure makes a mistake. -It was created by ugrep $as_me 6.5.0, which was+It was created by ugrep $as_me 7.0.0, which was generated by GNU Autoconf 2.72. Invocation command line was $ $0$ac_configure_args_raw@@ -3694,7 +3694,7 @@ fi # Define the identity of the package. PACKAGE='ugrep'- VERSION='6.5.0'+ VERSION='7.0.0' printf "%s\n" "#define PACKAGE \"$PACKAGE\"" >>confdefs.h@@ -11790,7 +11790,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log="-This file was extended by ugrep $as_me 6.5.0, which was+This file was extended by ugrep $as_me 7.0.0, which was generated by GNU Autoconf 2.72. Invocation command line was CONFIG_FILES = $CONFIG_FILES@@ -11863,7 +11863,7 @@ ac_cs_config_escaped=`printf "%s\n" "$ac_cs_config" | sed "s/^ //; s/'/'\\\\\\\\ cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config='$ac_cs_config_escaped' ac_cs_version="\\-ugrep config.status 6.5.0+ugrep config.status 7.0.0 configured by $0, generated by GNU Autoconf 2.72, with options \\"\$ac_cs_config\\"
@@ -1,4 +1,4 @@-AC_INIT([ugrep],[6.5.0],[https://github.com/Genivia/ugrep/issues],[ugrep],[https://ugrep.com])+AC_INIT([ugrep],[7.0.0],[https://github.com/Genivia/ugrep/issues],[ugrep],[https://ugrep.com]) AM_INIT_AUTOMAKE([foreign subdir-objects dist-xz no-dist-gzip]) AC_CONFIG_HEADERS([config.h]) AC_COPYRIGHT([Copyright (C) 2019-2024 Robert van Engelen, Genivia Inc.])
@@ -275,19 +275,27 @@ class AbstractLexer { { out().write(matcher().begin(), matcher().size()); }- /// Returns string with the text matched.+ /// Returns 0-terminated pattern match as a char pointer, does not include matched \0s, this is a constant-time operation. inline const char *text() const /// @returns matched text { return matcher().text(); }- /// Returns string with a copy of the text matched.+#if __cplusplus >= 201703L+ /// Returns the pattern match as a string_view (zero copy), does not include a terminating \0, this is a constant-time operation.+ inline const std::string_view strview() const+ /// @returns string_view with text matched+ {+ return matcher().strview();+ }+#endif+ /// Returns the pattern match as a string, a copy of text(), may include pattern-matched \0s. inline std::string str() const /// @returns matched text { return matcher().str(); }- /// Returns wide string with a copy of the text matched.+ /// Returns the pattern match as a wide string, converted from UTF-8 text(), may include pattern-matched \0s. inline std::wstring wstr() const /// @returns matched text {
@@ -64,7 +64,7 @@ namespace reflex { -/// Check ASCII word-like character `[A-Za-z0-9_]`, permitting the character range 0..303 (0x12F) and EOF.+/// Check ASCII word-like character `[A-Za-z0-9_]`, permitting the character range 0..303 (0x12f) and EOF. inline int isword(int c) ///< Character to check /// @returns nonzero if argument c is in `[A-Za-z0-9_]`, zero otherwise {@@ -120,8 +120,8 @@ class AbstractMatcher { #else static const size_t BOLSZ = REFLEX_BOLSZ; #endif- static const size_t REDO = 0x7FFFFFFF; ///< reflex::Matcher::accept() returns "redo" with reflex::Matcher option "A"- static const size_t EMPTY = 0xFFFFFFFF; ///< accept() returns "empty" last split at end of input+ static const size_t REDO = 0x7fffffff; ///< reflex::Matcher::accept() returns "redo" with reflex::Matcher option "A"+ static const size_t EMPTY = 0xffffffff; ///< accept() returns "empty" last split at end of input }; /// Context returned by before() and after() struct Context {@@ -388,7 +388,8 @@ class AbstractMatcher { } if (!own_) {- max_ = Const::BUFSZ;+ // adjust max to add byte for a terminating \0+ max_ = Const::BUFSZ + 1; #if WITH_REALLOC #if defined(__WIN32__) || defined(_WIN32) || defined(WIN32) || defined(_WIN64) || defined(__BORLANDC__) buf_ = static_cast<char*>(_aligned_malloc(max_, 4096));@@ -440,13 +441,16 @@ class AbstractMatcher { blk_ = blk; if (blk > 0 || eof_ || in.eof()) return true;- size_t n = in.size(); // get the (rest of the) data size, which is 0 if unknown (e.g. reading input from a TTY or a pipe)+ // get the (rest of the) data size, which is 0 if unknown (e.g. reading input from a TTY or a pipe)+ size_t n = in.size(); if (n > 0) {- (void)grow(n + 1); // now attempt to fetch all (remaining) data to store in the buffer, +1 for a final \0+ // now attempt to fetch all (remaining) data to store in the buffer, +1 for a final \0+ (void)grow(n + 1); end_ += get(buf_, n); }- while (in.good()) // there is more to get while good(), e.g. via wrap()+ // there is more to get while good(), e.g. via wrap()+ while (in.good()) { (void)grow(); size_t len = get(buf_ + end_, max_ - end_);@@ -454,8 +458,9 @@ class AbstractMatcher { break; end_ += len; }+ // make sure we have room for a final \0 if (end_ == max_)- (void)grow(1); // make sure we have room for a final \0+ (void)grow(1); eof_ = in.eof(); return eof_; }@@ -602,7 +607,7 @@ class AbstractMatcher { { return txt_ + len_; }- /// Returns 0-terminated string of the text matched, does not include matched \0s, this is a constant-time operation.+ /// Returns 0-terminated pattern match as a char pointer, does not include matched \0s, this is a constant-time operation. inline const char *text() /// @returns 0-terminated const char* string with text matched {@@ -613,19 +618,27 @@ class AbstractMatcher { } return txt_; }- /// Returns the text matched as a string, a copy of text(), may include matched \0s.+#if __cplusplus >= 201703L+ /// Returns the pattern match as a string_view (zero copy), does not include a terminating \0, this is a constant-time operation.+ inline const std::string_view strview() const+ /// @returns string_view with text matched+ {+ return std::string_view(txt_, len_);+ }+#endif+ /// Returns the text matched as a string, a copy of text(), may include pattern-matched \0s. inline std::string str() const /// @returns string with text matched { return std::string(txt_, len_); }- /// Returns the match as a wide string, converted from UTF-8 text(), may include matched \0s.+ /// Returns the pattern match as a wide string, converted from UTF-8 text(), may include pattern-matched \0s. inline std::wstring wstr() const /// @returns wide string with text matched { return wcs(txt_, len_); }- /// Returns the length of the matched text in number of bytes, including matched \0s, a constant-time operation.+ /// Returns the length of the matched text in number of bytes, including pattern-matched \0s, a constant-time operation. inline size_t size() const /// @returns match size in bytes {@@ -638,7 +651,7 @@ class AbstractMatcher { size_t n = 0; const char *e = txt_ + len_; for (const char *s = txt_; s < e; ++s)- n += (*s & 0xC0) != 0x80;+ n += (*s & 0xc0) != 0x80; return n; } /// Returns the first 8-bit character of the text matched.@@ -729,7 +742,7 @@ class AbstractMatcher { else { // count column offset in UTF-8 chars- k += ((*s & 0xC0) != 0x80);+ k += ((*s & 0xc0) != 0x80); } ++s; }@@ -781,7 +794,7 @@ class AbstractMatcher { if (*s == '\t') k += 1 + (~k & m); // count tab spacing else- k += ((*s & 0xC0) != 0x80); // count column offset in UTF-8 chars+ k += ((*s & 0xc0) != 0x80); // count column offset in UTF-8 chars ++s; } cpb_ = txt_;@@ -804,7 +817,7 @@ class AbstractMatcher { if (*s == '\t') k += 1 + (~k & (opt_.T - 1)); // count tab spacing else if (*s != '\r' && *s != '\n')- k += ((*s & 0xC0) != 0x80); // count column offset in UTF-8 chars+ k += ((*s & 0xc0) != 0x80); // count column offset in UTF-8 chars ++s; } return k - n;@@ -830,7 +843,7 @@ class AbstractMatcher { if (*s == '\t') n += 1 + (~n & (opt_.T - 1)); else- n += (*s & 0xC0) != 0x80;+ n += (*s & 0xc0) != 0x80; } return n - m; #endif@@ -855,7 +868,7 @@ class AbstractMatcher { if (*s == '\t') k += 1 + (~k & (opt_.T - 1)); else- k += (*s & 0xC0) != 0x80;+ k += (*s & 0xc0) != 0x80; } return k > 0 ? k - 1 : 0; }@@ -979,7 +992,7 @@ class AbstractMatcher { return EOF; if (static_cast<unsigned char>(*s++ = c) >= 0x80) {- while (((*s++ = get()) & 0xC0) == 0x80)+ while (((*s++ = get()) & 0xc0) == 0x80) continue; got_ = static_cast<unsigned char>(buf_[cur_ = --pos_]); }@@ -1092,21 +1105,34 @@ class AbstractMatcher { } return buf_ + end_; }- /// Return number of bytes available given number of bytes to fetch ahead, limited by input size and buffer size+ /// Return pointer to the end of the match + len after, or at end of file, DANGER: invalidates previous bol() and text() pointers, use aft() before bol(), text(), begin(), and end() when those are used.+ inline const char *aft(size_t len)+ /// @returns pointer to the end of the match + len.+ {+ size_t size = fetch(len);+ return size >= len ? buf_ + pos_ + len : buf_ + pos_ + size;+ }+ /// Return pointer to the begin of the match - len before, or at the begin of the file.+ inline const char *bef(size_t len)+ /// @returns pointer to the begin of the match - len.+ {+ return txt_ >= buf_ + len ? txt_ - len : buf_;+ }+ /// Return number of bytes available given number of bytes to fetch ahead, limited by input size and buffer size, DANGER: invalidates previous bol() and text() pointers, use fetch() before bol(), text(), begin(), and end() when those are used. inline size_t fetch(size_t len) /// @returns number of bytes available after fetching. { DBGLOG("AbstractMatcher::fetch(%zu)", len); if (eof_) return 0;- if (len <= end_ - (txt_ - buf_))- return end_ - (txt_ - buf_);+ if (pos_ + len <= end_)+ return end_ - pos_ ; if (end_ + len + 1 >= max_) (void)grow(); if (end_ + len + 1 >= max_) len = max_ - end_ - 1; end_ += get(buf_ + end_, len);- return avail();+ return end_ - pos_; } /// Returns the number of bytes in the buffer available to search from the current begin()/text() position. inline size_t avail()@@ -1155,7 +1181,7 @@ class AbstractMatcher { reset_text(); const char *e = eol(); // warning: must call eol() before bol() const char *b = bol();- while (b < e && (*b & 0xC0) == 0x80) // make sure we advance forward to valid UTF-8+ while (b < e && (*b & 0xc0) == 0x80) // make sure we advance forward to valid UTF-8 ++b; return wcs(b, e - b); }@@ -1390,16 +1416,20 @@ class AbstractMatcher { cno_ = 0; if (bol_ + Const::BOLSZ - buf_ < txt_ - bol_) {- // this line is very long, so shift all the way to the match instead of to the begin of the last line+ // this line is too long, shift all the way to the match instead of to the begin of the last line DBGLOG("Line in buffer is too long to shift, moving bol position to text match position"); (void)columno(); bol_ = txt_; } size_t gap = bol_ - buf_;- if (gap > 0)+ if (gap > 4096) {+ // make the new end_ address page-aligned to read input, retain some data before bol+ gap -= 4096 - ((reinterpret_cast<std::ptrdiff_t>(buf_ + end_) - gap) & 4095);+ // invoke user-defined handler when defined if (evh_ != NULL) (*evh_)(*this, buf_, gap, num_);+ // update state and shift cur_ -= gap; ind_ -= gap; pos_ -= gap;@@ -1410,15 +1440,19 @@ class AbstractMatcher { num_ += gap; std::memmove(buf_, buf_ + gap, end_); }- if (max_ - end_ >= need)+ if (max_ - end_ >= need + 1) { DBGLOG("Shift buffer to close gap of %zu bytes", gap); } else { size_t newmax = end_ + need;+ // adjust max to page-sized+ --max_; while (max_ < newmax) max_ *= 2;+ // adjust max to add byte for a terminating \0+ ++max_; DBGLOG("Expand buffer to %zu bytes", max_); #if WITH_REALLOC #if defined(__WIN32__) || defined(_WIN32) || defined(WIN32) || defined(_WIN64) || defined(__BORLANDC__)@@ -1520,7 +1554,7 @@ class AbstractMatcher { } #endif }- /// Reset the matched text by removing the terminating \0, which is needed to search for a new match.+ /// Reset the matched text by removing the terminating \0 when applicable, which is needed to search for a new match. inline void reset_text() { if (chr_ != '\0')@@ -1637,7 +1671,7 @@ class PatternMatcher : public AbstractMatcher { : AbstractMatcher(matcher.in, matcher.opt_), pat_(matcher.pat_),- own_(false)+ del_(false) { DBGLOG("PatternMatcher::PatternMatcher(matcher)"); }@@ -1645,7 +1679,7 @@ class PatternMatcher : public AbstractMatcher { virtual ~PatternMatcher() { DBGLOG("PatternMatcher::~PatternMatcher()");- if (own_ && pat_ != NULL)+ if (del_ && pat_ != NULL) delete pat_; } /// Assign a matcher, the underlying pattern object is shared (not deep copied).@@ -1673,10 +1707,10 @@ class PatternMatcher : public AbstractMatcher { DBGLOG("PatternMatcher::pattern()"); if (pat_ != &pattern) {- if (own_ && pat_ != NULL)+ if (del_ && pat_ != NULL) delete pat_; pat_ = &pattern;- own_ = false;+ del_ = false; } return *this; }@@ -1687,10 +1721,10 @@ class PatternMatcher : public AbstractMatcher { DBGLOG("PatternMatcher::pattern()"); if (pat_ != pattern) {- if (own_ && pat_ != NULL)+ if (del_ && pat_ != NULL) delete pat_; pat_ = pattern;- own_ = false;+ del_ = false; } return *this; }@@ -1699,10 +1733,10 @@ class PatternMatcher : public AbstractMatcher { /// @returns this matcher { DBGLOG("PatternMatcher::pattern(\"%s\")", pattern);- if (own_ && pat_ != NULL)+ if (del_ && pat_ != NULL) delete pat_; pat_ = new Pattern(pattern);- own_ = true;+ del_ = true; return *this; } /// Set the pattern from a regex string to use with this matcher.@@ -1710,10 +1744,10 @@ class PatternMatcher : public AbstractMatcher { /// @returns this matcher { DBGLOG("PatternMatcher::pattern(\"%s\")", pattern.c_str());- if (own_ && pat_ != NULL)+ if (del_ && pat_ != NULL) delete pat_; pat_ = new Pattern(pattern);- own_ = true;+ del_ = true; return *this; } /// Returns true if this matcher has a pattern.@@ -1726,7 +1760,7 @@ class PatternMatcher : public AbstractMatcher { inline bool own_pattern() const /// @returns true if this matcher has its own pattern {- return own_ && pat_ != NULL;+ return del_ && pat_ != NULL; } /// Returns a reference to the pattern object associated with this matcher. virtual const Pattern& pattern() const@@ -1744,7 +1778,7 @@ class PatternMatcher : public AbstractMatcher { : AbstractMatcher(input, opt), pat_(pattern),- own_(false)+ del_(false) { } /// Construct a base abstract matcher from a persistent pattern object (that is shared with this class) and an input character sequence. PatternMatcher(@@ -1754,7 +1788,7 @@ class PatternMatcher : public AbstractMatcher { : AbstractMatcher(input, opt), pat_(&pattern),- own_(false)+ del_(false) { } /// Construct a base abstract matcher from a regex pattern string and an input character sequence. PatternMatcher(@@ -1764,7 +1798,7 @@ class PatternMatcher : public AbstractMatcher { : AbstractMatcher(input, opt), pat_(new Pattern(pattern)),- own_(true)+ del_(true) { } /// Construct a base abstract matcher from a regex pattern string and an input character sequence. PatternMatcher(@@ -1774,10 +1808,10 @@ class PatternMatcher : public AbstractMatcher { : AbstractMatcher(input, opt), pat_(new Pattern(pattern)),- own_(true)+ del_(true) { } const Pattern *pat_; ///< points to the pattern object used by the matcher- bool own_; ///< true if PatternMatcher::pat_ was allocated and should be deleted+ bool del_; ///< true if PatternMatcher::pat_ was allocated and should be deleted }; /// A specialization of the pattern matcher class template for std::string, extends abstract matcher base class.@@ -1790,13 +1824,13 @@ class PatternMatcher<std::string> : public AbstractMatcher { : AbstractMatcher(matcher.in, matcher.opt_), pat_(matcher.pat_ != NULL ? new Pattern(*matcher.pat_) : NULL),- own_(matcher.pat_ != NULL)+ del_(matcher.pat_ != NULL) { } /// Delete matcher, deletes pattern when owned virtual ~PatternMatcher() { DBGLOG("PatternMatcher::~PatternMatcher()");- if (own_ && pat_ != NULL)+ if (del_ && pat_ != NULL) delete pat_; } /// Assign a matcher, the underlying pattern string is shared (not deep copied).@@ -1824,10 +1858,10 @@ class PatternMatcher<std::string> : public AbstractMatcher { DBGLOG("Patternatcher::pattern()"); if (pat_ != pattern) {- if (own_ && pat_ != NULL)+ if (del_ && pat_ != NULL) delete pat_; pat_ = pattern;- own_ = false;+ del_ = false; } return *this; }@@ -1836,10 +1870,10 @@ class PatternMatcher<std::string> : public AbstractMatcher { /// @returns this matcher { DBGLOG("Patternatcher::pattern(\"%s\")", pattern);- if (own_ && pat_ != NULL)+ if (del_ && pat_ != NULL) delete pat_; pat_ = new Pattern(pattern);- own_ = true;+ del_ = true; return *this; } /// Set the pattern from a regex string to use with this matcher.@@ -1847,10 +1881,10 @@ class PatternMatcher<std::string> : public AbstractMatcher { /// @returns this matcher { DBGLOG("Patternatcher::pattern(\"%s\")", pattern.c_str());- if (own_ && pat_ != NULL)+ if (del_ && pat_ != NULL) delete pat_; pat_ = new Pattern(pattern);- own_ = true;+ del_ = true; return *this; } /// Returns true if this matcher has a pattern.@@ -1863,7 +1897,7 @@ class PatternMatcher<std::string> : public AbstractMatcher { inline bool own_pattern() const /// @returns true if this matcher has its own pattern {- return own_ && pat_ != NULL;+ return del_ && pat_ != NULL; } /// Returns a reference to the pattern string associated with this matcher. virtual const Pattern& pattern() const@@ -1881,7 +1915,7 @@ class PatternMatcher<std::string> : public AbstractMatcher { : AbstractMatcher(input, opt), pat_(pattern),- own_(false)+ del_(false) { } /// Construct a base abstract matcher from a regex pattern string and an input character sequence. PatternMatcher(@@ -1891,7 +1925,7 @@ class PatternMatcher<std::string> : public AbstractMatcher { : AbstractMatcher(input, opt), pat_(new Pattern(pattern)),- own_(true)+ del_(true) { } /// Construct a base abstract matcher from a regex pattern string and an input character sequence. PatternMatcher(@@ -1901,10 +1935,10 @@ class PatternMatcher<std::string> : public AbstractMatcher { : AbstractMatcher(input, opt), pat_(new Pattern(pattern)),- own_(true)+ del_(true) { } const Pattern *pat_; ///< points to the pattern string used by the matcher- bool own_; ///< true if PatternMatcher::pat_ was allocated and should be deleted+ bool del_; ///< true if PatternMatcher::pat_ was allocated and should be deleted }; } // namespace reflex
@@ -56,6 +56,10 @@ namespace reflex { /** Dynamic bit vectors are stored in Bits objects, which can be manipulated with the usual bit-operations (`|` (bitor), `&` (bitand), `^` (bitxor)).+Supports comparison relations on bit vectors, check if all bits set, check if+any bits are set, flip bits, shift bits left or right, count bits, check if a+bit vectors intersects another, check if a bit vector contains another.+find_first bit, find_next bit. Example:
@@ -316,7 +316,6 @@ class FuzzyMatcher : public Matcher { reset_text(); SaveState sst(ded_); len_ = 0; // split text length starts with 0- anc_ = false; // no word boundary anchor found and applied scan: txt_ = buf_ + cur_; #if !defined(WITH_NO_INDENT)@@ -414,6 +413,8 @@ redo: break; ch = get(); DBGLOG("Get: ch = %d (0x%x)", ch, ch);+ // count down to halt cycling on lone meta edges in repetitions, 5 should suffice+ int metas = 5; // to jump to longest sequence of matching metas jump = Pattern::Const::IMAX; while (true)@@ -492,8 +493,9 @@ redo: #endif case Pattern::META_EOB - Pattern::META_MIN: DBGLOG("EOB? %d", ch);- if (jump == Pattern::Const::IMAX && ch == EOF)+ if (metas > 0 && jump == Pattern::Const::IMAX && ch == EOF) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -502,8 +504,9 @@ redo: continue; case Pattern::META_BOB - Pattern::META_MIN: DBGLOG("BOB? %d", at_bob());- if (jump == Pattern::Const::IMAX && at_bob())+ if (metas > 0 && jump == Pattern::Const::IMAX && at_bob()) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -512,9 +515,10 @@ redo: continue; case Pattern::META_EOL - Pattern::META_MIN: DBGLOG("EOL? %d", ch);- anc_ = true;- if (jump == Pattern::Const::IMAX && (ch == EOF || ch == '\n' || (ch == '\r' && peek() == '\n')))+ if (metas > 0 && jump == Pattern::Const::IMAX &&+ (ch == EOF || ch == '\n' || (ch == '\r' && peek() == '\n'))) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -523,9 +527,9 @@ redo: continue; case Pattern::META_BOL - Pattern::META_MIN: DBGLOG("BOL? %d", bol);- anc_ = true;- if (jump == Pattern::Const::IMAX && bol)+ if (metas > 0 && jump == Pattern::Const::IMAX && bol) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -534,9 +538,9 @@ redo: continue; case Pattern::META_EWE - Pattern::META_MIN: DBGLOG("EWE? %d", at_ewe(ch));- anc_ = true;- if (jump == Pattern::Const::IMAX && at_ewe(ch))+ if (metas > 0 && jump == Pattern::Const::IMAX && at_ewe(ch)) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -545,9 +549,9 @@ redo: continue; case Pattern::META_BWE - Pattern::META_MIN: DBGLOG("BWE? %d", at_bwe(ch));- anc_ = true;- if (jump == Pattern::Const::IMAX && at_bwe(ch))+ if (metas > 0 && jump == Pattern::Const::IMAX && at_bwe(ch)) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -556,9 +560,9 @@ redo: continue; case Pattern::META_EWB - Pattern::META_MIN: DBGLOG("EWB? %d", at_ewb());- anc_ = true;- if (jump == Pattern::Const::IMAX && at_ewb())+ if (metas > 0 && jump == Pattern::Const::IMAX && at_ewb()) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -567,9 +571,9 @@ redo: continue; case Pattern::META_BWB - Pattern::META_MIN: DBGLOG("BWB? %d", at_bwb());- anc_ = true;- if (jump == Pattern::Const::IMAX && at_bwb())+ if (metas > 0 && jump == Pattern::Const::IMAX && at_bwb()) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -578,9 +582,9 @@ redo: continue; case Pattern::META_NWE - Pattern::META_MIN: DBGLOG("NWE? %d", at_nwe(ch));- anc_ = true;- if (jump == Pattern::Const::IMAX && at_nwe(ch))+ if (metas > 0 && jump == Pattern::Const::IMAX && at_nwe(ch)) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -589,9 +593,9 @@ redo: continue; case Pattern::META_NWB - Pattern::META_MIN: DBGLOG("NWB? %d", at_nwb());- anc_ = true;- if (jump == Pattern::Const::IMAX && at_nwb())+ if (metas > 0 && jump == Pattern::Const::IMAX && at_nwb()) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -600,9 +604,9 @@ redo: continue; case Pattern::META_WBE - Pattern::META_MIN: DBGLOG("WBE? %d", at_wbe(ch));- anc_ = true;- if (jump == Pattern::Const::IMAX && at_wbe(ch))+ if (metas > 0 && jump == Pattern::Const::IMAX && at_wbe(ch)) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -611,9 +615,9 @@ redo: continue; case Pattern::META_WBB - Pattern::META_MIN: DBGLOG("WBB? %d", at_wbb());- anc_ = true;- if (jump == Pattern::Const::IMAX && at_wbb())+ if (metas > 0 && jump == Pattern::Const::IMAX && at_wbb()) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -635,27 +639,25 @@ redo: bpos = pos_ - (txt_ - buf_) - 1; DBGLOG("Backtrack point: back = %u pos = %zu", back, bpos); }- pc = pat_->opc_ + jump;- opcode = *pc; } } if (jump == Pattern::Const::IMAX) {- if (back != Pattern::Const::IMAX)+ if (back != Pattern::Const::IMAX && bpos + 1 == pos_ - (txt_ - buf_)) { pc = pat_->opc_ + back; opcode = *pc;+ DBGLOG("Backtrack 1: back = %u pos = %zu ch = %d", back, pos_, ch); back = Pattern::Const::IMAX; } break; }- DBGLOG("Try jump = %u", jump);- if (back == Pattern::Const::IMAX)+ if (back == static_cast<Pattern::Index>(pc - pat_->opc_)) {- back = static_cast<Pattern::Index>(pc - pat_->opc_); bpos = pos_ - (txt_ - buf_) - 1;- DBGLOG("Backtrack point: back = %u pos = %zu", back, bpos);+ DBGLOG("Backtrack update point: back = %u pos = %zu", back, bpos); }+ DBGLOG("Try jump = %u", jump); pc = pat_->opc_ + jump; opcode = *pc; jump = Pattern::Const::IMAX;@@ -665,21 +667,21 @@ redo: } else {- if (ch == EOF)- break;- ch = get(); if (Pattern::is_opcode_halt(opcode)) { if (back != Pattern::Const::IMAX) { pos_ = (txt_ - buf_) + bpos; pc = pat_->opc_ + back;- DBGLOG("Backtrack: back = %u pos = %zu ch = %d", back, pos_, ch);+ DBGLOG("Backtrack 2: back = %u pos = %zu ch = %d", back, pos_, ch); back = Pattern::Const::IMAX; continue; } break; }+ if (ch == EOF)+ break;+ ch = get(); DBGLOG("Get: ch = %d (0x%x) at pos %zu", ch, ch, pos_ - 1); if (bin_ || (ch & 0xC0) != 0x80 || ch == EOF) {@@ -755,7 +757,7 @@ unrolled: { pc = pat_->opc_ + back; pos_ = (txt_ - buf_) + bpos;- DBGLOG("Backtrack: back = %u pos = %zu ch = %d", back, pos_, ch);+ DBGLOG("Backtrack 3: back = %u pos = %zu ch = %d", back, pos_, ch); back = Pattern::Const::IMAX; continue; }@@ -1050,11 +1052,6 @@ unrolled: { if (!at_end()) {- if (anc_)- {- cur_ = txt_ - buf_; // reset current to pattern start when a word boundary was encountered- anc_ = false;- } // fuzzy search with find() can safely advance on a single prefix char of the regex if (pos_ > cur_) {
@@ -37,11 +37,6 @@ #ifndef REFLEX_MATCHER_H #define REFLEX_MATCHER_H -#if !defined(HAVE_NEON)-/// enable predict match patterns after strings longer than 4 chars (this is a bit slower on ARM NEON/AArch64)-#define WITH_STRING_PM-#endif- #include <reflex/absmatcher.h> #include <reflex/pattern.h> #include <stack>@@ -400,61 +395,51 @@ class Matcher : public PatternMatcher<reflex::Pattern> { /// FSM code META EOL. inline bool FSM_META_EOL(int c) {- anc_ = true; return c == EOF || c == '\n' || (c == '\r' && peek() == '\n'); } /// FSM code META BOL. inline bool FSM_META_BOL() {- anc_ = true; return fsm_.bol; } /// FSM code META EWE. inline bool FSM_META_EWE(int c) {- anc_ = true; return at_ewe(c); } /// FSM code META BWE. inline bool FSM_META_BWE(int c) {- anc_ = true; return at_bwe(c); } /// FSM code META EWB. inline bool FSM_META_EWB() {- anc_ = true; return at_ewb(); } /// FSM code META BWB. inline bool FSM_META_BWB() {- anc_ = true; return at_bwb(); } /// FSM code META NWE. inline bool FSM_META_NWE(int c) {- anc_ = true; return at_nwe(c); } /// FSM code META NWB. inline bool FSM_META_NWB() {- anc_ = true; return at_nwb(); } /// FSM code META WBE. inline bool FSM_META_WBE(int c) {- anc_ = true; return at_wbe(c); } /// FSM code META WBB. inline bool FSM_META_WBB() {- anc_ = true; return at_wbb(); } protected:@@ -1290,42 +1275,42 @@ class Matcher : public PatternMatcher<reflex::Pattern> { return isword(c); #endif }- /// Check end of word at match end boundary MATCH\>.+ /// Check end of word at match end boundary MATCH\> at pos. inline bool at_ewe(int c) ///< character last read with get() { return at_we(c, pos_) && at_ew(c); }- /// Check begin of word at match end boundary MATCH\<.+ /// Check begin of word at match end boundary MATCH\< at pos. inline bool at_bwe(int c) ///< character last read with get() { return !at_we(c, pos_) && !at_ew(c); }- /// Check end of word at match begin boundary \>MATCH (after split with len_ > 0 or len_ = 0 for find).+ /// Check end of word at match begin boundary \>MATCH after matching (SPLIT len_ > 0 or len_ = 0 for FIND). inline bool at_ewb() { return !at_bw() && !at_wb(); }- /// Check begin of word at match begin boundary \<MATCH (after split with len_ > 0 or len_ = 0 for find).+ /// Check begin of word at match begin boundary \<MATCH after matching (SPLIT len_ > 0 or len_ = 0 for FIND). inline bool at_bwb() { return at_bw() && at_wb(); }- /// Check not a word boundary at match end MATCH\B.+ /// Check not a word boundary at match end MATCH\B at pos. inline bool at_nwe(int c) ///< character last read with get() { return at_we(c, pos_) != at_ew(c); }- /// Check not a word boundary at match begin \BMATCH (after split with len_ > 0 or len_ = 0 for find).+ /// Check not a word boundary at match begin \BMATCH after matching (SPLIT len_ > 0 or len_ = 0 for FIND). inline bool at_nwb() { return at_bw() != at_wb(); }- /// Check word boundary at match end MATCH\b.+ /// Check word boundary at match end MATCH\b at pos. inline bool at_wbe(int c) ///< character last read with get() { return at_we(c, pos_) == at_ew(c); }- /// Check word boundary at match begin \bMATCH (after split with len_ > 0 or len_ = 0 for find).+ /// Check word boundary at match begin \bMATCH after matching (SPLIT len_ > 0 or len_ = 0 for FIND). inline bool at_wbb() { return at_bw() == at_wb();@@ -1346,66 +1331,71 @@ class Matcher : public PatternMatcher<reflex::Pattern> { void simd_init_advance_avx512bw(); /// Default method is none (unset) bool advance_none(size_t loc);- // Single needle (SSE2/NEON) methods+ // Single needle SSE2/NEON methods+ bool advance_pattern_pin1_one(size_t loc); bool advance_pattern_pin1_pma(size_t loc);- bool advance_pattern_pin1_pmh(size_t loc);- // Generated multi-needle SSE2 or NEON methods+ template <uint8_t MIN> bool advance_pattern_pin1_pmh(size_t loc);+ // Generated multi-needle SSE2/NEON methods bool advance_pattern_pin2_one(size_t loc); bool advance_pattern_pin2_pma(size_t loc);- bool advance_pattern_pin2_pmh(size_t loc);+ template <uint8_t MIN> bool advance_pattern_pin2_pmh(size_t loc); bool advance_pattern_pin3_one(size_t loc); bool advance_pattern_pin3_pma(size_t loc);- bool advance_pattern_pin3_pmh(size_t loc);+ template <uint8_t MIN> bool advance_pattern_pin3_pmh(size_t loc); bool advance_pattern_pin4_one(size_t loc); bool advance_pattern_pin4_pma(size_t loc);- bool advance_pattern_pin4_pmh(size_t loc);+ template <uint8_t MIN> bool advance_pattern_pin4_pmh(size_t loc); bool advance_pattern_pin5_one(size_t loc); bool advance_pattern_pin5_pma(size_t loc);- bool advance_pattern_pin5_pmh(size_t loc);+ template <uint8_t MIN> bool advance_pattern_pin5_pmh(size_t loc); bool advance_pattern_pin6_one(size_t loc); bool advance_pattern_pin6_pma(size_t loc);- bool advance_pattern_pin6_pmh(size_t loc);+ template <uint8_t MIN> bool advance_pattern_pin6_pmh(size_t loc); bool advance_pattern_pin7_one(size_t loc); bool advance_pattern_pin7_pma(size_t loc);- bool advance_pattern_pin7_pmh(size_t loc);+ template <uint8_t MIN> bool advance_pattern_pin7_pmh(size_t loc); bool advance_pattern_pin8_one(size_t loc); bool advance_pattern_pin8_pma(size_t loc);- bool advance_pattern_pin8_pmh(size_t loc);+ template <uint8_t MIN> bool advance_pattern_pin8_pmh(size_t loc); // Single needle AVX2 methods bool simd_advance_pattern_pin1_pma_avx2(size_t loc);- bool simd_advance_pattern_pin1_pmh_avx2(size_t loc);+ template <uint8_t MIN> bool simd_advance_pattern_pin1_pmh_avx2(size_t loc); // Generated AVX2 multi-needle methods bool simd_advance_pattern_pin2_one_avx2(size_t loc); bool simd_advance_pattern_pin2_pma_avx2(size_t loc);- bool simd_advance_pattern_pin2_pmh_avx2(size_t loc);+ template <uint8_t MIN> bool simd_advance_pattern_pin2_pmh_avx2(size_t loc); bool simd_advance_pattern_pin3_one_avx2(size_t loc); bool simd_advance_pattern_pin3_pma_avx2(size_t loc);- bool simd_advance_pattern_pin3_pmh_avx2(size_t loc);+ template <uint8_t MIN> bool simd_advance_pattern_pin3_pmh_avx2(size_t loc); bool simd_advance_pattern_pin4_one_avx2(size_t loc); bool simd_advance_pattern_pin4_pma_avx2(size_t loc);- bool simd_advance_pattern_pin4_pmh_avx2(size_t loc);+ template <uint8_t MIN> bool simd_advance_pattern_pin4_pmh_avx2(size_t loc); bool simd_advance_pattern_pin5_one_avx2(size_t loc); bool simd_advance_pattern_pin5_pma_avx2(size_t loc);- bool simd_advance_pattern_pin5_pmh_avx2(size_t loc);+ template <uint8_t MIN> bool simd_advance_pattern_pin5_pmh_avx2(size_t loc); bool simd_advance_pattern_pin6_one_avx2(size_t loc); bool simd_advance_pattern_pin6_pma_avx2(size_t loc);- bool simd_advance_pattern_pin6_pmh_avx2(size_t loc);+ template <uint8_t MIN> bool simd_advance_pattern_pin6_pmh_avx2(size_t loc); bool simd_advance_pattern_pin7_one_avx2(size_t loc); bool simd_advance_pattern_pin7_pma_avx2(size_t loc);- bool simd_advance_pattern_pin7_pmh_avx2(size_t loc);+ template <uint8_t MIN> bool simd_advance_pattern_pin7_pmh_avx2(size_t loc); bool simd_advance_pattern_pin8_one_avx2(size_t loc); bool simd_advance_pattern_pin8_pma_avx2(size_t loc);- bool simd_advance_pattern_pin8_pmh_avx2(size_t loc);+ template <uint8_t MIN> bool simd_advance_pattern_pin8_pmh_avx2(size_t loc); bool simd_advance_pattern_pin16_one_avx2(size_t loc); bool simd_advance_pattern_pin16_pma_avx2(size_t loc);- bool simd_advance_pattern_pin16_pmh_avx2(size_t loc);- // Minimal long patterns+ template <uint8_t MIN> bool simd_advance_pattern_pin16_pmh_avx2(size_t loc);+ // Minimal patterns bool advance_pattern_min1(size_t loc); bool advance_pattern_min2(size_t loc); bool advance_pattern_min3(size_t loc);- bool advance_pattern_min4(size_t loc);- // Minimal long patterns- bool advance_pattern(size_t loc);+ template <uint8_t MIN> bool advance_pattern_min4(size_t loc);+#ifdef WITH_BITAP_AVX2 // use in case vectorized bitap (hashed) is faster than serial version (typically not!!)+ // Minimal 4 byte long patterns using bitap hashed pairs with AVX2+ template <uint8_t MIN> bool simd_advance_pattern_min4_avx2(size_t loc);+#endif+ // Minimal patterns+ bool advance_pattern_pma(size_t loc); // One char methods bool advance_char(size_t loc); bool advance_char_pma(size_t loc);@@ -1424,34 +1414,24 @@ class Matcher : public PatternMatcher<reflex::Pattern> { template <uint8_t LEN> bool simd_advance_chars_pmh_avx512bw(size_t loc); // String methods bool advance_string(size_t loc);-#if defined(WITH_STRING_PM) bool advance_string_pma(size_t loc); bool advance_string_pmh(size_t loc);-#endif // String AVX2 metnods bool simd_advance_string_avx2(size_t loc);-#if defined(WITH_STRING_PM) bool simd_advance_string_pma_avx2(size_t loc); bool simd_advance_string_pmh_avx2(size_t loc);-#endif // String AVX512BW metnods bool simd_advance_string_avx512bw(size_t loc);-#if defined(WITH_STRING_PM) bool simd_advance_string_pma_avx512bw(size_t loc); bool simd_advance_string_pmh_avx512bw(size_t loc);-#endif // String NEON metnods bool simd_advance_string_neon(const char *&s, const char *e);-#if defined(WITH_STRING_PM) bool simd_advance_string_pma_neon(const char *&s, const char *e); bool simd_advance_string_pmh_neon(const char *&s, const char *e);-#endif // Fallback Boyer-Moore methods bool advance_string_bm(size_t loc);-#if defined(WITH_STRING_PM) bool advance_string_bm_pma(size_t loc); bool advance_string_bm_pmh(size_t loc);-#endif #if !defined(WITH_NO_INDENT) /// Update indentation column counter for indent() and dedent(). inline void newline()@@ -1491,7 +1471,6 @@ class Matcher : public PatternMatcher<reflex::Pattern> { FSM fsm_; ///< local state for FSM code bool (Matcher::* adv_)(size_t loc); ///< advance FIND function pointer bool mrk_; ///< indent \i or dedent \j in pattern found: should check and update indent stops- bool anc_; ///< match is anchored, advance slowly to retry when searching }; } // namespace reflex
@@ -43,6 +43,7 @@ #include <reflex/input.h> #include <reflex/ranges.h> #include <reflex/setop.h>+#include <cstdint> #include <cctype> #include <cstring> #include <iostream>@@ -53,6 +54,10 @@ #include <array> #include <bitset> #include <vector>+#include <stack>++// ugrep 7.0: use vectorized bitap (hashed) with AVX2, but it is not faster (in our extensive emperical testing)+// #define WITH_BITAP_AVX2 // ugrep 3.7.0a: use a map to construct fixed string pattern trees // #define WITH_TREE_MAP@@ -70,21 +75,24 @@ class Pattern { friend class Matcher; ///< permit access by the reflex::Matcher engine friend class FuzzyMatcher; ///< permit access by the reflex::FuzzyMatcher engine public:+ typedef uint8_t Bitap; ///< bitap bitmask, may change in a future update typedef uint8_t Pred; ///< predict match bits- typedef uint32_t Hash; ///< hash value type, max value is Const::HASH+ typedef uint16_t Hash; ///< hash value type, max value is Const::HASH typedef uint32_t Index; ///< index into opcodes array Pattern::opc_ and subpattern indexing typedef uint32_t Accept; ///< group capture index typedef uint32_t Opcode; ///< 32 bit opcode word typedef void (*FSM)(class Matcher&); ///< function pointer to FSM code /// Common constants. struct Const {- static const Index IMAX = 0xFFFFFFFF; ///< max index, also serves as a marker- static const Index GMAX = 0xFEFFFF; ///< max goto index- static const Accept AMAX = 0xFDFFFF; ///< max accept- static const Index LMAX = 0xFAFFFF; ///< max lookahead index- static const Index LONG = 0xFFFE; ///< LONG marker for 64 bit opcodes, must be HALT-1- static const Index HALT = 0xFFFF; ///< HALT marker for GOTO opcodes, must be 16 bit max+ static const Index IMAX = 0xffffffff; ///< max index, also serves as a marker+ static const Index GMAX = 0xfeffff; ///< max goto index+ static const Accept AMAX = 0xfdffff; ///< max accept+ static const Index LMAX = 0xfaffff; ///< max lookahead index+ static const Index LONG = 0xfffe; ///< LONG marker for 64 bit opcodes, must be HALT-1+ static const Index HALT = 0xffff; ///< HALT marker for GOTO opcodes, must be 16 bit max static const Hash HASH = 0x1000; ///< size of the predict match array+ static const Hash BTAP = 0x0800; ///< size of the bitap hashed character pairs array+ static const Bitap BITS = 8; ///< number of bitap bits, may change in a future update }; /// Construct an unset pattern. Pattern()@@ -357,20 +365,22 @@ class Pattern { /// Returns true when match is predicted, based on s[0..3..e-1] (e >= s + 4). inline bool predict_match(const char *s, size_t n) const {- Hash h = static_cast<uint8_t>(*s);- Hash f = pmh_[h] & 1;+ uint32_t h = static_cast<uint8_t>(*s);+ uint32_t f = pmh_[h] & 1; h = hash(h, static_cast<uint8_t>(*++s)); f |= pmh_[h] & 2; h = hash(h, static_cast<uint8_t>(*++s)); f |= pmh_[h] & 4; h = hash(h, static_cast<uint8_t>(*++s)); f |= pmh_[h] & 8;+ if (f != 0)+ return false; const char *e = s + n - 3;- Hash m = 16;- while (f == 0 && ++s < e)+ uint32_t m = 16;+ while (++s < e) { h = hash(h, static_cast<uint8_t>(*s));- f = pmh_[h] & m;+ f |= pmh_[h] & m; m <<= 1; } return f == 0;@@ -378,14 +388,14 @@ class Pattern { /// Returns true when match is predicted using my PM4 logic. inline bool predict_match(const char *s) const {- uint8_t b0 = s[0];- uint8_t b1 = s[1];- uint8_t b2 = s[2];- uint8_t b3 = s[3];- Hash h1 = hash(b0, b1);- Hash h2 = hash(h1, b2);- Hash h3 = hash(h2, b3);- Pred p = (pma_[b0] & 0xc0) | (pma_[h1] & 0x30) | (pma_[h2] & 0x0c) | (pma_[h3] & 0x03);+ uint8_t c0 = static_cast<uint8_t>(s[0]);+ uint8_t c1 = static_cast<uint8_t>(s[1]);+ uint8_t c2 = static_cast<uint8_t>(s[2]);+ uint8_t c3 = static_cast<uint8_t>(s[3]);+ uint32_t h1 = hash(c0, c1);+ uint32_t h2 = hash(h1, c2);+ uint32_t h3 = hash(h2, c3);+ Pred p = (pma_[c0] & 0xc0) | (pma_[h1] & 0x30) | (pma_[h2] & 0x0c) | (pma_[h3] & 0x03); Pred m = ((((((p >> 2) | p) >> 2) | p) >> 1) | p); return m != 0xff; }@@ -456,8 +466,8 @@ class Pattern { bool any() const { return b[0] | b[1] | b[2] | b[3] | b[4]; } bool intersects(const Chars& c) const { return (b[0] & c.b[0]) | (b[1] & c.b[1]) | (b[2] & c.b[2]) | (b[3] & c.b[3]) | (b[4] & c.b[4]); } bool contains(const Chars& c) const { return !(c - *this).any(); }- bool contains(Char c) const { return b[c >> 6] & (1ULL << (c & 0x3F)); }- Chars& add(Char c) { b[c >> 6] |= 1ULL << (c & 0x3F); return *this; }+ bool contains(Char c) const { return b[c >> 6] & (1ULL << (c & 0x3f)); }+ Chars& add(Char c) { b[c >> 6] |= 1ULL << (c & 0x3f); return *this; } Chars& add(Char lo, Char hi) { while (lo <= hi) add(lo++); return *this; } Chars& flip() { b[0] = ~b[0]; b[1] = ~b[1]; b[2] = ~b[2]; b[3] = ~b[3]; b[4] = ~b[4]; return *this; } Chars& flip256() { b[0] = ~b[0]; b[1] = ~b[1]; b[2] = ~b[2]; b[3] = ~b[3]; return *this; }@@ -488,9 +498,9 @@ class Pattern { /// Finite state machine construction position information. struct Position { typedef uint64_t value_type;- static const Iter MAXITER = 0xFFFF;- static const Location MAXLOC = 0xFFFFFFFFUL;- static const value_type NPOS = 0xFFFFFFFFFFFFFFFFULL;+ static const Iter MAXITER = 0xffff;+ static const Location MAXLOC = 0xffffffffUL;+ static const value_type NPOS = 0xffffffffffffffffULL; static const value_type RES1 = 1ULL << 48; ///< reserved static const value_type RES2 = 1ULL << 49; ///< reserved static const value_type RES3 = 1ULL << 50; ///< reserved@@ -509,11 +519,11 @@ class Pattern { Position ticked(bool b) const { return b ? Position(k | TICKED) : Position(k & ~TICKED); } Position anchor(bool b) const { return b ? Position(k | ANCHOR) : Position(k & ~ANCHOR); } Position accept(bool b) const { return b ? Position(k | ACCEPT) : Position(k & ~ACCEPT); }- Position lazy(Lazy l) const { return Position((k & 0x00FFFFFFFFFFFFFFULL) | static_cast<value_type>(l) << 56); }- Position pos() const { return Position(k & 0x0000FFFFFFFFFFFFULL); }+ Position lazy(Lazy l) const { return Position((k & 0x00ffffffffffffffULL) | static_cast<value_type>(l) << 56); }+ Position pos() const { return Position(k & 0x0000ffffffffffffULL); } Location loc() const { return static_cast<Location>(k); } Accept accepts() const { return static_cast<Accept>(k); }- Iter iter() const { return static_cast<Index>((k >> 32) & 0xFFFF); }+ Iter iter() const { return static_cast<Index>((k >> 32) & 0xffff); } bool negate() const { return (k & NEGATE) != 0; } bool ticked() const { return (k & TICKED) != 0; } bool anchor() const { return (k & ANCHOR) != 0; }@@ -683,6 +693,112 @@ class Pattern { Accept accept; ///< nonzero if final state, the index of an accepted/captured subpattern bool redo; ///< true if this is a final state of a negative pattern };+ // transitive closure of DFA meta edges; no follow metas to accepting states and no follow cycles+ struct MetaEdgesClosure {+ MetaEdgesClosure(State& state)+ {+ edge = state.edges.begin();+ end = state.edges.end();+ accept = state.accept > 0 || state.edges.empty();+ walk();+ }+ MetaEdgesClosure(State *state)+ {+ edge = state->edges.begin();+ end = state->edges.end();+ accept = state->accept > 0 || state->edges.empty();+ walk();+ }+ ~MetaEdgesClosure()+ {+ // clean up markers+ while (!done())+ ++edge;+ }+ MetaEdgesClosure& operator++()+ {+ ++edge;+ walk();+ return *this;+ }+ Char lo() const+ {+ return edge->first;+ }+ Char hi() const+ {+ return edge->second.first;+ }+ State *state() const+ {+ return edge->second.second; // target state is non-NULL by walk()+ }+ bool accepting() const+ {+ return accept;+ }+ bool next_accepting() const+ {+ if (state() == NULL || state()->accept > 0 || state()->edges.empty())+ return true;+ return is_meta(state()->edges.rbegin()->first) && MetaEdgesClosure(state()).find_accepting();+ }+ bool find_accepting()+ {+ while (!done())+ ++edge;+ return accepting();+ }+ bool done()+ {+ while (edge == end)+ {+ if (stack.empty())+ return true;+ // restore previous iterators+ edge = stack.top().first;+ end = stack.top().second;+ stack.pop();+ // unmark state visited+ state()->index = 0;+ ++edge;+ }+ return false;+ }+ void walk()+ {+ if (done())+ return;+ // walk the DFA graph acyclicly until non-meta edge to a non-NULL state+ while (is_meta(lo()) || state() == NULL)+ {+ // find non-empty non-visited non-accepting state on a meta edge+ State *next_state;+ do+ {+ next_state = state();+ if (next_state == NULL || next_state->accept > 0 || next_state->edges.empty())+ accept = true;+ else if (next_state->index != 1)+ break;+ ++edge;+ if (done())+ return;+ } while (is_meta(lo()) || next_state == NULL);+ // save current iterators+ stack.push(std::pair<State::Edges::const_iterator,State::Edges::const_iterator>(edge,end));+ // mark state as visited+ next_state->index = 1;+ // new iterators+ edge = next_state->edges.begin();+ end = next_state->edges.end();+ }+ }+ std::stack<std::pair<State::Edges::const_iterator,State::Edges::const_iterator> > stack;+ State::Edges::const_iterator edge;+ State::Edges::const_iterator end;+ bool accept;+ }; typedef std::list<State*> List; static const uint16_t ALLOC = 1024; ///< allocate 1024 DFA states at a time, to improve performance static const uint16_t MAX_DEPTH = 256; ///< analyze DFA up to states this deep to improve predict match@@ -824,13 +940,13 @@ class Pattern { META_EWE = 0x108, ///< end of word at end `x\>` // line and buffer boundaries META_BOL = 0x109, ///< begin of line `^`- META_EOL = 0x10A, ///< end of line `$`- META_BOB = 0x10B, ///< begin of buffer `\A`- META_EOB = 0x10C, ///< end of buffer `\Z`+ META_EOL = 0x10a, ///< end of line `$`+ META_BOB = 0x10b, ///< begin of buffer `\A`+ META_EOB = 0x10c, ///< end of buffer `\Z` // indent boundaries- META_UND = 0x10D, ///< undent boundary `\k`- META_IND = 0x10E, ///< indent boundary `\i` (must be one but the largest META code)- META_DED = 0x10F, ///< dedent boundary `\j` (must be the largest META code)+ META_UND = 0x10d, ///< undent boundary `\k`+ META_IND = 0x10e, ///< indent boundary `\i` (must be one but the largest META code)+ META_DED = 0x10f, ///< dedent boundary `\j` (must be the largest META code) // end of boundaries META_MAX ///< max meta characters };@@ -910,7 +1026,7 @@ class Pattern { const Positions& pos, Positions& pos1) const; void greedy(Positions& pos) const;- void trim_anchors(Positions& follow, const Position p) const;+ void trim_anchors(Positions& follow) const; void trim_lazy(Positions *pos, const Lazypos& lazypos) const; void compile_transition( DFA::State *state,@@ -948,11 +1064,9 @@ class Pattern { void export_code() const; void analyze_dfa(DFA::State *start); void gen_min(std::set<DFA::State*>& states);- void gen_min_start(std::set<DFA::State*>& states, std::set<DFA::State*>& next);- void gen_min_transitions(size_t level, std::set<DFA::State*>& next); void gen_predict_match(std::set<DFA::State*>& states);- void gen_predict_match_start(std::set<DFA::State*>& states, std::map<DFA::State*,ORanges<Hash> >& hashes);- void gen_predict_match_transitions(size_t level, DFA::State *state, const ORanges<Hash>& labels, std::map<DFA::State*,ORanges<Hash> >& hashes);+ void gen_predict_match_start(std::set<DFA::State*>& states, std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >& first_hashes);+ void gen_predict_match_transitions(size_t level, DFA::State *state, const std::pair<ORanges<Hash>,ORanges<Char> >& previous, std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >& level_hashes); void gen_match_hfa(DFA::State *start); void gen_match_hfa_start(DFA::State *start, HFA::State& index, HFA::StateHashes& hashes); bool gen_match_hfa_transitions(size_t level, size_t& max_level, DFA::State *state, const HFA::HashRanges& previous, HFA::State& index, HFA::StateHashes& hashes);@@ -1040,23 +1154,23 @@ class Pattern { } static inline Opcode opcode_long(Index index) {- return 0xFF000000 | (index & 0xFFFFFF); // index <= Const::GMAX (0xFEFFFF max)+ return 0xff000000 | (index & 0xffffff); // index <= Const::GMAX (0xfeffff max) } static inline Opcode opcode_take(Index index) {- return 0xFE000000 | (index & 0xFFFFFF); // index <= Const::AMAX (0xFDFFFF max)+ return 0xfe000000 | (index & 0xffffff); // index <= Const::AMAX (0xfdffff max) } static inline Opcode opcode_redo() {- return 0xFD000000;+ return 0xfd000000; } static inline Opcode opcode_tail(Index index) {- return 0xFC000000 | (index & 0xFFFFFF); // index <= Const::LMAX (0xFAFFFF max)+ return 0xfc000000 | (index & 0xffffff); // index <= Const::LMAX (0xfaffff max) } static inline Opcode opcode_head(Index index) {- return 0xFB000000 | (index & 0xFFFFFF); // index <= Const::LMAX (0xFAFFFF max)+ return 0xfb000000 | (index & 0xffffff); // index <= Const::LMAX (0xfaffff max) } static inline Opcode opcode_goto( Char lo,@@ -1067,45 +1181,45 @@ class Pattern { } static inline Opcode opcode_halt() {- return 0x00FFFFFF;+ return 0x00ffffff; } static inline bool is_opcode_long(Opcode opcode) {- return (opcode & 0xFF000000) == 0xFF000000;+ return (opcode & 0xff000000) == 0xff000000; } static inline bool is_opcode_take(Opcode opcode) {- return (opcode & 0xFE000000) == 0xFE000000;+ return (opcode & 0xfe000000) == 0xfe000000; } static inline bool is_opcode_redo(Opcode opcode) {- return opcode == 0xFD000000;+ return opcode == 0xfd000000; } static inline bool is_opcode_tail(Opcode opcode) {- return (opcode & 0xFF000000) == 0xFC000000;+ return (opcode & 0xff000000) == 0xfc000000; } static inline bool is_opcode_head(Opcode opcode) {- return (opcode & 0xFF000000) == 0xFB000000;+ return (opcode & 0xff000000) == 0xfb000000; } static inline bool is_opcode_halt(Opcode opcode) {- return opcode == 0x00FFFFFF;+ return opcode == 0x00ffffff; } static inline bool is_opcode_goto(Opcode opcode) {- return (opcode << 8) >= (opcode & 0xFF000000);+ return (opcode << 8) >= (opcode & 0xff000000); } static inline bool is_opcode_meta(Opcode opcode) {- return (opcode & 0x00FF0000) == 0x00000000 && (opcode >> 24) > 0;+ return (opcode & 0x00ff0000) == 0x00000000 && (opcode >> 24) > 0; } static inline bool is_opcode_goto( Opcode opcode, unsigned char c) {- return c >= (opcode >> 24) && c <= ((opcode >> 16) & 0xFF);+ return c >= (opcode >> 24) && c <= ((opcode >> 16) & 0xff); } static inline Char meta_of(Opcode opcode) {@@ -1117,19 +1231,19 @@ class Pattern { } static inline Char hi_of(Opcode opcode) {- return is_opcode_meta(opcode) ? meta_of(opcode) : (opcode >> 16) & 0xFF;+ return is_opcode_meta(opcode) ? meta_of(opcode) : (opcode >> 16) & 0xff; } static inline Index index_of(Opcode opcode) {- return opcode & 0xFFFF;+ return opcode & 0xffff; } static inline Index long_index_of(Opcode opcode) {- return opcode & 0xFFFFFF;+ return opcode & 0xffffff; } static inline Lookahead lookahead_of(Opcode opcode) {- return opcode & 0xFFFF;+ return opcode & 0xffff; } /// convert to lower case if c is a letter a-z, A-Z. static inline Char lowercase(Char c)@@ -1142,12 +1256,17 @@ class Pattern { return static_cast<unsigned char>(c & ~0x20); } /// predict match hash 0 <= hash() < Const::HASH.- static inline Hash hash(Hash h, uint8_t b)+ static inline uint32_t hash(uint32_t h, uint8_t b) { return ((h << 3) ^ b) & (Const::HASH - 1); }+ /// bitap character pairs hash+ static inline uint32_t bihash(uint8_t a, uint8_t b)+ {+ return (a ^ (b << 6)) & (Const::BTAP - 1);+ } /// file indexing hash 0 <= indexhash() < 65536, must be additive: indexhash(x,b+1) = indexhash(x,b)+1 modulo 2^16.- static inline Hash indexhash(Hash h, uint8_t b)+ static inline uint32_t indexhash(Hash h, uint8_t b) { return static_cast<uint16_t>((h << 6) - h - h - h + b); }@@ -1168,16 +1287,22 @@ class Pattern { const Opcode *opc_; ///< points to the table with compiled finite state machine opcodes FSM fsm_; ///< function pointer to FSM code Index nop_; ///< number of opcodes generated- Index cut_; ///< DFA s-t cut to improve predict match and HFA accuracy together with lbk_ and cbk_+ Index cut_; ///< DFA s-t cut to improve predict match and HFA accuracy with lbk_ and cbk_ size_t len_; ///< length of chr_[], less or equal to 255 size_t min_; ///< patterns after the prefix are at least this long but no more than 8 size_t pin_; ///< number of needles, 0 to 16 std::bitset<256> cbk_; ///< characters to look back over when lbk_ > 0, never includes \n std::bitset<256> fst_; ///< the beginning characters of the pattern- char chr_[256]; ///< pattern prefix string or character needles for needle-based search- Pred bit_[256]; ///< bitap array- Pred pmh_[Const::HASH]; ///< predict-match hash array- Pred pma_[Const::HASH]; ///< predict-match array+ char chr_[256]; ///< pattern prefix string or character needles for needle-based search+ Bitap bit_[256]; ///< bitsets of characters for the first positions (one position per bit)+ Bitap tap_[Const::BTAP]; ///< bitap hashed character pairs array+#ifdef WITH_BITAP_AVX2 // in case vectorized bitap (hashed) is faster than serial version (typically not!)+#if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2)+ uint16_t vtp_[Const::BTAP * 4]; ///< AVX2 vectorized bitap hashed character pairs array+#endif+#endif+ Pred pmh_[Const::HASH]; ///< predict-match bloom filter hash up to first 8 positions+ Pred pma_[Const::HASH]; ///< predict-match 4 (PM4) array uint16_t lbk_; ///< lookback distance or 0xffff unlimited lookback or 0 for no lookback (empty cbk_) uint16_t lbm_; ///< loopback minimum distance when lbk_ > 0 uint16_t lcp_; ///< primary least common character position in the pattern or 0xffff@@ -1189,7 +1314,7 @@ class Pattern { float ems_; ///< ms elapsed time to compile DFA edges float wms_; ///< ms elapsed time to assemble code words float ams_; ///< ms elapsed time to analyze DFA for predict match and HFA- size_t npy_; ///< entropy derived from the bitap array bit_[]+ uint16_t npy_; ///< entropy derived from the bitap array bit_[] bool one_; ///< true if matching one string stored in chr_[] without meta/anchors bool bol_; ///< true if matching all patterns at the begin of a line with anchor ^ };
@@ -49,6 +49,9 @@ # include <emmintrin.h> #elif defined(HAVE_NEON) # include <arm_neon.h>+# if defined(__ARM_ACLE)+# include <arm_acle.h>+# endif #endif #if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2)@@ -148,14 +151,28 @@ extern bool simd_isutf8_avx2(const char *& b, const char *e); } // namespace reflex +#elif defined(HAVE_NEON)++// If we have hardware clz (but it is rather slow)+#if defined(__ARM_ACLE) && defined(__ARM_FEATURE_CLZ)+inline uint32_t ctz(uint32_t x)+{+ return __clz(__rbit(x));+}+inline uint32_t ctzl(uint64_t x)+{+ return __clzl(__rbitl(x));+}+#endif+ #endif namespace reflex { -// Count newlines in string s up to t-extern size_t nlcount(const char *s, const char *t);+/// Count newlines in string s up to position e in the string+extern size_t nlcount(const char *s, const char *e); -// Check if valid UTF-8 encoding and does not include a NUL, but accept surrogates and 3/4 byte overlongs+/// Check if valid UTF-8 encoding and does not include a NUL, but accept surrogates and 3/4 byte overlongs extern bool isutf8(const char *s, const char *e); } // namespace reflex
@@ -37,6 +37,7 @@ #ifndef REFLEX_UTF8_H #define REFLEX_UTF8_H +#include <cstddef> #include <cstring> #include <string>
@@ -2200,6 +2200,7 @@ std::string convert(const char *pattern, const char *signature, convert_flag_typ break; case '^': anc = true;+ beg = false; break; case '$': if (beg && (flags & convert_flag::lex))
@@ -44,7 +44,6 @@ size_t Matcher::match(Method method) DBGLOG("BEGIN Matcher::match()"); reset_text(); len_ = 0; // split text length starts with 0- anc_ = false; // no word boundary anchor found and applied size_t retry = 0; // retry regex match at lookback positions for predicted matches scan: txt_ = buf_ + cur_;@@ -87,7 +86,7 @@ redo: if (pat_->opc_ != NULL) { const Pattern::Opcode *pc = pat_->opc_;- Pattern::Index back = Pattern::Const::IMAX; // where to jump back to+ Pattern::Index back = Pattern::Const::IMAX; // where to jump back to when backtracking over meta edges size_t bpos = 0; // backtrack position in the input while (true) {@@ -98,7 +97,7 @@ redo: { switch (opcode >> 24) {- case 0xFE: // TAKE+ case 0xfe: // TAKE { int c; if (!opt_.W || (c = peek(), at_we(c, pos_)))@@ -110,13 +109,13 @@ redo: } ++pc; continue;- case 0xFD: // REDO+ case 0xfd: // REDO cap_ = Const::REDO; DBGLOG("Redo"); cur_ = pos_; ++pc; continue;- case 0xFC: // TAIL+ case 0xfc: // TAIL { Pattern::Lookahead la = Pattern::lookahead_of(opcode); DBGLOG("Tail: %u", la);@@ -125,7 +124,7 @@ redo: ++pc; continue; }- case 0xFB: // HEAD+ case 0xfb: // HEAD { Pattern::Lookahead la = Pattern::lookahead_of(opcode); DBGLOG("Head: lookahead[%u] = %zu", la, pos_ - (txt_ - buf_));@@ -153,6 +152,8 @@ redo: break; ch = get(); DBGLOG("Get: ch = %d", ch);+ // count down to halt cycling on lone meta edges in repetitions, 5 should suffice+ int metas = 5; // to jump to longest sequence of matching metas jump = Pattern::Const::IMAX; while (true)@@ -164,7 +165,7 @@ redo: // we no longer have to pass through all if jump and back are set switch (opcode >> 24) {- case 0xFE: // TAKE+ case 0xfe: // TAKE if (!opt_.W || at_we(ch, pos_ - 1)) { cap_ = Pattern::long_index_of(opcode);@@ -175,7 +176,7 @@ redo: } opcode = *++pc; continue;- case 0xFD: // REDO+ case 0xfd: // REDO cap_ = Const::REDO; DBGLOG("Redo"); cur_ = pos_;@@ -183,7 +184,7 @@ redo: --cur_; // must unget one char opcode = *++pc; continue;- case 0xFC: // TAIL+ case 0xfc: // TAIL { Pattern::Lookahead la = Pattern::lookahead_of(opcode); DBGLOG("Tail: %u", la);@@ -192,7 +193,7 @@ redo: opcode = *++pc; continue; }- case 0xFB: // HEAD+ case 0xfb: // HEAD opcode = *++pc; continue; #if !defined(WITH_NO_INDENT)@@ -231,8 +232,9 @@ redo: #endif case Pattern::META_EOB - Pattern::META_MIN: DBGLOG("EOB? %d", ch);- if (jump == Pattern::Const::IMAX && ch == EOF)+ if (metas > 0 && jump == Pattern::Const::IMAX && ch == EOF) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -241,8 +243,9 @@ redo: continue; case Pattern::META_BOB - Pattern::META_MIN: DBGLOG("BOB? %d", at_bob());- if (jump == Pattern::Const::IMAX && at_bob())+ if (metas > 0 && jump == Pattern::Const::IMAX && at_bob()) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -251,10 +254,10 @@ redo: continue; case Pattern::META_EOL - Pattern::META_MIN: DBGLOG("EOL? %d", ch);- anc_ = true;- if (jump == Pattern::Const::IMAX &&+ if (metas > 0 && jump == Pattern::Const::IMAX && (ch == EOF || ch == '\n' || (ch == '\r' && peek() == '\n'))) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -263,9 +266,9 @@ redo: continue; case Pattern::META_BOL - Pattern::META_MIN: DBGLOG("BOL? %d", bol);- anc_ = true;- if (jump == Pattern::Const::IMAX && bol)+ if (metas > 0 && jump == Pattern::Const::IMAX && bol) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -274,9 +277,9 @@ redo: continue; case Pattern::META_EWE - Pattern::META_MIN: DBGLOG("EWE? %d", at_ewe(ch));- anc_ = true;- if (jump == Pattern::Const::IMAX && at_ewe(ch))+ if (metas > 0 && jump == Pattern::Const::IMAX && at_ewe(ch)) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -285,9 +288,9 @@ redo: continue; case Pattern::META_BWE - Pattern::META_MIN: DBGLOG("BWE? %d", at_bwe(ch));- anc_ = true;- if (jump == Pattern::Const::IMAX && at_bwe(ch))+ if (metas > 0 && jump == Pattern::Const::IMAX && at_bwe(ch)) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -296,9 +299,9 @@ redo: continue; case Pattern::META_EWB - Pattern::META_MIN: DBGLOG("EWB? %d", at_ewb());- anc_ = true;- if (jump == Pattern::Const::IMAX && at_ewb())+ if (metas > 0 && jump == Pattern::Const::IMAX && at_ewb()) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -307,9 +310,9 @@ redo: continue; case Pattern::META_BWB - Pattern::META_MIN: DBGLOG("BWB? %d", at_bwb());- anc_ = true;- if (jump == Pattern::Const::IMAX && at_bwb())+ if (metas > 0 && jump == Pattern::Const::IMAX && at_bwb()) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -318,9 +321,9 @@ redo: continue; case Pattern::META_NWE - Pattern::META_MIN: DBGLOG("NWE? %d", at_nwe(ch));- anc_ = true;- if (jump == Pattern::Const::IMAX && at_nwe(ch))+ if (metas > 0 && jump == Pattern::Const::IMAX && at_nwe(ch)) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -329,9 +332,9 @@ redo: continue; case Pattern::META_NWB - Pattern::META_MIN: DBGLOG("NWB? %d", at_nwb());- anc_ = true;- if (jump == Pattern::Const::IMAX && at_nwb())+ if (metas > 0 && jump == Pattern::Const::IMAX && at_nwb()) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -340,9 +343,9 @@ redo: continue; case Pattern::META_WBE - Pattern::META_MIN: DBGLOG("WBE? %d", at_wbe(ch));- anc_ = true;- if (jump == Pattern::Const::IMAX && at_wbe(ch))+ if (metas > 0 && jump == Pattern::Const::IMAX && at_wbe(ch)) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc);@@ -351,16 +354,16 @@ redo: continue; case Pattern::META_WBB - Pattern::META_MIN: DBGLOG("WBB? %d", at_wbb());- anc_ = true;- if (jump == Pattern::Const::IMAX && at_wbb())+ if (metas > 0 && jump == Pattern::Const::IMAX && at_wbb()) {+ --metas; jump = Pattern::index_of(opcode); if (jump == Pattern::Const::LONG) jump = Pattern::long_index_of(*++pc); } opcode = *++pc; continue;- case 0xFF: // LONG+ case 0xff: // LONG opcode = *++pc; continue; }@@ -375,27 +378,25 @@ redo: bpos = pos_ - (txt_ - buf_) - 1; DBGLOG("Backtrack point: back = %u pos = %zu", back, bpos); }- pc = pat_->opc_ + jump;- opcode = *pc; } } if (jump == Pattern::Const::IMAX) {- if (back != Pattern::Const::IMAX)+ if (back != Pattern::Const::IMAX && bpos + 1 == pos_ - (txt_ - buf_)) { pc = pat_->opc_ + back; opcode = *pc;+ DBGLOG("Backtrack 1: back = %u pos = %zu ch = %d", back, pos_, ch); back = Pattern::Const::IMAX; } break; }- DBGLOG("Try jump = %u", jump);- if (back == Pattern::Const::IMAX)+ if (back == static_cast<Pattern::Index>(pc - pat_->opc_)) {- back = static_cast<Pattern::Index>(pc - pat_->opc_); bpos = pos_ - (txt_ - buf_) - 1;- DBGLOG("Backtrack point: back = %u pos = %zu", back, bpos);+ DBGLOG("Backtrack update point: back = %u pos = %zu", back, bpos); }+ DBGLOG("Try jump = %u", jump); pc = pat_->opc_ + jump; opcode = *pc; jump = Pattern::Const::IMAX;@@ -411,7 +412,7 @@ redo: { pos_ = (txt_ - buf_) + bpos; pc = pat_->opc_ + back;- DBGLOG("Backtrack: back = %u pos = %zu ch = %d", back, pos_, ch);+ DBGLOG("Backtrack 2: back = %u pos = %zu ch = %d", back, pos_, ch); back = Pattern::Const::IMAX; continue; }@@ -425,7 +426,7 @@ redo: break; } Pattern::Opcode lo = ch << 24;- Pattern::Opcode hi = lo | 0x00FFFFFF;+ Pattern::Opcode hi = lo | 0x00ffffff; unrolled: if (hi < opcode || lo > (opcode << 8)) {@@ -493,7 +494,7 @@ redo: { pc = pat_->opc_ + back; pos_ = (txt_ - buf_) + bpos;- DBGLOG("Backtrack: back = %u pos = %zu ch = %d", back, pos_, ch);+ DBGLOG("Backtrack 3: back = %u pos = %zu ch = %d", back, pos_, ch); back = Pattern::Const::IMAX; continue; }@@ -589,16 +590,9 @@ redo: { --retry; set_current(++cur_);- anc_ = false; DBGLOG("Find: try next pos %zu", cur_); goto scan; }- // anchor or boundary?- if (anc_)- {- cur_ = txt_ - buf_; // reset current to pattern start when a word boundary was encountered- anc_ = false;- } if (cur_ < pos_) // if we didn't fail on META alone { if ((this->*adv_)(cur_ + 1))@@ -714,6 +708,50 @@ redo: return cap_; } +// expand code for all pin minimal cases+#define INIT_ADV_PAT_PIN_CASE(PIN) \+ switch (pat_->min_) \+ { \+ case 0: \+ case 1: \+ adv_ = &Matcher::advance_pattern_pin##PIN##_one; \+ break; \+ case 2: \+ case 3: \+ adv_ = &Matcher::advance_pattern_pin##PIN##_pma; \+ break; \+ case 4: \+ adv_ = &Matcher::advance_pattern_pin##PIN##_pmh<4>; \+ break; \+ case 5: \+ adv_ = &Matcher::advance_pattern_pin##PIN##_pmh<5>; \+ break; \+ case 6: \+ adv_ = &Matcher::advance_pattern_pin##PIN##_pmh<6>; \+ break; \+ case 7: \+ adv_ = &Matcher::advance_pattern_pin##PIN##_pmh<7>; \+ break; \+ case 8: \+ adv_ = &Matcher::advance_pattern_pin##PIN##_pmh<8>; \+ break; \+ }++// in init_advance(): select advance_pattern_min1() or advance_pattern_pma() based on the machine, heuristically+#if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2)+# define MAX_PATTERN_MIN1_NPY 33+# define MAX_PATTERN_MIN2_NPY 36+# define MAX_PATTERN_MIN3_NPY 47+#elif defined(HAVE_NEON) && defined(__aarch64__)+# define MAX_PATTERN_MIN1_NPY 30+# define MAX_PATTERN_MIN2_NPY 24+# define MAX_PATTERN_MIN3_NPY 36+#else+# define MAX_PATTERN_MIN1_NPY 50+# define MAX_PATTERN_MIN2_NPY 56+# define MAX_PATTERN_MIN3_NPY 56+#endif+ /// Initialize specialized pattern search methods to advance the engine to a possible match void Matcher::init_advance() {@@ -727,92 +765,93 @@ void Matcher::init_advance() switch (pat_->pin_) { case 1:- if (pat_->min_ < 4)- adv_ = &Matcher::advance_pattern_pin1_pma;- else- adv_ = &Matcher::advance_pattern_pin1_pmh;+ switch (pat_->min_)+ {+ case 0:+ case 1:+ adv_ = &Matcher::advance_pattern_pin1_one;+ break;+ case 2:+ case 3:+ adv_ = &Matcher::advance_pattern_pin1_pma;+ break;+ case 4:+ adv_ = &Matcher::advance_pattern_pin1_pmh<4>;+ break;+ case 5:+ adv_ = &Matcher::advance_pattern_pin1_pmh<5>;+ break;+ case 6:+ adv_ = &Matcher::advance_pattern_pin1_pmh<6>;+ break;+ case 7:+ adv_ = &Matcher::advance_pattern_pin1_pmh<7>;+ break;+ case 8:+ adv_ = &Matcher::advance_pattern_pin1_pmh<8>;+ break;+ } break; #if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2) || defined(HAVE_NEON) case 2:- if (pat_->min_ == 1)- adv_ = &Matcher::advance_pattern_pin2_one;- else if (pat_->min_ < 4)- adv_ = &Matcher::advance_pattern_pin2_pma;- else- adv_ = &Matcher::advance_pattern_pin2_pmh;+ INIT_ADV_PAT_PIN_CASE(2); break; case 3:- if (pat_->min_ == 1)- adv_ = &Matcher::advance_pattern_pin3_one;- else if (pat_->min_ < 4)- adv_ = &Matcher::advance_pattern_pin3_pma;- else- adv_ = &Matcher::advance_pattern_pin3_pmh;+ INIT_ADV_PAT_PIN_CASE(3); break; case 4:- if (pat_->min_ == 1)- adv_ = &Matcher::advance_pattern_pin4_one;- else if (pat_->min_ < 4)- adv_ = &Matcher::advance_pattern_pin4_pma;- else- adv_ = &Matcher::advance_pattern_pin4_pmh;+ INIT_ADV_PAT_PIN_CASE(4); break; case 5:- if (pat_->min_ == 1)- adv_ = &Matcher::advance_pattern_pin5_one;- else if (pat_->min_ < 4)- adv_ = &Matcher::advance_pattern_pin5_pma;- else- adv_ = &Matcher::advance_pattern_pin5_pmh;+ INIT_ADV_PAT_PIN_CASE(5); break; case 6:- if (pat_->min_ == 1)- adv_ = &Matcher::advance_pattern_pin6_one;- else if (pat_->min_ < 4)- adv_ = &Matcher::advance_pattern_pin6_pma;- else- adv_ = &Matcher::advance_pattern_pin6_pmh;+ INIT_ADV_PAT_PIN_CASE(6); break; case 7:- if (pat_->min_ == 1)- adv_ = &Matcher::advance_pattern_pin7_one;- else if (pat_->min_ < 4)- adv_ = &Matcher::advance_pattern_pin7_pma;- else- adv_ = &Matcher::advance_pattern_pin7_pmh;+ INIT_ADV_PAT_PIN_CASE(7); break; case 8:- if (pat_->min_ == 1)- adv_ = &Matcher::advance_pattern_pin8_one;- else if (pat_->min_ < 4)- adv_ = &Matcher::advance_pattern_pin8_pma;- else- adv_ = &Matcher::advance_pattern_pin8_pmh;+ INIT_ADV_PAT_PIN_CASE(8); break; #endif default:- if (pat_->min_ >= 4 || pat_->npy_ < 16 || (pat_->min_ >= 2 && pat_->npy_ >= 56))+ switch (pat_->min_) {- switch (pat_->min_)- {- case 0:- case 1:+ case 0:+ case 1:+ if (pat_->npy_ <= MAX_PATTERN_MIN1_NPY) adv_ = &Matcher::advance_pattern_min1;- break;- case 2:+ else+ adv_ = &Matcher::advance_pattern_pma;+ break;+ case 2:+ if (pat_->npy_ <= MAX_PATTERN_MIN2_NPY) adv_ = &Matcher::advance_pattern_min2;- break;- case 3:+ else+ adv_ = &Matcher::advance_pattern_pma;+ break;+ case 3:+ if (pat_->npy_ <= MAX_PATTERN_MIN3_NPY) adv_ = &Matcher::advance_pattern_min3;- break;- default:- adv_ = &Matcher::advance_pattern_min4;- break;- }- }- else- {- adv_ = &Matcher::advance_pattern;+ else+ adv_ = &Matcher::advance_pattern_pma;+ break;+ case 4:+ adv_ = &Matcher::advance_pattern_min4<4>;+ break;+ case 5:+ adv_ = &Matcher::advance_pattern_min4<5>;+ break;+ case 6:+ adv_ = &Matcher::advance_pattern_min4<6>;+ break;+ case 7:+ adv_ = &Matcher::advance_pattern_min4<7>;+ break;+ case 8:+ adv_ = &Matcher::advance_pattern_min4<8>;+ break; } } }@@ -845,24 +884,20 @@ void Matcher::init_advance() } else if (pat_->bmd_ == 0) {-#if defined(WITH_STRING_PM) if (pat_->min_ >= 4) adv_ = &Matcher::advance_string_pmh; else if (pat_->min_ > 0) adv_ = &Matcher::advance_string_pma; else-#endif adv_ = &Matcher::advance_string; } else {-#if defined(WITH_STRING_PM) if (pat_->min_ >= 4) adv_ = &Matcher::advance_string_bm_pmh; else if (pat_->min_ > 0) adv_ = &Matcher::advance_string_bm_pma; else-#endif adv_ = &Matcher::advance_string_bm; } #if defined(HAVE_AVX512BW) || defined(HAVE_AVX2)@@ -883,7 +918,39 @@ bool Matcher::advance_none(size_t) return false; } -/// My "needle search" method when pin=1+/// My homegrown "needle search" method when needle pin=1 and min=0 or 1+bool Matcher::advance_pattern_pin1_one(size_t loc)+{+ const char *chr = pat_->chr_;+ uint16_t lcp = pat_->lcp_;+ char chr0 = chr[0];+ while (true)+ {+ const char *s = buf_ + loc + lcp;+ const char *e = buf_ + end_;+ if (s < e && (s = static_cast<const char*>(std::memchr(s, chr0, e - s))) != NULL)+ {+ s -= lcp;+ loc = s - buf_;+ if (s > e - 4 || pat_->predict_match(s))+ {+ set_current(loc);+ return true;+ }+ ++loc;+ }+ else+ {+ loc = e - buf_;+ set_current_and_peek_more(loc - 1);+ loc = cur_ + 1;+ if (loc + 1 > end_)+ return false;+ }+ }+}++/// My homegrown "needle search" method when needle pin=1 and min=2 or 3 bool Matcher::advance_pattern_pin1_pma(size_t loc) { const char *chr = pat_->chr_;@@ -917,8 +984,7 @@ bool Matcher::advance_pattern_pin1_pma(size_t loc) } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + min > end_)@@ -943,11 +1009,16 @@ bool Matcher::advance_pattern_pin1_pma(size_t loc) uint64_t mask = vgetq_lane_u64(vmask64, 0); if (mask != 0) {- for (uint16_t i = 0; i < 8; ++i)+ loc = s - lcp - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do { if ((mask & 0xff)) {- loc = s - lcp + i - buf_; if (loc + 4 > end_ || pat_->predict_match(&buf_[loc])) { set_current(loc);@@ -955,16 +1026,22 @@ bool Matcher::advance_pattern_pin1_pma(size_t loc) } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } mask = vgetq_lane_u64(vmask64, 1); if (mask != 0) {- for (uint16_t i = 8; i < 16; ++i)+ loc = s - lcp + 8 - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do { if ((mask & 0xff)) {- loc = s - lcp + i - buf_; if (loc + 4 > end_ || pat_->predict_match(&buf_[loc])) { set_current(loc);@@ -972,12 +1049,12 @@ bool Matcher::advance_pattern_pin1_pma(size_t loc) } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + min > end_)@@ -1014,11 +1091,11 @@ bool Matcher::advance_pattern_pin1_pma(size_t loc) } } -/// My "needle search" method when pin=1+/// My homegrown "needle search" method when needle pin=1 and min>=4+template <uint8_t MIN> bool Matcher::advance_pattern_pin1_pmh(size_t loc) { const char *chr = pat_->chr_;- size_t min = pat_->min_; uint16_t lcp = pat_->lcp_; uint16_t lcs = pat_->lcs_; #if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2)@@ -1027,7 +1104,7 @@ bool Matcher::advance_pattern_pin1_pmh(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - min + 1;+ const char *e = buf_ + end_ + lcp - MIN + 1; while (s <= e - 16) { __m128i vstrlcp = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s));@@ -1039,7 +1116,7 @@ bool Matcher::advance_pattern_pin1_pmh(size_t loc) { uint32_t offset = ctz(mask); loc = s - lcp + offset - buf_;- if (pat_->predict_match(&buf_[loc], min))+ if (pat_->predict_match(&buf_[loc], MIN)) { set_current(loc); return true;@@ -1048,13 +1125,12 @@ bool Matcher::advance_pattern_pin1_pmh(size_t loc) } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1;- if (loc + min > end_)+ if (loc + MIN > end_) return false;- if (loc + min + 15 > end_)+ if (loc + MIN + 15 > end_) break; } #elif defined(HAVE_NEON)@@ -1063,7 +1139,7 @@ bool Matcher::advance_pattern_pin1_pmh(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - min + 1;+ const char *e = buf_ + end_ + lcp - MIN + 1; while (s <= e - 16) { uint8x16_t vstrlcp = vld1q_u8(reinterpret_cast<const uint8_t*>(s));@@ -1074,46 +1150,57 @@ bool Matcher::advance_pattern_pin1_pmh(size_t loc) uint64_t mask = vgetq_lane_u64(vmask64, 0); if (mask != 0) {- for (uint16_t i = 0; i < 8; ++i)+ loc = s - lcp - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do { if ((mask & 0xff)) {- loc = s - lcp + i - buf_;- if (pat_->predict_match(&buf_[loc], min))+ if (pat_->predict_match(&buf_[loc], MIN)) { set_current(loc); return true; } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } mask = vgetq_lane_u64(vmask64, 1); if (mask != 0) {- for (uint16_t i = 8; i < 16; ++i)+ loc = s - lcp + 8 - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do { if ((mask & 0xff)) {- loc = s - lcp + i - buf_;- if (pat_->predict_match(&buf_[loc], min))+ if (pat_->predict_match(&buf_[loc], MIN)) { set_current(loc); return true; } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1;- if (loc + min > end_)+ if (loc + MIN > end_) return false;- if (loc + min + 15 > end_)+ if (loc + MIN + 15 > end_) break; } #endif@@ -1127,7 +1214,7 @@ bool Matcher::advance_pattern_pin1_pmh(size_t loc) { s -= lcp; loc = s - buf_;- if (s + min > e || (s[lcs] == chr1 && pat_->predict_match(s, min)))+ if (s + MIN > e || (s[lcs] == chr1 && pat_->predict_match(s, MIN))) { set_current(loc); return true;@@ -1139,7 +1226,7 @@ bool Matcher::advance_pattern_pin1_pmh(size_t loc) loc = e - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1;- if (loc + min > end_)+ if (loc + MIN > end_) return false; } }@@ -1147,7 +1234,7 @@ bool Matcher::advance_pattern_pin1_pmh(size_t loc) #if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2) -/// My "needle search" methods+/// My homegrown "needle search" methods #define ADV_PAT_PIN_ONE(N, INIT, COMP) \ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ { \@@ -1184,7 +1271,7 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ if (loc + 16 > end_) \ break; \ } \- return advance_pattern(loc); \+ return advance_pattern_pma(loc); \ } ADV_PAT_PIN_ONE(2, \@@ -1278,7 +1365,7 @@ ADV_PAT_PIN_ONE(8, \ veq = _mm_or_si128(veq, _mm_cmpeq_epi8(v7, vstr)); \ ) -/// My "needle search" methods+/// My homegrown "needle search" methods #define ADV_PAT_PIN(N, INIT, COMP) \ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ { \@@ -1303,7 +1390,7 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ { \ uint32_t offset = ctz(mask); \ loc = s - lcp + offset - buf_; \- if (loc + 4 > end_ || pat_->predict_match(&buf_[loc])) \+ if (loc + min + 3 > end_ || pat_->predict_match(&buf_[loc])) \ { \ set_current(loc); \ return true; \@@ -1312,8 +1399,7 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ } \ s += 16; \ } \- s -= lcp; \- loc = s - buf_; \+ loc = s - lcp - buf_; \ set_current_and_peek_more(loc - 1); \ loc = cur_ + 1; \ if (loc + min > end_) \@@ -1321,20 +1407,20 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ if (loc + min + 15 > end_) \ break; \ } \- return advance_pattern(loc); \+ return advance_pattern_pma(loc); \ } \ \+template <uint8_t MIN> \ bool Matcher::advance_pattern_pin##N##_pmh(size_t loc) \ { \ const char *chr = pat_->chr_; \- size_t min = pat_->min_; \ uint16_t lcp = pat_->lcp_; \ uint16_t lcs = pat_->lcs_; \ INIT \ while (true) \ { \ const char *s = buf_ + loc + lcp; \- const char *e = buf_ + end_ + lcp - min + 1; \+ const char *e = buf_ + end_ + lcp - MIN + 1; \ while (s <= e - 16) \ { \ __m128i vstrlcp = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s)); \@@ -1347,7 +1433,7 @@ bool Matcher::advance_pattern_pin##N##_pmh(size_t loc) \ { \ uint32_t offset = ctz(mask); \ loc = s - lcp + offset - buf_; \- if (pat_->predict_match(&buf_[loc], min)) \+ if (pat_->predict_match(&buf_[loc], MIN)) \ { \ set_current(loc); \ return true; \@@ -1356,16 +1442,15 @@ bool Matcher::advance_pattern_pin##N##_pmh(size_t loc) \ } \ s += 16; \ } \- s -= lcp; \- loc = s - buf_; \+ loc = s - lcp - buf_; \ set_current_and_peek_more(loc - 1); \ loc = cur_ + 1; \- if (loc + min > end_) \+ if (loc + MIN > end_) \ return false; \- if (loc + min + 15 > end_) \+ if (loc + MIN + 15 > end_) \ break; \ } \- return advance_pattern_min4(loc); \+ return advance_pattern_min4<MIN>(loc); \ } ADV_PAT_PIN(2, \@@ -1524,7 +1609,7 @@ ADV_PAT_PIN(8, \ #elif defined(HAVE_NEON) -/// My "needle search" methods+/// My homegrown "needle search" methods #define ADV_PAT_PIN_ONE(N, INIT, COMP) \ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ { \@@ -1542,11 +1627,16 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ uint64_t mask = vgetq_lane_u64(vmask64, 0); \ if (mask != 0) \ { \- for (uint16_t i = 0; i < 8; ++i) \+ loc = s - buf_; \+ if (static_cast<uint32_t>(mask) == 0) \ { \- if ((mask & 0xff)) \+ mask >>= 32; \+ loc += 4; \+ } \+ do \+ { \+ if ((mask & 0xff) != 0) \ { \- loc = s + i - buf_; \ if (loc + 4 > end_ || pat_->predict_match(&buf_[loc])) \ { \ set_current(loc); \@@ -1554,16 +1644,22 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ } \ } \ mask >>= 8; \- } \+ ++loc; \+ } while (mask != 0); \ } \ mask = vgetq_lane_u64(vmask64, 1); \ if (mask != 0) \ { \- for (uint16_t i = 8; i < 16; ++i) \+ loc = s + 8 - buf_; \+ if (static_cast<uint32_t>(mask) == 0) \ { \- if ((mask & 0xff)) \+ mask >>= 32; \+ loc += 4; \+ } \+ do \+ { \+ if ((mask & 0xff) != 0) \ { \- loc = s + i - buf_; \ if (loc + 4 > end_ || pat_->predict_match(&buf_[loc])) \ { \ set_current(loc); \@@ -1571,7 +1667,8 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ } \ } \ mask >>= 8; \- } \+ ++loc; \+ } while (mask != 0); \ } \ s += 16; \ } \@@ -1583,7 +1680,7 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ if (loc + 16 > end_) \ break; \ } \- return advance_pattern(loc); \+ return advance_pattern_pma(loc); \ } ADV_PAT_PIN_ONE(2, \@@ -1716,7 +1813,7 @@ ADV_PAT_PIN_ONE(8, \ vceqq_u8(v7, vstr)); \ ) -/// My "needle search" methods+/// My homegrown "needle search" methods #define ADV_PAT_PIN(N, INIT, COMP) \ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ { \@@ -1738,11 +1835,16 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ uint64_t mask = vgetq_lane_u64(vmask64, 0); \ if (mask != 0) \ { \- for (uint16_t i = 0; i < 8; ++i) \+ loc = s - lcp - buf_; \+ if (static_cast<uint32_t>(mask) == 0) \ { \- if ((mask & 0xff)) \+ mask >>= 32; \+ loc += 4; \+ } \+ do \+ { \+ if ((mask & 0xff) != 0) \ { \- loc = s - lcp + i - buf_; \ if (loc + 4 > end_ || pat_->predict_match(&buf_[loc])) \ { \ set_current(loc); \@@ -1750,16 +1852,22 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ } \ } \ mask >>= 8; \- } \+ ++loc; \+ } while (mask != 0); \ } \ mask = vgetq_lane_u64(vmask64, 1); \ if (mask != 0) \ { \- for (uint16_t i = 8; i < 16; ++i) \+ loc = s - lcp + 8 - buf_; \+ if (static_cast<uint32_t>(mask) == 0) \ { \- if ((mask & 0xff)) \+ mask >>= 32; \+ loc += 4; \+ } \+ do \+ { \+ if ((mask & 0xff) != 0) \ { \- loc = s - lcp + i - buf_; \ if (loc + 4 > end_ || pat_->predict_match(&buf_[loc])) \ { \ set_current(loc); \@@ -1767,12 +1875,12 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ } \ } \ mask >>= 8; \- } \+ ++loc; \+ } while (mask != 0); \ } \ s += 16; \ } \- s -= lcp; \- loc = s - buf_; \+ loc = s - lcp - buf_; \ set_current_and_peek_more(loc - 1); \ loc = cur_ + 1; \ if (loc + min > end_) \@@ -1780,20 +1888,20 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ if (loc + min + 15 > end_) \ break; \ } \- return advance_pattern(loc); \+ return advance_pattern_pma(loc); \ } \ \+template <uint8_t MIN> \ bool Matcher::advance_pattern_pin##N##_pmh(size_t loc) \ { \ const char *chr = pat_->chr_; \- size_t min = pat_->min_; \ uint16_t lcp = pat_->lcp_; \ uint16_t lcs = pat_->lcs_; \ INIT \ while (true) \ { \ const char *s = buf_ + loc + lcp; \- const char *e = buf_ + end_ + lcp - min + 1; \+ const char *e = buf_ + end_ + lcp - MIN + 1; \ while (s <= e - 16) \ { \ uint8x16_t vstrlcp = vld1q_u8(reinterpret_cast<const uint8_t*>(s)); \@@ -1803,49 +1911,60 @@ bool Matcher::advance_pattern_pin##N##_pmh(size_t loc) \ uint64_t mask = vgetq_lane_u64(vmask64, 0); \ if (mask != 0) \ { \- for (uint16_t i = 0; i < 8; ++i) \+ loc = s - lcp - buf_; \+ if (static_cast<uint32_t>(mask) == 0) \+ { \+ mask >>= 32; \+ loc += 4; \+ } \+ do \ { \- if ((mask & 0xff)) \+ if ((mask & 0xff) != 0) \ { \- loc = s - lcp + i - buf_; \- if (pat_->predict_match(&buf_[loc], min)) \+ if (loc + 4 > end_ || pat_->predict_match(&buf_[loc])) \ { \ set_current(loc); \ return true; \ } \ } \ mask >>= 8; \- } \+ ++loc; \+ } while (mask != 0); \ } \ mask = vgetq_lane_u64(vmask64, 1); \ if (mask != 0) \ { \- for (uint16_t i = 8; i < 16; ++i) \+ loc = s - lcp + 8 - buf_; \+ if (static_cast<uint32_t>(mask) == 0) \+ { \+ mask >>= 32; \+ loc += 4; \+ } \+ do \ { \- if ((mask & 0xff)) \+ if ((mask & 0xff) != 0) \ { \- loc = s - lcp + i - buf_; \- if (pat_->predict_match(&buf_[loc], min)) \+ if (loc + 4 > end_ || pat_->predict_match(&buf_[loc])) \ { \ set_current(loc); \ return true; \ } \ } \ mask >>= 8; \- } \+ ++loc; \+ } while (mask != 0); \ } \ s += 16; \ } \- s -= lcp; \- loc = s - buf_; \+ loc = s - lcp - buf_; \ set_current_and_peek_more(loc - 1); \ loc = cur_ + 1; \- if (loc + min > end_) \+ if (loc + MIN > end_) \ return false; \- if (loc + min + 15 > end_) \+ if (loc + MIN + 15 > end_) \ break; \ } \- return advance_pattern_min4(loc); \+ return advance_pattern_min4<MIN>(loc); \ } ADV_PAT_PIN(2, \@@ -2082,44 +2201,47 @@ ADV_PAT_PIN(8, \ #endif -/// Minimal 1 char pattern usign the bitap first bit and PM4+/// Minimal 1 byte long patterns using 4-way bitap hashed pairs then PM4 bool Matcher::advance_pattern_min1(size_t loc) {- const Pattern::Pred *bit = pat_->bit_;+ const Pattern::Pred *tap = pat_->tap_; while (true) { const char *s = buf_ + loc;- const char *e = buf_ + end_ - 3;- bool f = true;- while (s < e &&- (f = (bit[static_cast<uint8_t>(s[0])] &- bit[static_cast<uint8_t>(s[1])] &- bit[static_cast<uint8_t>(s[2])] &- bit[static_cast<uint8_t>(s[3])] & 1)))+ const char *e = buf_ + end_ - 4;+ uint8_t c0 = static_cast<uint8_t>(buf_[loc]);+ while (s < e) {+ uint8_t c1 = static_cast<uint8_t>(s[1]);+ uint8_t c2 = static_cast<uint8_t>(s[2]);+ uint8_t c3 = static_cast<uint8_t>(s[3]);+ uint8_t c4 = static_cast<uint8_t>(s[4]);+ if (!(tap[Pattern::bihash(c0, c1)] &+ tap[Pattern::bihash(c1, c2)] &+ tap[Pattern::bihash(c2, c3)] &+ tap[Pattern::bihash(c3, c4)] & 1))+ break;+ c0 = c4; s += 4; }- loc = s - buf_;- if (!f)+ if (s < e) {- if ((bit[static_cast<uint8_t>(*s)] & 1))+ if (!pat_->predict_match(s) &&+ ++s <= e && !pat_->predict_match(s) &&+ ++s <= e && !pat_->predict_match(s) &&+ ++s <= e && !pat_->predict_match(s)) {- if ((bit[static_cast<uint8_t>(*++s)] & 1))- if ((bit[static_cast<uint8_t>(*++s)] & 1))- ++s;- loc = s - buf_;- }- if (s < e && !pat_->predict_match(s))- {- ++loc;+ loc = s - buf_ + 1; continue; }+ loc = s - buf_; set_current(loc); return true; }+ loc = s - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1;- if (loc + 3 >= end_)+ if (loc + 4 >= end_) { set_current(loc); return loc + 1 <= end_;@@ -2127,19 +2249,21 @@ bool Matcher::advance_pattern_min1(size_t loc) } } -/// Minimal 2 char pattern using bitap and PM4+/// Minimal 2 byte long patterns using bitap hashed pairs and PM4 bool Matcher::advance_pattern_min2(size_t loc) {- const Pattern::Pred *bit = pat_->bit_;+ const Pattern::Pred *tap = pat_->tap_; uint32_t state = ~0; while (true) { const char *s = buf_ + loc;- const char *e = buf_ + end_;+ const char *e = buf_ + end_ - 1;+ uint8_t c0 = static_cast<uint8_t>(*s); while (s < e) {- state = (state << 1) | bit[static_cast<uint8_t>(*s)];- ++s;+ uint8_t c1 = static_cast<uint8_t>(*++s);+ state = (state << 1) | tap[Pattern::bihash(c0, c1)];+ c0 = c1; if ((state & 2) == 0 && (s > e - 2 || pat_->predict_match(s - 2))) { loc = s - buf_ - 2;@@ -2150,24 +2274,26 @@ bool Matcher::advance_pattern_min2(size_t loc) loc = s - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1;- if (loc + 2 > end_)+ if (loc + 1 >= end_) return false; } } -/// Minimal 3 char pattern using bitap and PM4+/// Minimal 3 byte long pattern using bitap hashed pairs and PM4 bool Matcher::advance_pattern_min3(size_t loc) {- const Pattern::Pred *bit = pat_->bit_;+ const Pattern::Pred *tap = pat_->tap_; uint32_t state = ~0; while (true) { const char *s = buf_ + loc;- const char *e = buf_ + end_;+ const char *e = buf_ + end_ - 1;+ uint8_t c0 = static_cast<uint8_t>(*s); while (s < e) {- state = (state << 1) | bit[static_cast<uint8_t>(*s)];- ++s;+ uint8_t c1 = static_cast<uint8_t>(*++s);+ state = (state << 1) | tap[Pattern::bihash(c0, c1)];+ c0 = c1; if ((state & 4) == 0 && (s > e - 1 || pat_->predict_match(s - 3))) { loc = s - buf_ - 3;@@ -2178,69 +2304,73 @@ bool Matcher::advance_pattern_min3(size_t loc) loc = s - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1;- if (loc + 3 > end_)+ if (loc + 1 >= end_) return false; } } -/// Minimal 4 char pattern using bitap and PM hashing+/// Minimal 4 byte long patterns (MIN>=4) using bitap hashed pairs and Bloom filter hashing+template <uint8_t MIN> bool Matcher::advance_pattern_min4(size_t loc) {- const Pattern::Pred *bit = pat_->bit_;- size_t min = pat_->min_;+ const Pattern::Pred *tap = pat_->tap_; uint32_t state1 = ~0; uint32_t state2 = ~0;- uint32_t mask = 1 << (min - 1);+ uint32_t mask = 1 << (MIN - 1); while (true) { const char *s = buf_ + loc;- const char *e = buf_ + end_ - 1;+ const char *e = buf_ + end_ - 2;+ uint8_t c0 = static_cast<uint8_t>(*s); while (s < e) {- state2 = (state1 << 1) | bit[static_cast<uint8_t>(s[0])];- state1 = (state2 << 1) | bit[static_cast<uint8_t>(s[1])];- s += 2;- if ((state1 & state2 & mask) == 0)+ uint8_t c1 = static_cast<uint8_t>(*++s);+ state2 = (state1 << 1) | tap[Pattern::bihash(c0, c1)];+ c0 = static_cast<uint8_t>(*++s);+ state1 = (state2 << 1) | tap[Pattern::bihash(c1, c0)];+ if ((state2 & mask) == 0 && pat_->predict_match(s - MIN - 1, MIN)) {- if ((state2 & mask) == 0)- {- state1 = state2;- --s;- }- if (pat_->predict_match(s - min, min))- {- loc = s - buf_ - min;- set_current(loc);- return true;- }+ loc = s - buf_ - MIN - 1;+ set_current(loc);+ return true;+ }+ if ((state1 & mask) == 0 && pat_->predict_match(s - MIN, MIN))+ {+ loc = s - buf_ - MIN;+ set_current(loc);+ return true; } } loc = s - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1;- if (loc + min > end_)- return false;+ if (loc + 2 >= end_)+ {+ if (loc + 1 >= end_)+ return false;+ --loc;+ state1 = state2;+ } } } -/// Minimal 1 char pattern using PM4-bool Matcher::advance_pattern(size_t loc)+/// Minimal 1 byte long pattern using PM4+bool Matcher::advance_pattern_pma(size_t loc) { while (true) { const char *s = buf_ + loc;- const char *e = buf_ + end_ - 6;- bool f = true;- while (s < e &&- (f = (!pat_->predict_match(s) &&- !pat_->predict_match(++s) &&- !pat_->predict_match(++s) &&- !pat_->predict_match(++s))))+ const char *e = buf_ + end_;+ while (s < e - 6 &&+ !pat_->predict_match(s) &&+ !pat_->predict_match(++s) &&+ !pat_->predict_match(++s) &&+ !pat_->predict_match(++s)) { ++s; } loc = s - buf_;- if (!f)+ if (s < e) { set_current(loc); return true;@@ -2278,7 +2408,7 @@ bool Matcher::advance_char(size_t loc) } } -/// One char followed by 1 to 3 minimal char pattern+/// One char followed by 1 to 4 characters bool Matcher::advance_char_pma(size_t loc) { char chr0 = pat_->chr_[0];@@ -2290,9 +2420,11 @@ bool Matcher::advance_char_pma(size_t loc) if (s != NULL) { loc = s - buf_;- set_current(loc); if (s > e - 5 || pat_->predict_match(s + 1))+ {+ set_current(loc); return true;+ } ++loc; } else@@ -2306,7 +2438,7 @@ bool Matcher::advance_char_pma(size_t loc) } } -/// One char followed by 4 minimal char pattern+/// One char followed by 4 to 8 characters bool Matcher::advance_char_pmh(size_t loc) { char chr0 = pat_->chr_[0];@@ -2363,7 +2495,7 @@ bool Matcher::advance_chars(size_t loc) uint32_t offset = ctz(mask); loc = s - lcp + offset - buf_; if (LEN == 2 ||- (LEN == 3 ? s[offset + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + offset, chr + 1, LEN - 2) == 0))+ (LEN == 3 ? s[offset + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + offset, chr + 1, LEN - 1) == 0)) { set_current(loc); return true;@@ -2372,8 +2504,7 @@ bool Matcher::advance_chars(size_t loc) } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + LEN > end_)@@ -2399,39 +2530,50 @@ bool Matcher::advance_chars(size_t loc) uint64_t mask = vgetq_lane_u64(vmask64, 0); if (mask != 0) {- for (uint16_t i = 0; i < 8; ++i)+ loc = s - lcp - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do { if ((mask & 0xff) && (LEN == 2 ||- (LEN == 3 ? s[i + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + i, chr + 1, LEN - 2) == 0)))+ (LEN == 3 ? buf_[loc + 1] == chr[1] : std::memcmp(&buf_[loc + 1], chr + 1, LEN - 1) == 0))) {- loc = s - lcp + i - buf_; set_current(loc); return true; } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } mask = vgetq_lane_u64(vmask64, 1); if (mask != 0) {- for (uint16_t i = 8; i < 16; ++i)+ loc = s - lcp + 8 - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do { if ((mask & 0xff) && (LEN == 2 ||- (LEN == 3 ? s[i + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + i, chr + 1, LEN - 2) == 0)))+ (LEN == 3 ? buf_[loc + 1] == chr[1] : std::memcmp(&buf_[loc + 1], chr + 1, LEN - 1) == 0))) {- loc = s - lcp + i - buf_; set_current(loc); return true; } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + LEN > end_)@@ -2455,7 +2597,7 @@ bool Matcher::advance_chars(size_t loc) break; } if (LEN == 2 ||- (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 2) == 0))+ (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 1) == 0)) { loc = s - lcp - buf_; set_current(loc);@@ -2471,7 +2613,7 @@ bool Matcher::advance_chars(size_t loc) } } -/// Few chars followed by 2 to 3 minimal char pattern+/// Few chars followed by 1 to 4 characters template<uint8_t LEN> bool Matcher::advance_chars_pma(size_t loc) {@@ -2483,7 +2625,7 @@ bool Matcher::advance_chars_pma(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - LEN + 1;+ const char *e = buf_ + end_ + lcp - LEN - min + 1; __m128i vlcp = _mm_set1_epi8(chr[lcp]); __m128i vlcs = _mm_set1_epi8(chr[lcs]); while (s <= e - 16)@@ -2497,7 +2639,7 @@ bool Matcher::advance_chars_pma(size_t loc) { uint32_t offset = ctz(mask); if (LEN == 2 ||- (LEN == 3 ? s[offset + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + offset, chr + 1, LEN - 2) == 0))+ (LEN == 3 ? s[offset + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + offset, chr + 1, LEN - 1) == 0)) { loc = s - lcp + offset - buf_; if (loc + LEN + 4 > end_ || pat_->predict_match(&buf_[loc + LEN]))@@ -2510,8 +2652,7 @@ bool Matcher::advance_chars_pma(size_t loc) } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + LEN + min > end_)@@ -2523,7 +2664,7 @@ bool Matcher::advance_chars_pma(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - LEN + 1;+ const char *e = buf_ + end_ + lcp - LEN - min + 1; uint8x16_t vlcp = vdupq_n_u8(chr[lcp]); uint8x16_t vlcs = vdupq_n_u8(chr[lcs]); while (s <= e - 16)@@ -2537,13 +2678,18 @@ bool Matcher::advance_chars_pma(size_t loc) uint64_t mask = vgetq_lane_u64(vmask64, 0); if (mask != 0) {- for (uint16_t i = 0; i < 8; ++i)+ loc = s - lcp - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do { if ((mask & 0xff) && (LEN == 2 ||- (LEN == 3 ? s[i + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + i, chr + 1, LEN - 2) == 0)))+ (LEN == 3 ? buf_[loc + 1] == chr[1] : std::memcmp(&buf_[loc + 1], chr + 1, LEN - 1) == 0))) {- loc = s - lcp + i - buf_; if (loc + LEN + 4 > end_ || pat_->predict_match(&buf_[loc + LEN])) { set_current(loc);@@ -2551,18 +2697,24 @@ bool Matcher::advance_chars_pma(size_t loc) } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } mask = vgetq_lane_u64(vmask64, 1); if (mask != 0) {- for (uint16_t i = 8; i < 16; ++i)+ loc = s - lcp + 8 - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do { if ((mask & 0xff) && (LEN == 2 ||- (LEN == 3 ? s[i + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + i, chr + 1, LEN - 2) == 0)))+ (LEN == 3 ? buf_[loc + 1] == chr[1] : std::memcmp(&buf_[loc + 1], chr + 1, LEN - 1) == 0))) {- loc = s - lcp + i - buf_; if (loc + LEN + 4 > end_ || pat_->predict_match(&buf_[loc + LEN])) { set_current(loc);@@ -2570,12 +2722,12 @@ bool Matcher::advance_chars_pma(size_t loc) } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + LEN + min > end_)@@ -2587,7 +2739,7 @@ bool Matcher::advance_chars_pma(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - LEN + 1;+ const char *e = buf_ + end_ + lcp - LEN - min + 1; while (s < e) { do@@ -2599,7 +2751,7 @@ bool Matcher::advance_chars_pma(size_t loc) break; } if (LEN == 2 ||- (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 2) == 0))+ (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 1) == 0)) { loc = s - lcp - buf_; if (loc + LEN + 4 > end_ || pat_->predict_match(&buf_[loc + LEN]))@@ -2618,7 +2770,7 @@ bool Matcher::advance_chars_pma(size_t loc) } } -/// Few chars followed by 4 minimal char pattern+/// Few chars followed by 4 to 8 characters template<uint8_t LEN> bool Matcher::advance_chars_pmh(size_t loc) {@@ -2630,7 +2782,7 @@ bool Matcher::advance_chars_pmh(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - LEN + 1;+ const char *e = buf_ + end_ + lcp - LEN - min + 1; __m128i vlcp = _mm_set1_epi8(chr[lcp]); __m128i vlcs = _mm_set1_epi8(chr[lcs]); while (s <= e - 16)@@ -2644,10 +2796,10 @@ bool Matcher::advance_chars_pmh(size_t loc) { uint32_t offset = ctz(mask); if (LEN == 2 ||- (LEN == 3 ? s[offset + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + offset, chr + 1, LEN - 2) == 0))+ (LEN == 3 ? s[offset + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + offset, chr + 1, LEN - 1) == 0)) { loc = s - lcp + offset - buf_;- if (loc + LEN + min > end_ || pat_->predict_match(&buf_[loc + LEN], min))+ if (pat_->predict_match(&buf_[loc + LEN], min)) { set_current(loc); return true;@@ -2657,8 +2809,7 @@ bool Matcher::advance_chars_pmh(size_t loc) } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + LEN + min > end_)@@ -2670,7 +2821,7 @@ bool Matcher::advance_chars_pmh(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - LEN + 1;+ const char *e = buf_ + end_ + lcp - LEN - min + 1; uint8x16_t vlcp = vdupq_n_u8(chr[lcp]); uint8x16_t vlcs = vdupq_n_u8(chr[lcs]); while (s <= e - 16)@@ -2684,45 +2835,56 @@ bool Matcher::advance_chars_pmh(size_t loc) uint64_t mask = vgetq_lane_u64(vmask64, 0); if (mask != 0) {- for (uint16_t i = 0; i < 8; ++i)+ loc = s - lcp - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do { if ((mask & 0xff) && (LEN == 2 ||- (LEN == 3 ? s[i + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + i, chr + 1, LEN - 2) == 0)))+ (LEN == 3 ? buf_[loc + 1] == chr[1] : std::memcmp(&buf_[loc + 1], chr + 1, LEN - 1) == 0))) {- size_t loc = s - lcp + i - buf_;- if (loc + LEN + min > end_ || pat_->predict_match(&buf_[loc + LEN], min))+ if (pat_->predict_match(&buf_[loc + LEN], min)) { set_current(loc); return true; } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } mask = vgetq_lane_u64(vmask64, 1); if (mask != 0) {- for (uint16_t i = 8; i < 16; ++i)+ loc = s - lcp + 8 - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do { if ((mask & 0xff) && (LEN == 2 ||- (LEN == 3 ? s[i + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + i, chr + 1, LEN - 2) == 0)))+ (LEN == 3 ? buf_[loc + 1] == chr[1] : std::memcmp(&buf_[loc + 1], chr + 1, LEN - 1) == 0))) {- size_t loc = s - lcp + i - buf_;- if (loc + LEN + min > end_ || pat_->predict_match(&buf_[loc + LEN], min))+ if (pat_->predict_match(&buf_[loc + LEN], min)) { set_current(loc); return true; } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + LEN + min > end_)@@ -2734,7 +2896,7 @@ bool Matcher::advance_chars_pmh(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - LEN + 1;+ const char *e = buf_ + end_ + lcp - LEN - min + 1; while (s < e) { do@@ -2746,10 +2908,10 @@ bool Matcher::advance_chars_pmh(size_t loc) break; } if (LEN == 2 ||- (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 2) == 0))+ (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 1) == 0)) { loc = s - lcp - buf_;- if (loc + LEN + min > end_ || pat_->predict_match(&buf_[loc + LEN], min))+ if (pat_->predict_match(&buf_[loc + LEN], min)) { set_current(loc); return true;@@ -2800,8 +2962,7 @@ bool Matcher::advance_string(size_t loc) } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + len > end_)@@ -2816,8 +2977,7 @@ bool Matcher::advance_string(size_t loc) const char *e = buf_ + end_ + lcp - len + 1; if (simd_advance_string_neon(s, e)) return true;- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + len > end_)@@ -2856,9 +3016,7 @@ bool Matcher::advance_string(size_t loc) } } -#if defined(WITH_STRING_PM)--/// String followed by 1 to 3 minimal char pattern+/// String followed by 1 to 4 characters bool Matcher::advance_string_pma(size_t loc) { const char *chr = pat_->chr_;@@ -2871,7 +3029,7 @@ bool Matcher::advance_string_pma(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - len + 1;+ const char *e = buf_ + end_ + lcp - len - min + 1; __m128i vlcp = _mm_set1_epi8(chr[lcp]); __m128i vlcs = _mm_set1_epi8(chr[lcs]); while (s <= e - 16)@@ -2897,8 +3055,7 @@ bool Matcher::advance_string_pma(size_t loc) } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + len + min > end_)@@ -2910,11 +3067,10 @@ bool Matcher::advance_string_pma(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - len + 1;+ const char *e = buf_ + end_ + lcp - len - min + 1; if (simd_advance_string_pma_neon(s, e)) return true;- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + len + min > end_)@@ -2926,7 +3082,7 @@ bool Matcher::advance_string_pma(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - len + 1;+ const char *e = buf_ + end_ + lcp - len - min + 1; while (s < e) { do@@ -2956,7 +3112,7 @@ bool Matcher::advance_string_pma(size_t loc) } } -/// String followed by 4 minimal char pattern+/// String followed by 4 to 8 characters bool Matcher::advance_string_pmh(size_t loc) { const char *chr = pat_->chr_;@@ -2969,7 +3125,7 @@ bool Matcher::advance_string_pmh(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - len + 1;+ const char *e = buf_ + end_ + lcp - len - min + 1; __m128i vlcp = _mm_set1_epi8(chr[lcp]); __m128i vlcs = _mm_set1_epi8(chr[lcs]); while (s <= e - 16)@@ -2985,7 +3141,7 @@ bool Matcher::advance_string_pmh(size_t loc) if (std::memcmp(s - lcp + offset, chr, len) == 0) { loc = s - lcp + offset - buf_;- if (loc + len + min > end_ || pat_->predict_match(&buf_[loc + len], min))+ if (pat_->predict_match(&buf_[loc + len], min)) { set_current(loc); return true;@@ -2995,8 +3151,7 @@ bool Matcher::advance_string_pmh(size_t loc) } s += 16; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + len + min > end_)@@ -3008,11 +3163,10 @@ bool Matcher::advance_string_pmh(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - len + 1;+ const char *e = buf_ + end_ + lcp - len - min + 1; if (simd_advance_string_pmh_neon(s, e)) return true;- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + len + min > end_)@@ -3024,7 +3178,7 @@ bool Matcher::advance_string_pmh(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - len + 1;+ const char *e = buf_ + end_ + lcp - len - min + 1; while (s < e) { do@@ -3038,7 +3192,7 @@ bool Matcher::advance_string_pmh(size_t loc) if (std::memcmp(s - lcp, chr, len) == 0) { loc = s - lcp - buf_;- if (loc + len + min > end_ || pat_->predict_match(&buf_[loc + len], min))+ if (pat_->predict_match(&buf_[loc + len], min)) { set_current(loc); return true;@@ -3054,8 +3208,6 @@ bool Matcher::advance_string_pmh(size_t loc) } } -#endif // WITH_STRING_PM- #if defined(HAVE_NEON) // Implements NEON/AArch64 string search scheme based on http://0x80.pl/articles/simd-friendly-karp-rabin.html 64 bit optimized@@ -3078,38 +3230,48 @@ bool Matcher::simd_advance_string_neon(const char *&s, const char *e) uint64_t mask = vgetq_lane_u64(vmask64, 0); if (mask != 0) {- for (uint16_t i = 0; i < 8; ++i)+ size_t loc = s - lcp - buf_;+ if (static_cast<uint32_t>(mask) == 0) {- if ((mask & 0xff) && std::memcmp(s - lcp + i, chr, len) == 0)+ mask >>= 32;+ loc += 4;+ }+ do+ {+ if ((mask & 0xff) && std::memcmp(&buf_[loc], chr, len) == 0) {- size_t loc = s - lcp + i - buf_; set_current(loc); return true; } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } mask = vgetq_lane_u64(vmask64, 1); if (mask != 0) {- for (uint16_t i = 8; i < 16; ++i)+ size_t loc = s - lcp + 8 - buf_;+ if (static_cast<uint32_t>(mask) == 0) {- if ((mask & 0xff) && std::memcmp(s - lcp + i, chr, len) == 0)+ mask >>= 32;+ loc += 4;+ }+ do+ {+ if ((mask & 0xff) && std::memcmp(&buf_[loc], chr, len) == 0) {- size_t loc = s - lcp + i - buf_; set_current(loc); return true; } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } s += 16; } return false; } -#if defined(WITH_STRING_PM)- // Implements NEON/AArch64 string search scheme based on http://0x80.pl/articles/simd-friendly-karp-rabin.html 64 bit optimized bool Matcher::simd_advance_string_pma_neon(const char *&s, const char *e) {@@ -3130,11 +3292,16 @@ bool Matcher::simd_advance_string_pma_neon(const char *&s, const char *e) uint64_t mask = vgetq_lane_u64(vmask64, 0); if (mask != 0) {- for (uint16_t i = 0; i < 8; ++i)+ size_t loc = s - lcp - buf_;+ if (static_cast<uint32_t>(mask) == 0)+ {+ mask >>= 32;+ loc += 4;+ }+ do {- if ((mask & 0xff) && std::memcmp(s - lcp + i, chr, len) == 0)+ if ((mask & 0xff) && std::memcmp(&buf_[loc], chr, len) == 0) {- size_t loc = s - lcp + i - buf_; if (loc + len + 4 > end_ || pat_->predict_match(&buf_[loc + len])) { set_current(loc);@@ -3142,16 +3309,22 @@ bool Matcher::simd_advance_string_pma_neon(const char *&s, const char *e) } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } mask = vgetq_lane_u64(vmask64, 1); if (mask != 0) {- for (uint16_t i = 8; i < 16; ++i)+ size_t loc = s - lcp + 8 - buf_;+ if (static_cast<uint32_t>(mask) == 0) {- if ((mask & 0xff) && std::memcmp(s - lcp + i, chr, len) == 0)+ mask >>= 32;+ loc += 4;+ }+ do+ {+ if ((mask & 0xff) && std::memcmp(&buf_[loc], chr, len) == 0) {- size_t loc = s - lcp + i - buf_; if (loc + len + 4 > end_ || pat_->predict_match(&buf_[loc + len])) { set_current(loc);@@ -3159,7 +3332,8 @@ bool Matcher::simd_advance_string_pma_neon(const char *&s, const char *e) } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } s += 16; }@@ -3172,7 +3346,7 @@ bool Matcher::simd_advance_string_pmh_neon(const char *&s, const char *e) uint16_t lcp = pat_->lcp_; uint16_t lcs = pat_->lcs_; size_t len = pat_->len_;- size_t min = pat_->min_; // min >= 4+ size_t min = pat_->min_; const char *chr = pat_->chr_; uint8x16_t vlcp = vdupq_n_u8(chr[lcp]); uint8x16_t vlcs = vdupq_n_u8(chr[lcs]);@@ -3187,47 +3361,57 @@ bool Matcher::simd_advance_string_pmh_neon(const char *&s, const char *e) uint64_t mask = vgetq_lane_u64(vmask64, 0); if (mask != 0) {- for (uint16_t i = 0; i < 8; ++i)+ size_t loc = s - lcp - buf_;+ if (static_cast<uint32_t>(mask) == 0) {- if ((mask & 0xff) && std::memcmp(s - lcp + i, chr, len) == 0)+ mask >>= 32;+ loc += 4;+ }+ do+ {+ if ((mask & 0xff) && std::memcmp(&buf_[loc], chr, len) == 0) {- size_t loc = s - lcp + i - buf_;- if (loc + len + min > end_ || pat_->predict_match(&buf_[loc + len], min))+ if (pat_->predict_match(&buf_[loc + len], min)) { set_current(loc); return true; } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } mask = vgetq_lane_u64(vmask64, 1); if (mask != 0) {- for (uint16_t i = 8; i < 16; ++i)+ size_t loc = s - lcp + 8 - buf_;+ if (static_cast<uint32_t>(mask) == 0) {- if ((mask & 0xff) && std::memcmp(s - lcp + i, chr, len) == 0)+ mask >>= 32;+ loc += 4;+ }+ do+ {+ if ((mask & 0xff) && std::memcmp(&buf_[loc], chr, len) == 0) {- size_t loc = s - lcp + i - buf_;- if (loc + len + min > end_ || pat_->predict_match(&buf_[loc + len], min))+ if (pat_->predict_match(&buf_[loc + len], min)) { set_current(loc); return true; } } mask >>= 8;- }+ ++loc;+ } while (mask != 0); } s += 16; } return false; } -#endif // WITH_STRING_PM- #endif // HAVE_NEON -/// My improved Boyer-Moore string search+/// My homegrown improved Boyer-Moore string search, a fallback method bool Matcher::advance_string_bm(size_t loc) { const char *chr = pat_->chr_;@@ -3283,9 +3467,7 @@ bool Matcher::advance_string_bm(size_t loc) } } -#if defined(WITH_STRING_PM)--/// My improved Boyer-Moore string search followed by a 1 to 3 minimal char pattern, using PM4+/// My homegrown improved Boyer-Moore string search followed by 1 to 3 minimal byte long patterns, using PM4 bool Matcher::advance_string_bm_pma(size_t loc) { const char *chr = pat_->chr_;@@ -3344,7 +3526,7 @@ bool Matcher::advance_string_bm_pma(size_t loc) } } -/// My improved Boyer-Moore string search followed by a 4 minimal char pattern, using PM+/// My homegrown improved Boyer-Moore string search followed by 4 minimal bytes long patterns bool Matcher::advance_string_bm_pmh(size_t loc) { const char *chr = pat_->chr_;@@ -3404,6 +3586,4 @@ bool Matcher::advance_string_bm_pmh(size_t loc) } } -#endif // WITH_STRING_PM- } // namespace reflex
@@ -46,6 +46,34 @@ namespace reflex { #if defined(HAVE_AVX2) || defined(HAVE_AVX512BW) +#define SIMD_INIT_ADV_PAT_PIN_CASE_AVX2(PIN) \+ switch (pat_->min_) \+ { \+ case 0: \+ case 1: \+ adv_ = &Matcher::simd_advance_pattern_pin##PIN##_one_avx2; \+ break; \+ case 2: \+ case 3: \+ adv_ = &Matcher::simd_advance_pattern_pin##PIN##_pma_avx2; \+ break; \+ case 4: \+ adv_ = &Matcher::simd_advance_pattern_pin##PIN##_pmh_avx2<4>; \+ break; \+ case 5: \+ adv_ = &Matcher::simd_advance_pattern_pin##PIN##_pmh_avx2<5>; \+ break; \+ case 6: \+ adv_ = &Matcher::simd_advance_pattern_pin##PIN##_pmh_avx2<6>; \+ break; \+ case 7: \+ adv_ = &Matcher::simd_advance_pattern_pin##PIN##_pmh_avx2<7>; \+ break; \+ case 8: \+ adv_ = &Matcher::simd_advance_pattern_pin##PIN##_pmh_avx2<8>; \+ break; \+ }+ // AVX2 runtime optimized function callback overrides void Matcher::simd_init_advance_avx2() {@@ -54,75 +82,74 @@ void Matcher::simd_init_advance_avx2() switch (pat_->pin_) { case 1:- if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_pattern_pin1_pma_avx2;- else- adv_ = &Matcher::simd_advance_pattern_pin1_pmh_avx2;+ switch (pat_->min_)+ {+ case 2:+ case 3:+ adv_ = &Matcher::simd_advance_pattern_pin1_pma_avx2;+ break;+ case 4:+ adv_ = &Matcher::simd_advance_pattern_pin1_pmh_avx2<4>;+ break;+ case 5:+ adv_ = &Matcher::simd_advance_pattern_pin1_pmh_avx2<5>;+ break;+ case 6:+ adv_ = &Matcher::simd_advance_pattern_pin1_pmh_avx2<6>;+ break;+ case 7:+ adv_ = &Matcher::simd_advance_pattern_pin1_pmh_avx2<7>;+ break;+ case 8:+ adv_ = &Matcher::simd_advance_pattern_pin1_pmh_avx2<8>;+ break;+ } break; case 2:- if (pat_->min_ == 1)- adv_ = &Matcher::simd_advance_pattern_pin2_one_avx2;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_pattern_pin2_pma_avx2;- else- adv_ = &Matcher::simd_advance_pattern_pin2_pmh_avx2;+ SIMD_INIT_ADV_PAT_PIN_CASE_AVX2(2); break; case 3:- if (pat_->min_ == 1)- adv_ = &Matcher::simd_advance_pattern_pin3_one_avx2;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_pattern_pin3_pma_avx2;- else- adv_ = &Matcher::simd_advance_pattern_pin3_pmh_avx2;+ SIMD_INIT_ADV_PAT_PIN_CASE_AVX2(3); break; case 4:- if (pat_->min_ == 1)- adv_ = &Matcher::simd_advance_pattern_pin4_one_avx2;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_pattern_pin4_pma_avx2;- else- adv_ = &Matcher::simd_advance_pattern_pin4_pmh_avx2;+ SIMD_INIT_ADV_PAT_PIN_CASE_AVX2(4); break; case 5:- if (pat_->min_ == 1)- adv_ = &Matcher::simd_advance_pattern_pin5_one_avx2;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_pattern_pin5_pma_avx2;- else- adv_ = &Matcher::simd_advance_pattern_pin5_pmh_avx2;+ SIMD_INIT_ADV_PAT_PIN_CASE_AVX2(5); break; case 6:- if (pat_->min_ == 1)- adv_ = &Matcher::simd_advance_pattern_pin6_one_avx2;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_pattern_pin6_pma_avx2;- else- adv_ = &Matcher::simd_advance_pattern_pin6_pmh_avx2;+ SIMD_INIT_ADV_PAT_PIN_CASE_AVX2(6); break; case 7:- if (pat_->min_ == 1)- adv_ = &Matcher::simd_advance_pattern_pin7_one_avx2;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_pattern_pin7_pma_avx2;- else- adv_ = &Matcher::simd_advance_pattern_pin7_pmh_avx2;+ SIMD_INIT_ADV_PAT_PIN_CASE_AVX2(7); break; case 8:- if (pat_->min_ == 1)- adv_ = &Matcher::simd_advance_pattern_pin8_one_avx2;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_pattern_pin8_pma_avx2;- else- adv_ = &Matcher::simd_advance_pattern_pin8_pmh_avx2;+ SIMD_INIT_ADV_PAT_PIN_CASE_AVX2(8); break; case 16:- if (pat_->min_ == 1)- adv_ = &Matcher::simd_advance_pattern_pin16_one_avx2;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_pattern_pin16_pma_avx2;- else- adv_ = &Matcher::simd_advance_pattern_pin16_pmh_avx2;+ SIMD_INIT_ADV_PAT_PIN_CASE_AVX2(16); break;+#ifdef WITH_BITAP_AVX2 // use in case vectorized bitap (hashed) is faster than serial version (typically not!!)+ default:+ switch (pat_->min_)+ {+ case 4:+ adv_ = &Matcher::simd_advance_pattern_min4_avx2<4>;+ break;+ case 5:+ adv_ = &Matcher::simd_advance_pattern_min4_avx2<5>;+ break;+ case 6:+ adv_ = &Matcher::simd_advance_pattern_min4_avx2<6>;+ break;+ case 7:+ adv_ = &Matcher::simd_advance_pattern_min4_avx2<7>;+ break;+ case 8:+ adv_ = &Matcher::simd_advance_pattern_min4_avx2<8>;+ break;+ }+#endif } } else if (pat_->len_ == 1)@@ -149,18 +176,16 @@ void Matcher::simd_init_advance_avx2() } else if (pat_->bmd_ == 0) {-#if defined(WITH_STRING_PM) if (pat_->min_ >= 4) adv_ = &Matcher::simd_advance_string_pmh_avx2; else if (pat_->min_ > 0) adv_ = &Matcher::simd_advance_string_pma_avx2; else-#endif adv_ = &Matcher::simd_advance_string_avx2; } } -// My "needle search" method when pin=1+// My homegrown "needle search" method when needle pin=1 bool Matcher::simd_advance_pattern_pin1_pma_avx2(size_t loc) { const char *chr = pat_->chr_;@@ -191,8 +216,7 @@ bool Matcher::simd_advance_pattern_pin1_pma_avx2(size_t loc) } s += 32; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + min > end_)@@ -203,11 +227,11 @@ bool Matcher::simd_advance_pattern_pin1_pma_avx2(size_t loc) return advance_pattern_pin1_pma(loc); } -// My "needle search" method when pin=1+// My homegrown "needle search" method when needle pin=1+template <uint8_t MIN> bool Matcher::simd_advance_pattern_pin1_pmh_avx2(size_t loc) { const char *chr = pat_->chr_;- size_t min = pat_->min_; uint16_t lcp = pat_->lcp_; uint16_t lcs = pat_->lcs_; __m256i vlcp = _mm256_set1_epi8(chr[0]);@@ -215,7 +239,7 @@ bool Matcher::simd_advance_pattern_pin1_pmh_avx2(size_t loc) while (true) { const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - min + 1;+ const char *e = buf_ + end_ + lcp - MIN + 1; while (s <= e - 32) { __m256i vstrlcp = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s));@@ -228,25 +252,24 @@ bool Matcher::simd_advance_pattern_pin1_pmh_avx2(size_t loc) uint32_t offset = ctz(mask); loc = s - lcp + offset - buf_; set_current(loc);- if (pat_->predict_match(&buf_[loc], min))+ if (pat_->predict_match(&buf_[loc], MIN)) return true; mask &= mask - 1; } s += 32; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1;- if (loc + min > end_)+ if (loc + MIN > end_) return false;- if (loc + min + 31 > end_)+ if (loc + MIN + 31 > end_) break; }- return advance_pattern_pin1_pmh(loc);+ return advance_pattern_pin1_pmh<MIN>(loc); } -// My "needle search" methods+// My homegrown "needle search" methods #define ADV_PAT_PIN_ONE(N, INIT, COMP) \ bool Matcher::simd_advance_pattern_pin##N##_one_avx2(size_t loc) \ { \@@ -283,7 +306,7 @@ bool Matcher::simd_advance_pattern_pin##N##_one_avx2(size_t loc) \ if (loc + 32 > end_) \ break; \ } \- return advance_pattern(loc); \+ return advance_pattern_pma(loc); \ } ADV_PAT_PIN_ONE(2, \@@ -412,7 +435,7 @@ ADV_PAT_PIN_ONE(16, \ veq = _mm256_or_si256(veq, _mm256_cmpeq_epi8(vf, vstr)); \ ) -// My "needle search" methods+// My homegrown "needle search" methods #define ADV_PAT_PIN(N, INIT, COMP) \ bool Matcher::simd_advance_pattern_pin##N##_pma_avx2(size_t loc) \ { \@@ -446,8 +469,7 @@ bool Matcher::simd_advance_pattern_pin##N##_pma_avx2(size_t loc) \ } \ s += 32; \ } \- s -= lcp; \- loc = s - buf_; \+ loc = s - lcp - buf_; \ set_current_and_peek_more(loc - 1); \ loc = cur_ + 1; \ if (loc + min > end_) \@@ -455,20 +477,20 @@ bool Matcher::simd_advance_pattern_pin##N##_pma_avx2(size_t loc) \ if (loc + min + 31 > end_) \ break; \ } \- return advance_pattern(loc); \+ return advance_pattern_pma(loc); \ } \ \+template <uint8_t MIN> \ bool Matcher::simd_advance_pattern_pin##N##_pmh_avx2(size_t loc) \ { \ const char *chr = pat_->chr_; \- size_t min = pat_->min_; \ uint16_t lcp = pat_->lcp_; \ uint16_t lcs = pat_->lcs_; \ INIT \ while (true) \ { \ const char *s = buf_ + loc + lcp; \- const char *e = buf_ + end_ + lcp - min + 1; \+ const char *e = buf_ + end_ + lcp - MIN + 1; \ while (s <= e - 32) \ { \ __m256i vstrlcp = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s)); \@@ -481,7 +503,7 @@ bool Matcher::simd_advance_pattern_pin##N##_pmh_avx2(size_t loc) \ { \ uint32_t offset = ctz(mask); \ loc = s - lcp + offset - buf_; \- if (pat_->predict_match(&buf_[loc], min)) \+ if (pat_->predict_match(&buf_[loc], MIN)) \ { \ set_current(loc); \ return true; \@@ -490,16 +512,15 @@ bool Matcher::simd_advance_pattern_pin##N##_pmh_avx2(size_t loc) \ } \ s += 32; \ } \- s -= lcp; \- loc = s - buf_; \+ loc = s - lcp - buf_; \ set_current_and_peek_more(loc - 1); \ loc = cur_ + 1; \- if (loc + min > end_) \+ if (loc + MIN > end_) \ return false; \- if (loc + min + 31 > end_) \+ if (loc + MIN + 31 > end_) \ break; \ } \- return advance_pattern_min4(loc); \+ return advance_pattern_min4<MIN>(loc); \ } ADV_PAT_PIN(2, \@@ -722,6 +743,90 @@ ADV_PAT_PIN(16, \ veqlcs = _mm256_or_si256(veqlcs, _mm256_cmpeq_epi8(vlcsf, vstrlcs)); \ ) +#ifdef WITH_BITAP_AVX2 // use in case vectorized bitap (hashed) is faster than serial version (typically not!!)++/// Minimal 4 byte long patterns (MIN>=4) using bitap hashed pairs with AVX2+template <uint8_t MIN>+bool Matcher::simd_advance_pattern_min4_avx2(size_t loc)+{+ const uint32_t btap = Pattern::Const::BTAP;+ const __m128i vmod = _mm_set1_epi32(btap - 1);+ const __m128i vselect = _mm_set_epi8(-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 13, 9, 5, 1);+ const __m128i voffset = _mm_set_epi32(0, btap, 2 * btap, 3 * btap);+ uint32_t state0 = ~0U << (8 - (MIN - 1));+ uint32_t state1 = ~0U << (8 - (MIN - 2));+ uint32_t state2 = ~0U << (8 - (MIN - 3));+ uint32_t state3 = ~0U << (8 - (MIN - 4));+ if (MIN <= 6)+ state3 = state2;+ if (MIN <= 5)+ state2 = state1;+ if (MIN <= 4)+ state1 = state0;+ __m128i vstate = _mm_set_epi32(state0, state1, state2, state3);+ __m128i vc0 = _mm_set1_epi32(buf_[loc++]);+ while (true)+ {+ const char *s = buf_ + loc;+ const char *e = buf_ + end_ - 3;+ while (s < e)+ {+ __m128i vc1 = _mm_cvtepu8_epi32(_mm_loadu_si32(reinterpret_cast<const uint32_t*>(s)));+ vc0 = _mm_alignr_epi8(vc1, vc0, 12);+ // hash+ __m128i vh = _mm_and_si128(_mm_xor_si128(vc0, _mm_slli_epi32(vc1, 6)), vmod);+ // gather bitap hashed bits+ __m128i vb = _mm_i32gather_epi32(reinterpret_cast<const int32_t*>(pat_->vtp_), _mm_or_si128(vh, voffset), 2);+ // shift-or+ vstate = _mm_or_si128(_mm_slli_epi32(vstate, 4), vb);+ // pass last char to the next iteration+ vc0 = vc1;+ // get most significant bit of each byte, check each 2nd byte of the 4x32 bit words+ uint32_t mask = _mm_extract_epi32(_mm_shuffle_epi8(vstate, vselect), 0);+ if ((mask & 0x00000008) == 0 && pat_->predict_match(s - MIN + 0, MIN))+ {+ loc = s - buf_ - MIN + 0;+ set_current(loc);+ return true;+ }+ if ((mask & 0x00000404) == 0 && pat_->predict_match(s - MIN + 1, MIN))+ {+ loc = s - buf_ - MIN + 1;+ set_current(loc);+ return true;+ }+ if ((mask & 0x00020202) == 0 && pat_->predict_match(s - MIN + 2, MIN))+ {+ loc = s - buf_ - MIN + 2;+ set_current(loc);+ return true;+ }+ if ((mask & 0x01010101) == 0 && pat_->predict_match(s - MIN + 3, MIN))+ {+ loc = s - buf_ - MIN + 3;+ set_current(loc);+ return true;+ }+ // butterfly-or:+ // a b c d input vec+ // c d a b swizzle+ // a|c b|d c|a d|b or+ // b|d a|c d|b c|a swizzle+ // a|c|b|d b|d|a|c c|a|d|b d|b|c|a or+ vstate = _mm_or_si128(vstate, _mm_shuffle_epi32(vstate, 0x4e)); // = 01 00 11 10 = 1 0 3 2+ vstate = _mm_or_si128(vstate, _mm_shuffle_epi32(vstate, 0xb1)); // = 10 11 00 01 = 2 3 0 1+ s += 4;+ }+ loc = s - buf_;+ set_current_and_peek_more(loc - 1);+ loc = cur_ + 1;+ if (loc + 3 >= end_)+ return advance_pattern_min4<MIN>(loc - MIN);+ }+}++#endif+ /// Few chars template<uint8_t LEN> bool Matcher::simd_advance_chars_avx2(size_t loc)@@ -756,8 +861,7 @@ bool Matcher::simd_advance_chars_avx2(size_t loc) } s += 32; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + LEN > end_)@@ -806,8 +910,7 @@ bool Matcher::simd_advance_chars_pma_avx2(size_t loc) } s += 32; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + LEN + min > end_)@@ -854,8 +957,7 @@ bool Matcher::simd_advance_chars_pmh_avx2(size_t loc) } s += 32; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + LEN + min > end_)@@ -899,8 +1001,7 @@ bool Matcher::simd_advance_string_avx2(size_t loc) } s += 32; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + len > end_)@@ -911,8 +1012,6 @@ bool Matcher::simd_advance_string_avx2(size_t loc) return advance_string(loc); } -#if defined(WITH_STRING_PM)- /// Implements AVX2 string search scheme based on http://0x80.pl/articles/simd-friendly-karp-rabin.html bool Matcher::simd_advance_string_pma_avx2(size_t loc) {@@ -950,8 +1049,7 @@ bool Matcher::simd_advance_string_pma_avx2(size_t loc) } s += 32; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + len + min > end_)@@ -997,8 +1095,7 @@ bool Matcher::simd_advance_string_pmh_avx2(size_t loc) } s += 32; }- s -= lcp;- loc = s - buf_;+ loc = s - lcp - buf_; set_current_and_peek_more(loc - 1); loc = cur_ + 1; if (loc + len + min > end_)@@ -1009,8 +1106,6 @@ bool Matcher::simd_advance_string_pmh_avx2(size_t loc) return advance_string_pmh(loc); } -#endif // WITH_STRING_PM- #else // appease ranlib "has no symbols"
@@ -203,38 +203,68 @@ void Pattern::init(const char *options, const uint8_t *pred) size_t n = 2 + len_; if (len_ == 0) {- // get bitap bit_[] parameters- for (size_t i = 0; i < 256; ++i)+ // load bit_[] parameters+ for (int i = 0; i < 256; ++i) bit_[i] = ~pred[i + n]; n += 256;+ if ((pred[1] & 0x80) != 0)+ {+ // load tap_[] parameters+ for (int i = 0; i < Const::BTAP; ++i)+ tap_[i] = ~pred[i + n];+ n += Const::BTAP;+ }+ else+ {+ // lossly (uncorrelated) populate tap_[] from bit_[] when missing, for backward compatibility+ std::memset(tap_, 0xff, sizeof(tap_));+ for (size_t k = 0; k < min_; ++k)+ {+ Bitap mask = 1 << k;+ if (k + 1 < min_)+ {+ for (Char ch = 0; ch < 256; ++ch)+ if ((bit_[ch] & mask) == 0)+ for (Char next_ch = 0; next_ch < 256; ++next_ch)+ tap_[bihash(ch, next_ch)] &= ~(~(bit_[next_ch] >> 1) & mask);+ }+ else+ {+ for (Char ch = 0; ch < 256; ++ch)+ if ((bit_[ch] & mask) == 0)+ for (Char next_ch = 0; next_ch < 256; ++next_ch)+ tap_[bihash(ch, next_ch)] &= ~mask;+ }+ }+ } } if (min_ < 4) {- // get predict match PM4 pma_[] parameters- for (size_t i = 0; i < Const::HASH; ++i)+ // load predict match PM4 pma_[] parameters+ for (int i = 0; i < Const::HASH; ++i) pma_[i] = ~pred[i + n]; } else {- // get predict match hash pmh_[] parameters- for (size_t i = 0; i < Const::HASH; ++i)+ // load predict match hash pmh_[] parameters+ for (int i = 0; i < Const::HASH; ++i) pmh_[i] = ~pred[i + n]; } n += Const::HASH; if ((pred[1] & 0x20) != 0) {- // get lookback parameters lbk_ lbm_ and cbk_[] after s-t cut and first s-t cut pattern characters fst_[]+ // load lookback parameters lbk_ lbm_ and cbk_[] after s-t cut and first s-t cut pattern characters fst_[] lbk_ = pred[n + 0] | (pred[n + 1] << 8); lbm_ = pred[n + 2] | (pred[n + 3] << 8);- for (size_t i = 0; i < 256; ++i)+ for (int i = 0; i < 256; ++i) cbk_.set(i, pred[n + 4 + (i >> 3)] & (1 << (i & 7)));- for (size_t i = 0; i < 256; ++i)+ for (int i = 0; i < 256; ++i) fst_.set(i, pred[n + 4 + 32 + (i >> 3)] & (1 << (i & 7))); n += 4 + 32 + 32; } else {- // get first pattern characters fst_[] from bitap+ // load first pattern characters fst_[] from bit_[] for (size_t i = 0; i < 256; ++i) fst_.set(i, (bit_[i] & 1) == 0); }@@ -295,13 +325,20 @@ void Pattern::init(const char *options, const uint8_t *pred) // delete the tree DFA tfa_.clear(); }- // clean up bitap and compute bitap entropy if (len_ == 0) {- // bitap entropy to estimate false positive rate- npy_ = 0; if (min_ > 0) {+ if (min_ < 8)+ {+ Bitap mask = ~((1 << min_) - 1);+ for (Char i = 0; i < 256; ++i)+ bit_[i] |= mask;+ for (Hash i = 0; i < Const::BTAP; ++i)+ tap_[i] |= mask;+ }+ // bitap entropy+ npy_ = 0; for (Char i = 0; i < 256; ++i) { bit_[i] |= ~((1 << min_) - 1);@@ -314,13 +351,27 @@ void Pattern::init(const char *options, const uint8_t *pred) npy_ += (bit_[i] & 0x40) == 0; npy_ += (bit_[i] & 0x80) == 0; }- // average entropy per bitap position, we don't use bitap when entropy is too high for short patterns+ // average entropy per pattern position, we don't use bitap when entropy is too high for short patterns npy_ /= min_;+#ifdef WITH_BITAP_AVX2 // in case vectorized bitap (hashed) is faster than serial version (typically not!)+#if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2)+ if (have_HW_AVX512BW() || have_HW_AVX2())+ {+ // vectorized bitap hashed pairs array for AVX2+ uint32_t shift = 8 - (min_ - 1);+ for (Hash j = 0; j < 4 * Const::BTAP; j += Const::BTAP, ++shift)+ for (Hash i = 0; i < Const::BTAP; ++i)+ vtp_[i + j] = tap_[i] << shift;+ }+#endif+#endif } // needle count and frequency thresholds to enable needle-based search uint16_t pinmax = 8;- uint16_t freqmax = 251;+ const uint16_t freqmax1 = 20; // upper bound for one position when needle pins>5 or 1<min<=3+ const uint16_t freqmax2 = 251; // upper bound #if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2)+ const uint16_t freqmax3 = 300; // upper bound for freqlcp+freqlcs when needle pins>8 and min>=4 if (have_HW_AVX512BW() || have_HW_AVX2()) pinmax = 16; else if (have_HW_SSE2())@@ -328,28 +379,30 @@ void Pattern::init(const char *options, const uint8_t *pred) else pinmax = 1; #elif defined(HAVE_NEON)+ const uint16_t freqmax3 = 160; // upper bound for freqlcp+freqlcs when needle pins>6 and min>=4 pinmax = 8; #else+ const uint16_t freqmax3 = 160; // checked but unused pinmax = 1; #endif- // get needles+ // find needles pin_ = 0; lcp_ = 0; lcs_ = 0; uint16_t nlcp = 65535; // max and undefined uint16_t nlcs = 65535; // max and undefined- uint8_t freqlcp = 255; // max and undefined- uint8_t freqlcs = 255; // max and undefined- size_t min = (min_ == 0 ? 1 : min_);- uint8_t score[8][3]; // avg freq, unique position k < min, number of pins n <= pinmax+ uint16_t freqlcp = 255; // max and undefined+ uint16_t freqlcs = 255; // max and undefined+ size_t min = std::max<size_t>(1, min_);+ uint8_t score[8][3]; // max freq, unique needle position k < min, number of pins n <= pinmax size_t scores = 0; for (uint8_t k = 0; k < min; ++k) {- Pred mask = 1 << k;+ Bitap mask = 1 << k; uint8_t n = 0; uint16_t max = 0; uint16_t sum = 0;- // at position k count the matching characters and find the max and sum character frequency+ // at position k count the matching characters and find the usm and max character frequency for (uint16_t i = 0; i < 256 && n <= pinmax; ++i) { if ((bit_[i] & mask) == 0)@@ -361,31 +414,38 @@ void Pattern::init(const char *options, const uint8_t *pred) sum += freq; } }- if (n > 0 && n <= pinmax && max <= freqmax)+ if (n > 0 && n <= pinmax && max <= freqmax2) {- // score average frequency, twice penalize pins > 8+ // score needle max frequency adjusted, penalty for higher number of needle pins>8 uint8_t m = static_cast<uint8_t>(std::min((sum + n - 1) / n * ((n > 8) + 1), 255));- size_t i;- for (i = 0; i < scores; ++i)+ if (m <= freqmax2) {- // keep scores sorted by average (mean) frequency- if (score[i][0] > m || (score[i][0] == m && score[i][2] > n))+ size_t i;+ for (i = 0; i < scores; ++i) {- memmove(score[i+1], score[i], static_cast<uint8_t*>(score[scores]) - static_cast<uint8_t*>(score[i]));- break;+ // keep scores sorted by average (mean) frequency or secondary by number of pins required+ if (score[i][0] > m || (score[i][0] == m && score[i][2] > n))+ {+ memmove(score[i+1], score[i], static_cast<uint8_t*>(score[scores]) - static_cast<uint8_t*>(score[i]));+ break;+ } }+ score[i][0] = m;+ score[i][1] = k;+ score[i][2] = n;+ ++scores; }- score[i][0] = m;- score[i][1] = k;- score[i][2] = n;- ++scores; } }- if (scores == 1)+ if (scores == 1 && min_ <= 3) { freqlcp = freqlcs = score[0][0]; lcp_ = lcs_ = score[0][1]; nlcp = nlcs = score[0][2];+ // no needle search for one needle position when pins>5 or when frequency is too high, use PM4 instead+ uint16_t freqmax = min_ > 1 || nlcp > 5 ? freqmax1 : freqmax2;+ if (freqlcp > freqmax)+ freqlcp = freqlcs = 255; } else if (scores >= 2) {@@ -395,35 +455,39 @@ void Pattern::init(const char *options, const uint8_t *pred) freqlcs = score[1][0]; lcs_ = score[1][1]; nlcs = score[1][2];- if (scores > 2)+ if (lcp_ + 1 == lcs_ || lcs_ + 1 == lcp_ || (nlcp <= 8 && nlcs > 8)) {- if (lcp_ + 1 == lcs_ || lcs_ + 1 == lcp_ || nlcs > 8)+ for (size_t i = 2; i < scores; ++i) {- for (size_t i = 2; i < scores; ++i)+ if (score[i][2] <= 8 && abs(lcp_ - score[i][1]) > 1) {- if (score[i][2] <= 8 && abs(lcp_ - lcs_) < abs(lcp_ - score[i][1]))- {- freqlcs = score[i][0];- lcs_ = score[i][1];- nlcs = score[i][2];- break;- }+ freqlcs = score[i][0];+ lcs_ = score[i][1];+ nlcs = score[i][2];+ break; } } } } // number of needles required uint16_t n = std::max(nlcp, nlcs);- DBGLOG("min=%zu lcp=%hu(%hu) pin=%hu nlcp=%hu(%hu) freq=%hu(%hu) npy=%zu cut=%u", min, lcp_, lcs_, n, nlcp, nlcs, freqlcp, freqlcs, npy_, cut_);- // determine if a needle-based search is worthwhile, below or meeting the thresholds- if (n <= pinmax && freqlcp <= freqmax)+ // determine if a needle-based search is worthwhile heuristically, when freqlcp + freqlcs <= freqmax+ uint16_t freqmax = 2 * freqmax2;+#if defined(HAVE_NEON)+ if (n > 6 && min_ >= 4)+ freqmax = freqmax3;+#else // only runtime AVX2 supports pins>8, which should be constrained, because it is noisy+ if (n > 8 && min_ >= 3)+ freqmax = freqmax3;+#endif+ if (n > 0 && n <= pinmax && freqlcp + freqlcs <= freqmax) {- // bridge the gap from 9 to 16 to handle 9 to 16 combined+ // bridge the gap from 9 to 16 to handle 9 to 16 combined with AVX2 if (n > 8) n = 16; uint16_t j = 0, k = n;- Pred masklcp = 1 << lcp_;- Pred masklcs = 1 << lcs_;+ Bitap masklcp = 1 << lcp_;+ Bitap masklcs = 1 << lcs_; for (uint16_t i = 0; i < 256; ++i) { if ((bit_[i] & masklcp) == 0)@@ -438,10 +502,11 @@ void Pattern::init(const char *options, const uint8_t *pred) chr_[k] = chr_[k - 1]; pin_ = n; }+ DBGLOG("min=%zu lcp=%hu(%hu) pin=%zu nlcp=%hu(%hu) freq=%hu(%hu) npy=%hu cut=%u", min, lcp_, lcs_, pin_, nlcp, nlcs, freqlcp, freqlcs, npy_, cut_); } else if (len_ > 1) {- // produce lcp and lcs positions and Boyer-Moore bms_[] shifts when bmd_ > 0+ // produce 1st lcp and 2nd lcs needle positions and Boyer-Moore bms_[] shifts when bmd_ > 0 uint8_t n = static_cast<uint8_t>(len_); // okay to cast: actually never more than 255 uint16_t i; for (i = 0; i < 256; ++i)@@ -526,7 +591,7 @@ void Pattern::init(const char *options, const uint8_t *pred) } } }- DBGLOG("len=%zu bmd=%zu lcp=%hu(%hu)", len_, bmd_, lcp_, lcs_);+ DBGLOG("len=%zu min=%zu bmd=%zu lcp=%hu(%hu)", len_, min_, bmd_, lcp_, lcs_); } } @@ -686,7 +751,8 @@ void Pattern::parse( loc = 0; } }- bol_ = at(loc) == '^';+ // assume bol unless pattern is empty, reset flag later when no ^ is used at the start of (sub)patterns+ bol_ = at(loc) != '\0'; do { Location end = loc;@@ -726,6 +792,7 @@ void Pattern::parse( if (loc < end) { // string pattern found w/o regex metas: merge string into the tree DFA+ bol_ = false; bool quote = false; #ifdef WITH_TREE_DFA DFA::State *t = tfa_.start();@@ -793,8 +860,6 @@ void Pattern::parse( } else {- if (at(loc) != '^')- bol_ = false; parse2( true, loc,@@ -945,12 +1010,19 @@ void Pattern::parse2( { pos_add(a_pos, Position(loc)); loc += 2;- begin = false;+ if (begin)+ {+ bol_ = false;+ begin = false;+ } } else { if (escapes_at(loc, "ij"))+ {+ bol_ = false; begin = false;+ } break; } }@@ -1070,7 +1142,11 @@ void Pattern::parse3( if (c == '*' || c == '+' || c == '?') { if (c == '*' || c == '?')+ { nullable = true;+ if (begin)+ bol_ = false;+ } if (at(++loc) == '?') { if (++lazyidx == 0)@@ -1374,92 +1450,98 @@ void Pattern::parse4( error(regex_error::mismatched_parens, loc); } }- else if (c == '[')+ else {- pos_add(firstpos, loc);- pos_add(lastpos, loc);- nullable = false;- if ((c = at(++loc)) == '^')- c = at(++loc);- while (c != '\0')+ // reset the bol flag if the begin of a pattern has no ^ anchor+ if (begin && c != '^')+ bol_ = false;+ if (c == '[') {- if (c == '[' && (at(loc + 1) == ':' || at(loc + 1) == '.' || at(loc + 1) == '='))+ pos_add(firstpos, loc);+ pos_add(lastpos, loc);+ nullable = false;+ if ((c = at(++loc)) == '^')+ c = at(++loc);+ while (c != '\0') {- size_t c_loc = find_at(loc + 2, static_cast<char>(at(loc + 1)));- if (c_loc != std::string::npos && at(static_cast<Location>(c_loc + 1)) == ']')- loc = static_cast<Location>(c_loc + 1);+ if (c == '[' && (at(loc + 1) == ':' || at(loc + 1) == '.' || at(loc + 1) == '='))+ {+ size_t c_loc = find_at(loc + 2, static_cast<char>(at(loc + 1)));+ if (c_loc != std::string::npos && at(static_cast<Location>(c_loc + 1)) == ']')+ loc = static_cast<Location>(c_loc + 1);+ }+ else if (c == opt_.e && !opt_.b)+ {+ ++loc;+ }+ if ((c = at(++loc)) == ']')+ break; }- else if (c == opt_.e && !opt_.b)- {+ if (c == '\0')+ error(regex_error::mismatched_brackets, loc);+ ++loc;+ }+ else if ((c == '"' && opt_.q) || escape_at(loc) == 'Q')+ {+ bool quoted = (c == '"');+ if (!quoted) ++loc;+ Location q_loc = ++loc;+ c = at(loc);+ if (c != '\0' && (quoted ? c != '"' : c != opt_.e || at(loc + 1) != 'E'))+ {+ pos_add(firstpos, loc);+ Position p;+ do+ {+ if (quoted && c == opt_.e && at(loc + 1) == '"')+ ++loc;+ if (p != Position::NPOS)+ pos_add(followpos[p.pos()], loc);+ p = loc++;+ c = at(loc);+ } while (c != '\0' && (!quoted || c != '"') && (quoted || c != opt_.e || at(loc + 1) != 'E'));+ pos_add(lastpos, p);+ nullable = false;+ modifiers[ModConst::q].insert(q_loc, loc - 1); }- if ((c = at(++loc)) == ']')- break;+ if (!quoted && at(loc) != '\0')+ ++loc;+ if (at(loc) != '\0')+ ++loc;+ else+ error(regex_error::mismatched_quotation, loc); }- if (c == '\0')- error(regex_error::mismatched_brackets, loc);- ++loc;- }- else if ((c == '"' && opt_.q) || escape_at(loc) == 'Q')- {- bool quoted = (c == '"');- if (!quoted)+ else if (c == '#' && opt_.x)+ { ++loc;- Location q_loc = ++loc;- c = at(loc);- if (c != '\0' && (quoted ? c != '"' : c != opt_.e || at(loc + 1) != 'E'))+ while ((c = at(loc)) != '\0' && c != '\n')+ ++loc;+ if (c == '\n')+ ++loc;+ }+ else if (std::isspace(c) && opt_.x)+ {+ ++loc;+ }+ else if (c == ')')+ {+ error(begin ? regex_error::empty_expression : regex_error::mismatched_parens, loc++);+ }+ else if (c != '\0' && c != '|' && c != '?' && c != '*' && c != '+') { pos_add(firstpos, loc);- Position p;- do- {- if (quoted && c == opt_.e && at(loc + 1) == '"')- ++loc;- if (p != Position::NPOS)- pos_add(followpos[p.pos()], loc);- p = loc++;- c = at(loc);- } while (c != '\0' && (!quoted || c != '"') && (quoted || c != opt_.e || at(loc + 1) != 'E'));- pos_add(lastpos, p);+ pos_add(lastpos, loc); nullable = false;- modifiers[ModConst::q].insert(q_loc, loc - 1);+ if (c == opt_.e)+ c = parse_esc(loc);+ else+ ++loc;+ }+ else if (c != '\0')+ {+ error(begin ? regex_error::empty_expression : regex_error::invalid_syntax, loc); }- if (!quoted && at(loc) != '\0')- ++loc;- if (at(loc) != '\0')- ++loc;- else- error(regex_error::mismatched_quotation, loc);- }- else if (c == '#' && opt_.x)- {- ++loc;- while ((c = at(loc)) != '\0' && c != '\n')- ++loc;- if (c == '\n')- ++loc;- }- else if (std::isspace(c) && opt_.x)- {- ++loc;- }- else if (c == ')')- {- error(begin ? regex_error::empty_expression : regex_error::mismatched_parens, loc++);- }- else if (c != '\0' && c != '|' && c != '?' && c != '*' && c != '+')- {- pos_add(firstpos, loc);- pos_add(lastpos, loc);- nullable = false;- if (c == opt_.e)- c = parse_esc(loc);- else- ++loc;- }- else if (begin && c != '\0') // permits empty regex pattern but not empty subpatterns- {- error(regex_error::empty_expression, loc); } DBGLOG("END parse4()"); }@@ -1525,7 +1607,7 @@ Pattern::Char Pattern::parse_esc(Location& loc, Chars *chars) const } else if (c == 'e') {- c = 0x1B;+ c = 0x1b; ++loc; } else if (c == 'N')@@ -1595,7 +1677,7 @@ Pattern::Char Pattern::parse_esc(Location& loc, Chars *chars) const } ++loc; }- if (c <= 0xFF && chars != NULL)+ if (c <= 0xff && chars != NULL) chars->add(c); return c; }@@ -1751,7 +1833,7 @@ void Pattern::compile( if (opt_.i) { // normalize by removing upper case if option i (case insensitivem matching) is enabled- static const uint64_t upper[5] = { 0x0000000000000000ULL, 0x0000000007FFFFFEULL, 0ULL, 0ULL, 0ULL };+ static const uint64_t upper[5] = { 0x0000000000000000ULL, 0x0000000007fffffeULL, 0ULL, 0ULL, 0ULL }; chars -= Chars(upper); } if (chars.any())@@ -1893,7 +1975,7 @@ void Pattern::compile( if (opt_.i) { // normalize by removing upper case if option i (case insensitive matching) is enabled- static const uint64_t upper[5] = { 0x0000000000000000ULL, 0x0000000007FFFFFEULL, 0ULL, 0ULL, 0ULL };+ static const uint64_t upper[5] = { 0x0000000000000000ULL, 0x0000000007fffffeULL, 0ULL, 0ULL, 0ULL }; chars -= Chars(upper); } if (chars.any())@@ -2040,7 +2122,7 @@ void Pattern::compile( if (opt_.i) { // normalize by removing upper case if option i (case insensitive matching) is enabled- static const uint64_t upper[5] = { 0x0000000000000000ULL, 0x0000000007FFFFFEULL, 0ULL, 0ULL, 0ULL };+ static const uint64_t upper[5] = { 0x0000000000000000ULL, 0x0000000007fffffeULL, 0ULL, 0ULL, 0ULL }; chars -= Chars(upper); } if (chars.any())@@ -2154,44 +2236,29 @@ void Pattern::greedy(Positions& pos) const *p = p->lazy(0); } -void Pattern::trim_anchors(Positions& follow, const Position p) const+void Pattern::trim_anchors(Positions& follow) const { #ifdef DEBUG DBGLOG("trim_anchors({"); for (Positions::const_iterator q = follow.begin(); q != follow.end(); ++q) DBGLOGPOS(*q);- DBGLOGA(" }, %u)", p.loc());+ DBGLOGA(" })"); #endif Positions::iterator q = follow.begin(); Positions::iterator end = follow.end();- // check if we follow into an accepting state, if so trim follow state to remove back edges and cyclic anchors e.g. (^$)*+ // if we follow an anchor into an accepting state, then trim follow state while (q != end && !q->accept()) ++q; if (q != end) { q = follow.begin();- if (p.anchor())- {- while (q != follow.end())- {- // erase if not accepting and not a begin anchor and not a ) lookahead tail- if (!q->accept() && !q->anchor() && at(q->loc()) != ')')- q = follow.erase(q);- else- ++q;- }- }- else+ while (q != follow.end()) {- Location loc = p.loc();- while (q != follow.end())- {- // erase if not accepting and not a begin anchor and back edge- if (!q->accept() && !q->anchor() && q->loc() <= loc)- q = follow.erase(q);- else- ++q;- }+ // erase if not accepting and not a begin anchor and not a ) lookahead tail+ if (!q->accept() && !q->anchor() && at(q->loc()) != ')')+ q = follow.erase(q);+ else+ ++q; } } #ifdef DEBUG@@ -2397,22 +2464,21 @@ void Pattern::compile_transition( case '.': if (is_modified(ModConst::s, modifiers, loc)) {- static const uint64_t dot[5] = { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0ULL };+ static const uint64_t dot[5] = { 0xffffffffffffffffULL, 0xffffffffffffffffULL, 0xffffffffffffffffULL, 0xffffffffffffffffULL, 0ULL }; chars |= Chars(dot); } else {- static const uint64_t dot[5] = { 0xFFFFFFFFFFFFFBFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0ULL };+ static const uint64_t dot[5] = { 0xfffffffffffffbffULL, 0xffffffffffffffffULL, 0xffffffffffffffffULL, 0xffffffffffffffffULL, 0ULL }; chars |= Chars(dot); } break; case '^': chars.add(is_modified(ModConst::m, modifiers, loc) ? META_BOL : META_BOB);- trim_anchors(follow, *k);+ trim_anchors(follow); break; case '$': chars.add(is_modified(ModConst::m, modifiers, loc) ? META_EOL : META_EOB);- trim_anchors(follow, *k); break; default: if (c == '[')@@ -2445,27 +2511,22 @@ void Pattern::compile_transition( break; case 'A': chars.add(META_BOB);- trim_anchors(follow, *k);+ trim_anchors(follow); break; case 'z': chars.add(META_EOB);- trim_anchors(follow, *k); break; case 'B': chars.add(k->anchor() ? META_NWB : META_NWE);- trim_anchors(follow, *k); break; case 'b': chars.add(k->anchor() ? META_WBB : META_WBE);- trim_anchors(follow, *k); break; case '<': chars.add(k->anchor() ? META_BWB : META_BWE);- trim_anchors(follow, *k); break; case '>': chars.add(k->anchor() ? META_EWB : META_EWE);- trim_anchors(follow, *k); break; default: c = parse_esc(loc, &chars);@@ -2638,20 +2699,20 @@ void Pattern::posix(size_t index, Chars& chars) const { DBGLOG("posix(%lu)", index); static const uint64_t posix_chars[14][5] = {- { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0ULL, 0ULL, 0ULL }, // ASCII- { 0x0000000100003E00ULL, 0x0000000000000000ULL, 0ULL, 0ULL, 0ULL }, // Space: \t-\r, ' '- { 0x03FF000000000000ULL, 0x0000007E0000007EULL, 0ULL, 0ULL, 0ULL }, // XDigit: 0-9, A-F, a-f- { 0x00000000FFFFFFFFULL, 0x8000000000000000ULL, 0ULL, 0ULL, 0ULL }, // Cntrl: \x00-0x1F, \0x7F- { 0xFFFFFFFF00000000ULL, 0x7FFFFFFFFFFFFFFFULL, 0ULL, 0ULL, 0ULL }, // Print: ' '-'~'- { 0x03FF000000000000ULL, 0x07FFFFFE07FFFFFEULL, 0ULL, 0ULL, 0ULL }, // Alnum: 0-9, A-Z, a-z- { 0x0000000000000000ULL, 0x07FFFFFE07FFFFFEULL, 0ULL, 0ULL, 0ULL }, // Alpha: A-Z, a-z+ { 0xffffffffffffffffULL, 0xffffffffffffffffULL, 0ULL, 0ULL, 0ULL }, // ASCII+ { 0x0000000100003e00ULL, 0x0000000000000000ULL, 0ULL, 0ULL, 0ULL }, // Space: \t-\r, ' '+ { 0x03ff000000000000ULL, 0x0000007e0000007eULL, 0ULL, 0ULL, 0ULL }, // XDigit: 0-9, A-F, a-f+ { 0x00000000ffffffffULL, 0x8000000000000000ULL, 0ULL, 0ULL, 0ULL }, // Cntrl: \x00-0x1f, \0x7f+ { 0xffffffff00000000ULL, 0x7fffffffffffffffULL, 0ULL, 0ULL, 0ULL }, // Print: ' '-'~'+ { 0x03ff000000000000ULL, 0x07fffffe07fffffeULL, 0ULL, 0ULL, 0ULL }, // Alnum: 0-9, A-Z, a-z+ { 0x0000000000000000ULL, 0x07fffffe07fffffeULL, 0ULL, 0ULL, 0ULL }, // Alpha: A-Z, a-z { 0x0000000100000200ULL, 0x0000000000000000ULL, 0ULL, 0ULL, 0ULL }, // Blank: \t, ' '- { 0x03FF000000000000ULL, 0x0000000000000000ULL, 0ULL, 0ULL, 0ULL }, // Digit: 0-9- { 0xFFFFFFFE00000000ULL, 0x7FFFFFFFFFFFFFFFULL, 0ULL, 0ULL, 0ULL }, // Graph: '!'-'~'- { 0x0000000000000000ULL, 0x07FFFFFE00000000ULL, 0ULL, 0ULL, 0ULL }, // Lower: a-z- { 0xFC00FFFE00000000ULL, 0x78000001F8000001ULL, 0ULL, 0ULL, 0ULL }, // Punct: '!'-'/', ':'-'@', '['-'`', '{'-'~'- { 0x0000000000000000ULL, 0x0000000007FFFFFEULL, 0ULL, 0ULL, 0ULL }, // Upper: A-Z- { 0x03FF000000000000ULL, 0x07FFFFFE87FFFFFEULL, 0ULL, 0ULL, 0ULL }, // Word: 0-9, A-Z, a-z, _+ { 0x03ff000000000000ULL, 0x0000000000000000ULL, 0ULL, 0ULL, 0ULL }, // Digit: 0-9+ { 0xfffffffe00000000ULL, 0x7fffffffffffffffULL, 0ULL, 0ULL, 0ULL }, // Graph: '!'-'~'+ { 0x0000000000000000ULL, 0x07fffffe00000000ULL, 0ULL, 0ULL, 0ULL }, // Lower: a-z+ { 0xfc00fffe00000000ULL, 0x78000001f8000001ULL, 0ULL, 0ULL, 0ULL }, // Punct: '!'-'/', ':'-'@', '['-'`', '{'-'~'+ { 0x0000000000000000ULL, 0x0000000007fffffeULL, 0ULL, 0ULL, 0ULL }, // Upper: A-Z+ { 0x03ff000000000000ULL, 0x07fffffe87fffffeULL, 0ULL, 0ULL, 0ULL }, // Word: 0-9, A-Z, a-z, _ }; chars |= Chars(posix_chars[index]); }@@ -2693,7 +2754,7 @@ void Pattern::compact_dfa(DFA::State *start) for (DFA::State::Edges::iterator i = state->edges.begin(); i != state->edges.end(); ++i) { Char hi = i->second.first;- if (hi >= 0xFF)+ if (hi >= 0xff) break; DFA::State::Edges::iterator j = i; ++j;@@ -2764,13 +2825,13 @@ void Pattern::encode_dfa(DFA::State *start) nop_ += i->second.first - lo; } // add final dead state (HALT opcode) only when needed, i.e. skip dead state if all chars 0-255 are already covered- if (hi <= 0xFF)+ if (hi <= 0xff) {- state->edges[hi] = DFA::State::Edge(0xFF, static_cast<DFA::State*>(NULL)); // cast to appease MSVC 2010+ state->edges[hi] = DFA::State::Edge(0xff, static_cast<DFA::State*>(NULL)); // cast to appease MSVC 2010 ++nop_; } #else- Char lo = 0xFF;+ Char lo = 0xff; bool covered = false; for (DFA::State::Edges::const_reverse_iterator i = state->edges.rbegin(); i != state->edges.rend(); ++i) {@@ -2830,7 +2891,7 @@ void Pattern::encode_dfa(DFA::State *start) } } #else- Char lo = 0xFF;+ Char lo = 0xff; for (DFA::State::Edges::const_reverse_iterator i = state->edges.rbegin(); i != state->edges.rend(); ++i) { Char hi = i->first;@@ -3132,7 +3193,7 @@ void Pattern::gencode_dfa(const DFA::State *start) const print_char(file, lo); ::fprintf(file, ")"); }- else if (hi == 0xFF)+ else if (hi == 0xff) { ::fprintf(file, " if ("); print_char(file, lo);@@ -3224,7 +3285,7 @@ void Pattern::gencode_dfa(const DFA::State *start) const print_char(file, lo); ::fprintf(file, ")"); }- else if (hi == 0xFF)+ else if (hi == 0xff) { ::fprintf(file, " if ("); print_char(file, lo);@@ -3378,7 +3439,7 @@ void Pattern::gencode_dfa_closure(FILE *file, const DFA::State *state, int nest, print_char(file, lo); ::fprintf(file, ")"); }- else if (hi == 0xFF)+ else if (hi == 0xff) { ::fprintf(file, "if ("); print_char(file, lo);@@ -3426,7 +3487,7 @@ void Pattern::gencode_dfa_closure(FILE *file, const DFA::State *state, int nest, print_char(file, lo); ::fprintf(file, ")"); }- else if (hi == 0xFF)+ else if (hi == 0xff) { ::fprintf(file, "if ("); print_char(file, lo);@@ -3760,6 +3821,7 @@ void Pattern::analyze_dfa(DFA::State *start) bool cut_backedge = false; // if we cound a backedge for the current cut uint16_t cut_depth = 0; // breadth-first search depth of the current cut uint16_t cut_fin_depth = 0; // shortest distance to a final state for the current cut+ uint16_t cut_fin_count = 0; // number of characters to the final states uint16_t cut_span = 0; // length of the current cut, from the cut to the last state searched uint16_t cut_count = 0xffff; // number of characters at the start of the current cut uint16_t min_count = 0xffff; // min count of characters over the span of the current cut@@ -3772,6 +3834,7 @@ void Pattern::analyze_dfa(DFA::State *start) bool best_cut_backedge = false; uint16_t best_cut_depth = 0; uint16_t best_cut_fin_depth = 0xffff;+ uint16_t best_cut_fin_count = 0; uint16_t best_cut_span = 0; uint16_t best_cut_count = 0xffff; uint16_t best_min_count = 0xffff;@@ -3792,22 +3855,19 @@ void Pattern::analyze_dfa(DFA::State *start) for (std::set<DFA::State*>::iterator it = states.begin(); it != states.end(); ++it) { DFA::State *state = *it;- DFA::State::Edges::iterator edge, end = state->edges.end();- for (edge = state->edges.begin(); edge != end; ++edge)+ for (DFA::MetaEdgesClosure edge(state); !edge.done(); ++edge) {- DFA::State *next_state = edge->second.second;- if (next_state == NULL)- continue;- Char lo = edge->first;- Char hi = edge->second.first;- if (depth == 0 && !is_meta(lo))+ DFA::State *next_state = edge.state();+ Char lo = edge.lo();+ Char hi = edge.hi();+ if (depth == 0) for (Char ch = lo; ch <= hi; ++ch) fst_.set(ch);- if ((lo <= '\n' && hi >= '\n') || next_state->accept > 0 || next_state->edges.empty() || is_meta(lo) || is_meta(next_state->edges.rbegin()->first))+ if ((lo <= '\n' && hi >= '\n') || edge.next_accepting()) { // reset the next state BFS depth to zero, to prevent edges to next states to be marked as backedges next_state->first = lo <= '\n' && hi >= '\n' ? DFA::KEEP_PATH : 0;- // separate states that reach a final state or a state with a meta edge+ // separate states that reach a final state fin_states.insert(state); // depth if (fin_depth == 0xffff)@@ -3816,7 +3876,7 @@ void Pattern::analyze_dfa(DFA::State *start) fin_count += hi - lo + 1; continue; }- if (next_state->first == 0 || next_state->first > cut_depth + 1U)+ if (next_state->first == 0 || next_state->first > cut_depth + 1) next_chars.insert(lo, hi); if (next_state->first == 0) {@@ -3825,7 +3885,8 @@ void Pattern::analyze_dfa(DFA::State *start) else if (next_state->first <= state->first) { chars.insert(lo, hi);- if (next_state->first > cut_depth + 1U) // has a backedge to a state after the new cut?+ // has a backedge to a state after the new cut?+ if (cut_depth == 0 || next_state->first > cut_depth + 1) has_backedge = true; backedge = true; // has a backedge to a previous state continue;@@ -3838,32 +3899,34 @@ void Pattern::analyze_dfa(DFA::State *start) for (Char ch = range->first; ch < range->second; ++ch) max_freq = std::max(max_freq, frequency(static_cast<uint8_t>(ch))); uint16_t prev_min_count = min_count;- if (count + fin_count > max_count)- max_count = count + fin_count;+ if (count > max_count)+ max_count = count; if (count + fin_count < min_count) min_count = count + fin_count; if (is_more) cut_span = depth - cut_depth;- DBGLOGN("depth %hu has-backedge=%d cut-len=%hu count=%zu fin-count=%hu min-count=%hu max-count=%hu max-freq=%hu", depth, has_backedge, cut_span, count, fin_count, min_count, max_count, max_freq);+ DBGLOGN("depth %hu backedge=%d has-backedge=%d cut-span=%hu count=%hu cut-count=%hu fin-count=%hu min-count=%hu max-count=%hu max-freq=%hu", depth, backedge, has_backedge, cut_span, count, cut_count, fin_count, min_count, max_count, max_freq); if (searching) { // make a cut? bool make_cut = false; if (has_backedge)- make_cut = (max_count > 4 || max_freq > 251);+ make_cut = (max_count > fin_count + 4 || max_freq > 251 || 2 * count < max_count);+ else if (fin_count == 0)+ make_cut = (cut_span > 6 && prev_min_count < 0xffff && prev_min_count > 8 && prev_min_count >= min_count); else- make_cut = (cut_span >= 3 && prev_min_count < 0xffff && prev_min_count > 8 && prev_min_count >= 2 * min_count);+ make_cut = (cut_span > 7 && prev_min_count < 0xffff && prev_min_count > 8 && min_count <= 2); if (make_cut) { // determine if this is a better cut than the last- bool better = false;+ bool better; if (cut_span <= 2) better = (cut_span > best_cut_span); else better = (best_min_count >= prev_min_count && cut_span >= best_cut_span); if (better) {- DBGLOGN("new improved cut-depth=%hu %hu/%hu %hu/%hu %hu/%hu", cut_depth, cut_span, best_cut_span, min_count, best_min_count, cut_count, best_cut_count);+ DBGLOGN("new cut depth=%hu span=%hu/%hu min-count=%hu/%hu count=%hu/%hu", cut_depth, cut_span, best_cut_span, min_count, best_min_count, cut_count, best_cut_count); best_cut_states = cut_states; best_cut_fin_states = cut_fin_states; best_cut_count = cut_count;@@ -3871,19 +3934,13 @@ void Pattern::analyze_dfa(DFA::State *start) best_cut_backedge = cut_backedge; best_cut_depth = cut_depth; best_cut_fin_depth = cut_fin_depth;+ best_cut_fin_count = cut_fin_count; best_cut_span = cut_span; best_min_count = prev_min_count; searching = false; } } }- // are we done?- if (count <= fin_count || !is_more)- {- if (is_more)- ++cut_span;- break;- } if (!searching) { if (depth > 0)@@ -3893,18 +3950,16 @@ void Pattern::analyze_dfa(DFA::State *start) for (std::set<DFA::State*>::iterator it = states.begin(); it != states.end(); ++it) { DFA::State *state = *it;- DFA::State::Edges::iterator edge, end = state->edges.end();- for (edge = state->edges.begin(); edge != end; ++edge)+ for (DFA::MetaEdgesClosure edge(state); !edge.done(); ++edge) {- DFA::State *next_state = edge->second.second;- if (next_state == NULL)- continue;- Char lo = edge->first;- Char hi = edge->second.first;- if ((lo <= '\n' && hi >= '\n') || next_state->accept > 0 || next_state->edges.empty() || is_meta(lo) || is_meta(next_state->edges.rbegin()->first))- continue;- if (next_state->first == 0 || next_state->first > depth + 1U)- next_chars.insert(lo, hi);+ Char lo = edge.lo();+ Char hi = edge.hi();+ if ((lo > '\n' || hi < '\n') && !edge.next_accepting())+ {+ DFA::State *next_state = edge.state();+ if (next_state->first == 0 || next_state->first > depth + 1)+ next_chars.insert(lo, hi);+ } } } count = static_cast<uint16_t>(next_chars.count()); // never more than 256@@ -3917,38 +3972,54 @@ void Pattern::analyze_dfa(DFA::State *start) cut_backedge = backedge; cut_depth = depth; cut_fin_depth = fin_depth == 0xffff ? depth : fin_depth;+ cut_fin_count = fin_count; // prepare to find another cut chars.clear(); has_backedge = false; max_freq = 0; max_count = count;- min_count = count;+ min_count = cut_count; searching = true; } chars += next_chars; states.swap(next_states);+ // are we done?+ if (count <= fin_count || !is_more)+ {+ if (is_more)+ ++cut_span;+ break;+ } } // did we find more than one cut? if (best_cut_depth > 0 || best_cut_backedge || best_cut_span > 0) { // if the current cut is not a better cut, then use the last best cut bool better = false;- if (best_cut_count > cut_count || (best_cut_span == 1 && best_cut_count == cut_count))+ if ((best_cut_span == 1 ||+ (!cut_backedge && min_count < best_min_count) ||+ best_cut_fin_count == cut_fin_count) &&+ cut_count <= best_cut_count &&+ min_count <= best_min_count) {- if (cut_span > best_cut_span)- better = true;+ if (cut_span == 2 && fin_count > cut_count)+ // regex like [a-z]+-[a-z]+ and r[a-z]*st are OK to cut but r[a-z]*s. is not+ better = (min_count < best_min_count);+ else if (cut_span > best_cut_span)+ // regex like r[a-z]*st are OK to cut but r[a-z]*s is not+ better = (cut_fin_count == 0 || min_count < best_min_count); else if (cut_span >= 2 || cut_span == best_cut_span)- better = (best_min_count > min_count);+ better = (min_count < best_min_count); } if (better) { // the current cut is best- DBGLOGN("cut: %hu/%hu %hu/%hu %hu/%hu", cut_span, best_cut_span, cut_count, best_cut_count, min_count, best_min_count);+ DBGLOGN("cut: depth=%hu/%hu span=%hu/%hu count=%hu/%hu min-count=%hu/%hu", cut_depth, best_cut_depth, cut_span, best_cut_span, cut_count, best_cut_count, min_count, best_min_count); } else {- // the last best cut is best- DBGLOGN("best: %hu/%hu %hu/%hu %hu/%hu", cut_span, best_cut_span, cut_count, best_cut_count, min_count, best_min_count);+ // the last best cut was best+ DBGLOGN("best: depth=%hu/%hu span=%hu/%hu count=%hu/%hu min-count=%hu/%hu", cut_depth, best_cut_depth, cut_span, best_cut_span, cut_count, best_cut_count, min_count, best_min_count); cut_states = best_cut_states; cut_fin_states = best_cut_fin_states; cut_count = best_cut_count;@@ -3956,13 +4027,14 @@ void Pattern::analyze_dfa(DFA::State *start) cut_backedge = best_cut_backedge; cut_depth = best_cut_depth; cut_fin_depth = best_cut_fin_depth;+ cut_fin_count = best_cut_fin_count; } } // did we find a suitable cut? if (cut_depth > 0 || cut_backedge) { cut_ = cut_depth + 1;- std::set<DFA::State*> sweep[HFA::MAX_DEPTH];+ std::set<DFA::State*> sweep[8]; // sweep depth 8 is max of min_ (or 16 if HFA uses cuts, but it does not) // include final states in the cut states cut_states.insert(cut_fin_states.begin(), cut_fin_states.end()); // new start states@@ -3972,8 +4044,8 @@ void Pattern::analyze_dfa(DFA::State *start) DFA::State *state = *it; start = dfa_.state(); start->first = 1;- DFA::State::Edges::iterator end = state->edges.end(); // add edges to the new start state, ignore backedges to states <= cut+ DFA::State::Edges::iterator end = state->edges.end(); for (DFA::State::Edges::iterator edge = state->edges.begin(); edge != end; ++edge) { DFA::State *next_state = edge->second.second;@@ -3988,7 +4060,7 @@ void Pattern::analyze_dfa(DFA::State *start) if (!start->edges.empty()) start_states.insert(start); }- // sweep forward over states up to 8 levels (max bitap length) or 16 levels (HFA::MAX_DEPTH) to mark states+ // sweep forward over states up to 8 levels, the max of min_ (or 16 if HFA uses cuts, but it does not) size_t depth; for (depth = 0; depth < 7 && !sweep[depth].empty(); ++depth) {@@ -3996,18 +4068,18 @@ void Pattern::analyze_dfa(DFA::State *start) for (std::set<DFA::State*>::iterator it = sweep[depth].begin(); it != fin; ++it) { DFA::State *state = *it;- if (state->accept > 0 || state->edges.empty() || is_meta(state->edges.rbegin()->first))+ DFA::MetaEdgesClosure check_edge(state);+ while (!check_edge.done())+ ++check_edge;+ if (check_edge.accepting()) continue; // add edges from the new start state, ignore backedges to states <= cut bool can = false, any = false;- DFA::State::Edges::iterator end = state->edges.end();- for (DFA::State::Edges::iterator edge = state->edges.begin(); edge != end; ++edge)+ for (DFA::MetaEdgesClosure edge(state); !edge.done(); ++edge) {- DFA::State *next_state = edge->second.second;- if (next_state == NULL)- continue;- Char lo = edge->first;- Char hi = edge->second.first;+ DFA::State *next_state = edge.state();+ Char lo = edge.lo();+ Char hi = edge.hi(); if ((lo <= '\n' && hi >= '\n') || state->first == DFA::KEEP_PATH) { any = true;@@ -4035,6 +4107,7 @@ void Pattern::analyze_dfa(DFA::State *start) state->first = any ? DFA::LOOP_PATH : DFA::DEAD_PATH; } }+ DBGLOGN("max depth=%zu remaining after cut=%u", depth - 1, cut_); // sweep backward to mark states loopy or dead when all out paths lead to a dead state for (; depth > 0; --depth) {@@ -4042,17 +4115,19 @@ void Pattern::analyze_dfa(DFA::State *start) for (std::set<DFA::State*>::iterator it = sweep[depth - 1].begin(); it != fin; ++it) { DFA::State *state = *it;- if (state->first == DFA::KEEP_PATH || state->accept > 0 || state->edges.empty() || is_meta(state->edges.rbegin()->first))+ if (state->first == DFA::KEEP_PATH)+ continue;+ DFA::MetaEdgesClosure check_edge(state);+ while (!check_edge.done())+ ++check_edge;+ if (check_edge.accepting()) continue; bool all = true;- DFA::State::Edges::iterator end = state->edges.end();- for (DFA::State::Edges::iterator edge = state->edges.begin(); edge != end; ++edge)+ for (DFA::MetaEdgesClosure edge(state); !edge.done(); ++edge) {- DFA::State *next_state = edge->second.second;- if (next_state == NULL)- continue;- Char lo = edge->first;- Char hi = edge->second.first;+ DFA::State *next_state = edge.state();+ Char lo = edge.lo();+ Char hi = edge.hi(); if (next_state->first == DFA::DEAD_PATH) { cut_chars.insert(lo, hi);@@ -4081,30 +4156,29 @@ void Pattern::analyze_dfa(DFA::State *start) { bool all = true; DFA::State *state = *it;- DFA::State::Edges::iterator end = state->edges.end();- for (DFA::State::Edges::iterator edge = state->edges.begin(); edge != end; ++edge)+ for (DFA::MetaEdgesClosure edge(state); !edge.done(); ++edge) {- DFA::State *next_state = edge->second.second;- if (next_state == NULL)- continue;+ DFA::State *next_state = edge.state();+ Char lo = edge.lo();+ Char hi = edge.hi(); if (next_state->first == DFA::DEAD_PATH) {- cut_chars.insert(edge->first, edge->second.first);+ cut_chars.insert(lo, hi); } else if (next_state->first == DFA::LOOP_PATH) { all = false; // not all are marked dead- cut_chars.insert(edge->first, edge->second.first);- next_chars.insert(edge->first, edge->second.first);+ cut_chars.insert(lo, hi);+ next_chars.insert(lo, hi); } else { all = false; // not all are marked dead- next_chars.insert(edge->first, edge->second.first);+ next_chars.insert(lo, hi); } #ifdef DEBUG if (next_state->first != DFA::DEAD_PATH)- DBGLOGN("%u: %d..%d -> %u", state->first, edge->first, edge->second.first, next_state->first);+ DBGLOGN("%u: %d..%d -> %u", state->first, lo, hi, next_state->first); #endif } if (all)@@ -4152,14 +4226,21 @@ void Pattern::analyze_dfa(DFA::State *start) break; } Char lo = state->edges.begin()->first;- if (!is_meta(lo) && lo == state->edges.begin()->second.first)+ if (lo == state->edges.begin()->second.first) {- if (len_ >= 255)+ if (!is_meta(lo))+ {+ if (len_ >= 255)+ {+ one_ = false;+ break;+ }+ chr_[len_++] = static_cast<uint8_t>(lo);+ }+ else { one_ = false;- break; }- chr_[len_++] = static_cast<uint8_t>(lo); } else {@@ -4174,22 +4255,32 @@ void Pattern::analyze_dfa(DFA::State *start) } state = next; }+#if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2) || defined(HAVE_NEON)+ // do not allow len_ == 1 unless we're accepting, use needles or bitap+ if (len_ == 1 && state->accept == 0 && !state->edges.empty())+ {+ len_ = 0;+ one_ = false;+ state = start;+ }+#endif if (state != NULL && ((state->accept > 0 && !state->edges.empty()) || state->redo)) one_ = false; if (state != NULL && (len_ == 0 || state->accept == 0)) start_states.insert(state); } min_ = 0;- std::memset(bit_, 0xFF, sizeof(bit_));- std::memset(pmh_, 0xFF, sizeof(pmh_));- std::memset(pma_, 0xFF, sizeof(pma_));+ std::memset(bit_, 0xff, sizeof(bit_));+ std::memset(tap_, 0xff, sizeof(tap_));+ std::memset(pmh_, 0xff, sizeof(pmh_));+ std::memset(pma_, 0xff, sizeof(pma_)); if (!start_states.empty()) { gen_predict_match(start_states); #ifdef DEBUG for (Char i = 0; i < 256; ++i) {- if (bit_[i] != 0xFF)+ if (bit_[i] != 0xff) { if (isprint(i)) DBGLOGN("bit['%c'] = %02x", i, bit_[i]);@@ -4199,7 +4290,7 @@ void Pattern::analyze_dfa(DFA::State *start) } for (Hash i = 0; i < Const::HASH; ++i) {- if (pmh_[i] != 0xFF)+ if (pmh_[i] != 0xff) { if (isprint(pmh_[i])) DBGLOGN("pmh['%c'] = %02x", i, pmh_[i]);@@ -4209,7 +4300,7 @@ void Pattern::analyze_dfa(DFA::State *start) } for (Hash i = 0; i < Const::HASH; ++i) {- if (pma_[i] != 0xFF)+ if (pma_[i] != 0xff) { if (isprint(pma_[i])) DBGLOGN("pma['%c'] = %02x", i, pma_[i]);@@ -4219,7 +4310,7 @@ void Pattern::analyze_dfa(DFA::State *start) } #endif }- DBGLOG("min = %zu len = %zu", min_, len_);+ DBGLOG("min=%zu len=%zu", min_, len_); DBGLOG("END Pattern::analyze_dfa()"); } @@ -4227,110 +4318,70 @@ void Pattern::gen_min(std::set<DFA::State*>& states) { // find min between 0 and 8 min_ = 8;- std::set<DFA::State*> next;- gen_min_start(states, next);- for (size_t level = 1; level < min_; ++level)- gen_min_transitions(level, next);-}--void Pattern::gen_min_start(std::set<DFA::State*>& states, std::set<DFA::State*>& next)-{- bool empty = true;- for (std::set<DFA::State*>::iterator it = states.begin(); it != states.end(); ++it)+ std::set<DFA::State*> prev, next(states);+ for (size_t level = 0; level < min_; ++level) {- DFA::State *state = *it;- if (empty && !state->edges.empty())- empty = false;- for (DFA::State::Edges::iterator edge = state->edges.begin(); edge != state->edges.end(); ++edge)+ bool none = true;+ prev.clear();+ prev.swap(next);+ for (std::set<DFA::State*>::iterator from = prev.begin(); from != prev.end(); ++from) {- Char lo = edge->first;- if (is_meta(lo))+ DFA::MetaEdgesClosure edge(*from);+ for (; !edge.done() && !edge.accepting(); ++edge) {- min_ = 0;- return;- }- DFA::State *next_state = edge->second.second;- // ignore edges from a state to a state with breadth-first depth <= cut- if (next_state != NULL && lbk_ > 0)- if (next_state->first > 0 && next_state->first <= cut_)+ DFA::State *next_state = edge.state();+ // ignore edges from a state to a state with breadth-first depth <= cut+ if (lbk_ > 0 && next_state->first > 0 && next_state->first <= cut_) continue;- // don't visit next state if it is accepting or when any edges from it are meta- if (next_state != NULL && (next_state->accept > 0 || next_state->edges.empty() || is_meta(next_state->edges.rbegin()->first)))- next_state = NULL;- if (next_state != NULL)- next.insert(next_state);- else- min_ = 1;- }- }- if (empty)- min_ = 0;-}--void Pattern::gen_min_transitions(size_t level, std::set<DFA::State*>& next)-{- std::set<DFA::State*> prev;- prev.swap(next);- for (std::set<DFA::State*>::iterator from = prev.begin(); from != prev.end(); ++from)- {- DFA::State *state = *from;- for (DFA::State::Edges::iterator edge = state->edges.begin(); edge != state->edges.end(); ++edge)- {- Char lo = edge->first;- if (is_meta(lo))+ none = false;+ if (min_ == level + 1)+ continue;+ if (edge.next_accepting())+ min_ = level + 1;+ else+ next.insert(next_state);+ }+ // is this state accepting through one or more meta edges in the closure?+ if (edge.accepting()) {- min_ = level;- return;+ none = true;+ break; }- DFA::State *next_state = level < 7 ? edge->second.second : NULL;- // ignore edges from a state to a state with breadth-first depth <= cut- if (next_state != NULL && lbk_ > 0)- if (next_state->first > 0 && next_state->first <= cut_)- continue;- // don't visit next state if it is accepting or when any edges from it are meta- if (next_state != NULL && (next_state->accept > 0 || next_state->edges.empty() || is_meta(next_state->edges.rbegin()->first)))- next_state = NULL;- if (next_state != NULL)- next.insert(next_state);- else if (min_ > level)- min_ = level + 1; }+ if (none)+ min_ = level; } } void Pattern::gen_predict_match(std::set<DFA::State*>& states) {- // find min between 0 and 8 then populate bitap and PM hashes (bounded by min)+ // find min between 0 and 8 then populate bitap and hashes (bounded by min) gen_min(states);- std::map<DFA::State*,ORanges<Hash> > hashes[8];+ std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > > hashes[8]; gen_predict_match_start(states, hashes[0]);- for (size_t level = 1; level < std::max<size_t>(min_, 4); ++level)- for (std::map<DFA::State*,ORanges<Hash> >::iterator from = hashes[level - 1].begin(); from != hashes[level - 1].end(); ++from)+ for (size_t level = 1; level < std::max<size_t>(min_, 4) && !hashes[level - 1].empty(); ++level)+ for (std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >::iterator from = hashes[level - 1].begin(); from != hashes[level - 1].end(); ++from) gen_predict_match_transitions(level, from->first, from->second, hashes[level]); } -void Pattern::gen_predict_match_start(std::set<DFA::State*>& states, std::map<DFA::State*,ORanges<Hash> >& hashes)+void Pattern::gen_predict_match_start(std::set<DFA::State*>& states, std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >& first_hashes) { for (std::set<DFA::State*>::iterator it = states.begin(); it != states.end(); ++it) {- DFA::State *state = *it; // state at level 0- for (DFA::State::Edges::iterator edge = state->edges.begin(); edge != state->edges.end(); ++edge)+ DFA::State *state = *it;+ for (DFA::MetaEdgesClosure edge(state); !edge.done(); ++edge) {- Char lo = edge->first;- if (is_meta(lo))- break;- // next level state to visit- DFA::State *next_state = edge->second.second;- // ignore states before the cut, since we don't use them for bitap and PM hashing- if (next_state != NULL && lbk_ > 0)- if (next_state->first > 0 && next_state->first <= cut_)- continue;- bool accept = next_state == NULL || next_state->accept > 0 || is_meta(next_state->edges.rbegin()->first);- Char hi = edge->second.first;- if (next_state != NULL)- hashes[next_state].insert(lo, hi);- uint8_t mask = ~(1 << 6);- if (accept)+ DFA::State *next_state = edge.state();+ // ignore states before the cut, since we don't use them for bitap and hashing+ if (lbk_ > 0 && next_state->first > 0 && next_state->first <= cut_)+ continue;+ bool next_accept = edge.next_accepting();+ Char lo = edge.lo();+ Char hi = edge.hi();+ DBGLOG("PM start %p: %u~%u %s", state, lo, hi, next_accept ? "accept" : "");+ first_hashes[next_state].first.insert(lo, hi);+ Bitap mask = ~(1 << 6);+ if (next_accept) mask &= ~(1 << 7); for (Char ch = lo; ch <= hi; ++ch) {@@ -4338,45 +4389,112 @@ void Pattern::gen_predict_match_start(std::set<DFA::State*>& states, std::map<DF pmh_[ch] &= ~1; pma_[ch] &= mask; }+ // this is the last state to populate bitap+ if (min_ <= 1)+ {+ if (next_accept)+ {+ // last tap_[] when accepting is hashed with all 256 possible next characters+ DBGLOG("tap %u~%u as accepting", lo, hi);+ for (Char last_ch = lo; last_ch <= hi; ++last_ch)+ for (Char ch = (last_ch & ((1 << 6) - 1)); ch < Const::BTAP; ch += (1 << 6))+ tap_[ch] &= ~1;+ }+ else+ {+ // hash all characters on edges from this state, to improve prediction accuracy+ for (DFA::MetaEdgesClosure next_edge(next_state); !next_edge.done(); ++next_edge)+ {+ Char next_lo = next_edge.lo();+ Char next_hi = next_edge.hi();+ DBGLOG("tap %u~%u with %u~%u", lo, hi, next_lo, next_hi);+ for (Char next_ch = (next_lo << 6); next_ch <= (next_hi << 6); next_ch += (1 << 6))+ for (Char ch = lo; ch <= hi; ++ch)+ tap_[(ch ^ next_ch) & (Const::BTAP - 1)] &= ~1;+ }+ }+ } DBGLOG("0 bitap %u..%u -> %p", lo, hi, next_state); } }+ // ranges are the same characters for the start state+ for (std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >::iterator it = first_hashes.begin(); it != first_hashes.end(); ++it)+ it->second.second = it->second.first; } -void Pattern::gen_predict_match_transitions(size_t level, DFA::State *state, const ORanges<Hash>& previous, std::map<DFA::State*,ORanges<Hash> >& level_hashes)+void Pattern::gen_predict_match_transitions(size_t level, DFA::State *state, const std::pair<ORanges<Hash>,ORanges<Char> >& previous, std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > >& level_hashes) {- for (DFA::State::Edges::iterator edge = state->edges.begin(); edge != state->edges.end(); ++edge)+ for (DFA::MetaEdgesClosure edge(state); !edge.done(); ++edge) {- Char lo = edge->first;- if (is_meta(lo))- break;- // next level state to visit- DFA::State *next_state = edge->second.second;- // ignore states before the cut, since we don't use them for bitap and PM hashing- if (next_state != NULL && lbk_ > 0)- if (next_state->first > 0 && next_state->first <= cut_)- continue;- bool accept = next_state == NULL || next_state->accept > 0 || is_meta(next_state->edges.rbegin()->first);- ORanges<Hash> *next_hashes = next_state != NULL && level + 1 < std::max<size_t>(min_, 4) ? &level_hashes[next_state] : NULL;- Char hi = edge->second.first;+ DFA::State *next_state = edge.state();+ // ignore states before the cut, since we don't use them for bitap and hashing+ if (lbk_ > 0 && next_state->first > 0 && next_state->first <= cut_)+ continue;+ bool next_accept = edge.next_accepting();+ std::pair<ORanges<Hash>,ORanges<Char> > *next_hashes = level + 1 < std::max<size_t>(min_, 4) ? &level_hashes[next_state] : NULL;+ Char lo = edge.lo();+ Char hi = edge.hi();+ DBGLOG("PM level %zu %p: %u~%u %s%s", level, state, lo, hi, next_accept ? "accept " : "", next_hashes ? "nexthashes" : ""); if (level < min_) {- // populate bitap- uint8_t mask = ~(1 << level);+ // populate bit array+ Bitap mask = ~(1 << level); for (Char ch = lo; ch <= hi; ++ch) bit_[ch] &= mask; DBGLOG("%zu bitap %p: %u..%u -> %p", level, state, lo, hi, next_state);+ // update tap_[] bitap hashed pairs at previous level using previous character ranges+ mask >>= 1;+ for (ORanges<Char>::iterator prev_range = previous.second.begin(); prev_range != previous.second.end(); ++prev_range)+ {+ Char prev_lo = prev_range->first;+ Char prev_hi = prev_range->second;+ DBGLOG("tap %u~%u with %u~%u", prev_lo, prev_hi-1, lo, hi);+ for (Char ch = (lo << 6); ch <= (hi << 6); ch += (1 << 6))+ for (Char prev_ch = prev_lo; prev_ch < prev_hi; ++prev_ch)+ tap_[(prev_ch ^ ch) & (Const::BTAP - 1)] &= mask;+ }+ if (level + 1 < min_ && next_hashes != NULL)+ {+ // pass character range to the next state+ next_hashes->second.insert(lo, hi);+ }+ else+ {+ // this is the last state to populate bitap+ mask = ~(1 << level);+ if (next_accept)+ {+ // last tap_[] when accepting is hashed with all 256 possible next characters+ DBGLOG("tap %u~%u as accepting", lo, hi);+ for (Char last_ch = lo; last_ch <= hi; ++last_ch)+ for (Char ch = (last_ch & ((1 << 6) - 1)); ch < Const::BTAP; ch += (1 << 6))+ tap_[ch] &= mask;+ }+ else+ {+ // hash all characters on edges from this state, to improve prediction accuracy+ for (DFA::MetaEdgesClosure next_edge(next_state); !next_edge.done(); ++next_edge)+ {+ Char next_lo = next_edge.lo();+ Char next_hi = next_edge.hi();+ DBGLOG("tap %u~%u with %u~%u", lo, hi, next_lo, next_hi);+ for (Char next_ch = (next_lo << 6); next_ch <= (next_hi << 6); next_ch += (1 << 6))+ for (Char ch = lo; ch <= hi; ++ch)+ tap_[(ch ^ next_ch) & (Const::BTAP - 1)] &= mask;+ }+ }+ } } if (level < 4) {- // populate PM4+ // populate PM4 hashes for level 0 to 3 uint8_t pmh_mask = ~(1 << level); uint8_t pma_mask = ~(1 << (6 - 2 * level));- if (level == 3 || accept)+ if (level == 3 || next_accept) pma_mask &= ~(1 << (7 - 2 * level)); if (next_hashes != NULL) {- for (ORanges<Hash>::iterator prev_range = previous.begin(); prev_range != previous.end(); ++prev_range)+ for (ORanges<Hash>::iterator prev_range = previous.first.begin(); prev_range != previous.first.end(); ++prev_range) { Hash prev_lo = prev_range->first; Hash prev_hi = prev_range->second;@@ -4387,14 +4505,14 @@ void Pattern::gen_predict_match_transitions(size_t level, DFA::State *state, con Hash h = hash(prev, static_cast<uint8_t>(ch)); pmh_[h] &= pmh_mask; pma_[h] &= pma_mask;- next_hashes->insert(h);+ next_hashes->first.insert(h); } } } } else {- for (ORanges<Hash>::iterator prev_range = previous.begin(); prev_range != previous.end(); ++prev_range)+ for (ORanges<Hash>::iterator prev_range = previous.first.begin(); prev_range != previous.first.end(); ++prev_range) { Hash prev_lo = prev_range->first; Hash prev_hi = prev_range->second;@@ -4415,7 +4533,7 @@ void Pattern::gen_predict_match_transitions(size_t level, DFA::State *state, con uint8_t pmh_mask = ~(1 << level); if (next_hashes != NULL) {- for (ORanges<Hash>::iterator prev_range = previous.begin(); prev_range != previous.end(); ++prev_range)+ for (ORanges<Hash>::iterator prev_range = previous.first.begin(); prev_range != previous.first.end(); ++prev_range) { Hash prev_lo = prev_range->first; Hash prev_hi = prev_range->second;@@ -4425,14 +4543,14 @@ void Pattern::gen_predict_match_transitions(size_t level, DFA::State *state, con { Hash h = hash(prev, static_cast<uint8_t>(ch)); pmh_[h] &= pmh_mask;- next_hashes->insert(h);+ next_hashes->first.insert(h); } } } } else {- for (ORanges<Hash>::iterator prev_range = previous.begin(); prev_range != previous.end(); ++prev_range)+ for (ORanges<Hash>::iterator prev_range = previous.first.begin(); prev_range != previous.first.end(); ++prev_range) { Hash prev_lo = prev_range->first; Hash prev_hi = prev_range->second;@@ -4476,22 +4594,17 @@ void Pattern::gen_match_hfa(DFA::State *start) void Pattern::gen_match_hfa_start(DFA::State *start, HFA::State& index, HFA::StateHashes& hashes) {- if (start->accept == 0 && !start->edges.empty() && !is_meta(start->edges.rbegin()->first))+ if (start->accept == 0 && !start->edges.empty()) { start->index = index++;- for (DFA::State::Edges::const_iterator edge = start->edges.begin(); edge != start->edges.end(); ++edge)+ for (DFA::MetaEdgesClosure edge(start); !edge.done(); ++edge) {- DFA::State *next_state = edge->second.second;- if (next_state == NULL)- continue;- // ignore edges from a state to a state with breadth-first depth <= cut- if (lbk_ > 0 && next_state->first > 0 && next_state->first <= cut_)- continue;+ DFA::State *next_state = edge.state(); if (next_state->index == 0) next_state->index = index++; // cannot overflow max states if HFA::MAX_STATES >= 256 hfa_.states[start->index].insert(next_state->index);- Char lo = edge->first;- Char hi = edge->second.first;+ Char lo = edge.lo();+ Char hi = edge.hi(); DBGLOG("0 HFA %p: %u..%u -> %p", start, lo, hi, next_state); hashes[next_state][0].insert(lo, hi); }@@ -4500,17 +4613,13 @@ void Pattern::gen_match_hfa_start(DFA::State *start, HFA::State& index, HFA::Sta bool Pattern::gen_match_hfa_transitions(size_t level, size_t& max_level, DFA::State *state, const HFA::HashRanges& previous, HFA::State& index, HFA::StateHashes& hashes) {- if (state->accept > 0 || state->edges.empty() || is_meta(state->edges.rbegin()->first))+ DFA::MetaEdgesClosure edge(state);+ if (state->accept > 0 || state->edges.empty() || edge.next_accepting()) return true; size_t ranges = 0; // total number of hash ranges at this depth level from the DFA/HFA start state- for (DFA::State::Edges::const_iterator edge = state->edges.begin(); edge != state->edges.end(); ++edge)+ for (; !edge.done(); ++edge) {- DFA::State *next_state = edge->second.second;- if (next_state == NULL)- continue;- // ignore edges from a state to a state with breadth-first depth <= cut- if (lbk_ > 0 && next_state->first > 0 && next_state->first <= cut_)- continue;+ DFA::State *next_state = edge.state(); if (next_state->index == 0) { if (index >= HFA::MAX_STATES)@@ -4523,8 +4632,8 @@ bool Pattern::gen_match_hfa_transitions(size_t level, size_t& max_level, DFA::St next_state->index = index++; // enumerate the next state } hfa_.states[state->index].insert(next_state->index);- Char lo = edge->first;- Char hi = edge->second.first;+ Char lo = edge.lo();+ Char hi = edge.hi(); DBGLOG("%zu HFA %p: %u..%u -> %p", level, state, lo, hi, next_state); for (size_t offset = std::max(HFA::MAX_CHAIN - 1, level) + 1 - HFA::MAX_CHAIN; offset < level; ++offset) {@@ -4635,53 +4744,59 @@ bool Pattern::match_hfa_transitions(size_t level, const HFA::Hashes& hashes, con return any; } +#ifndef WITH_NO_CODEGEN void Pattern::write_predictor(FILE *file) const {- ::fprintf(file, "extern const reflex::Pattern::Pred reflex_pred_%s[%zu] = {", opt_.n.empty() ? "FSM" : opt_.n.c_str(), 2 + len_ + (len_ == 0) * 256 + Const::HASH + (lbk_ > 0) * 68);- ::fprintf(file, "\n %3hhu,%3hhu,", static_cast<uint8_t>(len_), (static_cast<uint8_t>(min_ | (one_ << 4) | ((lbk_ > 0) << 5) | (bol_ << 6))));+ ::fprintf(file, "extern const reflex::Pattern::Pred reflex_pred_%s[%zu] = {", opt_.n.empty() ? "FSM" : opt_.n.c_str(), 2 + len_ + (len_ == 0) * (256 + Const::BTAP) + Const::HASH + (lbk_ > 0) * 68);+ ::fprintf(file, "\n %3hhu,%3hhu,", static_cast<uint8_t>(len_), (static_cast<uint8_t>(min_ | (one_ << 4) | ((lbk_ > 0) << 5) | (bol_ << 6) | 0x80))); // save match characters chr_[0..len_-1] for (size_t i = 0; i < len_; ++i)- ::fprintf(file, "%s%3hhu,", ((i + 2) & 0xF) ? "" : "\n ", static_cast<uint8_t>(chr_[i]));+ ::fprintf(file, "%s%3hhu,", ((i + 2) & 0xf) ? "" : "\n ", static_cast<uint8_t>(chr_[i])); if (len_ == 0) {- // save bitap bit_[] parameters- for (Char i = 0; i < 256; ++i)- ::fprintf(file, "%s%3hhu,", (i & 0xF) ? "" : "\n ", static_cast<uint8_t>(~bit_[i]));+ // save bit_[] parameters+ for (int i = 0; i < 256; ++i)+ ::fprintf(file, "%s%3hhu,", (i & 0xf) ? "" : "\n ", static_cast<uint8_t>(~bit_[i]));+ // save tap_[] parameters+ for (int i = 0; i < Const::BTAP; ++i)+ ::fprintf(file, "%s%3hhu,", (i & 0xf) ? "" : "\n ", static_cast<uint8_t>(~tap_[i])); } if (min_ < 4) { // save predict match PM4 pma_[] parameters- for (Hash i = 0; i < Const::HASH; ++i)- ::fprintf(file, "%s%3hhu,", (i & 0xF) ? "" : "\n ", static_cast<uint8_t>(~pma_[i]));+ for (int i = 0; i < Const::HASH; ++i)+ ::fprintf(file, "%s%3hhu,", (i & 0xf) ? "" : "\n ", static_cast<uint8_t>(~pma_[i])); } else { // save predict match hash pmh_[] parameters- for (Hash i = 0; i < Const::HASH; ++i)- ::fprintf(file, "%s%3hhu,", (i & 0xF) ? "" : "\n ", static_cast<uint8_t>(~pmh_[i]));+ for (int i = 0; i < Const::HASH; ++i)+ ::fprintf(file, "%s%3hhu,", (i & 0xf) ? "" : "\n ", static_cast<uint8_t>(~pmh_[i])); } if (lbk_ > 0) { // save lookback parameters lbk_ lbm_ cbk_[] after s-t cut and first s-t cut pattern characters fst_[] ::fprintf(file, "\n %3hhu,%3hhu,%3hhu,%3hhu,", static_cast<uint8_t>(lbk_ & 0xff), static_cast<uint8_t>(lbk_ >> 8), static_cast<uint8_t>(lbm_ & 0xff), static_cast<uint8_t>(lbm_ >> 8));- for (size_t i = 0; i < 256; i += 8)+ for (int i = 0; i < 256; i += 8) { uint8_t b = 0;- for (size_t j = 0; j < 8; ++j)+ for (int j = 0; j < 8; ++j) b |= cbk_.test(i + j) << j;- ::fprintf(file, "%s%3hhu,", (i & 0x7F) ? "" : "\n ", b);+ ::fprintf(file, "%s%3hhu,", (i & 0x7f) ? "" : "\n ", b); } for (size_t i = 0; i < 256; i += 8) { uint8_t b = 0;- for (size_t j = 0; j < 8; ++j)+ for (int j = 0; j < 8; ++j) b |= fst_.test(i + j) << j;- ::fprintf(file, "%s%3hhu,", (i & 0x7F) ? "" : "\n ", b);+ ::fprintf(file, "%s%3hhu,", (i & 0x7f) ? "" : "\n ", b); } } ::fprintf(file, "\n};\n\n"); }+#endif +#ifndef WITH_NO_CODEGEN void Pattern::write_namespace_open(FILE *file) const { if (opt_.z.empty())@@ -4696,7 +4811,9 @@ void Pattern::write_namespace_open(FILE *file) const } ::fprintf(file, "namespace %s {\n\n", s.substr(i).c_str()); }+#endif +#ifndef WITH_NO_CODEGEN void Pattern::write_namespace_close(FILE *file) const { if (opt_.z.empty())@@ -4711,5 +4828,6 @@ void Pattern::write_namespace_close(FILE *file) const } ::fprintf(file, "} // namespace %s\n\n", s.substr(i).c_str()); }+#endif } // namespace reflex
@@ -82,20 +82,31 @@ size_t nlcount(const char *s, const char *t) while ((reinterpret_cast<std::ptrdiff_t>(s) & 0x0f) != 0) n += (*s++ == '\n'); __m128i vlcn = _mm_set1_epi8('\n');+ __m128i v0 = _mm_setzero_si128(); while (s <= e) { __m128i vlcm1 = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s)); __m128i vlcm2 = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s + 16)); __m128i vlcm3 = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s + 32)); __m128i vlcm4 = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s + 48));- __m128i vlceq1 = _mm_cmpeq_epi8(vlcm1, vlcn);- __m128i vlceq2 = _mm_cmpeq_epi8(vlcm2, vlcn);- __m128i vlceq3 = _mm_cmpeq_epi8(vlcm3, vlcn);- __m128i vlceq4 = _mm_cmpeq_epi8(vlcm4, vlcn);- n += popcount(_mm_movemask_epi8(vlceq1))- + popcount(_mm_movemask_epi8(vlceq2))- + popcount(_mm_movemask_epi8(vlceq3))- + popcount(_mm_movemask_epi8(vlceq4));+ // take absolute value of comparisons to get 0 or 1 per byte+ __m128i vlceq1 = _mm_sub_epi8(v0, _mm_cmpeq_epi8(vlcm1, vlcn));+ __m128i vlceq2 = _mm_sub_epi8(v0, _mm_cmpeq_epi8(vlcm2, vlcn));+ __m128i vlceq3 = _mm_sub_epi8(v0, _mm_cmpeq_epi8(vlcm3, vlcn));+ __m128i vlceq4 = _mm_sub_epi8(v0, _mm_cmpeq_epi8(vlcm4, vlcn));+ // sum all up (we have a limited range 0..4 to sum to a total max 4x16=64 < 256)+ // more than two times faster than four popcounts over four movemasks for SSE2 (not for AVX2)+ __m128i vsum = _mm_add_epi8(_mm_add_epi8(vlceq1, vlceq2), _mm_add_epi8(vlceq3, vlceq4));+ uint16_t sum =+ _mm_extract_epi16(vsum, 0) ++ _mm_extract_epi16(vsum, 1) ++ _mm_extract_epi16(vsum, 2) ++ _mm_extract_epi16(vsum, 3) ++ _mm_extract_epi16(vsum, 4) ++ _mm_extract_epi16(vsum, 5) ++ _mm_extract_epi16(vsum, 6) ++ _mm_extract_epi16(vsum, 7);+ n += static_cast<uint8_t>(sum) + (sum >> 8); s += 64; } }@@ -119,8 +130,8 @@ size_t nlcount(const char *s, const char *t) #if defined(__aarch64__) n += vaddvq_s8(vqabsq_s8(vreinterpretq_s8_u8(vaddq_u8(vleq0, vaddq_u8(vleq1, vaddq_u8(vleq2, vleq3)))))); #else- // my horizontal sum method (we have a very limited range 0..4 to sum to a total max 4x16=64 < 256)- uint64x2_t vsum = vreinterpretq_u64_s8(vqabsq_s8(vreinterpretq_s8_u8(vaddq_u8(vleq0, vaddq_u8(vleq1, vaddq_u8(vleq2, vleq3))))));+ // my horizontal sum method (we have a limited range 0..4 to sum to a total max 4x16=64 < 256)+ uint64x2_t vsum = vreinterpretq_u64_s8(vqabsq_s8(vreinterpretq_s8_u8(vaddq_u8(vaddq_u8(vleq0, vleq1), vaddq_u8(vleq2, vleq3))))); uint64_t sum0 = vgetq_lane_u64(vsum, 0) + vgetq_lane_u64(vsum, 1); uint32_t sum1 = static_cast<uint32_t>(sum0) + (sum0 >> 32); uint16_t sum2 = static_cast<uint16_t>(sum1) + (sum1 >> 16);@@ -186,17 +197,17 @@ bool isutf8(const char *s, const char *e) } s += 16; }- // my UTF-8 validation method- // 224ms to check 1,000,000,000 bytes on a Intel quad core i7 2.9 GHz 16GB 2133 MHz LPDDR3+ // my UTF-8 check method+ // 204ms to check 1,000,000,000 bytes on a Intel quad core i7 2.9 GHz 16GB 2133 MHz LPDDR3 // // scalar code: // int8_t p = 0, q = 0, r = 0; // while (s < e) // { // int8_t c = static_cast<int8_t>(*s++);- // if (!(c > 0 || (c > -63 && c < -11)))+ // if (!(c > 0 || c < -64 || (c > -63 && c < -11))) // return false;- // if ((-(c < -64) ^ (p | q | r)) & 0x80)+ // if (((-(c > -63) ^ (p | q | r)) & 0x80) != 0x80) // return false; // r = (q & (q << 1)); // q = (p & (p << 1));@@ -212,20 +223,19 @@ bool isutf8(const char *s, const char *e) __m128i vr = v0; while (s <= e - 16) {- // step 1: check valid signed byte ranges+ // step 1: check valid signed byte ranges, including continuation bytes 0x80 to 0xbf // c = s[i]- // if (!(c > 0 || (c > -63 && c < -11)))+ // if (!(c > 0 || c < -64 || (c > -63 && c < -11))) // return false // __m128i vc = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s)); __m128i vt = _mm_and_si128(_mm_cmpgt_epi8(vc, vxc1), _mm_cmplt_epi8(vc, vxf5)); vt = _mm_or_si128(vt, _mm_cmplt_epi8(vc, vxc0)); vt = _mm_or_si128(vt, _mm_cmpgt_epi8(vc, v0));- if (_mm_movemask_epi8(vt) != 0xffff)- return false;+ __m128i vm = vt; // // step 2: check UTF-8 multi-byte sequences of 2, 3 and 4 bytes long- // if ((-(c < -64) ^ (p | q | r)) & 0x80)+ // if (((-(c > -63) ^ (p | q | r)) & 0x80) != 0x80) // return false // r = (q & (q << 1)) // q = (p & (p << 1))@@ -255,7 +265,7 @@ bool isutf8(const char *s, const char *e) // // SSE2 code to perform r = (q & (q << 1)); q = (p & (p << 1)); p = (c & (c << 1)); // shift parts of the old vp, vq, vr and new vp, vq, vr in vt using psrldq and por- // then check if ((-(c < -64) ^ (p | q | r))) bit 7 is 0+ // then check if ((-(c > -63) ^ (p | q | r))) bit 7 is 1 in a combined test with step 1 // vt = _mm_bsrli_si128(vp, 15); vp = _mm_and_si128(vc, _mm_add_epi8(vc, vc));@@ -266,8 +276,9 @@ bool isutf8(const char *s, const char *e) vt = _mm_or_si128(vt, _mm_bslli_si128(vp, 1)); vt = _mm_or_si128(vt, _mm_bslli_si128(vq, 2)); vt = _mm_or_si128(vt, _mm_bslli_si128(vr, 3));- vt = _mm_xor_si128(vt, _mm_cmplt_epi8(vc, vxc0));- if (_mm_movemask_epi8(vt) != 0x0000)+ vt = _mm_xor_si128(vt, _mm_cmpgt_epi8(vc, vxc1));+ vm = _mm_and_si128(vm, vt);+ if (_mm_movemask_epi8(vm) != 0xffff) return false; s += 16; }@@ -297,17 +308,17 @@ bool isutf8(const char *s, const char *e) } s += 16; }- // my UTF-8 validation method- // 134ms to check 1,000,000,000 bytes on Apple M1 Pro (AArch64)+ // my UTF-8 check method+ // 116ms to check 1,000,000,000 bytes on Apple M1 Pro (AArch64) // // scalar code: // int8_t p = 0, q = 0, r = 0; // while (s < e) // { // int8_t c = static_cast<int8_t>(*s++);- // if (!(c > 0 || (c > -63 && c < -11)))+ // if (!(c > 0 || c < -64 || (c > -63 && c < -11))) // return false;- // if ((-(c < -64) ^ (p | q | r)) & 0x80)+ // if (((-(c > -63) ^ (p | q | r)) & 0x80) != 0x80) // return false; // r = (q & (q << 1)); // q = (p & (p << 1));@@ -323,9 +334,9 @@ bool isutf8(const char *s, const char *e) int8x16_t vr = v0; while (s <= e - 16) {- // step 1: check valid signed byte ranges+ // step 1: check valid signed byte ranges, including continuation bytes 0x80 to 0xbf // c = s[i]- // if (!(c > 0 || (c > -63 && c < -11)))+ // if (!(c > 0 || c < -64 || (c > -63 && c < -11))) // return false // int8x16_t vc = vld1q_s8(reinterpret_cast<const int8_t*>(s));@@ -333,11 +344,9 @@ bool isutf8(const char *s, const char *e) vt = vorrq_s8(vt, vreinterpretq_s8_u8(vcltq_s8(vc, vxc0))); vt = vorrq_s8(vt, vreinterpretq_s8_u8(vcgtq_s8(vc, v0))); int64x2_t vm = vreinterpretq_s64_s8(vt);- if ((vgetq_lane_s64(vm, 0) & vgetq_lane_s64(vm, 1)) != -1LL)- return false; // // step 2: check UTF-8 multi-byte sequences of 2, 3 and 4 bytes long- // if ((-(c < -64) ^ (p | q | r)) & 0x80)+ // if (((-(c > -63) ^ (p | q | r)) & 0x80) != 0x80) // return false // r = (q & (q << 1)) // q = (p & (p << 1))@@ -367,7 +376,7 @@ bool isutf8(const char *s, const char *e) // // optimized code to perform r = (q & (q << 1)); q = (p & (p << 1)); p = (c & (c << 1)); // shift parts of the old vp, vq, vr and new vp, vq, vr in vt using EXT- // then check if ((-(c < -64) ^ (p | q | r))) bit 7 is 0+ // then check if ((-(c > -63) ^ (p | q | r))) bit 7 is 1 in a combined test with step 1 // int8x16_t vo = vp; vp = vandq_s8(vc, vshlq_n_s8(vc, 1));@@ -378,9 +387,9 @@ bool isutf8(const char *s, const char *e) vo = vr; vr = vandq_s8(vq, vshlq_n_s8(vq, 1)); vt = vorrq_s8(vt, vextq_s8(vo, vr, 13));- vt = veorq_s8(vt, vreinterpretq_s8_u8(vcltq_s8(vc, vxc0)));- vm = vreinterpretq_s64_s8(vt);- if (((vgetq_lane_s64(vm, 0) | vgetq_lane_s64(vm, 1)) & 0x8080808080808080LL) != 0)+ vt = veorq_s8(vt, vreinterpretq_s8_u8(vcgtq_s8(vc, vxc1)));+ vm = vandq_s64(vm, vreinterpretq_s64_s8(vt));+ if (((vgetq_lane_s64(vm, 0) & vgetq_lane_s64(vm, 1)) & 0x8080808080808080LL) != 0x8080808080808080LL) return false; s += 16; }
@@ -89,16 +89,16 @@ bool simd_isutf8_avx2(const char *& b, const char *e) { __m256i vc = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s)); __m256i vm = _mm256_cmpgt_epi8(vc, v00);- if (_mm256_movemask_epi8(vm) != 0xffffffff)+ if (_mm256_movemask_epi8(vm) != -1) { vm = _mm256_cmpeq_epi8(vc, v00);- if (_mm256_movemask_epi8(vm) != 0x00000000)+ if (_mm256_movemask_epi8(vm) != 0) return false; break; } s += 32; }- // my UTF-8 validation method+ // my UTF-8 check method // 117ms to check 1,000,000,000 bytes on a Intel quad core i7 2.9 GHz 16GB 2133 MHz LPDDR3 const __m256i vxc0 = _mm256_set1_epi8(0xc0); const __m256i vxc1 = _mm256_set1_epi8(0xc1);@@ -113,8 +113,7 @@ bool simd_isutf8_avx2(const char *& b, const char *e) __m256i vt = _mm256_and_si256(_mm256_cmpgt_epi8(vc, vxc1), _mm256_cmpgt_epi8(vxf5, vc)); vt = _mm256_or_si256(vt, _mm256_cmpgt_epi8(vxc0, vc)); vt = _mm256_or_si256(vt, _mm256_cmpgt_epi8(vc, v0));- if (_mm256_movemask_epi8(vt) != 0xffffffff)- return false;+ __m256i vm = vt; __m256i vo = vp; vp = _mm256_and_si256(vc, _mm256_add_epi8(vc, vc)); // vt = [vp,vo] >> 15*8 split in 128 bit lanes:@@ -133,8 +132,9 @@ bool simd_isutf8_avx2(const char *& b, const char *e) // vthi |= [vrhi,vrlo] >> 13*8 // vtlo |= [vrlo,vohi] >> 13*8 vt = _mm256_or_si256(vt, _mm256_alignr_epi8(vr, _mm256_permute2x128_si256(vr, vo, 0x03), 13));- vt = _mm256_xor_si256(vt, _mm256_cmpgt_epi8(vxc0, vc));- if (_mm256_movemask_epi8(vt) != 0x00000000)+ vt = _mm256_xor_si256(vt, _mm256_cmpgt_epi8(vc, vxc1));+ vm = _mm256_and_si256(vm, vt);+ if (_mm256_movemask_epi8(vm) != -1) return false; s += 32; }
@@ -373,6 +373,10 @@ if option \fB-H\fR is used: \fITEXT\fR, the quoted pathname and separator, \\" and \\\\ replace " and \\. .IP \fB%h\fR the quoted file pathname, \\" and \\\\ replace " and \\.+.IP \fB%[\fR\fITEXT\fR\fB]I\fR+if option \fB-H\fR is used: \fITEXT\fR, the pathname as XML character data and separator.+.IP \fB%i\fR+the file pathname as XML character data. .IP \fB%[\fR\fITEXT\fR\fB]N\fR if option \fB-n\fR is used: \fITEXT\fR, the line number and separator. .IP \fB%n\fR@@ -496,8 +500,8 @@ When present, the argument must be placed in \fB[]\fR brackets, for example \fB%[\fR\fISEP\fR\fB]$\fR and \fB%u\fR are switches and do not send anything to the output. .PP-The separator used by the \fB%F\fR, \fB%H\fR, \fB%N\fR, \fB%K\fR, \fB%B\fR,-\fB%S\fR and \fB%G\fR fields may be changed by preceding the field by+The separator used by the \fB%F\fR, \fB%H\fR, \fB%I\fR, \fB%N\fR, \fB%K\fR,+\fB%B\fR, \fB%S\fR and \fB%G\fR fields may be changed by preceding the field by \fB%[\fR\fISEP\fR\fB]$\fR. When \fB[\fR\fISEP\fR\fB]\fR is not provided, this reverts the separator to the default separator or the separator specified with \fB--separator\fR.
@@ -1,4 +1,4 @@-.TH UGREP "1" "August 23, 2024" "ugrep 6.5.0" "User Commands"+.TH UGREP "1" "October 24, 2024" "ugrep 7.0.0" "User Commands" .SH NAME \fBugrep\fR, \fBug\fR -- file pattern searcher .SH SYNOPSIS@@ -466,13 +466,14 @@ option \fB\-Z\fR and `\fB\-\-help\fR format' displays a list of \fB\-\-format\fR .TP \fB\-\-hexdump\fR[=[1\-8][a][bch][A[\fINUM\fR]][B[\fINUM\fR]][C[\fINUM\fR]]] Output matches in 1 to 8 columns of 8 hexadecimal octets. The-default is 2 columns or 16 octets per line. Option `a' outputs a+default is 2 columns or 16 octets per line. Argument `a' outputs a `*' for all hex lines that are identical to the previous hex line, `b' removes all space breaks, `c' removes the character column, `h'-removes hex spacing, `A' includes up to NUM hex lines after the-match, `B' includes up to NUM hex lines before the match and `C'-includes up to NUM hex lines. When NUM is omitted, the matching-line is included in the output. See also options \fB\-U\fR, \fB\-W\fR and \fB\-X\fR.+removes hex spacing, `A' includes up to NUM hex lines after a+match, `B' includes up to NUM hex lines before a match and `C'+includes up to NUM hex lines before and after a match. Arguments+`A', `B' and `C' are the same as options \fB\-A\fR, \fB\-B\fR and \fB\-C\fR when used+with \fB\-\-hexdump\fR. See also options \fB\-U\fR, \fB\-W\fR and \fB\-X\fR. .TP \fB\-\-hidden\fR, \fB\-.\fR Search hidden files and directories.@@ -709,13 +710,13 @@ the default is 3 (300ms delay). No whitespace may be given between \fB\-e\fR \fIPATTERN\fR, i.e. a PATTERN argument requires option \fB\-e\fR. Press F1 or CTRL\-Z to view the help screen. Press F2 or CTRL\-Y to invoke a command to view or edit the file shown at the top of the screen.-The command can be specified with option \fB\-\-view\fR, or defaults to-environment variable PAGER when defined, or EDITOR. Press Tab and-Shift\-Tab to navigate directories and to select a file to search.-Press Enter to select lines to output. Press ALT\-l for option \fB\-l\fR-to list files, ALT\-n for \fB\-n\fR, etc. Non\-option commands include-ALT\-] to increase context and ALT\-} to increase fuzzyness. See-also options \fB\-\-no\-confirm\fR, \fB\-\-delay\fR, \fB\-\-split\fR and \fB\-\-view\fR.+The command can be specified with option \fB\-\-view\fR and defaults to+environment variable PAGER when defined, or VISUAL or EDITOR.+Press Tab or Shift\-Tab to navigate directories and to select a file+to search. Press Enter to select lines to output. Press ALT\-l for+option \fB\-l\fR to list files, ALT\-n for \fB\-n\fR, etc. Non\-option commands+include ALT\-] to increase context and ALT\-} to increase fuzzyness.+See also options \fB\-\-no\-confirm\fR, \fB\-\-delay\fR, \fB\-\-split\fR and \fB\-\-view\fR. .TP \fB\-q\fR, \fB\-\-quiet\fR, \fB\-\-silent\fR Quiet mode: suppress all output. Only search a file until a match@@ -761,7 +762,7 @@ the specified FILE, but recursive config loading is not allowed. Use SEP as field separator between file name, line number, column number, byte offset and the matched line. The default separator is a colon (`:') and a bar (`|') for multi\-line pattern matches, and a-dash (`\-') for context lines. See also \fB\-\-group\-separator\fR.+dash (`\-') for context lines. See also option \fB\-\-group\-separator\fR. .TP \fB\-\-split\fR Split the \fB\-Q\fR query TUI screen on startup.@@ -850,9 +851,9 @@ Use COMMAND to view/edit a file in \fB\-Q\fR query TUI by pressing CTRL\-Y. .TP \fB\-W\fR, \fB\-\-with\-hex\fR Output binary matches in hexadecimal, leaving text matches alone.-This option is equivalent to the \fB\-\-binary\-files\fR=with\-hex option-with \fB\-\-hexdump\fR=2C. To omit the matching line from the hex output,-combine option \fB\-\-hexdump\fR with option \fB\-W\fR. See also option \fB\-U\fR.+This option is equivalent to the \fB\-\-binary\-files\fR=with\-hex option.+To omit the matching line from the hex output, use both options \fB\-W\fR+and \fB\-\-hexdump\fR. See also options \fB\-U\fR. .TP \fB\-w\fR, \fB\-\-word\-regexp\fR The PATTERN is searched for as a word, such that the matching text@@ -866,8 +867,8 @@ of the terminal window is used if NUM is not specified. Note that double wide characters in the output may result in wider lines. .TP \fB\-X\fR, \fB\-\-hex\fR-Output matches in hexadecimal. This option is equivalent to the-\fB\-\-binary\-files\fR=hex option with \fB\-\-hexdump\fR=2C. To omit the matching+Output matches and matching lines in hexadecimal. This option is+equivalent to the \fB\-\-binary\-files\fR=hex option. To omit the matching line from the hex output use option \fB\-\-hexdump\fR. See also option \fB\-U\fR. .TP \fB\-x\fR, \fB\-\-line\-regexp\fR@@ -1142,6 +1143,10 @@ if option \fB-H\fR is used: \fITEXT\fR, the quoted pathname and separator, \\" and \\\\ replace " and \\. .IP \fB%h\fR the quoted file pathname, \\" and \\\\ replace " and \\.+.IP \fB%[\fR\fITEXT\fR\fB]I\fR+if option \fB-H\fR is used: \fITEXT\fR, the pathname as XML character data and separator.+.IP \fB%i\fR+the file pathname as XML character data. .IP \fB%[\fR\fITEXT\fR\fB]N\fR if option \fB-n\fR is used: \fITEXT\fR, the line number and separator. .IP \fB%n\fR@@ -1265,8 +1270,8 @@ When present, the argument must be placed in \fB[]\fR brackets, for example \fB%[\fR\fISEP\fR\fB]$\fR and \fB%u\fR are switches and do not send anything to the output. .PP-The separator used by the \fB%F\fR, \fB%H\fR, \fB%N\fR, \fB%K\fR, \fB%B\fR,-\fB%S\fR and \fB%G\fR fields may be changed by preceding the field by+The separator used by the \fB%F\fR, \fB%H\fR, \fB%I\fR, \fB%N\fR, \fB%K\fR,+\fB%B\fR, \fB%S\fR and \fB%G\fR fields may be changed by preceding the field by \fB%[\fR\fISEP\fR\fB]$\fR. When \fB[\fR\fISEP\fR\fB]\fR is not provided, this reverts the separator to the default separator or the separator specified with \fB--separator\fR.
@@ -1,4 +1,4 @@-.TH UGREP-INDEXER "1" "August 23, 2024" "ugrep-indexer 6.5.0" "User Commands"+.TH UGREP-INDEXER "1" "October 24, 2024" "ugrep-indexer 7.0.0" "User Commands" .SH NAME \fBugrep-indexer\fR -- file indexer to accelerate recursive searching .SH SYNOPSIS
@@ -1,4 +1,4 @@-.TH UGREP "1" "August 23, 2024" "ugrep 6.5.0" "User Commands"+.TH UGREP "1" "October 24, 2024" "ugrep 7.0.0" "User Commands" .SH NAME \fBugrep\fR, \fBug\fR -- file pattern searcher .SH SYNOPSIS@@ -466,13 +466,14 @@ option \fB\-Z\fR and `\fB\-\-help\fR format' displays a list of \fB\-\-format\fR .TP \fB\-\-hexdump\fR[=[1\-8][a][bch][A[\fINUM\fR]][B[\fINUM\fR]][C[\fINUM\fR]]] Output matches in 1 to 8 columns of 8 hexadecimal octets. The-default is 2 columns or 16 octets per line. Option `a' outputs a+default is 2 columns or 16 octets per line. Argument `a' outputs a `*' for all hex lines that are identical to the previous hex line, `b' removes all space breaks, `c' removes the character column, `h'-removes hex spacing, `A' includes up to NUM hex lines after the-match, `B' includes up to NUM hex lines before the match and `C'-includes up to NUM hex lines. When NUM is omitted, the matching-line is included in the output. See also options \fB\-U\fR, \fB\-W\fR and \fB\-X\fR.+removes hex spacing, `A' includes up to NUM hex lines after a+match, `B' includes up to NUM hex lines before a match and `C'+includes up to NUM hex lines before and after a match. Arguments+`A', `B' and `C' are the same as options \fB\-A\fR, \fB\-B\fR and \fB\-C\fR when used+with \fB\-\-hexdump\fR. See also options \fB\-U\fR, \fB\-W\fR and \fB\-X\fR. .TP \fB\-\-hidden\fR, \fB\-.\fR Search hidden files and directories.@@ -709,13 +710,13 @@ the default is 3 (300ms delay). No whitespace may be given between \fB\-e\fR \fIPATTERN\fR, i.e. a PATTERN argument requires option \fB\-e\fR. Press F1 or CTRL\-Z to view the help screen. Press F2 or CTRL\-Y to invoke a command to view or edit the file shown at the top of the screen.-The command can be specified with option \fB\-\-view\fR, or defaults to-environment variable PAGER when defined, or EDITOR. Press Tab and-Shift\-Tab to navigate directories and to select a file to search.-Press Enter to select lines to output. Press ALT\-l for option \fB\-l\fR-to list files, ALT\-n for \fB\-n\fR, etc. Non\-option commands include-ALT\-] to increase context and ALT\-} to increase fuzzyness. See-also options \fB\-\-no\-confirm\fR, \fB\-\-delay\fR, \fB\-\-split\fR and \fB\-\-view\fR.+The command can be specified with option \fB\-\-view\fR and defaults to+environment variable PAGER when defined, or VISUAL or EDITOR.+Press Tab or Shift\-Tab to navigate directories and to select a file+to search. Press Enter to select lines to output. Press ALT\-l for+option \fB\-l\fR to list files, ALT\-n for \fB\-n\fR, etc. Non\-option commands+include ALT\-] to increase context and ALT\-} to increase fuzzyness.+See also options \fB\-\-no\-confirm\fR, \fB\-\-delay\fR, \fB\-\-split\fR and \fB\-\-view\fR. .TP \fB\-q\fR, \fB\-\-quiet\fR, \fB\-\-silent\fR Quiet mode: suppress all output. Only search a file until a match@@ -761,7 +762,7 @@ the specified FILE, but recursive config loading is not allowed. Use SEP as field separator between file name, line number, column number, byte offset and the matched line. The default separator is a colon (`:') and a bar (`|') for multi\-line pattern matches, and a-dash (`\-') for context lines. See also \fB\-\-group\-separator\fR.+dash (`\-') for context lines. See also option \fB\-\-group\-separator\fR. .TP \fB\-\-split\fR Split the \fB\-Q\fR query TUI screen on startup.@@ -850,9 +851,9 @@ Use COMMAND to view/edit a file in \fB\-Q\fR query TUI by pressing CTRL\-Y. .TP \fB\-W\fR, \fB\-\-with\-hex\fR Output binary matches in hexadecimal, leaving text matches alone.-This option is equivalent to the \fB\-\-binary\-files\fR=with\-hex option-with \fB\-\-hexdump\fR=2C. To omit the matching line from the hex output,-combine option \fB\-\-hexdump\fR with option \fB\-W\fR. See also option \fB\-U\fR.+This option is equivalent to the \fB\-\-binary\-files\fR=with\-hex option.+To omit the matching line from the hex output, use both options \fB\-W\fR+and \fB\-\-hexdump\fR. See also options \fB\-U\fR. .TP \fB\-w\fR, \fB\-\-word\-regexp\fR The PATTERN is searched for as a word, such that the matching text@@ -866,8 +867,8 @@ of the terminal window is used if NUM is not specified. Note that double wide characters in the output may result in wider lines. .TP \fB\-X\fR, \fB\-\-hex\fR-Output matches in hexadecimal. This option is equivalent to the-\fB\-\-binary\-files\fR=hex option with \fB\-\-hexdump\fR=2C. To omit the matching+Output matches and matching lines in hexadecimal. This option is+equivalent to the \fB\-\-binary\-files\fR=hex option. To omit the matching line from the hex output use option \fB\-\-hexdump\fR. See also option \fB\-U\fR. .TP \fB\-x\fR, \fB\-\-line\-regexp\fR@@ -1142,6 +1143,10 @@ if option \fB-H\fR is used: \fITEXT\fR, the quoted pathname and separator, \\" and \\\\ replace " and \\. .IP \fB%h\fR the quoted file pathname, \\" and \\\\ replace " and \\.+.IP \fB%[\fR\fITEXT\fR\fB]I\fR+if option \fB-H\fR is used: \fITEXT\fR, the pathname as XML character data and separator.+.IP \fB%i\fR+the file pathname as XML character data. .IP \fB%[\fR\fITEXT\fR\fB]N\fR if option \fB-n\fR is used: \fITEXT\fR, the line number and separator. .IP \fB%n\fR@@ -1265,8 +1270,8 @@ When present, the argument must be placed in \fB[]\fR brackets, for example \fB%[\fR\fISEP\fR\fB]$\fR and \fB%u\fR are switches and do not send anything to the output. .PP-The separator used by the \fB%F\fR, \fB%H\fR, \fB%N\fR, \fB%K\fR, \fB%B\fR,-\fB%S\fR and \fB%G\fR fields may be changed by preceding the field by+The separator used by the \fB%F\fR, \fB%H\fR, \fB%I\fR, \fB%N\fR, \fB%K\fR,+\fB%B\fR, \fB%S\fR and \fB%G\fR fields may be changed by preceding the field by \fB%[\fR\fISEP\fR\fB]$\fR. When \fB[\fR\fISEP\fR\fB]\fR is not provided, this reverts the separator to the default separator or the separator specified with \fB--separator\fR.
@@ -678,7 +678,8 @@ void Output::format(const char *format, size_t matches) case '$': sep = arg;- len = s - arg - 1;+ if (arg != NULL)+ len = s - arg - 1; break; case 't':@@ -910,6 +911,47 @@ bool Output::format(const char *format, const char *pathname, const std::string& } break; + case 'I':+ if (flag_with_filename && (heading || !partname.empty()))+ {+ if (arg != NULL)+ str(arg, s - arg - 1);+ if (!partname.empty())+ {+ std::string name;+ if (heading)+ name = pathname;+ name.push_back('{');+ name.append(partname);+ name.push_back('}');+ xml(name.c_str(), name.size());+ }+ else+ {+ xml(pathname, strlen(pathname));+ }+ if (sep != NULL)+ str(sep, len);+ else+ str(flag_separator);+ }+ break;++ case 'i':+ if (!partname.empty())+ {+ std::string name(pathname);+ name.push_back('{');+ name.append(partname);+ name.push_back('}');+ xml(name.c_str(), name.size());+ }+ else+ {+ xml(pathname, strlen(pathname));+ }+ break;+ case 'N': if (flag_line_number) {@@ -1413,7 +1455,8 @@ bool Output::format(const char *format, const char *pathname, const std::string& case '$': sep = arg;- len = s - arg - 1;+ if (arg != NULL)+ len = s - arg - 1; break; case 'R':@@ -1637,6 +1680,47 @@ void Output::format_invert(const char *format, const char *pathname, const std:: } break; + case 'I':+ if (flag_with_filename && (heading || !partname.empty()))+ {+ if (arg != NULL)+ str(arg, s - arg - 1);+ if (!partname.empty())+ {+ std::string name;+ if (heading)+ name = pathname;+ name.push_back('{');+ name.append(partname);+ name.push_back('}');+ xml(name.c_str(), name.size());+ }+ else+ {+ xml(pathname, strlen(pathname));+ }+ if (sep != NULL)+ str(sep, len);+ else+ str(flag_separator);+ }+ break;++ case 'i':+ if (!partname.empty())+ {+ std::string name(pathname);+ name.push_back('{');+ name.append(partname);+ name.push_back('}');+ xml(name.c_str(), name.size());+ }+ else+ {+ xml(pathname, strlen(pathname));+ }+ break;+ case 'N': if (flag_line_number) {@@ -1819,7 +1903,8 @@ void Output::format_invert(const char *format, const char *pathname, const std:: case '$': sep = arg;- len = s - arg - 1;+ if (arg != NULL)+ len = s - arg - 1; break; case 'R':
@@ -976,7 +976,7 @@ class Output { char *cur_; // current position in the current buffer int mode_; // bitmask 1 if line buffered 2 if hold size_t cols_; // number of columns output so far, if --width- ANSI ansi_; // ANSI escape sequence+ ANSI ansi_; // ANSI escape sequence state machine state bool skip_; // skip until next newline in buffers, if --width };
@@ -810,11 +810,14 @@ void Query::query() get_flags(); - // if --view is empty (default), then try the PAGER or EDITOR environment variable as viewer or use the default viewer+ // if --view is empty (default), then try the PAGER, VISUAL or EDITOR environment variable as viewer or use the default viewer if (flag_view != NULL && *flag_view == '\0') { flag_view = getenv("PAGER"); + if (flag_view == NULL)+ flag_view = getenv("VISUAL");+ if (flag_view == NULL) flag_view = getenv("EDITOR");
@@ -35,7 +35,7 @@ */ // DO NOT ALTER THIS LINE: updated by makemake.sh and we need it physically here for MSVC++ build from source-#define UGREP_VERSION "6.5.0"+#define UGREP_VERSION "7.0.0" // use a task-parallel thread to decompress the stream into a pipe to search, also handles nested archives #define WITH_DECOMPRESSION_THREAD@@ -720,6 +720,18 @@ void usage(const char *message, const char *arg = NULL) } } +#ifdef HAVE_LIBZ+// decompression error, function used by+void cannot_decompress(const char *pathname, const char *message)+{+ ++warnings;+ if (flag_no_messages)+ return;+ printf("ugrep-indexer: warning: cannot decompress %s: %s\n", pathname, message != NULL ? message : "");+ fflush(stdout);+}+#endif+ // display a warning message unless option -s (--no-messages) void warning(const char *message, const char *arg = NULL) {@@ -747,18 +759,6 @@ void error(const char *message, const char *arg) fflush(stdout); } -#ifdef HAVE_LIBZ-// decompression error, function used by-void cannot_decompress(const char *pathname, const char *message)-{- ++warnings;- if (!flag_verbose || flag_no_messages)- return;- printf("ugrep-indexer: warning: cannot decompress %s: %s\n", pathname, message != NULL ? message : "");- fflush(stdout);-}-#endif- // convert unsigned decimal to non-negative size_t, produce error when conversion fails size_t strtonum(const char *string, const char *message) {@@ -1790,7 +1790,7 @@ void indexer(const char *pathname) printf("%13" PRIu64 " directories ignored with --ignore-files\n%13" PRIu64 " files ignored with --ignore-files\n", ign_dirs, ign_files); printf("%13" PRIu64 " symbolic links skipped\n%13" PRIu64 " devices skipped\n", num_links, num_other); if (warnings > 0)- printf("%13zu warnings\n", warnings);+ printf("%13zu warnings and errors\n", warnings); if (add_dirs == 0 && add_files == 0 && mod_files == 0 && del_files == 0) printf("\nChecked: indexes are fresh and up to date\n\n"); else@@ -1809,7 +1809,7 @@ void indexer(const char *pathname) printf("%13" PRIu64 " directories ignored with --ignore-files\n%13" PRIu64 " files ignored with --ignore-files\n", ign_dirs, ign_files); printf("%13" PRIu64 " symbolic links skipped\n%13" PRIu64 " devices skipped\n", num_links, num_other); if (!flag_quiet && warnings > 0)- printf("%13zu warnings\n", warnings);+ printf("%13zu warnings and errors\n", warnings); if (sum_hashes_size > 0) printf("%13" PRId64 " bytes indexing storage increase at %" PRId64 " bytes/file\n\n", sum_hashes_size, sum_hashes_size / num_files); else
@@ -2311,7 +2311,7 @@ struct Grep { #ifndef OS_WIN - // extend the reflex::Input::Handler to handle stdin from a TTY or from a slow pipe+ // extend the reflex::Input::Handler to handle nonblocking stdin from a TTY or from a slow pipe struct StdInHandler : public reflex::Input::Handler { StdInHandler(Grep *grep)@@ -4043,7 +4043,6 @@ struct Grep { { // check up to 64K in buffer for binary data, the buffer is a window over the input file size_t avail = std::min<size_t>(matcher->avail(), 65536);- if (avail == 0) return false; @@ -6519,8 +6518,8 @@ void init(int argc, const char **argv) { int context = 0; - flag_hex_after = (flag_after_context == 0);- flag_hex_before = (flag_before_context == 0);+ flag_hex_after = flag_after_context + 1;+ flag_hex_before = flag_before_context + 1; for (const char *s = flag_hexdump; *s != '\0'; ++s) {@@ -6547,17 +6546,17 @@ void init(int argc, const char **argv) break; case 'A':- flag_hex_after = 0;+ flag_hex_after = 2; context = 1; break; case 'B':- flag_hex_before = 0;+ flag_hex_before = 2; context = 2; break; case 'C':- flag_hex_after = flag_hex_before = 0;+ flag_hex_after = flag_hex_before = 2; context = 3; break; @@ -6593,6 +6592,9 @@ void init(int argc, const char **argv) // enable option -X if -W is not enabled if (!flag_with_hex) flag_hex = true;++ // disable -ABC line context to use hex binary context+ flag_after_context = flag_before_context = 0; } // --hex takes priority over --with-hex takes priority over -I takes priority over -a@@ -6862,7 +6864,7 @@ void init(int argc, const char **argv) else if (flag_xml) { flag_format_begin = "<grep>\n";- flag_format_open = " <file%[]$%[ name=]H>\n";+ flag_format_open = " <file%[\"]$%[ name=\"]I>\n"; flag_format = " <match%[\"]$%[ line=\"]N%[ column=\"]K%[ offset=\"]B>%X</match>\n%u"; flag_format_close = " </file>\n"; flag_format_end = "</grep>\n";@@ -7045,7 +7047,9 @@ void init(int argc, const char **argv) // scan the type_table[] for the specified type, allowing type to be a prefix when unambiguous for (size_t j = 0; type_table[j].type != NULL; ++j) {- if (type.compare(0, size, type_table[j].type, size) == 0)+ size_t typelen = strlen(type_table[j].type);++ if (size <= typelen && type.compare(0, size, type_table[j].type, size) == 0) { // an ambiguous prefix is not a valid type if (found)@@ -7055,7 +7059,7 @@ void init(int argc, const char **argv) i = j; // if full type match then we found a valid type match- if (strlen(type_table[j].type) == size)+ if (size == typelen) { valid = true; break;@@ -8754,7 +8758,7 @@ void ugrep() close_pager(); } -// perform a limited ugrep search on a single file with optional archive part and store up to num results in a vector, may throw an exception+// perform a limited ugrep search on a single file with optional archive part and store up to num results in a vector, may throw an exception, used by the TUI void ugrep_find_text_preview(const char *filename, const char *partname, size_t from_lineno, size_t max, size_t& lineno, size_t& num, std::vector<std::string>& text) { // we can only return a text preview when the main search engine ugrep() already started and executes, or after it ends@@ -8778,7 +8782,7 @@ void ugrep_find_text_preview(const char *filename, const char *partname, size_t delete matcher; } -// extract a part from an archive and send to a stream+// extract a part from an archive and send to a stream, used by the TUI void ugrep_extract(const char *filename, const char *partname, FILE *output) { Grep grep(NULL, NULL, NULL);@@ -11250,6 +11254,16 @@ void Grep::search(const char *pathname, uint16_t cost) binary = flag_hex || (flag_with_hex && is_binary(bol, eol - bol)); + if (binary && (flag_hex_after > 0 || flag_hex_before > 0))+ {+ const char *aft = matcher->aft((flag_hex_after + flag_hex_before) * flag_hex_columns);+ if (aft > eol)+ {+ eol = aft;+ bol = matcher->bol(); // warning: bol() position may have shifted with aft()+ }+ }+ if (binfile || (binary && !flag_hex && !flag_with_hex)) { if (flag_binary_without_match)@@ -11288,7 +11302,14 @@ void Grep::search(const char *pathname, uint16_t cost) { if (flag_hex_before > 0) {- size_t left = (flag_hex_before - 1) * flag_hex_columns + (first % flag_hex_columns);+ const char *bef = matcher->bef(flag_hex_before * flag_hex_columns);+ if (bef < bol)+ {+ bol = bef;+ border = begin - bol;+ }++ size_t left = flag_hex_before * flag_hex_columns + (first % flag_hex_columns) - flag_hex_columns; if (begin > bol + left) { bol = begin - left;@@ -11396,8 +11417,8 @@ void Grep::search(const char *pathname, uint16_t cost) } } - // no -u and no colors: if the match does not span more than one line, then skip to end of the line- if (!flag_ungroup && !colorize)+ // no -u, no --hexdump and no colors: if the match does not span more than one line, then skip to end of the line+ if (!flag_ungroup && !colorize && !(binary && (flag_hex_after > 0 || flag_hex_before > 0))) if (!flag_multiline && !matcher->at_bol()) if (!matcher->skip('\n')) break;@@ -11422,34 +11443,52 @@ void Grep::search(const char *pathname, uint16_t cost) if (binary) {- if (flag_hex_after > 0 && flag_hex_before > 0)+ if (restline_data != NULL) {- size_t right = flag_hex_after * flag_hex_columns - ((restline_last - 1) % flag_hex_columns) - 1;- if (right < first - restline_last)+ if (restline_last + restline_size > first)+ restline_size = first - restline_last;++ if (flag_hex_after > 0) {- out.dump.hex(Output::Dump::HEX_LINE, restline_last, restline_data, right);+ size_t right = flag_hex_after * flag_hex_columns - ((restline_last - 1) % flag_hex_columns) - 1;+ if (right < restline_size)+ {+ out.dump.hex(Output::Dump::HEX_LINE, restline_last, restline_data, right); - restline_data += right;- restline_size -= right;- restline_last += right;+ restline_data += right;+ restline_size -= right;+ restline_last += right;+ }+ else+ {+ out.dump.hex(Output::Dump::HEX_LINE, restline_last, restline_data, restline_size); - size_t left = (flag_hex_before - 1) * flag_hex_columns + (first % flag_hex_columns);+ restline_data = NULL;+ }+ } - if (left < first - restline_last)+ if (restline_data != NULL)+ {+ if (flag_hex_before > 0) {- if (!flag_no_header)- out.header(pathname, partname, heading, current_lineno, matcher, first, flag_separator_bar, binary);-- left = first - restline_last - left;+ size_t left = flag_hex_before * flag_hex_columns + (first % flag_hex_columns) - flag_hex_columns;+ if (left < restline_size)+ {+ if (!flag_no_header)+ out.header(pathname, partname, heading, current_lineno, matcher, first, flag_separator_bar, binary); - restline_data += left;- restline_size -= left;- restline_last += left;+ restline_data = restline_data + restline_size - left;+ restline_last = restline_last + restline_size - left;+ restline_size = left;+ } }++ out.dump.hex(Output::Dump::HEX_LINE, restline_last, restline_data, restline_size); }++ restline_data = NULL; } - out.dump.hex(Output::Dump::HEX_LINE, restline_last, restline_data, first - restline_last); out.dump.hex(Output::Dump::HEX_MATCH, first, begin, size); } else@@ -11498,19 +11537,39 @@ void Grep::search(const char *pathname, uint16_t cost) } } + const char *eol = matcher->eol(true); // warning: call eol() before end()+ const char *end = matcher->end();+ if (lines == 1) {- restline_data += last - restline_last;- restline_size -= last - restline_last;+ if (binary && (flag_hex_after > 0 || flag_hex_before > 0))+ {+ const char *aft = matcher->aft((flag_hex_after + flag_hex_before) * flag_hex_columns);+ if (aft > eol)+ {+ eol = aft;+ end = matcher->end(); // warning: end() position may have shifted with aft()+ }+ }++ restline_data = end;+ restline_size = eol - end; restline_last = last; } else {- const char *eol = matcher->eol(true); // warning: call eol() before end()- const char *end = matcher->end();- binary = flag_hex || (flag_with_hex && is_binary(end, eol - end)); + if (binary && (flag_hex_after > 0 || flag_hex_before > 0))+ {+ const char *aft = matcher->aft((flag_hex_after + flag_hex_before) * flag_hex_columns);+ if (aft > eol)+ {+ eol = aft;+ end = matcher->end(); // warning: end() position may have shifted with aft()+ }+ }+ if (hex && !binary) out.dump.done(); else if (!hex && binary)@@ -12201,13 +12260,6 @@ void Grep::search(const char *pathname, uint16_t cost) { if (binary) {- if (flag_hex_after > 0)- {- size_t right = flag_hex_after * flag_hex_columns - ((restline_last - 1) % flag_hex_columns) - 1;- if (right < restline_size)- restline_size = right;- }- out.dump.hex(Output::Dump::HEX_LINE, restline_last, restline_data, restline_size); } else@@ -12323,16 +12375,6 @@ void Grep::search(const char *pathname, uint16_t cost) if (binary) {- if (flag_hex_before > 0)- {- size_t left = (flag_hex_before - 1) * flag_hex_columns + (first % flag_hex_columns);- if (begin > bol + left)- {- bol = begin - left;- border = left;- }- }- out.dump.hex(Output::Dump::HEX_LINE, first - border, bol, border); out.dump.hex(Output::Dump::HEX_MATCH, first, begin, size); @@ -12454,7 +12496,9 @@ void Grep::search(const char *pathname, uint16_t cost) if (binary) {- out.dump.hex(Output::Dump::HEX_LINE, restline_last, restline_data, first - restline_last);+ if (restline_data != NULL)+ out.dump.hex(Output::Dump::HEX_LINE, restline_last, restline_data, first - restline_last);+ out.dump.hex(Output::Dump::HEX_MATCH, first, begin, size); } else@@ -12577,13 +12621,6 @@ void Grep::search(const char *pathname, uint16_t cost) { if (binary) {- if (flag_hex_after > 0)- {- size_t right = flag_hex_after * flag_hex_columns - ((restline_last - 1) % flag_hex_columns) - 1;- if (right < restline_size)- restline_size = right;- }- out.dump.hex(Output::Dump::HEX_LINE, restline_last, restline_data, restline_size); } else@@ -13212,7 +13249,7 @@ exit_search: Stats::found_file(); } -// search input after lineno to populate a string vector with the matching line and lines after up to max lines+// search input after lineno to populate a string vector with the matching line and lines after up to max lines. used by the TUI void Grep::find_text_preview(const char *filename, const char *findpart, size_t from_lineno, size_t max, size_t& lineno, size_t& num, std::vector<std::string>& text) { // no results yet@@ -13296,7 +13333,7 @@ void Grep::find_text_preview(const char *filename, const char *findpart, size_t continue; } -// extract a part from an archive and send to a stream+// extract a part from an archive and send to a stream, used by the TUI void Grep::extract(const char *filename, const char *findpart, FILE *output) { try@@ -13385,7 +13422,7 @@ void trim(std::string& line) line.erase(pos, len - pos); } -// trim path separators from an argv[] argument - important: modifies the argv[] string+// trim path separators from an argv[] argument - important: modifies the argv[] string passed as arg void trim_pathname_arg(const char *arg) { // remove trailing path separators after the drive prefix and path, if any - note: this truncates argv[] strings@@ -14034,13 +14071,14 @@ void help(std::ostream& out) option -Z and `--help format' displays a list of --format fields.\n\ --hexdump[=[1-8][a][bch][A[NUM]][B[NUM]][C[NUM]]]\n\ Output matches in 1 to 8 columns of 8 hexadecimal octets. The\n\- default is 2 columns or 16 octets per line. Option `a' outputs a\n\+ default is 2 columns or 16 octets per line. Argument `a' outputs a\n\ `*' for all hex lines that are identical to the previous hex line,\n\ `b' removes all space breaks, `c' removes the character column, `h'\n\- removes hex spacing, `A' includes up to NUM hex lines after the\n\- match, `B' includes up to NUM hex lines before the match and `C'\n\- includes up to NUM hex lines. When NUM is omitted, the matching\n\- line is included in the output. See also options -U, -W and -X.\n\+ removes hex spacing, `A' includes up to NUM hex lines after a\n\+ match, `B' includes up to NUM hex lines before a match and `C'\n\+ includes up to NUM hex lines before and after a match. Arguments\n\+ `A', `B' and `C' are the same as options -A, -B and -C when used\n\+ with --hexdump. See also options -U, -W and -X.\n\ --hidden, -.\n\ Search " #ifdef OS_WIN@@ -14257,13 +14295,13 @@ void help(std::ostream& out) -e PATTERN, i.e. a PATTERN argument requires option -e. Press F1\n\ or CTRL-Z to view the help screen. Press F2 or CTRL-Y to invoke a\n\ command to view or edit the file shown at the top of the screen.\n\- The command can be specified with option --view, or defaults to\n\- environment variable PAGER when defined, or EDITOR. Press Tab and\n\- Shift-Tab to navigate directories and to select a file to search.\n\- Press Enter to select lines to output. Press ALT-l for option -l\n\- to list files, ALT-n for -n, etc. Non-option commands include\n\- ALT-] to increase context and ALT-} to increase fuzzyness. See\n\- also options --no-confirm, --delay, --split and --view.\n\+ The command can be specified with option --view and defaults to\n\+ environment variable PAGER when defined, or VISUAL or EDITOR.\n\+ Press Tab or Shift-Tab to navigate directories and to select a file\n\+ to search. Press Enter to select lines to output. Press ALT-l for\n\+ option -l to list files, ALT-n for -n, etc. Non-option commands\n\+ include ALT-] to increase context and ALT-} to increase fuzzyness.\n\+ See also options --no-confirm, --delay, --split and --view.\n\ -q, --quiet, --silent\n\ Quiet mode: suppress all output. Only search a file until a match\n\ has been found.\n\@@ -14301,7 +14339,7 @@ void help(std::ostream& out) Use SEP as field separator between file name, line number, column\n\ number, byte offset and the matched line. The default separator is\n\ a colon (`:') and a bar (`|') for multi-line pattern matches, and a\n\- dash (`-') for context lines. See also --group-separator.\n\+ dash (`-') for context lines. See also option --group-separator.\n\ --split\n\ Split the -Q query TUI screen on startup.\n\ --sort[=KEY]\n\@@ -14364,9 +14402,9 @@ void help(std::ostream& out) Use COMMAND to view/edit a file in -Q query TUI by pressing CTRL-Y.\n\ -W, --with-hex\n\ Output binary matches in hexadecimal, leaving text matches alone.\n\- This option is equivalent to the --binary-files=with-hex option\n\- with --hexdump=2C. To omit the matching line from the hex output,\n\- combine option --hexdump with option -W. See also option -U.\n\+ This option is equivalent to the --binary-files=with-hex option.\n\+ To omit the matching line from the hex output, use both options -W\n\+ and --hexdump. See also options -U.\n\ -w, --word-regexp\n\ The PATTERN is searched for as a word, such that the matching text\n\ is preceded by a non-word character and is followed by a non-word\n\@@ -14377,8 +14415,8 @@ void help(std::ostream& out) of the terminal window is used if NUM is not specified. Note that\n\ double wide characters in the output may result in wider lines.\n\ -X, --hex\n\- Output matches in hexadecimal. This option is equivalent to the\n\- --binary-files=hex option with --hexdump=2C. To omit the matching\n\+ Output matches and matching lines in hexadecimal. This option is\n\+ equivalent to the --binary-files=hex option. To omit the matching\n\ line from the hex output use option --hexdump. See also option -U.\n\ -x, --line-regexp\n\ Select only those matches that exactly match the whole line, as if\n\@@ -14581,14 +14619,16 @@ void help(const char *what) %b byte offset of a match %; ; if %m > 1, same as %[;]>\n\ %B %[...]B ... + byte offset, if -b %| | if %m > 1, same as %[|]>\n\ %c matching pattern as C/C++ %[...]$ assign ... to separator\n\- %C matching line as C/C++ %[ms]=...%= color of ms ... color off\n\- %d byte size of a match --------------------------------------\n\- %e end offset of a match \n\- %f pathname of matching file Fields that require -P for captures:\n\+ %C matching line as C/C++ %$ reset to default separator\n\+ %d byte size of a match %[ms]=...%= color of ms ... color off\n\+ %e end offset of a match --------------------------------------\n\+ %f pathname of matching file \n\ %F %[...]F ... + pathname, if -H \n\- %+ %F as heading/break, if -+ field output\n\- %h quoted \"pathname\" ---------- --------------------------\n\- %H %[...]H ... + \"pathname\", if -H %1 %2...%9 group capture\n\+ %+ %F as heading/break, if -+ Fields that require -P for captures:\n\+ %h quoted \"pathname\" \n\+ %H %[...]H ... + \"pathname\", if -H field output\n\+ %i pathname as XML ---------- --------------------------\n\+ %I %[...]I ... + pathname XML, if -H %1 %2...%9 group capture\n\ %j matching pattern as JSON %[n]# nth group capture\n\ %J matching line as JSON %[n]b nth capture byte offset\n\ %k column number of a match %[n]d nth capture byte size\n\@@ -14662,32 +14702,33 @@ Character context on a matching line before or after a match is output when\n\ a{3}? 3 a's lazily \\cZ control character ^Z\n\ a{3,}? 3 or more a's lazily \\0 NUL\n\ a{3,7}? 3 to 7 a's lazily \\0ddd octal character code ddd\n\- -------------------------------------- \\xhh hex character code hh\n\- \\x{hhhh} Unicode code point U+hhhh\n\- pattern character classes \\u{hhhh} Unicode code point U+hhhh\n\- ---------- -------------------------- --------------------------------------\n\- [abc-e] one character a,b,c,d,e \n\- [^abc-e] one char not a,b,c,d,e,\\n pattern anchors and boundaries\n\- [[:name:]] one char in POSIX class: ---------- --------------------------\n\- alnum a-z,A-Z,0-9 ^ begin of line anchor\n\- alpha a-z,A-Z $ end of line anchor\n\- ascii ASCII char \\x00-\\x7f \\A begin of file anchor\n\- blank space or tab \\Z end of file anchodr\n\- cntrl control characters \\b word boundary\n\- digit 0-9 \\B non-word boundary\n\- graph visible characters \\< start of word boundary\n\- lower a-z \\> end of word boundary\n\- print visible chars and space (?=...) lookahead (-P)\n\- punct punctuation characters (?!...) negative lookahead (-P)\n\- space space,\\t,\\v,\\f,\\r (?<=...) lookbehind (-P)\n\- upper A-Z (?<!...) negative lookbehind (-P)\n\- word a-z,A-Z,0-9,_ --------------------------------------\n\+ a(b|cd?) ab or ac or acd \\xhh hex character code hh\n\+ -------------------------------------- \\x{hhhh} Unicode code point U+hhhh\n\+ \\u{hhhh} Unicode code point U+hhhh\n\+ pattern character classes --------------------------------------\n\+ ---------- -------------------------- \n\+ [abc-e] one character a,b,c,d,e pattern anchors and boundaries\n\+ [^abc-e] one char not a,b,c,d,e,\\n ---------- --------------------------\n\+ [[:name:]] one char in POSIX class: ^ begin of line anchor\n\+ alnum a-z,A-Z,0-9 $ end of line anchor\n\+ alpha a-z,A-Z \\A begin of file anchor\n\+ ascii ASCII char \\x00-\\x7f \\Z end of file anchodr\n\+ blank space or tab \\b word boundary\n\+ cntrl control characters \\B non-word boundary\n\+ digit 0-9 \\< start of word boundary\n\+ graph visible characters \\> end of word boundary\n\+ lower a-z (?=...) lookahead (-P)\n\+ print visible chars and space (?!...) negative lookahead (-P)\n\+ punct punctuation characters (?<=...) lookbehind (-P)\n\+ space space,\\t,\\v,\\f,\\r (?<!...) negative lookbehind (-P)\n\+ upper A-Z --------------------------------------\n\+ word a-z,A-Z,0-9,_ (-P): pattern requires option -P\n\ xdigit 0-9,a-f,A-F \n\ \\p{class} one character in class pattern grouping\n\ \\P{class} one char not in class ---------- --------------------------\n\- \\d a digit (...) capturing group (-P)\n\- \\D a non-digit (...) non-capturing group\n\- \\h a space or tab (?:...) non-capturing group\n\+ \\d a digit (...) non-capturing group\n\+ \\D a non-digit (...) capturing group (-P)\n\+ \\h a space or tab (?:...) non-capturing group (-P)\n\ \\H not a space or tab (?<X>...) capturing, named X (-P)\n\ \\s a whitespace except \\n \\1 matches group 1 (-P)\n\ \\S a non-whitespace \\g{10} matches group 10 (-P)\n\@@ -14696,8 +14737,8 @@ Character context on a matching line before or after a match is output when\n\ -------------------------------------- --------------------------------------\n\ (-P): pattern requires option -P\n\ \n\-Option -P enables Perl regex matching with Unicode patterns, Unicode word\n\-boundary matching, lookarounds and capturing groups.\n\+Option -P enables Perl regex matching with Unicode patterns, lookarounds and\n\+capturing groups.\n\ \n\ Option -U disables full Unicode pattern matching: non-POSIX Unicode character\n\ classes \\p{class} are disabled, ASCII, LATIN1 and binary regex patterns only.\n\
@@ -38,7 +38,7 @@ #define UGREP_HPP // DO NOT ALTER THIS LINE: updated by makemake.sh and we need it physically here for MSVC++ build from source-#define UGREP_VERSION "6.5.0"+#define UGREP_VERSION "7.0.0" // disable mmap because mmap is almost always slower than the file reading speed improvements since 3.0.0 #define WITH_NO_MMAP