ceph/src/arrow/js/src/util/int.ts

   1 // Licensed to the Apache Software Foundation (ASF) under one
   2 // or more contributor license agreements.  See the NOTICE file
   3 // distributed with this work for additional information
   4 // regarding copyright ownership.  The ASF licenses this file
   5 // to you under the Apache License, Version 2.0 (the
   6 // "License"); you may not use this file except in compliance
   7 // with the License.  You may obtain a copy of the License at
   8 //
   9 //   http://www.apache.org/licenses/LICENSE-2.0
  10 //
  11 // Unless required by applicable law or agreed to in writing,
  12 // software distributed under the License is distributed on an
  13 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  14 // KIND, either express or implied.  See the License for the
  15 // specific language governing permissions and limitations
  16 // under the License.
  17
  18 /** @ignore */
  19 const carryBit16 = 1 << 16;
  20
  21 /** @ignore */
  22 function intAsHex(value: number): string {
  23     if (value < 0) {
  24         value = 0xFFFFFFFF + value + 1;
  25     }
  26     return `0x${value.toString(16)}`;
  27 }
  28
  29 /** @ignore */
  30 const kInt32DecimalDigits = 8;
  31 /** @ignore */
  32 const kPowersOfTen = [1,
  33                       10,
  34                       100,
  35                       1000,
  36                       10000,
  37                       100000,
  38                       1000000,
  39                       10000000,
  40                       100000000];
  41
  42 /** @ignore */
  43 export class BaseInt64 {
  44     constructor (protected buffer: Uint32Array) {}
  45
  46     public high(): number { return this.buffer[1]; }
  47     public low (): number { return this.buffer[0]; }
  48
  49     protected _times(other: BaseInt64) {
  50         // Break the left and right numbers into 16 bit chunks
  51         // so that we can multiply them without overflow.
  52         const L = new Uint32Array([
  53             this.buffer[1] >>> 16,
  54             this.buffer[1] & 0xFFFF,
  55             this.buffer[0] >>> 16,
  56             this.buffer[0] & 0xFFFF
  57         ]);
  58
  59         const R = new Uint32Array([
  60             other.buffer[1] >>> 16,
  61             other.buffer[1] & 0xFFFF,
  62             other.buffer[0] >>> 16,
  63             other.buffer[0] & 0xFFFF
  64         ]);
  65
  66         let product = L[3] * R[3];
  67         this.buffer[0] = product & 0xFFFF;
  68
  69         let sum = product >>> 16;
  70
  71         product = L[2] * R[3];
  72         sum += product;
  73
  74         product = (L[3] * R[2]) >>> 0;
  75         sum += product;
  76
  77         this.buffer[0] += sum << 16;
  78
  79         this.buffer[1] = (sum >>> 0 < product ? carryBit16 : 0);
  80
  81         this.buffer[1] += sum >>> 16;
  82         this.buffer[1] += L[1] * R[3] + L[2] * R[2] + L[3] * R[1];
  83         this.buffer[1] += (L[0] * R[3] + L[1] * R[2] + L[2] * R[1] + L[3] * R[0]) << 16;
  84
  85         return this;
  86       }
  87
  88     protected _plus(other: BaseInt64) {
  89         const sum = (this.buffer[0] + other.buffer[0]) >>> 0;
  90         this.buffer[1] += other.buffer[1];
  91         if (sum < (this.buffer[0] >>> 0)) {
  92           ++this.buffer[1];
  93         }
  94         this.buffer[0] = sum;
  95     }
  96
  97     public lessThan(other: BaseInt64): boolean {
  98         return this.buffer[1] < other.buffer[1] ||
  99             (this.buffer[1] === other.buffer[1] && this.buffer[0] < other.buffer[0]);
 100     }
 101
 102     public equals(other: BaseInt64): boolean {
 103         return this.buffer[1] === other.buffer[1] && this.buffer[0] == other.buffer[0];
 104     }
 105
 106     public greaterThan(other: BaseInt64): boolean {
 107         return other.lessThan(this);
 108     }
 109
 110     public hex(): string {
 111         return `${intAsHex(this.buffer[1])} ${intAsHex(this.buffer[0])}`;
 112     }
 113 }
 114
 115 /** @ignore */
 116 export class Uint64 extends BaseInt64 {
 117     public times(other: Uint64): Uint64 {
 118         this._times(other);
 119         return this;
 120     }
 121
 122     public plus(other: Uint64): Uint64 {
 123         this._plus(other);
 124         return this;
 125     }
 126
 127     /** @nocollapse */
 128     public static from(val: any, out_buffer = new Uint32Array(2)): Uint64 {
 129         return Uint64.fromString(
 130             typeof(val) === 'string' ? val : val.toString(),
 131             out_buffer
 132         );
 133     }
 134
 135     /** @nocollapse */
 136     public static fromNumber(num: number, out_buffer = new Uint32Array(2)): Uint64 {
 137         // Always parse numbers as strings - pulling out high and low bits
 138         // directly seems to lose precision sometimes
 139         // For example:
 140         //     > -4613034156400212000 >>> 0
 141         //     721782784
 142         // The correct lower 32-bits are 721782752
 143         return Uint64.fromString(num.toString(), out_buffer);
 144     }
 145
 146     /** @nocollapse */
 147     public static fromString(str: string, out_buffer = new Uint32Array(2)): Uint64 {
 148         const length = str.length;
 149
 150         const out = new Uint64(out_buffer);
 151         for (let posn = 0; posn < length;) {
 152             const group = kInt32DecimalDigits < length - posn ?
 153                           kInt32DecimalDigits : length - posn;
 154             const chunk = new Uint64(new Uint32Array([parseInt(str.substr(posn, group), 10), 0]));
 155             const multiple = new Uint64(new Uint32Array([kPowersOfTen[group], 0]));
 156
 157             out.times(multiple);
 158             out.plus(chunk);
 159
 160             posn += group;
 161         }
 162
 163         return out;
 164     }
 165
 166     /** @nocollapse */
 167     public static convertArray(values: (string|number)[]): Uint32Array {
 168         const data = new Uint32Array(values.length * 2);
 169         for (let i = -1, n = values.length; ++i < n;) {
 170             Uint64.from(values[i], new Uint32Array(data.buffer, data.byteOffset + 2 * i * 4, 2));
 171         }
 172         return data;
 173     }
 174
 175     /** @nocollapse */
 176     public static multiply(left: Uint64, right: Uint64): Uint64 {
 177         const rtrn = new Uint64(new Uint32Array(left.buffer));
 178         return rtrn.times(right);
 179     }
 180
 181     /** @nocollapse */
 182     public static add(left: Uint64, right: Uint64): Uint64 {
 183         const rtrn = new Uint64(new Uint32Array(left.buffer));
 184         return rtrn.plus(right);
 185     }
 186 }
 187
 188 /** @ignore */
 189 export class Int64 extends BaseInt64 {
 190     public negate(): Int64 {
 191         this.buffer[0] = ~this.buffer[0] + 1;
 192         this.buffer[1] = ~this.buffer[1];
 193
 194         if (this.buffer[0] == 0) { ++this.buffer[1]; }
 195         return this;
 196     }
 197
 198     public times(other: Int64): Int64 {
 199         this._times(other);
 200         return this;
 201     }
 202
 203     public plus(other: Int64): Int64 {
 204         this._plus(other);
 205         return this;
 206     }
 207
 208     public lessThan(other: Int64): boolean {
 209         // force high bytes to be signed
 210         const this_high = this.buffer[1] << 0;
 211         const other_high = other.buffer[1] << 0;
 212         return this_high < other_high ||
 213             (this_high === other_high && this.buffer[0] < other.buffer[0]);
 214     }
 215
 216     /** @nocollapse */
 217     public static from(val: any, out_buffer = new Uint32Array(2)): Int64 {
 218         return Int64.fromString(
 219             typeof(val) === 'string' ? val : val.toString(),
 220             out_buffer
 221         );
 222     }
 223
 224     /** @nocollapse */
 225     public static fromNumber(num: number, out_buffer = new Uint32Array(2)): Int64 {
 226         // Always parse numbers as strings - pulling out high and low bits
 227         // directly seems to lose precision sometimes
 228         // For example:
 229         //     > -4613034156400212000 >>> 0
 230         //     721782784
 231         // The correct lower 32-bits are 721782752
 232         return Int64.fromString(num.toString(), out_buffer);
 233     }
 234
 235     /** @nocollapse */
 236     public static fromString(str: string, out_buffer = new Uint32Array(2)): Int64 {
 237         // TODO: Assert that out_buffer is 0 and length = 2
 238         const negate = str.startsWith('-');
 239         const length = str.length;
 240
 241         const out = new Int64(out_buffer);
 242         for (let posn = negate ? 1 : 0; posn < length;) {
 243             const group = kInt32DecimalDigits < length - posn ?
 244                           kInt32DecimalDigits : length - posn;
 245             const chunk = new Int64(new Uint32Array([parseInt(str.substr(posn, group), 10), 0]));
 246             const multiple = new Int64(new Uint32Array([kPowersOfTen[group], 0]));
 247
 248             out.times(multiple);
 249             out.plus(chunk);
 250
 251             posn += group;
 252         }
 253         return negate ? out.negate() : out;
 254     }
 255
 256     /** @nocollapse */
 257     public static convertArray(values: (string|number)[]): Uint32Array {
 258         const data = new Uint32Array(values.length * 2);
 259         for (let i = -1, n = values.length; ++i < n;) {
 260             Int64.from(values[i], new Uint32Array(data.buffer, data.byteOffset + 2 * i * 4, 2));
 261         }
 262         return data;
 263     }
 264
 265     /** @nocollapse */
 266     public static multiply(left: Int64, right: Int64): Int64 {
 267         const rtrn = new Int64(new Uint32Array(left.buffer));
 268         return rtrn.times(right);
 269     }
 270
 271     /** @nocollapse */
 272     public static add(left: Int64, right: Int64): Int64 {
 273         const rtrn = new Int64(new Uint32Array(left.buffer));
 274         return rtrn.plus(right);
 275     }
 276 }
 277
 278 /** @ignore */
 279 export class Int128 {
 280     constructor (private buffer: Uint32Array) {
 281         // buffer[3] MSB (high)
 282         // buffer[2]
 283         // buffer[1]
 284         // buffer[0] LSB (low)
 285     }
 286
 287     public high(): Int64 {
 288         return new Int64(new Uint32Array(this.buffer.buffer, this.buffer.byteOffset + 8, 2));
 289     }
 290
 291     public low(): Int64 {
 292         return new Int64(new Uint32Array(this.buffer.buffer, this.buffer.byteOffset, 2));
 293     }
 294
 295     public negate(): Int128 {
 296         this.buffer[0] = ~this.buffer[0] + 1;
 297         this.buffer[1] = ~this.buffer[1];
 298         this.buffer[2] = ~this.buffer[2];
 299         this.buffer[3] = ~this.buffer[3];
 300
 301         if (this.buffer[0] == 0) { ++this.buffer[1]; }
 302         if (this.buffer[1] == 0) { ++this.buffer[2]; }
 303         if (this.buffer[2] == 0) { ++this.buffer[3]; }
 304         return this;
 305     }
 306
 307     public times(other: Int128): Int128 {
 308         // Break the left and right numbers into 32 bit chunks
 309         // so that we can multiply them without overflow.
 310         const L0 = new Uint64(new Uint32Array([this.buffer[3],  0]));
 311         const L1 = new Uint64(new Uint32Array([this.buffer[2],  0]));
 312         const L2 = new Uint64(new Uint32Array([this.buffer[1],  0]));
 313         const L3 = new Uint64(new Uint32Array([this.buffer[0],  0]));
 314
 315         const R0 = new Uint64(new Uint32Array([other.buffer[3], 0]));
 316         const R1 = new Uint64(new Uint32Array([other.buffer[2], 0]));
 317         const R2 = new Uint64(new Uint32Array([other.buffer[1], 0]));
 318         const R3 = new Uint64(new Uint32Array([other.buffer[0], 0]));
 319
 320         let product = Uint64.multiply(L3, R3);
 321         this.buffer[0] = product.low();
 322
 323         const sum = new Uint64(new Uint32Array([product.high(), 0]));
 324
 325         product = Uint64.multiply(L2, R3);
 326         sum.plus(product);
 327
 328         product = Uint64.multiply(L3, R2);
 329         sum.plus(product);
 330
 331         this.buffer[1] = sum.low();
 332
 333         this.buffer[3] = (sum.lessThan(product) ? 1 : 0);
 334
 335         this.buffer[2] = sum.high();
 336         const high = new Uint64(new Uint32Array(this.buffer.buffer, this.buffer.byteOffset + 8, 2));
 337
 338         high.plus(Uint64.multiply(L1, R3))
 339             .plus(Uint64.multiply(L2, R2))
 340             .plus(Uint64.multiply(L3, R1));
 341         this.buffer[3] += Uint64.multiply(L0, R3)
 342                         .plus(Uint64.multiply(L1, R2))
 343                         .plus(Uint64.multiply(L2, R1))
 344                         .plus(Uint64.multiply(L3, R0)).low();
 345
 346         return this;
 347     }
 348
 349     public plus(other: Int128): Int128 {
 350         const sums = new Uint32Array(4);
 351         sums[3] = (this.buffer[3] + other.buffer[3]) >>> 0;
 352         sums[2] = (this.buffer[2] + other.buffer[2]) >>> 0;
 353         sums[1] = (this.buffer[1] + other.buffer[1]) >>> 0;
 354         sums[0] = (this.buffer[0] + other.buffer[0]) >>> 0;
 355
 356         if (sums[0] < (this.buffer[0] >>> 0)) {
 357             ++sums[1];
 358         }
 359         if (sums[1] < (this.buffer[1] >>> 0)) {
 360             ++sums[2];
 361         }
 362         if (sums[2] < (this.buffer[2] >>> 0)) {
 363             ++sums[3];
 364         }
 365
 366         this.buffer[3] = sums[3];
 367         this.buffer[2] = sums[2];
 368         this.buffer[1] = sums[1];
 369         this.buffer[0] = sums[0];
 370
 371         return this;
 372     }
 373
 374     public hex(): string {
 375         return `${intAsHex(this.buffer[3])} ${intAsHex(this.buffer[2])} ${intAsHex(this.buffer[1])} ${intAsHex(this.buffer[0])}`;
 376     }
 377
 378     /** @nocollapse */
 379     public static multiply(left: Int128, right: Int128): Int128 {
 380         const rtrn = new Int128(new Uint32Array(left.buffer));
 381         return rtrn.times(right);
 382     }
 383
 384     /** @nocollapse */
 385     public static add(left: Int128, right: Int128): Int128 {
 386         const rtrn = new Int128(new Uint32Array(left.buffer));
 387         return rtrn.plus(right);
 388     }
 389
 390     /** @nocollapse */
 391     public static from(val: any, out_buffer = new Uint32Array(4)): Int128 {
 392         return Int128.fromString(
 393             typeof(val) === 'string' ? val : val.toString(),
 394             out_buffer
 395         );
 396     }
 397
 398     /** @nocollapse */
 399     public static fromNumber(num: number, out_buffer = new Uint32Array(4)): Int128 {
 400         // Always parse numbers as strings - pulling out high and low bits
 401         // directly seems to lose precision sometimes
 402         // For example:
 403         //     > -4613034156400212000 >>> 0
 404         //     721782784
 405         // The correct lower 32-bits are 721782752
 406         return Int128.fromString(num.toString(), out_buffer);
 407     }
 408
 409     /** @nocollapse */
 410     public static fromString(str: string, out_buffer = new Uint32Array(4)): Int128 {
 411         // TODO: Assert that out_buffer is 0 and length = 4
 412         const negate = str.startsWith('-');
 413         const length = str.length;
 414
 415         const out = new Int128(out_buffer);
 416         for (let posn = negate ? 1 : 0; posn < length;) {
 417             const group = kInt32DecimalDigits < length - posn ?
 418                           kInt32DecimalDigits : length - posn;
 419             const chunk = new Int128(new Uint32Array([parseInt(str.substr(posn, group), 10), 0, 0, 0]));
 420             const multiple = new Int128(new Uint32Array([kPowersOfTen[group], 0, 0, 0]));
 421
 422             out.times(multiple);
 423             out.plus(chunk);
 424
 425             posn += group;
 426         }
 427
 428         return negate ? out.negate() : out;
 429     }
 430
 431     /** @nocollapse */
 432     public static convertArray(values: (string|number)[]): Uint32Array {
 433         // TODO: Distinguish between string and number at compile-time
 434         const data = new Uint32Array(values.length * 4);
 435         for (let i = -1, n = values.length; ++i < n;) {
 436             Int128.from(values[i], new Uint32Array(data.buffer, data.byteOffset + 4 * 4 * i, 4));
 437         }
 438         return data;
 439     }
 440 }