stdbuiltinmathLimblimb_bitsHalfLimbhalf_limb_bitsDoubleLimbSignedDoubleLimbLog2LimbAllocatormemmaxIntminIntassertEndianSignednessnative_endianConstantsconstantscalcLimbLencalcLog10LimbsBufferLencalcToStringLimbsBufferLencalcDivLimbsBufferLencalcMulLimbsBufferLencalcMulWrapLimbsBufferLencalcSetStringLimbsBufferLencalcSetStringLimbCountcalcPowLimbsBufferLencalcSqrtLimbsBufferLencalcNonZeroTwosCompLimbCountcalcTwosCompLimbCountaddMulLimbWithCarrysubMulLimbWithBorrowTwosCompIntLimitRoundExactnessMutableConstManagedAccOpllmulaccllmulaccKaratsuballaccumllcmpllmulaccLongllmulLimbllnormalizellsubcarryllsublladdcarrylladdlldiv1lldiv0p5llshlllshrllnotllsignedorllsignedandllsignedxorllsquareBasecasellpowfixedIntFromSignedDoubleLimbslicesOverlaptesting_allocatorCasetestOneShiftCasetestOneShiftCaseNoAliasingtestOneShiftCaseAliasingtestFormat
std.math.big.int.AccOp
容器
累加式函数(llmulacc、llmulaccKaratsuba、llmulaccLong、llmulLimb) 可使用的不同运算符。这些函数都会将 计算值累加到现有结果中。
字段
add将计算出的值加到结果中。
sub从结果中减去计算出的值。
std.math.big.int.addMulLimbWithCarry
函数
a + b * c + *carry,将 carry 设置为溢出的位。
pub fn addMulLimbWithCarry(a: Limb, b: Limb, c: Limb, carry: *Limb) Limb
参数
std.math.big.int.Allocator
别名
别名目标 std.mem.Allocator
std.math.big.int.assert
别名
别名目标 std.debug.assert
std.math.big.int.builtin
常量
std.math.big.int.calcDivLimbsBufferLen
函数
pub fn calcDivLimbsBufferLen(a_len: usize, b_len: usize) usize
参数
a_len: usize
b_len: usize
std.math.big.int.calcLimbLen
函数
返回存储 scalar 所需的 limb 数量;该值必须是
基本整数或浮点数。
注意:如果 scalar 并非编译时已知,可以改用
此值的编译时已知上界:
calcTwosCompLimbCount(@typeInfo(@TypeOf(scalar)).int.bits)
pub fn calcLimbLen(scalar: anytype) usize
std.math.big.int.calcLog10LimbsBufferLen
函数
与 calcToStringLimbsBufferLen 相同,但不进行无用的基数检查。
pub fn calcLog10LimbsBufferLen(a_len: usize) usize
参数
a_len: usize
std.math.big.int.calcMulLimbsBufferLen
函数
pub fn calcMulLimbsBufferLen(a_len: usize, b_len: usize, aliases: usize) usize
参数
a_len: usize
b_len: usize
aliases: usize
std.math.big.int.calcMulWrapLimbsBufferLen
函数
pub fn calcMulWrapLimbsBufferLen(bit_count: usize, a_len: usize, b_len: usize, aliases: usize) usize
参数
bit_count: usize
a_len: usize
b_len: usize
aliases: usize
std.math.big.int.calcNonZeroTwosCompLimbCount
函数
计算存储一个 bit_count 位的二进制补码数所需的数位数量。
pub fn calcNonZeroTwosCompLimbCount(bit_count: usize) usize
参数
bit_count: usize
std.math.big.int.calcPowLimbsBufferLen
函数
pub fn calcPowLimbsBufferLen(a_bit_count: usize, y: usize) usize
参数
a_bit_count: usize
y: usize
std.math.big.int.calcSetStringLimbCount
函数
假定数为负数时,string_len 不包含负号。
pub fn calcSetStringLimbCount(base: u8, string_len: usize) usize
参数
base: u8
string_len: usize
std.math.big.int.calcSetStringLimbsBufferLen
函数
pub fn calcSetStringLimbsBufferLen(base: u8, string_len: usize) usize
参数
base: u8
string_len: usize
std.math.big.int.calcSqrtLimbsBufferLen
函数
pub fn calcSqrtLimbsBufferLen(a_bit_count: usize) usize
参数
a_bit_count: usize
std.math.big.int.calcToStringLimbsBufferLen
函数
pub fn calcToStringLimbsBufferLen(a_len: usize, base: u8) usize
参数
a_len: usize
base: u8
std.math.big.int.calcTwosCompLimbCount
函数
计算存储 bit_count 位二进制补码数所需的 limb 数量。
特殊处理 bit_count == 0,此时返回 1。零位整数只能存储零值,
而此大整数实现使用一个 limb 存储零。
pub fn calcTwosCompLimbCount(bit_count: usize) usize
参数
bit_count: usize
std.math.big.int.Case
容器
字段
std.math.big.int.Const
容器
具有固定不可变字集合的任意精度大整数。
字段
limbs: []const Limb原始数位,具有以下性质:
- 小端顺序
- limbs.len >= 1
- 零表示为 limbs.len == 1 且 limbs[0] == 0。
应避免直接访问 limbs。
positive: bool
toManagedtoMutabledumpabsnegateisOddisEvenbitCountAbsbitCountTwosCompbitCountTwosCompForSignednesspopCountfitsInTwosCompfitssizeInBaseUpperBoundConvertErrortoInttoFloatformatformatNumbertoStringAlloctoStringwriteTwosComplementwritePackedTwosComplementorderAbsorderorderAgainstScalareqlZeroeqlAbseqlclzctzlog2log10Alloclog10
std.math.big.int.Const.abs
函数
pub fn abs(self: Const) Const
参数
self: Const
std.math.big.int.Const.bitCountAbs
函数
返回表示整数绝对值所需的位数。
pub fn bitCountAbs(self: Const) usize
参数
self: Const
std.math.big.int.Const.bitCountTwosComp
函数
返回以二进制补码形式表示该整数所需的位数。
若整数为负,返回有符号整数表示该值 所需的位数。若为正,则返回无符号整数 所需的位数。任意无符号整数均可放入位数 比返回值多一位的有符号整数。
例如,-127 返回 8,因为可放入 i8;127 返回 7,因为可放入 u7。
pub fn bitCountTwosComp(self: Const) usize
参数
self: Const
std.math.big.int.Const.bitCountTwosCompForSignedness
函数
返回按照给定的有符号性,以二进制补码形式表示 该整数所需的位数。
pub fn bitCountTwosCompForSignedness(self: Const, signedness: std.builtin.Signedness) usize
参数
self: Const
signedness: std.builtin.Signedness
std.math.big.int.Const.clz
函数
返回二进制补码形式中的前导零数量。
pub fn clz(a: Const, bits: Limb) Limb
参数
std.math.big.int.Const.ConvertError
错误集合
错误
- NegativeIntoUnsigned
- TargetTooSmall
std.math.big.int.Const.ctz
函数
返回二进制补码形式中的尾随零数量。
pub fn ctz(a: Const, bits: Limb) Limb
参数
std.math.big.int.Const.dump
函数
pub fn dump(self: Const) void
参数
self: Const
std.math.big.int.Const.eql
函数
若 a == b,返回 true。
pub fn eql(a: Const, b: Const) bool
参数
std.math.big.int.Const.eqlAbs
函数
若 |a| == |b|,返回 true。
pub fn eqlAbs(a: Const, b: Const) bool
参数
std.math.big.int.Const.eqlZero
函数
若 a == 0 则返回 true。
pub fn eqlZero(a: Const) bool
参数
a: Const
std.math.big.int.Const.fits
函数
返回 self 是否可容纳于请求类型的整数。
pub fn fits(self: Const, comptime T: type) bool
参数
self: Const
T: type
std.math.big.int.Const.fitsInTwosComp
函数
pub fn fitsInTwosComp(self: Const, signedness: Signedness, bit_count: usize) bool
参数
std.math.big.int.Const.format
函数
pub fn format(self: Const, w: *std.Io.Writer) std.Io.Writer.Error!void
参数
错误
- WriteFailed
详细诊断信息见
Writer实现。
std.math.big.int.Const.formatNumber
函数
若整数的绝对值大于或等于 pow(2, 64 * @sizeOf(usize) * 8),
此函数无法打印数值字符串,改为输出 "(BigInt)"。
原因是渲染算法需要反转字符串,从而需要 O(N) 内存。
不会因此失败的大整数打印方式参见 toString 和 toStringAlloc。
pub fn formatNumber(self: Const, w: *std.Io.Writer, number: std.fmt.Number) std.Io.Writer.Error!void
参数
错误
- WriteFailed
详细诊断信息见
Writer实现。
std.math.big.int.Const.isEven
函数
pub fn isEven(self: Const) bool
参数
self: Const
std.math.big.int.Const.isOdd
函数
pub fn isOdd(self: Const) bool
参数
self: Const
std.math.big.int.Const.log10
函数
计算以 10 为底的对数,向下取整。
limbs_buffer 用作临时存储。所需大小由 calcLog10LimbsBufferLen 给出。
pub fn log10(a: Const, limbs_buffer: []Limb) Limb
参数
std.math.big.int.Const.log10Alloc
函数
计算以 10 为底的对数,向下取整。
分配器用于分配临时缓冲区。
pub fn log10Alloc(a: Const, allocator: Allocator) Allocator.Error!Limb
参数
错误
- OutOfMemory
std.math.big.int.Const.log2
函数
计算以 2 为底的对数,并向下取整。
pub fn log2(a: Const) Limb
参数
a: Const
std.math.big.int.Const.negate
函数
pub fn negate(self: Const) Const
参数
self: Const
std.math.big.int.Const.order
函数
当 a < b、a == b 或 a > b 时,分别返回 math.Order.lt、math.Order.eq、math.Order.gt。
pub fn order(a: Const, b: Const) math.Order
参数
std.math.big.int.Const.orderAbs
函数
当 |a| < |b|、|a| == |b| 或 |a| > |b| 时,分别返回 math.Order.lt、math.Order.eq、math.Order.gt。
pub fn orderAbs(a: Const, b: Const) math.Order
参数
std.math.big.int.Const.orderAgainstScalar
函数
与 order 相同,但右侧操作数是原始整数。
pub fn orderAgainstScalar(lhs: Const, scalar: anytype) math.Order
参数
lhs: Const
std.math.big.int.Const.popCount
函数
具有二进制补码语义的 @popCount。
返回此值按给定整数位宽 bit_count 表示为 二进制补码时,值为 1 的位的数量。 包括最前面的符号位,负值的符号位为 1。
断言 bit_count 足以用二进制补码表示 value,
且最终结果可容纳于 usize。
断言最高有效端没有多余的空 limb,
即 limb 数量与 calcLimbLen() 匹配,且零不为负数。
pub fn popCount(self: Const, bit_count: usize) usize
参数
self: Const
bit_count: usize
std.math.big.int.Const.sizeInBaseUpperBound
函数
返回整数在给定进制下的大致表示长度,负数会计入负号。 用于确定输出该值所需的字符数量。结果不精确,可能比实际值多约 1–2 字节。 TODO: 研究能否精确计算。
pub fn sizeInBaseUpperBound(self: Const, base: usize) usize
参数
self: Const
base: usize
std.math.big.int.Const.toFloat
类型函数
将自身转换为 Float。
pub fn toFloat(self: Const, comptime Float: type, round: Round) struct { Float, Exactness }
参数
std.math.big.int.Const.toInt
函数
将 self 转换为 Int。
若无法在不截断的情况下将 self 缩窄为请求类型,则返回错误。
pub fn toInt(self: Const, comptime Int: type) ConvertError!Int
参数
self: Const
Int: type
错误
- NegativeIntoUnsigned
- TargetTooSmall
std.math.big.int.Const.toManaged
函数
结果是由调用方管理的独立资源。
pub fn toManaged(self: Const, allocator: Allocator) Allocator.Error!Managed
参数
错误
- OutOfMemory
std.math.big.int.Const.toMutable
函数
断言 limbs 足够大,能够存储该值。
pub fn toMutable(self: Const, limbs: []Limb) Mutable
参数
std.math.big.int.Const.toString
函数
将自身转换为指定进制的字符串。
断言 base 位于 [2, 36] 范围内。
string 为调用方提供、至少长 sizeInBaseUpperBound 字节的切片,
用于写入结果。
返回字符串长度。
limbs_buffer 是调用方提供给 toString 的工作区内存,其
长度必须至少为 calcToStringLimbsBufferLen。
进制为二的幂时,忽略 limbs_buffer。
另请参见更高层函数 toStringAlloc。
pub fn toString(self: Const, string: []u8, base: u8, case: std.fmt.Case, limbs_buffer: []Limb) usize
参数
std.math.big.int.Const.toStringAlloc
函数
将自身转换为指定进制的字符串。
调用者拥有返回内存的所有权。
断言 base 位于范围 [2, 36]。
另见比此函数更底层的 toString。
pub fn toStringAlloc(self: Const, allocator: Allocator, base: u8, case: std.fmt.Case) Allocator.Error![]u8
参数
错误
- OutOfMemory
std.math.big.int.Const.writePackedTwosComplement
函数
将 x 的值写入紧凑内存 buffer。
断言 buffer 足够大,能容纳位数为 bit_count 的值,位置为偏移 bit_offset。
这等价于将一个具有 bit_count 位的整数值,视为紧凑内存中位于给定位偏移的字段进行存储。
pub fn writePackedTwosComplement(x: Const, buffer: []u8, bit_offset: usize, bit_count: usize, endian: Endian) void
参数
std.math.big.int.Const.writeTwosComplement
函数
将 x 的值写入 buffer。
断言 buffer 足以存储该值。
填充 buffer,使其内容与通过
@ptrCast(*[buffer.len]const u8, &x) 观察到的内容一致。字节顺序由 endian 决定,
任何必要的填充位都添加在最高有效位一端。
pub fn writeTwosComplement(x: Const, buffer: []u8, endian: Endian) void
参数
std.math.big.int.constants
常量
Constants
std.math.big.int.Constants
容器
字段
big_bases: [37]Limb
digits_per_limb: [37]u8
std.math.big.int.DoubleLimb
别名
std.math.big.int.Endian
别名
别名目标 std.lang.Endian
std.math.big.int.Exactness
容器
字段
inexact
exact
std.math.big.int.fixedIntFromSignedDoubleLimb
函数
fn fixedIntFromSignedDoubleLimb(A: SignedDoubleLimb, storage: []Limb) Mutable
参数
A: SignedDoubleLimb
storage: []Limb
std.math.big.int.half_limb_bits
常量
std.math.big.int.HalfLimb
别名
std.math.big.int.Limb
别名
别名目标 std.math.big.Limb
std.math.big.int.limb_bits
常量
std.math.big.int.llaccum
函数
r = r (op) a。
结果按 r.len 取模计算。
fn llaccum(comptime op: AccOp, r: []Limb, a: []const Limb) void
参数
std.math.big.int.lladd
函数
fn lladd(r: []Limb, a: []const Limb, b: []const Limb) void
参数
std.math.big.int.lladdcarry
函数
Knuth 4.3.1,算法 A。
fn lladdcarry(r: []Limb, a: []const Limb, b: []const Limb) Limb
参数
std.math.big.int.llcmp
函数
对于字,当 |a| < |b|、|a| == |b|、|a| > |b| 时分别返回 -1、0、1。
pub fn llcmp(a: []const Limb, b: []const Limb) i8
参数
std.math.big.int.lldiv0p5
函数
fn lldiv0p5(quo: []Limb, rem: *Limb, a: []const Limb, b: HalfLimb) void
参数
std.math.big.int.lldiv1
函数
Knuth 4.3.1,习题 16。
fn lldiv1(quo: []Limb, rem: *Limb, a: []const Limb, b: Limb) void
参数
std.math.big.int.llmulacc
函数
Knuth 4.3.1,算法 M。
r = r (op) a * b r 不得与 a 或 b 共用存储。
结果按 r.len 取模计算。r.len >= a.len + b.len 时不会溢出。
fn llmulacc(comptime op: AccOp, opt_allocator: ?Allocator, r: []Limb, a: []const Limb, b: []const Limb) void
参数
std.math.big.int.llmulaccKaratsuba
函数
Knuth 4.3.1,算法 M。
r = r (op) a * b r 不得与 a 或 b 共用存储。
结果按 r.len 取模计算。r.len >= a.len + b.len 时不会溢出。
fn llmulaccKaratsuba( comptime op: AccOp, allocator: Allocator, r: []Limb, a: []const Limb, b: []const Limb, ) error{OutOfMemory}!void
参数
错误
- OutOfMemory
std.math.big.int.llmulaccLong
函数
r = r (op) y * xi
结果按 r.len 取模。当 r.len >= a.len + b.len 时不会溢出。
fn llmulaccLong(comptime op: AccOp, r: []Limb, a: []const Limb, b: []const Limb) void
参数
std.math.big.int.llmulLimb
函数
r = r (op) y * xi
结果按 r.len 对应的模计算。
返回操作是否溢出。
fn llmulLimb(comptime op: AccOp, acc: []Limb, y: []const Limb, xi: Limb) bool
参数
std.math.big.int.llnormalize
函数
返回 limb 可能具有的最小长度。
fn llnormalize(a: []const Limb) usize
参数
a: []const Limb
std.math.big.int.llnot
函数
fn llnot(r: []Limb) void
参数
r: []Limb
std.math.big.int.llpow
函数
Knuth 4.6.3
fn llpow(r: []Limb, a: []const Limb, b: u32, tmp_limbs: []Limb) void
参数
std.math.big.int.llshl
函数
执行 r = a << shift,并返回受影响的 limb 数。
若 a 与 r 重叠,则断言 r.ptr >= a.ptr。 r 必须有足够容量存储 a << shift。
fn llshl(r: []Limb, a: []const Limb, shift: usize) usize
参数
用法示例
test llshl {
if (limb_bits != 64) return error.SkipZigTest;
// 1 << 63
const left_one = 0x8000000000000000;
const maxint: Limb = 0xFFFFFFFFFFFFFFFF;
// zig fmt: off
try testOneShiftCase(.llshl, .{0, &.{0}, &.{0}});
try testOneShiftCase(.llshl, .{0, &.{1}, &.{1}});
try testOneShiftCase(.llshl, .{0, &.{125484842448}, &.{125484842448}});
try testOneShiftCase(.llshl, .{0, &.{0xdeadbeef}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{0, &.{maxint}, &.{maxint}});
try testOneShiftCase(.llshl, .{0, &.{left_one}, &.{left_one}});
try testOneShiftCase(.llshl, .{0, &.{0, 1}, &.{0, 1}});
try testOneShiftCase(.llshl, .{0, &.{1, 2}, &.{1, 2}});
try testOneShiftCase(.llshl, .{0, &.{left_one, 1}, &.{left_one, 1}});
try testOneShiftCase(.llshl, .{1, &.{0}, &.{0}});
try testOneShiftCase(.llshl, .{1, &.{2}, &.{1}});
try testOneShiftCase(.llshl, .{1, &.{250969684896}, &.{125484842448}});
try testOneShiftCase(.llshl, .{1, &.{0x1bd5b7dde}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{1, &.{0xfffffffffffffffe, 1}, &.{maxint}});
try testOneShiftCase(.llshl, .{1, &.{0, 1}, &.{left_one}});
try testOneShiftCase(.llshl, .{1, &.{0, 2}, &.{0, 1}});
try testOneShiftCase(.llshl, .{1, &.{2, 4}, &.{1, 2}});
try testOneShiftCase(.llshl, .{1, &.{0, 3}, &.{left_one, 1}});
try testOneShiftCase(.llshl, .{5, &.{32}, &.{1}});
try testOneShiftCase(.llshl, .{5, &.{4015514958336}, &.{125484842448}});
try testOneShiftCase(.llshl, .{5, &.{0x1bd5b7dde0}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{5, &.{0xffffffffffffffe0, 0x1f}, &.{maxint}});
try testOneShiftCase(.llshl, .{5, &.{0, 16}, &.{left_one}});
try testOneShiftCase(.llshl, .{5, &.{0, 32}, &.{0, 1}});
try testOneShiftCase(.llshl, .{5, &.{32, 64}, &.{1, 2}});
try testOneShiftCase(.llshl, .{5, &.{0, 48}, &.{left_one, 1}});
try testOneShiftCase(.llshl, .{64, &.{0, 1}, &.{1}});
try testOneShiftCase(.llshl, .{64, &.{0, 125484842448}, &.{125484842448}});
try testOneShiftCase(.llshl, .{64, &.{0, 0xdeadbeef}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{64, &.{0, maxint}, &.{maxint}});
try testOneShiftCase(.llshl, .{64, &.{0, left_one}, &.{left_one}});
try testOneShiftCase(.llshl, .{64, &.{0, 0, 1}, &.{0, 1}});
try testOneShiftCase(.llshl, .{64, &.{0, 1, 2}, &.{1, 2}});
try testOneShiftCase(.llshl, .{64, &.{0, left_one, 1}, &.{left_one, 1}});
try testOneShiftCase(.llshl, .{35, &.{0x800000000}, &.{1}});
try testOneShiftCase(.llshl, .{35, &.{13534986488655118336, 233}, &.{125484842448}});
try testOneShiftCase(.llshl, .{35, &.{0xf56df77800000000, 6}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{35, &.{0xfffffff800000000, 0x7ffffffff}, &.{maxint}});
try testOneShiftCase(.llshl, .{35, &.{0, 17179869184}, &.{left_one}});
try testOneShiftCase(.llshl, .{35, &.{0, 0x800000000}, &.{0, 1}});
try testOneShiftCase(.llshl, .{35, &.{0x800000000, 0x1000000000}, &.{1, 2}});
try testOneShiftCase(.llshl, .{35, &.{0, 0xc00000000}, &.{left_one, 1}});
try testOneShiftCase(.llshl, .{70, &.{0, 64}, &.{1}});
try testOneShiftCase(.llshl, .{70, &.{0, 8031029916672}, &.{125484842448}});
try testOneShiftCase(.llshl, .{70, &.{0, 0x37ab6fbbc0}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{70, &.{0, 0xffffffffffffffc0, 63}, &.{maxint}});
try testOneShiftCase(.llshl, .{70, &.{0, 0, 32}, &.{left_one}});
try testOneShiftCase(.llshl, .{70, &.{0, 0, 64}, &.{0, 1}});
try testOneShiftCase(.llshl, .{70, &.{0, 64, 128}, &.{1, 2}});
try testOneShiftCase(.llshl, .{70, &.{0, 0, 0x60}, &.{left_one, 1}});
// zig fmt: on
}
std.math.big.int.llshr
函数
执行 r = a >> shift,返回受影响的 limb 数。
若 a 与 r 重叠,则断言 r.ptr <= a.ptr。 r 必须有足够容量存储 a >> shift。
行为示例参见下方测试。
fn llshr(r: []Limb, a: []const Limb, shift: usize) usize
参数
用法示例
test llshr {
if (limb_bits != 64) return error.SkipZigTest;
// 1 << 63
const left_one = 0x8000000000000000;
const maxint: Limb = 0xFFFFFFFFFFFFFFFF;
// zig fmt: off
try testOneShiftCase(.llshr, .{0, &.{0, 0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{0, &.{0, 1}, &.{0, 1}});
try testOneShiftCase(.llshr, .{0, &.{15, 1}, &.{15, 1}});
try testOneShiftCase(.llshr, .{0, &.{987656565, 123456789456}, &.{987656565, 123456789456}});
try testOneShiftCase(.llshr, .{0, &.{0xfeebdaed, 0xdeadbeef}, &.{0xfeebdaed, 0xdeadbeef}});
try testOneShiftCase(.llshr, .{0, &.{1, maxint}, &.{1, maxint}});
try testOneShiftCase(.llshr, .{0, &.{0, left_one}, &.{0, left_one}});
try testOneShiftCase(.llshr, .{1, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{1, &.{left_one}, &.{0, 1}});
try testOneShiftCase(.llshr, .{1, &.{0x8000000000000007}, &.{15, 1}});
try testOneShiftCase(.llshr, .{1, &.{493828282, 61728394728}, &.{987656565, 123456789456}});
try testOneShiftCase(.llshr, .{1, &.{0x800000007f75ed76, 0x6f56df77}, &.{0xfeebdaed, 0xdeadbeef}});
try testOneShiftCase(.llshr, .{1, &.{left_one, 0x7fffffffffffffff}, &.{1, maxint}});
try testOneShiftCase(.llshr, .{1, &.{0, 0x4000000000000000}, &.{0, left_one}});
try testOneShiftCase(.llshr, .{64, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{64, &.{1}, &.{0, 1}});
try testOneShiftCase(.llshr, .{64, &.{1}, &.{15, 1}});
try testOneShiftCase(.llshr, .{64, &.{123456789456}, &.{987656565, 123456789456}});
try testOneShiftCase(.llshr, .{64, &.{0xdeadbeef}, &.{0xfeebdaed, 0xdeadbeef}});
try testOneShiftCase(.llshr, .{64, &.{maxint}, &.{1, maxint}});
try testOneShiftCase(.llshr, .{64, &.{left_one}, &.{0, left_one}});
try testOneShiftCase(.llshr, .{72, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{72, &.{0}, &.{0, 1}});
try testOneShiftCase(.llshr, .{72, &.{0}, &.{15, 1}});
try testOneShiftCase(.llshr, .{72, &.{482253083}, &.{987656565, 123456789456}});
try testOneShiftCase(.llshr, .{72, &.{0xdeadbe}, &.{0xfeebdaed, 0xdeadbeef}});
try testOneShiftCase(.llshr, .{72, &.{0xffffffffffffff}, &.{1, maxint}});
try testOneShiftCase(.llshr, .{72, &.{0x80000000000000}, &.{0, left_one}});
// zig fmt: on
}
std.math.big.int.llsignedand
函数
fn llsignedand(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_positive: bool) bool
参数
std.math.big.int.llsignedor
函数
fn llsignedor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_positive: bool) bool
参数
std.math.big.int.llsignedxor
函数
fn llsignedxor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_positive: bool) bool
参数
std.math.big.int.llsquareBasecase
函数
r 不得与 x 存在别名关系。
fn llsquareBasecase(r: []Limb, x: []const Limb) void
参数
std.math.big.int.llsub
函数
fn llsub(r: []Limb, a: []const Limb, b: []const Limb) void
参数
std.math.big.int.llsubcarry
函数
Knuth 4.3.1,算法 S。
fn llsubcarry(r: []Limb, a: []const Limb, b: []const Limb) Limb
参数
std.math.big.int.Log2Limb
别名
std.math.big.int.Managed
容器
附带管理内存的分配器的任意精度大整数。
按需分配内存,以确保操作永不溢出。取值范围 仅受可用内存限制。
字段
allocator: AllocatorManaged 请求内存时使用的分配器。
limbs: []Limb原始数位,具有以下性质:
- 小端顺序
- limbs.len >= 1
- 零表示为 Managed.len() == 1 且 limbs[0] == 0。
应避免直接访问 limbs。
metadata: usize最高位为符号位。置位时 Managed 为负,否则为正。 其余位表示 Managed 使用的 limb 数量。
sign_bitdefault_capacityinittoMutabletoConstinitSetinitCapacitylenisPositivesetSignsetLensetMetadataensureCapacitydeinitclonecloneWithDifferentAllocatorcopyswapdumpnegateabsisOddisEvenbitCountAbsbitCountTwosCompfitsInTwosCompfitssizeInBaseUpperBoundsetConvertErrortoInttoFloatsetStringsetTwosCompIntLimittoStringformatformatNumberorderAbsordereqlZeroeqlAbseqlnormalizeaddScalaraddaddWrapaddSatsubsubWrapsubSatmulmulWrapensureTwosCompCapacitylimbsAliasDistinctensureAliasAwareCapacityensureAddScalarCapacityensureAddCapacityensureMulCapacitydivFloordivCeildivTruncshiftLeftshiftLeftSatshiftRightbitNotWrapbitOrbitAndbitXorgcdsqrpowsqrttruncatesaturatepopCount
std.math.big.int.Managed.abs
函数
变为正数。
pub fn abs(self: *Managed) void
参数
self: *Managed
std.math.big.int.Managed.add
函数
r = a + b
r、a 和 b 可以互为别名。
无法分配内存时返回错误。
pub fn add(r: *Managed, a: *const Managed, b: *const Managed) Allocator.Error!void
参数
错误
- OutOfMemory
std.math.big.int.Managed.addSat
函数
r = a + b,采用二进制补码饱和语义。
r、a 和 b 可以是别名。
无法分配内存时返回错误。
pub fn addSat(r: *Managed, a: *const Managed, b: *const Managed, signedness: Signedness, bit_count: usize) Allocator.Error!void
参数
错误
- OutOfMemory
std.math.big.int.Managed.addScalar
函数
r = a + scalar
r 和 a 可以互为别名。
无法分配内存时返回错误。
pub fn addScalar(r: *Managed, a: *const Managed, scalar: anytype) Allocator.Error!void
参数
错误
- OutOfMemory
std.math.big.int.Managed.addWrap
函数
r = a + b,采用二进制补码回绕语义。返回是否发生任何溢出。
r、a 和 b 可以互为别名。
若无法分配内存,则返回错误。
pub fn addWrap( r: *Managed, a: *const Managed, b: *const Managed, signedness: Signedness, bit_count: usize, ) Allocator.Error!bool
参数
错误
- OutOfMemory
std.math.big.int.Managed.bitAnd
函数
r = a & b
pub fn bitAnd(r: *Managed, a: *const Managed, b: *const Managed) !void
参数
std.math.big.int.Managed.bitCountAbs
函数
返回表示整数绝对值所需的位数。
pub fn bitCountAbs(self: Managed) usize
参数
self: Managed
std.math.big.int.Managed.bitCountTwosComp
函数
返回以二进制补码形式表示该整数所需的位数。
若整数为负,返回有符号整数表示该值 所需的位数。若为正,则返回无符号整数 所需的位数。任意无符号整数均可放入位数 比返回值多一位的有符号整数。
例如,-127 返回 8,因为可放入 i8;127 返回 7,因为可放入 u7。
pub fn bitCountTwosComp(self: Managed) usize
参数
self: Managed
std.math.big.int.Managed.bitNotWrap
函数
r = ~a,采用二进制补码回绕语义。 r 和 a 可以是别名。
pub fn bitNotWrap(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void
参数
std.math.big.int.Managed.bitOr
函数
r = a | b
a 和 b 均零扩展至两者中较长者的长度。
pub fn bitOr(r: *Managed, a: *const Managed, b: *const Managed) !void
参数
std.math.big.int.Managed.bitXor
函数
r = a ^ b
pub fn bitXor(r: *Managed, a: *const Managed, b: *const Managed) !void
参数
std.math.big.int.Managed.clone
函数
返回同值的 Managed。返回的 Managed 是深拷贝,
可独立于原对象修改,其资源也独立于原对象
管理。
pub fn clone(other: Managed) !Managed
参数
other: Managed
std.math.big.int.Managed.cloneWithDifferentAllocator
函数
pub fn cloneWithDifferentAllocator(other: Managed, allocator: Allocator) !Managed
参数
std.math.big.int.Managed.ConvertError
别名
std.math.big.int.Managed.copy
函数
将整数值复制到已有的 Managed,使二者具有相同值。
若接收方容量不足,则分配额外内存。
pub fn copy(self: *Managed, other: Const) !void
参数
std.math.big.int.Managed.default_capacity
常量
创建 Managed 时默认分配的 limb 数量。
std.math.big.int.Managed.deinit
函数
释放所有关联内存。
pub fn deinit(self: *Managed) void
参数
self: *Managed
std.math.big.int.Managed.divCeil
函数
q = a / b(余数 r)
a / b 向上取整(朝正无穷方向)。
无法分配内存时返回错误。
pub fn divCeil(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void
参数
std.math.big.int.Managed.divFloor
函数
q = a / b(余数 r)
a / b 向下取整(朝 0 方向)。
无法分配内存时返回错误。
pub fn divFloor(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void
参数
std.math.big.int.Managed.divTrunc
函数
q = a / b(余数 r)
a / b 被截断(向负无穷舍入)。
无法分配内存时返回错误。
pub fn divTrunc(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void
参数
std.math.big.int.Managed.dump
函数
调试工具:将状态输出到 stderr。
pub fn dump(self: Managed) void
参数
self: Managed
std.math.big.int.Managed.ensureAddCapacity
函数
如果某些参数彼此构成别名,请在执行 add 之前使用此函数。
pub fn ensureAddCapacity(r: *Managed, a: *const Managed, b: *const Managed) !void
参数
std.math.big.int.Managed.ensureAddScalarCapacity
函数
若部分参数彼此互为别名,请在执行 addScalar 前使用此函数
pub fn ensureAddScalarCapacity(r: *Managed, a: *const Managed, scalar: anytype) !void
参数
std.math.big.int.Managed.ensureAliasAwareCapacity
函数
当 aliased 为 false 时,包括两个指针引用同一对象的情况,
ensureCapacity 可能重新分配。依赖不同 Managed 实例
互为别名的调用方,必须先确保容量,再建立别名。
参见 https://github.com/ziglang/zig/issues/6167
fn ensureAliasAwareCapacity(r: *Managed, needed: usize, aliased: bool) !void
参数
std.math.big.int.Managed.ensureCapacity
函数
确保 Managed 已分配足以容纳 capacity 个 limb 的空间。若 Managed 容量不足, 将精确分配所需大小。即使所请求容量仅比当前容量 多一个 limb,也会执行分配。
pub fn ensureCapacity(self: *Managed, capacity: usize) !void
参数
self: *Managed
capacity: usize
std.math.big.int.Managed.ensureMulCapacity
函数
若部分参数彼此互为别名,请在执行 mul 前使用此函数
pub fn ensureMulCapacity(rma: *Managed, a: *const Managed, b: *const Managed) !void
参数
std.math.big.int.Managed.ensureTwosCompCapacity
函数
pub fn ensureTwosCompCapacity(r: *Managed, bit_count: usize) !void
参数
r: *Managed
bit_count: usize
std.math.big.int.Managed.eql
函数
a == b 时返回 true。
pub fn eql(a: Managed, b: Managed) bool
参数
std.math.big.int.Managed.eqlAbs
函数
当 |a| == |b| 时返回 true。
pub fn eqlAbs(a: Managed, b: Managed) bool
参数
std.math.big.int.Managed.eqlZero
函数
若 a == 0,返回 true。
pub fn eqlZero(a: Managed) bool
参数
a: Managed
std.math.big.int.Managed.fits
函数
返回 self 是否可容纳于请求类型的整数。
pub fn fits(self: Managed, comptime T: type) bool
参数
self: Managed
T: type
std.math.big.int.Managed.fitsInTwosComp
函数
pub fn fitsInTwosComp(self: Managed, signedness: Signedness, bit_count: usize) bool
参数
std.math.big.int.Managed.format
函数
使 std.fmt.format 能与 Managed 配合使用。
pub fn format(self: Managed, w: *std.Io.Writer) std.Io.Writer.Error!void
参数
错误
- WriteFailed
详细诊断信息见
Writer实现。
std.math.big.int.Managed.formatNumber
函数
若整数的绝对值大于或等于 pow(2, 64 * @sizeOf(usize) * 8),
此函数无法打印数值字符串,改为输出 "(BigInt)"。
原因是渲染算法需要反转字符串,从而需要 O(N) 内存。
不会因此失败的大整数打印方式参见 toString 和 toStringAlloc。
pub fn formatNumber(self: Managed, w: *std.Io.Writer, n: std.fmt.Number) std.Io.Writer.Error!void
参数
错误
- WriteFailed
详细诊断信息见
Writer实现。
std.math.big.int.Managed.gcd
函数
rma 可与 x 或 y 互为别名。 x 与 y 可以互为别名。
使用 rma 的分配器提供临时存储,以提升乘法性能。
pub fn gcd(rma: *Managed, x: *const Managed, y: *const Managed) !void
参数
std.math.big.int.Managed.init
函数
创建新的 Managed。立即分配 default_capacity 个字。
初始化后的整数值为 0。
pub fn init(allocator: Allocator) !Managed
参数
allocator: Allocator
std.math.big.int.Managed.initCapacity
函数
创建具有指定容量的新 Managed。若 capacity < default_capacity,
则改用默认容量。
初始化后的整数值为 0。
pub fn initCapacity(allocator: Allocator, capacity: usize) !Managed
参数
allocator: Allocator
capacity: usize
std.math.big.int.Managed.initSet
函数
创建值为 value 的新 Managed。
等同于先调用 init,再调用 set。
pub fn initSet(allocator: Allocator, value: anytype) !Managed
参数
allocator: Allocator
std.math.big.int.Managed.isEven
函数
pub fn isEven(self: Managed) bool
参数
self: Managed
std.math.big.int.Managed.isOdd
函数
pub fn isOdd(self: Managed) bool
参数
self: Managed
std.math.big.int.Managed.isPositive
函数
返回 Managed 是否为正。
pub fn isPositive(self: Managed) bool
参数
self: Managed
std.math.big.int.Managed.len
函数
返回当前使用中的 limb 数量。
pub fn len(self: Managed) usize
参数
self: Managed
std.math.big.int.Managed.limbsAliasDistinct
函数
若两个不同的 Managed 参数共享同一个 limb 缓冲区,则为 true。
明确排除 @intFromPtr(a) == @intFromPtr(b) 的情况,即同一对象。
若两个指针指向同一个 Managed 实例,ensureCapacity 可在需要时重新分配缓冲区,而不会为该对象创建悬空指针。
fn limbsAliasDistinct(a: *const Managed, b: *const Managed) bool
参数
std.math.big.int.Managed.mul
函数
rma = a * b
rma、a 和 b 可以指向同一内存。不过,rma 不与 a 或 b 共用存储时效率更高。
无法分配内存时返回错误。
rma 的分配器用于临时存储,以加速乘法。
pub fn mul(rma: *Managed, a: *const Managed, b: *const Managed) !void
参数
std.math.big.int.Managed.mulWrap
函数
rma = a * b,采用二进制补码回绕语义。
rma、a 和 b 可以互为别名,但若 rma 不与 a 或 b 互为别名,效率更高。
无法分配内存时返回错误。
使用 rma 的分配器提供临时存储,以加快乘法。
pub fn mulWrap( rma: *Managed, a: *const Managed, b: *const Managed, signedness: Signedness, bit_count: usize, ) !void
参数
std.math.big.int.Managed.negate
函数
对符号取反。
pub fn negate(self: *Managed) void
参数
self: *Managed
std.math.big.int.Managed.normalize
函数
规范化可能存在的前导零序列。
[1, 2, 3, 4, 0] -> [1, 2, 3, 4] [1, 2, 0, 0, 0] -> [1, 2] [0, 0, 0, 0, 0] -> [0]
pub fn normalize(r: *Managed, length: usize) void
参数
r: *Managed
length: usize
std.math.big.int.Managed.order
函数
当 a < b、a == b 或 a > b 时,分别返回 math.Order.lt、math.Order.eq 或 math.Order.gt。
pub fn order(a: Managed, b: Managed) math.Order
参数
std.math.big.int.Managed.orderAbs
函数
当 |a| < |b|、|a| == |b| 或 |a| > |b| 时, 分别返回 math.Order.lt、math.Order.eq 或 math.Order.gt。
pub fn orderAbs(a: Managed, b: Managed) math.Order
参数
std.math.big.int.Managed.popCount
函数
r = @popCount(a),采用二进制补码语义。 r 和 a 可以是别名。
pub fn popCount(r: *Managed, a: *const Managed, bit_count: usize) !void
参数
std.math.big.int.Managed.pow
函数
pub fn pow(rma: *Managed, a: *const Managed, b: u32) !void
参数
std.math.big.int.Managed.saturate
函数
r = saturate(Int(signedness, bit_count), a)
pub fn saturate(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void
参数
std.math.big.int.Managed.set
函数
将 Managed 设置为 value。value 必须为基本整数类型。
pub fn set(self: *Managed, value: anytype) Allocator.Error!void
参数
self: *Managed
错误
- OutOfMemory
std.math.big.int.Managed.setLen
函数
设置 Managed 的长度。
如果使用 setLen,则必须相应地规范化 Managed。
pub fn setLen(self: *Managed, new_len: usize) void
参数
self: *Managed
new_len: usize
std.math.big.int.Managed.setMetadata
函数
pub fn setMetadata(self: *Managed, positive: bool, length: usize) void
参数
std.math.big.int.Managed.setSign
函数
设置 Managed 的符号。
pub fn setSign(self: *Managed, positive: bool) void
参数
self: *Managed
positive: bool
std.math.big.int.Managed.setString
函数
根据字符串表示 value 设置自身。
value 只能包含不大于 base 的数字,且不区分大小写。不允许进制前缀,例如 0x43 应直接写作 43。输入字符串中的下划线会被忽略,可用作数字分隔符。
若无法分配内存,或 value 中包含对指定进制无效的数字,则返回错误。
使用自身的分配器提供临时存储,以提升乘法性能。
pub fn setString(self: *Managed, base: u8, value: []const u8) !void
参数
std.math.big.int.Managed.setTwosCompIntLimit
函数
将 self 设为二进制补码整数的上界或下界。 注意:结果仍采用符号数值表示,而非二进制补码!要将结果转换为 二进制补码,只需取其绝对值。
pub fn setTwosCompIntLimit( r: *Managed, limit: TwosCompIntLimit, signedness: Signedness, bit_count: usize, ) !void
参数
std.math.big.int.Managed.shiftLeft
函数
r = a << shift,即 r = a * 2^shift r 和 a 可以互为别名。
pub fn shiftLeft(r: *Managed, a: *const Managed, shift: usize) !void
参数
std.math.big.int.Managed.shiftLeftSat
函数
r = a <<| shift,采用二进制补码饱和语义。 r 和 a 可以互为别名。
pub fn shiftLeftSat(r: *Managed, a: *const Managed, shift: usize, signedness: Signedness, bit_count: usize) !void
参数
std.math.big.int.Managed.shiftRight
函数
r = a >> shift r 和 a 可以互为别名。
pub fn shiftRight(r: *Managed, a: *const Managed, shift: usize) !void
参数
std.math.big.int.Managed.sign_bit
常量
usize
std.math.big.int.Managed.sizeInBaseUpperBound
函数
返回给定进制下整数的近似大小。负值会为负号留出空间。 此值用于确定打印该值所需的字符数。它并不精确, 可能比给定值多出约 1 至 2 字节。
pub fn sizeInBaseUpperBound(self: Managed, base: usize) usize
参数
self: Managed
base: usize
std.math.big.int.Managed.sqr
函数
r = a * a
pub fn sqr(rma: *Managed, a: *const Managed) !void
参数
std.math.big.int.Managed.sqrt
函数
r = ⌊√a⌋
pub fn sqrt(rma: *Managed, a: *const Managed) !void
参数
std.math.big.int.Managed.sub
函数
r = a - b
r、a 和 b 可以是别名。
若无法分配内存则返回错误。
pub fn sub(r: *Managed, a: *const Managed, b: *const Managed) !void
参数
std.math.big.int.Managed.subSat
函数
r = a - b,采用二进制补码饱和语义。
r、a 和 b 可以互为别名。
若无法分配内存,则返回错误。
pub fn subSat( r: *Managed, a: *const Managed, b: *const Managed, signedness: Signedness, bit_count: usize, ) Allocator.Error!void
参数
错误
- OutOfMemory
std.math.big.int.Managed.subWrap
函数
r = a - b,采用二进制补码回绕语义。返回是否发生溢出。
r、a 和 b 可以互为别名。
若无法分配内存,则返回错误。
pub fn subWrap( r: *Managed, a: *const Managed, b: *const Managed, signedness: Signedness, bit_count: usize, ) Allocator.Error!bool
参数
错误
- OutOfMemory
std.math.big.int.Managed.swap
函数
高效地交换两个 Managed。仅交换 limb 指针,不执行完整复制。
调用此函数后,limbs 字段的地址将发生变化。
pub fn swap(self: *Managed, other: *Managed) void
参数
std.math.big.int.Managed.toConst
函数
pub fn toConst(self: Managed) Const
参数
self: Managed
std.math.big.int.Managed.toFloat
类型函数
将 self 转换为 Float。
pub fn toFloat(self: Managed, comptime Float: type, round: Round) struct { Float, Exactness }
参数
std.math.big.int.Managed.toInt
函数
将 self 转换为 Int。
若无法在不截断的情况下将 self 缩窄为请求类型,则返回错误。
pub fn toInt(self: Managed, comptime Int: type) ConvertError!Int
参数
self: Managed
Int: type
错误
- NegativeIntoUnsigned ConvertError
- TargetTooSmall ConvertError
std.math.big.int.Managed.toMutable
函数
pub fn toMutable(self: Managed) Mutable
参数
self: Managed
std.math.big.int.Managed.toString
函数
将 self 转换为指定基数的字符串。内存由提供的分配器分配,而不是 self 中的分配器。
pub fn toString(self: Managed, allocator: Allocator, base: u8, case: std.fmt.Case) ![]u8
参数
std.math.big.int.Managed.truncate
函数
r = truncate(Int(signedness, bit_count), a)
pub fn truncate(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void
参数
std.math.big.int.math
别名
别名目标 std.math
std.math.big.int.maxInt
别名
别名目标 std.math.maxInt
std.math.big.int.mem
别名
别名目标 std.mem
std.math.big.int.minInt
别名
别名目标 std.math.minInt
std.math.big.int.Mutable
容器
任意精度大整数,具有固定的一组可变数位。
字段
limbs: []Limb原始数位,满足:
- 按小端序排列
- limbs.len >= 1
- 零表示为 limbs.len == 1 且 limbs[0] == 0。
应避免直接访问 limbs。
这些是已分配的 limb;len 字段给出有效范围。
len: usize
positive: bool
toConstConvertErrortoInttoFloateqlZerotoManagedinitcopyswapdumpclonenegateabssetsetStringsetTwosCompIntLimitsetFloataddScalaraddCarryaddaddWrapaddSatsubCarrysubsubWrapsubSatmulmulNoAliasmulWrapmulWrapNoAliasbitReversebyteSwappopCountsqrNoAliasdivFloordivCeildivTruncshiftLeftshiftLeftSatshiftRightbitNotWrapbitOrbitAndbitXorgcdpowsqrtgcdNoAliasgcdLehmerdivdivmodtruncatesaturatereadTwosComplementreadPackedTwosComplementnormalizeformatformatNumber
std.math.big.int.Mutable.abs
函数
修改为绝对值
pub fn abs(self: *Mutable) void
参数
self: *Mutable
std.math.big.int.Mutable.add
函数
r = a + b
r、a 和 b 可以共用存储。
断言结果可存入 r。r 所需 limb 数量的上界为
@max(a.limbs.len, b.limbs.len) + 1。
pub fn add(r: *Mutable, a: Const, b: Const) void
参数
std.math.big.int.Mutable.addCarry
函数
加法的基础实现。将 a 和 b 的 @max(a.limbs.len, b.limbs.len) 个元素相加,
返回是否发生溢出。
r、a 和 b 可以互为别名。
断言 r 有足够元素容纳结果。上界为 @max(a.limbs.len, b.limbs.len)。
fn addCarry(r: *Mutable, a: Const, b: Const) bool
参数
std.math.big.int.Mutable.addSat
函数
r = a + b,采用二进制补码饱和语义。 r、a 和 b 可以共用存储。
断言结果可存入 r。r 所需 limb 数量的上界为
calcTwosCompLimbCount(bit_count)。
pub fn addSat(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) void
参数
std.math.big.int.Mutable.addScalar
函数
r = a + scalar
r 和 a 可以互为别名。 scalar 是基本整数类型。
断言结果能放入 r。r 所需数位数量的上界为
@max(a.limbs.len, calcLimbLen(scalar)) + 1。
pub fn addScalar(r: *Mutable, a: Const, scalar: anytype) void
参数
std.math.big.int.Mutable.addWrap
函数
r = a + b,采用二进制补码回绕语义。返回是否发生溢出。 r、a 和 b 可以互为别名。
断言结果可放入 r。r 所需 limb 数的上界为
calcTwosCompLimbCount(bit_count)。
pub fn addWrap(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) bool
参数
std.math.big.int.Mutable.bitAnd
函数
按二进制补码语义计算 r = a & b。 r 可以与 a 或 b 互为别名。
断言 r 具有足够的 limb 存储结果。
如果只有 a 为正,上界为 a.limbs.len。
如果只有 b 为正,上界为 b.limbs.len。
如果 a 和 b 都为正,上界为 @min(a.limbs.len, b.limbs.len)。
如果 a 和 b 都为负,上界为 @max(a.limbs.len, b.limbs.len) + 1。
pub fn bitAnd(r: *Mutable, a: Const, b: Const) void
参数
std.math.big.int.Mutable.bitNotWrap
函数
r = ~a,采用二进制补码回绕语义。 r 可以与 a 互为别名。
断言 r 有足够的 limb 存储结果。r 所需 limb 数的上界为
calcTwosCompLimbCount(bit_count)。
pub fn bitNotWrap(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void
参数
std.math.big.int.Mutable.bitOr
函数
r = a | b,采用二进制补码语义。 r 可以与 a 或 b 共用存储。
a 和 b 会零扩展到二者中较长者的长度。
断言 r 有足够的 limb 存储结果。上界为 @max(a.limbs.len, b.limbs.len)。
pub fn bitOr(r: *Mutable, a: Const, b: Const) void
参数
std.math.big.int.Mutable.bitReverse
函数
r = @bitReverse(a),采用二进制补码语义。 r 与 a 可以互为别名。
断言结果能放入 r。r 所需 limb 数的上界为
calcTwosCompLimbCount(bit_count)。
pub fn bitReverse(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void
参数
std.math.big.int.Mutable.bitXor
函数
r = a ^ b,采用二进制补码语义。 r 可以与 a 或 b 共用存储。
断言 r 有足够的 limb 存储结果。如果 a 和 b 的符号属性相同,
上界为 @max(a.limbs.len, b.limbs.len)。否则,如果 a 和 b 中
恰有一个为负,上界为 @max(a.limbs.len, b.limbs.len) + 1。
pub fn bitXor(r: *Mutable, a: Const, b: Const) void
参数
std.math.big.int.Mutable.byteSwap
函数
r = @byteSwap(a),采用二进制补码语义。 r 和 a 可以共用存储。
断言结果可存入 r。r 所需 limb 数量的上界为
calcTwosCompLimbCount(8*byte_count)。
pub fn byteSwap(r: *Mutable, a: Const, signedness: Signedness, byte_count: usize) void
参数
std.math.big.int.Mutable.clone
函数
克隆一个 Mutable,返回值相同的新 Mutable。新 Mutable 是深拷贝, 可独立于原对象修改。 断言 limbs 足以存储该值。
pub fn clone(other: Mutable, limbs: []Limb) Mutable
参数
std.math.big.int.Mutable.ConvertError
别名
std.math.big.int.Mutable.copy
函数
将 Const 的值复制到已有 Mutable,使两者具有相同值。 断言该值可容纳于 limb 缓冲区中。
pub fn copy(self: *Mutable, other: Const) void
参数
std.math.big.int.Mutable.div
函数
fn div(q: *Mutable, r: *Mutable, x: *Mutable, y: *Mutable) void
参数
std.math.big.int.Mutable.divCeil
函数
q = a / b (rem r)
a / b 向上取整(向 +inf 舍入)。 q 可以与 a 或 b 共用存储。
断言存在足够的内存存储 q 和 r。
r 的 limb 数量上界为 b.limbs.len。
q 的 limb 数量上界由 a.limbs 给出。
limbs_buffer 用作临时存储。所需大小由 calcDivLimbsBufferLen 给出。
pub fn divCeil( q: *Mutable, r: *Mutable, a: Const, b: Const, limbs_buffer: []Limb, ) void
参数
std.math.big.int.Mutable.divFloor
函数
q = a / b(余数为 r)。
a / b 取整,向零舍入。 q 可以与 a 或 b 互为别名。
断言内存足以存储 q 和 r。
r 的 limb 数量上界为 b.limbs.len。
q 的 limb 数量上界由 a.limbs 给出。
limbs_buffer 用作临时存储,所需数量由 calcDivLimbsBufferLen 给出。
pub fn divFloor( q: *Mutable, r: *Mutable, a: Const, b: Const, limbs_buffer: []Limb, ) void
参数
std.math.big.int.Mutable.divmod
函数
《应用密码学手册》,14.20
x = qy + r,其中 0 <= r < y y 会被修改,但返回时恢复原状。
fn divmod( q: *Mutable, r: *Mutable, x: *Mutable, y: *Mutable, ) void
参数
std.math.big.int.Mutable.divTrunc
函数
q = a / b,余数为 r。
a / b 按向负无穷方向取整。 q 可以与 a 或 b 互为别名。
断言具有足够内存存储 q 和 r。
r 的 limb 数上界为 b.limbs.len。
q 的 limb 数上界为 a.limbs.len。
limbs_buffer 用作临时存储,所需大小由 calcDivLimbsBufferLen 给出。
pub fn divTrunc( q: *Mutable, r: *Mutable, a: Const, b: Const, limbs_buffer: []Limb, ) void
参数
std.math.big.int.Mutable.dump
函数
pub fn dump(self: Mutable) void
参数
self: Mutable
std.math.big.int.Mutable.eqlZero
函数
若 a == 0 则返回 true。
pub fn eqlZero(self: Mutable) bool
参数
self: Mutable
std.math.big.int.Mutable.format
函数
pub fn format(self: Mutable, w: *std.Io.Writer) std.Io.Writer.Error!void
参数
错误
- WriteFailed
详细诊断信息见
Writer实现。
std.math.big.int.Mutable.formatNumber
函数
若整数的绝对值大于或等于 pow(2, 64 * @sizeOf(usize) * 8),
此函数无法打印数值字符串,改为输出 "(BigInt)"。
原因是渲染算法需要反转字符串,从而需要 O(N) 内存。
不会因此失败的大整数打印方式参见 Const.toString 和 Const.toStringAlloc。
pub fn formatNumber(self: Mutable, w: *std.Io.Writer, n: std.fmt.Number) std.Io.Writer.Error!void
参数
错误
- WriteFailed
详细诊断信息见
Writer实现。
std.math.big.int.Mutable.gcd
函数
rma 可以与 x 或 y 共用存储。
x 和 y 可以彼此共用存储。
断言 rma 有足够的 limb 存储结果。上界为
@min(x.limbs.len, y.limbs.len)。
limbs_buffer 在操作期间用作临时存储。此函数返回时,
其长度与调用函数时相同。
pub fn gcd(rma: *Mutable, x: Const, y: Const, limbs_buffer: *std.array_list.Managed(Limb)) !void
参数
std.math.big.int.Mutable.gcdLehmer
函数
fn gcdLehmer(result: *Mutable, xa: Const, ya: Const, limbs_buffer: *std.array_list.Managed(Limb)) !void
参数
std.math.big.int.Mutable.gcdNoAlias
函数
rma 不得与 x 或 y 互为别名。
x 和 y 可以互为别名。
断言 rma 有足够的 limb 存储结果,上界由 calcGcdNoAliasLimbLen 给出。
limbs_buffer 在操作期间用作临时存储。
pub fn gcdNoAlias(rma: *Mutable, x: Const, y: Const, limbs_buffer: *std.array_list.Managed(Limb)) !void
参数
std.math.big.int.Mutable.init
函数
value 是基本整数类型。
断言该值可存入所提供的 limbs_buffer。
注意:可使用 calcLimbLen 确定应为 limbs_buffer 分配多大的数组。
pub fn init(limbs_buffer: []Limb, value: anytype) Mutable
参数
limbs_buffer: []Limb
std.math.big.int.Mutable.mul
函数
rma = a * b
rma 可以与 a 或 b 互为别名。
a 和 b 可以互为别名。
断言结果可容纳于 rma。rma 所需 limb 数的
上界为 a.limbs.len + b.limbs.len。
limbs_buffer 用于临时存储,所需大小由 calcMulLimbsBufferLen 给出。
pub fn mul(rma: *Mutable, a: Const, b: Const, limbs_buffer: []Limb, allocator: ?Allocator) void
参数
std.math.big.int.Mutable.mulNoAlias
函数
rma = a * b
rma 不得与 a 或 b 别名。
a 和 b 可以互相别名。
断言结果可容纳于 rma。rma 所需 limb 数
的上界为 a.limbs.len + b.limbs.len。
若提供 allocator,则用于临时存储,以提升
乘法性能。遇到 error.OutOfMemory 时使用回退算法。
pub fn mulNoAlias(rma: *Mutable, a: Const, b: Const, allocator: ?Allocator) void
参数
std.math.big.int.Mutable.mulWrap
函数
rma = a * b,采用二进制补码回绕语义。
rma 可以与 a 或 b 别名。
a 和 b 可以互相别名。
断言结果可容纳于 rma。rma 所需 limb 数
的上界为 a.limbs.len + b.limbs.len。
limbs_buffer 用于临时存储,所需大小由 calcMulWrapLimbsBufferLen 给出。
pub fn mulWrap( rma: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize, limbs_buffer: []Limb, allocator: ?Allocator, ) void
参数
std.math.big.int.Mutable.mulWrapNoAlias
函数
rma = a * b,采用二进制补码回绕语义。
rma 不得与 a 或 b 互为别名。
a 和 b 可以互为别名。
断言结果能够放入 rma。所需 limb 数量的上界为 a.limbs.len + b.limbs.len。
若提供 allocator,则用于临时存储,以提升乘法性能。出现 error.OutOfMemory 时,会使用后备算法处理。
pub fn mulWrapNoAlias( rma: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize, allocator: ?Allocator, ) void
参数
std.math.big.int.Mutable.negate
函数
pub fn negate(self: *Mutable) void
参数
self: *Mutable
std.math.big.int.Mutable.normalize
函数
规范化可能存在的前导零序列。
[1, 2, 3, 4, 0] -> [1, 2, 3, 4] [1, 2, 0, 0, 0] -> [1, 2] [0, 0, 0, 0, 0] -> [0]
pub fn normalize(r: *Mutable, length: usize) void
参数
r: *Mutable
length: usize
std.math.big.int.Mutable.popCount
函数
r = @popCount(a),采用二进制补码语义。 r 与 a 可以互为别名。
断言结果能放入 r。r 所需 limb 数的上界为
calcTwosCompLimbCount(bit_count)。
pub fn popCount(r: *Mutable, a: Const, bit_count: usize) void
参数
std.math.big.int.Mutable.pow
函数
q = a ^ b
r 不得与 a 互为别名。
断言 r 有足够的 limb 存储结果。上界为
calcPowLimbsBufferLen(a.bitCountAbs(), b)。
limbs_buffer 用作临时存储。
所需大小由 calcPowLimbsBufferLen 给出。
pub fn pow(r: *Mutable, a: Const, b: u32, limbs_buffer: []Limb) void
参数
std.math.big.int.Mutable.readPackedTwosComplement
函数
从打包内存 buffer 读取 x 的值。
断言 buffer 足够大,能够在偏移量 bit_offset 处
容纳位大小为 bit_count 的值。
等同于加载一个 bit_count 位整数,
将其视为打包内存中给定位偏移处的字段。
pub fn readPackedTwosComplement( x: *Mutable, buffer: []const u8, bit_offset: usize, bit_count: usize, endian: Endian, signedness: Signedness, ) void
参数
x: *Mutable
buffer: []const u8
bit_offset: usize
bit_count: usize
endian: Endian
signedness: Signedness
std.math.big.int.Mutable.readTwosComplement
函数
从 buffer 读取 x 的值。
断言 buffer 足以容纳位宽为 bit_count 的值。
解释 buffer 内容时,将其视为
@ptrCast(*[buffer.len]const u8, &x) 的内容。字节顺序由 endian 决定,
任何必要的填充位都应位于最高有效位一端。
pub fn readTwosComplement( x: *Mutable, buffer: []const u8, bit_count: usize, endian: Endian, signedness: Signedness, ) void
参数
std.math.big.int.Mutable.saturate
函数
遵循二进制补码语义,将整数饱和到指定比特数。 r 可以与 a 互为别名。
断言 r 有足够存储空间容纳结果。
上界为 calcTwosCompLimbCount(a.len)。
pub fn saturate(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void
参数
std.math.big.int.Mutable.set
函数
将 Mutable 设置为 value。value 必须为基本整数类型。
断言该值可放入 limb 缓冲区。
注意:可用 calcLimbLen 确定存储某个值
所需的 limb 缓冲区大小。
pub fn set(self: *Mutable, value: anytype) void
参数
self: *Mutable
std.math.big.int.Mutable.setFloat
函数
将 Mutable 设置为按 round 舍入的浮点值。
返回转换是否精确(即 round 未影响结果)。
pub fn setFloat(self: *Mutable, value: anytype, round: Round) Exactness
参数
std.math.big.int.Mutable.setString
函数
根据字符串表示 value 设置自身。
value 只能包含不大于 base 的数字,且不区分大小写。不允许进制前缀,例如 0x43 应直接写作 43。输入字符串中的下划线会被忽略,可用作数字分隔符。
self.limbs 必须有足够内存容纳该值。可使用 calcSetStringLimbCount 确定所需 limb 数量的上界。
断言进制处于 [2, 36] 范围。
若值中包含对指定进制无效的数字,返回错误。
pub fn setString( self: *Mutable, base: u8, value: []const u8, ) error{InvalidCharacter}!void
参数
错误
- InvalidCharacter
std.math.big.int.Mutable.setTwosCompIntLimit
函数
将 self 设为二进制补码整数的任一边界值。 注意:结果仍为符号与绝对值表示,而非二进制补码!要将结果 转换为二进制补码,取绝对值即可。
断言结果可容纳于 r。r 所需 limb 数量的
上界为 calcTwosCompLimbCount(bit_count)。
pub fn setTwosCompIntLimit( r: *Mutable, limit: TwosCompIntLimit, signedness: Signedness, bit_count: usize, ) void
参数
std.math.big.int.Mutable.shiftLeft
函数
r = a << shift,即 r = a * 2^shift。
r 和 a 可以互为别名。
断言内存足以容纳结果。limb 数上界为
a.limbs.len + (shift / (@sizeOf(Limb) * 8))。
pub fn shiftLeft(r: *Mutable, a: Const, shift: usize) void
参数
std.math.big.int.Mutable.shiftLeftSat
函数
r = a <<| shift,采用二进制补码饱和语义。
r 和 a 可以互为别名。
断言有足够内存存放结果。r 所需 limb 数的上界为
calcTwosCompLimbCount(bit_count)。
pub fn shiftLeftSat(r: *Mutable, a: Const, shift: usize, signedness: Signedness, bit_count: usize) void
参数
std.math.big.int.Mutable.shiftRight
函数
r = a >> shift r 和 a 可以互为别名。
断言内存足以容纳结果。limb 数上界为
a.limbs.len - (shift / (@bitSizeOf(Limb)))。
pub fn shiftRight(r: *Mutable, a: Const, shift: usize) void
参数
std.math.big.int.Mutable.sqrNoAlias
函数
rma = a * a
rma 不得与 a 互为别名。
断言结果可容纳于 rma。rma 所需 limb 数量的
上界为 2 * a.limbs.len + 1。
如果提供 allocator,则将其用于临时存储以提高
乘法性能。遇到 error.OutOfMemory 时采用后备算法。
pub fn sqrNoAlias(rma: *Mutable, a: Const, opt_allocator: ?Allocator) void
参数
std.math.big.int.Mutable.sqrt
函数
r = ⌊√a⌋
r 可以与 a 共用存储。
断言 r 有足够的 limb 存储结果。上界为
(a.limbs.len - 1) / 2 + 1。
limbs_buffer 用作临时存储。
所需大小由 calcSqrtLimbsBufferLen 给出。
pub fn sqrt( r: *Mutable, a: Const, limbs_buffer: []Limb, ) void
参数
std.math.big.int.Mutable.sub
函数
r = a - b
r、a 和 b 可以互为别名。
断言结果能放入 r。r 所需数位数量的上界为
@max(a.limbs.len, b.limbs.len) + 1。若两操作数均为正,则不需要 +1。
pub fn sub(r: *Mutable, a: Const, b: Const) void
参数
std.math.big.int.Mutable.subCarry
函数
减法的基础实现。从 a 和 b 减去 @max(a.limbs.len, b.limbs.len) 个元素,并返回是否发生溢出。
r、a 和 b 可以互为别名。
断言 r 的元素数量足以容纳结果,上界为 @max(a.limbs.len, b.limbs.len)。
fn subCarry(r: *Mutable, a: Const, b: Const) bool
参数
std.math.big.int.Mutable.subSat
函数
r = a - b,采用二进制补码饱和语义。 r、a 和 b 可以互为别名。
断言结果能放入 r。r 所需 limb 数的上界为
calcTwosCompLimbCount(bit_count)。
pub fn subSat(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) void
参数
std.math.big.int.Mutable.subWrap
函数
r = a - b,采用二进制补码回绕语义。返回是否发生溢出。
r、a 和 b 可以指向同一内存。
断言结果可存入 r。r 所需 limb 数量的上界为
calcTwosCompLimbCount(bit_count)。
pub fn subWrap(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) bool
参数
std.math.big.int.Mutable.swap
函数
高效交换两个 Mutable。此操作交换 limb 指针,不执行完整拷贝。 调用此函数后,limbs 字段存放的地址将不再相同。
pub fn swap(self: *Mutable, other: *Mutable) void
参数
std.math.big.int.Mutable.toConst
函数
pub fn toConst(self: Mutable) Const
参数
self: Mutable
std.math.big.int.Mutable.toFloat
类型函数
将 self 转换为 Float。
pub fn toFloat(self: Mutable, comptime Float: type, round: Round) struct { Float, Exactness }
参数
std.math.big.int.Mutable.toInt
函数
将 self 转换为 Int。
若无法在不截断的情况下将 self 缩窄为请求类型,则返回错误。
pub fn toInt(self: Mutable, comptime Int: type) ConvertError!Int
参数
self: Mutable
Int: type
错误
- NegativeIntoUnsigned ConvertError
- TargetTooSmall ConvertError
std.math.big.int.Mutable.toManaged
函数
断言分配器拥有 limbs 内存。
若非如此,请使用 toConst().toManaged()。
pub fn toManaged(self: Mutable, allocator: Allocator) Managed
参数
std.math.big.int.Mutable.truncate
函数
遵循二进制补码语义,将整数截断到指定比特数。
r 可以与 a 互为别名。
断言 r 有足够存储空间计算结果。
上界为 calcTwosCompLimbCount(a.len)。
pub fn truncate(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void
参数
std.math.big.int.native_endian
常量
std.math.big.int.Round
容器
字段
nearest_even舍入到最近的可表示值;距离相同时,选择 最低位为 0 的表示。
away向远离零的方向舍入。
trunc向零舍入。
floor向负无穷方向取整。
ceil向正无穷大舍入。
std.math.big.int.SignedDoubleLimb
别名
std.math.big.int.Signedness
别名
别名目标 std.lang.Signedness
std.math.big.int.slicesOverlap
函数
fn slicesOverlap(a: []const Limb, b: []const Limb) bool
参数
std.math.big.int.std
别名
别名目标 std
std.math.big.int.subMulLimbWithBorrow
函数
a - b * c - *carry,将 carry 设为溢出的位
fn subMulLimbWithBorrow(a: Limb, b: Limb, c: Limb, carry: *Limb) Limb
参数
std.math.big.int.testFormat
函数
fn testFormat(a: Managed, expected: []const u8) !void
参数
a: Managed
expected: []const u8
std.math.big.int.testing_allocator
别名
std.math.big.int.testOneShiftCase
函数
fn testOneShiftCase(comptime function: enum { llshr, llshl }, case: Case) !void
参数
std.math.big.int.testOneShiftCaseAliasing
函数
fn testOneShiftCaseAliasing(func: fn ([]Limb, []const Limb, usize) usize, case: Case, shift_direction: isize) !void
参数
std.math.big.int.testOneShiftCaseNoAliasing
函数
fn testOneShiftCaseNoAliasing(func: fn ([]Limb, []const Limb, usize) usize, case: Case) !void
参数
std.math.big.int.TwosCompIntLimit
容器
用于表示二进制补码整数的任一边界值。
字段
min
max
源码
std/math/big/int.zig
const std = @import("../../std.zig");
const builtin = @import("builtin");
const math = std.math;
const Limb = std.math.big.Limb;
const limb_bits = @typeInfo(Limb).int.bits;
const HalfLimb = std.math.big.HalfLimb;
const half_limb_bits = @typeInfo(HalfLimb).int.bits;
const DoubleLimb = std.math.big.DoubleLimb;
const SignedDoubleLimb = std.math.big.SignedDoubleLimb;
const Log2Limb = std.math.big.Log2Limb;
const Allocator = std.mem.Allocator;
const mem = std.mem;
const maxInt = std.math.maxInt;
const minInt = std.math.minInt;
const assert = std.debug.assert;
const Endian = std.builtin.Endian;
const Signedness = std.builtin.Signedness;
const native_endian = builtin.cpu.arch.endian();
// 针对支持的进制(2 - 36)在编译期计算的常量。
// 对进制 0 - 1,所有值均设为 0,以便通过
// `constants.value[b]` 访问给定进制 b 的常量。
const Constants = struct {
// big_bases[b] 是能放入单个 Limb 的最大 b 的幂,
// 即 big_bases[b] = b^k < 2^@bitSizeOf(Limb),且 b^(k+1) >= 2^@bitSizeOf(Limb)。
big_bases: [37]Limb,
// digits_per_limb[b] 为前一字段使用的 k 值
digits_per_limb: [37]u8,
};
const constants: Constants = blk: {
@setEvalBranchQuota(2000);
var digits_per_limb: [37]u8 = @splat(0);
var bases: [37]Limb = @splat(0);
for (2..37) |base| {
digits_per_limb[base] = @intCast(math.log(Limb, base, math.maxInt(Limb)));
bases[base] = std.math.pow(Limb, base, digits_per_limb[base]);
}
break :blk Constants{ .big_bases = bases, .digits_per_limb = digits_per_limb };
};
/// 返回存储 `scalar` 所需的 limb 数量;该值必须是
/// 基本整数或浮点数。
/// 注意:如果 `scalar` 并非编译时已知,可以改用
/// 此值的编译时已知上界:
/// `calcTwosCompLimbCount(@typeInfo(@TypeOf(scalar)).int.bits)`
pub fn calcLimbLen(scalar: anytype) usize {
switch (@typeInfo(@TypeOf(scalar))) {
.int, .comptime_int => {
if (scalar == 0) return 1;
const w_value = @abs(scalar);
return @as(usize, @intCast(@divFloor(@as(Limb, @intCast(math.log2(w_value))), limb_bits) + 1));
},
.float => {
const repr: std.math.FloatRepr(@TypeOf(scalar)) = @bitCast(scalar);
return switch (repr.exponent) {
.denormal => 1,
else => return calcNonZeroTwosCompLimbCount(@as(usize, 2) + @max(repr.exponent.unbias(), 0)),
.infinite => 0,
};
},
.comptime_float => return calcLimbLen(@as(f128, scalar)),
else => @compileError("expected float or int, got " ++ @typeName(@TypeOf(scalar))),
}
}
/// 与 `calcToStringLimbsBufferLen` 相同,但不进行无用的基数检查。
pub fn calcLog10LimbsBufferLen(a_len: usize) usize {
return a_len + 2 + a_len + calcDivLimbsBufferLen(a_len, 1);
}
pub fn calcToStringLimbsBufferLen(a_len: usize, base: u8) usize {
if (math.isPowerOfTwo(base))
return 0;
return a_len + 2 + a_len + calcDivLimbsBufferLen(a_len, 1);
}
pub fn calcDivLimbsBufferLen(a_len: usize, b_len: usize) usize {
return a_len + b_len + 4;
}
pub fn calcMulLimbsBufferLen(a_len: usize, b_len: usize, aliases: usize) usize {
return aliases * @max(a_len, b_len);
}
pub fn calcMulWrapLimbsBufferLen(bit_count: usize, a_len: usize, b_len: usize, aliases: usize) usize {
const req_limbs = calcTwosCompLimbCount(bit_count);
return aliases * @min(req_limbs, @max(a_len, b_len));
}
pub fn calcSetStringLimbsBufferLen(base: u8, string_len: usize) usize {
const limb_count = calcSetStringLimbCount(base, string_len);
return calcMulLimbsBufferLen(limb_count, limb_count, 2);
}
/// 假定数为负数时,`string_len` 不包含负号。
pub fn calcSetStringLimbCount(base: u8, string_len: usize) usize {
const base_f: f32 = @floatFromInt(base);
const string_len_f: f32 = @floatFromInt(string_len);
return 1 + @as(usize, @intFromFloat(@ceil(string_len_f * std.math.log2(base_f) / limb_bits)));
}
pub fn calcPowLimbsBufferLen(a_bit_count: usize, y: usize) usize {
// 其中的 2 用于满足 llmulacc 的最小空间要求
return 2 + (a_bit_count * y + (limb_bits - 1)) / limb_bits;
}
pub fn calcSqrtLimbsBufferLen(a_bit_count: usize) usize {
const a_limb_count = (a_bit_count - 1) / limb_bits + 1;
const shift = (a_bit_count + 1) / 2;
const u_s_rem_limb_count = 1 + ((shift / limb_bits) + 1);
return a_limb_count + 3 * u_s_rem_limb_count + calcDivLimbsBufferLen(a_limb_count, u_s_rem_limb_count);
}
/// 计算存储一个 `bit_count` 位的二进制补码数所需的数位数量。
pub fn calcNonZeroTwosCompLimbCount(bit_count: usize) usize {
assert(bit_count != 0);
return calcTwosCompLimbCount(bit_count);
}
/// 计算存储 `bit_count` 位二进制补码数所需的 limb 数量。
///
/// 特殊处理 `bit_count == 0`,此时返回 1。零位整数只能存储零值,
/// 而此大整数实现使用一个 limb 存储零。
pub fn calcTwosCompLimbCount(bit_count: usize) usize {
return @max(@divCeil(bit_count, @bitSizeOf(Limb)), 1);
}
/// a + b * c + *carry,将 carry 设置为溢出的位。
pub fn addMulLimbWithCarry(a: Limb, b: Limb, c: Limb, carry: *Limb) Limb {
// ov1[0] = a + *carry
const ov1 = @addWithOverflow(a, carry.*);
// r2 = b * c
const bc = @as(DoubleLimb, math.mulWide(Limb, b, c));
const r2 = @as(Limb, @truncate(bc));
const c2 = @as(Limb, @truncate(bc >> limb_bits));
// ov2[0] = ov1[0] + r2
const ov2 = @addWithOverflow(ov1[0], r2);
// 此处绝不会溢出:c1 和 c3 均为 0 或 1;若两者都为 1,
// 则 c2 至少满足 <= maxInt(Limb) - 2。
carry.* = ov1[1] + c2 + ov2[1];
return ov2[0];
}
/// a - b * c - *carry,将 carry 设为溢出的位
fn subMulLimbWithBorrow(a: Limb, b: Limb, c: Limb, carry: *Limb) Limb {
// ov1[0] = a - *carry
const ov1 = @subWithOverflow(a, carry.*);
// r2 = b * c
const bc = @as(DoubleLimb, std.math.mulWide(Limb, b, c));
const r2 = @as(Limb, @truncate(bc));
const c2 = @as(Limb, @truncate(bc >> limb_bits));
// ov2[0] = ov1[0] - r2
const ov2 = @subWithOverflow(ov1[0], r2);
carry.* = ov1[1] + c2 + ov2[1];
return ov2[0];
}
/// 用于表示二进制补码整数的任一边界值。
pub const TwosCompIntLimit = enum {
// 8 位整数的下限:无符号时为 0x00,有符号时为 (-)0x80。
min,
// 上限;对于 8 位整数,无符号时为 0xFF,有符号时为 0x7F。
max,
};
pub const Round = enum {
/// 舍入到最近的可表示值;距离相同时,选择
/// 最低位为 0 的表示。
nearest_even,
/// 向远离零的方向舍入。
away,
/// 向零舍入。
trunc,
/// 向负无穷方向取整。
floor,
/// 向正无穷大舍入。
ceil,
};
pub const Exactness = enum { inexact, exact };
/// 任意精度大整数,具有固定的一组可变数位。
pub const Mutable = struct {
/// 原始数位,满足:
///
/// * 按小端序排列
/// * limbs.len >= 1
/// * 零表示为 limbs.len == 1 且 limbs[0] == 0。
///
/// 应避免直接访问 limbs。
/// 这些是已分配的 limb;`len` 字段给出有效范围。
limbs: []Limb,
len: usize,
positive: bool,
pub fn toConst(self: Mutable) Const {
return .{
.limbs = self.limbs[0..self.len],
.positive = self.positive,
};
}
pub const ConvertError = Const.ConvertError;
/// 将 `self` 转换为 `Int`。
///
/// 若无法在不截断的情况下将 self 缩窄为请求类型,则返回错误。
pub fn toInt(self: Mutable, comptime Int: type) ConvertError!Int {
return self.toConst().toInt(Int);
}
/// 将 `self` 转换为 `Float`。
pub fn toFloat(self: Mutable, comptime Float: type, round: Round) struct { Float, Exactness } {
return self.toConst().toFloat(Float, round);
}
/// 若 `a == 0` 则返回 true。
pub fn eqlZero(self: Mutable) bool {
return self.toConst().eqlZero();
}
/// 断言分配器拥有 limbs 内存。
/// 若非如此,请使用 `toConst().toManaged()`。
pub fn toManaged(self: Mutable, allocator: Allocator) Managed {
return .{
.allocator = allocator,
.limbs = self.limbs,
.metadata = if (self.positive)
self.len & ~Managed.sign_bit
else
self.len | Managed.sign_bit,
};
}
/// `value` 是基本整数类型。
/// 断言该值可存入所提供的 `limbs_buffer`。
/// 注意:可使用 `calcLimbLen` 确定应为 `limbs_buffer` 分配多大的数组。
pub fn init(limbs_buffer: []Limb, value: anytype) Mutable {
limbs_buffer[0] = 0;
var self: Mutable = .{
.limbs = limbs_buffer,
.len = 1,
.positive = true,
};
self.set(value);
return self;
}
/// 将 Const 的值复制到已有 Mutable,使两者具有相同值。
/// 断言该值可容纳于 limb 缓冲区中。
pub fn copy(self: *Mutable, other: Const) void {
if (self.limbs.ptr != other.limbs.ptr) {
@memcpy(self.limbs[0..other.limbs.len], other.limbs[0..other.limbs.len]);
}
// 在设置 `positive` 之前规范化,
// 使 `eqlZero` 无需遍历多余的零数位。
self.normalize(other.limbs.len);
self.positive = other.positive or other.eqlZero();
}
/// 高效交换两个 Mutable。此操作交换 limb 指针,不执行完整拷贝。
/// 调用此函数后,limbs 字段存放的地址将不再相同。
pub fn swap(self: *Mutable, other: *Mutable) void {
mem.swap(Mutable, self, other);
}
pub fn dump(self: Mutable) void {
for (self.limbs[0..self.len]) |limb| {
std.debug.print("{x} ", .{limb});
}
std.debug.print("len={} capacity={} positive={}\n", .{ self.len, self.limbs.len, self.positive });
}
/// 克隆一个 Mutable,返回值相同的新 Mutable。新 Mutable 是深拷贝,
/// 可独立于原对象修改。
/// 断言 limbs 足以存储该值。
pub fn clone(other: Mutable, limbs: []Limb) Mutable {
@memcpy(limbs[0..other.len], other.limbs[0..other.len]);
return .{
.limbs = limbs,
.len = other.len,
.positive = other.positive,
};
}
pub fn negate(self: *Mutable) void {
self.positive = !self.positive;
}
/// 修改为绝对值
pub fn abs(self: *Mutable) void {
self.positive = true;
}
/// 将 Mutable 设置为 value。value 必须为基本整数类型。
/// 断言该值可放入 limb 缓冲区。
/// 注意:可用 `calcLimbLen` 确定存储某个值
/// 所需的 limb 缓冲区大小。
pub fn set(self: *Mutable, value: anytype) void {
const T = @TypeOf(value);
const needed_limbs = calcLimbLen(value);
assert(needed_limbs <= self.limbs.len); // 值过大
self.len = needed_limbs;
self.positive = value >= 0;
switch (@typeInfo(T)) {
.int => |info| {
var w_value = @abs(value);
if (info.bits <= limb_bits) {
self.limbs[0] = w_value;
} else {
var i: usize = 0;
while (true) : (i += 1) {
self.limbs[i] = @as(Limb, @truncate(w_value));
w_value >>= limb_bits;
if (w_value == 0) break;
}
}
},
.comptime_int => {
comptime var w_value = @abs(value);
if (w_value <= maxInt(Limb)) {
self.limbs[0] = w_value;
} else {
const mask = (1 << limb_bits) - 1;
comptime var i = 0;
inline while (true) : (i += 1) {
self.limbs[i] = w_value & mask;
w_value >>= limb_bits;
if (w_value == 0) break;
}
}
},
else => @compileError("cannot set Mutable using type " ++ @typeName(T)),
}
}
/// 根据字符串表示 `value` 设置自身。
///
/// `value` 只能包含不大于 `base` 的数字,且不区分大小写。不允许进制前缀,例如 0x43 应直接写作 43。输入字符串中的下划线会被忽略,可用作数字分隔符。
///
/// `self.limbs` 必须有足够内存容纳该值。可使用 `calcSetStringLimbCount` 确定所需 limb 数量的上界。
/// 断言进制处于 [2, 36] 范围。
///
/// 若值中包含对指定进制无效的数字,返回错误。
///
///
///
pub fn setString(
self: *Mutable,
base: u8,
value: []const u8,
) error{InvalidCharacter}!void {
assert(base >= 2);
assert(base <= 36);
var i: usize = 0;
var positive = true;
if (value.len > 0 and value[0] == '-') {
positive = false;
i += 1;
}
@memset(self.limbs, 0);
self.len = 1;
var limb: Limb = 0;
var j: usize = 0;
for (value[i..]) |ch| {
if (ch == '_') {
continue;
}
const d = try std.fmt.charToDigit(ch, base);
limb *= base;
limb += d;
j += 1;
if (j == constants.digits_per_limb[base]) {
const len = @min(self.len + 1, self.limbs.len);
// r = a * b = a + a * (b - 1)
// 当 self.limbs 不足以存储该数时触发断言
assert(!llmulLimb(.add, self.limbs[0..len], self.limbs[0..len], constants.big_bases[base] - 1));
assert(lladdcarry(self.limbs[0..len], self.limbs[0..len], &[1]Limb{limb}) == 0);
if (self.limbs.len > self.len and self.limbs[self.len] != 0)
self.len += 1;
j = 0;
limb = 0;
}
}
if (j > 0) {
const len = @min(self.len + 1, self.limbs.len);
// 当 self.limbs 不足以存储该数时触发断言
assert(!llmulLimb(.add, self.limbs[0..len], self.limbs[0..len], math.pow(Limb, base, j) - 1));
assert(lladdcarry(self.limbs[0..len], self.limbs[0..len], &[1]Limb{limb}) == 0);
if (self.limbs.len > self.len and self.limbs[self.len] != 0)
self.len += 1;
}
self.positive = positive;
}
/// 将 self 设为二进制补码整数的任一边界值。
/// 注意:结果仍为符号与绝对值表示,而非二进制补码!要将结果
/// 转换为二进制补码,取绝对值即可。
///
/// 断言结果可容纳于 `r`。r 所需 limb 数量的
/// 上界为 `calcTwosCompLimbCount(bit_count)`。
pub fn setTwosCompIntLimit(
r: *Mutable,
limit: TwosCompIntLimit,
signedness: Signedness,
bit_count: usize,
) void {
// 处理零位类型。
if (bit_count == 0) {
r.set(0);
return;
}
const req_limbs = calcTwosCompLimbCount(bit_count);
const bit: Log2Limb = @truncate(bit_count - 1);
const signmask = @as(Limb, 1) << bit; // 0b0..010..0,其中 1 为符号位。
const mask = (signmask << 1) -% 1; // 0b0..011..1,其中最左侧的 1 是符号位。
r.positive = true;
switch (signedness) {
.signed => switch (limit) {
.min => {
// 负边界,有符号值 = -0x80。
r.len = req_limbs;
@memset(r.limbs[0 .. r.len - 1], 0);
r.limbs[r.len - 1] = signmask;
r.positive = false;
},
.max => {
// 有符号正数边界 = 0x7F。
// 注意,此分支需要归一化,
// 因为首位应为 0。
// 针对 1 位整数的特殊情况。
if (bit_count == 1) {
r.set(0);
} else {
const new_req_limbs = calcTwosCompLimbCount(bit_count - 1);
const msb = @as(Log2Limb, @truncate(bit_count - 2));
const new_signmask = @as(Limb, 1) << msb; // 0b0..010..0,其中 1 为符号位。
const new_mask = (new_signmask << 1) -% 1; // 0b0..001..1,其中最右侧的 0 是符号位。
r.len = new_req_limbs;
@memset(r.limbs[0 .. r.len - 1], maxInt(Limb));
r.limbs[r.len - 1] = new_mask;
}
},
},
.unsigned => switch (limit) {
.min => {
// 最小边界,无符号值 = 0x00
r.set(0);
},
.max => {
// 上界,无符号 = 0xFF
r.len = req_limbs;
@memset(r.limbs[0 .. r.len - 1], maxInt(Limb));
r.limbs[r.len - 1] = mask;
},
},
}
}
/// 将 Mutable 设置为按 `round` 舍入的浮点值。
/// 返回转换是否精确(即 `round` 未影响结果)。
pub fn setFloat(self: *Mutable, value: anytype, round: Round) Exactness {
const Float = @TypeOf(value);
if (Float == comptime_float) return self.setFloat(@as(f128, value), round);
const abs_value = @abs(value);
if (abs_value < 1.0) {
if (abs_value == 0.0) {
self.set(0);
return .exact;
}
self.set(@as(i2, round: switch (round) {
.nearest_even => if (abs_value <= 0.5) 0 else continue :round .away,
.away => if (value < 0.0) -1 else 1,
.trunc => 0,
.floor => -@as(i2, @intFromBool(value < 0.0)),
.ceil => @intFromBool(value > 0.0),
}));
return .inexact;
}
const Repr = std.math.FloatRepr(Float);
const repr: Repr = @bitCast(value);
const exponent = repr.exponent.unbias();
assert(exponent >= 0);
const int_bit: Repr.Mantissa = 1 << (@bitSizeOf(Repr.Mantissa) - 1);
const mantissa = int_bit | repr.mantissa;
if (exponent >= @bitSizeOf(Repr.Normalized.Fraction)) {
self.set(mantissa);
self.shiftLeft(self.toConst(), @intCast(exponent - @bitSizeOf(Repr.Normalized.Fraction)));
self.positive = repr.sign == .positive;
return .exact;
}
self.set(mantissa >> @intCast(@bitSizeOf(Repr.Normalized.Fraction) - exponent));
const round_bits: Repr.Normalized.Fraction = @truncate(mantissa << @intCast(exponent));
if (round_bits == 0) {
self.positive = repr.sign == .positive;
return .exact;
}
round: switch (round) {
.nearest_even => {
const half: Repr.Normalized.Fraction = 1 << (@bitSizeOf(Repr.Normalized.Fraction) - 1);
if (round_bits >= half) self.addScalar(self.toConst(), 1);
if (round_bits == half) self.limbs[0] &= ~@as(Limb, 1);
},
.away => self.addScalar(self.toConst(), 1),
.trunc => {},
.floor => switch (repr.sign) {
.positive => {},
.negative => continue :round .away,
},
.ceil => switch (repr.sign) {
.positive => continue :round .away,
.negative => {},
},
}
self.positive = repr.sign == .positive;
return .inexact;
}
/// r = a + scalar
///
/// r 和 a 可以互为别名。
/// scalar 是基本整数类型。
///
/// 断言结果能放入 `r`。r 所需数位数量的上界为
/// `@max(a.limbs.len, calcLimbLen(scalar)) + 1`。
pub fn addScalar(r: *Mutable, a: Const, scalar: anytype) void {
// 通常可以直接用 calcLimbLen 确定所需 limb 数量,
// 但当 scalar 不是 comptime_int 时,此数量在编译期未知。因此,
// 对于非 comptime_int 标量,改用 calcTwosCompLimbCount。如果 scalar 在其类型中
// 恰好具有较小的绝对值,该方法可能过于保守,但
// 能够使用栈且无需传入分配器,仍然值得。
// 注意,无论如何,Mutable.init 仍会将 len 设置为 calcLimbLen(scalar)。
const limbs_len = comptime switch (@typeInfo(@TypeOf(scalar))) {
.comptime_int => calcLimbLen(scalar),
.int => |info| calcTwosCompLimbCount(info.bits),
else => @compileError("expected scalar to be an int"),
};
var limbs: [limbs_len]Limb = undefined;
const operand = init(&limbs, scalar).toConst();
return add(r, a, operand);
}
/// 加法的基础实现。将 a 和 b 的 `@max(a.limbs.len, b.limbs.len)` 个元素相加,
/// 返回是否发生溢出。
/// r、a 和 b 可以互为别名。
///
/// 断言 r 有足够元素容纳结果。上界为 `@max(a.limbs.len, b.limbs.len)`。
fn addCarry(r: *Mutable, a: Const, b: Const) bool {
if (a.eqlZero()) {
r.copy(b);
return false;
} else if (b.eqlZero()) {
r.copy(a);
return false;
} else if (a.positive != b.positive) {
if (a.positive) {
// (a) + (-b) => a - b
return r.subCarry(a, b.abs());
} else {
// (-a) + (b) => b - a
return r.subCarry(b, a.abs());
}
} else {
r.positive = a.positive;
if (a.limbs.len >= b.limbs.len) {
const c = lladdcarry(r.limbs, a.limbs, b.limbs);
r.normalize(a.limbs.len);
return c != 0;
} else {
const c = lladdcarry(r.limbs, b.limbs, a.limbs);
r.normalize(b.limbs.len);
return c != 0;
}
}
}
/// r = a + b
///
/// r、a 和 b 可以共用存储。
///
/// 断言结果可存入 `r`。r 所需 limb 数量的上界为
/// `@max(a.limbs.len, b.limbs.len) + 1`。
pub fn add(r: *Mutable, a: Const, b: Const) void {
if (r.addCarry(a, b)) {
// 修正结果。注意 addCarry 按 a.limbs.len 或 b.limbs.len 规范化,
// 因此需要在此设置长度。
const msl = @max(a.limbs.len, b.limbs.len);
// `[add|sub]Carry` 按 `msl` 进行归一化,因此需要在此处手动修正结果。
// 注意,正因为完成了归一化,中间的 limb 在此处为零。
r.len = msl + 1;
r.limbs[msl] = 1; // 若此处触发 panic,则 `r` 的空间不足。
}
}
/// r = a + b,采用二进制补码回绕语义。返回是否发生溢出。
/// r、a 和 b 可以互为别名。
///
/// 断言结果可放入 `r`。r 所需 limb 数的上界为
/// `calcTwosCompLimbCount(bit_count)`。
pub fn addWrap(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) bool {
const req_limbs = calcTwosCompLimbCount(bit_count);
// 若有高位,则取其切片;这些位会被忽略,从而可以用 addCarry 判断
// 是否发生溢出。
const x: Const = .{
.positive = a.positive,
.limbs = a.limbs[0..@min(req_limbs, a.limbs.len)],
};
const y: Const = .{
.positive = b.positive,
.limbs = b.limbs[0..@min(req_limbs, b.limbs.len)],
};
var carry_truncated = false;
if (r.addCarry(x, y)) {
// 这里有两种可能:
// - 超出 req_limbs。此时忽略进位,因为截断时原本就会将它移除。
// - a 与 b 的元素少于 req_limbs,且它们的元素发生溢出。此情况需要处理。
// 注意:此后仍可能需要回绕。
//
const msl = @max(a.limbs.len, b.limbs.len);
if (msl < req_limbs) {
r.len = msl + 1;
r.limbs[msl] = 1;
} else {
carry_truncated = true;
}
}
if (!r.toConst().fitsInTwosComp(signedness, bit_count)) {
r.truncate(r.toConst(), signedness, bit_count);
return true;
}
return carry_truncated;
}
/// r = a + b,采用二进制补码饱和语义。
/// r、a 和 b 可以共用存储。
///
/// 断言结果可存入 `r`。r 所需 limb 数量的上界为
/// `calcTwosCompLimbCount(bit_count)`。
pub fn addSat(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) void {
const req_limbs = calcTwosCompLimbCount(bit_count);
// 若有高位,则取其切片;这些位会被忽略,从而可以用 addCarry 判断
// 是否发生溢出。
const x: Const = .{
.positive = a.positive,
.limbs = a.limbs[0..@min(req_limbs, a.limbs.len)],
};
const y: Const = .{
.positive = b.positive,
.limbs = b.limbs[0..@min(req_limbs, b.limbs.len)],
};
if (r.addCarry(x, y)) {
// 此处有两种可能:
// - 超过 req_limbs,因而需要饱和处理。
// - a 和 b 的元素数均少于 req_limbs,但这些元素发生溢出。
// 注意:此时也*可能*需要饱和处理。
const msl = @max(a.limbs.len, b.limbs.len);
if (msl < req_limbs) {
r.len = msl + 1;
r.limbs[msl] = 1;
// 注意:若 msl == req_limbs - 1,可能仍需要饱和处理
} else {
// req_limbs 溢出,必须饱和。
return r.setTwosCompIntLimit(if (r.positive) .max else .min, signedness, bit_count);
}
}
// 若结果无法表示,则饱和到边界值。
r.saturate(r.toConst(), signedness, bit_count);
}
/// 减法的基础实现。从 a 和 b 减去 `@max(a.limbs.len, b.limbs.len)` 个元素,并返回是否发生溢出。
/// r、a 和 b 可以互为别名。
///
/// 断言 r 的元素数量足以容纳结果,上界为 `@max(a.limbs.len, b.limbs.len)`。
///
fn subCarry(r: *Mutable, a: Const, b: Const) bool {
if (a.eqlZero()) {
r.copy(b);
r.positive = !b.positive;
return false;
} else if (b.eqlZero()) {
r.copy(a);
return false;
} else if (a.positive != b.positive) {
if (a.positive) {
// (a) - (-b) => a + b
return r.addCarry(a, b.abs());
} else {
// (-a) - (b) => -a + -b
return r.addCarry(a, b.negate());
}
} else if (a.positive) {
if (a.order(b) != .lt) {
// (a) - (b) => a - b
const c = llsubcarry(r.limbs, a.limbs, b.limbs);
r.normalize(a.limbs.len);
r.positive = true;
return c != 0;
} else {
// (a) - (b) => -b + a => -(b - a)
const c = llsubcarry(r.limbs, b.limbs, a.limbs);
r.normalize(b.limbs.len);
r.positive = false;
return c != 0;
}
} else {
if (a.order(b) == .lt) {
// (-a) - (-b) => -(a - b)
const c = llsubcarry(r.limbs, a.limbs, b.limbs);
r.normalize(a.limbs.len);
r.positive = false;
return c != 0;
} else {
// (-a) - (-b) => --b + -a => b - a
const c = llsubcarry(r.limbs, b.limbs, a.limbs);
r.normalize(b.limbs.len);
r.positive = true;
return c != 0;
}
}
}
/// r = a - b
///
/// r、a 和 b 可以互为别名。
///
/// 断言结果能放入 `r`。r 所需数位数量的上界为
/// `@max(a.limbs.len, b.limbs.len) + 1`。若两操作数均为正,则不需要 +1。
pub fn sub(r: *Mutable, a: Const, b: Const) void {
r.add(a, b.negate());
}
/// r = a - b,采用二进制补码回绕语义。返回是否发生溢出。
///
/// r、a 和 b 可以指向同一内存。
/// 断言结果可存入 `r`。r 所需 limb 数量的上界为
/// `calcTwosCompLimbCount(bit_count)`。
pub fn subWrap(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) bool {
return r.addWrap(a, b.negate(), signedness, bit_count);
}
/// r = a - b,采用二进制补码饱和语义。
/// r、a 和 b 可以互为别名。
///
/// 断言结果能放入 `r`。r 所需 limb 数的上界为
/// `calcTwosCompLimbCount(bit_count)`。
pub fn subSat(r: *Mutable, a: Const, b: Const, signedness: Signedness, bit_count: usize) void {
r.addSat(a, b.negate(), signedness, bit_count);
}
/// rma = a * b
///
/// `rma` 可以与 `a` 或 `b` 互为别名。
/// `a` 和 `b` 可以互为别名。
///
/// 断言结果可容纳于 `rma`。rma 所需 limb 数的
/// 上界为 `a.limbs.len + b.limbs.len`。
///
/// `limbs_buffer` 用于临时存储,所需大小由 `calcMulLimbsBufferLen` 给出。
pub fn mul(rma: *Mutable, a: Const, b: Const, limbs_buffer: []Limb, allocator: ?Allocator) void {
var buf_index: usize = 0;
const a_copy = if (rma.limbs.ptr == a.limbs.ptr) blk: {
const start = buf_index;
@memcpy(limbs_buffer[buf_index..][0..a.limbs.len], a.limbs);
buf_index += a.limbs.len;
break :blk a.toMutable(limbs_buffer[start..buf_index]).toConst();
} else a;
const b_copy = if (rma.limbs.ptr == b.limbs.ptr) blk: {
const start = buf_index;
@memcpy(limbs_buffer[buf_index..][0..b.limbs.len], b.limbs);
buf_index += b.limbs.len;
break :blk b.toMutable(limbs_buffer[start..buf_index]).toConst();
} else b;
return rma.mulNoAlias(a_copy, b_copy, allocator);
}
/// rma = a * b
///
/// `rma` 不得与 `a` 或 `b` 别名。
/// `a` 和 `b` 可以互相别名。
///
/// 断言结果可容纳于 `rma`。rma 所需 limb 数
/// 的上界为 `a.limbs.len + b.limbs.len`。
///
/// 若提供 `allocator`,则用于临时存储,以提升
/// 乘法性能。遇到 `error.OutOfMemory` 时使用回退算法。
pub fn mulNoAlias(rma: *Mutable, a: Const, b: Const, allocator: ?Allocator) void {
assert(rma.limbs.ptr != a.limbs.ptr); // 非法别名关系
assert(rma.limbs.ptr != b.limbs.ptr); // 非法别名关系
if (a.limbs.len == 1 and b.limbs.len == 1) {
rma.limbs[0], const overflow_bit = @mulWithOverflow(a.limbs[0], b.limbs[0]);
if (overflow_bit == 0) {
rma.len = 1;
rma.positive = (a.positive == b.positive) or rma.limbs[0] == 0;
return;
}
}
@memset(rma.limbs[0 .. a.limbs.len + b.limbs.len], 0);
llmulacc(.add, allocator, rma.limbs, a.limbs, b.limbs);
rma.normalize(a.limbs.len + b.limbs.len);
rma.positive = (a.positive == b.positive);
}
/// rma = a * b,采用二进制补码回绕语义。
///
/// `rma` 可以与 `a` 或 `b` 别名。
/// `a` 和 `b` 可以互相别名。
///
/// 断言结果可容纳于 `rma`。rma 所需 limb 数
/// 的上界为 `a.limbs.len + b.limbs.len`。
///
/// `limbs_buffer` 用于临时存储,所需大小由 `calcMulWrapLimbsBufferLen` 给出。
pub fn mulWrap(
rma: *Mutable,
a: Const,
b: Const,
signedness: Signedness,
bit_count: usize,
limbs_buffer: []Limb,
allocator: ?Allocator,
) void {
var buf_index: usize = 0;
const req_limbs = calcTwosCompLimbCount(bit_count);
const a_copy = if (rma.limbs.ptr == a.limbs.ptr) blk: {
const start = buf_index;
const a_len = @min(req_limbs, a.limbs.len);
@memcpy(limbs_buffer[buf_index..][0..a_len], a.limbs[0..a_len]);
buf_index += a_len;
break :blk a.toMutable(limbs_buffer[start..buf_index]).toConst();
} else a;
const b_copy = if (rma.limbs.ptr == b.limbs.ptr) blk: {
const start = buf_index;
const b_len = @min(req_limbs, b.limbs.len);
@memcpy(limbs_buffer[buf_index..][0..b_len], b.limbs[0..b_len]);
buf_index += b_len;
break :blk a.toMutable(limbs_buffer[start..buf_index]).toConst();
} else b;
return rma.mulWrapNoAlias(a_copy, b_copy, signedness, bit_count, allocator);
}
/// rma = a * b,采用二进制补码回绕语义。
///
/// `rma` 不得与 `a` 或 `b` 互为别名。
/// `a` 和 `b` 可以互为别名。
///
/// 断言结果能够放入 `rma`。所需 limb 数量的上界为 `a.limbs.len + b.limbs.len`。
///
/// 若提供 `allocator`,则用于临时存储,以提升乘法性能。出现 `error.OutOfMemory` 时,会使用后备算法处理。
///
///
pub fn mulWrapNoAlias(
rma: *Mutable,
a: Const,
b: Const,
signedness: Signedness,
bit_count: usize,
allocator: ?Allocator,
) void {
assert(rma.limbs.ptr != a.limbs.ptr); // 非法别名关系
assert(rma.limbs.ptr != b.limbs.ptr); // 非法别名关系
const req_limbs = calcTwosCompLimbCount(bit_count);
// 此处可以忽略高位,因为那些结果最终会被丢弃。
const a_limbs = a.limbs[0..@min(req_limbs, a.limbs.len)];
const b_limbs = b.limbs[0..@min(req_limbs, b.limbs.len)];
@memset(rma.limbs[0..req_limbs], 0);
llmulacc(.add, allocator, rma.limbs, a_limbs, b_limbs);
rma.normalize(@min(req_limbs, a.limbs.len + b.limbs.len));
rma.positive = (a.positive == b.positive);
rma.truncate(rma.toConst(), signedness, bit_count);
}
/// r = @bitReverse(a),采用二进制补码语义。
/// r 与 a 可以互为别名。
///
/// 断言结果能放入 `r`。r 所需 limb 数的上界为
/// `calcTwosCompLimbCount(bit_count)`。
pub fn bitReverse(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void {
if (bit_count == 0) {
r.limbs[0] = 0;
r.len = 1;
r.positive = true;
return;
}
r.copy(a);
const limbs_required = calcTwosCompLimbCount(bit_count);
if (!a.positive) {
r.positive = true; // 取负。
r.bitNotWrap(r.toConst(), .unsigned, bit_count); // 按位非。
r.addScalar(r.toConst(), 1); // 加一。
} else if (limbs_required > a.limbs.len) {
// 零扩展到输出所需长度
for (r.limbs[a.limbs.len..limbs_required]) |*limb| {
limb.* = 0;
}
r.len = limbs_required;
}
// 0b0..01..1000,具有 @log2(@sizeOf(Limb)) 个连续的 1
const endian_mask: usize = (@sizeOf(Limb) - 1) << 3;
const bytes = std.mem.sliceAsBytes(r.limbs);
var k: usize = 0;
while (k < ((bit_count + 1) / 2)) : (k += 1) {
var i = k;
var rev_i = bit_count - i - 1;
// 此“端序掩码”将 Limb 中的低位(小端)字节映射到对应的高位
// (大端)字节,同时不改变所索引的 limb
if (native_endian == .big) {
i ^= endian_mask;
rev_i ^= endian_mask;
}
const bit_i = std.mem.readPackedInt(u1, bytes, i, .little);
const bit_rev_i = std.mem.readPackedInt(u1, bytes, rev_i, .little);
std.mem.writePackedInt(u1, bytes, i, bit_rev_i, .little);
std.mem.writePackedInt(u1, bytes, rev_i, bit_i, .little);
}
// 计算用于输出的符号数值表示
if (signedness == .signed) {
const last_bit = switch (native_endian) {
.little => std.mem.readPackedInt(u1, bytes, bit_count - 1, .little),
.big => std.mem.readPackedInt(u1, bytes, (bit_count - 1) ^ endian_mask, .little),
};
if (last_bit == 1) {
r.bitNotWrap(r.toConst(), .unsigned, bit_count); // 按位非。
r.addScalar(r.toConst(), 1); // 加一。
r.positive = false; // 取负。
}
}
r.normalize(r.len);
}
/// r = @byteSwap(a),采用二进制补码语义。
/// r 和 a 可以共用存储。
///
/// 断言结果可存入 `r`。r 所需 limb 数量的上界为
/// `calcTwosCompLimbCount(8*byte_count)`。
pub fn byteSwap(r: *Mutable, a: Const, signedness: Signedness, byte_count: usize) void {
if (byte_count == 0) {
r.limbs[0] = 0;
r.len = 1;
r.positive = true;
return;
}
r.copy(a);
const limbs_required = calcTwosCompLimbCount(8 * byte_count);
if (!a.positive) {
r.positive = true; // 取负。
r.bitNotWrap(r.toConst(), .unsigned, 8 * byte_count); // 按位非。
r.addScalar(r.toConst(), 1); // 加一。
} else if (limbs_required > a.limbs.len) {
// 零扩展到输出所需长度
for (r.limbs[a.limbs.len..limbs_required]) |*limb| {
limb.* = 0;
}
r.len = limbs_required;
}
// 0b0..01..1,具有 @log2(@sizeOf(Limb)) 个尾随的 1
const endian_mask: usize = @sizeOf(Limb) - 1;
var bytes = std.mem.sliceAsBytes(r.limbs);
assert(bytes.len >= byte_count);
var k: usize = 0;
while (k < (byte_count + 1) / 2) : (k += 1) {
var i = k;
var rev_i = byte_count - k - 1;
// 此“端序掩码”将 Limb 中的低位(小端)字节映射到对应的高位
// (大端)字节,同时不改变所索引的 limb
if (native_endian == .big) {
i ^= endian_mask;
rev_i ^= endian_mask;
}
const byte_i = bytes[i];
const byte_rev_i = bytes[rev_i];
bytes[rev_i] = byte_i;
bytes[i] = byte_rev_i;
}
// 计算用于输出的符号数值表示
if (signedness == .signed) {
const last_byte = switch (native_endian) {
.little => bytes[byte_count - 1],
.big => bytes[(byte_count - 1) ^ endian_mask],
};
if (last_byte & (1 << 7) != 0) { // 检查最后一个字节的符号位
r.bitNotWrap(r.toConst(), .unsigned, 8 * byte_count); // 按位非。
r.addScalar(r.toConst(), 1); // 加一。
r.positive = false; // 取负。
}
}
r.normalize(r.len);
}
/// r = @popCount(a),采用二进制补码语义。
/// r 与 a 可以互为别名。
///
/// 断言结果能放入 `r`。r 所需 limb 数的上界为
/// `calcTwosCompLimbCount(bit_count)`。
pub fn popCount(r: *Mutable, a: Const, bit_count: usize) void {
r.copy(a);
if (!a.positive) {
r.positive = true; // 取负。
r.bitNotWrap(r.toConst(), .unsigned, bit_count); // 按位非。
r.addScalar(r.toConst(), 1); // 加一。
}
var sum: Limb = 0;
for (r.limbs[0..r.len]) |limb| {
sum += @popCount(limb);
}
r.set(sum);
}
/// rma = a * a
///
/// `rma` 不得与 `a` 互为别名。
///
/// 断言结果可容纳于 `rma`。rma 所需 limb 数量的
/// 上界为 `2 * a.limbs.len + 1`。
///
/// 如果提供 `allocator`,则将其用于临时存储以提高
/// 乘法性能。遇到 `error.OutOfMemory` 时采用后备算法。
pub fn sqrNoAlias(rma: *Mutable, a: Const, opt_allocator: ?Allocator) void {
_ = opt_allocator;
assert(rma.limbs.ptr != a.limbs.ptr); // 非法别名关系
@memset(rma.limbs, 0);
llsquareBasecase(rma.limbs, a.limbs);
rma.normalize(2 * a.limbs.len + 1);
rma.positive = true;
}
/// q = a / b(余数为 r)。
///
/// a / b 取整,向零舍入。
/// q 可以与 a 或 b 互为别名。
///
/// 断言内存足以存储 q 和 r。
/// r 的 limb 数量上界为 `b.limbs.len`。
/// q 的 limb 数量上界由 `a.limbs` 给出。
///
/// `limbs_buffer` 用作临时存储,所需数量由 `calcDivLimbsBufferLen` 给出。
pub fn divFloor(
q: *Mutable,
r: *Mutable,
a: Const,
b: Const,
limbs_buffer: []Limb,
) void {
const sep = a.limbs.len + 2;
var x = a.toMutable(limbs_buffer[0..sep]);
var y = b.toMutable(limbs_buffer[sep..]);
div(q, r, &x, &y);
// 注意,`div` 执行向零截断除法,满足:
// @divTrunc(a, b) * b + @rem(a, b) = a
// 因此 r = a - @divTrunc(a, b) * b
// 注意,@rem(a, -b) = @rem(-b, a) = -@rem(a, b) = -@rem(-a, -b)
// 对于 divTrunc,希望执行:
// @divFloor(a, b) * b + @mod(a, b) = a
// 注意:
// @divFloor(-a, b)
// = @divFloor(a, -b)
// = -@divCeil(a, b)
// = -@divFloor(a + b - 1, b)
// = -@divTrunc(a + b - 1, b)
// 注(1):
// @divTrunc(a + b - 1, b) * b + @rem(a + b - 1, b) = a + b - 1
// = @divTrunc(a + b - 1, b) * b + @rem(a - 1, b) = a + b - 1
// = @divTrunc(a + b - 1, b) * b + @rem(a - 1, b) - b + 1 = a
if (a.positive and b.positive) {
// 正数与正数的情况,无需任何操作。
} else if (a.positive and !b.positive) {
// a/-b -> q 为负,因此需要修正向下取整。
// 减去一,使除法向下取整。
// @divFloor(a, -b) * -b + @mod(a, -b) = a
// 若 b 整除 a,则 @divFloor(a, -b) * -b = a。
// 否则,@divFloor(a, -b) * -b > a,因此 @mod(a, -b) 为负。
// 有如下关系:
// @divFloor(a, -b) * -b + @mod(a, -b) = a
// = -@divTrunc(a + b - 1, b) * -b + @mod(a, -b) = a
// = @divTrunc(a + b - 1, b) * b + @mod(a, -b) = a
// 在 (1) 中代入 a:
// @divTrunc(a + b - 1, b) * b + @rem(a - 1, b) - b + 1 = @divTrunc(a + b - 1, b) * b + @mod(a, -b)
// 得到:
// @mod(a, -b) = @rem(a - 1, b) - b + 1
// 注意,此时 `r` 保存 @rem(a, b)。
//
// 若 @rem(a, b) 不为 0:
// @rem(a - 1, b) = @rem(a, b) - 1
// => @mod(a, -b) = @rem(a, b) - 1 - b + 1 = @rem(a, b) - b
// 否则:
// @rem(a - 1, b) = @rem(a + b - 1, b) = @rem(b - 1, b) = b - 1
// => @mod(a, -b) = b - 1 - b + 1 = 0
if (!r.eqlZero()) {
q.addScalar(q.toConst(), -1);
r.positive = true;
r.sub(r.toConst(), y.toConst().abs());
}
} else if (!a.positive and b.positive) {
// -a/b -> q 为负,因此需要修正向下取整。
// 减去一,使除法向下取整。
// @divFloor(-a, b) * b + @mod(-a, b) = a
// 若 b 整除 a,则 @divFloor(-a, b) * b = -a。
// 否则,@divFloor(-a, b) * b < -a,因此 @mod(-a, b) 为正。
// 有:
// @divFloor(-a, b) * b + @mod(-a, b) = -a
// = -@divTrunc(a + b - 1, b) * b + @mod(-a, b) = -a
// = @divTrunc(a + b - 1, b) * b - @mod(-a, b) = a
// 将 a 代入式(1):
// @divTrunc(a + b - 1, b) * b + @rem(a - 1, b) - b + 1 = @divTrunc(a + b - 1, b) * b - @mod(-a, b)
// 得到:
// @rem(a - 1, b) - b + 1 = -@mod(-a, b)
// => -@mod(-a, b) = @rem(a - 1, b) - b + 1
// => @mod(-a, b) = -(@rem(a - 1, b) - b + 1) = -@rem(a - 1, b) + b - 1
//
// 若 @rem(a, b) 不为 0:
// @rem(a - 1, b) = @rem(a, b) - 1
// => @mod(-a, b) = -(@rem(a, b) - 1) + b - 1 = -@rem(a, b) + 1 + b - 1 = -@rem(a, b) + b
// 否则:
// @rem(a - 1, b) = b - 1
// => @mod(-a, b) = -(b - 1) + b - 1 = 0
if (!r.eqlZero()) {
q.addScalar(q.toConst(), -1);
r.positive = false;
r.add(r.toConst(), y.toConst().abs());
}
} else if (!a.positive and !b.positive) {
// a/b -> q 为正,无需修正向下取整。
// @divFloor(-a, -b) * -b + @mod(-a, -b) = -a
// 若 b 整除 a,则 @divFloor(-a, -b) * -b = -a。
// 否则,@divFloor(-a, -b) * -b > -a,因此 @mod(-a, -b) 为负。
// 有如下关系:
// @divFloor(-a, -b) * -b + @mod(-a, -b) = -a
// = @divTrunc(a, b) * -b + @mod(-a, -b) = -a
// = @divTrunc(a, b) * b - @mod(-a, -b) = a
// 还有:
// @divTrunc(a, b) * b + @rem(a, b) = a
// 代入 a:
// @divTrunc(a, b) * b + @rem(a, b) = @divTrunc(a, b) * b - @mod(-a, -b)
// => @rem(a, b) = -@mod(-a, -b)
// => @mod(-a, -b) = -@rem(a, b)
r.positive = false;
}
}
/// q = a / b (rem r)
///
/// a / b 向上取整(向 +inf 舍入)。
/// q 可以与 a 或 b 共用存储。
///
/// 断言存在足够的内存存储 q 和 r。
/// r 的 limb 数量上界为 `b.limbs.len`。
/// q 的 limb 数量上界由 `a.limbs` 给出。
///
/// `limbs_buffer` 用作临时存储。所需大小由 `calcDivLimbsBufferLen` 给出。
pub fn divCeil(
q: *Mutable,
r: *Mutable,
a: Const,
b: Const,
limbs_buffer: []Limb,
) void {
const sep = a.limbs.len + 2;
var x = a.toMutable(limbs_buffer[0..sep]);
var y = b.toMutable(limbs_buffer[sep..]);
// div 执行截断除法(@divTrunc):结果为正时
// 向负无穷方向舍入,结果为负时
// 向正无穷方向舍入。
div(q, r, &x, &y);
// @rem 给出 @divTrunc 之后的余数,定义为:
// x * @divTrunc(x, y) + @rem(x, y) = x
// 适用于所有满足 y != 0 的整数 x、y。
// 下文中,a、b 为满足 a >= 0、b > 0 的整数,并将
// modCeil 视为 @divCeil 之后的余数,定义为:
// x * @divCeil(x, y) + modCeil(x, y) = x
// 适用于所有满足 y != 0 的整数 x、y。
if (a.positive != b.positive or r.eqlZero()) {
// 此时结果为负,或者余数为 0。
// 若结果为负,默认的截断除法已经向正无穷舍入,因此无需调整。
// 若余数为 0,则除法精确,也无需调整。
//
} else {
// 符号相同。
// 有:
// modCeil(a, b) != 0
// => @divCeil(a, b) = @divTrunc(a, b) + 1
// 以及:
// b * @divTrunc(a, b) + @rem(a, b) = a
// b * @divCeil(a, b) + modCeil(a, b) = a
// => b * @divTrunc(a, b) + b + modCeil(a, b) = a
// => modCeil(a, b) = @rem(a, b) - b
//
// 由于 b 保持自身符号,此推导对正负 b 均成立。
q.addScalar(q.toConst(), 1);
r.sub(r.toConst(), y.toConst());
}
}
/// q = a / b,余数为 r。
///
/// a / b 按向负无穷方向取整。
/// q 可以与 a 或 b 互为别名。
///
/// 断言具有足够内存存储 q 和 r。
/// r 的 limb 数上界为 `b.limbs.len`。
/// q 的 limb 数上界为 `a.limbs.len`。
///
/// `limbs_buffer` 用作临时存储,所需大小由 `calcDivLimbsBufferLen` 给出。
pub fn divTrunc(
q: *Mutable,
r: *Mutable,
a: Const,
b: Const,
limbs_buffer: []Limb,
) void {
const sep = a.limbs.len + 2;
var x = a.toMutable(limbs_buffer[0..sep]);
var y = b.toMutable(limbs_buffer[sep..]);
div(q, r, &x, &y);
}
/// r = a << shift,即 r = a * 2^shift。
///
/// r 和 a 可以互为别名。
///
/// 断言内存足以容纳结果。limb 数上界为
/// `a.limbs.len + (shift / (@sizeOf(Limb) * 8))`。
pub fn shiftLeft(r: *Mutable, a: Const, shift: usize) void {
const new_len = llshl(r.limbs, a.limbs, shift);
r.normalize(new_len);
r.positive = a.positive;
}
/// r = a <<| shift,采用二进制补码饱和语义。
///
/// r 和 a 可以互为别名。
///
/// 断言有足够内存存放结果。r 所需 limb 数的上界为
/// `calcTwosCompLimbCount(bit_count)`。
pub fn shiftLeftSat(r: *Mutable, a: Const, shift: usize, signedness: Signedness, bit_count: usize) void {
// 特殊情况:参数为负,但结果应为无符号数时,
// 一律返回 0。
if (!a.positive and signedness == .unsigned) {
r.set(0);
return;
}
// 检查移位是否会溢出。若未移位值中,位于
// `bit_count - shift` 以上的任何位(二进制补码表示)被置位,就会溢出。
// 注意,此处不计符号位。
// 处理超过目标类型位宽的移位,同时也处理零位整数。
//
if (bit_count <= shift) {
// 此情况下,只有 `a` 为零时才不会溢出。
if (a.eqlZero()) {
r.set(0);
} else {
r.setTwosCompIntLimit(if (a.positive) .max else .min, signedness, bit_count);
}
return;
}
const checkbit = bit_count - shift - @intFromBool(signedness == .signed);
// 若 `checkbit` 及更高位均为零,则不会溢出。
if (checkbit >= a.limbs.len * limb_bits) {
// `checkbit` 超出 a 的范围,因此必定不会发生溢出,
// 可改用普通移位。
// 注意,若 `a` 已规范化(此处如此假定),这会检查高位数位中已置位的位。
// 注意,此时 r 应已具有执行常规移位所需的足够 limb。
// 在此情况下,最高有效 limb 的移位仍可能溢出。
r.shiftLeft(a, shift);
return;
} else if (checkbit < (a.limbs.len - 1) * limb_bits) {
// `checkbit` 不在最高有效 limb 中。如果 `a` 已归一化,最高有效
// limb 不会为零,因此此时需要饱和。注意,根据归一化
// 规则,`a.limbs.len` 必须至少为一。
r.setTwosCompIntLimit(if (a.positive) .max else .min, signedness, bit_count);
return;
}
// 使用最高有效 limb 中需要检查的位生成掩码。需要检查
// 所有有效位不低于 checkbit 的位。
// const msb = @truncate(Log2Limb, checkbit);
// const checkmask = (@as(Limb, 1) << msb) -% 1;
if (a.limbs[a.limbs.len - 1] >> @as(Log2Limb, @truncate(checkbit)) != 0) {
// 需要饱和处理。
r.setTwosCompIntLimit(if (a.positive) .max else .min, signedness, bit_count);
return;
}
// 此移位不应溢出,因此调用 llshl 并手动归一化,
// 避免需要额外 limb。
const new_len = llshl(r.limbs, a.limbs, shift);
r.normalize(new_len);
r.positive = a.positive;
}
/// r = a >> shift
/// r 和 a 可以互为别名。
///
/// 断言内存足以容纳结果。limb 数上界为
/// `a.limbs.len - (shift / (@bitSizeOf(Limb)))`。
pub fn shiftRight(r: *Mutable, a: Const, shift: usize) void {
const full_limbs_shifted_out = shift / limb_bits;
const remaining_bits_shifted_out = shift % limb_bits;
if (a.limbs.len <= full_limbs_shifted_out) {
// 对负数移位会收敛到 -1,而不是 0
if (a.positive) {
r.len = 1;
r.positive = true;
r.limbs[0] = 0;
} else {
r.len = 1;
r.positive = false;
r.limbs[0] = 1;
}
return;
}
const nonzero_negative_shiftout = if (a.positive) false else nonzero: {
for (a.limbs[0..full_limbs_shifted_out]) |x| {
if (x != 0)
break :nonzero true;
}
if (remaining_bits_shifted_out == 0)
break :nonzero false;
const not_covered: Log2Limb = @intCast(limb_bits - remaining_bits_shifted_out);
break :nonzero a.limbs[full_limbs_shifted_out] << not_covered != 0;
};
const new_len = llshr(r.limbs, a.limbs, shift);
r.len = new_len;
r.positive = a.positive;
if (nonzero_negative_shiftout) r.addScalar(r.toConst(), -1);
r.normalize(r.len);
}
/// r = ~a,采用二进制补码回绕语义。
/// r 可以与 a 互为别名。
///
/// 断言 r 有足够的 limb 存储结果。r 所需 limb 数的上界为
/// `calcTwosCompLimbCount(bit_count)`。
pub fn bitNotWrap(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void {
r.copy(a.negate());
const negative_one: Const = .{ .limbs = &.{1}, .positive = false };
_ = r.addWrap(r.toConst(), negative_one, signedness, bit_count);
}
/// r = a | b,采用二进制补码语义。
/// r 可以与 a 或 b 共用存储。
///
/// a 和 b 会零扩展到二者中较长者的长度。
///
/// 断言 r 有足够的 limb 存储结果。上界为 `@max(a.limbs.len, b.limbs.len)`。
pub fn bitOr(r: *Mutable, a: Const, b: Const) void {
// 简单情况:llsignedor 不支持零。
if (a.eqlZero()) {
r.copy(b);
return;
} else if (b.eqlZero()) {
r.copy(a);
return;
}
if (a.limbs.len >= b.limbs.len) {
r.positive = llsignedor(r.limbs, a.limbs, a.positive, b.limbs, b.positive);
r.normalize(if (b.positive) a.limbs.len else b.limbs.len);
} else {
r.positive = llsignedor(r.limbs, b.limbs, b.positive, a.limbs, a.positive);
r.normalize(if (a.positive) b.limbs.len else a.limbs.len);
}
}
/// 按二进制补码语义计算 r = a & b。
/// r 可以与 a 或 b 互为别名。
///
/// 断言 r 具有足够的 limb 存储结果。
/// 如果只有 a 为正,上界为 `a.limbs.len`。
/// 如果只有 b 为正,上界为 `b.limbs.len`。
/// 如果 a 和 b 都为正,上界为 `@min(a.limbs.len, b.limbs.len)`。
/// 如果 a 和 b 都为负,上界为 `@max(a.limbs.len, b.limbs.len) + 1`。
pub fn bitAnd(r: *Mutable, a: Const, b: Const) void {
// 简单情况:llsignedand 不支持零。
if (a.eqlZero()) {
r.copy(a);
return;
} else if (b.eqlZero()) {
r.copy(b);
return;
}
if (a.limbs.len >= b.limbs.len) {
r.positive = llsignedand(r.limbs, a.limbs, a.positive, b.limbs, b.positive);
r.normalize(if (b.positive) b.limbs.len else if (a.positive) a.limbs.len else a.limbs.len + 1);
} else {
r.positive = llsignedand(r.limbs, b.limbs, b.positive, a.limbs, a.positive);
r.normalize(if (a.positive) a.limbs.len else if (b.positive) b.limbs.len else b.limbs.len + 1);
}
}
/// r = a ^ b,采用二进制补码语义。
/// r 可以与 a 或 b 共用存储。
///
/// 断言 r 有足够的 limb 存储结果。如果 a 和 b 的符号属性相同,
/// 上界为 `@max(a.limbs.len, b.limbs.len)`。否则,如果 a 和 b 中
/// 恰有一个为负,上界为 `@max(a.limbs.len, b.limbs.len) + 1`。
pub fn bitXor(r: *Mutable, a: Const, b: Const) void {
// 简单情况,因为 llsignedxor 不支持负零。
if (a.eqlZero()) {
r.copy(b);
return;
} else if (b.eqlZero()) {
r.copy(a);
return;
}
if (a.limbs.len > b.limbs.len) {
r.positive = llsignedxor(r.limbs, a.limbs, a.positive, b.limbs, b.positive);
r.normalize(a.limbs.len + @intFromBool(a.positive != b.positive));
} else {
r.positive = llsignedxor(r.limbs, b.limbs, b.positive, a.limbs, a.positive);
r.normalize(b.limbs.len + @intFromBool(a.positive != b.positive));
}
}
/// rma 可以与 x 或 y 共用存储。
/// x 和 y 可以彼此共用存储。
/// 断言 `rma` 有足够的 limb 存储结果。上界为
/// `@min(x.limbs.len, y.limbs.len)`。
///
/// `limbs_buffer` 在操作期间用作临时存储。此函数返回时,
/// 其长度与调用函数时相同。
pub fn gcd(rma: *Mutable, x: Const, y: Const, limbs_buffer: *std.array_list.Managed(Limb)) !void {
const prev_len = limbs_buffer.items.len;
defer limbs_buffer.shrinkRetainingCapacity(prev_len);
const x_copy = if (rma.limbs.ptr == x.limbs.ptr) blk: {
const start = limbs_buffer.items.len;
try limbs_buffer.appendSlice(x.limbs);
break :blk x.toMutable(limbs_buffer.items[start..]).toConst();
} else x;
const y_copy = if (rma.limbs.ptr == y.limbs.ptr) blk: {
const start = limbs_buffer.items.len;
try limbs_buffer.appendSlice(y.limbs);
break :blk y.toMutable(limbs_buffer.items[start..]).toConst();
} else y;
return gcdLehmer(rma, x_copy, y_copy, limbs_buffer);
}
/// q = a ^ b
///
/// r 不得与 a 互为别名。
///
/// 断言 `r` 有足够的 limb 存储结果。上界为
/// `calcPowLimbsBufferLen(a.bitCountAbs(), b)`。
///
/// `limbs_buffer` 用作临时存储。
/// 所需大小由 `calcPowLimbsBufferLen` 给出。
pub fn pow(r: *Mutable, a: Const, b: u32, limbs_buffer: []Limb) void {
assert(r.limbs.ptr != a.limbs.ptr); // 非法别名关系
// 先处理所有简单情况
switch (b) {
0 => {
// a^0 = 1
return r.set(1);
},
1 => {
// a^1 = a
return r.copy(a);
},
else => {},
}
if (a.eqlZero()) {
// 0^b = 0
return r.set(0);
} else if (a.limbs.len == 1 and a.limbs[0] == 1) {
// 1^b = 1 且 -1^b = ±1
r.set(1);
r.positive = a.positive or (b & 1) == 0;
return;
}
// 此处 a>1 且 b>1
const needed_limbs = calcPowLimbsBufferLen(a.bitCountAbs(), b);
assert(r.limbs.len >= needed_limbs);
assert(limbs_buffer.len >= needed_limbs);
llpow(r.limbs, a.limbs, b, limbs_buffer);
r.normalize(needed_limbs);
r.positive = a.positive or (b & 1) == 0;
}
/// r = ⌊√a⌋
///
/// r 可以与 a 共用存储。
///
/// 断言 `r` 有足够的 limb 存储结果。上界为
/// `(a.limbs.len - 1) / 2 + 1`。
///
/// `limbs_buffer` 用作临时存储。
/// 所需大小由 `calcSqrtLimbsBufferLen` 给出。
pub fn sqrt(
r: *Mutable,
a: Const,
limbs_buffer: []Limb,
) void {
// Brent 和 Zimmermann,《现代计算机算术》,算法 1.13 SqrtInt
// https://members.loria.fr/PZimmermann/mca/pub226.html
var buf_index: usize = 0;
var t = b: {
const start = buf_index;
buf_index += a.limbs.len;
break :b Mutable.init(limbs_buffer[start..buf_index], 0);
};
var u = b: {
const start = buf_index;
const shift = (a.bitCountAbs() + 1) / 2;
buf_index += 1 + ((shift / limb_bits) + 1);
var m = Mutable.init(limbs_buffer[start..buf_index], 1);
m.shiftLeft(m.toConst(), shift); // u 必须 >= ⌊√a⌋,且为提高效率,应尽可能小
break :b m;
};
var s = b: {
const start = buf_index;
buf_index += u.limbs.len;
break :b u.toConst().toMutable(limbs_buffer[start..buf_index]);
};
var rem = b: {
const start = buf_index;
buf_index += s.limbs.len;
break :b Mutable.init(limbs_buffer[start..buf_index], 0);
};
while (true) {
t.divFloor(&rem, a, s.toConst(), limbs_buffer[buf_index..]);
t.add(t.toConst(), s.toConst());
u.shiftRight(t.toConst(), 1);
if (u.toConst().order(s.toConst()).compare(.gte)) {
r.copy(s.toConst());
return;
}
// 交换 u 和 s,避免将 u 复制到 s
const tmp_s = s;
s = u;
u = tmp_s;
}
}
/// rma 不得与 x 或 y 互为别名。
/// x 和 y 可以互为别名。
/// 断言 `rma` 有足够的 limb 存储结果,上界由 `calcGcdNoAliasLimbLen` 给出。
///
/// `limbs_buffer` 在操作期间用作临时存储。
pub fn gcdNoAlias(rma: *Mutable, x: Const, y: Const, limbs_buffer: *std.array_list.Managed(Limb)) !void {
assert(rma.limbs.ptr != x.limbs.ptr); // 非法别名关系
assert(rma.limbs.ptr != y.limbs.ptr); // 非法别名关系
return gcdLehmer(rma, x, y, limbs_buffer);
}
fn gcdLehmer(result: *Mutable, xa: Const, ya: Const, limbs_buffer: *std.array_list.Managed(Limb)) !void {
var x = try xa.toManaged(limbs_buffer.allocator);
defer x.deinit();
x.abs();
var y = try ya.toManaged(limbs_buffer.allocator);
defer y.deinit();
y.abs();
if (x.toConst().order(y.toConst()) == .lt) {
x.swap(&y);
}
var t_big = try Managed.init(limbs_buffer.allocator);
defer t_big.deinit();
var r = try Managed.init(limbs_buffer.allocator);
defer r.deinit();
var tmp_x = try Managed.init(limbs_buffer.allocator);
defer tmp_x.deinit();
while (y.len() > 1 and !y.eqlZero()) {
assert(x.isPositive() and y.isPositive());
assert(x.len() >= y.len());
var xh: SignedDoubleLimb = x.limbs[x.len() - 1];
var yh: SignedDoubleLimb = if (x.len() > y.len()) 0 else y.limbs[x.len() - 1];
var A: SignedDoubleLimb = 1;
var B: SignedDoubleLimb = 0;
var C: SignedDoubleLimb = 0;
var D: SignedDoubleLimb = 1;
while (yh + C != 0 and yh + D != 0) {
const q = @divFloor(xh + A, yh + C);
const qp = @divFloor(xh + B, yh + D);
if (q != qp) {
break;
}
var t = A - q * C;
A = C;
C = t;
t = B - q * D;
B = D;
D = t;
t = xh - q * yh;
xh = yh;
yh = t;
}
if (B == 0) {
// t_big = x % y,r 未使用
try r.divTrunc(&t_big, &x, &y);
assert(t_big.isPositive());
x.swap(&y);
y.swap(&t_big);
} else {
var storage: [8]Limb = undefined;
const Ap = fixedIntFromSignedDoubleLimb(A, storage[0..2]).toManaged(limbs_buffer.allocator);
const Bp = fixedIntFromSignedDoubleLimb(B, storage[2..4]).toManaged(limbs_buffer.allocator);
const Cp = fixedIntFromSignedDoubleLimb(C, storage[4..6]).toManaged(limbs_buffer.allocator);
const Dp = fixedIntFromSignedDoubleLimb(D, storage[6..8]).toManaged(limbs_buffer.allocator);
// t_big = Ax + By
try r.mul(&x, &Ap);
try t_big.mul(&y, &Bp);
try t_big.add(&r, &t_big);
// u = Cx + Dy,将 r 视作 u
try tmp_x.copy(x.toConst());
try x.mul(&tmp_x, &Cp);
try r.mul(&y, &Dp);
try r.add(&x, &r);
x.swap(&t_big);
y.swap(&r);
}
}
// 欧几里得算法
assert(x.toConst().order(y.toConst()) != .lt);
while (!y.toConst().eqlZero()) {
try t_big.divTrunc(&r, &x, &y);
x.swap(&y);
y.swap(&r);
}
result.copy(x.toConst());
}
// 默认截断。
fn div(q: *Mutable, r: *Mutable, x: *Mutable, y: *Mutable) void {
assert(!y.eqlZero()); // 除以零
assert(q != r); // 非法别名关系
const q_positive = (x.positive == y.positive);
const r_positive = x.positive;
if (x.toConst().orderAbs(y.toConst()) == .lt) {
// q 可能与 x 互为别名,因此先处理 r。
r.copy(x.toConst());
r.positive = r_positive;
q.set(0);
return;
}
// 处理除数和被除数末尾的全零字,下述算法不处理它们。
// 注意,两者都必须具有非零 limb。
// const x_trailing = std.mem.findScalar(Limb, x.limbs[0..x.len], 0).?;
// const y_trailing = std.mem.findScalar(Limb, y.limbs[0..y.len], 0).?;
//
const x_trailing = for (x.limbs[0..x.len], 0..) |xi, i| {
if (xi != 0) break i;
} else unreachable;
const y_trailing = for (y.limbs[0..y.len], 0..) |yi, i| {
if (yi != 0) break i;
} else unreachable;
const xy_trailing = @min(x_trailing, y_trailing);
if (y.len - xy_trailing == 1) {
const divisor = y.limbs[y.len - 1];
// 针对小除数的优化。使用半个 limb 可避免在热点代码路径中要求 DoubleLimb
// 除法,因为这类除法经常需要 compiler_rt 软件模拟。
if (divisor < maxInt(HalfLimb)) {
lldiv0p5(q.limbs, &r.limbs[0], x.limbs[xy_trailing..x.len], @as(HalfLimb, @intCast(divisor)));
} else {
lldiv1(q.limbs, &r.limbs[0], x.limbs[xy_trailing..x.len], divisor);
}
q.normalize(x.len - xy_trailing);
q.positive = q_positive;
r.len = 1;
r.positive = r_positive;
} else {
// 缩减 x、y,移除两者共有的尾随零 limb。
var x0: Mutable = .{
.limbs = x.limbs[xy_trailing..],
.len = x.len - xy_trailing,
.positive = true,
};
var y0: Mutable = .{
.limbs = y.limbs[xy_trailing..],
.len = y.len - xy_trailing,
.positive = true,
};
divmod(q, r, &x0, &y0);
q.positive = q_positive;
r.positive = r_positive;
}
if (xy_trailing != 0 and r.limbs[r.len - 1] != 0) {
// 已知按字对齐,因此在此手动移位。
@memmove(r.limbs[xy_trailing..][0..r.len], r.limbs[0..r.len]);
@memset(r.limbs[0..xy_trailing], 0);
r.len += xy_trailing;
}
}
/// 《应用密码学手册》,14.20
///
/// x = qy + r,其中 0 <= r < y
/// y 会被修改,但返回时恢复原状。
fn divmod(
q: *Mutable,
r: *Mutable,
x: *Mutable,
y: *Mutable,
) void {
// 0.
// 归一化,使 y[t] > b/2
const lz = @clz(y.limbs[y.len - 1]);
const norm_shift = if (lz == 0 and y.toConst().isOdd())
limb_bits // 强制添加一个 limb,使 y 为偶数。
else
lz;
x.shiftLeft(x.toConst(), norm_shift);
y.shiftLeft(y.toConst(), norm_shift);
const n = x.len - 1;
const t = y.len - 1;
const shift = n - t;
// 1.
// 对 0 <= j <= n - t,将 q[j] 设为 0
q.len = shift + 1;
q.positive = true;
@memset(q.limbs[0..q.len], 0);
// 2.
// while x >= y * b^(n - t):
// x -= y * b^(n - t)
// q[n - t] += 1
// 注意,若 y[t] > base/2 且 y 为偶数,此算法只执行一次;
// 步骤 0 已确保这些条件,因此可将 while 替换为 if。
// 乘以 b^(n - t) 实际上等同于右移 n - t 个 limb。
// 也可将 x >= y * b^(n - t) 改写为 x/b^(n - t) >= y,并利用移位。
{
// x >= y * b^(n - t) 可替换为 x/b^(n - t) >= y。
// 将 x 除以 b^(n - t)
var tmp: Mutable = .{
.limbs = x.limbs[shift..],
.len = x.len - shift,
.positive = true,
};
if (tmp.toConst().order(y.toConst()) != .lt) {
// 执行 x -= y * b^(n - t)。
// 注意,无需移位,只需从 x[n - t..] 中减去 y,即可得到结果。
// 也可以重用已经包含 x 对应部分的 tmp。注意,
// 此操作也会修改 x。
// 由于前面的检查,此处不会下溢。
tmp.sub(tmp.toConst(), y.toConst());
// tmp.sub 已规范化 tmp,但现在需要规范化 x。
x.limbs.len = tmp.limbs.len + shift;
q.limbs[shift] += 1;
}
}
// 3.
// 令 i 从 n 递减到 t + 1,执行
var i = n;
while (i >= t + 1) : (i -= 1) {
const k = i - t - 1;
// 步骤 3.1。
// if x_i == y_t:
// q[i - t - 1] = b - 1
// else:
// q[i - t - 1] = (x[i] * b + x[i - 1]) / y[t]
if (x.limbs[i] == y.limbs[t]) {
q.limbs[k] = maxInt(Limb);
} else {
const q0 = (@as(DoubleLimb, x.limbs[i]) << limb_bits) | @as(DoubleLimb, x.limbs[i - 1]);
const n0 = @as(DoubleLimb, y.limbs[t]);
q.limbs[k] = @as(Limb, @intCast(q0 / n0));
}
// 3.2
// while q[i - t - 1] * (y[t] * b + y[t - 1] > x[i] * b * b + x[i - 1] + x[i - 2]:
// q[i - t - 1] -= 1
// 注意,若 y[t] > b / 2,此部分最多重复两次。
// 从 y 中提取。
const y0 = if (t > 0) y.limbs[t - 1] else 0;
const y1 = y.limbs[t];
// 从 x 中提取。
// 注意:大端序。
const tmp0 = [_]Limb{
x.limbs[i],
if (i >= 1) x.limbs[i - 1] else 0,
if (i >= 2) x.limbs[i - 2] else 0,
};
while (true) {
// 与 q[i - t - 1] 进行特设的 2x1 乘法。
// 注意,使用大端序。
var tmp1 = [_]Limb{ 0, undefined, undefined };
tmp1[2] = addMulLimbWithCarry(0, y0, q.limbs[k], &tmp1[0]);
tmp1[1] = addMulLimbWithCarry(0, y1, q.limbs[k], &tmp1[0]);
// 大端序比较
if (mem.order(Limb, &tmp1, &tmp0) != .gt)
break;
q.limbs[k] -= 1;
}
// 3.3.
// x -= q[i - t - 1] * y * b^(i - t - 1)
// 注意,此处乘以单个 limb。
// 若将第一次乘法的结果加到 x[i - t - 1],
// 则无需执行移位。
const underflow = llmulLimb(.sub, x.limbs[k..x.len], y.limbs[0..y.len], q.limbs[k]);
// 3.4.
// if x < 0:
// x += y * b^(i - t - 1)
// q[i - t - 1] -= 1
// 注意,使用上一操作的下溢标志检查 x < 0。
if (underflow) {
// 虽然没有正确设置 x 的有符号性,但此操作应使它重新变为正数。
llaccum(.add, x.limbs[k..x.len], y.limbs[0..y.len]);
q.limbs[k] -= 1;
}
}
x.normalize(x.len);
q.normalize(q.len);
// 对 r 和 y 去正规化。
r.shiftRight(x.toConst(), norm_shift);
y.shiftRight(y.toConst(), norm_shift);
}
/// 遵循二进制补码语义,将整数截断到指定比特数。
/// `r` 可以与 `a` 互为别名。
///
/// 断言 `r` 有足够存储空间计算结果。
/// 上界为 `calcTwosCompLimbCount(a.len)`。
pub fn truncate(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void {
// 处理 0 位整数。
if (bit_count == 0) {
@branchHint(.unlikely);
r.set(0);
return;
}
const max_limbs = calcTwosCompLimbCount(bit_count);
const sign_bit = @as(Limb, 1) << @truncate(bit_count - 1);
const mask = @as(Limb, maxInt(Limb)) >> @truncate(-%bit_count);
// 猜测结果是否与 `a` 具有相同符号。
// * 若结果为有符号零,猜测为 `true`。
// * 若结果为最小有符号整数,猜测为 `false`。
// * 若结果为无符号零,猜测为 `a.positive`。
// * 其他情况,猜测正确。
const same_sign_guess = switch (signedness) {
.signed => max_limbs > a.limbs.len or a.limbs[max_limbs - 1] & sign_bit == 0,
.unsigned => a.positive,
};
const abs_trunc_a: Const = .{
.positive = true,
.limbs = a.limbs[0..llnormalize(a.limbs[0..@min(a.limbs.len, max_limbs)])],
};
if (same_sign_guess or abs_trunc_a.eqlZero()) {
// 以下条件之一成立:
// * 结果为零。
// * 结果非零,且符号与 `a` 相同。
r.copy(abs_trunc_a);
if (max_limbs <= r.len) r.limbs[max_limbs - 1] &= mask;
r.normalize(r.len);
r.positive = a.positive or r.eqlZero();
} else {
// 以下条件之一成立:
// * 结果为最小有符号整数。
// * 结果为无符号零。
// * 结果非零,且符号与 `a` 相反。
r.addScalar(abs_trunc_a, -1);
llnot(r.limbs[0..r.len]);
@memset(r.limbs[r.len..max_limbs], maxInt(Limb));
r.limbs[max_limbs - 1] &= mask;
r.normalize(max_limbs);
r.positive = switch (signedness) {
// 符号位仍然置位的唯一值是最小有符号整数。
.signed => !a.positive and r.limbs[max_limbs - 1] & sign_bit == 0,
.unsigned => !a.positive or r.eqlZero(),
};
}
}
/// 遵循二进制补码语义,将整数饱和到指定比特数。
/// r 可以与 a 互为别名。
///
/// 断言 `r` 有足够存储空间容纳结果。
/// 上界为 `calcTwosCompLimbCount(a.len)`。
pub fn saturate(r: *Mutable, a: Const, signedness: Signedness, bit_count: usize) void {
if (!a.fitsInTwosComp(signedness, bit_count)) {
r.setTwosCompIntLimit(if (r.positive) .max else .min, signedness, bit_count);
}
}
/// 从 `buffer` 读取 `x` 的值。
/// 断言 `buffer` 足以容纳位宽为 `bit_count` 的值。
///
/// 解释 `buffer` 内容时,将其视为
/// @ptrCast(*[buffer.len]const u8, &x) 的内容。字节顺序由 `endian` 决定,
/// 任何必要的填充位都应位于最高有效位一端。
pub fn readTwosComplement(
x: *Mutable,
buffer: []const u8,
bit_count: usize,
endian: Endian,
signedness: Signedness,
) void {
return readPackedTwosComplement(x, buffer, 0, bit_count, endian, signedness);
}
/// 从打包内存 `buffer` 读取 `x` 的值。
/// 断言 `buffer` 足够大,能够在偏移量 `bit_offset` 处
/// 容纳位大小为 `bit_count` 的值。
///
/// 等同于加载一个 `bit_count` 位整数,
/// 将其视为打包内存中给定位偏移处的字段。
pub fn readPackedTwosComplement(
x: *Mutable,
buffer: []const u8,
bit_offset: usize,
bit_count: usize,
endian: Endian,
signedness: Signedness,
) void {
if (bit_count == 0) {
x.limbs[0] = 0;
x.len = 1;
x.positive = true;
return;
}
// 检查输入是否为负数
var positive = true;
if (signedness == .signed) {
const total_bits = bit_offset + bit_count;
const last_byte = switch (endian) {
.little => ((total_bits + 7) / 8) - 1,
.big => buffer.len - ((total_bits + 7) / 8),
};
const sign_bit = @as(u8, 1) << @as(u3, @intCast((total_bits - 1) % 8));
positive = ((buffer[last_byte] & sign_bit) == 0);
}
// 复制所有完整的大整数 limb
var carry: u1 = 1;
var limb_index: usize = 0;
var bit_index: usize = 0;
while (limb_index < bit_count / @bitSizeOf(Limb)) : (limb_index += 1) {
// 读取一个 Limb 的位
var limb = mem.readPackedInt(Limb, buffer, bit_index + bit_offset, endian);
bit_index += @bitSizeOf(Limb);
// 二进制补码(先按位取反,再加进位位)。
if (!positive) {
const ov = @addWithOverflow(~limb, carry);
limb = ov[0];
carry = ov[1];
}
x.limbs[limb_index] = limb;
}
// 复制剩余位
if (bit_count != bit_index) {
// 读取所有剩余位
var limb = switch (signedness) {
.unsigned => mem.readVarPackedInt(Limb, buffer, bit_index + bit_offset, bit_count - bit_index, endian, .unsigned),
.signed => b: {
const SLimb = @Int(.signed, @bitSizeOf(Limb));
const limb = mem.readVarPackedInt(SLimb, buffer, bit_index + bit_offset, bit_count - bit_index, endian, .signed);
break :b @as(Limb, @bitCast(limb));
},
};
// 二进制补码(先按位取反,再加进位位)。
if (!positive) {
const ov = @addWithOverflow(~limb, carry);
assert(ov[1] == 0);
limb = ov[0];
}
x.limbs[limb_index] = limb;
limb_index += 1;
}
x.positive = positive;
x.len = limb_index;
x.normalize(x.len);
}
/// 规范化可能存在的前导零序列。
///
/// [1, 2, 3, 4, 0] -> [1, 2, 3, 4]
/// [1, 2, 0, 0, 0] -> [1, 2]
/// [0, 0, 0, 0, 0] -> [0]
pub fn normalize(r: *Mutable, length: usize) void {
r.len = llnormalize(r.limbs[0..length]);
}
pub fn format(self: Mutable, w: *std.Io.Writer) std.Io.Writer.Error!void {
return formatNumber(self, w, .{});
}
/// 若整数的绝对值大于或等于 `pow(2, 64 * @sizeOf(usize) * 8)`,
/// 此函数无法打印数值字符串,改为输出 "(BigInt)"。
/// 原因是渲染算法需要反转字符串,从而需要 O(N) 内存。
/// 不会因此失败的大整数打印方式参见 `Const.toString` 和 `Const.toStringAlloc`。
pub fn formatNumber(self: Mutable, w: *std.Io.Writer, n: std.fmt.Number) std.Io.Writer.Error!void {
return self.toConst().formatNumber(w, n);
}
};
/// 具有固定不可变字集合的任意精度大整数。
pub const Const = struct {
/// 原始数位,具有以下性质:
///
/// * 小端顺序
/// * limbs.len >= 1
/// * 零表示为 limbs.len == 1 且 limbs[0] == 0。
///
/// 应避免直接访问 limbs。
limbs: []const Limb,
positive: bool,
/// 结果是由调用方管理的独立资源。
pub fn toManaged(self: Const, allocator: Allocator) Allocator.Error!Managed {
const limbs = try allocator.alloc(Limb, @max(Managed.default_capacity, self.limbs.len));
@memcpy(limbs[0..self.limbs.len], self.limbs);
return .{
.allocator = allocator,
.limbs = limbs,
.metadata = if (self.positive)
self.limbs.len & ~Managed.sign_bit
else
self.limbs.len | Managed.sign_bit,
};
}
/// 断言 `limbs` 足够大,能够存储该值。
pub fn toMutable(self: Const, limbs: []Limb) Mutable {
@memcpy(limbs[0..self.limbs.len], self.limbs[0..self.limbs.len]);
return .{
.limbs = limbs,
.positive = self.positive,
.len = self.limbs.len,
};
}
pub fn dump(self: Const) void {
for (self.limbs[0..self.limbs.len]) |limb| {
std.debug.print("{x} ", .{limb});
}
std.debug.print("len={} positive={}\n", .{ self.limbs.len, self.positive });
}
pub fn abs(self: Const) Const {
return .{
.limbs = self.limbs,
.positive = true,
};
}
pub fn negate(self: Const) Const {
return .{
.limbs = self.limbs,
.positive = !self.positive,
};
}
pub fn isOdd(self: Const) bool {
return self.limbs[0] & 1 != 0;
}
pub fn isEven(self: Const) bool {
return !self.isOdd();
}
/// 返回表示整数绝对值所需的位数。
pub fn bitCountAbs(self: Const) usize {
return (self.limbs.len - 1) * limb_bits + (limb_bits - @clz(self.limbs[self.limbs.len - 1]));
}
/// 返回以二进制补码形式表示该整数所需的位数。
///
/// 若整数为负,返回有符号整数表示该值
/// 所需的位数。若为正,则返回无符号整数
/// 所需的位数。任意无符号整数均可放入位数
/// 比返回值多一位的有符号整数。
///
/// 例如,-127 返回 8,因为可放入 i8;127 返回 7,因为可放入 u7。
pub fn bitCountTwosComp(self: Const) usize {
var bits = self.bitCountAbs();
// 若整个值只有一个位置位(例如 0b100000000),则其二进制补码取反结果少需一位。
//
if (!self.positive) block: {
bits += 1;
if (@popCount(self.limbs[self.limbs.len - 1]) == 1) {
for (self.limbs[0 .. self.limbs.len - 1]) |limb| {
if (@popCount(limb) != 0) {
break :block;
}
}
bits -= 1;
}
}
return bits;
}
/// 返回按照给定的有符号性,以二进制补码形式表示
/// 该整数所需的位数。
pub fn bitCountTwosCompForSignedness(self: Const, signedness: std.builtin.Signedness) usize {
return self.bitCountTwosComp() + @intFromBool(self.positive and signedness == .signed);
}
/// 具有二进制补码语义的 @popCount。
///
/// 返回此值按给定整数位宽 bit_count 表示为
/// 二进制补码时,值为 1 的位的数量。
/// 包括最前面的符号位,负值的符号位为 1。
///
/// 断言 bit_count 足以用二进制补码表示 value,
/// 且最终结果可容纳于 usize。
/// 断言最高有效端没有多余的空 limb,
/// 即 limb 数量与 `calcLimbLen()` 匹配,且零不为负数。
pub fn popCount(self: Const, bit_count: usize) usize {
var sum: usize = 0;
if (self.positive) {
for (self.limbs) |limb| {
sum += @popCount(limb);
}
} else {
assert(self.fitsInTwosComp(.signed, bit_count));
assert(self.limbs[self.limbs.len - 1] != 0);
var remaining_bits = bit_count;
var carry: u1 = 1;
var add_res: Limb = undefined;
// 除最高有效 limb 外的所有 limb。
for (self.limbs[0 .. self.limbs.len - 1]) |limb| {
const ov = @addWithOverflow(~limb, carry);
add_res = ov[0];
carry = ov[1];
sum += @popCount(add_res);
remaining_bits -= limb_bits; // fitsInTwosComp 已断言不会下溢
}
// 最高有效 limb 的有效位数可能少于 @bitSizeOf(Limb),
// 可用 @clz() 检测。
// limb 的数量也可能不足以填满 bit_count。
const limb = self.limbs[self.limbs.len - 1];
const leading_zeroes = @clz(limb);
// 上方已断言最高有效 limb 不全为 0,
// 因此 ~limb 不可能全为 1,~limb + 1 不可能溢出。
sum += @popCount(~limb + carry);
sum -= leading_zeroes; // 所有前导零均被翻转并加入 sum,因此撤销这些影响。
const remaining_ones = remaining_bits - (limb_bits - leading_zeroes); // 所有未被 Limb 覆盖的位
sum += remaining_ones;
}
return sum;
}
pub fn fitsInTwosComp(self: Const, signedness: Signedness, bit_count: usize) bool {
if (self.eqlZero()) {
return true;
}
if (signedness == .unsigned and !self.positive) {
return false;
}
return bit_count >= self.bitCountTwosCompForSignedness(signedness);
}
/// 返回 self 是否可容纳于请求类型的整数。
pub fn fits(self: Const, comptime T: type) bool {
const info = @typeInfo(T).int;
return self.fitsInTwosComp(info.signedness, info.bits);
}
/// 返回整数在给定进制下的大致表示长度,负数会计入负号。
/// 用于确定输出该值所需的字符数量。结果不精确,可能比实际值多约 1–2 字节。
/// TODO: 研究能否精确计算。
///
pub fn sizeInBaseUpperBound(self: Const, base: usize) usize {
const bit_count = @as(usize, @intFromBool(!self.positive)) + self.bitCountAbs();
return (bit_count / math.log2(base)) + 2;
}
pub const ConvertError = error{
NegativeIntoUnsigned,
TargetTooSmall,
};
/// 将 `self` 转换为 `Int`。
///
/// 若无法在不截断的情况下将 self 缩窄为请求类型,则返回错误。
pub fn toInt(self: Const, comptime Int: type) ConvertError!Int {
switch (@typeInfo(Int)) {
.int => |info| {
// 确保正确处理 -0。
if (self.eqlZero()) return 0;
const Unsigned = @Int(.unsigned, info.bits);
if (!self.fitsInTwosComp(info.signedness, info.bits)) {
return error.TargetTooSmall;
}
var r: Unsigned = 0;
if (@sizeOf(Unsigned) <= @sizeOf(Limb)) {
r = @intCast(self.limbs[0]);
} else {
for (self.limbs[0..self.limbs.len], 0..) |_, ri| {
const limb = self.limbs[self.limbs.len - ri - 1];
r <<= limb_bits;
r |= limb;
}
}
if (info.signedness == .unsigned) {
return if (self.positive) @intCast(r) else error.NegativeIntoUnsigned;
} else {
if (self.positive) {
return @intCast(r);
} else {
if (math.cast(Int, r)) |ok| {
return -ok;
} else {
return minInt(Int);
}
}
}
},
else => @compileError("expected int type, found '" ++ @typeName(Int) ++ "'"),
}
}
/// 将自身转换为 `Float`。
pub fn toFloat(self: Const, comptime Float: type, round: Round) struct { Float, Exactness } {
if (Float == comptime_float) return self.toFloat(f128, round);
const normalized_abs: Const = .{
.limbs = self.limbs[0..llnormalize(self.limbs)],
.positive = true,
};
if (normalized_abs.eqlZero()) return .{ if (self.positive) 0.0 else -0.0, .exact };
const Repr = std.math.FloatRepr(Float);
var mantissa_limbs: [calcNonZeroTwosCompLimbCount(1 + @bitSizeOf(Repr.Mantissa))]Limb = undefined;
var mantissa: Mutable = .{
.limbs = &mantissa_limbs,
.positive = undefined,
.len = undefined,
};
var exponent = normalized_abs.bitCountAbs() - 1;
const exactness: Exactness = exactness: {
if (exponent <= @bitSizeOf(Repr.Normalized.Fraction)) {
mantissa.shiftLeft(normalized_abs, @intCast(@bitSizeOf(Repr.Normalized.Fraction) - exponent));
break :exactness .exact;
}
const shift: usize = @intCast(exponent - @bitSizeOf(Repr.Normalized.Fraction));
mantissa.shiftRight(normalized_abs, shift);
const final_limb_index = (shift - 1) / limb_bits;
const round_bits = normalized_abs.limbs[final_limb_index] << @truncate(-%shift) |
@intFromBool(!std.mem.allEqual(Limb, normalized_abs.limbs[0..final_limb_index], 0));
if (round_bits == 0) break :exactness .exact;
round: switch (round) {
.nearest_even => {
const half: Limb = 1 << (limb_bits - 1);
if (round_bits >= half) mantissa.addScalar(mantissa.toConst(), 1);
if (round_bits == half) mantissa.limbs[0] &= ~@as(Limb, 1);
},
.away => mantissa.addScalar(mantissa.toConst(), 1),
.trunc => {},
.floor => if (!self.positive) continue :round .away,
.ceil => if (self.positive) continue :round .away,
}
break :exactness .inexact;
};
const normalized_res: Repr.Normalized = .{
.fraction = @truncate(mantissa.toInt(Repr.Mantissa) catch |err| switch (err) {
error.NegativeIntoUnsigned => unreachable,
error.TargetTooSmall => fraction: {
assert(mantissa.toConst().orderAgainstScalar(1 << @bitSizeOf(Repr.Mantissa)).compare(.eq));
exponent += 1;
break :fraction 1 << (@bitSizeOf(Repr.Mantissa) - 1);
},
}),
.exponent = std.math.lossyCast(Repr.Normalized.Exponent, exponent),
};
return .{ normalized_res.reconstruct(if (self.positive) .positive else .negative), exactness };
}
pub fn format(self: Const, w: *std.Io.Writer) std.Io.Writer.Error!void {
return self.formatNumber(w, .{});
}
/// 若整数的绝对值大于或等于 `pow(2, 64 * @sizeOf(usize) * 8)`,
/// 此函数无法打印数值字符串,改为输出 "(BigInt)"。
/// 原因是渲染算法需要反转字符串,从而需要 O(N) 内存。
/// 不会因此失败的大整数打印方式参见 `toString` 和 `toStringAlloc`。
pub fn formatNumber(self: Const, w: *std.Io.Writer, number: std.fmt.Number) std.Io.Writer.Error!void {
const available_len = 64;
if (self.limbs.len > available_len)
return w.writeAll("(BigInt)");
var limbs: [calcToStringLimbsBufferLen(available_len, 10)]Limb = undefined;
const biggest: Const = .{
.limbs = &@as([available_len]Limb, @splat(comptime math.maxInt(Limb))),
.positive = false,
};
var buf: [biggest.sizeInBaseUpperBound(2)]u8 = undefined;
const base: u8 = number.mode.base() orelse @panic("TODO print big int in scientific form");
const len = self.toString(&buf, base, number.case, &limbs);
return w.writeAll(buf[0..len]);
}
/// 将自身转换为指定进制的字符串。
/// 调用者拥有返回内存的所有权。
/// 断言 `base` 位于范围 [2, 36]。
/// 另见比此函数更底层的 `toString`。
pub fn toStringAlloc(self: Const, allocator: Allocator, base: u8, case: std.fmt.Case) Allocator.Error![]u8 {
assert(base >= 2);
assert(base <= 36);
if (self.eqlZero()) {
return allocator.dupe(u8, "0");
}
const string = try allocator.alloc(u8, self.sizeInBaseUpperBound(base));
errdefer allocator.free(string);
const limbs = try allocator.alloc(Limb, calcToStringLimbsBufferLen(self.limbs.len, base));
defer allocator.free(limbs);
return allocator.realloc(string, self.toString(string, base, case, limbs));
}
/// 将自身转换为指定进制的字符串。
/// 断言 `base` 位于 [2, 36] 范围内。
/// `string` 为调用方提供、至少长 `sizeInBaseUpperBound` 字节的切片,
/// 用于写入结果。
/// 返回字符串长度。
/// `limbs_buffer` 是调用方提供给 `toString` 的工作区内存,其
/// 长度必须至少为 `calcToStringLimbsBufferLen`。
/// 进制为二的幂时,忽略 `limbs_buffer`。
/// 另请参见更高层函数 `toStringAlloc`。
pub fn toString(self: Const, string: []u8, base: u8, case: std.fmt.Case, limbs_buffer: []Limb) usize {
assert(base >= 2);
assert(base <= 36);
if (self.eqlZero()) {
string[0] = '0';
return 1;
}
var digits_len: usize = 0;
// 2 的幂:可以单遍处理,并用掩码提取数字。
if (math.isPowerOfTwo(base)) {
const base_shift = math.log2_int(Limb, base);
outer: for (self.limbs[0..self.limbs.len]) |limb| {
var shift: usize = 0;
while (shift < limb_bits) : (shift += base_shift) {
const r = @as(u8, @intCast((limb >> @as(Log2Limb, @intCast(shift))) & @as(Limb, base - 1)));
const ch = std.fmt.digitToChar(r, case);
string[digits_len] = ch;
digits_len += 1;
// 若已到末尾,则此后必须全部为零。
if (digits_len == string.len) break :outer;
}
}
// 总会在某个位置包含非零数位。
while (string[digits_len - 1] == '0') {
digits_len -= 1;
}
} else {
// 非 2 的幂:按字长批量进行除法。
// 此处使用 HalfLimb,使除法走更快的 lldiv0p5 路径而非 lldiv1 路径。
const digits_per_limb = math.log(HalfLimb, base, maxInt(HalfLimb));
var limb_base: Limb = 1;
var j: usize = 0;
while (j < digits_per_limb) : (j += 1) {
limb_base *= base;
}
const b: Const = .{ .limbs = &[_]Limb{limb_base}, .positive = true };
var q: Mutable = .{
.limbs = limbs_buffer[0 .. self.limbs.len + 2],
.positive = true, // 忽略 self.positive,以取得绝对值。
.len = self.limbs.len,
};
@memcpy(q.limbs[0..self.limbs.len], self.limbs);
var r: Mutable = .{
.limbs = limbs_buffer[q.limbs.len..][0..self.limbs.len],
.positive = true,
.len = 1,
};
r.limbs[0] = 0;
const rest_of_the_limbs_buf = limbs_buffer[q.limbs.len + r.limbs.len ..];
while (q.len >= 2) {
// 此处传入分配器没有帮助,因为该除法会丢失信息,
// 而非产生信息。[TODO: 需要引用依据]
q.divTrunc(&r, q.toConst(), b, rest_of_the_limbs_buf);
var r_word = r.limbs[0];
var i: usize = 0;
while (i < digits_per_limb) : (i += 1) {
const ch = std.fmt.digitToChar(@as(u8, @intCast(r_word % base)), case);
r_word /= base;
string[digits_len] = ch;
digits_len += 1;
}
}
{
assert(q.len == 1);
var r_word = q.limbs[0];
while (r_word != 0) {
const ch = std.fmt.digitToChar(@as(u8, @intCast(r_word % base)), case);
r_word /= base;
string[digits_len] = ch;
digits_len += 1;
}
}
}
if (!self.positive) {
string[digits_len] = '-';
digits_len += 1;
}
const s = string[0..digits_len];
mem.reverse(u8, s);
return s.len;
}
/// 将 `x` 的值写入 `buffer`。
/// 断言 `buffer` 足以存储该值。
///
/// 填充 `buffer`,使其内容与通过
/// @ptrCast(*[buffer.len]const u8, &x) 观察到的内容一致。字节顺序由 `endian` 决定,
/// 任何必要的填充位都添加在最高有效位一端。
pub fn writeTwosComplement(x: Const, buffer: []u8, endian: Endian) void {
return writePackedTwosComplement(x, buffer, 0, 8 * buffer.len, endian);
}
/// 将 `x` 的值写入紧凑内存 `buffer`。
/// 断言 `buffer` 足够大,能容纳位数为 `bit_count` 的值,位置为偏移 `bit_offset`。
///
/// 这等价于将一个具有 `bit_count` 位的整数值,视为紧凑内存中位于给定位偏移的字段进行存储。
///
///
pub fn writePackedTwosComplement(x: Const, buffer: []u8, bit_offset: usize, bit_count: usize, endian: Endian) void {
assert(x.fitsInTwosComp(if (x.positive) .unsigned else .signed, bit_count));
// 复制所有完整的大整数 limb
var carry: u1 = 1;
var limb_index: usize = 0;
var bit_index: usize = 0;
while (limb_index < bit_count / @bitSizeOf(Limb)) : (limb_index += 1) {
var limb: Limb = if (limb_index < x.limbs.len) x.limbs[limb_index] else 0;
// 二进制补码(先按位取反,再加进位位)。
if (!x.positive) {
const ov = @addWithOverflow(~limb, carry);
limb = ov[0];
carry = ov[1];
}
// 写入一个大整数 limb 的位
mem.writePackedInt(Limb, buffer, bit_index + bit_offset, limb, endian);
bit_index += @bitSizeOf(Limb);
}
// 复制剩余位
if (bit_count != bit_index) {
var limb: Limb = if (limb_index < x.limbs.len) x.limbs[limb_index] else 0;
// 二进制补码(先按位取反,再加进位位)。
if (!x.positive) limb = ~limb +% carry;
// 写出所有剩余位
mem.writeVarPackedInt(buffer, bit_index + bit_offset, bit_count - bit_index, limb, endian);
}
}
/// 当 `|a| < |b|`、`|a| == |b|` 或 `|a| > |b|` 时,分别返回 `math.Order.lt`、`math.Order.eq`、`math.Order.gt`。
///
pub fn orderAbs(a: Const, b: Const) math.Order {
if (a.limbs.len < b.limbs.len) {
return .lt;
}
if (a.limbs.len > b.limbs.len) {
return .gt;
}
var i: usize = a.limbs.len - 1;
while (i != 0) : (i -= 1) {
if (a.limbs[i] != b.limbs[i]) {
break;
}
}
if (a.limbs[i] < b.limbs[i]) {
return .lt;
} else if (a.limbs[i] > b.limbs[i]) {
return .gt;
} else {
return .eq;
}
}
/// 当 `a < b`、`a == b` 或 `a > b` 时,分别返回 `math.Order.lt`、`math.Order.eq`、`math.Order.gt`。
pub fn order(a: Const, b: Const) math.Order {
if (a.positive != b.positive) {
if (eqlZero(a) and eqlZero(b)) {
return .eq;
} else {
return if (a.positive) .gt else .lt;
}
} else {
const r = orderAbs(a, b);
return if (a.positive) r else switch (r) {
.lt => math.Order.gt,
.eq => math.Order.eq,
.gt => math.Order.lt,
};
}
}
/// 与 `order` 相同,但右侧操作数是原始整数。
pub fn orderAgainstScalar(lhs: Const, scalar: anytype) math.Order {
// 通常可以直接用 calcLimbLen 确定所需 limb 数量,
// 但当 scalar 不是 comptime_int 时,此数量在编译期未知。因此,
// 对于非 comptime_int 标量,改用 calcTwosCompLimbCount。如果 scalar 在其类型中
// 恰好具有较小的绝对值,该方法可能过于保守,但
// 能够使用栈且无需传入分配器,仍然值得。
// 注意,无论如何,Mutable.init 仍会将 len 设置为 calcLimbLen(scalar)。
const limbs_len = comptime switch (@typeInfo(@TypeOf(scalar))) {
.comptime_int => calcLimbLen(scalar),
.int => |info| calcTwosCompLimbCount(info.bits),
else => @compileError("expected scalar to be an int"),
};
var limbs: [limbs_len]Limb = undefined;
const rhs = Mutable.init(&limbs, scalar);
return order(lhs, rhs.toConst());
}
/// 若 `a == 0` 则返回 true。
pub fn eqlZero(a: Const) bool {
var d: Limb = 0;
for (a.limbs) |limb| d |= limb;
return d == 0;
}
/// 若 `|a| == |b|`,返回 true。
pub fn eqlAbs(a: Const, b: Const) bool {
return orderAbs(a, b) == .eq;
}
/// 若 `a == b`,返回 true。
pub fn eql(a: Const, b: Const) bool {
return order(a, b) == .eq;
}
/// 返回二进制补码形式中的前导零数量。
pub fn clz(a: Const, bits: Limb) Limb {
// 字按小端顺序存储,但需要按大端顺序遍历。
if (!a.positive and !a.eqlZero()) return 0;
var total_limb_lz: Limb = 0;
var i: usize = a.limbs.len;
const bits_per_limb = @bitSizeOf(Limb);
while (i != 0) {
i -= 1;
const this_limb_lz = @clz(a.limbs[i]);
total_limb_lz += this_limb_lz;
if (this_limb_lz != bits_per_limb) break;
}
const total_limb_bits = a.limbs.len * bits_per_limb;
return total_limb_lz + bits - total_limb_bits;
}
/// 返回二进制补码形式中的尾随零数量。
pub fn ctz(a: Const, bits: Limb) Limb {
// limb 按小端序存储。将负数转换为二进制补码时,
// 会翻转最低置位位之上的所有位,不影响尾随零的数量。
if (a.eqlZero()) return bits;
var result: Limb = 0;
for (a.limbs) |limb| {
const limb_tz = @ctz(limb);
result += limb_tz;
if (limb_tz != @bitSizeOf(Limb)) break;
}
return @min(result, bits);
}
/// 计算以 2 为底的对数,并向下取整。
pub fn log2(a: Const) Limb {
assert(a.positive);
assert(!a.eqlZero());
return a.bitCountAbs() - 1;
}
/// 计算以 10 为底的对数,向下取整。
///
/// 分配器用于分配临时缓冲区。
pub fn log10Alloc(a: Const, allocator: Allocator) Allocator.Error!Limb {
const limbs_buffer = try allocator.alloc(Limb, calcLog10LimbsBufferLen(a.limbs.len));
defer allocator.free(limbs_buffer);
return a.log10(limbs_buffer);
}
/// 计算以 10 为底的对数,向下取整。
///
/// `limbs_buffer` 用作临时存储。所需大小由 `calcLog10LimbsBufferLen` 给出。
pub fn log10(a: Const, limbs_buffer: []Limb) Limb {
assert(a.positive);
assert(!a.eqlZero());
const limb_base_as_bigint: Const = .{ .limbs = &.{constants.big_bases[10]}, .positive = true };
var q: Mutable = .{
.limbs = limbs_buffer[0 .. a.limbs.len + 2],
.positive = true,
.len = a.limbs.len,
};
@memcpy(q.limbs[0..a.limbs.len], a.limbs);
var remainder: Mutable = .{
.limbs = limbs_buffer[q.limbs.len..][0..a.limbs.len],
.positive = true,
.len = 1,
};
const division_buf = limbs_buffer[q.limbs.len + remainder.limbs.len ..];
var num_digits: Limb = 0;
while (q.len >= 2) {
q.divTrunc(&remainder, q.toConst(), limb_base_as_bigint, division_buf);
num_digits += constants.digits_per_limb[10];
}
var remaining_limb = q.limbs[0];
while (remaining_limb != 0) {
remaining_limb /= 10;
num_digits += 1;
}
return num_digits - 1;
}
};
/// 附带管理内存的分配器的任意精度大整数。
///
/// 按需分配内存,以确保操作永不溢出。取值范围
/// 仅受可用内存限制。
pub const Managed = struct {
pub const sign_bit: usize = 1 << (@typeInfo(usize).int.bits - 1);
/// 创建 `Managed` 时默认分配的 limb 数量。
pub const default_capacity = 4;
/// Managed 请求内存时使用的分配器。
allocator: Allocator,
/// 原始数位,具有以下性质:
///
/// * 小端顺序
/// * limbs.len >= 1
/// * 零表示为 Managed.len() == 1 且 limbs[0] == 0。
///
/// 应避免直接访问 limbs。
limbs: []Limb,
/// 最高位为符号位。置位时 Managed 为负,否则为正。
/// 其余位表示 Managed 使用的 limb 数量。
metadata: usize,
/// 创建新的 `Managed`。立即分配 `default_capacity` 个字。
/// 初始化后的整数值为 `0`。
pub fn init(allocator: Allocator) !Managed {
return initCapacity(allocator, default_capacity);
}
pub fn toMutable(self: Managed) Mutable {
return .{
.limbs = self.limbs,
.positive = self.isPositive(),
.len = self.len(),
};
}
pub fn toConst(self: Managed) Const {
return .{
.limbs = self.limbs[0..self.len()],
.positive = self.isPositive(),
};
}
/// 创建值为 `value` 的新 `Managed`。
///
/// 等同于先调用 `init`,再调用 `set`。
pub fn initSet(allocator: Allocator, value: anytype) !Managed {
var s = try Managed.init(allocator);
errdefer s.deinit();
try s.set(value);
return s;
}
/// 创建具有指定容量的新 Managed。若 capacity < default_capacity,
/// 则改用默认容量。
/// 初始化后的整数值为 `0`。
pub fn initCapacity(allocator: Allocator, capacity: usize) !Managed {
return .{
.allocator = allocator,
.metadata = 1,
.limbs = block: {
const limbs = try allocator.alloc(Limb, @max(default_capacity, capacity));
limbs[0] = 0;
break :block limbs;
},
};
}
/// 返回当前使用中的 limb 数量。
pub fn len(self: Managed) usize {
return self.metadata & ~sign_bit;
}
/// 返回 Managed 是否为正。
pub fn isPositive(self: Managed) bool {
return self.metadata & sign_bit == 0;
}
/// 设置 Managed 的符号。
pub fn setSign(self: *Managed, positive: bool) void {
if (positive) {
self.metadata &= ~sign_bit;
} else {
self.metadata |= sign_bit;
}
}
/// 设置 Managed 的长度。
///
/// 如果使用 setLen,则必须相应地规范化 Managed。
pub fn setLen(self: *Managed, new_len: usize) void {
self.metadata &= sign_bit;
self.metadata |= new_len;
}
pub fn setMetadata(self: *Managed, positive: bool, length: usize) void {
self.metadata = if (positive) length & ~sign_bit else length | sign_bit;
}
/// 确保 Managed 已分配足以容纳 capacity 个 limb 的空间。若 Managed 容量不足,
/// 将精确分配所需大小。即使所请求容量仅比当前容量
/// 多一个 limb,也会执行分配。
pub fn ensureCapacity(self: *Managed, capacity: usize) !void {
if (capacity <= self.limbs.len) {
return;
}
self.limbs = try self.allocator.realloc(self.limbs, capacity);
}
/// 释放所有关联内存。
pub fn deinit(self: *Managed) void {
self.allocator.free(self.limbs);
self.* = undefined;
}
/// 返回同值的 `Managed`。返回的 `Managed` 是深拷贝,
/// 可独立于原对象修改,其资源也独立于原对象
/// 管理。
pub fn clone(other: Managed) !Managed {
return other.cloneWithDifferentAllocator(other.allocator);
}
pub fn cloneWithDifferentAllocator(other: Managed, allocator: Allocator) !Managed {
return .{
.allocator = allocator,
.metadata = other.metadata,
.limbs = block: {
const limbs = try allocator.alloc(Limb, other.len());
@memcpy(limbs, other.limbs[0..other.len()]);
break :block limbs;
},
};
}
/// 将整数值复制到已有的 `Managed`,使二者具有相同值。
/// 若接收方容量不足,则分配额外内存。
pub fn copy(self: *Managed, other: Const) !void {
if (self.limbs.ptr == other.limbs.ptr) return;
try self.ensureCapacity(other.limbs.len);
@memcpy(self.limbs[0..other.limbs.len], other.limbs[0..other.limbs.len]);
self.setMetadata(other.positive, other.limbs.len);
}
/// 高效地交换两个 `Managed`。仅交换 limb 指针,不执行完整复制。
/// 调用此函数后,limbs 字段的地址将发生变化。
pub fn swap(self: *Managed, other: *Managed) void {
mem.swap(Managed, self, other);
}
/// 调试工具:将状态输出到 stderr。
pub fn dump(self: Managed) void {
for (self.limbs[0..self.len()]) |limb| {
std.debug.print("{x} ", .{limb});
}
std.debug.print("len={} capacity={} positive={}\n", .{ self.len(), self.limbs.len, self.isPositive() });
}
/// 对符号取反。
pub fn negate(self: *Managed) void {
self.metadata ^= sign_bit;
}
/// 变为正数。
pub fn abs(self: *Managed) void {
self.metadata &= ~sign_bit;
}
pub fn isOdd(self: Managed) bool {
return self.limbs[0] & 1 != 0;
}
pub fn isEven(self: Managed) bool {
return !self.isOdd();
}
/// 返回表示整数绝对值所需的位数。
pub fn bitCountAbs(self: Managed) usize {
return self.toConst().bitCountAbs();
}
/// 返回以二进制补码形式表示该整数所需的位数。
///
/// 若整数为负,返回有符号整数表示该值
/// 所需的位数。若为正,则返回无符号整数
/// 所需的位数。任意无符号整数均可放入位数
/// 比返回值多一位的有符号整数。
///
/// 例如,-127 返回 8,因为可放入 i8;127 返回 7,因为可放入 u7。
pub fn bitCountTwosComp(self: Managed) usize {
return self.toConst().bitCountTwosComp();
}
pub fn fitsInTwosComp(self: Managed, signedness: Signedness, bit_count: usize) bool {
return self.toConst().fitsInTwosComp(signedness, bit_count);
}
/// 返回 self 是否可容纳于请求类型的整数。
pub fn fits(self: Managed, comptime T: type) bool {
return self.toConst().fits(T);
}
/// 返回给定进制下整数的近似大小。负值会为负号留出空间。
/// 此值用于确定打印该值所需的字符数。它并不精确,
/// 可能比给定值多出约 1 至 2 字节。
pub fn sizeInBaseUpperBound(self: Managed, base: usize) usize {
return self.toConst().sizeInBaseUpperBound(base);
}
/// 将 Managed 设置为 value。value 必须为基本整数类型。
pub fn set(self: *Managed, value: anytype) Allocator.Error!void {
try self.ensureCapacity(calcLimbLen(value));
var m = self.toMutable();
m.set(value);
self.setMetadata(m.positive, m.len);
}
pub const ConvertError = Const.ConvertError;
/// 将 `self` 转换为 `Int`。
///
/// 若无法在不截断的情况下将 self 缩窄为请求类型,则返回错误。
pub fn toInt(self: Managed, comptime Int: type) ConvertError!Int {
return self.toConst().toInt(Int);
}
/// 将 `self` 转换为 `Float`。
pub fn toFloat(self: Managed, comptime Float: type, round: Round) struct { Float, Exactness } {
return self.toConst().toFloat(Float, round);
}
/// 根据字符串表示 `value` 设置自身。
///
/// `value` 只能包含不大于 `base` 的数字,且不区分大小写。不允许进制前缀,例如 0x43 应直接写作 43。输入字符串中的下划线会被忽略,可用作数字分隔符。
///
/// 若无法分配内存,或 `value` 中包含对指定进制无效的数字,则返回错误。
///
/// 使用自身的分配器提供临时存储,以提升乘法性能。
///
///
///
pub fn setString(self: *Managed, base: u8, value: []const u8) !void {
if (base < 2 or base > 36) return error.InvalidBase;
try self.ensureCapacity(calcSetStringLimbCount(base, value.len));
var m = self.toMutable();
try m.setString(base, value);
self.setMetadata(m.positive, m.len);
}
/// 将 self 设为二进制补码整数的上界或下界。
/// 注意:结果仍采用符号数值表示,而非二进制补码!要将结果转换为
/// 二进制补码,只需取其绝对值。
pub fn setTwosCompIntLimit(
r: *Managed,
limit: TwosCompIntLimit,
signedness: Signedness,
bit_count: usize,
) !void {
try r.ensureCapacity(calcTwosCompLimbCount(bit_count));
var m = r.toMutable();
m.setTwosCompIntLimit(limit, signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// 将 self 转换为指定基数的字符串。内存由提供的分配器分配,而不是 self 中的分配器。
///
pub fn toString(self: Managed, allocator: Allocator, base: u8, case: std.fmt.Case) ![]u8 {
if (base < 2 or base > 36) return error.InvalidBase;
return self.toConst().toStringAlloc(allocator, base, case);
}
/// 使 `std.fmt.format` 能与 `Managed` 配合使用。
pub fn format(self: Managed, w: *std.Io.Writer) std.Io.Writer.Error!void {
return formatNumber(self, w, .{});
}
/// 若整数的绝对值大于或等于 `pow(2, 64 * @sizeOf(usize) * 8)`,
/// 此函数无法打印数值字符串,改为输出 "(BigInt)"。
/// 原因是渲染算法需要反转字符串,从而需要 O(N) 内存。
/// 不会因此失败的大整数打印方式参见 `toString` 和 `toStringAlloc`。
pub fn formatNumber(self: Managed, w: *std.Io.Writer, n: std.fmt.Number) std.Io.Writer.Error!void {
return self.toConst().formatNumber(w, n);
}
/// 当 |a| < |b|、|a| == |b| 或 |a| > |b| 时,
/// 分别返回 math.Order.lt、math.Order.eq 或 math.Order.gt。
pub fn orderAbs(a: Managed, b: Managed) math.Order {
return a.toConst().orderAbs(b.toConst());
}
/// 当 a < b、a == b 或 a > b 时,分别返回 math.Order.lt、math.Order.eq
/// 或 math.Order.gt。
pub fn order(a: Managed, b: Managed) math.Order {
return a.toConst().order(b.toConst());
}
/// 若 a == 0,返回 true。
pub fn eqlZero(a: Managed) bool {
return a.toConst().eqlZero();
}
/// 当 |a| == |b| 时返回 true。
pub fn eqlAbs(a: Managed, b: Managed) bool {
return a.toConst().eqlAbs(b.toConst());
}
/// a == b 时返回 true。
pub fn eql(a: Managed, b: Managed) bool {
return a.toConst().eql(b.toConst());
}
/// 规范化可能存在的前导零序列。
///
/// [1, 2, 3, 4, 0] -> [1, 2, 3, 4]
/// [1, 2, 0, 0, 0] -> [1, 2]
/// [0, 0, 0, 0, 0] -> [0]
pub fn normalize(r: *Managed, length: usize) void {
assert(length > 0);
assert(length <= r.limbs.len);
var j = length;
while (j > 0) : (j -= 1) {
if (r.limbs[j - 1] != 0) {
break;
}
}
// 处理零
r.setLen(if (j != 0) j else 1);
}
/// r = a + scalar
///
/// r 和 a 可以互为别名。
///
/// 无法分配内存时返回错误。
pub fn addScalar(r: *Managed, a: *const Managed, scalar: anytype) Allocator.Error!void {
const needed = @max(a.len(), calcLimbLen(scalar)) + 1;
const aliased = limbsAliasDistinct(r, a);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.addScalar(a.toConst(), scalar);
r.setMetadata(m.positive, m.len);
}
/// r = a + b
///
/// r、a 和 b 可以互为别名。
///
/// 无法分配内存时返回错误。
pub fn add(r: *Managed, a: *const Managed, b: *const Managed) Allocator.Error!void {
const needed = @max(a.len(), b.len()) + 1;
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.add(a.toConst(), b.toConst());
r.setMetadata(m.positive, m.len);
}
/// r = a + b,采用二进制补码回绕语义。返回是否发生任何溢出。
///
/// r、a 和 b 可以互为别名。
///
/// 若无法分配内存,则返回错误。
pub fn addWrap(
r: *Managed,
a: *const Managed,
b: *const Managed,
signedness: Signedness,
bit_count: usize,
) Allocator.Error!bool {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
const wrapped = m.addWrap(a.toConst(), b.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
return wrapped;
}
/// r = a + b,采用二进制补码饱和语义。
///
/// r、a 和 b 可以是别名。
///
/// 无法分配内存时返回错误。
pub fn addSat(r: *Managed, a: *const Managed, b: *const Managed, signedness: Signedness, bit_count: usize) Allocator.Error!void {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.addSat(a.toConst(), b.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// r = a - b
///
/// r、a 和 b 可以是别名。
///
/// 若无法分配内存则返回错误。
pub fn sub(r: *Managed, a: *const Managed, b: *const Managed) !void {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = @max(a.len(), b.len()) + 1;
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.sub(a.toConst(), b.toConst());
r.setMetadata(m.positive, m.len);
}
/// r = a - b,采用二进制补码回绕语义。返回是否发生溢出。
///
/// r、a 和 b 可以互为别名。
///
/// 若无法分配内存,则返回错误。
pub fn subWrap(
r: *Managed,
a: *const Managed,
b: *const Managed,
signedness: Signedness,
bit_count: usize,
) Allocator.Error!bool {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
const wrapped = m.subWrap(a.toConst(), b.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
return wrapped;
}
/// r = a - b,采用二进制补码饱和语义。
///
/// r、a 和 b 可以互为别名。
///
/// 若无法分配内存,则返回错误。
pub fn subSat(
r: *Managed,
a: *const Managed,
b: *const Managed,
signedness: Signedness,
bit_count: usize,
) Allocator.Error!void {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.subSat(a.toConst(), b.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// rma = a * b
///
/// rma、a 和 b 可以指向同一内存。不过,rma 不与 a 或 b 共用存储时效率更高。
///
/// 无法分配内存时返回错误。
///
/// rma 的分配器用于临时存储,以加速乘法。
pub fn mul(rma: *Managed, a: *const Managed, b: *const Managed) !void {
var alias_count: usize = 0;
if (rma.limbs.ptr == a.limbs.ptr)
alias_count += 1;
if (rma.limbs.ptr == b.limbs.ptr)
alias_count += 1;
const needed = a.len() + b.len() + 1;
const capacity_alias = limbsAliasDistinct(rma, a) or limbsAliasDistinct(rma, b);
try rma.ensureAliasAwareCapacity(needed, capacity_alias);
var m = rma.toMutable();
if (alias_count == 0) {
m.mulNoAlias(a.toConst(), b.toConst(), rma.allocator);
} else {
const limb_count = calcMulLimbsBufferLen(a.len(), b.len(), alias_count);
const limbs_buffer = try rma.allocator.alloc(Limb, limb_count);
defer rma.allocator.free(limbs_buffer);
m.mul(a.toConst(), b.toConst(), limbs_buffer, rma.allocator);
}
rma.setMetadata(m.positive, m.len);
}
/// rma = a * b,采用二进制补码回绕语义。
///
/// rma、a 和 b 可以互为别名,但若 rma 不与 a 或 b 互为别名,效率更高。
///
/// 无法分配内存时返回错误。
///
/// 使用 rma 的分配器提供临时存储,以加快乘法。
pub fn mulWrap(
rma: *Managed,
a: *const Managed,
b: *const Managed,
signedness: Signedness,
bit_count: usize,
) !void {
var alias_count: usize = 0;
if (rma.limbs.ptr == a.limbs.ptr)
alias_count += 1;
if (rma.limbs.ptr == b.limbs.ptr)
alias_count += 1;
const needed = calcTwosCompLimbCount(bit_count);
const capacity_alias = limbsAliasDistinct(rma, a) or limbsAliasDistinct(rma, b);
try rma.ensureAliasAwareCapacity(needed, capacity_alias);
var m = rma.toMutable();
if (alias_count == 0) {
m.mulWrapNoAlias(a.toConst(), b.toConst(), signedness, bit_count, rma.allocator);
} else {
const limb_count = calcMulWrapLimbsBufferLen(bit_count, a.len(), b.len(), alias_count);
const limbs_buffer = try rma.allocator.alloc(Limb, limb_count);
defer rma.allocator.free(limbs_buffer);
m.mulWrap(a.toConst(), b.toConst(), signedness, bit_count, limbs_buffer, rma.allocator);
}
rma.setMetadata(m.positive, m.len);
}
pub fn ensureTwosCompCapacity(r: *Managed, bit_count: usize) !void {
try r.ensureCapacity(calcTwosCompLimbCount(bit_count));
}
/// 若两个不同的 `Managed` 参数共享同一个 limb 缓冲区,则为 true。
///
/// 明确排除 `@intFromPtr(a) == @intFromPtr(b)` 的情况,即同一对象。
/// 若两个指针指向同一个 `Managed` 实例,`ensureCapacity` 可在需要时重新分配缓冲区,而不会为该对象创建悬空指针。
///
fn limbsAliasDistinct(a: *const Managed, b: *const Managed) bool {
return @intFromPtr(a) != @intFromPtr(b) and a.limbs.ptr == b.limbs.ptr;
}
/// 当 `aliased` 为 false 时,包括两个指针引用同一对象的情况,
/// `ensureCapacity` 可能重新分配。依赖不同 `Managed` 实例
/// 互为别名的调用方,必须先确保容量,再建立别名。
/// 参见 https://github.com/ziglang/zig/issues/6167
fn ensureAliasAwareCapacity(r: *Managed, needed: usize, aliased: bool) !void {
if (aliased) {
assert(needed <= r.limbs.len);
} else {
try r.ensureCapacity(needed);
}
}
/// 若部分参数彼此互为别名,请在执行 `addScalar` 前使用此函数
pub fn ensureAddScalarCapacity(r: *Managed, a: *const Managed, scalar: anytype) !void {
try r.ensureCapacity(@max(a.len(), calcLimbLen(scalar)) + 1);
}
/// 如果某些参数彼此构成别名,请在执行 `add` 之前使用此函数。
pub fn ensureAddCapacity(r: *Managed, a: *const Managed, b: *const Managed) !void {
try r.ensureCapacity(@max(a.len(), b.len()) + 1);
}
/// 若部分参数彼此互为别名,请在执行 `mul` 前使用此函数
pub fn ensureMulCapacity(rma: *Managed, a: *const Managed, b: *const Managed) !void {
try rma.ensureCapacity(a.len() + b.len() + 1);
}
/// q = a / b(余数 r)
///
/// a / b 向下取整(朝 0 方向)。
///
/// 无法分配内存时返回错误。
pub fn divFloor(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void {
const q_alias = limbsAliasDistinct(q, a) or limbsAliasDistinct(q, b);
const r_alias = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try q.ensureAliasAwareCapacity(a.len(), q_alias);
try r.ensureAliasAwareCapacity(b.len(), r_alias);
var mq = q.toMutable();
var mr = r.toMutable();
const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.len(), b.len()));
defer q.allocator.free(limbs_buffer);
mq.divFloor(&mr, a.toConst(), b.toConst(), limbs_buffer);
q.setMetadata(mq.positive, mq.len);
r.setMetadata(mr.positive, mr.len);
}
/// q = a / b(余数 r)
///
/// a / b 向上取整(朝正无穷方向)。
///
/// 无法分配内存时返回错误。
pub fn divCeil(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void {
const q_alias = limbsAliasDistinct(q, a) or limbsAliasDistinct(q, b);
const r_alias = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try q.ensureAliasAwareCapacity(a.len(), q_alias);
try r.ensureAliasAwareCapacity(b.len(), r_alias);
var mq = q.toMutable();
var mr = r.toMutable();
const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.len(), b.len()));
defer q.allocator.free(limbs_buffer);
mq.divCeil(&mr, a.toConst(), b.toConst(), limbs_buffer);
q.setMetadata(mq.positive, mq.len);
r.setMetadata(mr.positive, mr.len);
}
/// q = a / b(余数 r)
///
/// a / b 被截断(向负无穷舍入)。
///
/// 无法分配内存时返回错误。
pub fn divTrunc(q: *Managed, r: *Managed, a: *const Managed, b: *const Managed) !void {
const q_alias = limbsAliasDistinct(q, a) or limbsAliasDistinct(q, b);
const r_alias = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try q.ensureAliasAwareCapacity(a.len(), q_alias);
try r.ensureAliasAwareCapacity(b.len(), r_alias);
var mq = q.toMutable();
var mr = r.toMutable();
const limbs_buffer = try q.allocator.alloc(Limb, calcDivLimbsBufferLen(a.len(), b.len()));
defer q.allocator.free(limbs_buffer);
mq.divTrunc(&mr, a.toConst(), b.toConst(), limbs_buffer);
q.setMetadata(mq.positive, mq.len);
r.setMetadata(mr.positive, mr.len);
}
/// r = a << shift,即 r = a * 2^shift
/// r 和 a 可以互为别名。
pub fn shiftLeft(r: *Managed, a: *const Managed, shift: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = a.len() + (shift / limb_bits) + 1;
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.shiftLeft(a.toConst(), shift);
r.setMetadata(m.positive, m.len);
}
/// r = a <<| shift,采用二进制补码饱和语义。
/// r 和 a 可以互为别名。
pub fn shiftLeftSat(r: *Managed, a: *const Managed, shift: usize, signedness: Signedness, bit_count: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.shiftLeftSat(a.toConst(), shift, signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// r = a >> shift
/// r 和 a 可以互为别名。
pub fn shiftRight(r: *Managed, a: *const Managed, shift: usize) !void {
if (a.len() <= shift / limb_bits) {
// 对负数移位会收敛到 -1,而不是 0
if (a.isPositive()) {
r.metadata = 1;
r.limbs[0] = 0;
} else {
r.metadata = 1;
r.setSign(false);
r.limbs[0] = 1;
}
return;
}
const aliased = limbsAliasDistinct(r, a);
const needed = a.len() - (shift / limb_bits);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.shiftRight(a.toConst(), shift);
r.setMetadata(m.positive, m.len);
}
/// r = ~a,采用二进制补码回绕语义。
/// r 和 a 可以是别名。
pub fn bitNotWrap(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.bitNotWrap(a.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// r = a | b
///
/// a 和 b 均零扩展至两者中较长者的长度。
pub fn bitOr(r: *Managed, a: *const Managed, b: *const Managed) !void {
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
const needed = @max(a.len(), b.len());
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.bitOr(a.toConst(), b.toConst());
r.setMetadata(m.positive, m.len);
}
/// r = a & b
pub fn bitAnd(r: *Managed, a: *const Managed, b: *const Managed) !void {
const cap = if (a.len() >= b.len())
if (b.isPositive()) b.len() else if (a.isPositive()) a.len() else a.len() + 1
else if (a.isPositive()) a.len() else if (b.isPositive()) b.len() else b.len() + 1;
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try r.ensureAliasAwareCapacity(cap, aliased);
var m = r.toMutable();
m.bitAnd(a.toConst(), b.toConst());
r.setMetadata(m.positive, m.len);
}
/// r = a ^ b
pub fn bitXor(r: *Managed, a: *const Managed, b: *const Managed) !void {
const cap = @max(a.len(), b.len()) + @intFromBool(a.isPositive() != b.isPositive());
const aliased = limbsAliasDistinct(r, a) or limbsAliasDistinct(r, b);
try r.ensureAliasAwareCapacity(cap, aliased);
var m = r.toMutable();
m.bitXor(a.toConst(), b.toConst());
r.setMetadata(m.positive, m.len);
}
/// rma 可与 x 或 y 互为别名。
/// x 与 y 可以互为别名。
///
/// 使用 rma 的分配器提供临时存储,以提升乘法性能。
pub fn gcd(rma: *Managed, x: *const Managed, y: *const Managed) !void {
const aliased = limbsAliasDistinct(rma, x) or limbsAliasDistinct(rma, y);
const needed = @min(x.len(), y.len());
try rma.ensureAliasAwareCapacity(needed, aliased);
var m = rma.toMutable();
var limbs_buffer = std.array_list.Managed(Limb).init(rma.allocator);
defer limbs_buffer.deinit();
try m.gcd(x.toConst(), y.toConst(), &limbs_buffer);
rma.setMetadata(m.positive, m.len);
}
/// r = a * a
pub fn sqr(rma: *Managed, a: *const Managed) !void {
const needed_limbs = 2 * a.len() + 1;
const capacity_alias = limbsAliasDistinct(rma, a);
const same_buffer = rma.limbs.ptr == a.limbs.ptr;
try rma.ensureAliasAwareCapacity(needed_limbs, capacity_alias);
if (same_buffer) {
const a_len = a.len();
const tmp = try rma.allocator.alloc(Limb, a_len);
defer rma.allocator.free(tmp);
@memcpy(tmp[0..a_len], a.limbs[0..a_len]);
const a_const: Const = .{ .limbs = tmp[0..a_len], .positive = a.isPositive() };
var rma_mut = rma.toMutable();
rma_mut.sqrNoAlias(a_const, rma.allocator);
rma.setMetadata(rma_mut.positive, rma_mut.len);
} else {
var rma_mut = rma.toMutable();
rma_mut.sqrNoAlias(a.toConst(), rma.allocator);
rma.setMetadata(rma_mut.positive, rma_mut.len);
}
}
pub fn pow(rma: *Managed, a: *const Managed, b: u32) !void {
const needed_limbs = calcPowLimbsBufferLen(a.bitCountAbs(), b);
const capacity_alias = limbsAliasDistinct(rma, a);
const same_buffer = rma.limbs.ptr == a.limbs.ptr;
try rma.ensureAliasAwareCapacity(needed_limbs, capacity_alias);
const limbs_buffer = try rma.allocator.alloc(Limb, needed_limbs);
defer rma.allocator.free(limbs_buffer);
if (same_buffer) {
const a_len = a.len();
const tmp = try rma.allocator.alloc(Limb, a_len);
defer rma.allocator.free(tmp);
@memcpy(tmp[0..a_len], a.limbs[0..a_len]);
const a_const: Const = .{ .limbs = tmp[0..a_len], .positive = a.isPositive() };
var rma_mut = rma.toMutable();
rma_mut.pow(a_const, b, limbs_buffer);
rma.setMetadata(rma_mut.positive, rma_mut.len);
} else {
var rma_mut = rma.toMutable();
rma_mut.pow(a.toConst(), b, limbs_buffer);
rma.setMetadata(rma_mut.positive, rma_mut.len);
}
}
/// r = ⌊√a⌋
pub fn sqrt(rma: *Managed, a: *const Managed) !void {
const bit_count = a.bitCountAbs();
const aliased = limbsAliasDistinct(rma, a);
if (bit_count == 0) {
try rma.set(0);
rma.setMetadata(a.isPositive(), rma.len());
return;
}
if (!a.isPositive()) {
return error.SqrtOfNegativeNumber;
}
const needed_limbs = calcSqrtLimbsBufferLen(bit_count);
const limbs_buffer = try rma.allocator.alloc(Limb, needed_limbs);
defer rma.allocator.free(limbs_buffer);
const needed = (a.len() - 1) / 2 + 1;
try rma.ensureAliasAwareCapacity(needed, aliased);
var m = rma.toMutable();
m.sqrt(a.toConst(), limbs_buffer);
rma.setMetadata(m.positive, m.len);
}
/// r = truncate(Int(signedness, bit_count), a)
pub fn truncate(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.truncate(a.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// r = saturate(Int(signedness, bit_count), a)
pub fn saturate(r: *Managed, a: *const Managed, signedness: Signedness, bit_count: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.saturate(a.toConst(), signedness, bit_count);
r.setMetadata(m.positive, m.len);
}
/// r = @popCount(a),采用二进制补码语义。
/// r 和 a 可以是别名。
pub fn popCount(r: *Managed, a: *const Managed, bit_count: usize) !void {
const aliased = limbsAliasDistinct(r, a);
const needed = calcTwosCompLimbCount(bit_count);
try r.ensureAliasAwareCapacity(needed, aliased);
var m = r.toMutable();
m.popCount(a.toConst(), bit_count);
r.setMetadata(m.positive, m.len);
}
};
/// 累加式函数(llmulacc、llmulaccKaratsuba、llmulaccLong、llmulLimb)
/// 可使用的不同运算符。这些函数都会将
/// 计算值累加到现有结果中。
const AccOp = enum {
/// 将计算出的值加到结果中。
add,
/// 从结果中减去计算出的值。
sub,
};
/// Knuth 4.3.1,算法 M。
///
/// r = r (op) a * b
/// r 不得与 a 或 b 共用存储。
///
/// 结果按 `r.len` 取模计算。`r.len >= a.len + b.len` 时不会溢出。
fn llmulacc(comptime op: AccOp, opt_allocator: ?Allocator, r: []Limb, a: []const Limb, b: []const Limb) void {
assert(r.len >= a.len);
assert(r.len >= b.len);
assert(!slicesOverlap(r, a));
assert(!slicesOverlap(r, b));
// 按从大到小排序。
var x = a;
var y = b;
if (a.len < b.len) {
x = b;
y = a;
}
k_mul: {
if (y.len > 48) {
if (opt_allocator) |allocator| {
llmulaccKaratsuba(op, allocator, r, x, y) catch |err| switch (err) {
error.OutOfMemory => break :k_mul, // 在下方处理
};
return;
}
}
}
llmulaccLong(op, r, x, y);
}
/// Knuth 4.3.1,算法 M。
///
/// r = r (op) a * b
/// r 不得与 a 或 b 共用存储。
///
/// 结果按 `r.len` 取模计算。`r.len >= a.len + b.len` 时不会溢出。
fn llmulaccKaratsuba(
comptime op: AccOp,
allocator: Allocator,
r: []Limb,
a: []const Limb,
b: []const Limb,
) error{OutOfMemory}!void {
assert(r.len >= a.len);
assert(a.len >= b.len);
assert(!slicesOverlap(r, a));
assert(!slicesOverlap(r, b));
// 经典 Karatsuba 算法:
// a = a1 * B + a0
// b = b1 * B + b0
// 其中 a0, b0 < B
//
// 于是有:
// ab = a * b
// = (a1 * B + a0) * (b1 * B + b0)
// = a1 * b1 * B * B + a1 * B * b0 + a0 * b1 * B + a0 * b0
// = a1 * b1 * B * B + (a1 * b0 + a0 * b1) * B + a0 * b0
//
// 注意:
// a1 * b0 + a0 * b1
// = (a1 + a0)(b1 + b0) - a1 * b1 - a0 * b0
// = (a0 - a1)(b1 - b0) + a1 * b1 + a0 * b0
//
// 由此得到:
// ab = p2 * B^2 + (p0 + p1 + p2) * B + p0
//
// 其中:
// p0 = a0 * b0
// p1 = (a0 - a1)(b1 - b0)
// p2 = a1 * b1
//
// 注意,(a0 - a1) 和 (b1 - b0) 的取值满足 -B < x < B,因此必须注意这里的符号。
// 还可得:
// 0 <= p0 <= 2B
// -2B <= p1 <= 2B
//
// 注意,当 B 是字长度的整数倍时,乘以 B 相当于移位,或对字数组进行切片。
//
// 此函数计算乘法结果对 r.len 取模后的值。这意味着:
// - p2 和 p1 只需对 r.len - B 取模后计算。
// - 对于 p2,p2 * B^2 需要对 r.len - 2 * B 取模后再相加。
//
const split = b.len / 2; // B
const limbs_after_split = r.len - split; // 为 p1 和 p2 计算的大整数 limb。
const limbs_after_split2 = r.len - split * 2; // 为 p2 * B^2 添加的 limb。
// a0 和 b0 需要完整取值范围。
const a0 = a[0..llnormalize(a[0..split])];
const b0 = b[0..llnormalize(b[0..split])];
// 对于 a1 和 b1,只需要 `limbs_after_split` 个字。
const a1 = blk: {
var a1 = a[split..];
a1.len = @min(llnormalize(a1), limbs_after_split);
break :blk a1;
};
const b1 = blk: {
var b1 = b[split..];
b1.len = @min(llnormalize(b1), limbs_after_split);
break :blk b1;
};
// 注意,上方相对于 `split` 的切片有效,是因为 a.len > b.len。
// 需要临时内存存储中间结果。
// 注意,可通过重排计算来减少所需临时变量:
// ab = p2 * B^2 + (p0 + p1 + p2) * B + p0
// = p2 * B^2 + (p0 * B + p1 * B + p2 * B) + p0
// = (p2 * B^2 + p2 * B) + (p0 * B + p0) + p1 * B
// 假定无溢出,分配的内存至少足以
// 将 a 和 b 的高两个分段相乘。
const tmp = try allocator.alloc(Limb, a.len - split + b.len - split);
defer allocator.free(tmp);
// 计算 p2。
// 注意,不必计算完整 p2,只需计算满足 r 所需的足够字数。
const p2_limbs = @min(limbs_after_split, a1.len + b1.len);
@memset(tmp[0..p2_limbs], 0);
llmulacc(.add, allocator, tmp[0..p2_limbs], a1[0..@min(a1.len, p2_limbs)], b1[0..@min(b1.len, p2_limbs)]);
const p2 = tmp[0..llnormalize(tmp[0..p2_limbs])];
// 将 p2 * B 加到结果。
llaccum(op, r[split..], p2);
// 需要时将 p2 * B^2 加入结果。
if (limbs_after_split2 > 0) {
llaccum(op, r[split * 2 ..], p2[0..@min(p2.len, limbs_after_split2)]);
}
// 计算 p0。
// 由于 a0.len, b0.len <= split 且 r.len >= split * 2,需要计算完整位宽的 p0。
const p0_limbs = a0.len + b0.len;
@memset(tmp[0..p0_limbs], 0);
llmulacc(.add, allocator, tmp[0..p0_limbs], a0, b0);
const p0 = tmp[0..llnormalize(tmp[0..p0_limbs])];
// 将 p0 加到结果。
llaccum(op, r, p0);
// 将 p0 * B 加到结果中。此情况下可能无需全部值。
llaccum(op, r[split..], p0[0..@min(limbs_after_split, p0.len)]);
// 最后,计算并添加 p1。
// 从现在起,a0 和 b0 只需使用 `limbs_after_split` 个 limb,
// 因为后续计算结果将乘以 B 后再加上。
const a0x = a0[0..@min(a0.len, limbs_after_split)];
const b0x = b0[0..@min(b0.len, limbs_after_split)];
const j0_sign = llcmp(a0x, a1);
const j1_sign = llcmp(b1, b0x);
if (j0_sign * j1_sign == 0) {
// p1 为零,无需进行任何计算。
return;
}
@memset(tmp, 0);
// p1 非零,因此计算中间项 j0 = a0 - a1 和 j1 = b1 - b0。
// 注意,此情况仍需存储中间结果
// j0 和 j1。由于 tmp.len >= 2B,可以将两个
// 中间结果都存入已分配的数组。
const j0 = tmp[0 .. a.len - split];
const j1 = tmp[a.len - split ..];
// 确保没有减法溢出。
if (j0_sign == 1) {
// a0 > a1.
_ = llsubcarry(j0, a0x, a1);
} else {
// a0 < a1.
_ = llsubcarry(j0, a1, a0x);
}
if (j1_sign == 1) {
// b1 > b0.
_ = llsubcarry(j1, b1, b0x);
} else {
// b1 > b0.
_ = llsubcarry(j1, b0x, b1);
}
if (j0_sign * j1_sign == 1) {
// 若 j0 和 j1 均为正,则有:
// p1 = j0 * j1
// 若 j0 和 j1 均为负,则有:
// p1 = -j0 * -j1 = j0 * j1
// 此时可使用 llmulacc 将 p1 加到结果。
llmulacc(op, allocator, r[split..], j0[0..llnormalize(j0)], j1[0..llnormalize(j1)]);
} else {
// 此时 j0 或 j1 为负,有:
// p1 = -(j0 * j1)
// 因此现在需要相减,而非累加。
const inverted_op = if (op == .add) .sub else .add;
llmulacc(inverted_op, allocator, r[split..], j0[0..llnormalize(j0)], j1[0..llnormalize(j1)]);
}
}
/// r = r (op) a。
/// 结果按 `r.len` 取模计算。
fn llaccum(comptime op: AccOp, r: []Limb, a: []const Limb) void {
assert(!slicesOverlap(r, a) or @intFromPtr(r.ptr) <= @intFromPtr(a.ptr));
if (op == .sub) {
_ = llsubcarry(r, r, a);
return;
}
assert(r.len != 0 and a.len != 0);
assert(r.len >= a.len);
var i: usize = 0;
var carry: Limb = 0;
while (i < a.len) : (i += 1) {
const ov1 = @addWithOverflow(r[i], a[i]);
r[i] = ov1[0];
const ov2 = @addWithOverflow(r[i], carry);
r[i] = ov2[0];
carry = @as(Limb, ov1[1]) + ov2[1];
}
while ((carry != 0) and i < r.len) : (i += 1) {
const ov = @addWithOverflow(r[i], carry);
r[i] = ov[0];
carry = ov[1];
}
}
/// 对于字,当 |a| < |b|、|a| == |b|、|a| > |b| 时分别返回 -1、0、1。
pub fn llcmp(a: []const Limb, b: []const Limb) i8 {
const a_len = llnormalize(a);
const b_len = llnormalize(b);
if (a_len < b_len) {
return -1;
}
if (a_len > b_len) {
return 1;
}
var i: usize = a_len - 1;
while (i != 0) : (i -= 1) {
if (a[i] != b[i]) {
break;
}
}
if (a[i] < b[i]) {
return -1;
} else if (a[i] > b[i]) {
return 1;
} else {
return 0;
}
}
/// r = r (op) y * xi
/// 结果按 `r.len` 取模。当 `r.len >= a.len + b.len` 时不会溢出。
fn llmulaccLong(comptime op: AccOp, r: []Limb, a: []const Limb, b: []const Limb) void {
assert(r.len >= a.len);
assert(a.len >= b.len);
var i: usize = 0;
while (i < b.len) : (i += 1) {
_ = llmulLimb(op, r[i..], a, b[i]);
}
}
/// r = r (op) y * xi
/// 结果按 `r.len` 对应的模计算。
/// 返回操作是否溢出。
fn llmulLimb(comptime op: AccOp, acc: []Limb, y: []const Limb, xi: Limb) bool {
assert(!slicesOverlap(acc, y) or @intFromPtr(acc.ptr) <= @intFromPtr(y.ptr));
if (xi == 0) {
return false;
}
const split = @min(y.len, acc.len);
var a_lo = acc[0..split];
var a_hi = acc[split..];
switch (op) {
.add => {
var carry: Limb = 0;
var j: usize = 0;
while (j < a_lo.len) : (j += 1) {
a_lo[j] = addMulLimbWithCarry(a_lo[j], y[j], xi, &carry);
}
j = 0;
while ((carry != 0) and (j < a_hi.len)) : (j += 1) {
const ov = @addWithOverflow(a_hi[j], carry);
a_hi[j] = ov[0];
carry = ov[1];
}
return carry != 0;
},
.sub => {
var borrow: Limb = 0;
var j: usize = 0;
while (j < a_lo.len) : (j += 1) {
a_lo[j] = subMulLimbWithBorrow(a_lo[j], y[j], xi, &borrow);
}
j = 0;
while ((borrow != 0) and (j < a_hi.len)) : (j += 1) {
const ov = @subWithOverflow(a_hi[j], borrow);
a_hi[j] = ov[0];
borrow = ov[1];
}
return borrow != 0;
},
}
}
/// 返回 limb 可能具有的最小长度。
fn llnormalize(a: []const Limb) usize {
var j = a.len;
while (j > 0) : (j -= 1) {
if (a[j - 1] != 0) {
break;
}
}
// 处理零
return if (j != 0) j else 1;
}
/// Knuth 4.3.1,算法 S。
fn llsubcarry(r: []Limb, a: []const Limb, b: []const Limb) Limb {
assert(a.len != 0 and b.len != 0);
assert(a.len >= b.len);
assert(r.len >= a.len);
assert(!slicesOverlap(r, a) or @intFromPtr(r.ptr) <= @intFromPtr(a.ptr));
assert(!slicesOverlap(r, b) or @intFromPtr(r.ptr) <= @intFromPtr(b.ptr));
var i: usize = 0;
var borrow: Limb = 0;
while (i < b.len) : (i += 1) {
const ov1 = @subWithOverflow(a[i], b[i]);
r[i] = ov1[0];
const ov2 = @subWithOverflow(r[i], borrow);
r[i] = ov2[0];
borrow = @as(Limb, ov1[1]) + ov2[1];
}
while (i < a.len) : (i += 1) {
const ov = @subWithOverflow(a[i], borrow);
r[i] = ov[0];
borrow = ov[1];
}
return borrow;
}
fn llsub(r: []Limb, a: []const Limb, b: []const Limb) void {
assert(a.len > b.len or (a.len == b.len and a[a.len - 1] >= b[b.len - 1]));
assert(llsubcarry(r, a, b) == 0);
}
/// Knuth 4.3.1,算法 A。
fn lladdcarry(r: []Limb, a: []const Limb, b: []const Limb) Limb {
assert(a.len != 0 and b.len != 0);
assert(a.len >= b.len);
assert(r.len >= a.len);
assert(!slicesOverlap(r, a) or @intFromPtr(r.ptr) <= @intFromPtr(a.ptr));
assert(!slicesOverlap(r, b) or @intFromPtr(r.ptr) <= @intFromPtr(b.ptr));
var i: usize = 0;
var carry: Limb = 0;
while (i < b.len) : (i += 1) {
const ov1 = @addWithOverflow(a[i], b[i]);
r[i] = ov1[0];
const ov2 = @addWithOverflow(r[i], carry);
r[i] = ov2[0];
carry = @as(Limb, ov1[1]) + ov2[1];
}
while (i < a.len) : (i += 1) {
const ov = @addWithOverflow(a[i], carry);
r[i] = ov[0];
carry = ov[1];
}
return carry;
}
fn lladd(r: []Limb, a: []const Limb, b: []const Limb) void {
assert(r.len >= a.len + 1);
r[a.len] = lladdcarry(r, a, b);
}
/// Knuth 4.3.1,习题 16。
fn lldiv1(quo: []Limb, rem: *Limb, a: []const Limb, b: Limb) void {
assert(a.len > 1 or a[0] >= b);
assert(quo.len >= a.len);
rem.* = 0;
for (a, 0..) |_, ri| {
const i = a.len - ri - 1;
const pdiv = ((@as(DoubleLimb, rem.*) << limb_bits) | a[i]);
if (pdiv == 0) {
quo[i] = 0;
rem.* = 0;
} else if (pdiv < b) {
quo[i] = 0;
rem.* = @as(Limb, @truncate(pdiv));
} else if (pdiv == b) {
quo[i] = 1;
rem.* = 0;
} else {
quo[i] = @as(Limb, @truncate(@divTrunc(pdiv, b)));
rem.* = @as(Limb, @truncate(pdiv - (quo[i] *% b)));
}
}
}
fn lldiv0p5(quo: []Limb, rem: *Limb, a: []const Limb, b: HalfLimb) void {
assert(a.len > 1 or a[0] >= b);
assert(quo.len >= a.len);
rem.* = 0;
for (a, 0..) |_, ri| {
const i = a.len - ri - 1;
const ai_high = a[i] >> half_limb_bits;
const ai_low = a[i] & ((1 << half_limb_bits) - 1);
// 将除法拆为两次除法,每次处理半个 limb。传递余数。
const ai_high_with_carry = (rem.* << half_limb_bits) | ai_high;
const ai_high_quo = ai_high_with_carry / b;
rem.* = ai_high_with_carry % b;
const ai_low_with_carry = (rem.* << half_limb_bits) | ai_low;
const ai_low_quo = ai_low_with_carry / b;
rem.* = ai_low_with_carry % b;
quo[i] = (ai_high_quo << half_limb_bits) | ai_low_quo;
}
}
/// 执行 r = a << shift,并返回受影响的 limb 数。
///
/// 若 a 与 r 重叠,则断言 r.ptr >= a.ptr。
/// r 必须有足够容量存储 a << shift。
fn llshl(r: []Limb, a: []const Limb, shift: usize) usize {
std.debug.assert(a.len >= 1);
if (slicesOverlap(a, r))
std.debug.assert(@intFromPtr(r.ptr) >= @intFromPtr(a.ptr));
if (shift == 0) {
if (a.ptr != r.ptr) @memmove(r[0..a.len], a);
return a.len;
}
if (shift >= limb_bits) {
const limb_shift = shift / limb_bits;
const affected = llshl(r[limb_shift..], a, shift % limb_bits);
@memset(r[0..limb_shift], 0);
return limb_shift + affected;
}
// 保证 shift < limb_bits
const bit_shift: Log2Limb = @truncate(shift);
const opposite_bit_shift: Log2Limb = @truncate(limb_bits - bit_shift);
// 仅当最后一个元素的移位发生溢出时才需要额外的字。
// 这有助于实现 `shiftLeftSat`。
const overflows = a[a.len - 1] >> opposite_bit_shift != 0;
if (overflows) {
std.debug.assert(r.len >= a.len + 1);
} else {
std.debug.assert(r.len >= a.len);
}
var i: usize = a.len;
if (overflows) {
// 上方已断言 r 足够大
r[a.len] = a[a.len - 1] >> opposite_bit_shift;
}
while (i > 1) {
i -= 1;
r[i] = (a[i - 1] >> opposite_bit_shift) | (a[i] << bit_shift);
}
r[0] = a[0] << bit_shift;
return a.len + @intFromBool(overflows);
}
/// 执行 r = a >> shift,返回受影响的 limb 数。
///
/// 若 a 与 r 重叠,则断言 r.ptr <= a.ptr。
/// r 必须有足够容量存储 a >> shift。
///
/// 行为示例参见下方测试。
fn llshr(r: []Limb, a: []const Limb, shift: usize) usize {
if (slicesOverlap(a, r))
std.debug.assert(@intFromPtr(r.ptr) <= @intFromPtr(a.ptr));
if (a.len == 0) return 0;
if (shift == 0) {
std.debug.assert(r.len >= a.len);
if (a.ptr != r.ptr) @memmove(r[0..a.len], a);
return a.len;
}
if (shift >= limb_bits) {
if (shift / limb_bits >= a.len) {
r[0] = 0;
return 1;
}
return llshr(r, a[shift / limb_bits ..], shift % limb_bits);
}
// 保证 shift < limb_bits
const bit_shift: Log2Limb = @truncate(shift);
const opposite_bit_shift: Log2Limb = @truncate(limb_bits - bit_shift);
// 存在将 r 设置为 0 风险的特殊情况。
if (a.len == 1) {
r[0] = a[0] >> bit_shift;
return 1;
}
if (a.len == 0) {
r[0] = 0;
return 1;
}
// 如果移位后最高有效字变为 0
const shrink = a[a.len - 1] >> bit_shift == 0;
std.debug.assert(r.len >= a.len - @intFromBool(shrink));
var i: usize = 0;
while (i < a.len - 1) : (i += 1) {
r[i] = (a[i] >> bit_shift) | (a[i + 1] << opposite_bit_shift);
}
if (!shrink)
r[i] = a[i] >> bit_shift;
return a.len - @intFromBool(shrink);
}
// r = ~r
fn llnot(r: []Limb) void {
for (r) |*elem| {
elem.* = ~elem.*;
}
}
// 按二进制补码语义计算 r = a | b。
// r 可以与操作数互为别名。
// a 和 b 均不得为 0。
// 结果为正时返回 `true`。
// b 为正时,r 至少需要 `a.len` 个 limb 的存储空间。
// b 为负时,r 至少需要 `b.len` 个 limb 的存储空间。
fn llsignedor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_positive: bool) bool {
assert(r.len >= a.len);
assert(a.len >= b.len);
if (a_positive and b_positive) {
// 简单情况,结果为正。
var i: usize = 0;
while (i < b.len) : (i += 1) {
r[i] = a[i] | b[i];
}
while (i < a.len) : (i += 1) {
r[i] = a[i];
}
return true;
} else if (!a_positive and b_positive) {
// 结果为负。
// r = (--a) | b
// = ~(-a - 1) | b
// = ~(-a - 1) | ~~b
// = ~((-a - 1) & ~b)
// = -(((-a - 1) & ~b) + 1)
var i: usize = 0;
var a_borrow: u1 = 1;
var r_carry: u1 = 1;
while (i < b.len) : (i += 1) {
const ov1 = @subWithOverflow(a[i], a_borrow);
a_borrow = ov1[1];
const ov2 = @addWithOverflow(ov1[0] & ~b[i], r_carry);
r[i] = ov2[0];
r_carry = ov2[1];
}
// 要使此时 r_carry 非零,~b[i] 必须全为一,这要求 b[i] 为零。
// b 已规范化时不可能如此,因此此处不可能有进位。
// 另外,x & ~b 只能清除位,因此 (x & ~b) <= x,意味着 (-a - 1) + 1 绝不会溢出。
//
assert(r_carry == 0);
// 当 b = 0 时,得到 (-a - 1) & ~0 = -a - 1。
// 注意,若 a_borrow 为零,则不必计算高位字,因此可在此提前返回。
//
while (i < a.len and a_borrow == 1) : (i += 1) {
const ov = @subWithOverflow(a[i], a_borrow);
r[i] = ov[0];
a_borrow = ov[1];
}
assert(a_borrow == 0); // a 原值为 0。
return false;
} else if (a_positive and !b_positive) {
// 结果为负。
// r = a | (--b)
// = a | ~(-b - 1)
// = ~~a | ~(-b - 1)
// = ~(~a & (-b - 1))
// = -((~a & (-b - 1)) + 1)
var i: usize = 0;
var b_borrow: u1 = 1;
var r_carry: u1 = 1;
while (i < b.len) : (i += 1) {
const ov1 = @subWithOverflow(b[i], b_borrow);
b_borrow = ov1[1];
const ov2 = @addWithOverflow(~a[i] & ov1[0], r_carry);
r[i] = ov2[0];
r_carry = ov2[1];
}
// b 至少为 1,因此绝不应下溢。
assert(b_borrow == 0); // b 原值为 0
// x & ~a 只能清除位,因此 (x & ~a) <= x;也就是说,(-b - 1) + 1 永不溢出。
assert(r_carry == 0);
// b = 0 且 b_borrow = 0 时,得到 ~a & (0 - 0) = ~a & 0 = 0。
// 省略设置高位字节,仅在调用 llsignedor 时处理它们。
return false;
} else {
// 结果为负。
// r = (--a) | (--b)
// = ~(-a - 1) | ~(-b - 1)
// = ~((-a - 1) & (-b - 1))
// = -(~(~((-a - 1) & (-b - 1))) + 1)
// = -((-a - 1) & (-b - 1) + 1)
var i: usize = 0;
var a_borrow: u1 = 1;
var b_borrow: u1 = 1;
var r_carry: u1 = 1;
while (i < b.len) : (i += 1) {
const ov1 = @subWithOverflow(a[i], a_borrow);
a_borrow = ov1[1];
const ov2 = @subWithOverflow(b[i], b_borrow);
b_borrow = ov2[1];
const ov3 = @addWithOverflow(ov1[0] & ov2[0], r_carry);
r[i] = ov3[0];
r_carry = ov3[1];
}
// b 至少为 1,因此绝不应下溢。
assert(b_borrow == 0); // b 原值为 0
// 绝不会溢出,因为要使 b_limb 为 maxInt(Limb),
// b_borrow 必须为 1。
// x & y 只能清除位,即 x & y <= x 且 x & y <= y。这意味着
// 当 x = a - 1 且 y = b - 1 时,+1 项绝不会导致溢出。
assert(r_carry == 0);
// 当 b = 0 且 b_borrow = 0 时,(-a - 1) & (0 - 0) = (-a - 1) & 0 = 0。
// 省略高位字节的设置,仅在调用 llsignedor 时处理它们。
return false;
}
}
// 按二进制补码语义计算 r = a & b。
// r 可以与操作数互为别名。
// a 和 b 均不得为 0。
// 结果为正时返回 `true`。
// 此处假定 `a.len >= b.len`,因此:
// 1. 当 b 为正时,r 至少需要 `b.len` 个 limb 的存储空间;
// 2. 当 b 为负而 a 为正时,r 至少需要 `a.len` 个 limb 的存储空间;
// 3. 当 a 和 b 均为负时,r 至少需要 `a.len + 1` 个 limb 的存储空间。
fn llsignedand(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_positive: bool) bool {
assert(a.len != 0 and b.len != 0);
assert(a.len >= b.len);
assert(r.len >= if (b_positive) b.len else if (a_positive) a.len else a.len + 1);
if (a_positive and b_positive) {
// 简单情况,结果为正。
var i: usize = 0;
while (i < b.len) : (i += 1) {
r[i] = a[i] & b[i];
}
// b = 0 时,a & 0 = 0,因此高位字节为零。
// 此处省略设置它们,
// 在调用 llsignedand 时直接丢弃。
return true;
} else if (!a_positive and b_positive) {
// 结果为正。
// r = (--a) & b
// = ~(-a - 1) & b
var i: usize = 0;
var a_borrow: u1 = 1;
while (i < b.len) : (i += 1) {
const ov = @subWithOverflow(a[i], a_borrow);
a_borrow = ov[1];
r[i] = ~ov[0] & b[i];
}
// 当 b = 0 时,~(a - 1) & 0 = 0,因此高位字节为零。
// 此处省略其设置,在调用 llsignedand 时
// 直接丢弃它们。
return true;
} else if (a_positive and !b_positive) {
// 结果为正。
// r = a & (--b)
// = a & ~(-b - 1)
var i: usize = 0;
var b_borrow: u1 = 1;
while (i < b.len) : (i += 1) {
const ov = @subWithOverflow(b[i], b_borrow);
b_borrow = ov[1];
r[i] = a[i] & ~ov[0];
}
assert(b_borrow == 0); // b 原值为 0
// 当 b = 0 且 b_borrow = 0 时,a & ~(0 - 0) = a & ~0 = a,
// 因此高位字节与 a 的对应字节相同。
while (i < a.len) : (i += 1) {
r[i] = a[i];
}
return true;
} else {
// 结果为负。
// r = (--a) & (--b)
// = ~(-a - 1) & ~(-b - 1)
// = ~((-a - 1) | (-b - 1))
// = -(((-a - 1) | (-b - 1)) + 1)
var i: usize = 0;
var a_borrow: u1 = 1;
var b_borrow: u1 = 1;
var r_carry: u1 = 1;
while (i < b.len) : (i += 1) {
const ov1 = @subWithOverflow(a[i], a_borrow);
a_borrow = ov1[1];
const ov2 = @subWithOverflow(b[i], b_borrow);
b_borrow = ov2[1];
const ov3 = @addWithOverflow(ov1[0] | ov2[0], r_carry);
r[i] = ov3[0];
r_carry = ov3[1];
}
// b 至少为 1,因此绝不应下溢。
assert(b_borrow == 0); // b 原值为 0
// 当 b = 0 且 b_borrow = 0 时,有 (-a - 1) | (0 - 0) = (-a - 1) | 0 = -a - 1。
while (i < a.len) : (i += 1) {
const ov1 = @subWithOverflow(a[i], a_borrow);
a_borrow = ov1[1];
const ov2 = @addWithOverflow(ov1[0], r_carry);
r[i] = ov2[0];
r_carry = ov2[1];
}
assert(a_borrow == 0); // a 原值为 0。
// 此处最后一次加法可能溢出,因此必须考虑这一点。
r[i] = r_carry;
return false;
}
}
// r = a ^ b,采用二进制补码语义。
// r 可以与输入互为别名。
// a 和 b 不得为 -0。
// 结果为正时返回 `true`。
// a 和 b 符号相同时,r 至少需要 `@max(a.len, b.len)` 个 limb。
// 否则,r 至少需要 `@max(a.len, b.len) + 1` 个 limb。
fn llsignedxor(r: []Limb, a: []const Limb, a_positive: bool, b: []const Limb, b_positive: bool) bool {
assert(a.len != 0 and b.len != 0);
assert(r.len >= a.len);
assert(a.len >= b.len);
// 若 a 和 b 均为正,结果为正,且 r = a ^ b。
// 若 a 为负、b 为正,则结果为负,并有:
// r = --(--a ^ b)
// = --(~(-a - 1) ^ b)
// = -(~(~(-a - 1) ^ b) + 1)
// = -(((-a - 1) ^ b) + 1)
// a 为正、b 为负时同理,只需交换两侧。
// 若 a 和 b 均为负,结果为正,并有:
// r = (--a) ^ (--b)
// = ~(-a - 1) ^ ~(-b - 1)
// = (-a - 1) ^ (-b - 1)
// 这些操作可归纳如下:
// - 若 a 为负,在异或前将 |a| 减 1。
// - 若 b 为负,在异或前将 |b| 减 1。
// - 若结果应为负,将结果加 1。
var i: usize = 0;
var a_borrow = @intFromBool(!a_positive);
var b_borrow = @intFromBool(!b_positive);
var r_carry = @intFromBool(a_positive != b_positive);
while (i < b.len) : (i += 1) {
const ov1 = @subWithOverflow(a[i], a_borrow);
a_borrow = ov1[1];
const ov2 = @subWithOverflow(b[i], b_borrow);
b_borrow = ov2[1];
const ov3 = @addWithOverflow(ov1[0] ^ ov2[0], r_carry);
r[i] = ov3[0];
r_carry = ov3[1];
}
while (i < a.len) : (i += 1) {
const ov1 = @subWithOverflow(a[i], a_borrow);
a_borrow = ov1[1];
const ov2 = @addWithOverflow(ov1[0], r_carry);
r[i] = ov2[0];
r_carry = ov2[1];
}
// 若两个输入的符号不同,则需要一个额外的字。
if (a_positive != b_positive) {
r[i] = r_carry;
} else {
assert(r_carry == 0);
}
assert(a_borrow == 0);
assert(b_borrow == 0);
return a_positive == b_positive;
}
/// r 不得与 x 存在别名关系。
fn llsquareBasecase(r: []Limb, x: []const Limb) void {
const x_norm = x;
assert(r.len >= 2 * x_norm.len + 1);
assert(!slicesOverlap(r, x));
// 利用系数关于对角线的对称性,仅用 (N^2 + N)/2 次乘法计算 N 个 limb 的大整数的平方:
//
// a b c *
// a b c =
// -------------------
// ca cb cc +
// ba bb bc +
// aa ab ac
//
// 注意:
// - 每列中每个交叉乘积项都出现两次。
// - 平方项始终位于第 2k 列,0 <= k < N。
//
//
for (x_norm, 0..) |v, i| {
// 累加所有 x[i]*x[j](其中 x!=j)乘积
const overflow = llmulLimb(.add, r[2 * i + 1 ..], x_norm[i + 1 ..], v);
assert(!overflow);
}
// 每个乘积出现两次,因此乘以 2
_ = llshl(r, r[0 .. 2 * x_norm.len], 1);
for (x_norm, 0..) |v, i| {
// 计算各平方并求和
const overflow = llmulLimb(.add, r[2 * i ..], x[i..][0..1], v);
assert(!overflow);
}
}
/// Knuth 4.6.3
fn llpow(r: []Limb, a: []const Limb, b: u32, tmp_limbs: []Limb) void {
var tmp1: []Limb = undefined;
var tmp2: []Limb = undefined;
// 乘法要求操作数与结果变量不能互为别名,
// 使用输出 limb 和另一组临时 limb 可克服此
// 限制。
// 初始赋值使结果最终落在 `r` 中,省去一次额外内存
// 复制;每个 1 都会使索引翻转两次,因此只有零
// 会影响最终位置。
const b_leading_zeros = @clz(b);
const exp_zeros = @popCount(~b) - b_leading_zeros;
if (exp_zeros & 1 != 0) {
tmp1 = tmp_limbs;
tmp2 = r;
} else {
tmp1 = r;
tmp2 = tmp_limbs;
}
@memcpy(tmp1[0..a.len], a);
@memset(tmp1[a.len..], 0);
// 将指数视为二进制数,从左到右扫描,
// 跳过最高的置位位。
// 若当前位为零,则将结果平方;若为一,
// 则将结果平方后乘以 a。
const exp_bits = 32 - 1 - b_leading_zeros;
var exp = b << @as(u5, @intCast(1 + b_leading_zeros));
var i: usize = 0;
while (i < exp_bits) : (i += 1) {
// 平方
@memset(tmp2, 0);
llsquareBasecase(tmp2, tmp1[0..llnormalize(tmp1)]);
mem.swap([]Limb, &tmp1, &tmp2);
// 乘以 a
const ov = @shlWithOverflow(exp, 1);
exp = ov[0];
if (ov[1] != 0) {
@memset(tmp2, 0);
llmulacc(.add, null, tmp2, tmp1[0..llnormalize(tmp1)], a);
mem.swap([]Limb, &tmp1, &tmp2);
}
}
}
// 存储必须在返回值的整个生存期内有效
fn fixedIntFromSignedDoubleLimb(A: SignedDoubleLimb, storage: []Limb) Mutable {
assert(storage.len >= 2);
const A_is_positive = A >= 0;
const Au = @as(DoubleLimb, @intCast(if (A < 0) -A else A));
storage[0] = @as(Limb, @truncate(Au));
storage[1] = @as(Limb, @truncate(Au >> limb_bits));
return .{
.limbs = storage[0..2],
.positive = A_is_positive,
.len = 2,
};
}
fn slicesOverlap(a: []const Limb, b: []const Limb) bool {
// 如果 a.ptr + a.len <= b.ptr 或 b.ptr + b.len <= a.ptr,则不存在重叠。
return @intFromPtr(a.ptr + a.len) > @intFromPtr(b.ptr) and @intFromPtr(b.ptr + b.len) > @intFromPtr(a.ptr);
}
test {
_ = @import("int_test.zig");
}
const testing_allocator = std.testing.allocator;
test "llshl shift by whole number of limb" {
const padding = maxInt(Limb);
var r: [10]Limb = @splat(padding);
const A: Limb = @truncate(0xCCCCCCCCCCCCCCCCCCCCCCC);
const B: Limb = @truncate(0x22222222222222222222222);
const data = [2]Limb{ A, B };
for (0..9) |i| {
@memset(&r, padding);
const len = llshl(&r, &data, i * @bitSizeOf(Limb));
try std.testing.expectEqual(i + 2, len);
try std.testing.expectEqualSlices(Limb, &data, r[i .. i + 2]);
for (r[0..i]) |x|
try std.testing.expectEqual(0, x);
for (r[i + 2 ..]) |x|
try std.testing.expectEqual(padding, x);
}
}
test llshl {
if (limb_bits != 64) return error.SkipZigTest;
// 1 << 63
const left_one = 0x8000000000000000;
const maxint: Limb = 0xFFFFFFFFFFFFFFFF;
// zig fmt: off
try testOneShiftCase(.llshl, .{0, &.{0}, &.{0}});
try testOneShiftCase(.llshl, .{0, &.{1}, &.{1}});
try testOneShiftCase(.llshl, .{0, &.{125484842448}, &.{125484842448}});
try testOneShiftCase(.llshl, .{0, &.{0xdeadbeef}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{0, &.{maxint}, &.{maxint}});
try testOneShiftCase(.llshl, .{0, &.{left_one}, &.{left_one}});
try testOneShiftCase(.llshl, .{0, &.{0, 1}, &.{0, 1}});
try testOneShiftCase(.llshl, .{0, &.{1, 2}, &.{1, 2}});
try testOneShiftCase(.llshl, .{0, &.{left_one, 1}, &.{left_one, 1}});
try testOneShiftCase(.llshl, .{1, &.{0}, &.{0}});
try testOneShiftCase(.llshl, .{1, &.{2}, &.{1}});
try testOneShiftCase(.llshl, .{1, &.{250969684896}, &.{125484842448}});
try testOneShiftCase(.llshl, .{1, &.{0x1bd5b7dde}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{1, &.{0xfffffffffffffffe, 1}, &.{maxint}});
try testOneShiftCase(.llshl, .{1, &.{0, 1}, &.{left_one}});
try testOneShiftCase(.llshl, .{1, &.{0, 2}, &.{0, 1}});
try testOneShiftCase(.llshl, .{1, &.{2, 4}, &.{1, 2}});
try testOneShiftCase(.llshl, .{1, &.{0, 3}, &.{left_one, 1}});
try testOneShiftCase(.llshl, .{5, &.{32}, &.{1}});
try testOneShiftCase(.llshl, .{5, &.{4015514958336}, &.{125484842448}});
try testOneShiftCase(.llshl, .{5, &.{0x1bd5b7dde0}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{5, &.{0xffffffffffffffe0, 0x1f}, &.{maxint}});
try testOneShiftCase(.llshl, .{5, &.{0, 16}, &.{left_one}});
try testOneShiftCase(.llshl, .{5, &.{0, 32}, &.{0, 1}});
try testOneShiftCase(.llshl, .{5, &.{32, 64}, &.{1, 2}});
try testOneShiftCase(.llshl, .{5, &.{0, 48}, &.{left_one, 1}});
try testOneShiftCase(.llshl, .{64, &.{0, 1}, &.{1}});
try testOneShiftCase(.llshl, .{64, &.{0, 125484842448}, &.{125484842448}});
try testOneShiftCase(.llshl, .{64, &.{0, 0xdeadbeef}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{64, &.{0, maxint}, &.{maxint}});
try testOneShiftCase(.llshl, .{64, &.{0, left_one}, &.{left_one}});
try testOneShiftCase(.llshl, .{64, &.{0, 0, 1}, &.{0, 1}});
try testOneShiftCase(.llshl, .{64, &.{0, 1, 2}, &.{1, 2}});
try testOneShiftCase(.llshl, .{64, &.{0, left_one, 1}, &.{left_one, 1}});
try testOneShiftCase(.llshl, .{35, &.{0x800000000}, &.{1}});
try testOneShiftCase(.llshl, .{35, &.{13534986488655118336, 233}, &.{125484842448}});
try testOneShiftCase(.llshl, .{35, &.{0xf56df77800000000, 6}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{35, &.{0xfffffff800000000, 0x7ffffffff}, &.{maxint}});
try testOneShiftCase(.llshl, .{35, &.{0, 17179869184}, &.{left_one}});
try testOneShiftCase(.llshl, .{35, &.{0, 0x800000000}, &.{0, 1}});
try testOneShiftCase(.llshl, .{35, &.{0x800000000, 0x1000000000}, &.{1, 2}});
try testOneShiftCase(.llshl, .{35, &.{0, 0xc00000000}, &.{left_one, 1}});
try testOneShiftCase(.llshl, .{70, &.{0, 64}, &.{1}});
try testOneShiftCase(.llshl, .{70, &.{0, 8031029916672}, &.{125484842448}});
try testOneShiftCase(.llshl, .{70, &.{0, 0x37ab6fbbc0}, &.{0xdeadbeef}});
try testOneShiftCase(.llshl, .{70, &.{0, 0xffffffffffffffc0, 63}, &.{maxint}});
try testOneShiftCase(.llshl, .{70, &.{0, 0, 32}, &.{left_one}});
try testOneShiftCase(.llshl, .{70, &.{0, 0, 64}, &.{0, 1}});
try testOneShiftCase(.llshl, .{70, &.{0, 64, 128}, &.{1, 2}});
try testOneShiftCase(.llshl, .{70, &.{0, 0, 0x60}, &.{left_one, 1}});
// zig fmt: on
}
test "llshl shift 0" {
const n = @bitSizeOf(Limb);
if (n <= 20) return error.SkipZigTest;
// zig fmt: off
try testOneShiftCase(.llshl, .{0, &.{0}, &.{0}});
try testOneShiftCase(.llshl, .{1, &.{0}, &.{0}});
try testOneShiftCase(.llshl, .{5, &.{0}, &.{0}});
try testOneShiftCase(.llshl, .{13, &.{0}, &.{0}});
try testOneShiftCase(.llshl, .{20, &.{0}, &.{0}});
try testOneShiftCase(.llshl, .{0, &.{0, 0}, &.{0, 0}});
try testOneShiftCase(.llshl, .{2, &.{0, 0}, &.{0, 0}});
try testOneShiftCase(.llshl, .{7, &.{0, 0}, &.{0, 0}});
try testOneShiftCase(.llshl, .{11, &.{0, 0}, &.{0, 0}});
try testOneShiftCase(.llshl, .{19, &.{0, 0}, &.{0, 0}});
try testOneShiftCase(.llshl, .{0, &.{0}, &.{0}});
try testOneShiftCase(.llshl, .{n, &.{0, 0}, &.{0}});
try testOneShiftCase(.llshl, .{2*n, &.{0, 0, 0}, &.{0}});
try testOneShiftCase(.llshl, .{3*n, &.{0, 0, 0, 0}, &.{0}});
try testOneShiftCase(.llshl, .{4*n, &.{0, 0, 0, 0, 0}, &.{0}});
try testOneShiftCase(.llshl, .{0, &.{0, 0}, &.{0, 0}});
try testOneShiftCase(.llshl, .{n, &.{0, 0, 0}, &.{0, 0}});
try testOneShiftCase(.llshl, .{2*n, &.{0, 0, 0, 0}, &.{0, 0}});
try testOneShiftCase(.llshl, .{3*n, &.{0, 0, 0, 0, 0}, &.{0, 0}});
try testOneShiftCase(.llshl, .{4*n, &.{0, 0, 0, 0, 0, 0}, &.{0, 0}});
// zig fmt: on
}
test "llshr shift 0" {
const n = @bitSizeOf(Limb);
// zig fmt: off
try testOneShiftCase(.llshr, .{0, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{1, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{5, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{13, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{20, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{0, &.{0, 0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{2, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{7, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{11, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{19, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{n, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{2*n, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{3*n, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{4*n, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{n, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{2*n, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{3*n, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{4*n, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{1, &.{}, &.{}});
try testOneShiftCase(.llshr, .{2, &.{}, &.{}});
try testOneShiftCase(.llshr, .{64, &.{}, &.{}});
// zig fmt: on
}
test "llshr to 0" {
const n = @bitSizeOf(Limb);
if (n != 64 and n != 32) return error.SkipZigTest;
// zig fmt: off
try testOneShiftCase(.llshr, .{1, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{1, &.{0}, &.{1}});
try testOneShiftCase(.llshr, .{5, &.{0}, &.{1}});
try testOneShiftCase(.llshr, .{65, &.{0}, &.{0, 1}});
try testOneShiftCase(.llshr, .{193, &.{0}, &.{0, 0, maxInt(Limb)}});
try testOneShiftCase(.llshr, .{193, &.{0}, &.{maxInt(Limb), 1, maxInt(Limb)}});
try testOneShiftCase(.llshr, .{193, &.{0}, &.{0xdeadbeef, 0xabcdefab, 0x1234}});
// zig fmt: on
}
test "llshr single" {
if (limb_bits != 64) return error.SkipZigTest;
// 1 << 63
const left_one = 0x8000000000000000;
const maxint: Limb = 0xFFFFFFFFFFFFFFFF;
// zig fmt: off
try testOneShiftCase(.llshr, .{0, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{0, &.{1}, &.{1}});
try testOneShiftCase(.llshr, .{0, &.{125484842448}, &.{125484842448}});
try testOneShiftCase(.llshr, .{0, &.{0xdeadbeef}, &.{0xdeadbeef}});
try testOneShiftCase(.llshr, .{0, &.{maxint}, &.{maxint}});
try testOneShiftCase(.llshr, .{0, &.{left_one}, &.{left_one}});
try testOneShiftCase(.llshr, .{1, &.{0}, &.{0}});
try testOneShiftCase(.llshr, .{1, &.{1}, &.{2}});
try testOneShiftCase(.llshr, .{1, &.{62742421224}, &.{125484842448}});
try testOneShiftCase(.llshr, .{1, &.{62742421223}, &.{125484842447}});
try testOneShiftCase(.llshr, .{1, &.{0x6f56df77}, &.{0xdeadbeef}});
try testOneShiftCase(.llshr, .{1, &.{0x7fffffffffffffff}, &.{maxint}});
try testOneShiftCase(.llshr, .{1, &.{0x4000000000000000}, &.{left_one}});
try testOneShiftCase(.llshr, .{8, &.{1}, &.{256}});
try testOneShiftCase(.llshr, .{8, &.{490175165}, &.{125484842448}});
try testOneShiftCase(.llshr, .{8, &.{0xdeadbe}, &.{0xdeadbeef}});
try testOneShiftCase(.llshr, .{8, &.{0xffffffffffffff}, &.{maxint}});
try testOneShiftCase(.llshr, .{8, &.{0x80000000000000}, &.{left_one}});
// zig fmt: on
}
test llshr {
if (limb_bits != 64) return error.SkipZigTest;
// 1 << 63
const left_one = 0x8000000000000000;
const maxint: Limb = 0xFFFFFFFFFFFFFFFF;
// zig fmt: off
try testOneShiftCase(.llshr, .{0, &.{0, 0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{0, &.{0, 1}, &.{0, 1}});
try testOneShiftCase(.llshr, .{0, &.{15, 1}, &.{15, 1}});
try testOneShiftCase(.llshr, .{0, &.{987656565, 123456789456}, &.{987656565, 123456789456}});
try testOneShiftCase(.llshr, .{0, &.{0xfeebdaed, 0xdeadbeef}, &.{0xfeebdaed, 0xdeadbeef}});
try testOneShiftCase(.llshr, .{0, &.{1, maxint}, &.{1, maxint}});
try testOneShiftCase(.llshr, .{0, &.{0, left_one}, &.{0, left_one}});
try testOneShiftCase(.llshr, .{1, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{1, &.{left_one}, &.{0, 1}});
try testOneShiftCase(.llshr, .{1, &.{0x8000000000000007}, &.{15, 1}});
try testOneShiftCase(.llshr, .{1, &.{493828282, 61728394728}, &.{987656565, 123456789456}});
try testOneShiftCase(.llshr, .{1, &.{0x800000007f75ed76, 0x6f56df77}, &.{0xfeebdaed, 0xdeadbeef}});
try testOneShiftCase(.llshr, .{1, &.{left_one, 0x7fffffffffffffff}, &.{1, maxint}});
try testOneShiftCase(.llshr, .{1, &.{0, 0x4000000000000000}, &.{0, left_one}});
try testOneShiftCase(.llshr, .{64, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{64, &.{1}, &.{0, 1}});
try testOneShiftCase(.llshr, .{64, &.{1}, &.{15, 1}});
try testOneShiftCase(.llshr, .{64, &.{123456789456}, &.{987656565, 123456789456}});
try testOneShiftCase(.llshr, .{64, &.{0xdeadbeef}, &.{0xfeebdaed, 0xdeadbeef}});
try testOneShiftCase(.llshr, .{64, &.{maxint}, &.{1, maxint}});
try testOneShiftCase(.llshr, .{64, &.{left_one}, &.{0, left_one}});
try testOneShiftCase(.llshr, .{72, &.{0}, &.{0, 0}});
try testOneShiftCase(.llshr, .{72, &.{0}, &.{0, 1}});
try testOneShiftCase(.llshr, .{72, &.{0}, &.{15, 1}});
try testOneShiftCase(.llshr, .{72, &.{482253083}, &.{987656565, 123456789456}});
try testOneShiftCase(.llshr, .{72, &.{0xdeadbe}, &.{0xfeebdaed, 0xdeadbeef}});
try testOneShiftCase(.llshr, .{72, &.{0xffffffffffffff}, &.{1, maxint}});
try testOneShiftCase(.llshr, .{72, &.{0x80000000000000}, &.{0, left_one}});
// zig fmt: on
}
const Case = struct { usize, []const Limb, []const Limb };
fn testOneShiftCase(comptime function: enum { llshr, llshl }, case: Case) !void {
const func = if (function == .llshl) llshl else llshr;
const shift_direction = if (function == .llshl) -1 else 1;
try testOneShiftCaseNoAliasing(func, case);
try testOneShiftCaseAliasing(func, case, shift_direction);
}
fn testOneShiftCaseNoAliasing(func: fn ([]Limb, []const Limb, usize) usize, case: Case) !void {
const padding = maxInt(Limb);
var r: [20]Limb = @splat(padding);
const shift = case[0];
const expected = case[1];
const data = case[2];
std.debug.assert(expected.len <= 20);
const len = func(&r, data, shift);
try std.testing.expectEqual(expected.len, len);
try std.testing.expectEqualSlices(Limb, expected, r[0..len]);
try std.testing.expect(mem.allEqual(Limb, r[len..], padding));
}
fn testOneShiftCaseAliasing(func: fn ([]Limb, []const Limb, usize) usize, case: Case, shift_direction: isize) !void {
const padding = maxInt(Limb);
var r: [60]Limb = @splat(padding);
const base = 20;
assert(shift_direction == 1 or shift_direction == -1);
for (0..10) |limb_shift| {
const shift = case[0];
const expected = case[1];
const data = case[2];
std.debug.assert(expected.len <= 20);
@memset(&r, padding);
const final_limb_base: usize = @intCast(base + shift_direction * @as(isize, @intCast(limb_shift)));
const written_data = r[final_limb_base..][0..data.len];
@memcpy(written_data, data);
const len = func(r[base..], written_data, shift);
try std.testing.expectEqual(expected.len, len);
try std.testing.expectEqualSlices(Limb, expected, r[base .. base + len]);
}
}
test "format" {
var a: Managed = try .init(std.testing.allocator);
defer a.deinit();
try a.set(123);
try testFormat(a, "123");
try a.set(-123);
try testFormat(a, "-123");
try a.set(20000000000000000000); // > maxInt(u64)
try testFormat(a, "20000000000000000000");
try a.set(1 << 64 * @sizeOf(usize) * 8);
try testFormat(a, "(BigInt)");
try a.set(-(1 << 64 * @sizeOf(usize) * 8));
try testFormat(a, "(BigInt)");
}
fn testFormat(a: Managed, expected: []const u8) !void {
try std.testing.expectFmt(expected, "{f}", .{a});
try std.testing.expectFmt(expected, "{f}", .{a.toMutable()});
try std.testing.expectFmt(expected, "{f}", .{a.toConst()});
}