drunkenbishop 0.1.0

//! Library implementing the "drunken bishop" algorithm,
//! popularly used in the OpenSSH "randomart" key visualization feature.
//!
//! Special thanks to the paper
//! "The drunken bishop: An analysis of the OpenSSH fingerprint visualization algorithm"
//! by Dirk Loss, Tobias Limmer, and Alexander von Gernler.
//!
//! The board size is locked to a 17 by 9 grid, to match the OpenSSH implementation.
//! Unlike the original implementation however, no ASCII border will be drawn around the output.
//!
//! This crate includes optional features that are not enabled by default:
//! * `hexparse` - introduces a new function that accepts a hexadecimal string, and parses it into bytes, before rendering.
//! * `hash` - introduces a new function that accepts any arbitrary string, and hashes it with SHA-256, before rendering.

use thiserror::Error;

/// Render the path of the "drunken bishop" from a slice of bytes.
///
/// There are no requirements for input size.
/// An empty slice will yield a board with only the starting marker at the center.
///
/// Should the "drunken bishop" visit a location on the grid over 15 times,
/// the value at that location will safely overflow back to 0.
/// This behavior is unlikely to occur with smaller input sizes.
pub fn render(data: &[u8]) -> String {
    // naive implementation that simulates coverage.
    // could be optimized with map and offset implementation.

    // row-major order 2d array.
    let mut grid = [[0u8; 17]; 9];
    // (x, y) coordinate pair for bishop.
    let mut bishop: [usize; 2] = [8, 4];

    grid[bishop[1]][bishop[0]] = 15; // S

    for byte in data {
        for i in 0..4 {
            let bit_pair = (byte >> i & 1, byte >> (i + 1) & 1);
            let mut moved = false;

            match bit_pair {
                (0, 0) => {
                    if !(bishop[0] == 0 || bishop[1] == 0) {
                        bishop[0] -= 1;
                        bishop[1] -= 1;
                        moved = true;
                    }
                }
                (0, 1) => {
                    if !(bishop[0] == 16 || bishop[1] == 0) {
                        bishop[0] += 1;
                        bishop[1] -= 1;
                        moved = true;
                    }
                }
                (1, 0) => {
                    if !(bishop[0] == 0 || bishop[1] == 8) {
                        bishop[0] -= 1;
                        bishop[1] += 1;
                        moved = true;
                    }
                }
                (1, 1) => {
                    if !(bishop[0] == 16 || bishop[1] == 8) {
                        bishop[0] += 1;
                        bishop[1] += 1;
                        moved = true;
                    }
                }
                _ => {} // never should happen.
            };

            if moved {
                grid[bishop[1]][bishop[0]] += 1;
            }

            // overflow condition.
            if grid[bishop[1]][bishop[0]] > 14 {
                grid[bishop[1]][bishop[0]] = 0;
            }
        }
    }

    grid[bishop[1]][bishop[0]] = 16; // E

    let mut out = String::new();
    for row in grid {
        for value in row {
            out.push(match value {
                0 => ' ',
                1 => '.',
                2 => 'o',
                3 => '+',
                4 => '=',
                5 => '*',
                6 => 'B',
                7 => 'O',
                8 => 'X',
                9 => '@',
                10 => '%',
                11 => '&',
                12 => '#',
                13 => '/',
                14 => '^',
                15 => 'S',
                16 => 'E',
                _ => '!',
            });
        }
        out.push('\n');
    }

    out.strip_suffix('\n').unwrap_or(&out).to_owned()
}

/// Errors that may arise while rendering.
#[derive(Error, Debug)]
pub enum RenderError {
    /// Thrown if feature `hexparse` is enabled, and parsing the given hexadecimal string for rendering fails.
    #[error("Hex string could not be parsed")]
    HexParsingError,
}

/// Render the path of the "drunken bishop" from a hex string.
///
/// Internally, this function calls `render()` after parsing the given string,
/// and thus shares the same inherent rendering behavior.
#[cfg(feature="hexparse")]
pub fn render_from_hex(data: &str) -> Result<String, RenderError> {
    if let Ok(bytes) = hex::decode(data) {
        Ok(render(bytes.as_slice()))
    }
    else {
        Err(RenderError::HexParsingError)
    }
}

/// Render the path of the "drunken bishop" from an arbitrary UTF-8 string,
/// that is hashed with SHA-256.
///
/// Internally, this function calls `render()` after parsing the given string,
/// and thus shares the same inherent rendering behavior.
///
/// Because the input is hashed before being rendered,
/// the "drunken bishop" will always make 64 steps,
/// regardless of the length of the initial input.
///
/// Unlike the other render functions,
/// it is not possible to recover the original input from the generated pattern,
/// because of the use of the hash function.
#[cfg(feature="hash")]
pub fn render_s256(data: &str) -> String {
    use sha2::{Digest, Sha256};
    let mut hasher = Sha256::new();
    hasher.update(data);
    let bytes = hasher.finalize();

    render(&bytes[..])
}

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

    static BACK_AND_FORTH_OUT: &'static str = "    .            \n     o           \n      o          \n       o         \n        E        \n                 \n                 \n                 \n                 ";

    #[test]
    fn back_and_forth() {
        assert_eq!(BACK_AND_FORTH_OUT, render(&[0, 255]));
    }

    #[test]
    fn hello_world() {
        assert_eq!("    o            \n   o o .         \n  . + +          \n   o = .         \n    = = S        \n   . * +         \n      E          \n     . o         \n      o          ", render(&[72, 101, 108, 108, 111, 32, 119, 111, 114, 108, 100, 46]));
    }

    #[test]
    #[cfg(feature="hexparse")]
    fn hexparse() {
        assert_eq!(BACK_AND_FORTH_OUT, render_from_hex("00ff").unwrap());
    }

    #[test]
    #[cfg(feature="hexparse")]
    #[should_panic(expected="should crash")]
    fn hexparse_err() {
        render_from_hex("zzzz").expect("should crash");
    }

    #[test]
    #[cfg(feature="hash")]
    fn hash() {
        assert_eq!("        o o o    \n       . E + o   \n        . o o =  \n       . o = O o \n        . = @ *  \n         + + %   \n          * + = =\n         . + X * \n            O    ", render_s256("0 -> localhost"));
    }
}