diff --git a/basis/IntInf.sml b/basis/IntInf.sml index 7fb3d095..2324b6ce 100644 --- a/basis/IntInf.sml +++ b/basis/IntInf.sml @@ -1,140 +1,149 @@ (* Title: Standard Basis Library: IntInf structure and signature. Copyright David Matthews 2000, 2016-17, 2023 This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation. This library 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 Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA *) signature INT_INF = sig include INTEGER val divMod : int * int -> int * int val quotRem : int * int -> int * int val pow : int * Int.int -> int val log2 : int -> Int.int val orb : int * int -> int val xorb : int * int -> int val andb : int * int -> int val notb : int -> int val << : int * Word.word -> int val ~>> : int * Word.word -> int end; structure IntInf : INT_INF = struct type int = LargeInt.int + val largeIntToWord: int -> word = RunCall.unsafeCast (* Masked out by signature *) + val quotRem = LibrarySupport.quotRem fun divMod (x, y) = let val (q, r) = quotRem(x, y) in (* If the remainder is zero or the same sign as the divisor then the result is the same as quotRem. Otherwise round down the quotient and round up the remainder. *) if r = 0 orelse (r < 0) = (y < 0) then (q, r) else (q-1, r+y) end (* Return the position of the highest bit set in the value. *) local val log2Long: int -> Int.int = RunCall.rtsCallFast1 "PolyLog2Arbitrary"; in fun log2 (i: int) : Int.int = if i <= 0 then raise Domain else if LibrarySupport.largeIntIsSmall i - then Word.toInt(LibrarySupport.log2Word(Word.fromLargeInt i)) + then Word.toInt(LibrarySupport.log2Word(largeIntToWord i)) else log2Long i end local (* These are implemented in the RTS. *) val orbFn : int * int -> int = RunCall.rtsCallFull2 "PolyOrArbitrary" and xorbFn : int * int -> int = RunCall.rtsCallFull2 "PolyXorArbitrary" and andbFn : int * int -> int = RunCall.rtsCallFull2 "PolyAndArbitrary" open LibrarySupport - val largeIntToWord: int -> word = RunCall.unsafeCast in (* Handle the short cases using the word operations. The special cases of or-ing with a short negative value and and-ing with a short positive also always produce short results but extracting the low-order word from the long-format argument involves an RTS call so it's not worthwhile. *) fun orb(i, j) = if largeIntIsSmall i andalso largeIntIsSmall j then Word.toLargeIntX(Word.orb(largeIntToWord i, largeIntToWord j)) else orbFn(i, j) fun andb(i, j) = if largeIntIsSmall i andalso largeIntIsSmall j then Word.toLargeIntX(Word.andb(largeIntToWord i, largeIntToWord j)) else andbFn(i, j) fun xorb(i, j) = if largeIntIsSmall i andalso largeIntIsSmall j then Word.toLargeIntX(Word.xorb(largeIntToWord i, largeIntToWord j)) else xorbFn(i, j) end (* notb is defined as ~ (i+1) and there doesn't seem to be much advantage in implementing it any other way. *) fun notb i = ~(i + 1) local fun power(acc: LargeInt.int, _, 0w0) = acc | power(acc, n, i) = power( if Word.andb(i, 0w1) = 0w1 then acc * n else acc, n * n, Word.>>(i, 0w1) ) in fun pow(i: LargeInt.int, j: Int.int) = if j < 0 then(* Various exceptional cases. *) ( if i = 0 then raise Div else if i = 1 then 1 else if i = ~1 then if Int.rem(j, 2) = 0 then (*even*) 1 else (*odd*) ~1 else 0 ) else if LibrarySupport.isShortInt j then power(1, i, Word.fromInt j) else (* Long: This is possible only if int is arbitrary precision. If the value to be multiplied is anything other than 0 or 1 we'll exceed the maximum size of a cell. *) if i = 0 then 0 else if i = 1 then 1 else raise Size end local val shiftR: LargeInt.int * word -> LargeInt.int = RunCall.rtsCallFull2 "PolyShiftRightArbitrary" and shiftL: LargeInt.int * word -> LargeInt.int = RunCall.rtsCallFull2 "PolyShiftLeftArbitrary" + val maxShortShift = LibrarySupport.wordSize * 0w8 - 0w2 in - val << = shiftL + fun << (i: int, j: Word.word) = + (* We can use a word shift provided the value is short and will not shift any bits out or + into the sign bit. This will only work for positive integers. It would be possible + to use this for negative integers by negating the argument and the result. *) + if i = 0 orelse j = 0w0 then i + else if LibrarySupport.largeIntIsSmall i andalso LibrarySupport.log2Word(largeIntToWord i) + j < maxShortShift + then Word.toLargeIntX(Word.<<(largeIntToWord i, j)) + else shiftL(i, j) fun ~>> (i: int, j: Word.word) = if LibrarySupport.largeIntIsSmall i - then Word.toLargeIntX(Word.~>>(Word.fromLargeInt i, j)) + then Word.toLargeIntX(Word.~>>(largeIntToWord i, j)) else shiftR(i, j) end open LargeInt (* Inherit everything from LargeInt. Do this last because it overrides the overloaded functions. *) end; diff --git a/basis/LibrarySupport.sml b/basis/LibrarySupport.sml index d3c5b166..a4e1fc49 100644 --- a/basis/LibrarySupport.sml +++ b/basis/LibrarySupport.sml @@ -1,238 +1,238 @@ (* Title: Standard Basis Library: Support functions Copyright David C.J. Matthews 2000, 2015-20, 2023 This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License version 2.1 as published by the Free Software Foundation. This library 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 Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA *) (* We need to execute these calls BEFORE compiling LibrarySupport if we want them to be compiled in as constants. *) structure MachineConstants = struct local val isBigEndian: unit -> bool = RunCall.rtsCallFast1 "PolyIsBigEndian" in val bigEndian : bool = isBigEndian () end val wordSize : word = RunCall.bytesPerWord (* This is the same as wordSize in native 32-bit and 64-bit but different in 32-in-64. *) val sysWordSize: word = RunCall.memoryCellLength(Word.toLargeWord 0w0) * wordSize end; structure LibrarySupport :> sig eqtype address (* eqtype so we can compare vectors. *) structure CharArray: sig datatype array = Array of word*address end structure Word8Array: sig datatype array = Array of word*address eqtype vector val wVecLength: vector -> word end val w8vectorToString: Word8Array.vector -> string and w8vectorFromString: string -> Word8Array.vector val wordSize: word and sysWordSize: word val bigEndian: bool val allocString: word -> string (* Create a mutable string. *) val allocBytes: word -> address val isShortInt : int -> bool val largeIntIsSmall: LargeInt.int -> bool val unsignedShortOrRaiseSubscript: int -> word val unsignedShortOrRaiseSize: int -> word val sizeAsWord : string -> word val stringAsAddress : string -> address val w8vectorAsAddress : Word8Array.vector -> address val maxAllocation: word and maxString: word val emptyVector: word val quotRem: LargeInt.int*LargeInt.int -> LargeInt.int*LargeInt.int val getOSType: unit -> int eqtype syserror val syserrorToWord: syserror -> LargeWord.word val syserrorFromWord : LargeWord.word -> syserror exception SysErr of (string * syserror option) val onEntryList: (unit->unit) list ref (* This is picked up by InitialPolyML *) val addOnEntry: (unit->unit) -> unit val atExitList: (unit->unit) list ref (* This is picked up by OS.Process *) val addAtExit: (unit->unit) -> unit val volatileListRef: unit -> 'a list ref val volatileWordRef: unit -> word ref val volatileOptionRef: unit -> 'a option ref val log2Word: word -> word end = struct (* An address is the address of a vector in memory. *) type address = Bootstrap.byteArray (* This forces pointer equality. *) local (* Add a pretty printer to avoid crashes during debugging. *) open PolyML fun prettyAddress _ _ (_: address) = PolyML.PrettyString "byteArray" in val () = addPrettyPrinter prettyAddress end (* This is always a short non-negative integer so can be cast as word or int. *) fun sizeAsWord(s: string): word = RunCall.loadUntagged(s, 0w0) (* Provide the implementation of CharArray.array, Word8Array.array and Word8Array.vector (= Word8Vector.vector) here so that they are available to the IO routines. *) structure CharArray = struct datatype array = Array of word*address end structure Word8Array = struct (* Using the Array constructor here does not add any overhead since it is compiled as an identity function. *) datatype array = Array of word*address (* The representation of Word8Vector.vector is the same as that of string. We define it as "string" here so that it inherits the same equality function. The representation is assumed by the RTS. *) type vector = string val wVecLength: vector -> word = sizeAsWord end (* Identity functions to provide convertions. *) fun w8vectorToString s = s and w8vectorFromString s = s (* There are circumstances when we want to pass the address of a string where we expect an address. *) val stringAsAddress : string -> address = RunCall.unsafeCast val w8vectorAsAddress = stringAsAddress o w8vectorToString open MachineConstants; local val F_mutable_bytes : word = 0wx41 (* This is put in by Initialise and filtered out later. *) val setLengthWord: string * word -> unit = fn (s, n) => RunCall.storeUntagged(s, 0w0, n) val callGetAllocationSize = RunCall.rtsCallFast0 "PolyGetMaxAllocationSize" val callGetMaxStringSize = RunCall.rtsCallFast0 "PolyGetMaxStringSize" in (* Get the maximum allocation size. This is the maximum value that can fit in the length field of a segment. *) val maxAllocation = callGetAllocationSize() and maxString = callGetMaxStringSize() (* Check that we have a short int. This is only necessary if int is arbitrary precision. If int is fixed precision it will always be true. *) fun isShortInt(i: int): bool = not Bootstrap.intIsArbitraryPrecision orelse RunCall.isShort i (* Test whether a large int will fit in the short format. *) val largeIntIsSmall: LargeInt.int -> bool = RunCall.isShort fun unsignedShortOrRaiseSize (i: int): word = if isShortInt i andalso i >= 0 then RunCall.unsafeCast i else raise Size fun unsignedShortOrRaiseSubscript (i: int): word = if isShortInt i andalso i >= 0 then RunCall.unsafeCast i else raise Subscript fun allocBytes bytes : address = let val words : word = if bytes > maxString then raise Size (* The maximum string size is slightly smaller than the maximum array size because strings have a length word. It seems best to use the same maximum size for CharArray/Word8Array. *) else (bytes + wordSize - 0w1) div wordSize val mem = RunCall.allocateByteMemory(words, F_mutable_bytes) (* Zero the last word. *) val () = if words = 0w0 then () else RunCall.storeUntagged(RunCall.unsafeCast mem, words-0w1, 0w0) in mem end (* Allocate store for the string and set the first word to contain the length and the rest zero. *) fun allocString charsW = let (* The space is the number of characters plus space for the length word plus rounding. *) val words : word = (charsW + 0w2 * wordSize - 0w1) div wordSize val _ = words <= maxAllocation orelse raise Size val vec = RunCall.allocateByteMemory(words, F_mutable_bytes) (* Zero any extra bytes we've needed for rounding to a number of words. This isn't essential but ensures that RTS sharing passes will merge strings that are otherwise the same. *) val () = RunCall.storeUntagged(vec, words-0w1, 0w0) in (* Set the length word. Since this is untagged we can't simply use assign_word.*) setLengthWord(vec, charsW); vec end (* Volatile refs. They are cleared to 0/nil/NONE in an exported or saved state and their current value is not written to a child state, unlike normal refs. They are used for things like mutexes, condition variables and the list of currently open streams which should always be reset. *) local fun volatileRef() : 'a ref = RunCall.allocateWordMemory(0w1, 0wx48, 0w0) in val volatileListRef = volatileRef and volatileWordRef = volatileRef and volatileOptionRef = volatileRef end end (* Create an empty vector. This is used wherever we want an empty vector. It can't be 'a vector which is what we want because of the value restriction. *) val emptyVector: word = RunCall.allocateWordMemory(0w0, 0w0, 0w0) val quotRem = LargeInt.quotRem val getOSType: unit -> int = RunCall.rtsCallFast0 "PolyGetOSType" (* syserror is the same as SysWord.word and these are needed in Posix at least. *) type syserror = LargeWord.word fun syserrorToWord i = i and syserrorFromWord i = i exception SysErr = RunCall.SysErr (* The onEntry list. PolyML.onEntry adds a mutex here. *) val onEntryList: (unit->unit) list ref = ref[] fun addOnEntry f = onEntryList := f :: !onEntryList (* The atExit list - This is a volatile since it should be reset at the start, unlike the onEntry list. *) val atExitList = volatileListRef() fun addAtExit f = atExitList := f :: !atExitList - (* This is needed in IntInf so nees to be captured before LargeInt is redefined. *) + (* This is needed in IntInf so needs to be captured before LargeInt is redefined. *) val log2Word = LargeInt.log2Word end;