#[cfg(feature = "parallel")]
use rayon::prelude::*;
#[cfg(test)]
#[inline(always)]
fn u8_dot_u32(a: &[u8], b: &[u8]) -> u32 {
assert_eq!(a.len(), b.len(), "u8_dot_u32 inputs must have equal length");
#[cfg(target_arch = "aarch64")]
{
use std::arch::aarch64::*;
let n = a.len();
let chunks = n / 16;
let rem = n % 16;
let mut acc0: uint32x4_t;
let mut acc1: uint32x4_t;
let mut acc2: uint32x4_t;
let mut acc3: uint32x4_t;
unsafe {
acc0 = vdupq_n_u32(0);
acc1 = vdupq_n_u32(0);
acc2 = vdupq_n_u32(0);
acc3 = vdupq_n_u32(0);
for i in 0..chunks {
let ap = a.as_ptr().add(i * 16);
let bp = b.as_ptr().add(i * 16);
let va = vld1q_u8(ap);
let vb = vld1q_u8(bp);
let lo_u16 = vmull_u8(vget_low_u8(va), vget_low_u8(vb));
let hi_u16 = vmull_high_u8(va, vb);
acc0 = vaddq_u32(acc0, vmovl_u16(vget_low_u16(lo_u16)));
acc1 = vaddq_u32(acc1, vmovl_high_u16(lo_u16));
acc2 = vaddq_u32(acc2, vmovl_u16(vget_low_u16(hi_u16)));
acc3 = vaddq_u32(acc3, vmovl_high_u16(hi_u16));
}
let sum4 = vaddq_u32(vaddq_u32(acc0, acc1), vaddq_u32(acc2, acc3));
let mut total = vaddvq_u32(sum4);
for i in (n - rem)..n {
total += a[i] as u32 * b[i] as u32;
}
total
}
}
#[cfg(not(target_arch = "aarch64"))]
{
a.chunks(8)
.zip(b.chunks(8))
.map(|(ac, bc)| {
ac.iter()
.zip(bc.iter())
.map(|(&x, &y)| (x as u32) * (y as u32))
.sum::<u32>()
})
.sum()
}
}
#[inline(always)]
pub fn u8_l2sq_u32(a: &[u8], b: &[u8]) -> u32 {
assert_eq!(
a.len(),
b.len(),
"u8_l2sq_u32 inputs must have equal length"
);
#[cfg(target_arch = "aarch64")]
{
use std::arch::aarch64::*;
let n = a.len();
let chunks = n / 16;
let rem = n % 16;
let mut acc0: uint32x4_t;
let mut acc1: uint32x4_t;
let mut acc2: uint32x4_t;
let mut acc3: uint32x4_t;
unsafe {
acc0 = vdupq_n_u32(0);
acc1 = vdupq_n_u32(0);
acc2 = vdupq_n_u32(0);
acc3 = vdupq_n_u32(0);
for i in 0..chunks {
let ap = a.as_ptr().add(i * 16);
let bp = b.as_ptr().add(i * 16);
let va = vld1q_u8(ap);
let vb = vld1q_u8(bp);
let diff = vabdq_u8(va, vb);
let lo_u16 = vmull_u8(vget_low_u8(diff), vget_low_u8(diff));
let hi_u16 = vmull_high_u8(diff, diff);
acc0 = vaddq_u32(acc0, vmovl_u16(vget_low_u16(lo_u16)));
acc1 = vaddq_u32(acc1, vmovl_high_u16(lo_u16));
acc2 = vaddq_u32(acc2, vmovl_u16(vget_low_u16(hi_u16)));
acc3 = vaddq_u32(acc3, vmovl_high_u16(hi_u16));
}
let sum4 = vaddq_u32(vaddq_u32(acc0, acc1), vaddq_u32(acc2, acc3));
let mut total = vaddvq_u32(sum4);
for i in (n - rem)..n {
let d = (a[i] as i32) - (b[i] as i32);
total += (d * d) as u32;
}
total
}
}
#[cfg(not(target_arch = "aarch64"))]
{
a.chunks(8)
.zip(b.chunks(8))
.map(|(ac, bc)| {
ac.iter()
.zip(bc.iter())
.map(|(&x, &y)| {
let d = (x as i32) - (y as i32);
(d * d) as u32
})
.sum::<u32>()
})
.sum()
}
}
#[derive(Debug, Clone, PartialEq)]
pub enum QuantError {
EmptyCorpus,
ZeroDims,
FlatLengthNotDivisible { len: usize, dims: usize },
RaggedRow {
row: usize,
expected: usize,
got: usize,
},
EncodeLengthMismatch { expected: usize, got: usize },
}
impl std::fmt::Display for QuantError {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::EmptyCorpus => write!(f, "cannot train on empty corpus"),
Self::ZeroDims => write!(f, "dims must be > 0"),
Self::FlatLengthNotDivisible { len, dims } => write!(
f,
"flat vector length {len} is not a multiple of dims {dims}"
),
Self::RaggedRow { row, expected, got } => write!(
f,
"row {row} has length {got}, expected {expected} (dims fixed by row 0)"
),
Self::EncodeLengthMismatch { expected, got } => write!(
f,
"vector length {got} does not match codec dims {expected}"
),
}
}
}
impl std::error::Error for QuantError {}
fn flat_min_max(vectors: &[f32], dims: usize) -> Result<(Vec<f32>, Vec<f32>), QuantError> {
if dims == 0 {
return Err(QuantError::ZeroDims);
}
if vectors.is_empty() {
return Err(QuantError::EmptyCorpus);
}
if !vectors.len().is_multiple_of(dims) {
return Err(QuantError::FlatLengthNotDivisible {
len: vectors.len(),
dims,
});
}
let n = vectors.len() / dims;
let mut min = vec![f32::INFINITY; dims];
let mut max = vec![f32::NEG_INFINITY; dims];
for row in 0..n {
let v = &vectors[row * dims..(row + 1) * dims];
for (d, &x) in v.iter().enumerate() {
if x.is_finite() {
if x < min[d] {
min[d] = x;
}
if x > max[d] {
max[d] = x;
}
}
}
}
finalize_min_max(&mut min, &mut max);
Ok((min, max))
}
fn row_min_max(vectors: &[Vec<f32>]) -> Result<(usize, Vec<f32>, Vec<f32>), QuantError> {
if vectors.is_empty() {
return Err(QuantError::EmptyCorpus);
}
let dims = vectors[0].len();
if dims == 0 {
return Err(QuantError::ZeroDims);
}
let mut min = vec![f32::INFINITY; dims];
let mut max = vec![f32::NEG_INFINITY; dims];
for (row, v) in vectors.iter().enumerate() {
if v.len() != dims {
return Err(QuantError::RaggedRow {
row,
expected: dims,
got: v.len(),
});
}
for (d, &x) in v.iter().enumerate() {
if x.is_finite() {
if x < min[d] {
min[d] = x;
}
if x > max[d] {
max[d] = x;
}
}
}
}
finalize_min_max(&mut min, &mut max);
Ok((dims, min, max))
}
fn finalize_min_max(min: &mut [f32], max: &mut [f32]) {
for d in 0..min.len() {
if !min[d].is_finite() {
min[d] = 0.0;
}
if !max[d].is_finite() || max[d] <= min[d] {
max[d] = min[d] + 1.0;
}
}
}
#[derive(Debug, Clone)]
pub struct Sq8Codec {
pub min: Vec<f32>,
pub scale: Vec<f32>,
pub scale_sq: Vec<f32>,
pub scale_sq_f64: Vec<f64>,
pub mean_scale_sq: f32,
pub scale_sq_residual: Vec<f32>,
pub offset_sq_sum: f32,
pub offset_sq_sum_f64: f64,
}
#[derive(Debug, Clone)]
pub struct EncodedVector {
pub codes: Vec<u8>,
pub norm: f32,
pub soc_sum: f32,
pub soc_sum_f64: f64,
pub residual_dot_bias: f32,
}
impl Sq8Codec {
fn build_from_min_max(min: Vec<f32>, max: Vec<f32>) -> Self {
let dims = min.len();
let scale: Vec<f32> = (0..dims).map(|d| (max[d] - min[d]) / 255.0).collect();
let scale_sq: Vec<f32> = scale.iter().map(|s| s * s).collect();
let scale_sq_f64: Vec<f64> = scale.iter().map(|&s| f64::from(s) * f64::from(s)).collect();
let mean_scale_sq = scale_sq.iter().sum::<f32>() / dims as f32;
let scale_sq_residual: Vec<f32> = scale_sq.iter().map(|&ss| ss - mean_scale_sq).collect();
let offset_sq_sum: f32 = min.iter().map(|o| o * o).sum();
let offset_sq_sum_f64: f64 = min.iter().map(|&o| f64::from(o) * f64::from(o)).sum();
Self {
min,
scale,
scale_sq,
scale_sq_f64,
mean_scale_sq,
scale_sq_residual,
offset_sq_sum,
offset_sq_sum_f64,
}
}
pub fn train_flat(vectors: &[f32], dims: usize) -> Self {
Self::try_train_flat(vectors, dims).unwrap_or_else(|e| panic!("{e}"))
}
pub fn try_train_flat(vectors: &[f32], dims: usize) -> Result<Self, QuantError> {
let (min, max) = flat_min_max(vectors, dims)?;
Ok(Self::build_from_min_max(min, max))
}
pub fn train(vectors: &[Vec<f32>]) -> Self {
Self::try_train(vectors).unwrap_or_else(|e| panic!("{e}"))
}
pub fn try_train(vectors: &[Vec<f32>]) -> Result<Self, QuantError> {
let (_dims, min, max) = row_min_max(vectors)?;
Ok(Self::build_from_min_max(min, max))
}
pub fn encode(&self, v: &[f32]) -> EncodedVector {
self.try_encode(v).unwrap_or_else(|e| panic!("{e}"))
}
pub fn try_encode(&self, v: &[f32]) -> Result<EncodedVector, QuantError> {
let dims = self.min.len();
if v.len() != dims {
return Err(QuantError::EncodeLengthMismatch {
expected: dims,
got: v.len(),
});
}
Ok(self.encode_unchecked(v))
}
fn encode_unchecked(&self, v: &[f32]) -> EncodedVector {
let dims = self.min.len();
let mut codes = Vec::with_capacity(dims);
let mut soc_sum = 0.0f32;
let mut soc_sum_f64 = 0.0f64;
let mut residual_dot_bias = 0.0f32;
let norm = v.iter().map(|x| x * x).sum::<f32>().sqrt();
for (d, &x) in v.iter().enumerate() {
let s = self.scale[d];
let inv_s = if s > 1e-12 { 1.0 / s } else { 0.0 };
let raw = (x - self.min[d]) * inv_s;
let code = raw.round().clamp(0.0, 255.0) as u8;
codes.push(code);
soc_sum += s * self.min[d] * code as f32;
soc_sum_f64 += f64::from(s) * f64::from(self.min[d]) * f64::from(code);
residual_dot_bias += self.scale_sq_residual[d] * code as f32;
}
EncodedVector {
codes,
norm,
soc_sum,
soc_sum_f64,
residual_dot_bias,
}
}
pub fn encode_flat_par(&self, vectors: &[f32], dims: usize) -> Vec<EncodedVector> {
self.try_encode_flat_par(vectors, dims)
.unwrap_or_else(|e| panic!("{e}"))
}
pub fn try_encode_flat_par(
&self,
vectors: &[f32],
dims: usize,
) -> Result<Vec<EncodedVector>, QuantError> {
if dims == 0 {
return Err(QuantError::ZeroDims);
}
if !vectors.len().is_multiple_of(dims) {
return Err(QuantError::FlatLengthNotDivisible {
len: vectors.len(),
dims,
});
}
if dims != self.min.len() {
return Err(QuantError::EncodeLengthMismatch {
expected: self.min.len(),
got: dims,
});
}
let n = vectors.len() / dims;
#[cfg(feature = "parallel")]
let encoded = (0..n)
.into_par_iter()
.map(|i| self.encode_unchecked(&vectors[i * dims..(i + 1) * dims]))
.collect();
#[cfg(not(feature = "parallel"))]
let encoded = (0..n)
.map(|i| self.encode_unchecked(&vectors[i * dims..(i + 1) * dims]))
.collect();
Ok(encoded)
}
pub fn encode_par(&self, vectors: &[Vec<f32>]) -> Vec<EncodedVector> {
self.try_encode_par(vectors)
.unwrap_or_else(|e| panic!("{e}"))
}
pub fn try_encode_par(&self, vectors: &[Vec<f32>]) -> Result<Vec<EncodedVector>, QuantError> {
let dims = self.min.len();
for v in vectors {
if v.len() != dims {
return Err(QuantError::EncodeLengthMismatch {
expected: dims,
got: v.len(),
});
}
}
#[cfg(feature = "parallel")]
let encoded = vectors
.par_iter()
.map(|v| self.encode_unchecked(v))
.collect();
#[cfg(not(feature = "parallel"))]
let encoded = vectors.iter().map(|v| self.encode_unchecked(v)).collect();
Ok(encoded)
}
#[inline]
pub fn approx_dot(&self, a: &EncodedVector, b: &EncodedVector) -> f32 {
let dims = self.scale_sq.len();
assert_eq!(
a.codes.len(),
dims,
"approx_dot input codes must match codec dims"
);
assert_eq!(
b.codes.len(),
dims,
"approx_dot input codes must match codec dims"
);
let dot: f64 = self
.scale
.iter()
.zip(self.min.iter())
.zip(a.codes.iter())
.zip(b.codes.iter())
.map(|(((&scale, &min), &ac), &bc)| {
let scale = f64::from(scale);
let min = f64::from(min);
let a_value = scale.mul_add(f64::from(ac), min);
let b_value = scale.mul_add(f64::from(bc), min);
a_value * b_value
})
.sum();
dot as f32
}
#[inline]
pub fn approx_cosine_dist(&self, a: &EncodedVector, b: &EncodedVector) -> f32 {
let denom = a.norm * b.norm;
if !denom.is_finite() || denom <= 0.0 {
return 1.0;
}
let dot = self.approx_dot(a, b);
let cosine = (dot / denom).clamp(-1.0, 1.0);
1.0 - cosine
}
#[inline]
pub fn approx_l2_sq(&self, a: &EncodedVector, b: &EncodedVector) -> f32 {
let dims = self.scale_sq.len();
assert_eq!(
a.codes.len(),
dims,
"approx_l2_sq input codes must match codec dims"
);
assert_eq!(
b.codes.len(),
dims,
"approx_l2_sq input codes must match codec dims"
);
let weighted: f64 = self
.scale_sq
.iter()
.zip(a.codes.iter())
.zip(b.codes.iter())
.map(|((&weight, &ac), &bc)| {
let delta = f64::from(ac) - f64::from(bc);
f64::from(weight) * delta * delta
})
.sum();
weighted as f32
}
pub fn dims(&self) -> usize {
self.min.len()
}
}
#[derive(Debug, Clone)]
pub struct GsSq8Codec {
pub min: Vec<f32>,
pub gs: f32,
pub gs_sq: f32,
pub anisotropy_ratio: f32,
}
#[derive(Debug, Clone)]
pub struct GsEncodedVector {
pub codes: Vec<u8>,
}
impl GsSq8Codec {
fn build_from_min_max(min: Vec<f32>, max: Vec<f32>) -> Self {
let dims = min.len();
let ranges: Vec<f32> = (0..dims).map(|d| max[d] - min[d]).collect();
let max_range = ranges.iter().cloned().fold(0.0f32, f32::max);
let gs = if max_range > 1e-12 {
max_range / 255.0
} else {
1.0 / 255.0
};
let min_range_nonzero = ranges
.iter()
.cloned()
.filter(|&r| r > 1e-12)
.fold(f32::INFINITY, f32::min);
let anisotropy_ratio = if min_range_nonzero.is_finite() && min_range_nonzero > 0.0 {
max_range / min_range_nonzero
} else {
1.0
};
Self {
min,
gs,
gs_sq: gs * gs,
anisotropy_ratio,
}
}
pub fn train_flat(vectors: &[f32], dims: usize) -> Self {
Self::try_train_flat(vectors, dims).unwrap_or_else(|e| panic!("{e}"))
}
pub fn try_train_flat(vectors: &[f32], dims: usize) -> Result<Self, QuantError> {
let (min, max) = flat_min_max(vectors, dims)?;
Ok(Self::build_from_min_max(min, max))
}
pub fn train(vectors: &[Vec<f32>]) -> Self {
Self::try_train(vectors).unwrap_or_else(|e| panic!("{e}"))
}
pub fn try_train(vectors: &[Vec<f32>]) -> Result<Self, QuantError> {
let (_dims, min, max) = row_min_max(vectors)?;
Ok(Self::build_from_min_max(min, max))
}
#[inline]
pub fn encode(&self, v: &[f32]) -> GsEncodedVector {
self.try_encode(v).unwrap_or_else(|e| panic!("{e}"))
}
pub fn try_encode(&self, v: &[f32]) -> Result<GsEncodedVector, QuantError> {
let dims = self.min.len();
if v.len() != dims {
return Err(QuantError::EncodeLengthMismatch {
expected: dims,
got: v.len(),
});
}
Ok(self.encode_unchecked(v))
}
#[inline]
fn encode_unchecked(&self, v: &[f32]) -> GsEncodedVector {
let inv_gs = if self.gs > 1e-12 { 1.0 / self.gs } else { 0.0 };
let codes = v
.iter()
.enumerate()
.map(|(d, &x)| ((x - self.min[d]) * inv_gs).round().clamp(0.0, 255.0) as u8)
.collect();
GsEncodedVector { codes }
}
pub fn encode_flat_par(&self, vectors: &[f32], dims: usize) -> Vec<GsEncodedVector> {
self.try_encode_flat_par(vectors, dims)
.unwrap_or_else(|e| panic!("{e}"))
}
pub fn try_encode_flat_par(
&self,
vectors: &[f32],
dims: usize,
) -> Result<Vec<GsEncodedVector>, QuantError> {
if dims == 0 {
return Err(QuantError::ZeroDims);
}
if !vectors.len().is_multiple_of(dims) {
return Err(QuantError::FlatLengthNotDivisible {
len: vectors.len(),
dims,
});
}
if dims != self.min.len() {
return Err(QuantError::EncodeLengthMismatch {
expected: self.min.len(),
got: dims,
});
}
let n = vectors.len() / dims;
#[cfg(feature = "parallel")]
let encoded = (0..n)
.into_par_iter()
.map(|i| self.encode_unchecked(&vectors[i * dims..(i + 1) * dims]))
.collect();
#[cfg(not(feature = "parallel"))]
let encoded = (0..n)
.map(|i| self.encode_unchecked(&vectors[i * dims..(i + 1) * dims]))
.collect();
Ok(encoded)
}
#[inline]
pub fn l2_sq(&self, a: &GsEncodedVector, b: &GsEncodedVector) -> f32 {
self.gs_sq * u8_l2sq_u32(&a.codes, &b.codes) as f32
}
#[inline]
pub fn l2_sq_codes(&self, a: &[u8], b: &[u8]) -> f32 {
self.gs_sq * u8_l2sq_u32(a, b) as f32
}
pub fn dims(&self) -> usize {
self.min.len()
}
#[inline]
pub fn is_in_distribution(&self, v: &[f32]) -> bool {
let max_code = 255.0 * self.gs;
v.iter()
.zip(self.min.iter())
.all(|(&x, &mn)| x >= mn && x <= mn + max_code)
}
}
#[cfg(test)]
#[path = "codec_tests.rs"]
mod tests;