Build Monotonic Sortable ULID Strings

use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::Mutex;
use std::time::{SystemTime, UNIX_EPOCH};

const ALPHABET: &[u8; 32] = b"0123456789ABCDEFGHJKMNPQRSTVWXYZ";
const MAX_RANDOM: u128 = (1u128 << 80) - 1;

static STATE: Mutex<Option<(u64, u128)>> = Mutex::new(None);
static COUNTER: AtomicU64 = AtomicU64::new(0);

fn splitmix64(state: &mut u64) -> u64 {
    *state = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
    let mut value = *state;
    value = (value ^ (value >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
    value = (value ^ (value >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
    value ^ (value >> 31)
}

fn encode(mut value: u128, length: usize) -> String {
    let mut characters = vec![b'0'; length];
    for index in (0..length).rev() {
        characters[index] = ALPHABET[(value & 31) as usize];
        value >>= 5;
    }
    String::from_utf8(characters).expect("alphabet is ASCII")
}

fn new_ulid() -> String {
    let millis = SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .expect("system clock is before the Unix epoch")
        .as_millis() as u64;

    let mut guard = STATE.lock().expect("ULID state poisoned");
    let randomness = match *guard {
        Some((last_millis, last_random)) if last_millis == millis => {
            last_random.wrapping_add(1) & MAX_RANDOM
        }
        _ => {
            let sequence = COUNTER.fetch_add(1, Ordering::Relaxed);
            let mut seed = millis ^ sequence.rotate_left(17) ^ 0x9E37_79B9_7F4A_7C15;
            let high = splitmix64(&mut seed);
            let low = splitmix64(&mut seed);
            (((high as u128) << 64) | (low as u128)) >> 48
        }
    };
    *guard = Some((millis, randomness));

    let value = ((millis as u128) << 80) | randomness;
    encode(value, 26)
}

fn main() {
    let first = new_ulid();
    let second = new_ulid();
    println!("{first}\n{second}");
    assert_eq!(first.len(), 26);
    assert!(first < second, "ULIDs should sort in creation order");
    assert!(first.bytes().all(|byte| ALPHABET.contains(&byte)));

    let identifiers: Vec<String> = (0..100).map(|_| new_ulid()).collect();
    assert!(identifiers.windows(2).all(|pair| pair[0] < pair[1]));
}