# Matasano cryptopals: Conversion to base 64 (with generic types)

My main interest is in how I have handled the generics and if it's idiomatic. I want the user to be able to specify what kind of integer type they would like to use for the encoding (u8, u16, u32, u64).

I want to keep the hex string -> vector of numbers and vector of numbers -> base 64 string conversions separate.

My first worry is around specifying the traits of my generic. I've done so with:

<T: PrimInt + FromPrimitive + ToPrimitive>


Perhaps I should of created my own custom type listing all the required traits explicitly and used that?

My second worry is how I interact with raw primitive types:

FromPrimitive::from_u64(0).unwrap();


and:

ToPrimitive::to_u8(&to_encode).unwrap()


It would obviously be nicer to not have this messy conversion in cases where I know it's OK:

let a:T = 0;//vs FromPrimitive::from_u64(0).unwrap();


Feedback on these issues is most important to me, but more general comments also welcome! I do wonder if in real life the use of generics here is even useful (violates KISS?).

http://cryptopals.com/sets/1/challenges/1/ is the specific challenge this code is for.

extern crate num;

use self::num::traits::PrimInt;
use self::num::{ToPrimitive, FromPrimitive};
use std::mem::size_of;
use std::char;

pub fn hex_decode<T: PrimInt + FromPrimitive + ToPrimitive>(hex:&str) -> Vec<T>{
let num_of_4_bits = (size_of::<T>()*8) / 4;
let mut hex_bytes:Vec<T> = Vec::new();
let zero:T = FromPrimitive::from_u64(0).unwrap();
hex_bytes.resize(hex.len()/num_of_4_bits,  zero);
for (index, character) in hex.chars().enumerate(){
let modulus = index % num_of_4_bits;
let shift = 4 * ((num_of_4_bits - 1) - modulus);
let decoded_hex:T = FromPrimitive::from_u32(character.to_digit(16).unwrap()).unwrap();
let hex_index = index/num_of_4_bits;
hex_bytes[hex_index] = hex_bytes[hex_index] | (decoded_hex << shift);
}
hex_bytes
}

pub fn make_length_multiple_of_3<T: FromPrimitive>(raw_binary: &mut Vec<T>){
while raw_binary.len() % 3 != 0{
raw_binary.push(FromPrimitive::from_u64(0).unwrap());
}
}

fn handle_carried_bits<T: PrimInt + FromPrimitive + ToPrimitive>(carried_over_bits:T, previous_bits_left:usize, binary_element:T) -> (u8, usize){
let type_length = size_of::<T>() * 8;
let bits_left = type_length - (6 - previous_bits_left);
let bottom_bits =  binary_element >> bits_left;
let to_encode = carried_over_bits | bottom_bits;
(ToPrimitive::to_u8(&to_encode).unwrap(), bits_left)
}

//we encode 6 bits at a time, thus we need a multiple of 6 to encode
//as long as T has 2^x bits, and vector has length 3*y:
// (2^x)*3*y = (2^(x-1))*y*6 will always be a multiple of 6
//so check size of T is a power of 2, then ensure number of elements is a multiple of 3
pub fn encode_to_base64<T: PrimInt + FromPrimitive + ToPrimitive>(raw_binary: Vec<T>) -> String {
assert!(size_of::<T>().count_ones() == 1 && size_of::<T>() * 8 > 1);
let mut local_raw_binary = raw_binary.clone();
make_length_multiple_of_3(&mut local_raw_binary);
let mut base_64 = "".to_string();
let mut carried_over_bits: T = FromPrimitive::from_u64(0).unwrap();
let mut previous_bits_left = 0;
for index in 0..local_raw_binary.len(){
let (to_encode, mut bits_left) = handle_carried_bits(carried_over_bits, previous_bits_left, local_raw_binary[index]);
base_64.push(encode_to_char(ToPrimitive::to_u8(&to_encode).unwrap()));
while bits_left >= 6 {
let to_encode = six_bit_mask & (local_raw_binary[index] >> (bits_left - 6));
bits_left -= 6;
base_64.push(encode_to_char(ToPrimitive::to_u8(&to_encode).unwrap()));
}
carried_over_bits = six_bit_mask & (local_raw_binary[index] << (6 - bits_left));
previous_bits_left = bits_left;
}
return base_64;
}

fn encode_to_char(bits: u8) -> char {
match bits {
0 ... 25 => char::from_u32('A' as u32 + bits as u32).unwrap(),
26 ... 51 => char::from_u32('a' as u32 + (bits - 26) as u32).unwrap(),
52 ... 61 => char::from_u32('0' as u32 + (bits - 52) as u32).unwrap(),
62 => '+',
63 => '/',
_ => panic!("{} cannot be encoded to a base 64 character", bits),
}
}


Examples from my test code:

#[test]
fn hex_decode_test(){
let hex = "49276d206b696c6c";
let u8_bin = vec![0b01001001,0b00100111,0b01101101,0b00100000,0b01101011,0b01101001,0b01101100,0b01101100];
assert_eq!(format!("{:?}",u8_bin), format!("{:?}",hex_to_base64::hex_decode::<u8>(hex)));
let u16_bin = vec![0b0100100100100111,0b0110110100100000,0b0110101101101001,0b0110110001101100];
assert_eq!(format!("{:?}",u16_bin), format!("{:?}",hex_to_base64::hex_decode::<u16>(hex)));
let u32_bin = vec![0b01001001001001110110110100100000,0b01101011011010010110110001101100];
assert_eq!(format!("{:?}",u32_bin), format!("{:?}",hex_to_base64::hex_decode::<u32>(hex)));
let u64_bin = vec![0b0100100100100111011011010010000001101011011010010110110001101100 as u64];
assert_eq!(format!("{:?}",u64_bin), format!("{:?}",hex_to_base64::hex_decode::<u64>(hex)));
}

#[test]
fn based_64_encode_test() {
let hex = "49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d";
let encoded = "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t";
assert_eq!(encoded,hex_to_base64::encode_to_base64(hex_to_base64::hex_decode::<u8>(hex)));
assert_eq!(encoded,hex_to_base64::encode_to_base64(hex_to_base64::hex_decode::<u16>(hex)));
assert_eq!(encoded,hex_to_base64::encode_to_base64(hex_to_base64::hex_decode::<u32>(hex)));
assert_eq!(encoded,hex_to_base64::encode_to_base64(hex_to_base64::hex_decode::<u64>(hex)));
}


1. [Style] Space after :
2. [Style] Spaces around binary operators like / or *.
3. [Style] Only one space after a comma.
4. [Style] Space before the { that opens a block.
5. 4 bits is often referred to as a nybble (because it's half a byte and programmers think we are funny).
6. [Performance] Why clone the incoming Vec?? If the function is going to take ownership of the item anyway, it might as well make use of it and change it in place.
7. [Idiomatic] There are multiple places with redundant type annotations (let foo: SomeType). Type inference can handle most of those cases. Leave them off for easier reading and refactoring.
8. [Idiomatic, Performance] Should not iterate over the indices of an array when you can just iterate over each value.
9. [UX] Split production assert!s with && into multiple for better error reporting.
10. [UX] Use assert_eq! in production code for better error reporting.
11. [UX] Use the optional last argument to assert! / assert_eq! in production code to provide better error reporting.
12. [Idiomatic, Performance] Hoist constants out of loops.
13. [Style] I was happy to see smaller functions and multiple intermediate variables and I like that, but the bodies of some functions are still dense. Perhaps some spare newlines between lines would help.
14. [Typo] based_64_encode_test should be base_64_encode_test.
15. [Idiomatic] Don't use an explicit return at the end of a function.
16. [Tests] The tests have multiple assertions per test method. Since the first error stops the test, this forces more cycles of testing to see all errors. Also means programmer has to go to the line of code to know what failed instead of reading the name of the test.
17. [Idiomatic] Memorize Iterator methods for things like map and collect. Use them all the time unless there's a good reason not to. See hex_decode for examples.
18. [Style] Small helper functions give names to concepts like "number of bits" or "zero for this type". They can also consolidate error handling like unwrap.
19. [Idiomatic] String::new is more obvious (and slightly faster for now) than "".to_string.
20. [Tests] Why is the test output transformed with format!?

extern crate num;

use self::num::traits::PrimInt;
use self::num::{ToPrimitive, FromPrimitive};
use std::mem::size_of;
use std::char;

fn n_bits<T>() -> usize { size_of::<T>() * 8 }
fn n_nybbles<T>() -> usize { n_bits::<T>() / 4 }
fn zero<T: FromPrimitive>() -> T { FromPrimitive::from_u64(0).unwrap() }

pub fn hex_decode<T: PrimInt + FromPrimitive + ToPrimitive>(hex: &str) -> Vec<T> {
let zero = zero();

hex.as_bytes().chunks(n_nybbles::<T>()).map(|chunk| {
let mut v = zero;
for &byte in chunk {
v = v << 4;
let decoded = (byte as char).to_digit(16).unwrap();
v = v | FromPrimitive::from_u32(decoded).unwrap();
}
v
}).collect()
}

pub fn make_length_multiple_of_3<T: PrimInt + FromPrimitive>(raw_binary: &mut Vec<T>) {
let zero = zero();
while raw_binary.len() % 3 != 0 {
raw_binary.push(zero);
}
}

fn handle_carried_bits<T: PrimInt + FromPrimitive + ToPrimitive>(carried_over_bits: T, previous_bits_left: usize, binary_element: T) -> (u8, usize) {
let type_length = n_bits::<T>();
let bits_left = type_length - (6 - previous_bits_left);
let bottom_bits = binary_element >> bits_left;
let to_encode = carried_over_bits | bottom_bits;
(ToPrimitive::to_u8(&to_encode).unwrap(), bits_left)
}

// we encode 6 bits at a time, thus we need a multiple of 6 to encode
// as long as T has 2^x bits, and vector has length 3*y:
// (2^x)*3*y = (2^(x-1))*y*6 will always be a multiple of 6 so check
// size of T is a power of 2, then ensure number of elements is a
// multiple of 3
pub fn encode_to_base64<T: PrimInt + FromPrimitive + ToPrimitive>(mut local_raw_binary: Vec<T>) -> String {
assert_eq!(size_of::<T>().count_ones(), 1);
assert!(n_bits::<T>() > 1);

make_length_multiple_of_3(&mut local_raw_binary);

let mut base_64 = String::new();
let mut carried_over_bits = zero();
let mut previous_bits_left = 0;

for element in local_raw_binary {
let (to_encode, mut bits_left) = handle_carried_bits(carried_over_bits, previous_bits_left, element);
base_64.push(encode_to_char(ToPrimitive::to_u8(&to_encode).unwrap()));
while bits_left >= 6  {
let to_encode = six_bit_mask & (element >> (bits_left - 6));
bits_left -= 6;
base_64.push(encode_to_char(ToPrimitive::to_u8(&to_encode).unwrap()));
}
carried_over_bits = six_bit_mask & (element << (6 - bits_left));
previous_bits_left = bits_left;
}

base_64
}

fn encode_to_char(bits: u8) -> char {
match bits {
0 ... 25 => char::from_u32('A' as u32 + bits as u32).unwrap(),
26 ... 51 => char::from_u32('a' as u32 + (bits - 26) as u32).unwrap(),
52 ... 61 => char::from_u32('0' as u32 + (bits - 52) as u32).unwrap(),
62 => '+',
63 => '/',
_ => panic!("{} cannot be encoded to a base 64 character", bits),
}
}

#[test]
fn hex_decode_test() {
let hex = "49276d206b696c6c";
let u8_bin = vec![0b01001001,0b00100111,0b01101101,0b00100000,0b01101011,0b01101001,0b01101100,0b01101100];
assert_eq!(u8_bin, hex_decode::<u8>(hex));
let u16_bin = vec![0b0100100100100111,0b0110110100100000,0b0110101101101001,0b0110110001101100];
assert_eq!(u16_bin, hex_decode::<u16>(hex));
let u32_bin = vec![0b01001001001001110110110100100000,0b01101011011010010110110001101100];
assert_eq!(u32_bin, hex_decode::<u32>(hex));
let u64_bin = vec![0b0100100100100111011011010010000001101011011010010110110001101100];
assert_eq!(u64_bin, hex_decode::<u64>(hex));
}

#[test]
fn base_64_encode_test() {
let hex = "49276d206b696c6c696e6720796f757220627261696e206c696b65206120706f69736f6e6f7573206d757368726f6f6d";
let encoded = "SSdtIGtpbGxpbmcgeW91ciBicmFpbiBsaWtlIGEgcG9pc29ub3VzIG11c2hyb29t";
assert_eq!(encoded,encode_to_base64(hex_decode::<u8>(hex)));
assert_eq!(encoded,encode_to_base64(hex_decode::<u16>(hex)));
assert_eq!(encoded,encode_to_base64(hex_decode::<u32>(hex)));
assert_eq!(encoded,encode_to_base64(hex_decode::<u64>(hex)));
}


I do wonder if in real life the use of generics here is even useful (violates KISS?).

That was my main concern when reading through this. In my experience, I've never wanted to convert to anything but a "chunk of bytes". I also wonder if different endian platforms will cause problems here.

Did you start from a concrete implementation (say u8) and then make it more generic, or did you attempt to start from a generic point-of-view? I've found it useful to wait until I need a second type and then identify the differences and introduce abstraction at that point.

Perhaps I should have created my own custom type listing all the required traits explicitly and used that?

I think that I would have created a new trait. You could then have created the helper methods like my n_bits directly on the trait.

It would obviously be nicer to not have this messy conversion in cases where I know it's OK

The problem is that you can never know if it's OK. Traits are open-ended, and anyone can implement it for any type. This includes other crates who might just always implement it as returning an error.

This could be a benefit of creating your own type - you would have more control over what is acceptable and what you expect.

Another idea would be to create a little struct of constants that you could create once and then just reuse in inner functions:

struct Constants<T> {
zero: T,
six: T,
}

impl Constants<T>
where T: FromPrimitive
{
fn new_from_primitive() -> Option<Constants> {
...
}
}


As a challenge, I'd encourage you to try to implement encode_to_base64 without needing to pad incoming data. This would allow you to accept a &[u8] instead and make the function usable in more contexts (when you don't own the data).

As a followup challenge, try to create an iterator that starts from a &[u8] and yields 6 bits at a time (in a u8, most likely). You should then be able to write something similar to:

MyIterator::new(bytes).map(encode_to_char).collect()


You may not want to try to accept a &[T] for these challenges, to start with.

• To answer some of your questions: 6: Still thinking in terms of non-ownership langs (I should've been passing &raw_binary for the clone to make sense?) 11: assert_eq doesn't seem to take a 3rd parameter I agree with your approach to abstractions. In this case I started from a working (but shoddy) u8 version and generalised from a "I wonder if I can" standpoint, not for any practical purpose Based on your answer, I'll probably stick to u8 for the later challenges. – Mehow Feb 21 '16 at 22:58
• assert_eq! doesn't [...] take a 3rd parameter — well, that's a shame. Hopefully the Debug formatting of the types is useful enough... not for any practical purpose — that's absolutely fine. Playing with code for the purposes of "what happens if I do this" is a great way of learning! Sometimes, trying something like this is the way to realize that "no, I shouldn't do it like that", but it may also help you when the time comes that it is the right decision! – Shepmaster Feb 22 '16 at 3:24