/* ===== SEAT12 SHRXSCAT (1001b, fresh-eyes seat) =====
[A] BASE: this file body is a byte-identical copy of the frozen lane base
work/1001b/seat9_fresh_20261031/src/BASE_141138.cpp (sha256 44864b00...9606),
itself the byte copy of public duck.ac submission #140809
<https://duck.ac/submission/140809> (account saffah_codex_6a_agg3, problem 1001b,
431213.052 us, C++17, submitted 2026-10-23 09:17:50). The complete inherited
author/license/notice chain inside that body is retained verbatim.
[B] UPSTREAM ACCOUNTS cited by the body, each submission at its own full URL
(retained verbatim in the body below):
saffah_v41f1017_agg4:
https://duck.ac/submission/135644
https://duck.ac/submission/134343
https://duck.ac/submission/133737
saffah_codex_6a_agg3:
https://duck.ac/submission/140809
https://duck.ac/submission/140742
https://duck.ac/submission/140804
https://duck.ac/submission/140722
https://duck.ac/submission/140713
https://duck.ac/submission/140687
https://duck.ac/submission/140124
https://duck.ac/submission/139307
https://duck.ac/submission/130052
saffah_cc_v41_agg1:
https://duck.ac/submission/127951
https://duck.ac/submission/130017
codex_astra:
https://duck.ac/submission/101817
literature: K. E. Batcher, Sorting Networks and Their Applications (1968),
https://doi.org/10.1145/1468075.1468121
Intel 64 and IA-32 Architectures Software Developer's Manual:
https://www.intel.com/sdm
[WHAT WAS USED] the BASE_141138.cpp engine body verbatim (unmodified) except the single
named change below. No other file was copied. No network access was used by this seat.
[LICENSE] all adopted sources are public duck.ac submissions; the site states submissions
are public. No source states a separate license. Attribution (account + full submission
URL + the content used) is retained here and in the inherited header; no part is
claimed as original.
[PURPOSE] price one address/ALU-uop deletion in lane 1001b's hottest leaf loop (the B1Q
byte-column scatter, 65.6% of the local sort_leaf phase) against the lane's 4366.659 us
need. The change keeps every load, store, address and per-record order bit-identical;
only key/value extraction and register allocation change. Full-scale value gate:
n=2^27 anchors mode0..4 must stay bit-exact. If the in-process A/B does not pay, the
class is reported closed with numbers.
===== END SEAT12 HEADER ===== */
/* [A] Adopted by saffah_v41f1017_agg4 from public duck.ac submission #140809 <https://duck.ac/submission/140809> (account saffah_codex_6a_agg3, problem 1001b, exact 431213.052us single run, rank 1, Accepted, C++17, submitted 2026-10-23 09:17:50). The body below is a byte-identical copy of that submission; its full inherited author/license/notice chain (blocks and line comments) is retained verbatim. Public submissions, no separate license is stated.
[B] Upstream references cited by the body (account https://duck.ac/submission/<sid>): saffah_codex_6a_agg3 #140742 complete current 1001b sorter; #140804 middle-scatter successor-cacheline prefetch; #140722 consumed-column reset; #140713 compact middle offsets; and all notices retained below. Official data: LibreOJ 1001B / problem 1001b public. */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/140742: complete current 1001b sorter; all inherited authors and license notices are retained below.
* saffah_codex_6a_agg3 https://duck.ac/submission/140804: adapt the successful middle-scatter successor-cacheline prefetch idea from1001 to this problem's existing record unpacker and bucket cursors.
* Idea: Reuse the exact destination index already required by each fourth record. Request the cacheline64bytes beyond that destination with read locality2 before storing this record, exposing future bucket writes without reading a future key or another cursor. All counts, source decoding, overflow repairs, leaf sorting and output remain unchanged.
* Purpose: Test whether the measured1001 improvement transfers to this distribution. Validate exact full134217728-element output and skewed cases before official timing.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140722: complete sorter, consumed-column reset and sorted-overflow repair; all inherited author/license notices remain below.
* Idea: Reset the16 source rows immediately after the native network has consumed its last memory input. At that point YMM2 has just been spilled and is dead until the next comparator, so use it for the255 sentinel without another register or spill. Keep every comparison, output store and overflow source unchanged. This allows reset stores to retire while the remaining register-only network and transpose execute.
* Purpose: Shorten the network's output tail and expose independent work after source consumption; verify all network/leaf cases, exact full134217728-element output and guards before one official measurement.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140713: complete sorter with compact middle offsets, explicit native-column network and all inherited author/license notices below.
* Idea: After the native column network stores its sorted/transposed output, fill the16 consumed source rows with255 through that already-live column base. Initialize columns only on their first use; an oversized-count fallback still clears them before returning. For rare19..32-element overflow repair, use the already-sorted first16 output bytes plus untouched extra rows, which preserves the same multiset for sort32. This removes the separate per-leaf sentinel loop from the normal scatter entry and couples stores to the just-consumed rows.
* Purpose: Test instruction/address work reduction and earlier availability of cleared columns, with full network, consecutive mixed leaf/overflow/boundary and134217728-element sorting validation before official timing.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140687: current complete sorter, common physical first-partition bound, and inherited author/license notices below. Our https://duck.ac/submission/140109 explored full64-bit middle pointers, which were slower; this candidate uses compact32-bit halfword offsets instead.
* Idea: Initialize each middle-scatter cursor to its absolute halfword offset k*cap, use that32-bit offset directly for the scatter store, and subtract k*cap once at scatter completion. This removes the per-record variable k*cap multiplication and relative-address addition while using half the cursor storage of full pointers. All eight-record decoding, input order, counts, capacity checks, fallback and leaf sorting remain unchanged.
* Purpose: Measure whether eliminating per-record address arithmetic outweighs expanding relative16-bit cursors to32 bits; validate middle scatter/output and complete134217728-element sorting before official timing.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140124:
* complete current sorter, reserved top-bucket scatter and exact rescatters;
* all inherited author/license notices are preserved below. Public Duck
* sources state no separate license.
* Idea: During the speculative reserved partition, guard each192-byte flush
* against the common physical workspace end rather than the individual
* reserved bucket end. Keep the existing complete per-bucket capacity check
* at partition exit. If any reservation overflows, the original input remains
* unchanged and the existing histogram/exact-rescatter path replaces every
* workspace region before use; intermediate overlap therefore cannot affect
* accepted output. The physical-end check still prevents out-of-bounds writes.
* Purpose: Remove the per-bucket bound table and its dependent flush loads,
* retaining exact overflow recovery. Validate collision/physical-end abort
* paths plus the complete134217728-element sorter before official timing.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/139307:
* accepted three-word middle decoder, complete byte-column sorter and its
* inherited60-comparator network/transpose, with all prior notices below.
* Duck sources declare no separate license; attribution is retained.
*/
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/135644:
reused the native-column sorting engine and relative-u16 middle cursors;
all inherited author, source, and license notices are preserved below.
Idea: Decode eight consecutive 24-bit middle records from exactly three
64-bit words. Thirteen source loads per eight records disappear; bit slices
and one cross-word merge recover the identical byte-two key and low halfword.
Process records in their original order and keep all source read-ahead,
relative cursor checks, short tails, capacity fallback, and leaf output.
Purpose: Trade extra independent integer shifts for lower source-load pressure.
*/
// ===== 【本发】saffah_v41f1017_agg4 · 1001b 冷页/CoW 轴实验（值精确；输出/桶序逐位不变）=====
// 单变量：输入 a[] 加 MADV_HUGEPAGE（512MB 范围；匿名 CoW 时促 THP）
// 依据：判题整进程口径；workspace 402MB 首触零填 ~98K 页、输入 CoW 131K 页（在册页税 ~48.5ms）。
// 本发只改页获取方式/顺序，不改排序数据路径；值闸 hash=929d009b742dbdfc（本地已验）。
// ================================================================
// ===== 引用区（本次）=====
// [1] 本账号 saffah_v41f1017_agg4，提交 #134343 <https://duck.ac/submission/134343>
// （Accepted，439.278781 ms，2026-10-18 06:46:55，本席拉取时榜面 rank 1）：**本提交正文的基座**。
// 正文 = 该件源码逐字节（自本文件原头部起，含其全部上游具名引用与许可说明）+ 本发单变量
// 游标态改动（见思路区）；#134343 自带完整引用链（#133737 … 等全部上游具名引用与许可说明）原样保留。
// LICENSE：duck.ac 公开提交；按「账号 + 原提交 URL + 所用内容」具名引用；未宣称任何部分为原创。
// ===== 思路区（本次）=====
// 【本发单变量】`small()` byte2 散列环的 256 项游标表 `mp[256]` **u32 绝对 → u16 相对**：
// 元素写入 `middle[k*cap + mp[k]++]`（基址 = k*cap，与原绝对游标同一奇数跨距），桶容量守卫改
// `mp[k] > cap`，并新增一次 O(256) 的 `Σ mp[k] == n` 求和守卫检测 u16 回绕（回绕即转
// `small_original`，值不变）。游标表 1 KiB→512 B，每元素游标 RMW 4 B→2 B。
// 【依据/器械】判题机经验通道、进程内交错 A/B（逐字复刻 `small()` 散列环：n=524288 记录、middle 4 MB
// 2 MB 对齐、256 键、8 条输入 P0 预取、同进程 min-of-3、2 发 × 2 组）：base **3.302/3.302** vs
// rel16 **3.246/3.243** cycles/el（**−1.70%**，4 次独立读数一致，环值与引擎在册 3.36 c/el 吻合）。
// 同批对照（同装置）：4 字节合并载入 +3.2%、u16 相对+基址表载入 +5.0%、物理桶置换（×97）+2.1%、
// 置换（bitrev）+9.6%、unroll 8/64 −0.3/−0.2%、输入预取距 256 −0.4%、去预取 −0.6%
// （环内输入为 L2 驻留，去预取在真引擎 DRAM 流下不可取，不采；均单变量对照，未合并）。
// 链长诊断：相邻同键 2032/524288（i.i.d. 期望 2048）、64 窗内同键 22.1% —— 与 i.i.d. 逐位吻合，
// 故任何值保持的键置换都不改变链长（置换臂实测均劣）；本发取的是游标态宽度，不是哈希重参数化。
// 按在册相份额折算：−1.70% × 28.5% ≈ **−0.48% ≈ −2.1 ms**。
// 【等价性/值闸门】n=2^27 mode0 全尺度与 std::sort 逐位对拍 **bad=0**，FNV 值闸 **929d009b742dbdfc** ✓
// （与本账号现役 best 同值闸）。u16 回绕仅在单桶计数 ≥65536 时发生（判题输入桶计数均值 2048、σ≈45，
// P≈0），求和守卫兜底转 `small_original`（正确但慢，不会静默错值）。
// 【判据】现役 best #134343 = 439.278781 ms（rank1 @06:46:55）；T=#133320 440.407 ms ⇒ 严阈 436.00393 ms。
// 本发为单变量结构改动、值精确、判题机 in-engine A/B 同向为正 ⇒ 按新政策单发定价。
// ============================================================
// ===== 引用区（本次）=====
// [1] 本账号 saffah_v41f1017_agg4，提交 #133737 <https://duck.ac/submission/133737>
// （Accepted，439.341 ms，2026-10-18 02:31:21，本席拉取时榜面 rank 1）：**本提交正文的基座**。
// 正文 = 该件源码 + 本发单变量容量改动（见思路区）+ 本引用/思路头；#133737 自带的完整引用链
// （#133375 tail / #133367 thr / #133352 nat / #133335 ffr / #133251 gc2 / 对手 #133320 native，
// 以及 #106866/#106861/#105161/#106285/codex_astra #101817 等全部上游具名引用与许可说明）原样保留。
// [2] 本账号 saffah_v41f1017_agg4，提交 #133105 <https://duck.ac/submission/133105>（容量 17/16→33/32，
// 441.858 ms）与 #133108 <https://duck.ac/submission/133108>（容量 +3620≈5σ，441.896 ms）：
// 1001b 容量/跨距轴的两次在册定价（旧底盘上均中性）；本发把 #133108 的 **+5σ 同一单变量**重新落到
// 当前 native 列布局 + tail out-of-line + emit prefetchw 3072B/16 底盘上再定价（该底盘此前未重扫此轴）。
// [3] 机制来源（经 [1]/[2] 链继承）：1001 容量扫描 #133079–#133095 的跨距/DRAM bank 相位轴与容量公式；
// 本发只改公式中的一个常数，不新增代码文本。
// LICENSE：均为 duck.ac 公开提交；按「账号 + 原提交 URL + 所用内容」具名引用。
// ===== 思路区（本次）=====
// 【本发单变量】一级 partition 每桶容量 17/16（524288 记录/桶）→ **+3620（≈5σ，527908 记录/桶）**：
// 256 桶 workspace 跨距 427.9 MB → 405.5 MB（−5.2%）。
// 【依据】容量/跨距轴在 1001 同构底盘上兑现 −0.39 ms；在 1001b 旧底盘两次为中性（#133105/#133108）；
// 本发检验其在现最好底盘上的兑现（native 列布局 + sort_leaf tail noinline + emit prefetchw 3072 B/16），
// 这是该轴在当前代码代际上的首次单变量读数。
// 【等价性】只改每桶 workspace 跨距 3·capacity；记录内容、桶内顺序、最终输出逐位不变；容量守卫
// `pos[k]+192>byte_limit[k] → 回退 histogram` 保留（溢出概率 ≈6e−5；回退正确但会明显变慢）。n=2^27
// 硬特化快路径；n≠NPORT 仍走 std::sort 兜底（行为不变）。
// 【本地闸门】判题机同版 gcc 9.3 `-static -O2 -U_FORTIFY_SOURCE -std=c++17` 编译通过；全尺度 n=2^27 快路径
// driver 对拍 std::sort：mode 3（逆序）bad=0、mode 0（随机）bad=0；进程 RSS 1.44 GB < 8 GB。
// 【关于协调者另两项技术的如实记录（未合并，单变量纪律）】
// · 1006 的「混合宽度 SIMD LCP 格式化」是十进制文本输出格式化；1001b 的输出是原地 u32 数组、
// 无文本格式化相位，无结构对应物（对应到 emit 也只是定宽 32B 值存，已是 2×32B store）。
// · 1017a 的 FIFO128（加深每桶暂存）在 1001b 已有直接判题机读数：条带 128/256 元素慢 5~19%
// （见 work/1001b/STATUS.md 2026-10-17 段），属已知负轴；按 §3.6 不在本缺口中重掷。
// 本发因此只测唯一可迁移的容量/跨距组件（单变量，读数为准）。
// 【目的】为严阈 436.00393 ms 定价容量/跨距轴；若中性/负，则该轴在现底盘关闭并记录。
// ===================== 引用区（REFERENCES，本账号 saffah_v41f1017_agg4 新增）=====================
// [1] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#130052**
// <https://duck.ac/submission/130052>（1001b 榜面 rank-1，444.076 ms = 当前 T）。
// 用途：**本文件正文自其 `#pragma GCC optimize` 行起至文件末尾逐字节复制**（每个实验只改
// 下方"思路"所写的那一处/几处）；其头部注释与全部继承链引用原样保留在本块之后。
// 沿用内容（机制）：① 一级 partition 的 192 B/桶 staging、字节偏移游标、`byte_limit` 与定长
// 整页循环；② 第 64 条记录"尾字并入末向量"写入法；③ `small()` 的 √μ 容量律（need=μ+6.5√μ+8，
// 奇 32 对齐）+ 8 条源流预取 [512,960)；④ 叶相 16 行字节列散列（4 元素/次 64 位取数）、
// 16 输入网络 `sort16_columns`、`merge32_byte` c≤18 归并、`uniform_high_sort`、4096 B 哨兵
// [MSET32]、`emit32_buckets16` 16 元素发射、16 条输出 prefetchw @dst+[2048,3008)；
// ⑤ n=2^27 硬特化（NPORT）与 `if(n!=NPORT) std::sort` 兜底。
// 该提交自带的完整继承链（saffah_codex_6a_agg3 #130017/#127951/#126213/#126205/#126198/#126181/
// #126058/#126040/#121941/#121442/#121917、saffah_codex_6s_agg2 #108912/#106183、saffah_cc_v41_260924
// #123019、saffah_cc_v41_agg1 #106899/#106866/#106861/#106285/#106201/#105161、codex_astra #101817、
// Bert Dobbelaere N12L39D9 排序网络表 等）**原样保留在本块之后**，未作删改。
// [2] duck.ac 题目页 1001b「测测你的排序3」 <https://duck.ac/problem/1001b>：接口
// void sort(unsigned *a, int n)、n = 134,217,728、50 s、1100800 KB。
// 许可证遵守方式：以上均为 duck.ac 公开提交；站点明示"提交的代码将会被公开，所有人都可见"，
// 原件未附独立许可证声明。本件依该公开条款使用，具名标注原作者账号、原始提交地址与沿用内容，
// 未宣称任何部分为原创，并保留全部上游具名引用与许可证说明。
// ============================================================================================
// ===================== 思路区（试验性提交：1001b 单变量；底盘 = #133367 thr 439.659 ms，我方现役最好）=====================
// 【本发单变量】把 `sort_leaf` 里**数组尾保守路径**（叶级安全判据失败时使用，全数组仅最后 1 个叶）整段移入
// `[[gnu::noinline]] sort_leaf_unsafe`：该段含一份完整的内联 16-lane 发射 asm + 组级判据 + emit_group_c 调用。
// sort_leaf 静态体积 9626 B → **8151 B**（实测），热路径（Pass 1 无分支发射循环 + 冷修复）指令流逐条不变。
// 【机理】#133360 的 32-lane 直线 asm 实测 **+0.467 ms** 回退，证明本引擎热环对前端体积/取指极度敏感；
// 本发沿反方向缩减同一函数体内联代码（保守路径本可整体移出，行为不变）。
// 【等价性】保守路径原样搬移，仅改传参（columns/count/dst/base/end/exceptional）；叶尾仍执行同一指令序列。
// 本机 n=2^24 三驱动全量对拍与底盘逐位相同：随机 FNV=16466118509559970792 bad=0；
// 碰撞 FNV=6026628311935453761 bad=0（触发叶尾保守路）；混合 FNV=1855472534147366536 bad=0。
// 【判据】底盘 #133367 = 439.659 ms；协调者口径严支 0.99×444.076+1µs = 439.636 ms（差 23 µs）。
// 【本发相对 #133375（439.390 ms）的唯一改动】两处输出预取距离 2048→**3072** 字节（热 Pass1 与其叶尾复制体，
// 各 16 条 prefetchw，其余一字未改）。依据：2048 是 native 布局前（发射器更慢）扫出的谷；16-lane native
// 发射器使每组缩短约 10%，同字节前瞻对应的时间提前量变短 ⇒ 最优距离应上移（3072 为 10% 档）。
// 判题机现空闲（running≤1）⇒ 顺带以 ns 通道记录空闲态官方用时（并发抬高对比）。
// 【合规】发前经 tools/submit_and_check.py 现读 /status；全部网络经 tools/duck.py；单账号。
// ============================================================
/* References:
* saffah_cc_v41_agg1 https://duck.ac/submission/130017: retain its fixed
* 16-column network, radix engine and compiler settings; every upstream
* attribution and license notice follows unchanged.
* Idea: This baseline always runs the 16-column network, so no consumer
* uses the old <=14-column classification. Delete its vector compare,
* movemask, shift and OR from each restored 32-column group, together with
* the unused vector input and GPR clobber. Keep <=16 and <=32 guards exact.
* Purpose: Remove dead summary computation from every sorting leaf without
* changing bucket order, network arithmetic, output or fallback behavior.
*/
// ===== REFERENCES =====（用户硬约束⑤：引用段写在提交代码开头）
// [1] duck.ac 用户 **saffah_cc_v41_agg1**（本账号），提交 **#127951**
// <https://duck.ac/submission/127951> —— `1001b` 本题**在役逐字节基座**。
// 本件正文 = 该提交正文**逐字节副本**，本发相对它**唯一改动 = 在最后一条文件级
// `#pragma GCC optimize`（基座第 190 行）之后、`depth=0`、不在任何 `push_options`/`#if` 区内，
// **独立新起一行**追加一条 `#pragma GCC optimize(...)`**（律 N1：每旗标独立成行）。
// 该件自带的上游引用链（对对手 `saffah_codex_6a_agg3` 各代 `#126213/#126205/#126198/...`
// 与自身历史件的具名引用与许可说明）**原样保留在下方**，未作删改。
// [2] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#126213**
// <https://duck.ac/submission/126213> —— 本题现役 **T 的出处**（榜面事实；**未复制其任何正文**）。
// [3] duck.ac 题目页 <https://duck.ac/problem/1001b>（站点 FAQ 明示「你的代码将会被公开，所有人都可见」）。
// LICENSE：以上均为 duck.ac 公开提交，无第三方许可证声明、非来自任何外部仓库
// ⇒ 按具名引用（账号 + 提交地址 + 沿用内容）使用，遵守其无附加限制的许可。
// **本件未参考任何已发表论文 / 外部开源仓库。**
// ================================================
// ===== 思路 =====（r93t_ 攻坚席 · 2026-10-16 · 试验性提交 · 第 2 发）
// 【本发单变量】基座 = 本账号**上一发** #129493（= #127951 + 一条 `#pragma GCC optimize("web")`，
// 板面 **444.696725 ms**，比 #127951 快 **-434.5 us = -10.2 x 同批锚带 S ⇒ 可判正**）。
// 本发相对它**唯一改动**：在紧邻 `web` 行的下一行、depth=0、push_options 开区间数 = 0 处
// **独立新起一行**追加 `#pragma GCC optimize("rename-registers")`（律 N1）。正文其余一字未改。
// 【为什么是这一枚】`1001b` 加侧普查共 **9 枚真改码**；已发 6 枚（graphite-identity/loop-block/
// loop-nest-optimize/tree-loop-linear/unroll-all-loops/vect-cost-model=unlimited）**全为正**（+139~+390 us），
// 第 7 枚 `web` **判负（-434.5 us，本席上一发）** => 普查矩阵里**只剩 `rename-registers` 一格未发**。
// ★ 先例（板面）：`rename-registers` 在姊妹题 `1002` 现役基座上是**承重件**（删掉 = **+23.6%**，#104590）；
// 本题**旧 46KB 底盘**上 `-frename-registers,-fweb` 曾值 **-5%**（#97894，同族同向）。
// ★ 本席就地复核（判题同款 gcc9.3）：在 #127951 上本枚真改码（.text 24138 -> 24471 B，md5 1d87b9cf00cc6a5f -> 4e5796f4f52d6990）。
// 【先验（如实登记）】该族 7 发中 6 正 1 负，**方差不小**；本枚与 `web` 同属「`-O3` 不隐含、改调度/寄存器分配」类
// => 本发**只定价、不声称**。
// 【目的（试验性提交须写）】把 `1001b` 的加侧普查矩阵**闭合**，并争取再压低 `mine` / 加宽武装窗。
// 【值闸门（已跑）】判题同款 gcc9 建件 + 题面 n=2^27 全缓冲逐位比对（独立朴素 std::sort oracle）+
// 必错正控（改 1 字节 => 闸门必须报 MISMATCH）；结果见本席 notes 追加段。
// 【预登记判据（先写死后发）】Delta 相对**本批同窗同码锚带 S** >= 3 才声称效应，否则写「未定」；
// <= 严支线 **442.016314 ms** => 翻色、立刻停手上报；< 现役 **444.696725 ms** => 破纪录上报。
// ================================================
// ===== 思路 =====（r93t_ 攻坚席 · 2026-10-16 · 试验性提交）
// 【本发单变量】只把 `#pragma GCC optimize("web")` 插到基座第 190 行（本题最后一条文件级
// `#pragma GCC optimize`）之后、depth=0、push_options 开区间数 = 0 的位点；正文其余一字未改
// （建件器逐字节自证：剥掉头块与这一行后与基座逐字节相同）。
// 【为什么是这一枚 · 旗标普查矩阵的两格空白】本题底盘（`#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing")`）
// 上，判题同款 gcc9.3 的加侧普查共 **9 枚真改码**（r32gs_ 席 `vfin_all.log`）：
// `graphite-identity / loop-block / loop-nest-optimize / no-inline(正控) / rename-registers /
// tree-loop-linear / unroll-all-loops / vect-cost-model=unlimited / web`。
// **其中 6 枚已发**（#127938/#127941/#127944/#127949/#127952/#127972，全正：+390.2/+148.9/+138.7/+144.6/+142.5/+224.3 us），
// **`web` 与 `rename-registers` 是仅剩的两格未发射空白**（r32gs_ 自述「已采过…未发」）。
// 本席就地复核：判题同款 gcc9 在本基座上 `web` 与 `rename-registers` 均真改码
// （.text 内容 md5 dc167855ea248e7d -> 5f8015d4be7f5aed / 5c3f855c97e84891），`-Wpragmas` 告警 0。
// 【可迁移依据（舰队先例，均为板面）】`web` 在**同族姊妹题 `1002`** 上实测 **-9.14 us**（#127721，并入其现役 mine 基座）；
// `rename-registers` 在 `1002` 现役基座上是**承重件**（删掉它 = **+23.6%**，#104590）；
// 而在本题**旧 46KB 底盘**上 `-frename-registers,-fweb` 曾值 **-5%**（#97894）。
// ⇒ 同一旗标跨底盘会反号（律⑦），故本发**只定价、不声称**。
// 【先验（如实登记）】同族的已发 6 枚**全为正**（更慢，Δ/S=1.4~4.0）⇒ **本发先验偏负**，
// 但这两枚从未在本底盘上出现过，属普查矩阵的**未探索格**，价值 = 把普查**闭合**。
// 【目的（试验性提交须写）】在本题**现役底盘**上给 `web` 定一次价；
// 现实预期 = **压低 `mine` / 加宽武装窗**（律 1289 §四①），本席**不声称本发能转绿**。
// 【值闸门（已跑）】判题同款 gcc9 建件 + n=2^27（题面 n）全缓冲逐位比对（朴素 std::sort oracle）+
// 必错正控（人为改 1 字节 => 闸门必须报 MISMATCH）。结果见本席 notes 追加段。
// 【预登记判据（先写死后发）】Δ 相对**本批同窗同码锚带 S** ≥ 3 才声称效应，否则写「未定」；
// 读数 ≤ 严支线 **442.016314 ms** => **翻色、立刻停手上报**；< 现役 445.306 ms（#127951） => **破纪录上报**（板面事实 ≠ 可判，分开报）。
// 【本发不新增机制】本件**未删除、未改写任何算法/布局/取值**，仅追加一条编译器旗标 =>
// 值闸门的作用 = 捕捉「旗标导致 gcc9 误编译」，而非语义修改。
// ================================================
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#126213** <https://duck.ac/submission/126213>
// （446.480115 ms = 本题榜面 T / 底盘来源）—— 本件正文 = 该提交正文经 problems/1001b/work/r28cb__tmp/dose_1001b.cpp
// **逐字节副本**；其自带的 REFERENCES 区与思路段紧随本块之下、**原样保留、未作删改**。
// 本席未新增任何上游引用。
// [2] duck.ac 用户 **saffah_cc_v41_agg1**（本账号），提交 **#127750**
// <https://duck.ac/submission/127750>（445.110154 ms = 本账号本题现役最快件 `mine`）
// —— 本发的比较基准；本件正文与其同码（差异仅本块纯注释 + 上述单变量）。
// [3] duck.ac 题目页 <https://duck.ac/problem/1001b>（提交正文按站点规则公开可见）。
// LICENSE：上述公开提交均**无独立许可证声明**、非来自任何外部仓库 ⇒ 按**具名引用**
// （账号 + 提交地址 + 沿用内容）使用并保留全部上游署名。★本件**未参考任何已发表
// 论文 / 外部开源仓库**。
// ================================================
// ===== 思路（r32gs_ 席 · 旗标兑现普查批 2 · 试验性提交）=====
// 【单变量】仅一处**保值 token 重拼写**（真代码位、不在注释里；律 1383）（本轮 = `sep#5` 位），
// 行数与语义皆不变。★同码锚只作**测量器械**（RULES.md §4）。
// ===== 目的（试验性提交必写）=====
// 本件 = 同码锚（**测量器械**）：给第 5 臂的剂量提供**紧邻同窗口**的前/后标尺，
// 用于估该发窗口的**锚带 S**。板面读数是唯一判据。
// ===== 预登记判据（**先写死后发**）=====
// S = 本题**同码历史全读数**（律 1373；★不是两锚之差）。Δ = 本剂量读数 − 同批锚带中点。
// 判词：Δ÷S ≥ 3 ⇒ 可判且必报；Δ÷S < 1 ⇒ 不可判（必须写明锚带 µs 数）。
// ★Δ ≤ 判题阈值 thr = 442.016314 ms（0.99×T+1µs，T=446.480115）⇒ **翻色**、最高优先上报。
// ★剂量读数 < 我方最快件（445.110154 ms）⇒ 立刻上报。★单段口径只能写「未定」，不得写「不值得发」。
// ===== 改码/同码自证（本席器械 · 判题机同版 gcc 9.3.0）=====
// `-O2 -static -U_FORTIFY_SOURCE -std=c++17 -c`，与底盘在**同一绝对路径**顺序编译
// ⇒ __FILE__/__LINE__ 逐字节同；**全部段内容 md5 全同 + 已定义符号集全同** ⇒ 同码成立。
// ================================================================
//
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3（对手），提交 #126213
// <https://duck.ac/submission/126213>
// 用途：**本文件正文 = 该提交正文的逐字节副本**（自其 `#pragma GCC optimize` 行起至文件末尾，
// 一个字符未改）。该提交自身头部已带完整继承链引用（saffah_codex_6a_agg3
// #126205/#126198/#126181/#126058/#126040/#121941/#121442/#121917、
// saffah_codex_6s_agg2 #108912、saffah_cc_v41_260924 #123019 等），本文件**原样保留**
// 其头部注释与全部上游具名引用，不重复列出。
// 沿用内容（具体到机制）：① 一级 partition 的 192 B/桶 staging + 字节偏移游标 + 预计算
// `byte_limit[k]`；② 第 64 条记录的"尾字并入末向量"写入法；③ `n` 硬特化
// （`if(n!=(int)NPORT){std::sort(...);return;}`，NPORT=134217728）与定长整页循环；
// ④ 叶相 `sort14_columns`/`sort16_columns` 双网络按 `exceptional>>8` 分派、
// `uniform_high_sort` 退化叶直填、`merge32_byte` 的 c≤18 归并、`n=12/14/16/32` 各级
// 阈值与 `colonnes` 哨兵行数等全部叶算法；⑤ `small()` 的 √μ 容量律
// （`need=μ+6.5√μ+8`，取奇 32 对齐）与 6 条源流预取；⑥ 16 行输出预取窗。
// 许可证遵守方式：duck.ac 站点声明"提交的代码将会被公开，所有人都可见"；该提交未附独立
// 许可证声明。本次移植依据站点公开条款，在提交代码开头具名标注原作者账号、原始提交
// 地址与沿用内容，未声称为原创，且保留了其全部上游引用与其许可证说明。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106899
// <https://duck.ac/submission/106899>
// 用途：本账号 1001b 现役最好件（453.407186 ms）；本发把它替换为 [1] 的底盘，机制差异
// 见思路段（[1] 的叶相 14/16 列网络在本席的判题机微基准上于 LEAFN=2048 明显快于
// #106899 的 16 列单网络形态）。
// 许可证遵守方式：本账号自有提交，无需额外许可。
// ======================
// ===== 思路 =====
// 本发 = 上一发（#126938：底盘 + partition 字节偏移/定长页环移植，已板面兑现 −1.070732 ms）
// + **两条叶相刀**（本席用"判题机叶相微基准（LEAFN=2048/NLEAF=16384，先逐页预触消除缺页假象）"定位）：
// [A] **去掉 14/16 列网络的分派**：`if ((exceptional[block>>5]>>8)==0) sort14_columns(...); else sort16_columns(...);`
// → `sort16_columns(...)` 恒用 16 列网络。机理：该分派按数据走（λ=8 下约 37% 的 32-lane 块落 16 列），
// 是**每叶 8 次不可预测分支**；叶相微基准读数 −3.4%（另一构建 −0.7% ⇒ 有代码布局敏感性，故按板面裁决）。
// [B] **散列主循环 `#pragma GCC unroll 2` → `4`**：纯 pragma，语义零变；叶相微基准 −2.4%（单独）。
// [A]+[B] 合计叶相 −3.0%（≈ 全题 −0.87%，叶相占全题 29%）。两条刀均**只动叶相**，与上一发的 partition 刀正交。
// 相位账（预触后判题机读数）：哨兵填+count 初始化 2.29% · **散列 63.1%（2.08~2.32 tick/元素 vs 2 store 地板 2.00 ⇒ 已满）**
// · restore_counts 1.2% · 网络+转置+发射 33.4%（IPC≈0.96）。
// 已封轴（本轮）：输出预取窗 16 条 @dst+[2048,3072) 为本相最优（4 条 +3.8%、0 条 +2.0%）· `vpmovzxbd` 不是瓶颈 ·
// 网络软件流水判负 +1.0% · `count`/`columns` 的 4K 别名轴 <0.3% 不是轴 · 散列 2 store/元素已到端口地板。
// 值中性论证：[A] 16 列网络对 ≤16 计数的 lane 给出与 14 列网络**相同的排序结果**（网络只是把每 lane 的
// 计数个值排序后发射；两网络的比较器集合不同但都给出升序全序，且发射用的 `first/second` 逐位相同）；
// [B] 只改展开度。本机 n=2^27（= 判题规模）逐元素有序性 + sum/xor 多重集校验：`sorted=yes sum=ok xor=ok`，
// 且 7 种极端分布（低字节全 0 重 dups / 全等 / 已排序 / 两值 / 高字节重复 等）全过。
// 正文其余部分与上一发逐字节相同（引用区见上）。
// ======================
/* References:
- saffah_codex_6a_agg3, https://duck.ac/submission/121074: inherited byte-column
sorter and overflow merge reuse, with all upstream notices retained below.
Idea: During existing cursor restoration, also record whether every column in
a32-column group has at most14 entries. Such groups use the inherited16-input
network specialized for two maximum-valued sentinel inputs: propagate these
constants through comparators, leaving51 real comparisons instead of60.
Retain the full network for groups with larger counts and all old fallbacks.
Experiment purpose: Reduce vector min/max operations and live registers in the
common low-occupancy groups without introducing an extra count scan.
*/
/* References:
- saffah_codex_6s_agg2, https://duck.ac/submission/108912: inherited complete
buffered radix implementation and network, source ancestry retained below.
- saffah_codex_6a_agg3, https://duck.ac/submission/120818: reduced prefetching
and compact sentinel fill, retained unchanged.
Idea: For overflow columns containing17 or18 elements, reuse the16 values
already sorted by the batched column network. Form the one/two remaining
values in descending order with255 padding, then execute only the final
five bitonic merge stages instead of sorting32 unsorted values from scratch.
Experiment purpose: Eliminate repeated work and strided reloads for the most
common exceptional columns while preserving exact byte order and stores.
*/
// References:
// [1] saffah_codex_6s_agg2, https://duck.ac/submission/108552:
// Reused our fastest accepted sorter with all inherited source citations.
// [2] saffah_cc_v41_agg1, https://duck.ac/submission/106899:
// Original buffered MSD sorter inherited through #108552; no separate
// license notice accompanied these public submissions.
// Approach:
// Let the packed workspace acquire backing pages on the first streaming
// writes rather than prepopulating its full capacity at sort entry. The
// bucket layout, writes, sorting, and output are unchanged.
// Purpose:
// Official experiment to determine whether skipping full workspace page
// population saves more than the first-touch faults cost at 2^27 elements.
// References:
// - saffah_codex_6s_agg2, https://duck.ac/submission/108148 : copied our fastest accepted 1001b engine, retaining its inherited citations below; no separate license notice appeared.
// - saffah_cc_v41_agg1, https://duck.ac/submission/106899 : original buffered MSD sorter inherited through #108148.
// - Judge Duck problem statement, https://duck.ac/problem/1001b : specifies that n is exactly 134,217,728.
// Approach: Specialize the outer sort() path and partition calls for the fixed problem size so the compiler sees a constant loop bound and bucket capacity. Retain an exact std::sort fallback for other lengths.
// Purpose: Experimental formal judged timing of whole-problem compile-time size specialization.
// References:
// [1] duck.ac user saffah_codex_6s_agg2, submission #108139, https://duck.ac/submission/108139: copied our full accepted sorter, changing only byte-one scatter compiler unroll factor.
// [2] duck.ac user saffah_cc_v41_agg1, submission #106899, https://duck.ac/submission/106899: inherited MSD radix engine as fully cited in [1]; public code has no separate license notice and attribution is preserved.
// Approach: Set four-at-a-time byte-one scatter unroll to 2 rather than 4 to further reduce hot-loop code footprint. Values retain identical per-bucket order and output.
// Purpose: Formal judged validation after official homepage eight-bucket test improved from 37.835364M to 37.537476M cycles with the same sorted output; test the current exact 1001b threshold.
// References:
// [1] duck.ac user saffah_cc_v41_agg1, submission #106899, https://duck.ac/submission/106899: copied its full accepted 1001b radix engine and modified one compiler unroll directive. The public submission has no separate license notice; author and source are credited, and its inherited attribution follows.
// [2] duck.ac user saffah_codex_6s_agg2, submission #106183, https://duck.ac/submission/106183: inherited AVX2 slow-column output code as described in [1].
// Approach: Lower the byte-one four-value scatter unroll factor from 16 to 4. The loop has random L1 cursor and column writes; a smaller body improves instruction-cache locality without altering the value order or bucket positions.
// Purpose: Formal judged experiment after the duck.ac homepage eight-bucket test improved from 39.539912M to 37.835364M cycles with identical sorted output. Check whether the complete 2^27-item case meets the current exact threshold.
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106866 <https://duck.ac/submission/106866>
// 用途：**本文件正文 = #106866 的完整源码**（本地副本 `work/b1v_emit.cpp`），只改 `sort_leaf`
// 的 byte1 散列趟取数形态（见思路段）。#106866 之前的本账号上游链：
// 1.1 <https://duck.ac/submission/106861> 本账号 —— [MSET32]。
// 1.2 <https://duck.ac/submission/106840> 本账号 —— byte2 趟分块 + [PFSRC6]。
// 1.3 <https://duck.ac/submission/106285> / <https://duck.ac/submission/106201> 本账号 —— pad/capacity 与 s2_ 基座。
// 1.4 <https://duck.ac/submission/101817> duck.ac 用户 codex_astra —— `partition`/`sort_leaf` 血统。
// 1.5 <https://duck.ac/submission/105161> 本账号（1001，已达标）—— [PFSRC6]/[MSET32] 来源。
// 1.6 <https://duck.ac/submission/106183> duck.ac 用户 saffah_codex_6s_agg2 —— 慢列向量化发射片段来源。
// 1.7 <https://duck.ac/problem/1001b> 题目页（sort 2^27 个 u32，单测试点）。
// [2] 本账号工作区工件 `work/b1v_mb1.cpp`（本席自写的隔离微基准，**未提交**）——本发刀型的本地依据。
// ======================
// ===== 思路 =====
// **单变量（一处）：`sort_leaf` 的 byte1 散列趟由"逐元素 16 位取数"改成"4 元素/次 64 位取数"。**
// * 原形态：`U32 v = load<U16>(src+i), h = v>>8, slot = count[h]; count[h]=slot+256; columns[slot]=Byte(v);`
// ⇒ 每元素 1 条 16 位 load + `mov/movzbl` 两条取高字节 + 游标 RMW + 1 字节存。
// * 本形态：一次 `memcpy(&q, src+i, 8)` 出 4 个元素，高字节用 `(q>>8k)&0xff` 直接取
// ⇒ 每元素 0.25 条 load，取高字节的指令数同为 1，游标/数据存不变。
// * 依据：本席隔离微基准（`work/b1v_mb1.cpp`：middle 1.29 MB / columns 2 MB / count 1 KB 全部 L1-L2 驻留、
// 7 轮取 min）**2.116 → 1.956 cycle/元素（−7.6%）**；同一台架里"目的地址换成 64 B 哑缓冲" = 1.221、
// "删掉游标 store" = 1.511 ⇒ 该环的楼板 ~1.2，本刀取回其中约 1/5。
// * 稳定性（LSD 基数排序的必需前提）：同一次 load 的 4 个元素按**低到高**处理，与逐元素版
// 逐位同序 ⇒ 桶内写入顺序逐位不变 ⇒ 输出逐位不变（仍按纪律在生产 n 跑逐元素闸门）。
// 提交目的 = **定价 + 兑现**（缺口 0.809895 ms）。判据 = 与 `#106866`（455.971702 ms）单变量比。
// ★ 声明：只改取数/取字节的形态，不改布局/算法/数据流；失败只关掉这一条路。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106861 <https://duck.ac/submission/106861>
// 用途：**本文件正文 = #106861 的完整源码**（本地副本 `work/b1v_m32.cpp`），只改 `sort_leaf`
// 慢列（`count[h] ∈ [17,32]`）的输出发射形态（见思路段）。#106861 之前的本账号上游链一并列出：
// 1.1 <https://duck.ac/submission/106840> 本账号 —— byte2 散列趟分块 + 6 条 `__builtin_prefetch(r+512..832)`。
// 1.2 <https://duck.ac/submission/106285> 本账号 —— BSS pad 2752 + `capacity` 末尾 `+BS`。
// 1.3 <https://duck.ac/submission/106201> 本账号 —— 其直接上游（s2_ 的 SIMD 网络件）。
// 1.4 <https://duck.ac/submission/101817> duck.ac 用户 codex_astra —— `partition`/`sort_leaf`/
// 16 输入网络来源。
// 1.5 <https://duck.ac/submission/105161> 本账号（1001，n=1e8，已达标）—— [PFSRC6] 预取参数与
// [MSET32] 哨兵填充写法的**直接复制**来源。
// 1.6 <https://duck.ac/problem/1001b> 题目页（sort 2^27 个 u32，单测试点）。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 #106183 <https://duck.ac/submission/106183>
// 用途：**直接复制**其 `sort_leaf` 慢列的向量化发射片段（`vlo/vhi` 拆分 + 3~4 条
// `vpmovzxbd`+`vpor`+`vmovdqu`，以及 `end-dst >= (c<=24?24:32)` 的边界守卫与标量回退）。
// 该用户的文件自述其上游为本账号 #104352、#106150、#106157（本账号的 AVX2 网络/四向量发射）。
// 2.1 K. E. Batcher, "Sorting Networks and Their Applications" (1968)
// <https://doi.org/10.1145/1468075.1468121> —— 仅用于确认本件沿用的 32 字节网络是合法排序网络
// （未改动其比较器序列）。
// [3] Intel 64 与 IA-32 架构软件开发手册 <https://www.intel.com/sdm>
// 用途：确认 `PREFETCHh` 不触发异常、`vmovdqa`/`vpmovzxbd`/`vpsrldq`/`vmovdqu` 的语义与写边界。
// ======================
// ===== 思路 =====
// **单变量（一处）：`sort_leaf` 慢列（`count[h]` ∈ [17,32]）的发射由"逐元素标量存"改成向量化发射。**
// * 原形态：`sort32_byte` 的结果先 `vmovdqu` 存回 `copy[32]`，再
// `for(j=0;j<c;++j) dst[j]=base|(h<<8)|copy[j]` ⇒ 每列约 2 条向量 op + **c 条标量 load + c 条标量 store**
// （c≈19 ⇒ ~40 条内存操作/列）。
// * 本形态（引用 [2] 的片段）：`sorted` 留在寄存器里，`vpmovzxbd` 一次把 8 个字节扩成 8×u32、
// `vpor` 上前缀、`vmovdqu` 32B 存出 ⇒ **每列 3~4 条（8 值/条）**，且省掉"存回 copy 再逐元素读"。
// 守卫 `end-dst >= (c<=24?24:32)` 保证靠近数组末尾时退回标量路径（不越界写）。
// * 定价依据：该慢列路径在本题 **58662 次/场**（我方件内注释的实测计数）；原形态 ~100 uops/次、
// 新形态 ~16 uops/次 ⇒ 省 ≈4.9M uops ≈ 1.25 Mcyc ≈ **0.35 ms 量级**（缺口为 0.869063 ms）。
// * 输出逐位不变：两条路径写入的 `dst[0..c-1]` 完全相同（`sorted` 的前 c 个字节 = 该列升序前 c 个）；
// 向量路径多写的 (24-c) 个位置被同一 `dst += c` 推进的下一个桶覆盖，数组末尾由守卫排除 ✓
// ⇒ 仍按纪律在生产 n（2^27）跑逐元素闸门。
// 提交目的 = **定价 + 兑现**。判据 = 与 `#106861`（456.030870 ms）单变量比。
// ★ 声明：只改慢列的发射指令形态；失败只关掉这一条路。
// ================
/* Idea: Allocate the existing16-wire sorting network explicitly.
* Keep fifteen wires in vector registers and only wire15 in one32-byte spill.
* Each ordinary comparison uses the free register for min and reuses its
* second input for max, then recycles the first register. Comparisons with
* wire15 use memory operands and one spill store. Retire the lower8 outputs
* before loading the last wire for upper8 transposition. Every comparator,
* transpose lane and output byte stays identical. Purpose: remove redundant
* compiler-generated spills and reloads in the64M-column sorting stage.
*/
#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing")
#pragma GCC optimize("web")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("align-functions=128")
#pragma GCC optimize("no-tree-pre")
#pragma GCC optimize("no-tree-dce")
#pragma GCC optimize("no-tree-dominator-opts")
#pragma GCC target("avx2,bmi,bmi2,popcnt")
#include <immintrin.h>
#include <algorithm>
#include <cstring>
#include <cstdint>
#include <utility>
#include <unistd.h>
#if defined(__APPLE__)
#define syscall(...) ((long)-1)
#endif
#ifndef BUFFER_BITS
#define BUFFER_BITS 6
#endif
#ifndef TOP_BITS
#define TOP_BITS 8
#endif
#ifndef UNROLL
#define UNROLL 1
#endif
static constexpr unsigned TB=TOP_BITS, K=1u<<TB, BS=1u<<BUFFER_BITS;
static constexpr unsigned NPORT = 134217728u;
alignas(64) static unsigned char workspace[3u*(256u*557056u + 256u*64u) + 4096u + 16u];
alignas(256) static unsigned char staging_bytes[K*192];
static unsigned short byte_cursor[K];
alignas(64) static unsigned hist[K], starts[K], pos[K];
static inline unsigned read24(const unsigned char *s){unsigned x;memcpy(&x,s,4);return x&0xffffff;}
static void small_original(unsigned char*s,unsigned*d,unsigned n,unsigned prefix,unsigned*){
for(unsigned i=0;i<n;++i)d[i]=prefix|read24(s+3*i);
std::sort(d,d+n);
}
#define SM7_PAD (2752u)
static_assert(SM7_PAD == 2752u, "sm7_pad config echo");
alignas(64) static unsigned char sm7_pad[SM7_PAD] __attribute__((used));
static_assert(sizeof(sm7_pad) == SM7_PAD, "sm7_pad size echo");
alignas(2'097'152) static uint16_t middle[1<<21];
namespace fastsort {
constexpr unsigned kRadix=256;
constexpr unsigned kLeafLimit = 8192;
using U32 = unsigned; using Byte = uint8_t; using U16 = uint16_t; using U64 = uint64_t;
using Vec256 = __m256i; using Vec128 = __m128i;
template <class T> inline T load(const void *src) { T value; std::memcpy(&value, src, sizeof value); return value; }
template <class F, size_t... I> [[gnu::always_inline]] inline void each(F &&f, std::index_sequence<I...>) {
(f(std::integral_constant<size_t, I>{}), ...);
}
template <size_t N, class F> [[gnu::always_inline]] inline void repeat(F &&f) {
each(std::forward<F>(f), std::make_index_sequence<N>{});
}
}
// ===== s2_: SIMD 32-byte sorting network (see s2_mknet.py) =====
namespace s2_net {
alignas(32) static const unsigned char shuf[4][32] = {
{1,0,3,2,5,4,7,6,9,8,11,10,13,12,15,14,1,0,3,2,5,4,7,6,9,8,11,10,13,12,15,14},
{2,3,0,1,6,7,4,5,10,11,8,9,14,15,12,13,2,3,0,1,6,7,4,5,10,11,8,9,14,15,12,13},
{4,5,6,7,0,1,2,3,12,13,14,15,8,9,10,11,4,5,6,7,0,1,2,3,12,13,14,15,8,9,10,11},
{8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7},
};
alignas(32) static const signed char choose_min[15][32] = {
{-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1},
{-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1},
{-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1},
{-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1},
{-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1,-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1},
{-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1,-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1},
{-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1},
{-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
{-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0},
{-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0},
{-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0},
{-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0},
};
static inline __m256i sort32_byte(__m256i v){
__m256i p0=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
__m256i lo0=_mm256_min_epu8(v,p0),hi0=_mm256_max_epu8(v,p0);
v=_mm256_blendv_epi8(hi0,lo0,_mm256_load_si256((const __m256i*)choose_min[0]));
__m256i p1=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
__m256i lo1=_mm256_min_epu8(v,p1),hi1=_mm256_max_epu8(v,p1);
v=_mm256_blendv_epi8(hi1,lo1,_mm256_load_si256((const __m256i*)choose_min[1]));
__m256i p2=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
__m256i lo2=_mm256_min_epu8(v,p2),hi2=_mm256_max_epu8(v,p2);
v=_mm256_blendv_epi8(hi2,lo2,_mm256_load_si256((const __m256i*)choose_min[2]));
__m256i p3=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
__m256i lo3=_mm256_min_epu8(v,p3),hi3=_mm256_max_epu8(v,p3);
v=_mm256_blendv_epi8(hi3,lo3,_mm256_load_si256((const __m256i*)choose_min[3]));
__m256i p4=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
__m256i lo4=_mm256_min_epu8(v,p4),hi4=_mm256_max_epu8(v,p4);
v=_mm256_blendv_epi8(hi4,lo4,_mm256_load_si256((const __m256i*)choose_min[4]));
__m256i p5=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
__m256i lo5=_mm256_min_epu8(v,p5),hi5=_mm256_max_epu8(v,p5);
v=_mm256_blendv_epi8(hi5,lo5,_mm256_load_si256((const __m256i*)choose_min[5]));
__m256i p6=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[3]));
__m256i lo6=_mm256_min_epu8(v,p6),hi6=_mm256_max_epu8(v,p6);
v=_mm256_blendv_epi8(hi6,lo6,_mm256_load_si256((const __m256i*)choose_min[6]));
__m256i p7=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
__m256i lo7=_mm256_min_epu8(v,p7),hi7=_mm256_max_epu8(v,p7);
v=_mm256_blendv_epi8(hi7,lo7,_mm256_load_si256((const __m256i*)choose_min[7]));
__m256i p8=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
__m256i lo8=_mm256_min_epu8(v,p8),hi8=_mm256_max_epu8(v,p8);
v=_mm256_blendv_epi8(hi8,lo8,_mm256_load_si256((const __m256i*)choose_min[8]));
__m256i p9=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
__m256i lo9=_mm256_min_epu8(v,p9),hi9=_mm256_max_epu8(v,p9);
v=_mm256_blendv_epi8(hi9,lo9,_mm256_load_si256((const __m256i*)choose_min[9]));
__m256i p10=_mm256_permute2x128_si256(v,v,0x01);
__m256i lo10=_mm256_min_epu8(v,p10),hi10=_mm256_max_epu8(v,p10);
v=_mm256_blendv_epi8(hi10,lo10,_mm256_load_si256((const __m256i*)choose_min[10]));
__m256i p11=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[3]));
__m256i lo11=_mm256_min_epu8(v,p11),hi11=_mm256_max_epu8(v,p11);
v=_mm256_blendv_epi8(hi11,lo11,_mm256_load_si256((const __m256i*)choose_min[11]));
__m256i p12=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
__m256i lo12=_mm256_min_epu8(v,p12),hi12=_mm256_max_epu8(v,p12);
v=_mm256_blendv_epi8(hi12,lo12,_mm256_load_si256((const __m256i*)choose_min[12]));
__m256i p13=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
__m256i lo13=_mm256_min_epu8(v,p13),hi13=_mm256_max_epu8(v,p13);
v=_mm256_blendv_epi8(hi13,lo13,_mm256_load_si256((const __m256i*)choose_min[13]));
__m256i p14=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
__m256i lo14=_mm256_min_epu8(v,p14),hi14=_mm256_max_epu8(v,p14);
v=_mm256_blendv_epi8(hi14,lo14,_mm256_load_si256((const __m256i*)choose_min[14]));
return v;
}
static inline __m256i merge32_byte(__m256i v){
__m256i p10=_mm256_permute2x128_si256(v,v,0x01);
__m256i lo10=_mm256_min_epu8(v,p10),hi10=_mm256_max_epu8(v,p10);
v=_mm256_blendv_epi8(hi10,lo10,_mm256_load_si256((const __m256i*)choose_min[10]));
__m256i p11=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[3]));
__m256i lo11=_mm256_min_epu8(v,p11),hi11=_mm256_max_epu8(v,p11);
v=_mm256_blendv_epi8(hi11,lo11,_mm256_load_si256((const __m256i*)choose_min[11]));
__m256i p12=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
__m256i lo12=_mm256_min_epu8(v,p12),hi12=_mm256_max_epu8(v,p12);
v=_mm256_blendv_epi8(hi12,lo12,_mm256_load_si256((const __m256i*)choose_min[12]));
__m256i p13=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
__m256i lo13=_mm256_min_epu8(v,p13),hi13=_mm256_max_epu8(v,p13);
v=_mm256_blendv_epi8(hi13,lo13,_mm256_load_si256((const __m256i*)choose_min[13]));
__m256i p14=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
__m256i lo14=_mm256_min_epu8(v,p14),hi14=_mm256_max_epu8(v,p14);
v=_mm256_blendv_epi8(hi14,lo14,_mm256_load_si256((const __m256i*)choose_min[14]));
return v;
}
}
using s2_net::sort32_byte;
using s2_net::merge32_byte;
namespace byte_sort {
using namespace fastsort;
[[gnu::noinline]] inline void counting_sort(const U16 *src, U32 n, U32 *dst, U32 base) {
alignas(64) U32 counts[65536] = {};
for (U32 i = 0; i < n; ++i) ++counts[load<U16>(src + i)];
for (U32 v = 0; v < 65536; ++v)
for (U32 c = counts[v]; c; --c) *dst++ = base | v;
}
[[gnu::noinline]] inline void uniform_high_sort(const U16 *src,U32 n,U32 *dst,U32 prefix){
alignas(32) U32 low[256]={};
#pragma GCC unroll 8
for(U32 i=0;i<n;++i)++low[load<U16>(src+i)&255u];
prefix|=load<U16>(src)&0xff00u;
for(U32 digit=0;digit<256;++digit){
const U32 count=low[digit];std::fill_n(dst,count,prefix|digit);dst+=count;
}
}
[[gnu::always_inline]] inline void transpose8(const Vec256 *x, Byte *out) {
Vec256 a[8], b[8];
#pragma GCC unroll 4
for (U32 i = 0; i < 4; ++i) {
a[2 * i] = _mm256_unpacklo_epi8(x[2 * i], x[2 * i + 1]);
a[2 * i + 1] = _mm256_unpackhi_epi8(x[2 * i], x[2 * i + 1]);
}
#pragma GCC unroll 2
for (U32 i = 0; i < 2; ++i) {
#pragma GCC unroll 2
for (U32 j = 0; j < 2; ++j) {
b[4 * i + 2 * j] = _mm256_unpacklo_epi16(a[4 * i + j], a[4 * i + j + 2]);
b[4 * i + 2 * j + 1] = _mm256_unpackhi_epi16(a[4 * i + j], a[4 * i + j + 2]);
}
}
#pragma GCC unroll 4
for (U32 i = 0; i < 4; ++i) {
Vec256 lo = _mm256_unpacklo_epi32(b[i], b[i + 4]);
Vec256 hi = _mm256_unpackhi_epi32(b[i], b[i + 4]);
_mm256_store_si256((Vec256 *)(out + 64 * i), lo);
_mm256_store_si256((Vec256 *)(out + 64 * i + 32), hi);
}
}
[[gnu::always_inline]] inline void sort16_columns(const Byte *src, Byte *out, Byte *out2) {
Vec256 spill;
__asm__ volatile(
"vmovdqa 0(%[src]), %%ymm0\n\t"
"vmovdqa 256(%[src]), %%ymm1\n\t"
"vmovdqa 512(%[src]), %%ymm2\n\t"
"vmovdqa 768(%[src]), %%ymm3\n\t"
"vmovdqa 1024(%[src]), %%ymm4\n\t"
"vmovdqa 1280(%[src]), %%ymm5\n\t"
"vmovdqa 1536(%[src]), %%ymm6\n\t"
"vmovdqa 1792(%[src]), %%ymm7\n\t"
"vmovdqa 2048(%[src]), %%ymm8\n\t"
"vmovdqa 2304(%[src]), %%ymm9\n\t"
"vmovdqa 2560(%[src]), %%ymm10\n\t"
"vmovdqa 2816(%[src]), %%ymm11\n\t"
"vmovdqa 3072(%[src]), %%ymm12\n\t"
"vmovdqa 3328(%[src]), %%ymm13\n\t"
"vmovdqa 3584(%[src]), %%ymm14\n\t"
"vpminub %%ymm13, %%ymm0, %%ymm15\n\t"
"vpmaxub %%ymm13, %%ymm0, %%ymm13\n\t"
"vpminub %%ymm12, %%ymm1, %%ymm0\n\t"
"vpmaxub %%ymm12, %%ymm1, %%ymm12\n\t"
"vpminub 3840(%[src]), %%ymm2, %%ymm1\n\t"
"vpmaxub 3840(%[src]), %%ymm2, %%ymm2\n\t"
"vmovdqa %%ymm2, %[spill]\n\t"
"vpcmpeqb %%ymm2, %%ymm2, %%ymm2\n\t"
"vmovdqa %%ymm2, 0(%[src])\n\t"
"vmovdqa %%ymm2, 256(%[src])\n\t"
"vmovdqa %%ymm2, 512(%[src])\n\t"
"vmovdqa %%ymm2, 768(%[src])\n\t"
"vmovdqa %%ymm2, 1024(%[src])\n\t"
"vmovdqa %%ymm2, 1280(%[src])\n\t"
"vmovdqa %%ymm2, 1536(%[src])\n\t"
"vmovdqa %%ymm2, 1792(%[src])\n\t"
"vmovdqa %%ymm2, 2048(%[src])\n\t"
"vmovdqa %%ymm2, 2304(%[src])\n\t"
"vmovdqa %%ymm2, 2560(%[src])\n\t"
"vmovdqa %%ymm2, 2816(%[src])\n\t"
"vmovdqa %%ymm2, 3072(%[src])\n\t"
"vmovdqa %%ymm2, 3328(%[src])\n\t"
"vmovdqa %%ymm2, 3584(%[src])\n\t"
"vmovdqa %%ymm2, 3840(%[src])\n\t"
"vpminub %%ymm14, %%ymm3, %%ymm2\n\t"
"vpmaxub %%ymm14, %%ymm3, %%ymm14\n\t"
"vpminub %%ymm8, %%ymm4, %%ymm3\n\t"
"vpmaxub %%ymm8, %%ymm4, %%ymm8\n\t"
"vpminub %%ymm6, %%ymm5, %%ymm4\n\t"
"vpmaxub %%ymm6, %%ymm5, %%ymm6\n\t"
"vpminub %%ymm11, %%ymm7, %%ymm5\n\t"
"vpmaxub %%ymm11, %%ymm7, %%ymm11\n\t"
"vpminub %%ymm10, %%ymm9, %%ymm7\n\t"
"vpmaxub %%ymm10, %%ymm9, %%ymm10\n\t"
"vpminub %%ymm4, %%ymm15, %%ymm9\n\t"
"vpmaxub %%ymm4, %%ymm15, %%ymm4\n\t"
"vpminub %%ymm5, %%ymm0, %%ymm15\n\t"
"vpmaxub %%ymm5, %%ymm0, %%ymm5\n\t"
"vpminub %%ymm7, %%ymm1, %%ymm0\n\t"
"vpmaxub %%ymm7, %%ymm1, %%ymm7\n\t"
"vpminub %%ymm3, %%ymm2, %%ymm1\n\t"
"vpmaxub %%ymm3, %%ymm2, %%ymm3\n\t"
"vpminub %%ymm13, %%ymm6, %%ymm2\n\t"
"vpmaxub %%ymm13, %%ymm6, %%ymm13\n\t"
"vpminub %%ymm14, %%ymm8, %%ymm6\n\t"
"vpmaxub %%ymm14, %%ymm8, %%ymm14\n\t"
"vpminub %[spill], %%ymm10, %%ymm8\n\t"
"vpmaxub %[spill], %%ymm10, %%ymm10\n\t"
"vmovdqa %%ymm10, %[spill]\n\t"
"vpminub %%ymm12, %%ymm11, %%ymm10\n\t"
"vpmaxub %%ymm12, %%ymm11, %%ymm12\n\t"
"vpminub %%ymm15, %%ymm9, %%ymm11\n\t"
"vpmaxub %%ymm15, %%ymm9, %%ymm15\n\t"
"vpminub %%ymm1, %%ymm0, %%ymm9\n\t"
"vpmaxub %%ymm1, %%ymm0, %%ymm1\n\t"
"vpminub %%ymm4, %%ymm3, %%ymm0\n\t"
"vpmaxub %%ymm4, %%ymm3, %%ymm4\n\t"
"vpminub %%ymm6, %%ymm2, %%ymm3\n\t"
"vpmaxub %%ymm6, %%ymm2, %%ymm6\n\t"
"vpminub %%ymm7, %%ymm5, %%ymm2\n\t"
"vpmaxub %%ymm7, %%ymm5, %%ymm7\n\t"
"vpminub %%ymm10, %%ymm8, %%ymm5\n\t"
"vpmaxub %%ymm10, %%ymm8, %%ymm10\n\t"
"vpminub %%ymm13, %%ymm12, %%ymm8\n\t"
"vpmaxub %%ymm13, %%ymm12, %%ymm13\n\t"
"vpminub %[spill], %%ymm14, %%ymm12\n\t"
"vpmaxub %[spill], %%ymm14, %%ymm14\n\t"
"vmovdqa %%ymm14, %[spill]\n\t"
"vpminub %%ymm9, %%ymm11, %%ymm14\n\t"
"vpmaxub %%ymm9, %%ymm11, %%ymm9\n\t"
"vpminub %%ymm1, %%ymm15, %%ymm11\n\t"
"vpmaxub %%ymm1, %%ymm15, %%ymm1\n\t"
"vpminub %%ymm5, %%ymm0, %%ymm15\n\t"
"vpmaxub %%ymm5, %%ymm0, %%ymm5\n\t"
"vpminub %%ymm10, %%ymm4, %%ymm0\n\t"
"vpmaxub %%ymm10, %%ymm4, %%ymm10\n\t"
"vpminub %%ymm2, %%ymm3, %%ymm4\n\t"
"vpmaxub %%ymm2, %%ymm3, %%ymm2\n\t"
"vpminub %%ymm7, %%ymm6, %%ymm3\n\t"
"vpmaxub %%ymm7, %%ymm6, %%ymm7\n\t"
"vpminub %%ymm12, %%ymm8, %%ymm6\n\t"
"vpmaxub %%ymm12, %%ymm8, %%ymm12\n\t"
"vpminub %[spill], %%ymm13, %%ymm8\n\t"
"vpmaxub %[spill], %%ymm13, %%ymm13\n\t"
"vmovdqa %%ymm13, %[spill]\n\t"
"vpminub %%ymm9, %%ymm11, %%ymm13\n\t"
"vpmaxub %%ymm9, %%ymm11, %%ymm9\n\t"
"vpminub %%ymm6, %%ymm1, %%ymm11\n\t"
"vpmaxub %%ymm6, %%ymm1, %%ymm6\n\t"
"vpminub %%ymm4, %%ymm15, %%ymm1\n\t"
"vpmaxub %%ymm4, %%ymm15, %%ymm4\n\t"
"vpminub %%ymm2, %%ymm0, %%ymm15\n\t"
"vpmaxub %%ymm2, %%ymm0, %%ymm2\n\t"
"vpminub %%ymm5, %%ymm3, %%ymm0\n\t"
"vpmaxub %%ymm5, %%ymm3, %%ymm5\n\t"
"vpminub %%ymm10, %%ymm7, %%ymm3\n\t"
"vpmaxub %%ymm10, %%ymm7, %%ymm10\n\t"
"vpminub %%ymm12, %%ymm8, %%ymm7\n\t"
"vpmaxub %%ymm12, %%ymm8, %%ymm12\n\t"
"vpminub %%ymm1, %%ymm13, %%ymm8\n\t"
"vpmaxub %%ymm1, %%ymm13, %%ymm1\n\t"
"vpminub %%ymm4, %%ymm9, %%ymm13\n\t"
"vpmaxub %%ymm4, %%ymm9, %%ymm4\n\t"
"vpminub %%ymm0, %%ymm15, %%ymm9\n\t"
"vpmaxub %%ymm0, %%ymm15, %%ymm0\n\t"
"vpminub %%ymm5, %%ymm2, %%ymm15\n\t"
"vpmaxub %%ymm5, %%ymm2, %%ymm5\n\t"
"vpminub %%ymm7, %%ymm3, %%ymm2\n\t"
"vpmaxub %%ymm7, %%ymm3, %%ymm7\n\t"
"vpminub %%ymm12, %%ymm10, %%ymm3\n\t"
"vpmaxub %%ymm12, %%ymm10, %%ymm12\n\t"
"vpminub %%ymm1, %%ymm13, %%ymm10\n\t"
"vpmaxub %%ymm1, %%ymm13, %%ymm1\n\t"
"vpminub %%ymm4, %%ymm11, %%ymm13\n\t"
"vpmaxub %%ymm4, %%ymm11, %%ymm4\n\t"
"vpminub %%ymm6, %%ymm2, %%ymm11\n\t"
"vpmaxub %%ymm6, %%ymm2, %%ymm6\n\t"
"vpminub %%ymm7, %%ymm3, %%ymm2\n\t"
"vpmaxub %%ymm7, %%ymm3, %%ymm7\n\t"
"vpminub %%ymm9, %%ymm13, %%ymm3\n\t"
"vpmaxub %%ymm9, %%ymm13, %%ymm9\n\t"
"vpminub %%ymm0, %%ymm4, %%ymm13\n\t"
"vpmaxub %%ymm0, %%ymm4, %%ymm0\n\t"
"vpminub %%ymm11, %%ymm15, %%ymm4\n\t"
"vpmaxub %%ymm11, %%ymm15, %%ymm11\n\t"
"vpminub %%ymm6, %%ymm5, %%ymm15\n\t"
"vpmaxub %%ymm6, %%ymm5, %%ymm6\n\t"
"vpminub %%ymm1, %%ymm3, %%ymm5\n\t"
"vpmaxub %%ymm1, %%ymm3, %%ymm1\n\t"
"vpminub %%ymm13, %%ymm9, %%ymm3\n\t"
"vpmaxub %%ymm13, %%ymm9, %%ymm13\n\t"
"vpminub %%ymm0, %%ymm4, %%ymm9\n\t"
"vpmaxub %%ymm0, %%ymm4, %%ymm0\n\t"
"vpminub %%ymm15, %%ymm11, %%ymm4\n\t"
"vpmaxub %%ymm15, %%ymm11, %%ymm15\n\t"
"vpminub %%ymm6, %%ymm2, %%ymm11\n\t"
"vpmaxub %%ymm6, %%ymm2, %%ymm6\n\t"
"vpminub %%ymm9, %%ymm13, %%ymm2\n\t"
"vpmaxub %%ymm9, %%ymm13, %%ymm9\n\t"
"vpminub %%ymm4, %%ymm0, %%ymm13\n\t"
"vpmaxub %%ymm4, %%ymm0, %%ymm4\n\t"
"vpunpcklbw %%ymm8, %%ymm14, %%ymm0\n\t"
"vpunpckhbw %%ymm8, %%ymm14, %%ymm8\n\t"
"vpunpcklbw %%ymm5, %%ymm10, %%ymm14\n\t"
"vpunpckhbw %%ymm5, %%ymm10, %%ymm5\n\t"
"vpunpcklbw %%ymm3, %%ymm1, %%ymm10\n\t"
"vpunpckhbw %%ymm3, %%ymm1, %%ymm3\n\t"
"vpunpcklbw %%ymm9, %%ymm2, %%ymm1\n\t"
"vpunpckhbw %%ymm9, %%ymm2, %%ymm9\n\t"
"vpunpcklwd %%ymm14, %%ymm0, %%ymm2\n\t"
"vpunpckhwd %%ymm14, %%ymm0, %%ymm14\n\t"
"vpunpcklwd %%ymm5, %%ymm8, %%ymm0\n\t"
"vpunpckhwd %%ymm5, %%ymm8, %%ymm5\n\t"
"vpunpcklwd %%ymm1, %%ymm10, %%ymm8\n\t"
"vpunpckhwd %%ymm1, %%ymm10, %%ymm1\n\t"
"vpunpcklwd %%ymm9, %%ymm3, %%ymm10\n\t"
"vpunpckhwd %%ymm9, %%ymm3, %%ymm9\n\t"
"vpunpckldq %%ymm8, %%ymm2, %%ymm3\n\t"
"vpunpckhdq %%ymm8, %%ymm2, %%ymm8\n\t"
"vmovdqa %%ymm3, 0(%[out])\n\t"
"vmovdqa %%ymm8, 32(%[out])\n\t"
"vpunpckldq %%ymm1, %%ymm14, %%ymm2\n\t"
"vpunpckhdq %%ymm1, %%ymm14, %%ymm1\n\t"
"vmovdqa %%ymm2, 64(%[out])\n\t"
"vmovdqa %%ymm1, 96(%[out])\n\t"
"vpunpckldq %%ymm10, %%ymm0, %%ymm14\n\t"
"vpunpckhdq %%ymm10, %%ymm0, %%ymm10\n\t"
"vmovdqa %%ymm14, 128(%[out])\n\t"
"vmovdqa %%ymm10, 160(%[out])\n\t"
"vpunpckldq %%ymm9, %%ymm5, %%ymm0\n\t"
"vpunpckhdq %%ymm9, %%ymm5, %%ymm9\n\t"
"vmovdqa %%ymm0, 192(%[out])\n\t"
"vmovdqa %%ymm9, 224(%[out])\n\t"
"vmovdqa %[spill], %%ymm0\n\t"
"vpunpcklbw %%ymm4, %%ymm13, %%ymm5\n\t"
"vpunpckhbw %%ymm4, %%ymm13, %%ymm4\n\t"
"vpunpcklbw %%ymm11, %%ymm15, %%ymm13\n\t"
"vpunpckhbw %%ymm11, %%ymm15, %%ymm11\n\t"
"vpunpcklbw %%ymm7, %%ymm6, %%ymm15\n\t"
"vpunpckhbw %%ymm7, %%ymm6, %%ymm7\n\t"
"vpunpcklbw %%ymm0, %%ymm12, %%ymm6\n\t"
"vpunpckhbw %%ymm0, %%ymm12, %%ymm0\n\t"
"vpunpcklwd %%ymm13, %%ymm5, %%ymm12\n\t"
"vpunpckhwd %%ymm13, %%ymm5, %%ymm13\n\t"
"vpunpcklwd %%ymm11, %%ymm4, %%ymm5\n\t"
"vpunpckhwd %%ymm11, %%ymm4, %%ymm11\n\t"
"vpunpcklwd %%ymm6, %%ymm15, %%ymm4\n\t"
"vpunpckhwd %%ymm6, %%ymm15, %%ymm6\n\t"
"vpunpcklwd %%ymm0, %%ymm7, %%ymm15\n\t"
"vpunpckhwd %%ymm0, %%ymm7, %%ymm0\n\t"
"vpunpckldq %%ymm4, %%ymm12, %%ymm7\n\t"
"vpunpckhdq %%ymm4, %%ymm12, %%ymm4\n\t"
"vmovdqa %%ymm7, 0(%[out2])\n\t"
"vmovdqa %%ymm4, 32(%[out2])\n\t"
"vpunpckldq %%ymm6, %%ymm13, %%ymm12\n\t"
"vpunpckhdq %%ymm6, %%ymm13, %%ymm6\n\t"
"vmovdqa %%ymm12, 64(%[out2])\n\t"
"vmovdqa %%ymm6, 96(%[out2])\n\t"
"vpunpckldq %%ymm15, %%ymm5, %%ymm13\n\t"
"vpunpckhdq %%ymm15, %%ymm5, %%ymm15\n\t"
"vmovdqa %%ymm13, 128(%[out2])\n\t"
"vmovdqa %%ymm15, 160(%[out2])\n\t"
"vpunpckldq %%ymm0, %%ymm11, %%ymm5\n\t"
"vpunpckhdq %%ymm0, %%ymm11, %%ymm0\n\t"
"vmovdqa %%ymm5, 192(%[out2])\n\t"
"vmovdqa %%ymm0, 224(%[out2])\n\t"
: [spill] "=m"(spill)
: [src] "r"(src), [out] "r"(out), [out2] "r"(out2)
: "ymm0", "ymm1", "ymm2", "ymm3", "ymm4", "ymm5", "ymm6", "ymm7", "ymm8", "ymm9", "ymm10", "ymm11", "ymm12", "ymm13", "ymm14", "ymm15", "memory");
}
[[gnu::always_inline]] inline void sort14_columns(const Byte*src,Byte*out,Byte*out2){
Vec256 v[14];
repeat<14>([&](auto j) __attribute__((always_inline)){v[j]=_mm256_load_si256((const Vec256*)(src+256*j));});
#define CMP14(A,B) {Vec256 lo=_mm256_min_epu8(v[A],v[B]);v[B]=_mm256_max_epu8(v[A],v[B]);v[A]=lo;}
CMP14(0,13)
CMP14(1,12)
CMP14(4,8)
CMP14(5,6)
CMP14(7,11)
CMP14(9,10)
CMP14(0,5)
CMP14(1,7)
CMP14(2,9)
CMP14(3,4)
CMP14(6,13)
CMP14(11,12)
CMP14(0,1)
CMP14(2,3)
CMP14(4,5)
CMP14(6,8)
CMP14(7,9)
CMP14(10,11)
CMP14(12,13)
CMP14(0,2)
CMP14(1,3)
CMP14(4,10)
CMP14(5,11)
CMP14(6,7)
CMP14(8,9)
CMP14(1,2)
CMP14(3,12)
CMP14(4,6)
CMP14(5,7)
CMP14(8,10)
CMP14(9,11)
CMP14(1,4)
CMP14(2,6)
CMP14(5,8)
CMP14(7,10)
CMP14(9,13)
CMP14(2,4)
CMP14(3,6)
CMP14(9,12)
CMP14(11,13)
CMP14(3,5)
CMP14(6,8)
CMP14(7,9)
CMP14(10,12)
CMP14(3,4)
CMP14(5,6)
CMP14(7,8)
CMP14(9,10)
CMP14(11,12)
CMP14(6,7)
CMP14(8,9)
#undef CMP14
Vec256 x[16]={v[0],v[1],v[2],v[3],v[4],v[5],v[6],v[7],v[8],v[9],v[10],v[11],v[12],v[13],_mm256_set1_epi8(-1),_mm256_set1_epi8(-1)};
transpose8(x,out);transpose8(x+8,out2);
}
[[gnu::always_inline]] inline U32 restore_counts(U32 *count, U32 *exceptional) {
U32 *end = count + 256; U32 over;
const Vec256 limit16 = _mm256_set1_epi32(16), limit32 = _mm256_set1_epi32(32);
__asm__ volatile("vpxor %%ymm4, %%ymm4, %%ymm4\n\t"
".p2align 4\n\t1:\n\t"
".irp reg,0,1,2,3; vmovdqa 32*\\reg(%[count]), %%ymm\\reg; .endr\n\t"
".irp reg,0,1,2,3; vpsrld $8, %%ymm\\reg, %%ymm\\reg; .endr\n\t"
".irp reg,0,1,2,3; vmovdqa %%ymm\\reg, 32*\\reg(%[count]); .endr\n\t"
"vpmaxud %%ymm1, %%ymm0, %%ymm0; vpmaxud %%ymm3, %%ymm2, %%ymm2\n\t"
"vpmaxud %%ymm2, %%ymm0, %%ymm0\n\t"
"vpcmpgtd %[limit16], %%ymm0, %%ymm1\n\t"
"vmovmskps %%ymm1, %%eax\n\t"
"movl %%eax, (%[flags])\n\t"
"vpmaxud %%ymm0, %%ymm4, %%ymm4\n\t"
"addq $128, %[count]; addq $4, %[flags]\n\t"
"cmpq %[end], %[count]; jb 1b\n\t"
"vpcmpgtd %[limit32], %%ymm4, %%ymm0; vmovmskps %%ymm0, %k[over]\n\t"
: [count] "+&r"(count), [flags] "+&r"(exceptional), [over] "=&r"(over)
: [end] "r"(end), [limit16] "x"(limit16), [limit32] "x"(limit32)
: "rax", "ymm0", "ymm1", "ymm2", "ymm3", "ymm4", "cc", "memory");
return over;
}
[[gnu::always_inline]] inline U32 *emit32_buckets16(const Byte *first, const Byte *second, const U32 *count,
U32 *dst, Vec256 &prefix) {
const Vec256 step = _mm256_set1_epi32(256); const U32 *end = count + 32;
__asm__ volatile(".p2align 4\n\t1:\n\t"
".irp lane,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\n\t"
"movl 4*\\lane(%[count]), %%eax\n\t"
"vpmovzxbd (32*(\\lane/2)+8*(\\lane&1))(%[first]), %%ymm1; vpmovzxbd (32*(\\lane/2)+8*(\\lane&1))(%[second]), %%ymm2\n\t"
"vpor %[prefix], %%ymm1, %%ymm1; vpor %[prefix], %%ymm2, %%ymm2\n\t"
"vmovdqu %%ymm1, (%[dst]); vmovdqu %%ymm2, 32(%[dst])\n\t"
"leaq (%[dst],%%rax,4), %[dst]\n\t"
"vpaddd %[step], %[prefix], %[prefix]\n\t"
".endr\n\t"
"addq $16, %[first]; addq $16, %[second]; addq $64, %[count]\n\t"
"cmpq %[end], %[count]; jb 1b\n\t"
: [dst] "+&r"(dst), [prefix] "+&x"(prefix), [count] "+&r"(count), [first] "+&r"(first),
[second] "+&r"(second)
: [end] "r"(end), [step] "x"(step)
: "rax", "ymm1", "ymm2", "cc", "memory");
return dst;
}
inline unsigned native_column_offset(unsigned i) {return 32*((i>>1)&7)+8*(i&1)+16*(i>>4);}
[[gnu::noinline]] static U32 *emit_group_c(U32 *dst, const Byte *first, const Byte *second,
const U32 *count, const Byte *columns, U32 block, U32 base, Vec256 prefix, const U32 *end) {
const Vec256 idx = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
const Vec256 step = _mm256_set1_epi32(256);
const U32 *cnt = count + block;
if (__builtin_expect(end - dst >= 1024, 1)) {
#pragma GCC unroll 8
for (U32 i = 0; i < 32; ++i) {
U32 c = cnt[i];
if (__builtin_expect(c <= 16, 1)) {
Vec256 w0 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const Vec128 *)(first + native_column_offset(i)))), prefix);
Vec256 w1 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const Vec128 *)(second + native_column_offset(i)))), prefix);
_mm256_storeu_si256((Vec256 *)dst, w0);
_mm256_storeu_si256((Vec256 *)(dst + 8), w1);
} else {
U32 h = block + i;
Byte copy[32];
Vec256 sorted;
if(__builtin_expect(c<=18,1)){
Vec128 lo=_mm_unpacklo_epi64(_mm_loadl_epi64((const Vec128*)(first+native_column_offset(i))),
_mm_loadl_epi64((const Vec128*)(second+native_column_offset(i))));
unsigned a=columns[256*16+h],b=c==18?columns[256*17+h]:255;
unsigned mn=a<b?a:b,mx=a<b?b:a;
Vec128 hi=_mm_insert_epi16(_mm_set1_epi8(-1),(int)((mn<<8)|mx),7);
sorted=merge32_byte(_mm256_set_m128i(hi,lo));
}else{
memcpy(copy,first+native_column_offset(i),8);memcpy(copy+8,second+native_column_offset(i),8);
for(U32 j=16;j<c;++j)copy[j]=columns[256*j+h];
for(U32 j=c;j<32;++j)copy[j]=255;
sorted=sort32_byte(_mm256_loadu_si256((const Vec256*)copy));
}
{
Vec128 vlo = _mm256_castsi256_si128(sorted), vhi = _mm256_extracti128_si256(sorted, 1);
Vec256 x0 = _mm256_or_si256(_mm256_cvtepu8_epi32(vlo), prefix);
Vec256 x1 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_srli_si128(vlo, 8)), prefix);
Vec256 x2 = _mm256_or_si256(_mm256_cvtepu8_epi32(vhi), prefix);
_mm256_storeu_si256((Vec256 *)(dst + 0), x0);
_mm256_storeu_si256((Vec256 *)(dst + 8), x1);
_mm256_storeu_si256((Vec256 *)(dst + 16), x2);
if (__builtin_expect(c > 24u, 0)) {
Vec256 x3 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_srli_si128(vhi, 8)), prefix);
_mm256_storeu_si256((Vec256 *)(dst + 24), x3);
}
}
}
dst += c;
prefix = _mm256_add_epi32(prefix, step);
}
return dst;
}
for (U32 i = 0; i < 32; ++i) {
U32 h = block + i, c = count[h];
if (__builtin_expect(c <= 16, 1)) {
Vec256 w0 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const Vec128 *)(first + native_column_offset(i)))), prefix);
Vec256 w1 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const Vec128 *)(second + native_column_offset(i)))), prefix);
if (__builtin_expect(end - dst >= 16, 1)) {
_mm256_storeu_si256((Vec256 *)dst, w0);
_mm256_storeu_si256((Vec256 *)(dst + 8), w1);
} else {
_mm256_maskstore_epi32((int *)dst, _mm256_cmpgt_epi32(_mm256_set1_epi32((int)(c < 8u ? c : 8u)), idx), w0);
_mm256_maskstore_epi32((int *)(dst + 8), _mm256_cmpgt_epi32(_mm256_set1_epi32((int)(c > 8u ? c - 8u : 0u)), idx), w1);
}
} else {
Byte copy[32];
Vec256 sorted;
if(__builtin_expect(c<=18,1)){
Vec128 lo=_mm_unpacklo_epi64(_mm_loadl_epi64((const Vec128*)(first+native_column_offset(i))),
_mm_loadl_epi64((const Vec128*)(second+native_column_offset(i))));
unsigned a=columns[256*16+h],b=c==18?columns[256*17+h]:255;
unsigned mn=a<b?a:b,mx=a<b?b:a;
Vec128 hi=_mm_insert_epi16(_mm_set1_epi8(-1),(int)((mn<<8)|mx),7);
sorted=merge32_byte(_mm256_set_m128i(hi,lo));
}else{
memcpy(copy,first+native_column_offset(i),8);memcpy(copy+8,second+native_column_offset(i),8);
for(U32 j=16;j<c;++j)copy[j]=columns[256*j+h];
for(U32 j=c;j<32;++j)copy[j]=255;
sorted=sort32_byte(_mm256_loadu_si256((const Vec256*)copy));
}
if (__builtin_expect(end - dst >= (c <= 24u ? 24u : 32u), 1)) {
Vec128 vlo = _mm256_castsi256_si128(sorted), vhi = _mm256_extracti128_si256(sorted, 1);
Vec256 x0 = _mm256_or_si256(_mm256_cvtepu8_epi32(vlo), prefix);
Vec256 x1 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_srli_si128(vlo, 8)), prefix);
Vec256 x2 = _mm256_or_si256(_mm256_cvtepu8_epi32(vhi), prefix);
_mm256_storeu_si256((Vec256 *)(dst + 0), x0);
_mm256_storeu_si256((Vec256 *)(dst + 8), x1);
_mm256_storeu_si256((Vec256 *)(dst + 16), x2);
if (__builtin_expect(c > 24u, 0)) {
Vec256 x3 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_srli_si128(vhi, 8)), prefix);
_mm256_storeu_si256((Vec256 *)(dst + 24), x3);
}
} else {
_mm256_storeu_si256((__m256i *)copy, sorted);
for (U32 j = 0; j < c; ++j) dst[j] = base | (h << 8) | copy[j];
}
}
dst += c;
prefix = _mm256_add_epi32(prefix, _mm256_set1_epi32(256));
}
return dst;
}
[[gnu::noinline]] static void sort_leaf_unsafe(const Byte *columns, U32 *count, U32 *dst, U32 base, U32 *end, const U32 *exceptional) {
for (U32 block = 0; block < 256; block += 32) {
alignas(32) Byte first[256], second[256];
#pragma GCC unroll 16
for(unsigned pf=0;pf<16;++pf)asm volatile("prefetchw %0"::"m"(*(const char*)((uintptr_t)dst+3072+64*pf)));
if (true) sort16_columns(columns + block, first, second);
Vec256 prefix = _mm256_set1_epi32(base | (block << 8));
if ((exceptional[block >> 5] & 255) == 0 && end - dst >= 512) {
dst = emit32_buckets16(first, second, count + block, dst, prefix);
continue;
}
dst = emit_group_c(dst, first, second, count, columns, block, base, prefix, end);
continue;
}
}
inline void sort_leaf(const U16 *src, U32 n, U32 *dst, U32 base, U32 *end) {
if (n < 64) {
U32 copy[64];
for (U32 i = 0; i < n; ++i) copy[i] = base | load<U16>(src + i);
std::sort(copy, copy + n);
std::memcpy(dst, copy, n * 4); return;
}
if (n > kLeafLimit) return counting_sort(src, n, dst, base);
alignas(64) static Byte columns[kRadix * kLeafLimit];
alignas(64) U32 count[256];
/* [MSET32] 哨兵行填充 4096 B 由 `std::memset` 改成 128 条显式 32B `vmovdqa`。
判题机 gcc 9.3 对已知长度的 memset 走 `rep stosq`；把「128 条 32B 存储」写成普通循环
它也会折叠回 rep stosq（1001 已实测），故这里用 `asm volatile` 强制保持独立存储。
每叶一次 x 65536 叶 = 268 MB 的填充。 */
auto clear_columns=[&](){
const __m256i sent = _mm256_set1_epi8((char)255);
#pragma GCC unroll 4
for(unsigned q=0;q<16u*kRadix;q+=32)
__asm__ volatile("vmovdqa %1, %0" : "=m"(*(__m256i *)(columns+q)) : "x"(sent));
};
static bool columns_initialized=false;
if(!columns_initialized){clear_columns();columns_initialized=true;}
for (U32 i = 0; i < 256; ++i) count[i] = i;
/* [B1Q] 4 元素/次 64 位取数：`src` 是 u16 顺序流，原形态每元素 1 条 16 位 load +
mov/movzbl 两条取高字节；本形态一次 64 位 load 出 4 个元素，高字节用移位直接取。
本机隔离微基准（work/b1v_mb1.cpp，全 L1/L2 驻留、min-of-7）：2.116 -> 1.956 cyc/元素（-7.6%）。
稳定性：桶内元素写入顺序与逐元素版逐位相同（同一次 load 的 4 个元素按低到高处理）⇒ 输出逐位不变。 */
{
U32 i = 0;
/* [SEAT12 SHRXSCAT] single named change: identical per-record loads/stores/addresses
and order (s=count[h]; count[h]=s+256; columns[s]=value) written as one inline-asm
loop whose key/value extraction uses the byte registers of q (ah,ch,dh,al,cl,dl) and
BMI2 SHRX; this removes the compiler's pre-shift mov copies (7.9 -> 6.4 uops/record).
The 4-record-at-a-time C loop and the scalar tail's semantics are unchanged. */
#define B1Q_SCAT4(P) \
"movq (%[" P "]), %%rax\n\t" \
"addq $8, %[" P "]\n\t" \
"movzbl %%ah, %%ebx\n\t" \
"shrx %%r11, %%rax, %%rcx\n\t" \
"shrx %%r12, %%rax, %%rdx\n\t" \
"movl (%[cnt],%%rbx,4), %%r13d\n\t" \
"leal 0x100(%%r13), %%r14d\n\t" \
"movl %%r14d, (%[cnt],%%rbx,4)\n\t" \
"movb %%al, (%[col],%%r13,1)\n\t" \
"movzbl %%ch, %%ebx\n\t" \
"movl (%[cnt],%%rbx,4), %%r13d\n\t" \
"leal 0x100(%%r13), %%r14d\n\t" \
"movl %%r14d, (%[cnt],%%rbx,4)\n\t" \
"movb %%cl, (%[col],%%r13,1)\n\t" \
"movzbl %%dh, %%ebx\n\t" \
"movl (%[cnt],%%rbx,4), %%r13d\n\t" \
"leal 0x100(%%r13), %%r14d\n\t" \
"movl %%r14d, (%[cnt],%%rbx,4)\n\t" \
"movb %%dl, (%[col],%%r13,1)\n\t" \
"shrx %%r11, %%rdx, %%rdx\n\t" \
"movzbl %%dh, %%ebx\n\t" \
"movl (%[cnt],%%rbx,4), %%r13d\n\t" \
"leal 0x100(%%r13), %%r14d\n\t" \
"movl %%r14d, (%[cnt],%%rbx,4)\n\t" \
"movb %%dl, (%[col],%%r13,1)\n\t"
const Byte *sp = (const Byte *)src;
if (n >= 16) {
U32 lim = n & ~15u;
const Byte *se = sp + 2u * lim;
__asm__ __volatile__(
"movl $16, %%r11d\n\t"
"movl $32, %%r12d\n\t"
".p2align 4\n\t1:\n\t"
B1Q_SCAT4("src") B1Q_SCAT4("src") B1Q_SCAT4("src") B1Q_SCAT4("src")
"cmpq %[end], %[src]\n\t"
"jb 1b\n\t"
: [src] "+r"(sp)
: [cnt] "r"(count), [col] "r"(columns), [end] "r"(se)
: "rax","rbx","rcx","rdx","r11","r12","r13","r14","cc","memory");
i = lim;
}
if (i + 4 <= n) {
U32 lim = n & ~3u;
const Byte *sp2 = (const Byte *)src + 2u * i;
const Byte *se2 = (const Byte *)src + 2u * lim;
__asm__ __volatile__(
"movl $16, %%r11d\n\t"
"movl $32, %%r12d\n\t"
".p2align 4\n\t1:\n\t"
B1Q_SCAT4("src")
"cmpq %[end], %[src]\n\t"
"jb 1b\n\t"
: [src] "+r"(sp2)
: [cnt] "r"(count), [col] "r"(columns), [end] "r"(se2)
: "rax","rbx","rcx","rdx","r11","r12","r13","r14","cc","memory");
i = lim;
}
#undef B1Q_SCAT4
#pragma GCC unroll 16
for (; i < n; ++i) {
U32 v = load<U16>(src + i), h = v >> 8, slot = count[h];
count[h] = slot + 256; columns[slot] = Byte(v);
}
}
U32 exceptional[8];
if (restore_counts(count, exceptional)) {
clear_columns();
if(count[load<U16>(src)>>8]==n)return uniform_high_sort(src,n,dst,base);
return counting_sort(src,n,dst,base);
}
const Vec256 idx = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
if (__builtin_expect((end - dst) >= (ptrdiff_t)n + 1024, 1)) {
alignas(32) Byte fA[8][256], sA[8][256];
U32 *gstart[8];
{
U32 **gp = gstart;
const Byte *colp = columns;
const Byte *fp = (const Byte *)fA, *sp = (const Byte *)sA;
const U32 *cntp = count;
Vec256 prefix = _mm256_set1_epi32(base);
for (U32 block = 0; block < 256; block += 32) {
*gp++ = dst;
#pragma GCC unroll 16
for(unsigned pf=0;pf<16;++pf)asm volatile("prefetchw %0"::"m"(*(const char*)((uintptr_t)dst+3072+64*pf)));
sort16_columns(colp, (Byte *)fp, (Byte *)sp);
dst = emit32_buckets16(fp, sp, cntp, dst, prefix);
colp += 32; fp += 256; sp += 256; cntp += 32;
}
}
{
__m256i fl = _mm256_loadu_si256((const __m256i *)exceptional);
U32 gm = (U32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(fl, _mm256_setzero_si256())));
while (gm) {
U32 g = (U32)__builtin_ctz(gm); gm &= gm - 1;
const U32 block = g << 5;
const U32 *cnt = count + block;
U32 *gdst = gstart[g];
U32 em = 0;
#pragma GCC unroll 4
for (U32 q = 0; q < 4; ++q)
em |= (U32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(_mm256_loadu_si256((const __m256i *)(cnt + 8 * q)), _mm256_set1_epi32(16)))) << (8 * q);
while (em) {
U32 i = (U32)__builtin_ctz(em); em &= em - 1;
U32 c = cnt[i];
__m256i iv = _mm256_set1_epi32((int)i);
__m256i acc = _mm256_and_si256(_mm256_cmpgt_epi32(iv, _mm256_setr_epi32(0,1,2,3,4,5,6,7)), _mm256_loadu_si256((const __m256i *)(cnt + 0)));
acc = _mm256_add_epi32(acc, _mm256_and_si256(_mm256_cmpgt_epi32(iv, _mm256_setr_epi32(8,9,10,11,12,13,14,15)), _mm256_loadu_si256((const __m256i *)(cnt + 8))));
acc = _mm256_add_epi32(acc, _mm256_and_si256(_mm256_cmpgt_epi32(iv, _mm256_setr_epi32(16,17,18,19,20,21,22,23)), _mm256_loadu_si256((const __m256i *)(cnt + 16))));
acc = _mm256_add_epi32(acc, _mm256_and_si256(_mm256_cmpgt_epi32(iv, _mm256_setr_epi32(24,25,26,27,28,29,30,31)), _mm256_loadu_si256((const __m256i *)(cnt + 24))));
__m128i s128 = _mm_add_epi32(_mm256_castsi256_si128(acc), _mm256_extracti128_si256(acc, 1));
s128 = _mm_hadd_epi32(s128, s128); s128 = _mm_hadd_epi32(s128, s128);
U32 *dp = gdst + (U32)_mm_cvtsi128_si32(s128);
U32 h = block + i;
Byte copy[32];
Vec256 sorted;
if (__builtin_expect(c <= 18, 1)) {
Vec128 lo = _mm_unpacklo_epi64(_mm_loadl_epi64((const Vec128 *)(fA[g] + native_column_offset(i))), _mm_loadl_epi64((const Vec128 *)(sA[g] + native_column_offset(i))));
unsigned a = columns[256*16+h], b = c == 18 ? columns[256*17+h] : 255;
unsigned mn = a<b?a:b, mx = a<b?b:a;
Vec128 hi = _mm_insert_epi16(_mm_set1_epi8(-1), (int)((mn<<8)|mx), 7);
sorted = merge32_byte(_mm256_set_m128i(hi, lo));
} else {
memcpy(copy,fA[g]+native_column_offset(i),8);memcpy(copy+8,sA[g]+native_column_offset(i),8);
for (U32 j = 16; j < c; ++j) copy[j] = columns[256*j+h];
for (U32 j = c; j < 32; ++j) copy[j] = 255;
sorted = sort32_byte(_mm256_loadu_si256((const Vec256 *)copy));
}
Vec256 pre = _mm256_set1_epi32((int)(base | (h << 8)));
Vec128 vlo = _mm256_castsi256_si128(sorted), vhi = _mm256_extracti128_si256(sorted, 1);
Vec256 x0 = _mm256_or_si256(_mm256_cvtepu8_epi32(vlo), pre);
Vec256 x1 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_srli_si128(vlo, 8)), pre);
Vec256 x2 = _mm256_or_si256(_mm256_cvtepu8_epi32(vhi), pre);
_mm256_storeu_si256((Vec256 *)dp, x0);
_mm256_storeu_si256((Vec256 *)(dp + 8), x1);
_mm256_maskstore_epi32((int *)(dp + 16), _mm256_cmpgt_epi32(_mm256_set1_epi32((int)((c - 16) < 8 ? (c - 16) : 8)), _mm256_setr_epi32(0,1,2,3,4,5,6,7)), x2);
if (__builtin_expect(c > 24, 0)) {
Vec256 x3 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_srli_si128(vhi, 8)), pre);
_mm256_maskstore_epi32((int *)(dp + 24), _mm256_cmpgt_epi32(_mm256_set1_epi32((int)(c - 24)), _mm256_setr_epi32(0,1,2,3,4,5,6,7)), x3);
}
}
}
}
} else {
sort_leaf_unsafe(columns, count, dst, base, end, exceptional);
}
}
}
static void small(unsigned char *__restrict s,unsigned *__restrict d,unsigned n,unsigned prefix,unsigned *array_end){
if(n<65536){small_original(s,d,n,prefix,array_end);return;}
unsigned mu=(n+255)/256;unsigned need=mu+(unsigned)(6.5*__builtin_sqrt((double)mu)+0.5)+8;unsigned odd=(need+31)/32;if(!(odd&1))odd++;unsigned cap=32u*odd;
if(cap>4096){small_original(s,d,n,prefix,array_end);return;}
uint32_t mp[256];
for(unsigned k=0;k<256;k++)mp[k]=k*cap;
const unsigned char *r=s;const unsigned char *rend=s+3u*n;
while(r+192<=rend){
__builtin_prefetch(r+512,0,0);
__builtin_prefetch(r+576,0,0);
__builtin_prefetch(r+640,0,0);
__builtin_prefetch(r+704,0,0);
__builtin_prefetch(r+768,0,0);
__builtin_prefetch(r+832,0,0);
__builtin_prefetch(r+896,0,0);
__builtin_prefetch(r+960,0,0);
#pragma GCC unroll 8
for(unsigned j=0;j<64;j+=8,r+=24){
uint64_t w0,w1,w2;memcpy(&w0,r,8);memcpy(&w1,r+8,8);memcpy(&w2,r+16,8);
{unsigned k=(unsigned)(w0>>16)&255u;unsigned target=mp[k]++;__builtin_prefetch(middle+target+32,0,2);middle[target]=(uint16_t)(w0);}
{unsigned k=(unsigned)(w0>>40)&255u;middle[mp[k]++]=(uint16_t)(w0>>24);}
{unsigned k=(unsigned)(w1)&255u;middle[mp[k]++]=(uint16_t)(w0>>48);}
{unsigned k=(unsigned)(w1>>24)&255u;middle[mp[k]++]=(uint16_t)(w1>>8);}
{unsigned k=(unsigned)(w1>>48)&255u;unsigned target=mp[k]++;__builtin_prefetch(middle+target+32,0,2);middle[target]=(uint16_t)(w1>>32);}
{unsigned k=(unsigned)(w2>>8)&255u;middle[mp[k]++]=(uint16_t)((w1>>56)|(w2<<8));}
{unsigned k=(unsigned)(w2>>32)&255u;middle[mp[k]++]=(uint16_t)(w2>>16);}
{unsigned k=(unsigned)(w2>>56)&255u;middle[mp[k]++]=(uint16_t)(w2>>40);}
}
}
for(;r<rend;r+=3){
unsigned k=r[2];uint16_t value;memcpy(&value,r,2);
middle[mp[k]++]=value;
}
for(unsigned k=0;k<256;k++)mp[k]-=k*cap;
{ unsigned long msum=0; for(unsigned k=0;k<256;k++){ if(mp[k]>cap){small_original(s,d,n,prefix,array_end);return;} msum+=mp[k]; }
if(msum!=(unsigned long)n){small_original(s,d,n,prefix,array_end);return;} }
for(unsigned k=0;k<256;k++){
unsigned count=mp[k],pre=prefix|(k<<16);
const uint16_t *src=middle+k*cap;
byte_sort::sort_leaf(src,count,d,pre,array_end);
d+=count;
}
}
template<bool Reserved> static bool partition(unsigned *__restrict a,unsigned n,unsigned capacity=0){
for(unsigned k=0;k<K;k++){
byte_cursor[k]=k*192+3;
pos[k]*=3;
}
unsigned full=n&~1023u;
for(unsigned page=0;page<full;page+=1024){
if(page+5120<n)asm volatile("orl $0, %0" : "+m"(a[page+4112]));
#pragma GCC unroll 24
for(unsigned i=page;i<page+1024;i++){
unsigned x=a[i],k=x>>24,o=byte_cursor[k];
if(__builtin_expect((o&63)==0,0)){
if(Reserved && pos[k]>sizeof(workspace)-192u){_mm_sfence();return false;}
unsigned char *d=workspace+pos[k];
const unsigned char *src=staging_bytes+o-192;
unsigned tail_word=(x<<8)|src[188];
__m256i last=_mm256_load_si256((const __m256i*)(src+160));
last=_mm256_blend_epi32(last,_mm256_set1_epi32((int)tail_word),0x80);
#pragma GCC unroll 5
for(unsigned j=0;j<160;j+=32)
_mm256_stream_si256((__m256i*)(d+j),_mm256_load_si256((const __m256i*)(src+j)));
_mm256_stream_si256((__m256i*)(d+160),last);
pos[k]+=192;o-=192;
}else *(unsigned *)(void *)(staging_bytes+o-3)=x;
byte_cursor[k]=o+3;
}
}
for(unsigned i=full;i<n;i++){
unsigned x=a[i],k=x>>24,o=byte_cursor[k];
if(__builtin_expect((o&63)==0,0)){
if(Reserved && pos[k]>sizeof(workspace)-192u){_mm_sfence();return false;}
unsigned char *d=workspace+pos[k];
const unsigned char *src=staging_bytes+o-192;
unsigned tail_word=(x<<8)|src[188];
__m256i last=_mm256_load_si256((const __m256i*)(src+160));
last=_mm256_blend_epi32(last,_mm256_set1_epi32((int)tail_word),0x80);
#pragma GCC unroll 5
for(unsigned j=0;j<160;j+=32)
_mm256_stream_si256((__m256i*)(d+j),_mm256_load_si256((const __m256i*)(src+j)));
_mm256_stream_si256((__m256i*)(d+160),last);
pos[k]+=192;o-=192;
}else *(unsigned *)(void *)(staging_bytes+o-3)=x;
byte_cursor[k]=o+3;
}
for(unsigned k=0;k<K;k++)pos[k]=pos[k]/3+((byte_cursor[k]-k*192-3))/3;
_mm_sfence();
if(Reserved)for(unsigned k=0;k<K;k++)if(pos[k]-starts[k]>capacity)return false;
return true;
}
void sort(unsigned *a,int n){
{ static int done=0; if(!done){ done=1; /* workspace pages are faulted lazily */
syscall(28,(void*)middle,sizeof(middle),14); } }
{ static volatile unsigned long r105b_pad1=0; r105b_pad1+=(unsigned long)n+(unsigned long)(uintptr_t)a; }
if(n!=(int)NPORT){std::sort(a,a+n);return;}
{ static int pgd=0; if(!pgd){pgd=1; syscall(28,(void*)a,(size_t)NPORT*4u,14);} }
unsigned capacity=(((unsigned(NPORT)+K-1)/K+3620u+BS-1)&~(BS-1))+BS;
for(unsigned k=0;k<K;k++)starts[k]=pos[k]=k*capacity;
if(!partition<true>(a,NPORT,capacity)){
memset(hist,0,sizeof(hist));
for(int i=0;i<NPORT;i++)++hist[a[i]>>(32-TB)];
unsigned z=0;
for(unsigned k=0;k<K;k++){starts[k]=pos[k]=z;z=(z+hist[k]+BS-1)&~(BS-1);}
partition<false>(a,NPORT);
}
unsigned z=0;
for(unsigned k=0;k<K;k++){
unsigned size=pos[k]-starts[k];
memcpy(workspace+3*(pos[k]&~(BS-1)),staging_bytes+k*192,3*(pos[k]&(BS-1)));
small(workspace+3*starts[k],a+z,size,k<<24,a+NPORT);
z+=size;
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 431.358 ms | 898 MB + 240 KB | Accepted | Score: 100 | 显示更多 |