Javascript – Comma Trick

Reading An Open Letter to JavaScript Leaders Regarding Semicolons where Isaac Z. Schlueter explains his unorthodox coding style a line of code struck me.

if (!cb_ && typeof conf === "function") cb_ = conf , conf = {}

He was able to execute more than one statement in a if without the need of { }. I have recently been working on python scripts for http://db.mmo-champion.com/ and this discovery made me want to imitate pythonic indentation in Javascript.

The comma trick

You can use the , separator to chain statement. This group them into only one block of code. Therefore you can execute all of them without the need of { }. The rule is easy: put a , at the end of every line but a ; on the last line of the block.

if (test)
  first_action(), // Note the important ','
  second_action(); // Note the lack of ','
third_action();

For example, it is possible to write a little program that outputs the Fibonacci Numbers without the use of any { } and therefore imitate python indentation style with no ending }.

var curr = 0, next = 1, tmp;
for (var i = 0; i < 10; ++i)
  tmp = curr + next,
  curr = next,
  next = tmp,
  console.log('Fibo', i, '=', curr);
 
// ...
// Fibo 5 = 8
// Fibo 6 = 13
// Fibo 7 = 21
// Fibo 8 = 34
// ...

// …
// Fibo 5 = 8
// Fibo 6 = 13
// Fibo 7 = 21
// Fibo 8 = 34
// …

The issues

Sadly, the use of this is trick is extremely limited. You cannot use any of these keywords inside the “blocks”: if, for, var.

for (var i = 0; i < 3; ++i)
  k = i * 10 + 1,
  if (k % 2 == 0)
    console.log(i);
// SyntaxError: Unexpected token if
 
for (var i = 0; i < 3; ++i)
  var k = 10,
  console.log(k);
// Firefox: SyntaxError: missing ; before statement
// Chrome: SyntaxError: Unexpected token .

for (var i = 0; i < 3; ++i)
var k = 10,
console.log(k);
// Firefox: SyntaxError: missing ; before statement
// Chrome: SyntaxError: Unexpected token .

Beginning with comma

If you don’t fall into the use cases of these issues and you are a bit worried about the bugs resulting in the mix of the , and ;, you can start your lines with commas.

var k;
for (var i = 0; i < 10; ++i)
  , k = i * 10
  , console.log(i)
// SyntaxError: Unexpected token ,

But we need to add some empty statement before the first , so that it compiles. In python : is used but it doesn’t parse in Javascript. We can use $ for example, it is a valid statement: it reads the variable and does nothing with it.

var $;
for (var i = 0; i < 10; ++i)$ // Use of $ instead of : in python
  , k = i * 10
  , console.log(k)
// 0
// 10
// ...

Debugging purpose

The main use of this trick I can see is for debugging purpose. If there is code executed in a test without { } and you want to log something when the program goes into this part of the code. Before you had to add { } and then remove them which is really annoying. Now it’s easier!

for (test)
  doSomething();
// Before
for (test) {
  val = doSomething();
  console.log('Executed!', val);
}
 
// After
for (test)
  val = doSomething(),
  console.log('Executed!', val);

// After
for (test)
val = doSomething(),
console.log(‘Executed!’, val);

Conclusion

Using the comma trick to do { }-less indentation is far from viable. However this may still be useful for debugging and overall it is fun to try new coding styles!

$(‘.wp_syntax span:contains(SyntaxError)’).css(‘color’, ‘red’);

As I wanted to find good reasons to use Javascript as a language to do image processing, I thought of distributed computing that would be extremely easy to do. Users have nothing to install, they just have to visit a webpage. And since we want many users to participate we could embed it into a popular webpage.

There are many issues using browsers as distributed computing nodes:

  • User approbation: Will they allow you to run random script on their machine as they just wanted to visit a site.
  • Liability of the Data: Since process is being done on untrusted people, we must find ways to verify it.
  • User disconnection: We are going to compute the data while they are browsing the web, if they change of URL, reload the page or close their browser we wont get any result.

User Disconnection Over Time

In order to test the last point, I added a small Javascript program on the popular website MMO-Champion.com. Every one minute, it will send the time spent on the page to my server. I ran it for about 2 hours (then it DDOS’ed my server :(). I aggregated the results in the following chart.

var chart;
$(document).ready(function() {
chart = new Highcharts.Chart({
chart: {
renderTo: ‘chart-browser-1’,
defaultSeriesType: ‘spline’
},
title: { text: ‘Users “alive” after x minutes’ },
yAxis: { title: { text: ‘Users’ }, max: 4500 },
xAxis: { title: { text: ‘Minutes’ }, categories: [1, 2], labels: {step:10}},
plotOptions: { spline: { lineWidth: 2, states: { hover: { lineWidth: 3 } }, marker: { enabled: false, states: { hover: { enabled: true, symbol: ‘circle’, radius: 5, lineWidth: 1 } } } } },
tooltip: { formatter: function() { return ‘‘+ this.y +’ users after ‘ + this.x + ‘ minutes
‘; }},
series: [
{
name: ‘Users’,
data: [4315, 3206, 2521, 1969, 1586, 1318, 1305, 1155, 997, 938, 892, 878, 874, 873, 773, 769, 753, 742, 741, 739, 738, 726, 726, 720, 719, 716, 709, 706, 703, 698, 693, 692, 690, 683, 683, 681, 673, 672, 671, 666, 663, 661, 660, 659, 656, 652, 650, 645, 642, 632, 628, 615, 583, 580, 549, 534, 530, 515, 496, 493]
}
]
});
});

We can extract 3 phases from this graph.

  • Under 5 minutes the user is really likely to disconnect.
  • Between 5 and 15 minutes, the chance of disconnection is reducing
  • After 15 minutes, really few users are disconnecting.

You can see it in another way:

  • 50% of the users that have stayed 10 minutes are staying 1 hour.
  • 10% of the users that have stayed 1 minutes are staying 1 hour.

Chance of Script Completion

What we really want to know is either or not our script will complete. In order to test that I took the data we gather and computed the percentage of users that would still be there X minutes later.

var chart;
$(document).ready(function() {
chart = new Highcharts.Chart({
chart: {
renderTo: ‘chart-browser-2’,
defaultSeriesType: ‘spline’
},
title: { text: ‘Chance of completing a script before a user disconnects’ },
yAxis: { title: { text: ‘Chance of Completion’ }, min: 0, max: 100 },
xAxis: { title: { text: ‘Minutes’ }, categories: [1, 2], labels: {step:10}},
plotOptions: { spline: { lineWidth: 2, states: { hover: { lineWidth: 3 } }, marker: { enabled: false, states: { hover: { enabled: true, symbol: ‘circle’, radius: 5, lineWidth: 1 } } } } },
tooltip: { formatter: function() { return ‘‘ + this.y + ‘% chance of completing a ‘ + this.series.name + ‘ script after ‘+ this.x +’ minutes
‘; }},
series: [
{
name: ‘1 minute’,
data: [74, 78, 78, 80, 83, 99, 88, 86, 94, 95, 98, 99, 99, 88, 99, 97, 98, 99, 99, 99, 98, 100, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 98, 100, 99, 98, 99, 99, 99, 99]
},
{
name: ‘5 minutes’,
data: [30, 40, 45, 50, 59, 67, 67, 75, 87, 82, 86, 85, 84, 84, 95, 95, 96, 97, 97, 97, 97, 97, 97, 97, 97, 96, 97, 97, 97, 97, 98, 97, 97, 98, 97, 97, 98, 98, 98, 98]
},
{
name: ‘10 minutes’,
data: [20, 27, 34, 44, 48, 58, 57, 64, 74, 78, 82, 82, 83, 82, 93, 93, 94, 95, 94, 94, 93, 95, 95, 94, 94, 95, 94, 95, 95, 95, 95, 95, 95, 96, 96, 95, 96, 95, 95, 94]
}
]
});
});

After 15 minutes, a script that takes 1-10 minutes to complete has 95% chance of finishing without being interrupted.

Conclusion

The user disconnection is not really an issue. If do the computation on users that are staying more than 15 minutes, we have a 95% rate of completion for a 10 minutes script.

Javascript – Array Performances

Image Processing is an active research area and it is mostly written in C and C++ because of performance reasons. Browser makers are at war to make Javascript fast. I want to know if it is viable to do it in Javascript.

At the moment, there are really few people doing Image Processing in Javascript. I listed some examples there:

Image processing is computational heavy, you have to do the same operation on millions of elements. In order to get acceptable performances we should look into all the possible ways to implement it and micro benchmark those. Today we start with the different types of Arrays.

Different types of Arrays

In Javascript there are 3 ways to get an array of data.

  • Classic Arrays. The Javascript Arrays that you get using [1, 2, 3] or new Array(size)
    var classic = new Array(1048576);
  • Canvas Data. You can access the raw pixel elements of a canvas in an array. It’s an array of 4 * width * height * unsigned 8 bit integers (0 – 255).
    var canvas = $('#canvas').getContext('2d').getImageData(0, 0, 512, 512).data;
  • Typed Arrays. They are being introduced in Javascript for WebGL (spec).
    var typed8 = new Uint8Array(1048576);
    var typed32 = new Uint32Array(1048576);

Benchmarks

The objective of this benchmark is to test both read and write abilities of the arrays for use in image processing. We used an array of 1 millions of elements (1024 * 1024) with random values ranging from 0 to 255. We benchmark a loop that increases all the values by one.

for (var i = 0; i < 1048576; ++i) {
  array[i] += 1;
}
Note: The following results were made in December 2010. The implementation of Typed Arrays have improved a lot. The benchmark and conclusions are no longer accurate.

var chart;
$(document).ready(function() {
chart = new Highcharts.Chart({
chart: {
renderTo: ‘chart-javascript’,
defaultSeriesType: ‘column’
},
title: {
text: ‘Array Performance’
},
xAxis: {
categories: [‘Classic Array’, ‘Canvas Data’, ‘Uint8Array’, ‘Uint32Array’]
},
yAxis: {
allowDecimals: false,
min: 0,
title: {
text: ‘Operations per second (higher is better)’
}
},
tooltip: {
formatter: function() {
return this.x + ‘, ‘ + this.series.name + ‘: ‘+ this.y +’
‘ }
},
series: [{
name: ‘Chrome’,
version: ‘10.0.611.0 Canary’,
data: [70, 56, 40, 43]
}, {
name: ‘Firefox’,
version: ‘Minefield 4.0b9pre’,
data: [83, 58, 37, 37]
}, {
name: ‘Opera’,
version: ‘11.00 Beta 1111’,
data: [65, 80]
}, {
name: ‘Safari’,
version: ‘5.0.3 (7533.19.4)’,
data: [85, 18]
}]
});
});

(Chrome 10.0.611.0 Canary, Firefox Minefield 4.0b9pre, Opera 11.00 Beta 1111, Safari 5.0.3 (7533.19.4))

Conclusion

Typed Arrays are not viable

Typed arrays are a new addition to Javascript and the specifications are not frozen yet. A wish would have been that they perform better as they are direct machine representation. However benchs shows us the opposite. There is probably a lot of boxing / unboxing being done behind the scene between the representation and the number type.

One advantage of typed arrays is the ability to instantly work on a raw binary image (like p*m). All you have to do is to map your typed array to the file data part.

Since Typed Arrays are not implemented on all browsers and are slower than both classic arrays and canvas, they should not be used right now.

Classical Arrays

In both Chrome and Firefox classical arrays are faster than canvas (respectively 25% and 45%). They are containing numbers that are stored on either 32 or 64 bits (Mozilla Implementation). This is more than the 8 bits of the Canvas element.

Images are usually being stored in binary files readable either through the Canvas element or the Typed Arrays. The use of Classical Arrays requires to do 2 type conversions (loading and saving). This is a big overhead for small processing.

If you want to do heavy processing and are targeting either Firefox or Chrome, Classical Arrays may be a good choice. For more than 8 bits values it is the preferred method.

Canvas Arrays

Canvas Arrays are slower than classical arrays in Chrome and Firefox, however they are really fast on Opera. They have one huge advantage is the ability to be read and written directly through the canvas element. But they are limited to unsigned 8 bits.

If you want to do normal processing on traditional rgb values, Canvas Array is the best option. Especially on Opera where it is blazing fast.

As I read an article about solving the 8-queen problem storing the board in a 64bit integer (French) I wanted to test it in Javascript. I knew that numbers where not stored as int64 but who knows, maybe it would have worked!

As you may have expected, it failed, giving completly off results. The reason behind this is a lack of precision, the least significant bits are being ignored.

(0x8040201008040201).toString(2)
//  10000000 01000000 00100000 00010000 00001000 00000100 00000010 00000001
>> "10000000 01000000 00100000 00010000 00001000 00000100 00000000 00000000"
                                                                ^         ^

Floating Points

The reason behind this behavior is the fact that numbers are stored as floating points! The best way to know what’s the exact storage system is to look at the specifications:

The type Number is a set of values representing numbers. In ECMAScript, the set of values represents the double-precision 64-bit format IEEE 754 values including the special “Not-a-Number” (NaN) values, positive infinity, and negative infinity.

Source: ECMA 262 – 4.3.20 Number Type

Looking at Wikipedia we’ve got this table:

table.center {
text-align: center;
margin: 0 auto;
border-collapse: collapse;
}
table.center, table.center td {
border: 1px solid #ccc;
}
table.center td {
width: 100px;
}

Total bits Sign Exponent Significand
64 1 11 52

If you don’t know how floating point values are working, let me quick explain it to you. It’s in fact really simple. You start with a normal unsigned integer, in this case of 52 bits. You shift it left or right with the value of the exponent, here stored on 11 bits. And if the sign bit is set, you mark it as negative. (This is a really simplistic view, but serve the purpose here!)

Example:

Significand: 1000 1100 1001, Exponent: 4, Sign: 1
 
- 1000 1100 1001 0000
                < <<<

– 1000 1100 1001 0000
< <<<

As you can see, when the exponent is set, 0 are being added at the end of the number. This is the source of our precision loss.

Maximum Integer

With this in mind we can guess the biggest number that does not suffer from this. We have to fill the significand with 1, set the exponent to 0 and the sign to 0. It is the number 253-1.

Significand: 111..111 ~ 52, Exponent: 0, Sign: 0
 
  1111 1111 .... 1111 = 2 ^ 53 - 1

1111 1111 …. 1111 = 2 ^ 53 – 1

Now let’s see what happen if we want to write 253.

Significand: 100..000 ~ 52, Exponent: 1, Sign: 0
 
1 0000 0000 .... 0000 = 2 ^ 53
                    <

1 0000 0000 …. 0000 = 2 ^ 53
<

It still works due to the fact that the least significant bit is set to 0 during the shift. However this is impossible to write 253+1, the next number we can write is 253+2!

Significand: 100..001 ~ 52, Exponent: 1, Sign: 0
 
1 0000 0000 .... 0010 = 2 ^ 53 + 2
                    <

1 0000 0000 …. 0010 = 2 ^ 53 + 2
<

When Trouble Arises!

Finally, we can provide the first example such as n == n + 1!

Math.pow(2, 53) == Math.pow(2, 53) + 1
>> true

You should take care using traditional loops with big numbers, they will go infinite after that maximum integer value.

// WARNING: DO NOT TRY THIS AT HOME!
 
var MAX_INT = Math.pow(2, 53); // 9 007 199 254 740 992
for (var i = MAX_INT; i < MAX_INT + 2; ++i) {
  // infinite loop
}

var MAX_INT = Math.pow(2, 53); // 9 007 199 254 740 992
for (var i = MAX_INT; i < MAX_INT + 2; ++i) {
// infinite loop
}

Conclusion

The integer part of the Number type in Javascript is safe in [-253 .. 253] (253 = 9 007 199 254 740 992). Beyond this there will be precision loss on the least significant numbers.

If you want to use bigger integers there are several options:

  • String: if you don’t want to perform arithmetic operations on them.
  • Combine Multiple Numbers: One number gives you 52 bits of precision. It’s possible to use an array of them to achieve the precision you need. See Closure Long (Int64) and Leemon Big Integer for examples.

Javascript – Fake Arrays

A friend of mine gave me a great challenge. Find out how jQuery did to return objects that behave like arrays but that are not arrays! The aim of this article is to find out how Firebug and Web Inspector can display an object with the bracket notation.

$('a')
>> [<a href="http://vjeux.com/">vjeux</a>, <a href="http://google.com/">google</a>]

Not an Array!

First, let’s make sure that this is really not an Array. If you wonder why just not subclassing the array, there are many reasons explained on this great article.

// Easy way
typeof $('a')
>> "object"
 
// Normal way
$('a') instanceof Array
>> false
 
// Duck typing ...
$('a').indexOf
>> undefined
 
// Object toString
// http://whattheheadsaid.com/2010/10/cross-context-isarray-and-internet-explorer
Object.prototype.toString.call($('a'))
>> "[object Object]"
 
// http://ajaxian.com/archives/isarray-why-is-it-so-bloody-hard-to-get-right
$('a').constructor
>> function Object() { [native code] }
 
// ES5 Way
// https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/isArray
Array.isArray($('a'))
>> false

// Normal way
$(‘a’) instanceof Array
>> false

// Duck typing …
$(‘a’).indexOf
>> undefined

// Object toString
// http://whattheheadsaid.com/2010/10/cross-context-isarray-and-internet-explorer
Object.prototype.toString.call($(‘a’))
>> "[object Object]"

// http://ajaxian.com/archives/isarray-why-is-it-so-bloody-hard-to-get-right
$(‘a’).constructor
>> function Object() { [native code] }

// ES5 Way
// https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/isArray
Array.isArray($(‘a’))
>> false

Testing …

Obviously Firebug and Web Inspector must use another technique. What they need to display an Array is only the length property and the keys [0 .. length-1]. So let’s try!

({0: 42, 1: 666, length: 2})
>> Object { 0=42, 1=666, length=2 }

This is obviously not working 🙁

In Source the Truth Lies!

Hopefully, both Webkit and Firebug are open source projects, this means that anyone can browse the source code and therefore tell exactly what happens behind the scene.

// Web Inspector Source Code
// http://trac.webkit.org/browser/trunk/WebCore/inspector/front-end/InjectedScript.js#L409
 
// FireBug's array detection.
if (isFinite(obj.length) && typeof obj.splice === "function")
  return "array";

// FireBug’s array detection.
if (isFinite(obj.length) && typeof obj.splice === "function")
return "array";

We can see that Duck Typing is being used. It is now really easy to trick Firebug and Web Inspector to make them believe that your objects are arrays! Only 3 small rules are required:

  • [0 .. length – 1]: Array elements
  • length: Set to a positive integer
  • splice: Any function (even empty)

And here is the demo 🙂

({0: 42, 1: 666, length: 2, splice: function() {}})
>> [42, 666]

WoWTal.com Cataclysm

Check out the updated World of Warcraft talent calculator I’ve been working on 🙂

// Add VideoJS to all video tags on the page when the DOM is ready
VideoJS.setupAllWhenReady();

Javascript – Slug

A slug is a way to represent a title with a limited charset (only lowercase letter and dash) to be inserted in the url. Even if it is a common function there is no good enough implentation when you Google for it.

Here are the features I needed:

  • No multiple dashes. ---- is converted to -
  • No wrapping dashes. -title- is converted to title
  • Basic support for internationalization. Coût d'éclat is converted to cout-d-eclat Don’t look at the spelling mistake!
  • Basic support for common signs. 13$ & 12€ is converted to 13-dollar-and-12-euro

Demo

You can try the demo and see if it fits your needs.
var keys = keys || function (o) { var a = []; for (var k in o) a.push(k); return a; };
slug = function (string) {
// var accents = “àáäâèéëêìíïîòóöôùúüûñç”;
var accents = “u00e0u00e1u00e4u00e2u00e8”
+ “u00e9u00ebu00eau00ecu00edu00ef”
+ “u00eeu00f2u00f3u00f6u00f4u00f9”
+ “u00fau00fcu00fbu00f1u00e7”;
var without = “aaaaeeeeiiiioooouuuunc”;
var map = {‘@’: ‘ at ‘, ‘u20ac’: ‘ euro ‘,
‘$’: ‘ dollar ‘, ‘u00a5’: ‘ yen ‘,
‘u0026’: ‘ and ‘, ‘u00e6’: ‘ae’, ‘u0153’: ‘oe’};
return string
// Handle uppercase characters
.toLowerCase()
// Handle accentuated characters
.replace(
new RegExp(‘[‘ + accents + ‘]’, ‘g’),
function (c) { return without.charAt(accents.indexOf(c)); })
// Handle special characters
.replace(
new RegExp(‘[‘ + keys(map).join(”) + ‘]’, ‘g’),
function (c) { return map[c]; })
// Dash special characters
.replace(/[^a-z0-9]/g, ‘-‘)
// Compress multiple dash
.replace(/-+/g, ‘-‘)
// Trim dashes
.replace(/^-|-$/g, ”);
};

Code

var keys = keys || function (o) { var a = []; for (var k in o) a.push(k); return a; };
 
var slug = function (string) {
//  var accents = "àáäâèéëêìíïîòóöôùúüûñç";
  var accents = "u00e0u00e1u00e4u00e2u00e8"
    + "u00e9u00ebu00eau00ecu00edu00ef"
    + "u00eeu00f2u00f3u00f6u00f4u00f9"
    + "u00fau00fcu00fbu00f1u00e7";
 
  var without = "aaaaeeeeiiiioooouuuunc";
 
  var map = {'@': ' at ', 'u20ac': ' euro ', 
    '$': ' dollar ', 'u00a5': ' yen ',
    'u0026': ' and ', 'u00e6': 'ae', 'u0153': 'oe'};
 
  return string
    // Handle uppercase characters
    .toLowerCase()
 
    // Handle accentuated characters
    .replace(
      new RegExp('[' + accents + ']', 'g'),
      function (c) { return without.charAt(accents.indexOf(c)); })
 
    // Handle special characters
    .replace(
      new RegExp('[' + keys(map).join('') + ']', 'g'),
      function (c) { return map[c]; })
 
    // Dash special characters
    .replace(/[^a-z0-9]/g, '-')
 
    // Compress multiple dash
    .replace(/-+/g, '-')
 
    // Trim dashes
    .replace(/^-|-$/g, '');
};

var slug = function (string) {
// var accents = "àáäâèéëêìíïîòóöôùúüûñç";
var accents = "u00e0u00e1u00e4u00e2u00e8"
+ "u00e9u00ebu00eau00ecu00edu00ef"
+ "u00eeu00f2u00f3u00f6u00f4u00f9"
+ "u00fau00fcu00fbu00f1u00e7";

var without = "aaaaeeeeiiiioooouuuunc";

var map = {‘@’: ‘ at ‘, ‘u20ac’: ‘ euro ‘,
‘$’: ‘ dollar ‘, ‘u00a5’: ‘ yen ‘,
‘u0026’: ‘ and ‘, ‘u00e6’: ‘ae’, ‘u0153’: ‘oe’};

return string
// Handle uppercase characters
.toLowerCase()

// Handle accentuated characters
.replace(
new RegExp(‘[‘ + accents + ‘]’, ‘g’),
function (c) { return without.charAt(accents.indexOf(c)); })

// Handle special characters
.replace(
new RegExp(‘[‘ + keys(map).join(”) + ‘]’, ‘g’),
function (c) { return map[c]; })

// Dash special characters
.replace(/[^a-z0-9]/g, ‘-‘)

// Compress multiple dash
.replace(/-+/g, ‘-‘)

// Trim dashes
.replace(/^-|-$/g, ”);
};

Bonus

If you are bored, here is a little exercise for you. Can you find a and b such as

a >= b && a < = b
// true
 
a == b
// false

a == b
// false

Javascript – Ajax Binary Reader

BinaryReader is buggy and no longer maintained. Check out jDataView for an up to date version.

With WebGL coming in, it is important to be able to deal with binary data files like the models. Since there is no such thing on the internet right now I decided to make my own. The javascript BinaryReader library tries to mimic the C# BinaryReader.

The code is mostly based on the binary-parser class from Jonas Raoni Soares Silva. I’ve added the position management and re-factored the code to remove the with syntax.

In order to load a file into a string, you have to add req.overrideMimeType('text/plain; charset=x-user-defined'); in the Ajax XMLHttpRequest. To read more about this technique, see the Mozilla Developer Center. Here is an overview of the compatible browsers.

  • Chrome 4.0.295.0: Works
  • Firefox 3.5.7: Works
  • Safari 4.0.4: Works
  • Internet Explorer 8: Does not work. Doesn’t have the overrideMimeType method.
  • Opera 10.10: Does not work. Have the overrideMimeType method but doesn’t take it in account.

I hope this will help you to parse binary files!

BinaryReader is buggy and no longer maintained. Check out jDataView for an up to date version.

Download

API

Constructor

  • new BinaryReader(data: String) – Create a BinaryReader with the specified file.

Read Methods

  • BinaryReader.readChar()
  • BinaryReader.readString(length: Number)
  • BinaryReader.readInt8()
  • BinaryReader.readUInt8()
  • BinaryReader.readInt16()
  • BinaryReader.readUInt16()
  • BinaryReader.readInt32()
  • BinaryReader.readUInt32()
  • BinaryReader.readUInt32()
  • BinaryReader.readFloat()
  • BinaryReader.readDouble()

Position Methods

  • BinaryReader.seek(pos: Number) – Go to a specific position (in Byte) in the file
  • BinaryReader.getPosition() – Returns the actual position (in Byte) in the file
  • BinaryReader.getSize() – Returns the size (in Byte) of the file

Exception

  • Error(“Index out of bound”) – When you try to read something that is beyond the end of the file.
BinaryReader is buggy and no longer maintained. Check out jDataView for an up to date version.

Example – Demo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// Code from https://developer.mozilla.org/En/Using_XMLHttpRequest#Receiving_binary_data
function load_binary_resource(url) {
	var req = new XMLHttpRequest();
	req.open('GET', url, false);
	// The following line says we want to receive data as Binary and not as Unicode
	req.overrideMimeType('text/plain; charset=x-user-defined');
	req.send(null);
	if (req.status != 200) return '';
	return req.responseText;
}
 
// Load the file
var file = load_binary_resource('author.gif');
 
// Create the Binary Reader
var reader = new BinaryReader(file);
 
// Read some informations
var tag		= reader.readString(6);
var width	= reader.readUInt16();
var height	= reader.readUInt16();
 
// Move around the file and try to read what is there
reader.seek(parseInt('FA', 16));
var random	= reader.readFloat();
 
console.log(
	tag,	// GIF89a
	width,	// 16
	height,	// 16
	random	// 66.01171875
);

// Load the file
var file = load_binary_resource(‘author.gif’);

// Create the Binary Reader
var reader = new BinaryReader(file);

// Read some informations
var tag = reader.readString(6);
var width = reader.readUInt16();
var height = reader.readUInt16();

// Move around the file and try to read what is there
reader.seek(parseInt(‘FA’, 16));
var random = reader.readFloat();

console.log(
tag, // GIF89a
width, // 16
height, // 16
random // 66.01171875
);

Existing Dispatch Methods

Dispatch is the process of mapping a function call to a specific function based on its arguments. Most of the time this is done at runtime through the binding phase, however it usually lacks of modularity.

Dispatch by Type

The first way dispatch has been implemented is through function overloading. Two functions share the same name and depending on the type of the argument, a choice will be made to call the right one.

int   sqr(int i)   { return i * i; } // int version
float sqr(float i) { return i * i; } // float version

When entering the Oriented Object world, there is a more powerful way to dispatch that is not only based on the type but also the type hierarchy. You can allow an object of type A to use the method implementation of one of its children.

class A { public: virtual void print() = 0; };
 
class B : public A { public: void print() { std::cout < < "B" << std::endl; }; };
class C : public A { public: void print() { std::cout < < "C" << std::endl; }; };
 
void doPrint(A& a) {
  // A doesn't have a definition of the print method
  // There is an implicit dispatching to determine which of the B::print or C::print 
  // will be called. This is done at runtime
  a.print();
}

class B : public A { public: void print() { std::cout < < "B" << std::endl; }; };
class C : public A { public: void print() { std::cout < < "C" << std::endl; }; };

void doPrint(A& a) {
// A doesn’t have a definition of the print method
// There is an implicit dispatching to determine which of the B::print or C::print
// will be called. This is done at runtime
a.print();
}

This is a single dispatch since we could see the print function this way: void print(B this) { ... }. In C++ we are limited to only one dispatch, even if Stroustrup proposed a way to support multimethods in C++. The main problem is that it’s being limited to types.

Dispatch by Constant Value

There are ways to use other criteria in order to dispatch, for example the use of numerical constants. In C++ the way to do it is to use templates.

// General case
template < int N >
struct fact {
  enum { value = N * fact< N - 1 >::value };
};
 
// Specialization for n = 0
template <>
struct fact< 0 > {
  enum { value = 1 };
};

// Specialization for n = 0
template <>
struct fact< 0 > {
enum { value = 1 };
};

You have a code that will run differently depending on the parameter. We can now write functions that work for specialized types and that takes in account their type hierarchy and for specialized cases represented with numerical constants.

If you want to do fancier things, you are stuck! Your only way to achieve the result you expect is to write custom branching yourself. This is where Full dispatch comes in action.

Full Dispatch

Full Dispatch instead of redirecting to the right function based on hard-coded parameters such as the type or the equality of the argument with some constant, allows you to provide a function for each argument.

This way, you will be able to dispatch the function based on the criterion you want. You are no more stuck with a special subset of the language.

You would like to write something like this:

int fact(int n : n == 0 || n == 1) { return 1; }
int fact(int n) { return n * fact(n - 1); }

Implementation

To dispatch, we have to know two informations for each overriding method: the actual function and a list of boolean function to test against the parameters.

I’ve chosen to store it as an array of overriding method, where the overriding is stored as an array containing in first element the actual function followed by the argument conditions.

The dispatching function is trivial to write, you just have to walk through that table and if all the arguments match the conditions then call it.

function fullDispatch(arg, list) {
  outer: for (var i = 0; i < list.length; ++i) {
    if (list[i].length - 1 !== arg.length) {
      // Arguments length is different than number of conditions, no need to continue
      continue;
    }
 
    for (var j = 0; j < arg.length; ++j) {
      if (typeof list[i][j + 1] === 'function' && !list[i][j + 1](arg[j])) {
        // Condition fail, try next overriding function
        continue outer;
      }
    }
    // Execute the right function
    return list[i][0].apply(this, arg);
  }
  output.error('no dispatch found');
}

for (var j = 0; j < arg.length; ++j) {
if (typeof list[i][j + 1] === ‘function’ && !list[i][j + 1](arg[j])) {
// Condition fail, try next overriding function
continue outer;
}
}
// Execute the right function
return list[i][0].apply(this, arg);
}
output.error(‘no dispatch found’);
}

And here is the code to use it for the factorial function:

var fact = function () {
  return fullDispatch(arguments, fact.list);
}
 
fact.list = [
  [function (n) { return 1; },
    function (n) { return n === 0 || n === 1; }],
 
  [function (n) { return n * fact(n - 1); },
    null]
];

fact.list = [
[function (n) { return 1; },
function (n) { return n === 0 || n === 1; }],

[function (n) { return n * fact(n – 1); },
null]
];

Helper functions

Most of the time, the condition functions will be trivial to write and will make the code unreadable because of the verbose way to declare an anonymous function.

The first step to make this cleaner was to allow null to be used when you don’t want to impose any condition on the argument. It means “always return yes” and avoid a useless function call.

Then, we want to avoid to write basic conditions such as “is zero” or “is negative”. Using the power of lambda function in association with closure, it’s possible to write generics helpers to make these with no effort.

var helper = {};
 
// Combination
helper.or = function (f, g) { return function (x) { return f(x) || g(x); }; };
helper.and = function (f, g) { return function (x) { return f(x) && g(x); }; };
helper.not = function (f) { return function (x) { return !f(x); }; };
 
// Primitives
helper.Value = function (n) { return function (x) { return x === n; }; };
helper.StrictNegative = function (x) { return x < 0; };
 
// Primitive Combinations
helper.Zero = helper.Value(0);
helper.Negative = helper.or(helper.StrictNegative, helper.Zero);
helper.StrictPositive = helper.not(helper.or(helper.Zero, helper.StrictNegative));
helper.Positive = helper.not(helper.StrictNegative);

// Combination
helper.or = function (f, g) { return function (x) { return f(x) || g(x); }; };
helper.and = function (f, g) { return function (x) { return f(x) && g(x); }; };
helper.not = function (f) { return function (x) { return !f(x); }; };

// Primitives
helper.Value = function (n) { return function (x) { return x === n; }; };
helper.StrictNegative = function (x) { return x < 0; };

// Primitive Combinations
helper.Zero = helper.Value(0);
helper.Negative = helper.or(helper.StrictNegative, helper.Zero);
helper.StrictPositive = helper.not(helper.or(helper.Zero, helper.StrictNegative));
helper.Positive = helper.not(helper.StrictNegative);

Of course, the shown primitive combinations could be written directly but this shows you how to construct and use complex functions based on few bricks.

Final Result

This is an example of the ackermann function written with the Full Dispatch method and the little helper functions.

var ackermann = function () {
  return fullDispatch(arguments, ackermann.list);
}
 
ackermann.list = [
  [function (m, n) { return n + 1; },
    helper.Zero,
    null],
 
  [function (m, n) { return ackermann(m - 1, 1); },
    helper.StrictPositive,
    helper.Zero],
 
  [function (m, n) { return ackermann(m - 1, ackermann(m, n - 1)); },
    helper.StrictPositive,
    helper.StrictPositive]
];

ackermann.list = [
[function (m, n) { return n + 1; },
helper.Zero,
null],

[function (m, n) { return ackermann(m – 1, 1); },
helper.StrictPositive,
helper.Zero],

[function (m, n) { return ackermann(m – 1, ackermann(m, n – 1)); },
helper.StrictPositive,
helper.StrictPositive]
];

Write Less, Do More

The current version works well but is the syntax is too heavy. In order to make this work we have to copy each time the fullDispatch call which isn’t good. We can use a function generator to do the work.

We want to put the conditions first, since they will tend to be smaller, they will appear nicely in one line just before the function definition. And having a setter could be interesting, this would allow to check the input and hide the structure from the user.

Applying these modifications, we would have a code that look like this:

var ack = FullDispatch();
 
ack.add([Zero, null], function (m, n) { return n + 1; });
ack.add([StrictPositive, Zero], function (m, n) { return ack(m - 1, 1); });
ack.add([StrictPositive, StrictPositive], function (m, n) { return ack(m - 1, ack(m, n - 1)); });
ack.add([null, null], function (m, n) { return 0; });

ack.add([Zero, null], function (m, n) { return n + 1; });
ack.add([StrictPositive, Zero], function (m, n) { return ack(m – 1, 1); });
ack.add([StrictPositive, StrictPositive], function (m, n) { return ack(m – 1, ack(m, n – 1)); });
ack.add([null, null], function (m, n) { return 0; });

Which is a pretty nice result. This is not as short as the haskell code but this doesn’t use any syntaxic sugar from the language and can be used with any kind of argument conditions.

ackermann 0 n = n+1 
ackermann (m+1) 0 = ackermann m 1
ackermann (m+1) (n+1) = ackermann m (ackermann (m+1) n)
ackermann _ _ = 0

To make this work we create a function that is going to to the real dispatch and augment it with the setter and the function list.

var FullDispatch = function () {
  // Create the function that does the real dispatch
  var object = function () {
    return fullDispatch(arguments, object.list);
  };
 
  // Give the setter to the function
  object.add = function (conds, func) {
    object.list.push([func].concat(conds))
  }
 
  // Initialize the function list
  object.list = [];
 
  return object;
};

// Give the setter to the function
object.add = function (conds, func) {
object.list.push([func].concat(conds))
}

// Initialize the function list
object.list = [];

return object;
};

Demo

The code demonstrated here can been seen working in a demo.

Follow-Up

This little library is working well as it is. There is still some work to do in this field. First, we have to find uses for this pattern. I haven’t thought yet of any uses of it and the example provided do not show the real benefit of such a tool. I am pretty sure now this is known and implemented some of you will find how to use it!

The second point is performance issues. Having such a modular dispatch system is great for expressiveness but come at a price. The overhead is pretty huge. One dispatch of a call costs at most n * m where n is the number of overriding functions and m is the number of arguments.

Functions can be added a way that only one (or two) conditions are tested each time. By mimicking the way you would write a branching using if-then-else, the overhead is one function call per condition (and per argument).

It’s certainly enough to avoid when performance is required, however I am confident this is acceptable in most conditions compared to the flexibility it gives. Benchmarks would be more than welcome.

Javascript – Sorting Table

For my new project on World of Raids I have to implement a table sorting. The browser not stable sorting and the faster sorting trick add difficulty to the task.

String Comparison

As mentionned in the Speed Up Javascript Sort() article, using a string as a key to represent each element is faster than using a custom sort function in most browsers.

Tables are commonly made of two data types: Numbers and Strings. Strings are the final representation so no work is involved there so our work will be focused on Numbers. What we want is to fit a number into a string. A string is a succession of characters, each one able to hold 256 values. So, we can see the problem as encoding the number into a base 256 which is trivial.

Padding

String comparison does not work exactly like we want it. It reads all the characters one by one and if they mismatch then it returns who is the highest. So for example "10" < "5" because '1' < '5'. We have to pad every numbers with 0 at the beginning and become "10" > "05".

In this case we are adding one 0 because 10 is 2 digits and 5 is only one. We won’t know the values of other elements when making a comparison, so two solutions apply: either we iterate over all the elements and retrieve the highest, or we set an arbitrary maximum.

Characters Maximum
1 256
2 65 536
3 16 777 216
4 4 294 967 296

With that table in mind, it is obvious that it would be a waste of time to inspect every element just to find the highest value. 1 or 2 characters will probably fit most uses but if you want to be safe, you will always be able to store your number into 4 characters which is acceptable.

Here is the code to do the conversion:

function compareAsc(num, digits) {
  var s = "";
  // Encode num in base 256
  while (num !== 0) {
    s = String.fromCharCode((num % 256) | 0) + s;
    num = (num / 256) | 0;
    digits -= 1;
  }
  // Fill with 0
  while (digits > 0) {
    s = String.fromCharCode(0) + s;
    digits -= 1;
  }
  return s;
}

For the sake of simplicity, this code is using string concatenation which requires to build up new strings and make copy several times. Since this is for small strings (up to 4 characters!) this is probably alright but one looking for performances could bench this with the use of an Array with a .concat() at the end to build the string.

Also note that numbers are stored as float in Javascript, so we are rounding (flooring to be exact) all the values using the |0 trick.

Descending Order

We have made the code for an ascending sort but we have to handle the other case. We cannot just revert the order of the sorting or adding a minus sign before the number. What we have to do is to do a 256-complement of the final result, in other terms: digit = 255 – digit. Let see an example for a base 10.

00 -> 99
01 -> 98
...
54 -> 45
55 -> 44
56 -> 43
...
98 -> 01
99 -> 00

You can see that all the numbers are now sorted in the opposite order.

Here is the associated code :

function compareDesc(num, digits) {
  var s = "";
  // Encode num in base 256 and do the 256-complement
  while (num !== 0) {
    s = String.fromCharCode(255 - (num % 256) | 0) + s;
    num = (num / 256) | 0;
    digits -= 1;
  }
  while (digits >= 0) {
    s = String.fromCharCode(255) + s;
    digits -= 1;
  }
  return s;
}

Floats and Negatives

We have handled all the positive integers but they are not alone. In order to deal with the negative numbers you can apply the 2-complement to the number. This is how it is done in computer arithmetic.

To handle floats, it is possible to treat them as integers by multiplying by 10^(number of decimal displayed). So 12.34 is translated to 1234 and 11 to 1100 and it’s working just fine. You will probably need more than 4 characters if you are using huge numbers though.

Stable Sorting

Implementing a table sorting requires the sorting algorithm to be stable (values that have the same key keep their original order). This property allows people to sort by multiple columns, the last one having the highest weight.

However, browser implementations of the Array.sort() are not stable. From there we have two solutions, implementing a stable sort in javascript or find a way to emulate that behaviour. Since Javascript is slow in many browsers, implementing such a computation heavy algorithm in Javascript is going to slow down things and requires more efforts than I am willing to spend on this project.

The solution instead is to understand what the stable property means and find a way to code it.

Stable sorting algorithms maintain the relative order of records with equal keys. […] Whenever there are two records (let’s say R and S) with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list.

We can easily transpose that sentence into the sorting function:

if (R.key == S.key)
  return compare(R.position, S.position)

We need to know one more thing to do the computation: the position of each element in the list before sorting. This is straightforward to do, you have to iterate over all the elements and update their position field. This requires n steps which is acceptable.

Here is the full Javascript code

var sort = function (a, b) {
  if (a.key === b.key)
    return a.position - b.position;
  if (a.key < b.key)
    return -1;
  return 1;
};

String comparison

To apply this concept to the string comparison, you can append the position at the end of the string. "Key" now being "Key1", "Key2" and so on. When the keys are equal, the position is used for the comparison instead. We can reuse the compareAsc() function to encode the position using the minimal size.

This works well for fixed-size strings like the representation of numbers. However common strings do not share that property and a problem arise when two strings share a common base.

Take “Method” and “Methodology”. It is obvious that "Method" < "Methodology". Now append the position: "Method" + chr(250) > "Methodology" + chr(251) the comparison changed because chr(250) > 'o'. (Where chr = String.fromCharCode').

The way to fix this problem is to add a chr(0) before the position. Considering that a normal string never contains a chr(0), the chr(0) will always be lesser than any character of the string and therefore stop the comparison. The longer string always wins!