bigint.c

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

	unsigned int nb;
	unsigned int rb;
	int i;
	struct bigint_t tmp;

#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) || (!bigint_check(a)))
		return 0;
#endif
	if (n == 0)
		return bigint_cpy(r, a);
	nw = n / (sizeof (unsigned int) * 8);
	nb = n % (sizeof (unsigned int) * 8);
	rb = sizeof (unsigned int) * 8 - nb;
	if (!bigint_init(&tmp, a->offset + nw + 1))
		return 0;
	if (!nb)
		memcpy(&(tmp.data[nw]), a->data,
		       a->offset * sizeof (unsigned int));
	else {
		for (i = a->offset; i > 0; i--) {
			tmp.data[i + nw] |= a->data[i - 1] >> rb;
			tmp.data[i + nw - 1] = a->data[i - 1] << nb;
		}
	}
	tmp.offset = a->offset + nw + 1;
	bigint_trim(&tmp);
	bigint_cpy(r, &tmp);
	bigint_clean(&tmp);
	return 1;
}

int
bigint_rsh(struct bigint_t *r, const struct bigint_t *a, unsigned int n)
{
	unsigned int nw;
	unsigned int nb;
	unsigned int rb;
	unsigned int i;
	struct bigint_t tmp;

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

	if (n == 0)
		return bigint_cpy(r, a);
	if (bigint_bits(a) <= n) {
		if (!bigint_extend(r, 1))
			return 0;
		SET_ZERO(r);
		return 1;
	}
	nw = n / (sizeof (unsigned int) * 8);
	nb = n % (sizeof (unsigned int) * 8);
	rb = sizeof (unsigned int) * 8 - nb;
	if (!bigint_init(&tmp, a->offset - nw))
		return 0;
	if (!nb)
		memcpy(tmp.data, &(a->data[nw]),
		       sizeof (unsigned int) * (a->offset - nw));
	else {
		for (i = 0; i < a->offset - nw - 1; i++)
			tmp.data[i] |=
			    (a->data[i + nw] >> nb) | (a->
						       data[i + nw + 1] << rb);
		tmp.data[i] = a->data[i + nw] >> nb;
	}
	tmp.offset = a->offset - nw;
	bigint_trim(&tmp);
	bigint_cpy(r, &tmp);
	bigint_clean(&tmp);
	return 1;
}

int
bigint_mod(struct bigint_t *r,
	   const struct bigint_t *a, const struct bigint_t *b)
{
	unsigned int na;
	unsigned int nb;
	int i;
	struct bigint_t tmp;
	struct bigint_t ret;
	int res;

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

	res = 0;
	if (IS_ZERO(b))
		return 0;
	if (IS_ONE(b)) {
		if (!bigint_extend(r, 1))
			return 0;
		SET_ZERO(r);
		return 1;
	}
	if (!bigint_init(&ret, 0))
		return 0;
	if (IS_NEGATIVE(a) || IS_NEGATIVE(b))
		SET_NEGATIVE(&ret);
	if (!bigint_cpy(&ret, a)) {
		bigint_clean(&ret);
		return 0;
	}
	if (bigint_cmp(a, b) < 0) {
		bigint_trim(&ret);
		res = 1;
		goto out;
	}
	na = bigint_bits(a);
	nb = bigint_bits(b);
	if (!bigint_init(&tmp, a->offset))
		goto errout;

	if (!bigint_lsh(&tmp, b, na - nb))
		goto errout;

	for (i = na - nb; i >= 0; i--) {
		if (bigint_cmp(&ret, &tmp) >= 0) {
			if (!bigint_sub(&ret, &ret, &tmp))
				goto errout;
		}
		if (!bigint_rsh(&tmp, &tmp, 1))
			goto errout;
	}
	res = 1;
      out:
	if (!bigint_cpy(r, &ret))
		res = 0;
	else
		bigint_trim(r);
	if (IS_NEGATIVE(r))
		res = bigint_fix(r, b);
      errout:
	bigint_clean(&tmp);
	bigint_clean(&ret);
	return res;
}

int
bigint_setbit(struct bigint_t *a, unsigned offset)
{
#ifdef BIGINT_DEBUG
	if (!bigint_check(a))
		return 0;
#endif
	if ((offset / (8 * sizeof (unsigned int))) >= a->offset)
		return 0;

	a->data[offset / (8 * sizeof (unsigned int))] |=
	    1 << (offset % (8 * sizeof (unsigned int)));
	return 1;
}

int
bigint_clearbit(struct bigint_t *a, unsigned offset)
{
#ifdef BIGINT_DEBUG
	if (!bigint_check(a))
		return 0;
#endif
	if ((offset / (8 * sizeof (unsigned int))) >= a->offset)
		return 0;

	a->data[offset / (8 * sizeof (unsigned int))] &=
	    ~(1 << (offset % (8 * sizeof (unsigned int))));
	return 1;
}

/* cut from bit (not include) at offset */
int
bigint_trunc(struct bigint_t *a, unsigned int offset)
{
	unsigned int na;
	unsigned int nb;
	int i;

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

	na = offset / (8 * sizeof (unsigned int));
	nb = offset % (8 * sizeof (unsigned int));
	if (na >= a->offset)
		return 1;
	a->data[na] &= (0xFFFFFFFF) << nb;
	for (i = na - 1; i >= 0; i--)
		a->data[i] = 0;
	return 1;
}

/* cut to (included) bit at offset */
int
bigint_chop(struct bigint_t *a, unsigned offset)
{
	unsigned int na;
	unsigned int nb;
	unsigned int i;

#ifdef BIGINT_DEBUG
	if (!bigint_check(a))
		return 0;
#endif
	na = offset / (8 * sizeof (unsigned int));
	nb = offset % (8 * sizeof (unsigned int));
	if (na >= a->offset)
		return 1;
	if (nb)
		a->data[na] &= 0xFFFFFFFF >> (8 * sizeof (unsigned int) - nb);
	else
		a->data[na] = 0x00;
	for (i = a->offset - 1; i > na; i--)
		a->data[i] = 0;
	bigint_trim(a);
	return 1;
}

int
bigint_div(struct bigint_t *r,
	   const struct bigint_t *a, const struct bigint_t *b)
{
	unsigned int na;
	unsigned int nb;
	int i;
	struct bigint_t tmp;
	struct bigint_t ret;
	struct bigint_t ta;
	int res;

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

	res = 0;

	if (IS_ZERO(b))
		return 0;

	if (IS_ONE(b))
		return bigint_cpy(r, a);

	if (!bigint_init(&ret, 0))
		return 0;

	if (IS_NEGATIVE(a) || IS_NEGATIVE(b))
		SET_NEGATIVE(&ret);

	if (bigint_cmp(a, b) < 0) {
		SET_ZERO(&ret);
		res = 1;
		goto out;;
	}

	na = bigint_bits(a);
	nb = bigint_bits(b);
	if (!bigint_extend(&ret, a->offset - b->offset + 1))
		goto out;

	ret.offset = a->offset - b->offset + 1;

	if (!bigint_init(&tmp, a->offset))
		goto errout;

	if (!bigint_lsh(&tmp, b, na - nb))
		goto errout;

	if (!bigint_init(&ta, 0))
		goto errout;

	if (!bigint_cpy(&ta, a))
		goto errout;

	for (i = na - nb; i >= 0; i--) {
		if (bigint_cmp(&ta, &tmp) >= 0) {
			bigint_setbit(&ret, i);
			if (!bigint_sub(&ta, &ta, &tmp))
				goto errout;
		}
		if (!bigint_rsh(&tmp, &tmp, 1))
			goto errout;
	}
	res = 1;
      out:
	if (!bigint_cpy(r, &ret))
		res = 0;
	else
		bigint_trim(r);
	if (IS_NEGATIVE(a) || IS_NEGATIVE(b))
		SET_NEGATIVE(r);
      errout:
	bigint_clean(&tmp);
	bigint_clean(&ret);
	bigint_clean(&ta);
	return res;
}

int
bigint_init_uint(struct bigint_t *r, unsigned int n)
{
	if (!bigint_init(r, 1))
		return 0;

	r->data[0] = n;
	r->offset = 1;
	bigint_trim(r);
	return 1;
}

struct bigint_t *
bigint_new_uint(const unsigned int n)
{
	struct bigint_t *r;

	if ((r = bigint_new(1)) == NULL)
		return NULL;
	r->data[0] = n;
	r->offset = 1;
	bigint_trim(r);
	return r;
}

int
bigint_init_bin(struct bigint_t *r, const unsigned char *n, unsigned int len)
{
	unsigned int nw;
	unsigned int nr;
	unsigned int i;

	nw = len / 4;
	nr = len % 4;
	if (!bigint_init(r, nw + ((nr) ? 1 : 0)))
		return 0;

	for (i = 0; i < nw; i++)
		r->data[i] = (unsigned int) n[len - i * 4 - 1] |
		    (unsigned int) n[len - i * 4 - 2] << 8 |
		    (unsigned int) n[len - i * 4 - 3] << 16 |
		    (unsigned int) n[len - i * 4 - 4] << 24;
	switch (nr) {
	case 1:
		r->data[i] = (unsigned int) n[0];
		break;
	case 2:
		r->data[i] = (unsigned int) n[1] | (unsigned int) n[0] << 8;
		break;
	case 3:
		r->data[i] = (unsigned int) n[2] |
		    (unsigned int) n[1] << 8 | (unsigned int) n[0] << 16;
		break;
	}
	r->offset = nw + ((nr) ? 1 : 0);
	bigint_trim(r);
	return 1;
}

struct bigint_t *
bigint_new_bin(const unsigned char *n, unsigned int len)
{
	struct bigint_t *r;
	unsigned int nw;
	unsigned int nr;
	unsigned int i;

	nw = len / 4;
	nr = len % 4;
	if ((r = bigint_new(nw + ((nr) ? 1 : 0))) == NULL)
		return NULL;
	for (i = 0; i < nw; i++)
		r->data[i] = (unsigned int) n[len - i * 4 - 1] |
		    (unsigned int) n[len - i * 4 - 2] << 8 |
		    (unsigned int) n[len - i * 4 - 3] << 16 |
		    (unsigned int) n[len - i * 4 - 4] << 24;
	switch (nr) {
	case 1:
		r->data[i] = (unsigned int) n[0];
		break;
	case 2:
		r->data[i] = (unsigned int) n[1] | (unsigned int) n[0] << 8;
		break;
	case 3:
		r->data[i] = (unsigned int) n[2] |
		    (unsigned int) n[1] << 8 | (unsigned int) n[0] << 16;
		break;
	}
	r->offset = nw + ((nr) ? 1 : 0);
	bigint_trim(r);
	return r;
}

int
bigint_binlen(const struct bigint_t *n)
{
	unsigned int len;

	len = bigint_bytes(n);
	return (!len) ? 1 : len;
}

int
bigint_tobin(const struct bigint_t *n, char *bin)
{
	unsigned int base;
	int i;
	unsigned int nr;

	if (IS_ZERO(n)) {
		bin[0] = 0x00;
		return 1;
	}
	nr = bigint_bytes(n) % 4;
	base = 0;
	switch (nr) {
	case 0:
		bin[base++] =
		    (unsigned char) ((n->data[n->offset - 1] & 0xFF000000) >>
				     24);
		bin[base++] =
		    (unsigned char) ((n->data[n->offset - 1] & 0x00FF0000) >>
				     16);
		bin[base++] =
		    (unsigned char) ((n->data[n->offset - 1] & 0x0000FF00) >>
				     8);
		bin[base++] =
		    (unsigned char) (n->data[n->offset - 1] & 0x000000FF);
		break;
	case 3:
		bin[base++] =
		    (unsigned char) ((n->data[n->offset - 1] & 0x00FF0000) >>
				     16);
		bin[base++] =
		    (unsigned char) ((n->data[n->offset - 1] & 0x0000FF00) >>
				     8);
		bin[base++] =
		    (unsigned char) (n->data[n->offset - 1] & 0x000000FF);
		break;
	case 2:
		bin[base++] =
		    (unsigned char) ((n->data[n->offset - 1] & 0x0000FF00) >>
				     8);
		bin[base++] =
		    (unsigned char) (n->data[n->offset - 1] & 0x000000FF);
		break;
	case 1:
		bin[base++] =
		    (unsigned char) (n->data[n->offset - 1] & 0x000000FF);
		break;
	}
	for (i = n->offset - 2; i >= 0; i--) {
		bin[base++] = (unsigned char) ((n->data[i] & 0xFF000000) >> 24);
		bin[base++] = (unsigned char) ((n->data[i] & 0x00FF0000) >> 16);
		bin[base++] = (unsigned char) ((n->data[i] & 0x0000FF00) >> 8);
		bin[base++] = (unsigned char) (n->data[i] & 0x000000FF);
	}
	return 1;
}

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

	if (!bigint_add(r, a, b))
		return 0;
	if (!bigint_mod(r, r, m))
		return 0;
	return 1;
}

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

	if (!bigint_sub(r, a, b))
		return 0;
	if (!bigint_fix(r, m))
		return 0;
	if (!bigint_mod(r, r, m))
		return 0;
	return 1;
}

int
bigint_mod_mul(struct bigint_t *r,
	       const struct bigint_t *a,
	       const struct bigint_t *b, const struct bigint_t *m)
{
#ifdef BIGINT_DEBUG
	if ((!bigint_check(r)) ||
	    (!bigint_check(a)) || (!bigint_check(b)) || (!bigint_check(m)))
		return 0;
#endif
	if (!bigint_mul(r, a, b))
		return 0;
	if (!bigint_mod(r, r, m))
		return 0;
	return 1;
}

int
calculate_seed(int index, struct bigint_t *buffer, const struct bigint_t *m)
{
	int i;
	int j;
	int found;

	if (IS_VALID(&buffer[index]))
		return 1;

	if (!bigint_init(&buffer[index], 0))
		return 0;

	found = 0;
	for (i = index - 1; i >= 0; i--) {
		if (IS_VALID(&buffer[i])) {
			found = 1;
			break;
		}
	}

	if (found) {
		if (!bigint_cpy(&buffer[index], &buffer[i])) {
			bigint_clean(&buffer[index]);
			return 0;
		}
		for (j = 0; j < (index - i); j++) {
			if (!bigint_mod_mul
			    (&buffer[index], &buffer[index], &buffer[0], m)) {
				bigint_clean(&buffer[index]);
				return 0;
			}
		}
	} else
		return 0;
	return 1;
}

int
bigint_mod_exp(struct bigint_t *r,
	       const struct bigint_t *a,
	       const struct bigint_t *b, const struct bigint_t *m)
{
	int i;
	int j;
	unsigned char window;
	struct bigint_t buffer[BIGINT_TABLE_SIZE];
	struct bigint_t tmp;
	struct bigint_t ret;