wedb_embed 0.1.1

use rapidhash::v3::rapidhash_v3;

/// HyperLogLog 寄存器总数（2^14 = 16384，对标 Apache Kvrocks kHyperLogLogRegisterCount）
pub const HLL_REGISTERS: usize = 16384;
/// 密集存储字节数（16384 * 6 位 / 8 = 12288 字节，对标 Apache Kvrocks kHyperLogLogRegisterBytes）
pub const HLL_DENSE_SIZE: usize = 12288;
/// 桶索引位数（14 位，对标 Apache Kvrocks kHyperLogLogRegisterCountPow）
pub const HLL_REGISTER_COUNT_POW: usize = 14;
/// 桶索引掩码（0x3FFF，对标 Apache Kvrocks kHyperLogLogRegisterCountMask）
pub const HLL_REGISTER_COUNT_MASK: u64 = (1 << HLL_REGISTER_COUNT_POW) - 1;
/// 剩余哈希位数（50 位，对标 Apache Kvrocks kHyperLogLogHashBitCount）
pub const HLL_HASH_BIT_COUNT: usize = 50;
/// 单个寄存器位宽（6 位，对标 Apache Kvrocks kHyperLogLogRegisterBits）
pub const HLL_REGISTER_BITS: usize = 6;
/// 6-bit 寄存器最大值（63，对标 Apache Kvrocks kHyperLogLogRegisterMax）
pub const HLL_REGISTER_MAX: u8 = (1 << HLL_REGISTER_BITS) - 1;
/// 渐近常数 alpha_infinity = 0.5 / ln(2)（对标 Apache Kvrocks kHyperLogLogAlpha）
pub const HLL_ALPHA_INF: f64 = 0.721_347_520_444_481_7;
/// 寄存器数量浮点常数 m = 16384.0
pub const HLL_M_F64: f64 = HLL_REGISTERS as f64;
/// 寄存器数量倒数 1.0 / m
pub const HLL_INV_M: f64 = 1.0 / HLL_M_F64;
/// 预计算常量 alpha * m^2（编译期计算，避免运行时重复乘法）
pub const HLL_ALPHA_M_SQ: f64 = HLL_ALPHA_INF * HLL_M_F64 * HLL_M_F64;
/// 分段总数（16 段，对标 Apache Kvrocks kHyperLogLogSegmentCount）
pub const HLL_SEGMENT_COUNT: usize = 16;
/// 每段寄存器数（1024，对标 Apache Kvrocks kHyperLogLogSegmentRegisters）
pub const HLL_SEGMENT_REGISTERS: usize = 1024;
/// 每段字节数（768 字节，对标 Apache Kvrocks kHyperLogLogSegmentBytes）
pub const HLL_SEGMENT_BYTES: usize = 768;
/// 哈希种子常量（对标 Apache Kvrocks kHyperLogLogHashSeed）
pub const HLL_HASH_SEED: u32 = 0xadc8_3b19;

/// RapidHash 64 位哈希函数
#[inline]
pub fn rapid_hash(bytes: &[u8]) -> u64 {
    rapidhash_v3(bytes)
}

/// MurmurHash64A 哈希函数（1:1 对标 Redis / Apache Kvrocks HllMurMurHash64A）
#[inline]
pub fn murmur_hash_64a(data: &[u8], seed: u32) -> u64 {
    const M: u64 = 0xc6a4_a793_5bd1_e995;
    const R: u32 = 47;
    let len = data.len();
    let mut h = (seed as u64) ^ ((len as u64).wrapping_mul(M));

    let (chunks, remainder) = data.as_chunks::<8>();
    for chunk in chunks {
        let mut k = u64::from_le_bytes(*chunk);
        k = k.wrapping_mul(M);
        k ^= k >> R;
        k = k.wrapping_mul(M);
        h ^= k;
        h = h.wrapping_mul(M);
    }

    if !remainder.is_empty() {
        let mut k = 0u64;
        for (i, &b) in remainder.iter().enumerate() {
            k |= (b as u64) << (i * 8);
        }
        h ^= k;
        h = h.wrapping_mul(M);
    }

    h ^= h >> R;
    h = h.wrapping_mul(M);
    h ^= h >> R;
    h
}

/// 兼容 Redis / Kvrocks 默认 seed 的 HLL MurmurHash64A（对标 Apache Kvrocks HyperLogLog::HllHash）
#[inline]
pub fn hll_murmur_hash_64a(data: &[u8]) -> u64 {
    murmur_hash_64a(data, HLL_HASH_SEED)
}

/// 从 64 位哈希值中提取 14 位桶索引和 50 位尾随零计数（对标 Apache Kvrocks ExtractDenseHllResult）
#[inline]
pub const fn extract_dense_hll_result(hash: u64) -> (usize, u8) {
    let index = (hash & HLL_REGISTER_COUNT_MASK) as usize;
    let shifted = (hash >> HLL_REGISTER_COUNT_POW) | (1u64 << HLL_HASH_BIT_COUNT);
    let count = (shifted.trailing_zeros() + 1) as u8;
    (index, count)
}

/// Otmar Ertl 辅助函数 sigma (arXiv:1702.01284，对标 Apache Kvrocks HllSigma)
#[inline]
pub fn hll_sigma(x: f64) -> f64 {
    if x <= 0.0 || x.is_nan() {
        return 0.0;
    }
    if x >= 1.0 {
        return f64::INFINITY;
    }
    let mut x = x;
    let mut y = 1.0;
    let mut z = x;
    loop {
        x *= x;
        let z_prime = z;
        z += x * y;
        y += y;
        if z_prime == z {
            break;
        }
    }
    z
}

/// Otmar Ertl 辅助函数 tau (arXiv:1702.01284，对标 Apache Kvrocks HllTau)
#[inline]
pub fn hll_tau(x: f64) -> f64 {
    if x <= 0.0 || x >= 1.0 || x.is_nan() {
        return 0.0;
    }
    let mut x = x;
    let mut y = 1.0;
    let mut z = 1.0 - x;
    loop {
        x = x.sqrt();
        let z_prime = z;
        y *= 0.5;
        let diff = 1.0 - x;
        z -= diff * diff * y;
        if z_prime == z {
            break;
        }
    }
    z / 3.0
}

/// 基于寄存器直方图使用 Otmar Ertl (2017) LogLog-Beta 算法计算基数估算（零堆分配极速计算）
#[inline]
pub fn hll_estimate_from_histo(reghisto: &[usize; 64]) -> u64 {
    let mut z =
        HLL_M_F64 * hll_tau((HLL_M_F64 - reghisto[HLL_HASH_BIT_COUNT + 1] as f64) * HLL_INV_M);
    for j in (1..=HLL_HASH_BIT_COUNT).rev() {
        z += reghisto[j] as f64;
        z *= 0.5;
    }
    z += HLL_M_F64 * hll_sigma(reghisto[0] as f64 * HLL_INV_M);
    if z <= 0.0 || z.is_nan() || z.is_infinite() {
        0
    } else {
        (HLL_ALPHA_M_SQ / z).round() as u64
    }
}