Skip to content

Instantly share code, notes, and snippets.

@upsuper

upsuper/Cargo.toml

Last active Jul 11, 2019
Embed
What would you like to do?
Verify whether there is any MD5 conflict in all possible Chinese mobile numbers https://twitter.com/upsuper/status/1148222832540672001
[package]
name = "cnmobile-md5"
version = "0.1.0"
authors = ["Xidorn Quan <me@upsuper.org>"]
edition = "2018"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[profile.release]
lto = true
[dependencies]
fnv = "1.0.6"
itertools = "0.8.0"
md5 = "0.6.1"
num_cpus = "1.10.1"
rayon = "1.1.0"
use fnv::FnvHashSet;
use itertools::Itertools;
use rayon::prelude::*;
use std::env;
use std::fmt::{self, Display};
use std::ops::RangeInclusive;
use std::thread;
const HASH_CUT: usize = 8;
fn main() {
let args: Vec<String> = env::args().collect();
assert_eq!(args.len(), 3);
const PHONE_RANGE: RangeInclusive<u64> = 13_000_000_000..=20_000_000_000;
let input_start = str::parse(&args[1]).expect("start phone number");
let input_end = str::parse(&args[2]).expect("end phone number");
assert!(input_start < input_end);
assert!(PHONE_RANGE.contains(&input_start));
assert!(PHONE_RANGE.contains(&input_end));
let input_len = input_end - input_start;
let cpu_num = num_cpus::get() as u64;
let range_for = |i: u64| {
let bound = |i| input_start + i * input_len / cpu_num;
bound(i)..bound(i + 1)
};
let threads = (0..cpu_num)
.map(|i| {
let range = range_for(i);
thread::spawn(move || {
let mut set =
FnvHashSet::with_capacity_and_hasher(range.clone().count(), Default::default());
let mut buf = [0u8; 11];
let mut hash = [0u8; HASH_CUT];
buf.copy_from_slice(range.start.to_string().as_bytes());
for m in range.clone() {
hash.copy_from_slice(&md5::compute(&buf).0[..HASH_CUT]);
if set.contains(&hash) {
println!(
"in range conflict: {}...{}: {}",
range.start,
m,
Digest(&hash)
);
} else {
set.insert(hash);
}
for digit in buf.iter_mut().rev() {
if *digit == b'9' {
*digit = b'0';
} else {
*digit += 1;
break;
}
}
}
(range, set)
})
})
.collect::<Vec<_>>();
let sets = threads
.into_iter()
.map(|thread| thread.join().unwrap())
.collect::<Vec<_>>();
let set_pairs = sets.iter().tuple_combinations().collect::<Vec<(_, _)>>();
set_pairs
.par_iter()
.for_each(|((range_a, set_a), (range_b, set_b))| {
println!("{:?} & {:?}", range_a, range_b);
if set_a.is_disjoint(set_b) {
return;
}
let intersection = set_a.intersection(set_b).collect::<Vec<_>>();
for item in intersection {
println!(
"conflict between {:?} and {:?}: {}",
range_a,
range_b,
Digest(item)
);
}
});
}
struct Digest<'a>(&'a [u8]);
impl Display for Digest<'_> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
for x in self.0 {
write!(f, "{:02x}", x)?;
}
Ok(())
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment