use std::sync::OnceLock;
use crate::error::{MnemoError, Result};
use crate::format::PAYLOAD;
pub(crate) const PAGE_HEADER: usize = 16;
pub(crate) const PAGE_KIND_VECTOR: u8 = 2;
pub(crate) fn entry_len(dims: usize) -> usize {
dims * 2 + 4
}
pub(crate) fn per_page(dims: usize) -> usize {
(PAYLOAD - PAGE_HEADER) / entry_len(dims)
}
pub(crate) fn f32_to_f16(x: f32) -> u16 {
let b = x.to_bits();
let sign = ((b >> 16) & 0x8000) as u16;
let exp = ((b >> 23) & 0xff) as i32;
let man = b & 0x007f_ffff;
if exp == 0xff {
return sign | 0x7c00 | if man != 0 { 0x0200 } else { 0 };
}
let e = exp - 127 + 15;
if e >= 0x1f {
return sign | 0x7c00;
}
if e <= 0 {
if e < -10 {
return sign;
}
let m = man | 0x0080_0000;
let shift = (14 - e) as u32;
let half = m >> shift;
let rem = m & ((1u32 << shift) - 1);
let halfway = 1u32 << (shift - 1);
let mut h = half;
if rem > halfway || (rem == halfway && (half & 1) == 1) {
h += 1;
}
return sign | h as u16;
}
let mut h = ((e as u32) << 10) | (man >> 13);
let rem = man & 0x1fff;
if rem > 0x1000 || (rem == 0x1000 && (h & 1) == 1) {
h += 1;
}
sign | h as u16
}
pub(crate) fn f16_to_f32(h: u16) -> f32 {
let sign = ((h & 0x8000) as u32) << 16;
let exp = ((h >> 10) & 0x1f) as u32;
let man = (h & 0x03ff) as u32;
let bits = if exp == 0 {
if man == 0 {
sign
} else {
let mut e = 113u32;
let mut m = man;
while m & 0x0400 == 0 {
m <<= 1;
e -= 1;
}
sign | (e << 23) | ((m & 0x03ff) << 13)
}
} else if exp == 0x1f {
sign | 0x7f80_0000 | (man << 13)
} else {
sign | ((exp + 112) << 23) | (man << 13)
};
f32::from_bits(bits)
}
fn table() -> &'static [f32] {
static TABLE: OnceLock<Vec<f32>> = OnceLock::new();
TABLE.get_or_init(|| (0..=u16::MAX).map(f16_to_f32).collect())
}
pub(crate) fn quantize(v: &[f32]) -> (Vec<u16>, f32) {
let h: Vec<u16> = v.iter().map(|&x| f32_to_f16(x)).collect();
let t = table();
let norm = h
.iter()
.map(|&x| {
let f = t[x as usize];
f * f
})
.sum::<f32>()
.sqrt();
(h, norm)
}
pub(crate) fn dequantize(h: &[u16]) -> Vec<f32> {
let t = table();
h.iter().map(|&x| t[x as usize]).collect()
}
#[inline(always)]
fn widen(h: u16) -> f32 {
let h = h as u32;
let mag = f32::from_bits((h & 0x7fff) << 13) * f32::from_bits(0x7780_0000);
f32::from_bits(mag.to_bits() | ((h & 0x8000) << 16))
}
pub(crate) fn dot_f16(q: &[f32], h: &[u16]) -> f32 {
let n = q.len().min(h.len());
let (q, h) = (&q[..n], &h[..n]);
let mut acc = [0f32; 8];
let mut qc = q.chunks_exact(8);
let mut hc = h.chunks_exact(8);
for (qa, ha) in (&mut qc).zip(&mut hc) {
let qa: &[f32; 8] = qa.try_into().expect("chunk of 8");
let ha: &[u16; 8] = ha.try_into().expect("chunk of 8");
for ((a, &x), &y) in acc.iter_mut().zip(qa).zip(ha) {
*a += x * widen(y);
}
}
let mut sum = ((acc[0] + acc[4]) + (acc[1] + acc[5])) + ((acc[2] + acc[6]) + (acc[3] + acc[7]));
for (&x, &y) in qc.remainder().iter().zip(hc.remainder()) {
sum += x * widen(y);
}
sum
}
pub(crate) fn similarity_f16(
metric: crate::memory::Metric,
q: &[f32],
q_norm: f32,
h: &[u16],
v_norm: f32,
) -> f32 {
use crate::memory::Metric;
let dot = dot_f16(q, h);
match metric {
Metric::Dot => dot,
Metric::Cosine => {
if q_norm == 0.0 || v_norm == 0.0 {
0.0
} else {
dot / (q_norm * v_norm)
}
}
Metric::L2 => {
let d2 = (q_norm * q_norm + v_norm * v_norm - 2.0 * dot).max(0.0);
1.0 / (1.0 + d2.sqrt())
}
}
}
pub(crate) fn encode_page(dims: usize, gen: u64, entries: &[(&[u16], f32)]) -> Vec<u8> {
let el = entry_len(dims);
let mut out = Vec::with_capacity(PAGE_HEADER + entries.len() * el);
out.push(PAGE_KIND_VECTOR);
out.push(0); out.push(0); out.push(0); out.extend_from_slice(&(entries.len() as u16).to_le_bytes());
out.extend_from_slice(&((entries.len() * el) as u16).to_le_bytes());
out.extend_from_slice(&gen.to_le_bytes());
for (h, norm) in entries {
for x in h.iter() {
out.extend_from_slice(&x.to_le_bytes());
}
out.extend_from_slice(&norm.to_le_bytes());
}
out
}
pub(crate) fn decode_entry_into(
page: &[u8],
dims: usize,
slot: usize,
out: &mut [u16],
) -> Result<f32> {
let bad = || MnemoError::Invalid("malformed vector page".into());
if page.len() < PAGE_HEADER || page[0] != PAGE_KIND_VECTOR || out.len() != dims {
return Err(bad());
}
let n = u16::from_le_bytes([page[4], page[5]]) as usize;
if slot >= n {
return Err(bad());
}
let el = entry_len(dims);
let o = PAGE_HEADER + slot * el;
let e = page.get(o..o + el).ok_or_else(bad)?;
for (dst, c) in out.iter_mut().zip(e[..dims * 2].chunks_exact(2)) {
*dst = u16::from_le_bytes([c[0], c[1]]);
}
Ok(f32::from_le_bytes([
e[dims * 2],
e[dims * 2 + 1],
e[dims * 2 + 2],
e[dims * 2 + 3],
]))
}
pub(crate) fn decode_entry(page: &[u8], dims: usize, slot: usize) -> Result<(Vec<u16>, f32)> {
let bad = || MnemoError::Invalid("malformed vector page".into());
if page.len() < PAGE_HEADER || page[0] != PAGE_KIND_VECTOR {
return Err(bad());
}
let n = u16::from_le_bytes([page[4], page[5]]) as usize;
if slot >= n {
return Err(bad());
}
let el = entry_len(dims);
let o = PAGE_HEADER + slot * el;
let e = page.get(o..o + el).ok_or_else(bad)?;
let h: Vec<u16> = e[..dims * 2]
.chunks_exact(2)
.map(|c| u16::from_le_bytes([c[0], c[1]]))
.collect();
let norm = f32::from_le_bytes([
e[dims * 2],
e[dims * 2 + 1],
e[dims * 2 + 2],
e[dims * 2 + 3],
]);
Ok((h, norm))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn f16_round_trip_is_exact_for_every_half() {
for h in 0..=u16::MAX {
let f = f16_to_f32(h);
if f.is_nan() {
assert!(f16_to_f32(f32_to_f16(f)).is_nan());
continue;
}
assert_eq!(f32_to_f16(f), h, "half {h:#06x} -> {f} -> back");
}
}
#[test]
fn f32_to_f16_rounds_to_nearest_even() {
assert_eq!(f32_to_f16(1.0), 0x3c00);
assert_eq!(f32_to_f16(-2.0), 0xc000);
assert_eq!(f32_to_f16(65504.0), 0x7bff);
assert_eq!(f32_to_f16(1e9), 0x7c00);
assert_eq!(f32_to_f16(0.0), 0);
assert_eq!(f32_to_f16(-0.0), 0x8000);
assert_eq!(f32_to_f16(1.0 + 2f32.powi(-11)), 0x3c00);
assert_eq!(f32_to_f16(1.0 + 2f32.powi(-11) + 2f32.powi(-20)), 0x3c01);
assert_eq!(f32_to_f16(2f32.powi(-24)), 1);
assert_eq!(f32_to_f16(2f32.powi(-25)), 0);
for i in 1..1000 {
let x = i as f32 * 0.000_37 - 0.18;
let y = f16_to_f32(f32_to_f16(x));
assert!((x - y).abs() <= x.abs() * 2f32.powi(-11) + 2f32.powi(-25));
}
}
#[test]
fn fast_widen_is_exact_for_every_finite_half() {
for h in 0..=u16::MAX {
let f = f16_to_f32(h);
if f.is_finite() {
assert_eq!(widen(h).to_bits(), f.to_bits(), "half {h:#06x}");
}
}
let q: Vec<f32> = (0..19).map(|i| i as f32 * 0.1 - 0.7).collect();
let (h, _) = quantize(&q);
let slow: f32 = q.iter().zip(dequantize(&h)).map(|(a, b)| a * b).sum();
assert!((dot_f16(&q, &h) - slow).abs() < 1e-5);
}
#[test]
fn page_round_trip_and_similarity() {
let dims = 384;
assert_eq!(entry_len(dims), 772);
assert_eq!(per_page(dims), 10);
let vs: Vec<Vec<f32>> = (0..10)
.map(|k| {
(0..dims)
.map(|i| ((i * 7 + k * 13) % 17) as f32 / 17.0 - 0.5)
.collect()
})
.collect();
let qs: Vec<(Vec<u16>, f32)> = vs.iter().map(|v| quantize(v)).collect();
let refs: Vec<(&[u16], f32)> = qs.iter().map(|(h, n)| (h.as_slice(), *n)).collect();
let page = encode_page(dims, 42, &refs);
assert!(page.len() <= PAYLOAD);
for (slot, (h, n)) in qs.iter().enumerate() {
let (h2, n2) = decode_entry(&page, dims, slot).unwrap();
assert_eq!(&h2, h);
assert_eq!(n2, *n);
}
assert!(decode_entry(&page, dims, 10).is_err());
let q = &vs[3];
let qn = q.iter().map(|x| x * x).sum::<f32>().sqrt();
for (v, (h, n)) in vs.iter().zip(&qs) {
for metric in [
crate::memory::Metric::Cosine,
crate::memory::Metric::Dot,
crate::memory::Metric::L2,
] {
let exact = crate::memory::similarity(metric, q, v);
let approx = similarity_f16(metric, q, qn, h, *n);
let tol = 2e-3 * exact.abs().max(1.0);
assert!(
(exact - approx).abs() < tol,
"{metric:?}: {exact} vs {approx}"
);
}
}
assert_eq!(dequantize(&qs[0].0).len(), dims);
}
}