summa_core/structures/postings/
horizontal_bp128.rs

1//! Bitpacking utilities for compact integer encoding
2//!
3//! Implements SIMD-friendly bitpacking for posting list compression.
4//! Uses PForDelta-style encoding with exceptions for outliers.
5//!
6//! Optimizations:
7//! - SIMD-accelerated unpacking (when available)
8//! - Hillis-Steele parallel prefix sum for delta decoding
9//! - Binary search within decoded blocks
10//! - Variable block sizes based on posting list length
11
12use crate::structures::simd;
13use byteorder::{LittleEndian, ReadBytesExt, WriteBytesExt};
14use std::io::{self, Read, Write};
15
16/// Block size for bitpacking (128 integers per block for SIMD alignment)
17pub const HORIZONTAL_BP128_BLOCK_SIZE: usize = 128;
18
19/// Small block size for short posting lists (better cache locality)
20pub const SMALL_BLOCK_SIZE: usize = 32;
21
22/// Threshold for using small blocks (posting lists shorter than this use small blocks)
23pub const SMALL_BLOCK_THRESHOLD: usize = 256;
24
25/// Pack a block of 128 u32 values using the specified bit width
26pub fn pack_block(
27    values: &[u32; HORIZONTAL_BP128_BLOCK_SIZE],
28    bit_width: u8,
29    output: &mut Vec<u8>,
30) {
31    pack_block_n(values, bit_width, output);
32}
33
34/// Pack `values` at `width` bits each (little-endian bit order) into `out`.
35/// This is the one little-endian bit packer; every value must fit `width`.
36pub(super) fn pack_block_n(values: &[u32], width: u8, out: &mut Vec<u8>) {
37    debug_assert!(width <= 32, "bit width exceeds u32");
38    debug_assert!(
39        width == 32 || values.iter().all(|&v| v >> width == 0),
40        "value exceeds the packed width"
41    );
42    if width == 0 || values.is_empty() {
43        return;
44    }
45    if width == 32 {
46        for &v in values {
47            out.extend_from_slice(&v.to_le_bytes());
48        }
49        return;
50    }
51    let start = out.len();
52    out.resize(start + (values.len() * width as usize).div_ceil(8), 0);
53    let dst = &mut out[start..];
54    let mut bit_pos = 0usize;
55    for &v in values {
56        let mut acc = (v as u64) << (bit_pos & 7);
57        let mut byte = bit_pos >> 3;
58        let mut remaining = (bit_pos & 7) + width as usize;
59        while remaining > 0 {
60            dst[byte] |= acc as u8;
61            acc >>= 8;
62            byte += 1;
63            remaining = remaining.saturating_sub(8);
64        }
65        bit_pos += width as usize;
66    }
67}
68
69/// Unpack a block of 128 u32 values without requiring trailing padding.
70///
71/// Panics if the width exceeds 32 or the encoded input is truncated.
72pub fn unpack_block(input: &[u8], bit_width: u8, output: &mut [u32; HORIZONTAL_BP128_BLOCK_SIZE]) {
73    unpack_block_n(input, bit_width, output, HORIZONTAL_BP128_BLOCK_SIZE);
74}
75
76/// Unpack `n` horizontally packed integers, without reading outside `input`.
77/// Byte-aligned widths reuse SIMD widening; other widths use bounded word
78/// loads with a scalar tail. Shared by packed postings and patched low bits.
79///
80/// Panics if the width exceeds 32 or the input/output extents are too short.
81#[inline]
82pub fn unpack_block_n(input: &[u8], bit_width: u8, output: &mut [u32], n: usize) {
83    assert!(bit_width <= 32, "bit width exceeds u32");
84    let output = &mut output[..n];
85    let bytes = n
86        .checked_mul(usize::from(bit_width))
87        .expect("packed input length overflows usize")
88        .div_ceil(8);
89    let input = &input[..bytes];
90    match bit_width {
91        0 => output.fill(0),
92        8 => simd::unpack_8bit(input, output, n),
93        16 => simd::unpack_16bit(input, output, n),
94        32 => simd::unpack_32bit(input, output, n),
95        _ => {
96            let mask = (1u64 << bit_width) - 1;
97            let mut bit_pos = 0usize;
98            for slot in output {
99                let byte = bit_pos >> 3;
100                let word = if byte + 8 <= input.len() {
101                    u64::from_le_bytes(input[byte..byte + 8].try_into().unwrap())
102                } else {
103                    let mut word = 0u64;
104                    for (i, &b) in input[byte..].iter().enumerate() {
105                        word |= (b as u64) << (i * 8);
106                    }
107                    word
108                };
109                *slot = ((word >> (bit_pos & 7)) & mask) as u32;
110                bit_pos += usize::from(bit_width);
111            }
112        }
113    }
114}
115
116/// Binary search within a decoded block to find first element >= target
117/// Returns the index within the block, or block.len() if not found
118#[inline]
119pub fn binary_search_block(block: &[u32], target: u32) -> usize {
120    match block.binary_search(&target) {
121        Ok(idx) => idx,
122        Err(idx) => idx,
123    }
124}
125
126/// Bitpacked block with skip info for block-max pruning
127#[derive(Debug, Clone)]
128pub struct HorizontalBP128Block {
129    /// Delta-encoded doc_ids (bitpacked)
130    pub doc_deltas: Vec<u8>,
131    /// Bit width for doc deltas
132    pub doc_bit_width: u8,
133    /// Term frequencies (bitpacked)
134    pub term_freqs: Vec<u8>,
135    /// Bit width for term frequencies
136    pub tf_bit_width: u8,
137    /// First doc_id in this block (absolute)
138    pub first_doc_id: u32,
139    /// Last doc_id in this block (absolute)
140    pub last_doc_id: u32,
141    /// Number of docs in this block
142    pub num_docs: u16,
143    /// Maximum term frequency in this block (for BM25F upper bound calculation)
144    pub max_tf: u32,
145    /// Maximum impact score in this block (for MaxScore pruning)
146    /// This is computed using BM25F with conservative length normalization
147    pub max_block_score: f32,
148}
149
150impl HorizontalBP128Block {
151    /// Serialize the block
152    pub fn serialize<W: Write>(&self, writer: &mut W) -> io::Result<()> {
153        writer.write_u32::<LittleEndian>(self.first_doc_id)?;
154        writer.write_u32::<LittleEndian>(self.last_doc_id)?;
155        writer.write_u16::<LittleEndian>(self.num_docs)?;
156        writer.write_u8(self.doc_bit_width)?;
157        writer.write_u8(self.tf_bit_width)?;
158        writer.write_u32::<LittleEndian>(self.max_tf)?;
159        writer.write_f32::<LittleEndian>(self.max_block_score)?;
160
161        // Write doc deltas
162        writer.write_u16::<LittleEndian>(self.doc_deltas.len() as u16)?;
163        writer.write_all(&self.doc_deltas)?;
164
165        // Write term freqs
166        writer.write_u16::<LittleEndian>(self.term_freqs.len() as u16)?;
167        writer.write_all(&self.term_freqs)?;
168
169        Ok(())
170    }
171
172    /// Deserialize a block
173    pub fn deserialize<R: Read>(reader: &mut R) -> io::Result<Self> {
174        let first_doc_id = reader.read_u32::<LittleEndian>()?;
175        let last_doc_id = reader.read_u32::<LittleEndian>()?;
176        let num_docs = reader.read_u16::<LittleEndian>()?;
177        let doc_bit_width = reader.read_u8()?;
178        let tf_bit_width = reader.read_u8()?;
179        let max_tf = reader.read_u32::<LittleEndian>()?;
180        let max_block_score = reader.read_f32::<LittleEndian>()?;
181
182        let doc_deltas_len = reader.read_u16::<LittleEndian>()? as usize;
183        let mut doc_deltas = vec![0u8; doc_deltas_len];
184        reader.read_exact(&mut doc_deltas)?;
185
186        let term_freqs_len = reader.read_u16::<LittleEndian>()? as usize;
187        let mut term_freqs = vec![0u8; term_freqs_len];
188        reader.read_exact(&mut term_freqs)?;
189
190        Ok(Self {
191            doc_deltas,
192            doc_bit_width,
193            term_freqs,
194            tf_bit_width,
195            first_doc_id,
196            last_doc_id,
197            num_docs,
198            max_tf,
199            max_block_score,
200        })
201    }
202
203    /// Decode doc_ids from this block
204    pub fn decode_doc_ids(&self) -> Vec<u32> {
205        let mut output = vec![0u32; self.num_docs as usize];
206        self.decode_doc_ids_into(&mut output);
207        output
208    }
209
210    /// Decode doc_ids into a pre-allocated buffer (avoids allocation)
211    #[inline]
212    pub fn decode_doc_ids_into(&self, output: &mut [u32]) -> usize {
213        let count = self.num_docs as usize;
214        if count == 0 {
215            return 0;
216        }
217
218        // Fused unpack + delta decode - no intermediate buffer needed
219        simd::unpack_delta_decode(
220            &self.doc_deltas,
221            self.doc_bit_width,
222            output,
223            self.first_doc_id,
224            count,
225        );
226
227        count
228    }
229
230    /// Decode term frequencies from this block
231    pub fn decode_term_freqs(&self) -> Vec<u32> {
232        let mut output = vec![0u32; self.num_docs as usize];
233        self.decode_term_freqs_into(&mut output);
234        output
235    }
236
237    /// Decode term frequencies into a pre-allocated buffer (avoids allocation)
238    #[inline]
239    pub fn decode_term_freqs_into(&self, output: &mut [u32]) -> usize {
240        let count = self.num_docs as usize;
241        if count == 0 {
242            return 0;
243        }
244
245        // Use slice-based unpack to avoid temp buffer copy
246        unpack_block_n(&self.term_freqs, self.tf_bit_width, output, count);
247
248        // TF is stored as tf-1, so add 1 back
249        simd::add_one(output, count);
250
251        count
252    }
253}
254
255/// Bitpacked posting list with block-level skip info
256#[derive(Debug, Clone)]
257pub struct HorizontalBP128PostingList {
258    /// Blocks of postings
259    pub blocks: Vec<HorizontalBP128Block>,
260    /// Total document count
261    pub doc_count: u32,
262    /// Maximum score across all blocks (for MaxScore pruning)
263    pub max_score: f32,
264}
265
266impl HorizontalBP128PostingList {
267    /// Create from raw doc_ids and term frequencies
268    pub fn from_postings(doc_ids: &[u32], term_freqs: &[u32], idf: f32) -> Self {
269        assert_eq!(doc_ids.len(), term_freqs.len());
270
271        if doc_ids.is_empty() {
272            return Self {
273                blocks: Vec::new(),
274                doc_count: 0,
275                max_score: 0.0,
276            };
277        }
278
279        let mut blocks = Vec::new();
280        let mut max_score = 0.0f32;
281        let mut i = 0;
282
283        while i < doc_ids.len() {
284            let block_end = (i + HORIZONTAL_BP128_BLOCK_SIZE).min(doc_ids.len());
285            let block_docs = &doc_ids[i..block_end];
286            let block_tfs = &term_freqs[i..block_end];
287
288            let block = Self::create_block(block_docs, block_tfs, idf);
289            max_score = max_score.max(block.max_block_score);
290            blocks.push(block);
291
292            i = block_end;
293        }
294
295        Self {
296            blocks,
297            doc_count: doc_ids.len() as u32,
298            max_score,
299        }
300    }
301
302    fn create_block(doc_ids: &[u32], term_freqs: &[u32], idf: f32) -> HorizontalBP128Block {
303        use crate::query::bm25_upper_bound;
304
305        let num_docs = doc_ids.len();
306        let first_doc_id = doc_ids[0];
307        let last_doc_id = *doc_ids.last().unwrap();
308
309        // Compute deltas (delta - 1 to save one bit since deltas are always >= 1)
310        let mut deltas = [0u32; HORIZONTAL_BP128_BLOCK_SIZE];
311        let mut max_delta = 0u32;
312        for j in 1..num_docs {
313            let delta = doc_ids[j] - doc_ids[j - 1] - 1;
314            deltas[j - 1] = delta;
315            max_delta = max_delta.max(delta);
316        }
317
318        // Compute max TF and prepare TF array (store tf-1)
319        let mut tfs = [0u32; HORIZONTAL_BP128_BLOCK_SIZE];
320        let mut max_tf = 0u32;
321
322        for (j, &tf) in term_freqs.iter().enumerate() {
323            tfs[j] = tf - 1; // Store tf-1
324            max_tf = max_tf.max(tf);
325        }
326
327        // BM25 upper bound score using conservative length normalization
328        let max_block_score = bm25_upper_bound(max_tf as f32, idf);
329
330        let doc_bit_width = simd::bits_needed(max_delta);
331        let tf_bit_width = simd::bits_needed(max_tf.saturating_sub(1)); // Store tf-1
332
333        let mut doc_deltas = Vec::new();
334        pack_block(&deltas, doc_bit_width, &mut doc_deltas);
335
336        let mut term_freqs_packed = Vec::new();
337        pack_block(&tfs, tf_bit_width, &mut term_freqs_packed);
338
339        HorizontalBP128Block {
340            doc_deltas,
341            doc_bit_width,
342            term_freqs: term_freqs_packed,
343            tf_bit_width,
344            first_doc_id,
345            last_doc_id,
346            num_docs: num_docs as u16,
347            max_tf,
348            max_block_score,
349        }
350    }
351
352    /// Serialize the posting list
353    pub fn serialize<W: Write>(&self, writer: &mut W) -> io::Result<()> {
354        writer.write_u32::<LittleEndian>(self.doc_count)?;
355        writer.write_f32::<LittleEndian>(self.max_score)?;
356        writer.write_u32::<LittleEndian>(self.blocks.len() as u32)?;
357
358        for block in &self.blocks {
359            block.serialize(writer)?;
360        }
361
362        Ok(())
363    }
364
365    /// Deserialize a posting list
366    pub fn deserialize<R: Read>(reader: &mut R) -> io::Result<Self> {
367        let doc_count = reader.read_u32::<LittleEndian>()?;
368        let max_score = reader.read_f32::<LittleEndian>()?;
369        let num_blocks = reader.read_u32::<LittleEndian>()? as usize;
370
371        let mut blocks = Vec::with_capacity(num_blocks);
372        for _ in 0..num_blocks {
373            blocks.push(HorizontalBP128Block::deserialize(reader)?);
374        }
375
376        Ok(Self {
377            blocks,
378            doc_count,
379            max_score,
380        })
381    }
382
383    /// Create an iterator
384    pub fn iterator(&self) -> HorizontalBP128Iterator<'_> {
385        HorizontalBP128Iterator::new(self)
386    }
387}
388
389/// Iterator over bitpacked posting list with block skipping support
390pub struct HorizontalBP128Iterator<'a> {
391    posting_list: &'a HorizontalBP128PostingList,
392    /// Current block index
393    current_block: usize,
394    /// Number of valid elements in current block
395    current_block_len: usize,
396    /// Pre-allocated buffer for decoded doc_ids (avoids allocation per block)
397    block_doc_ids: Vec<u32>,
398    /// Pre-allocated buffer for decoded term freqs
399    block_term_freqs: Vec<u32>,
400    /// Position within current block
401    pos_in_block: usize,
402    /// Whether we've exhausted all postings
403    exhausted: bool,
404}
405
406impl<'a> HorizontalBP128Iterator<'a> {
407    pub fn new(posting_list: &'a HorizontalBP128PostingList) -> Self {
408        // Pre-allocate buffers to block size to avoid allocations during iteration
409        let mut iter = Self {
410            posting_list,
411            current_block: 0,
412            current_block_len: 0,
413            block_doc_ids: vec![0u32; HORIZONTAL_BP128_BLOCK_SIZE],
414            block_term_freqs: vec![0u32; HORIZONTAL_BP128_BLOCK_SIZE],
415            pos_in_block: 0,
416            exhausted: posting_list.blocks.is_empty(),
417        };
418
419        if !iter.exhausted {
420            iter.decode_current_block();
421        }
422
423        iter
424    }
425
426    #[inline]
427    fn decode_current_block(&mut self) {
428        let block = &self.posting_list.blocks[self.current_block];
429        // Decode into pre-allocated buffers (no allocation!)
430        self.current_block_len = block.decode_doc_ids_into(&mut self.block_doc_ids);
431        block.decode_term_freqs_into(&mut self.block_term_freqs);
432        self.pos_in_block = 0;
433    }
434
435    /// Current document ID
436    #[inline]
437    pub fn doc(&self) -> u32 {
438        if self.exhausted {
439            u32::MAX
440        } else {
441            self.block_doc_ids[self.pos_in_block]
442        }
443    }
444
445    /// Current term frequency
446    #[inline]
447    pub fn term_freq(&self) -> u32 {
448        if self.exhausted {
449            0
450        } else {
451            self.block_term_freqs[self.pos_in_block]
452        }
453    }
454
455    /// Advance to next document
456    #[inline]
457    pub fn advance(&mut self) -> u32 {
458        if self.exhausted {
459            return u32::MAX;
460        }
461
462        self.pos_in_block += 1;
463
464        if self.pos_in_block >= self.current_block_len {
465            self.current_block += 1;
466            if self.current_block >= self.posting_list.blocks.len() {
467                self.exhausted = true;
468                return u32::MAX;
469            }
470            self.decode_current_block();
471        }
472
473        self.doc()
474    }
475
476    /// Seek to first doc >= target (with block skipping and binary search)
477    pub fn seek(&mut self, target: u32) -> u32 {
478        if self.exhausted {
479            return u32::MAX;
480        }
481
482        // Binary search to find the right block
483        let block_idx = self.posting_list.blocks[self.current_block..].binary_search_by(|block| {
484            if block.last_doc_id < target {
485                std::cmp::Ordering::Less
486            } else if block.first_doc_id > target {
487                std::cmp::Ordering::Greater
488            } else {
489                std::cmp::Ordering::Equal
490            }
491        });
492
493        let target_block = match block_idx {
494            Ok(idx) => self.current_block + idx,
495            Err(idx) => {
496                if self.current_block + idx >= self.posting_list.blocks.len() {
497                    self.exhausted = true;
498                    return u32::MAX;
499                }
500                self.current_block + idx
501            }
502        };
503
504        // Move to target block if different
505        if target_block != self.current_block {
506            self.current_block = target_block;
507            self.decode_current_block();
508        } else if self.current_block_len == 0 {
509            self.decode_current_block();
510        }
511
512        // Binary search within the block
513        let pos = binary_search_block(
514            &self.block_doc_ids[self.pos_in_block..self.current_block_len],
515            target,
516        );
517        self.pos_in_block += pos;
518
519        if self.pos_in_block >= self.current_block_len {
520            // Target not in this block, move to next
521            self.current_block += 1;
522            if self.current_block >= self.posting_list.blocks.len() {
523                self.exhausted = true;
524                return u32::MAX;
525            }
526            self.decode_current_block();
527        }
528
529        self.doc()
530    }
531
532    /// Get max score for remaining blocks (for MaxScore optimization)
533    pub fn max_remaining_score(&self) -> f32 {
534        if self.exhausted {
535            return 0.0;
536        }
537
538        self.posting_list.blocks[self.current_block..]
539            .iter()
540            .map(|b| b.max_block_score)
541            .fold(0.0f32, |a, b| a.max(b))
542    }
543
544    /// Skip to next block (for block-max pruning)
545    pub fn skip_to_block_with_doc(&mut self, target: u32) -> Option<(u32, f32)> {
546        while self.current_block < self.posting_list.blocks.len() {
547            let block = &self.posting_list.blocks[self.current_block];
548            if block.last_doc_id >= target {
549                return Some((block.first_doc_id, block.max_block_score));
550            }
551            self.current_block += 1;
552        }
553        self.exhausted = true;
554        None
555    }
556
557    /// Get current block's max score
558    pub fn current_block_max_score(&self) -> f32 {
559        if self.exhausted {
560            0.0
561        } else {
562            self.posting_list.blocks[self.current_block].max_block_score
563        }
564    }
565
566    /// Get current block's max term frequency (for BM25F upper bound recalculation)
567    pub fn current_block_max_tf(&self) -> u32 {
568        if self.exhausted {
569            0
570        } else {
571            self.posting_list.blocks[self.current_block].max_tf
572        }
573    }
574}
575
576#[cfg(test)]
577mod tests {
578    use super::*;
579
580    #[cfg(all(unix, feature = "native"))]
581    #[test]
582    fn exact_width_unpack_never_reads_past_the_encoded_slice() {
583        const CHILD: &str = "SUMMA_CODEC_GUARD_CHILD";
584        const COMPLETE: &str = "guard-page decode verified";
585        if std::env::var_os(CHILD).is_none() {
586            let child = std::process::Command::new(std::env::current_exe().unwrap())
587                .args([
588                    "--exact",
589                    "structures::postings::horizontal_bp128::tests::exact_width_unpack_never_reads_past_the_encoded_slice",
590                    "--nocapture",
591                    "--test-threads=1",
592                ])
593                .env(CHILD, "1")
594                .output()
595                .unwrap();
596            assert!(
597                child.status.success(),
598                "exact-width decoder crossed the protected boundary: {}\n{}\n{}",
599                child.status,
600                String::from_utf8_lossy(&child.stdout),
601                String::from_utf8_lossy(&child.stderr)
602            );
603            assert!(String::from_utf8_lossy(&child.stdout).contains(COMPLETE));
604            return;
605        }
606        // Isolate a potential SIGBUS/SIGSEGV in the child test process.
607        let page = unsafe { libc::sysconf(libc::_SC_PAGESIZE) };
608        assert!(page >= 512);
609        let page = page as usize;
610        let mapping = unsafe {
611            libc::mmap(
612                std::ptr::null_mut(),
613                page * 2,
614                libc::PROT_READ | libc::PROT_WRITE,
615                libc::MAP_PRIVATE | libc::MAP_ANON,
616                -1,
617                0,
618            )
619        };
620        assert_ne!(mapping, libc::MAP_FAILED);
621        struct Mapping(*mut libc::c_void, usize);
622        impl Drop for Mapping {
623            fn drop(&mut self) {
624                unsafe {
625                    libc::munmap(self.0, self.1);
626                }
627            }
628        }
629        let _mapping = Mapping(mapping, page * 2);
630        let boundary = unsafe { mapping.cast::<u8>().add(page) };
631        assert_eq!(
632            unsafe { libc::mprotect(boundary.cast(), page, libc::PROT_NONE) },
633            0
634        );
635        for width in 0..=32u8 {
636            let mask = if width == 32 {
637                u32::MAX
638            } else {
639                (1u32 << width) - 1
640            };
641            let values = std::array::from_fn(|i| {
642                if width == 0 {
643                    0
644                } else {
645                    (i as u32).wrapping_mul(2_654_435_761) & mask
646                }
647            });
648            let mut packed = Vec::new();
649            pack_block(&values, width, &mut packed);
650            // Independent bit-at-a-time oracle for the persisted layout.
651            let mut expected_bytes = vec![0u8; (values.len() * usize::from(width)).div_ceil(8)];
652            for (i, &value) in values.iter().enumerate() {
653                for bit in 0..usize::from(width) {
654                    let at = i * usize::from(width) + bit;
655                    expected_bytes[at / 8] |= (((value >> bit) & 1) as u8) << (at % 8);
656                }
657            }
658            assert_eq!(packed, expected_bytes);
659            for count in 0..=HORIZONTAL_BP128_BLOCK_SIZE {
660                let len = (count * usize::from(width)).div_ceil(8);
661                let start = unsafe { boundary.sub(len) };
662                unsafe {
663                    std::ptr::copy_nonoverlapping(packed.as_ptr(), start, len);
664                }
665                let input = unsafe { std::slice::from_raw_parts(start, len) };
666                let mut decoded = vec![0xDEADBEEF; count + 4];
667                unpack_block_n(input, width, &mut decoded[..count], count);
668                assert_eq!(
669                    &decoded[..count],
670                    &values[..count],
671                    "width={width} count={count}"
672                );
673                assert_eq!(&decoded[count..], &[0xDEADBEEF; 4]);
674                if count == HORIZONTAL_BP128_BLOCK_SIZE {
675                    let mut full = [0; HORIZONTAL_BP128_BLOCK_SIZE];
676                    unpack_block(input, width, &mut full);
677                    assert_eq!(full, values);
678                }
679            }
680        }
681        println!("{COMPLETE}");
682    }
683
684    #[test]
685    fn test_bits_needed() {
686        assert_eq!(simd::bits_needed(0), 0);
687        assert_eq!(simd::bits_needed(1), 1);
688        assert_eq!(simd::bits_needed(2), 2);
689        assert_eq!(simd::bits_needed(3), 2);
690        assert_eq!(simd::bits_needed(255), 8);
691        assert_eq!(simd::bits_needed(256), 9);
692    }
693
694    #[test]
695    fn test_pack_unpack() {
696        let mut values = [0u32; HORIZONTAL_BP128_BLOCK_SIZE];
697        for (i, value) in values.iter_mut().enumerate() {
698            *value = (i * 3) as u32;
699        }
700
701        let max_val = values.iter().max().copied().unwrap();
702        let bit_width = simd::bits_needed(max_val);
703
704        let mut packed = Vec::new();
705        pack_block(&values, bit_width, &mut packed);
706
707        let mut unpacked = [0u32; HORIZONTAL_BP128_BLOCK_SIZE];
708        unpack_block(&packed, bit_width, &mut unpacked);
709
710        assert_eq!(values, unpacked);
711    }
712
713    #[test]
714    fn test_bitpacked_posting_list() {
715        let doc_ids: Vec<u32> = (0..200).map(|i| i * 2).collect();
716        let term_freqs: Vec<u32> = (0..200).map(|i| (i % 10) + 1).collect();
717
718        let posting_list = HorizontalBP128PostingList::from_postings(&doc_ids, &term_freqs, 1.0);
719
720        assert_eq!(posting_list.doc_count, 200);
721        assert_eq!(posting_list.blocks.len(), 2); // 128 + 72
722
723        // Test iteration
724        let mut iter = posting_list.iterator();
725        for (i, &expected_doc) in doc_ids.iter().enumerate() {
726            assert_eq!(iter.doc(), expected_doc, "Mismatch at position {}", i);
727            assert_eq!(iter.term_freq(), term_freqs[i]);
728            if i < doc_ids.len() - 1 {
729                iter.advance();
730            }
731        }
732    }
733
734    #[test]
735    fn test_bitpacked_seek() {
736        let doc_ids: Vec<u32> = vec![10, 20, 30, 100, 200, 300, 1000, 2000];
737        let term_freqs: Vec<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8];
738
739        let posting_list = HorizontalBP128PostingList::from_postings(&doc_ids, &term_freqs, 1.0);
740        let mut iter = posting_list.iterator();
741
742        assert_eq!(iter.seek(25), 30);
743        assert_eq!(iter.seek(100), 100);
744        assert_eq!(iter.seek(500), 1000);
745        assert_eq!(iter.seek(3000), u32::MAX);
746    }
747
748    #[test]
749    fn test_serialization() {
750        let doc_ids: Vec<u32> = (0..50).map(|i| i * 3).collect();
751        let term_freqs: Vec<u32> = (0..50).map(|_| 1).collect();
752
753        let posting_list = HorizontalBP128PostingList::from_postings(&doc_ids, &term_freqs, 1.5);
754
755        let mut buffer = Vec::new();
756        posting_list.serialize(&mut buffer).unwrap();
757
758        let restored = HorizontalBP128PostingList::deserialize(&mut &buffer[..]).unwrap();
759
760        assert_eq!(restored.doc_count, posting_list.doc_count);
761        assert_eq!(restored.blocks.len(), posting_list.blocks.len());
762
763        // Verify iteration produces same results
764        let mut iter1 = posting_list.iterator();
765        let mut iter2 = restored.iterator();
766
767        while iter1.doc() != u32::MAX {
768            assert_eq!(iter1.doc(), iter2.doc());
769            assert_eq!(iter1.term_freq(), iter2.term_freq());
770            iter1.advance();
771            iter2.advance();
772        }
773    }
774
775    #[test]
776    fn test_simd_delta_decode() {
777        // Test simd::delta_decode
778        let deltas2 = [0u32; 16]; // gaps of 1 (stored as 0)
779        let mut output2 = [0u32; 16];
780        simd::delta_decode(&mut output2, &deltas2, 100, 8);
781        // first_doc_id=100, then +1 each
782        assert_eq!(&output2[..8], &[100, 101, 102, 103, 104, 105, 106, 107]);
783
784        // Test with varying deltas (stored as gap-1)
785        // gaps: 2, 1, 3, 1, 5, 1, 1 → stored as: 1, 0, 2, 0, 4, 0, 0
786        let deltas3 = [1u32, 0, 2, 0, 4, 0, 0, 0];
787        let mut output3 = [0u32; 8];
788        simd::delta_decode(&mut output3, &deltas3, 10, 8);
789        // 10, 10+2=12, 12+1=13, 13+3=16, 16+1=17, 17+5=22, 22+1=23, 23+1=24
790        assert_eq!(&output3[..8], &[10, 12, 13, 16, 17, 22, 23, 24]);
791    }
792
793    #[test]
794    fn test_delta_decode_large_block() {
795        // Test with a full 128-element block
796        let doc_ids: Vec<u32> = (0..128).map(|i| i * 5 + 100).collect();
797        let term_freqs: Vec<u32> = vec![1; 128];
798
799        let posting_list = HorizontalBP128PostingList::from_postings(&doc_ids, &term_freqs, 1.0);
800        let decoded = posting_list.blocks[0].decode_doc_ids();
801
802        assert_eq!(decoded.len(), 128);
803        for (i, (&expected, &actual)) in doc_ids.iter().zip(decoded.iter()).enumerate() {
804            assert_eq!(expected, actual, "Mismatch at position {}", i);
805        }
806    }
807}
summa_core/structures/postings/horizontal_bp128.rs

summa_core/structures/postings/
horizontal_bp128.rs
