/* References:
- saffah_codex_6a_agg3, https://duck.ac/submission/126056: accepted compact counting-sort front end and17-bit ambiguity threshold queue.
- saffah_codex_6a_agg3, https://duck.ac/submission/126047: eight-point bucket-byte transpose and dimension-major bucket lookups accepted for1016b, adapted here to six planes and eight-byte point records. All inherited engine attributions retained below; no separate software license notice is shown by the public sources.
Idea: Store each dimension's bucket output contiguously, transpose six planes in eight-point blocks into the existing row records, and let single-dimension query-order counting read the compact plane directly. Multi-dimension scans retain the identical point records and all padding is neutral.
Purpose: Reduce strided bucket writes and the cache footprint of random single-dimension bucket reads.
*/
/* References:
- saffah_codex_6a_agg3, https://duck.ac/submission/125974: current accepted compressed ambiguity queue and all inherited six-dimensional counting engine notices retained below.
- saffah_codex_6a_agg3, https://duck.ac/submission/126047 and https://duck.ac/submission/126043: copied the byte-frequency overflow test and compact start/arrival cursor idea, already accepted for1016b and1013b. Their original public-engine attributions are retained in those sources and the inherited engine notices below; no separate software license notice is shown by these public sources.
Idea: Transfer the proven counting-sort front end to this six-dimensional instance. Build byte frequencies and accept the compact path only when their total equals N, proving no byte wrapped. One32-bit cursor holds an immutable20-bit group start and its arriving-point count; adjacent starts provide exact group ends. Fuse stable placement, strict rank and bucket output in one input traversal. Any frequency overflow or oversized N retains the full original wide-table path.
Purpose: Reduce random frequency-table and cursor traffic without changing ties, ranks or the downstream ambiguity queue.
*/
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/123257: copied the signature/min-fold engine and deferred ambiguity queue, retaining all inherited author references below.
- saffah_codex_6a_agg3, https://duck.ac/submission/120242: inherited signature-plane construction, as credited by123257.
These public source pages show no separate software license notice.
Idea: In this100000-point six-dimensional instance, each ranked threshold fits17bits. Store eight low16-bit lanes in a16-byte queue record and place the six high bits in otherwise unused high bits of the existing64-bit handle. Reconstruct the exact thresholds at replay, with neutral lanes explicitly restored. Prepare the compressed threshold once per query before its candidate loop. Other dimensions retain the original representation.
Purpose: Test reducing each ambiguous candidate's queue traffic from40 to24bytes without adding random shared-threshold accesses.
*/
// ===== [b12i_ 席] 2026-10-03 · 1012b · 提交 · 两处改动（[AMBH] 回放预取提示 + [AMBC] 入队打包）=====
// ===== REFERENCES =====
// （本文件由前席件逐字派生；原引用块在 --strip 时被压缩，此处完整重述全部来源，
// 未取用任何未列出的代码。复用的每一处：账号 + 原提交地址 + 用了什么。）
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #120242
// <https://duck.ac/submission/120242>：本发「签名平面构建」段（8 记录 SSE 字节转置 +
// 64 位存储，`a12b_sigrow` -> `s_sig`）的来源，逐字保留；该件自述以本账号 #111658 为
// 引擎基座。原件未附独立许可声明。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #111658
// <https://duck.ac/submission/111658>：本发正文引擎部分（签名 / MIN-FOLD）的来源。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #120356
// <https://duck.ac/submission/120356>：本账号 `[BKT]` 刀（ASCR 分组改走桶前缀数组）的来源。
// [4] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #120400
// <https://duck.ac/submission/120400>：本账号 `[PFSC]` 刀（查询侧 `out[]` 写行预取）的来源。
// [5] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #123231
// <https://duck.ac/submission/123231>：**本发正文的直接基座**（判题机 58.797424 ms，
// 本题现役最好件，= 本文件 + 本发两处改动），其 `[AMB2]` 刀（amb 延迟回放段两级预取 +
// 目的地行预热，前瞻 32/16/16）逐字保留。
// 许可：duck.ac 题面明示「你提交的代码将会被公开」，上述公开源码均未附独立许可声明，
// 本发依该条款使用并具名标注来源账号与原提交地址，未宣称原创。
// ======================
// ===== 思路 =====
// 本发 = 基座 #123231 + 两处改动，均为逐位等价的调度 / 数据布局改动。
// 【本席新测得的账（判题机同进程 8 臂、单变量全局消融、重复臂地板 0.02%）】
// amb 路径总额 = **10,130,824 拍 = 4.87%**，三段分解：
// · 回放段（`noreplay` 消融） = **3,756,901 拍（1.81%）**
// · 入队三存（`norunq` 消融） = ** 388,626 拍（0.19%）**
// · 余项（`if (amb)` 分支 + ctz 循环 + 交互）= **5,985,297 拍（2.87%）**
// 队列规模实测 **129,503 条 / 30 次回放 / 单次 ≤4,545**（此前按 13 万条估算，量级正确）。
// 参考（判题机同进程 8 臂相位尺，逐字孪生臂地板 0.39%）：回放段 28.49~28.72 拍/条目。
// 【改动 1 / [AMBH]】`[AMBD]` 延迟回放段的两条随机表预取提示 `NTA(0)` -> `T0(3)`：
// 原文 `__builtin_prefetch(&odd[s_abj[z+32]], 0, 0)` 与
// `__builtin_prefetch(s_pm + odd[s_abj[z+16]]*SMP_ROW, 0, 0)`
// 本发两处 hint 改 3（`out[]` 那条本来就是 3，未动）。
// 定价（判题机 `tools/probe.py`，同进程 8 臂、rdtscp 只包回放段 + 全程序 rdtscp，全部臂
// checksum 逐位同 `9cee5d16595065e9`）：回放段 28.72 -> **27.78** 拍/条目；
// **全程序 207,278,814 -> 206,834,764 = −444,050 拍（拷贝臂对拷贝臂，同窗同批）**。
// 机理：回放体每条目要经两级随机链（`s_abj[z] -> odd[j]` 400 KB -> `s_pm` 随机行 800 KB），
// 只能靠预取把每一跳变成 L1 命中；`prefetchnta` 取回的行在 L1 是「最先淘汰」标记，而前瞻
// 32/16 拍意味同时有 48~96 条此类行在飞 ⇒ 正好是 NTA 最吃亏的场景（实测同批 NTA->T1 与
// 无预取臂都更差，见 `work/b12i_rp2.py` 的臂表）。
// 【改动 2 / [AMBC]】入队把两个 4 字节存合并成一个 8 字节存，回放对称地用一个 8 字节载入：
// 原文 `s_abi[amb_n] = i; s_abj[amb_n] = aj + (u32)t;` + 回放 `s_abi[z]` / `s_abj[z]` 两次载入
// 本发 `s_abij[amb_n] = ((u64)i << 32) | (u64)(aj + (u32)t);` + 回放一次 8 字节载入后拆包。
// 依据：`norunq` 消融量出「入队三存」= 388,626 拍 ⇒ 每去掉 1/3 的存 + 回放侧 1 次载入
// ≈ −0.1 ~ −0.2M 拍。语义逐位等价（同一对 (i, j) 经不同路径到达回放）。
// 【闸门】官形状（k=6 n=1e5）checksum 必须仍为 `e3e2647f6f4f1b11`（本发本机两次逐位验同）；
// 正控 = 汇编里回放段 `prefetchnta` 归零（全部改 T0）。
// 【实验性提交声明】本发为**优化提交**（非探针）：两处改动均逐位等价（checksum 相同），
// 目的 = 在判题机板面上把 #123231 的 58.797424 ms 再压低 ≥0.168 ms（严支 58.629503）；
// 若无增益，保留原最好件 #123231。
// ================
#define MF_NOSDMPB 1
#pragma GCC optimize("O3,no-strict-aliasing")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=skylake")
#include <immintrin.h>
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)
extern "C" void *malloc(unsigned long);
typedef unsigned u32;
typedef unsigned short u16;
typedef unsigned char u8;
typedef unsigned long long u64;
#define AMBD_CAP 16384
static u32 s_abi[AMBD_CAP], s_abj[AMBD_CAP];
static unsigned long long s_abij[AMBD_CAP];
static __m256i s_abqT[AMBD_CAP], s_abqTh[AMBD_CAP];
alignas(64) static __m128i s_abqLo[AMBD_CAP];
#define LDU256(p) ({ __m256i _v256; __asm__("vmovdqu %1, %0" : "=x"(_v256) : "m"(*(const __m256i *)(p))); _v256; })
#ifndef MAXN
#define MAXN 100016
#endif
#define MAXK 6
#define STRIDE 8
#define MF_SPL ((size_t)(MAXN + 64))
#ifndef MF_APF
#define MF_APF 0
#endif
#ifndef MF_QCOEF
#define MF_QCOEF 80
#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 1900
#endif
#ifndef MF_NOFILTB
#define MF_NOFILTB 0
#endif
#ifndef MF_PFB
#define MF_PFB 8
#endif
#define MF_PFB1 64
#define MF_PFB2 16
#define MF_PFB3 8
#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_FR_NOMETA
#define MF_FR_NOMETA 0
#endif
#ifndef MAXQ
#define MAXQ 512
#endif
static u32 s_ord[MAXK][MAXN];
static u32 s_gt[MAXK][MAXN];
static u32 s_pm[(size_t)MAXN * STRIDE] __attribute__((aligned(64)));
static u8 s_bd[(size_t)MAXN * STRIDE];
alignas(64) static u8 bucket_planes[(size_t)MAXK*MAXN];
static u8 s_oth[MAXK][MAXK];
static int s_oth_ready = 0;
static u32 g_SBK = MAXK;
static u32 s_g[MAXN];
static u32 s_qord[MAXN], s_tmp[MAXN], s_cntv[MAXN];
alignas(64) static u32 compact_cursor[MAXN+8];
alignas(64) static u8 compact_hist[MAXN+8];
static unsigned long long s_vtab[MAXN + 8] __attribute__((aligned(64)));
static u8 s_bkt[MAXN];
static u32 s_nid[MAXN];
static u32 s_pos[MAXK][MAXN] __attribute__((aligned(64)));
static u32 s_posp[(size_t)MAXK * MAXN] __attribute__((aligned(64)));
static u64 s_facc[(size_t)(MAXK - 1) * (((MAXN) + 63) / 64 + 16)] __attribute__((aligned(64)));
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;
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_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_maxr[(size_t)MAXK * MAXK * MAXQ] __attribute__((aligned(64)));
static u8 *s_sig = 0;
alignas(32) static const unsigned char b12b_mskb[4][32] = {
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4},
{8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8},
{12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12,12}
};
static u8 a12b_sigrow[(size_t)MAXN * STRIDE] __attribute__((aligned(64)));
static int g_sigrow_on = 0;
static int g_sig_on = 0;
static int g_sig_merged = 0;
static u32 g_sigsh = 0;
static u32 s_pofs[(size_t)MAXK * MAXQ];
static u32 s_plen[(size_t)MAXK * MAXQ];
static int g_plen_on = 0;
#define g_k1 0
#define g_k2 0
#define g_k3 1
#define g_k6 0
#define K1DR 18
static u32 g_W, g_Q, g_B;
static u32 g_KS;
static unsigned long long g_bmag = 0;
static u32 g_SMP = STRIDE;
__attribute__((aligned(64))) static __m256i g_blm[MAXK][MAXK];
static int g_blm_ready = 0;
static int g_nosort = 0;
static int g_nosdmp = 0;
static int g_skip_and = 0, g_skip_fringe = 0;
#define FPOS(d, b) s_fpos[(size_t)(d) * MAXQ + (b)]
#define BVAL(d, b) s_bval[(size_t)(d) * MAXQ + (b)]
static void *pool_alloc(size_t bytes) {
void *raw = malloc(bytes + (2u << 20));
if (!raw) return 0;
return (void *)(((size_t)raw + (2u << 20) - 1) & ~(size_t)((2u << 20) - 1));
}
__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, acc = z;
u32 w = 0, cnt = 0, total = 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);
acc = _mm256_add_epi8(acc, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo), _mm256_shuffle_epi8(lk, hi)));
if (++cnt == 31) { tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc, z)); acc = z; cnt = 0; }
}
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc, 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 KK, int DD>
__attribute__((target("avx2,popcnt")))
static void fringe_d(u32 N, u32 *out, u32 ds, u32 q0, u32 q1, u32 Q, u32 W, u32 d1) {
const int k = KK;
const int K1 = KK - 1;
const u32 KS_ROW = (KK <= 8) ? 8u : (u32)KK;
const u32 SMP_ROW = (KK <= 8) ? 8u : (u32)STRIDE;
const int d = DD;
#if !MF_FR_NOSORT
#if MF_ASCR
if (d != (int)d1)
#endif
{
u32 *cntv = s_cntv;
for (u32 v = 0; v <= Q; v++) cntv[v] = 0;
for (u32 qi = q0; qi < q1; qi++) {
#if MF_PFB > 0
if (qi + MF_PFB2 < q1) _mm_prefetch((const char *)(bucket_planes + (size_t)d*N+s_qord[qi + MF_PFB2]), _MM_HINT_T0);
#endif
{ u32 bb = bucket_planes[(size_t)d*N+s_qord[qi]]; s_bkt[qi] = bb; cntv[bb + 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 = s_qord[qi]; s_tmp[cntv[s_bkt[qi] + 1]++] = id; }
for (u32 qi = q0; qi < q1; qi++) s_qord[qi] = s_tmp[qi];
}
#endif
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 u8 *const sbase = s_sig + (size_t)d * (k - 1) * MF_SPL;
int amb_n = 0;
const u32 *const odd = s_ord[d];
for (u32 qi = q0; qi < q1; qi++) {
u32 i = s_qord[qi];
#if MF_PFB > 0
{
u32 qj = qi + MF_PFB3;
if (qj < q1) {
u32 j = s_qord[qj];
_mm_prefetch((const char *)(s_pm + (size_t)(j) * SMP_ROW), _MM_HINT_T0);
_mm_prefetch((const char *)(s_gt[d] + j), _MM_HINT_T0);
_mm_prefetch((const char *)(s_bd + (size_t)j * g_SBK + d), _MM_HINT_T0);
_mm_prefetch((const char *)(out + j), _MM_HINT_T0);
}
}
#endif
const u8 *bd = s_bd + (size_t)i * g_SBK;
const u32 lo = FPOS(d, bd[d]);
const u32 hi = s_gt[d][i];
if (lo >= hi) continue;
const u32 *rec = s_pm + (size_t)(i) * SMP_ROW;
__m256i qr = _mm256_or_si256(LDA((const __m256i *)rec), khi8v);
__m256i qT, qTh;
if (k <= 8) {
__m256i VBv = _mm256_setr_epi32(
(int)((0 < d && 0 != (int)ds) ? BVAL(0, bd[0]) : 0x7FFFFFFFu),
(int)((1 < d && 1 != (int)ds) ? BVAL(1, bd[1]) : 0x7FFFFFFFu),
(int)((2 < d && 2 != (int)ds) ? BVAL(2, bd[2]) : 0x7FFFFFFFu),
(int)((3 < d && 3 != (int)ds) ? BVAL(3, bd[3]) : 0x7FFFFFFFu),
(int)((4 < d && 4 != (int)ds) ? BVAL(4, bd[4]) : 0x7FFFFFFFu),
(int)((5 < d && 5 != (int)ds) ? BVAL(5, bd[5]) : 0x7FFFFFFFu),
(int)((6 < d && 6 != (int)ds) ? BVAL(6, bd[6]) : 0x7FFFFFFFu),
(int)((7 < d && 7 != (int)ds) ? BVAL(7, bd[7]) : 0x7FFFFFFFu));
__m256i Avm = VBv;
qT = _mm256_min_epi32(qr, Avm);
qTh = all8;
} else {
u32 Av[STRIDE] __attribute__((aligned(32)));
for (int e = 0; e < k; e++) Av[e] = (e == ds) ? 0x7FFFFFFFu : BVAL(e, bd[e]);
for (int e = k; e < STRIDE; e++) Av[e] = 0x7FFFFFFFu;
__m256i Avm = _mm256_or_si256(LDU256(Av), notexlo);
qT = _mm256_min_epi32(qr, Avm);
__m256i qrh = _mm256_or_si256(LDU256((rec + 8)), khi8hv);
__m256i Avmh = _mm256_or_si256(LDU256((Av + 8)), notexloh);
qTh = _mm256_min_epi32(qrh, Avmh);
}
u32 add = 0;
const u32 *c0 = s_sdmp[d] ? (s_sdmp[d] + (size_t)lo * KS_ROW) : 0;
if (g_use_filt) {
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_ROW) : (s_pm + (size_t)(s_ord[d][j]) * SMP_ROW);
__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_cmpgt_epi32(qTh, pvh), all8);
}
add += ok;
}
}
out[i] += add;
continue;
}
#if MF_NOSDMPB
if (g_sig_on && (hi - lo) >= 2) {
#else
if (c0 && g_sig_on && (hi - lo) >= 2) {
#endif
__m256i qsb[16];
{
const __m256i bias8 = _mm256_set1_epi8((char)0x80);
const __m256i siglo = _mm256_xor_si256(_mm256_srli_epi32(qT, 9), bias8);
const __m256i ylo = _mm256_broadcastsi128_si256(_mm256_castsi256_si128(siglo));
const __m256i yhi = _mm256_broadcastsi128_si256(_mm256_extracti128_si256(siglo, 1));
__m256i zlo = ylo, zhi = yhi;
if (k > 8) {
const __m256i sighi = _mm256_xor_si256(_mm256_srli_epi32(qTh, 9), bias8);
zlo = _mm256_broadcastsi128_si256(_mm256_castsi256_si128(sighi));
zhi = _mm256_broadcastsi128_si256(_mm256_extracti128_si256(sighi, 1));
}
for (int sl = 0; sl < k - 1; sl++) {
const int e = sl < (int)d ? sl : sl + 1;
const __m256i src = (e < 8) ? ((e < 4) ? ylo : yhi) : ((e < 12) ? zlo : zhi);
qsb[sl] = _mm256_shuffle_epi8(src, _mm256_load_si256((const __m256i *)b12b_mskb[e & 3]));
}
}
__m128i queue_lo; unsigned long long queue_i = (unsigned long long)i << 32;
if constexpr(KK==6) {
__m256i lows=_mm256_and_si256(qT,_mm256_set1_epi32(65535));
queue_lo=_mm_packus_epi32(_mm256_castsi256_si128(lows),_mm256_extracti128_si256(lows,1));
queue_i |= (unsigned long long)(_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_slli_epi32(qT,15))) & 63) << 49;
}
u32 aj = lo, aacc = 0, aexact = 0;
for (; aj + 32 <= hi; aj += 32) {
__m256i lt, eq = _mm256_setzero_si256();
if (g_k3) {
__m256i ac0 = _mm256_subs_epi8(LDU256(sbase + aj), qsb[0]);
__m256i ac1 = _mm256_subs_epi8(LDU256(sbase + MF_SPL + aj), qsb[1]);
for (int sl = 2; sl < k - 1; sl += 2) {
__m256i cv0 = LDU256(sbase + (size_t)sl * MF_SPL + aj);
ac0 = _mm256_max_epi8(ac0, _mm256_subs_epi8(cv0, qsb[sl]));
if (sl + 1 < k - 1) {
__m256i cv1 = LDU256(sbase + (size_t)(sl + 1) * MF_SPL + aj);
ac1 = _mm256_max_epi8(ac1, _mm256_subs_epi8(cv1, qsb[sl + 1]));
}
}
__m256i M = _mm256_max_epi8(ac0, ac1);
lt = M;
eq = _mm256_cmpeq_epi8(M, _mm256_setzero_si256());
} else {
lt = _mm256_set1_epi8(-1);
for (int sl = 0; sl < k - 1; sl++) {
__m256i cv = LDU256((sbase + (size_t)sl * MF_SPL + aj));
lt = _mm256_and_si256(lt, _mm256_cmpeq_epi8(_mm256_max_epu8(cv, qsb[sl]), qsb[sl]));
eq = _mm256_or_si256(eq, _mm256_cmpeq_epi8(cv, qsb[sl]));
}
}
u32 ltm = (u32)_mm256_movemask_epi8(lt);
u32 amb = (u32)_mm256_movemask_epi8(eq);
aacc += (u32)__builtin_popcount(ltm);
if (amb) {
int a2 = amb;
while (a2) {
int t = __builtin_ctz(a2); a2 &= a2 - 1;
if (amb_n < AMBD_CAP) {
s_abij[amb_n] = queue_i | (unsigned long long)(aj + (u32)t);
if constexpr(KK==6) _mm_store_si128(&s_abqLo[amb_n],queue_lo);
else _mm256_store_si256(&s_abqT[amb_n], qT);
if (k > 8) _mm256_store_si256(&s_abqTh[amb_n], qTh);
amb_n++;
} else {
const u32 *cp = c0 ? (c0 + (size_t)(aj + (u32)t - lo) * KS_ROW)
: (s_pm + (size_t)(odd[aj + (u32)t]) * SMP_ROW);
__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_cmpgt_epi32(qTh, pvh), all8);
}
aacc += okl;
}
}
}
}
{
u32 r = hi - aj;
if (r) {
u32 base, lk;
if (hi >= 32u) { base = hi - 32u; lk = 32u - r; }
else { base = 0u; lk = lo; }
u32 kmask = ((r >= 32u) ? 0xFFFFFFFFu : ((1u << r) - 1u)) << lk;
__m256i lt, eq = _mm256_setzero_si256();
if (g_k3) {
__m256i ac0 = _mm256_subs_epi8(LDU256(sbase + base), qsb[0]);
__m256i ac1 = _mm256_subs_epi8(LDU256(sbase + MF_SPL + base), qsb[1]);
for (int sl = 2; sl < k - 1; sl += 2) {
__m256i cv0 = LDU256(sbase + (size_t)sl * MF_SPL + base);
ac0 = _mm256_max_epi8(ac0, _mm256_subs_epi8(cv0, qsb[sl]));
if (sl + 1 < k - 1) {
__m256i cv1 = LDU256(sbase + (size_t)(sl + 1) * MF_SPL + base);
ac1 = _mm256_max_epi8(ac1, _mm256_subs_epi8(cv1, qsb[sl + 1]));
}
}
__m256i M = _mm256_max_epi8(ac0, ac1);
lt = M;
eq = _mm256_cmpeq_epi8(M, _mm256_setzero_si256());
} else {
lt = _mm256_set1_epi8(-1);
for (int sl = 0; sl < k - 1; sl++) {
__m256i cv = LDU256((sbase + (size_t)sl * MF_SPL + base));
lt = _mm256_and_si256(lt, _mm256_cmpeq_epi8(_mm256_max_epu8(cv, qsb[sl]), qsb[sl]));
eq = _mm256_or_si256(eq, _mm256_cmpeq_epi8(cv, qsb[sl]));
}
}
u32 ltm = ((u32)_mm256_movemask_epi8(lt)) & kmask;
u32 amb = ((u32)_mm256_movemask_epi8(eq)) & kmask;
aacc += (u32)__builtin_popcount(ltm);
if (amb) {
int a2 = amb;
while (a2) {
int t = __builtin_ctz(a2); a2 &= a2 - 1;
if (amb_n < AMBD_CAP) {
s_abij[amb_n] = queue_i | (unsigned long long)(base + (u32)t);
if constexpr(KK==6) _mm_store_si128(&s_abqLo[amb_n],queue_lo);
else _mm256_store_si256(&s_abqT[amb_n], qT);
if (k > 8) _mm256_store_si256(&s_abqTh[amb_n], qTh);
amb_n++;
} else {
const u32 *cp = c0 ? (c0 + (size_t)(base + (u32)t - lo) * KS_ROW)
: (s_pm + (size_t)(odd[base + (u32)t]) * SMP_ROW);
__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_cmpgt_epi32(qTh, pvh), all8);
}
aacc += okl;
}
}
}
}
}
add = aacc;
} else if (c0) {
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_ROW));
__m256i p2 = LDU256((c + 2 * KS_ROW));
__m256i p3 = LDU256((c + 3 * KS_ROW));
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_ROW;
}
for (; j < hi; j++, c += KS_ROW) {
__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_ROW));
__m256i p2 = LDU256((c + 2 * KS_ROW));
__m256i p3 = LDU256((c + 3 * KS_ROW));
__m256i h0 = LDU256((c + 8));
__m256i h1 = LDU256((c + KS_ROW + 8));
__m256i h2 = LDU256((c + 2 * KS_ROW + 8));
__m256i h3 = LDU256((c + 3 * KS_ROW + 8));
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p0), all8) & (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, h0), all8);
a1 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p1), all8) & (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, h1), all8);
a2 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p2), all8) & (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, h2), all8);
a3 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p3), all8) & (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, h3), all8);
c += 4 * KS_ROW;
}
for (; j < hi; j++, c += KS_ROW) {
__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_cmpgt_epi32(qTh, pvh), all8);
}
add = a0 + a1 + a2 + a3;
}
} else {
for (u32 j = lo; j < hi; j++) {
const u32 *c = s_pm + (size_t)(odd[j]) * SMP_ROW;
__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_cmpgt_epi32(qTh, pvh), all8);
}
add += ok;
}
}
out[i] += add;
}
if (amb_n) {
auto replay_one = [&](int z) {
unsigned long long pp_ = s_abij[z];
const u32 *cp = s_pm + (size_t)odd[(u32)pp_] * SMP_ROW;
__m256i pv = LDU256(cp);
__m256i qv;
if constexpr(KK==6) {
__m256i lo=_mm256_cvtepu16_epi32(_mm_load_si128(&s_abqLo[z]));
__m256i hi=_mm256_set1_epi32((u32)(pp_>>49));
hi=_mm256_and_si256(_mm256_sllv_epi32(hi,_mm256_setr_epi32(16,15,14,13,12,11,10,9)),_mm256_set1_epi32(65536));
qv=_mm256_blend_epi32(_mm256_or_si256(lo,hi),_mm256_set1_epi32(0x7fffffff),0xc0);
} else qv=_mm256_load_si256((const __m256i *)&s_abqT[z]);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qv, pv), all8);
if (k > 8) {
__m256i pvh = LDU256((cp + 8));
__m256i qvh = _mm256_load_si256((const __m256i *)&s_abqTh[z]);
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qvh, pvh), all8);
}
out[(u32)(pp_ >> 32) & (KK==6 ? 0x1ffffu : 0xffffffffu)] += ok;
};
int z = 0;
for (; z + 48 < amb_n; z++) {
{ unsigned long long q1_ = s_abij[z + 32]; __builtin_prefetch((const char *)&odd[(u32)q1_], 0, 3); }
{ unsigned long long q2_ = s_abij[z + 16]; __builtin_prefetch(s_pm + (size_t)odd[(u32)q2_] * SMP_ROW, 0, 3); }
{ unsigned long long q3_ = s_abij[z + 16]; __builtin_prefetch((const char *)(out + ((u32)(q3_ >> 32) & (KK==6 ? 0x1ffffu : 0xffffffffu))), 0, 3); }
replay_one(z);
}
for (; z < amb_n; z++) replay_one(z);
amb_n = 0;
}
}
template<int KK>
__attribute__((target("avx2,popcnt")))
__attribute__((flatten)) __attribute__((flatten)) static void query_group(u32 N, u32 *out, u32 ds, u32 q0, u32 q1, u32 Q, u32 W) {
const int k = KK;
const int K1 = KK - 1;
const u32 KS_ROW = (KK <= 8) ? 8u : (u32)KK;
const u32 SMP_ROW = (KK <= 8) ? 8u : (u32)STRIDE;
#if MF_ASCR
const u32 d1 = (ds == 0) ? 1u : 0u;
const u32 e1 = (d1 < ds) ? d1 : d1 - 1;
{
u32 *cntv = s_cntv;
for (u32 v = 0; v <= Q; v++) cntv[v] = 0;
for (u32 qi = q0; qi < q1; qi++) {
#if MF_PFB > 0
if (qi + MF_PFB1 < q1) _mm_prefetch((const char *)(bucket_planes + (size_t)d1*N+s_qord[qi + MF_PFB1]), _MM_HINT_T0);
#endif
{ u32 bb = bucket_planes[(size_t)d1*N+s_qord[qi]]; s_bkt[qi] = bb; cntv[bb + 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 = s_qord[qi]; s_tmp[cntv[s_bkt[qi] + 1]++] = id; }
for (u32 qi = q0; qi < q1; qi++) s_qord[qi] = s_tmp[qi];
}
#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++) { u32 bb = bucket_planes[(size_t)dd*N+s_qord[qi]]; s_bkt[qi] = bb; cntv[bb + 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 = s_qord[qi]; s_tmp[cntv[s_bkt[qi] + 1]++] = id; }
for (u32 qi = q0; qi < q1; qi++) s_qord[qi] = s_tmp[qi];
}
}
#ifdef PF_DIST
for (u32 qi = q0; qi < q0 + PF_DIST && qi + PF_DIST < q1; qi++) {
u32 j = s_qord[qi + PF_DIST];
const u8 *bdn = s_bd + (size_t)j * g_SBK;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const char *pp = (const char *)(s_bs + ((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
{
for (u32 b1 = 0; b1 < Q; b1++) {
u32 qi = s_cntv[b1], qe = s_cntv[b1 + 1];
if (qi >= qe) continue;
const u64 *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][s_qord[t]]; if (rr > mx) mx = rr; }
u32 nwd = (mx >> 6) + 1;
if (0) {
const u64 *src = bp1;
{ u32 w = 0;
for (; w + 4 <= nwd; w += 4)
_mm256_store_si256((__m256i *)(s_ascr + w), LDU256((const __m256i *)(src + w)));
for (; w < nwd; w++) s_ascr[w] = src[w]; }
bp1 = s_ascr;
}
for (u32 qq = qi; qq < qe; qq++) {
u32 i = s_qord[qq];
const u8 *bd = s_bd + (size_t)i * g_SBK;
#if MF_PFA > 0
{
u32 qj = qq + MF_PFA;
if (qj < qe) {
u32 j = s_qord[qj];
_mm_prefetch((const char *)(s_bd + (size_t)j * g_SBK), _MM_HINT_T0);
_mm_prefetch((const char *)(s_gt[ds] + j), _MM_HINT_T0);
}
}
#endif
const u32 R = s_gt[ds][i];
u32 cnt = 0;
if (R && !g_skip_and) {
const u64 *bp[MAXK];
for (int e = 0; e < K1; e++) {
if (e == (int)e1) bp[e] = bp1;
else { 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); }
}
cnt = and_popcount_range<KK - 1>(bp, R >> 6, R & 63u);
}
out[i] = cnt;
}
}
}
#else
for (u32 qi = q0; qi < q1; qi++) {
u32 i = s_qord[qi];
const u8 *bd = s_bd + (size_t)i * g_SBK;
#if MF_PFA > 0
{
u32 qj = qi + MF_PFA;
if (qj < q1) {
u32 j = s_qord[qj];
_mm_prefetch((const char *)(s_bd + (size_t)j * g_SBK), _MM_HINT_T0);
_mm_prefetch((const char *)(s_gt[ds] + j), _MM_HINT_T0);
}
}
#endif
#ifdef PF_DIST
if (qi + PF_DIST < q1) {
u32 j = s_qord[qi + PF_DIST];
const u8 *bdn = s_bd + (size_t)j * g_SBK;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const char *pp = (const char *)(s_bs + ((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_gt[ds][i];
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;
for (int d_ = 0; d_ < k; d_++) {
if (d_ == (int)ds) continue;
switch (d_) {
case 0: fringe_d<KK,0>(N, out, ds, q0, q1, Q, W, d1); break;
case 1: fringe_d<KK,1>(N, out, ds, q0, q1, Q, W, d1); break;
case 2: fringe_d<KK,2>(N, out, ds, q0, q1, Q, W, d1); break;
case 3: fringe_d<KK,3>(N, out, ds, q0, q1, Q, W, d1); break;
case 4: fringe_d<KK,4>(N, out, ds, q0, q1, Q, W, d1); break;
case 5: fringe_d<KK,5>(N, out, ds, q0, q1, Q, W, d1); break;
}
}
}
__attribute__((target("avx2")))
static void solve_mf(u32 N, const unsigned **x, u32 *out, int k) {
const u32 W = ((N + 63) / 64 + 7u) & ~7u;
if (!s_oth_ready) {
for (int a = 0; a < MAXK; a++) { int t = 0;
for (int b = 0; b < MAXK; b++) if (b != a) s_oth[a][t++] = (u8)b; }
s_oth_ready = 1;
}
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 * (u64)(k - 1) * (u64)MF_SPL;
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;
g_Q = q;
if (g_Q > (u32)MAXQ) g_Q = (u32)MAXQ;
g_B = (N + g_Q - 1) / g_Q;
}
const u32 Q = g_Q, B = g_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];
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;
khi8v = LDU256(lo8);
khi8hv = LDU256(hi8);
}
g_SBK = (u32)((k < (int)STRIDE) ? (int)STRIDE : k);
g_bmag = ((1ull << 40) + g_B - 1) / g_B;
const int K1 = k - 1;
if (!g_blm_ready) {
for (int a = 0; a < MAXK; a++)
for (int b = 0; b < MAXK; b++) {
u32 m[8];
for (int e = 0; e < 8; e++) m[e] = ((e < b && e != a) ? 0xFFFFFFFFu : 0u);
g_blm[a][b] = LDU256(m);
}
g_blm_ready = 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>24?N-24:0;
for(u32 i=0;i<lim;i++){
u32 future=xd[i+24];if(future>=N)future=0;
__asm__ volatile("prefetchw %0" :: "m"(*(const char*)(hc+future)));
u32 v=xd[i];hc[v<N?v:0]++;
}
for(u32 i=lim;i<N;i++){u32 v=xd[i];hc[v<N?v:0]++;}
u32 sum=0;for(u32 v=0;v<=N;v++){ct[v]=sum;sum+=hc[v];}
if(sum==N && N<1048576u){
u32*gt=s_gt[d];
for(u32 i=0;i<N;i++){
u32 v=xd[i];if(v>=N)v=0;
u32 w=ct[v],st=w&0xfffffu,pos=st+(w>>20);
ct[v]=w+(1u<<20);od[pos]=i;gt[i]=st;
u32 end=ct[v+1]&0xfffffu;
#if MF_FB2
s_posp[(size_t)i*MAXK+d]=pos;
#else
if(g_use_filt)s_pos[d][i]=pos;
#endif
u32 n0=end-1u;if(n0>N)n0=N;
u32 bb=(u32)(((u64)n0*g_bmag)>>40);
bucket_planes[(size_t)d*N+i]=bb>Q-1?Q-1:bb;
}
}else{
for (u32 i = 0; i <= N; i++) s_cntv[i] = 0;
for (u32 i = 0; i < N; i++) { u32 v = xd[i]; s_cntv[v < N ? v : 0]++; }
{ 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; } }
for (u32 v = 0; v < N; v++)
s_vtab[v] = ((unsigned long long)s_cntv[v + 1] << 34) | ((unsigned long long)s_cntv[v] << 17)
| (unsigned long long)s_cntv[v];
#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;
}
#else
if (g_use_filt) {
u32 *pp = s_pos[d];
u32 *gt = s_gt[d];
for (u32 i = 0; i < N; i++) {
u32 v = xd[i]; if (v >= N) v = 0;
unsigned long long w = s_vtab[v];
u32 q = (u32)(w & 0x1FFFFu), st = (u32)((w >> 17) & 0x1FFFFu), en = (u32)((w >> 34) & 0x1FFFFu);
od[q] = i; s_vtab[v] = w + 1ull; pp[i] = q;
gt[i] = st;
u32 n0 = en - 1u; if (n0 > N) n0 = (u32)N;
u32 bb = (u32)(((u64)n0 * g_bmag) >> 40);
bucket_planes[(size_t)d*N+i] = bb > Q - 1 ? Q - 1 : bb;
}
} else {
u32 *gt = s_gt[d];
for (u32 i = 0; i < N; i++) {
u32 v = xd[i]; if (v >= N) v = 0;
unsigned long long w = s_vtab[v];
u32 q = (u32)(w & 0x1FFFFu), st = (u32)((w >> 17) & 0x1FFFFu), en = (u32)((w >> 34) & 0x1FFFFu);
od[q] = i; s_vtab[v] = w + 1ull;
gt[i] = st;
u32 n0 = en - 1u; if (n0 > N) n0 = (u32)N;
u32 bb = (u32)(((u64)n0 * g_bmag) >> 40);
bucket_planes[(size_t)d*N+i] = bb > Q - 1 ? Q - 1 : bb;
}
}
#endif
}
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;
}
u32 bi=0;
if(k==6 && g_SBK==8){
for(;bi+8<=N;bi+=8){
__m128i a0=_mm_loadl_epi64((const __m128i*)(bucket_planes+bi));
__m128i a1=_mm_loadl_epi64((const __m128i*)(bucket_planes+N+bi));
__m128i a2=_mm_loadl_epi64((const __m128i*)(bucket_planes+2*N+bi));
__m128i a3=_mm_loadl_epi64((const __m128i*)(bucket_planes+3*N+bi));
__m128i a4=_mm_loadl_epi64((const __m128i*)(bucket_planes+4*N+bi));
__m128i a5=_mm_loadl_epi64((const __m128i*)(bucket_planes+5*N+bi));
__m128i x0=_mm_unpacklo_epi8(a0,a1),x1=_mm_unpacklo_epi8(a2,a3);
__m128i x2=_mm_unpacklo_epi8(a4,a5),z=_mm_setzero_si128();
__m128i y0=_mm_unpacklo_epi16(x0,x1),y1=_mm_unpackhi_epi16(x0,x1);
__m128i y2=_mm_unpacklo_epi16(x2,z),y3=_mm_unpackhi_epi16(x2,z);
_mm_storeu_si128((__m128i*)(s_bd+(size_t)bi*8),_mm_unpacklo_epi32(y0,y2));
_mm_storeu_si128((__m128i*)(s_bd+(size_t)bi*8+16),_mm_unpackhi_epi32(y0,y2));
_mm_storeu_si128((__m128i*)(s_bd+(size_t)bi*8+32),_mm_unpacklo_epi32(y1,y3));
_mm_storeu_si128((__m128i*)(s_bd+(size_t)bi*8+48),_mm_unpackhi_epi32(y1,y3));
}
}
for(;bi<N;bi++)for(int d=0;d<k;d++)s_bd[(size_t)bi*g_SBK+d]=bucket_planes[(size_t)d*N+bi];
g_SMP = (k <= 8) ? 8u : (u32)STRIDE;
for (u32 i = 0; i < N; i++) {
u32 *p = s_pm + (size_t)i * g_SMP;
for (int d = 0; d < k; d++) p[d] = x[d][i];
for (u32 d = (u32)k; d < g_SMP; d++) p[d] = 0;
}
{
u32 nn = N - 1; u32 sh = 0;
while (nn > 255u) { nn >>= 1; sh++; }
g_sigsh = sh;
size_t need = (size_t)k * (k - 1) * MF_SPL;
static u8 *sigpool = 0; static size_t sigcap = 0;
if (need > ((size_t)220 << 20)) { 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
#if MF_FB3
if (g_use_filt) {
u32 Qc = g_Qc;
u64 wc = (u64)N / Qc + 1;
for (int e = 0; e < k; e++) {
const unsigned *xe = x[e];
const u32 *pe = s_ord[e];
u32 ptr = 0;
u32 *bn = s_bnde + (size_t)e * (MAXQ + 2);
for (u32 c = 0; c <= Qc; c++) {
u64 v = (u64)c * wc;
if (v > 0xFFFFFFFFull) v = 0xFFFFFFFFull;
while (v && ptr < N && (u64)xe[pe[ptr]] < v) ptr++;
bn[c] = ptr;
}
}
}
#endif
if (g_use_filt) {
u32 Qc = g_Qc;
u64 wc = (u64)N / Qc + 1;
size_t need2 = (size_t)k * k * (Qc + 1) * W * sizeof(u64);
static u64 *fpool = 0; static size_t fcap = 0;
if (need2 > fcap) { fpool = (u64 *)pool_alloc(need2 + 4096); fcap = need2; }
if (fpool) {
s_fbm = fpool; g_fbm_W = W;
#if MF_FB2
for (int d = 0; d < k; d++)
for (int e = 0; e < k; e++) {
if (e == d) continue;
u64 *b0 = s_fbm + (size_t)(d * k + e) * (Qc + 1) * W;
for (u32 w = 0; w < W; w++) b0[w] = 0;
}
for (int e = 0; e < k; e++) {
const unsigned *xe = x[e];
const u32 *pe = s_ord[e];
int dmap[MAXK], km1 = 0;
for (int d = 0; d < k; d++) if (d != e) dmap[km1++] = d;
for (int i = 0; i < km1; i++) { u64 *a = s_facc + (size_t)i * W; for (u32 w = 0; w < W; w++) a[w] = 0; }
u32 ptr = 0;
for (u32 c = 1; c <= Qc; c++) {
u64 v = (u64)c * wc;
if (v > 0xFFFFFFFFull) v = 0xFFFFFFFFull;
while (ptr < N && (u64)xe[pe[ptr]] < v) {
const u32 *pv = s_posp + (size_t)pe[ptr] * MAXK;
for (int i = 0; i < km1; i++) {
u32 q = pv[dmap[i]];
s_facc[(size_t)i * W + (q >> 6)] |= 1ull << (q & 63);
}
ptr++;
}
for (int i = 0; i < km1; i++) {
int d = dmap[i];
u64 *dst = s_fbm + ((size_t)(d * k + e) * (Qc + 1) + c) * W;
const u64 *src = s_facc + (size_t)i * W;
#if MF_NT
{ u32 w = 0;
for (; w + 4 <= W; w += 4) _mm256_stream_si256((__m256i *)(dst + w), LDA((const __m256i *)(src + w)));
for (; w < W; w++) dst[w] = src[w]; }
#else
{ u32 w = 0;
for (; w + 4 <= W; w += 4) _mm256_storeu_si256((__m256i *)(dst + w), LDU256((const __m256i *)(src + w)));
for (; w < W; w++) dst[w] = src[w]; }
#endif
}
}
}
#else
for (int d = 0; d < k; d++) {
for (int e = 0; e < k; e++) {
if (e == d) continue;
const unsigned *xe = x[e];
const u32 *pe = s_ord[e];
const u32 *pd = s_pos[d];
u64 *base = s_fbm + (size_t)(d * k + e) * (Qc + 1) * W;
for (u32 w = 0; w < W; w++) base[w] = 0;
u64 *cur = s_acc;
for (u32 w = 0; w < W; w++) cur[w] = 0;
u32 ptr = 0;
for (u32 c = 1; c <= Qc; c++) {
#if MF_FB3
u32 pend = s_bnde[(size_t)e * (MAXQ + 2) + c];
#else
u64 v = (u64)c * wc;
if (v > 0xFFFFFFFFull) v = 0xFFFFFFFFull;
u32 pend = ptr;
{ const unsigned *xe_ = xe; const u32 *pe_ = pe;
while (pend < N && (u64)xe_[pe_[pend]] < v) pend++; }
#endif
while (ptr < pend) { u32 q = pd[pe[ptr]]; cur[q >> 6] |= 1ull << (q & 63); ptr++; }
u64 *dst = base + (size_t)c * W;
#if MF_NT
{ u32 w = 0;
for (; w + 4 <= W; w += 4) _mm256_stream_si256((__m256i *)(dst + w), LDA((const __m256i *)(cur + w)));
for (; w < W; w++) dst[w] = cur[w]; }
#else
for (u32 w = 0; w < W; w++) dst[w] = cur[w];
#endif
}
}
}
#endif
} else { g_use_filt = 0; }
_mm_sfence();
}
{
size_t mrn = (size_t)MAXK * MAXK * MAXQ;
for (size_t z = 0; z < mrn; z++) s_maxr[z] = 0;
}
for (u32 i = 0; i < N; i++) {
u32 best = 0xFFFFFFFFu; int ds = 0;
for (int d = 0; d < k; d++) {
u32 g = s_gt[d][i];
if (g < best) { best = g; ds = d; }
}
s_g[i] = (u32)ds;
if (g_plen_on) {
const u8 *bdv = s_bd + (size_t)i * g_SBK;
u32 *mr = s_maxr + ((size_t)ds * MAXK) * MAXQ;
u32 bb = best;
const u8 *oth = s_oth[ds];
for (int t = 0; t < k - 1; t++) {
u32 d = oth[t];
u32 *pm = mr + (size_t)d * MAXQ + bdv[d];
u32 cur = *pm;
*pm = (bb > cur) ? bb : cur;
}
}
}
for (u32 i = 0; i < N; i++) s_qord[i] = i;
{
for (u32 v = 0; v <= (u32)k; v++) s_cntv[v] = 0;
for (u32 i = 0; i < N; i++) s_cntv[s_g[i] + 1]++;
{ u32 ac = 0; for (u32 v = 0; v <= (u32)k; v++) { u32 c = s_cntv[v]; s_cntv[v] = ac; ac += c; } }
for (u32 i = 0; i < N; i++) { u32 id = s_qord[i]; s_tmp[s_cntv[s_g[id] + 1]++] = id; }
for (u32 i = 0; i < N; i++) s_qord[i] = s_tmp[i];
}
u32 gstart[MAXK + 2];
{ u32 c = 0; for (int d = 0; d <= k; d++) { gstart[d] = c; while (c < N && (int)s_g[s_qord[c]] == d) c++; } gstart[k + 1] = c; }
g_sigrow_on = 0;
if (s_sig && k <= (int)STRIDE && N <= (u32)MAXN) {
for (u32 i = 0; i < N; i++) {
u8 *dst = a12b_sigrow + (size_t)i * STRIDE;
for (int e = 0; e < k; e++) dst[e] = (u8)((u8)(x[e][i] >> 9) ^ (u8)0x80);
}
g_sigrow_on = 1;
}
#if MF_NOSDMP
g_nosdmp = 1;
#endif
#if MF_NOSDMPB
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;
for (u32 j = 0; j < N; j++) {
#if MF_PFB > 0
if (j + MF_PFB < N) _mm_prefetch((const char *)(s_pm + (size_t)(od[j + MF_PFB]) * g_SMP), _MM_HINT_T0);
#endif
const u32 *row = s_pm + (size_t)(od[j]) * g_SMP;
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;
for (int sl = 0; sl < k - 1; sl++) { int e = sl < d ? sl : sl + 1; sb[(size_t)sl * MF_SPL + j] = (u8)((u8)(row[e] >> 9) ^ (u8)0x80); }
}
}
if (s_sig) g_sig_merged = 1;
}
}
}
}
if (s_sig && !g_sig_merged && k==6 && g_sigrow_on) {
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 j=0;
for(;j+8<=N;j+=8) {
if(j+64<N)_mm_prefetch((const char *)(a12b_sigrow+(size_t)od[j+64]*8),_MM_HINT_T0);
__m128i r0=_mm_loadl_epi64((const __m128i *)(a12b_sigrow+(size_t)od[j+0]*8));
__m128i r1=_mm_loadl_epi64((const __m128i *)(a12b_sigrow+(size_t)od[j+1]*8));
__m128i r2=_mm_loadl_epi64((const __m128i *)(a12b_sigrow+(size_t)od[j+2]*8));
__m128i r3=_mm_loadl_epi64((const __m128i *)(a12b_sigrow+(size_t)od[j+3]*8));
__m128i r4=_mm_loadl_epi64((const __m128i *)(a12b_sigrow+(size_t)od[j+4]*8));
__m128i r5=_mm_loadl_epi64((const __m128i *)(a12b_sigrow+(size_t)od[j+5]*8));
__m128i r6=_mm_loadl_epi64((const __m128i *)(a12b_sigrow+(size_t)od[j+6]*8));
__m128i r7=_mm_loadl_epi64((const __m128i *)(a12b_sigrow+(size_t)od[j+7]*8));
__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);
if(d!=0)_mm_storel_epi64((__m128i *)(base+(size_t)(0<d?0:0-1)*MF_SPL+j),v0);
if(d!=1)_mm_storel_epi64((__m128i *)(base+(size_t)(1<d?1:1-1)*MF_SPL+j),_mm_srli_si128(v0,8));
if(d!=2)_mm_storel_epi64((__m128i *)(base+(size_t)(2<d?2:2-1)*MF_SPL+j),v1);
if(d!=3)_mm_storel_epi64((__m128i *)(base+(size_t)(3<d?3:3-1)*MF_SPL+j),_mm_srli_si128(v1,8));
if(d!=4)_mm_storel_epi64((__m128i *)(base+(size_t)(4<d?4:4-1)*MF_SPL+j),v2);
if(d!=5)_mm_storel_epi64((__m128i *)(base+(size_t)(5<d?5:5-1)*MF_SPL+j),_mm_srli_si128(v2,8));
}
for(;j<N;j++) {
const u8 *row=a12b_sigrow+(size_t)od[j]*8;
for(int e=0;e<k;e++)if(e!=d)base[(size_t)(e<d?e:e-1)*MF_SPL+j]=row[e];
}
}
g_sig_merged=1;
}
if (s_sig && !g_sig_merged) {
const int use_sr = g_sigrow_on;
for (int d = 0; d < k; d++) {
const u32 *od = s_ord[d];
u8 *base = s_sig + (size_t)d * (k - 1) * MF_SPL;
for (u32 j = 0; j < N; j++) {
#if MF_PFB > 0
if (use_sr) {
if (j + 64 < N) _mm_prefetch((const char *)(a12b_sigrow + (size_t)od[j + 64] * STRIDE), _MM_HINT_T0);
} else if (j + MF_PFB < N) {
_mm_prefetch((const char *)(s_pm + (size_t)(od[j + MF_PFB]) * g_SMP), _MM_HINT_T0);
}
#endif
if (use_sr) {
const u8 *row = a12b_sigrow + (size_t)(od[j]) * STRIDE;
for (int sl = 0; sl < k - 1; sl++) { int e = sl < d ? sl : sl + 1; base[(size_t)sl * MF_SPL + j] = row[e]; }
} else {
const u32 *row = s_pm + (size_t)(od[j]) * g_SMP;
for (int sl = 0; sl < k - 1; sl++) { int e = sl < d ? sl : sl + 1; base[(size_t)sl * MF_SPL + j] = (u8)((u8)(row[e] >> 9) ^ (u8)0x80); }
}
}
}
}
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;
#if MF_WTRIM
{
u32 mx = 1;
for (u32 qi = q0; qi < q1; qi++) { u32 rr = s_gt[ds][s_qord[qi]]; 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
{
const u32 *od = s_ord[ds];
for (u32 j = 0; j < N; j++) {
if (j + 32 < N) _mm_prefetch((const char *)(s_nid + od[j + 32]), _MM_HINT_T0);
s_nid[od[j]] = j;
}
}
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const unsigned *xd = x[d];
const u32 *od = s_ord[d];
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;
while (ptr < pend) {
if (ptr + 16 < pend) _mm_prefetch((const char *)(s_nid + od[ptr + 16]), _MM_HINT_T0);
u32 q = s_nid[od[ptr]]; cur[q >> 6] |= 1ull << (q & 63); ptr++; }
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
{ u32 w = 0;
for (; w + 4 <= wlen; w += 4) _mm256_storeu_si256((__m256i *)(dst + w), LDU256((const __m256i *)(cur + w)));
for (; 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: query_group<10>(N, out, ds, q0, q1, Q, Wpool); break;
}
}
}
void count_4d(int n, const unsigned *x[4], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 4); }
void count_5d(int n, const unsigned *x[5], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 5); }
void count_6d(int n, const unsigned *x[6], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 6); }
void count_7d(int n, const unsigned *x[7], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 7); }
void count_8d(int n, const unsigned *x[8], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 8); }
void count_9d(int n, const unsigned *x[9], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 9); }
void count_10d(int n, const unsigned *x[10], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 10); }
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 57.831 ms | 21 MB + 704 KB | Accepted | Score: 100 | 显示更多 |