xmas_elf/
hash.rs

1use core::mem;
2
3use symbol_table::Entry;
4use zero::{read, Pod};
5
6#[derive(Clone, Copy, Debug)]
7#[repr(C)]
8struct HashTableInner {
9    bucket_count: u32,
10    chain_count: u32,
11    first_bucket: u32,
12}
13
14const OFFSET_OF_FIRST_BUCKET: usize = mem::offset_of!(HashTableInner, first_bucket);
15
16#[derive(Clone, Copy, Debug)]
17pub struct HashTable<'a> {
18    inner: &'a HashTableInner,
19    bounds: usize, // In number of u32s
20}
21
22unsafe impl Pod for HashTableInner {}
23
24pub fn hash(input: &str) -> u32 {
25    let mut result = 0;
26    for i in input.bytes() {
27        result = (result << 4) + i as u32;
28        let g = result & 0xf0000000;
29        if g != 0 {
30            result ^= g >> 24;
31        }
32        result &= !g
33    }
34    result
35}
36
37impl<'a> HashTable<'a> {
38    pub(crate) fn read(data: &'a [u8]) -> HashTable<'a> {
39        HashTable {
40            inner: read(&data[0..12]),
41            bounds: (data.len() - OFFSET_OF_FIRST_BUCKET) / mem::size_of::<u32>(),
42        }
43    }
44
45    pub fn get_bucket(&self, index: u32) -> u32 {
46        assert!(index < self.inner.bucket_count);
47        assert!((index as usize) < self.bounds);
48        unsafe {
49            let ptr = (&self.inner.first_bucket as *const u32).offset(index as isize);
50            *ptr
51        }
52    }
53
54    pub fn get_chain(&self, index: u32) -> u32 {
55        assert!(index < self.inner.chain_count);
56        let index = self.inner.bucket_count + index;
57        assert!((index as usize) < self.bounds);
58        unsafe {
59            let ptr = (&self.inner.first_bucket as *const u32).offset(index as isize);
60            *ptr
61        }
62    }
63
64    pub fn lookup<F>(&'a self, _name: &str, _f: F) -> &'a dyn Entry
65        where F: Fn(&dyn Entry) -> bool
66    {
67        // TODO
68        unimplemented!();
69    }
70}
xmas_elf/hash.rs

xmas_elf/
hash.rs
