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;