Below is the list of changes that have just been committed into a local
6.0-falcon repository of chris. When chris does a push these changes will
be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html
ChangeSet@stripped, 2007-06-18 18:13:08-05:00, chris@stripped +3 -0
Added arbitrary division capability to the BigInt class. This
enables operations on numbers having greater than 9 digits, for
example DECIMAL(65,30).
WL#3923 "Arbitrary Precision Division for Falcon BigInt
Bug#26607 "Falcon: decimal(31,30) does not work"
Bug#28725 "Falcon: crash with decimal"
storage/falcon/BigInt.cpp@stripped, 2007-06-18 18:13:06-05:00, chris@stripped +291 -15
Added or modified the following methods to for arbitrary precision division:
BigInt::divide() - takes BigInt dividend and divisor, returns BigInt quotient and remainder
BigInt::scaleTo() - modified to scale using large division if necessary
BigInt::buildPowerTable() - builds power of 10 table
BigInt::nlz() - count number of leading zero bits
storage/falcon/BigInt.h@stripped, 2007-06-18 18:13:06-05:00, chris@stripped +11 -1
Added function declarations for BigInt large divide.
storage/falcon/ScaledBinary.cpp@stripped, 2007-06-18 18:13:06-05:00, chris@stripped +73 -8
ScaledBinary::putBigInt() now handles fractions > 9 digits.
Also fixed casting bug in putBinaryDecimal().
Added comments.
# This is a BitKeeper patch. What follows are the unified diffs for the
# set of deltas contained in the patch. The rest of the patch, the part
# that BitKeeper cares about, is below these diffs.
# User: chris
# Host: terrazzo.site
# Root: /home/chris/work/dev/dev-9/mysql-5.1-falcon
--- 1.10/storage/falcon/BigInt.cpp 2007-06-08 13:19:09 -05:00
+++ 1.11/storage/falcon/BigInt.cpp 2007-06-18 18:13:06 -05:00
@@ -18,21 +18,33 @@
//////////////////////////////////////////////////////////////////////
#include <stdio.h>
+#include <malloc.h>
#include "Engine.h"
#include "BigInt.h"
#include "Value.h"
+#ifdef _DEBUG
+#undef THIS_FILE
+static const char THIS_FILE[]=__FILE__;
+#endif
+
+#define MPBASE 32
+#define B 0x100000000 // Number base (MPBASE bits)
+
+static BigInt* powerTable[maxPowerOfTen];
+static bool powerTableInit;
+
static const int powersOfTen [] = {
- 1,
- 10,
- 100,
- 1000,
- 10000,
- 100000,
- 1000000,
- 10000000,
- 100000000,
- 1000000000
+ 1, // 0
+ 10, // 1
+ 100, // 2
+ 1000, // 3
+ 10000, // 4
+ 100000, // 5
+ 1000000, // 6
+ 10000000, // 7
+ 100000000, // 8
+ 1000000000 // 9
};
static int byteShifts [] = { 24, 16, 8, 0 };
@@ -85,7 +97,6 @@
}
}
-
void BigInt::subtract(int index, BigWord value)
{
while (value)
@@ -267,13 +278,54 @@
normalize();
}
-int BigInt::scaleTo(int toScale)
+void BigInt::scaleTo(int toScale)
+{
+ BigWord intResult;
+ BigInt bigInt;
+
+ if (scale <= 9)
+ scaleTo(toScale, &intResult);
+ else
+ scaleTo(toScale, &bigInt);
+}
+
+BigInt BigInt::scaleTo(int toScale, BigInt* result)
{
int delta = toScale - scale;
scale = toScale;
+ result->clear();
+
+ if (!powerTableInit)
+ buildPowerTable();
if (delta == 0)
- return 0;
+ return *result;
+
+ if (delta > 9) //cwp handle <= 9
+ {
+ *result = divide(powerTable[delta]);
+ return *result;
+ }
+
+ while (delta < -9)
+ {
+ multiply(powersOfTen[9]);
+ delta += 9;
+ }
+
+ multiply(powersOfTen[-delta]);
+
+ return *result;
+}
+
+BigWord BigInt::scaleTo(int toScale, BigWord* result)
+{
+ int delta = toScale - scale;
+ scale = toScale;
+ *result = 0;
+
+ if (delta == 0)
+ return *result;
if (delta > 0)
{
@@ -283,7 +335,8 @@
delta -= 9;
}
- return divide(powersOfTen[delta]);
+ *result = divide(powersOfTen[delta]);
+ return *result;
}
while (delta < -9)
@@ -294,7 +347,7 @@
multiply(powersOfTen[-delta]);
- return 0;
+ return *result;
}
void BigInt::setString(int stringLength, const char* string)
@@ -427,3 +480,226 @@
return (int) words[1] >= 0;
}
+
+// Count number of leading zero bits
+// TBD: Use native CLZ (for gcc use _builtin_clz, for windows see below)
+
+int BigInt::nlz(uint64 x)
+{
+ int n;
+
+ if (x == 0) return(64);
+ n = 0;
+ if (x <= 0x00000000FFFFFFFF) {n = n + 32; x = x << 32;}
+ if (x <= 0x0000FFFFFFFFFFFF) {n = n + 16; x = x << 16;}
+ if (x <= 0x00FFFFFFFFFFFFFF) {n = n + 8; x = x << 8;}
+ if (x <= 0x0FFFFFFFFFFFFFFF) {n = n + 4; x = x << 4;}
+ if (x <= 0x3FFFFFFFFFFFFFFF) {n = n + 2; x = x << 2;}
+ if (x <= 0x7FFFFFFFFFFFFFFF) {n = n + 1;}
+ return n;
+}
+
+#if 0
+uint32 clz (uint32 a)
+{
+ _asm
+ {
+ mov eax, [a]
+ bsr eax, eax
+ xor eax, 31
+ mov [a], eax
+ }
+
+ return a;
+}
+#endif
+
+
+BigInt BigInt::divide(const BigInt* divisor)
+{
+ BigInt quotient;
+ BigInt remainder;
+
+ divide(this, divisor, "ient, &remainder);
+ memcpy(this->words, quotient.words, sizeof(this->words));
+ this->length = quotient.length;
+
+ return(remainder);
+}
+
+// Arbitrary precision division based upon Knuth Algorithm D
+
+int BigInt::divide(const BigInt* dividend, const BigInt* divisor, BigInt* quotient, BigInt* remainder)
+ {
+ uint32* q = quotient->words;
+ uint32* r = remainder->words;
+ const uint32* u = dividend->words;
+ const uint32* v = divisor->words;
+ int m = dividend->length;
+ int n = divisor->length;
+
+ uint32 *un, *vn; // normalized form of u, v
+ uint64 qhat; // estimated quotient digit
+ uint64 rhat; // remainder
+ uint64 p; // product of two digits
+ int s, i, j;
+ int64 t, k;
+
+ quotient->clear();
+ remainder->clear();
+
+ // Check for invalid parameters
+
+ if (m < n || n <= 0 || v[n-1] == 0)
+ return(1);
+
+ // Take care of the case of a single-digit divisor
+
+ if (n == 1)
+ {
+ k = 0;
+
+ for (j = m - 1; j >= 0; j--)
+ {
+ q[j] = (uint32)((k*B + u[j]) / v[0]);
+ k = (k*B + u[j]) - q[j] *v[0];
+ }
+
+ if (r != NULL) r[0] = (uint32)k;
+
+ // Take a best guess at the quotient length, adjust as necessary
+
+ quotient->length = m - n + 1;
+ remainder->length = n;
+ quotient->normalize();
+ remainder->normalize();
+
+ return(0);
+ }
+
+ // Normalize by shifting v left just enough so that its high-order bit is on,
+ // and shift u left the same amount. We may have to append a high-order digit
+ // on the dividend; we do that unconditionally.
+
+ // Step D1
+
+ s = nlz(v[n-1]) - MPBASE; // 0 <= s <= MPBASE.
+ vn = (uint32 *)_malloca(4*n);
+
+ for (i = n - 1; i > 0; i--)
+ vn[i] = (v[i] << s) | (v[i-1] >> (MPBASE-s));
+
+ vn[0] = v[0] << s;
+
+ un = (uint32 *)_malloca(4*(m+1));
+ un[m] = u[m-1] >> (MPBASE-s);
+
+ for (i = m - 1; i > 0; i--)
+ un[i] = (u[i] << s) | (u[i-1] >> (MPBASE-s));
+
+ un[0] = u[0] << s;
+
+ // Step D2: Main loop
+
+ for (j = m - n; j >= 0; j--)
+ {
+ // Step D3: Compute estimate qhat of q[j]
+
+ qhat = un[j+n]*B;
+ qhat += un[j+n-1];
+ qhat /= vn[n-1];
+ // qhat = (un[j+n]*B + un[j+n-1]) / vn[n-1];
+
+ rhat = un[j+n]*B;
+ rhat += un[j+n-1];
+ uint64 q2 = qhat*vn[n-1];
+ rhat -= q2;
+ // rhat = (un[j+n]*B + un[j+n-1]) - qhat*vn[n-1];
+
+ again:
+
+ if (qhat >= B || qhat*vn[n-2] > B*rhat + un[j+n-2])
+ {
+ qhat = qhat - 1;
+ rhat = rhat + vn[n-1];
+ if (rhat < B) goto again;
+ }
+
+ // Step D4: Multiply and subtract
+
+ k = 0;
+
+ for (i = 0; i < n; i++)
+ {
+ p = qhat*vn[i];
+ t = un[i+j] - k;
+ t -= (p & 0xFFFFFFFF);
+ //t = un[i+j] - k - (p & 0xFFFFFFFF);
+
+ un[i+j] = (uint32)t;
+ k = (p >> MPBASE) - (t >> MPBASE);
+ }
+
+ t = un[j+n] - k;
+ un[j+n] = (uint32)t;
+
+ // Step D5: Store quotient digit
+
+ q[j] = (uint32)qhat;
+
+ if (t < 0)
+ {
+ // Step D6: If we subtracted too much, add back
+
+ q[j] = q[j] - 1;
+ k = 0;
+
+ for (i = 0; i < n; i++)
+ {
+ t = (uint64)un[i+j] + (uint64)vn[i] + k;
+ //t = un[i+j] + vn[i] + k;
+ un[i+j] = (uint32)t;
+ k = ((uint64)t) >> MPBASE;
+ }
+
+ un[j+n] = (uint32) (un[j+n] + k);
+ }
+
+ } // Step D7: End j
+
+ // Step D8: Unnormalize remainder
+
+ if (r != NULL)
+ {
+ for (i = 0; i < n; i++)
+ r[i] = (un[i] >> s) | (un[i+1] << (MPBASE-s));
+ }
+
+ // Take a best guess at the quotient length, adjust as necessary
+
+ quotient->length = m - n + 1;
+ remainder->length = n;
+ quotient->normalize();
+ remainder->normalize();
+
+ _freea(un);
+ _freea(vn);
+ return(0);
+ }
+
+// Generate a table of BigInt powers of 10
+
+void BigInt::buildPowerTable()
+ {
+ BigInt* bigInt = ::new BigInt;
+ bigInt->set(powersOfTen[9], 0);
+ powerTable[9] = bigInt;
+
+ for (int i = 10; i < maxPowerOfTen; i++)
+ {
+ powerTable[i] = ::new BigInt(powerTable[i-1]);
+ powerTable[i]->multiply(10);
+ }
+
+ powerTableInit = true;
+ }
--- 1.8/storage/falcon/BigInt.h 2007-04-23 21:08:07 -05:00
+++ 1.9/storage/falcon/BigInt.h 2007-06-18 18:13:06 -05:00
@@ -26,6 +26,7 @@
static const int maxBigWords = 10;
static const int bigWordBits = 32;
+static const int maxPowerOfTen = 65;
#define LOW_WORD(n) ((BigWord) n)
#define HIGH_WORD(n) ((BigWord)(n >> bigWordBits))
@@ -44,7 +45,11 @@
virtual void multiply(BigWord value);
virtual BigWord divide (BigWord value);
- virtual int scaleTo(int toScale);
+ virtual BigInt divide(const BigInt* divisor);
+ virtual int divide(const BigInt * dividend, const BigInt * divisor, BigInt * quotient, BigInt * remainder);
+ virtual void scaleTo(int toScale);
+ virtual BigWord scaleTo(int toScale, BigWord* result);
+ virtual BigInt scaleTo(int toScale, BigInt* result);
virtual void set(BigWord value32);
virtual int getByteLength(void);
virtual void getBytes(char* bytes);
@@ -62,6 +67,9 @@
void getString(int bufferLength, char* buffer);
double getDouble(void);
int compare(BigInt* bigInt);
+ int nlz(uint64 x);
+ void buildPowerTable();
+
short length;
short scale;
@@ -73,6 +81,8 @@
length = 0;
scale = 0;
neg = false;
+ for (int i = 0; i < maxBigWords; i++)
+ words[i] = 0;
}
inline void add(int index, BigWord value)
--- 1.11/storage/falcon/ScaledBinary.cpp 2007-04-23 21:08:07 -05:00
+++ 1.12/storage/falcon/ScaledBinary.cpp 2007-06-18 18:13:06 -05:00
@@ -120,7 +120,6 @@
return group;
}
-
int ScaledBinary::numberBytes(int digits)
{
return (digits / DIGITS_PER_INT) * sizeof(decimal_digit_t) + bytesByDigit[digits % DIGITS_PER_INT];
@@ -130,11 +129,18 @@
{
int64 absNumber = (number >= 0) ? number : -number;
char *p = ptr;
+
+ // Shift right by 'scale', store the integer portion
+
putBinaryNumber(absNumber / powersOfTen[scale], precision - scale, &p, false);
+ // Store fractional digits
+
if (scale)
putBinaryNumber(absNumber % powersOfTen[scale], scale, &p, true);
+ // Handle sign
+
if (number < 0)
for (char *q = ptr; q < p; ++q)
*q ^= -1;
@@ -150,6 +156,8 @@
int partialDigits = digits % DIGITS_PER_INT;
int partialBytes = bytesByDigit[partialDigits];
+ // If not a fraction, get the high-order 4 bytes (or less), store in 'value'
+
if (!isFraction && partialBytes)
{
value = getBinaryGroup(position, partialBytes, ptr);
@@ -157,12 +165,16 @@
partialBytes = 0;
}
+ // Get remaining bytes in 4-byte groups, leftshift 'value' then add each group
+
for (int n = 0; n < groups; ++n)
{
value = value * BASE + getBinaryGroup(position, sizeof(decimal_digit_t), ptr);
position += sizeof(decimal_digit_t);
}
+ // If fraction, then rightshift 'value' and add in the remaining digits
+
if (partialBytes)
value = value * powersOfTen[partialDigits] + getBinaryGroup(position, partialBytes, ptr);
@@ -189,9 +201,9 @@
index -= DIGITS_PER_INT;
if (index)
- putBinaryGroup(((uint) scaleInt64(number, index)) % BASE, DIGITS_PER_INT, &p);
+ putBinaryGroup((uint)(scaleInt64(number, index) % BASE), DIGITS_PER_INT, &p);
else
- putBinaryGroup((uint) number % BASE, DIGITS_PER_INT, &p);
+ putBinaryGroup((uint) (number % BASE), DIGITS_PER_INT, &p);
}
if (partialDigits)
@@ -233,6 +245,8 @@
int partialDigits = digits % DIGITS_PER_INT;
int partialBytes = bytesByDigit[partialDigits];
+ // Store leading partial group integer digits, always < 9
+
if (!isFraction && partialBytes)
{
BigWord value = getBinaryGroup(position, partialBytes, ptr);
@@ -241,14 +255,23 @@
partialBytes = 0;
}
+ // Store remaining digits by collapsing 9-digit groups into int32, then accumulate
+
for (int n = 0; n < groups; ++n)
{
+ // Get next group of 9 decimal digits, store in int32
+
BigWord value = getBinaryGroup(position, sizeof(decimal_digit_t), ptr);
+
+ // Leftshift current value by 9 digits and add the new value
+
bigInt->multiply(BASE);
bigInt->add(0, value);
position += sizeof(decimal_digit_t);
}
+ // If this is a fraction, then rightshift and add in leading digits
+
if (partialBytes)
{
bigInt->multiply((uint32) powersOfTen[partialDigits]);
@@ -274,24 +297,66 @@
int digits = precision - scale;
int groups = digits / DIGITS_PER_INT;
int partialDigits = digits % DIGITS_PER_INT;
- BigInt number(bigInt), *hack = &number;
- uint32 fraction = number.scaleTo(0);
+ BigInt number(bigInt);
+ uint32 fraction;
+ BigInt bigFraction;
uint32 data[20];
+
+ // Scale to isolate the integer but save the fractional digits
+
+ if (scale <= 9)
+ number.scaleTo(0, &fraction);
+ else
+ number.scaleTo(0, &bigFraction);
+
int n;
+ // Store each 9-digit group, descale by 10^9 for each
+
for (n = 0; n < groups; ++n)
- data[n] = (number.length) ? hack->divide(BASE) : 0;
+ data[n] = (number.length) ? number.divide(BASE) : 0;
+
+ // First put the group of partial (< 9) digits
if (partialDigits)
- putBinaryGroup((number.length) ? hack->divide(BASE) : 0, partialDigits, &p);
+ putBinaryGroup((number.length) ? number.divide(BASE) : 0, partialDigits, &p);
+
+ // Now put each 9-digit group
while (--n >= 0)
+ {
putBinaryGroup(data[n], DIGITS_PER_INT, &p);
+ data[n] = 0;
+ }
// Now handle fraction
- if (scale)
+ if (scale <= 9)
putBinaryNumber(fraction, scale, &p, true);
+ else
+ {
+ groups = scale / DIGITS_PER_INT;
+ partialDigits = scale % DIGITS_PER_INT;
+
+ // Isolate the trailing partial digits (< 9)
+
+ uint32 partial = bigFraction.divide(powersOfTen[partialDigits]);
+
+ // Store each 9-digit group, descale by 10^9 for each
+
+ for (n = 0; n < groups; ++n)
+ data[n] = (bigFraction.length) ? bigFraction.divide(BASE) : 0;
+
+ // Write the 9-digit groups LSB first
+
+ while (--n >= 0)
+ putBinaryGroup(data[n], DIGITS_PER_INT, &p);
+
+ // Write the trailing digits
+
+ if (partialDigits)
+ putBinaryGroup(partial, partialDigits, &p);
+ }
if (bigInt->neg)
for (char *q = ptr; q < p; ++q)
| Thread |
|---|
| • bk commit into 6.0-falcon tree (chris:1.2575) BUG#26607 | cpowers | 19 Jun |
