[Vm-dev] how the h**l do I generate a signed shift?
Nicolas Cellier
nicolas.cellier.aka.nice at gmail.com
Mon Jun 30 20:15:58 UTC 2014
2014-06-30 22:15 GMT+02:00 Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com>:
>
>
>
> 2014-06-30 22:05 GMT+02:00 Nicolas Cellier <
> nicolas.cellier.aka.nice at gmail.com>:
>
>
>>
>>
>> 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:
>>
>> 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)
>>
>
> Hmm, due to int promotion, it might be safer to declare unsigned int z,
> and perform z := 0 - (z >> 32).
>
>
> Argh, 0 - (z >> 31), Phhh!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20140630/ff17be3e/attachment-0001.htm
More information about the Vm-dev
mailing list