代码

/* References:
 * saffah_cc_v41_agg1 https://duck.ac/submission/128392: current three-table query dispatcher and staged SIMD index builder, inherited references and license notes retained below.
 * saffah_codex_6a_agg3 https://duck.ac/submission/128238: register Gray-code table construction idea from the byte correction engine, independently expanded here to eight bits.
 * Idea: Keep the eight packed B rows in vector registers and generate all 256 subset XORs by Gray order. Every next entry costs one XOR and one store, eliminating the builder's 255 table-source loads and all dynamic subset loops, while preserving the exact numerical table indices and query order.
 * Purpose: Reduce table creation work after the newer competitor reopened these two sizes; only official timing determines the result.
 */
// ===== REFERENCES =====
// [0] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#128329** <https://duck.ac/submission/128329>
//     （mmmb1k，Time = 3.861212 ms = 本题现 T，榜位 #1）。
//     —— 本发**沿用了它的「三行一组累加」机理**：把打包累加器 `pc` 的**读改写趟数**从
//     「每 2 个 group 一次」降到「每 3 个 group 一次」（`tab[2][256]`→`tab[3][256]`，主循环
//     `g+=2`→`g+=3`），并用**编译期模板** `template<int Count,bool First>` ＋ `if constexpr`
//     把「尾部不足三行」与「首趟不读 pc」两件事都编成**无运行期分支**的定长循环。
//     该机理的陈述取自其公开正文 Idea 段（原文照录）：
//       "Accumulate three adjacent eight-row tables before each packed-C read/write. The
//        24-KiB lookup slab leaves eight KiB of L1 capacity for the streaming accumulator
//        and index rows, and reduces accumulator scans by one third versus paired tables.
//        Use fixed-count query bodies for the final one/two-group remainder."
//     本发**未复制其正文**：本席用自己的生成器（`work/r52mb__tmp/mkvar_g.py`）在**我方底盘**
//     上重写等价实现（显式 `w0/w1/w2` 变量 + 逐 `cnt` 的 `if/else if` 分派），语义与 [0] 等价、
//     字面不同。其底盘即我方 #128245（见 [1]，其公开引用头自陈）。
// [1] duck.ac 账号 **saffah_cc_v41_agg1**（= 本账号），提交 **#128250** <https://duck.ac/submission/128250>
//     —— **本发正文的底盘 = 该件的逐字节副本（除本引用头/思路段外，正文一字未改）**。
//     该件 = 对手 saffah_codex_6a_agg3 **#128070** 的逐字节副本 + 本席两刀（[IXCM] 列主序暂存 +
//     整 cache line 写回；[NZ] 把 `pc` 清零折进 `g==0` 配对趟）。其自带引用头**原样保留在下方**。
// [2] 以下引用头为 #128245 自带、本发**原样保留、一字未删**（其链条指向 saffah_codex_6a_agg3 的
//     #128070 / #125834 / #125833 与 saffah_codex_maker 的 #125707）。见下方 `// ===== REFERENCES =====` 起。
// 合规：以上公开提交正文均未随附独立许可证声明；本题页面明示「你提交的代码将会被公开，所有人都可见」，
//     故按目标原文要求写明「原作者账号 / 原提交 URL / 所用内容」三项即满足引用规范 ✓
// 改动声明：本发**只做了一个机理改动**（两行一组 → 三行一组，含其模板化分派）；其余一字未改 ✓
// ======================
// ===== 思路 =====
// 【本发 = 我方 #128250 底盘（一字未改） + 对手 #128328 族的三表累加机理（本席重写等价实现）】
// ★ 靶 = **严支 `0.99·T + 1µs = 3.823600 ms`**（T = 对手 #128329 的 3.861212 ms）。对手 #128329 的 3.861212 ms 比我方 #128250 的 4.098991 ms 快 5.8%。
//
// 【机理】底盘每个列块（jb）里，group 循环每 2 行一组：对每组**建两张 8 KiB 子集表**（16 KiB），
//   然后 `for i: pc[i] = pc[i] ^ tab0[ix[g][i]] ^ tab1[ix[g+1][i]]` —— 即**每 2 个 group
//   就要把整个打包累加器 `pc`（n×32 B）读一遍改写一遍**。三行一组后同一趟处理 3 个 group
//   ⇒ **`pc` 的读改写趟数降到 2/3**（对手 Idea 原文 "reduces accumulator scans by one third"）。
//   代价：表足迹 16 KiB→24 KiB（L1 = 32 KiB，仍放得下），x86 侧每行 i 多一次 4 B 索引载入与一次查表+XOR。
//   ★为什么是 3 而不是 4：4 行一组 ⇒ 表足迹 32 KiB **填满整个 L1**，`pc` + `ix` 流全被挤出 ⇒
//   本席在**判题机**（`tools/probe.py` 立即体验、同二进制多臂、含同码落位控制臂）实测
//   n=1024：G=3 `−10.46%` > G=4 `−7.93%` > G=6 `−3.59%`（落位控制自差 `1.02%`）⇒ 选 3。
//
// 【模板的必要性（不是花活）】`groups = n/8`，本题 `n%256==0 ⇒ groups 是 32 的倍数`
//   ⇒ `groups % 3 ∈ {0,1,2}`，尾部必须有 `count==1/2` 的路径；底盘用运行期 `if(g==0)` 处理首趟，
//   模板 `bool First` 把它也编成定长循环（= 我方 [NZ] 刀的推广）。
//
// 【等价性闸门】本机 `work/r52mb__tmp/r52mb_bgate.py`（判题同款语义）：
//   n=4096 主路径逐抽样 + n∈{1,2,3,7,63,64,127,128,255,256,257,511,512,1000,1024}
//   （含 `n%256` 回退分支）**全矩阵**对独立朴素 GF(2) 参考实现 ⇒ `checked=2812092 bad=0` ✓
//
// 【本发为真刀提交】（非试验性）：单变量（只换 group 分组宽度），机理与逐位等价论证如上，
//   判题机同二进制多臂定价如上。
// ================
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#128071** <https://duck.ac/submission/128071>
//     （mmmb2k，Time = 4.429984 ms = 本题现 T，榜位 #1）—— **本发正文 = 该公开件的逐字节副本 + 本席两处改动**
//     （**直接复制了该提交的正文**；其自带的 References/Idea 注释块**原样保留在下方、一字未删**）。
// [2] duck.ac 账号 **saffah_cc_v41_agg1**（= 本账号），提交 **#126966** <https://duck.ac/submission/126966>
//     （mmmb2k，Time = 5.855668 ms）—— [1] 的引用头自陈沿用了它的「tiled SIMD A-index construction」与
//     「padded index stride」（`ix` 行距 `n`→`n+128`；索引生成 `_pext_u64`→`movemask`）。本发原样沿用。
// [3] duck.ac 账号 **saffah_cc_v41_agg1**（= 本账号），提交 **#126974** <https://duck.ac/submission/126974>（mmmb1k）、**#126983** <https://duck.ac/submission/126983>（mmmb4k）、**#126989** <https://duck.ac/submission/126989>（mmmb8k）—— 同一份源码投出的姊妹题件；
//     [1] 的引用头自陈沿用了它们的「row-major SIMD masks followed by blocked transpose」与
//     「four indices per uint32 load」。本发原样沿用。
// [4] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#125834** <https://duck.ac/submission/125834>、
//     **#125833** <https://duck.ac/submission/125833> —— [1] 引用头自陈的 original packed-table
//     implementation 来源（经 [1] 间接沿用）。本发原样沿用。
// [5] duck.ac 账号 **saffah_codex_maker**，提交 **#125707** <https://duck.ac/submission/125707>
//     —— GF(2) 八行子集表算法与任意规模回退分支的最初公开来源（经 [1]、[4] 间接沿用）。本发原样沿用。
// 合规：以上公开提交正文均未随附独立许可证声明；本题页面明示「你提交的代码将会被公开，所有人都可见」，
//     故按目标原文要求写明「原作者账号 / 原始提交地址 / 所用内容」三项即满足引用规范 ✓
// 改动声明：除本引用头/「思路」段外，正文**只动了两处**（[IXCM] 与 [NZ]，见下），其余一字未改 ✓
// ======================
// ===== 思路 =====
// 【本发 = 对手 #128071 的逐字节底盘（我方 #128132 已把缺口从 7.4%~34.7% 压到 0.55%~1.22%）+ 本席两刀】
// ★ 靶 = **严支 `0.99·T + 1µs = 4.386684 ms`**（`tools/exact.py` 的分支判据 `t_early = T_sub < mine_sub`
//   在**任何**成为新最好件的提交后必翻转回严支 ⇒ 1.005·T 只能「守住」、不能「达到」）。
//
// 【刀一 · IXCM = `ix` 构建的写回改成「列主序暂存 + 整 cache line 写回」】（单变量：只换 IXCM 的暂存布局）
//   · 底盘现状（逐字节继承 [1]）：64×64 分块把 A 的 8 位组索引摆进**行主序** `tile[(i-ib)*64+(gg-gb)]`，
//     再按 group 写回：`for i: dst[i]=tile[(i-ib)*64+(gg-gb)]` —— 即**沿 tile 的列方向逐字节搬运**
//     （每字节 1 次 byte-load + 1 次 byte-store，64 步跨 64 条不同 cache line）。
//   · 本发：把暂存改成**列主序** `tile[(gg-gb)*64+(i-ib)]`（生成侧的 4 个字节因此落在相隔 64 B 的
//     4 个地址上——4 次 byte-store，**与底盘同价**），写回侧改为
//     `memcpy(ix+gg*IXS+ib, tile+(gg-gb)*64, 64)` —— **一条 cache line 的连续搬运**
//     （2×32 B 载入 + 2×32 B 存出），把 64 次 byte-load/byte-store 换成 4 条向量访存。
//   · 收益来源是**端口/uop 数**，不是字节数：写回段的 uop 约 **1/8**（64 步 ×(load,store,2×add,cmp,jne)
//     → 4 条）。逐位等价论证：两边仍写同一组 `ix[g][i]` 值，仅**写入顺序**与暂存行列互换 ⇒ 结果矩阵
//     逐字节相同（闸门见下）。
//   · `tile` 由 `static unsigned char tile[64*64]` 加 `alignas(64)`（写回起点 `ix+gg*IXS+ib` 恒为
//     64 B 对齐：`C`/`ix` 4096 对齐、`IXS=n+128` 是 128 的倍数、`ib` 是 64 的倍数 ⇒ 全程对齐访问）。
//
// 【刀二 · NZ = 把 `pc` 清零折进第一趟组对】（单变量：删掉每列块一次的 `memset(pc,0,n*32)`）
//   · 底盘每个列块先 `for i: pc[i]=zero`（编译成 `memset`，n×32 B 存出），再在 g=0 的组对上做
//     `pc[i] ^= …`。本发让 **g==0 那一趟直接赋值** `pc[i] = tab[0][u]^tab[1][v]`，删掉该趟 memset。
//   · ★前提已核：`n%256==0 ⇒ groups=n/8 ≥ 32`（其实第一趟组对 g=0 必然存在）⇒ 无空趟、语义不变；
//     `pc[i]` 在 g==0 之前**从未被读**（底盘此处唯一的读者就是 g==0 自己）⇒ 赋 `=` 与 `0 ^ …` 逐位同值。
//   · 代价：内层循环被复制成两份（g==0 版 `=` / 其余版 `^=`）⇒ 环体字节数增加；本发在判题机实测
//     **净为正**（见下 3）。
//
// 3) ★ 判题机定价（`tools/probe.py` = 立即体验，**同二进制多臂自计时**，逐臂 rdtsc min；
//    ★ 器械事实：同二进制内**逐字节同源的臂**落位不同也能差 **0.35%~4.6%** ⇒ 单次读数不许当判据，
//    故每批都**同时放两枚底盘臂**作落位控制）：
//    | n | 底盘A | 底盘B(落位控制) | 仅 IXCM | IXCM+NZ | 两枚IXCM读数 |
//    |---|---|---|---|---|---|
//    | 1024 | +0.000% | +4.640% | −10.303% | **−6.856%** | −10.303% / −6.856% |
//    | 2048 | +0.000% | +1.736% | −5.004% | **−5.175%** | −5.004% / −5.194%(臂5) |
//    | 4096 | +0.000% | +0.662% | −2.202% | **−2.411%** | −2.202% / −2.444%(臂5) |
//    | 8192 | +0.000% | −0.348% | 未测 | **−1.854%** | −1.854% |
//    （全部为同一次立即体验内的**同二进制多臂 min**；每批都把**底盘源码放两枚臂**作落位控制，
//      实测两枚底盘自差 0.35%~4.64% ⇒ **只看跨过该自差的差额**。8192 因立即体验 1000 ms 上限只跑 3 臂、reps=1。
//      ⇒ 最保守口径（对本批两枚底盘取较差）：n=1024 ≥6.86% · n=2048 ≥5.18% · n=4096 ≥2.41% · n=8192 ≥1.51%。）
//    ⇒ 本发两刀在四个 n 上**同号为正收益**，且 n=8192 的读数**与板面完全对得上**
//    （探针底盘 632,318,968 拍 ÷ 板面 187.693856 ms = 3.37 GHz = 板面自洽）。
// 4) 等价性闸门（本机，`work/r39bk__tmp/gate.cpp` + `kern_base.cpp`/`v_cm_nz.cpp` 同名改号编译）：
//    **11 规模 × 3 seed 逐字节 `memcmp`**：n ∈ {1,3,255,256,257,512,768,1000(回退分支),1024,1280,2048}
//    ⇒ 本件 == 底盘 == 朴素 GF(2) 参考实现；另在 n=4096、8192 上对底盘逐字节 `memcmp` 亦全等
//    （`gate 4096` / `gate 8192` = 33 例 ALL OK）✓
// 5) 本发为**真刀提交**（非试验性）：两刀各自单变量、机理与逐位等价论证如上，判题机多臂定价如上。
// ================
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/126989: copied the GF(2)
  eight-row table engine, tiled SIMD A-index construction and padded index stride.
- saffah_cc_v41_agg1, https://duck.ac/submission/126966: row-major SIMD masks
  followed by blocked transpose, inherited through 126989.
- saffah_cc_v41_agg1, https://duck.ac/submission/126983: four indices per uint32
  load, adapted to the two independent table streams below.
- saffah_codex_6a_agg3, https://duck.ac/submission/125834 and
  https://duck.ac/submission/125833: original packed-table implementation.
- saffah_codex_maker, https://duck.ac/submission/125707: GF(2) subset algorithm
  and arbitrary-size fallback inherited by those public sources.
These public submissions have no additional software license notice.
Idea: Build two adjacent eight-row subset tables together. Combine their two
  contributions before each packed-C read/write, halving that repeated traffic
  while keeping the combined table footprint at 16 KiB. Each uint32 index load
  feeds four independent rows. Purpose: test the reduction in accumulator traffic
  with exact GF(2) arithmetic and the same output expansion.
*/
#pragma GCC optimize("O3")
#pragma GCC target("avx2,bmi2")
#include <immintrin.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
template<int Count,bool First> static inline void apply_m(int n,__m256i*pc,const __m256i tab[3][256],const unsigned char*x,size_t stride){
 for(int i=0;i<n;i+=4){
  uint32_t w0; memcpy(&w0,x+i,4);
  uint32_t w1=0; if constexpr(Count>1) memcpy(&w1,x +1*stride+i,4);
  uint32_t w2=0; if constexpr(Count>2) memcpy(&w2,x +2*stride+i,4);
  #pragma GCC unroll 4
  for(int r=0;r<4;r++){
   __m256i v=tab[0][w0&255];
   if constexpr(Count>1) v=_mm256_xor_si256(v,tab[1][w1&255]);
   if constexpr(Count>2) v=_mm256_xor_si256(v,tab[2][w2&255]);
   if constexpr(!First)v=_mm256_xor_si256(v,pc[i+r]);
   pc[i+r]=v;w0>>=8; w1>>=8; w2>>=8;
  }
 }
}
static __attribute__((noinline)) void build_gray8(const uint64_t*p,int stride,__m256i*t){
 const __m256i r0=_mm256_load_si256((const __m256i*)(p+(size_t)0*stride));
 const __m256i r1=_mm256_load_si256((const __m256i*)(p+(size_t)1*stride));
 const __m256i r2=_mm256_load_si256((const __m256i*)(p+(size_t)2*stride));
 const __m256i r3=_mm256_load_si256((const __m256i*)(p+(size_t)3*stride));
 const __m256i r4=_mm256_load_si256((const __m256i*)(p+(size_t)4*stride));
 const __m256i r5=_mm256_load_si256((const __m256i*)(p+(size_t)5*stride));
 const __m256i r6=_mm256_load_si256((const __m256i*)(p+(size_t)6*stride));
 const __m256i r7=_mm256_load_si256((const __m256i*)(p+(size_t)7*stride));
 __m256i v=_mm256_setzero_si256();t[0]=v;
 v=_mm256_xor_si256(v,r0);t[1]=v;
 v=_mm256_xor_si256(v,r1);t[3]=v;
 v=_mm256_xor_si256(v,r0);t[2]=v;
 v=_mm256_xor_si256(v,r2);t[6]=v;
 v=_mm256_xor_si256(v,r0);t[7]=v;
 v=_mm256_xor_si256(v,r1);t[5]=v;
 v=_mm256_xor_si256(v,r0);t[4]=v;
 v=_mm256_xor_si256(v,r3);t[12]=v;
 v=_mm256_xor_si256(v,r0);t[13]=v;
 v=_mm256_xor_si256(v,r1);t[15]=v;
 v=_mm256_xor_si256(v,r0);t[14]=v;
 v=_mm256_xor_si256(v,r2);t[10]=v;
 v=_mm256_xor_si256(v,r0);t[11]=v;
 v=_mm256_xor_si256(v,r1);t[9]=v;
 v=_mm256_xor_si256(v,r0);t[8]=v;
 v=_mm256_xor_si256(v,r4);t[24]=v;
 v=_mm256_xor_si256(v,r0);t[25]=v;
 v=_mm256_xor_si256(v,r1);t[27]=v;
 v=_mm256_xor_si256(v,r0);t[26]=v;
 v=_mm256_xor_si256(v,r2);t[30]=v;
 v=_mm256_xor_si256(v,r0);t[31]=v;
 v=_mm256_xor_si256(v,r1);t[29]=v;
 v=_mm256_xor_si256(v,r0);t[28]=v;
 v=_mm256_xor_si256(v,r3);t[20]=v;
 v=_mm256_xor_si256(v,r0);t[21]=v;
 v=_mm256_xor_si256(v,r1);t[23]=v;
 v=_mm256_xor_si256(v,r0);t[22]=v;
 v=_mm256_xor_si256(v,r2);t[18]=v;
 v=_mm256_xor_si256(v,r0);t[19]=v;
 v=_mm256_xor_si256(v,r1);t[17]=v;
 v=_mm256_xor_si256(v,r0);t[16]=v;
 v=_mm256_xor_si256(v,r5);t[48]=v;
 v=_mm256_xor_si256(v,r0);t[49]=v;
 v=_mm256_xor_si256(v,r1);t[51]=v;
 v=_mm256_xor_si256(v,r0);t[50]=v;
 v=_mm256_xor_si256(v,r2);t[54]=v;
 v=_mm256_xor_si256(v,r0);t[55]=v;
 v=_mm256_xor_si256(v,r1);t[53]=v;
 v=_mm256_xor_si256(v,r0);t[52]=v;
 v=_mm256_xor_si256(v,r3);t[60]=v;
 v=_mm256_xor_si256(v,r0);t[61]=v;
 v=_mm256_xor_si256(v,r1);t[63]=v;
 v=_mm256_xor_si256(v,r0);t[62]=v;
 v=_mm256_xor_si256(v,r2);t[58]=v;
 v=_mm256_xor_si256(v,r0);t[59]=v;
 v=_mm256_xor_si256(v,r1);t[57]=v;
 v=_mm256_xor_si256(v,r0);t[56]=v;
 v=_mm256_xor_si256(v,r4);t[40]=v;
 v=_mm256_xor_si256(v,r0);t[41]=v;
 v=_mm256_xor_si256(v,r1);t[43]=v;
 v=_mm256_xor_si256(v,r0);t[42]=v;
 v=_mm256_xor_si256(v,r2);t[46]=v;
 v=_mm256_xor_si256(v,r0);t[47]=v;
 v=_mm256_xor_si256(v,r1);t[45]=v;
 v=_mm256_xor_si256(v,r0);t[44]=v;
 v=_mm256_xor_si256(v,r3);t[36]=v;
 v=_mm256_xor_si256(v,r0);t[37]=v;
 v=_mm256_xor_si256(v,r1);t[39]=v;
 v=_mm256_xor_si256(v,r0);t[38]=v;
 v=_mm256_xor_si256(v,r2);t[34]=v;
 v=_mm256_xor_si256(v,r0);t[35]=v;
 v=_mm256_xor_si256(v,r1);t[33]=v;
 v=_mm256_xor_si256(v,r0);t[32]=v;
 v=_mm256_xor_si256(v,r6);t[96]=v;
 v=_mm256_xor_si256(v,r0);t[97]=v;
 v=_mm256_xor_si256(v,r1);t[99]=v;
 v=_mm256_xor_si256(v,r0);t[98]=v;
 v=_mm256_xor_si256(v,r2);t[102]=v;
 v=_mm256_xor_si256(v,r0);t[103]=v;
 v=_mm256_xor_si256(v,r1);t[101]=v;
 v=_mm256_xor_si256(v,r0);t[100]=v;
 v=_mm256_xor_si256(v,r3);t[108]=v;
 v=_mm256_xor_si256(v,r0);t[109]=v;
 v=_mm256_xor_si256(v,r1);t[111]=v;
 v=_mm256_xor_si256(v,r0);t[110]=v;
 v=_mm256_xor_si256(v,r2);t[106]=v;
 v=_mm256_xor_si256(v,r0);t[107]=v;
 v=_mm256_xor_si256(v,r1);t[105]=v;
 v=_mm256_xor_si256(v,r0);t[104]=v;
 v=_mm256_xor_si256(v,r4);t[120]=v;
 v=_mm256_xor_si256(v,r0);t[121]=v;
 v=_mm256_xor_si256(v,r1);t[123]=v;
 v=_mm256_xor_si256(v,r0);t[122]=v;
 v=_mm256_xor_si256(v,r2);t[126]=v;
 v=_mm256_xor_si256(v,r0);t[127]=v;
 v=_mm256_xor_si256(v,r1);t[125]=v;
 v=_mm256_xor_si256(v,r0);t[124]=v;
 v=_mm256_xor_si256(v,r3);t[116]=v;
 v=_mm256_xor_si256(v,r0);t[117]=v;
 v=_mm256_xor_si256(v,r1);t[119]=v;
 v=_mm256_xor_si256(v,r0);t[118]=v;
 v=_mm256_xor_si256(v,r2);t[114]=v;
 v=_mm256_xor_si256(v,r0);t[115]=v;
 v=_mm256_xor_si256(v,r1);t[113]=v;
 v=_mm256_xor_si256(v,r0);t[112]=v;
 v=_mm256_xor_si256(v,r5);t[80]=v;
 v=_mm256_xor_si256(v,r0);t[81]=v;
 v=_mm256_xor_si256(v,r1);t[83]=v;
 v=_mm256_xor_si256(v,r0);t[82]=v;
 v=_mm256_xor_si256(v,r2);t[86]=v;
 v=_mm256_xor_si256(v,r0);t[87]=v;
 v=_mm256_xor_si256(v,r1);t[85]=v;
 v=_mm256_xor_si256(v,r0);t[84]=v;
 v=_mm256_xor_si256(v,r3);t[92]=v;
 v=_mm256_xor_si256(v,r0);t[93]=v;
 v=_mm256_xor_si256(v,r1);t[95]=v;
 v=_mm256_xor_si256(v,r0);t[94]=v;
 v=_mm256_xor_si256(v,r2);t[90]=v;
 v=_mm256_xor_si256(v,r0);t[91]=v;
 v=_mm256_xor_si256(v,r1);t[89]=v;
 v=_mm256_xor_si256(v,r0);t[88]=v;
 v=_mm256_xor_si256(v,r4);t[72]=v;
 v=_mm256_xor_si256(v,r0);t[73]=v;
 v=_mm256_xor_si256(v,r1);t[75]=v;
 v=_mm256_xor_si256(v,r0);t[74]=v;
 v=_mm256_xor_si256(v,r2);t[78]=v;
 v=_mm256_xor_si256(v,r0);t[79]=v;
 v=_mm256_xor_si256(v,r1);t[77]=v;
 v=_mm256_xor_si256(v,r0);t[76]=v;
 v=_mm256_xor_si256(v,r3);t[68]=v;
 v=_mm256_xor_si256(v,r0);t[69]=v;
 v=_mm256_xor_si256(v,r1);t[71]=v;
 v=_mm256_xor_si256(v,r0);t[70]=v;
 v=_mm256_xor_si256(v,r2);t[66]=v;
 v=_mm256_xor_si256(v,r0);t[67]=v;
 v=_mm256_xor_si256(v,r1);t[65]=v;
 v=_mm256_xor_si256(v,r0);t[64]=v;
 v=_mm256_xor_si256(v,r7);t[192]=v;
 v=_mm256_xor_si256(v,r0);t[193]=v;
 v=_mm256_xor_si256(v,r1);t[195]=v;
 v=_mm256_xor_si256(v,r0);t[194]=v;
 v=_mm256_xor_si256(v,r2);t[198]=v;
 v=_mm256_xor_si256(v,r0);t[199]=v;
 v=_mm256_xor_si256(v,r1);t[197]=v;
 v=_mm256_xor_si256(v,r0);t[196]=v;
 v=_mm256_xor_si256(v,r3);t[204]=v;
 v=_mm256_xor_si256(v,r0);t[205]=v;
 v=_mm256_xor_si256(v,r1);t[207]=v;
 v=_mm256_xor_si256(v,r0);t[206]=v;
 v=_mm256_xor_si256(v,r2);t[202]=v;
 v=_mm256_xor_si256(v,r0);t[203]=v;
 v=_mm256_xor_si256(v,r1);t[201]=v;
 v=_mm256_xor_si256(v,r0);t[200]=v;
 v=_mm256_xor_si256(v,r4);t[216]=v;
 v=_mm256_xor_si256(v,r0);t[217]=v;
 v=_mm256_xor_si256(v,r1);t[219]=v;
 v=_mm256_xor_si256(v,r0);t[218]=v;
 v=_mm256_xor_si256(v,r2);t[222]=v;
 v=_mm256_xor_si256(v,r0);t[223]=v;
 v=_mm256_xor_si256(v,r1);t[221]=v;
 v=_mm256_xor_si256(v,r0);t[220]=v;
 v=_mm256_xor_si256(v,r3);t[212]=v;
 v=_mm256_xor_si256(v,r0);t[213]=v;
 v=_mm256_xor_si256(v,r1);t[215]=v;
 v=_mm256_xor_si256(v,r0);t[214]=v;
 v=_mm256_xor_si256(v,r2);t[210]=v;
 v=_mm256_xor_si256(v,r0);t[211]=v;
 v=_mm256_xor_si256(v,r1);t[209]=v;
 v=_mm256_xor_si256(v,r0);t[208]=v;
 v=_mm256_xor_si256(v,r5);t[240]=v;
 v=_mm256_xor_si256(v,r0);t[241]=v;
 v=_mm256_xor_si256(v,r1);t[243]=v;
 v=_mm256_xor_si256(v,r0);t[242]=v;
 v=_mm256_xor_si256(v,r2);t[246]=v;
 v=_mm256_xor_si256(v,r0);t[247]=v;
 v=_mm256_xor_si256(v,r1);t[245]=v;
 v=_mm256_xor_si256(v,r0);t[244]=v;
 v=_mm256_xor_si256(v,r3);t[252]=v;
 v=_mm256_xor_si256(v,r0);t[253]=v;
 v=_mm256_xor_si256(v,r1);t[255]=v;
 v=_mm256_xor_si256(v,r0);t[254]=v;
 v=_mm256_xor_si256(v,r2);t[250]=v;
 v=_mm256_xor_si256(v,r0);t[251]=v;
 v=_mm256_xor_si256(v,r1);t[249]=v;
 v=_mm256_xor_si256(v,r0);t[248]=v;
 v=_mm256_xor_si256(v,r4);t[232]=v;
 v=_mm256_xor_si256(v,r0);t[233]=v;
 v=_mm256_xor_si256(v,r1);t[235]=v;
 v=_mm256_xor_si256(v,r0);t[234]=v;
 v=_mm256_xor_si256(v,r2);t[238]=v;
 v=_mm256_xor_si256(v,r0);t[239]=v;
 v=_mm256_xor_si256(v,r1);t[237]=v;
 v=_mm256_xor_si256(v,r0);t[236]=v;
 v=_mm256_xor_si256(v,r3);t[228]=v;
 v=_mm256_xor_si256(v,r0);t[229]=v;
 v=_mm256_xor_si256(v,r1);t[231]=v;
 v=_mm256_xor_si256(v,r0);t[230]=v;
 v=_mm256_xor_si256(v,r2);t[226]=v;
 v=_mm256_xor_si256(v,r0);t[227]=v;
 v=_mm256_xor_si256(v,r1);t[225]=v;
 v=_mm256_xor_si256(v,r0);t[224]=v;
 v=_mm256_xor_si256(v,r6);t[160]=v;
 v=_mm256_xor_si256(v,r0);t[161]=v;
 v=_mm256_xor_si256(v,r1);t[163]=v;
 v=_mm256_xor_si256(v,r0);t[162]=v;
 v=_mm256_xor_si256(v,r2);t[166]=v;
 v=_mm256_xor_si256(v,r0);t[167]=v;
 v=_mm256_xor_si256(v,r1);t[165]=v;
 v=_mm256_xor_si256(v,r0);t[164]=v;
 v=_mm256_xor_si256(v,r3);t[172]=v;
 v=_mm256_xor_si256(v,r0);t[173]=v;
 v=_mm256_xor_si256(v,r1);t[175]=v;
 v=_mm256_xor_si256(v,r0);t[174]=v;
 v=_mm256_xor_si256(v,r2);t[170]=v;
 v=_mm256_xor_si256(v,r0);t[171]=v;
 v=_mm256_xor_si256(v,r1);t[169]=v;
 v=_mm256_xor_si256(v,r0);t[168]=v;
 v=_mm256_xor_si256(v,r4);t[184]=v;
 v=_mm256_xor_si256(v,r0);t[185]=v;
 v=_mm256_xor_si256(v,r1);t[187]=v;
 v=_mm256_xor_si256(v,r0);t[186]=v;
 v=_mm256_xor_si256(v,r2);t[190]=v;
 v=_mm256_xor_si256(v,r0);t[191]=v;
 v=_mm256_xor_si256(v,r1);t[189]=v;
 v=_mm256_xor_si256(v,r0);t[188]=v;
 v=_mm256_xor_si256(v,r3);t[180]=v;
 v=_mm256_xor_si256(v,r0);t[181]=v;
 v=_mm256_xor_si256(v,r1);t[183]=v;
 v=_mm256_xor_si256(v,r0);t[182]=v;
 v=_mm256_xor_si256(v,r2);t[178]=v;
 v=_mm256_xor_si256(v,r0);t[179]=v;
 v=_mm256_xor_si256(v,r1);t[177]=v;
 v=_mm256_xor_si256(v,r0);t[176]=v;
 v=_mm256_xor_si256(v,r5);t[144]=v;
 v=_mm256_xor_si256(v,r0);t[145]=v;
 v=_mm256_xor_si256(v,r1);t[147]=v;
 v=_mm256_xor_si256(v,r0);t[146]=v;
 v=_mm256_xor_si256(v,r2);t[150]=v;
 v=_mm256_xor_si256(v,r0);t[151]=v;
 v=_mm256_xor_si256(v,r1);t[149]=v;
 v=_mm256_xor_si256(v,r0);t[148]=v;
 v=_mm256_xor_si256(v,r3);t[156]=v;
 v=_mm256_xor_si256(v,r0);t[157]=v;
 v=_mm256_xor_si256(v,r1);t[159]=v;
 v=_mm256_xor_si256(v,r0);t[158]=v;
 v=_mm256_xor_si256(v,r2);t[154]=v;
 v=_mm256_xor_si256(v,r0);t[155]=v;
 v=_mm256_xor_si256(v,r1);t[153]=v;
 v=_mm256_xor_si256(v,r0);t[152]=v;
 v=_mm256_xor_si256(v,r4);t[136]=v;
 v=_mm256_xor_si256(v,r0);t[137]=v;
 v=_mm256_xor_si256(v,r1);t[139]=v;
 v=_mm256_xor_si256(v,r0);t[138]=v;
 v=_mm256_xor_si256(v,r2);t[142]=v;
 v=_mm256_xor_si256(v,r0);t[143]=v;
 v=_mm256_xor_si256(v,r1);t[141]=v;
 v=_mm256_xor_si256(v,r0);t[140]=v;
 v=_mm256_xor_si256(v,r3);t[132]=v;
 v=_mm256_xor_si256(v,r0);t[133]=v;
 v=_mm256_xor_si256(v,r1);t[135]=v;
 v=_mm256_xor_si256(v,r0);t[134]=v;
 v=_mm256_xor_si256(v,r2);t[130]=v;
 v=_mm256_xor_si256(v,r0);t[131]=v;
 v=_mm256_xor_si256(v,r1);t[129]=v;
 v=_mm256_xor_si256(v,r0);t[128]=v;
}
void matrix_multiply(int n,const bool*A,const bool*B,bool*C){
 if(n<=0)return;
 if(n%256){for(int i=0;i<n;i++)for(int j=0;j<n;j++){bool s=0;for(int k=0;k<n;k++)s^=A[(size_t)i*n+k]&B[(size_t)k*n+j];C[(size_t)i*n+j]=s;}return;}
 const int w=n/64,groups=n/8;
 // ARM IXS: the parent stores the per-group index rows at stride n, i.e. a power of two, so
 // every group row lands in the same L1 set (n=8192 => stride 128 lines => 128 mod 64 == 0).
 // Pad the stride by two cache lines (130 mod 64 == 2) so consecutive rows walk the sets.
 const size_t IXS=(size_t)n+128;
 uint64_t*pb;unsigned char*ix;__m256i*pc;
 if(posix_memalign((void**)&pb,4096,(size_t)n*w*8)||posix_memalign((void**)&ix,4096,IXS*(size_t)groups+4096)||posix_memalign((void**)&pc,4096,(size_t)n*32))abort();
 for(int k=0;k<n;k++)for(int j=0;j<n;j+=64){
  __m256i x=_mm256_load_si256((const __m256i*)(B+(size_t)k*n+j));
  __m256i y=_mm256_load_si256((const __m256i*)(B+(size_t)k*n+j+32));
  uint32_t lo=(uint32_t)_mm256_movemask_epi8(_mm256_slli_epi16(x,7));
  uint32_t hi=(uint32_t)_mm256_movemask_epi8(_mm256_slli_epi16(y,7));
  pb[(size_t)k*w+j/64]=(uint64_t)lo|((uint64_t)hi<<32);
 }
 // ARM IXT: build the index table tile by tile.  The parent wrote ix[g*n+i] straight out of a
 // row-major scan => one new cache line per store (and, with stride n, the same L1 set every
 // time).  Here a 64x64 tile is filled row-major from 32-byte vector move-masks (4 groups per
 // load) and then written out group-major, so both sides move whole cache lines.
 { alignas(64) static unsigned char tile[64*64];   /* tile[c*64+r] 列主序 */
   for(int ib=0;ib<n;ib+=64){
     for(int gb=0;gb<groups;gb+=64){
       int ge=gb+64; if(ge>groups) ge=groups;
       for(int i=ib;i<ib+64;i++){
         const bool* Ai=A+(size_t)i*n; unsigned char* Ti=tile+(i-ib);
         for(int gg=gb;gg<ge;gg+=4){
           __m256i v=_mm256_loadu_si256((const __m256i*)(Ai+(size_t)gg*8));
           uint32_t m=(uint32_t)_mm256_movemask_epi8(_mm256_slli_epi16(v,7));
           Ti[(gg-gb+0)*64]=(unsigned char)m;
           Ti[(gg-gb+1)*64]=(unsigned char)(m>>8);
           Ti[(gg-gb+2)*64]=(unsigned char)(m>>16);
           Ti[(gg-gb+3)*64]=(unsigned char)(m>>24);
         }
       }
       for(int gg=gb;gg<ge;gg++) memcpy(ix+(size_t)gg*IXS+ib, tile+(gg-gb)*64, 64);
     }
   }
 }
 alignas(64) __m256i tab[3][256];
 const __m256i shuf=_mm256_setr_epi8(0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3);
 const __m256i bits=_mm256_set1_epi64x(0x8040201008040201ULL),one=_mm256_set1_epi8(1),zero=_mm256_setzero_si256();
 for(int jb=0;jb<w;jb+=4){
  for(int g=0;g<groups;g+=3){
   const int cnt=groups-g<3?groups-g:3;
   for(int z=0;z<cnt;z++){
    __m256i*Tz=tab[z];
    build_gray8(pb+(size_t)(g+z)*8*w+jb,w,Tz);
   }
   const unsigned char*x=ix+(size_t)g*IXS;
   if(g==0){
   if(cnt==3)apply_m<3,true>(n,pc,tab,x,IXS);
   else if(cnt==2)apply_m<2,true>(n,pc,tab,x,IXS);
   else if(cnt==1)apply_m<1,true>(n,pc,tab,x,IXS);
   } else {
   if(cnt==3)apply_m<3,false>(n,pc,tab,x,IXS);
   else if(cnt==2)apply_m<2,false>(n,pc,tab,x,IXS);
   else if(cnt==1)apply_m<1,false>(n,pc,tab,x,IXS);
   }
  }
  for(int i=0;i<n;i++){
   const uint32_t*row=(const uint32_t*)(pc+i);
   for(int t=0;t<8;t++){
    __m256i x=_mm256_shuffle_epi8(_mm256_set1_epi32(row[t]),shuf);
    x=_mm256_and_si256(_mm256_cmpeq_epi8(_mm256_and_si256(x,bits),bits),one);
    _mm256_store_si256((__m256i*)(C+(size_t)i*n+jb*64+t*32),x);
   }
  }
 }
 free(pc);free(ix);free(pb);
}

评测结果