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?
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 adivision 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)
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 adivision 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)]. ^0In 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).
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 adivision 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)]. ^0In 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!
2014-06-30 22:15 GMT+02:00 Nicolas Cellier < nicolas.cellier.aka.nice@gmail.com>:
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 adivision 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)]. ^0In 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...
Hi Nicolas,
On Mon, Jun 30, 2014 at 1:05 PM, Nicolas Cellier < nicolas.cellier.aka.nice@gmail.com> wrote:
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 adivision 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:
if the 32-bit large int version passes all the tests why hasn't it replaced the byte one?
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)]. ^0In 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)
Hi All,
sorry for that noise...
On Mon, Jun 30, 2014 at 12:24 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
Hi All,
I recently eliminated the optimization in Slang that replaces adivision 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?
Doh:
Intger methdos for *VMMaker signedBitShift: anInteger "For historical reasons Slang generates an unsigned shift from all of the shift operators >>, << & bitShift:. These are too deeply entrenched to try and redefine the semantics. So instead we provide a signed bitShift: that signals to Slang that its argument should be cast to signed, not to unsigned, when being shifted." ^self bitShift: anInteger
apologies
2014-07-01 0:41 GMT+02:00 Eliot Miranda eliot.miranda@gmail.com:
Hi All,
sorry for that noise...
On Mon, Jun 30, 2014 at 12:24 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
Hi All,
I recently eliminated the optimization in Slang that replaces adivision 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?
Doh:
Intger methdos for *VMMaker signedBitShift: anInteger "For historical reasons Slang generates an unsigned shift from all of the shift operators >>, << & bitShift:. These are too deeply entrenched to try and redefine the semantics. So instead we provide a signed bitShift: that signals to Slang that its argument should be cast to signed, not to unsigned, when being shifted." ^self bitShift: anInteger
apologies
best, Eliot
Though remember that signed right shift is theoretically implementation defined (though I'm not aware of a compiler/processor providing 0 expansion), and that signed right shift behavior is undefined in case of overflow... http://stackoverflow.com/questions/4009885/arithmetic-bit-shift-on-a-signed-... C is a very strange language... Portable? I just hate its (lack of) signed integer arithmetic model.
2014-07-01 0:56 GMT+02:00 Nicolas Cellier < nicolas.cellier.aka.nice@gmail.com>:
2014-07-01 0:41 GMT+02:00 Eliot Miranda eliot.miranda@gmail.com:
Hi All,
sorry for that noise...
On Mon, Jun 30, 2014 at 12:24 PM, Eliot Miranda eliot.miranda@gmail.com wrote:
Hi All,
I recently eliminated the optimization in Slang that replaces adivision 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?
Doh:
Intger methdos for *VMMaker signedBitShift: anInteger "For historical reasons Slang generates an unsigned shift from all of the shift operators >>, << & bitShift:. These are too deeply entrenched to try and redefine the semantics. So instead we provide a signed bitShift: that signals to Slang that its argument should be cast to signed, not to unsigned, when being shifted." ^self bitShift: anInteger
apologies
best, Eliot
Though remember that signed right shift is theoretically implementation defined (though I'm not aware of a compiler/processor providing 0 expansion), and that signed right shift behavior is undefined in case of overflow...
signed left shift is undefined in case of overflow I should better read again before sending...
http://stackoverflow.com/questions/4009885/arithmetic-bit-shift-on-a-signed-... C is a very strange language... Portable? I just hate its (lack of) signed integer arithmetic model.
On Mon, Jun 30, 2014 at 12:24:12PM -0700, Eliot Miranda wrote:
Hi All,
I recently eliminated the optimization in Slang that replaces adivision 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.
<slightly OT>
I'm just catching up with the conversation, and I see that the issue is now resolved, but it's worth noting that John Maloney's method comment from August 1998 is worthy of our appreciation :)
CCodeGenerator class>>initialize "CCodeGenerator initialize"
UseRightShiftForDivide := true. "If UseRightShiftForDivide is true, the translator will generate a right-shift when it encounters a division by a constant that is a small power of two. For example, 'x / 8' will generate '((int) x >> 3)'. The coercion to int is done to make it clear that the C compiler should generate a signed shift." "Note: The Kernighan and Ritchie 2nd Edition C manual, p. 49, leaves the semantics of right-shifting a negative number open to the discretion of the compiler implementor. However, it strongly suggests that most compilers should generate an arithmetic right shift (i.e., shifting in the sign bit), which is the same as dividing by a power of two. If your compiler does not generate or simulate an arithmetic shift, then make this class variable false and re-translate."
</slightly OT>
Dave
On 01.07.2014, at 01:27, David T. Lewis lewis@mail.msen.com wrote:
On Mon, Jun 30, 2014 at 12:24:12PM -0700, Eliot Miranda wrote:
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.
<slightly OT>
I'm just catching up with the conversation, and I see that the issue is now resolved, but it's worth noting that John Maloney's method comment from August 1998 is worthy of our appreciation :)
CCodeGenerator class>>initialize "CCodeGenerator initialize"
UseRightShiftForDivide := true. "If UseRightShiftForDivide is true, the translator will generate a right-shift when it encounters a division by a constant that is a small power of two. For example, 'x / 8' will generate '((int) x >> 3)'. The coercion to int is done to make it clear that the C compiler should generate a signed shift." "Note: The Kernighan and Ritchie 2nd Edition C manual, p. 49, leaves the semantics of right-shifting a negative number open to the discretion of the compiler implementor. However, it strongly suggests that most compilers should generate an arithmetic right shift (i.e., shifting in the sign bit), which is the same as dividing by a power of two. If your compiler does not generate or simulate an arithmetic shift, then make this class variable false and re-translate."
</slightly OT>
Dave
... except that even C's arithmetic right shift is NOT the same as dividing by a power of two for negative values:
-1 / 2 == 0
-1 >> 1 == -1
And C's '/' is not at all the same as Squeak's '//', as previously noted, which is why we have 'quo:'.
It's not just C, of course, and not just signed shifts. E.g. I'm having fun implementing BitBlt in JavaScript. Had this:
mask = 0xFFFFFFFF; while (mask != 0) { ... mask = mask >>> bitdepth; }
Here, '>>>' is a logical shift, meaning it shifts in zeroes. All values are positive. Bitdepth is 1, 2, 4, 8, 16, or 32. Still got into an endless loop. Nice, huh? And allegedly C might do the same, depending on the compiler.
- Bert -
vm-dev@lists.squeakfoundation.org
-
Bert Freudenberg -
David T. Lewis -
Eliot Miranda -
Nicolas Cellier