23#ifndef __LMMP_LONGLONG_H__
24#define __LMMP_LONGLONG_H__
26#if defined(LMMP_ASM_X64) && (defined(__GNUC__) || defined(__clang__))
32#if defined(__GNUC__) || defined(__clang__)
36#define ctz_shr_u64(r, x, cnt) \
38 unsigned long long _x_ = (x); \
39 (cnt) = __builtin_ctzll(_x_); \
45#define clz_shl_u64(r, x, cnt) \
47 unsigned long long _x_ = (x); \
48 (cnt) = __builtin_clzll(_x_); \
49 (r) = (unsigned long long)(_x_ << (cnt)); \
55#define ctz_shr_u64(r, x, cnt) \
59 while ((_x_ & 1) == 0) { \
69#define clz_shl_u64(r, x, cnt) \
73 while ((_x_ & 0x8000000000000000ULL) == 0) { \
82#if defined(__GNUC__) || defined(__clang__)
86#define ctz_shr_u32(r, x, cnt) \
88 unsigned int _x_ = (x); \
89 (cnt) = __builtin_ctz(_x_); \
95#define clz_shl_u32(r, x, cnt) \
97 unsigned int _x_ = (x); \
98 (cnt) = __builtin_clz(_x_); \
105#define ctz_shr_u32(r, x, cnt) \
107 uint32_t _x_ = (x); \
109 while ((_x_ & 1U) == 0) { \
119#define clz_shl_u32(r, x, cnt) \
121 uint32_t _x_ = (x); \
123 while ((_x_ & 0x80000000U) == 0) { \
132static inline void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high) {
133#if (defined(__GNUC__) || defined(__clang__))
134 __uint128_t
prod = (__uint128_t)a * b;
135 *low = (uint64_t)
prod;
136 *high = (uint64_t)(
prod >> 64);
138 uint64_t ah = a >> 32, bh = b >> 32;
139 a = (uint32_t)a, b = (uint32_t)b;
140 uint64_t
r0 = a * b,
r1 = a * bh,
r2 = ah * b,
r3 = ah * bh;
141 r3 += (
r1 >> 32) + (
r2 >> 32);
142 r1 = (uint32_t)
r1,
r2 = (uint32_t)
r2;
145 *high =
r3 + (
r1 >> 32);
146 *low = (
r1 << 32) | (uint32_t)
r0;
151#if (defined(__GNUC__) || defined(__clang__)) && defined(__SIZEOF_INT128__)
152 __uint128_t
t = (__uint128_t)a * (__uint128_t)b;
153 return (uint64_t)(
t >> 64);
155 uint64_t ah = a >> 32, bh = b >> 32;
156 a = (uint32_t)a, b = (uint32_t)b;
157 uint64_t
r0 = a * b,
r1 = a * bh,
r2 = ah * b,
r3 = ah * bh;
158 r3 += (
r1 >> 32) + (
r2 >> 32);
159 r1 = (uint32_t)
r1,
r2 = (uint32_t)
r2;
162 return r3 + (
r1 >> 32);
166static inline void _umul128to256_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4]) {
174#if defined(LMMP_ASM_X64) && defined(__GNUC__) && !defined(__clang__)
181 "movq %[al], %%rdx \n\t"
182 "mulxq %[bl], %[r0], %[r1] \n\t"
183 "xorq %[r2], %[r2] \n\t"
184 "xorq %[r3], %[r3] \n\t"
185 "mulxq %[bh], %%r8, %%r9 \n\t"
186 "movq %[ah], %%rdx \n\t"
187 "addq %%r8, %[r1] \n\t"
188 "adcxq %%r9, %[r2] \n\t"
189 "adcq $0, %[r3] \n\t"
190 "mulxq %[bl], %%r8, %%r9 \n\t"
191 "addq %%r8, %[r1] \n\t"
192 "adcxq %%r9, %[r2] \n\t"
193 "adcq $0, %[r3] \n\t"
194 "mulxq %[bh], %%r8, %%r9 \n\t"
195 "addq %%r8, %[r2] \n\t"
196 "adcxq %%r9, %[r3] \n\t"
198 : [ah]
"rm"(a_high), [al]
"rm"(a_low), [bh]
"rm"(b_high), [bl]
"rm"(b_low)
199 :
"cc",
"rdx",
"r8",
"r9");
204#elif defined(LMMP_ASM_X64) && defined(__clang__)
210 __uint128_t p00 = (__uint128_t)a_low * b_low;
211 __uint128_t p01 = (__uint128_t)a_low * b_high;
212 __uint128_t p10 = (__uint128_t)a_high * b_low;
213 __uint128_t p11 = (__uint128_t)a_high * b_high;
214 __uint128_t mid = p01 + p10;
215 __uint128_t cm = mid < p01;
216 __uint128_t l = (mid << 64) + p00;
217 __uint128_t cl = l < p00;
218 __uint128_t h = p11 + (mid >> 64) + cl + (cm << 64);
220 rr[1] = (uint64_t)(l >> 64);
222 rr[3] = (uint64_t)(h >> 64);
223#elif defined(LMMP_ASM_ARM64) && (defined(__GNUC__) || defined(__clang__))
230 uint64_t
r0,
r1,
r2,
r3, t4, t5, t6, t7;
232 "mul %[r0], %[al], %[bl] \n\t"
233 "umulh %[r1], %[al], %[bl] \n\t"
234 "mul %[r2], %[al], %[bh] \n\t"
235 "umulh %[r3], %[al], %[bh] \n\t"
236 "mul %[t4], %[ah], %[bl] \n\t"
237 "umulh %[t5], %[ah], %[bl] \n\t"
238 "mul %[t6], %[ah], %[bh] \n\t"
239 "umulh %[t7], %[ah], %[bh] \n\t"
240 "adds %[r2], %[r2], %[t4] \n\t"
241 "adcs %[r3], %[r3], %[t5] \n\t"
242 "adc %[t7], %[t7], xzr \n\t"
243 "adds %[r1], %[r1], %[r2] \n\t"
244 "adcs %[r2], %[t6], %[r3] \n\t"
245 "adc %[r3], %[t7], xzr \n\t"
247 [t4]
"=&r"(t4), [t5]
"=&r"(t5), [t6]
"=&r"(t6), [t7]
"=&r"(t7)
248 : [ah]
"r"(a_high), [al]
"r"(a_low), [bh]
"r"(b_high), [bl]
"r"(b_low)
257 uint64_t p1_low, p1_high;
258 uint64_t p2_low, p2_high;
264 uint64_t carry = (rr[1] < p1_low) ? 1 : 0;
266 carry += (rr[1] < p2_low) ? 1 : 0;
269 carry = (rr[2] < carry) ? 1 : 0;
271 carry += (rr[2] < p1_high) ? 1 : 0;
273 carry += (rr[2] < p2_high) ? 1 : 0;
279static inline void _usqr128to256_(uint64_t a_high, uint64_t a_low, uint64_t rr[4]) {
287#if defined(LMMP_ASM_X64) && defined(__GNUC__) && !defined(__clang__)
293 uint64_t p0l, t_l, t_h, p3l,
r1,
r2,
r3, z;
295 "movq %[al], %%rdx \n\t"
296 "mulxq %[al], %[p0l], %[r1] \n\t"
297 "mulxq %[ah], %[t_l], %[t_h] \n\t"
298 "movq %[ah], %%rdx \n\t"
299 "mulxq %[ah], %[p3l], %[r3] \n\t"
300 "movq %[t_h], %[r2] \n\t"
301 "shldq $1, %[t_l], %[r2] \n\t"
302 "shrq $63, %[t_h] \n\t"
303 "leaq (%[t_l], %[t_l]), %[t_l]\n\t"
304 "xorq %[z], %[z] \n\t"
305 "adcxq %[t_l], %[r1] \n\t"
306 "adoxq %[p3l], %[r2] \n\t"
307 "adcxq %[z], %[r2] \n\t"
308 "adoxq %[t_h], %[r3] \n\t"
309 "adcxq %[z], %[r3] \n\t"
310 : [p0l]
"=&r"(p0l), [t_l]
"=&r"(t_l), [t_h]
"=&r"(t_h), [p3l]
"=&r"(p3l),
311 [
r1]
"=&r"(
r1), [
r2]
"=&r"(
r2), [
r3]
"=&r"(
r3), [z]
"=&r"(z)
312 : [ah]
"rm"(a_high), [al]
"rm"(a_low)
318#elif defined(LMMP_ASM_X64) && defined(__clang__)
321 __uint128_t p0 = (__uint128_t)a_low * a_low;
322 __uint128_t m = (__uint128_t)a_low * a_high;
323 __uint128_t p1 = (__uint128_t)a_high * a_high;
324 __uint128_t ml = m << 1;
325 __uint128_t mh = m >> 127;
326 __uint128_t l = (ml << 64) + p0;
327 __uint128_t cl = l < p0;
328 __uint128_t h = p1 + (ml >> 64) + cl + (mh << 64);
330 rr[1] = (uint64_t)(l >> 64);
332 rr[3] = (uint64_t)(h >> 64);
333#elif defined(LMMP_ASM_ARM64) && (defined(__GNUC__) || defined(__clang__))
339 uint64_t
r0,
r1,
r2,
r3, t5, t6, t7;
341 "mul %[r0], %[al], %[al] \n\t"
342 "umulh %[r1], %[al], %[al] \n\t"
343 "mul %[r2], %[al], %[ah] \n\t"
344 "umulh %[r3], %[al], %[ah] \n\t"
345 "lsr %[t7], %[r3], 63 \n\t"
346 "extr %[r3], %[r3], %[r2], 63 \n\t"
347 "mul %[t5], %[ah], %[ah] \n\t"
348 "umulh %[t6], %[ah], %[ah] \n\t"
349 "adds %[r1], %[r1], %[r2], lsl 1 \n\t"
350 "adcs %[r2], %[t5], %[r3] \n\t"
351 "adc %[r3], %[t6], %[t7] \n\t"
353 [t5]
"=&r"(t5), [t6]
"=&r"(t6), [t7]
"=&r"(t7)
354 : [ah]
"r"(a_high), [al]
"r"(a_low)
361 uint64_t p1_low, p1_high;
365 rr[3] += p1_high >> 63;
366 p1_high = (p1_high << 1) | (p1_low >> 63);
369 uint64_t carry = (rr[1] < p1_low) ? 1 : 0;
372 carry = (rr[2] < carry) ? 1 : 0;
374 carry += (rr[2] < p1_high) ? 1 : 0;
381static inline __uint128_t
_umul128to128_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low) {
383 return (__uint128_t)a_low * b_low + ((__uint128_t)(uint64_t)(a_low * b_high + a_high * b_low) << 64);
386static inline uint64_t
_udiv128by64to64_(uint64_t numhi, uint64_t numlo, uint64_t den, uint64_t* r) {
387#if (defined(__GNUC__) || defined(__clang__)) && defined(LMMP_ASM_X64)
389 __asm__(
"div %[v]" :
"=a"(result),
"=d"(*r) : [v]
"r"(den),
"a"(numlo),
"d"(numhi));
392 const uint64_t b = ((uint64_t)1 << 32);
401 uint64_t den10 = den;
402 uint64_t num10 = numlo;
425 numhi |= (numlo >> (-shift & 63)) & (uint64_t)(-(int64_t)shift >> 63);
428 num1 = (uint32_t)(numlo >> 32);
429 num0 = (uint32_t)(numlo & 0xFFFFFFFFu);
430 den1 = (uint32_t)(den >> 32);
431 den0 = (uint32_t)(den & 0xFFFFFFFFu);
436 c2 = rhat * b + num1;
438 qhat -= (
c1 - c2 > den) ? 2 : 1;
441 rem = numhi * b + num1 - q1 * den;
446 c2 = rhat * b + num0;
448 qhat -= (
c1 - c2 > den) ? 2 : 1;
451 q = ((uint64_t)q1 << 32) | q0;
454 *r = num10 - q * den10;
472#if defined(__SIZEOF_INT128__)
474typedef __uint128_t u128;
477#define _u128low(x) ((uint64_t)(x))
479#define _u128high(x) ((uint64_t)((x) >> 64))
482static inline __uint128_t _u128load(
const uint64_t* p) {
483 return ((__uint128_t)p[1] << 64) | p[0];
486static inline void _u128store(uint64_t* p, __uint128_t x) {
488 p[1] = (uint64_t)(x >> 64);
492#error "u128 scalar helpers require __uint128_t (GCC/Clang 64-bit targets)"
495#define _add_ssaaaa(sh, sl, ah, al, bh, bl) \
499 (sh) = (ah) + (bh) + (_x_ < (al)); \
503#define _sub_ddmmss(sh, sl, ah, al, bh, bl) \
507 (sh) = (ah) - (bh) - ((al) < (bl)); \
512static inline void _umulhi128_sloppy_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[2]) {
513#if defined(LMMP_ASM_X64) && defined(__GNUC__) && !defined(__clang__)
516 uint64_t
r0,
r1,
s, u, j;
518 "movq %[ah], %%rdx \n\t"
519 "mulxq %[bl], %[j], %[u] \n\t"
520 "mulxq %[bh], %[r0], %[r1] \n\t"
521 "movq %[al], %%rdx \n\t"
522 "mulxq %[bh], %[j], %[s] \n\t"
523 "addq %[s], %[r0] \n\t"
524 "adcq $0, %[r1] \n\t"
525 "addq %[u], %[r0] \n\t"
526 "adcq $0, %[r1] \n\t"
527 : [
r0]
"=&r"(
r0), [
r1]
"=&r"(
r1), [
s]
"=&r"(
s), [u]
"=&r"(u), [j]
"=&r"(j)
528 : [ah]
"rm"(a_high), [al]
"rm"(a_low), [bh]
"rm"(b_high), [bl]
"rm"(b_low)
533 u128 r = (((u128)a_low * b_high) >> 64) + (((u128)a_high * b_low) >> 64) + (u128)a_high * b_high;
535 rr[1] = _u128high(r);
540static inline void _usqr128to192_(uint64_t a_high, uint64_t a_low, uint64_t rr[3]) {
541#if defined(LMMP_ASM_X64) && defined(__GNUC__) && !defined(__clang__)
543 uint64_t
r0,
r1,
r2, tl, th, j;
545 "movq %[al], %%rdx \n\t"
546 "mulxq %[al], %[r0], %[r1] \n\t"
547 "mulxq %[ah], %[tl], %[th] \n\t"
548 "movq %[ah], %%rdx \n\t"
549 "mulxq %[ah], %[r2], %[j] \n\t"
550 "addq %[tl], %[r1] \n\t"
551 "adcq %[th], %[r2] \n\t"
552 "addq %[tl], %[r1] \n\t"
553 "adcq %[th], %[r2] \n\t"
554 : [
r0]
"=&r"(
r0), [
r1]
"=&r"(
r1), [
r2]
"=&r"(
r2), [tl]
"=&r"(tl), [th]
"=&r"(th), [j]
"=&r"(j)
555 : [ah]
"rm"(a_high), [al]
"rm"(a_low)
561 u128 p0 = (u128)a_low * a_low;
562 u128
t = (u128)a_low * a_high;
563 u128 acc = ((u128)(a_high * a_high) << 64) | _u128high(p0);
565 rr[0] = _u128low(p0);
566 rr[1] = _u128low(acc);
567 rr[2] = _u128high(acc);
571static inline void _umullo128x64_(uint64_t a_high, uint64_t a_low, uint64_t b, uint64_t rr[2]) {
572#if defined(LMMP_ASM_X64) && defined(__GNUC__) && !defined(__clang__)
575 uint64_t
r0,
r1,
t, j;
577 "movq %[al], %%rdx \n\t"
578 "mulxq %[b], %[r0], %[r1] \n\t"
579 "movq %[ah], %%rdx \n\t"
580 "mulxq %[b], %[t], %[j] \n\t"
581 "addq %[t], %[r1] \n\t"
582 : [
r0]
"=&r"(
r0), [
r1]
"=&r"(
r1), [
t]
"=&r"(
t), [j]
"=&r"(j)
583 : [ah]
"rm"(a_high), [al]
"rm"(a_low), [b]
"rm"(b)
588 u128
t = (((u128)a_high << 64) | a_low) * b;
590 rr[1] = _u128high(
t);
596#define _udiv_qrnnd_preinv(q, r, nh, nl, d, di) \
598 __uint128_t _s_ = (__uint128_t)(mp_limb_t)(nh) * (mp_limb_t)(di); \
599 _s_ += ((__uint128_t)(mp_limb_t)((nh) + 1) << 64) | (mp_limb_t)(nl); \
600 mp_limb_t _qh_ = (mp_limb_t)(_s_ >> 64); \
601 mp_limb_t _ql_ = (mp_limb_t)_s_; \
602 mp_limb_t _r_ = (mp_limb_t)(nl) - _qh_ * (mp_limb_t)(d); \
603 mp_limb_t _mask_ = -(mp_limb_t)(_r_ > _ql_); \
605 _r_ += _mask_ & (mp_limb_t)(d); \
606 if (_r_ >= (mp_limb_t)(d)) { \
607 _r_ -= (mp_limb_t)(d); \
616static inline uint64_t
_bpow_step_(uint64_t nh, uint64_t m, uint64_t inv) {
617 __uint128_t
s = (__uint128_t)nh * inv + ((__uint128_t)(nh + 1) << 64);
618 uint64_t r = 0 - (uint64_t)(
s >> 64) * m;
619 uint64_t mask = -(uint64_t)(r > (uint64_t)
s);
626static inline uint64_t
_bpow_preinv_(uint64_t m, uint64_t
k,
int nb, uint64_t inv) {
634#define _udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv) \
636 mp_limb_t _t0_, _t1_, _mask_; \
637 __uint128_t _s_ = (__uint128_t)(mp_limb_t)(n2) * (mp_limb_t)(dinv); \
638 _s_ += ((__uint128_t)(mp_limb_t)(n2) << 64) | (mp_limb_t)(n1); \
639 mp_limb_t _q0_ = (mp_limb_t)_s_; \
640 (q) = (mp_limb_t)(_s_ >> 64); \
642 (r1) = (n1) - (d1) * (q); \
643 _sub_ddmmss((r1), (r0), (r1), (n0), (d1), (d0)); \
644 _umul64to128_((d0), (q), &_t0_, &_t1_); \
645 _sub_ddmmss((r1), (r0), (r1), (r0), _t1_, _t0_); \
648 _mask_ = -(uint64_t)((r1) >= _q0_); \
650 _add_ssaaaa((r1), (r0), (r1), (r0), _mask_ & (d1), _mask_ & (d0)); \
651 if ((r1) >= (d1)) { \
652 if ((r1) > (d1) || (r0) >= (d0)) { \
654 _sub_ddmmss((r1), (r0), (r1), (r0), (d1), (d0)); \
661#define _udiv32by32_q_preinv(q, n0, dinv) \
663 uint64_t _hi_, _lo_; \
664 _umul64to128_((n0), (dinv), &_lo_, &_hi_); \
672#define _U64_SHIFT_MASK 0x3F
673#define _ADD_MARKER 0x40
687 uint32_t floor_log_2_d = 63 - shift;
690 if ((d & (d - 1)) == 0) {
696 result.
more = (uint8_t)(floor_log_2_d - (branchfree != 0));
698 uint64_t proposed_m, rem;
703 const uint64_t e = d - rem;
706 if (!branchfree && e < ((uint64_t)1 << floor_log_2_d)) {
708 more = (uint8_t)floor_log_2_d;
715 proposed_m += proposed_m;
716 const uint64_t twice_rem = rem + rem;
717 if (twice_rem >= d || twice_rem < rem)
721 result.
magic = 1 + proposed_m;
742 uint64_t
t = ((numer - q) >> 1) + q;
743 return t >> denom->
more;
static uint64_t _bpow_preinv_(uint64_t m, uint64_t k, int nb, uint64_t inv)
static void _umulhi128_sloppy_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[2])
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)
#define _U64_SHIFT_MASK
from https://libdivide.com/
static _udiv64_t _udiv64_gen_internal_(uint64_t d, int branchfree)
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
static void _umul128to256_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4])
static uint64_t _bpow_step_(uint64_t nh, uint64_t m, uint64_t inv)
static void _umullo128x64_(uint64_t a_high, uint64_t a_low, uint64_t b, uint64_t rr[2])
static _udiv64_t _udiv64_gen(uint64_t d)
static uint64_t _udiv64by64_q_preinv(uint64_t numer, const _udiv64_t *denom)
static uint64_t _udiv128by64to64_(uint64_t numhi, uint64_t numlo, uint64_t den, uint64_t *r)
#define clz_shl_u64(r, x, cnt)
static void _usqr128to192_(uint64_t a_high, uint64_t a_low, uint64_t rr[3])
static __uint128_t _umul128to128_(uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low)
static void _usqr128to256_(uint64_t a_high, uint64_t a_low, uint64_t rr[4])