#pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")
#include <immintrin.h>
typedef unsigned long U;
#ifndef N
#define N 100000000U
#endif
#define BUCKETS 256U
#ifndef LOW0_BITS_LOCAL
#define LOW0_BITS_LOCAL 8U
#endif
#define LOW0_BUCKETS_LOCAL (1U << LOW0_BITS_LOCAL)
#define LOW1_BITS_LOCAL (16U - LOW0_BITS_LOCAL)
#define LOW1_BUCKETS_LOCAL (1U << LOW1_BITS_LOCAL)
#define LOW_BUCKETS_LOCAL (LOW0_BUCKETS_LOCAL > LOW1_BUCKETS_LOCAL ? \
LOW0_BUCKETS_LOCAL : LOW1_BUCKETS_LOCAL)
#ifndef U32_BUFFER_SIZE
#define U32_BUFFER_SIZE 64U
#endif
#ifndef PACKED_BUFFER_SIZE
#define PACKED_BUFFER_SIZE 64U
#endif
#define HIGH_BUFFER_SIZE 64U
#ifndef HIGH_SCATTER_MODE
#define HIGH_SCATTER_MODE 3
#endif
#ifndef HIGH_PREFETCH_OFFSET
#define HIGH_PREFETCH_OFFSET -1
#endif
#ifndef HIGH_STAGE_ONLY
#define HIGH_STAGE_ONLY 0
#endif
#ifndef SIMD_UNPACK
#define SIMD_UNPACK 1
#endif
#define RESERVED_CAPACITY (((N + BUCKETS - 1) / BUCKETS) + 8192U)
#define WORK_N (RESERVED_CAPACITY * BUCKETS)
static unsigned char work[3ULL * WORK_N] __attribute__((aligned(64)));
static unsigned position[BUCKETS], starts[BUCKETS + 1];
static unsigned count[3][BUCKETS];
static unsigned mid_start[BUCKETS + 1];
#ifndef LOW_COUNT_32
#define LOW_COUNT_32 0
#endif
#if LOW_COUNT_32
typedef unsigned LowCount;
#else
typedef unsigned short LowCount;
#endif
static LowCount low16_count[2][LOW_BUCKETS_LOCAL]
__attribute__((aligned(64)));
static unsigned short low16_work[8192] __attribute__((aligned(64)));
/* Inputs are distinct. A 64-Kibit set gives the sorted low half directly;
the 1-Kibit summary avoids scanning empty 64-value words. */
static unsigned long low16_bits[1024] __attribute__((aligned(64)));
static unsigned long low16_present[16] __attribute__((aligned(64)));
#ifndef LOW_FINAL_COMPACT
#define LOW_FINAL_COMPACT 2
#endif
#if LOW_FINAL_COMPACT == 2
static unsigned short low16_final[8192] __attribute__((aligned(64)));
#endif
#ifndef LOW_HIST_MODE
#define LOW_HIST_MODE 0
#endif
#ifndef LOW_SCATTER_UNROLL
#define LOW_SCATTER_UNROLL 1
#endif
#ifndef LOW_FINAL_UNROLL
#define LOW_FINAL_UNROLL 1
#endif
#ifndef LOW_PREFETCH_OFFSET
#define LOW_PREFETCH_OFFSET -1
#endif
#ifndef LOW_FINAL_PREFETCH_OFFSET
#define LOW_FINAL_PREFETCH_OFFSET -1
#endif
#ifndef LOW_PREFIX_SIMD
#define LOW_PREFIX_SIMD 0
#endif
#ifndef MID16_BUFFER_SIZE
#define MID16_BUFFER_SIZE 64U
#endif
#ifndef TINY_LOW_SORT
#define TINY_LOW_SORT 0
#endif
#ifndef MID_SCATTER_MODE
#define MID_SCATTER_MODE 2
#endif
#ifndef MID_EXPLICIT_UNROLL
#define MID_EXPLICIT_UNROLL 4
#endif
#ifndef MID_STAGE_ONLY
#define MID_STAGE_ONLY 0
#endif
#ifndef MID_LOAD32
#define MID_LOAD32 0
#endif
#ifndef MID_RESTRICT
#define MID_RESTRICT 1
#endif
#ifndef MID_CURSOR_ALIGN
#define MID_CURSOR_ALIGN 32
#endif
#ifndef MID_PREFETCH_OFFSET
#define MID_PREFETCH_OFFSET -1
#endif
#ifndef MID_PREFETCH_LOCALITY
#define MID_PREFETCH_LOCALITY 3
#endif
#if MID_RESTRICT
#define MID_R __restrict
#else
#define MID_R
#endif
#if MID_LOAD32
#define MID_VALUE(P) (((const PackedU32 *)(P))->value)
#define MID_DIGIT(P, V) (((V) >> 16) & 255U)
#else
#define MID_VALUE(P) (((const PackedU16 *)(P))->value)
#define MID_DIGIT(P, V) ((P)[2])
#endif
static unsigned short mid16_buffer[BUCKETS][MID16_BUFFER_SIZE]
__attribute__((aligned(64)));
static unsigned fill[BUCKETS], high_fill[BUCKETS];
static unsigned high_buffers[BUCKETS][HIGH_BUFFER_SIZE]
__attribute__((aligned(64)));
#define BUFFER_BYTES (U32_BUFFER_SIZE * 4U > 3U * PACKED_BUFFER_SIZE ? \
U32_BUFFER_SIZE * 4U : 3U * PACKED_BUFFER_SIZE)
static unsigned char buffers[BUCKETS][BUFFER_BYTES]
__attribute__((aligned(64)));
static U duck;
typedef struct __attribute__((packed, may_alias)) {
unsigned value;
} PackedU32;
typedef struct __attribute__((packed, may_alias)) {
unsigned short value;
} PackedU16;
U getauxval(U key) { return duck; }
static __attribute__((always_inline)) inline void prefix_low_counts(
LowCount *values) {
#if LOW_PREFIX_SIMD && LOW_COUNT_32
unsigned sum = 0;
for (unsigned digit = 0; digit < BUCKETS; digit += 8) {
__m256i original = _mm256_load_si256(
(const __m256i *)(values + digit));
__m256i inclusive = _mm256_add_epi32(
original, _mm256_slli_si256(original, 4));
inclusive = _mm256_add_epi32(
inclusive, _mm256_slli_si256(inclusive, 8));
__m128i low = _mm256_castsi256_si128(inclusive);
__m128i high = _mm256_extracti128_si256(inclusive, 1);
high = _mm_add_epi32(high,
_mm_set1_epi32(_mm_extract_epi32(low, 3)));
inclusive = _mm256_inserti128_si256(
_mm256_castsi128_si256(low), high, 1);
inclusive = _mm256_add_epi32(inclusive, _mm256_set1_epi32(sum));
_mm256_store_si256((__m256i *)(values + digit),
_mm256_sub_epi32(inclusive, original));
sum = (unsigned)_mm256_extract_epi32(inclusive, 7);
}
#else
unsigned sum = 0;
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
unsigned amount = values[digit];
values[digit] = (LowCount)sum;
sum += amount;
}
#endif
}
static __attribute__((always_inline)) inline unsigned load24(
const unsigned char *source) {
return ((const PackedU32 *)source)->value & 0x00ffffffU;
}
static __attribute__((always_inline)) inline void store24(
unsigned char *destination, unsigned value) {
destination[0] = (unsigned char)value;
destination[1] = (unsigned char)(value >> 8);
destination[2] = (unsigned char)(value >> 16);
}
static __attribute__((always_inline)) inline void store24_buffer(
unsigned char *destination, unsigned value) {
((PackedU32 *)destination)->value = value;
}
static __attribute__((always_inline)) inline void pack16(
__m256i first, __m256i second,
__m128i *out0, __m128i *out1, __m128i *out2) {
const __m128i compact = _mm_setr_epi8(
0, 1, 2, 4, 5, 6, 8, 9, 10, 12, 13, 14, -1, -1, -1, -1);
__m128i p0 = _mm_shuffle_epi8(_mm256_castsi256_si128(first), compact);
__m128i p1 = _mm_shuffle_epi8(_mm256_extracti128_si256(first, 1), compact);
__m128i p2 = _mm_shuffle_epi8(_mm256_castsi256_si128(second), compact);
__m128i p3 = _mm_shuffle_epi8(_mm256_extracti128_si256(second, 1), compact);
*out0 = _mm_or_si128(p0, _mm_slli_si128(p1, 12));
*out1 = _mm_or_si128(_mm_srli_si128(p1, 4), _mm_slli_si128(p2, 8));
*out2 = _mm_or_si128(_mm_srli_si128(p2, 8), _mm_slli_si128(p3, 4));
}
static __attribute__((always_inline)) inline void flush_packed64(
unsigned char *destination, const unsigned *source,
unsigned non_temporal) {
__m128i x0, x1, x2, x3, x4, x5;
pack16(_mm256_load_si256((const __m256i *)(source + 0)),
_mm256_load_si256((const __m256i *)(source + 8)),
&x0, &x1, &x2);
pack16(_mm256_load_si256((const __m256i *)(source + 16)),
_mm256_load_si256((const __m256i *)(source + 24)),
&x3, &x4, &x5);
__m256i y0 = _mm256_inserti128_si256(_mm256_castsi128_si256(x0), x1, 1);
__m256i y1 = _mm256_inserti128_si256(_mm256_castsi128_si256(x2), x3, 1);
__m256i y2 = _mm256_inserti128_si256(_mm256_castsi128_si256(x4), x5, 1);
if (non_temporal) {
_mm256_stream_si256((__m256i *)(destination + 0), y0);
_mm256_stream_si256((__m256i *)(destination + 32), y1);
_mm256_stream_si256((__m256i *)(destination + 64), y2);
} else {
_mm256_storeu_si256((__m256i *)(destination + 0), y0);
_mm256_storeu_si256((__m256i *)(destination + 32), y1);
_mm256_storeu_si256((__m256i *)(destination + 64), y2);
}
pack16(_mm256_load_si256((const __m256i *)(source + 32)),
_mm256_load_si256((const __m256i *)(source + 40)),
&x0, &x1, &x2);
pack16(_mm256_load_si256((const __m256i *)(source + 48)),
_mm256_load_si256((const __m256i *)(source + 56)),
&x3, &x4, &x5);
y0 = _mm256_inserti128_si256(_mm256_castsi128_si256(x0), x1, 1);
y1 = _mm256_inserti128_si256(_mm256_castsi128_si256(x2), x3, 1);
y2 = _mm256_inserti128_si256(_mm256_castsi128_si256(x4), x5, 1);
if (non_temporal) {
_mm256_stream_si256((__m256i *)(destination + 96), y0);
_mm256_stream_si256((__m256i *)(destination + 128), y1);
_mm256_stream_si256((__m256i *)(destination + 160), y2);
} else {
_mm256_storeu_si256((__m256i *)(destination + 96), y0);
_mm256_storeu_si256((__m256i *)(destination + 128), y1);
_mm256_storeu_si256((__m256i *)(destination + 160), y2);
}
}
static __attribute__((always_inline)) inline void flush_u32_regular(
unsigned *destination, const unsigned *source) {
for (unsigned offset = 0; offset < U32_BUFFER_SIZE; offset += 8)
_mm256_storeu_si256((__m256i *)(destination + offset),
_mm256_load_si256(
(const __m256i *)(source + offset)));
}
static void scatter_high_packed(const unsigned *source) {
#if HIGH_SCATTER_MODE == 3
for (unsigned digit = 0; digit < BUCKETS; ++digit)
position[digit] = digit * RESERVED_CAPACITY;
for (unsigned i = 0; i < N; ++i) {
unsigned value = source[i], digit = value >> 24;
unsigned output = position[digit]++;
((PackedU32 *)(work + 3ULL * output))->value = value;
}
#elif HIGH_SCATTER_MODE == 1 || HIGH_SCATTER_MODE == 2
unsigned char *cursor[BUCKETS] __attribute__((aligned(64)));
for (unsigned digit = 0; digit < BUCKETS; ++digit)
cursor[digit] = work + 3ULL * digit * RESERVED_CAPACITY;
for (unsigned i = 0; i < N; ++i) {
unsigned value = source[i], digit = value >> 24;
unsigned char *destination = cursor[digit];
#if HIGH_SCATTER_MODE == 2
((PackedU32 *)destination)->value = value;
#else
((PackedU16 *)destination)->value = (unsigned short)value;
destination[2] = (unsigned char)(value >> 16);
#endif
if (HIGH_PREFETCH_OFFSET >= 0 &&
(((U)destination & 63U) == (unsigned)HIGH_PREFETCH_OFFSET))
__builtin_prefetch(destination + 64, 1, 3);
cursor[digit] = destination + 3;
}
for (unsigned digit = 0; digit < BUCKETS; ++digit)
position[digit] = digit * RESERVED_CAPACITY +
(unsigned)((cursor[digit] -
(work + 3ULL * digit * RESERVED_CAPACITY)) / 3);
#else
for (unsigned digit = 0; digit < BUCKETS; ++digit)
position[digit] = digit * RESERVED_CAPACITY;
for (unsigned i = 0; i < N; ++i) {
unsigned value = source[i];
unsigned digit = value >> 24;
unsigned output = position[digit];
unsigned char *destination = work + 3ULL * output;
if ((U)destination & 31U) {
store24(destination, value);
position[digit] = output + 1;
} else {
unsigned slot = high_fill[digit];
high_buffers[digit][slot] = value;
if (slot == HIGH_BUFFER_SIZE - 1) {
flush_packed64(destination,
high_buffers[digit], 1);
position[digit] = output + HIGH_BUFFER_SIZE;
high_fill[digit] = 0;
} else high_fill[digit] = slot + 1;
}
}
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
unsigned output = position[digit];
unsigned amount = high_fill[digit];
const unsigned *source_buffer = high_buffers[digit];
for (unsigned j = 0; j < amount; ++j)
store24(work + 3ULL * (output + j), source_buffer[j]);
position[digit] = output + amount;
high_fill[digit] = 0;
}
_mm_sfence();
#endif
}
static inline void prefix(unsigned *values, unsigned base) {
unsigned sum = base;
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
unsigned amount = values[digit];
values[digit] = sum;
sum += amount;
}
}
static __attribute__((always_inline)) inline void packed_to_u32(
const unsigned char *source, unsigned source_begin,
unsigned source_end, unsigned *destination, const unsigned *start,
unsigned shift, unsigned high) {
const __m128i expand = _mm_setr_epi8(
0, 1, 2, -1, 3, 4, 5, -1, 6, 7, 8, -1, 9, 10, 11, -1);
#define EMIT_U32(VALUE) do { \
unsigned value = (VALUE) | high; \
unsigned digit = (value >> shift) & 255U; \
unsigned sequence = fill[digit]++; \
unsigned slot = sequence & (U32_BUFFER_SIZE - 1); \
((unsigned *)buffers[digit])[slot] = value; \
if (slot == U32_BUFFER_SIZE - 1) \
flush_u32_regular(destination + start[digit] + sequence + 1 - \
U32_BUFFER_SIZE, \
(const unsigned *)buffers[digit]); \
} while (0)
unsigned i = source_begin;
const unsigned char *packed = source + 3ULL * source_begin;
#if SIMD_UNPACK
for (; i + 16 <= source_end; i += 16, packed += 48) {
__m128i in0 = _mm_loadu_si128((const __m128i *)(packed + 0));
__m128i in1 = _mm_loadu_si128((const __m128i *)(packed + 16));
__m128i in2 = _mm_loadu_si128((const __m128i *)(packed + 32));
__m128i v0 = _mm_shuffle_epi8(in0, expand);
__m128i v1 = _mm_shuffle_epi8(_mm_alignr_epi8(in1, in0, 12), expand);
__m128i v2 = _mm_shuffle_epi8(_mm_alignr_epi8(in2, in1, 8), expand);
__m128i v3 = _mm_shuffle_epi8(_mm_srli_si128(in2, 4), expand);
EMIT_U32((unsigned)_mm_cvtsi128_si32(v0));
EMIT_U32((unsigned)_mm_extract_epi32(v0, 1));
EMIT_U32((unsigned)_mm_extract_epi32(v0, 2));
EMIT_U32((unsigned)_mm_extract_epi32(v0, 3));
EMIT_U32((unsigned)_mm_cvtsi128_si32(v1));
EMIT_U32((unsigned)_mm_extract_epi32(v1, 1));
EMIT_U32((unsigned)_mm_extract_epi32(v1, 2));
EMIT_U32((unsigned)_mm_extract_epi32(v1, 3));
EMIT_U32((unsigned)_mm_cvtsi128_si32(v2));
EMIT_U32((unsigned)_mm_extract_epi32(v2, 1));
EMIT_U32((unsigned)_mm_extract_epi32(v2, 2));
EMIT_U32((unsigned)_mm_extract_epi32(v2, 3));
EMIT_U32((unsigned)_mm_cvtsi128_si32(v3));
EMIT_U32((unsigned)_mm_extract_epi32(v3, 1));
EMIT_U32((unsigned)_mm_extract_epi32(v3, 2));
EMIT_U32((unsigned)_mm_extract_epi32(v3, 3));
}
#endif
for (; i < source_end; ++i, packed += 3)
EMIT_U32(load24(packed));
#undef EMIT_U32
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
unsigned amount = fill[digit] & (U32_BUFFER_SIZE - 1);
unsigned output = start[digit] +
(fill[digit] & ~(U32_BUFFER_SIZE - 1));
const unsigned *source_buffer = (const unsigned *)buffers[digit];
for (unsigned j = 0; j < amount; ++j)
destination[output + j] = source_buffer[j];
fill[digit] = 0;
}
}
static __attribute__((always_inline)) inline void u32_to_packed(
const unsigned *source, unsigned begin, unsigned end,
unsigned char *destination, const unsigned *start, unsigned shift) {
for (unsigned i = begin; i < end; ++i) {
unsigned value = source[i];
unsigned digit = (value >> shift) & 255U;
unsigned sequence = fill[digit]++;
unsigned slot = sequence & (PACKED_BUFFER_SIZE - 1);
((unsigned *)buffers[digit])[slot] = value;
if (slot == PACKED_BUFFER_SIZE - 1)
flush_packed64(destination +
3ULL * (start[digit] + sequence + 1 -
PACKED_BUFFER_SIZE),
(const unsigned *)buffers[digit], 0);
}
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
unsigned amount = fill[digit] & (PACKED_BUFFER_SIZE - 1);
unsigned output = start[digit] +
(fill[digit] & ~(PACKED_BUFFER_SIZE - 1));
const unsigned *source_buffer = (const unsigned *)buffers[digit];
for (unsigned j = 0; j < amount; ++j)
store24(destination + 3ULL * (output + j), source_buffer[j]);
fill[digit] = 0;
}
}
static __attribute__((always_inline)) inline void packed_to_u16(
const unsigned char * MID_R source, unsigned source_begin,
unsigned source_end, unsigned short * MID_R destination,
unsigned * MID_R start) {
#if MID_SCATTER_MODE == 0
unsigned output_position[BUCKETS], pass_fill[BUCKETS] = {0};
for (unsigned digit = 0; digit < BUCKETS; ++digit)
output_position[digit] = start[digit];
const unsigned char *input = source + 3ULL * source_begin;
for (unsigned i = source_begin; i < source_end; ++i, input += 3) {
unsigned value = ((const PackedU16 *)input)->value;
unsigned digit = input[2];
unsigned output = output_position[digit];
unsigned slot = pass_fill[digit];
mid16_buffer[digit][slot] = (unsigned short)value;
if (slot == MID16_BUFFER_SIZE - 1U) {
for (unsigned j = 0; j < MID16_BUFFER_SIZE; j += 16)
_mm256_storeu_si256((__m256i *)(destination + output + j),
_mm256_load_si256(
(const __m256i *)(mid16_buffer[digit] + j)));
output_position[digit] = output + MID16_BUFFER_SIZE;
pass_fill[digit] = 0;
} else pass_fill[digit] = slot + 1;
}
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
unsigned output = output_position[digit], amount = pass_fill[digit];
for (unsigned i = 0; i < amount; ++i)
destination[output + i] = mid16_buffer[digit][i];
}
#elif MID_SCATTER_MODE == 1
/* The active destination line for each of the 256 streams occupies only
16 KiB in total, so test whether the L1 can act as the scatter buffer. */
unsigned output_position[BUCKETS];
for (unsigned digit = 0; digit < BUCKETS; ++digit)
output_position[digit] = start[digit];
const unsigned char *input = source + 3ULL * source_begin;
const unsigned char *input_end = source + 3ULL * source_end;
#define EMIT_DIRECT(P) do { \
const unsigned char *record = (P); \
unsigned value = MID_VALUE(record); \
unsigned digit = MID_DIGIT(record, value); \
destination[output_position[digit]++] = (unsigned short)value; \
} while (0)
#if MID_EXPLICIT_UNROLL >= 8
for (; input + 24 <= input_end; input += 24) {
EMIT_DIRECT(input + 0); EMIT_DIRECT(input + 3);
EMIT_DIRECT(input + 6); EMIT_DIRECT(input + 9);
EMIT_DIRECT(input + 12); EMIT_DIRECT(input + 15);
EMIT_DIRECT(input + 18); EMIT_DIRECT(input + 21);
}
#elif MID_EXPLICIT_UNROLL >= 4
for (; input + 12 <= input_end; input += 12) {
EMIT_DIRECT(input + 0); EMIT_DIRECT(input + 3);
EMIT_DIRECT(input + 6); EMIT_DIRECT(input + 9);
}
#elif MID_EXPLICIT_UNROLL >= 2
for (; input + 6 <= input_end; input += 6) {
EMIT_DIRECT(input + 0); EMIT_DIRECT(input + 3);
}
#endif
for (; input < input_end; input += 3) EMIT_DIRECT(input);
#undef EMIT_DIRECT
#elif MID_SCATTER_MODE == 2
unsigned short *output_cursor[BUCKETS]
__attribute__((aligned(MID_CURSOR_ALIGN)));
for (unsigned digit = 0; digit < BUCKETS; ++digit)
output_cursor[digit] = destination + start[digit];
const unsigned char *input = source + 3ULL * source_begin;
const unsigned char *input_end = source + 3ULL * source_end;
#define EMIT_DIRECT(P) do { \
const unsigned char *record = (P); \
unsigned value = MID_VALUE(record); \
unsigned digit = MID_DIGIT(record, value); \
unsigned short *output = output_cursor[digit]; \
*output = (unsigned short)value; \
if (MID_PREFETCH_OFFSET >= 0 && \
(((U)output & 63U) == (unsigned)MID_PREFETCH_OFFSET)) \
__builtin_prefetch(output + 32, 1, MID_PREFETCH_LOCALITY); \
output_cursor[digit] = output + 1; \
} while (0)
#if MID_EXPLICIT_UNROLL >= 8
for (; input + 24 <= input_end; input += 24) {
EMIT_DIRECT(input + 0); EMIT_DIRECT(input + 3);
EMIT_DIRECT(input + 6); EMIT_DIRECT(input + 9);
EMIT_DIRECT(input + 12); EMIT_DIRECT(input + 15);
EMIT_DIRECT(input + 18); EMIT_DIRECT(input + 21);
}
#elif MID_EXPLICIT_UNROLL >= 4
for (; input + 12 <= input_end; input += 12) {
EMIT_DIRECT(input + 0); EMIT_DIRECT(input + 3);
EMIT_DIRECT(input + 6); EMIT_DIRECT(input + 9);
}
#elif MID_EXPLICIT_UNROLL >= 2
for (; input + 6 <= input_end; input += 6) {
EMIT_DIRECT(input + 0); EMIT_DIRECT(input + 3);
}
#endif
for (; input < input_end; input += 3) EMIT_DIRECT(input);
#undef EMIT_DIRECT
#elif MID_SCATTER_MODE == 3
/* One monotonically increasing sequence number replaces the separate
output-position and partial-fill state of the baseline. */
unsigned sequence[BUCKETS] = {0};
const unsigned char *input = source + 3ULL * source_begin;
const unsigned char *input_end = source + 3ULL * source_end;
#define EMIT_BUFFERED(P) do { \
const unsigned char *record = (P); \
unsigned value = ((const PackedU16 *)record)->value; \
unsigned digit = record[2]; \
unsigned number = sequence[digit]++; \
unsigned slot = number & (MID16_BUFFER_SIZE - 1U); \
mid16_buffer[digit][slot] = (unsigned short)value; \
if (slot == MID16_BUFFER_SIZE - 1U) { \
unsigned short *output = destination + start[digit] + number + \
1U - MID16_BUFFER_SIZE; \
for (unsigned j = 0; j < MID16_BUFFER_SIZE; j += 16) \
_mm256_storeu_si256((__m256i *)(output + j), \
_mm256_load_si256( \
(const __m256i *)(mid16_buffer[digit] + j))); \
} \
} while (0)
#if MID_EXPLICIT_UNROLL >= 8
for (; input + 24 <= input_end; input += 24) {
EMIT_BUFFERED(input + 0); EMIT_BUFFERED(input + 3);
EMIT_BUFFERED(input + 6); EMIT_BUFFERED(input + 9);
EMIT_BUFFERED(input + 12); EMIT_BUFFERED(input + 15);
EMIT_BUFFERED(input + 18); EMIT_BUFFERED(input + 21);
}
#elif MID_EXPLICIT_UNROLL >= 4
for (; input + 12 <= input_end; input += 12) {
EMIT_BUFFERED(input + 0); EMIT_BUFFERED(input + 3);
EMIT_BUFFERED(input + 6); EMIT_BUFFERED(input + 9);
}
#elif MID_EXPLICIT_UNROLL >= 2
for (; input + 6 <= input_end; input += 6) {
EMIT_BUFFERED(input + 0); EMIT_BUFFERED(input + 3);
}
#endif
for (; input < input_end; input += 3) EMIT_BUFFERED(input);
#undef EMIT_BUFFERED
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
unsigned amount = sequence[digit] & (MID16_BUFFER_SIZE - 1U);
unsigned output = start[digit] +
(sequence[digit] & ~(MID16_BUFFER_SIZE - 1U));
for (unsigned i = 0; i < amount; ++i)
destination[output + i] = mid16_buffer[digit][i];
}
#elif MID_SCATTER_MODE == 4
/* count[2] is dead after this pass, so use it as the output cursor and
avoid copying a second 1 KiB position array for every high bucket. */
unsigned pass_fill[BUCKETS] = {0};
const unsigned char *input = source + 3ULL * source_begin;
const unsigned char *input_end = source + 3ULL * source_end;
#define EMIT_BUFFERED(P) do { \
const unsigned char *record = (P); \
unsigned value = ((const PackedU16 *)record)->value; \
unsigned digit = record[2]; \
unsigned slot = pass_fill[digit]; \
mid16_buffer[digit][slot] = (unsigned short)value; \
if (slot == MID16_BUFFER_SIZE - 1U) { \
unsigned output = start[digit]; \
for (unsigned j = 0; j < MID16_BUFFER_SIZE; j += 16) \
_mm256_storeu_si256((__m256i *)(destination + output + j), \
_mm256_load_si256( \
(const __m256i *)(mid16_buffer[digit] + j))); \
start[digit] = output + MID16_BUFFER_SIZE; \
pass_fill[digit] = 0; \
} else pass_fill[digit] = slot + 1; \
} while (0)
#if MID_EXPLICIT_UNROLL >= 8
for (; input + 24 <= input_end; input += 24) {
EMIT_BUFFERED(input + 0); EMIT_BUFFERED(input + 3);
EMIT_BUFFERED(input + 6); EMIT_BUFFERED(input + 9);
EMIT_BUFFERED(input + 12); EMIT_BUFFERED(input + 15);
EMIT_BUFFERED(input + 18); EMIT_BUFFERED(input + 21);
}
#elif MID_EXPLICIT_UNROLL >= 4
for (; input + 12 <= input_end; input += 12) {
EMIT_BUFFERED(input + 0); EMIT_BUFFERED(input + 3);
EMIT_BUFFERED(input + 6); EMIT_BUFFERED(input + 9);
}
#elif MID_EXPLICIT_UNROLL >= 2
for (; input + 6 <= input_end; input += 6) {
EMIT_BUFFERED(input + 0); EMIT_BUFFERED(input + 3);
}
#endif
for (; input < input_end; input += 3) EMIT_BUFFERED(input);
#undef EMIT_BUFFERED
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
unsigned output = start[digit], amount = pass_fill[digit];
for (unsigned i = 0; i < amount; ++i)
destination[output + i] = mid16_buffer[digit][i];
}
#elif MID_SCATTER_MODE == 5
/* As with mode 4, start is dead after this pass; for direct stores it can
itself be the complete cursor table. */
const unsigned char *input = source + 3ULL * source_begin;
const unsigned char *input_end = source + 3ULL * source_end;
#define EMIT_DIRECT(P) do { \
const unsigned char *record = (P); \
unsigned value = MID_VALUE(record); \
unsigned digit = MID_DIGIT(record, value); \
destination[start[digit]++] = (unsigned short)value; \
} while (0)
#if MID_EXPLICIT_UNROLL >= 8
for (; input + 24 <= input_end; input += 24) {
EMIT_DIRECT(input + 0); EMIT_DIRECT(input + 3);
EMIT_DIRECT(input + 6); EMIT_DIRECT(input + 9);
EMIT_DIRECT(input + 12); EMIT_DIRECT(input + 15);
EMIT_DIRECT(input + 18); EMIT_DIRECT(input + 21);
}
#elif MID_EXPLICIT_UNROLL >= 4
for (; input + 12 <= input_end; input += 12) {
EMIT_DIRECT(input + 0); EMIT_DIRECT(input + 3);
EMIT_DIRECT(input + 6); EMIT_DIRECT(input + 9);
}
#elif MID_EXPLICIT_UNROLL >= 2
for (; input + 6 <= input_end; input += 6) {
EMIT_DIRECT(input + 0); EMIT_DIRECT(input + 3);
}
#endif
for (; input < input_end; input += 3) EMIT_DIRECT(input);
#undef EMIT_DIRECT
#else
#error unsupported MID_SCATTER_MODE
#endif
}
#undef MID_R
#undef MID_VALUE
#undef MID_DIGIT
void sort(unsigned *a, int n) {
(void)n;
scatter_high_packed(a);
#if HIGH_STAGE_ONLY
_mm256_zeroupper();
return;
#endif
unsigned sum = 0;
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
starts[digit] = sum;
sum += position[digit] - digit * RESERVED_CAPACITY;
}
starts[BUCKETS] = N;
unsigned short *compressed = (unsigned short *)a;
for (unsigned bucket = BUCKETS; bucket-- != 0;) {
unsigned begin = starts[bucket], end = starts[bucket + 1];
unsigned source_begin = bucket * RESERVED_CAPACITY;
unsigned source_end = source_begin + end - begin;
__builtin_memset(count[2], 0, sizeof(count[2]));
const unsigned char *packed_source = work + 3ULL * source_begin;
for (unsigned i = source_begin; i < source_end;
++i, packed_source += 3)
++count[2][packed_source[2]];
unsigned middle_sum = begin;
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
mid_start[digit] = middle_sum;
middle_sum += count[2][digit];
count[2][digit] = mid_start[digit];
}
mid_start[BUCKETS] = end;
unsigned high = bucket << 24;
packed_to_u16(work, source_begin, source_end, compressed, count[2]);
#if !MID_STAGE_ONLY
for (unsigned mid = BUCKETS; mid-- != 0;) {
unsigned low_begin = mid_start[mid], low_end = mid_start[mid + 1];
#if 1
for (unsigned i = low_begin; i < low_end; ++i) {
unsigned value = compressed[i];
unsigned word = value >> 6;
low16_bits[word] |= 1UL << (value & 63U);
low16_present[word >> 6] |= 1UL << (word & 63U);
}
unsigned output = low_begin;
unsigned fixed = high | (mid << 16);
for (unsigned group = 0; group < 16; ++group) {
unsigned long words = low16_present[group];
low16_present[group] = 0;
while (words) {
unsigned within = (unsigned)__builtin_ctzl(words);
unsigned word = (group << 6) | within;
unsigned long values = low16_bits[word];
low16_bits[word] = 0;
while (values) {
unsigned bit = (unsigned)__builtin_ctzl(values);
a[output++] = fixed | (word << 6) | bit;
values &= values - 1;
}
words &= words - 1;
}
}
#elif TINY_LOW_SORT
__builtin_memset(low16_count[1], 0, sizeof(low16_count[1]));
for (unsigned i = low_begin; i < low_end; ++i)
++low16_count[1][compressed[i] >> 8];
unsigned high_sum = 0;
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
unsigned amount = low16_count[1][digit];
low16_count[0][digit] = (unsigned short)high_sum;
high_sum += amount;
low16_count[1][digit] = (unsigned short)high_sum;
}
for (unsigned i = low_begin; i < low_end; ++i) {
unsigned value = compressed[i], digit = value >> 8;
low16_work[low16_count[0][digit]++] = (unsigned short)value;
}
unsigned tiny_begin = 0;
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
unsigned tiny_end = low16_count[1][digit];
for (unsigned i = tiny_begin + 1; i < tiny_end; ++i) {
unsigned short value = low16_work[i];
unsigned j = i;
while (j > tiny_begin && low16_work[j - 1] > value) {
low16_work[j] = low16_work[j - 1];
--j;
}
low16_work[j] = value;
}
tiny_begin = tiny_end;
}
unsigned fixed = high | (mid << 16), amount = low_end - low_begin;
for (unsigned i = 0; i < amount; ++i)
a[low_begin + i] = fixed | low16_work[i];
#else
__builtin_memset(low16_count, 0, sizeof(low16_count));
#if LOW_HIST_MODE == 1
unsigned i = low_begin;
LowCount count0a[BUCKETS] = {0}, count1a[BUCKETS] = {0};
for (; i + 2 <= low_end; i += 2) {
unsigned value0 = compressed[i + 0];
unsigned value1 = compressed[i + 1];
++low16_count[0][(unsigned char)value0];
++low16_count[1][(unsigned char)(value0 >> 8)];
++count0a[(unsigned char)value1];
++count1a[(unsigned char)(value1 >> 8)];
}
for (; i < low_end; ++i) {
unsigned value = compressed[i];
++low16_count[0][(unsigned char)value];
++low16_count[1][(unsigned char)(value >> 8)];
}
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
low16_count[0][digit] += count0a[digit];
low16_count[1][digit] += count1a[digit];
}
#elif LOW_HIST_MODE == 2
unsigned i = low_begin;
LowCount count0a[BUCKETS] = {0}, count1a[BUCKETS] = {0};
LowCount count0b[BUCKETS] = {0}, count1b[BUCKETS] = {0};
LowCount count0c[BUCKETS] = {0}, count1c[BUCKETS] = {0};
for (; i + 4 <= low_end; i += 4) {
unsigned value0 = compressed[i + 0];
unsigned value1 = compressed[i + 1];
unsigned value2 = compressed[i + 2];
unsigned value3 = compressed[i + 3];
++low16_count[0][(unsigned char)value0];
++low16_count[1][(unsigned char)(value0 >> 8)];
++count0a[(unsigned char)value1];
++count1a[(unsigned char)(value1 >> 8)];
++count0b[(unsigned char)value2];
++count1b[(unsigned char)(value2 >> 8)];
++count0c[(unsigned char)value3];
++count1c[(unsigned char)(value3 >> 8)];
}
for (; i < low_end; ++i) {
unsigned value = compressed[i];
++low16_count[0][(unsigned char)value];
++low16_count[1][(unsigned char)(value >> 8)];
}
for (unsigned digit = 0; digit < BUCKETS; ++digit) {
low16_count[0][digit] += count0a[digit] + count0b[digit] +
count0c[digit];
low16_count[1][digit] += count1a[digit] + count1b[digit] +
count1c[digit];
}
#elif LOW_HIST_MODE == 3
for (unsigned i = low_begin; i < low_end; ++i) {
unsigned value = compressed[i];
++low16_count[0][(unsigned char)value];
}
#elif LOW_HIST_MODE == 4
for (unsigned i = low_begin; i < low_end; ++i) {
unsigned value = compressed[i];
++low16_count[0][value & (LOW0_BUCKETS_LOCAL - 1U)];
}
for (unsigned i = low_begin; i < low_end; ++i) {
unsigned value = compressed[i];
++low16_count[1][value >> LOW0_BITS_LOCAL];
}
#else
for (unsigned i = low_begin; i < low_end; ++i) {
unsigned value = compressed[i];
++low16_count[0][value & (LOW0_BUCKETS_LOCAL - 1U)];
++low16_count[1][value >> LOW0_BITS_LOCAL];
}
#endif
#if LOW_HIST_MODE == 3
prefix_low_counts(low16_count[0]);
#else
#if LOW_PREFIX_SIMD
prefix_low_counts(low16_count[0]);
prefix_low_counts(low16_count[1]);
#else
unsigned sum0 = 0, sum1 = 0;
unsigned prefix_buckets = LOW_BUCKETS_LOCAL;
for (unsigned digit = 0; digit < prefix_buckets; ++digit) {
unsigned amount0 = low16_count[0][digit];
unsigned amount1 = low16_count[1][digit];
low16_count[0][digit] = (LowCount)sum0;
low16_count[1][digit] = (LowCount)sum1;
sum0 += amount0;
sum1 += amount1;
}
#endif
#endif
#if LOW_SCATTER_UNROLL == 4
unsigned scatter_i = low_begin;
#define EMIT_LOW_SCATTER(INDEX) do { \
unsigned value = compressed[(INDEX)]; \
low16_work[low16_count[0][(unsigned char)value]++] = \
(unsigned short)value; \
if (LOW_HIST_MODE == 3) \
++low16_count[1][value >> 8]; \
} while (0)
for (; scatter_i + 4 <= low_end; scatter_i += 4) {
EMIT_LOW_SCATTER(scatter_i + 0);
EMIT_LOW_SCATTER(scatter_i + 1);
EMIT_LOW_SCATTER(scatter_i + 2);
EMIT_LOW_SCATTER(scatter_i + 3);
}
for (; scatter_i < low_end; ++scatter_i)
EMIT_LOW_SCATTER(scatter_i);
#undef EMIT_LOW_SCATTER
#else
for (unsigned i = low_begin; i < low_end; ++i) {
unsigned value = compressed[i];
unsigned digit = value & (LOW0_BUCKETS_LOCAL - 1U);
unsigned short *output =
low16_work + low16_count[0][digit]++;
*output = (unsigned short)value;
if (LOW_HIST_MODE == 3)
++low16_count[1][value >> 8];
if (LOW_PREFETCH_OFFSET >= 0 &&
(((U)output & 63U) == (unsigned)LOW_PREFETCH_OFFSET))
__builtin_prefetch(output + 32, 1, 3);
}
#endif
#if LOW_HIST_MODE == 3
prefix_low_counts(low16_count[1]);
#endif
unsigned fixed = high | (mid << 16), amount = low_end - low_begin;
#if LOW_FINAL_COMPACT == 2
#if LOW_FINAL_UNROLL == 4
unsigned final_scatter_i = 0;
#define EMIT_LOW_FINAL(INDEX) do { \
unsigned value = low16_work[(INDEX)]; \
low16_final[low16_count[1][value >> 8]++] = \
(unsigned short)value; \
} while (0)
for (; final_scatter_i + 4 <= amount; final_scatter_i += 4) {
EMIT_LOW_FINAL(final_scatter_i + 0);
EMIT_LOW_FINAL(final_scatter_i + 1);
EMIT_LOW_FINAL(final_scatter_i + 2);
EMIT_LOW_FINAL(final_scatter_i + 3);
}
for (; final_scatter_i < amount; ++final_scatter_i)
EMIT_LOW_FINAL(final_scatter_i);
#undef EMIT_LOW_FINAL
#else
for (unsigned i = 0; i < amount; ++i) {
unsigned value = low16_work[i];
unsigned digit = value >> LOW0_BITS_LOCAL;
unsigned short *output =
low16_final + low16_count[1][digit]++;
*output = (unsigned short)value;
if (LOW_FINAL_PREFETCH_OFFSET >= 0 &&
(((U)output & 63U) ==
(unsigned)LOW_FINAL_PREFETCH_OFFSET))
__builtin_prefetch(output + 32, 1, 3);
}
#endif
unsigned output_i = 0;
__m256i fixed8 = _mm256_set1_epi32((int)fixed);
for (; output_i + 8 <= amount; output_i += 8) {
__m128i words = _mm_load_si128(
(const __m128i *)(low16_final + output_i));
__m256i values = _mm256_cvtepu16_epi32(words);
_mm256_storeu_si256((__m256i *)(a + low_begin + output_i),
_mm256_or_si256(values, fixed8));
}
for (; output_i < amount; ++output_i)
a[low_begin + output_i] = fixed | low16_final[output_i];
#else
for (unsigned i = 0; i < amount; ++i) {
unsigned value = low16_work[i];
a[low_begin + low16_count[1][value >> LOW0_BITS_LOCAL]++] =
fixed | value;
}
#endif
#endif
}
#endif
}
_mm256_zeroupper();
}
__attribute__((noreturn))
void __libc_start_main(int (*entry)(int, char **, char **), int argc,
char **argv) {
U *aux = (U *)(argv + 2);
while (aux[0] != 0x6b637564UL) aux += 2;
duck = aux[1]; entry(argc, argv, (char **)0);
__asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall"
::: "rax", "rdi", "rcx", "r11", "memory");
__builtin_unreachable();
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 921.229 ms | 668 MB + 580 KB | Accepted | Score: 100 | 显示更多 |