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