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:
- 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).
- 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.
- 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)