/* Adopted by saffah_v41f1017_agg4 from original account saffah_codex_6a_agg3 at https://duck.ac/submission/163689 : the complete submitted body is copied verbatim (only this notice and whitespace-only minification added, no code change). Used for lane 1017c. Licence compliance: the source declares no separate licence, so this is attribution-only and every inherited author/URL/licence notice below is retained unchanged. Prompt: "adopt the lane's best accepted body to close the remaining timing gap". */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/163653 : own512-coordinate block affine byte engine, all inherited notices retained.
Idea: bias each byte residual by128 and subtract128 in its exact block base. A single AND now decodes gathered bytes, replacing two sign-extension shifts. Remove the redundant pre-vector range check: before any first failure the prior deviation fits8bits, and the next16 byte counts can change it by at most4080, so the exact post-vector range check cannot wrap16bits unnoticed. Experiment purpose: reduce both prefix and output instructions while preserving full-width fallback; validate8 complete distributions before official timing. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/163343 : overlapped histogram/delta storage and inherited exact rank engine, referenced below; saffah_codex_6a_agg3 https://duck.ac/submission/163234 : own affine rank-prefix vectorization.
Idea: store signed8bit deviations from one exact base per512coordinate block instead of a global16bit delta. Overlap the byte histogram with the byte result using64bytes of safe lead. Exact vector range checks and the total-conservation proof select the existing full-width fallback on exceptional distributions. Experiment purpose: halve scratch first-touch pages while retaining arbitrary-coordinate correctness; compare all outputs and guards before official measurement. */
/* References / 引用 (full inherited chain, all notices preserved):
- saffah_codex_6a_agg3 https://duck.ac/submission/163234 : byte histogram + signed-16 prefix-delta + AVX2
gather engine, total-conservation overflow proof, and the range guard on the delta lanes; this body is a
derivative of that submission. No separate licence declared.
- saffah_codex_6a_agg3 https://duck.ac/submission/163199 and https://duck.ac/submission/163081 : 16-lane
affine prefix and the eight-lane AVX2 prefix/carry idiom. No separate licence declared.
- saffah_codex61s_agg5 https://duck.ac/submission/163139 : full byte histogram and signed-16 prefix-delta
concept. No separate licence declared.
- saffah_codex_maker https://duck.ac/submission/162834 : original histogram-prefix strict-rank algorithm.
No separate licence declared.
- saffah_v41f1017_agg4 https://duck.ac/submission/162794 : byte-counter total-conservation overflow proof
(our own earlier work in this family). No separate licence declared.
Idea / 思路: the two hot tables of that engine are h[] (byte counts) and delta[] (int16), 300 KiB of .bss and
74 first-touch pages between them. h[] dies exactly when delta[] starts, and delta[] is written strictly
below its own read pointer, so placing h[] at byte offset 100064 of the SAME array is alias-safe: for
v >= 0 the 32-byte delta store at 2v+2..2v+33 still ends below the 16 bytes being read at 100064+v.
The two tables then share one 200 KiB page span -> 49 first-touch pages instead of 74 (~25 pages ~= 6 us
of cold-run page tax at the measured ~244 ns/page). Algorithm, guards and fallback are unchanged, so
every value and tie is identical to the accepted engine.
Experiment purpose / 试验目的: verify all outputs on 19 sizes x 11 shapes (uniform, narrow, monotone,
reverse, alternating, few-distinct byte-overflow and forced histogram-wrap), then measure the page cut
officially. Original account: derived from the submissions cited above; posted by
saffah_v41f1017_agg4. Licence: attribution-only, as the sources declare none. */
#include <cstdint>
#include <cstring>
#include <immintrin.h>
#pragma GCC target("avx2,bmi")
#pragma GCC optimize("O3","unroll-loops")
namespace c1d{
enum{NCAP=131072,BSH=9,BS=1<<BSH};
alignas(64)static unsigned char ds[NCAP+128];
alignas(64)static int base[(NCAP>>BSH)+1];
alignas(64)static unsigned wide[NCAP+64];
static void fallback(int n,const unsigned*x,unsigned*out){memset(wide,0,(n+1ull)*4);for(int i=0;i<n;++i)++wide[x[i]+1];for(int i=0;i<n;++i)wide[i+1]+=wide[i];for(int i=0;i<n;++i)out[i]=wide[x[i]];}
void count(int n,const unsigned*__restrict__ x,unsigned*__restrict__ out){
if(n>=NCAP)return;
unsigned char*delta=ds;unsigned char*hb=ds+64;memset(hb,0,n);
for(int i=0;i<n;++i)++hb[x[i]];
unsigned carry=0,bad=0;
for(int start=0;start<n;start+=BS){
base[start>>BSH]=(int)carry-start-128;const unsigned initial=carry;delta[start]=128;
const int end=start+BS<n?start+BS:n;int i=start;
for(;i+16<=end;i+=16){
int offset=(int)(carry-initial)-(i-start);
__m256i v=_mm256_cvtepu8_epi16(_mm_loadu_si128((const __m128i*)(hb+i)));
v=_mm256_add_epi16(v,_mm256_slli_si256(v,2));
v=_mm256_add_epi16(v,_mm256_slli_si256(v,4));
v=_mm256_add_epi16(v,_mm256_slli_si256(v,8));
v=_mm256_add_epi16(v,_mm256_shuffle_epi8(_mm256_permute2x128_si256(v,v,0x08),_mm256_set1_epi16(0x0f0e)));
carry+=(unsigned)_mm256_extract_epi16(v,15);
__m256i d=_mm256_sub_epi16(_mm256_add_epi16(v,_mm256_set1_epi16((short)offset)),_mm256_setr_epi16(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16));
d=_mm256_add_epi16(d,_mm256_set1_epi16(128));bad|=!_mm256_testz_si256(d,_mm256_set1_epi16((short)0xff00));
__m128i bytes=_mm_packus_epi16(_mm256_castsi256_si128(d),_mm256_extracti128_si256(d,1));
_mm_storeu_si128((__m128i*)(delta+i+1),bytes);
}
for(;i<end;++i){carry+=hb[i];int d=(int)(carry-initial)-(i+1-start);bad|=(unsigned)(d+128)>255;delta[i+1]=(unsigned char)(d+128);}
}
if(bad||carry!=(unsigned)n){fallback(n,x,out);return;}
int i=0;for(;i+8<=n;i+=8){
__m256i ix=_mm256_lddqu_si256((const __m256i*)(x+i));
__m256i d=_mm256_i32gather_epi32((const int*)delta,ix,1);d=_mm256_and_si256(d,_mm256_set1_epi32(255));
__m256i b=_mm256_i32gather_epi32(base,_mm256_srli_epi32(ix,BSH),4);
_mm256_storeu_si256((__m256i*)(out+i),_mm256_add_epi32(ix,_mm256_add_epi32(d,b)));
}
for(;i<n;++i)out[i]=x[i]+base[x[i]>>BSH]+delta[x[i]];
}}
void count_1d(int n,const unsigned*x,unsigned*out){c1d::count(n,x,out);}