bigint.c

iscsi源代码 UNH的progect 有initiator端和target端的源码

/*	security/math/bigint.c

	vi: set autoindent tabstop=8 shiftwidth=4 :

*/
/*
	Copyright (C) 2001-2003 InterOperability Lab (IOL)
	University of New Hampshier (UNH)
	Durham, NH 03824

	This program is free software; you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation; either version 2, or (at your option)
	any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program; if not, write to the Free Software
	Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
	USA.

	The name of IOL and/or UNH may not be used to endorse or promote products
	derived from this software without specific prior written permission.
*/

#include "linux/string.h"
#include "linux/slab.h"
#include "linux/stddef.h"

#include "../../common/my_memory.h"

#include "bigint.h"

static unsigned int bigint_bitmaps[] = {
	0x00000001, 0x00000002, 0x00000004, 0x00000008,
	0x00000010, 0x00000020, 0x00000040, 0x00000080,
	0x00000100, 0x00000200, 0x00000400, 0x00000800,
	0x00001000, 0x00002000, 0x00004000, 0x00008000,
	0x00010000, 0x00020000, 0x00040000, 0x00080000,
	0x00100000, 0x00200000, 0x00400000, 0x00800000,
	0x01000000, 0x02000000, 0x04000000, 0x08000000,
	0x10000000, 0x20000000, 0x40000000, 0x80000000
};

#ifdef BIGINT_DEBUG
static unsigned long memory_used = 0;
#endif

int
bigint_init(struct bigint_t *n, unsigned len)
{
#ifdef BIGINT_DEBUG
	if (n == NULL)
		return 0;
#endif
	memset(n, 0, sizeof (struct bigint_t));
	if (!len)
		len = BIGINT_INIT_DATALEN;
	if ((n->data =
	     (unsigned int *) my_kmalloc(len * sizeof (unsigned int),
					 "bigint data")) == NULL)
		return 0;
	n->size = len;
	memset(n->data, 0, n->size * sizeof (unsigned int));
#ifdef BIGINT_DEBUG
	memory_used += n->size * sizeof (unsigned int);
#endif
	SET_VALID(n);
	return 1;
}

int
bigint_clean(struct bigint_t *n)
{
#ifdef BIGINT_DEBUG
	if (!bigint_check(n))
		return 0;
#endif
	if (IS_VALID(n) && (n->data))
		my_kfree((void **) &n->data, "bigint data");
#ifdef BIGITN_DEBUG
	memory_used -= n->size * sizeof (unsigned int);
#endif
	memset(n, 0, sizeof (struct bigint_t));
	return 1;
}

struct bigint_t *
bigint_new(unsigned int size)
{
	struct bigint_t *r;
	if ((r =
	     (struct bigint_t *) my_kmalloc(sizeof (struct bigint_t),
					    "bigint")) == NULL)
		return NULL;
	r->flags = 0;
	r->offset = 0;
	r->data = NULL;
	if (size == 0)
		size++;
	if ((r->data =
	     (unsigned int *) my_kmalloc(size * sizeof (unsigned int),
					 "data")) == NULL) {
		my_kfree((void **) &r, "bigint data");
		return NULL;
	}
	r->size = size;
#ifdef BIGINT_DEBUG
	memory_used += sizeof (struct bigint_t);
	memory_used += r->size * (sizeof (unsigned int));
#endif
	SET_VALID(r);
	return r;
}

void
bigint_free(struct bigint_t *n)
{
	if (n != NULL) {
		if (n->data != NULL) {
			my_kfree((void **) &n->data, "data");
#ifdef BIGINT_DEBUG
			memory_used -= n->size * (sizeof (unsigned int));
#endif
			my_kfree((void **) &n, "bigint");
		}
#ifdef BIGINT_DEBUG
		memory_used -= sizeof (struct bigint_t);
#endif
	}
}

void
bigint_print(const struct bigint_t *n)
{
	int i;

	printk("\n***********big integer***********\n");
	printk("size: %d\n", n->size);
	printk("offset: %d\n", n->offset);
	if (IS_NEGATIVE(n))
		printk("negative\n");
	printk("data:\n");
	for (i = n->offset; i > 0; i--)
		printk("%08x\n", n->data[i - 1]);
	printk("****************end***************\n");
}

#ifdef BIGINT_DEBUG
void
bigint_checkmemory()
{
	printk("\n***********big integer***********\n");
	printk("memory used: %lu byte(s)\n", memory_used);
	printk("****************end***************\n");
}
#endif

int
bigint_check(const struct bigint_t *n)
{
	if (n == NULL)
		return 0;
	if ((n->data == NULL) && (n->offset > 0))
		return 0;
	if (n->offset > n->size)
		return 0;
	return 1;
}

int
bigint_clear(struct bigint_t *n)
{
	n->flags = 0;
	n->offset = 0;
	if (n->size)
		memset(n->data, 0, n->size * sizeof (unsigned int));
	return 1;
}

int
bigint_trim(struct bigint_t *n)
{
	while (n->offset && (n->data[n->offset - 1] == 0))
		n->offset--;
	return 1;
}

int
bigint_extend(struct bigint_t *n, unsigned int size)
{
	unsigned int *temp;

	if (size <= n->size)
		return 1;
	if ((temp =
	     (unsigned int *) my_kmalloc(size * sizeof (unsigned int),
					 "temp")) == NULL)
		return 0;
#ifdef BIGINT_DEBUG
	memory_used += (size - n->size) * sizeof (unsigned int);
#endif
	memset(temp, 0, sizeof (unsigned int) * size);
	if (n->data) {
		memcpy(temp, n->data, sizeof (unsigned int) * n->offset);
		my_kfree((void **) &n->data, "data");
	}
	n->data = temp;
	n->size = size;
	return 1;
}

int
bigint_cpy(struct bigint_t *a, const struct bigint_t *b)
{
	if (a == b)
		return 1;
	a->flags = b->flags;
	if (a->offset < b->offset) {
		if (!bigint_extend(a, b->offset))
			return 0;
	}
	if (b->offset > 0)
		memcpy(a->data, b->data, b->offset * sizeof (unsigned int));
	a->offset = b->offset;
	return 1;
}

unsigned int
bigint_bits(const struct bigint_t *a)
{
	int nw;
	unsigned int d;
	int i;

	nw = 0;
	if (a->offset) {
		nw = (a->offset - 1) * sizeof (unsigned int) * 8;
		d = a->data[a->offset - 1];
		for (i = 32; i > 0; i--) {
			if (bigint_bitmaps[i - 1] & d) {
				nw += i;
				break;
			}
		}
	}
	return nw;
}

unsigned int
bigint_bytes(const struct bigint_t *a)
{
	int nw;
	unsigned int d;

	nw = 0;
	if (a->offset) {
		nw = (a->offset - 1) * sizeof (unsigned int);
		d = a->data[a->offset - 1];
		if (d & 0xFF000000)
			nw += 4;
		else if (d & 0x00FF0000)
			nw += 3;
		else if (d & 0x0000FF00)
			nw += 2;
		else if (d & 0x000000FF)
			nw += 1;
	}
	return nw;
}

int
bigint_cmp(const struct bigint_t *a, const struct bigint_t *b)
{
	int i;

#ifdef BIGINT_DEBUG
	if ((!bigint_check(a)) || (!bigint_check(b)))
		return 0;
#endif

	if (a->offset > b->offset)
		return 1;
	if (a->offset < b->offset)
		return -1;
	for (i = a->offset; i > 0; i--) {
		if (a->data[i - 1] > b->data[i - 1])
			return 1;
		if (a->data[i - 1] < b->data[i - 1])
			return -1;
	}
	return 0;
}

int
bigint_add_inner(struct bigint_t *r,
		 const struct bigint_t *a, const struct bigint_t *b)
{
	const struct bigint_t *tmp;
	struct bigint_t ret;
	unsigned int max;
	unsigned int min;
	unsigned int *ap;
	unsigned int *bp;
	unsigned int *rp;
	unsigned long long carry = 0;	//should be long long in linux
	unsigned int i;

	if (b->offset > a->offset) {
		tmp = a;
		a = b;
		b = tmp;
	}
	max = a->offset;
	min = b->offset;
	if (!bigint_init(&ret, max + 1))
		return 0;
	ap = a->data;
	bp = b->data;
	rp = ret.data;
	for (i = 0; i < min; i++) {
		carry += (unsigned long long) (ap[i]) + (unsigned long long) (bp[i]);	//should be long long in linux
		rp[i] = (unsigned int) (carry & 0xFFFFFFFF);
		carry >>= 32;
	}
	while (carry && (i < max)) {
		carry += (unsigned long long) ap[i];	//should be long long in linux
		rp[i] = (unsigned int) (carry & 0xFFFFFFFF);
		carry >>= 32;
		i++;
	}
	if (!carry) {
		for (; i < max; i++)
			rp[i] = ap[i];
	} else
		rp[i] = (unsigned int) carry;
	ret.offset = max + 1;
	bigint_trim(&ret);
	if (!bigint_cpy(r, &ret)) {
		bigint_clean(&ret);
		return 0;
	}
	bigint_clean(&ret);
	return 1;
}

int
bigint_sub_inner(struct bigint_t *r,
		 const struct bigint_t *a, const struct bigint_t *b)
{
	const struct bigint_t *tmp;
	struct bigint_t ret;
	unsigned int max;
	unsigned int min;
	unsigned int *ap;
	unsigned int *bp;
	unsigned int *rp;
	unsigned int carry = 0;
	unsigned int i;
	int neg;

#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) || (!bigint_check(a)) || (!bigint_check(b)))
		return 0;
#endif

	neg = 0;
	if (bigint_cmp(a, b) < 0) {
		neg = 1;
		tmp = a;
		a = b;
		b = tmp;
	}
	max = a->offset;
	min = b->offset;
	if (!bigint_init(&ret, max))
		return 0;
	if (neg)
		SET_NEGATIVE(&ret);
	ap = a->data;
	bp = b->data;
	rp = ret.data;
	for (i = 0; i < min; i++) {
		if (carry) {
			carry = (ap[i] <= bp[i]);
			rp[i] = ap[i] - bp[i] - 1;
		} else {
			carry = (ap[i] < bp[i]);
			rp[i] = ap[i] - bp[i];
		}
	}
	while (carry && (i < max)) {
		rp[i] = ap[i] - 1;
		carry = (!ap[0]);
		i++;
	}
	if (!carry) {
		for (; i < max; i++)
			rp[i] = ap[i];
	}
	ret.offset = max;
	bigint_trim(&ret);
	if (!bigint_cpy(r, &ret)) {
		bigint_clean(&ret);
		return 0;
	}
	bigint_clean(&ret);
	return 1;
}

int
bigint_add(struct bigint_t *r,
	   const struct bigint_t *a, const struct bigint_t *b)
{
#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) || (!bigint_check(a)) || (!bigint_check(b)))
		return 0;
#endif

	if (IS_NEGATIVE(a) && IS_NEGATIVE(b)) {
		if (bigint_add_inner(r, a, b)) {
			SET_NEGATIVE(r);
			return 1;
		} else
			return 0;
	}
	if (!IS_NEGATIVE(a) && IS_NEGATIVE(b))
		return bigint_sub_inner(r, a, b);
	if (IS_NEGATIVE(a) && !IS_NEGATIVE(b))
		return bigint_sub_inner(r, b, a);
	if (!IS_NEGATIVE(a) && !IS_NEGATIVE(b))
		return bigint_add_inner(r, a, b);
	return 0;
}

int
bigint_sub(struct bigint_t *r,
	   const struct bigint_t *a, const struct bigint_t *b)
{
#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) || (!bigint_check(a)) || (!bigint_check(b)))
		return 0;
#endif

	if (IS_NEGATIVE(a) && IS_NEGATIVE(b)) {
		if (bigint_sub_inner(r, a, b)) {
			if (IS_NEGATIVE(r))
				SET_POSITIVE(r);
			else
				SET_NEGATIVE(r);
			return 1;
		} else
			return 0;
	}
	if (!IS_NEGATIVE(a) && IS_NEGATIVE(b))
		return bigint_add_inner(r, a, b);
	if (IS_NEGATIVE(a) && !IS_NEGATIVE(b)) {
		if (bigint_add_inner(r, b, a)) {
			SET_NEGATIVE(r);
			return 1;
		} else
			return 0;
	}
	if (!IS_NEGATIVE(a) && !IS_NEGATIVE(b))
		return bigint_sub_inner(r, a, b);
	return 0;
}

int
bigint_mul(struct bigint_t *r,
	   const struct bigint_t *a, const struct bigint_t *b)
{
	const struct bigint_t *tmp;
	struct bigint_t ret;
	unsigned int al;
	unsigned int bl;
	unsigned int rl;
	unsigned int *rp;
	unsigned int *ap;
	unsigned int *bp;
	unsigned int *cp;
	unsigned int i;
	unsigned int j;
	unsigned long long carry;

#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) || (!bigint_check(a)) || (!bigint_check(b)))
		return 0;
#endif

	if (IS_ZERO(a) || IS_ZERO(b)) {
		SET_ZERO(r);
		return 1;
	}
	if (IS_ONE(a)) {
		if (!bigint_cpy(r, b))
			return 0;
		if (IS_NEGATIVE(a) || IS_NEGATIVE(b))
			SET_NEGATIVE(r);
		return 1;
	}
	if (IS_ONE(b)) {
		if (!bigint_cpy(r, a))
			return 0;
		if (IS_NEGATIVE(a) || IS_NEGATIVE(b))
			SET_NEGATIVE(r);
		return 1;
	}
	if (b->offset > a->offset) {
		tmp = a;
		a = b;
		b = tmp;
	}
	al = a->offset;
	bl = b->offset;
	rl = al + bl;
	if (!bigint_init(&ret, rl))
		return 0;
	if (IS_NEGATIVE(a) || IS_NEGATIVE(b))
		SET_NEGATIVE(&ret);
	ap = a->data;
	bp = b->data;
	rp = ret.data;
	cp = &(rp[al]);
	for (i = 0; i < bl; i++) {
		carry = 0;
		for (j = 0; j < al; j++) {
			carry +=
			    ((unsigned long long) ap[j]) *
			    ((unsigned long long) bp[i])
			    + ((unsigned long long) rp[i + j]);
			rp[i + j] = (unsigned int) (carry & 0xFFFFFFFF);
			carry >>= 32;
		}
		cp[i] = (unsigned int) carry;
	}
	ret.offset = rl;
	bigint_trim(&ret);
	if (!bigint_cpy(r, &ret)) {
		bigint_clean(&ret);
		return 0;
	}
	bigint_clean(&ret);
	if (IS_NEGATIVE(a) || IS_NEGATIVE(b))
		SET_NEGATIVE(r);
	return 1;
}

int
bigint_fix(struct bigint_t *a, const struct bigint_t *n)
{
	while (IS_NEGATIVE(a)) {
		SET_POSITIVE(a);
		if (!bigint_sub(a, n, a))
			return 0;
	}
	return 1;
}

int
bigint_lsh(struct bigint_t *r, const struct bigint_t *a, unsigned int n)
{
	unsigned int nw;