Snowhash in Rust with WASM

May 22, 2018 · 1275 words · 6 minutes read rust wasm procedural hash

A little while ago I came across this Snowflake generator. It’s a project by Raph Levein that takes a hash string and uses it to procedurally generate a unique snowflake. He explains that

the original motivation was as a cryptographically secure visual hash, so that people would reliably be able to tell by visual inspection whether two hashes were identical.

I thought that was a pretty cool idea. Having someway to quickly tell if two similar strings were distinct has some real benefits. But to be honest, I thought the snowflakes that were generated were the coolest part (pun completely intended).

I set about rewriting the project in Rust using the algorithm Raph described in a follow up article he posted. As I was writing it I thought generating snowflakes would also be a great way to play around with Wasm.

Targeting Wasm from Rust code has been something I’ve been meaning to check out. And this project was perfect for it. The Rust code could handle all the procedural generation stuff, and then I could write a small bit of JS to call the Wasm function and draw each point onto a Canvas.

impl Snowhash

Let’s start from the top: the main generate function.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/// Generate points from the provided hash string.
pub fn generate(hash: &str) -> Vec<Point> {
    let seed: &[_] = &[hash_sum(hash)];
    let mut rng: StdRng = SeedableRng::from_seed(seed);

    let mut open = vec![Point::origin()];
    let mut closed = vec![];
    let mut filled = vec![];

    for bit in BitStr::from_str(hash) {
        let index = rng.gen_range(0, open.len());
        let point = open.remove(index);

        if point.on_axis() || bit.as_bool() {
            let mut reflection = point.reflection();
            filled.append(&mut reflection);

            let mut extension = extend(&point, &closed);
            open.append(&mut extension);
        }
        closed.push(point);
    }
    filled
}

That’s not a lot of code, but let’s run through it bit by bit.

1
2
3
let seed: &[_] = &[hash_sum(hash)];
let mut rng: StdRng = SeedableRng::from_seed(seed);

First we seed the random number generator (RNG). hash_sum takes the u8 value of each character in hash and adds them all together. I found that this resulted in greater changes between two similar hashes, when compared to having a fixed seed.

We also don’t want this to be an unreproducible seed, such as Unix time since epoch. Using that would mean that the same hash would produce two distinct snowflakes. It would still look cool, but that would go against the whole point of generating the snowflake from the hash.

Next, we iterate through all the bits in the hash with BitStr::from_str(hash). I’ll come back to the BitStr implementation a bit later.

1
2
3
let index = rng.gen_range(0, open.len());
let point = open.remove(index);

And for each iteration we get a random point from open and remove it from the vector.

1
2
3
4
5
6
7
8
9
if point.on_axis() || bit.as_bool() {
    let mut reflection = point.reflection();
    filled.append(&mut reflection);

    let mut extension = extend(&point, &closed);
    open.append(&mut extension);
}
closed.push(point);

The final section is the loop iteration. This is just the algorithm that Raph described. The extend function grabs all neighbours of point, in our specific slice, that we haven’t seen yet (isn’t in closed).

At the end of this function we return filled: Vec<Point> which is, as the name suggests, all the points we need to fill to show the snowflake.

Point

The Point struct is exactly what you’d expect. It’s a just a tuple struct of two i32s.

1
2
pub struct Point(i32, i32);

It also has a bunch of methods to make the generate function a bit cleaner, namely Point::reflection and Point::neighbours.

BitStr

Implementing BitStr required a bit more thought. Here’s the struct.

1
2
3
4
5
6
struct BitStr<'a> {
    bytes: Bytes<'a>,
    cur: Option<u8>,
    cur_idx: u8,
}

bytes are the bytes we want to iterate though. cur is the current byte, or another way of putting it is the most recent byte taken from bytes. And cur_inx is the index into cur, used for extracting individual bits from the byte.

This struct just implements the Iterator trait so we can iterated over all the bits. Then, for each iteration we grab the next bit, with some bit shifting. If we find we have gone through all the bits in cur then we reset cur_idx and grab the next byte from bytes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl<'a> Iterator for BitStr<'a> {
    type Item = Bit;

    fn next(&mut self) -> Option<Self::Item> {
        if self.cur.is_none() || self.cur_idx >= 8 {
            self.cur = self.bytes.next();
            self.cur_idx = 0;
        }

        if let Some(byte) = self.cur {
            let bit = Bit::from_u8((byte << self.cur_idx) & 128);
            self.cur_idx += 1;
            return Some(bit);
        }
        None
    }
}

Bit

If I’m implementing my own BitStr I may as well implement my own Bit as well. For this I also wanted to take advantage of Rust’s empty tuple, which has a size of 0.

1
2
struct Bit(Option<()>);

Even though we’re now using a Rust specific type, the Bit implementation is still super simple. If bit.0.is_some() then it’s a high bit, and if bit.0.is_none() then it’s a low bit.

impl From for Png

That’s the entire implementation. Not too much logic for some really interesting snowflakes. Now I just need to display them.

Before jumping straight into compiling to Wasm, I went for something a bit more familiar and rendered the points as a PNG. For this I used cairo-rs, a wrapper around the Cairo Graphics clib.

Coming this far we get some pretty interesting looking snowflakes, like this one from the title banner.

1
$ snowhash_png 2552a8f69a6d45dbd786a8452d14dc841c665f04e763bb2c6b2157b8b95a231a

Or this one from a randomly generated hash.

1
$ snowhash_png dd76ecd83a8b238b58507b13096f6727cabf33ad90530c9a97de07b55d3efa3b

Plug those hashes into the Snowhash generator on this site and you should see the exact same snowflake. But this generator makes no guarantees between machines when running snowhash_png.

To achieve consistency between snowhash_wasm, and snowhash_png on multiple devices I imagine all that is required is some small changes to the RNG. But that’s something to look into another day.

impl From for Wasm

For now, onto Wasm.

This turned out to be much easier than I was expecting. In fact, excluding imports and a helper function, this is all that we need.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#[derive(Serialize)]
struct CanvasPoint(f64, f64);

#[wasm_bindgen]
pub fn generate(hash: &str) -> String {
    let points: Vec<CanvasPoint> = snowhash::generate(hash)
        .iter()
        .map(|point| hex_to_cartesian(point.x() as f64, point.y() as f64))
        .map(|(x, y)| CanvasPoint(x, y))
        .collect();
    serde_json::to_string(&points).unwrap()
}

I created a new struct CanvasPoint just so I didn’t have to make the Snowhash library depend on serde.

And the generate function just takes the points from snowhash::generate(hash), converts them from Hex grid coordinates into Cartesian grid coordinates, and turns the resulting Vec into a JSON list.

The #[wasm_bindgen] macro above the generate function tells the rust compiler that we want to make this function available as part of the Wasm module. Without it, the JS code wouldn’t be able to call snowhash.generate().

Something else worth mentioning is that Wasm, at the time of writing, only supports numeric types. I thought that this would allow me to return a Vec<(f64, f64)> from generate but that isn’t supported just yet.

As a workaround I went with serializing Vec<CanvasPoint> to JSON. In JS land, there’s already a module to parse JSON strings without needing to include any external libs.

Reducing the Bundle

Compiling to Wasm and adding some JS to draw the hexagons to the canvas worked out pretty well. Except that the bundle started out as being ~710KB.

I’d heard that this is a bit of an issue. There seems to be some good work going into improving this but it’s still a fair way to go.

Still I wanted to reduce the size at least a little if I could.

I was surprised by how little effort I had to put in to drop the bundle size by nearly 50%, to 358KB. All I did was install wasm-opt, as part of the WebAssembly/binaryen toolchain, and run wasm-opt -Os snowhash.wasm. The -Os flag tells wasm-opt to optimize for size over speed and, well it seemed to do the job.

Snowhash

So after that explanation here’s the finished product. I’ve embedded it at the bottom of the post, but it’s also available on it’s own page.

By the way, if you get tired of manually changing the hash, click on the snowflake (the canvas) and a new random snowflake will be created.

Enjoy!