/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126233: accepted seven-dimensional engine and inherited citations retained.
* Idea: Establish the incremental-anchor allocation before maximum-span
* setup. When it is available, omit updates for that anchor's unused stored
* bitmap plane. Its all-zero metadata yields only minimal reserved spans;
* queries already obtain that plane from the incremental scratch bitmap.
* If allocation fails, retain every original stored-plane update and path.
* Purpose: Remove dead random max-table updates and the unused plane's
* reserved address range without changing any queried bitmap or fringe.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126214: accepted immediate SAD and compact six-plane signatures, original citations retained.
* Idea: Reduce coarse-grid coefficient140 to110 after the compact fringe
* and counting setup changes. The measured fringe is only about13 percent
* of runtime; reducing materialized prefix planes trades a longer fringe
* against less construction and a smaller cold bitmap working set.
* Purpose: Official experiment of the lower-grid side of this updated engine;
* the previous180-grid experiment was slower and is not retained here.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126154: accepted bitmap/signature engine, all citations retained below.
* Idea: Reduce each nibble-popcount vector immediately with SAD into two
* independent64-bit accumulators. This removes the byte-overflow counter,
* periodic31-block branch, reset and final byte reduction, while preserving
* the six bitmap streams, next-query prefetch and scalar tails.
* Purpose: Official experiment trading a regular SAD per vector for less
* hot-loop control and shorter accumulation dependencies.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126071: retained accepted seven-dimensional engine and all inherited source citations.
* saffah_codex_6a_agg3 https://duck.ac/submission/126127: adapted its compact live signature-plane layout and compile-time omitted-plane builder from eight dimensions.
* saffah_cc_v41_agg1 https://duck.ac/submission/122417: original compact live plane representation in its nine-dimensional variant.
* Idea: Keep only six live signature planes per omitted coordinate, remap
* query broadcasts to those indices, and emit six constant-offset transpose
* stores. Preserve the existing seeded maximum, deferred exact ties, bucket
* geometry, scalar tails and coordinate rank builder.
* Purpose: Remove one unused plane of storage and writes per coordinate order.
*/
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/123963: retained packed cursor/fused setup, latest fringe and all inherited references.
* saffah_codex_6a_agg3, https://duck.ac/submission/126047: reused validated byte-frequency sum overflow test.
* Idea: Construct existing compact cursors from one-byte frequencies instead
* of full-width frequencies. A total equal to N proves every byte frequency
* is exact; overflow selects the existing full-width fallback. This reduces
* random counting footprint fourfold and removes per-bin maximum tracking.
* Purpose: Official experiment reducing million-point setup costs.
*/
/* ===== a13ax_ seat: [SCANLEAN] the fringe byte-signature scan's inner loop, leaner =====
* Body: byte-copy of saffah_cc_v41_agg1 #123929 (a13as_ seat, https://duck.ac/submission/123929),
* itself built on saffah_codex_6a_agg3 #121929 (the current T, https://duck.ac/submission/121929).
* Two strictly
* result-preserving edits, both inside the per-32-position signature scan of `fringe_dim`:
*
* 1. LEAN BLOCK LOOP. The original loop is `for (; aj + 32 <= hi; aj += 32) { ... }`, which
* gcc-9.3 turns into lea/lea/cmp/jb/mov/jmp around a body whose `ac` chain starts from the
* constant 0x80. Rewritten as a do/while over `ax_last = hi - 32` with
* ac = subs_epi8(cv[e0], qsb[e0]) -- e0 = first plane != d (max(-128,x) = x)
* for (e != d, e != e0) ac = max(ac, subs_epi8(cv[e], qsb[e]))
* if (!testz_si256(eqz, eqz)) { amb = movemask(eqz); ...unchanged tie/exact block... }
* where eqz = cmpeq_epi8(ac, 0). The amb mask is bit-identical (it is the movemask of the
* same vector), it is simply materialised inside the 1.2%-taken branch instead of always.
* Per 32 positions: 6 loads, 6 vpsubsb, 5 vpmaxsb (not 6), 1 vpcmpeqb, 1 vpmovmskb (not 2),
* 1 popcnt, 1 vptest + jcc (instead of movemask+mov+test+jcc) and a 2-uop back edge
* (add/cmp+jb) instead of a 5-uop one -- 25 renamed uops vs 29, same result.
* gcc-9.3 listing confirmed locally (ref/gcc9 = the judge's compiler): 28 vs 32 instructions
* in the hot block. Fold of the first max is exact: 0x80 is the minimum int8, i.e. the
* identity of signed max.
* 2. NOODPF. `_mm_prefetch(odd + aj + 64)` is deleted. `odd = s_ord[d]` is read only on the
* tie-overflow / c0 fallback paths, never on the live path, so the prefetch is pure work
* (59e6 pf/solve) that also drags 4 MB per dim of never-read lines through L1/L2 and evicts
* the scan's own working set. Verified result-preserving by a13aw_ (封条 2030) and again
* here by the gate below.
*
* Both edits are bit-exact: 39-cell k=7 gate (brute-force oracle n<=9000 mode 0-4 x 3 seeds,
* n=1e5 mode 10-14, n=1e6 Q=0/1512/2700 checksums) 0 DIFF, checksums unchanged.
*
* Local pricing (same machine, same argv 7 1000000 12345 10 1512, n=1e6, interleaved paired
* rounds, in-process memclobbered fringe span = sum of the 7 per-dim rdtsc windows):
* 8 rounds base vs arm: fringe 964.2/977.6/972.0/982.4/968.6/970.4/970.8/986.5 vs
* 958.5/958.4/929.9/966.6/967.3/963.6/967.9/968.0 => 8/8 lower,
* paired mean -14.0e6 ticks (-1.45%), best pair -42.1e6 (-4.3%);
* wall in the same 8 rounds: 7/8 lower, mean -137 ms (-1.57%), best 8335.6 vs 8604.7 ms.
* The mechanism is work removal (uops + useless prefetch traffic), the class a13as_ calibrated
* at +0.30 judge-ms per local-ms and #123929 realised at 0.60, so the expected judge gain lies
* above the 7.674088 ms gap; the local ruler alone cannot resolve 0.2% of the wall.
* =============================================================================== */
/* ===== a13as_ seat: [Y2-BL] branchless argmin + branchless scatter-max in the group plane (y2) =====
* Built ON TOP of this seat's #123927 [OD-GROUP] body (its own block follows below); the single
* variable priced here is Y2-BL. The file therefore contains two of this seat's changes, both gated:
* [OD-GROUP] (parent, shipped as #123927) - od's high bits carry the query group, the bucket is
* rebuilt from the FPOS table in K_frord, which deletes that pass's random 4 MB gather (7e6 loads);
* [Y2-BL] (this shot) - branchless argmin / scatter-max in the y2 group plane.
*
* The FG_maxr_y2 block runs once per solve over all N points and does two data-dependent things per
* point: (1) ds = argmin over d of s_gt[d][i] (a query's group = its smallest rank) and (2) for each
* other dim a scatter-max mr[d*MAXQ + b] = max(mr[...], R) into the 1 MB s_maxr table. Both are
* written as `if (...)` updates, i.e. 13 unpredictable data-dependent branches per point (13e6 per
* solve -- the compared values are ranks of random coordinates, so neither update is predictable).
* Rewriting both as conditional moves keeps the semantics exactly:
* nb = (g < best) ? g : best; ds = (g < best) ? d : ds; best = nb; // strict < keeps the
* first minimal d
* { u32 *mp = mr + d*MAXQ + b; u32 mv = *mp; *mp = (bb > mv) ? bb : mv; } // same maximum
* No value changes anywhere -> bit-exact: 39-cell k=7 gate (brute-force oracle n<=9000 mode 0-4 x 3
* seeds, n=1e5 mode 10-14, n=1e6 Q=0/1512/2700 checksums, n=1234567) 0 DIFF, checksums 7842486998 /
* 7782794688 unchanged.
* Local A/B (round-robin min-of-N, same argv, n=1e6 Q=1512): FG_maxr_y2 38.4e6 -> 28.5e6 ticks
* (-9.9e6, -26%). The block wall reading is inside the noise band, so the shot is priced on the
* phase counter; its mechanism (a mispredicted branch costs the same ~15-20 cycles on both machines)
* is the one class of local reading this seat has found to be machine-independent.
* Judge price calibration carried over from the parent shot: the judge pays for accesses / uops and
* NOT for touched footprint ([SG-NIB] #123904 lost 13.7 ms by shrinking a gather's footprint only),
* which is why this one removes instructions rather than bytes.
* =============================================================================== */
/* ===== a13as_ seat: [OD-GROUP] od's high 12 bits carry the query GROUP, the bucket is rebuilt in K_frord =====
* The K_frord pass (query re-ordering, once per dim, 7e6 elements per solve) accepts each point's
* group with a RANDOM 4 MB gather g = s_g[od_d[r] & 0xFFFFF] -- one random load per element into the
* same 4 MB footprint as s_pos. Meanwhile od_d[p]'s high 12 bits hold the point's BUCKET, which is a
* *function of the d-position p alone*: the d-order is sorted by value, so bucket(p) = the bucket of
* the value class containing p = ((class_end(p)) * bmag) >> 40 exactly as the sort computed it, and
* class_end(p) = (the next class start) - 1 is available from the FPOS table that A7 already built
* (FPOS(d,b) is by construction a class start, and is non-decreasing in b). So K_frord rebuilds the
* bucket from r with a cursor that only moves at class boundaries (~N/B steps per dim) and od's high
* bits are free to carry the group, which then arrives in the word K_frord already loads -- the gather
* (7e6 random loads) and its prefetch disappear entirely.
*
* Sort-phase restructure this needs (the group does not exist until all seven s_gt planes do):
* loop 1: A1..A4 (histogram / prefix / fused placement, no scatter, no BVAL)
* B_bdtr, s_maxr zero, the y2 group plane (all three only need s_gt / s_bdT / s_bd)
* loop 2: A5b scatter od[pp[i]] = i | (s_g[i] << 20)
* loop 3: A7 (BVAL / FPOS - it reads od, so it must follow loop 2)
* then C_pmfill (it reads BVAL), then the untouched remainder.
* Every array that leaves the block is value-identical: od's low 20 bits, s_frord's {id,bucket} words
* (rebuilt bit-exactly, see below), s_bd / s_bdT, BVAL / FPOS, s_pm, s_maxr. 39-cell k=7 gate
* (brute-force oracle n<=9000 mode 0-4 x 3 seeds, n=1e5 mode 10-14, n=1e6 Q=0/1512/2700 checksums,
* n=1234567) 0 DIFF, n=1e6 checksums 7842486998 / 7782794688 unchanged.
* Bucket equality is not a heuristic: the reconstruction is (class_end * bmag) >> 40 with the same
* bmag and the same Q-1 cap as the sort's own s_bdT write, so the word written to s_frord[d] is
* bit-identical to the od word the sort used to scatter (verified by the gate's checksums, and a
* wrong split would break the AND/fringe coverage, which the brute-force cells would show at once).
* Local A/B (round-robin min-of-N, same argv, n=1e6 Q=1512): K_frord 82.4e6 -> 34.7e6 ticks.
* =============================================================================== */
/* ===== REFERENCES =====
* saffah_codex_6a_agg3, https://duck.ac/submission/121929 : the current T (4315.755175 ms). The engine body is a
* byte-identical copy of that submission, inherited through saffah_cc_v41_agg1 #121984 (b13y3_ seat), #122107
* (b13y4_), #122246 (b13y5_), #122587 (a13ah_) and #122653 (a13ai_); only the reference/思路 header text
* differs between copies. All inherited citations retained; no separate license displayed.
* saffah_cc_v41_agg1 #123698 (a13aq_ seat), https://duck.ac/submission/123698 : the [PKSLOT] packed
* counting-sort slot word {start:20, arrival:12} (s_ct) this file carries unchanged; it is the current
* best of this account (4292.371024 ms) and the baseline this change is measured against.
* work/a13ar__tmp/a13ar_mkclk.py and a13ar_gate.sh (a13ar_ seat) : the rdtsc sub-phase clock / LOCAL_TEST
* 3-rep harness and the 39-cell k=7 equivalence gate, reused as a13as_mkclk.py and a13as_gate.sh.
* work/a13ar__tmp/a13ar_cmp.sh : round-robin min-of-N comparator, reused as a13as_ab.sh.
* ===== 思路 =====
* [a13as_ seat] [OD-GROUP]: move the query group into od's dead high bits (the bucket is a function of the
* d-position and is rebuilt from the FPOS table in K_frord), which deletes the pass's random 4 MB gather.
* Single variable; the restructure exists only because the group must be known before od is scattered.
* (A previous shot of this seat, [SG-NIB] #123904, packed s_g 4-bit-per-entry instead -- it kept the
* gather and only shrank its footprint, and the judge measured it 13.7 ms SLOWER: the footprint is not
* what this machine pays for.)
*/
/* ===== a13aq_ seat: [PKSLOT] packed counting-sort slot (single variable) =====
* The counting sort's placement pass and its gt/bucket pass index the SAME value slot v but
* touched two different 4 MB arrays (s_tmp for the running destination slot, s_cntv for the
* prefix-sum start), i.e. THREE random 4 MB accesses per (point, dim): s_tmp RMW, s_cntv load,
* od scatter. Here the two per-value words are packed into one 32-bit word
* s_ct[v] = { lo 20 bits: start[v] , hi 12 bits: arrival index within the class }
* so the placement pass reads s_ct[v] ONCE and derives everything the old pair of passes
* derived: q = start + arrival (identical to s_tmp[v]++ in the same i order),
* gt = start (identical to s_cntv[v]),
* num = s_ct[v+1] - 1 (identical to s_cntv[v+1] - 1; the neighbour slot's low
* field is never modified, and it usually shares the 64 B line),
* and bumps the arrival field in place. Every array (pp, gt, s_bdT, od, and the bucket bits)
* receives exactly the same values in exactly the same order, so the transformation is
* bit-exact -- 39-cell gate incl. the k=7 brute-force oracle, 0 diffs, n=1e6 checksums
* 7842486998 / 7782794688 unchanged.
* A 12-bit arrival field can only overflow for data whose value classes exceed 4096 points;
* that case is detected in the prefix-sum pass and the original three passes run instead, so
* correctness never depends on the packing.
* Priced on the judge: the whole setup block is 800.9e6 -> 723.0e6 local ticks (-9.7%), of
* which the fused pass replaces 214.5e6 by 150.8e6 (-29.7%); the judge-side setup split
* measured this round (#123669) put the old three-pass tail at 71.7 ms and the s_sig fill at
* 41.5 ms of a ~220 ms setup, so the tail is the largest single block of the remaining deficit.
* =============================================================================== */
/* ===== REFERENCES =====
* saffah_codex_6a_agg3, https://duck.ac/submission/121929 : the current T (4315.755175 ms). This file's engine body is
* a byte-identical copy of that submission, inherited through saffah_cc_v41_agg1 #121984 (b13y3_ seat), #122107
* (b13y4_), #122246 (b13y5_) and #122587 (a13ah_); only the reference/思路 header text differs between those copies.
* All inherited citations retained; no separate license displayed.
* ===== 思路 =====
* [a13ai_ seat] [TIEBATCH2]: the fringe byte-signature scan's ambiguous ("tie") positions are no longer resolved
* inline. Inline, each tie costs `odd[pos]` -> `s_pm[j]` : a two-level dependent load chain ending in a random
* 64B row of the 64 MB point-record array, which the OoO window cannot overlap with anything. Here the scan just
* APPENDS (i, pos, d, qT[8]) = 48B to a file-scope buffer (4 stores, no memory side effect, no chain), and a
* second pass after each ds group resolves the whole batch by software pipelining: phase A computes every
* j = s_ord[d][pos] and issues prefetch(s_pm + j*STRIDE) 256 entries ahead, phase B loads the rows and applies the
* identical `testc(cmpgt(qT,pv))` predicate. The integer `ok` values added to `out[i]` are unchanged, only their
* schedule is (integer addition is commutative, so the result is bit-identical: 43-cell gate, 0 diffs).
* Priced on the judge with a same-binary runtime toggle (g_nooff, no cross-binary layout noise), interleaved,
* n=3e5/Q=810: inline arm 503.997/503.907 ms, deferred arm 498.676/498.669 ms => -5.28 ms (-1.05%), in-arm
* spread <=0.09 ms. This is a work-removal change, not a prefetch/reorder change, so it prices on the probe;
* at the board geometry the record array is 64 MB (vs 19 MB here) so the removed DRAM latency per entry is larger.
* Buffer is capped (TIE_CAP 524288 entries); on overflow the original inline path runs, so correctness never
* depends on the buffer. k!=7 keeps the inline path (judge only calls count_7d).
* Gate: k=4..8 brute-force oracle, 5 modes x 3 seeds, plus n=1e6 checksums at Q=1512/1620/2700 - 43 cells, 0 diffs
* vs the shipped #121984 body.
*/
#define MF_NOSDMP 1
#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing,schedule-insns")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=skylake")
#define MF_QCOEF 110
#define MF_NOFILTB 1
#define MF_SPL ((size_t)1000064)
#include <immintrin.h>
#include <type_traits>
#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 char u8;
typedef unsigned short u16;
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
#endif
#define MAXK 8
#define STRIDE 16
#ifndef MF_APF
#define MF_APF 0
#endif
#ifndef MF_QCOEF
#define MF_QCOEF 122
#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 1800
#endif
#ifndef MF_NOFILTB
#define MF_NOFILTB 0
#endif
#ifndef MF_PFB
#define MF_PFB 6
#define MF_PFSC 32
#define MF_PFSC2 32
#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 2
#endif
#ifndef MF_FR_NOMETA
#define MF_FR_NOMETA 0
#endif
#ifndef MAXQ
#define MAXQ 4096
#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)));
#define E6Z_BDR (((size_t)(MAXN) + 31u) & ~(size_t)31u)
static u16 s_bdT[(size_t)MAXK * E6Z_BDR];
static u16 s_bd[(size_t)MAXN * MAXK];
static u32 s_g[MAXN];
static u32 s_qord[MAXN], s_tmp[MAXN], s_cntv[MAXN];
static u32 s_ct[MAXN + 8] __attribute__((aligned(64)));
static u16 s_bkt[MAXN];
static u16 s_bks[MAXN];
static u32 s_nid[MAXN];
static u32 s_pos[MAXK][MAXN];
static u32 s_posp[(size_t)MAXK * MAXN];
#ifndef MF_INCA
#define MF_INCA 1
#endif
#ifndef MF_INCA_PFD
#define MF_INCA_PFD 0
#endif
static int g_inca = 0;
static u32 *s_ho = 0;
static size_t s_ho_cap = 0;
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;
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];
static u8 *s_sig = 0;
static int g_sig_on = 0;
static int g_sig_merged = 0;
static u32 g_sigsh = 0;
static u32 solve_generation;
#define TIE_CAP 524288
#define TIE_EW 12
static u32 s_tbuf[(size_t)TIE_CAP * TIE_EW];
static u32 s_tj[TIE_CAP];
static u32 s_tn = 0;
static int g_nooff = 0;
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;
#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) {
__m128i lo = _mm256_castsi256_si128(v);
__m128i hi = _mm256_extracti128_si256(v, 1);
__m128i s = _mm_add_epi64(lo, hi);
return (u32)((u64)_mm_cvtsi128_si64(s) + (u64)_mm_extract_epi64(s, 1));
}
template<int KK>
__attribute__((target("avx2,popcnt")))
static u32 and_popcount_range(const u64 *const *bs, u32 Wr, u32 rem, const u64 *const *bsNext) {
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;
u32 wlim = (Wr > 96u) ? (Wr - 96u) : 0u;
for (; w + 8 <= wlim; w += 8) {
if (KK > 1) _mm_prefetch((const char *)(bs[1] + w + 96), _MM_HINT_T0);
if (KK > 2) _mm_prefetch((const char *)(bs[2] + w + 96), _MM_HINT_T0);
if (KK > 3) _mm_prefetch((const char *)(bs[3] + w + 96), _MM_HINT_T0);
if (KK > 4) _mm_prefetch((const char *)(bs[4] + w + 96), _MM_HINT_T0);
if (KK > 5) _mm_prefetch((const char *)(bs[5] + w + 96), _MM_HINT_T0);
if (KK > 6) _mm_prefetch((const char *)(bs[6] + w + 96), _MM_HINT_T0);
if (KK > 7) _mm_prefetch((const char *)(bs[7] + w + 96), _MM_HINT_T0);
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < KK; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi64(acc0, _mm256_sad_epu8(_mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)), z));
__m256i b = LDU256((bs[0] + w + 4));
for (int d = 1; d < KK; d++) b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc1 = _mm256_add_epi64(acc1, _mm256_sad_epu8(_mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)), z));
}
if (bsNext) {
u32 off = 0;
for (; w + 8 <= Wr; w += 8, off += 8) {
if (KK > 1) _mm_prefetch((const char *)(bsNext[1] + off), _MM_HINT_T0);
if (KK > 2) _mm_prefetch((const char *)(bsNext[2] + off), _MM_HINT_T0);
if (KK > 3) _mm_prefetch((const char *)(bsNext[3] + off), _MM_HINT_T0);
if (KK > 4) _mm_prefetch((const char *)(bsNext[4] + off), _MM_HINT_T0);
if (KK > 5) _mm_prefetch((const char *)(bsNext[5] + off), _MM_HINT_T0);
if (KK > 6) _mm_prefetch((const char *)(bsNext[6] + off), _MM_HINT_T0);
if (KK > 7) _mm_prefetch((const char *)(bsNext[7] + off), _MM_HINT_T0);
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < KK; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi64(acc0, _mm256_sad_epu8(_mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)), z));
__m256i b = LDU256((bs[0] + w + 4));
for (int d = 1; d < KK; d++) b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc1 = _mm256_add_epi64(acc1, _mm256_sad_epu8(_mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)), z));
}
}
for (; w + 8 <= Wr; w += 8) {
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < KK; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi64(acc0, _mm256_sad_epu8(_mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)), z));
__m256i b = LDU256((bs[0] + w + 4));
for (int d = 1; d < KK; d++) b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc1 = _mm256_add_epi64(acc1, _mm256_sad_epu8(_mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)), z));
}
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 lo2 = _mm256_and_si256(a, lm);
__m256i hi2 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi64(acc0, _mm256_sad_epu8(_mm256_add_epi8(_mm256_shuffle_epi8(lk, lo2), _mm256_shuffle_epi8(lk, hi2)), z));
}
tot = _mm256_add_epi64(acc0, acc1);
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>
__attribute__((target("avx2,popcnt")))
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 ASTRL = STRIDE;
#if MF_ASCR
const u32 d1 = (ds == 0) ? 1u : 0u;
const u32 e1 = (d1 < ds) ? d1 : d1 - 1;
{
const u32* fo=s_frord[d1];
for(u32 qi=q0;qi<q1;qi++)s_qord[qi]=fo[qi]&0xFFFFFu;
}
#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 * E6Z_BDR + s_qord[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 = s_qord[qi]; s_tmp[cntv[s_bdT[(size_t)dd * E6Z_BDR + id] + 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 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 + ((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
{
#if MF_INCA
const u32 *a13_ho = 0;
u32 a13_app = 0;
if (g_inca) {
a13_ho = s_ho;
for (u32 w = 0; w < AS_WORDS; w++) s_ascr[w] = 0;
}
#endif
u32 qi = q0;
while (qi < q1) {
const u32 *fo=s_frord[d1];
u32 b1=fo[qi]>>20;
u32 qe=qi+1;
while(qe<q1 && (fo[qe]>>20)==b1)qe++;
const u64 *bp1 = g_plen_on ? (s_bs + s_pofs[(size_t)e1 * MAXQ + b1])
: (s_bs + ((size_t)e1 * (Q + 1) + b1) * W);
#if MF_INCA
if (a13_ho) {
u32 pto = (b1 < Q) ? FPOS(d1, b1) : (u32)N;
const u32 *hp = a13_ho;
#if MF_INCA_PFD > 0
while (a13_app < pto) {
if (a13_app + MF_INCA_PFD < pto)
_mm_prefetch((const char *)(s_ascr + (hp[a13_app + MF_INCA_PFD] >> 6)), _MM_HINT_T0);
u32 q = hp[a13_app]; s_ascr[q >> 6] |= 1ull << (q & 63); a13_app++; }
#else
while (a13_app < pto) { u32 q = hp[a13_app]; s_ascr[q >> 6] |= 1ull << (q & 63); a13_app++; }
#endif
bp1 = s_ascr;
} else
#endif
{
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 (nwd <= AS_WORDS) {
const u64 *src = bp1;
for (u32 w = 0; w < nwd; w++) s_ascr[w] = src[w];
bp1 = s_ascr;
}
}
const u64 *bp2v[2][MAXK];
u32 Rcur = s_gt[ds][s_qord[qi]];
{
const u16 *bd0 = s_bd + (size_t)s_qord[qi] * MAXK;
for (int e = 0; e < K1; e++) {
if (e == (int)e1) bp2v[qi & 1u][e] = bp1;
else { int d = (e < ds) ? e : e + 1;
bp2v[qi & 1u][e] = g_plen_on ? (s_bs + s_pofs[(size_t)e * MAXQ + bd0[d]])
: (s_bs + ((size_t)e * (Q + 1) + bd0[d]) * W); }
}
}
for (u32 qq = qi; qq < qe; qq++) {
u32 i = s_qord[qq];
#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 * MAXK), _MM_HINT_T0);
_mm_prefetch((const char *)(s_gt[ds] + j), _MM_HINT_T0);
__asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(out + j)));
}
}
#endif
if (qq + 1 < qe) {
const u16 *bdn = s_bd + (size_t)s_qord[qq + 1] * MAXK;
const u64 **bn = bp2v[(qq + 1) & 1u];
for (int e = 0; e < K1; e++) {
if (e == (int)e1) bn[e] = bp1;
else { int d = (e < ds) ? e : e + 1;
bn[e] = g_plen_on ? (s_bs + s_pofs[(size_t)e * MAXQ + bdn[d]])
: (s_bs + ((size_t)e * (Q + 1) + bdn[d]) * W); }
}
}
const u32 R = Rcur;
if (qq + 1 < qe) Rcur = s_gt[ds][s_qord[qq + 1]];
u32 cnt = 0;
if (R && !g_skip_and) {
cnt = and_popcount_range<KK - 1>(bp2v[qq & 1u], R >> 6, R & 63u,
(qq + 1 < qe) ? bp2v[(qq + 1) & 1u] : 0);
}
out[i] = cnt;
}
qi = qe;
}
}
#else
for (u32 qi = q0; qi < q1; qi++) {
u32 i = s_qord[qi];
const u16 *bd = s_bd + (size_t)i * MAXK;
#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 * MAXK), _MM_HINT_T0);
_mm_prefetch((const char *)(s_gt[ds] + j), _MM_HINT_T0);
_mm_prefetch((const char *)(out + j), _MM_HINT_T0);
}
}
#endif
#ifdef PF_DIST
if (qi + PF_DIST < q1) {
u32 j = s_qord[qi + PF_DIST];
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 + ((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, 0);
}
out[i] = cnt;
}
#endif
if (g_skip_fringe) return;
const u32 *const avpool=s_pm+8;
auto fringe_dim = [&](auto dim) {
constexpr int d=decltype(dim)::value;
if(d==ds) return;
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 u8 *const sbase = s_sig + (size_t)d * (k-1) * MF_SPL;
const u32 *const odd = s_ord[d];
for (u32 qi = q0; qi < q1; qi++) {
u32 i = fo[qi] & 0xFFFFFu;
#if MF_PFB > 0
{
u32 qj = qi + MF_PFB;
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 *)(s_gt[d] + j), _MM_HINT_T0);
__asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(out + j)));
}
}
#endif
const u32 lo = FPOS(d, fo[qi] >> 20);
const u32 hi = s_gt[d][i];
if (lo >= hi) continue;
const u32 *rec = s_pm + (size_t)i * STRIDE;
const u32 *Avp = avpool + (size_t)i * ASTRL;
__m256i qr = _mm256_or_si256(_mm256_load_si256((const __m256i *)rec), khi8v);
__m256i Avm = _mm256_or_si256(LDU256(Avp), notexlo);
__m256i qT = _mm256_min_epi32(qr, Avm);
__m256i qTh;
if (k > 9) {
__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 if (k > 8) {
qTh = _mm256_or_si256(LDU256((rec + 8)), khi8hv);
} else {
qTh = all8;
}
u32 add = 0;
const u32 *c0 = s_sdmp[d] ? (s_sdmp[d] + (size_t)lo * g_KS) : 0;
if (g_use_filt && KK == 9) {
const u32 w0 = lo >> 6;
const u32 nw = ((hi - 1) >> 6) - w0 + 1;
const u64 wcs = (u64)N / g_Qc + 1;
const u32 FW = g_fbm_W;
const u64 *rows[8];
int nr = 0;
for (int e = 0; e < 9; e++) {
if (e == d) continue;
u32 cell = (u32)((u64)rec[e] / wcs) + 1;
if (cell > g_Qc) cell = g_Qc;
rows[nr++] = s_fbm + ((size_t)(d * 9 + e) * (g_Qc + 1) + cell) * FW + w0;
}
const u64 *r0 = rows[0];
const u64 *r1 = rows[1];
const u64 *r2 = rows[2];
const u64 *r3 = rows[3];
const u64 *r4 = rows[4];
const u64 *r5 = rows[5];
const u64 *r6 = rows[6];
const u64 *r7 = rows[7];
const u32 remh = hi & 63u;
{
u64 vv = r0[0] & r1[0] & r2[0] & r3[0] & r4[0] & r5[0] & r6[0] & r7[0];
vv &= ~0ull << (lo & 63);
if (nw == 1u && remh) vv &= (1ull << remh) - 1;
u32 word = w0;
#if MF_FR_NOCAND
vv = 0;
#endif
while (vv) {
int t = __builtin_ctzll(vv);
vv &= vv - 1;
u32 j = (word << 6) + (u32)t;
const u32 *cp = c0 ? (c0 + (size_t)(j - lo) * g_KS) : (s_pm + (size_t)(s_ord[d][j] & 0xFFFFFu) * STRIDE);
__m256i pv = LDU256(cp);
__m256i pvh = LDU256(cp + 8);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
add += ok;
}
}
for (u32 w = 1; w + 1 < nw; w++) {
u64 vv = r0[w] & r1[w] & r2[w] & r3[w] & r4[w] & r5[w] & r6[w] & r7[w];
u32 word = w0 + w;
#if MF_FR_NOCAND
vv = 0;
#endif
while (vv) {
int t = __builtin_ctzll(vv);
vv &= vv - 1;
u32 j = (word << 6) + (u32)t;
const u32 *cp = c0 ? (c0 + (size_t)(j - lo) * g_KS) : (s_pm + (size_t)(s_ord[d][j] & 0xFFFFFu) * STRIDE);
__m256i pv = LDU256(cp);
__m256i pvh = LDU256(cp + 8);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
add += ok;
}
}
if (nw > 1u) {
u32 w = nw - 1u;
u64 vv = r0[w] & r1[w] & r2[w] & r3[w] & r4[w] & r5[w] & r6[w] & r7[w];
if (remh) vv &= (1ull << remh) - 1;
u32 word = w0 + w;
#if MF_FR_NOCAND
vv = 0;
#endif
while (vv) {
int t = __builtin_ctzll(vv);
vv &= vv - 1;
u32 j = (word << 6) + (u32)t;
const u32 *cp = c0 ? (c0 + (size_t)(j - lo) * g_KS) : (s_pm + (size_t)(s_ord[d][j] & 0xFFFFFu) * STRIDE);
__m256i pv = LDU256(cp);
__m256i pvh = LDU256(cp + 8);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
add += ok;
}
}
out[i] += add;
continue;
}
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) * g_KS) : (s_pm + (size_t)(s_ord[d][j] & 0xFFFFFu) * 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_cmpgt_epi32(qTh, pvh), all8);
}
add += ok;
}
}
out[i] += add;
continue;
}
if (g_sig_on && (hi - lo) >= 2) {
__m256i qsb[16];
{
const __m256i zero8 = _mm256_setzero_si256();
const __m256i shv = _mm256_set1_epi32((int)g_sigsh);
const __m256i bias8 = _mm256_set1_epi8((char)0x80);
const __m256i sv_lo = _mm256_srlv_epi32(qT, shv);
const __m128i u16=_mm_packus_epi32(_mm256_castsi256_si128(sv_lo),_mm256_extracti128_si256(sv_lo,1));
const __m128i u8s=_mm_packus_epi16(u16,u16);
const __m256i packed=_mm256_xor_si256(_mm256_broadcastsi128_si256(u8s),bias8);
for (int e = 0; e < k; e++) {
if(e==(int)d)continue;
qsb[e-(e>(int)d)]=_mm256_shuffle_epi8(packed,_mm256_set1_epi8((char)e));
}
}
u32 aj = lo, aacc = 0, aexact = 0;
if (lo + 32u <= hi) {
const u32 ax_last = hi - 32u;
const int ax_e0 = ((int)d == 0) ? 1 : 0;
do {
__m256i ac=_mm256_subs_epi8(LDU256(sbase+aj),qsb[0]);
for(int e=1;e<k-1;e++){
__m256i cv=LDU256(sbase+(size_t)e*MF_SPL+aj);
ac=_mm256_max_epi8(ac,_mm256_subs_epi8(cv,qsb[e]));
}
u32 decm = (u32)_mm256_movemask_epi8(ac);
aacc += (u32)__builtin_popcount(decm);
{
__m256i eqz = _mm256_cmpeq_epi8(ac, _mm256_setzero_si256());
if (!_mm256_testz_si256(eqz, eqz)) {
u32 amb = (u32)_mm256_movemask_epi8(eqz);
if (k == 7 && !c0 && !g_nooff && s_tn + 32u <= (u32)TIE_CAP) {
u32 *te = s_tbuf + (size_t)s_tn * TIE_EW;
do {
int t = __builtin_ctz(amb); amb &= amb - 1;
te[0] = i; te[1] = aj + (u32)t; te[2] = (u32)d;
_mm256_storeu_si256((__m256i *)(te + 3), qT);
te += TIE_EW; s_tn++;
} while (amb);
} else {
while (amb) {
int t = __builtin_ctz(amb); amb &= amb - 1;
const u32 *cp = c0 ? (c0 + (size_t)(aj + (u32)t - lo) * g_KS) : (s_pm + (size_t)(odd[aj + (u32)t] & 0xFFFFFu) * 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_cmpgt_epi32(qTh, pvh), all8);
}
aacc += okl;
}
}
}
}
aj += 32u;
} while (aj <= ax_last);
}
{
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;
const int ax_e0t = ((int)d == 0) ? 1 : 0;
__m256i ac=_mm256_subs_epi8(LDU256(sbase+base),qsb[0]);
for(int e=1;e<k-1;e++){
__m256i cv=LDU256(sbase+(size_t)e*MF_SPL+base);
ac=_mm256_max_epi8(ac,_mm256_subs_epi8(cv,qsb[e]));
}
u32 decm = ((u32)_mm256_movemask_epi8(ac)) & kmask;
__m256i ax_eqz = _mm256_cmpeq_epi8(ac, _mm256_setzero_si256());
u32 amb = _mm256_testz_si256(ax_eqz, ax_eqz) ? 0u : (((u32)_mm256_movemask_epi8(ax_eqz)) & kmask);
aacc += (u32)__builtin_popcount(decm);
if (amb) {
if (k == 7 && !c0 && !g_nooff && s_tn + 32u <= (u32)TIE_CAP) {
u32 *te = s_tbuf + (size_t)s_tn * TIE_EW;
do {
int t = __builtin_ctz(amb); amb &= amb - 1;
te[0] = i; te[1] = base + (u32)t; te[2] = (u32)d;
_mm256_storeu_si256((__m256i *)(te + 3), qT);
te += TIE_EW; s_tn++;
} while (amb);
} else {
while (amb) {
int t = __builtin_ctz(amb); amb &= amb - 1;
const u32 *cp = c0 ? (c0 + (size_t)(base + (u32)t - lo) * g_KS) : (s_pm + (size_t)(odd[base + (u32)t] & 0xFFFFFu) * 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_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 + g_KS));
__m256i p2 = LDU256((c + 2 * g_KS));
__m256i p3 = LDU256((c + 3 * g_KS));
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 * g_KS;
}
for (; j < hi; j++, c += g_KS) {
__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 + g_KS));
__m256i p2 = LDU256((c + 2 * g_KS));
__m256i p3 = LDU256((c + 3 * g_KS));
__m256i h0 = LDU256((c + 8));
__m256i h1 = LDU256((c + g_KS + 8));
__m256i h2 = LDU256((c + 2 * g_KS + 8));
__m256i h3 = LDU256((c + 3 * g_KS + 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 * g_KS;
}
for (; j < hi; j++, c += g_KS) {
__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] & 0xFFFFFu) * STRIDE;
__m256i pv = _mm256_load_si256((const __m256i *)c);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = _mm256_load_si256((const __m256i *)(c + 8));
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
}
add += ok;
}
}
out[i] += add;
}
};
if constexpr(KK>0) fringe_dim(std::integral_constant<int,0>{});
if constexpr(KK>1) fringe_dim(std::integral_constant<int,1>{});
if constexpr(KK>2) fringe_dim(std::integral_constant<int,2>{});
if constexpr(KK>3) fringe_dim(std::integral_constant<int,3>{});
if constexpr(KK>4) fringe_dim(std::integral_constant<int,4>{});
if constexpr(KK>5) fringe_dim(std::integral_constant<int,5>{});
if constexpr(KK>6) fringe_dim(std::integral_constant<int,6>{});
if constexpr(KK>7) fringe_dim(std::integral_constant<int,7>{});
if constexpr(KK>8) fringe_dim(std::integral_constant<int,8>{});
if constexpr(KK>9) fringe_dim(std::integral_constant<int,9>{});
}
__attribute__((target("avx2,popcnt")))
static void a13_tie_flush(u32 *out) {
u32 n = s_tn;
if (!n) return;
s_tn = 0;
const __m256i all8 = _mm256_set1_epi32(-1);
u32 b0 = 0;
while (b0 < n) {
u32 b1 = b0 + 256u; if (b1 > n) b1 = n;
for (u32 q = b0; q < b1; q++) {
const u32 *e = s_tbuf + (size_t)q * TIE_EW;
u32 j = s_ord[e[2]][e[1]] & 0xFFFFFu;
s_tj[q] = j;
_mm_prefetch((const char *)(s_pm + (size_t)j * STRIDE), _MM_HINT_T0);
}
for (u32 q = b0; q < b1; q++) {
const u32 *e = s_tbuf + (size_t)q * TIE_EW;
const u32 *cp = s_pm + (size_t)s_tj[q] * STRIDE;
__m256i pv = LDU256(cp);
__m256i qv = _mm256_loadu_si256((const __m256i *)(e + 3));
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qv, pv), all8);
out[e[0]] += ok;
}
b0 = b1;
}
}
__attribute__((target("avx2")))
static void solve_mf(u32 N, const unsigned **x, u32 *out, int k) {
++solve_generation;
s_tn = 0;
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;
#if !MF_NOFILTB
overhead += (u64)k * k * 4 * N;
#endif
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 (k == 9 && N >= 900000) q = 1400;
if ((u64)q > Qmem) q = (u32)Qmem;
if (q > N) q = N;
if (q > (u32)(MAXQ - 1)) q = (u32)(MAXQ - 1);
g_Q = q;
g_B = (N + q - 1) / q;
}
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];
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);
}
const int K1 = k - 1;
for (int d = 0; d < k; d++) {
const unsigned *xd = x[d];
u32 *od = s_ord[d];
static u8 hist8[MAXN+1] __attribute__((aligned(64)));
u32 *ct=s_ct;
for(u32 i=0;i<=N;i++)hist8[i]=0;
for(u32 i=0;i<N;i++){u32 v=xd[i];hist8[v<N?v:0]++;}
u32 sum=0;
for(u32 i=0;i<=N;i++){u32 c=hist8[i];ct[i]=sum;sum+=c;}
int pk=(sum==N);
if (!pk) {
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; } }
{
u32 *pp = s_pos[d];
for (u32 i = 0; i < N; i++) {
#if MF_PFSC2 > 0
if (i + MF_PFSC2 < N) { u32 vp = xd[i + MF_PFSC2]; _mm_prefetch((const char *)(s_tmp + (vp < N ? vp : 0u)), _MM_HINT_T0); }
#endif
u32 v = xd[i]; if (v >= N) v = 0; u32 q = s_tmp[v]++; pp[i] = q;
}
}
{ u32 *gt = s_gt[d];
for (u32 i = 0; i < N; i++) {
#if MF_PFSC > 0
if (i + MF_PFSC < N) { u32 vp = xd[i + MF_PFSC]; _mm_prefetch((const char *)(s_cntv + (vp < N ? vp : 0u)), _MM_HINT_T0); }
#endif
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);
u32 bbq = bb > Q - 1 ? Q - 1 : bb;
s_bdT[(size_t)d * E6Z_BDR + i] = bbq;
} }
#if MF_FB2
for (u32 i = 0; i < N; i++) {
#if MF_PFSC2 > 0
if (i + MF_PFSC2 < N) { u32 vp = xd[i + MF_PFSC2]; _mm_prefetch((const char *)(s_tmp + (vp < N ? vp : 0u)), _MM_HINT_T0); }
#endif
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
} else {
{
u32 *pp = s_pos[d];
u32 *gt = s_gt[d];
u32 *ctp = s_ct;
for (u32 i = 0; i < N; i++) {
#if MF_PFSC2 > 0
if (i + MF_PFSC2 < N) { u32 vp = xd[i + MF_PFSC2]; _mm_prefetch((const char *)(ctp + (vp < N ? vp : 0u)), _MM_HINT_T0); }
#endif
u32 v = xd[i]; if (v >= N) v = 0;
u32 w = ctp[v];
u32 st = w & 0xFFFFFu;
pp[i] = st + (w >> 20);
gt[i] = st;
u32 num = (ctp[v + 1] & 0xFFFFFu) - 1u; if (num > N) num = N;
u32 bb = (u32)(((u64)num * bmag) >> 40);
u32 bbq = bb > Q - 1 ? Q - 1 : bb;
s_bdT[(size_t)d * E6Z_BDR + i] = bbq;
ctp[v] = w + (1u << 20);
}
}
}
#endif
}
for (u32 i0 = 0; i0 < N; i0 += 64) {
u32 i1 = i0 + 64; if (i1 > N) i1 = N;
for (u32 i = i0; i < i1; i++) {
u16 *dst = s_bd + (size_t)i * MAXK;
for (int dd = 0; dd < k; dd++) dst[dd] = s_bdT[(size_t)dd * E6Z_BDR + i];
}
}
#if MF_INCA
{
size_t needho = (size_t)N * sizeof(u32) + 4096;
if (needho > s_ho_cap) { s_ho = (u32 *)pool_alloc(needho); s_ho_cap = s_ho ? needho : 0; }
g_inca = (s_ho && (u64)N <= (u64)AS_WORDS * 64ull) ? 1 : 0;
}
#endif
{
size_t mrn = (size_t)MAXK * MAXK * MAXQ;
for (size_t z = 0; z < mrn; z++) s_maxr[z] = 0;
}
{
static u32 y2_dsb[1024], y2_bst[1024];
for (u32 i0 = 0; i0 < N; i0 += 1024) {
u32 i1 = i0 + 1024; if (i1 > N) i1 = N;
for (u32 i = i0; i < i1; i++) {
u32 best = 0xFFFFFFFFu; u32 ds = 0;
for (int d = 0; d < k; d++) {
u32 g = s_gt[d][i];
u32 nb = (g < best) ? g : best;
ds = (g < best) ? (u32)d : ds;
best = nb;
}
y2_dsb[i - i0] = (u32)ds;
y2_bst[i - i0] = best;
s_g[i] = (u32)ds;
}
if (g_plen_on) {
for (u32 i = i0; i < i1; i++) {
u32 ds = y2_dsb[i - i0];
u32 bb = y2_bst[i - i0];
const u16 *bdv = s_bd + (size_t)i * MAXK;
u32 *mr = s_maxr + ((size_t)ds * MAXK) * MAXQ;
const int first=g_inca?1:0;
for (int d = first; d < k; d++) {
if (d == ds || (g_inca && ds==0 && d==1)) continue;
u32 b = bdv[d];
{ u32 *mp = mr + (size_t)d * MAXQ + b; u32 mv = *mp; *mp = (bb > mv) ? bb : mv; }
}
}
}
}
}
/* [a13as_ OD-GROUP] od[d][p] now carries the point's query group in its high bits; the bucket it
used to carry is rebuilt from p in K_frord. */
for (int d = 0; d < k; d++) {
u32 *od = s_ord[d];
const u32 *pp = s_pos[d];
for (u32 i = 0; i < N; i++) {
#if MF_PFSC2 > 0
if (i + MF_PFSC2 < N) { u32 qp = pp[i + MF_PFSC2]; _mm_prefetch((const char *)(od + qp), _MM_HINT_T0); }
#endif
od[pp[i]] = i | ((u32)s_g[i] << 20);
}
}
for (int d = 0; d < k; d++) {
/* BVAL/FPOS moved out of the sort loop: it reads od, which loop 2 above fills. */
const unsigned *xd = x[d];
u32 *od = s_ord[d];
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] & 0xFFFFFu];
BVAL(d, b) = v;
u32 gs = pos;
while (gs > 0 && xd[od[gs - 1] & 0xFFFFFu] == v) gs--;
FPOS(d, b) = gs;
}
BVAL(d, Q) = 0xFFFFFFFFu; FPOS(d, Q) = 0;
}
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];
for (int d = k; d < STRIDE; d++) p[d] = 0;
const u16*bd=s_bd+(size_t)i*MAXK;
for(int d=0;d<k;d++)p[8+d]=BVAL(d,bd[d]);
for(int d=k;d<8;d++)p[8+d]=0x7fffffffu;
}
{
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) || (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
#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] & 0xFFFFFu] < 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] & 0xFFFFFu] < 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), _mm256_load_si256((const __m256i *)(src + w)));
for (; w < W; w++) dst[w] = src[w]; }
#else
for (u32 w = 0; 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] & 0xFFFFFu] < v) pend++; }
#endif
while (ptr < pend) { u32 q = pd[pe[ptr] & 0xFFFFFu]; 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), _mm256_load_si256((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();
}
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; }
for (int d = 0; d < k; d++) {
u32 pos[MAXK];
for (int ds = 0; ds < k; ds++) pos[ds] = gstart[ds];
/* [a13as_ OD-GROUP] the group of the point at d-position r rides in od's high bits; the bucket
is rebuilt here as max{b : FPOS(d,b) <= r}. FPOS(d,b) is the first d-position of bucket b and
the d-order is sorted by value, so bucket(r) is monotone in r and one monotone cursor over the
FPOS table (Q steps per dim, amortised 0.0015 per element) recovers it exactly. */
const u32 *fpo = s_fpos + (size_t)d * MAXQ;
u32 bb = 0, nb = (Q > 1) ? fpo[1] : N;
u32 e_cur = ((Q > 1) ? (fpo[1] - 1u) : (N - 1u));
u32 bl = (u32)(((u64)e_cur * bmag) >> 40);
if (bl > Q - 1) bl = Q - 1;
for (u32 r = 0; r < N; r++) {
if (r >= nb) { /* class boundary: only ~N/B times per dim */
while (bb + 1 < Q && fpo[bb + 1] <= r) bb++;
e_cur = (bb + 1 < Q) ? (fpo[bb + 1] - 1u) : (N - 1u);
bl = (u32)(((u64)e_cur * bmag) >> 40);
if (bl > Q - 1) bl = Q - 1;
nb = (bb + 1 < Q) ? fpo[bb + 1] : N;
}
u32 x = s_ord[d][r];
u32 id = x & 0xFFFFFu;
u32 dst = pos[x >> 20]++;
s_frord[d][dst] = id | (bl << 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;
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] & 0xFFFFFu) * STRIDE), _MM_HINT_T0);
#endif
const u32 *row = s_pm + (size_t)(od[j] & 0xFFFFFu) * 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;
for(int e=0;e<k;e++)if(e!=d){u32 z_=row[e]>>g_sigsh;sb[(size_t)(e-(e>d))*MF_SPL+j]=(u8)(z_^0x80u);}
}
}
if (s_sig) g_sig_merged = 1;
}
}
}
}
if (s_sig && !g_sig_merged && k==7) {
static u8 cached_signature[(size_t)MAXN*8] __attribute__((aligned(64)));
for(u32 i=0;i<N;i++)for(int e=0;e<7;e++){u32 v=x[e][i]>>g_sigsh;cached_signature[(size_t)i*8+e]=(u8)(v ^ 0x80u);}
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;auto emit=[&](auto tag){constexpr int OMIT=decltype(tag)::value;
for(;j+8<=N;j+=8) {
if(j+64<N)_mm_prefetch((const char *)(cached_signature+(size_t)(od[j+64]&0xFFFFFu)*8),_MM_HINT_T0);
__m128i r0=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)(od[j+0]&0xFFFFFu)*8));
__m128i r1=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)(od[j+1]&0xFFFFFu)*8));
__m128i r2=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)(od[j+2]&0xFFFFFu)*8));
__m128i r3=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)(od[j+3]&0xFFFFFu)*8));
__m128i r4=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)(od[j+4]&0xFFFFFu)*8));
__m128i r5=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)(od[j+5]&0xFFFFFu)*8));
__m128i r6=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)(od[j+6]&0xFFFFFu)*8));
__m128i r7=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)(od[j+7]&0xFFFFFu)*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);
__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 constexpr(OMIT!=0)_mm_storel_epi64((__m128i*)(base+(size_t)(0-(0>OMIT))*MF_SPL+j),v0);
if constexpr(OMIT!=1)_mm_storel_epi64((__m128i*)(base+(size_t)(1-(1>OMIT))*MF_SPL+j),_mm_srli_si128(v0,8));
if constexpr(OMIT!=2)_mm_storel_epi64((__m128i*)(base+(size_t)(2-(2>OMIT))*MF_SPL+j),v1);
if constexpr(OMIT!=3)_mm_storel_epi64((__m128i*)(base+(size_t)(3-(3>OMIT))*MF_SPL+j),_mm_srli_si128(v1,8));
if constexpr(OMIT!=4)_mm_storel_epi64((__m128i*)(base+(size_t)(4-(4>OMIT))*MF_SPL+j),v2);
if constexpr(OMIT!=5)_mm_storel_epi64((__m128i*)(base+(size_t)(5-(5>OMIT))*MF_SPL+j),_mm_srli_si128(v2,8));
if constexpr(OMIT!=6)_mm_storel_epi64((__m128i*)(base+(size_t)(6-(6>OMIT))*MF_SPL+j),v3);
}
};switch(d){case 0:emit(std::integral_constant<int,0>{});break;case 1:emit(std::integral_constant<int,1>{});break;case 2:emit(std::integral_constant<int,2>{});break;case 3:emit(std::integral_constant<int,3>{});break;case 4:emit(std::integral_constant<int,4>{});break;case 5:emit(std::integral_constant<int,5>{});break;case 6:emit(std::integral_constant<int,6>{});break;}
for(;j<N;j++) {
const u8 *row=cached_signature+(size_t)(od[j]&0xFFFFFu)*8;
for(int e=0;e<k;e++)if(e!=d)base[(size_t)(e-(e>d))*MF_SPL+j]=row[e];
}
}
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;
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] & 0xFFFFFu) * STRIDE), _MM_HINT_T0);
#endif
const u32 *row = s_pm + (size_t)(od[j] & 0xFFFFFu) * STRIDE;
for(int e=0;e<k;e++)if(e!=d){u32 z_=row[e]>>g_sigsh;base[(size_t)(e-(e>d))*MF_SPL+j]=(u8)(z_^0x80u);}
}
}
}
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 *const spp = s_pos[ds];
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];
#if MF_INCA
if (g_inca && d == ((ds == 0) ? 1 : 0)) {
u32 *dstho = s_ho;
const u32 *hp = spp;
for (u32 j = 0; j < N; j++) dstho[j] = hp[od[j] & 0xFFFFFu];
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;
while (ptr < pend) { u32 q = spp[od[ptr] & 0xFFFFFu]; 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), _mm256_load_si256((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
}
query_group<7>(N, out, ds, q0, q1, Q, Wpool);
a13_tie_flush(out);
}
}
void count_7d(int n, const unsigned *x[7], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 7); }
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 4.252 s | 569 MB + 40 KB | Accepted | Score: 100 | 显示更多 |