#if (defined(__clang__) || defined(__GNUC__)) && !defined(_MSC_VER)
#define RESTRICT __restrict__
#else
#define RESTRICT __restrict
#endif

#define XSTRINGIFY(a) STRINGIFY(a)
#define STRINGIFY(a) #a

#define LOG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

#define ASSERT(cond, ...)                                               \
    do {                                                                \
        if (!(cond)) [[unlikely]] {                                     \
            LOG(__FILE__ ":%d: assertion failed: " #cond __VA_OPT__(" | %s"), __LINE__ __VA_OPT__(,) __VA_ARGS__); \
            abort();                                                    \
        }                                                               \
    } while (0)

#ifdef NDEBUG
#define DASSERT(cond, ...)       \
    do {                    \
        (void)sizeof(cond); \
    } while (0)
#else
#define DASSERT(cond, ...) ASSERT(cond __VA_OPT__(,) __VA_ARGS__)
#endif

#define COUNT(arr) (sizeof((arr)) / sizeof((arr)[0]))


static uint32_t
BitScanForward32(uint32_t n)
{
#if defined(__clang__) || defined(__GNUC__)
    return (uint32_t)__builtin_ctz(n);
#else
    unsigned long index;
    _BitScanForward(&index, (unsigned long)n);
    return (uint32_t)index;
#endif
}

static uint64_t
BitScanForward64(uint64_t n)
{
#if defined(__clang__) || defined(__GNUC__)
    return (uint32_t)__builtin_ctzll(n);
#else
    unsigned long index;
    ::_BitScanForward64(&index, n);
    return (uint32_t)index;
#endif
}

static uint16_t
ByteSwap16(uint16_t val)
{
#if defined(__clang__) || defined(__GNUC__)
    return __builtin_bswap16(val);
#else
    return _byteswap_ushort(val);
#endif
}

static uint32_t
ByteSwap32(uint32_t val)
{
#if defined(__clang__) || defined(__GNUC__)
    return __builtin_bswap32(val);
#else
    return _byteswap_ulong(val);
#endif
}

static uint64_t
ByteSwap64(uint64_t val)
{
#if defined(__clang__) || defined(__GNUC__)
    return __builtin_bswap64(val);
#else
    return _byteswap_uint64(val);
#endif
}

static int64_t
LRound(double x)
{
#if defined(__clang__) || defined(__GNUC__)
    return __builtin_lround(x);
#else
    double bias;
    if (x >= 0)
        bias = 0.5;
    else
        bias = -0.5;
    return _mm_cvtsd_si64(_mm_set_sd(x + bias));
#endif
}

static uint64_t
UMul128(uint64_t a, uint64_t b, uint64_t& hi)
{
#if defined(__clang__) || defined(__GNUC__)
    unsigned __int128 res = (unsigned __int128)a * b;
    hi = (uint64_t)(res >> 64);
    return (uint64_t)res;
#else
    return _umul128(a, b, &hi);
#endif
}

uint64_t
UDiv128(uint64_t hi, uint64_t lo, uint64_t divisor, uint64_t& reminder)
{
#if defined(__clang__) || defined(__GNUC__)
    unsigned __int128 dividend = ((unsigned __int128)hi << 64) | lo;
    reminder = (uint64_t)(dividend % divisor);
    return (uint64_t)(dividend / divisor);
#else
    return _udiv128(hi, lo, divisor, &reminder);
#endif
}

static uint32_t
AtomicLoad32(const uint32_t* p)
{
#if defined(__clang__) || defined(__GNUC__)
    return __atomic_load_n(p, __ATOMIC_ACQUIRE);
#else
    return (uint32_t)_InterlockedOr((volatile long*)p, 0);
#endif
}

static void
AtomicStore32(uint32_t* p, uint32_t v)
{
#if defined(__clang__) || defined(__GNUC__)
    __atomic_store_n(p, v, __ATOMIC_RELEASE);
#else
    _InterlockedExchange((volatile long*)p, (long)v);
#endif
}

static uint64_t
AtomicLoad64(const uint64_t* p)
{
#if defined(__clang__) || defined(__GNUC__)
    return __atomic_load_n(p, __ATOMIC_ACQUIRE);
#else
    return (uint64_t)_InterlockedOr64((volatile long long*)p, 0);
#endif
}

static void
AtomicStore64(uint64_t* p, uint64_t v)
{
#if defined(__clang__) || defined(__GNUC__)
    __atomic_store_n(p, v, __ATOMIC_RELEASE);
#else
    _InterlockedExchange64((volatile long long*)p, (long long)v);
#endif
}