/* References / 引用:
saffah_codex_6a_agg3 https://duck.ac/submission/163689: directly copy the complete512-coordinate byte-affine histogram/prefix/rank-gather engine and all inherited author/full URL/use/licence notices below:
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.
saffah_codex61s_agg5 https://duck.ac/submission/163690: our four independent16-coordinate prefix scans and64-coordinate carry combination, adapted from signed16 global deltas to guarded biased-byte local deltas. No outside or separately licensed code is added.
Approach / 思路: Build four prefix vectors independently before composing their exact carry offsets. Load all64 source histogram bytes before writing any overlapped destination bytes; preserve64-byte lead and every byte-range/total-conservation fallback check. Output mode=stream_gatherbase: original temporal8, aligned non-temporal16 with two gathers, or non-temporal16 with scalar L1 block-base loads. Scalar prologue/tails preserve arbitrary output alignment.
Experiment purpose / 试验目的: Full100k reference/128brutes plus five complete independent sorted-oracle shapes and guards before immediate official timing. No local performance veto.
*/
#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]];}
static inline __m256i byte_prefix16(const unsigned char*p){__m256i v=_mm256_cvtepu8_epi16(_mm_loadu_si128((const __m128i*)p));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));return _mm256_add_epi16(v,_mm256_shuffle_epi8(_mm256_permute2x128_si256(v,v,0x08),_mm256_set1_epi16(0x0f0e)));}
static inline void byte_prefix_write(unsigned char*p,__m256i v,int offset,unsigned&bad){auto 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));_mm_storeu_si128((__m128i*)p,_mm_packus_epi16(_mm256_castsi256_si128(d),_mm256_extracti128_si256(d,1)));}
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+64<=end;i+=64){auto a=byte_prefix16(hb+i),b=byte_prefix16(hb+i+16),c=byte_prefix16(hb+i+32),d=byte_prefix16(hb+i+48);unsigned sa=_mm256_extract_epi16(a,15),sb=_mm256_extract_epi16(b,15),sc=_mm256_extract_epi16(c,15),sd=_mm256_extract_epi16(d,15);int offset=(int)(carry-initial)-(i-start);byte_prefix_write(delta+i+1,a,offset,bad);byte_prefix_write(delta+i+17,b,offset+(int)sa-16,bad);byte_prefix_write(delta+i+33,c,offset+(int)(sa+sb)-32,bad);byte_prefix_write(delta+i+49,d,offset+(int)(sa+sb+sc)-48,bad);carry+=sa+sb+sc+sd;}
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<n&&((uintptr_t)(out+i)&31);++i)out[i]=x[i]+base[x[i]>>BSH]+delta[x[i]];for(;i+16<=n;i+=16){{__m256i ix=_mm256_lddqu_si256((const __m256i*)(x+i+0));__m256i d=_mm256_and_si256(_mm256_i32gather_epi32((const int*)delta,ix,1),_mm256_set1_epi32(255));__m256i b=_mm256_i32gather_epi32(base,_mm256_srli_epi32(ix,BSH),4);_mm256_stream_si256((__m256i*)(out+i+0),_mm256_add_epi32(ix,_mm256_add_epi32(d,b)));}{__m256i ix=_mm256_lddqu_si256((const __m256i*)(x+i+8));__m256i d=_mm256_and_si256(_mm256_i32gather_epi32((const int*)delta,ix,1),_mm256_set1_epi32(255));__m256i b=_mm256_i32gather_epi32(base,_mm256_srli_epi32(ix,BSH),4);_mm256_stream_si256((__m256i*)(out+i+8),_mm256_add_epi32(ix,_mm256_add_epi32(d,b)));}}_mm_sfence();
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);}