Skip to main content

tensor4all_core/index_key/
mod.rs

1//! Bit-packed integer keys for multi-index maps.
2//!
3//! A [`FlatIndexer`](crate::index_key::FlatIndexer) turns a multi-index over fixed local dimensions into a
4//! single integer key suitable for hashing. Dimension `i` occupies
5//! `ceil(log2(d_i))` bits at a fixed offset, so encoding is shift-and-OR with
6//! no multiplication, and two multi-indices collide only if they are equal.
7//!
8//! Widths up to 512 bits use fixed-width fast paths; wider index spaces fall
9//! back to a limb-backed representation with the same semantics.
10//!
11//! The ladder stops at 512 bits. Since #1224 the 65..=512-bit arms are packed
12//! digit by digit on the stack (see `fixed`) and converted to the arm's type
13//! once, so their encode cost no longer grows with the bignum's digit count;
14//! above 512 bits the key itself would need more inline space than a boxed
15//! arm is worth, so wider index spaces use heap limbs.
16//!
17//! The packers must stay inlined; see `fixed` for why that attribute is
18//! load-bearing.
19
20use thiserror::Error;
21
22mod dynamic;
23mod fixed;
24
25/// Failures from index-key construction and encoding.
26#[derive(Debug, Clone, Copy, PartialEq, Eq, Error)]
27pub enum IndexKeyError {
28    /// A local dimension was zero, so the index space is empty.
29    #[error("local dimension at position {position} is zero")]
30    ZeroDimension {
31        /// Position of the offending dimension.
32        position: usize,
33    },
34    /// A multi-index had the wrong number of components.
35    #[error("expected a multi-index of length {expected}, got {actual}")]
36    LengthMismatch {
37        /// Number of local dimensions the indexer was built with.
38        expected: usize,
39        /// Number of components supplied.
40        actual: usize,
41    },
42    /// A component was not less than its local dimension.
43    #[error("index {value} at position {position} is not below dimension {dim}")]
44    IndexOutOfRange {
45        /// Position of the offending component.
46        position: usize,
47        /// The supplied value.
48        value: usize,
49        /// The local dimension at that position.
50        dim: usize,
51    },
52    /// The requested key width exceeds what this build can represent.
53    #[error("requested key width {requested_bits} bits is too large")]
54    WidthOverflow {
55        /// Total bits requested.
56        requested_bits: u64,
57    },
58}
59
60/// Number of bits needed to represent the values `0..dim`.
61///
62/// # Errors
63///
64/// Returns [`IndexKeyError::ZeroDimension`] when `dim` is zero, since an empty
65/// local space has no representable value.
66///
67/// # Examples
68///
69/// ```
70/// use tensor4all_core::index_key::dimension_bits;
71/// assert_eq!(dimension_bits(1).unwrap(), 0);
72/// assert_eq!(dimension_bits(4).unwrap(), 2);
73/// assert_eq!(dimension_bits(5).unwrap(), 3);
74/// assert!(dimension_bits(0).is_err());
75/// ```
76pub fn dimension_bits(dim: usize) -> Result<u32, IndexKeyError> {
77    match dim {
78        0 => Err(IndexKeyError::ZeroDimension { position: 0 }),
79        1 => Ok(0),
80        _ => Ok(usize::BITS - (dim - 1).leading_zeros()),
81    }
82}
83
84/// Total bit width of the bit-packed key for `local_dims`.
85///
86/// # Errors
87///
88/// Returns [`IndexKeyError::ZeroDimension`] naming the first zero dimension,
89/// and [`IndexKeyError::WidthOverflow`] if the widths do not fit a `u64`.
90///
91/// # Examples
92///
93/// ```
94/// use tensor4all_core::index_key::total_bits;
95/// assert_eq!(total_bits(&[2, 2, 2]).unwrap(), 3);
96/// assert_eq!(total_bits(&[4, 3, 1]).unwrap(), 4);
97/// assert_eq!(total_bits(&[]).unwrap(), 0);
98/// assert!(total_bits(&[2, 0]).is_err());
99/// ```
100pub fn total_bits(local_dims: &[usize]) -> Result<u64, IndexKeyError> {
101    let mut sum = 0u64;
102    for (position, &dim) in local_dims.iter().enumerate() {
103        let bits = dimension_bits(dim).map_err(|_| IndexKeyError::ZeroDimension { position })?;
104        sum = sum
105            .checked_add(u64::from(bits))
106            .ok_or(IndexKeyError::WidthOverflow {
107                requested_bits: u64::MAX,
108            })?;
109    }
110    Ok(sum)
111}
112
113/// The storage arm holding a key's bits.
114///
115/// Private: the arm is an implementation detail chosen from the key's width,
116/// and exposing it would let callers build a key whose declared width and
117/// contents disagree.
118#[derive(Debug, Clone, PartialEq, Eq, Hash)]
119enum Repr {
120    /// Keys up to 64 bits.
121    U64(u64),
122    /// Keys up to 128 bits.
123    U128(u128),
124    /// Keys up to 256 bits.
125    U256(Box<bnum::types::U256>),
126    /// Keys up to 512 bits.
127    U512(Box<bnum::types::U512>),
128    /// Keys wider than 512 bits, as little-endian 64-bit limbs.
129    Limbs(dynamic::Limbs),
130}
131
132/// A bit-packed multi-index key.
133///
134/// A key carries the width it was built for, and the storage arm is a function
135/// of that width, so two keys are equal exactly when they were built for the
136/// same width and hold the same bits. Arms wider than 128 bits are boxed so a
137/// narrow key does not pay the footprint of the widest arm.
138///
139/// The contents are deliberately opaque. A key can only be produced by
140/// [`FlatIndexer::encode`] or [`KeyBuilder::finish`], both of which establish
141/// that its value occupies exactly `width_bits` bits. [`KeyBuilder::push`]
142/// relies on that invariant to place a sub-key without masking or truncation,
143/// and it is not one a caller could be asked to maintain by hand.
144///
145/// # Examples
146///
147/// ```
148/// use tensor4all_core::index_key::FlatIndexer;
149/// let indexer = FlatIndexer::try_new(&[2, 2]).unwrap();
150/// let a = indexer.encode(&[1, 0]).unwrap();
151/// let b = indexer.encode(&[0, 1]).unwrap();
152/// assert_ne!(a, b);
153/// assert_eq!(a, indexer.encode(&[1, 0]).unwrap());
154/// assert_eq!(a.width_bits(), 2);
155/// ```
156#[derive(Debug, Clone, PartialEq, Eq, Hash)]
157pub struct IndexKey {
158    width_bits: u64,
159    repr: Repr,
160}
161
162impl IndexKey {
163    /// The width this key was built for, in bits.
164    ///
165    /// This is what [`KeyBuilder::push`] consumes, so a sub-key can never be
166    /// appended under a width that disagrees with its contents.
167    ///
168    /// # Examples
169    ///
170    /// ```
171    /// use tensor4all_core::index_key::FlatIndexer;
172    /// let indexer = FlatIndexer::try_new(&[3, 4]).unwrap();
173    /// assert_eq!(indexer.width_bits(), 4);
174    /// assert_eq!(indexer.encode(&[2, 3]).unwrap().width_bits(), 4);
175    /// ```
176    pub fn width_bits(&self) -> u64 {
177        self.width_bits
178    }
179
180    /// Returns the heap payload bytes owned by this key, including spare limb capacity.
181    ///
182    /// Inline keys of at most 128 bits own no heap payload. Wider fixed-width
183    /// keys own their boxed storage; limb-backed keys include the allocation's
184    /// full capacity. This excludes the inline [`IndexKey`] value, allocator
185    /// headers, allocator rounding, and any temporary builder storage. Use it
186    /// when accounting for keys retained in a cache or collection.
187    ///
188    /// # Examples
189    ///
190    /// ```
191    /// use tensor4all_core::index_key::FlatIndexer;
192    /// let narrow = FlatIndexer::try_new(&[2, 2]).unwrap().encode(&[1, 0]).unwrap();
193    /// assert_eq!(narrow.owned_heap_bytes(), 0);
194    /// let wide = FlatIndexer::try_new(&[2; 130]).unwrap().encode(&[1; 130]).unwrap();
195    /// assert_eq!(wide.owned_heap_bytes(), 32);
196    /// ```
197    pub fn owned_heap_bytes(&self) -> usize {
198        match &self.repr {
199            Repr::U64(_) | Repr::U128(_) => 0,
200            Repr::U256(value) => std::mem::size_of_val(value.as_ref()),
201            Repr::U512(value) => std::mem::size_of_val(value.as_ref()),
202            Repr::Limbs(value) => dynamic::owned_heap_bytes(value),
203        }
204    }
205
206    /// The storage arm, for tests that pin which arm a width selects.
207    #[cfg(test)]
208    fn repr(&self) -> &Repr {
209        &self.repr
210    }
211
212    /// Builds a key from limbs already known to occupy exactly `width_bits`.
213    ///
214    /// The arm is selected from `width_bits` alone, which is what keeps a
215    /// composed key equal to the same value from [`FlatIndexer::encode`].
216    fn from_limbs(limbs: &dynamic::Limbs, width_bits: u64) -> Self {
217        fn digit(limbs: &[u64], position: usize) -> u64 {
218            limbs.get(position).copied().unwrap_or(0)
219        }
220        fn digits<const N: usize>(limbs: &[u64]) -> [u64; N] {
221            let mut out = [0u64; N];
222            for (position, slot) in out.iter_mut().enumerate() {
223                *slot = digit(limbs, position);
224            }
225            out
226        }
227        let repr = match width_bits {
228            0..=64 => Repr::U64(digit(limbs, 0)),
229            65..=128 => {
230                Repr::U128(u128::from(digit(limbs, 0)) | (u128::from(digit(limbs, 1)) << 64))
231            }
232            129..=256 => Repr::U256(Box::new(bnum::types::U256::from_digits(digits::<4>(limbs)))),
233            257..=512 => Repr::U512(Box::new(bnum::types::U512::from_digits(digits::<8>(limbs)))),
234            _ => {
235                let mut truncated = limbs.clone();
236                truncated.truncate(dynamic::limb_count(width_bits));
237                Repr::Limbs(truncated)
238            }
239        };
240        Self { width_bits, repr }
241    }
242}
243
244/// Encodes multi-indices over fixed local dimensions as [`IndexKey`] values.
245///
246/// Dimension `i` occupies `ceil(log2(d_i))` bits at a fixed offset, so distinct
247/// multi-indices always produce distinct keys.
248///
249/// # Examples
250///
251/// ```
252/// use tensor4all_core::index_key::FlatIndexer;
253/// let indexer = FlatIndexer::try_new(&[3, 4]).unwrap();
254/// assert_eq!(indexer.width_bits(), 4);
255/// assert_eq!(indexer.len(), 2);
256/// assert!(indexer.encode(&[2, 3]).is_ok());
257/// assert!(indexer.encode(&[3, 0]).is_err());
258/// ```
259#[derive(Debug, Clone)]
260pub struct FlatIndexer {
261    dims: Vec<usize>,
262    offsets: Vec<u64>,
263    width_bits: u64,
264    /// Digit layout for the 65..=512-bit arms; empty for every other width.
265    layout: fixed::DigitLayout,
266}
267
268impl FlatIndexer {
269    /// Builds an indexer for `local_dims`.
270    ///
271    /// # Errors
272    ///
273    /// Returns [`IndexKeyError::ZeroDimension`] when any dimension is zero and
274    /// [`IndexKeyError::WidthOverflow`] when the packed width exceeds what this
275    /// build can represent.
276    ///
277    /// # Examples
278    ///
279    /// ```
280    /// use tensor4all_core::index_key::FlatIndexer;
281    /// assert!(FlatIndexer::try_new(&[2, 3, 4]).is_ok());
282    /// assert!(FlatIndexer::try_new(&[2, 0]).is_err());
283    /// ```
284    pub fn try_new(local_dims: &[usize]) -> Result<Self, IndexKeyError> {
285        let mut offsets = Vec::with_capacity(local_dims.len());
286        let mut field_bits = Vec::with_capacity(local_dims.len());
287        let mut width_bits = 0u64;
288        for (position, &dim) in local_dims.iter().enumerate() {
289            let bits =
290                dimension_bits(dim).map_err(|_| IndexKeyError::ZeroDimension { position })?;
291            // A singleton always encodes zero. Use a valid offset even when
292            // it follows the final bit of a fixed-width arm or limb array.
293            offsets.push(if bits == 0 { 0 } else { width_bits });
294            field_bits.push(bits);
295            width_bits =
296                width_bits
297                    .checked_add(u64::from(bits))
298                    .ok_or(IndexKeyError::WidthOverflow {
299                        requested_bits: u64::MAX,
300                    })?;
301        }
302        let layout = if (65..=512).contains(&width_bits) {
303            fixed::DigitLayout::new(&offsets, &field_bits, width_bits)
304        } else {
305            fixed::DigitLayout::default()
306        };
307        Ok(Self {
308            dims: local_dims.to_vec(),
309            offsets,
310            width_bits,
311            layout,
312        })
313    }
314
315    /// Total packed width in bits.
316    pub fn width_bits(&self) -> u64 {
317        self.width_bits
318    }
319
320    /// Number of local dimensions.
321    pub fn len(&self) -> usize {
322        self.dims.len()
323    }
324
325    /// Whether the indexer has no dimensions.
326    pub fn is_empty(&self) -> bool {
327        self.dims.is_empty()
328    }
329
330    /// Encodes a multi-index.
331    ///
332    /// # Errors
333    ///
334    /// Returns [`IndexKeyError::LengthMismatch`] when `idx` has the wrong
335    /// length, and [`IndexKeyError::IndexOutOfRange`] when a component is not
336    /// below its dimension. No input produces a silently wrapped key.
337    ///
338    /// # Examples
339    ///
340    /// ```
341    /// use tensor4all_core::index_key::FlatIndexer;
342    /// let indexer = FlatIndexer::try_new(&[2, 2]).unwrap();
343    /// assert!(indexer.encode(&[1, 1]).is_ok());
344    /// assert!(indexer.encode(&[2, 0]).is_err());
345    /// assert!(indexer.encode(&[0]).is_err());
346    /// ```
347    pub fn encode(&self, idx: &[usize]) -> Result<IndexKey, IndexKeyError> {
348        self.check(idx)?;
349        let repr = match self.width_bits {
350            0..=64 => Repr::U64(fixed::pack_u64(idx, &self.offsets)),
351            65..=128 => {
352                let [low, high] = fixed::pack_digits::<2>(idx, &self.offsets, &self.layout);
353                Repr::U128(u128::from(low) | (u128::from(high) << 64))
354            }
355            129..=256 => Repr::U256(Box::new(bnum::types::U256::from_digits(
356                fixed::pack_digits::<4>(idx, &self.offsets, &self.layout),
357            ))),
358            257..=512 => Repr::U512(Box::new(bnum::types::U512::from_digits(
359                fixed::pack_digits::<8>(idx, &self.offsets, &self.layout),
360            ))),
361            _ => {
362                let mut limbs = dynamic::zeroed(self.width_bits)?;
363                for (&value, &offset) in idx.iter().zip(&self.offsets) {
364                    dynamic::place(&mut limbs, value, offset);
365                }
366                Repr::Limbs(limbs)
367            }
368        };
369        Ok(IndexKey {
370            width_bits: self.width_bits,
371            repr,
372        })
373    }
374
375    /// Validates length and per-dimension bounds before any packing happens.
376    fn check(&self, idx: &[usize]) -> Result<(), IndexKeyError> {
377        if idx.len() != self.dims.len() {
378            return Err(IndexKeyError::LengthMismatch {
379                expected: self.dims.len(),
380                actual: idx.len(),
381            });
382        }
383        // Branch-free scan first: it vectorizes, and valid input is the hot
384        // path. Only a failed scan pays for locating the offending position.
385        let any_out_of_range = idx
386            .iter()
387            .zip(&self.dims)
388            .fold(false, |bad, (&value, &dim)| bad | (value >= dim));
389        if !any_out_of_range {
390            return Ok(());
391        }
392        for (position, (&value, &dim)) in idx.iter().zip(&self.dims).enumerate() {
393            if value >= dim {
394                return Err(IndexKeyError::IndexOutOfRange {
395                    position,
396                    value,
397                    dim,
398                });
399            }
400        }
401        Ok(())
402    }
403}
404
405/// Assembles one key by appending sub-keys at successive bit offsets.
406///
407/// This is the composition operation a tree needs: a node's key is its own
408/// local key followed by each child's key, so
409/// `key(node) = local ++ key(c1) ++ key(c2) ++ ...`. Appending at a known bit
410/// offset costs one pass over the pushed key's limbs, so composing a tree is
411/// linear in total width rather than quadratic as a multiply-based mixed-radix
412/// composition would be.
413///
414/// The result equals what [`FlatIndexer::encode`] produces for the
415/// concatenated multi-index, so a composed key and a directly encoded one are
416/// interchangeable as map keys.
417///
418/// # Examples
419///
420/// ```
421/// use tensor4all_core::index_key::{FlatIndexer, KeyBuilder};
422/// let local = FlatIndexer::try_new(&[3, 2]).unwrap();
423/// let child = FlatIndexer::try_new(&[4]).unwrap();
424/// let whole = FlatIndexer::try_new(&[3, 2, 4]).unwrap();
425///
426/// let mut builder = KeyBuilder::with_capacity_bits(whole.width_bits()).unwrap();
427/// builder.push(&local.encode(&[2, 1]).unwrap()).unwrap();
428/// builder.push(&child.encode(&[3]).unwrap()).unwrap();
429///
430/// assert_eq!(builder.finish(), whole.encode(&[2, 1, 3]).unwrap());
431/// ```
432#[derive(Debug, Clone)]
433pub struct KeyBuilder {
434    limbs: dynamic::Limbs,
435    offset: u64,
436    capacity_bits: u64,
437}
438
439impl KeyBuilder {
440    /// Creates a builder able to hold `width_bits` of appended sub-keys.
441    ///
442    /// # Errors
443    ///
444    /// Returns [`IndexKeyError::WidthOverflow`] when the width cannot be
445    /// allocated on this platform.
446    ///
447    /// # Examples
448    ///
449    /// ```
450    /// use tensor4all_core::index_key::KeyBuilder;
451    /// assert!(KeyBuilder::with_capacity_bits(0).is_ok());
452    /// assert!(KeyBuilder::with_capacity_bits(4096).is_ok());
453    /// ```
454    pub fn with_capacity_bits(width_bits: u64) -> Result<Self, IndexKeyError> {
455        Ok(Self {
456            limbs: dynamic::zeroed(width_bits)?,
457            offset: 0,
458            capacity_bits: width_bits,
459        })
460    }
461
462    /// Total bits appended so far.
463    pub fn width_bits(&self) -> u64 {
464        self.offset
465    }
466
467    /// Appends `key` at the current offset, advancing by the key's own width.
468    ///
469    /// The width comes from the key itself, so a sub-key can never be placed
470    /// under a width that disagrees with its contents -- which would overwrite
471    /// the following field and silently break injectivity.
472    ///
473    /// # Errors
474    ///
475    /// Returns [`IndexKeyError::WidthOverflow`] when the append would exceed
476    /// the declared capacity, rather than truncating the key.
477    ///
478    /// # Examples
479    ///
480    /// ```
481    /// use tensor4all_core::index_key::{FlatIndexer, KeyBuilder};
482    /// let indexer = FlatIndexer::try_new(&[2, 2]).unwrap();
483    /// let key = indexer.encode(&[1, 1]).unwrap();
484    /// let mut builder = KeyBuilder::with_capacity_bits(2).unwrap();
485    /// assert!(builder.push(&key).is_ok());
486    /// assert!(builder.push(&key).is_err());
487    /// ```
488    pub fn push(&mut self, key: &IndexKey) -> Result<(), IndexKeyError> {
489        let key_width_bits = key.width_bits;
490        let end = self
491            .offset
492            .checked_add(key_width_bits)
493            .ok_or(IndexKeyError::WidthOverflow {
494                requested_bits: u64::MAX,
495            })?;
496        if end > self.capacity_bits {
497            return Err(IndexKeyError::WidthOverflow {
498                requested_bits: end,
499            });
500        }
501        let offset = self.offset;
502        match &key.repr {
503            Repr::U64(value) => {
504                dynamic::place_limbs(&mut self.limbs, &[*value], key_width_bits, offset);
505            }
506            Repr::U128(value) => {
507                let source = [*value as u64, (*value >> 64) as u64];
508                dynamic::place_limbs(&mut self.limbs, &source, key_width_bits, offset);
509            }
510            Repr::U256(value) => {
511                dynamic::place_limbs(&mut self.limbs, value.digits(), key_width_bits, offset);
512            }
513            Repr::U512(value) => {
514                dynamic::place_limbs(&mut self.limbs, value.digits(), key_width_bits, offset);
515            }
516            Repr::Limbs(value) => {
517                dynamic::place_limbs(&mut self.limbs, value, key_width_bits, offset);
518            }
519        }
520        self.offset = end;
521        Ok(())
522    }
523
524    /// Produces the key for the bits actually appended.
525    ///
526    /// The arm is selected from the appended width, not from the declared
527    /// capacity, so a composed key equals the same value from
528    /// [`FlatIndexer::encode`] even when the builder was given more capacity
529    /// than it ended up using.
530    ///
531    /// # Examples
532    ///
533    /// ```
534    /// use tensor4all_core::index_key::{FlatIndexer, KeyBuilder};
535    /// let indexer = FlatIndexer::try_new(&[2, 2]).unwrap();
536    /// let key = indexer.encode(&[1, 0]).unwrap();
537    ///
538    /// // Over-declared capacity does not change the composed key.
539    /// let mut tight = KeyBuilder::with_capacity_bits(2).unwrap();
540    /// tight.push(&key).unwrap();
541    /// let mut loose = KeyBuilder::with_capacity_bits(600).unwrap();
542    /// loose.push(&key).unwrap();
543    /// let composed = tight.finish();
544    /// assert_eq!(composed, loose.finish());
545    /// assert_eq!(composed, key);
546    ///
547    /// let empty = KeyBuilder::with_capacity_bits(8).unwrap();
548    /// assert_eq!(empty.finish().width_bits(), 0);
549    /// ```
550    pub fn finish(self) -> IndexKey {
551        IndexKey::from_limbs(&self.limbs, self.offset)
552    }
553}
554
555#[cfg(test)]
556mod tests;