lthash_rs/
lthash16.rs

1use std::marker::PhantomData;
2
3use digest::ExtendableOutput;
4
5use crate::{
6    utils::{into_bytes, read_u16, HexDisplayRef16},
7    LtHash,
8};
9
10/// A LtHash checksum with 16 bits per chunk and 1024 chunks.
11#[derive(Clone, Copy)]
12pub struct LtHash16<H> {
13    pub(crate) checksum: [u16; 1024],
14    hasher: PhantomData<H>,
15}
16
17// Ensure we don't accidentally remove Send/Sync, since LtHash16 should be Send/Sync.
18static_assertions::assert_impl_all!(LtHash16<()>: Send, Sync, Unpin);
19
20impl<H> LtHash16<H> {
21    pub(crate) const fn name(&self) -> &'static str {
22        "LtHash16"
23    }
24}
25
26impl<H> LtHash16<H>
27where
28    H: ExtendableOutput + Default,
29{
30    #[inline(always)]
31    pub fn new() -> Self {
32        Self::default()
33    }
34
35    fn hash_object(&mut self, object: impl AsRef<[u8]>) -> [u8; 2048] {
36        let mut output = [0u8; 2048];
37        H::digest_xof(object, output.as_mut());
38        output
39    }
40
41    #[inline(always)]
42    fn display_hex_ref(&self) -> HexDisplayRef16<'_> {
43        HexDisplayRef16(&self.checksum[..])
44    }
45}
46
47impl<H> Default for LtHash16<H>
48where
49    H: ExtendableOutput + Default,
50{
51    #[inline(always)]
52    fn default() -> Self {
53        Self {
54            checksum: [0; 1024],
55            hasher: Default::default(),
56        }
57    }
58}
59
60impl<H> LtHash for LtHash16<H>
61where
62    H: ExtendableOutput + Default,
63{
64    /// Inserts an element to LtHash, actually it generates the hash (of size 2048 bytes) of the object and sums it to the checksum.
65    fn insert(&mut self, element: impl AsRef<[u8]>) {
66        let hashed = self.hash_object(element);
67        let mut i = 0;
68        while i < 2048 {
69            let xi = &self.checksum[i / 2];
70            let yi = &hashed[i..i + 2];
71            let yi = read_u16(yi);
72            let sum = xi.wrapping_add(yi);
73            self.checksum[i / 2] = sum;
74            i += 2;
75        }
76    }
77
78    /// Removes an element to LtHash, actually it generates the hash (of size 2048 bytes) of the object and removes it from the checksum.
79    fn remove(&mut self, element: impl AsRef<[u8]>) {
80        let hashed = self.hash_object(element);
81        let mut i = 0;
82        while i < 2048 {
83            let xi = &self.checksum[i / 2];
84            let yi = &hashed[i..i + 2];
85            let yi = read_u16(yi);
86            let diff = xi.wrapping_sub(yi);
87            self.checksum[i / 2] = diff;
88            i += 2;
89        }
90    }
91
92    /// Provides the hex value as String of the checksum.
93    fn to_hex_string(&self) -> String {
94        self.display_hex_ref().to_string()
95    }
96
97    /// Takes the union of `self` and `rhs`
98    ///
99    /// Equivalent to cloning `self`, then adding all the objects in `rhs`.
100    ///
101    /// Equivalent to `self | other`
102    ///
103    /// # Examples
104    /// ```
105    /// # use lthash_rs::LtHash;
106    /// # use lthash_rs::LtHash16;
107    /// # use sha3::Shake256;
108    /// # use std::iter::FromIterator;
109    /// let mut left = LtHash16::<Shake256>::new();
110    /// left.insert("hello");
111    ///
112    /// let mut right = LtHash16::<Shake256>::new();
113    /// right.insert("world");
114    ///
115    /// assert_eq!(left.union(&right), LtHash16::<Shake256>::from_iter(&["hello", "world"]));
116    /// ```
117    fn union(&self, rhs: &Self) -> Self {
118        let mut checksum = [0; 1024];
119
120        for (checksum, (&lhs, &rhs)) in checksum
121            .iter_mut()
122            .zip(self.checksum.iter().zip(rhs.checksum.iter()))
123        {
124            *checksum = lhs.wrapping_add(rhs);
125        }
126
127        Self {
128            checksum,
129            hasher: PhantomData,
130        }
131    }
132
133    /// Takes the difference of `self` and `rhs`.
134    ///
135    /// Equivalent to cloning `self`, then removing all the objects in `rhs`.
136    ///
137    /// Equivalent to `self - other`
138    ///
139    /// # Examples
140    /// ```
141    /// # use lthash_rs::LtHash;
142    /// # use lthash_rs::LtHash16;
143    /// # use sha3::Shake256;
144    /// # use std::iter::FromIterator;
145    /// let mut left = LtHash16::<Shake256>::new();
146    /// left.extend(&["hello", "world"]);
147    ///
148    /// let mut right = LtHash16::<Shake256>::new();
149    /// right.insert("hello");
150    ///
151    /// assert_eq!(left.difference(&right), LtHash16::from_iter(&["world"]));
152    /// ```
153    fn difference(&self, rhs: &Self) -> Self {
154        let mut checksum = [0; 1024];
155
156        for (checksum, (&lhs, &rhs)) in checksum
157            .iter_mut()
158            .zip(self.checksum.iter().zip(rhs.checksum.iter()))
159        {
160            *checksum = lhs.wrapping_sub(rhs);
161        }
162
163        Self {
164            checksum,
165            hasher: PhantomData,
166        }
167    }
168
169    /// Clears the internal checksum
170    fn reset(&mut self) {
171        self.checksum.fill(0);
172    }
173
174    /// Converts self into the inner list of bytes
175    fn into_bytes(self) -> Vec<u8> {
176        into_bytes(self.checksum)
177    }
178}
179
180impl<H> TryFrom<&[u8]> for LtHash16<H> {
181    type Error = String;
182
183    fn try_from(bytes: &[u8]) -> Result<Self, Self::Error> {
184        if bytes.len() != 2048 {
185            return Err(String::from("Wrong number of bytes."));
186        }
187
188        let mut checksum = [0; 1024];
189
190        for (checksum, bytes) in checksum.iter_mut().zip(bytes.chunks_exact(2))
191        {
192            *checksum =
193                u16::from_le_bytes(bytes.try_into().map_err(|_| {
194                    String::from("Error converting bytes to u16.")
195                })?);
196        }
197
198        Ok(Self {
199            checksum,
200            hasher: PhantomData,
201        })
202    }
203}
lthash_rs/lthash16.rs

lthash_rs/
lthash16.rs
