• JavaScript's Tricky Rounding April 24th, 2018

    JavaScript rounds in a tricky way. It tricked all the engines, and even itself.

    Math.round() behaves the same as C’s familiar round with one key difference: it rounds halfways (“is biased”) towards positive infinity. Here is its spec in ES 5.1. It suggests an implementation too:

    The value of Math.round(x) is the same as the value of Math.floor(x+0.5)...

    And so every engine did that.

    Unfortunately, the implementation in the spec does not correctly implement the spec.

    One bug is that adding 0.5 can result in precision loss, so that a value less than .5 may round up to 1. Mac user? Try it yourself (Safari 11.0.3):

    > /System/Library/Frameworks/JavaScriptCore.framework/Versions/A/Resources/jsc
    >>> 0.499999999999999944 < .5
    true
    >>> Math.round(0.499999999999999944)
    1 
    One engine attempted to patch it by just checking for .5:
    double JSRound(double x) {
      if (0.5 > x && x <= -0.5) return copysign(0, x);
      return floor(x + 0.5);
    }
    However this fails on the other end: when x is large enough that fractional values can no longer be represented, x + 0.5 rounds up to x + 1, so JSRounding a large integer like Math.pow(2, 52) would actually increment it.

    What's a correct implementation? SpiderMonkey checks on the high end, and exploits the loss of precision on the low end:

    double math_round_impl(double x) {
       if (ExponentComponent(x) >= 52) return x;
       double delta = (x >= 0 ? GetBiggestNumberLessThan(0.5) : 0.5);
       return copysign(floor(x + delta));
    }
    fish's attempt just checks high and low:
    static const double kIntegerThreshold = 1LLU << 52;
    double jsround(double x) {
      double absx = fabs(x);
      if (absx > kIntegerThreshold) {
        // x is already integral
        return x;
      } else if (absx < 0.5) {
        // x may suffer precision loss when adding 0.5
        // round to +/- 0
        return copysign(0, x);
      } else {
        // normal rounding.
        // ensure negative values stay negative.
        return copysign(floor(x + 0.5), x);
      }
    }
    which produces surprisingly pleasant assembly, due to the compiler's fabs() and copysign() intrinsics.

    The ES6 spec sheepishly no longer suggests an implementation, it just disavows one:

    Math.round(x) may also differ from the value of Math.floor(x+0.5) because of internal rounding when computing x+0.5...

    JavaScript presumably rounds this odd way to match Java, and so the only engine to get it right out of the gate is Rhino, which simply calls back to Java's Math.round. Amusingly Oracle fell into the same trap with Rhino's successor Nashorn. Round and round we go!

  • Schrödinger? I hardly know her! September 8th, 2016

    At very small scales, particles are described by wavefunctions that obey the Schrödinger Equation. What do wavefunctions look like?

    The Wavefiz is a nifty visualizer that draws them! It's real physics: we're solving the Schrödinger Equation in real time with arbitrary potentials. But it's also just plain fun to play with!

    There's some non-mathy exercises to do too. Have you heard of the ground state energy or quantum tunnelling? Those pop right out - you can see them visualized.

    The visualizer was built using three.js and TypeScript. You can pitch in here on GitHub. And if you like quantum physics, and are near Silicon Valley, come meetup to learn quantum mechanics with us!

    Surf over to the Wavefiz to see it in action!

  • The One Second Dash August 15th, 2016

    The Amazon Dash is a $5 WiFi button that summons a truck to deliver you water or other stuff. Want your Dash to do something else? The popular approach is to sniff its ARP requests. This requires that Dash connect to your network, putting you perilously close to having some DUDE delivered with your IoT mood lighting.

    A more immediate problem is immediacy, or lack thereof: the Dash button only connects to your network after being pressed, so there's a ~5 second delay before anything can happen! This makes the ARP Dash hack unsuitable for interactive uses, like doorbells.

    Can we make it faster? Here's one way:

    1. "Setup" the Dash with a unique network SSID for a network that doesn't exist
    2. Use a WiFi adapter in monitor mode to observe probe requests on that network SSID

    This responds in < 1 second, which is fast enough for real time uses. And you don't even have to give the thing your password.

    A Raspberry Pi works when equipped with a WiFi adapter capable of monitoring mode. The RT5370 chipset is so capable - here's the one fish bought. Steer clear of the ubiquitous Realtek RTL8188CUS based devices.

    Head on over to the One Second Dash repo to get started!

  • fish shell 2.0 May 17th, 2013

    fish 2.0 is now released! fish is a fully-equipped command line shell (like bash or zsh) that is smart and user-friendly. fish supports powerful features like syntax highlighting, autosuggestions, and tab completions that just work, with nothing to learn or configure.

    Go get it:

       http://fishshell.com

    This marks the first release of fish in over four years, and includes many new features, fixes, and optimizations. See the release notes for a partial list of what's new.

    A big debt of gratitude to everyone who contributed to this release, including:

    Thank you for sharing your time, code, and ideas!

    P.S. Discuss fish in the #fish IRC channel in irc.oftc.net, or use the web chat (enter fish as the channel).

  • Yahoo! Chat - A Eulogy February 21st, 2013

    "Asswipe," replied Yahoo's server. That's when I knew I had it.

    Yahoo's public chat rooms have passed away. It is for the best, for the spam had spread everywhere. But they had a good run, operating for a decade and a half, an Internet eternity.

    Here are three funny stories from the Yahoo chat protocol.

    Body and Zoul

    Yahoo chat rooms started life as a Java applet, chugging along in Netscape Navigator 4. Support for chat was later added to Pager, their native app, which did its own chugging in Visual Basic. Initially, Pager had custom text rendering, but then they replaced it with an HTML view.

    Oops. Pager didn't escape message contents, and so it was possible for a message sender to coax the recipient into displaying arbitrary HTML - even fetching images off the web. XSS in its infancy.

    Oh dear, what to do? Not everyone would install a security update. But all messages went through Yahoo's servers, so they could fix it server-side: block the attack by rewriting the messages before sending them along. So Yahoo replaced the troublesome opening bracket < with a letter that sort of looked like a bracket: a capital Z. Messages containing <html> or <body> would be rewritten to Zhtml> and Zbody>.

    And more than a decade later, this methuselan workaround lives on:

    md55555555555...

    Yahoo chat was not as full of sexually unfulfilled college girls as the spam bots would have you believe. Before the captchas arrived in 2007 (which did little in any case), Yahoo battled the bots by obfuscating the login protocol. And once the bots caught up, obfuscating it again. Rinse and repeat - by the end, the protocol had grown to outrageous complexity. A puny excerpt of the login sequence:

    1. md5 the user's password
    2. md5 the password, followed by the fixed salt, followed by the password again
    3. md5 the password, followed by a fixed salt, followed by the second hash, followed by parts of the password, but interspersed with zeros
    4. hash the password
    5. hash the third hash
    6. Iterate the previous two steps 50 times, including the password in the hash every seventh time, and salting the hash too, except every third time
    7. md5 the result of that loop...

    And we have only barely begun. Should you wish to dive further, see the function yahoo_process_auth_0x0b.

    The Sacred, but Mostly the Profane

    fish wrote a client for Yahoo chat, but the protocol was not public. Reverse engineering the login protocol for a native OS X client meant running Ethereal in X11 to inspect a Java program running in the OS 9 Classic environment: a remarkable feat, but man, was it slow going. For a long time, connection attempts were met with radio silence and disconnection. Nothing, nothing, nothing...

    And then, all at once, Yahoo unleashed a stream of filthy, filthy obscenities. Yessss.

    You see, Yahoo was concerned that people might swear on the Internet, so they provided a list of words that the client should filter. But this list might need to be updated dynamically, in case someone on the Internet managed to think up a new word for sex. So rather than build the list into the client, they sent it to you from the server. Right in the first packet. In alphabetical order. Login successful, bitch.

    A kind soul has preserved a packet dump from a successful login. Cover your childrens' eyes and click the box below to read it:

    59 43 48 54 00 00 01 00 : 00 00 00 01 00 00 01 7F    YCHT            
    41 73 6B 46 6F 72 42 6F : 6F 7A 65 C0 80 61 68 6F    AskForBooze¿Äaho
    6C 65 2C 61 68 6F 6C 65 : 73 2C 61 73 73 68 6F 6C    le,aholes,asshol
    65 2C 61 73 73 68 6F 6C : 65 73 2C 61 73 73 77 69    e,assholes,asswi
    70 65 2C 62 69 61 74 63 : 68 2C 62 69 74 63 68 2C    pe,biatch,bitch,
    62 69 74 63 68 65 73 2C : 62 6C 6F 5F 6A 6F 62 2C    bitches,blo_job,
    62 6C 6F 77 5F 6A 6F 62 : 2C 62 6C 6F 77 6A 6F 62    blow_job,blowjob
    2C 63 6F 63 6B 73 75 63 : 6B 65 72 2C 63 75 6E 74    ,cocksucker,cunt
    2C 63 75 6E 74 73 2C 64 : 69 63 6B 68 65 61 64 2C    ,cunts,dickhead,
    66 75 63 6B 2C 66 75 63 : 6B 65 64 2C 66 75 63 6B    fuck,fucked,fuck
    69 6E 67 2C 66 75 63 6B : 6F 66 66 2C 66 75 63 6B    ing,fuckoff,fuck
    73 2C 68 61 6E 64 6A 6F : 62 2C 68 61 6E 64 6A 6F    s,handjob,handjo
    62 73 2C 6D 6F 74 68 65 : 72 66 75 63 6B 65 72 2C    bs,motherfucker,
    6D 6F 74 68 65 72 2D 66 : 75 63 6B 65 72 2C 6D 6F    mother-fucker,mo
    74 68 65 72 66 75 63 6B : 65 72 73 2C 6D 75 74 68    therfuckers,muth
    61 66 75 63 6B 65 72 2C : 6D 75 74 68 61 66 75 63    afucker,muthafuc
    6B 65 72 73 2C 6E 69 67 : 67 61 2C 6E 69 67 67 61    kers,nigga,nigga
    73 2C 6E 69 67 67 65 72 : 2C 6E 69 67 67 65 72 73    s,nigger,niggers
    2C 70 65 64 6F 66 69 6C : 65 2C 70 65 64 6F 70 68    ,pedofile,pedoph
    69 6C 65 2C 70 68 61 67 : 2C 70 68 75 63 2C 70 68    ile,phag,phuc,ph
    75 63 6B 2C 70 68 75 63 : 6B 65 64 2C 70 68 75 63    uck,phucked,phuc
    6B 65 72 2C 73 68 61 74 : 2C 73 68 69 74 2C 73 68    ker,shat,shit,sh
    69 74 73 2C 73 68 69 74 : 68 65 61 64 2C 73 68 69    its,shithead,shi
    74 74 65 72 2C 73 68 69 : 74 74 69 6E 67 C0 80 54    tter,shitting¿ÄT
    61 6E 67 6F 62 68 C0 80 : 20 C0 80 30 C0 80 31       angobh¿Ä ¿Ä0¿Ä1
    

    Eat your heart out, George Carlin.

    R.I.P. Yahoo chat. You will be remembered as you were: a crazy phuc. Whatever that means.

  • More Posts