I came up with an algorithm and created a Rust implementation of it.
I've already posted it for code review previously but created another post since I've made many changes to it, including the ones suggested in response to my previous post.
I've also added some new functionality and would like to ensure the code is of sufficient quality before releasing it on Crates.io and GitHub.
Here's my previous post:
RANDEVU - Rust crate implementing a simple algorithm I invented
I'm eager to hear your feedback and thoughts and am open to ANY suggestions that may help me improve the code further.
The code should be performant, clean, easy to use, idiomatic, etc.
I'm also looking for potentially better names for certain variables and stuff.
Feel free to suggest edits/edit the post itself if you think it can be improved.
You can find more info about the algorithm and its purpose here: https://github.com/TypicalHog/randevu
Note that some things have changed a bit since the last release (for example - the hash calculation has been changed from blake3(blake3(OBJECT) || blake3(DATE)) to blake3::keyed_hash(DATE, OBJECT) to improve performance by eliminating 2 out of 3 hash calculations), but the README is still valid (and hopefully at least somewhat decent source of info about the algorithm - I did my best trying to explain stuff, but I'm still looking to improve it further in the future).
The functions can panic if they are given a date where the year is outside of the 0000 to 9999 range.
I'm not sure if I should make the function return the result instead of panicking since I'd like to avoid having to unwrap() the output and would prefer if the function returned just a simple u32/chrono::NaiveTime (but I'm open to changing my mind on this one).
The newest function rdvt() is not yet documented on GitHub or Crates.io, but I'll do my best to explain it here:
In addition to an object and a date (same as rdv()), it also takes a rank (which is a positive integer - u32).
The function calculates the keyed blake3 hash of an object, using the date and a rank as key, and uses the resulting (pseudorandom) bits to generate and return a random uniform time (chrono::NaiveTime) between 0h and 24h (down to nanosecond precision).
Time is calculated by taking the first bit of the hash and in case it's a binary one - 12h is added to the time, then we add 6h if the 2nd bit of the hash is a one, 3h for the 3rd bit, 1.5h for 4th and so on until the increment reaches the small enough value where it doesn't contribute anything to the time (when it becomes less than 1ns, essentially).
This means if all of the bits in the hash were zeros - time would be zero, and if they were all ones - time would be 23:59:59:999:999:999h (the very last and highest possible value).
Here's the formula that describes how the returned time is calculated (note that the actual code short-circuits and stops earlier than going through all 256 bits since we only ever need around 46 bits before the increment becomes smaller than 1ns (the code stops only in case the sum of tiny sub 1ns increments can't contribute enough to change the last digit in the total time (even if all of the rest of the bits in the hash were to be ones))): $$time = \sum_{i=1}^{256} bits_i*\frac{12h}{i}$$
Feel free to ask ANY questions regarding the code, the algorithm, its function, use cases, or anything else you'd like explained or clarified.
Here's the code (I haven't written any tests yet, so they are not included for review):
//! The official Rust implementation of the [RANDEVU](https://github.com/TypicalHog/randevu) algorithm
//!
//! # Example
//! ```rust
//! use chrono::Utc;
//! use randevu::rdv;
//!
//! fn main() {
//! let object = "THE_SIMPSONS";
//! let date = Utc::now().date_naive();
//! let rdv = rdv(object, &date);
//!
//! println!("Object {} has RDV{} today", object, rdv);
//! }
//! ```
use blake3;
use chrono;
use itoa;
/// Creates a 32-byte KEY `[u8; 32]` from a given DATE `&chrono::NaiveDate`
/// **Note:** Panics if the year is not between 0000 and 9999
fn create_key(date: &chrono::NaiveDate) -> [u8; 32] {
let mut year = chrono::Datelike::year(date);
let mut month = chrono::Datelike::month(date);
let mut day = chrono::Datelike::day(date);
if year < 0 || year > 9999 {
panic!("year must be between 0000 and 9999");
}
let mut key = [0u8; 32];
// Write ISO 8601 formatted date (YYYY-MM-DD) into key
key[9] = '0' as u8 + (day % 10) as u8;
day /= 10;
key[8] = '0' as u8 + day as u8;
key[7] = '-' as u8;
key[6] = '0' as u8 + (month % 10) as u8;
month /= 10;
key[5] = '0' as u8 + month as u8;
key[4] = '-' as u8;
key[3] = '0' as u8 + (year % 10) as u8;
year /= 10;
key[2] = '0' as u8 + (year % 10) as u8;
year /= 10;
key[1] = '0' as u8 + (year % 10) as u8;
year /= 10;
key[0] = '0' as u8 + year as u8;
key
}
/// Returns RDV value `u32` for an OBJECT `&str` on a specific DATE `&chrono::NaiveDate`
/// **Note:** Panics if the year is not between 0000 and 9999
///
/// **RDV = number of leading zero bits in blake3::keyed_hash(DATE, OBJECT)**
pub fn rdv(object: &str, date: &chrono::NaiveDate) -> u32 {
let hash = blake3::keyed_hash(&create_key(date), object.as_bytes());
let mut rdv = 0;
for &byte in hash.as_bytes() {
rdv += byte.leading_zeros();
if byte != 0 {
break;
}
}
rdv
}
/// Returns RDVT time `chrono::NaiveTime` of a given RANK `u32` for an OBJECT `&str` on a specific DATE `&chrono::NaiveDate`
/// **Note:** Panics if the year is not between 0000 and 9999
pub fn rdvt(object: &str, date: &chrono::NaiveDate, rank: u32) -> chrono::NaiveTime {
let mut key = create_key(date);
key[10] = '_' as u8;
let mut buffer = itoa::Buffer::new();
let rank_str = buffer.format(rank);
key[11..11 + rank_str.len()].copy_from_slice(&rank_str.as_bytes()[..rank_str.len()]);
let hash = blake3::keyed_hash(&key, object.as_bytes());
let mut total: f64 = 0.0;
let mut increment: f64 = 12.0 * 60.0 * 60.0 * 1_000_000_000.0;
for (i, byte) in hash.as_bytes().iter().enumerate() {
for j in (0..8).rev() {
let bit = (byte >> j) & 1;
if bit == 1 {
total += increment;
}
increment /= 2.0;
}
if i > 4 {
if 1.0 - total.fract() > 2.0 * increment {
break;
}
}
}
let rdvt = chrono::NaiveTime::MIN + chrono::TimeDelta::nanoseconds(total as i64);
rdvt
}
UPDATE:
I've done a full overhaul of the code and updated the post to be in line with that.
Here's the full text of the old post for those interested:
https://pastebin.com/6xbjFSFe