liptimer.c

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

			i--;
		b[0] = i;
	}
	for (i = hal + 1; i <= al; i++)
		(*a1)[i - hal] = a[i];
	(*a1)[0] = al - hal;
	if (bbig)
	{
		for (i = hal + 1; i <= restoreb0; i++)
			(*a3)[i - hal] = b[i];
		(*a3)[0] = restoreb0 - hal;
	}
	kar_mul0(a, b, a4, shi + 5);
	zadd(a, (*a1), a0);
	a[0] = al;
	if (bbig)
	{
		kar_mul0((*a1), (*a3), c, shi + 5);
		zadd(b, (*a3), a2);
		b[0] = restoreb0;
		kar_mul0((*a0), (*a2), a3, shi + 5);
	}
	else
		kar_mul0((*a0), b, a3, shi + 5);
	zsubpos((*a3), (*a4), a3);
	if (bbig)
		zsubpos((*a3), *c, a3);
	zlshift((*a3), hal * NBITS, a3);
	hal <<= 1;
	if (bbig)
	{
		for (i = (*c)[0]; i; i--)
			(*c)[i + hal] = (*c)[i];
		for (i = hal; i > (*a4)[0]; i--)
			(*c)[i] = 0;
		for (; i; i--)
			(*c)[i] = (*a4)[i];
		(*c)[0] += hal;
	}
	else
	{
		for (i = (*a4)[0]; i >= 0; i--)
			(*c)[i] = (*a4)[i];
	}
	zadd(*c, (*a3), c);
}


#define zaddmulsq0(sql, sqa, sqb) \
{ \
        register long lsqi = (sql); \
        register long lsqs = *(sqb); \
        register verylong lsqa = (sqa); \
        register verylong lsqb = (sqb); \
        long lsqcarry = 0; \
 \
        lsqb++; \
        for (; lsqi > 0; lsqi--) \
        { \
                zaddmulp0(lsqa, *lsqb, lsqs, &lsqcarry); \
                lsqa++; \
                lsqb++; \
        } \
        *lsqa += lsqcarry; \
/* Be careful, the last lama is unnormalized */ \
}


#define zaddmulpsq0(_a, _b, _t) \
{ \
        register at = *(_a); \
        register long aa = (at + (_b) * (_b)) & RADIXM; \
 \
        *(_t) = (long) (0.25 + fradix_inv0 * (((double) (at - aa)) \
			      + ((double) (_b)) * ((double) (_b)))); \
        *(_a) = aa; \
}


kar_sq0(
	verylong a,
	verylong *c,
	long shi
	)
{
	register long al;
	register long hal;
	register long i;
	register verylong pc;
	verylong *a0;
	verylong *a1;
	verylong *a2;

	zsetlength(c, (i = ((al = a[0]) << 1)), "in kar_sq, second argument");
	if ((shi >= (3 * KAR_DEPTH)) || (al < K_S_C))
	{
		register unsigned long uncar;
		long carry = 0;
		pc = &(*c)[1];
		for (; i > 0; i--)
			*pc++ = 0;
		for (hal = 1; hal <= al; hal++)
		{
			i += 2;
			{
				zaddmulsq0(al - hal, &((*c)[i]), &(a[hal]));
			}
			uncar = ((*c)[i - 1] << 1) + carry;
			(*c)[i - 1] = uncar & RADIXM;
			uncar = ((*c)[i] << 1) + (uncar >> NBITS);
			{
				zaddmulpsq0(&(*c)[i - 1], a[hal], &carry);
			}
			uncar += carry;
			carry = uncar >> NBITS;
			(*c)[i] = uncar & RADIXM;
		}
		while ((i > 1) && (!((*c)[i])))
			i--;
		(*c)[0] = i;
		return;
	}
	a0 = &(kar_mem[shi]);
	a1 = &(kar_mem[shi + 1]);
	a2 = &(kar_mem[shi + 2]);
	hal = ((al + 1) >> 1);
	zsetlength(a0, al + hal + 2, "in kar_sq, locals\n");
	zsetlength(a1, al + 2, "");
	zsetlength(a2, al, "");
	i = hal;
	while ((i > 1) && (!(a[i])))
		i--;
	a[0] = i;
	for (i = hal + 1; i <= al; i++)
		(*a0)[i - hal] = a[i];
	(*a0)[0] = al - hal;
	kar_sq0(a, a1, shi + 3);
	zadd(a, (*a0), a2);
	kar_sq0((*a0), c, shi + 3);
	a[0] = al;
	kar_sq0((*a2), a0, shi + 3);
	zsubpos((*a0), (*a1), a0);
	zsubpos((*a0), *c, a0);
	zlshift((*a0), hal * NBITS, a0);
	hal <<= 1;
	for (i = (*c)[0]; i; i--)
		(*c)[i + hal] = (*c)[i];
	for (i = hal; i > (*a1)[0]; i--)
		(*c)[i] = 0;
	for (; i; i--)
		(*c)[i] = (*a1)[i];
	(*c)[0] += hal;
	zadd(*c, (*a0), c);
}
/* SINGLE_MUL = 1, PLAIN = 0, KARAT = 0 */
/* warning: must first convert to 26 bit radix */


void
zmul1(
        verylong a,
        verylong b,
        verylong *c
        )
{       /* output not input */
        register long aneg;
        register long bneg;
        verylong olda;
        verylong oldb;

        if (ALLOCATE && (!a || !b))
        {
                zzero(c);
                return;
        }
        if (a == b)
        {
                zsq(a, c);
                return;
        }
        if (!kar_mem_initialized)
        {
                kar_mem_initialized = 1;
                for (aneg = (5 * KAR_DEPTH) - 1; aneg >= 0; aneg--)
                        kar_mem[aneg] = (verylong) 0;
        }
        olda = a;
        oldb = b;
        if (aneg = (*a < 0))
                a[0] = -a[0];
        if (bneg = (*b < 0))
                b[0] = -b[0];
        if (*a > *b)
                kar_mul1(a, b, c, (long) 0);
        else
                kar_mul1(b, a, c, (long) 0);
        if (aneg != bneg && ((*c)[1] || (*c)[0] != 1))
                (*c)[0] = -(*c)[0];
        if (aneg)
                olda[0] = -olda[0];
        if (bneg)
                oldb[0] = -oldb[0];
}


void
zsq1(
        verylong a,
        verylong *c
        )
{       /* output is not input */
        register long aneg;

        if (ALLOCATE && !a)
        {
                zzero(c);
                return;
        }
        if (!kar_mem_initialized)
        {
                kar_mem_initialized = 1;
                for (aneg = (5 * KAR_DEPTH) - 1; aneg >= 0; aneg--)
                        kar_mem[aneg] = (verylong) 0;
        }
        if (aneg = (*a < 0))
                a[0] = -a[0];
        kar_sq1(a, c, (long) 0);
        if (aneg)
                a[0] = -a[0];
}

#define LO1(x) (((unsigned long *) &x)[1])
#define HI1(x) (((unsigned long *) &x)[0])
static void zsubpos1();

typedef union { double d; unsigned long rep[2]; } d_or_rep;

#define FetchHiLo1(hi,lo,x) \
{ \
   d_or_rep _l_xx; \
   _l_xx.d = x; \
   hi = _l_xx.rep[0]; \
   lo = _l_xx.rep[1]; \
}

void zaddmul1(
        long ams,
        long *ama,
        long *amb
        )
{
        register long carry = 0;
        register long i = (*amb++);
        register double dams = (double) ams;
        register double xx;
        register double yy;
        register unsigned long lo_wd, lo;
        register unsigned long hi_wd, hi;

        xx  =  ((double) (*amb))*dams + 4503599627370496.0;
        for (; i > 1; i--)
        {
                yy =  ((double) (*(++amb)))*dams +4503599627370496.0;
                FetchHiLo1(hi_wd, lo_wd, xx);
                lo = lo_wd & 0x3FFFFFF;
                hi = ((hi_wd<<6)|(lo_wd>>26)) & 0x3FFFFFF;
                lo = lo + (*ama) + carry;
                *ama = lo & 0x3FFFFFF;
                carry = hi + (lo >> 26);
                ama++;
                xx = yy;
        }

        FetchHiLo1(hi_wd, lo_wd, xx);
        lo = lo_wd & 0x3FFFFFF;
        hi = ((hi_wd<<6)|(lo_wd>>26)) & 0x3FFFFFF;
        lo = lo + (*ama) + carry;
        *ama = lo & 0x3FFFFFF;
        carry = hi + (lo >> 26);
        ama++;
        *ama += carry;
}


static void
zaddls1(
        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) < (1L<<26))
                        carry = 0;
                else
                {
                        *pc -= (1L<<26);
                        carry = 1;
                }
        }
        for (; i <= sa; i++)
        {
                if ((*(++pc) = (*(++a)) + carry) < (1L<<26))
                        carry = 0;
                else
                {
                        *pc -= (1L<<26);
                        carry = 1;
                }
        }
        if (carry)
        {
                c[0] = sa + 1;
                *(++pc) = 1;
        }
        else
                c[0] = sa;
}

void
z2mul1(
        verylong n,
        verylong *rres
        )
{
        register long sn;
        register long i;
        register long carry = 0;
        verylong res = *rres;

        if (ALLOCATE && !n)
        {
                zzero(rres);
                return;
        }
        if ((!n[1]) && (n[0] == 1))
        {
                zzero(rres);
                return;
        }
        if ((sn = n[0]) < 0)
                sn = -sn;
        zsetlength(&res, sn + 1, "in z2mul, second argument");
        if (n == *rres) n = res;
        *rres = res;
        for (i = 1; i <= sn; i++)
        {
                if ((res[i] = (n[i] << 1) + carry) >= (1L<<26))
                {
                        res[i] -= (1L<<26);
                        carry = 1;
                }
                else
                        carry = 0;
        }
        if (carry)
                res[++sn] = 1;
        if (n[0] < 0)
                res[0] = -sn;
        else
                res[0] = sn;
}

void
zlshift1(
	verylong n,
	long k,
	verylong *rres
	)
{
	register long big;
	register long small;
	register long sn;
	register long i;
	register long cosmall;
	verylong res = *rres;

	if (ALLOCATE && !n)
	{
		zzero(rres);
		return;
	}
	if ((!n[1]) && (n[0] == 1))
	{
		zzero(rres);
		return;
	}
	if (!k)
	{
		if (n != *rres)
			zcopy(n, rres);
		return;
	}
	if (k < 0)
	{
		zrshift(n, -k, rres);
		return;
	}
	if (k == 1)
	{
		z2mul1(n, rres);
		return;
	}
	if ((sn = n[0]) < 0)
		sn = -sn;
	i = sn + (big = k / 26);
	if (small = k - big * 26)
	{
		zsetlength(&res, i + 1, "in zlshift, third argument");
		if (n == *rres) n = res;
		*rres = res;
		res[i + 1] = n[sn] >> (cosmall = 26 - small);
		for (i = sn; i > 1; i--)
			res[i + big] = ((n[i] << small) & ((1L<<26)-1)) + (n[i - 1] >> cosmall);
		res[big + 1] = (n[1] << small) & ((1L<<26)-1);
		for (i = big; i; i--)
			res[i] = 0;
		if (res[sn + big + 1])
			big++;
	}
	else
	{
		zsetlength(&res, i, "in zlshift, third argument");
		if (n == *rres) n = res;
		*rres = res;
		for (i = sn; i; i--)
			res[i + big] = n[i];
		for (i = big; i; i--)
			res[i] = 0;
	}
	if (n[0] > 0)
		res[0] = n[0] + big;
	else
		res[0] = n[0] - big;
}


void
zadd1(
        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) < (1L<<26))i = 0;
                                else
                                {
                                        *pc -= (1L<<26);
                                        i = 1;
                                }
                        }
                        if (i)
                        {
                                c[0] = sb + 1;
                                *(++pc) = 1;
                        }
                        else
                                c[0] = sb;
                }
                else if (sa > sb)
                        zaddls1(a, b, c);
                else
                        zaddls1(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)
                {
                        zsubpos1(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
                {
                        zsubpos1(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
zsub1(
	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 */