6
\$\begingroup\$

As a hobby project (and to learn the language), I'm working on a crypto library in Rust. The following is a component thereof, which implements encryption with and the cracking of the Caesar cipher.

My primary interest is whether the code follows best practices, with a secondary concern regarding its efficiency. I'm not very used to Rust idioms, and there are a few places where I feel that the code is clunky, but can't see a better solution.

Note that:

  • this being a hobby project, I aim to write most everything myself and avoid external libraries;
  • as this is part of a larger (as yet unwritten) framework, I have generalised more than necessary for this component alone. If it seems over-engineered, that would be because it has been designed for easy implementation of other [poly]alphabetic ciphers, like a more general substitution cipher or the Vigenère cipher.

lib.rs

#![feature(const_option)]
pub mod alphabetic;
pub mod caesar;
pub mod frequency;

alphabetic.rs

///Provides various types for dealing with alphabetic ciphers, like
///the Caesar and Vigenère ciphers.
use std::{
    cmp::{self, Ordering},
    fmt::{self, Display},
    ops::{Add, Sub},
};
pub const ALPHABET_SIZE: usize = 26;
#[derive(Copy, Clone, Debug)]
pub enum Case {
    Upper,
    Lower,
}
#[derive(Copy, Clone, Debug)]
///Contains a `value` (zero-indexed and guaranteed to be in the range 0-25) and
/// a `Case` specifying the case. The case is only used for display purposes,
/// and when cases are mixed in arithmetic operations, the output favours
///`Case::Upper` (so if one letter is uppercase, the result will also be
/// uppercase); this ensures that addition is at least commutative.
pub struct Letter {
    pub value: u8,
    pub case: Case,
}
impl Letter {
    ///Constructs a new `Letter` from its `u8` and `Case` components.
    pub const fn new(value: u8, case: Case) -> Letter {
        Letter {
            value: (value) % ALPHABET_SIZE as u8,
            case,
        }
    }
    ///Constructs a new `Letter`, accepting a negative alphabetical index
    ///(which will wrap around).
    pub fn from_signed(value: i8, case: Case) -> Letter {
        Letter {
            //rem_euclid returns nonnegative integers so this cast is safe
            value: value.rem_euclid(ALPHABET_SIZE as i8) as u8,
            case,
        }
    }
    ///Returns the `Letter` corresponding to a given `char`, or `None` if
    ///the `char` is out of the alphabetical ASCII range.
    pub const fn try_from_char(char_value: char) -> Option<Letter> {
        let (start, case) = match char_value {
            'A'..='Z' => ('A' as u32, Case::Upper),
            'a'..='z' => ('a' as u32, Case::Lower),
            _ => return None,
        };
        Some(Letter::new((char_value as u32 - start) as u8, case))
    }
    ///Returns the `Letter` corresponding to a given byte, or `None` if the
    ///byte is out of the alphabetical ASCII range.
    pub fn try_from_utf8(byte_value: u8) -> Option<Letter> {
        let (start, case) = match byte_value {
            0x41..=0x5A => (0x41, Case::Upper),
            0x61..=0x7A => (0x61, Case::Lower),
            _ => return None,
        };
        Some(Letter::new(byte_value - start, case))
    }
    ///Returns the `char` corresponding to the alphabetical character specified
    ///by `self.value` and `self.case`. Returns `None` if this fails, but that
    ///could only happen if `self.value` where out of its correct range (0-25).
    ///Typically we can be sure that is not the case, so we can `unwrap` the
    /// result, or use the `unsafe` `to_char_unchecked` if speed is
    /// required.
    pub fn try_to_char(&self) -> Option<char> {
        char::from_u32(match self.case {
            Case::Upper => self.value as u32 + 'A' as u32,
            Case::Lower => self.value as u32 + 'a' as u32,
        })
    }
    ///# Safety
    ///This should be safe in all circumstances, since `from_u32_unchecked`
    ///could only fail if the value is out of ASCII range. So long as our
    ///range guarantee on `self.value` (0-25) is met, the corresponding `u32`
    ///will be in range.
    pub unsafe fn to_char_unchecked(&self) -> char {
        char::from_u32_unchecked(match self.case {
            Case::Upper => self.value as u32 + 'A' as u32,
            Case::Lower => self.value as u32 + 'a' as u32,
        })
    }
    ///Returns the (ASCII) byte corresponding to the character specified by
    ///`self.value` and `self.case`.
    pub fn to_utf8(&self) -> u8 {
        match self.case {
            Case::Upper => self.value + 0x41,
            Case::Lower => self.value + 0x61,
        }
    }
    ///Returns `Case::Lower` iff both inputs are lowercase, and `Case::Upper`
    ///otherwise. Used internally to decide which case to give the result of an
    /// arithmetic operation on two `Letter`s.
    fn combined_case(case1: Case, case2: Case) -> Case {
        match (case1, case2) {
            (Case::Lower, Case::Lower) => Case::Lower,
            _ => Case::Upper,
        }
    }
}
///`Letters` add their values, wrapping around the alphabet if necessary.
impl Add<Letter> for Letter {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        Self::new(
            self.value + rhs.value,
            Letter::combined_case(self.case, rhs.case),
        )
    }
}
impl Add<i8> for Letter {
    type Output = Self;
    fn add(self, rhs: i8) -> Self {
        Self::from_signed(self.value as i8 + rhs, self.case)
    }
}
impl Sub<Letter> for Letter {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        Self::from_signed(
            self.value as i8 - rhs.value as i8,
            Letter::combined_case(self.case, rhs.case),
        )
    }
}
impl Sub<i8> for Letter {
    type Output = Self;
    fn sub(self, rhs: i8) -> Self {
        Self::from_signed(self.value as i8 - rhs, self.case)
    }
}
impl PartialEq for Letter {
    fn eq(&self, other: &Self) -> bool {
        self.value == other.value
    }
}
impl Eq for Letter {}
impl Ord for Letter {
    fn cmp(&self, other: &Self) -> Ordering {
        self.value.cmp(&other.value)
    }
}
impl PartialOrd for Letter {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl Display for Letter {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.try_to_char().ok_or(fmt::Error)?)
    }
}
#[derive(Clone, Debug, PartialEq)]
///Newtype over a `Vec<Letter>`. Allows conversion to and from a UTF-8 string,
///and allows elementwise addition and other operations.
pub struct Alphabetic(Vec<Letter>);
impl Alphabetic {
    pub fn new(vec: Vec<Letter>) -> Alphabetic {
        Alphabetic(vec)
    }
    ///Returns an `Alphabetic` from the given string, but returns `None` if the
    /// string contains any non-alphabetic characters.
    pub fn try_from_str(string: &str) -> Option<Alphabetic> {
        let letters: Option<Vec<Letter>> = string.bytes().map(Letter::try_from_utf8).collect();
        Some(Alphabetic::new(letters?))
    }
    ///Returns an `Alphabetic` from the given string. Unlike `try_from_str`,
    /// this function will simply ignore any characters which it cannot
    /// convert, rather than returning `None`.
    pub fn from_str_filtered(string: &str) -> Alphabetic {
        Alphabetic::new(
            string
                .bytes()
                .filter(|x| x.is_ascii_alphabetic())
                .map(|x| Letter::try_from_utf8(x).unwrap())
                .collect(),
        )
    }
    ///Applies `func` to each pair of values from `self` and `other`,
    /// collecting the results into a new `Alphabetic`. If it reaches the
    /// end of one of the strings, it will simply dump the remainder of the
    /// longer string into the output; therefore, the output is always the
    /// same length as the longer of the two strings.
    pub fn pairwise_map(
        &self,
        other: &Self,
        func: Box<dyn Fn(Letter, Letter) -> Letter>,
    ) -> Alphabetic {
        let mut buf: Vec<Letter> = Vec::with_capacity(cmp::max(self.len(), other.len()));
        let mut self_iter = self.iter();
        let mut other_iter = other.iter();
        loop {
            match (self_iter.next(), other_iter.next()) {
                (Some(sval), Some(oval)) => buf.push(func(*sval, *oval)),
                (Some(sval), None) => {
                    buf.push(*sval);
                    buf.extend(self_iter);
                    break;
                }
                (None, Some(oval)) => {
                    buf.push(*oval);
                    buf.extend(other_iter);
                    break;
                }
                (None, None) => break,
            }
        }

        Alphabetic::new(buf)
    }
    //exposed functions from the inner vec
    pub fn len(&self) -> usize {
        self.0.len()
    }
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }
    pub fn iter(&self) -> std::slice::Iter<Letter> {
        self.0.iter()
    }
}
impl Display for Alphabetic {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", {
            let chars = String::from_utf8(self.iter().map(Letter::to_utf8).collect());
            chars.map_err(|_e| fmt::Error)?
        })
    }
}
//copy-paste boilerplate land
///Addition and subtraction on `Alphabetic`s works by adding/subtracting each
/// pair of `Letter`s, until we reach the end of either string, at which point
/// the remainder of the longer string will be appended.
impl Add<Alphabetic> for Alphabetic {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        self.pairwise_map(&other, Box::new(|x, y| x + y))
    }
}
impl Add<Letter> for Alphabetic {
    type Output = Self;
    fn add(self, other: Letter) -> Self {
        Alphabetic::new(self.iter().map(|x| *x + other).collect())
    }
}
impl Add<i8> for Alphabetic {
    type Output = Self;
    fn add(self, other: i8) -> Self {
        Alphabetic::new(self.iter().map(|x| *x + other).collect())
    }
}
impl Sub<Alphabetic> for Alphabetic {
    type Output = Self;
    fn sub(self, other: Self) -> Self {
        self.pairwise_map(&other, Box::new(|x, y| x - y))
    }
}
impl Sub<Letter> for Alphabetic {
    type Output = Self;
    fn sub(self, other: Letter) -> Self {
        Alphabetic::new(self.iter().map(|x| *x - other).collect())
    }
}
impl Sub<i8> for Alphabetic {
    type Output = Self;
    fn sub(self, other: i8) -> Self {
        Alphabetic::new(self.iter().map(|x| *x - other).collect())
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_char_display() {
        let mut letter = Letter::try_from_char('U').unwrap();
        //display property works properly
        assert_eq!(format!("{}", letter), "U");
        letter = Letter::new(6, Case::Lower);
        //initialising letters from their values works properly
        assert_eq!(format!("{}", letter), "g");
    }
    #[test]
    fn test_char_operators() {
        let letter1 = Letter::new(8, Case::Lower);
        let letter2 = Letter::from_signed(-16, Case::Lower);
        assert_eq!(format!("{}", letter1 + letter2), "s");
        assert_eq!(format!("{}", letter1 - letter2), "y");
        assert!(letter2 > letter1);
        assert!(letter2 != letter1);
    }
    #[test]
    fn test_alphabetic_display() {
        let alpha = Alphabetic::try_from_str("hello").unwrap();
        //display property works properly
        assert_eq!(format!("{}", alpha), "hello");
        let beta = Alphabetic::try_from_str("helloり");
        //try_from_str correctly does not accept non-alphabetic chars
        assert_eq!(beta, None);
    }
    #[test]
    fn test_alphabetic_addition() {
        let alpha = Alphabetic::try_from_str("hello").unwrap();
        let beta = Alphabetic::try_from_str("bbbbb").unwrap();
        assert_eq!((alpha + beta).to_string(), "ifmmp");
        let long = Alphabetic::try_from_str("longabcdefgh").unwrap();
        let short = Alphabetic::try_from_str("short").unwrap();
        //strings of different lengths can be added, commutatively
        assert_eq!((long.clone() + short.clone()).to_string(), "dvbxtbcdefgh");
        assert_eq!((short.clone() + long.clone()).to_string(), "dvbxtbcdefgh");
        //letter can be added to alphabetic
        assert_eq!(
            (Alphabetic::try_from_str("bbbbbb").unwrap() + Letter::try_from_char('b').unwrap())
                .to_string(),
            "cccccc"
        );
    }
    #[test]
    fn test_empty_values() {
        let a = Alphabetic::try_from_str("").unwrap();
        let b = Alphabetic::from_str_filtered("");
        let c = Alphabetic::new(vec![]);
        assert_eq!(a.to_string(), "");
        assert_eq!(b.to_string(), "");
        assert_eq!(c.to_string(), "");
    }
}

frequency.rs

///Provides utilities relating to frequency analysis, to be used by cipher
/// modules.
use crate::alphabetic::{self, Alphabetic, Case, Letter};
//https://en.wikipedia.org/wiki/Letter_frequency
//relative frequencies of letters in the english language, in alphabet order
pub const ENGLISH_FREQUENCIES: [f64; alphabetic::ALPHABET_SIZE] = [
    0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015, 0.06094, 0.06966, 0.00153,
    0.00772, 0.04025, 0.02406, 0.06749, 0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056,
    0.02758, 0.00978, 0.02360, 0.00150, 0.01974, 0.00074,
];
///Returns a `Vec` of relative frequencies of each `Letter` in the string.
pub fn frequencies(string: &Alphabetic) -> Vec<f64> {
    let mut counts = vec![0usize; alphabetic::ALPHABET_SIZE];
    string.iter().for_each(|x| {
        counts[x.value as usize] += 1;
    });
    let sum = counts.iter().sum::<usize>();
    if sum == 0 {
        return vec![0f64; alphabetic::ALPHABET_SIZE];
    }
    counts.into_iter().map(|x| x as f64 / sum as f64).collect()
}

///Returns the `Letter` which occurs most frequently in the given string.
///# Panics
///There are 2 `unwrap`s in this function. One of them
/// unwraps the result of a `std::slice::Iter::max_by()`,
/// which yields `None` only when the iter is empty Since we
/// use the constant iter `(0..26)`, this is not a concern.
/// The other unwrap is on the result of an
/// `f64::partial_cmp()`, which would fail if one of the
/// `f64`s is an unusual value, like `NaN`. We obtain these
/// values from division and check for division by zero, so
/// there *should* be no way for this panic to occur.
pub fn most_frequent_letter(string: &Alphabetic) -> Letter {
    let freqs = frequencies(string);
    Letter::new(
        (0..26)
            .max_by(|x, y| freqs[*x].partial_cmp(&freqs[*y]).unwrap())
            .unwrap() as u8,
        Case::Lower,
    )
}
///Returns a `Vec` containing the `Letters` representing `a` through `z`, in
/// order from most frequent to least frequent in the given string.
pub fn letters_by_frequency(string: &Alphabetic) -> Vec<Letter> {
    let freqs = frequencies(string);
    let mut indices: Vec<usize> = (0..26).collect();
    indices.sort_by(|x, y| freqs[*y].partial_cmp(&freqs[*x]).unwrap());
    indices
        .into_iter()
        .map(|x| Letter::new(x as u8, Case::Lower))
        .collect()
}
///Returns the mean squared difference between two `f64` slices. The mean
/// squared difference is only defined on two slices of the same length (if the
/// slices are not the same length, this function returns `None`). It is defined
/// as the sum of the squares of the differences between each pair of items (one
/// from each slice), divided by the length of the slices.
pub fn mean_squared_difference(freqs1: &[f64], freqs2: &[f64]) -> Option<f64> {
    let length = match (freqs1.len(), freqs2.len()) {
        (0, _) | (_, 0) => {
            return None;
        }
        (x, y) if x == y => x,
        _ => return None,
    };
    let mut sum = 0f64;
    for i in 0..length {
        sum += (freqs1[i] - freqs2[i]).powi(2)
    }
    Some(sum)
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_frequency() {
        let string = Alphabetic::try_from_str("hello").unwrap();
        assert_eq!(
            most_frequent_letter(&string),
            Letter::try_from_char('l').unwrap()
        );
        let freqs: Vec<f64> = vec![
            0.0, 0.0, 0.0, 0.0, 0.2, 0.0, 0.0, 0.2, 0.0, 0.0, 0.0, 0.4, 0.0, 0.0, 0.2, 0.0, 0.0,
            0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
        ];
        assert_eq!(frequencies(&string), freqs);
        let letters = letters_by_frequency(&string);
        assert_eq!(letters[0], Letter::try_from_char('l').unwrap());
        assert_eq!(letters[1], Letter::try_from_char('e').unwrap());
        assert_eq!(letters[2], Letter::try_from_char('h').unwrap());
        assert_eq!(letters[3], Letter::try_from_char('o').unwrap());
    }
}

caesar.rs

///Provides functions for encrypting and cracking Caesar ciphers.
use crate::{
    alphabetic::{self, Alphabetic, Letter},
    frequency::{frequencies, mean_squared_difference, most_frequent_letter, ENGLISH_FREQUENCIES},
};
///Shift the given string by the given number of places.
pub fn shift(string: &Alphabetic, num_places: i8) -> Alphabetic {
    string.clone() + num_places
}
///Iterator over all of the possible shifts of a given string.
pub struct GenShifts(Alphabetic, i8);
impl GenShifts {
    fn new(string: Alphabetic) -> GenShifts {
        GenShifts(string, 0)
    }
}
impl Iterator for GenShifts {
    type Item = Alphabetic;
    fn next(&mut self) -> Option<Self::Item> {
        if self.1 == alphabetic::ALPHABET_SIZE as i8 {
            return None;
        }
        self.1 += 1;
        Some(shift(&self.0, self.1 - 1))
    }
}
pub fn gen_shifts(string: Alphabetic) -> GenShifts {
    GenShifts::new(string)
}
///Crack an encrypted string by shifting the string such
/// that the most common character therein is mapped to 'e'
/// (the most common letter in English)
pub fn crack_match_maxima(string: &Alphabetic) -> Alphabetic {
    const MOST_FREQUENT_ENGLISH: Letter = Letter::try_from_char('e').unwrap();
    string.clone() - most_frequent_letter(&string) + MOST_FREQUENT_ENGLISH
}
///Crack an encrypted string by choosing the shift which
/// minimises the MSE (mean squared error) between the
/// observed letter frequencies and the expected letter
/// frequencies (based on a large sample of English text)
pub fn crack_minimise_mse(string: &Alphabetic) -> Alphabetic {
    gen_shifts(string.clone())
        .min_by(|x, y| {
            let mse = |x| mean_squared_difference(&frequencies(x), &ENGLISH_FREQUENCIES).unwrap();
            mse(x).partial_cmp(&mse(y)).unwrap()
        })
        .unwrap()
}

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

    #[test]
    fn test_shift() {
        assert_eq!(
            shift(&Alphabetic::try_from_str("abcdef").unwrap(), 1).to_string(),
            "bcdefg"
        );
        let mut shifts = gen_shifts(Alphabetic::try_from_str("abcdef").unwrap());
        assert_eq!(shifts.next().unwrap().to_string(), "abcdef");
        assert_eq!(shifts.next().unwrap().to_string(), "bcdefg");
        assert_eq!(shifts.next().unwrap().to_string(), "cdefgh");
        assert_eq!(shifts.next().unwrap().to_string(), "defghi");
    }
    #[test]
    fn test_crack() {
        let original = Alphabetic::from_str_filtered(
            "If it were done when 'tis done, then 'twere well
             It were done quickly: if the assassination
             Could trammel up the consequence, and catch
             With his surcease success; that but this blow
             Might be the be-all and the end-all here,
             But here, upon this bank and shoal of time,
             We'ld jump the life to come. But in these cases
             We still have judgment here; that we but teach
             Bloody instructions, which, being taught, return
             To plague the inventor: this even-handed justice
             Commends the ingredients of our poison'd chalice
             To our own lips. He's here in double trust;
             First, as I am his kinsman and his subject,
             Strong both against the deed; then, as his host,
             Who should against his murderer shut the door,
             Not bear the knife myself. Besides, this Duncan
             Hath borne his faculties so meek, hath been
             So clear in his great office, that his virtues
             Will plead like angels, trumpet-tongued, against
             The deep damnation of his taking-off;
             And pity, like a naked new-born babe,
             Striding the blast, or heaven's cherubim, horsed
             Upon the sightless couriers of the air,
             Shall blow the horrid deed in every eye,
             That tears shall drown the wind. I have no spur
             To prick the sides of my intent, but only
             Vaulting ambition, which o'erleaps itself
             And falls on the other.",
        );
        let shifted = shift(&original, 6);
        assert_eq!(crack_match_maxima(&shifted), original);
        assert_eq!(crack_minimise_mse(&shifted), original);
    }
}
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

Overall, your implementation looks good! Your code is well documented, it has unit tests and the use of the standard traits is also great.

Here are some of my suggestions:

The value field of Letter must be in the range 0-25, I would either add an assertion in the new method of Letter that panics if the range is violated, or make it return a Result and handle the error.


Implementing the above will allow you to move the unsafe from pub unsafe fn to_char_unchecked(&self) -> char into the method body as it will always be safe to convert. It's a good practice to avoid unsafe in public APIs whenever it's possible by creating a safe abstraction over the unsafe code.


value and case should not be public. You can change them to pub(crate).


Remove the need for unstable features.

const MOST_FREQUENT_ENGLISH: Letter = Letter::try_from_char('e').unwrap();

can be replaced with

const MOST_FREQUENT_ENGLISH: Letter = Letter {
        value: 4,
        case: Case::Lower,
    };

and #![feature(const_option)] can be removed. The const variable can also be taken out of the method.


fn combined_case(case1: Case, case2: Case) -> Case can be implemented using the Add trait as you have done for Letter.


Use filter_map() instead of filter() and map().

Alphabetic::new(
            string
                .bytes()
                .filter(|x| x.is_ascii_alphabetic())
                .map(|x| Letter::try_from_utf8(x).unwrap())
                .collect(),
        )

can be replaced with

Alphabetic::new(
            string
                .bytes()
                .filter_map(Letter::try_from_utf8)
                .collect(),
        )

assert!(letter2 != letter1); can be changed to assert_ne!(letter2, letter1);


Avoid dynamic dispatch. There is no need to use dynamic dispatch in this method

 pub fn pairwise_map(
        &self,
        other: &Self,
        func: Box<dyn Fn(Letter, Letter) -> Letter>,
    ) -> Alphabetic 

It can be changed using generic type:

pub fn pairwise_map<Func>(&self, other: &Self, func: Func) -> Alphabetic
    where
        Func: Fn(Letter, Letter) -> Letter,

Or an fn pointer:

 pub fn pairwise_map(
        &self,
        other: &Self,
        func: fn(Letter, Letter) -> Letter,
    ) -> Alphabetic {

This:

let length = match (freqs1.len(), freqs2.len()) {
        (0, _) | (_, 0) => {
            return None;
        }
        (x, y) if x == y => x,
        _ => return None,
    };

can be simplified

let length = match (freqs1.len(), freqs2.len()) {
        (x, y) if x == y && x != 0 => x,
        _ => return None,
    };
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Thank you for the useful pointers (pun not intended)! I honestly didn't even know about pub(crate) or filter_map, and I'm not sure why I went for a box for the function. My only question is about the last part with the match statement - you seem to have written the same thing twice rather than changing it? \$\endgroup\$
    – Egg-Fault
    Jun 8, 2021 at 18:37
  • 1
    \$\begingroup\$ Sorry, I've changed it now :) \$\endgroup\$
    – DobromirM
    Jun 9, 2021 at 9:46
  • \$\begingroup\$ What a fantastic review! \$\endgroup\$
    – MEMark
    Nov 17, 2022 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.