Last active
May 30, 2017 13:32
-
-
Save emilbayes/5842ebfa6e00779c8486 to your computer and use it in GitHub Desktop.
"64-bit" add
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
'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; | |
} | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
thanks!