250618.1 · eada75555a2bc033559b182f334e0406bc54a641
released 7.5
smaller and faster with extended dual predict-match PM3+PM5 algorithms; plus feature requests: fix #491 fix #493 fix #495
reading declarations
@@ -4120,10 +4120,10 @@ in markdown: -b, --byte-offset The offset in bytes of a pattern match is displayed in front of- the respective matched line. When -u is specified, displays the- offset for each pattern matched on the same line. Byte offsets- are exact for ASCII, UTF-8 and raw binary input. Otherwise, the- byte offset in the UTF-8 normalized input is displayed.+ the respective matched line. When -u or --ungroup is specified,+ displays the offset for each pattern matched on the same line.+ Byte offsets are exact for ASCII, UTF-8 and raw binary input.+ Otherwise, the offset in the UTF-8-normalized input is displayed. --binary-files=TYPE Controls searching and reporting pattern matches in binary files.@@ -4135,8 +4135,9 @@ in markdown: problematic consequences if the terminal driver interprets some of it as commands. `hex' reports all matches in hexadecimal. `with-hex' only reports binary matches in hexadecimal, leaving- text matches alone. A match is considered binary when matching a- zero byte or invalid UTF. Short options are -a, -I, -U, -W and+ text matches alone. Files having NUL (zero) bytes are binary and+ files with invalid UTF encoding are binary unless option -U or+ --ascii or --binary is specified. Short options are -a, -I, -W, -X. --bool, -%, -%%@@ -4272,9 +4273,9 @@ in markdown: --encoding=ENCODING The encoding format of the input. The default ENCODING is binary or UTF-8 which are treated the same. Therefore, --encoding=binary- has no effect. Note that option -U or --binary specifies binary- PATTERN matching (text matching is the default). ENCODING can be:- `binary', `ASCII', `UTF-8', `UTF-16', `UTF-16BE', `UTF-16LE',+ has no effect. Contrast this with option -U or --ascii or+ --binary that specifies raw binary PATTERN matching. ENCODING can+ be: `binary', `ASCII', `UTF-8', `UTF-16', `UTF-16BE', `UTF-16LE', `UTF-32', `UTF-32BE', `UTF-32LE', `LATIN1', `ISO-8859-1', `ISO-8859-2', `ISO-8859-3', `ISO-8859-4', `ISO-8859-5', `ISO-8859-6', `ISO-8859-7', `ISO-8859-8', `ISO-8859-9',@@ -4456,7 +4457,9 @@ in markdown: -I, --ignore-binary Ignore matches in binary files. This option is equivalent to the- --binary-files=without-match option.+ --binary-files=without-match option. Files having NUL (zero)+ bytes are binary. Also files with invalid UTF encoding are binary+ unless option -U or --ascii or --binary is specified. -i, --ignore-case Perform case insensitive matching. By default, ugrep is case@@ -4531,8 +4534,8 @@ in markdown: that the start-up time to search may be increased when complex search patterns are specified that contain large Unicode character classes combined with `*' or `+' repeats, which should be avoided.- Option -U or --ascii improves performance. Option --stats- displays an index search report.+ Option -U or --ascii or --binary improves performance. Option+ --stats displays an index search report. -J NUM, --jobs=NUM Specifies the number of threads spawned to search files. By@@ -4827,10 +4830,10 @@ in markdown: -U, --ascii, --binary Disables Unicode matching for ASCII and binary matching. PATTERN- matches bytes, not Unicode characters. For example, -U '\xa3'- matches byte A3 (hex) instead of the Unicode code point U+00A3- represented by the UTF-8 sequence C2 A3. See also option- --dotall.+ matches bytes. For example, -U '\xa3' matches byte A3 (hex)+ instead of the Unicode code point U+00A3 represented by the UTF-8+ sequence C2 A3. Input is not flagged as "binary" for having+ invalid UTF, only for having NUL (zero) bytes. -u, --ungroup Do not group multiple pattern matches on the same matched line.@@ -4922,8 +4925,7 @@ in markdown: formats: gzip (.gz), compress (.Z), zip, 7z, bzip2 (.bz, .bz2, .bzip2, .tbz, .tbz2, .tb2, .tz2), xz (.xz, .txz) and lzma (requires suffix .lzma, .tlz), zstd (.zst, .zstd, .tzst), lz4- (requires suffix .lz4), brotli (requires suffix .br), bzip3- (requires suffix .bz3).+ (requires suffix .lz4), brotli (requires suffix .br). --zmax=NUM When used with option -z or --decompress, searches the contents of@@ -5512,7 +5514,7 @@ in markdown: - ugrep 7.4.3 May 15, 2025 UGREP(1)+ ugrep 7.5.0 June 18, 2025 UGREP(1) 🔝 [Back to table of contents](#toc)
@@ -1,6 +1,6 @@ #! /bin/sh # Guess values for system-dependent variables and create Makefiles.-# Generated by GNU Autoconf 2.72 for ugrep 7.4.3.+# Generated by GNU Autoconf 2.72 for ugrep 7.5.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='7.4.3'-PACKAGE_STRING='ugrep 7.4.3'+PACKAGE_VERSION='7.5.0'+PACKAGE_STRING='ugrep 7.5.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 7.4.3 to adapt to many kinds of systems.+'configure' configures ugrep 7.5.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 7.4.3:";;+ short | recursive ) echo "Configuration of ugrep 7.5.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 7.4.3+ugrep configure 7.5.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 7.4.3, which was+It was created by ugrep $as_me 7.5.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='7.4.3'+ VERSION='7.5.0' printf "%s\n" "#define PACKAGE \"$PACKAGE\"" >>confdefs.h@@ -11808,7 +11808,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 7.4.3, which was+This file was extended by ugrep $as_me 7.5.0, which was generated by GNU Autoconf 2.72. Invocation command line was CONFIG_FILES = $CONFIG_FILES@@ -11881,7 +11881,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 7.4.3+ugrep config.status 7.5.0 configured by $0, generated by GNU Autoconf 2.72, with options \\"\$ac_cs_config\\"
@@ -1,4 +1,4 @@-AC_INIT([ugrep],[7.4.3],[https://github.com/Genivia/ugrep/issues],[ugrep],[https://ugrep.com])+AC_INIT([ugrep],[7.5.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-2025 Robert van Engelen, Genivia Inc.])
@@ -44,6 +44,7 @@ #define REFLEX_OVERRIDE override #endif +/// Optimize (un)likely branches #if defined(__GNUC__) || defined(__clang__) #define REFLEX_LIKELY(x) __builtin_expect(!!(x), 1) #define REFLEX_UNLIKELY(x) __builtin_expect(!!(x), 0)
@@ -1344,104 +1344,76 @@ class Matcher : public PatternMatcher<reflex::Pattern> { // Single needle SSE2/NEON methods bool advance_pattern_pin1_one(size_t loc); bool advance_pattern_pin1_pma(size_t loc);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- 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);- template <uint8_t MIN> bool advance_pattern_min4(size_t loc);+ bool advance_pattern_mink(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);- bool advance_char_pmh(size_t loc); // Few chars methods template <uint8_t LEN> bool advance_chars(size_t loc); template <uint8_t LEN> bool advance_chars_pma(size_t loc);- template <uint8_t LEN> bool advance_chars_pmh(size_t loc); // Few chars AVX2 methods template <uint8_t LEN> bool simd_advance_chars_avx2(size_t loc); template <uint8_t LEN> bool simd_advance_chars_pma_avx2(size_t loc);- template <uint8_t LEN> bool simd_advance_chars_pmh_avx2(size_t loc); // Few chars AVX512BW methods template <uint8_t LEN> bool simd_advance_chars_avx512bw(size_t loc); template <uint8_t LEN> bool simd_advance_chars_pma_avx512bw(size_t loc);- template <uint8_t LEN> bool simd_advance_chars_pmh_avx512bw(size_t loc); // String methods bool advance_string(size_t loc); bool advance_string_pma(size_t loc);- bool advance_string_pmh(size_t loc); // String AVX2 metnods bool simd_advance_string_avx2(size_t loc); bool simd_advance_string_pma_avx2(size_t loc);- bool simd_advance_string_pmh_avx2(size_t loc); // String AVX512BW metnods bool simd_advance_string_avx512bw(size_t loc); bool simd_advance_string_pma_avx512bw(size_t loc);- bool simd_advance_string_pmh_avx512bw(size_t loc); // String NEON metnods bool simd_advance_string_neon(const char *& s, const char *e); bool simd_advance_string_pma_neon(const char *& s, const char *e);- bool simd_advance_string_pmh_neon(const char *& s, const char *e); // Fallback Boyer-Moore methods bool advance_string_bm(size_t loc); bool advance_string_bm_pma(size_t loc);- bool advance_string_bm_pmh(size_t loc); #if !defined(WITH_NO_INDENT) /// Update indentation column counter for indent() and dedent(). inline void newline()
@@ -64,6 +64,10 @@ // ugrep 3.7.0b: use a DFA as a tree to bypass DFA construction step when possible #define WITH_TREE_DFA +// Predict-match PM3+PM5 or PM4+PM4 chains (default PM4), benchmarking results favor PM3+PM5+#define WITH_PM3_PM5+// #define WITH_PM4_PM4+ #if (defined(__WIN32__) || defined(_WIN32) || defined(WIN32) || defined(_WIN64) || defined(__BORLANDC__)) && !defined(__CYGWIN__) && !defined(__MINGW32__) && !defined(__MINGW64__) # pragma warning( disable : 4290 ) #endif@@ -75,8 +79,8 @@ 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 uint8_t Bitap; ///< bitap bitmask, unsigned 8, 16 or 32 bit for 8, 16 or 32 BITS (number of characters matched)+ typedef uint16_t Pred; ///< predict match bits for PM3+PM5 or PM4+PM4 to store 2x8 bits 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@@ -90,9 +94,19 @@ class Pattern { 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+ static const Hash HASH = 0x2000; ///< size of the predict match array (16K bytes)+ static const Hash BTAP = 0x4000; ///< size of the bitap hashed character pairs array (16K bytes)+ static const Bitap BITS = 8; ///< number of bitap bits <= 8*sizeof(Bitap) >= PM_M, may change in a future update+#if defined(WITH_PM3_PM5)+ static const Pred PM_K = 3; ///< first predict-match step+ static const Pred PM_M = 8; ///< total predict-match length 3+5 of PM3+PM5+#elif defined(WITH_PM4_PM4)+ static const Pred PM_K = 4; ///< first predict-match step+ static const Pred PM_M = 8; ///< total predict-match length 4+4 of PM4+PM4+#else+ static const Pred PM_K = 4; ///< first predict-match step+ static const Pred PM_M = 4; ///< total predict-match length 4 of PM4+#endif }; /// Construct an unset pattern. Pattern()@@ -362,30 +376,76 @@ class Pattern { { return ams_; }- /// Returns true when match is predicted, based on s[0..3..e-1] (e >= s + 4 and n >= 4).- inline bool predict_match(const char *s, size_t n) const- {- 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)+#if defined(WITH_PM3_PM5)+ /// Returns true when match is predicted using my PM3+PM5 logic for min>=1.+ inline bool predict_match(const char *s) const+ {+ 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]);+ uint32_t h1 = hash(c0, c1);+ uint32_t h2 = hash(h1, c2);+ Pred p0 = (pma_[c0] & 0xc000) | (pma_[h1] & 0x3000) | (pma_[h2] & 0x0c00);+ Pred m0 = ((((p0 >> 2) | p0) >> 1) | p0);+ if (m0 >= 0xfc00) return false;- const char *e = s + n - 3;- uint32_t m = 16;- while (++s < e)- {- h = hash(h, static_cast<uint8_t>(*s));- f |= pmh_[h] & m;- m <<= 1;- }- return f == 0;+ if (m0 != 0xf680)+ return true;+ uint8_t c3 = static_cast<uint8_t>(s[3]);+ uint8_t c4 = static_cast<uint8_t>(s[4]);+ uint8_t c5 = static_cast<uint8_t>(s[5]);+ uint8_t c6 = static_cast<uint8_t>(s[6]);+ uint8_t c7 = static_cast<uint8_t>(s[7]);+ uint32_t h3 = hash(h2, c3);+ uint32_t h4 = hash(h3, c4);+ uint32_t h5 = hash(h4, c5);+ uint32_t h6 = hash(h5, c6);+ uint32_t h7 = hash(h6, c7);+ Pred p1 = (pma_[h3] & 0x0300) | (pma_[h4] & 0x00c0) | (pma_[h5] & 0x0030) | (pma_[h6] & 0x000c) | (pma_[h7] & 0x0003);+ Pred m1 = ((((((((p1 >> 2) | p1) >> 2) | p1) >> 2) | p1) >> 1) | p1);+ return m1 != 0x03ff; }- /// Returns true when match is predicted using my PM4 logic.+ /// Returns true when match is predicted using my PM3 logic for min>=1 prior to PM3+PM5.+ inline bool predict_match_quick(const char *s) const+ {+ 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]);+ uint32_t h1 = hash(c0, c1);+ uint32_t h2 = hash(h1, c2);+ Pred p0 = (pma_[c0] & 0xc000) | (pma_[h1] & 0x3000) | (pma_[h2] & 0x0c00);+ Pred m0 = ((((p0 >> 2) | p0) >> 1) | p0);+ return m0 < 0xfc00;+ }+ /// Returns true when match is predicted using my PM3+PM5 logic for min>=3.+ inline bool predict_match_min(const char *s) const+ {+ 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]);+ uint32_t h1 = hash(c0, c1);+ uint32_t h2 = hash(h1, c2);+ Pred p0 = (pma_[c0] & 0x4000) | (pma_[h1] & 0x1000) | (pma_[h2] & 0x0400);+ if (p0 > 0x0400)+ return false;+ if (p0 == 0)+ return true;+ uint8_t c3 = static_cast<uint8_t>(s[3]);+ uint8_t c4 = static_cast<uint8_t>(s[4]);+ uint8_t c5 = static_cast<uint8_t>(s[5]);+ uint8_t c6 = static_cast<uint8_t>(s[6]);+ uint8_t c7 = static_cast<uint8_t>(s[7]);+ uint32_t h3 = hash(h2, c3);+ uint32_t h4 = hash(h3, c4);+ uint32_t h5 = hash(h4, c5);+ uint32_t h6 = hash(h5, c6);+ uint32_t h7 = hash(h6, c7);+ Pred p1 = (pma_[h3] & 0x0300) | (pma_[h4] & 0x00c0) | (pma_[h5] & 0x0030) | (pma_[h6] & 0x000c) | (pma_[h7] & 0x0003);+ Pred m1 = ((((((((p1 >> 2) | p1) >> 2) | p1) >> 2) | p1) >> 1) | p1);+ return m1 != 0x03ff;+ }+#elif defined(WITH_PM4_PM4)+ /// Returns true when match is predicted using my PM4+PM4 logic for min>=1. inline bool predict_match(const char *s) const { uint8_t c0 = static_cast<uint8_t>(s[0]);@@ -395,10 +455,99 @@ class Pattern { 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;+ Pred p0 = (pma_[c0] & 0xc000) | (pma_[h1] & 0x3000) | (pma_[h2] & 0x0c00) | (pma_[h3] & 0x0300);+ Pred m0 = ((((((p0 >> 2) | p0) >> 2) | p0) >> 1) | p0);+ if (m0 >= 0xff00)+ return false;+ if (m0 != 0xfde8)+ return true;+ uint8_t c4 = static_cast<uint8_t>(s[4]);+ uint8_t c5 = static_cast<uint8_t>(s[5]);+ uint8_t c6 = static_cast<uint8_t>(s[6]);+ uint8_t c7 = static_cast<uint8_t>(s[7]);+ uint32_t h4 = hash(h3, c4);+ uint32_t h5 = hash(h4, c5);+ uint32_t h6 = hash(h5, c6);+ uint32_t h7 = hash(h6, c7);+ Pred p1 = (pma_[h4] & 0x00c0) | (pma_[h5] & 0x0030) | (pma_[h6] & 0x000c) | (pma_[h7] & 0x0003);+ Pred m1 = ((((((p1 >> 2) | p1) >> 2) | p1) >> 1) | p1);+ return m1 != 0x00ff;+ }+ /// Returns true when match is predicted using my PM4 logic for min>=1 prior to PM4+PM4.+ inline bool predict_match_quick(const char *s) const+ {+ 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 p0 = (pma_[c0] & 0xc000) | (pma_[h1] & 0x3000) | (pma_[h2] & 0x0c00) | (pma_[h3] & 0x0300);+ Pred m0 = ((((((p0 >> 2) | p0) >> 2) | p0) >> 1) | p0);+ return m0 < 0xff00;+ }+ /// Returns true when match is predicted using my PM4+PM4 logic for min>=4.+ inline bool predict_match_min(const char *s) const+ {+ 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 p0 = (pma_[c0] & 0x4000) | (pma_[h1] & 0x1000) | (pma_[h2] & 0x0400) | (pma_[h3] & 0x0300);+ if (p0 > 0x0100)+ return false;+ if (p0 == 0)+ return true;+ uint8_t c4 = static_cast<uint8_t>(s[4]);+ uint8_t c5 = static_cast<uint8_t>(s[5]);+ uint8_t c6 = static_cast<uint8_t>(s[6]);+ uint8_t c7 = static_cast<uint8_t>(s[7]);+ uint32_t h4 = hash(h3, c4);+ uint32_t h5 = hash(h4, c5);+ uint32_t h6 = hash(h5, c6);+ uint32_t h7 = hash(h6, c7);+ Pred p1 = (pma_[h4] & 0x00c0) | (pma_[h5] & 0x0030) | (pma_[h6] & 0x000c) | (pma_[h7] & 0x0003);+ Pred m1 = ((((((p1 >> 2) | p1) >> 2) | p1) >> 1) | p1);+ return m1 != 0x00ff;+ }+#else+ /// Returns true when match is predicted using my PM4 logic for min>=1.+ inline bool predict_match(const char *s) const+ {+ 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 p0 = (pma_[c0] & 0xc000) | (pma_[h1] & 0x3000) | (pma_[h2] & 0x0c00) | (pma_[h3] & 0x0300);+ Pred m0 = ((((((p0 >> 2) | p0) >> 2) | p0) >> 1) | p0);+ return m0 < 0xff00;+ }+ /// Returns true when match is predicted (not used)+ inline bool predict_match_quick(const char *) const+ {+ return true;+ }+ /// Returns true when match is predicted using my PM4 logic for min>=4.+ inline bool predict_match_min(const char *s) const+ {+ 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 p0 = (pma_[c0] & 0x4000) | (pma_[h1] & 0x1000) | (pma_[h2] & 0x0400) | (pma_[h3] & 0x0300);+ return p0 <= 0x0100; }+#endif /// Relative frequency of English letters with upper/lower-case ratio = 0.0563, punctuation and UTF-8 bytes. static uint8_t frequency(uint8_t c) {@@ -745,7 +894,7 @@ class Pattern { } bool find_accepting() {- while (!done())+ while (!done() && !accepting()) { ++edge; walk();@@ -1069,7 +1218,7 @@ class Pattern { void gen_min(std::set<DFA::State*>& states); void gen_predict_match(std::set<DFA::State*>& states); 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_predict_match_transitions(uint16_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);@@ -1273,15 +1422,15 @@ class Pattern { { return static_cast<unsigned char>(c & ~0x20); }- /// predict match hash 0 <= hash() < Const::HASH.+ /// predict match hash 0 <= hash() < Const::HASH, must be additive: hash(h,b+1) = hash(h,b)+1 modulo Const::HASH. static inline uint32_t hash(uint32_t h, uint8_t b) {- return ((h << 3) ^ b) & (Const::HASH - 1);+ return ((h << 3) - h + b) & (Const::HASH - 1); }- /// bitap character pairs hash+ /// bitap character pairs hash. static inline uint32_t bihash(uint8_t a, uint8_t b) {- return (a ^ (b << 6)) & (Const::BTAP - 1);+ return (a ^ (static_cast<uint32_t>(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 uint32_t indexhash(Hash h, uint8_t b)@@ -1299,16 +1448,16 @@ class Pattern { std::string rex_; ///< regular expression string std::vector<Location> end_; ///< entries point to the subpattern's ending '|' or '\0' std::vector<bool> acc_; ///< true if subpattern n is accepting (state is reachable)- size_t vno_; ///< number of finite state machine vertices |V| (nodes)- size_t eno_; ///< number of finite state machine edges |E| (arrows)- size_t hno_; ///< number of indexing hash tables (HFA edges)+ uint32_t vno_; ///< number of finite state machine vertices |V| (nodes)+ uint32_t eno_; ///< number of finite state machine edges |E| (arrows)+ uint32_t hno_; ///< number of indexing hash tables (HFA edges) 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 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+ uint16_t len_; ///< length of chr_[], less or equal to 255+ uint16_t min_; ///< patterns after the prefix are at least this long but no more than Const::BITS+ uint16_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@@ -1319,13 +1468,12 @@ class Pattern { 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+ Pred pma_[Const::HASH]; ///< predict-match 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 uint16_t lcs_; ///< secondary least common character position in the pattern or 0xffff- size_t bmd_; ///< Boyer-Moore jump distance on mismatch, B-M is enabled when bmd_ > 0 (<= 255)+ uint16_t bmd_; ///< Boyer-Moore jump distance on mismatch, B-M is enabled when bmd_ > 0 (<= 255) uint8_t bms_[256]; ///< Boyer-Moore skip array float pms_; ///< ms elapsed time to parse regex float vms_; ///< ms elapsed time to compile DFA vertices
@@ -47,7 +47,11 @@ # define fseeko _fseeki64 #else # include <unistd.h> // off_t, fstat()-# include <sys/select.h>+# if (defined(__WIN32__) || defined(_WIN32) || defined(WIN32) || defined(_WIN64)) && (defined(__MINGW32__) || defined(__MINGW64__)) && defined(_UCRT)+# include <winsock2.h>+# else+# include <sys/select.h>+# endif #endif namespace reflex {
@@ -751,47 +751,10 @@ redo: // 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+ if (pat_->min_ <= 1) \+ adv_ = &Matcher::advance_pattern_pin##PIN##_one; \+ else \+ adv_ = &Matcher::advance_pattern_pin##PIN##_pma; /// Initialize specialized pattern search methods to advance the engine to a possible match void Matcher::init_advance()@@ -806,32 +769,10 @@ void Matcher::init_advance() switch (pat_->pin_) { case 1:- 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;- }+ if (pat_->min_ <= 1)+ adv_ = &Matcher::advance_pattern_pin1_one;+ else+ adv_ = &Matcher::advance_pattern_pin1_pma; break; #if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2) || defined(HAVE_NEON) case 2:@@ -861,38 +802,18 @@ void Matcher::init_advance() { case 0: case 1:- if (pat_->npy_ <= MAX_PATTERN_MIN1_NPY)- adv_ = &Matcher::advance_pattern_min1;- else- adv_ = &Matcher::advance_pattern_pma;+ adv_ = &Matcher::advance_pattern_min1; break; case 2:- if (pat_->npy_ <= MAX_PATTERN_MIN2_NPY)- adv_ = &Matcher::advance_pattern_min2;- else- adv_ = &Matcher::advance_pattern_pma;+ adv_ = &Matcher::advance_pattern_min2; break;+#if !defined(WITH_PM3_PM5) case 3:- if (pat_->npy_ <= MAX_PATTERN_MIN3_NPY)- adv_ = &Matcher::advance_pattern_min3;- 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>;+ adv_ = &Matcher::advance_pattern_min3; break;+#endif+ default:+ adv_ = &Matcher::advance_pattern_mink; } } }@@ -900,46 +821,36 @@ void Matcher::init_advance() { if (pat_->min_ == 0) adv_ = &Matcher::advance_char;- else if (pat_->min_ < 4)- adv_ = &Matcher::advance_char_pma; else- adv_ = &Matcher::advance_char_pmh;+ adv_ = &Matcher::advance_char_pma; } else if (pat_->len_ == 2) { if (pat_->min_ == 0) adv_ = &Matcher::advance_chars<2>;- else if (pat_->min_ < 4)- adv_ = &Matcher::advance_chars_pma<2>; else- adv_ = &Matcher::advance_chars_pmh<2>;+ adv_ = &Matcher::advance_chars_pma<2>; } else if (pat_->len_ == 3) { if (pat_->min_ == 0) adv_ = &Matcher::advance_chars<3>;- else if (pat_->min_ < 4)- adv_ = &Matcher::advance_chars_pma<3>; else- adv_ = &Matcher::advance_chars_pmh<3>;+ adv_ = &Matcher::advance_chars_pma<3>; } else if (pat_->bmd_ == 0) {- if (pat_->min_ >= 4)- adv_ = &Matcher::advance_string_pmh;- else if (pat_->min_ > 0)- adv_ = &Matcher::advance_string_pma;- else+ if (pat_->min_ == 0) adv_ = &Matcher::advance_string;+ else+ adv_ = &Matcher::advance_string_pma; } else {- if (pat_->min_ >= 4)- adv_ = &Matcher::advance_string_bm_pmh;- else if (pat_->min_ > 0)- adv_ = &Matcher::advance_string_bm_pma;- else+ if (pat_->min_ == 0) adv_ = &Matcher::advance_string_bm;+ else+ adv_ = &Matcher::advance_string_bm_pma; } #if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) // AVX2 runtime optimized function callback overrides@@ -971,7 +882,7 @@ bool Matcher::advance_pattern_pin1_one(size_t loc) if (s < e && (s = static_cast<const char*>(std::memchr(s, chr0, e - s))) != NULL) { loc = s - buf_;- if (s > e - 4 || pat_->predict_match(s))+ if (REFLEX_UNLIKELY(s > e - Pattern::Const::PM_M) || pat_->predict_match(s)) { set_current(loc); return true;@@ -989,11 +900,11 @@ bool Matcher::advance_pattern_pin1_one(size_t loc) } } -/// My homegrown "needle search" method when needle pin=1 and min=2 or 3+/// My homegrown "needle search" method when needle pin=1 bool Matcher::advance_pattern_pin1_pma(size_t loc) { const char *chr = pat_->chr_;- const size_t min = pat_->min_;+ const uint16_t min = pat_->min_; const uint16_t lcp = pat_->lcp_; const uint16_t lcs = pat_->lcs_; const char chr0 = chr[0];@@ -1016,7 +927,7 @@ bool Matcher::advance_pattern_pin1_pma(size_t loc) { uint32_t offset = ctz(mask); size_t k = s - lcp + offset - buf_;- if (k + 4 > end_ || pat_->predict_match(&buf_[k]))+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) { set_current(k); return true;@@ -1048,7 +959,7 @@ bool Matcher::advance_pattern_pin1_pma(size_t loc) { if ((mask & 0xff)) {- if (k + 4 > end_ || pat_->predict_match(&buf_[k]))+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) { set_current(k); return true;@@ -1071,7 +982,7 @@ bool Matcher::advance_pattern_pin1_pma(size_t loc) { if ((mask & 0xff)) {- if (k + 4 > end_ || pat_->predict_match(&buf_[k]))+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) { set_current(k); return true;@@ -1089,7 +1000,7 @@ bool Matcher::advance_pattern_pin1_pma(size_t loc) { s -= lcp; loc = s - buf_;- if (s > e - 4 || (s[lcs] == chr1 && pat_->predict_match(s)))+ if (REFLEX_UNLIKELY(s > e - Pattern::Const::PM_M) || (s[lcs] == chr1 && pat_->predict_match(s))) { set_current(loc); return true;@@ -1108,125 +1019,6 @@ bool Matcher::advance_pattern_pin1_pma(size_t loc) } } -/// 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_;- const uint16_t lcp = pat_->lcp_;- const uint16_t lcs = pat_->lcs_;- const int chr0 = chr[0];- const int chr1 = chr[1];- while (true)- {- const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - MIN + 1;-#if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2)- __m128i vlcp = _mm_set1_epi8(chr0);- __m128i vlcs = _mm_set1_epi8(chr1);- while (s <= e - 16)- {- __m128i vstrlcp = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s));- __m128i vstrlcs = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s + lcs - lcp));- __m128i veqlcp = _mm_cmpeq_epi8(vlcp, vstrlcp);- __m128i veqlcs = _mm_cmpeq_epi8(vlcs, vstrlcs);- uint32_t mask = _mm_movemask_epi8(_mm_and_si128(veqlcp, veqlcs));- while (REFLEX_UNLIKELY(mask != 0))- {- uint32_t offset = ctz(mask);- size_t k = s - lcp + offset - buf_;- if (pat_->predict_match(&buf_[k], MIN))- {- set_current(k);- return true;- }- mask &= mask - 1;- }- s += 16;- }-#elif defined(HAVE_NEON)- uint8x16_t vlcp = vdupq_n_u8(chr0);- uint8x16_t vlcs = vdupq_n_u8(chr1);- while (s <= e - 16)- {- uint8x16_t vstrlcp = vld1q_u8(reinterpret_cast<const uint8_t*>(s));- uint8x16_t vstrlcs = vld1q_u8(reinterpret_cast<const uint8_t*>(s + lcs - lcp));- uint8x16_t vmasklcp8 = vceqq_u8(vlcp, vstrlcp);- uint8x16_t vmasklcs8 = vceqq_u8(vlcs, vstrlcs);- uint64x2_t vmask64 = vreinterpretq_u64_u8(vandq_u8(vmasklcp8, vmasklcs8));- uint64_t mask = vgetq_lane_u64(vmask64, 0);- if (REFLEX_UNLIKELY(mask != 0))- {- size_t k = s - lcp - buf_;- if (static_cast<uint32_t>(mask) == 0)- {- mask >>= 32;- k += 4;- }- do- {- if ((mask & 0xff))- {- if (pat_->predict_match(&buf_[k], MIN))- {- set_current(k);- return true;- }- }- mask >>= 8;- ++k;- } while (mask != 0);- }- mask = vgetq_lane_u64(vmask64, 1);- if (REFLEX_UNLIKELY(mask != 0))- {- size_t k = s - lcp + 8 - buf_;- if (static_cast<uint32_t>(mask) == 0)- {- mask >>= 32;- k += 4;- }- do- {- if ((mask & 0xff))- {- if (pat_->predict_match(&buf_[k], MIN))- {- set_current(k);- return true;- }- }- mask >>= 8;- ++k;- } while (mask != 0);- }- s += 16;- }-#endif- 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 + MIN > e || (s[lcs] == chr1 && pat_->predict_match(s, MIN)))- {- set_current(loc);- return true;- }- ++loc;- }- else- {- if (e > buf_ + loc + lcp)- loc = e - buf_ - lcp;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + MIN > end_ && eof_)- return false;- }- }-}- #if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2) /// My homegrown "needle search" methods for pins with min=0 or 1@@ -1249,7 +1041,7 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ { \ uint32_t offset = ctz(mask); \ size_t k = s + offset - buf_; \- if (k + 4 > end_ || pat_->predict_match(&buf_[k])) \+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) \ { \ set_current(k); \ return true; \@@ -1258,7 +1050,7 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ } \ s += 16; \ } \- while (s < e - 3) \+ while (s < e - (Pattern::Const::PM_M - 1)) \ { \ if (pat_->predict_match(s++)) \ { \@@ -1270,7 +1062,7 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ loc = s - buf_; \ set_current_and_peek_more(loc); \ loc = cur_; \- if (loc + 3 >= end_) \+ if (loc + (Pattern::Const::PM_M - 1) >= end_) \ return true; \ } \ }@@ -1366,12 +1158,12 @@ ADV_PAT_PIN_ONE(8, \ veq = _mm_or_si128(veq, _mm_cmpeq_epi8(v7, vstr)); \ ) -/// My homegrown "needle search" methods for pins with min=2 or 3 (pma) and min>=4 (pmh)+/// My homegrown "needle search" methods for pins #define ADV_PAT_PIN(N, INIT, COMP) \ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ { \ const char *chr = pat_->chr_; \- const size_t min = pat_->min_; \+ const uint16_t min = pat_->min_; \ const uint16_t lcp = pat_->lcp_; \ const uint16_t lcs = pat_->lcs_; \ INIT \@@ -1391,7 +1183,7 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ { \ uint32_t offset = ctz(mask); \ size_t k = s - lcp + offset - buf_; \- if (k + min + 3 > end_ || pat_->predict_match(&buf_[k])) \+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) \ { \ set_current(k); \ return true; \@@ -1401,7 +1193,7 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ s += 16; \ } \ s -= lcp; \- e = buf_ + end_ - 3; \+ e = buf_ + end_ - (Pattern::Const::PM_M - 1); \ while (s < e) \ { \ if (pat_->predict_match(s++)) \@@ -1416,60 +1208,9 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ loc = cur_; \ if (loc + min > end_ && eof_) \ return false; \- if (loc + 3 >= end_) \+ if (loc + (Pattern::Const::PM_M - 1) >= end_) \ return true; \ } \-} \-\-template <uint8_t MIN> \-bool Matcher::advance_pattern_pin##N##_pmh(size_t loc) \-{ \- const char *chr = pat_->chr_; \- const uint16_t lcp = pat_->lcp_; \- const uint16_t lcs = pat_->lcs_; \- INIT \- while (true) \- { \- const char *s = buf_ + loc + lcp; \- const char *e = buf_ + end_ + lcp - MIN + 1; \- while (s <= e - 16) \- { \- __m128i vstrlcp = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s)); \- __m128i vstrlcs = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s + lcs - lcp)); \- __m128i veqlcp = _mm_cmpeq_epi8(vlcp0, vstrlcp); \- __m128i veqlcs = _mm_cmpeq_epi8(vlcs0, vstrlcs); \- COMP \- uint32_t mask = _mm_movemask_epi8(_mm_and_si128(veqlcp, veqlcs)); \- while (REFLEX_UNLIKELY(mask != 0)) \- { \- uint32_t offset = ctz(mask); \- size_t k = s - lcp + offset - buf_; \- if (pat_->predict_match(&buf_[k], MIN)) \- { \- set_current(k); \- return true; \- } \- mask &= mask - 1; \- } \- s += 16; \- } \- s -= lcp; \- e = buf_ + end_ - MIN + 1; \- while (s < e) \- { \- if (pat_->predict_match(s++, MIN)) \- { \- size_t k = s - buf_ - 1; \- set_current(k); \- return true; \- } \- } \- loc = s - buf_; \- set_current_and_peek_more(loc); \- loc = cur_; \- if (loc + MIN > end_ && eof_) \- return false; \- } \ } ADV_PAT_PIN(2, \@@ -1656,7 +1397,7 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ { \ if ((mask & 0xff) != 0) \ { \- if (k + 4 > end_ || pat_->predict_match(&buf_[k])) \+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) \ { \ set_current(k); \ return true; \@@ -1679,7 +1420,7 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ { \ if ((mask & 0xff) != 0) \ { \- if (k + 4 > end_ || pat_->predict_match(&buf_[k])) \+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) \ { \ set_current(k); \ return true; \@@ -1691,7 +1432,7 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ } \ s += 16; \ } \- while (s < e - 3) \+ while (s < e - (Pattern::Const::PM_M - 1)) \ { \ if (pat_->predict_match(s++)) \ { \@@ -1703,7 +1444,7 @@ bool Matcher::advance_pattern_pin##N##_one(size_t loc) \ loc = s - buf_; \ set_current_and_peek_more(loc); \ loc = cur_; \- if (loc + 3 >= end_) \+ if (loc + (Pattern::Const::PM_M - 1) >= end_) \ return true; \ } \ }@@ -1838,12 +1579,12 @@ ADV_PAT_PIN_ONE(8, \ vceqq_u8(v7, vstr)); \ ) -/// My homegrown "needle search" methods for pins with min=2 or 3 (pma) and min>=4 (pmh)+/// My homegrown "needle search" methods for pins #define ADV_PAT_PIN(N, INIT, COMP) \ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ { \ const char *chr = pat_->chr_; \- const size_t min = pat_->min_; \+ const uint16_t min = pat_->min_; \ const uint16_t lcp = pat_->lcp_; \ const uint16_t lcs = pat_->lcs_; \ INIT \@@ -1870,7 +1611,7 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ { \ if ((mask & 0xff) != 0) \ { \- if (k + 4 > end_ || pat_->predict_match(&buf_[k])) \+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) \ { \ set_current(k); \ return true; \@@ -1893,7 +1634,7 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ { \ if ((mask & 0xff) != 0) \ { \- if (k + 4 > end_ || pat_->predict_match(&buf_[k])) \+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) \ { \ set_current(k); \ return true; \@@ -1906,7 +1647,7 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ s += 16; \ } \ s -= lcp; \- e = buf_ + end_ - 3; \+ e = buf_ + end_ - (Pattern::Const::PM_M - 1); \ while (s < e) \ { \ if (pat_->predict_match(s++)) \@@ -1921,93 +1662,9 @@ bool Matcher::advance_pattern_pin##N##_pma(size_t loc) \ loc = cur_; \ if (loc + min > end_ && eof_) \ return false; \- if (loc + 3 >= end_) \+ if (loc + (Pattern::Const::PM_M - 1) >= end_) \ return true; \ } \-} \-\-template <uint8_t MIN> \-bool Matcher::advance_pattern_pin##N##_pmh(size_t loc) \-{ \- const char *chr = pat_->chr_; \- const uint16_t lcp = pat_->lcp_; \- const uint16_t lcs = pat_->lcs_; \- INIT \- while (true) \- { \- const char *s = buf_ + loc + lcp; \- const char *e = buf_ + end_ + lcp - MIN + 1; \- while (s <= e - 16) \- { \- uint8x16_t vstrlcp = vld1q_u8(reinterpret_cast<const uint8_t*>(s)); \- uint8x16_t vstrlcs = vld1q_u8(reinterpret_cast<const uint8_t*>(s + lcs - lcp)); \- COMP \- uint64x2_t vmask64 = vreinterpretq_u64_u8(vandq_u8(vmasklcp8, vmasklcs8)); \- uint64_t mask = vgetq_lane_u64(vmask64, 0); \- if (REFLEX_UNLIKELY(mask != 0)) \- { \- size_t k = s - lcp - buf_; \- if (static_cast<uint32_t>(mask) == 0) \- { \- mask >>= 32; \- k += 4; \- } \- do \- { \- if ((mask & 0xff) != 0) \- { \- if (k + 4 > end_ || pat_->predict_match(&buf_[k])) \- { \- set_current(k); \- return true; \- } \- } \- mask >>= 8; \- ++k; \- } while (mask != 0); \- } \- mask = vgetq_lane_u64(vmask64, 1); \- if (REFLEX_UNLIKELY(mask != 0)) \- { \- size_t k = s - lcp + 8 - buf_; \- if (static_cast<uint32_t>(mask) == 0) \- { \- mask >>= 32; \- k += 4; \- } \- do \- { \- if ((mask & 0xff) != 0) \- { \- if (k + 4 > end_ || pat_->predict_match(&buf_[k])) \- { \- set_current(k); \- return true; \- } \- } \- mask >>= 8; \- ++k; \- } while (mask != 0); \- } \- s += 16; \- } \- s -= lcp; \- e = buf_ + end_ - MIN + 1; \- while (s < e) \- { \- if (pat_->predict_match(s++, MIN)) \- { \- size_t k = s - buf_ - 1; \- set_current(k); \- return true; \- } \- } \- loc = s - buf_; \- set_current_and_peek_more(loc); \- loc = cur_; \- if (loc + MIN > end_ && eof_) \- return false; \- } \ } ADV_PAT_PIN(2, \@@ -2244,14 +1901,14 @@ ADV_PAT_PIN(8, \ #endif -/// Minimal 1 byte long patterns with min=0 or 1 using 4-way bitap hashed pairs then PM4+/// Minimal 1 byte long patterns with min=0 or 1 using 4-way bitap hashed pairs and PM bool Matcher::advance_pattern_min1(size_t loc) {- const Pattern::Pred *tap = pat_->tap_;+ const Pattern::Bitap *tap = pat_->tap_; while (true) { const char *s = buf_ + loc;- const char *e = buf_ + end_ - 4;+ const char *e = buf_ + end_ - (Pattern::Const::PM_M + 2); uint8_t c0 = static_cast<uint8_t>(buf_[loc]); while (s < e) {@@ -2259,66 +1916,73 @@ bool Matcher::advance_pattern_min1(size_t loc) 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))+ if ((!(tap[Pattern::bihash(c0, c1)] & 1) && pat_->predict_match_quick(&s[0])) ||+ (!(tap[Pattern::bihash(c1, c2)] & 1) && pat_->predict_match_quick(&s[1])) ||+ (!(tap[Pattern::bihash(c2, c3)] & 1) && pat_->predict_match_quick(&s[2])) ||+ (!(tap[Pattern::bihash(c3, c4)] & 1) && pat_->predict_match_quick(&s[3]))) break; c0 = c4; s += 4; } if (s < e) {- if (!pat_->predict_match(s) &&- ++s <= e && !pat_->predict_match(s) &&- ++s <= e && !pat_->predict_match(s) &&- ++s <= e && !pat_->predict_match(s))+ if (pat_->predict_match(s++) ||+ pat_->predict_match(s++) ||+ pat_->predict_match(s++) ||+ pat_->predict_match(s++)) {- loc = s - buf_ + 1;- continue;+ size_t k = s - buf_ - 1;+ set_current(k);+ return true; }- size_t k = s - buf_;- set_current(k);- return true;+ loc = s - buf_; }- loc = s - buf_;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + 4 >= end_)+ else {- s = buf_ + loc;- e = buf_ + end_;- while (s < e)+ loc = s - buf_;+ set_current_and_peek_more(loc);+ loc = cur_;+ if (loc + Pattern::Const::PM_M + 2 >= end_) {- uint8_t c1 = s + 1 < e ? static_cast<uint8_t>(s[1]) : 0;- if (!(tap[Pattern::bihash(c0, c1)] & 1))- break;- c0 = c1;- ++s;+ s = buf_ + loc;+ e = buf_ + end_;+ c0 = static_cast<uint8_t>(s[0]);+ while (s < e)+ {+ uint8_t c1 = s + 1 < e ? static_cast<uint8_t>(s[1]) : 0;+ if (!(tap[Pattern::bihash(c0, c1)] & 1))+ {+ size_t k = s - buf_;+ set_current(k);+ return true;+ }+ c0 = c1;+ ++s;+ }+ loc = s - buf_;+ set_current(loc);+ return false; }- loc = s - buf_;- set_current(loc);- return loc + 1 <= end_; } } } -/// Minimal 2 byte long patterns with min=2 using bitap hashed pairs and PM4+/// Minimal 2 byte long patterns with min=2 using bitap hashed pairs then PM bool Matcher::advance_pattern_min2(size_t loc) {- const Pattern::Pred *tap = pat_->tap_;+ const Pattern::Bitap *tap = pat_->tap_; uint32_t state = ~0; while (true) { const char *s = buf_ + loc;- const char *e = buf_ + end_ - 1;+ const char *e = buf_ + end_ - (Pattern::Const::PM_M - 1); uint8_t c0 = static_cast<uint8_t>(*s); while (s < e) { 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)))+ if ((state & 2) == 0 && pat_->predict_match(s - 2)) { size_t k = s - buf_ - 2; set_current(k);@@ -2329,37 +1993,56 @@ bool Matcher::advance_pattern_min2(size_t loc) size_t m = std::min<size_t>(1, loc); // to clamp loc - 1 set_current_and_peek_more(loc - m); // clamp loc - 1 loc = cur_ + m;- if (loc + 1 >= end_ && eof_)+ if (loc + (Pattern::Const::PM_M - 1) >= end_ && eof_) {+ // keep going, we may have matches in the last bytes+ s = buf_ + loc;+ e = buf_ + end_ - 1;+ c0 = static_cast<uint8_t>(s[0]);+ while (s < e)+ {+ uint8_t c1 = static_cast<uint8_t>(*++s);+ state = (state << 1) | tap[Pattern::bihash(c0, c1)];+ c0 = c1;+ if ((state & 2) == 0)+ {+ size_t k = s - buf_ - 2;+ set_current(k);+ return true;+ }+ } uint8_t c1 = 0; // reached the end state = (state << 1) | tap[Pattern::bihash(c0, c1)]; if ((state & 2) == 0) {- set_current(loc - 1);+ size_t k = s - buf_ - 1;+ set_current(k); return true; }+ loc = s - buf_; set_current(loc); return false; } } } -/// Minimal 3 byte long pattern with min=3 using bitap hashed pairs and PM4+#if !defined(WITH_PM3_PM5)+/// Minimal 3 byte long pattern with min=3 using bitap hashed pairs then PM4+PM4 bool Matcher::advance_pattern_min3(size_t loc) {- const Pattern::Pred *tap = pat_->tap_;+ const Pattern::Bitap *tap = pat_->tap_; uint32_t state = ~0; while (true) { const char *s = buf_ + loc;- const char *e = buf_ + end_ - 1;+ const char *e = buf_ + end_ - (Pattern::Const::PM_M - 2); uint8_t c0 = static_cast<uint8_t>(*s); while (s < e) { 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)))+ if ((state & 4) == 0 && pat_->predict_match(s - 3)) { size_t k = s - buf_ - 3; set_current(k);@@ -2370,33 +2053,53 @@ bool Matcher::advance_pattern_min3(size_t loc) size_t m = std::min<size_t>(2, loc); // to clamp loc - 2 set_current_and_peek_more(loc - m); // clamp loc - 2 loc = cur_ + m;- if (loc + 1 >= end_ && eof_)+ if (loc + (Pattern::Const::PM_M - 2) >= end_ && eof_) {+ // keep going, we may have matches in the last bytes+ s = buf_ + loc;+ e = buf_ + end_ - 1;+ c0 = static_cast<uint8_t>(s[0]);+ while (s < e)+ {+ uint8_t c1 = static_cast<uint8_t>(*++s);+ state = (state << 1) | tap[Pattern::bihash(c0, c1)];+ c0 = c1;+ if ((state & 4) == 0)+ {+ size_t k = s - buf_ - 3;+ set_current(k);+ return true;+ }+ } uint8_t c1 = 0; // reached the end state = (state << 1) | tap[Pattern::bihash(c0, c1)]; if ((state & 4) == 0) {- set_current(loc - 2);+ size_t k = s - buf_ - 2;+ set_current(k); return true; }+ loc = s - buf_; set_current(loc); return false; } } }+#endif -/// 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)+/// Minimal k byte long patterns (MIN>=k) using bitap hashed pairs and PMk+PMx+bool Matcher::advance_pattern_mink(size_t loc) {- const Pattern::Pred *tap = pat_->tap_;+ const Pattern::Bitap *tap = pat_->tap_;+ const uint16_t min = pat_->min_;+ const uint16_t sub = (min < Pattern::Const::PM_M + 2 ? Pattern::Const::PM_M + 2 - min : 0);+ const uint32_t mask = 1 << (min - 1); uint32_t state1 = ~0; uint32_t state2 = ~0;- uint32_t mask = 1 << (MIN - 1);- const char *s = buf_ + loc;- const char *e = buf_ + end_ - 2; while (true) {+ const char *s = buf_ + loc;+ const char *e = buf_ + end_ - sub; uint8_t c0 = static_cast<uint8_t>(*s); while (s < e) {@@ -2404,34 +2107,55 @@ bool Matcher::advance_pattern_min4(size_t loc) 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 && pat_->predict_match_min(s - min - 1)) {- size_t k = s - buf_ - MIN - 1;+ size_t k = s - buf_ - min - 1; set_current(k); return true; }- if ((state1 & mask) == 0 && pat_->predict_match(s - MIN, MIN))+ if ((state1 & mask) == 0 && pat_->predict_match_min(s - min)) {- size_t k = s - buf_ - MIN;+ size_t k = s - buf_ - min; set_current(k); return true; } }- size_t ahead = s - buf_;- size_t m = std::min<size_t>(MIN - 1, ahead); // to clamp ahead - MIN + 1- set_current_and_peek_more(ahead - m); // clamp ahead - MIN + 1- s = buf_ + cur_ + m;- e = buf_ + end_ - 2;- if (s >= e && eof_)+ loc = s - buf_;+ size_t m = std::min<size_t>(min - 1, loc); // to clamp loc - min + 1+ set_current_and_peek_more(loc - m); // clamp loc - min + 1+ loc = cur_ + m;+ if (loc + sub >= end_ && eof_) {- c0 = static_cast<uint8_t>(*s);+ // keep going, we may have a match in the last bytes+ s = buf_ + loc;+ e = buf_ + end_ - 2;+ c0 = static_cast<uint8_t>(s[0]);+ while (s < e)+ {+ 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)+ {+ size_t k = s - buf_ - min - 1;+ set_current(k);+ return true;+ }+ if ((state1 & mask) == 0)+ {+ size_t k = s - buf_ - min;+ set_current(k);+ return true;+ }+ } if (s == e + 1) { uint8_t c1 = 0; // reached the end state2 = (state1 << 1) | tap[Pattern::bihash(c0, c1)];- if ((state2 & mask) == 0 && pat_->predict_match(s - MIN + 1, MIN))+ if ((state2 & mask) == 0) {- size_t k = s - buf_ - MIN + 1;+ size_t k = s - buf_ - min + 1; set_current(k); return true; }@@ -2442,52 +2166,26 @@ bool Matcher::advance_pattern_min4(size_t loc) state2 = (state1 << 1) | tap[Pattern::bihash(c0, c1)]; c0 = 0; // reached the end state1 = (state2 << 1) | tap[Pattern::bihash(c1, c0)];- if ((state2 & mask) == 0 && pat_->predict_match(s - MIN, MIN))+ if ((state2 & mask) == 0) {- size_t k = s - buf_ - MIN;+ size_t k = s - buf_ - min; set_current(k); return true; }- if ((state1 & mask) == 0 && pat_->predict_match(s - MIN + 1, MIN))+ if ((state1 & mask) == 0) {- size_t k = s - buf_ - MIN + 1;+ size_t k = s - buf_ - min + 1; set_current(k); return true; } }- set_current(ahead);+ loc = s - buf_;+ set_current(loc); return false; } } } -/// Minimal 1 byte long pattern with min=0 or 1 using PM4-bool Matcher::advance_pattern_pma(size_t loc)-{- while (true)- {- const char *s = buf_ + loc;- const char *e = buf_ + end_;- while (s < e - 6)- {- if (pat_->predict_match(s++) ||- pat_->predict_match(s++) ||- pat_->predict_match(s++) ||- pat_->predict_match(s++))- {- size_t k = s - buf_ - 1;- set_current(k);- return true;- }- }- loc = s - buf_;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + 6 >= end_)- return advance_pattern_min1(loc);- }-}- /// One char bool Matcher::advance_char(size_t loc) {@@ -2511,7 +2209,7 @@ bool Matcher::advance_char(size_t loc) } } -/// One char followed by 1 to 4 characters+/// One char followed by some pattern bool Matcher::advance_char_pma(size_t loc) { const char chr0 = pat_->chr_[0];@@ -2523,38 +2221,7 @@ bool Matcher::advance_char_pma(size_t loc) if (s != NULL) { loc = s - buf_;- if (s > e - 5 || pat_->predict_match(s + 1))- {- set_current(loc);- return true;- }- ++loc;- }- else- {- loc = e - buf_;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + 1 > end_ && eof_)- return false;- }- }-}--/// One char followed by 4 to 8 characters-bool Matcher::advance_char_pmh(size_t loc)-{- const char chr0 = pat_->chr_[0];- const size_t min = pat_->min_;- while (true)- {- const char *s = buf_ + loc;- const char *e = buf_ + end_;- s = static_cast<const char*>(std::memchr(s, chr0, e - s));- if (s != NULL)- {- loc = s - buf_;- if (s + 1 + min > e || pat_->predict_match(s + 1, min))+ if (REFLEX_UNLIKELY(s > e - Pattern::Const::PM_M - 1) || pat_->predict_match(s + 1)) { set_current(loc); return true;@@ -2692,147 +2359,14 @@ bool Matcher::advance_chars(size_t loc) } } -/// Few (2 or 3) chars followed by 1 to 4 characters+/// Few (2 or 3) chars followed by a pattern template<uint8_t LEN> bool Matcher::advance_chars_pma(size_t loc) { const uint16_t lcp = 0; const uint16_t lcs = LEN - 1; const char *chr = pat_->chr_;- const size_t min = pat_->min_;- while (true)- {- const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - LEN - min + 1;-#if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2)- __m128i vlcp = _mm_set1_epi8(chr[lcp]);- __m128i vlcs = _mm_set1_epi8(chr[lcs]);- while (s <= e - 16)- {- __m128i vlcpm = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s));- __m128i vlcsm = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s + lcs - lcp));- __m128i vlcpeq = _mm_cmpeq_epi8(vlcp, vlcpm);- __m128i vlcseq = _mm_cmpeq_epi8(vlcs, vlcsm);- uint32_t mask = _mm_movemask_epi8(_mm_and_si128(vlcpeq, vlcseq));- while (REFLEX_UNLIKELY(mask != 0))- {- 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 - 1) == 0))- {- size_t k = s - lcp + offset - buf_;- if (k + LEN + 4 > end_ || pat_->predict_match(&buf_[k + LEN]))- {- set_current(k);- return true;- }- }- mask &= mask - 1;- }- s += 16;- }-#elif defined(HAVE_NEON)- uint8x16_t vlcp = vdupq_n_u8(chr[lcp]);- uint8x16_t vlcs = vdupq_n_u8(chr[lcs]);- while (s <= e - 16)- {- uint8x16_t vlcpm = vld1q_u8(reinterpret_cast<const uint8_t*>(s));- uint8x16_t vlcsm = vld1q_u8(reinterpret_cast<const uint8_t*>(s) + lcs - lcp);- uint8x16_t vlcpeq = vceqq_u8(vlcp, vlcpm);- uint8x16_t vlcseq = vceqq_u8(vlcs, vlcsm);- uint8x16_t vmask8 = vandq_u8(vlcpeq, vlcseq);- uint64x2_t vmask64 = vreinterpretq_u64_u8(vmask8);- uint64_t mask = vgetq_lane_u64(vmask64, 0);- if (REFLEX_UNLIKELY(mask != 0))- {- size_t k = s - lcp - buf_;- if (static_cast<uint32_t>(mask) == 0)- {- mask >>= 32;- k += 4;- }- do- {- if ((mask & 0xff) &&- (LEN == 2 ||- (LEN == 3 ? buf_[k + 1] == chr[1] : std::memcmp(&buf_[k + 1], chr + 1, LEN - 1) == 0)))- {- if (k + LEN + 4 > end_ || pat_->predict_match(&buf_[k + LEN]))- {- set_current(k);- return true;- }- }- mask >>= 8;- ++k;- } while (mask != 0);- }- mask = vgetq_lane_u64(vmask64, 1);- if (REFLEX_UNLIKELY(mask != 0))- {- size_t k = s - lcp + 8 - buf_;- if (static_cast<uint32_t>(mask) == 0)- {- mask >>= 32;- k += 4;- }- do- {- if ((mask & 0xff) &&- (LEN == 2 ||- (LEN == 3 ? buf_[k + 1] == chr[1] : std::memcmp(&buf_[k + 1], chr + 1, LEN - 1) == 0)))- {- if (k + LEN + 4 > end_ || pat_->predict_match(&buf_[k + LEN]))- {- set_current(k);- return true;- }- }- mask >>= 8;- ++k;- } while (mask != 0);- }- s += 16;- }-#endif- while (s < e)- {- do- s = static_cast<const char*>(std::memchr(s, chr[lcp], e - s));- while (s != NULL && s[lcs - lcp] != chr[lcs] && ++s < e);- if (s == NULL || s >= e)- {- s = e;- break;- }- if (LEN == 2 ||- (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 1) == 0))- {- size_t k = s - lcp - buf_;- if (k + LEN + 4 > end_ || pat_->predict_match(&buf_[k + LEN]))- {- set_current(k);- return true;- }- }- ++s;- }- loc = s - lcp - buf_;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + LEN + min > end_ && eof_)- return false;- }-}--/// Few (2 or 3) chars followed by 4 to 8 characters-template<uint8_t LEN>-bool Matcher::advance_chars_pmh(size_t loc)-{- const uint16_t lcp = 0;- const uint16_t lcs = LEN - 1;- const char *chr = pat_->chr_;- const size_t min = pat_->min_;+ const uint16_t min = pat_->min_; while (true) { const char *s = buf_ + loc + lcp;@@ -2854,7 +2388,7 @@ bool Matcher::advance_chars_pmh(size_t loc) (LEN == 3 ? s[offset + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + offset, chr + 1, LEN - 1) == 0)) { size_t k = s - lcp + offset - buf_;- if (pat_->predict_match(&buf_[k + LEN], min))+ if (REFLEX_UNLIKELY(k + LEN + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + LEN])) { set_current(k); return true;@@ -2890,7 +2424,7 @@ bool Matcher::advance_chars_pmh(size_t loc) (LEN == 2 || (LEN == 3 ? buf_[k + 1] == chr[1] : std::memcmp(&buf_[k + 1], chr + 1, LEN - 1) == 0))) {- if (pat_->predict_match(&buf_[k + LEN], min))+ if (REFLEX_UNLIKELY(k + LEN + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + LEN])) { set_current(k); return true;@@ -2915,7 +2449,7 @@ bool Matcher::advance_chars_pmh(size_t loc) (LEN == 2 || (LEN == 3 ? buf_[k + 1] == chr[1] : std::memcmp(&buf_[k + 1], chr + 1, LEN - 1) == 0))) {- if (pat_->predict_match(&buf_[k + LEN], min))+ if (REFLEX_UNLIKELY(k + LEN + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + LEN])) { set_current(k); return true;@@ -2942,7 +2476,7 @@ bool Matcher::advance_chars_pmh(size_t loc) (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 1) == 0)) { size_t k = s - lcp - buf_;- if (pat_->predict_match(&buf_[k + LEN], min))+ if (REFLEX_UNLIKELY(k + LEN + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + LEN])) { set_current(k); return true;@@ -2962,7 +2496,7 @@ bool Matcher::advance_chars_pmh(size_t loc) bool Matcher::advance_string(size_t loc) { const char *chr = pat_->chr_;- const size_t len = pat_->len_;+ const uint16_t len = pat_->len_; uint16_t lcp = pat_->lcp_; uint16_t lcs = pat_->lcs_; while (true)@@ -3028,8 +2562,8 @@ bool Matcher::advance_string(size_t loc) bool Matcher::advance_string_pma(size_t loc) { const char *chr = pat_->chr_;- const size_t len = pat_->len_;- const size_t min = pat_->min_;+ const uint16_t len = pat_->len_;+ const uint16_t min = pat_->min_; const uint16_t lcp = pat_->lcp_; const uint16_t lcs = pat_->lcs_; while (true)@@ -3053,7 +2587,7 @@ bool Matcher::advance_string_pma(size_t loc) if (std::memcmp(s - lcp + offset, chr, len) == 0) { size_t k = s - lcp + offset - buf_;- if (k + len + 4 > end_ || pat_->predict_match(&buf_[k + len]))+ if (REFLEX_UNLIKELY(k + len + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + len])) { set_current(k); return true;@@ -3081,80 +2615,7 @@ bool Matcher::advance_string_pma(size_t loc) if (std::memcmp(s - lcp, chr, len) == 0) { size_t k = s - lcp - buf_;- if (k + len + 4 > end_ || pat_->predict_match(&buf_[k + len]))- {- set_current(k);- return true;- }- }- ++s;- }- loc = s - lcp - buf_;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + len + min > end_ && eof_)- return false;- }-}--/// String followed by 4 to 8 characters-bool Matcher::advance_string_pmh(size_t loc)-{- const char *chr = pat_->chr_;- const size_t len = pat_->len_;- const size_t min = pat_->min_;- const uint16_t lcp = pat_->lcp_;- const uint16_t lcs = pat_->lcs_;- while (true)- {- const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - len - min + 1;-#if defined(HAVE_AVX512BW) || defined(HAVE_AVX2) || defined(HAVE_SSE2)- // implements SSE2 string search scheme based on http://0x80.pl/articles/simd-friendly-karp-rabin.html- __m128i vlcp = _mm_set1_epi8(chr[lcp]);- __m128i vlcs = _mm_set1_epi8(chr[lcs]);- while (s <= e - 16)- {- __m128i vlcpm = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s));- __m128i vlcsm = _mm_loadu_si128(reinterpret_cast<const __m128i*>(s + lcs - lcp));- __m128i vlcpeq = _mm_cmpeq_epi8(vlcp, vlcpm);- __m128i vlcseq = _mm_cmpeq_epi8(vlcs, vlcsm);- uint32_t mask = _mm_movemask_epi8(_mm_and_si128(vlcpeq, vlcseq));- while (REFLEX_UNLIKELY(mask != 0))- {- uint32_t offset = ctz(mask);- if (std::memcmp(s - lcp + offset, chr, len) == 0)- {- size_t k = s - lcp + offset - buf_;- if (pat_->predict_match(&buf_[k + len], min))- {- set_current(k);- return true;- }- }- mask &= mask - 1;- }- s += 16;- }-#elif defined(HAVE_NEON)- // slightly faster when abstracted into a routine- if (simd_advance_string_pmh_neon(s, e))- return true;-#endif- while (s < e)- {- do- s = static_cast<const char*>(std::memchr(s, chr[lcp], e - s));- while (s != NULL && s[lcs - lcp] != chr[lcs] && ++s < e);- if (s == NULL || s >= e)- {- s = e;- break;- }- if (std::memcmp(s - lcp, chr, len) == 0)- {- size_t k = s - lcp - buf_;- if (pat_->predict_match(&buf_[k + len], min))+ if (REFLEX_UNLIKELY(k + len + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + len])) { set_current(k); return true;@@ -3177,7 +2638,7 @@ bool Matcher::simd_advance_string_neon(const char *& s, const char *e) { const uint16_t lcp = pat_->lcp_; const uint16_t lcs = pat_->lcs_;- const size_t len = pat_->len_;+ const uint16_t len = pat_->len_; const char *chr = pat_->chr_; uint8x16_t vlcp = vdupq_n_u8(chr[lcp]); uint8x16_t vlcs = vdupq_n_u8(chr[lcs]);@@ -3239,7 +2700,7 @@ bool Matcher::simd_advance_string_pma_neon(const char *& s, const char *e) { const uint16_t lcp = pat_->lcp_; const uint16_t lcs = pat_->lcs_;- const size_t len = pat_->len_;+ const uint16_t len = pat_->len_; const char *chr = pat_->chr_; uint8x16_t vlcp = vdupq_n_u8(chr[lcp]); uint8x16_t vlcs = vdupq_n_u8(chr[lcs]);@@ -3264,7 +2725,7 @@ bool Matcher::simd_advance_string_pma_neon(const char *& s, const char *e) { if ((mask & 0xff) && std::memcmp(&buf_[k], chr, len) == 0) {- if (k + len + 4 > end_ || pat_->predict_match(&buf_[k + len]))+ if (REFLEX_UNLIKELY(k + len + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + len])) { set_current(k); return true;@@ -3287,76 +2748,7 @@ bool Matcher::simd_advance_string_pma_neon(const char *& s, const char *e) { if ((mask & 0xff) && std::memcmp(&buf_[k], chr, len) == 0) {- if (k + len + 4 > end_ || pat_->predict_match(&buf_[k + len]))- {- set_current(k);- return true;- }- }- mask >>= 8;- ++k;- } while (mask != 0);- }- s += 16;- }- return false;-}--// 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_pmh_neon(const char *& s, const char *e)-{- const uint16_t lcp = pat_->lcp_;- const uint16_t lcs = pat_->lcs_;- const size_t len = pat_->len_;- const 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]);- while (s <= e - 16)- {- uint8x16_t vlcpm = vld1q_u8(reinterpret_cast<const uint8_t*>(s));- uint8x16_t vlcsm = vld1q_u8(reinterpret_cast<const uint8_t*>(s) + lcs - lcp);- uint8x16_t vlcpeq = vceqq_u8(vlcp, vlcpm);- uint8x16_t vlcseq = vceqq_u8(vlcs, vlcsm);- uint8x16_t vmask8 = vandq_u8(vlcpeq, vlcseq);- uint64x2_t vmask64 = vreinterpretq_u64_u8(vmask8);- uint64_t mask = vgetq_lane_u64(vmask64, 0);- if (REFLEX_UNLIKELY(mask != 0))- {- size_t k = s - lcp - buf_;- if (static_cast<uint32_t>(mask) == 0)- {- mask >>= 32;- k += 4;- }- do- {- if ((mask & 0xff) && std::memcmp(&buf_[k], chr, len) == 0)- {- if (pat_->predict_match(&buf_[k + len], min))- {- set_current(k);- return true;- }- }- mask >>= 8;- ++k;- } while (mask != 0);- }- mask = vgetq_lane_u64(vmask64, 1);- if (REFLEX_UNLIKELY(mask != 0))- {- size_t k = s - lcp + 8 - buf_;- if (static_cast<uint32_t>(mask) == 0)- {- mask >>= 32;- k += 4;- }- do- {- if ((mask & 0xff) && std::memcmp(&buf_[k], chr, len) == 0)- {- if (pat_->predict_match(&buf_[k + len], min))+ if (REFLEX_UNLIKELY(k + len + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + len])) { set_current(k); return true;@@ -3378,8 +2770,8 @@ bool Matcher::advance_string_bm(size_t loc) { const char *chr = pat_->chr_; const uint8_t *bms = pat_->bms_;- const size_t len = pat_->len_;- const size_t bmd = pat_->bmd_;+ const uint16_t len = pat_->len_;+ const uint16_t bmd = pat_->bmd_; const uint16_t lcp = pat_->lcp_; while (true) {@@ -3429,73 +2821,13 @@ bool Matcher::advance_string_bm(size_t loc) } } -/// My homegrown improved Boyer-Moore string search followed by 1 to 3 minimal byte long patterns, using PM4+/// My homegrown improved Boyer-Moore string search followed by minimal 1 byte long patterns, using PM bool Matcher::advance_string_bm_pma(size_t loc) { const char *chr = pat_->chr_; const uint8_t *bms = pat_->bms_;- const size_t len = pat_->len_;- const size_t bmd = pat_->bmd_;- const uint16_t lcp = pat_->lcp_;- while (true)- {- const char *s = buf_ + loc + len - 1;- const char *e = buf_ + end_;- const char *t = chr + len - 1;- while (s < e)- {- size_t k = 0;- do- s += k = bms[static_cast<uint8_t>(*s)];- while (k > 0 ? s < e : s[lcp - len + 1] != chr[lcp] && (s += bmd) < e);- if (s >= e)- break;- const char *p = t - 1;- const char *q = s - 1;- while (p >= chr && *p == *q)- {- --p;- --q;- }- if (p < chr)- {- k = q - buf_ + 1;- if (k + len + 4 > end_ || pat_->predict_match(&buf_[k + len]))- {- set_current(k);- return true;- }- }- if (chr + bmd >= p)- {- s += bmd;- }- else- {- k = bms[static_cast<uint8_t>(*q)];- if (p + k > t + bmd)- s += k - (t - p);- else- s += bmd;- }- }- s -= len - 1;- loc = s - buf_;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + len > end_ && eof_)- return false;- }-}--/// 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_;- const uint8_t *bms = pat_->bms_;- const size_t bmd = pat_->bmd_;- const size_t len = pat_->len_;- const size_t min = pat_->min_;+ const uint16_t len = pat_->len_;+ const uint16_t bmd = pat_->bmd_; const uint16_t lcp = pat_->lcp_; while (true) {@@ -3520,7 +2852,7 @@ bool Matcher::advance_string_bm_pmh(size_t loc) if (p < chr) { k = q - buf_ + 1;- if (k + len + min > end_ || pat_->predict_match(&buf_[k + len], min))+ if (REFLEX_UNLIKELY(k + len + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + len])) { set_current(k); return true;
@@ -47,32 +47,10 @@ 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; \- }+ if (pat_->min_ <= 0) \+ adv_ = &Matcher::simd_advance_pattern_pin##PIN##_one_avx2; \+ else \+ adv_ = &Matcher::simd_advance_pattern_pin##PIN##_pma_avx2; // AVX2 runtime optimized function callback overrides void Matcher::simd_init_advance_avx2()@@ -82,28 +60,8 @@ void Matcher::simd_init_advance_avx2() switch (pat_->pin_) { case 1:- 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;- }+ if (pat_->min_ >= 2)+ adv_ = &Matcher::simd_advance_pattern_pin1_pma_avx2; break; case 2: SIMD_INIT_ADV_PAT_PIN_CASE_AVX2(2);@@ -160,28 +118,22 @@ void Matcher::simd_init_advance_avx2() { if (pat_->min_ == 0) adv_ = &Matcher::simd_advance_chars_avx2<2>;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_chars_pma_avx2<2>; else- adv_ = &Matcher::simd_advance_chars_pmh_avx2<2>;+ adv_ = &Matcher::simd_advance_chars_pma_avx2<2>; } else if (pat_->len_ == 3) { if (pat_->min_ == 0) adv_ = &Matcher::simd_advance_chars_avx2<3>;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_chars_pma_avx2<3>; else- adv_ = &Matcher::simd_advance_chars_pmh_avx2<3>;+ adv_ = &Matcher::simd_advance_chars_pma_avx2<3>; } else if (pat_->bmd_ == 0) {- if (pat_->min_ >= 4)- adv_ = &Matcher::simd_advance_string_pmh_avx2;- else if (pat_->min_ > 0)- adv_ = &Matcher::simd_advance_string_pma_avx2;- else+ if (pat_->min_ == 0) adv_ = &Matcher::simd_advance_string_avx2;+ else+ adv_ = &Matcher::simd_advance_string_pma_avx2; } } @@ -189,7 +141,7 @@ void Matcher::simd_init_advance_avx2() bool Matcher::simd_advance_pattern_pin1_pma_avx2(size_t loc) { const char *chr = pat_->chr_;- const size_t min = pat_->min_;+ const uint16_t min = pat_->min_; const uint16_t lcp = pat_->lcp_; const uint16_t lcs = pat_->lcs_; const char chr0 = chr[0];@@ -212,7 +164,7 @@ bool Matcher::simd_advance_pattern_pin1_pma_avx2(size_t loc) uint32_t offset = ctz(mask); size_t k = s - lcp + offset - buf_; set_current(k);- if (k + 4 > end_ || pat_->predict_match(&buf_[k]))+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) return true; mask &= mask - 1; }@@ -223,7 +175,7 @@ bool Matcher::simd_advance_pattern_pin1_pma_avx2(size_t loc) { s -= lcp; loc = s - buf_;- if (s > e - 4 || (s[lcs] == chr1 && pat_->predict_match(s)))+ if (REFLEX_UNLIKELY(s > e - Pattern::Const::PM_M) || (s[lcs] == chr1 && pat_->predict_match(s))) { set_current(loc); return true;@@ -242,63 +194,6 @@ bool Matcher::simd_advance_pattern_pin1_pma_avx2(size_t loc) } } -// 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_;- const uint16_t lcp = pat_->lcp_;- const uint16_t lcs = pat_->lcs_;- const char chr0 = chr[0];- const char chr1 = chr[1];- __m256i vlcp = _mm256_set1_epi8(chr0);- __m256i vlcs = _mm256_set1_epi8(chr1);- while (true)- {- const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - MIN + 1;- while (s <= e - 32)- {- __m256i vstrlcp = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s));- __m256i vstrlcs = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s + lcs - lcp));- __m256i veqlcp = _mm256_cmpeq_epi8(vlcp, vstrlcp);- __m256i veqlcs = _mm256_cmpeq_epi8(vlcs, vstrlcs);- uint32_t mask = _mm256_movemask_epi8(_mm256_and_si256(veqlcp, veqlcs));- while (REFLEX_UNLIKELY(mask != 0))- {- uint32_t offset = ctz(mask);- size_t k = s - lcp + offset - buf_;- set_current(k);- if (pat_->predict_match(&buf_[k], MIN))- return true;- mask &= mask - 1;- }- s += 32;- }- 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 + MIN > e || (s[lcs] == chr1 && pat_->predict_match(s, MIN)))- {- set_current(loc);- return true;- }- ++loc;- }- else- {- if (e > buf_ + loc + lcp)- loc = e - buf_ - lcp;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + MIN > end_ && eof_)- return false;- }- }-}- // 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) \@@ -319,7 +214,7 @@ bool Matcher::simd_advance_pattern_pin##N##_one_avx2(size_t loc) \ { \ uint32_t offset = ctz(mask); \ size_t k = s + offset - buf_; \- if (k + 4 > end_ || pat_->predict_match(&buf_[k])) \+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) \ { \ set_current(k); \ return true; \@@ -328,7 +223,7 @@ bool Matcher::simd_advance_pattern_pin##N##_one_avx2(size_t loc) \ } \ s += 32; \ } \- while (s < e - 3) \+ while (s < e - (Pattern::Const::PM_M - 1)) \ { \ if (pat_->predict_match(s++)) \ { \@@ -340,7 +235,7 @@ bool Matcher::simd_advance_pattern_pin##N##_one_avx2(size_t loc) \ loc = s - buf_; \ set_current_and_peek_more(loc); \ loc = cur_; \- if (loc + 3 >= end_) \+ if (loc + (Pattern::Const::PM_M - 1) >= end_) \ return true; \ } \ }@@ -476,7 +371,7 @@ ADV_PAT_PIN_ONE(16, \ bool Matcher::simd_advance_pattern_pin##N##_pma_avx2(size_t loc) \ { \ const char *chr = pat_->chr_; \- const size_t min = pat_->min_; \+ const uint16_t min = pat_->min_; \ const uint16_t lcp = pat_->lcp_; \ const uint16_t lcs = pat_->lcs_; \ INIT \@@ -496,7 +391,7 @@ bool Matcher::simd_advance_pattern_pin##N##_pma_avx2(size_t loc) \ { \ uint32_t offset = ctz(mask); \ size_t k = s - lcp + offset - buf_; \- if (k + 4 > end_ || pat_->predict_match(&buf_[k])) \+ if (REFLEX_UNLIKELY(k + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k])) \ { \ set_current(k); \ return true; \@@ -506,7 +401,7 @@ bool Matcher::simd_advance_pattern_pin##N##_pma_avx2(size_t loc) \ s += 32; \ } \ s -= lcp; \- e = buf_ + end_ - 3; \+ e = buf_ + end_ - (Pattern::Const::PM_M - 1); \ while (s < e) \ { \ if (pat_->predict_match(s++)) \@@ -521,60 +416,9 @@ bool Matcher::simd_advance_pattern_pin##N##_pma_avx2(size_t loc) \ loc = cur_; \ if (loc + min > end_ && eof_) \ return false; \- if (loc + 3 >= end_) \+ if (loc + (Pattern::Const::PM_M - 1) >= end_) \ return true; \ } \-} \-\-template <uint8_t MIN> \-bool Matcher::simd_advance_pattern_pin##N##_pmh_avx2(size_t loc) \-{ \- const char *chr = pat_->chr_; \- const uint16_t lcp = pat_->lcp_; \- const uint16_t lcs = pat_->lcs_; \- INIT \- while (true) \- { \- const char *s = buf_ + loc + lcp; \- const char *e = buf_ + end_ + lcp - MIN + 1; \- while (s <= e - 32) \- { \- __m256i vstrlcp = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s)); \- __m256i vstrlcs = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s + lcs - lcp)); \- __m256i veqlcp = _mm256_cmpeq_epi8(vlcp0, vstrlcp); \- __m256i veqlcs = _mm256_cmpeq_epi8(vlcs0, vstrlcs); \- COMP \- uint32_t mask = _mm256_movemask_epi8(_mm256_and_si256(veqlcp, veqlcs)); \- while (REFLEX_UNLIKELY(mask != 0)) \- { \- uint32_t offset = ctz(mask); \- size_t k = s - lcp + offset - buf_; \- if (pat_->predict_match(&buf_[k], MIN)) \- { \- set_current(k); \- return true; \- } \- mask &= mask - 1; \- } \- s += 32; \- } \- s -= lcp; \- e = buf_ + end_ - MIN + 1; \- while (s < e) \- { \- if (pat_->predict_match(s++, MIN)) \- { \- size_t k = s - buf_ - 1; \- set_current(k); \- return true; \- } \- } \- loc = s - buf_; \- set_current_and_peek_more(loc); \- loc = cur_; \- if (loc + MIN > end_ && eof_) \- return false; \- } \ } ADV_PAT_PIN(2, \@@ -822,7 +666,7 @@ bool Matcher::simd_advance_pattern_min4_avx2(size_t loc) while (true) { const char *s = buf_ + loc;- const char *e = buf_ + end_ - 3;+ const char *e = buf_ + end_ - 7; while (s < e) { __m128i vc1 = _mm_cvtepu8_epi32(_mm_loadu_si32(reinterpret_cast<const uint32_t*>(s)));@@ -837,25 +681,25 @@ bool Matcher::simd_advance_pattern_min4_avx2(size_t loc) 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))+ if ((mask & 0x00000008) == 0 && pat_->predict_match(s - MIN + 0)) { size_t k = s - buf_ - MIN + 0; set_current(k); return true; }- if ((mask & 0x00000404) == 0 && pat_->predict_match(s - MIN + 1, MIN))+ if ((mask & 0x00000404) == 0 && pat_->predict_match(s - MIN + 1)) { size_t k = s - buf_ - MIN + 1; set_current(k); return true; }- if ((mask & 0x00020202) == 0 && pat_->predict_match(s - MIN + 2, MIN))+ if ((mask & 0x00020202) == 0 && pat_->predict_match(s - MIN + 2)) { size_t k = s - buf_ - MIN + 2; set_current(k); return true; }- if ((mask & 0x01010101) == 0 && pat_->predict_match(s - MIN + 3, MIN))+ if ((mask & 0x01010101) == 0 && pat_->predict_match(s - MIN + 3)) { size_t k = s - buf_ - MIN + 3; set_current(k);@@ -875,8 +719,8 @@ bool Matcher::simd_advance_pattern_min4_avx2(size_t loc) size_t m = std::min<size_t>(MIN, loc); // to clamp loc - MIN set_current_and_peek_more(loc - m); // clamp loc - MIN loc = cur_ + m;- if (loc + 3 >= end_)- return advance_pattern_min4<MIN>(loc - MIN);+ if (loc + 7 >= end_)+ return advance_pattern_min4(loc - MIN); } } @@ -950,7 +794,7 @@ bool Matcher::simd_advance_chars_pma_avx2(size_t loc) const uint16_t lcp = 0; const uint16_t lcs = LEN - 1; const char *chr = pat_->chr_;- const size_t min = pat_->min_;+ const uint16_t min = pat_->min_; while (true) { const char *s = buf_ + loc + lcp;@@ -971,7 +815,7 @@ bool Matcher::simd_advance_chars_pma_avx2(size_t loc) (LEN == 3 ? s[offset + 1 - lcp] : std::memcmp(s + 1 - lcp + offset, chr + 1, LEN - 2) == 0)) { size_t k = s - lcp + offset - buf_;- if (k + LEN + 4 > end_ || pat_->predict_match(&buf_[k + LEN]))+ if (REFLEX_UNLIKELY(k + LEN + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + LEN])) { set_current(k); return true;@@ -995,73 +839,7 @@ bool Matcher::simd_advance_chars_pma_avx2(size_t loc) (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 1) == 0)) { size_t k = s - lcp - buf_;- if (k + LEN + 4 > end_ || pat_->predict_match(&buf_[k + LEN]))- {- set_current(k);- return true;- }- }- ++s;- }- loc = s - lcp - buf_;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + LEN + min > end_ && eof_)- return false;- }-}--/// Few chars followed by 4 minimal char pattern-template<uint8_t LEN>-bool Matcher::simd_advance_chars_pmh_avx2(size_t loc)-{- const uint16_t lcp = 0;- const uint16_t lcs = LEN - 1;- const char *chr = pat_->chr_;- const size_t min = pat_->min_;- while (true)- {- const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - LEN - min + 1;- __m256i vlcp = _mm256_set1_epi8(chr[lcp]);- __m256i vlcs = _mm256_set1_epi8(chr[lcs]);- while (s <= e - 32)- {- __m256i vlcpm = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s));- __m256i vlcsm = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s + lcs - lcp));- __m256i vlcpeq = _mm256_cmpeq_epi8(vlcp, vlcpm);- __m256i vlcseq = _mm256_cmpeq_epi8(vlcs, vlcsm);- uint32_t mask = _mm256_movemask_epi8(_mm256_and_si256(vlcpeq, vlcseq));- while (REFLEX_UNLIKELY(mask != 0))- {- 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))- {- size_t k = s - lcp + offset - buf_;- set_current(k);- if (k + LEN + min > end_ || pat_->predict_match(&buf_[k + LEN], min))- return true;- }- mask &= mask - 1;- }- s += 32;- }- while (s < e)- {- do- s = static_cast<const char*>(std::memchr(s, chr[lcp], e - s));- while (s != NULL && s[lcs - lcp] != chr[lcs] && ++s < e);- if (s == NULL || s >= e)- {- s = e;- break;- }- if (LEN == 2 ||- (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 1) == 0))- {- size_t k = s - lcp - buf_;- if (pat_->predict_match(&buf_[k + LEN], min))+ if (REFLEX_UNLIKELY(k + LEN + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + LEN])) { set_current(k); return true;@@ -1081,7 +859,7 @@ bool Matcher::simd_advance_chars_pmh_avx2(size_t loc) bool Matcher::simd_advance_string_avx2(size_t loc) { const char *chr = pat_->chr_;- const size_t len = pat_->len_;+ const uint16_t len = pat_->len_; const uint16_t lcp = pat_->lcp_; const uint16_t lcs = pat_->lcs_; while (true)@@ -1140,8 +918,8 @@ bool Matcher::simd_advance_string_avx2(size_t loc) bool Matcher::simd_advance_string_pma_avx2(size_t loc) { const char *chr = pat_->chr_;- const size_t len = pat_->len_;- const size_t min = pat_->min_;+ const uint16_t len = pat_->len_;+ const uint16_t min = pat_->min_; const uint16_t lcp = pat_->lcp_; const uint16_t lcs = pat_->lcs_; while (true)@@ -1163,7 +941,7 @@ bool Matcher::simd_advance_string_pma_avx2(size_t loc) if (std::memcmp(s - lcp + offset, chr, len) == 0) { size_t k = s - lcp + offset - buf_;- if (k + len + 4 > end_ || pat_->predict_match(&buf_[k + len]))+ if (REFLEX_UNLIKELY(k + len + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + len])) { set_current(k); return true;@@ -1186,71 +964,7 @@ bool Matcher::simd_advance_string_pma_avx2(size_t loc) if (std::memcmp(s - lcp, chr, len) == 0) { size_t k = s - lcp - buf_;- if (k + len + 4 > end_ || pat_->predict_match(&buf_[k + len]))- {- set_current(k);- return true;- }- }- ++s;- }- loc = s - lcp - buf_;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + len + min > end_ && eof_)- return false;- }-}--/// Implements AVX2 string search scheme based on http://0x80.pl/articles/simd-friendly-karp-rabin.html-bool Matcher::simd_advance_string_pmh_avx2(size_t loc)-{- const char *chr = pat_->chr_;- const size_t len = pat_->len_;- const size_t min = pat_->min_;- const uint16_t lcp = pat_->lcp_;- const uint16_t lcs = pat_->lcs_;- while (true)- {- const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - len - min + 1;- __m256i vlcp = _mm256_set1_epi8(chr[lcp]);- __m256i vlcs = _mm256_set1_epi8(chr[lcs]);- while (s <= e - 32)- {- __m256i vlcpm = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s));- __m256i vlcsm = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(s + lcs - lcp));- __m256i vlcpeq = _mm256_cmpeq_epi8(vlcp, vlcpm);- __m256i vlcseq = _mm256_cmpeq_epi8(vlcs, vlcsm);- uint32_t mask = _mm256_movemask_epi8(_mm256_and_si256(vlcpeq, vlcseq));- while (REFLEX_UNLIKELY(mask != 0))- {- uint32_t offset = ctz(mask);- if (std::memcmp(s - lcp + offset, chr, len) == 0)- {- size_t k = s - lcp + offset - buf_;- set_current(k);- if (k + len + min > end_ || pat_->predict_match(&buf_[k + len], min))- return true;- }- mask &= mask - 1;- }- s += 32;- }- while (s < e)- {- do- s = static_cast<const char*>(std::memchr(s, chr[lcp], e - s));- while (s != NULL && s[lcs - lcp] != chr[lcs] && ++s < e);- if (s == NULL || s >= e)- {- s = e;- break;- }- if (std::memcmp(s - lcp, chr, len) == 0)- {- size_t k = s - lcp - buf_;- if (pat_->predict_match(&buf_[k + len], min))+ if (REFLEX_UNLIKELY(k + len + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + len])) { set_current(k); return true;
@@ -61,28 +61,22 @@ void Matcher::simd_init_advance_avx512bw() { if (pat_->min_ == 0) adv_ = &Matcher::simd_advance_chars_avx512bw<2>;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_chars_pma_avx512bw<2>; else- adv_ = &Matcher::simd_advance_chars_pmh_avx512bw<2>;+ adv_ = &Matcher::simd_advance_chars_pma_avx512bw<2>; } else if (pat_->len_ == 3) { if (pat_->min_ == 0) adv_ = &Matcher::simd_advance_chars_avx512bw<3>;- else if (pat_->min_ < 4)- adv_ = &Matcher::simd_advance_chars_pma_avx512bw<3>; else- adv_ = &Matcher::simd_advance_chars_pmh_avx512bw<3>;+ adv_ = &Matcher::simd_advance_chars_pma_avx512bw<3>; } else if (pat_->bmd_ == 0) {- if (pat_->min_ >= 4)- adv_ = &Matcher::simd_advance_string_pmh_avx512bw;- else if (pat_->min_ > 0)- adv_ = &Matcher::simd_advance_string_pma_avx512bw;- else+ if (pat_->min_ == 0) adv_ = &Matcher::simd_advance_string_avx512bw;+ else+ adv_ = &Matcher::simd_advance_string_pma_avx512bw; } } @@ -152,7 +146,7 @@ bool Matcher::simd_advance_chars_pma_avx512bw(size_t loc) const uint16_t lcp = 0; const uint16_t lcs = LEN - 1; const char *chr = pat_->chr_;- const size_t min = pat_->min_;+ const uint16_t min = pat_->min_; while (true) { const char *s = buf_ + loc + lcp;@@ -171,7 +165,7 @@ bool Matcher::simd_advance_chars_pma_avx512bw(size_t loc) (LEN == 3 ? s[offset + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + offset, chr + 1, LEN - 2) == 0)) { size_t k = s - lcp + offset - buf_;- if (k + LEN + 4 > end_ || pat_->predict_match(&buf_[k + LEN]))+ if (REFLEX_UNLIKELY(k + LEN + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + LEN])) { set_current(k); return true;@@ -195,73 +189,7 @@ bool Matcher::simd_advance_chars_pma_avx512bw(size_t loc) (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 1) == 0)) { size_t k = s - lcp - buf_;- if (k + LEN + 4 > end_ || pat_->predict_match(&buf_[k + LEN]))- {- set_current(k);- return true;- }- }- ++s;- }- loc = s - lcp - buf_;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + LEN + min > end_ && eof_)- return false;- }-}--/// Few chars followed by 4 minimal char pattern-template<uint8_t LEN>-bool Matcher::simd_advance_chars_pmh_avx512bw(size_t loc)-{- const uint16_t lcp = 0;- const uint16_t lcs = LEN - 1;- const char *chr = pat_->chr_;- size_t min = pat_->min_;- while (true)- {- const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - LEN - min + 1;- __m512i vlcp = _mm512_set1_epi8(chr[lcp]);- __m512i vlcs = _mm512_set1_epi8(chr[lcs]);- while (s <= e - 64)- {- __m512i vlcpm = _mm512_loadu_si512(reinterpret_cast<const __m512i*>(s));- __m512i vlcsm = _mm512_loadu_si512(reinterpret_cast<const __m512i*>(s + lcs - lcp));- uint64_t mask = _mm512_cmpeq_epi8_mask(vlcp, vlcpm) & _mm512_cmpeq_epi8_mask(vlcs, vlcsm);- while (REFLEX_UNLIKELY(mask != 0))- {- uint32_t offset = ctzl(mask);- if (LEN == 2 ||- (LEN == 3 ? s[offset + 1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp + offset, chr + 1, LEN - 2) == 0))- {- size_t k = s - lcp + offset - buf_;- if (k + LEN + min > end_ || pat_->predict_match(&buf_[k + LEN], min))- {- set_current(k);- return true;- }- }- mask &= mask - 1;- }- s += 64;- }- while (s < e)- {- do- s = static_cast<const char*>(std::memchr(s, chr[lcp], e - s));- while (s != NULL && s[lcs - lcp] != chr[lcs] && ++s < e);- if (s == NULL || s >= e)- {- s = e;- break;- }- if (LEN == 2 ||- (LEN == 3 ? s[1 - lcp] == chr[1] : std::memcmp(s + 1 - lcp, chr + 1, LEN - 1) == 0))- {- size_t k = s - lcp - buf_;- if (pat_->predict_match(&buf_[k + LEN], min))+ if (REFLEX_UNLIKELY(k + LEN + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + LEN])) { set_current(k); return true;@@ -281,7 +209,7 @@ bool Matcher::simd_advance_chars_pmh_avx512bw(size_t loc) bool Matcher::simd_advance_string_avx512bw(size_t loc) { const char *chr = pat_->chr_;- const size_t len = pat_->len_;+ const uint16_t len = pat_->len_; const uint16_t lcp = pat_->lcp_; const uint16_t lcs = pat_->lcs_; while (true)@@ -338,72 +266,8 @@ bool Matcher::simd_advance_string_avx512bw(size_t loc) bool Matcher::simd_advance_string_pma_avx512bw(size_t loc) { const char *chr = pat_->chr_;- const size_t len = pat_->len_;- const size_t min = pat_->min_;- const uint16_t lcp = pat_->lcp_;- const uint16_t lcs = pat_->lcs_;- while (true)- {- const char *s = buf_ + loc + lcp;- const char *e = buf_ + end_ + lcp - len - min + 1;- __m512i vlcp = _mm512_set1_epi8(chr[lcp]);- __m512i vlcs = _mm512_set1_epi8(chr[lcs]);- while (s <= e - 64)- {- __m512i vlcpm = _mm512_loadu_si512(reinterpret_cast<const __m512i*>(s));- __m512i vlcsm = _mm512_loadu_si512(reinterpret_cast<const __m512i*>(s + lcs - lcp));- uint64_t mask = _mm512_cmpeq_epi8_mask(vlcp, vlcpm) & _mm512_cmpeq_epi8_mask(vlcs, vlcsm);- while (REFLEX_UNLIKELY(mask != 0))- {- uint32_t offset = ctzl(mask);- if (std::memcmp(s - lcp + offset, chr, len) == 0)- {- size_t k = s - lcp + offset - buf_;- if (k + len + 4 > end_ || pat_->predict_match(&buf_[k + len]))- {- set_current(k);- return true;- }- }- mask &= mask - 1;- }- s += 64;- }- while (s < e)- {- do- s = static_cast<const char*>(std::memchr(s, chr[lcp], e - s));- while (s != NULL && s[lcs - lcp] != chr[lcs] && ++s < e);- if (s == NULL || s >= e)- {- s = e;- break;- }- if (std::memcmp(s - lcp, chr, len) == 0)- {- size_t k = s - lcp - buf_;- if (k + len + 4 > end_ || pat_->predict_match(&buf_[k + len]))- {- set_current(k);- return true;- }- }- ++s;- }- loc = s - lcp - buf_;- set_current_and_peek_more(loc);- loc = cur_;- if (loc + len + min > end_ && eof_)- return false;- }-}--/// Implements AVX512BW string search scheme based on http://0x80.pl/articles/simd-friendly-karp-rabin.html-bool Matcher::simd_advance_string_pmh_avx512bw(size_t loc)-{- const char *chr = pat_->chr_;- const size_t len = pat_->len_;- const size_t min = pat_->min_;+ const uint16_t len = pat_->len_;+ const uint16_t min = pat_->min_; const uint16_t lcp = pat_->lcp_; const uint16_t lcs = pat_->lcs_; while (true)@@ -423,7 +287,7 @@ bool Matcher::simd_advance_string_pmh_avx512bw(size_t loc) if (std::memcmp(s - lcp + offset, chr, len) == 0) { size_t k = s - lcp + offset - buf_;- if (k + len + min > end_ || pat_->predict_match(&buf_[k + len], min))+ if (REFLEX_UNLIKELY(k + len + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + len])) { set_current(k); return true;@@ -446,7 +310,7 @@ bool Matcher::simd_advance_string_pmh_avx512bw(size_t loc) if (std::memcmp(s - lcp, chr, len) == 0) { size_t k = s - lcp - buf_;- if (pat_->predict_match(&buf_[k + len], min))+ if (REFLEX_UNLIKELY(k + len + Pattern::Const::PM_M > end_) || pat_->predict_match(&buf_[k + len])) { set_current(k); return true;
@@ -210,50 +210,15 @@ void Pattern::init(const char *options, const uint8_t *pred) 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)- {- // load predict match PM4 pma_[] parameters- for (int i = 0; i < Const::HASH; ++i)- pma_[i] = ~pred[i + n];+ // load tap_[] parameters+ for (int i = 0; i < Const::BTAP; ++i)+ tap_[i] = ~pred[i + n];+ n += Const::BTAP; }- else- {- // load predict match hash pmh_[] parameters- for (int i = 0; i < Const::HASH; ++i)- pmh_[i] = ~pred[i + n];- }- n += Const::HASH;+ // load predict match array pma_[] parameters+ for (int i = 0; i < Const::HASH; ++i)+ pma_[i] = ~pred[2 * i + n] + (~pred[2 * i + n + 1] << 8);+ n += 2 * Const::HASH; if ((pred[1] & 0x20) != 0) { // load lookback parameters lbk_ lbm_ and cbk_[] after s-t cut and first s-t cut pattern characters fst_[]@@ -332,7 +297,7 @@ void Pattern::init(const char *options, const uint8_t *pred) { if (min_ > 0) {- if (min_ < 8)+ if (min_ < Const::BITS) { Bitap mask = ~((1 << min_) - 1); for (Char i = 0; i < 256; ++i)@@ -361,7 +326,7 @@ void Pattern::init(const char *options, const uint8_t *pred) if (have_HW_AVX512BW() || have_HW_AVX2()) { // vectorized bitap hashed pairs array for AVX2- uint32_t shift = 8 - (min_ - 1);+ uint32_t shift = Const::BITS - (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;@@ -396,7 +361,7 @@ void Pattern::init(const char *options, const uint8_t *pred) uint16_t nlcs = 65535; // max and undefined uint16_t freqlcp = 255; // max and undefined uint16_t freqlcs = 255; // max and undefined- size_t min = std::max<size_t>(1, min_);+ uint16_t min = std::max<uint16_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)@@ -405,7 +370,7 @@ void Pattern::init(const char *options, const uint8_t *pred) uint8_t n = 0; uint16_t max = 0; uint16_t sum = 0;- // at position k count the matching characters and find the usm and max character frequency+ // at position k count the matching characters and find the sum and max character frequency for (uint16_t i = 0; i < 256 && n <= pinmax; ++i) { if ((bit_[i] & mask) == 0)@@ -505,7 +470,7 @@ 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 lbk=%u lbm=%u", min, lcp_, lcs_, pin_, nlcp, nlcs, freqlcp, freqlcs, npy_, cut_, lbk_, lbm_);+ DBGLOG("min=%hu lcp=%hu(%hu) pin=%hu nlcp=%hu(%hu) freq=%hu(%hu) npy=%hu cut=%u lbk=%u lbm=%u", min, lcp_, lcs_, pin_, nlcp, nlcs, freqlcp, freqlcs, npy_, cut_, lbk_, lbm_); } else if (len_ > 1) {@@ -594,7 +559,7 @@ void Pattern::init(const char *options, const uint8_t *pred) } } }- DBGLOG("len=%zu min=%zu bmd=%zu lcp=%hu(%hu)", len_, min_, bmd_, lcp_, lcs_);+ DBGLOG("len=%hu min=%hu bmd=%hu lcp=%hu(%hu)", len_, min_, bmd_, lcp_, lcs_); } } @@ -4100,7 +4065,7 @@ void Pattern::analyze_dfa(DFA::State *start) if (cut_depth > 0 || cut_backedge) { cut_ = cut_depth + 1;- std::set<DFA::State*> sweep[8]; // sweep depth 8 is max of min_ (or 16 if HFA uses cuts, but it does not)+ std::set<DFA::State*> sweep[Const::BITS]; // 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@@ -4342,7 +4307,6 @@ void Pattern::analyze_dfa(DFA::State *start) min_ = 0; 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()) {@@ -4360,17 +4324,7 @@ void Pattern::analyze_dfa(DFA::State *start) } for (Hash i = 0; i < Const::HASH; ++i) {- if (pmh_[i] != 0xff)- {- if (isprint(i))- DBGLOGN("pmh['%c'] = %02x", i, pmh_[i]);- else- DBGLOGN("pmh[%3d] = %02x", i, pmh_[i]);- }- }- for (Hash i = 0; i < Const::HASH; ++i)- {- if (pma_[i] != 0xff)+ if (pma_[i] != (1 << (8 * Const::PM_M)) - 1) { if (isprint(i)) DBGLOGN("pma['%c'] = %02x", i, pma_[i]);@@ -4380,14 +4334,14 @@ void Pattern::analyze_dfa(DFA::State *start) } #endif }- DBGLOG("min=%zu len=%zu", min_, len_);+ DBGLOG("min=%hu len=%hu", min_, len_); DBGLOG("END Pattern::analyze_dfa()"); } void Pattern::gen_min(std::set<DFA::State*>& states) {- // find min between 0 and 8- min_ = 8;+ // find min between 0 and Const::BITS+ min_ = Const::BITS; std::set<DFA::State*> prev, next(states); for (size_t level = 0; level < min_; ++level) {@@ -4425,11 +4379,11 @@ void Pattern::gen_min(std::set<DFA::State*>& states) void Pattern::gen_predict_match(std::set<DFA::State*>& states) {- // find min between 0 and 8 then populate bitap and hashes (bounded by min)+ // find min between 0 and Const::BITS then populate bitap and hashes (bounded by min) gen_min(states);- std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > > hashes[8];+ std::map<DFA::State*,std::pair<ORanges<Hash>,ORanges<Char> > > hashes[Const::BITS]; gen_predict_match_start(states, hashes[0]);- for (size_t level = 1; level < std::max<size_t>(min_, 4) && !hashes[level - 1].empty(); ++level)+ for (uint16_t level = 1; level < Const::BITS && !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]); }@@ -4450,16 +4404,15 @@ void Pattern::gen_predict_match_start(std::set<DFA::State*>& states, std::map<DF 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);+ Pred pma_mask = ~(1 << (8 * sizeof(Pred) - 2)); if (next_accept)- mask &= ~(1 << 7);+ pma_mask &= ~(1 << (8 * sizeof(Pred) - 1)); for (Char ch = lo; ch <= hi; ++ch) { bit_[ch] &= ~1;- pmh_[ch] &= ~1;- pma_[ch] &= mask;+ pma_[ch] &= pma_mask; }- // this is the last state to populate bitap+ // this is the first and last state to populate bitap if (min_ <= 1) { if (next_accept)@@ -4492,7 +4445,7 @@ void Pattern::gen_predict_match_start(std::set<DFA::State*>& states, std::map<DF it->second.second = it->second.first; } -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)+void Pattern::gen_predict_match_transitions(uint16_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::MetaEdgesClosure edge(state); !edge.done(); ++edge) {@@ -4500,8 +4453,11 @@ void Pattern::gen_predict_match_transitions(size_t level, DFA::State *state, con // 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;+ // previous level hashes are completely saturated, or highly saturated after 4 levels, then next hashes will be saturated too+ bool next_saturated = (level + 1 > 4 && level + 1 < Const::BITS ? previous.first.count() >= Const::HASH / 8 : previous.first.size() == 1 && previous.first.lo() == 0 && previous.first.hi() == Const::HASH - 1);+ // next state is accepting (closed over metas) 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;+ std::pair<ORanges<Hash>,ORanges<Char> > *next_hashes = (level + 1 < Const::BITS && !next_accept) ? &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" : "");@@ -4523,10 +4479,11 @@ void Pattern::gen_predict_match_transitions(size_t level, DFA::State *state, con 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)+ if (level + 1 < min_) {- // pass character range to the next state- next_hashes->second.insert(lo, hi);+ // pass character range for bitap to the next state+ if (next_hashes != NULL)+ next_hashes->second.insert(lo, hi); } else {@@ -4555,53 +4512,55 @@ void Pattern::gen_predict_match_transitions(size_t level, DFA::State *state, con } } }- if (level < 4)+ if (level < Const::PM_M) {- // 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 || next_accept)- pma_mask &= ~(1 << (7 - 2 * level));- if (next_hashes != NULL)+ // populate predict match hashes+ Pred pma_comb = (level + 1 == Const::PM_K && !next_accept ? 1 << (8 * sizeof(Pred) - 2 * Const::PM_K) : 0);+ Pred pma_mask = ~(1 << (8 * sizeof(Pred) - 2 - 2 * level));+ if (level + 1 == Const::PM_K || level + 1 == Const::PM_M || next_saturated || next_accept)+ pma_mask &= ~(1 << (8 * sizeof(Pred) - 1 - 2 * level));+ if (!next_saturated && next_hashes != NULL) {+ ORanges<Hash>& next_hashes_first = next_hashes->first; 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; for (Hash prev = prev_lo; prev < prev_hi; ++prev) {- for (Char ch = lo; ch <= hi; ++ch)+ Hash lo_h = hash(prev, static_cast<uint8_t>(lo));+ Hash hi_h = hash(prev, static_cast<uint8_t>(hi));+ if (lo_h <= hi_h) {- Hash h = hash(prev, static_cast<uint8_t>(ch));- pmh_[h] &= pmh_mask;- pma_[h] &= pma_mask;- next_hashes->first.insert(h);+ next_hashes_first.insert(lo_h, hi_h);+ for (Hash h = lo_h; h <= hi_h; ++h)+ {+ Pred pma_keep = pma_[h] & pma_comb;+ pma_[h] &= pma_mask;+ pma_[h] |= pma_keep;+ } }- }- }- }- else- {- 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;- for (Hash prev = prev_lo; prev < prev_hi; ++prev)- {- for (Char ch = lo; ch <= hi; ++ch)+ else {- Hash h = hash(prev, static_cast<uint8_t>(ch));- pmh_[h] &= pmh_mask;- pma_[h] &= pma_mask;+ next_hashes_first.insert(lo_h, Const::HASH - 1);+ next_hashes_first.insert(0, hi_h);+ for (Hash h = lo_h; h < Const::HASH; ++h)+ {+ Pred pma_keep = pma_[h] & pma_comb;+ pma_[h] &= pma_mask;+ pma_[h] |= pma_keep;+ }+ for (Hash h = 0; h <= hi_h; ++h)+ {+ Pred pma_keep = pma_[h] & pma_comb;+ pma_[h] &= pma_mask;+ pma_[h] |= pma_keep;+ } } } } }- }- else if (level < min_)- {- uint8_t pmh_mask = ~(1 << level);- if (next_hashes != NULL)+ else { for (ORanges<Hash>::iterator prev_range = previous.first.begin(); prev_range != previous.first.end(); ++prev_range) {@@ -4609,27 +4568,31 @@ void Pattern::gen_predict_match_transitions(size_t level, DFA::State *state, con Hash prev_hi = prev_range->second; for (Hash prev = prev_lo; prev < prev_hi; ++prev) {- for (Char ch = lo; ch <= hi; ++ch)+ Hash lo_h = hash(prev, static_cast<uint8_t>(lo));+ Hash hi_h = hash(prev, static_cast<uint8_t>(hi));+ if (lo_h <= hi_h) {- Hash h = hash(prev, static_cast<uint8_t>(ch));- pmh_[h] &= pmh_mask;- next_hashes->first.insert(h);+ for (Hash h = lo_h; h <= hi_h; ++h)+ {+ Pred pma_keep = pma_[h] & pma_comb;+ pma_[h] &= pma_mask;+ pma_[h] |= pma_keep;+ } }- }- }- }- else- {- 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;- for (Hash prev = prev_lo; prev < prev_hi; ++prev)- {- for (Char ch = lo; ch <= hi; ++ch)+ else {- Hash h = hash(prev, static_cast<uint8_t>(ch));- pmh_[h] &= pmh_mask;+ for (Hash h = lo_h; h < Const::HASH; ++h)+ {+ Pred pma_keep = pma_[h] & pma_comb;+ pma_[h] &= pma_mask;+ pma_[h] |= pma_keep;+ }+ for (Hash h = 0; h <= hi_h; ++h)+ {+ Pred pma_keep = pma_[h] & pma_comb;+ pma_[h] &= pma_mask;+ pma_[h] |= pma_keep;+ } } } }@@ -4817,8 +4780,8 @@ bool Pattern::match_hfa_transitions(size_t level, const HFA::Hashes& hashes, con #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::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)));+ ::fprintf(file, "// reflex::Pattern FSM code or opcode constructor also takes a search pattern prediction table:\nextern const uint8_t reflex_pred_%s[%u] = {", opt_.n.empty() ? "FSM" : opt_.n.c_str(), 2 + len_ + (len_ == 0) * (256 + Const::BTAP) + 2 * 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)))); // 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]));@@ -4831,18 +4794,9 @@ void Pattern::write_predictor(FILE *file) const 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 (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 (int i = 0; i < Const::HASH; ++i)- ::fprintf(file, "%s%3hhu,", (i & 0xf) ? "" : "\n ", static_cast<uint8_t>(~pmh_[i]));- }+ // save predict match array pma_[] parameters+ for (int i = 0; i < Const::HASH; ++i)+ ::fprintf(file, "%s%3hhu,%3hhu,", (i & 0x7) ? "" : "\n ", static_cast<uint8_t>(~pma_[i] & 0xff), static_cast<uint8_t>(~pma_[i] >> 8)); if (lbk_ > 0) { // save lookback parameters lbk_ lbm_ cbk_[] after s-t cut and first s-t cut pattern characters fst_[]
@@ -1,4 +1,4 @@-.TH UGREP "1" "May 15, 2025" "ugrep 7.4.3" "User Commands"+.TH UGREP "1" "June 18, 2025" "ugrep 7.5.0" "User Commands" .SH NAME \fBugrep\fR, \fBug\fR -- file pattern searcher .SH SYNOPSIS@@ -167,10 +167,10 @@ the match or shortens the match. See also options \fB\-A\fR, \fB\-C\fR and \fB\ .TP \fB\-b\fR, \fB\-\-byte\-offset\fR The offset in bytes of a pattern match is displayed in front of the-respective matched line. When \fB\-u\fR is specified, displays the offset-for each pattern matched on the same line. Byte offsets are exact-for ASCII, UTF\-8 and raw binary input. Otherwise, the byte offset-in the UTF\-8 normalized input is displayed.+respective matched line. When \fB\-u\fR or \fB\-\-ungroup\fR is specified,+displays the offset for each pattern matched on the same line.+Byte offsets are exact for ASCII, UTF\-8 and raw binary input.+Otherwise, the offset in the UTF\-8\-normalized input is displayed. .TP \fB\-\-binary\-files\fR=\fITYPE\fR Controls searching and reporting pattern matches in binary files.@@ -182,8 +182,9 @@ which might output binary garbage to the terminal, which can have problematic consequences if the terminal driver interprets some of it as commands. `hex' reports all matches in hexadecimal. `with\-hex' only reports binary matches in hexadecimal, leaving text-matches alone. A match is considered binary when matching a zero-byte or invalid UTF. Short options are \fB\-a\fR, \fB\-I\fR, \fB\-U\fR, \fB\-W\fR and \fB\-X\fR.+matches alone. Files having NUL (zero) bytes are binary and files+with invalid UTF encoding are binary unless option \fB\-U\fR or \fB\-\-ascii\fR+or \fB\-\-binary\fR is specified. Short options are \fB\-a\fR, \fB\-I\fR, \fB\-W\fR, \fB\-X\fR. .TP \fB\-\-bool\fR, \fB\-%\fR, \fB\-%\fR% Specifies Boolean query patterns. A Boolean query pattern is@@ -317,8 +318,8 @@ after option \fB\-f\fR or after the FILE arguments. \fB\-\-encoding\fR=\fIENCODING\fR The encoding format of the input. The default ENCODING is binary or UTF\-8 which are treated the same. Therefore, \fB\-\-encoding\fR=binary-has no effect. Note that option \fB\-U\fR or \fB\-\-binary\fR specifies binary-PATTERN matching (text matching is the default). ENCODING can be:+has no effect. Contrast this with option \fB\-U\fR or \fB\-\-ascii\fR or \fB\-\-binary\fR+that specifies raw binary PATTERN matching. ENCODING can be: `binary', `ASCII', `UTF\-8', `UTF\-16', `UTF\-16BE', `UTF\-16LE', `UTF\-32', `UTF\-32BE', `UTF\-32LE', `LATIN1', `ISO\-8859\-1', `ISO\-8859\-2', `ISO\-8859\-3', `ISO\-8859\-4', `ISO\-8859\-5',@@ -495,7 +496,9 @@ the hyperlink and when option \fB\-k\fR is specified, the column number. .TP \fB\-I\fR, \fB\-\-ignore\-binary\fR Ignore matches in binary files. This option is equivalent to the-\fB\-\-binary\-files\fR=without\-match option.+\fB\-\-binary\-files\fR=without\-match option. Files having NUL (zero) bytes+are binary. Also files with invalid UTF encoding are binary unless+option \fB\-U\fR or \fB\-\-ascii\fR or \fB\-\-binary\fR is specified. .TP \fB\-i\fR, \fB\-\-ignore\-case\fR Perform case insensitive matching. By default, ugrep is case@@ -570,8 +573,8 @@ file systems, or any file system that is slow to search. Note that the start\-up time to search may be increased when complex search patterns are specified that contain large Unicode character classes combined with `*' or `+' repeats, which should be avoided. Option-\fB\-U\fR or \fB\-\-ascii\fR improves performance. Option \fB\-\-stats\fR displays an-index search report.+\fB\-U\fR or \fB\-\-ascii\fR or \fB\-\-binary\fR improves performance. Option \fB\-\-stats\fR+displays an index search report. .TP \fB\-J\fR \fINUM\fR, \fB\-\-jobs\fR=\fINUM\fR Specifies the number of threads spawned to search files. By@@ -862,9 +865,10 @@ output is sent to a terminal. .TP \fB\-U\fR, \fB\-\-ascii\fR, \fB\-\-binary\fR Disables Unicode matching for ASCII and binary matching. PATTERN-matches bytes, not Unicode characters. For example, \fB\-U\fR '\\xa3'-matches byte A3 (hex) instead of the Unicode code point U+00A3-represented by the UTF\-8 sequence C2 A3. See also option \fB\-\-dotall\fR.+matches bytes. For example, \fB\-U\fR '\\xa3' matches byte A3 (hex)+instead of the Unicode code point U+00A3 represented by the UTF\-8+sequence C2 A3. Input is not flagged as "binary" for having+invalid UTF, only for having NUL (zero) bytes. .TP \fB\-u\fR, \fB\-\-ungroup\fR Do not group multiple pattern matches on the same matched line.@@ -955,8 +959,7 @@ bzip2 (.bz, .bz2, .bzip2, .tbz, .tbz2, .tb2, .tz2), xz (.xz, .txz) and lzma (requires suffix .lzma, .tlz), zstd (.zst, .zstd, .tzst), lz4 (requires suffix .lz4),-brotli (requires suffix .br),-bzip3 (requires suffix .bz3).+brotli (requires suffix .br). .TP \fB\-\-zmax\fR=\fINUM\fR When used with option \fB\-z\fR or \fB\-\-decompress\fR, searches the contents of
@@ -1,4 +1,4 @@-.TH UGREP-INDEXER "1" "May 15, 2025" "ugrep-indexer 7.4.3" "User Commands"+.TH UGREP-INDEXER "1" "June 18, 2025" "ugrep-indexer 7.5.0" "User Commands" .SH NAME \fBugrep-indexer\fR -- file indexer to accelerate recursive searching .SH SYNOPSIS@@ -147,8 +147,7 @@ bzip2 (requires suffix .bz, .bz2, .bzip2, .tbz, .tbz2, .tb2, .tz2), lzma and xz (requires suffix .lzma, .tlz, .xz, .txz), lz4 (requires suffix .lz4), zstd (requires suffix .zst, .zstd, .tzst),-brotli (requires suffix .br),-bzip3 (requires suffix .bz3).+brotli (requires suffix .br). .TP \fB\-\-zmax\fR=\fINUM\fR When used with option \fB\-z\fR (\fB\-\-decompress\fR), indexes the contents of
@@ -1,4 +1,4 @@-.TH UGREP "1" "May 15, 2025" "ugrep 7.4.3" "User Commands"+.TH UGREP "1" "June 18, 2025" "ugrep 7.5.0" "User Commands" .SH NAME \fBugrep\fR, \fBug\fR -- file pattern searcher .SH SYNOPSIS@@ -167,10 +167,10 @@ the match or shortens the match. See also options \fB\-A\fR, \fB\-C\fR and \fB\ .TP \fB\-b\fR, \fB\-\-byte\-offset\fR The offset in bytes of a pattern match is displayed in front of the-respective matched line. When \fB\-u\fR is specified, displays the offset-for each pattern matched on the same line. Byte offsets are exact-for ASCII, UTF\-8 and raw binary input. Otherwise, the byte offset-in the UTF\-8 normalized input is displayed.+respective matched line. When \fB\-u\fR or \fB\-\-ungroup\fR is specified,+displays the offset for each pattern matched on the same line.+Byte offsets are exact for ASCII, UTF\-8 and raw binary input.+Otherwise, the offset in the UTF\-8\-normalized input is displayed. .TP \fB\-\-binary\-files\fR=\fITYPE\fR Controls searching and reporting pattern matches in binary files.@@ -182,8 +182,9 @@ which might output binary garbage to the terminal, which can have problematic consequences if the terminal driver interprets some of it as commands. `hex' reports all matches in hexadecimal. `with\-hex' only reports binary matches in hexadecimal, leaving text-matches alone. A match is considered binary when matching a zero-byte or invalid UTF. Short options are \fB\-a\fR, \fB\-I\fR, \fB\-U\fR, \fB\-W\fR and \fB\-X\fR.+matches alone. Files having NUL (zero) bytes are binary and files+with invalid UTF encoding are binary unless option \fB\-U\fR or \fB\-\-ascii\fR+or \fB\-\-binary\fR is specified. Short options are \fB\-a\fR, \fB\-I\fR, \fB\-W\fR, \fB\-X\fR. .TP \fB\-\-bool\fR, \fB\-%\fR, \fB\-%\fR% Specifies Boolean query patterns. A Boolean query pattern is@@ -317,8 +318,8 @@ after option \fB\-f\fR or after the FILE arguments. \fB\-\-encoding\fR=\fIENCODING\fR The encoding format of the input. The default ENCODING is binary or UTF\-8 which are treated the same. Therefore, \fB\-\-encoding\fR=binary-has no effect. Note that option \fB\-U\fR or \fB\-\-binary\fR specifies binary-PATTERN matching (text matching is the default). ENCODING can be:+has no effect. Contrast this with option \fB\-U\fR or \fB\-\-ascii\fR or \fB\-\-binary\fR+that specifies raw binary PATTERN matching. ENCODING can be: `binary', `ASCII', `UTF\-8', `UTF\-16', `UTF\-16BE', `UTF\-16LE', `UTF\-32', `UTF\-32BE', `UTF\-32LE', `LATIN1', `ISO\-8859\-1', `ISO\-8859\-2', `ISO\-8859\-3', `ISO\-8859\-4', `ISO\-8859\-5',@@ -495,7 +496,9 @@ the hyperlink and when option \fB\-k\fR is specified, the column number. .TP \fB\-I\fR, \fB\-\-ignore\-binary\fR Ignore matches in binary files. This option is equivalent to the-\fB\-\-binary\-files\fR=without\-match option.+\fB\-\-binary\-files\fR=without\-match option. Files having NUL (zero) bytes+are binary. Also files with invalid UTF encoding are binary unless+option \fB\-U\fR or \fB\-\-ascii\fR or \fB\-\-binary\fR is specified. .TP \fB\-i\fR, \fB\-\-ignore\-case\fR Perform case insensitive matching. By default, ugrep is case@@ -570,8 +573,8 @@ file systems, or any file system that is slow to search. Note that the start\-up time to search may be increased when complex search patterns are specified that contain large Unicode character classes combined with `*' or `+' repeats, which should be avoided. Option-\fB\-U\fR or \fB\-\-ascii\fR improves performance. Option \fB\-\-stats\fR displays an-index search report.+\fB\-U\fR or \fB\-\-ascii\fR or \fB\-\-binary\fR improves performance. Option \fB\-\-stats\fR+displays an index search report. .TP \fB\-J\fR \fINUM\fR, \fB\-\-jobs\fR=\fINUM\fR Specifies the number of threads spawned to search files. By@@ -862,9 +865,10 @@ output is sent to a terminal. .TP \fB\-U\fR, \fB\-\-ascii\fR, \fB\-\-binary\fR Disables Unicode matching for ASCII and binary matching. PATTERN-matches bytes, not Unicode characters. For example, \fB\-U\fR '\\xa3'-matches byte A3 (hex) instead of the Unicode code point U+00A3-represented by the UTF\-8 sequence C2 A3. See also option \fB\-\-dotall\fR.+matches bytes. For example, \fB\-U\fR '\\xa3' matches byte A3 (hex)+instead of the Unicode code point U+00A3 represented by the UTF\-8+sequence C2 A3. Input is not flagged as "binary" for having+invalid UTF, only for having NUL (zero) bytes. .TP \fB\-u\fR, \fB\-\-ungroup\fR Do not group multiple pattern matches on the same matched line.@@ -955,8 +959,7 @@ bzip2 (.bz, .bz2, .bzip2, .tbz, .tbz2, .tb2, .tz2), xz (.xz, .txz) and lzma (requires suffix .lzma, .tlz), zstd (.zst, .zstd, .tzst), lz4 (requires suffix .lz4),-brotli (requires suffix .br),-bzip3 (requires suffix .bz3).+brotli (requires suffix .br). .TP \fB\-\-zmax\fR=\fINUM\fR When used with option \fB\-z\fR or \fB\-\-decompress\fR, searches the contents of
@@ -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 "7.4.3"+#define UGREP_VERSION "7.5.0" // use a task-parallel thread to decompress the stream into a pipe to search, also handles nested archives #define WITH_DECOMPRESSION_THREAD@@ -1258,24 +1258,27 @@ void cat(const std::string& pathname, std::stack<Entry>& dir_entries, std::vecto if ((cFileName[0] != '.' && (attr & (FILE_ATTRIBUTE_HIDDEN|FILE_ATTRIBUTE_SYSTEM)) == 0) || (flag_hidden && cFileName[1] != '\0' && cFileName[1] != '.')) {- if ((attr & FILE_ATTRIBUTE_REPARSE_POINT) != 0)+ if ((attr & FILE_ATTRIBUTE_DIRECTORY) != 0) {- /* TODO consider following symlink, but ugrep.exe doesn't do that yet either- if (flag_dereference_files && (attr & (FILE_ATTRIBUTE_DIRECTORY|FILE_ATTRIBUTE_DEVICE)) == 0 && !dir_only)+ // check if this is a dir to index and not a symlink+ if (((ffd.dwFileAttributes & FILE_ATTRIBUTE_REPARSE_POINT) == 0 ||+ ffd.dwReserved0 != IO_REPARSE_TAG_SYMLINK) &&+ (dir_only || include_dir(entry_pathname.c_str(), cFileName.c_str()))) {- }- */- }- else if ((attr & FILE_ATTRIBUTE_DIRECTORY) != 0)- {- if (dir_only || include_dir(entry_pathname.c_str(), cFileName.c_str())) dir_entries.emplace(entry_pathname, cFileName.size(), modified_time(ffd), file_size(ffd));+ } else+ { ++ign_dirs;+ } } else if ((attr & FILE_ATTRIBUTE_DEVICE) == 0 && !dir_only) {- if (include_file(entry_pathname.c_str(), cFileName.c_str()))+ // check if this is a file to index and not a symlink unless -S is specified+ if ((flag_dereference_files ||+ (ffd.dwFileAttributes & FILE_ATTRIBUTE_REPARSE_POINT) == 0 ||+ ffd.dwReserved0 != IO_REPARSE_TAG_SYMLINK) &&+ include_file(entry_pathname.c_str(), cFileName.c_str())) { uint64_t file_time = modified_time(ffd); last_time = std::max(last_time, file_time);
@@ -702,8 +702,8 @@ inline bool is_binary(const char *s, size_t n) if (flag_encoding_type == reflex::Input::file_encoding::null_data) return false; - // not -a and -U or -W: file is binary if it has a \0 (NUL) or an invalid UTF-8 encoding- if (!flag_text && (!flag_binary || flag_with_hex))+ // not -a and -U or -W: file is binary if it has a \0 (NUL) or an invalid UTF-8 encoding when --encoding is unset+ if (!flag_text && (!flag_binary || flag_with_hex) && flag_encoding_type == reflex::Input::file_encoding::plain) return !reflex::isutf8(s, s + n); // otherwise, file is binary if it contains a \0 (NUL) which is what GNU grep checks@@ -3256,7 +3256,7 @@ struct Grep { virtual void ugrep(); // search file or directory for pattern matches- Type select(size_t level, const char *pathname, const char *basename, int type, ino_t& inode, uint64_t& info, bool is_argument = false);+ Type select(size_t level, const char *pathname, const char *basename, int type, uint32_t attr, ino_t& inode, uint64_t& info, bool is_argument = false); // recurse a directory virtual void recurse(size_t level, const char *pathname);@@ -3920,7 +3920,6 @@ struct Grep { bool init_read() { // initialize Grep search and output variables- interactive = false; binfile = false; lineno = flag_min_line > 0 ? flag_min_line - 1 : 0; heading = flag_with_filename;@@ -3929,6 +3928,9 @@ struct Grep { matches = 0; stop = false; + // "interactive" and possibly slow input from a standard input device or pipe+ bool interactive = false;+ const char *base; size_t size; @@ -3957,8 +3959,8 @@ struct Grep { { struct stat buf; - // if input is a character device (TTY) or a pipe, then make stdin nonblocking and register a stdin handler to continue reading and flush results to output- if (fstat(0, &buf) == 0 && (S_ISCHR(buf.st_mode) || S_ISFIFO(buf.st_mode)))+ // if input is a character device (e.g. TTY) or a pipe, then make stdin nonblocking and register a stdin handler to continue reading and flush results to output, don't check for invalid Unicode input+ if (fstat(0, &buf) == 0 && (S_ISCHR(buf.st_mode) || S_ISFIFO(buf.st_mode) | S_ISSOCK(buf.st_mode))) { interactive = (fcntl(0, F_SETFL, fcntl(0, F_GETFL) | O_NONBLOCK) != -1); if (interactive)@@ -3966,11 +3968,13 @@ struct Grep { } } #else- { }+ // for Windows we don't check for invalid Unicode input, no stdin handler+ if (input == stdin && !flag_quiet && !flag_files_with_matches && !flag_count)+ interactive = true; #endif } - // when non-blocking do not check init_is_binary(), wait until handler detects binary files+ // when non-blocking do not check init_is_binary(), wait until handler detects binary files that have NUL bytes if (!interactive) { if (flag_binary_without_match)@@ -4090,7 +4094,6 @@ struct Grep { MMap mmap; // mmap state reflex::Input input; // input to the matcher FILE *file_in; // the current input file- bool interactive; // search non-blocking standard input (e.g. TTY or pipe) bool binfile; // the file being searched is a binary file size_t lineno; // the line number of the last match bool heading; // heading on/off, initially set to --with-filename@@ -6867,7 +6870,7 @@ void init(int argc, const char **argv) else { // use threads to descent into a directory- if ((attr & FILE_ATTRIBUTE_DIRECTORY) != 0 && (attr & FILE_ATTRIBUTE_REPARSE_POINT) == 0)+ if ((attr & FILE_ATTRIBUTE_DIRECTORY) != 0) { if (flag_directories_action == Action::UNSP) flag_all_threads = true;@@ -6940,11 +6943,16 @@ void init(int argc, const char **argv) if (!flag_stdin && Static::arg_files.empty()) {- // if no FILE specified when reading standard input from a TTY then enable -R if not already -r or -R- if (isatty(STDIN_FILENO) && (flag_directories_action == Action::UNSP || flag_directories_action == Action::RECURSE))+ if (!flag_from.empty())+ {+ // all --from=FILE are empty, warn (don't search recursively)+ for (const auto& from : flag_from)+ warning("--from: empty", from.c_str());+ }+ else if (isatty(STDIN_FILENO) && (flag_directories_action == Action::UNSP || flag_directories_action == Action::RECURSE)) {- if (flag_directories_action == Action::UNSP)- flag_directories_action = Action::RECURSE;+ // if no FILE specified when reading standard input from a TTY then enable -r if not already -r or -R+ flag_directories_action = Action::RECURSE; // recursive search with worker threads flag_all_threads = true;@@ -7561,8 +7569,25 @@ void terminal() flag_color_term = SetConsoleMode(hConOut, outMode) != 0; } #endif- }+ const char *val; + // no color when NO_COLOR is set or when ConEmuANSI is OFF+ if (((val = getenv("NO_COLOR")) != NULL && *val != '\0') ||+ ((val = getenv("ConEmuANSI")) != NULL && strcmp(val, "OFF") == 0))+ {+ flag_color_term = false;+ }+ else if (!flag_color_term)+ {+ // try ANSICON or COLORTERM or ConEmuANSI is ON+ if (getenv("ANSICON") != NULL ||+ getenv("COLORTERM") != NULL ||+ ((val = getenv("ConEmuANSI")) != NULL && strcmp(val, "ON") == 0))+ {+ flag_color_term = true;+ }+ }+ } #else // check whether we have a color terminal@@ -8486,7 +8511,7 @@ void ugrep() flag_directories_action = Action::RECURSE; } - // -p (--no-dereference) and -S (--dereference): -p takes priority over -S and -R+ // -p (--no-dereference) and -S (--dereference-files): -p takes priority over -S and -R if (flag_no_dereference) flag_dereference = flag_dereference_files = false; @@ -9070,7 +9095,10 @@ void Grep::ugrep() } else {-#ifndef OS_WIN+#ifdef OS_WIN+ const DWORD attr = INVALID_FILE_ATTRIBUTES;+#else+ const uint32_t attr = 0; std::pair<std::set<ino_t>::iterator,bool> vino; #endif @@ -9095,7 +9123,7 @@ void Grep::ugrep() uint64_t info; // search file or recursively search directory based on selection criteria- switch (select(1, pathname, basename, DIRENT_TYPE_UNKNOWN, inode, info, true))+ switch (select(1, pathname, basename, DIRENT_TYPE_UNKNOWN, attr, inode, info, true)) { case Type::DIRECTORY: if (flag_directories_action != Action::SKIP)@@ -9126,14 +9154,16 @@ void Grep::ugrep() } // select file or directory to search for pattern matches, return SKIP, DIRECTORY or OTHER-Grep::Type Grep::select(size_t level, const char *pathname, const char *basename, int type, ino_t& inode, uint64_t& info, bool is_argument)+Grep::Type Grep::select(size_t level, const char *pathname, const char *basename, int type, uint32_t attr, ino_t& inode, uint64_t& info, bool is_argument) { if (*basename == '.' && !flag_hidden && !is_argument) return Type::SKIP; #ifdef OS_WIN - DWORD attr = GetFileAttributesW(utf8_decode(pathname).c_str());+ // use file attributes from FindFirstFileW() WIN32_FIND_DATAW dwFileAttributes otherwise attr == INVALID_FILE_ATTRIBUTES+ if (attr == INVALID_FILE_ATTRIBUTES)+ attr = GetFileAttributesW(utf8_decode(pathname).c_str()); if (attr == INVALID_FILE_ATTRIBUTES) {@@ -9142,10 +9172,6 @@ Grep::Type Grep::select(size_t level, const char *pathname, const char *basename return Type::SKIP; } - // skip FILE_ATTRIBUTE_REPARSE_POINT even when it is a symlink- if ((attr & FILE_ATTRIBUTE_REPARSE_POINT) != 0)- return Type::SKIP;- // skip hidden and system files unless explicitly searched with --hidden if (!flag_hidden && !is_argument && ((attr & FILE_ATTRIBUTE_HIDDEN) || (attr & FILE_ATTRIBUTE_SYSTEM))) return Type::SKIP;@@ -9346,6 +9372,8 @@ Grep::Type Grep::select(size_t level, const char *pathname, const char *basename #else + (void)attr;+ struct stat buf; // -R or -S or command line argument FILE to search: follow symlinks to directories@@ -9740,7 +9768,16 @@ void Grep::recurse(size_t level, const char *pathname) } ino_t inode = 0;- Type type = select(level + 1, entry_pathname.c_str(), cFileName.c_str(), DIRENT_TYPE_UNKNOWN, inode, info);+ Type type = select(level + 1, entry_pathname.c_str(), cFileName.c_str(), DIRENT_TYPE_UNKNOWN, ffd.dwFileAttributes, inode, info);++ // check if we're recursing on a symlink to skip them when -p or -r is specified+ if (!flag_dereference && (ffd.dwFileAttributes & FILE_ATTRIBUTE_REPARSE_POINT) != 0 && ffd.dwReserved0 == IO_REPARSE_TAG_SYMLINK)+ {+ if (type == Type::DIRECTORY)+ type = Type::SKIP;+ else if (type == Type::OTHER && !flag_dereference_files)+ type = Type::SKIP;+ } // --index: search indexed files quickly, but only when necessary on demand if (type == Type::OTHER && Static::index_pattern != NULL)@@ -9949,10 +9986,10 @@ void Grep::recurse(size_t level, const char *pathname) // search entry_pathname, unless searchable directory into which we should recurse #if defined(HAVE_STRUCT_DIRENT_D_TYPE) && defined(HAVE_STRUCT_DIRENT_D_INO) inode = dirent->d_ino;- type = select(level + 1, entry_pathname.c_str(), dirent->d_name, dirent->d_type, inode, info);+ type = select(level + 1, entry_pathname.c_str(), dirent->d_name, dirent->d_type, 0, inode, info); #else inode = 0;- type = select(level + 1, entry_pathname.c_str(), dirent->d_name, DIRENT_TYPE_UNKNOWN, inode, info);+ type = select(level + 1, entry_pathname.c_str(), dirent->d_name, DIRENT_TYPE_UNKNOWN, 0, inode, info); #endif if (flag_sort_key == Sort::LIST)@@ -13818,10 +13855,10 @@ void help(std::ostream& out) the match or shortens the match. See also options -A, -C and -y.\n\ -b, --byte-offset\n\ The offset in bytes of a pattern match is displayed in front of the\n\- respective matched line. When -u is specified, displays the offset\n\- for each pattern matched on the same line. Byte offsets are exact\n\- for ASCII, UTF-8 and raw binary input. Otherwise, the byte offset\n\- in the UTF-8 normalized input is displayed.\n\+ respective matched line. When -u or --ungroup is specified,\n\+ displays the offset for each pattern matched on the same line.\n\+ Byte offsets are exact for ASCII, UTF-8 and raw binary input.\n\+ Otherwise, the offset in the UTF-8-normalized input is displayed.\n\ --binary-files=TYPE\n\ Controls searching and reporting pattern matches in binary files.\n\ TYPE can be `binary', `without-match`, `text`, `hex` and\n\@@ -13832,8 +13869,9 @@ void help(std::ostream& out) problematic consequences if the terminal driver interprets some of\n\ it as commands. `hex' reports all matches in hexadecimal.\n\ `with-hex' only reports binary matches in hexadecimal, leaving text\n\- matches alone. A match is considered binary when matching a zero\n\- byte or invalid UTF. Short options are -a, -I, -U, -W and -X.\n\+ matches alone. Files having NUL (zero) bytes are binary and files\n\+ with invalid UTF encoding are binary unless option -U or --ascii\n\+ or --binary is specified. Short options are -a, -I, -W, -X.\n\ --bool, -%, -%%\n\ Specifies Boolean query patterns. A Boolean query pattern is\n\ composed of `AND', `OR', `NOT' operators and grouping with `(' `)'.\n\@@ -13948,8 +13986,8 @@ void help(std::ostream& out) --encoding=ENCODING\n\ The encoding format of the input. The default ENCODING is binary\n\ or UTF-8 which are treated the same. Therefore, --encoding=binary\n\- has no effect. Note that option -U or --binary specifies binary\n\- PATTERN matching (text matching is the default). ENCODING can be:\n\+ has no effect. Contrast this with option -U or --ascii or --binary\n\+ that specifies raw binary PATTERN matching. ENCODING can be:\n\ "; size_t k = 10; for (int i = 0; encoding_table[i].format != NULL; ++i)@@ -14125,7 +14163,9 @@ void help(std::ostream& out) the hyperlink and when option -k is specified, the column number.\n\ -I, --ignore-binary\n\ Ignore matches in binary files. This option is equivalent to the\n\- --binary-files=without-match option.\n\+ --binary-files=without-match option. Files having NUL (zero) bytes\n\+ are binary. Also files with invalid UTF encoding are binary unless\n\+ option -U or --ascii or --binary is specified.\n\ -i, --ignore-case\n\ Perform case insensitive matching. By default, ugrep is case\n\ sensitive.\n\@@ -14197,8 +14237,8 @@ void help(std::ostream& out) the start-up time to search may be increased when complex search\n\ patterns are specified that contain large Unicode character classes\n\ combined with `*' or `+' repeats, which should be avoided. Option\n\- -U or --ascii improves performance. Option --stats displays an\n\- index search report.\n\+ -U or --ascii or --binary improves performance. Option --stats\n\+ displays an index search report.\n\ -J NUM, --jobs=NUM\n\ Specifies the number of threads spawned to search files. By\n\ default an optimum number of threads is spawned to search files\n\@@ -14442,9 +14482,10 @@ void help(std::ostream& out) output is sent to a terminal.\n\ -U, --ascii, --binary\n\ Disables Unicode matching for ASCII and binary matching. PATTERN\n\- matches bytes, not Unicode characters. For example, -U '\\xa3'\n\- matches byte A3 (hex) instead of the Unicode code point U+00A3\n\- represented by the UTF-8 sequence C2 A3. See also option --dotall.\n\+ matches bytes. For example, -U '\\xa3' matches byte A3 (hex)\n\+ instead of the Unicode code point U+00A3 represented by the UTF-8\n\+ sequence C2 A3. Input is not flagged as \"binary\" for having\n\+ invalid UTF, only for having NUL (zero) bytes.\n\ -u, --ungroup\n\ Do not group multiple pattern matches on the same matched line.\n\ Output the matched line again for each additional pattern match.\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 "7.4.3"+#define UGREP_VERSION "7.5.0" // disable mmap because mmap is almost always slower than the file reading speed improvements since 3.0.0 #define WITH_NO_MMAP