#![deny(missing_docs)]
use std::{
cmp::Ord,
error::Error,
fmt::{Debug, Display, Formatter},
iter, mem,
ops::Range,
str::FromStr,
sync::{
atomic::{AtomicBool, Ordering},
mpsc, Arc,
},
thread::{self, JoinHandle},
};
#[cfg(feature = "opencl")]
use ocl::{
builders::DeviceSpecifier::TypeFlags,
flags::{DeviceType, MemFlags},
prm::Uint16,
Buffer, Context, Kernel, Platform, Program, Queue,
};
#[cfg(feature = "opencl")]
use std::convert::TryInto;
#[derive(Debug, PartialEq)]
pub struct HashSearchWorker<H: GitHashFn> {
processed_commit: ProcessedCommit,
hash_spec: HashSpec<H>,
search_space: Range<u64>,
}
#[derive(Debug, PartialEq, Clone)]
struct ProcessedCommit {
data: Box<[u8]>,
commit_range: Range<usize>,
num_static_blocks: usize,
}
#[derive(Debug)]
struct PartiallyHashedCommit<'a, H: GitHashFn> {
intermediate_state: H::State,
dynamic_blocks: &'a mut [H::Block],
}
#[derive(Debug, PartialEq, Clone)]
pub struct HashSpec<H: GitHashFn> {
data: H::State,
mask: H::State,
}
#[non_exhaustive]
#[derive(PartialEq, Eq)]
pub enum ParseHashSpecErr {
TooLong,
InvalidCharacter(char),
}
#[derive(Debug, PartialEq, Eq)]
pub struct GitCommit<H: GitHashFn> {
object: Vec<u8>,
hash: H::State,
}
pub trait GitHashFn: private::Sealed + Debug + Send + Clone + Eq + 'static {
type State: AsRef<[u32]> + AsMut<[u32]> + Clone + Copy + Debug + Default + Eq + Send;
const INITIAL_STATE: Self::State;
type Block: AsRef<[u8]> + AsMut<[u8]> + Copy + Debug;
fn compress(state: &mut Self::State, blocks: &[Self::Block]);
#[cfg(feature = "opencl")]
const KERNEL: &'static str;
}
#[derive(Debug, Clone, Eq, PartialEq)]
pub enum Sha1 {}
impl GitHashFn for Sha1 {
type State = [u32; 5];
const INITIAL_STATE: Self::State = [0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0];
type Block = sha1::digest::core_api::Block<sha1::Sha1Core>;
fn compress(state: &mut Self::State, blocks: &[Self::Block]) {
sha1::compress(state, blocks)
}
#[cfg(feature = "opencl")]
const KERNEL: &'static str = include_str!("sha1_matcher.cl");
}
#[derive(Debug, Clone, Eq, PartialEq)]
pub enum Sha256 {}
impl GitHashFn for Sha256 {
type State = [u32; 8];
const INITIAL_STATE: Self::State = [
0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab,
0x5be0cd19,
];
type Block = sha2::digest::core_api::Block<sha2::Sha256>;
fn compress(state: &mut Self::State, blocks: &[Self::Block]) {
sha2::compress256(state, blocks)
}
#[cfg(feature = "opencl")]
const KERNEL: &'static str = include_str!("sha256_matcher.cl");
}
mod private {
pub trait Sealed {}
impl Sealed for super::Sha1 {}
impl Sealed for super::Sha256 {}
}
impl<H: GitHashFn> HashSearchWorker<H> {
pub fn new(current_commit: &[u8], hash_spec: HashSpec<H>) -> Self {
Self {
processed_commit: ProcessedCommit::new(current_commit),
hash_spec,
search_space: 0..(1 << 48),
}
}
pub fn with_capped_search_space(mut self, workload: u64) -> Self {
self.search_space = self.search_space.start
..Ord::min(self.search_space.end, self.search_space.start + workload);
self
}
fn split_search_space(self, divisor: u64) -> impl Iterator<Item = Self> {
let amount_per_worker = (self.search_space.end - self.search_space.start) / divisor;
(0..divisor).map(move |index| {
let range_start = index * amount_per_worker + self.search_space.start;
let range_end = if index < divisor - 1 {
range_start + amount_per_worker
} else {
self.search_space.end
};
Self {
processed_commit: self.processed_commit.clone(),
hash_spec: self.hash_spec.clone(),
search_space: range_start..range_end,
}
})
}
pub fn search(self) -> Option<GitCommit<H>> {
#[cfg(feature = "opencl")]
if Self::gpus_available() {
return self.search_with_gpu().unwrap();
}
self.search_with_cpus()
}
#[cfg(feature = "opencl")]
fn gpus_available() -> bool {
Platform::first().is_ok()
&& !TypeFlags(DeviceType::GPU)
.to_device_list(None::<Platform>)
.unwrap()
.is_empty()
}
#[allow(clippy::needless_collect)]
fn search_with_cpus(self) -> Option<GitCommit<H>> {
let thread_count = num_cpus::get_physical();
let lame_duck_cancel_signal = Arc::new(AtomicBool::new(false));
let (shared_sender, receiver) = mpsc::channel();
let _handles = self
.split_search_space(thread_count as u64)
.map(|worker| {
let result_sender = shared_sender.clone();
let worker_cancel_signal = Arc::clone(&lame_duck_cancel_signal);
thread::spawn(move || {
let _ = result_sender
.send(worker.search_with_cpu_single_threaded(worker_cancel_signal));
})
})
.collect::<Vec<JoinHandle<()>>>();
for _ in 0..thread_count {
if let Some(result) = receiver.recv().unwrap() {
lame_duck_cancel_signal.store(true, Ordering::Relaxed);
#[cfg(debug_assertions)]
_handles
.into_iter()
.map(JoinHandle::join)
.collect::<Result<Vec<_>, _>>()
.unwrap();
return Some(result);
}
}
None
}
#[inline(never)]
fn search_with_cpu_single_threaded(
self,
lame_duck_cancel_signal: Arc<AtomicBool>,
) -> Option<GitCommit<H>> {
let HashSearchWorker {
search_space,
hash_spec,
mut processed_commit,
..
} = self;
let mut partially_hashed_commit = processed_commit.as_partially_hashed_commit::<H>();
let lame_duck_check_interval = Ord::min(search_space.end - search_space.start, 1 << 20);
for base_padding_specifier in search_space.step_by(lame_duck_check_interval as usize) {
for index_in_interval in 0..lame_duck_check_interval {
partially_hashed_commit.scatter_padding(base_padding_specifier + index_in_interval);
if hash_spec.matches(&partially_hashed_commit.current_hash()) {
return Some(GitCommit::new(processed_commit.commit()));
}
}
if lame_duck_cancel_signal.load(Ordering::Relaxed) {
break;
}
}
None
}
#[cfg(feature = "opencl")]
fn search_with_gpu(self) -> ocl::Result<Option<GitCommit<H>>> {
let HashSearchWorker {
search_space,
hash_spec,
mut processed_commit,
..
} = self;
let mut partially_hashed_commit = processed_commit.as_partially_hashed_commit::<H>();
let num_threads = *[
hash_spec.estimated_attempts_needed().saturating_mul(4),
search_space.end - search_space.start,
1 << 22,
]
.iter()
.min()
.unwrap() as usize;
assert!(num_threads < u32::MAX as usize);
let devices = TypeFlags(DeviceType::GPU).to_device_list(Some(Platform::default()))?[0];
let context = Context::builder().devices(devices).build()?;
let queue = Queue::new(&context, devices, None)?;
let mut successful_match_receiver_host_handle = [u32::MAX];
let successful_match_receiver = Buffer::builder()
.queue(queue.clone())
.len(1)
.flags(MemFlags::READ_WRITE)
.copy_host_slice(&successful_match_receiver_host_handle)
.build()?;
const BASE_PADDING_SPECIFIER_ARG: &str = "base_padding_specifier";
let kernel = Kernel::builder()
.name("scatter_padding_and_find_match")
.program(
&Program::builder()
.src(H::KERNEL)
.cmplr_opt("-Werror")
.build(&context)?,
)
.arg(
&Buffer::builder()
.queue(queue.clone())
.len(hash_spec.data.as_ref().len())
.flags(MemFlags::READ_ONLY)
.copy_host_slice(hash_spec.data.as_ref())
.build()?,
)
.arg(
&Buffer::builder()
.queue(queue.clone())
.len(hash_spec.mask.as_ref().len())
.flags(MemFlags::READ_ONLY)
.copy_host_slice(hash_spec.mask.as_ref())
.build()?,
)
.arg(
&Buffer::builder()
.queue(queue.clone())
.len(partially_hashed_commit.intermediate_state.as_ref().len())
.flags(MemFlags::READ_ONLY)
.copy_host_slice(partially_hashed_commit.intermediate_state.as_ref())
.build()?,
)
.arg_named(BASE_PADDING_SPECIFIER_ARG, 0u64) .arg(
&Buffer::builder()
.queue(queue.clone())
.len(partially_hashed_commit.dynamic_blocks.len())
.flags(MemFlags::READ_ONLY)
.copy_host_slice(
&partially_hashed_commit
.dynamic_blocks
.iter()
.map(|&block| encode_into_opencl_vector::<H>(block))
.collect::<Vec<_>>(),
)
.build()?,
)
.arg(partially_hashed_commit.dynamic_blocks.len() as u64)
.arg(&successful_match_receiver)
.queue(queue)
.global_work_size(num_threads)
.build()?;
for base_padding_specifier in search_space.step_by(num_threads) {
kernel.set_arg(BASE_PADDING_SPECIFIER_ARG, base_padding_specifier)?;
unsafe {
kernel.enq()?;
}
successful_match_receiver
.read(&mut successful_match_receiver_host_handle[..])
.enq()?;
if successful_match_receiver_host_handle[0] != u32::MAX {
let successful_padding_specifier =
base_padding_specifier + (successful_match_receiver_host_handle[0] as u64);
partially_hashed_commit.scatter_padding(successful_padding_specifier);
assert!(
hash_spec.matches(&partially_hashed_commit.current_hash()),
"\
A GPU search reported a commit with a successful match, but when that \
commit was hashed in postprocessing, it didn't match the desired spec. \
This is a bug. The most likely explanation is that the two implementations of \
`scatter_padding` in Rust and OpenCL (or the implementations of SHA1/SHA256) have diverged \
from each other.\n\npartial commit:\n\t{:?}\ndesired hash spec:\n\t{:?}\ncommit hash \
produced during postprocessing:{:?}\n\tpadding specifier: {}",
partially_hashed_commit,
hash_spec,
partially_hashed_commit.current_hash(),
successful_padding_specifier,
);
return Ok(Some(GitCommit::new(processed_commit.commit())));
}
}
Ok(None)
}
}
impl ProcessedCommit {
const DYNAMIC_PADDING_LENGTH: usize = 48;
fn new(original_commit: &[u8]) -> Self {
let padding_insertion_point = Self::get_padding_insertion_point(original_commit);
let replaceable_padding_size = original_commit[padding_insertion_point..]
.iter()
.take_while(|&&byte| byte == b' ' || byte == b'\t')
.count();
let static_padding_length = Self::compute_static_padding_length(
padding_insertion_point,
original_commit.len() - replaceable_padding_size + Self::DYNAMIC_PADDING_LENGTH,
);
let commit_length = original_commit.len() - replaceable_padding_size
+ static_padding_length
+ Self::DYNAMIC_PADDING_LENGTH;
let mut data = format!("commit {}\0", commit_length).into_bytes();
let commit_range = data.len()..(data.len() + commit_length);
data.extend(&original_commit[..padding_insertion_point]);
data.resize(data.len() + static_padding_length, b' ');
assert_eq!(data.len() % 64, 0);
let num_static_blocks = data.len() / 64;
data.resize(data.len() + Self::DYNAMIC_PADDING_LENGTH, b'\t');
data.extend(&original_commit[padding_insertion_point + replaceable_padding_size..]);
assert_eq!(data.len(), commit_range.end);
data.extend(sha_finalization_padding(data.len()));
assert_eq!(data.len() % 64, 0);
Self {
data: data.into_boxed_slice(),
commit_range,
num_static_blocks,
}
}
fn get_padding_insertion_point(commit: &[u8]) -> usize {
let mut found_gpgsig_line = false;
const SIGNATURE_MARKER: &[u8] = b"-----END PGP SIGNATURE-----";
for index in 0..commit.len() {
if commit[index..].starts_with(b"\ngpgsig ")
|| commit[index..].starts_with(b"\ngpgsig-sha256 ")
{
found_gpgsig_line = true;
} else if !found_gpgsig_line && commit[index..].starts_with(b"\n\n") {
break;
} else if found_gpgsig_line && commit[index..].starts_with(SIGNATURE_MARKER) {
return index + SIGNATURE_MARKER.len();
}
}
commit.len()
- commit
.iter()
.rev()
.take_while(|&&byte| byte == b' ' || byte == b'\t' || byte == b'\n')
.count()
}
fn compute_static_padding_length(
commit_length_before_static_padding: usize,
commit_length_excluding_static_padding: usize,
) -> usize {
let compute_alignment = |padding_len: usize| {
(format!(
"commit {}\0",
commit_length_excluding_static_padding + padding_len
)
.len()
+ commit_length_before_static_padding
+ padding_len)
% 64
};
let prefix_length_estimate = format!("commit {}\0", commit_length_excluding_static_padding)
.len()
+ commit_length_before_static_padding;
let initial_padding_length_guess = (64 - prefix_length_estimate % 64) % 64;
let static_padding_length = if compute_alignment(initial_padding_length_guess) == 0 {
initial_padding_length_guess
} else if compute_alignment(initial_padding_length_guess - 1) == 0 {
initial_padding_length_guess - 1
} else {
initial_padding_length_guess + 63
};
assert_eq!(compute_alignment(static_padding_length), 0);
debug_assert!((0..static_padding_length).all(|len| compute_alignment(len) != 0));
static_padding_length
}
fn commit(&self) -> &[u8] {
&self.data[self.commit_range.clone()]
}
fn as_partially_hashed_commit<H: GitHashFn>(&mut self) -> PartiallyHashedCommit<H> {
let (static_blocks, dynamic_blocks) =
as_chunks_mut::<H>(&mut self.data[..]).split_at_mut(self.num_static_blocks);
let mut intermediate_state = H::INITIAL_STATE;
H::compress(&mut intermediate_state, static_blocks);
PartiallyHashedCommit {
intermediate_state,
dynamic_blocks,
}
}
}
impl<'a, H: GitHashFn> PartiallyHashedCommit<'a, H> {
#[inline(always)]
fn dynamic_padding_mut(&mut self) -> &mut [u8] {
&mut self.dynamic_blocks[0].as_mut()[..48]
}
#[inline(always)]
fn scatter_padding(&mut self, padding_specifier: u64) {
static PADDING_CHUNKS: [[u8; 8]; 256] = {
let mut padding_chunks = [[0; 8]; 256];
let mut i = 0;
while i < 256 {
let mut j = 0;
while j < 8 {
padding_chunks[i][j] = if i & (0x80 >> j) == 0 { b' ' } else { b'\t' };
j += 1;
}
i += 1;
}
padding_chunks
};
for (padding_chunk, &padding_specifier_byte) in self
.dynamic_padding_mut()
.chunks_exact_mut(8)
.zip(padding_specifier.to_le_bytes().iter())
{
padding_chunk.copy_from_slice(&PADDING_CHUNKS[padding_specifier_byte as usize]);
}
}
#[inline(always)]
fn current_hash(&self) -> H::State {
let mut hash = self.intermediate_state;
H::compress(&mut hash, self.dynamic_blocks);
hash
}
}
impl<H: GitHashFn> HashSpec<H> {
#[inline(always)]
fn matches(&self, hash: &H::State) -> bool {
hash.as_ref()
.iter()
.zip(self.mask.as_ref().iter())
.map(|(&hash_word, &mask_word)| hash_word & mask_word)
.zip(self.data.as_ref().iter())
.all(|(masked_hash_word, &hash_spec_word)| masked_hash_word == hash_spec_word)
}
#[cfg(feature = "opencl")]
fn estimated_attempts_needed(&self) -> u64 {
2u64.saturating_pow(
self.mask
.as_ref()
.iter()
.map(|word| word.count_ones())
.sum(),
)
}
}
impl<H: GitHashFn> FromStr for HashSpec<H> {
type Err = ParseHashSpecErr;
fn from_str(prefix_string: &str) -> Result<Self, Self::Err> {
let max_hex_character_length = mem::size_of::<H::State>() * 2;
if prefix_string.chars().count() > max_hex_character_length {
return Err(ParseHashSpecErr::TooLong);
}
let mut parsed_hash_spec = HashSpec::<H> {
data: H::State::default(),
mask: H::State::default(),
};
for ((hash_spec_chunk, data_word), mask_word) in prefix_string
.chars()
.chain(iter::repeat('_'))
.take(max_hex_character_length)
.collect::<Vec<_>>()
.chunks(8)
.zip(parsed_hash_spec.data.as_mut())
.zip(parsed_hash_spec.mask.as_mut())
{
for (&hash_spec_character, slot_bit_offset) in
hash_spec_chunk.iter().zip((0..32).step_by(4).rev())
{
if let Some(hex_character_value) = hash_spec_character.to_digit(16) {
*data_word |= hex_character_value << slot_bit_offset;
*mask_word |= 0xf << slot_bit_offset;
} else if hash_spec_character != '_' {
return Err(ParseHashSpecErr::InvalidCharacter(hash_spec_character));
}
}
}
Ok(parsed_hash_spec)
}
}
impl<H: GitHashFn> Default for HashSpec<H> {
fn default() -> Self {
"0000000".parse().unwrap()
}
}
impl Error for ParseHashSpecErr {}
impl Display for ParseHashSpecErr {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
match *self {
Self::TooLong => write!(f, "hash spec can't be longer than an actual hash"),
Self::InvalidCharacter(c) => write!(f, "hash spec contains invalid character '{}' (only hex characters and underscores are allowed)", c),
}
}
}
impl Debug for ParseHashSpecErr {
fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
<Self as Display>::fmt(self, f)
}
}
impl<H: GitHashFn> GitCommit<H> {
pub fn new(commit: &[u8]) -> Self {
Self {
object: commit.to_vec(),
hash: {
let mut state = H::INITIAL_STATE;
let commit_header = format!("commit {}\0", commit.len()).into_bytes();
let commit_data_length = commit_header.len() + commit.len();
H::compress(
&mut state,
as_chunks_mut::<H>(
commit_header
.into_iter()
.chain(commit.iter().cloned())
.chain(sha_finalization_padding(commit_data_length))
.collect::<Vec<_>>()
.as_mut(),
),
);
state
},
}
}
pub fn object(&self) -> &[u8] {
&self.object
}
pub fn hex_hash(&self) -> String {
self.hash
.as_ref()
.iter()
.map(|word| format!("{:08x}", word))
.collect()
}
}
#[cfg(feature = "opencl")]
fn encode_into_opencl_vector<H: GitHashFn>(data: H::Block) -> Uint16 {
let words: [u32; 16] = data
.as_ref()
.chunks(4)
.map(|chunk| u32::from_be_bytes(chunk.try_into().unwrap()))
.collect::<Vec<_>>()
.try_into()
.unwrap();
words.into()
}
fn as_chunks_mut<H: GitHashFn>(slice: &mut [u8]) -> &mut [H::Block] {
assert_eq!(mem::size_of::<H::Block>(), 64);
assert_eq!(mem::align_of::<H::Block>(), mem::align_of::<u8>());
assert_eq!(slice.len() % mem::size_of::<H::Block>(), 0);
unsafe {
std::slice::from_raw_parts_mut(
slice.as_mut_ptr().cast(),
slice.len() / mem::size_of::<H::Block>(),
)
}
}
fn sha_finalization_padding(data_length: usize) -> impl IntoIterator<Item = u8> {
iter::once(0x80)
.chain(iter::repeat(0).take((55 - data_length as isize).rem_euclid(64) as usize))
.chain(<[u8; 8]>::into_iter((data_length as u64 * 8).to_be_bytes()))
}
#[cfg(test)]
mod tests;