// 1008e8 -- 2D dominance counting, n = 1e8: out[i] = #{j: x[j]<x[i] and y[j]<y[i]}
//
// v6 = v5's memory-fitted design with the random y gathers removed. On the judge
// v5 was AC at 14.263 s, and a variant whose gather was replaced by a cheap hash
// of idx ran 6.207 s -- so ~8 s of v5 was 1e8 random reads into the 400 MB y
// array (4 KB pages -> TLB miss + page walk on almost every one). Here y is
// permuted in lockstep with the x radix sort (an extra 4-byte stream per pass,
// ~2.4 GB of extra traffic in total, far cheaper than the gathers).
//
// The problem is split by the y median so each half fits:
// y_i < K : out[i] = #{j: y_j<y_i, x_j<x_i} (all such j are low)
// y_i >= K : out[i] = #{j low: x_j < x_i} + #{j high: y_j<y_i, x_j<x_i}
// The cross term is one sequential merge of the two x-sorted key arrays.
//
// Record encoding
// during split/sort : [spare:11 | idx:27 | x:27] (x in the low bits)
// after attach : [cnt:11 | idx:27 | y:26] (y shifted into [0,2^26))
// The per-element count is 27 bits: 11 in the record + the top 16 in a u16 array,
// so every count travels with its element and out[] never receives a random RMW.
//
// Buffers (M = n/2 + slack): RA,RB,RC u64[M] (~400 MB each), Y1,Y2 u32[M]
// (~200 MB each), U1 u16[M] (100 MB) = ~1.66 GB of our own, plus the tasklib's
// out (400 MB) which holds the answers (and nothing else).
#include <cstdint>
#include <cstring>
#include <cstdlib>
#include <sys/mman.h>
#include <immintrin.h>
#include <cstdio>
#include <time.h>
#define PHN 12
static double g_ph[PHN]; static const char *g_pn[PHN]={"splitA","sort_xA","attachA","levelsA","emitA","splitB","sort_xB","cross","attachB","levelsB","emitB","TOTAL"};
static inline double phnow(){struct timespec t;clock_gettime(CLOCK_MONOTONIC,&t);return t.tv_sec+t.tv_nsec*1e-9;}
void phdump(){for(int i=0;i<PHN;i++)fprintf(stderr,"PHASE %-9s %8.3f s\n",g_pn[i],g_ph[i]);}
#ifndef NO_AVX2
#pragma GCC push_options
#pragma GCC target("avx2")
#endif
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
static const u64 M27 = 0x7FFFFFFull;
static const u64 LOW53 = 0x1FFFFFFFFFFFFFull; // idx:27 | y:26
static u64 *RAB, *RA, *RB, *RC; // ARM m155: RA/RB are the two halves of one pool
static u32 *Y12, *Y1, *Y2; // Y1/Y2 likewise (branchless half select)
static u16 *U1;
static size_t gCap;
static const unsigned *gX, *gY;
static unsigned *gOut;
static u32 gCnt[4096];
static u32 gH12[1024]; // ARM m155: [0..511] low half's L1-digit hist, [512..] high
static u32 gNxt[512]; // histogram of the NEXT radix pass, built during the current scatter
static u32 gBndL2[520]; // L2 bucket boundaries inside the current L1 bucket
static u32 gBndL1[520];
static size_t gOutLim = 0;
static u32 gCur[4096];
static u32 gIdxH[1032]; // SC1-B: idx digit = idx>>17, 1024 buckets
static u32 gIdxCur[1024]; // per-idx-digit write cursor
static u32 gBnd2[512][513]; // per-L1-bucket L2 boundaries (phase split)
// ---- branchless 8x8x8 cumulative digit counter: query = 3 loads, insert = 3
// masked SIMD suffix adds over 8-lane u32; 2 KB of state, all L1 resident.
static u32 gP1[8];
static u32 gP2[8][8];
static u32 gP3[8][8][8];
static u32 gMsk[8][8] __attribute__((aligned(32)));
static int gMskInit = 0;
static inline void cnt_init(void) {
if (!gMskInit) {
for (u32 m = 0; m < 8; m++)
for (u32 i = 0; i < 8; i++) gMsk[m][i] = (i > m);
gMskInit = 1;
}
memset(gP1, 0, sizeof(gP1));
memset(gP2, 0, sizeof(gP2));
memset(gP3, 0, sizeof(gP3));
}
static inline u32 cnt_q(u32 d) {
u32 a = d >> 6, b = (d >> 3) & 7, c = d & 7;
return gP1[a] + gP2[a][b] + gP3[a][b][c];
}
static inline void cnt_ins(u32 d) {
u32 a = d >> 6, b = (d >> 3) & 7, c = d & 7;
// ARM m155 MASKDROP: gMsk[m][i] is `(i > m)`, i.e. ALREADY 0/1, so `and(mask, one)` was an
// identity and the `one` broadcast bought nothing: 3 vpand + 3 broadcasts per insert removed.
__m256i v3 = _mm256_loadu_si256((const __m256i *)&gP3[a][b][0]);
_mm256_storeu_si256((__m256i *)&gP3[a][b][0],
_mm256_add_epi32(v3, _mm256_load_si256((const __m256i *)gMsk[c])));
__m256i v2 = _mm256_loadu_si256((const __m256i *)&gP2[a][0]);
_mm256_storeu_si256((__m256i *)&gP2[a][0],
_mm256_add_epi32(v2, _mm256_load_si256((const __m256i *)gMsk[b])));
__m256i v1 = _mm256_loadu_si256((const __m256i *)&gP1[0]);
_mm256_storeu_si256((__m256i *)&gP1[0],
_mm256_add_epi32(v1, _mm256_load_si256((const __m256i *)gMsk[a])));
}
// CI4: ported from the SIBLING row 1008 (which boards this; 1008e8 did not carry it).
// The top counter level is held in a YMM register and queried with vpermd, so the
// per-element 4-byte load from a just-written 32-byte store (store->load-forward
// failure) disappears, as does the 32-byte store itself.
static inline u32 lane8(__m256i v, u32 a) {
__m256i sel = _mm256_permutevar8x32_epi32(v, _mm256_set1_epi32((int)a));
return (u32)_mm_cvtsi128_si32(_mm256_castsi256_si128(sel));
}
static inline u32 cnt_qv(u32 d, __m256i P1v) {
u32 a = d >> 6, b = (d >> 3) & 7, c = d & 7;
return lane8(P1v, a) + gP2[a][b] + gP3[a][b][c];
}
static inline void cnt_insv(u32 d, __m256i &P1v) {
u32 a = d >> 6, b = (d >> 3) & 7, c = d & 7;
__m256i v3 = _mm256_loadu_si256((const __m256i *)&gP3[a][b][0]);
_mm256_storeu_si256((__m256i *)&gP3[a][b][0], _mm256_add_epi32(v3, _mm256_load_si256((const __m256i *)gMsk[c])));
__m256i v2 = _mm256_loadu_si256((const __m256i *)&gP2[a][0]);
_mm256_storeu_si256((__m256i *)&gP2[a][0], _mm256_add_epi32(v2, _mm256_load_si256((const __m256i *)gMsk[b])));
P1v = _mm256_add_epi32(P1v, _mm256_load_si256((const __m256i *)gMsk[a]));
}
static void *bigalloc(size_t bytes) {
void *p = mmap(0, bytes, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (p != MAP_FAILED) return p; // mmap fails on JudgeDuck -> malloc
return malloc(bytes);
}
// ------------------------------------------------------------------
// 3-pass LSD radix sort by x of [spare:11|idx:27|x:27] records, permuting the
// parallel y array with the identical permutation; the result ends in X1 / Yb.
//
// ARM: the histogram of each pass is DERIVED DURING THE PREVIOUS PASS'S SCATTER,
// where the record is already in a register -- the three standalone histogram
// sweeps over the records are gone. Pass 1's histogram must be supplied by the
// caller, which has x[i] in hand while it is already building the record.
static void sort_x(u64 *X0, u64 *X1, u32 *Ya, u32 *Yb, size_t m) {
// ---- pass 1: gCnt must already hold the histogram of (X0[i] & 511) ----
gCur[0] = 0;
for (u32 b = 1; b < 512; b++) gCur[b] = gCur[b - 1] + gCnt[b - 1];
memset(gNxt, 0, sizeof(gNxt));
for (size_t i = 0; i < m; i++) {
u64 rec = X0[i];
u32 q = gCur[(u32)rec & 511u]++;
X1[q] = rec;
Yb[q] = Ya[i];
gNxt[(u32)(rec >> 9) & 511u]++;
}
// ---- pass 2: gCnt <- gNxt (histogram of X1 >> 9), build pass 3's histogram ----
memcpy(gCnt, gNxt, sizeof(gNxt));
gCur[0] = 0;
for (u32 b = 1; b < 512; b++) gCur[b] = gCur[b - 1] + gCnt[b - 1];
memset(gNxt, 0, sizeof(gNxt));
for (size_t i = 0; i < m; i++) {
u64 rec = X1[i];
u32 q = gCur[(u32)(rec >> 9) & 511u]++;
X0[q] = rec;
Ya[q] = Yb[i];
gNxt[(u32)(rec >> 18) & 511u]++;
}
// ---- pass 3: gCnt <- gNxt (histogram of X0 >> 18) ----
memcpy(gCnt, gNxt, sizeof(gNxt));
gCur[0] = 0;
for (u32 b = 1; b < 512; b++) gCur[b] = gCur[b - 1] + gCnt[b - 1];
for (size_t i = 0; i < m; i++) {
u64 rec = X0[i];
u32 q = gCur[(u32)(rec >> 18) & 511u]++;
X1[q] = rec;
Yb[q] = Ya[i];
}
}
// ------------------------------------------------------------------
// y is already in sequence order (Yv); fold the x-tie correction into the 27-bit
// count, rewrite the record as [cnt:11|idx:27|y:26], histogram y's top digit.
// `preseed` = the count already holds the half's cross term (high half).
// ------------------------------------------------------------------
// FUSED attach + L1. The old code wrote an intermediate record
// [cnt:11|idx:27|y:26] into X, and levels()'s L1 pass read the WHOLE array back to
// scatter it into the L1 layout. Both the write and the read-back are gone: the two
// sweeps walked the same array in the same order, so the correction and the scatter
// belong in one loop. Per half this deletes ~911 MB of traffic at n=1e8.
static void attach_l1(u64 *X, const u32 *Yv, u32 *Xout, u64 *Dst, unsigned char *Cb,
const u32 *Pseed, size_t m, int preseed) {
gCur[0] = 0;
for (u32 b = 1; b <= 512; b++) gCur[b] = gCur[b - 1] + gCnt[b - 1];
for (u32 b = 0; b <= 512; b++) gBndL1[b] = gCur[b];
cnt_init();
// CI4 (port of sibling 1008's single-pass fusion): the x-group boundary is found by
// the element that CHANGES xv, so the separate q-scan (one dependent load+mask+cmp+
// branch per element over the whole array) is deleted. `gstart` replaces the group
// base; the dup loop still runs over exactly [group_start, a).
__m256i P1v = _mm256_setzero_si256();
size_t gstart = 0;
u64 prev_xv = ~(u64)0;
for (size_t a = 0; a < m; a++) {
u64 rec = X[a];
u64 xv = rec & M27;
if (xv != prev_xv) { gstart = a; prev_xv = xv; }
u32 ia = (u32)((rec >> 27) & M27);
u32 xvv = (u32)rec & (u32)M27;
u32 ya = Yv[a];
u32 dup = 0;
if (a > gstart) { for (size_t b = gstart; b < a; b++) dup += (Yv[b] < ya); }
u32 cnt = preseed ? Pseed[a] : 0u; // full 27-bit preseed, no record/side split
cnt = (cnt - dup) & 0x7FFFFFFu;
if (Xout) Xout[a] = xvv;
u32 d1 = (ya >> 17) & 511u;
cnt = (cnt + cnt_qv(d1, P1v)) & 0x7FFFFFFu;
cnt_insv(d1, P1v);
u32 qq = gCur[d1]++;
Dst[qq] = ((u64)(cnt & 0xFFFFFu) << 44) | ((u64)(ya & 0x1FFFFu) << 27) | (u64)ia;
// ^ (ya&255)<<27 | ((ya>>8)&511)<<35 -- the two shifts collapse into one, exactly
Cb[qq] = (unsigned char)(cnt >> 20); // cnt < 2^27, so cnt>>20 <= 127
}
}
// ------------------------------------------------------------------
// Two-pass MSD rank accumulation over the 26-bit y field (digits 9/9/8), with the
// last two digits resolved inside the L1 bucket (L1 cache resident) and out[] stored
// directly. Replaces sol_v6's four-pass L1/L2/L3/L4 chain.
//
// incoming (from attach): X0[t] = [cnt:11 @53..63 | idx:27 @26..52 | y:26 @0..25],
// Ca[t] = cnt >> 11 (array is x-sorted)
// working layout: [cntlo:20 @44..63 | d2:9 @35..43 | d3:8 @27..34 | idx:27 @0..26]
// side[q] = cnt >> 20 (low byte of the u16 side array)
// count <= n-1 < 2^27 => 20 + 8 bits is enough.
static void levels(u64 *X0, u64 *X1, u16 *Ca, unsigned char *Cb, size_t m, unsigned *out) {
// ---------------- L1 is done by attach_l1; L2 + L3 follow ----------
// ARM (lane l1008e8_1002): the L3 pass used to end in `out[idx] = cnt`, i.e.
// 1e8 random 4-byte stores into the 400 MB output array. Here the half is
// split into 512 buckets by the TOP 9 BITS OF idx (a digit the record already
// carried) and the L3 pass scatters (cnt<<27|idx) into those buckets instead.
// The global idx-digit histogram is built DURING the L2 histogram sweep (the
// record is in a register for free), so the split costs one extra 512-entry
// array, not an extra pass. The emit then walks the buckets in increasing idx
// order: 512 monotone windows of 195 313 slots, no page walk and no RFO storm.
memset(gIdxH, 0, sizeof(gIdxH));
// ---- phase A: L2 for every L1 bucket, plus the idx-digit histogram ----------
for (u32 b0 = 0; b0 < 512; b0++) {
size_t s = gBndL1[b0], e = gBndL1[b0 + 1];
if (e - s <= 1) {
if (e > s) { gIdxH[(u32)(X1[s] >> 17) & 1023u]++;
u32 c0 = ((u32)(X1[s] >> 44) | ((u32)Cb[s] << 20)) & 0x7FFFFFFu;
X0[s] = ((u64)c0 << 35) | (X1[s] & 0x00000007FFFFFFFFull); }
gBnd2[b0][0] = s; gBnd2[b0][1] = e;
continue;
}
// L2: histogram the d2 digit (bits 35..43) of this bucket
memset(gCnt, 0, 512 * sizeof(u32));
for (size_t t = s; t < e; t++) { u64 rc = X1[t];
gCnt[(u32)(rc >> 35) & 511u]++;
gIdxH[(u32)(rc >> 17) & 1023u]++; }
gCur[0] = 0;
for (u32 b = 1; b <= 512; b++) gCur[b] = gCur[b - 1] + gCnt[b - 1];
for (u32 b = 0; b <= 512; b++) gBnd2[b0][b] = s + gCur[b];
cnt_init();
__m256i P1v = _mm256_setzero_si256();
for (size_t t = s; t < e; t++) {
u64 rec = X1[t];
u32 d2 = (u32)(rec >> 35) & 511u;
u32 inc = cnt_qv(d2, P1v);
cnt_insv(d2, P1v);
u32 q = s + gCur[d2]++;
u32 cnt = (((u32)(rec >> 44) | ((u32)Cb[t] << 20)) + inc) & 0x7FFFFFFu;
/* keep d2(35..43), d3(27..34), idx(0..26) -- L3 run-keys on d2 */
X0[q] = ((u64)cnt << 35) | (rec & 0x00000007FFFFFFFFull);
}
}
// ---- prefix the idx-digit histogram; X1 is dead from here on ---------------
{ u32 run = 0;
for (u32 b = 0; b < 1024; b++) { u32 c = gIdxH[b]; gIdxCur[b] = run; run += c; } }
// ---- phase B: L3 for every L1 bucket, scattered 8 B into X1 (the idx bucket)
for (u32 b0 = 0; b0 < 512; b0++) {
size_t s = gBndL1[b0], e = gBndL1[b0 + 1];
if (e - s <= 1) {
if (e > s) { u64 rc = X0[s];
X1[gIdxCur[(u32)(rc >> 17) & 1023u]++] = rc; }
continue;
}
// L3 inside X0[s..e): runs of equal d2, digit d3 (bits 27..34).
for (u32 d2 = 0; d2 < 512; d2++) {
size_t p = gBnd2[b0][d2], qq = gBnd2[b0][d2 + 1];
if (qq <= p) continue;
if (qq - p == 1) {
u32 c0 = ((u32)(X0[p] >> 35)) & 0x7FFFFFFu;
X1[gIdxCur[(u32)(X0[p] >> 17) & 1023u]++] = ((u64)c0 << 27) | (X0[p] & M27);
} else {
cnt_init();
__m256i P1v = _mm256_setzero_si256();
for (size_t a = p; a < qq; a++) {
u64 rec = X0[a];
u32 d3 = (u32)(rec >> 27) & 255u;
u32 inc = cnt_qv(d3, P1v);
cnt_insv(d3, P1v);
u32 cnt = ((u32)(rec >> 35) + inc) & 0x7FFFFFFu;
X1[gIdxCur[(u32)(rec >> 17) & 1023u]++] = ((u64)cnt << 27) | (rec & M27);
}
}
}
}
}
// ARM: the emit. gIdxCur[b] now holds the END of idx-bucket b (it started at the
// bucket's prefix offset and was advanced once per element), so the buckets are
// already laid out in increasing idx order and out[] is filled by one forward sweep.
static void emit_idx_buckets(const u64 *Xb, size_t m, unsigned *out) {
size_t p = 0;
for (u32 b = 0; b < 1024; b++) {
size_t q = gIdxCur[b];
// ARM m155 EMITPF: out[idx] is a 4 B store into a ~390 KB window, so every line RFOs and the
// RFO latency is on the critical path. idx is already in the record 8 ahead (a sequential
// load), so the fetch can be issued before it is needed.
size_t lim = q > 8 ? q - 8 : p;
for (; p < lim; p++) {
_mm_prefetch((const char *)&out[(u32)(Xb[p + 8] & M27)], _MM_HINT_T0);
out[(u32)(Xb[p] & M27)] = (u32)(Xb[p] >> 27);
}
for (; p < q; p++) out[(u32)(Xb[p] & M27)] = (u32)(Xb[p] >> 27);
}
}
// ------------------------------------------------------------------
void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
double _t0=phnow();
if (n <= 0) return;
if (n == 1) { out[0] = 0; return; }
if (n <= 2000) {
memset(out, 0, (size_t)n * 4);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (x[j] < x[i] && y[j] < y[i]) out[i]++;
return;
}
size_t N = (size_t)n;
size_t M = N / 2 + 70000; // slack for the cut granularity
if (gCap < M) {
if (RAB) { munmap(RAB, gCap * 16); munmap(RC, gCap * 8); }
if (Y12) munmap(Y12, gCap * 8);
if (U1) munmap(U1, gCap * 2);
RAB = (u64 *)bigalloc(M * 16); // low half [0,M) | high half [M,2M) -- same 16 B/el
RC = (u64 *)bigalloc(M * 8);
Y12 = (u32 *)bigalloc(M * 8);
U1 = (u16 *)bigalloc(M * 2);
RA = RAB; RB = RAB + M;
Y1 = Y12; Y2 = Y12 + M;
gCap = M;
if (!RAB || !RC || !Y12 || !U1) { gCap = 0; return; }
}
gX = x; gY = y; gOut = out; gOutLim = N;
// ---- choose the y cut K: exact bucket boundaries over the top 11 bits of y
static u32 hist[2048];
memset(hist, 0, sizeof(hist));
for (size_t i = 0; i < N; i++) hist[y[i] >> 16]++;
size_t want = N / 2, acc = 0;
u32 K = 0;
for (u32 b = 0; b < 2048; b++) {
acc += hist[b];
if (acc >= want) { K = (b + 1) << 16; break; }
}
if (K == 0) K = 1u << 16;
size_t lo = acc, hi = N - acc;
// constraints: both halves fit their buffers, the high half fits out (8 bytes
// per record in 4 bytes per element), and both y ranges fit the 26-bit field
if (hi == 0 || lo >= M || hi > N / 2 || hi >= M || (u64)K > (1u << 26) ||
(u64)(N - K) > (1u << 26)) {
memset(out, 0, N * 4); // pathological input: bail out
for (size_t i = 0; i < N; i++)
for (size_t j = 0; j < N; j++)
if (x[j] < x[i] && y[j] < y[i]) out[i]++;
return;
}
// ---- ARM m155 SPLITFUSE: ONE sweep of x[]/y[] fills BOTH halves.
// The two old passes each read the same 8 B/el of x,y but write only one half, so the second
// read was pure waste. The half select is ARITHMETIC (`off = M-lo+hi` style, see below) so the
// loop has no data-dependent branch; the first attempt branched on `take` and cost 23 cyc/el
// vs the 17 cyc/el of the two passes it replaced -- measured, not guessed.
// Buffer routing that makes this possible with NO new allocation:
// * the low half's sorted-y output goes into `out` (the answer array, untouched until the
// emits; attach consumes it before emitA overwrites it);
// * the low half's count side array is U1 (free until the cross term writes it).
{
double _t = phnow();
memset(gCnt, 0, 1024 * sizeof(u32));
memset(gH12, 0, sizeof(gH12));
size_t alo = 0, ahi = 0;
for (size_t i = 0; i < N; i++) {
unsigned xi = x[i], yi = y[i];
unsigned th = (yi >= K); // 1 = high half
u32 yv = yi - (K & (0u - th)); // yi (low) or yi-K (high)
size_t off = alo + (size_t)th * (M - alo + ahi); // th==0 -> alo, th==1 -> M+ahi
RAB[off] = ((u64)i << 27) | (u64)xi;
Y12[off] = yv;
alo += (th ^ 1u); ahi += th;
gCnt[(th << 9) | (xi & 511u)] += 1;
gH12[(th << 9) | ((yv >> 17) & 511u)] += 1;
}
lo = alo; hi = ahi;
g_ph[0]+=phnow()-_t; }
// ---- low half: x sort (records -> RC, y -> Y2)
{ double _t=phnow();
sort_x(RA, RC, Y1, (u32 *)out, lo);
g_ph[1]+=phnow()-_t; }
// the low half's sorted x values are emitted by attach() itself (Y1 is free
// after sort_x's pass 3); the standalone copy sweep is gone
memcpy(gCnt, gH12, 512 * sizeof(u32));
{ double _t=phnow();
attach_l1(RC, (u32 *)out, Y1, RA, (unsigned char *)U1, (const u32 *)0, lo, 0);
g_ph[2]+=phnow()-_t; }
{ double _t=phnow();
levels(RC, RA, U1, (unsigned char *)U1, lo, out); // low half: buckets of (cnt,idx) in RA
g_ph[3]+=phnow()-_t; }
{ double _t=phnow();
emit_idx_buckets(RA, lo, out); // monotone sweep -> out
g_ph[4]+=phnow()-_t; }
// split B is done by the fused sweep above (g_ph[5] stays 0)
// ---- high half: x sort (records -> RC, y -> RA reused as a u32 buffer)
memcpy(gCnt, gCnt + 512, 512 * sizeof(u32)); // the fused sweep left it in slot 1
{ double _t=phnow();
sort_x(RB, RC, Y2, (u32 *)RA, hi);
g_ph[6]+=phnow()-_t; }
// ---- cross term: #{low: x_j < x_i} for every high element, one merge sweep
{
size_t a = 0; u32 run = 0; double _tc = phnow();
const size_t nblk = lo >> 3; size_t jb = 0; // ARM m155 CROSSBLK
for (size_t b = 0; b < hi; b++) {
u64 rec = RC[b];
u32 xb = (u32)rec & (u32)M27;
// ARM m155 CROSSBLK: the BW12 loop carried `a` through load->cmpgt->movemask->popcount
// EVERY element (~13 cyc of serial dependency per high element). Y1 is sorted, so a
// whole 8-low block is below xb iff its LAST element is; advance whole BLOCKS against
// that single scalar, then get the within-block count with one off-chain SIMD compare.
// The chain now steps once per 8 lows consumed, i.e. ~1/8 per high element.
if (jb < nblk) {
while (jb < nblk && Y1[(jb << 3) + 7] < xb) jb++;
if (jb < nblk) {
const __m256i xv = _mm256_set1_epi32((int)xb);
__m256i yv = _mm256_loadu_si256((const __m256i *)(Y1 + (jb << 3)));
unsigned c = (unsigned)__builtin_popcount(
(unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(xv, yv))));
a = (jb << 3) + c; // block's max is >= xb, so c <= 7
} else a = (nblk << 3);
} else a = (nblk << 3);
while (a < lo && Y1[a] < xb) a++; // at most the 7-element tail remains
run = (u32)a; // run == a at every step, by construction
((u32 *)Y2)[b] = run; // ARM m155 CPSEED: the whole 27-bit preseed in one u32 in
// the dead Y2 buffer -- the old form re-wrote all of RC
// (a second pass over an 8 B/el array) plus a u16 side array.
}
g_ph[7]+=phnow()-_tc; }
memcpy(gCnt, gH12 + 512, 512 * sizeof(u32));
{ double _t=phnow();
attach_l1(RC, (u32 *)RA, (u32 *)0, RB, (unsigned char *)Y1, (const u32 *)Y2, hi, 1);
g_ph[8]+=phnow()-_t; }
{ double _t=phnow();
levels(RC, RB, U1, (unsigned char *)Y1, hi, out); // high half: buckets of (cnt,idx) in RB
g_ph[9]+=phnow()-_t; }
{ double _t=phnow();
emit_idx_buckets(RB, hi, out);
g_ph[10]+=phnow()-_t; } // monotone sweep -> out
g_ph[11]+=phnow()-_t0; phdump();
}