1use candle_core::{DType, Device, Tensor};
4use rayon::prelude::*;
5
6use crate::binary::binarize_sign_no_grad;
7use crate::error::{LittleBitError, Result};
8
9#[derive(Debug, Clone, PartialEq, Eq)]
17pub struct PackedBinaryMatrix {
18 rows: usize,
19 cols: usize,
20 words_per_row: usize,
21 data: Vec<i32>,
22}
23
24impl PackedBinaryMatrix {
25 pub fn from_words(rows: usize, cols: usize, data: Vec<i32>) -> Result<Self> {
30 let words_per_row = cols.div_ceil(32);
31 let expected_len = rows.saturating_mul(words_per_row);
32 if data.len() != expected_len {
33 return Err(LittleBitError::InvalidShape {
34 expected: format!("{rows}x{words_per_row} ({expected_len} words)"),
35 actual: format!("{} words", data.len()),
36 });
37 }
38 Ok(Self {
39 rows,
40 cols,
41 words_per_row,
42 data,
43 })
44 }
45
46 #[must_use]
48 pub fn rows(&self) -> usize {
49 self.rows
50 }
51
52 #[must_use]
54 pub fn cols(&self) -> usize {
55 self.cols
56 }
57
58 #[must_use]
60 pub fn words_per_row(&self) -> usize {
61 self.words_per_row
62 }
63
64 #[must_use]
66 pub fn words(&self) -> &[i32] {
67 &self.data
68 }
69
70 #[must_use]
72 pub fn memory_bytes(&self) -> usize {
73 self.data.len() * std::mem::size_of::<i32>()
74 }
75
76 #[must_use]
78 pub fn unpack_to_i8(&self) -> Vec<i8> {
79 let mut out = Vec::with_capacity(self.rows * self.cols);
80 for row in 0..self.rows {
81 let row_words = &self.data[row * self.words_per_row..(row + 1) * self.words_per_row];
82 for col in 0..self.cols {
83 let word = row_words[col / 32] as u32;
84 let bit = (word >> (col % 32)) & 1;
85 out.push(if bit == 0 { 1 } else { -1 });
86 }
87 }
88 out
89 }
90
91 pub fn matmul_transposed_f32(&self, x: &[f32], batch_rows: usize) -> Result<Vec<f32>> {
99 let expected_len = batch_rows.saturating_mul(self.cols);
100 if x.len() != expected_len {
101 return Err(LittleBitError::InvalidShape {
102 expected: format!("{batch_rows}x{} ({expected_len} elements)", self.cols),
103 actual: format!("{} elements", x.len()),
104 });
105 }
106 if batch_rows == 0 || self.rows == 0 {
107 return Ok(vec![0.0; batch_rows * self.rows]);
108 }
109
110 let mut output = vec![0.0f32; batch_rows * self.rows];
111 let cols = self.cols;
112 let words_per_row = self.words_per_row;
113 let words = &self.data;
114
115 for (b, out_row) in output.chunks_exact_mut(self.rows).enumerate() {
116 let x_row = &x[b * cols..(b + 1) * cols];
117 let x_total: f64 = x_row.iter().map(|&v| f64::from(v)).sum();
118
119 let compute_row = |w_row_idx: usize| -> f32 {
120 let w_words = &words[w_row_idx * words_per_row..(w_row_idx + 1) * words_per_row];
121 let mut neg_sum = 0.0_f64;
122 for (w_idx, &word_i32) in w_words.iter().enumerate() {
123 let mut w = word_i32 as u32;
124 let col_base = w_idx * 32;
125 let valid_cols = (cols - col_base).min(32);
126 if valid_cols < 32 {
127 w &= (1u32 << valid_cols) - 1;
128 }
129 let x_chunk = &x_row[col_base..col_base + valid_cols];
130 while w != 0 {
131 let bit = w.trailing_zeros() as usize;
132 neg_sum += f64::from(x_chunk[bit]);
133 w &= w - 1;
134 }
135 }
136 (x_total - 2.0 * neg_sum) as f32
137 };
138
139 if self.rows >= 64 {
140 out_row.par_iter_mut().enumerate().for_each(|(r, dst)| {
141 *dst = compute_row(r);
142 });
143 } else {
144 for (r, dst) in out_row.iter_mut().enumerate() {
145 *dst = compute_row(r);
146 }
147 }
148 }
149
150 Ok(output)
151 }
152
153 pub fn to_tensors(&self, device: &Device) -> Result<(Tensor, Tensor)> {
158 let packed = Tensor::from_slice(&self.data, (self.rows, self.words_per_row), device)?;
159 let shape = Tensor::from_slice(&[self.rows as i64, self.cols as i64], 2, device)?;
160 Ok((packed, shape))
161 }
162}
163
164pub fn pack_i8_slice(values: &[i8], rows: usize, cols: usize) -> Result<PackedBinaryMatrix> {
170 let expected = rows.saturating_mul(cols);
171 if values.len() != expected {
172 return Err(LittleBitError::InvalidShape {
173 expected: format!("{rows}x{cols} ({expected} elements)"),
174 actual: format!("{} elements", values.len()),
175 });
176 }
177
178 let words_per_row = cols.div_ceil(32);
179 let mut data = vec![0i32; rows * words_per_row];
180
181 for row in 0..rows {
182 let row_in = &values[row * cols..(row + 1) * cols];
183 let row_out = &mut data[row * words_per_row..(row + 1) * words_per_row];
184 for (col, &val) in row_in.iter().enumerate() {
185 match val {
186 1 => {}
187 -1 => {
188 let word_idx = col / 32;
189 let bit_idx = col % 32;
190 row_out[word_idx] = ((row_out[word_idx] as u32) | (1u32 << bit_idx)) as i32;
191 }
192 other => {
193 return Err(LittleBitError::InvalidBinaryValue {
194 row,
195 col,
196 value: other,
197 });
198 }
199 }
200 }
201 }
202
203 Ok(PackedBinaryMatrix {
204 rows,
205 cols,
206 words_per_row,
207 data,
208 })
209}
210
211pub fn unpack_i32_slice(words: &[i32], rows: usize, cols: usize) -> Result<Vec<i8>> {
216 let mat = PackedBinaryMatrix::from_words(rows, cols, words.to_vec())?;
217 Ok(mat.unpack_to_i8())
218}
219
220pub fn binary_packer(tensor: &Tensor) -> Result<(Tensor, Tensor)> {
226 let dims = tensor.dims();
227 if dims.len() != 2 {
228 return Err(LittleBitError::InvalidShape {
229 expected: "2D tensor".to_string(),
230 actual: format!("{dims:?}"),
231 });
232 }
233 let (rows, cols) = (dims[0], dims[1]);
234 let bin = binarize_sign_no_grad(&tensor.to_dtype(DType::F32)?)?;
235 let host = bin.to_device(&Device::Cpu)?.to_vec2::<f32>()?;
236
237 let mut i8_buf = Vec::with_capacity(rows * cols);
238 for row_vals in host {
239 for v in row_vals {
240 i8_buf.push(if v < 0.0 { -1i8 } else { 1i8 });
241 }
242 }
243
244 let packed = pack_i8_slice(&i8_buf, rows, cols)?;
245 packed.to_tensors(tensor.device())
246}
247
248pub fn binary_unpacker(
255 packed: &Tensor,
256 original_shape: (usize, usize),
257 target_dtype: DType,
258 device: &Device,
259) -> Result<Tensor> {
260 if packed.dtype() != DType::I32 {
261 return Err(LittleBitError::UnsupportedDtype(format!(
262 "expected I32 packed tensor, got {:?}",
263 packed.dtype()
264 )));
265 }
266 let dims = packed.dims();
267 let (rows, cols) = original_shape;
268 let words_per_row = cols.div_ceil(32);
269 if dims != [rows, words_per_row] {
270 return Err(LittleBitError::InvalidShape {
271 expected: format!("[{rows}, {words_per_row}]"),
272 actual: format!("{dims:?}"),
273 });
274 }
275
276 let words = packed
277 .to_device(&Device::Cpu)?
278 .reshape(rows * words_per_row)?
279 .to_vec1::<i32>()?;
280 let i8_vals = unpack_i32_slice(&words, rows, cols)?;
281 let f32_vals: Vec<f32> = i8_vals.into_iter().map(f32::from).collect();
282 let t = Tensor::from_vec(f32_vals, (rows, cols), device)?;
283 if target_dtype == DType::F32 {
284 Ok(t)
285 } else {
286 Ok(t.to_dtype(target_dtype)?)
287 }
288}
289
290#[cfg(test)]
291mod tests {
292 use super::*;
293
294 #[test]
295 fn exact_bit_patterns_match_upstream_lsb_first() -> Result<()> {
296 let ones = vec![1i8; 32];
298 assert_eq!(pack_i8_slice(&ones, 1, 32)?.words(), &[0i32]);
299
300 let neg_ones = vec![-1i8; 32];
302 assert_eq!(pack_i8_slice(&neg_ones, 1, 32)?.words(), &[-1i32]);
303
304 let mut bit31 = vec![1i8; 32];
306 bit31[31] = -1;
307 assert_eq!(pack_i8_slice(&bit31, 1, 32)?.words(), &[i32::MIN]);
308
309 let alt: Vec<i8> = (0..32).map(|i| if i % 2 == 0 { 1 } else { -1 }).collect();
311 assert_eq!(
312 pack_i8_slice(&alt, 1, 32)?.words(),
313 &[0xAAAA_AAAA_u32 as i32]
314 );
315 Ok(())
316 }
317
318 #[test]
319 fn round_trip_across_edge_widths() -> Result<()> {
320 for cols in [1usize, 7, 8, 31, 32, 33, 63, 64, 65, 100] {
321 let rows = 5;
322 let vals: Vec<i8> = (0..rows * cols)
323 .map(|k| if (k * 7 + 3) % 3 == 0 { -1 } else { 1 })
324 .collect();
325 let packed = pack_i8_slice(&vals, rows, cols)?;
326 assert_eq!(packed.unpack_to_i8(), vals, "width={cols}");
327 }
328 Ok(())
329 }
330
331 #[test]
332 fn rejects_non_binary_values() {
333 let err = pack_i8_slice(&[1, -1, 0, 1], 2, 2).expect_err("zero must fail");
334 assert!(matches!(
335 err,
336 LittleBitError::InvalidBinaryValue {
337 row: 1,
338 col: 0,
339 value: 0
340 }
341 ));
342 }
343
344 #[test]
345 fn packed_matmul_matches_dense_matmul_exactly() -> Result<()> {
346 let rows = 71;
347 let cols = 100;
348 let batch = 4;
349 let w_i8: Vec<i8> = (0..rows * cols)
350 .map(|k| if (k * 13 + 5) % 5 < 2 { -1 } else { 1 })
351 .collect();
352 let packed = pack_i8_slice(&w_i8, rows, cols)?;
353
354 let x: Vec<f32> = (0..batch * cols)
355 .map(|k| ((k % 19) as f32 - 9.0) * 0.13)
356 .collect();
357 let got = packed.matmul_transposed_f32(&x, batch)?;
358
359 let dev = Device::Cpu;
360 let x_t = Tensor::from_slice(&x, (batch, cols), &dev)?;
361 let w_f32: Vec<f32> = w_i8.iter().map(|&v| f32::from(v)).collect();
362 let w_t = Tensor::from_slice(&w_f32, (rows, cols), &dev)?;
363 let want = x_t.matmul(&w_t.t()?)?.flatten_all()?.to_vec1::<f32>()?;
364
365 for (i, (&g, &w)) in got.iter().zip(want.iter()).enumerate() {
366 assert!((g - w).abs() < 1e-4, "idx {i}: got {g}, want {w}");
367 }
368 Ok(())
369 }
370}