代码

#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <immintrin.h>
#pragma GCC target("avx2")

// Four-Russians multiplication over GF(2): each eight input rows generate
// 256 possible XOR combinations, reused by every output row.
void matrix_multiply(int n,const bool*A,const bool*B,bool*C) {
    if(n<=0)return;
    if(n%64 || n%8) {
        for(int i=0;i<n;++i)for(int j=0;j<n;++j){
            bool v=false;
            for(int k=0;k<n;++k)v^=A[(size_t)i*n+k]&B[(size_t)k*n+j];
            C[(size_t)i*n+j]=v;
        }
        return;
    }
    const size_t words=(size_t)n/64;
    uint64_t*packed_b=nullptr,*packed_c=nullptr,*table=nullptr;
    if(posix_memalign((void**)&packed_b,4096,(size_t)n*words*8) ||
       posix_memalign((void**)&packed_c,4096,(size_t)n*words*8) ||
       posix_memalign((void**)&table,4096,256*words*8))abort();
    memset(packed_b,0,(size_t)n*words*8);
    memset(packed_c,0,(size_t)n*words*8);
    for(int k=0;k<n;++k)for(int j=0;j<n;++j)
        packed_b[(size_t)k*words+(size_t)j/64]|=(uint64_t)B[(size_t)k*n+j]<<(j&63);
    for(int base=0;base<n;base+=8){
        memset(table,0,words*8);
        for(int m=1;m<256;++m){
            int bit=__builtin_ctz((unsigned)m),prev=m&(m-1);
            const uint64_t*x=table+(size_t)prev*words;
            const uint64_t*y=packed_b+(size_t)(base+bit)*words;
            uint64_t*z=table+(size_t)m*words;
            for(size_t w=0;w<words;++w)z[w]=x[w]^y[w];
        }
        for(int i=0;i<n;++i){
            const bool*a=A+(size_t)i*n+base;
            unsigned mask=(unsigned)a[0]|((unsigned)a[1]<<1)|((unsigned)a[2]<<2)|
                ((unsigned)a[3]<<3)|((unsigned)a[4]<<4)|((unsigned)a[5]<<5)|
                ((unsigned)a[6]<<6)|((unsigned)a[7]<<7);
            const uint64_t*x=table+(size_t)mask*words;
            uint64_t*y=packed_c+(size_t)i*words;
            for(size_t w=0;w<words;++w)y[w]^=x[w];
        }
    }
    for(int i=0;i<n;++i)for(int j=0;j<n;++j)
        C[(size_t)i*n+j]=(bool)((packed_c[(size_t)i*words+(size_t)j/64]>>(j&63))&1U);
    free(table);free(packed_c);free(packed_b);
}

评测结果