Branch data Line data Source code
1 : : /*
2 : : * Copyright (C) 2026 by Thun Lu. All rights reserved.
3 : : * Author: Thun Lu <thun.lu@zohomail.cn>
4 : : * Repo: https://github.com/thun-res/vlink
5 : : * _ __ __ _ __
6 : : * | | / / / / (_) ____ / /__
7 : : * | | / / / / / / / __ \ / //_/
8 : : * | |/ / / /___ / / / / / / / ,<
9 : : * |___/ /_____/ /_/ /_/ /_/ /_/|_|
10 : : *
11 : : * Licensed under the Apache License, Version 2.0 (the "License");
12 : : * you may not use this file except in compliance with the License.
13 : : * You may obtain a copy of the License at
14 : : *
15 : : * http://www.apache.org/licenses/LICENSE-2.0
16 : : *
17 : : * Unless required by applicable law or agreed to in writing, software
18 : : * distributed under the License is distributed on an "AS IS" BASIS,
19 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
20 : : * See the License for the specific language governing permissions and
21 : : * limitations under the License.
22 : : */
23 : :
24 : : #include "./base/uint128.h"
25 : :
26 : : #include <iomanip>
27 : : #include <iostream>
28 : : #include <stdexcept>
29 : : #include <utility>
30 : :
31 : : #if defined(_MSC_VER)
32 : : #include <intrin.h>
33 : : #endif
34 : :
35 : : namespace vlink {
36 : :
37 : 5 : std::ostream& operator<<(std::ostream& os, const Uint128& value) noexcept {
38 : 5 : std::ios_base::fmtflags f(os.flags());
39 : 5 : char fill = os.fill();
40 : :
41 : 5 : os << "0x" << std::uppercase << std::hex << std::setfill('0');
42 : :
43 [ + + ]: 5 : if (value.high_ != 0) {
44 : 1 : os << value.high_ << std::setw(16) << value.low_;
45 : : } else {
46 : 4 : os << value.low_;
47 : : }
48 : :
49 : 5 : os.flags(f);
50 : 5 : os.fill(fill);
51 : :
52 : 5 : return os;
53 : : }
54 : :
55 : : // Uint128
56 : 0 : int Uint128::clz64(uint64_t x) noexcept {
57 : : #if defined(__GNUG__) || defined(__clang__)
58 [ # # ]: 0 : return x ? __builtin_clzll(x) : 64;
59 : : #elif defined(_MSC_VER)
60 : : unsigned long idx; // NOLINT(runtime/int, google-runtime-int)
61 : :
62 : : if (_BitScanReverse64(&idx, x)) {
63 : : return 63 - static_cast<int>(idx);
64 : : }
65 : :
66 : : return 64;
67 : : #else
68 : :
69 : : if (x == 0) {
70 : : return 64;
71 : : }
72 : :
73 : : int n = 0;
74 : :
75 : : while ((x & (1ull << 63)) == 0) {
76 : : x <<= 1;
77 : : ++n;
78 : : }
79 : :
80 : : return n;
81 : : #endif
82 : : }
83 : :
84 : 0 : void Uint128::mul_64_128(uint64_t a, uint64_t b, uint64_t& hi, uint64_t& lo) noexcept {
85 : : #if defined(__SIZEOF_INT128__)
86 : 0 : __uint128_t p = static_cast<__uint128_t>(a) * static_cast<__uint128_t>(b);
87 : :
88 : 0 : hi = static_cast<uint64_t>(p >> 64);
89 : 0 : lo = static_cast<uint64_t>(p);
90 : : #else
91 : : const uint64_t a0 = static_cast<uint32_t>(a);
92 : : const uint64_t a1 = a >> 32;
93 : : const uint64_t b0 = static_cast<uint32_t>(b);
94 : : const uint64_t b1 = b >> 32;
95 : :
96 : : const uint64_t p00 = a0 * b0;
97 : : const uint64_t p01 = a0 * b1;
98 : : const uint64_t p10 = a1 * b0;
99 : : const uint64_t p11 = a1 * b1;
100 : :
101 : : uint64_t carry = 0;
102 : : uint64_t mid = (p00 >> 32) + (p01 & 0xFFFFFFFFULL) + (p10 & 0xFFFFFFFFULL);
103 : : lo = (p00 & 0xFFFFFFFFULL) | (mid << 32);
104 : : carry = (mid >> 32);
105 : :
106 : : hi = p11 + (p01 >> 32) + (p10 >> 32) + carry;
107 : : #endif
108 : 0 : }
109 : :
110 : 0 : uint64_t Uint128::add64_carry(uint64_t a, uint64_t b, uint64_t& carry_out) noexcept {
111 : 0 : uint64_t s = a + b;
112 : :
113 [ # # ]: 0 : carry_out = (s < a) ? 1 : 0;
114 : :
115 : 0 : return s;
116 : : }
117 : :
118 : 0 : void Uint128::add_128_with64(uint64_t& high, uint64_t& low, uint64_t add_low, uint64_t add_high) noexcept {
119 : 0 : uint64_t c = 0;
120 : :
121 : 0 : low = add64_carry(low, add_low, c);
122 : :
123 : 0 : high = high + add_high + c;
124 : 0 : }
125 : :
126 : 0 : Uint128 Uint128::mul_u128_fallback(const Uint128& x, const Uint128& y) noexcept {
127 : 0 : uint64_t xh = x.get_high();
128 : 0 : uint64_t xl = x.get_low();
129 : 0 : uint64_t yh = y.get_high();
130 : 0 : uint64_t yl = y.get_low();
131 : :
132 : 0 : uint64_t p0_hi = 0;
133 : 0 : uint64_t p0_lo = 0;
134 : 0 : mul_64_128(xl, yl, p0_hi, p0_lo);
135 : :
136 : 0 : uint64_t p1_hi = 0;
137 : 0 : uint64_t p1_lo = 0;
138 : 0 : mul_64_128(xl, yh, p1_hi, p1_lo);
139 : :
140 : 0 : uint64_t p2_hi = 0;
141 : 0 : uint64_t p2_lo = 0;
142 : 0 : mul_64_128(xh, yl, p2_hi, p2_lo);
143 : :
144 : 0 : uint64_t p3_hi = 0;
145 : 0 : uint64_t p3_lo = 0;
146 : 0 : mul_64_128(xh, yh, p3_hi, p3_lo);
147 : :
148 : 0 : uint64_t low = p0_lo;
149 : 0 : uint64_t high = p0_hi;
150 : :
151 : 0 : uint64_t c1 = 0;
152 : 0 : high = add64_carry(high, p1_lo, c1);
153 : 0 : uint64_t c2 = 0;
154 : 0 : high = add64_carry(high, p2_lo, c2);
155 : :
156 : : (void)p1_hi;
157 : : (void)p2_hi;
158 : : (void)p3_hi;
159 : : (void)c1;
160 : : (void)c2;
161 : :
162 : 0 : return Uint128(high, low);
163 : : }
164 : :
165 : 11 : std::pair<Uint128, Uint128> Uint128::u128_divmod(const Uint128& dividend, const Uint128& divisor) {
166 [ + - + + : 11 : if VUNLIKELY (divisor.get_high() == 0 && divisor.get_low() == 0) {
+ + ]
167 [ + - ]: 4 : throw std::domain_error("Uint128 division by zero");
168 : : }
169 : :
170 : : #if defined(__SIZEOF_INT128__)
171 : 7 : __uint128_t a = (static_cast<__uint128_t>(dividend.get_high()) << 64) | dividend.get_low();
172 : 7 : __uint128_t b = (static_cast<__uint128_t>(divisor.get_high()) << 64) | divisor.get_low();
173 : :
174 : 7 : __uint128_t q = a / b;
175 : 7 : __uint128_t r = a % b;
176 : :
177 : 7 : return {Uint128(static_cast<uint64_t>(q >> 64), static_cast<uint64_t>(q)),
178 : 7 : Uint128(static_cast<uint64_t>(r >> 64), static_cast<uint64_t>(r))};
179 : : #else
180 : : Uint128 zero{0};
181 : :
182 : : if (dividend < divisor) {
183 : : return {zero, dividend};
184 : : }
185 : :
186 : : if (dividend == divisor) {
187 : : return {Uint128{1}, zero};
188 : : }
189 : :
190 : : Uint128 quotient{0};
191 : : Uint128 remainder{0};
192 : :
193 : : for (int i = 127; i >= 0; --i) {
194 : : remainder <<= 1;
195 : : Uint128 bit_mask = (i >= 64) ? Uint128{1ULL << (i - 64), 0} : Uint128{0, 1ULL << i};
196 : :
197 : : if ((dividend & bit_mask) != zero) {
198 : : remainder |= Uint128{1};
199 : : }
200 : :
201 : : if (remainder >= divisor) {
202 : : remainder -= divisor;
203 : : quotient |= bit_mask;
204 : : }
205 : : }
206 : :
207 : : return {quotient, remainder};
208 : : #endif
209 : : }
210 : :
211 : : } // namespace vlink
212 : :
213 : : namespace std {
214 : 6 : size_t hash<vlink::Uint128>::operator()(const vlink::Uint128& value) const noexcept {
215 : 6 : uint64_t h = value.get_high();
216 : 6 : uint64_t l = value.get_low();
217 : :
218 : 6 : h ^= l;
219 : 6 : h ^= h >> 33;
220 : 6 : h *= 0xff51afd7ed558ccdULL;
221 : 6 : h ^= h >> 33;
222 : 6 : h *= 0xc4ceb9fe1a85ec53ULL;
223 : 6 : h ^= h >> 33;
224 : :
225 : 6 : return static_cast<size_t>(h);
226 : : }
227 : : } // namespace std
|
