]>
Commit | Line | Data |
---|---|---|
1d09f67e TL |
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 | } |