# HG changeset patch # User Claus Gittinger # Date 1456488550 -3600 # Node ID 3ae994a585786394d2a4e921280ffdaa0d016d27 # Parent 45c2b67527f12962f42ca574fc10dffdc068c283 #REFACTORING class: LargeInteger added: #absDestructiveSubtract: removed: #absSubtract: changed:8 methods refactoring division diff -r 45c2b67527f1 -r 3ae994a58578 LargeInteger.st --- a/LargeInteger.st Fri Feb 26 11:45:37 2016 +0100 +++ b/LargeInteger.st Fri Feb 26 13:09:10 2016 +0100 @@ -507,36 +507,19 @@ See #quo: which returns -2 in the above case and #rem: which is the corresponding remainder." - |cls divMod quo abs "{ Class: SmallInteger }" n| - - - cls := aNumber class. + |nrClass divMod quo| + + nrClass := aNumber class. " this is the common case, dividing by a SmallInteger. Use a special method for this case ... " - (cls == SmallInteger) ifTrue:[ - abs := aNumber. - abs := abs abs. - (abs between:1 and:(SmallInteger maxBytes == 8 ifTrue:16r0fffffffffff ifFalse:16r00ffffff)) ifTrue:[ - divMod := self absFastDivMod:abs. - ] ifFalse:[ - n := abs asLargeInteger. - ]. - ] ifFalse:[ - " - if the argument is not a largeInteger, coerce - " - (cls == self class) ifFalse:[ - ^ self retry:#// coercing:aNumber - ]. - n := aNumber + ((nrClass == SmallInteger) or:[ nrClass == self class]) ifFalse:[ + ^ self retry:#// coercing:aNumber ]. - - divMod isNil ifTrue:[ - divMod := self absDivMod:n. - ]. + divMod := self absDivMod:aNumber. + quo := divMod at:1. (sign == aNumber sign) ifFalse:[ "/ adjust for truncation if negative and there is a remainder ... @@ -546,9 +529,9 @@ (divMod at:2) == 0 ifFalse:[ ^ quo - 1 ]. - quo digitLength == SmallInteger maxBytes ifTrue:[ - ^ quo compressed - ]. +"/ quo digitLength == SmallInteger maxBytes ifTrue:[ +"/ ^ quo compressed +"/ ]. ]. ^ quo @@ -599,38 +582,16 @@ Redefined here for speed." - |abs rem negativeDivisor| - - aNumber negative ifTrue:[ - negativeDivisor := true. - abs := aNumber negated. - ] ifFalse:[ - negativeDivisor := false. - abs := aNumber. + |rem negativeDivisor nrClass| + + nrClass := aNumber class. + ((nrClass == SmallInteger) or:[nrClass == self class]) ifFalse:[ + ^ self retry:#\\ coercing:aNumber ]. - - " - this is the common case, dividing by a SmallInteger. - Use a special method for this case ... - " - (aNumber class == SmallInteger) ifTrue:[ - (abs between:1 and:(SmallInteger maxBytes == 8 ifTrue:16r00ffffffffff ifFalse:16r00ffffff)) ifTrue:[ - rem := (self absFastDivMod:abs) at:2. - ] ifFalse:[ - rem := self absMod:abs asLargeInteger - ]. - ] ifFalse:[ - " - if the argument is not a largeInteger, coerce - " - (aNumber class == self class) ifFalse:[ - ^ self retry:#\\ coercing:aNumber - ]. - - rem := self absMod:abs. - ]. - - rem = 0 ifFalse:[ + + rem := (self absDivMod:aNumber) at:2. + rem ~~ 0 ifTrue:[ + negativeDivisor := aNumber negative. negativeDivisor ifTrue:[ rem := rem setSign:-1 ]. @@ -700,36 +661,46 @@ This is redefined here for more performance (as the remainder is generated as a side effect of division)" - |cls n| + |nrClass| ((self < 0) or:[aNumber <= 0]) ifTrue:[ + "/ this is rubbish ^ super divMod:aNumber ]. "/ only handle the common case here - cls := aNumber class. - (cls == SmallInteger) ifTrue:[ - " - this is the common case, dividing by a SmallInteger. - Use a special method for this case ... - " - (aNumber between:1 and:(SmallInteger maxBytes == 8 ifTrue:16r00ffffffffffff ifFalse:16r00ffffff)) ifTrue:[ - ^ self absFastDivMod:aNumber abs. - ]. - n := aNumber asLargeInteger. - ] ifFalse:[ - (cls == self class) ifFalse:[ + nrClass := aNumber class. + (nrClass == SmallInteger) ifFalse:[ + (nrClass == self class) ifFalse:[ ^ super divMod:aNumber ]. - n := aNumber. ]. - ^ self absDivMod:n abs. + ^ self absDivMod:aNumber. " 9000000000 // 4000000000 => 2 9000000000 \\ 4000000000 => 1000000000 + 9000000000 divMod: 4000000000 => #(2 1000000000) + -9000000000 divMod: 4000000000 => #(-3 3000000000) + 9000000000 divMod: -4000000000 => #(-3 -3000000000) + -9000000000 divMod: -4000000000 => #(2 -1000000000) + + 9000000000000000000 absDivMod: 400000000000000 => #(22500 0) + -9000000000000000000 absDivMod: 400000000000000 => #(22500 0) + 9000000000000000000 absDivMod: -400000000000000 => #(22500 0) + -9000000000000000000 absDivMod: -400000000000000 => #(22500 0) + + 9000000000000000000 absDivMod: 4000000000000000 => #(2250 0) + -9000000000000000000 absDivMod: 4000000000000000 => #(2250 0) + 9000000000000000000 absDivMod: -4000000000000000 => #(2250 0) + -9000000000000000000 absDivMod: -4000000000000000 => #(2250 0) + + 9000000000000000000 absDivMod: 4000000000000000000 => #(2 1000000000000000000) + -9000000000000000000 absDivMod: 4000000000000000000 => #(2 1000000000000000000) + 9000000000000000000 absDivMod: -4000000000000000000 => #(2 1000000000000000000) + -9000000000000000000 absDivMod: -4000000000000000000 => #(2 1000000000000000000) " "Created: / 29.10.1996 / 21:22:05 / cg" @@ -824,43 +795,23 @@ "return the quotient of the receiver and the argument, aNumber. The result is truncated toward zero (which is different from //, which truncates toward negative infinity). - The results sign is negative if the receiver has a sign - different from the args sign. + The result's sign is negative if the receiver has a sign different from the arg's sign. The following is always true: (receiver quo: aNumber) * aNumber + (receiver rem: aNumber) = receiver " - |otherSign quo abs "{ Class: SmallInteger }" | - - otherSign := aNumber sign. - - " - this is the common case, dividing by a SmallInteger. - Use a special method for this case ... - " - (aNumber class == SmallInteger) ifTrue:[ - abs := aNumber. - abs := abs abs. - (abs between:1 and:16r00ffffff) ifTrue:[ - quo := (self absFastDivMod:abs) at:1. - (sign == otherSign) ifTrue:[^ quo]. - ^ quo setSign:-1 - ] - ]. - - " - if the argument is not a largeInteger, coerce - " - (aNumber class == self class) ifFalse:[ + |nrClass quo | + + nrClass := aNumber class. + ((nrClass == SmallInteger) or:[ nrClass == self class] ) ifFalse:[ ^ self retry:#quo: coercing:aNumber ]. - - sign < 0 ifTrue:[ - (sign == otherSign) ifTrue:[^ (self absDivMod:aNumber negated) at:1]. - ] ifFalse:[ - (sign == otherSign) ifTrue:[^ (self absDivMod:aNumber) at:1]. + + quo := (self absDivMod:aNumber) at:1. + (sign == aNumber sign) ifTrue:[ + ^ quo ]. - ^ ((self absDivMod:aNumber) at:1) setSign:-1 + ^ quo setSign:-1 " 900 // 400 @@ -895,33 +846,17 @@ (receiver quo: aNumber) * aNumber + (receiver rem: aNumber) = receiver " - |rem abs "{ Class: SmallInteger }" | - - " - this is the common case, dividing by a SmallInteger. - Use special code for this case ... - " - (aNumber class == SmallInteger) ifTrue:[ - abs := aNumber. - abs := abs abs. - (abs between:1 and:16r00ffffff) ifTrue:[ - rem := (self absFastDivMod:abs) at:2. - ] ifFalse:[ - rem := self absMod:abs asLargeInteger + |nrClass rem| + + nrClass := aNumber class. + ((nrClass == SmallInteger) or:[ nrClass == self class ]) ifFalse:[ + ^ self retry:#rem coercing:aNumber + ]. + rem := (self absDivMod:aNumber) at:2. + rem ~~ 0 ifTrue:[ + sign < 0 ifTrue:[ + ^ rem setSign:-1 ]. - ] ifFalse:[ - " - if the argument is not a largeInteger, coerce - " - (aNumber class == self class) ifFalse:[ - ^ self retry:#rem coercing:aNumber - ]. - - rem := self absMod:aNumber - ]. - - sign < 0 ifTrue:[ - ^ rem setSign:-1 ]. ^ rem @@ -2831,6 +2766,218 @@ !LargeInteger methodsFor:'private'! +absDestructiveSubtract:aLargeInteger + "private helper for division: + destructively subtract aLargeInteger from myself + AND return true, if the result is non-zero, false otherwise. + (i.e. this method has both a return value and a side-effect on the receiver) + Does not care about the signs of the receiver and argument + The receiver must be >= the argument. + The receiver must be a temporary scratch-number" + + |otherDigitByteArray + len1 "{ Class: SmallInteger }" + len2 "{ Class: SmallInteger }" + index "{ Class: SmallInteger }" + borrow "{ Class: SmallInteger }" + diff "{ Class: SmallInteger }" + notZero + | + + notZero := false. + len1 := digitByteArray size. + otherDigitByteArray := aLargeInteger digitBytes. + len2 := otherDigitByteArray size. + len2 > len1 ifTrue:[ + [(otherDigitByteArray at:len2) == 0] whileTrue:[ + len2 := len2 - 1 + ]. + len2 > len1 ifTrue:[ + self error:'operation failed' "/ may not be called that way + ]. + ]. + "/ knowing that len2 is <= len1 +%{ + + OBJ _digitByteArray = __INST(digitByteArray); + + if (__isByteArray(_digitByteArray) + && __isByteArray(otherDigitByteArray)) { + int _len1 = __intVal(len1), + _len2 = __intVal(len2); + unsigned char *_myDigits, *_otherDigits; + int _index = 1, _borrow = 0; + INT _diff; + int anyBitNonZero = 0; + + _otherDigits = __ByteArrayInstPtr(otherDigitByteArray)->ba_element; + _myDigits = __ByteArrayInstPtr(_digitByteArray)->ba_element; + +#if defined(__LSBFIRST__) +# if __POINTER_SIZE__ == 8 + { + int _len2Q; + /* + * subtract int-wise + */ + _len2Q = _len2-4; + while (_index <= _len2Q) { + /* do not combine the expression below (may lead to unsigned result on some machines) */ + _diff = ((unsigned int *)(_myDigits+_index-1))[0]; + _diff -= ((unsigned int *)(_otherDigits+_index-1))[0]; + _diff -= _borrow; + if (_diff >= 0) { + _borrow = 0; + } else { + _borrow = 1; + /* _diff += 0x100000000; */ + } + ((unsigned int *)(_myDigits+_index-1))[0] = _diff; + anyBitNonZero |= (_diff & 0xFFFFFFFFL); + _index += 4; + } + } +# endif + + /* + * subtract short-wise + */ + while (_index < _len2) { + /* do not combine the expression below (may lead to unsigned result on some machines */ + _diff = ((unsigned short *)(_myDigits+_index-1))[0]; + _diff -= ((unsigned short *)(_otherDigits+_index-1))[0]; + _diff -= _borrow; + if (_diff >= 0) { + _borrow = 0; + } else { + _borrow = 1; + /* _diff += 0x10000; */ + } + ((unsigned short *)(_myDigits+_index-1))[0] = _diff; + anyBitNonZero |= (_diff & 0xFFFF); + _index += 2; + } + + if (_index <= _len2) { + /* + * cannot continue with shorts - there is an odd number of + * bytes in the minuent + */ + } else { + while (_index < _len1) { + /* do not combine the expression below (may lead to unsigned result on some machines */ + _diff = ((unsigned short *)(_myDigits+_index-1))[0]; + _diff -= _borrow; + if (_diff >= 0) { + /* _borrow = 0; */ + ((unsigned short *)(_myDigits+_index-1))[0] = _diff; + anyBitNonZero |= (_diff & 0xFFFF); + _index += 2; + while (_index < _len1) { + anyBitNonZero |= ((unsigned short *)(_myDigits+_index-1))[0]; + if (anyBitNonZero) { + RETURN (true); + } + _index += 2; + } + /* last odd index */ + if (_index <= _len1) { + anyBitNonZero |= _myDigits[_index - 1];; + if (anyBitNonZero) { + RETURN (true); + } + _index++; + } + RETURN (anyBitNonZero ? true : false); + } + _borrow = 1; + /* _diff += 0x10000; */ + + ((unsigned short *)(_myDigits+_index-1))[0] = _diff; + anyBitNonZero |= (_diff & 0xFFFF); + _index += 2; + } + } +#endif + /* + * subtract byte-wise + */ + while (_index <= _len2) { + /* do not combine the expression below (may lead to unsigned result on some machines */ + _diff = _myDigits[_index - 1]; + _diff -= _otherDigits[_index - 1]; + _diff -= _borrow; + if (_diff >= 0) { + _borrow = 0; + } else { + _borrow = 1; + /* _diff += 0x100; */ + } + _myDigits[_index - 1] = _diff; + anyBitNonZero |= (_diff & 0xFF); + _index++; + } + + while (_index <= _len1) { + /* do not combine the expression below (may lead to unsigned result on some machines */ + _diff = _myDigits[_index - 1]; + _diff -= _borrow; + if (_diff >= 0) { + /* _borrow = 0; */ + _myDigits[_index - 1] = _diff; + anyBitNonZero |= (_diff & 0xFF); + _index++; + while (_index <= _len1) { + anyBitNonZero |= _myDigits[_index - 1]; + if (anyBitNonZero) { + RETURN (true); + } + _index++; + } + break; + } + _borrow = 1; + /* _diff += 0x100; */ + + _myDigits[_index - 1] = _diff; + anyBitNonZero |= (_diff & 0xFF); + _index++; + } + RETURN (anyBitNonZero ? true : false); + } +%}. + + index := 1. + borrow := 0. + + [index <= len1] whileTrue:[ + diff := borrow. + diff := diff + (digitByteArray basicAt:index). + index <= len2 ifTrue:[ + diff := diff - (otherDigitByteArray basicAt:index). + ]. + + "/ workaround for gcc code generator bug + (diff >= 0) ifTrue:[ + borrow := 0 + ] ifFalse:[ + borrow := -1. + diff := diff + 16r100 + ]. + diff ~~ 0 ifTrue:[ + notZero := true + ]. + digitByteArray basicAt:index put:diff. + index := index + 1 + ]. + + ^ notZero + + "Created: / 5.11.1996 / 16:23:47 / cg" + "Modified: / 5.11.1996 / 18:56:50 / cg" + "Modified: / 27.4.1999 / 18:08:23 / stefan" +! + absDivMod:anInteger "return an array with two LargeIntegers representing abs(self) // abs(theArgument) and abs(self) \\ abs(theArgument). @@ -2839,25 +2986,34 @@ |dividend divisor quo digits + divModOrNil shift "{ Class: SmallInteger }" | anInteger == 0 ifTrue:[ ^ ZeroDivide raiseRequestWith:thisContext ]. - self = anInteger ifTrue:[ - ^ Array with:1 with:0 + anInteger class == SmallInteger ifTrue:[ + divisor := anInteger abs. + divModOrNil := self absFastDivMod:divisor. + divModOrNil notNil ifTrue:[^ divModOrNil]. + divisor := divisor asLargeInteger. + ] ifFalse:[ + self = anInteger ifTrue:[ + ^ Array with:1 with:0 + ]. + divisor := anInteger. ]. - - shift := self highBit - anInteger highBit. + + shift := self highBit - divisor highBit. dividend := self class digitBytes:digitByteArray copy. "/ self simpleDeepCopy sign:1. shift < 0 ifTrue:[ ^ Array with:0 with:dividend compressed. ]. shift == 0 ifTrue:[ - divisor := self class digitBytes:(anInteger digitBytes copy). "/ anInteger simpleDeepCopy. + divisor := self class digitBytes:(divisor digitBytes copy). "/ anInteger simpleDeepCopy. ] ifFalse:[ - divisor := anInteger bitShift:shift. + divisor := divisor bitShift:shift. ]. quo := self class basicNew numberOfDigits:((shift // 8) + 1). @@ -2867,7 +3023,7 @@ [shift > 0] whileTrue:[ (dividend absLess:divisor) ifFalse:[ digits bitSetAt:shift. - (dividend absSubtract: divisor) ifFalse:[ "result == 0" + (dividend absDestructiveSubtract: divisor) ifFalse:[ "result == 0" ^ Array with:quo compressed with:0 ]. ]. @@ -2986,8 +3142,9 @@ absFastDivMod:aPositiveSmallInteger "return an array with two LargeIntegers representing - abs(self) // aPositiveSmallInteger and - abs(self) \\ aPositiveSmallInteger." + abs(self) // aPositiveSmallInteger and + abs(self) \\ aPositiveSmallInteger + or nil, if not computed by optimized code" |tmp1 "{ Class: SmallInteger }" prevRest "{ Class: SmallInteger }" @@ -3128,11 +3285,11 @@ slow code - not normally reached (could also do a primitiveFailure here) " - ok ifFalse:[ - ^ self absDivMod:(self class value:aPositiveSmallInteger). + ok ifTrue:[ + ^ Array with:(result compressed) with:prevRest ]. - - ^ Array with:(result compressed) with:prevRest + ^ nil + " 16r123412341234 asLargeInteger absDivMod:(LargeInteger value:10) @@ -4199,7 +4356,7 @@ shift := shift + 1. [shift > 0] whileTrue:[ (dividend absLess:divisor) ifFalse:[ - (dividend absSubtract: divisor) ifFalse:[ "result == 0" + (dividend absDestructiveSubtract: divisor) ifFalse:[ "result == 0" ^ 0 ]. ]. @@ -5099,221 +5256,6 @@ "Modified: 11.8.1997 / 03:23:37 / cg" ! -absSubtract:aLargeInteger - "private helper for division: - destructively subtract aLargeInteger from myself - AND return true, if the result is non-zero, false otherwise. - (i.e. this method has both a return value and a side-effect - on the receiver) - Only allowed for positive receiver and argument - The receiver must be >= the argument. - The receiver must be a temporary scratch-number" - - |otherDigitByteArray - len1 "{ Class: SmallInteger }" - len2 "{ Class: SmallInteger }" - index "{ Class: SmallInteger }" - borrow "{ Class: SmallInteger }" - diff "{ Class: SmallInteger }" - notZero - | - - notZero := false. - len1 := digitByteArray size. - otherDigitByteArray := aLargeInteger digitBytes. - len2 := otherDigitByteArray size. - len2 > len1 ifTrue:[ - [(otherDigitByteArray at:len2) == 0] whileTrue:[ - len2 := len2 - 1 - ]. - len2 > len1 ifTrue:[ - self error:'operation failed' "/ may not be called that way - ]. - ]. - "/ knowing that len2 is <= len1 -%{ - - OBJ _digitByteArray = __INST(digitByteArray); - - if (__isByteArray(_digitByteArray) - && __isByteArray(otherDigitByteArray)) { - int _len1 = __intVal(len1), - _len2 = __intVal(len2); - unsigned char *_myDigits, *_otherDigits; - int _index = 1, _borrow = 0; - INT _diff; - int anyBitNonZero = 0; - - _otherDigits = __ByteArrayInstPtr(otherDigitByteArray)->ba_element; - _myDigits = __ByteArrayInstPtr(_digitByteArray)->ba_element; - -#if defined(__LSBFIRST__) -# if __POINTER_SIZE__ == 8 - { - int _len2Q; - /* - * subtract int-wise - */ - _len2Q = _len2-2; - while (_index < _len2Q) { - /* do not combine the expression below (may lead to unsigned result on some machines */ - _diff = ((unsigned int *)(_myDigits+_index-1))[0]; - _diff -= ((unsigned int *)(_otherDigits+_index-1))[0]; - _diff -= _borrow; - if (_diff >= 0) { - _borrow = 0; - } else { - _borrow = 1; - /* _diff += 0x10000; */ - } - ((unsigned int *)(_myDigits+_index-1))[0] = _diff; - anyBitNonZero |= (_diff & 0xFFFFFFFFL); - _index += 4; - } - } -# endif - - /* - * subtract short-wise - */ - while (_index < _len2) { - /* do not combine the expression below (may lead to unsigned result on some machines */ - _diff = ((unsigned short *)(_myDigits+_index-1))[0]; - _diff -= ((unsigned short *)(_otherDigits+_index-1))[0]; - _diff -= _borrow; - if (_diff >= 0) { - _borrow = 0; - } else { - _borrow = 1; - /* _diff += 0x10000; */ - } - ((unsigned short *)(_myDigits+_index-1))[0] = _diff; - anyBitNonZero |= (_diff & 0xFFFF); - _index += 2; - } - - if (_index <= _len2) { - /* - * cannot continue with shorts - there is an odd number of - * bytes in the minuent - */ - } else { - while (_index < _len1) { - /* do not combine the expression below (may lead to unsigned result on some machines */ - _diff = ((unsigned short *)(_myDigits+_index-1))[0]; - _diff -= _borrow; - if (_diff >= 0) { - /* _borrow = 0; */ - ((unsigned short *)(_myDigits+_index-1))[0] = _diff; - anyBitNonZero |= (_diff & 0xFFFF); - _index += 2; - while (_index < _len1) { - anyBitNonZero |= ((unsigned short *)(_myDigits+_index-1))[0]; - if (anyBitNonZero) { - RETURN (true); - } - _index += 2; - } - /* last odd index */ - if (_index <= _len1) { - anyBitNonZero |= _myDigits[_index - 1];; - if (anyBitNonZero) { - RETURN (true); - } - _index++; - } - RETURN (anyBitNonZero ? true : false); - } - _borrow = 1; - /* _diff += 0x10000; */ - - ((unsigned short *)(_myDigits+_index-1))[0] = _diff; - anyBitNonZero |= (_diff & 0xFFFF); - _index += 2; - } - } -#endif - /* - * subtract byte-wise - */ - while (_index <= _len2) { - /* do not combine the expression below (may lead to unsigned result on some machines */ - _diff = _myDigits[_index - 1]; - _diff -= _otherDigits[_index - 1]; - _diff -= _borrow; - if (_diff >= 0) { - _borrow = 0; - } else { - _borrow = 1; - /* _diff += 0x100; */ - } - _myDigits[_index - 1] = _diff; - anyBitNonZero |= (_diff & 0xFF); - _index++; - } - - while (_index <= _len1) { - /* do not combine the expression below (may lead to unsigned result on some machines */ - _diff = _myDigits[_index - 1]; - _diff -= _borrow; - if (_diff >= 0) { - /* _borrow = 0; */ - _myDigits[_index - 1] = _diff; - anyBitNonZero |= (_diff & 0xFF); - _index++; - while (_index <= _len1) { - anyBitNonZero |= _myDigits[_index - 1]; - if (anyBitNonZero) { - RETURN (true); - } - _index++; - } - break; - } - _borrow = 1; - /* _diff += 0x100; */ - - _myDigits[_index - 1] = _diff; - anyBitNonZero |= (_diff & 0xFF); - _index++; - } - RETURN (anyBitNonZero ? true : false); - } -%}. - - index := 1. - borrow := 0. - - [index <= len1] whileTrue:[ - diff := borrow. - diff := diff + (digitByteArray basicAt:index). - index <= len2 ifTrue:[ - diff := diff - (otherDigitByteArray basicAt:index). - ]. - - "/ workaround for - "/ gcc code generator bug - - (diff >= 0) ifTrue:[ - borrow := 0 - ] ifFalse:[ - borrow := -1. - diff := diff + 16r100 - ]. - diff ~~ 0 ifTrue:[ - notZero := true - ]. - digitByteArray basicAt:index put:diff. - index := index + 1 - ]. - - ^ notZero - - "Created: / 5.11.1996 / 16:23:47 / cg" - "Modified: / 5.11.1996 / 18:56:50 / cg" - "Modified: / 27.4.1999 / 18:08:23 / stefan" -! - div2 "private helper for division: destructively divide the receiver by 2.