Friday, August 29, 2014

Deconstructing Floats: frexp() and ldexp() in JavaScript

While working on my SqueakJS VM, it became necessary to deconstruct floating point numbers into their mantissa and exponent parts, and assembling them again. Peeking into the C sources of the regular VM, I saw they use the frexp() and ldexp() functions found in the standard C math library.

Unfortunately, JavaScript does not provide these two functions. But surely there must have been someone who needed these before me, right? Sure enough, a Google search came up with a few implementations. However, an hour later I was convinced none of them actually are fully equivalent to the C functions. They were imprecise, that is, deconstructing a float using frexp() and reconstructing it with ldexp() did not result in the original value. But that is the basic use case: for all float values, if
[mantissa, exponent] = frexp(value)
value = ldexp(mantissa, exponent)
even if the value is subnormal. None of the implementations (even the complex ones) really worked.

I had to implement it myself, and here is my implementation (also as JSFiddle):
function frexp(value) {
    if (value === 0) return [value, 0];
    var data = new DataView(new ArrayBuffer(8));
    data.setFloat64(0, value);
    var bits = (data.getUint32(0) >>> 20) & 0x7FF;
    if (bits === 0) { // denormal
        data.setFloat64(0, value * Math.pow(2, 64));  // exp + 64
        bits = ((data.getUint32(0) >>> 20) & 0x7FF) - 64;
    var exponent = bits - 1022;
    var mantissa = ldexp(value, -exponent);
    return [mantissa, exponent];

function ldexp(mantissa, exponent) {
  var steps = Math.min(3, Math.ceil(Math.abs(exponent) / 1023));
    var result = mantissa;
    for (var i = 0; i < steps; i++)
        result *= Math.pow(2, Math.floor((exponent + i) / steps));
    return result;
My frexp() uses a DataView to extract the exponent bits of the IEEE-754 float representation. If those bits are 0 then it is a subnormal. In that case I normalize it by multiplying with 264, getting the bits again, and subtracting 64. After applying the bias, the exponent is ready, and used to get the mantissa by canceling out the exponent from the original value.

My ldexp() is pretty straight-forward, except it needs to be able to multiply by very large and very small numbers. The smallest positive float is 0.5-1073, and to get its mantissa we need to to multiply with 21073. That is larger then the largest float 21023. By multiplying in steps we can deal with that. Three steps are needed for e.g. ldexp(5e-324, 1023+1074) which otherwise would result in Infinity.

So there you have it. Hope it's useful to someone.

Correction: The code I originally posted here for ldexp() still had a bug, it did not test for too small exponents. I fixed it above, and updated the JSFiddle, too. Also, Nicolas Cellier noticed other rounding and underflow problems, his suggestions for ldexp() are now used above.

Friday, July 04, 2014

SqueakJS runs Etoys now

TL;DR: Try Etoys in your web browser without a plugin (still buggy, but even works on iPad). Feedback from more platforms is very welcome, and fixes to improve the compatibility, too.
Half a year has passed since my initial release of SqueakJS. Now I can report on some significant progress since then.

For one, I adopted a UI layout similar to Dan’s Smalltalk-72 emulator, where the debugger interface is only visible when the system is stopped. Now that the basics are working, there is no need to show the debugger all the time. Try it yourself at the Lively page.

But more importantly, many more subsystems are working now. BitBlt is almost complete (all the important modes are implemented), WarpBlt works (for scaling and rotating morphs), the image can be saved, an emulated file system supports reading and writing of persistent files. This now is enough to not only run the very old and undemanding “mini.image”, but SqueakJS now can even run the very latest Etoys image, the same version as on Squeakland. Beware of the many incomplete features and outright bugs still left to be fixed, but try it for yourself here.

While Etoys feels a lot slower than the MVC “mini.image”, and some operations take many seconds, it is surprisingly responsive for normal interaction. On the browsers with the fastest JIT compilers (Safari on Mac, IE on Windows) it is almost good enough, even though no serious optimizations were done yet. It is also interesting to see that some browsers (Chrome and Firefox) are currently significantly slower. And not just a little slower, but Safari outperforms Chrome by 200% for this workload! This is likely due to Safari›’s excellent LLVM-based FTL JIT.

The remarkable thing about the screenshot above is how unremarkable it looks. Apart from the missing white oval behind the “Home” label it looks just like it’s supposed to. In comparison, a week ago the screen still looked like this:

The difference is that Tobias Pape and I added support for Balloon2D rendering. This is Squeak’s default vector rendering engine, originally created by Andreas Raab to show Flash animations. But unlike the rest of the SqueakJS VM, we did not port the original code. Instead, our plugin intercepts the drawing commands and renders them using HTML5 canvas drawing routines. While still far from complete, it can already render one kind of important shapes: TrueType font glyphs. They are defined by B├ęzier curves, which need to be rendered with anti-aliasing to look nice. And now that we can render text, the graphics are almost complete. Many more details still need to be implemented, especially color gradients.

This highlights one strength of Squeak: The VM and its plugin modules present a well-defined, stable interface to the outside world. That is what makes a machine truly “virtual”. In contrast, other systems rely on FFI (the foreign function interface) or similar techniques for extension. While convenient during rapid development, it does not keep the interface small and stable. That interface is overly broad and unpredictable. Typically, client code must be special-cased per platform. It's calling C functions directly, which may or may not exist on a given platform. That makes it much harder to move the system to another platform, and in particular one that is completely different, like the web browser. The Squeak Etoys image on the other hand did not have to be modified at all.

What I’d like to see fixed in Squeak is that there should be working fallback code for all non-essential primitive functions. This would make it much easier to get up and running on new platforms.

For SqueakJS, bugs need to get fixed, and many features are still missing to run Etoys fully. Adding support for other Squeak releases than Etoys would be great (closure/Cog/Spur images). Contributions are welcome: fork my github project.