wedb_embed 0.1.0

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;
/// 分段总数（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)
}

/// 从 64 位哈希值中提取 14 位桶索引和 50 位尾随零计数（对标 Apache Kvrocks ExtractDenseHllResult）
#[inline]
pub 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 m = HLL_REGISTERS as f64;
    let mut z = m * hll_tau((m - reghisto[HLL_HASH_BIT_COUNT + 1] as f64) / m);
    for j in (1..=HLL_HASH_BIT_COUNT).rev() {
        z += reghisto[j] as f64;
        z *= 0.5;
    }
    z += m * hll_sigma(reghisto[0] as f64 / m);
    if z <= 0.0 || z.is_nan() || z.is_infinite() {
        0
    } else {
        (HLL_ALPHA_INF * m * m / z).round() as u64
    }
}