Thursday, June 18, 2015

A quick overview of what WebAssembly is and what it is not (yet)

There's been a lot of buzz today about WebAssembly, and that's completely understandable. A bytecode form of Javascript has been on the minds of many web developers for a long time. But the online commentary seems to have been based more on hopes than on released information. I hope to clear up some of that confusion. Note that I'm not involved in the project at all, so some of this information is likely incorrect; feel free to leave a comment if I've gotten something wrong.

WebAssembly isn't a spec yet. It's not even a draft spec. It's an idea and a proof-of-concept. So far, that's all that's in the public. But it has a lot of promise.

The WebAssembly roadmap essentially spells out three phases:

  1. A minimum viable product (MVP) that is roughly analogous to asm.js, specifically targeting C/C++ as the source language
  2. Additional features, such as threads, SIMD, and proper exception handling, all still with a focus on C/C++
  3. "Everything else", including features meant to support more languages. One such feature is access from WebAssembly code to objects on the garbage-collected Javascript heap. This could enable WebAssembly code to access the DOM and web APIs (which would not be supported in either of the previous iterations). This phase also contains support for things like large heaps, coroutines, tail-call optimization, mmapping files, etc. If and when we get to this phase, I would expect it to get further split.

There will also be a polyfill, since browsers will not initially support WebAssembly. In fact, there is already a polyfill, but it's more of a proof-of-concept than an actual implementation. There is no WebAssembly spec yet; this polyfill is merely to test the viability of a binary-encoded AST.

Initially, it's not wrong to think of WebAssembly as binary-encoded asm.js, though that will change over time. It may eventually grow to the point that it could replace Javascript, but in its first two incarnations, you will still need some JS code (to interact with the DOM and with web APIs). A likely use case is to compile low-level, algorithmic code (think image processing, compression, or encryption code) to WebAssembly, but to still write the bulk of your application in plain JS. If you're not familiar with asm.js, it might make sense to look into it; many of the same limitations of that environment also appear to apply to the first incarnation of WebAssembly.

However, even at this early stage, WebAssembly does specify some features that even asm.js doesn't provide. In particular, it talks about 64-bit integer operations, which asm.js can't natively provide. The current polyfill POC doesn't seem to support them, and they may choose for the polyfill to always implement them as floating-point operations, but an actual runtime would need to provide proper support for int64 (and other sizes as well, like int8 and int16).

WebAssembly only deals with the binary format and runtime environment; it doesn't provide any new APIs for dealing with the DOM or the network or anything like that. It may eventually provide alternatives to other web APIs (WebWorkers would be an obvious one, when WebAssembly eventually adds threading support).

The current plan for WebAssembly is to not use bytecode in the same way as JVM or CLR use bytecode. Those VMs represent their bytecode as an instruction stream, similar to instructions for non-virtual machines. WebAssembly, on the other hand, appears to be going more for a "serialized abstract syntax tree" form. The claim seems to be that this can be compressed more efficiently than can be achieved using general-purpose compression routines, and that doesn't seem too crazy. This distinction isn't important for web app developers, though it could mean that "disassembled" WebAssembly is easier to grok than disassembled JVM bytecode.

WebAssembly will have defined binary AND text forms. So, while you won't be able to curl a WebAssembly file and immediately understand it, there will be tooling to convert from the binary form to the text form (which will certainly eventually be built into browsers). It seems likely that the bytecode semantics will make concessions to retain some degree of human readability when converted to text form.

I really like this quote from Peter Kasting in the comments on Ars. Like, seriously, if you have an Ars account, go give him some fake internet points.

Notably, the people working on WebAssembly are the PNaCl (Google) and asm.js (Mozilla) teams. In some sense this can be considered the followon effort to those projects, meant to combine the best attributes from each, and in a way that can be agreed on by all browser vendors.

This is exactly how the system is supposed to work: individual teams try to advance the state of the art, and eventually all those lessons learned are incorporated into a new and better system. See e.g. SPDY -> HTTP2. WebAssembly draws on both the past work and the experience of all those involved, and wouldn't be what it is without them.

I say this partly so the sorts of people who have bemoaned "non-standard" vendor efforts in the past may have reason to pause next time they feel the urge to do so. No one wants a balkanized world forever, but that vendor-specific effort may gain the sort of real-world experience necessary to come back and design a great cross-vendor solution afterwards. All four major browser vendors have taken flak for this sort of thing in the past, and in my mind often unfairly so.

All told, it looks like this is just the first, small step. I'm a little surprised that they went public so early. Either they really plan to develop it in the open, or the tech media got wind of it and blew it well out of proportion. Whatever the case, this looks like it will be a large undertaking. It's very promising that everybody seems to be at the table. And given that the browser vendors appear to want to actively develop their products, we might actually be able to use this within a couple of years.

What a time to be alive!

Tuesday, June 16, 2015

The joys of parsing a toy programming language

In my personal time, I've been playing at building a toy programming language. Progress has been slow, but things are finally starting to come together. Last night, I ended up finding an interesting bug, and I wanted to document it here.

The syntax of my language isn't super complicated. Here's an example of a function:

def foo(a, b) = a + b

Because this language is a so-called modern language, it has to support lambdas as well. Here's an example:

val bar = (a, b) => a + b

You can call functions and lambdas using the same syntax:

foo(5, 7)
bar(5, 7)

Naturally, since lambdas are first-class, we need to support more complicated call syntax as well. In particular, this should be allowed:

((a, b) => a + b)(5, 7)

In order to support that, here's the section of the grammar that describes function calls (you can imagine the rest of the grammer):

FnCall    :=  Callable lparen Args rParen
Callable  :=  identifier
          :=  lParen Expression rParen
Args      :=  identifier MoreArgs
          :=  epsilon
MoreArgs  :=  comma identifier MoreArgs
          :=  epsilon

My compiler was able to successfully compile and run this extremely simple program:

val bar = (a, b) => a + b
bar(5, 7)

But imagine my surprise when it failed to compile this program:

val bar = (a, b) => a + b
(bar)(5, 7)

Looking at the parse tree, it was obvious what had happened. It turns out that my grammar was ambiguous, and the parser had chosen this interpretation:

val bar = (a, b) => a + (b(bar))(5, 7)

Rather than parsing this as a definition and a corresponding expression, it instead parsed it as a single definition. It assumed that b was a function of one parameter, which returned a function of two parameters. Even this simpler grammar has the same problem:

FnCall    :=  identifier lparen Args rParen
Args      :=  identifier MoreArgs
          :=  epsilon
MoreArgs  :=  comma identifier MoreArgs
          :=  epsilon

Given this program:

val bar = (a, b) => a + b
(5 + 7) * 2

This could (and would) get parsed as:

val bar = (a, b) => a + b(5 + 7) * 2

(It's worth noting that, if I had been using a shift / reduce parser, this would have been detected as a S/R conflict. But I'm not using a S/R parser; I'm using the Scala parser combinator library, mostly because it was easy to get started and I haven't outgrown it yet.)

Looking at Scala, from which I stole a lot of my syntax, I found that newline handling is a bit complicated, though the rules are laid out plainly in section 1.2 of the Scala language spec. Essentially, a newline can be treated either as plain whitespace or as a statement terminator, depending on the context. Within a parenthesized expression, newlines are always treated as whitespace. Outside an expression, newlines are treated as statement terminators if they appear between a token that could end a statement and a token that could begin a statement. One one hand, having written a fair amount of Scala, the rules feel pretty natural and intuitive. However, you do end up with strange behavior at the edges, as the following example demonstrates:

(succ
  (5))   => 6

{succ
  (5)}   => 5

On the other hand, Haskell (with which I'm admittedly not very familiar) appears to use indentation level to determine expression grouping. That is, while this is valid:

main = putStrLn "hi"

and this is also valid:

main = putStrLn 
 "hi"

this is not:

main = putStrLn 
"hi"

Context is not considered, so unlike Scala, this still fails:

main = (putStrLn 
"hi")

Both of these approaches have merit. Haskell's approach is natural enough, though there are some unambiguous representations that it would reject. Scala's approach is more permissive, at the cost of more complicated implementation rules and more surprising behavior. I can't tell which is more appropriate for my language.

For now, I took neither approach. I realized that, as far as I know, I have but one case where expressions are ambiguous - when the parameters to a function appear on a separate line from the Callable itself. It was possible for me to simply require that the whitespace between the Callable and its parameters not include any newlines. So an identifier at the end of a line will NEVER be considered to be a function call. I don't think this will remain this way forever, but I think it will get me unstuck.

Monday, March 04, 2013

Updating a System Shock 2 Wallpaper for HD Resolutions (in Javascript!)

Back when I was in college, I was a big System Shock 2 fan. My favorite co-op experience of all time was when my dorm roommate and I played SS2 together. I had all kinds of ideas for case mods (even though I had neither the money nor the tools to make it happen). Ultimately, my only creative contribution to the world of Shock was to combine two wallpapers that were floating around the net into one of my very own:

Yeah, I was pretty pleased with myself back in the day. In any case, I wanted to commemorate the recent GoG re-release of SS2 by inviting Shodan to adorn my desktop yet again. Unfortunately, screen resolutions have increased quite a bit in the intervening years, and a pixelated Shodan simply won't do. Fortunately, in the GoG re-release, they included a ludicrously high resolution 5100x3338 pixel render. All I need to do is to scale that down, generate the ASCII half, blend them, and Bob's your uncle.

I'm sure that there are a lot of image to ASCII generators out there, but I can't shy away from a chance to learn something, so I decided to try to write my own. That's not even the interesting part of the story. Because I'm a masochist, I decided to do it with HTML and Javascript. I figured that, between the drag-and-drop API, canvas, and a high-performance JS engine like V8, I could probably get away with it.

Many hours later, I have something that basically works. I'll probably clean it up and get it posted to GitHub. It wasn't too hard to allow dropping an image file onto the page. I end up doing a lot of work against a scratch canvas before finally dumping the output into an image element using the HTMLCanvasElement toDataUrl method. This is great; I can then drag the image off the page and onto my desktop (something that the canvas element doesn't automatically do). Even though the data URL is ridiculously long, it correctly displays on the screen. However, when I was working with the original 17 megapixel image, I found that dragging the output image out of my browser would immediately crash the Chrome tab. Fortunately, Chrome has no problems with the image at my target resolution (1920x1080).

Because this extremely long data URL feels pretty sketchy, I looked to see if there was a way around it. I would love to output the results to a canvas element instead of an image. All I need is to use the DnD API to make the canvas a valid drag source. Of course, in order to do that, I need to be able to generate the PNG bytestream, as well as synthesize a File object in the browser. While it's definitely possible to build a pure-JS PNG encoder, I don't see any way to synthesize a File object. Although the DnD spec specifically asks for a File, maybe it would be happy with an arbitrary Blob instead; I don't know, and I haven't yet tried. If the spec doesn't support this use case, it's a shame; I can think of a number of cases where it would be neat to generate a file from client-side JS.

I like to think that my skills of an artist have improved in the intervening years as well. A little stylistic shading, and here is the result.

I used a different technique to generate the digital side (the original used 0s and 1s and modulated the intensity on a pixel-by-pixel basis; I achieve my shading by choosing from a larger palette of characters). Still, I feel like the end result has the same tone as the original. And just like last time, I'm pretty pleased with myself. Let me know what you think!

Edit: The code is available on GitHub. You can try it out on my site.

Saturday, January 14, 2012

Using Apache on Mac OS X to serve files outside ~/Sites

I'm working on a web project that basically contains just static HTML and Javascript. (well OK, there's also one, small PHP script, but it might be going away in the near future). I tend to keep all my source code in ~/src, but to host it, I also need it to appear in ~/Sites. After some small trial-and-error, I ended up putting the everything (git repo and all) into ~/Sites, and then symlinked it to ~/src. It wasn't pretty, but it worked.

So I just did some reorganization that pretty much invalidated that old structure. In particular, I have moved everything that needs to be deployed into ~/src/project/web. However, I want it to be accessible via http://localhost/me/project. I tried physically moving the project back into ~/src, and then making a symlink to the subdirectory, but that didn't work. Apache would still produce 403s for all the relevant files. So I had to roll up my sleeves and dive into Apache configuration.

Before I go further, I'm compelled to pull out the old soapbox. I have painfully little experience with Apache - I have never had to configure or support it in a production environment, and that makes me happy. From this position of ignorance, I have decided that Apache is a dinosaur that should have died a long time ago. For example, instead of configuring the server from the request's point of view (as has been popularized by Rails' routing logic), it is configured from the filesystem's point of view. The default Mac OS configuration has, buried somewhere in the middle of the file, a directive that disallows the serving of all files under /. Because, I guess, they would be served by default if that directive wasn't present? But still, nobody seems to want to spend the time to produce a replacement web server, and so we struggle on. </rant>

The default Apache install on MacOS 10.7 uses a split apache configuration file. The bulk of the configuration is in /etc/apache2/httpd.conf. However, each user also gets their own /etc/apache2/users/me.conf, which are all imported into the main configuration. And while the main configuration file specifies the FollowSymlinks option, I discovered that the same is not true in my personal config file. All I had to do was to add the FollowSymlinks option to that configuration file, restart Apache, and everything started working.

So if you have only basic web serving needs, the default config should suffice. If, however, you want/need to spread the files around your disk, you need to mess with the Apache configuration.

Monday, September 05, 2011

Mysterious, Blank User in 10.7 Sharing Dialog

I wanted to copy some files from my PC to my Mac. When I went to turn on SMB sharing, I came across this:

I was wondering about the identity of this phantom user. It turns out that it is the macports user. He doesn't show up on the login screen. He never showed up under 10.6. Apparently, Apple changed something about the way users are reported to applications.

If it bothers you, you can fix it with dscl.

sudo dscl . -create /Users/macports RealName macports

The first parameter is the machine you want to administer; . is apparently a shortcut for localhost. Then we give the command - we want to create a new key. Then we specify where this key should be created - in this case, the macports user's Directory Services path. Next is the name of the key - RealName is what appears to be used by the sharing dialog. (RealName is also assigned on users you create through System Preferences). Finally, we provide a value for this user's name. Now, we have this:

Tuesday, September 14, 2010

DES Encryption As Used in VNC Authentication

A few notes about how DES is used in the VNC Authentication security type (type 2)

  1. DES is used in ECB mode.
  2. The ECB Key is based upon an ASCII password. The key must be 8 bytes long. The password is either truncated to 8 bytes, or else zeros are added to the end to bring it up to 8 bytes. As an additional twist, each byte in flipped. So, if the ASCII password was "pword" [0x 70 77 6F 72 64], the resulting key would be [0x 0E EE F6 4E 26 00 00 00].
  3. The VNC Authentication scheme sends a 16 byte challenge. This challenge should be encrypted with the key that was just described, but DES in ECB mode can only encrypt an 8 byte message. So, the challenge is split into two messages, encrypted separately, and then jammed back together.
Here is some pseudocode (in Erlang) that should explain better than words can.
password_to_key(Password) ->
    Flipped = lists:map(fun flip_byte/1, Password),
    Truncated = truncate(Flipped, 8),
    pad(Truncated, 8, $\0).

encrypt_challenge(Password, Challenge) ->
    Key = password_to_key(Password),
    <<High:8/binary, Low:8/binary>> = Challenge,
    EncHigh = crypto:des_ecb_encrypt(Key, High),
    EncLow = crypto:des_ecb_encrypt(Key, Low),
    <<EncHigh/binary, EncLow/binary>>.

Wednesday, July 28, 2010

Unpacking a Safari Extension

So, now that Safari extensions are official (and not just a developer curiosity), I decided to see what people had managed to make over at the extension gallery. It looks like there are some cool ideas out there. I was somewhat interested in the Exposer extension, which sounded a bit like Exposé for Safari. It seems like it kinda works, except that it doesn't always bring up the list of windows, and it's also really slow (it looks like visibleContentsAsDataURL is the culprit, natch, plus I have dozens of tabs open at a time).

Anyway, while I was checking it out, I realized that I had no idea what some of these Safari extensions were doing in the background. Stop and think for a moment; do you really want to run code that some Jimmy wrote in his basement to be able to watch everything that you do in your browser? Maybe I'm just paranoid, but I'd like to know what is really going on.

So, naturally, I tried unpacking an extension. It wasn't particularly hard, but you have to realize that a .safariextz file isn't a ZIP archive. It's a XAR. I know; I opened it up in my hex editor.

Here's how you can unpack one for yourself:

xar -xvf extension.safariextz -C ~/Desktop

Don't worry; there's a directory just inside the safariextz archive. Now to see if there's anything malicious in these extensions. (Exposer looks clean so far.)