LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
longlong.h 文件参考
#include <stdint.h>
longlong.h 的引用(Include)关系图:
此图展示该文件被哪些文件直接或间接地引用了:

浏览该文件的源代码.

结构体

struct  _udiv64_t

宏定义

#define _ADD_MARKER   0x40
#define _add_ssaaaa(sh, sl, ah, al, bh, bl)
#define _sub_ddmmss(sh, sl, ah, al, bh, bl)
#define _U64_SHIFT_MASK   0x3F
 from https://libdivide.com/
#define _udiv32by32_q_preinv(q, n0, dinv)
#define _udiv_qr_3by2(q, r1, r0, n2, n1, n0, d1, d0, dinv)
#define _udiv_qrnnd_preinv(q, r, nh, nl, d, di)
#define clz_shl_u32(r, x, cnt)
#define clz_shl_u64(r, x, cnt)
#define ctz_shr_u32(r, x, cnt)
#define ctz_shr_u64(r, x, cnt)
 Copyright (C) 2026 HJimmyK (Jericho Knox)

类型定义

typedef struct _udiv64_t _udiv64_t

函数

static uint64_t _bpow_preinv_ (uint64_t m, uint64_t k, int nb, uint64_t inv)
static uint64_t _bpow_step_ (uint64_t nh, uint64_t m, uint64_t inv)
static uint64_t _udiv128by64to64_ (uint64_t numhi, uint64_t numlo, uint64_t den, uint64_t *r)
static _udiv64_t _udiv64_gen (uint64_t d)
static _udiv64_t _udiv64_gen_internal_ (uint64_t d, int branchfree)
static uint64_t _udiv64by64_q_preinv (uint64_t numer, const _udiv64_t *denom)
static __uint128_t _umul128to128_ (uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low)
static void _umul128to256_ (uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[4])
static void _umul64to128_ (uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
static uint64_t _umul64to64hi_ (uint64_t a, uint64_t b)
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 void _umullo128x64_ (uint64_t a_high, uint64_t a_low, uint64_t b, uint64_t rr[2])
static void _usqr128to192_ (uint64_t a_high, uint64_t a_low, uint64_t rr[3])
static void _usqr128to256_ (uint64_t a_high, uint64_t a_low, uint64_t rr[4])

结构体说明

◆ _udiv64_t

struct _udiv64_t

在文件 longlong.h 第 675 行定义.

_udiv64_t 的协作图:
成员变量
uint64_t magic
uint8_t more

宏定义说明

◆ _ADD_MARKER

#define _ADD_MARKER   0x40

在文件 longlong.h 第 673 行定义.

被这些函数引用 _udiv64_gen_internal_().

◆ _add_ssaaaa

#define _add_ssaaaa ( sh,
sl,
ah,
al,
bh,
bl )
值:
do { \
uint64_t _x_; \
_x_ = (al) + (bl); \
(sh) = (ah) + (bh) + (_x_ < (al)); \
(sl) = _x_; \
} while (0)

在文件 longlong.h 第 495 行定义.

被这些函数引用 ll_small_2_powmod(), lmmp_sqrt_3_() , 以及 lmmp_sqrt_4_().

◆ _sub_ddmmss

#define _sub_ddmmss ( sh,
sl,
ah,
al,
bh,
bl )
值:
do { \
uint64_t _x_; \
_x_ = (al) - (bl); \
(sh) = (ah) - (bh) - ((al) < (bl)); \
(sl) = _x_; \
} while (0)

在文件 longlong.h 第 503 行定义.

被这些函数引用 is2_notrial_i_(), ll_small_is_prime_mr(), ll_small_reduce2_precise(), ll_small_sqrmod(), ll_small_sqrmod_sloppy(), lmmp_sqrt_3_() , 以及 lmmp_sqrt_4_().

◆ _U64_SHIFT_MASK

#define _U64_SHIFT_MASK   0x3F

from https://libdivide.com/

在文件 longlong.h 第 672 行定义.

被这些函数引用 _udiv64_gen().

◆ _udiv32by32_q_preinv

#define _udiv32by32_q_preinv ( q,
n0,
dinv )
值:
do { \
uint64_t _hi_, _lo_; \
_umul64to128_((n0), (dinv), &_lo_, &_hi_); \
(q) = _hi_; \
} while (0)

在文件 longlong.h 第 661 行定义.

被这些函数引用 count_2facodd_factors(), count_factors(), count_factors() , 以及 count_factors().

◆ _udiv_qr_3by2

#define _udiv_qr_3by2 ( q,
r1,
r0,
n2,
n1,
n0,
d1,
d0,
dinv )
值:
do { \
mp_limb_t _t0_, _t1_, _mask_; \
__uint128_t _s_ = (__uint128_t)(mp_limb_t)(n2) * (mp_limb_t)(dinv); \
_s_ += ((__uint128_t)(mp_limb_t)(n2) << 64) | (mp_limb_t)(n1); \
mp_limb_t _q0_ = (mp_limb_t)_s_; \
(q) = (mp_limb_t)(_s_ >> 64); \
\
(r1) = (n1) - (d1) * (q); \
_sub_ddmmss((r1), (r0), (r1), (n0), (d1), (d0)); \
_umul64to128_((d0), (q), &_t0_, &_t1_); \
_sub_ddmmss((r1), (r0), (r1), (r0), _t1_, _t0_); \
(q)++; \
\
_mask_ = -(uint64_t)((r1) >= _q0_); \
(q) += _mask_; \
_add_ssaaaa((r1), (r0), (r1), (r0), _mask_ & (d1), _mask_ & (d0)); \
if ((r1) >= (d1)) { \
if ((r1) > (d1) || (r0) >= (d0)) { \
(q)++; \
_sub_ddmmss((r1), (r0), (r1), (r0), (d1), (d0)); \
} \
} \
} while (0)
uint64_t mp_limb_t
定义 lmmp.h:92
#define r1
#define r0

在文件 longlong.h 第 634 行定义.

被这些函数引用 ipn_sdiv_mul1_(), lmmp_div_2_(), lmmp_div_2_s_(), lmmp_div_3_2_(), lmmp_div_basecase_() , 以及 lmmp_mod_2_().

◆ _udiv_qrnnd_preinv

#define _udiv_qrnnd_preinv ( q,
r,
nh,
nl,
d,
di )
值:
do { \
__uint128_t _s_ = (__uint128_t)(mp_limb_t)(nh) * (mp_limb_t)(di); \
_s_ += ((__uint128_t)(mp_limb_t)((nh) + 1) << 64) | (mp_limb_t)(nl); \
mp_limb_t _qh_ = (mp_limb_t)(_s_ >> 64); \
mp_limb_t _ql_ = (mp_limb_t)_s_; \
mp_limb_t _r_ = (mp_limb_t)(nl) - _qh_ * (mp_limb_t)(d); \
mp_limb_t _mask_ = -(mp_limb_t)(_r_ > _ql_); \
_qh_ += _mask_; \
_r_ += _mask_ & (mp_limb_t)(d); \
if (_r_ >= (mp_limb_t)(d)) { \
_r_ -= (mp_limb_t)(d); \
_qh_++; \
} \
(r) = _r_; \
(q) = _qh_; \
} while (0)

在文件 longlong.h 第 596 行定义.

被这些函数引用 lmmp_div3_(), lmmp_div_1_(), lmmp_div_1_s_(), lmmp_mod_1_(), lmmp_mod_preinv_1_() , 以及 lmmp_mulmod_ulong_().

◆ clz_shl_u32

#define clz_shl_u32 ( r,
x,
cnt )
值:
do { \
uint32_t _x_ = (x); \
int _c_ = 0; \
while ((_x_ & 0x80000000U) == 0) { \
_c_++; \
_x_ <<= 1; \
} \
(cnt) = _c_; \
(r) = _x_; \
} while (0)

在文件 longlong.h 第 119 行定义.

◆ clz_shl_u64

#define clz_shl_u64 ( r,
x,
cnt )
值:
do { \
uint64_t _x_ = (x); \
int _c_ = 0; \
while ((_x_ & 0x8000000000000000ULL) == 0) { \
_c_++; \
_x_ <<= 1; \
} \
(cnt) = _c_; \
(r) = _x_; \
} while (0)

在文件 longlong.h 第 69 行定义.

被这些函数引用 _udiv128by64to64_(), _udiv64_gen_internal_(), mont_R2(), mont_R2() , 以及 trialdiv_init_chunk_().

◆ ctz_shr_u32

#define ctz_shr_u32 ( r,
x,
cnt )
值:
do { \
uint32_t _x_ = (x); \
int _i_ = 0; \
while ((_x_ & 1U) == 0) { \
_i_++; \
_x_ >>= 1; \
} \
cnt = _i_; \
(r) = _x_; \
} while (0)

在文件 longlong.h 第 105 行定义.

被这些函数引用 lmmp_odd_nPr_product_() , 以及 lmmp_odd_nPr_product_().

◆ ctz_shr_u64

#define ctz_shr_u64 ( r,
x,
cnt )
值:
do { \
uint64_t _x_ = (x); \
int _i_ = 0; \
while ((_x_ & 1) == 0) { \
_i_++; \
_x_ >>= 1; \
} \
cnt = _i_; \
(r) = _x_; \
} while (0)

Copyright (C) 2026 HJimmyK (Jericho Knox)

This file is part of LMMP.

LMMP is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public License along with this library. If not, see https://www.gnu.org/licenses/.

SPDX-License-Identifier: LGPL-3.0-or-later

在文件 longlong.h 第 55 行定义.

被这些函数引用 lmmp_arith_seqprod_(), lmmp_gcdext_derive_(), lmmp_is_prime_uint_notrial_(), lmmp_is_prime_ulong_notrial_(), lmmp_odd_nCr_uint_(), lmmp_odd_nCr_ushort_(), lmmp_odd_nPr_uint_(), lmmp_odd_nPr_ulong_(), lmmp_odd_nPr_ushort_(), lmmp_powlo_(), lmmp_powlo_1_(), lmmp_powlo_2_(), lmmp_powmod_1_(), lmmp_powmod_2_() , 以及 lmmp_powmod_odd_mont_().

类型定义说明

◆ _udiv64_t

typedef struct _udiv64_t _udiv64_t

函数说明

◆ _bpow_preinv_()

uint64_t _bpow_preinv_ ( uint64_t m,
uint64_t k,
int nb,
uint64_t inv )
inlinestatic

在文件 longlong.h 第 626 行定义.

626 {
627 uint64_t r = _bpow_step_((uint64_t)1 << k, m, inv);
628 if (nb >= 2) r = _bpow_step_(r, m, inv);
629 return r >> k;
630}
#define k
static uint64_t _bpow_step_(uint64_t nh, uint64_t m, uint64_t inv)

引用了 _bpow_preinv_(), _bpow_step_() , 以及 k.

被这些函数引用 _bpow_preinv_(), mont_R2(), mont_R2() , 以及 trialdiv_init_chunk_().

函数调用图:
这是这个函数的调用关系图:

◆ _bpow_step_()

uint64_t _bpow_step_ ( uint64_t nh,
uint64_t m,
uint64_t inv )
inlinestatic

在文件 longlong.h 第 616 行定义.

616 {
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);
620 r += mask & m;
621 if (r >= m) r -= m;
622 return r;
623}
#define s

引用了 _bpow_step_() , 以及 s.

被这些函数引用 _bpow_preinv_() , 以及 _bpow_step_().

函数调用图:
这是这个函数的调用关系图:

◆ _udiv128by64to64_()

uint64_t _udiv128by64to64_ ( uint64_t numhi,
uint64_t numlo,
uint64_t den,
uint64_t * r )
inlinestatic

在文件 longlong.h 第 386 行定义.

386 {
387#if (defined(__GNUC__) || defined(__clang__)) && defined(LMMP_ASM_X64)
388 uint64_t result;
389 __asm__("div %[v]" : "=a"(result), "=d"(*r) : [v] "r"(den), "a"(numlo), "d"(numhi));
390 return result;
391#else
392 const uint64_t b = ((uint64_t)1 << 32);
393
394 uint32_t q1;
395 uint32_t q0;
396
397 uint64_t q;
398
399 int shift;
400
401 uint64_t den10 = den;
402 uint64_t num10 = numlo;
403
404 uint32_t den1;
405 uint32_t den0;
406 uint32_t num1;
407 uint32_t num0;
408
409 uint64_t rem;
410
411 uint64_t qhat;
412 uint64_t rhat;
413
414 uint64_t c1;
415 uint64_t c2;
416
417 if (numhi >= den) {
418 if (r)
419 *r = ~0ull;
420 return ~0ull;
421 }
422
423 clz_shl_u64(den, den, shift);
424 numhi <<= shift;
425 numhi |= (numlo >> (-shift & 63)) & (uint64_t)(-(int64_t)shift >> 63);
426 numlo <<= shift;
427
428 num1 = (uint32_t)(numlo >> 32);
429 num0 = (uint32_t)(numlo & 0xFFFFFFFFu);
430 den1 = (uint32_t)(den >> 32);
431 den0 = (uint32_t)(den & 0xFFFFFFFFu);
432
433 qhat = numhi / den1;
434 rhat = numhi % den1;
435 c1 = qhat * den0;
436 c2 = rhat * b + num1;
437 if (c1 > c2)
438 qhat -= (c1 - c2 > den) ? 2 : 1;
439 q1 = (uint32_t)qhat;
440
441 rem = numhi * b + num1 - q1 * den;
442
443 qhat = rem / den1;
444 rhat = rem % den1;
445 c1 = qhat * den0;
446 c2 = rhat * b + num0;
447 if (c1 > c2)
448 qhat -= (c1 - c2 > den) ? 2 : 1;
449 q0 = (uint32_t)qhat;
450
451 q = ((uint64_t)q1 << 32) | q0;
452
453 if (r)
454 *r = num10 - q * den10;
455 return q;
456#endif
457}
#define clz_shl_u64(r, x, cnt)
#define c1

引用了 _udiv128by64to64_(), c1 , 以及 clz_shl_u64.

被这些函数引用 _udiv128by64to64_(), _udiv64_gen_internal_(), lmmp_powmod_1_(), lmmp_sqrt_3_() , 以及 lmmp_sqrt_4_().

函数调用图:
这是这个函数的调用关系图:

◆ _udiv64_gen()

_udiv64_t _udiv64_gen ( uint64_t d)
inlinestatic

在文件 longlong.h 第 734 行定义.

734 {
736 _udiv64_t ret = {tmp.magic, (uint8_t)(tmp.more & _U64_SHIFT_MASK)};
737 return ret;
738}
#define _U64_SHIFT_MASK
from https://libdivide.com/
static _udiv64_t _udiv64_gen_internal_(uint64_t d, int branchfree)
#define tmp

引用了 _U64_SHIFT_MASK, _udiv64_gen(), _udiv64_gen_internal_() , 以及 tmp.

被这些函数引用 _udiv64_gen() , 以及 lmmp_powmod_uint_odd_().

函数调用图:
这是这个函数的调用关系图:

◆ _udiv64_gen_internal_()

_udiv64_t _udiv64_gen_internal_ ( uint64_t d,
int branchfree )
inlinestatic

在文件 longlong.h 第 681 行定义.

681 {
682 _udiv64_t result;
683 int shift;
684 uint64_t t;
685 clz_shl_u64(t, d, shift);
686 (void)t;
687 uint32_t floor_log_2_d = 63 - shift;
688
689 // Power of 2
690 if ((d & (d - 1)) == 0) {
691 // We need to subtract 1 from the shift value in case of an unsigned
692 // branchfree divider because there is a hardcoded right shift by 1
693 // in its division algorithm. Because of this we also need to add back
694 // 1 in its recovery algorithm.
695 result.magic = 0;
696 result.more = (uint8_t)(floor_log_2_d - (branchfree != 0));
697 } else {
698 uint64_t proposed_m, rem;
699 uint8_t more;
700 // (1 << (64 + floor_log_2_d)) / d
701 proposed_m = _udiv128by64to64_((uint64_t)1 << floor_log_2_d, 0, d, &rem);
702
703 const uint64_t e = d - rem;
704
705 // This power works if e < 2**floor_log_2_d.
706 if (!branchfree && e < ((uint64_t)1 << floor_log_2_d)) {
707 // This power works
708 more = (uint8_t)floor_log_2_d;
709 } else {
710 // We have to use the general 65-bit algorithm. We need to compute
711 // (2**power) / d. However, we already have (2**(power-1))/d and
712 // its remainder. By doubling both, and then correcting the
713 // remainder, we can compute the larger division.
714 // don't care about overflow here - in fact, we expect it
715 proposed_m += proposed_m;
716 const uint64_t twice_rem = rem + rem;
717 if (twice_rem >= d || twice_rem < rem)
718 proposed_m += 1;
719 more = (uint8_t)(floor_log_2_d | _ADD_MARKER);
720 }
721 result.magic = 1 + proposed_m;
722 result.more = more;
723 // result.more's shift should in general be ceil_log_2_d. But if we
724 // used the smaller power, we subtract one from the shift because we're
725 // using the smaller power. If we're using the larger power, we
726 // subtract one from the shift because it's taken care of by the add
727 // indicator. So floor_log_2_d happens to be correct in both cases,
728 // which is why we do it outside of the if statement.
729 }
730 return result;
731}
#define _ADD_MARKER
static uint64_t _udiv128by64to64_(uint64_t numhi, uint64_t numlo, uint64_t den, uint64_t *r)
uint64_t magic
#define t

引用了 _ADD_MARKER, _udiv128by64to64_(), _udiv64_gen_internal_(), clz_shl_u64, _udiv64_t::magic, _udiv64_t::more , 以及 t.

被这些函数引用 _udiv64_gen() , 以及 _udiv64_gen_internal_().

函数调用图:
这是这个函数的调用关系图:

◆ _udiv64by64_q_preinv()

uint64_t _udiv64by64_q_preinv ( uint64_t numer,
const _udiv64_t * denom )
inlinestatic

在文件 longlong.h 第 740 行定义.

740 {
741 uint64_t q = _umul64to64hi_(numer, denom->magic);
742 uint64_t t = ((numer - q) >> 1) + q;
743 return t >> denom->more;
744}
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)

引用了 _udiv64by64_q_preinv(), _umul64to64hi_(), _udiv64_t::magic, _udiv64_t::more , 以及 t.

被这些函数引用 _udiv64by64_q_preinv() , 以及 lmmp_powmod_uint_odd_().

函数调用图:
这是这个函数的调用关系图:

◆ _umul128to128_()

__uint128_t _umul128to128_ ( uint64_t a_high,
uint64_t a_low,
uint64_t b_high,
uint64_t b_low )
inlinestatic

在文件 longlong.h 第 381 行定义.

381 {
382 // al*bh + ah*bl 的 64 位回绕和恰为交叉贡献的可见部分
383 return (__uint128_t)a_low * b_low + ((__uint128_t)(uint64_t)(a_low * b_high + a_high * b_low) << 64);
384}

引用了 _umul128to128_().

被这些函数引用 _umul128to128_(), ll_small_sqrmod_sloppy(), lmmp_binvert_4_(), lmmp_binvert_unbalance_2_(), lmmp_divexact_2_(), lmmp_is_prime_2_() , 以及 lmmp_powlo_2_().

函数调用图:
这是这个函数的调用关系图:

◆ _umul128to256_()

void _umul128to256_ ( uint64_t a_high,
uint64_t a_low,
uint64_t b_high,
uint64_t b_low,
uint64_t rr[4] )
inlinestatic

在文件 longlong.h 第 166 行定义.

166 {
167 /*
168 | res0 | res1 | res2 | res3 |
169 | p0l | p0h | | |
170 | p1l | p1h | |
171 | p2l | p2h | |
172 | | p3l | p3h |
173 */
174#if defined(LMMP_ASM_X64) && defined(__GNUC__) && !defined(__clang__)
175 /* 4×mulx + 运行累加:p1/p2/p3 依次流入 r8/r9 暂存(以 clobber 声明,
176 乱序重命名消除 WAR),每个部分积以 add/adcx/adc 三连加进累加器
177 (进位至多 1,res3 侧经 adc $0 传播)。相对九输出分解式,asm
178 边界同时保活的寄存器由 9 输出 + rdx 压缩为 4 输出 + r8/r9/rdx */
179 uint64_t r0, r1, r2, r3;
180 __asm__(
181 "movq %[al], %%rdx \n\t"
182 "mulxq %[bl], %[r0], %[r1] \n\t" // p0 = al*bl
183 "xorq %[r2], %[r2] \n\t"
184 "xorq %[r3], %[r3] \n\t"
185 "mulxq %[bh], %%r8, %%r9 \n\t" // p1 = al*bh
186 "movq %[ah], %%rdx \n\t"
187 "addq %%r8, %[r1] \n\t" // res1 += p1l
188 "adcxq %%r9, %[r2] \n\t" // res2 += p1h + c
189 "adcq $0, %[r3] \n\t"
190 "mulxq %[bl], %%r8, %%r9 \n\t" // p2 = ah*bl
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" // p3 = ah*bh
195 "addq %%r8, %[r2] \n\t" // res2 += p3l
196 "adcxq %%r9, %[r3] \n\t" // res3 += p3h + c
197 : [r0] "=&r"(r0), [r1] "=&r"(r1), [r2] "=&r"(r2), [r3] "=&r"(r3)
198 : [ah] "rm"(a_high), [al] "rm"(a_low), [bh] "rm"(b_high), [bl] "rm"(b_low)
199 : "cc", "rdx", "r8", "r9");
200 rr[0] = r0;
201 rr[1] = r1;
202 rr[2] = r2;
203 rr[3] = r3;
204#elif defined(LMMP_ASM_X64) && defined(__clang__)
205 /* clang-x64 组合式:clang 的 mulhi 识别/进位融合/双移位合并把本
206 形态编成与手写 asm 同构体且无块边界税(asm 块输出强制驻活使
207 栈流量×3、调度冻结,探针 ladder 慢 1.7×);GCC 无此融合(组合
208 式朴素展开 30+ 条指令),x64-GCC 走上方 asm。位置在 u128
209 typedef 之前,此处直接用 __uint128_t */
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; /* 129 位交叉和进位,属 hi 的第 64 位 */
216 __uint128_t l = (mid << 64) + p00;
217 __uint128_t cl = l < p00; /* 进位属 hi 的第 0 位 */
218 __uint128_t h = p11 + (mid >> 64) + cl + (cm << 64);
219 rr[0] = (uint64_t)l;
220 rr[1] = (uint64_t)(l >> 64);
221 rr[2] = (uint64_t)h;
222 rr[3] = (uint64_t)(h >> 64);
223#elif defined(LMMP_ASM_ARM64) && (defined(__GNUC__) || defined(__clang__))
224 /* 8×(mul|umulh) + adds/adcs 标志链收尾,共 14 条:C 语句间无法保活
225 NZCV 进位,纯 C 形态最少 21 条(进位须 cset 物化)。关键次序:
226 p11h 在 CF=tc(交叉和 129 位顶)后立即 adc xzr 吸收进位(免 cset
227 与额外寄存器),随后 r1/r2/r3 三连以 adds/adcs/adc 单进位链收拢
228 (列和第三项恒 <=1,进位至多 1)。r1/r2 输出寄存器兼作交叉积
229 暂存(写终值前死亡),边界足迹 4 输出 + 4 暂存。 */
230 uint64_t r0, r1, r2, r3, t4, t5, t6, t7;
231 __asm__(
232 "mul %[r0], %[al], %[bl] \n\t" /* p00l -> r0 终值 */
233 "umulh %[r1], %[al], %[bl] \n\t" /* p00h */
234 "mul %[r2], %[al], %[bh] \n\t" /* p01l */
235 "umulh %[r3], %[al], %[bh] \n\t" /* p01h */
236 "mul %[t4], %[ah], %[bl] \n\t" /* p10l */
237 "umulh %[t5], %[ah], %[bl] \n\t" /* p10h */
238 "mul %[t6], %[ah], %[bh] \n\t" /* p11l */
239 "umulh %[t7], %[ah], %[bh] \n\t" /* p11h */
240 "adds %[r2], %[r2], %[t4] \n\t" /* tl = p01l+p10l, CF=tc0 */
241 "adcs %[r3], %[r3], %[t5] \n\t" /* th = p01h+p10h+tc0, CF=tc */
242 "adc %[t7], %[t7], xzr \n\t" /* p11h += tc(立即吃 CF) */
243 "adds %[r1], %[r1], %[r2] \n\t" /* r1 = p00h+tl, CF=c1 */
244 "adcs %[r2], %[t6], %[r3] \n\t" /* r2 = p11l+th+c1, CF=ch */
245 "adc %[r3], %[t7], xzr \n\t" /* r3 = p11h+tc+ch */
246 : [r0] "=&r"(r0), [r1] "=&r"(r1), [r2] "=&r"(r2), [r3] "=&r"(r3),
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)
249 : "cc");
250 rr[0] = r0;
251 rr[1] = r1;
252 rr[2] = r2;
253 rr[3] = r3;
254#else
255 /* 纯 C 路径:__uint128_t 组合写法在 GCC 下生成代码反而劣于显式
256 limb 进位链(128 位中间值引发寄存器溢出与额外 mov),保留朴素结构。 */
257 uint64_t p1_low, p1_high; // p1 = a_low × b_high
258 uint64_t p2_low, p2_high; // p2 = a_high × b_low
259 _umul64to128_(a_low, b_low, rr, rr + 1);
260 _umul64to128_(a_low, b_high, &p1_low, &p1_high);
261 _umul64to128_(a_high, b_low, &p2_low, &p2_high);
262 _umul64to128_(a_high, b_high, rr + 2, rr + 3);
263 rr[1] += p1_low;
264 uint64_t carry = (rr[1] < p1_low) ? 1 : 0;
265 rr[1] += p2_low;
266 carry += (rr[1] < p2_low) ? 1 : 0;
267
268 rr[2] += carry;
269 carry = (rr[2] < carry) ? 1 : 0;
270 rr[2] += p1_high;
271 carry += (rr[2] < p1_high) ? 1 : 0;
272 rr[2] += p2_high;
273 carry += (rr[2] < p2_high) ? 1 : 0;
274
275 rr[3] += carry;
276#endif
277}
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
#define r2
#define r3

引用了 _umul128to256_(), _umul64to128_(), r0, r1, r2 , 以及 r3.

被这些函数引用 _umul128to256_(), exp2_fixed_128(), lmmp_binvert_4_(), lmmp_binvert_unbalance_2_(), lmmp_divexact_2_(), log2_fixed_128(), mul_128() , 以及 mul_128().

函数调用图:
这是这个函数的调用关系图:

◆ _umul64to128_()

void _umul64to128_ ( uint64_t a,
uint64_t b,
uint64_t * low,
uint64_t * high )
inlinestatic

在文件 longlong.h 第 132 行定义.

132 {
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);
137#else
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;
143 r1 += r2;
144 r1 += (r0 >> 32);
145 *high = r3 + (r1 >> 32);
146 *low = (r1 << 32) | (uint32_t)r0;
147#endif
148}
#define prod

引用了 _umul64to128_(), prod, r0, r1, r2 , 以及 r3.

被这些函数引用 _umul128to192_(), _umul128to256_(), _umul64to128_(), _usqr128to256_(), exp2_fixed_64(), lmmp_binvert_2_(), lmmp_binvert_4_(), lmmp_binvert_unbalance_1_(), lmmp_divexact_1_(), lmmp_divexact_basecase_(), lmmp_divexact_odd_pi_(), lmmp_hgcd_lehmer2_(), lmmp_hgcd_matrix_mul_u_(), lmmp_hgcd_step_(), lmmp_inv_2_1_(), lmmp_mont_redc_bc_(), log2_fixed_64() , 以及 pcg64_128_action().

函数调用图:
这是这个函数的调用关系图:

◆ _umul64to64hi_()

uint64_t _umul64to64hi_ ( uint64_t a,
uint64_t b )
inlinestatic

在文件 longlong.h 第 150 行定义.

150 {
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);
154#else
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;
160 r1 += r2;
161 r1 += (r0 >> 32);
162 return r3 + (r1 >> 32);
163#endif
164}

引用了 _umul64to64hi_(), r0, r1, r2, r3 , 以及 t.

被这些函数引用 _udiv64by64_q_preinv(), _umul64to64hi_(), exp2_fixed_64(), ll_small_reduce2_precise(), lmmp_divexact_basecase_(), lmmp_mont_init_(), log2_fixed_64() , 以及 urem32_preinv().

函数调用图:
这是这个函数的调用关系图:

◆ _umulhi128_sloppy_()

void _umulhi128_sloppy_ ( uint64_t a_high,
uint64_t a_low,
uint64_t b_high,
uint64_t b_low,
uint64_t rr[2] )
inlinestatic

在文件 longlong.h 第 512 行定义.

512 {
513#if defined(LMMP_ASM_X64) && defined(__GNUC__) && !defined(__clang__)
514 /* 3×mulx + 2×(add/adc):交叉积取高 limb 只需 mulx 高输出,低输出
515 写入同一废弃寄存器 */
516 uint64_t r0, r1, s, u, j;
517 __asm__(
518 "movq %[ah], %%rdx \n\t"
519 "mulxq %[bl], %[j], %[u] \n\t" // u = hi(a1*b0)
520 "mulxq %[bh], %[r0], %[r1] \n\t" // a1*b1, rdx = a1
521 "movq %[al], %%rdx \n\t"
522 "mulxq %[bh], %[j], %[s] \n\t" // s = hi(a0*b1)
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)
529 : "cc", "rdx");
530 rr[0] = r0;
531 rr[1] = r1;
532#else
533 u128 r = (((u128)a_low * b_high) >> 64) + (((u128)a_high * b_low) >> 64) + (u128)a_high * b_high;
534 rr[0] = _u128low(r);
535 rr[1] = _u128high(r);
536#endif
537}

引用了 _umulhi128_sloppy_(), r0, r1 , 以及 s.

被这些函数引用 _umulhi128_sloppy_() , 以及 ll_small_sqrmod_sloppy().

函数调用图:
这是这个函数的调用关系图:

◆ _umullo128x64_()

void _umullo128x64_ ( uint64_t a_high,
uint64_t a_low,
uint64_t b,
uint64_t rr[2] )
inlinestatic

在文件 longlong.h 第 571 行定义.

571 {
572#if defined(LMMP_ASM_X64) && defined(__GNUC__) && !defined(__clang__)
573 /* 2×mulx;a1*b 高 limb 丢弃即截断语义。p1 低输出与 p0 高 limb
574 分属寄存器后一条 add 合并 */
575 uint64_t r0, r1, t, j;
576 __asm__(
577 "movq %[al], %%rdx \n\t"
578 "mulxq %[b], %[r0], %[r1] \n\t" // p0 = a0*b
579 "movq %[ah], %%rdx \n\t"
580 "mulxq %[b], %[t], %[j] \n\t" // p1 = a1*b(高 limb j 废弃)
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)
584 : "cc", "rdx");
585 rr[0] = r0;
586 rr[1] = r1;
587#else
588 u128 t = (((u128)a_high << 64) | a_low) * b;
589 rr[0] = _u128low(t);
590 rr[1] = _u128high(t);
591#endif
592}

引用了 _umullo128x64_(), r0, r1 , 以及 t.

被这些函数引用 _umullo128x64_(), ll_small_mul1_() , 以及 ll_small_reduce2_precise().

函数调用图:
这是这个函数的调用关系图:

◆ _usqr128to192_()

void _usqr128to192_ ( uint64_t a_high,
uint64_t a_low,
uint64_t rr[3] )
inlinestatic

在文件 longlong.h 第 540 行定义.

540 {
541#if defined(LMMP_ASM_X64) && defined(__GNUC__) && !defined(__clang__)
542 /* 3×mulx;a1^2 高输出契约下为 0,写入废弃寄存器 */
543 uint64_t r0, r1, r2, tl, th, j;
544 __asm__(
545 "movq %[al], %%rdx \n\t"
546 "mulxq %[al], %[r0], %[r1] \n\t" // p0 = a0^2
547 "mulxq %[ah], %[tl], %[th] \n\t" // t = a0*a1
548 "movq %[ah], %%rdx \n\t"
549 "mulxq %[ah], %[r2], %[j] \n\t" // a1^2 低 limb(高 limb 契约为 0)
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)
556 : "cc", "rdx");
557 rr[0] = r0;
558 rr[1] = r1;
559 rr[2] = r2;
560#else
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);
564 acc = acc + t + t;
565 rr[0] = _u128low(p0);
566 rr[1] = _u128low(acc);
567 rr[2] = _u128high(acc);
568#endif
569}

引用了 _usqr128to192_(), r0, r1, r2 , 以及 t.

被这些函数引用 _usqr128to192_() , 以及 ll_small_sqrmod_sloppy().

函数调用图:
这是这个函数的调用关系图:

◆ _usqr128to256_()

void _usqr128to256_ ( uint64_t a_high,
uint64_t a_low,
uint64_t rr[4] )
inlinestatic

在文件 longlong.h 第 279 行定义.

279 {
280 /*
281 | res0 | res1 | res2 | res3 |
282 | p0l | p0h | | |
283 | p1l | p1h | |
284 | p1l | p1h | |
285 | | p3l | p3h |
286 */
287#if defined(LMMP_ASM_X64) && defined(__GNUC__) && !defined(__clang__)
288 /* 3×mulx;交叉积 p1 左移一位成为 129 位(v 为溢出位),
289 shld 一条完成高位拼接,adcx/adox 双链吸收 v 与两段进位。
290 res2 的两次加法(+p3l、+c1)各自至多产生一个进位且不会同时
291 产生,分别落在 OF 与 CF,故链尾须以 adox、adcx 各一条收拢,
292 缺一会导致 res2 恰为 2^64-1 再加 c1 时进位丢失(res3 少 1)。 */
293 uint64_t p0l, t_l, t_h, p3l, r1, r2, r3, z;
294 __asm__(
295 "movq %[al], %%rdx \n\t"
296 "mulxq %[al], %[p0l], %[r1] \n\t" // p0 = al*al, r1 = p0h
297 "mulxq %[ah], %[t_l], %[t_h] \n\t" // t = al*ah
298 "movq %[ah], %%rdx \n\t"
299 "mulxq %[ah], %[p3l], %[r3] \n\t" // p3 = ah*ah, r3 = p3h
300 "movq %[t_h], %[r2] \n\t"
301 "shldq $1, %[t_l], %[r2] \n\t" // r2 = t_h<<1 | t_l>>63
302 "shrq $63, %[t_h] \n\t" // t_h = v(129 位溢出,属于 res3 段)
303 "leaq (%[t_l], %[t_l]), %[t_l]\n\t" // t_l = 2*al*ah 低 64 位(lea 不动标志)
304 "xorq %[z], %[z] \n\t" // CF = OF = 0(须在移位类指令之后)
305 "adcxq %[t_l], %[r1] \n\t" // r1 = p0h + t_l, CF = res2 进位
306 "adoxq %[p3l], %[r2] \n\t" // r2 += p3l, OF = res3 进位
307 "adcxq %[z], %[r2] \n\t" // r2 += CF = res2
308 "adoxq %[t_h], %[r3] \n\t" // r3 += v + OF
309 "adcxq %[z], %[r3] \n\t" // r3 += CF = res3(收拢 res2 的 c1 进位)
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)
313 : "cc", "rdx");
314 rr[0] = p0l;
315 rr[1] = r1;
316 rr[2] = r2;
317 rr[3] = r3;
318#elif defined(LMMP_ASM_X64) && defined(__clang__)
319 /* clang-x64 组合式(同 _umul128to256_ 分支依据):交叉积单次
320 乘法后整体加倍,129 位进位经 m >> 127 顶位提取 */
321 __uint128_t p0 = (__uint128_t)a_low * a_low;
322 __uint128_t m = (__uint128_t)a_low * a_high; /* 交叉积,加倍后 129 位 */
323 __uint128_t p1 = (__uint128_t)a_high * a_high;
324 __uint128_t ml = m << 1;
325 __uint128_t mh = m >> 127; /* 加倍进位(0/1),属 hi 的第 64 位 */
326 __uint128_t l = (ml << 64) + p0;
327 __uint128_t cl = l < p0;
328 __uint128_t h = p1 + (ml >> 64) + cl + (mh << 64);
329 rr[0] = (uint64_t)l;
330 rr[1] = (uint64_t)(l >> 64);
331 rr[2] = (uint64_t)h;
332 rr[3] = (uint64_t)(h >> 64);
333#elif defined(LMMP_ASM_ARM64) && (defined(__GNUC__) || defined(__clang__))
334 /* 6×(mul|umulh) + lsr/extr 拆交叉积加倍 + 三连标志链,共 11 条。
335 加倍的 129 位拆法:tc = 交叉 hi >> 63(顶位,属 res3 段),
336 extr 一条取 (hi:lo)>>63 即加倍后的 res2 段,低 limb 以
337 adds 的 lsl #1 移位操作数直接并入 p0h(移出的位已由 extr 收取)。
338 tc 以寄存器进入收尾 adc(CF 链被 r1 的 adds 重置,不可滞留标志)。 */
339 uint64_t r0, r1, r2, r3, t5, t6, t7;
340 __asm__(
341 "mul %[r0], %[al], %[al] \n\t" /* p0l -> r0 终值 */
342 "umulh %[r1], %[al], %[al] \n\t" /* p0h */
343 "mul %[r2], %[al], %[ah] \n\t" /* 交叉 lo */
344 "umulh %[r3], %[al], %[ah] \n\t" /* 交叉 hi */
345 "lsr %[t7], %[r3], 63 \n\t" /* tc = 加倍后第 129 位 */
346 "extr %[r3], %[r3], %[r2], 63 \n\t" /* th2 = (交叉hi:交叉lo)>>63 */
347 "mul %[t5], %[ah], %[ah] \n\t" /* p1l */
348 "umulh %[t6], %[ah], %[ah] \n\t" /* p1h */
349 "adds %[r1], %[r1], %[r2], lsl 1 \n\t" /* r1 = p0h+2*交叉lo, CF=c1 */
350 "adcs %[r2], %[t5], %[r3] \n\t" /* r2 = p1l+th2+c1, CF=ch */
351 "adc %[r3], %[t6], %[t7] \n\t" /* r3 = p1h+tc+ch */
352 : [r0] "=&r"(r0), [r1] "=&r"(r1), [r2] "=&r"(r2), [r3] "=&r"(r3),
353 [t5] "=&r"(t5), [t6] "=&r"(t6), [t7] "=&r"(t7)
354 : [ah] "r"(a_high), [al] "r"(a_low)
355 : "cc");
356 rr[0] = r0;
357 rr[1] = r1;
358 rr[2] = r2;
359 rr[3] = r3;
360#else
361 uint64_t p1_low, p1_high; // p1 = a_low × a_high
362 _umul64to128_(a_low, a_low, rr, rr + 1);
363 _umul64to128_(a_low, a_high, &p1_low, &p1_high);
364 _umul64to128_(a_high, a_high, rr + 2, rr + 3);
365 rr[3] += p1_high >> 63;
366 p1_high = (p1_high << 1) | (p1_low >> 63);
367 p1_low <<= 1;
368 rr[1] += p1_low;
369 uint64_t carry = (rr[1] < p1_low) ? 1 : 0;
370
371 rr[2] += carry;
372 carry = (rr[2] < carry) ? 1 : 0;
373 rr[2] += p1_high;
374 carry += (rr[2] < p1_high) ? 1 : 0;
375
376 rr[3] += carry;
377#endif
378}

引用了 _umul64to128_(), _usqr128to256_(), r0, r1, r2 , 以及 r3.

被这些函数引用 _usqr128to256_(), exp2_fixed_128(), log2_fixed_128(), log2_fixed_64(), sqr_128() , 以及 sqr_128().

函数调用图:
这是这个函数的调用关系图: