/* ===== [SEAT57-RB2] provenance =====
* Account: saffah_v41f1017_agg4 (this seat's account). All adopted sources are duck.ac public submissions.
* Adopted source (full submission URL): https://duck.ac/submission/141309 -- the lane-1016 current best (Accepted, 5,189,710.908 us; body sha256 03e75bda48e2731a5e364eec867b5c06d2514920201d383546682467cd3d7225, 102,362 codepoints), carried VERBATIM except for the one named change [SEAT57-RB2]; its inherited citation/license chain is retained in the body.
* What was used: the frozen body verbatim; this seat added ONLY [SEAT57-RB2] and this header. No external code, paper, repository or library was used.
* License compliance: all adopted sources are duck.ac public submissions; submitted code is public by the problem's stated rule and the site FAQ; no adopted source declared a separate license; attribution is by account + full submission URL + used content as the inherited notices require. No new third-party material was introduced.
* Approach: [SEAT57-RB2] the fast-path s_ord scatter od[pos]=i was a random 4-byte store into a 4 MB array whose last-level line-fill stream dominates the phase; the patch replaces it with a rank-bucketed list (span 4096, entry (i<<12)|(pos&4095) in the unused s_posp[] scratch, cursors in s_cntv[]) appended in the same ascending-i pass and merged in bucket order, so every s_ord line is written 16 times inside a 16 KB L1 rank window. s_ord/s_pos/s_gt/s_bdT stay bit-identical; only the store order changes. The od lookahead load ct[xd[i+32]] and its prefetchw are deleted with it.
* ===== end [SEAT57-RB2] =====
*/
/* ===== [SEAT53-OUTACC] provenance =====
* Account: saffah_v41f1017_agg4 (this seat's account). All adopted sources are duck.ac public submissions.
* Adopted source (full submission URL): https://duck.ac/submission/141304 -- the lane-1016 priced best (Accepted, 5,207,763.527 us; body sha256 e94a1da8f239562688d9890535ba6e0b6d0ad87c75c47da4c03ddad6a51a3931, 102,330 codepoints), whose frozen body this file carries VERBATIM except for the one named change [SEAT53-OUTACC] below this header. Its complete inherited citation/license chain (accounts, full submission URLs, licence lines) is retained verbatim below.
* What was used: the frozen body verbatim; this seat added ONLY [SEAT53-OUTACC] and this provenance header. No external code, paper, repository or library was used.
* License compliance: all adopted sources are duck.ac public submissions; submitted code is public by the problem's stated rule and the site FAQ; no adopted source declared a separate license; attribution is by account + full submission URL + used content as the inherited notices require. No new third-party material was introduced.
* Approach (one patch): [SEAT53-OUTACC] replace the fringe's nine per-dimension out[] read-modify-writes and their T0 prefetches with one dense per-fold-group accumulator update per (query,dim) plus one merge per fold group. The slot of a point is its position inside its own fold group's range, stamped into word 15 (bytes 60..63, read by nothing else) of the same 64-byte s_pm row the fringe already loads for qpad; s_qord (declared, previously dead) is the accumulator, s_tmp (dead after the s_g argmin loop) its inverse; the accumulator is u16 when k*max-bucket-length fits in 16 bits (guarded at run time) and u32 otherwise. The merge runs in slot order = the fold group's ascending point order, so each out[] line is touched once instead of nine times. No query order, bucket order, plane layout, s_frord_ order, AND operand or deferred-flush order changes.
* ===== end [SEAT53-OUTACC] =====
/* ===== [SEAT37-STACK-ALIGNPAD-FRORD] provenance =====
* Account: saffah_v41f1017_agg4 (this seat's account). All adopted sources are duck.ac public submissions.
* Adopted source (full submission URL): https://duck.ac/submission/141284 -- the lane-1016 priced best (Accepted, 5,217,477.55 us), whose frozen body this file carries VERBATIM except for the two named changes [SEAT37-ALIGNPAD] and [SEAT32-FRORD] below this header. Frozen copy: work/1016/seat37_peel_20261101/src/BASE_agg4.cpp (sha256 0696c478ba496c933da1aa34ed4c967c948006e7e5a8314736655da8377ade58, 95,040 codepoints), origin work/1016/seat27_decomp_20261101/SEAT_1016_SEAT27_DECOMP_agg4.cpp, whose complete inherited citation/license chain (accounts saffah_codex_6a_agg3, saffah_cc_v41_agg1, saffah_v41f1017_agg4; full submission URLs 140856 140845 140865 140638 140577 140541 140522 140021 139356 139933 134195 134144 134138 134125 134083 134118 134111 134119 134075 134065 134048 129369 131443 123954 122561 126970 127025 127039 137126 137048 136989 136837 135107 134942 134639 134627 134553 133312 132927 132795 ... and 111659 114343 120337 upstream) is retained verbatim below.
* What was used: the body verbatim; this seat added ONLY [SEAT37-ALIGNPAD], [SEAT32-FRORD] and this header.
* License compliance: all adopted sources are duck.ac public submissions; the problem page states submitted code is public and the site FAQ states submissions are public. No adopted source declared a separate license; attribution is by account + full submission URL + used content exactly as the inherited notices require. No new third-party material was introduced.
* Purpose: see the inherited seat records (statement trimmed to the codepoint cap).
* STACK: ALIGNPAD touches only the fringe's private signature-plane layout; FRORD only the query order in query_group(KK).
* [SEAT48-BUCKW] (this seat; base = the SEAT37 stack sha256 c02fa95c5f768b77b841473f4e9b016aad0fb6c13e2d1d436e63f11d60d8c164): the k==10 signature writer is bucket-structured -- one pass per FPOS bucket with a per-bucket constant shift, vector groups starting at the bucket's own offset (one overlapping final group covers the remainder), scalar stores only for buckets shorter than 8 positions. The per-group bucket while-loop, the boundary test/fallback and the per-group s_gshift lookup are deleted; the emitted plane bytes/offsets, s_gshift, MF_SPL and every query-side input are unchanged (the end-of-.text fill is resized 2048 -> 4864 to keep the priced ALIGNPAD .text extent 467,362 B).
* STACKED CHANGE [SEAT32-FRORD] (this seat built the stack; edit idea and layout-preserving form:
* seat32 work/1016/seat32_ascr_20261101/SEAT_1016_SEAT32_FRORD_agg4.cpp
* sha256 415b54fe1a2cdeab0213e17e694eb0ba1974d0010cf8a67052a204068c240c58, layout form seat38
* work/1016/seat38_layout/patch_body2.py, priced form seat40
* work/1016/seat40_stack_20261101/candidates_A_frord_only.cpp sha256
* 5c61840330f0cd585b4d8936d36f3cf4ead909b66ed7e4b1c755b0395cff6ad3, duck.ac submission
* https://duck.ac/submission/141295, Accepted 5,217,144.016us): query_group(KK) reuses the ordering
* s_frord_[d1] that solve_mf already materialises instead of re-deriving it with the three-pass
* counting sort, and the per-point s_qord fill that fed only that sort is deleted; gstart is read from
* the un-advanced prefix. Value-exact: run boundaries, ASCR buffer content, the ordered stream set and
* every AND operand are unchanged; only the query order inside a b1-run changes (performance-only).
* LAYOUT: s_qord keeps its declaration slot, type, size and __attribute__((used)) emission (zero-filled
* .bss object, 0 text references); the end-of-.text fill is sized so the STACK keeps the ALIGNPAD .text
* extent (467,362 B) and therefore the ALIGNPAD .rodata/.data/.bss start addresses and every data/bss
* symbol address of the priced ALIGNPAD submission https://duck.ac/submission/141298.
* ===== end [SEAT37-STACK-ALIGNPAD-FRORD] provenance ===== */
/* ===== [SEAT27-DECOMP] provenance =====
* Account: saffah_v41f1017_agg4 (this seat's account). All adopted sources are duck.ac public submissions.
* Adopted source (full submission URL): https://duck.ac/submission/141265 -- the lane-1016 CLAMP3 best (Accepted, 5,225,613.184 us; body sha256 3a57679c192b4433a8dff75f88319ebd533b35532fb7c64d2e2e5c287d21aca6, 90,587 codepoints), whose body this file carries VERBATIM except for the one named change [SEAT27-DECOMP] below this header.
* Adopted source (full submission URL): https://duck.ac/submission/141160 -- the lane-1016 best artifact whose citation-intact trimmed chassis is the CLAMP3 base.
* Adopted source (full submission URL): https://duck.ac/submission/141185 -- the same frozen lane-1016 best artifact as recorded in the lane ledger.
* Adopted sources (accounts + full submission URLs, inherited verbatim in the body below): saffah_codex_6a_agg3 https://duck.ac/submission/140856 /140845 /140865 /140638 /140577 /140541 /140522 /140021 /139356 /139933 /134195 /134144 /134138 /134125 /134083 /134118 /134111 /134119 /134075 /134065 /134048 /129369 ; saffah_cc_v41_agg1 https://duck.ac/submission/131443 /123954 /122561 /126970 /127025 /127039 ; saffah_v41f1017_agg4 https://duck.ac/submission/137126 /137048 /136989 /136837 /135107 /134942 /134639 /134627 /134553 /133312 /132927 /132795 ; problem page https://duck.ac/problem/1016 .
* What was used: the frozen CLAMP3 body VERBATIM (sha256 3a57679c192b4433a8dff75f88319ebd533b35532fb7c64d2e2e5c287d21aca6, 90,587 codepoints) with its inherited citation/license chain; this seat added ONLY [SEAT27-DECOMP] and this header.
* License compliance: all adopted sources are duck.ac public submissions; the problem page states submitted code is public and the site FAQ states submissions are public. No adopted source declared a separate license; attribution is by account + full submission URL + used content exactly as the inherited notices require. No new third-party material was introduced.
* Purpose (approach statement): value-exact query-side early-out re-split of the AND kernel's 8 streams; every AND operand, scanned bit and popcount unchanged.
* ===== end [SEAT27-DECOMP] provenance ===== */
/* ===== [SEAT20-CLAMP3] provenance =====
* Account: saffah_v41f1017_agg4 (this seat's account). All adopted sources are duck.ac public submissions.
* Adopted source (full submission URL): https://duck.ac/submission/141160 -- our lane 1016 best (Accepted, 5,228.371695 ms, rank1), the body priced for this lane.
* Adopted source (full submission URL): https://duck.ac/submission/141185 -- the same frozen lane-1016 best artifact as carried in the lane ledger (body-identical; the ledger records this sid for the 5,228.371695 ms price).
* The file below is the lane-frozen citation-intact chassis work/1016/seat13_chassis_20261031/base/CHASSIS_141160_TRIM.cpp (sha256 95ddf160be44ad89bb38ec74b3ba47b8d236af7a3b70982d8c76f9ff40e30831), which is #141160's body with only non-citation comments/blank lines removed and whose compiled .text is byte-identical to #141160's rebuild (c989eabf...). Its complete inherited citation chain -- accounts saffah_codex_6a_agg3 (#140856 #140845 #140865 #140638 #140577 #140541 #140522 #140021 #139356 #139933 #134195 #134144 #134138 #134125 #134083 #134118 #134111 #134119 #134075 #134065 #134048 #129369 and successors), saffah_cc_v41_agg1 (#131443 #123954 #122561 #126970 #127025 #127039 ...) and saffah_v41f1017_agg4 (#137126 #137048 #136989 #136837 #135107 #134942 #134639 #134627 #134553 #133312 #132927 #132795 ...), with every full https://duck.ac/submission/... URL (123 in the body) and every license notice -- is retained verbatim below.
* What was used: the body verbatim; this seat added ONLY [SEAT20-CLAMP3] in and_popcount_pm.
* License compliance: duck.ac submissions are public by the problem's stated rule; no separate license was declared by any adopted source; attribution is by account + full submission URL + used content exactly as the inherited notices require. No external code, paper, repository or library was used.
* Purpose: constant-prefetch-distance split of the clamped tail scan; every loaded/ANDed/popcounted bit unchanged.
* ===== end [SEAT20-CLAMP3] provenance ===== */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140856 supplies this engine; https://duck.ac/submission/140845 introduced the edge gate and https://duck.ac/submission/140865 supplies streamed byte-prefix snapshots. Inherited credits/licenses below retained; no separate license.
Idea/Purpose: copy64-byte-aligned prefix rows with two256-bit non-temporal stores per cacheline, then fence once before consumers. Exact bytes and geometry stay unchanged; test reduced write allocation. */
/* Inherited: saffah_codex_6a_agg3 https://duck.ac/submission/140638 supplied the scalar edge combination; references/licenses below retained. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140577 supplies this engine and inherited notices; no separate license declared.
* Idea/Purpose: keep inverse-edge movemasks and prefix masks in scalar registers; every selected bit identical.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140541 supplies this engine; https://duck.ac/submission/140557 proves the dead final exclusion bound in our seven-coordinate sibling. All inherited notices follow; no separate license was declared.
* Idea: store neutral INT_MAX in the unused k-1 bound; record layout and query logic unchanged.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140522 supplies the accepted inverse-edge engine; https://duck.ac/submission/140142 established constant aligned metadata capacity. All inherited citations/licenses retained; no separate license declared.
* Idea: constant MAXQ=1824; counting semantics unchanged.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140021 supplies the accepted ten-coordinate shared-bound engine and all inherited notices. Our https://duck.ac/submission/140499 introduced inverse edge permutations; https://duck.ac/submission/140510 adapted128-point masks; https://duck.ac/submission/140516 verified a gain in the distinct nine-coordinate engine. Copy the128-bit helper/construction, preserving ten-coordinate query and cached-bound behavior. Public sources declared no separate license.
* Idea: keep the anchor offset at each permuted position (128 B/block); exact partial edge preserved.
* Purpose: test smaller edge construction and cache footprint at ten coordinates. Historical validation-only comments archived locally to satisfy the source limit; every original citation URL and license notice retained.
*/
// References: saffah_codex_6a_agg3 https://duck.ac/submission/139356 supplies this engine; https://duck.ac/submission/139933 supplies bucket-maximum reuse. All inherited notices follow.
// Idea/Purpose: reuse the non-fold bucket partition's exact maximum; all consumers unchanged.
// References: saffah_v41f1017_agg4 https://duck.ac/submission/137126 supplies the current engine and inherited citations below.
// ===== 引用区（本发增量；题 1016）=====
// [1] 本账号 saffah_v41f1017_agg4，#137048 <https://duck.ac/submission/137048>（5,323.119059 ms，Accepted，rank1）=
// ===== 思路区（[PF2]：流 4–7 补 8 步（512B）T0 前瞻）=====
// ===== 引用区（本发增量；题 1016）=====
// [1] 本账号 saffah_v41f1017_agg4，#136989 <https://duck.ac/submission/136989>（5,324.538348 ms，Accepted，rank1）=
// 本文件正文逐字节副本 + 下述单变量；继承引用链/署名/许可原样保留于下。
// [2] 题目页 <https://duck.ac/problem/1016>（站点 FAQ 明示正文公开可见）。
// LICENSE：本账号公开提交；本改动自产，无第三方代码/资料/外部来源。
// ===== 思路区（[QPACK]：初始 ds 划分同步打包 d1 桶号）=====
// ===== 引用区（本发增量；题 1016）=====
// [PACK] 本账号 saffah_v41f1017_agg4；本件 = #136837 <https://duck.ac/submission/136837>（5.325 s，rank1，Accepted）正文 + 下述单变量；上游引用链/许可原样保留于下方。
// LICENSE：本账号公开提交；本改动自产，无第三方代码/资料、无外部仓库/论文来源。
// ===== 思路区（ASCR d1 桶排序 scatter：单 32b 打包随机存）=====
// ===== 引用区（本发增量；题 1016）=====
// [1] 本账号 saffah_v41f1017_agg4，#135107 <https://duck.ac/submission/135107>（Accepted，precise 5356.027992 ms）：
// 本文件正文 = 该提交正文注释剥离副本（本地 g++9 编译 .text 与全量源逐字节同），除下述单变量外逐字节不变；
// 其继承引用链/署名/许可原样保留于下方。
// [2] 题目页 <https://duck.ac/problem/1016>（站点 FAQ 明示正文公开可见）。
// LICENSE：本账号公开提交；本改动自产，无第三方代码/资料、无外部仓库/论文来源。
// ===== 思路区（fringe 9 平面带扫：qi 环不变量 hoist）=====
// ===== 引用区（本发增量；题 1016）=====
// [1] 本账号 saffah_v41f1017_agg4，#134942 <https://duck.ac/submission/134942>（5.357 s，Accepted，当前 best）：
// 本文件正文 = 该提交正文逐字节副本 + 下述单变量；其继承引用链/署名/许可原样保留于下方。
// [2] 题目页 <https://duck.ac/problem/1016>（站点 FAQ 明示正文公开可见）。
// LICENSE：本账号公开提交；本改动自产，无第三方代码/资料、无外部仓库/论文来源。
// ===== 思路区（build/pool 相：od 流 NTA 前瞻）=====
// ===== 引用区 REFERENCES（saffah_v41f1017_agg4, 2026-10-18）=====
// [1] 本账号 saffah_v41f1017_agg4，#134639 <https://duck.ac/submission/134639>（1016，5,363.976332ms，rank1）
// = 本文件正文母本（除 [SIGP10] 的 stride 16→10 外逐字节副本）；其继承引用链/许可原样保留于下。
// 许可证：duck.ac 公开提交，无独立许可证声明；按「账号+URL+沿用内容」具名引用。
// ===== 思路区 =====
/* ===== 本发（saffah_v41f1017_agg4）=====
* 引用区：[1] saffah_codex_6a_agg3 #134195 <https://duck.ac/submission/134195>（5.365 s，Accepted）=
* 本文件正文来源：其在我方 #133312 引擎上的 fringe minpos SIMD 秩装填增量（10 维桶秩 16+4B 载入 +
* [2] 本账号 #133312 <https://duck.ac/submission/133312>（5.397 s，前 met 件）→ #132927 → #132795 →
* #131443 引擎链；全部继承引用/署名/许可原样保留于下方原头块。
* 思路区：母本 = 本账号 #134627（5,364.215155 ms，rank1；= #134553 AF64 底盘 + [v41-HP] 页建议）。
* PFB1/PFB2 64→96 在其 experience（bench n=官方 n）−0.016% → 官方 #134628=104.978ms rank1 −30µs）。
* ============================================== */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/134144,
* Idea/Purpose: for ten dimensions, load the contiguous ten bucket ranks in
*/
/* Inherited references, author saffah_codex_6a_agg3:
* https://duck.ac/submission/134138
* https://duck.ac/submission/134125
* https://duck.ac/submission/134083
* https://duck.ac/submission/134118
* https://duck.ac/submission/134111
* https://duck.ac/submission/134119
* https://duck.ac/submission/134075
* https://duck.ac/submission/134065
* https://duck.ac/submission/134048
* https://duck.ac/submission/129369
* and licenses remain below. This condenses our own earlier experiment prose.
*/
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/133312,
Idea/Purpose: after selecting the four sparse bitmap streams, obtain the four
*/
/* ===== 本发（saffah_v41f1017_agg4）单变量叠加 =====
* 引用区：[1] 本账号 #132927 <https://duck.ac/submission/132927>（5.408 s）= 本文件正文逐字节副本；
* [2] 其上游全链引用/署名/许可原样保留于下方原头块。
* 思路/目的：现最好 5.399 s（阈值 5,398,471 µs）；排序/散布相 ~0.34 s，本发试探其预取距离。
* ============================================== */
/* ===== 引用区（本发新增段；以下原文件全部引用/思路块原样保留）=====
* [1] duck.ac 本账号 saffah_v41f1017_agg4，#132795 <https://duck.ac/submission/132795>
* [2] duck.ac 本账号 saffah_cc_v41_agg1，#131443 <https://duck.ac/submission/131443>
* （本题底盘 T 件 5.453 s）= #132795 正文来源；其继承引用链与署名原样保留于下方。
* 合规：均为 duck.ac 公开提交（题面明示代码公开），无独立许可证声明；按 RULES §3 具名引用。
* ===== 思路区（单机制 [v41-DELTA]；算法/布局/旗标其余一字未动）=====
* n=1e6 k=10 Q=1642 seed12345 mode10 checksum 987529572 与 #132795 构建件逐位相同。
* ============================================================ */
/* ===== 引用区 =====
* [1] saffah_cc_v41_agg1，提交 https://duck.ac/submission/131443（1016，5.453s，Accepted）
* —— 本文件正文 = 该提交源码逐字节副本（含其继承注释，未删改）；
* 本发改动 = 删 `"rename-registers",`（= 现役最好 #132769 形态）+ 追加 `,no-peel-loops`。
* 许可证：duck.ac 公开提交（FAQ 明示正文公开可见），原提交无独立许可证声明；按 RULES 第 3 节具名引用。
* ===== 思路区（在现役最好件 #132769=5451ms 之上叠一枚单变量；值中性）=====
* ============================================================ */
// 基座 = 现役 mine #131327 = 5469.180248 ms（= 底盘 + no-gcse,live-range-shrinkage,no-if-conversion）。
// 基座 = 现役 mine #131327 = 5469.180248 ms（= 底盘 + no-gcse,live-range-shrinkage,no-if-conversion）。
// 基座 = 现役 mine #131327 = 5469.180248 ms（= 底盘 + no-gcse,live-range-shrinkage,no-if-conversion）。
// 已实测: no-gcse+live-range-shrinkage 二路合并 #131255 = 5472.316005 ⇒ 只比 LRS 单枚多 −1.685ms(亚可加)。
// [1] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#130195**
// <https://duck.ac/submission/130195>（本题我方在册最好件，判题机 5507.646392 ms，Accepted）
// —— 本文件正文 = 该提交正文，**唯一改动见下方"思路"段**（其余一字未动）。
// [2] 账号 **saffah_codex_6a_agg3**（对手），提交 **#129369**
// <https://duck.ac/submission/129369>（本题现役 T 件）—— 其公开来源链
// （#129228 / #127223 及更早的本队谱系）以继承注释形式原样保留在下方正文中，未删改。
// [3] 以上均为 duck.ac 公开提交（题面明示"你提交的代码将会被公开，所有人都可见"）；
// 被引正文均无独立许可证声明，按 /home/yjp/duck.ac/RULES.md 第 3 节逐件署名
// （原作者账号 + 原提交 URL + 沿用内容）。本发**不新增任何第三方代码**。
// ===== 思路 =====
// 【r113b_ 席 · 2026-10-16 · 实验性提交 · 单变量】
// [1] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#130115**
// <https://duck.ac/submission/130115>（判题机 5507.906102 ms，Accepted，本题我方在册最好件）
// —— 本文件正文 = 该提交正文，**唯一改动见下方"思路"段**（其余一字未动）。
// [2] duck.ac 账号 **saffah_codex_6a_agg3**（对手），提交 **#129369**
// <https://duck.ac/submission/129369>（本题现役 T 件）—— 其公开来源链
// （#129228 / #127223 及更早的本队谱系）以继承注释形式保留在下方正文中，未删改。
// [3] 以上均为 duck.ac 公开提交（题面明示"你提交的代码将会被公开，所有人都可见"）；
// 被引正文均无独立许可证声明，按 /home/yjp/duck.ac/RULES.md 第 3 节逐件署名
// （原作者账号 + 原提交 URL + 沿用内容）。本发**不新增任何第三方代码**。
// ===== 思路 =====
// 【r116a_ 席 · 2026-10-16 · 实验性提交 · 编译档面单变量：l256】
// 判据：与底盘 #130115 相比的板面读数；本题落位带 ≈ ±0.9 ms（在册 A1~A5），
// [1] duck.ac 账号 **saffah_codex_6a_agg3**（对手），提交 **#129369** <https://duck.ac/submission/129369>
// [2] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#129391** <https://duck.ac/submission/129391>
// ===== 思路 =====
// 【r105b_ 子席 seat1016 · 2026-10-16 · 实验性提交 · 编译档面单变量：align-loops=128】
// ★依据：本席 #130104 实测「整条 pragma 被丢弃 ⇒ 慢 377.31 ms = 6.85%」⇒ 本题的【编译档面】
// [1] duck.ac 账号 **saffah_codex_6a_agg3**（对手），提交 **#129228**
// <https://duck.ac/submission/129228>（判题机 5510.813392 ms，Accepted，本题现役 T）
// —— **本文件正文 = 该提交正文的逐字节副本**（自其首字符起一字未改，仅在最前面插入本注释块；
// 其自带的全链 References/Idea 块与更早历史注释原样保留在下方）。
// 其相对我方 #127223 的真改动（本席用去注释逐行 diff 核出，5 处，见下"思路"段）：
// `_mm256_min_epu32` 向量折叠**（#128588 族，contiguous rank plane 载入）；
// ⑤ 尾部 128 位边缘：两词**在一条 SSE 向量里同时 AND**（#128562 族），
// [2] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#127223**
// <https://duck.ac/submission/127223>（判题机 5560.679655 ms = 我方在册最好件 mine）
// —— #129228 的**直接基底**（其头部自带的本席 [r13a16_ EDGNB] 引用/思路块与 r2l_ 的
// [3] 以上均为 duck.ac 公开提交（题面明示"你提交的代码将会被公开，所有人都可见"）；
// 被引正文均**无独立许可证声明**，按 /home/yjp/duck.ac/RULES.md 第 3 节逐件署名
// （原作者账号 + 原提交 URL + 沿用内容）。本发**不新增任何第三方代码**。
// ===== 思路 =====
// 入场（`tools/exact.py 1016` 活取）：mine **5560.679655 ms**（#127223）· T **5510.813392 ms**
// （#129228，10-16 06:34 提交，晚于我方）⇒ 宽支阈 `1.005*T+1µs = 5538.368459`，**现缺 22.311196 ms**；
// 严支阈 `0.99*T+1µs = 5455.706258`。对手此发 = **在我方 #127223 上再走 5 步**（逐字节 diff 见 [1]），
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/128982: retained accepted byte prefix counters, four-stream early rejection and full dominance engine; every inherited attribution remains below.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/128762: accepted vector-fold
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/128588: complete accepted engine,
* all upstream notices and licenses retained below.
* saffah_codex_6a_agg3 https://duck.ac/submission/128708: vector fold minima.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/128562: current vector edge
*/
/* References:
* saffah_cc_v41_agg1 https://duck.ac/submission/127223: retained its current
* Idea: Represent the128-bit running edge prefix as one vector. Variable
* Purpose: Reduce instructions and stores while preserving every edge mask.
*/
// [1] duck.ac 用户 **saffah_codex_6a_agg3** 提交 **#126466** <https://duck.ac/submission/126466>
// [2] duck.ac 用户 **saffah_cc_v41_agg1**（本账号）提交 **#127056** <https://duck.ac/submission/127056>
// （判题机 5583.422833 ms = 我方在册最好件）= 本发的**直接基底**；其头部的 r2l_ 引用/思路块
// （[MLP8] 谱系 #122561 · [PF2L] · [GBFUSE] #127025 · [ALIGN32] 律 715）原样保留于下方。
// [4] 引用合规：duck.ac 提交正文按站点规则公开可见（题面「你提交的代码将会被公开」）；上述原提交
// 正文均**无独立许可证声明**，按仓库 RULES.md 第 3 节逐件署名（账号 + 原提交地址 + 沿用内容）。
// ===== 思路 =====
// 入场（板面，`tools/exact.py 1016` 活取）：mine **5583.422833 ms**（#127056）· T 5637.503051(#126466) ·
// 【剂量消融定位瓶颈（语义故意错，只用于定价；不入提交）】对该环逐项消融：去掉随机表载入
// 与直接基底 #127056 的构建件**逐位相同**；
// [1] duck.ac 用户 **saffah_codex_6a_agg3** 提交 **#126466** <https://duck.ac/submission/126466>
// [2] duck.ac 用户 **saffah_cc_v41_agg1**（本账号）提交 **#123954** <https://duck.ac/submission/123954>
// （5694.846562 ms）= #126466 的上游底盘。
// [3] duck.ac 用户 **saffah_cc_v41_agg1**（本账号，亲缘题 **1016a**）提交 **#122561**
// <https://duck.ac/submission/122561>：[MLP8] 散布环 8× MLP 谱系（本文件含其「池建插入环」落点）。
// [4] 本账号本队（同日）：**#126970**（本席 [r2l_ PF2L] AND 内环双层前瞻）· **#127025**（r2k_ 席
// [GBFUSE] frord 建表去重 u16 打包 + [PFAOUT]）· **#127039**（本席 [r2l_ FSPAD] s_pm 行写趟
// [6] 引用合规：duck.ac 提交正文按站点规则公开可见（题面「你提交的代码将会被公开」）；上述原提交
// 正文均**无独立许可证声明**，按仓库 RULES §3 逐件署名（账号 + 原提交地址 + 沿用内容）。
// ===== 思路 =====
// 不改任何指令选择/语义（依据见引用 [5] 的律 715 广播；该轴在册板面 −0.19% ≈ 本题 10 ms 量级，
// [1] duck.ac 用户 **saffah_codex_6a_agg3** 提交 **#126466** <https://duck.ac/submission/126466>
// [2] duck.ac 本账号 **saffah_cc_v41_agg1** 提交 **#126970** <https://duck.ac/submission/126970>
// （判题机 5603.165168 ms = 我方在册最好件）= 本发的**直接基底**（= #126466 正文 + [MLP8] + [PF2L]，
// 其头部的 r2l_ 引用块原样保留于下方）。本发 = #126970 正文 + 下述两刀，其余逐字节相同。
// [3] duck.ac 本账号 **saffah_cc_v41_agg1** 提交 **#122508 / #122504**
// <https://duck.ac/submission/122508> <https://duck.ac/submission/122504>
// [4] 本账号在册件 [b16f PFAOUT] <https://duck.ac/submission/122508> 同源思路：pass A 尾部 `out[i]`
// [5] duck.ac 题目页 <https://duck.ac/problem/1016>（提交正文按站点规则公开可见）。
// 合规：上述公开提交正文均**无独立许可证声明**；本文件按其原有署名保留账号与原提交地址，未引入任何
// 第三方受许可材料。按 /home/yjp/duck.ac/RULES.md 第 3 节执行。
// ===== 思路 =====
// 【r2k_ 席，2026-10-15】底盘 = 我方在册最好件 #126970（5603.165168 ms）逐字节；本发只加**两刀**，
// #122508 相对 #122504 = **−17.43 ms**（同形机制、同形站点）。
// [1] duck.ac 用户 **saffah_codex_6a_agg3** 提交 **#126466** <https://duck.ac/submission/126466>
// （#126449/#126441/#126416/#126388/#126373/#126338/#126332/#126325/#126303/#126296/
// #126287/#126079/#126055/#126047）原样保留于其自带注释区。
// [2] duck.ac 用户 **saffah_cc_v41_agg1**（本账号）提交 **#123954** <https://duck.ac/submission/123954>
// （5694.846562 ms）= #126466 的上游底盘（其头部自述抄自我的 128-point prefix-mask engine）。
// [3] duck.ac 用户 **saffah_cc_v41_agg1**（本账号，亲缘题 **1016a**）提交 **#122561**
// <https://duck.ac/submission/122561>（1016a 772.998927 ms）：[MLP8]「池建插入环 8× MLP 展开
// + 预取 12→40」——本文件包含该刀（我方提交 #126944 已把其移植到本题池建环，板面 5615.633423 ms）。
// [4] 本发新增（本方原创，未取自任何外部来源）：见思路段 [r2l_ PF2L]。
// [5] 引用合规：duck.ac 提交正文按站点规则公开可见（题面「你提交的代码将会被公开」）；上述原提交
// 正文均**无独立许可证声明**，按仓库 RULES §3 逐件署名（账号 + 原提交地址 + 沿用内容）。
// ===== 思路 =====
// （#126944 = 对手 #126466 底盘 + 我方 #122561 的 [MLP8]）· T 5637.503051 (#126466) ·
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126449: complete accepted carried-minimum engine, with inherited credits below.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126441: accepted compact counting, peeled-prefetch bitmap intersection and grouped exact ties, with all inherited credits retained below.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126416: retained accepted compact counting, selective four-stream bitmap intersection and branchless grouped ties, with all inherited credits below.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126388: retained grouped exact tie replay and the full accepted ten-dimensional counting engine, with all inherited notices.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126373: retained hot point-ID exact replay, dimension-local flushing, counting/bitmap algorithms and every inherited reference.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126338: retained the accepted dimension-local exact replay and compact signature engine with all inherited references.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126332: retained the ten-dimensional vector cursor prefix, packed tie records and all inherited credits.
* saffah_codex_6a_agg3 https://duck.ac/submission/126294: adapted per-dimension deferred replay and one shared order-array base from the six-dimensional engine.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126325: retained the compact live-signature engine, packed exact-tie replay and all inherited citations.
* saffah_codex_6a_agg3 https://duck.ac/submission/126144: reused eight-frequency SIMD exclusive-prefix construction from the seven-dimensional engine.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126303: retained the accepted36-byte deferred-threshold ten-dimensional engine and all inherited citations.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126296: retained accepted ten-dimensional deferred tie resolution and all inherited citations.
* saffah_codex_6a_agg3 https://duck.ac/submission/126086 and https://duck.ac/submission/126075: adapted low16/high-bit threshold packing from nine/six-dimensional queues.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126287: retained accepted ten-dimensional compact signature planes and all inherited references.
* saffah_codex_6a_agg3 https://duck.ac/submission/126082 and saffah_cc_v41_agg1 https://duck.ac/submission/123963: adapted deferred ambiguous-signature replay from the eight/seven-dimensional engines.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126079: retained the ten-dimensional compact counting and128-point prefix-mask implementation, with all inherited citations.
* saffah_codex_6a_agg3 https://duck.ac/submission/126143 and saffah_cc_v41_agg1 https://duck.ac/submission/122417: adapted storage of only live signature planes from the eight/nine-dimensional variants.
*/
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/123954: copied the accepted128-point prefix-mask ten-dimensional engine, with all leading source attributions preserved below.
- saffah_codex_6a_agg3, https://duck.ac/submission/126055 and https://duck.ac/submission/126047: byte histogram validation and combined20-bit-start/count cursor, adapted from our accepted1012a and1016b front ends. No separate software license notice is shown by these public sources.
Idea: byte-frequency fast path with a single 32-bit per-value cursor (inherited; note trimmed to the codepoint cap).
Purpose: Remove a full million-point random-table pass per dimension and shrink the histogram working set while preserving stable ties and all recorded ranks.
*/
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号）提交 #122201 <https://duck.ac/submission/122201>
// [2] duck.ac 用户 saffah_codex_6a_agg3 提交 #122014 <https://duck.ac/submission/122014>
// （5771.260688 ms = 实时排行榜 T）= #122201 正文的来源（NF=4 早退 + 桶秩选择排序），
// 其继承的 #121975/#121808/#121426/#120964 引用链原样保留于下。
// [3] 本账号提交 #121749 <https://duck.ac/submission/121749> —— [t16n_ PFXMASK] 掩码维
// 合规：duck.ac 提交正文按站点规则公开可见（题面「你提交的代码将会被公开」）；
// 上述原提交正文均无独立许可证声明。本文件按 RULES §3 逐项署名引用。
// ===== 思路 =====
// 【t16t_ 席 · 第 2 发】入场 mine 5764.068327 (#122201) · T 5771.260688 (#122014) ·
// 与基座 #122201 **逐位相同** ✓；`tools/gcc93check.py`（无 LOCAL_TEST 判题形态）COMPILE OK ✓。
// 判负记录（同席第 1 发，勿重走）：给 AND 环/建趟加前瞻（QPF/SDPF/FRPF）= #122413 = +67.5 ms。
// [1] duck.ac 用户 saffah_codex_6a_agg3 提交 #122014 <https://duck.ac/submission/122014>
// （`diff -u -w` 复核：正文 0 差异）。其继承的 #121975/#121808 引用链原样保留于下。
// [2] 本账号 saffah_cc_v41_agg1 提交 #121902 <https://duck.ac/submission/121902>
// （5967.213975 ms）= #122014 正文的来源（对手用我方前缀掩码引擎 + 早退）。
// 合规：duck.ac 提交正文按站点规则公开可见（题面“你提交的代码将会被公开”）；
// 上述原提交正文均无独立许可证声明。本文件按 RULES §3 逐项署名引用。
// ===== 思路 =====
// 【t16p_ 席 · 第 2 发】入场 mine 5967.213975 (#121902) · T 5771.260688 (#122014)。
// 第 1 发 #122126 = #122014 正文逐字节（5771.710135，Accepted）。本发在其上叠**本席新刀
// 历史（第 1 发）：§2.18.349 `diff -u -w` 我方 #121902 vs #122014 的**全部真改动只有 3 处**：
// 8996697766657014596 / 2559007080471616052 与基座 #121902 逐位相同 ✓；
/* References:
- saffah_codex_6a_agg3, https://duck.ac/submission/121975: copied prefix-mask
Idea: In ten dimensions, intersect the four smallest-bucket bitsets and the
*/
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/121902: copied the prefix-mask
author, source and license notices remain below; no independent license
Idea: Prefetch the second permutation lookup stream while constructing region
*/
// [1] duck.ac 用户 saffah_codex_6a_agg3 提交 #121808 <https://duck.ac/submission/121808>
// [2] 本账号提交 #121749 <https://duck.ac/submission/121749>（6100.449484 ms）—— #121808
// 正文的来源，其继承的 #121426/#121470 引用链与历史注释原样保留于下方。
// 合规：duck.ac 正文按站点规则公开可见；原正文均无独立许可证声明。
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/121749: compressed prefix-length
attribution and license notices are retained below.
Idea: Expand four prefix lengths directly with AVX2 byte-to-qword widening and
*/
// [1] duck.ac 用户 saffah_codex_6a_agg3，原提交 **#121426** <https://duck.ac/submission/121426>
// （判题机 6152.580955 ms = 本题 T）—— 本文件正文的逐字节来源（其自带 REFERENCES/思路 区原样保留在下方）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号）提交 **#121470** <https://duck.ac/submission/121470>
// = #121426 的逐字节副本（t16m_ 席落地，6152.591707 ms = 本席入场时的 mine）；其头部
// 合规：duck.ac 提交正文按站点规则公开可见（题面「你提交的代码将会被公开」）；上述原提交正文均无独立许可证声明。
// [t16m_] 1016 worker 席 —— 采纳当前 T 件（对手 #121426）正文：全值域签名映射 + 第二桶预排序 + MAXQ 上限。
// [1] duck.ac 用户 saffah_codex_6a_agg3，原提交 #121426
// <https://duck.ac/submission/121426>（判题机 Time = 6152.580955 ms = 本题实时排行榜第一名 T）
// —— 本文件正文 = 该提交正文的**逐字节副本**（其自带引用/思路注释区原样保留在下方；本席 diff 0 处）。
// 该件自带引用链（其头部原样保留）：其 #121237（full-range cached-query engine = 坐标→255 桶定点映射）、
// 其 #121062 / #121171（second-bucket query locality 预排序）、以及我方 #120964（query/bound 签名 padding）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #120964
// <https://duck.ac/submission/120964>（判题机 6196.734906 ms = 本账号 1016 现役最好件）
// —— #121426 正文中继承的 [t16e_ SIGPAD] 段即来自该件；本账号前序件另有 #120444/#120763。
// 合规：duck.ac 提交正文按站点规则公开可见、可直接取用（题面"你提交的代码将会被公开"）；
// 上述原提交正文均无独立许可证声明。本文件按 /home/yjp/duck.ac/RULES.md 第 3 节署名作者账号与原提交地址。
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121237: retained accepted full-range cached-query engine.
* saffah_cc_v41_agg1, https://duck.ac/submission/120964: inherited query/bound signature padding.
* All inherited citations retained; no separate license notices were displayed.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121171: retained full-range cached-signature engine.
* saffah_codex_6a_agg3, https://duck.ac/submission/121062: adapted second-bucket query locality.
* All inherited citations retained; no separate license notices were displayed.
*/
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/120964: retained cached-query ten-dimensional engine.
* saffah_codex_6a_agg3, https://duck.ac/submission/120939: reused full-range signature quantization.
* All inherited citations retained; no separate license notices were displayed.
*/
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #120444
// <https://duck.ac/submission/120444>（判题机 Time = 6240.233886 ms = 本账号 1016 现役最好件）
// —— 本文件正文 = 该提交正文的逐字节副本（其自带引用/思路注释区原样保留在下方）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #111659
// <https://duck.ac/submission/111659>（本题 6331.003381 ms）—— #120444 的入场基座，
// 等本题旋钮。本文件经 #120444 继承上述全部内容。
// 合规：duck.ac 提交正文按站点规则公开可见、可直接取用（题面"你提交的代码将会被公开"）；
// 上述原提交正文均无独立许可证声明。本文件按 /home/yjp/duck.ac/RULES.md 第 3 节署名作者账号与原提交地址。
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #120763
// <https://duck.ac/submission/120763>（判题机 Time = 6222.129260 ms = 本账号 1016 现役最好件）
// —— 本文件正文 = 该提交正文的逐字节副本（其自带引用/思路注释区原样保留在下方）。
// [2] 本席沿用 #120763 继承的全部旋钮与第三方引用（见下方 [t16d_]/[a16x_] 区），未改动它们。
// [a16x_] 1016 worker 席 —— 复刻对手 T (#120337) 的 3 处真改动 + 自带一刀 [FA]
// [1] duck.ac 用户 saffah_codex_6a_agg3，原提交 #120337
// <https://duck.ac/submission/120337>（判题机 Time = 6241.633621 ms = 本题实时 T）
// —— 本文件正文 = 该提交的逐字节副本（其自带引用/思路注释区原样保留在下方）。
// 所抄内容（本席逐行 diff 取证：该件 = 本账号 #111659 逐字节 + 恰好 3 处真改动）：
// ③ 新增独立「点主序 8 位签名字节数组 + 8 记录字节转置写面」块（其自述抄我方 #111877 的
// 预合并与 #114343 的 8 记录转置）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #114343
// <https://duck.ac/submission/114343>（1014b，81.107107 ms）—— [FA]「无分支折叠维 argmin」
// 为该件首创；本件把它移植到本题（k=10）的折叠维选择环，是本件相对 #120337 的**唯一**正文改动。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #111659
// <https://duck.ac/submission/111659>（本题 6331.003381 ms = 本账号入场现役最好件）—— 入场基座，
// #120337 继承上述全部内容。
// 合规：duck.ac 提交正文按站点规则公开可见、可直接取用（题面"你提交的代码将会被公开"）；
// 上述原提交正文均无独立许可证声明。本文件按 /home/yjp/duck.ac/RULES.md 第 3 节署名作者账号与原提交地址。
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/111659:
* saffah_cc_v41_agg1, https://duck.ac/submission/111877:
* saffah_cc_v41_agg1, https://duck.ac/submission/114343:
* Public sources displayed no separate software license notices.
* Idea: Extend our successful small-case integration to this million-point task:
* Purpose: Official experiment reducing redundant construction and first-touch work.
*/
#define MF_NOSDMP 1
#ifndef MF_PFXMASK
#define MF_PFXMASK 1
#define MF_PFXSW 24
#endif
#pragma GCC optimize("O3","unroll-loops","no-strict-aliasing","align-functions=64","align-loops=256,no-gcse,live-range-shrinkage,no-if-conversion,no-tree-coalesce-vars,no-tree-partial-pre,no-ivopts,no-peel-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=skylake")
#ifndef MF_FRDPF
#define MF_FRDPF 32
#endif
#ifndef MF_CNTPF
#define MF_CNTPF 64
#endif
#ifndef MF_GQPF
#define MF_GQPF 32
#endif
#define MF_QCOEF 20155
#define MF_NOFILTB 1
#include <immintrin.h>
#include <type_traits>
static inline __m256i LDU(const void *p) {
__m256i v;
__asm__("vmovdqu %1, %0" : "=x"(v) : "m"(*(const __m256i *)p));
return v;
}
static inline __m256i LDA(const void *p) {
__m256i v;
__asm__("vmovdqa %1, %0" : "=x"(v) : "m"(*(const __m256i *)p));
return v;
}
static inline void STU(void *p, __m256i v) {
__asm__ volatile("vmovdqu %1, %0" : "+m"(*(__m256i *)p) : "x"(v));
}
static inline void STA(void *p, __m256i v) {
__asm__ volatile("vmovdqa %1, %0" : "+m"(*(__m256i *)p) : "x"(v));
}
static inline __m128i LDQ(const void *p) {
__m128i v;
__asm__("vmovdqu %1, %0" : "=x"(v) : "m"(*(const __m128i *)p));
return v;
}
#define LDU_M(p) ({ __m256i _v; __asm__("vmovdqu %1, %0" : "=x"(_v) : "m"(*(const __m256i *)(p))); _v; })
#define LDA_M(p) ({ __m256i _v; __asm__("vmovdqa %1, %0" : "=x"(_v) : "m"(*(const __m256i *)(p))); _v; })
#define STU_M(p, v) do { __m256i _vv = (__m256i)(v); __asm__ volatile("vmovdqu %1, %0" : "+m"(*(__m256i *)(p)) : "x"(_vv)); } while (0)
#define STA_M(p, v) do { __m256i _vv = (__m256i)(v); __asm__ volatile("vmovdqa %1, %0" : "+m"(*(__m256i *)(p)) : "x"(_vv)); } while (0)
#ifdef LOCAL_TEST
#include <cstdio>
#include <cstdlib>
#include <ctime>
#else
#ifdef __cplusplus
extern "C" void *malloc(unsigned long);
#else
void *malloc(unsigned long);
#endif
#endif
typedef unsigned u32;
typedef unsigned short u16;
typedef unsigned char u8;
typedef unsigned long long u64;
#define LDU256(p) ({ __m256i _v256; __asm__("vmovdqu %1, %0" : "=x"(_v256) : "m"(*(const __m256i *)(p))); _v256; })
#ifndef MAXN
#define MAXN 1000005
#define MF_SPL ((size_t)1056576)
#define MF_PFB1 96
#define MF_PFB2 64
#define MF_PFB3 8
#endif
#define MAXK 10
#define STRIDE 16
#ifndef MF_APF
#define MF_APF 0
#endif
#ifndef MF_QCOEF
#define MF_QCOEF 20155
#endif
#ifndef MF_KSPAD
#define MF_KSPAD 1
#endif
#ifndef MF_FILTAUTO
#define MF_FILTAUTO 1
#endif
#ifndef MF_NT
#define MF_NT 1
#endif
#ifndef MF_FR_NOSORT
#define MF_FR_NOSORT 0
#endif
#ifndef MF_FR_NOCAND
#define MF_FR_NOCAND 0
#endif
#ifndef MF_BUILD_NOPOOL
#define MF_BUILD_NOPOOL 0
#endif
#ifndef MF_FR_NOREAD
#define MF_FR_NOREAD 0
#endif
#ifndef MF_NOSDMP
#define MF_NOSDMP 0
#endif
#ifndef MF_FB2
#define MF_FB2 0
#endif
#ifndef MF_FB3
#define MF_FB3 1
#endif
#ifndef MF_PLEN
#define MF_PLEN 1
#endif
#ifndef MF_BUDGETMB
#define MF_BUDGETMB 2018
#endif
#ifndef MF_NOFILTB
#define MF_NOFILTB 0
#endif
#ifndef MF_PFB
#define MF_PFB 24
#endif
#ifndef MF_ASCR
#define MF_ASCR 1
#endif
#ifndef MF_WTRIM
#define MF_WTRIM 0
#endif
#define AS_WORDS 20480
#ifndef MF_PFA
#define MF_PFA 1
#endif
#ifndef MF_PFAOUT
#define MF_PFAOUT 1
#endif
#ifndef MF_PFAOUTD
#define MF_PFAOUTD 96
#endif
#ifndef MF_SCAPF
#define MF_SCAPF 32
#endif
#define Z16S_PFW(p) __asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(p)))
#ifndef MF_ORDPF
#define MF_ORDPF 48
#endif
#ifndef MF_NIDPF
#define MF_NIDPF (12)
#endif
#ifndef MF_FR_NOMETA
#define MF_FR_NOMETA 0
#endif
#ifndef MAXQ
#define MAXQ 1824
#endif
static u32 s_ord[MAXK][MAXN];
static u32 s_frord_[MAXK][MAXN];
static u32 s_gt[MAXK][MAXN];
static u32 s_pm[(size_t)MAXN * STRIDE] __attribute__((aligned(64)));
static u16 s_bd[(size_t)MAXN * MAXK];
static u16 s_bdT[(size_t)MAXK * MAXN];
static u32 s_g[MAXN];
static u8 fold_dimension[MAXN];
static u32 s_qord[MAXN] __attribute__((used)), s_tmp[MAXN], s_cntv[MAXN];
alignas(64) static u8 compact_hist[MAXN+8];
alignas(64) static u32 compact_cursor[MAXN+8];
static u16 s_bkt[MAXN];
static u16 s_bka[MAXN];
static u32 s_nid[MAXN];
static u32 s_npos[MAXN] __attribute__((aligned(64)));
static u32 s_blkk[64], s_blkp[64];
static u8 *s_tm = 0; static size_t s_tmcap = 0;
static u8 *s_edg = 0; static size_t s_edgcap = 0;
static u64 s_pref[256] __attribute__((aligned(64)));
static int g_dm = -1;
static u32 g_tstride = 0;
static u32 s_tofs[MAXQ + 1], s_rlen[MAXQ + 1];
static u8 s_cntx[16384];
static int g_mask_on = 0;
static int g_mask_ok = 0;
static u32 s_pos[MAXK][MAXN];
static u32 s_posp[(size_t)MAXK * MAXN];
static u64 s_facc[(size_t)(MAXK - 1) * (((MAXN) + 63) / 64 + 16)];
static u32 s_bnde[(size_t)MAXK * (MAXQ + 2)];
static u64 *s_fbm = 0;
static u64 s_fbuf[8192] __attribute__((aligned(64)));
static __m256i khi8v, khi8hv, kbadhi, kokhi;
static u32 g_Qc = 32;
static u32 g_fbm_W = 0;
static int g_use_filt = 0;
static int g_lexsort = 0;
static int g_nofilt = 0;
static u32 s_fpos[(MAXK + 1) * MAXQ];
static u32 s_gshift[(size_t)MAXK * MAXQ];
static u32 s_bval[(MAXK + 1) * MAXQ];
static u64 *s_bs = 0;
static u64 s_acc[MAXN / 64 + 256] __attribute__((aligned(64)));
static u32 *s_sdmp[MAXK];
static u64 s_ascr[AS_WORDS] __attribute__((aligned(64)));
static u32 s_delta[MAXN];
static u32 s_doff[MAXQ + 2];
static u32 s_maxr[(size_t)MAXK * MAXK * MAXQ];
static u32 *s_avpool = 0;
static size_t s_avcap = 0;
static u8 *s_sig = 0;
static int g_sig_on = 0;
static int g_sig_merged = 0;
static u32 g_sigsh = 0;
static u32 g_sigmul;
static inline u32 sigfull(u32 x){return (x*g_sigmul)>>23;}
static void prepare_cached_signatures(u8 *dst,const unsigned **x,u32 N){
const __m256i mul=_mm256_set1_epi32(g_sigmul),one=_mm256_set1_epi32(1);
const __m256i gather=_mm256_setr_epi8(0,4,8,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,4,8,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1);
const __m128i mask2=_mm_set_epi64x(0,65535);
u32 i=0;
for(;i+8<=N;i+=8){
__m128i c[10];
#pragma GCC unroll 10
for(int d=0;d<10;++d){
__m256i q=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x[d]+i)),mul);
q=_mm256_max_epu32(_mm256_srli_epi32(q,23),one);
q=_mm256_shuffle_epi8(q,gather);
c[d]=_mm_unpacklo_epi32(_mm256_castsi256_si128(q),_mm256_extracti128_si256(q,1));
}
__m128i t0=_mm_unpacklo_epi8(c[0],c[1]),t1=_mm_unpacklo_epi8(c[2],c[3]);
__m128i t2=_mm_unpacklo_epi8(c[4],c[5]),t3=_mm_unpacklo_epi8(c[6],c[7]);
__m128i u0=_mm_unpacklo_epi16(t0,t1),u1=_mm_unpackhi_epi16(t0,t1);
__m128i u2=_mm_unpacklo_epi16(t2,t3),u3=_mm_unpackhi_epi16(t2,t3);
__m128i r[4]={_mm_unpacklo_epi32(u0,u2),_mm_unpackhi_epi32(u0,u2),_mm_unpacklo_epi32(u1,u3),_mm_unpackhi_epi32(u1,u3)};
__m128i tail=_mm_unpacklo_epi8(c[8],c[9]);
#pragma GCC unroll 8
for(int p=0;p<8;++p){
__m128i lo=(p&1)?_mm_srli_si128(r[p/2],8):r[p/2];
__m128i hi=_mm_and_si128(_mm_srli_si128(tail,p*2),mask2);
_mm_storeu_si128((__m128i*)(dst+(size_t)(i+p)*10),_mm_unpacklo_epi64(lo,hi));
}
}
for(;i<N;++i)for(int d=0;d<10;++d){u32 v=sigfull(x[d][i]);dst[(size_t)i*10+d]=(u8)(v?v:1u);}
}
static u32 s_pofs[(size_t)MAXK * MAXQ];
static u32 s_plen[(size_t)MAXK * MAXQ];
static int g_plen_on = 0;
static u32 g_W, g_Q, g_B;
static u32 g_KS;
static int g_nosort = 0;
static int g_nosdmp = 0;
static int g_skip_and = 0, g_skip_fringe = 0;
static int g_acc16 = 0;
#define FPOS(d, b) s_fpos[(size_t)(d) * MAXQ + (b)]
#define BVAL(d, b) s_bval[(size_t)(d) * MAXQ + (b)]
extern "C" int madvise(void*, unsigned long, int);
static void *pool_alloc(size_t bytes) {
void *raw = malloc(bytes + (2u << 20));
if (!raw) return 0;
void *al = (void *)(((size_t)raw + (2u << 20) - 1) & ~(size_t)((2u << 20) - 1));
if (bytes >= (size_t)(4u << 20)) madvise(al, bytes, 14);
return al;
}
static constexpr u32 DEFER_CAP=1u<<19;
alignas(64) static u32 defer_entries[(size_t)DEFER_CAP*9];
static u32 defer_count;
static void flush_deferred(u32*out,const u32*order){
u32 n=defer_count;defer_count=0;
for(u32 b=0;b<n;b+=128){
u32 end=b+128<n?b+128:n;
for(u32 j=b;j<end;j++){
const u32*e=defer_entries+(size_t)j*9;
u32 id=e[1];
__builtin_prefetch(out+e[0],1,3);
_mm_prefetch((const char*)(s_pm+(size_t)id*STRIDE),_MM_HINT_T0);
}
for(u32 j=b;j<end;){
const u32*e=defer_entries+(size_t)j*9;
const u32 query=e[0];
__m256i lo=_mm256_cvtepu16_epi32(_mm_loadu_si128((const __m128i*)(e+2)));
__m256i hi=_mm256_cvtepu8_epi32(_mm_cvtsi64_si128((long long)_pdep_u64(e[6],0x0f0f0f0f0f0f0f0full)));
__m256i th=_mm256_or_si256(lo,_mm256_slli_epi32(hi,16));
__m128i upper=_mm_loadl_epi64((const __m128i*)(e+7));
u32 count=0;
do{
const u32*p=s_pm+(size_t)defer_entries[(size_t)j*9+1]*STRIDE;
__m256i a=_mm256_cmpgt_epi32(th,_mm256_load_si256((const __m256i*)p));
__m128i h=_mm_cmpgt_epi32(upper,_mm_loadl_epi64((const __m128i*)(p+8)));
u32 mask=(u32)_mm256_movemask_epi8(a);
mask&=(u32)_mm_movemask_epi8(h)|0xffffff00u;
count+=(mask==0xffffffffu);
++j;
}while(j<end&&defer_entries[(size_t)j*9]==query);
out[query]+=count;
}
}
}
__attribute__((target("avx2,popcnt")))
static inline u32 hsum256(__m256i v) {
u64 b[4];
_mm256_storeu_si256((__m256i *)b, v);
return (u32)(b[0] + b[1] + b[2] + b[3]);
}
template<int KK>
__attribute__((target("avx2,popcnt")))
static u32 and_popcount_range(const u64 *const *bs, u32 Wr, u32 rem) {
const __m256i lm = _mm256_set1_epi8(0x0f);
const __m256i lk = _mm256_setr_epi8(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
const __m256i z = _mm256_setzero_si256();
__m256i tot = z, acc0 = z, acc1 = z;
u32 w = 0, cnt = 0, total = 0;
for (; w + 8 <= Wr; w += 8) {
if (KK > 1) _mm_prefetch((const char *)(bs[1] + w + 32), _MM_HINT_T0);
if (KK > 2) _mm_prefetch((const char *)(bs[2] + w + 32), _MM_HINT_T0);
if (KK > 3) _mm_prefetch((const char *)(bs[3] + w + 32), _MM_HINT_T0);
if (KK > 4) _mm_prefetch((const char *)(bs[4] + w + 32), _MM_HINT_T0);
if (KK > 5) _mm_prefetch((const char *)(bs[5] + w + 32), _MM_HINT_T0);
if (KK > 6) _mm_prefetch((const char *)(bs[6] + w + 32), _MM_HINT_T0);
if (KK > 7) _mm_prefetch((const char *)(bs[7] + w + 32), _MM_HINT_T0);
if (KK > 8) _mm_prefetch((const char *)(bs[8] + w + 32), _MM_HINT_T0);
__m256i a = LDU256((bs[0] + w));
__m256i b = LDU256((bs[0] + w + 4));
for (int d = 1; d < KK; d++) {
a = _mm256_and_si256(a, LDU256((bs[d] + w)));
b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
}
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)));
acc1 = _mm256_add_epi8(acc1, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)));
if (++cnt == 31) {
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
acc0 = acc1 = z; cnt = 0;
}
}
for (; w + 4 <= Wr; w += 4) {
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < KK; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
__m256i lo = _mm256_and_si256(a, lm);
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo), _mm256_shuffle_epi8(lk, hi)));
}
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
total = hsum256(tot);
for (; w < Wr; w++) {
u64 v = bs[0][w];
for (int d = 1; d < KK; d++) v &= bs[d][w];
total += (u32)__builtin_popcountll(v);
}
if (rem) {
u64 v = bs[0][Wr];
for (int d = 1; d < KK; d++) v &= bs[d][Wr];
total += (u32)__builtin_popcountll(v & ((1ull << rem) - 1));
}
return total;
}
template<int NS>
__attribute__((target("avx2,popcnt")))
static u32 and_popcount_pm(const u64 *const *bs, const u8 *trow, const u8 *edgp, u32 Wf, u32 cut) {
const __m256i lm = _mm256_set1_epi8(0x0f);
const __m256i lk = _mm256_setr_epi8(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
const __m256i z = _mm256_setzero_si256();
const __m256i ones=_mm256_set1_epi64x(-1);
const __m128i sub64v=_mm_set1_epi16(0x4000);
__m256i tot = z, acc0 = z, acc1 = z;
u32 w = 0, total = 0;
auto scan_full=[&](auto clamp_tag,u32 stop){
constexpr bool Clamped=decltype(clamp_tag)::value;
while (w + 8 <= stop) {
u32 batchstop=stop < w+248u ? stop : w+248u;
for (; w + 8 <= batchstop; w += 8) {
constexpr int NF=(NS<=4)?NS:5;
const u32 ld32 = Clamped ? ((w + 32u < Wf) ? 32u : 0u) : 32u;
const u32 ld32b = Clamped ? ((w + 64u < Wf) ? 64u : 0u) : 64u;
for (int d = 0; d < NF; d++) { if constexpr(Clamped) _mm_prefetch((const char *)(bs[d] + w + ld32), _MM_HINT_T0); _mm_prefetch((const char *)(bs[d] + w + ld32b), _MM_HINT_T0); }
_mm_prefetch((const char *)(trow + (w >> 1) + (Clamped ? ((w + 64u < Wf) ? 32u : 0u) : 32u)), _MM_HINT_T0);
__m256i a,b;
if constexpr(NF==4){
__m256i a0=LDU256(bs[0]+w),a2=LDU256(bs[2]+w);
__m256i b0=LDU256(bs[0]+w+4),b2=LDU256(bs[2]+w+4);
__asm__("vpand %2,%1,%0" : "=x"(a0) : "x"(a0),"m"(*(const __m256i*)(bs[1]+w)));
__asm__("vpand %2,%1,%0" : "=x"(a2) : "x"(a2),"m"(*(const __m256i*)(bs[3]+w)));
__asm__("vpand %2,%1,%0" : "=x"(b0) : "x"(b0),"m"(*(const __m256i*)(bs[1]+w+4)));
__asm__("vpand %2,%1,%0" : "=x"(b2) : "x"(b2),"m"(*(const __m256i*)(bs[3]+w+4)));
a=_mm256_and_si256(a0,a2);b=_mm256_and_si256(b0,b2);
}else if constexpr(NF==5){
__m256i a0=LDU256(bs[0]+w),a2=LDU256(bs[2]+w),a4=LDU256(bs[4]+w);
__m256i b0=LDU256(bs[0]+w+4),b2=LDU256(bs[2]+w+4),b4=LDU256(bs[4]+w+4);
__asm__("vpand %2,%1,%0" : "=x"(a0) : "x"(a0),"m"(*(const __m256i*)(bs[1]+w)));
__asm__("vpand %2,%1,%0" : "=x"(a2) : "x"(a2),"m"(*(const __m256i*)(bs[3]+w)));
__asm__("vpand %2,%1,%0" : "=x"(b0) : "x"(b0),"m"(*(const __m256i*)(bs[1]+w+4)));
__asm__("vpand %2,%1,%0" : "=x"(b2) : "x"(b2),"m"(*(const __m256i*)(bs[3]+w+4)));
a=_mm256_and_si256(_mm256_and_si256(a0,a2),a4);
b=_mm256_and_si256(_mm256_and_si256(b0,b2),b4);
}else{
a = LDU256((bs[0] + w));
b = LDU256((bs[0] + w + 4));
for (int d = 1; d < NF; d++) {
a = _mm256_and_si256(a, LDU256((bs[d] + w)));
b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
}
}
u32 tb = *(const u32 *)(trow + (w >> 1));
__m128i tv=_mm_cvtsi32_si128((int)tb);
__m128i tdup=_mm_unpacklo_epi8(tv,tv);
__m128i tsub=_mm_subs_epu8(tdup,sub64v);
a = _mm256_and_si256(a,_mm256_xor_si256(_mm256_sllv_epi64(ones,_mm256_cvtepu8_epi64(tsub)),ones));
b = _mm256_and_si256(b,_mm256_xor_si256(_mm256_sllv_epi64(ones,_mm256_cvtepu8_epi64(_mm_srli_si128(tsub,4))),ones));
if constexpr(NS>4){
__m256i live=_mm256_or_si256(a,b);
if(_mm256_testz_si256(live,live))continue;
if constexpr(NS==8){
for(int d=5;d<8;d++){_mm_prefetch((const char*)(bs[d]+w+ld32),_MM_HINT_T0);_mm_prefetch((const char*)(bs[d]+w+ld32b),_MM_HINT_T0);}
__m256i c0=LDU256(bs[5]+w),c2=LDU256(bs[7]+w);
__m256i d0=LDU256(bs[5]+w+4),d2=LDU256(bs[7]+w+4);
__asm__("vpand %2,%1,%0":"=x"(c0):"x"(c0),"m"(*(const __m256i*)(bs[6]+w)));
__asm__("vpand %2,%1,%0":"=x"(d0):"x"(d0),"m"(*(const __m256i*)(bs[6]+w+4)));
a=_mm256_and_si256(a,_mm256_and_si256(c0,c2));
b=_mm256_and_si256(b,_mm256_and_si256(d0,d2));
}else{
for(int d=NF;d<NS;d++){
_mm_prefetch((const char*)(bs[d]+w+ld32),_MM_HINT_T0);
a=_mm256_and_si256(a,LDU256(bs[d]+w));
b=_mm256_and_si256(b,LDU256(bs[d]+w+4));
}
}
}
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)));
acc1 = _mm256_add_epi8(acc1, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)));
}
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
acc0 = acc1 = z;
}
};
scan_full(std::false_type{}, Wf>64u?Wf-64u:0u);
// [SEAT20-CLAMP3] Clamped tail scan: three phases with CONSTANT prefetch distances.
// For w in the tail the base recomputed ld32=(w+32<Wf)?32:0 and ld32b=(w+64<Wf)?64:0 every
// 8-word step (16 address/compare instructions) and spilled/reloaded plane base pointers.
// The predicates are monotone in w, so the tail splits into exact sub-ranges on which both
// distances are constant; every prefetch is still issued at the identical address for the
// identical w. Phase bounds: w+64<Wf <=> w+8<=Wf-57, w+32<Wf <=> w+8<=Wf-25.
{
u32 lim = Wf;
u32 eA = 0u; if (Wf > 64u) { u32 x = Wf - 57u; eA = (x < lim) ? x : lim; }
u32 eB = 0u; if (Wf > 32u) { u32 x = Wf - 25u; eB = (x < lim) ? x : lim; }
auto scan_phase=[&](auto d32c, auto d64c, u32 stop){
constexpr u32 D32 = decltype(d32c)::value;
constexpr u32 D64 = decltype(d64c)::value;
constexpr u32 T32 = (D64 == 64u) ? 32u : 0u;
for (; w + 8 <= stop; w += 8) {
constexpr int NF=(NS<=4)?NS:5;
for (int d = 0; d < NF; d++) { _mm_prefetch((const char *)(bs[d] + w + D32), _MM_HINT_T0); _mm_prefetch((const char *)(bs[d] + w + D64), _MM_HINT_T0); }
_mm_prefetch((const char *)(trow + (w >> 1) + T32), _MM_HINT_T0);
__m256i a,b;
if constexpr(NF==4){
__m256i a0=LDU256(bs[0]+w),a2=LDU256(bs[2]+w);
__m256i b0=LDU256(bs[0]+w+4),b2=LDU256(bs[2]+w+4);
__asm__("vpand %2,%1,%0" : "=x"(a0) : "x"(a0),"m"(*(const __m256i*)(bs[1]+w)));
__asm__("vpand %2,%1,%0" : "=x"(a2) : "x"(a2),"m"(*(const __m256i*)(bs[3]+w)));
__asm__("vpand %2,%1,%0" : "=x"(b0) : "x"(b0),"m"(*(const __m256i*)(bs[1]+w+4)));
__asm__("vpand %2,%1,%0" : "=x"(b2) : "x"(b2),"m"(*(const __m256i*)(bs[3]+w+4)));
a=_mm256_and_si256(a0,a2);b=_mm256_and_si256(b0,b2);
}else if constexpr(NF==5){
__m256i a0=LDU256(bs[0]+w),a2=LDU256(bs[2]+w),a4=LDU256(bs[4]+w);
__m256i b0=LDU256(bs[0]+w+4),b2=LDU256(bs[2]+w+4),b4=LDU256(bs[4]+w+4);
__asm__("vpand %2,%1,%0" : "=x"(a0) : "x"(a0),"m"(*(const __m256i*)(bs[1]+w)));
__asm__("vpand %2,%1,%0" : "=x"(a2) : "x"(a2),"m"(*(const __m256i*)(bs[3]+w)));
__asm__("vpand %2,%1,%0" : "=x"(b0) : "x"(b0),"m"(*(const __m256i*)(bs[1]+w+4)));
__asm__("vpand %2,%1,%0" : "=x"(b2) : "x"(b2),"m"(*(const __m256i*)(bs[3]+w+4)));
a=_mm256_and_si256(_mm256_and_si256(a0,a2),a4);
b=_mm256_and_si256(_mm256_and_si256(b0,b2),b4);
}else{
a = LDU256((bs[0] + w));
b = LDU256((bs[0] + w + 4));
for (int d = 1; d < NF; d++) {
a = _mm256_and_si256(a, LDU256((bs[d] + w)));
b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
}
}
u32 tb = *(const u32 *)(trow + (w >> 1));
__m128i tv=_mm_cvtsi32_si128((int)tb);
__m128i tdup=_mm_unpacklo_epi8(tv,tv);
__m128i tsub=_mm_subs_epu8(tdup,sub64v);
a = _mm256_and_si256(a,_mm256_xor_si256(_mm256_sllv_epi64(ones,_mm256_cvtepu8_epi64(tsub)),ones));
b = _mm256_and_si256(b,_mm256_xor_si256(_mm256_sllv_epi64(ones,_mm256_cvtepu8_epi64(_mm_srli_si128(tsub,4))),ones));
if constexpr(NS>4){
__m256i live=_mm256_or_si256(a,b);
if(_mm256_testz_si256(live,live))continue;
if constexpr(NS==8){
for(int d=5;d<8;d++){_mm_prefetch((const char*)(bs[d]+w+D32),_MM_HINT_T0);_mm_prefetch((const char*)(bs[d]+w+D64),_MM_HINT_T0);}
__m256i c0=LDU256(bs[5]+w),c2=LDU256(bs[7]+w);
__m256i d0=LDU256(bs[5]+w+4),d2=LDU256(bs[7]+w+4);
__asm__("vpand %2,%1,%0":"=x"(c0):"x"(c0),"m"(*(const __m256i*)(bs[6]+w)));
__asm__("vpand %2,%1,%0":"=x"(d0):"x"(d0),"m"(*(const __m256i*)(bs[6]+w+4)));
a=_mm256_and_si256(a,_mm256_and_si256(c0,c2));
b=_mm256_and_si256(b,_mm256_and_si256(d0,d2));
}else{
for(int d=NF;d<NS;d++){
_mm_prefetch((const char*)(bs[d]+w+D32),_MM_HINT_T0);
a=_mm256_and_si256(a,LDU256(bs[d]+w));
b=_mm256_and_si256(b,LDU256(bs[d]+w+4));
}
}
}
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)));
acc1 = _mm256_add_epi8(acc1, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)));
}
};
scan_phase(std::integral_constant<u32,32u>{}, std::integral_constant<u32,64u>{}, eA);
scan_phase(std::integral_constant<u32,32u>{}, std::integral_constant<u32, 0u>{}, eB);
scan_phase(std::integral_constant<u32, 0u>{}, std::integral_constant<u32, 0u>{}, lim);
}
for (; w + 4 <= Wf; w += 4) {
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < NS; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
u32 tb = *(const u16 *)(trow + (w >> 1));
__m128i tv=_mm_cvtsi32_si128((int)tb);
__m128i tdup=_mm_unpacklo_epi8(tv,tv);
__m128i tsub=_mm_subs_epu8(tdup,sub64v);
a = _mm256_and_si256(a,_mm256_xor_si256(_mm256_sllv_epi64(ones,_mm256_cvtepu8_epi64(tsub)),ones));
__m256i lo = _mm256_and_si256(a, lm);
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo), _mm256_shuffle_epi8(lk, hi)));
}
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
total = hsum256(tot);
for (; w < Wf; w++) {
u64 v = bs[0][w];
for (int d = 1; d < NS; d++) v &= bs[d][w];
u32 c = trow[w >> 1];
u32 k = (w & 1u) ? ((c > 64u) ? c - 64u : 0u) : c;
total += (u32)__builtin_popcountll(v & s_pref[k]);
}
{
u32 c = trow[Wf >> 1];
__m128i v = _mm_loadu_si128((const __m128i*)(bs[0] + Wf));
for(int d=1;d<NS;d++) v=_mm_and_si128(v,_mm_loadu_si128((const __m128i*)(bs[d]+Wf)));
const u64 vl=(u64)_mm_cvtsi128_si64(v)&s_pref[c];
const u64 vh=(u64)_mm_extract_epi64(v,1)&((c>64u)?s_pref[c-64u]:0ull);
if(vl|vh){
const __m256i ec=_mm256_set1_epi8((char)cut);
if(vl){u32 m0=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(ec,_mm256_loadu_si256((const __m256i*)edgp)));
u32 m1=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(ec,_mm256_loadu_si256((const __m256i*)(edgp+32))));
total+=(u32)__builtin_popcountll(vl&((u64)m0|((u64)m1<<32)));}
if(vh){u32 m0=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(ec,_mm256_loadu_si256((const __m256i*)(edgp+64))));
u32 m1=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(ec,_mm256_loadu_si256((const __m256i*)(edgp+96))));
total+=(u32)__builtin_popcountll(vh&((u64)m0|((u64)m1<<32)));}}
}
return total;
}
#define T16E_QTCALC() \
const u32 *Avp_ = avpool + (size_t)i * STRIDE; \
__m256i qr_ = _mm256_or_si256(LDA((const __m256i *)rec), khi8v); \
__m256i qT = _mm256_min_epi32(qr_, _mm256_or_si256(LDU256(Avp_), notexlo)); \
__m256i qTh; \
if (k > 8) { \
__m256i qrh_ = _mm256_or_si256(LDU256((rec + 8)), khi8hv); \
__m256i Avmh_ = _mm256_or_si256(LDU256((Avp_ + 8)), notexloh); \
qTh = _mm256_min_epi32(qrh_, Avmh_); \
} else { qTh = all8; }
struct RankGatherMasks{alignas(16) u8 m[10][10][2][16]{};constexpr RankGatherMasks(){
for(unsigned a=0;a<10;a++)for(unsigned b=0;b<10;b++){for(unsigned h=0;h<2;h++)for(unsigned j=0;j<16;j++)m[a][b][h][j]=128;
if(a==b)continue;unsigned j=0;for(unsigned d=0;d<10;d++)if(d!=a&&d!=b){for(unsigned z=0;z<2;z++)m[a][b][d/8][2*j+z]=2*(d%8)+z;j++;}}}};
static constexpr RankGatherMasks rank_gather_masks{};
static inline __m128i compact_stream_ranks(const u16*bd,unsigned a,unsigned b){
u32 tail;__builtin_memcpy(&tail,bd+8,4);
return _mm_or_si128(_mm_shuffle_epi8(_mm_loadu_si128((const __m128i*)bd),_mm_load_si128((const __m128i*)rank_gather_masks.m[a][b][0])),_mm_shuffle_epi8(_mm_cvtsi32_si128(tail),_mm_load_si128((const __m128i*)rank_gather_masks.m[a][b][1])));
}
struct StreamComplements{u16 code[256]{};constexpr StreamComplements(){
for(unsigned m=0;m<256;m++){unsigned v=0,j=0;for(unsigned i=0;i<8;i++)if(!(m&(1u<<i))){v|=i<<(3*j);j++;}code[m]=(u16)v;}}};
static constexpr StreamComplements stream_complements{};
template<int KK>
__attribute__((target("avx2,popcnt")))
static void query_group(u32 N, u32 *out, u32 ds, u32 q0, u32 q1, u32 Q, u32 W) {
const u32 KS_C = (KK <= 8) ? 8u : (u32)KK;
const int k = KK;
const int K1 = KK - 1;
u32 *qo = s_qord, *qt = s_tmp;
#if MF_ASCR
const u32 d1 = (ds == 0) ? 1u : 0u;
const u32 e1 = (d1 < ds) ? d1 : d1 - 1;
const u32 dmx = (u32)g_dm, emx = (dmx < ds) ? dmx : dmx - 1u;
{
/* [SEAT32-FRORD] s_frord_[d1][q0..q1) is already (dim-d1 bucket << 20) | index, bucketed
and ascending, for exactly this fold group. Reuse it; do not re-derive it. */
qo = s_frord_[d1];
(void)qt;
}
#else
const u32 d1 = 0, e1 = 0;
#endif
if (g_lexsort) {
u32 *cntv = s_cntv;
for (int dd = k - 1; dd >= 0; dd--) {
if (dd == ds) continue;
for (u32 v = 0; v <= Q; v++) cntv[v] = 0;
for (u32 qi = q0; qi < q1; qi++) cntv[s_bdT[(size_t)dd * N + qo[qi]] + 1]++;
{ u32 ac = q0; for (u32 v = 0; v <= Q; v++) { u32 c = cntv[v]; cntv[v] = ac; ac += c; } }
for (u32 qi = q0; qi < q1; qi++) { u32 id = qo[qi]; qt[cntv[s_bdT[(size_t)dd * N + id] + 1]++] = id; }
{ u32 *swp = qo; qo = qt; qt = swp; }
}
for (u32 qi = q0; qi < q1; qi++) s_bka[qi] = s_bdT[(size_t)d1 * N + qo[qi]];
}
#define PF_DIST 4
#ifdef PF_DIST
for (u32 qi = q0; qi < q0 + PF_DIST && qi + PF_DIST < q1; qi++) {
u32 j = qo[qi + PF_DIST] & 0xFFFFFu;
const u16 *bdn = s_bd + (size_t)j * MAXK;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const char *pp = (const char *)(s_bs + (g_plen_on ? s_pofs[(size_t)e * MAXQ + bdn[d]]
: ((size_t)e * (Q + 1) + bdn[d]) * W));
_mm_prefetch(pp, _MM_HINT_T0);
_mm_prefetch(pp + 64, _MM_HINT_T0);
_mm_prefetch(pp + 128, _MM_HINT_T0);
}
}
#endif
#if MF_ASCR
{
u32 cur_b = 0;
for (u32 w = 0; w < W; w++) s_ascr[w] = 0;
u32 qi = q0;
while (qi < q1) {
u32 b1 = qo[qi] >> 20;
u32 qe = qi + 1;
while (qe < q1 && (qo[qe] >> 20) == b1) qe++;
const u64 *bp1;
if (!g_lexsort) {
for (u32 bb = cur_b + 1; bb <= b1; bb++) {
u32 p0 = (bb == 1) ? 0 : s_doff[bb - 1];
u32 p1 = s_doff[bb];
for (u32 t = p0; t < p1; t++) { u32 q = s_delta[t]; s_ascr[q >> 6] |= 1ull << (q & 63); }
}
cur_b = b1;
bp1 = s_ascr;
} else {
bp1 = g_plen_on ? (s_bs + s_pofs[(size_t)e1 * MAXQ + b1])
: (s_bs + ((size_t)e1 * (Q + 1) + b1) * W);
u32 mx = 1;
for (u32 t = qi; t < qe; t++) { u32 rr = s_gt[ds][qo[t]]; if (rr > mx) mx = rr; }
u32 nwd = (mx >> 6) + 2;
if (nwd <= AS_WORDS) {
const u64 *src = bp1;
for (u32 w = 0; w < nwd; w++) s_ascr[w] = src[w];
bp1 = s_ascr;
}
}
for (u32 qq = qi; qq < qe; qq++) {
u32 i = qo[qq] & 0xFFFFFu;
const u16 *bd = s_bd + (size_t)i * MAXK;
#if MF_PFAOUT
{ u32 oo = qq + MF_PFAOUTD; if (oo < qe) _mm_prefetch((const char *)(out + (qo[oo] & 0xFFFFFu)), _MM_HINT_T0); }
#endif
#if MF_PFA > 0
{
u32 qj = qq + MF_PFA;
if (qj < qe) {
u32 j = qo[qj] & 0xFFFFFu;
_mm_prefetch((const char *)(s_bd + (size_t)j * MAXK), _MM_HINT_T0);
_mm_prefetch((const char *)(s_g + j), _MM_HINT_T0);
}
}
#endif
const u32 R = s_g[i] >> 4;
u32 cnt = 0;
if (R && !g_skip_and) {
const u64 *bp[MAXK];
u16 brank[MAXK];
int nbx = 0;
for (int e = 0; e < K1; e++) {
if (g_mask_ok && e == (int)emx) continue;
if constexpr(KK!=10){int rd=(e<ds)?e:e+1; brank[nbx]=bd[rd];}
if (e == (int)e1) bp[nbx++] = bp1;
else { int d = (e < ds) ? e : e + 1;
bp[nbx++] = g_plen_on ? (s_bs + s_pofs[(size_t)e * MAXQ + bd[d]])
: (s_bs + ((size_t)e * (Q + 1) + bd[d]) * W); }
}
if(g_mask_ok && nbx==8){
__m128i ranks; if constexpr(KK==10)ranks=compact_stream_ranks(bd,ds,dmx);else ranks=_mm_loadu_si128((const __m128i*)brank);
/* [SEAT27-DECOMP] ASCR lane is lane 0 for every ds (e1=(d1<ds)?d1:d1-1, d1=(ds==0)?1:0 -> 0). Force its rank
above every bucket so the 4-winner selects the 4 sparsest DENSE planes; the complement enumeration is in
lane order, so the ASCR then occupies slot 4 (the first conditional slot). Value-neutral: order only. */
ranks=_mm_insert_epi16(ranks,0x7FFF,0);
const __m128i lanes=_mm_setr_epi16(0,1,2,3,4,5,6,7);
int selected[4];unsigned used=0;
#pragma GCC unroll 4
for(int z=0;z<4;z++){
__m128i v=_mm_minpos_epu16(ranks);
unsigned j=(unsigned)_mm_extract_epi16(v,1);
selected[z]=j;used|=1u<<j;
ranks=_mm_or_si128(ranks,_mm_cmpeq_epi16(lanes,_mm_set1_epi16(j)));
}
const u64* ordered[8];
for(int z=0;z<4;z++)ordered[z]=bp[selected[z]];
unsigned rest=stream_complements.code[used];
for(int z=0;z<4;z++){ordered[4+z]=bp[rest&7u];rest>>=3;}
for(int z=0;z<8;z++)bp[z]=ordered[z];
}else if(g_mask_ok && nbx>=8){
for(int z=0;z<4;z++){
int best=z;
u16 minrank=brank[z];
for(int j=z+1;j<nbx;j++){
const u16 rank=brank[j];
const bool less=rank<minrank;
best=less?j:best;
minrank=less?rank:minrank;
}
const u64*p=bp[z];bp[z]=bp[best];bp[best]=p;
u16 rr=brank[z];brank[z]=brank[best];brank[best]=rr;
}
}
cnt = g_mask_ok
? and_popcount_pm<KK - 2>(bp, s_tm + s_tofs[bd[dmx]], s_edg + ((size_t)(R >> 7) << 7), (R >> 7) << 1, R & 127u)
: and_popcount_range<KK - 1>(bp, R >> 6, R & 63u);
}
out[i] = cnt;
}
qi = qe;
}
}
#else
for (u32 qi = q0; qi < q1; qi++) {
u32 i = qo[qi];
const u16 *bd = s_bd + (size_t)i * MAXK;
#if MF_PFA > 0
{
u32 qj = qi + MF_PFA;
if (qj < q1) {
u32 j = qo[qj] & 0xFFFFFu;
_mm_prefetch((const char *)(s_bd + (size_t)j * MAXK), _MM_HINT_T0);
_mm_prefetch((const char *)(s_g + j), _MM_HINT_T0);
}
}
#if MF_PFAOUT
{ u32 oo = qi + MF_PFAOUTD;
if (oo < q1) _mm_prefetch((const char *)(out + qo[oo]), _MM_HINT_T0); }
#endif
#endif
#ifdef PF_DIST
if (qi + PF_DIST < q1) {
u32 j = qo[qi + PF_DIST] & 0xFFFFFu;
const u16 *bdn = s_bd + (size_t)j * MAXK;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const char *pp = (const char *)(s_bs + (g_plen_on ? s_pofs[(size_t)e * MAXQ + bdn[d]]
: ((size_t)e * (Q + 1) + bdn[d]) * W));
_mm_prefetch(pp, _MM_HINT_T0);
_mm_prefetch(pp + 64, _MM_HINT_T0);
_mm_prefetch(pp + 128, _MM_HINT_T0);
}
}
#endif
const u32 R = s_g[i] >> 4;
u32 cnt = 0;
if (R && !g_skip_and) {
const u64 *bp[MAXK];
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
bp[e] = g_plen_on ? (s_bs + s_pofs[(size_t)e * MAXQ + bd[d]])
: (s_bs + ((size_t)e * (Q + 1) + bd[d]) * W);
#ifdef DBG_PLEN
if (g_plen_on) {
u32 need = (R >> 6) + ((R & 63) ? 1 : 0);
if (need > s_plen[(size_t)e * MAXQ + bd[d]])
printf("DBG ds=%d e=%d d=%d b=%u R=%u need=%u len=%u\n", ds, e, d, bd[d], R, need, s_plen[(size_t)e * MAXQ + bd[d]]);
}
#endif
}
cnt = and_popcount_range<KK - 1>(bp, R >> 6, R & 63u);
}
out[i] = cnt;
}
#endif
if (g_skip_fringe) return;
u32 *const avpool = s_avpool;
for (int d = 0; d < k; d++) {
if (d == ds) continue;
const u32 *fo = s_frord_[d];
u32 exmask = 0;
for (int e = 0; e < d; e++) if (e != ds) exmask |= 1u << e;
u32 hiA[8], hiAh[8];
for (int e = 0; e < 8; e++) hiA[e] = ((exmask >> e) & 1u) ? 0u : 0x7FFFFFFFu;
for (int e = 8; e < 16; e++) hiAh[e - 8] = ((exmask >> e) & 1u) ? 0u : 0x7FFFFFFFu;
const __m256i notexlo = LDU256(hiA);
const __m256i notexloh = LDU256(hiAh);
const __m256i all8 = _mm256_set1_epi32(-1);
const u32 *const odd = s_ord[d];
alignas(16) u8 qmask_bytes[16],dmask_bytes[16];
for(int e=0;e<16;e++){qmask_bytes[e]=(e<d&&e!=(int)ds)?0:255;dmask_bytes[e]=(e==d)?255:0;}
const __m128i qmask=_mm_load_si128((const __m128i*)qmask_bytes),dmask=_mm_load_si128((const __m128i*)dmask_bytes);
__m256i qidx[16];
for(int e=0;e<k-1;e++)qidx[e]=_mm256_set1_epi8((char)(e<d?e:e+1));
const u8 *const sgbase_d = s_sig ? (s_sig + (size_t)d * (k-1) * MF_SPL) : (const u8 *)0;
const u32 *const gt_d = s_gt[d];
const u32 *const fpos_d = s_fpos + (size_t)d * MAXQ;
for (u32 qi = q0; qi < q1; qi++) {
u32 i = fo[qi] & 0xFFFFFu;
#if MF_PFB > 0
{
u32 qj = qi + MF_PFB3;
if (qj < q1) {
u32 j = fo[qj] & 0xFFFFFu;
_mm_prefetch((const char *)(s_pm + (size_t)j * STRIDE), _MM_HINT_T0);
_mm_prefetch((const char *)(gt_d + j), _MM_HINT_T0);
}
}
#endif
const u32 lo = fpos_d[fo[qi] >> 20];
const u32 hi = gt_d[i];
if (lo >= hi) continue;
const u32 *rec = s_pm + (size_t)i * STRIDE;
const u8 *const qpad = ((const u8 *)rec) + 40;
u32 add = 0;
const u32 *c0 = s_sdmp[d] ? (s_sdmp[d] + (size_t)lo * KS_C) : 0;
if (g_use_filt) { T16E_QTCALC();
const u32 w0 = lo >> 6;
const u32 nw = ((hi - 1) >> 6) - w0 + 1;
u64 *fb = s_fbuf;
const u64 wcs = (u64)N / g_Qc + 1;
const u32 FW = g_fbm_W;
int first = 1;
#if MF_FR_NOREAD
first = 0;
for (u32 w = 0; w < nw; w++) fb[w] = 0;
#endif
for (int e = 0; e < k; e++) {
if (e == d) continue;
u32 c = (u32)((u64)rec[e] / wcs) + 1;
if (c > g_Qc) c = g_Qc;
const u64 *row = s_fbm + ((size_t)(d * k + e) * (g_Qc + 1) + c) * FW + w0;
if (first) { for (u32 w = 0; w < nw; w++) fb[w] = row[w]; first = 0; }
else { for (u32 w = 0; w < nw; w++) fb[w] &= row[w]; }
}
fb[0] &= ~0ull << (lo & 63);
u32 r2 = hi & 63u;
if (r2) fb[nw - 1] &= (1ull << r2) - 1;
for (u32 w = 0; w < nw; w++) {
u64 vv = fb[w];
#if MF_FR_NOCAND
vv = 0;
#endif
while (vv) {
int t = __builtin_ctzll(vv);
vv &= vv - 1;
u32 j = ((w0 + w) << 6) + (u32)t;
const u32 *cp = c0 ? (c0 + (size_t)(j - lo) * KS_C) : (s_pm + (size_t)s_ord[d][j] * STRIDE);
__m256i pv = LDU256(cp);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDU256((cp + 8));
ok &= (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, pvh)), kokhi);
}
add += ok;
}
}
if (g_acc16) ((u16 *)s_qord)[rec[15]] += (u16)add; else s_qord[rec[15]] += add;continue;
}
if (g_sig_on && (hi - lo) >= 2) {
__m256i qsb[16];
{
__m128i qr8=_mm_loadu_si128((const __m128i*)qpad);
__m128i qb8=_mm_loadl_epi64((const __m128i*)(qpad+k));
if constexpr(KK>=10)qb8=_mm_insert_epi8(qb8,qpad[k+8],8);
__m128i qs=_mm_or_si128(_mm_min_epu8(qr8,_mm_or_si128(qb8,qmask)),dmask);
__m256i qwide=_mm256_broadcastsi128_si256(qs);
for(int e=0;e<k-1;e++)qsb[e]=_mm256_shuffle_epi8(qwide,qidx[e]);
}
const u8 *const sgbase = sgbase_d + s_gshift[(size_t)d * MAXQ + (fo[qi] >> 20)];
u32 aj = lo, aacc = 0, aexact = 0;
for (; aj + 32 <= hi; aj += 32) {
__m256i ac = _mm256_subs_epu8(LDU256(sgbase + aj), qsb[0]);
for (int e = 1; e < k-1; e++) {
__m256i cv = LDU256(sgbase + (size_t)e * MF_SPL + aj);
ac = _mm256_or_si256(ac, _mm256_subs_epu8(cv, qsb[e]));
}
__m256i lt = _mm256_cmpeq_epi8(ac, _mm256_setzero_si256());
u32 ltm = (u32)_mm256_movemask_epi8(lt);
u32 amb = (u32)_mm256_movemask_epi8(_mm256_cmpeq_epi8(ac, _mm256_set1_epi8(1)));
aacc += (u32)__builtin_popcount(ltm);
if (amb) { T16E_QTCALC();
__m256i lv=_mm256_and_si256(qT,_mm256_set1_epi32(65535));
__m128i packed_low=_mm_packus_epi32(_mm256_castsi256_si128(lv),_mm256_extracti128_si256(lv,1));
__m256i hv=_mm256_and_si256(_mm256_srli_epi32(qT,16),_mm256_set1_epi32(15));
__m128i hw=_mm_packus_epi32(_mm256_castsi256_si128(hv),_mm256_extracti128_si256(hv,1));
__m128i hb=_mm_packus_epi16(hw,hw);
u32 packed_high=(u32)_pext_u64((u64)_mm_cvtsi128_si64(hb),0x0f0f0f0f0f0f0f0full);
while (amb) {
int t = __builtin_ctz(amb); amb &= amb - 1;
if(KK==10 && !c0 && defer_count<DEFER_CAP){
u32*e=defer_entries+(size_t)defer_count++*9;
e[0]=i;e[1]=odd[aj+(u32)t];
_mm_storeu_si128((__m128i*)(e+2),packed_low);e[6]=packed_high;
_mm_storel_epi64((__m128i*)(e+7),_mm256_castsi256_si128(qTh));
continue;
}
const u32 *cp = c0 ? (c0 + (size_t)(aj + (u32)t - lo) * KS_C) : (s_pm + (size_t)odd[aj + (u32)t] * STRIDE);
__m256i pv = LDU256(cp);
u32 okl = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDU256((cp + 8));
okl &= (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, pvh)), kokhi);
}
aacc += okl;
}
}
}
{
u32 r = hi - aj;
if (r) {
u32 kmask = (1u << r) - 1u;
const u8 *const tp = sgbase + aj;
__m256i ac = _mm256_subs_epu8(LDU256(tp), qsb[0]);
for (int e = 1; e < k-1; e++) {
__m256i cv = LDU256(tp + (size_t)e * MF_SPL);
ac = _mm256_or_si256(ac, _mm256_subs_epu8(cv, qsb[e]));
}
__m256i lt = _mm256_cmpeq_epi8(ac, _mm256_setzero_si256());
u32 ltm = ((u32)_mm256_movemask_epi8(lt)) & kmask;
u32 amb = ((u32)_mm256_movemask_epi8(_mm256_cmpeq_epi8(ac, _mm256_set1_epi8(1)))) & kmask;
aacc += (u32)__builtin_popcount(ltm);
if (amb) { T16E_QTCALC();
__m256i lv=_mm256_and_si256(qT,_mm256_set1_epi32(65535));
__m128i packed_low=_mm_packus_epi32(_mm256_castsi256_si128(lv),_mm256_extracti128_si256(lv,1));
__m256i hv=_mm256_and_si256(_mm256_srli_epi32(qT,16),_mm256_set1_epi32(15));
__m128i hw=_mm_packus_epi32(_mm256_castsi256_si128(hv),_mm256_extracti128_si256(hv,1));
__m128i hb=_mm_packus_epi16(hw,hw);
u32 packed_high=(u32)_pext_u64((u64)_mm_cvtsi128_si64(hb),0x0f0f0f0f0f0f0f0full);
while (amb) {
int t = __builtin_ctz(amb); amb &= amb - 1;
if(KK==10 && !c0 && defer_count<DEFER_CAP){
u32*e=defer_entries+(size_t)defer_count++*9;
e[0]=i;e[1]=odd[aj+(u32)t];
_mm_storeu_si128((__m128i*)(e+2),packed_low);e[6]=packed_high;
_mm_storel_epi64((__m128i*)(e+7),_mm256_castsi256_si128(qTh));
continue;
}
const u32 *cp = c0 ? (c0 + (size_t)(aj + (u32)t - lo) * KS_C) : (s_pm + (size_t)odd[aj + (u32)t] * STRIDE);
__m256i pv = LDU256(cp);
u32 okl = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDU256((cp + 8));
okl &= (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, pvh)), kokhi);
}
aacc += okl;
}
}
}
}
add = aacc;
} else if (c0) {
T16E_QTCALC();
if (k <= 8) {
const u32 *c = c0;
u32 a0 = 0, a1 = 0, a2 = 0, a3 = 0;
u32 j = lo;
for (; j + 4 <= hi; j += 4) {
__m256i p0 = LDU256((c));
__m256i p1 = LDU256((c + KS_C));
__m256i p2 = LDU256((c + 2 * KS_C));
__m256i p3 = LDU256((c + 3 * KS_C));
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p0), all8);
a1 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p1), all8);
a2 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p2), all8);
a3 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p3), all8);
c += 4 * KS_C;
}
for (; j < hi; j++, c += KS_C) {
__m256i pv = LDU256(c);
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
}
add = a0 + a1 + a2 + a3;
} else {
const u32 *c = c0;
u32 a0 = 0, a1 = 0, a2 = 0, a3 = 0;
u32 j = lo;
for (; j + 4 <= hi; j += 4) {
__m256i p0 = LDU256((c));
__m256i p1 = LDU256((c + KS_C));
__m256i p2 = LDU256((c + 2 * KS_C));
__m256i p3 = LDU256((c + 3 * KS_C));
__m256i h0 = LDU256((c + 8));
__m256i h1 = LDU256((c + KS_C + 8));
__m256i h2 = LDU256((c + 2 * KS_C + 8));
__m256i h3 = LDU256((c + 3 * KS_C + 8));
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p0), all8) & (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, h0)), kokhi);
a1 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p1), all8) & (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, h1)), kokhi);
a2 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p2), all8) & (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, h2)), kokhi);
a3 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p3), all8) & (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, h3)), kokhi);
c += 4 * KS_C;
}
for (; j < hi; j++, c += KS_C) {
__m256i pv = LDU256(c);
__m256i pvh = LDU256((c + 8));
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8) &
(u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, pvh)), kokhi);
}
add = a0 + a1 + a2 + a3;
}
} else {
T16E_QTCALC();
for (u32 j = lo; j < hi; j++) {
const u32 *c = s_pm + (size_t)odd[j] * STRIDE;
__m256i pv = LDA((const __m256i *)c);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDA((const __m256i *)(c + 8));
ok &= (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, pvh)), kokhi);
}
add += ok;
}
}
if (g_acc16) ((u16 *)s_qord)[rec[15]] += (u16)add; else s_qord[rec[15]] += add;}
if constexpr(KK==10)flush_deferred(out,odd);
}
/* [SEAT53-OUTACC] fold the nine dimension sums into out[] once per point, in ascending point order. */
if (g_acc16) { for (u32 sl_ = q0; sl_ < q1; sl_++) out[s_tmp[sl_]] += ((u16 *)s_qord)[sl_]; }
else for (u32 sl_ = q0; sl_ < q1; sl_++) out[s_tmp[sl_]] += s_qord[sl_];
}
static u8 cached_signature[(size_t)MAXN*16] __attribute__((aligned(64)));
template<int K>
__attribute__((target("avx2")))
static void solve_mf(u32 N, const unsigned **x, u32 *out) {
const int k = K;
const u32 W = ((N + 63) / 64 + 7u) & ~7u;
g_W = W;
#ifdef MF_SKIP_AND
g_skip_and = 1;
#endif
#ifdef MF_FILT
g_use_filt = 1;
#endif
#ifdef MF_NOFILT
g_use_filt = 0;
#endif
#ifdef MF_Q
g_Q = MF_Q; g_B = (u32)((N + (MF_Q) - 1) / (MF_Q));
#endif
#ifdef MF_FILT
g_use_filt = 1;
#endif
#ifdef MF_NOFILT
g_use_filt = 0;
#endif
#ifdef MF_SKIP_FRINGE
g_skip_fringe = 1;
#endif
if (!g_Q) {
u64 r = (u64)N, s2 = 0;
while (s2 * s2 < r) s2++;
u64 overhead = (u64)(5 * k + 21) * N * 4;
overhead += (u64)k * k * 4 * N;
overhead += (u64)k * k * ((u64)N + 64);
overhead += (u64)N * ((k <= 8) ? 8u : (u32)k) * 4 * k;
u64 budget = ((u64)MF_BUDGETMB << 20);
if (budget > overhead + ((u64)64 << 20)) budget -= overhead; else budget = (u64)64 << 20;
#if MF_PLEN
static const u32 kfill[7] = {72, 67, 62, 58, 54, 50, 46};
u64 perfill = ((u64)(k - 1) * W * 8) * kfill[k - 4] / 100;
#else
u64 perfill = (u64)(k - 1) * W * 8;
#endif
u64 Qmem = budget / (perfill ? perfill : 1);
if (Qmem < 8) Qmem = 8;
static const u32 kscale[7] = {82, 91, 100, 108, 115, 122, 129};
u32 q = (u32)((s2 * MF_QCOEF + 99) / 100);
q = (u32)(((u64)q * kscale[k - 4] + 99) / 100);
if ((u64)q > Qmem) q = (u32)Qmem;
if (q > N) q = N;
if(q>=MAXQ)q=MAXQ-1;
g_Q = q;
g_B = (N + q - 1) / q;
}
for (u32 t = 0; t < 256u; t++) s_pref[t] = (t >= 64u) ? ~0ull : ((1ull << t) - 1ull);
g_mask_on = MF_PFXMASK;
const u32 Q = g_Q, B = g_B;
const u64 bmag = ((1ull << 40) + B - 1) / B;
#if MF_PLEN
g_plen_on = 1;
#endif
#if MF_WTRIM
u32 Wpool = W;
#else
const u32 Wpool = W;
#endif
#if MF_FILTAUTO
if (!g_use_filt && B >= 400) g_use_filt = 1;
#endif
if (g_use_filt && (u64)k * k * (g_Qc + 1) * W * 8 > ((u64)700 << 20)) g_use_filt = 0;
#if !MF_FILTAUTO
g_use_filt = 0;
#endif
{
int lo8[8], hi8[8], bad8[8];
for (int e = 0; e < 8; e++) lo8[e] = (e < k) ? 0 : 0x7FFFFFFF;
for (int e = 0; e < 8; e++) hi8[e] = (8 + e < k) ? 0 : 0x7FFFFFFF;
for (int e = 0; e < 8; e++) bad8[e] = (8 + e < k) ? 0 : -1;
khi8v = LDU256(lo8);
khi8hv = LDU256(hi8);
kbadhi = LDU256(bad8);
kokhi = _mm256_xor_si256(kbadhi, _mm256_set1_epi32(-1));
}
const int K1 = k - 1;
for (int d = 0; d < k; d++) {
const unsigned *xd = x[d];
u32 *od = s_ord[d];
u8*hc=compact_hist;u32*ct=compact_cursor;
for(u32 i=0;i<=N;i++)hc[i]=0;
u32 lim=N>MF_ORDPF?N-MF_ORDPF:0;
for(u32 i=0;i<lim;i++){
Z16S_PFW(hc+xd[i+MF_ORDPF]);
hc[xd[i]]++;
}
for(u32 i=lim;i<N;i++){u32 v=xd[i];hc[v<N?v:0]++;}
u32 sum=0;
u32 hv=0;
for(;hv+8<=N+1;hv+=8){
__m256i c=_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)(hc+hv)));
__m256i p=_mm256_add_epi32(c,_mm256_slli_si256(c,4));
p=_mm256_add_epi32(p,_mm256_slli_si256(p,8));
__m128i lo=_mm256_castsi256_si128(p),hi=_mm256_extracti128_si256(p,1);
hi=_mm_add_epi32(hi,_mm_shuffle_epi32(lo,255));
__m256i inc=_mm256_inserti128_si256(_mm256_castsi128_si256(lo),hi,1);
__m256i ex=_mm256_add_epi32(_mm256_sub_epi32(inc,c),_mm256_set1_epi32(sum));
_mm256_storeu_si256((__m256i*)(ct+hv),ex);
sum+=(u32)_mm_extract_epi32(hi,3);
}
for(;hv<=N;hv++){u32 c=hc[hv];ct[hv]=sum;sum+=c;}
if(sum==N && N<1048576u){
u32*gt=s_gt[d];u32*pp=s_pos[d];
u32*bl=(u32*)s_qord;u32*bc=(u32*)s_cntv;const u32 NB=(N+4095u)>>12;for(u32 b=0;b<NB;b++)bc[b]=0;
for(u32 i=0;i<N;i++){
if(i+2*MF_SCAPF<N){_mm_prefetch((const char*)(ct+xd[i+2*MF_SCAPF]),_MM_HINT_T0);}
u32 v=xd[i];
u32 w=ct[v],st=w&0xfffffu,pos=st+(w>>20);ct[v]=w+(1u<<20);
pp[i]=pos;gt[i]=st;
u32 bp=pos>>12;bl[((size_t)bp<<12)+bc[bp]++]=(i<<12)|(pos&4095u);
#if MF_FB2
s_posp[(size_t)i*MAXK+d]=pos;
#endif
u32 num=(ct[v+1]&0xfffffu)-1u;
u32 bb=(u32)(((u64)num*bmag)>>40);
s_bdT[(size_t)d*N+i]=(u16)bb;
}
for(u32 b=0;b<NB;b++){u32*c=bl+((size_t)b<<12);u32 e=bc[b];size_t o=(size_t)b<<12;for(u32 j=0;j<e;j++){u32 x=c[j];od[o+(x&4095u)]=x>>12;}}
}else{
for (u32 i = 0; i <= N; i++) s_cntv[i] = 0;
#if MF_ORDPF > 0
{ u32 i = 0;
for (; i + MF_ORDPF < N; i++) {
u32 vn = xd[i + MF_ORDPF];
Z16S_PFW(s_cntv + (vn < N ? vn : 0));
u32 v = xd[i]; s_cntv[v < N ? v : 0]++;
}
for (; i < N; i++) { u32 v = xd[i]; s_cntv[v < N ? v : 0]++; }
}
#else
for (u32 i = 0; i < N; i++) { u32 v = xd[i]; s_cntv[v < N ? v : 0]++; }
#endif
{ u32 s = 0; for (u32 i = 0; i <= N; i++) { u32 c = s_cntv[i]; s_cntv[i] = s; s_tmp[i] = s; s += c; } }
#if MF_FB2
for (u32 i = 0; i < N; i++) {
u32 v = xd[i]; if (v >= N) v = 0; u32 q = s_tmp[v]++; od[q] = i;
s_posp[(size_t)i * MAXK + d] = q;
s_pos[d][i] = q;
}
#else
{
u32 *pp = s_pos[d];
for (u32 i = 0; i < N; i++) {
if (i + 2*MF_SCAPF < N) { u32 v2 = xd[i + 2*MF_SCAPF]; if (v2 >= N) v2 = 0;
_mm_prefetch((const char *)(s_tmp + v2), _MM_HINT_T0); }
if (i + MF_SCAPF < N) { u32 vf = xd[i + MF_SCAPF]; if (vf >= N) vf = 0;
Z16S_PFW(&od[s_tmp[vf]]); }
u32 v = xd[i]; if (v >= N) v = 0; u32 q = s_tmp[v]++; od[q] = i; pp[i] = q;
}
}
#endif
{ u32 *gt = s_gt[d];
for (u32 i = 0; i < N; i++) {
{if (i + MF_CNTPF < N) { u32 vp = xd[i + MF_CNTPF]; if (vp >= N) vp = 0;
_mm_prefetch((const char *)(s_cntv + vp), _MM_HINT_T0); }}
u32 v = xd[i]; if (v >= N) v = 0;
gt[i] = s_cntv[v];
u32 num = s_cntv[v + 1] - 1u; if (num > N) num = N;
u32 bb = (u32)(((u64)num * bmag) >> 40);
{ u16 bbx = (bb > Q - 1 ? Q - 1 : (u16)bb);
s_bdT[(size_t)d * N + i] = bbx; }
} }
}
BVAL(d, 0) = 0; FPOS(d, 0) = 0;
for (u32 b = 1; b < Q; b++) {
u32 pos = b * B < N ? b * B : N - 1;
u32 v = xd[od[pos]];
BVAL(d, b) = v;
u32 gs = pos;
while (gs > 0 && xd[od[gs - 1]] == v) gs--;
FPOS(d, b) = gs;
}
BVAL(d, Q) = 0xFFFFFFFFu; FPOS(d, Q) = 0;
}
{
/* [SEAT53-OUTACC] 16-bit accumulator guard: add <= bucket length, so the nine-dim sum <= k*max bucket length. */
u32 mb = 0; const u32 lbm = (N - 1u) / B;
for (int d = 0; d < k; d++) for (u32 b = 0; b <= lbm; b++) {
u32 s0 = FPOS(d, b), e0 = (b < lbm) ? FPOS(d, b + 1) : N;
if (e0 > s0 && e0 - s0 > mb) mb = e0 - s0;
}
g_acc16 = ((u64)mb * (u64)k <= 65535u);
}
{
const u32 lb=(N-1u)/B;
for(int d=0;d<k;d++){
u32 *sh=s_gshift+(size_t)d*MAXQ; const u32 *fp=s_fpos+(size_t)d*MAXQ;
u32 sg=0; sh[0]=0;
for(u32 b=1;b<=lb;b++){ sg += (0u-(fp[b]+sg))&31u; sh[b]=sg; }
}
}
if(k==10){
u32 i=0;
for(;i+8<=N;i+=8){
__m128i c0=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)0*N+i));
__m128i c1=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)1*N+i));
__m128i c2=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)2*N+i));
__m128i c3=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)3*N+i));
__m128i c4=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)4*N+i));
__m128i c5=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)5*N+i));
__m128i c6=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)6*N+i));
__m128i c7=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)7*N+i));
__m128i c8=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)8*N+i));
__m128i c9=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)9*N+i));
__m128i t0=_mm_unpacklo_epi16(c0,c1),t1=_mm_unpackhi_epi16(c0,c1);
__m128i t2=_mm_unpacklo_epi16(c2,c3),t3=_mm_unpackhi_epi16(c2,c3);
__m128i t4=_mm_unpacklo_epi16(c4,c5),t5=_mm_unpackhi_epi16(c4,c5);
__m128i t6=_mm_unpacklo_epi16(c6,c7),t7=_mm_unpackhi_epi16(c6,c7);
__m128i u0=_mm_unpacklo_epi32(t0,t2),u1=_mm_unpackhi_epi32(t0,t2);
__m128i u2=_mm_unpacklo_epi32(t1,t3),u3=_mm_unpackhi_epi32(t1,t3);
__m128i u4=_mm_unpacklo_epi32(t4,t6),u5=_mm_unpackhi_epi32(t4,t6);
__m128i u6=_mm_unpacklo_epi32(t5,t7),u7=_mm_unpackhi_epi32(t5,t7);
__m128i w0=_mm_unpacklo_epi64(u0,u4),w1=_mm_unpackhi_epi64(u0,u4);
__m128i w2=_mm_unpacklo_epi64(u1,u5),w3=_mm_unpackhi_epi64(u1,u5);
__m128i w4=_mm_unpacklo_epi64(u2,u6),w5=_mm_unpackhi_epi64(u2,u6);
__m128i w6=_mm_unpacklo_epi64(u3,u7),w7=_mm_unpackhi_epi64(u3,u7);
__m128i p0=_mm_unpacklo_epi16(c8,c9),p1=_mm_unpackhi_epi16(c8,c9);
u8* rb=(u8*)(s_bd+(size_t)i*MAXK);
_mm_storeu_si128((__m128i*)(rb+0),w0);*(u32*)(rb+16)=(u32)_mm_extract_epi32(p0,0);
_mm_storeu_si128((__m128i*)(rb+20),w1);*(u32*)(rb+36)=(u32)_mm_extract_epi32(p0,1);
_mm_storeu_si128((__m128i*)(rb+40),w2);*(u32*)(rb+56)=(u32)_mm_extract_epi32(p0,2);
_mm_storeu_si128((__m128i*)(rb+60),w3);*(u32*)(rb+76)=(u32)_mm_extract_epi32(p0,3);
_mm_storeu_si128((__m128i*)(rb+80),w4);*(u32*)(rb+96)=(u32)_mm_extract_epi32(p1,0);
_mm_storeu_si128((__m128i*)(rb+100),w5);*(u32*)(rb+116)=(u32)_mm_extract_epi32(p1,1);
_mm_storeu_si128((__m128i*)(rb+120),w6);*(u32*)(rb+136)=(u32)_mm_extract_epi32(p1,2);
_mm_storeu_si128((__m128i*)(rb+140),w7);*(u32*)(rb+156)=(u32)_mm_extract_epi32(p1,3);
}
for(;i<N;i++){u16 *row = s_bd + (size_t)i * MAXK; for (int d = 0; d < k; d++) row[d] = s_bdT[(size_t)d * N + i];}
} else {
for (u32 i = 0; i < N; i++) {
u16 *row = s_bd + (size_t)i * MAXK;
for (int d = 0; d < k; d++) row[d] = s_bdT[(size_t)d * N + i];
}
}
{
u32 nn = N - 1; u32 sh = 0;
while (nn > 255u) { nn >>= 1; sh++; }
g_sigsh = sh;
g_sigmul=N>1?(u32)((255ULL<<23)/(N-1)):0;
size_t need = (size_t)k * (k-1) * MF_SPL + 64;
static u8 *sigpool = 0; static size_t sigcap = 0;
if (need > ((size_t)220 << 20) || (size_t)N + 32 > MF_SPL) { sigpool = 0; sigcap = 0; }
else if (need > sigcap) { sigpool = (u8 *)pool_alloc(need); sigcap = sigpool ? need : 0; }
if (sigpool) {
s_sig = sigpool;
g_sig_on = 1;
g_sig_merged = 0;
}
}
#if MF_NOFILTB
g_use_filt = 0;
#endif
{
size_t needav = (size_t)N * STRIDE * 4 + 256;
if (needav > s_avcap) {
s_avpool = (u32 *)pool_alloc(needav);
s_avcap = s_avpool ? needav : 0;
}
}
{
size_t mrn = (size_t)MAXK * MAXK * MAXQ;
for (size_t z = 0; z < mrn; z++) s_maxr[z] = 0;
}
if(k==10){
u32 i=0;
for(;i+8<=N;i+=8){
__m256i v=_mm256_slli_epi32(_mm256_loadu_si256((const __m256i*)(s_gt[0]+i)),4);
for(unsigned d=1;d<10;++d){
__m256i q=_mm256_or_si256(_mm256_slli_epi32(_mm256_loadu_si256((const __m256i*)(s_gt[d]+i)),4),_mm256_set1_epi32(d));
v=_mm256_min_epu32(v,q);
}
_mm256_storeu_si256((__m256i*)(s_tmp+i),v);
}
for(;i<N;++i){u32 v=s_gt[0][i]<<4;for(unsigned d=1;d<10;++d){u32 q=(s_gt[d][i]<<4)|d;if(q<v)v=q;}s_tmp[i]=v;}
}
for (u32 i = 0; i < N; i++) {
u32 best;int ds;
if(k==10){best=s_tmp[i]>>4;ds=s_tmp[i]&15u;}else{
u64 bpk = ((u64)s_gt[0][i] << 4);
for (int d = 1; d < k; d++) {
u64 g = ((u64)s_gt[d][i] << 4) | (u64)d;
bpk = (g < bpk) ? g : bpk;
}
best = (u32)(bpk >> 4);
ds = (int)(bpk & 15u);
}
s_g[i] = (best << 4) | (u32)ds;
const u16 *bdv = s_bd + (size_t)i * MAXK;
u32 *av = s_avpool + (size_t)i * STRIDE;
u32 *mr = s_maxr + ((size_t)ds * MAXK) * MAXQ;
fold_dimension[i]=(u8)ds;
for (int d = 0; d < k; d++) {
if (d == ds) { av[d] = 0x7FFFFFFFu; continue; }
u32 b = bdv[d];
av[d] = d+1<k ? BVAL(d, b) : 0x7FFFFFFFu;
if (g_plen_on) { u32 *mp_ = mr + (size_t)d * MAXQ + b; u32 m0_ = *mp_;
*mp_ = (best > m0_) ? best : m0_; }
}
}
/* [SEAT53-OUTACC] prefix hoisted above the s_pm fill; row word 15 = fold-group slot, s_qord = acc, s_tmp = inverse. */
{
for (u32 v = 0; v <= (u32)k; v++) s_cntv[v] = 0;
for (u32 i = 0; i < N; i++) s_cntv[(s_g[i] & 15u) + 1]++;
{ u32 ac = 0; for (u32 v = 0; v <= (u32)k; v++) { u32 c = s_cntv[v]; s_cntv[v] = ac; ac += c; } }
}
u32 gstart[MAXK + 2];
{ gstart[0]=0; for(int d=1;d<k;++d)gstart[d]=s_cntv[d+1]; gstart[k]=N; gstart[k+1]=N; }
if (g_acc16) { for (u32 z = 0; z < N; z++) ((u16 *)s_qord)[z] = 0; } else { for (u32 z = 0; z < N; z++) s_qord[z] = 0; }
u32 spos[MAXK];
for (int d0 = 0; d0 < k; d0++) spos[d0] = gstart[d0];
if (s_sig) {
const u32 sh = g_sigsh;
if(k==10) prepare_cached_signatures(cached_signature,x,N);
for (u32 i = 0; i < N; i++) {
u32 *row = s_pm + (size_t)i * STRIDE;
for (int d = 0; d < k; d++) row[d] = x[d][i];
{ u32 sl_ = spos[fold_dimension[i]]++; row[15] = sl_; s_tmp[sl_] = i; }
const u32 *av = s_avpool + (size_t)i * STRIDE;
u8 *pad = (u8 *)row + 40;
if(k==10){ const u8 *cs=cached_signature+(size_t)i*10; __m128i cv=_mm_sub_epi8(_mm_loadu_si128((const __m128i*)cs),_mm_set1_epi8(1)); _mm_storeu_si128((__m128i*)pad,cv); } else { for (int e = 0; e < k; e++) { u32 v = sigfull(row[e]); pad[e] = (u8)(v ? v-1u : 0u); } }
if(k==10){ __m256i a8=_mm256_loadu_si256((const __m256i*)av);
__m256i s8=_mm256_max_epu32(_mm256_srli_epi32(_mm256_mullo_epi32(a8,_mm256_set1_epi32((int)g_sigmul)),23),_mm256_set1_epi32(1));
__m128i lo=_mm256_castsi256_si128(s8), hi=_mm256_extracti128_si256(s8,1);
__m128i b16=_mm_packus_epi32(lo,hi); __m128i b8=_mm_packus_epi16(b16,b16);
b8=_mm_sub_epi8(b8,_mm_set1_epi8(1)); _mm_storel_epi64((__m128i*)(pad+10),b8);
u32 v8=sigfull(av[8]); pad[18]=(u8)(v8?v8-1u:0u); } else { for (int e = 0; e + 1 < k; e++) { u32 v = sigfull(av[e]); pad[k + e] = (u8)(v ? v-1u : 0u); } }
}
} else {
for (u32 i = 0; i < N; i++) {
u32 *p = s_pm + (size_t)i * STRIDE;
for (int d = 0; d < k; d++) p[d] = x[d][i];
{ u32 sl_ = spos[fold_dimension[i]]++; p[15] = sl_; s_tmp[sl_] = i; }
}
}
/* [SEAT32-FRORD] s_qord store loop removed: it fed only the deleted counting sort.
[OUTACC] the prefix block itself is now hoisted above the s_pm fill. */
for (int d = 0; d < k; d++) {
u32 pos[MAXK];
for (int ds = 0; ds < k; ds++) pos[ds] = gstart[ds];
const u32 last_bucket=(N-1u)/B;
u32 r=0;
for(u32 b=0;b<=last_bucket;++b){
const u32 end=b==last_bucket?N:FPOS(d,b+1);
for(;r<end;++r){
if(r+MF_FRDPF<N){u32 ip=s_ord[d][r+MF_FRDPF];_mm_prefetch((const char*)(fold_dimension+ip),_MM_HINT_T0);}
u32 id=s_ord[d][r];u32 dst=pos[fold_dimension[id]]++;
s_frord_[d][dst]=id|(b<<20);
}
}
}
#if MF_NOSDMP
g_nosdmp = 1;
#endif
if (!g_nosdmp) {
u32 KS = k;
#if MF_KSPAD
if (k <= 8) KS = 8;
#endif
size_t per = (size_t)N * KS * 4;
size_t lim = (size_t)150 << 20;
if (k >= 9) lim = (size_t)470 << 20;
if (per * k <= lim) {
static u32 *pool = 0; static size_t cap = 0;
if (per * k > cap) { pool = (u32 *)pool_alloc(per * k + 256); cap = per * k; }
if (pool) {
g_KS = KS;
for (int d = 0; d < k; d++) {
s_sdmp[d] = pool + (size_t)d * N * g_KS;
const u32 *od = s_ord[d];
u32 *dst = s_sdmp[d];
const u32 KSx = g_KS;
u32 jb = 0; const u32 lb2 = (N - 1u) / B; const u32 *const fpd2 = s_fpos + (size_t)d * MAXQ; const u32 *const sh2 = s_gshift + (size_t)d * MAXQ;
for (u32 j = 0; j < N; j++) {
while (jb < lb2 && fpd2[jb + 1] <= j) jb++;
#if MF_PFB > 0
if (j + MF_PFB < N) _mm_prefetch((const char *)(s_pm + (size_t)od[j + MF_PFB] * STRIDE), _MM_HINT_T0);
#endif
const u32 *row = s_pm + (size_t)od[j] * STRIDE;
u32 *dp = dst + (size_t)j * KSx;
for (u32 e = 0; e < KSx; e++) dp[e] = (e < (u32)k) ? row[e] : 0u;
if (s_sig) {
u8 *sb = s_sig + (size_t)d * (k-1) * MF_SPL;
u32 off2 = j + sh2[jb];
for (int e = 0; e < k; e++) if(e!=d) sb[(size_t)(e-(e>d)) * MF_SPL + off2] = (u8)((sigfull(row[e])) | ((sigfull(row[e])) == 0));
}
}
if (s_sig) g_sig_merged = 1;
}
}
}
}
if (s_sig && !g_sig_merged && k==10) {
for(int d=0;d<k;d++) {
const u32 *od=s_ord[d];
u8 *base=s_sig+(size_t)d*(k-1)*MF_SPL;
const u32 lb=(N-1u)/B;const u32*const fpd=s_fpos+(size_t)d*MAXQ;const u32*const sh=s_gshift+(size_t)d*MAXQ;
u32 s0=0;
for(u32 b=0;b<=lb;b++) {
const u32 e0=b==lb?N:fpd[b+1];
if(e0<=s0)continue;
u8 *const bb=base+sh[b];
u32 j=s0;
if(e0-s0>=8) {
for(;j<e0;j+=8) {
if(j+8>e0)j=e0-8;
if(j+64<N){const u32*op=od+j+64;
_mm_prefetch((const char *)(cached_signature+(size_t)op[0]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[1]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[2]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[3]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[4]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[5]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[6]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[7]*10),_MM_HINT_T0);}
__m128i r0=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+0]*10));
__m128i r1=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+1]*10));
__m128i r2=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+2]*10));
__m128i r3=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+3]*10));
__m128i r4=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+4]*10));
__m128i r5=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+5]*10));
__m128i r6=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+6]*10));
__m128i r7=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+7]*10));
__m128i t0=_mm_unpacklo_epi8(r0,r1);
__m128i t1=_mm_unpacklo_epi8(r2,r3);
__m128i t2=_mm_unpacklo_epi8(r4,r5);
__m128i t3=_mm_unpacklo_epi8(r6,r7);
__m128i u0=_mm_unpacklo_epi16(t0,t1);
__m128i u1=_mm_unpackhi_epi16(t0,t1);
__m128i u2=_mm_unpacklo_epi16(t2,t3);
__m128i u3=_mm_unpackhi_epi16(t2,t3);
__m128i v0=_mm_unpacklo_epi32(u0,u2);
__m128i v1=_mm_unpackhi_epi32(u0,u2);
__m128i v2=_mm_unpacklo_epi32(u1,u3);
__m128i v3=_mm_unpackhi_epi32(u1,u3);
__m128i h0=_mm_unpackhi_epi8(r0,r1);
__m128i h1=_mm_unpackhi_epi8(r2,r3);
__m128i h2=_mm_unpackhi_epi8(r4,r5);
__m128i h3=_mm_unpackhi_epi8(r6,r7);
__m128i hu0=_mm_unpacklo_epi16(h0,h1),hu1=_mm_unpacklo_epi16(h2,h3);
__m128i v4=_mm_unpacklo_epi32(hu0,hu1);
if(d!=0)_mm_storel_epi64((__m128i *)(bb+(size_t)(0-(0>d))*MF_SPL+j),v0);
if(d!=1)_mm_storel_epi64((__m128i *)(bb+(size_t)(1-(1>d))*MF_SPL+j),_mm_srli_si128(v0,8));
if(d!=2)_mm_storel_epi64((__m128i *)(bb+(size_t)(2-(2>d))*MF_SPL+j),v1);
if(d!=3)_mm_storel_epi64((__m128i *)(bb+(size_t)(3-(3>d))*MF_SPL+j),_mm_srli_si128(v1,8));
if(d!=4)_mm_storel_epi64((__m128i *)(bb+(size_t)(4-(4>d))*MF_SPL+j),v2);
if(d!=5)_mm_storel_epi64((__m128i *)(bb+(size_t)(5-(5>d))*MF_SPL+j),_mm_srli_si128(v2,8));
if(d!=6)_mm_storel_epi64((__m128i *)(bb+(size_t)(6-(6>d))*MF_SPL+j),v3);
if(d!=7)_mm_storel_epi64((__m128i *)(bb+(size_t)(7-(7>d))*MF_SPL+j),_mm_srli_si128(v3,8));
if(d!=8)_mm_storel_epi64((__m128i *)(bb+(size_t)(8-(8>d))*MF_SPL+j),v4);
if(d!=9)_mm_storel_epi64((__m128i *)(bb+(size_t)(9-(9>d))*MF_SPL+j),_mm_srli_si128(v4,8));
}
} else {
for(;j<e0;j++) {
const u8 *row=cached_signature+(size_t)od[j]*10;
for(int e=0;e<k;e++)if(e!=(int)d)bb[(size_t)(e-(e>d))*MF_SPL+j]=row[e];
}
}
s0=e0;
}
}
g_sig_merged=1;
}
if (s_sig && !g_sig_merged) {
for (int d = 0; d < k; d++) {
const u32 *od = s_ord[d];
u8 *base = s_sig + (size_t)d * (k-1) * MF_SPL;
u32 nb = 0; const u32 lb = (N - 1u) / B; const u32 *const fpd = s_fpos + (size_t)d * MAXQ; const u32 *const sh = s_gshift + (size_t)d * MAXQ;
for (u32 j = 0; j < N; j++) {
while (nb < lb && fpd[nb + 1] <= j) nb++;
const u32 off = j + sh[nb];
#if MF_PFB > 0
if (j + MF_PFB < N) _mm_prefetch((const char *)(s_pm + (size_t)od[j + MF_PFB] * STRIDE), _MM_HINT_T0);
#endif
const u32 *row = s_pm + (size_t)od[j] * STRIDE;
for (int e = 0; e < k; e++) if(e!=d) base[(size_t)(e-(e>d)) * MF_SPL + off] = (u8)((sigfull(row[e])) | ((sigfull(row[e])) == 0));
}
}
}
u64 poolwords = (u64)K1 * (Q + 1) * W;
#if MF_PLEN
if (g_plen_on) {
u64 best = 0;
for (int dsx = 0; dsx < k; dsx++) {
u64 tot = 0;
for (int e = 0; e < K1; e++) {
int d = (e < dsx) ? e : e + 1;
const u32 *mr = s_maxr + ((size_t)dsx * MAXK + d) * MAXQ;
for (u32 b = 0; b <= Q; b++) {
u32 RR = mr[b];
u32 len = ((RR >> 6) + 8u) & ~7u;
if (len > W) len = W;
tot += len;
}
}
if (tot > best) best = tot;
}
if (best && best < poolwords) poolwords = best;
}
#endif
size_t need = (size_t)poolwords * sizeof(u64);
static u64 *pool = 0; static size_t cap2 = 0;
if (need > cap2) { pool = (u64 *)pool_alloc(need + 4096); cap2 = need; }
s_bs = pool;
for (int ds = 0; ds < k; ds++) {
u32 q0 = gstart[ds], q1 = gstart[ds + 1];
if (q0 >= q1) continue;
u32 rlim=0;
{const u32*rm=s_maxr+((size_t)ds*MAXK+(ds?0:1))*MAXQ;
for(u32 b=0;b<=Q;++b)if(rm[b]>rlim)rlim=rm[b];}
#if MF_WTRIM
{
u32 mx = rlim>1?rlim:1;
if(!g_plen_on)for (u32 qi = q0; qi < q1; qi++) { u32 rr = s_gt[ds][s_qord[qi] & 0xFFFFFu]; if (rr > mx) mx = rr; }
u32 wp = ((mx >> 6) + 8u) & ~7u;
Wpool = (wp < W) ? wp : W;
}
#endif
#if MF_PLEN
if (g_plen_on) {
u64 tot = 0;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const u32 *mr = s_maxr + ((size_t)ds * MAXK + d) * MAXQ;
u32 *po = s_pofs + (size_t)e * MAXQ;
u32 *pl = s_plen + (size_t)e * MAXQ;
for (u32 b = 0; b <= Q; b++) {
u32 RR = mr[b];
u32 len = ((RR >> 6) + 8u) & ~7u;
if (len > Wpool) len = Wpool;
po[b] = (u32)tot; pl[b] = len; tot += len;
}
}
if (tot > (u64)K1 * (Q + 1) * W) { g_plen_on = 0; }
}
#endif
g_mask_ok = 0;
if (g_mask_on) {
{ u32 dd0 = (ds == 0) ? 1u : 0u; g_dm = 0; while ((u32)g_dm == (u32)ds || (u32)g_dm == dd0) g_dm++; }
const u32 dmx = (u32)g_dm;
const u32 *const sdsp = s_pos[ds], *const sdmo = s_pos[dmx], *const sdom = s_ord[dmx], *const sdsr = s_ord[ds];
const u32 *const mrx = s_maxr + ((size_t)ds * MAXK + dmx) * MAXQ;
u32 mblk = 1; { u32 acc = 0;
for (u32 b = 0; b <= Q; b++) {
u32 rr = (mrx[b] >> 7) + 1u; if (rr > Wpool) rr = Wpool; if (rr > mblk) mblk = rr;
u32 rl = (rr + 63u) & ~63u; s_tofs[b] = acc; s_rlen[b] = rl; acc += rl; }
if (mblk > Wpool) mblk = Wpool;
{ size_t tnd = acc;
if (tnd > s_tmcap) { s_tm = (u8 *)pool_alloc(tnd + 4096); s_tmcap = s_tm ? tnd : 0; } } }
{ size_t end = ((size_t)mblk + 1) * 128;
if (end > s_edgcap) { s_edg = (u8 *)pool_alloc(end + 4096); s_edgcap = s_edg ? end : 0; } }
if (s_tm && s_edg) {
g_mask_ok = 1; g_tstride = mblk;
{ u8 *const cnt = s_cntx;
for (u32 m = 0; m < mblk; m++) cnt[m] = 0;
u32 j2 = 0;
for (u32 b = 0; b <= Q; b++) {
u32 L = (b == 0u) ? 0u : ((b < Q) ? FPOS(dmx, b) : (u32)N);
while (j2 < L) {
{ u32 pf = j2 + MF_PFXSW; if (pf >= N) pf = j2; u32 pp = sdom[pf];
_mm_prefetch((const char *)(sdsp + pp), _MM_HINT_T0); Z16S_PFW(&s_npos[pp]); }
u32 p = sdom[j2]; j2++;
u32 rk = sdsp[p]; u32 blk = rk >> 7;
if (blk < mblk) { u32 c = cnt[blk]; cnt[blk] = c + 1u; s_npos[p] = (blk << 7) | c; }
else s_npos[p] = rk;
}
{ u8 *row = s_tm + s_tofs[b]; u32 rl = s_rlen[b];
for(u32 z=0;z<rl;z+=64){
_mm256_stream_si256((__m256i*)(row+z),_mm256_loadu_si256((const __m256i*)(cnt+z)));
_mm256_stream_si256((__m256i*)(row+z+32),_mm256_loadu_si256((const __m256i*)(cnt+z+32)));} }
}
_mm_sfence();
}
{ u32 nb = (N + 127u) >> 7; if (mblk > nb) mblk = nb;
for (u32 m = 0; m < mblk; m++) {
u32 b0 = m << 7, nj = N - b0; if (nj > 128u) nj = 128u;
u8 *const edge=s_edg+(size_t)m*128;
if(nj<128u)__builtin_memset(edge,127,128);
for (u32 j = 0; j < nj; j++) {
u32 look=b0+j+32;
if(look<N)_mm_prefetch((const char*)(s_npos+sdsr[look]),_MM_HINT_T0);
u32 sg = s_npos[sdsr[b0 + j]] & 127u;
edge[sg]=(u8)j;
} } }
} else g_mask_on = 0;
}
const u32 *s_nid = g_mask_ok ? s_npos : s_pos[ds];
const u32 emsk = (g_mask_ok ? ((u32)g_dm < (u32)ds ? (u32)g_dm : (u32)g_dm - 1u) : 0xffffffffu);
const u32 LIM=((((rlim>>7)<<1)+2u)<<6);
for (int e = 0; e < K1; e++) {
if ((u32)e == emsk) continue;
int d = (e < ds) ? e : e + 1;
const unsigned *xd = x[d];
const u32 *od = s_ord[d];
#if MF_ASCR && !MF_BUILD_NOPOOL
{
const u32 d1b = (ds == 0) ? 1u : 0u;
const u32 e1b = (d1b < ds) ? d1b : d1b - 1u;
if ((u32)e == e1b && !g_lexsort) {
u32 dp = 0, ptr2 = 0;
s_doff[0] = 0;
for (u32 b = 1; b <= Q; b++) {
u32 pend = (b < Q) ? FPOS(d, b) : (u32)N;
u32 pp = ptr2;
const u32 nidpf = 40;
for (; pp + 8 <= pend; pp += 8) {
if (pp + nidpf + 8 <= pend) {
_mm_prefetch((const char *)(s_nid + od[pp + nidpf]), _MM_HINT_T0);
_mm_prefetch((const char *)(s_nid + od[pp + nidpf + 4]), _MM_HINT_T0);
}
if (pp + 72 <= pend) _mm_prefetch((const char *)(od + pp + 64), _MM_HINT_NTA);
u32 q0 = s_nid[od[pp + 0]], q1 = s_nid[od[pp + 1]], q2 = s_nid[od[pp + 2]], q3 = s_nid[od[pp + 3]];
u32 q4 = s_nid[od[pp + 4]], q5 = s_nid[od[pp + 5]], q6 = s_nid[od[pp + 6]], q7 = s_nid[od[pp + 7]];
s_delta[dp]=q0;dp+=(q0<LIM);s_delta[dp]=q1;dp+=(q1<LIM);s_delta[dp]=q2;dp+=(q2<LIM);s_delta[dp]=q3;dp+=(q3<LIM);
s_delta[dp]=q4;dp+=(q4<LIM);s_delta[dp]=q5;dp+=(q5<LIM);s_delta[dp]=q6;dp+=(q6<LIM);s_delta[dp]=q7;dp+=(q7<LIM);
}
for (; pp + nidpf < pend; pp++) {
_mm_prefetch((const char *)(s_nid + od[pp + nidpf]), _MM_HINT_T0);
u32 qq2 = s_nid[od[pp]]; s_delta[dp] = qq2; dp += (qq2 < LIM);
}
for (; pp < pend; pp++) { u32 qq3 = s_nid[od[pp]]; s_delta[dp] = qq3; dp += (qq3 < LIM); }
s_doff[b] = dp;
ptr2 = pend;
}
continue;
}
}
#endif
u64 *base = g_plen_on ? s_bs : (s_bs + (size_t)e * (Q + 1) * Wpool);
u64 *cur = s_acc;
for (u32 w = 0; w < Wpool; w++) cur[w] = 0;
if (g_plen_on) {
u64 *d0 = s_bs + s_pofs[(size_t)e * MAXQ];
u32 l0 = s_plen[(size_t)e * MAXQ];
for (u32 w = 0; w < l0; w++) d0[w] = 0;
}
u32 ptr = 0;
#if MF_BUILD_NOPOOL
while (ptr < N) ptr++;
#else
for (u32 b = 1; b <= Q; b++) {
u32 pend = (b < Q) ? FPOS(d, b) : (u32)N;
#if MF_NIDPF > 0
{ u32 pp = ptr;
const u32 nidpf = 40;
for (; pp + 8 <= pend; pp += 8) {
if (pp + nidpf + 8 <= pend) {
_mm_prefetch((const char *)(s_nid + od[pp + nidpf]), _MM_HINT_T0);
_mm_prefetch((const char *)(s_nid + od[pp + nidpf + 4]), _MM_HINT_T0);
}
u32 q0 = s_nid[od[pp + 0]], q1 = s_nid[od[pp + 1]], q2 = s_nid[od[pp + 2]], q3 = s_nid[od[pp + 3]];
u32 q4 = s_nid[od[pp + 4]], q5 = s_nid[od[pp + 5]], q6 = s_nid[od[pp + 6]], q7 = s_nid[od[pp + 7]];
cur[q0 >> 6] |= 1ull << (q0 & 63); cur[q1 >> 6] |= 1ull << (q1 & 63);
cur[q2 >> 6] |= 1ull << (q2 & 63); cur[q3 >> 6] |= 1ull << (q3 & 63);
cur[q4 >> 6] |= 1ull << (q4 & 63); cur[q5 >> 6] |= 1ull << (q5 & 63);
cur[q6 >> 6] |= 1ull << (q6 & 63); cur[q7 >> 6] |= 1ull << (q7 & 63);
}
for (; pp + nidpf < pend; pp++) {
_mm_prefetch((const char *)(s_nid + od[pp + nidpf]), _MM_HINT_T0);
u32 q = s_nid[od[pp]]; cur[q >> 6] |= 1ull << (q & 63);
}
for (; pp < pend; pp++) { u32 q = s_nid[od[pp]]; cur[q >> 6] |= 1ull << (q & 63); }
}
ptr = pend;
#else
while (ptr < pend) { u32 q = s_nid[od[ptr]]; cur[q >> 6] |= 1ull << (q & 63); ptr++; }
#endif
u64 *dst = g_plen_on ? (base + s_pofs[(size_t)e * MAXQ + b])
: (base + (size_t)b * Wpool);
u32 wlen = g_plen_on ? s_plen[(size_t)e * MAXQ + b] : Wpool;
#if MF_NT
{
u32 w = 0;
for (; w + 4 <= wlen; w += 4)
_mm256_stream_si256((__m256i *)(dst + w), LDA((const __m256i *)(cur + w)));
for (; w < wlen; w++) dst[w] = cur[w];
}
#else
for (u32 w = 0; w < wlen; w++) dst[w] = cur[w];
#endif
}
_mm_sfence();
#endif
}
switch (k) {
case 4: query_group<4>(N, out, ds, q0, q1, Q, Wpool); break;
case 5: query_group<5>(N, out, ds, q0, q1, Q, Wpool); break;
case 6: query_group<6>(N, out, ds, q0, q1, Q, Wpool); break;
case 7: query_group<7>(N, out, ds, q0, q1, Q, Wpool); break;
case 8: query_group<8>(N, out, ds, q0, q1, Q, Wpool); break;
case 9: query_group<9>(N, out, ds, q0, q1, Q, Wpool); break;
default: defer_count=0;
query_group<10>(N, out, ds, q0, q1, Q, Wpool);
break;
}
}
}
void count_10d(int n, const unsigned *x[10], unsigned *out) { solve_mf<10>((u32)n, (const unsigned **)x, out); }
/* [SEAT37-STACK-LAYOUT] end-of-.text fill: keeps the STACK .text extent equal to the priced ALIGNPAD
submission's (467,362 B), so the page-aligned .rodata/.data/.bss start addresses and every data/bss
symbol address are the priced ALIGNPAD ones. Emitted after every engine function. */
__attribute__((used,noinline,naked)) static void seat37_text_pad(void){ __asm__ __volatile__(".fill 4864,1,0x90"); }
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 5.162 s | 920 MB + 860 KB | Accepted | Score: 100 | 显示更多 |