u128.fz
# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation. If not, see <https://www.gnu.org/licenses/>.
# -----------------------------------------------------------------------
#
# Tokiwa Software GmbH, Germany
#
# Source code of Fuzion standard library feature u128
#
# Author: Fridtjof Siebert (siebert@tokiwa.software)
#
# -----------------------------------------------------------------------
# u128 -- 128-bit unsigned integer values
#
public u128(public hi u64, public lo u64) : num.wrap_around, has_interval is
public thiz => u128 hi lo
# overflow checking
# would negation -thiz cause an overflow?
redef wrapped_on_neg => !is_zero
# would addition thiz + other cause an overflow or underflow?
public fixed overflow_on_add (other u128) => u128.max -° thiz < other
public fixed underflow_on_add(other u128) => false
# would subtraction thiz - other cause an overflow or underflow?
public fixed overflow_on_sub (other u128) => false
public fixed underflow_on_sub(other u128) => thiz < other
# would multiplication thiz * other cause an overflow or underflow?
public fixed overflow_on_mul (other u128) => if (other = u128.zero) false else (thiz *° other / other) != thiz
public fixed underflow_on_mul(other u128) => false
# neg, add, sub, mul with wrap-around semantics
public fixed prefix -° u128 => carry u64 := { if (lo > u64 0 ) 1 else 0 }; u128 (u64 0 -° hi -° carry) (u64 0 -° lo)
public fixed infix +° (other u128) u128 => carry u64 := { if (lo +° other.lo < lo) 1 else 0 }; u128 (hi +° other.hi +° carry) (lo +° other.lo)
public fixed infix -° (other u128) u128 => carry u64 := { if (lo < other.lo ) 1 else 0 }; u128 (hi -° other.hi -° carry) (lo -° other.lo)
public fixed infix *° (other u128) u128 =>
a0 := lo & 0x_ffff_ffff
a1 := lo >> 32
a2 := hi & 0x_ffff_ffff
a3 := hi >> 32
b0 := other.lo & 0x_ffff_ffff
b1 := other.lo >> 32
b2 := other.hi & 0x_ffff_ffff
b3 := other.hi >> 32
p00 := a0*b0
p10 := a1*b0
p01 := a0*b1
p20 := a2*b0
p11 := a1*b1
p02 := a0*b2
p30 := a3*b0
p21 := a2*b1
p12 := a1*b2
p03 := a0*b3
(u128 0 p00 +°
u128 p10>>32 p10<<32 +°
u128 p01>>32 p01<<32 +°
u128 p20 0 +°
u128 p11 0 +°
u128 p02 0 +°
u128 p30<<32 0 +°
u128 p21<<32 0 +°
u128 p12<<32 0 +°
u128 p03<<32 0 )
# division and remainder with check for div-by-zero
public fixed infix / (other u128)
pre
safety: other != u128.zero
=> div other
public fixed infix % (other u128)
pre
safety: other != u128.zero
=> mod other
# private division and remainder with crash in case of div-by-zero
private div (other u128) u128 =>
if thiz < other
u128.zero
else
ob := other.highest_one_bit.trailing_zeros
for
rem := thiz, rem - s
bit := rem.highest_one_bit >> ob.as_u128, bit >> u128.one
d := other << bit.trailing_zeros.as_u128, d >> u128.one
s := if (rem < d) u128.zero else d
p := if (rem < d) u128.zero else bit
res := p, res + p
until bit = u128.zero
check
debug: res *° other + rem = thiz
res
private mod (other u128) u128 =>
thiz - (div other) *° other
# bitwise and, or and xor operations
public fixed infix & (other u128) u128 => u128 (hi & other.hi) (lo & other.lo)
public fixed infix | (other u128) u128 => u128 (hi | other.hi) (lo | other.lo)
public fixed infix ^ (other u128) u128 => u128 (hi ^ other.hi) (lo ^ other.lo)
# shift operations (unsigned)
public fixed infix >> (other u128) u128 =>
n := other.as_u64 # NYI: other should be of type u32
if n ≥ u64 128
u128 0 0
else if n ≥ u64 64
u128 0 (hi >> (n - 64))
else if n > u64 0
u128 (hi >> n) ((lo >> n) | (hi << (u64 64 - n)))
else
thiz
public fixed infix << (other u128) u128 =>
n := other.as_u64 # NYI: other should be of type u32
if n ≥ u64 128
u128 0 0
else if n ≥ u64 64
u128 (lo << (n-64)) 0
else if n > u64 0
u128 ((hi << n) | (lo >> (u64 64 - n))) (lo << n)
else
thiz
# equality
#
fixed type.equality(a, b u128) =>
a.hi = b.hi && a.lo = b.lo
# total order
#
fixed type.lteq(a, b u128) =>
a.hi < b.hi || (a.hi = b.hi) && (a.lo ≤ b.lo)
public as_i8 i8
pre
thiz ≤ i8.max.as_u128
=>
lo.as_i8
public as_i16 i16
pre
thiz ≤ i16.max.as_u128
=>
lo.as_i16
public as_i32 i32
pre
thiz ≤ i32.max.as_u128
=>
lo.as_i32
public as_i64 i64
pre
thiz ≤ i64.max.as_u128
post
analysis: result.as_u128 = thiz
=>
lo.as_i64
public as_u8 u8
pre
thiz ≤ u8.max.as_u128
post
analysis: result.as_u128 = thiz
=>
lo.as_u8
public as_u16 u16
pre
thiz ≤ u16.max.as_u128
post
analysis: result.as_u128 = thiz
=>
lo.as_u16
public as_u32 u32
pre
thiz ≤ u32.max.as_u128
post
analysis: result.as_u128 = thiz
=>
lo.as_u32
public as_u64 u64
pre
thiz ≤ u64.max.as_u128
post
analysis: result.as_u128 = thiz
=>
lo
public low8bits u8 => lo.low8bits
public low16bits u16 => lo.low16bits
public low32bits u32 => lo.low32bits
public low64bits u64 => lo
# create hash code from this number
public type.hash_code(a u128.this) u64 =>
a.hi ^ a.lo
# find the highest 1 bit in this integer and return integer with
# this single bit set or 0 if this is 0.
#
public highest_one_bit u128 =>
if hi = u64 0
u128 0 lo.highest_one_bit
else
u128 hi.highest_one_bit 0
# count the number of trailing zeros in this integer.
#
public trailing_zeros i32 =>
if lo = u64 0
64 + hi.trailing_zeros
else
lo.trailing_zeros
# count the number of 1 bits in the binary representation of this
# integer.
#
public ones_count i32 =>
hi.ones_count + lo.ones_count
# returns the number in whose bit representation all bits are ones
fixed redef type.all_bits_set => u128 0x_ffff_ffff_ffff_ffff 0x_ffff_ffff_ffff_ffff
# minimum
#
public fixed type.min => u128 0 0
# maximum
#
public fixed type.max => u128 0x_ffff_ffff_ffff_ffff 0x_ffff_ffff_ffff_ffff
# identity element for 'infix +'
#
public fixed type.zero => u128 0 0
# identity element for 'infix *'
#
public fixed type.one => u128 0 1
