diff options
Diffstat (limited to 'js/binary/arith.js')
-rw-r--r-- | js/binary/arith.js | 413 |
1 files changed, 413 insertions, 0 deletions
diff --git a/js/binary/arith.js b/js/binary/arith.js new file mode 100644 index 00000000..70257de7 --- /dev/null +++ b/js/binary/arith.js @@ -0,0 +1,413 @@ +// Protocol Buffers - Google's data interchange format +// Copyright 2008 Google Inc. All rights reserved. +// https://developers.google.com/protocol-buffers/ +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +/** + * @fileoverview This file contains helper code used by jspb.utils to + * handle 64-bit integer conversion to/from strings. + * + * @author cfallin@google.com (Chris Fallin) + * + * TODO(haberman): move this to javascript/closure/math? + */ + +goog.provide('jspb.arith.Int64'); +goog.provide('jspb.arith.UInt64'); + +/** + * UInt64 implements some 64-bit arithmetic routines necessary for properly + * handling 64-bit integer fields. It implements lossless integer arithmetic on + * top of JavaScript's number type, which has only 53 bits of precision, by + * representing 64-bit integers as two 32-bit halves. + * + * @param {number} lo The low 32 bits. + * @param {number} hi The high 32 bits. + * @constructor + */ +jspb.arith.UInt64 = function(lo, hi) { + /** + * The low 32 bits. + * @public {number} + */ + this.lo = lo; + /** + * The high 32 bits. + * @public {number} + */ + this.hi = hi; +}; + + +/** + * Compare two 64-bit numbers. Returns -1 if the first is + * less, +1 if the first is greater, or 0 if both are equal. + * @param {!jspb.arith.UInt64} other + * @return {number} + */ +jspb.arith.UInt64.prototype.cmp = function(other) { + if (this.hi < other.hi || (this.hi == other.hi && this.lo < other.lo)) { + return -1; + } else if (this.hi == other.hi && this.lo == other.lo) { + return 0; + } else { + return 1; + } +}; + + +/** + * Right-shift this number by one bit. + * @return {!jspb.arith.UInt64} + */ +jspb.arith.UInt64.prototype.rightShift = function() { + var hi = this.hi >>> 1; + var lo = (this.lo >>> 1) | ((this.hi & 1) << 31); + return new jspb.arith.UInt64(lo >>> 0, hi >>> 0); +}; + + +/** + * Left-shift this number by one bit. + * @return {!jspb.arith.UInt64} + */ +jspb.arith.UInt64.prototype.leftShift = function() { + var lo = this.lo << 1; + var hi = (this.hi << 1) | (this.lo >>> 31); + return new jspb.arith.UInt64(lo >>> 0, hi >>> 0); +}; + + +/** + * Test the MSB. + * @return {boolean} + */ +jspb.arith.UInt64.prototype.msb = function() { + return !!(this.hi & 0x80000000); +}; + + +/** + * Test the LSB. + * @return {boolean} + */ +jspb.arith.UInt64.prototype.lsb = function() { + return !!(this.lo & 1); +}; + + +/** + * Test whether this number is zero. + * @return {boolean} + */ +jspb.arith.UInt64.prototype.zero = function() { + return this.lo == 0 && this.hi == 0; +}; + + +/** + * Add two 64-bit numbers to produce a 64-bit number. + * @param {!jspb.arith.UInt64} other + * @return {!jspb.arith.UInt64} + */ +jspb.arith.UInt64.prototype.add = function(other) { + var lo = ((this.lo + other.lo) & 0xffffffff) >>> 0; + var hi = + (((this.hi + other.hi) & 0xffffffff) >>> 0) + + (((this.lo + other.lo) >= 0x100000000) ? 1 : 0); + return new jspb.arith.UInt64(lo >>> 0, hi >>> 0); +}; + + +/** + * Subtract two 64-bit numbers to produce a 64-bit number. + * @param {!jspb.arith.UInt64} other + * @return {!jspb.arith.UInt64} + */ +jspb.arith.UInt64.prototype.sub = function(other) { + var lo = ((this.lo - other.lo) & 0xffffffff) >>> 0; + var hi = + (((this.hi - other.hi) & 0xffffffff) >>> 0) - + (((this.lo - other.lo) < 0) ? 1 : 0); + return new jspb.arith.UInt64(lo >>> 0, hi >>> 0); +}; + + +/** + * Multiply two 32-bit numbers to produce a 64-bit number. + * @param {number} a The first integer: must be in [0, 2^32-1). + * @param {number} b The second integer: must be in [0, 2^32-1). + * @return {!jspb.arith.UInt64} + */ +jspb.arith.UInt64.mul32x32 = function(a, b) { + // Directly multiplying two 32-bit numbers may produce up to 64 bits of + // precision, thus losing precision because of the 53-bit mantissa of + // JavaScript numbers. So we multiply with 16-bit digits (radix 65536) + // instead. + var aLow = (a & 0xffff); + var aHigh = (a >>> 16); + var bLow = (b & 0xffff); + var bHigh = (b >>> 16); + var productLow = + // 32-bit result, result bits 0-31, take all 32 bits + (aLow * bLow) + + // 32-bit result, result bits 16-47, take bottom 16 as our top 16 + ((aLow * bHigh) & 0xffff) * 0x10000 + + // 32-bit result, result bits 16-47, take bottom 16 as our top 16 + ((aHigh * bLow) & 0xffff) * 0x10000; + var productHigh = + // 32-bit result, result bits 32-63, take all 32 bits + (aHigh * bHigh) + + // 32-bit result, result bits 16-47, take top 16 as our bottom 16 + ((aLow * bHigh) >>> 16) + + // 32-bit result, result bits 16-47, take top 16 as our bottom 16 + ((aHigh * bLow) >>> 16); + + // Carry. Note that we actually have up to *two* carries due to addition of + // three terms. + while (productLow >= 0x100000000) { + productLow -= 0x100000000; + productHigh += 1; + } + + return new jspb.arith.UInt64(productLow >>> 0, productHigh >>> 0); +}; + + +/** + * Multiply this number by a 32-bit number, producing a 96-bit number, then + * truncate the top 32 bits. + * @param {number} a The multiplier. + * @return {!jspb.arith.UInt64} + */ +jspb.arith.UInt64.prototype.mul = function(a) { + // Produce two parts: at bits 0-63, and 32-95. + var lo = jspb.arith.UInt64.mul32x32(this.lo, a); + var hi = jspb.arith.UInt64.mul32x32(this.hi, a); + // Left-shift hi by 32 bits, truncating its top bits. The parts will then be + // aligned for addition. + hi.hi = hi.lo; + hi.lo = 0; + return lo.add(hi); +}; + + +/** + * Divide a 64-bit number by a 32-bit number to produce a + * 64-bit quotient and a 32-bit remainder. + * @param {number} _divisor + * @return {Array.<jspb.arith.UInt64>} array of [quotient, remainder], + * unless divisor is 0, in which case an empty array is returned. + */ +jspb.arith.UInt64.prototype.div = function(_divisor) { + if (_divisor == 0) { + return []; + } + + // We perform long division using a radix-2 algorithm, for simplicity (i.e., + // one bit at a time). TODO: optimize to a radix-2^32 algorithm, taking care + // to get the variable shifts right. + var quotient = new jspb.arith.UInt64(0, 0); + var remainder = new jspb.arith.UInt64(this.lo, this.hi); + var divisor = new jspb.arith.UInt64(_divisor, 0); + var unit = new jspb.arith.UInt64(1, 0); + + // Left-shift the divisor and unit until the high bit of divisor is set. + while (!divisor.msb()) { + divisor = divisor.leftShift(); + unit = unit.leftShift(); + } + + // Perform long division one bit at a time. + while (!unit.zero()) { + // If divisor < remainder, add unit to quotient and subtract divisor from + // remainder. + if (divisor.cmp(remainder) <= 0) { + quotient = quotient.add(unit); + remainder = remainder.sub(divisor); + } + // Right-shift the divisor and unit. + divisor = divisor.rightShift(); + unit = unit.rightShift(); + } + + return [quotient, remainder]; +}; + + +/** + * Convert a 64-bit number to a string. + * @return {string} + * @override + */ +jspb.arith.UInt64.prototype.toString = function() { + var result = ''; + var num = this; + while (!num.zero()) { + var divResult = num.div(10); + var quotient = divResult[0], remainder = divResult[1]; + result = remainder.lo + result; + num = quotient; + } + if (result == '') { + result = '0'; + } + return result; +}; + + +/** + * Parse a string into a 64-bit number. Returns `null` on a parse error. + * @param {string} s + * @return {?jspb.arith.UInt64} + */ +jspb.arith.UInt64.fromString = function(s) { + var result = new jspb.arith.UInt64(0, 0); + // optimization: reuse this instance for each digit. + var digit64 = new jspb.arith.UInt64(0, 0); + for (var i = 0; i < s.length; i++) { + if (s[i] < '0' || s[i] > '9') { + return null; + } + var digit = parseInt(s[i], 10); + digit64.lo = digit; + result = result.mul(10).add(digit64); + } + return result; +}; + + +/** + * Make a copy of the uint64. + * @return {!jspb.arith.UInt64} + */ +jspb.arith.UInt64.prototype.clone = function() { + return new jspb.arith.UInt64(this.lo, this.hi); +}; + + +/** + * Int64 is like UInt64, but modifies string conversions to interpret the stored + * 64-bit value as a twos-complement-signed integer. It does *not* support the + * full range of operations that UInt64 does: only add, subtract, and string + * conversions. + * + * N.B. that multiply and divide routines are *NOT* supported. They will throw + * exceptions. (They are not necessary to implement string conversions, which + * are the only operations we really need in jspb.) + * + * @param {number} lo The low 32 bits. + * @param {number} hi The high 32 bits. + * @constructor + */ +jspb.arith.Int64 = function(lo, hi) { + /** + * The low 32 bits. + * @public {number} + */ + this.lo = lo; + /** + * The high 32 bits. + * @public {number} + */ + this.hi = hi; +}; + + +/** + * Add two 64-bit numbers to produce a 64-bit number. + * @param {!jspb.arith.Int64} other + * @return {!jspb.arith.Int64} + */ +jspb.arith.Int64.prototype.add = function(other) { + var lo = ((this.lo + other.lo) & 0xffffffff) >>> 0; + var hi = + (((this.hi + other.hi) & 0xffffffff) >>> 0) + + (((this.lo + other.lo) >= 0x100000000) ? 1 : 0); + return new jspb.arith.Int64(lo >>> 0, hi >>> 0); +}; + + +/** + * Subtract two 64-bit numbers to produce a 64-bit number. + * @param {!jspb.arith.Int64} other + * @return {!jspb.arith.Int64} + */ +jspb.arith.Int64.prototype.sub = function(other) { + var lo = ((this.lo - other.lo) & 0xffffffff) >>> 0; + var hi = + (((this.hi - other.hi) & 0xffffffff) >>> 0) - + (((this.lo - other.lo) < 0) ? 1 : 0); + return new jspb.arith.Int64(lo >>> 0, hi >>> 0); +}; + + +/** + * Make a copy of the int64. + * @return {!jspb.arith.Int64} + */ +jspb.arith.Int64.prototype.clone = function() { + return new jspb.arith.Int64(this.lo, this.hi); +}; + + +/** + * Convert a 64-bit number to a string. + * @return {string} + * @override + */ +jspb.arith.Int64.prototype.toString = function() { + // If the number is negative, find its twos-complement inverse. + var sign = (this.hi & 0x80000000) != 0; + var num = new jspb.arith.UInt64(this.lo, this.hi); + if (sign) { + num = new jspb.arith.UInt64(0, 0).sub(num); + } + return (sign ? '-' : '') + num.toString(); +}; + + +/** + * Parse a string into a 64-bit number. Returns `null` on a parse error. + * @param {string} s + * @return {?jspb.arith.Int64} + */ +jspb.arith.Int64.fromString = function(s) { + var hasNegative = (s.length > 0 && s[0] == '-'); + if (hasNegative) { + s = s.substring(1); + } + var num = jspb.arith.UInt64.fromString(s); + if (num === null) { + return null; + } + if (hasNegative) { + num = new jspb.arith.UInt64(0, 0).sub(num); + } + return new jspb.arith.Int64(num.lo, num.hi); +}; |