WebAssembly Does Not Have A “raw binary” Data Type
|SHA256 Algorithm Overview||WebAssembly Does Not Have A “raw binary” Data Type||WebAssembly Program Architecture|
A Fundamental Collision of Concepts
- The basic unit of data processed by the SHA256 algorithm is an uninterpreted sequence of 32 bits (I.E. raw binary)
- WebAssembly only has numeric data types
WebAssembly can only read data from memory using one of its numeric data types.
So like it or not, if you use an
i32 instruction to read a value from memory, that value will be interpreted as an integer whose byte order is determined by the endianness of the CPU on which you’re running.
(Almost all processors nowadays are little-endian)
For example, if you call
(i32.load (local.get $some_offset)), then WebAssembly will use the following logic:
- The developer wants the 32-bit integer found in memory at
$some_offsetto be placed on the stack
- Since I’m running on a little-endian processor, the data in memory must have been stored in little-endian byte order
- So, before placing the value on the stack, I must reverse the byte order otherwise there will be a nonsense value on the stack…
So the raw binary value
0x0A0B0C0D in memory appears on the stack as
This problem might be fixed when the Garbage Collection proposal is implemented, but it probably won’t involve the arrival of a new datatype called
If such a data type were created, then a naïve solution might look like this:
(local $raw_bin raw32) (local.set $raw_bin (raw32.load $some_offset))
This would be great, but I doubt it will be implemented that way…
So the problem is simply this: before the SHA256 algorithm can start, we must swap the endianness of the data in memory so that when it is loaded onto the stack, the bytes appear in the expected network order.
Fortunately in our case, there is a simple workaround.
The host environment writes the file data to shared memory in network order. The file is then divided into 64-byte chunks, where each chunk forms the seed value at the start of the next 512-byte message digest.
All we need to do is this:
- Treat the data in this 64-byte chunk as if it were 16
- Swap the endianness of each
- Write the swapped
i32values to the start of the message digest
After that, we no longer need to care about endianness because the data will always appear on the stack in the correct byte order.
We could reverse the byte-order of each
i32 individually, but fortunately, WebAssembly makes a large number of SIMD (Single Instruction, Multiple Data) instructions available to us.
These instructions are designed to peform the same operation on multiple data values in parallel.
This not only simplifies the coding, but gives us a four-fold performance improvement.
In the loop where the raw binary file data is copied from the message block into the start of the message digest, instead of using the
memory.copy instruction, we can use the SIMD instruction
“Swizzle” is just a goofy name for rearranging a set of things into a new order.
;; Transfer the next 64 bytes from the message block to words 0..15 of the message schedule as raw binary ;; Use i8x16.swizzle to swap endianness (loop $next_msg_sched_vec (v128.store (i32.add (global.get $MSG_SCHED_OFFSET) (local.get $offset)) (i8x16.swizzle (v128.load (i32.add (local.get $blk_ptr) (local.get $ptr))) ;; 4 words of raw binary in network byte order (v128.const i8x16 3 2 1 0 7 6 5 4 11 10 9 8 15 14 13 12) ;; Rearrange bytes into this order of indices ) ) (local.set $offset (i32.add (local.get $offset) (i32.const 16))) (br_if $next_msg_sched_vec (i32.lt_u (local.get $offset) (i32.const 64))) )
Notice that we are now using instructions belonging to a different dataype:
v128 (128-bit vector), not
i8x16 instruction belongs to the
v128 data type and means “treat this block of 128 bits as if it were 16, 8-bit integers”.
Here, we load a block of 128 bits onto the stack, then using
i8x16.swizzle, we rearrange the byte order according to the vector of indices supplied as the second argument.
The same block of data is then treated as a group of four
i32 values which are written back to memory.
Now, when those
i32s are read back onto the stack, WebAssembly will assume that they have been stored in little-endian byte order, and the bytes will be reversed — back into network byte order.
Thus by some simple trickery, we have ensured that the data is always processed in the correct byte order.