1(* 2 Title: Standard Basis Library: IntInf structure and signature. 3 Copyright David Matthews 2000, 2016-17 4 5 This library is free software; you can redistribute it and/or 6 modify it under the terms of the GNU Lesser General Public 7 License version 2.1 as published by the Free Software Foundation. 8 9 This library is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 12 Lesser General Public License for more details. 13 14 You should have received a copy of the GNU Lesser General Public 15 License along with this library; if not, write to the Free Software 16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 17*) 18signature INT_INF = 19sig 20 include INTEGER 21 val divMod : int * int -> int * int 22 val quotRem : int * int -> int * int 23 val pow : int * Int.int -> int 24 val log2 : int -> Int.int 25 val orb : int * int -> int 26 val xorb : int * int -> int 27 val andb : int * int -> int 28 val notb : int -> int 29 val << : int * Word.word -> int 30 val ~>> : int * Word.word -> int 31end; 32 33structure IntInf : INT_INF = 34struct 35 type int = LargeInt.int 36 37 val quotRem = LibrarySupport.quotRem 38 39 fun divMod (x, y) = 40 let 41 val (q, r) = quotRem(x, y) 42 in 43 (* If the remainder is zero or the same sign as the 44 divisor then the result is the same as quotRem. 45 Otherwise round down the quotient and round up the remainder. *) 46 if r = 0 orelse (r < 0) = (y < 0) 47 then (q, r) 48 else (q-1, r+y) 49 end 50 51 (* Return the position of the highest bit set in the value. *) 52 local 53 val isShort: int -> bool = RunCall.isShort 54 fun loadByte(l: LargeInt.int, i: Int.int):word = RunCall.loadByteFromImmutable(l, Word.fromInt i) 55 val segLength: LargeInt.int -> Int.int = Word.toInt o RunCall.memoryCellLength 56 57 (* Compute log2 for a short value. The top bit of i will always be 58 zero since we've checked that it's positive so it will always 59 terminate. *) 60 fun log2Word(i: word, j: word, n: Int.int) = 61 if Word.>(j, i) then n-1 62 else log2Word(i, Word.<<(j, 0w1), n+1) 63 64 (* The value is represented as little-endian byte segment. 65 High-order bytes may be zero so we work back until we 66 find a non-zero byte and then find the bit-position 67 within it. *) 68 fun log2Long(i, byte) = 69 let 70 val b = loadByte(i, byte) 71 in 72 if b = 0w0 then log2Long(i, byte-1) 73 else log2Word(b, 0w2, 1) + byte*8 74 end 75 76 in 77 fun log2 (i: int) : Int.int = 78 if i <= 0 then raise Domain 79 else if isShort i 80 then log2Word(Word.fromLargeInt i, 0w2, 1) 81 else (* i is actually a pointer to a byte segment. *) 82 let 83 val bytes = segLength i * Word.toInt RunCall.bytesPerWord 84 in 85 log2Long(i, bytes-1) 86 end 87 end 88 89 (* These are implemented in the RTS. *) 90 val orb : int * int -> int = RunCall.rtsCallFull2 "PolyOrArbitrary" 91 and xorb : int * int -> int = RunCall.rtsCallFull2 "PolyXorArbitrary" 92 and andb : int * int -> int = RunCall.rtsCallFull2 "PolyAndArbitrary" 93 94 (* notb is defined as ~ (i+1) and there doesn't seem to be much advantage 95 in implementing it any other way. *) 96 fun notb i = ~(i + 1) 97 98 local 99 fun power(acc: LargeInt.int, _, 0w0) = acc 100 | power(acc, n, i) = 101 power( 102 if Word.andb(i, 0w1) = 0w1 103 then acc * n 104 else acc, 105 n * n, Word.>>(i, 0w1) 106 ) 107 in 108 fun pow(i: LargeInt.int, j: Int.int) = 109 if j < 0 110 then(* Various exceptional cases. *) 111 ( 112 if i = 0 then raise Div 113 else if i = 1 then 1 114 else if i = ~1 115 then if Int.rem(j, 2) = 0 then (*even*) 1 else (*odd*) ~1 116 else 0 117 ) 118 else if LibrarySupport.isShortInt j 119 then power(1, i, Word.fromInt j) 120 else 121 (* Long: This is possible only if int is arbitrary precision. If the 122 value to be multiplied is anything other than 0 or 1 123 we'll exceed the maximum size of a cell. *) 124 if i = 0 then 0 125 else if i = 1 then 1 126 else raise Size 127 end 128 129 (* These could be implemented in the RTS although I doubt if it's 130 really worth it. *) 131 local 132 val maxShift = Word.fromInt Word.wordSize 133 val fullShift = pow(2, Word.wordSize) 134 in 135 fun << (i: int, j: Word.word) = 136 if j < maxShift 137 then i * Word.toLargeInt(Word.<<(0w1, j)) 138 else <<(i * fullShift, j-maxShift) 139 end 140 141 fun ~>> (i: int, j: Word.word) = LargeInt.div(i, pow(2, Word.toInt j)) 142 143 open LargeInt (* Inherit everything from LargeInt. Do this last because it overrides the overloaded functions. *) 144end; 145