mirror of
https://github.com/nim-lang/Nim.git
synced 2025-12-28 17:04:41 +00:00
782 lines
30 KiB
Nim
782 lines
30 KiB
Nim
## This module is for compiler internal use only. For reliable error
|
|
## messages and range checks, the compiler needs a data type that can
|
|
## hold all from ``low(BiggestInt)`` to ``high(BiggestUInt)``, This
|
|
## type is for that purpose.
|
|
|
|
from math import trunc
|
|
|
|
type
|
|
Int128* = object
|
|
udata: array[4,uint32]
|
|
|
|
template sdata(arg: Int128, idx: int): int32 =
|
|
# udata and sdata was supposed to be in a union, but unions are
|
|
# handled incorrectly in the VM.
|
|
cast[ptr int32](arg.udata[idx].unsafeAddr)[]
|
|
|
|
# encoding least significant int first (like LittleEndian)
|
|
|
|
const
|
|
Zero* = Int128(udata: [0'u32,0,0,0])
|
|
One* = Int128(udata: [1'u32,0,0,0])
|
|
Ten* = Int128(udata: [10'u32,0,0,0])
|
|
Min = Int128(udata: [0'u32,0,0,0x80000000'u32])
|
|
Max = Int128(udata: [high(uint32),high(uint32),high(uint32),uint32(high(int32))])
|
|
NegOne* = Int128(udata: [0xffffffff'u32,0xffffffff'u32,0xffffffff'u32,0xffffffff'u32])
|
|
|
|
template low*(t: typedesc[Int128]): Int128 = Min
|
|
template high*(t: typedesc[Int128]): Int128 = Max
|
|
|
|
proc `$`*(a: Int128): string
|
|
|
|
proc toInt128*[T: SomeInteger | bool](arg: T): Int128 =
|
|
when T is bool: result.sdata(0) = int32(arg)
|
|
elif T is SomeUnsignedInt:
|
|
when sizeof(arg) <= 4:
|
|
result.udata[0] = uint32(arg)
|
|
else:
|
|
result.udata[0] = uint32(arg and T(0xffffffff))
|
|
result.udata[1] = uint32(arg shr 32)
|
|
elif sizeof(arg) <= 4:
|
|
result.sdata(0) = int32(arg)
|
|
if arg < 0: # sign extend
|
|
result.sdata(1) = -1
|
|
result.sdata(2) = -1
|
|
result.sdata(3) = -1
|
|
else:
|
|
let tmp = int64(arg)
|
|
result.udata[0] = uint32(tmp and 0xffffffff)
|
|
result.sdata(1) = int32(tmp shr 32)
|
|
if arg < 0: # sign extend
|
|
result.sdata(2) = -1
|
|
result.sdata(3) = -1
|
|
|
|
template isNegative(arg: Int128): bool =
|
|
arg.sdata(3) < 0
|
|
|
|
template isNegative(arg: int32): bool =
|
|
arg < 0
|
|
|
|
proc bitconcat(a,b: uint32): uint64 =
|
|
(uint64(a) shl 32) or uint64(b)
|
|
|
|
proc bitsplit(a: uint64): (uint32,uint32) =
|
|
(cast[uint32](a shr 32), cast[uint32](a))
|
|
|
|
proc toInt64*(arg: Int128): int64 =
|
|
if isNegative(arg):
|
|
assert(arg.sdata(3) == -1, "out of range")
|
|
assert(arg.sdata(2) == -1, "out of range")
|
|
else:
|
|
assert(arg.sdata(3) == 0, "out of range")
|
|
assert(arg.sdata(2) == 0, "out of range")
|
|
|
|
cast[int64](bitconcat(arg.udata[1], arg.udata[0]))
|
|
|
|
proc toInt64Checked*(arg: Int128; onError: int64): int64 =
|
|
if isNegative(arg):
|
|
if arg.sdata(3) != -1 or arg.sdata(2) != -1:
|
|
return onError
|
|
else:
|
|
if arg.sdata(3) != 0 or arg.sdata(2) != 0:
|
|
return onError
|
|
return cast[int64](bitconcat(arg.udata[1], arg.udata[0]))
|
|
|
|
proc toInt32*(arg: Int128): int32 =
|
|
if isNegative(arg):
|
|
assert(arg.sdata(3) == -1, "out of range")
|
|
assert(arg.sdata(2) == -1, "out of range")
|
|
assert(arg.sdata(1) == -1, "out of range")
|
|
else:
|
|
assert(arg.sdata(3) == 0, "out of range")
|
|
assert(arg.sdata(2) == 0, "out of range")
|
|
assert(arg.sdata(1) == 0, "out of range")
|
|
|
|
arg.sdata(0)
|
|
|
|
proc toInt16*(arg: Int128): int16 =
|
|
if isNegative(arg):
|
|
assert(arg.sdata(3) == -1, "out of range")
|
|
assert(arg.sdata(2) == -1, "out of range")
|
|
assert(arg.sdata(1) == -1, "out of range")
|
|
else:
|
|
assert(arg.sdata(3) == 0, "out of range")
|
|
assert(arg.sdata(2) == 0, "out of range")
|
|
assert(arg.sdata(1) == 0, "out of range")
|
|
|
|
int16(arg.sdata(0))
|
|
|
|
proc toInt8*(arg: Int128): int8 =
|
|
if isNegative(arg):
|
|
assert(arg.sdata(3) == -1, "out of range")
|
|
assert(arg.sdata(2) == -1, "out of range")
|
|
assert(arg.sdata(1) == -1, "out of range")
|
|
else:
|
|
assert(arg.sdata(3) == 0, "out of range")
|
|
assert(arg.sdata(2) == 0, "out of range")
|
|
assert(arg.sdata(1) == 0, "out of range")
|
|
|
|
int8(arg.sdata(0))
|
|
|
|
proc toInt*(arg: Int128): int =
|
|
when sizeof(int) == 4:
|
|
cast[int](toInt32(arg))
|
|
else:
|
|
cast[int](toInt64(arg))
|
|
|
|
proc toUInt64*(arg: Int128): uint64 =
|
|
assert(arg.udata[3] == 0)
|
|
assert(arg.udata[2] == 0)
|
|
bitconcat(arg.udata[1], arg.udata[0])
|
|
|
|
proc toUInt32*(arg: Int128): uint32 =
|
|
assert(arg.udata[3] == 0)
|
|
assert(arg.udata[2] == 0)
|
|
assert(arg.udata[1] == 0)
|
|
arg.udata[0]
|
|
|
|
proc toUInt16*(arg: Int128): uint16 =
|
|
assert(arg.udata[3] == 0)
|
|
assert(arg.udata[2] == 0)
|
|
assert(arg.udata[1] == 0)
|
|
uint16(arg.udata[0])
|
|
|
|
proc toUInt8*(arg: Int128): uint8 =
|
|
assert(arg.udata[3] == 0)
|
|
assert(arg.udata[2] == 0)
|
|
assert(arg.udata[1] == 0)
|
|
uint8(arg.udata[0])
|
|
|
|
proc toUInt*(arg: Int128): uint =
|
|
when sizeof(int) == 4:
|
|
cast[uint](toInt32(arg))
|
|
else:
|
|
cast[uint](toInt64(arg))
|
|
|
|
proc castToInt64*(arg: Int128): int64 =
|
|
## Conversion to int64 without range check.
|
|
cast[int64](bitconcat(arg.udata[1], arg.udata[0]))
|
|
|
|
proc castToUInt64*(arg: Int128): uint64 =
|
|
## Conversion to uint64 without range check.
|
|
cast[uint64](bitconcat(arg.udata[1], arg.udata[0]))
|
|
|
|
proc addToHex(result: var string; arg: uint32) =
|
|
for i in 0..<8:
|
|
let idx = (arg shr ((7-i) * 4)) and 0xf
|
|
result.add "0123456789abcdef"[idx]
|
|
|
|
proc addToHex*(result: var string; arg: Int128) =
|
|
var i = 3
|
|
while i >= 0:
|
|
result.addToHex(arg.udata[i])
|
|
i -= 1
|
|
|
|
proc toHex*(arg: Int128): string =
|
|
result.addToHex(arg)
|
|
|
|
proc inc*(a: var Int128, y: uint32 = 1) =
|
|
let input = a
|
|
a.udata[0] += y
|
|
if unlikely(a.udata[0] < y):
|
|
a.udata[1].inc
|
|
if unlikely(a.udata[1] == 0):
|
|
a.udata[2].inc
|
|
if unlikely(a.udata[2] == 0):
|
|
a.udata[3].inc
|
|
doAssert(a.sdata(3) != low(int32), "overflow")
|
|
|
|
proc cmp*(a,b: Int128): int =
|
|
let tmp1 = cmp(a.sdata(3), b.sdata(3))
|
|
if tmp1 != 0: return tmp1
|
|
let tmp2 = cmp(a.udata[2], b.udata[2])
|
|
if tmp2 != 0: return tmp2
|
|
let tmp3 = cmp(a.udata[1], b.udata[1])
|
|
if tmp3 != 0: return tmp3
|
|
let tmp4 = cmp(a.udata[0], b.udata[0])
|
|
return tmp4
|
|
|
|
proc `<`*(a,b: Int128): bool =
|
|
cmp(a,b) < 0
|
|
|
|
proc `<=`*(a,b: Int128): bool =
|
|
cmp(a,b) <= 0
|
|
|
|
proc `==`*(a,b: Int128): bool =
|
|
if a.udata[0] != b.udata[0]: return false
|
|
if a.udata[1] != b.udata[1]: return false
|
|
if a.udata[2] != b.udata[2]: return false
|
|
if a.udata[3] != b.udata[3]: return false
|
|
return true
|
|
|
|
proc inplaceBitnot(a: var Int128) =
|
|
a.udata[0] = not a.udata[0]
|
|
a.udata[1] = not a.udata[1]
|
|
a.udata[2] = not a.udata[2]
|
|
a.udata[3] = not a.udata[3]
|
|
|
|
proc bitnot*(a: Int128): Int128 =
|
|
result.udata[0] = not a.udata[0]
|
|
result.udata[1] = not a.udata[1]
|
|
result.udata[2] = not a.udata[2]
|
|
result.udata[3] = not a.udata[3]
|
|
|
|
proc bitand*(a,b: Int128): Int128 =
|
|
result.udata[0] = a.udata[0] and b.udata[0]
|
|
result.udata[1] = a.udata[1] and b.udata[1]
|
|
result.udata[2] = a.udata[2] and b.udata[2]
|
|
result.udata[3] = a.udata[3] and b.udata[3]
|
|
|
|
proc bitor*(a,b: Int128): Int128 =
|
|
result.udata[0] = a.udata[0] or b.udata[0]
|
|
result.udata[1] = a.udata[1] or b.udata[1]
|
|
result.udata[2] = a.udata[2] or b.udata[2]
|
|
result.udata[3] = a.udata[3] or b.udata[3]
|
|
|
|
proc bitxor*(a,b: Int128): Int128 =
|
|
result.udata[0] = a.udata[0] xor b.udata[0]
|
|
result.udata[1] = a.udata[1] xor b.udata[1]
|
|
result.udata[2] = a.udata[2] xor b.udata[2]
|
|
result.udata[3] = a.udata[3] xor b.udata[3]
|
|
|
|
proc `shr`*(a: Int128, b: int): Int128 =
|
|
let b = b and 127
|
|
if b < 32:
|
|
result.sdata(3) = a.sdata(3) shr b
|
|
result.udata[2] = cast[uint32](bitconcat(a.udata[3], a.udata[2]) shr b)
|
|
result.udata[1] = cast[uint32](bitconcat(a.udata[2], a.udata[1]) shr b)
|
|
result.udata[0] = cast[uint32](bitconcat(a.udata[1], a.udata[0]) shr b)
|
|
elif b < 64:
|
|
if isNegative(a):
|
|
result.sdata(3) = -1
|
|
result.sdata(2) = a.sdata(3) shr (b and 31)
|
|
result.udata[1] = cast[uint32](bitconcat(a.udata[3], a.udata[2]) shr (b and 31))
|
|
result.udata[0] = cast[uint32](bitconcat(a.udata[2], a.udata[1]) shr (b and 31))
|
|
elif b < 96:
|
|
if isNegative(a):
|
|
result.sdata(3) = -1
|
|
result.sdata(2) = -1
|
|
result.sdata(1) = a.sdata(3) shr (b and 31)
|
|
result.udata[0] = cast[uint32](bitconcat(a.udata[3], a.udata[2]) shr (b and 31))
|
|
else: # b < 128
|
|
if isNegative(a):
|
|
result.sdata(3) = -1
|
|
result.sdata(2) = -1
|
|
result.sdata(1) = -1
|
|
result.sdata(0) = a.sdata(3) shr (b and 31)
|
|
|
|
proc `shl`*(a: Int128, b: int): Int128 =
|
|
let b = b and 127
|
|
if b < 32:
|
|
result.udata[0] = a.udata[0] shl b
|
|
result.udata[1] = cast[uint32]((bitconcat(a.udata[1], a.udata[0]) shl b) shr 32)
|
|
result.udata[2] = cast[uint32]((bitconcat(a.udata[2], a.udata[1]) shl b) shr 32)
|
|
result.udata[3] = cast[uint32]((bitconcat(a.udata[3], a.udata[2]) shl b) shr 32)
|
|
elif b < 64:
|
|
result.udata[0] = 0
|
|
result.udata[1] = a.udata[0] shl (b and 31)
|
|
result.udata[2] = cast[uint32]((bitconcat(a.udata[1], a.udata[0]) shl (b and 31)) shr 32)
|
|
result.udata[3] = cast[uint32]((bitconcat(a.udata[2], a.udata[1]) shl (b and 31)) shr 32)
|
|
elif b < 96:
|
|
result.udata[0] = 0
|
|
result.udata[1] = 0
|
|
result.udata[2] = a.udata[0] shl (b and 31)
|
|
result.udata[3] = cast[uint32]((bitconcat(a.udata[1], a.udata[0]) shl (b and 31)) shr 32)
|
|
else:
|
|
result.udata[0] = 0
|
|
result.udata[1] = 0
|
|
result.udata[2] = 0
|
|
result.udata[3] = a.udata[0] shl (b and 31)
|
|
|
|
proc `+`*(a,b: Int128): Int128 =
|
|
let tmp0 = uint64(a.udata[0]) + uint64(b.udata[0])
|
|
result.udata[0] = cast[uint32](tmp0)
|
|
let tmp1 = uint64(a.udata[1]) + uint64(b.udata[1]) + (tmp0 shr 32)
|
|
result.udata[1] = cast[uint32](tmp1)
|
|
let tmp2 = uint64(a.udata[2]) + uint64(b.udata[2]) + (tmp1 shr 32)
|
|
result.udata[2] = cast[uint32](tmp2)
|
|
let tmp3 = uint64(a.udata[3]) + uint64(b.udata[3]) + (tmp2 shr 32)
|
|
result.udata[3] = cast[uint32](tmp3)
|
|
|
|
proc `+=`*(a: var Int128, b: Int128) =
|
|
a = a + b
|
|
|
|
proc `-`*(a: Int128): Int128 =
|
|
result = bitnot(a)
|
|
result.inc
|
|
|
|
proc `-`*(a,b: Int128): Int128 =
|
|
a + (-b)
|
|
|
|
proc `-=`*(a: var Int128, b: Int128) =
|
|
a = a - b
|
|
|
|
proc abs*(a: Int128): Int128 =
|
|
if isNegative(a):
|
|
-a
|
|
else:
|
|
a
|
|
|
|
proc abs(a: int32): int =
|
|
if a < 0: -a else: a
|
|
|
|
proc `*`(a: Int128, b: uint32): Int128 =
|
|
let tmp0 = uint64(a.udata[0]) * uint64(b)
|
|
let tmp1 = uint64(a.udata[1]) * uint64(b)
|
|
let tmp2 = uint64(a.udata[2]) * uint64(b)
|
|
let tmp3 = uint64(a.udata[3]) * uint64(b)
|
|
|
|
if unlikely(tmp3 > uint64(high(int32))):
|
|
assert(false, "overflow")
|
|
|
|
result.udata[0] = cast[uint32](tmp0)
|
|
result.udata[1] = cast[uint32](tmp1) + cast[uint32](tmp0 shr 32)
|
|
result.udata[2] = cast[uint32](tmp2) + cast[uint32](tmp1 shr 32)
|
|
result.udata[3] = cast[uint32](tmp3) + cast[uint32](tmp2 shr 32)
|
|
|
|
proc `*`*(a: Int128, b: int32): Int128 =
|
|
result = a * cast[uint32](abs(b))
|
|
if b < 0:
|
|
result = -result
|
|
|
|
proc `*=`*(a: var Int128, b: int32): Int128 =
|
|
result = result * b
|
|
|
|
proc makeInt128(high,low: uint64): Int128 =
|
|
result.udata[0] = cast[uint32](low)
|
|
result.udata[1] = cast[uint32](low shr 32)
|
|
result.udata[2] = cast[uint32](high)
|
|
result.udata[3] = cast[uint32](high shr 32)
|
|
|
|
proc high64(a: Int128): uint64 =
|
|
bitconcat(a.udata[3], a.udata[2])
|
|
|
|
proc low64(a: Int128): uint64 =
|
|
bitconcat(a.udata[1], a.udata[0])
|
|
|
|
proc `*`*(lhs,rhs: Int128): Int128 =
|
|
let
|
|
a = cast[uint64](lhs.udata[0])
|
|
b = cast[uint64](lhs.udata[1])
|
|
c = cast[uint64](lhs.udata[2])
|
|
d = cast[uint64](lhs.udata[3])
|
|
|
|
e = cast[uint64](rhs.udata[0])
|
|
f = cast[uint64](rhs.udata[1])
|
|
g = cast[uint64](rhs.udata[2])
|
|
h = cast[uint64](rhs.udata[3])
|
|
|
|
|
|
let a32 = cast[uint64](lhs.udata[1])
|
|
let a00 = cast[uint64](lhs.udata[0])
|
|
let b32 = cast[uint64](rhs.udata[1])
|
|
let b00 = cast[uint64](rhs.udata[0])
|
|
|
|
result = makeInt128(high64(lhs) * low64(rhs) + low64(lhs) * high64(rhs) + a32 * b32, a00 * b00)
|
|
result = result + toInt128(a32 * b00) shl 32
|
|
result = result + toInt128(a00 * b32) shl 32
|
|
|
|
proc `*=`*(a: var Int128, b: Int128) =
|
|
a = a * b
|
|
|
|
import bitops
|
|
|
|
proc fastLog2*(a: Int128): int =
|
|
if a.udata[3] != 0:
|
|
return 96 + fastLog2(a.udata[3])
|
|
if a.udata[2] != 0:
|
|
return 64 + fastLog2(a.udata[2])
|
|
if a.udata[1] != 0:
|
|
return 32 + fastLog2(a.udata[1])
|
|
if a.udata[0] != 0:
|
|
return fastLog2(a.udata[0])
|
|
|
|
proc divMod*(dividend, divisor: Int128): tuple[quotient, remainder: Int128] =
|
|
assert(divisor != Zero)
|
|
let isNegativeA = isNegative(dividend)
|
|
let isNegativeB = isNegative(divisor)
|
|
|
|
var dividend = abs(dividend)
|
|
let divisor = abs(divisor)
|
|
|
|
if divisor > dividend:
|
|
result.quotient = Zero
|
|
if isNegativeA:
|
|
result.remainder = -dividend
|
|
else:
|
|
result.remainder = dividend
|
|
return
|
|
|
|
if divisor == dividend:
|
|
if isNegativeA xor isNegativeB:
|
|
result.quotient = NegOne
|
|
else:
|
|
result.quotient = One
|
|
result.remainder = Zero
|
|
return
|
|
|
|
var denominator = divisor
|
|
var quotient = Zero
|
|
|
|
# Left aligns the MSB of the denominator and the dividend.
|
|
let shift = fastLog2(dividend) - fastLog2(denominator)
|
|
denominator = denominator shl shift
|
|
|
|
# Uses shift-subtract algorithm to divide dividend by denominator. The
|
|
# remainder will be left in dividend.
|
|
for i in 0..shift:
|
|
quotient = quotient shl 1
|
|
if dividend >= denominator:
|
|
dividend = dividend - denominator
|
|
quotient = bitor(quotient, One)
|
|
|
|
denominator = denominator shr 1
|
|
|
|
if isNegativeA xor isNegativeB:
|
|
result.quotient = -quotient
|
|
else:
|
|
result.quotient = quotient
|
|
if isNegativeA:
|
|
result.remainder = -dividend
|
|
else:
|
|
result.remainder = dividend
|
|
|
|
proc `div`*(a,b: Int128): Int128 =
|
|
let (a,b) = divMod(a,b)
|
|
return a
|
|
|
|
proc `mod`*(a,b: Int128): Int128 =
|
|
let (a,b) = divMod(a,b)
|
|
return b
|
|
|
|
proc addInt128*(result: var string; value: Int128) =
|
|
let initialSize = result.len
|
|
if value == Zero:
|
|
result.add "0"
|
|
elif value == low(Int128):
|
|
result.add "-170141183460469231731687303715884105728"
|
|
else:
|
|
let isNegative = isNegative(value)
|
|
var value = abs(value)
|
|
while value > Zero:
|
|
let (quot, rem) = divMod(value, Ten)
|
|
result.add "0123456789"[rem.toInt64]
|
|
value = quot
|
|
if isNegative:
|
|
result.add '-'
|
|
|
|
var i = initialSize
|
|
var j = high(result)
|
|
while i < j:
|
|
swap(result[i], result[j])
|
|
i += 1
|
|
j -= 1
|
|
|
|
proc `$`*(a: Int128): string =
|
|
result.addInt128(a)
|
|
|
|
proc parseDecimalInt128*(arg: string, pos: int = 0): Int128 =
|
|
assert(pos < arg.len)
|
|
assert(arg[pos] in {'-','0'..'9'})
|
|
|
|
var isNegative = false
|
|
var pos = pos
|
|
if arg[pos] == '-':
|
|
isNegative = true
|
|
pos += 1
|
|
|
|
result = Zero
|
|
while pos < arg.len and arg[pos] in '0'..'9':
|
|
result = result * Ten
|
|
result.inc(uint32(arg[pos]) - uint32('0'))
|
|
pos += 1
|
|
|
|
if isNegative:
|
|
result = -result
|
|
|
|
# fluff
|
|
|
|
proc `<`*(a: Int128, b: BiggestInt): bool =
|
|
cmp(a,toInt128(b)) < 0
|
|
|
|
proc `<`*(a: BiggestInt, b: Int128): bool =
|
|
cmp(toInt128(a), b) < 0
|
|
|
|
proc `<=`*(a: Int128, b: BiggestInt): bool =
|
|
cmp(a,toInt128(b)) <= 0
|
|
|
|
proc `<=`*(a: BiggestInt, b: Int128): bool =
|
|
cmp(toInt128(a), b) <= 0
|
|
|
|
proc `==`*(a: Int128, b: BiggestInt): bool =
|
|
a == toInt128(b)
|
|
|
|
proc `==`*(a: BiggestInt, b: Int128): bool =
|
|
toInt128(a) == b
|
|
|
|
proc `-`*(a: BiggestInt, b: Int128): Int128 =
|
|
toInt128(a) - b
|
|
|
|
proc `-`*(a: Int128, b: BiggestInt): Int128 =
|
|
a - toInt128(b)
|
|
|
|
proc `+`*(a: BiggestInt, b: Int128): Int128 =
|
|
toInt128(a) + b
|
|
|
|
proc `+`*(a: Int128, b: BiggestInt): Int128 =
|
|
a + toInt128(b)
|
|
|
|
proc toFloat64*(arg: Int128): float64 =
|
|
let isNegative = isNegative(arg)
|
|
let arg = abs(arg)
|
|
|
|
let a = float64(bitconcat(arg.udata[1], arg.udata[0]))
|
|
let b = float64(bitconcat(arg.udata[3], arg.udata[2]))
|
|
|
|
result = a + 18446744073709551616'f64 * b # a + 2^64 * b
|
|
if isNegative:
|
|
result = -result
|
|
|
|
proc ldexp(x: float64, exp: cint): float64 {.importc: "ldexp", header: "<math.h>".}
|
|
|
|
template bitor(a,b,c: Int128): Int128 = bitor(bitor(a,b), c)
|
|
|
|
proc toInt128*(arg: float64): Int128 =
|
|
let isNegative = arg < 0
|
|
let v0 = ldexp(abs(arg), -100)
|
|
let w0 = uint64(trunc(v0))
|
|
let v1 = ldexp(v0 - float64(w0), 50)
|
|
let w1 = uint64(trunc(v1))
|
|
let v2 = ldexp(v1 - float64(w1), 50)
|
|
let w2 = uint64(trunc(v2))
|
|
|
|
let res = bitor(toInt128(w0) shl 100, toInt128(w1) shl 50, toInt128(w2))
|
|
if isNegative:
|
|
return -res
|
|
else:
|
|
return res
|
|
|
|
proc maskUInt64*(arg: Int128): Int128 {.noinit, inline.} =
|
|
result.udata[0] = arg.udata[0]
|
|
result.udata[1] = arg.udata[1]
|
|
result.udata[2] = 0
|
|
result.udata[3] = 0
|
|
|
|
proc maskUInt32*(arg: Int128): Int128 {.noinit, inline.} =
|
|
result.udata[0] = arg.udata[0]
|
|
result.udata[1] = 0
|
|
result.udata[2] = 0
|
|
result.udata[3] = 0
|
|
|
|
proc maskUInt16*(arg: Int128): Int128 {.noinit, inline.} =
|
|
result.udata[0] = arg.udata[0] and 0xffff
|
|
result.udata[1] = 0
|
|
result.udata[2] = 0
|
|
result.udata[3] = 0
|
|
|
|
proc maskUInt8*(arg: Int128): Int128 {.noinit, inline.} =
|
|
result.udata[0] = arg.udata[0] and 0xff
|
|
result.udata[1] = 0
|
|
result.udata[2] = 0
|
|
result.udata[3] = 0
|
|
|
|
proc maskBytes*(arg: Int128, numbytes: int): Int128 {.noinit.} =
|
|
case numbytes
|
|
of 1:
|
|
return maskUInt8(arg)
|
|
of 2:
|
|
return maskUInt16(arg)
|
|
of 4:
|
|
return maskUInt32(arg)
|
|
of 8:
|
|
return maskUInt64(arg)
|
|
else:
|
|
assert(false, "masking only implemented for 1, 2, 4 and 8 bytes")
|
|
|
|
|
|
|
|
|
|
when isMainModule:
|
|
let (a,b) = divMod(Ten,Ten)
|
|
|
|
doAssert $One == "1"
|
|
doAssert $Ten == "10"
|
|
doAssert $Zero == "0"
|
|
let c = parseDecimalInt128("12345678989876543210123456789")
|
|
doAssert $c == "12345678989876543210123456789"
|
|
|
|
var d : array[39, Int128]
|
|
d[0] = parseDecimalInt128("1")
|
|
d[1] = parseDecimalInt128("10")
|
|
d[2] = parseDecimalInt128("100")
|
|
d[3] = parseDecimalInt128("1000")
|
|
d[4] = parseDecimalInt128("10000")
|
|
d[5] = parseDecimalInt128("100000")
|
|
d[6] = parseDecimalInt128("1000000")
|
|
d[7] = parseDecimalInt128("10000000")
|
|
d[8] = parseDecimalInt128("100000000")
|
|
d[9] = parseDecimalInt128("1000000000")
|
|
d[10] = parseDecimalInt128("10000000000")
|
|
d[11] = parseDecimalInt128("100000000000")
|
|
d[12] = parseDecimalInt128("1000000000000")
|
|
d[13] = parseDecimalInt128("10000000000000")
|
|
d[14] = parseDecimalInt128("100000000000000")
|
|
d[15] = parseDecimalInt128("1000000000000000")
|
|
d[16] = parseDecimalInt128("10000000000000000")
|
|
d[17] = parseDecimalInt128("100000000000000000")
|
|
d[18] = parseDecimalInt128("1000000000000000000")
|
|
d[19] = parseDecimalInt128("10000000000000000000")
|
|
d[20] = parseDecimalInt128("100000000000000000000")
|
|
d[21] = parseDecimalInt128("1000000000000000000000")
|
|
d[22] = parseDecimalInt128("10000000000000000000000")
|
|
d[23] = parseDecimalInt128("100000000000000000000000")
|
|
d[24] = parseDecimalInt128("1000000000000000000000000")
|
|
d[25] = parseDecimalInt128("10000000000000000000000000")
|
|
d[26] = parseDecimalInt128("100000000000000000000000000")
|
|
d[27] = parseDecimalInt128("1000000000000000000000000000")
|
|
d[28] = parseDecimalInt128("10000000000000000000000000000")
|
|
d[29] = parseDecimalInt128("100000000000000000000000000000")
|
|
d[30] = parseDecimalInt128("1000000000000000000000000000000")
|
|
d[31] = parseDecimalInt128("10000000000000000000000000000000")
|
|
d[32] = parseDecimalInt128("100000000000000000000000000000000")
|
|
d[33] = parseDecimalInt128("1000000000000000000000000000000000")
|
|
d[34] = parseDecimalInt128("10000000000000000000000000000000000")
|
|
d[35] = parseDecimalInt128("100000000000000000000000000000000000")
|
|
d[36] = parseDecimalInt128("1000000000000000000000000000000000000")
|
|
d[37] = parseDecimalInt128("10000000000000000000000000000000000000")
|
|
d[38] = parseDecimalInt128("100000000000000000000000000000000000000")
|
|
|
|
for i in 0..<d.len:
|
|
for j in 0..<d.len:
|
|
doAssert(cmp(d[i], d[j]) == cmp(i,j))
|
|
if i + j < d.len:
|
|
doAssert d[i] * d[j] == d[i+j]
|
|
if i - j >= 0:
|
|
doAssert d[i] div d[j] == d[i-j]
|
|
|
|
var sum: Int128
|
|
|
|
for it in d:
|
|
sum += it
|
|
|
|
doAssert $sum == "111111111111111111111111111111111111111"
|
|
|
|
for it in d.mitems:
|
|
it = -it
|
|
|
|
for i in 0..<d.len:
|
|
for j in 0..<d.len:
|
|
doAssert(cmp(d[i], d[j]) == -cmp(i,j))
|
|
if i + j < d.len:
|
|
doAssert d[i] * d[j] == -d[i+j]
|
|
if i - j >= 0:
|
|
doAssert d[i] div d[j] == -d[i-j]
|
|
|
|
doAssert $high(Int128) == "170141183460469231731687303715884105727"
|
|
doAssert $low(Int128) == "-170141183460469231731687303715884105728"
|
|
|
|
var ma = 100'i64
|
|
var mb = 13
|
|
|
|
doAssert toInt128(ma) * toInt128(0) == toInt128(0)
|
|
doAssert toInt128(-ma) * toInt128(0) == toInt128(0)
|
|
|
|
# sign correctness
|
|
doAssert divMod(toInt128( ma),toInt128( mb)) == (toInt128( ma div mb), toInt128( ma mod mb))
|
|
doAssert divMod(toInt128(-ma),toInt128( mb)) == (toInt128(-ma div mb), toInt128(-ma mod mb))
|
|
doAssert divMod(toInt128( ma),toInt128(-mb)) == (toInt128( ma div -mb), toInt128( ma mod -mb))
|
|
doAssert divMod(toInt128(-ma),toInt128(-mb)) == (toInt128(-ma div -mb), toInt128(-ma mod -mb))
|
|
|
|
doAssert divMod(toInt128( mb),toInt128( mb)) == (toInt128( mb div mb), toInt128( mb mod mb))
|
|
doAssert divMod(toInt128(-mb),toInt128( mb)) == (toInt128(-mb div mb), toInt128(-mb mod mb))
|
|
doAssert divMod(toInt128( mb),toInt128(-mb)) == (toInt128( mb div -mb), toInt128( mb mod -mb))
|
|
doAssert divMod(toInt128(-mb),toInt128(-mb)) == (toInt128(-mb div -mb), toInt128(-mb mod -mb))
|
|
|
|
doAssert divMod(toInt128( mb),toInt128( ma)) == (toInt128( mb div ma), toInt128( mb mod ma))
|
|
doAssert divMod(toInt128(-mb),toInt128( ma)) == (toInt128(-mb div ma), toInt128(-mb mod ma))
|
|
doAssert divMod(toInt128( mb),toInt128(-ma)) == (toInt128( mb div -ma), toInt128( mb mod -ma))
|
|
doAssert divMod(toInt128(-mb),toInt128(-ma)) == (toInt128(-mb div -ma), toInt128(-mb mod -ma))
|
|
|
|
let e = parseDecimalInt128("70997106675279150998592376708984375")
|
|
|
|
let strArray = [
|
|
# toHex(e shr 0), toHex(e shr 1), toHex(e shr 2), toHex(e shr 3)
|
|
"000dac6d782d266a37300c32591eee37", "0006d636bc1693351b9806192c8f771b", "00036b1b5e0b499a8dcc030c9647bb8d", "0001b58daf05a4cd46e601864b23ddc6",
|
|
"0000dac6d782d266a37300c32591eee3", "00006d636bc1693351b9806192c8f771", "000036b1b5e0b499a8dcc030c9647bb8", "00001b58daf05a4cd46e601864b23ddc",
|
|
"00000dac6d782d266a37300c32591eee", "000006d636bc1693351b9806192c8f77", "0000036b1b5e0b499a8dcc030c9647bb", "000001b58daf05a4cd46e601864b23dd",
|
|
"000000dac6d782d266a37300c32591ee", "0000006d636bc1693351b9806192c8f7", "00000036b1b5e0b499a8dcc030c9647b", "0000001b58daf05a4cd46e601864b23d",
|
|
"0000000dac6d782d266a37300c32591e", "00000006d636bc1693351b9806192c8f", "000000036b1b5e0b499a8dcc030c9647", "00000001b58daf05a4cd46e601864b23",
|
|
"00000000dac6d782d266a37300c32591", "000000006d636bc1693351b9806192c8", "0000000036b1b5e0b499a8dcc030c964", "000000001b58daf05a4cd46e601864b2",
|
|
"000000000dac6d782d266a37300c3259", "0000000006d636bc1693351b9806192c", "00000000036b1b5e0b499a8dcc030c96", "0000000001b58daf05a4cd46e601864b",
|
|
"0000000000dac6d782d266a37300c325", "00000000006d636bc1693351b9806192", "000000000036b1b5e0b499a8dcc030c9", "00000000001b58daf05a4cd46e601864",
|
|
"00000000000dac6d782d266a37300c32", "000000000006d636bc1693351b980619", "0000000000036b1b5e0b499a8dcc030c", "000000000001b58daf05a4cd46e60186",
|
|
"000000000000dac6d782d266a37300c3", "0000000000006d636bc1693351b98061", "00000000000036b1b5e0b499a8dcc030", "0000000000001b58daf05a4cd46e6018",
|
|
"0000000000000dac6d782d266a37300c", "00000000000006d636bc1693351b9806", "000000000000036b1b5e0b499a8dcc03", "00000000000001b58daf05a4cd46e601",
|
|
"00000000000000dac6d782d266a37300", "000000000000006d636bc1693351b980", "0000000000000036b1b5e0b499a8dcc0", "000000000000001b58daf05a4cd46e60",
|
|
"000000000000000dac6d782d266a3730", "0000000000000006d636bc1693351b98", "00000000000000036b1b5e0b499a8dcc", "0000000000000001b58daf05a4cd46e6",
|
|
"0000000000000000dac6d782d266a373", "00000000000000006d636bc1693351b9", "000000000000000036b1b5e0b499a8dc", "00000000000000001b58daf05a4cd46e",
|
|
"00000000000000000dac6d782d266a37", "000000000000000006d636bc1693351b", "0000000000000000036b1b5e0b499a8d", "000000000000000001b58daf05a4cd46",
|
|
"000000000000000000dac6d782d266a3", "0000000000000000006d636bc1693351", "00000000000000000036b1b5e0b499a8", "0000000000000000001b58daf05a4cd4",
|
|
"0000000000000000000dac6d782d266a", "00000000000000000006d636bc169335", "000000000000000000036b1b5e0b499a", "00000000000000000001b58daf05a4cd",
|
|
"00000000000000000000dac6d782d266", "000000000000000000006d636bc16933", "0000000000000000000036b1b5e0b499", "000000000000000000001b58daf05a4c",
|
|
"000000000000000000000dac6d782d26", "0000000000000000000006d636bc1693", "00000000000000000000036b1b5e0b49", "0000000000000000000001b58daf05a4",
|
|
"0000000000000000000000dac6d782d2", "00000000000000000000006d636bc169", "000000000000000000000036b1b5e0b4", "00000000000000000000001b58daf05a",
|
|
"00000000000000000000000dac6d782d", "000000000000000000000006d636bc16", "0000000000000000000000036b1b5e0b", "000000000000000000000001b58daf05",
|
|
"000000000000000000000000dac6d782", "0000000000000000000000006d636bc1", "00000000000000000000000036b1b5e0", "0000000000000000000000001b58daf0",
|
|
"0000000000000000000000000dac6d78", "00000000000000000000000006d636bc", "000000000000000000000000036b1b5e", "00000000000000000000000001b58daf",
|
|
"00000000000000000000000000dac6d7", "000000000000000000000000006d636b", "0000000000000000000000000036b1b5", "000000000000000000000000001b58da",
|
|
"000000000000000000000000000dac6d", "0000000000000000000000000006d636", "00000000000000000000000000036b1b", "0000000000000000000000000001b58d",
|
|
"0000000000000000000000000000dac6", "00000000000000000000000000006d63", "000000000000000000000000000036b1", "00000000000000000000000000001b58",
|
|
"00000000000000000000000000000dac", "000000000000000000000000000006d6", "0000000000000000000000000000036b", "000000000000000000000000000001b5",
|
|
"000000000000000000000000000000da", "0000000000000000000000000000006d", "00000000000000000000000000000036", "0000000000000000000000000000001b",
|
|
"0000000000000000000000000000000d", "00000000000000000000000000000006", "00000000000000000000000000000003", "00000000000000000000000000000001",
|
|
"00000000000000000000000000000000", "00000000000000000000000000000000", "00000000000000000000000000000000", "00000000000000000000000000000000",
|
|
"00000000000000000000000000000000", "00000000000000000000000000000000", "00000000000000000000000000000000", "00000000000000000000000000000000",
|
|
"00000000000000000000000000000000", "00000000000000000000000000000000", "00000000000000000000000000000000", "00000000000000000000000000000000",
|
|
]
|
|
|
|
for i in 0 ..< 128:
|
|
let str1 = toHex(e shr i)
|
|
let str2 = strArray[i]
|
|
doAssert str1 == str2
|
|
|
|
let strArray2 = [
|
|
"000dac6d782d266a37300c32591eee37", "001b58daf05a4cd46e601864b23ddc6e", "0036b1b5e0b499a8dcc030c9647bb8dc", "006d636bc1693351b9806192c8f771b8",
|
|
"00dac6d782d266a37300c32591eee370", "01b58daf05a4cd46e601864b23ddc6e0", "036b1b5e0b499a8dcc030c9647bb8dc0", "06d636bc1693351b9806192c8f771b80",
|
|
"0dac6d782d266a37300c32591eee3700", "1b58daf05a4cd46e601864b23ddc6e00", "36b1b5e0b499a8dcc030c9647bb8dc00", "6d636bc1693351b9806192c8f771b800",
|
|
"dac6d782d266a37300c32591eee37000", "b58daf05a4cd46e601864b23ddc6e000", "6b1b5e0b499a8dcc030c9647bb8dc000", "d636bc1693351b9806192c8f771b8000",
|
|
"ac6d782d266a37300c32591eee370000", "58daf05a4cd46e601864b23ddc6e0000", "b1b5e0b499a8dcc030c9647bb8dc0000", "636bc1693351b9806192c8f771b80000",
|
|
"c6d782d266a37300c32591eee3700000", "8daf05a4cd46e601864b23ddc6e00000", "1b5e0b499a8dcc030c9647bb8dc00000", "36bc1693351b9806192c8f771b800000",
|
|
"6d782d266a37300c32591eee37000000", "daf05a4cd46e601864b23ddc6e000000", "b5e0b499a8dcc030c9647bb8dc000000", "6bc1693351b9806192c8f771b8000000",
|
|
"d782d266a37300c32591eee370000000", "af05a4cd46e601864b23ddc6e0000000", "5e0b499a8dcc030c9647bb8dc0000000", "bc1693351b9806192c8f771b80000000",
|
|
"782d266a37300c32591eee3700000000", "f05a4cd46e601864b23ddc6e00000000", "e0b499a8dcc030c9647bb8dc00000000", "c1693351b9806192c8f771b800000000",
|
|
"82d266a37300c32591eee37000000000", "05a4cd46e601864b23ddc6e000000000", "0b499a8dcc030c9647bb8dc000000000", "1693351b9806192c8f771b8000000000",
|
|
"2d266a37300c32591eee370000000000", "5a4cd46e601864b23ddc6e0000000000", "b499a8dcc030c9647bb8dc0000000000", "693351b9806192c8f771b80000000000",
|
|
"d266a37300c32591eee3700000000000", "a4cd46e601864b23ddc6e00000000000", "499a8dcc030c9647bb8dc00000000000", "93351b9806192c8f771b800000000000",
|
|
"266a37300c32591eee37000000000000", "4cd46e601864b23ddc6e000000000000", "99a8dcc030c9647bb8dc000000000000", "3351b9806192c8f771b8000000000000",
|
|
"66a37300c32591eee370000000000000", "cd46e601864b23ddc6e0000000000000", "9a8dcc030c9647bb8dc0000000000000", "351b9806192c8f771b80000000000000",
|
|
"6a37300c32591eee3700000000000000", "d46e601864b23ddc6e00000000000000", "a8dcc030c9647bb8dc00000000000000", "51b9806192c8f771b800000000000000",
|
|
"a37300c32591eee37000000000000000", "46e601864b23ddc6e000000000000000", "8dcc030c9647bb8dc000000000000000", "1b9806192c8f771b8000000000000000",
|
|
"37300c32591eee370000000000000000", "6e601864b23ddc6e0000000000000000", "dcc030c9647bb8dc0000000000000000", "b9806192c8f771b80000000000000000",
|
|
"7300c32591eee3700000000000000000", "e601864b23ddc6e00000000000000000", "cc030c9647bb8dc00000000000000000", "9806192c8f771b800000000000000000",
|
|
"300c32591eee37000000000000000000", "601864b23ddc6e000000000000000000", "c030c9647bb8dc000000000000000000", "806192c8f771b8000000000000000000",
|
|
"00c32591eee370000000000000000000", "01864b23ddc6e0000000000000000000", "030c9647bb8dc0000000000000000000", "06192c8f771b80000000000000000000",
|
|
"0c32591eee3700000000000000000000", "1864b23ddc6e00000000000000000000", "30c9647bb8dc00000000000000000000", "6192c8f771b800000000000000000000",
|
|
"c32591eee37000000000000000000000", "864b23ddc6e000000000000000000000", "0c9647bb8dc000000000000000000000", "192c8f771b8000000000000000000000",
|
|
"32591eee370000000000000000000000", "64b23ddc6e0000000000000000000000", "c9647bb8dc0000000000000000000000", "92c8f771b80000000000000000000000",
|
|
"2591eee3700000000000000000000000", "4b23ddc6e00000000000000000000000", "9647bb8dc00000000000000000000000", "2c8f771b800000000000000000000000",
|
|
"591eee37000000000000000000000000", "b23ddc6e000000000000000000000000", "647bb8dc000000000000000000000000", "c8f771b8000000000000000000000000",
|
|
"91eee370000000000000000000000000", "23ddc6e0000000000000000000000000", "47bb8dc0000000000000000000000000", "8f771b80000000000000000000000000",
|
|
"1eee3700000000000000000000000000", "3ddc6e00000000000000000000000000", "7bb8dc00000000000000000000000000", "f771b800000000000000000000000000",
|
|
"eee37000000000000000000000000000", "ddc6e000000000000000000000000000", "bb8dc000000000000000000000000000", "771b8000000000000000000000000000",
|
|
"ee370000000000000000000000000000", "dc6e0000000000000000000000000000", "b8dc0000000000000000000000000000", "71b80000000000000000000000000000",
|
|
"e3700000000000000000000000000000", "c6e00000000000000000000000000000", "8dc00000000000000000000000000000", "1b800000000000000000000000000000",
|
|
"37000000000000000000000000000000", "6e000000000000000000000000000000", "dc000000000000000000000000000000", "b8000000000000000000000000000000",
|
|
"70000000000000000000000000000000", "e0000000000000000000000000000000", "c0000000000000000000000000000000", "80000000000000000000000000000000",
|
|
]
|
|
|
|
for i in 0 ..< 128:
|
|
let str1 = toHex(e shl i)
|
|
let str2 = strArray2[i]
|
|
doAssert str1 == str2
|