代码

/* References:
 * saffah_codex_6a_agg3 https://duck.ac/submission/140270: adopted NTT/parser/formatter chassis (T=2012.506us);
 *   its complete upstream reference chain (#140111, #140026, #139999, #139959, #139903, #139892, #139878, #139611,
 *   saffah_v41f1017_agg4 #139420/#134328, saffah_cc_v41_agg1 #128293/#127125/#122189, and the original NTT base)
 *   is retained by reference in base_140270.cpp, from which this body was produced by string-aware comment removal.
 *   Purpose: name the reused work; this submission adds only the deletion described below.
 * Idea: the engine's forward DIF butterfly reduces its sum branch with vadd4(x,y)=min_epu32(x+y,x+y-4P). That
 *   reduction is the identity whenever x+y<4P (x+y-4P underflows and the unsigned min returns x+y). Several forward
 *   sites have a provable bound:
 *   (1) col_fuse256_128: the ra sum adds two parsed digits (<P each), the rc sum adds two Shoup outputs (<2P each);
 *       reduce rc modulo 2P instead of 4P (vred2) so every fused output is <2P, and delete the +4P offsets that are
 *       added before the Shoup products (4P = 0 mod P).
 *   (2) row_scale2: drop the row-0 early return; row 0's Montgomery table entry is the identity (RM, step 1), so all
 *       rows enter the row transform Montgomery-reduced (<1.01P) and the H=256 row-stage sum is <2.03P.
 *   (3) st4_fwd_jo: the H=256 sum is plain (inputs <1.01P); for H=128..8 the odd off-blocks (the [2H,4H) quarter of
 *       each 4H block) pair two diff outputs of the previous stage, every diff output is a Shoup result <2P, so the
 *       sum is <4P; the off loop is split into S (vadd4) and D (plain add) halves.
 *   (4) tail8_inv stage h=1 and col_tail3_dit_range stage h=1: inputs are Montgomery outputs (<1.05P), sums <2.1P.
 *   (5) generic forward column stage h=64: after the fuse all four row quarters are <2P, sums <4P; guarded by
 *       g_forward_active_rows<=N1/2 so act>256 keeps the original reduction.
 *   Deleted instructions only; every remaining value keeps its previous representative bound. Byte-identical output
 *   on 108/108 gates (28 lane inputs + 8 oracle inputs x 3 d->ol), vendor gcc 9.3.0 and system g++ 15.2.
 * Purpose: delete executed work that the DIF range proof shows is dead, at Ir parity with ticks.
 */
#pragma GCC optimize("O3","no-unroll-loops","rename-registers","ira-loop-pressure","modulo-sched","web","unswitch-loops","split-paths","gcse-after-reload","tree-vectorize","predictive-commoning","schedule-insns2","no-stack-protector","omit-frame-pointer","reorder-blocks-and-partition","sched-pressure","sched-spec-load","modulo-sched-allow-regmoves","no-tree-forwprop","no-tree-ch","no-tree-pre","no-cse-follow-jumps","no-inline-small-functions","schedule-insns","no-ira-share-spill-slots","no-sched-pressure","unroll-loops","no-if-conversion")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=skylake")
#include <cstdio>
#include <cstdint>
#include <cstring>
#include <cstdlib>
#include <immintrin.h>
typedef uint32_t u32;typedef uint64_t u64;typedef uint16_t u16;
#define TGT __attribute__((target("avx2")))
TGT static inline __m256i ldu256(const void *p){__m256i r;__asm__("vmovdqu %1, %0" : "=x"(r): "m"(*(const __m256i *)p));return r;}TGT static inline void stu256(void *p,__m256i v){__asm__ volatile("vmovdqu %1, %0" : "=m"(*(__m256i *)p): "x"(v));}TGT static inline void stm32(void *p,u32 v){__asm__ volatile("movl %1, %0" : "=m"(*(u32 *)p): "r"(v));}
#define P     13631489u
#define PM1   (P-1u)
#define P2    (2u*P)
#define P4    (4u*P)
#define P4M1  (4u*P-1u)
#define N1    512u
#define N2    512u
#define NN    (N1*N2)
#define CT_TB_a 128u
TGT static inline __m256i vmulhi32(__m256i a,__m256i b){__m256i e=_mm256_mul_epu32(a,b);__m256i o=_mm256_mul_epu32(_mm256_srli_epi64(a,32),_mm256_srli_epi64(b,32));e=_mm256_srli_epi64(e,32);return _mm256_blend_epi32(e,o,0xAA);}TGT static inline __m128i vmulhi32_128(__m128i a,__m128i b){__m128i e=_mm_mul_epu32(a,b);__m128i o=_mm_mul_epu32(_mm_srli_epi64(a,32),_mm_srli_epi64(b,32));e=_mm_srli_epi64(e,32);return _mm_blend_epi32(e,o,0xAA);}TGT static inline __m256i vadd4(__m256i x,__m256i y,__m256i p4,__m256i p4m1){__m256i u=_mm256_add_epi32(x,y);return _mm256_min_epu32(u,_mm256_sub_epi32(u,p4));}TGT static inline __m256i vdiff4(__m256i x,__m256i y,__m256i p4){return _mm256_add_epi32(_mm256_sub_epi32(x,y),p4);}TGT static inline __m256i vmulhi32b(__m256i a,__m256i b){__m256i e=_mm256_mul_epu32(a,b);__m256i o=_mm256_mul_epu32(_mm256_srli_epi64(a,32),b);e=_mm256_srli_epi64(e,32);return _mm256_blend_epi32(e,o,0xAA);}TGT static inline __m256i vshoupb(__m256i a,__m256i w,__m256i ws,__m256i pv){__m256i t=_mm256_mullo_epi32(a,w);__m256i q=vmulhi32b(a,ws);return _mm256_sub_epi32(t,_mm256_mullo_epi32(q,pv));}TGT static inline __m256i vshoup(__m256i a,__m256i w,__m256i ws,__m256i pv){__m256i t=_mm256_mullo_epi32(a,w);__m256i q=vmulhi32(a,ws);return _mm256_sub_epi32(t,_mm256_mullo_epi32(q,pv));}TGT static inline __m256i vmont(__m256i a,__m256i b,__m256i pv,__m256i pinv){const __m256i ao=_mm256_bsrli_epi128(a,4),bo=_mm256_bsrli_epi128(b,4);__m256i even=_mm256_mul_epu32(a,b),odd=_mm256_mul_epu32(ao,bo);const __m256i me=_mm256_mul_epu32(even,pinv),mo=_mm256_mul_epu32(odd,pinv);even=_mm256_add_epi64(even,_mm256_mul_epu32(me,pv));odd=_mm256_add_epi64(odd,_mm256_mul_epu32(mo,pv));return _mm256_or_si256(_mm256_bsrli_epi128(even,4),odd);}struct DI{unsigned long abi;const char *s;unsigned long sn;char *o;unsigned long ol;unsigned long os;char *e;unsigned long el;unsigned long es;const char *IB;unsigned long IBl;char *OB;unsigned long OBl;unsigned long tsc;}__attribute__((packed));static DI *find_duck(int argc,char **argv){unsigned long *p =(unsigned long *)(argv + argc + 1);while(*p)p++;p++;for(int i = 0;i < 32 && p[0];i++,p += 2)if(p[0] == 0x6b637564UL){DI *d =(DI *)p[1];return(d && d->abi == 40)? d : 0;}return 0;}static u32 powmod32(u32 a,u32 e){u32 r=1;while(e){if(e&1)r=(u32)((u64)r*a%P);a=(u32)((u64)a*a%P);e>>=1;}return r;}static inline u32 ws_of(u32 w){return(u32)(((u64)w<<32)/P);}struct SwTabs{u32 CW[64+N1],CWS[64+N1],JW[64+N1],JWS[64+N1];u32 RW[64+N2],RWS[64+N2],IW[64+N2],IWS[64+N2];u32 REV1[N1];u32 g_pinv,g_R2,g_w,g_ninv;};constexpr u32 cpow(u32 a,u32 e){u32 r=1;while(e){if(e&1)r=(u32)((u64)r*a%P);a=(u32)((u64)a*a%P);e>>=1;}return r;}constexpr u32 cws(u32 w){return(u32)(((u64)w<<32)/P);}constexpr void ctab(u32*W,u32*WS,u32 L,u32 w){u32 h=L>>1;for(;;){u32 off=L-2*h,st=cpow(w,L/(2*h)),acc=1;for(u32 j=0;j<h;j++){W[off+j]=acc;WS[off+j]=cws(acc);acc=(u32)((u64)acc*st%P);}if(h==1)break;h>>=1;}}constexpr SwTabs make_sw(){SwTabs t{};{u32 iv=1;for(int q=0;q<5;q++)iv*=2u-P*iv;t.g_pinv=0u-iv;}t.g_R2=(u32)(((u64)((1ull<<32)%P)*((1ull<<32)%P))%P);t.g_w=cpow(3,(P-1)/NN);t.g_ninv=cpow(NN,P-2);u32 wn1=cpow(t.g_w,N2),wn2=cpow(t.g_w,N1);ctab(t.CW,t.CWS,N1,wn1);ctab(t.JW,t.JWS,N1,cpow(wn1,P-2));ctab(t.RW,t.RWS,N2,wn2);ctab(t.IW,t.IWS,N2,cpow(wn2,P-2));{u32 l1=0;while((1u<<l1)<N1)l1++;for(u32 i=0;i<N1;i++){u32 r=0;for(u32 b=0;b<l1;b++)if(i&(1u<<b))r|=1u<<(l1-1-b);t.REV1[i]=r;}}return t;}alignas(64)static constexpr SwTabs SW = make_sw();
#define CW     (SW.CW)
#define CWS    (SW.CWS)
#define JW     (SW.JW)
#define JWS    (SW.JWS)
#define RW     (SW.RW)
#define RWS    (SW.RWS)
#define IW     (SW.IW)
#define IWS    (SW.IWS)
#define REV1   (SW.REV1)
#define g_pinv (SW.g_pinv)
#define g_R2   (SW.g_R2)
#define g_w    (SW.g_w)
#define g_ninv (SW.g_ninv)
static u32 g_A_store[NN],g_B_store[NN];static u32 *g_A = g_A_store;static u32 *g_B = g_B_store;static void init_small(){}TGT static void low3_dif(u32*p,const u32*LT,const u32*LTS){const __m256i p4=_mm256_set1_epi32((int)P4),p4m1=_mm256_set1_epi32((int)P4M1),pv=_mm256_set1_epi32((int)P);const __m128i p4s=_mm256_castsi256_si128(p4),p4m1s=_mm256_castsi256_si128(p4m1),pvs=_mm256_castsi256_si128(pv);__m256i x=ldu256((const void*)p);__m128i xl=_mm256_castsi256_si128(x),xh=_mm256_extracti128_si256(x,1);__m128i u=_mm_add_epi32(xl,xh);u=_mm_sub_epi32(u,_mm_and_si128(_mm_cmpgt_epi32(u,p4m1s),p4s));__m128i d=_mm_add_epi32(_mm_sub_epi32(xl,xh),p4s);__m128i t4=_mm_loadu_si128((const __m128i*)LT),ts4=_mm_loadu_si128((const __m128i*)LTS);__m128i dm=_mm_sub_epi32(_mm_mullo_epi32(d,t4),_mm_mullo_epi32(vmulhi32_128(d,ts4),pvs));__m128i yl=u,yh=dm;__m128i tw2=_mm_setr_epi32(0,0,1,(int)LT[5]);__m128i tws2=_mm_setr_epi32(0,0,(int)ws_of(1),(int)LTS[5]);
#define DIF_H2(a) do{ __m128i t_=_mm_shuffle_epi32(a,_MM_SHUFFLE(1,0,3,2)); \
__m128i u_=_mm_add_epi32(a,t_); __m128i u2=_mm_sub_epi32(u_,_mm_and_si128(_mm_cmpgt_epi32(u_,p4m1s),p4s)); \
__m128i d_=_mm_add_epi32(_mm_sub_epi32(a,t_),p4s); \
__m128i ds_=_mm_shuffle_epi32(d_,_MM_SHUFFLE(1,0,1,0)); \
__m128i dd_=_mm_sub_epi32(_mm_mullo_epi32(ds_,tw2),_mm_mullo_epi32(vmulhi32_128(ds_,tws2),pvs)); \
a=_mm_blend_epi32(u2,dd_,0xC); }while(0)
#define DIF_H1(a) do{ __m128i t_=_mm_shuffle_epi32(a,_MM_SHUFFLE(2,3,0,1)); \
__m128i u_=_mm_add_epi32(a,t_); __m128i u2=_mm_sub_epi32(u_,_mm_and_si128(_mm_cmpgt_epi32(u_,p4m1s),p4s)); \
__m128i d_=_mm_add_epi32(_mm_sub_epi32(a,t_),p4s); \
d_=_mm_sub_epi32(d_,_mm_and_si128(_mm_cmpgt_epi32(d_,p4m1s),p4s)); \
__m128i ds_=_mm_shuffle_epi32(d_,_MM_SHUFFLE(2,3,0,1)); \
a=_mm_blend_epi32(u2,ds_,0xA); }while(0)
DIF_H2(yl);DIF_H2(yh);DIF_H1(yl);DIF_H1(yh);stu256((void*)p,_mm256_inserti128_si256(_mm256_castsi128_si256(yl),yh,1));}TGT static void low3_dit(u32*p,const u32*LT,const u32*LTS){const __m256i p4=_mm256_set1_epi32((int)P4),p4m1=_mm256_set1_epi32((int)P4M1),pv=_mm256_set1_epi32((int)P);const __m128i p4s=_mm256_castsi256_si128(p4),p4m1s=_mm256_castsi256_si128(p4m1),pvs=_mm256_castsi256_si128(pv);__m256i x=ldu256((const void*)p);__m128i yl=_mm256_castsi256_si128(x),yh=_mm256_extracti128_si256(x,1);
#define DIT_H1(a) do{ __m128i t_=_mm_shuffle_epi32(a,_MM_SHUFFLE(2,3,0,1)); \
__m128i s_=_mm_add_epi32(a,t_); __m128i s2=_mm_sub_epi32(s_,_mm_and_si128(_mm_cmpgt_epi32(s_,p4m1s),p4s)); \
__m128i d_=_mm_add_epi32(_mm_sub_epi32(a,t_),p4s); \
d_=_mm_sub_epi32(d_,_mm_and_si128(_mm_cmpgt_epi32(d_,p4m1s),p4s)); \
__m128i ds_=_mm_shuffle_epi32(d_,_MM_SHUFFLE(2,3,0,1)); \
a=_mm_blend_epi32(s2,ds_,0xA); }while(0)
DIT_H1(yl);DIT_H1(yh);__m128i tw2=_mm_setr_epi32(1,(int)LT[5],0,0);__m128i tws2=_mm_setr_epi32(1,(int)LTS[5],0,0);
#define DIT_H2(a) do{ __m128i t_=_mm_shuffle_epi32(a,_MM_SHUFFLE(1,0,3,2)); \
__m128i v_=_mm_sub_epi32(_mm_mullo_epi32(t_,tw2),_mm_mullo_epi32(vmulhi32_128(t_,tws2),pvs)); \
__m128i s_=_mm_add_epi32(a,v_); __m128i s2=_mm_sub_epi32(s_,_mm_and_si128(_mm_cmpgt_epi32(s_,p4m1s),p4s)); \
__m128i d_=_mm_add_epi32(_mm_sub_epi32(a,v_),p4s); \
__m128i dd_=_mm_shuffle_epi32(d_,_MM_SHUFFLE(1,0,1,0)); \
a=_mm_blend_epi32(s2,dd_,0xC); }while(0)
DIT_H2(yl);DIT_H2(yh);{__m128i t4=_mm_loadu_si128((const __m128i*)LT),ts4=_mm_loadu_si128((const __m128i*)LTS);__m128i t=_mm_sub_epi32(_mm_mullo_epi32(yh,t4),_mm_mullo_epi32(vmulhi32_128(yh,ts4),pvs));__m128i s=_mm_add_epi32(yl,t);s=_mm_sub_epi32(s,_mm_and_si128(_mm_cmpgt_epi32(s,p4m1s),p4s));__m128i d=_mm_add_epi32(_mm_sub_epi32(yl,t),p4s);yl=s;yh=d;}stu256((void*)p,_mm256_inserti128_si256(_mm256_castsi128_si256(yl),yh,1));}typedef __m256i V;TGT static inline V vshx(V a,V w,V ws,V pv){V t=_mm256_mullo_epi32(a,w);V q=vmulhi32(a,ws);return _mm256_sub_epi32(t,_mm256_mullo_epi32(q,pv));}TGT static inline V vredx(V a,V p4,V p4m1){return _mm256_min_epu32(a,_mm256_sub_epi32(a,p4));}TGT static inline V vadd4x(V x,V y,V p4,V p4m1){V u=_mm256_add_epi32(x,y);return _mm256_min_epu32(u,_mm256_sub_epi32(u,p4));}TGT static inline V vdiff4x(V x,V y,V p4){return _mm256_add_epi32(_mm256_sub_epi32(x,y),p4);}TGT static inline void tail8_dif(u32*q,V w4,V ws4,V w2,V ws2_x,V p4,V p4m1,V pv){for(int v=0;v<8;v++){V*pv_=(V*)(q+8*v);V x=pv_[0];V t=_mm256_permute2x128_si256(x,x,0x01);V s=vadd4x(x,t,p4,p4m1);V d=vshx(vdiff4x(t,x,p4),w4,ws4,pv);x=_mm256_blend_epi32(s,d,0xF0);t=_mm256_shuffle_epi32(x,0x4E);s=vadd4x(x,t,p4,p4m1);d=vshx(_mm256_shuffle_epi32(vdiff4x(x,t,p4),0x4E),w2,ws2_x,pv);x=_mm256_blend_epi32(s,d,0xCC);t=_mm256_shuffle_epi32(x,0xB1);s=vadd4x(x,t,p4,p4m1);d=vredx(_mm256_shuffle_epi32(vdiff4x(x,t,p4),0xB1),p4,p4m1);pv_[0]=_mm256_blend_epi32(s,d,0xAA);}}TGT static inline void tail8_dit(u32*q,V w4lo,V ws4lo,V w2d,V ws2d,V p4,V p4m1,V pv){for(int v=0;v<8;v++){V*pv_=(V*)(q+8*v);V x=pv_[0];V t=_mm256_shuffle_epi32(x,0xB1);V s=vadd4x(x,t,p4,p4m1);V d=vredx(_mm256_shuffle_epi32(vdiff4x(x,t,p4),0xB1),p4,p4m1);x=_mm256_blend_epi32(s,d,0xAA);t=_mm256_shuffle_epi32(x,0x4E);V val=vshx(t,w2d,ws2d,pv);s=vadd4x(x,val,p4,p4m1);d=_mm256_shuffle_epi32(vdiff4x(x,val,p4),0x4E);x=_mm256_blend_epi32(s,d,0xCC);t=vshx(_mm256_permute2x128_si256(x,x,0x01),w4lo,ws4lo,pv);s=vadd4x(x,t,p4,p4m1);d=_mm256_permute2x128_si256(vdiff4x(x,t,p4),vdiff4x(x,t,p4),0x01);pv_[0]=_mm256_blend_epi32(s,d,0xF0);}}TGT static inline void tailconst(const u32*LT,const u32*LTS,V&w4,V&ws4,V&w4lo,V&ws4lo,V&w2,V&ws2_x,V&w2d,V&ws2d){__m128i l4=_mm_loadu_si128((const __m128i*)LT),ls4=_mm_loadu_si128((const __m128i*)LTS);w4=_mm256_inserti128_si256(_mm256_setzero_si256(),l4,1);ws4=_mm256_inserti128_si256(_mm256_setzero_si256(),ls4,1);w4lo=_mm256_castsi128_si256(l4);ws4lo=_mm256_castsi128_si256(ls4);w2=_mm256_setr_epi32(0,0,LT[4],LT[5],0,0,LT[4],LT[5]);ws2_x=_mm256_setr_epi32(0,0,LTS[4],LTS[5],0,0,LTS[4],LTS[5]);w2d=_mm256_setr_epi32(1,LT[5],0,0,1,LT[5],0,0);ws2d=_mm256_setr_epi32(1,LTS[5],0,0,1,LTS[5],0,0);}
#define CP4   _mm256_set1_epi32((int)P4)
#define CP4M1 _mm256_set1_epi32((int)P4M1)
#define CPV   _mm256_set1_epi32((int)P)
template<u32 H> TGT static void st_fwd(u32*row,const u32*w,const u32*ws){const __m256i p4=CP4,p4m1=CP4M1,pv=CPV;for(u32 s=0;s<N2;s+=2*H){u32*r0=row+s,*r1=r0+H;for(u32 j=0;j<H;j+=8){__m256i x=ldu256((const void*)(r0+j)),y=ldu256((const void*)(r1+j));stu256((void*)(r0+j),vadd4(x,y,p4,p4m1));stu256((void*)(r1+j),vshoup(vdiff4(x,y,p4),ldu256((const void*)(w+j)),ldu256((const void*)(ws+j)),pv));}}}template<u32 H> TGT static void st_inv(u32*row,const u32*w,const u32*ws){const __m256i p4=CP4,p4m1=CP4M1,pv=CPV;for(u32 s=0;s<N2;s+=2*H){u32*r0=row+s,*r1=r0+H;for(u32 j=0;j<H;j+=8){__m256i x=ldu256((const void*)(r0+j)),y=ldu256((const void*)(r1+j));__m256i t=vshoup(y,ldu256((const void*)(w+j)),ldu256((const void*)(ws+j)),pv);__m256i sa=_mm256_add_epi32(x,t);sa=_mm256_min_epu32(sa,_mm256_sub_epi32(sa,p4));__m256i ds=_mm256_add_epi32(_mm256_sub_epi32(x,t),p4);ds=_mm256_min_epu32(ds,_mm256_sub_epi32(ds,p4));stu256((void*)(r0+j),sa);stu256((void*)(r1+j),ds);}}}template<u32 H> TGT static void st2_fwd(u32*ra,u32*rb,const u32*w,const u32*ws){const __m256i p4=CP4,p4m1=CP4M1,pv=CPV;for(u32 s=0;s<N2;s+=2*H){u32*a0=ra+s,*a1=a0+H,*b0=rb+s,*b1=b0+H;for(u32 j=0;j<H;j+=8){_mm_prefetch((const char*)(a0+j+128),_MM_HINT_T0);_mm_prefetch((const char*)(b0+j+128),_MM_HINT_T0);__m256i x=ldu256((const void*)(a0+j)),y=ldu256((const void*)(a1+j));__m256i u=ldu256((const void*)(b0+j)),v=ldu256((const void*)(b1+j));__m256i wv=ldu256((const void*)(w+j)),wsv=ldu256((const void*)(ws+j));stu256((void*)(a0+j),vadd4(x,y,p4,p4m1));stu256((void*)(a1+j),vshoup(vdiff4(x,y,p4),wv,wsv,pv));stu256((void*)(b0+j),vadd4(u,v,p4,p4m1));stu256((void*)(b1+j),vshoup(vdiff4(u,v,p4),wv,wsv,pv));}}}template<u32 H> TGT static void st2_inv(u32*ra,u32*rb,const u32*w,const u32*ws){const __m256i p4=CP4,p4m1=CP4M1,pv=CPV;for(u32 s=0;s<N2;s+=2*H){u32*a0=ra+s,*a1=a0+H,*b0=rb+s,*b1=b0+H;for(u32 j=0;j<H;j+=8){_mm_prefetch((const char*)(a0+j+128),_MM_HINT_T0);_mm_prefetch((const char*)(b0+j+128),_MM_HINT_T0);__m256i x=ldu256((const void*)(a0+j)),y=ldu256((const void*)(a1+j));__m256i u=ldu256((const void*)(b0+j)),v=ldu256((const void*)(b1+j));__m256i wv=ldu256((const void*)(w+j)),wsv=ldu256((const void*)(ws+j));__m256i t=vshoup(y,wv,wsv,pv),q=vshoup(v,wv,wsv,pv);__m256i sa=_mm256_add_epi32(x,t);__m256i sb=_mm256_add_epi32(u,q);__m256i da=_mm256_add_epi32(_mm256_sub_epi32(x,t),p4);__m256i db=_mm256_add_epi32(_mm256_sub_epi32(u,q),p4);stu256((void*)(a0+j),sa);stu256((void*)(a1+j),da);stu256((void*)(b0+j),sb);stu256((void*)(b1+j),db);}}}TGT static void tail_fwd_so(u32*row,V w4,V ws4,V w2,V ws2_x,V p4,V p4m1,V pv){for(u32 i=0;i<N2;i+=8){V x=ldu256((const void*)(row+i));V t=_mm256_permute2x128_si256(x,x,0x01);V s=vadd4x(x,t,p4,p4m1);V d=vshx(vdiff4x(t,x,p4),w4,ws4,pv);stu256((void*)(row+i),_mm256_blend_epi32(s,d,0xF0));}for(u32 i=0;i<N2;i+=8){V x=ldu256((const void*)(row+i));V t=_mm256_shuffle_epi32(x,0x4E);V s=vadd4x(x,t,p4,p4m1);V d=vshx(_mm256_shuffle_epi32(vdiff4x(x,t,p4),0x4E),w2,ws2_x,pv);stu256((void*)(row+i),_mm256_blend_epi32(s,d,0xCC));}for(u32 i=0;i<N2;i+=8){V x=ldu256((const void*)(row+i));V t=_mm256_shuffle_epi32(x,0xB1);V s=vadd4x(x,t,p4,p4m1);V d=vredx(_mm256_shuffle_epi32(vdiff4x(x,t,p4),0xB1),p4,p4m1);stu256((void*)(row+i),_mm256_blend_epi32(s,d,0xAA));}}TGT static void tail_inv_so(u32*row,V w4lo,V ws4lo,V w2d,V ws2d,V p4,V p4m1,V pv){for(u32 i=0;i<N2;i+=8){V x=ldu256((const void*)(row+i));V t=_mm256_shuffle_epi32(x,0xB1);V s=vadd4x(x,t,p4,p4m1);V d=vredx(_mm256_shuffle_epi32(vdiff4x(x,t,p4),0xB1),p4,p4m1);stu256((void*)(row+i),_mm256_blend_epi32(s,d,0xAA));}for(u32 i=0;i<N2;i+=8){V x=ldu256((const void*)(row+i));V t=_mm256_shuffle_epi32(x,0x4E);V val=vshx(t,w2d,ws2d,pv);V s=vadd4x(x,val,p4,p4m1);V d=_mm256_shuffle_epi32(vdiff4x(x,val,p4),0x4E);stu256((void*)(row+i),_mm256_blend_epi32(s,d,0xCC));}for(u32 i=0;i<N2;i+=8){V x=ldu256((const void*)(row+i));V t=vshx(_mm256_permute2x128_si256(x,x,0x01),w4lo,ws4lo,pv);V s=vadd4x(x,t,p4,p4m1);V d=_mm256_permute2x128_si256(vdiff4x(x,t,p4),vdiff4x(x,t,p4),0x01);stu256((void*)(row+i),_mm256_blend_epi32(s,d,0xF0));}}TGT static void row_dif(u32*row,u32 dir){const u32*W = dir? IW : RW;const u32*WS = dir? IWS : RWS;V w4,ws4,w4lo,ws4lo,w2,ws2_x,w2d,ws2d;tailconst(W+(N2-8),WS+(N2-8),w4,ws4,w4lo,ws4lo,w2,ws2_x,w2d,ws2d);if(!dir){st_fwd<256>(row,W+(N2-512),WS+(N2-512));st_fwd<128>(row,W+(N2-256),WS+(N2-256));st_fwd<64>(row,W+(N2-128),WS+(N2-128));st_fwd<32>(row,W+(N2-64),WS+(N2-64));st_fwd<16>(row,W+(N2-32),WS+(N2-32));st_fwd<8>(row,W+(N2-16),WS+(N2-16));tail_fwd_so(row,w4,ws4,w2,ws2_x,CP4,CP4M1,CPV);}else{tail_inv_so(row,w4lo,ws4lo,w2d,ws2d,CP4,CP4M1,CPV);st_inv<8>(row,W+(N2-16),WS+(N2-16));st_inv<16>(row,W+(N2-32),WS+(N2-32));st_inv<32>(row,W+(N2-64),WS+(N2-64));st_inv<64>(row,W+(N2-128),WS+(N2-128));st_inv<128>(row,W+(N2-256),WS+(N2-256));st_inv<256>(row,W+(N2-512),WS+(N2-512));}}TGT static void row_dif2(u32*ra,u32*rb,u32 dir){const u32*W = dir? IW : RW;const u32*WS = dir? IWS : RWS;V w4,ws4,w4lo,ws4lo,w2,ws2_x,w2d,ws2d;tailconst(W+(N2-8),WS+(N2-8),w4,ws4,w4lo,ws4lo,w2,ws2_x,w2d,ws2d);if(!dir){st2_fwd<256>(ra,rb,W+(N2-512),WS+(N2-512));st2_fwd<128>(ra,rb,W+(N2-256),WS+(N2-256));st2_fwd<64>(ra,rb,W+(N2-128),WS+(N2-128));st2_fwd<32>(ra,rb,W+(N2-64),WS+(N2-64));st2_fwd<16>(ra,rb,W+(N2-32),WS+(N2-32));st2_fwd<8>(ra,rb,W+(N2-16),WS+(N2-16));tail_fwd_so(ra,w4,ws4,w2,ws2_x,CP4,CP4M1,CPV);tail_fwd_so(rb,w4,ws4,w2,ws2_x,CP4,CP4M1,CPV);}else{tail_inv_so(ra,w4lo,ws4lo,w2d,ws2d,CP4,CP4M1,CPV);tail_inv_so(rb,w4lo,ws4lo,w2d,ws2d,CP4,CP4M1,CPV);st2_inv<8>(ra,rb,W+(N2-16),WS+(N2-16));st2_inv<16>(ra,rb,W+(N2-32),WS+(N2-32));st2_inv<32>(ra,rb,W+(N2-64),WS+(N2-64));st2_inv<64>(ra,rb,W+(N2-128),WS+(N2-128));st2_inv<128>(ra,rb,W+(N2-256),WS+(N2-256));st2_inv<256>(ra,rb,W+(N2-512),WS+(N2-512));}}TGT static void col_tail3_dif(u32*a,const u32*W,const u32*WS){const __m256i p4=_mm256_set1_epi32((int)P4),p4m1=_mm256_set1_epi32((int)P4M1),pv=_mm256_set1_epi32((int)P);__m256i w4[4],ws4[4],w2[2],ws2_x[2];for(int k=0;k<4;k++){w4[k]=_mm256_set1_epi32((int)W[N1-8+k]);ws4[k]=_mm256_set1_epi32((int)WS[N1-8+k]);}for(int k=0;k<2;k++){w2[k]=_mm256_set1_epi32((int)W[N1-4+k]);ws2_x[k]=_mm256_set1_epi32((int)WS[N1-4+k]);}for(u32 s=0;s<N1;s+=8){u32*r0=a+(size_t)s*N2;for(u32 c=0;c<N2;c+=8){_mm_prefetch((const char*)(r0+c+256),_MM_HINT_T0);_mm_prefetch((const char*)(r0+4*N2+c+256),_MM_HINT_T0);__m256i x0=ldu256((const void*)(r0+c)),x4=ldu256((const void*)(r0+4*N2+c));__m256i x1=ldu256((const void*)(r0+N2+c)),x5=ldu256((const void*)(r0+5*N2+c));__m256i x2=ldu256((const void*)(r0+2*N2+c)),x6=ldu256((const void*)(r0+6*N2+c));__m256i x3=ldu256((const void*)(r0+3*N2+c)),x7=ldu256((const void*)(r0+7*N2+c));__m256i y0=vadd4(x0,x4,p4,p4m1),z0=vshoup(vdiff4(x0,x4,p4),w4[0],ws4[0],pv);__m256i y1=vadd4(x1,x5,p4,p4m1),z1=vshoup(vdiff4(x1,x5,p4),w4[1],ws4[1],pv);__m256i y2=vadd4(x2,x6,p4,p4m1),z2=vshoup(vdiff4(x2,x6,p4),w4[2],ws4[2],pv);__m256i y3=vadd4(x3,x7,p4,p4m1),z3=vshoup(vdiff4(x3,x7,p4),w4[3],ws4[3],pv);__m256i p0=vadd4(y0,y2,p4,p4m1),q0=vshoup(vdiff4(y0,y2,p4),w2[0],ws2_x[0],pv);__m256i p1=vadd4(y1,y3,p4,p4m1),q1=vshoup(vdiff4(y1,y3,p4),w2[1],ws2_x[1],pv);__m256i p2=vadd4(z0,z2,p4,p4m1),q2=vshoup(vdiff4(z0,z2,p4),w2[0],ws2_x[0],pv);__m256i p3=vadd4(z1,z3,p4,p4m1),q3=vshoup(vdiff4(z1,z3,p4),w2[1],ws2_x[1],pv);stu256((void*)(r0+c),vadd4(p0,p1,p4,p4m1));stu256((void*)(r0+N2+c),vredx(vdiff4(p0,p1,p4),p4,p4m1));stu256((void*)(r0+2*N2+c),vadd4(q0,q1,p4,p4m1));stu256((void*)(r0+3*N2+c),vredx(vdiff4(q0,q1,p4),p4,p4m1));stu256((void*)(r0+4*N2+c),vadd4(p2,p3,p4,p4m1));stu256((void*)(r0+5*N2+c),vredx(vdiff4(p2,p3,p4),p4,p4m1));stu256((void*)(r0+6*N2+c),vadd4(q2,q3,p4,p4m1));stu256((void*)(r0+7*N2+c),vredx(vdiff4(q2,q3,p4),p4,p4m1));}}}TGT static void col_tail3_dif_range(u32*a,const u32*W,const u32*WS,u32 s0,u32 tb){const __m256i p4=_mm256_set1_epi32((int)P4),p4m1=_mm256_set1_epi32((int)P4M1),pv=_mm256_set1_epi32((int)P);__m256i w4[4],ws4[4],w2[2],ws2_x[2];for(int k=0;k<4;k++){w4[k]=_mm256_set1_epi32((int)W[N1-8+k]);ws4[k]=_mm256_set1_epi32((int)WS[N1-8+k]);}for(int k=0;k<2;k++){w2[k]=_mm256_set1_epi32((int)W[N1-4+k]);ws2_x[k]=_mm256_set1_epi32((int)WS[N1-4+k]);}for(u32 s=s0;s<s0+tb;s+=16){u32*r0=a+(size_t)s*N2;for(u32 c=0;c<N2;c+=8){_mm_prefetch((const char*)(r0+c+256),_MM_HINT_T0);_mm_prefetch((const char*)(r0+4*N2+c+256),_MM_HINT_T0);__m256i x0=ldu256((const void*)(r0+c)),x4=ldu256((const void*)(r0+4*N2+c));__m256i x1=ldu256((const void*)(r0+N2+c)),x5=ldu256((const void*)(r0+5*N2+c));__m256i x2=ldu256((const void*)(r0+2*N2+c)),x6=ldu256((const void*)(r0+6*N2+c));__m256i x3=ldu256((const void*)(r0+3*N2+c)),x7=ldu256((const void*)(r0+7*N2+c));__m256i y0=vadd4(x0,x4,p4,p4m1),z0=vredx(vdiff4(x0,x4,p4),p4,p4m1);__m256i y1=vadd4(x1,x5,p4,p4m1),z1=vshoup(vdiff4(x1,x5,p4),w4[1],ws4[1],pv);__m256i y2=vadd4(x2,x6,p4,p4m1),z2=vshoup(vdiff4(x2,x6,p4),w4[2],ws4[2],pv);__m256i y3=vadd4(x3,x7,p4,p4m1),z3=vshoup(vdiff4(x3,x7,p4),w4[3],ws4[3],pv);__m256i p0=vadd4(y0,y2,p4,p4m1),q0=vredx(vdiff4(y0,y2,p4),p4,p4m1);__m256i p1=vadd4(y1,y3,p4,p4m1),q1=vshoup(vdiff4(y1,y3,p4),w2[1],ws2_x[1],pv);__m256i p2=vadd4(z0,z2,p4,p4m1),q2=vredx(vdiff4(z0,z2,p4),p4,p4m1);__m256i p3=_mm256_add_epi32(z1,z3),q3=vshoup(vdiff4(z1,z3,p4),w2[1],ws2_x[1],pv);stu256((void*)(r0+c),vadd4(p0,p1,p4,p4m1));stu256((void*)(r0+N2+c),vredx(vdiff4(p0,p1,p4),p4,p4m1));stu256((void*)(r0+2*N2+c),vadd4(q0,q1,p4,p4m1));stu256((void*)(r0+3*N2+c),vredx(vdiff4(q0,q1,p4),p4,p4m1));stu256((void*)(r0+4*N2+c),vadd4(p2,p3,p4,p4m1));stu256((void*)(r0+5*N2+c),vredx(vdiff4(p2,p3,p4),p4,p4m1));stu256((void*)(r0+6*N2+c),vadd4(q2,q3,p4,p4m1));stu256((void*)(r0+7*N2+c),vredx(vdiff4(q2,q3,p4),p4,p4m1));}}
for(u32 s=s0+8;s<s0+tb;s+=16){u32*r0=a+(size_t)s*N2;for(u32 c=0;c<N2;c+=8){_mm_prefetch((const char*)(r0+c+256),_MM_HINT_T0);_mm_prefetch((const char*)(r0+4*N2+c+256),_MM_HINT_T0);__m256i x0=ldu256((const void*)(r0+c)),x4=ldu256((const void*)(r0+4*N2+c));__m256i x1=ldu256((const void*)(r0+N2+c)),x5=ldu256((const void*)(r0+5*N2+c));__m256i x2=ldu256((const void*)(r0+2*N2+c)),x6=ldu256((const void*)(r0+6*N2+c));__m256i x3=ldu256((const void*)(r0+3*N2+c)),x7=ldu256((const void*)(r0+7*N2+c));__m256i y0=_mm256_add_epi32(x0,x4),y1=_mm256_add_epi32(x1,x5),y2=_mm256_add_epi32(x2,x6),y3=_mm256_add_epi32(x3,x7);__m256i z0=vredx(vdiff4(x0,x4,p4),p4,p4m1);__m256i z1=vshoup(vdiff4(x1,x5,p4),w4[1],ws4[1],pv);__m256i z2=vshoup(vdiff4(x2,x6,p4),w4[2],ws4[2],pv);__m256i z3=vshoup(vdiff4(x3,x7,p4),w4[3],ws4[3],pv);__m256i p0=vadd4(y0,y2,p4,p4m1),q0=vredx(vdiff4(y0,y2,p4),p4,p4m1);__m256i p1=vadd4(y1,y3,p4,p4m1),q1=vshoup(vdiff4(y1,y3,p4),w2[1],ws2_x[1],pv);__m256i p2=vadd4(z0,z2,p4,p4m1),q2=vredx(vdiff4(z0,z2,p4),p4,p4m1);__m256i p3=_mm256_add_epi32(z1,z3),q3=vshoup(vdiff4(z1,z3,p4),w2[1],ws2_x[1],pv);stu256((void*)(r0+c),vadd4(p0,p1,p4,p4m1));stu256((void*)(r0+N2+c),vredx(vdiff4(p0,p1,p4),p4,p4m1));stu256((void*)(r0+2*N2+c),vadd4(q0,q1,p4,p4m1));stu256((void*)(r0+3*N2+c),vredx(vdiff4(q0,q1,p4),p4,p4m1));stu256((void*)(r0+4*N2+c),vadd4(p2,p3,p4,p4m1));stu256((void*)(r0+5*N2+c),vredx(vdiff4(p2,p3,p4),p4,p4m1));stu256((void*)(r0+6*N2+c),vadd4(q2,q3,p4,p4m1));stu256((void*)(r0+7*N2+c),vredx(vdiff4(q2,q3,p4),p4,p4m1));}}
}TGT static inline void bfd(__m256i&u,__m256i&v,__m256i w,__m256i ws,__m256i p4,__m256i p4m1,__m256i pv){__m256i t=vshoup(v,w,ws,pv);__m256i s=vadd4(u,t,p4,p4m1);v=vredx(vdiff4(u,t,p4),p4,p4m1);u=s;}TGT static void col_tail3_dit(u32*a,const u32*W,const u32*WS){const __m256i p4=_mm256_set1_epi32((int)P4),p4m1=_mm256_set1_epi32((int)P4M1),pv=_mm256_set1_epi32((int)P);__m256i w4[4],ws4[4],w2[2],ws2_x[2];for(int k=0;k<4;k++){w4[k]=_mm256_set1_epi32((int)W[N1-8+k]);ws4[k]=_mm256_set1_epi32((int)WS[N1-8+k]);}for(int k=0;k<2;k++){w2[k]=_mm256_set1_epi32((int)W[N1-4+k]);ws2_x[k]=_mm256_set1_epi32((int)WS[N1-4+k]);}__m256i w1v=_mm256_set1_epi32((int)W[N1-2]),ws1v=_mm256_set1_epi32((int)WS[N1-2]);for(u32 s=0;s<N1;s+=8){u32*r0=a+(size_t)s*N2;for(u32 c=0;c<N2;c+=8){_mm_prefetch((const char*)(r0+c+256),_MM_HINT_T0);_mm_prefetch((const char*)(r0+4*N2+c+256),_MM_HINT_T0);__m256i x0=ldu256((const void*)(r0+c)),x4=ldu256((const void*)(r0+4*N2+c));__m256i x1=ldu256((const void*)(r0+N2+c)),x5=ldu256((const void*)(r0+5*N2+c));__m256i x2=ldu256((const void*)(r0+2*N2+c)),x6=ldu256((const void*)(r0+6*N2+c));__m256i x3=ldu256((const void*)(r0+3*N2+c)),x7=ldu256((const void*)(r0+7*N2+c));bfd(x0,x1,w1v,ws1v,p4,p4m1,pv);bfd(x2,x3,w1v,ws1v,p4,p4m1,pv);bfd(x4,x5,w1v,ws1v,p4,p4m1,pv);bfd(x6,x7,w1v,ws1v,p4,p4m1,pv);bfd(x0,x2,w2[0],ws2_x[0],p4,p4m1,pv);bfd(x1,x3,w2[1],ws2_x[1],p4,p4m1,pv);bfd(x4,x6,w2[0],ws2_x[0],p4,p4m1,pv);bfd(x5,x7,w2[1],ws2_x[1],p4,p4m1,pv);bfd(x0,x4,w4[0],ws4[0],p4,p4m1,pv);bfd(x1,x5,w4[1],ws4[1],p4,p4m1,pv);bfd(x2,x6,w4[2],ws4[2],p4,p4m1,pv);bfd(x3,x7,w4[3],ws4[3],p4,p4m1,pv);stu256((void*)(r0+c),x0);stu256((void*)(r0+4*N2+c),x4);stu256((void*)(r0+N2+c),x1);stu256((void*)(r0+5*N2+c),x5);stu256((void*)(r0+2*N2+c),x2);stu256((void*)(r0+6*N2+c),x6);stu256((void*)(r0+3*N2+c),x3);stu256((void*)(r0+7*N2+c),x7);}}}TGT static inline void bfd1(__m256i&u,__m256i&v,__m256i p4,__m256i p4m1){__m256i s=vadd4(u,v,p4,p4m1);v=vredx(vdiff4(u,v,p4),p4,p4m1);u=s;}TGT static void col_tail3_dit_range(u32*a,const u32*W,const u32*WS,u32 s0,u32 tb){const __m256i p4=_mm256_set1_epi32((int)P4),p4m1=_mm256_set1_epi32((int)P4M1),pv=_mm256_set1_epi32((int)P);__m256i w4[4],ws4[4],w2[2],ws2_x[2];for(int k=0;k<4;k++){w4[k]=_mm256_set1_epi32((int)W[N1-8+k]);ws4[k]=_mm256_set1_epi32((int)WS[N1-8+k]);}for(int k=0;k<2;k++){w2[k]=_mm256_set1_epi32((int)W[N1-4+k]);ws2_x[k]=_mm256_set1_epi32((int)WS[N1-4+k]);}__m256i w1v=_mm256_set1_epi32((int)W[N1-2]),ws1v=_mm256_set1_epi32((int)WS[N1-2]);for(u32 s=s0;s<s0+tb;s+=8){u32*r0=a+(size_t)s*N2;for(u32 c=0;c<N2;c+=8){_mm_prefetch((const char*)(r0+c+256),_MM_HINT_T0);_mm_prefetch((const char*)(r0+4*N2+c+256),_MM_HINT_T0);__m256i x0=ldu256((const void*)(r0+c)),x4=ldu256((const void*)(r0+4*N2+c));__m256i x1=ldu256((const void*)(r0+N2+c)),x5=ldu256((const void*)(r0+5*N2+c));__m256i x2=ldu256((const void*)(r0+2*N2+c)),x6=ldu256((const void*)(r0+6*N2+c));__m256i x3=ldu256((const void*)(r0+3*N2+c)),x7=ldu256((const void*)(r0+7*N2+c));{__m256i s0_=_mm256_add_epi32(x0,x1);x1=vredx(vdiff4(x0,x1,p4),p4,p4m1);x0=s0_;}{__m256i s1_=_mm256_add_epi32(x2,x3);x3=vredx(vdiff4(x2,x3,p4),p4,p4m1);x2=s1_;}{__m256i s2_=_mm256_add_epi32(x4,x5);x5=vredx(vdiff4(x4,x5,p4),p4,p4m1);x4=s2_;}{__m256i s3_=_mm256_add_epi32(x6,x7);x7=vredx(vdiff4(x6,x7,p4),p4,p4m1);x6=s3_;}bfd1(x0,x2,p4,p4m1);bfd(x1,x3,w2[1],ws2_x[1],p4,p4m1,pv);bfd1(x4,x6,p4,p4m1);bfd(x5,x7,w2[1],ws2_x[1],p4,p4m1,pv);bfd1(x0,x4,p4,p4m1);bfd(x1,x5,w4[1],ws4[1],p4,p4m1,pv);bfd(x2,x6,w4[2],ws4[2],p4,p4m1,pv);bfd(x3,x7,w4[3],ws4[3],p4,p4m1,pv);stu256((void*)(r0+c),x0);stu256((void*)(r0+4*N2+c),x4);stu256((void*)(r0+N2+c),x1);stu256((void*)(r0+5*N2+c),x5);stu256((void*)(r0+2*N2+c),x2);stu256((void*)(r0+6*N2+c),x6);stu256((void*)(r0+3*N2+c),x3);stu256((void*)(r0+7*N2+c),x7);}}}TGT static inline __m256i norm_final(__m256i v,__m256i p2,__m256i p){const __m256i n=_mm256_srli_epi32(v,20);const __m256i q=_mm256_mulhi_epu16(n,_mm256_set1_epi16(5042));const __m256i r=_mm256_sub_epi32(v,_mm256_mullo_epi32(q,p));return _mm256_min_epu32(r,_mm256_add_epi32(r,p));}static u32 g_output_len;TGT static void final_col_norm(u32*a,u32 dstlen){const __m256i p4=_mm256_set1_epi32((int)P4),pv=_mm256_set1_epi32((int)P);const __m256i p2=_mm256_set1_epi32((int)P2);for(u32 j=0;j<(N1>>1);j++){if((size_t)j*N2 >= dstlen)break;u32*r0=a+(size_t)j*N2,*r1=r0+(size_t)(N1>>1)*N2;const bool need_second =(size_t)(j+(N1>>1))*N2 < dstlen;__m256i wv=_mm256_set1_epi32((int)JW[j]);__m256i wsv=_mm256_set1_epi32((int)JWS[j]);for(u32 c=0;c<N2;c+=64){__m256i x0=ldu256((const void*)(r0+c)),y0=ldu256((const void*)(r1+c));__m256i x1=ldu256((const void*)(r0+c+8)),y1=ldu256((const void*)(r1+c+8));__m256i x2=ldu256((const void*)(r0+c+16)),y2=ldu256((const void*)(r1+c+16));__m256i x3=ldu256((const void*)(r0+c+24)),y3=ldu256((const void*)(r1+c+24));__m256i x4=ldu256((const void*)(r0+c+32)),y4=ldu256((const void*)(r1+c+32));__m256i x5=ldu256((const void*)(r0+c+40)),y5=ldu256((const void*)(r1+c+40));__m256i x6=ldu256((const void*)(r0+c+48)),y6=ldu256((const void*)(r1+c+48));__m256i x7=ldu256((const void*)(r0+c+56)),y7=ldu256((const void*)(r1+c+56));__m256i t0=vshoupb(y0,wv,wsv,pv);__m256i t1=vshoupb(y1,wv,wsv,pv);__m256i t2=vshoupb(y2,wv,wsv,pv);__m256i t3=vshoupb(y3,wv,wsv,pv);__m256i t4=vshoupb(y4,wv,wsv,pv);__m256i t5=vshoupb(y5,wv,wsv,pv);__m256i t6=vshoupb(y6,wv,wsv,pv);__m256i t7=vshoupb(y7,wv,wsv,pv);__m256i s0=_mm256_add_epi32(x0,t0);__m256i s1=_mm256_add_epi32(x1,t1);__m256i s2=_mm256_add_epi32(x2,t2);__m256i s3=_mm256_add_epi32(x3,t3);__m256i s4=_mm256_add_epi32(x4,t4);__m256i s5=_mm256_add_epi32(x5,t5);__m256i s6=_mm256_add_epi32(x6,t6);__m256i s7=_mm256_add_epi32(x7,t7);stu256((void*)(r0+c),norm_final(s0,p2,pv));stu256((void*)(r0+c+8),norm_final(s1,p2,pv));stu256((void*)(r0+c+16),norm_final(s2,p2,pv));stu256((void*)(r0+c+24),norm_final(s3,p2,pv));stu256((void*)(r0+c+32),norm_final(s4,p2,pv));stu256((void*)(r0+c+40),norm_final(s5,p2,pv));stu256((void*)(r0+c+48),norm_final(s6,p2,pv));stu256((void*)(r0+c+56),norm_final(s7,p2,pv));if(need_second){__m256i d0=_mm256_add_epi32(_mm256_sub_epi32(x0,t0),p4);__m256i d1=_mm256_add_epi32(_mm256_sub_epi32(x1,t1),p4);__m256i d2=_mm256_add_epi32(_mm256_sub_epi32(x2,t2),p4);__m256i d3=_mm256_add_epi32(_mm256_sub_epi32(x3,t3),p4);__m256i d4=_mm256_add_epi32(_mm256_sub_epi32(x4,t4),p4);__m256i d5=_mm256_add_epi32(_mm256_sub_epi32(x5,t5),p4);__m256i d6=_mm256_add_epi32(_mm256_sub_epi32(x6,t6),p4);__m256i d7=_mm256_add_epi32(_mm256_sub_epi32(x7,t7),p4);stu256((void*)(r1+c),norm_final(d0,p2,pv));stu256((void*)(r1+c+8),norm_final(d1,p2,pv));stu256((void*)(r1+c+16),norm_final(d2,p2,pv));stu256((void*)(r1+c+24),norm_final(d3,p2,pv));stu256((void*)(r1+c+32),norm_final(d4,p2,pv));stu256((void*)(r1+c+40),norm_final(d5,p2,pv));stu256((void*)(r1+c+48),norm_final(d6,p2,pv));stu256((void*)(r1+c+56),norm_final(d7,p2,pv));}}}}static u32 g_forward_active_rows=N1/2;TGT static inline __m256i vred2(__m256i x,__m256i y){__m256i u=_mm256_add_epi32(x,y);const __m256i p2=_mm256_set1_epi32((int)P2);return _mm256_min_epu32(u,_mm256_sub_epi32(u,p2));}
TGT static void col_fuse256_128(u32*a,const u32*W,const u32*WS){const __m256i p4=_mm256_set1_epi32((int)P4),p4m1=_mm256_set1_epi32((int)P4M1),pv=_mm256_set1_epi32((int)P);const u32 act=g_forward_active_rows;const u32 jb=act>128u?((act-128u<128u)?act-128u:128u):0u;const u32 ja=act<128u?act:128u;for(u32 j=0;j<ja;j++){u32*ra=a+(size_t)j*N2,*rb=ra+(size_t)128*N2,*rc=ra+(size_t)256*N2,*rd=ra+(size_t)384*N2;const __m256i w12=_mm256_set1_epi32((int)W[256+j]),ws12=_mm256_set1_epi32((int)WS[256+j]);if(j<jb){const __m256i wa=_mm256_set1_epi32((int)W[j]),wsa=_mm256_set1_epi32((int)WS[j]);const __m256i wb=_mm256_set1_epi32((int)W[j+128]),wsb=_mm256_set1_epi32((int)WS[j+128]);for(u32 c=0;c<N2;c+=32){__m256i a0=ldu256((const void*)(ra+c)),a1=ldu256((const void*)(ra+c+8));__m256i a2=ldu256((const void*)(ra+c+16)),a3=ldu256((const void*)(ra+c+24));__m256i b0=ldu256((const void*)(rb+c)),b1=ldu256((const void*)(rb+c+8));__m256i b2=ldu256((const void*)(rb+c+16)),b3=ldu256((const void*)(rb+c+24));stu256((void*)(ra+c),_mm256_add_epi32(a0,b0));stu256((void*)(ra+c+8),_mm256_add_epi32(a1,b1));stu256((void*)(ra+c+16),_mm256_add_epi32(a2,b2));stu256((void*)(ra+c+24),_mm256_add_epi32(a3,b3));stu256((void*)(rb+c),vshoupb(vdiff4(a0,b0,p4),w12,ws12,pv));stu256((void*)(rb+c+8),vshoupb(vdiff4(a1,b1,p4),w12,ws12,pv));stu256((void*)(rb+c+16),vshoupb(vdiff4(a2,b2,p4),w12,ws12,pv));stu256((void*)(rb+c+24),vshoupb(vdiff4(a3,b3,p4),w12,ws12,pv));a0=vshoupb(a0,wa,wsa,pv);a1=vshoupb(a1,wa,wsa,pv);a2=vshoupb(a2,wa,wsa,pv);a3=vshoupb(a3,wa,wsa,pv);b0=vshoupb(b0,wb,wsb,pv);b1=vshoupb(b1,wb,wsb,pv);b2=vshoupb(b2,wb,wsb,pv);b3=vshoupb(b3,wb,wsb,pv);stu256((void*)(rc+c),vred2(a0,b0));stu256((void*)(rc+c+8),vred2(a1,b1));stu256((void*)(rc+c+16),vred2(a2,b2));stu256((void*)(rc+c+24),vred2(a3,b3));stu256((void*)(rd+c),vshoupb(vdiff4(a0,b0,p4),w12,ws12,pv));stu256((void*)(rd+c+8),vshoupb(vdiff4(a1,b1,p4),w12,ws12,pv));stu256((void*)(rd+c+16),vshoupb(vdiff4(a2,b2,p4),w12,ws12,pv));stu256((void*)(rd+c+24),vshoupb(vdiff4(a3,b3,p4),w12,ws12,pv));}}else{const __m256i wa=_mm256_set1_epi32((int)W[j]),wsa=_mm256_set1_epi32((int)WS[j]);for(u32 c=0;c<N2;c+=32){__m256i a0=ldu256((const void*)(ra+c)),a1=ldu256((const void*)(ra+c+8));__m256i a2=ldu256((const void*)(ra+c+16)),a3=ldu256((const void*)(ra+c+24));stu256((void*)(rb+c),vshoupb(a0,w12,ws12,pv));stu256((void*)(rb+c+8),vshoupb(a1,w12,ws12,pv));stu256((void*)(rb+c+16),vshoupb(a2,w12,ws12,pv));stu256((void*)(rb+c+24),vshoupb(a3,w12,ws12,pv));a0=vshoupb(a0,wa,wsa,pv);a1=vshoupb(a1,wa,wsa,pv);a2=vshoupb(a2,wa,wsa,pv);a3=vshoupb(a3,wa,wsa,pv);stu256((void*)(rc+c),a0);stu256((void*)(rc+c+8),a1);stu256((void*)(rc+c+16),a2);stu256((void*)(rc+c+24),a3);stu256((void*)(rd+c),vshoupb(a0,w12,ws12,pv));stu256((void*)(rd+c+8),vshoupb(a1,w12,ws12,pv));stu256((void*)(rd+c+16),vshoupb(a2,w12,ws12,pv));stu256((void*)(rd+c+24),vshoupb(a3,w12,ws12,pv));}}}}TGT __attribute__((noinline))static void col_tr(u32*a,u32 dir){const __m256i p4=_mm256_set1_epi32((int)P4),p4m1=_mm256_set1_epi32((int)P4M1),pv=_mm256_set1_epi32((int)P);const u32*W = dir? JW : CW;const u32*WS = dir? JWS : CWS;if(!dir){if(g_forward_active_rows<=N1/2)col_fuse256_128(a,W,WS);for(int ph=0;ph<2;ph++){if(ph==0 && g_forward_active_rows<=N1/2)continue;const u32 TB = ph ? CT_TB_a : N1,h0 = ph ?(CT_TB_a>>1):(N1>>1),h1 = ph ? 8u : CT_TB_a;for(u32 s0=0;s0<N1;s0+=TB){for(u32 h=h0;h>=h1;h>>=1){const u32*w=W+(N1-2*h),*ws=WS+(N1-2*h);for(u32 s=s0;s<s0+TB;s+=2*h){u32*r0=a+(size_t)s*N2,*r1=r0+(size_t)h*N2;for(u32 j=0;j<h;j++,r0+=N2,r1+=N2){__m256i wv=_mm256_set1_epi32((int)w[j]),wsv=_mm256_set1_epi32((int)ws[j]);if(j+h>=g_forward_active_rows){if(j>=g_forward_active_rows){continue;}for(u32 c=0;c<N2;c+=32){__m256i x0=ldu256((const void*)(r0+c));__m256i x1=ldu256((const void*)(r0+c+8));__m256i x2=ldu256((const void*)(r0+c+16));__m256i x3=ldu256((const void*)(r0+c+24));stu256((void*)(r1+c),vshoupb(_mm256_add_epi32(x0,p4),wv,wsv,pv));stu256((void*)(r1+c+8),vshoupb(_mm256_add_epi32(x1,p4),wv,wsv,pv));stu256((void*)(r1+c+16),vshoupb(_mm256_add_epi32(x2,p4),wv,wsv,pv));stu256((void*)(r1+c+24),vshoupb(_mm256_add_epi32(x3,p4),wv,wsv,pv));}continue;}if(h==64u&&g_forward_active_rows<=N1/2u){for(u32 c=0;c<N2;c+=32){_mm_prefetch((const char*)(r0+c+512),_MM_HINT_T0);_mm_prefetch((const char*)(r1+c+512),_MM_HINT_T0);__m256i x0=ldu256((const void*)(r0+c)),y0=ldu256((const void*)(r1+c));__m256i x1=ldu256((const void*)(r0+c+8)),y1=ldu256((const void*)(r1+c+8));__m256i x2=ldu256((const void*)(r0+c+16)),y2=ldu256((const void*)(r1+c+16));__m256i x3=ldu256((const void*)(r0+c+24)),y3=ldu256((const void*)(r1+c+24));stu256((void*)(r0+c),_mm256_add_epi32(x0,y0));stu256((void*)(r0+c+8),_mm256_add_epi32(x1,y1));stu256((void*)(r0+c+16),_mm256_add_epi32(x2,y2));stu256((void*)(r0+c+24),_mm256_add_epi32(x3,y3));stu256((void*)(r1+c),vshoupb(vdiff4(x0,y0,p4),wv,wsv,pv));stu256((void*)(r1+c+8),vshoupb(vdiff4(x1,y1,p4),wv,wsv,pv));stu256((void*)(r1+c+16),vshoupb(vdiff4(x2,y2,p4),wv,wsv,pv));stu256((void*)(r1+c+24),vshoupb(vdiff4(x3,y3,p4),wv,wsv,pv));}}else{for(u32 c=0;c<N2;c+=32){_mm_prefetch((const char*)(r0+c+512),_MM_HINT_T0);_mm_prefetch((const char*)(r1+c+512),_MM_HINT_T0);__m256i x0=ldu256((const void*)(r0+c)),y0=ldu256((const void*)(r1+c));__m256i x1=ldu256((const void*)(r0+c+8)),y1=ldu256((const void*)(r1+c+8));__m256i x2=ldu256((const void*)(r0+c+16)),y2=ldu256((const void*)(r1+c+16));__m256i x3=ldu256((const void*)(r0+c+24)),y3=ldu256((const void*)(r1+c+24));stu256((void*)(r0+c),vadd4(x0,y0,p4,p4m1));stu256((void*)(r0+c+8),vadd4(x1,y1,p4,p4m1));stu256((void*)(r0+c+16),vadd4(x2,y2,p4,p4m1));stu256((void*)(r0+c+24),vadd4(x3,y3,p4,p4m1));stu256((void*)(r1+c),vshoupb(vdiff4(x0,y0,p4),wv,wsv,pv));stu256((void*)(r1+c+8),vshoupb(vdiff4(x1,y1,p4),wv,wsv,pv));stu256((void*)(r1+c+16),vshoupb(vdiff4(x2,y2,p4),wv,wsv,pv));stu256((void*)(r1+c+24),vshoupb(vdiff4(x3,y3,p4),wv,wsv,pv));}}}}}if(ph)col_tail3_dif_range(a,W,WS,s0,CT_TB_a);}}}else{for(int ph=0;ph<2;ph++){const u32 TB = ph ? N1 : CT_TB_a,h0 = ph ? CT_TB_a : 8u,h1 = ph ?(N1>>2):(CT_TB_a>>1);for(u32 s0=0;s0<N1;s0+=TB){if(!ph)col_tail3_dit_range(a,W,WS,s0,CT_TB_a);for(u32 h=h0;h<=h1;h<<=1){const u32*w=W+(N1-2*h),*ws=WS+(N1-2*h);for(u32 s=s0;s<s0+TB;s+=2*h){u32*r0=a+(size_t)s*N2,*r1=r0+(size_t)h*N2;for(u32 j=0;j<h;j++,r0+=N2,r1+=N2){__m256i wv=_mm256_set1_epi32((int)w[j]),wsv=_mm256_set1_epi32((int)ws[j]);for(u32 c=0;c<N2;c+=32){_mm_prefetch((const char*)(r0+c+512),_MM_HINT_T0);_mm_prefetch((const char*)(r1+c+512),_MM_HINT_T0);__m256i x0=ldu256((const void*)(r0+c)),y0=ldu256((const void*)(r1+c));__m256i x1=ldu256((const void*)(r0+c+8)),y1=ldu256((const void*)(r1+c+8));__m256i x2=ldu256((const void*)(r0+c+16)),y2=ldu256((const void*)(r1+c+16));__m256i x3=ldu256((const void*)(r0+c+24)),y3=ldu256((const void*)(r1+c+24));__m256i t0=vshoupb(y0,wv,wsv,pv),t1=vshoupb(y1,wv,wsv,pv),t2=vshoupb(y2,wv,wsv,pv),t3=vshoupb(y3,wv,wsv,pv);__m256i s0=_mm256_add_epi32(x0,t0);__m256i s1=_mm256_add_epi32(x1,t1);__m256i s2=_mm256_add_epi32(x2,t2);__m256i s3=_mm256_add_epi32(x3,t3);__m256i d0=_mm256_add_epi32(_mm256_sub_epi32(x0,t0),p4);__m256i d1=_mm256_add_epi32(_mm256_sub_epi32(x1,t1),p4);__m256i d2=_mm256_add_epi32(_mm256_sub_epi32(x2,t2),p4);__m256i d3=_mm256_add_epi32(_mm256_sub_epi32(x3,t3),p4);stu256((void*)(r0+c),s0);stu256((void*)(r0+c+8),s1);stu256((void*)(r0+c+16),s2);stu256((void*)(r0+c+24),s3);stu256((void*)(r1+c),d0);stu256((void*)(r1+c+8),d1);stu256((void*)(r1+c+16),d2);stu256((void*)(r1+c+24),d3);}}}}}}final_col_norm(a,g_output_len);}}
#define CVSTR 40
struct CvTable{u32 v[(size_t)512*CVSTR];};constexpr u32 powmod_const(u32 a,u32 e){u32 r=1;while(e){if(e&1)r=(u32)((u64)r*a%P);a=(u32)((u64)a*a%P);e>>=1;}return r;}constexpr CvTable make_cv_const(bool inverse){CvTable table{};const u32 RM=(u32)((1ull<<32)%P);u32 root=powmod_const(3,(P-1)/NN);if(inverse)root=powmod_const(root,P-2);const u32 ninv=powmod_const(NN,P-2);for(u32 i=0;i<N1;i++){u32 rev=0;for(u32 b=0;b<9;b++)if(i&(1u<<b))rev|=1u<<(8-b);u32 row_root=powmod_const(root,rev);u32 value=inverse?(u32)((u64)ninv*RM%P):RM;for(u32 t=0;t<32;t++){table.v[(size_t)i*CVSTR+t]=value;value=(u32)((u64)value*row_root%P);}table.v[(size_t)i*CVSTR+32]=inverse?(u32)((u64)value*NN%P):value;u32 step=powmod_const(row_root,32);table.v[(size_t)i*CVSTR+33]=step;table.v[(size_t)i*CVSTR+34]=(u32)(((u64)step<<32)/P);}return table;}alignas(64)static constexpr CvTable g_cvF=make_cv_const(false);alignas(64)static constexpr CvTable g_cvI=make_cv_const(true);TGT static void row_scale(u32*row,const u32*cv){if(cv==g_cvI.v){constexpr u32 w=powmod_const(NN,P-2),ws=(u32)(((u64)w<<32)/P);const __m256i wv=_mm256_set1_epi32(w),wsv=_mm256_set1_epi32(ws),pv=CPV;for(u32 j=0;j<N2;j+=8)stu256(row+j,vshoupb(ldu256(row+j),wv,wsv,pv));return;}const __m256i pv=_mm256_set1_epi32((int)P);__m256i pinv=_mm256_set1_epi32((int)g_pinv);__m256i c0=ldu256((const void*)(cv+0));__m256i c1=ldu256((const void*)(cv+8));__m256i c2=ldu256((const void*)(cv+16));__m256i c3=ldu256((const void*)(cv+24));__m256i stp=_mm256_set1_epi32((int)cv[33]);__m256i stps=_mm256_set1_epi32((int)cv[34]);for(u32 j=0;;j+=32){__m256i x0=ldu256((const void*)(row+j));__m256i x1=ldu256((const void*)(row+j+8));__m256i x2=ldu256((const void*)(row+j+16));__m256i x3=ldu256((const void*)(row+j+24));stu256((void*)(row+j),vmont(x0,c0,pv,pinv));stu256((void*)(row+j+8),vmont(x1,c1,pv,pinv));stu256((void*)(row+j+16),vmont(x2,c2,pv,pinv));stu256((void*)(row+j+24),vmont(x3,c3,pv,pinv));if(j==N2-32)break;c0=vshoupb(c0,stp,stps,pv);c1=vshoupb(c1,stp,stps,pv);c2=vshoupb(c2,stp,stps,pv);c3=vshoupb(c3,stp,stps,pv);}}TGT static void row_scale2(u32*ra,u32*rb,const u32*cv){const __m256i pv=CPV;__m256i pinv=_mm256_set1_epi32((int)g_pinv);__m256i c0=ldu256((const void*)(cv+0));__m256i c1=ldu256((const void*)(cv+8));__m256i c2=ldu256((const void*)(cv+16));__m256i c3=ldu256((const void*)(cv+24));__m256i stp=_mm256_set1_epi32((int)cv[33]);__m256i stps=_mm256_set1_epi32((int)cv[34]);for(u32 j=0;;j+=32){__m256i x0=ldu256((const void*)(ra+j)),x1=ldu256((const void*)(ra+j+8));__m256i x2=ldu256((const void*)(ra+j+16)),x3=ldu256((const void*)(ra+j+24));__m256i y0=ldu256((const void*)(rb+j)),y1=ldu256((const void*)(rb+j+8));__m256i y2=ldu256((const void*)(rb+j+16)),y3=ldu256((const void*)(rb+j+24));stu256((void*)(ra+j),vmont(x0,c0,pv,pinv));stu256((void*)(ra+j+8),vmont(x1,c1,pv,pinv));stu256((void*)(ra+j+16),vmont(x2,c2,pv,pinv));stu256((void*)(ra+j+24),vmont(x3,c3,pv,pinv));stu256((void*)(rb+j),vmont(y0,c0,pv,pinv));stu256((void*)(rb+j+8),vmont(y1,c1,pv,pinv));stu256((void*)(rb+j+16),vmont(y2,c2,pv,pinv));stu256((void*)(rb+j+24),vmont(y3,c3,pv,pinv));if(j==N2-32)break;c0=vshoupb(c0,stp,stps,pv);c1=vshoupb(c1,stp,stps,pv);c2=vshoupb(c2,stp,stps,pv);c3=vshoupb(c3,stp,stps,pv);}}static u32 g_pw[N1],g_pwi[N1];TGT static void fwd_pre(u32*a,const u32*src,u32 srclen){u32 rows=(srclen+N2-1)/N2;if(a!=src)for(u32 i=0;i<rows;i++){u32 lim=((i+1)*(u64)N2<=srclen)?N2:(u32)(srclen-(u64)i*N2);memcpy(a+(size_t)i*N2,src+(size_t)i*N2,(size_t)lim*4);}g_forward_active_rows=rows;col_tr(a,0);}TGT static void inv(u32*dst,u32 dstlen,u32*a){for(u32 i=0;i<N1;i+=2){row_dif2(a+(size_t)i*N2,a+(size_t)(i+1)*N2,1);row_scale(a+(size_t)i*N2,g_cvI.v+(size_t)i*CVSTR);row_scale(a+(size_t)(i+1)*N2,g_cvI.v+(size_t)(i+1)*CVSTR);}col_tr(a,1);{const __m256i pv=_mm256_set1_epi32((int)P),p2v=_mm256_set1_epi32((int)P2);const __m256i pm1=_mm256_set1_epi32((int)PM1),p2m1=_mm256_set1_epi32((int)P2-1);u32 i=0;for(;i+8<=dstlen;i+=8){__m256i v=ldu256((const void*)(a+i));v=_mm256_min_epu32(v,_mm256_sub_epi32(v,p2v));v=_mm256_min_epu32(v,_mm256_sub_epi32(v,pv));stu256((void*)(dst+i),v);}for(;i<dstlen;i++){u32 v=a[i];if(v>=P2)v-=P2;if(v>=P)v-=P;dst[i]=v;}}}TGT static void pw_row(u32*a,u32*b){const __m256i pv=_mm256_set1_epi32((int)P);__m256i pinv=_mm256_set1_epi32((int)g_pinv);for(u32 i=0;i<N2;i+=8)stu256((void*)(a+i),vmont(ldu256((const void*)(a+i)),ldu256((const void*)(b+i)),pv,pinv));}static const char* g_ip;static const char* g_ie;static inline u32 nxt(){while(g_ip<g_ie &&(*g_ip<'0'||*g_ip>'9'))g_ip++;u32 v=0;while(g_ip<g_ie&&*g_ip>='0'&&*g_ip<='9')v=v*10+(u32)(*g_ip++-'0');return v;}struct FmtTabs{u32 P2T[100];u32 T4[10000];u32 T3S[1000];u32 P2TS[100];};constexpr FmtTabs make_fmt(){FmtTabs t{};for(u32 i=0;i<100;i++)t.P2T[i]=(u32)('0'+i/10)|((u32)('0'+i%10)<<8);for(u32 a=0;a<100;a++){u32 hh=t.P2T[a],o=a*100u;for(u32 b=0;b<100;b++)t.T4[o+b]=hh|(t.P2T[b]<<16);}for(u32 c=0;c<10;c++){u32 hi=(u32)('0'+c),o=c*100u;for(u32 r=0;r<100;r++)t.T3S[o+r]=((hi|(t.P2T[r]<<8))<<8)|0x20u;}for(u32 i=0;i<100;i++)t.P2TS[i]=(t.P2T[i]<<8)|0x20u;return t;}alignas(64)static constexpr FmtTabs FMT = make_fmt();
#define P2T (FMT.P2T)
#define T4  (FMT.T4)
#define T3S (FMT.T3S)
#define P2TS (FMT.P2TS)
static void init_t4(){}static void init_t3(){}static void init_b2d(){}
#define B2D_RSH ((u32)((1ull<<32)%P))
TGT static inline __m256i digit_montgomery(__m256i d){
return _mm256_sub_epi32(_mm256_slli_epi32(d,20),_mm256_madd_epi16(d,_mm256_set1_epi32(315)));
}
TGT static void parse_fast(const char*p,const char*e,u32 la,u32 lb,u32*nzA,u32*nzB){u32 k=0;const u32 TOT=la+lb;const __m256i lo0=_mm256_set1_epi8((char)('0'-1));const __m256i shufE=_mm256_setr_epi8(0,2,4,6,8,10,12,14,-1,-1,-1,-1,-1,-1,-1,-1,0,2,4,6,8,10,12,14,-1,-1,-1,-1,-1,-1,-1,-1);const __m256i shufO=_mm256_setr_epi8(1,3,5,7,9,11,13,15,-1,-1,-1,-1,-1,-1,-1,-1,1,3,5,7,9,11,13,15,-1,-1,-1,-1,-1,-1,-1,-1);const __m128i dasc=_mm_set1_epi8((char)0x30);const __m256i rv=_mm256_set1_epi32((int)B2D_RSH);__m128i vA=_mm_setzero_si128(),vB=_mm_setzero_si128();u32 sA=0,sB=0;u32 exp=1u;__m256i shuf=shufE;while(p+32<=e && k+16u<=la){__m256i v=ldu256((const void*)p);u32 m=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(v,lo0));if(m==exp || m==0x55555555u || m==0xAAAAAAAAu){if(m!=exp){exp=m;shuf=(m==0x55555555u)?shufE:shufO;}__m256i s=_mm256_shuffle_epi8(v,shuf);__m256i q=_mm256_permute4x64_epi64(s,0xD8);__m128i x=_mm_sub_epi8(_mm256_castsi256_si128(q),dasc);__m256i w0=_mm256_cvtepu8_epi32(x);__m256i w1=_mm256_cvtepu8_epi32(_mm_srli_si128(x,8));vA=_mm_or_si128(vA,x);stu256((void*)(g_A+k),w0);stu256((void*)(g_A+k+8),w1);k+=16u;p+=32;continue;}while(m){int b=__builtin_ctz(m);m&=m-1;u32 d=(u32)((unsigned char)p[b]-'0');if(k<la){g_A[k]=d;sA|=d;}else{g_B[k-la]=(d*B2D_RSH);sB|=d;}k++;}p+=32;}for(;p<e && k<la;p++){u32 c=(u32)(*p-'0');if(c>9u)continue;g_A[k]=c;sA|=c;k++;}exp=1u;shuf=shufE;while(p+32<=e && k+16u<=TOT){__m256i v=ldu256((const void*)p);u32 m=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(v,lo0));if(m==exp || m==0x55555555u || m==0xAAAAAAAAu){if(m!=exp){exp=m;shuf=(m==0x55555555u)?shufE:shufO;}__m256i s=_mm256_shuffle_epi8(v,shuf);__m256i q=_mm256_permute4x64_epi64(s,0xD8);__m128i x=_mm_sub_epi8(_mm256_castsi256_si128(q),dasc);__m256i w0=_mm256_cvtepu8_epi32(x);__m256i w1=_mm256_cvtepu8_epi32(_mm_srli_si128(x,8));vB=_mm_or_si128(vB,x);u32 t=k-la;stu256((void*)(g_B+t),digit_montgomery(w0));stu256((void*)(g_B+t+8),digit_montgomery(w1));k+=16u;p+=32;continue;}while(m){int b=__builtin_ctz(m);m&=m-1;u32 d=(u32)((unsigned char)p[b]-'0');if(k<la){g_A[k]=d;sA|=d;}else{g_B[k-la]=(d*B2D_RSH);sB|=d;}k++;}p+=32;}for(;p<e && k<TOT;p++){u32 c=(u32)(*p-'0');if(c>9u)continue;if(k<la){g_A[k]=c;sA|=c;}else{g_B[k-la]=(c*B2D_RSH);sB|=c;}k++;}sA|=(u32)(_mm_testz_si128(vA,vA)?0u:1u);sB|=(u32)(_mm_testz_si128(vB,vB)?0u:1u);*nzA=sA;*nzB=sB;}TGT static bool all_zero_coeff(const u32*a,u32 n){__m256i acc=_mm256_setzero_si256();u32 i=0;for(;i+8<=n;i+=8)acc=_mm256_or_si256(acc,ldu256((const void*)(a+i)));if(!_mm256_testz_si256(acc,acc))return false;for(;i<n;i++)if(a[i])return false;return true;}TGT static size_t emit_zeros(char*o,u32 n){const size_t len=(size_t)n*2;size_t i=0;const __m256i zz=_mm256_set1_epi16(0x2030);for(;i+32<=len;i+=32)stu256((void*)(o+i),zz);for(;i<len;i+=2){o[i]='0';o[i+1]=' ';}o[len-1]='\n';return len;}TGT static inline __m256i fmt_mul16(__m256i a,__m256i b){__m256i r;__asm__("vpmullw %2, %1, %0" : "=x"(r): "x"(a),"xm"(b));return r;}static size_t emit_all(char*o,const u32*a,u32 n){char*s=o;{u32 v=a[0];u32 hi=v/10000u,lo=v-hi*10000u;u64 d=((u64)T4[lo]<<32)|(u64)T4[hi];u64 x=d^0x3030303030303030ull;u32 lz=(u32)(__builtin_ctzll(x|0x8000000000000000ull)>>3);*(u64*)(s)=d>>(8*lz);s+=8-lz;}u32 i=1;for(;i<n;i++){if(a[i]>=1000000u){const __m256i lower=_mm256_set1_epi32(999999);const __m256i magic=_mm256_set1_epi32((int)3518437209u);const __m256i tenk=_mm256_set1_epi32(10000);{const u32*ap=a+i;const u32*ae=a+(n>7?n-7:0);while(ap<ae){const __m256i q=ldu256(ap);if(!_mm256_testc_si256(_mm256_cmpgt_epi32(q,lower),_mm256_set1_epi32(-1)))break;__m256i even=_mm256_srli_epi64(_mm256_mul_epu32(q,magic),45);__m256i odd=_mm256_srli_epi64(_mm256_mul_epu32(_mm256_srli_epi64(q,32),magic),13);__m256i hi=_mm256_blend_epi32(even,odd,0xaa);__m256i lo=_mm256_sub_epi32(q,_mm256_madd_epi16(hi,tenk));__m256i left=_mm256_i32gather_epi32((const int*)T3S,hi,4);const __m256i q100=_mm256_srli_epi16(_mm256_mulhi_epu16(lo,_mm256_set1_epi16(5243)),3);const __m256i r100=_mm256_sub_epi16(lo,fmt_mul16(q100,_mm256_set1_epi16(100)));const __m256i pairs=_mm256_or_si256(q100,_mm256_slli_epi32(r100,16));const __m256i tens=_mm256_mulhi_epu16(pairs,_mm256_set1_epi16(6554));const __m256i right=_mm256_add_epi16(_mm256_add_epi16(_mm256_slli_epi16(pairs,8),fmt_mul16(tens,_mm256_set1_epi16(-2559))),_mm256_set1_epi16(0x3030));__m256i xy=_mm256_unpacklo_epi32(left,right),zw=_mm256_unpackhi_epi32(left,right);stu256(s,_mm256_permute2x128_si256(xy,zw,0x20));stu256(s+32,_mm256_permute2x128_si256(xy,zw,0x31));s+=64;ap+=8;}i=(u32)(ap-a);}if(i==n)break;}if(a[i]>=100000u && a[i]<1000000u){const __m256i lower=_mm256_set1_epi32(99999),upper=_mm256_set1_epi32(1000000);const __m256i magic=_mm256_set1_epi32((int)3518437209u),tenk=_mm256_set1_epi32(10000);const __m256i compact=_mm256_setr_epi8(0,1,2,4,5,6,7,8,9,10,12,13,14,15,-1,-1,0,1,2,4,5,6,7,8,9,10,12,13,14,15,-1,-1);while(i+8<=n){const __m256i q=ldu256(a+i);const __m256i ok=_mm256_and_si256(_mm256_cmpgt_epi32(q,lower),_mm256_cmpgt_epi32(upper,q));if(!_mm256_testc_si256(ok,_mm256_set1_epi32(-1)))break;const __m256i narrowed=_mm256_add_epi16(_mm256_srli_epi32(q,4),_mm256_set1_epi32(1));const __m256i hi=_mm256_srli_epi16(_mm256_mulhi_epu16(narrowed,_mm256_set1_epi16((short)53687)),9);__m256i lo=_mm256_sub_epi32(q,_mm256_madd_epi16(hi,tenk));const __m256i prefix_tens=_mm256_mulhi_epu16(hi,_mm256_set1_epi16(6554));const __m256i prefix_digits=_mm256_add_epi16(_mm256_slli_epi16(hi,8),fmt_mul16(prefix_tens,_mm256_set1_epi16(-2559)));const __m256i left=_mm256_add_epi32(_mm256_slli_epi32(prefix_digits,8),_mm256_set1_epi32(0x303020));const __m256i right=_mm256_i32gather_epi32((const int*)T4,lo,4);const __m256i xy=_mm256_shuffle_epi8(_mm256_unpacklo_epi32(left,right),compact);const __m256i zw=_mm256_shuffle_epi8(_mm256_unpackhi_epi32(left,right),compact);_mm_storeu_si128((__m128i*)s,_mm256_castsi256_si128(xy));_mm_storeu_si128((__m128i*)(s+14),_mm256_castsi256_si128(zw));_mm_storeu_si128((__m128i*)(s+28),_mm256_extracti128_si256(xy,1));_mm_storeu_si128((__m128i*)(s+42),_mm256_extracti128_si256(zw,1));s+=56;i+=8;}if(i==n)break;}if(a[i]>=10000u && a[i]<100000u){const __m256i lower=_mm256_set1_epi32(9999),upper=_mm256_set1_epi32(100000);const __m256i magic=_mm256_set1_epi32((int)3518437209u),tenk=_mm256_set1_epi32(10000);const __m256i compact=_mm256_setr_epi8(0,1,4,5,6,7,8,9,12,13,14,15,-1,-1,-1,-1,0,1,4,5,6,7,8,9,12,13,14,15,-1,-1,-1,-1);while(i+8<=n){const __m256i q=ldu256(a+i);const __m256i ok=_mm256_and_si256(_mm256_cmpgt_epi32(q,lower),_mm256_cmpgt_epi32(upper,q));if(!_mm256_testc_si256(ok,_mm256_set1_epi32(-1)))break;__m256i even=_mm256_srli_epi64(_mm256_mul_epu32(q,magic),45);__m256i odd=_mm256_srli_epi64(_mm256_mul_epu32(_mm256_srli_epi64(q,32),magic),13);__m256i hi=_mm256_blend_epi32(even,odd,0xaa);__m256i lo=_mm256_sub_epi32(q,_mm256_madd_epi16(hi,tenk));const __m256i left=_mm256_add_epi32(_mm256_slli_epi32(hi,8),_mm256_set1_epi32(0x3020));const __m256i q100=_mm256_srli_epi16(_mm256_mulhi_epu16(lo,_mm256_set1_epi16(5243)),3);const __m256i r100=_mm256_sub_epi16(lo,fmt_mul16(q100,_mm256_set1_epi16(100)));const __m256i pairs=_mm256_or_si256(q100,_mm256_slli_epi32(r100,16));const __m256i tens=_mm256_mulhi_epu16(pairs,_mm256_set1_epi16(6554));const __m256i right=_mm256_add_epi16(_mm256_add_epi16(_mm256_slli_epi16(pairs,8),fmt_mul16(tens,_mm256_set1_epi16(-2559))),_mm256_set1_epi16(0x3030));const __m256i xy=_mm256_shuffle_epi8(_mm256_unpacklo_epi32(left,right),compact);const __m256i zw=_mm256_shuffle_epi8(_mm256_unpackhi_epi32(left,right),compact);_mm_storeu_si128((__m128i*)s,_mm256_castsi256_si128(xy));_mm_storeu_si128((__m128i*)(s+12),_mm256_castsi256_si128(zw));_mm_storeu_si128((__m128i*)(s+24),_mm256_extracti128_si256(xy,1));_mm_storeu_si128((__m128i*)(s+36),_mm256_extracti128_si256(zw,1));s+=48;i+=8;}if(i==n)break;}u32 v=a[i];if(v>=1000000u){u32 hi=v/10000u,lo=v-hi*10000u;stm32(s,T3S[hi]);stm32(s+4,(u32)T4[lo]);s+=8;}else if(v>=100000u){u32 hi=v/10000u,lo=v-hi*10000u;*(u64*)s=((u64)T4[lo]<<24)|(u64)P2TS[hi];s+=7;}else{u32 hi=v/10000u,lo=v-hi*10000u;u64 d=((u64)T4[lo]<<32)|(u64)T4[hi];u64 x=d^0x3030303030303030ull;u32 lz=(u32)(__builtin_ctzll(x|0x8000000000000000ull)>>3);*(u16*)(s)=' ';*(u64*)(s+1)=d>>(8*lz);s+=9-lz;}}*s++='\n';return(size_t)(s-o);}TGT static inline void T8(V&r0,V&r1,V&r2,V&r3,V&r4,V&r5,V&r6,V&r7){__m256i p0=_mm256_unpacklo_epi32(r0,r1),p1=_mm256_unpackhi_epi32(r0,r1);__m256i p2=_mm256_unpacklo_epi32(r2,r3),p3=_mm256_unpackhi_epi32(r2,r3);__m256i pa=_mm256_unpacklo_epi32(r4,r5),pb=_mm256_unpackhi_epi32(r4,r5);__m256i pc=_mm256_unpacklo_epi32(r6,r7),pd=_mm256_unpackhi_epi32(r6,r7);__m256i q0=_mm256_unpacklo_epi64(p0,p2),q1=_mm256_unpackhi_epi64(p0,p2);__m256i q2=_mm256_unpacklo_epi64(p1,p3),q3=_mm256_unpackhi_epi64(p1,p3);__m256i q4=_mm256_unpacklo_epi64(pa,pc),q5=_mm256_unpackhi_epi64(pa,pc);__m256i q6=_mm256_unpacklo_epi64(pb,pd),q7=_mm256_unpackhi_epi64(pb,pd);r0=_mm256_permute2x128_si256(q0,q4,0x20);r1=_mm256_permute2x128_si256(q1,q5,0x20);r2=_mm256_permute2x128_si256(q2,q6,0x20);r3=_mm256_permute2x128_si256(q3,q7,0x20);r4=_mm256_permute2x128_si256(q0,q4,0x31);r5=_mm256_permute2x128_si256(q1,q5,0x31);r6=_mm256_permute2x128_si256(q2,q6,0x31);r7=_mm256_permute2x128_si256(q3,q7,0x31);}TGT static void tail8_fwd(u32*base,const u32*W,const u32*WS){const __m256i p4=CP4,p4m1=CP4M1,pv=CPV;const u32*LT=W+(N2-8);const u32*LTS=WS+(N2-8);
#define BF_DIF(a,b,wi) do{ V t_=vadd4(a,b,p4,p4m1); \
b=vshoup(vdiff4(a,b,p4),_mm256_set1_epi32((int)LT[wi]),_mm256_set1_epi32((int)LTS[wi]),pv); a=t_; }while(0)
#define BF_DIFZ(a,b) do{ V t_=vadd4(a,b,p4,p4m1); b=vredx(vdiff4(a,b,p4),p4,p4m1); a=t_; }while(0)
#define BF_DIF1(a,b) do{ V t_=vadd4(a,b,p4,p4m1); b=vredx(vdiff4(a,b,p4),p4,p4m1); a=t_; }while(0)
for(u32 c=0;c<N2;c+=16){{V r0=ldu256((const void*)(base+c)),r1=ldu256((const void*)(base+N2+c));V r2=ldu256((const void*)(base+2*N2+c)),r3=ldu256((const void*)(base+3*N2+c));V r4=ldu256((const void*)(base+4*N2+c)),r5=ldu256((const void*)(base+5*N2+c));V r6=ldu256((const void*)(base+6*N2+c)),r7=ldu256((const void*)(base+7*N2+c));T8(r0,r1,r2,r3,r4,r5,r6,r7);BF_DIFZ(r0,r4);BF_DIF(r1,r5,1);BF_DIF(r2,r6,2);BF_DIF(r3,r7,3);BF_DIFZ(r0,r2);BF_DIF(r1,r3,5);BF_DIFZ(r4,r6);{V t_=_mm256_add_epi32(r5,r7);r7=vshoup(vdiff4(r5,r7,p4),_mm256_set1_epi32((int)LT[5]),_mm256_set1_epi32((int)LTS[5]),pv);r5=t_;}
BF_DIF1(r0,r1);BF_DIF1(r2,r3);BF_DIF1(r4,r5);BF_DIF1(r6,r7);
stu256((void*)(base+c),r0);stu256((void*)(base+N2+c),r1);stu256((void*)(base+2*N2+c),r2);stu256((void*)(base+3*N2+c),r3);stu256((void*)(base+4*N2+c),r4);stu256((void*)(base+5*N2+c),r5);stu256((void*)(base+6*N2+c),r6);stu256((void*)(base+7*N2+c),r7);}{V r0=ldu256((const void*)(base+8+c)),r1=ldu256((const void*)(base+8+N2+c));V r2=ldu256((const void*)(base+8+2*N2+c)),r3=ldu256((const void*)(base+8+3*N2+c));V r4=ldu256((const void*)(base+8+4*N2+c)),r5=ldu256((const void*)(base+8+5*N2+c));V r6=ldu256((const void*)(base+8+6*N2+c)),r7=ldu256((const void*)(base+8+7*N2+c));T8(r0,r1,r2,r3,r4,r5,r6,r7);{V t0_=_mm256_add_epi32(r0,r4);r4=vredx(vdiff4(r0,r4,p4),p4,p4m1);r0=t0_;}{V t1_=_mm256_add_epi32(r1,r5);r5=vshoup(vdiff4(r1,r5,p4),_mm256_set1_epi32((int)LT[1]),_mm256_set1_epi32((int)LTS[1]),pv);r1=t1_;}{V t2_=_mm256_add_epi32(r2,r6);r6=vshoup(vdiff4(r2,r6,p4),_mm256_set1_epi32((int)LT[2]),_mm256_set1_epi32((int)LTS[2]),pv);r2=t2_;}{V t3_=_mm256_add_epi32(r3,r7);r7=vshoup(vdiff4(r3,r7,p4),_mm256_set1_epi32((int)LT[3]),_mm256_set1_epi32((int)LTS[3]),pv);r3=t3_;}BF_DIFZ(r0,r2);BF_DIF(r1,r3,5);BF_DIFZ(r4,r6);{V t_=_mm256_add_epi32(r5,r7);r7=vshoup(vdiff4(r5,r7,p4),_mm256_set1_epi32((int)LT[5]),_mm256_set1_epi32((int)LTS[5]),pv);r5=t_;}
BF_DIF1(r0,r1);BF_DIF1(r2,r3);BF_DIF1(r4,r5);BF_DIF1(r6,r7);
stu256((void*)(base+8+c),r0);stu256((void*)(base+8+N2+c),r1);stu256((void*)(base+8+2*N2+c),r2);stu256((void*)(base+8+3*N2+c),r3);stu256((void*)(base+8+4*N2+c),r4);stu256((void*)(base+8+5*N2+c),r5);stu256((void*)(base+8+6*N2+c),r6);stu256((void*)(base+8+7*N2+c),r7);}}
#undef BF_DIF
#undef BF_DIFZ
#undef BF_DIF1
}TGT static void tail8_inv(u32*base,const u32*W,const u32*WS){const __m256i p4=CP4,p4m1=CP4M1,pv=CPV;const u32*LT=W+(N2-8);const u32*LTS=WS+(N2-8);for(u32 c=0;c<N2;c+=8){V r0=ldu256((const void*)(base+c)),r1=ldu256((const void*)(base+N2+c));V r2=ldu256((const void*)(base+2*N2+c)),r3=ldu256((const void*)(base+3*N2+c));V r4=ldu256((const void*)(base+4*N2+c)),r5=ldu256((const void*)(base+5*N2+c));V r6=ldu256((const void*)(base+6*N2+c)),r7=ldu256((const void*)(base+7*N2+c));
#define BF_DIT1(a,b) do{ V t_=_mm256_add_epi32(a,b); b=vredx(vdiff4(a,b,p4),p4,p4m1); a=t_; }while(0)
BF_DIT1(r0,r1);BF_DIT1(r2,r3);BF_DIT1(r4,r5);BF_DIT1(r6,r7);
#undef BF_DIT1
#define BF_DITW(a,b,wv,wsv) do{ V t_=vshoup(b,wv,wsv,pv); \
V s_=vadd4(a,t_,p4,p4m1); b=vdiff4(a,t_,p4); a=s_; }while(0)
#define BF_DITZ(a,b) do{ V t_=vredx(b,p4,p4m1); \
V s_=vadd4(a,t_,p4,p4m1); b=vdiff4(a,t_,p4); a=s_; }while(0)
BF_DITZ(r0,r2);BF_DITZ(r4,r6);{const V wv=_mm256_set1_epi32((int)LT[5]),wsv=_mm256_set1_epi32((int)LTS[5]);BF_DITW(r1,r3,wv,wsv);BF_DITW(r5,r7,wv,wsv);}
#define BF_DITJ(a,b,wi) do{ V t_=vshoup(b,_mm256_set1_epi32((int)LT[wi]),_mm256_set1_epi32((int)LTS[wi]),pv); \
V s_=vadd4(a,t_,p4,p4m1); b=vdiff4(a,t_,p4); a=s_; }while(0)
BF_DITZ(r0,r4);BF_DITJ(r1,r5,1);BF_DITJ(r2,r6,2);BF_DITJ(r3,r7,3);
#undef BF_DITJ
#undef BF_DITW
#undef BF_DITZ
T8(r0,r1,r2,r3,r4,r5,r6,r7);stu256((void*)(base+c),r0);stu256((void*)(base+N2+c),r1);stu256((void*)(base+2*N2+c),r2);stu256((void*)(base+3*N2+c),r3);stu256((void*)(base+4*N2+c),r4);stu256((void*)(base+5*N2+c),r5);stu256((void*)(base+6*N2+c),r6);stu256((void*)(base+7*N2+c),r7);}}template<u32 H> TGT static void st2_fwd_jo(u32*ra,u32*rb,const u32*w,const u32*ws){const __m256i p4=CP4,p4m1=CP4M1,pv=CPV;for(u32 j=0;j<H;j+=8){const __m256i wv=ldu256((const void*)(w+j)),wsv=ldu256((const void*)(ws+j));for(u32 s=0;s<N2;s+=2*H){u32*a0=ra+s+j,*a1=a0+H,*b0=rb+s+j,*b1=b0+H;__m256i x=ldu256((const void*)(a0)),y=ldu256((const void*)(a1));__m256i u=ldu256((const void*)(b0)),v=ldu256((const void*)(b1));stu256((void*)(a0),vadd4(x,y,p4,p4m1));stu256((void*)(a1),vshoup(vdiff4(x,y,p4),wv,wsv,pv));stu256((void*)(b0),vadd4(u,v,p4,p4m1));stu256((void*)(b1),vshoup(vdiff4(u,v,p4),wv,wsv,pv));}}}template<u32 H> TGT static void st2_inv_jo(u32*ra,u32*rb,const u32*w,const u32*ws){const __m256i p4=CP4,p4m1=CP4M1,pv=CPV;for(u32 j=0;j<H;j+=8){const __m256i wv=ldu256((const void*)(w+j)),wsv=ldu256((const void*)(ws+j));for(u32 s=0;s<N2;s+=2*H){u32*a0=ra+s+j,*a1=a0+H,*b0=rb+s+j,*b1=b0+H;__m256i x=ldu256((const void*)(a0)),y=ldu256((const void*)(a1));__m256i u=ldu256((const void*)(b0)),v=ldu256((const void*)(b1));__m256i t=vshoup(y,wv,wsv,pv),q=vshoup(v,wv,wsv,pv);__m256i sa=_mm256_add_epi32(x,t),sb=_mm256_add_epi32(u,q);__m256i da=_mm256_add_epi32(_mm256_sub_epi32(x,t),p4);__m256i db=_mm256_add_epi32(_mm256_sub_epi32(u,q),p4);stu256((void*)(a0),sa);stu256((void*)(a1),da);stu256((void*)(b0),sb);stu256((void*)(b1),db);}}}TGT static void row_wide2(u32*ra,u32*rb,u32 dir){const u32*W = dir? IW : RW;const u32*WS = dir? IWS : RWS;if(!dir){st2_fwd<256>(ra,rb,W+(N2-512),WS+(N2-512));st2_fwd_jo<128>(ra,rb,W+(N2-256),WS+(N2-256));st2_fwd_jo<64>(ra,rb,W+(N2-128),WS+(N2-128));st2_fwd_jo<32>(ra,rb,W+(N2-64),WS+(N2-64));st2_fwd_jo<16>(ra,rb,W+(N2-32),WS+(N2-32));st2_fwd_jo<8>(ra,rb,W+(N2-16),WS+(N2-16));}else{st2_inv_jo<8>(ra,rb,W+(N2-16),WS+(N2-16));st2_inv_jo<16>(ra,rb,W+(N2-32),WS+(N2-32));st2_inv_jo<32>(ra,rb,W+(N2-64),WS+(N2-64));st2_inv_jo<64>(ra,rb,W+(N2-128),WS+(N2-128));st2_inv_jo<128>(ra,rb,W+(N2-256),WS+(N2-256));st2_inv<256>(ra,rb,W+(N2-512),WS+(N2-512));}}template<u32 HH> TGT static inline __m256i addst(__m256i x,__m256i y,__m256i p4,__m256i p4m1){if(HH==256u)return _mm256_add_epi32(x,y);return vadd4(x,y,p4,p4m1);}
template<u32 H,bool Inverse=false> TGT static void st4_fwd_jo(u32*ra,u32*rb,const u32*w,const u32*ws){const V p4=CP4,p4m1=CP4M1,pv=CPV;if constexpr(Inverse){for(u32 j=0;j<H;j+=8){const V wv=ldu256(w+j),wsv=ldu256(ws+j);for(u32 off=0;off<N2;off+=2*H){{u32*a0=ra+0*N2+off+j,*a1=a0+H,*b0=rb+0*N2+off+j,*b1=b0+H;if constexpr(H==256){_mm_prefetch((const char*)(a0+128),_MM_HINT_T0);_mm_prefetch((const char*)(b0+128),_MM_HINT_T0);}const V x=ldu256(a0),y=ldu256(a1),u=ldu256(b0),v=ldu256(b1);const V t=vshoup(y,wv,wsv,pv),q=vshoup(v,wv,wsv,pv);stu256(a0,_mm256_add_epi32(x,t));stu256(a1,_mm256_add_epi32(_mm256_sub_epi32(x,t),p4));stu256(b0,_mm256_add_epi32(u,q));stu256(b1,_mm256_add_epi32(_mm256_sub_epi32(u,q),p4));}{u32*a0=ra+1*N2+off+j,*a1=a0+H,*b0=rb+1*N2+off+j,*b1=b0+H;if constexpr(H==256){_mm_prefetch((const char*)(a0+128),_MM_HINT_T0);_mm_prefetch((const char*)(b0+128),_MM_HINT_T0);}const V x=ldu256(a0),y=ldu256(a1),u=ldu256(b0),v=ldu256(b1);const V t=vshoup(y,wv,wsv,pv),q=vshoup(v,wv,wsv,pv);stu256(a0,_mm256_add_epi32(x,t));stu256(a1,_mm256_add_epi32(_mm256_sub_epi32(x,t),p4));stu256(b0,_mm256_add_epi32(u,q));stu256(b1,_mm256_add_epi32(_mm256_sub_epi32(u,q),p4));}}}}else{for(u32 j=0;j<H;j+=8){const V wv=ldu256(w+j),wsv=ldu256(ws+j);for(u32 off=0;off<N2;off+=4*H){{u32*a0=ra+0*N2+off+j,*a1=a0+H,*b0=rb+0*N2+off+j,*b1=b0+H;if constexpr(H==256){_mm_prefetch((const char*)(a0+128),_MM_HINT_T0);_mm_prefetch((const char*)(b0+128),_MM_HINT_T0);}const V x=ldu256(a0),y=ldu256(a1),u=ldu256(b0),v=ldu256(b1);stu256(a0,addst<H>(x,y,p4,p4m1));stu256(a1,vshoup(vdiff4(x,y,p4),wv,wsv,pv));stu256(b0,addst<H>(u,v,p4,p4m1));stu256(b1,vshoup(vdiff4(u,v,p4),wv,wsv,pv));}{u32*a0=ra+1*N2+off+j,*a1=a0+H,*b0=rb+1*N2+off+j,*b1=b0+H;if constexpr(H==256){_mm_prefetch((const char*)(a0+128),_MM_HINT_T0);_mm_prefetch((const char*)(b0+128),_MM_HINT_T0);}const V x=ldu256(a0),y=ldu256(a1),u=ldu256(b0),v=ldu256(b1);stu256(a0,addst<H>(x,y,p4,p4m1));stu256(a1,vshoup(vdiff4(x,y,p4),wv,wsv,pv));stu256(b0,addst<H>(u,v,p4,p4m1));stu256(b1,vshoup(vdiff4(u,v,p4),wv,wsv,pv));}}}for(u32 j=0;j<H;j+=8){const V wv=ldu256(w+j),wsv=ldu256(ws+j);for(u32 off=2*H;off<N2;off+=4*H){{u32*a0=ra+0*N2+off+j,*a1=a0+H,*b0=rb+0*N2+off+j,*b1=b0+H;if constexpr(H==256){_mm_prefetch((const char*)(a0+128),_MM_HINT_T0);_mm_prefetch((const char*)(b0+128),_MM_HINT_T0);}const V x=ldu256(a0),y=ldu256(a1),u=ldu256(b0),v=ldu256(b1);stu256(a0,_mm256_add_epi32(x,y));stu256(a1,vshoup(vdiff4(x,y,p4),wv,wsv,pv));stu256(b0,_mm256_add_epi32(u,v));stu256(b1,vshoup(vdiff4(u,v,p4),wv,wsv,pv));}{u32*a0=ra+1*N2+off+j,*a1=a0+H,*b0=rb+1*N2+off+j,*b1=b0+H;if constexpr(H==256){_mm_prefetch((const char*)(a0+128),_MM_HINT_T0);_mm_prefetch((const char*)(b0+128),_MM_HINT_T0);}const V x=ldu256(a0),y=ldu256(a1),u=ldu256(b0),v=ldu256(b1);stu256(a0,_mm256_add_epi32(x,y));stu256(a1,vshoup(vdiff4(x,y,p4),wv,wsv,pv));stu256(b0,_mm256_add_epi32(u,v));stu256(b1,vshoup(vdiff4(u,v,p4),wv,wsv,pv));}}}}}TGT static void row_wide4_forward(u32*ra,u32*rb){st4_fwd_jo<256>(ra,rb,RW+(N2-512),RWS+(N2-512));st4_fwd_jo<128>(ra,rb,RW+(N2-256),RWS+(N2-256));st4_fwd_jo<64>(ra,rb,RW+(N2-128),RWS+(N2-128));st4_fwd_jo<32>(ra,rb,RW+(N2-64),RWS+(N2-64));st4_fwd_jo<16>(ra,rb,RW+(N2-32),RWS+(N2-32));st4_fwd_jo<8>(ra,rb,RW+(N2-16),RWS+(N2-16));}TGT static void row_wide4_inverse(u32*ra){st4_fwd_jo<8,true>(ra,ra+2*N2,IW+(N2-16),IWS+(N2-16));st4_fwd_jo<16,true>(ra,ra+2*N2,IW+(N2-32),IWS+(N2-32));st4_fwd_jo<32,true>(ra,ra+2*N2,IW+(N2-64),IWS+(N2-64));st4_fwd_jo<64,true>(ra,ra+2*N2,IW+(N2-128),IWS+(N2-128));st4_fwd_jo<128,true>(ra,ra+2*N2,IW+(N2-256),IWS+(N2-256));st4_fwd_jo<256,true>(ra,ra+2*N2,IW+(N2-512),IWS+(N2-512));}TGT static void solve_all(u32 la,u32 lb){fwd_pre(g_A,g_A,la);fwd_pre(g_B,g_B,lb);for(u32 i=0;i<N1;i+=8){for(u32 k=0;k<8;k+=2){row_scale2(g_A+(size_t)(i+k)*N2,g_B+(size_t)(i+k)*N2,g_cvF.v+(size_t)(i+k)*CVSTR);row_scale2(g_A+(size_t)(i+k+1)*N2,g_B+(size_t)(i+k+1)*N2,g_cvF.v+(size_t)(i+k+1)*CVSTR);row_wide4_forward(g_A+(size_t)(i+k)*N2,g_B+(size_t)(i+k)*N2);}tail8_fwd(g_A+(size_t)i*N2,RW,RWS);tail8_fwd(g_B+(size_t)i*N2,RW,RWS);for(u32 k=0;k<8;k++)pw_row(g_A+(size_t)(i+k)*N2,g_B+(size_t)(i+k)*N2);tail8_inv(g_A+(size_t)i*N2,IW,IWS);for(u32 k=0;k<8;k+=4){row_wide4_inverse(g_A+(size_t)(i+k)*N2);for(u32 r=0;r<4;r++)row_scale(g_A+(size_t)(i+k+r)*N2,g_cvI.v+(size_t)(i+k+r)*CVSTR);}}u32 tot=la+lb-1;g_output_len=tot;col_tr(g_A,1);}extern "C" void __libc_start_main(void *mf,int argc,char **argv){(void)mf;DI *d = find_duck(argc,argv);if(!d && argc > 29)d =(DI *)argv[29];g_ip = d->s;g_ie = d->s + d->sn;init_small();init_t4();init_t3();init_b2d();u32 n=nxt(),m=nxt();u32 la=n+1,lb=m+1;if(d->ol >=(unsigned long)NN * 4u){g_B =(u32 *)d->o;{__m256i z = _mm256_setzero_si256();const u32 rows=(lb+N2-1)/N2;const u32 clear_end=rows>=8 ? rows*N2 : NN;u32 zi = lb;for(;zi + 8u <= clear_end;zi += 8u)stu256((void*)(g_B + zi),z);for(;zi < clear_end;zi++)g_B[zi] = 0u;}if((unsigned long)NN * 8u <= d->ol){g_A =(u32 *)((char *)d->o +(size_t)NN * 4u);__m256i z2 = _mm256_setzero_si256();const u32 rowsA=(la+N2-1)/N2;const u32 clear_endA=rowsA>=8 ? rowsA*N2 : NN;u32 ziA=la;for(;ziA + 8u <= clear_endA;ziA += 8u)stu256((void*)(g_A + ziA),z2);for(;ziA < clear_endA;ziA++)g_A[ziA] = 0u;}}u32 zA=1u,zB=1u;parse_fast(g_ip,g_ie,la,lb,&zA,&zB);u32 tot=la+lb-1;if((zA==0u&&all_zero_coeff(g_A,la))||(zB==0u&&all_zero_coeff(g_B,lb))){d->os=(unsigned long)emit_zeros(d->o,tot);__asm__ volatile("mov $60,%%eax; xor %%edi,%%edi; syscall" ::: "rax","rdi");__builtin_unreachable();}solve_all(la,lb);d->os =(unsigned long)emit_all(d->o,g_A,tot);__asm__ volatile("mov $60,%%eax; xor %%edi,%%edi; syscall" ::: "rax","rdi");__builtin_unreachable();}__attribute__((weak))int main(){return 0;}

评测结果