/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171684 (Accepted 903.753 ms) and its parent 171614 (913.902 ms) supply the live-prefix engine and the paired5x16 2M coarse-root gate; our own 171530 supplies the prior PLUS10M radix5 engine. Adopted verbatim below with no edit to any computation. All original authors, source URLs and the complete HintFFT MIT notice are retained.
Purpose / 试验目的: bank the rival's two verified mechanisms against our 916,302.955 ms body -- (a) live-final radix-8 pruning of the natural-output row inverse, (b) the paired5x16 root-fusion gate at 2M complex points. Five full10M exact outputs and the64 output guards unchanged. */
/* 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 / 思路: The final CRT reads only coefficients0..9999999, hence rows0..1953 of the5120-column inverse grid. Stop final scatter before wholly dead row groups, retaining the final eight-row group through1959; all transform inputs and internal rows remain complete. Combine that removed write traffic with exact Barrett exponentiation, eight independent inverse-root chains and periodically reseeded long-double coarse roots sampled into lower levels. Preserve the full radix5 transform and every correction/output bound.
Experiment purpose / 试验目的: Five complete10M independent three-prime patterns, thirteen direct coefficients each, input hashes and64output guards before official measurement; no local timing gate. */
/* Idea / 思路: At the natural-output row inverse only, retain all dependencies through the first nine bits, then specialize the final radix8 pass to its1960 live low outputs. Compute the first three512-output sums and424 values of the fourth; omit the four high-output differences and their stores. Every input still participates through the first two local butterfly layers.1954rows cover all10M coefficients, and the extra six retain the existing eight-row scatter. All other row inverses remain complete. Experiment purpose: five full10M independent exact outputs, thirteen direct coefficients/input preservation/64guards before official timing of removed dead inverse arithmetic and memory writes. */
/* 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);}
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.MT(FH), c1 = c1.MT(HG); \
c3 = c3.MT(HG.MT(FH)); \
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.MT(FH), c1 = c1.MT(HG); \
c3 = c3.MT(HG.MT(FH)); \
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.MT(FH), c1 = c1.BT(HG); \
c3 = c3.BT(HG.MT(FH)); \
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.MT(w),w3=w2 .MT(w);
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.MT(w),w3=w2 .MT(w);
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.MT(w);
c2=c2 .MT(w);c1=c1 .MT(w2);c3=c3 .MT(w2 .MT(w));
A[k2][0]=c0;A[k2][1]=c1;A[k2][2]=c2;A[k2][3]=c3;
}
AH BC wB=TB[j0>>3],wB2=wB.MT(wB),wB3=wB2 .MT(wB);
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.MT(w),w3=w2 .MT(w),w4=w2 .MT(w2);
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.MT(ww),w3=w2 .MT(ww),w4=w2 .MT(w2);
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.MT(ww),w3=w2 .MT(ww);
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.MT(ww),w3=w2 .MT(ww);
#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=64;
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.MT(ww),w3=w2 .MT(ww),w4=w2 .MT(w2);
#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.MT(ww),w3=w2 .MT(ww);
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.MT(ww),w3=w2 .MT(ww);
#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.MT(w),w3=w2 .MT(w);++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.MT(z),z3=z2 .MT(z);
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.MT(w),w3=w2 .MT(w),w4=w2 .MT(w2);++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.MT(w),w3=w2 .MT(w),w4=w2 .MT(w2);
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 | 915.913 ms | 375 MB + 560 KB | Accepted | Score: 100 | 显示更多 |