elf-loader/src/elf_hash_table.rs (a74924e) - apple-crates · Git

elf_hash_table.rs

use goblin::elf::{Sym, Symtab};
use goblin::strtab::Strtab;

/// A .gnu.hash section, in the host's byte order and word size.
// HACK: the bloom filter is skipped, lookups always walk the chains.
pub struct GnuHash {
    symbol_offset: u32,
    buckets: Vec<u32>,
    chains: Vec<u32>,
}

impl GnuHash {
    /// The words are copied out of the section, so it doesn't have to be aligned.
    pub fn parse(section: &[u8]) -> Option<GnuHash> {
        let (words, _): (&[[u8; 4]], _) = section.as_chunks();
        let words: Vec<u32> = words.iter().copied().map(u32::from_ne_bytes).collect();

match words.as_slice() {
            [
                bucket_count,
                symbol_offset,
                bloom_size,
                _bloom_shift,
                rest @ ..,
            ] => {
                let bloom_words = *bloom_size as usize * size_of::<usize>() / size_of::<u32>();
                let (buckets, chains) = rest
                    .get(bloom_words..)?
                    .split_at_checked(*bucket_count as usize)?;

Some(GnuHash {
                    symbol_offset: *symbol_offset,
                    buckets: buckets.to_vec(),
                    chains: chains.to_vec(),
                })
            }
            _ => None,
        }
    }

pub fn find(&self, name: &str, symbols: &Symtab, strings: &Strtab) -> Option<Sym> {
        let hash = hash(name);
        let bucket = (hash as usize)
            .checked_rem(self.buckets.len())
            .map(|index| self.buckets[index])?;

// Symbols before the offset are not hashed, so such a bucket is empty.
        let chain_start = bucket.checked_sub(self.symbol_offset)? as usize;
        let chain = self
            .chains
            .get(chain_start..)?
            .iter()
            .zip(symbols.iter().skip(bucket as usize));

for (chain_hash, symbol) in chain {
            if chain_hash & !1 == hash & !1 && strings.get_at(symbol.st_name) == Some(name) {
                return Some(symbol);
            }

// The last element of a chain has its lowest bit set.
            if chain_hash & 1 == 1 {
                break;
            }
        }
        None
    }
}

pub fn hash(symbol: &str) -> u32 {
    symbol.bytes().fold(5381, |hash, byte| {
        hash.wrapping_mul(33).wrapping_add(u32::from(byte))
    })
}

#[cfg(test)]
mod tests {
    use super::*;

#[test]
    fn hash_matches_the_gnu_reference_values() {
        assert_eq!(hash(""), 0x0000_1505);
        assert_eq!(hash("printf"), 0x156b_2bb8);
        assert_eq!(hash("exit"), 0x7c96_7e3f);
        assert_eq!(hash("syscall"), 0xbac2_12a0);
    }

#[test]
    fn truncated_sections_are_rejected() {
        let header = [1u32, 1, 1, 6];
        let section: Vec<u8> = header.iter().flat_map(|word| word.to_ne_bytes()).collect();
        // The bloom filter and the bucket are missing.
        assert!(GnuHash::parse(&section).is_none());
        assert!(GnuHash::parse(&section[..12]).is_none());
    }
}

apple-crates

Refactor and unify a lot of things for another project and implement airdrop support