bramble-transport 0.1.0

//! BTP reordering windows

use super::{Keychain, RotateKeys};
use crate::{crypto::Tag, Error, Result};
use std::mem::swap;

/// A set of BTP reordering windows (for the previous, current, and next time periods)
pub struct ReorderingWindows {
    now: u64,
    previous: ReorderingWindow,
    current: ReorderingWindow,
    next: ReorderingWindow,
}

/// A stream identifier (a time period and a number)
#[derive(PartialEq, Eq, Copy, Clone, Debug)]
pub struct StreamId {
    pub period: u64,
    pub number: u64,
}

impl ReorderingWindows {
    /// Creates a set of reordering windows using the given period as current
    pub fn new<K>(now: u64, keys: &mut K) -> Result<Self>
    where
        K: RotateKeys,
    {
        Ok(Self {
            previous: ReorderingWindow::new(&keys.incoming_keys_for(now - 1)?),
            current: ReorderingWindow::new(&keys.incoming_keys_for(now)?),
            next: ReorderingWindow::new(&keys.incoming_keys_for(now + 1)?),
            now,
        })
    }

    /// Advances the windows to the given period
    pub fn advance_to<K>(&mut self, period: u64, keys: &mut K) -> Result<()>
    where
        K: RotateKeys,
    {
        if period < self.now - 1 {
            return Err(Error::TimePeriodIsPast);
        }
        while period > self.now {
            self.rotate(keys)?;
        }
        Ok(())
    }

    /// Rotates the windows once
    pub fn rotate<K>(&mut self, keys: &mut K) -> Result<()>
    where
        K: RotateKeys,
    {
        self.now += 1;
        self.previous = ReorderingWindow::new(&keys.incoming_keys_for(self.now + 1)?);
        swap(&mut self.previous, &mut self.current);
        swap(&mut self.current, &mut self.next);
        Ok(())
    }

    /// Finds a previously unseen tag and returns the corresponding stream identifier
    pub fn see<K>(&mut self, new_tag: Tag, keys: &mut K) -> Option<StreamId>
    where
        K: RotateKeys,
    {
        if let Some(number) = self
            .previous
            .see(new_tag, &keys.incoming_keys_for(self.now - 1).ok()?)
        {
            return Some(StreamId {
                number,
                period: self.now - 1,
            });
        }
        if let Some(number) = self
            .current
            .see(new_tag, &keys.incoming_keys_for(self.now).ok()?)
        {
            return Some(StreamId {
                number,
                period: self.now,
            });
        }
        if let Some(number) = self
            .next
            .see(new_tag, &keys.incoming_keys_for(self.now + 1).ok()?)
        {
            return Some(StreamId {
                number,
                period: self.now + 1,
            });
        }
        None
    }
}

/// A BTP reordering window
struct ReorderingWindow {
    tags: Vec<(Tag, bool)>,
    base_stream: u64,
}

impl ReorderingWindow {
    /// Creates a new BTP reordering window
    fn new(keys: &Keychain) -> Self {
        let mut window = Self {
            tags: vec![],
            base_stream: 0,
        };
        window.add_tags(WINDOW_LEN, keys);
        window
    }

    /// Finds a new unseen tag (and marks it seen), or returns None if it was already seen or unknown
    pub fn see(&mut self, new_tag: Tag, keys: &Keychain) -> Option<u64> {
        let pos = self.tags.iter().position(|&(tag, _)| tag == new_tag)?;
        let (_, seen) = &mut self.tags[pos];
        if *seen {
            return None;
        }
        *seen = true;
        let stream_number = self.base_stream + pos as u64;
        let upper_half_slide = if pos >= WINDOW_LEN / 2 {
            pos - WINDOW_LEN / 2
        } else {
            0
        };
        let lowest_slide = self.tags[upper_half_slide..]
            .iter()
            .position(|(_, seen)| !seen)
            .expect("reordering window exhausted");
        let to_slide = upper_half_slide + lowest_slide;
        if to_slide > 0 {
            self.tags.drain(..to_slide);
            self.base_stream += to_slide as u64;
            self.add_tags(to_slide, keys);
        }
        Some(stream_number)
    }

    fn add_tags(&mut self, n: usize, keys: &Keychain) {
        let n = n as u64;
        let start = self.base_stream + self.tags.len() as u64;
        let end = start + n;
        for i in start..end {
            let tag = Tag::new(keys.tag_key(), i);
            self.tags.push((tag, false));
        }
    }
}

const WINDOW_LEN: usize = 32;