tiny_id 0.1.5

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

/// Compute the prime factors of a given number in ascending order.
///
/// This only needs to go up to the size of our alphabet, which will usually
/// be in the range of 25-50 characters, so we don't have to do anything
/// fancy, just use a loop to keep cutting the number down to size.
#[allow(clippy::mut_range_bound)]
fn factorize(mut n: u32) -> Vec<u32> {
    let mut result = Vec::new();
    'outer: while n > 1 {
        let last = result.last().cloned();
        for i in last.unwrap_or(2)..n {
            if n % i == 0 {
                if last != Some(i) {
                    result.push(i)
                }

                n /= i;
                continue 'outer;
            }

            if i * i > n {
                break;
            }
        }

        if result.last() != Some(&n) {
            result.push(n)
        }
        break;
    }

    result
}

/// Generate the multiplier used for the linear congruent multiplier.
/// `m_base` is assumed to be an n-th root of the actual `m`, with `n > 1`.
/// This has the implication that if `m_base` is even, it is assumed that
/// `m = m_base ^ n` is divisible by 4.
pub fn generate_a(m_base: u32) -> u32 {
    let factors = factorize(m_base);
    let mut prod = factors.into_iter().rfold(1, |lhs, rhs| lhs * rhs);

    // LCG calls for (a - 1) to be divisible by 4 if m is divisible
    // by 4. Since we are operating on the *base* m, i.e. m = m_base ^ l
    // with l > 1, m_base being even implies that m_base is divisible by 4.
    // In these cases prod is already even, so we double it to make it
    // divisible by 4.
    if m_base % 2 == 0 {
        prod *= 2
    }

    prod + 1
}

#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
#[derive(Clone, Debug)]
pub struct LinearCongruentMultiplier {
    /// The first value generated by this LCM.
    first: u64,

    /// The most recent value generated by this LCM.
    next: u64,

    /// The modulus.
    pub m: u64,

    /// The increment.
    c: u64,

    /// The multiplier.
    a: u64,

    exhausted: bool,
}

impl LinearCongruentMultiplier {
    pub fn new(seed: u64, m: u64, c: u64, a: u64) -> Self {
        Self {
            first: seed,
            next: seed,
            m,
            c,
            a,
            exhausted: false,
        }
    }

    /// Return the next value generated by the LCM, and update the
    /// internal state.
    pub fn next(&mut self) -> u64 {
        let value = self.next;

        self.next = (self.a * self.next + self.c) % self.m;

        if self.next == self.first {
            self.exhausted = true;
        }

        value
    }

    /// Returns `true` iff the next value that will be generated is
    /// equal to the first value that was returned. This is true
    /// when the LCM is intitially created.
    pub fn exhausted(&self) -> bool {
        self.exhausted
    }
}

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

    #[test]
    fn test_factorize() {
        assert_eq!(vec![2], factorize(2));
        assert_eq!(vec![3], factorize(3));
        assert_eq!(vec![2], factorize(4));

        assert_eq!(vec![2, 5], factorize(10));
        assert_eq!(vec![3, 5], factorize(15));

        assert_eq!(vec![3], factorize(27));
        assert_eq!(vec![3, 37], factorize(111));

        assert_eq!(vec![269], factorize(269));
    }

    #[test]
    fn test_generate_a() {
        assert_eq!(13, generate_a(6));

        // Not factorizable.
        assert_eq!(8, generate_a(7));

        // Not even.
        assert_eq!(34, generate_a(99));

        // Even.
        assert_eq!(53, generate_a(26));
    }
}