Wow... Here's something interesting:  the right shift for negative large
integers appears to have the same semantics as the algebraic right shift as
implemented on the PowerPC.  This this generalization correct?  If so,
identical semantics could be found by generating the correct _asm
instruction in the vm.

And, if this is desirable, then perhaps it's easier to make the small
integer semantics emulate the large integer semantics on all platforms, i
suppose by:

negating x
shifting x
negating x

which requires ugliness in the case of x=16r40000000.

I wonder whether it's possible to implement a two's complement shifting
semantics efficiently on LargeNegativeIntegers.  Are they not implemented as
polynomials?

-John

> -----Original Message-----
> From: sr at Klaus.priv [mailto:sr at Klaus.priv]On Behalf Of Stephan Rudlof
> Sent: Tuesday, June 06, 2000 4:51 PM
> To: squeak at cs.uiuc.edu; Ingalls, Dan; Raab, Andreas; Stefan Matthias
> Aust; R. A. Harmon; John Maloney; Leandro Caniglia
> Subject: [BUG][SEMANTIC] semantics of Integer bit ops, e.g. >>bitShift:
> [was: Re: Large integers problem...]
>
>
> Dear Squeakers,
>
> the LargeIntegers problem is mainly an Integer semantics problem and
> goes much deeper. The LargeIntegers module just implements the current
> semantic for LargeIntegers.
>
> 'Numerical' Squeakers: Please take some time and read this straining
> mail, because the problem lays in the fundaments of Squeak!
>
>
> While thinking about defining >>highBit for negative Integers, too -
> e.g. by returning #infinite - I've found a nasty semantic problem.
>
>
> The semantics of Integer>>bitShift: (used for LargeIntegers) differs
> from the one of SmallInteger>>bitShift: :
>
> For left shifts the semantics are the same
>
> ((Integer new: 1 neg: true) at: 1 put: 5; yourself) bitShift: 1. -10
> "LargeNegativeInteger"
> -5 bitShift: 1. -10
>
> *but* for right shifts *not*:
>
> ((Integer new: 1 neg: true) at: 1 put: 5; yourself) bitShift: -1. -2
> -5 bitShift: -1. -3
>
> Another example (because you could argue, the above is unsafe since not
> #normalize'd LargeIntegers):
>
> (2 << 32) negated bitShift: -1 -4294967296	"large"
> (2 << 32 + 1) negated bitShift: -1  -4294967296
> (2 << 16) negated bitShift: -1 -65536		"small"
> (2 << 16 + 1) negated bitShift: -1 -65537	"!"
>
> The reasons are:
> - LargeNegativeIntegers: they are treated always as positive values and
> the sign is applied to the result;
> - negative SmallIntegers
> 	- left shift: same as for LargeNegativeIntegers,
> 	- right shift: realized by shifting the 2-complement and
> transforming
> it back (2 >>bitInvert's)!
>
> The LargeNegativeIntegers treatment is wrong here.
>
> Let's take a look onto the bits:
> 0 bitShift: -1 0
> -1 bitShift: -1 -1 "..1 -> ..1"
> -2 bitShift: -1 -1 "..10 -> ..1"
> -3 bitShift: -1 -2 "..101 -> ..10"
> -4 bitShift: -1 -2  "..100 -> ..10"
> -5 bitShift: -1 -3  "..1011 -> ..101"
> -6 bitShift: -1 -3  "..1010 -> ..101"
>
> A right shift of negative Integers takes one-bits from the left, if we
> take the 2-complement representation with an infinite number of ones to
> the left.
>
> So
>
> SmallInteger>>
> bitShift: arg
> 	"Primitive. Answer an Integer whose value is the receiver's value
> 	shifted left by the number of bits indicated by the
> argument. Negative
> 	arguments shift right. The receiver is interpreted as having
> 	2's-complement representation.
> 	Essential.  See Object documentation whatIsAPrimitive."
> 	<primitive: 17>
> 	self >= 0 ifTrue: [^ super bitShift: arg].
> 	^ arg >= 0
> 		ifTrue: [(self negated bitShift: arg) negated]
> 		ifFalse: [(self bitInvert bitShift: arg) bitInvert]
>
> does it right, but not
>
> Integer>>
> bitShift: shiftCount
> 	"Answer an Integer whose value (in twos-complement
> representation) is
> 	 the receiver's value (in twos-complement representation)
> shifted left
> 	by
> 	 the number of bits indicated by the argument. Negative arguments
> 	shift right. Zeros are shifted in from the right in left shifts."
> 	| rShift |
> 	shiftCount >= 0 ifTrue: [^ self digitLshift: shiftCount]. "OK."
> 	rShift _ 0 - shiftCount.
> 	^ (self
> 		digitRshift: (rShift bitAnd: 7)
> 		bytes: (rShift bitShift: -3)
> 		lookfirst: self digitLength) normalize
>
> , which calls >>digitRshift:bytes:lookfirst, but this - private - method
> works only 2-complement correct for positive Integers!
>
> So the right shift variant here is wrong!
>
> The ANSI standard
> 	NCITS J20 DRAFT December, 1997 of ANSI Smalltalk Standard
> revision 1.9
> avoids this problem by just stating that the result is undefined for
> negative Integers:
>
> ---
>
> 5.6.5.8 Message: bitShift: shift
> Synopsis
>
> NCITS J20 DRAFT December, 1997 141
> of ANSI Smalltalk Standard revision 1.9
> Answer the result of logically bit-wise shifting the binary
> representation of the receiver by shift
> bits.
> Definition: <integer>
> If shift is positive, the receiver is shifted left and zeros (0) are
> shifted in on the right. If shift is
> negative, the receiver is shifted right and low order bits are
> discarded.
> The result is undefined if either the receiver is negative.
> Parameters
> shift <integer> uncaptured
> Return Values
> <integer>unspecified
> Errors
> none
>
> ---
> ('either' seems to be a typos here.)
>
> For other bit operations ANSI says the same.
>
>
> So I see two solutions of the problems:
>
> - to go after ANSI and kicking off shift and possibly other bit ops for
> negative Integers, or
> - to give the Integer shift operation methods the same semantics as the
> SmallInteger ones, means consequently 2-complement semantics.
>
> In both cases it has taken care of the arithmetic methods which rely on
> shift operations, because negative Integers come into play here.
>
> Currently I don't have an opinion about what's best, but I think a
> refactoring *is* needed!
>
> Comments?
>
>
> Greetings,
>
> Stephan
>
>
> PS: Some good news:
> 	- >>bitInvert: works as expected,
> 	- digit logic operations should work correctly (at least for the
> LargeIntegersPlugin, because it is only defined for *positive* Integers,
> otherwise standard ST methods are used...)
>
> Stephan Rudlof wrote:
> >
> > Andreas,
> >
> > "Raab, Andreas" wrote:
> > >
> > > Folks,
> > >
> > > I just run into an interesting problem. When I attempted to compute
> > >
> > >         -585148196 / -1442692966
> > >
> > > (not by typing in these numbers of course ;-) I got an error
> saying "highBit
> > > is not defined for negative numbers".
> >
> > I cannot repeat this error, by evaluating into a workspace I get:
> >
> > -585148196 / -1442692966  -> (58/143)
> > -585148196 // -1442692966 -> 0
> >
> > another example to get a result >0:
> >
> > -5851481960 / -1442692966 -> (580/143)
> > -5851481960 // -1442692966 -> 4
> >
> > with 2.8alpha#2242 with LargeIntegers module.
> >
> > But just I've seen that I *can* confirm this error, if I *comment* *out*
> > the call of the LargeIntegers module!
> > Interesting!
> >
> > Seems to be a case where the LargeInteger module computes better than
> > the standard ST methods.
> >
> > Explanation:
> >
> > - semantics: the error message is correct at this point in the ST
> > method: a negative integer in 2-complements arithmetics with
> > [infinite/not fixed] length hasn't a high bit! Theoretically there is an
> > infinite number of leading one bits.
> > - methods: LargePositiveInteger>>highBit can always be used for
> > LargeNegativeInteger, but >>highBit for negative SmallIntegers isn't
> > defined!
> >
> > - LargeIntegers: After taking a look into the LargeIntegersPlugin and
> > into the callers Integer>>/, >>quo:, LargePositiveInteger>>\\\ and the
> > DSA ones of Integer>>digitDiv:neg:, I would say, that all is correct
> > here. The here called
> >         LargeIntegersPlugin>>primDigitDiv: secondInteger negative: neg
> > method converts the int args to LargeIntegers and treats them as
> > positive ones while dividing them. The sign is computed by and given as
> > arg from the callers of Integer>>digitDiv:neg:.
> > Some further computation confirms *same* semantics for
> > SmallInteger/SmallInteger versus SmallInteger/LargeInteger arithmetics
> > (in the latter case the SmallInteger will be transformed to a non
> > normalized LargeInteger):
> >
> > -12 // -32 0 "SmallInteger/SmallInteger"
> > -12 \\ -32 -12
> > -585148196 // -1442692966 0 "SmallInteger/LargeInteger"
> > -585148196 \\ -1442692966 -585148196
> > 12 // -32 -1
> > 12 \\ -32 -20
> > 585148196 // -1442692966 -1
> > 585148196 \\ -1442692966 -857544770
> >         -1442692966 - -857544770 -585148196
> > -12 // 32  -1
> > -12 \\ 32  20
> > -585148196 // 1442692966  -1
> > -585148196 \\ 1442692966  857544770
> >
> > and
> >
> > -32 // -12 2
> > -32 \\ -12 -8
> > -1442692966 // -585148196 2
> > -1442692966 \\ -585148196 -272396574
> >
> > -32 // 12  -3
> > -32 \\ 12  4
> > -1442692966 // 585148196  -3
> > -1442692966 \\ 585148196 312751622
> >
> > 32 // -12  -3
> > 32 \\ -12  -4
> > 1442692966 // -585148196  -3
> > 1442692966 \\ -585148196 -312751622
> >
> > So the bug is in the old ST method >>digitDiv:neg: or in the callers of
> > it:
> > - e.g. (!, there is/are other(s) (at least Integer>>/ (these are the
> > 'official' ones...)))
> > Integer
> > >>quo: aNumber
> >         "Refer to the comment in Number quo:"
> >         | ng quo |
> >         aNumber isInteger
> >                 ifTrue:
> >                         [ng _ self negative == aNumber negative
> == false.
> >                         quo _ (self digitDiv: (aNumber class ==
> SmallInteger
> >                                                         ifTrue:
> [aNumber abs]
> >
> ifFalse: [aNumber])
> >                                                 neg: ng)
> >                                                 at: 1.
> >                         ^ quo normalize].
> >         ^ aNumber adaptToInteger: self andSend: #quo:
> >
> > , works well for positive/negative LargeIntegers/SmallInteger *args* and
> > for positive/negative LargeInteger receivers as for positive
> > SmallInteger receivers,
> > but *not* for *negative* SmallInteger receivers! That's the point.
> >
> > With the LargeIntegers module this works, because it converts all
> > SmallIntegers to LargeIntegers.
> >
> > > It seems something is broken in the
> > > logic for large negative integers here. The interesting thing
> is that the
> > > LargeIntegersPlugin actually computes the correct result (I
> was originally
> > > working in a somewhat outdated image and switched to the
> latest one for
> > > seeing if the problem has been solved). However, when
> commenting out the
> > > primitive in #digitDiv:neg: the same error occurs.
> >
> > Your LargeIntegers module probably wasn't installed correctly!
> > Check 1000 factorial... ;-)
> >
> > >
> > > Can somebody shed a bit light on this?! I hate it when
> Integer's don't work
> > > ;-)
> >
> > Me, too.
> >
> > >
> > >   - Andreas
> >
> > Greetings,
> >
> > Stephan
> > --
> > Stephan Rudlof (sr at evolgo.de)
> >    "Genius doesn't work on an assembly line basis.
> >     You can't simply say, 'Today I will be brilliant.'"
> >     -- Kirk, "The Ultimate Computer", stardate 4731.3
>
> --
> Stephan Rudlof (sr at evolgo.de)
>    "Genius doesn't work on an assembly line basis.
>     You can't simply say, 'Today I will be brilliant.'"
>     -- Kirk, "The Ultimate Computer", stardate 4731.3
>
>