/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/172737: copied full q-first inverse/four64B-root/hybrid2NT OR100M engine, inherited accounts/URLs/uses/licences retained below. Own https://duck.ac/submission/172268: surrounding-loop64 alignment idea, independently applied to this scale and native body.
Approach / 思路: Align GCC9 native loop entries to64 bytes around the explicit root and recursive SIMD graphs. Keep all memory geometry, dataflow, transforms, direct/staged publication and valid tails identical; only actual native branch/loop layout changes.
Experiment purpose / 试验目的: Skip exact allocated-ELF/relocation/export equality with the accepted parent only. Different code receives full100M independent-zeta and129 quadratic proof then immediate official measurement; no local timing gate. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/172704: copied full q-first-inverse/single-scratch OR100M engine and inherited accounts/URLs/uses/licences below. Own https://duck.ac/submission/172680: four complete-line root factors and hybrid2-NT/6-staged mechanism, independently transposed to subset direction. Approach / 思路: Keep full64B donors in12/16 YMM for all four six/eight-plane root factors while preserving the latest q-first inverse order. Both eight-row passes directly NT-publish rows0/1, stage rows2..7, then drain each remaining row contiguously. Explicit last-input variants retain zero suffixes; unchanged row0 is still copied to its distinct NT destination. Preserve all partial guards, recursive kernels, row pitches and fences. Experiment purpose / 试验目的: Full100M independent-zeta/129 quadratic proof before prompt official measurement of the distinct schedule; no local timing gate. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/172192 complete current OR100M engine, adopted verbatim in every statement and constant; our own https://duck.ac/submission/172610 asymmetric top-octant staging tile. All inherited author/source/use/licence notices below are retained unchanged. Approach / 思路: ONE value-exact reordering of the final root inverse (the third phase of root8_wave). The 6-arm (q) and 8-octant (rr) Mobius factors commute over disjoint index bits, so the stage now inverts over q FIRST (6 values read at the 64 MiB arm stride) and over rr SECOND, publishing each q's eight contiguous 4 KiB output runs immediately. The previous order inverted rr first (8 values at the 1 MiB octant stride) and published per rr. Every butterfly, partial-arm guard (q<5||off<R), output address and non-temporal burst length is unchanged; only the order of the two commuting inverse factors and the publish grouping changes. Experiment purpose / 试验目的: judge-frame microbenchmark (duck.experience, the exact in-frame tile loop at 1/8 scale, 48 MiB, correct value gate against the shipped order) measured shipped 32,467 kt -> swapped 27,201 kt = -16.2 % with the value gate OK and a same-code control at +0.14 %; then this official timing. Local full-size FNV-1a over all 100,000,000 uint32 = 812ec556cabf1d91, identical to the adopted base. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/171733: complete current direct-unchanged-donor OR100M engine copied with every inherited original author/account/URL/use/licence notice below. Own https://duck.ac/submission/172069: copied16-YMM complete-line recursive graph and four-base/invariant-stride address mechanism, mirrored for subset direction. Approach / 思路: Mirror the eight recursive octants' physical addresses q to7-q, turning the accepted complete64B superset zeta/Mobius register graph into exact OR subset transforms. Keep all16 donor YMM halves until their changed full lines are stored; physical octant0 remains untouched. Four descending even bases share one negative byte stride. Preserve the original4096-item cache leaf, large top-pass guard, unchanged-donor root geometry and all partial paths. Experiment purpose / 试验目的: Full100M independent bottom-up modular-zeta and129 small quadratic outputs before prompt official measurement of this distinct recursive residency/address schedule; no local timing filter. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171584: complete current convore8 root/leaf/layout engine and staged top-octant transform, copied with every original author/account/URL/use/licence notice below. Required inherited notices are retained verbatim; no separate public Duck source licence is stated. Approach / 思路: Octant0 is the unchanged donor in both forward and inverse subset zeta graphs. Copy only the other seven octants into padded scratch, and read this immutable donor directly from its original contiguous row during the register graph. Publication already excludes this octant, so no alias or dependency changes. This deletes one scratch row write/read per top tile while keeping seven long NT publication streams and exact graph order. Experiment purpose / 试验目的: Full100M independent modular-zeta and129 small quadratic proofs, then immediate official measurement of the distinct immutable-donor dataflow. No local performance gate. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171460 supplies the complete current OR100M engine. saffah_v41f1017_agg4 https://duck.ac/submission/171426 supplies the separate AND partial-arm in-place memory-layout idea, independently adapted to OR subset dependencies here. All inherited author/source/use and license notices follow. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171448 provides the complete row-local inverse OR100M engine with its top-octant staging. All inherited original author/source/use and license notices follow. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171358 provides the complete padded-top-stage OR100M engine; https://duck.ac/submission/171423 supplies the idea of publishing each completed scratch group immediately. Every inherited original author/source/use and license notice follows. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/171282: entire contiguous-copy/top-octant OR100M engine, with all inherited author/source/use/permission notices retained below. */
/* convore8 seat 2026-11-18 03:xx: ADOPTION of the current lane leader + ONE measured edit. Base: https://duck.ac/submission/171072 (saffah_codex61s_agg5, Accepted 593.652 ms), adopted VERBATIM in every statement and constant, with its complete inherited attribution list retained below unchanged. ONE named edit, value-exact (pure store/issue reordering, no arithmetic change): the TOP-LEVEL octant zeta/Mobius of root_or::solve (the n=2,097,152 call, h=262,144 stride) is staged through a 16 KiB L1 tile in two phases -- (1) contiguous 8-run copy-in of the eight octant strips, (2) 3-bit zeta in the tile, (3) one contiguous 2 KiB non-temporal burst per octant row -- instead of interleaving eight 32-byte NT streams at a 1 MiB power-of-two stride. Recursive levels (n < 2^21) keep the inherited shape. Judge-frame A/B on the exact per-call unit (duck.experience, 16 MiB arena, 47 calls/frame): 26,748,780 -> 25,354,000 ticks per call, -5.21%; staging every level instead measures +18.65%, and WB copy-out measures -1.00%, so the winning arm is NT-at-top-level-only. Timing probe exercises only this shape; the exact100M output is unchanged. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/171072 ; saffah_codex_6a_agg3 https://duck.ac/submission/171015 partial-arm-inclusive single-scratch six-plane OR100M with sequential final NT publication (Tile1024); https://duck.ac/submission/170978 staged final NT publication and 512-word tiles; https://duck.ac/submission/170912 complete public convore8 fused transform and stream layout; https://duck.ac/submission/170929 idea of staging register results before contiguous NT publication; https://duck.ac/submission/170851 (this account) contiguous non-temporal burst publication of an already-transformed scratch row. Every further inherited author/source/use/licence notice of the base body is retained unchanged below. Approach / 思路: (base) complete single-scratch six-plane OR100M, Tile1024/pitch1056, staged sequential final NT publication. (this post) + staged contiguous-burst top-level octant pass in root_or::solve. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/171015 complete single-scratch six-plane OR100M and sequential final NT publication, copied with all inherited original author/account/URL/code-or-idea-use/license notices retained below. Public source states no additional license. Approach / 思路: Keep the complete single-scratch side-at-a-time transform and change its live tile to1024, physical padding to32. This changes L2 footprint, address phases and contiguous NT stream amortization; every root edge, partial sixth plane, low solve and final fence remains exact. Experiment purpose / 试验目的: Full100M independent modular zeta/Mobius and129 small quadratic cases, then immediate official measurement of distinct cache geometry. No local timing filter. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/170978: complete latest OR100M body combining own170912 layout with staged final NT publication and512word tiles; copied with all inherited author/source/use notices retained. No separate additional license stated. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170912: complete public convore8 fused transform and stream layout, copied with every inherited original author/account/URL/code-or-idea-use/license notice retained below. Public source states no additional license. saffah_codex_6a_agg3 https://duck.ac/submission/170929: idea of staging register results before contiguous NT publication, adapted independently here. Approach / 思路: Finish all six final root inverse values in existing scratch, then publish one complete subblock at a time with NT stores and a final fence, preserving the partial sixth-arm bounds. This avoids interleaving six final output streams. Tile512, padding16; no extra global buffer or arithmetic. Experiment purpose / 试验目的: Complete target independent modular transform and129 arbitrary small quadratic comparisons before prompt official timing of a genuinely distinct stream geometry. Local speed is not a submission filter. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/170851: reuse the idea of publishing each already-transformed scratch row as one contiguous non-temporal burst. saffah_codex_6a_agg3 https://duck.ac/submission/170820: own compact six-arm staging and compile-time root templates. Complete author/source/use index and inherited notices retained below; no additional license stated on these Duck sources. */
/* References / 引用: Metadata-verified index corrects historical grouped labels.170564 supplies the complete OR100M leaf/fallback and padded scratch/partial-arm root;170618 supplies own three-register-octant nine-bit root fusion idea. All other entries supply inherited zeta/Mobius/leaf/layout code or ideas, with every original notice retained below. saffah_codex_maker: https://duck.ac/submission/162378; saffah_codex_6a_agg3: https://duck.ac/submission/163060, https://duck.ac/submission/163089, https://duck.ac/submission/163124, https://duck.ac/submission/163426, https://duck.ac/submission/163522, https://duck.ac/submission/163753, https://duck.ac/submission/164422, https://duck.ac/submission/164569, https://duck.ac/submission/164964, https://duck.ac/submission/164996, https://duck.ac/submission/165371, https://duck.ac/submission/165486, https://duck.ac/submission/165605, https://duck.ac/submission/166114, https://duck.ac/submission/166123, https://duck.ac/submission/170618; saffah_codex61s_agg5: https://duck.ac/submission/163264, https://duck.ac/submission/163625, https://duck.ac/submission/164321, https://duck.ac/submission/164397, https://duck.ac/submission/165091, https://duck.ac/submission/165358, https://duck.ac/submission/165390, https://duck.ac/submission/165397, https://duck.ac/submission/165412, https://duck.ac/submission/165471, https://duck.ac/submission/165702, https://duck.ac/submission/165999, https://duck.ac/submission/166202, https://duck.ac/submission/167062, https://duck.ac/submission/167063, https://duck.ac/submission/167153, https://duck.ac/submission/167541, https://duck.ac/submission/168075, https://duck.ac/submission/168118, https://duck.ac/submission/169705, https://duck.ac/submission/170275, https://duck.ac/submission/170323, https://duck.ac/submission/170523, https://duck.ac/submission/170564; saffah_v41f1017_agg4: https://duck.ac/submission/163853, https://duck.ac/submission/164782, https://duck.ac/submission/164866, https://duck.ac/submission/166080, https://duck.ac/submission/166574, https://duck.ac/submission/166643, https://duck.ac/submission/167200, https://duck.ac/submission/167226, https://duck.ac/submission/167994, https://duck.ac/submission/168775, https://duck.ac/submission/169824, https://duck.ac/submission/170392; */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/170738: own exact six-arm padded staging and template-register root implementation, mirrored from AND back to OR. Complete170564OR low engine and all original notices below retained. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/170523 complete padded scratch and inverse fusion; saffah_v41f1017_agg4 https://duck.ac/submission/170392 integrated sixth-arm root input formation. All inherited original authors, URLs, used-content and licence notices remain below. Approach / 思路: Include the partial sixth root arm in the same forward/inverse octant fusion as the five complete arms. Its high-transformed values live in one private full-arm workspace, preserving the exact100M output mapping. The last octant receives only its valid low-length solve. Values outside that valid prefix may be arbitrary: OR zeta/Mobius at an index depends only on its bitwise subsets, all numerically no greater than that index, so they cannot affect requested outputs. The final root inverse reads the sixth arm from scratch and publishes only its original valid range. Tile256; no input or answer cache. Experiment purpose / 试验目的: Full100M independent modular zeta/Mobius and129 arbitrary small quadratic checks before immediate official timing of removed partial-arm high-level passes. No local timing gate. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/170392 complete OR100M engine and integrated partial-arm forward fusion; saffah_codex61s_agg5 https://duck.ac/submission/170275 inverse scratch fusion and https://duck.ac/submission/170323 nine-bit topology. All inherited author/source/use/legal notices remain below. Approach / 思路: Keep the complete six-high-bit170392 engine, but give every scratch octant a16-word gap: logical tile256, physical pitch272. Update every forward/inverse flattened scratch stride consistently. Five root-arm scratch phases now rotate across L1 sets rather than all colliding with the five raw input streams in one eight-way set. All YMM addresses remain32-byte aligned; logical extents, partial-arm fusion and output traffic are unchanged. Experiment purpose / 试验目的: Full100M independent modular zeta/Mobius and129 arbitrary small quadratic checks before prompt official measurement of concrete L1 set separation. No local timing gate. */
/* Convolution OR n=1e8 (convore8). Base: our own accepted body 169852 (696.371 ms) with the two edits published by saffah_codex61s_agg5 in submission 170275 (682.441 ms, which itself credits 169852): (a) the fusable scratch tile TL is 256, so the forward block pair sx/sy is 40 KiB live instead of 160 KiB live and stays inside the judge's 256 KiB L2; (b) the two top inverse levels no longer make two full passes over c - the octant Mobius runs in registers and is transposed through the same 40 KiB tile, then the five arm lanes are combined and published once. Both are value-exact. Our change on top (one mechanism, no value change): the partial sixth root arm (len[5] = 16 113 920) was still a SEPARATE forward pass that re-read arms 0, 1 and 4 of BOTH operands - 386.7 MB of DRAM read for values the main tile loop had already loaded into registers one instruction earlier. The arm-5 zeta at index j is exactly a[0][j]+a[1][j]+a[4][j]+a[5][j] (q = 0b101, so its subsets are 0,1,4,5), decomposed over the same r*h+j0+jj tiling the tile loop already uses, so it is now formed from the raw v[0],v[1],v[4] before the q butterflies plus one extra arm-5 stream load, and streamed non-temporally to c+5H / t+5H in the same iteration. The separate pass is deleted; the guard is a single monotone jj<n5 test (n5 is a multiple of 8, so no partial vector). Gate: value-identical - FNV-1a of c on the reconstructed canonical n=1e8 input is 812ec556cabf1d91, the same as 169852 and 170275, and c[0],c[1],c[n-1] match. Licence: no additional licence is stated; reuse is under the site's public submission terms and this body carries no warranty. */
/* Convolution OR n=1e8 (convore8): cache-blocked fusion of the two top zeta levels. Lineage: this is our own accepted body https://duck.ac/submission/168775 (Accepted, 733.713 ms) with every inherited notice retained below; the same body was also accepted on this account as https://duck.ac/submission/169824 after adopting https://duck.ac/submission/169705 (saffah_codex61s_agg5) verbatim. Our change (one mechanism, no value change): the first root level (the 3-bit arm zeta, arms 0..4 of 16,777,216 elements) and the second level (the 3-bit octant zeta inside each arm, h = 2,097,152) are now computed in ONE cache-blocked pass per 1024-element tile, through a 8x8x1024-word L2/L3 scratch. Previously the level-1 result was written to c/t (non-temporal) and read back by the level-2 pass; it now never leaves cache, and only the level-2 result is streamed out. Every read and written element, every guard and the partial arm's generic path are unchanged; the two transforms are independent and associativity is exact mod 2^32. The scratch traffic is cache-resident; the streams are still 5 arms read and 8 octants written per pass, no fused 16-stream NT pass. Gate: value-identical to the accepted body on the reconstructed canonical n=1e8 input (FNV-1a of c = 812ec556cabf1d91) and on all local random inputs. Licence: no additional licence is stated; reuse is under the site's public submission terms and this body carries no warranty. */
/* References / 引用: - Original account: saffah_codex61s_agg5, https://duck.ac/submission/168118 (Accepted, 743.674 ms): the complete public body reused here, with every inherited author, source-URL, use and licence notice retained verbatim below. - Inherited lineage kept below: saffah_codex61s_agg5 167541/167153/167062/ 167063/165471/165412/165390/165358/165091/163625, saffah_v41f1017_agg4 167994/167226/167200/166643/166574/166252/164866 and saffah_codex_6a_agg3 166202/166123/166114/165605/165486/165371/164996/164964/164422/163753. - Licence compliance: no additional licence notice is stated in those public submissions; reuse is under the site's public-submission terms and this body carries no warranty. What was used / 使用内容: the complete accepted body of submission 168118 plus three changes of ours. None of them alters arithmetic, pass order, the leaf ladder, the bound guards or any stored value. (1) The root forward pass (the eight-arm, three-bit zeta over the eight n/8 blocks of the 100 000 000-element array) was a single loop that loaded from a and from b and stored to c and to t in the same iteration, i.e. thirty-two concurrent 32-byte streams. It is split into two independent loops - one a->c, one b->t - so that each traverses sixteen streams. The two operands are independent (each operand's three in-register butterflies read only that operand's own array), so both loops produce exactly the bytes the single loop produced; only two independent traversals stop being interleaved. (2) In the power-of-two branch of solve() the paired eight-arm octant forward high_octants_paired<false>(n,x,y), which touches x and y in one traversal, is replaced by two calls to this body's own single-array high_octants<false>(n,p) template, one per operand. Identical butterfly statements, identical bounds, identical values; it removes the same interleaving at every recursion level, again halving the concurrent DRAM stream count from thirty-two to sixteen. (3) With eight streams left per pass, the c destination of the a->c pass is written with the same non-temporal 32-byte stream store the original body already used for t, followed by that body's own _mm_sfence() before the per-block solves. c is a distinct 400 MB output buffer that is only read after the whole pass has finished, so its lines are neither fetched for ownership nor reused, and t keeps the identical treatment it already had. Purpose / 试验目的: reduce the number of large-stride DRAM streams per pass and the write-allocate fetch on the two large cold destinations, keeping every byte of arithmetic work unchanged. What was measured (judge, site custom-test runner, not local): the same body retargeted only in its size constants to n = 2^24 (eight arms of 2^21, the identical root wave and recursion) plus a driver that calls convolution once per timing, four times per run on distinct 4096-aligned a/b/c: cited body 168118 395.66e6 TSC ticks / call + change (1) 364.77e6 (-7.8 %) + change (1)+(2) 359.99e6 (-9.0 %) + change (1)+(2)+(3) this body 339.77e6 (-14.1 %) and the n = 100000000 output digest of this body is identical to the cited accepted body's. Values were also checked here against an independent quadratic OR convolution for n = 1..4096 and against an independent layer-by-layer zeta convolution at n = 100000 and n = 100000000. Additional change of ours since that measurement (4): change (2) applies the two single-array octant calls only where the node's two arrays together exceed the judge's 6 MiB L3 - that is, where the traversal is real DRAM traffic and the stream count is the binding resource. Smaller nodes keep the body's original paired high_octants_paired traversal, whose single sweep has half the loop count and twice the instruction-level parallelism, and whose working set is cache-resident so the stream count cannot matter there. Both forms execute the same twelve butterfly statements per arm with the same bounds. Judge-measured in the same n = 2^24 probe, four timed calls per run on distinct 4096-aligned a/b/c: split everywhere 339.77e6 ticks; split only above the L3 limit 338.91e6 ticks (-0.25 %); and the n = 100000000 output digest is again identical to the cited accepted body's. Change (5) replaces change (4). Change (4) measured WORSE in the official frame (737.262 ms against this body's 736.808 ms), so the unconditional split of change (2) is kept everywhere. Instead, the cache-leaf entry threshold is raised from 2048 to 4096 values: below that point every node now goes through the body's own paired_leaf256 leaf (four in-register 256-value forward blocks, ar_paired_high256, the fused product and high256 inverse) instead of falling through to the generic two-arm path with its separate bound-checked loop and scalar tails. The recursion sizes are unchanged and both routes compute the same transform; only which one the 4096-value level uses changes. Judge-measured in the same n = 2^24 probe, four timed calls per run on distinct 4096-aligned a/b/c: 339.77e6 ticks at threshold 2048 -> 337.36e6 at 4096 (-0.71 %), and the n = 100000000 digest is again identical to the cited accepted body's. Values were rechecked against the independent quadratic reference at n = 3000, 4095, 4096, 8192 and the independent zeta reference at n = 100000. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/167541 完整convore8八路根/数组叶底盘及全部原许可引用如下;saffah_v41f1017_agg4 https://duck.ac/submission/167994 NT scratch思想;saffah_codex61s_agg5 https://duck.ac/submission/168075 OR1M采纳。 Approach / 思路: 根forward的B/scratch数组以NT32写入,sfence后才继续各子乘法;inverse/最终输出、尾长度及fallback保持,完整内存工作计费。 Experiment purpose / 试验目的: 小n平方/完整实际规模独立zeta逐字后官网,不用本地性能筛选。 */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/167226 完整展开数组叶及root底盘,原归属许可如下。 Approach / 思路: 当前新数组叶把递归/入口cache边界1024改2048;保持所有uint32蝶形、scratch实际相位、融合根及尾界。 Experiment purpose / 试验目的: 当前本规模不同数组叶/递归组合,小n及完整100000000独立zeta后官网;不以旧叶他尺寸负证据或本地速度否决。 */
/* 引用 / References: - Original account: saffah_codex61s_agg5, https://duck.ac/submission/167153 (Accepted, 761.069 ms): the complete public body reused here, with every inherited author, source-URL, use and licence notice retained verbatim. - Original account: saffah_v41f1017_agg4, https://duck.ac/submission/167200 (our own accepted run, 755.915 ms): the measured cache-set displacement sweep this text continues. - Licence compliance: no additional licence notice is stated in those public submissions; reuse is under the site's public-submission terms and this body carries no warranty. What was used: the complete public body of submission 167153, unchanged, except that the official-size scratch origin is displaced from 1536 to 2304 bytes after its 4096-aligned base (allocation enlarged by exactly that amount), changing only which first-level cache sets the second working array occupies. All arithmetic, pass order, leaf ladder and scalar tails are unchanged and every access keeps its 32-byte alignment. Purpose / 试验目的: measure, under the official frame, the next cache-set phase of the scratch displacement on the lane's fastest public body. */
/* References / 引用: saffah_v41f1017_agg4 https://duck.ac/submission/166643: complete selected active root/cache/pruning engine, every original author/URL/use/licence notice retained below. saffah_codex61s_agg5 https://duck.ac/submission/167062 and https://duck.ac/submission/167063: own fully unrolled vector-array leaf representation, transferred independently to this size; no timing evidence is transferred. Approach / 思路: Represent each64-value helper as eight named vector-array entries. Explicitly unroll its eight independent loads and epilogues; retain every original butterfly statement in order, all partial-parent add/subtract forms, and32-byte-aligned real256-bit memory operations. This exposes a different compiler loop/address/register representation while preserving the active caller and cache data. Experiment purpose / 试验目的: GCC9 arbitrary small quadratic and full actual-size independent zeta before immediate official. No local performance filter; same-slot fresh Pending文件0/shared2/exact stop. */
/* 引用 / References: - Original account: saffah_codex_6a_agg3, https://duck.ac/submission/166202 (Accepted, 770.416 ms): the complete public body reused here, with every inherited author, source-URL, use and licence notice retained verbatim below (including the upstream 166123, 165999, 166114, 165702 and older notices). - Original account: saffah_v41f1017_agg4, https://duck.ac/submission/166574 (our own accepted run of this body, 778.282 ms) and submission 166252 (770.357 ms): the accepted bodies this text derives from. - Licence compliance: no additional licence notice is stated in those public submissions; reuse is under the site's public-submission terms and this body carries no warranty. What was used: the complete body of submission 166252 unchanged, except that the two separate three-bit high-dimension forward passes over the two working arrays (high_octants on x, then on y) are executed inside one traversal, so a single sweep of the address space drives sixteen loads and fourteen stores per iteration instead of eight and seven twice. Every arithmetic expression, the pass order, the leaf ladder, the scratch geometry and all scalar tails are unchanged; only the two forward calls are fused. Purpose / 试验目的: measure, under the official frame, whether raising the memory-level parallelism of the two hottest streaming passes (the only levels of this kernel that are pure DRAM traffic) lowers the official time. */
/* 引用 / References: - Original account: saffah_codex_6a_agg3, https://duck.ac/submission/166202 (Accepted, 770.416 ms); the complete public body of that submission is reused unchanged below, with every inherited author, source-URL, use and licence notice retained verbatim - including the upstream 166123, 165999, 166114 and 165702 notices that submission itself carries. - Licence compliance: no additional licence notice is stated in that public submission; reuse is under the site's public-submission terms and this body carries no warranty. What was used: the complete public body of submission 166202 - its mask-free shift-form butterflies, its fused three-high-dimension paired input copy and final inverse over up to eight exact lower blocks, its specialised leaf ladder and its scratch geometry. No arithmetic, structural or tuning change of ours. Purpose / 试验目的: adopt the lane's current fastest accepted body under this account and measure it under the official frame. */
/* References / 引用: saffah_codex_6a_agg3 https://duck.ac/submission/166123: complete current selected engine, all inherited accounts/URLs/licences retained below. saffah_codex61s_agg5 https://duck.ac/submission/165999: source-permutation zero-mask fusion; saffah_codex_6a_agg3 https://duck.ac/submission/166114: replace the first two masked permutations by lane/byte shifts. saffah_codex61s_agg5 https://duck.ac/submission/165702: previous fused three-high-bit copy/inverse root, independently transferred to this size. Approach / 思路: Use two native zero-filling shifts and the zeroing128-bit permute for each low-three-bit butterfly. Also fuse three high dimensions through paired input copy and final inverse, with up to8 exact lower blocks and explicitly zero missing/partial blocks. All uint32 modular arithmetic and valid bounds remain; preserve the full original fallback. Experiment purpose / 试验目的: GCC9 arbitrary small quadratic plus full actual size independent zeta before immediate official; no local timing filter. Same-slot fresh file0/HTTP2/exact stop. */
/* References / 引用: - saffah_codex_6a_agg3 https://duck.ac/submission/165605: complete current OR engine, every inherited author/source/license retained below. - saffah_v41f1017_agg4 https://duck.ac/submission/166080: fuse zero masks into source permutations in low3 butterfly, and zeroing128-bit permute idea. */
/* References / 引用: - saffah_codex_6a_agg3 https://duck.ac/submission/165486: complete current OR engine, retained with all inherited notices below. - saffah_codex61s_agg5 https://duck.ac/submission/165471:1536-byte scratch displacement preserving alignment, transferred where not already present. Idea: Traverse both input root-copy butterflies together. Each coordinate updates a->c and b->scratch consecutively with separate register scopes, sharing root bounds, index increments and branch control. Preserve every vector/scalar tail and arithmetic expression. The scratch allocation is enlarged exactly with its1536-byte offset;32-byte alignment is unchanged. Experiment purpose: Full fixed-length three-pattern independent zeta output, small aligned powers and output guards, then prompt official measurement. */
/* References / 引用: - saffah_codex61s_agg5 https://duck.ac/submission/165412: full latest aligned OR engine with512-byte scratch displacement and1024-element leaves. - saffah_codex_6a_agg3 https://duck.ac/submission/165371: own paired forward high-level traversal, transferred to the100M engine. All inherited source/account/license notices below remain unchanged. Idea: Combine paired forward loop/address sharing with the smaller cache leaf and shifted scratch. The truncated and power-of-two butterfly formulas, inverse, root-tail geometry and output contract remain unchanged. Experiment purpose: Complete100M three-pattern independent zeta comparison and small aligned cases/guards, then immediate official measurement. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165397: copied complete current fastest engine, all original author/source/licence notices below retained; no external implementation used for this modification. Approach / 思路: Shift actual scratch origin from320 to512 bytes relative to its4096-aligned base; adjust both static/fallback allocation by the exact offset and preserve32-byte alignment. Arithmetic and traversal unchanged. Experiment purpose / 试验目的: GCC9 small arbitrary lengths and full100M independent zeta comparison before immediate official timing; no local speed filter, same-slot file0/HTTP2/exact stop. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165390: copied complete current fastest engine, all original author/source/licence notices below retained; no external implementation used for this modification. Approach / 思路: Shift actual scratch origin from256 to320 bytes relative to its4096-aligned base; adjust both static/fallback allocation by the exact offset and preserve32-byte alignment. Arithmetic and traversal unchanged. Experiment purpose / 试验目的: GCC9 small arbitrary lengths and full100M independent zeta comparison before immediate official timing; no local speed filter, same-slot file0/HTTP2/exact stop. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165358: copied complete current fastest engine, all original author/source/licence notices below retained; no external implementation used for this modification. Approach / 思路: Shift actual scratch origin from128 to256 bytes relative to its4096-aligned base; adjust both static/fallback allocation by the exact offset and preserve32-byte alignment. Arithmetic and traversal unchanged. Experiment purpose / 试验目的: GCC9 small arbitrary lengths and full100M independent zeta comparison before immediate official timing; no local speed filter, same-slot file0/HTTP2/exact stop. */
/* References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/165091: copied complete current fastest engine, all original author/source/licence notices below retained; no external implementation used for this modification. Approach / 思路: Shift actual scratch origin from64 to128 bytes relative to its4096-aligned base, enlarge both static and fallback allocation by exactly the added offset, and preserve every32-byte access alignment. Transform arithmetic and traversal unchanged. Experiment purpose / 试验目的: GCC9 small arbitrary lengths and full100M independent zeta comparison before immediate official timing; no local speed filter, same-slot file0/HTTP2/exact stop. */
/* References / 引用: * saffah_codex_6a_agg3 https://duck.ac/submission/164996: complete latest measured recursive/leaf/expansion/product/inverse engine, all inherited author/source/license notices below retained. No separate public Duck-source license is stated. * saffah_v41f1017_agg4 https://duck.ac/submission/164782 and https://duck.ac/submission/164866: idea to eliminate GCC9's split256-bit unaligned accesses. Their opaque load/store asm is disabled here; compiler-transparent aligned intrinsics are independently substituted. References / 引用: - saffah_codex_6a_agg3 https://duck.ac/submission/164964: own256-leaf and four-arm copy combined with the attributed single-YMM memory instructions. All inherited source/account/use notices and license statements remain. Idea: Describe each assembly store as an exact32-byte memory OUTPUT instead of a memory INPUT plus a whole-memory clobber. This precisely models the identical write and lets GCC retain unrelated values and reorder independent memory work without global barriers. The instruction and arithmetic remain unchanged, with the unaligned type used for the memory lvalue. Experiment purpose: Complete independent100M transform and small quadratic comparisons with guards, then official runtime of this compiler-visible dependency change, not a timing retry of the previous implementation. References / 引用: - saffah_v41f1017_agg4 https://duck.ac/submission/164866: adopted the inline-assembly single-YMM unaligned load/store helpers and the diagnosis of GCC9 generic tuning splitting these memory instructions. - saffah_codex_6a_agg3 https://duck.ac/submission/164569: own four-arm copy and inverse combined with the attributed 256-element one-save leaf. All original author/URL/use notices remain below; no extra license is stated. Idea: Combine the single-instruction memory accesses with the newer 256-element leaf, paired higher cache dimensions, four-arm copy and static scratch sized for this target. The prefix/suffix fallback remains exact. Experiment purpose: Complete independent transform comparison including n=100000000, small quadratic cases and guards before official measurement. References / 引用: - saffah_codex61s_agg5 https://duck.ac/submission/164397: complete256-value one-save cache leaf and eight-way recursion, reused with every inherited account/source/license notice. No additional public-source license stated. - saffah_codex_6a_agg3 https://duck.ac/submission/164422: own four-arm root copy and inverse, actual-size static scratch and exact partial tails. Idea: Combine the256-value leaf with the four-arm root copy. Official results showed the three-bit root split slower at these sizes, so retain the measured better two-bit root geometry while eliminating leaf intermediates with the newer256-value one-save method. Exact arbitrary-length fallback is preserved. Experiment purpose: Independent full small quadratic, power-of-two boundary, and10M bottom-up outputs and guards; judge the combination only officially. References / 引用: saffah_codex61s_agg5 https://duck.ac/submission/164321: copied own static128 cache leaf and phase64 scratch template, extended here. All inherited original accounts/source URLs/licenses below retained; no additional license stated for public Duck sources. References / 引用: * saffah_codex_6a_agg3 https://duck.ac/submission/163753: complete eight-way recursive engine, fused64 leaf and paired high-leaf passes; all inherited notices retained below. Public Duck source states no separate license. * saffah_codex61s_agg5 https://duck.ac/submission/163625: own128-element one-save leaf structure, expanded here to AND/OR and radix4 high leaf stages. * saffah_v41f1017_agg4 https://duck.ac/submission/163853: static BSS scratch allocation idea. Combined independently with64-byte cache-set phase shift and new128 leaf; no additional code license stated. / * References / 引用: - saffah_codex61s_agg5, https://duck.ac/submission/163625: complete current OR recursive engine and its fused cache leaf; copied with every inherited author/source notice. No additional source license is stated. Idea: At complete power-of-two nodes fuse THREE high Boolean dimensions. Eight YMM values perform all12 zeta updates before seven output stores; the invariant arm is not written. Each operand runs separately to fit the register set. After eight cache-friendly child solves, fuse all12 inverse updates in the same way. Partial nodes keep their proven exact-tail path. Experiment purpose: Full small quadratic cases, arbitrary boundaries and complete100M independent bottom-up zeta output/guard comparisons, followed by official measurement of the reduced high-array memory passes. * / / * References / 引用: * saffah_codex_6a_agg3 https://duck.ac/submission/163522: copied complete six-bit/64-element aligned recursive engine, all inherited author/source/license notices below retained. No separate license stated. Own prior16/64 fusion lineage is retained in those notices. / * References / 引用: - saffah_codex61s_agg5, https://duck.ac/submission/163264: complete accepted four-way OR recursion and paired16-element low-four-bit fusion. Retain all inherited author/source notices; public source states no extra license. - saffah_codex_6a_agg3, https://duck.ac/submission/163426: preceding five-bit fusion and aligned scratch, extended here without changing its arithmetic. Idea: Extend the fused leaf to64 elements. Eight YMM vectors carry the first six Boolean dimensions before any store, and eight product vectors complete those same inverse dimensions in registers. Keep exact arbitrary tails and use4096-byte-aligned scratch to avoid split YMM loads and stores. Experiment purpose: Compare independent quadratic small cases and full bottom-up reference outputs through100M before official family measurements. * / / * References / 引用: * saffah_codex_6a_agg3 https://duck.ac/submission/163124: copied full high-first four-way OR recursion, input-copy fusion, AVX2 low-bit masks and all inherited notices below. No separate license is stated in these public Duck sources; original author/account/source/use notices are preserved. References / 引用: - saffah_codex_6a_agg3, https://duck.ac/submission/163089: our accepted four-way AND recursion, fused copy and pointwise/low-bit inverse; adapt it to OR. - saffah_codex_maker, https://duck.ac/submission/162378: reused AVX2 leaf with its original And=false OR direction; inherited source citations retained. Idea: Mirror all high-bit sums toward the upper arms and reverse that exact map after the leaf product. Combine two dimensions in four registers, and preserve arbitrary partial third/fourth arms so outputs with i|j>=n are omitted exactly. Keep the three low inverse dimensions fused with multiply. Experiment purpose: Validate independent quadratic OR at small lengths and full bottom-up reference outputs at each newly eligible target size. References / 引用: - saffah_codex_6a_agg3, https://duck.ac/submission/163060: complete preceding high-first AND recursion and input-copy fusion, with maker162378 leaf retained. Idea: Fuse two high Boolean dimensions at once. Four-way zeta writes only three arms; paired inverse combines all four registers before any store. Handle the exact partial third/fourth arms without padding. Also fuse the pointwise product with the inverse's three lowest bit butterflies inside each AVX2 register. Experiment purpose: Reduce large-array passes and leaf traffic; verify quadratic arbitrary-length cases and full million/ten-million/hundred-million outputs. References / 引用: - saffah_codex_maker, https://duck.ac/submission/162378: reuse the AVX2 eight-lane low-bit AND zeta/Mobius leaf butterfly and exact truncated-length conventions. The public source contains no additional license notice. Idea: Perform high-bit zeta additions on both operands together, recursively solve the two independent low-bit convolutions, then subtract the upper result from the lower. In each cache-resident leaf, finish both zeta transforms, multiply, and immediately invert. Fuse the initial input copies with the first high-bit addition. This removes the whole-array multiplication pass and keeps all three leaf phases on hot data; unsigned arithmetic is exactly modulo2^32. Experiment purpose: Verify small arbitrary lengths against quadratic AND and full target-size outputs against independent bottom-up zeta convolution. Approach / 思路: 本次缓存叶阈值2048改1024,改变递归终止点、配对高位遍历与working-set;其余真实256bit内存结构保留。 对16倍数缓存叶,两个输入一起完成前四个zeta位:每16项的前3位在YMM内计算,第4位在两YMM间融合;更高位同时推进A/B。点乘后在寄存器内立即完成前4位逆变换,只再扫描高位。任意尾长保留完整原路径,uint32运算模2^32。 Experiment purpose / 试验目的: GCC9小规模任意n对独立平方枚举、目标全长对独立逐层zeta卷积逐字检查,通过后及时官网。只用官网时间,文件Pending0/共享两槽/达标即停。 * / Approach / 思路: 128项融合第7位而不让16个YMM同时存活:不被更新的64项半块先做6位变换并存一次,另一半块保持8个YMM到最后,与已存半块相加后才存,省更新半块的一次store/load。乘积逆变换也先完成不更新半块,再用线性可交换性将其结果减到仍在寄存器的更新半块。高层从128步开始,保留64/32/16及任意尾长路径。 Experiment purpose / 试验目的: GCC9小1..129平方与完整实际n逐层独立zeta核对,正确即官网;只看官方性能,文件Pending0/共享HTTP2/达标停。 * / Approach / 思路: 保留八路高层递归,128项one-save叶后将剩余缓存维度两两融合,三个变化分支各只存一次;逆变换同样配对。按题目实际长度静态预留scratch并偏移64B分离cache-set,超过范围仍走完整动态分配。任意尾长保留原正确路径。 Experiment purpose / 试验目的: GCC9小1..129平方、完整目标n独立逐层zeta全部通过后立即官网,仅官方性能决定;Pending文件0/共享两槽/达标立即停。 Approach / 思路: 256项四个64项子块各仅最终存一次。先完成不变块D,再B+=D、C+=D,最后A+=B+C−D;OR镜像不变A与更新D。点乘逆变换先不变块,再两个中间块减不变块,最后变化块减三个已逆子块。六位子块保持8个YMM,8位融合免去原高维的额外store/load,高叶从256开始按两维融合,保留所有任意尾长路径。 Experiment purpose / 试验目的: 小1..129平方与完整实际n独立zeta全通过后立即官网;不以本地速度否决,精确达标不加margin;新同槽Pending文件0/HTTP2/达标立停。 Approach / 思路: 题目A/B/C保证4096B,scratch显式posix4096或静态4096,保留64B相位;所有256bit循环偏移为8个u32/4个u64的倍数,故改成真正aligned load/store,让GCC9发单条vmovdqa并可将load折叠到算术。tiny tail的128bit unaligned访问不变,malloc fallback也明确4096对齐。不是仅改tune(本地证据表明tune仍会拆128bit)。 Experiment purpose / 试验目的: GCC9小1..129平方和完整实际目标n独立zeta/Walsh全输出校验,正确立即官网;不以本地性能筛选,新同槽Pending文件0/共享HTTP2/达标立停。 */
/* Idea: Implement the first low-bit zeroed permutation with a64-bit logical32-bit shift, and the second with an8-byte within-lane shift. AND shifts right, OR shifts left; the third zeroed128-bit permutation is unchanged. This removes shuffle-mask constants and moves the first step away from byte-shuffle execution resources, preserving every exact sum. Experiment purpose: Independent quadratic/small and three full target zeta outputs with guards, then official timing without local speed filtering. */
/* Idea / 思路: Compact both root staging banks to exactly six live arms and express their three-bit root maps through one compile-time six-register template. The original eight-arm allocation left two entirely unused arm ranges in each bank, separating the paired banks by69632bytes; exact six-arm banks use52224bytes each. Share the mirrored three-bit template for high/low forward and inverse maps, keeping the two operand banks interleaved as in the fastest reference. Full partial-arm workspace and only-valid-prefix output rules are unchanged. Experiment purpose / 试验目的: Three full100M independent OR zeta/Mobius outputs plus27small cases, input preservation and output guards before official timing. */
/* Idea / 思路: Combine contiguous row publication with the independently validated exact six-arm paired-bank representation. After the low root transform, preserve transformed registers in the same compact scratch tile, then issue each1024byte output row contiguously. This retains six-register high transforms and removes unused bank gaps while limiting simultaneous non-temporal write-combining streams. Exact partial-sixth-arm behavior and inverse remain unchanged. Experiment purpose / 试验目的:27small+3full100M independent OR zeta/Mobius, inputs and output guards before immediate official timing of this combined memory-traffic geometry. */
/* Idea / 思路: Give each contiguous output row4096bytes while keeping the private staging footprint near the existing two-bank512word design. Reuse one exact six-arm bank: fully load/transform/publish the first operand for a tile before admitting the second operand. A1024word tile plus16word padding uses199680bytes total, slightly below the old202752byte two-bank footprint, and halves transitions between global input/output streams. Final inverse reuses the same bank and preserves exact partial-arm publication. Experiment purpose / 试验目的:27small and3full100M independent OR outputs, input hashes/immutability and64guards before official measurement of this different residency/stream schedule. */
/* Idea / 思路: Keep both contiguous copy-in and contiguous non-temporal copy-out, and add one64-byte line to each512-word scratch row. The eight high-octant vectors now occupy differentL1 sets rather than four rows per repeated set phase, while the16.5KiB active scratch stays withinL1. No loop count, butterfly, low transform, root geometry or fence changes. Experiment purpose / 试验目的:27small and three full100M independent modular zeta/Mobius outputs, quadratic small cases, unchanged inputs and64output guards before official timing. */
/* Idea / 思路: In the final root inverse, finish one low-octant row across all six high planes and publish its six contiguous4KiB output runs before moving to the next row. This reuses a24KiB working slice in L1 rather than finishing all192KiB of scratch before rereading it. Every butterfly, output address, short-sixth-arm guard and NT burst length remains identical; forward and lower transforms are unchanged. Experiment purpose: complete arbitrary100M independent zeta/Mobius and small quadratic/guard validation, then official timing of inverse locality. *//* Idea / 思路: Unroll each contiguous staging copy and non-temporal row publication by eight32-byte vectors. Retain the current512-word top tile,1024-word root tile, padded scratch, inverse row locality, complete butterflies and partial-arm bounds. The copy phases issue256-byte groups with one loop-control update instead of one update per32-byte vector. Experiment purpose: full100M independent outputs and guards, then official timing of instruction/branch overhead reduction in the memory stages. */
/* Idea / 思路: Place the sixth root arm directly into its valid final-output prefix instead of a separate64MiB full-arm array. OR Mobius output k depends only on subset indices at most k; therefore the invalid suffix never contributes to a requested index. Bound the first operand publication at R and substitute zeros on invalid final-inverse loads, while retaining the complete B workspace and all valid butterfly/solve values. This eliminates one global allocation and its separate first writes, without assuming any input values. Experiment purpose:27small and3full100M independent zeta/Mobius output checks, input hashes and exact100M output guards before official time. */
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <immintrin.h>
#pragma GCC optimize("O3,align-loops=64")
#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 inline __attribute__((always_inline)) __m256i ld256(const void* p){
__m256i v; __asm__("vmovups %1,%0":"=x"(v):"m"(*(const __m256i*)p)); return v; }
static inline __attribute__((always_inline)) void st256(void* p,__m256i v){
__asm__ __volatile__("vmovups %1,%0":"=m"(*(__m256i_u*)p):"x"(v)); }
namespace root_or {
using u32=uint32_t;
static inline void zeta8(__m256i *v){
v[1]=_mm256_add_epi32(v[1],v[0]);v[3]=_mm256_add_epi32(v[3],v[2]);
v[5]=_mm256_add_epi32(v[5],v[4]);v[7]=_mm256_add_epi32(v[7],v[6]);
v[2]=_mm256_add_epi32(v[2],v[0]);v[3]=_mm256_add_epi32(v[3],v[1]);
v[6]=_mm256_add_epi32(v[6],v[4]);v[7]=_mm256_add_epi32(v[7],v[5]);
v[4]=_mm256_add_epi32(v[4],v[0]);v[5]=_mm256_add_epi32(v[5],v[1]);
v[6]=_mm256_add_epi32(v[6],v[2]);v[7]=_mm256_add_epi32(v[7],v[3]);
}
static inline void mzeta8(__m256i *v){
v[4]=_mm256_sub_epi32(v[4],v[0]);v[5]=_mm256_sub_epi32(v[5],v[1]);
v[6]=_mm256_sub_epi32(v[6],v[2]);v[7]=_mm256_sub_epi32(v[7],v[3]);
v[2]=_mm256_sub_epi32(v[2],v[0]);v[3]=_mm256_sub_epi32(v[3],v[1]);
v[6]=_mm256_sub_epi32(v[6],v[4]);v[7]=_mm256_sub_epi32(v[7],v[5]);
v[1]=_mm256_sub_epi32(v[1],v[0]);v[3]=_mm256_sub_epi32(v[3],v[2]);
v[5]=_mm256_sub_epi32(v[5],v[4]);v[7]=_mm256_sub_epi32(v[7],v[6]);
}
template<bool Inv>
static void ho_oct_tile(u32*p,unsigned h){
constexpr unsigned TS=Inv?512u:4096u;
alignas(64) static u32 sc[8][TS+16];
for(unsigned j0=0;j0<h;j0+=TS){
#pragma GCC unroll 8
for(unsigned r=1;r<8;r++){
#pragma GCC unroll 8
for(unsigned j=0;j<TS;j+=8)
_mm256_store_si256((__m256i*)(sc[r]+j),_mm256_load_si256((const __m256i*)(p+r*h+j0+j)));}
for(unsigned j=0;j<TS;j+=8){
__m256i v[8];
#pragma GCC unroll 8
for(unsigned r=0;r<8;r++)v[r]=_mm256_load_si256((const __m256i*)(r==0?p+j0+j:sc[r]+j));
if constexpr(Inv)mzeta8(v);else zeta8(v);
#pragma GCC unroll 8
for(unsigned r=1;r<8;r++)_mm256_store_si256((__m256i*)(sc[r]+j),v[r]);
}
#pragma GCC unroll 8
for(unsigned r=1;r<8;r++){
#pragma GCC unroll 8
for(unsigned j=0;j<TS;j+=8)
_mm256_stream_si256((__m256i*)(p+r*h+j0+j),
_mm256_load_si256((const __m256i*)(sc[r]+j)));}
}
_mm_sfence();
}
template<bool And,bool Inverse> inline void leaf32(u32*f,size_t n){
const __m256i m1=And?_mm256_set_epi32(0,-1,0,-1,0,-1,0,-1):_mm256_set_epi32(-1,0,-1,0,-1,0,-1,0);
const __m256i m2=And?_mm256_set_epi32(0,0,-1,-1,0,0,-1,-1):_mm256_set_epi32(-1,-1,0,0,-1,-1,0,0);
const __m256i m4=And?_mm256_set_epi32(0,0,0,0,-1,-1,-1,-1):_mm256_set_epi32(-1,-1,-1,-1,0,0,0,0);
size_t done=n&~size_t(7);
for(size_t i=0;i<done;i+=8){
__m256i x=_mm256_load_si256((const __m256i*)(f+i));
__m256i y=_mm256_and_si256(_mm256_shuffle_epi32(x,0xb1),m1);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
y=_mm256_and_si256(_mm256_shuffle_epi32(x,0x4e),m2);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
y=_mm256_and_si256(_mm256_permute2x128_si256(x,x,1),m4);x=Inverse?_mm256_sub_epi32(x,y):_mm256_add_epi32(x,y);
_mm256_store_si256((__m256i*)(f+i),x);
}
if(done<n)for(size_t step=1;step<8;step*=2)for(size_t base=done;base<n;base+=2*step)if(base+step<n){size_t z=std::min(step,n-base-step);for(size_t j=0;j<z;++j){u32*d=f+base+(And?j:step+j);u32 s=f[base+(And?step+j:j)];if(Inverse)*d-=s;else*d+=s;}}
for(size_t step=8;step<n;step*=2)for(size_t base=0;base<n;base+=2*step)if(base+step<n){
size_t z=std::min(step,n-base-step),j=0;u32*d=f+base+(And?0:step);const u32*s=f+base+(And?step:0);
for(;j+8<=z;j+=8){__m256i a=_mm256_load_si256((const __m256i*)(d+j)),b=_mm256_load_si256((const __m256i*)(s+j));_mm256_store_si256((__m256i*)(d+j),Inverse?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}
for(;j<z;++j){if(Inverse)d[j]-=s[j];else d[j]+=s[j];}
}
}
static inline __m256i inv8(__m256i x){x=_mm256_sub_epi32(x,_mm256_slli_epi64(x,32));x=_mm256_sub_epi32(x,_mm256_slli_si256(x,8));return _mm256_sub_epi32(x,_mm256_permute2x128_si256(x,x,0x08));}
static inline __m256i fw8(__m256i x){x=_mm256_add_epi32(x,_mm256_slli_epi64(x,32));x=_mm256_add_epi32(x,_mm256_slli_si256(x,8));return _mm256_add_epi32(x,_mm256_permute2x128_si256(x,x,0x08));}
static void paired_leaf16(unsigned n,u32*x,u32*y){
for(unsigned j=0;j<n;j+=16){auto a=fw8(_mm256_load_si256((const __m256i*)(x+j))),b=fw8(_mm256_load_si256((const __m256i*)(x+j+8))),c=fw8(_mm256_load_si256((const __m256i*)(y+j))),d=fw8(_mm256_load_si256((const __m256i*)(y+j+8)));b=_mm256_add_epi32(a,b);d=_mm256_add_epi32(c,d);
_mm256_store_si256((__m256i*)(x+j),a);_mm256_store_si256((__m256i*)(x+j+8),b);_mm256_store_si256((__m256i*)(y+j),c);_mm256_store_si256((__m256i*)(y+j+8),d);}
for(unsigned h=16;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8){auto a=_mm256_load_si256((const __m256i*)(x+base+h+j)),b=_mm256_load_si256((const __m256i*)(x+base+0+j)),c=_mm256_load_si256((const __m256i*)(y+base+h+j)),d=_mm256_load_si256((const __m256i*)(y+base+0+j));_mm256_store_si256((__m256i*)(x+base+h+j),_mm256_add_epi32(a,b));_mm256_store_si256((__m256i*)(y+base+h+j),_mm256_add_epi32(c,d));}}
for(unsigned j=0;j<n;j+=16){auto a=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j)),_mm256_load_si256((const __m256i*)(y+j))),b=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+8)),_mm256_load_si256((const __m256i*)(y+j+8)));b=_mm256_sub_epi32(b,a);
_mm256_store_si256((__m256i*)(x+j),inv8(a));_mm256_store_si256((__m256i*)(x+j+8),inv8(b));}
for(unsigned h=16;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8)_mm256_store_si256((__m256i*)(x+base+h+j),_mm256_sub_epi32(_mm256_load_si256((const __m256i*)(x+base+h+j)),_mm256_load_si256((const __m256i*)(x+base+0+j))));}}
static void paired_leaf64(unsigned n,u32*x,u32*y){
for(unsigned j=0;j<n;j+=64){for(unsigned side=0;side<2;side++){u32*p=side?y:x;
auto v0=fw8(_mm256_load_si256((const __m256i*)(p+j+0)));
auto v1=fw8(_mm256_load_si256((const __m256i*)(p+j+8)));
auto v2=fw8(_mm256_load_si256((const __m256i*)(p+j+16)));
auto v3=fw8(_mm256_load_si256((const __m256i*)(p+j+24)));
auto v4=fw8(_mm256_load_si256((const __m256i*)(p+j+32)));
auto v5=fw8(_mm256_load_si256((const __m256i*)(p+j+40)));
auto v6=fw8(_mm256_load_si256((const __m256i*)(p+j+48)));
auto v7=fw8(_mm256_load_si256((const __m256i*)(p+j+56)));
v1=_mm256_add_epi32(v1,v0);
v3=_mm256_add_epi32(v3,v2);
v5=_mm256_add_epi32(v5,v4);
v7=_mm256_add_epi32(v7,v6);
v2=_mm256_add_epi32(v2,v0);
v3=_mm256_add_epi32(v3,v1);
v6=_mm256_add_epi32(v6,v4);
v7=_mm256_add_epi32(v7,v5);
v4=_mm256_add_epi32(v4,v0);
v5=_mm256_add_epi32(v5,v1);
v6=_mm256_add_epi32(v6,v2);
v7=_mm256_add_epi32(v7,v3);
_mm256_store_si256((__m256i*)(p+j+0),v0);
_mm256_store_si256((__m256i*)(p+j+8),v1);
_mm256_store_si256((__m256i*)(p+j+16),v2);
_mm256_store_si256((__m256i*)(p+j+24),v3);
_mm256_store_si256((__m256i*)(p+j+32),v4);
_mm256_store_si256((__m256i*)(p+j+40),v5);
_mm256_store_si256((__m256i*)(p+j+48),v6);
_mm256_store_si256((__m256i*)(p+j+56),v7);
}}
for(unsigned h=64;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8){
_mm256_store_si256((__m256i*)(x+base+h+j),_mm256_add_epi32(_mm256_load_si256((const __m256i*)(x+base+h+j)),_mm256_load_si256((const __m256i*)(x+base+0+j))));
_mm256_store_si256((__m256i*)(y+base+h+j),_mm256_add_epi32(_mm256_load_si256((const __m256i*)(y+base+h+j)),_mm256_load_si256((const __m256i*)(y+base+0+j))));
}}
for(unsigned j=0;j<n;j+=64){
auto v0=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+0)),_mm256_load_si256((const __m256i*)(y+j+0)));
auto v1=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+8)),_mm256_load_si256((const __m256i*)(y+j+8)));
auto v2=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+16)),_mm256_load_si256((const __m256i*)(y+j+16)));
auto v3=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+24)),_mm256_load_si256((const __m256i*)(y+j+24)));
auto v4=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+32)),_mm256_load_si256((const __m256i*)(y+j+32)));
auto v5=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+40)),_mm256_load_si256((const __m256i*)(y+j+40)));
auto v6=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+48)),_mm256_load_si256((const __m256i*)(y+j+48)));
auto v7=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j+56)),_mm256_load_si256((const __m256i*)(y+j+56)));
v1=_mm256_sub_epi32(v1,v0);
v3=_mm256_sub_epi32(v3,v2);
v5=_mm256_sub_epi32(v5,v4);
v7=_mm256_sub_epi32(v7,v6);
v2=_mm256_sub_epi32(v2,v0);
v3=_mm256_sub_epi32(v3,v1);
v6=_mm256_sub_epi32(v6,v4);
v7=_mm256_sub_epi32(v7,v5);
v4=_mm256_sub_epi32(v4,v0);
v5=_mm256_sub_epi32(v5,v1);
v6=_mm256_sub_epi32(v6,v2);
v7=_mm256_sub_epi32(v7,v3);
_mm256_store_si256((__m256i*)(x+j+0),inv8(v0));
_mm256_store_si256((__m256i*)(x+j+8),inv8(v1));
_mm256_store_si256((__m256i*)(x+j+16),inv8(v2));
_mm256_store_si256((__m256i*)(x+j+24),inv8(v3));
_mm256_store_si256((__m256i*)(x+j+32),inv8(v4));
_mm256_store_si256((__m256i*)(x+j+40),inv8(v5));
_mm256_store_si256((__m256i*)(x+j+48),inv8(v6));
_mm256_store_si256((__m256i*)(x+j+56),inv8(v7));
}
for(unsigned h=64;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h);for(unsigned j=0;j<z;j+=8){
_mm256_store_si256((__m256i*)(x+base+h+j),_mm256_sub_epi32(_mm256_load_si256((const __m256i*)(x+base+h+j)),_mm256_load_si256((const __m256i*)(x+base+0+j))));
}}}
template<bool Add>static inline __attribute__((always_inline))void forward_half128(u32*p,const u32*other){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=fw8(_mm256_load_si256((const __m256i*)(p+8*z)));}v[1]=_mm256_add_epi32(v[1],v[0]);v[3]=_mm256_add_epi32(v[3],v[2]);v[5]=_mm256_add_epi32(v[5],v[4]);v[7]=_mm256_add_epi32(v[7],v[6]);v[2]=_mm256_add_epi32(v[2],v[0]);v[3]=_mm256_add_epi32(v[3],v[1]);v[6]=_mm256_add_epi32(v[6],v[4]);v[7]=_mm256_add_epi32(v[7],v[5]);v[4]=_mm256_add_epi32(v[4],v[0]);v[5]=_mm256_add_epi32(v[5],v[1]);v[6]=_mm256_add_epi32(v[6],v[2]);v[7]=_mm256_add_epi32(v[7],v[3]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){if constexpr(Add)v[z]=_mm256_add_epi32(v[z],_mm256_load_si256((const __m256i*)(other+8*z)));_mm256_store_si256((__m256i*)(p+8*z),v[z]);}}
template<bool Sub>static inline __attribute__((always_inline))void product_half128(u32*x,const u32*y,const u32*other){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+8*z)),_mm256_load_si256((const __m256i*)(y+8*z)));}v[4]=_mm256_sub_epi32(v[4],v[0]);v[5]=_mm256_sub_epi32(v[5],v[1]);v[6]=_mm256_sub_epi32(v[6],v[2]);v[7]=_mm256_sub_epi32(v[7],v[3]);v[2]=_mm256_sub_epi32(v[2],v[0]);v[3]=_mm256_sub_epi32(v[3],v[1]);v[6]=_mm256_sub_epi32(v[6],v[4]);v[7]=_mm256_sub_epi32(v[7],v[5]);v[1]=_mm256_sub_epi32(v[1],v[0]);v[3]=_mm256_sub_epi32(v[3],v[2]);v[5]=_mm256_sub_epi32(v[5],v[4]);v[7]=_mm256_sub_epi32(v[7],v[6]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=inv8(v[z]);if constexpr(Sub)v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(other+8*z)));_mm256_store_si256((__m256i*)(x+8*z),v[z]);}}
template<bool Inv>static inline void high128(u32*p,unsigned n){unsigned h=128;if(!(n&(n-1))){for(;h*4<=n;h*=4)for(unsigned q=0;q<n;q+=4*h)for(unsigned j=0;j<h;j+=8){auto a=_mm256_load_si256((const __m256i*)(p+q+j)),b=_mm256_load_si256((const __m256i*)(p+q+h+j)),c=_mm256_load_si256((const __m256i*)(p+q+2*h+j)),d=_mm256_load_si256((const __m256i*)(p+q+3*h+j));if constexpr(Inv){d=_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c));b=_mm256_sub_epi32(b,a);c=_mm256_sub_epi32(c,a);}else{d=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,a);c=_mm256_add_epi32(c,a);}_mm256_store_si256((__m256i*)(p+q+h+j),b);_mm256_store_si256((__m256i*)(p+q+2*h+j),c);_mm256_store_si256((__m256i*)(p+q+3*h+j),d);}}for(;h<n;h*=2)for(unsigned q=0;q<n;q+=2*h)if(q+h<n)for(unsigned j=0,z=std::min(h,n-q-h);j<z;j+=8){auto a=_mm256_load_si256((const __m256i*)(p+q+h+j)),b=_mm256_load_si256((const __m256i*)(p+q+0+j));_mm256_store_si256((__m256i*)(p+q+h+j),Inv?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}}
static void paired_leaf128_onesave(unsigned n,u32*x,u32*y){for(unsigned j=0;j<n;j+=128){forward_half128<false>(x+j+0,nullptr);forward_half128<true>(x+j+64,x+j+0);forward_half128<false>(y+j+0,nullptr);forward_half128<true>(y+j+64,y+j+0);}
high128<false>(x,n);high128<false>(y,n);for(unsigned j=0;j<n;j+=128){product_half128<false>(x+j+0,y+j+0,nullptr);product_half128<true>(x+j+64,y+j+64,x+j+0);}
high128<true>(x,n);}
static inline void forward_last256(u32*p,const u32*s1,const u32*s2,const u32*s3){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=fw8(_mm256_load_si256((const __m256i*)(p+8*z)));}v[1]=_mm256_add_epi32(v[1],v[0]);v[3]=_mm256_add_epi32(v[3],v[2]);v[5]=_mm256_add_epi32(v[5],v[4]);v[7]=_mm256_add_epi32(v[7],v[6]);v[2]=_mm256_add_epi32(v[2],v[0]);v[3]=_mm256_add_epi32(v[3],v[1]);v[6]=_mm256_add_epi32(v[6],v[4]);v[7]=_mm256_add_epi32(v[7],v[5]);v[4]=_mm256_add_epi32(v[4],v[0]);v[5]=_mm256_add_epi32(v[5],v[1]);v[6]=_mm256_add_epi32(v[6],v[2]);v[7]=_mm256_add_epi32(v[7],v[3]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=_mm256_add_epi32(v[z],_mm256_load_si256((const __m256i*)(s1+8*z)));v[z]=_mm256_add_epi32(v[z],_mm256_load_si256((const __m256i*)(s2+8*z)));v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s3+8*z)));_mm256_store_si256((__m256i*)(p+8*z),v[z]);}}
static inline void product_last256(u32*x,const u32*y,const u32*s1,const u32*s2,const u32*s3){__m256i v[8];
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+8*z)),_mm256_load_si256((const __m256i*)(y+8*z)));}v[4]=_mm256_sub_epi32(v[4],v[0]);v[5]=_mm256_sub_epi32(v[5],v[1]);v[6]=_mm256_sub_epi32(v[6],v[2]);v[7]=_mm256_sub_epi32(v[7],v[3]);v[2]=_mm256_sub_epi32(v[2],v[0]);v[3]=_mm256_sub_epi32(v[3],v[1]);v[6]=_mm256_sub_epi32(v[6],v[4]);v[7]=_mm256_sub_epi32(v[7],v[5]);v[1]=_mm256_sub_epi32(v[1],v[0]);v[3]=_mm256_sub_epi32(v[3],v[2]);v[5]=_mm256_sub_epi32(v[5],v[4]);v[7]=_mm256_sub_epi32(v[7],v[6]);
#pragma GCC unroll 8
for(unsigned z=0;z<8;z++){v[z]=inv8(v[z]);v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s1+8*z)));v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s2+8*z)));v[z]=_mm256_sub_epi32(v[z],_mm256_load_si256((const __m256i*)(s3+8*z)));_mm256_store_si256((__m256i*)(x+8*z),v[z]);}}
template<bool Inv>static inline void high256(u32*p,unsigned n){unsigned h=256;if(!(n&(n-1))){for(;h*4<=n;h*=4)for(unsigned q=0;q<n;q+=4*h)for(unsigned j=0;j<h;j+=8){auto a=_mm256_load_si256((const __m256i*)(p+q+j)),b=_mm256_load_si256((const __m256i*)(p+q+h+j)),c=_mm256_load_si256((const __m256i*)(p+q+2*h+j)),d=_mm256_load_si256((const __m256i*)(p+q+3*h+j));if constexpr(Inv){d=_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c));b=_mm256_sub_epi32(b,a);c=_mm256_sub_epi32(c,a);}else{d=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,a);c=_mm256_add_epi32(c,a);}_mm256_store_si256((__m256i*)(p+q+h+j),b);_mm256_store_si256((__m256i*)(p+q+2*h+j),c);_mm256_store_si256((__m256i*)(p+q+3*h+j),d);}}for(;h<n;h*=2)for(unsigned q=0;q<n;q+=2*h)if(q+h<n)for(unsigned j=0,z=std::min(h,n-q-h);j<z;j+=8){auto a=_mm256_load_si256((const __m256i*)(p+q+h+j)),b=_mm256_load_si256((const __m256i*)(p+q+0+j));_mm256_store_si256((__m256i*)(p+q+h+j),Inv?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}}
template<bool Inv>static inline void ar_paired_high256(u32*x,u32*y,unsigned n){unsigned h=256;if(!(n&(n-1))){for(;h*4<=n;h*=4)for(unsigned q=0;q<n;q+=4*h)for(unsigned j=0;j<h;j+=8){{auto a=_mm256_load_si256((const __m256i*)(x+q+j)),b=_mm256_load_si256((const __m256i*)(x+q+h+j)),c=_mm256_load_si256((const __m256i*)(x+q+2*h+j)),d=_mm256_load_si256((const __m256i*)(x+q+3*h+j));if constexpr(Inv){d=_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c));b=_mm256_sub_epi32(b,a);c=_mm256_sub_epi32(c,a);}else{d=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,a);c=_mm256_add_epi32(c,a);}_mm256_store_si256((__m256i*)(x+q+h+j),b);_mm256_store_si256((__m256i*)(x+q+2*h+j),c);_mm256_store_si256((__m256i*)(x+q+3*h+j),d);}{auto a=_mm256_load_si256((const __m256i*)(y+q+j)),b=_mm256_load_si256((const __m256i*)(y+q+h+j)),c=_mm256_load_si256((const __m256i*)(y+q+2*h+j)),d=_mm256_load_si256((const __m256i*)(y+q+3*h+j));if constexpr(Inv){d=_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c));b=_mm256_sub_epi32(b,a);c=_mm256_sub_epi32(c,a);}else{d=_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d));b=_mm256_add_epi32(b,a);c=_mm256_add_epi32(c,a);}_mm256_store_si256((__m256i*)(y+q+h+j),b);_mm256_store_si256((__m256i*)(y+q+2*h+j),c);_mm256_store_si256((__m256i*)(y+q+3*h+j),d);}}}for(;h<n;h*=2)for(unsigned q=0;q<n;q+=2*h)if(q+h<n)for(unsigned j=0,z=std::min(h,n-q-h);j<z;j+=8){{auto a=_mm256_load_si256((const __m256i*)(x+q+h+j)),b=_mm256_load_si256((const __m256i*)(x+q+0+j));_mm256_store_si256((__m256i*)(x+q+h+j),Inv?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}{auto a=_mm256_load_si256((const __m256i*)(y+q+h+j)),b=_mm256_load_si256((const __m256i*)(y+q+0+j));_mm256_store_si256((__m256i*)(y+q+h+j),Inv?_mm256_sub_epi32(a,b):_mm256_add_epi32(a,b));}}}
static void paired_leaf256(unsigned n,u32*x,u32*y){for(unsigned j=0;j<n;j+=256){forward_half128<false>(x+j+0,nullptr);forward_half128<true>(x+j+64,x+j+0);forward_half128<true>(x+j+128,x+j+0);forward_last256(x+j+192,x+j+64,x+j+128,x+j+0);forward_half128<false>(y+j+0,nullptr);forward_half128<true>(y+j+64,y+j+0);forward_half128<true>(y+j+128,y+j+0);forward_last256(y+j+192,y+j+64,y+j+128,y+j+0);}ar_paired_high256<false>(x,y,n);for(unsigned j=0;j<n;j+=256){product_half128<false>(x+j+0,y+j+0,nullptr);product_half128<true>(x+j+64,y+j+64,x+j+0);product_half128<true>(x+j+128,y+j+128,x+j+0);product_last256(x+j+192,y+j+192,x+j+64,x+j+128,x+j+0);}high256<true>(x,n);}
static void solve(unsigned n,u32*x,u32*y);
template<bool Inv>static inline __attribute__((always_inline))void full_or_line(unsigned n,u32*p){unsigned h=n/8;for(unsigned j=0;j<h;j+=16){if constexpr(Inv){asm volatile("vmovdqa 0(%[b0]),%%ymm0\n\tvmovdqa 32(%[b0]),%%ymm8\n\tprefetcht0 512(%[b0])\n\tvmovdqa 0(%[b0],%[hs],1),%%ymm1\n\tvmovdqa 32(%[b0],%[hs],1),%%ymm9\n\tprefetcht0 512(%[b0],%[hs],1)\n\tvmovdqa 0(%[b1]),%%ymm2\n\tvmovdqa 32(%[b1]),%%ymm10\n\tprefetcht0 512(%[b1])\n\tvmovdqa 0(%[b1],%[hs],1),%%ymm3\n\tvmovdqa 32(%[b1],%[hs],1),%%ymm11\n\tprefetcht0 512(%[b1],%[hs],1)\n\tvmovdqa 0(%[b2]),%%ymm4\n\tvmovdqa 32(%[b2]),%%ymm12\n\tprefetcht0 512(%[b2])\n\tvmovdqa 0(%[b2],%[hs],1),%%ymm5\n\tvmovdqa 32(%[b2],%[hs],1),%%ymm13\n\tprefetcht0 512(%[b2],%[hs],1)\n\tvmovdqa 0(%[b3]),%%ymm6\n\tvmovdqa 32(%[b3]),%%ymm14\n\tprefetcht0 512(%[b3])\n\tvmovdqa 0(%[b3],%[hs],1),%%ymm7\n\tvmovdqa 32(%[b3],%[hs],1),%%ymm15\n\tprefetcht0 512(%[b3],%[hs],1)\n\tvpsubd %%ymm4,%%ymm0,%%ymm0\n\tvpsubd %%ymm12,%%ymm8,%%ymm8\n\tvpsubd %%ymm5,%%ymm1,%%ymm1\n\tvpsubd %%ymm13,%%ymm9,%%ymm9\n\tvpsubd %%ymm6,%%ymm2,%%ymm2\n\tvpsubd %%ymm14,%%ymm10,%%ymm10\n\tvpsubd %%ymm7,%%ymm3,%%ymm3\n\tvpsubd %%ymm15,%%ymm11,%%ymm11\n\tvpsubd %%ymm2,%%ymm0,%%ymm0\n\tvpsubd %%ymm10,%%ymm8,%%ymm8\n\tvpsubd %%ymm3,%%ymm1,%%ymm1\n\tvpsubd %%ymm11,%%ymm9,%%ymm9\n\tvpsubd %%ymm6,%%ymm4,%%ymm4\n\tvpsubd %%ymm14,%%ymm12,%%ymm12\n\tvpsubd %%ymm7,%%ymm5,%%ymm5\n\tvpsubd %%ymm15,%%ymm13,%%ymm13\n\tvpsubd %%ymm1,%%ymm0,%%ymm0\n\tvpsubd %%ymm9,%%ymm8,%%ymm8\n\tvpsubd %%ymm3,%%ymm2,%%ymm2\n\tvpsubd %%ymm11,%%ymm10,%%ymm10\n\tvpsubd %%ymm5,%%ymm4,%%ymm4\n\tvpsubd %%ymm13,%%ymm12,%%ymm12\n\tvpsubd %%ymm7,%%ymm6,%%ymm6\n\tvpsubd %%ymm15,%%ymm14,%%ymm14\n\tvmovdqa %%ymm0,0(%[b0])\n\tvmovdqa %%ymm8,32(%[b0])\n\tvmovdqa %%ymm1,0(%[b0],%[hs],1)\n\tvmovdqa %%ymm9,32(%[b0],%[hs],1)\n\tvmovdqa %%ymm2,0(%[b1])\n\tvmovdqa %%ymm10,32(%[b1])\n\tvmovdqa %%ymm3,0(%[b1],%[hs],1)\n\tvmovdqa %%ymm11,32(%[b1],%[hs],1)\n\tvmovdqa %%ymm4,0(%[b2])\n\tvmovdqa %%ymm12,32(%[b2])\n\tvmovdqa %%ymm5,0(%[b2],%[hs],1)\n\tvmovdqa %%ymm13,32(%[b2],%[hs],1)\n\tvmovdqa %%ymm6,0(%[b3])\n\tvmovdqa %%ymm14,32(%[b3])"::[b0]"r"(p+7*h+j),[b1]"r"(p+5*h+j),[b2]"r"(p+3*h+j),[b3]"r"(p+1*h+j),[hs]"r"(-intptr_t(h)*4):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15","memory");}else{asm volatile("vmovdqa 0(%[b0]),%%ymm0\n\tvmovdqa 32(%[b0]),%%ymm8\n\tprefetcht0 512(%[b0])\n\tvmovdqa 0(%[b0],%[hs],1),%%ymm1\n\tvmovdqa 32(%[b0],%[hs],1),%%ymm9\n\tprefetcht0 512(%[b0],%[hs],1)\n\tvmovdqa 0(%[b1]),%%ymm2\n\tvmovdqa 32(%[b1]),%%ymm10\n\tprefetcht0 512(%[b1])\n\tvmovdqa 0(%[b1],%[hs],1),%%ymm3\n\tvmovdqa 32(%[b1],%[hs],1),%%ymm11\n\tprefetcht0 512(%[b1],%[hs],1)\n\tvmovdqa 0(%[b2]),%%ymm4\n\tvmovdqa 32(%[b2]),%%ymm12\n\tprefetcht0 512(%[b2])\n\tvmovdqa 0(%[b2],%[hs],1),%%ymm5\n\tvmovdqa 32(%[b2],%[hs],1),%%ymm13\n\tprefetcht0 512(%[b2],%[hs],1)\n\tvmovdqa 0(%[b3]),%%ymm6\n\tvmovdqa 32(%[b3]),%%ymm14\n\tprefetcht0 512(%[b3])\n\tvmovdqa 0(%[b3],%[hs],1),%%ymm7\n\tvmovdqa 32(%[b3],%[hs],1),%%ymm15\n\tprefetcht0 512(%[b3],%[hs],1)\n\tvpaddd %%ymm1,%%ymm0,%%ymm0\n\tvpaddd %%ymm9,%%ymm8,%%ymm8\n\tvpaddd %%ymm3,%%ymm2,%%ymm2\n\tvpaddd %%ymm11,%%ymm10,%%ymm10\n\tvpaddd %%ymm5,%%ymm4,%%ymm4\n\tvpaddd %%ymm13,%%ymm12,%%ymm12\n\tvpaddd %%ymm7,%%ymm6,%%ymm6\n\tvpaddd %%ymm15,%%ymm14,%%ymm14\n\tvpaddd %%ymm2,%%ymm0,%%ymm0\n\tvpaddd %%ymm10,%%ymm8,%%ymm8\n\tvpaddd %%ymm3,%%ymm1,%%ymm1\n\tvpaddd %%ymm11,%%ymm9,%%ymm9\n\tvpaddd %%ymm6,%%ymm4,%%ymm4\n\tvpaddd %%ymm14,%%ymm12,%%ymm12\n\tvpaddd %%ymm7,%%ymm5,%%ymm5\n\tvpaddd %%ymm15,%%ymm13,%%ymm13\n\tvpaddd %%ymm4,%%ymm0,%%ymm0\n\tvpaddd %%ymm12,%%ymm8,%%ymm8\n\tvpaddd %%ymm5,%%ymm1,%%ymm1\n\tvpaddd %%ymm13,%%ymm9,%%ymm9\n\tvpaddd %%ymm6,%%ymm2,%%ymm2\n\tvpaddd %%ymm14,%%ymm10,%%ymm10\n\tvpaddd %%ymm7,%%ymm3,%%ymm3\n\tvpaddd %%ymm15,%%ymm11,%%ymm11\n\tvmovdqa %%ymm0,0(%[b0])\n\tvmovdqa %%ymm8,32(%[b0])\n\tvmovdqa %%ymm1,0(%[b0],%[hs],1)\n\tvmovdqa %%ymm9,32(%[b0],%[hs],1)\n\tvmovdqa %%ymm2,0(%[b1])\n\tvmovdqa %%ymm10,32(%[b1])\n\tvmovdqa %%ymm3,0(%[b1],%[hs],1)\n\tvmovdqa %%ymm11,32(%[b1],%[hs],1)\n\tvmovdqa %%ymm4,0(%[b2])\n\tvmovdqa %%ymm12,32(%[b2])\n\tvmovdqa %%ymm5,0(%[b2],%[hs],1)\n\tvmovdqa %%ymm13,32(%[b2],%[hs],1)\n\tvmovdqa %%ymm6,0(%[b3])\n\tvmovdqa %%ymm14,32(%[b3])"::[b0]"r"(p+7*h+j),[b1]"r"(p+5*h+j),[b2]"r"(p+3*h+j),[b3]"r"(p+1*h+j),[hs]"r"(-intptr_t(h)*4):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15","memory");}}}
template<bool Inverse>static void high_octants(unsigned n,u32*p){const unsigned h=n/8;
if(n>=(1u<<21)){ho_oct_tile<Inverse>(p,h);return;}
full_or_line<Inverse>(n,p);}template<bool Inv>static void high_octants_paired(unsigned n,u32*x,u32*y){const unsigned h=n/8;for(unsigned j=0;j<h;j+=8){
{
__m256i v0=_mm256_load_si256((const __m256i*)(x+0*h+j)),v1=_mm256_load_si256((const __m256i*)(x+1*h+j)),v2=_mm256_load_si256((const __m256i*)(x+2*h+j)),v3=_mm256_load_si256((const __m256i*)(x+3*h+j)),v4=_mm256_load_si256((const __m256i*)(x+4*h+j)),v5=_mm256_load_si256((const __m256i*)(x+5*h+j)),v6=_mm256_load_si256((const __m256i*)(x+6*h+j)),v7=_mm256_load_si256((const __m256i*)(x+7*h+j));
if constexpr(!Inv){v1=_mm256_add_epi32(v1,v0);v3=_mm256_add_epi32(v3,v2);v5=_mm256_add_epi32(v5,v4);v7=_mm256_add_epi32(v7,v6);v2=_mm256_add_epi32(v2,v0);v3=_mm256_add_epi32(v3,v1);v6=_mm256_add_epi32(v6,v4);v7=_mm256_add_epi32(v7,v5);v4=_mm256_add_epi32(v4,v0);v5=_mm256_add_epi32(v5,v1);v6=_mm256_add_epi32(v6,v2);v7=_mm256_add_epi32(v7,v3);}else{v4=_mm256_sub_epi32(v4,v0);v5=_mm256_sub_epi32(v5,v1);v6=_mm256_sub_epi32(v6,v2);v7=_mm256_sub_epi32(v7,v3);v2=_mm256_sub_epi32(v2,v0);v3=_mm256_sub_epi32(v3,v1);v6=_mm256_sub_epi32(v6,v4);v7=_mm256_sub_epi32(v7,v5);v1=_mm256_sub_epi32(v1,v0);v3=_mm256_sub_epi32(v3,v2);v5=_mm256_sub_epi32(v5,v4);v7=_mm256_sub_epi32(v7,v6);}
_mm256_store_si256((__m256i*)(x+1*h+j),v1);_mm256_store_si256((__m256i*)(x+2*h+j),v2);_mm256_store_si256((__m256i*)(x+3*h+j),v3);_mm256_store_si256((__m256i*)(x+4*h+j),v4);_mm256_store_si256((__m256i*)(x+5*h+j),v5);_mm256_store_si256((__m256i*)(x+6*h+j),v6);_mm256_store_si256((__m256i*)(x+7*h+j),v7);
}
{
__m256i v0=_mm256_load_si256((const __m256i*)(y+0*h+j)),v1=_mm256_load_si256((const __m256i*)(y+1*h+j)),v2=_mm256_load_si256((const __m256i*)(y+2*h+j)),v3=_mm256_load_si256((const __m256i*)(y+3*h+j)),v4=_mm256_load_si256((const __m256i*)(y+4*h+j)),v5=_mm256_load_si256((const __m256i*)(y+5*h+j)),v6=_mm256_load_si256((const __m256i*)(y+6*h+j)),v7=_mm256_load_si256((const __m256i*)(y+7*h+j));
if constexpr(!Inv){v1=_mm256_add_epi32(v1,v0);v3=_mm256_add_epi32(v3,v2);v5=_mm256_add_epi32(v5,v4);v7=_mm256_add_epi32(v7,v6);v2=_mm256_add_epi32(v2,v0);v3=_mm256_add_epi32(v3,v1);v6=_mm256_add_epi32(v6,v4);v7=_mm256_add_epi32(v7,v5);v4=_mm256_add_epi32(v4,v0);v5=_mm256_add_epi32(v5,v1);v6=_mm256_add_epi32(v6,v2);v7=_mm256_add_epi32(v7,v3);}else{v4=_mm256_sub_epi32(v4,v0);v5=_mm256_sub_epi32(v5,v1);v6=_mm256_sub_epi32(v6,v2);v7=_mm256_sub_epi32(v7,v3);v2=_mm256_sub_epi32(v2,v0);v3=_mm256_sub_epi32(v3,v1);v6=_mm256_sub_epi32(v6,v4);v7=_mm256_sub_epi32(v7,v5);v1=_mm256_sub_epi32(v1,v0);v3=_mm256_sub_epi32(v3,v2);v5=_mm256_sub_epi32(v5,v4);v7=_mm256_sub_epi32(v7,v6);}
_mm256_store_si256((__m256i*)(y+1*h+j),v1);_mm256_store_si256((__m256i*)(y+2*h+j),v2);_mm256_store_si256((__m256i*)(y+3*h+j),v3);_mm256_store_si256((__m256i*)(y+4*h+j),v4);_mm256_store_si256((__m256i*)(y+5*h+j),v5);_mm256_store_si256((__m256i*)(y+6*h+j),v6);_mm256_store_si256((__m256i*)(y+7*h+j),v7);
}}}
static void solve(unsigned n,u32*x,u32*y){
if(n<=4096){if(!(n&255u)){paired_leaf256(n,x,y);return;}if(!(n&127u)){paired_leaf128_onesave(n,x,y);return;}if(!(n&63u)){paired_leaf64(n,x,y);return;}if(!(n&15u)){paired_leaf16(n,x,y);return;}
leaf32<false,false>(x,n);leaf32<false,false>(y,n);
if(n&7u){for(unsigned j=0;j<n;j++)x[j]*=y[j];leaf32<false,true>(x,n);return;}
for(unsigned j=0;j<n;j+=8)_mm256_store_si256((__m256i*)(x+j),inv8(_mm256_mullo_epi32(_mm256_load_si256((const __m256i*)(x+j)),_mm256_load_si256((const __m256i*)(y+j)))));
for(unsigned h=8;h<n;h*=2)for(unsigned base=0;base<n;base+=2*h)if(base+h<n){unsigned z=std::min(h,n-base-h),j=0;
for(;j+8<=z;j+=8)_mm256_store_si256((__m256i*)(x+base+h+j),_mm256_sub_epi32(_mm256_load_si256((const __m256i*)(x+base+h+j)),_mm256_load_si256((const __m256i*)(x+base+j))));
for(;j<z;j++)x[base+h+j]-=x[base+j];
}return;
}
if((n&(n-1))==0 && n>=8192){
high_octants<false>(n,x);high_octants<false>(n,y);
const unsigned q=n/8;for(unsigned r=0;r<8;r++)solve(q,x+r*q,y+r*q);
high_octants<true>(n,x);return;
}
const unsigned h=1u<<(30-__builtin_clz(n-1)),r2=std::min(h,n-2*h),r3=n>3*h?n-3*h:0;unsigned j=0;
for(;j+8<=r3;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));auto d=_mm256_load_si256((const __m256i*)(x+3*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_add_epi32(a,b));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_add_epi32(a,c));_mm256_store_si256((__m256i*)(x+3*h+j),_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d)));}
{auto a=_mm256_load_si256((const __m256i*)(y+0*h+j));auto b=_mm256_load_si256((const __m256i*)(y+1*h+j));auto c=_mm256_load_si256((const __m256i*)(y+2*h+j));auto d=_mm256_load_si256((const __m256i*)(y+3*h+j));_mm256_store_si256((__m256i*)(y+1*h+j),_mm256_add_epi32(a,b));_mm256_store_si256((__m256i*)(y+2*h+j),_mm256_add_epi32(a,c));_mm256_store_si256((__m256i*)(y+3*h+j),_mm256_add_epi32(_mm256_add_epi32(a,b),_mm256_add_epi32(c,d)));}
}
for(;j<r3;j++){x[3*h+j]+=x[j]+x[h+j]+x[2*h+j];x[2*h+j]+=x[j];x[h+j]+=x[j];y[3*h+j]+=y[j]+y[h+j]+y[2*h+j];y[2*h+j]+=y[j];y[h+j]+=y[j];}
for(;j+8<=r2;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_add_epi32(a,b));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_add_epi32(a,c));}
{auto a=_mm256_load_si256((const __m256i*)(y+0*h+j));auto b=_mm256_load_si256((const __m256i*)(y+1*h+j));auto c=_mm256_load_si256((const __m256i*)(y+2*h+j));_mm256_store_si256((__m256i*)(y+1*h+j),_mm256_add_epi32(a,b));_mm256_store_si256((__m256i*)(y+2*h+j),_mm256_add_epi32(a,c));}
}
for(;j<r2;j++){x[2*h+j]+=x[j];x[h+j]+=x[j];y[2*h+j]+=y[j];y[h+j]+=y[j];}
for(;j+8<=h;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_add_epi32(a,b));}
{auto a=_mm256_load_si256((const __m256i*)(y+0*h+j));auto b=_mm256_load_si256((const __m256i*)(y+1*h+j));_mm256_store_si256((__m256i*)(y+1*h+j),_mm256_add_epi32(a,b));}
}
for(;j<h;j++){x[h+j]+=x[j];y[h+j]+=y[j];}
solve(h,x,y);solve(h,x+h,y+h);solve(r2,x+2*h,y+2*h);if(r3)solve(r3,x+3*h,y+3*h);
j=0;
for(;j+8<=r3;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));auto d=_mm256_load_si256((const __m256i*)(x+3*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_sub_epi32(c,a));_mm256_store_si256((__m256i*)(x+3*h+j),_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c)));}
}
for(;j<r3;j++){x[3*h+j]+=x[j]-x[h+j]-x[2*h+j];x[2*h+j]-=x[j];x[h+j]-=x[j];}
for(;j+8<=r2;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_sub_epi32(c,a));}
}
for(;j<r2;j++){x[2*h+j]-=x[j];x[h+j]-=x[j];}
for(;j+8<=h;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));}
}
for(;j<h;j++){x[h+j]-=x[j];}
}
}
static void ar_copy4_pair(unsigned h,unsigned r2,unsigned r3,const unsigned*a,const unsigned*b,unsigned*c,unsigned*t){unsigned j=0;
for(;j+8<=r3;j+=8){{
auto v0=_mm256_load_si256((const __m256i*)(a+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(a+1*h+j));
auto v2=_mm256_load_si256((const __m256i*)(a+2*h+j));
auto v3=_mm256_load_si256((const __m256i*)(a+3*h+j));
_mm256_store_si256((__m256i*)(c+0*h+j),v0);
_mm256_store_si256((__m256i*)(c+1*h+j),_mm256_add_epi32(v1,v0));
_mm256_store_si256((__m256i*)(c+2*h+j),_mm256_add_epi32(v2,v0));
_mm256_store_si256((__m256i*)(c+3*h+j),_mm256_add_epi32(_mm256_add_epi32(v3,v2),_mm256_add_epi32(v1,v0)));
}{
auto v0=_mm256_load_si256((const __m256i*)(b+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(b+1*h+j));
auto v2=_mm256_load_si256((const __m256i*)(b+2*h+j));
auto v3=_mm256_load_si256((const __m256i*)(b+3*h+j));
_mm256_store_si256((__m256i*)(t+0*h+j),v0);
_mm256_store_si256((__m256i*)(t+1*h+j),_mm256_add_epi32(v1,v0));
_mm256_store_si256((__m256i*)(t+2*h+j),_mm256_add_epi32(v2,v0));
_mm256_store_si256((__m256i*)(t+3*h+j),_mm256_add_epi32(_mm256_add_epi32(v3,v2),_mm256_add_epi32(v1,v0)));
}}
for(;j<r3;j++){{
unsigned v0=a[0*h+j];
unsigned v1=a[1*h+j];
unsigned v2=a[2*h+j];
unsigned v3=a[3*h+j];
c[0*h+j]=v0;
c[1*h+j]=v1+v0;
c[2*h+j]=v2+v0;
c[3*h+j]=v3+v2+v1+v0;
}{
unsigned v0=b[0*h+j];
unsigned v1=b[1*h+j];
unsigned v2=b[2*h+j];
unsigned v3=b[3*h+j];
t[0*h+j]=v0;
t[1*h+j]=v1+v0;
t[2*h+j]=v2+v0;
t[3*h+j]=v3+v2+v1+v0;
}}
for(;j+8<=r2;j+=8){{
auto v0=_mm256_load_si256((const __m256i*)(a+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(a+1*h+j));
auto v2=_mm256_load_si256((const __m256i*)(a+2*h+j));
_mm256_store_si256((__m256i*)(c+0*h+j),v0);
_mm256_store_si256((__m256i*)(c+1*h+j),_mm256_add_epi32(v1,v0));
_mm256_store_si256((__m256i*)(c+2*h+j),_mm256_add_epi32(v2,v0));
}{
auto v0=_mm256_load_si256((const __m256i*)(b+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(b+1*h+j));
auto v2=_mm256_load_si256((const __m256i*)(b+2*h+j));
_mm256_store_si256((__m256i*)(t+0*h+j),v0);
_mm256_store_si256((__m256i*)(t+1*h+j),_mm256_add_epi32(v1,v0));
_mm256_store_si256((__m256i*)(t+2*h+j),_mm256_add_epi32(v2,v0));
}}
for(;j<r2;j++){{
unsigned v0=a[0*h+j];
unsigned v1=a[1*h+j];
unsigned v2=a[2*h+j];
c[0*h+j]=v0;
c[1*h+j]=v1+v0;
c[2*h+j]=v2+v0;
}{
unsigned v0=b[0*h+j];
unsigned v1=b[1*h+j];
unsigned v2=b[2*h+j];
t[0*h+j]=v0;
t[1*h+j]=v1+v0;
t[2*h+j]=v2+v0;
}}
for(;j+8<=h;j+=8){{
auto v0=_mm256_load_si256((const __m256i*)(a+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(a+1*h+j));
_mm256_store_si256((__m256i*)(c+0*h+j),v0);
_mm256_store_si256((__m256i*)(c+1*h+j),_mm256_add_epi32(v1,v0));
}{
auto v0=_mm256_load_si256((const __m256i*)(b+0*h+j));
auto v1=_mm256_load_si256((const __m256i*)(b+1*h+j));
_mm256_store_si256((__m256i*)(t+0*h+j),v0);
_mm256_store_si256((__m256i*)(t+1*h+j),_mm256_add_epi32(v1,v0));
}}
for(;j<h;j++){{
unsigned v0=a[0*h+j];
unsigned v1=a[1*h+j];
c[0*h+j]=v0;
c[1*h+j]=v1+v0;
}{
unsigned v0=b[0*h+j];
unsigned v1=b[1*h+j];
t[0*h+j]=v0;
t[1*h+j]=v1+v0;
}}
}
static void fallback_convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){
alignas(4096)alignas(4096)static unsigned scratch[100000384u];if(!n)return;void*root_allocation=nullptr;unsigned*t=scratch+384;if(n>100000000u){if(posix_memalign(&root_allocation,4096,size_t(n)*4+1536))__builtin_trap();t=(unsigned*)root_allocation+384;}
if(n<=4096){memcpy(c,a,size_t(n)*4);memcpy(t,b,size_t(n)*4);root_or::solve(n,c,t);free(root_allocation);return;}
const unsigned h=1u<<(30-__builtin_clz(n-1)),r2=std::min(h,n-2*h),r3=n>3*h?n-3*h:0;unsigned j=0;
ar_copy4_pair(h,r2,r3,a,b,c,t);
root_or::solve(h,c,t);root_or::solve(h,c+h,t+h);root_or::solve(r2,c+2*h,t+2*h);if(r3)root_or::solve(r3,c+3*h,t+3*h);
unsigned*x=c;
j=0;
for(;j+8<=r3;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));auto d=_mm256_load_si256((const __m256i*)(x+3*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_sub_epi32(c,a));_mm256_store_si256((__m256i*)(x+3*h+j),_mm256_sub_epi32(_mm256_add_epi32(d,a),_mm256_add_epi32(b,c)));}
}
for(;j<r3;j++){x[3*h+j]+=x[j]-x[h+j]-x[2*h+j];x[2*h+j]-=x[j];x[h+j]-=x[j];}
for(;j+8<=r2;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));auto c=_mm256_load_si256((const __m256i*)(x+2*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));_mm256_store_si256((__m256i*)(x+2*h+j),_mm256_sub_epi32(c,a));}
}
for(;j<r2;j++){x[2*h+j]-=x[j];x[h+j]-=x[j];}
for(;j+8<=h;j+=8){
{auto a=_mm256_load_si256((const __m256i*)(x+0*h+j));auto b=_mm256_load_si256((const __m256i*)(x+1*h+j));_mm256_store_si256((__m256i*)(x+1*h+j),_mm256_sub_epi32(b,a));}
}
for(;j<h;j++){x[h+j]-=x[j];}
free(root_allocation);
}
template<bool Inv,unsigned Q>static inline void ar_or_roots(__m256i(&v)[Q]){
#pragma GCC unroll 3
for(unsigned st=0;st<3;st++){unsigned bit=Inv?2-st:st;
#pragma GCC unroll 8
for(unsigned q=0;q<Q;q++)if(q&(1u<<bit)){if constexpr(Inv)v[q]=_mm256_sub_epi32(v[q],v[q^(1u<<bit)]);else v[q]=_mm256_add_epi32(v[q],v[q^(1u<<bit)]);}}
}
template<bool Last>static inline __attribute__((always_inline))void or6fw(const unsigned*src,unsigned*dst){if constexpr(Last){asm volatile(R"or64(
vmovdqa 0(%[src]),%%ymm0
vmovdqa 32(%[src]),%%ymm6
vmovdqa 67108864(%[src]),%%ymm1
vmovdqa 67108896(%[src]),%%ymm7
vmovdqa 134217728(%[src]),%%ymm2
vmovdqa 134217760(%[src]),%%ymm8
vmovdqa 201326592(%[src]),%%ymm3
vmovdqa 201326624(%[src]),%%ymm9
vmovdqa 268435456(%[src]),%%ymm4
vmovdqa 268435488(%[src]),%%ymm10
vmovdqa 335544320(%[src]),%%ymm5
vmovdqa 335544352(%[src]),%%ymm11
vpaddd %%ymm0,%%ymm1,%%ymm1
vpaddd %%ymm6,%%ymm7,%%ymm7
vpaddd %%ymm2,%%ymm3,%%ymm3
vpaddd %%ymm8,%%ymm9,%%ymm9
vpaddd %%ymm4,%%ymm5,%%ymm5
vpaddd %%ymm10,%%ymm11,%%ymm11
vpaddd %%ymm0,%%ymm2,%%ymm2
vpaddd %%ymm6,%%ymm8,%%ymm8
vpaddd %%ymm1,%%ymm3,%%ymm3
vpaddd %%ymm7,%%ymm9,%%ymm9
vpaddd %%ymm0,%%ymm4,%%ymm4
vpaddd %%ymm6,%%ymm10,%%ymm10
vpaddd %%ymm1,%%ymm5,%%ymm5
vpaddd %%ymm7,%%ymm11,%%ymm11
vmovdqa %%ymm0,0(%[dst])
vmovdqa %%ymm6,32(%[dst])
vmovdqa %%ymm1,33792(%[dst])
vmovdqa %%ymm7,33824(%[dst])
vmovdqa %%ymm2,67584(%[dst])
vmovdqa %%ymm8,67616(%[dst])
vmovdqa %%ymm3,101376(%[dst])
vmovdqa %%ymm9,101408(%[dst])
vmovdqa %%ymm4,135168(%[dst])
vmovdqa %%ymm10,135200(%[dst])
vmovdqa %%ymm5,168960(%[dst])
vmovdqa %%ymm11,168992(%[dst])
)or64"::[src]"r"(src),[dst]"r"(dst):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","memory");}else{asm volatile(R"or64(
vmovdqa 0(%[src]),%%ymm0
vmovdqa 32(%[src]),%%ymm6
vmovdqa 67108864(%[src]),%%ymm1
vmovdqa 67108896(%[src]),%%ymm7
vmovdqa 134217728(%[src]),%%ymm2
vmovdqa 134217760(%[src]),%%ymm8
vmovdqa 201326592(%[src]),%%ymm3
vmovdqa 201326624(%[src]),%%ymm9
vmovdqa 268435456(%[src]),%%ymm4
vmovdqa 268435488(%[src]),%%ymm10
vpxor %%ymm5,%%ymm5,%%ymm5
vpxor %%ymm11,%%ymm11,%%ymm11
vpaddd %%ymm0,%%ymm1,%%ymm1
vpaddd %%ymm6,%%ymm7,%%ymm7
vpaddd %%ymm2,%%ymm3,%%ymm3
vpaddd %%ymm8,%%ymm9,%%ymm9
vpaddd %%ymm4,%%ymm5,%%ymm5
vpaddd %%ymm10,%%ymm11,%%ymm11
vpaddd %%ymm0,%%ymm2,%%ymm2
vpaddd %%ymm6,%%ymm8,%%ymm8
vpaddd %%ymm1,%%ymm3,%%ymm3
vpaddd %%ymm7,%%ymm9,%%ymm9
vpaddd %%ymm0,%%ymm4,%%ymm4
vpaddd %%ymm6,%%ymm10,%%ymm10
vpaddd %%ymm1,%%ymm5,%%ymm5
vpaddd %%ymm7,%%ymm11,%%ymm11
vmovdqa %%ymm0,0(%[dst])
vmovdqa %%ymm6,32(%[dst])
vmovdqa %%ymm1,33792(%[dst])
vmovdqa %%ymm7,33824(%[dst])
vmovdqa %%ymm2,67584(%[dst])
vmovdqa %%ymm8,67616(%[dst])
vmovdqa %%ymm3,101376(%[dst])
vmovdqa %%ymm9,101408(%[dst])
vmovdqa %%ymm4,135168(%[dst])
vmovdqa %%ymm10,135200(%[dst])
vmovdqa %%ymm5,168960(%[dst])
vmovdqa %%ymm11,168992(%[dst])
)or64"::[src]"r"(src),[dst]"r"(dst):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","memory");}}
template<bool Last>static inline __attribute__((always_inline))void or6inv(const unsigned*src,unsigned*dst){if constexpr(Last){asm volatile(R"or64(
vmovdqa 0(%[src]),%%ymm0
vmovdqa 32(%[src]),%%ymm6
vmovdqa 67108864(%[src]),%%ymm1
vmovdqa 67108896(%[src]),%%ymm7
vmovdqa 134217728(%[src]),%%ymm2
vmovdqa 134217760(%[src]),%%ymm8
vmovdqa 201326592(%[src]),%%ymm3
vmovdqa 201326624(%[src]),%%ymm9
vmovdqa 268435456(%[src]),%%ymm4
vmovdqa 268435488(%[src]),%%ymm10
vmovdqa 335544320(%[src]),%%ymm5
vmovdqa 335544352(%[src]),%%ymm11
vpsubd %%ymm0,%%ymm4,%%ymm4
vpsubd %%ymm6,%%ymm10,%%ymm10
vpsubd %%ymm1,%%ymm5,%%ymm5
vpsubd %%ymm7,%%ymm11,%%ymm11
vpsubd %%ymm0,%%ymm2,%%ymm2
vpsubd %%ymm6,%%ymm8,%%ymm8
vpsubd %%ymm1,%%ymm3,%%ymm3
vpsubd %%ymm7,%%ymm9,%%ymm9
vpsubd %%ymm0,%%ymm1,%%ymm1
vpsubd %%ymm6,%%ymm7,%%ymm7
vpsubd %%ymm2,%%ymm3,%%ymm3
vpsubd %%ymm8,%%ymm9,%%ymm9
vpsubd %%ymm4,%%ymm5,%%ymm5
vpsubd %%ymm10,%%ymm11,%%ymm11
vmovdqa %%ymm0,0(%[dst])
vmovdqa %%ymm6,32(%[dst])
vmovdqa %%ymm1,33792(%[dst])
vmovdqa %%ymm7,33824(%[dst])
vmovdqa %%ymm2,67584(%[dst])
vmovdqa %%ymm8,67616(%[dst])
vmovdqa %%ymm3,101376(%[dst])
vmovdqa %%ymm9,101408(%[dst])
vmovdqa %%ymm4,135168(%[dst])
vmovdqa %%ymm10,135200(%[dst])
vmovdqa %%ymm5,168960(%[dst])
vmovdqa %%ymm11,168992(%[dst])
)or64"::[src]"r"(src),[dst]"r"(dst):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","memory");}else{asm volatile(R"or64(
vmovdqa 0(%[src]),%%ymm0
vmovdqa 32(%[src]),%%ymm6
vmovdqa 67108864(%[src]),%%ymm1
vmovdqa 67108896(%[src]),%%ymm7
vmovdqa 134217728(%[src]),%%ymm2
vmovdqa 134217760(%[src]),%%ymm8
vmovdqa 201326592(%[src]),%%ymm3
vmovdqa 201326624(%[src]),%%ymm9
vmovdqa 268435456(%[src]),%%ymm4
vmovdqa 268435488(%[src]),%%ymm10
vpxor %%ymm5,%%ymm5,%%ymm5
vpxor %%ymm11,%%ymm11,%%ymm11
vpsubd %%ymm0,%%ymm4,%%ymm4
vpsubd %%ymm6,%%ymm10,%%ymm10
vpsubd %%ymm1,%%ymm5,%%ymm5
vpsubd %%ymm7,%%ymm11,%%ymm11
vpsubd %%ymm0,%%ymm2,%%ymm2
vpsubd %%ymm6,%%ymm8,%%ymm8
vpsubd %%ymm1,%%ymm3,%%ymm3
vpsubd %%ymm7,%%ymm9,%%ymm9
vpsubd %%ymm0,%%ymm1,%%ymm1
vpsubd %%ymm6,%%ymm7,%%ymm7
vpsubd %%ymm2,%%ymm3,%%ymm3
vpsubd %%ymm8,%%ymm9,%%ymm9
vpsubd %%ymm4,%%ymm5,%%ymm5
vpsubd %%ymm10,%%ymm11,%%ymm11
vmovdqa %%ymm0,0(%[dst])
vmovdqa %%ymm6,32(%[dst])
vmovdqa %%ymm1,33792(%[dst])
vmovdqa %%ymm7,33824(%[dst])
vmovdqa %%ymm2,67584(%[dst])
vmovdqa %%ymm8,67616(%[dst])
vmovdqa %%ymm3,101376(%[dst])
vmovdqa %%ymm9,101408(%[dst])
vmovdqa %%ymm4,135168(%[dst])
vmovdqa %%ymm10,135200(%[dst])
vmovdqa %%ymm5,168960(%[dst])
vmovdqa %%ymm11,168992(%[dst])
)or64"::[src]"r"(src),[dst]"r"(dst):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","memory");}}
static inline __attribute__((always_inline))void or8fw(const unsigned*src,unsigned*dst,unsigned*out){asm volatile(R"or64(
vmovdqa 0(%[src]),%%ymm0
vmovdqa 32(%[src]),%%ymm8
vmovdqa 4224(%[src]),%%ymm1
vmovdqa 4256(%[src]),%%ymm9
vmovdqa 8448(%[src]),%%ymm2
vmovdqa 8480(%[src]),%%ymm10
vmovdqa 12672(%[src]),%%ymm3
vmovdqa 12704(%[src]),%%ymm11
vmovdqa 16896(%[src]),%%ymm4
vmovdqa 16928(%[src]),%%ymm12
vmovdqa 21120(%[src]),%%ymm5
vmovdqa 21152(%[src]),%%ymm13
vmovdqa 25344(%[src]),%%ymm6
vmovdqa 25376(%[src]),%%ymm14
vmovdqa 29568(%[src]),%%ymm7
vmovdqa 29600(%[src]),%%ymm15
vpaddd %%ymm0,%%ymm1,%%ymm1
vpaddd %%ymm8,%%ymm9,%%ymm9
vpaddd %%ymm2,%%ymm3,%%ymm3
vpaddd %%ymm10,%%ymm11,%%ymm11
vpaddd %%ymm4,%%ymm5,%%ymm5
vpaddd %%ymm12,%%ymm13,%%ymm13
vpaddd %%ymm6,%%ymm7,%%ymm7
vpaddd %%ymm14,%%ymm15,%%ymm15
vpaddd %%ymm0,%%ymm2,%%ymm2
vpaddd %%ymm8,%%ymm10,%%ymm10
vpaddd %%ymm1,%%ymm3,%%ymm3
vpaddd %%ymm9,%%ymm11,%%ymm11
vpaddd %%ymm4,%%ymm6,%%ymm6
vpaddd %%ymm12,%%ymm14,%%ymm14
vpaddd %%ymm5,%%ymm7,%%ymm7
vpaddd %%ymm13,%%ymm15,%%ymm15
vpaddd %%ymm0,%%ymm4,%%ymm4
vpaddd %%ymm8,%%ymm12,%%ymm12
vpaddd %%ymm1,%%ymm5,%%ymm5
vpaddd %%ymm9,%%ymm13,%%ymm13
vpaddd %%ymm2,%%ymm6,%%ymm6
vpaddd %%ymm10,%%ymm14,%%ymm14
vpaddd %%ymm3,%%ymm7,%%ymm7
vpaddd %%ymm11,%%ymm15,%%ymm15
vmovntdq %%ymm0,0(%[out])
vmovntdq %%ymm8,32(%[out])
vmovntdq %%ymm1,8388608(%[out])
vmovntdq %%ymm9,8388640(%[out])
vmovdqa %%ymm2,8448(%[dst])
vmovdqa %%ymm10,8480(%[dst])
vmovdqa %%ymm3,12672(%[dst])
vmovdqa %%ymm11,12704(%[dst])
vmovdqa %%ymm4,16896(%[dst])
vmovdqa %%ymm12,16928(%[dst])
vmovdqa %%ymm5,21120(%[dst])
vmovdqa %%ymm13,21152(%[dst])
vmovdqa %%ymm6,25344(%[dst])
vmovdqa %%ymm14,25376(%[dst])
vmovdqa %%ymm7,29568(%[dst])
vmovdqa %%ymm15,29600(%[dst])
)or64"::[src]"r"(src),[dst]"r"(dst),[out]"r"(out):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15","memory");}
static inline __attribute__((always_inline))void or8inv(const unsigned*src,unsigned*dst,unsigned*out){asm volatile(R"or64(
vmovdqa 0(%[src]),%%ymm0
vmovdqa 32(%[src]),%%ymm8
vmovdqa 4224(%[src]),%%ymm1
vmovdqa 4256(%[src]),%%ymm9
vmovdqa 8448(%[src]),%%ymm2
vmovdqa 8480(%[src]),%%ymm10
vmovdqa 12672(%[src]),%%ymm3
vmovdqa 12704(%[src]),%%ymm11
vmovdqa 16896(%[src]),%%ymm4
vmovdqa 16928(%[src]),%%ymm12
vmovdqa 21120(%[src]),%%ymm5
vmovdqa 21152(%[src]),%%ymm13
vmovdqa 25344(%[src]),%%ymm6
vmovdqa 25376(%[src]),%%ymm14
vmovdqa 29568(%[src]),%%ymm7
vmovdqa 29600(%[src]),%%ymm15
vpsubd %%ymm0,%%ymm4,%%ymm4
vpsubd %%ymm8,%%ymm12,%%ymm12
vpsubd %%ymm1,%%ymm5,%%ymm5
vpsubd %%ymm9,%%ymm13,%%ymm13
vpsubd %%ymm2,%%ymm6,%%ymm6
vpsubd %%ymm10,%%ymm14,%%ymm14
vpsubd %%ymm3,%%ymm7,%%ymm7
vpsubd %%ymm11,%%ymm15,%%ymm15
vpsubd %%ymm0,%%ymm2,%%ymm2
vpsubd %%ymm8,%%ymm10,%%ymm10
vpsubd %%ymm1,%%ymm3,%%ymm3
vpsubd %%ymm9,%%ymm11,%%ymm11
vpsubd %%ymm4,%%ymm6,%%ymm6
vpsubd %%ymm12,%%ymm14,%%ymm14
vpsubd %%ymm5,%%ymm7,%%ymm7
vpsubd %%ymm13,%%ymm15,%%ymm15
vpsubd %%ymm0,%%ymm1,%%ymm1
vpsubd %%ymm8,%%ymm9,%%ymm9
vpsubd %%ymm2,%%ymm3,%%ymm3
vpsubd %%ymm10,%%ymm11,%%ymm11
vpsubd %%ymm4,%%ymm5,%%ymm5
vpsubd %%ymm12,%%ymm13,%%ymm13
vpsubd %%ymm6,%%ymm7,%%ymm7
vpsubd %%ymm14,%%ymm15,%%ymm15
vmovntdq %%ymm0,0(%[out])
vmovntdq %%ymm8,32(%[out])
vmovntdq %%ymm1,8388608(%[out])
vmovntdq %%ymm9,8388640(%[out])
vmovdqa %%ymm2,8448(%[dst])
vmovdqa %%ymm10,8480(%[dst])
vmovdqa %%ymm3,12672(%[dst])
vmovdqa %%ymm11,12704(%[dst])
vmovdqa %%ymm4,16896(%[dst])
vmovdqa %%ymm12,16928(%[dst])
vmovdqa %%ymm5,21120(%[dst])
vmovdqa %%ymm13,21152(%[dst])
vmovdqa %%ymm6,25344(%[dst])
vmovdqa %%ymm14,25376(%[dst])
vmovdqa %%ymm7,29568(%[dst])
vmovdqa %%ymm15,29600(%[dst])
)or64"::[src]"r"(src),[dst]"r"(dst),[out]"r"(out):"ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","ymm8","ymm9","ymm10","ymm11","ymm12","ymm13","ymm14","ymm15","memory");}
static void root8_wave(const unsigned*a,const unsigned*b,unsigned*c){
constexpr unsigned H=16777216,R=16113920,L=H/8,T=1024,LP=T+32;
alignas(4096)static unsigned work[6*H+384];unsigned*t=work+384,*last=c+5*H;
alignas(64)static unsigned sc[1][6][8][LP];
for(unsigned j0=0;j0<L;j0+=T){
for(unsigned side=0;side<2;side++){
const unsigned*in=side?b:a;
for(unsigned rr=0;rr<8;rr++)for(unsigned j=0;j<T;j+=16){unsigned off=rr*L+j0+j;if(off<R)or6fw<true>(in+off,sc[0][0][rr]+j);else or6fw<false>(in+off,sc[0][0][rr]+j);}
for(unsigned q=0;q<6;q++){
for(unsigned j=0;j<T;j+=16){unsigned*out=side?t+q*H:(q==5?last:c+q*H);or8fw(sc[0][q][0]+j,sc[0][q][0]+j,out+j0+j);}
unsigned*out=side?t+q*H:(q==5?last:c+q*H);
for(unsigned rr=2;rr<8;rr++){
#pragma GCC unroll 8
for(unsigned j=0;j<T;j+=8)if(side||q<5||rr*L+j0+j<R)_mm256_stream_si256((__m256i*)(out+rr*L+j0+j),_mm256_load_si256((const __m256i*)(sc[0][q][rr]+j)));}
}
}
}
_mm_sfence();
for(unsigned q=0;q<6;q++)for(unsigned rr=0;rr<8;rr++){unsigned off=rr*L,z=q<5?L:(off<R?std::min(L,R-off):0);if(z)root_or::solve(z,(q==5?last:c+q*H)+off,t+q*H+off);}
for(unsigned j0=0;j0<L;j0+=T){
for(unsigned rr=0;rr<8;rr++)for(unsigned j=0;j<T;j+=16){unsigned off=rr*L+j0+j;if(off<R)or6inv<true>(c+off,sc[0][0][rr]+j);else or6inv<false>(c+off,sc[0][0][rr]+j);}
for(unsigned q=0;q<6;q++){
for(unsigned j=0;j<T;j+=16)or8inv(sc[0][q][0]+j,sc[0][q][0]+j,c+q*H+j0+j);
for(unsigned rr=2;rr<8;rr++){
#pragma GCC unroll 8
for(unsigned j=0;j<T;j+=8){unsigned off=rr*L+j0+j;if(q<5||off<R)_mm256_stream_si256((__m256i*)(c+q*H+off),_mm256_load_si256((const __m256i*)(sc[0][q][rr]+j)));}}
}
}
_mm_sfence();
}
void convolution(unsigned n,const unsigned*a,const unsigned*b,unsigned*c){if(n==100000000u)root8_wave(a,b,c);else fallback_convolution(n,a,b,c);}