Verify whether there is any MD5 conflict in all possible Chinese mobile numbers https://twitter.com/upsuper/status/1148222832540672001

Cargo.toml

[package]
name = "cnmobile-md5"
version = "0.1.0"
authors = ["Xidorn Quan <[email protected]>"]
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"

main.rs

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(())
    }
}