Skip to main content

lance_bitpacking/
lib.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright The Lance Authors
3
4// NOTICE:
5// This file is a modification of the `fastlanes` crate: https://github.com/spiraldb/fastlanes
6// It is modified to allow a rust stable build
7//
8// The original code can be accessed at
9//      https://github.com/spiraldb/fastlanes/blob/8e0ff374f815d919d0c0ebdccf5ffd9e6dc7d663/src/bitpacking.rs
10//      https://github.com/spiraldb/fastlanes/blob/8e0ff374f815d919d0c0ebdccf5ffd9e6dc7d663/src/lib.rs
11//      https://github.com/spiraldb/fastlanes/blob/8e0ff374f815d919d0c0ebdccf5ffd9e6dc7d663/src/macros.rs
12//
13// The original code is licensed under the Apache Software License:
14// https://github.com/spiraldb/fastlanes/blob/8e0ff374f815d919d0c0ebdccf5ffd9e6dc7d663/LICENSE
15
16use arrayref::{array_mut_ref, array_ref};
17use core::mem::size_of;
18
19mod bitpacker_internal;
20
21pub use bitpacker_internal::{BitPacker, BitPacker4x, BitPacker8x};
22
23pub const FL_ORDER: [usize; 8] = [0, 4, 2, 6, 1, 5, 3, 7];
24
25pub trait FastLanes: Sized + Copy {
26    const T: usize = size_of::<Self>() * 8;
27    const LANES: usize = 1024 / Self::T;
28}
29
30// Implement the trait for basic unsigned integer types
31impl FastLanes for u8 {}
32impl FastLanes for u16 {}
33impl FastLanes for u32 {}
34impl FastLanes for u64 {}
35
36macro_rules! pack {
37    ($T:ty, $W:expr, $packed:expr, $lane:expr, | $_1:tt $idx:ident | $($body:tt)*) => {
38        macro_rules! __kernel__ {( $_1 $idx:ident ) => ( $($body)* )}
39        {
40            use paste::paste;
41
42            // The number of bits of T.
43            const T: usize = <$T>::T;
44
45            #[inline(always)]
46            fn index(row: usize, lane: usize) -> usize {
47                let o = row / 8;
48                let s = row % 8;
49                (FL_ORDER[o] * 16) + (s * 128) + lane
50            }
51
52            if $W == 0 {
53                // Nothing to do if W is 0, since the packed array is zero bytes.
54            } else if $W == T {
55                // Special case for W=T, we can just copy the input value directly to the packed value.
56                paste!(seq_t!(row in $T {
57                    let idx = index(row, $lane);
58                    $packed[<$T>::LANES * row + $lane] = __kernel__!(idx);
59                }));
60            } else {
61                // A mask of W bits.
62                let mask: $T = (1 << $W) - 1;
63
64                // First we loop over each lane in the virtual 1024 bit word.
65                let mut tmp: $T = 0;
66
67                // Loop over each of the rows of the lane.
68                // Inlining this loop means all branches are known at compile time and
69                // the code is auto-vectorized for SIMD execution.
70                paste!(seq_t!(row in $T {
71                    let idx = index(row, $lane);
72                    let src = __kernel__!(idx);
73                    let src = src & mask;
74
75                    // Shift the src bits into their position in the tmp output variable.
76                    if row == 0 {
77                        tmp = src;
78                    } else {
79                        tmp |= src << (row * $W) % T;
80                    }
81
82                    // If the next packed position is after our current one, then we have filled
83                    // the current output and we can write the packed value.
84                    let curr_word: usize = (row * $W) / T;
85                    let next_word: usize = ((row + 1) * $W) / T;
86
87                    #[allow(unused_assignments)]
88                    if next_word > curr_word {
89                        $packed[<$T>::LANES * curr_word + $lane] = tmp;
90                        let remaining_bits: usize = ((row + 1) * $W) % T;
91                        // Keep the remaining bits for the next packed value.
92                        tmp = src >> $W - remaining_bits;
93                    }
94                }));
95            }
96        }
97    };
98}
99
100macro_rules! unpack {
101    ($T:ty, $W:expr, $packed:expr, $lane:expr, | $_1:tt $idx:ident, $_2:tt $elem:ident | $($body:tt)*) => {
102        macro_rules! __kernel__ {( $_1 $idx:ident, $_2 $elem:ident ) => ( $($body)* )}
103        {
104            use paste::paste;
105
106            // The number of bits of T.
107            const T: usize = <$T>::T;
108
109            #[inline(always)]
110            fn index(row: usize, lane: usize) -> usize {
111                let o = row / 8;
112                let s = row % 8;
113                (FL_ORDER[o] * 16) + (s * 128) + lane
114            }
115
116            if $W == 0 {
117                // Special case for W=0, we just need to zero the output.
118                // We'll still respect the iteration order in case the kernel has side effects.
119                paste!(seq_t!(row in $T {
120                    let idx = index(row, $lane);
121                    let zero: $T = 0;
122                    __kernel__!(idx, zero);
123                }));
124            } else if $W == T {
125                // Special case for W=T, we can just copy the packed value directly to the output.
126                paste!(seq_t!(row in $T {
127                    let idx = index(row, $lane);
128                    let src = $packed[<$T>::LANES * row + $lane];
129                    __kernel__!(idx, src);
130                }));
131            } else {
132                #[inline]
133                fn mask(width: usize) -> $T {
134                    if width == T { <$T>::MAX } else { (1 << (width % T)) - 1 }
135                }
136
137                let mut src: $T = $packed[$lane];
138                let mut tmp: $T;
139
140                paste!(seq_t!(row in $T {
141                    // Figure out the packed positions
142                    let curr_word: usize = (row * $W) / T;
143                    let next_word = ((row + 1) * $W) / T;
144
145                    let shift = (row * $W) % T;
146
147                    if next_word > curr_word {
148                        // Consume some bits from the curr packed input, the remainder are in the next
149                        // packed input value
150                        let remaining_bits = ((row + 1) * $W) % T;
151                        let current_bits = $W - remaining_bits;
152                        tmp = (src >> shift) & mask(current_bits);
153
154                        if next_word < $W {
155                            // Load the next packed value
156                            src = $packed[<$T>::LANES * next_word + $lane];
157                            // Consume the remaining bits from the next input value.
158                            tmp |= (src & mask(remaining_bits)) << current_bits;
159                        }
160                    } else {
161                        // Otherwise, just grab W bits from the src value
162                        tmp = (src >> shift) & mask($W);
163                    }
164
165                    // Write out the unpacked value
166                    let idx = index(row, $lane);
167                    __kernel__!(idx, tmp);
168                }));
169            }
170        }
171    };
172}
173
174// Macro for repeating a code block bit_size_of::<T> times.
175macro_rules! seq_t {
176    ($ident:ident in u8 $body:tt) => {seq_macro::seq!($ident in 0..8 $body)};
177    ($ident:ident in u16 $body:tt) => {seq_macro::seq!($ident in 0..16 $body)};
178    ($ident:ident in u32 $body:tt) => {seq_macro::seq!($ident in 0..32 $body)};
179    ($ident:ident in u64 $body:tt) => {seq_macro::seq!($ident in 0..64 $body)};
180}
181
182/// `BitPack` into a compile-time known bit-width.
183pub trait BitPacking: FastLanes {
184    /// Packs 1024 elements into `W` bits each, where `W` is runtime-known instead of
185    /// compile-time known.
186    ///
187    /// # Safety
188    /// The input slice must be of exactly length 1024. The output slice must be of length
189    /// `1024 * W / T`, where `T` is the bit-width of Self and `W` is the packed width.
190    /// These lengths are checked only with `debug_assert` (i.e., not checked on release builds).
191    unsafe fn unchecked_pack(width: usize, input: &[Self], output: &mut [Self]);
192
193    /// Unpacks 1024 elements from `W` bits each, where `W` is runtime-known instead of
194    /// compile-time known.
195    ///
196    /// # Safety
197    /// The input slice must be of length `1024 * W / T`, where `T` is the bit-width of Self and `W`
198    /// is the packed width. The output slice must be of exactly length 1024.
199    /// These lengths are checked only with `debug_assert` (i.e., not checked on release builds).
200    unsafe fn unchecked_unpack(width: usize, input: &[Self], output: &mut [Self]);
201}
202
203impl BitPacking for u8 {
204    unsafe fn unchecked_pack(width: usize, input: &[Self], output: &mut [Self]) {
205        let packed_len = 128 * width / size_of::<Self>();
206        debug_assert_eq!(
207            output.len(),
208            packed_len,
209            "Output buffer must be of size 1024 * W / T"
210        );
211        debug_assert_eq!(input.len(), 1024, "Input buffer must be of size 1024");
212        debug_assert!(
213            width <= Self::T,
214            "Width must be less than or equal to {}",
215            Self::T
216        );
217
218        match width {
219            0 => {
220                // Nothing to write when width is zero.
221            }
222            1 => pack_8_1(
223                array_ref![input, 0, 1024],
224                array_mut_ref![output, 0, 1024 / 8],
225            ),
226            2 => pack_8_2(
227                array_ref![input, 0, 1024],
228                array_mut_ref![output, 0, 1024 * 2 / 8],
229            ),
230            3 => pack_8_3(
231                array_ref![input, 0, 1024],
232                array_mut_ref![output, 0, 1024 * 3 / 8],
233            ),
234            4 => pack_8_4(
235                array_ref![input, 0, 1024],
236                array_mut_ref![output, 0, 1024 * 4 / 8],
237            ),
238            5 => pack_8_5(
239                array_ref![input, 0, 1024],
240                array_mut_ref![output, 0, 1024 * 5 / 8],
241            ),
242            6 => pack_8_6(
243                array_ref![input, 0, 1024],
244                array_mut_ref![output, 0, 1024 * 6 / 8],
245            ),
246            7 => pack_8_7(
247                array_ref![input, 0, 1024],
248                array_mut_ref![output, 0, 1024 * 7 / 8],
249            ),
250            8 => pack_8_8(
251                array_ref![input, 0, 1024],
252                array_mut_ref![output, 0, 1024 * 8 / 8],
253            ),
254
255            _ => unreachable!("Unsupported width: {}", width),
256        }
257    }
258
259    unsafe fn unchecked_unpack(width: usize, input: &[Self], output: &mut [Self]) {
260        let packed_len = 128 * width / size_of::<Self>();
261        debug_assert_eq!(
262            input.len(),
263            packed_len,
264            "Input buffer must be of size 1024 * W / T"
265        );
266        debug_assert_eq!(output.len(), 1024, "Output buffer must be of size 1024");
267        debug_assert!(
268            width <= Self::T,
269            "Width must be less than or equal to {}",
270            Self::T
271        );
272
273        match width {
274            0 => {
275                // A zero-width packed chunk implies all zeros.
276                output.fill(0);
277            }
278            1 => unpack_8_1(
279                array_ref![input, 0, 1024 / 8],
280                array_mut_ref![output, 0, 1024],
281            ),
282            2 => unpack_8_2(
283                array_ref![input, 0, 1024 * 2 / 8],
284                array_mut_ref![output, 0, 1024],
285            ),
286            3 => unpack_8_3(
287                array_ref![input, 0, 1024 * 3 / 8],
288                array_mut_ref![output, 0, 1024],
289            ),
290            4 => unpack_8_4(
291                array_ref![input, 0, 1024 * 4 / 8],
292                array_mut_ref![output, 0, 1024],
293            ),
294            5 => unpack_8_5(
295                array_ref![input, 0, 1024 * 5 / 8],
296                array_mut_ref![output, 0, 1024],
297            ),
298            6 => unpack_8_6(
299                array_ref![input, 0, 1024 * 6 / 8],
300                array_mut_ref![output, 0, 1024],
301            ),
302            7 => unpack_8_7(
303                array_ref![input, 0, 1024 * 7 / 8],
304                array_mut_ref![output, 0, 1024],
305            ),
306            8 => unpack_8_8(
307                array_ref![input, 0, 1024 * 8 / 8],
308                array_mut_ref![output, 0, 1024],
309            ),
310
311            _ => unreachable!("Unsupported width: {}", width),
312        }
313    }
314}
315
316impl BitPacking for u16 {
317    unsafe fn unchecked_pack(width: usize, input: &[Self], output: &mut [Self]) {
318        let packed_len = 128 * width / size_of::<Self>();
319        debug_assert_eq!(
320            output.len(),
321            packed_len,
322            "Output buffer must be of size 1024 * W / T"
323        );
324        debug_assert_eq!(input.len(), 1024, "Input buffer must be of size 1024");
325        debug_assert!(
326            width <= Self::T,
327            "Width must be less than or equal to {}",
328            Self::T
329        );
330
331        match width {
332            0 => {
333                // Nothing to write when width is zero.
334            }
335            1 => pack_16_1(
336                array_ref![input, 0, 1024],
337                array_mut_ref![output, 0, 1024 / 16],
338            ),
339            2 => pack_16_2(
340                array_ref![input, 0, 1024],
341                array_mut_ref![output, 0, 1024 * 2 / 16],
342            ),
343            3 => pack_16_3(
344                array_ref![input, 0, 1024],
345                array_mut_ref![output, 0, 1024 * 3 / 16],
346            ),
347            4 => pack_16_4(
348                array_ref![input, 0, 1024],
349                array_mut_ref![output, 0, 1024 * 4 / 16],
350            ),
351            5 => pack_16_5(
352                array_ref![input, 0, 1024],
353                array_mut_ref![output, 0, 1024 * 5 / 16],
354            ),
355            6 => pack_16_6(
356                array_ref![input, 0, 1024],
357                array_mut_ref![output, 0, 1024 * 6 / 16],
358            ),
359            7 => pack_16_7(
360                array_ref![input, 0, 1024],
361                array_mut_ref![output, 0, 1024 * 7 / 16],
362            ),
363            8 => pack_16_8(
364                array_ref![input, 0, 1024],
365                array_mut_ref![output, 0, 1024 * 8 / 16],
366            ),
367            9 => pack_16_9(
368                array_ref![input, 0, 1024],
369                array_mut_ref![output, 0, 1024 * 9 / 16],
370            ),
371
372            10 => pack_16_10(
373                array_ref![input, 0, 1024],
374                array_mut_ref![output, 0, 1024 * 10 / 16],
375            ),
376            11 => pack_16_11(
377                array_ref![input, 0, 1024],
378                array_mut_ref![output, 0, 1024 * 11 / 16],
379            ),
380            12 => pack_16_12(
381                array_ref![input, 0, 1024],
382                array_mut_ref![output, 0, 1024 * 12 / 16],
383            ),
384            13 => pack_16_13(
385                array_ref![input, 0, 1024],
386                array_mut_ref![output, 0, 1024 * 13 / 16],
387            ),
388            14 => pack_16_14(
389                array_ref![input, 0, 1024],
390                array_mut_ref![output, 0, 1024 * 14 / 16],
391            ),
392            15 => pack_16_15(
393                array_ref![input, 0, 1024],
394                array_mut_ref![output, 0, 1024 * 15 / 16],
395            ),
396            16 => pack_16_16(
397                array_ref![input, 0, 1024],
398                array_mut_ref![output, 0, 1024 * 16 / 16],
399            ),
400
401            _ => unreachable!("Unsupported width: {}", width),
402        }
403    }
404
405    unsafe fn unchecked_unpack(width: usize, input: &[Self], output: &mut [Self]) {
406        let packed_len = 128 * width / size_of::<Self>();
407        debug_assert_eq!(
408            input.len(),
409            packed_len,
410            "Input buffer must be of size 1024 * W / T"
411        );
412        debug_assert_eq!(output.len(), 1024, "Output buffer must be of size 1024");
413        debug_assert!(
414            width <= Self::T,
415            "Width must be less than or equal to {}",
416            Self::T
417        );
418
419        match width {
420            0 => {
421                output.fill(0);
422            }
423            1 => unpack_16_1(
424                array_ref![input, 0, 1024 / 16],
425                array_mut_ref![output, 0, 1024],
426            ),
427            2 => unpack_16_2(
428                array_ref![input, 0, 1024 * 2 / 16],
429                array_mut_ref![output, 0, 1024],
430            ),
431            3 => unpack_16_3(
432                array_ref![input, 0, 1024 * 3 / 16],
433                array_mut_ref![output, 0, 1024],
434            ),
435            4 => unpack_16_4(
436                array_ref![input, 0, 1024 * 4 / 16],
437                array_mut_ref![output, 0, 1024],
438            ),
439            5 => unpack_16_5(
440                array_ref![input, 0, 1024 * 5 / 16],
441                array_mut_ref![output, 0, 1024],
442            ),
443            6 => unpack_16_6(
444                array_ref![input, 0, 1024 * 6 / 16],
445                array_mut_ref![output, 0, 1024],
446            ),
447            7 => unpack_16_7(
448                array_ref![input, 0, 1024 * 7 / 16],
449                array_mut_ref![output, 0, 1024],
450            ),
451            8 => unpack_16_8(
452                array_ref![input, 0, 1024 * 8 / 16],
453                array_mut_ref![output, 0, 1024],
454            ),
455            9 => unpack_16_9(
456                array_ref![input, 0, 1024 * 9 / 16],
457                array_mut_ref![output, 0, 1024],
458            ),
459
460            10 => unpack_16_10(
461                array_ref![input, 0, 1024 * 10 / 16],
462                array_mut_ref![output, 0, 1024],
463            ),
464            11 => unpack_16_11(
465                array_ref![input, 0, 1024 * 11 / 16],
466                array_mut_ref![output, 0, 1024],
467            ),
468            12 => unpack_16_12(
469                array_ref![input, 0, 1024 * 12 / 16],
470                array_mut_ref![output, 0, 1024],
471            ),
472            13 => unpack_16_13(
473                array_ref![input, 0, 1024 * 13 / 16],
474                array_mut_ref![output, 0, 1024],
475            ),
476            14 => unpack_16_14(
477                array_ref![input, 0, 1024 * 14 / 16],
478                array_mut_ref![output, 0, 1024],
479            ),
480            15 => unpack_16_15(
481                array_ref![input, 0, 1024 * 15 / 16],
482                array_mut_ref![output, 0, 1024],
483            ),
484            16 => unpack_16_16(
485                array_ref![input, 0, 1024 * 16 / 16],
486                array_mut_ref![output, 0, 1024],
487            ),
488
489            _ => unreachable!("Unsupported width: {}", width),
490        }
491    }
492}
493
494impl BitPacking for u32 {
495    unsafe fn unchecked_pack(width: usize, input: &[Self], output: &mut [Self]) {
496        let packed_len = 128 * width / size_of::<Self>();
497        debug_assert_eq!(
498            output.len(),
499            packed_len,
500            "Output buffer must be of size 1024 * W / T"
501        );
502        debug_assert_eq!(input.len(), 1024, "Input buffer must be of size 1024");
503        debug_assert!(
504            width <= Self::T,
505            "Width must be less than or equal to {}",
506            Self::T
507        );
508
509        match width {
510            0 => {
511                // Nothing to write when width is zero.
512            }
513            1 => pack_32_1(
514                array_ref![input, 0, 1024],
515                array_mut_ref![output, 0, 1024 / 32],
516            ),
517            2 => pack_32_2(
518                array_ref![input, 0, 1024],
519                array_mut_ref![output, 0, 1024 * 2 / 32],
520            ),
521            3 => pack_32_3(
522                array_ref![input, 0, 1024],
523                array_mut_ref![output, 0, 1024 * 3 / 32],
524            ),
525            4 => pack_32_4(
526                array_ref![input, 0, 1024],
527                array_mut_ref![output, 0, 1024 * 4 / 32],
528            ),
529            5 => pack_32_5(
530                array_ref![input, 0, 1024],
531                array_mut_ref![output, 0, 1024 * 5 / 32],
532            ),
533            6 => pack_32_6(
534                array_ref![input, 0, 1024],
535                array_mut_ref![output, 0, 1024 * 6 / 32],
536            ),
537            7 => pack_32_7(
538                array_ref![input, 0, 1024],
539                array_mut_ref![output, 0, 1024 * 7 / 32],
540            ),
541            8 => pack_32_8(
542                array_ref![input, 0, 1024],
543                array_mut_ref![output, 0, 1024 * 8 / 32],
544            ),
545            9 => pack_32_9(
546                array_ref![input, 0, 1024],
547                array_mut_ref![output, 0, 1024 * 9 / 32],
548            ),
549
550            10 => pack_32_10(
551                array_ref![input, 0, 1024],
552                array_mut_ref![output, 0, 1024 * 10 / 32],
553            ),
554            11 => pack_32_11(
555                array_ref![input, 0, 1024],
556                array_mut_ref![output, 0, 1024 * 11 / 32],
557            ),
558            12 => pack_32_12(
559                array_ref![input, 0, 1024],
560                array_mut_ref![output, 0, 1024 * 12 / 32],
561            ),
562            13 => pack_32_13(
563                array_ref![input, 0, 1024],
564                array_mut_ref![output, 0, 1024 * 13 / 32],
565            ),
566            14 => pack_32_14(
567                array_ref![input, 0, 1024],
568                array_mut_ref![output, 0, 1024 * 14 / 32],
569            ),
570            15 => pack_32_15(
571                array_ref![input, 0, 1024],
572                array_mut_ref![output, 0, 1024 * 15 / 32],
573            ),
574            16 => pack_32_16(
575                array_ref![input, 0, 1024],
576                array_mut_ref![output, 0, 1024 * 16 / 32],
577            ),
578            17 => pack_32_17(
579                array_ref![input, 0, 1024],
580                array_mut_ref![output, 0, 1024 * 17 / 32],
581            ),
582            18 => pack_32_18(
583                array_ref![input, 0, 1024],
584                array_mut_ref![output, 0, 1024 * 18 / 32],
585            ),
586            19 => pack_32_19(
587                array_ref![input, 0, 1024],
588                array_mut_ref![output, 0, 1024 * 19 / 32],
589            ),
590
591            20 => pack_32_20(
592                array_ref![input, 0, 1024],
593                array_mut_ref![output, 0, 1024 * 20 / 32],
594            ),
595            21 => pack_32_21(
596                array_ref![input, 0, 1024],
597                array_mut_ref![output, 0, 1024 * 21 / 32],
598            ),
599            22 => pack_32_22(
600                array_ref![input, 0, 1024],
601                array_mut_ref![output, 0, 1024 * 22 / 32],
602            ),
603            23 => pack_32_23(
604                array_ref![input, 0, 1024],
605                array_mut_ref![output, 0, 1024 * 23 / 32],
606            ),
607            24 => pack_32_24(
608                array_ref![input, 0, 1024],
609                array_mut_ref![output, 0, 1024 * 24 / 32],
610            ),
611            25 => pack_32_25(
612                array_ref![input, 0, 1024],
613                array_mut_ref![output, 0, 1024 * 25 / 32],
614            ),
615            26 => pack_32_26(
616                array_ref![input, 0, 1024],
617                array_mut_ref![output, 0, 1024 * 26 / 32],
618            ),
619            27 => pack_32_27(
620                array_ref![input, 0, 1024],
621                array_mut_ref![output, 0, 1024 * 27 / 32],
622            ),
623            28 => pack_32_28(
624                array_ref![input, 0, 1024],
625                array_mut_ref![output, 0, 1024 * 28 / 32],
626            ),
627            29 => pack_32_29(
628                array_ref![input, 0, 1024],
629                array_mut_ref![output, 0, 1024 * 29 / 32],
630            ),
631
632            30 => pack_32_30(
633                array_ref![input, 0, 1024],
634                array_mut_ref![output, 0, 1024 * 30 / 32],
635            ),
636            31 => pack_32_31(
637                array_ref![input, 0, 1024],
638                array_mut_ref![output, 0, 1024 * 31 / 32],
639            ),
640            32 => pack_32_32(
641                array_ref![input, 0, 1024],
642                array_mut_ref![output, 0, 1024 * 32 / 32],
643            ),
644
645            _ => unreachable!("Unsupported width: {}", width),
646        }
647    }
648
649    unsafe fn unchecked_unpack(width: usize, input: &[Self], output: &mut [Self]) {
650        let packed_len = 128 * width / size_of::<Self>();
651        debug_assert_eq!(
652            input.len(),
653            packed_len,
654            "Input buffer must be of size 1024 * W / T"
655        );
656        debug_assert_eq!(output.len(), 1024, "Output buffer must be of size 1024");
657        debug_assert!(
658            width <= Self::T,
659            "Width must be less than or equal to {}",
660            Self::T
661        );
662
663        match width {
664            0 => {
665                output.fill(0);
666            }
667            1 => unpack_32_1(
668                array_ref![input, 0, 1024 / 32],
669                array_mut_ref![output, 0, 1024],
670            ),
671            2 => unpack_32_2(
672                array_ref![input, 0, 1024 * 2 / 32],
673                array_mut_ref![output, 0, 1024],
674            ),
675            3 => unpack_32_3(
676                array_ref![input, 0, 1024 * 3 / 32],
677                array_mut_ref![output, 0, 1024],
678            ),
679            4 => unpack_32_4(
680                array_ref![input, 0, 1024 * 4 / 32],
681                array_mut_ref![output, 0, 1024],
682            ),
683            5 => unpack_32_5(
684                array_ref![input, 0, 1024 * 5 / 32],
685                array_mut_ref![output, 0, 1024],
686            ),
687            6 => unpack_32_6(
688                array_ref![input, 0, 1024 * 6 / 32],
689                array_mut_ref![output, 0, 1024],
690            ),
691            7 => unpack_32_7(
692                array_ref![input, 0, 1024 * 7 / 32],
693                array_mut_ref![output, 0, 1024],
694            ),
695            8 => unpack_32_8(
696                array_ref![input, 0, 1024 * 8 / 32],
697                array_mut_ref![output, 0, 1024],
698            ),
699            9 => unpack_32_9(
700                array_ref![input, 0, 1024 * 9 / 32],
701                array_mut_ref![output, 0, 1024],
702            ),
703
704            10 => unpack_32_10(
705                array_ref![input, 0, 1024 * 10 / 32],
706                array_mut_ref![output, 0, 1024],
707            ),
708            11 => unpack_32_11(
709                array_ref![input, 0, 1024 * 11 / 32],
710                array_mut_ref![output, 0, 1024],
711            ),
712            12 => unpack_32_12(
713                array_ref![input, 0, 1024 * 12 / 32],
714                array_mut_ref![output, 0, 1024],
715            ),
716            13 => unpack_32_13(
717                array_ref![input, 0, 1024 * 13 / 32],
718                array_mut_ref![output, 0, 1024],
719            ),
720            14 => unpack_32_14(
721                array_ref![input, 0, 1024 * 14 / 32],
722                array_mut_ref![output, 0, 1024],
723            ),
724            15 => unpack_32_15(
725                array_ref![input, 0, 1024 * 15 / 32],
726                array_mut_ref![output, 0, 1024],
727            ),
728            16 => unpack_32_16(
729                array_ref![input, 0, 1024 * 16 / 32],
730                array_mut_ref![output, 0, 1024],
731            ),
732            17 => unpack_32_17(
733                array_ref![input, 0, 1024 * 17 / 32],
734                array_mut_ref![output, 0, 1024],
735            ),
736            18 => unpack_32_18(
737                array_ref![input, 0, 1024 * 18 / 32],
738                array_mut_ref![output, 0, 1024],
739            ),
740            19 => unpack_32_19(
741                array_ref![input, 0, 1024 * 19 / 32],
742                array_mut_ref![output, 0, 1024],
743            ),
744
745            20 => unpack_32_20(
746                array_ref![input, 0, 1024 * 20 / 32],
747                array_mut_ref![output, 0, 1024],
748            ),
749            21 => unpack_32_21(
750                array_ref![input, 0, 1024 * 21 / 32],
751                array_mut_ref![output, 0, 1024],
752            ),
753            22 => unpack_32_22(
754                array_ref![input, 0, 1024 * 22 / 32],
755                array_mut_ref![output, 0, 1024],
756            ),
757            23 => unpack_32_23(
758                array_ref![input, 0, 1024 * 23 / 32],
759                array_mut_ref![output, 0, 1024],
760            ),
761            24 => unpack_32_24(
762                array_ref![input, 0, 1024 * 24 / 32],
763                array_mut_ref![output, 0, 1024],
764            ),
765            25 => unpack_32_25(
766                array_ref![input, 0, 1024 * 25 / 32],
767                array_mut_ref![output, 0, 1024],
768            ),
769            26 => unpack_32_26(
770                array_ref![input, 0, 1024 * 26 / 32],
771                array_mut_ref![output, 0, 1024],
772            ),
773            27 => unpack_32_27(
774                array_ref![input, 0, 1024 * 27 / 32],
775                array_mut_ref![output, 0, 1024],
776            ),
777            28 => unpack_32_28(
778                array_ref![input, 0, 1024 * 28 / 32],
779                array_mut_ref![output, 0, 1024],
780            ),
781            29 => unpack_32_29(
782                array_ref![input, 0, 1024 * 29 / 32],
783                array_mut_ref![output, 0, 1024],
784            ),
785
786            30 => unpack_32_30(
787                array_ref![input, 0, 1024 * 30 / 32],
788                array_mut_ref![output, 0, 1024],
789            ),
790            31 => unpack_32_31(
791                array_ref![input, 0, 1024 * 31 / 32],
792                array_mut_ref![output, 0, 1024],
793            ),
794            32 => unpack_32_32(
795                array_ref![input, 0, 1024 * 32 / 32],
796                array_mut_ref![output, 0, 1024],
797            ),
798
799            _ => unreachable!("Unsupported width: {}", width),
800        }
801    }
802}
803
804impl BitPacking for u64 {
805    unsafe fn unchecked_pack(width: usize, input: &[Self], output: &mut [Self]) {
806        let packed_len = 128 * width / size_of::<Self>();
807        debug_assert_eq!(
808            output.len(),
809            packed_len,
810            "Output buffer must be of size 1024 * W / T"
811        );
812        debug_assert_eq!(input.len(), 1024, "Input buffer must be of size 1024");
813        debug_assert!(
814            width <= Self::T,
815            "Width must be less than or equal to {}",
816            Self::T
817        );
818
819        match width {
820            0 => {
821                // Nothing to write when width is zero.
822            }
823            1 => pack_64_1(
824                array_ref![input, 0, 1024],
825                array_mut_ref![output, 0, 1024 / 64],
826            ),
827            2 => pack_64_2(
828                array_ref![input, 0, 1024],
829                array_mut_ref![output, 0, 1024 * 2 / 64],
830            ),
831            3 => pack_64_3(
832                array_ref![input, 0, 1024],
833                array_mut_ref![output, 0, 1024 * 3 / 64],
834            ),
835            4 => pack_64_4(
836                array_ref![input, 0, 1024],
837                array_mut_ref![output, 0, 1024 * 4 / 64],
838            ),
839            5 => pack_64_5(
840                array_ref![input, 0, 1024],
841                array_mut_ref![output, 0, 1024 * 5 / 64],
842            ),
843            6 => pack_64_6(
844                array_ref![input, 0, 1024],
845                array_mut_ref![output, 0, 1024 * 6 / 64],
846            ),
847            7 => pack_64_7(
848                array_ref![input, 0, 1024],
849                array_mut_ref![output, 0, 1024 * 7 / 64],
850            ),
851            8 => pack_64_8(
852                array_ref![input, 0, 1024],
853                array_mut_ref![output, 0, 1024 * 8 / 64],
854            ),
855            9 => pack_64_9(
856                array_ref![input, 0, 1024],
857                array_mut_ref![output, 0, 1024 * 9 / 64],
858            ),
859
860            10 => pack_64_10(
861                array_ref![input, 0, 1024],
862                array_mut_ref![output, 0, 1024 * 10 / 64],
863            ),
864            11 => pack_64_11(
865                array_ref![input, 0, 1024],
866                array_mut_ref![output, 0, 1024 * 11 / 64],
867            ),
868            12 => pack_64_12(
869                array_ref![input, 0, 1024],
870                array_mut_ref![output, 0, 1024 * 12 / 64],
871            ),
872            13 => pack_64_13(
873                array_ref![input, 0, 1024],
874                array_mut_ref![output, 0, 1024 * 13 / 64],
875            ),
876            14 => pack_64_14(
877                array_ref![input, 0, 1024],
878                array_mut_ref![output, 0, 1024 * 14 / 64],
879            ),
880            15 => pack_64_15(
881                array_ref![input, 0, 1024],
882                array_mut_ref![output, 0, 1024 * 15 / 64],
883            ),
884            16 => pack_64_16(
885                array_ref![input, 0, 1024],
886                array_mut_ref![output, 0, 1024 * 16 / 64],
887            ),
888            17 => pack_64_17(
889                array_ref![input, 0, 1024],
890                array_mut_ref![output, 0, 1024 * 17 / 64],
891            ),
892            18 => pack_64_18(
893                array_ref![input, 0, 1024],
894                array_mut_ref![output, 0, 1024 * 18 / 64],
895            ),
896            19 => pack_64_19(
897                array_ref![input, 0, 1024],
898                array_mut_ref![output, 0, 1024 * 19 / 64],
899            ),
900
901            20 => pack_64_20(
902                array_ref![input, 0, 1024],
903                array_mut_ref![output, 0, 1024 * 20 / 64],
904            ),
905            21 => pack_64_21(
906                array_ref![input, 0, 1024],
907                array_mut_ref![output, 0, 1024 * 21 / 64],
908            ),
909            22 => pack_64_22(
910                array_ref![input, 0, 1024],
911                array_mut_ref![output, 0, 1024 * 22 / 64],
912            ),
913            23 => pack_64_23(
914                array_ref![input, 0, 1024],
915                array_mut_ref![output, 0, 1024 * 23 / 64],
916            ),
917            24 => pack_64_24(
918                array_ref![input, 0, 1024],
919                array_mut_ref![output, 0, 1024 * 24 / 64],
920            ),
921            25 => pack_64_25(
922                array_ref![input, 0, 1024],
923                array_mut_ref![output, 0, 1024 * 25 / 64],
924            ),
925            26 => pack_64_26(
926                array_ref![input, 0, 1024],
927                array_mut_ref![output, 0, 1024 * 26 / 64],
928            ),
929            27 => pack_64_27(
930                array_ref![input, 0, 1024],
931                array_mut_ref![output, 0, 1024 * 27 / 64],
932            ),
933            28 => pack_64_28(
934                array_ref![input, 0, 1024],
935                array_mut_ref![output, 0, 1024 * 28 / 64],
936            ),
937            29 => pack_64_29(
938                array_ref![input, 0, 1024],
939                array_mut_ref![output, 0, 1024 * 29 / 64],
940            ),
941
942            30 => pack_64_30(
943                array_ref![input, 0, 1024],
944                array_mut_ref![output, 0, 1024 * 30 / 64],
945            ),
946            31 => pack_64_31(
947                array_ref![input, 0, 1024],
948                array_mut_ref![output, 0, 1024 * 31 / 64],
949            ),
950            32 => pack_64_32(
951                array_ref![input, 0, 1024],
952                array_mut_ref![output, 0, 1024 * 32 / 64],
953            ),
954            33 => pack_64_33(
955                array_ref![input, 0, 1024],
956                array_mut_ref![output, 0, 1024 * 33 / 64],
957            ),
958            34 => pack_64_34(
959                array_ref![input, 0, 1024],
960                array_mut_ref![output, 0, 1024 * 34 / 64],
961            ),
962            35 => pack_64_35(
963                array_ref![input, 0, 1024],
964                array_mut_ref![output, 0, 1024 * 35 / 64],
965            ),
966            36 => pack_64_36(
967                array_ref![input, 0, 1024],
968                array_mut_ref![output, 0, 1024 * 36 / 64],
969            ),
970            37 => pack_64_37(
971                array_ref![input, 0, 1024],
972                array_mut_ref![output, 0, 1024 * 37 / 64],
973            ),
974            38 => pack_64_38(
975                array_ref![input, 0, 1024],
976                array_mut_ref![output, 0, 1024 * 38 / 64],
977            ),
978            39 => pack_64_39(
979                array_ref![input, 0, 1024],
980                array_mut_ref![output, 0, 1024 * 39 / 64],
981            ),
982
983            40 => pack_64_40(
984                array_ref![input, 0, 1024],
985                array_mut_ref![output, 0, 1024 * 40 / 64],
986            ),
987            41 => pack_64_41(
988                array_ref![input, 0, 1024],
989                array_mut_ref![output, 0, 1024 * 41 / 64],
990            ),
991            42 => pack_64_42(
992                array_ref![input, 0, 1024],
993                array_mut_ref![output, 0, 1024 * 42 / 64],
994            ),
995            43 => pack_64_43(
996                array_ref![input, 0, 1024],
997                array_mut_ref![output, 0, 1024 * 43 / 64],
998            ),
999            44 => pack_64_44(
1000                array_ref![input, 0, 1024],
1001                array_mut_ref![output, 0, 1024 * 44 / 64],
1002            ),
1003            45 => pack_64_45(
1004                array_ref![input, 0, 1024],
1005                array_mut_ref![output, 0, 1024 * 45 / 64],
1006            ),
1007            46 => pack_64_46(
1008                array_ref![input, 0, 1024],
1009                array_mut_ref![output, 0, 1024 * 46 / 64],
1010            ),
1011            47 => pack_64_47(
1012                array_ref![input, 0, 1024],
1013                array_mut_ref![output, 0, 1024 * 47 / 64],
1014            ),
1015            48 => pack_64_48(
1016                array_ref![input, 0, 1024],
1017                array_mut_ref![output, 0, 1024 * 48 / 64],
1018            ),
1019            49 => pack_64_49(
1020                array_ref![input, 0, 1024],
1021                array_mut_ref![output, 0, 1024 * 49 / 64],
1022            ),
1023
1024            50 => pack_64_50(
1025                array_ref![input, 0, 1024],
1026                array_mut_ref![output, 0, 1024 * 50 / 64],
1027            ),
1028            51 => pack_64_51(
1029                array_ref![input, 0, 1024],
1030                array_mut_ref![output, 0, 1024 * 51 / 64],
1031            ),
1032            52 => pack_64_52(
1033                array_ref![input, 0, 1024],
1034                array_mut_ref![output, 0, 1024 * 52 / 64],
1035            ),
1036            53 => pack_64_53(
1037                array_ref![input, 0, 1024],
1038                array_mut_ref![output, 0, 1024 * 53 / 64],
1039            ),
1040            54 => pack_64_54(
1041                array_ref![input, 0, 1024],
1042                array_mut_ref![output, 0, 1024 * 54 / 64],
1043            ),
1044            55 => pack_64_55(
1045                array_ref![input, 0, 1024],
1046                array_mut_ref![output, 0, 1024 * 55 / 64],
1047            ),
1048            56 => pack_64_56(
1049                array_ref![input, 0, 1024],
1050                array_mut_ref![output, 0, 1024 * 56 / 64],
1051            ),
1052            57 => pack_64_57(
1053                array_ref![input, 0, 1024],
1054                array_mut_ref![output, 0, 1024 * 57 / 64],
1055            ),
1056            58 => pack_64_58(
1057                array_ref![input, 0, 1024],
1058                array_mut_ref![output, 0, 1024 * 58 / 64],
1059            ),
1060            59 => pack_64_59(
1061                array_ref![input, 0, 1024],
1062                array_mut_ref![output, 0, 1024 * 59 / 64],
1063            ),
1064
1065            60 => pack_64_60(
1066                array_ref![input, 0, 1024],
1067                array_mut_ref![output, 0, 1024 * 60 / 64],
1068            ),
1069            61 => pack_64_61(
1070                array_ref![input, 0, 1024],
1071                array_mut_ref![output, 0, 1024 * 61 / 64],
1072            ),
1073            62 => pack_64_62(
1074                array_ref![input, 0, 1024],
1075                array_mut_ref![output, 0, 1024 * 62 / 64],
1076            ),
1077            63 => pack_64_63(
1078                array_ref![input, 0, 1024],
1079                array_mut_ref![output, 0, 1024 * 63 / 64],
1080            ),
1081            64 => pack_64_64(
1082                array_ref![input, 0, 1024],
1083                array_mut_ref![output, 0, 1024 * 64 / 64],
1084            ),
1085
1086            _ => unreachable!("Unsupported width: {}", width),
1087        }
1088    }
1089
1090    unsafe fn unchecked_unpack(width: usize, input: &[Self], output: &mut [Self]) {
1091        let packed_len = 128 * width / size_of::<Self>();
1092        debug_assert_eq!(
1093            input.len(),
1094            packed_len,
1095            "Input buffer must be of size 1024 * W / T"
1096        );
1097        debug_assert_eq!(output.len(), 1024, "Output buffer must be of size 1024");
1098        debug_assert!(
1099            width <= Self::T,
1100            "Width must be less than or equal to {}",
1101            Self::T
1102        );
1103
1104        match width {
1105            0 => {
1106                output.fill(0);
1107            }
1108            1 => unpack_64_1(
1109                array_ref![input, 0, 1024 / 64],
1110                array_mut_ref![output, 0, 1024],
1111            ),
1112            2 => unpack_64_2(
1113                array_ref![input, 0, 1024 * 2 / 64],
1114                array_mut_ref![output, 0, 1024],
1115            ),
1116            3 => unpack_64_3(
1117                array_ref![input, 0, 1024 * 3 / 64],
1118                array_mut_ref![output, 0, 1024],
1119            ),
1120            4 => unpack_64_4(
1121                array_ref![input, 0, 1024 * 4 / 64],
1122                array_mut_ref![output, 0, 1024],
1123            ),
1124            5 => unpack_64_5(
1125                array_ref![input, 0, 1024 * 5 / 64],
1126                array_mut_ref![output, 0, 1024],
1127            ),
1128            6 => unpack_64_6(
1129                array_ref![input, 0, 1024 * 6 / 64],
1130                array_mut_ref![output, 0, 1024],
1131            ),
1132            7 => unpack_64_7(
1133                array_ref![input, 0, 1024 * 7 / 64],
1134                array_mut_ref![output, 0, 1024],
1135            ),
1136            8 => unpack_64_8(
1137                array_ref![input, 0, 1024 * 8 / 64],
1138                array_mut_ref![output, 0, 1024],
1139            ),
1140            9 => unpack_64_9(
1141                array_ref![input, 0, 1024 * 9 / 64],
1142                array_mut_ref![output, 0, 1024],
1143            ),
1144
1145            10 => unpack_64_10(
1146                array_ref![input, 0, 1024 * 10 / 64],
1147                array_mut_ref![output, 0, 1024],
1148            ),
1149            11 => unpack_64_11(
1150                array_ref![input, 0, 1024 * 11 / 64],
1151                array_mut_ref![output, 0, 1024],
1152            ),
1153            12 => unpack_64_12(
1154                array_ref![input, 0, 1024 * 12 / 64],
1155                array_mut_ref![output, 0, 1024],
1156            ),
1157            13 => unpack_64_13(
1158                array_ref![input, 0, 1024 * 13 / 64],
1159                array_mut_ref![output, 0, 1024],
1160            ),
1161            14 => unpack_64_14(
1162                array_ref![input, 0, 1024 * 14 / 64],
1163                array_mut_ref![output, 0, 1024],
1164            ),
1165            15 => unpack_64_15(
1166                array_ref![input, 0, 1024 * 15 / 64],
1167                array_mut_ref![output, 0, 1024],
1168            ),
1169            16 => unpack_64_16(
1170                array_ref![input, 0, 1024 * 16 / 64],
1171                array_mut_ref![output, 0, 1024],
1172            ),
1173            17 => unpack_64_17(
1174                array_ref![input, 0, 1024 * 17 / 64],
1175                array_mut_ref![output, 0, 1024],
1176            ),
1177            18 => unpack_64_18(
1178                array_ref![input, 0, 1024 * 18 / 64],
1179                array_mut_ref![output, 0, 1024],
1180            ),
1181            19 => unpack_64_19(
1182                array_ref![input, 0, 1024 * 19 / 64],
1183                array_mut_ref![output, 0, 1024],
1184            ),
1185
1186            20 => unpack_64_20(
1187                array_ref![input, 0, 1024 * 20 / 64],
1188                array_mut_ref![output, 0, 1024],
1189            ),
1190            21 => unpack_64_21(
1191                array_ref![input, 0, 1024 * 21 / 64],
1192                array_mut_ref![output, 0, 1024],
1193            ),
1194            22 => unpack_64_22(
1195                array_ref![input, 0, 1024 * 22 / 64],
1196                array_mut_ref![output, 0, 1024],
1197            ),
1198            23 => unpack_64_23(
1199                array_ref![input, 0, 1024 * 23 / 64],
1200                array_mut_ref![output, 0, 1024],
1201            ),
1202            24 => unpack_64_24(
1203                array_ref![input, 0, 1024 * 24 / 64],
1204                array_mut_ref![output, 0, 1024],
1205            ),
1206            25 => unpack_64_25(
1207                array_ref![input, 0, 1024 * 25 / 64],
1208                array_mut_ref![output, 0, 1024],
1209            ),
1210            26 => unpack_64_26(
1211                array_ref![input, 0, 1024 * 26 / 64],
1212                array_mut_ref![output, 0, 1024],
1213            ),
1214            27 => unpack_64_27(
1215                array_ref![input, 0, 1024 * 27 / 64],
1216                array_mut_ref![output, 0, 1024],
1217            ),
1218            28 => unpack_64_28(
1219                array_ref![input, 0, 1024 * 28 / 64],
1220                array_mut_ref![output, 0, 1024],
1221            ),
1222            29 => unpack_64_29(
1223                array_ref![input, 0, 1024 * 29 / 64],
1224                array_mut_ref![output, 0, 1024],
1225            ),
1226
1227            30 => unpack_64_30(
1228                array_ref![input, 0, 1024 * 30 / 64],
1229                array_mut_ref![output, 0, 1024],
1230            ),
1231            31 => unpack_64_31(
1232                array_ref![input, 0, 1024 * 31 / 64],
1233                array_mut_ref![output, 0, 1024],
1234            ),
1235            32 => unpack_64_32(
1236                array_ref![input, 0, 1024 * 32 / 64],
1237                array_mut_ref![output, 0, 1024],
1238            ),
1239            33 => unpack_64_33(
1240                array_ref![input, 0, 1024 * 33 / 64],
1241                array_mut_ref![output, 0, 1024],
1242            ),
1243            34 => unpack_64_34(
1244                array_ref![input, 0, 1024 * 34 / 64],
1245                array_mut_ref![output, 0, 1024],
1246            ),
1247            35 => unpack_64_35(
1248                array_ref![input, 0, 1024 * 35 / 64],
1249                array_mut_ref![output, 0, 1024],
1250            ),
1251            36 => unpack_64_36(
1252                array_ref![input, 0, 1024 * 36 / 64],
1253                array_mut_ref![output, 0, 1024],
1254            ),
1255            37 => unpack_64_37(
1256                array_ref![input, 0, 1024 * 37 / 64],
1257                array_mut_ref![output, 0, 1024],
1258            ),
1259            38 => unpack_64_38(
1260                array_ref![input, 0, 1024 * 38 / 64],
1261                array_mut_ref![output, 0, 1024],
1262            ),
1263            39 => unpack_64_39(
1264                array_ref![input, 0, 1024 * 39 / 64],
1265                array_mut_ref![output, 0, 1024],
1266            ),
1267
1268            40 => unpack_64_40(
1269                array_ref![input, 0, 1024 * 40 / 64],
1270                array_mut_ref![output, 0, 1024],
1271            ),
1272            41 => unpack_64_41(
1273                array_ref![input, 0, 1024 * 41 / 64],
1274                array_mut_ref![output, 0, 1024],
1275            ),
1276            42 => unpack_64_42(
1277                array_ref![input, 0, 1024 * 42 / 64],
1278                array_mut_ref![output, 0, 1024],
1279            ),
1280            43 => unpack_64_43(
1281                array_ref![input, 0, 1024 * 43 / 64],
1282                array_mut_ref![output, 0, 1024],
1283            ),
1284            44 => unpack_64_44(
1285                array_ref![input, 0, 1024 * 44 / 64],
1286                array_mut_ref![output, 0, 1024],
1287            ),
1288            45 => unpack_64_45(
1289                array_ref![input, 0, 1024 * 45 / 64],
1290                array_mut_ref![output, 0, 1024],
1291            ),
1292            46 => unpack_64_46(
1293                array_ref![input, 0, 1024 * 46 / 64],
1294                array_mut_ref![output, 0, 1024],
1295            ),
1296            47 => unpack_64_47(
1297                array_ref![input, 0, 1024 * 47 / 64],
1298                array_mut_ref![output, 0, 1024],
1299            ),
1300            48 => unpack_64_48(
1301                array_ref![input, 0, 1024 * 48 / 64],
1302                array_mut_ref![output, 0, 1024],
1303            ),
1304            49 => unpack_64_49(
1305                array_ref![input, 0, 1024 * 49 / 64],
1306                array_mut_ref![output, 0, 1024],
1307            ),
1308
1309            50 => unpack_64_50(
1310                array_ref![input, 0, 1024 * 50 / 64],
1311                array_mut_ref![output, 0, 1024],
1312            ),
1313            51 => unpack_64_51(
1314                array_ref![input, 0, 1024 * 51 / 64],
1315                array_mut_ref![output, 0, 1024],
1316            ),
1317            52 => unpack_64_52(
1318                array_ref![input, 0, 1024 * 52 / 64],
1319                array_mut_ref![output, 0, 1024],
1320            ),
1321            53 => unpack_64_53(
1322                array_ref![input, 0, 1024 * 53 / 64],
1323                array_mut_ref![output, 0, 1024],
1324            ),
1325            54 => unpack_64_54(
1326                array_ref![input, 0, 1024 * 54 / 64],
1327                array_mut_ref![output, 0, 1024],
1328            ),
1329            55 => unpack_64_55(
1330                array_ref![input, 0, 1024 * 55 / 64],
1331                array_mut_ref![output, 0, 1024],
1332            ),
1333            56 => unpack_64_56(
1334                array_ref![input, 0, 1024 * 56 / 64],
1335                array_mut_ref![output, 0, 1024],
1336            ),
1337            57 => unpack_64_57(
1338                array_ref![input, 0, 1024 * 57 / 64],
1339                array_mut_ref![output, 0, 1024],
1340            ),
1341            58 => unpack_64_58(
1342                array_ref![input, 0, 1024 * 58 / 64],
1343                array_mut_ref![output, 0, 1024],
1344            ),
1345            59 => unpack_64_59(
1346                array_ref![input, 0, 1024 * 59 / 64],
1347                array_mut_ref![output, 0, 1024],
1348            ),
1349
1350            60 => unpack_64_60(
1351                array_ref![input, 0, 1024 * 60 / 64],
1352                array_mut_ref![output, 0, 1024],
1353            ),
1354            61 => unpack_64_61(
1355                array_ref![input, 0, 1024 * 61 / 64],
1356                array_mut_ref![output, 0, 1024],
1357            ),
1358            62 => unpack_64_62(
1359                array_ref![input, 0, 1024 * 62 / 64],
1360                array_mut_ref![output, 0, 1024],
1361            ),
1362            63 => unpack_64_63(
1363                array_ref![input, 0, 1024 * 63 / 64],
1364                array_mut_ref![output, 0, 1024],
1365            ),
1366            64 => unpack_64_64(
1367                array_ref![input, 0, 1024 * 64 / 64],
1368                array_mut_ref![output, 0, 1024],
1369            ),
1370
1371            _ => unreachable!("Unsupported width: {}", width),
1372        }
1373    }
1374}
1375
1376macro_rules! unpack_8 {
1377    ($name:ident, $bits:expr) => {
1378        fn $name(input: &[u8; 1024 * $bits / u8::T], output: &mut [u8; 1024]) {
1379            for lane in 0..u8::LANES {
1380                unpack!(u8, $bits, input, lane, |$idx, $elem| {
1381                    output[$idx] = $elem;
1382                });
1383            }
1384        }
1385    };
1386}
1387
1388unpack_8!(unpack_8_1, 1);
1389unpack_8!(unpack_8_2, 2);
1390unpack_8!(unpack_8_3, 3);
1391unpack_8!(unpack_8_4, 4);
1392unpack_8!(unpack_8_5, 5);
1393unpack_8!(unpack_8_6, 6);
1394unpack_8!(unpack_8_7, 7);
1395unpack_8!(unpack_8_8, 8);
1396
1397macro_rules! pack_8 {
1398    ($name:ident, $bits:expr) => {
1399        fn $name(input: &[u8; 1024], output: &mut [u8; 1024 * $bits / u8::T]) {
1400            for lane in 0..u8::LANES {
1401                pack!(u8, $bits, output, lane, |$idx| { input[$idx] });
1402            }
1403        }
1404    };
1405}
1406pack_8!(pack_8_1, 1);
1407pack_8!(pack_8_2, 2);
1408pack_8!(pack_8_3, 3);
1409pack_8!(pack_8_4, 4);
1410pack_8!(pack_8_5, 5);
1411pack_8!(pack_8_6, 6);
1412pack_8!(pack_8_7, 7);
1413pack_8!(pack_8_8, 8);
1414
1415macro_rules! unpack_16 {
1416    ($name:ident, $bits:expr) => {
1417        fn $name(input: &[u16; 1024 * $bits / u16::T], output: &mut [u16; 1024]) {
1418            for lane in 0..u16::LANES {
1419                unpack!(u16, $bits, input, lane, |$idx, $elem| {
1420                    output[$idx] = $elem;
1421                });
1422            }
1423        }
1424    };
1425}
1426
1427unpack_16!(unpack_16_1, 1);
1428unpack_16!(unpack_16_2, 2);
1429unpack_16!(unpack_16_3, 3);
1430unpack_16!(unpack_16_4, 4);
1431unpack_16!(unpack_16_5, 5);
1432unpack_16!(unpack_16_6, 6);
1433unpack_16!(unpack_16_7, 7);
1434unpack_16!(unpack_16_8, 8);
1435unpack_16!(unpack_16_9, 9);
1436unpack_16!(unpack_16_10, 10);
1437unpack_16!(unpack_16_11, 11);
1438unpack_16!(unpack_16_12, 12);
1439unpack_16!(unpack_16_13, 13);
1440unpack_16!(unpack_16_14, 14);
1441unpack_16!(unpack_16_15, 15);
1442unpack_16!(unpack_16_16, 16);
1443
1444macro_rules! pack_16 {
1445    ($name:ident, $bits:expr) => {
1446        fn $name(input: &[u16; 1024], output: &mut [u16; 1024 * $bits / u16::T]) {
1447            for lane in 0..u16::LANES {
1448                pack!(u16, $bits, output, lane, |$idx| { input[$idx] });
1449            }
1450        }
1451    };
1452}
1453
1454pack_16!(pack_16_1, 1);
1455pack_16!(pack_16_2, 2);
1456pack_16!(pack_16_3, 3);
1457pack_16!(pack_16_4, 4);
1458pack_16!(pack_16_5, 5);
1459pack_16!(pack_16_6, 6);
1460pack_16!(pack_16_7, 7);
1461pack_16!(pack_16_8, 8);
1462pack_16!(pack_16_9, 9);
1463pack_16!(pack_16_10, 10);
1464pack_16!(pack_16_11, 11);
1465pack_16!(pack_16_12, 12);
1466pack_16!(pack_16_13, 13);
1467pack_16!(pack_16_14, 14);
1468pack_16!(pack_16_15, 15);
1469pack_16!(pack_16_16, 16);
1470
1471macro_rules! unpack_32 {
1472    ($name:ident, $bit_width:expr) => {
1473        fn $name(input: &[u32; 1024 * $bit_width / u32::T], output: &mut [u32; 1024]) {
1474            for lane in 0..u32::LANES {
1475                unpack!(u32, $bit_width, input, lane, |$idx, $elem| {
1476                    output[$idx] = $elem
1477                });
1478            }
1479        }
1480    };
1481}
1482
1483unpack_32!(unpack_32_1, 1);
1484unpack_32!(unpack_32_2, 2);
1485unpack_32!(unpack_32_3, 3);
1486unpack_32!(unpack_32_4, 4);
1487unpack_32!(unpack_32_5, 5);
1488unpack_32!(unpack_32_6, 6);
1489unpack_32!(unpack_32_7, 7);
1490unpack_32!(unpack_32_8, 8);
1491unpack_32!(unpack_32_9, 9);
1492unpack_32!(unpack_32_10, 10);
1493unpack_32!(unpack_32_11, 11);
1494unpack_32!(unpack_32_12, 12);
1495unpack_32!(unpack_32_13, 13);
1496unpack_32!(unpack_32_14, 14);
1497unpack_32!(unpack_32_15, 15);
1498unpack_32!(unpack_32_16, 16);
1499unpack_32!(unpack_32_17, 17);
1500unpack_32!(unpack_32_18, 18);
1501unpack_32!(unpack_32_19, 19);
1502unpack_32!(unpack_32_20, 20);
1503unpack_32!(unpack_32_21, 21);
1504unpack_32!(unpack_32_22, 22);
1505unpack_32!(unpack_32_23, 23);
1506unpack_32!(unpack_32_24, 24);
1507unpack_32!(unpack_32_25, 25);
1508unpack_32!(unpack_32_26, 26);
1509unpack_32!(unpack_32_27, 27);
1510unpack_32!(unpack_32_28, 28);
1511unpack_32!(unpack_32_29, 29);
1512unpack_32!(unpack_32_30, 30);
1513unpack_32!(unpack_32_31, 31);
1514unpack_32!(unpack_32_32, 32);
1515
1516macro_rules! pack_32 {
1517    ($name:ident, $bits:expr) => {
1518        fn $name(input: &[u32; 1024], output: &mut [u32; 1024 * $bits / u32::BITS as usize]) {
1519            for lane in 0..u32::LANES {
1520                pack!(u32, $bits, output, lane, |$idx| { input[$idx] });
1521            }
1522        }
1523    };
1524}
1525
1526pack_32!(pack_32_1, 1);
1527pack_32!(pack_32_2, 2);
1528pack_32!(pack_32_3, 3);
1529pack_32!(pack_32_4, 4);
1530pack_32!(pack_32_5, 5);
1531pack_32!(pack_32_6, 6);
1532pack_32!(pack_32_7, 7);
1533pack_32!(pack_32_8, 8);
1534pack_32!(pack_32_9, 9);
1535pack_32!(pack_32_10, 10);
1536pack_32!(pack_32_11, 11);
1537pack_32!(pack_32_12, 12);
1538pack_32!(pack_32_13, 13);
1539pack_32!(pack_32_14, 14);
1540pack_32!(pack_32_15, 15);
1541pack_32!(pack_32_16, 16);
1542pack_32!(pack_32_17, 17);
1543pack_32!(pack_32_18, 18);
1544pack_32!(pack_32_19, 19);
1545pack_32!(pack_32_20, 20);
1546pack_32!(pack_32_21, 21);
1547pack_32!(pack_32_22, 22);
1548pack_32!(pack_32_23, 23);
1549pack_32!(pack_32_24, 24);
1550pack_32!(pack_32_25, 25);
1551pack_32!(pack_32_26, 26);
1552pack_32!(pack_32_27, 27);
1553pack_32!(pack_32_28, 28);
1554pack_32!(pack_32_29, 29);
1555pack_32!(pack_32_30, 30);
1556pack_32!(pack_32_31, 31);
1557pack_32!(pack_32_32, 32);
1558
1559macro_rules! unpack_64 {
1560    ($name:ident, $bit_width:expr) => {
1561        fn $name(input: &[u64; 1024 * $bit_width / u64::T], output: &mut [u64; 1024]) {
1562            for lane in 0..u64::LANES {
1563                unpack!(u64, $bit_width, input, lane, |$idx, $elem| {
1564                    output[$idx] = $elem
1565                });
1566            }
1567        }
1568    };
1569}
1570
1571unpack_64!(unpack_64_1, 1);
1572unpack_64!(unpack_64_2, 2);
1573unpack_64!(unpack_64_3, 3);
1574unpack_64!(unpack_64_4, 4);
1575unpack_64!(unpack_64_5, 5);
1576unpack_64!(unpack_64_6, 6);
1577unpack_64!(unpack_64_7, 7);
1578unpack_64!(unpack_64_8, 8);
1579unpack_64!(unpack_64_9, 9);
1580unpack_64!(unpack_64_10, 10);
1581unpack_64!(unpack_64_11, 11);
1582unpack_64!(unpack_64_12, 12);
1583unpack_64!(unpack_64_13, 13);
1584unpack_64!(unpack_64_14, 14);
1585unpack_64!(unpack_64_15, 15);
1586unpack_64!(unpack_64_16, 16);
1587unpack_64!(unpack_64_17, 17);
1588unpack_64!(unpack_64_18, 18);
1589unpack_64!(unpack_64_19, 19);
1590unpack_64!(unpack_64_20, 20);
1591unpack_64!(unpack_64_21, 21);
1592unpack_64!(unpack_64_22, 22);
1593unpack_64!(unpack_64_23, 23);
1594unpack_64!(unpack_64_24, 24);
1595unpack_64!(unpack_64_25, 25);
1596unpack_64!(unpack_64_26, 26);
1597unpack_64!(unpack_64_27, 27);
1598unpack_64!(unpack_64_28, 28);
1599unpack_64!(unpack_64_29, 29);
1600unpack_64!(unpack_64_30, 30);
1601unpack_64!(unpack_64_31, 31);
1602unpack_64!(unpack_64_32, 32);
1603
1604unpack_64!(unpack_64_33, 33);
1605unpack_64!(unpack_64_34, 34);
1606unpack_64!(unpack_64_35, 35);
1607unpack_64!(unpack_64_36, 36);
1608unpack_64!(unpack_64_37, 37);
1609unpack_64!(unpack_64_38, 38);
1610unpack_64!(unpack_64_39, 39);
1611unpack_64!(unpack_64_40, 40);
1612unpack_64!(unpack_64_41, 41);
1613unpack_64!(unpack_64_42, 42);
1614unpack_64!(unpack_64_43, 43);
1615unpack_64!(unpack_64_44, 44);
1616unpack_64!(unpack_64_45, 45);
1617unpack_64!(unpack_64_46, 46);
1618unpack_64!(unpack_64_47, 47);
1619unpack_64!(unpack_64_48, 48);
1620unpack_64!(unpack_64_49, 49);
1621unpack_64!(unpack_64_50, 50);
1622unpack_64!(unpack_64_51, 51);
1623unpack_64!(unpack_64_52, 52);
1624unpack_64!(unpack_64_53, 53);
1625unpack_64!(unpack_64_54, 54);
1626unpack_64!(unpack_64_55, 55);
1627unpack_64!(unpack_64_56, 56);
1628unpack_64!(unpack_64_57, 57);
1629unpack_64!(unpack_64_58, 58);
1630unpack_64!(unpack_64_59, 59);
1631unpack_64!(unpack_64_60, 60);
1632unpack_64!(unpack_64_61, 61);
1633unpack_64!(unpack_64_62, 62);
1634unpack_64!(unpack_64_63, 63);
1635unpack_64!(unpack_64_64, 64);
1636
1637macro_rules! pack_64 {
1638    ($name:ident, $bits:expr) => {
1639        fn $name(input: &[u64; 1024], output: &mut [u64; 1024 * $bits / u64::BITS as usize]) {
1640            for lane in 0..u64::LANES {
1641                pack!(u64, $bits, output, lane, |$idx| { input[$idx] });
1642            }
1643        }
1644    };
1645}
1646
1647pack_64!(pack_64_1, 1);
1648pack_64!(pack_64_2, 2);
1649pack_64!(pack_64_3, 3);
1650pack_64!(pack_64_4, 4);
1651pack_64!(pack_64_5, 5);
1652pack_64!(pack_64_6, 6);
1653pack_64!(pack_64_7, 7);
1654pack_64!(pack_64_8, 8);
1655pack_64!(pack_64_9, 9);
1656pack_64!(pack_64_10, 10);
1657pack_64!(pack_64_11, 11);
1658pack_64!(pack_64_12, 12);
1659pack_64!(pack_64_13, 13);
1660pack_64!(pack_64_14, 14);
1661pack_64!(pack_64_15, 15);
1662pack_64!(pack_64_16, 16);
1663pack_64!(pack_64_17, 17);
1664pack_64!(pack_64_18, 18);
1665pack_64!(pack_64_19, 19);
1666pack_64!(pack_64_20, 20);
1667pack_64!(pack_64_21, 21);
1668pack_64!(pack_64_22, 22);
1669pack_64!(pack_64_23, 23);
1670pack_64!(pack_64_24, 24);
1671pack_64!(pack_64_25, 25);
1672pack_64!(pack_64_26, 26);
1673pack_64!(pack_64_27, 27);
1674pack_64!(pack_64_28, 28);
1675pack_64!(pack_64_29, 29);
1676pack_64!(pack_64_30, 30);
1677pack_64!(pack_64_31, 31);
1678pack_64!(pack_64_32, 32);
1679
1680pack_64!(pack_64_33, 33);
1681pack_64!(pack_64_34, 34);
1682pack_64!(pack_64_35, 35);
1683pack_64!(pack_64_36, 36);
1684pack_64!(pack_64_37, 37);
1685pack_64!(pack_64_38, 38);
1686pack_64!(pack_64_39, 39);
1687pack_64!(pack_64_40, 40);
1688pack_64!(pack_64_41, 41);
1689pack_64!(pack_64_42, 42);
1690pack_64!(pack_64_43, 43);
1691pack_64!(pack_64_44, 44);
1692pack_64!(pack_64_45, 45);
1693pack_64!(pack_64_46, 46);
1694pack_64!(pack_64_47, 47);
1695pack_64!(pack_64_48, 48);
1696pack_64!(pack_64_49, 49);
1697pack_64!(pack_64_50, 50);
1698pack_64!(pack_64_51, 51);
1699pack_64!(pack_64_52, 52);
1700pack_64!(pack_64_53, 53);
1701pack_64!(pack_64_54, 54);
1702pack_64!(pack_64_55, 55);
1703pack_64!(pack_64_56, 56);
1704pack_64!(pack_64_57, 57);
1705pack_64!(pack_64_58, 58);
1706pack_64!(pack_64_59, 59);
1707pack_64!(pack_64_60, 60);
1708pack_64!(pack_64_61, 61);
1709pack_64!(pack_64_62, 62);
1710pack_64!(pack_64_63, 63);
1711pack_64!(pack_64_64, 64);
1712
1713#[cfg(test)]
1714mod test {
1715    use super::*;
1716    use bitpacking::{BitPacker as ExternalBitPacker, BitPacker4x as ExternalBitPacker4x};
1717    use core::array;
1718    // a fast random number generator
1719    pub struct XorShift {
1720        state: u64,
1721    }
1722
1723    impl XorShift {
1724        pub fn new(seed: u64) -> Self {
1725            Self { state: seed }
1726        }
1727
1728        pub fn next(&mut self) -> u64 {
1729            let mut x = self.state;
1730            x ^= x << 13;
1731            x ^= x >> 7;
1732            x ^= x << 17;
1733            self.state = x;
1734            x
1735        }
1736    }
1737
1738    fn mask_for_width(width: u8) -> u32 {
1739        match width {
1740            0 => 0,
1741            32 => u32::MAX,
1742            _ => (1u32 << width) - 1,
1743        }
1744    }
1745
1746    fn raw_bitpacker4x_case(width: u8, seed: u64) -> Vec<u32> {
1747        let mask = mask_for_width(width);
1748        let mut rng = XorShift::new(seed);
1749        (0..BitPacker4x::BLOCK_LEN)
1750            .map(|idx| match seed % 4 {
1751                0 => 0,
1752                1 => mask,
1753                2 => idx as u32 & mask,
1754                _ => (rng.next() as u32) & mask,
1755            })
1756            .collect()
1757    }
1758
1759    fn sorted_bitpacker4x_case(width: u8, seed: u64) -> (u32, Vec<u32>) {
1760        if width == 0 {
1761            return (17, vec![17; BitPacker4x::BLOCK_LEN]);
1762        }
1763        if width == 32 {
1764            return (0, vec![u32::MAX; BitPacker4x::BLOCK_LEN]);
1765        }
1766
1767        let mask = mask_for_width(width).min(127);
1768        let mut rng = XorShift::new(seed);
1769        let mut current = 17u32;
1770        let values = (0..BitPacker4x::BLOCK_LEN)
1771            .map(|_| {
1772                current += (rng.next() as u32) & mask;
1773                current
1774            })
1775            .collect();
1776        (17, values)
1777    }
1778
1779    #[test]
1780    fn test_bitpacker4x_raw_compatible_with_external_bitpacking() {
1781        let ours = BitPacker4x::new();
1782        let external = ExternalBitPacker4x::new();
1783
1784        for width in 0..=32 {
1785            for seed in [0, 1, 2, 123456789] {
1786                let values = raw_bitpacker4x_case(width, seed);
1787                assert_eq!(ours.num_bits(&values), external.num_bits(&values));
1788
1789                let mut actual = vec![0u8; BitPacker4x::compressed_block_size(width)];
1790                let actual_len = ours.compress(&values, &mut actual, width);
1791
1792                let mut expected = vec![0u8; ExternalBitPacker4x::compressed_block_size(width)];
1793                let expected_len = external.compress(&values, &mut expected, width);
1794
1795                assert_eq!(actual_len, expected_len);
1796                assert_eq!(actual, expected, "width {width} seed {seed}");
1797
1798                let mut decoded = vec![0u32; BitPacker4x::BLOCK_LEN];
1799                let consumed = ours.decompress(&actual, &mut decoded, width);
1800                assert_eq!(consumed, actual_len);
1801                assert_eq!(decoded, values);
1802            }
1803        }
1804    }
1805
1806    #[test]
1807    fn test_bitpacker4x_sorted_compatible_with_external_bitpacking() {
1808        let ours = BitPacker4x::new();
1809        let external = ExternalBitPacker4x::new();
1810
1811        for width in 0..=32 {
1812            for seed in [0, 1, 2, 123456789] {
1813                let (initial, values) = sorted_bitpacker4x_case(width, seed);
1814                assert_eq!(
1815                    ours.num_bits_sorted(initial, &values),
1816                    external.num_bits_sorted(initial, &values)
1817                );
1818
1819                let mut actual = vec![0u8; BitPacker4x::compressed_block_size(width)];
1820                let actual_len = ours.compress_sorted(initial, &values, &mut actual, width);
1821
1822                let mut expected = vec![0u8; ExternalBitPacker4x::compressed_block_size(width)];
1823                let expected_len = external.compress_sorted(initial, &values, &mut expected, width);
1824
1825                assert_eq!(actual_len, expected_len);
1826                assert_eq!(actual, expected, "width {width} seed {seed}");
1827
1828                let mut decoded = vec![0u32; BitPacker4x::BLOCK_LEN];
1829                let consumed = ours.decompress_sorted(initial, &actual, &mut decoded, width);
1830                assert_eq!(consumed, actual_len);
1831                assert_eq!(decoded, values);
1832            }
1833        }
1834    }
1835
1836    // a macro version of this function generalize u8, u16, u32, u64 takes very long time for a test build, so I
1837    // write it for each type separately
1838    fn pack_unpack_u8(bit_width: usize) {
1839        let mut values: [u8; 1024] = [0; 1024];
1840        let mut rng = XorShift::new(123456789);
1841        for value in &mut values {
1842            *value = (rng.next() % (1 << bit_width)) as u8;
1843        }
1844
1845        let mut packed = vec![0; 1024 * bit_width / 8];
1846        for lane in 0..u8::LANES {
1847            // Always loop over lanes first. This is what the compiler vectorizes.
1848            pack!(u8, bit_width, packed, lane, |$pos| {
1849                values[$pos]
1850            });
1851        }
1852
1853        let mut unpacked: [u8; 1024] = [0; 1024];
1854        for lane in 0..u8::LANES {
1855            // Always loop over lanes first. This is what the compiler vectorizes.
1856            unpack!(u8, bit_width, packed, lane, |$idx, $elem| {
1857                unpacked[$idx] = $elem;
1858            });
1859        }
1860
1861        assert_eq!(values, unpacked);
1862    }
1863
1864    fn pack_unpack_u16(bit_width: usize) {
1865        let mut values: [u16; 1024] = [0; 1024];
1866        let mut rng = XorShift::new(123456789);
1867        for value in &mut values {
1868            *value = (rng.next() % (1 << bit_width)) as u16;
1869        }
1870
1871        let mut packed = vec![0; 1024 * bit_width / 16];
1872        for lane in 0..u16::LANES {
1873            // Always loop over lanes first. This is what the compiler vectorizes.
1874            pack!(u16, bit_width, packed, lane, |$pos| {
1875                values[$pos]
1876            });
1877        }
1878
1879        let mut unpacked: [u16; 1024] = [0; 1024];
1880        for lane in 0..u16::LANES {
1881            // Always loop over lanes first. This is what the compiler vectorizes.
1882            unpack!(u16, bit_width, packed, lane, |$idx, $elem| {
1883                unpacked[$idx] = $elem;
1884            });
1885        }
1886
1887        assert_eq!(values, unpacked);
1888    }
1889
1890    fn pack_unpack_u32(bit_width: usize) {
1891        let mut values: [u32; 1024] = [0; 1024];
1892        let mut rng = XorShift::new(123456789);
1893        for value in &mut values {
1894            *value = (rng.next() % (1 << bit_width)) as u32;
1895        }
1896
1897        let mut packed = vec![0; 1024 * bit_width / 32];
1898        for lane in 0..u32::LANES {
1899            // Always loop over lanes first. This is what the compiler vectorizes.
1900            pack!(u32, bit_width, packed, lane, |$pos| {
1901                values[$pos]
1902            });
1903        }
1904
1905        let mut unpacked: [u32; 1024] = [0; 1024];
1906        for lane in 0..u32::LANES {
1907            // Always loop over lanes first. This is what the compiler vectorizes.
1908            unpack!(u32, bit_width, packed, lane, |$idx, $elem| {
1909                unpacked[$idx] = $elem;
1910            });
1911        }
1912
1913        assert_eq!(values, unpacked);
1914    }
1915
1916    fn pack_unpack_u64(bit_width: usize) {
1917        let mut values: [u64; 1024] = [0; 1024];
1918        let mut rng = XorShift::new(123456789);
1919        if bit_width == 64 {
1920            for value in &mut values {
1921                *value = rng.next();
1922            }
1923        } else {
1924            for value in &mut values {
1925                *value = rng.next() % (1 << bit_width);
1926            }
1927        }
1928
1929        let mut packed = vec![0; 1024 * bit_width / 64];
1930        for lane in 0..u64::LANES {
1931            // Always loop over lanes first. This is what the compiler vectorizes.
1932            pack!(u64, bit_width, packed, lane, |$pos| {
1933                values[$pos]
1934            });
1935        }
1936
1937        let mut unpacked: [u64; 1024] = [0; 1024];
1938        for lane in 0..u64::LANES {
1939            // Always loop over lanes first. This is what the compiler vectorizes.
1940            unpack!(u64, bit_width, packed, lane, |$idx, $elem| {
1941                unpacked[$idx] = $elem;
1942            });
1943        }
1944
1945        assert_eq!(values, unpacked);
1946    }
1947
1948    #[test]
1949    fn test_pack() {
1950        pack_unpack_u8(0);
1951        pack_unpack_u8(1);
1952        pack_unpack_u8(2);
1953        pack_unpack_u8(3);
1954        pack_unpack_u8(4);
1955        pack_unpack_u8(5);
1956        pack_unpack_u8(6);
1957        pack_unpack_u8(7);
1958        pack_unpack_u8(8);
1959
1960        pack_unpack_u16(0);
1961        pack_unpack_u16(1);
1962        pack_unpack_u16(2);
1963        pack_unpack_u16(3);
1964        pack_unpack_u16(4);
1965        pack_unpack_u16(5);
1966        pack_unpack_u16(6);
1967        pack_unpack_u16(7);
1968        pack_unpack_u16(8);
1969        pack_unpack_u16(9);
1970        pack_unpack_u16(10);
1971        pack_unpack_u16(11);
1972        pack_unpack_u16(12);
1973        pack_unpack_u16(13);
1974        pack_unpack_u16(14);
1975        pack_unpack_u16(15);
1976        pack_unpack_u16(16);
1977
1978        pack_unpack_u32(0);
1979        pack_unpack_u32(1);
1980        pack_unpack_u32(2);
1981        pack_unpack_u32(3);
1982        pack_unpack_u32(4);
1983        pack_unpack_u32(5);
1984        pack_unpack_u32(6);
1985        pack_unpack_u32(7);
1986        pack_unpack_u32(8);
1987        pack_unpack_u32(9);
1988        pack_unpack_u32(10);
1989        pack_unpack_u32(11);
1990        pack_unpack_u32(12);
1991        pack_unpack_u32(13);
1992        pack_unpack_u32(14);
1993        pack_unpack_u32(15);
1994        pack_unpack_u32(16);
1995        pack_unpack_u32(17);
1996        pack_unpack_u32(18);
1997        pack_unpack_u32(19);
1998        pack_unpack_u32(20);
1999        pack_unpack_u32(21);
2000        pack_unpack_u32(22);
2001        pack_unpack_u32(23);
2002        pack_unpack_u32(24);
2003        pack_unpack_u32(25);
2004        pack_unpack_u32(26);
2005        pack_unpack_u32(27);
2006        pack_unpack_u32(28);
2007        pack_unpack_u32(29);
2008        pack_unpack_u32(30);
2009        pack_unpack_u32(31);
2010        pack_unpack_u32(32);
2011
2012        pack_unpack_u64(0);
2013        pack_unpack_u64(1);
2014        pack_unpack_u64(2);
2015        pack_unpack_u64(3);
2016        pack_unpack_u64(4);
2017        pack_unpack_u64(5);
2018        pack_unpack_u64(6);
2019        pack_unpack_u64(7);
2020        pack_unpack_u64(8);
2021        pack_unpack_u64(9);
2022        pack_unpack_u64(10);
2023        pack_unpack_u64(11);
2024        pack_unpack_u64(12);
2025        pack_unpack_u64(13);
2026        pack_unpack_u64(14);
2027        pack_unpack_u64(15);
2028        pack_unpack_u64(16);
2029        pack_unpack_u64(17);
2030        pack_unpack_u64(18);
2031        pack_unpack_u64(19);
2032        pack_unpack_u64(20);
2033        pack_unpack_u64(21);
2034        pack_unpack_u64(22);
2035        pack_unpack_u64(23);
2036        pack_unpack_u64(24);
2037        pack_unpack_u64(25);
2038        pack_unpack_u64(26);
2039        pack_unpack_u64(27);
2040        pack_unpack_u64(28);
2041        pack_unpack_u64(29);
2042        pack_unpack_u64(30);
2043        pack_unpack_u64(31);
2044        pack_unpack_u64(32);
2045        pack_unpack_u64(33);
2046        pack_unpack_u64(34);
2047        pack_unpack_u64(35);
2048        pack_unpack_u64(36);
2049        pack_unpack_u64(37);
2050        pack_unpack_u64(38);
2051        pack_unpack_u64(39);
2052        pack_unpack_u64(40);
2053        pack_unpack_u64(41);
2054        pack_unpack_u64(42);
2055        pack_unpack_u64(43);
2056        pack_unpack_u64(44);
2057        pack_unpack_u64(45);
2058        pack_unpack_u64(46);
2059        pack_unpack_u64(47);
2060        pack_unpack_u64(48);
2061        pack_unpack_u64(49);
2062        pack_unpack_u64(50);
2063        pack_unpack_u64(51);
2064        pack_unpack_u64(52);
2065        pack_unpack_u64(53);
2066        pack_unpack_u64(54);
2067        pack_unpack_u64(55);
2068        pack_unpack_u64(56);
2069        pack_unpack_u64(57);
2070        pack_unpack_u64(58);
2071        pack_unpack_u64(59);
2072        pack_unpack_u64(60);
2073        pack_unpack_u64(61);
2074        pack_unpack_u64(62);
2075        pack_unpack_u64(63);
2076        pack_unpack_u64(64);
2077    }
2078
2079    fn unchecked_pack_unpack_u8(bit_width: usize) {
2080        let mut values = [0u8; 1024];
2081        let mut rng = XorShift::new(123456789);
2082        for value in &mut values {
2083            *value = (rng.next() % (1 << bit_width)) as u8;
2084        }
2085        let mut packed = vec![0; 1024 * bit_width / 8];
2086        unsafe {
2087            BitPacking::unchecked_pack(bit_width, &values, &mut packed);
2088        }
2089        let mut output = [0; 1024];
2090        unsafe { BitPacking::unchecked_unpack(bit_width, &packed, &mut output) };
2091        assert_eq!(values, output);
2092    }
2093
2094    fn unchecked_pack_unpack_u16(bit_width: usize) {
2095        let mut values = [0u16; 1024];
2096        let mut rng = XorShift::new(123456789);
2097        for value in &mut values {
2098            *value = (rng.next() % (1 << bit_width)) as u16;
2099        }
2100        let mut packed = vec![0; 1024 * bit_width / u16::T];
2101        unsafe {
2102            BitPacking::unchecked_pack(bit_width, &values, &mut packed);
2103        }
2104        let mut output = [0; 1024];
2105        unsafe { BitPacking::unchecked_unpack(bit_width, &packed, &mut output) };
2106        assert_eq!(values, output);
2107    }
2108
2109    fn unchecked_pack_unpack_u32(bit_width: usize) {
2110        let mut values = [0u32; 1024];
2111        let mut rng = XorShift::new(123456789);
2112        for value in &mut values {
2113            *value = (rng.next() % (1 << bit_width)) as u32;
2114        }
2115        let mut packed = vec![0; 1024 * bit_width / u32::T];
2116        unsafe {
2117            BitPacking::unchecked_pack(bit_width, &values, &mut packed);
2118        }
2119        let mut output = [0; 1024];
2120        unsafe { BitPacking::unchecked_unpack(bit_width, &packed, &mut output) };
2121        assert_eq!(values, output);
2122    }
2123
2124    fn unchecked_pack_unpack_u64(bit_width: usize) {
2125        let mut values = [0u64; 1024];
2126        let mut rng = XorShift::new(123456789);
2127        if bit_width == 64 {
2128            for value in &mut values {
2129                *value = rng.next();
2130            }
2131        } else {
2132            for value in &mut values {
2133                *value = rng.next() % (1 << bit_width);
2134            }
2135        }
2136        let mut packed = vec![0; 1024 * bit_width / u64::T];
2137        unsafe {
2138            BitPacking::unchecked_pack(bit_width, &values, &mut packed);
2139        }
2140        let mut output = [0; 1024];
2141        unsafe { BitPacking::unchecked_unpack(bit_width, &packed, &mut output) };
2142        assert_eq!(values, output);
2143    }
2144
2145    #[test]
2146    fn test_unchecked_pack() {
2147        let input = array::from_fn(|i| i as u32);
2148        let mut packed = [0; 320];
2149        unsafe { BitPacking::unchecked_pack(10, &input, &mut packed) };
2150        let mut output = [0; 1024];
2151        unsafe { BitPacking::unchecked_unpack(10, &packed, &mut output) };
2152        assert_eq!(input, output);
2153
2154        unchecked_pack_unpack_u8(1);
2155        unchecked_pack_unpack_u8(2);
2156        unchecked_pack_unpack_u8(3);
2157        unchecked_pack_unpack_u8(4);
2158        unchecked_pack_unpack_u8(5);
2159        unchecked_pack_unpack_u8(6);
2160        unchecked_pack_unpack_u8(7);
2161        unchecked_pack_unpack_u8(8);
2162
2163        unchecked_pack_unpack_u16(1);
2164        unchecked_pack_unpack_u16(2);
2165        unchecked_pack_unpack_u16(3);
2166        unchecked_pack_unpack_u16(4);
2167        unchecked_pack_unpack_u16(5);
2168        unchecked_pack_unpack_u16(6);
2169        unchecked_pack_unpack_u16(7);
2170        unchecked_pack_unpack_u16(8);
2171        unchecked_pack_unpack_u16(9);
2172        unchecked_pack_unpack_u16(10);
2173        unchecked_pack_unpack_u16(11);
2174        unchecked_pack_unpack_u16(12);
2175        unchecked_pack_unpack_u16(13);
2176        unchecked_pack_unpack_u16(14);
2177        unchecked_pack_unpack_u16(15);
2178        unchecked_pack_unpack_u16(16);
2179
2180        unchecked_pack_unpack_u32(1);
2181        unchecked_pack_unpack_u32(2);
2182        unchecked_pack_unpack_u32(3);
2183        unchecked_pack_unpack_u32(4);
2184        unchecked_pack_unpack_u32(5);
2185        unchecked_pack_unpack_u32(6);
2186        unchecked_pack_unpack_u32(7);
2187        unchecked_pack_unpack_u32(8);
2188        unchecked_pack_unpack_u32(9);
2189        unchecked_pack_unpack_u32(10);
2190        unchecked_pack_unpack_u32(11);
2191        unchecked_pack_unpack_u32(12);
2192        unchecked_pack_unpack_u32(13);
2193        unchecked_pack_unpack_u32(14);
2194        unchecked_pack_unpack_u32(15);
2195        unchecked_pack_unpack_u32(16);
2196        unchecked_pack_unpack_u32(17);
2197        unchecked_pack_unpack_u32(18);
2198        unchecked_pack_unpack_u32(19);
2199        unchecked_pack_unpack_u32(20);
2200        unchecked_pack_unpack_u32(21);
2201        unchecked_pack_unpack_u32(22);
2202        unchecked_pack_unpack_u32(23);
2203        unchecked_pack_unpack_u32(24);
2204        unchecked_pack_unpack_u32(25);
2205        unchecked_pack_unpack_u32(26);
2206        unchecked_pack_unpack_u32(27);
2207        unchecked_pack_unpack_u32(28);
2208        unchecked_pack_unpack_u32(29);
2209        unchecked_pack_unpack_u32(30);
2210        unchecked_pack_unpack_u32(31);
2211        unchecked_pack_unpack_u32(32);
2212
2213        unchecked_pack_unpack_u64(1);
2214        unchecked_pack_unpack_u64(2);
2215        unchecked_pack_unpack_u64(3);
2216        unchecked_pack_unpack_u64(4);
2217        unchecked_pack_unpack_u64(5);
2218        unchecked_pack_unpack_u64(6);
2219        unchecked_pack_unpack_u64(7);
2220        unchecked_pack_unpack_u64(8);
2221        unchecked_pack_unpack_u64(9);
2222        unchecked_pack_unpack_u64(10);
2223        unchecked_pack_unpack_u64(11);
2224        unchecked_pack_unpack_u64(12);
2225        unchecked_pack_unpack_u64(13);
2226        unchecked_pack_unpack_u64(14);
2227        unchecked_pack_unpack_u64(15);
2228        unchecked_pack_unpack_u64(16);
2229        unchecked_pack_unpack_u64(17);
2230        unchecked_pack_unpack_u64(18);
2231        unchecked_pack_unpack_u64(19);
2232        unchecked_pack_unpack_u64(20);
2233        unchecked_pack_unpack_u64(21);
2234        unchecked_pack_unpack_u64(22);
2235        unchecked_pack_unpack_u64(23);
2236        unchecked_pack_unpack_u64(24);
2237        unchecked_pack_unpack_u64(25);
2238        unchecked_pack_unpack_u64(26);
2239        unchecked_pack_unpack_u64(27);
2240        unchecked_pack_unpack_u64(28);
2241        unchecked_pack_unpack_u64(29);
2242        unchecked_pack_unpack_u64(30);
2243        unchecked_pack_unpack_u64(31);
2244        unchecked_pack_unpack_u64(32);
2245        unchecked_pack_unpack_u64(33);
2246        unchecked_pack_unpack_u64(34);
2247        unchecked_pack_unpack_u64(35);
2248        unchecked_pack_unpack_u64(36);
2249        unchecked_pack_unpack_u64(37);
2250        unchecked_pack_unpack_u64(38);
2251        unchecked_pack_unpack_u64(39);
2252        unchecked_pack_unpack_u64(40);
2253        unchecked_pack_unpack_u64(41);
2254        unchecked_pack_unpack_u64(42);
2255        unchecked_pack_unpack_u64(43);
2256        unchecked_pack_unpack_u64(44);
2257        unchecked_pack_unpack_u64(45);
2258        unchecked_pack_unpack_u64(46);
2259        unchecked_pack_unpack_u64(47);
2260        unchecked_pack_unpack_u64(48);
2261        unchecked_pack_unpack_u64(49);
2262        unchecked_pack_unpack_u64(50);
2263        unchecked_pack_unpack_u64(51);
2264        unchecked_pack_unpack_u64(52);
2265        unchecked_pack_unpack_u64(53);
2266        unchecked_pack_unpack_u64(54);
2267        unchecked_pack_unpack_u64(55);
2268        unchecked_pack_unpack_u64(56);
2269        unchecked_pack_unpack_u64(57);
2270        unchecked_pack_unpack_u64(58);
2271        unchecked_pack_unpack_u64(59);
2272        unchecked_pack_unpack_u64(60);
2273        unchecked_pack_unpack_u64(61);
2274        unchecked_pack_unpack_u64(62);
2275        unchecked_pack_unpack_u64(63);
2276        unchecked_pack_unpack_u64(64);
2277    }
2278}