Last active
July 16, 2018 18:31
-
-
Save countingpine/a4f463e19fd879a33ff7088efd313484 to your computer and use it in GitHub Desktop.
uintT.bas - UDT to represent an unsigned integer twice as large as the given type. Mainly intended for 128 bits, but designed to accommodate smaller types for easier testing.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| '' FT = full type (doesn't always exist) | |
| '' HT = half type (make up the two halves of the number) | |
| '' QT = quarter type (used for multiplication) | |
| '' 32 / 16 / 8 | |
| 'type FT as ulong | |
| 'type HT as ushort | |
| 'type QT as ubyte | |
| '' 64 / 32 / 16 | |
| 'type FT as ulongint | |
| 'type HT as ulong | |
| 'type QT as ushort | |
| '' [128] / 64 / 32 | |
| 'type FT as ... | |
| type HT as ulongint | |
| type QT as ulong | |
| '' macros for splitting up HT into QT halves | |
| #define HT_LO(n) (cast(QT, (n))) | |
| #define HT_HI(n) (cast(QT, (n) shl QW)) | |
| '' Bit width of types | |
| '' FW/HW/QW = full width / half width / quarter width | |
| const FW = sizeof(HT) * 8 * 2 | |
| const HW = FW \ 2 | |
| const QW = HW \ 2 | |
| #macro RETURNS_VAL(expr) | |
| #ifdef FT | |
| return (expr) | |
| #endif | |
| #endmacro | |
| #define RETURNS(expr) RETURNS_VAL( tofull(expr) ) | |
| #macro DOES(stmt) | |
| #ifdef FT | |
| stmt | |
| return | |
| #endif | |
| #endmacro | |
| type uintT | |
| as HT lo, hi | |
| end type | |
| #ifdef FT | |
| function tofull(a as FT) as uintT | |
| dim as uintT ret | |
| ret.lo = cast(HT, a) | |
| ret.hi = a shr HW | |
| return ret | |
| end function | |
| function full(a as const uintT) as FT | |
| return a.lo or cast(FT, a.hi) shl HW | |
| end function | |
| #endif | |
| function CT(lo as HT, hi as HT = 0) as uintT | |
| dim ret as uintT | |
| ret.lo = lo: ret.hi = hi | |
| return ret | |
| end function | |
| function debug(a as const uintT) as string | |
| if a.hi = 0 then return str(a.lo) | |
| return "(" & str(a.hi) & " << " & HW & ") + " & str(a.lo) | |
| end function | |
| function add(a as const uintT, b as const uintT) as uintT | |
| RETURNS( full(a) + full(b) ) | |
| #define ADD_OVERFLOW(a, b) (cast(typeof(a), (a) + (b)) < (a)) | |
| if ADD_OVERFLOW(a.lo, b.lo) then | |
| return CT(a.lo + b.lo, a.hi + b.hi + 1) | |
| else | |
| return CT(a.lo + b.lo, a.hi + b.hi) | |
| end if | |
| end function | |
| function subtract(a as const uintT, b as const uintT) as uintT | |
| RETURNS( full(a) - full(b) ) | |
| #define SUB_OVERFLOW(a, b) (cast(typeof(a), (a) - (b)) > (a)) | |
| if SUB_OVERFLOW(a.lo, b.lo) then | |
| return CT(a.lo - b.lo, a.hi - b.hi - 1) | |
| else | |
| return CT(a.lo - b.lo, a.hi - b.hi) | |
| end if | |
| end function | |
| sub add_to(byref a as uintT, b as const uintT) | |
| DOES( a = tofull(full(a) + full(b)) ) | |
| #define ADD_OVERFLOW(a, b) (cast(typeof(a), (a) + (b)) < (a)) | |
| if ADD_OVERFLOW(a.lo, b.lo) then a.hi += 1 | |
| a.lo += b.lo | |
| a.hi += b.hi | |
| end sub | |
| sub subtract_from(byref a as uintT, b as const uintT) | |
| DOES( a = tofull(full(a) - full(b)) ) | |
| #define SUB_OVERFLOW(a, b) ((a) < (b)) | |
| if SUB_OVERFLOW(a.lo, b.lo) then a.hi -= 1 | |
| a.lo -= b.lo | |
| a.hi -= b.hi | |
| end sub | |
| function multiply_HT(a as HT, b as HT) as uintT | |
| RETURNS( cast(FT, a) * b ) | |
| dim as QT al = cast(QT, a), ah = cast(QT, a shr QW) | |
| dim as QT bl = cast(QT, b), bh = cast(QT, b shr QW) | |
| dim as HT lo = cast(HT, al) * bl | |
| dim as HT m1 = cast(HT, al) * bh | |
| dim as HT m2 = cast(HT, ah) * bl | |
| dim as HT hi = cast(HT, ah) * bh | |
| lo += cast(HT, m1 shl QW): if lo < cast(HT, m1 shl QW) then hi += 1 | |
| lo += cast(HT, m2 shl QW): if lo < cast(HT, m2 shl QW) then hi += 1 | |
| hi += cast(HT, m1 shr QW) | |
| hi += cast(HT, m2 shr QW) | |
| return CT(lo, hi) | |
| end function | |
| function shift(a as const uintT, b as integer) as uintT | |
| RETURNS( full(a) shl b ) | |
| 'return cheat(grab(a) shl b) | |
| if b = 0 then | |
| return a | |
| elseif b = HW then | |
| return CT(0, a.lo) | |
| elseif b < HW then | |
| return CT(a.lo shl b, a.hi shl b or a.lo shr (HW - b)) | |
| else | |
| return CT(0, a.lo shl (b - HW)) | |
| end if | |
| end function | |
| function rshift(a as const uintT, b as integer) as uintT | |
| RETURNS( full(a) shr b ) | |
| if b = 0 then | |
| return a | |
| elseif b = HW then | |
| return CT(a.hi, 0) | |
| elseif b < HW then | |
| return CT(a.lo shr b or a.hi shl (HW - b), a.hi shr b) | |
| else | |
| return CT(a.hi shr (b - HW), 0) | |
| end if | |
| end function | |
| function pow2(b as integer) as uintT | |
| RETURNS( cast(FT, 1) shl b ) | |
| if b < HW then | |
| return CT(1ull shl b, 0) | |
| else | |
| return CT(0, 1ull shl (b - HW)) | |
| end if | |
| end function | |
| function multiply(a as const uintT, b as const uintT) as uintT | |
| RETURNS( full(a) * full(b) ) | |
| dim as uintT ret = multiply_HT(a.lo, b.lo) | |
| ret.hi += (a.lo * b.hi) | |
| ret.hi += (a.hi * b.lo) | |
| return ret | |
| end function | |
| function cmp(a as const uintT, b as const uintT) as integer | |
| RETURNS_VAL( iif(full(a) >= full(b), sgn(full(a) - full(b)), -1) ) | |
| if a.hi > b.hi then return 1 | |
| if a.hi < b.hi then return -1 | |
| if a.lo > b.lo then return 1 | |
| if a.lo < b.lo then return -1 | |
| return 0 | |
| end function | |
| function less(a as const uintT, b as const uintT) as integer | |
| return cmp(a, b) < 0 | |
| end function | |
| function gtr(a as const uintT, b as const uintT) as integer | |
| return cmp(a, b) > 0 | |
| end function | |
| function leq(a as const uintT, b as const uintT) as integer | |
| return cmp(a, b) <= 0 | |
| end function | |
| function geq(a as const uintT, b as const uintT) as integer | |
| return cmp(a, b) >= 0 | |
| end function | |
| function equal(a as const uintT, b as const uintT) as integer | |
| return cmp(a, b) = 0 | |
| end function | |
| function neq(a as const uintT, b as const uintT) as integer | |
| return cmp(a, b) <> 0 | |
| end function | |
| sub divmod(a as const uintT, b as const uintT, byref quo_ as uintT, byref rmdr_ as uintT) | |
| DOES( quo_ = tofull(full(a) \ full(b)) : _ | |
| rmdr_ = tofull(full(a) mod full(b)) ) | |
| dim as uintT quo = (0, 0), rmdr = a | |
| dim as uintT test = b | |
| assert(equal(add(multiply(b, quo), rmdr), a)) | |
| dim as integer i = 0 | |
| while i < FW and less(test, a) and less(test, pow2(FW-1)) | |
| i += 1 | |
| test = shift(test, 1) | |
| wend | |
| if gtr(test, a) and i > 0 then i -= 1: test = rshift(test, 1) | |
| assert(leq(test, a) orelse gtr(b, a)) | |
| while i >= 0 | |
| if geq(rmdr, test) then | |
| subtract_from rmdr, test | |
| assert(less(rmdr, test)) | |
| add_to quo, pow2(i) | |
| assert(equal(add(multiply(b, quo), rmdr), a)) | |
| end if | |
| test = rshift(test, 1) | |
| i -= 1 | |
| wend | |
| assert(less(rmdr, shift(b, 0))) | |
| assert(equal(add(multiply(b, quo), rmdr), a)) | |
| assert(less(rmdr, b)) | |
| quo_ = quo | |
| rmdr_ = rmdr | |
| end sub | |
| function divide(a as const uintT, b as const uintT) as uintT | |
| RETURNS( full(a) \ full(b) ) | |
| dim as uintT quo, rmdr | |
| divmod(a, b, quo, rmdr) | |
| return quo | |
| end function | |
| function base10(a as const uintT) as string | |
| RETURNS_VAL( str(full(a)) ) | |
| dim as string ret | |
| dim as const uintT TEN = (10, 0) | |
| dim as uintT tmp = a | |
| dim as uintT dig | |
| while tmp.lo <> 0 or tmp.hi <> 0 | |
| divmod(tmp, TEN, tmp, dig) | |
| ret = dig.lo & ret | |
| wend | |
| return ret | |
| end function | |
| function from_base10(a as const string) as uintT | |
| dim ret as uintT = CT(0) | |
| for i as integer = 0 to len(a) - 1 | |
| select case a[i] | |
| case asc("0") to asc("9") | |
| ret = multiply(ret, CT(10)) | |
| add_to ret, CT(a[i] - asc("0")) | |
| case else | |
| exit for | |
| end select | |
| next i | |
| return ret | |
| end function |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.