Implement binary format

[kripken]

There is a proposal for a wasm binary format, links in the design repo.

We should implement it in a new header (wasm-binary.h perhaps), and add tests. Might use the tests from the v8-native repo, although that's been merged to upstream v8, so maybe we'd need to look there. Or, maybe we'd just use our existing tests and see we can translate them to binary and back?

The V8 binary format might be a waste of time, and they already have a wast to binary encoder for testing, so perhaps just check that it can encode the asm2wasm output.

If you are working on the binary format then here's some background that I absorbed looking at publicly released prototypes and a little experimentation.

The polyfill-prototype-1 still seems a useful guide and it used a number of techniques to compress the opcode encoding but it is now obsolete because it was designed for a fixed set of opcodes and the current design appears to require supporting an arbitrary set of opcodes.

It used separate opcode tables for a child branch of the AST based on the immediate parent opcode, using the type I32, F32, and F64 to distinguish between opcode tables. This would appear to generalize to an adaptive tree based compression approach.

It used a byte size encoding which might be very significant for another 'string' based compression layer to do well with the output. However it does appear that a variable size Huffman encoding could do much better, and it's not clear if a general 'string' based compressor could predict the patterns nearly as well from a linearised AST.

It uses a one byte encoding for a few high frequency opcodes that includes an short immediate within this byte. Bit 7 encodes between the immediate format and the non-immediate format. The immediate format includes a 2 bit opcode field and a 5 bit immediate field. The non-immediate format includes a 7 bit opcode field.

Some quick checking shows that considering both the parent opcode plus the argument position can give much better prediction for some high frequency opcodes. A simple Huffman encoding could compress these child opcodes very well above. Using a general 'string' compression algorithm would miss some of these patterns because there might be other branches between a parent opcode and a child opcode breaking up the 'string'.

[kripken]

I think it's still worth doing the current binary proposal. Then our binary output can be tested with the other tools. And we can track the spec as it changes, continuously over time. It's likely the final spec will not be radically different, and so that way we'll move towards it along with everything else.

[kripken]

I did a bunch of work on this, it's in src/wasm-binary.h. It should be most of the code to write the binary format, but it's not complete, and it's written but not compiled or tested.

I'll get back to this when I can, but if someone wants to work on this, that would be great. Getting it to write the binary format shouldn't be much more work.

[kripken]

Pull #100 landed, and there are now wasm-as and wasm-dis tools, that convert to and from the binary format, and they can parse/unparse basic stuff.

Still TODO is to verify that the spec test suite is converted ok, and runs ok after conversion.