use crate::clock;
use crate::sha256::{hex, Sha256};
use std::fs;
use std::io::Write;
use std::path::{Path, PathBuf};
pub const ENTROPY_BITS: f64 = 256.0;
pub const ENTROPY_LABEL: &[u8] = b"radbeeper/entropy/1";
pub fn mcv_min_entropy(counts: &[u32]) -> f64 {
let n = counts.len();
if n < 2 {
return 0.0;
}
let mut freq = std::collections::HashMap::new();
for c in counts {
*freq.entry(*c).or_insert(0usize) += 1;
}
let most = freq.values().copied().max().unwrap_or(0);
let p = most as f64 / n as f64;
let upper = p + 2.576 * (p * (1.0 - p) / (n - 1) as f64).sqrt();
if upper >= 1.0 {
return 0.0;
}
-upper.log2()
}
pub fn poisson_min_entropy(rate: f64) -> f64 {
if rate <= 0.0 {
return 0.0;
}
let mut p = (-rate).exp();
let mut best = p;
for k in 1..(rate as i64 + 2) {
p *= rate / k as f64;
if p > best {
best = p;
}
}
if best >= 1.0 {
return 0.0;
}
-best.log2()
}
pub fn pack_counts(counts: &[u32]) -> String {
counts.iter().map(|c| format!("{:x}", (*c).min(15))).collect()
}
pub fn unpack_counts(text: &str) -> Vec<u32> {
text.chars().filter_map(|c| c.to_digit(16)).collect()
}
pub fn group_hex(text: &str) -> String {
text.as_bytes()
.chunks(8)
.map(|c| String::from_utf8_lossy(c).into_owned())
.collect::<Vec<_>>()
.join(" ")
}
pub struct Record {
pub seq: u64,
pub started: f64,
pub seconds: usize,
pub bits: f64,
pub rate: f64,
pub counts: String,
pub hex: String,
}
pub struct Entropy {
pub want: f64,
pub counts: Vec<u32>,
pub times: Vec<f64>,
pub started: Option<f64>,
pub total: u64,
pub seq: u64,
}
impl Default for Entropy {
fn default() -> Self {
Self::new(ENTROPY_BITS)
}
}
impl Entropy {
pub fn new(want: f64) -> Entropy {
Entropy {
want,
counts: Vec::new(),
times: Vec::new(),
started: None,
total: 0,
seq: 0,
}
}
pub fn reset(&mut self) {
self.counts.clear();
self.times.clear();
self.started = None;
self.total = 0;
}
pub fn add(&mut self, counts: u32) {
let now = clock::now();
self.add_at(now, counts);
}
pub fn add_at(&mut self, when: f64, counts: u32) {
if self.started.is_none() {
self.started = Some(when);
}
self.counts.push(counts);
self.times.push(when);
self.total += counts as u64;
}
pub fn rate(&self) -> f64 {
if self.counts.is_empty() {
0.0
} else {
self.total as f64 / self.counts.len() as f64
}
}
pub fn per_sample(&self) -> f64 {
mcv_min_entropy(&self.counts)
}
pub fn bits(&self) -> f64 {
self.per_sample() * self.counts.len() as f64
}
pub fn model_bits(&self) -> f64 {
poisson_min_entropy(self.rate()) * self.counts.len() as f64
}
pub fn ready(&self) -> bool {
self.bits() >= self.want
}
pub fn wait(&self) -> Option<i64> {
let per = self.per_sample();
if per <= 0.0 {
return None;
}
Some((((self.want - self.bits()) / per).ceil() as i64).max(0))
}
pub fn digest(&self, seq: u64) -> String {
let mut h = Sha256::new();
h.update(ENTROPY_LABEL);
h.update(
format!("\0{}\0{}\0", seq, self.started.unwrap_or(0.0) as i64)
.as_bytes(),
);
h.update(pack_counts(&self.counts).as_bytes());
hex(&h.finish())
}
pub fn frame(&self, seq: u64, suspect: bool) -> Frame {
let mut samples = Vec::with_capacity(self.counts.len());
let mut prev: Option<f64> = None;
for (i, count) in self.counts.iter().enumerate() {
let when = self.times.get(i).copied();
let gap = match (prev, when) {
(None, _) => 0,
(Some(p), Some(w)) => ((w - p).round().max(0.0)) as u32,
(Some(_), None) => 1,
};
if when.is_some() {
prev = when;
} else if let Some(p) = prev {
prev = Some(p + 1.0);
}
samples.push((gap, *count));
}
Frame {
seq,
started: self.started.unwrap_or(0.0) as i64,
suspect,
samples,
key: self.digest(seq),
}
}
pub fn draw(&mut self) -> (String, Record) {
let seq = self.seq;
let out = self.digest(seq);
let record = Record {
seq,
started: self.started.unwrap_or(0.0),
seconds: self.counts.len(),
bits: self.bits(),
rate: self.rate(),
counts: pack_counts(&self.counts),
hex: out.clone(),
};
self.seq += 1;
self.reset();
(out, record)
}
}
pub fn check_record(seq: u64, started: f64, counts: &[u32], want: &str) -> bool {
let mut e = Entropy::default();
e.started = Some(started);
e.counts = counts.to_vec();
e.total = counts.iter().map(|c| *c as u64).sum();
e.digest(seq) == want
}
pub fn pool_status(pool: &Entropy, prefix: &str) -> String {
match pool.wait() {
Some(left) => format!("{}{}s", prefix, left),
None if pool.counts.is_empty() => "no counts yet".to_string(),
None => format!("measuring the source ({}s)", pool.counts.len()),
}
}
pub fn write_record(dir: &Path, record: &Record, serial: &str, suspect: bool)
-> std::io::Result<PathBuf>
{
let path = dir.join(format!("random-{}.tsv", if serial.is_empty() {
"unknown"
} else {
serial
}));
let fresh = fs::metadata(&path).map(|m| m.len() == 0).unwrap_or(true);
let mut f = fs::OpenOptions::new().create(true).append(true).open(&path)?;
if fresh {
writeln!(f, "#seq\ttime\tseconds\trate\tbits\tflat\thex\tcounts")?;
}
writeln!(
f,
"{}\t{}\t{}\t{:.4}\t{:.1}\t{}\t{}\t{}",
record.seq,
clock::stamp(record.started),
record.seconds,
record.rate,
record.bits,
if suspect { "no" } else { "yes" },
record.hex,
record.counts
)?;
write_hex(dir, &record.hex, serial)?;
Ok(path)
}
pub fn write_hex(dir: &Path, hex: &str, serial: &str) -> std::io::Result<PathBuf> {
let path = dir.join(format!("random-{}.hex", if serial.is_empty() {
"unknown"
} else {
serial
}));
let mut f = fs::OpenOptions::new().create(true).append(true).open(&path)?;
writeln!(f, "{} {}", clock::stamp(clock::now()), hex)?;
Ok(path)
}
pub const FRAME_MAGIC: &[u8; 4] = b"RBF1";
const FRAME_ESCAPE: u8 = 0xFE;
const FRAME_INLINE_MAX: u32 = 0xFD;
fn put_varint(out: &mut Vec<u8>, mut v: u64) {
loop {
let byte = (v & 0x7f) as u8;
v >>= 7;
if v == 0 {
out.push(byte);
return;
}
out.push(byte | 0x80);
}
}
fn get_varint(buf: &[u8], at: &mut usize) -> Option<u64> {
let mut v = 0u64;
let mut shift = 0;
loop {
let b = *buf.get(*at)?;
*at += 1;
v |= ((b & 0x7f) as u64) << shift;
if b & 0x80 == 0 {
return Some(v);
}
shift += 7;
if shift > 63 {
return None;
}
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct Frame {
pub seq: u64,
pub started: i64,
pub suspect: bool,
pub samples: Vec<(u32, u32)>,
pub key: String,
}
impl Frame {
pub fn counts(&self) -> Vec<u32> {
self.samples.iter().map(|(_, c)| *c).collect()
}
pub fn seconds(&self) -> u64 {
self.samples.iter().map(|(g, _)| *g as u64).sum()
}
pub fn verifies(&self) -> bool {
check_record(self.seq, self.started as f64, &self.counts(), &self.key)
}
pub fn encode(&self) -> Vec<u8> {
let mut out = Vec::with_capacity(32 + self.samples.len() + 48);
out.extend_from_slice(FRAME_MAGIC);
out.push(if self.suspect { 1 } else { 0 });
put_varint(&mut out, self.seq);
put_varint(&mut out, self.started.max(0) as u64);
put_varint(&mut out, self.samples.len() as u64);
for (gap, count) in &self.samples {
if *gap == 1 && *count <= FRAME_INLINE_MAX {
out.push(*count as u8);
} else {
out.push(FRAME_ESCAPE);
put_varint(&mut out, *gap as u64);
put_varint(&mut out, *count as u64);
}
}
let key = hex_bytes(&self.key);
put_varint(&mut out, key.len() as u64);
out.extend_from_slice(&key);
out
}
pub fn decode(buf: &[u8]) -> Option<(Frame, usize)> {
if buf.len() < 5 || &buf[..4] != FRAME_MAGIC {
return None;
}
let mut at = 4;
let suspect = buf[at] != 0;
at += 1;
let seq = get_varint(buf, &mut at)?;
let started = get_varint(buf, &mut at)? as i64;
let n = get_varint(buf, &mut at)? as usize;
if n > buf.len() {
return None;
}
let mut samples = Vec::with_capacity(n);
for _ in 0..n {
let tag = *buf.get(at)?;
at += 1;
if tag == FRAME_ESCAPE {
let gap = get_varint(buf, &mut at)? as u32;
let count = get_varint(buf, &mut at)? as u32;
samples.push((gap, count));
} else if tag == 0xFF {
return None;
} else {
samples.push((1, tag as u32));
}
}
let klen = get_varint(buf, &mut at)? as usize;
if klen > buf.len().saturating_sub(at) {
return None;
}
let key = hex(&buf[at..at + klen]);
at += klen;
Some((Frame { seq, started, suspect, samples, key }, at))
}
}
fn hex_bytes(text: &str) -> Vec<u8> {
let d: Vec<u8> = text
.bytes()
.filter_map(|c| (c as char).to_digit(16).map(|v| v as u8))
.collect();
d.chunks(2).filter(|p| p.len() == 2).map(|p| (p[0] << 4) | p[1]).collect()
}
pub fn write_frame(dir: &Path, frame: &Frame, serial: &str) -> std::io::Result<PathBuf> {
let path = dir.join(format!("random-{}.bin", if serial.is_empty() {
"unknown"
} else {
serial
}));
let mut f = fs::OpenOptions::new().create(true).append(true).open(&path)?;
f.write_all(&frame.encode())?;
f.flush()?;
Ok(path)
}
pub fn read_frames(path: &Path) -> Vec<Frame> {
let Ok(buf) = fs::read(path) else { return Vec::new() };
let mut out = Vec::new();
let mut at = 0usize;
while at + 4 <= buf.len() {
match Frame::decode(&buf[at..]) {
Some((f, used)) if used > 0 && ends_cleanly(&buf, at + used) => {
out.push(f);
at += used;
}
_ => {
at += 1;
while at + 4 <= buf.len() && &buf[at..at + 4] != FRAME_MAGIC {
at += 1;
}
}
}
}
out
}
fn ends_cleanly(buf: &[u8], at: usize) -> bool {
at == buf.len() || (at + 4 <= buf.len() && &buf[at..at + 4] == FRAME_MAGIC)
}
pub struct Emission {
pub seq: u64,
pub time: String,
pub seconds: usize,
pub rate: f64,
pub bits: f64,
pub flat: bool,
pub hex: String,
pub counts: Vec<u32>,
}
pub fn read_emissions(path: &Path) -> Vec<Emission> {
let text = match fs::read_to_string(path) {
Ok(t) => t,
Err(_) => return Vec::new(),
};
let mut out = Vec::new();
for line in text.lines() {
if line.starts_with('#') || line.trim().is_empty() {
continue;
}
let c: Vec<&str> = line.split('\t').collect();
if c.len() < 8 {
continue;
}
let parsed = (|| {
Some(Emission {
seq: c[0].parse().ok()?,
time: c[1].to_string(),
seconds: c[2].parse().ok()?,
rate: c[3].parse().ok()?,
bits: c[4].parse().ok()?,
flat: c[5] == "yes",
hex: c[6].to_string(),
counts: if c[7].chars().all(|ch| ch.is_ascii_hexdigit()) {
unpack_counts(c[7])
} else {
return None;
},
})
})();
if let Some(e) = parsed {
out.push(e);
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
struct Rng(u32);
impl Rng {
fn next(&mut self, n: u32) -> u32 {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 17;
self.0 ^= self.0 << 5;
self.0 % n
}
}
#[test]
fn the_worth_of_a_sample_is_measured_not_modelled() {
let even: Vec<u32> = (0..400).map(|i| i % 4).collect();
assert!(mcv_min_entropy(&even) > 1.5);
let mut lumpy = vec![0u32; 300];
lumpy.extend(std::iter::repeat(6u32).take(100));
assert!(mcv_min_entropy(&lumpy) < mcv_min_entropy(&even));
assert_eq!(mcv_min_entropy(&[0, 1]), 0.0);
assert_eq!(mcv_min_entropy(&[]), 0.0);
}
#[test]
fn a_counter_stuck_at_one_count_a_second_earns_nothing() {
let mut pool = Entropy::default();
for _ in 0..3600 {
pool.add(1);
}
assert_eq!(pool.bits(), 0.0);
assert!(!pool.ready());
assert_eq!(pool.wait(), None);
assert!(pool.model_bits() > 256.0, "the model would have called this good");
}
#[test]
fn a_dead_counter_never_becomes_ready() {
let mut pool = Entropy::default();
for _ in 0..3600 {
pool.add(0);
}
assert_eq!(pool.bits(), 0.0);
assert!(!pool.ready());
}
#[test]
fn it_will_not_hand_over_bits_it_has_not_earned() {
let mut rng = Rng(11);
let mut pool = Entropy::default();
for _ in 0..50 {
pool.add(rng.next(4));
}
assert!(!pool.ready());
assert!(pool.wait().unwrap() > 0);
for _ in 0..350 {
pool.add(rng.next(4));
}
assert!(pool.ready());
}
#[test]
fn the_countdown_only_ever_overruns() {
let mut rng = Rng(5);
let mut pool = Entropy::default();
let mut quoted = None;
let mut served = 0i64;
while !pool.ready() {
pool.add(rng.next(4));
served += 1;
if quoted.is_none() && served == 60 {
quoted = Some(pool.wait().unwrap() + served);
}
assert!(served < 5000, "the pool never filled");
}
assert!(quoted.unwrap() >= served);
}
#[test]
fn the_line_is_64_hex_characters() {
let mut pool = Entropy::default();
for i in 0..400u32 {
pool.add(i % 3);
}
let (text, _record) = pool.draw();
assert_eq!(text.len(), 64);
assert!(text.chars().all(|c| c.is_ascii_hexdigit() && !c.is_uppercase()));
}
#[test]
fn drawing_a_line_empties_the_pool_and_moves_the_sequence_on() {
let mut pool = Entropy::default();
for i in 0..400u32 {
pool.add(i % 3);
}
let (_t, r) = pool.draw();
assert_eq!(r.seq, 0);
assert_eq!(r.seconds, 400);
assert!(pool.counts.is_empty());
assert_eq!(pool.started, None);
assert_eq!(pool.seq, 1);
}
#[test]
fn a_line_can_be_recomputed_from_what_was_written_beside_it() {
let mut pool = Entropy::default();
for i in 0..400u32 {
pool.add((i * 7) % 4);
}
let (_t, r) = pool.draw();
let counts = unpack_counts(&r.counts);
assert!(check_record(r.seq, r.started, &counts, &r.hex));
let mut tampered = counts.clone();
tampered[0] = if tampered[0] == 1 { 2 } else { 1 };
assert!(!check_record(r.seq, r.started, &tampered, &r.hex));
assert!(!check_record(r.seq + 1, r.started, &counts, &r.hex));
}
#[test]
fn counts_pack_to_one_nibble_and_clamp_at_fifteen() {
assert_eq!(pack_counts(&[0, 1, 10, 15]), "01af");
assert_eq!(pack_counts(&[16, 99, 4000]), "fff",
"a second with sixteen counts is not doing the work here");
assert_eq!(unpack_counts("01af"), vec![0, 1, 10, 15]);
assert_eq!(unpack_counts(""), Vec::<u32>::new());
}
#[test]
fn a_quiet_minute_of_background_costs_a_byte_a_second() {
let mut pool = Entropy::default();
let t0 = 1_700_000_000.0;
for i in 0..60 {
pool.add_at(t0 + i as f64, (i % 4) as u32);
}
let frame = pool.frame(7, false);
let bytes = frame.encode();
assert_eq!(frame.samples.len(), 60);
assert!(bytes.len() < 60 + 48, "{} bytes for a minute", bytes.len());
assert!(bytes.len() * 5 < 60 * 12, "{} vs {}", bytes.len(), 60 * 12);
}
#[test]
fn a_frame_round_trips_through_its_own_encoding() {
let mut pool = Entropy::default();
let t0 = 1_700_000_000.0;
for i in 0..10 {
pool.add_at(t0 + i as f64, i as u32);
}
pool.add_at(t0 + 25.0, 9000);
pool.add_at(t0 + 26.0, 300);
let frame = pool.frame(3, true);
let bytes = frame.encode();
let (back, used) = Frame::decode(&bytes).expect("decodes");
assert_eq!(used, bytes.len(), "the whole frame was consumed");
assert_eq!(back, frame);
assert!(back.suspect);
assert_eq!(back.counts()[10], 9000);
assert_eq!(back.counts()[11], 300);
assert_eq!(back.samples[10].0, 16);
assert_eq!(back.seconds(), 26);
}
#[test]
fn a_frame_recomputes_the_key_it_was_written_with() {
let mut pool = Entropy::default();
let t0 = 1_700_000_000.0;
for i in 0..40 {
pool.add_at(t0 + i as f64, (i * 7 % 5) as u32);
}
let frame = pool.frame(pool.seq, false);
assert!(frame.verifies(), "the frame does not produce its own key");
let drawn = pool.draw().0;
assert_eq!(frame.key, drawn);
let mut tampered = frame.clone();
tampered.samples[5].1 += 1;
assert!(!tampered.verifies(), "a changed count still verified");
}
#[test]
fn a_damaged_file_still_yields_the_frames_around_the_damage() {
let dir = std::env::temp_dir()
.join(format!("radbeeper-frames-{}", std::process::id()));
let _ = fs::remove_dir_all(&dir);
fs::create_dir_all(&dir).unwrap();
let mut whole: Vec<Frame> = Vec::new();
for seq in 0..3u64 {
let mut pool = Entropy::default();
let t0 = 1_700_000_000.0 + seq as f64 * 1000.0;
for i in 0..20 {
pool.add_at(t0 + i as f64, (seq as u32 + i as u32) % 6);
}
let f = pool.frame(seq, false);
write_frame(&dir, &f, "F48824B8207F7E").unwrap();
whole.push(f);
}
let path = dir.join("random-F48824B8207F7E.bin");
assert_eq!(read_frames(&path), whole);
let mut buf = fs::read(&path).unwrap();
let second = buf
.windows(4)
.enumerate()
.filter(|(_, w)| *w == FRAME_MAGIC)
.map(|(i, _)| i)
.nth(1)
.unwrap();
buf[second + 8] ^= 0xFF;
buf[second + 9] ^= 0xFF;
fs::write(&path, &buf).unwrap();
let got = read_frames(&path);
assert!(got.contains(&whole[0]), "the frame before the damage was lost");
assert!(got.contains(&whole[2]), "the frame after the damage was lost");
fs::write(&path, &buf[..buf.len() - 9]).unwrap();
assert!(read_frames(&path).contains(&whole[0]));
let _ = fs::remove_dir_all(&dir);
}
#[test]
fn hex_is_grouped_so_it_can_be_read_aloud() {
let g = group_hex(&"a".repeat(64));
assert_eq!(g.split(' ').count(), 8);
assert!(g.split(' ').all(|b| b.len() == 8));
}
#[test]
fn the_status_line_gives_each_state_its_own_words() {
let mut pool = Entropy::default();
assert_eq!(pool_status(&pool, "next in "), "no counts yet");
pool.add(1);
pool.add(0);
assert_eq!(pool_status(&pool, "next in "), "measuring the source (2s)");
let mut rng = Rng(3);
for _ in 0..200 {
pool.add(rng.next(4));
}
assert!(pool_status(&pool, "next in ").starts_with("next in "));
}
}