/* 引用:saffah_v41f1017_agg4 https://duck.ac/submission/172744 完整单指令256位加载/顺序父记录实现;原引及许可全部保留。思路:物理窗口由49152缩小至36864,仍保持48/32/16整除,以降低每窗输出与输入的缓存工作集;所有对子及游标逻辑不变。目的:两份全100M/新旧边界/错位/输入哈希/守卫验证后官网测量。*/
/* References / 引用: saffah_codex_6a_agg3
https://duck.ac/submission/170571: complete Accepted sorted parent-row
list, monotone active prefix, fourfold SSE partner fusion/cursors/tails.
saffah_v41f1017_agg4 https://duck.ac/submission/170554: row-invariant flag
specialization idea, extended independently from twofold to fourfold rows.
All inherited authors, exact URLs, used content and notices are retained.
Own saffah_codex61s_agg5 https://duck.ac/submission/170650:
previous generic-lambda row specialization, officially Accepted but slow.
Approach / 思路: Emit the three specialized vector regions lexically in
multiply itself so the owning function directly sees all row scalars,
pointers and cursor variables, without a separate generic-lambda operator
or its capture-object accesses. Each local child helper has literal bool
flags and the original loop arithmetic. Additionally, Instantiate the entire32-wide/eight-wide vector phase
for the three possible row-flag pairs: no child,2i only, or2i plus4i.
Dispatch once per row and make both fusion flags compile-time constants
inside each specialization. Preserve the original SSE partner products,
masked crossing/steady-state arithmetic, scatter order, deferred cursor
updates and every pair. Physical target block=49152.
Experiment purpose:129 quadratic sizes and full10^8 independent divisor
pairs with an explicit specialized-path hit/input/64guards, then official
measurement; local speed never rejects the candidate.
*/
/* References / 引用: Each ID denotes https://duck.ac/submission/{ID}; verified official authors override historical misattributions.
saffah_cc_v41_agg1:100000.
saffah_codex61s_agg5:164808,164972,166022,166311,166337,166395,170141,170182.
saffah_codex_6a_agg3:165981,167080,167081,167082.
saffah_v41f1017_agg4:164782,164866,166996,167233,167897,170438.
170438: copied complete fourfold/odd-part-three folded engine, aligned generic starts, cursor boundaries and masked fringes.170182: incremental integer-square-root window bound idea.170141: doubled-row fusion;167897/167233/167082/167080/167081: first-writer48 stream, generic32 unroll and deferred tails/diagonals.166996/166395/166337/166311/166022/165981: inherited fused low rows and cursor methods;164972/164866/164808/164782: full-width load/store methods. No separate source license is attached.
Idea / 思路: Build the sorted list of actual generic parent divisors once, removing folded child rows from traversal itself. Advance the integer-square-root bound monotonically once per physical window and grow the active prefix of this list. Each window then visits only relevant parent cursors, without repeated64-bit i*i bounds or per-row child/modulus tests. Keep170438 original scalar/SSE child products because the wider partner experiment did not improve official timing. All row order, product coverage and cursor/tail behavior remain unchanged. Purpose: reduce the per-window scheduler overhead with full100M and boundary/arbitrary correctness checks before official measurement. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/170669: complete lexical three-region multiply implementation, with all inherited notices above retained. saffah_codex_6a_agg3 https://duck.ac/submission/170611: idea of separating initial masked partner folds from steady unconditional folds; that earlier generic-lambda implementation was slow. Duck sources have no additional license notice.
Idea / 思路: In the two partner-enabled lexical regions, test once whether the starting aligned cursor is past every child cursor. If so, use a full lexical copy of the body whose partner additions are unconditional; otherwise retain the original masked boundary body. All later product indices increase, so the single row test suffices. This combines the observed efficient lexical layout with removing repeated child-start comparisons inside each32-product iteration. Purpose: reduce folded-row bookkeeping, with full100M and fallback verification before online measurement. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170707: complete lexical steady-fold engine; https://duck.ac/submission/170526: first-writer low-row fusion idea. All inherited authors and notices above retained.
Idea / 思路: Fuse row8 into the existing row4 SSE vector before the48-output first-writer stores. Each16-output section computes two row8 products and interleaves them into the four row4 products. Mask the initial diagonal/crossing section, handle window fringes with a row8 cursor, and delete row8 from generic traversal and final tails. Purpose: eliminate row8's separate destination read-modify-write stream. Validate all100M outputs plus boundaries and fallback cases before official timing. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170728: complete first-writer row8 fusion and lexical engine. All inherited sources above retained.
Idea / 思路: Extend the row8 first-writer vector with one row16 scalar product in its low lane for each16 output positions. Use its exact diagonal cutoff and cursor fringes, then remove row16 from generic traversal and final tails. Purpose: eliminate another sparse destination read-modify-write pass while reusing row8-to-row4 interleaving. Full100M, random, boundaries and small cases verified before official timing. */
/* References / 引用:
* saffah_v41f1017_agg4 https://duck.ac/submission/171744: complete accepted engine with row-constant caching, large-input specialization, first-writer16 and all inherited notices above.
Idea / 思路: Cache coefficients only for actual generic parent rows, in their traversal order, using exactly six32-bit words per parent instead of eight words for every divisor. Index by the current parent-row ordinal. This removes unused folded-row entries and padding from repeated coefficient traffic, while preserving all six constants, specialization, cursors, pair coverage and arithmetic order.
Experiment purpose: independent divisor-pair outputs for two full100M arrays, boundaries, hashes and guards, then official timing of the compact physical coefficient stream.
*/
/* References / 引用:
* saffah_codex_6a_agg3 https://duck.ac/submission/171798: actual-parent coefficient cache and complete accepted multiplication engine, retaining all inherited author URLs and notices above.
Idea / 思路: Partition independent parent rows by zero, one or two folded children. Each sorted group has its own monotone active prefix and exactly two, four or six coefficient words per row. Instantiate each group with compile-time child flags, eliminating runtime shape branches and unused coefficient traffic. Outputs are modulo-2^32 additive, and each child cursor has exactly one parent, so group traversal preserves coverage and results.
Experiment purpose: full independent100M divisor-pair correctness, varied boundaries/alignment/input hashes and output guards, then official timing of reduced coefficient footprint and compile-time row shapes.
*/
/* References / 引用:
* saffah_codex_6a_agg3 https://duck.ac/submission/171847: compile-time child-count groups and compact coefficients; all original engine references and notices remain above.
Idea / 思路: Store each generic parent's divisor, two advancing cursors and used coefficients in one contiguous record. Folded child cursors retain their separate array because no folded child is a generic parent. Each hot iteration now reads and writes the parent's sequential record, avoiding the dependent position[i] lookup and separate row-index stream. Reconcile parent cursors once after all windows for the final scalar tails.
Experiment purpose: verify two full100M independent divisor-pair arrays plus boundaries, alignments, guards and input hashes, then measure the official cost of unifying hot parent state.
*/
#include <type_traits>
#include<type_traits>
#include <immintrin.h>
#include <algorithm>
#include <cstdint>
#include <vector>
#include <cstring>
static __attribute__((always_inline))inline __m256i root_ld256(const void*p){__m256i v;__asm__("vmovups %1,%0":"=x"(v):"m"(*(const __m256i*)p));return v;}
static __attribute__((always_inline,target("avx")))inline __m256i root_single256_li(const __m256i*p){__m256i v;__asm__("vmovdqu %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_si(__m256i*p,__m256i v){__asm__("vmovdqu %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline __m256d root_single256_ld(const double*p){__m256d v;__asm__("vmovupd %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_sd(double*p,__m256d v){__asm__("vmovupd %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
static __attribute__((always_inline,target("avx")))inline __m256 root_single256_lf(const float*p){__m256 v;__asm__("vmovups %1,%0":"=x"(v):"m"(*(const unsigned char(*)[32])p));return v;}
static __attribute__((always_inline,target("avx")))inline void root_single256_sf(float*p,__m256 v){__asm__("vmovups %1,%0":"=m"(*(unsigned char(*)[32])p):"x"(v));}
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
namespace root_fast {
using u32=unsigned;using u64=unsigned long long;
inline u32 reduce(__m256i x){__m128i y=_mm_add_epi32(_mm256_castsi256_si128(x),_mm256_extracti128_si256(x,1));y=_mm_add_epi32(y,_mm_srli_si128(y,8));y=_mm_add_epi32(y,_mm_srli_si128(y,4));return _mm_cvtsi128_si32(y);}
inline void divide(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;u32 sb=0;for(unsigned j=1;j<n;++j)sb+=b[j];c[0]=a[0]*sb;
constexpr unsigned block=65536;
for(unsigned lo=1;lo<n;lo+=block){unsigned hi=std::min(n,lo+block);
for(unsigned i=1;u64(i)*i<hi;++i){
unsigned j=std::max(i,(lo+i-1)/i),last=(hi-1)/i,k=i*j;u32 sum=0,bi=b[i];
if(j==i){sum+=a[k]*bi;++j;k+=i;}
__m256i vs=_mm256_setzero_si256(),vb=_mm256_set1_epi32(bi),ix=_mm256_setr_epi32(0,i,2*i,3*i,4*i,5*i,6*i,7*i);
for(;j+7<=last;j+=8,k+=8*i){
__m256i x=_mm256_i32gather_epi32((const int*)(a+k),ix,4);
vs=_mm256_add_epi32(vs,_mm256_mullo_epi32(x,root_ld256(b+j)));
__m256i old=_mm256_loadu_si256((const __m256i*)(c+j));
_mm256_storeu_si256((__m256i*)(c+j),_mm256_add_epi32(old,_mm256_mullo_epi32(x,vb)));
}
sum+=reduce(vs);
for(;j<=last;++j,k+=i){u32 x=a[k];sum+=x*b[j];c[j]+=x*bi;}c[i]+=sum;
}
}
}
inline void floor_conv(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){
if(!n)return;std::vector<u32>prefix(n);u32 total=0;
for(unsigned i=0;i<n;++i){prefix[i]=total;total+=a[i];}
divide(n,prefix.data(),b,c);
u32 tail=0,previous=0;unsigned bound=n;
for(unsigned k=1;k<n;++k){unsigned need=(n-1)/k+1;while(bound>need)tail+=b[--bound];u32 current=c[k]+total*tail;c[k-1]=current-previous;previous=current;}
while(bound>1)tail+=b[--bound];c[n-1]=total*tail-previous;
}
inline std::vector<unsigned> primes(unsigned n){
std::vector<unsigned char> comp((n+1)/2);std::vector<unsigned> ps;
if(n>2)ps.push_back(2);
for(unsigned i=3;u64(i)*i<n;i+=2)if(!comp[i/2])for(unsigned j=i*i;j<n;j+=i*2)comp[j/2]=1;
for(unsigned i=3;i<n;i+=2)if(!comp[i/2])ps.push_back(i);return ps;
}
inline void gcd_conv(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;auto ps=primes(n);std::vector<unsigned> f(b,b+n);std::memcpy(c,a,size_t(n)*4);
for(unsigned p:ps){
unsigned i=(n-1)/p;__m256i ix=_mm256_setr_epi32(0,p,2*p,3*p,4*p,5*p,6*p,7*p);
for(;i>=15;i-=8){unsigned l=i-7;
auto x=_mm256_i32gather_epi32((const int*)(c+l*p),ix,4),y=_mm256_i32gather_epi32((const int*)(f.data()+l*p),ix,4);
_mm256_storeu_si256((__m256i*)(c+l),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(c+l)),x));
_mm256_storeu_si256((__m256i*)(f.data()+l),_mm256_add_epi32(_mm256_loadu_si256((const __m256i*)(f.data()+l)),y));
}
for(;i;--i){c[i]+=c[i*p];f[i]+=f[i*p];}
}
for(unsigned i=1;i<n;++i)c[i]*=f[i];
for(unsigned p:ps){
unsigned last=(n-1)/p,i=1;__m256i ix=_mm256_setr_epi32(0,p,2*p,3*p,4*p,5*p,6*p,7*p);
for(;i+7<=last;i+=8){auto x=_mm256_i32gather_epi32((const int*)(c+i*p),ix,4);_mm256_storeu_si256((__m256i*)(c+i),_mm256_sub_epi32(_mm256_loadu_si256((const __m256i*)(c+i)),x));}
for(;i<=last;++i)c[i]-=c[i*p];
}
c[0]=a[0]*b[0];for(unsigned i=1;i<n;++i)c[i]+=a[0]*b[i]+b[0]*a[i];
}
}
namespace root_fast {
inline void lcm_conv(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;auto ps=primes(n);std::vector<unsigned>f(b,b+n);std::memcpy(c,a,size_t(n)*4);
u32 sa=0,sb=0;for(unsigned i=0;i<n;++i){sa+=a[i];sb+=b[i];}
for(unsigned p:ps){unsigned last=(n-1)/p;for(unsigned i=1,k=p;i<=last;++i,k+=p){c[k]+=c[i];f[k]+=f[i];}}
for(unsigned i=1;i<n;++i)c[i]*=f[i];
for(unsigned p:ps){for(unsigned i=(n-1)/p,k=i*p;i;--i,k-=p)c[k]-=c[i];}
c[0]=a[0]*sb+b[0]*sa-a[0]*b[0];
}
#ifdef ROOT_PAIR_CHECK
static uint64_t root_pair_hits=0;
#endif
#ifdef ROOT_ROW_FLAGS_CHECK
static uint64_t root_row_flags_hits=0;
#endif
template<bool root_BIG> inline void multiply_t(unsigned n,const unsigned*__restrict a,const unsigned*__restrict b,unsigned*__restrict c){
if(!n)return;if(n==1){c[0]=a[0]*b[0];return;}
__m256i vsa=_mm256_setzero_si256(),vsb=_mm256_setzero_si256();
u32 sa=a[0]+a[1],sb=b[0]+b[1];
const unsigned block=36864;
unsigned bound=1;while(u64(bound)*bound<n)++bound;
struct Position{unsigned j,k;};std::vector<Position>position(bound+1);
for(unsigned i=1;i<bound;++i)position[i]={i+1,i*i+i};c[1]=0;std::vector<unsigned> rowgroups[3];std::vector<u32> coeffgroups[3];
for(unsigned i=5;i<bound;++i){if(i==8||i==16)continue;if(i>=10&&(i&3)==2)continue;if(i>=20&&(i&7)==4)continue;if(i==12||i==24)continue;
bool pair=(i>=5&&((i&1)||i==6)&&2*i<bound);unsigned g=pair?(4*i<bound?2:1):0;rowgroups[g].push_back(i);auto &v=coeffgroups[g];v.push_back(i);v.push_back(position[i].j);v.push_back(position[i].k);v.push_back(a[i]);v.push_back(b[i]);if(g>=1){v.push_back(a[2*i]);v.push_back(b[2*i]);v.push_back(position[2*i].j);}if(g>=2){v.push_back(a[4*i]);v.push_back(b[4*i]);v.push_back(position[4*i].j);}}
unsigned imax=3,activegroups[3]={};
position[2]={3,6};
const u32 a1=a[1],b1=b[1],a2=n>2?a[2]:0,b2=n>2?b[2]:0;
const bool root_sixteen=root_BIG||(bound>16);const unsigned a16=n>16?a[16]:0,b16=n>16?b[16]:0;const bool root_eight=root_BIG||(bound>8);const unsigned a8=n>8?a[8]:0,b8=n>8?b[8]:0;const __m128i va8=_mm_set1_epi32(a8),vb8=_mm_set1_epi32(b8);const bool root_four=root_BIG||(bound>4);const u32 root_a4=n>4?a[4]:0,root_b4=n>4?b[4]:0;
const __m128i root_va4=_mm_set1_epi32(root_a4),root_vb4=_mm_set1_epi32(root_b4),root_zero128=_mm_setzero_si128();
const bool root_three=root_BIG||(bound>3);const u32 a3r=n>3?a[3]:0,b3r=n>3?b[3]:0;
const __m256i va3=_mm256_set1_epi32((int)a3r),vb3=_mm256_set1_epi32((int)b3r);
const __m256i g0i=_mm256_setr_epi32(0,0,0,1,0,0,2,0),g1i=_mm256_setr_epi32(0,3,0,0,4,0,0,5);
const __m256i h0i=_mm256_setr_epi32(0,0,0,0,0,1,0,0),h1i=_mm256_setr_epi32(2,0,0,3,0,0,4,0);
const __m256i k0i=_mm256_setr_epi32(0,0,0,0,1,0,0,2),k1i=_mm256_setr_epi32(0,0,3,0,0,4,0,0);
const auto va1=_mm256_set1_epi32(a1),vb1=_mm256_set1_epi32(b1),va2=_mm256_set1_epi32(a2),vb2=_mm256_set1_epi32(b2),zero=_mm256_setzero_si256();
for(unsigned lo=1;lo<n;lo+=block){unsigned hi=std::min(n,lo+block);while(u64(imax)*imax<hi)++imax;for(unsigned g=0;g<3;++g)while(activegroups[g]<rowgroups[g].size()&&rowgroups[g][activegroups[g]]<imax)++activegroups[g];
unsigned k=position[1].k,j2=position[2].j,k2=position[2].k;
unsigned root_j4=root_four?position[4].j:0,root_k4=root_four?position[4].k:hi;unsigned root_j8=root_eight?position[8].j:0,root_k8=root_eight?position[8].k:hi;unsigned root_j16=root_sixteen?position[16].j:0,root_k16=root_sixteen?position[16].k:hi;
unsigned j3=root_three?position[3].j:0,k3=root_three?position[3].k:hi;
for(;k<hi&&(k%48);++k){u32 av=a[k],bv=b[k];sa+=av;sb+=bv;c[k]=a1*bv+b1*av;}
for(;k2<k&&k2<hi;++j2,k2+=2)c[k2]+=a2*b[j2]+b2*a[j2];
for(;root_k4<k&&root_k4<hi;++root_j4,root_k4+=4)c[root_k4]+=root_a4*b[root_j4]+root_b4*a[root_j4];for(;root_k8<k&&root_k8<hi;++root_j8,root_k8+=8)c[root_k8]+=a8*b[root_j8]+b8*a[root_j8];for(;root_k16<k&&root_k16<hi;++root_j16,root_k16+=16)c[root_k16]+=a16*b[root_j16]+b16*a[root_j16];
for(;k3<k&&k3<hi;++j3,k3+=3)c[k3]+=a3r*b[j3]+b3r*a[j3];
for(;k+47<hi;k+=48,j2+=24,k2+=48){
unsigned q=k/3;
{
auto av0=_mm256_loadu_si256((const __m256i*)(a+k)),av1=_mm256_loadu_si256((const __m256i*)(a+k+8));
auto bv0=_mm256_loadu_si256((const __m256i*)(b+k)),bv1=_mm256_loadu_si256((const __m256i*)(b+k+8));
vsa=_mm256_add_epi32(vsa,_mm256_add_epi32(av0,av1));vsb=_mm256_add_epi32(vsb,_mm256_add_epi32(bv0,bv1));
auto u0=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv0),_mm256_mullo_epi32(vb1,av0));
auto u1=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv1),_mm256_mullo_epi32(vb1,av1));
auto xy=_mm256_add_epi32(_mm256_mullo_epi32(va2,_mm256_loadu_si256((const __m256i*)(b+j2))),_mm256_mullo_epi32(vb2,_mm256_loadu_si256((const __m256i*)(a+j2))));
auto xl=_mm256_unpacklo_epi32(xy,zero),xh=_mm256_unpackhi_epi32(xy,zero);
auto x0=_mm256_permute2x128_si256(xl,xh,0x20),x1=_mm256_permute2x128_si256(xl,xh,0x31);
if(root_four){unsigned w=k/4;__m128i four=_mm_add_epi32(_mm_mullo_epi32(root_va4,_mm_loadu_si128((const __m128i*)(b+w))),_mm_mullo_epi32(root_vb4,_mm_loadu_si128((const __m128i*)(a+w))));if(root_eight){unsigned q=w/2;__m128i more=_mm_add_epi32(_mm_mullo_epi32(va8,_mm_loadl_epi64((const __m128i*)(b+q))),_mm_mullo_epi32(vb8,_mm_loadl_epi64((const __m128i*)(a+q))));more=_mm_and_si128(more,_mm_cmpgt_epi32(_mm_setr_epi32(q,q+1,0,0),_mm_set1_epi32(8)));if(root_sixteen&&q>=34){unsigned r=q/2;more=_mm_add_epi32(more,_mm_cvtsi32_si128(a16*b[r]+b16*a[r]));}four=_mm_add_epi32(four,_mm_unpacklo_epi32(more,root_zero128));}
x0=_mm256_add_epi32(x0,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(four,root_zero128)));
x1=_mm256_add_epi32(x1,_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(four,root_zero128)));}
if(root_three){__m256i g=_mm256_add_epi32(_mm256_mullo_epi32(va3,_mm256_loadu_si256((const __m256i*)(b+q))),_mm256_mullo_epi32(vb3,_mm256_loadu_si256((const __m256i*)(a+q))));
x0=_mm256_add_epi32(x0,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,g0i),zero,0xB6));
x1=_mm256_add_epi32(x1,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,g1i),zero,0x6D));}
_mm256_storeu_si256((__m256i*)(c+k),_mm256_add_epi32(u0,x0));
_mm256_storeu_si256((__m256i*)(c+k+8),_mm256_add_epi32(u1,x1));
}
{
auto av0=_mm256_loadu_si256((const __m256i*)(a+k+16)),av1=_mm256_loadu_si256((const __m256i*)(a+k+24));
auto bv0=_mm256_loadu_si256((const __m256i*)(b+k+16)),bv1=_mm256_loadu_si256((const __m256i*)(b+k+24));
vsa=_mm256_add_epi32(vsa,_mm256_add_epi32(av0,av1));vsb=_mm256_add_epi32(vsb,_mm256_add_epi32(bv0,bv1));
auto u0=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv0),_mm256_mullo_epi32(vb1,av0));
auto u1=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv1),_mm256_mullo_epi32(vb1,av1));
auto xy=_mm256_add_epi32(_mm256_mullo_epi32(va2,_mm256_loadu_si256((const __m256i*)(b+j2+8))),_mm256_mullo_epi32(vb2,_mm256_loadu_si256((const __m256i*)(a+j2+8))));
auto xl=_mm256_unpacklo_epi32(xy,zero),xh=_mm256_unpackhi_epi32(xy,zero);
auto x0=_mm256_permute2x128_si256(xl,xh,0x20),x1=_mm256_permute2x128_si256(xl,xh,0x31);
if(root_four){unsigned w=k/4+4;__m128i four=_mm_add_epi32(_mm_mullo_epi32(root_va4,_mm_loadu_si128((const __m128i*)(b+w))),_mm_mullo_epi32(root_vb4,_mm_loadu_si128((const __m128i*)(a+w))));if(root_eight){unsigned q=w/2;__m128i more=_mm_add_epi32(_mm_mullo_epi32(va8,_mm_loadl_epi64((const __m128i*)(b+q))),_mm_mullo_epi32(vb8,_mm_loadl_epi64((const __m128i*)(a+q))));more=_mm_and_si128(more,_mm_cmpgt_epi32(_mm_setr_epi32(q,q+1,0,0),_mm_set1_epi32(8)));if(root_sixteen&&q>=34){unsigned r=q/2;more=_mm_add_epi32(more,_mm_cvtsi32_si128(a16*b[r]+b16*a[r]));}four=_mm_add_epi32(four,_mm_unpacklo_epi32(more,root_zero128));}
x0=_mm256_add_epi32(x0,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(four,root_zero128)));
x1=_mm256_add_epi32(x1,_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(four,root_zero128)));}
if(root_three){__m256i g=_mm256_add_epi32(_mm256_mullo_epi32(va3,_mm256_loadu_si256((const __m256i*)(b+q+6))),_mm256_mullo_epi32(vb3,_mm256_loadu_si256((const __m256i*)(a+q+6))));
x0=_mm256_add_epi32(x0,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,h0i),zero,0xDB));
x1=_mm256_add_epi32(x1,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,h1i),zero,0xB6));}
_mm256_storeu_si256((__m256i*)(c+k+16),_mm256_add_epi32(u0,x0));
_mm256_storeu_si256((__m256i*)(c+k+24),_mm256_add_epi32(u1,x1));
}
{
auto av0=_mm256_loadu_si256((const __m256i*)(a+k+32)),av1=_mm256_loadu_si256((const __m256i*)(a+k+40));
auto bv0=_mm256_loadu_si256((const __m256i*)(b+k+32)),bv1=_mm256_loadu_si256((const __m256i*)(b+k+40));
vsa=_mm256_add_epi32(vsa,_mm256_add_epi32(av0,av1));vsb=_mm256_add_epi32(vsb,_mm256_add_epi32(bv0,bv1));
auto u0=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv0),_mm256_mullo_epi32(vb1,av0));
auto u1=_mm256_add_epi32(_mm256_mullo_epi32(va1,bv1),_mm256_mullo_epi32(vb1,av1));
auto xy=_mm256_add_epi32(_mm256_mullo_epi32(va2,_mm256_loadu_si256((const __m256i*)(b+j2+16))),_mm256_mullo_epi32(vb2,_mm256_loadu_si256((const __m256i*)(a+j2+16))));
auto xl=_mm256_unpacklo_epi32(xy,zero),xh=_mm256_unpackhi_epi32(xy,zero);
auto x0=_mm256_permute2x128_si256(xl,xh,0x20),x1=_mm256_permute2x128_si256(xl,xh,0x31);
if(root_four){unsigned w=k/4+8;__m128i four=_mm_add_epi32(_mm_mullo_epi32(root_va4,_mm_loadu_si128((const __m128i*)(b+w))),_mm_mullo_epi32(root_vb4,_mm_loadu_si128((const __m128i*)(a+w))));if(root_eight){unsigned q=w/2;__m128i more=_mm_add_epi32(_mm_mullo_epi32(va8,_mm_loadl_epi64((const __m128i*)(b+q))),_mm_mullo_epi32(vb8,_mm_loadl_epi64((const __m128i*)(a+q))));more=_mm_and_si128(more,_mm_cmpgt_epi32(_mm_setr_epi32(q,q+1,0,0),_mm_set1_epi32(8)));if(root_sixteen&&q>=34){unsigned r=q/2;more=_mm_add_epi32(more,_mm_cvtsi32_si128(a16*b[r]+b16*a[r]));}four=_mm_add_epi32(four,_mm_unpacklo_epi32(more,root_zero128));}
x0=_mm256_add_epi32(x0,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(four,root_zero128)));
x1=_mm256_add_epi32(x1,_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(four,root_zero128)));}
if(root_three){__m256i g=_mm256_add_epi32(_mm256_mullo_epi32(va3,_mm256_loadu_si256((const __m256i*)(b+q+11))),_mm256_mullo_epi32(vb3,_mm256_loadu_si256((const __m256i*)(a+q+11))));
x0=_mm256_add_epi32(x0,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,k0i),zero,0x6D));
x1=_mm256_add_epi32(x1,_mm256_blend_epi32(_mm256_permutevar8x32_epi32(g,k1i),zero,0xDB));}
_mm256_storeu_si256((__m256i*)(c+k+32),_mm256_add_epi32(u0,x0));
_mm256_storeu_si256((__m256i*)(c+k+40),_mm256_add_epi32(u1,x1));
}
if(root_four){root_j4=k/4+12;root_k4=k+48;}if(root_eight){root_j8=k/8+6;root_k8=k+48;}if(root_sixteen&&k+48>272){root_j16=k/16+3;root_k16=k+48;}
j3=q+16;k3=k+48;
}
for(;k<hi;++k){u32 av=a[k],bv=b[k];sa+=av;sb+=bv;c[k]=a1*bv+b1*av;}
for(;k2<hi;++j2,k2+=2)c[k2]+=a2*b[j2]+b2*a[j2];
for(;root_k4<hi;++root_j4,root_k4+=4)c[root_k4]+=root_a4*b[root_j4]+root_b4*a[root_j4];for(;root_k8<hi;++root_j8,root_k8+=8)c[root_k8]+=a8*b[root_j8]+b8*a[root_j8];for(;root_k16<hi;++root_j16,root_k16+=16)c[root_k16]+=a16*b[root_j16]+b16*a[root_j16];
for(;k3<hi;++j3,k3+=3)c[k3]+=a3r*b[j3]+b3r*a[j3];
position[1]={k,k};position[2]={j2,k2};if(root_four)position[4]={root_j4,root_k4};if(root_eight)position[8]={root_j8,root_k8};if(root_sixteen)position[16]={root_j16,root_k16};if(root_three)position[3]={j3,k3};
auto runrows=[&](auto kind) __attribute__((always_inline)) {constexpr unsigned g=decltype(kind)::value;constexpr unsigned stride=(g==0?5:(g==1?8:11));auto &rowsc=coeffgroups[g];unsigned active=activegroups[g];
{u32*record=rowsc.data();for(unsigned row=0;row<active;++row,record+=stride){unsigned i=record[0];
unsigned j=record[1],k=record[2];
unsigned kend=(7u*i<hi)?hi-7u*i:0u;
if(k>=kend)continue;
u32 ai=record[3],bi=record[4];
auto va=_mm256_set1_epi32((int)ai),vb=_mm256_set1_epi32((int)bi);
constexpr bool root_pair=(g>=1);
const unsigned root_start=root_pair?record[7]:0;
const __m128i root_av2=_mm_set1_epi32(root_pair?record[5]:0),root_bv2=_mm_set1_epi32(root_pair?record[6]:0);
constexpr bool root_deep=(g>=2);
constexpr bool root_pair4=(g>=2);
const unsigned root_start4=root_pair4?record[10]:0;
const __m128i root_av4=_mm_set1_epi32(root_pair4?record[8]:0),root_bv4=_mm_set1_epi32(root_pair4?record[9]:0);
{if(root_pair){while(j&7){c[k]+=ai*b[j]+bi*a[j];++j;k+=i;}}}
#ifdef ROOT_ROW_FLAGS_CHECK
++root_row_flags_hits;
#endif
if(!root_pair){auto root_double=[&](__m256i value,unsigned jj){
if constexpr(!false)return value;
unsigned half=jj/2;
if(half>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));}
else if(half+3>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
__m128i mask=_mm_cmpgt_epi32(_mm_setr_epi32(half,half+1,half+2,half+3),_mm_set1_epi32(root_start-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_and_si128(more,mask)));}
if constexpr(false){unsigned h4=jj/4;
if(h4>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));}
else if(h4+1>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
__m128i k4=_mm_cmpgt_epi32(_mm_setr_epi32(h4,h4+1,0,0),_mm_set1_epi32(root_start4-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(_mm_and_si128(m4,k4),root_zero128)));}}
return value;
};
{unsigned kend32=(31u*i<hi)?hi-31u*i:0u;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];volatile u32*pv=v;
_mm256_store_si256((__m256i*)v,v0);c[k]+=pv[0];c[k+1*i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=pv[0];c[k+9*i]+=pv[1];c[k+10*i]+=pv[2];c[k+11*i]+=pv[3];c[k+12*i]+=pv[4];c[k+13*i]+=pv[5];c[k+14*i]+=pv[6];c[k+15*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=pv[0];c[k+17*i]+=pv[1];c[k+18*i]+=pv[2];c[k+19*i]+=pv[3];c[k+20*i]+=pv[4];c[k+21*i]+=pv[5];c[k+22*i]+=pv[6];c[k+23*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=pv[0];c[k+25*i]+=pv[1];c[k+26*i]+=pv[2];c[k+27*i]+=pv[3];c[k+28*i]+=pv[4];c[k+29*i]+=pv[5];c[k+30*i]+=pv[6];c[k+31*i]+=pv[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];volatile u32*pv=v;_mm256_store_si256((__m256i*)v,vxy);c[k]+=pv[0];c[k+i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
}}
}else if(root_pair4){if(j/2>=root_start&&j/4>=root_start4){auto root_double=[&](__m256i value,unsigned jj){unsigned half=jj/2;
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));
unsigned h4=jj/4;__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));
return value;};
{unsigned kend32=(31u*i<hi)?hi-31u*i:0u;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];volatile u32*pv=v;
_mm256_store_si256((__m256i*)v,v0);c[k]+=pv[0];c[k+1*i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=pv[0];c[k+9*i]+=pv[1];c[k+10*i]+=pv[2];c[k+11*i]+=pv[3];c[k+12*i]+=pv[4];c[k+13*i]+=pv[5];c[k+14*i]+=pv[6];c[k+15*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=pv[0];c[k+17*i]+=pv[1];c[k+18*i]+=pv[2];c[k+19*i]+=pv[3];c[k+20*i]+=pv[4];c[k+21*i]+=pv[5];c[k+22*i]+=pv[6];c[k+23*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=pv[0];c[k+25*i]+=pv[1];c[k+26*i]+=pv[2];c[k+27*i]+=pv[3];c[k+28*i]+=pv[4];c[k+29*i]+=pv[5];c[k+30*i]+=pv[6];c[k+31*i]+=pv[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];volatile u32*pv=v;_mm256_store_si256((__m256i*)v,vxy);c[k]+=pv[0];c[k+i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
}}
}else{auto root_double=[&](__m256i value,unsigned jj){
if constexpr(!true)return value;
unsigned half=jj/2;
if(half>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));}
else if(half+3>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
__m128i mask=_mm_cmpgt_epi32(_mm_setr_epi32(half,half+1,half+2,half+3),_mm_set1_epi32(root_start-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_and_si128(more,mask)));}
if constexpr(true){unsigned h4=jj/4;
if(h4>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));}
else if(h4+1>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
__m128i k4=_mm_cmpgt_epi32(_mm_setr_epi32(h4,h4+1,0,0),_mm_set1_epi32(root_start4-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(_mm_and_si128(m4,k4),root_zero128)));}}
return value;
};
{unsigned kend32=(31u*i<hi)?hi-31u*i:0u;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];volatile u32*pv=v;
_mm256_store_si256((__m256i*)v,v0);c[k]+=pv[0];c[k+1*i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=pv[0];c[k+9*i]+=pv[1];c[k+10*i]+=pv[2];c[k+11*i]+=pv[3];c[k+12*i]+=pv[4];c[k+13*i]+=pv[5];c[k+14*i]+=pv[6];c[k+15*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=pv[0];c[k+17*i]+=pv[1];c[k+18*i]+=pv[2];c[k+19*i]+=pv[3];c[k+20*i]+=pv[4];c[k+21*i]+=pv[5];c[k+22*i]+=pv[6];c[k+23*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=pv[0];c[k+25*i]+=pv[1];c[k+26*i]+=pv[2];c[k+27*i]+=pv[3];c[k+28*i]+=pv[4];c[k+29*i]+=pv[5];c[k+30*i]+=pv[6];c[k+31*i]+=pv[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];volatile u32*pv=v;_mm256_store_si256((__m256i*)v,vxy);c[k]+=pv[0];c[k+i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
}}
}}else{if(j/2>=root_start){auto root_double=[&](__m256i value,unsigned jj){unsigned half=jj/2;
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));
return value;};
{unsigned kend32=(31u*i<hi)?hi-31u*i:0u;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];volatile u32*pv=v;
_mm256_store_si256((__m256i*)v,v0);c[k]+=pv[0];c[k+1*i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=pv[0];c[k+9*i]+=pv[1];c[k+10*i]+=pv[2];c[k+11*i]+=pv[3];c[k+12*i]+=pv[4];c[k+13*i]+=pv[5];c[k+14*i]+=pv[6];c[k+15*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=pv[0];c[k+17*i]+=pv[1];c[k+18*i]+=pv[2];c[k+19*i]+=pv[3];c[k+20*i]+=pv[4];c[k+21*i]+=pv[5];c[k+22*i]+=pv[6];c[k+23*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=pv[0];c[k+25*i]+=pv[1];c[k+26*i]+=pv[2];c[k+27*i]+=pv[3];c[k+28*i]+=pv[4];c[k+29*i]+=pv[5];c[k+30*i]+=pv[6];c[k+31*i]+=pv[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];volatile u32*pv=v;_mm256_store_si256((__m256i*)v,vxy);c[k]+=pv[0];c[k+i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
}}}else{auto root_double=[&](__m256i value,unsigned jj){
if constexpr(!true)return value;
unsigned half=jj/2;
if(half>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(more));}
else if(half+3>=root_start){
__m128i more=_mm_add_epi32(_mm_mullo_epi32(root_av2,_mm_loadu_si128((const __m128i*)(b+half))),_mm_mullo_epi32(root_bv2,_mm_loadu_si128((const __m128i*)(a+half))));
__m128i mask=_mm_cmpgt_epi32(_mm_setr_epi32(half,half+1,half+2,half+3),_mm_set1_epi32(root_start-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_and_si128(more,mask)));}
if constexpr(false){unsigned h4=jj/4;
if(h4>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(m4,root_zero128)));}
else if(h4+1>=root_start4){__m128i m4=_mm_add_epi32(_mm_mullo_epi32(root_av4,_mm_loadl_epi64((const __m128i*)(b+h4))),_mm_mullo_epi32(root_bv4,_mm_loadl_epi64((const __m128i*)(a+h4))));
__m128i k4=_mm_cmpgt_epi32(_mm_setr_epi32(h4,h4+1,0,0),_mm_set1_epi32(root_start4-1));
value=_mm256_add_epi32(value,_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(_mm_and_si128(m4,k4),root_zero128)));}}
return value;
};
{unsigned kend32=(31u*i<hi)?hi-31u*i:0u;
for(;k<kend32;j+=32,k+=32*i){
auto v0=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
v0=root_double(v0,j);
auto v1=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+8)),_mm256_mullo_epi32(vb,root_ld256(a+j+8)));
v1=root_double(v1,j+8);
auto v2=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+16)),_mm256_mullo_epi32(vb,root_ld256(a+j+16)));
v2=root_double(v2,j+16);
auto v3=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j+24)),_mm256_mullo_epi32(vb,root_ld256(a+j+24)));
v3=root_double(v3,j+24);
alignas(32)u32 v[8];volatile u32*pv=v;
_mm256_store_si256((__m256i*)v,v0);c[k]+=pv[0];c[k+1*i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v1);c[k+8*i]+=pv[0];c[k+9*i]+=pv[1];c[k+10*i]+=pv[2];c[k+11*i]+=pv[3];c[k+12*i]+=pv[4];c[k+13*i]+=pv[5];c[k+14*i]+=pv[6];c[k+15*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v2);c[k+16*i]+=pv[0];c[k+17*i]+=pv[1];c[k+18*i]+=pv[2];c[k+19*i]+=pv[3];c[k+20*i]+=pv[4];c[k+21*i]+=pv[5];c[k+22*i]+=pv[6];c[k+23*i]+=pv[7];
_mm256_store_si256((__m256i*)v,v3);c[k+24*i]+=pv[0];c[k+25*i]+=pv[1];c[k+26*i]+=pv[2];c[k+27*i]+=pv[3];c[k+28*i]+=pv[4];c[k+29*i]+=pv[5];c[k+30*i]+=pv[6];c[k+31*i]+=pv[7];
}
for(;k<kend;j+=8,k+=8*i){
auto vxy=_mm256_add_epi32(_mm256_mullo_epi32(va,root_ld256(b+j)),_mm256_mullo_epi32(vb,root_ld256(a+j)));
vxy=root_double(vxy,j);
alignas(32)u32 v[8];volatile u32*pv=v;_mm256_store_si256((__m256i*)v,vxy);c[k]+=pv[0];c[k+i]+=pv[1];c[k+2*i]+=pv[2];c[k+3*i]+=pv[3];c[k+4*i]+=pv[4];c[k+5*i]+=pv[5];c[k+6*i]+=pv[6];c[k+7*i]+=pv[7];
}}}}
record[1]=j;record[2]=k;
if(root_pair&&j/2>root_start)record[7]=j/2;if(root_pair4&&j/4>root_start4)record[10]=j/4;
}}
};runrows(std::integral_constant<unsigned,0>{});runrows(std::integral_constant<unsigned,1>{});runrows(std::integral_constant<unsigned,2>{});
}
for(unsigned g=0;g<3;++g){auto &v=coeffgroups[g];unsigned step=(g==0?5:(g==1?8:11));for(size_t q=0;q<v.size();q+=step){unsigned i=v[q];position[i]={v[q+1],v[q+2]};if(g>=1){unsigned j2=v[q+7];position[2*i]={j2,2u*i*j2};}if(g>=2){unsigned j4=v[q+10];position[4*i]={j4,4u*i*j4};}}}
for(unsigned i=3;i<bound;++i)if(i!=4&&i!=8&&i!=16)if(!(bound>3&&i==3)){unsigned j=position[i].j,k=position[i].k;for(;k<n;++j,k+=i)c[k]+=a[i]*b[j]+b[i]*a[j];}
for(unsigned i=1;i<bound;++i)c[u64(i)*i]+=a[i]*b[i];
sa+=reduce(vsa);sb+=reduce(vsb);c[0]=a[0]*sb+b[0]*sa-a[0]*b[0];
}
}
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){unsigned long long bd=1;while(bd*bd<n)++bd;if(bd>16)root_fast::multiply_t<true>(n,a,b,c);else root_fast::multiply_t<false>(n,a,b,c);}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 795.964 ms | 381 MB + 932 KB | Accepted | Score: 100 | 显示更多 |