[Vm-dev] slip in LargeIntegers >> normalizePositive:

Eliot Miranda eliot.miranda at gmail.com
Fri Mar 6 21:41:24 UTC 2015


Hi Nicolas,

On Fri, Mar 6, 2015 at 10:35 AM, Nicolas Cellier <ncellier at ifrance.com>
wrote:

>
> I'm trying to understand the negative case...
>
> We have the magnitude on one side xMag
> We minSmallInteger in two complement on the other side yTC
> We know that the magnitude of minSmallInteger is yMag=bitInvert(yTC)+1
> We know that all bytes of yTC are 0 but the MSB
> Thus all bytes of bitInvert(yTC) are 16rFF
> Thus all bytes of yMag are 0, but the highest which is (MSB(yTC) xOr: 256)
> + 1.
>
> Thus, assuming same byte length:
> MSB(xMag) < MSB(yMag) => x is a CSI
> MSB(xMag) > MSB(yMag) => x is large
> MSB(xMag) = MSB(yMag) => we must inquire the LSBs of xMag..
> (1 to: len-1) anySatisfy: [:i | (xMag digitAt: i) ~= 0] => x isLarge
> otherwise, x is minSmallInteger
>
> Eliot, I fail to see the bitInvert(MSB(minSmallInteger))+1 in your code...
> Did I miss something?
>

You're talking about normalizeNegative: right?  I haven't changed anything
fundamental here.  The check is in

len <= sLen ifTrue:
[(len < sLen
  or: [(pointer at: sLen - 1)
< (self cDigitOfCSI: interpreterProxy minSmallInteger at: sLen)]) ifTrue:
"interpreterProxy minSmallInteger lastDigit"
["If high digit less, then can be small"
val := 0 - (pointer at: (len := len - 1)).
len - 1 to: 0 by: -1 do:
[:i | val := val * 256 - (pointer at: i)].
^val asOop: SmallInteger].
 1 to: sLen do:
[:i | | byte | "If all digits same, then = minSmallInteger (sr:
minSmallInteger digits 1 to sLen - 1 are 0)"
byte := i > len ifTrue: [0] ifFalse: [pointer at: i - 1].
byte ~= (self cDigitOfCSI: interpreterProxy minSmallInteger at: i) ifTrue:
"Not so; return self shortened"
[len < oldLen ifTrue: "^ self growto: len"
[^self bytes: aLargeNegativeInteger growTo: len].
 ^aLargeNegativeInteger]].
 ^interpreterProxy minSmallInteger asOop: SmallInteger].

The first part deals with the simple case of something shorter than
SmallInteger minVal, or the same length whose top byte is less:

(len < sLen
  or: [(pointer at: sLen - 1)
< (self cDigitOfCSI: interpreterProxy minSmallInteger at: sLen)]) ifTrue:
"interpreterProxy minSmallInteger lastDigit"
["If high digit less, then can be small"
val := 0 - (pointer at: (len := len - 1)).
len - 1 to: 0 by: -1 do:
[:i | val := val * 256 - (pointer at: i)].
^val asOop: SmallInteger].

 The second part deals with the possibility of SmallInteger minVal:

 1 to: sLen do:
[:i | | byte | "If all digits same, then = minSmallInteger (sr:
minSmallInteger digits 1 to sLen - 1 are 0)"
byte := i > len ifTrue: [0] ifFalse: [pointer at: i - 1].
byte ~= (self cDigitOfCSI: interpreterProxy minSmallInteger at: i) ifTrue:
"Not so; return self shortened"
[len < oldLen ifTrue: "^ self growto: len"
[^self bytes: aLargeNegativeInteger growTo: len].
 ^aLargeNegativeInteger]].
 ^interpreterProxy minSmallInteger asOop: SmallInteger].

The bit invert is in cDigitOfCSI:at:
cDigitOfCSI: csi at: ix
^(csi < 0
ifTrue: [0 - csi]
ifFalse: [csi]) >> (ix - 1 * 8) bitAnd: 255

answers 64 for "self cDigitOfCSI: interpreterProxy minSmallInteger at: 4"
in 32 bits (16 in 64-bits).  So cDigitOfCSI:at: is answering magnitude, not
2's complement bytes.

Here's the original code before I streamlined it.  I don't see a
significant difference:

len <= sLen
ifTrue:
["SmallInteger minVal"
minVal := interpreterProxy minSmallInteger.
(len < sLen or: [(self digitOfBytes: aLargeNegativeInteger at: sLen)
< (self cDigitOfCSI: minVal at: sLen)
"minVal lastDigit"])
ifTrue:
["If high digit less, then can be small"
val := 0.
len
to: 1
by: -1
do: [:i | val := val * 256 - (self unsafeByteOf: aLargeNegativeInteger at:
i)].
^ val asOop: SmallInteger].
1 to: sLen do: [:i | "If all digits same, then = minVal (sr: minVal digits
1 to 3 are 0)"
(self digitOfBytes: aLargeNegativeInteger at: i)
= (self cDigitOfCSI: minVal at: i)
ifFalse: ["Not so; return self shortened"
len < oldLen
ifTrue: ["^ self growto: len"
^ self bytes: aLargeNegativeInteger growTo: len]
ifFalse: [^ aLargeNegativeInteger]]].
^ minVal asOop: SmallInteger].

Or am I misunderstanding?


> Nicolas
>
> 2015-03-06 0:37 GMT+01:00 Eliot Miranda <eliot.miranda at gmail.com>:
>
>>
>> Hi Nicolas,
>>
>>    I found my misunderstanding.  Can you review this version instead?
>>
>>
>>
>> On Thu, Mar 5, 2015 at 11:41 AM, Eliot Miranda <eliot.miranda at gmail.com>
>> wrote:
>>
>>> Hi Nicolas,
>>>
>>>      would you mind also reviewing the attached changes?  There's a bug
>>> in them somewhere, although I think they're close to correct.  The ideas
>>> here are to
>>>
>>> - avoid calling firstIndexableField: on every call to unsafeByteOf:at:
>>> in isNormalized:, normalizePositive: and normalizeNegative:.  Do this by
>>> cacheing firstIndexableField in a local pointer variable
>>> - move the bounds check in cDigitOfCSI:at: out to clients that aren't
>>> invoking cDigitOfCSI:at: with in-bounds indices
>>> - avoid the immediate test in digitLengthOf: when it is known that the
>>> object is non-immediate.  Do so by adding digitLengthOfNonImmediate:.
>>>
>>> Of course this approach can be extended to other LargeIntegers methods,
>>> but one step at a time :-/
>>>
>>> On Wed, Mar 4, 2015 at 2:49 PM, Nicolas Cellier <
>>> nicolas.cellier.aka.nice at gmail.com> wrote:
>>>
>>>>
>>>>
>>>> sLen := interpreterProxy minSmallInteger > 16r3FFFFFFF
>>>>
>>>> sounds like a copy/paste error
>>>> I would expect maxSmallInteger here.
>>>>
>>>>
>>>
>>>
>>> --
>>> best,
>>> Eliot
>>>
>>
>>
>>
>> --
>> best,
>> Eliot
>>
>>
>
>


-- 
best,
Eliot
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20150306/834fa05e/attachment-0001.htm


More information about the Vm-dev mailing list