[Vm-dev] how the h**l do I generate a signed shift?

Eliot Miranda eliot.miranda at gmail.com
Mon Jun 30 22:40:09 UTC 2014


Hi Nicolas,


On Mon, Jun 30, 2014 at 1:05 PM, Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com> wrote:

>
> 2014-06-30 21:24 GMT+02:00 Eliot Miranda <eliot.miranda at gmail.com>:
>
>>
>> Hi All,
>>
>>     I recently eliminated the optimization in Slang that replaces a
>> division by a power of two with a shift, because the code cast the argument
>> to signed, and hence broke unsigned division.  That's what used to be
>> controlled by the UseRightShiftForDivide class var of CCodeGenerator.
>>
>> Yesterday I found out that that optimization is the only thing that's
>> keeping the LargeIntegers plugin afloat.  To whit:
>>
>> LargeIntegersPlugin>>cDigitSub: pByteSmall
>>  len: smallLen
>> with: pByteLarge
>> len: largeLen
>> into: pByteRes
>>  | z limit |
>> <var: #pByteSmall type: 'unsigned char * '>
>> <var: #pByteLarge type: 'unsigned char * '>
>>  <var: #pByteRes type: 'unsigned char * '>
>>
>> z := 0.
>> "Loop invariant is -1<=z<=1"
>>  limit := smallLen - 1.
>> 0 to: limit do:
>> [:i |
>>  z := z + (pByteLarge at: i) - (pByteSmall at: i).
>> pByteRes at: i put: z - (z // 256 * 256).
>> "sign-tolerant form of (z bitAnd: 255)"
>>  z := z // 256].
>> limit := largeLen - 1.
>> smallLen to: limit do:
>>  [:i |
>> z := z + (pByteLarge at: i) .
>> pByteRes at: i put: z - (z // 256 * 256).
>>  "sign-tolerant form of (z bitAnd: 255)"
>> z := z // 256].
>>
>> The "z := z // 256"'s at the end of the loops were being generated as
>>         z = ((sqInt) z) >> 8;
>>  which is essential for the signed arithmetic implicit in "z := z +
>> (pByteLarge at: i) - (pByteSmall at: i)" to work.
>>
>> So what's the right thing to do?
>>
>> In C -1 // 256 = 0, but in Smalltalk -1 // 256 = -1 (// rounds towards -
>> infinity), whereas  (-1 quo: 256) = 0 (quo: rounds towards 0).
>>
>> I could modify the code generator to generate Smalltalk semantics for //,
>> but its not pretty (one has to check signedness, check if there's a
>> remainder, etc).
>>
>> What I'd like is to have a signed bitShift:.  Wait you say, bitShift: is
>> signed.  Ah, but the code generator generates unsigned shifts for all
>> bitShift:'s !!!!.
>>
>> So some ideas:
>>
>> 1. change bitShift: to obey the type of the receiver (Slang allows one to
>> type variables, defaulting to a singed long). This is my preference, but it
>> risks breaking a good handful of negative bitShift: uses in plugins (which
>> is where I'm worried about regressions).
>>
>> 2. change bitShift: to obey explicit casts, generating a signed shift for
>>    foo asInteger bitShift: expr
>>    (self cCoerceSimple: #foo to: #sqInt) bitShift: expr
>> Seriously?!?! this stinks.
>>
>> 3. write
>> z := self cCode: [z >>= 8] inSmalltalk: [z // 256]
>>
>> Seriously?!?! this stinks too.
>>
>> Anything else that makes any sense?
>> --
>> best,
>> Eliot
>>
>

Hi Eliot,
> look how I did it in the 32bits LargInt variant:
>

if the 32-bit large int version passes all the tests why hasn't it replaced
the byte one?

cDigitSub: pWordSmall
>         len: smallLen
>         with: pWordLarge
>         len: largeLen
>         into: pWordRes
>     | z limit |
>     <var: #pWordSmall type: 'unsigned int * '>
>     <var: #pWordLarge type: 'unsigned int * '>
>     <var: #pWordRes type: 'unsigned int * '>
>     <var: #z type: 'unsigned long long '>
>
>     z := 0.
>     limit := smallLen - 1.
>     0 to: limit do:
>         [:i |
>         z := z + (pWordLarge at: i) - (pWordSmall at: i).
>         pWordRes at: i put: (z bitAnd: 16rFFFFFFFF).
>         z := 0 - (z >> 63)].
>     limit := largeLen - 1.
>     smallLen to: limit do:
>         [:i |
>         z := z + (pWordLarge at: i) .
>         pWordRes at: i put: (z bitAnd: 16rFFFFFFFF).
>         z := 0 - (z >> 63)].
>     ^0
>
> In unsigned arithmetic, all these ops are perfectly well defined, and I
> don't think they suck.
> So you can translate it back to unsigned char * and unsigned short (z >>
> 16)
>



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


More information about the Vm-dev mailing list