1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107

#![no_std]
//! A function to calculate [lipmaa](https://github.com/AljoschaMeyer/bamboo/blob/master/README.md#links-and-entry-verification) sequence numbers.
//!
//! From the bamboo spec: "The lipmaalinks are chosen such that for any pair of entries there is a path from the newer to the older one of a length logarithmic in their distance."
//!
//! ```
//! use lipmaa_link::lipmaa;
//!
//! let result = lipmaa(13);
//! assert_eq!(result, 4);
//! ```
//!

/// Calculates the lipmaa link number given the current sequence number.
#[no_mangle]
pub extern "C" fn lipmaa(n: u64) -> u64 {
    let mut m: u128 = 1;
    let mut po3: u128 = 3;
    let mut u: u128 = n as u128;

    // find k such that (3^k - 1)/2 >= n
    while m < n as u128 {
        po3 *= 3;
        m = (po3 - 1) / 2;
    }

    // find longest possible backjump
    po3 /= 3;
    if m != n as u128 {
        while u != 0 {
            m = (po3 - 1) / 2;
            po3 /= 3;
            u %= m;
        }

        if m != po3 {
            po3 = m;
        }
    }

    return n - po3 as u64;
}
#[cfg(test)]
mod tests {

    use crate::lipmaa;

    #[test]
    fn lipmaa_is_ok() {
        let actual_expecteds = [
            (1, 0),
            (2, 1),
            (3, 2),
            (4, 1),
            (5, 4),
            (6, 5),
            (7, 6),
            (8, 4),
            (9, 8),
            (10, 9),
            (11, 10),
            (12, 8),
            (13, 4),
            (14, 13),
            (15, 14),
            (16, 15),
            (17, 13),
            (18, 17),
            (19, 18),
            (20, 19),
            (21, 17),
            (22, 21),
            (23, 22),
            (24, 23),
            (25, 21),
            (26, 13),
            (27, 26),
            (28, 27),
            (29, 28),
            (30, 26),
            (31, 30),
            (32, 31),
            (33, 32),
            (34, 30),
            (35, 34),
            (36, 35),
            (37, 36),
            (38, 34),
            (39, 26),
            (40, 13),
            (121, 40),
        ];

        actual_expecteds
            .iter()
            .for_each(|(n, expected)| assert_eq!(lipmaa(*n), *expected))
    }

    #[test]
    fn largest_n_u32() {
        assert_eq!(lipmaa(core::u32::MAX as u64), 4294967294);
    }
    #[test]
    fn largest_n_u64_no_explode() {
        lipmaa(core::u64::MAX);
    }
}