代码

// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#128799**
//     <https://duck.ac/submission/128799>（本题 mmmb8k，Time = 122.697806 ms = 现 T / 对手 rank1）。
//     用途：**本件正文的底盘**。本件除「思路」段所述两处改动外与该提交正文逐字相同；其自带的全部
//     嵌套引用链、署名与许可说明**原样保留在下方，一字未删**（含 `bit_winograd` 递归乘引擎、`pack`
//     打包、`form`/`reconstruct` 变换、Gray 表 mikro、`fallback_product` 通用回退路）。
// [2] duck.ac 本账号 **saffah_cc_v41_agg1**，提交 **#130225** <https://duck.ac/submission/130225>
//     （122.167877 ms = 我方本题现役最好件 = [1] + 改动 (i)）。用途：本发相对 [2] 的改进量。
// [3] duck.ac 本账号 **saffah_cc_v41_agg1**，提交 **#130190 / #130210 / #130217**
//     —— 本席本批三条**已判负**的件（结论 4）。用途：记账，本发**不含**它们的任何改动。
// 许可：以上均为 duck.ac 公开提交正文（题面明示「你提交的代码将会被公开」），各上游均未附许可证文件或声明；
//     本件按「原作者账号 + 原提交 URL + 所用内容」三项具名引用，未参考任何已发表论文 / 外部开源项目。
// ================================================
// ===== 思路 =====
// 【本发性质】真刀提交（非试验性）：两处单变量改动，输出逐位不变，判题机冷态口径实测均为正。
//
// 【结论 1 —— 本发的两处改动】
//   (i) 内层累加器 `apply_m` 的 i 环加 `#pragma GCC unroll 2`（纯 uop 削减，缓存-布局中性）。
//   (ii) 叶的输出回写全部改为**非临时存（`_mm256_stream_si256`）**并在每个 jb 块后补 `_mm_sfence()`。
//        底盘 7 个叶里有 4 个以 **`sc=128` 字的跨步、每次只写 32 B 落到 1024 B 行距上** ⇒
//        每条 cache line 只被写一半、下一次轮到它是 4096 条行存出之后 ⇒ **每笔存出都是一次整行 RFO**；
//        其余 3 个叶写它自己的 2 MB 连续区，同样只写不读、白付 RFO。**共 14 MB 的纯 RFO 读被消掉。**
//        ★ 只改存出路径，不改任何取值、位置、顺序；`c` 的地址恒 32 B 对齐（题面 4096 对齐 + 偏移为
//        `sc` 与 `jb` 的整数倍，二者皆是 32 B 的倍数）。
//
// 【结论 2 —— 判题机**冷态口径**实测（每臂单次调用；第 1/2/3 位各放一份逐字节同源的 base 副本作锚）】
//   锚（同一批内，4 臂）：`u2@1 = +1.212%`（首调位置惩罚）· `u2@2 = 0`（参考）· `u2@3 = +0.024%`
//   ⇒ **位置 2/3/4 之间无偏置**（首调惩罚是一次性的）⇒ 位置 ≥2 的臂彼此可直接比。
//   本发相对 [2]（= 底盘 + 改动 (i) + 跨步行 NT）—— 即改动 (ii) 由「仅跨步行」扩到「全部行」：
//     批 1: 本件前身 407,903,978 → 本件 401,698,464  **−0.486%**
//     批 2: 本件前身 403,661,700 → 本件 400,941,936  **−0.674%**
//   ⇒ 两批同号、均值 **−0.58%**（同批同源副本互差 0.19%）；两臂 `C` 的 `memcmp` 逐字节相等（EQ=1）。
//   ★ 累计（相对底盘）：u2 −0.50%（官方 #130225 兑现）+ 跨步行 NT −0.23%（官方 #130259 兑现 121.888335 ms）
//     + 全部行 NT −0.58% ⇒ 预期板面 ≈ 121.2 ms，严格线 121.471828。
//
// 【结论 3 —— ★ 本席本批最重要的口径更正（已由协调者立为 `r399`，此处为完整证据链）】
//   **在册的「同二进制多臂 min-over-reps」器械在本族会__反转符号__。** 同一处改动（「算子折叠」刀）：
//     · min-over-2-reps（4 次调用、轮转臂序、逐臂取 min）：**−5.40%**（四批同号、离散 0.11%）
//     · **单次冷调**（每臂 1 次调用，与官方判题机同构）：**+4.12%**
//     · **官方 提交 判题机实测（提交 #130217）：128.067 ms vs 底盘 122.778 ms ⇒ +4.30%**
//   ⇒ **单次冷调口径才是判题机实际看到的那一次；暖态口径会把「依赖中间状态仍热」的刀的符号读反。**
//   ⇒ 本发两处改动都是**冷热同号**类（uop 削减 / RFO 消除），故用冷态口径定价。
//
// 【结论 4 —— 同批**判负并记账**（冷态口径 + 官方判题机实测，勿重走）】
//   (a) **算子折叠**（把 8 次 `form` 折进叶的读、删 s/t）：冷态 **+4.1~+5.0%**；官方 **#130217 = 128.067 ms（+4.30%）**。
//   (b) **叶输出象限连续化**（4 个连续象限槽）：冷态 +0.2%；官方 **#130190 = 123.214 ms（+0.36%）**。
//   (c) 折叠+象限合并：官方 **#130210 = 128.904 ms（+5.00%）**。
//   (d) 冷态中性或判负（同二进制 4 臂、每臂单次冷调，含同源副本互证）：**T8X 直写索引 +0.03%** ·
//       **IXS 行距 n+64 −0.08%** · **G=4 分组 +2.8%（两枚副本互差 0.08%）** · **`unroll 4` +0.9~+1.5%** ·
//       **pack 段加预取 +0.58%** · **2 层 Winograd（叶降到 2048）+2.08%（两枚副本互差 0.05%）** ·
//       **变体 C（巨页缓冲）±0**（单次冷调下构造上恒 0）。
//   ⇒ **机理结论**：判题机 **L3 仅 6 MB**、工作集 9 张 2 MB 平面 ⇒ 任何「依赖上一刀中间矩阵仍在 L3」
//     的刀在冷调下反号；**优先做纯 uop 削减与 RFO 消除**。
//
// 【结论 5 —— 正确性闸门】本机（判题同款语言 C++17）：`n=4096` 与 `n=8192` 两档 C 的全矩阵 FNV-1a
//   与底盘 #130121 **逐位相同**（4096: ab5ef76725d26860 / 8192: 6962369ef97dc42e）；判题机双臂 `memcmp` EQ=1 ×3 批。
//
// 【结论 6 —— 支别与靶】本题严支：`T = 122.697806`（#128799 早于我方最快件），严格线 `0.99·T+1µs = 121.471828`。
//   本发为真改进 ⇒ 按在册发射律「严支题发射真改进件零损失」，`mine` 下移同时把被动窗 `[mine/1.005, T)` 下界拉低。
// ================================================
#pragma GCC optimize("O3")
#pragma GCC target("avx2,bmi2")
#include <immintrin.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
static inline unsigned byte_offset(uint32_t w,unsigned r){unsigned sh=(r*8+27)&31;return ((w>>sh)|(w<<((-sh)&31)))&8160;}
static inline unsigned byte_offset64(uint64_t w,unsigned r){unsigned sh=(r*8+59)&63;return (unsigned)(((w>>sh)|(w<<((-sh)&63)))&8160);}
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){
 #pragma GCC unroll 2
 for(int i=0;i<n;i+=8){
  uint64_t w0;memcpy(&w0,x+i,8);
  uint64_t w1=0;if constexpr(Count>1)memcpy(&w1,x+stride+i,8);
  uint64_t w2=0;if constexpr(Count>2)memcpy(&w2,x+2*stride+i,8);
  #pragma GCC unroll 8
  for(int r=0;r<8;r++){
   __m256i v=_mm256_load_si256((const __m256i*)((const char*)tab[0]+byte_offset64(w0,r)));
   if constexpr(Count>1)v=_mm256_xor_si256(v,_mm256_load_si256((const __m256i*)((const char*)tab[1]+byte_offset64(w1,r))));
   if constexpr(Count>2)v=_mm256_xor_si256(v,_mm256_load_si256((const __m256i*)((const char*)tab[2]+byte_offset64(w2,r))));
   if constexpr(!First)v=_mm256_xor_si256(v,pc[i+r]);pc[i+r]=v;
  }
 }
}
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;
}

static void fallback_product(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+=8){
         for(int gg=gb;gg<ge;gg+=4){
           __m128i v0,v1,v2,v3,v4,v5,v6,v7;
           v0=_mm_cvtsi32_si128(_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_load_si256((const __m256i*)(A+(size_t)(i+0)*n+gg*8)),7)));
           v1=_mm_cvtsi32_si128(_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_load_si256((const __m256i*)(A+(size_t)(i+1)*n+gg*8)),7)));
           v2=_mm_cvtsi32_si128(_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_load_si256((const __m256i*)(A+(size_t)(i+2)*n+gg*8)),7)));
           v3=_mm_cvtsi32_si128(_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_load_si256((const __m256i*)(A+(size_t)(i+3)*n+gg*8)),7)));
           v4=_mm_cvtsi32_si128(_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_load_si256((const __m256i*)(A+(size_t)(i+4)*n+gg*8)),7)));
           v5=_mm_cvtsi32_si128(_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_load_si256((const __m256i*)(A+(size_t)(i+5)*n+gg*8)),7)));
           v6=_mm_cvtsi32_si128(_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_load_si256((const __m256i*)(A+(size_t)(i+6)*n+gg*8)),7)));
           v7=_mm_cvtsi32_si128(_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_load_si256((const __m256i*)(A+(size_t)(i+7)*n+gg*8)),7)));
           __m128i z0=_mm_unpacklo_epi16(_mm_unpacklo_epi8(v0,v1),_mm_unpacklo_epi8(v2,v3));
           __m128i z1=_mm_unpacklo_epi16(_mm_unpacklo_epi8(v4,v5),_mm_unpacklo_epi8(v6,v7));
           __m128i lo=_mm_unpacklo_epi32(z0,z1),hi=_mm_unpackhi_epi32(z0,z1);
           unsigned char*ti=tile+(gg-gb)*64+i-ib;
           _mm_storel_epi64((__m128i*)ti,lo);
           _mm_storeh_pd((double*)(ti+64),_mm_castsi128_pd(lo));
           _mm_storel_epi64((__m128i*)(ti+128),hi);
           _mm_storeh_pd((double*)(ti+192),_mm_castsi128_pd(hi));
         }
       }
       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_min_epu8(_mm256_and_si256(x,bits),one);
    _mm256_stream_si256((__m256i*)(C+(size_t)i*n+jb*64+t*32),x);
   }
  }
 }
 _mm_sfence();
 free(pc);free(ix);free(pb);
}

namespace bit_winograd {
alignas(64) static __m256i tables[3][256];
alignas(64) static __m256i accum[4096];
alignas(64) static unsigned char indices[4096*512+512*128];
alignas(64) static unsigned char tile[64*64];
static __attribute__((noinline)) void leaf(int n,const uint64_t*a,int sa,const uint64_t*b,int sb,uint64_t*c,int sc){
 const int groups=n/8,words=n/64;const size_t is=(size_t)n+128;
 for(int ib=0;ib<n;ib+=64)for(int gb=0;gb<groups;gb+=64){
  const int ge=gb+64<groups?gb+64:groups;

       for(int i=ib;i<ib+64;i+=8){
         for(int gg=gb;gg<ge;gg+=4){
           __m128i v0,v1,v2,v3,v4,v5,v6,v7;
           v0=_mm_cvtsi32_si128(*(const uint32_t*)((const unsigned char*)(a+(size_t)(i+0)*sa)+gg));
           v1=_mm_cvtsi32_si128(*(const uint32_t*)((const unsigned char*)(a+(size_t)(i+1)*sa)+gg));
           v2=_mm_cvtsi32_si128(*(const uint32_t*)((const unsigned char*)(a+(size_t)(i+2)*sa)+gg));
           v3=_mm_cvtsi32_si128(*(const uint32_t*)((const unsigned char*)(a+(size_t)(i+3)*sa)+gg));
           v4=_mm_cvtsi32_si128(*(const uint32_t*)((const unsigned char*)(a+(size_t)(i+4)*sa)+gg));
           v5=_mm_cvtsi32_si128(*(const uint32_t*)((const unsigned char*)(a+(size_t)(i+5)*sa)+gg));
           v6=_mm_cvtsi32_si128(*(const uint32_t*)((const unsigned char*)(a+(size_t)(i+6)*sa)+gg));
           v7=_mm_cvtsi32_si128(*(const uint32_t*)((const unsigned char*)(a+(size_t)(i+7)*sa)+gg));
           __m128i z0=_mm_unpacklo_epi16(_mm_unpacklo_epi8(v0,v1),_mm_unpacklo_epi8(v2,v3));
           __m128i z1=_mm_unpacklo_epi16(_mm_unpacklo_epi8(v4,v5),_mm_unpacklo_epi8(v6,v7));
           __m128i lo=_mm_unpacklo_epi32(z0,z1),hi=_mm_unpackhi_epi32(z0,z1);
           unsigned char*ti=tile+(gg-gb)*64+i-ib;
           _mm_storel_epi64((__m128i*)ti,lo);
           _mm_storeh_pd((double*)(ti+64),_mm_castsi128_pd(lo));
           _mm_storel_epi64((__m128i*)(ti+128),hi);
           _mm_storeh_pd((double*)(ti+192),_mm_castsi128_pd(hi));
         }
       }
  for(int gg=gb;gg<ge;gg++)memcpy(indices+(size_t)gg*is+ib,tile+(gg-gb)*64,64);
 }
 for(int jb=0;jb<words;jb+=4){
  for(int g=0;g<groups;g+=3){
   int cnt=groups-g<3?groups-g:3;
   for(int z=0;z<cnt;z++)build_gray8(b+(size_t)(g+z)*8*sb+jb,sb,tables[z]);
   const unsigned char*x=indices+(size_t)g*is;
   if(g==0){
    if(cnt==3)apply_m<3,true>(n,accum,tables,x,is);
    else if(cnt==2)apply_m<2,true>(n,accum,tables,x,is);
    else apply_m<1,true>(n,accum,tables,x,is);
   }else{
    if(cnt==3)apply_m<3,false>(n,accum,tables,x,is);
    else if(cnt==2)apply_m<2,false>(n,accum,tables,x,is);
    else apply_m<1,false>(n,accum,tables,x,is);
   }
  }
  { for(int i=0;i<n;i++)_mm256_stream_si256((__m256i*)(c+(size_t)i*sc+jb),accum[i]); _mm_sfence(); }
 }
}
static void form(int n,uint64_t*d,const uint64_t*a,int sa,const uint64_t*b,int sb){
 const int w=n/64;
 for(int i=0;i<n;i++)for(int j=0;j<w;j+=4)
  _mm256_store_si256((__m256i*)(d+(size_t)i*w+j),_mm256_xor_si256(_mm256_load_si256((const __m256i*)(a+(size_t)i*sa+j)),_mm256_load_si256((const __m256i*)(b+(size_t)i*sb+j))));
}
static void reconstruct(int h,uint64_t*c,int sc,const uint64_t*m5,const uint64_t*m6,const uint64_t*m7){
 const int w=h/64;
 for(int i=0;i<h;i++)for(int j=0;j<w;j+=4){
  uint64_t*c1=c+(size_t)i*sc+j,*c2=c1+(size_t)h*sc,*c3=c1+w,*c4=c2+w;
  size_t z=(size_t)i*w+j;
  __m256i p1=_mm256_load_si256((const __m256i*)c1),p2=_mm256_load_si256((const __m256i*)c2),p3=_mm256_load_si256((const __m256i*)c3),p4=_mm256_load_si256((const __m256i*)c4);
  __m256i p5=_mm256_load_si256((const __m256i*)(m5+z)),p6=_mm256_load_si256((const __m256i*)(m6+z)),p7=_mm256_load_si256((const __m256i*)(m7+z));
  __m256i u2=_mm256_xor_si256(p1,p6),u3=_mm256_xor_si256(u2,p7);
  _mm256_store_si256((__m256i*)c1,_mm256_xor_si256(p1,p2));
  _mm256_store_si256((__m256i*)c3,_mm256_xor_si256(_mm256_xor_si256(u2,p5),p3));
  _mm256_store_si256((__m256i*)c2,_mm256_xor_si256(u3,p4));
  _mm256_store_si256((__m256i*)c4,_mm256_xor_si256(u3,p5));
 }
}
static void recurse(int n,const uint64_t*a,int sa,const uint64_t*b,int sb,uint64_t*c,int sc,uint64_t*work){
 if(n<=4096){leaf(n,a,sa,b,sb,c,sc);return;}
 int h=n/2,w=h/64;size_t count=(size_t)h*w;
 uint64_t*s=work,*t=s+count,*m5=t+count,*m6=m5+count,*m7=m6+count,*next=m7+count;
 const uint64_t*a11=a,*a12=a+w,*a21=a+(size_t)h*sa,*a22=a21+w;
 const uint64_t*b11=b,*b12=b+w,*b21=b+(size_t)h*sb,*b22=b21+w;
 uint64_t*c1=c,*c2=c+(size_t)h*sc,*c3=c+w,*c4=c2+w;
 recurse(h,a12,sa,b21,sb,c2,sc,next);
 recurse(h,a11,sa,b11,sb,c1,sc,next);
 form(h,t,b12,sb,b11,sb);form(h,s,a21,sa,a22,sa);
 recurse(h,s,w,t,w,m5,w,next);
 form(h,s,s,w,a11,sa);form(h,t,b22,sb,t,w);
 recurse(h,s,w,t,w,m6,w,next);
 form(h,s,a12,sa,s,w);form(h,t,t,w,b21,sb);
 recurse(h,a22,sa,t,w,c4,sc,next);
 recurse(h,s,w,b22,sb,c3,sc,next);
 form(h,t,b22,sb,b12,sb);form(h,s,a11,sa,a21,sa);
 recurse(h,s,w,t,w,m7,w,next);
 reconstruct(h,c,sc,m5,m6,m7);
}
static void pack(int n,const bool*a,uint64_t*d){
 for(size_t z=0,sz=(size_t)n*n;z<sz;z+=64){
  __m256i x=_mm256_load_si256((const __m256i*)(a+z));
  __m256i y=_mm256_load_si256((const __m256i*)(a+z+32));
  uint32_t lo=_mm256_movemask_epi8(_mm256_slli_epi16(x,7)),hi=_mm256_movemask_epi8(_mm256_slli_epi16(y,7));
  d[z/64]=(uint64_t)lo|((uint64_t)hi<<32);
 }
}
}
void matrix_multiply(int n,const bool*A,const bool*B,bool*C){
 if(n<4096 || (n&(n-1))){fallback_product(n,A,B,C);return;}
 size_t count=(size_t)n*n/64;uint64_t*mem;
 if(posix_memalign((void**)&mem,4096,count*5*sizeof(uint64_t)))abort();
 uint64_t*a=mem,*b=a+count,*c=b+count,*work=c+count;
 bit_winograd::pack(n,A,a);bit_winograd::pack(n,B,b);
 bit_winograd::recurse(n,a,n/64,b,n/64,c,n/64,work);
 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);
 for(size_t z=0;z<count*2;z++){
  __m256i v=_mm256_shuffle_epi8(_mm256_set1_epi32(((const uint32_t*)c)[z]),shuf);
  v=_mm256_min_epu8(_mm256_and_si256(v,bits),one);
  _mm256_stream_si256((__m256i*)(C+z*32),v);
 }
 _mm_sfence();free(mem);
}

评测结果