static char rcsid[] = "$Id: H:/drh/idioms/book/RCS/mp.doc,v 1.11 1996/06/26 23:02:01 drh Exp $";
#include <ctype.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include "assert.h"
#include "fmt.h"
#include "mem.h"
#include "xp.h"
#include "mp.h"
#define T MP_T
#define sign(x) ((x)[nbytes-1]>>shift)
#define ones(n) (~(~0UL<<(((n)-1)%8+1)))
#define iszero(x) (XP_length(nbytes,(x))==1 && (x)[0]==0)
#define BASE (1<<8)
#define bitop(op) \
int i; assert(z); assert(x); assert(y); \
for (i = 0; i < nbytes; i++) z[i] = x[i] op y[i]; \
return z
#define bitopi(op) assert(z); assert(x); \
applyu(op, z, x, y); \
return z
#define shft(fill, op) \
assert(x); assert(z); assert(s >= 0); \
if (s >= nbits) memset(z, fill, nbytes); \
else op(nbytes, z, nbytes, x, s, fill); \
z[nbytes-1] &= msb; \
return z
const Except_T MP_Dividebyzero = { "Division by zero" };
const Except_T MP_Overflow = { "Overflow" };
static int nbits = 32;
static int nbytes = (32-1)/8 + 1;
static int shift = (32-1)%8;
static unsigned char msb = 0xFF;
static unsigned char temp[16 + 16 + 16 + 2*16+2];
static T tmp[] = {temp, temp+1*16, temp+2*16, temp+3*16};
static int applyu(T op(T, T, T), T z, T x,
unsigned long u) {
unsigned long carry;
{ T z = tmp[2]; carry = XP_fromint(nbytes, z, u);
carry |= z[nbytes-1]&~msb;
z[nbytes-1] &= msb; }
op(z, x, tmp[2]);
return carry != 0;
}
static int apply(T op(T, T, T), T z, T x, long v) {
{ T z = tmp[2]; if (v == LONG_MIN) {
XP_fromint(nbytes, z, LONG_MAX + 1UL);
XP_neg(nbytes, z, z, 1);
} else if (v < 0) {
XP_fromint(nbytes, z, -v);
XP_neg(nbytes, z, z, 1);
} else
XP_fromint(nbytes, z, v);
z[nbytes-1] &= msb; }
op(z, x, tmp[2]);
return (nbits < 8*(int)sizeof (v) &&
(v < -(1L<<(nbits-1)) || v >= (1L<<(nbits-1))));
}
int MP_set(int n) {
int prev = nbits;
assert(n > 1);
nbits = n;
nbytes = (n-1)/8 + 1;
shift = (n-1)%8;
msb = ones(n);
if (tmp[0] != temp)
FREE(tmp[0]);
if (nbytes <= 16)
tmp[0] = temp;
else
tmp[0] = ALLOC(3*nbytes + 2*nbytes + 2);
tmp[1] = tmp[0] + 1*nbytes;
tmp[2] = tmp[0] + 2*nbytes;
tmp[3] = tmp[0] + 3*nbytes;
return prev;
}
T MP_new(unsigned long u) {
return MP_fromintu(ALLOC(nbytes), u);
}
T MP_fromintu(T z, unsigned long u) {
unsigned long carry;
assert(z);
carry = XP_fromint(nbytes, z, u);
carry |= z[nbytes-1]&~msb;
z[nbytes-1] &= msb;
if (carry)
RAISE(MP_Overflow);
return z;
}
T MP_fromint(T z, long v) {
assert(z);
if (v == LONG_MIN) {
XP_fromint(nbytes, z, LONG_MAX + 1UL);
XP_neg(nbytes, z, z, 1);
} else if (v < 0) {
XP_fromint(nbytes, z, -v);
XP_neg(nbytes, z, z, 1);
} else
XP_fromint(nbytes, z, v);
z[nbytes-1] &= msb;
if ((nbits < 8*(int)sizeof (v) &&
(v < -(1L<<(nbits-1)) || v >= (1L<<(nbits-1)))))
RAISE(MP_Overflow);
return z;
}
long MP_toint(T x) {
unsigned char d[sizeof (unsigned long)];
assert(x);
MP_cvt(8*sizeof d, d, x);
return XP_toint(sizeof d, d);
}
T MP_cvt(int m, T z, T x) {
int fill, i, mbytes = (m - 1)/8 + 1;
assert(m > 1);
assert(x); assert(z);
fill = sign(x) ? 0xFF : 0;
if (m < nbits) {
int carry = (x[mbytes-1]^fill)&~ones(m);
for (i = mbytes; i < nbytes; i++)
carry |= x[i]^fill;
memcpy(z, x, mbytes);
z[mbytes-1] &= ones(m);
if (carry)
RAISE(MP_Overflow);
} else {
memcpy(z, x, nbytes);
z[nbytes-1] |= fill&~msb;
for (i = nbytes; i < mbytes; i++)
z[i] = fill;
z[mbytes-1] &= ones(m);
}
return z;
}
unsigned long MP_tointu(T x) {
unsigned char d[sizeof (unsigned long)];
assert(x);
MP_cvtu(8*sizeof d, d, x);
return XP_toint(sizeof d, d);
}
T MP_cvtu(int m, T z, T x) {
int i, mbytes = (m - 1)/8 + 1;
assert(m > 1);
assert(x); assert(z);
if (m < nbits) {
int carry = x[mbytes-1]&~ones(m);
for (i = mbytes; i < nbytes; i++)
carry |= x[i];
memcpy(z, x, mbytes);
z[mbytes-1] &= ones(m);
if (carry)
RAISE(MP_Overflow);
} else {
memcpy(z, x, nbytes);
for (i = nbytes; i < mbytes; i++)
z[i] = 0;
}
return z;
}
T MP_addu(T z, T x, T y) {
int carry;
assert(x); assert(y); assert(z);
carry = XP_add(nbytes, z, x, y, 0);
carry |= z[nbytes-1]&~msb;
z[nbytes-1] &= msb;
if (carry)
RAISE(MP_Overflow);
return z;
}
T MP_subu(T z, T x, T y) {
int borrow;
assert(x); assert(y); assert(z);
borrow = XP_sub(nbytes, z, x, y, 0);
borrow |= z[nbytes-1]&~msb;
z[nbytes-1] &= msb;
if (borrow)
RAISE(MP_Overflow);
return z;
}
T MP_mul2u(T z, T x, T y) {
assert(x); assert(y); assert(z);
memset(tmp[3], '\0', 2*nbytes);
XP_mul(tmp[3], nbytes, x, nbytes, y);
memcpy(z, tmp[3], (2*nbits - 1)/8 + 1);
return z;
}
T MP_mulu(T z, T x, T y) {
assert(x); assert(y); assert(z);
memset(tmp[3], '\0', 2*nbytes);
XP_mul(tmp[3], nbytes, x, nbytes, y);
memcpy(z, tmp[3], nbytes);
z[nbytes-1] &= msb;
{
int i;
if (tmp[3][nbytes-1]&~msb)
RAISE(MP_Overflow);
for (i = 0; i < nbytes; i++)
if (tmp[3][i+nbytes] != 0)
RAISE(MP_Overflow);
}
return z;
}
T MP_divu(T z, T x, T y) {
assert(x); assert(y); assert(z);
{
memcpy(tmp[1], y, nbytes);
y = tmp[1];
}
if (!XP_div(nbytes, z, x, nbytes, y, tmp[2], tmp[3]))
RAISE(MP_Dividebyzero);
return z;
}
T MP_modu(T z, T x, T y) {
assert(x); assert(y); assert(z);
{
memcpy(tmp[1], y, nbytes);
y = tmp[1];
}
if (!XP_div(nbytes, tmp[2], x, nbytes, y, z, tmp[3]))
RAISE(MP_Dividebyzero);
return z;
}
T MP_add(T z, T x, T y) {
int sx, sy;
assert(x); assert(y); assert(z);
sx = sign(x);
sy = sign(y);
XP_add(nbytes, z, x, y, 0);
z[nbytes-1] &= msb;
if (sx == sy && sy != sign(z))
RAISE(MP_Overflow);
return z;
}
T MP_sub(T z, T x, T y) {
int sx, sy;
assert(x); assert(y); assert(z);
sx = sign(x);
sy = sign(y);
XP_sub(nbytes, z, x, y, 0);
z[nbytes-1] &= msb;
if (sx != sy && sy == sign(z))
RAISE(MP_Overflow);
return z;
}
T MP_neg(T z, T x) {
int sx;
assert(x); assert(z);
sx = sign(x);
XP_neg(nbytes, z, x, 1);
z[nbytes-1] &= msb;
if (sx && sx == sign(z))
RAISE(MP_Overflow);
return z;
}
T MP_mul2(T z, T x, T y) {
int sx, sy;
assert(x); assert(y); assert(z);
sx = sign(x);
sy = sign(y);
if (sx) {
XP_neg(nbytes, tmp[0], x, 1);
x = tmp[0];
x[nbytes-1] &= msb;
}
if (sy) {
XP_neg(nbytes, tmp[1], y, 1);
y = tmp[1];
y[nbytes-1] &= msb;
}
memset(tmp[3], '\0', 2*nbytes);
XP_mul(tmp[3], nbytes, x, nbytes, y);
if (sx != sy)
XP_neg((2*nbits - 1)/8 + 1, z, tmp[3], 1);
else
memcpy(z, tmp[3], (2*nbits - 1)/8 + 1);
return z;
}
T MP_mul(T z, T x, T y) {
int sx, sy;
assert(x); assert(y); assert(z);
sx = sign(x);
sy = sign(y);
if (sx) {
XP_neg(nbytes, tmp[0], x, 1);
x = tmp[0];
x[nbytes-1] &= msb;
}
if (sy) {
XP_neg(nbytes, tmp[1], y, 1);
y = tmp[1];
y[nbytes-1] &= msb;
}
memset(tmp[3], '\0', 2*nbytes);
XP_mul(tmp[3], nbytes, x, nbytes, y);
if (sx != sy)
XP_neg(nbytes, z, tmp[3], 1);
else
memcpy(z, tmp[3], nbytes);
z[nbytes-1] &= msb;
{
int i;
if (tmp[3][nbytes-1]&~msb)
RAISE(MP_Overflow);
for (i = 0; i < nbytes; i++)
if (tmp[3][i+nbytes] != 0)
RAISE(MP_Overflow);
}
if (sx == sy && sign(z))
RAISE(MP_Overflow);
return z;
}
T MP_div(T z, T x, T y) {
int sx, sy;
assert(x); assert(y); assert(z);
sx = sign(x);
sy = sign(y);
if (sx) {
XP_neg(nbytes, tmp[0], x, 1);
x = tmp[0];
x[nbytes-1] &= msb;
}
if (sy) {
XP_neg(nbytes, tmp[1], y, 1);
y = tmp[1];
y[nbytes-1] &= msb;
} else {
memcpy(tmp[1], y, nbytes);
y = tmp[1];
}
if (!XP_div(nbytes, z, x, nbytes, y, tmp[2], tmp[3]))
RAISE(MP_Dividebyzero);
if (sx != sy) {
XP_neg(nbytes, z, z, 1);
if (!iszero(tmp[2]))
XP_diff(nbytes, z, z, 1);
z[nbytes-1] &= msb;
} else if
cii11.rar （81个子文件） 
cii11 
install.html 15KB
packing.lst 1KB include fmt.h 1KB array.h 531B text.h 2KB chan.h 335B xp.h 1KB sem.h 486B str.h 2KB except.h 2KB mp.h 2KB arrayrep.h 302B bit.h 827B ring.h 691B atom.h 335B thread.h 583B mem.h 910B assert.h 265B seq.h 534B arena.h 565B list.h 685B arith.h 312B table.h 704B stack.h 368B set.h 769B ap.h 1KB src set.c 7KB ap.c 9KB chan.c 937B memmove.c 473B arith.c 636B mp.c 16KB xp.c 6KB thread-nt.c 7KB arena.c 2KB array.c 2KB text.c 10KB strncmp.c 393B seq.c 3KB fmt.c 9KB memcmp.c 378B table.c 3KB bit.c 4KB list.c 2KB strerror.c 405B mem.c 1KB ring.c 4KB libcii.def 3KB atom.c 5KB str.c 6KB memchk.c 3KB stack.c 954B except.c 837B thread.c 7KB swtch.s 4KB assert.c 219B README 548B makefile 7KB examples sieve.c 2KB integer.c 881B wf.c 2KB idents.c 909B ids.c 599B getword.h 191B mpcalc.c 5KB kref.c 3KB words.c 1018B iref.c 4KB basename.c 720B double.c 1KB calc.c 3KB cref.c 3KB sort.c 2KB integer.h 399B spin.c 1KB getword.c 725B xref.c 3KB custom.mk 8B CPYRIGHT 881B history.html 13KB makefile.nt 8KB资源评论
