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

Fri Mar 6 22:21:50 UTC 2015

2015-03-06 22:41 GMT+01:00 Eliot Miranda <eliot.miranda at gmail.com>:

>
> 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.
>

Ah, of course, I see it now :)

So you don't really use the knowledge that following digits are 0...
That could save the repeated shifts and bitAnd:... unless the C compiler
unroll that loop.

>
> 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/356c7eec/attachment.htm