1// Copyright (C) 2023 The Android Open Source Project
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//      http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15export class BigintMath {
16  static INT64_MAX: bigint = (2n ** 63n) - 1n;
17  static INT64_MIN: bigint = -(2n ** 63n);
18
19  // Returns the smallest integral power of 2 that is not smaller than n.
20  // If n is less than or equal to 0, returns 1.
21  static bitCeil(n: bigint): bigint {
22    let result = 1n;
23    while (result < n) {
24      result <<= 1n;
25    }
26    return result;
27  }
28
29  // Returns the largest integral power of 2 which is not greater than n.
30  // If n is less than or equal to 0, returns 1.
31  static bitFloor(n: bigint): bigint {
32    let result = 1n;
33    while ((result << 1n) <= n) {
34      result <<= 1n;
35    }
36    return result;
37  }
38
39  // Returns the largest integral value x where 2^x is not greater than n.
40  static log2(n: bigint): number {
41    let result = 1n;
42    let log2 = 0;
43    while ((result << 1n) <= n) {
44      result <<= 1n;
45      ++log2;
46    }
47    return log2;
48  }
49
50  // Returns the integral multiple of step which is closest to n.
51  // If step is less than or equal to 0, returns n.
52  static quant(n: bigint, step: bigint): bigint {
53    step = BigintMath.max(1n, step);
54    const halfStep = step / 2n;
55    return step * ((n + halfStep) / step);
56  }
57
58  // Returns the largest integral multiple of step which is not larger than n.
59  // If step is less than or equal to 0, returns n.
60  static quantFloor(n: bigint, step: bigint): bigint {
61    step = BigintMath.max(1n, step);
62    return step * (n / step);
63  }
64
65  // Returns the smallest integral multiple of step which is not smaller than n.
66  // If step is less than or equal to 0, returns n.
67  static quantCeil(n: bigint, step: bigint): bigint {
68    step = BigintMath.max(1n, step);
69    const remainder = n % step;
70    if (remainder === 0n) {
71      return n;
72    }
73    const quotient = n / step;
74    return (quotient + 1n) * step;
75  }
76
77  // Returns the greater of a and b.
78  static max(a: bigint, b: bigint): bigint {
79    return a > b ? a : b;
80  }
81
82  // Returns the smaller of a and b.
83  static min(a: bigint, b: bigint): bigint {
84    return a < b ? a : b;
85  }
86
87  // Returns the number of 1 bits in n.
88  static popcount(n: bigint): number {
89    if (n < 0n) {
90      throw Error(`Can\'t get popcount of negative number ${n}`);
91    }
92    let count = 0;
93    while (n) {
94      if (n & 1n) {
95        ++count;
96      }
97      n >>= 1n;
98    }
99    return count;
100  }
101
102  // Return the ratio between two bigints as a number.
103  static ratio(dividend: bigint, divisor: bigint): number {
104    return Number(dividend) / Number(divisor);
105  }
106
107  // Calculates the absolute value of a n.
108  static abs(n: bigint) {
109    return n < 0n ? -1n * n : n;
110  }
111}
112