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

[Nicolas Cellier]

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)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20140630/eac99943/attachment.htm