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

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Mon Jun 30 21:55:50 UTC 2014


2014-06-30 22:15 GMT+02:00 Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com>:

>
>
>
> 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!
>
>
Or more future proof 0 - (z >> (sizeof(z) * CHAR_BIT - 1 )), but I have no
idea how to access a macro (CHAR_BIT) provided by another .h in slang...
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20140630/ede3a747/attachment.htm


More information about the Vm-dev mailing list