"

 COPYRIGHT (c) 1988 by Claus Gittinger

	      All Rights Reserved

 This software is furnished under a license and may be used

 only in accordance with the terms of that license and with the

 inclusion of the above copyright notice.   This software may not

 be provided or otherwise made available to, or used by, any

 other person.  No title to or ownership of the software is

 hereby transferred.

"

Number subclass:#Integer

       instanceVariableNames:''

       classVariableNames:'DefaultDisplayRadix'

       poolDictionaries:''

       category:'Magnitude-Numbers'

!

Integer comment:'

COPYRIGHT (c) 1988 by Claus Gittinger

	      All Rights Reserved

'!

!Integer class methodsFor:'documentation'!

copyright

"

 COPYRIGHT (c) 1988 by Claus Gittinger

	      All Rights Reserved

 This software is furnished under a license and may be used

 only in accordance with the terms of that license and with the

 inclusion of the above copyright notice.   This software may not

 be provided or otherwise made available to, or used by, any

 other person.  No title to or ownership of the software is

 hereby transferred.

"

!

version

"

"

!

documentation

"

    abstract superclass for all integer numbers.

    See details in concrete subclasses LargeInteger and SmallInteger.

    Class variables:

	DefaultDisplayRadix     the radix in which integers present their 

				displayString (which is used in inspectors)

				If you are to look at many hex numbers, bitmasks

				etc. you may set this to 2 or 16.

				(avoids typing printStringRadix:.. all the time

				 - I know - I am lazy ;-). Default is 10.

"

! !

!Integer class methodsFor:'constants'!

zero

    "return the neutral element for addition"

    ^ 0

!

unity

    "return the neutral element for multiplication"

    ^ 1

! !

!Integer class methodsFor:'instance creation'!

new:numberOfBytes neg:negative

    "for ST-80 compatibility:

     Return an empty Integer (uninitialized value) with space for

     numberOfBytes bytes (= digitLength). The additional argument

     negative specifies if the result should be a negative number.

     The digits can be stored byte-wise into the result, using digitAt:put:"

    ^ (LargeInteger basicNew numberOfDigits:numberOfBytes) 

		sign:(negative ifTrue:[-1] ifFalse:[1])

! !

!Integer class methodsFor:'misc'!

displayRadix:aNumber

    "being tired of always sending #printStringRadix: in the inspectors,

     this allows you to change the default print radix for the displayString

     method."

    DefaultDisplayRadix := aNumber

    "

     Integer displayRadix:16. 123456 inspect

     Integer displayRadix:10. 123456 inspect

    "

! !

!Integer methodsFor:'arithmetic'!

quo:aNumber

    "Return the integer quotient of dividing the receiver by aNumber with

     truncation towards zero. For Integers this is same as //"

    ^ self // aNumber

! !

!Integer methodsFor:'double dispatching'!

sumFromFraction:aFraction

    |d|

    d := aFraction denominator.

    ^ (Fraction numerator:(aFraction numerator + (self * d))

	      denominator:d) reduced

!

differenceFromFraction:aFraction

    |d|

    d := aFraction denominator.

    ^ (Fraction numerator:(aFraction numerator - (self * d))

	      denominator:d) reduced

!

productFromFraction:aFraction

    ^ (Fraction numerator:(self * aFraction numerator)

	      denominator:aFraction denominator) reduced

!

quotientFromFraction:aFraction

    ^ (Fraction numerator:aFraction numerator

	      denominator:(self * aFraction denominator)) reduced

! !

!Integer methodsFor:'bit operators'!

bitAnd:anInteger

    "return the bitwise-and of the receiver and the argument, anInteger"

    |result n byte|

    n := (anInteger digitLength) min:(self digitLength).

    result := self class basicNew numberOfDigits:n.

    1 to:n do:[:index |

	byte := (anInteger digitAt:index) bitAnd:(self digitAt:index).

	result digitAt:index put:byte.

    ].

    byte == 0 ifTrue:[

	^ result normalize

    ].

    ^ result

!

bitOr:anInteger

    "return the bitwise-or of the receiver and the argument, anInteger"

    |result n byte|

    n := (anInteger digitLength) max:(self digitLength).

    result := self class basicNew numberOfDigits:n.

    1 to:n do:[:index |

	byte := (anInteger digitAt:index) bitOr:(self digitAt:index).

	result digitAt:index put:byte.

    ].

    byte == 0 ifTrue:[

	^ result normalize

    ].

    ^ result

!

bitXor:anInteger

    "return the bitwise-or of the receiver and the argument, anInteger"

    |result n byte|

    n := (anInteger digitLength) max:(self digitLength).

    result := self class basicNew numberOfDigits:n.

    1 to:n do:[:index |

	byte := (anInteger digitAt:index) bitXor:(self digitAt:index).

	result digitAt:index put:byte.

    ].

    byte == 0 ifTrue:[

	^ result normalize

    ].

    ^ result

!

highBit

    "return the bitIndex of the highest bit set. The returned bitIndex

     starts at 1 for the least significant bit. Returns -1 if no bit is set."

    |byteNr highByte|

    byteNr := self digitLength.

    highByte := self digitAt:byteNr.

    ^ (byteNr - 1) * 8 + highByte highBit

    "

     1 highBit                  

     (1 bitShift:1) highBit     

     (1 bitShift:30) highBit    

     (1 bitShift:31) highBit    

     (1 bitShift:32) highBit    

     (1 bitShift:33) highBit    

     (1 bitShift:64) highBit     

     (1 bitShift:1000) highBit   

     ((1 bitShift:64)-1) highBit  

    "

!

bitAt:index

    "return the value of the index's bit (index starts at 1).

     Notice: the result of bitShift: on negative receivers is not 

	     defined in the language standard (since the implementation

	     is free to choose any internal representation for integers)"

    |i "{Class: SmallInteger}"|

    i := index - 1.

    ^ (self digitAt:(i // 8 + 1)) bitAt:(i \\ 8 + 1)

    "

     1 bitAt:1                  

     (1 bitShift:30) bitAt:30    

     (1 bitShift:30) bitAt:31    

     (1 bitShift:30) bitAt:32    

     (1 bitShift:31) bitAt:31    

     (1 bitShift:31) bitAt:32    

     (1 bitShift:31) bitAt:33    

     (1 bitShift:32) bitAt:32    

     (1 bitShift:32) bitAt:33    

     (1 bitShift:32) bitAt:34    

     (1 bitShift:64) bitAt:64     

     (1 bitShift:64) bitAt:65     

     (1 bitShift:64) bitAt:66     

     (1 bitShift:1000) bitAt:1000   

     (1 bitShift:1000) bitAt:1001  

     (1 bitShift:1000) bitAt:1002 

     (1 bitShift:1000) bitAt:2000  

    "

!

bitShift:shiftCount

    "return the value of the receiver shifted by shiftCount bits;

     leftShift if shiftCount > 0; rightShift otherwise.

     Notice: the result of bitShift: on negative receivers is not 

	     defined in the language standard (since the implementation

	     is free to choose any internal representation for integers)"

    |result 

     prev       "{ Class: SmallInteger }"

     next       "{ Class: SmallInteger }"

     byte       "{ Class: SmallInteger }"

     bitShift   "{ Class: SmallInteger }"

     revShift   "{ Class: SmallInteger }"

     digitShift "{ Class: SmallInteger }"

     n          "{ Class: SmallInteger }" 

     nn         "{ Class: SmallInteger }"|

    shiftCount > 0 ifTrue:[

	"left shift"

	digitShift := shiftCount // 8.

	bitShift := shiftCount \\ 8.

	n := self digitLength.

	"

	 modulu 8 shifts can be done faster ...

	"

	bitShift == 0 ifTrue:[

	    result := self class basicNew numberOfDigits:n + digitShift.

	    result sign:self sign.

	    result digits replaceFrom:(digitShift + 1) with:self digits.

	    "

	     no normalize needed, since receiver was already normalized

	    "

	    ^ result

	].

	"

	 less-than-8 shifts can be done faster ...

	"

	digitShift == 0 ifTrue:[

	    n := n + 1.

	    result := self class basicNew numberOfDigits:n.

	    result sign:self sign.

	    prev := 0.

	    1 to:n-1 do:[:index |

		byte := self digitAt:index.

		byte := (byte bitShift:bitShift) bitOr:prev.

		result digitAt:index put:(byte bitAnd:16rFF).

		prev := byte bitShift:-8.

	    ].

	    result digitAt:n put:prev.

	    "

	     might have stored a 0-byte ...

	    "

	    prev == 0 ifTrue:[

		^ result normalize

	    ].

	    ^ result.

	].

	"

	 slow case ...

	"

	n := n + digitShift + 1.

	result := self class basicNew numberOfDigits:n.

	result sign:self sign.

	byte := ((self digitAt:1) bitShift:bitShift) bitAnd:16rFF.

	result digitAt:(digitShift + 1) put:byte.

	revShift := -8 + bitShift.

	2 to:(self digitLength) do:[:index |

	    byte := (self digitAt:index) bitShift:bitShift.

	    byte := byte bitOr:((self digitAt:index-1) bitShift:revShift).

	    byte := byte bitAnd:16rFF.

	    result digitAt:(index + digitShift) put:byte

	].

	"

	 might have stored a 0-byte ...

	"

	byte == 0 ifTrue:[

	    ^ result normalize

	].

	^ result

    ].

    shiftCount < 0 ifTrue:[

	"right shift"

	digitShift := shiftCount negated // 8.

	bitShift := shiftCount negated \\ 8.

	n := self digitLength.

	digitShift >= n ifTrue:[

	    ^ 0

	].

	"

	 modulu 8 shifts can be done faster ...

	"

	bitShift == 0 ifTrue:[

	    n := n-digitShift.

	    result := self class basicNew numberOfDigits:n.

	    result sign:self sign.

	    result digits replaceFrom:1 with:self digits startingAt:(digitShift + 1) .

	    n <= 4 ifTrue:[

		^ result normalize

	    ].

	    ^ result

	].

	"

	 less-than-8 shifts can be done faster ...

	"

	digitShift == 0 ifTrue:[

	    result := self class basicNew numberOfDigits:n.

	    result sign:self sign.

	    prev := 0.

	    bitShift := bitShift negated.

	    revShift := 8 + bitShift.

	    n to:1 by:-1 do:[:index |

		byte := self digitAt:index.

		next := (byte bitShift:revShift) bitAnd:16rFF.

		byte := (byte bitShift:bitShift) bitOr:prev.

		result digitAt:index put:(byte bitAnd:16rFF).

		prev := next.

	    ].

	    (n <= 5) ifTrue:[

		^ result normalize

	    ].

	    ^ result

	].

	"

	 slow case ...

	"

	nn := n-digitShift.

	result := self class basicNew numberOfDigits:nn.

	result sign:self sign.

	prev := 0.

	bitShift := bitShift negated.

	revShift := 8 + bitShift.

	n to:(1 + digitShift) by:-1 do:[:index |

	    byte := self digitAt:index.

	    next := (byte bitShift:revShift) bitAnd:16rFF.

	    byte := (byte bitShift:bitShift) bitOr:prev.

	    result digitAt:(index - digitShift) put:byte.

	    prev := next.

	].

	"the last stored byte ..."

	^ result normalize

    ].

    ^ self "no shift"

! !

!Integer methodsFor:'truncation & rounding'!

ceiling

    "I am my ceiling"

    ^ self

!

floor

    "I am my floor"

    ^ self

!

rounded

    "return the receiver rounded toward the next Integer -

     for integers this is self"

    ^ self

!

truncated

    "return the receiver truncated towards zero - 

     for integers this is self"

    ^ self

!

normalize

    "this is ST/X's name for ST-80's compressed.

     ST/X may be changed for full compatibility."

    ^ self

!

compressed

    "this is ST-80's name for ST/X's normalize.

     ST/X may be changed for full compatibility."

    ^ self

! !

!Integer methodsFor:'queries'!

digitLength

    "return the number of bytes needed for the binary representation

     of the receiver"

    ^ (self log:256) ceiling asInteger

!

digitAt:n

    "return the n-th byte of the binary representation.

     This is a very stupid implementation, and should be redefined in

     concrete subclasses."

    |num count|

    num := self.

    count := n.

    [count > 1] whileTrue:[

	num := num // 256.

	count := count - 1

    ].

    ^ num \\ 256

    "

     16r44332211 digitAt:1     

     16r44332211 digitAt:2    

     16r44332211 digitAt:3     

     16r44332211 digitAt:4