fast_hamming 0.1.0

/// Finds the Hamming-Code for a 15-byte input array and returns a 16-byte array with the
/// rendundancy byte appended to the input array
pub fn encode_block(input: &[u8; 15]) -> [u8; 16] {
    let mut p1: u8 = 0;
    let mut p2: u8 = 0;

    let mut output = [0; 16];

    let mut power2: usize = 4;
    let mut data: u8 = 0;

    // number of bytes
    let mut insize = input.len();
    insize *= 8;

    let mut input_idx = 0;
    let mut output_idx = 0;

    // Parity + message bit counter
    let mut i = 3;
    // Bit counter
    let mut j = 0;
    loop {
        // stop when the bit counter is greater than the input length in bits
        if j >= insize {
            break;
        }

        // skip all bits that are at a power-of-two position
        if i == power2 {
            power2 *= 2;
            i += 1;
            continue;
        }

        // on every full byte (j is multiple of 8), copy data to the output and start a new round of parity calculation
        if j % 8 == 0 {
            data = input[input_idx];
            output[output_idx] = data;
            p2 ^= byte_parity(&data);
            input_idx += 1;
            output_idx += 1;
        }

        if data & 1 > 0 {
            p1 = p1 ^ (i as u8);
        }

        data >>= 1;

        // Increase indeces
        i += 1;
        j += 1;
    }

    p2 ^= byte_parity(&p1);

    output[output_idx] = p1 + (p2 << 7);

    output
}

/// Decodes a 16-byte array which has been coded with a Hamming-Code and has its ECC byte
/// appended and tries to decode it. If successful, returns a 15-byte array with the
/// original data.
pub fn decode_block(input: &[u8; 16]) -> Result<[u8; 15], FastHammingError> {
    let mut p1 = 0;
    let mut p2 = 0;
    let mut power2: usize = 4;
    let mut data = 0;
    let check = input[input.len() - 1];
    let mut output = [0; 15];

    // Copy input to output
    for i in 0..input.len() - 1 {
        output[i] = input[i].clone();
    }

    let insize = 15 * 8;

    let mut input_idx = 0;
    let mut i: usize = 3;
    let mut j: usize = 0;
    loop {
        if j >= insize {
            break;
        }

        if i == power2 {
            power2 *= 2;
            i += 1;
            continue;
        }

        if j % 8 == 0 {
            data = input[input_idx];
            input_idx += 1;
            p2 ^= byte_parity(&data);
        }

        if (data & 1) > 0 {
            p1 = p1 ^ (i as u8);
        }

        data >>= 1;
        i += 1;
        j += 1;
    }

    p1 ^= check & 0x7f;

    if p1 > 0 {
        let mut pm = check;
        p2 ^= byte_parity(&pm);

        // At least two errors
        if p2 == 0 {
            return Err(FastHammingError::TwoOrMoreErrors);
        }

        // Check for non-power of two in p1. A power of two means that one of the parity bits is wrong
        if (p1 & (p1 - 1)) != 0 {
            p2 = p1 - log2uint8(&p1) - 2;
            pm = p2 / 8;
            p2 = p2 % 8;
            // Fix the error
            output[pm as usize] ^= 1 << p2;
        }
    }

    Ok(output)
}

#[cfg_attr(test, derive(Debug, PartialEq))]
pub enum FastHammingError {
    TwoOrMoreErrors,
}

#[inline]
fn log2uint8(v: &u8) -> u8 {
    return 7 - v.leading_zeros() as u8;
}

/// Calculate the parity bit of the given byte
///
/// Returns a 1 if the input number in binary representation
/// has an odd number of bits set to 1. Returns else otherwise.
///
/// # Usage
/// ```
/// assert_eq!(byte_parity(&0), 0);
/// assert_eq!(byte_parity(&1), 1);
/// ```
#[inline]
fn byte_parity(input: &u8) -> u8 {
    let mut p = input.clone() as u32;
    p ^= p >> 4;
    p ^= p >> 2;
    p ^= p >> 1;
    p = p & 1;
    return p as u8;
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::{random, thread_rng, Rng};

    const DATA: [u8; 15] = [
        0x0b, 0x28, 0x48, 0x69, 0x5e, 0xc8, 0xeb, 0x87, 0x7f, 0x28, 0xdf, 0x52, 0x03, 0xb4, 0x46,
    ];

    const DATA_ENC: [u8; 16] = [
        0x0b, 0x28, 0x48, 0x69, 0x5e, 0xc8, 0xeb, 0x87, 0x7f, 0x28, 0xdf, 0x52, 0x03, 0xb4, 0x46,
        0xd9,
    ];

    fn flip_random_bit(array: &mut [u8]) -> usize {
        let flip_idx: usize = thread_rng().gen_range(0..(array.len() * 8));
        let bit_idx = flip_idx % 8;
        let byte_idx = flip_idx >> 3;

        array[byte_idx] ^= 1 << bit_idx;

        return flip_idx;
    }

    #[test]
    fn test_encode_block() {
        let input = DATA;
        assert_eq!(encode_block(&input), DATA_ENC);
    }

    #[test]
    fn test_decode_block() {
        let coded = DATA_ENC;
        assert_eq!(decode_block(&coded).unwrap(), DATA);
    }

    #[test]
    fn test_encode_decode() {
        let original_data: [u8; 15] = random();
        let mut encoded_data: [u8; 16];
        let decoded_data: [u8; 15];
        encoded_data = encode_block(&original_data);
        let flipped_bit_idx = flip_random_bit(&mut encoded_data);
        decoded_data = decode_block(&encoded_data).unwrap();
        assert_eq!(
            original_data,
            decoded_data,
            "Expected {:?} but got {:?}. Flipped bit {:?} of byte {:?}",
            original_data,
            decoded_data,
            flipped_bit_idx,
            flipped_bit_idx / 8
        );
    }

    #[test]
    fn stress_test_encode_decode() {
        let n_runs = 1000000;
        for _ in 0..n_runs {
            test_encode_decode();
        }
    }

    #[test]
    fn stress_test_two_bit_error() {
        let n_runs = 1000000;
        for _ in 0..n_runs {
            test_two_bit_error();
        }
    }

    #[test]
    fn test_two_bit_error() {
        let original_data: [u8; 15] = random();
        let mut encoded_data: [u8; 16];

        encoded_data = encode_block(&original_data);
        let bit_idx1 = flip_random_bit(&mut encoded_data);
        let bit_idx2 = flip_random_bit(&mut encoded_data);
        let decoded_data = decode_block(&encoded_data);
        if !(bit_idx1 == bit_idx2) {
            assert_eq!(decoded_data, Err(FastHammingError::TwoOrMoreErrors));
        } else {
            assert_eq!(decoded_data, Ok(original_data));
        }
    }

    #[test]
    fn test_log2() {
        assert_eq!(log2uint8(&1), 0);
        assert_eq!(log2uint8(&2), 1);
        assert_eq!(log2uint8(&3), 1);
        assert_eq!(log2uint8(&4), 2);
        assert_eq!(log2uint8(&7), 2);
        assert_eq!(log2uint8(&8), 3);
        assert_eq!(log2uint8(&16), 4);
        assert_eq!(log2uint8(&32), 5);
        assert_eq!(log2uint8(&64), 6);
        assert_eq!(log2uint8(&128), 7);
        assert_eq!(log2uint8(&255), 7);
    }

    #[test]
    fn test_parity() {
        for i in 0..=255 {
            assert_eq!(byte_parity(&i), i.count_ones() as u8 % 2);
        }
    }
}