gistfile1.md

From Fabrice Bellard, with minor name change (umulh):

// return the high 32 bit part of the 64 bit addition of (hi0, lo0) and (hi1, lo1)
Math.iaddh(lo0, hi0, lo1, hi1)

// return the high 32 bit part of the 64 bit subtraction of (hi0, lo0) and (hi1, lo1)
Math.isubh(lo0, hi0, lo1, hi1)

// return the high 32 bit part of the signed 64 bit product of the 32 bit numbers a and b
Math.imulh(a, b)

// return the high 32 bit part of the unsigned 64 bit product of the 32 bit numbers a and b
Math.umulh(a, b)

All these functions convert their argument to 32 bit integers. They return a signed 32 bit integer.

With these functions, the 64 bit operations are easy to implement :

// (hi_res, lo_res) = (hi0, lo0) + (hi1, lo1) (64 bit addition):

lo_res = (lo0 + lo1) | 0;
hi_res = Math.iaddh(lo0, hi0, lo1, hi1);

// (hi_res, lo_res) = (hi0, lo0) - (hi1, lo1) (64 bit subtraction):

lo_res = (lo0 - lo1) | 0;
hi_res = Math.isubh(lo0, hi0, lo1, hi1);

// (hi_res, lo_res) = a * b (signed 64 bit product of 32 bit integers):

lo_res = Math.imul(a, b);
hi_res = Math.imulh(a, b);

// (hi_res, lo_res) = a * b (unsigned 64 bit product of 32 bit integers):

lo_res = Math.imul(a, b);
hi_res = Math.umulh(a, b);

// (hi_res, lo_res) = (hi0, lo0) * (hi1, lo1) (signed 64 bit product of 64 bit integers):

lo_res = Math.imul(lo0, lo1);
hi_res = (Math.imulh(lo0, lo1) + Math.imul(lo0, hi1)) | 0;
hi_res = (hi_res + Math.imul(lo1, hi0)) | 0;

// (hi_res, lo_res) = (hi0, lo0) * (hi1, lo1) (unsigned 64 bit product of 64 bit integers):

lo_res = Math.imul(lo0, lo1);
hi_res = (Math.umulh(lo0, lo1) + Math.imul(lo0, hi1)) | 0;
hi_res = (hi_res + Math.imul(lo1, hi0)) | 0;

Fabrice wrote:

"It is easy for the compiler to optimize the code because only 32 bit integers are used and because the functions have no side effect. Even if the compiler does not remove the duplicate operation for the low 32 bit parts, the overhead is very small on a 32 bit CPU (1 more instruction than the optimal code)."

UPDATE to provide 64x64=64 functions:

// (hi_res, lo_res) = (hi0, lo0) * (hi1, lo1) (signed 64 bit product of 64 bit integers):

lo_res = Math.imul(lo0, lo1);
hi_res = Math.imulx(lo0, hi0, lo1, hi1);

// (hi_res, lo_res) = (hi0, lo0) * (hi1, lo1) (unsigned 64 bit product of 64 bit integers):

lo_res = Math.imul(lo0, lo1);
hi_res = Math.umulx(lo0, hi0, lo1, hi1);

The x suffix is straw, it could be hx to connote hi_res is the result, or something longer.

/be

While these imulh and umulh are pretty ordinary, these iaddh and isubh were a little surprising to me. I expected Math.iaddh and Math.isubh to have two arguments and return 0 or 1, holding the carry value, similar to how imulh and umulh work.

In this way, 64-bit add would be:

lo_res = (lo0 + lo1) | 0;
hi_res = hi0 + hi1 + Math.iaddh(lo0, lo1) | 0;

However, if you're thinking that JITs are going to want to pattern-match the whole thing to actual 64-bit arithmetic, this would make more work for them. But in that case, perhaps we should instead go the other way and make Math.imulh and Math.umulh take 4 inputs too. This would make the 32x32=64 case less nice, but it'd make the 64x64=64 case use less code, and that's the more common case for e.g. Emscripten.

(I'm leaving aside the concern of using carry flags to implement big-integer math here :-)).

Good point. Perhaps the best of all worlds proposal would provide Math.imulx and Math.umulx in addition, for 64x64=64 arithmetic with user and JIT convenience. I'll update the gist to sketch these.

From [bn.js][https://github.com/indutny/bn.js] point of view I could only say that it'll simplify code a lot if we would have explicit carry bit information. Otherwise looking great to me!

Boy this is great news! Couple of questions:

• Will typed arrays include Int/Uint64 arrays/views?
• Wasn't there a "bignum" TC39 proposal that might be more general?
• Why "little endian" .. i.e. lo, hi pairs? Wouldn't hi, lo pairs be more natural? Maybe natural imul extension?
  Next we'll solve 0.1 + 0.2 = 0.30000000000000004!

@backspaces, this is the minimum viable 64-bit kernel semantics for polyfills and Emscripten, no more. It helps for building bignums, but Int64Array and so on want the real int64/uint64 pair, also coming but behind this MV64bKS :-P.

Why little-endian? Good q, as you can see from the edit history I used hi, lo parameter order at first for the updated [iu]mulx methods, then changed to match Fabrice Bellard's order. I suspect LE is ingrained in his fingers and brain due to x86. My old BE habits from the IP protocols, 68K, MIPS have faded. I'm agnostic. Anyone have a compelling reason for (lo, hi) or (hi, lo) pair-component order?

/be

I don't think it matter when you are dealing with named parameters and for the vast majority of developers who aren't asm hackers hi-lo probably will make more sense.

If you were actually dealing with 32-bit values, lo-hi might enable some memory layout trickery on little-endian machines (or the opposite for big-endians). But since the 32-bits values are encapsulated by a float64 that all seems unlikely.

Pretty much suggests to me that hi-lo is the way to go for parameters.

Happy to go with (hi, lo) throughout. Waiting till next week for more feedback.

/be

+1 for carry bits. Regarding endianness, I'd be ok with using whatever the underlying architecture supports, or barring that default to x86-64 (little endian).

For calling conventions, I'd favor (lo,hi) but am relatively ambivalent (I have no concrete reason to prefer this, it is just a gut feeling).

(Updated comment)

I'm happy with LE (lo-hi). I mean this is the way I do it in bn.js at the moment, and it will be more consistent for the most of the bignum-in-vanilla-js developers.

Does this offer any advantage operating on values known to be between 2^32 and 2^53 vs using basic multiply and division? e.g. for unsigned operations:

let lo = num >>> 0;
let hi = (num / 0x100000000) >>> 0;
// and
num = (hi * 0x100000000) + lo;

@trevnorris hell yes :) We currently can do only 26bit * 26bit, and it does work through conversion to floating point and back from it.

Additional point, to store 256bit secp256k1 keys elliptic is using ten 26bit limbs. With this patch it'll be just 8. Considering that multiplication is O(n^2) it might give up to 56% improvement on bn.js multiplication, taking in account additional 20% boost from not using floating point it is almost 2x boost!

@trevnorris: division when you can strength-reduce by right-shifting is best done by shifting, but that only works for 32 bits. Bigger dividends want specific hard-coded solutions for div-by-power-of-2. Anything general wants Newton-Raphson or better, in library code.

/be

@BrendanEich Hm. I missed that the API in your gist is only for math operations. My example was to turn an existing value into the hi and low 32 bits.

So say someone has a value within (2^32, 2^53] and wants to turn it into the hi and low 32 bit range. Is there a proposed API to perform that operation?

@trevnorris, sorry, I know you asked @BrendanEich about it, but I'd like to reply anyway.

I think this API mostly applies to the (2^32, 2^32) ( lo+hi ) pairs. You could just store number in this format, as I'm planning to do in bn.js, or you could as well convert 2^53 floating point number to it using division and binary &. I don't think that there is a big value in introducing new API methods, considering that they'll convert FP number to 64bit pair in the quite similar way internally.

As noted on twitter, see also https://github.com/dherman/float.js for cracking JS 64-bit doubles via typed arrays and their aliasing powers.

/be

I'm finding the naming of these functions pretty confusing. Are they acronyms?

They're abbreviated: imulh is short for "integer, multiply, high bits". It's consistent with the naming of functions like Math.imul.

I also suggest add Math.popcnt Math.popcnt64 support

https://msdn.microsoft.com/zh-cn/library/bb385231.aspx

Maybe also Math.popcnt16 support

Pardon my ignorance, but instead of these specific functions, wouldn't it be great to have custom types work with normal operators? I always thought that JS might benefit from more custom-ish types like matrixes and simply have them work with +-/*<>... operators instead of creating whole new objects/methods like Math.iaddh and SIMD.%type%.mul()

@BrendanEich is this proposal alive or I should remove it from the next version of core-js? -)