Fuzion Logo
flang.dev — The Fuzion Language Portal
JavaScript seems to be disabled. Functionality is limited.

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
#
u128(hi, lo u64) : wrappingInteger<u128>, hasInterval<u128>, u128s is

  #  redef thiz => u128.this  -- NYI: This causes a type error when using C backend
  redef thiz => u128 hi lo

  # overflow checking

  # would negation -thiz cause an overflow?
  redef wrappedOnNeg => !isZero

  # would addtion thiz + other cause an overflow or underflow?
  redef overflowOnAdd (other u128) => max -° thiz < other
  redef underflowOnAdd(other u128) => false

  # would subtraction thiz - other cause an overflow or underflow?
  redef overflowOnSub (other u128) => false
  redef underflowOnSub(other u128) => thiz < other

  # would multiplication thiz * other cause an overflow or underflow?
  redef overflowOnMul (other u128) => if (other = zero) false else (thiz *° other / other) != thiz
  redef underflowOnMul(other u128) => false

  # neg, add, sub, mul with wrap-around semantics
  redef prefix -°             u128 is carry u64 := { if (lo > 0             ) 1 else 0 }; u128 (u64 0 -° hi -° carry) (u64 0 -° lo)
  redef infix +° (other u128) u128 is carry u64 := { if (lo +° other.lo < lo) 1 else 0 }; u128 (hi +° other.hi +° carry) (lo +° other.lo)
  redef infix -° (other u128) u128 is carry u64 := { if (lo < other.lo      ) 1 else 0 }; u128 (hi -° other.hi -° carry) (lo -° other.lo)
  redef infix *° (other u128) u128 is
    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
  redef infix / (other u128)
    pre
      safety: other != zero
   => div other
  redef infix %  (other u128)
    pre
      safety: other != zero
   => mod other

  # private division and remainder with crash in case of div-by-zero
  private div (other u128) u128 is
    if thiz < other
      zero
    else
      ob := other.highestOneBit.trailingZeros
      for
        rem := thiz, rem - s
        bit := rem.highestOneBit >> ob.as_u128, bit >> one
        d := other << bit.trailingZeros.as_u128, d >> one
        s := if (rem < d) zero else d
        p := if (rem < d) zero else bit
        res := p, res + p
      until bit = zero
        check
          debug: res *° other + rem = thiz
        res

  private mod (other u128) u128 is
    thiz - div(other) *° other

  # bitwise and, or and xor operations
  redef infix &  (other u128) u128 is u128 (hi & other.hi) (lo & other.lo)
  redef infix |  (other u128) u128 is u128 (hi | other.hi) (lo | other.lo)
  redef infix ^  (other u128) u128 is u128 (hi ^ other.hi) (lo ^ other.lo)

  # shift operations (unsigned)
  redef infix >> (other u128) u128 is
    n := other.as_u64  # NYI: other should be of type u32
    if n >= 128
      u128 0 0
    else if n >= 64
      u128 0 (hi >> (n - 64))
    else if n > 0
      u128 (hi >> n) ((lo >> n) | (hi << (u64 64 - n)))
    else
      thiz

  redef infix << (other u128) u128 is
    n := other.as_u64  # NYI: other should be of type u32
    if n >= 128
      u128 0 0
    else if n >= 64
      u128 (lo << (n-64)) 0
    else if n > 0
      u128 ((hi << n) | (lo >> (u64 64 - n))) (lo << n)
    else
      thiz

  # comparison
  redef infix == (other u128) bool is hi == other.hi && lo == other.lo
  redef infix != (other u128) bool is !(thiz == other)
  redef infix <  (other u128) bool is hi < other.hi || hi = other.hi && lo <  other.lo
  redef infix <= (other u128) bool is hi < other.hi || hi = other.hi && lo <= other.lo
  redef infix >  (other u128) bool is hi > other.hi || hi = other.hi && lo >  other.lo
  redef infix >= (other u128) bool is hi > other.hi || hi = other.hi && lo >= other.lo

  redef infix =  (other u128) bool is hi = other.hi && lo = other.lo
  redef infix /= (other u128) bool is !(thiz = other)

  as_i8 i8
    pre
      thiz <= i8.max.as_u128
    is
      lo.as_i8
  as_i16 i16
    pre
      thiz <= i16.max.as_u128
    is
      lo.as_i16
  as_i32 i32
    pre
      thiz <= i32.max.as_u128
    is
      lo.as_i32
  as_i64 i64
    pre
      thiz <= i64.max.as_u128
    post
      analysis: result.as_u128 = thiz
    is
      lo.as_i64
  as_u8 u8
    pre
      thiz <= u8.max.as_u128
    post
      analysis: result.as_u128 = thiz
    is
      lo.as_u8
  as_u16 u16
    pre
      thiz <= u16.max.as_u128
    post
      analysis: result.as_u128 = thiz
    is
      lo.as_u16
  as_u32 u32
    pre
      thiz <= u32.max.as_u128
    post
      analysis: result.as_u128 = thiz
    is
      lo.as_u32
  as_u64 u64
    pre
      thiz <= u64.max.as_u128
    post
      analysis: result.as_u128 = thiz
    is
      lo

  low8bits  u8  is lo.low8bits
  low16bits u16 is lo.low16bits
  low32bits u32 is lo.low32bits
  low64bits u64 is lo

  # NYI: max is redefined here only to solve repeated inheritance conflict. Since max inherited
  # from hasInterval is abstract, fz should not complain about this conflict.
  redef max => u128 0x_ffff_ffff_ffff_ffff 0x_ffff_ffff_ffff_ffff


  # create hash code from this number
  hash u64 is
    hi ^ lo


  # find the highest 1 bit in this integer and return integer with
  # this single bit set or 0 if this is 0.
  #
  highestOneBit u128 is
    if hi = 0
      u128 0 lo.highestOneBit
    else
      u128 hi.highestOneBit 0


  # count the number of trailing zeros in this integer.
  #
  trailingZeros i32 is
    if lo = 0
      64 + hi.trailingZeros
    else
      lo.trailingZeros


  # count the number of 1 bits in the binary representation of this
  # integer.
  #
  onesCount i32 is
    hi.onesCount + lo.onesCount


# u128s -- unit type defining features related to u128 but not requiring an
# instance
#
u128s : wrappingIntegers<u128> is

  redef name => "u128"

  redef zero => u128 0 0
  redef one  => u128 0 1

  redef min => u128 0 0
  redef max => u128 0x_ffff_ffff_ffff_ffff 0x_ffff_ffff_ffff_ffff


# u128 -- returns value of unit type u128s
#
# This is a convenience feature that allows using, e.g., 'u128.sum' to
# get the the monoid of (u128, infix +) instead of 'u128s.sum'.
#
# since this u128 with no arguments is a routine and not a constructor, it
# does not define a type (which would cause a name clash with u128 with one
# argument).
#
u128 => u128s