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 : 4 : std::ostream& operator<<(std::ostream& os, const Uint128& value) noexcept {
38 : 4 : std::ios_base::fmtflags f(os.flags());
39 : :
40 : 4 : os << "0x" << std::uppercase << std::hex << std::setfill('0');
41 : :
42 [ + + ]: 4 : if (value.high_ != 0) {
43 : 1 : os << value.high_ << std::setw(16) << value.low_;
44 : : } else {
45 : 3 : os << value.low_;
46 : : }
47 : :
48 : 4 : os.flags(f);
49 : :
50 : 4 : return os;
51 : : }
52 : :
53 : : // Uint128
54 : 0 : int Uint128::clz64(uint64_t x) noexcept {
55 : : #if defined(__GNUG__) || defined(__clang__)
56 [ # # ]: 0 : return x ? __builtin_clzll(x) : 64;
57 : : #elif defined(_MSC_VER)
58 : : unsigned long idx; // NOLINT(runtime/int, google-runtime-int)
59 : :
60 : : if (_BitScanReverse64(&idx, x)) {
61 : : return 63 - static_cast<int>(idx);
62 : : }
63 : :
64 : : return 64;
65 : : #else
66 : :
67 : : if (x == 0) {
68 : : return 64;
69 : : }
70 : :
71 : : int n = 0;
72 : :
73 : : while ((x & (1ull << 63)) == 0) {
74 : : x <<= 1;
75 : : ++n;
76 : : }
77 : :
78 : : return n;
79 : : #endif
80 : : }
81 : :
82 : 0 : void Uint128::mul_64_128(uint64_t a, uint64_t b, uint64_t& hi, uint64_t& lo) noexcept {
83 : : #if defined(__SIZEOF_INT128__)
84 : 0 : __uint128_t p = static_cast<__uint128_t>(a) * static_cast<__uint128_t>(b);
85 : :
86 : 0 : hi = static_cast<uint64_t>(p >> 64);
87 : 0 : lo = static_cast<uint64_t>(p);
88 : : #else
89 : : const uint64_t a0 = static_cast<uint32_t>(a);
90 : : const uint64_t a1 = a >> 32;
91 : : const uint64_t b0 = static_cast<uint32_t>(b);
92 : : const uint64_t b1 = b >> 32;
93 : :
94 : : const uint64_t p00 = a0 * b0;
95 : : const uint64_t p01 = a0 * b1;
96 : : const uint64_t p10 = a1 * b0;
97 : : const uint64_t p11 = a1 * b1;
98 : :
99 : : uint64_t carry = 0;
100 : : uint64_t mid = (p00 >> 32) + (p01 & 0xFFFFFFFFULL) + (p10 & 0xFFFFFFFFULL);
101 : : lo = (p00 & 0xFFFFFFFFULL) | (mid << 32);
102 : : carry = (mid >> 32);
103 : :
104 : : hi = p11 + (p01 >> 32) + (p10 >> 32) + carry;
105 : : #endif
106 : 0 : }
107 : :
108 : 0 : uint64_t Uint128::add64_carry(uint64_t a, uint64_t b, uint64_t& carry_out) noexcept {
109 : 0 : uint64_t s = a + b;
110 : :
111 [ # # ]: 0 : carry_out = (s < a) ? 1 : 0;
112 : :
113 : 0 : return s;
114 : : }
115 : :
116 : 0 : void Uint128::add_128_with64(uint64_t& high, uint64_t& low, uint64_t add_low, uint64_t add_high) noexcept {
117 : 0 : uint64_t c = 0;
118 : :
119 : 0 : low = add64_carry(low, add_low, c);
120 : :
121 : 0 : high = high + add_high + c;
122 : 0 : }
123 : :
124 : 0 : Uint128 Uint128::mul_u128_fallback(const Uint128& x, const Uint128& y) noexcept {
125 : 0 : uint64_t xh = x.get_high();
126 : 0 : uint64_t xl = x.get_low();
127 : 0 : uint64_t yh = y.get_high();
128 : 0 : uint64_t yl = y.get_low();
129 : :
130 : 0 : uint64_t p0_hi = 0;
131 : 0 : uint64_t p0_lo = 0;
132 : 0 : mul_64_128(xl, yl, p0_hi, p0_lo);
133 : :
134 : 0 : uint64_t p1_hi = 0;
135 : 0 : uint64_t p1_lo = 0;
136 : 0 : mul_64_128(xl, yh, p1_hi, p1_lo);
137 : :
138 : 0 : uint64_t p2_hi = 0;
139 : 0 : uint64_t p2_lo = 0;
140 : 0 : mul_64_128(xh, yl, p2_hi, p2_lo);
141 : :
142 : 0 : uint64_t p3_hi = 0;
143 : 0 : uint64_t p3_lo = 0;
144 : 0 : mul_64_128(xh, yh, p3_hi, p3_lo);
145 : :
146 : 0 : uint64_t low = p0_lo;
147 : 0 : uint64_t high = p0_hi;
148 : :
149 : 0 : uint64_t c1 = 0;
150 : 0 : high = add64_carry(high, p1_lo, c1);
151 : 0 : uint64_t c2 = 0;
152 : 0 : high = add64_carry(high, p2_lo, c2);
153 : :
154 : : (void)p1_hi;
155 : : (void)p2_hi;
156 : : (void)p3_hi;
157 : : (void)c1;
158 : : (void)c2;
159 : :
160 : 0 : return Uint128(high, low);
161 : : }
162 : :
163 : 11 : std::pair<Uint128, Uint128> Uint128::u128_divmod(const Uint128& dividend, const Uint128& divisor) {
164 [ + - + + : 11 : if VUNLIKELY (divisor.get_high() == 0 && divisor.get_low() == 0) {
+ + ]
165 [ + - ]: 4 : throw std::domain_error("Uint128 division by zero");
166 : : }
167 : :
168 : : #if defined(__SIZEOF_INT128__)
169 : 7 : __uint128_t a = (static_cast<__uint128_t>(dividend.get_high()) << 64) | dividend.get_low();
170 : 7 : __uint128_t b = (static_cast<__uint128_t>(divisor.get_high()) << 64) | divisor.get_low();
171 : :
172 : 7 : __uint128_t q = a / b;
173 : 7 : __uint128_t r = a % b;
174 : :
175 : 7 : return {Uint128(static_cast<uint64_t>(q >> 64), static_cast<uint64_t>(q)),
176 : 7 : Uint128(static_cast<uint64_t>(r >> 64), static_cast<uint64_t>(r))};
177 : : #else
178 : : Uint128 zero{0};
179 : :
180 : : if (dividend < divisor) {
181 : : return {zero, dividend};
182 : : }
183 : :
184 : : if (dividend == divisor) {
185 : : return {Uint128{1}, zero};
186 : : }
187 : :
188 : : Uint128 quotient{0};
189 : : Uint128 remainder{0};
190 : :
191 : : for (int i = 127; i >= 0; --i) {
192 : : remainder <<= 1;
193 : : Uint128 bit_mask = (i >= 64) ? Uint128{1ULL << (i - 64), 0} : Uint128{0, 1ULL << i};
194 : :
195 : : if ((dividend & bit_mask) != zero) {
196 : : remainder |= Uint128{1};
197 : : }
198 : :
199 : : if (remainder >= divisor) {
200 : : remainder -= divisor;
201 : : quotient |= bit_mask;
202 : : }
203 : : }
204 : :
205 : : return {quotient, remainder};
206 : : #endif
207 : : }
208 : :
209 : : } // namespace vlink
210 : :
211 : : namespace std {
212 : 6 : size_t hash<vlink::Uint128>::operator()(const vlink::Uint128& value) const noexcept {
213 : 6 : uint64_t h = value.get_high();
214 : 6 : uint64_t l = value.get_low();
215 : :
216 : 6 : h ^= l;
217 : 6 : h ^= h >> 33;
218 : 6 : h *= 0xff51afd7ed558ccdULL;
219 : 6 : h ^= h >> 33;
220 : 6 : h *= 0xc4ceb9fe1a85ec53ULL;
221 : 6 : h ^= h >> 33;
222 : :
223 : 6 : return static_cast<size_t>(h);
224 : : }
225 : : } // namespace std
|
