Skip to content

Instantly share code, notes, and snippets.

@emilbayes
Last active May 30, 2017 13:32
Show Gist options
  • Save emilbayes/5842ebfa6e00779c8486 to your computer and use it in GitHub Desktop.
Save emilbayes/5842ebfa6e00779c8486 to your computer and use it in GitHub Desktop.
"64-bit" add
'use strict';
/**
* "64-bit" means unsinged 64-bit integer, contained in Uint32Array(2) in
* Big Endian order
*/
module.exports = {
//Arithmetic
/**
* Add two "64-bit" uintegers leveraging the fact that floating points arithmetic
* is integer safe up to 2^53 - 1.
* @param {Uint32Array} s1 "64-bit" uinteger
* @param {Uint32Array} s2 "64-bit" uinteger
* @param {Uint32Array} dest "64-bit" uinteger to write result to
* @return {Uint32Array} dest
*/
add: function(s1, s2, dest) {
//Add lower bits as we'll use this twice
var lowerSum = s1[1] + s2[1];
//Add higher bits and carry-over from lower. The carry-over is calculated
// as follows:
//
// * Leverage the fact that floating point arithmetic is integer safe up
// to 2^25 - 1.
// * The carry over will be the 33rd bit, however bit operations are only
// 32-bit in Javascript.
// * `num >>> 1 === Math.floor(num / 2)` which means that we can shift down
// a 64-bit, integer safe, floating point while preserving the highest bit.
// * This high bit will now be the carry-over.
//
//So now we can calculate the sum of the higher bits, and add the carry-over
//from the lower bits
dest[0] = s1[0] + s2[0] + (lowerSum / 2 >>> 31);
//Mask the lower sum as to avoid overflow
dest[1] = lowerSum & 0xFFFFFFFF;
return dest;
},
//Bitwise
/**
* XOR two "64-bit" uinteger, mutating `dest`
* @param {Uint32Array} s1 "64-bit" uinteger
* @param {Uint32Array} s2 "64-bit" uinteger
* @param {Uint32Array} dest "64-bit" uinteger to write result to
* @return {Uint32Array} dest
*/
xor: function(s1, s2, dest) {
//XOR is component independent
dest[0] = s1[0] ^ s2[0];
dest[1] = s1[1] ^ s2[1];
return dest;
},
/**
* Right shift a "64-bit" uinteger, mutating `dest`
* Also known as Zero-fill right shift
* @param {Uint32Array} s "64-bit" uinteger
* @param {Number} n Right shift by n, range [0, 31]
* @param {Uint32Array} dest "64-bit" uinteger to write result to
* @return {Uint32Array} dest
*/
rightShift: function(s, n, dest) {
//Create mask for the n lowest bits
var mask = 0xFFFFFFFF >>> (32 - n);
//Right shift lower bits and prepend left shifted bits from higher bits
dest[1] = (s[1] >>> n) | ((s[0] & mask) << (32 - n));
//Right shift higher bits
dest[0] = s[0] >>> n;
return dest;
},
/**
* Left shift a "64-bit" uinteger, mutating `dest`
* @param {Uint32Array} s "64-bit" uinteger
* @param {Number} n Left shift by n, range [0, 31]
* @param {Uint32Array} dest "64-bit" uinteger to write result to
* @return {Uint32Array} dest
*/
leftShift: function(s, n, dest) {
//Create a mask for the n highst bits
var mask = 0xFFFFFFFF << (32 - n);
//Left shift higher bits and append left shifted bits from lower bits
dest[0] = (s[0] << n) | ((s[1] & mask) >>> (32 - n));
//Left shift lower bits
dest[1] = s[1] << n;
return dest;
}
};
@emilbayes
Copy link
Author

thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment