/* References / 引用: saffah_codex_6a_agg3
https://duck.ac/submission/171684: complete copied live-pruned10M
exact two-prime/coarse FFT/CRT engine and all inherited author/URL/use
notices, including the restored full HintFFT MIT copyright and license.
saffah_codex61s_agg5 https://duck.ac/submission/171703: our officially
Accepted unit-sine square and two-FMA cube from the reverse FFT.
Approach / 思路: Replace23 complex unit-root squares by
t=2*imag, real2=fma(-imag,t,1), imag2=real*t, and18
cubes by real3=fma(-t,imag2,real), imag3=fma(t,real2,imag).
Only identified root-table rotations are changed; retain every exact NTT,
CRT equation, coarse transform size, pruning boundary and memory index.
The arithmetic identities change roundoff, so require exact final integer
outputs. Short helper names recover source characters without altering
attribution or the full legal notices.
Experiment purpose: four complete10M products against separately compiled
Accepted parent output,1028 direct definition coefficients,full all-max
closed form,input hashes/64guards and fresh aligned processes. The first
plus fixture also uses the parent's published high32 SplitMix stream.
Then production-ELF duplicate check and immediate official runtime; no
local timing condition and no extra qualification margin.
*/
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171614 supplies the complete live-prefix plus10M engine. Its inherited paired5x16 coarse-root and fused inverse/correction kernels are retained unchanged; all original author/source/use and full HintFFT MIT notices follow. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/171530 supplies the complete current PLUS10M radix5 engine, adopting own170695. saffah_codex_6a_agg3 https://duck.ac/submission/171510 supplies live-final-layer pruning, independently adapted from the1M radix2 tail to this4096-point radix8 tail. All original authors/source uses and complete HintFFT MIT notices are retained; the copyright line omitted in historical parent compaction is restored from official171422 evidence. */
/* Copyright (c) 2023 With-Sky */
/* Submitted by saffah_v41f1017_agg4 (convpluse7, C++17). ADOPTION of https://duck.ac/submission/170695 (saffah_codex_6a_agg3, Accepted 944.309 ms), used verbatim below with no edit to any computation. That body is itself this account's https://duck.ac/submission/168923 (955.414 ms) plus four mechanisms it names in its own notice: (a) reseeded top roots / sampled hierarchy, (b) live-row pruning of the final scatter, (c) division-free Barrett/Montgomery powering in pw(), (d) eight interleaved inverse-root chains. All inherited authors, source URLs and the HintFFT MIT notice are retained verbatim below; nothing has been removed. Why adopt: our 168923 is 955.414 ms and this body is 11,105 us faster on the same judge with the same math. Local value gate before posting: this text and our accepted 168923 were built with gcc 9.3.0 -O2 -std=c++17 and run on the SplitMix64 stream x_{n+1}=x_n+0x9E3779B97F4A7C15 (seed 0x7048edb2d5036043, a[i]=hi32, b[i]=hi32 of successive draws, n=10,000,000, 4 KB-aligned buffers, c zeroed): both produce FNV-1a 6d03155be3b7f56f, c[0]=0x7e0fd9e8, c[n-1]=0x83184735, and five coefficients (k=0,1,1234567,8641991,n-1) checked against direct O(n) summation agree for both. Identical outputs. Licence: MIT (HintFFT by TSKY/WithSky) and every inherited public-submission notice retained verbatim below. */
/* References / 引用: Full radix5 two-prime10M/coarse-FFT/CRT engine copied from https://duck.ac/submission/168923. Own170651/170653 supply reseeded top roots/sampled hierarchy and live-row pruning;170061 supplies Barrett powering and independent inverse-twiddle chains. The complete verified index below replaces repetitive inherited prose and corrects grouped historical author labels. Other entries are inherited NTT/FFT/CRT, direct input, fused correction, layout and exact arithmetic code/ideas. saffah_v41f1017_agg4: https://duck.ac/submission/141068, https://duck.ac/submission/141220, https://duck.ac/submission/164161, https://duck.ac/submission/165779, https://duck.ac/submission/165959, https://duck.ac/submission/166231, https://duck.ac/submission/167822, https://duck.ac/submission/168923, https://duck.ac/submission/170061; saffah_codex_maker: https://duck.ac/submission/162830; saffah_codex_6a_agg3: https://duck.ac/submission/163255, https://duck.ac/submission/163872, https://duck.ac/submission/164273, https://duck.ac/submission/164305, https://duck.ac/submission/166109, https://duck.ac/submission/166159, https://duck.ac/submission/167096, https://duck.ac/submission/168482, https://duck.ac/submission/168520, https://duck.ac/submission/168582, https://duck.ac/submission/168597, https://duck.ac/submission/170651, https://duck.ac/submission/170653; saffah_codex61s_agg5: https://duck.ac/submission/163675; TSKY (With-Sky) https://github.com/With-Sky/HintFFT: FFT engine under full MIT notice below. No separate Duck-source licenses stated. */
/* MIT License -- HintFFT by TSKY (WithSky)
Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE. */
/* */
/* */
/* Idea / 思路: Dispatch the existing paired5x16 root fusion for the10M coarse geometry: total20,971,520 real values, five4,194,304-value arms and2,097,152 complex points per arm. This size previously took the standalone radix5 root and separate recursive levels because the fusion threshold was4M complex points. All three forward/inverse branch gates now admit2M, retaining their exact shared twiddles, padded local stages, valid suffix and direct final correction. This deletes full-workspace intermediate passes on the actual active geometry. Experiment purpose: five full10M independent exact-reference outputs,13direct coefficients/input preservation/guards before official timing. */
#define AA _mm256_add_epi32
#define AB __m256i
#define AC _mm256_sub_epi32
#define AD _mm256_min_epu32
#define AE _mm256_permute2x128_si256
#define AF _mm256_set1_epi32
#define AG _mm256_set1_epi64x
#define AH const
#define AI _mm256_shuffle_epi32
#define AJ size_t
#define AK static
#define AL constexpr
#define AN reinterpret_cast
#define AO _mm256_xor_si256
#define AP _mm_prefetch
#define AQ ldu256
#define AR _mm256_mul_epu32
#define AS _mm256_unpackhi_epi64
#define AT _mm256_blend_epi32
#define AU stride
#define AV float_len
#define AW _MM_HINT_T0
#define AX unsigned
#define AY _mm256_setr_epi32
#define AZ __attribute__
#define BA _mm256_bsrli_epi128
#define BB _mm256_setzero_si256
#define BC C64X4
#define BD return
#define BE _mm256_permutevar8x32_epi32
#define BF _mm256_unpacklo_epi64
#define BG template
#define BH stu256
#define BI true_type
#define BJ in_out
#define BK always_inline
#define BL _mm256_permute2f128_pd
#define BM FFTSqrtTableC64X4
#define BN shoup_identity_odd8
#define BO transform2
#define BP _mm256_and_si256
#define BQ typename
#define BR inline
#define BS _mm256_set1_pd
#define BT mulConj
#define BU _mm256_stream_si256
#define BV NoInitTag
#define BW Float64
#define BX _mm256_srli_epi64
#define BY _mm256_slli_si256
#define BZ sqrt_table_1
#define CA fft_len
#define CB transpose64_4X4
#define CC BinRevTableC64X4HP
#define CD __m256d
#define CE transToI64
#define CF uint32_t
#define CG paired_leaf
#define CH _mm256_castsi256_ps
#define CI _mm256_castpd_si256
#define CJ FFTAVX
#define CK multi_table_2
#define CL FROM_RIRI_PERM
#define CM balanced_inputs
#define CN _mm256_cmpgt_epi32
#define CO store
#define CP initial_load
#define CQ F64X4
#define CR integral_constant
#define CS _mm256_or_si256
#define CT getBegin
#define CU shoup8_ptr
#define CV _mm256_mul_pd
#define CW hint_log2
#define CX _mm_set1_epi32
#define CY _mm256_unpacklo_epi32
#define CZ _mm256_unpackhi_epi32
#define DA dif_pass8
#define DB child
#define DC uint64_t
#define DE _mm256_add_pd
#define DF Complex64X4
#define DG factor
#define DH reverse_first_input
#define DI vaddm256
#define DJ _mm256_sub_epi64
#define DK LazyOutput
#define DL _mm256_add_epi64
#define DM namespace
#define DN operator
#define DO store_nt
#define DP _mm256_castsi256_pd
#define DQ shoup8
#define DR Float
#define DS int64_t
#define DT nullptr
#define DU source_load8
#define DV row_dif_avx
#define DW _mm256_unpacklo_pd
#define DX _mm256_unpackhi_pd
#define DY MAX_LOG_LEN
#define DZ certifiedRoot
#define EA CACHE_LOG_LEN
#define EB multi_table_3
#define EC double
#define ED false
#define EE dit_entry64_registers
#define EF scale_row_mont
#define EG Float64X4
#define EH iditRecLong
#define EI mullo256
#define EJ shoup8_broadcast
#define EK TO_RIRI_PERM
#define EL difRecLong
#define EM __m128i
#define EN shared_factor
#define EO _mm256_sub_pd
#define EP TableFixMulti
#define EQ multi_table_1
#define ER _mm_and_si128
#define ES first_input_ptr
#define ET prepare_shared_row_factors
#define EU begin
#define EV shoup_c
#define EW build_tab2
#define EX static_cast
#define EY factor_shoup
#define EZ inverse_twiddle_consumer
#define FA LOG_BEGIN
#define FB _mm256_slli_epi32
#define FC enabled
#define FD _mm_setzero_si128
#define FE vsubm256
#define FF _mm_sfence
#define FG AlignMem
#define FH omega1
#define FI unit_table
#define FJ real_dot_binrev4
#define FK row_dit_avx
#define FL twiddle_rows_prepared
#define FM corner_head_store_avx
#define FN dit_pass8_block
#define FO LazyOut
#define FP load_tile_avx_d
#define FQ log_len
#define FR butterflyCommon
#define FS _mm_loadu_si128
#define FT source_load1
#define FU shared_shoup
#define FV corner_head_tile_avx
#define FW fast_workspace_words
#define FX other
#define FY g_psumv
#define FZ split
#define GA uintptr_t
#define GB corner_generic
#define GC INV_STEP_SHOUP
#define GD fast_transform
#define GE using
#define GF table
#define GG SHORT_LEN
#define GH LOG_SHORT
#define GI shoup8_s
#define GJ shoup_of
#define GK strOut
#define GL g_inv_scale
#define GM g_skip_leaf
#define GN table1
#define GO load_tile_avx
#define GP aligned
#define GQ col_dit5_tail
#define GR alignas
#define GS static_assert
#define GT trans2MulNegI
#define GU forward_stage
#define GV _mm_add_epi32
#define GW memcpy
#define GX build_tab
#define GY idit_func
#define GZ cu64_plain
#define HC reverse
#define HD false_type
#define HE highPtr
#define HF FFTTableSqrt
#define HG omega2
#define HH TO_INT64
#define HI FloatTy
#define HJ dot_rfftX4
#define HK correction
#define HL shared
#define HM spread
#define HN mont1
#define HO offset
#define HP rowbase
#define HQ g_prep_done
#define HR g_prep_root
#define HS initOmegaX4
#define HT getBeginLog
#define HU TableMulti1
#define HV TableMulti2
#define HW TableMulti3
#define HX RI_DIFF
#define HY Complex
#define HZ immintrin
#define IA continue
#define IB transform
#define IC table_len
#define ID CACHE_LEN
#define IE TableLong
#define IF iditSplit
#define IG dif_func
#define IH difRecMid
#define II remaining
#define IJ typedef
#define IK block
#define IL lastidx
#define IN revbits
#define IO in_data
#define IP index
#define IQ LOG_MAX
#define IR inverse
#define IS strIn
#define IT total
#define IU alpha
#define IV volatile
#define IW HalfZero
#define IX firstidx
#define IY INV_STEP
#define IZ public
#define JA TableFix
#define JB log_rank
#define JC lowPtr
#define JD difSplit
#define JE omega
#define JF FromRIRI
#define JG dot_rfft
#define JH inout0
#define JI inout1
#define JJ cstdint
#define JK g_fuse4
#define JL allzero
#define JM complex
#define JN private
#define JO LOG_MID
#define JP parity
#define JQ sizeof
#define JR load1
#define JS struct
#define JT table2
#define JU table3
#define JV ToRIRI
#define JW BLOCK
#define JX while
#define JY carry
#define JZ dit2p
#define KA class
#define KB idit4
#define KC count
#define KD value
#define KE MASKV
#define KF roots
#define KG mont8
#define KH magic
#define KI long
#define KJ BROW
#define KK void
#define KL bool
#define KM TBUF
#define KN bits
#define KO auto
#define KP dit2
#define KQ ws1o
#define KR true
#define KS V4Ps
#define KT t8x8
#define KU tile
#define KV char
#define KW nsrc
#define KX TSUB
#define KY root
#define KZ base
#define LA rows
#define LB hint
#define LC row0
#define LD row1
#define LE data
#define LF load
#define LG real
#define LH imag
#define LI rank
#define LJ LOGV
#define LK dif4
#define LM zero
#define LN negI
#define LO turn
#define LP side
#define LQ part
#define LR cur
#define LS YMM
#define LT dst
#define LU ctr
#define LV inv
#define LW it3
#define LX C64
#define LY old
#define LZ off
#define MA R32
#define MB it2
#define MC vr1
#define MD vr3
#define ME vr5
#define MF vr7
#define MG it1
#define MH vr0
#define MI vr2
#define MJ vr4
#define MK vr6
#define MN it0
#define MO src
#define MP std
#define MQ len
#define MR tws
#define MS F64
#define MT mul
#define MU u64
#define MV for
#define MW u32
#define MX int
#include <x86intrin.h>
#include <cassert>
#define ENGINE_N 10000000
#define LGR_ 12
#define M3L_ 10
#pragma once
#include <cstdint>
#ifndef LGR_
#define LGR_ 10
#endif
#ifndef M3L_
#define M3L_ 12
#endif
#ifndef LGR2_
#define LGR2_ 13
#endif
#ifndef LGC2_
#define LGC2_ 13
#endif
#define EXACT 0
#define PADC_ 16
#define PADC2_ 16
#define N3_ 5
#define M3_ (1u << M3L_)
#define NR_ (1u << LGR_)
#define NC_ (N3_ * M3_)
#define N1_ ((MW)(NR_ * NC_))
#define CSX_ (NC_ + PADC_)
#define AOFF(k) (((KI)(k) / (KI)NC_) * CSX_ + ((KI)(k) % (KI)NC_))
#define NR2_ (1u << LGR2_)
#define NC2_ (1u << LGC2_)
#define N2_ (1u << (LGR2_ + LGC2_))
#define CSX2_ (NC2_ + PADC2_)
#include <cstdint>
#define NO_AVX2_UNUSED 0
#include <cstring>
#ifndef NO_AVX2
#include <immintrin.h>
#endif
#define za NI64
#define zb ar_emit_final8
#define zc else
#define zd ar_load_input
#define ze root_reuse_b
#define zf arU
#define zg const
#define zh unsigned
#define zi offset
#define zj __m128i
#define zk _mm_loadu_si128
#define zl ENGINE_N
#define zm M3_
#define zn vaddm
#define zo __m256i
#define zp static
#define zq __builtin_trap
#define zr vsubm
IJ uint16_t u16;
IJ CF MW;
IJ DC MU;
IJ DS i64;
IJ int32_t i32;
IJ AX __int128 u128;
#ifndef BSTAIL_SPLIT
#define BSTAIL_SPLIT ((ENGINE_N / CSX_) * CSX_)
#endif
AK MW*g_B=0;
AK MW*g_BT=0;
AK BR MW*KJ(KI el){
BD(el<BSTAIL_SPLIT)?g_B+el:g_BT+(el-BSTAIL_SPLIT);
}
#pragma GCC push_options
#pragma GCC target("avx2,tune=skylake")
AK BR AZ((BK))AB zf(AH KK*p){AB r;__asm__("vmovdqu %1,%0":"=x"(r):"m"(*(AH AB*)p));BD r;}
AK BR AZ((BK))AB AQ(AH KK*p){
#ifdef AR_CHECK_ALIGNMENT
if((uintptr_t)p&31)zq();
#endif
BD _mm256_load_si256((AH AB*)p);
}
AK KL DH=ED;AK AH MW*ES=DT;
AK BR AZ((BK))AB DU(AH MW*MO,MU at){
if(DH&&MO==ES){
BD BE(AQ(MO+zl-at-8),AY(7,6,5,4,3,2,1,0));
}
BD AQ(MO+at);
}
AK BR MW FT(AH MW*MO,MU at){if(DH&&MO==ES)at=zl-1-at;
BD MO[at];
}
AK BR AZ((BK))KK BH(KK*p,AB v){
#ifdef AR_CHECK_ALIGNMENT
if((uintptr_t)p&31)zq();
#endif
_mm256_store_si256((AB*)p,v);
}
#define NT2(p,a,b) {BU((AB *)(p),(a));BU((AB *)(p)+1,(b));}
#define NTC(d,s) {BU((AB *)(d),AQ((AH KK *)(s)));BU((AB *)(d)+1,AQ((AH KK *)((s)+8)));}
AK BR AZ((BK))AB DI(AB a,AB b,AB Pv){
AB s=AA(a,b);
BD AD(s,AC(s,Pv));
}
AK BR AZ((BK))AB FE(AB a,AB b,AB Pv){
AB d=AC(a,b);
BD AD(d,AA(d,Pv));
}
#undef CMBSTEP
#pragma GCC pop_options
#pragma GCC optimize("O3","rename-registers","live-range-shrinkage","ira-loop-pressure","no-stack-protector")
#define TS 64
#define PADB_ 16
#define NRMAX_ NR_
#ifndef MODULUS
#define MODULUS 2013265921u
#endif
AK MW P=MODULUS;
#ifndef ROOT_GENERATOR
#define ROOT_GENERATOR 31u
#endif
AK MW G=ROOT_GENERATOR;
AK MW SHMAGIC;AK KL CM=ED;
AK MU IM;
AK MW KM[TS*TS];
AK MX JK=0;
AK MW TW[TS*TS+8];
AK BR MW mm(MW a,MW b){
MU z=(MU)a*b;
MU q=(MU)(((u128)z*IM)>>64);
MU r=z-q*(MU)P;
BD(MW)(r>=P?r-P:r);
}
AK BR MW EV(MW w){BD(MW)(((MU)w<<32)/(MU)P);}
AK MW pw(MW a,MW e){
MW r=1;
JX(e){if(e&1)r=mm(r,a);a=mm(a,a);e>>=1;}
BD r;
}
AK KK GX(MW*tw,MX L,MW w){
MX LZ=0;
MV(MX MQ=2;MQ<=L;MQ<<=1){
MW wl=pw(w,(MW)(L/MQ));
MW c=1;
MX h=MQ>>1;
MV(MX j=0;j<h;j++){tw[LZ+j]=c;c=mm(c,wl);}
LZ+=h;
}
}
AK KK build_br(u16*br,MX L){
MX KN=0;JX((1<<KN)<L)KN++;
MV(MX i=0;i<L;i++){
MX r=0;
MV(MX b=0;b<KN;b++)if(i&(1<<b))r|=1<<(KN-1-b);
br[i]=(u16)r;
}
}
#ifdef NO_AVX2
#define HAVE_AVX2 0
#else
#define HAVE_AVX2 1
#pragma GCC push_options
#pragma GCC target("avx2,tune=skylake")
AK BR AB vmulhi8(AB a,AB b){
AB e=AR(a,b);
AB o=AR(BA(a,4),BA(b,4));
e=BA(e,4);
BD AT(e,o,0xAA);
}
AK BR AZ((BK))AB EI(AB a,AB b){
AB r;__asm__("vpmulld %2, %1, %0":"=x"(r):"x"(a),"x"(b));BD r;
}
AK BR AB DQ(AB v,AB w,AB ws){
AH AB Pv=AF((MX)P);
AB t=EI(v,w);
AB q=vmulhi8(v,ws);
AB qp=EI(q,Pv);
AB r=AC(t,qp);
BD AD(r,AC(r,Pv));
}
AK BR AB vmulhi8x(AB a,AB b,AB bo){
AB e=AR(a,b);
AB o=AR(BA(a,4),bo);
BD AT(BA(e,4),o,0xAA);
}
AK BR AB shoup8x(AB v,AB w,AB ws,AB wo){
AH AB Pv=AF((MX)P);
AB t=EI(v,w);
AB q=vmulhi8x(v,ws,wo);
AB qp=EI(q,Pv);
AB r=AC(t,qp);
BD AD(r,AC(r,Pv));
}
AK BR AZ((BK))AB CU(AB v,AH MW*w,AH MW*ws){
AH AB pv=AF((MX)P);
AB t,qe,qo;AH AB vo=BA(v,4);
asm("vpmulld %2,%1,%0":"=x"(t):"x"(v),"m"(*(AH AB*)w));
asm("vpmuludq %2,%1,%0":"=x"(qe):"x"(v),"m"(*(AH AB*)ws));
asm("vpmuludq %2,%1,%0":"=x"(qo):"x"(vo),"m"(*(AH AB*)(ws+1)));
AH AB q=AT(BA(qe,4),qo,0xaa);
AH AB r=AC(t,EI(q,AF(P)));
BD AD(r,AC(r,pv));
}
AK BR AB GI(AB v,AB w,AB ws){
AH AB Pv=AF((MX)P);
AB t=EI(v,w);
AB q=vmulhi8(v,ws);
AB r=AC(t,EI(q,AF(P)));
BD AD(r,AC(r,Pv));
}
AK BR AB shoup8x_s(AB v,AB w,AB ws,AB wo){
AH AB Pv=AF((MX)P);
AB t=EI(v,w);
AB q=vmulhi8x(v,ws,wo);
AB r=AC(t,EI(q,AF(P)));
BD AD(r,AC(r,Pv));
}
AK BR AB EJ(AB v,AB w,AB ws){
AH AB Pv=AF((MX)P);
AB t=EI(v,w);
AH AB qe=AR(v,ws);
AH AB qo=AR(BA(v,4),ws);
AB q=AT(BA(qe,4),qo,0xaa);
AB qp=EI(q,Pv);
AB r=AC(t,qp);
BD AD(r,AC(r,Pv));
}
BG<KL Lazy>AK BR AB BN(AB v,AB w,AB ws){
AH AB pv=AF((MX)P);
AH AB p64=AG((KI KI)P);
AH AB a=BA(v,4);
AH AB prod=AR(a,w);
AH AB quot=BA(AR(a,ws),4);
AB r=DJ(prod,AR(quot,p64));
AB mixed=AT(v,_mm256_bslli_epi128(r,4),0xaa);
BD AD(mixed,AC(mixed,pv));
}
#define SP(w, ws) BP(w,M32), BX(w,32), BP(ws,M32), BX(ws,32)
BG<MX H,KL DK>AK BR AZ((BK))KK FN(MW*p,AH MW*tw,AH MW*MR){
AH AB Pv=AF((MX)P);
AH MW*t1=tw+H-1,*s1=MR+H-1;
AH MW*t2=tw+2*H-1,*s2=MR+2*H-1;
AH MW*t3=tw+4*H-1,*s3=MR+4*H-1;
MV(MX j=0;j<H;j+=8){
AB v0=AQ(p+j),v1=AQ(p+j+H),
v2=AQ(p+j+2*H),v3=AQ(p+j+3*H),
v4=AQ(p+j+4*H),v5=AQ(p+j+5*H),
v6=AQ(p+j+6*H),v7=AQ(p+j+7*H);
KO KP=[&](AB&a,AB&b,AB w,AB ws,AB wo,KL lazy=ED){
AB bm=shoup8x_s(b,w,ws,wo),LY=a;
if(lazy){a=AA(LY,bm);b=AA(AC(LY,bm),Pv);}
zc{a=DI(LY,bm,Pv);b=FE(LY,bm,Pv);}
};
KO JZ=[&](AB&a,AB&b,AH MW*w,AH MW*ws,KL lazy){
AB bm=CU(b,w,ws),LY=a;
if(lazy){a=AA(LY,bm);b=AA(AC(LY,bm),Pv);}
zc{a=DI(LY,bm,Pv);b=FE(LY,bm,Pv);}
};
AB w1=zf(t1+j),ws1=zf(s1+j),KQ=zf(s1+j+1);
KP(v0,v1,w1,ws1,KQ);KP(v2,v3,w1,ws1,KQ,KR);
KP(v4,v5,w1,ws1,KQ);KP(v6,v7,w1,ws1,KQ,KR);
{
AH AB w20=zf(t2+j),ws20=zf(s2+j),ws20o=zf(s2+j+1);
KP(v0,v2,w20,ws20,ws20o);KP(v4,v6,w20,ws20,ws20o,KR);
}
asm IV(""::"x"(v0),"x"(v2),"x"(v4),"x"(v6):"memory");
{
AH AB w21=zf(t2+j+H),ws21=zf(s2+j+H),ws21o=zf(s2+j+H+1);
KP(v1,v3,w21,ws21,ws21o);KP(v5,v7,w21,ws21,ws21o,KR);
}
JZ(v0,v4,t3+j,s3+j,DK);
JZ(v1,v5,t3+j+H,s3+j+H,DK);
JZ(v2,v6,t3+j+2*H,s3+j+2*H,DK);
JZ(v3,v7,t3+j+3*H,s3+j+3*H,DK);
BH(p+j,v0);BH(p+j+H,v1);
BH(p+j+2*H,v2);BH(p+j+3*H,v3);
BH(p+j+4*H,v4);BH(p+j+5*H,v5);
BH(p+j+6*H,v6);BH(p+j+7*H,v7);
}
}
AK BR AZ((BK))KK ar_live_final(MW*p,AH MW*tw,AH MW*MR){
AL MX H=512;
AH AB Pv=AF((MX)P);
AH MW*t1=tw+H-1,*s1=MR+H-1;
AH MW*t2=tw+2*H-1,*s2=MR+2*H-1;
AH MW*t3=tw+4*H-1,*s3=MR+4*H-1;
MV(MX j=0;j<H;j+=8){
AB v0=AQ(p+j),v1=AQ(p+j+H),
v2=AQ(p+j+2*H),v3=AQ(p+j+3*H),
v4=AQ(p+j+4*H),v5=AQ(p+j+5*H),
v6=AQ(p+j+6*H),v7=AQ(p+j+7*H);
KO KP=[&](AB&a,AB&b,AB w,AB ws,AB wo,KL lazy=ED){
AB bm=shoup8x_s(b,w,ws,wo),LY=a;
if(lazy){a=AA(LY,bm);b=AA(AC(LY,bm),Pv);}
zc{a=DI(LY,bm,Pv);b=FE(LY,bm,Pv);}
};
KO JZ=[&](AB&a,AB&b,AH MW*w,AH MW*ws,KL lazy){
AB bm=CU(b,w,ws),LY=a;
if(lazy){a=AA(LY,bm);b=AA(AC(LY,bm),Pv);}
zc{a=DI(LY,bm,Pv);b=FE(LY,bm,Pv);}
};
AB w1=zf(t1+j),ws1=zf(s1+j),KQ=zf(s1+j+1);
KP(v0,v1,w1,ws1,KQ);KP(v2,v3,w1,ws1,KQ,KR);
KP(v4,v5,w1,ws1,KQ);KP(v6,v7,w1,ws1,KQ,KR);
{
AH AB w20=zf(t2+j),ws20=zf(s2+j),ws20o=zf(s2+j+1);
KP(v0,v2,w20,ws20,ws20o);KP(v4,v6,w20,ws20,ws20o,KR);
}
asm IV(""::"x"(v0),"x"(v2),"x"(v4),"x"(v6):"memory");
{
AH AB w21=zf(t2+j+H),ws21=zf(s2+j+H),ws21o=zf(s2+j+H+1);
KP(v1,v3,w21,ws21,ws21o);KP(v5,v7,w21,ws21,ws21o,KR);
}
v0=DI(v0,CU(v4,t3+j,s3+j),Pv);v1=DI(v1,CU(v5,t3+j+H,s3+j+H),Pv);v2=DI(v2,CU(v6,t3+j+2*H,s3+j+2*H),Pv);
BH(p+j,v0);BH(p+j+H,v1);BH(p+j+2*H,v2);
if(j<424){v3=DI(v3,CU(v7,t3+j+3*H,s3+j+3*H),Pv);BH(p+j+3*H,v3);}
}
}
BG<MX H>AK KK dit_pass8(MW*x,MX L,AH MW*tw,AH MW*MR){
MV(MX i=0;i<L;i+=16*H){
FN<H,ED>(x+i,tw,MR);
if(i+8*H<L)FN<H,KR>(x+i+8*H,tw,MR);
}
}
BG<KL DK>AK BR AZ((BK))KK EE(
AB&v0,AB&v1,AB&v2,AB&v3,AB&v4,AB&v5,AB&v6,AB&v7,AH MW*tw,AH MW*MR){
AL MX H=8,j=0;
AH AB Pv=AF((MX)P);
AH MW*t1=tw+7,*s1=MR+7,*t2=tw+15,*s2=MR+15,*t3=tw+31,*s3=MR+31;
KO KP=[&](AB&a,AB&b,AB w,AB ws,AB wo,KL lazy=ED){
AB bm=shoup8x_s(b,w,ws,wo),LY=a;
if(lazy){a=AA(LY,bm);b=AA(AC(LY,bm),Pv);}
zc{a=DI(LY,bm,Pv);b=FE(LY,bm,Pv);}
};
KO JZ=[&](AB&a,AB&b,AH MW*w,AH MW*ws,KL lazy){
AB bm=CU(b,w,ws),LY=a;
if(lazy){a=AA(LY,bm);b=AA(AC(LY,bm),Pv);}
zc{a=DI(LY,bm,Pv);b=FE(LY,bm,Pv);}
};
AB w1=zf(t1+j),ws1=zf(s1+j),KQ=zf(s1+j+1);
KP(v0,v1,w1,ws1,KQ);KP(v2,v3,w1,ws1,KQ,KR);
KP(v4,v5,w1,ws1,KQ);KP(v6,v7,w1,ws1,KQ,KR);
AB w20=zf(t2+j),ws20=zf(s2+j),ws20o=zf(s2+j+1);
AB w21=zf(t2+j+H),ws21=zf(s2+j+H),ws21o=zf(s2+j+H+1);
KP(v0,v2,w20,ws20,ws20o);KP(v4,v6,w20,ws20,ws20o,KR);
KP(v1,v3,w21,ws21,ws21o);KP(v5,v7,w21,ws21,ws21o,KR);
JZ(v0,v4,t3+j,s3+j,DK);
JZ(v1,v5,t3+j+H,s3+j+H,DK);
JZ(v2,v6,t3+j+2*H,s3+j+2*H,DK);
JZ(v3,v7,t3+j+3*H,s3+j+3*H,DK);
}
AK BR AB GJ(AB w);
AK BR AB KG(AB a,AB b);
AK BR AB mont8x(AB a,AB ax,AB b,AB bx);
BG<KL Product=ED,KL LazyTail=ED,KL LiveFinal=ED>
AK KK FK(MW*x,MX L,AH MW*tw,AH MW*MR,AH MW*FX=DT){
KO CP=[&](MX HO){
AB v=AQ(x+HO);
if AL(Product){AB y=AQ(FX+HO);
v=mont8x(v,zf(x+HO+1),y,zf(FX+HO+1));}
BD v;
};
if AL(Product){if(L<8)MV(MX i=0;i<L;++i)x[i]=mm(x[i],FX[i]);}
AB Pv=AF((MX)P),M1=AF(-1),Z=BB();
MX LZ=0;
if(L>=8){
AH AB V4=AY((MX)tw[1],(MX)tw[2],1,1,(MX)tw[1],(MX)tw[2],1,1);
AH AB V4s=AY((MX)MR[1],(MX)MR[2],2,2,(MX)MR[1],(MX)MR[2],2,2);
AH AB V8=AY((MX)tw[3],(MX)tw[4],(MX)tw[5],(MX)tw[6],1,1,1,1);
AH AB V8s=AY((MX)MR[3],(MX)MR[4],(MX)MR[5],(MX)MR[6],2,2,2,2);
AH AB V8Q=AY((MX)tw[3],(MX)tw[4],(MX)tw[5],(MX)tw[6],
(MX)tw[3],(MX)tw[4],(MX)tw[5],(MX)tw[6]);
AH AB V8Qs=AY((MX)MR[3],(MX)MR[4],(MX)MR[5],(MX)MR[6],
(MX)MR[3],(MX)MR[4],(MX)MR[5],(MX)MR[6]);
AH AB V4P=AG((KI KI)tw[2]);
AH AB KS=AG((KI KI)MR[2]);
AH AB IDX8=AY(4,5,6,7,0,1,2,3);
AH AB IDXQ4=AY(0,1,0,1,4,5,4,5);
AH AB IDXQ8=AY(0,1,2,3,0,1,2,3);
MX i4=0;
MV(;i4+64<=L;i4+=64){
AB MH=CP(i4+0);
AB MC=CP(i4+8);
AB MI=CP(i4+16);
AB MD=CP(i4+24);
AB MJ=CP(i4+32);
AB ME=CP(i4+40);
AB MK=CP(i4+48);
AB MF=CP(i4+56);
{
{
AB y=AI(MH,0xB1);
MH=AA(AA(AO(MH,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
MH=AD(MH,AC(MH,Pv));
}
}
{
{
AB y=AI(MC,0xB1);
MC=AA(AA(AO(MC,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
MC=AD(MC,AC(MC,Pv));
}
}
{
{
AB y=AI(MI,0xB1);
MI=AA(AA(AO(MI,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
MI=AD(MI,AC(MI,Pv));
}
}
{
{
AB y=AI(MD,0xB1);
MD=AA(AA(AO(MD,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
MD=AD(MD,AC(MD,Pv));
}
}
{
{
AB y=AI(MJ,0xB1);
MJ=AA(AA(AO(MJ,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
MJ=AD(MJ,AC(MJ,Pv));
}
}
{
{
AB y=AI(ME,0xB1);
ME=AA(AA(AO(ME,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
ME=AD(ME,AC(ME,Pv));
}
}
{
{
AB y=AI(MK,0xB1);
MK=AA(AA(AO(MK,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
MK=AD(MK,AC(MK,Pv));
}
}
{
{
AB y=AI(MF,0xB1);
MF=AA(AA(AO(MF,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
MF=AD(MF,AC(MF,Pv));
}
}
{
{
AB PP=AS(MH,MC);
AB MM=BN<ED>(PP,V4P,KS);
AB LL=BF(MH,MC);
AB SS=AD(AA(LL,MM),AC(AA(LL,MM),Pv));
AB DD=AD(AC(LL,MM),AA(AC(LL,MM),Pv));
MH=BF(SS,DD);
MC=AS(SS,DD);
}
}
{
{
AB PP=AS(MI,MD);
AB MM=BN<ED>(PP,V4P,KS);
AB LL=BF(MI,MD);
AB SS=AD(AA(LL,MM),AC(AA(LL,MM),Pv));
AB DD=AD(AC(LL,MM),AA(AC(LL,MM),Pv));
MI=BF(SS,DD);
MD=AS(SS,DD);
}
}
{
{
AB PP=AS(MJ,ME);
AB MM=BN<ED>(PP,V4P,KS);
AB LL=BF(MJ,ME);
AB SS=AD(AA(LL,MM),AC(AA(LL,MM),Pv));
AB DD=AD(AC(LL,MM),AA(AC(LL,MM),Pv));
MJ=BF(SS,DD);
ME=AS(SS,DD);
}
}
{
{
AB PP=AS(MK,MF);
AB MM=BN<ED>(PP,V4P,KS);
AB LL=BF(MK,MF);
AB SS=AD(AA(LL,MM),AC(AA(LL,MM),Pv));
AB DD=AD(AC(LL,MM),AA(AC(LL,MM),Pv));
MK=BF(SS,DD);
MF=AS(SS,DD);
}
}
{
{
AB YX=AE(MH,MC,0x31);
AB MM=GI(YX,V8Q,V8Qs);
AB XY=AE(MH,MC,0x20);
AB SS=AA(XY,MM);
AB DD=AA(AC(XY,MM),Pv);
MH=AE(SS,DD,0x20);
MH=AD(MH,AC(MH,Pv));
MC=AE(SS,DD,0x31);
}
}
{
{
AB YX=AE(MI,MD,0x31);
AB MM=GI(YX,V8Q,V8Qs);
AB XY=AE(MI,MD,0x20);
AB SS=AA(XY,MM);
AB DD=AA(AC(XY,MM),Pv);
MI=AE(SS,DD,0x20);
MI=AD(MI,AC(MI,Pv));
MD=AE(SS,DD,0x31);
}
}
{
{
AB YX=AE(MJ,ME,0x31);
AB MM=GI(YX,V8Q,V8Qs);
AB XY=AE(MJ,ME,0x20);
AB SS=AA(XY,MM);
AB DD=AA(AC(XY,MM),Pv);
MJ=AE(SS,DD,0x20);
MJ=AD(MJ,AC(MJ,Pv));
ME=AE(SS,DD,0x31);
}
}
{
{
AB YX=AE(MK,MF,0x31);
AB MM=GI(YX,V8Q,V8Qs);
AB XY=AE(MK,MF,0x20);
AB SS=AA(XY,MM);
AB DD=AA(AC(XY,MM),Pv);
MK=AE(SS,DD,0x20);
MK=AD(MK,AC(MK,Pv));
MF=AE(SS,DD,0x31);
}
}
if(L==4096||L==8192||L==16384){
if(i4&64)EE<KR>(MH,MC,MI,MD,MJ,ME,MK,MF,tw,MR);
zc EE<ED>(MH,MC,MI,MD,MJ,ME,MK,MF,tw,MR);
}
BH((KK*)((x+i4+0)),MH);
BH((KK*)((x+i4+8)),MC);
BH((KK*)((x+i4+16)),MI);
BH((KK*)((x+i4+24)),MD);
BH((KK*)((x+i4+32)),MJ);
BH((KK*)((x+i4+40)),ME);
BH((KK*)((x+i4+48)),MK);
BH((KK*)((x+i4+56)),MF);
}
MV(;i4<L;i4+=8){
AB v=CP(i4);
{
AB y=AI(v,0xB1);
v=AA(AA(AO(v,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
v=AD(v,AC(v,Pv));
}
{
AB y=AI(v,0x4E);
y=DQ(y,V4,V4s);
AB sa=AD(AA(v,y),AC(AA(v,y),Pv));
AB d=AD(AC(v,y),AA(AC(v,y),Pv));
d=BE(d,IDXQ4);
v=AT(sa,d,0xCC);
}
{
AB y=BE(v,IDX8);
y=DQ(y,V8,V8s);
AB sa=AD(AA(v,y),AC(AA(v,y),Pv));
AB d=AD(AC(v,y),AA(AC(v,y),Pv));
d=BE(d,IDXQ8);
v=AT(sa,d,0xF0);
}
BH((KK*)((x+i4)),v);
}
LZ=7;
MX MQ=16;
if(L==1024){
dit_pass8<8>(x,L,tw,MR);dit_pass8<64>(x,L,tw,MR);
MQ=1024;LZ=511;
}
if(L==4096||L==8192||L==16384){
dit_pass8<64>(x,L,tw,MR);
if AL(LiveFinal)ar_live_final(x,tw,MR);zc dit_pass8<512>(x,L,tw,MR);
MQ=8192;LZ=4095;
}
MV(;(MQ<<1)<=L;MQ<<=2){
MX h=MQ>>1;
AH MW*t1=tw+LZ,*ts1=MR+LZ;
AH MW*t2=t1+h,*ts2=ts1+h;
AH MW*t3=t2+h,*ts3=ts2+h;
LZ+=3*h;
MV(MX i=0;i<L;i+=(MQ<<1)){
MW*p=x+i;
MV(MX j=0;j<h;j+=8){
AB WV1=zf((AH KK*)((t1+j))),WS1=zf((AH KK*)((ts1+j)));
AB WV2=zf((AH KK*)((t2+j))),WS2=zf((AH KK*)((ts2+j)));
AB WV3=zf((AH KK*)((t3+j))),WS3=zf((AH KK*)((ts3+j)));
AB A=AQ((AH KK*)(p+j));
AB B=AQ((AH KK*)(p+j+h));
AB C=AQ((AH KK*)(p+j+2*h));
AB D=AQ((AH KK*)(p+j+3*h));
AB Bm=DQ(B,WV1,WS1),Dm=DQ(D,WV1,WS1);
AB Ap=DI(A,Bm,Pv),Bp=FE(A,Bm,Pv);
AB Cp=AA(C,Dm),Dp=AA(AC(C,Dm),Pv);
AB Cm=DQ(Cp,WV2,WS2),Dn=DQ(Dp,WV3,WS3);
if(LazyTail&&(MQ<<1)==L){
BH(p+j,AA(Ap,Cm));
BH(p+j+2*h,AA(AC(Ap,Cm),Pv));
BH(p+j+h,AA(Bp,Dn));
BH(p+j+3*h,AA(AC(Bp,Dn),Pv));
}zc{
BH((KK*)(p+j),DI(Ap,Cm,Pv));
BH((KK*)(p+j+2*h),FE(Ap,Cm,Pv));
BH((KK*)(p+j+h),DI(Bp,Dn,Pv));
BH((KK*)(p+j+3*h),FE(Bp,Dn,Pv));
}
}
}
}
if(MQ<=L){
MX h=MQ>>1;
AH MW*t=tw+LZ,*ts=MR+LZ;LZ+=h;
MV(MX i=0;i<L;i+=MQ){
MW*p=x+i,*q=x+i+h;
MV(MX j=0;j<h;j+=8){
AB u=AQ((AH KK*)(p+j));
AB v=GI(AQ((AH KK*)(q+j)),
zf((AH KK*)(t+j)),zf((AH KK*)(ts+j)));
BH((KK*)(p+j),DI(u,v,Pv));
BH((KK*)(q+j),FE(u,v,Pv));
}
}
}
}zc{
MV(MX MQ=2;MQ<=L;MQ<<=1){
MX h=MQ>>1;
AH MW*t=tw+LZ;LZ+=h;
MV(MX i=0;i<L;i+=MQ){
MW*p=x+i,*q=x+i+h;
MV(MX j=0;j<h;j++){
MW u=p[j],v=mm(q[j],t[j]);
MW sa=u+v;if(sa>=P)sa-=P;
MW d=u+P-v;if(d>=P)d-=P;
p[j]=sa;q[j]=d;
}
}
}
}
}
BG<MX H3,KL IW=ED>AK KK DA(MW*x,MX L,AH MW*tw,AH MW*MR){
AH AB Pv=AF((MX)P);
AH MX MQ=H3<<3;
AH MW*t1=tw+(MQ>>1)-1,*s1=MR+(MQ>>1)-1;
AH MW*t2=tw+(MQ>>2)-1,*s2=MR+(MQ>>2)-1;
AH MW*t3=tw+H3-1,*s3=MR+H3-1;
MV(MX i=0;i<L;i+=MQ){
MW*p=x+i;
MV(MX j=0;j<H3;j+=8){
AB v0=AQ(p+j),v1=AQ(p+j+H3),
v2=AQ(p+j+2*H3),v3=AQ(p+j+3*H3);
AB v4,v5,v6,v7;
KO dif2=[&](AB&a,AB&b,AB w,AB ws,AB wo){
AB sm=DI(a,b,Pv),df=AA(AC(a,b),Pv);
a=sm;b=shoup8x(df,w,ws,wo);
};
KO dif2p=[&](AB&a,AB&b,AH MW*w,AH MW*ws){
AB sm=DI(a,b,Pv),df=AA(AC(a,b),Pv);
a=sm;b=CU(df,w,ws);
};
if AL(IW){
v4=CU(v0,t1+j,s1+j);
v5=CU(v1,t1+j+H3,s1+j+H3);
v6=CU(v2,t1+j+2*H3,s1+j+2*H3);
v7=CU(v3,t1+j+3*H3,s1+j+3*H3);
}zc{
v4=AQ(p+j+4*H3);v5=AQ(p+j+5*H3);
v6=AQ(p+j+6*H3);v7=AQ(p+j+7*H3);
dif2p(v0,v4,t1+j,s1+j);
dif2p(v1,v5,t1+j+H3,s1+j+H3);
dif2p(v2,v6,t1+j+2*H3,s1+j+2*H3);
dif2p(v3,v7,t1+j+3*H3,s1+j+3*H3);
}
{
AH AB w20=zf(t2+j),s20=zf(s2+j),s20o=zf(s2+j+1);
dif2(v0,v2,w20,s20,s20o);dif2(v4,v6,w20,s20,s20o);
}
asm IV(""::"x"(v0),"x"(v2),"x"(v4),"x"(v6):"memory");
{
AH AB w21=zf(t2+j+H3),s21=zf(s2+j+H3),s21o=zf(s2+j+H3+1);
dif2(v1,v3,w21,s21,s21o);dif2(v5,v7,w21,s21,s21o);
}
asm IV(""::"x"(v1),"x"(v3),"x"(v5),"x"(v7):"memory");
AB w3=zf(t3+j),ws3=zf(s3+j),ws3o=zf(s3+j+1);
dif2(v0,v1,w3,ws3,ws3o);
BH(p+j,v0);BH(p+j+H3,v1);
dif2(v2,v3,w3,ws3,ws3o);
BH(p+j+2*H3,v2);BH(p+j+3*H3,v3);
dif2(v4,v5,w3,ws3,ws3o);
BH(p+j+4*H3,v4);BH(p+j+5*H3,v5);
dif2(v6,v7,w3,ws3,ws3o);
BH(p+j+6*H3,v6);BH(p+j+7*H3,v7);
}
}
}
BG<KL IW=ED,KL FO=ED,KL ResidentInner=ED>
AK KK DV(MW*x,MX L,AH MW*tw,AH MW*MR){
AB Pv=AF((MX)P),M1=AF(-1),Z=BB();
if(L>=8){
MX MQ=L;
if AL(ResidentInner){
DA<256>(x,L,tw,MR);DA<32>(x,L,tw,MR);MQ=32;
}zc{
if(L==16384){
DA<2048>(x,L,tw,MR);
MV(MX IK=0;IK<L;IK+=2048)DV<ED,FO,KR>(x+IK,2048,tw,MR);
BD;
}
if(L==1024){
DA<128>(x,L,tw,MR);DA<16>(x,L,tw,MR);
MQ=16;
}
if(L==4096){
DA<512,IW>(x,L,tw,MR);DA<64>(x,L,tw,MR);DA<8>(x,L,tw,MR);
MQ=8;
}zc if(L==8192){
DA<1024>(x,L,tw,MR);DA<128>(x,L,tw,MR);DA<16>(x,L,tw,MR);
MQ=16;
}
if(L==16384){
DA<2048>(x,L,tw,MR);DA<256>(x,L,tw,MR);DA<32>(x,L,tw,MR);
MQ=32;
}
}
AH KL Fuse32=(MQ==32&&(L&63)==0);
if(!Fuse32&&L!=4096&&L!=8192)
MV(;MQ>=32;MQ>>=2){
MX h=MQ>>1,h2=MQ>>2;
AH MW*t1=tw+h-1,*ts1=MR+h-1;
AH MW*t2=t1+h2,*ts2=ts1+h2;
AH MW*t3=tw+h2-1,*ts3=MR+h2-1;
MV(MX i=0;i<L;i+=MQ){
MW*p=x+i;
MV(MX j=0;j<h2;j+=8){
AB WV1=zf((AH KK*)((t1+j))),WS1=zf((AH KK*)((ts1+j)));
AB WV2=zf((AH KK*)((t2+j))),WS2=zf((AH KK*)((ts2+j)));
AB WV3=zf((AH KK*)((t3+j))),WS3=zf((AH KK*)((ts3+j)));
AB v0=AQ((AH KK*)((p+j)));
AB v1=AQ((AH KK*)((p+j+h2)));
AB v2=AQ((AH KK*)((p+j+h)));
AB v3=AQ((AH KK*)((p+j+h+h2)));
AB s02=AD(AA(v0,v2),AC(AA(v0,v2),Pv));
AB d02=AC(v0,v2);
AB s13=AD(AA(v1,v3),AC(AA(v1,v3),Pv));
AB d13=AC(v1,v3);
d02=AA(d02,Pv);
d13=AA(d13,Pv);
d02=DQ(d02,WV1,WS1);
d13=DQ(d13,WV2,WS2);
AB ra=AD(AA(s02,s13),AC(AA(s02,s13),Pv));
AB rb=AA(AC(s02,s13),Pv);
rb=DQ(rb,WV3,WS3);
AB rc=AD(AA(d02,d13),AC(AA(d02,d13),Pv));
AB rd=AA(AC(d02,d13),Pv);
rd=DQ(rd,WV3,WS3);
BH((KK*)((p+j)),ra);
BH((KK*)((p+j+h2)),rb);
BH((KK*)((p+j+h)),rc);
BH((KK*)((p+j+h+h2)),rd);
}
}
}
if(Fuse32)MQ=8;
if(MQ>=16){
MX h=MQ>>1;
AH MW*t=tw+h-1,*ts=MR+h-1;
MV(MX i=0;i<L;i+=MQ){
MW*p=x+i,*q=x+i+h;
MV(MX j=0;j<h;j+=8){
AB u=AQ((AH KK*)((p+j)));
AB v=AQ((AH KK*)((q+j)));
AB w=zf((AH KK*)((t+j)));
AB ws=zf((AH KK*)((ts+j)));
AB sa=AD(AA(u,v),AC(AA(u,v),Pv));
AB d=AA(AC(u,v),Pv);
d=GI(d,w,ws);
BH((KK*)((p+j)),sa);
BH((KK*)((q+j)),d);
}
}
}
AH AB V8=AY(1,1,1,1,(MX)tw[3],(MX)tw[4],(MX)tw[5],(MX)tw[6]);
AH AB V8s=AY(2,2,2,2,(MX)MR[3],(MX)MR[4],(MX)MR[5],(MX)MR[6]);
AH AB V8N=AY((MX)tw[3],(MX)tw[4],(MX)tw[5],(MX)tw[6],
(MX)(P-tw[3]),(MX)(P-tw[4]),(MX)(P-tw[5]),(MX)(P-tw[6]));
AH AB V8Ns=AY((MX)MR[3],(MX)MR[4],(MX)MR[5],(MX)MR[6],
(MX)EV(P-tw[3]),(MX)EV(P-tw[4]),(MX)EV(P-tw[5]),(MX)EV(P-tw[6]));
AH AB V4=AY(1,1,(MX)tw[1],(MX)tw[2],1,1,(MX)tw[1],(MX)tw[2]);
AH AB V4s=AY(2,2,(MX)MR[1],(MX)MR[2],2,2,(MX)MR[1],(MX)MR[2]);
AH AB V4P=AG((KI KI)tw[2]);
AH AB KS=AG((KI KI)MR[2]);
AH AB IDX8=AY(4,5,6,7,0,1,2,3);
KO finish32=[&](AB&v0,AB&v1,AB&v2,AB&v3){
AB s02=DI(v0,v2,Pv),s13=DI(v1,v3,Pv);
AB d02=CU(AA(AC(v0,v2),Pv),tw+15,MR+15);
AB d13=CU(AA(AC(v1,v3),Pv),tw+23,MR+23);
AB ra=DI(s02,s13,Pv),rc=DI(d02,d13,Pv);
AB rb=CU(AA(AC(s02,s13),Pv),tw+7,MR+7);
AB rd=CU(AA(AC(d02,d13),Pv),tw+7,MR+7);
v0=ra;v1=rb;v2=rc;v3=rd;
};
MX i4=0;
MV(;i4+64<=L;i4+=64){
AB MH=AQ((AH KK*)((x+i4+0)));
AB MC=AQ((AH KK*)((x+i4+8)));
AB MI=AQ((AH KK*)((x+i4+16)));
AB MD=AQ((AH KK*)((x+i4+24)));
AB MJ=AQ((AH KK*)((x+i4+32)));
AB ME=AQ((AH KK*)((x+i4+40)));
AB MK=AQ((AH KK*)((x+i4+48)));
AB MF=AQ((AH KK*)((x+i4+56)));
if(Fuse32){finish32(MH,MC,MI,MD);finish32(MJ,ME,MK,MF);}
{
{
AB X=AE(MH,MC,0x21);
AB Y=AE(MH,MC,0x30);
AB S=AD(AA(X,Y),AC(AA(X,Y),Pv));
AB D=AA(AC(Y,X),Pv);
D=DQ(D,V8N,V8Ns);
MH=AE(S,D,0x20);
MC=AE(S,D,0x31);
}
}
{
{
AB X=AE(MI,MD,0x21);
AB Y=AE(MI,MD,0x30);
AB S=AD(AA(X,Y),AC(AA(X,Y),Pv));
AB D=AA(AC(Y,X),Pv);
D=DQ(D,V8N,V8Ns);
MI=AE(S,D,0x20);
MD=AE(S,D,0x31);
}
}
{
{
AB X=AE(MJ,ME,0x21);
AB Y=AE(MJ,ME,0x30);
AB S=AD(AA(X,Y),AC(AA(X,Y),Pv));
AB D=AA(AC(Y,X),Pv);
D=DQ(D,V8N,V8Ns);
MJ=AE(S,D,0x20);
ME=AE(S,D,0x31);
}
}
{
{
AB X=AE(MK,MF,0x21);
AB Y=AE(MK,MF,0x30);
AB S=AD(AA(X,Y),AC(AA(X,Y),Pv));
AB D=AA(AC(Y,X),Pv);
D=DQ(D,V8N,V8Ns);
MK=AE(S,D,0x20);
MF=AE(S,D,0x31);
}
}
{
{
AB yu=AI(MH,0x4E);
AB saU=AD(AA(MH,yu),AC(AA(MH,yu),Pv));
AB du=AC(yu,MH);
du=AA(du,Pv);
AB yv=AI(MC,0x4E);
AB saV=AD(AA(MC,yv),AC(AA(MC,yv),Pv));
AB dv=AC(yv,MC);
dv=AA(dv,Pv);
AB PP=AS(du,dv);
AB MM=BN<KR>(PP,V4P,KS);
MH=AT(saU,BY(MM,8),0xCC);
MC=AT(saV,MM,0xCC);
}
}
{
{
AB yu=AI(MI,0x4E);
AB saU=AD(AA(MI,yu),AC(AA(MI,yu),Pv));
AB du=AC(yu,MI);
du=AA(du,Pv);
AB yv=AI(MD,0x4E);
AB saV=AD(AA(MD,yv),AC(AA(MD,yv),Pv));
AB dv=AC(yv,MD);
dv=AA(dv,Pv);
AB PP=AS(du,dv);
AB MM=BN<KR>(PP,V4P,KS);
MI=AT(saU,BY(MM,8),0xCC);
MD=AT(saV,MM,0xCC);
}
}
{
{
AB yu=AI(MJ,0x4E);
AB saU=AD(AA(MJ,yu),AC(AA(MJ,yu),Pv));
AB du=AC(yu,MJ);
du=AA(du,Pv);
AB yv=AI(ME,0x4E);
AB saV=AD(AA(ME,yv),AC(AA(ME,yv),Pv));
AB dv=AC(yv,ME);
dv=AA(dv,Pv);
AB PP=AS(du,dv);
AB MM=BN<KR>(PP,V4P,KS);
MJ=AT(saU,BY(MM,8),0xCC);
ME=AT(saV,MM,0xCC);
}
}
{
{
AB yu=AI(MK,0x4E);
AB saU=AD(AA(MK,yu),AC(AA(MK,yu),Pv));
AB du=AC(yu,MK);
du=AA(du,Pv);
AB yv=AI(MF,0x4E);
AB saV=AD(AA(MF,yv),AC(AA(MF,yv),Pv));
AB dv=AC(yv,MF);
dv=AA(dv,Pv);
AB PP=AS(du,dv);
AB MM=BN<KR>(PP,V4P,KS);
MK=AT(saU,BY(MM,8),0xCC);
MF=AT(saV,MM,0xCC);
}
}
{
{
AB y=AI(MH,0xB1);
MH=AA(AA(AO(MH,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
if AL(!FO)MH=AD(MH,AC(MH,Pv));
}
}
{
{
AB y=AI(MC,0xB1);
MC=AA(AA(AO(MC,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
if AL(!FO)MC=AD(MC,AC(MC,Pv));
}
}
{
{
AB y=AI(MI,0xB1);
MI=AA(AA(AO(MI,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
if AL(!FO)MI=AD(MI,AC(MI,Pv));
}
}
{
{
AB y=AI(MD,0xB1);
MD=AA(AA(AO(MD,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
if AL(!FO)MD=AD(MD,AC(MD,Pv));
}
}
{
{
AB y=AI(MJ,0xB1);
MJ=AA(AA(AO(MJ,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
if AL(!FO)MJ=AD(MJ,AC(MJ,Pv));
}
}
{
{
AB y=AI(ME,0xB1);
ME=AA(AA(AO(ME,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
if AL(!FO)ME=AD(ME,AC(ME,Pv));
}
}
{
{
AB y=AI(MK,0xB1);
MK=AA(AA(AO(MK,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
if AL(!FO)MK=AD(MK,AC(MK,Pv));
}
}
{
{
AB y=AI(MF,0xB1);
MF=AA(AA(AO(MF,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
if AL(!FO)MF=AD(MF,AC(MF,Pv));
}
}
BH((KK*)((x+i4+0)),MH);
BH((KK*)((x+i4+8)),MC);
BH((KK*)((x+i4+16)),MI);
BH((KK*)((x+i4+24)),MD);
BH((KK*)((x+i4+32)),MJ);
BH((KK*)((x+i4+40)),ME);
BH((KK*)((x+i4+48)),MK);
BH((KK*)((x+i4+56)),MF);
}
MV(;i4<L;i4+=8){
AB v=AQ((AH KK*)((x+i4)));
{
AB y=BE(v,IDX8);
AB sa=AD(AA(v,y),AC(AA(v,y),Pv));
AB d0=AC(y,v);
d0=AA(d0,Pv);
AB d=DQ(d0,V8,V8s);
v=AT(sa,d,0xF0);
}
{
AB y=AI(v,0x4E);
AB sa=AD(AA(v,y),AC(AA(v,y),Pv));
AB d=AC(y,v);
d=AA(d,Pv);
d=DQ(d,V4,V4s);
v=AT(sa,d,0xCC);
}
{
AB y=AI(v,0xB1);
v=AA(AA(AO(v,AG((KI KI)0xffffffff00000000ull)),y),
AG((KI KI)((MU)(P+1)<<32)));
if AL(!FO)v=AD(v,AC(v,Pv));
}
BH((KK*)((x+i4)),v);
}
}zc{
MV(MX MQ=L;MQ>=2;MQ>>=1){
MX h=MQ>>1;
AH MW*t=tw+h-1;
MV(MX i=0;i<L;i+=MQ){
MW*p=x+i,*q=x+i+h;
MV(MX j=0;j<h;j++){
MW u=p[j],v=q[j];
MW sa=u+v;if(sa>=P)sa-=P;
MW d=u+P-v;if(d>=P)d-=P;
p[j]=sa;q[j]=mm(d,t[j]);
}
}
}
}
}
AK AB FY[4];
AK MW g_psums;
AK MW psum_take(){
AB v=AA(AA(FY[0],FY[1]),AA(FY[2],FY[3]));
v=AA(v,AE(v,v,0x01));
v=AA(v,AI(v,0x4E));
v=AA(v,AI(v,0xB1));
BD g_psums+(MW)_mm256_extract_epi32(v,0);
}
AK KK psum_reset(){MV(MX i=0;i<4;i++)FY[i]=BB();g_psums=0;}
AK BR AB GJ(AB w){
AH AB ML=AF(SHMAGIC);
AB lo=AR(w,ML);
AB hi=AR(BX(w,32),ML);
AB m=AT(BX(lo,32),_mm256_slli_epi64(BX(hi,32),32),0xAA);
BD AA(AA(w,w),m);
}
AK BR KK KT(AB*r){
AB t0=CY(r[0],r[1]),t1=CZ(r[0],r[1]);
AB t2=CY(r[2],r[3]),t3=CZ(r[2],r[3]);
AB t4=CY(r[4],r[5]),t5=CZ(r[4],r[5]);
AB t6=CY(r[6],r[7]),t7=CZ(r[6],r[7]);
AB u0=BF(t0,t2),u1=AS(t0,t2);
AB u2=BF(t1,t3),u3=AS(t1,t3);
AB u4=BF(t4,t6),u5=AS(t4,t6);
AB u6=BF(t5,t7),u7=AS(t5,t7);
r[0]=AE(u0,u4,0x20);r[1]=AE(u1,u5,0x20);
r[2]=AE(u2,u6,0x20);r[3]=AE(u3,u7,0x20);
r[4]=AE(u0,u4,0x31);r[5]=AE(u1,u5,0x31);
r[6]=AE(u2,u6,0x31);r[7]=AE(u3,u7,0x31);
}
AK KK pointwise_mul_avx(MW*A,AH MW*B,MW n,MW sc,MW sx){
(KK)sc;
KI k=0;
MV(MX r=0;k<(KI)n;r++){
KI lim=(KI)sx-PADC_;
if(lim>(KI)n-k)lim=(KI)n-k;
MW*a=A+(KI)r*sx;
AH MW*b=KJ((KI)r*sx);
KI i=0;
MV(;i+8<=lim;i+=8){
AB x=AQ((AH KK*)(a+i));
AB y=AQ((AH KK*)(b+i));
BH((KK*)(a+i),DQ(x,y,GJ(y)));
}
MV(;i<lim;i++)a[i]=mm(a[i],b[i]);
k+=lim;
}
}
AK MW NPI=0;
AK MW MA;
AK BR MW HN(MW a,MW b){
MU z=(MU)a*(MU)b;
MW m=(MW)((MU)(MW)z*(MU)NPI);
MU t=(z+(MU)m*(MU)P)>>32;
BD(MW)(t>=P?t-P:t);
}
AK BR AB mont8x(AB a,AB ax,AB b,AB bx){
AB P64=AG((KI KI)P),NP=AG((KI KI)NPI);
AB Pv=AF((MX)P);
AB tlo=AR(a,b),thi=AR(ax,bx);
AB e2=AR(tlo,NP),o2=AR(thi,NP);
AB e4=AR(e2,P64),o4=AR(o2,P64);
AB e5=DL(tlo,e4),o5=DL(thi,o4);
AB u=CS(BA(e5,4),o5);
BD AD(u,AC(u,Pv));
}
AK BR AB KG(AB a,AB b){
AB P64=AG((KI KI)P),NP=AG((KI KI)NPI);
AB Pv=AF((MX)P);
AB ahi=BA(a,4),bhi=BA(b,4);
AB tlo=AR(a,b),thi=AR(ahi,bhi);
AB e2=AR(tlo,NP),o2=AR(thi,NP);
AB e4=AR(e2,P64),o4=AR(o2,P64);
AB e5=DL(tlo,e4),o5=DL(thi,o4);
AB u=CS(BA(e5,4),o5);
BD AD(u,AC(u,Pv));
}
AK KK scale_row_prepared(MW*LT,AH MW*MO,MW k,MW ks){
AH AB kv=AF((MX)k);
AH AB ksv=AF((MX)ks);
MV(MX v=0;v<TS;v+=8)
BH(LT+v,DQ(AQ(MO+v),kv,ksv));
}
AK KK EF(MW*LT,AH MW*MO,MW kM){
AH MW k=HN(kM,1u);
AH AB kv=AF((MX)k);
AH AB ks=AF((MX)EV(k));
MV(MX v=0;v<TS;v+=8)
BH(LT+v,DQ(AQ(MO+v),kv,ks));
}
AK KK twiddle_rows_mont(MW*TW,AH MW*RVM){
AB DG[TS/8],EY[TS/8];
AH AB one=AF(1);
MV(MX v=0;v<TS;v+=8){
DG[v/8]=KG(AQ(RVM+v),one);
EY[v/8]=GJ(DG[v/8]);
}
MV(MX u=1;u<TS;++u){
AH MW*prev=TW+(u-1)*TS;
MW*LR=TW+u*TS;
MV(MX v=0;v<TS;v+=8)
BH(LR+v,DQ(AQ(prev+v),
DG[v/8],EY[v/8]));
}
}
AK KK ET(AH MW*RV,AB*EN,AB*FU){
MV(MX v=0;v<TS;v+=8){
EN[v/8]=KG(AQ(RV+v),AF(1));
FU[v/8]=GJ(EN[v/8]);
}
}
AK KK FL(MW*TW,AH AB*DG,AH AB*EY){
MV(MX u=1;u<TS;++u){
AH MW*prev=TW+(u-1)*TS;
MW*LR=TW+u*TS;
MV(MX v=0;v<TS;v+=8)
BH(LR+v,DQ(AQ(prev+v),
DG[v/8],EY[v/8]));
}
}
AK KK scale_row_avx(MW*LT,AH MW*MO,MW k){
AH AB kv=AF((MX)k),ks=AF((MX)EV(k));
MV(MX v=0;v<TS;v+=8)
BH((KK*)((LT+v)),DQ(AQ((AH KK*)((MO+v))),kv,ks));
}
AK KK twiddle_rows_avx(MW*TW,AH MW*RV){
AB RVS[TS/8];
MV(MX v=0;v<TS;v+=8)RVS[v>>3]=GJ(AQ((AH KK*)((RV+v))));
MV(MX u=1;u<TS;u++){
AH MW*prv=TW+(u-1)*TS;
MW*LR=TW+u*TS;
MV(MX v=0;v<TS;v+=8){
AB r=AQ((AH KK*)((RV+v)));
BH((KK*)((LR+v)),DQ(AQ((AH KK*)((prv+v))),r,RVS[v>>3]));
}
}
}
AK KK corner_tile_avx(AH MW*in,MW*out,MX A0,MX B0,MX IS,MX GK,MX FZ){
MV(MX u0=0;u0<TS;u0+=8){
MV(MX v0=0;v0<TS;v0+=8){
AB r[8];
MV(MX k=0;k<8;k++){
AH MW*s=in+(MU)(A0+u0+k)*IS+B0+v0;
AH MW*tw=TW+(u0+k)*TS+v0;
AB x=AQ((AH KK*)(s));
AB w=AQ((AH KK*)(tw));
r[k]=KG(x,w);
}
KT(r);
MV(MX k=0;k<8;k++)
BH((KK*)(KM+(v0+k)*TS+u0),r[k]);
}
}
MV(MX v=0;v<TS;v++){
MW*d=FZ?KJ((KI)(B0+v)*GK+A0):out+(MU)(B0+v)*GK+A0;
AH MW*s=KM+v*TS;
if((((GA)d)&63u)==0u){
MV(MX u=0;u<TS;u+=16)NTC(d+u,s+u);
}zc{
MV(MX u=0;u<TS;u+=8)BH((KK*)(d+u),AQ((AH KK*)(s+u)));
}
}
}
AK KK corner_tile_avx_blk(AH MW*in,MW*out,MX A0c,MX B0,MX IS,MX GK,MX FZ){
MV(MX u0=0;u0<TS;u0+=8){
MV(MX v0=0;v0<TS;v0+=8){
AB r[8];
MV(MX k=0;k<8;k++){
AH MW*s=in+(MU)(u0+k)*IS+B0+v0;
AH MW*tw=TW+(u0+k)*TS+v0;
r[k]=KG(AQ((AH KK*)(s)),AQ((AH KK*)(tw)));
}
KT(r);
MV(MX k=0;k<8;k++)
BH((KK*)(KM+(v0+k)*TS+u0),r[k]);
}
}
MV(MX v=0;v<TS;v++){
MW*d=FZ?KJ((KI)(B0+v)*GK+A0c):out+(MU)(B0+v)*GK+A0c;
AH MW*s=KM+v*TS;
if((((GA)d)&63u)==0u){
MV(MX u=0;u<TS;u+=16)NTC(d+u,s+u);
}zc{
MV(MX u=0;u<TS;u+=8)BH((KK*)(d+u),AQ((AH KK*)(s+u)));
}
}
}
AK KK corner_tile_avx_to(AH MW*in,MW*KU,MX B0,MX IS){
(KK)IS;
AH KI SRF_=(KI)(NR_+PADB_);
MV(MX u0=0;u0<TS;u0+=8){
MV(MX v0=0;v0<TS;v0+=8){
AB r[8];
{
{AH MW*pf=in+B0+v0+(MU)(u0+8)*SRF_;
MV(MX k=0;k<8;k++)AP((AH KV*)(pf+(MU)k*SRF_),AW);}
AH MW*sb=in+B0+v0+(MU)u0*SRF_;
AH MW*tb=TW+(MU)u0*TS+v0;
MV(MX k=0;k<8;k++)
r[k]=mont8x(zf((AH KK*)(sb+(MU)k*SRF_)),zf((AH KK*)(sb+(MU)k*SRF_+1)),
zf((AH KK*)(tb+(KI)k*TS)),zf((AH KK*)(tb+(KI)k*TS+1)));
}
KT(r);
MV(MX k=0;k<8;k++)
BH((KK*)(KU+(v0+k)*TS+u0),r[k]);
}
}
}
AK KK GO(AH MW*MO,MW*S,MX r0,MX c0,MX R,MX C,MX LU,MX JL){
MV(MX rb0=0;rb0<TS;rb0+=8){
MV(MX cb0=0;cb0<TS;cb0+=16){
AB r[8];
if(JL){
MV(MX k=0;k<8;k++)r[k]=BB();
}zc{
MV(MX k=0;k<8;k++){
AH MW*s=MO+(MU)(r0+rb0+k)*C+c0+cb0;
AB x=DU(MO,(MU)(s-MO));
if(LU){
AB y=AC(x,AF(4));
AB z=AA(x,AF((MX)(P-4)));
x=AD(y,z);
}
if(CM){AH AB pp=AF(P),zz=BB();x=AC(x,AF((MX)0x80000000u));x=AA(x,BP(CN(zz,x),pp));x=AA(x,BP(CN(zz,x),pp));}x=AD(x,AC(x,AF(P)));x=AD(x,AC(x,AF(P)));r[k]=x;
}
}
KT(r);
MV(MX j=0;j<8;j++)
BH((KK*)(KM+(cb0+j)*TS+rb0),r[j]);
{
MX cb0b=cb0+8;
AB r2[8];
if(JL){
MV(MX k=0;k<8;k++)r2[k]=BB();
}zc{
MV(MX k=0;k<8;k++){
AH MW*s=MO+(MU)(r0+rb0+k)*C+c0+cb0b;
AB x=DU(MO,(MU)(s-MO));
if(LU){
AB y=AC(x,AF(4));
AB z=AA(x,AF((MX)(P-4)));
x=AD(y,z);
}
r2[k]=x;
}
}
KT(r2);
MV(MX j=0;j<8;j++)
BH((KK*)(KM+(cb0b+j)*TS+rb0),r2[j]);
}
}
}
MV(MX cb=0;cb<TS;cb++){
MW*d=S+(MU)(c0+cb)*R+r0;
AH MW*s=KM+cb*TS;
MV(MX rb=0;rb<TS;rb+=8)BH((KK*)(d+rb),AQ((AH KK*)(s+rb)));
}
}
AK KK FP(AH MW*MO,MW*S,MX r0,MX c0,MX C,MX dstr,MX LU,MX JL){
(KK)C;(KK)dstr;
AH KI CF_=(KI)NC_,DF_=(KI)(NR_+PADB_);
MV(MX rb0=0;rb0<TS;rb0+=8){
MV(MX cb0=0;cb0<TS;cb0+=8){
{AH MW*pf=MO+c0+cb0+(MU)(r0+rb0+8)*CF_;
if(DH&&MO==ES){AH MW*pm=MO+zl-8-(c0+cb0+(MU)(r0+rb0+8)*CF_);
MV(MX k=0;k<8;k++)AP((AH KV*)(pm-(MU)k*CF_),AW);}
zc MV(MX k=0;k<8;k++)AP((AH KV*)(pf+(MU)k*CF_),AW);}
AB r[8];
if(JL){
MV(MX k=0;k<8;k++)r[k]=BB();
}zc{
AH MW*sb=MO+(MU)(r0+rb0)*CF_+c0+cb0;
MV(MX k=0;k<8;k++){
AB x=DU(MO,(MU)(sb+(MU)k*CF_-MO));
FY[k&3]=AA(FY[k&3],x);
if(LU){
AB y=AC(x,AF(4));
AB z=AA(x,AF((MX)(P-4)));
x=AD(y,z);
}
if(CM){AH AB pp=AF(P),zz=BB();x=AC(x,AF((MX)0x80000000u));x=AA(x,BP(CN(zz,x),pp));x=AA(x,BP(CN(zz,x),pp));}x=AD(x,AC(x,AF(P)));x=AD(x,AC(x,AF(P)));r[k]=x;
}
}
KT(r);
{
AH MW*db=S+(MU)r0+rb0;
MV(MX j=0;j<8;j++)
BH((KK*)(db+(KI)(cb0+j)*DF_),r[j]);
}
}
}
}
AK KK load_block(AH MW*MO,MW KW,MW*S,MX c0,MX R,MX C,MX dstr,MX LU){
MV(MX r0=0;r0<R;r0+=TS){
MU IX=(MU)r0*C+c0;
MU IL=(MU)(r0+TS-1)*C+c0+TS-1;
if(IL<KW){FP(MO,S,r0,c0,C,dstr,LU,0);IA;}
if(IX>=KW){FP(MO,S,r0,c0,C,dstr,LU,1);IA;}
AH AB c4=AF(4),c4p=AF((MX)(P-4));
MV(MX rb=0;rb<TS;rb+=8){
MV(MX cb0=0;cb0<TS;cb0+=8){
AB r[8];
MV(MX k=0;k<8;k++){
MU idx=(MU)(r0+rb+k)*C+c0+cb0;
if(idx+8<=(MU)KW){
AB x=DU(MO,idx);
FY[k&3]=AA(FY[k&3],x);
if(LU)x=AD(AC(x,c4),AA(x,c4p));
if(CM){AH AB pp=AF(P),zz=BB();x=AC(x,AF((MX)0x80000000u));x=AA(x,BP(CN(zz,x),pp));x=AA(x,BP(CN(zz,x),pp));}x=AD(x,AC(x,AF(P)));x=AD(x,AC(x,AF(P)));r[k]=x;
}zc if(idx>=(MU)KW){
r[k]=BB();
}zc{
MW tmp[8];
MV(MX q=0;q<8;q++){
MU id=idx+q;MW v=0;
if(id<(MU)KW){v=FT(MO,id);if(CM){DS z=DS(v)-2147483648ll;z%=P;if(z<0)z+=P;v=AX(z);}zc{if(v>=P)v-=P;if(v>=P)v-=P;}g_psums+=v;if(LU)v=(v>=4u)?(v-4u):(v+(P-4u));}
tmp[q]=v;
}
r[k]=AQ((AH KK*)tmp);
}
}
KT(r);
AH MW*db=S+(MU)r0+rb;
MV(MX j=0;j<8;j++)BH((KK*)(db+(KI)(cb0+j)*dstr),r[j]);
}
}
}
}
AK KK copy_u32_avx(MW*LT,AH MW*MO,KI n){
KI i=0;
MV(;i+8<=n;i+=8)BH((KK*)(LT+i),AQ((AH KK*)(MO+i)));
MV(;i<n;i++)LT[i]=MO[i];
}
AK KK copy_u32_nt(MW*LT,AH MW*MO,KI n){
KI i=0;
KI ka=((-(KI)(((GA)LT)>>2))&15);
MV(;i<ka&&i<n;i++)LT[i]=MO[i];
MV(;i+16<=n;i+=16)NTC(LT+i,MO+i);
MV(;i+8<=n;i+=8){
AB v=AQ((AH KK*)(MO+i));
BU((AB*)(LT+i),v);
}
MV(;i<n;i++)LT[i]=MO[i];
FF();
}
AK KK untr_tile_avx(AH MW*in,MW*out,MX A0,MX B0,MX IS,MX GK){
MV(MX u0=0;u0<TS;u0+=8){
MV(MX v0=0;v0<TS;v0+=16){
AB r[8];
MV(MX k=0;k<8;k++)
r[k]=AQ((AH KK*)(KJ((KI)(A0+u0+k)*IS+B0+v0)));
KT(r);
MV(MX k=0;k<8;k++)
BH((KK*)(KM+(v0+k)*TS+u0),r[k]);
{
MX v0b=v0+8;
AB r2[8];
MV(MX k=0;k<8;k++)
r2[k]=AQ((AH KK*)(KJ((KI)(A0+u0+k)*IS+B0+v0b)));
KT(r2);
MV(MX k=0;k<8;k++)
BH((KK*)(KM+(v0b+k)*TS+u0),r2[k]);
}
}
}
MV(MX v=0;v<TS;v++){
MW*d=out+(MU)(B0+v)*GK+A0;
AH MW*s=KM+v*TS;
MV(MX u=0;u<TS;u+=16)NTC(d+u,s+u);
}
}
AK KK EW(MW*tw,MW*MR,MX L,MW w){
MX LZ=0;
MV(MX MQ=2;MQ<=L;MQ<<=1){
MW wl=pw(w,(MW)(L/MQ));
MW c=1;
MX h=MQ>>1;
MV(MX j=0;j<h;j++){tw[LZ+j]=c;MR[LZ+j]=EV(c);c=mm(c,wl);}
LZ+=h;
}
}
#pragma GCC pop_options
#endif
AK MW R5F[5],R5FS[5];
AK MW R5I[5],R5IS[5];
AK MW T5F_[4][zm+16],T5FS_[4][zm+16];
AK MW T5I[4*zm],T5IS[4*zm];
AK MW tsubFw[zm+8],tsubFsw[zm+8],tsubIw[zm+8],tsubIsw[zm+8];
AK MW KX[4][zm+64]AZ((GP(64)));
AK MW TT5I[4*zm+128]AZ((GP(64))),TT5IS[4*zm+128]AZ((GP(64)));
AK MW RTF[NR_+64]AZ((GP(64))),RTI[NR_+64]AZ((GP(64))),RWS[2*NR_+64]AZ((GP(64)));
AK KK build_radix5(MW KY){
AH MW H2=(P+1u)/2u;
MW w5=pw(KY,(MW)(NC_/5)),w52=mm(w5,w5),w53=mm(w52,w5),w54=mm(w53,w5);
MW h14=mm((MW)(((MU)w5+w54)%P),H2),g14=mm((MW)((w5+P-w54)%P),H2);
MW h23=mm((MW)(((MU)w52+w53)%P),H2),g23=mm((MW)((w52+P-w53)%P),H2);
MW iv=mm(H2,H2);
R5F[0]=iv;R5F[1]=(MW)(((MU)h14+iv)%P);R5F[2]=g23;
R5F[3]=(MW)((g14+P-g23)%P);R5F[4]=(MW)(((MU)g14+g23)%P);
R5I[0]=iv;R5I[1]=R5F[1];R5I[2]=(g23?P-g23:0);
R5I[3]=(MW)(((MU)g23+P-g14)%P);R5I[4]=(MW)((P-R5F[4])%P);
MV(MX i=0;i<5;i++){R5FS[i]=EV(R5F[i]);R5IS[i]=EV(R5I[i]);}
MV(MX s=1;s<5;s++){
MW g=pw(KY,(MW)s),gi=pw(g,P-2u),c=1,ci=1;
MW*pf=T5F_[s-1],*pf2=T5FS_[s-1];
MW*pi=T5I+(s-1)*zm,*pi2=T5IS+(s-1)*zm;
MV(MX j=0;j<(MX)zm;j++){pf[j]=c;pf2[j]=EV(c);c=mm(c,g);pi[j]=ci;pi2[j]=EV(ci);ci=mm(ci,gi);}
}
EW(tsubFw,tsubFsw,(MX)zm,pw(KY,5));
EW(tsubIw,tsubIsw,(MX)zm,pw(pw(KY,5),P-2u));
}
#pragma GCC push_options
#pragma GCC target("avx2,tune=skylake")
AK BR AZ((BK))AB zn(AB a,AB b,AB Pv){
AB s=AA(a,b);
BD AD(s,AC(s,Pv));
}
AK BR AZ((BK))AB zr(AB a,AB b,AB Pv){
AB d=AC(a,b);
BD AD(d,AA(d,Pv));
}
AK BR AZ((BK))KK dft5(AB*v,AH AB*c,AH AB*cs,AB Pv){
AB s1=zn(v[1],v[4],Pv),s2=zn(v[2],v[3],Pv);
AB d1=zr(v[1],v[4],Pv),d2=zr(v[2],v[3],Pv);
AB HL=zr(v[0],EJ(zn(s1,s2,Pv),c[0],cs[0]),Pv);
AB HM=EJ(zr(s1,s2,Pv),c[1],cs[1]);
AB LO=EJ(zn(d1,d2,Pv),c[2],cs[2]);
AB t1=zn(HL,HM,Pv),t2=zr(HL,HM,Pv);
AB u1=zn(LO,EJ(d1,c[3],cs[3]),Pv);
AB u2=zr(LO,EJ(d2,c[4],cs[4]),Pv);
AB X0=zn(v[0],zn(s1,s2,Pv),Pv);
v[0]=X0;v[1]=zn(t1,u1,Pv);v[2]=zn(t2,u2,Pv);
v[3]=zr(t2,u2,Pv);v[4]=zr(t1,u1,Pv);
}
AK KK col_dif5_head(MW*x){
AH AB Pv=AF((MX)P);
AB c[5],cs[5];
MV(MX i=0;i<5;i++){c[i]=AF((MX)R5F[i]);cs[i]=AF((MX)R5FS[i]);}
MV(MX j=0;j<(MX)zm;j+=8){
AB v[5];
MV(MX i=0;i<5;i++)v[i]=AQ((AH KK*)(x+(MU)i*zm+j));
dft5(v,c,cs,Pv);
BH((KK*)(x+j),v[0]);
MV(MX s=1;s<5;s++){
AB w=AQ((AH KK*)(T5F_[s-1]+j));
AB ws=AQ((AH KK*)(T5FS_[s-1]+j));
BH((KK*)(x+(MU)s*zm+j),DQ(v[s],w,ws));
}
}
}
#define N05Q_TAILROW(J) do { \
AB v[5],w,ws; \
v[0] = AQ((AH KK *)(x + (J))); \
MV (MX s = 1; s < 5; s++) { \
w = AQ((AH KK *)(TT5I + 16 + (s - 1) * M3_ + (J))); \
ws = AQ((AH KK *)(TT5IS + 16 + (s - 1) * M3_ + (J))); \
v[s] = DQ(AQ((AH KK *)(x + (MU)s * M3_ + (J))), w, ws); \
} \
dft5(v, c, cs, Pv); \
MV (MX i = 0; i < 5; i++) BH((KK *)(x + (MU)i * M3_ + (J)), v[i]); \
} JX (0)
AK KK col_dit5_tail(MW*x){
AH AB Pv=AF((MX)P);
AB c[5],cs[5];
MV(MX i=0;i<5;i++){c[i]=AF((MX)R5I[i]);cs[i]=AF((MX)R5IS[i]);}
MV(MX j=0;j<(MX)zm;j+=16){
N05Q_TAILROW(j);
N05Q_TAILROW(j+8);
}
}
AK KK col_dit5(MW*x){
MV(MX s=0;s<5;s++)FK(x+(MU)s*zm,(MX)zm,KX[2]+16,KX[3]+16);
GQ(x);
}
AK BR AZ((BK))KK FM(AH MW*t[],MW*d[],MX Ab,AH AB*hc,AH AB*hcs){
AH AB Pvh=AF((MX)P);
KO hf=[&](MX u,AB*o){
AB vv[5];
MV(MX i=0;i<5;i++)vv[i]=AQ((AH KK*)(t[i]+u));
dft5(vv,hc,hcs,Pvh);
o[0]=vv[0];
MV(MX s=1;s<5;s++)
o[s]=DQ(vv[s],AQ((AH KK*)(T5F_[s-1]+Ab+u)),AQ((AH KK*)(T5FS_[s-1]+Ab+u)));
};
MV(MX u=0;u<TS;u+=16){
AB p[5],q[5];hf(u,p);hf(u+8,q);
if((((GA)d[0]|(GA)d[1]|(GA)d[2]|(GA)d[3]|(GA)d[4])&63u)==0u){
MV(MX s=0;s<5;s++)NT2(d[s]+u,p[s],q[s]);
}zc{
MV(MX s=0;s<5;s++){BH(d[s]+u,p[s]);BH(d[s]+u+8,q[s]);}
}
}
}
AK KK FV(AH MW*tile,MW*X,MX B0,MX Ab,MX FZ){
AH MX AM=NC_/5,GK=CSX_;
AB hc[5],hcs[5];
MV(MX i=0;i<5;++i){hc[i]=AF((MX)R5F[i]);hcs[i]=AF((MX)R5FS[i]);}
MV(MX v=0;v<TS;v++){
AH MW*t[5];MV(MX p=0;p<5;p++)t[p]=tile+p*(TS*TS+32)+v*TS;
AH MU HP=(MU)(B0+v)*GK+Ab;
MW*d[5];MV(MX p=0;p<5;p++)d[p]=FZ?KJ((KI)(HP+p*(KI)AM)):X+HP+p*AM;
FM(t,d,Ab,hc,hcs);
}
}
AK KK col_convolve5(MW*a,MW*b){
MV(MX arm=0;arm<5;++arm){
MW*pa=a+(MU)arm*zm,*pb=b+(MU)arm*zm;
DV<ED,KR>(pa,(MX)zm,KX[0]+16,KX[1]+16);
DV(pb,(MX)zm,KX[0]+16,KX[1]+16);
if(arm==0)FK<KR>(pa,(MX)zm,KX[2]+16,KX[3]+16,pb);
zc FK<KR,KR>(pa,(MX)zm,KX[2]+16,KX[3]+16,pb);
}
GQ(a);
}
#pragma GCC pop_options
AK KK row_dit(MW*x,MX L,AH MW*tw,AH MW*MR){
#if HAVE_AVX2
FK(x,L,tw,MR);
BD;
#else
(KK)MR;
#endif
MX LZ=0;
MV(MX MQ=2;MQ<=L;MQ<<=1){
MX h=MQ>>1;
AH MW*t=tw+LZ;LZ+=h;
MV(MX i=0;i<L;i+=MQ){
MW*p=x+i,*q=x+i+h;
MV(MX j=0;j<h;j++){
MW u=p[j],v=mm(q[j],t[j]);
MW s=u+v;if(s>=P)s-=P;
MW d=u+P-v;if(d>=P)d-=P;
p[j]=s;q[j]=d;
}
}
}
}
AK KK pointwise(MW*A,AH MW*B,MW n,MW sc,MW sx){
#if HAVE_AVX2
pointwise_mul_avx(A,B,n,sc,sx);
BD;
#else
MV(KI i=0;i<(KI)n;i++){KI o=(i/(KI)(sx-PADC_))*sx+(i%(KI)(sx-PADC_));A[o]=mm(mm(A[o],B[o]),sc);}
#endif
}
AK KK row_dif(MW*x,MX L,AH MW*tw,AH MW*MR){
#if HAVE_AVX2
DV(x,L,tw,MR);
BD;
#else
(KK)MR;
#endif
MV(MX MQ=L;MQ>=2;MQ>>=1){
MX h=MQ>>1;
AH MW*t=tw+h-1;
MV(MX i=0;i<L;i+=MQ){
MW*p=x+i,*q=x+i+h;
MV(MX j=0;j<h;j++){
MW u=p[j],v=q[j];
MW s=u+v;if(s>=P)s-=P;
MW d=u+P-v;if(d>=P)d-=P;
p[j]=s;q[j]=mm(d,t[j]);
}
}
}
}
AK BR KK bitrev_pass(MW*x,MX L,AH u16*br){
MV(MX i=0;i<L;i++){
MX k=br[i];
if(i<k){MW t=x[i];x[i]=x[k];x[k]=t;}
}
}
JS Eng{
MX R,C,N,sx;
MX blkr;
MX r5;
MW w;
MW*tfR;MW*tiR;MW*tfC;MW*tiC;
MW*wsR;MW*wsC;
u16*brR;u16*brC;
};
AK KK col_dif5_arms(MW*x){
MV(MX s=0;s<5;s++)DV(x+(MU)s*zm,(MX)zm,KX[0]+16,KX[1]+16);
}
AK KK colfwd(Eng&e,MW*row){
#if HAVE_AVX2
if(e.r5){col_dif5_arms(row);BD;}
#endif
row_dif(row,e.C,e.tfC,e.wsC);
}
AK KK colinv(Eng&e,MW*row){
#if HAVE_AVX2
if(e.r5){col_dit5(row);BD;}
#endif
row_dit(row,e.C,e.tiC,e.wsC+e.C);
}
AK KK load_T(Eng&e,AH MW*MO,MW KW,MW*S,MX LU){
AH MX R=e.R,C=e.C;
#if HAVE_AVX2
if(KW<=(MW)R*(MW)C){
MV(MX r0=0;r0<R;r0+=TS){
MU tilerow=(MU)r0*C;
MV(MX c0=0;c0<C;c0+=TS){
MU IX=tilerow+c0;
MU IL=(MU)(r0+TS-1)*C+c0+TS-1;
if(IL<KW){GO(MO,S,r0,c0,R,C,LU,0);IA;}
if(IX>=KW){GO(MO,S,r0,c0,R,C,LU,1);IA;}
MV(MX rb=0;rb<TS;rb++){
MU KZ=(MU)(r0+rb)*C+c0;
MV(MX cb=0;cb<TS;cb++){
MU id=KZ+cb;
MW v=0;
if(id<KW){v=FT(MO,id);if(CM){DS z=DS(v)-2147483648ll;z%=P;if(z<0)z+=P;v=AX(z);}zc{if(v>=P)v-=P;if(v>=P)v-=P;}if(LU)v=(v>=4u)?(v-4u):(v+(P-4u));}
KM[cb*TS+rb]=v;
}
}
MV(MX cb=0;cb<TS;cb++){
MW*d=S+(MU)(c0+cb)*R+r0;
AH MW*s=KM+cb*TS;
MV(MX rb=0;rb<TS;rb++)d[rb]=s[rb];
}
}
}
BD;
}
#endif
MV(MX r0=0;r0<R;r0+=TS){
MV(MX c0=0;c0<C;c0+=TS){
MU IL=(MU)(r0+TS-1)*C+(c0+TS-1);
if(IL<KW){
MV(MX rb=0;rb<TS;rb++){
AH MW*s=MO+(MU)(r0+rb)*C+c0;
MV(MX cb=0;cb<TS;cb++){
MW v=s[cb];
if(LU)v=(v>=4u)?(v-4u):(v+(P-4u));
KM[cb*TS+rb]=v;
}
}
}zc{
MV(MX rb=0;rb<TS;rb++){
MU KZ=(MU)(r0+rb)*C+c0;
MV(MX cb=0;cb<TS;cb++){
MU id=KZ+cb;
MW v=0;
if(id<KW){v=FT(MO,id);if(CM){DS z=DS(v)-2147483648ll;z%=P;if(z<0)z+=P;v=AX(z);}zc{if(v>=P)v-=P;if(v>=P)v-=P;}if(LU)v=(v>=4u)?(v-4u):(v+(P-4u));}
KM[cb*TS+rb]=v;
}
}
}
MV(MX cb=0;cb<TS;cb++){
MW*d=S+(MU)(c0+cb)*R+r0;
AH MW*s=KM+cb*TS;
MV(MX rb=0;rb<TS;rb++)d[rb]=s[rb];
}
}
}
}
AK MW REV6[TS];
AK MW GL=1u;
AK MW POWT[1024],POWT64[1024];
AK KK build_rev6(KK){
MV(MX i=0;i<TS;i++){
MX r=0;
MV(MX b=0;b<6;b++)if(i&(1<<b))r|=1<<(5-b);
REV6[i]=(MW)r;
}
}
AK BR MW IN(MW x,MX lg){
MW r=0;
MV(MX b=0;b<lg;b++)if(x&(1u<<b))r|=1u<<(lg-1-b);
BD r;
}
BG<MX perm>
AK KK GB(AH MW*in,MW*out,MX nA,MX nB,MX IS,MX GK,MW KY,MX FZ){
MW wv[TS];
{MW c=1;MV(MX v=0;v<TS;v++){wv[v]=c;c=mm(c,KY);}}
AH MW w64=pw(KY,TS);
MX lgB=0,lgA=0;
JX((1<<lgB)<nB)lgB++;
JX((1<<lgA)<nA)lgA++;
AH MX S1=nB/TS,S2=nA/TS;
AH MX HB=lgB-6,HA=lgA-6;
MW RV2[TS],RV2b[TS],PW2[TS],cu[TS],cu64[TS],KZ[TS];
MW GZ[TS],cu64_shoup[TS];
if(perm==1){
MW g=pw(KY,(MW)S1);
{MW gM=mm(g,MA),c=MA;MV(MX t=0;t<TS;t++){RV2[REV6[t]]=c;c=HN(c,gM);}}
{MW rootM=mm(KY,MA),p=MA;MV(MX t=0;t<S1;t++){POWT[t]=p;p=HN(p,rootM);}}
}zc if(perm==2){
MW g=pw(KY,(MW)S2),g64=pw(g,64);
AH MW rootM2=mm(KY,MA),gM=mm(g,MA),g64M=mm(g64,MA);
{MW c=MA,c64=MA;
MV(MX t=0;t<TS;t++){RV2[REV6[t]]=c;RV2b[REV6[t]]=c64;c=HN(c,gM);c64=HN(c64,g64M);}}
{MW p=MA;MV(MX t=0;t<S2;t++){POWT[t]=p;p=HN(p,rootM2);}}
{MW q=pw(KY,64),qM=mm(q,MA),p=MA;MV(MX t=0;t<S2;t++){POWT64[t]=p;p=HN(p,qM);}}
}
MW wr=1;
AH MW INVSCALE=GL;
MV(MX A0=0;A0<nA;A0+=TS){
MW wr64=pw(wr,TS);
if(perm==1){
MW g=pw(wr,(MW)S1),gM2=mm(g,MA),c=MA;
MV(MX t=0;t<TS;t++){PW2[REV6[t]]=c;c=HN(c,gM2);}
}zc if(perm==2){
MX hi=A0/TS;
MW rH=POWT[IN((MW)hi,HA)],r64H=POWT64[IN((MW)hi,HA)];
AH MW INVSCALE_M=mm(INVSCALE,MA);
MV(MX u=0;u<TS;u++){
cu[u]=HN(RV2[u],rH);cu64[u]=HN(RV2b[u],r64H);KZ[u]=INVSCALE_M;
GZ[u]=HN(cu64[u],1u);cu64_shoup[u]=EV(GZ[u]);
}
}zc{
MW c=1;MV(MX v=0;v<TS;v++){PW2[v]=c;c=mm(c,wr);}
}
MW Vloc=1;
MW Vr=1;
MV(MX B0=0;B0<nB;B0+=TS){
if(perm==1){
MW H=IN((MW)(B0/TS),HB);
MW wrH=pw(wr,H),rootH=POWT[H];
MW RV[TS];
#if HAVE_AVX2
EF(RV,RV2,rootH);
EF(TW,PW2,mm(wrH,MA));
twiddle_rows_mont(TW,RV);
#else
MV(MX v=0;v<TS;v++)RV[v]=HN(RV2[v],rootH);
MV(MX v=0;v<TS;v++)TW[v]=HN(PW2[v],mm(wrH,MA));
MV(MX u=1;u<TS;u++){
AH MW*prv=TW+(u-1)*TS;
MW*LR=TW+u*TS;
MV(MX v=0;v<TS;v++)LR[v]=HN(prv[v],RV[v]);
}
#endif
}zc if(perm==2){
if(B0==0){
MV(MX u=0;u<TS;u++){
MW*LR=TW+u*TS;
LR[0]=KZ[u];
MV(MX v=1;v<TS;v++)LR[v]=HN(LR[v-1],cu[u]);
}
}zc{
MV(MX u=0;u<TS;u++){
MW*LR=TW+u*TS;
#if HAVE_AVX2
scale_row_prepared(LR,LR,GZ[u],cu64_shoup[u]);
#else
MW d=cu64[u];
MV(MX v=0;v<TS;v++)LR[v]=HN(LR[v],d);
#endif
}
}
}zc{
MW RV[TS];
MV(MX v=0;v<TS;v++)RV[v]=mm(Vloc,wv[v]);
MV(MX v=0;v<TS;v++)TW[v]=mm(Vr,PW2[v]);
MV(MX u=1;u<TS;u++){
AH MW*prv=TW+(u-1)*TS;
MW*LR=TW+u*TS;
MV(MX v=0;v<TS;v++)LR[v]=mm(prv[v],RV[v]);
}
}
#if HAVE_AVX2
corner_tile_avx(in,out,A0,B0,IS,GK,FZ);
#else
MV(MX u=0;u<TS;u++){
AH MW*s=in+(MU)(A0+u)*IS+B0;
AH MW*tw=TW+u*TS;
MV(MX v=0;v<TS;v++)KM[u*TS+v]=HN(s[v],tw[v]);
}
MV(MX v=0;v<TS;v++){
MW*d=out+(MU)(B0+v)*GK+A0;
MV(MX u=0;u<TS;u++)d[u]=KM[u*TS+v];
}
#endif
Vr=mm(Vr,wr64);
Vloc=mm(Vloc,w64);
}
wr=mm(wr,w64);
}
}
AK BR KK corner_fwd(Eng&e,AH MW*S,MW*X,MW KY){
GB<1>(S,X,e.C,e.R,e.R,e.sx,KY,0);
}
AK BR KK corner_inv(Eng&e,AH MW*X,MW*S,MW KY){
GB<2>(X,S,e.R,e.C,e.sx,e.R,KY,1);
}
AK KK untranspose(Eng&e,AH MW*S,MW*LT){
AH MX R=e.R,C=e.C;
#if HAVE_AVX2
MV(MX c0=0;c0<C;c0+=TS)
MV(MX r0=0;r0<R;r0+=TS)
untr_tile_avx(S,LT,c0,r0,R,e.sx);
BD;
#endif
MV(MX c0=0;c0<C;c0+=TS){
MV(MX r0=0;r0<R;r0+=TS){
MV(MX u=0;u<TS;u++){
AH MW*s=S+(MU)(c0+u)*R+r0;
MW*d=KM+u*TS;
MV(MX v=0;v<TS;v++)d[v]=s[v];
}
MV(MX v=0;v<TS;v++){
MW*d=LT+(MU)(r0+v)*e.sx+c0;
MV(MX u=0;u<TS;u++)d[u]=KM[u*TS+v];
}
}
}
}
#define N02I_SB (TS * (NRMAX_ + PADB_))
AK MW SBLK[5*N02I_SB]AZ((GP(64)));
AK MW TILE5[5][TS*TS+32]AZ((GP(64)));
#pragma GCC push_options
#pragma GCC target("avx2,tune=skylake")
AK MW GRV2[TS],GPOWT[NR_/TS];
AK MW GRV[TS][TS];
AK AB GSF[TS][TS/8],GSS[TS][TS/8];
AK MW GWRHM[256][5][NR_/TS],GPW2[256][5][TS];
AK MX HQ=0;AK MW HR=0;
AK KK fwd_prep1(MW KY){
if(HQ&&HR==KY)BD;
HQ=1;HR=KY;
AH MX S1=NR_/TS;
{MW g=pw(KY,(MW)S1),gM=mm(g,MA),c=MA;
MV(MX t=0;t<TS;t++){GRV2[REV6[t]]=c;c=HN(c,gM);}}
{MW rootM=mm(KY,MA),p=MA;
MV(MX t=0;t<S1;t++){GPOWT[t]=p;p=HN(p,rootM);}}
MV(MX H=0;H<S1;++H){EF(GRV[H],GRV2,GPOWT[H]);ET(GRV[H],GSF[H],GSS[H]);}
AH MX AM=NC_/5;
MV(MX Ai=0,Ab=0;Ab<AM;Ab+=TS,++Ai){
MV(MX p=0;p<5;p++){
AH MX A0=Ab+p*AM;AH MW wr=pw(KY,(MW)A0);
{AH MW wrM=mm(wr,MA);MW val=MA;MV(MX h=0;h<S1;++h){GWRHM[Ai][p][h]=val;val=HN(val,wrM);}}
{MW g=pw(wr,(MW)S1),gM2=mm(g,MA),c=MA;MV(MX t=0;t<TS;t++){GPW2[Ai][p][REV6[t]]=c;c=HN(c,gM2);}}
}
}
}
#pragma GCC pop_options
AK KK corner_fwd_stream(Eng&e,AH MW*MO,MW KW,MW*X,MX FZ,MX LU){
AH MX nA=(MX)NC_,nB=(MX)NR_,IS=(MX)(NR_+PADB_),GK=(MX)CSX_;
AH MW KY=e.w;
MX lgB=0;JX((1<<lgB)<nB)lgB++;
AH MX S1=nB/TS,HB=lgB-6;
fwd_prep1(KY);
AH KL halfzero=(nB==4096&&(MU)KW<=(MU)(nB/2)*nA);
AH MX AM=nA/5;
MV(MX Ab=0;Ab<AM;Ab+=TS){
AH MX Ai=Ab/TS;
MV(MX p=0;p<5;p++){
MW*S=SBLK+(MU)p*N02I_SB;
AH MX A0=Ab+p*AM;
load_block(MO,KW,S,A0,halfzero?nB/2:nB,nA,IS,LU);
MV(MX u=0;u<TS;++u){
if(halfzero)DV<KR,KR>(S+(MU)u*IS,nB,e.tfR,e.wsR);
zc row_dif(S+(MU)u*IS,nB,e.tfR,e.wsR);
}
}
MV(MX B0=0;B0<nB;B0+=TS){
MW H=IN((MW)(B0/TS),HB);
AH AB*EN=GSF[H];AH AB*FU=GSS[H];
MV(MX p=0;p<5;p++){
EF(TW,GPW2[Ai][p],GWRHM[Ai][p][H]);
FL(TW,EN,FU);
corner_tile_avx_to(SBLK+(MU)p*N02I_SB,TILE5[p],B0,IS);
}
FV(TILE5[0],X,B0,Ab,FZ);
}
}
}
AK KK fwd(Eng&e,AH MW*MO,MW KW,MW*S,MW*X,MX FZ,MX LU){
#ifdef OLD_FWD
load_T(e,MO,KW,S,LU);
MV(MX j0=0;j0<e.C;j0++){
MW*row=S+(MU)j0*e.R;
row_dif(row,e.R,e.tfR,e.wsR);
}
corner_fwd(e,S,X,e.w);
#else
(KK)S;
{corner_fwd_stream(e,MO,KW,X,FZ,LU);}
#endif
if(!JK){MV(MX k0=0;k0<e.R;k0++)
colfwd(e,FZ?KJ((KI)k0*e.sx):X+(MU)k0*e.sx);}
}
AK KK LV(Eng&e,MW*X,MW*S){MV(MX k0=0;k0<e.R;k0++)colinv(e,X+(MU)k0*e.sx);
corner_inv(e,X,S,pw(e.w,P-2u));
MV(MX j0=0;j0<e.C;j0++){
MW*row=KJ((KI)j0*e.R);
row_dit(row,e.R,e.tiR,e.wsR+e.R);
}
}
AK MW INV_TW[NRMAX_*TS]AZ((GP(64)));
AK MW IY[NRMAX_],GC[NRMAX_];
#pragma GCC push_options
#pragma GCC target("avx2,tune=skylake")
BG<KL Advance>
AK BR AZ((BK))KK EZ(Eng&e,MW*X,MX r0,MX c0){
(KK)e;
AH KI SXF_=(KI)CSX_,BLF_=(KI)(NR_+PADB_);
MV(MX u0=0;u0<TS;u0+=8){
MV(MX v0=0;v0<TS;v0+=8){
{AH MW*pf=X+(MU)(r0+u0+8)*SXF_+c0+v0;
MV(MX k=0;k<8;k++)AP((AH KV*)(pf+(MU)k*SXF_),AW);}
AB LA[8];
{
AH MW*sbase=X+(MU)(r0+u0)*SXF_+c0+v0;
MW*tbase=INV_TW+(r0+u0)*(KI)TS+v0;
MW*sblkbase=SBLK+(MU)v0*BLF_+r0+u0;
MV(MX k=0;k<8;++k){
AH MW*MO=sbase+(MU)k*SXF_;
MW*tw=tbase+(KI)k*TS;
AB w=AQ(tw);
if AL(Advance){
AH MX j=r0+u0+k;
BH(tw,EJ(w,AF((MX)IY[j]),
AF((MX)GC[j])));
}
LA[k]=KG(AQ(MO),w);
}
KT(LA);
MV(MX k=0;k<8;++k)
BH(sblkbase+(MU)k*BLF_,LA[k]);
}
}
}
}
AK KK inv_natural_stream(Eng&e,MW*X){
if(!JK)
MV(MX k=0;k<e.R;++k)colinv(e,X+(MU)k*e.sx);
AH MW KY=pw(e.w,P-2u);
AH MW seed=mm(mm(GL,MA),MA);
MX lg=0;JX((1<<lg)<e.R)++lg;
MV(MX k=0;k<e.R;++k){
AH MW DG=pw(KY,IN(k,lg));
AH MW factorM=mm(DG,MA);
IY[k]=pw(DG,TS);
GC[k]=EV(IY[k]);
MW*tw=INV_TW+k*TS;
MW f8=factorM;MV(MX q=0;q<3;++q)f8=HN(f8,f8);MW b0=seed;MV(MX r=0;r<8;++r){MW b=b0;MV(MX m=0;m<8;++m){tw[m*8+r]=b;b=HN(b,f8);}b0=HN(b0,factorM);}
}
MV(MX c0=0;c0<e.C;c0+=TS){
MV(MX r0=0;r0<e.R;r0+=TS){
EZ<KR>(e,X,r0,c0);
}
MV(MX v=0;v<TS;++v)
FK<ED,ED,KR>(SBLK+(MU)v*e.blkr,e.R,e.tiR,e.wsR+e.R);
{
AH KI SXF_=(KI)CSX_,BLF_=(KI)(NR_+PADB_);
MV(MX r0=0;r0<(MX)1960;r0+=TS){
MV(MX v0=0;v0<TS&&r0+v0<1954;v0+=8){
{
AH MW*sbase=SBLK+(MU)(r0+v0);
MW*dbase=X+(MU)(r0+v0)*SXF_+c0;
MV(MX u0=0;u0<TS;u0+=16){
AH MW*sp=sbase+(MU)u0*BLF_;
AB LA[8];
MV(MX k=0;k<8;++k)
LA[k]=AQ(sp+(MU)k*BLF_);
KT(LA);
MV(MX k=0;k<8;++k)BH(KM+k*8,LA[k]);
MV(MX k=0;k<8;++k)
LA[k]=AQ(sp+(MU)(8+k)*BLF_);
KT(LA);
MV(MX k=0;k<8;++k){
MW*LT=dbase+(MU)k*SXF_+u0;
BU((AB*)LT,AQ(KM+k*8));
BU((AB*)(LT+8),LA[k]);
}
}
}
}
}
}
}
FF();
}
AK KK fuse4_row_avx(MW*pa,AH MW*pb,MX n){
MX i=0;
MV(;i+8<=n;i+=8){
AB x=AQ((AH KK*)(pa+i));
AB y=AQ((AH KK*)(pb+i));
BH((KK*)(pa+i),DQ(x,y,GJ(y)));
}
MV(;i<n;i++)pa[i]=mm(pa[i],pb[i]);
}
#pragma GCC pop_options
AK KK eng_init(Eng&e,MX lgR,MX nC,MW w,MX sx,
MW*tfR,MW*tiR,MW*tfC,MW*tiC,u16*brR,u16*brC,
MW*wsR,MW*wsC){
e.R=1<<lgR;e.C=nC;e.N=e.R*e.C;e.w=w;e.sx=sx;
e.blkr=e.R+PADB_;
e.r5=(nC==(MX)NC_);
e.tfR=tfR;e.tiR=tiR;e.tfC=tfC;e.tiC=tiC;e.brR=brR;e.brC=brC;
e.wsR=wsR;e.wsC=wsC;
MW wR=pw(w,(MW)e.C),wC=pw(w,(MW)e.R);
#if HAVE_AVX2
EW(tfR,e.wsR,e.R,wR);EW(tiR,e.wsR+e.R,e.R,pw(wR,P-2u));
if(!e.r5){EW(tfC,e.wsC,e.C,wC);EW(tiC,e.wsC+e.C,e.C,pw(wC,P-2u));}
#else
GX(tfR,e.R,wR);GX(tiR,e.R,pw(wR,P-2u));
GX(tfC,e.C,wC);GX(tiC,e.C,pw(wC,P-2u));
#endif
build_br(brR,e.R);
if(!e.r5)build_br(brC,e.C);
build_rev6();
}
#pragma GCC push_options
#pragma GCC target("avx2,tune=skylake")
AK BR AZ((BK))AB scan8(AB v,AB&JY){
v=AA(v,BY(v,4));
v=AA(v,BY(v,8));
AB t=AE(BB(),v,0x20);
t=AI(t,0xFF);
v=AA(v,t);
v=AA(v,JY);
JY=BE(v,AF(7));
BD v;
}
AK MW*Aarr;AK MW*AOUT;
#if (NR_ * CSX_) > BSTAIL_SPLIT
#define BTAILN_ ((MX)((NR_ * CSX_) - BSTAIL_SPLIT))
#else
#define BTAILN_ 1
#endif
AK MW*BTAIL;
AK AL AJ FW=4ull*(5ull<<22)+512;
AK Eng E1,E2;
AK MW t1fR[NR_],t1iR[NR_],t1fC[1],t1iC[1];
AK u16 b1R[NR_],b1C[1];
AK MW w1R[2*NR_],w1C[2];
AK MW t2fR[NR2_],t2iR[NR2_],t2fC[NC2_],t2iC[NC2_];
AK u16 b2R[NR2_],b2C[NC2_];
AK MW w2R[2*NR2_],w2C[2*NC2_];
AK MX inited=0;
AK KK GD(AH AX*a,AH AX*b,AX*c,AX*workspace,AX modulus,AX generator,KL borrow_C,KL balanced,KL reverse_first=ED){
DH=reverse_first;ES=a;Aarr=workspace;BTAIL=workspace+2*AJ(NR_)*CSX_;P=modulus;AOUT=(modulus==2013265921u?workspace:workspace+AJ(NR_)*CSX_);G=generator;MA=(1ull<<32)%P;IM=~0ull/(MU)P;SHMAGIC=MW(IM-(2ull<<32));CM=balanced;
{MU LV=1;MV(MX i=0;i<5;i++)LV=LV*(2-(MU)P*LV);NPI=(MW)(-(MU)LV);
MW w1=pw(G,(MW)((P-1)/N1_));eng_init(E1,LGR_,(MX)NC_,w1,(MX)CSX_,t1fR,t1iR,t1fC,t1iC,b1R,b1C,w1R,w1C);
GW(RTF+16,t1fR,(AJ)NR_*4);GW(RTI+16,t1iR,(AJ)NR_*4);GW(RWS+16,w1R,(AJ)(2*NR_)*4);E1 .tfR=RTF+16;E1 .tiR=RTI+16;E1 .wsR=RWS+16;E1 .r5=1;
build_radix5(pw(w1,(MW)E1 .R));GW(TT5I+16,T5I,(AJ)(4*zm)*4);GW(TT5IS+16,T5IS,(AJ)(4*zm)*4);GW(KX[0]+16,tsubFw,(AJ)zm*4);GW(KX[1]+16,tsubFsw,(AJ)zm*4);GW(KX[2]+16,tsubIw,(AJ)zm*4);GW(KX[3]+16,tsubIsw,(AJ)zm*4);}
g_B=borrow_C?c:BTAIL;g_BT=borrow_C?BTAIL:BTAIL+BSTAIL_SPLIT;GL=pw(N1_%P,P-2u);JK=1;psum_reset();fwd(E1,a,zl,c,AOUT,0,0);psum_reset();fwd(E1,b,zl,c,c,1,0);
MV(AX r=0;r<NR_;++r)col_convolve5(AOUT+(MU)r*CSX_,KJ((KI)r*CSX_));inv_natural_stream(E1,AOUT);JK=0;
FF();
}
AK BR AX fast_residue(AX k){BD Aarr[AOFF(k)];}
#pragma GCC pop_options
#undef TS
#pragma once
AL KO statement="Do NOT modify this statement! "
"https://github.com/With-Sky/HintFFT "
"TSKY (WithSky)";
#include <complex>
#include <iostream>
#include <type_traits>
#include <cstdint>
#include <climits>
#include <cstring>
#include <immintrin.h>
#define NI64 BC(LB::BV{})
#pragma GCC target("avx2,fma,tune=skylake")
#pragma GCC optimize("O3,tree-vectorize")
#pragma GCC optimize("align-functions=32")
#pragma GCC optimize("ira-loop-pressure")
#pragma GCC optimize("sched-pressure")
DM LB
{
BG<BQ T,AJ ALIGN=64>
KA FG{
IZ:
GE Ptr=T*;
GE ConstPtr=AH T*;
~FG(){
if(ptr){
_mm_free(ptr);}};
FG():ptr(DT),MQ(0){}
FG(AJ n):ptr(AN<Ptr>(_mm_malloc(n*JQ(T),ALIGN))),MQ(n){}
FG(AH FG&)=delete;
FG&DN=(AH FG&)=delete;
T&DN[](AJ i){
BD ptr[i];}
AH T&DN[](AJ i)AH{
BD ptr[i];}
Ptr EU(){
BD ptr;}
Ptr end(){
BD ptr+MQ;}
ConstPtr EU()AH{
BD ptr;}
ConstPtr end()AH{
BD ptr+MQ;}
AJ size()AH{
BD MQ;}
JN:
T*ptr;
AJ MQ;};
BG<BQ LS>
BR KK transpose64_2X4(LS&LC,LS&LD){
KO t0=DW(CD(LC),CD(LD));
KO t1=DX(CD(LC),CD(LD));
LC=LS(BL(t0,t1,0x20));
LD=LS(BL(t0,t1,0x31));}
BG<BQ LS>
BR KK transpose64_4X2(LS&LC,LS&LD){
KO t0=BL(CD(LC),CD(LD),0x20);
KO t1=BL(CD(LC),CD(LD),0x31);
LC=LS(DW(t0,t1));
LD=LS(DX(t0,t1));}
BG<BQ LS>
BR KK CB(LS&LC,LS&LD,LS&row2,LS&row3){
KO t0=DW(CD(LC),CD(LD));
KO t1=DX(CD(LC),CD(LD));
KO t2=DW(CD(row2),CD(row3));
KO t3=DX(CD(row2),CD(row3));
LC=LS(BL(t0,t2,0x20));
LD=LS(BL(t1,t3,0x20));
row2=LS(BL(t0,t2,0x31));
row3=LS(BL(t1,t3,0x31));}
JS BV{};
KA EG{
IZ:
GE MS=EC;
GE CQ=EG;
EG():LE(_mm256_setzero_pd()){}
EG(BV){}
EG(CD IO):LE(IO){}
EG(MS IO):LE(BS(IO)){}
EG(AH MS*IO):LE(_mm256_load_pd(IO)){}
CQ DN+(AH CQ&FX)AH{
BD DE(LE,FX.LE);}
CQ DN-(AH CQ&FX)AH{
BD EO(LE,FX.LE);}
CQ DN*(AH CQ&FX)AH{
BD CV(LE,FX.LE);}
CQ DN/(AH CQ&FX)AH{
BD _mm256_div_pd(LE,FX.LE);}
AK CQ fmadd(AH CQ&a,AH CQ&b,AH CQ&c){
BD _mm256_fmadd_pd(a.LE,b.LE,c.LE);}
AK CQ fmsub(AH CQ&a,AH CQ&b,AH CQ&c){
BD _mm256_fmsub_pd(a.LE,b.LE,c.LE);}
BG<MX N>
CQ permute4x64()AH{
BD _mm256_permute4x64_pd(LE,N);}
CQ HC()AH{
BD permute4x64<0b00011011>();}
KK LF(AH MS*p){
LE=_mm256_load_pd(p);}
KK JR(AH MS*p){
LE=_mm256_broadcast_sd(p);}
KK CO(MS*p)AH{
_mm256_store_pd(p,LE);}
KK DO(MS*p)AH{
_mm256_stream_pd(p,LE);}
DN CD()AH{
BD LE;}
AB toI64X4()AH{
AL DC mask=(DC(1)<<52)-1;
AL DC HO=(DC(1)<<10)-1;
AH AB f64bits=CI(LE);
AB tail=BP(f64bits,AG(mask));
tail=CS(tail,AG(mask+1));
AB exp=BX(f64bits,52);
exp=DJ(AG(HO+52),exp);
BD _mm256_srlv_epi64(tail,exp);}
JN:
CD LE;};
JS DF{
GE BC=DF;
GE CQ=EG;
GE MS=EC;
DF(){}
DF(BV):LG(BV{}),LH(BV{}){}
DF(CQ LG,CQ LH):LG(LG),LH(LH){}
DF(AH MS*p):LG(p),LH(p+4){}
DF(AH MS*p_real,AH MS*p_imag):LG(p_real),LH(p_imag){}
BC DN+(AH BC&FX)AH{
BD BC(LG+FX.LG,LH+FX.LH);}
BC DN-(AH BC&FX)AH{
BD BC(LG-FX.LG,LH-FX.LH);}
BC DN*(AH CQ&FX)AH{
BD BC(LG*FX,LH*FX);}
BC MT(AH BC&FX)AH{
AH CQ ii=LH*FX.LH;
AH CQ ri=LG*FX.LH;
AH CQ r=CQ::fmsub(LG,FX.LG,ii);
AH CQ i=CQ::fmadd(LH,FX.LG,ri);
BD BC(r,i);}
C64X4 uS()const{
const F64X4 twice=imag+imag;
return C64X4(F64X4(_mm256_fnmadd_pd(__m256d(imag),__m256d(twice),_mm256_set1_pd(1.))),real*twice);}
C64X4 uC(const C64X4&square)const{
const F64X4 twice=imag+imag;
return C64X4(F64X4(_mm256_fnmadd_pd(__m256d(twice),__m256d(square.imag),__m256d(real))),F64X4(_mm256_fmadd_pd(__m256d(twice),__m256d(square.real),__m256d(imag))));}
BC BT(AH BC&FX)AH{
AH CQ ii=LH*FX.LH;
AH CQ ri=LG*FX.LH;
AH CQ r=CQ::fmadd(LG,FX.LG,ii);
AH CQ i=CQ::fmsub(LH,FX.LG,ri);
BD BC(r,i);}
BC HC()AH{
BD BC(LG.HC(),LH.HC());}
KK set1(MS real_in,MS imag_in){
LG=CQ(real_in);
LH=CQ(imag_in);}
BG<BQ T>
KK LF(AH T*p,MP::HD){
this->LF(p);}
BG<BQ T>
KK LF(AH T*p,MP::BI){
this->LF(p);
*this=this->toRRIIPermu();}
BG<BQ T>
KK LF(AH T*p){
LG.LF(AN<AH MS*>(p));
LH.LF(AN<AH MS*>(p)+4);}
KK JR(AH MS*real_p,AH MS*imag_p){
LG.JR(real_p);
LH.JR(imag_p);}
BG<BQ T>
KK CO(T*p,MP::HD)AH{
this->CO(p);}
BG<BQ T>
KK CO(T*p,MP::BI)AH{
this->toRIRIPermu().CO(p);}
BG<BQ T>
KK CO(T*p)AH{
LG.CO(AN<MS*>(p));
LH.CO(AN<MS*>(p)+4);}
BG<BQ T>
KK DO(T*p)AH{
LG.DO(AN<MS*>(p));
LH.DO(AN<MS*>(p)+4);}
BC toRIRIPermu()AH{
BC res=*this;
transpose64_2X4(res.LG,res.LH);
BD res;}
BC toRRIIPermu()AH{
BC res=*this;
transpose64_4X2(res.LG,res.LH);
BD res;}
BC CE(MP::HD)AH{
BD*this;}
BC CE(MP::BI)AH{
AH CD KH=BS(6755399441055744.0);
AH AB KN=CI(KH);BD BC(DP(DJ(CI(DE(LG,KH)),KN)),DP(DJ(CI(DE(LH,KH)),KN)));}
CQ LG,LH;};
GE Float32=float;
GE BW=EC;
AL BW HINT_PI=3.141592653589793238462643;
AL BW HINT_2PI=HINT_PI*2;
AL BW COS_PI_8=0.707106781186547524400844;
BG<BQ T>
AL T int_floor2(T n){
AL MX KN=JQ(n)*8;
MV(MX i=1;i<KN;i*=2){
n|=(n>>i);}
BD(n>>1)+1;}
BG<BQ T>
AL T int_ceil2(T n){
AL MX KN=JQ(n)*8;
n--;
MV(MX i=1;i<KN;i*=2){
n|=(n>>i);}
BD n+1;}
BG<BQ IntTy>
AL KL is_2pow(IntTy n){
BD n!=0&&(n&(n-1))==0;}
BG<BQ T>
AL MX CW(T n){
AL MX KN=JQ(n)*8;
MX l=-1,r=KN;
JX((l+1)!=r){
MX mid=(l+r)/2;
if((T(1)<<mid)>n){
r=mid;}
zc{
l=mid;}}
BD l;}
AL CF crc32(AH KV*str){
CF crc=0xFFFFFFFF;
JX(*str!='\0'){
crc^=*str;
MV(MX i=0;i<8;++i){
crc=(crc>>1)^(0-(crc&1))&0xEDB88320;}
str++;}
BD~crc;}
DM IB{
BG<BQ T>
BR KK BO(T&sum,T&diff){
T temp0=sum,temp1=diff;
sum=temp0+temp1;
diff=temp0-temp1;}
DM fft{
GE MS=BW;
GE LX=MP::JM<MS>;
GE CQ=EG;
GE BC=DF;
BR LX DZ(AJ n,AJ IP){
IP%=n;
AH AJ q=(4*IP+n/2)/n;
AH DS d=DS(4*IP)-DS(q*n);
AL KI EC pi=3.141592653589793238462643383279502884L;
AH KI EC x=(EX<KI EC>(d)/EX<KI EC>(n))*(pi/2);
AH KI EC xx=x*x;
KI EC sn=x,cs=1,st=x,ct=1;
MV(AX k=1;k<=18;++k){
st*=(-xx)/EX<KI EC>((2*k)*(2*k+1));
ct*=(-xx)/EX<KI EC>((2*k-1)*(2*k));
sn+=st;cs+=ct;
}
KI EC re,im;
switch(q&3){case 0:re=cs;im=sn;break;case 1:re=-sn;im=cs;break;case 2:re=-cs;im=-sn;break;default:re=sn;im=-cs;break;}
BD LX(EX<EC>(re),-EX<EC>(im));
}
BG<BQ DR,AJ OMEGA_LEN>
KA JA{
GR(64)DR GF[OMEGA_LEN*2];
IZ:
JA(AJ theta_divider,AJ DG,AJ AU){
MV(AJ EU=0,IP=0;EU<OMEGA_LEN*2;EU+=AU*2)
MV(AJ j=0;j<AU;++j,++IP){LX z=DZ(theta_divider,IP*DG);GF[EU+j]=DR(z.LG());GF[EU+j+AU]=DR(z.LH());}
}
AL AH DR&DN[](AJ IP)AH{
BD GF[IP];}};
void HS(double*arr,size_t fft_len,int table_len,int factor){
const long double step=-6.2831853071795864769252867665590057683943387987502L*(long double)factor/(long double)fft_len;long double ds,dc,ds2,dc2;__builtin_sincosl(step,&ds,&dc);__builtin_sincosl(2*step,&ds2,&dc2);
for(int j=0;j<table_len;j+=128){long double s0,c0;__builtin_sincosl(step*j,&s0,&c0);long double c1=c0*dc-s0*ds,s1=s0*dc+c0*ds;int end=std::min(j+128,table_len);for(int k=j;k<end;k+=2){size_t p=size_t(k/4)*8+k%4;arr[p]=(double)c0;arr[p+4]=(double)s0;if(k+1<end){arr[p+1]=(double)c1;arr[p+5]=(double)s1;}long double n0=c0*dc2-s0*ds2,n1=c1*dc2-s1*ds2;s0=s0*dc2+c0*ds2;s1=s1*dc2+c1*ds2;c0=n0;c1=n1;}}}
BG<BQ DR,MX FA,MX LOG_END,MX DIV>
KA EP{
GS(LOG_END>=FA);
GS(is_2pow(DIV));
AK AL AJ TABLE_CPX_LEN=(AJ(1)<<(LOG_END+1))/DIV;
GR(64)DR GF[TABLE_CPX_LEN*2];
IZ:
EP(AJ DG,AJ AU=4){
initBottomUp(DG,AU);}
KK initBottomUp(AJ DG,AJ AU){
(KK)AU;GS(MP::is_same<DR,BW>::KD);
size_t top=size_t(1)<<LOG_END;HS(HT(LOG_END),top,top/DIV,DG);for(int log_len=FA;log_len<LOG_END;++log_len){size_t len=size_t(1)<<log_len,stride=top/len;int n=int(len/DIV);DR*dst=HT(log_len);const DR*src=HT(LOG_END);for(int j=0;j<n;++j){int p=(j>>2)*8+(j&3),q2=int(j*stride),p2=(q2>>2)*8+(q2&3);dst[p]=src[p2];dst[p+4]=src[p2+4];}}
}
AL AH DR*HT(MX JB)AH{
BD CT(AJ(1)<<JB);}
AL DR*HT(MX JB){
BD CT(AJ(1)<<JB);}
AL AH DR*CT(AJ LI)AH{
BD&GF[LI*2/DIV];}
AL DR*CT(AJ LI){
BD&GF[LI*2/DIV];}};
BG<MX EA>
KA BM{
IZ:
GE MS=EC;
GE LX=MP::JM<EC>;
GE BC=LB::DF;
AK AL AJ ID=AJ(1)<<EA;
AK AL AJ MASK=ID-1;
AK AL AJ C4_COUNT=JQ(BC)/JQ(LX);
~BM(){
if(high)
{
delete[]high;}}
BM(){}
BM(AJ CA,MX len_div,MX DG){
init(CA,len_div,DG);}
KK init(AJ CA,MX len_div,MX DG){
AJ IC=CA/len_div,low_len=ID*C4_COUNT,high_len=IC/low_len;
if(high!=DT)delete[]high;high=new LX[high_len];
HS(AN<MS*>(&low[0]),CA,low_len,DG);
MV(AJ i=0;i<high_len;++i)high[i]=DZ(CA,i*low_len*DG);
}
AK AL AJ LJ=EA,KE=MASK;
AH BC*JC()AH{BD low;}
AH LX*HE()AH{BD high;}
BC DN[](AJ i)AH{
BC hi(BV{});
KO p=AN<AH MS*>(&high[i>>EA]);
hi.JR(p,p+1);
BD low[i&MASK].MT(hi);}
JN:
GR(64)BC low[ID];
LX*high=DT;};
BG<MX DIV,MX FA,MX IQ,MX EA>
KA HF{
GE IE=BM<EA>;
AK AL AJ GG=AJ(1)<<FA;
AK AL AJ TABLE_LEN=IQ-FA+1;
IZ:
HF(MX DG){
MV(MX i=0;i<TABLE_LEN;i++)
{
AJ CA=GG<<i;
GF[i].init(CA,DIV,DG);}}
AH IE&DN[](MX FQ)AH{
FQ-=FA;
BD GF[FQ];}
IE&DN[](MX FQ){
FQ-=FA;
BD GF[FQ];}
JN:
IE GF[TABLE_LEN];};
JS FFT{
BG<BQ DR>
AK KK trans2MulI(DR&r0,DR&i0,DR&r1,DR&i1){
KO temp=r1;
r1=r0+i1;
r0=r0-i1;
i1=i0-temp;
i0=i0+temp;}
BG<BQ DR>
AK KK GT(DR&r0,DR&i0,DR&r1,DR&i1){
KO temp=r1;
r1=r0-i1;
r0=r0+i1;
i1=i0+temp;
i0=i0-temp;}
BG<BQ DR>
AK KK LK(DR&r0,DR&i0,DR&r1,DR&i1,DR&r2,DR&i2,DR&r3,DR&i3){
JD(r0,i0,r1,i1,r2,i2,r3,i3);
BO(r0,r1);
BO(i0,i1);}
BG<BQ DR>
AK KK KB(DR&r0,DR&i0,DR&r1,DR&i1,DR&r2,DR&i2,DR&r3,DR&i3){
BO(r0,r1);
BO(i0,i1);
IF(r0,i0,r1,i1,r2,i2,r3,i3);}
BG<BQ DR>
AK KK JD(DR&r0,DR&i0,DR&r1,DR&i1,DR&r2,DR&i2,DR&r3,DR&i3){
BO(r0,r2);
BO(i0,i2);
BO(r1,r3);
BO(i1,i3);
GT(r2,i2,r3,i3);}
BG<BQ DR>
AK KK IF(DR&r0,DR&i0,DR&r1,DR&i1,DR&r2,DR&i2,DR&r3,DR&i3){
BO(r2,r3);
BO(i2,i3);
BO(r0,r2);
BO(i0,i2);
trans2MulI(r1,i1,r3,i3);}};
DM CG{extern KL FC;KK run(MS*,AJ);}
AK KL GM=ED;
JS CJ:IZ FFT{
AK AL MX GH=11,JO=17,IQ=21,LOG_CACHE=8;
AK AL AJ GG=AJ(1)<<GH,MID_LEN=AJ(1)<<JO,MAX_LEN=AJ(1)<<IQ;
GE TableFix4=AH JA<BW,4>;
GE TableFix8=AH JA<BW,8>;
GE HU=AH EP<BW,GH+1,JO,4>;
GE HV=AH EP<BW,6,GH+1,4>;
GE HW=AH EP<BW,6,GH,4>;
GE TableSqrt=AH HF<4,JO+1,IQ,LOG_CACHE>;
AK TableFix4 table_8,table_16_1,table_16_3;
AK TableFix8 table_32_1,table_32_3;
AK HV CK;
AK HW EB;
AK HU EQ;
AK TableSqrt BZ;
AK AL AH BW*it8=&table_8[0],*it16_1=&table_16_1[0],*it16_3=&table_16_3[0],*it32_1=&table_32_1[0],*it32_3=&table_32_3[0];
AK KK dif4x4(CQ&r0,CQ&i0,CQ&r1,CQ&i1,CQ&r2,CQ&i2,CQ&r3,CQ&i3){
CB(r0,r1,r2,r3);
CB(i0,i1,i2,i3);
LK(r0,i0,r1,i1,r2,i2,r3,i3);
CB(r0,r1,r2,r3);
CB(i0,i1,i2,i3);}
AK KK idit4x4(CQ&r0,CQ&i0,CQ&r1,CQ&i1,CQ&r2,CQ&i2,CQ&r3,CQ&i3){
CB(r0,r1,r2,r3);
CB(i0,i1,i2,i3);
KB(r0,i0,r1,i1,r2,i2,r3,i3);
CB(r0,r1,r2,r3);
CB(i0,i1,i2,i3);}
AK KK dif8x2(BC&c0,BC&c1,BC&c2,BC&c3){
BC JE(it8);
BO(c0,c1);
BO(c2,c3);
c1=c1 .MT(JE),c3=c3 .MT(JE);
dif4x4(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);}
AK KK idit8x2(BC&c0,BC&c1,BC&c2,BC&c3){
BC JE(it8);
idit4x4(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c1=c1 .BT(JE),c3=c3 .BT(JE);
BO(c0,c1);
BO(c2,c3);}
AK KK dif16(BW BJ[]){
KO p=AN<BC*>(BJ);
BC c0=p[0],c1=p[1],c2=p[2],c3=p[3];
LK(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c1=c1 .MT(BC(it8)),c2=c2 .MT(BC(it16_1)),c3=c3 .MT(BC(it16_3));
dif4x4(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
p[0]=c0,p[1]=c1,p[2]=c2,p[3]=c3;}
AK KK idit16(BW BJ[]){
KO p=AN<BC*>(BJ);
BC c0=p[0],c1=p[1],c2=p[2],c3=p[3],JE;
idit4x4(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c1=c1 .BT(BC(it8)),c2=c2 .BT(BC(it16_1)),c3=c3 .BT(BC(it16_3));
KB(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
p[0]=c0,p[1]=c1,p[2]=c2,p[3]=c3;}
AK KK dif32(BW BJ[]){
KO p=AN<BC*>(BJ);
BC c0=p[0],c1=p[2],c2=p[4],c3=p[6];
JD(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c2=c2 .MT(BC(it32_1)),c3=c3 .MT(BC(it32_3));
p[0]=c0,p[2]=c1,p[4]=c2,p[6]=c3;
c0=p[1],c1=p[3],c2=p[5],c3=p[7];
JD(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c2=c2 .MT(BC(it32_1+8)),c3=c3 .MT(BC(it32_3+8));
p[1]=c0,p[3]=c1,c0=p[4],c1=p[6];
dif8x2(c0,c2,c1,c3);
p[4]=c0,p[5]=c2,p[6]=c1,p[7]=c3;
dif16(BJ);}
AK KK idit32(BW BJ[]){
idit16(BJ);
KO p=AN<BC*>(BJ);
BC c0=p[4],c1=p[5],c2=p[6],c3=p[7];
idit8x2(c0,c1,c2,c3);
p[5]=c1,p[7]=c3,c1=p[0],c3=p[2];
c0=c0 .BT(BC(it32_1)),c2=c2 .BT(BC(it32_3));
IF(c1 .LG,c1 .LH,c3 .LG,c3 .LH,c0 .LG,c0 .LH,c2 .LG,c2 .LH);
p[0]=c1,p[2]=c3,p[4]=c0,p[6]=c2;
c0=p[1],c1=p[3],c2=p[5],c3=p[7];
c2=c2 .BT(BC(it32_1+8)),c3=c3 .BT(BC(it32_3+8));
IF(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
p[1]=c0,p[3]=c1,p[5]=c2,p[7]=c3;}
BG<BQ F32,BQ F16>
AK KK fftTiny(BW BJ[],AJ AV,F32&&func32,F16&&func16){
if(CW(AV/2)%2==0)
{
MV(KO end=BJ+AV;BJ<end;BJ+=32)
{
func16(BJ);}}
zc
{
MV(KO end=BJ+AV;BJ<end;BJ+=64)
{
func32(BJ);}}}
#define E8Z3_FUSE_MINRANK 256u
AK KK difTop2(BW*BJ,AJ AV,AJ R){
AH AJ S1=R/2,S2=R/8;
MV(BW*EU=BJ,*bend=BJ+AV;EU<bend;EU+=R*2){
AH BW*t1a=CK.CT(R*2),*t2a=CK.CT(R),*t3a=EB.CT(R);
AH BW*t1b=CK.CT(R/2),*t2b=CK.CT(R/4),*t3b=EB.CT(R/4);
MV(AJ j2=0;j2<S2;j2+=8){
BC v[4][4]={za,za,za,za,za,za,za,za,za,za,za,za,za,za,za,za};
MV(MX q=0;q<4;q++){
AH AJ LZ=(AJ)q*S2+j2;
BC c0(EU+LZ),c1(EU+S1+LZ),c2(EU+2*S1+LZ),c3(EU+3*S1+LZ);
LK(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c1=c1 .MT(BC(t2a+LZ));c2=c2 .MT(BC(t1a+LZ));c3=c3 .MT(BC(t3a+LZ));
v[0][q]=c0;v[1][q]=c1;v[2][q]=c2;v[3][q]=c3;
}
MV(MX s=0;s<4;s++){
BC c0=v[s][0],c1=v[s][1],c2=v[s][2],c3=v[s][3];
LK(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c1=c1 .MT(BC(t2b+j2));c2=c2 .MT(BC(t1b+j2));c3=c3 .MT(BC(t3b+j2));
c0 .CO(EU+(AJ)s*S1+j2);
c1 .CO(EU+(AJ)s*S1+S2+j2);
c2 .CO(EU+(AJ)s*S1+2*S2+j2);
c3 .CO(EU+(AJ)s*S1+3*S2+j2);
}
}
}
}
AK KK difIter(BW BJ[],AJ AV){
AJ CA=AV/2;
BC c0(BV{}),c1(BV{}),c2(BV{}),c3(BV{});
AJ AU=CA/2;
KO MN=BJ,MG=MN+AU,MB=MG+AU,LW=MB+AU;
if(CA>=E8Z3_FUSE_MINRANK){difTop2(BJ,AV,CA);}
MV(AJ LI=CA>=E8Z3_FUSE_MINRANK?CA/16:CA;LI>=64;LI/=4)
{
AU=LI/2;
MV(KO EU=BJ,end=BJ+AV;EU<end;EU+=LI*2)
{
KO GN=CK.CT(LI*2),JT=CK.CT(LI),JU=EB.CT(LI);
MN=EU,MG=MN+AU,MB=MG+AU,LW=MB+AU;
MV(;MN<EU+AU;MN+=8,MG+=8,MB+=8,LW+=8,GN+=8,JT+=8,JU+=8)
{
c0=MN,c1=MG,c2=MB,c3=LW;
LK(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c1=c1 .MT(BC(JT)),c2=c2 .MT(BC(GN)),c3=c3 .MT(BC(JU));
c0 .CO(MN),c1 .CO(MG),c2 .CO(MB),c3 .CO(LW);
}}}
fftTiny(BJ,AV,dif32,dif16);}
AK KK iditIter(BW BJ[],AJ AV){
if(CG::FC)CG::run(BJ,AV);
AJ CA=AV/2;
AJ LI=CW(CA)%2==0?64:128;
fftTiny(BJ,AV,idit32,idit16);
MV(;LI<=CA;LI*=4)
{
AH AJ AU=LI/2;
MV(KO EU=BJ,end=BJ+AV;EU<end;EU+=LI*2)
{
KO GN=CK.CT(LI*2),JT=CK.CT(LI),JU=EB.CT(LI);
KO MN=EU,MG=MN+AU,MB=MG+AU,LW=MB+AU;
MV(;MN<EU+AU;MN+=8,MG+=8,MB+=8,LW+=8,GN+=8,JT+=8,JU+=8)
{
BC c0=MN,c1=MG,c2=MB,c3=LW;
c1=c1 .BT(BC(JT)),c2=c2 .BT(BC(GN)),c3=c3 .BT(BC(JU));
KB(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c0 .CO(MN),c1 .CO(MG),c2 .CO(MB),c3 .CO(LW);
}}}}
#define difLayer(IG, BJ, AU, GF) \
do \
{ \
KO MN = BJ, MG = BJ + AU, MB = MG + AU, LW = MB + AU; \
AJ indx = 0; \
MV (KO end = MG; CL && MN < end; MN += 8, MG += 8, MB += 8, LW += 8, indx++) \
{ \
BC c0, c1, c2, c3, FH, HG; \
c0.LF(MN, JF{}), c1.LF(MG, JF{}), c2 = c0,c3 = c1; \
BO(c0,c1); \
GT(c2.LG,c2.LH,c3.LG,c3.LH); \
FH = GF[indx], c2 = c2.MT(FH); \
HG = FH.uS(), c1 = c1.MT(HG); \
c3 = c3.MT(FH.uC(HG)); \
c0.CO(MN), c1.CO(MG), c2.CO(MB), c3.CO(LW); \
} \
MV (KO end = MG; (!CL) && MN < end; MN += 8, MG += 8, MB += 8, LW += 8, indx++) \
{ \
AP((AH KV*)(MN+64),AW); \
AP((AH KV*)(MG+64),AW); \
AP((AH KV*)(MB+64),AW); \
AP((AH KV*)(LW+64),AW); \
BC c0 = MN, c1 = MG, c2 = MB, c3 = LW, FH, HG; \
LK(c0.LG, c0.LH, c1.LG, c1.LH, c2.LG, c2.LH, c3.LG, c3.LH); \
FH = GF[indx], c2 = c2.MT(FH); \
HG = FH.uS(), c1 = c1.MT(HG); \
c3 = c3.MT(FH.uC(HG)); \
c0.CO(MN), c1.CO(MG), c2.CO(MB), c3.CO(LW); \
} \
IG(BJ, AU); \
IG(BJ + AU, AU); \
IG(BJ + AU * 2, AU); \
IG(BJ + AU * 3, AU); \
} JX (0)
#define iditLayer(GY, BJ, AU, GF) \
do \
{ \
GY(BJ, AU); \
GY(BJ + AU, AU); \
GY(BJ + AU * 2, AU); \
GY(BJ + AU * 3, AU); \
KO MN = BJ, MG = BJ + AU, MB = MG + AU, LW = MB + AU; \
AJ indx = 0; \
_Pragma("GCC unroll 4") \
MV (KO end = MG; MN < end; MN += 8, MG += 8, MB += 8, LW += 8, indx++) \
{ \
AP((AH KV*)(MN+64),AW); \
AP((AH KV*)(MG+64),AW); \
AP((AH KV*)(MB+64),AW); \
AP((AH KV*)(LW+64),AW); \
BC c0 = MN, c1 = MG, c2 = MB, c3 = LW, FH, HG; \
FH = GF[indx], c2 = c2.BT(FH); \
HG = FH.uS(), c1 = c1.BT(HG); \
c3 = c3.BT(FH.uC(HG)); \
KB(c0.LG, c0.LH, c1.LG, c1.LH, c2.LG, c2.LH, c3.LG, c3.LH); \
c0 = c0.CE(ToI64{}), c1 = c1.CE(ToI64{}), c2 = c2.CE(ToI64{}), c3 = c3.CE(ToI64{}); \
c0.CO(MN, JV{}), c1.CO(MG, JV{}), c2.CO(MB, JV{}), c3.CO(LW, JV{}); \
} \
} JX (0)
BG<KL CL=ED>
AK KK IH(BW BJ[],AJ AV){
AH AJ CA=AV/2;
if(CA<=GG)
{
difIter(BJ,AV);
BD;}
GE JF=MP::CR<KL,CL>;
KO GN=AN<AH BC*>(EQ.CT(CA));
AH AJ AU=AV/4;
difLayer(IH,BJ,AU,GN);}
BG<KL EK=ED,KL HH=ED>
AK KK iditRecMid(BW BJ[],AJ AV){
AH AJ CA=AV/2;
if(CA<=GG)
{
if(!GM)iditIter(BJ,AV);
BD;}
GE JV=MP::CR<KL,EK>;
GE ToI64=MP::CR<KL,HH>;
AH AJ AU=AV/4;
KO GN=AN<AH BC*>(EQ.CT(CA));
iditLayer(iditRecMid,BJ,AU,GN);}
AK KK fusedLong(BW*a,AJ MQ,KL IR){
AJ AU=MQ/16;
AH KO&t0=BZ[CW(MQ/2)];
AH KO&t1=BZ[CW(MQ/8)];
if(IR)MV(MX k=0;k<16;k++)EH<ED,ED>(a+k*AU,AU);
MV(AJ j=0;j<AU;j+=8){
if(j>=64&&j+416<AU){
MV(MX k=0;k<16;k++)AP((AH KV*)(a+(AJ)k*AU+j-64+32*k),AW);
}
BC v[16];
KO butterfly=[&](BC&c0,BC&c1,BC&c2,BC&c3,AH BC&w){
BC w2=w.uS(),w3=w.uC(w2);
if(IR){
c1=c1 .BT(w2);c2=c2 .BT(w);c3=c3 .BT(w3);
KB(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
}zc{
LK(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c1=c1 .MT(w2);c2=c2 .MT(w);c3=c3 .MT(w3);
}
};
AH BC w=t1[j/8],w2=w.uS(),w3=w.uC(w2);
KO FR=[&](BC&c0,BC&c1,BC&c2,BC&c3){
if(IR){
c1=c1 .BT(w2);c2=c2 .BT(w);c3=c3 .BT(w3);
KB(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
}zc{
LK(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c1=c1 .MT(w2);c2=c2 .MT(w);c3=c3 .MT(w3);
}
};
if(IR){
#pragma GCC unroll 4
MV(MX q=0;q<4;q++){
v[4*q]=BC(a+(4*q)*AU+j);
v[4*q+1]=BC(a+(4*q+1)*AU+j);
v[4*q+2]=BC(a+(4*q+2)*AU+j);
v[4*q+3]=BC(a+(4*q+3)*AU+j);
FR(v[4*q],v[4*q+1],v[4*q+2],v[4*q+3]);
}
#pragma GCC unroll 4
MV(MX k=0;k<4;k++){
butterfly(v[k],v[k+4],v[k+8],v[k+12],t0[(k*AU+j)/8]);
v[k].CO(a+k*AU+j);
v[k+4].CO(a+(k+4)*AU+j);
v[k+8].CO(a+(k+8)*AU+j);
v[k+12].CO(a+(k+12)*AU+j);
}
}zc{
#pragma GCC unroll 4
MV(MX k=0;k<4;k++){
v[k]=BC(a+k*AU+j);
v[k+4]=BC(a+(k+4)*AU+j);
v[k+8]=BC(a+(k+8)*AU+j);
v[k+12]=BC(a+(k+12)*AU+j);
butterfly(v[k],v[k+4],v[k+8],v[k+12],t0[(k*AU+j)/8]);
}
#pragma GCC unroll 4
MV(MX q=0;q<4;q++){
FR(v[4*q],v[4*q+1],v[4*q+2],v[4*q+3]);
v[4*q].CO(a+(4*q)*AU+j);
v[4*q+1].CO(a+(4*q+1)*AU+j);
v[4*q+2].CO(a+(4*q+2)*AU+j);
v[4*q+3].CO(a+(4*q+3)*AU+j);
}
}
}
if(!IR)MV(MX k=0;k<16;k++)EL<ED>(a+k*AU,AU);
}
AK KK difFuseAB(BW*a,AJ AV){
AH AJ CA=AV/2;
AH AJ sa=AV/4;
AH AJ sb=sa/4;
AH KO&TA=BZ[CW(CA)];
AH BC*TB=AN<AH BC*>(EQ.CT(sa/2));
MV(AJ j0=0;j0<sb;j0+=8){
BC A[4][4]={za,za,za,za,za,za,za,za,za,za,za,za,za,za,za,za};
AH AJ jb=j0>>3;
AH BC*talp=TA.JC()+(jb&TA.KE);
AH BC talv=*talp;
AH AJ tahbase=(jb>>TA.LJ),tahstep=(sb>>3)>>TA.LJ;
MV(MX k2=0;k2<4;k2++){
MS*pj=a+(AJ)k2*sb+j0;
AP((AH KV*)(pj+sa+128+8*k2),AW);
AP((AH KV*)(pj+2*sa+136+8*k2),AW);
AP((AH KV*)(pj+3*sa+144+8*k2),AW);
BC c0(pj),c1(pj+sa),c2(pj+2*sa),c3(pj+3*sa);
LK(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
AH LX*tahp=TA.HE()+tahbase+(AJ)k2*tahstep;
BC tah(BV{});{AH MS*hq=AN<AH MS*>(tahp);tah.JR(hq,hq+1);}
BC w=talv.MT(tah),w2=w.uS();
c2=c2 .MT(w);c1=c1 .MT(w2);c3=c3 .MT(w.uC(w2));
A[k2][0]=c0;A[k2][1]=c1;A[k2][2]=c2;A[k2][3]=c3;
}
AH BC wB=TB[j0>>3],wB2=wB.uS(),wB3=wB.uC(wB2);
MV(MX k1=0;k1<4;k1++){
BC c0=A[0][k1],c1=A[1][k1],c2=A[2][k1],c3=A[3][k1];
LK(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c2=c2 .MT(wB);c1=c1 .MT(wB2);c3=c3 .MT(wB3);
MS*q=a+(AJ)k1*sa+j0;
c0 .CO(q);c1 .CO(q+sb);c2 .CO(q+2*sb);c3 .CO(q+3*sb);
}
}
MV(MX k1=0;k1<4;k1++)MV(MX k2=0;k2<4;k2++)
IH<ED>(a+(AJ)k1*sa+(AJ)k2*sb,sb);
}
BG<KL CL=ED>
AK KK EL(BW BJ[],AJ AV){
if AL(!CL)if(AV/2>=(1ULL<<22)){fusedLong(BJ,AV,ED);BD;}
AH AJ CA=AV/2;
if(CA<=MID_LEN)
{
IH<CL>(BJ,AV);
BD;}
if AL(!CL)
if(AV>(1ULL<<18)&&AV<=(1ULL<<20)){difFuseAB(BJ,AV);BD;}
GE JF=MP::CR<KL,CL>;
AH KO&GN=BZ[CW(CA)];
AH AJ AU=AV/4;
difLayer(EL,BJ,AU,GN);}
BG<KL EK=ED,KL HH=ED>
AK KK EH(BW BJ[],AJ AV){
if AL(!EK&&!HH)if(AV/2>=(1ULL<<22)){fusedLong(BJ,AV,KR);BD;}
AH AJ CA=AV/2;
if(CA<=MID_LEN)
{
iditRecMid<EK,HH>(BJ,AV);
BD;}
GE JV=MP::CR<KL,EK>;
GE ToI64=MP::CR<KL,HH>;
AH AJ AU=AV/4;
AH KO&GN=BZ[CW(CA)];
iditLayer(EH,BJ,AU,GN);}};
#undef difLayer
#undef iditLayer
AL MX CJ::GH,CJ::JO,CJ::IQ,CJ::LOG_CACHE;
AL AJ CJ::GG,CJ::MID_LEN,CJ::MAX_LEN;
CJ::TableFix4 CJ::table_8(8,1,4),CJ::table_16_1(16,1,4),CJ::table_16_3(16,3,4);
CJ::TableFix8 CJ::table_32_1(32,1,4),CJ::table_32_3(32,3,4);
CJ::HV CJ::CK(2);
CJ::HW CJ::EB(3);
CJ::HU CJ::EQ(1);
CJ::TableSqrt CJ::BZ(1);
AL CF bitrev32(CF n){
AL CF mask55=0x55555555;
AL CF mask33=0x33333333;
AL CF mask0f=0x0f0f0f0f;
AL CF maskff=0x00ff00ff;
n=((n&mask55)<<1)|((n>>1)&mask55);
n=((n&mask33)<<2)|((n>>2)&mask33);
n=((n&mask0f)<<4)|((n>>4)&mask0f);
n=((n&maskff)<<8)|((n>>8)&maskff);
BD(n<<16)|(n>>16);}
AL CF bitrev(CF n,MX MQ){
BD bitrev32(n)>>(32-MQ);}
BG<MX DY,MX DIV>
KA CC{
IZ:
AK AL MX LOG_BLOCK=2,JW=1<<LOG_BLOCK;
AK AL AJ MAX_LEN=AJ(1)<<DY;
JS Unit{
LX units[DY]{};
MS IK[JW*2]{};
Unit()
{
AL MS DG=MS(1)/DIV;
MV(MX i=0;i<DY;i++)
{
units[i]=getOmega(AJ(1)<<(i+1),1,DG);}
IK[0]=1,IK[JW]=0;
MV(MX i=1;i<JW;i++)
{
LX JE=getOmega(JW,bitrev(i,LOG_BLOCK),DG);
IK[i]=JE.LG(),IK[i+JW]=JE.LH();}}};
CC():IP(0),pop(0){
MP::GW(GF,FI.IK,JQ(FI.IK));}
KK reset(AJ i=0){
if(i==0)
{
pop=0,IP=i;
BD;}
pop=1,IP=i/JW;
MX LM=__builtin_ctzll(IP);
KO fp=AN<AH MS*>(&FI.units[LM+2]);
GF[1].JR(fp,fp+1);
GF[1]=GF[1].MT(GF[0]);}
BC iterate(){
BC res=GF[pop],unit4(BV{});
IP++;
MX LM=__builtin_ctzll(IP);
KO fp=AN<AH MS*>(&FI.units[LM+2]);
unit4 .JR(fp,fp+1);
pop-=LM;
GF[pop+1]=GF[pop].MT(unit4);
pop++;
BD res;}
AK LX getOmega(AJ n,AJ IP,MS DG=1){
(KK)DG;BD DZ(n*AJ(DIV),IP);
}
JN:
GR(64)AK AH Unit FI;
GR(64)BC GF[DY];
AJ IP;
MX pop;
MX log_max_iter,log_fft_len;};
BG<MX DY,MX DIV>
GR(64)AH BQ CC<DY,DIV>::Unit CC<DY,DIV>::FI;
BG<AJ HX=1,BQ HI>
BR KK JG(HI*JH,HI*JI,AH HI*in0,AH HI*in1,
AH MP::JM<HI>&JE,AH HI LV=1){
GE HY=MP::JM<HI>;
KO addConj=[](HY c0,HY c1){BD HY(c0 .LG()+c1 .LG(),c0 .LH()-c1 .LH());};
HY x0(JH[0],JH[HX]),x1(JI[0],JI[HX]),
y0(in0[0],in0[HX]),y1(in1[0],in1[HX]);
KO t0=x0*y0,t1=x1*y1,xy0=addConj(x0,x1),xy1=addConj(y0,y1);
KO t2=xy0*xy1;
y1=addConj(t0,t1);
x1=(y1+y1-t2)*JE*JE;
AH KO inv2=LV+LV;
x0=(t2-x1)*LV,x1=HY(t0 .LG()-t1 .LG(),t0 .LH()+t1 .LH())*inv2;
HY out0=x0+x1,out1(x0 .LG()-x1 .LG(),x1 .LH()-x0 .LH());
JH[0]=out0 .LG(),JH[HX]=out0 .LH();
JI[0]=out1 .LG(),JI[HX]=out1 .LH();}
BR KK HJ(MS*JH,MS*JI,AH MS*in0,AH MS*in1,AH BC&JE,AH CQ&LV){
BC x0=JH,x1=BC(JI).HC(),y0=in0,y1=BC(in1).HC();
AH BC dx(x0 .LG-x1 .LG,x0 .LH+x1 .LH),dy(y0 .LG-y1 .LG,y0 .LH+y1 .LH);
AH BC HK=dx.MT(dy).MT(BC(JE.LG+CQ(1.0),JE.LH))*CQ(0.25);
AH BC p0=x0 .MT(y0),p1=x1 .MT(y1);
AH CQ inv4=LV*CQ(4.0);
((p0-HK)*inv4).CO(JH);
(BC(p1 .LG-HK.LG,p1 .LH+HK.LH)*inv4).HC().CO(JI);}
BR KK FJ(BW BJ[],BW in[],AJ AV,BW scale=1){
BW LV=2.0*scale/AV;{
KO r0=BJ[0],i0=BJ[4],r1=in[0],i1=in[4];
BO(r0,i0);
BO(r1,i1);
r0*=r1,i0*=i1;
BO(r0,i0);
BJ[0]=r0*0.5*LV,BJ[4]=i0*0.5*LV;}
KO temp=LX(BJ[1],BJ[5])*LX(in[1],in[5])*LV;
BJ[1]=temp.LG(),BJ[5]=temp.LH();
LV/=4;
JG<4>(&BJ[2],&BJ[3],&in[2],&in[3],LX(COS_PI_8,-COS_PI_8),LV);
AL BW COS_16_1=0.92387953251128675612818318939;
AL BW SIN_16_1=0.38268343236508977172845998403;
JG<4>(&BJ[8],&BJ[11],&in[8],&in[11],LX(COS_16_1,-SIN_16_1),LV);
JG<4>(&BJ[9],&BJ[10],&in[9],&in[10],LX(-SIN_16_1,-COS_16_1),LV);
AH EG inv4=CQ(0.5*scale/AV);
CC<28,1>GF;
MV(AJ EU=16;EU<AV;EU*=2){
GF.reset(EU/2);
KO MN=BJ+EU,MG=MN+EU-8,MB=in+EU,LW=MB+EU-8;
MV(;MN<MG;MN+=8,MG-=8,MB+=8,LW-=8)
{
AP((AH KV*)(MN+256),AW);
AP((AH KV*)(MG-256),AW);
AP((AH KV*)(MB+256),AW);
AP((AH KV*)(LW-256),AW);
HJ(MN,MG,MB,LW,GF.iterate(),inv4);}}}
DM CG{
KL FC=ED;
MS*aa=DT,*bb=DT;
MS*bbch[5]={DT,DT,DT,DT,DT};
AJ DB=0,IT=0;
MX cid=0;
KL fuse=ED;
BC HO;
AK CC<28,1>&table_ref(){AK CC<28,1>GF;BD GF;}
KK EU(MS*a,MS*AH*bch,AJ ch,AJ n,MX r){
aa=a;MV(MX i=0;i<5;i++)bbch[i]=bch[i];bb=bch[0];DB=ch;IT=n;cid=r;FC=(r==1||r==2);
if(FC){LX z=DZ(5*(DB/2),r);HO=BC(z.LG(),z.LH());table_ref().reset();}
}
KK run(MS*p,AJ KC){
AH AJ first=(AJ)(p-aa)-(AJ)cid*DB;
AH CQ LV(0.5/IT);
KO&tbl=table_ref();
MS*ab=aa+(AJ)cid*DB;MS*ac=aa+(AJ)(6-cid)*DB-8;
MS*b0=bbch[cid];MS*b1=bbch[5-cid]+(DB-8);
AH AJ endj=first+KC;
AJ j=first;
AH AJ pfend=DB>192?MP::min(endj,DB-192):first;
MV(;j<pfend;j+=8){
AP((AH KV*)(ab+j+192),AW);
AP((AH KV*)(ac-j-192),AW);
AP((AH KV*)(b0+j+192),AW);
AP((AH KV*)(b1-j-192),AW);
HJ(ab+j,ac-j,b0+j,b1-j,tbl.iterate().MT(HO),LV);
}
MV(;j<endj;j+=8)
HJ(ab+j,ac-j,b0+j,b1-j,tbl.iterate().MT(HO),LV);
if(fuse&&(KC==(AJ(1)<<11)||KC==(AJ(1)<<12))){
MS*mp=aa+(AJ)(5-cid)*DB+(DB-first-KC);
KL en=FC;FC=ED;
CJ::iditIter(mp,KC);
FC=en;
}
}
}
BG<KL TO_INT=ED>
BR KK real_conv_avx(MS*in_out1,MS*in2,AJ AV){
CJ::EL<KR>(in_out1,AV);
CJ::EL<KR>(in2,AV);
FJ(in_out1,in2,AV);
CJ::EH<KR,TO_INT>(in_out1,AV);}}}}
zp zg zh*ar_in_a,*ar_in_b;zp size_t ar_na,ar_nb;zp bool ar_reverse_a;
zp zh*ar_final_c;zp zh char*ar_final_alpha;zp KL ar_rev=ED;
zp bool ze=false;
DM LB{DM IB{DM fft{
AK MS*g_bch[5]={DT,DT,DT,DT,DT};
zp inline zo ar_quant4(__m256d value,zj bytes){
constexpr uint64_t product=uint64_t(2013265921)*1866465281;
zg __m256d magic=_mm256_set1_pd(0x1.8p52),factor=_mm256_set1_pd(double(uint64_t(1)<<48)/double(product));
zo q=_mm256_sub_epi64(_mm256_castpd_si256(_mm256_add_pd(_mm256_mul_pd(value,factor),magic)),_mm256_castpd_si256(magic));
return _mm256_srli_epi64(_mm256_add_epi64(q,_mm256_add_epi64(_mm256_cvtepu8_epi64(bytes),_mm256_set1_epi64x(128))),8);
}
zp inline void zb(zg BC&value,size_t zi){
if(zi>=10000000)return;
size_t dst=ar_rev?(10000000-8-zi):zi;
BC v=value.toRIRIPermu();zj bytes=_mm_loadl_epi64((zg zj*)(ar_final_alpha+zi));
zo lo=ar_quant4(v.LG,bytes),hi=ar_quant4(v.LH,_mm_srli_si128(bytes,4));
zo carry=_mm256_permute4x64_epi64(_mm256_castps_si256(_mm256_shuffle_ps(_mm256_castsi256_ps(lo),_mm256_castsi256_ps(hi),0x88)),0xd8);
zo delta=_mm256_mullo_epi32(carry,_mm256_set1_epi32(uint32_t(uint64_t(2013265921)*1866465281)));
if(ar_rev)delta=_mm256_permutevar8x32_epi32(delta,_mm256_setr_epi32(7,6,5,4,3,2,1,0));
_mm256_storeu_si256((zo*)(ar_final_c+dst),_mm256_add_epi32(_mm256_loadu_si256((zg zo*)(ar_final_c+dst)),delta));
}
AK KK latest_real_conv5(MS*a,MS*b,AJ IT,AJ used_a,AJ used_b){
auto zd=[&](MS*zg*px,size_t zi)->BC{
zg bool isa=px[0]==a;zg zh*p=isa?ar_in_a:ar_in_b;size_t used=isa?ar_na:ar_nb;bool rev=isa&&ar_reverse_a;
if(zi>=used)return BC(CQ(0.0),CQ(0.0));
zj lo,hi;
if(zi+8<=used){zg zh*q=p+(rev?used-zi-8:zi);lo=zk((zg zj*)q);hi=zk((zg zj*)(q+4));if(rev){auto t=lo;lo=_mm_shuffle_epi32(hi,0x1b);hi=_mm_shuffle_epi32(t,0x1b);}}
zc{zh v[8];for(zh j=0;j<8;j++)v[j]=zi+j<used?p[rev?used-1-zi-j:zi+j]:0x80000000u;lo=zk((zg zj*)v);hi=zk((zg zj*)(v+4));}
zg zj sign=_mm_set1_epi32(int(0x80000000u));zg __m256d scale=_mm256_set1_pd(1./1048576.);
return BC(CQ(_mm256_mul_pd(_mm256_cvtepi32_pd(_mm_xor_si128(lo,sign)),scale)),CQ(_mm256_mul_pd(_mm256_cvtepi32_pd(_mm_xor_si128(hi,sign)),scale))).toRRIIPermu();
};
AH AJ DB=IT/5,L=DB/2;
BM<6>KF(IT/2,5,1);
AH CQ c1(0.30901699437494742410229341718282),c2(-0.80901699437494742410229341718282),
s1(0.95105651629515357211643933337938),s2(0.58778525229247312916870595463907),LM(0.0);
KO LN=[&](AH BC&z){BD BC(z.LH,LM-z.LG);};
KO posI=[&](AH BC&z){BD BC(LM-z.LH,z.LG);};
KO GU=[&](KO has2_tag,MS*AH*px,AJ j0,AJ jend){
AL KL HAS2=decltype(has2_tag)::KD;
MV(AJ j=j0;j<jend;j+=8){
AP((AH KV*)(px[0]+j+384),AW);
AP((AH KV*)(px[1]+j+384),AW);
if AL(HAS2)AP((AH KV*)(px[2]+j+384),AW);
BC x0,x1,x2;
x0=zd(px,0*DB+j);
x1=zd(px,1*DB+j);
if AL(HAS2)x2=zd(px,2*DB+j);
BC t1,t2,u1,u2;
if AL(HAS2){
t1=x0+x1*c1+x2*c2;
t2=x0+x1*c2+x2*c1;
u1=LN(x1*s1+x2*s2);
u2=LN(x1*s2-x2*s1);
}zc{
t1=x0+x1*c1;
t2=x0+x1*c2;
u1=LN(x1*s1);
u2=LN(x1*s2);
}
BC w=KF[j/8],w2=w.uS(),w3=w.uC(w2),w4=w2.uS();
if AL(HAS2)(x0+x1+x2).CO(px[0]+j);
zc(x0+x1).CO(px[0]+j);
(t1+u1).MT(w).CO(px[1]+j);
if AL(HAS2)(t2+u2).MT(w2).CO(px[2]+j);zc(t2+u2).MT(w2).DO(px[2]+j);
(t2-u2).MT(w3).DO(px[3]+j);
(t1-u1).MT(w4).DO(px[4]+j);
}
};
KO forward=[&](MS*AH*px,AJ used){
AJ active2=used>2*DB?used-2*DB:0;
AJ FZ=MP::min(DB,(active2+7)&~AJ(7));
if(DB/2>=(AJ(1)<<21)){
AH AJ AU=DB/16;
AH KO&tf0=CJ::BZ[CW(DB/2)];
AH KO&tf1=CJ::BZ[CW(DB/8)];
AL AJ W=128;
GR(64)MS ys[16][5][W];
MV(AJ j0=0;j0<AU;j0+=W){
AH AJ cnt=MP::min(W,AU-j0);
MV(MX k=0;k<16;k++){
AH AJ cb=(AJ)k*AU+j0;
MS*y0p=ys[k][0];MS*y1p=ys[k][1];MS*y2p=ys[k][2];MS*y3p=ys[k][3];MS*y4p=ys[k][4];
MV(AJ w=0;w<cnt;w+=8){
AH AJ c=cb+w;
AP((AH KV*)(px[0]+c+384),AW);
AP((AH KV*)(px[1]+c+384),AW);
BC x0,x1,x2;
x0=zd(px,0*DB+c);
x1=zd(px,1*DB+c);
BC t1v,t2v,u1v,u2v;
AH BC ww=KF[c/8],w2=ww.uS(),w3=ww.uC(w2),w4=w2.uS();
if(c<FZ){
x2=zd(px,2*DB+c);
AH BC both=x1+x2;
AH BC HL=x0-both*CQ(0.25);
AH BC HM=(x1-x2)*CQ(0.55901699437494742410229341718282);
AH BC LO=both*s2;
t1v=HL+HM;t2v=HL-HM;
u1v=LN(LO+x1*CQ(0.36327126400268044294773337874031));
u2v=LN(LO-x2*CQ(1.5388417685876267012851452880185));
(x0+x1+x2).CO(y0p+w);
}zc{
t1v=x0+x1*c1;
t2v=x0+x1*c2;
u1v=LN(x1*s1);
u2v=LN(x1*s2);
(x0+x1).CO(y0p+w);
}
(t1v+u1v).MT(ww).CO(y1p+w);
(t2v+u2v).MT(w2).CO(y2p+w);
(t2v-u2v).MT(w3).CO(y3p+w);
(t1v-u1v).MT(w4).CO(y4p+w);
}
}
#pragma GCC unroll 5
MV(MX r=0;r<5;r++){
MS*pr=px[r];
MV(AJ w=0;w<cnt;w+=8){
BC v[16];
#pragma GCC unroll 4
MV(MX k=0;k<4;k++){
v[k]=BC(ys[k][r]+w);v[k+4]=BC(ys[k+4][r]+w);v[k+8]=BC(ys[k+8][r]+w);v[k+12]=BC(ys[k+12][r]+w);
BC ww=tf0[((AJ)k*AU+j0+w)/8],w2=ww.uS(),w3=ww.uC(w2);
CJ::LK(v[k].LG,v[k].LH,v[k+4].LG,v[k+4].LH,v[k+8].LG,v[k+8].LH,v[k+12].LG,v[k+12].LH);
v[k+4]=v[k+4].MT(w2);v[k+8]=v[k+8].MT(ww);v[k+12]=v[k+12].MT(w3);
}
BC ww=tf1[(j0+w)/8],w2=ww.uS(),w3=ww.uC(w2);
#pragma GCC unroll 4
MV(MX q2=0;q2<4;q2++){
BC c0=v[4*q2],c1v=v[4*q2+1],c2v=v[4*q2+2],c3v=v[4*q2+3];
CJ::LK(c0 .LG,c0 .LH,c1v.LG,c1v.LH,c2v.LG,c2v.LH,c3v.LG,c3v.LH);
c1v=c1v.MT(w2);c2v=c2v.MT(ww);c3v=c3v.MT(w3);
AH AJ p=(AJ)(4*q2)*AU+j0+w;
if(r<2||(r==2&&p<FZ))c0 .CO(pr+p);zc c0 .DO(pr+p);
if(r<2||(r==2&&p+AU<FZ))c1v.CO(pr+p+AU);zc c1v.DO(pr+p+AU);
if(r<2||(r==2&&p+2*AU<FZ))c2v.CO(pr+p+2*AU);zc c2v.DO(pr+p+2*AU);
if(r<2||(r==2&&p+3*AU<FZ))c3v.CO(pr+p+3*AU);zc c3v.DO(pr+p+3*AU);
}
}
}
}
FF();
MV(MX r=0;r<5;++r)MV(MX k=0;k<16;++k)CJ::EL<ED>(px[r]+(AJ)k*AU,AU);
BD;
}
GU(MP::BI{},px,0,FZ);
GU(MP::HD{},px,FZ,DB);
FF();
MV(MX r=0;r<5;++r)CJ::EL<ED>(px[r],DB);
};
MS*pa[5];MV(MX r=0;r<5;++r)pa[r]=a+r*DB;
MS*pb[5];MV(MX r=0;r<5;++r)pb[r]=g_bch[r]?g_bch[r]:(b+r*DB);
if(DB/2>=(AJ(1)<<21)){
AJ splits[2];AJ useds[2]={used_a,used_b};
MV(MX z=0;z<2;z++){AJ active=useds[z]>2*DB?useds[z]-2*DB:0;splits[z]=MP::min(DB,(active+7)&~AJ(7));}
AH AJ AU=DB/16;
AH KO&tf0=CJ::BZ[CW(DB/2)];
AH KO&tf1=CJ::BZ[CW(DB/8)];
AL AJ W=128;
GR(64)MS ys[2][16][5][W];
MV(AJ j0=0;j0<AU;j0+=W){
AH AJ cnt=MP::min(W,AU-j0);
AH AJ tb=j0>>3;
AH BC*tf0lp0=tf0 .JC()+(tb&tf0 .KE);
AH BC*tf1lp0=tf1 .JC()+(tb&tf1 .KE);
AH AJ tfhstep=(AU>>3)>>tf0 .LJ;
BC tf0hi[4]={za,za,za,za},tf1hi(za);
MV(MX k=0;k<4;k++){AH LX*hp=tf0 .HE()+(tb>>tf0 .LJ)+(AJ)k*tfhstep;AH MS*q=AN<AH MS*>(hp);tf0hi[k].JR(q,q+1);}
{AH LX*hp=tf1 .HE()+(tb>>tf1 .LJ);AH MS*q=AN<AH MS*>(hp);tf1hi.JR(q,q+1);}
MV(MX k=0;k<16;k++){
AH AJ cb=(AJ)k*AU+j0;
AH AJ rb=cb>>3;
AH BC*rlp=KF.JC()+(rb&BM<6>::KE);
AH LX*rhp=KF.HE()+(rb>>BM<6>::LJ);
BC rhi(LB::BV{});{AH MS*q=AN<AH MS*>(rhp);rhi.JR(q,q+1);}
MV(AJ w=0;w<cnt;w+=8){
AH AJ c=cb+w;
AH BC ww=rlp->MT(rhi),w2=ww.uS(),w3=ww.uC(w2),w4=w2.uS();
#pragma GCC unroll 1
MV(MX LP=0;LP<(ze?1:2);LP++){
MS*AH*px=LP?pb:pa;AH AJ FZ=splits[LP];
MS*y0p=ys[LP][k][0];MS*y1p=ys[LP][k][1];MS*y2p=ys[LP][k][2];MS*y3p=ys[LP][k][3];MS*y4p=ys[LP][k][4];
AP((AH KV*)(px[0]+c+384),AW);
AP((AH KV*)(px[1]+c+384),AW);
BC x0(LB::BV{}),x1(LB::BV{}),x2(LB::BV{});
x0=zd(px,0*DB+c);
x1=zd(px,1*DB+c);
BC t1v(LB::BV{}),t2v(LB::BV{}),u1v(LB::BV{}),u2v(LB::BV{});
if(c<FZ){
x2=zd(px,2*DB+c);
AH BC both=x1+x2;
AH BC HL=x0-both*CQ(0.25);
AH BC HM=(x1-x2)*CQ(0.55901699437494742410229341718282);
AH BC LO=both*s2;
t1v=HL+HM;t2v=HL-HM;
u1v=LN(LO+x1*CQ(0.36327126400268044294773337874031));
u2v=LN(LO-x2*CQ(1.5388417685876267012851452880185));
(x0+x1+x2).CO(y0p+w);
}zc{
t1v=x0+x1*c1;
t2v=x0+x1*c2;
u1v=LN(x1*s1);
u2v=LN(x1*s2);
(x0+x1).CO(y0p+w);
}
(t1v+u1v).MT(ww).CO(y1p+w);
(t2v+u2v).MT(w2).CO(y2p+w);
(t2v-u2v).MT(w3).CO(y3p+w);
(t1v-u1v).MT(w4).CO(y4p+w);
}
++rlp;
}
}
MV(MX LP=0;LP<(ze?1:2);LP++){
MS*AH*px=LP?pb:pa;AH AJ FZ=splits[LP];
#pragma GCC unroll 5
MV(MX r=0;r<5;r++){
MS*pr=px[r];
AH BC*l0=tf0lp0;AH BC*l1=tf1lp0;
MV(AJ w=0;w<cnt;w+=8){
BC v[16]={za,za,za,za,za,za,za,za,za,za,za,za,za,za,za,za};
#pragma GCC unroll 4
MV(MX k=0;k<4;k++){
v[k]=BC(ys[LP][k][r]+w);v[k+4]=BC(ys[LP][k+4][r]+w);v[k+8]=BC(ys[LP][k+8][r]+w);v[k+12]=BC(ys[LP][k+12][r]+w);
BC ww=l0->MT(tf0hi[k]),w2=ww.uS(),w3=ww.uC(w2);
CJ::LK(v[k].LG,v[k].LH,v[k+4].LG,v[k+4].LH,v[k+8].LG,v[k+8].LH,v[k+12].LG,v[k+12].LH);
v[k+4]=v[k+4].MT(w2);v[k+8]=v[k+8].MT(ww);v[k+12]=v[k+12].MT(w3);
}
BC ww=l1->MT(tf1hi),w2=ww.uS(),w3=ww.uC(w2);
#pragma GCC unroll 4
MV(MX q2=0;q2<4;q2++){
BC c0=v[4*q2],c1v=v[4*q2+1],c2v=v[4*q2+2],c3v=v[4*q2+3];
CJ::LK(c0 .LG,c0 .LH,c1v.LG,c1v.LH,c2v.LG,c2v.LH,c3v.LG,c3v.LH);
c1v=c1v.MT(w2);c2v=c2v.MT(ww);c3v=c3v.MT(w3);
AH AJ p=(AJ)(4*q2)*AU+j0+w;
if(r<2||(r==2&&p<FZ))c0 .CO(pr+p);zc c0 .DO(pr+p);
if(r<2||(r==2&&p+AU<FZ))c1v.CO(pr+p+AU);zc c1v.DO(pr+p+AU);
if(r<2||(r==2&&p+2*AU<FZ))c2v.CO(pr+p+2*AU);zc c2v.DO(pr+p+2*AU);
if(r<2||(r==2&&p+3*AU<FZ))c3v.CO(pr+p+3*AU);zc c3v.DO(pr+p+3*AU);
}
++l0;++l1;
}
}
}
}
FF();
MV(MX LP=0;LP<(ze?1:2);LP++){MS*AH*px=LP?pb:pa;MV(MX r=0;r<5;++r)MV(MX k=0;k<16;++k)CJ::EL<ED>(px[r]+(AJ)k*AU,AU);}
}zc{forward(pa,used_a);if(!ze)forward(pb,used_b);}
FJ(a,pb[0],DB,0.2);
if(DB/2>=(AJ(1)<<21)){
AH AJ AU=DB/16;
CG::fuse=KR;
MV(MX r=0;r<5;r++){
if(r>=3)IA;
CG::EU(a,pb,DB,IT,r);
AH MX m=5-r;
MV(MX LQ=0;LQ<16;LQ++){
CJ::EH<ED,ED>(a+r*DB+LQ*AU,AU);
if(r==1||r==2){
KL en0=CG::FC;
GM=KR;CG::FC=ED;
CJ::EH<ED,ED>(a+(AJ)m*DB+(AJ)(15-LQ)*AU,AU);
GM=ED;CG::FC=en0;
}
}
}
CG::fuse=ED;
CG::FC=ED;
AH AJ conv=used_a+used_b-1;
AH AJ last_live=conv>=4*DB?MP::min(DB,(conv-4*DB+7)&~AJ(7)):DB;
AL AJ SL=32,TS=40;
GR(64)MS KU[80][TS];
AH KO&t0=CJ::BZ[CW(DB/2)];
AH KO&t1=CJ::BZ[CW(DB/8)];
MV(AJ IK=0;IK<AU;IK+=SL){
AH AJ KC=MP::min(SL,AU-IK);
AH AJ bj=IK>>3;
AH BC*t1lp0=t1 .JC()+(bj&t1 .KE);
BC t1hi(za);{AH LX*hp=t1 .HE()+(bj>>t1 .LJ);AH MS*q=AN<AH MS*>(hp);t1hi.JR(q,q+1);}
AH BC*t0lp0=t0 .JC()+(bj&t0 .KE);
AH AJ t0hstep=(AU>>3)>>t0 .LJ;
BC t0hi[4]={za,za,za,za};
MV(MX q=0;q<4;q++){AH LX*hp=t0 .HE()+(bj>>t0 .LJ)+(AJ)q*t0hstep;AH MS*hq=AN<AH MS*>(hp);t0hi[q].JR(hq,hq+1);}
AH BC*rlow0=KF.JC()+(bj&BM<6>::KE);
AH AJ rhbase=(bj>>BM<6>::LJ),rhstep=(AU>>3)>>BM<6>::LJ;
MV(MX r=0;r<5;r++){
MS*p=a+r*DB;
AH BC*t1lp=t1lp0;AH BC*t0lp=t0lp0;
MV(AJ k=0;k<KC;k+=8){
AH AJ j=IK+k;
if(j>=64&&j+416<AU)MV(MX q=0;q<16;q++)AP((AH KV*)(p+(AJ)q*AU+j-64+32*q),AW);
BC v[16]={za,za,za,za,za,za,za,za,za,za,za,za,za,za,za,za};
AH BC w=t1lp->MT(t1hi),w2=w.uS(),w3=w.uC(w2);++t1lp;
#pragma GCC unroll 4
MV(MX q=0;q<4;q++){
BC c0=p+(4*q)*AU+j,c1=p+(4*q+1)*AU+j,c2=p+(4*q+2)*AU+j,c3=p+(4*q+3)*AU+j;
c1=c1 .BT(w2);c2=c2 .BT(w);c3=c3 .BT(w3);
CJ::KB(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
v[4*q]=c0;v[4*q+1]=c1;v[4*q+2]=c2;v[4*q+3]=c3;
}
#pragma GCC unroll 4
MV(MX q=0;q<4;q++){
AH BC z=t0lp->MT(t0hi[q]),z2=z.uS(),z3=z.uC(z2);
BC c0=v[q],c1=v[q+4].BT(z2),c2=v[q+8].BT(z),c3=v[q+12].BT(z3);
CJ::KB(c0 .LG,c0 .LH,c1 .LG,c1 .LH,c2 .LG,c2 .LH,c3 .LG,c3 .LH);
c0 .CO(KU[16*r+q]+k);c1 .CO(KU[16*r+q+4]+k);c2 .CO(KU[16*r+q+8]+k);c3 .CO(KU[16*r+q+12]+k);
}
++t0lp;
}
}
MV(MX LQ=0;LQ<16;LQ++){
AH BC*rlp=rlow0;
BC rhi(za);{AH LX*hp=KF.HE()+rhbase+(AJ)LQ*rhstep;AH MS*hq=AN<AH MS*>(hp);rhi.JR(hq,hq+1);}
MV(AJ k=0;k<KC;k+=8){
AH AJ j=LQ*AU+IK+k;
BC w=rlp->MT(rhi),w2=w.uS(),w3=w.uC(w2),w4=w2.uS();++rlp;
BC x0=KU[LQ]+k,x1=BC(KU[16+LQ]+k).BT(w),x2=BC(KU[32+LQ]+k).BT(w2),
x3=BC(KU[48+LQ]+k).BT(w3),x4=BC(KU[64+LQ]+k).BT(w4);
BC sum1=x1+x4,sum2=x2+x3,diff1=x1-x4,diff2=x2-x3;
BC HL=x0-(sum1+sum2)*CQ(0.25);
BC HM=(sum1-sum2)*CQ(0.55901699437494742410229341718282);
BC LO=(diff1+diff2)*s2;
BC t1=HL+HM,t2=HL-HM;
BC u1=posI(LO+diff1*CQ(0.36327126400268044294773337874031));
BC u2=posI(LO-diff2*CQ(1.5388417685876267012851452880185));
zb(x0+sum1+sum2,j);
zb(t1+u1,DB+j);
zb(t2+u2,2*DB+j);
zb(t2-u2,3*DB+j);
if(j<last_live)zb(t1-u1,4*DB+j);
}
}
}
}zc{
MV(MX r=0;r<5;++r){
CG::EU(a,pb,DB,IT,r);
CJ::EH<ED,ED>(a+r*DB,DB);
}
CG::FC=ED;
MV(AJ j=0;j<DB;j+=8){
if(__builtin_expect(j+496<DB,1)){
AP((AH KV*)(a+j+256),AW);
AP((AH KV*)(a+DB+j+316),AW);
AP((AH KV*)(a+2*DB+j+376),AW);
AP((AH KV*)(a+3*DB+j+436),AW);
AP((AH KV*)(a+4*DB+j+496),AW);
}
BC w=KF[j/8],w2=w.uS(),w3=w.uC(w2),w4=w2.uS();
BC x0=a+j,x1=BC(a+DB+j).BT(w),x2=BC(a+2*DB+j).BT(w2),
x3=BC(a+3*DB+j).BT(w3),x4=BC(a+4*DB+j).BT(w4);
BC sum1=x1+x4,sum2=x2+x3,diff1=x1-x4,diff2=x2-x3;
BC HL=x0-(sum1+sum2)*CQ(0.25);
BC HM=(sum1-sum2)*CQ(0.55901699437494742410229341718282);
BC LO=(diff1+diff2)*s2;
BC t1=HL+HM,t2=HL-HM;
BC u1=posI(LO+diff1*CQ(0.36327126400268044294773337874031));
BC u2=posI(LO-diff2*CQ(1.5388417685876267012851452880185));
zb(x0+sum1+sum2,j);
zb(t1+u1,DB+j);
zb(t2+u2,2*DB+j);
zb(t2-u2,3*DB+j);
zb(t1-u1,4*DB+j);
}
}
}
}}}
DM LB{DM IB{DM fft{
AK KK real_conv5(MS*a,MS*b,AJ IT,AJ na,AJ nb){MV(AX r=0;r<5;++r)g_bch[r]=b+r*(IT/5);latest_real_conv5(a,b,IT,na,nb);}
}}}
#pragma once
#include <algorithm>
#include <cstdint>
#include <cmath>
#include <immintrin.h>
DM coarse_fft{
AL DC P=DC(2013265921)*1866465281;
AL AX SCALE=256;
KK correct(AX n,zg zh*pa,zg zh*pb,AX*c,AX KV*IU,bool minus,AX*WS){
AL AX JW=10485760;
AJ root_itmax=5*MP::max<AJ>(4096,LB::int_ceil2((2*AJ(JW)+4)/5));EC*A=(EC*)WS;EC*B=A+root_itmax;
MV(AX y=0;y<n;y+=JW)MV(AX x=0;x<n-y;x+=JW){
AX II=n-x-y,na=MP::min({JW,n-x,II}),nb=MP::min({JW,n-y,II});
AJ IT=5*MP::max<AJ>(4096,LB::int_ceil2((2*AJ(MP::max(na,nb))+4)/5));
ze=(y==0&&x==JW&&IT==root_itmax);
ar_in_a=pa+(minus?n-x-na:x);ar_na=na;ar_reverse_a=minus;ar_in_b=pb+y;ar_nb=nb;
ar_final_c=c;ar_final_alpha=IU;ar_rev=minus;
LB::IB::fft::real_conv5(A,B+256,IT,na,nb);
}
}
}
#pragma once
#include <immintrin.h>
#include <cstdint>
#include <cstring>
BR KK initialize_crt4(AX n,AX*c,AX KV*IU,AH AX*grid,AX rowLength,AX AU,AH AX*hg,AH AX*sa,AH AX*sb,KL rev){
AH CD pd=BS(1866465281.),ip=BS(1./1866465281.),iProduct=BS(1./(2013265921. *1866465281.));
AH EM LM=FD(),pp=CX(CF(DC(2013265921)*1866465281));
AX* __restrict cq=c;AX KV* __restrict iq=IU;AH AX* __restrict gq=grid;
#define CRT4(LY,R2,KX,DST) do{\
EM r1=ER(LY,CX(0x7fffffff));\
CD xx=_mm256_cvtepi32_pd(r1),yy=_mm256_cvtepi32_pd(R2);\
CD s0=EO(xx,yy);\
CD t1=CV(s0,BS(8137.)),t2=CV(s0,BS(4694.));\
CD u1=EO(t1,CV(_mm256_round_pd(CV(t1,ip),_MM_FROUND_TO_NEAREST_INT|_MM_FROUND_NO_EXC),pd));\
CD u2=EO(t2,CV(_mm256_round_pd(CV(t2,ip),_MM_FROUND_TO_NEAREST_INT|_MM_FROUND_NO_EXC),pd));\
CD dd=DE(CV(u1,BS(32768.)),u2);\
CD qr=_mm256_round_pd(CV(dd,ip),_MM_FROUND_TO_NEAREST_INT|_MM_FROUND_NO_EXC);\
CD tt=EO(dd,CV(qr,pd));\
tt=DE(tt,_mm256_and_pd(_mm256_cmp_pd(tt,_mm256_setzero_pd(),_CMP_LT_OQ),pd));\
EM ti=_mm256_cvtpd_epi32(tt);\
CD fr=DE(CV(tt,ip),CV(xx,iProduct));\
EM q=_mm256_cvtpd_epi32(CV(fr,BS(-256.)));\
EM KD=GV(r1,_mm_mullo_epi32(ti,CX(2013265921)));\
KD=_mm_sub_epi32(KD,ER(_mm_cmpgt_epi32(LM,q),pp));\
KD=GV(KD,ER(LY,CX(MX(0x80000000u))));\
q=ER(q,CX(255));q=_mm_packus_epi32(q,LM);q=_mm_packus_epi16(q,LM);\
CF bt=CF(_mm_cvtsi128_si32(q));GW(iq+(KX),&bt,4);DST=KD;\
}while(0)
AH AX* gp=gq;AH AX*hp=hg;AX cl=0;AB JP=BB();
MV(AX k=0;k<n;k+=8){
AB x=AO(DU(sa,k),DU(sb,k));
x=AO(x,BY(x,4));x=AO(x,BY(x,8));
AB lower=BE(x,AF(3));
x=AO(x,AT(BB(),lower,0xf0));x=AO(x,JP);
JP=BE(x,AF(7));
AB cv=CS(_mm256_loadu_si256((AH AB*)(hp+cl)),FB(x,31));
EM LA=_mm256_castsi256_si128(cv),LB=_mm256_extracti128_si256(cv,1);
EM RA=FS((AH EM*)(gp+cl)),RB=FS((AH EM*)(gp+cl+4));
EM vlo,vhi;CRT4(LA,RA,k,vlo);CRT4(LB,RB,k+4,vhi);AB vv=_mm256_setr_m128i(vlo,vhi);if(rev)vv=BE(vv,AY(7,6,5,4,3,2,1,0));_mm256_stream_si256((AB*)(cq+(rev?(n-8-k):k)),vv);
cl+=8;if(cl==rowLength){cl=0;gp+=AU;hp+=AU;}
}
_mm_sfence();
#undef CRT4
}
AK KK exact_convolution(AH AX*a,AH AX*b,AX*c,KL minus){
AL AX n=zl;
AL AX p1=2013265921,p2=1866465281;
KO va=[&](AX i)->AX{
BD a[minus?n-1-i:i];
};
KO vb=[&](AX i)->AX{
BD b[i];
};
AX*w=DT;AX KV*IU=DT;
if(posix_memalign((KK**)&w,64,FW*4)||posix_memalign((KK**)&IU,64,n))zq();
GD(a,b,c,w,p1,31,KR,KR,minus);
GD(a,b,c,w,p2,3,ED,KR,minus);
initialize_crt4(n,c,IU,AOUT,NC_,CSX_,Aarr,a,b,minus);
coarse_fft::correct(n,a,b,c,IU,minus,w);
/* M2/M3: mirrored stores, NT output store; workspace left mapped (process exits) */
}
KK convolution(AX n,AH AX*a,AH AX*b,AX*c){assert(n==zl);exact_convolution(a,b,c,ED);}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 904.916 ms | 375 MB + 640 KB | Accepted | Score: 100 | 显示更多 |