Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

3 files changed, 241 insertions, 0 deletions

diff --git a/vendor/odht/src/swisstable_group_query/mod.rs b/vendor/odht/src/swisstable_group_query/mod.rs
new file mode 100644
index 000000000..ed7f5f71f
--- /dev/null
+++ b/vendor/odht/src/swisstable_group_query/mod.rs
@@ -0,0 +1,117 @@
+cfg_if::cfg_if! {
+    if #[cfg(all(
+        target_feature = "sse2",
+        any(target_arch = "x86", target_arch = "x86_64"),
+        not(miri),
+        not(feature = "no_simd"),
+    ))] {
+        mod sse2;
+        use sse2 as imp;
+    } else {
+        mod no_simd;
+        use no_simd as imp;
+    }
+}
+
+pub use imp::GroupQuery;
+pub use imp::GROUP_SIZE;
+
+// While GROUP_SIZE is target-dependent for performance reasons,
+// we always do probing as if it was the same as REFERENCE_GROUP_SIZE.
+// This way the same slot indices will be assigned to the same
+// entries no matter the underlying target. This allows the
+// binary format of the table to be portable.
+pub const REFERENCE_GROUP_SIZE: usize = 16;
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    const EMPTY_GROUP: [u8; GROUP_SIZE] = [255; GROUP_SIZE];
+
+    fn full_group() -> [u8; GROUP_SIZE] {
+        let mut group = [0; GROUP_SIZE];
+        for i in 0..group.len() {
+            group[i] = i as u8;
+        }
+        group
+    }
+
+    #[test]
+    fn full() {
+        let mut q = GroupQuery::from(&full_group(), 42);
+
+        assert_eq!(Iterator::count(&mut q), 0);
+        assert!(!q.any_empty());
+        assert_eq!(q.first_empty(), None);
+    }
+
+    #[test]
+    fn all_empty() {
+        let mut q = GroupQuery::from(&EMPTY_GROUP, 31);
+
+        assert_eq!(Iterator::count(&mut q), 0);
+        assert!(q.any_empty());
+        assert_eq!(q.first_empty(), Some(0));
+    }
+
+    #[test]
+    fn partially_filled() {
+        for filled_up_to_index in 0..=(GROUP_SIZE - 2) {
+            let mut group = EMPTY_GROUP;
+
+            for i in 0..=filled_up_to_index {
+                group[i] = 42;
+            }
+
+            let mut q = GroupQuery::from(&group, 77);
+
+            assert_eq!(Iterator::count(&mut q), 0);
+            assert!(q.any_empty());
+            assert_eq!(q.first_empty(), Some(filled_up_to_index + 1));
+        }
+    }
+
+    #[test]
+    fn match_iter() {
+        let expected: Vec<_> = (0..GROUP_SIZE).filter(|x| x % 3 == 0).collect();
+
+        let mut group = full_group();
+
+        for i in &expected {
+            group[*i] = 103;
+        }
+
+        let mut q = GroupQuery::from(&group, 103);
+
+        let matches: Vec<usize> = (&mut q).collect();
+
+        assert_eq!(matches, expected);
+        assert!(!q.any_empty());
+        assert_eq!(q.first_empty(), None);
+    }
+
+    #[test]
+    fn match_iter_with_empty() {
+        let expected: Vec<_> = (0..GROUP_SIZE).filter(|x| x % 3 == 2).collect();
+
+        let mut group = full_group();
+
+        for i in &expected {
+            group[*i] = 99;
+        }
+
+        // Clear a few slots
+        group[3] = 255;
+        group[4] = 255;
+        group[GROUP_SIZE - 1] = 255;
+
+        let mut q = GroupQuery::from(&group, 99);
+
+        let matches: Vec<usize> = (&mut q).collect();
+
+        assert_eq!(matches, expected);
+        assert!(q.any_empty());
+        assert_eq!(q.first_empty(), Some(3));
+    }
+}
diff --git a/vendor/odht/src/swisstable_group_query/no_simd.rs b/vendor/odht/src/swisstable_group_query/no_simd.rs
new file mode 100644
index 000000000..81898fe47
--- /dev/null
+++ b/vendor/odht/src/swisstable_group_query/no_simd.rs
@@ -0,0 +1,70 @@
+use std::num::NonZeroU64;
+
+pub const GROUP_SIZE: usize = 8;
+
+type GroupWord = u64;
+type NonZeroGroupWord = NonZeroU64;
+
+pub struct GroupQuery {
+    eq_mask: GroupWord,
+    empty_mask: GroupWord,
+}
+
+#[inline]
+fn repeat(byte: u8) -> GroupWord {
+    GroupWord::from_ne_bytes([byte; GROUP_SIZE])
+}
+
+impl GroupQuery {
+    #[inline]
+    pub fn from(group: &[u8; GROUP_SIZE], h2: u8) -> GroupQuery {
+        // Adapted from this gem:
+        // https://github.com/rust-lang/hashbrown/blob/bbb5d3bb1c23569c15e54c670bc0c3669ae3e7dc/src/raw/generic.rs#L93-L109
+        // which in turn is based on
+        // http://graphics.stanford.edu/~seander/bithacks.html##ValueInWord
+        //
+        // Note the mask generated by the code below can contain false
+        // positives. But we don't care because it's rare and we need
+        // to compare keys anyway. In other words, a false positive here
+        // has pretty much the same effect as a hash collision, something
+        // that we need to deal with in any case anyway.
+
+        let group = GroupWord::from_le_bytes(*group);
+        let cmp = group ^ repeat(h2);
+        let high_bit_greater_than_128 = (!cmp) & repeat(0x80);
+        let high_bit_greater_than_128_or_zero = cmp.wrapping_sub(repeat(0x01));
+        let eq_mask = high_bit_greater_than_128_or_zero & high_bit_greater_than_128;
+
+        let empty_mask = group & repeat(0x80);
+
+        GroupQuery {
+            eq_mask,
+            empty_mask,
+        }
+    }
+
+    #[inline]
+    pub fn any_empty(&self) -> bool {
+        self.empty_mask != 0
+    }
+
+    #[inline]
+    pub fn first_empty(&self) -> Option<usize> {
+        Some((NonZeroGroupWord::new(self.empty_mask)?.trailing_zeros() / 8) as usize)
+    }
+}
+
+impl Iterator for GroupQuery {
+    type Item = usize;
+
+    #[inline]
+    fn next(&mut self) -> Option<usize> {
+        let index = NonZeroGroupWord::new(self.eq_mask)?.trailing_zeros() / 8;
+
+        // Clear the lowest bit
+        // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
+        self.eq_mask &= self.eq_mask - 1;
+
+        Some(index as usize)
+    }
+}
diff --git a/vendor/odht/src/swisstable_group_query/sse2.rs b/vendor/odht/src/swisstable_group_query/sse2.rs
new file mode 100644
index 000000000..89e41aa19
--- /dev/null
+++ b/vendor/odht/src/swisstable_group_query/sse2.rs
@@ -0,0 +1,54 @@
+use core::num::NonZeroU16;
+
+#[cfg(target_arch = "x86")]
+use core::arch::x86;
+#[cfg(target_arch = "x86_64")]
+use core::arch::x86_64 as x86;
+
+pub const GROUP_SIZE: usize = 16;
+
+pub struct GroupQuery {
+    matches: u16,
+    empty: u16,
+}
+
+impl GroupQuery {
+    #[inline]
+    pub fn from(group: &[u8; GROUP_SIZE], h2: u8) -> GroupQuery {
+        assert!(std::mem::size_of::<x86::__m128i>() == GROUP_SIZE);
+
+        unsafe {
+            let group = x86::_mm_loadu_si128(group as *const _ as *const x86::__m128i);
+            let cmp_byte = x86::_mm_cmpeq_epi8(group, x86::_mm_set1_epi8(h2 as i8));
+            let matches = x86::_mm_movemask_epi8(cmp_byte) as u16;
+            let empty = x86::_mm_movemask_epi8(group) as u16;
+
+            GroupQuery { matches, empty }
+        }
+    }
+
+    #[inline]
+    pub fn any_empty(&self) -> bool {
+        self.empty != 0
+    }
+
+    #[inline]
+    pub fn first_empty(&self) -> Option<usize> {
+        Some(NonZeroU16::new(self.empty)?.trailing_zeros() as usize)
+    }
+}
+
+impl Iterator for GroupQuery {
+    type Item = usize;
+
+    #[inline]
+    fn next(&mut self) -> Option<usize> {
+        let index = NonZeroU16::new(self.matches)?.trailing_zeros();
+
+        // Clear the lowest bit
+        // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
+        self.matches &= self.matches - 1;
+
+        Some(index as usize)
+    }
+}