LAMMP 4.1.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 _mont64_add(r, x, y, mod2)
 
#define _mont64_mul(r, x, y, mod, modInvNeg)
 
#define _mont64_mulinto(x, y, mod, modInvNeg)
 
#define _mont64_norm2(r, x, mod2)
 
#define _mont64_sub(r, x, y, mod2)
 
#define _mont64_toint(x, mod, modInvneg)
 
#define _mont64_tomont(x, r2, mod, modInvNeg)
 
#define _raw64_add(r, x, y)
 
#define _raw64_sub(r, x, y, mod2)
 
#define _sub_ddmmss(sh, sl, ah, al, bh, bl)
 
#define _u128add(r, x, y)
 
#define _u128add64(r, x, _i64)
 
#define _u128cmp(x, y)   ((x)[1] < (y)[1] || ((x)[1] == (y)[1] && (x)[0] < (y)[0]))
 
#define _u128high(x)   (*((x) + 1))
 
#define _u128low(x)   (*(x))
 
#define _u128lshl(x, y, n)
 
#define _u128lshr(x, y, n)
 
#define _u128mul(r, x, y)   _umul64to128_((x), (y), (r), (((r) + 1)))
 
#define _u128sub(r, x, y)
 
#define _u128sub64(r, x, _i64)
 
#define _u128x64to192(i192, i128, i64)
 
#define _u192add(i192, j192)
 
#define _u192sub(i192, j192)
 
#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 ctz_shl(r, x, cnt)
 

类型定义

typedef struct _udiv64_t _udiv64_t
 
typedef uint64_t u128[2]
 请注意，此处的蒙哥马利域的R为2^64，p不可超过2^63-1
 
typedef uint64_t u192[3]
 

函数

static int32_t _clz_u64_ (uint64_t val)
 
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 void _umul128to128_ (uint64_t a_high, uint64_t a_low, uint64_t b_high, uint64_t b_low, uint64_t rr[2])
 
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 _umulx64to128_ (uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
 

结构体说明

◆ _udiv64_t

struct _udiv64_t

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

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

宏定义说明

◆ _ADD_MARKER

#define _ADD_MARKER   0x40

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

◆ _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 第 408 行定义.

409 { \
410 uint64_t _x_; \
411 _x_ = (al) + (bl); \
412 (sh) = (ah) + (bh) + (_x_ < (al)); \
413 (sl) = _x_; \
414 } while (0)

◆ _mont64_add

#define _mont64_add (   r,
  x,
  y,
  mod2 
)
值:
do { \
(r) = (x) + (y); \
(r) = ((r) < (mod2)) ? (r) : ((r) - (mod2)); \
} while (0)

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

292 { \
293 (r) = (x) + (y); \
294 (r) = ((r) < (mod2)) ? (r) : ((r) - (mod2)); \
295 } while (0)

◆ _mont64_mul

#define _mont64_mul (   r,
  x,
  y,
  mod,
  modInvNeg 
)
值:
do { \
u128 _tmp1_ = {0, 0}; \
_u128mul(_tmp1_, (x), (y)); \
u128 _tmp2_ = {0, 0}; \
(*_tmp2_) = (*(_tmp1_)) * (modInvNeg); \
_u128mul(_tmp2_, (*(_tmp2_)), (mod)); \
_u128add(_tmp2_, _tmp2_, _tmp1_); \
(r) = (*(_tmp2_ + 1)); \
} while (0)
u128
uint64_t u128[2]
请注意，此处的蒙哥马利域的R为2^64，p不可超过2^63-1
Definition longlong.h:241

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

325 { \
326 u128 _tmp1_ = {0, 0}; \
327 _u128mul(_tmp1_, (x), (y)); \
328 u128 _tmp2_ = {0, 0}; \
329 (*_tmp2_) = (*(_tmp1_)) * (modInvNeg); \
330 _u128mul(_tmp2_, (*(_tmp2_)), (mod)); \
331 _u128add(_tmp2_, _tmp2_, _tmp1_); \
332 (r) = (*(_tmp2_ + 1)); \
333 } while (0)

◆ _mont64_mulinto

#define _mont64_mulinto (   x,
  y,
  mod,
  modInvNeg 
)
值:
do { \
u128 _tmp1_ = {0, 0}; \
_u128mul(_tmp1_, (x), (y)); \
u128 _tmp2_ = {0, 0}; \
*(_tmp2_) = (*(_tmp1_)) * (modInvNeg); \
_u128mul(_tmp2_, *(_tmp2_), (mod)); \
_u128add(_tmp2_, _tmp2_, _tmp1_); \
(x) = (*(_tmp2_ + 1) < (mod)) ? (*(_tmp2_ + 1)) : ((*(_tmp2_ + 1)) - (mod)); \
} while (0)

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

347 { \
348 u128 _tmp1_ = {0, 0}; \
349 _u128mul(_tmp1_, (x), (y)); \
350 u128 _tmp2_ = {0, 0}; \
351 *(_tmp2_) = (*(_tmp1_)) * (modInvNeg); \
352 _u128mul(_tmp2_, *(_tmp2_), (mod)); \
353 _u128add(_tmp2_, _tmp2_, _tmp1_); \
354 (x) = (*(_tmp2_ + 1) < (mod)) ? (*(_tmp2_ + 1)) : ((*(_tmp2_ + 1)) - (mod)); \
355 } while (0)

◆ _mont64_norm2

#define _mont64_norm2 (   r,
  x,
  mod2 
)
值:
do { \
(r) = (x) >= (mod2) ? ((x) - (mod2)) : (x); \
} while (0)

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

313 { \
314 (r) = (x) >= (mod2) ? ((x) - (mod2)) : (x); \
315 } while (0)

◆ _mont64_sub

#define _mont64_sub (   r,
  x,
  y,
  mod2 
)
值:
do { \
(r) = (((x) - (y)) > (x)) ? (((x) - (y)) + (mod2)) : ((x) - (y)); \
} while (0)

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

298 { \
299 (r) = (((x) - (y)) > (x)) ? (((x) - (y)) + (mod2)) : ((x) - (y)); \
300 } while (0)

◆ _mont64_toint

#define _mont64_toint (   x,
  mod,
  modInvneg 
)
值:
do { \
u128 _tmp_ = {0, 0}; \
*_tmp_ = (x) * (modInvneg); \
_u128mul(_tmp_, (*_tmp_), (mod)); \
_u128add64(_tmp_, _tmp_, x); \
(x) = (*(_tmp_ + 1) < (mod)) ? (*(_tmp_ + 1)) : ((*(_tmp_ + 1)) - (mod)); \
} while (0)

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

369 { \
370 u128 _tmp_ = {0, 0}; \
371 *_tmp_ = (x) * (modInvneg); \
372 _u128mul(_tmp_, (*_tmp_), (mod)); \
373 _u128add64(_tmp_, _tmp_, x); \
374 (x) = (*(_tmp_ + 1) < (mod)) ? (*(_tmp_ + 1)) : ((*(_tmp_ + 1)) - (mod)); \
375 } while (0)

◆ _mont64_tomont

#define _mont64_tomont (   x,
  r2,
  mod,
  modInvNeg 
)
值:
do { \
u128 _tmp1_ = {0, 0}; \
_u128mul(_tmp1_, (x), (r2)); \
u128 _tmp2_ = {0, 0}; \
*(_tmp2_) = (*(_tmp1_)) * (modInvNeg); \
_u128mul(_tmp2_, (*(_tmp2_)), (mod)); \
_u128add(_tmp2_, _tmp2_, _tmp1_); \
(x) = ((*(_tmp2_ + 1)) < (mod)) ? (*(_tmp2_ + 1)) : ((*(_tmp2_ + 1)) - (mod)); \
} while (0)
r2
#define r2

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

358 { \
359 u128 _tmp1_ = {0, 0}; \
360 _u128mul(_tmp1_, (x), (r2)); \
361 u128 _tmp2_ = {0, 0}; \
362 *(_tmp2_) = (*(_tmp1_)) * (modInvNeg); \
363 _u128mul(_tmp2_, (*(_tmp2_)), (mod)); \
364 _u128add(_tmp2_, _tmp2_, _tmp1_); \
365 (x) = ((*(_tmp2_ + 1)) < (mod)) ? (*(_tmp2_ + 1)) : ((*(_tmp2_ + 1)) - (mod)); \
366 } while (0)

◆ _raw64_add

#define _raw64_add (   r,
  x,
  y 
)
值:
do { \
(r) = (x) + (y); \
} while (0)

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

303 { \
304 (r) = (x) + (y); \
305 } while (0)

◆ _raw64_sub

#define _raw64_sub (   r,
  x,
  y,
  mod2 
)
值:
do { \
(r) = (x) - (y) + (mod2); \
} while (0)

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

308 { \
309 (r) = (x) - (y) + (mod2); \
310 } while (0)

◆ _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 第 416 行定义.

417 { \
418 uint64_t _x_; \
419 _x_ = (al) - (bl); \
420 (sh) = (ah) - (bh) - ((al) < (bl)); \
421 (sl) = _x_; \
422 } while (0)

◆ _u128add

#define _u128add (   r,
  x,
  y 
)
值:
do { \
(*(r)) = *(x) + *(y); \
(*((r) + 1)) = (*((x) + 1)) + (*((y) + 1)) + ((*(r)) < (*(y)) ? 1 : 0); \
} while (0)

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

261 { \
262 (*(r)) = *(x) + *(y); \
263 (*((r) + 1)) = (*((x) + 1)) + (*((y) + 1)) + ((*(r)) < (*(y)) ? 1 : 0); \
264 } while (0)

◆ _u128add64

#define _u128add64 (   r,
  x,
  _i64 
)
值:
do { \
(*(r)) = *(x) + (_i64); \
(*((r) + 1)) = (*((x) + 1)) + (((*(r)) < (_i64)) ? 1 : 0); \
} while (0)

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

267 { \
268 (*(r)) = *(x) + (_i64); \
269 (*((r) + 1)) = (*((x) + 1)) + (((*(r)) < (_i64)) ? 1 : 0); \
270 } while (0)

◆ _u128cmp

#define _u128cmp (   x,
  y 
)    ((x)[1] < (y)[1] || ((x)[1] == (y)[1] && (x)[0] < (y)[0]))

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

◆ _u128high

#define _u128high (   x)    (*((x) + 1))

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

◆ _u128low

#define _u128low (   x)    (*(x))

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

◆ _u128lshl

#define _u128lshl (   x,
  y,
  n 
)
值:
do { \
(*((x) + 1)) = ((*(y)) >> (64 - (n))) | ((*((y) + 1)) << (n)); \
(*(x)) = (*(y)) << (n); \
} while (0)

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

245 { \
246 (*((x) + 1)) = ((*(y)) >> (64 - (n))) | ((*((y) + 1)) << (n)); \
247 (*(x)) = (*(y)) << (n); \
248 } while (0)

◆ _u128lshr

#define _u128lshr (   x,
  y,
  n 
)
值:
do { \
(*(x)) = ((*(y)) >> (n)) | ((*((y) + 1)) << (64 - (n))); \
(*((x) + 1)) = (*((y) + 1)) >> (n); \
} while (0)

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

251 { \
252 (*(x)) = ((*(y)) >> (n)) | ((*((y) + 1)) << (64 - (n))); \
253 (*((x) + 1)) = (*((y) + 1)) >> (n); \
254 } while (0)

◆ _u128mul

#define _u128mul (   r,
  x,
  y 
)    _umul64to128_((x), (y), (r), (((r) + 1)))

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

◆ _u128sub

#define _u128sub (   r,
  x,
  y 
)
值:
do { \
uint64_t _c_ = (x)[0] < (y)[0]; \
(r)[0] = (x)[0] - (y)[0]; \
(r)[1] = (x)[1] - (y)[1] - _c_; \
} while (0)

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

283 { \
284 uint64_t _c_ = (x)[0] < (y)[0]; \
285 (r)[0] = (x)[0] - (y)[0]; \
286 (r)[1] = (x)[1] - (y)[1] - _c_; \
287 } while (0)

◆ _u128sub64

#define _u128sub64 (   r,
  x,
  _i64 
)
值:
do { \
uint64_t _c_ = (x)[0] < (_i64); \
(r)[0] = (x)[0] - (_i64); \
(r)[1] = (x)[1] - _c_; \
} while (0)

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

273 { \
274 uint64_t _c_ = (x)[0] < (_i64); \
275 (r)[0] = (x)[0] - (_i64); \
276 (r)[1] = (x)[1] - _c_; \
277 } while (0)

◆ _u128x64to192

#define _u128x64to192 (   i192,
  i128,
  i64 
)
值:
do { \
_umul64to128_((*(i128)), i64, (i192), ((i192) + 1)); \
uint64_t _tmp_; \
_umul64to128_((*((i128) + 1)), i64, (&(_tmp_)), ((i192) + 2)); \
(*((i192) + 1)) += _tmp_; \
(*((i192) + 2)) += ((*((i192) + 1)) < _tmp_) ? 1 : 0; \
} while (0)

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

378 { \
379 _umul64to128_((*(i128)), i64, (i192), ((i192) + 1)); \
380 uint64_t _tmp_; \
381 _umul64to128_((*((i128) + 1)), i64, (&(_tmp_)), ((i192) + 2)); \
382 (*((i192) + 1)) += _tmp_; \
383 (*((i192) + 2)) += ((*((i192) + 1)) < _tmp_) ? 1 : 0; \
384 } while (0)

◆ _u192add

#define _u192add (   i192,
  j192 
)
值:
do { \
(*(i192)) += (*(j192)); \
uint64_t _c_ = ((*(i192)) < (*j192)) ? 1 : 0; \
(*((i192) + 1)) += _c_; \
_c_ = ((*((i192) + 1)) < _c_) ? 1 : 0; \
(*((i192) + 1)) += (*((j192) + 1)); \
_c_ += ((*((i192) + 1)) < (*((j192) + 1))) ? 1 : 0; \
(*((i192) + 2)) += _c_ + (*((j192) + 2)); \
} while (0)

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

387 { \
388 (*(i192)) += (*(j192)); \
389 uint64_t _c_ = ((*(i192)) < (*j192)) ? 1 : 0; \
390 (*((i192) + 1)) += _c_; \
391 _c_ = ((*((i192) + 1)) < _c_) ? 1 : 0; \
392 (*((i192) + 1)) += (*((j192) + 1)); \
393 _c_ += ((*((i192) + 1)) < (*((j192) + 1))) ? 1 : 0; \
394 (*((i192) + 2)) += _c_ + (*((j192) + 2)); \
395 } while (0)

◆ _u192sub

#define _u192sub (   i192,
  j192 
)
值:
do { \
uint64_t _b_ = ((i192)[0] < (j192)[0]) ? 1 : 0; \
(i192)[0] -= (j192)[0]; \
uint64_t _b1_ = ((i192)[1] < (j192)[1]) ? 1 : 0; \
(i192)[1] -= (j192)[1]; \
_b1_ += ((i192)[1] < _b_) ? 1 : 0; \
(i192)[1] -= _b_; \
(i192)[2] = (i192)[2] - ((j192)[2] + _b1_); \
} while (0)

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

398 { \
399 uint64_t _b_ = ((i192)[0] < (j192)[0]) ? 1 : 0; \
400 (i192)[0] -= (j192)[0]; \
401 uint64_t _b1_ = ((i192)[1] < (j192)[1]) ? 1 : 0; \
402 (i192)[1] -= (j192)[1]; \
403 _b1_ += ((i192)[1] < _b_) ? 1 : 0; \
404 (i192)[1] -= _b_; \
405 (i192)[2] = (i192)[2] - ((j192)[2] + _b1_); \
406 } while (0)

◆ _U64_SHIFT_MASK

#define _U64_SHIFT_MASK   0x3F

from https://libdivide.com/

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

◆ _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 第 466 行定义.

467 { \
468 uint64_t _hi_, _lo_; \
469 _umul64to128_((n0), (dinv), &_lo_, &_hi_); \
470 (q) = _hi_; \
471 } while (0)

◆ _udiv_qr_3by2

#define _udiv_qr_3by2 (   q,
  r1,
  r0,
  n2,
  n1,
  n0,
  d1,
  d0,
  dinv 
)
值:
do { \
mp_limb_t _q0_, _t1_, _t0_, _mask_; \
_umul64to128_((n2), (dinv), &_q0_, &(q)); \
_add_ssaaaa((q), _q0_, (q), _q0_, (n2), (n1)); \
/* Compute the two most significant limbs of n - q'd */ \
(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)++; \
/* Conditionally adjust q and the remainders */ \
_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)
mp_limb_t
uint64_t mp_limb_t
Definition lmmp.h:211
r1
#define r1
r0
#define r0

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

442 { \
443 mp_limb_t _q0_, _t1_, _t0_, _mask_; \
444 _umul64to128_((n2), (dinv), &_q0_, &(q)); \
445 _add_ssaaaa((q), _q0_, (q), _q0_, (n2), (n1)); \
446 /* Compute the two most significant limbs of n - q'd */ \
447 (r1) = (n1) - (d1) * (q); \
448 _sub_ddmmss((r1), (r0), (r1), (n0), (d1), (d0)); \
449 _umul64to128_((d0), (q), &_t0_, &_t1_); \
450 _sub_ddmmss((r1), (r0), (r1), (r0), _t1_, _t0_); \
451 (q)++; \
452 /* Conditionally adjust q and the remainders */ \
453 _mask_ = -(uint64_t)((r1) >= _q0_); \
454 (q) += _mask_; \
455 _add_ssaaaa((r1), (r0), (r1), (r0), _mask_ & (d1), _mask_ & (d0)); \
456 if ((r1) >= (d1)) { \
457 if ((r1) > (d1) || (r0) >= (d0)) { \
458 (q)++; \
459 _sub_ddmmss((r1), (r0), (r1), (r0), (d1), (d0)); \
460 } \
461 } \
462 } while (0)

◆ _udiv_qrnnd_preinv

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

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

425 { \
426 uint64_t _qh_, _ql_, _r_, _mask_; \
427 _umul64to128_((nh), (di), &_ql_, &_qh_); \
428 _add_ssaaaa(_qh_, _ql_, _qh_, _ql_, (nh) + 1, (nl)); \
429 _r_ = (nl) - _qh_ * (d); \
430 _mask_ = -(mp_limb_t)(_r_ > _ql_); \
431 _qh_ += _mask_; \
432 _r_ += _mask_ & (d); \
433 if (_r_ >= (d)) { \
434 _r_ -= (d); \
435 _qh_++; \
436 } \
437 (r) = _r_; \
438 (q) = _qh_; \
439 } while (0)

◆ ctz_shl

#define ctz_shl (   r,
  x,
  cnt 
)
值:
do { \
unsigned long long _x_ = (x); \
(cnt) = __builtin_ctzll(_x_); \
(r) = _x_ >> (cnt); \
} while (0)

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

230 { \
231 unsigned long long _x_ = (x); \
232 (cnt) = __builtin_ctzll(_x_); \
233 (r) = _x_ >> (cnt); \
234 } while (0)

类型定义说明

◆ _udiv64_t

typedef struct _udiv64_t _udiv64_t

◆ u128

typedef uint64_t u128[2]

请注意，此处的蒙哥马利域的R为2^64，p不可超过2^63-1

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

◆ u192

typedef uint64_t u192[3]

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

函数说明

◆ _clz_u64_()

static int32_t _clz_u64_ ( uint64_t  val)
inlinestatic

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

121 {
122#if defined(__GNUC__) || defined(__clang__)
123 // Fast way to count leading zeros
124 return __builtin_clzll(val);
125#else
126 unsigned long cnt;
127 _BitScanReverse64(&cnt, val);
128 return 63 - cnt;
129#endif
130}

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

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

◆ _udiv128by64to64_()

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

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

132 {
133#if defined(__GNUC__) || defined(__clang__)
134#ifdef USE_ASM
135 uint64_t result;
136 __asm__("div %[v]" : "=a"(result), "=d"(*r) : [v] "r"(den), "a"(numlo), "d"(numhi));
137 return result;
138#else
139 __uint128_t num = (__uint128_t)numhi << 64 | numlo;
140 uint64_t result = num / den;
141 *r = num % den;
142 return result;
143#endif
144#else
145 const uint64_t b = ((uint64_t)1 << 32);
146
147 uint32_t q1;
148 uint32_t q0;
149
150 uint64_t q;
151
152 int shift;
153
154 uint64_t den10 = den;
155 uint64_t num10 = numlo;
156
157 uint32_t den1;
158 uint32_t den0;
159 uint32_t num1;
160 uint32_t num0;
161
162 uint64_t rem;
163
164 uint64_t qhat;
165 uint64_t rhat;
166
167 uint64_t c1;
168 uint64_t c2;
169
170 if (numhi >= den) {
171 if (r)
172 *r = ~0ull;
173 return ~0ull;
174 }
175
176 shift = _clz_u64_(den);
177 den <<= shift;
178 numhi <<= shift;
179 numhi |= (numlo >> (-shift & 63)) & (uint64_t)(-(int64_t)shift >> 63);
180 numlo <<= shift;
181
182 num1 = (uint32_t)(numlo >> 32);
183 num0 = (uint32_t)(numlo & 0xFFFFFFFFu);
184 den1 = (uint32_t)(den >> 32);
185 den0 = (uint32_t)(den & 0xFFFFFFFFu);
186
187 qhat = numhi / den1;
188 rhat = numhi % den1;
189 c1 = qhat * den0;
190 c2 = rhat * b + num1;
191 if (c1 > c2)
192 qhat -= (c1 - c2 > den) ? 2 : 1;
193 q1 = (uint32_t)qhat;
194
195 rem = numhi * b + num1 - q1 * den;
196
197 qhat = rem / den1;
198 rhat = rem % den1;
199 c1 = qhat * den0;
200 c2 = rhat * b + num0;
201 if (c1 > c2)
202 qhat -= (c1 - c2 > den) ? 2 : 1;
203 q0 = (uint32_t)qhat;
204
205 q = ((uint64_t)q1 << 32) | q0;
206
207 if (r)
208 *r = num10 - q * den10;
209 return q;
210#endif
211}
_clz_u64_
static int32_t _clz_u64_(uint64_t val)
Definition longlong.h:121
c1
#define c1

引用了 _clz_u64_() , 以及 c1.

被这些函数引用 _udiv64_gen_internal_().

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

◆ _udiv64_gen()

static _udiv64_t _udiv64_gen ( uint64_t  d)
inlinestatic

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

535 {
536 _udiv64_t tmp = _udiv64_gen_internal_(d, 1);
537 _udiv64_t ret = {tmp.magic, (uint8_t)(tmp.more & _U64_SHIFT_MASK)};
538 return ret;
539}
_udiv64_t::more
uint8_t more
Definition longlong.h:482
_U64_SHIFT_MASK
#define _U64_SHIFT_MASK
from https://libdivide.com/
Definition longlong.h:477
_udiv64_gen_internal_
static _udiv64_t _udiv64_gen_internal_(uint64_t d, int branchfree)
Definition longlong.h:486
_udiv64_t::magic
uint64_t magic
Definition longlong.h:481
_udiv64_t
Definition longlong.h:480

引用了 _U64_SHIFT_MASK, _udiv64_gen_internal_(), _udiv64_t::magic , 以及 _udiv64_t::more.

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

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

◆ _udiv64_gen_internal_()

static _udiv64_t _udiv64_gen_internal_ ( uint64_t  d,
int  branchfree 
)
inlinestatic

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

486 {
487 _udiv64_t result;
488 uint32_t floor_log_2_d = 63 - _clz_u64_(d);
489
490 // Power of 2
491 if ((d & (d - 1)) == 0) {
492 // We need to subtract 1 from the shift value in case of an unsigned
493 // branchfree divider because there is a hardcoded right shift by 1
494 // in its division algorithm. Because of this we also need to add back
495 // 1 in its recovery algorithm.
496 result.magic = 0;
497 result.more = (uint8_t)(floor_log_2_d - (branchfree != 0));
498 } else {
499 uint64_t proposed_m, rem;
500 uint8_t more;
501 // (1 << (64 + floor_log_2_d)) / d
502 proposed_m = _udiv128by64to64_((uint64_t)1 << floor_log_2_d, 0, d, &rem);
503
504 const uint64_t e = d - rem;
505
506 // This power works if e < 2**floor_log_2_d.
507 if (!branchfree && e < ((uint64_t)1 << floor_log_2_d)) {
508 // This power works
509 more = (uint8_t)floor_log_2_d;
510 } else {
511 // We have to use the general 65-bit algorithm. We need to compute
512 // (2**power) / d. However, we already have (2**(power-1))/d and
513 // its remainder. By doubling both, and then correcting the
514 // remainder, we can compute the larger division.
515 // don't care about overflow here - in fact, we expect it
516 proposed_m += proposed_m;
517 const uint64_t twice_rem = rem + rem;
518 if (twice_rem >= d || twice_rem < rem)
519 proposed_m += 1;
520 more = (uint8_t)(floor_log_2_d | _ADD_MARKER);
521 }
522 result.magic = 1 + proposed_m;
523 result.more = more;
524 // result.more's shift should in general be ceil_log_2_d. But if we
525 // used the smaller power, we subtract one from the shift because we're
526 // using the smaller power. If we're using the larger power, we
527 // subtract one from the shift because it's taken care of by the add
528 // indicator. So floor_log_2_d happens to be correct in both cases,
529 // which is why we do it outside of the if statement.
530 }
531 return result;
532}
_ADD_MARKER
#define _ADD_MARKER
Definition longlong.h:478
_udiv128by64to64_
static uint64_t _udiv128by64to64_(uint64_t numhi, uint64_t numlo, uint64_t den, uint64_t *r)
Definition longlong.h:132

引用了 _ADD_MARKER, _clz_u64_(), _udiv128by64to64_(), _udiv64_t::magic , 以及 _udiv64_t::more.

被这些函数引用 _udiv64_gen().

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

◆ _udiv64by64_q_preinv()

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

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

541 {
542 uint64_t q = _umul64to64hi_(numer, denom->magic);
543 uint64_t t = ((numer - q) >> 1) + q;
544 return t >> denom->more;
545}
_umul64to64hi_
static uint64_t _umul64to64hi_(uint64_t a, uint64_t b)
Definition longlong.h:60

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

被这些函数引用 lmmp_powmod_uint_(), miller_rabin_32(), trial_div13(), trial_div17(), trial_div19(), trial_div23(), trial_div29(), trial_div31(), trial_div37() , 以及 trial_div41().

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

◆ _umul128to128_()

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

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

115 {
116 _umulx64to128_(a_low, b_low, rr, rr + 1);
117 rr[1] += a_low * b_high;
118 rr[1] += a_high * b_low;
119}
_umulx64to128_
static void _umulx64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
Definition longlong.h:78

引用了 _umulx64to128_().

被这些函数引用 lmmp_binvert_4_().

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

◆ _umul128to256_()

static 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 第 86 行定义.

86 {
87 uint64_t p1_low, p1_high; // p1 = a_low × b_high
88 uint64_t p2_low, p2_high; // p2 = a_high × b_low
89 _umulx64to128_(a_low, b_low, rr, rr + 1);
90 _umulx64to128_(a_low, b_high, &p1_low, &p1_high);
91 _umulx64to128_(a_high, b_low, &p2_low, &p2_high);
92 _umulx64to128_(a_high, b_high, rr + 2, rr + 3);
93 /*
94 | res0 | res1 | res2 | res3 |
95 | p0l | p0h | | |
96 | p1l | p1h | |
97 | p2l | p2h | |
98 | | p3l | p3h |
99 */
100 rr[1] += p1_low;
101 uint64_t carry = (rr[1] < p1_low) ? 1 : 0;
102 rr[1] += p2_low;
103 carry += (rr[1] < p2_low) ? 1 : 0;
104
105 rr[2] += carry;
106 carry = (rr[2] < carry) ? 1 : 0;
107 rr[2] += p1_high;
108 carry += (rr[2] < p1_high) ? 1 : 0;
109 rr[2] += p2_high;
110 carry += (rr[2] < p2_high) ? 1 : 0;
111
112 rr[3] += carry;
113}

引用了 _umulx64to128_().

被这些函数引用 lmmp_binvert_4_().

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

◆ _umul64to128_()

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

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

31 {
32#if (defined(__GNUC__) || defined(__clang__))
33#if defined(USE_ASM) && (defined(__x86_64__))
34 __asm__("mul %[b]"
35 : "=a"(*low),
36 "=d"(*high)
37 : "a"(a), [b] "r"(b)
38 :
39 );
40#else
41 __uint128_t prod = (__uint128_t)a * b;
42 *low = (uint64_t)prod;
43 *high = (uint64_t)(prod >> 64);
44#endif
45#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_ARM64))
46 *low = _umul128(a, b, high);
47#else
48 uint64_t ah = a >> 32, bh = b >> 32;
49 a = (uint32_t)a, b = (uint32_t)b;
50 uint64_t r0 = a * b, r1 = a * bh, r2 = ah * b, r3 = ah * bh;
51 r3 += (r1 >> 32) + (r2 >> 32);
52 r1 = (uint32_t)r1, r2 = (uint32_t)r2;
53 r1 += r2;
54 r1 += (r0 >> 32);
55 *high = r3 + (r1 >> 32);
56 *low = (r1 << 32) | (uint32_t)r0;
57#endif
58}
r3
#define r3

引用了 r0, r1, r2 , 以及 r3.

被这些函数引用 _umulx64to128_(), lmmp_addmul_1_(), lmmp_binvert_2_(), lmmp_binvert_4_(), lmmp_inv_2_1_(), lmmp_mul_1_(), lmmp_mul_basecase_(), lmmp_mulmod_ulong_(), lmmp_sqr_basecase_(), lmmp_submul_1_() , 以及 pcg64_128_action().

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

◆ _umul64to64hi_()

static uint64_t _umul64to64hi_ ( uint64_t  a,
uint64_t  b 
)
inlinestatic

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

60 {
61#if (defined(__GNUC__) || defined(__clang__)) && defined(__SIZEOF_INT128__)
62 __uint128_t t = (__uint128_t)a * (__uint128_t)b;
63 return (uint64_t)(t >> 64);
64#elif defined(_MSC_VER) && (defined(_M_X64) || defined(_M_ARM64))
65 return __umulh(a, b);
66#else
67 uint64_t ah = a >> 32, bh = b >> 32;
68 a = (uint32_t)a, b = (uint32_t)b;
69 uint64_t r0 = a * b, r1 = a * bh, r2 = ah * b, r3 = ah * bh;
70 r3 += (r1 >> 32) + (r2 >> 32);
71 r1 = (uint32_t)r1, r2 = (uint32_t)r2;
72 r1 += r2;
73 r1 += (r0 >> 32);
74 return r3 + (r1 >> 32);
75#endif
76}

引用了 r0, r1, r2 , 以及 r3.

被这些函数引用 _udiv64by64_q_preinv().

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

◆ _umulx64to128_()

static void _umulx64to128_ ( uint64_t  a,
uint64_t  b,
uint64_t *  low,
uint64_t *  high 
)
inlinestatic

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

78 {
79#if defined(USE_ASM) && (defined(__x86_64__))
80 *low = _mulx_u64(a, b, high);
81#else
82 _umul64to128_(a, b, low, high);
83#endif
84}
_umul64to128_
static void _umul64to128_(uint64_t a, uint64_t b, uint64_t *low, uint64_t *high)
Definition longlong.h:31

引用了 _umul64to128_().

被这些函数引用 _umul128to128_(), _umul128to192_() , 以及 _umul128to256_().

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