Restoring authorship annotation for Ivan Blinkov <ivan@blinkov.ru>. Commit 1 of 2.

1 files changed, 467 insertions, 467 deletions

diff --git a/contrib/libs/hyperscan/src/rose/rose_build_lit_accel.cpp b/contrib/libs/hyperscan/src/rose/rose_build_lit_accel.cpp
index b389f493d1..5d7af28313 100644
--- a/contrib/libs/hyperscan/src/rose/rose_build_lit_accel.cpp
+++ b/contrib/libs/hyperscan/src/rose/rose_build_lit_accel.cpp
@@ -1,467 +1,467 @@
-/*
- * Copyright (c) 2017, Intel Corporation
- *
- * Redistribution and use in source and binary forms, with or without
- * modification, are permitted provided that the following conditions are met:
- *
- *  * Redistributions of source code must retain the above copyright notice,
- *    this list of conditions and the following disclaimer.
- *  * Redistributions in binary form must reproduce the above copyright
- *    notice, this list of conditions and the following disclaimer in the
- *    documentation and/or other materials provided with the distribution.
- *  * Neither the name of Intel Corporation nor the names of its contributors
- *    may be used to endorse or promote products derived from this software
- *    without specific prior written permission.
- *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
- * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
- * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
- * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
- * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
- * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
- * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
- * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
- * POSSIBILITY OF SUCH DAMAGE.
- */
-
-#include "rose_build_lit_accel.h"
-
-#include "grey.h"
-#include "ue2common.h"
-#include "hwlm/hwlm_build.h"
-#include "hwlm/hwlm_internal.h"
-#include "hwlm/hwlm_literal.h"
-#include "nfa/accel.h"
-#include "nfa/shufticompile.h"
-#include "nfa/trufflecompile.h"
-#include "util/compare.h"
-#include "util/dump_charclass.h"
-#include "util/ue2string.h"
-#include "util/verify_types.h"
-
-using namespace std;
-
-namespace ue2 {
-
-static const unsigned int MAX_ACCEL_OFFSET = 16;
-static const unsigned int MAX_SHUFTI_WIDTH = 240;
-
-static
-size_t mask_overhang(const AccelString &lit) {
-    size_t msk_true_size = lit.msk.size();
-    assert(msk_true_size <= HWLM_MASKLEN);
-    assert(HWLM_MASKLEN <= MAX_ACCEL_OFFSET);
-    for (u8 c : lit.msk) {
-        if (!c) {
-            msk_true_size--;
-        } else {
-            break;
-        }
-    }
-
-    if (lit.s.length() >= msk_true_size) {
-        return 0;
-    }
-
-    /* only short literals should be able to have a mask which overhangs */
-    assert(lit.s.length() < MAX_ACCEL_OFFSET);
-    return msk_true_size - lit.s.length();
-}
-
-static
-bool findDVerm(const vector<const AccelString *> &lits, AccelAux *aux) {
-    const AccelString &first = *lits.front();
-
-    struct candidate {
-        candidate(void)
-            : c1(0), c2(0), max_offset(0), b5insens(false), valid(false) {}
-        candidate(const AccelString &base, u32 offset)
-            : c1(base.s[offset]), c2(base.s[offset + 1]), max_offset(0),
-              b5insens(false), valid(true) {}
-        char c1;
-        char c2;
-        u32 max_offset;
-        bool b5insens;
-        bool valid;
-
-        bool operator>(const candidate &other) const {
-            if (!valid) {
-                return false;
-            }
-
-            if (!other.valid) {
-                return true;
-            }
-
-            if (other.cdiffers() && !cdiffers()) {
-                return false;
-            }
-
-            if (!other.cdiffers() && cdiffers()) {
-                return true;
-            }
-
-            if (!other.b5insens && b5insens) {
-                return false;
-            }
-
-            if (other.b5insens && !b5insens) {
-                return true;
-            }
-
-            if (max_offset > other.max_offset) {
-                return false;
-            }
-
-            return true;
-        }
-
-        bool cdiffers(void) const {
-            if (!b5insens) {
-                return c1 != c2;
-            }
-            return (c1 & CASE_CLEAR) != (c2 & CASE_CLEAR);
-        }
-    };
-
-    candidate best;
-
-    for (u32 i = 0; i < MIN(MAX_ACCEL_OFFSET, first.s.length()) - 1; i++) {
-        candidate curr(first, i);
-
-        /* check to see if this pair appears in each string */
-        for (const auto &lit_ptr : lits) {
-            const AccelString &lit = *lit_ptr;
-            if (lit.nocase && (ourisalpha(curr.c1) || ourisalpha(curr.c2))) {
-                curr.b5insens = true; /* no choice but to be case insensitive */
-            }
-
-            bool found = false;
-            bool found_nc = false;
-            for (u32 j = 0;
-                 !found && j < MIN(MAX_ACCEL_OFFSET, lit.s.length()) - 1; j++) {
-                found |= curr.c1 == lit.s[j] && curr.c2 == lit.s[j + 1];
-                found_nc |= (curr.c1 & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR)
-                    && (curr.c2 & CASE_CLEAR) == (lit.s[j + 1] & CASE_CLEAR);
-
-                if (curr.b5insens) {
-                    found = found_nc;
-                }
-            }
-
-            if (!curr.b5insens && !found && found_nc) {
-                curr.b5insens = true;
-                found = true;
-            }
-
-            if (!found) {
-                goto next_candidate;
-            }
-        }
-
-        /* check to find the max offset where this appears */
-        for (const auto &lit_ptr : lits) {
-            const AccelString &lit = *lit_ptr;
-            for (u32 j = 0; j < MIN(MAX_ACCEL_OFFSET, lit.s.length()) - 1;
-                 j++) {
-                bool found = false;
-                if (curr.b5insens) {
-                    found = (curr.c1 & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR)
-                     && (curr.c2 & CASE_CLEAR) == (lit.s[j + 1] & CASE_CLEAR);
-                } else {
-                    found = curr.c1 == lit.s[j] && curr.c2 == lit.s[j + 1];
-                }
-
-                if (found) {
-                    assert(j + mask_overhang(lit) <= MAX_ACCEL_OFFSET);
-                    ENSURE_AT_LEAST(&curr.max_offset, j + mask_overhang(lit));
-                    break;
-                }
-            }
-        }
-
-        if (curr > best) {
-            best = curr;
-        }
-
-    next_candidate:;
-    }
-
-    if (!best.valid) {
-        return false;
-    }
-
-    aux->dverm.offset = verify_u8(best.max_offset);
-
-    if (!best.b5insens) {
-        aux->dverm.accel_type = ACCEL_DVERM;
-        aux->dverm.c1 = best.c1;
-        aux->dverm.c2 = best.c2;
-        DEBUG_PRINTF("built dverm for %02hhx%02hhx\n",
-                     aux->dverm.c1, aux->dverm.c2);
-    } else {
-        aux->dverm.accel_type = ACCEL_DVERM_NOCASE;
-        aux->dverm.c1 = best.c1 & CASE_CLEAR;
-        aux->dverm.c2 = best.c2 & CASE_CLEAR;
-        DEBUG_PRINTF("built dverm nc for %02hhx%02hhx\n",
-                     aux->dverm.c1, aux->dverm.c2);
-    }
-    return true;
-}
-
-static
-bool findSVerm(const vector<const AccelString *> &lits, AccelAux *aux) {
-    const AccelString &first = *lits.front();
-
-    struct candidate {
-        candidate(void)
-            : c(0), max_offset(0), b5insens(false), valid(false) {}
-        candidate(const AccelString &base, u32 offset)
-            : c(base.s[offset]), max_offset(0),
-              b5insens(false), valid(true) {}
-        char c;
-        u32 max_offset;
-        bool b5insens;
-        bool valid;
-
-        bool operator>(const candidate &other) const {
-            if (!valid) {
-                return false;
-            }
-
-            if (!other.valid) {
-                return true;
-            }
-
-            if (!other.b5insens && b5insens) {
-                return false;
-            }
-
-            if (other.b5insens && !b5insens) {
-                return true;
-            }
-
-            if (max_offset > other.max_offset) {
-                return false;
-            }
-
-            return true;
-        }
-    };
-
-    candidate best;
-
-    for (u32 i = 0; i < MIN(MAX_ACCEL_OFFSET, first.s.length()); i++) {
-        candidate curr(first, i);
-
-        /* check to see if this pair appears in each string */
-        for (const auto &lit_ptr : lits) {
-            const AccelString &lit = *lit_ptr;
-            if (lit.nocase && ourisalpha(curr.c)) {
-                curr.b5insens = true; /* no choice but to be case insensitive */
-            }
-
-            bool found = false;
-            bool found_nc = false;
-            for (u32 j = 0;
-                 !found && j < MIN(MAX_ACCEL_OFFSET, lit.s.length()); j++) {
-                found |= curr.c == lit.s[j];
-                found_nc |= (curr.c & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR);
-
-                if (curr.b5insens) {
-                    found = found_nc;
-                }
-            }
-
-            if (!curr.b5insens && !found && found_nc) {
-                curr.b5insens = true;
-                found = true;
-            }
-
-            if (!found) {
-                goto next_candidate;
-            }
-        }
-
-        /* check to find the max offset where this appears */
-        for (const auto &lit_ptr : lits) {
-            const AccelString &lit = *lit_ptr;
-            for (u32 j = 0; j < MIN(MAX_ACCEL_OFFSET, lit.s.length()); j++) {
-                bool found = false;
-                if (curr.b5insens) {
-                    found = (curr.c & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR);
-                } else {
-                    found = curr.c == lit.s[j];
-                }
-
-                if (found) {
-                    assert(j + mask_overhang(lit) <= MAX_ACCEL_OFFSET);
-                    ENSURE_AT_LEAST(&curr.max_offset, j + mask_overhang(lit));
-                }
-            }
-        }
-
-        if (curr > best) {
-            best = curr;
-        }
-
-    next_candidate:;
-    }
-
-    if (!best.valid) {
-        return false;
-    }
-
-    if (!best.b5insens) {
-        aux->verm.accel_type = ACCEL_VERM;
-        aux->verm.c = best.c;
-        DEBUG_PRINTF("built verm for %02hhx\n", aux->verm.c);
-    } else {
-        aux->verm.accel_type = ACCEL_VERM_NOCASE;
-        aux->verm.c = best.c & CASE_CLEAR;
-        DEBUG_PRINTF("built verm nc for %02hhx\n", aux->verm.c);
-    }
-    aux->verm.offset = verify_u8(best.max_offset);
-
-    return true;
-}
-
-static
-void filterLits(const vector<AccelString> &lits, hwlm_group_t expected_groups,
-                vector<const AccelString *> *filtered_lits, u32 *min_len) {
-    *min_len = MAX_ACCEL_OFFSET;
-
-    for (const auto &lit : lits) {
-        if (!(lit.groups & expected_groups)) {
-            continue;
-        }
-
-        const size_t lit_len = lit.s.length();
-        if (lit_len < *min_len) {
-            *min_len = verify_u32(lit_len);
-        }
-
-        DEBUG_PRINTF("lit: '%s', nocase=%d, groups=0x%llx\n",
-                     escapeString(lit.s).c_str(), lit.nocase ? 1 : 0,
-                     lit.groups);
-        filtered_lits->push_back(&lit);
-    }
-}
-
-static
-bool litGuardedByCharReach(const CharReach &cr, const AccelString &lit,
-                           u32 max_offset) {
-    for (u32 i = 0; i <= max_offset && i < lit.s.length(); i++) {
-         unsigned char c = lit.s[i];
-         if (lit.nocase) {
-             if (cr.test(mytoupper(c)) && cr.test(mytolower(c))) {
-                 return true;
-             }
-         } else {
-             if (cr.test(c)) {
-                 return true;
-             }
-         }
-    }
-
-    return false;
-}
-
-static
-void findForwardAccelScheme(const vector<AccelString> &lits,
-                            hwlm_group_t expected_groups, AccelAux *aux) {
-    DEBUG_PRINTF("building accel expected=%016llx\n", expected_groups);
-    u32 min_len = MAX_ACCEL_OFFSET;
-    vector<const AccelString *> filtered_lits;
-
-    filterLits(lits, expected_groups, &filtered_lits, &min_len);
-    if (filtered_lits.empty()) {
-        return;
-    }
-
-    if (findDVerm(filtered_lits, aux)
-        || findSVerm(filtered_lits, aux)) {
-        return;
-    }
-
-    /* look for shufti/truffle */
-
-    vector<CharReach> reach(MAX_ACCEL_OFFSET, CharReach());
-    for (const auto &lit : lits) {
-        if (!(lit.groups & expected_groups)) {
-            continue;
-        }
-
-        u32 overhang = mask_overhang(lit);
-        for (u32 i = 0; i < overhang; i++) {
-            /* this offset overhangs the start of the real literal; look at the
-             * msk/cmp */
-            for (u32 j = 0; j < N_CHARS; j++) {
-                if ((j & lit.msk[i]) == lit.cmp[i]) {
-                    reach[i].set(j);
-                }
-            }
-        }
-        for (u32 i = overhang; i < MAX_ACCEL_OFFSET; i++) {
-            CharReach &reach_i = reach[i];
-            u32 i_effective = i - overhang;
-
-            if (litGuardedByCharReach(reach_i, lit, i_effective)) {
-                continue;
-            }
-            unsigned char c = i_effective < lit.s.length() ? lit.s[i_effective]
-                                                           : lit.s.back();
-            if (lit.nocase) {
-                reach_i.set(mytoupper(c));
-                reach_i.set(mytolower(c));
-            } else {
-                reach_i.set(c);
-            }
-        }
-    }
-
-    u32 min_count = ~0U;
-    u32 min_offset = ~0U;
-    for (u32 i = 0; i < MAX_ACCEL_OFFSET; i++) {
-        size_t count = reach[i].count();
-        DEBUG_PRINTF("offset %u is %s (reach %zu)\n", i,
-                     describeClass(reach[i]).c_str(), count);
-        if (count < min_count) {
-            min_count = (u32)count;
-            min_offset = i;
-        }
-    }
-
-    if (min_count > MAX_SHUFTI_WIDTH) {
-        DEBUG_PRINTF("FAIL: min shufti with %u chars is too wide\n", min_count);
-        return;
-    }
-
-    const CharReach &cr = reach[min_offset];
-    if (-1 !=
-        shuftiBuildMasks(cr, (u8 *)&aux->shufti.lo, (u8 *)&aux->shufti.hi)) {
-        DEBUG_PRINTF("built shufti for %s (%zu chars, offset %u)\n",
-                     describeClass(cr).c_str(), cr.count(), min_offset);
-        aux->shufti.accel_type = ACCEL_SHUFTI;
-        aux->shufti.offset = verify_u8(min_offset);
-        return;
-    }
-
-    truffleBuildMasks(cr, (u8 *)&aux->truffle.mask1, (u8 *)&aux->truffle.mask2);
-    DEBUG_PRINTF("built truffle for %s (%zu chars, offset %u)\n",
-                 describeClass(cr).c_str(), cr.count(), min_offset);
-    aux->truffle.accel_type = ACCEL_TRUFFLE;
-    aux->truffle.offset = verify_u8(min_offset);
-}
-
-void buildForwardAccel(HWLM *h, const vector<AccelString> &lits,
-                       hwlm_group_t expected_groups) {
-    findForwardAccelScheme(lits, expected_groups, &h->accel1);
-    findForwardAccelScheme(lits, HWLM_ALL_GROUPS, &h->accel0);
-
-    h->accel1_groups = expected_groups;
-}
-
-} // namespace ue2
+/* 
+ * Copyright (c) 2017, Intel Corporation 
+ * 
+ * Redistribution and use in source and binary forms, with or without 
+ * modification, are permitted provided that the following conditions are met: 
+ * 
+ *  * Redistributions of source code must retain the above copyright notice, 
+ *    this list of conditions and the following disclaimer. 
+ *  * Redistributions in binary form must reproduce the above copyright 
+ *    notice, this list of conditions and the following disclaimer in the 
+ *    documentation and/or other materials provided with the distribution. 
+ *  * Neither the name of Intel Corporation nor the names of its contributors 
+ *    may be used to endorse or promote products derived from this software 
+ *    without specific prior written permission. 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
+ * POSSIBILITY OF SUCH DAMAGE. 
+ */ 
+ 
+#include "rose_build_lit_accel.h" 
+ 
+#include "grey.h" 
+#include "ue2common.h" 
+#include "hwlm/hwlm_build.h" 
+#include "hwlm/hwlm_internal.h" 
+#include "hwlm/hwlm_literal.h" 
+#include "nfa/accel.h" 
+#include "nfa/shufticompile.h" 
+#include "nfa/trufflecompile.h" 
+#include "util/compare.h" 
+#include "util/dump_charclass.h" 
+#include "util/ue2string.h" 
+#include "util/verify_types.h" 
+ 
+using namespace std; 
+ 
+namespace ue2 { 
+ 
+static const unsigned int MAX_ACCEL_OFFSET = 16; 
+static const unsigned int MAX_SHUFTI_WIDTH = 240; 
+ 
+static 
+size_t mask_overhang(const AccelString &lit) { 
+    size_t msk_true_size = lit.msk.size(); 
+    assert(msk_true_size <= HWLM_MASKLEN); 
+    assert(HWLM_MASKLEN <= MAX_ACCEL_OFFSET); 
+    for (u8 c : lit.msk) { 
+        if (!c) { 
+            msk_true_size--; 
+        } else { 
+            break; 
+        } 
+    } 
+ 
+    if (lit.s.length() >= msk_true_size) { 
+        return 0; 
+    } 
+ 
+    /* only short literals should be able to have a mask which overhangs */ 
+    assert(lit.s.length() < MAX_ACCEL_OFFSET); 
+    return msk_true_size - lit.s.length(); 
+} 
+ 
+static 
+bool findDVerm(const vector<const AccelString *> &lits, AccelAux *aux) { 
+    const AccelString &first = *lits.front(); 
+ 
+    struct candidate { 
+        candidate(void) 
+            : c1(0), c2(0), max_offset(0), b5insens(false), valid(false) {} 
+        candidate(const AccelString &base, u32 offset) 
+            : c1(base.s[offset]), c2(base.s[offset + 1]), max_offset(0), 
+              b5insens(false), valid(true) {} 
+        char c1; 
+        char c2; 
+        u32 max_offset; 
+        bool b5insens; 
+        bool valid; 
+ 
+        bool operator>(const candidate &other) const { 
+            if (!valid) { 
+                return false; 
+            } 
+ 
+            if (!other.valid) { 
+                return true; 
+            } 
+ 
+            if (other.cdiffers() && !cdiffers()) { 
+                return false; 
+            } 
+ 
+            if (!other.cdiffers() && cdiffers()) { 
+                return true; 
+            } 
+ 
+            if (!other.b5insens && b5insens) { 
+                return false; 
+            } 
+ 
+            if (other.b5insens && !b5insens) { 
+                return true; 
+            } 
+ 
+            if (max_offset > other.max_offset) { 
+                return false; 
+            } 
+ 
+            return true; 
+        } 
+ 
+        bool cdiffers(void) const { 
+            if (!b5insens) { 
+                return c1 != c2; 
+            } 
+            return (c1 & CASE_CLEAR) != (c2 & CASE_CLEAR); 
+        } 
+    }; 
+ 
+    candidate best; 
+ 
+    for (u32 i = 0; i < MIN(MAX_ACCEL_OFFSET, first.s.length()) - 1; i++) { 
+        candidate curr(first, i); 
+ 
+        /* check to see if this pair appears in each string */ 
+        for (const auto &lit_ptr : lits) { 
+            const AccelString &lit = *lit_ptr; 
+            if (lit.nocase && (ourisalpha(curr.c1) || ourisalpha(curr.c2))) { 
+                curr.b5insens = true; /* no choice but to be case insensitive */ 
+            } 
+ 
+            bool found = false; 
+            bool found_nc = false; 
+            for (u32 j = 0; 
+                 !found && j < MIN(MAX_ACCEL_OFFSET, lit.s.length()) - 1; j++) { 
+                found |= curr.c1 == lit.s[j] && curr.c2 == lit.s[j + 1]; 
+                found_nc |= (curr.c1 & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR) 
+                    && (curr.c2 & CASE_CLEAR) == (lit.s[j + 1] & CASE_CLEAR); 
+ 
+                if (curr.b5insens) { 
+                    found = found_nc; 
+                } 
+            } 
+ 
+            if (!curr.b5insens && !found && found_nc) { 
+                curr.b5insens = true; 
+                found = true; 
+            } 
+ 
+            if (!found) { 
+                goto next_candidate; 
+            } 
+        } 
+ 
+        /* check to find the max offset where this appears */ 
+        for (const auto &lit_ptr : lits) { 
+            const AccelString &lit = *lit_ptr; 
+            for (u32 j = 0; j < MIN(MAX_ACCEL_OFFSET, lit.s.length()) - 1; 
+                 j++) { 
+                bool found = false; 
+                if (curr.b5insens) { 
+                    found = (curr.c1 & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR) 
+                     && (curr.c2 & CASE_CLEAR) == (lit.s[j + 1] & CASE_CLEAR); 
+                } else { 
+                    found = curr.c1 == lit.s[j] && curr.c2 == lit.s[j + 1]; 
+                } 
+ 
+                if (found) { 
+                    assert(j + mask_overhang(lit) <= MAX_ACCEL_OFFSET); 
+                    ENSURE_AT_LEAST(&curr.max_offset, j + mask_overhang(lit)); 
+                    break; 
+                } 
+            } 
+        } 
+ 
+        if (curr > best) { 
+            best = curr; 
+        } 
+ 
+    next_candidate:; 
+    } 
+ 
+    if (!best.valid) { 
+        return false; 
+    } 
+ 
+    aux->dverm.offset = verify_u8(best.max_offset); 
+ 
+    if (!best.b5insens) { 
+        aux->dverm.accel_type = ACCEL_DVERM; 
+        aux->dverm.c1 = best.c1; 
+        aux->dverm.c2 = best.c2; 
+        DEBUG_PRINTF("built dverm for %02hhx%02hhx\n", 
+                     aux->dverm.c1, aux->dverm.c2); 
+    } else { 
+        aux->dverm.accel_type = ACCEL_DVERM_NOCASE; 
+        aux->dverm.c1 = best.c1 & CASE_CLEAR; 
+        aux->dverm.c2 = best.c2 & CASE_CLEAR; 
+        DEBUG_PRINTF("built dverm nc for %02hhx%02hhx\n", 
+                     aux->dverm.c1, aux->dverm.c2); 
+    } 
+    return true; 
+} 
+ 
+static 
+bool findSVerm(const vector<const AccelString *> &lits, AccelAux *aux) { 
+    const AccelString &first = *lits.front(); 
+ 
+    struct candidate { 
+        candidate(void) 
+            : c(0), max_offset(0), b5insens(false), valid(false) {} 
+        candidate(const AccelString &base, u32 offset) 
+            : c(base.s[offset]), max_offset(0), 
+              b5insens(false), valid(true) {} 
+        char c; 
+        u32 max_offset; 
+        bool b5insens; 
+        bool valid; 
+ 
+        bool operator>(const candidate &other) const { 
+            if (!valid) { 
+                return false; 
+            } 
+ 
+            if (!other.valid) { 
+                return true; 
+            } 
+ 
+            if (!other.b5insens && b5insens) { 
+                return false; 
+            } 
+ 
+            if (other.b5insens && !b5insens) { 
+                return true; 
+            } 
+ 
+            if (max_offset > other.max_offset) { 
+                return false; 
+            } 
+ 
+            return true; 
+        } 
+    }; 
+ 
+    candidate best; 
+ 
+    for (u32 i = 0; i < MIN(MAX_ACCEL_OFFSET, first.s.length()); i++) { 
+        candidate curr(first, i); 
+ 
+        /* check to see if this pair appears in each string */ 
+        for (const auto &lit_ptr : lits) { 
+            const AccelString &lit = *lit_ptr; 
+            if (lit.nocase && ourisalpha(curr.c)) { 
+                curr.b5insens = true; /* no choice but to be case insensitive */ 
+            } 
+ 
+            bool found = false; 
+            bool found_nc = false; 
+            for (u32 j = 0; 
+                 !found && j < MIN(MAX_ACCEL_OFFSET, lit.s.length()); j++) { 
+                found |= curr.c == lit.s[j]; 
+                found_nc |= (curr.c & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR); 
+ 
+                if (curr.b5insens) { 
+                    found = found_nc; 
+                } 
+            } 
+ 
+            if (!curr.b5insens && !found && found_nc) { 
+                curr.b5insens = true; 
+                found = true; 
+            } 
+ 
+            if (!found) { 
+                goto next_candidate; 
+            } 
+        } 
+ 
+        /* check to find the max offset where this appears */ 
+        for (const auto &lit_ptr : lits) { 
+            const AccelString &lit = *lit_ptr; 
+            for (u32 j = 0; j < MIN(MAX_ACCEL_OFFSET, lit.s.length()); j++) { 
+                bool found = false; 
+                if (curr.b5insens) { 
+                    found = (curr.c & CASE_CLEAR) == (lit.s[j] & CASE_CLEAR); 
+                } else { 
+                    found = curr.c == lit.s[j]; 
+                } 
+ 
+                if (found) { 
+                    assert(j + mask_overhang(lit) <= MAX_ACCEL_OFFSET); 
+                    ENSURE_AT_LEAST(&curr.max_offset, j + mask_overhang(lit)); 
+                } 
+            } 
+        } 
+ 
+        if (curr > best) { 
+            best = curr; 
+        } 
+ 
+    next_candidate:; 
+    } 
+ 
+    if (!best.valid) { 
+        return false; 
+    } 
+ 
+    if (!best.b5insens) { 
+        aux->verm.accel_type = ACCEL_VERM; 
+        aux->verm.c = best.c; 
+        DEBUG_PRINTF("built verm for %02hhx\n", aux->verm.c); 
+    } else { 
+        aux->verm.accel_type = ACCEL_VERM_NOCASE; 
+        aux->verm.c = best.c & CASE_CLEAR; 
+        DEBUG_PRINTF("built verm nc for %02hhx\n", aux->verm.c); 
+    } 
+    aux->verm.offset = verify_u8(best.max_offset); 
+ 
+    return true; 
+} 
+ 
+static 
+void filterLits(const vector<AccelString> &lits, hwlm_group_t expected_groups, 
+                vector<const AccelString *> *filtered_lits, u32 *min_len) { 
+    *min_len = MAX_ACCEL_OFFSET; 
+ 
+    for (const auto &lit : lits) { 
+        if (!(lit.groups & expected_groups)) { 
+            continue; 
+        } 
+ 
+        const size_t lit_len = lit.s.length(); 
+        if (lit_len < *min_len) { 
+            *min_len = verify_u32(lit_len); 
+        } 
+ 
+        DEBUG_PRINTF("lit: '%s', nocase=%d, groups=0x%llx\n", 
+                     escapeString(lit.s).c_str(), lit.nocase ? 1 : 0, 
+                     lit.groups); 
+        filtered_lits->push_back(&lit); 
+    } 
+} 
+ 
+static 
+bool litGuardedByCharReach(const CharReach &cr, const AccelString &lit, 
+                           u32 max_offset) { 
+    for (u32 i = 0; i <= max_offset && i < lit.s.length(); i++) { 
+         unsigned char c = lit.s[i]; 
+         if (lit.nocase) { 
+             if (cr.test(mytoupper(c)) && cr.test(mytolower(c))) { 
+                 return true; 
+             } 
+         } else { 
+             if (cr.test(c)) { 
+                 return true; 
+             } 
+         } 
+    } 
+ 
+    return false; 
+} 
+ 
+static 
+void findForwardAccelScheme(const vector<AccelString> &lits, 
+                            hwlm_group_t expected_groups, AccelAux *aux) { 
+    DEBUG_PRINTF("building accel expected=%016llx\n", expected_groups); 
+    u32 min_len = MAX_ACCEL_OFFSET; 
+    vector<const AccelString *> filtered_lits; 
+ 
+    filterLits(lits, expected_groups, &filtered_lits, &min_len); 
+    if (filtered_lits.empty()) { 
+        return; 
+    } 
+ 
+    if (findDVerm(filtered_lits, aux) 
+        || findSVerm(filtered_lits, aux)) { 
+        return; 
+    } 
+ 
+    /* look for shufti/truffle */ 
+ 
+    vector<CharReach> reach(MAX_ACCEL_OFFSET, CharReach()); 
+    for (const auto &lit : lits) { 
+        if (!(lit.groups & expected_groups)) { 
+            continue; 
+        } 
+ 
+        u32 overhang = mask_overhang(lit); 
+        for (u32 i = 0; i < overhang; i++) { 
+            /* this offset overhangs the start of the real literal; look at the 
+             * msk/cmp */ 
+            for (u32 j = 0; j < N_CHARS; j++) { 
+                if ((j & lit.msk[i]) == lit.cmp[i]) { 
+                    reach[i].set(j); 
+                } 
+            } 
+        } 
+        for (u32 i = overhang; i < MAX_ACCEL_OFFSET; i++) { 
+            CharReach &reach_i = reach[i]; 
+            u32 i_effective = i - overhang; 
+ 
+            if (litGuardedByCharReach(reach_i, lit, i_effective)) { 
+                continue; 
+            } 
+            unsigned char c = i_effective < lit.s.length() ? lit.s[i_effective] 
+                                                           : lit.s.back(); 
+            if (lit.nocase) { 
+                reach_i.set(mytoupper(c)); 
+                reach_i.set(mytolower(c)); 
+            } else { 
+                reach_i.set(c); 
+            } 
+        } 
+    } 
+ 
+    u32 min_count = ~0U; 
+    u32 min_offset = ~0U; 
+    for (u32 i = 0; i < MAX_ACCEL_OFFSET; i++) { 
+        size_t count = reach[i].count(); 
+        DEBUG_PRINTF("offset %u is %s (reach %zu)\n", i, 
+                     describeClass(reach[i]).c_str(), count); 
+        if (count < min_count) { 
+            min_count = (u32)count; 
+            min_offset = i; 
+        } 
+    } 
+ 
+    if (min_count > MAX_SHUFTI_WIDTH) { 
+        DEBUG_PRINTF("FAIL: min shufti with %u chars is too wide\n", min_count); 
+        return; 
+    } 
+ 
+    const CharReach &cr = reach[min_offset]; 
+    if (-1 != 
+        shuftiBuildMasks(cr, (u8 *)&aux->shufti.lo, (u8 *)&aux->shufti.hi)) { 
+        DEBUG_PRINTF("built shufti for %s (%zu chars, offset %u)\n", 
+                     describeClass(cr).c_str(), cr.count(), min_offset); 
+        aux->shufti.accel_type = ACCEL_SHUFTI; 
+        aux->shufti.offset = verify_u8(min_offset); 
+        return; 
+    } 
+ 
+    truffleBuildMasks(cr, (u8 *)&aux->truffle.mask1, (u8 *)&aux->truffle.mask2); 
+    DEBUG_PRINTF("built truffle for %s (%zu chars, offset %u)\n", 
+                 describeClass(cr).c_str(), cr.count(), min_offset); 
+    aux->truffle.accel_type = ACCEL_TRUFFLE; 
+    aux->truffle.offset = verify_u8(min_offset); 
+} 
+ 
+void buildForwardAccel(HWLM *h, const vector<AccelString> &lits, 
+                       hwlm_group_t expected_groups) { 
+    findForwardAccelScheme(lits, expected_groups, &h->accel1); 
+    findForwardAccelScheme(lits, HWLM_ALL_GROUPS, &h->accel0); 
+ 
+    h->accel1_groups = expected_groups; 
+} 
+ 
+} // namespace ue2