Skip to main content

littlebit_core/
packer.rs

1//! LSB-first 32-bit binary matrix packing, unpacking, and compact 1-bit matmul.
2
3use candle_core::{DType, Device, Tensor};
4use rayon::prelude::*;
5
6use crate::binary::binarize_sign_no_grad;
7use crate::error::{LittleBitError, Result};
8
9/// Row-major 1-bit packed matrix with values in `{-1, +1}`.
10///
11/// Bit encoding follows upstream `quantization/utils/binary_packer.py` (`lsb_first`):
12/// - `+1` maps to bit `0`
13/// - `-1` maps to bit `1`
14/// - Rows are padded on the right to multiples of 32 with `+1` (bit `0`)
15/// - Each 32-bit chunk is stored as a signed `i32` word (LSB = lowest column index)
16#[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    /// Construct from pre-packed row-major 32-bit words after validating dimensions.
26    ///
27    /// # Errors
28    /// Returns [`LittleBitError::InvalidShape`] when `data.len() != rows * cols.div_ceil(32)`.
29    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    /// Number of rows in the original unpacked matrix.
47    #[must_use]
48    pub fn rows(&self) -> usize {
49        self.rows
50    }
51
52    /// Number of columns in the original unpacked matrix.
53    #[must_use]
54    pub fn cols(&self) -> usize {
55        self.cols
56    }
57
58    /// Number of `i32` words stored per row (`cols.div_ceil(32)`).
59    #[must_use]
60    pub fn words_per_row(&self) -> usize {
61        self.words_per_row
62    }
63
64    /// Borrow the underlying row-major `i32` word buffer.
65    #[must_use]
66    pub fn words(&self) -> &[i32] {
67        &self.data
68    }
69
70    /// Heap memory footprint in bytes of the packed word storage.
71    #[must_use]
72    pub fn memory_bytes(&self) -> usize {
73        self.data.len() * std::mem::size_of::<i32>()
74    }
75
76    /// Unpack back to row-major `Vec<i8>` containing only `-1` and `+1`.
77    #[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    /// Compute `Y = X @ W^T` where `X` is `(batch_rows, cols)` in row-major `f32`
92    /// and `W` (`self`) is `(rows, cols)` packed at 1 bit per weight.
93    ///
94    /// Returns a row-major `Vec<f32>` of shape `(batch_rows, rows)` without unpacking `W`.
95    ///
96    /// # Errors
97    /// Returns [`LittleBitError::InvalidShape`] when `x.len() != batch_rows * self.cols`.
98    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    /// Convert packed storage into `(packed_i32, shape_i64)` tensors matching upstream safetensors.
154    ///
155    /// # Errors
156    /// Returns an error if tensor creation fails.
157    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
164/// Pack a row-major `i8` matrix containing only `-1` and `+1` into [`PackedBinaryMatrix`].
165///
166/// # Errors
167/// Returns [`LittleBitError::InvalidShape`] when `values.len() != rows * cols`, or
168/// [`LittleBitError::InvalidBinaryValue`] if any element is not `-1` or `+1`.
169pub 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
211/// Unpack a raw slice of row-major 32-bit words back to `{-1, +1}` `Vec<i8>`.
212///
213/// # Errors
214/// Returns [`LittleBitError::InvalidShape`] if `words.len() != rows * cols.div_ceil(32)`.
215pub 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
220/// Binarize a 2D Candle tensor (`>= 0 => +1`, `< 0 => -1`) and pack it into
221/// `(packed_i32, shape_i64)` tensors matching upstream `binary_packer`.
222///
223/// # Errors
224/// Returns an error if `tensor` is not 2D or cannot be converted to host values.
225pub 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
248/// Unpack a 2D `I32` packed Candle tensor back into a `{-1, +1}` tensor of `target_dtype` on `device`.
249///
250/// Matches upstream `binary_unpacker`.
251///
252/// # Errors
253/// Returns an error if `packed` is not a 2D `I32` tensor matching `(rows, cols.div_ceil(32))`.
254pub 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        // 32 ones -> 0i32
297        let ones = vec![1i8; 32];
298        assert_eq!(pack_i8_slice(&ones, 1, 32)?.words(), &[0i32]);
299
300        // 32 minus-ones -> all bits set -> -1i32
301        let neg_ones = vec![-1i8; 32];
302        assert_eq!(pack_i8_slice(&neg_ones, 1, 32)?.words(), &[-1i32]);
303
304        // Single -1 at bit 31 -> 0x8000_0000_u32 as i32 == i32::MIN
305        let mut bit31 = vec![1i8; 32];
306        bit31[31] = -1;
307        assert_eq!(pack_i8_slice(&bit31, 1, 32)?.words(), &[i32::MIN]);
308
309        // Alternating +1 (even idx -> bit 0) and -1 (odd idx -> bit 1) => 0xAAAA_AAAA
310        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}