src/librustc_data_structures/stable_hasher.rs

   1 // Copyright 2016 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use std::hash::Hasher;
  12 use std::marker::PhantomData;
  13 use std::mem;
  14 use blake2b::Blake2bHasher;
  15 use rustc_serialize::leb128;
  16 use rustc_i128::{u128,i128};
  17
  18 fn write_unsigned_leb128_to_buf(buf: &mut [u8; 16], value: u64) -> usize {
  19     leb128::write_unsigned_leb128_to(value as u128, |i, v| buf[i] = v)
  20 }
  21
  22 fn write_signed_leb128_to_buf(buf: &mut [u8; 16], value: i64) -> usize {
  23     leb128::write_signed_leb128_to(value as i128, |i, v| buf[i] = v)
  24 }
  25
  26 /// When hashing something that ends up affecting properties like symbol names. We
  27 /// want these symbol names to be calculated independent of other factors like
  28 /// what architecture you're compiling *from*.
  29 ///
  30 /// The hashing just uses the standard `Hash` trait, but the implementations of
  31 /// `Hash` for the `usize` and `isize` types are *not* architecture independent
  32 /// (e.g. they has 4 or 8 bytes). As a result we want to avoid `usize` and
  33 /// `isize` completely when hashing.
  34 ///
  35 /// To do that, we encode all integers to be hashed with some
  36 /// arch-independent encoding.
  37 ///
  38 /// At the moment, we pass i8/u8 straight through and encode
  39 /// all other integers using leb128.
  40 ///
  41 /// This hasher currently always uses the stable Blake2b algorithm
  42 /// and allows for variable output lengths through its type
  43 /// parameter.
  44 #[derive(Debug)]
  45 pub struct StableHasher<W> {
  46     state: Blake2bHasher,
  47     bytes_hashed: u64,
  48     width: PhantomData<W>,
  49 }
  50
  51 pub trait StableHasherResult: Sized {
  52     fn finish(hasher: StableHasher<Self>) -> Self;
  53 }
  54
  55 impl<W: StableHasherResult> StableHasher<W> {
  56     pub fn new() -> Self {
  57         StableHasher {
  58             state: Blake2bHasher::new(mem::size_of::<W>(), &[]),
  59             bytes_hashed: 0,
  60             width: PhantomData,
  61         }
  62     }
  63
  64     pub fn finish(self) -> W {
  65         W::finish(self)
  66     }
  67 }
  68
  69 impl StableHasherResult for [u8; 20] {
  70     fn finish(mut hasher: StableHasher<Self>) -> Self {
  71         let mut result: [u8; 20] = [0; 20];
  72         result.copy_from_slice(hasher.state.finalize());
  73         result
  74     }
  75 }
  76
  77 impl StableHasherResult for u64 {
  78     fn finish(mut hasher: StableHasher<Self>) -> Self {
  79         hasher.state.finalize();
  80         hasher.state.finish()
  81     }
  82 }
  83
  84 impl<W> StableHasher<W> {
  85     #[inline]
  86     pub fn finalize(&mut self) -> &[u8] {
  87         self.state.finalize()
  88     }
  89
  90     #[inline]
  91     pub fn bytes_hashed(&self) -> u64 {
  92         self.bytes_hashed
  93     }
  94
  95     #[inline]
  96     fn write_uleb128(&mut self, value: u64) {
  97         let mut buf = [0; 16];
  98         let len = write_unsigned_leb128_to_buf(&mut buf, value);
  99         self.state.write(&buf[..len]);
 100         self.bytes_hashed += len as u64;
 101     }
 102
 103     #[inline]
 104     fn write_ileb128(&mut self, value: i64) {
 105         let mut buf = [0; 16];
 106         let len = write_signed_leb128_to_buf(&mut buf, value);
 107         self.state.write(&buf[..len]);
 108         self.bytes_hashed += len as u64;
 109     }
 110 }
 111
 112 // For the non-u8 integer cases we leb128 encode them first. Because small
 113 // integers dominate, this significantly and cheaply reduces the number of
 114 // bytes hashed, which is good because blake2b is expensive.
 115 impl<W> Hasher for StableHasher<W> {
 116     fn finish(&self) -> u64 {
 117         panic!("use StableHasher::finish instead");
 118     }
 119
 120     #[inline]
 121     fn write(&mut self, bytes: &[u8]) {
 122         self.state.write(bytes);
 123         self.bytes_hashed += bytes.len() as u64;
 124     }
 125
 126     #[inline]
 127     fn write_u8(&mut self, i: u8) {
 128         self.state.write_u8(i);
 129         self.bytes_hashed += 1;
 130     }
 131
 132     #[inline]
 133     fn write_u16(&mut self, i: u16) {
 134         self.write_uleb128(i as u64);
 135     }
 136
 137     #[inline]
 138     fn write_u32(&mut self, i: u32) {
 139         self.write_uleb128(i as u64);
 140     }
 141
 142     #[inline]
 143     fn write_u64(&mut self, i: u64) {
 144         self.write_uleb128(i);
 145     }
 146
 147     #[inline]
 148     fn write_usize(&mut self, i: usize) {
 149         self.write_uleb128(i as u64);
 150     }
 151
 152     #[inline]
 153     fn write_i8(&mut self, i: i8) {
 154         self.state.write_i8(i);
 155         self.bytes_hashed += 1;
 156     }
 157
 158     #[inline]
 159     fn write_i16(&mut self, i: i16) {
 160         self.write_ileb128(i as i64);
 161     }
 162
 163     #[inline]
 164     fn write_i32(&mut self, i: i32) {
 165         self.write_ileb128(i as i64);
 166     }
 167
 168     #[inline]
 169     fn write_i64(&mut self, i: i64) {
 170         self.write_ileb128(i);
 171     }
 172
 173     #[inline]
 174     fn write_isize(&mut self, i: isize) {
 175         self.write_ileb128(i as i64);
 176     }
 177 }