Math128: 128-bit Integer Math Library
[Query Object Framework]


Detailed Description

Quick-n-dirty 128-bit integer math lib. Things seem to mostly work, and have been tested, but not comprehensively tested.


Data Structures

struct  qofint128

Functions

gboolean equal128 (qofint128 a, qofint128 b)
int cmp128 (qofint128 a, qofint128 b)
qofint128 shift128 (qofint128 x)
qofint128 shiftleft128 (qofint128 x)
qofint128 inc128 (qofint128 a)
qofint128 add128 (qofint128 a, qofint128 b)
qofint128 mult128 (gint64 a, gint64 b)
qofint128 div128 (qofint128 n, gint64 d)
gint64 rem128 (qofint128 n, gint64 d)
guint64 gcf64 (guint64 num, guint64 denom)
qofint128 lcm128 (guint64 a, guint64 b)


Function Documentation

qofint128 add128 qofint128  a,
qofint128  b
[inline]
 

Add a pair of 128-bit numbers, returning a 128-bit number

Definition at line 296 of file qofmath128.c.

00297 {
00298   qofint128 sum;
00299   if (a.isneg == b.isneg)
00300   {
00301     sum.isneg = a.isneg;
00302     sum.hi = a.hi + b.hi;
00303     sum.lo = a.lo + b.lo;
00304     if ((sum.lo < a.lo) || (sum.lo < b.lo))
00305     {
00306      sum.hi ++;
00307     }
00308     sum.isbig = sum.hi || (sum.lo >> 63);
00309     return sum;
00310   }
00311   if ((b.hi > a.hi) ||
00312      ((b.hi == a.hi) && (b.lo > a.lo)))
00313   {
00314     qofint128 tmp = a;
00315     a = b;
00316     b = tmp;
00317   }
00318 
00319   sum.isneg = a.isneg;
00320   sum.hi = a.hi - b.hi;
00321   sum.lo = a.lo - b.lo;
00322 
00323   if (sum.lo > a.lo)
00324   {
00325     sum.hi --;
00326   }
00327 
00328   sum.isbig = sum.hi || (sum.lo >> 63);
00329   return sum;
00330 }

int cmp128 qofint128  a,
qofint128  b
[inline]
 

Return returns 1 if a>b, -1 if b>a, 0 if a == b

Definition at line 244 of file qofmath128.c.

00245 {
00246    if ((0 == a.isneg) && b.isneg) return 1;
00247    if (a.isneg && (0 == b.isneg)) return -1;
00248    if (0 == a.isneg)
00249    {
00250      if (a.hi > b.hi) return 1;
00251      if (a.hi < b.hi) return -1;
00252      if (a.lo > b.lo) return 1;
00253      if (a.lo < b.lo) return -1;
00254      return 0;
00255    }
00256 
00257    if (a.hi > b.hi) return -1;
00258    if (a.hi < b.hi) return 1;
00259    if (a.lo > b.lo) return -1;
00260    if (a.lo < b.lo) return 1;
00261    return 0;
00262 }

qofint128 div128 qofint128  n,
gint64  d
[inline]
 

Divide a signed 128-bit number by a signed 64-bit, returning a signed 128-bit number.

Definition at line 182 of file qofmath128.c.

00183 {
00184   qofint128 quotient;
00185   int i;
00186   guint64 remainder = 0;
00187 
00188   quotient = n;
00189   if (0 > d)
00190   {
00191     d = -d;
00192     quotient.isneg = !quotient.isneg;
00193   }
00194 
00195   /* Use grade-school long division algorithm */
00196   for (i=0; i<128; i++)
00197   {
00198     guint64 sbit = HIBIT & quotient.hi;
00199     remainder <<= 1;
00200     if (sbit) remainder |= 1;
00201     quotient = shiftleft128 (quotient);
00202     if (remainder >= d)
00203     {
00204        remainder -= d;
00205        quotient.lo |= 1;
00206     }
00207   }
00208 
00209   /* compute the carry situation */
00210   quotient.isbig = (quotient.hi || (quotient.lo >> 63));
00211 
00212   return quotient;
00213 }

gboolean equal128 qofint128  a,
qofint128  b
[inline]
 

Return true of two numbers are equal

Definition at line 234 of file qofmath128.c.

00235 {
00236         if (a.lo != b.lo) return 0;
00237         if (a.hi != b.hi) return 0;
00238         if (a.isneg != b.isneg) return 0;
00239         return 1;
00240 }

guint64 gcf64 guint64  num,
guint64  denom
[inline]
 

Return the greatest common factor of two 64-bit numbers

Definition at line 266 of file qofmath128.c.

00267 {
00268   guint64   t;
00269 
00270   t =  num % denom;
00271   num = denom;
00272   denom = t;
00273 
00274   /* The strategy is to use Euclid's algorithm */
00275   while (0 != denom) 
00276   {
00277     t = num % denom;
00278     num = denom;
00279     denom = t;
00280   }
00281   /* num now holds the GCD (Greatest Common Divisor) */
00282   return num;
00283 }

qofint128 inc128 qofint128  a  )  [inline]
 

increment a 128-bit number by one

Definition at line 155 of file qofmath128.c.

00156 {
00157   if (0 == a.isneg)
00158   {
00159     a.lo ++;
00160     if (0 == a.lo)
00161     {
00162       a.hi ++;
00163     }
00164   }
00165   else
00166   {
00167     if (0 == a.lo)
00168     {
00169       a.hi --;
00170     }
00171     a.lo --;
00172   }
00173 
00174   a.isbig = (a.hi != 0) || (a.lo >> 63);
00175   return a;
00176 }

qofint128 lcm128 guint64  a,
guint64  b
[inline]
 

Return the least common multiple of two 64-bit numbers.

Definition at line 287 of file qofmath128.c.

00288 {
00289   guint64 gcf = gcf64 (a,b);
00290   b /= gcf;
00291   return mult128 (a,b);
00292 }

qofint128 mult128 gint64  a,
gint64  b
[inline]
 

Multiply a pair of signed 64-bit numbers, returning a signed 128-bit number.

Definition at line 43 of file qofmath128.c.

00044 {
00045   qofint128 prod;
00046   guint64 a0, a1;
00047   guint64 b0, b1;
00048   guint64 d, d0, d1;
00049   guint64 e, e0, e1;
00050   guint64 f, f0, f1;
00051   guint64 g, g0, g1;
00052   guint64 sum, carry, roll, pmax;
00053 
00054   prod.isneg = 0;
00055   if (0>a)
00056   {
00057     prod.isneg = !prod.isneg;
00058     a = -a;
00059   }
00060 
00061   if (0>b)
00062   {
00063     prod.isneg = !prod.isneg;
00064     b = -b;
00065   }
00066 
00067   a1 = a >> 32;
00068   a0 = a - (a1<<32);
00069 
00070   b1 = b >> 32;
00071   b0 = b - (b1<<32);
00072 
00073   d = a0*b0;
00074   d1 = d >> 32;
00075   d0 = d - (d1<<32);
00076 
00077   e = a0*b1;
00078   e1 = e >> 32;
00079   e0 = e - (e1<<32);
00080 
00081   f = a1*b0;
00082   f1 = f >> 32;
00083   f0 = f - (f1<<32);
00084 
00085   g = a1*b1;
00086   g1 = g >> 32;
00087   g0 = g - (g1<<32);
00088 
00089   sum = d1+e0+f0;
00090   carry = 0;
00091   /* Can't say 1<<32 cause cpp will goof it up; 1ULL<<32 might work */
00092   roll = 1<<30;
00093   roll <<= 2;
00094 
00095   pmax = roll-1;
00096   while (pmax < sum)
00097   {
00098     sum -= roll;
00099     carry ++;
00100   }
00101 
00102   prod.lo = d0 + (sum<<32);
00103   prod.hi = carry + e1 + f1 + g0 + (g1<<32);
00104   // prod.isbig = (prod.hi || (sum >> 31));
00105   prod.isbig = prod.hi || (prod.lo >> 63);
00106 
00107   return prod;
00108 }

gint64 rem128 qofint128  n,
gint64  d
[inline]
 

Return the remainder of a signed 128-bit number modulo a signed 64-bit. That is, return nd in 128-bit math. I beleive that ths algo is overflow-free, but should be audited some more ...

Definition at line 221 of file qofmath128.c.

00222 {
00223   qofint128 quotient = div128 (n,d);
00224 
00225   qofint128 mu = mult128 (quotient.lo, d);
00226 
00227   gint64 nn = 0x7fffffffffffffffULL & n.lo;
00228   gint64 rr = 0x7fffffffffffffffULL & mu.lo;
00229   return nn - rr;
00230 }

qofint128 shift128 qofint128  x  )  [inline]
 

Shift right by one bit (i.e. divide by two)

Definition at line 112 of file qofmath128.c.

00113 {
00114   guint64 sbit = x.hi & 0x1;
00115   x.hi >>= 1;
00116   x.lo >>= 1;
00117   x.isbig = 0;
00118   if (sbit)
00119   {
00120     x.lo |= HIBIT;
00121     x.isbig = 1;
00122     return x;
00123   }
00124   if (x.hi)
00125   {
00126     x.isbig = 1;
00127   }
00128   return x;
00129 }

qofint128 shiftleft128 qofint128  x  )  [inline]
 

Shift leftt by one bit (i.e. multiply by two)

Definition at line 133 of file qofmath128.c.

00134 {
00135   guint64 sbit;
00136   sbit = x.lo & HIBIT;
00137   x.hi <<= 1;
00138   x.lo <<= 1;
00139   x.isbig = 0;
00140   if (sbit)
00141   {
00142     x.hi |= 1;
00143     x.isbig = 1;
00144     return x;
00145   }
00146   if (x.hi)
00147   {
00148     x.isbig = 1;
00149   }
00150   return x;
00151 }


Generated on Fri May 12 18:00:35 2006 for QOF by  doxygen 1.4.4