// Copyright (c) 2022 Christopher Berner
//
// MIT License
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all
// copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
// SOFTWARE.

// Copied from xxh3 crate, commit hash e91f09d1e930e179c11d5cfda6d14284bfb006f8

use alloc::vec::Vec;
use core::mem::size_of;

const STRIPE_LENGTH: usize = 64;
const SECRET_CONSUME_RATE: usize = 8;

const MIN_SECRET_SIZE: usize = 136;
const DEFAULT_SECRET: [u8; 192] = [
    0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
    0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
    0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
    0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
    0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3,
    0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8,
    0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d,
    0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64,
    0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb,
    0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e,
    0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce,
    0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e,
];

const PRIME32: [u64; 3] = [0x9E3779B1, 0x85EBCA77, 0xC2B2AE3D];
const PRIME64: [u64; 5] = [
    0x9E3779B185EBCA87,
    0xC2B2AE3D27D4EB4F,
    0x165667B19E3779F9,
    0x85EBCA77C2B2AE63,
    0x27D4EB2F165667C5,
];

const INIT_ACCUMULATORS: [u64; 8] = [
    PRIME32[2], PRIME64[0], PRIME64[1], PRIME64[2], PRIME64[3], PRIME32[1], PRIME64[4], PRIME32[0],
];

pub fn hash64_with_seed(data: &[u8], seed: u64) -> u64 {
    if data.len() <= 240 {
        hash64_0to240(data, &DEFAULT_SECRET, seed)
    } else {
        #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
        {
            if is_x86_feature_detected!("avx2") {
                // SAFETY: AVX2 availability is verified by the runtime check above.
                // `hash64_large_avx2` is `#[target_feature(enable = "avx2")]` and
                // requires the caller to guarantee the feature is present.
                unsafe {
                    return hash64_large_avx2(data, seed);
                }
            }
        }
        #[cfg(target_arch = "aarch64")]
        {
            // SAFETY: This block is only compiled on aarch64 where NEON is
            // always available. `hash64_large_neon` uses NEON intrinsics that
            // are guaranteed present on all AArch64 targets.
            unsafe { hash64_large_neon(data, seed) }
        }
        #[cfg(not(target_arch = "aarch64"))]
        hash64_large_generic(
            data,
            seed,
            gen_secret_generic,
            scramble_accumulators_generic,
            accumulate_stripe_generic,
        )
    }
}

pub fn hash128_with_seed(data: &[u8], seed: u64) -> u128 {
    if data.len() <= 240 {
        hash128_0to240(data, &DEFAULT_SECRET, seed)
    } else {
        #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
        if is_x86_feature_detected!("avx2") {
            // SAFETY: AVX2 availability is verified by the runtime check above.
            // `hash128_large_avx2` is `#[target_feature(enable = "avx2")]` and
            // requires the caller to guarantee the feature is present.
            unsafe {
                return hash128_large_avx2(data, seed);
            }
        }
        #[cfg(target_arch = "aarch64")]
        // SAFETY: This block is only compiled on aarch64 where NEON is always
        // available. `hash128_large_neon` uses NEON intrinsics that are
        // guaranteed present on all AArch64 targets.
        unsafe {
            hash128_large_neon(data, seed)
        }
        #[cfg(not(target_arch = "aarch64"))]
        hash128_large_generic(
            data,
            seed,
            gen_secret_generic,
            scramble_accumulators_generic,
            accumulate_stripe_generic,
        )
    }
}

fn get_u32(data: &[u8], i: usize) -> u32 {
    u32::from_le_bytes(
        data[i * size_of::<u32>()..(i + 1) * size_of::<u32>()]
            .try_into()
            .unwrap(),
    )
}

fn get_u64(data: &[u8], i: usize) -> u64 {
    u64::from_le_bytes(
        data[i * size_of::<u64>()..(i + 1) * size_of::<u64>()]
            .try_into()
            .unwrap(),
    )
}

fn xxh64_avalanche(mut x: u64) -> u64 {
    x ^= x >> 33;
    x = x.wrapping_mul(PRIME64[1]);
    x ^= x >> 29;
    x = x.wrapping_mul(PRIME64[2]);
    x ^= x >> 32;
    x
}

fn xxh3_avalanche(mut x: u64) -> u64 {
    x = xorshift(x, 37);
    x = x.wrapping_mul(0x165667919E3779F9);
    x = xorshift(x, 32);
    x
}

#[inline(always)]
fn merge_accumulators(
    accumulators: [u64; INIT_ACCUMULATORS.len()],
    secret: &[u8],
    init: u64,
) -> u64 {
    let mut result = init;
    for i in 0..4 {
        let a1 = accumulators[2 * i];
        let a2 = accumulators[2 * i + 1];
        let s1 = get_u64(&secret[16 * i..], 0);
        let s2 = get_u64(&secret[16 * i..], 1);
        result = result.wrapping_add(mul128_and_xor(a1 ^ s1, a2 ^ s2));
    }
    xxh3_avalanche(result)
}

#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
#[target_feature(enable = "avx2")]
unsafe fn scramble_accumulators_avx2(
    accumulators: &mut [u64; INIT_ACCUMULATORS.len()],
    secret: &[u8],
) {
    // SAFETY: Caller guarantees AVX2 is available (via `#[target_feature]`).
    // `accumulators` is a `[u64; 8]` (64 bytes = STRIPE_LENGTH) and `secret`
    // is at least STRIPE_LENGTH bytes, satisfying alignment and size
    // requirements for 256-bit SIMD loads/stores.
    unsafe {
        #[cfg(target_arch = "x86")]
        use core::arch::x86::*;
        #[cfg(target_arch = "x86_64")]
        use core::arch::x86_64::*;

        #[allow(clippy::cast_possible_truncation)]
        let simd_prime = _mm256_set1_epi32(PRIME32[0] as i32);
        let secret_ptr = secret.as_ptr();
        let accumulators_ptr = accumulators.as_mut_ptr();

        for i in 0..(STRIPE_LENGTH / 32) {
            let a = _mm256_loadu_si256((accumulators_ptr as *const __m256i).add(i));
            let shifted = _mm256_srli_epi64::<47>(a);
            let b = _mm256_xor_si256(a, shifted);

            let s = _mm256_loadu_si256((secret_ptr as *const __m256i).add(i));
            let c = _mm256_xor_si256(b, s);
            let c_high = _mm256_shuffle_epi32::<49>(c);

            let low = _mm256_mul_epu32(c, simd_prime);
            let high = _mm256_mul_epu32(c_high, simd_prime);
            let high = _mm256_slli_epi64::<32>(high);
            let result = _mm256_add_epi64(low, high);
            _mm256_storeu_si256((accumulators_ptr as *mut __m256i).add(i), result);
        }
    }
}

#[cfg(target_arch = "aarch64")]
unsafe fn scramble_accumulators_neon(
    accumulators: &mut [u64; INIT_ACCUMULATORS.len()],
    secret: &[u8],
) {
    #[cfg(target_arch = "aarch64")]
    use core::arch::aarch64::*;
    #[cfg(target_arch = "arm")]
    use core::arch::arm::*;

    // SAFETY: Caller guarantees NEON is available (always true on aarch64).
    // `accumulators` is a `[u64; 8]` (64 bytes) and `secret` is asserted to
    // be at least STRIPE_LENGTH bytes, so all NEON loads/stores are in bounds.
    unsafe {
        let prime = vdup_n_u32(PRIME32[0].try_into().unwrap());

        let accum_ptr = accumulators.as_mut_ptr();
        let secret_ptr = secret.as_ptr();
        assert!(secret.len() >= STRIPE_LENGTH);
        for i in 0..(STRIPE_LENGTH / 16) {
            // xorshift
            let accum = vld1q_u64(accum_ptr.add(i * 2));
            let shifted = vshrq_n_u64(accum, 47);
            let accum = veorq_u64(accum, shifted);

            // xor with secret
            let s = vld1q_u8(secret_ptr.add(i * 16));
            let accum = veorq_u64(accum, vreinterpretq_u64_u8(s));

            // mul with prime. Sadly there's no vmulq_u64
            let accum_low = vmovn_u64(accum);
            let accum_high = vshrn_n_u64(accum, 32);
            let prod_high = vshlq_n_u64(vmull_u32(accum_high, prime), 32);
            let accum = vmlal_u32(prod_high, accum_low, prime);
            vst1q_u64(accum_ptr.add(i * 2), accum);
        }
    }
}

fn scramble_accumulators_generic(accumulators: &mut [u64; INIT_ACCUMULATORS.len()], secret: &[u8]) {
    for (i, x) in accumulators.iter_mut().enumerate() {
        let s = get_u64(secret, i);
        *x = xorshift(*x, 47);
        *x ^= s;
        *x = x.wrapping_mul(PRIME32[0]);
    }
}

fn xorshift(x: u64, shift: u64) -> u64 {
    x ^ (x >> shift)
}

fn rrmxmx(mut x: u64, y: u64) -> u64 {
    x ^= x.rotate_left(49) ^ x.rotate_left(24);
    x = x.wrapping_mul(0x9FB21C651E98DF25);
    x ^= (x >> 35).wrapping_add(y);
    x = x.wrapping_mul(0x9FB21C651E98DF25);
    xorshift(x, 28)
}

fn mul128_and_xor(x: u64, y: u64) -> u64 {
    let z = u128::from(x) * u128::from(y);
    #[allow(clippy::cast_possible_truncation)]
    (z as u64 ^ (z >> 64) as u64)
}

fn mix16(data: &[u8], secret: &[u8], seed: u64) -> u64 {
    let x1 = get_u64(data, 0);
    let x2 = get_u64(data, 1);
    let s1 = get_u64(secret, 0).wrapping_add(seed);
    let s2 = get_u64(secret, 1).wrapping_sub(seed);

    mul128_and_xor(x1 ^ s1, x2 ^ s2)
}

fn mix32(state: (u64, u64), data1: &[u8], data2: &[u8], secret: &[u8], seed: u64) -> (u64, u64) {
    let (mut r_low, mut r_high) = state;

    r_low = r_low.wrapping_add(mix16(data1, secret, seed));
    r_low ^= get_u64(data2, 0).wrapping_add(get_u64(data2, 1));
    r_high = r_high.wrapping_add(mix16(data2, &secret[16..], seed));
    r_high ^= get_u64(data1, 0).wrapping_add(get_u64(data1, 1));

    (r_low, r_high)
}

fn gen_secret_generic(seed: u64) -> [u8; DEFAULT_SECRET.len()] {
    let mut secret = [0u8; DEFAULT_SECRET.len()];
    let iterations = DEFAULT_SECRET.len() / 16;
    for i in 0..iterations {
        let x = get_u64(&DEFAULT_SECRET, 2 * i).wrapping_add(seed);
        secret[16 * i..16 * i + 8].copy_from_slice(&x.to_le_bytes());
        let x = get_u64(&DEFAULT_SECRET, 2 * i + 1).wrapping_sub(seed);
        secret[16 * i + 8..16 * (i + 1)].copy_from_slice(&x.to_le_bytes());
    }
    secret
}

#[allow(clippy::cast_possible_truncation)]
#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
#[target_feature(enable = "avx2")]
unsafe fn gen_secret_avx2(seed: u64) -> [u8; DEFAULT_SECRET.len()] {
    // SAFETY: Caller guarantees AVX2 is available (via `#[target_feature]`).
    // `DEFAULT_SECRET` is 192 bytes and `output` is the same size; the loop
    // performs 6 iterations of 32-byte AVX2 loads/stores (6*32 = 192), so all
    // accesses are in bounds.
    unsafe {
        #[cfg(target_arch = "x86")]
        use core::arch::x86::*;
        #[cfg(target_arch = "x86_64")]
        use core::arch::x86_64::*;

        #[allow(clippy::cast_possible_wrap)]
        let xxh_i64 = 0u64.wrapping_sub(seed) as i64;
        #[allow(clippy::cast_possible_wrap)]
        let seed = seed as i64;

        let simd_seed = _mm256_set_epi64x(xxh_i64, seed, xxh_i64, seed);

        let mut output = [0u8; DEFAULT_SECRET.len()];
        let output_ptr = output.as_mut_ptr();
        let secret_ptr = DEFAULT_SECRET.as_ptr();
        for i in 0..6 {
            let s = _mm256_loadu_si256((secret_ptr as *const __m256i).add(i));
            let x = _mm256_add_epi64(s, simd_seed);
            _mm256_storeu_si256((output_ptr as *mut __m256i).add(i), x);
        }

        output
    }
}

#[cfg(target_arch = "aarch64")]
unsafe fn accumulate_stripe_neon(accumulators: &mut [u64; 8], data: &[u8], secret: &[u8]) {
    #[cfg(target_arch = "aarch64")]
    use core::arch::aarch64::*;
    #[cfg(target_arch = "arm")]
    use core::arch::arm::*;

    // SAFETY: Caller guarantees NEON is available. Both `data` and `secret`
    // are asserted to be at least STRIPE_LENGTH (64) bytes, and `accumulators`
    // is `[u64; 8]` (64 bytes). All NEON loads/stores stay within these bounds.
    unsafe {
        let accum_ptr = accumulators.as_mut_ptr();
        let data_ptr = data.as_ptr();
        let secret_ptr = secret.as_ptr();
        assert!(data.len() >= STRIPE_LENGTH);
        assert!(secret.len() >= STRIPE_LENGTH);
        for i in 0..(STRIPE_LENGTH / 16) {
            let x = vld1q_u8(data_ptr.add(i * 16));
            let s = vld1q_u8(secret_ptr.add(i * 16));
            let x64 = vreinterpretq_u64_u8(x);
            let y = vextq_u64(x64, x64, 1);

            let result = vld1q_u64(accum_ptr.add(i * 2));
            let result = vaddq_u64(result, y);

            let z = vreinterpretq_u64_u8(veorq_u8(x, s));
            let z_low = vmovn_u64(z);
            let z_high = vshrn_n_u64(z, 32);

            let result = vmlal_u32(result, z_low, z_high);
            vst1q_u64(accum_ptr.add(i * 2), result);
        }
    }
}

#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
#[target_feature(enable = "avx2")]
unsafe fn accumulate_stripe_avx2(accumulators: &mut [u64; 8], data: &[u8], secret: &[u8]) {
    // SAFETY: Caller guarantees AVX2 is available (via `#[target_feature]`).
    // Both `data` and `secret` are asserted to be at least STRIPE_LENGTH (64)
    // bytes, and `accumulators` is `[u64; 8]` (64 bytes). The loop performs
    // 2 iterations of 32-byte AVX2 loads/stores, all within bounds.
    unsafe {
        #[cfg(target_arch = "x86")]
        use core::arch::x86::*;
        #[cfg(target_arch = "x86_64")]
        use core::arch::x86_64::*;

        let data_ptr = data.as_ptr();
        let secret_ptr = secret.as_ptr();
        let accumulator_ptr = accumulators.as_mut_ptr();

        assert!(data.len() >= STRIPE_LENGTH);
        assert!(secret.len() >= STRIPE_LENGTH);
        for i in 0..(STRIPE_LENGTH / 32) {
            let x = _mm256_loadu_si256((data_ptr as *const __m256i).add(i));
            let s = _mm256_loadu_si256((secret_ptr as *const __m256i).add(i));

            let z = _mm256_xor_si256(x, s);
            let z_low = _mm256_shuffle_epi32::<49>(z);

            let product = _mm256_mul_epu32(z, z_low);
            let shuffled = _mm256_shuffle_epi32::<78>(x);

            let result = _mm256_loadu_si256((accumulator_ptr as *const __m256i).add(i));
            let result = _mm256_add_epi64(result, shuffled);
            let result = _mm256_add_epi64(result, product);
            _mm256_storeu_si256((accumulator_ptr as *mut __m256i).add(i), result);
        }
    }
}

fn accumulate_stripe_generic(accumulators: &mut [u64; 8], data: &[u8], secret: &[u8]) {
    for i in 0..accumulators.len() {
        let x = get_u64(&data[i * 8..], 0);
        let y = x ^ get_u64(&secret[i * 8..], 0);
        accumulators[i ^ 1] = accumulators[i ^ 1].wrapping_add(x);
        let z = (y & 0xFFFF_FFFF) * (y >> 32);
        accumulators[i] = accumulators[i].wrapping_add(z)
    }
}

#[inline(always)]
fn accumulate_block(
    accumulators: &mut [u64; 8],
    data: &[u8],
    secret: &[u8],
    stripes: usize,
    accum_stripe: unsafe fn(&mut [u64; 8], &[u8], &[u8]),
) {
    for i in 0..stripes {
        // SAFETY: `accum_stripe` is a function pointer to either a SIMD or
        // generic implementation. The caller ensures the appropriate CPU
        // feature is available. `data` and `secret` slicing is bounded by
        // `stripes` which is derived from `(data.len() - 1) / STRIPE_LENGTH`.
        unsafe {
            accum_stripe(
                accumulators,
                &data[i * STRIPE_LENGTH..],
                &secret[i * SECRET_CONSUME_RATE..],
            );
        }
    }
}

#[inline(always)]
fn hash_large_helper(
    data: &[u8],
    secret: &[u8],
    scramble: unsafe fn(&mut [u64; 8], &[u8]),
    accum_stripe: unsafe fn(&mut [u64; 8], &[u8], &[u8]),
) -> [u64; INIT_ACCUMULATORS.len()] {
    let mut accumulators = INIT_ACCUMULATORS;

    let stripes_per_block = (secret.len() - STRIPE_LENGTH) / SECRET_CONSUME_RATE;
    let block_len = STRIPE_LENGTH * stripes_per_block;
    let blocks = (data.len() - 1) / block_len;

    // accumulate all the blocks
    for i in 0..blocks {
        accumulate_block(
            &mut accumulators,
            &data[i * block_len..],
            secret,
            stripes_per_block,
            accum_stripe,
        );
        // SAFETY: `scramble` is a function pointer to either a SIMD or generic
        // implementation. The caller ensures the appropriate CPU feature is
        // available. The secret slice starts at `secret.len() - STRIPE_LENGTH`,
        // providing exactly STRIPE_LENGTH bytes.
        unsafe { scramble(&mut accumulators, &secret[secret.len() - STRIPE_LENGTH..]) };
    }

    // trailing partial block
    let stripes = ((data.len() - 1) - block_len * blocks) / STRIPE_LENGTH;
    accumulate_block(
        &mut accumulators,
        &data[blocks * block_len..],
        secret,
        stripes,
        accum_stripe,
    );

    // trailing stripe
    // SAFETY: `accum_stripe` is a function pointer whose CPU feature
    // requirement is satisfied by the caller. `data.len() > 240 >=
    // STRIPE_LENGTH` (enforced by the call sites), so the trailing slice
    // has exactly STRIPE_LENGTH bytes. The secret slice is similarly valid
    // because `secret.len() >= MIN_SECRET_SIZE > STRIPE_LENGTH + 7`.
    unsafe {
        accum_stripe(
            &mut accumulators,
            &data[data.len() - STRIPE_LENGTH..],
            &secret[secret.len() - STRIPE_LENGTH - 7..],
        );
    }

    accumulators
}

fn hash64_0(secret: &[u8], seed: u64) -> u64 {
    let mut result = seed;
    result ^= get_u64(secret, 7);
    result ^= get_u64(secret, 8);
    xxh64_avalanche(result)
}

fn hash64_1to3(data: &[u8], secret: &[u8], seed: u64) -> u64 {
    let x1 = data[0] as u32;
    let x2 = data[data.len() >> 1] as u32;
    let x3 = (*data.last().unwrap()) as u32;
    #[allow(clippy::cast_possible_truncation)]
    let x4 = data.len() as u32;

    let combined = ((x1 << 16) | (x2 << 24) | x3 | (x4 << 8)) as u64;
    let mut result = (get_u32(secret, 0) ^ get_u32(secret, 1)) as u64;
    result = result.wrapping_add(seed);
    result ^= combined;
    xxh64_avalanche(result)
}

fn hash64_4to8(data: &[u8], secret: &[u8], mut seed: u64) -> u64 {
    #[allow(clippy::cast_possible_truncation)]
    let truncate_seed = seed as u32;
    seed ^= u64::from(truncate_seed.swap_bytes()) << 32;
    let x1 = get_u32(data, 0) as u64;
    let x2 = get_u32(&data[data.len() - 4..], 0) as u64;
    let x = x2 | (x1 << 32);
    let s = (get_u64(secret, 1) ^ get_u64(secret, 2)).wrapping_sub(seed);
    rrmxmx(x ^ s, data.len() as u64)
}

fn hash64_9to16(data: &[u8], secret: &[u8], seed: u64) -> u64 {
    let s1 = (get_u64(secret, 3) ^ get_u64(secret, 4)).wrapping_add(seed);
    let s2 = (get_u64(secret, 5) ^ get_u64(secret, 6)).wrapping_sub(seed);
    let x1 = get_u64(data, 0) ^ s1;
    let x2 = get_u64(&data[data.len() - 8..], 0) ^ s2;
    let mut result = data.len() as u64;
    result = result.wrapping_add(x1.swap_bytes());
    result = result.wrapping_add(x2);
    result = result.wrapping_add(mul128_and_xor(x1, x2));
    xxh3_avalanche(result)
}

fn hash64_0to16(data: &[u8], secret: &[u8], seed: u64) -> u64 {
    if data.is_empty() {
        hash64_0(secret, seed)
    } else if data.len() < 4 {
        hash64_1to3(data, secret, seed)
    } else if data.len() <= 8 {
        hash64_4to8(data, secret, seed)
    } else {
        hash64_9to16(data, secret, seed)
    }
}

fn hash64_17to128(data: &[u8], secret: &[u8], seed: u64) -> u64 {
    let mut result = PRIME64[0].wrapping_mul(data.len() as u64);
    let iterations = (data.len() - 1) / 32;
    for i in (0..=iterations).rev() {
        result = result.wrapping_add(mix16(&data[16 * i..], &secret[32 * i..], seed));
        result = result.wrapping_add(mix16(
            &data[data.len() - 16 * (i + 1)..],
            &secret[32 * i + 16..],
            seed,
        ));
    }
    xxh3_avalanche(result)
}

fn hash64_129to240(data: &[u8], secret: &[u8], seed: u64) -> u64 {
    let mut result = PRIME64[0].wrapping_mul(data.len() as u64);
    for i in 0..8 {
        result = result.wrapping_add(mix16(&data[16 * i..], &secret[16 * i..], seed));
    }
    result = xxh3_avalanche(result);
    let iterations = data.len() / 16;
    for i in 8..iterations {
        result = result.wrapping_add(mix16(&data[16 * i..], &secret[16 * (i - 8) + 3..], seed));
    }
    result = result.wrapping_add(mix16(
        &data[data.len() - 16..],
        &secret[MIN_SECRET_SIZE - 17..],
        seed,
    ));

    xxh3_avalanche(result)
}

fn hash64_0to240(data: &[u8], secret: &[u8], seed: u64) -> u64 {
    if data.len() <= 16 {
        hash64_0to16(data, secret, seed)
    } else if data.len() <= 128 {
        hash64_17to128(data, secret, seed)
    } else {
        hash64_129to240(data, secret, seed)
    }
}

#[cfg(target_arch = "aarch64")]
unsafe fn hash64_large_neon(data: &[u8], seed: u64) -> u64 {
    hash64_large_generic(
        data,
        seed,
        gen_secret_generic,
        scramble_accumulators_neon,
        accumulate_stripe_neon,
    )
}

#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
#[target_feature(enable = "avx2")]
unsafe fn hash64_large_avx2(data: &[u8], seed: u64) -> u64 {
    hash64_large_generic(
        data,
        seed,
        gen_secret_avx2,
        scramble_accumulators_avx2,
        accumulate_stripe_avx2,
    )
}

#[inline(always)]
fn hash64_large_generic(
    data: &[u8],
    seed: u64,
    generate: unsafe fn(u64) -> [u8; DEFAULT_SECRET.len()],
    scramble: unsafe fn(&mut [u64; 8], &[u8]),
    accum_stripe: unsafe fn(&mut [u64; 8], &[u8], &[u8]),
) -> u64 {
    // SAFETY: `generate` is either `gen_secret_generic` (safe, no CPU
    // requirement) or `gen_secret_avx2` (caller guarantees AVX2 is available
    // via `is_x86_feature_detected!` or `#[target_feature]`).
    let secret = unsafe { generate(seed) };
    let accumulators = hash_large_helper(data, &secret, scramble, accum_stripe);

    merge_accumulators(
        accumulators,
        &secret[11..],
        PRIME64[0].wrapping_mul(data.len() as u64),
    )
}

fn hash128_0(secret: &[u8], seed: u64) -> u128 {
    let high = (hash64_0(&secret[3 * 8..], seed) as u128) << 64;
    let low = hash64_0(&secret[8..], seed) as u128;
    high | low
}

fn hash128_1to3(data: &[u8], secret: &[u8], seed: u64) -> u128 {
    let x1 = data[0] as u32;
    let x2 = data[data.len() >> 1] as u32;
    let x3 = (*data.last().unwrap()) as u32;
    #[allow(clippy::cast_possible_truncation)]
    let x4 = data.len() as u32;

    let combined_low = (x1 << 16) | (x2 << 24) | x3 | (x4 << 8);
    let combined_high: u64 = combined_low.swap_bytes().rotate_left(13).into();
    let s_low = ((get_u32(secret, 0) ^ get_u32(secret, 1)) as u64).wrapping_add(seed);
    let s_high = ((get_u32(secret, 2) ^ get_u32(secret, 3)) as u64).wrapping_sub(seed);
    let high = (xxh64_avalanche(combined_high ^ s_high) as u128) << 64;
    let low = xxh64_avalanche(combined_low as u64 ^ s_low) as u128;
    high | low
}

fn hash128_4to8(data: &[u8], secret: &[u8], mut seed: u64) -> u128 {
    #[allow(clippy::cast_possible_truncation)]
    let truncate_seed = seed as u32;
    seed ^= u64::from(truncate_seed.swap_bytes()) << 32;
    let x_low = get_u32(data, 0) as u64;
    let x_high = u32::from_le_bytes(data[data.len() - 4..].try_into().unwrap()) as u64;
    let x = x_low | (x_high << 32);
    let s = (get_u64(secret, 2) ^ get_u64(secret, 3)).wrapping_add(seed);

    let mut y = (x ^ s) as u128;
    y = y.wrapping_mul(PRIME64[0].wrapping_add((data.len() << 2) as u64) as u128);

    #[allow(clippy::cast_possible_truncation)]
    let mut r_low = y as u64;
    let mut r_high: u64 = (y >> 64).try_into().unwrap();
    r_high = r_high.wrapping_add(r_low << 1);
    r_low ^= r_high >> 3;
    r_low = xorshift(r_low, 35);
    r_low = r_low.wrapping_mul(0x9FB21C651E98DF25);
    r_low = xorshift(r_low, 28);
    r_high = xxh3_avalanche(r_high);

    ((r_high as u128) << 64) | r_low as u128
}

fn hash128_9to16(data: &[u8], secret: &[u8], seed: u64) -> u128 {
    let s_low = (get_u64(secret, 4) ^ get_u64(secret, 5)).wrapping_sub(seed);
    let s_high = (get_u64(secret, 6) ^ get_u64(secret, 7)).wrapping_add(seed);
    let x_low = get_u64(data, 0);
    let x_high = u64::from_le_bytes(data[data.len() - 8..].try_into().unwrap());
    let mixed = x_low ^ x_high ^ s_low;
    let x_high = x_high ^ s_high;

    let result = (mixed as u128).wrapping_mul(PRIME64[0] as u128);
    #[allow(clippy::cast_possible_truncation)]
    let mut r_low = result as u64;
    let mut r_high = (result >> 64) as u64;
    r_low = r_low.wrapping_add((data.len() as u64 - 1) << 54);
    r_high = r_high.wrapping_add(x_high);
    r_high = r_high.wrapping_add((x_high & 0xFFFF_FFFF).wrapping_mul(PRIME32[1] - 1));
    r_low ^= r_high.swap_bytes();

    let result2 = (r_low as u128).wrapping_mul(PRIME64[1] as u128);
    #[allow(clippy::cast_possible_truncation)]
    let mut r2_low = result2 as u64;
    let mut r2_high = (result2 >> 64) as u64;
    r2_high = r2_high.wrapping_add(r_high.wrapping_mul(PRIME64[1]));
    r2_low = xxh3_avalanche(r2_low);
    r2_high = xxh3_avalanche(r2_high);

    ((r2_high as u128) << 64) | r2_low as u128
}

fn hash128_0to16(data: &[u8], secret: &[u8], seed: u64) -> u128 {
    if data.is_empty() {
        hash128_0(secret, seed)
    } else if data.len() < 4 {
        hash128_1to3(data, secret, seed)
    } else if data.len() <= 8 {
        hash128_4to8(data, secret, seed)
    } else {
        hash128_9to16(data, secret, seed)
    }
}

fn hash128_17to128(data: &[u8], secret: &[u8], seed: u64) -> u128 {
    let len = data.len();
    let mut state = (PRIME64[0].wrapping_mul(len as u64), 0);
    if len > 32 {
        if len > 64 {
            if len > 96 {
                state = mix32(state, &data[48..], &data[len - 64..], &secret[96..], seed);
            }
            state = mix32(state, &data[32..], &data[len - 48..], &secret[64..], seed);
        }
        state = mix32(state, &data[16..], &data[len - 32..], &secret[32..], seed);
    }
    state = mix32(state, data, &data[len - 16..], secret, seed);

    let mut r_low = state.0.wrapping_add(state.1);
    let mut r_high = state.0.wrapping_mul(PRIME64[0]);
    r_high = r_high.wrapping_add(state.1.wrapping_mul(PRIME64[3]));
    r_high = r_high.wrapping_add((len as u64).wrapping_sub(seed).wrapping_mul(PRIME64[1]));
    r_low = xxh3_avalanche(r_low);
    r_high = 0u64.wrapping_sub(xxh3_avalanche(r_high));

    ((r_high as u128) << 64) | r_low as u128
}

fn hash128_129to240(data: &[u8], secret: &[u8], seed: u64) -> u128 {
    let len = data.len();
    let iterations = len / 32;
    let mut state = (PRIME64[0].wrapping_mul(len as u64), 0);

    for i in 0..4 {
        state = mix32(
            state,
            &data[32 * i..],
            &data[32 * i + 16..],
            &secret[32 * i..],
            seed,
        );
    }
    state.0 = xxh3_avalanche(state.0);
    state.1 = xxh3_avalanche(state.1);

    for i in 4..iterations {
        state = mix32(
            state,
            &data[32 * i..],
            &data[32 * i + 16..],
            &secret[3 + 32 * (i - 4)..],
            seed,
        );
    }
    state = mix32(
        state,
        &data[len - 16..],
        &data[len - 32..],
        &secret[MIN_SECRET_SIZE - 33..],
        0u64.wrapping_sub(seed),
    );

    let mut r_low = state.0.wrapping_add(state.1);
    let mut r_high = state.0.wrapping_mul(PRIME64[0]);
    r_high = r_high.wrapping_add(state.1.wrapping_mul(PRIME64[3]));
    r_high = r_high.wrapping_add((len as u64).wrapping_sub(seed).wrapping_mul(PRIME64[1]));
    r_low = xxh3_avalanche(r_low);
    r_high = 0u64.wrapping_sub(xxh3_avalanche(r_high));

    ((r_high as u128) << 64) | r_low as u128
}

fn hash128_0to240(data: &[u8], secret: &[u8], seed: u64) -> u128 {
    if data.len() <= 16 {
        hash128_0to16(data, secret, seed)
    } else if data.len() <= 128 {
        hash128_17to128(data, secret, seed)
    } else {
        hash128_129to240(data, secret, seed)
    }
}

#[cfg(target_arch = "aarch64")]
unsafe fn hash128_large_neon(data: &[u8], seed: u64) -> u128 {
    hash128_large_generic(
        data,
        seed,
        gen_secret_generic,
        scramble_accumulators_neon,
        accumulate_stripe_neon,
    )
}

#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
#[target_feature(enable = "avx2")]
unsafe fn hash128_large_avx2(data: &[u8], seed: u64) -> u128 {
    hash128_large_generic(
        data,
        seed,
        gen_secret_avx2,
        scramble_accumulators_avx2,
        accumulate_stripe_avx2,
    )
}

#[inline(always)]
fn hash128_large_generic(
    data: &[u8],
    seed: u64,
    generate: unsafe fn(u64) -> [u8; DEFAULT_SECRET.len()],
    scramble: unsafe fn(&mut [u64; 8], &[u8]),
    accum_stripe: unsafe fn(&mut [u64; 8], &[u8], &[u8]),
) -> u128 {
    // SAFETY: `generate` is either `gen_secret_generic` (safe, no CPU
    // requirement) or `gen_secret_avx2` (caller guarantees AVX2 is available
    // via `is_x86_feature_detected!` or `#[target_feature]`).
    let secret = unsafe { generate(seed) };
    let accumulators = hash_large_helper(data, &secret, scramble, accum_stripe);

    let low = merge_accumulators(
        accumulators,
        &secret[11..],
        PRIME64[0].wrapping_mul(data.len() as u64),
    );
    let high = merge_accumulators(
        accumulators,
        &secret[secret.len() - 64 - 11..],
        !(PRIME64[1].wrapping_mul(data.len() as u64)),
    );

    ((high as u128) << 64) | low as u128
}

// ---------------------------------------------------------------------------
// Streaming xxh3 hasher
// ---------------------------------------------------------------------------

const STRIPES_PER_BLOCK: usize = (DEFAULT_SECRET.len() - STRIPE_LENGTH) / SECRET_CONSUME_RATE;

/// Incremental xxh3 hasher that produces results identical to the one-shot
/// `hash64_with_seed` / `hash128_with_seed` functions, but processes data in
/// arbitrary-sized chunks with constant memory overhead.
///
/// For inputs <= 240 bytes the data is buffered and hashed at finalization
/// using the one-shot path. For larger inputs, 64-byte stripes are accumulated
/// incrementally and the trailing stripe is applied at finalization.
pub(crate) struct Xxh3StreamHasher {
    seed: u64,
    total_len: usize,
    accumulators: [u64; 8],
    stripe_count_in_block: usize,
    /// Unprocessed bytes. In small mode (total_len <= 240), this holds ALL
    /// data. In large mode, it holds at most STRIPE_LENGTH bytes -- we always
    /// retain the last incomplete stripe so we can correctly identify the
    /// trailing stripe at finalization.
    buf: Vec<u8>,
    /// The last STRIPE_LENGTH bytes of all data seen so far (for the trailing
    /// stripe in large mode). Only meaningful when total_len >= STRIPE_LENGTH.
    last_stripe: [u8; STRIPE_LENGTH],
    secret: [u8; DEFAULT_SECRET.len()],
}

impl Xxh3StreamHasher {
    pub(crate) fn new(seed: u64) -> Self {
        let secret = if seed == 0 {
            DEFAULT_SECRET
        } else {
            gen_secret_generic(seed)
        };
        Self {
            seed,
            total_len: 0,
            accumulators: INIT_ACCUMULATORS,
            stripe_count_in_block: 0,
            buf: Vec::with_capacity(256),
            last_stripe: [0u8; STRIPE_LENGTH],
            secret,
        }
    }

    pub(crate) fn update(&mut self, data: &[u8]) {
        if data.is_empty() {
            return;
        }
        self.total_len += data.len();
        self.update_last_stripe(data);
        self.buf.extend_from_slice(data);

        if self.total_len > 240 {
            self.drain_stripes();
        }
    }

    pub(crate) fn finish_128(self) -> u128 {
        if self.total_len <= 240 {
            return hash128_0to240(&self.buf, &DEFAULT_SECRET, self.seed);
        }

        let mut accumulators = self.accumulators;
        accumulate_stripe_generic(
            &mut accumulators,
            &self.last_stripe,
            &self.secret[self.secret.len() - STRIPE_LENGTH - 7..],
        );

        let low = merge_accumulators(
            accumulators,
            &self.secret[11..],
            PRIME64[0].wrapping_mul(self.total_len as u64),
        );
        let high = merge_accumulators(
            accumulators,
            &self.secret[self.secret.len() - 64 - 11..],
            !(PRIME64[1].wrapping_mul(self.total_len as u64)),
        );

        ((high as u128) << 64) | low as u128
    }

    pub(crate) fn finish_64(self) -> u64 {
        if self.total_len <= 240 {
            return hash64_0to240(&self.buf, &DEFAULT_SECRET, self.seed);
        }

        let mut accumulators = self.accumulators;
        accumulate_stripe_generic(
            &mut accumulators,
            &self.last_stripe,
            &self.secret[self.secret.len() - STRIPE_LENGTH - 7..],
        );

        merge_accumulators(
            accumulators,
            &self.secret[11..],
            PRIME64[0].wrapping_mul(self.total_len as u64),
        )
    }

    /// Process as many complete stripes as possible from `buf`, always leaving
    /// at most `STRIPE_LENGTH` bytes. The invariant: after this call,
    /// `buf.len() <= STRIPE_LENGTH`.
    ///
    /// We use `> STRIPE_LENGTH` (not `>=`) so that when the total length is an
    /// exact multiple of 64, the final complete stripe remains in `buf` rather
    /// than being processed as a regular stripe. This matches the one-shot
    /// algorithm which computes `(total_len - 1) / STRIPE_LENGTH` regular
    /// stripes.
    fn drain_stripes(&mut self) {
        let mut pos = 0;
        while self.buf.len() - pos > STRIPE_LENGTH {
            accumulate_stripe_generic(
                &mut self.accumulators,
                &self.buf[pos..pos + STRIPE_LENGTH],
                &self.secret[self.stripe_count_in_block * SECRET_CONSUME_RATE..],
            );
            pos += STRIPE_LENGTH;
            self.stripe_count_in_block += 1;
            if self.stripe_count_in_block == STRIPES_PER_BLOCK {
                scramble_accumulators_generic(
                    &mut self.accumulators,
                    &self.secret[self.secret.len() - STRIPE_LENGTH..],
                );
                self.stripe_count_in_block = 0;
            }
        }
        if pos > 0 {
            self.buf.drain(..pos);
        }
    }

    /// Maintain `last_stripe` as the last STRIPE_LENGTH bytes of all data seen.
    fn update_last_stripe(&mut self, data: &[u8]) {
        if data.len() >= STRIPE_LENGTH {
            self.last_stripe
                .copy_from_slice(&data[data.len() - STRIPE_LENGTH..]);
        } else {
            let shift = data.len();
            self.last_stripe.copy_within(shift.., 0);
            self.last_stripe[STRIPE_LENGTH - shift..].copy_from_slice(data);
        }
    }
}

#[cfg(test)]
mod test {
    use crate::tree_store::page_store::xxh3::{
        Xxh3StreamHasher, hash64_with_seed, hash128_with_seed,
    };

    #[test]
    fn test_empty() {
        let actual = hash64_with_seed(&[], 0);
        assert_eq!(actual, 3244421341483603138);
    }

    #[test]
    fn streaming_xxh3_matches_oneshot_128() {
        let sizes = [
            0,
            1,
            3,
            4,
            8,
            16,
            17,
            63,
            64,
            65,
            127,
            128,
            129,
            200,
            240,
            241,
            256,
            300,
            512,
            1023,
            1024,
            1025,
            4096,
            65536,
            1024 * 1024,
        ];
        for &size in &sizes {
            let data: Vec<u8> = (0..size).map(|i| (i % 251) as u8).collect();
            let expected = hash128_with_seed(&data, 0);

            // Single-shot streaming
            let mut h = Xxh3StreamHasher::new(0);
            h.update(&data);
            let actual = h.finish_128();
            assert_eq!(actual, expected, "size={size} single-update mismatch");

            // Chunked streaming (various chunk sizes)
            for chunk_size in [1, 3, 7, 13, 31, 63, 64, 65, 128, 256] {
                if chunk_size > size && size > 0 {
                    continue;
                }
                let mut h = Xxh3StreamHasher::new(0);
                for chunk in data.chunks(chunk_size.max(1)) {
                    h.update(chunk);
                }
                let actual = h.finish_128();
                assert_eq!(
                    actual, expected,
                    "size={size} chunk_size={chunk_size} mismatch"
                );
            }
        }
    }

    #[test]
    fn streaming_xxh3_matches_oneshot_64() {
        let sizes = [0, 1, 16, 128, 240, 241, 1024, 65536];
        for &size in &sizes {
            let data: Vec<u8> = (0..size).map(|i| (i % 251) as u8).collect();
            let expected = hash64_with_seed(&data, 0);

            let mut h = Xxh3StreamHasher::new(0);
            h.update(&data);
            let actual = h.finish_64();
            assert_eq!(actual, expected, "size={size} mismatch");

            // Chunked
            let mut h = Xxh3StreamHasher::new(0);
            for chunk in data.chunks(64) {
                h.update(chunk);
            }
            let actual = h.finish_64();
            assert_eq!(actual, expected, "size={size} chunked mismatch");
        }
    }

    #[test]
    fn streaming_xxh3_with_seed() {
        let data: Vec<u8> = (0..1000).map(|i| (i % 251) as u8).collect();
        let seed = 0xDEAD_BEEF_u64;

        let expected_128 = hash128_with_seed(&data, seed);
        let expected_64 = hash64_with_seed(&data, seed);

        let mut h128 = Xxh3StreamHasher::new(seed);
        let mut h64 = Xxh3StreamHasher::new(seed);
        for chunk in data.chunks(77) {
            h128.update(chunk);
            h64.update(chunk);
        }
        assert_eq!(h128.finish_128(), expected_128);
        assert_eq!(h64.finish_64(), expected_64);
    }

    #[test]
    fn streaming_xxh3_empty_updates() {
        let data = b"hello world";
        let expected = hash128_with_seed(data, 0);

        let mut h = Xxh3StreamHasher::new(0);
        h.update(b"");
        h.update(b"hello");
        h.update(b"");
        h.update(b" world");
        h.update(b"");
        assert_eq!(h.finish_128(), expected);
    }
}
