--- a/LargeInt.st Tue Nov 05 19:25:59 1996 +0100
+++ b/LargeInt.st Tue Nov 05 19:26:35 1996 +0100
@@ -257,7 +257,7 @@
The result is truncated toward negative infinity and negative,
if the operands signs differ."
- |otherSign divMod d rem abs "{ Class: SmallInteger }" n|
+ |otherSign divMod d quo abs "{ Class: SmallInteger }" n|
otherSign := aNumber sign.
@@ -270,14 +270,14 @@
abs := abs abs.
(abs between:1 and:16r003fffff) ifTrue:[
divMod := self absFastDiv:abs.
- rem := divMod at:1.
- (sign == otherSign) ifTrue:[^ rem].
+ quo := divMod at:1.
+ (sign == otherSign) ifTrue:[^ quo].
"/ stupid adjust ...
(divMod at:2) == 0 ifFalse:[
- ^ (rem sign:-1) - 1
+ ^ (quo sign:-1) - 1
].
- ^ rem sign:-1
+ ^ quo sign:-1
].
n := aNumber asLargeInteger.
] ifFalse:[
@@ -291,18 +291,16 @@
^ self retry:#// coercing:aNumber
].
- sign < 0 ifTrue:[
- (sign == otherSign) ifTrue:[^ (self absDiv:n negated) at:1].
- ] ifFalse:[
- (sign == otherSign) ifTrue:[^ (self absDiv:n) at:1].
- ].
+ divMod := self absDiv:n.
+
+ (sign == otherSign) ifTrue:[^ divMod at:1].
- divMod := self absDiv:n.
- "/ stupid adjust ...
+ "/ stupid adjust for truncation ...
+ quo := divMod at:1.
(divMod at:2) == 0 ifFalse:[
- ^ ((divMod at:1) sign:-1) - 1
+ ^ (quo sign:-1) - 1
].
- ^ (divMod at:1) sign:-1
+ ^ quo sign:-1
"
900 // 400
@@ -326,7 +324,7 @@
-9000000000 quo: -4000000000
"
- "Modified: 5.11.1996 / 14:16:46 / cg"
+ "Modified: 5.11.1996 / 16:39:36 / cg"
!
\\ aNumber
@@ -359,7 +357,7 @@
].
aNumber negative ifTrue:[
- ^ rem negated
+ ^ rem sign:-1
].
^ rem
@@ -374,6 +372,11 @@
9000000000 \\ -4000000000
-9000000000 \\ -4000000000
+ 9000000000 \\ 7
+ -9000000000 \\ 7
+ 9000000000 \\ -7
+ -9000000000 \\ -7
+
900 rem: 400
-900 rem: 400
900 rem: -400
@@ -385,7 +388,7 @@
-9000000000 rem: -4000000000
"
- "Modified: 5.11.1996 / 13:54:32 / cg"
+ "Modified: 5.11.1996 / 17:10:10 / cg"
!
divMod:aNumber
@@ -766,36 +769,38 @@
overhead of producing any intermediate byte-arrays (and the scanning)
"
(aSmallInteger == 0) ifTrue: [
- digitByteArray := #[0].
- sign := 0.
- ^ self
+ digitByteArray := ByteArray with:0.
+ sign := 0.
+ ^ self
].
(aSmallInteger < 0) ifTrue: [
- sign := -1.
- absValue := aSmallInteger negated
+ sign := -1.
+ absValue := aSmallInteger negated
] ifFalse: [
- sign := 1.
- absValue := aSmallInteger
+ sign := 1.
+ absValue := aSmallInteger
].
b1 := absValue bitAnd:16rFF.
absValue := absValue bitShift:-8.
absValue == 0 ifTrue:[
- digitByteArray := ByteArray with:b1
+ digitByteArray := ByteArray with:b1
] ifFalse:[
- b2 := absValue bitAnd:16rFF.
- absValue := absValue bitShift:-8.
- absValue == 0 ifTrue:[
- digitByteArray := ByteArray with:b1 with:b2
- ] ifFalse:[
- b3 := absValue bitAnd:16rFF.
- absValue := absValue bitShift:-8.
- absValue == 0 ifTrue:[
- digitByteArray := ByteArray with:b1 with:b2 with:b3
- ] ifFalse:[
- digitByteArray := ByteArray with:b1 with:b2 with:b3 with:absValue
- ]
- ]
+ b2 := absValue bitAnd:16rFF.
+ absValue := absValue bitShift:-8.
+ absValue == 0 ifTrue:[
+ digitByteArray := ByteArray with:b1 with:b2
+ ] ifFalse:[
+ b3 := absValue bitAnd:16rFF.
+ absValue := absValue bitShift:-8.
+ absValue == 0 ifTrue:[
+ digitByteArray := ByteArray with:b1 with:b2 with:b3
+ ] ifFalse:[
+ digitByteArray := ByteArray with:b1 with:b2 with:b3 with:absValue
+ ]
+ ]
]
+
+ "Modified: 5.11.1996 / 16:15:39 / cg"
! !
!LargeInteger methodsFor:'comparing'!
@@ -1054,7 +1059,7 @@
This method needs a rewrite."
|tmp1 tmp2
- rem
+ quo
count "{ Class: SmallInteger }"
digit "{ Class: SmallInteger }" |
@@ -1076,29 +1081,40 @@
].
count := 0.
- [tmp2 < tmp1] whileTrue:[
- tmp2 mul256.
+ [tmp2 absLess: tmp1] whileTrue:[
+ tmp2 mul2.
count := count + 1
].
- tmp2 div256.
+ tmp2 div2.
- rem := 0 asLargeInteger.
- rem sign:1.
+ quo := 0 asLargeInteger.
+ quo sign:1.
[count == 0] whileFalse:[
- digit := 0.
- [tmp1 >= tmp2] whileTrue:[
- digit := digit + 1.
- tmp1 := tmp1 - tmp2
+ quo mul2.
+ (tmp1 absLess:tmp2) ifFalse:[
+ quo digits at:1 put:((quo digits at:1) bitOr:1).
+ (tmp1 absSubtract: tmp2) ifFalse:[
+ "/ difference is zero; continue shifting
+ count := count - 1.
+ [count >= 8] whileTrue:[
+ quo mul256.
+ count := count - 8
+ ].
+ [count == 0] whileFalse:[
+ quo mul2.
+ count := count - 1.
+ ].
+ ^ Array with:quo compressed with:tmp1 compressed
+ ].
].
- rem := (rem * 256) + digit.
- tmp2 div256.
+ tmp2 div2.
count := count - 1
].
- ^ Array with:rem with:tmp1
+ ^ Array with:quo compressed with:tmp1 compressed
- "Modified: 5.11.1996 / 13:46:14 / cg"
+ "Modified: 5.11.1996 / 18:40:24 / cg"
!
absEq:aLargeInteger
@@ -1130,9 +1146,9 @@
^ true
!
-absFastDiv:aSmallInteger
+absFastDiv:aPositiveSmallInteger
"return an array with two LargeIntegers representing
- abs(self) // aSmallInteger and abs(self) \\ aSmallInteger"
+ abs(self) // aPositiveSmallInteger and abs(self) \\ aPositiveSmallInteger"
|tmp1 "{ Class: SmallInteger }"
prevRest "{ Class: SmallInteger }"
@@ -1140,12 +1156,12 @@
newDigitByteArray result
ok|
- aSmallInteger == 0 ifTrue:[
+ aPositiveSmallInteger == 0 ifTrue:[
^ DivisionByZeroSignal raise
].
"This cannot happen (if always normalized)
- self < aSmallInteger ifTrue:[
+ self < aPositiveSmallInteger ifTrue:[
^ Array with:0 with:self
].
"
@@ -1160,31 +1176,34 @@
if (__isByteArray(__digits)
&& __isByteArray(newDigitByteArray)
- && __bothSmallInteger(count, aSmallInteger)) {
+ && __bothSmallInteger(count, aPositiveSmallInteger)) {
unsigned int rest = 0;
int index = __intVal(count);
int index0;
- int divisor = __intVal(aSmallInteger);
+ unsigned divisor = __intVal(aPositiveSmallInteger);
unsigned char *digitBytes = __ByteArrayInstPtr(__digits)->ba_element;
unsigned char *resultBytes = __ByteArrayInstPtr(newDigitByteArray)->ba_element;
index0 = index;
- while (index > 1) {
- unsigned int t;
- unsigned div;
+/*
+ if (divisor < 0xFFFF) {
+ while (index > 1) {
+ unsigned int t;
+ unsigned div;
- index--;
- t = digitBytes[index];
- index--;
- t = (t << 8) | digitBytes[index];
- t = t | (rest << 16);
- div = t / divisor;
- rest = t % divisor;
- resultBytes[index+1] = (div >> 8);
- resultBytes[index] = (div & 0xFF);
+ index--;
+ t = digitBytes[index];
+ index--;
+ t = (t << 8) | digitBytes[index];
+ t = t | (rest << 16);
+ div = t / divisor;
+ rest = t % divisor;
+ resultBytes[index+1] = (div >> 8);
+ resultBytes[index] = (div & 0xFF);
+ }
}
-
+*/
while (index > 0) {
unsigned int t;
@@ -1211,13 +1230,7 @@
(could also do a primitiveFailure here)
"
ok ifFalse:[
- prevRest := 0.
- count to:1 by:-1 do:[:i |
- tmp1 := digitByteArray at:i.
- tmp1 := (tmp1 + (prevRest * 256)).
- newDigitByteArray at:i put:tmp1 // aSmallInteger.
- prevRest := (tmp1 \\ aSmallInteger).
- ]
+ self primitiveFailed
].
^ Array with:result compressed with:prevRest
@@ -1316,35 +1329,40 @@
!
absLess:aLargeInteger
- "return true, if abs(self) < abs(theArgument)"
+ "return true, if abs(self) < abs(theArgument).
+ This handles unnormalized largeIntegers."
- |len1 "{ Class: SmallInteger }"
- len2 "{ Class: SmallInteger }"
+ |myLen "{ Class: SmallInteger }"
+ otherLen "{ Class: SmallInteger }"
d1 "{ Class: SmallInteger }"
d2 "{ Class: SmallInteger }"
otherDigitByteArray |
- len1 := digitByteArray size.
+ myLen := digitByteArray size.
otherDigitByteArray := aLargeInteger digits.
- len2 := otherDigitByteArray size.
+ otherLen := otherDigitByteArray size.
- [(digitByteArray basicAt:len1) == 0] whileTrue:[
- len1 := len1 - 1
+ [(digitByteArray basicAt:myLen) == 0] whileTrue:[
+ myLen := myLen - 1
].
- [(otherDigitByteArray basicAt:len2) == 0] whileTrue:[
- len2 := len2 - 1
+ [(otherDigitByteArray basicAt:otherLen) == 0] whileTrue:[
+ otherLen := otherLen - 1
].
- (len1 < len2) ifTrue:[^ true].
- (len1 > len2) ifTrue:[^ false].
+ (myLen < otherLen) ifTrue:[^ true].
+ (myLen > otherLen) ifTrue:[^ false].
- [len1 > 0] whileTrue:[
- d1 := digitByteArray basicAt:len1.
- d2 := otherDigitByteArray basicAt:len1.
- (d1 < d2) ifTrue:[^ true].
- (d1 > d2) ifTrue:[^ false].
- len1 := len1 - 1
+ [myLen > 0] whileTrue:[
+ d1 := digitByteArray basicAt:myLen.
+ d2 := otherDigitByteArray basicAt:myLen.
+ d1 == d2 ifFalse:[
+ (d1 < d2) ifTrue:[^ true].
+ ^ false
+ ].
+ myLen := myLen - 1
].
^ false
+
+ "Modified: 5.11.1996 / 18:37:27 / cg"
!
absMinus:aLargeInteger
@@ -1563,12 +1581,181 @@
"Modified: 5.11.1996 / 14:09:34 / cg"
!
-div256
- "destructively divide the receiver by 256.
- private - used for division only"
+absSubtract:aLargeInteger
+ "destructively subtract aLargeInteger from myself.
+ A helper for division; only allowed for positive receiver
+ and argument. The receiver must be >= the argument.
+ The receiver must be a temporary scratch-number"
+
+ |result done
+ otherDigitByteArray resultDigitByteArray
+ len1 "{ Class: SmallInteger }"
+ len2 "{ Class: SmallInteger }"
+ index "{ Class: SmallInteger }"
+ borrow "{ Class: SmallInteger }"
+ diff "{ Class: SmallInteger }"
+ carry "{ Class: SmallInteger }"
+ lResult nonZero|
+
+ len1 := digitByteArray size.
+ otherDigitByteArray := aLargeInteger digits.
+ len2 := otherDigitByteArray size.
+ len2 > len1 ifTrue:[
+ [(otherDigitByteArray at:len2) == 0] whileTrue:[
+ len2 := len2 - 1
+ ].
+ len2 > len1 ifTrue:[
+ self halt "/ may not be called that way
+ ].
+ ].
+
+ nonZero := false.
+ index := 1.
+ borrow := 0.
+
+ done := false.
+ [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:[
+ nonZero := true
+ ].
+ digitByteArray basicAt:index put:diff.
+ index := index + 1
+ ].
+ ^ nonZero
+
+ "Created: 5.11.1996 / 16:23:47 / cg"
+ "Modified: 5.11.1996 / 18:56:50 / cg"
+!
+
+div2
+ "destructively divide the receiver by 2.
+ private - used for division only.
+ This is worth a primitive."
+
+%{ /* NOCONTEXT */
+ OBJ __digits = __INST(digitByteArray);
+
+ if (__isByteArray(__digits)) {
+ int __nBytes = __byteArraySize(__digits);
+ unsigned char *__bp = __ByteArrayInstPtr(__digits)->ba_element;
+ unsigned __this, __next;
+ int __idx;
+
+ if (__nBytes == 1) {
+ __bp[0] >>= 1;
+ RETURN (self);
+ }
+
+ __idx = 1;
+
+ if ((__idx+4) < __nBytes) {
+ __this = ((unsigned long *)__bp)[0];
- digitByteArray replaceFrom:1 with:digitByteArray startingAt:2.
- digitByteArray at:(digitByteArray size) put:0
+ while ((__idx+4) < __nBytes) {
+ __next = ((unsigned long *)__bp)[1];
+ __this >>= 1;
+ __this |= __next << 31;
+ ((unsigned long *)__bp)[0] = __this;
+ __this = __next;
+ __bp += 4;
+ __idx += 4;
+ }
+ }
+
+ __this = __bp[0];
+ while (__idx < __nBytes) {
+ __next = __bp[1];
+ __this >>= 1;
+ __this |= __next << 7;
+ __bp[0] = __this;
+ __this = __next;
+ __bp++;
+ __idx++;
+ }
+ __bp[0] = __this >> 1;
+ RETURN (self);
+ }
+%}.
+ self primitiveFailed
+
+ "
+ 100000 asLargeInteger div2
+ "
+
+ "Modified: 5.11.1996 / 16:12:56 / cg"
+!
+
+mul2
+ "destructively multiply the receiver by 2.
+ private - used for division only.
+ This is worth a primitive."
+
+ |nBytes "{ Class: SmallInteger }"
+ b "{ Class: SmallInteger }"
+ t|
+
+ nBytes := digitByteArray size.
+
+ b := digitByteArray at:nBytes.
+ (b bitAnd:16r80) ~~ 0 ifTrue:[
+ "/ need another byte
+ nBytes := nBytes + 1.
+ t := ByteArray uninitializedNew:nBytes.
+ t replaceFrom:1 with:digitByteArray.
+ t at:nBytes put:0.
+ digitByteArray := t.
+ ].
+
+%{
+ OBJ __digits = __INST(digitByteArray);
+
+ if (__isByteArray(__digits)) {
+ int __nBytes = __intVal(nBytes);
+ unsigned char *__bp = __ByteArrayInstPtr(__digits)->ba_element;
+ unsigned __carry = 0, __newCarry, __this;
+ int __idx;
+
+ while (__nBytes >= 4) {
+ __this = ((unsigned long *)__bp)[0];
+ __newCarry = __this >> 31;
+ ((unsigned long *)__bp)[0] = (__this << 1) | __carry;
+ __carry = __newCarry;
+ __bp += 4;
+ __nBytes -= 4;
+ }
+ while (__nBytes) {
+ __this = __bp[0];
+ __newCarry = __this >> 7;
+ __bp[0] = (__this << 1) | __carry;
+ __carry = __newCarry;
+ __bp ++;
+ __nBytes--;
+ }
+ RETURN (self);
+ }
+%}.
+ self primitiveFailed
+
+ "
+ 100000 asLargeInteger mul2
+ "
+
+ "Modified: 5.11.1996 / 16:37:32 / cg"
!
mul256
@@ -1638,5 +1825,5 @@
!LargeInteger class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic/Attic/LargeInt.st,v 1.36 1996-11-05 13:31:25 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/Attic/LargeInt.st,v 1.37 1996-11-05 18:26:35 cg Exp $'
! !
--- a/LargeInteger.st Tue Nov 05 19:25:59 1996 +0100
+++ b/LargeInteger.st Tue Nov 05 19:26:35 1996 +0100
@@ -257,7 +257,7 @@
The result is truncated toward negative infinity and negative,
if the operands signs differ."
- |otherSign divMod d rem abs "{ Class: SmallInteger }" n|
+ |otherSign divMod d quo abs "{ Class: SmallInteger }" n|
otherSign := aNumber sign.
@@ -270,14 +270,14 @@
abs := abs abs.
(abs between:1 and:16r003fffff) ifTrue:[
divMod := self absFastDiv:abs.
- rem := divMod at:1.
- (sign == otherSign) ifTrue:[^ rem].
+ quo := divMod at:1.
+ (sign == otherSign) ifTrue:[^ quo].
"/ stupid adjust ...
(divMod at:2) == 0 ifFalse:[
- ^ (rem sign:-1) - 1
+ ^ (quo sign:-1) - 1
].
- ^ rem sign:-1
+ ^ quo sign:-1
].
n := aNumber asLargeInteger.
] ifFalse:[
@@ -291,18 +291,16 @@
^ self retry:#// coercing:aNumber
].
- sign < 0 ifTrue:[
- (sign == otherSign) ifTrue:[^ (self absDiv:n negated) at:1].
- ] ifFalse:[
- (sign == otherSign) ifTrue:[^ (self absDiv:n) at:1].
- ].
+ divMod := self absDiv:n.
+
+ (sign == otherSign) ifTrue:[^ divMod at:1].
- divMod := self absDiv:n.
- "/ stupid adjust ...
+ "/ stupid adjust for truncation ...
+ quo := divMod at:1.
(divMod at:2) == 0 ifFalse:[
- ^ ((divMod at:1) sign:-1) - 1
+ ^ (quo sign:-1) - 1
].
- ^ (divMod at:1) sign:-1
+ ^ quo sign:-1
"
900 // 400
@@ -326,7 +324,7 @@
-9000000000 quo: -4000000000
"
- "Modified: 5.11.1996 / 14:16:46 / cg"
+ "Modified: 5.11.1996 / 16:39:36 / cg"
!
\\ aNumber
@@ -359,7 +357,7 @@
].
aNumber negative ifTrue:[
- ^ rem negated
+ ^ rem sign:-1
].
^ rem
@@ -374,6 +372,11 @@
9000000000 \\ -4000000000
-9000000000 \\ -4000000000
+ 9000000000 \\ 7
+ -9000000000 \\ 7
+ 9000000000 \\ -7
+ -9000000000 \\ -7
+
900 rem: 400
-900 rem: 400
900 rem: -400
@@ -385,7 +388,7 @@
-9000000000 rem: -4000000000
"
- "Modified: 5.11.1996 / 13:54:32 / cg"
+ "Modified: 5.11.1996 / 17:10:10 / cg"
!
divMod:aNumber
@@ -766,36 +769,38 @@
overhead of producing any intermediate byte-arrays (and the scanning)
"
(aSmallInteger == 0) ifTrue: [
- digitByteArray := #[0].
- sign := 0.
- ^ self
+ digitByteArray := ByteArray with:0.
+ sign := 0.
+ ^ self
].
(aSmallInteger < 0) ifTrue: [
- sign := -1.
- absValue := aSmallInteger negated
+ sign := -1.
+ absValue := aSmallInteger negated
] ifFalse: [
- sign := 1.
- absValue := aSmallInteger
+ sign := 1.
+ absValue := aSmallInteger
].
b1 := absValue bitAnd:16rFF.
absValue := absValue bitShift:-8.
absValue == 0 ifTrue:[
- digitByteArray := ByteArray with:b1
+ digitByteArray := ByteArray with:b1
] ifFalse:[
- b2 := absValue bitAnd:16rFF.
- absValue := absValue bitShift:-8.
- absValue == 0 ifTrue:[
- digitByteArray := ByteArray with:b1 with:b2
- ] ifFalse:[
- b3 := absValue bitAnd:16rFF.
- absValue := absValue bitShift:-8.
- absValue == 0 ifTrue:[
- digitByteArray := ByteArray with:b1 with:b2 with:b3
- ] ifFalse:[
- digitByteArray := ByteArray with:b1 with:b2 with:b3 with:absValue
- ]
- ]
+ b2 := absValue bitAnd:16rFF.
+ absValue := absValue bitShift:-8.
+ absValue == 0 ifTrue:[
+ digitByteArray := ByteArray with:b1 with:b2
+ ] ifFalse:[
+ b3 := absValue bitAnd:16rFF.
+ absValue := absValue bitShift:-8.
+ absValue == 0 ifTrue:[
+ digitByteArray := ByteArray with:b1 with:b2 with:b3
+ ] ifFalse:[
+ digitByteArray := ByteArray with:b1 with:b2 with:b3 with:absValue
+ ]
+ ]
]
+
+ "Modified: 5.11.1996 / 16:15:39 / cg"
! !
!LargeInteger methodsFor:'comparing'!
@@ -1054,7 +1059,7 @@
This method needs a rewrite."
|tmp1 tmp2
- rem
+ quo
count "{ Class: SmallInteger }"
digit "{ Class: SmallInteger }" |
@@ -1076,29 +1081,40 @@
].
count := 0.
- [tmp2 < tmp1] whileTrue:[
- tmp2 mul256.
+ [tmp2 absLess: tmp1] whileTrue:[
+ tmp2 mul2.
count := count + 1
].
- tmp2 div256.
+ tmp2 div2.
- rem := 0 asLargeInteger.
- rem sign:1.
+ quo := 0 asLargeInteger.
+ quo sign:1.
[count == 0] whileFalse:[
- digit := 0.
- [tmp1 >= tmp2] whileTrue:[
- digit := digit + 1.
- tmp1 := tmp1 - tmp2
+ quo mul2.
+ (tmp1 absLess:tmp2) ifFalse:[
+ quo digits at:1 put:((quo digits at:1) bitOr:1).
+ (tmp1 absSubtract: tmp2) ifFalse:[
+ "/ difference is zero; continue shifting
+ count := count - 1.
+ [count >= 8] whileTrue:[
+ quo mul256.
+ count := count - 8
+ ].
+ [count == 0] whileFalse:[
+ quo mul2.
+ count := count - 1.
+ ].
+ ^ Array with:quo compressed with:tmp1 compressed
+ ].
].
- rem := (rem * 256) + digit.
- tmp2 div256.
+ tmp2 div2.
count := count - 1
].
- ^ Array with:rem with:tmp1
+ ^ Array with:quo compressed with:tmp1 compressed
- "Modified: 5.11.1996 / 13:46:14 / cg"
+ "Modified: 5.11.1996 / 18:40:24 / cg"
!
absEq:aLargeInteger
@@ -1130,9 +1146,9 @@
^ true
!
-absFastDiv:aSmallInteger
+absFastDiv:aPositiveSmallInteger
"return an array with two LargeIntegers representing
- abs(self) // aSmallInteger and abs(self) \\ aSmallInteger"
+ abs(self) // aPositiveSmallInteger and abs(self) \\ aPositiveSmallInteger"
|tmp1 "{ Class: SmallInteger }"
prevRest "{ Class: SmallInteger }"
@@ -1140,12 +1156,12 @@
newDigitByteArray result
ok|
- aSmallInteger == 0 ifTrue:[
+ aPositiveSmallInteger == 0 ifTrue:[
^ DivisionByZeroSignal raise
].
"This cannot happen (if always normalized)
- self < aSmallInteger ifTrue:[
+ self < aPositiveSmallInteger ifTrue:[
^ Array with:0 with:self
].
"
@@ -1160,31 +1176,34 @@
if (__isByteArray(__digits)
&& __isByteArray(newDigitByteArray)
- && __bothSmallInteger(count, aSmallInteger)) {
+ && __bothSmallInteger(count, aPositiveSmallInteger)) {
unsigned int rest = 0;
int index = __intVal(count);
int index0;
- int divisor = __intVal(aSmallInteger);
+ unsigned divisor = __intVal(aPositiveSmallInteger);
unsigned char *digitBytes = __ByteArrayInstPtr(__digits)->ba_element;
unsigned char *resultBytes = __ByteArrayInstPtr(newDigitByteArray)->ba_element;
index0 = index;
- while (index > 1) {
- unsigned int t;
- unsigned div;
+/*
+ if (divisor < 0xFFFF) {
+ while (index > 1) {
+ unsigned int t;
+ unsigned div;
- index--;
- t = digitBytes[index];
- index--;
- t = (t << 8) | digitBytes[index];
- t = t | (rest << 16);
- div = t / divisor;
- rest = t % divisor;
- resultBytes[index+1] = (div >> 8);
- resultBytes[index] = (div & 0xFF);
+ index--;
+ t = digitBytes[index];
+ index--;
+ t = (t << 8) | digitBytes[index];
+ t = t | (rest << 16);
+ div = t / divisor;
+ rest = t % divisor;
+ resultBytes[index+1] = (div >> 8);
+ resultBytes[index] = (div & 0xFF);
+ }
}
-
+*/
while (index > 0) {
unsigned int t;
@@ -1211,13 +1230,7 @@
(could also do a primitiveFailure here)
"
ok ifFalse:[
- prevRest := 0.
- count to:1 by:-1 do:[:i |
- tmp1 := digitByteArray at:i.
- tmp1 := (tmp1 + (prevRest * 256)).
- newDigitByteArray at:i put:tmp1 // aSmallInteger.
- prevRest := (tmp1 \\ aSmallInteger).
- ]
+ self primitiveFailed
].
^ Array with:result compressed with:prevRest
@@ -1316,35 +1329,40 @@
!
absLess:aLargeInteger
- "return true, if abs(self) < abs(theArgument)"
+ "return true, if abs(self) < abs(theArgument).
+ This handles unnormalized largeIntegers."
- |len1 "{ Class: SmallInteger }"
- len2 "{ Class: SmallInteger }"
+ |myLen "{ Class: SmallInteger }"
+ otherLen "{ Class: SmallInteger }"
d1 "{ Class: SmallInteger }"
d2 "{ Class: SmallInteger }"
otherDigitByteArray |
- len1 := digitByteArray size.
+ myLen := digitByteArray size.
otherDigitByteArray := aLargeInteger digits.
- len2 := otherDigitByteArray size.
+ otherLen := otherDigitByteArray size.
- [(digitByteArray basicAt:len1) == 0] whileTrue:[
- len1 := len1 - 1
+ [(digitByteArray basicAt:myLen) == 0] whileTrue:[
+ myLen := myLen - 1
].
- [(otherDigitByteArray basicAt:len2) == 0] whileTrue:[
- len2 := len2 - 1
+ [(otherDigitByteArray basicAt:otherLen) == 0] whileTrue:[
+ otherLen := otherLen - 1
].
- (len1 < len2) ifTrue:[^ true].
- (len1 > len2) ifTrue:[^ false].
+ (myLen < otherLen) ifTrue:[^ true].
+ (myLen > otherLen) ifTrue:[^ false].
- [len1 > 0] whileTrue:[
- d1 := digitByteArray basicAt:len1.
- d2 := otherDigitByteArray basicAt:len1.
- (d1 < d2) ifTrue:[^ true].
- (d1 > d2) ifTrue:[^ false].
- len1 := len1 - 1
+ [myLen > 0] whileTrue:[
+ d1 := digitByteArray basicAt:myLen.
+ d2 := otherDigitByteArray basicAt:myLen.
+ d1 == d2 ifFalse:[
+ (d1 < d2) ifTrue:[^ true].
+ ^ false
+ ].
+ myLen := myLen - 1
].
^ false
+
+ "Modified: 5.11.1996 / 18:37:27 / cg"
!
absMinus:aLargeInteger
@@ -1563,12 +1581,181 @@
"Modified: 5.11.1996 / 14:09:34 / cg"
!
-div256
- "destructively divide the receiver by 256.
- private - used for division only"
+absSubtract:aLargeInteger
+ "destructively subtract aLargeInteger from myself.
+ A helper for division; only allowed for positive receiver
+ and argument. The receiver must be >= the argument.
+ The receiver must be a temporary scratch-number"
+
+ |result done
+ otherDigitByteArray resultDigitByteArray
+ len1 "{ Class: SmallInteger }"
+ len2 "{ Class: SmallInteger }"
+ index "{ Class: SmallInteger }"
+ borrow "{ Class: SmallInteger }"
+ diff "{ Class: SmallInteger }"
+ carry "{ Class: SmallInteger }"
+ lResult nonZero|
+
+ len1 := digitByteArray size.
+ otherDigitByteArray := aLargeInteger digits.
+ len2 := otherDigitByteArray size.
+ len2 > len1 ifTrue:[
+ [(otherDigitByteArray at:len2) == 0] whileTrue:[
+ len2 := len2 - 1
+ ].
+ len2 > len1 ifTrue:[
+ self halt "/ may not be called that way
+ ].
+ ].
+
+ nonZero := false.
+ index := 1.
+ borrow := 0.
+
+ done := false.
+ [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:[
+ nonZero := true
+ ].
+ digitByteArray basicAt:index put:diff.
+ index := index + 1
+ ].
+ ^ nonZero
+
+ "Created: 5.11.1996 / 16:23:47 / cg"
+ "Modified: 5.11.1996 / 18:56:50 / cg"
+!
+
+div2
+ "destructively divide the receiver by 2.
+ private - used for division only.
+ This is worth a primitive."
+
+%{ /* NOCONTEXT */
+ OBJ __digits = __INST(digitByteArray);
+
+ if (__isByteArray(__digits)) {
+ int __nBytes = __byteArraySize(__digits);
+ unsigned char *__bp = __ByteArrayInstPtr(__digits)->ba_element;
+ unsigned __this, __next;
+ int __idx;
+
+ if (__nBytes == 1) {
+ __bp[0] >>= 1;
+ RETURN (self);
+ }
+
+ __idx = 1;
+
+ if ((__idx+4) < __nBytes) {
+ __this = ((unsigned long *)__bp)[0];
- digitByteArray replaceFrom:1 with:digitByteArray startingAt:2.
- digitByteArray at:(digitByteArray size) put:0
+ while ((__idx+4) < __nBytes) {
+ __next = ((unsigned long *)__bp)[1];
+ __this >>= 1;
+ __this |= __next << 31;
+ ((unsigned long *)__bp)[0] = __this;
+ __this = __next;
+ __bp += 4;
+ __idx += 4;
+ }
+ }
+
+ __this = __bp[0];
+ while (__idx < __nBytes) {
+ __next = __bp[1];
+ __this >>= 1;
+ __this |= __next << 7;
+ __bp[0] = __this;
+ __this = __next;
+ __bp++;
+ __idx++;
+ }
+ __bp[0] = __this >> 1;
+ RETURN (self);
+ }
+%}.
+ self primitiveFailed
+
+ "
+ 100000 asLargeInteger div2
+ "
+
+ "Modified: 5.11.1996 / 16:12:56 / cg"
+!
+
+mul2
+ "destructively multiply the receiver by 2.
+ private - used for division only.
+ This is worth a primitive."
+
+ |nBytes "{ Class: SmallInteger }"
+ b "{ Class: SmallInteger }"
+ t|
+
+ nBytes := digitByteArray size.
+
+ b := digitByteArray at:nBytes.
+ (b bitAnd:16r80) ~~ 0 ifTrue:[
+ "/ need another byte
+ nBytes := nBytes + 1.
+ t := ByteArray uninitializedNew:nBytes.
+ t replaceFrom:1 with:digitByteArray.
+ t at:nBytes put:0.
+ digitByteArray := t.
+ ].
+
+%{
+ OBJ __digits = __INST(digitByteArray);
+
+ if (__isByteArray(__digits)) {
+ int __nBytes = __intVal(nBytes);
+ unsigned char *__bp = __ByteArrayInstPtr(__digits)->ba_element;
+ unsigned __carry = 0, __newCarry, __this;
+ int __idx;
+
+ while (__nBytes >= 4) {
+ __this = ((unsigned long *)__bp)[0];
+ __newCarry = __this >> 31;
+ ((unsigned long *)__bp)[0] = (__this << 1) | __carry;
+ __carry = __newCarry;
+ __bp += 4;
+ __nBytes -= 4;
+ }
+ while (__nBytes) {
+ __this = __bp[0];
+ __newCarry = __this >> 7;
+ __bp[0] = (__this << 1) | __carry;
+ __carry = __newCarry;
+ __bp ++;
+ __nBytes--;
+ }
+ RETURN (self);
+ }
+%}.
+ self primitiveFailed
+
+ "
+ 100000 asLargeInteger mul2
+ "
+
+ "Modified: 5.11.1996 / 16:37:32 / cg"
!
mul256
@@ -1638,5 +1825,5 @@
!LargeInteger class methodsFor:'documentation'!
version
- ^ '$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.36 1996-11-05 13:31:25 cg Exp $'
+ ^ '$Header: /cvs/stx/stx/libbasic/LargeInteger.st,v 1.37 1996-11-05 18:26:35 cg Exp $'
! !