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

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

2014-06-30 21:24 GMT+02:00 Eliot Miranda <eliot.miranda@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!