// ===== REFERENCES =====
// [1] duck.ac 本账号 saffah_cc_v41_agg1，提交 #103872 <https://duck.ac/submission/103872>
// 用途：**本文件的基座** —— 正文逐字节等于该提交，只在 `corr_rows` 这条路上做了下面
// `思路` 里写的一处改动（新增 `corr_rows64` 并把 `corr_rus` 跳到它）。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 #103649 <https://duck.ac/submission/103649>
// ：基座的引擎世代来源（nibble 校正表 + `FIRST` 首遍直接写）。
// [3] /home/yjp/duck.ac/BRIEF.md §2.18.761（笔记里的相位表是某一代的快照，动手前必须重测）、
// §2.18.741（"加速"先验 checksum 再看秒表）、§2.18.766（全 L1 对照臂定"是不是访存受限"）、
// §2.18.713（删 uop 的收益远小于加 uop 的代价 ⇒ 收益要按指令条数实测定价）。
// ======================
// ===== 思路 =====
// 【本发的唯一改动】**`corr_rows` 行循环的地址算术重写**（`corr_rows64`，仅用于 h=512 叶子）。
// 其余一字未改：同一张 nibble 表、同一套表构造、同一累加顺序、同一 `FIRST` 语义。
//
// 1) 相位账**重测**（判题机 probe，本代基座）：mikro 1170.1 M / cmb 64.4 M / **corr 58.0 M**
// （其中 **表构造 4.44 M、行更新 53.6 M**）/ L2blk 62.3 M / build 53.8 M / L1blk 40.7 M，
// 总 1449.4 M cycles。★ 这与笔记里"corr 63.9 M 其中表构造 31.0 M"**不是同一代** ——
// 那张表量的是**字节表**基座（`NB=4`、255 步递推），本基座已换成对手的 **nibble 表**
// （`NB=16`、15 步递推）⇒ **表构造掉了 7 倍、行更新翻了一倍**（§2.18.761 的现场命中）。
//
// 2) `objdump`（gcc 15，同一份 C）：行循环 **117 条指令/行**，其中向量只有 **34 条**
// （32 条查表 `vpxor` + 2 条 store）⇒ **83 条（71%）全是标量地址算术**：
// 每个分量 `movzbl` 取 A1 字节 → `mov/shr/and/add` 取 nibble → `movzbl/shl $6` 缩放，
// 16 个分量共 ~80 条。判题机 38.2 cycle/行 ⇒ **3.06 IPC ⇒ 发射受限**，所以**减指令就是减时间**。
// 重写：把该行 8 个 A1 字节**一次**读成 `uint64`，nibble 用立即数移位取，`<<6` 缩放。
//
// 3) **判题机单变量 A/B（`tools/probe.py`，gcc 9.3，同机同数据，四条臂）**：
// arm0 出厂 `corr_rows` 387 259 cyc / `corr_rus(512)` chk=8a0673914722e885
// arm1 bextr 版 159 169 chk 同上（逐位相同）
// **arm2 本发采用（移位版） 142 426 ⇒ −63.2%** chk 同上（逐位相同）
// arm3 消融（地址不含行信息） 121 139 ← 该循环的地板 chk 不同（答案是错的）
// arm4 出厂 `corr_rus` 原文 387 213 ← 与 arm0 只差 0.01%，确认 arm0 是忠实基线
// ⇒ 留在地板之上的余量只剩 21 289 cyc（占出厂 5.5%）⇒ **这条路上已经没什么可拿的了**。
//
// 4) **预期**：行更新 53.6 M −63% ≈ **−34 M cycles ≈ −9.4 ms**（远大于缺口 3.70 ms）。
// 保守按"只有一半兑现"算也是 −4.7 ms，仍 > 缺口。
// ⚠ 本机（gcc 15）同件读数：`corr_rus(512)` 277 191 → 91 509 cyc/call（−67%）⇒ 与判题机同号。
//
// 【闸门（§2.18.741）】本地 n=4096 全 16 MiB 输出 **`chk=7c95a2cbe108fb83`**，
// 与基座 #103872 逐位相同 ⇒ 语义未变（同 `dd` 出第二 hash 复核）。
// ================
#pragma GCC optimize("O3")
/* mmmc_k1: int8 GEMM C = A*B mod 256, EXACT, AVX2.
Split A = A0 + 128*A1 (A0 = A & 0x7F unsigned, A1 = top bit of each byte).
term1 = sum_k A0[i][k]*B[k][j] -> vpmaddubsw, no saturation (127*128*2 < 32768)
term2 = 128*(A1 . Bpar) mod 256 -> GF(2) matmul, 64 bits/word (Bpar = B&1)
Layout (lanes = columns): accum lane m is column j0+m.
x = vpbroadcastw of the 2-byte pair A0[i][2p..2p+1]
y = 32B load from BI[p] at 2*j0 ; BI[p][2j]=B[2p][j], BI[p][2j+1]=B[2p+1][j]
*/
#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing")
#include <immintrin.h>
#include <xmmintrin.h>
#include <stdint.h>
#include <string.h>
#include <stdio.h>
#define AVX2 __attribute__((target("avx2")))
#define NMAX 4096
/* == mmmpad_fleet ARM: SCRATCH ROW-STRIDE PAD ==
A0b and PBb are PRIVATE scratch, so their row stride is not semantic -- but it is `n`,
i.e. 4096 B at n=4096, which is EXACTLY the L1 way-period (64 sets x 64 B). Every row of
both buffers then maps its line j into set j, on top of C's rows (also `n`) and the mikro's
two-row window: 6+ streams share one set out of 8 ways. LDA/LDB pad the two scratch
strides. The cell (row i, col j) is still the same value -- only WHERE it lives changes.
The mikro takes the scratch stride as an argument instead of deriving `A0+n`. */
#ifndef PADA
#define PADA 192
#endif
#define LDA ((int)(NMAX + PADA))
#ifndef PADB
#define PADB 128
#endif
#define LDB ((int)(NMAX + PADB))
/* mc4b_: force every hot array's 4 KiB phase to a CHOSEN value instead of letting the
compiler's layout pick it. On the base build Pbb/Bpb/A1b/A0b/PBb all landed at
mod4096 = mod65536 = 832 (L1 set 13) -- the five arrays the mikro touches together are
mutually congruent at BOTH the 4 KiB and the 64 KiB level, and the judge's C is 0.
alignas(4096) on the wrapper makes data phase = pad mod 4096, independent of gcc version,
so this also removes "layout lottery" as a variable from every later experiment. */
#define MC4B_ARR(NAME, TYPE, COUNT, PAD) \
struct alignas(4096) NAME##_wrap_ { unsigned char _pad[PAD]; TYPE v[COUNT]; }; \
static NAME##_wrap_ NAME##_obj_; \
static TYPE *const NAME = NAME##_obj_.v;
MC4B_ARR(A0b, int8_t, (size_t)NMAX*LDA, 3072)
MC4B_ARR(A1b, uint64_t, NMAX*NMAX/8, 512)
MC4B_ARR(Bpb, uint64_t, NMAX*NMAX/8, 1024)
MC4B_ARR(Pbb, uint64_t, NMAX*NMAX/8, 1536)
MC4B_ARR(PBb, uint8_t, (size_t)NMAX*LDB, 3584)
static void generic_mm(int n, const int8_t*A, const int8_t*B, int8_t*C){
for (int i=0;i<n;i++) for (int j=0;j<n;j++){
int s=0; for(int k=0;k<n;k++) s += (int)A[(size_t)i*n+k]*(int)B[(size_t)k*n+j];
C[(size_t)i*n+j]=(int8_t)s;
}
}
AVX2 static inline __m256i bcast16(const int8_t*p){
__m256i v; __asm__("vpbroadcastw %1, %0" : "=x"(v) : "m"(*(const short*)p)); return v;
}
AVX2 static inline __m256i packlo8(__m256i a, __m256i b){
const __m256i m=_mm256_set1_epi16(0x00FF);
return _mm256_permute4x64_epi64(
_mm256_packus_epi16(_mm256_and_si256(a,m), _mm256_and_si256(b,m)), 0xD8);
}
AVX2 static void build_A0(int n, const int8_t*A){
const __m256i m=_mm256_set1_epi8(0x7F);
size_t tot=(size_t)n*n;
for (size_t i=0;i<tot;i+=32)
_mm256_store_si256((__m256i*)(A0b+i),
_mm256_and_si256(_mm256_load_si256((const __m256i*)(A+i)), m));
}
AVX2 static void build_A1bits(int n, const int8_t*A){
int W=n/64;
for (int i=0;i<n;i++){
const int8_t*row=A+(size_t)i*n; uint64_t*w=A1b+(size_t)i*W;
for (int k=0;k<n;k+=64){
uint32_t lo=(uint32_t)_mm256_movemask_epi8(_mm256_load_si256((const __m256i*)(row+k)));
uint32_t hi=(uint32_t)_mm256_movemask_epi8(_mm256_load_si256((const __m256i*)(row+k+32)));
w[k>>6]=(uint64_t)lo|((uint64_t)hi<<32);
}
}
}
AVX2 static void build_Bpbits(int n, const int8_t*B){
const __m256i one=_mm256_set1_epi8(1);
int W=n/64;
for (int k=0;k<n;k++){
const int8_t*row=B+(size_t)k*n; uint64_t*w=Bpb+(size_t)k*W;
for (int j=0;j<n;j+=64){
__m256i a=_mm256_slli_epi16(_mm256_and_si256(_mm256_load_si256((const __m256i*)(row+j)),one),7);
__m256i b=_mm256_slli_epi16(_mm256_and_si256(_mm256_load_si256((const __m256i*)(row+j+32)),one),7);
uint32_t lo=(uint32_t)_mm256_movemask_epi8(a);
uint32_t hi=(uint32_t)_mm256_movemask_epi8(b);
w[j>>6]=(uint64_t)lo|((uint64_t)hi<<32);
}
}
}
/* P[i] = XOR of Bp[k] over k with A1[i][k] set. NY = n/256 ymm per row. */
AVX2 static void corr_bits(int n){
int W=n/64, NY=W>>2;
for (int i=0;i<n;i++){
__m256i acc[16];
for(int t=0;t<NY;t++) acc[t]=_mm256_setzero_si256();
const uint64_t*row=A1b+(size_t)i*W;
for(int w=0;w<W;w++){
uint64_t b=row[w];
while(b){
int t=__builtin_ctzll(b); b&=b-1;
const uint64_t*br=Bpb+(size_t)(w*64+t)*W;
for(int q=0;q<NY;q++)
acc[q]=_mm256_xor_si256(acc[q],_mm256_load_si256((const __m256i*)(br+4*q)));
}
}
uint64_t*o=Pbb+(size_t)i*W;
for(int q=0;q<NY;q++) _mm256_store_si256((__m256i*)(o+4*q),acc[q]);
}
}
static uint64_t A1T[NMAX*NMAX/8] __attribute__((aligned(64)));
AVX2 static void transpose64(uint64_t *a){
int j,k; uint64_t m,t;
for (j=32,m=0xFFFFFFFF00000000ULL; j; j>>=1, m^=m>>j)
for (k=0;k<64;k=(k+j+1)&~j){
t=(a[k]^(a[k+j]<<j))&m;
a[k]^=t; a[k+j]^=(t>>j);
}
}
AVX2 static void build_A1T(int n){
int W=n/64;
for (int kb=0; kb<n; kb+=64)
for (int ib=0; ib<n; ib+=64){
uint64_t blk[64];
for (int i=0;i<64;i++) blk[i]=A1b[(size_t)(ib+i)*W+(kb>>6)];
transpose64(blk);
for (int k=0;k<64;k++) A1T[(size_t)(kb+k)*W+(ib>>6)]=blk[k];
}
}
/* P[i][j] = XOR over k with A1[i][k] set of Bp[k][j].
Per-output-row bit scan (dense 64-bit words -> predictable), K-BLOCKED so the
Bp slice stays in L2. P accumulated in memory across k-blocks. */
AVX2 static void corr_pass3(int n){
int W=n/64, NY=W>>2;
memset(Pbb,0,(size_t)n*W*8);
const int KB=256;
for (int kb=0; kb<n; kb+=KB){
int w0=kb>>6, w1=w0+(KB>>6);
for (int i=0;i<n;i++){
__m256i acc[16];
for (int q=0;q<NY;q++) acc[q]=_mm256_setzero_si256();
const uint64_t*row=A1b+(size_t)i*W;
for (int w=w0;w<w1;w++){
uint64_t b=row[w];
while(b){
int t=__builtin_ctzll(b); b&=b-1;
const uint64_t*br=Bpb+(size_t)(w*64+t)*W;
for (int q=0;q<NY;q++) acc[q]=_mm256_xor_si256(acc[q],_mm256_load_si256((const __m256i*)(br+4*q)));
}
}
uint64_t*o=Pbb+(size_t)i*W;
for (int q=0;q<NY;q++){
__m256i*po=(__m256i*)(o+4*q);
_mm256_store_si256(po,_mm256_xor_si256(_mm256_load_si256((const __m256i*)po),acc[q]));
}
}
}
}
/* specialized for n=4096 (W=64, NY=16): fully unrolled XOR loops */
/* corr16(): fully hand-written per-row GF(2) accumulate. Bit-identical output. */
#define AVX2BMI __attribute__((target("avx2,bmi")))
AVX2BMI static void corr16(void){
const int n=4096, W=64;
memset(Pbb,0,(size_t)n*W*8);
const int KB=64;
for (int kb=0; kb<n; kb+=KB){
int w0=kb>>6;
const char *bp0=(const char*)Bpb+(size_t)w0*32768;
const char *bp1=bp0; (void)bp1;
for (int i=0;i<n;i++){
const uint64_t*row=A1b+(size_t)i*W+w0;
uint64_t b0=row[0], b1=0;
uint64_t *o=Pbb+(size_t)i*W;
asm volatile(
"vpxor %%xmm0,%%xmm0,%%xmm0\n\t"
"vpxor %%xmm1,%%xmm1,%%xmm1\n\t"
"vpxor %%xmm2,%%xmm2,%%xmm2\n\t"
"vpxor %%xmm3,%%xmm3,%%xmm3\n\t"
"vpxor %%xmm4,%%xmm4,%%xmm4\n\t"
"vpxor %%xmm5,%%xmm5,%%xmm5\n\t"
"vpxor %%xmm6,%%xmm6,%%xmm6\n\t"
"vpxor %%xmm7,%%xmm7,%%xmm7\n\t"
"vpxor %%xmm8,%%xmm8,%%xmm8\n\t"
"vpxor %%xmm9,%%xmm9,%%xmm9\n\t"
"vpxor %%xmm10,%%xmm10,%%xmm10\n\t"
"vpxor %%xmm11,%%xmm11,%%xmm11\n\t"
"vpxor %%xmm12,%%xmm12,%%xmm12\n\t"
"vpxor %%xmm13,%%xmm13,%%xmm13\n\t"
"vpxor %%xmm14,%%xmm14,%%xmm14\n\t"
"vpxor %%xmm15,%%xmm15,%%xmm15\n\t"
"testq %[b0], %[b0]\n\t"
"jz 3%=f\n\t"
"1%=:\n\t"
"tzcntq %[b0], %%r11\n\t"
"shlq $9, %%r11\n\t"
"addq %[bp0], %%r11\n\t"
"vpxor 0(%%r11), %%ymm0, %%ymm0\n\t"
"vpxor 32(%%r11), %%ymm1, %%ymm1\n\t"
"vpxor 64(%%r11), %%ymm2, %%ymm2\n\t"
"vpxor 96(%%r11), %%ymm3, %%ymm3\n\t"
"vpxor 128(%%r11), %%ymm4, %%ymm4\n\t"
"vpxor 160(%%r11), %%ymm5, %%ymm5\n\t"
"vpxor 192(%%r11), %%ymm6, %%ymm6\n\t"
"vpxor 224(%%r11), %%ymm7, %%ymm7\n\t"
"vpxor 256(%%r11), %%ymm8, %%ymm8\n\t"
"vpxor 288(%%r11), %%ymm9, %%ymm9\n\t"
"vpxor 320(%%r11), %%ymm10, %%ymm10\n\t"
"vpxor 352(%%r11), %%ymm11, %%ymm11\n\t"
"vpxor 384(%%r11), %%ymm12, %%ymm12\n\t"
"vpxor 416(%%r11), %%ymm13, %%ymm13\n\t"
"vpxor 448(%%r11), %%ymm14, %%ymm14\n\t"
"vpxor 480(%%r11), %%ymm15, %%ymm15\n\t"
"blsrq %[b0], %[b0]\n\t"
"jnz 1%=b\n\t"
"3%=:\n\t"
"testq %[b1], %[b1]\n\t"
"jz 4%=f\n\t"
"2%=:\n\t"
"tzcntq %[b1], %%r11\n\t"
"shlq $9, %%r11\n\t"
"addq %[bp1], %%r11\n\t"
"vpxor 0(%%r11), %%ymm0, %%ymm0\n\t"
"vpxor 32(%%r11), %%ymm1, %%ymm1\n\t"
"vpxor 64(%%r11), %%ymm2, %%ymm2\n\t"
"vpxor 96(%%r11), %%ymm3, %%ymm3\n\t"
"vpxor 128(%%r11), %%ymm4, %%ymm4\n\t"
"vpxor 160(%%r11), %%ymm5, %%ymm5\n\t"
"vpxor 192(%%r11), %%ymm6, %%ymm6\n\t"
"vpxor 224(%%r11), %%ymm7, %%ymm7\n\t"
"vpxor 256(%%r11), %%ymm8, %%ymm8\n\t"
"vpxor 288(%%r11), %%ymm9, %%ymm9\n\t"
"vpxor 320(%%r11), %%ymm10, %%ymm10\n\t"
"vpxor 352(%%r11), %%ymm11, %%ymm11\n\t"
"vpxor 384(%%r11), %%ymm12, %%ymm12\n\t"
"vpxor 416(%%r11), %%ymm13, %%ymm13\n\t"
"vpxor 448(%%r11), %%ymm14, %%ymm14\n\t"
"vpxor 480(%%r11), %%ymm15, %%ymm15\n\t"
"blsrq %[b1], %[b1]\n\t"
"jnz 2%=b\n\t"
"4%=:\n\t"
"vpxor 0(%[o]), %%ymm0, %%ymm0\n\t"
"vmovdqu %%ymm0, 0(%[o])\n\t"
"vpxor 32(%[o]), %%ymm1, %%ymm1\n\t"
"vmovdqu %%ymm1, 32(%[o])\n\t"
"vpxor 64(%[o]), %%ymm2, %%ymm2\n\t"
"vmovdqu %%ymm2, 64(%[o])\n\t"
"vpxor 96(%[o]), %%ymm3, %%ymm3\n\t"
"vmovdqu %%ymm3, 96(%[o])\n\t"
"vpxor 128(%[o]), %%ymm4, %%ymm4\n\t"
"vmovdqu %%ymm4, 128(%[o])\n\t"
"vpxor 160(%[o]), %%ymm5, %%ymm5\n\t"
"vmovdqu %%ymm5, 160(%[o])\n\t"
"vpxor 192(%[o]), %%ymm6, %%ymm6\n\t"
"vmovdqu %%ymm6, 192(%[o])\n\t"
"vpxor 224(%[o]), %%ymm7, %%ymm7\n\t"
"vmovdqu %%ymm7, 224(%[o])\n\t"
"vpxor 256(%[o]), %%ymm8, %%ymm8\n\t"
"vmovdqu %%ymm8, 256(%[o])\n\t"
"vpxor 288(%[o]), %%ymm9, %%ymm9\n\t"
"vmovdqu %%ymm9, 288(%[o])\n\t"
"vpxor 320(%[o]), %%ymm10, %%ymm10\n\t"
"vmovdqu %%ymm10, 320(%[o])\n\t"
"vpxor 352(%[o]), %%ymm11, %%ymm11\n\t"
"vmovdqu %%ymm11, 352(%[o])\n\t"
"vpxor 384(%[o]), %%ymm12, %%ymm12\n\t"
"vmovdqu %%ymm12, 384(%[o])\n\t"
"vpxor 416(%[o]), %%ymm13, %%ymm13\n\t"
"vmovdqu %%ymm13, 416(%[o])\n\t"
"vpxor 448(%[o]), %%ymm14, %%ymm14\n\t"
"vmovdqu %%ymm14, 448(%[o])\n\t"
"vpxor 480(%[o]), %%ymm15, %%ymm15\n\t"
"vmovdqu %%ymm15, 480(%[o])\n\t"
: [b0]"+r"(b0), [b1]"+r"(b1)
: [bp0]"r"(bp0), [bp1]"r"(bp1), [o]"r"(o)
: "r11","cc","memory","ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15");
}
}
}
static void expand_bits(int n){
static uint8_t T[256*8]; static int ti=0;
if(!ti){ for(int v=0;v<256;v++) for(int b=0;b<8;b++) T[v*8+b]=((v>>b)&1)?0x80:0x00; ti=1; }
int W=n/64;
for(int i=0;i<n;i++){
const uint64_t*w=Pbb+(size_t)i*W; uint8_t*o=PBb+(size_t)i*LDB;
for(int q=0;q<W;q++){
uint64_t v=w[q];
for(int s=0;s<8;s++) memcpy(o+(q*8+s)*8, T+(((uint8_t)(v>>(8*s)))*8), 8);
}
}
}
#define NIB 2
#define NJ 4
/* nopb: bit->byte expansion patterns used by mikro_u4's epilogue. MC4C_IDX duplicates
each byte of the broadcast dword eight times; MC4C_SEL is the bit-select pattern that
turns "is bit b of this mask byte set" into an all-ones byte; MC4C_MSB narrows it to
0x80 (the value the shipped PBb used to carry). */
static const int8_t MC4C_IDX[32] __attribute__((aligned(32))) = {
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};
static const int8_t MC4C_SEL[32] __attribute__((aligned(32))) = {
1,2,4,8,16,32,64,(int8_t)0x80, 1,2,4,8,16,32,64,(int8_t)0x80,
1,2,4,8,16,32,64,(int8_t)0x80, 1,2,4,8,16,32,64,(int8_t)0x80};
static const int8_t MC4C_MSB[32] __attribute__((aligned(32))) = {
(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,
(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,
(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,
(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,
(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,(int8_t)0x80,
(int8_t)0x80,(int8_t)0x80};
static const int16_t W0FF[16] __attribute__((aligned(32))) =
{0x00FF,0x00FF,0x00FF,0x00FF,0x00FF,0x00FF,0x00FF,0x00FF,
0x00FF,0x00FF,0x00FF,0x00FF,0x00FF,0x00FF,0x00FF,0x00FF};
MC4B_ARR(BI3b, int8_t, NMAX*NMAX + (NMAX/64)*1024, 2048)
AVX2 static void build_BI3(int n, const int8_t*B){
int ng=n/64;
for (int p=0;p<n/2;p++){
const int8_t *r0=B+(size_t)(2*p)*n, *r1=r0+n;
for (int g=0;g<ng;g++){
const int8_t *a=r0+64*g, *b=r1+64*g;
int8_t *o=BI3b+((size_t)g*(n/2)+p)*128;
for (int t=0;t<64;t+=32){
__m256i va=_mm256_load_si256((const __m256i*)(a+t));
__m256i vb=_mm256_load_si256((const __m256i*)(b+t));
__m256i lo=_mm256_unpacklo_epi8(va,vb), hi=_mm256_unpackhi_epi8(va,vb);
_mm256_store_si256((__m256i*)(o+2*t), _mm256_permute2x128_si256(lo,hi,0x20));
_mm256_store_si256((__m256i*)(o+2*t+32), _mm256_permute2x128_si256(lo,hi,0x31));
}
}
}
}
AVX2 static void mikro_u4(int n,const int8_t*A0,const int8_t*BI,int8_t*C,const uint8_t*PB,int jb,int lda,int ldb){
const int8_t *x0=A0;
long nn=(long)n;
const int8_t *bib=BI; const int8_t *bibend=BI+(long)(n>>3)*512;
int8_t *C0=C+jb, *C1=C0+n;
const uint8_t *PB0=PB+jb, *PB1=PB0+ldb;
asm volatile(
"vpxor %%xmm8,%%xmm8,%%xmm8\n\t"
"vpxor %%xmm9,%%xmm9,%%xmm9\n\t"
"vpxor %%xmm10,%%xmm10,%%xmm10\n\t"
"vpxor %%xmm11,%%xmm11,%%xmm11\n\t"
"vpxor %%xmm12,%%xmm12,%%xmm12\n\t"
"vpxor %%xmm13,%%xmm13,%%xmm13\n\t"
"vpxor %%xmm14,%%xmm14,%%xmm14\n\t"
"vpxor %%xmm15,%%xmm15,%%xmm15\n\t"
".p2align 5\n\t"
"1:\n\t"
"vpbroadcastw 0(%[x0]), %%ymm0\n\t"
"vpbroadcastw %c[lda](%[x0]), %%ymm1\n\t"
"vmovdqa 0(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm8, %%ymm8\n\t"
"vpaddw %%ymm6, %%ymm12, %%ymm12\n\t"
"vmovdqa 32(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm9, %%ymm9\n\t"
"vpaddw %%ymm6, %%ymm13, %%ymm13\n\t"
"vmovdqa 64(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm10, %%ymm10\n\t"
"vpaddw %%ymm6, %%ymm14, %%ymm14\n\t"
"vmovdqa 96(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm11, %%ymm11\n\t"
"vpaddw %%ymm6, %%ymm15, %%ymm15\n\t"
"vpbroadcastw 2(%[x0]), %%ymm0\n\t"
"vpbroadcastw %c[lda]+2(%[x0]), %%ymm1\n\t"
"vmovdqa 128(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm8, %%ymm8\n\t"
"vpaddw %%ymm6, %%ymm12, %%ymm12\n\t"
"vmovdqa 160(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm9, %%ymm9\n\t"
"vpaddw %%ymm6, %%ymm13, %%ymm13\n\t"
"vmovdqa 192(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm10, %%ymm10\n\t"
"vpaddw %%ymm6, %%ymm14, %%ymm14\n\t"
"vmovdqa 224(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm11, %%ymm11\n\t"
"vpaddw %%ymm6, %%ymm15, %%ymm15\n\t"
"vpbroadcastw 4(%[x0]), %%ymm0\n\t"
"vpbroadcastw %c[lda]+4(%[x0]), %%ymm1\n\t"
"vmovdqa 256(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm8, %%ymm8\n\t"
"vpaddw %%ymm6, %%ymm12, %%ymm12\n\t"
"vmovdqa 288(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm9, %%ymm9\n\t"
"vpaddw %%ymm6, %%ymm13, %%ymm13\n\t"
"vmovdqa 320(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm10, %%ymm10\n\t"
"vpaddw %%ymm6, %%ymm14, %%ymm14\n\t"
"vmovdqa 352(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm11, %%ymm11\n\t"
"vpaddw %%ymm6, %%ymm15, %%ymm15\n\t"
"vpbroadcastw 6(%[x0]), %%ymm0\n\t"
"vpbroadcastw %c[lda]+6(%[x0]), %%ymm1\n\t"
"vmovdqa 384(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm8, %%ymm8\n\t"
"vpaddw %%ymm6, %%ymm12, %%ymm12\n\t"
"vmovdqa 416(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm9, %%ymm9\n\t"
"vpaddw %%ymm6, %%ymm13, %%ymm13\n\t"
"vmovdqa 448(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm10, %%ymm10\n\t"
"vpaddw %%ymm6, %%ymm14, %%ymm14\n\t"
"vmovdqa 480(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm11, %%ymm11\n\t"
"vpaddw %%ymm6, %%ymm15, %%ymm15\n\t"
"addq $8, %[x0]\n\t"
"addq $512, %[bib]\n\t"
"cmpq %[bibend], %[bib]\n\t"
"jb 1b\n\t"
"vpand %[mask], %%ymm8, %%ymm2\n\t"
"vpand %[mask], %%ymm9, %%ymm3\n\t"
"vpackuswb %%ymm3, %%ymm2, %%ymm2\n\t"
"vpermq $0xD8, %%ymm2, %%ymm2\n\t"
"vpxor 0(%[PB0]), %%ymm2, %%ymm2\n\t"
"vmovntdq %%ymm2, 0(%[C0])\n\t"
"vpand %[mask], %%ymm10, %%ymm2\n\t"
"vpand %[mask], %%ymm11, %%ymm3\n\t"
"vpackuswb %%ymm3, %%ymm2, %%ymm2\n\t"
"vpermq $0xD8, %%ymm2, %%ymm2\n\t"
"vpxor 32(%[PB0]), %%ymm2, %%ymm2\n\t"
"vmovntdq %%ymm2, 32(%[C0])\n\t"
"vpand %[mask], %%ymm12, %%ymm2\n\t"
"vpand %[mask], %%ymm13, %%ymm3\n\t"
"vpackuswb %%ymm3, %%ymm2, %%ymm2\n\t"
"vpermq $0xD8, %%ymm2, %%ymm2\n\t"
"vpxor 0(%[PB1]), %%ymm2, %%ymm2\n\t"
"vmovntdq %%ymm2, 0(%[C1])\n\t"
"vpand %[mask], %%ymm14, %%ymm2\n\t"
"vpand %[mask], %%ymm15, %%ymm3\n\t"
"vpackuswb %%ymm3, %%ymm2, %%ymm2\n\t"
"vpermq $0xD8, %%ymm2, %%ymm2\n\t"
"vpxor 32(%[PB1]), %%ymm2, %%ymm2\n\t"
"vmovntdq %%ymm2, 32(%[C1])\n\t"
: [x0]"+r"(x0), [bib]"+r"(bib)
: [lda]"i"(lda), [C0]"r"(C0), [C1]"r"(C1), [PB0]"r"(PB0), [PB1]"r"(PB1), [nn]"r"(nn), [mask]"m"(W0FF), [bibend]"r"(bibend)
: "ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15","cc","memory");
}
AVX2 static void mikro_u4_pb(int n,const int8_t*A0,const int8_t*BI,int8_t*C,const uint8_t*PB,int jb,int lda,int ldb){
const int8_t *x0=A0;
long nn=(long)n;
const int8_t *bib=BI; const int8_t *bibend=BI+(long)(n>>3)*512;
int8_t *C0=C+jb, *C1=C0+n;
const uint8_t *PB0=PB, *PB1=PB+ldb; /* PB = packed Pbb row ptr, ldb = row stride in bytes */
asm volatile(
"vpxor %%xmm8,%%xmm8,%%xmm8\n\t"
"vpxor %%xmm9,%%xmm9,%%xmm9\n\t"
"vpxor %%xmm10,%%xmm10,%%xmm10\n\t"
"vpxor %%xmm11,%%xmm11,%%xmm11\n\t"
"vpxor %%xmm12,%%xmm12,%%xmm12\n\t"
"vpxor %%xmm13,%%xmm13,%%xmm13\n\t"
"vpxor %%xmm14,%%xmm14,%%xmm14\n\t"
"vpxor %%xmm15,%%xmm15,%%xmm15\n\t"
".p2align 5\n\t"
"1:\n\t"
"vpbroadcastw 0(%[x0]), %%ymm0\n\t"
"vpbroadcastw %c[lda](%[x0]), %%ymm1\n\t"
"vmovdqa 0(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm8, %%ymm8\n\t"
"vpaddw %%ymm6, %%ymm12, %%ymm12\n\t"
"vmovdqa 32(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm9, %%ymm9\n\t"
"vpaddw %%ymm6, %%ymm13, %%ymm13\n\t"
"vmovdqa 64(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm10, %%ymm10\n\t"
"vpaddw %%ymm6, %%ymm14, %%ymm14\n\t"
"vmovdqa 96(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm11, %%ymm11\n\t"
"vpaddw %%ymm6, %%ymm15, %%ymm15\n\t"
"vpbroadcastw 2(%[x0]), %%ymm0\n\t"
"vpbroadcastw %c[lda]+2(%[x0]), %%ymm1\n\t"
"vmovdqa 128(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm8, %%ymm8\n\t"
"vpaddw %%ymm6, %%ymm12, %%ymm12\n\t"
"vmovdqa 160(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm9, %%ymm9\n\t"
"vpaddw %%ymm6, %%ymm13, %%ymm13\n\t"
"vmovdqa 192(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm10, %%ymm10\n\t"
"vpaddw %%ymm6, %%ymm14, %%ymm14\n\t"
"vmovdqa 224(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm11, %%ymm11\n\t"
"vpaddw %%ymm6, %%ymm15, %%ymm15\n\t"
"vpbroadcastw 4(%[x0]), %%ymm0\n\t"
"vpbroadcastw %c[lda]+4(%[x0]), %%ymm1\n\t"
"vmovdqa 256(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm8, %%ymm8\n\t"
"vpaddw %%ymm6, %%ymm12, %%ymm12\n\t"
"vmovdqa 288(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm9, %%ymm9\n\t"
"vpaddw %%ymm6, %%ymm13, %%ymm13\n\t"
"vmovdqa 320(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm10, %%ymm10\n\t"
"vpaddw %%ymm6, %%ymm14, %%ymm14\n\t"
"vmovdqa 352(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm11, %%ymm11\n\t"
"vpaddw %%ymm6, %%ymm15, %%ymm15\n\t"
"vpbroadcastw 6(%[x0]), %%ymm0\n\t"
"vpbroadcastw %c[lda]+6(%[x0]), %%ymm1\n\t"
"vmovdqa 384(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm8, %%ymm8\n\t"
"vpaddw %%ymm6, %%ymm12, %%ymm12\n\t"
"vmovdqa 416(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm9, %%ymm9\n\t"
"vpaddw %%ymm6, %%ymm13, %%ymm13\n\t"
"vmovdqa 448(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm10, %%ymm10\n\t"
"vpaddw %%ymm6, %%ymm14, %%ymm14\n\t"
"vmovdqa 480(%[bib]), %%ymm4\n\t"
"vpmaddubsw %%ymm4, %%ymm0, %%ymm5\n\t"
"vpmaddubsw %%ymm4, %%ymm1, %%ymm6\n\t"
"vpaddw %%ymm5, %%ymm11, %%ymm11\n\t"
"vpaddw %%ymm6, %%ymm15, %%ymm15\n\t"
"addq $8, %[x0]\n\t"
"addq $512, %[bib]\n\t"
"cmpq %[bibend], %[bib]\n\t"
"jb 1b\n\t"
"vmovdqa %[IDX], %%ymm0\n\t"
"vmovdqa %[SEL], %%ymm1\n\t"
"vmovdqa %[MSB], %%ymm5\n\t"
"vpand %[mask], %%ymm8, %%ymm2\n\t"
"vpand %[mask], %%ymm9, %%ymm3\n\t"
"vpackuswb %%ymm3, %%ymm2, %%ymm2\n\t"
"vpermq $0xD8, %%ymm2, %%ymm2\n\t"
"vpbroadcastd 0(%[PB0]), %%ymm4\n\t"
"vpshufb %%ymm0, %%ymm4, %%ymm4\n\t"
"vpand %%ymm1, %%ymm4, %%ymm4\n\t"
"vpcmpeqb %%ymm1, %%ymm4, %%ymm4\n\t"
"vpand %%ymm5, %%ymm4, %%ymm4\n\t"
"vpxor %%ymm4, %%ymm2, %%ymm2\n\t"
"vmovntdq %%ymm2, 0(%[C0])\n\t"
"vpand %[mask], %%ymm10, %%ymm2\n\t"
"vpand %[mask], %%ymm11, %%ymm3\n\t"
"vpackuswb %%ymm3, %%ymm2, %%ymm2\n\t"
"vpermq $0xD8, %%ymm2, %%ymm2\n\t"
"vpbroadcastd 4(%[PB0]), %%ymm4\n\t"
"vpshufb %%ymm0, %%ymm4, %%ymm4\n\t"
"vpand %%ymm1, %%ymm4, %%ymm4\n\t"
"vpcmpeqb %%ymm1, %%ymm4, %%ymm4\n\t"
"vpand %%ymm5, %%ymm4, %%ymm4\n\t"
"vpxor %%ymm4, %%ymm2, %%ymm2\n\t"
"vmovntdq %%ymm2, 32(%[C0])\n\t"
"vpand %[mask], %%ymm12, %%ymm2\n\t"
"vpand %[mask], %%ymm13, %%ymm3\n\t"
"vpackuswb %%ymm3, %%ymm2, %%ymm2\n\t"
"vpermq $0xD8, %%ymm2, %%ymm2\n\t"
"vpbroadcastd 0(%[PB1]), %%ymm4\n\t"
"vpshufb %%ymm0, %%ymm4, %%ymm4\n\t"
"vpand %%ymm1, %%ymm4, %%ymm4\n\t"
"vpcmpeqb %%ymm1, %%ymm4, %%ymm4\n\t"
"vpand %%ymm5, %%ymm4, %%ymm4\n\t"
"vpxor %%ymm4, %%ymm2, %%ymm2\n\t"
"vmovntdq %%ymm2, 0(%[C1])\n\t"
"vpand %[mask], %%ymm14, %%ymm2\n\t"
"vpand %[mask], %%ymm15, %%ymm3\n\t"
"vpackuswb %%ymm3, %%ymm2, %%ymm2\n\t"
"vpermq $0xD8, %%ymm2, %%ymm2\n\t"
"vpbroadcastd 4(%[PB1]), %%ymm4\n\t"
"vpshufb %%ymm0, %%ymm4, %%ymm4\n\t"
"vpand %%ymm1, %%ymm4, %%ymm4\n\t"
"vpcmpeqb %%ymm1, %%ymm4, %%ymm4\n\t"
"vpand %%ymm5, %%ymm4, %%ymm4\n\t"
"vpxor %%ymm4, %%ymm2, %%ymm2\n\t"
"vmovntdq %%ymm2, 32(%[C1])\n\t"
: [x0]"+r"(x0), [bib]"+r"(bib)
: [lda]"i"(lda), [C0]"r"(C0), [C1]"r"(C1), [PB0]"r"(PB0), [PB1]"r"(PB1),
[IDX]"m"(MC4C_IDX), [SEL]"m"(MC4C_SEL), [MSB]"m"(MC4C_MSB), [nn]"r"(nn), [mask]"m"(W0FF), [bibend]"r"(bibend)
: "ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15","cc","memory");
}
/* FUSED BUILDERS (ported from mmmc2k, pure-n): one pass over A, one over B */
AVX2 static void build_A0A1(int n, const int8_t*A){
const __m256i m=_mm256_set1_epi8(0x7F);
int W=n/64;
for (int i=0;i<n;i++){
const int8_t*row=A+(size_t)i*n;
int8_t*dst=A0b+(size_t)i*LDA;
uint64_t*w1=A1b+(size_t)i*W;
for (int k=0;k<n;k+=64){
__m256i v0=_mm256_load_si256((const __m256i*)(row+k));
__m256i v1=_mm256_load_si256((const __m256i*)(row+k+32));
_mm256_store_si256((__m256i*)(dst+k), _mm256_and_si256(v0,m));
_mm256_store_si256((__m256i*)(dst+k+32), _mm256_and_si256(v1,m));
w1[k>>6]=(uint64_t)(uint32_t)_mm256_movemask_epi8(v0)
|((uint64_t)(uint32_t)_mm256_movemask_epi8(v1)<<32);
}
}
}
AVX2 static void build_BI3Bp(int n, const int8_t*B){
const __m256i one=_mm256_set1_epi8(1);
int ng=n/64, W=n/64;
for (int p=0;p<n/2;p++){
const int8_t *r0=B+(size_t)(2*p)*n, *r1=r0+n;
uint64_t *w0p=Bpb+(size_t)(2*p)*W, *w1p=Bpb+(size_t)(2*p+1)*W;
for (int g=0;g<ng;g++){
const int8_t *a=r0+64*g, *b=r1+64*g;
int8_t *o=BI3b+((size_t)g*(n/2)+p)*128;
for (int t=0;t<64;t+=32){
__m256i va=_mm256_load_si256((const __m256i*)(a+t));
__m256i vb=_mm256_load_si256((const __m256i*)(b+t));
__m256i lo=_mm256_unpacklo_epi8(va,vb), hi=_mm256_unpackhi_epi8(va,vb);
_mm256_store_si256((__m256i*)(o+2*t), _mm256_permute2x128_si256(lo,hi,0x20));
_mm256_store_si256((__m256i*)(o+2*t+32), _mm256_permute2x128_si256(lo,hi,0x31));
uint32_t m0=(uint32_t)_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_and_si256(va,one),7));
uint32_t m1=(uint32_t)_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_and_si256(vb,one),7));
if(t==0) { w0p[g]=(uint64_t)m0; w1p[g]=(uint64_t)m1; }
else { w0p[g]|=(uint64_t)m0<<32; w1p[g]|=(uint64_t)m1<<32; }
}
}
}
}
/* ================= STRASSEN (exact over Z/256) =================
Every coefficient is +-1 and there is no division, so the identities hold in ANY commutative
ring; int8 arithmetic mod 256 is exactly that ring. The case table and the combine
coefficients are GENERATED from tables that mkstrassen4k.py's self-check brute-forces over
Z/256 before this file is written.
============================================================== */
#define SM 2048
static int8_t SA[SM*SM] __attribute__((aligned(64)));
static int8_t SB[SM*SM] __attribute__((aligned(64)));
static int8_t MMS[7][SM*SM] __attribute__((aligned(64)));
/* ============ FUSED QUADRANT PACKERS (--fuse) ============
The unfused path builds S2A/S2B with blk() and hands them to build_A0A1/build_BI3Bp, which
read them straight back: 2 MB written and 2 MB re-read per sub-product, x49. These write the
PACKED forms DIRECTLY from the parent's quadrants. Every stored value is identical by
construction, so this is a pure traffic deletion, not a re-derivation.
buildA_q/buildB_q(int h,int n,X,r0,c0,Y,r1,c1,op) == pack(X quad op Y quad)
========================================================= */
AVX2 static void buildA_q(int h,int n,const int8_t*X,int r0,int c0,
const int8_t*Y,int r1,int c1,int op){
const __m256i mx=_mm256_set1_epi8(0x7F);
int W=h/64;
for (int i=0;i<h;i++){
const int8_t*xa=X+(size_t)(r0+i)*n+c0, *ya=Y+(size_t)(r1+i)*n+c1;
int8_t*dst=A0b+(size_t)i*LDA;
uint64_t*w1=A1b+(size_t)i*W;
for (int k=0;k<h;k+=64){
__m256i v0=_mm256_load_si256((const __m256i*)(xa+k));
__m256i v1=_mm256_load_si256((const __m256i*)(xa+k+32));
if (op){ __m256i u0=_mm256_load_si256((const __m256i*)(ya+k));
__m256i u1=_mm256_load_si256((const __m256i*)(ya+k+32));
if(op==1){ v0=_mm256_add_epi8(v0,u0); v1=_mm256_add_epi8(v1,u1); }
else { v0=_mm256_sub_epi8(v0,u0); v1=_mm256_sub_epi8(v1,u1); } }
_mm256_store_si256((__m256i*)(dst+k), _mm256_and_si256(v0,mx));
_mm256_store_si256((__m256i*)(dst+k+32), _mm256_and_si256(v1,mx));
w1[k>>6]=(uint64_t)(uint32_t)_mm256_movemask_epi8(v0)
|((uint64_t)(uint32_t)_mm256_movemask_epi8(v1)<<32);
}
}
}
AVX2 static void buildB_q(int h,int n,const int8_t*X,int r0,int c0,
const int8_t*Y,int r1,int c1,int op){
const __m256i one=_mm256_set1_epi8(1);
int ng=h/64, W=h/64;
for (int p=0;p<h/2;p++){
const int8_t *ra=X+(size_t)(r0+2*p)*n+c0, *rb=X+(size_t)(r0+2*p+1)*n+c0;
const int8_t *sa=Y+(size_t)(r1+2*p)*n+c1, *sb=Y+(size_t)(r1+2*p+1)*n+c1;
uint64_t *w0p=Bpb+(size_t)(2*p)*W, *w1p=Bpb+(size_t)(2*p+1)*W;
for (int g=0;g<ng;g++){
for (int t=0;t<64;t+=32){
__m256i va=_mm256_load_si256((const __m256i*)(ra+64*g+t));
__m256i vb=_mm256_load_si256((const __m256i*)(rb+64*g+t));
if (op){ __m256i pa=_mm256_load_si256((const __m256i*)(sa+64*g+t));
__m256i pb=_mm256_load_si256((const __m256i*)(sb+64*g+t));
if(op==1){ va=_mm256_add_epi8(va,pa); vb=_mm256_add_epi8(vb,pb); }
else { va=_mm256_sub_epi8(va,pa); vb=_mm256_sub_epi8(vb,pb); } }
__m256i lo=_mm256_unpacklo_epi8(va,vb), hi=_mm256_unpackhi_epi8(va,vb);
int8_t *o=BI3b+(size_t)g*((h/2)*128+1024)+(size_t)p*128;
_mm256_store_si256((__m256i*)(o+2*t), _mm256_permute2x128_si256(lo,hi,0x20));
_mm256_store_si256((__m256i*)(o+2*t+32), _mm256_permute2x128_si256(lo,hi,0x31));
uint32_t mm0=(uint32_t)_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_and_si256(va,one),7));
uint32_t mm1=(uint32_t)_mm256_movemask_epi8(_mm256_slli_epi16(_mm256_and_si256(vb,one),7));
if(t==0){ w0p[g]=(uint64_t)mm0; w1p[g]=(uint64_t)mm1; }
else { w0p[g]|=(uint64_t)mm0<<32; w1p[g]|=(uint64_t)mm1<<32; }
}
}
}
}
/* ---- LEVEL 2 scratch: the m x m sub-product is itself Strassen-decomposed into 7 of h=m/2 ---- */
static int8_t S2M[7][1024*1024] __attribute__((aligned(64)));
/* Cblk += sum_k s_k * M_k (up to 4 terms; NULL skips a term). dst stride is `n`, block is m x m. */
AVX2 static void cmb(int8_t*C,int n,int r0,int c0,int m,
const int8_t*M0,int s0,const int8_t*M1,int s1,
const int8_t*M2,int s2,const int8_t*M3,int s3){
for (int i=0;i<m;i++){
int8_t *d=C+(size_t)(r0+i)*n+c0;
const int8_t *p0=M0?M0+(size_t)i*m:0, *p1=M1?M1+(size_t)i*m:0;
const int8_t *p2=M2?M2+(size_t)i*m:0, *p3=M3?M3+(size_t)i*m:0;
for (int j=0;j<m;j+=32){
__m256i v;
if (p0){ __m256i t=_mm256_load_si256((const __m256i*)(p0+j));
v = s0>0?t:_mm256_sub_epi8(_mm256_setzero_si256(),t); }
else v = _mm256_setzero_si256();
if (p1){ __m256i t=_mm256_load_si256((const __m256i*)(p1+j));
v = _mm256_add_epi8(v, s1>0?t:_mm256_sub_epi8(_mm256_setzero_si256(),t)); }
if (p2){ __m256i t=_mm256_load_si256((const __m256i*)(p2+j));
v = _mm256_add_epi8(v, s2>0?t:_mm256_sub_epi8(_mm256_setzero_si256(),t)); }
if (p3){ __m256i t=_mm256_load_si256((const __m256i*)(p3+j));
v = _mm256_add_epi8(v, s3>0?t:_mm256_sub_epi8(_mm256_setzero_si256(),t)); }
_mm256_stream_si256((__m256i*)(d+j), v);
}
}
}
/* dst[i*h+j] = X[(r0+i)*n+(c0+j)] op Y[(r1+i)*n+(c1+j)], op: 0 copy 1 add 2 sub (mod 256) */
AVX2 static void blk(int8_t*dst,const int8_t*X,int n,int r0,int c0,int h,
const int8_t*Y,int r1,int c1,int op){
for (int i=0;i<h;i++){
const int8_t *xa=X+(size_t)(r0+i)*n+c0, *ya=Y+(size_t)(r1+i)*n+c1;
int8_t *d=dst+(size_t)i*h;
int j=0;
if (op==0) for(;j+32<=h;j+=32) _mm256_store_si256((__m256i*)(d+j),
_mm256_load_si256((const __m256i*)(xa+j)));
else if (op==1) for(;j+32<=h;j+=32) _mm256_store_si256((__m256i*)(d+j),
_mm256_add_epi8(_mm256_load_si256((const __m256i*)(xa+j)),
_mm256_load_si256((const __m256i*)(ya+j))));
else for(;j+32<=h;j+=32) _mm256_store_si256((__m256i*)(d+j),
_mm256_sub_epi8(_mm256_load_si256((const __m256i*)(xa+j)),
_mm256_load_si256((const __m256i*)(ya+j))));
if (op) for(;j<h;j++) d[j]=(int8_t)(xa[j]+(op==1?ya[j]:-ya[j]));
}
}
/* ---------- 4-Russians GF(2) correction (our own `corr_rus`, from mmmc2k) ----------
P[i][*] = XOR over k with A1[i][k]=1 of Bp[k][*].
A1b row i holds n bits as n/8 bytes; for byte index bb the set bits are
k = 8*bb+t, so precompute per 8-k group g
TAB[g][v] = XOR_{t in bits(v)} Bp[8g+t][*]
and a row's contribution over k in [kb,kb+64) becomes 8 lookups instead of
~32 full-row reads. Table built by the Gray recursion T[v]=T[v&(v-1)]^Bp[k0+ctz(v)].
★ mc4_: extended to NY=4 so the m=1024 Strassen LEAVES (49 of them) are covered too;
the template already parameterised NY, this is a new instantiation + guard only.
Verbatim otherwise from problems/mmmc2k/work/zm2_c_final.cpp (this account's artifact). */
static uint8_t Gtab[8*256*(NMAX/8)] __attribute__((aligned(64)));
/* single-instruction 32B memory ops: gcc 9.3 -O2 otherwise splits
_mm256_loadu_si256 into vmovdqu xmm + vinserti128 (extra uop on p5). */
#define LDU32(p) ({ __m256i _v; __asm__("vmovdqu %1, %0" : "=x"(_v) : "m"(*(const __m256i*)(p))); _v; })
#define XOR32(dst,p) __asm__("vpxor %1, %0, %0" : "+x"(dst) : "m"(*(const __m256i*)(p)))
#define STU32(p,v) __asm__ volatile("vmovdqu %1, %0" : "+m"(*(__m256i*)(p)) : "x"(v))
/* ---- corr_rows64: the h=512 leaf's row pass (B == n/8 == 64) --------------------------
SAME algorithm, SAME table, SAME table construction, SAME accumulation order, SAME FIRST
semantics. The ONLY thing that changes is how the 16 nibble-table addresses are formed:
the row's eight A1 bytes are read ONCE as a uint64 and each nibble is scaled by an
immediate shift, instead of gcc's per-nibble `movzbl` / `shr` / `and` / `add` / `shl`
chain (objdump: 83 of the shipped row loop's 117 instructions are that arithmetic).
Judge A/B (tools/probe.py, gcc 9.3): 387.2 k -> 142.4 k cycles per corr_rus(512), Pbb
bit-identical over all 32768 bytes. */
template<bool FIRST>
__attribute__((target("avx2"))) static void corr_rows64(int n,int W,int gb0,const uint8_t*A1){
for(int i=0;i<n;i++){
const uint8_t*a=A1+(size_t)i*64+gb0;
uint64_t *po=Pbb+(size_t)i*W;
uint64_t w; memcpy(&w,a,8);
__m256i x0=_mm256_setzero_si256();
__m256i x1=_mm256_setzero_si256();
#pragma GCC unroll 16
for(int g=0;g<16;g++){
unsigned off=(unsigned)(((w>>(4*g))&15u)<<6);
const uint8_t*T=Gtab+off;
XOR32(x0,T+(g<<10));
XOR32(x1,T+(g<<10)+32);
}
if(FIRST){ STU32(po,x0); STU32(po+4,x1); }
else { STU32(po, _mm256_xor_si256(LDU32(po),x0));
STU32(po+4, _mm256_xor_si256(LDU32(po+4),x1)); }
}
}
template<int NY, bool FIRST>
__attribute__((target("avx2"))) static void corr_rows(int n,int B,int W,int gb0,const uint8_t*A1){
for(int i=0;i<n;i++){
const uint8_t*a=A1+(size_t)i*B;
uint64_t*po=Pbb+(size_t)i*W;
__m256i acc[NY];
for(int q=0;q<NY;q++) acc[q]=_mm256_setzero_si256();
for(int g=0;g<16;g++){
uint8_t bits=a[gb0+(g>>1)];
uint8_t value=(g&1)?(bits>>4):(bits&15);
const uint8_t*T=Gtab+((size_t)g*16+(size_t)value)*B;
for(int q=0;q<NY;q++) XOR32(acc[q],T+(size_t)q*32);
}
for(int q=0;q<NY;q++){
if (FIRST) STU32(po+4*(size_t)q, acc[q]);
else {
__m256i o=LDU32(po+4*(size_t)q);
STU32(po+4*(size_t)q, _mm256_xor_si256(o,acc[q]));
}
}
}
}
__attribute__((target("avx2"))) static void corr_rus(int n){
const int W=n/64, B=n/8, NY=B/32;
if(NY!=2 && NY!=4 && NY!=8 && NY!=16){ corr_pass3(n); return; }
const uint8_t*A1=(const uint8_t*)A1b;
const int NB=16; /* 8 k-groups of 8 = 64 k per block */
for(int kb=0;kb<n;kb+=NB*4){
for(int g=0;g<NB;g++){
const int k0=kb+g*4;
uint8_t*T0=Gtab+(size_t)g*16*B;
memset(T0,0,B);
for(int v=1;v<16;v++){
uint8_t*dst=T0+(size_t)v*B;
const uint8_t*pr=T0+(size_t)(v&(v-1))*B;
const uint8_t*bp=(const uint8_t*)(Bpb+(size_t)(k0+__builtin_ctz(v))*W);
for(int q=0;q<B;q+=32){
__m256i x=LDU32(pr+q);
XOR32(x,bp+q);
STU32(dst+q,x);
}
}
}
const int gb0=kb>>3;
if (B==64) { /* h=512 leaf: streamlined row pass, see corr_rows64 */
if (kb==0) corr_rows64<true >(n,W,gb0,A1);
else corr_rows64<false>(n,W,gb0,A1);
} else if (kb==0) {
if(NY==16) corr_rows<16,true>(n,B,W,gb0,A1);
else if(NY==8)corr_rows<8,true>(n,B,W,gb0,A1);
else if(NY==4)corr_rows<4,true>(n,B,W,gb0,A1);
else corr_rows<2,true>(n,B,W,gb0,A1);
} else {
if(NY==16) corr_rows<16,false>(n,B,W,gb0,A1);
else if(NY==8)corr_rows<8,false>(n,B,W,gb0,A1);
else if(NY==4)corr_rows<4,false>(n,B,W,gb0,A1);
else corr_rows<2,false>(n,B,W,gb0,A1);
}
}
}
/* The GF(2) + combine tail of a sub-product, i.e. everything after the operand packers. Split
out so the FUSED path can reach it without materialising S2A/S2B first. */
AVX2 static void submm_tail(int m,int8_t*Cp){
corr_rus(m);
/* nopb: expand_bits(m) DELETED -- mikro_u4_pb expands the mask from the packed Pbb row.
Pbb row stride is n/64 uint64 == n/8 bytes (n = m for a leaf). */
const int PW=m/64;
const int GB=256, IB=128;
for (int ib=0; ib<m; ib+=IB){
const int ihi = (ib+IB<m)? ib+IB : m;
for (int gb=0; gb<m; gb+=GB){
const int ghi = (gb+GB<m)? gb+GB : m;
for (int g=gb; g<ghi; g+=64){
const int8_t *bi = BI3b+(size_t)(g>>6)*((m/2)*128+1024);
for (int i=ib; i<ihi; i+=2)
mikro_u4_pb(m, A0b+(size_t)i*LDA, bi,
Cp+(size_t)i*m+g, (const uint8_t*)(Pbb+(size_t)i*PW)+(g>>3), 0, LDA, PW*8);
}
}
}
}
/* one m x m sub-product through the SHIPPED pipeline, NT-stored to Cp (m = 2048 in the
shipped dispatch; `m` is a parameter so the SAME code path gates at smaller m). */
AVX2 static void submm_plain(int m,const int8_t*Ap,const int8_t*Bp,int8_t*Cp){
build_A0A1(m,Ap); build_BI3Bp(m,Bp); submm_tail(m,Cp);
}
AVX2 static void submm(int m,const int8_t*Ap,const int8_t*Bp,int8_t*Cp);
#define S2MIN 1024
/* level 2: 7 sub-products of h=m/2, recombined by the SAME verified identity.
⛔ THE SUB-PRODUCT IS COMPUTED BY `submm_plain`, **NOT** BY `submm`.
Calling `submm(h,...)` re-enters this function at h, and the inner call **overwrites the
parent's own `S2A`/`S2B`/`S2M` scratch** -- so every `S2M[k]` except the last is destroyed
before the combine reads it. That is a 100 %-wrong build, and the 6-second A=I probe at
n=4096 found it (87 % of bytes wrong, all four blocks). If a deeper level is ever wanted,
it needs its own scratch, not the shared pool. */
/* Third-level operand blocks and seven independent 512-square outputs. */
static int8_t S2A[1024*1024] __attribute__((aligned(64)));
static int8_t S2B[1024*1024] __attribute__((aligned(64)));
static int8_t S3M[7][512*512] __attribute__((aligned(64)));
AVX2 static void submm_s3(int m,const int8_t*Ap,const int8_t*Bp,int8_t*Cp){
const int h=m>>1, o=h;
for (int k=0;k<7;k++){
switch(k){
case 0: buildA_q(h,m,Ap,0,0,Ap,o,o,1); buildB_q(h,m,Bp,0,0,Bp,o,o,1); submm_tail(h,S3M[0]); break;
case 1: buildA_q(h,m,Ap,o,0,Ap,o,o,1); buildB_q(h,m,Bp,0,0,Bp,0,0,0); submm_tail(h,S3M[1]); break;
case 2: buildA_q(h,m,Ap,0,0,Ap,0,0,0); buildB_q(h,m,Bp,0,o,Bp,o,o,2); submm_tail(h,S3M[2]); break;
case 3: buildA_q(h,m,Ap,o,o,Ap,o,o,0); buildB_q(h,m,Bp,o,0,Bp,0,0,2); submm_tail(h,S3M[3]); break;
case 4: buildA_q(h,m,Ap,0,0,Ap,0,o,1); buildB_q(h,m,Bp,o,o,Bp,o,o,0); submm_tail(h,S3M[4]); break;
case 5: buildA_q(h,m,Ap,o,0,Ap,0,0,2); buildB_q(h,m,Bp,0,0,Bp,0,o,1); submm_tail(h,S3M[5]); break;
case 6: buildA_q(h,m,Ap,0,o,Ap,o,o,2); buildB_q(h,m,Bp,o,0,Bp,o,o,1); submm_tail(h,S3M[6]); break;
}
}
_mm_sfence();
cmb(Cp,m,0,0,h, S3M[0],1,S3M[3],1,S3M[4],-1,S3M[6],1);
cmb(Cp,m,0,o,h, S3M[2],1,S3M[4],1,0,0,0,0);
cmb(Cp,m,o,0,h, S3M[1],1,S3M[3],1,0,0,0,0);
cmb(Cp,m,o,o,h, S3M[0],1,S3M[2],1,S3M[1],-1,S3M[5],1);
_mm_sfence();
}
AVX2 static void submm_s2(int m,const int8_t*Ap,const int8_t*Bp,int8_t*Cp){
const int h=m>>1, o=h;
for (int k=0;k<7;k++){
switch(k){
case 0: blk(S2A,Ap,m,0,0,h,Ap,o,o,1); blk(S2B,Bp,m,0,0,h,Bp,o,o,1); break;
case 1: blk(S2A,Ap,m,o,0,h,Ap,o,o,1); blk(S2B,Bp,m,0,0,h,Bp,0,0,0); break;
case 2: blk(S2A,Ap,m,0,0,h,Ap,0,0,0); blk(S2B,Bp,m,0,o,h,Bp,o,o,2); break;
case 3: blk(S2A,Ap,m,o,o,h,Ap,o,o,0); blk(S2B,Bp,m,o,0,h,Bp,0,0,2); break;
case 4: blk(S2A,Ap,m,0,0,h,Ap,0,o,1); blk(S2B,Bp,m,o,o,h,Bp,o,o,0); break;
case 5: blk(S2A,Ap,m,o,0,h,Ap,0,0,2); blk(S2B,Bp,m,0,0,h,Bp,0,o,1); break;
case 6: blk(S2A,Ap,m,0,o,h,Ap,o,o,2); blk(S2B,Bp,m,o,0,h,Bp,o,o,1); break;
}
submm_s3(h,S2A,S2B,S2M[k]);
}
_mm_sfence();
cmb(Cp,m,0,0,h, S2M[0],1,S2M[3],1,S2M[4],-1,S2M[6],1);
cmb(Cp,m,0,o,h, S2M[2],1,S2M[4],1,0,0,0,0);
cmb(Cp,m,o,0,h, S2M[1],1,S2M[3],1,0,0,0,0);
cmb(Cp,m,o,o,h, S2M[0],1,S2M[2],1,S2M[1],-1,S2M[5],1);
_mm_sfence();
}
AVX2 static void submm(int m,const int8_t*Ap,const int8_t*Bp,int8_t*Cp){
if (m>=S2MIN) { submm_s2(m,Ap,Bp,Cp); return; }
submm_plain(m,Ap,Bp,Cp);
}
AVX2 static void strassen1(int n,const int8_t*A,const int8_t*B,int8_t*C){
const int m=n>>1, o=m;
for (int k=0;k<7;k++){
switch(k){
case 0: blk(SA,A,n,0,0,m,A,o,o,1); blk(SB,B,n,0,0,m,B,o,o,1); break;
case 1: blk(SA,A,n,o,0,m,A,o,o,1); blk(SB,B,n,0,0,m,B,0,0,0); break;
case 2: blk(SA,A,n,0,0,m,A,0,0,0); blk(SB,B,n,0,o,m,B,o,o,2); break;
case 3: blk(SA,A,n,o,o,m,A,o,o,0); blk(SB,B,n,o,0,m,B,0,0,2); break;
case 4: blk(SA,A,n,0,0,m,A,0,o,1); blk(SB,B,n,o,o,m,B,o,o,0); break;
case 5: blk(SA,A,n,o,0,m,A,0,0,2); blk(SB,B,n,0,0,m,B,0,o,1); break;
case 6: blk(SA,A,n,0,o,m,A,o,o,2); blk(SB,B,n,o,0,m,B,o,o,1); break;
}
submm(m,SA,SB,MMS[k]);
}
_mm_sfence();
cmb(C,n,0,0,m, MMS[0],1,MMS[3],1,MMS[4],-1,MMS[6],1);
cmb(C,n,0,o,m, MMS[2],1,MMS[4],1,0,0,0,0);
cmb(C,n,o,0,m, MMS[1],1,MMS[3],1,0,0,0,0);
cmb(C,n,o,o,m, MMS[0],1,MMS[2],1,MMS[1],-1,MMS[5],1);
_mm_sfence();
}
AVX2 void matrix_multiply(int n, const int8_t *A, const int8_t *B, int8_t *C){
if (n<=0 || (n&255) || n>NMAX) { generic_mm(n,A,B,C); return; }
if (n==4096) { strassen1(n,A,B,C); return; }
/* x4: A1T is written by build_A1T and NEVER READ -- dead 16.78 MB + its transpose pass. */
/* FUSED: one pass over A (was two), one over B (was two) */
build_A0A1(n,A); build_BI3Bp(n,B);
if (n==4096) corr16(); else corr_pass3(n); expand_bits(n);
for (int g=0; g<n; g+=64)
for (int i=0; i<n; i+=2)
mikro_u4(n, A0b+(size_t)i*LDA, BI3b+(size_t)(g>>6)*(n/2)*128,
C+(size_t)i*n+g, PBb+(size_t)i*LDB+g, 0, LDA, LDB);
_mm_sfence();
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 400.894 ms | 65 MB + 244 KB | Accepted | Score: 100 | 显示更多 |