Skip to content

Instantly share code, notes, and snippets.

@pczarn

pczarn/iter-hash.asm

Last active August 29, 2015 14:15
Show Gist options
  • Save pczarn/644020c49432a4b3aaa8 to your computer and use it in GitHub Desktop.
Save pczarn/644020c49432a4b3aaa8 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
iter-hash.asm
.text
.file "myhash.bc"
.align 16, 0x90
.type _ZN4main20h487ea52046783e21hQaE,@function
_ZN4main20h487ea52046783e21hQaE: # @_ZN4main20h487ea52046783e21hQaE
.cfi_startproc
# BB#0:
cmp rsp, qword ptr fs:[112]
ja .LBB0_2
# BB#1:
movabs r10, 136
movabs r11, 0
call __morestack
ret
.LBB0_2: # %entry-block
push rbp
.Ltmp0:
.cfi_def_cfa_offset 16
push r15
.Ltmp1:
.cfi_def_cfa_offset 24
push r14
.Ltmp2:
.cfi_def_cfa_offset 32
push r13
.Ltmp3:
.cfi_def_cfa_offset 40
push r12
.Ltmp4:
.cfi_def_cfa_offset 48
push rbx
.Ltmp5:
.cfi_def_cfa_offset 56
sub rsp, 88
.Ltmp6:
.cfi_def_cfa_offset 144
.Ltmp7:
.cfi_offset rbx, -56
.Ltmp8:
.cfi_offset r12, -48
.Ltmp9:
.cfi_offset r13, -40
.Ltmp10:
.cfi_offset r14, -32
.Ltmp11:
.cfi_offset r15, -24
.Ltmp12:
.cfi_offset rbp, -16
movabs rbx, 8387220255154660723
movabs r15, 8317987319222330741
movabs rbp, 7816392313619706465
movabs r14, 7237128888997146477
mov byte ptr [rsp + 13], 12
mov byte ptr [rsp + 14], 23
mov byte ptr [rsp + 15], 34
lea rax, qword ptr [rsp + 13]
mov qword ptr [rsp + 16], rax
lea rax, qword ptr [rsp + 24]
mov qword ptr [rsp + 24], 3
lea rcx, qword ptr [rsp + 16]
#APP
#NO_APP
lea rcx, qword ptr [rsp + 32]
mov rdx, qword ptr [rsp + 16]
mov rsi, qword ptr [rsp + 24]
mov qword ptr [rsp], rsi # 8-byte Spill
mov qword ptr [rsp + 48], rax
mov qword ptr [rsp + 56], rcx
mov qword ptr [rsp + 64], rdx
add rdx, rsi
mov qword ptr [rsp + 72], rdx
mov byte ptr [rsp + 80], 0
lea rdi, qword ptr [rsp + 32]
lea rsi, qword ptr [rsp + 48]
call _ZN25Chunks8$LT$T$GT$.Iterator4next20h6088891530180175615E
mov rax, qword ptr [rsp + 32]
xor r12d, r12d
movzx ecx, al
cmp ecx, 1
jne .LBB0_5
# BB#3: # %match_case.lr.ph.i.i
lea r13, qword ptr [rsp + 48]
.align 16, 0x90
.LBB0_4: # %match_case.i.i
# =>This Inner Loop Header: Depth=1
shr rax, 8
mov rcx, rax
movabs rdx, 71776119061217280
and rcx, rdx
movzx r8d, al
mov rsi, rax
and rsi, 16711680
movzx edi, byte ptr [rsp + 40]
shl rdi, 56
movabs rdx, 281474959998720
and rax, rdx
or rax, rcx
or rax, rsi
or rax, r8
mov r12, rax
or r12, rdi
xor rbx, r12
add r15, r14
rol r14, 13
xor r14, r15
rol r15, 32
add rbp, rbx
rol rbx, 16
xor rbx, rbp
add r15, rbx
rol rbx, 21
xor rbx, r15
add rbp, r14
rol r14, 17
xor r14, rbp
rol rbp, 32
add r15, r14
rol r14, 13
xor r14, r15
rol r15, 32
add rbp, rbx
rol rbx, 16
xor rbx, rbp
add r15, rbx
rol rbx, 21
xor rbx, r15
add rbp, r14
rol r14, 17
xor r14, rbp
rol rbp, 32
xor r15, r12
lea rdi, qword ptr [rsp + 32]
mov rsi, r13
call _ZN25Chunks8$LT$T$GT$.Iterator4next20h6088891530180175615E
mov rax, qword ptr [rsp + 32]
movzx ecx, al
cmp ecx, 1
je .LBB0_4
.LBB0_5: # %_ZN4hash21h12932824202853158335E.exit
mov rcx, qword ptr [rsp] # 8-byte Reload
shl rcx, 56
movabs rax, 576460752303423488
add rax, rcx
or rax, r12
xor rbx, rax
add r15, r14
rol r14, 13
xor r14, r15
rol r15, 32
add rbp, rbx
rol rbx, 16
xor rbx, rbp
add r15, rbx
rol rbx, 21
xor rbx, r15
add rbp, r14
rol r14, 17
xor r14, rbp
rol rbp, 32
add r15, r14
rol r14, 13
xor r14, r15
rol r15, 32
add rbp, rbx
rol rbx, 16
xor rbx, rbp
add r15, rbx
rol rbx, 21
xor rbx, r15
add rbp, r14
rol r14, 17
xor r14, rbp
rol rbp, 32
xor r15, rax
xor rbp, 255
add r15, r14
rol r14, 13
xor r14, r15
rol r15, 32
add rbp, rbx
rol rbx, 16
xor rbx, rbp
add r15, rbx
rol rbx, 21
xor rbx, r15
add rbp, r14
rol r14, 17
xor r14, rbp
rol rbp, 32
add r15, r14
rol r14, 13
xor r14, r15
rol r15, 32
add rbp, rbx
rol rbx, 16
xor rbx, rbp
add r15, rbx
rol rbx, 21
xor rbx, r15
add rbp, r14
rol r14, 17
xor r14, rbp
rol rbp, 32
add r15, r14
rol r14, 13
xor r14, r15
rol r15, 32
add rbp, rbx
rol rbx, 16
xor rbx, rbp
add r15, rbx
rol rbx, 21
xor rbx, r15
add rbp, r14
rol r14, 17
xor r14, rbp
rol rbp, 32
add r15, r14
rol r14, 13
xor r14, r15
add rbp, rbx
rol rbx, 16
xor rbx, rbp
rol rbx, 21
add rbp, r14
rol r14, 17
xor r14, rbp
rol rbp, 32
xor rbp, r14
xor rbp, rbx
mov qword ptr [rsp + 32], rbp
lea rax, qword ptr [rsp + 32]
mov qword ptr [rsp + 48], rax
lea rax, qword ptr [rsp + 48]
#APP
#NO_APP
add rsp, 88
pop rbx
pop r12
pop r13
pop r14
pop r15
pop rbp
ret
.Ltmp13:
.size _ZN4main20h487ea52046783e21hQaE, .Ltmp13-_ZN4main20h487ea52046783e21hQaE
.cfi_endproc
.globl main
.align 16, 0x90
.type main,@function
main: # @main
.cfi_startproc
# BB#0: # %top
mov rax, rsi
mov rcx, rdi
mov edi, _ZN4main20h487ea52046783e21hQaE
mov rsi, rcx
mov rdx, rax
jmp _ZN2rt10lang_start20hc4be6dc9cdf9b156KzJE # TAILCALL
.Ltmp14:
.size main, .Ltmp14-main
.cfi_endproc
.align 16, 0x90
.type _ZN25Chunks8$LT$T$GT$.Iterator4next20h6088891530180175615E,@function
_ZN25Chunks8$LT$T$GT$.Iterator4next20h6088891530180175615E: # @"_ZN25Chunks8$LT$T$GT$.Iterator4next20h6088891530180175615E"
.cfi_startproc
# BB#0:
cmp rsp, qword ptr fs:[112]
ja .LBB2_2
# BB#1:
movabs r10, 24
movabs r11, 0
call __morestack
ret
.LBB2_2: # %entry-block
push r14
.Ltmp15:
.cfi_def_cfa_offset 16
push rbx
.Ltmp16:
.cfi_def_cfa_offset 24
push rax
.Ltmp17:
.cfi_def_cfa_offset 32
.Ltmp18:
.cfi_offset rbx, -24
.Ltmp19:
.cfi_offset r14, -16
mov rcx, qword ptr [rsi]
mov r9, qword ptr [rsi + 8]
cmp rcx, r9
je .LBB2_3
# BB#7: # %_ZN5slice36Iter$LT$$u27$a$C$$u20$T$GT$.Iterator4next20h4304909603811941422E.exit20.i
lea rax, qword ptr [rcx + 1]
mov qword ptr [rsi], rax
test rcx, rcx
je .LBB2_4
# BB#8: # %_ZN5slice36Iter$LT$$u27$a$C$$u20$T$GT$.Iterator4next20h4304909603811941422E.exit20.i.match_case_crit_edge
lea r10, qword ptr [rsi + 16]
lea r8, qword ptr [rsi + 24]
xor r11d, r11d
jmp .LBB2_9
.LBB2_3:
mov rax, rcx
.LBB2_4: # %match_else.i
mov byte ptr [rsi + 32], 1
mov rcx, qword ptr [rsi + 16]
cmp rcx, qword ptr [rsi + 24]
je .LBB2_20
# BB#5: # %else-block.i15.i
lea r10, qword ptr [rsi + 16]
lea rdx, qword ptr [rcx + 1]
mov qword ptr [r10], rdx
test rcx, rcx
je .LBB2_20
# BB#6:
mov r11b, 1
lea r8, qword ptr [rsi + 24]
.LBB2_9: # %match_case
mov cl, byte ptr [rcx]
mov byte ptr [rsp], cl
mov byte ptr [rsp + 7], 0
mov word ptr [rsp + 5], 0
mov dword ptr [rsp + 1], 0
mov edx, 1
.align 16, 0x90
.LBB2_10: # %match_case8
# =>This Inner Loop Header: Depth=1
lea r14, qword ptr [rdx + 1]
test r11b, r11b
je .LBB2_12
# BB#11: # %then-block-3237-.i42
# in Loop: Header=BB2_10 Depth=1
mov rcx, qword ptr [r10]
cmp rcx, qword ptr [r8]
jne .LBB2_16
jmp .LBB2_18
.align 16, 0x90
.LBB2_12: # %else-block.i44
# in Loop: Header=BB2_10 Depth=1
cmp rax, r9
mov rbx, r9
je .LBB2_15
# BB#13: # %_ZN5slice36Iter$LT$$u27$a$C$$u20$T$GT$.Iterator4next20h4304909603811941422E.exit20.i45
# in Loop: Header=BB2_10 Depth=1
lea rbx, qword ptr [rax + 1]
mov qword ptr [rsi], rbx
test rax, rax
je .LBB2_15
# BB#14: # in Loop: Header=BB2_10 Depth=1
xor r11d, r11d
jmp .LBB2_17
.align 16, 0x90
.LBB2_15: # %match_else.i46
# in Loop: Header=BB2_10 Depth=1
mov byte ptr [rsi + 32], 1
mov rcx, qword ptr [rsi + 16]
mov r11b, 1
cmp rcx, qword ptr [rsi + 24]
mov rax, rbx
je .LBB2_18
.LBB2_16: # %_ZN4iter32Chain$LT$A$C$$u20$B$GT$.Iterator4next21h18133864556562345281E.exit49
# in Loop: Header=BB2_10 Depth=1
lea rbx, qword ptr [rcx + 1]
mov qword ptr [r10], rbx
test rcx, rcx
mov rbx, rax
mov rax, rcx
je .LBB2_18
.LBB2_17: # %_ZN5slice38_$u5b$T$u5d$.ops..IndexMut$LT$uint$GT$9index_mut20h4953912456177802737E.exit
# in Loop: Header=BB2_10 Depth=1
mov al, byte ptr [rax]
mov byte ptr [rsp + rdx], al
cmp r14, 8
mov rax, rbx
mov rdx, r14
jb .LBB2_10
.LBB2_18: # %clean_ast_903_
mov rax, qword ptr [rsp]
mov qword ptr [rdi + 1], rax
mov byte ptr [rdi], 1
jmp .LBB2_19
.LBB2_20: # %match_else
mov byte ptr [rdi], 0
.LBB2_19: # %join18
mov rax, rdi
add rsp, 8
pop rbx
pop r14
ret
.Ltmp20:
.size _ZN25Chunks8$LT$T$GT$.Iterator4next20h6088891530180175615E, .Ltmp20-_ZN25Chunks8$LT$T$GT$.Iterator4next20h6088891530180175615E
.cfi_endproc
.section ".note.GNU-stack","",@progbits
Raw
iter-hash.rs
#![feature(globs, macro_rules, default_type_params, asm, if_let, old_orphan_check)]
extern crate test;
use test::black_box;
use std::mem;
use std::default::Default;
use std::num::{Int, ToPrimitive};
use std::ops::Shr;
use std::{option, str, slice};
use std::mem::size_of;
use std::iter::{FlatMap, Cloned, Chain, repeat, ExactSizeIterator, AdditiveIterator};
use self::test::Bencher;
/// A hashable type.
pub trait Hash<'a> {
type Contents: Iterator<Item=&'a u8>;
fn as_byte_contents(&self) -> (<Self as Hash>::Contents, usize);
}
/// A trait which represents the ability to hash an arbitrary stream of bytes.
pub trait Hasher<'a> {
/// Result type of one run of hashing generated by this hasher.
type Output;
/// Resets this hasher back to its initial state (as if it were just
/// created).
fn reset(&mut self);
/// Completes hashing, producing the output hash generated.
fn hash<T: Iterator<Item=&'a u8>>(&mut self, iter: T, length: usize) -> Self::Output;
}
/// Hash a value with the default SipHasher algorithm (two initial keys of 0).
pub fn hash<'a, T: Hash<'a>, H: Hasher<'a> + Default>(value: &T) -> H::Output {
let mut h: H = Default::default();
let (iter, len) = value.as_byte_contents();
h.hash(iter, len)
}
//////////////////////////////////////////////////////////////////////////////
type IntIter<'a> = slice::Iter<'a, u8>;
macro_rules! impl_hash {
($ty:ident, $uty:ident) => {
impl<'a> Hash<'a> for &'a $ty {
type Contents = IntIter<'a>;
#[inline(always)]
fn as_byte_contents(&self) -> (IntIter<'a>, usize) {
let a: &'a [u8; ::std::$ty::BYTES] = unsafe { mem::transmute(*self) };
(
a.iter(),
size_of::<$ty>()
)
}
}
}
}
impl_hash! { u8, u8 }
impl_hash! { u16, u16 }
impl_hash! { u32, u32 }
impl_hash! { u64, u64 }
impl_hash! { usize, usize }
impl_hash! { i8, u8 }
impl_hash! { i16, u16 }
impl_hash! { i32, u32 }
impl_hash! { i64, u64 }
impl_hash! { isize, usize }
type SliceContents<'a> = Chain<slice::Iter<'a, u8>, slice::Iter<'a, u8>>;
impl<'a> Hash<'a> for &'a [u8] {
type Contents = SliceContents<'a>;
fn as_byte_contents(&self) -> (SliceContents<'a>, usize) {
let this: &'a std::raw::Slice<u8> = unsafe { mem::transmute(self) };
let len: &'a [u8; ::std::usize::BYTES] = unsafe { mem::transmute(&this.len) };
(
len.iter().chain(self.iter()),
self.len() + size_of::<usize>()
)
}
}
impl<'a, T: ?Sized, U: Iterator<Item=&'a u8>> Hash<'a> for &'a T where T: Hash<'a, Contents=U> {
type Contents = U;
#[inline]
fn as_byte_contents(&self) -> (U, usize) {
(*self).as_byte_contents()
}
}
impl<'a, T: ?Sized, U: Iterator<Item=&'a u8>> Hash<'a> for &'a mut T where T: Hash<'a, Contents=U> {
type Contents = U;
#[inline]
fn as_byte_contents(&self) -> (U, usize) {
(*self).as_byte_contents()
}
}
/// An implementation of SipHash 2-4.
///
/// See: http://131002.net/siphash/
///
/// Consider this as a main "general-purpose" hash for all hashtables: it
/// runs at good speed (competitive with spooky and city) and permits
/// strong _keyed_ hashing. Key your hashtables from a strong RNG,
/// such as `rand::Rng`.
///
/// Although the SipHash algorithm is considered to be cryptographically
/// strong, this implementation has not been reviewed for such purposes.
/// As such, all cryptographic uses of this implementation are strongly
/// discouraged.
pub struct SipHasher {
k0: u64,
k1: u64,
length: uint, // how many bytes we've processed
v0: u64, // hash state
v1: u64,
v2: u64,
v3: u64,
tail: u64, // unprocessed bytes le
ntail: uint, // how many bytes in tail are valid
}
// sadly, these macro definitions can't appear later,
// because they're needed in the following defs;
// this design could be improved.
macro_rules! u8to64_le {
($buf:expr, $i:expr) =>
($buf[0+$i] as u64 |
($buf[1+$i] as u64) << 8 |
($buf[2+$i] as u64) << 16 |
($buf[3+$i] as u64) << 24 |
($buf[4+$i] as u64) << 32 |
($buf[5+$i] as u64) << 40 |
($buf[6+$i] as u64) << 48 |
($buf[7+$i] as u64) << 56);
($buf:expr, $i:expr, $len:expr) =>
({
let mut t = 0;
let mut out = 0u64;
while t < $len {
out |= ($buf[t+$i] as u64) << t*8;
t += 1;
}
out
});
}
macro_rules! rotl {
($x:expr, $b:expr) =>
(($x << $b) | ($x >> (64 - $b)))
}
macro_rules! compress {
($v0:expr, $v1:expr, $v2:expr, $v3:expr) =>
({
$v0 += $v1; $v1 = rotl!($v1, 13); $v1 ^= $v0;
$v0 = rotl!($v0, 32);
$v2 += $v3; $v3 = rotl!($v3, 16); $v3 ^= $v2;
$v0 += $v3; $v3 = rotl!($v3, 21); $v3 ^= $v0;
$v2 += $v1; $v1 = rotl!($v1, 17); $v1 ^= $v2;
$v2 = rotl!($v2, 32);
})
}
impl SipHasher {
/// Creates a new `SipHasher` with the two initial keys set to 0.
#[inline]
pub fn new() -> SipHasher {
SipHasher::new_with_keys(0, 0)
}
/// Creates a `SipHasher` that is keyed off the provided keys.
#[inline]
pub fn new_with_keys(key0: u64, key1: u64) -> SipHasher {
let mut state = SipHasher {
k0: key0,
k1: key1,
length: 0,
v0: 0,
v1: 0,
v2: 0,
v3: 0,
tail: 0,
ntail: 0,
};
state.reset();
state
}
}
struct Chunks8<T> {
iter: T,
}
impl<'a, T: Iterator<Item=&'a u8>> Iterator for Chunks8<T> {
type Item = u64;
#[inline(never)]
fn next(&mut self) -> Option<u64> {
// let ary =
// [self.iter.next().unwrap_or(0),
// self.iter.next().unwrap_or(0),
// self.iter.next().unwrap_or(0),
// self.iter.next().unwrap_or(0),
// self.iter.next().unwrap_or(0),
// self.iter.next().unwrap_or(0),
// self.iter.next().unwrap_or(0),
// self.iter.next().unwrap_or(0),];
// Some(u8to64_le!(ary, 0))
match self.iter.next() {
Some(mi) => {
let mut msg: [u8; 8] = [*mi, 0, 0, 0, 0, 0, 0, 0];
let mut iter = &mut self.iter;
for i in 1u..8 {
msg[i] = if let Some(x) = iter.next() { *x } else { break };
}
Some(u8to64_le!(msg, 0))
}
None => None
}
// let mut mi = 0;
// for _ in 0..8 {
// mi |= self.iter.next().unwrap_or(0) as u64;
// mi <<= 8;
// }
// Some(mi)
}
}
impl<'a> Hasher<'a> for SipHasher {
type Output = u64;
fn reset(&mut self) {
self.length = 0;
self.v0 = self.k0 ^ 0x736f6d6570736575;
self.v1 = self.k1 ^ 0x646f72616e646f6d;
self.v2 = self.k0 ^ 0x6c7967656e657261;
self.v3 = self.k1 ^ 0x7465646279746573;
self.ntail = 0;
}
fn hash<T: Iterator<Item=&'a u8>>(&mut self, mut iter: T, mut length: usize) -> u64 {
let mut v0 = self.v0;
let mut v1 = self.v1;
let mut v2 = self.v2;
let mut v3 = self.v3;
let mut iter = Chunks8 { iter: iter };
let mut mi = 0;
let mut i = 0;
for chunk in iter {
mi = chunk;
v3 ^= mi;
compress!(v0, v1, v2, v3);
compress!(v0, v1, v2, v3);
v0 ^= mi;
}
mi |= ((length & 0xff) as u64) << 56;
v3 ^= mi;
compress!(v0, v1, v2, v3);
compress!(v0, v1, v2, v3);
v0 ^= mi;
v2 ^= 0xff;
compress!(v0, v1, v2, v3);
compress!(v0, v1, v2, v3);
compress!(v0, v1, v2, v3);
compress!(v0, v1, v2, v3);
return v0 ^ v1 ^ v2 ^ v3;
}
}
impl Clone for SipHasher {
#[inline]
fn clone(&self) -> SipHasher {
SipHasher {
k0: self.k0,
k1: self.k1,
length: self.length,
v0: self.v0,
v1: self.v1,
v2: self.v2,
v3: self.v3,
tail: self.tail,
ntail: self.ntail,
}
}
}
impl Default for SipHasher {
fn default() -> SipHasher {
SipHasher::new()
}
}
#[bench]
fn bench_slice(bench: &mut Bencher) {
let val: &[u8] = &[12, 23, 34, 45, 12, 12, 23, ];
// let mut val = 0u64;
let mut r = &val;
unsafe { asm!("" : "+r"(r) ::: "volatile"); }
bench.iter(||
hash::<_, SipHasher>(&r)
)
}
#[bench]
fn bench_std(bench: &mut Bencher) {
let mut val: &[u8] = &[12, 23, 34, 45, 12, 12, 23, ];
// let mut val = 0u64;
let mut r = &mut val;
unsafe { asm!("" : "+r"(r) ::: "volatile"); }
bench.iter(||
::std::hash::hash::<_, ::std::hash::SipHasher>(&r)
)
}
#[cfg(not(test))]
fn main() {
let mut val: &[u8] = &[12, 23, 34];
let mut r = &val;
unsafe { asm!("" : "+r"(r) ::: "volatile"); }
black_box(&hash::<_, SipHasher>(&val));
// black_box(&::std::hash::hash::<_, ::std::hash::SipHasher>(&r));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment