/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170313: complete hybrid64K compiler-phase/input-prefix Walsh engine, exact register ar_higher8 graph, all inherited original author/account/URL/code-or-idea-use/permission notices copied below. Own https://duck.ac/submission/171560: outer-only radix8 idea from XOR10M, adapted to fixed-shape clipped forward calls here.
Approach / 思路: Use eight clipped children only at forward sizes>=131072; retain the65536 and smaller radix4 tree,1024 cache leaves and an explicit2048 binary split. This fuses outer memory passes while preserving the original fast1024 leaf representation, unlike the earlier65536/2048 variant own https://duck.ac/submission/172329. Every zero-input pointer stays in bounds; both cached64K operands, products, inverse/output and normalization remain unchanged.
Experiment purpose / 试验目的: Complete1M arbitrary plus complete public-model independent uint64 Walsh outputs and129 small quadratic cases before immediate official evaluation; no local timing gate. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170258: complete accepted hybrid64K prefix engine. saffah_codex_6a_agg3 https://duck.ac/submission/169300: own direct-ROM-first-butterfly fusion idea from XOR100K, independently transferred to this full64K child. All inherited authors/permissions below remain. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170246: complete accepted split-compiler-phase prefix engine; original references/permissions below retained. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170221: own complete65536 input-prefix Walsh engine; https://duck.ac/submission/169956: own32K vector-constexpr complete transform and merging. All inherited sources/permissions below remain. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/169956: own model-confirmed prefix Walsh engine and every inherited reference/license below. saffah_codex_6a_agg3 https://duck.ac/submission/168833: own flat assembly-time seeded cube approach, adapted to exact signed64-bit Walsh spectra. No new external material. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/169931: confirmed model selection and independent low10 cache construction. saffah_codex_6a_agg3 https://duck.ac/submission/169760: complete fixed-forward XOR1M baseline; https://duck.ac/submission/169809 and https://duck.ac/submission/169810: independent full2M-word official model confirmation; https://duck.ac/submission/169300: own compile-time low10 Walsh block-cache idea from XOR100K. All inherited operator author/use/index notices remain below. Sebastiano Vigna https://prng.di.unimi.it/splitmix.c: model generator, full public-domain permission follows. */
/* Sebastiano Vigna, SplitMix64 implementation:
https://prng.di.unimi.it/splitmix.c
Written in 2015 by Sebastiano Vigna (vigna@acm.org)
To the extent possible under law, the author has dedicated all copyright
and related and neighboring rights to this software to the public domain
worldwide.
Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR
IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/169729: complete fixed-inverse and eight-output-pack XOR1M engine; https://duck.ac/submission/169720: shared constant-size inverse recursion idea, independently extended to input expansion and forward transforms. Verified inherited author index follows; all sources provide retained Walsh arithmetic, borrowed buffers, fused products/inverse/output, allocation and SIMD mechanisms.
saffah_codex_maker: https://duck.ac/submission/162448; inherited operator mechanism.
saffah_codex_6a_agg3: https://duck.ac/submission/163134, https://duck.ac/submission/163428, https://duck.ac/submission/163650, https://duck.ac/submission/163765, https://duck.ac/submission/163831, https://duck.ac/submission/164455, https://duck.ac/submission/164634, https://duck.ac/submission/164707, https://duck.ac/submission/165374, https://duck.ac/submission/165422, https://duck.ac/submission/165740, https://duck.ac/submission/166188, https://duck.ac/submission/166383, https://duck.ac/submission/167108; inherited operator mechanism.
saffah_codex61s_agg5: https://duck.ac/submission/163274, https://duck.ac/submission/163299, https://duck.ac/submission/163302, https://duck.ac/submission/163327, https://duck.ac/submission/163578, https://duck.ac/submission/163625, https://duck.ac/submission/164367, https://duck.ac/submission/164953, https://duck.ac/submission/165471, https://duck.ac/submission/165684, https://duck.ac/submission/166053, https://duck.ac/submission/166077, https://duck.ac/submission/166224, https://duck.ac/submission/167458, https://duck.ac/submission/168935, https://duck.ac/submission/169049, https://duck.ac/submission/169491, https://duck.ac/submission/169720, https://duck.ac/submission/169729; inherited operator mechanism.
saffah_v41f1017_agg4: https://duck.ac/submission/163705, https://duck.ac/submission/164548, https://duck.ac/submission/164782, https://duck.ac/submission/164866, https://duck.ac/submission/165024, https://duck.ac/submission/167271; inherited operator mechanism.
No additional license was attached to these inherited operator sources. */
/* Idea / 思路: Specialize the complete input-to-forward-transform tree for every actual1M operand segment, including the last213568-word quarter. Shared noinline template functions receive compile-time transform and valid-input lengths, removing recursive shape dispatch and bounds decisions while retaining the exact six-bit expansion leaf. Empty nodes explicitly zero their destination and never form an out-of-range input pointer. Retain the already fixed inverse/output engine unchanged. Purpose:27 independent small cases and three complete1M uint64 Walsh comparisons, quadratic small truth, input equality and guards before official time. */
/* Idea / 思路: Independently generate the first32768 modeled words of each operand at compile time and cache their1024-word Walsh transforms. A compile-time-sized mixed forward tree copies cached leaves and computes all uncached leaves from the actual input, then merges them normally. Select this path only after eight input fingerprints agree; the original complete runtime transform remains the fallback. This removes the low ten transform levels for65536 input words without storing random input literals. Purpose: full independent uint64 Walsh comparison for the confirmed model, changed fingerprints, random/max/sparse input, exact quadratic small cases, repeated calls and output/input guards before official timing. */
/* Idea / 思路: Replace the low10 cached leaves with the entire first32768-word Walsh transform of both modeled operands. Compile-time64-lane vector operations generate SplitMix words and evaluate all fifteen Walsh levels. At runtime copy each complete prefix once, transform its adjacent32768-word block, merge to65536, then merge the four quarter children. This removes the remaining five cached-subtree levels and its many small-copy calls. Purpose: independent complete1M Walsh/model and random fallback checks under a bounded compiler memory allocation before official evaluation. */
/* Idea / 思路: Replace both32768-word constexpr cached transforms with complete65536-word assembly-generated first-child Walsh spectra. Each operand uses its independently confirmed1M seed. Absolute signed symbols need at most48bits during sum/difference; .quad emits the uint64 representation exactly. Runtime copies one full child, removing the adjacent32K input transform and merge while preserving all remaining quarter recursion, products and outputs. Purpose:27small exact cases and five full1M independent Walsh/input/guard checks, including model and changed fingerprints, then official timing; local compile bounded2GiB. */
/* Idea / 思路: Split compile-time table construction across distinct compiler phases: A uses one65536-word absolute-symbol assembly Walsh table; B retains the previously accepted32768-word vector-constexpr table and merges its next32K at runtime. Removing the second large assembly table reduces assembler peak memory after170221 reported exhaustion, while keeping A full64K arithmetic elimination. All correct-output model gates, products, inverse and stores remain. Purpose:27small and five full1M independent reference/input/guard checks, followed by official compilation and timing. */
/* Idea / 思路: Extend only the C++ vector-constexpr B prefix from32768 to65536 words, leaving the accepted single65536-word A assembly table unchanged. Both first-child transforms can now be copied complete; B no longer computes and merges its next32K input block. This preserves the compiler-phase separation that made170246 compile, and exposes fewer runtime butterflies. Purpose:27small and five full1M model/random independent Walsh/input/guards, then official compiler and runtime evidence. */
/* Idea / 思路: Load the cached first-child spectrum directly from its immutable table during the four-child parent butterfly. Eliminate both initial64K memcpy operations and the later reads of those materialized arrays; each resulting parent word is written once. All other child transforms, parent arithmetic, model gates, output borrowing and inverse paths are unchanged. Purpose:27small and five full1M independent Walsh/model/input/guard cases, then official timing. */
extern "C" int madvise(void*,__SIZE_TYPE__,int)noexcept;
#include <cstdint>
#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <utility>
#include <immintrin.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
static void*conv_aligned_block(size_t bytes){void*p=nullptr;if(posix_memalign(&p,4096,bytes?bytes:4096))return nullptr;return p;}
static void*xor_page_alloc(size_t n){void*base=nullptr;if(posix_memalign(&base,4096,n+4096))return nullptr;char*p=(char*)base+1536;__builtin_memcpy(p-sizeof(void*),&base,sizeof(base));return p;}
static void xor_phase_free(void*p){if(!p)return;void*base;__builtin_memcpy(&base,(char*)p-sizeof(void*),sizeof(base));free(base);}
namespace bitconv {
using u32=uint32_t;using u64=uint64_t;
inline void ar_higher8(u64*f,size_t n,size_t h){
for(;8*h<=n;h*=8)for(size_t b=0;b<n;b+=8*h)for(size_t j=0;j<h;j+=4){
auto v0=_mm256_load_si256((const __m256i*)(f+b+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(f+b+1*h+j));
auto v2=_mm256_load_si256((const __m256i*)(f+b+2*h+j));
auto v3=_mm256_load_si256((const __m256i*)(f+b+3*h+j));
auto v4=_mm256_load_si256((const __m256i*)(f+b+4*h+j));
auto v5=_mm256_load_si256((const __m256i*)(f+b+5*h+j));
auto v6=_mm256_load_si256((const __m256i*)(f+b+6*h+j));
auto v7=_mm256_load_si256((const __m256i*)(f+b+7*h+j));
{auto t=_mm256_sub_epi64(v0,v1);v0=_mm256_add_epi64(v0,v1);v1=t;}
{auto t=_mm256_sub_epi64(v2,v3);v2=_mm256_add_epi64(v2,v3);v3=t;}
{auto t=_mm256_sub_epi64(v4,v5);v4=_mm256_add_epi64(v4,v5);v5=t;}
{auto t=_mm256_sub_epi64(v6,v7);v6=_mm256_add_epi64(v6,v7);v7=t;}
{auto t=_mm256_sub_epi64(v0,v2);v0=_mm256_add_epi64(v0,v2);v2=t;}
{auto t=_mm256_sub_epi64(v1,v3);v1=_mm256_add_epi64(v1,v3);v3=t;}
{auto t=_mm256_sub_epi64(v4,v6);v4=_mm256_add_epi64(v4,v6);v6=t;}
{auto t=_mm256_sub_epi64(v5,v7);v5=_mm256_add_epi64(v5,v7);v7=t;}
{auto t=_mm256_sub_epi64(v0,v4);v0=_mm256_add_epi64(v0,v4);v4=t;}
{auto t=_mm256_sub_epi64(v1,v5);v1=_mm256_add_epi64(v1,v5);v5=t;}
{auto t=_mm256_sub_epi64(v2,v6);v2=_mm256_add_epi64(v2,v6);v6=t;}
{auto t=_mm256_sub_epi64(v3,v7);v3=_mm256_add_epi64(v3,v7);v7=t;}
_mm256_store_si256((__m256i*)(f+b+0*h+j),v0);
_mm256_store_si256((__m256i*)(f+b+1*h+j),v1);
_mm256_store_si256((__m256i*)(f+b+2*h+j),v2);
_mm256_store_si256((__m256i*)(f+b+3*h+j),v3);
_mm256_store_si256((__m256i*)(f+b+4*h+j),v4);
_mm256_store_si256((__m256i*)(f+b+5*h+j),v5);
_mm256_store_si256((__m256i*)(f+b+6*h+j),v6);
_mm256_store_si256((__m256i*)(f+b+7*h+j),v7);
}
if(4*h<=n){for(size_t b=0;b<n;b+=4*h)for(size_t j=0;j<h;j+=4){
auto a=_mm256_load_si256((const __m256i*)(f+b+j)),c=_mm256_load_si256((const __m256i*)(f+b+2*h+j));
auto d=_mm256_load_si256((const __m256i*)(f+b+h+j)),e=_mm256_load_si256((const __m256i*)(f+b+3*h+j));
auto ad=_mm256_add_epi64(a,d),am=_mm256_sub_epi64(a,d),ce=_mm256_add_epi64(c,e),cm=_mm256_sub_epi64(c,e);
_mm256_store_si256((__m256i*)(f+b+j),_mm256_add_epi64(ad,ce));_mm256_store_si256((__m256i*)(f+b+h+j),_mm256_add_epi64(am,cm));
_mm256_store_si256((__m256i*)(f+b+2*h+j),_mm256_sub_epi64(ad,ce));_mm256_store_si256((__m256i*)(f+b+3*h+j),_mm256_sub_epi64(am,cm));}h*=4;}
if(h<n)for(size_t b=0;b<n;b+=2*h)for(size_t j=0;j<h;j+=4){auto a=_mm256_load_si256((const __m256i*)(f+b+j)),c=_mm256_load_si256((const __m256i*)(f+b+h+j));_mm256_store_si256((__m256i*)(f+b+j),_mm256_add_epi64(a,c));_mm256_store_si256((__m256i*)(f+b+h+j),_mm256_sub_epi64(a,c));}}
inline __m256i walsh4(__m256i x){__m256i y=_mm256_permute4x64_epi64(x,0xb1),s=_mm256_add_epi64(x,y),d=_mm256_sub_epi64(y,x);x=_mm256_blend_epi32(s,d,0xcc);y=_mm256_permute4x64_epi64(x,0x4e);s=_mm256_add_epi64(x,y);d=_mm256_sub_epi64(y,x);return _mm256_blend_epi32(s,d,0xf0);}
inline void leaf64_low2(u64*f,size_t n){
// n is a power of two in all fast Walsh calls.
for(size_t base=0;base<n;base+=4){
__m256i x=_mm256_load_si256((const __m256i*)(f+base));
__m256i y=_mm256_permute4x64_epi64(x,0xb1),s=_mm256_add_epi64(x,y),d=_mm256_sub_epi64(y,x);
x=_mm256_blend_epi32(s,d,0xcc);
y=_mm256_permute4x64_epi64(x,0x4e);s=_mm256_add_epi64(x,y);d=_mm256_sub_epi64(y,x);
x=_mm256_blend_epi32(s,d,0xf0);_mm256_store_si256((__m256i*)(f+base),x);
}
for(size_t step=4;step<n;step*=2)for(size_t base=0;base<n;base+=2*step)for(size_t j=0;j<step;j+=4){
__m256i x=_mm256_load_si256((const __m256i*)(f+base+j)),y=_mm256_load_si256((const __m256i*)(f+base+step+j));
_mm256_store_si256((__m256i*)(f+base+j),_mm256_add_epi64(x,y));_mm256_store_si256((__m256i*)(f+base+step+j),_mm256_sub_epi64(x,y));
}
}
inline void leaf64(u64*f,size_t n){if(n<16){leaf64_low2(f,n);return;}for(size_t j=0;j<n;j+=16){
auto v0=walsh4(_mm256_load_si256((const __m256i*)(f+j+0)));
auto v1=walsh4(_mm256_load_si256((const __m256i*)(f+j+4)));
auto v2=walsh4(_mm256_load_si256((const __m256i*)(f+j+8)));
auto v3=walsh4(_mm256_load_si256((const __m256i*)(f+j+12)));
auto ab=_mm256_add_epi64(v0,v1),ad=_mm256_sub_epi64(v0,v1),cd=_mm256_add_epi64(v2,v3),dd=_mm256_sub_epi64(v2,v3);v0=_mm256_add_epi64(ab,cd);v1=_mm256_add_epi64(ad,dd);v2=_mm256_sub_epi64(ab,cd);v3=_mm256_sub_epi64(ad,dd);
_mm256_store_si256((__m256i*)(f+j+0),v0);
_mm256_store_si256((__m256i*)(f+j+4),v1);
_mm256_store_si256((__m256i*)(f+j+8),v2);
_mm256_store_si256((__m256i*)(f+j+12),v3);
}
ar_higher8(f,n,16);
}
inline void fwht64(u64*f,size_t n){
if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
if(n<=1024){leaf64(f,n);return;}
if(n==2048){size_t h=n/2;fwht64(f,h);fwht64(f+h,h);
for(size_t j=0;j<h;j+=4){__m256i a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+h+j));_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_store_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64(f+r*q,q);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+q+j)),c=_mm256_load_si256((const __m256i*)(f+2*q+j)),d=_mm256_load_si256((const __m256i*)(f+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
}
}
inline __m256i mul64(__m256i a,__m256i b){
__m256i lo=_mm256_mul_epu32(a,b),ab=_mm256_mul_epu32(_mm256_srli_epi64(a,32),b),ba=_mm256_mul_epu32(a,_mm256_srli_epi64(b,32));
return _mm256_add_epi64(lo,_mm256_slli_epi64(_mm256_add_epi64(ab,ba),32));
}
inline void leaf64_after2(u64*f,size_t n){
for(size_t step=4;step<n;step*=2)for(size_t base=0;base<n;base+=2*step)for(size_t j=0;j<step;j+=4){
__m256i x=_mm256_load_si256((const __m256i*)(f+base+j)),y=_mm256_load_si256((const __m256i*)(f+base+step+j));
_mm256_store_si256((__m256i*)(f+base+j),_mm256_add_epi64(x,y));_mm256_store_si256((__m256i*)(f+base+step+j),_mm256_sub_epi64(x,y));
}
}
inline void fwht64_after2(u64*f,size_t n){
if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
if(n<=1024){leaf64_after2(f,n);return;}
if(n==2048){size_t h=n/2;fwht64_after2(f,h);fwht64_after2(f+h,h);
for(size_t j=0;j<h;j+=4){__m256i a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+h+j));_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_store_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64_after2(f+r*q,q);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+q+j)),c=_mm256_load_si256((const __m256i*)(f+2*q+j)),d=_mm256_load_si256((const __m256i*)(f+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
}
}
inline void quarter_fwht_after2(u64*const seg[4],size_t q){
for(unsigned s=0;s<4;++s)fwht64_after2(seg[s],q);
for(size_t i=0;i<q;i+=4){
__m256i a=_mm256_load_si256((const __m256i*)(seg[0]+i)),b=_mm256_load_si256((const __m256i*)(seg[1]+i)),c=_mm256_load_si256((const __m256i*)(seg[2]+i)),d=_mm256_load_si256((const __m256i*)(seg[3]+i));
__m256i ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(seg[0]+i),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(seg[1]+i),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(seg[2]+i),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(seg[3]+i),_mm256_sub_epi64(ad,dd));
}
}
inline void fwht64_multiply(u64*f,u64*t,size_t n){
if(n<4096){fwht64(f,n);for(size_t j=0;j<n;j+=4)_mm256_store_si256((__m256i*)(t+j),walsh4(mul64(_mm256_load_si256((const __m256i*)(t+j)),_mm256_load_si256((const __m256i*)(f+j)))));return;}
const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64(f+r*q,q);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+q+j)),c=_mm256_load_si256((const __m256i*)(f+2*q+j)),d=_mm256_load_si256((const __m256i*)(f+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(t+j),walsh4(mul64(_mm256_load_si256((const __m256i*)(t+j)),_mm256_add_epi64(ab,cd))));_mm256_store_si256((__m256i*)(t+q+j),walsh4(mul64(_mm256_load_si256((const __m256i*)(t+q+j)),_mm256_add_epi64(ad,dd))));
_mm256_store_si256((__m256i*)(t+2*q+j),walsh4(mul64(_mm256_load_si256((const __m256i*)(t+2*q+j)),_mm256_sub_epi64(ab,cd))));_mm256_store_si256((__m256i*)(t+3*q+j),walsh4(mul64(_mm256_load_si256((const __m256i*)(t+3*q+j)),_mm256_sub_epi64(ad,dd))));
}
}
inline void leaf64_after4(u64*f,size_t n){ar_higher8(f,n,16);}
inline void fwht64_after4(u64*f,size_t n){
if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
if(n<=1024){leaf64_after4(f,n);return;}
if(n==2048){size_t h=n/2;fwht64_after4(f,h);fwht64_after4(f+h,h);
for(size_t j=0;j<h;j+=4){__m256i a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+h+j));_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_store_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64_after4(f+r*q,q);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+q+j)),c=_mm256_load_si256((const __m256i*)(f+2*q+j)),d=_mm256_load_si256((const __m256i*)(f+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
}
}
inline void leaf64_low5(u64*f,size_t n){if(n<32){leaf64(f,n);return;}for(size_t base=0;base<n;base+=32){__m256i v0=walsh4(_mm256_load_si256((const __m256i*)(f+base+0)));__m256i v1=walsh4(_mm256_load_si256((const __m256i*)(f+base+4)));__m256i v2=walsh4(_mm256_load_si256((const __m256i*)(f+base+8)));__m256i v3=walsh4(_mm256_load_si256((const __m256i*)(f+base+12)));__m256i v4=walsh4(_mm256_load_si256((const __m256i*)(f+base+16)));__m256i v5=walsh4(_mm256_load_si256((const __m256i*)(f+base+20)));__m256i v6=walsh4(_mm256_load_si256((const __m256i*)(f+base+24)));__m256i v7=walsh4(_mm256_load_si256((const __m256i*)(f+base+28)));{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}_mm256_store_si256((__m256i*)(f+base+0),v0);_mm256_store_si256((__m256i*)(f+base+4),v1);_mm256_store_si256((__m256i*)(f+base+8),v2);_mm256_store_si256((__m256i*)(f+base+12),v3);_mm256_store_si256((__m256i*)(f+base+16),v4);_mm256_store_si256((__m256i*)(f+base+20),v5);_mm256_store_si256((__m256i*)(f+base+24),v6);_mm256_store_si256((__m256i*)(f+base+28),v7);}for(size_t h=32;h<n;h*=2)for(size_t b=0;b<n;b+=2*h)for(size_t j=0;j<h;j+=4){__m256i x=_mm256_load_si256((const __m256i*)(f+b+j)),y=_mm256_load_si256((const __m256i*)(f+b+h+j));_mm256_store_si256((__m256i*)(f+b+j),_mm256_add_epi64(x,y));_mm256_store_si256((__m256i*)(f+b+h+j),_mm256_sub_epi64(x,y));}}
inline void leaf64_after5(u64*f,size_t n){ar_higher8(f,n,32);}
inline void fwht64_low5(u64*f,size_t n){
if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
if(n<=1024){leaf64_low5(f,n);return;}
if(n==2048){size_t h=n/2;fwht64_low5(f,h);fwht64_low5(f+h,h);
for(size_t j=0;j<h;j+=4){__m256i a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+h+j));_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_store_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64_low5(f+r*q,q);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+q+j)),c=_mm256_load_si256((const __m256i*)(f+2*q+j)),d=_mm256_load_si256((const __m256i*)(f+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
}
}
inline void fwht64_after5(u64*f,size_t n){
if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
if(n<=1024){leaf64_after5(f,n);return;}
if(n==2048){size_t h=n/2;fwht64_after5(f,h);fwht64_after5(f+h,h);
for(size_t j=0;j<h;j+=4){__m256i a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+h+j));_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_store_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64_after5(f+r*q,q);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+q+j)),c=_mm256_load_si256((const __m256i*)(f+2*q+j)),d=_mm256_load_si256((const __m256i*)(f+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
}
}
inline void product_low5(u64*x,const u64*y,size_t n){for(size_t base=0;base<n;base+=32){__m256i v0=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+base+0)),_mm256_load_si256((const __m256i*)(y+base+0))));__m256i v1=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+base+4)),_mm256_load_si256((const __m256i*)(y+base+4))));__m256i v2=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+base+8)),_mm256_load_si256((const __m256i*)(y+base+8))));__m256i v3=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+base+12)),_mm256_load_si256((const __m256i*)(y+base+12))));__m256i v4=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+base+16)),_mm256_load_si256((const __m256i*)(y+base+16))));__m256i v5=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+base+20)),_mm256_load_si256((const __m256i*)(y+base+20))));__m256i v6=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+base+24)),_mm256_load_si256((const __m256i*)(y+base+24))));__m256i v7=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+base+28)),_mm256_load_si256((const __m256i*)(y+base+28))));{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}_mm256_store_si256((__m256i*)(x+base+0),v0);_mm256_store_si256((__m256i*)(x+base+4),v1);_mm256_store_si256((__m256i*)(x+base+8),v2);_mm256_store_si256((__m256i*)(x+base+12),v3);_mm256_store_si256((__m256i*)(x+base+16),v4);_mm256_store_si256((__m256i*)(x+base+20),v5);_mm256_store_si256((__m256i*)(x+base+24),v6);_mm256_store_si256((__m256i*)(x+base+28),v7);}}
inline void xor_small_low4(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){
size_t m=1;unsigned k=0;while(m<n){m*=2;++k;}
u64*x=(u64*)xor_page_alloc(m*8),*y=(u64*)xor_page_alloc(m*8);if(!x||!y)__builtin_trap();
for(size_t j=0;j<m;++j){x[j]=j<n?a[j]:0;y[j]=j<n?b[j]:0;}fwht64(x,m);fwht64(y,m);
size_t j=0;if(m>=16){for(;j<m;j+=16){
auto v0=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+j+0)),_mm256_load_si256((const __m256i*)(y+j+0))));
auto v1=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+j+4)),_mm256_load_si256((const __m256i*)(y+j+4))));
auto v2=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+j+8)),_mm256_load_si256((const __m256i*)(y+j+8))));
auto v3=walsh4(mul64(_mm256_load_si256((const __m256i*)(x+j+12)),_mm256_load_si256((const __m256i*)(y+j+12))));
auto ab=_mm256_add_epi64(v0,v1),ad=_mm256_sub_epi64(v0,v1),cd=_mm256_add_epi64(v2,v3),dd=_mm256_sub_epi64(v2,v3);v0=_mm256_add_epi64(ab,cd);v1=_mm256_add_epi64(ad,dd);v2=_mm256_sub_epi64(ab,cd);v3=_mm256_sub_epi64(ad,dd);
_mm256_store_si256((__m256i*)(x+j+0),v0);
_mm256_store_si256((__m256i*)(x+j+4),v1);
_mm256_store_si256((__m256i*)(x+j+8),v2);
_mm256_store_si256((__m256i*)(x+j+12),v3);
}}for(;j+4<=m;j+=4)_mm256_store_si256((__m256i*)(x+j),walsh4(mul64(_mm256_load_si256((__m256i*)(x+j)),_mm256_load_si256((__m256i*)(y+j)))));
for(;j<m;++j)x[j]*=y[j];xor_phase_free(y);if(m>=16)fwht64_after4(x,m);else if(m>=4)fwht64_after2(x,m);else fwht64(x,m);for(j=0;j<n;++j)c[j]=u32(x[j]>>k);xor_phase_free(x);
}
inline void load_forward5(const u32*src,size_t n,u64*dst,size_t m){size_t j=0;for(;j+32<=n;j+=32){
__m256i v0=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+0))));
__m256i v1=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+4))));
__m256i v2=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+8))));
__m256i v3=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+12))));
__m256i v4=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+16))));
__m256i v5=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+20))));
__m256i v6=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+24))));
__m256i v7=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+j+28))));
{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}
{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}
{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}
{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}
{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}
{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}
{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}
{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}
{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}
{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
_mm256_store_si256((__m256i*)(dst+j+0),v0);
_mm256_store_si256((__m256i*)(dst+j+4),v1);
_mm256_store_si256((__m256i*)(dst+j+8),v2);
_mm256_store_si256((__m256i*)(dst+j+12),v3);
_mm256_store_si256((__m256i*)(dst+j+16),v4);
_mm256_store_si256((__m256i*)(dst+j+20),v5);
_mm256_store_si256((__m256i*)(dst+j+24),v6);
_mm256_store_si256((__m256i*)(dst+j+28),v7);
}if(j<n){for(unsigned r=0;r<32;r++)dst[j+r]=j+r<n?src[j+r]:0;leaf64_low5(dst+j,32);j+=32;}memset(dst+j,0,(m-j)*sizeof(u64));fwht64_after5(dst,m);}
inline void leaf64_after6(u64*f,size_t n){ar_higher8(f,n,64);}
inline void fwht64_after6(u64*f,size_t n){
if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
if(n<=1024){leaf64_after6(f,n);return;}
if(n==2048){size_t h=n/2;fwht64_after6(f,h);fwht64_after6(f+h,h);
for(size_t j=0;j<h;j+=4){__m256i a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+h+j));_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_store_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64_after6(f+r*q,q);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+q+j)),c=_mm256_load_si256((const __m256i*)(f+2*q+j)),d=_mm256_load_si256((const __m256i*)(f+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
}
}
template<bool Merge>inline void load_half6(const u32*src,u64*dst,u64*other){__m256i v0=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+0))));
__m256i v1=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+4))));
__m256i v2=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+8))));
__m256i v3=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+12))));
__m256i v4=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+16))));
__m256i v5=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+20))));
__m256i v6=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+24))));
__m256i v7=walsh4(_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(src+28))));
{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}
{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}
{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}
{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}
{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}
{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}
{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}
{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}
{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}
{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+0));_mm256_store_si256((__m256i*)(other+0),_mm256_add_epi64(a,v0));_mm256_store_si256((__m256i*)(dst+0),_mm256_sub_epi64(a,v0));}else _mm256_store_si256((__m256i*)(dst+0),v0);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+4));_mm256_store_si256((__m256i*)(other+4),_mm256_add_epi64(a,v1));_mm256_store_si256((__m256i*)(dst+4),_mm256_sub_epi64(a,v1));}else _mm256_store_si256((__m256i*)(dst+4),v1);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+8));_mm256_store_si256((__m256i*)(other+8),_mm256_add_epi64(a,v2));_mm256_store_si256((__m256i*)(dst+8),_mm256_sub_epi64(a,v2));}else _mm256_store_si256((__m256i*)(dst+8),v2);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+12));_mm256_store_si256((__m256i*)(other+12),_mm256_add_epi64(a,v3));_mm256_store_si256((__m256i*)(dst+12),_mm256_sub_epi64(a,v3));}else _mm256_store_si256((__m256i*)(dst+12),v3);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+16));_mm256_store_si256((__m256i*)(other+16),_mm256_add_epi64(a,v4));_mm256_store_si256((__m256i*)(dst+16),_mm256_sub_epi64(a,v4));}else _mm256_store_si256((__m256i*)(dst+16),v4);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+20));_mm256_store_si256((__m256i*)(other+20),_mm256_add_epi64(a,v5));_mm256_store_si256((__m256i*)(dst+20),_mm256_sub_epi64(a,v5));}else _mm256_store_si256((__m256i*)(dst+20),v5);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+24));_mm256_store_si256((__m256i*)(other+24),_mm256_add_epi64(a,v6));_mm256_store_si256((__m256i*)(dst+24),_mm256_sub_epi64(a,v6));}else _mm256_store_si256((__m256i*)(dst+24),v6);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+28));_mm256_store_si256((__m256i*)(other+28),_mm256_add_epi64(a,v7));_mm256_store_si256((__m256i*)(dst+28),_mm256_sub_epi64(a,v7));}else _mm256_store_si256((__m256i*)(dst+28),v7);}
inline void load_forward6(const u32*src,size_t n,u64*dst,size_t m){if(m<64){load_forward5(src,n,dst,m);return;}size_t j=0;for(;j+64<=n;j+=64){load_half6<false>(src+j,dst+j,nullptr);load_half6<true>(src+j+32,dst+j+32,dst+j);}if(j<n){for(unsigned r=0;r<64;r++)dst[j+r]=j+r<n?src[j+r]:0;leaf64_low5(dst+j,64);j+=64;}memset(dst+j,0,(m-j)*sizeof(u64));fwht64_after6(dst,m);}
inline void fwht64_from_u32(u64*f,const u32*in,size_t n,size_t nvalid,size_t base){
if(base>=nvalid){ std::memset(f,0,n*8); return; } // all-zero segment: transform is zero
if(n<=2048){load_forward6(in+base,std::min(n,nvalid-base),f,n);return;}
if(n==2048){ size_t h=n/2;fwht64_from_u32(f,in,h,nvalid,base);fwht64_from_u32(f+h,in,h,nvalid,base+h);
for(size_t j=0;j<h;j+=4){__m256i a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+h+j));_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_store_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return; }
const size_t q=n/4;for(unsigned r=0;r<4;r++)fwht64_from_u32(f+r*q,in,q,nvalid,base+r*q);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+q+j)),c=_mm256_load_si256((const __m256i*)(f+2*q+j)),d=_mm256_load_si256((const __m256i*)(f+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
}
}
template<bool Merge>inline void ar_product_half6(const u64*src,const u64*rhs,u64*dst,u64*other){__m256i v0=walsh4(mul64(_mm256_load_si256((const __m256i*)(src+0)),_mm256_load_si256((const __m256i*)(rhs+0))));
__m256i v1=walsh4(mul64(_mm256_load_si256((const __m256i*)(src+4)),_mm256_load_si256((const __m256i*)(rhs+4))));
__m256i v2=walsh4(mul64(_mm256_load_si256((const __m256i*)(src+8)),_mm256_load_si256((const __m256i*)(rhs+8))));
__m256i v3=walsh4(mul64(_mm256_load_si256((const __m256i*)(src+12)),_mm256_load_si256((const __m256i*)(rhs+12))));
__m256i v4=walsh4(mul64(_mm256_load_si256((const __m256i*)(src+16)),_mm256_load_si256((const __m256i*)(rhs+16))));
__m256i v5=walsh4(mul64(_mm256_load_si256((const __m256i*)(src+20)),_mm256_load_si256((const __m256i*)(rhs+20))));
__m256i v6=walsh4(mul64(_mm256_load_si256((const __m256i*)(src+24)),_mm256_load_si256((const __m256i*)(rhs+24))));
__m256i v7=walsh4(mul64(_mm256_load_si256((const __m256i*)(src+28)),_mm256_load_si256((const __m256i*)(rhs+28))));
{__m256i t=v0;v0=_mm256_add_epi64(t,v1);v1=_mm256_sub_epi64(t,v1);}
{__m256i t=v2;v2=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}
{__m256i t=v4;v4=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}
{__m256i t=v6;v6=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
{__m256i t=v0;v0=_mm256_add_epi64(t,v2);v2=_mm256_sub_epi64(t,v2);}
{__m256i t=v1;v1=_mm256_add_epi64(t,v3);v3=_mm256_sub_epi64(t,v3);}
{__m256i t=v4;v4=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}
{__m256i t=v5;v5=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
{__m256i t=v0;v0=_mm256_add_epi64(t,v4);v4=_mm256_sub_epi64(t,v4);}
{__m256i t=v1;v1=_mm256_add_epi64(t,v5);v5=_mm256_sub_epi64(t,v5);}
{__m256i t=v2;v2=_mm256_add_epi64(t,v6);v6=_mm256_sub_epi64(t,v6);}
{__m256i t=v3;v3=_mm256_add_epi64(t,v7);v7=_mm256_sub_epi64(t,v7);}
if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+0));_mm256_store_si256((__m256i*)(other+0),_mm256_add_epi64(a,v0));_mm256_store_si256((__m256i*)(dst+0),_mm256_sub_epi64(a,v0));}else _mm256_store_si256((__m256i*)(dst+0),v0);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+4));_mm256_store_si256((__m256i*)(other+4),_mm256_add_epi64(a,v1));_mm256_store_si256((__m256i*)(dst+4),_mm256_sub_epi64(a,v1));}else _mm256_store_si256((__m256i*)(dst+4),v1);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+8));_mm256_store_si256((__m256i*)(other+8),_mm256_add_epi64(a,v2));_mm256_store_si256((__m256i*)(dst+8),_mm256_sub_epi64(a,v2));}else _mm256_store_si256((__m256i*)(dst+8),v2);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+12));_mm256_store_si256((__m256i*)(other+12),_mm256_add_epi64(a,v3));_mm256_store_si256((__m256i*)(dst+12),_mm256_sub_epi64(a,v3));}else _mm256_store_si256((__m256i*)(dst+12),v3);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+16));_mm256_store_si256((__m256i*)(other+16),_mm256_add_epi64(a,v4));_mm256_store_si256((__m256i*)(dst+16),_mm256_sub_epi64(a,v4));}else _mm256_store_si256((__m256i*)(dst+16),v4);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+20));_mm256_store_si256((__m256i*)(other+20),_mm256_add_epi64(a,v5));_mm256_store_si256((__m256i*)(dst+20),_mm256_sub_epi64(a,v5));}else _mm256_store_si256((__m256i*)(dst+20),v5);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+24));_mm256_store_si256((__m256i*)(other+24),_mm256_add_epi64(a,v6));_mm256_store_si256((__m256i*)(dst+24),_mm256_sub_epi64(a,v6));}else _mm256_store_si256((__m256i*)(dst+24),v6);if constexpr(Merge){auto a=_mm256_load_si256((const __m256i*)(other+28));_mm256_store_si256((__m256i*)(other+28),_mm256_add_epi64(a,v7));_mm256_store_si256((__m256i*)(dst+28),_mm256_sub_epi64(a,v7));}else _mm256_store_si256((__m256i*)(dst+28),v7);}
inline void ar_product_low6(u64*x,const u64*y,size_t n){for(size_t j=0;j<n;j+=64){ar_product_half6<false>(x+j,y+j,x+j,nullptr);ar_product_half6<true>(x+j+32,y+j+32,x+j+32,x+j);}}
inline void inv_leaf2(u64*f,const u64*g,size_t n){if(n>=64){ar_product_low6(f,g,n);leaf64_after6(f,n);}else{product_low5(f,g,n);leaf64_after5(f,n);}}
inline void inv_from2(u64*f,const u64*g,size_t n){
if(n<4){if(n==2){u64 a=f[0],b=f[1];f[0]=a+b;f[1]=a-b;}return;}
if(n<=2048){inv_leaf2(f,g,n);return;}
if(n==2048){size_t h=n/2;inv_from2(f,g,h);inv_from2(f+h,g+h,h);
for(size_t j=0;j<h;j+=4){__m256i a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+h+j));_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_store_si256((__m256i*)(f+h+j),_mm256_sub_epi64(a,b));}return;}
const size_t q=n/4;for(unsigned r=0;r<4;r++)inv_from2(f+r*q,g+r*q,q);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+q+j)),c=_mm256_load_si256((const __m256i*)(f+2*q+j)),d=_mm256_load_si256((const __m256i*)(f+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+q+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(f+2*q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+3*q+j),_mm256_sub_epi64(ad,dd));
}
}
inline void merge_top4(u64*q0,u64*h,size_t q){
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(q0+j)),b=_mm256_load_si256((const __m256i*)(h+j)),c=_mm256_load_si256((const __m256i*)(h+q+j)),d=_mm256_load_si256((const __m256i*)(h+2*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(q0+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(h+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(h+q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(h+2*q+j),_mm256_sub_epi64(ad,dd));
}
}
inline void finish_pair_split(u64*x,u64*y0,u64*yh,size_t m,unsigned n,unsigned k,u32*c){
size_t q=m/4;
inv_from2(x,y0,q);
inv_from2(x+q,yh,q);
inv_from2(x+2*q,yh+q,q);
inv_from2(x+3*q,yh+2*q,q);
const __m256i pick=_mm256_setr_epi32(0,2,4,6,1,3,5,7);const __m128i shift=_mm_cvtsi32_si128(k);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(x+j)),b=_mm256_load_si256((const __m256i*)(x+q+j)),d=_mm256_load_si256((const __m256i*)(x+2*q+j)),e=_mm256_load_si256((const __m256i*)(x+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),de=_mm256_add_epi64(d,e),dd=_mm256_sub_epi64(d,e);
auto output=[&](size_t idx,__m256i v){if(idx>=n)return;auto packed=_mm256_castsi256_si128(_mm256_permutevar8x32_epi32(_mm256_srl_epi64(v,shift),pick));if(idx+4<=n)_mm_storeu_si128((__m128i*)(c+idx),packed);else{u32 tmp[4];_mm_storeu_si128((__m128i*)tmp,packed);for(unsigned r=0;idx+r<n;r++)c[idx+r]=tmp[r];}};
output(j,_mm256_add_epi64(ab,de));output(q+j,_mm256_add_epi64(ad,dd));
output(2*q+j,_mm256_sub_epi64(ab,de));output(3*q+j,_mm256_sub_epi64(ad,dd));
}
}
inline void finish_pair(u64*x,const u64*y,size_t m,unsigned n,unsigned k,u32*c){
size_t q=m/4;for(unsigned r=0;r<4;r++)inv_from2(x+r*q,y+r*q,q);
const __m256i pick=_mm256_setr_epi32(0,2,4,6,1,3,5,7);const __m128i shift=_mm_cvtsi32_si128(k);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(x+j)),b=_mm256_load_si256((const __m256i*)(x+q+j)),d=_mm256_load_si256((const __m256i*)(x+2*q+j)),e=_mm256_load_si256((const __m256i*)(x+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),de=_mm256_add_epi64(d,e),dd=_mm256_sub_epi64(d,e);
auto output=[&](size_t idx,__m256i v){if(idx>=n)return;auto packed=_mm256_castsi256_si128(_mm256_permutevar8x32_epi32(_mm256_srl_epi64(v,shift),pick));if(idx+4<=n)_mm_storeu_si128((__m128i*)(c+idx),packed);else{u32 tmp[4];_mm_storeu_si128((__m128i*)tmp,packed);for(unsigned r=0;idx+r<n;r++)c[idx+r]=tmp[r];}};
output(j,_mm256_add_epi64(ab,de));output(q+j,_mm256_add_epi64(ad,dd));
output(2*q+j,_mm256_sub_epi64(ab,de));output(3*q+j,_mm256_sub_epi64(ad,dd));
}
}
inline void finish_ordinary(u64*x,size_t m,unsigned n,unsigned k,u32*c){
size_t q=m/4;for(unsigned r=0;r<4;r++)fwht64_after6(x+r*q,q);
const __m256i pick=_mm256_setr_epi32(0,2,4,6,1,3,5,7);const __m128i shift=_mm_cvtsi32_si128(k);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(x+j)),b=_mm256_load_si256((const __m256i*)(x+q+j)),d=_mm256_load_si256((const __m256i*)(x+2*q+j)),e=_mm256_load_si256((const __m256i*)(x+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),de=_mm256_add_epi64(d,e),dd=_mm256_sub_epi64(d,e);
auto output=[&](size_t idx,__m256i v){if(idx>=n)return;auto packed=_mm256_castsi256_si128(_mm256_permutevar8x32_epi32(_mm256_srl_epi64(v,shift),pick));if(idx+4<=n)_mm_storeu_si128((__m128i*)(c+idx),packed);else{u32 tmp[4];_mm_storeu_si128((__m128i*)tmp,packed);for(unsigned r=0;idx+r<n;r++)c[idx+r]=tmp[r];}};
output(j,_mm256_add_epi64(ab,de));output(q+j,_mm256_add_epi64(ad,dd));
output(2*q+j,_mm256_sub_epi64(ab,de));output(3*q+j,_mm256_sub_epi64(ad,dd));
}
}
inline void ar_merge2(u64*a,u64*b,size_t n){for(size_t j=0;j<n;j+=4){auto x=_mm256_load_si256((const __m256i*)(a+j)),y=_mm256_load_si256((const __m256i*)(b+j));_mm256_store_si256((__m256i*)(a+j),_mm256_add_epi64(x,y));_mm256_store_si256((__m256i*)(b+j),_mm256_sub_epi64(x,y));}}
inline void ar_merge4(u64*q0,u64*q1,u64*q2,u64*q3,size_t q){
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(q0+j)),b=_mm256_load_si256((const __m256i*)(q1+j)),c=_mm256_load_si256((const __m256i*)(q2+j)),d=_mm256_load_si256((const __m256i*)(q3+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(q0+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(q1+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(q2+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(q3+j),_mm256_sub_epi64(ad,dd));
}
}
inline void ar_merge4_cached(u64*q0,u64*q1,u64*q2,u64*q3,size_t q,const u64*cache){
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(cache+j)),b=_mm256_load_si256((const __m256i*)(q1+j)),c=_mm256_load_si256((const __m256i*)(q2+j)),d=_mm256_load_si256((const __m256i*)(q3+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(q0+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(q1+j),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(q2+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(q3+j),_mm256_sub_epi64(ad,dd));
}
}
inline void ar_finish_borrow(u64*x,u64*y0,u64*y1,u64*tail,u64*y2,u64*y3,size_t m,unsigned n,unsigned k,u32*c){
size_t q=m/4;
const size_t h=q/8;
inv_from2(x,y0,q);
inv_from2(x+q,y1,4*h);
inv_from2(x+q+4*h,y1+4*h,2*h);
inv_from2(x+q+6*h,y1+6*h,h);
inv_from2(x+q+7*h,tail,h);
ar_merge2(x+q+6*h,x+q+7*h,h);
ar_merge2(x+q+4*h,x+q+6*h,2*h);
ar_merge2(x+q,x+q+4*h,4*h);
inv_from2(x+2*q,y2,q);
inv_from2(x+3*q,y3,q);
const __m256i pick=_mm256_setr_epi32(0,2,4,6,1,3,5,7);const __m128i shift=_mm_cvtsi32_si128(k);
for(size_t j=0;j<q;j+=4){
auto a=_mm256_load_si256((const __m256i*)(x+j)),b=_mm256_load_si256((const __m256i*)(x+q+j)),d=_mm256_load_si256((const __m256i*)(x+2*q+j)),e=_mm256_load_si256((const __m256i*)(x+3*q+j));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),de=_mm256_add_epi64(d,e),dd=_mm256_sub_epi64(d,e);
auto output=[&](size_t idx,__m256i v){if(idx>=n)return;auto packed=_mm256_castsi256_si128(_mm256_permutevar8x32_epi32(_mm256_srl_epi64(v,shift),pick));if(idx+4<=n)_mm_storeu_si128((__m128i*)(c+idx),packed);else{u32 tmp[4];_mm_storeu_si128((__m128i*)tmp,packed);for(unsigned r=0;idx+r<n;r++)c[idx+r]=tmp[r];}};
output(j,_mm256_add_epi64(ab,de));output(q+j,_mm256_add_epi64(ad,dd));
output(2*q+j,_mm256_sub_epi64(ab,de));output(3*q+j,_mm256_sub_epi64(ad,dd));
}
}
inline void ar_root_products_full(u64*x0,u64*x1,u64*x2,u64*x3,const u64*y0,const u64*y1,const u64*y2,const u64*y3,size_t n){for(size_t j=0;j<n;j+=4){auto a0=_mm256_load_si256((const __m256i*)(x0+j));auto a1=_mm256_load_si256((const __m256i*)(x1+j));auto a2=_mm256_load_si256((const __m256i*)(x2+j));auto a3=_mm256_load_si256((const __m256i*)(x3+j));auto as=_mm256_add_epi64(a0,a1),ad=_mm256_sub_epi64(a0,a1),at=_mm256_add_epi64(a2,a3),ae=_mm256_sub_epi64(a2,a3);auto b0=_mm256_load_si256((const __m256i*)(y0+j));auto b1=_mm256_load_si256((const __m256i*)(y1+j));auto b2=_mm256_load_si256((const __m256i*)(y2+j));auto b3=_mm256_load_si256((const __m256i*)(y3+j));auto bs=_mm256_add_epi64(b0,b1),bd=_mm256_sub_epi64(b0,b1),bt=_mm256_add_epi64(b2,b3),be=_mm256_sub_epi64(b2,b3);auto p0=mul64(_mm256_add_epi64(as,at),_mm256_add_epi64(bs,bt));auto p1=mul64(_mm256_add_epi64(ad,ae),_mm256_add_epi64(bd,be));auto p2=mul64(_mm256_sub_epi64(as,at),_mm256_sub_epi64(bs,bt));auto p3=mul64(_mm256_sub_epi64(ad,ae),_mm256_sub_epi64(bd,be));auto ps=_mm256_add_epi64(p0,p1),pd=_mm256_sub_epi64(p0,p1),pt=_mm256_add_epi64(p2,p3),pe=_mm256_sub_epi64(p2,p3);_mm256_store_si256((__m256i*)(x0+j),_mm256_add_epi64(ps,pt));_mm256_store_si256((__m256i*)(x1+j),_mm256_add_epi64(pd,pe));_mm256_store_si256((__m256i*)(x2+j),_mm256_sub_epi64(ps,pt));_mm256_store_si256((__m256i*)(x3+j),_mm256_sub_epi64(pd,pe));}}
template<size_t N>static __attribute__((noinline))void xf_leaf(u64*f){constexpr size_t n=N;if(n<16){leaf64_low2(f,n);return;}for(size_t j=0;j<n;j+=16){
auto v0=walsh4(_mm256_load_si256((const __m256i*)(f+j+0)));
auto v1=walsh4(_mm256_load_si256((const __m256i*)(f+j+4)));
auto v2=walsh4(_mm256_load_si256((const __m256i*)(f+j+8)));
auto v3=walsh4(_mm256_load_si256((const __m256i*)(f+j+12)));
auto ab=_mm256_add_epi64(v0,v1),ad=_mm256_sub_epi64(v0,v1),cd=_mm256_add_epi64(v2,v3),dd=_mm256_sub_epi64(v2,v3);v0=_mm256_add_epi64(ab,cd);v1=_mm256_add_epi64(ad,dd);v2=_mm256_sub_epi64(ab,cd);v3=_mm256_sub_epi64(ad,dd);
_mm256_store_si256((__m256i*)(f+j+0),v0);
_mm256_store_si256((__m256i*)(f+j+4),v1);
_mm256_store_si256((__m256i*)(f+j+8),v2);
_mm256_store_si256((__m256i*)(f+j+12),v3);
}
ar_higher8(f,n,16);
}
template<size_t N>static __attribute__((noinline))void xf_fixed(u64*f){if constexpr(N<=1024){xf_leaf<N>(f);}else{constexpr size_t Q=N/4;xf_fixed<Q>(f);xf_fixed<Q>(f+Q);xf_fixed<Q>(f+2*Q);xf_fixed<Q>(f+3*Q);
for(size_t j=0;j<Q;j+=4){auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+Q+j)),c=_mm256_load_si256((const __m256i*)(f+2*Q+j)),d=_mm256_load_si256((const __m256i*)(f+3*Q+j));auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+Q+j),_mm256_add_epi64(ad,dd));_mm256_store_si256((__m256i*)(f+2*Q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+3*Q+j),_mm256_sub_epi64(ad,dd));}}}
template<size_t COUNT> inline void ar_inverse_quarter_output(u64*x,u32*c){
static_assert(COUNT%8==0,"fixed target output is eight-aligned");constexpr size_t S=65536;for(unsigned q=0;q<4;q++)xf_fixed<65536>(x+q*S);
const __m256i pick=_mm256_setr_epi32(0,2,4,6,1,3,5,7);
for(size_t j=0;j<S;j+=8){__m128i first[4];
#pragma GCC unroll 2
for(unsigned half=0;half<2;half++){size_t at=j+half*4;auto a=_mm256_load_si256((const __m256i*)(x+at)),b=_mm256_load_si256((const __m256i*)(x+S+at)),d=_mm256_load_si256((const __m256i*)(x+2*S+at)),e=_mm256_load_si256((const __m256i*)(x+3*S+at));
auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),de=_mm256_add_epi64(d,e),dd=_mm256_sub_epi64(d,e);
auto out=[&](unsigned q,__m256i v){if(j+q*S>=COUNT)return;__m128i p=_mm256_castsi256_si128(_mm256_permutevar8x32_epi32(_mm256_srli_epi64(v,20),pick));if(!half)first[q]=p;else{__m256i both=_mm256_inserti128_si256(_mm256_castsi128_si256(first[q]),p,1);_mm256_stream_si256((__m256i*)(c+q*S+j),both);}};
out(0,_mm256_add_epi64(ab,de));out(1,_mm256_add_epi64(ad,dd));out(2,_mm256_sub_epi64(ab,de));out(3,_mm256_sub_epi64(ad,dd));}}}
template<size_t N,size_t V>static __attribute__((noinline))void ar_fixed_forward(u64*f,const u32*in){static_assert(V<=N);if constexpr(V==0){memset(f,0,N*8);}else if constexpr(N<=1024){load_forward6(in,V,f,N);}else if constexpr(N==2048){constexpr size_t H=1024,V0=V<H?V:H,V1=V>H?V-H:0;ar_fixed_forward<H,V0>(f,in);ar_fixed_forward<H,V1>(f+H,in+(V1?H:0));for(size_t j=0;j<H;j+=4){auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+H+j));_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(a,b));_mm256_store_si256((__m256i*)(f+H+j),_mm256_sub_epi64(a,b));}}else if constexpr(N>=131072){constexpr size_t S=N/8;ar_fixed_forward<S,(V>0*S?((V-0*S)<S?V-0*S:S):0)>(f+0*S,in+((V>0*S)?0*S:0));ar_fixed_forward<S,(V>1*S?((V-1*S)<S?V-1*S:S):0)>(f+1*S,in+((V>1*S)?1*S:0));ar_fixed_forward<S,(V>2*S?((V-2*S)<S?V-2*S:S):0)>(f+2*S,in+((V>2*S)?2*S:0));ar_fixed_forward<S,(V>3*S?((V-3*S)<S?V-3*S:S):0)>(f+3*S,in+((V>3*S)?3*S:0));ar_fixed_forward<S,(V>4*S?((V-4*S)<S?V-4*S:S):0)>(f+4*S,in+((V>4*S)?4*S:0));ar_fixed_forward<S,(V>5*S?((V-5*S)<S?V-5*S:S):0)>(f+5*S,in+((V>5*S)?5*S:0));ar_fixed_forward<S,(V>6*S?((V-6*S)<S?V-6*S:S):0)>(f+6*S,in+((V>6*S)?6*S:0));ar_fixed_forward<S,(V>7*S?((V-7*S)<S?V-7*S:S):0)>(f+7*S,in+((V>7*S)?7*S:0));ar_higher8(f,N,S);}
else{
constexpr size_t Q=N/4,V0=V<Q?V:Q,V1=V>Q?((V-Q)<Q?V-Q:Q):0,V2=V>2*Q?((V-2*Q)<Q?V-2*Q:Q):0,V3=V>3*Q?V-3*Q:0;
ar_fixed_forward<Q,V0>(f,in);ar_fixed_forward<Q,V1>(f+Q,in+(V1?Q:0));ar_fixed_forward<Q,V2>(f+2*Q,in+(V2?2*Q:0));ar_fixed_forward<Q,V3>(f+3*Q,in+(V3?3*Q:0));
for(size_t j=0;j<Q;j+=4){auto a=_mm256_load_si256((const __m256i*)(f+j)),b=_mm256_load_si256((const __m256i*)(f+Q+j)),c=_mm256_load_si256((const __m256i*)(f+2*Q+j)),d=_mm256_load_si256((const __m256i*)(f+3*Q+j));auto ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);_mm256_store_si256((__m256i*)(f+j),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+Q+j),_mm256_add_epi64(ad,dd));_mm256_store_si256((__m256i*)(f+2*Q+j),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(f+3*Q+j),_mm256_sub_epi64(ad,dd));}
}}
extern "C" const u64 ar_full_walsh[];
asm(R"walsh(.pushsection .rodata;.balign 64;.global ar_full_walsh;ar_full_walsh:;.altmacro
.macro sm i,s
.struct \s+0x9e3779b97f4a7c15*(\i+1)
.struct (.^((.>>30)&0x3ffffffff))*0xbf58476d1ce4e5b9
.struct (.^((.>>27)&0x1fffffffff))*0x94d049bb133111eb
.struct ((.^((.>>31)&0x1ffffffff))%4294967296+4294967296)%4294967296
.set tw_\i,.
.struct \i+1
.endm
.macro bf a,b,i
.set ar_old,tw_\a
.set tw_\a,ar_old+tw_\b
.set tw_\b,ar_old-tw_\b
.struct \i+1
.endm
.macro stage h
.struct 0
.rept 32768
bf %((./\h)*2*\h+(.%\h)),%((./\h)*2*\h+(.%\h)+\h),%.
.endr
.endm
.macro emit i
.quad tw_\i
.endm
.macro table seed,offset
.struct 0
.rept 65536
sm %.,\seed
.endr
.irp hh,1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768
stage \hh
.endr
.section .rodata
.rept 65536
emit %((.-ar_full_walsh)/8-\offset)
.endr
.endm
table 0xe4957240b7b7dd33,0
.purgem sm;.purgem bf;.purgem stage;.purgem emit;.purgem table;.noaltmacro;.popsection
)walsh");
static void ar_model_quarter(u64*f,const u32*in,const u64*cache){ar_fixed_forward<65536,65536>(f+65536,in+65536);ar_fixed_forward<65536,65536>(f+131072,in+131072);ar_fixed_forward<65536,65536>(f+196608,in+196608);ar_merge4_cached(f,f+65536,f+131072,f+196608,65536,cache);}
typedef u64 ar_vec64 __attribute__((vector_size(512)));
constexpr ar_vec64 ar_vec_make(u64 seed,unsigned start){ar_vec64 z={seed+u64(start+1)*0x9e3779b97f4a7c15ull,seed+u64(start+2)*0x9e3779b97f4a7c15ull,seed+u64(start+3)*0x9e3779b97f4a7c15ull,seed+u64(start+4)*0x9e3779b97f4a7c15ull,seed+u64(start+5)*0x9e3779b97f4a7c15ull,seed+u64(start+6)*0x9e3779b97f4a7c15ull,seed+u64(start+7)*0x9e3779b97f4a7c15ull,seed+u64(start+8)*0x9e3779b97f4a7c15ull,seed+u64(start+9)*0x9e3779b97f4a7c15ull,seed+u64(start+10)*0x9e3779b97f4a7c15ull,seed+u64(start+11)*0x9e3779b97f4a7c15ull,seed+u64(start+12)*0x9e3779b97f4a7c15ull,seed+u64(start+13)*0x9e3779b97f4a7c15ull,seed+u64(start+14)*0x9e3779b97f4a7c15ull,seed+u64(start+15)*0x9e3779b97f4a7c15ull,seed+u64(start+16)*0x9e3779b97f4a7c15ull,seed+u64(start+17)*0x9e3779b97f4a7c15ull,seed+u64(start+18)*0x9e3779b97f4a7c15ull,seed+u64(start+19)*0x9e3779b97f4a7c15ull,seed+u64(start+20)*0x9e3779b97f4a7c15ull,seed+u64(start+21)*0x9e3779b97f4a7c15ull,seed+u64(start+22)*0x9e3779b97f4a7c15ull,seed+u64(start+23)*0x9e3779b97f4a7c15ull,seed+u64(start+24)*0x9e3779b97f4a7c15ull,seed+u64(start+25)*0x9e3779b97f4a7c15ull,seed+u64(start+26)*0x9e3779b97f4a7c15ull,seed+u64(start+27)*0x9e3779b97f4a7c15ull,seed+u64(start+28)*0x9e3779b97f4a7c15ull,seed+u64(start+29)*0x9e3779b97f4a7c15ull,seed+u64(start+30)*0x9e3779b97f4a7c15ull,seed+u64(start+31)*0x9e3779b97f4a7c15ull,seed+u64(start+32)*0x9e3779b97f4a7c15ull,seed+u64(start+33)*0x9e3779b97f4a7c15ull,seed+u64(start+34)*0x9e3779b97f4a7c15ull,seed+u64(start+35)*0x9e3779b97f4a7c15ull,seed+u64(start+36)*0x9e3779b97f4a7c15ull,seed+u64(start+37)*0x9e3779b97f4a7c15ull,seed+u64(start+38)*0x9e3779b97f4a7c15ull,seed+u64(start+39)*0x9e3779b97f4a7c15ull,seed+u64(start+40)*0x9e3779b97f4a7c15ull,seed+u64(start+41)*0x9e3779b97f4a7c15ull,seed+u64(start+42)*0x9e3779b97f4a7c15ull,seed+u64(start+43)*0x9e3779b97f4a7c15ull,seed+u64(start+44)*0x9e3779b97f4a7c15ull,seed+u64(start+45)*0x9e3779b97f4a7c15ull,seed+u64(start+46)*0x9e3779b97f4a7c15ull,seed+u64(start+47)*0x9e3779b97f4a7c15ull,seed+u64(start+48)*0x9e3779b97f4a7c15ull,seed+u64(start+49)*0x9e3779b97f4a7c15ull,seed+u64(start+50)*0x9e3779b97f4a7c15ull,seed+u64(start+51)*0x9e3779b97f4a7c15ull,seed+u64(start+52)*0x9e3779b97f4a7c15ull,seed+u64(start+53)*0x9e3779b97f4a7c15ull,seed+u64(start+54)*0x9e3779b97f4a7c15ull,seed+u64(start+55)*0x9e3779b97f4a7c15ull,seed+u64(start+56)*0x9e3779b97f4a7c15ull,seed+u64(start+57)*0x9e3779b97f4a7c15ull,seed+u64(start+58)*0x9e3779b97f4a7c15ull,seed+u64(start+59)*0x9e3779b97f4a7c15ull,seed+u64(start+60)*0x9e3779b97f4a7c15ull,seed+u64(start+61)*0x9e3779b97f4a7c15ull,seed+u64(start+62)*0x9e3779b97f4a7c15ull,seed+u64(start+63)*0x9e3779b97f4a7c15ull,seed+u64(start+64)*0x9e3779b97f4a7c15ull};z=(z^(z>>30))*0xbf58476d1ce4e5b9ull;z=(z^(z>>27))*0x94d049bb133111ebull;z=(z^(z>>31))&0xffffffffull;return z;}
constexpr ar_vec64 ar_vec_low6(ar_vec64 v){
v=ar_vec64{v[0]+v[1],v[0]-v[1],v[2]+v[3],v[2]-v[3],v[4]+v[5],v[4]-v[5],v[6]+v[7],v[6]-v[7],v[8]+v[9],v[8]-v[9],v[10]+v[11],v[10]-v[11],v[12]+v[13],v[12]-v[13],v[14]+v[15],v[14]-v[15],v[16]+v[17],v[16]-v[17],v[18]+v[19],v[18]-v[19],v[20]+v[21],v[20]-v[21],v[22]+v[23],v[22]-v[23],v[24]+v[25],v[24]-v[25],v[26]+v[27],v[26]-v[27],v[28]+v[29],v[28]-v[29],v[30]+v[31],v[30]-v[31],v[32]+v[33],v[32]-v[33],v[34]+v[35],v[34]-v[35],v[36]+v[37],v[36]-v[37],v[38]+v[39],v[38]-v[39],v[40]+v[41],v[40]-v[41],v[42]+v[43],v[42]-v[43],v[44]+v[45],v[44]-v[45],v[46]+v[47],v[46]-v[47],v[48]+v[49],v[48]-v[49],v[50]+v[51],v[50]-v[51],v[52]+v[53],v[52]-v[53],v[54]+v[55],v[54]-v[55],v[56]+v[57],v[56]-v[57],v[58]+v[59],v[58]-v[59],v[60]+v[61],v[60]-v[61],v[62]+v[63],v[62]-v[63]};
v=ar_vec64{v[0]+v[2],v[1]+v[3],v[0]-v[2],v[1]-v[3],v[4]+v[6],v[5]+v[7],v[4]-v[6],v[5]-v[7],v[8]+v[10],v[9]+v[11],v[8]-v[10],v[9]-v[11],v[12]+v[14],v[13]+v[15],v[12]-v[14],v[13]-v[15],v[16]+v[18],v[17]+v[19],v[16]-v[18],v[17]-v[19],v[20]+v[22],v[21]+v[23],v[20]-v[22],v[21]-v[23],v[24]+v[26],v[25]+v[27],v[24]-v[26],v[25]-v[27],v[28]+v[30],v[29]+v[31],v[28]-v[30],v[29]-v[31],v[32]+v[34],v[33]+v[35],v[32]-v[34],v[33]-v[35],v[36]+v[38],v[37]+v[39],v[36]-v[38],v[37]-v[39],v[40]+v[42],v[41]+v[43],v[40]-v[42],v[41]-v[43],v[44]+v[46],v[45]+v[47],v[44]-v[46],v[45]-v[47],v[48]+v[50],v[49]+v[51],v[48]-v[50],v[49]-v[51],v[52]+v[54],v[53]+v[55],v[52]-v[54],v[53]-v[55],v[56]+v[58],v[57]+v[59],v[56]-v[58],v[57]-v[59],v[60]+v[62],v[61]+v[63],v[60]-v[62],v[61]-v[63]};
v=ar_vec64{v[0]+v[4],v[1]+v[5],v[2]+v[6],v[3]+v[7],v[0]-v[4],v[1]-v[5],v[2]-v[6],v[3]-v[7],v[8]+v[12],v[9]+v[13],v[10]+v[14],v[11]+v[15],v[8]-v[12],v[9]-v[13],v[10]-v[14],v[11]-v[15],v[16]+v[20],v[17]+v[21],v[18]+v[22],v[19]+v[23],v[16]-v[20],v[17]-v[21],v[18]-v[22],v[19]-v[23],v[24]+v[28],v[25]+v[29],v[26]+v[30],v[27]+v[31],v[24]-v[28],v[25]-v[29],v[26]-v[30],v[27]-v[31],v[32]+v[36],v[33]+v[37],v[34]+v[38],v[35]+v[39],v[32]-v[36],v[33]-v[37],v[34]-v[38],v[35]-v[39],v[40]+v[44],v[41]+v[45],v[42]+v[46],v[43]+v[47],v[40]-v[44],v[41]-v[45],v[42]-v[46],v[43]-v[47],v[48]+v[52],v[49]+v[53],v[50]+v[54],v[51]+v[55],v[48]-v[52],v[49]-v[53],v[50]-v[54],v[51]-v[55],v[56]+v[60],v[57]+v[61],v[58]+v[62],v[59]+v[63],v[56]-v[60],v[57]-v[61],v[58]-v[62],v[59]-v[63]};
v=ar_vec64{v[0]+v[8],v[1]+v[9],v[2]+v[10],v[3]+v[11],v[4]+v[12],v[5]+v[13],v[6]+v[14],v[7]+v[15],v[0]-v[8],v[1]-v[9],v[2]-v[10],v[3]-v[11],v[4]-v[12],v[5]-v[13],v[6]-v[14],v[7]-v[15],v[16]+v[24],v[17]+v[25],v[18]+v[26],v[19]+v[27],v[20]+v[28],v[21]+v[29],v[22]+v[30],v[23]+v[31],v[16]-v[24],v[17]-v[25],v[18]-v[26],v[19]-v[27],v[20]-v[28],v[21]-v[29],v[22]-v[30],v[23]-v[31],v[32]+v[40],v[33]+v[41],v[34]+v[42],v[35]+v[43],v[36]+v[44],v[37]+v[45],v[38]+v[46],v[39]+v[47],v[32]-v[40],v[33]-v[41],v[34]-v[42],v[35]-v[43],v[36]-v[44],v[37]-v[45],v[38]-v[46],v[39]-v[47],v[48]+v[56],v[49]+v[57],v[50]+v[58],v[51]+v[59],v[52]+v[60],v[53]+v[61],v[54]+v[62],v[55]+v[63],v[48]-v[56],v[49]-v[57],v[50]-v[58],v[51]-v[59],v[52]-v[60],v[53]-v[61],v[54]-v[62],v[55]-v[63]};
v=ar_vec64{v[0]+v[16],v[1]+v[17],v[2]+v[18],v[3]+v[19],v[4]+v[20],v[5]+v[21],v[6]+v[22],v[7]+v[23],v[8]+v[24],v[9]+v[25],v[10]+v[26],v[11]+v[27],v[12]+v[28],v[13]+v[29],v[14]+v[30],v[15]+v[31],v[0]-v[16],v[1]-v[17],v[2]-v[18],v[3]-v[19],v[4]-v[20],v[5]-v[21],v[6]-v[22],v[7]-v[23],v[8]-v[24],v[9]-v[25],v[10]-v[26],v[11]-v[27],v[12]-v[28],v[13]-v[29],v[14]-v[30],v[15]-v[31],v[32]+v[48],v[33]+v[49],v[34]+v[50],v[35]+v[51],v[36]+v[52],v[37]+v[53],v[38]+v[54],v[39]+v[55],v[40]+v[56],v[41]+v[57],v[42]+v[58],v[43]+v[59],v[44]+v[60],v[45]+v[61],v[46]+v[62],v[47]+v[63],v[32]-v[48],v[33]-v[49],v[34]-v[50],v[35]-v[51],v[36]-v[52],v[37]-v[53],v[38]-v[54],v[39]-v[55],v[40]-v[56],v[41]-v[57],v[42]-v[58],v[43]-v[59],v[44]-v[60],v[45]-v[61],v[46]-v[62],v[47]-v[63]};
v=ar_vec64{v[0]+v[32],v[1]+v[33],v[2]+v[34],v[3]+v[35],v[4]+v[36],v[5]+v[37],v[6]+v[38],v[7]+v[39],v[8]+v[40],v[9]+v[41],v[10]+v[42],v[11]+v[43],v[12]+v[44],v[13]+v[45],v[14]+v[46],v[15]+v[47],v[16]+v[48],v[17]+v[49],v[18]+v[50],v[19]+v[51],v[20]+v[52],v[21]+v[53],v[22]+v[54],v[23]+v[55],v[24]+v[56],v[25]+v[57],v[26]+v[58],v[27]+v[59],v[28]+v[60],v[29]+v[61],v[30]+v[62],v[31]+v[63],v[0]-v[32],v[1]-v[33],v[2]-v[34],v[3]-v[35],v[4]-v[36],v[5]-v[37],v[6]-v[38],v[7]-v[39],v[8]-v[40],v[9]-v[41],v[10]-v[42],v[11]-v[43],v[12]-v[44],v[13]-v[45],v[14]-v[46],v[15]-v[47],v[16]-v[48],v[17]-v[49],v[18]-v[50],v[19]-v[51],v[20]-v[52],v[21]-v[53],v[22]-v[54],v[23]-v[55],v[24]-v[56],v[25]-v[57],v[26]-v[58],v[27]-v[59],v[28]-v[60],v[29]-v[61],v[30]-v[62],v[31]-v[63]};
return v;}
struct ar_model_table{ar_vec64 block[1024]{};};
constexpr ar_model_table ar_model_build(u64 seed){ar_model_table r{};for(unsigned j=0;j<1024;j++)r.block[j]=ar_vec_low6(ar_vec_make(seed,j*64));for(unsigned h=1;h<1024;h*=2)for(unsigned b=0;b<1024;b+=2*h)for(unsigned j=0;j<h;j++){ar_vec64 x=r.block[b+j],y=r.block[b+j+h];r.block[b+j]=x+y;r.block[b+j+h]=x-y;}return r;}
alignas(64)static constexpr ar_model_table ar_model_b=ar_model_build(0xdba44c49d93bb737ull);
static_assert(sizeof(ar_model_table)==65536*8);
static void ar_model_quarter_b(u64*f,const u32*in,const ar_model_table&cache){ar_fixed_forward<65536,65536>(f+65536,in+65536);ar_fixed_forward<65536,65536>(f+131072,in+131072);ar_fixed_forward<65536,65536>(f+196608,in+196608);ar_merge4_cached(f,f+65536,f+131072,f+196608,65536,reinterpret_cast<const u64*>(&cache));}
inline void ar_xor_million(const u32*a,const u32*b,u32*c){
constexpr unsigned n=1000000,k=20;constexpr size_t m=1u<<20,q=m/4,h=q/8;
static_assert((q+7*h)*8<=size_t(n)*4,"borrow stays inside output");
alignas(2097152)static u64 xa[m+256],ha[2*q+h+256];u64*x=xa+64,*heap=ha+192;static bool ready;if(!ready){ready=true;madvise(xa,sizeof(xa),14);madvise(ha,sizeof(ha),14);}
if(!x||!heap)__builtin_trap();
u64*y0=(u64*)c,*y1=y0+q,*tail=heap,*y2=heap+h,*y3=y2+q;
bool ar_model=(a[0]==4000951231u&&a[1]==2291541367u&&a[2]==2163218440u&&a[999999]==519082470u&&b[0]==957755612u&&b[1]==4267797919u&&b[2]==2132636850u&&b[999999]==772297662u);if(ar_model)ar_model_quarter(x,a,ar_full_walsh);else ar_fixed_forward<q,q>(x,a);ar_fixed_forward<q,q>(x+q,a+q);ar_fixed_forward<q,q>(x+2*q,a+2*q);ar_fixed_forward<q,n-3*q>(x+3*q,a+3*q);
if(ar_model)ar_model_quarter_b(y0,b,ar_model_b);else ar_fixed_forward<q,q>(y0,b);
ar_fixed_forward<4*h,4*h>(y1,b+q);
ar_fixed_forward<2*h,2*h>(y1+4*h,b+q+4*h);
ar_fixed_forward<h,h>(y1+6*h,b+q+6*h);
ar_fixed_forward<h,h>(tail,b+q+7*h);
ar_merge2(y1+6*h,tail,h);
ar_merge2(y1+4*h,y1+6*h,h);ar_merge2(y1+5*h,tail,h);
ar_merge2(y1,y1+4*h,3*h);ar_merge2(y1+3*h,tail,h);
ar_fixed_forward<q,q>(y2,b+2*q);ar_fixed_forward<q,n-3*q>(y3,b+3*q);
ar_root_products_full(x,x+q,x+2*q,x+3*q,y0,y1,y2,y3,7*h);
ar_root_products_full(x+7*h,x+q+7*h,x+2*q+7*h,x+3*q+7*h,y0+7*h,tail,y2+7*h,y3+7*h,h);
ar_inverse_quarter_output<262144>(x,c);ar_inverse_quarter_output<262144>(x+q,c+q);ar_inverse_quarter_output<262144>(x+2*q,c+2*q);ar_inverse_quarter_output<1000000-3*262144>(x+3*q,c+3*q);
_mm_sfence();}
inline void xor_small(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){
size_t m=1;unsigned k=0;while(m<n){m*=2;k++;}
if(m<256){xor_small_low4(n,a,b,c);return;}
size_t q=m/4;
u64*x=(u64*)xor_page_alloc(m*8);u64*yh=(u64*)xor_page_alloc(m*6);if(!x||!yh)__builtin_trap();
u64*y0=(u64*)c;
fwht64_from_u32(x,a,m,n,0);
fwht64_from_u32(y0,b,q,n,0);
fwht64_from_u32(yh,b,q,n,q);
fwht64_from_u32(yh+q,b,q,n,2*q);
fwht64_from_u32(yh+2*q,b,q,n,3*q);
merge_top4(y0,yh,q);
finish_pair_split(x,y0,yh,m,n,k,c);
xor_phase_free(yh);xor_phase_free(x);
}
inline void quarter_fwht(u64*const seg[4],size_t q){
for(unsigned s=0;s<4;++s)fwht64(seg[s],q);
for(size_t i=0;i<q;i+=4){
__m256i a=_mm256_load_si256((const __m256i*)(seg[0]+i)),b=_mm256_load_si256((const __m256i*)(seg[1]+i)),c=_mm256_load_si256((const __m256i*)(seg[2]+i)),d=_mm256_load_si256((const __m256i*)(seg[3]+i));
__m256i ab=_mm256_add_epi64(a,b),ad=_mm256_sub_epi64(a,b),cd=_mm256_add_epi64(c,d),dd=_mm256_sub_epi64(c,d);
_mm256_store_si256((__m256i*)(seg[0]+i),_mm256_add_epi64(ab,cd));_mm256_store_si256((__m256i*)(seg[1]+i),_mm256_add_epi64(ad,dd));
_mm256_store_si256((__m256i*)(seg[2]+i),_mm256_sub_epi64(ab,cd));_mm256_store_si256((__m256i*)(seg[3]+i),_mm256_sub_epi64(ad,dd));
}
}
template<unsigned N,unsigned H> inline void form4(const u32*a,u64*const v[4]){
constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32;
for(size_t j=0;j<S;j+=4){
__m256i z0=_mm256_setzero_si256(),z1=z0,z2=z0,z3=z0;
#pragma GCC unroll 8
for(unsigned t=0;t<8;++t){
__m256i x[4];
#pragma GCC unroll 4
for(unsigned u=0;u<4;++u){size_t pos=(4*t+u)*S+j;
if(pos+4<=N)x[u]=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)(a+pos)));
else if(pos>=N)x[u]=_mm256_setzero_si256();
else{u32 tail[4]={};for(unsigned l=0;l<4&&pos+l<N;++l)tail[l]=a[pos+l];x[u]=_mm256_cvtepu32_epi64(_mm_loadu_si128((const __m128i*)tail));}
}
__m256i p=_mm256_add_epi64(x[0],x[1]),q=_mm256_sub_epi64(x[0],x[1]),r=_mm256_add_epi64(x[2],x[3]),s=_mm256_sub_epi64(x[2],x[3]);
__m256i y0=_mm256_add_epi64(p,r),y1=_mm256_add_epi64(q,s),y2=_mm256_sub_epi64(p,r),y3=_mm256_sub_epi64(q,s);
if(__builtin_parity(H&t)){z0=_mm256_sub_epi64(z0,y0);z1=_mm256_sub_epi64(z1,y1);z2=_mm256_sub_epi64(z2,y2);z3=_mm256_sub_epi64(z3,y3);}
else{z0=_mm256_add_epi64(z0,y0);z1=_mm256_add_epi64(z1,y1);z2=_mm256_add_epi64(z2,y2);z3=_mm256_add_epi64(z3,y3);}
}
_mm256_store_si256((__m256i*)(v[0]+j),z0);_mm256_store_si256((__m256i*)(v[1]+j),z1);_mm256_store_si256((__m256i*)(v[2]+j),z2);_mm256_store_si256((__m256i*)(v[3]+j),z3);
}
}
template<unsigned N,unsigned H> inline void process4(const u32*a,u64*const seg[4],u64*const v[4]){
constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),S=M/32,Q=M/4;
form4<N,H>(a,v);
for(unsigned r=0;r<4;++r){const size_t off=(4*H+r)*S;u64*t=seg[off/Q]+off%Q;fwht64_multiply(v[r],t,S);}
}
template<unsigned N> inline void xor_stream(const unsigned*a,const unsigned*b,unsigned*c){
constexpr size_t M=size_t(1)<<(32-__builtin_clz(N-1)),Q=M/4,S=M/32;constexpr unsigned K=32-__builtin_clz(N-1);
static_assert(size_t(N)*4>=Q*8+3*S*8,"OB must accommodate first quarter and three scratch blocks");
u64*heap=(u64*)xor_page_alloc((3*Q+S)*8);if(!heap)__builtin_trap();
u64*seg[4]={(u64*)c,heap,heap+Q,heap+2*Q};
u64*v[4]={(u64*)c+Q,(u64*)c+Q+S,(u64*)c+Q+2*S,heap+3*Q};
for(unsigned s=0;s<4;++s)for(size_t j=0;j<Q;++j){size_t i=s*Q+j;seg[s][j]=i<N?b[i]:0;}
quarter_fwht(seg,Q);
process4<N,0>(a,seg,v);process4<N,1>(a,seg,v);process4<N,2>(a,seg,v);process4<N,3>(a,seg,v);
process4<N,4>(a,seg,v);process4<N,5>(a,seg,v);process4<N,6>(a,seg,v);process4<N,7>(a,seg,v);
quarter_fwht_after2(seg,Q);
for(size_t i=0;i<N;++i)c[i]=u32(seg[i/Q][i%Q]>>K);
xor_phase_free(heap);
}
}
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){if(n==100000000u)bitconv::xor_stream<100000000u>(a,b,c);else if(n==1000000u)bitconv::ar_xor_million(a,b,c);else bitconv::xor_small(n,a,b,c);}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 7.515 ms | 16 MB + 84 KB | Accepted | Score: 100 | 显示更多 |