1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
//! SipHash 的实现。

#![allow(deprecated)] // 不建议使用此模块中的类型

use crate::cmp;
use crate::marker::PhantomData;
use crate::mem;
use crate::ptr;

/// SipHash 1-3 的实现。
///
/// 当前,这是标准库使用的默认哈希函数 (例如,`collections::HashMap` 默认使用它)。
///
///
/// See: <https://131002.net/siphash>
#[unstable(feature = "hashmap_internals", issue = "none")]
#[rustc_deprecated(
    since = "1.13.0",
    reason = "use `std::collections::hash_map::DefaultHasher` instead"
)]
#[derive(Debug, Clone, Default)]
#[doc(hidden)]
pub struct SipHasher13 {
    hasher: Hasher<Sip13Rounds>,
}

/// SipHash 2-4 的实现。
///
/// See: <https://131002.net/siphash/>
#[unstable(feature = "hashmap_internals", issue = "none")]
#[rustc_deprecated(
    since = "1.13.0",
    reason = "use `std::collections::hash_map::DefaultHasher` instead"
)]
#[derive(Debug, Clone, Default)]
struct SipHasher24 {
    hasher: Hasher<Sip24Rounds>,
}

/// SipHash 2-4 的实现。
///
/// See: <https://131002.net/siphash/>
///
/// SipHash 是通用的哈希函数: 它以良好的速度运行 (与 Spooky 和 City 竞争),并允许强大的 _keyed_ 哈希。
///
/// 这使您可以从强大的 RNG (例如 [`rand::os::OsRng`](https://doc.rust-lang.org/rand/rand/os/struct.OsRng.html)) 中键入哈希表。
///
/// 尽管 SipHash 算法通常被认为是强大的,但它并非旨在用于加密目的。
/// 这样,此实现的所有加密用途都是 _strongly discouraged_。
///
///
#[stable(feature = "rust1", since = "1.0.0")]
#[rustc_deprecated(
    since = "1.13.0",
    reason = "use `std::collections::hash_map::DefaultHasher` instead"
)]
#[derive(Debug, Clone, Default)]
pub struct SipHasher(SipHasher24);

#[derive(Debug)]
struct Hasher<S: Sip> {
    k0: u64,
    k1: u64,
    length: usize, // 我们处理了多少字节
    state: State,  // 哈希状态
    tail: u64,     // 未处理的字节
    ntail: usize,  // 尾部有多少字节有效
    _marker: PhantomData<S>,
}

#[derive(Debug, Clone, Copy)]
#[repr(C)]
struct State {
    // v0, v2 和 v1,v3 在算法中成对出现,SipHash 的 simd 实现将使用 v02 和 v13 的 vectors。
    //
    // 通过将它们以这种顺序放置在结构体中,编译器本身可以进行一些 simd 优化。
    //
    v0: u64,
    v2: u64,
    v1: u64,
    v3: u64,
}

macro_rules! compress {
    ($state:expr) => {{ compress!($state.v0, $state.v1, $state.v2, $state.v3) }};
    ($v0:expr, $v1:expr, $v2:expr, $v3:expr) => {{
        $v0 = $v0.wrapping_add($v1);
        $v1 = $v1.rotate_left(13);
        $v1 ^= $v0;
        $v0 = $v0.rotate_left(32);
        $v2 = $v2.wrapping_add($v3);
        $v3 = $v3.rotate_left(16);
        $v3 ^= $v2;
        $v0 = $v0.wrapping_add($v3);
        $v3 = $v3.rotate_left(21);
        $v3 ^= $v0;
        $v2 = $v2.wrapping_add($v1);
        $v1 = $v1.rotate_left(17);
        $v1 ^= $v2;
        $v2 = $v2.rotate_left(32);
    }};
}

/// 以 LE 顺序从字节流中加载所需类型的整数。
/// 使用 `copy_nonoverlapping` 使编译器生成最有效的方法来从可能未对齐的地址加载它。
///
///
/// 不安全,因为: 未经检查的索引在 i..i + size_of (int_ty)
macro_rules! load_int_le {
    ($buf:expr, $i:expr, $int_ty:ident) => {{
        debug_assert!($i + mem::size_of::<$int_ty>() <= $buf.len());
        let mut data = 0 as $int_ty;
        ptr::copy_nonoverlapping(
            $buf.as_ptr().add($i),
            &mut data as *mut _ as *mut u8,
            mem::size_of::<$int_ty>(),
        );
        data.to_le()
    }};
}

/// 最多使用一个字节切片的 7 个字节来加载 u64。
/// 它看起来很笨拙,但是发生的 `copy_nonoverlapping` 调用 (通过 `load_int_le!`) 都具有固定的大小,并且避免调用 `memcpy`,这对于提高速度非常有用。
///
///
/// 不安全的原因是: 启动时未检查索引 start..start+len
#[inline]
unsafe fn u8to64_le(buf: &[u8], start: usize, len: usize) -> u64 {
    debug_assert!(len < 8);
    let mut i = 0; // 输出 u64 中的当前字节索引 (来自 LSB)
    let mut out = 0;
    if i + 3 < len {
        // SAFETY: `i` 不能大于 `len`,并且调用者必须保证索引 start..start + len 在范围之内。
        //
        out = unsafe { load_int_le!(buf, start + i, u32) } as u64;
        i += 4;
    }
    if i + 1 < len {
        // SAFETY: 与上述相同。
        out |= (unsafe { load_int_le!(buf, start + i, u16) } as u64) << (i * 8);
        i += 2
    }
    if i < len {
        // SAFETY: 与上述相同。
        out |= (unsafe { *buf.get_unchecked(start + i) } as u64) << (i * 8);
        i += 1;
    }
    debug_assert_eq!(i, len);
    out
}

impl SipHasher {
    /// 用两个初始键设置为 0 创建一个新的 `SipHasher`。
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[rustc_deprecated(
        since = "1.13.0",
        reason = "use `std::collections::hash_map::DefaultHasher` instead"
    )]
    pub fn new() -> SipHasher {
        SipHasher::new_with_keys(0, 0)
    }

    /// 创建一个 `SipHasher`,该 `SipHasher` 从提供的键上退出。
    #[inline]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[rustc_deprecated(
        since = "1.13.0",
        reason = "use `std::collections::hash_map::DefaultHasher` instead"
    )]
    pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
        SipHasher(SipHasher24 { hasher: Hasher::new_with_keys(key0, key1) })
    }
}

impl SipHasher13 {
    /// 用两个初始键设置为 0 创建一个新的 `SipHasher13`。
    #[inline]
    #[unstable(feature = "hashmap_internals", issue = "none")]
    #[rustc_deprecated(
        since = "1.13.0",
        reason = "use `std::collections::hash_map::DefaultHasher` instead"
    )]
    pub fn new() -> SipHasher13 {
        SipHasher13::new_with_keys(0, 0)
    }

    /// 创建一个 `SipHasher13`,该 `SipHasher13` 从提供的键上退出。
    #[inline]
    #[unstable(feature = "hashmap_internals", issue = "none")]
    #[rustc_deprecated(
        since = "1.13.0",
        reason = "use `std::collections::hash_map::DefaultHasher` instead"
    )]
    pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher13 {
        SipHasher13 { hasher: Hasher::new_with_keys(key0, key1) }
    }
}

impl<S: Sip> Hasher<S> {
    #[inline]
    fn new_with_keys(key0: u64, key1: u64) -> Hasher<S> {
        let mut state = Hasher {
            k0: key0,
            k1: key1,
            length: 0,
            state: State { v0: 0, v1: 0, v2: 0, v3: 0 },
            tail: 0,
            ntail: 0,
            _marker: PhantomData,
        };
        state.reset();
        state
    }

    #[inline]
    fn reset(&mut self) {
        self.length = 0;
        self.state.v0 = self.k0 ^ 0x736f6d6570736575;
        self.state.v1 = self.k1 ^ 0x646f72616e646f6d;
        self.state.v2 = self.k0 ^ 0x6c7967656e657261;
        self.state.v3 = self.k1 ^ 0x7465646279746573;
        self.ntail = 0;
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl super::Hasher for SipHasher {
    #[inline]
    fn write(&mut self, msg: &[u8]) {
        self.0.hasher.write(msg)
    }

    #[inline]
    fn finish(&self) -> u64 {
        self.0.hasher.finish()
    }
}

#[unstable(feature = "hashmap_internals", issue = "none")]
impl super::Hasher for SipHasher13 {
    #[inline]
    fn write(&mut self, msg: &[u8]) {
        self.hasher.write(msg)
    }

    #[inline]
    fn finish(&self) -> u64 {
        self.hasher.finish()
    }
}

impl<S: Sip> super::Hasher for Hasher<S> {
    // Note: 没有为此类型定义整数哈希方法 (`write_u *`,`write_i*`)。
    // 我们可以添加它们,在 librustc_data_structures/sip128.rs 中复制 `short_write` 实现,然后将 `write_u *`/`write_i*` 方法添加到 `SipHasher`,`SipHasher13` 和 `DefaultHasher`。
    //
    // 这将大大加快这些散列的整数散列速度,但会以稍微降低某些基准的编译速度为代价。
    // 有关详细信息,请参见 #69152。
    //
    //
    #[inline]
    fn write(&mut self, msg: &[u8]) {
        let length = msg.len();
        self.length += length;

        let mut needed = 0;

        if self.ntail != 0 {
            needed = 8 - self.ntail;
            // SAFETY: `cmp::min(length, needed)` 保证不超过 `length`
            self.tail |= unsafe { u8to64_le(msg, 0, cmp::min(length, needed)) } << (8 * self.ntail);
            if length < needed {
                self.ntail += length;
                return;
            } else {
                self.state.v3 ^= self.tail;
                S::c_rounds(&mut self.state);
                self.state.v0 ^= self.tail;
                self.ntail = 0;
            }
        }

        // 缓冲的尾巴现在被冲洗,处理新的输入。
        let len = length - needed;
        let left = len & 0x7; // len % 8

        let mut i = needed;
        while i < len - left {
            // SAFETY: 因为 `len - left` 是 `len` 的 8 的最大倍数,并且因为 `i` 以 `len` 为 `length - needed` 的 `needed` 开头,所以保证 `i + 8` 小于或等于 `length`。
            //
            //
            let mi = unsafe { load_int_le!(msg, i, u64) };

            self.state.v3 ^= mi;
            S::c_rounds(&mut self.state);
            self.state.v0 ^= mi;

            i += 8;
        }

        // SAFETY: `i` 现在是 `needed + len.div_euclid(8) * 8`,因此 `i + left` = `needed + len` = `length`,根据定义,它等于 `msg.len()`。
        //
        //
        self.tail = unsafe { u8to64_le(msg, i, left) };
        self.ntail = left;
    }

    #[inline]
    fn finish(&self) -> u64 {
        let mut state = self.state;

        let b: u64 = ((self.length as u64 & 0xff) << 56) | self.tail;

        state.v3 ^= b;
        S::c_rounds(&mut state);
        state.v0 ^= b;

        state.v2 ^= 0xff;
        S::d_rounds(&mut state);

        state.v0 ^ state.v1 ^ state.v2 ^ state.v3
    }
}

impl<S: Sip> Clone for Hasher<S> {
    #[inline]
    fn clone(&self) -> Hasher<S> {
        Hasher {
            k0: self.k0,
            k1: self.k1,
            length: self.length,
            state: self.state,
            tail: self.tail,
            ntail: self.ntail,
            _marker: self._marker,
        }
    }
}

impl<S: Sip> Default for Hasher<S> {
    /// 创建两个初始键设置为 0 的 `Hasher<S>`。
    #[inline]
    fn default() -> Hasher<S> {
        Hasher::new_with_keys(0, 0)
    }
}

#[doc(hidden)]
trait Sip {
    fn c_rounds(_: &mut State);
    fn d_rounds(_: &mut State);
}

#[derive(Debug, Clone, Default)]
struct Sip13Rounds;

impl Sip for Sip13Rounds {
    #[inline]
    fn c_rounds(state: &mut State) {
        compress!(state);
    }

    #[inline]
    fn d_rounds(state: &mut State) {
        compress!(state);
        compress!(state);
        compress!(state);
    }
}

#[derive(Debug, Clone, Default)]
struct Sip24Rounds;

impl Sip for Sip24Rounds {
    #[inline]
    fn c_rounds(state: &mut State) {
        compress!(state);
        compress!(state);
    }

    #[inline]
    fn d_rounds(state: &mut State) {
        compress!(state);
        compress!(state);
        compress!(state);
        compress!(state);
    }
}