Follow @nxtchg

Author Topic: Simplifying Int64 polyfill  (Read 486 times)


  • Overlord
  • *****
  • Posts: 1115
  • Respect: +61
    • View Profile
Simplifying Int64 polyfill
« on: June 28, 2017, 07:47:26 am »
While porting Ed25519 to JS we discovered that in a few places the normal 53-bit lossless arithmetic supported by native JS floats is not enough and we need int64.

So I took this polyfill: and simplified it quite a bit: from 24 Kb to 6.

First, I merged both Int64 and Uint64 into a single data type, because signedness is not the issue of storage (under the hood everything is stored as 2's-complement anyway), but the issue of operations.

For example, when you do a right shift, you need to specify whether you want your sign bit extended or not.

Unsigned data types have relatively limited use anyway, so it makes sense to be signed by default.

Merging the two types allowed to merge "base-class" functions with type-specific ones. For example, in the original there is uadd() base function and add() in each sub-type.

Dealing with signedness at the level of operations also allowed to merge functions together and share a lot of code:

Code: [Select]
Int64.prototype.cmp = function(v, unsign)
var a = (unsign ? this.hi >>> 0 : this.hi | 0);
var b = (unsign ?    v.hi >>> 0 :    v.hi | 0);

if(a < b) return -1;
if(a > b) return +1;

if(this.lo < v.lo) return -1;
if(this.lo > v.lo) return +1;

return 0;

Next, throwing exceptions in each function like this:

Code: [Select]
if(!(a instanceof Uint64)) throw TypeError(a + ' is not an Uint64');

is stupid. Most of the time you want to mix Int64 with regular numbers and it will fall on its face each time!

It's much better to convert numbers into Int64 first:

Code: [Select]
if(!(v instanceof Int64)) v = new Int64(v);

If you want to be extra paranoid, you can then check 'v' type at a single point - in the constructor.

Next, when you build a class like this, you need to decide whether it should be immutable (like JS strings) or not.

Being immutable is convenient:

Code: [Select]
c = a.add(b);

Indeed the original is built this way.

But it leaves you no way to opt-out! You cannot now perform operations in-place, which for Int64 makes a lot of sense.

And if you do something like this:

Code: [Select]
e = a.add(b).mul(c).shl(d);

you clone the object 3 times and this can affect performance.

So I decided to do all operations in-place. This returns the choice of when to copy back to the user:

Code: [Select]

The rest of simplifications were mostly just more sensible naming. Who the hell names the shift function shiftRightLogical()?! shr() is no good for you?!


But of course the committee in charge of that particular API would never agree to 'shr'! It just doesn't sound too important.

Somehow add() is ok, but shr() - oh, noes!

Well, anyway, now we have a nice Int64 class to use in any JS project: and Ed25519 porting is 75% complete.
Tentacle Overlord, The Deranged Genius of The Abyss