1// Protocol Buffers - Google's data interchange format 2// Copyright 2008 Google Inc. All rights reserved. 3// https://developers.google.com/protocol-buffers/ 4// 5// Redistribution and use in source and binary forms, with or without 6// modification, are permitted provided that the following conditions are 7// met: 8// 9// * Redistributions of source code must retain the above copyright 10// notice, this list of conditions and the following disclaimer. 11// * Redistributions in binary form must reproduce the above 12// copyright notice, this list of conditions and the following disclaimer 13// in the documentation and/or other materials provided with the 14// distribution. 15// * Neither the name of Google Inc. nor the names of its 16// contributors may be used to endorse or promote products derived from 17// this software without specific prior written permission. 18// 19// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31/** 32 * @fileoverview This file contains helper code used by jspb.utils to 33 * handle 64-bit integer conversion to/from strings. 34 * 35 * @author cfallin@google.com (Chris Fallin) 36 * 37 * TODO(haberman): move this to javascript/closure/math? 38 */ 39 40goog.provide('jspb.arith.Int64'); 41goog.provide('jspb.arith.UInt64'); 42 43/** 44 * UInt64 implements some 64-bit arithmetic routines necessary for properly 45 * handling 64-bit integer fields. It implements lossless integer arithmetic on 46 * top of JavaScript's number type, which has only 53 bits of precision, by 47 * representing 64-bit integers as two 32-bit halves. 48 * 49 * @param {number} lo The low 32 bits. 50 * @param {number} hi The high 32 bits. 51 * @constructor 52 */ 53jspb.arith.UInt64 = function(lo, hi) { 54 /** 55 * The low 32 bits. 56 * @public {number} 57 */ 58 this.lo = lo; 59 /** 60 * The high 32 bits. 61 * @public {number} 62 */ 63 this.hi = hi; 64}; 65 66 67/** 68 * Compare two 64-bit numbers. Returns -1 if the first is 69 * less, +1 if the first is greater, or 0 if both are equal. 70 * @param {!jspb.arith.UInt64} other 71 * @return {number} 72 */ 73jspb.arith.UInt64.prototype.cmp = function(other) { 74 if (this.hi < other.hi || (this.hi == other.hi && this.lo < other.lo)) { 75 return -1; 76 } else if (this.hi == other.hi && this.lo == other.lo) { 77 return 0; 78 } else { 79 return 1; 80 } 81}; 82 83 84/** 85 * Right-shift this number by one bit. 86 * @return {!jspb.arith.UInt64} 87 */ 88jspb.arith.UInt64.prototype.rightShift = function() { 89 var hi = this.hi >>> 1; 90 var lo = (this.lo >>> 1) | ((this.hi & 1) << 31); 91 return new jspb.arith.UInt64(lo >>> 0, hi >>> 0); 92}; 93 94 95/** 96 * Left-shift this number by one bit. 97 * @return {!jspb.arith.UInt64} 98 */ 99jspb.arith.UInt64.prototype.leftShift = function() { 100 var lo = this.lo << 1; 101 var hi = (this.hi << 1) | (this.lo >>> 31); 102 return new jspb.arith.UInt64(lo >>> 0, hi >>> 0); 103}; 104 105 106/** 107 * Test the MSB. 108 * @return {boolean} 109 */ 110jspb.arith.UInt64.prototype.msb = function() { 111 return !!(this.hi & 0x80000000); 112}; 113 114 115/** 116 * Test the LSB. 117 * @return {boolean} 118 */ 119jspb.arith.UInt64.prototype.lsb = function() { 120 return !!(this.lo & 1); 121}; 122 123 124/** 125 * Test whether this number is zero. 126 * @return {boolean} 127 */ 128jspb.arith.UInt64.prototype.zero = function() { 129 return this.lo == 0 && this.hi == 0; 130}; 131 132 133/** 134 * Add two 64-bit numbers to produce a 64-bit number. 135 * @param {!jspb.arith.UInt64} other 136 * @return {!jspb.arith.UInt64} 137 */ 138jspb.arith.UInt64.prototype.add = function(other) { 139 var lo = ((this.lo + other.lo) & 0xffffffff) >>> 0; 140 var hi = 141 (((this.hi + other.hi) & 0xffffffff) >>> 0) + 142 (((this.lo + other.lo) >= 0x100000000) ? 1 : 0); 143 return new jspb.arith.UInt64(lo >>> 0, hi >>> 0); 144}; 145 146 147/** 148 * Subtract two 64-bit numbers to produce a 64-bit number. 149 * @param {!jspb.arith.UInt64} other 150 * @return {!jspb.arith.UInt64} 151 */ 152jspb.arith.UInt64.prototype.sub = function(other) { 153 var lo = ((this.lo - other.lo) & 0xffffffff) >>> 0; 154 var hi = 155 (((this.hi - other.hi) & 0xffffffff) >>> 0) - 156 (((this.lo - other.lo) < 0) ? 1 : 0); 157 return new jspb.arith.UInt64(lo >>> 0, hi >>> 0); 158}; 159 160 161/** 162 * Multiply two 32-bit numbers to produce a 64-bit number. 163 * @param {number} a The first integer: must be in [0, 2^32-1). 164 * @param {number} b The second integer: must be in [0, 2^32-1). 165 * @return {!jspb.arith.UInt64} 166 */ 167jspb.arith.UInt64.mul32x32 = function(a, b) { 168 // Directly multiplying two 32-bit numbers may produce up to 64 bits of 169 // precision, thus losing precision because of the 53-bit mantissa of 170 // JavaScript numbers. So we multiply with 16-bit digits (radix 65536) 171 // instead. 172 var aLow = (a & 0xffff); 173 var aHigh = (a >>> 16); 174 var bLow = (b & 0xffff); 175 var bHigh = (b >>> 16); 176 var productLow = 177 // 32-bit result, result bits 0-31, take all 32 bits 178 (aLow * bLow) + 179 // 32-bit result, result bits 16-47, take bottom 16 as our top 16 180 ((aLow * bHigh) & 0xffff) * 0x10000 + 181 // 32-bit result, result bits 16-47, take bottom 16 as our top 16 182 ((aHigh * bLow) & 0xffff) * 0x10000; 183 var productHigh = 184 // 32-bit result, result bits 32-63, take all 32 bits 185 (aHigh * bHigh) + 186 // 32-bit result, result bits 16-47, take top 16 as our bottom 16 187 ((aLow * bHigh) >>> 16) + 188 // 32-bit result, result bits 16-47, take top 16 as our bottom 16 189 ((aHigh * bLow) >>> 16); 190 191 // Carry. Note that we actually have up to *two* carries due to addition of 192 // three terms. 193 while (productLow >= 0x100000000) { 194 productLow -= 0x100000000; 195 productHigh += 1; 196 } 197 198 return new jspb.arith.UInt64(productLow >>> 0, productHigh >>> 0); 199}; 200 201 202/** 203 * Multiply this number by a 32-bit number, producing a 96-bit number, then 204 * truncate the top 32 bits. 205 * @param {number} a The multiplier. 206 * @return {!jspb.arith.UInt64} 207 */ 208jspb.arith.UInt64.prototype.mul = function(a) { 209 // Produce two parts: at bits 0-63, and 32-95. 210 var lo = jspb.arith.UInt64.mul32x32(this.lo, a); 211 var hi = jspb.arith.UInt64.mul32x32(this.hi, a); 212 // Left-shift hi by 32 bits, truncating its top bits. The parts will then be 213 // aligned for addition. 214 hi.hi = hi.lo; 215 hi.lo = 0; 216 return lo.add(hi); 217}; 218 219 220/** 221 * Divide a 64-bit number by a 32-bit number to produce a 222 * 64-bit quotient and a 32-bit remainder. 223 * @param {number} _divisor 224 * @return {Array<jspb.arith.UInt64>} array of [quotient, remainder], 225 * unless divisor is 0, in which case an empty array is returned. 226 */ 227jspb.arith.UInt64.prototype.div = function(_divisor) { 228 if (_divisor == 0) { 229 return []; 230 } 231 232 // We perform long division using a radix-2 algorithm, for simplicity (i.e., 233 // one bit at a time). TODO: optimize to a radix-2^32 algorithm, taking care 234 // to get the variable shifts right. 235 var quotient = new jspb.arith.UInt64(0, 0); 236 var remainder = new jspb.arith.UInt64(this.lo, this.hi); 237 var divisor = new jspb.arith.UInt64(_divisor, 0); 238 var unit = new jspb.arith.UInt64(1, 0); 239 240 // Left-shift the divisor and unit until the high bit of divisor is set. 241 while (!divisor.msb()) { 242 divisor = divisor.leftShift(); 243 unit = unit.leftShift(); 244 } 245 246 // Perform long division one bit at a time. 247 while (!unit.zero()) { 248 // If divisor < remainder, add unit to quotient and subtract divisor from 249 // remainder. 250 if (divisor.cmp(remainder) <= 0) { 251 quotient = quotient.add(unit); 252 remainder = remainder.sub(divisor); 253 } 254 // Right-shift the divisor and unit. 255 divisor = divisor.rightShift(); 256 unit = unit.rightShift(); 257 } 258 259 return [quotient, remainder]; 260}; 261 262 263/** 264 * Convert a 64-bit number to a string. 265 * @return {string} 266 * @override 267 */ 268jspb.arith.UInt64.prototype.toString = function() { 269 var result = ''; 270 var num = this; 271 while (!num.zero()) { 272 var divResult = num.div(10); 273 var quotient = divResult[0], remainder = divResult[1]; 274 result = remainder.lo + result; 275 num = quotient; 276 } 277 if (result == '') { 278 result = '0'; 279 } 280 return result; 281}; 282 283 284/** 285 * Parse a string into a 64-bit number. Returns `null` on a parse error. 286 * @param {string} s 287 * @return {?jspb.arith.UInt64} 288 */ 289jspb.arith.UInt64.fromString = function(s) { 290 var result = new jspb.arith.UInt64(0, 0); 291 // optimization: reuse this instance for each digit. 292 var digit64 = new jspb.arith.UInt64(0, 0); 293 for (var i = 0; i < s.length; i++) { 294 if (s[i] < '0' || s[i] > '9') { 295 return null; 296 } 297 var digit = parseInt(s[i], 10); 298 digit64.lo = digit; 299 result = result.mul(10).add(digit64); 300 } 301 return result; 302}; 303 304 305/** 306 * Make a copy of the uint64. 307 * @return {!jspb.arith.UInt64} 308 */ 309jspb.arith.UInt64.prototype.clone = function() { 310 return new jspb.arith.UInt64(this.lo, this.hi); 311}; 312 313 314/** 315 * Int64 is like UInt64, but modifies string conversions to interpret the stored 316 * 64-bit value as a twos-complement-signed integer. It does *not* support the 317 * full range of operations that UInt64 does: only add, subtract, and string 318 * conversions. 319 * 320 * N.B. that multiply and divide routines are *NOT* supported. They will throw 321 * exceptions. (They are not necessary to implement string conversions, which 322 * are the only operations we really need in jspb.) 323 * 324 * @param {number} lo The low 32 bits. 325 * @param {number} hi The high 32 bits. 326 * @constructor 327 */ 328jspb.arith.Int64 = function(lo, hi) { 329 /** 330 * The low 32 bits. 331 * @public {number} 332 */ 333 this.lo = lo; 334 /** 335 * The high 32 bits. 336 * @public {number} 337 */ 338 this.hi = hi; 339}; 340 341 342/** 343 * Add two 64-bit numbers to produce a 64-bit number. 344 * @param {!jspb.arith.Int64} other 345 * @return {!jspb.arith.Int64} 346 */ 347jspb.arith.Int64.prototype.add = function(other) { 348 var lo = ((this.lo + other.lo) & 0xffffffff) >>> 0; 349 var hi = 350 (((this.hi + other.hi) & 0xffffffff) >>> 0) + 351 (((this.lo + other.lo) >= 0x100000000) ? 1 : 0); 352 return new jspb.arith.Int64(lo >>> 0, hi >>> 0); 353}; 354 355 356/** 357 * Subtract two 64-bit numbers to produce a 64-bit number. 358 * @param {!jspb.arith.Int64} other 359 * @return {!jspb.arith.Int64} 360 */ 361jspb.arith.Int64.prototype.sub = function(other) { 362 var lo = ((this.lo - other.lo) & 0xffffffff) >>> 0; 363 var hi = 364 (((this.hi - other.hi) & 0xffffffff) >>> 0) - 365 (((this.lo - other.lo) < 0) ? 1 : 0); 366 return new jspb.arith.Int64(lo >>> 0, hi >>> 0); 367}; 368 369 370/** 371 * Make a copy of the int64. 372 * @return {!jspb.arith.Int64} 373 */ 374jspb.arith.Int64.prototype.clone = function() { 375 return new jspb.arith.Int64(this.lo, this.hi); 376}; 377 378 379/** 380 * Convert a 64-bit number to a string. 381 * @return {string} 382 * @override 383 */ 384jspb.arith.Int64.prototype.toString = function() { 385 // If the number is negative, find its twos-complement inverse. 386 var sign = (this.hi & 0x80000000) != 0; 387 var num = new jspb.arith.UInt64(this.lo, this.hi); 388 if (sign) { 389 num = new jspb.arith.UInt64(0, 0).sub(num); 390 } 391 return (sign ? '-' : '') + num.toString(); 392}; 393 394 395/** 396 * Parse a string into a 64-bit number. Returns `null` on a parse error. 397 * @param {string} s 398 * @return {?jspb.arith.Int64} 399 */ 400jspb.arith.Int64.fromString = function(s) { 401 var hasNegative = (s.length > 0 && s[0] == '-'); 402 if (hasNegative) { 403 s = s.substring(1); 404 } 405 var num = jspb.arith.UInt64.fromString(s); 406 if (num === null) { 407 return null; 408 } 409 if (hasNegative) { 410 num = new jspb.arith.UInt64(0, 0).sub(num); 411 } 412 return new jspb.arith.Int64(num.lo, num.hi); 413}; 414