lip.c

应用密码学这本书的源代码

		sa = -sa;
	d = *(a += sa);
	while (--sa)
	{
		d <<= NBITS;
		d += *(--a);
	}
	return (d);
}

void
zultoz(
        unsigned long a[],
        long b,
        verylong *c
        )
{
        register long i;
        if (b<0) return;
        zuintoz(a[b-1],c);
        for (i=b-2;i>=0;i--) {
                register long j=1;
                register unsigned long d = a[i];
                zlshift(*c,CHARL*SIZEOFLONG,c);
                while (d) {
                        (*c)[j++] += (long)(d&RADIXM);
                        d >>= NBITS;
                }

        }
}

long
ztoul(
        verylong a,
        unsigned long b[],
        long *c
        )
{
        STATIC verylong ca = 0;
        STATIC verylong aux = 0;
        register long i=1;
        if (*c<=0) return(0);
        if (ziszero(a)) {
                b[0] = 0;
                *c = 1;
                return(1);
        }
        zcopy(a,&ca);
        zabs(&ca);
        for (;;) {
                zlowbits(ca,CHARL*SIZEOFLONG,&aux);
                if (i>*c) return(0);
                b[i-1] = ztouint(aux);
                zrshift(ca,CHARL*SIZEOFLONG,&ca);
                if (ziszero(ca)) {
                        *c = i;
                        return(1);
                }
                i++;
        }
}

void
zsbastoz(
	long base,
	long row[],
	long len,
	verylong *n
	)
{
	register long i;

	zintoz(row[len - 1], n);
	for (i = len - 1; i--;)
	{
		zsmul(*n, base, n);
		zsadd(*n, row[i], n);
	}
}

void
zbastoz(
	verylong base,
	verylong row[],
	long len,
	verylong *n
	)
{
	register long i;

	zcopy(row[len - 1], n);
	for (i = len - 1; i--;)
	{
		zmulin(base, n);
		zadd(*n, row[i], n);
	}
}

long 
zstobas(
	verylong n,
	long base,
	long row[],
	long *len
	)
{
 /* return 1 if it fits, 0 otherwise */
 /* n >= 0, base > 1 */
	register long i = 0;
	register long max = *len;
	STATIC verylong q = 0;
	STATIC verylong nn = 0;

	if (max < 1)
		return (0);
	if (base < 0)
		base = -base;
	if (base <= 1)
		return (0);
	*len = 0;
	row[0] = 0;
	zcopy(n, &nn);
	zabs(&nn);
	for (;;)
	{
		row[i] = zsdiv(nn, base, &q);
		i++;
		if ((q[1] == 0) && (q[0] == 1))
		{
			*len = i;
			FREE2SPACE(q,nn);
			return (1);
		}
		if (i == max) {
			FREE2SPACE(q,nn);
			return (0);
		}
		zswap(&q, &nn);
	}
}

long 
zstosymbas(
	verylong n,
	long base,
	long row[],
	long *len
	)
{
 /* return 1 if it fits, 0 otherwise */
 /* n >= 0, base > 1 */
	register long i = 0;
	register long max = *len;
	register long hbase;
	STATIC verylong q = 0;
	STATIC verylong nn = 0;

	if (max < 1)
		return (0);
	if (base < 0)
		base = -base;
	if (base <= 1)
		return (0);
	hbase = (base >> 1);
	*len = 0;
	row[0] = 0;
	zcopy(n, &nn);
	zabs(&nn);
	for (;;)
	{
		if ((row[i] = zsdiv(nn, base, &q)) > hbase)
		{
			row[i] -= base;
			zsadd(q, 1, &q);
		}
		i++;
		if ((q[1] == 0) && (q[0] == 1))
		{
			*len = i;
			FREE2SPACE(q,nn);
			return (1);
		}
		if (i == max) {
			FREE2SPACE(q,nn);
			return (0);
		}
		zswap(&q, &nn);
	}
}

long 
ztobas(
	verylong n,
	verylong base,
	verylong row[],
	long *len
	)
{
 /* return 1 if it fits, 0 otherwise */
 /* n >= 0, base > 1 */
	register long i = 0;
	register long max = *len;
	STATIC verylong q = 0;
	STATIC verylong nn = 0;
	STATIC verylong lbase = 0;

	if (max < 1)
		return (0);
	zcopy(base, &lbase);
	zabs(&lbase);
	if (zscompare(base, 1) <= 0)
		return (0);
	*len = 0;
	zintoz(0, &(row[0]));
	zcopy(n, &nn);
	zabs(&nn);
	for (;;)
	{
		zdiv(nn, lbase, &q, &(row[i]));
		i++;
		if ((q[1] == 0) && (q[0] == 1))
		{
			*len = i;
			FREE2SPACE(q,nn); FREESPACE(lbase);
			return (1);
		}
		if (i == max) {
			FREE2SPACE(q,nn); FREESPACE(lbase);
			return (0);
		}
		zswap(&q, &nn);
	}
}

long 
ztosymbas(
	verylong n,
	verylong base,
	verylong row[],
	long *len
	)
{
 /* return 1 if it fits, 0 otherwise */
 /* n >= 0, base > 1 */
	register long i = 0;
	register long max = *len;
	STATIC verylong q = 0;
	STATIC verylong nn = 0;
	STATIC verylong lbase = 0;
	STATIC verylong hbase = 0;

	if (max < 1)
		return (0);
	zcopy(base, &lbase);
	zabs(&lbase);
	if (zscompare(base, 1) <= 0)
		return (0);
	z2div(lbase, &hbase);
	*len = 0;
	zintoz(0, &(row[0]));
	zcopy(n, &nn);
	zabs(&nn);
	for (;;)
	{
		zdiv(nn, lbase, &q, &(row[i]));
		if (zcompare(row[i], hbase) > 0)
		{
			zsub(row[i], lbase, &(row[i]));
			zsadd(q, 1, &q);
		}
		i++;
		if ((q[1] == 0) && (q[0] == 1))
		{
			*len = i;
			FREE2SPACE(q,nn); FREE2SPACE(lbase,hbase);
			return (1);
		}
		if (i == max) {
			FREE2SPACE(q,nn); FREE2SPACE(lbase,hbase);
			return (0);
		}
		zswap(&q, &nn);
	}
}

long 
zcompare(
	verylong a,
	verylong b
	)
{
	register long sa;
	register long sb;

	if (ALLOCATE && !a)
	{
		if (!b)
			return (0);
		if (b[0] < 0)
			return (1);
		if (b[0] > 1)
			return (-1);
		if (b[1])
			return (-1);
		return (0);
	}
	if (ALLOCATE && !b)
	{
		if (a[0] < 0)
			return (-1);
		if (a[0] > 1)
			return (1);
		if (a[1])
			return (1);
		return (0);
	}
 /* if (a==b) return (0); but who is comparing identical addresses? */
	if ((sa = *a) > (sb = *b))
		return (1);
	if (sa < sb)
		return (-1);
	if (sa < 0)
		sa = (-sa);
	a += sa;
	b += sa;
	for (; sa; sa--)
	{
		if (*a > *b)
		{
			if (sb < 0)
				return (-1);
			return (1);
		}
		if (*a-- < *b--)
		{
			if (sb < 0)
				return (1);
			return (-1);
		}
	/*
	 * depending on the relative speed of various operations it might be
	 * better to do the following: if ((aux=(*a--)-(*b--))>0) { if (sb<0)
	 * return (-1); return (1); } else if (aux<0) { if (sb<0) return (1);
	 * return (-1); } where aux is a register long
	 */
	}
	return (0);
}

void
znegate(
	verylong *aa
	)
{
	verylong a = *aa;

	if (!a)
		return;
	if (a[1] || a[0] != 1)
		a[0] = (-a[0]);
}

void
zsadd(
	verylong a,
	long d,
	verylong *b
	)
{
	STATIC verylong x = 0;

	zintoz(d, &x);
	zadd(a, x, b);
	FREESPACE(x);
}

static void
zaddls(
	verylong a,
	verylong b,
	verylong c
	)
{
/* low level c = a+b, b shorter than a, output can be input */
	register long sa = *a;
	register long sb = *b;
	register long carry = 0;
	register long i;
	register verylong pc;

 /* we know that sa and sb are both >0 or both <0 */
	pc = &c[0];
	if (sa < 0)
	{
		sa = -sa;
		sb = -sb;
	}
	for (i = 1; i <= sb; i++)
	{
		if ((*(++pc) = (*(++a)) + (*(++b)) + carry) < RADIX)
			carry = 0;
		else
		{
			*pc -= RADIX;
			carry = 1;
		}
	}
	for (; i <= sa; i++)
	{
		if ((*(++pc) = (*(++a)) + carry) < RADIX)
			carry = 0;
		else
		{
			*pc -= RADIX;
			carry = 1;
		}
	}
	if (carry)
	{
		c[0] = sa + 1;
		*(++pc) = 1;
	}
	else
		c[0] = sa;
}

void
zsubpos(
	verylong a,
	verylong b,
	verylong *cc
	)
{
	register long sa = a[0];
	register long sb = b[0];
	register long carry = 0;
	register long i;
	register verylong pc;
	verylong c = *cc;

	if (ALLOCATE && !b)
	{
		if (a)
			zcopy(a, cc);
		else
			zzero(cc);
		return;
	}
	if (ALLOCATE && !a)
	{
		zzero(cc);
		return;
	}
	zsetlength(&c, sa, "in zsubpos, third argument");
	/* if *cc == a, then nothing will happen */
	/* if *cc == b, then b might point to freed space, so */
	if (b == *cc) b = c;
	*cc = c;
	pc = &c[0];
	for (i = 1; i <= sb; i++)
	{
		if ((*(++pc) = (*(++a)) - (*(++b)) - carry) >= 0)
			carry = 0;
		else
		{
			*pc += RADIX;
			carry = 1;
		};
	}
	for (; i <= sa; i++)
	{
		if ((*(++pc) = (*(++a)) - carry) >= 0)
			carry = 0;
		else
		{
			*pc += RADIX;
			carry = 1;
		};
	}
	i = sa;
	while ((i > 1) && (!(*pc)))
	{
		i--;
		pc--;
	}
	c[0] = i;
}

void
zadd(
	verylong a,
	verylong b,
	verylong *cc
	)
{
	register long sa;
	register long sb;
	register long anegative;
	verylong c = *cc;

	if (ALLOCATE && !a)
	{
		if (b)
			zcopy(b, cc);
		else
			zzero(cc);
		return;
	}
	if (ALLOCATE && !b)
	{
		zcopy(a, cc);
		return;
	}
	if ((anegative = ((sa = a[0]) < 0)) == ((sb = b[0]) < 0))
	{
	/* signs a and b are the same */
		register long i;
		if (anegative)
		{
			sa = -sa;
			sb = -sb;
		}
		zsetlength(&c, (sa > sb ? sa : sb) + 1, "in zadd, third argument");
		if (a == *cc) a = c;
		if (b == *cc) b = c;
		*cc = c;
		if (sa == sb)
		{
			register verylong pc;
			pc = &c[0];
			i = 0;
			for (; sa; sa--)
			{
				if ((*(++pc) = (*(++a)) + (*(++b)) + i) < RADIX)
					i = 0;
				else
				{
					*pc -= RADIX;
					i = 1;
				}
			}
			if (i)
			{
				c[0] = sb + 1;
				*(++pc) = 1;
			}
			else
				c[0] = sb;
		}
		else if (sa > sb)
			zaddls(a, b, c);
		else
			zaddls(b, a, c);
		if (anegative)
			c[0] = -c[0];
	/* if anegative, then c cannot be zero */
	}
	else
	{
	/* signs a and b are different */
		verylong old;
		verylong oldc;

		oldc = c;
		if (anegative)
		{
			a[0] = -a[0];
			old = a;
		}
		else
		{
			b[0] = -b[0];
			old = b;
		}
	/* the one that's negative cannot be zero */
		if (!(sa = zcompare(a, b)))
		{
			zzero(&c);
			*cc = c;
			if (anegative)
			{
				if (old != oldc)
					a[0] = -a[0];
			}
			else if (old != oldc)
				b[0] = -b[0];
		}
		else if (sa > 0)
		{
			zsubpos(a, b, &c);
			*cc = c;
			if (anegative)
			{
				c[0] = -c[0];
				if (old != oldc)
					a[0] = -a[0];
			}
			else if (old != oldc)
				b[0] = -b[0];
		}
		else
		{
			zsubpos(b, a, &c);
			*cc = c;
			if (!anegative)
			{
				c[0] = -c[0];
				if (old != oldc)
					b[0] = -b[0];
			}
			else if (old != oldc)
				a[0] = -a[0];
		}
	}
}

void
zsub(
	verylong a,
	verylong b,
	verylong *cc
	)
{
	register long sa;
	register long sb;
	register long anegative;
	verylong c = *cc;

	if (ALLOCATE && !b)
	{
		if (a)
			zcopy(a, cc);
		else
			zzero(cc);
		return;
	}
	if (ALLOCATE && !a)
	{
		zcopy(b, cc);
		znegate(cc);
		return;
	}
	if ((anegative = ((sa = a[0]) < 0)) == ((sb = b[0]) < 0))
	{
	/* signs a and b are the same */
		register long carry = 0;
		register long i;
		register verylong pc;
		register long agrb;

		if (!(agrb = zcompare(a, b)))
		{
			zzero(cc);
			return;
		}
		if ((agrb > 0 && anegative) || (agrb < 0 && !anegative))
		{
			pc = a;
			a = b;
			b = pc;
			sa = *a;
			sb = *b;
		}
		if (anegative)
		{
			sa = -sa;
			sb = -sb;
		}
		zsetlength(&c, sa, "in zsub, third argument");
                if (b == *cc) b = c;
		*cc = c;
		pc = &c[0];
		for (i = 1; i <= sb; i++)
		{
			if ((*(++pc) = (*(++a)) - (*(++b)) - carry) >= 0)
				carry = 0;
			else
			{
				*pc += RADIX;
				carry = 1;
			};
		}
		for (; i <= sa; i++)
		{
			if ((*(++pc) = (*(++a)) - carry) >= 0)
				carry = 0;
			else
			{
				*pc += RADIX;
				carry = 1;
			};
		}
		i = sa;
		while ((i > 1) && (!(*pc)))
		{
			i--;
			pc--;
		}
		if (agrb > 0)
			c[0] = i;
		else
			c[0] = -i;
	}
	else
	{
	/* signs a and b are different */
		verylong old;
		verylong oldc;

		oldc = c;
		if (anegative)
		{
			a[0] = -a[0];
			old = a;
		}
		else
		{
			b[0] = -b[0];
			old = b;
		}
	/* the one that's negative cannot be zero */
		zadd(a, b, &c);
		*cc = c;
		if (anegative)
		{
			c[0] = -c[0];
			if (old != oldc)
				a[0] = -a[0];
		}
		else if (old != oldc)
			b[0] = -b[0];
	}
}

void
zsmul(
	verylong a,
	long d,
	verylong *bb
	)
{
	register long sa;
	register long i;
	register verylong pb;
	register long bnegative = 0;
	verylong b = *bb;

	if (( d >= RADIX) || (-d >= RADIX)) {
		STATIC verylong x = 0;
		zintoz(d,&x);
		zmulin(a,&x);
		zcopy(x,bb);
		FREESPACE(x);
		return;
	}

	if (ALLOCATE && !a)
	{
		zzero(bb);
		return;
	}