nn_logical.c

/*
 *  Copyright (C) 2017 - This file is part of libecc project
 *
 *  Authors:
 *      Ryad BENADJILA <[email protected]>
 *      Arnaud EBALARD <[email protected]>
 *      Jean-Pierre FLORI <[email protected]>
 *
 *  Contributors:
 *      Nicolas VIVET <[email protected]>
 *      Karim KHALFALLAH <[email protected]>
 *
 *  This software is licensed under a dual BSD and GPL v2 license.
 *  See LICENSE file at the root folder of the project.
 */
#include <libecc/nn/nn_logical.h>
#include <libecc/nn/nn.h>

/*
 * nn_lshift_fixedlen: left logical shift in N, i.e. compute out = (in << cnt).
 *
 * Aliasing is possible for 'in' and 'out', i.e. x <<= cnt can be computed
 * using nn_lshift_fixedlen(x, x, cnt).
 *
 * The function supports 'in' and 'out' parameters of differents sizes.
 *
 * The operation time of the function depends on the size of 'in' and
 * 'out' parameters and the value of 'cnt'. It does not depend on the
 * value of 'in'.
 *
 * It is to be noted that the function uses out->wlen as the
 * upper limit for its work, i.e. bits shifted above out->wlen
 * are lost (the NN size of the output is not modified).
 *
 * The function returns 0 on sucess, -1 on error.
 *
 * Aliasing supported.
 */
int nn_lshift_fixedlen(nn_t out, nn_src_t in, bitcnt_t cnt)
{
	int ipos, opos, dec, ret;
	bitcnt_t lshift, hshift;
	u8 owlen, iwlen;

	ret = nn_check_initialized(in); EG(ret, err);
	ret = nn_check_initialized(out); EG(ret, err);
	owlen = out->wlen;
	iwlen = in->wlen;

	dec = cnt / WORD_BITS;
	hshift = cnt % WORD_BITS;
	lshift = (bitcnt_t)(WORD_BITS - hshift);

	for (opos = owlen - 1; opos >= 0; opos--) {
		word_t hipart = 0, lopart = 0;

		ipos = opos - dec - 1;
		if ((ipos >= 0) && (ipos < iwlen)) {
			lopart = WRSHIFT(in->val[ipos], lshift);
		}

		ipos = opos - dec;
		if ((ipos >= 0) && (ipos < iwlen)) {
			hipart = WLSHIFT(in->val[ipos], hshift);
		}

		out->val[opos] = hipart | lopart;
	}

err:
	return ret;
}

/*
 * nn_lshift: left logical shift in N, i.e. compute out = (in << cnt).
 *
 * Aliasing is possible for 'in' and 'out', i.e. x <<= cnt can be computed
 * using nn_lshift(x, x, cnt).
 *
 * The function supports 'in' and 'out' parameters of differents sizes.
 *
 * The operation time of the function depends on the size of 'in' and
 * 'out' parameters and the value of 'cnt'. It does not depend on the
 * value of 'in'.
 *
 * It is to be noted that the function computes the output bit length
 * depending on the shift count and the input length, i.e. out bit length
 * will be roughly in bit length  plus cnt, maxed to NN_MAX_BIT_LEN.
 *
 * The function returns 0 on success, -1 on error.
 *
 * Aliasing supported.
 */
int nn_lshift(nn_t out, nn_src_t in, bitcnt_t cnt)
{
	bitcnt_t lshift, hshift, blen;
	int ipos, opos, dec, ret;
	u8 owlen, iwlen;

	ret = nn_check_initialized(in); EG(ret, err);
	iwlen = in->wlen;

	/* Initialize output if no aliasing is used */
	if (out != in) {
		ret = nn_init(out, 0); EG(ret, err);
	}

	/* Adapt output length accordingly */
	ret = nn_bitlen(in, &blen); EG(ret, err);
	owlen = (u8)LOCAL_MIN(BIT_LEN_WORDS(cnt + blen),
			BIT_LEN_WORDS(NN_MAX_BIT_LEN));
	out->wlen = owlen;

	dec = cnt / WORD_BITS;
	hshift = cnt % WORD_BITS;
	lshift = (bitcnt_t)(WORD_BITS - hshift);

	for (opos = owlen - 1; opos >= 0; opos--) {
		word_t hipart = 0, lopart = 0;

		ipos = opos - dec - 1;
		if ((ipos >= 0) && (ipos < iwlen)) {
			lopart = WRSHIFT(in->val[ipos], lshift);
		}

		ipos = opos - dec;
		if ((ipos >= 0) && (ipos < iwlen)) {
			hipart = WLSHIFT(in->val[ipos], hshift);
		}

		out->val[opos] = hipart | lopart;
	}

err:
	return ret;
}

/*
 * nn_rshift_fixedlen: right logical shift in N, i.e. compute out = (in >> cnt).
 *
 * Aliasing is possible for 'in' and 'out', i.e. x >>= cnt can be computed
 * using nn_rshift_fixedlen(x, x, cnt).
 *
 * The function supports 'in' and 'out' parameters of differents sizes.
 *
 * The operation time of the function depends on the size of 'in' and
 * 'out' parameters and the value of 'cnt'. It does not depend on the
 * value of 'in'.
 * It is to be noted that the function uses out->wlen as the
 * upper limit for its work, which means zeroes are shifted in while
 * keeping the same NN output size.
 *
 * The function returns 0 on success, -1 on error.
 *
 * Aliasing supported.
 */
int nn_rshift_fixedlen(nn_t out, nn_src_t in, bitcnt_t cnt)
{
	int ipos, opos, dec, ret;
	bitcnt_t lshift, hshift;
	u8 owlen, iwlen;

	ret = nn_check_initialized(in); EG(ret, err);
	ret = nn_check_initialized(out); EG(ret, err);
	owlen = out->wlen;
	iwlen = in->wlen;

	dec = cnt / WORD_BITS;
	lshift = cnt % WORD_BITS;
	hshift = (bitcnt_t)(WORD_BITS - lshift);

	for (opos = 0; opos < owlen; opos++) {
		word_t hipart = 0, lopart = 0;

		ipos = opos + dec;
		if ((ipos >= 0) && (ipos < iwlen)) {
			lopart = WRSHIFT(in->val[ipos], lshift);
		}

		ipos = opos + dec + 1;
		if ((ipos >= 0) && (ipos < iwlen)) {
			hipart = WLSHIFT(in->val[ipos], hshift);
		}

		out->val[opos] = hipart | lopart;
	}

err:
	return ret;
}

/*
 * nn_rshift: right logical shift in N, i.e. compute out = (in >> cnt).
 *
 * Aliasing is possible for 'in' and 'out', i.e. x >>= cnt can be computed
 * using nn_rshift_fixedlen(x, x, cnt).
 *
 * The function supports 'in' and 'out' parameters of differents sizes.
 *
 * The operation time of the function depends on the size of 'in' and
 * 'out' parameters and the value of 'cnt'. It does not depend on the
 * value of 'in'.
 * It is to be noted that the function adapts the output size to
 * the input size and the shift bit count, i.e. out bit lenth is roughly
 * equal to input bit length minus cnt.
 *
 * The function returns 0 on success, -1 on error.
 *
 * Aliasing supported.
 */
int nn_rshift(nn_t out, nn_src_t in, bitcnt_t cnt)
{
	int ipos, opos, dec, ret;
	bitcnt_t lshift, hshift;
	u8 owlen, iwlen;
	bitcnt_t blen;

	ret = nn_check_initialized(in); EG(ret, err);
	iwlen = in->wlen;
	/* Initialize output if no aliasing is used */
	if (out != in) {
		ret = nn_init(out, 0); EG(ret, err);
	}

	dec = cnt / WORD_BITS;
	lshift = cnt % WORD_BITS;
	hshift = (bitcnt_t)(WORD_BITS - lshift);

	/* Adapt output length accordingly */
	ret = nn_bitlen(in, &blen); EG(ret, err);
	if (cnt > blen) {
		owlen = 0;
	} else {
		owlen = (u8)BIT_LEN_WORDS(blen - cnt);
	}
	/* Adapt output length in out */
	out->wlen = owlen;

	for (opos = 0; opos < owlen; opos++) {
		word_t hipart = 0, lopart = 0;

		ipos = opos + dec;
		if ((ipos >= 0) && (ipos < iwlen)) {
			lopart = WRSHIFT(in->val[ipos], lshift);
		}

		ipos = opos + dec + 1;
		if ((ipos >= 0) && (ipos < iwlen)) {
			hipart = WLSHIFT(in->val[ipos], hshift);
		}

		out->val[opos] = hipart | lopart;
	}

	/*
	 * Zero the output upper part now that we don't need it anymore
	 * NB: as we cannot use our normalize helper here (since a consistency
	 * check is done on wlen and upper part), we have to do this manually
	 */
	for (opos = owlen; opos < NN_MAX_WORD_LEN; opos++) {
		out->val[opos] = 0;
	}

err:
	return ret;
}

/*
 * This function right rotates the input NN value by the value 'cnt' on the
 * bitlen basis. The function does it in the following way; right rotation
 * of x by cnt is "simply": (x >> cnt) ^ (x << (bitlen - cnt))
 *
 * The function returns 0 on success, -1 on error.
 *
 * Aliasing supported.
 */
int nn_rrot(nn_t out, nn_src_t in, bitcnt_t cnt, bitcnt_t bitlen)
{
	u8 owlen = (u8)BIT_LEN_WORDS(bitlen);
	int ret;
	nn tmp;
	tmp.magic = WORD(0);

	MUST_HAVE((bitlen <= NN_MAX_BIT_LEN), ret, err);
	MUST_HAVE((cnt < bitlen), ret, err);

	ret = nn_check_initialized(in); EG(ret, err);
	ret = nn_init(&tmp, 0); EG(ret, err);
	ret = nn_lshift(&tmp, in, (bitcnt_t)(bitlen - cnt)); EG(ret, err);
	ret = nn_set_wlen(&tmp, owlen); EG(ret, err);
	ret = nn_rshift(out, in, cnt); EG(ret, err);
	ret = nn_set_wlen(out, owlen); EG(ret, err);
	ret = nn_xor(out, out, &tmp); EG(ret, err);

	/* Mask the last word if necessary */
	if (((bitlen % WORD_BITS) != 0) && (out->wlen > 0)) {
		/* shift operation below is ok (less than WORD_BITS) */
		word_t mask = (word_t)(((word_t)(WORD(1) << (bitlen % WORD_BITS))) - 1);
		out->val[out->wlen - 1] &= mask;
	}

err:
	nn_uninit(&tmp);

	return ret;
}

/*
 * This function left rotates the input NN value by the value 'cnt' on the
 * bitlen basis. The function does it in the following way; Left rotation
 * of x by cnt is "simply": (x << cnt) ^ (x >> (bitlen - cnt))
 *
 * The function returns 0 on success, -1 on error.
 *
 * Aliasing supported.
 */
int nn_lrot(nn_t out, nn_src_t in, bitcnt_t cnt, bitcnt_t bitlen)
{
	u8 owlen = (u8)BIT_LEN_WORDS(bitlen);
	int ret;
	nn tmp;
	tmp.magic = WORD(0);

	MUST_HAVE(!(bitlen > NN_MAX_BIT_LEN), ret, err);
	MUST_HAVE(!(cnt >= bitlen), ret, err);

	ret = nn_check_initialized(in); EG(ret, err);
	ret = nn_init(&tmp, 0); EG(ret, err);
	ret = nn_lshift(&tmp, in, cnt); EG(ret, err);
	ret = nn_set_wlen(&tmp, owlen); EG(ret, err);
	ret = nn_rshift(out, in, (bitcnt_t)(bitlen - cnt)); EG(ret, err);
	ret = nn_set_wlen(out, owlen); EG(ret, err);
	ret = nn_xor(out, out, &tmp); EG(ret, err);

	/* Mask the last word if necessary */
	if (((bitlen % WORD_BITS) != 0) && (out->wlen > 0)) {
		word_t mask = (word_t)(((word_t)(WORD(1) << (bitlen % WORD_BITS))) - 1);
		out->val[out->wlen - 1] &= mask;
	}

err:
	nn_uninit(&tmp);

	return ret;
}

/*
 * Compute XOR between B and C and put the result in A. B and C must be
 * initialized. Aliasing is supported, i.e. A can be one of the parameter B or
 * C. If aliasing is not used, A will be initialized by the function. Function
 * execution time depends on the word length of larger parameter but not on its
 * particular value.
 *
 * The function returns 0 on success, -1 on error.
 *
 * Aliasing supported.
 */
int nn_xor(nn_t A, nn_src_t B, nn_src_t C)
{
	int ret;
	u8 i;

	ret = nn_check_initialized(B); EG(ret, err);
	ret = nn_check_initialized(C); EG(ret, err);

	/* Initialize the output if no aliasing is used */
	if ((A != B) && (A != C)) {
		ret = nn_init(A, 0);  EG(ret, err);
	}

	/* Set output wlen accordingly */
	A->wlen = (C->wlen < B->wlen) ? B->wlen : C->wlen;

	for (i = 0; i < A->wlen; i++) {
		A->val[i] = (B->val[i] ^ C->val[i]);
	}

err:
	return ret;
}

/*
 * Compute logical OR between B and C and put the result in A. B and C must be
 * initialized. Aliasing is supported, i.e. A can be one of the parameter B or
 * C. If aliasing is not used, A will be initialized by the function. Function
 * execution time depends on the word length of larger parameter but not on its
 * particular value.
 *
 * The function returns 0 on success, -1 on error.
 *
 * Aliasing supported.
 */
int nn_or(nn_t A, nn_src_t B, nn_src_t C)
{
	int ret;
	u8 i;

	ret = nn_check_initialized(B); EG(ret, err);
	ret = nn_check_initialized(C); EG(ret, err);

	/* Initialize the output if no aliasing is used */
	if ((A != B) && (A != C)) {
		ret = nn_init(A, 0); EG(ret, err);
	}

	/* Set output wlen accordingly */
	A->wlen = (C->wlen < B->wlen) ? B->wlen : C->wlen;

	for (i = 0; i < A->wlen; i++) {
		A->val[i] = (B->val[i] | C->val[i]);
	}

err:
	return ret;
}

/*
 * Compute logical AND between B and C and put the result in A. B and C must be
 * initialized. Aliasing is supported, i.e. A can be one of the parameter B or
 * C. If aliasing is not used, A will be initialized by the function. Function
 * execution time depends on the word length of larger parameter but not on its
 * particular value.
 *
 * The function returns 0 on success, -1 on error.
 *
 * Aliasing supported.
 */
int nn_and(nn_t A, nn_src_t B, nn_src_t C)
{
	int ret;
	u8 i;

	ret = nn_check_initialized(B); EG(ret, err);
	ret = nn_check_initialized(C); EG(ret, err);

	/* Initialize the output if no aliasing is used */
	if ((A != B) && (A != C)) {
		ret = nn_init(A, 0); EG(ret, err);
	}

	/* Set output wlen accordingly */
	A->wlen = (C->wlen < B->wlen) ? B->wlen : C->wlen;

	for (i = 0; i < A->wlen; i++) {
		A->val[i] = (B->val[i] & C->val[i]);
	}

err:
	return ret;
}

/*
 * Compute logical NOT of B and put the result in A. B must be initialized.
 * Aliasing is supported. If aliasing is not used, A will be initialized by
 * the function.
 *
 * The function returns 0 on success, -1 on error.
 *
 * Aliasing supported.
 */
int nn_not(nn_t A, nn_src_t B)
{
	int ret;
	u8 i;

	ret = nn_check_initialized(B); EG(ret, err);

	/* Initialize the output if no aliasing is used */
	if (A != B) {
		ret = nn_init(A, 0); EG(ret, err);
	}

	/* Set output wlen accordingly */
	A->wlen = B->wlen;

	for (i = 0; i < A->wlen; i++) {
		A->val[i] = (word_t)(~(B->val[i]));
	}

err:
	return ret;
}

/* Count leading zeros of a word. This is constant time */
ATTRIBUTE_WARN_UNUSED_RET static u8 wclz(word_t A)
{
	u8 cnt = WORD_BITS, over = 0;
	int i;

	for (i = (WORD_BITS - 1); i >= 0; i--) {
		/* i is less than WORD_BITS so shift operations below are ok */
		u8 mask = (u8)(((A & (WORD(1) << i)) >> i) & 0x1);
		over |= mask;
		cnt = (u8)(cnt - over);
	}

	return cnt;
}

/*
 * Count leading zeros of an initialized nn. This is NOT constant time. The
 * function returns 0 on success, -1 on error. On success, the number of
 * leading zeroes is available in 'lz'. 'lz' is not meaningful on error.
 */
int nn_clz(nn_src_t in, bitcnt_t *lz)
{
	bitcnt_t cnt = 0;
	int ret;
	u8 i;

	/* Sanity check */
	MUST_HAVE((lz != NULL), ret, err);
	ret = nn_check_initialized(in); EG(ret, err);

	for (i = in->wlen; i > 0; i--) {
		if (in->val[i - 1] == 0) {
			cnt = (bitcnt_t)(cnt +  WORD_BITS);
		} else {
			cnt = (bitcnt_t)(cnt + wclz(in->val[i - 1]));
			break;
		}
	}
	*lz = cnt;

err:
	return ret;
}

/*
 * Compute bit length of given nn. This is NOT constant-time.  The
 * function returns 0 on success, -1 on error. On success, the bit length
 * of 'in' is available in 'blen'. 'blen' is not meaningful on error.
 */
int nn_bitlen(nn_src_t in, bitcnt_t *blen)
{
	bitcnt_t _blen = 0;
	int ret;
	u8 i;

	/* Sanity check */
	MUST_HAVE((blen != NULL), ret, err);
	ret = nn_check_initialized(in); EG(ret, err);

	for (i = in->wlen; i > 0; i--) {
		if (in->val[i - 1] != 0) {
			_blen = (bitcnt_t)((i * WORD_BITS) - wclz(in->val[i - 1]));
			break;
		}
	}
	(*blen) = _blen;

err:
	return ret;
}

/*
 * On success (return value is 0), the function provides via 'bitval' the value
 * of the bit at position 'bit' in 'in' nn. 'bitval' in not meaningful error
 * (when return value is -1).
 */
int nn_getbit(nn_src_t in, bitcnt_t bit, u8 *bitval)
{
	bitcnt_t widx = bit / WORD_BITS;
	u8 bidx = bit % WORD_BITS;
	int ret;

	/* Sanity check */
	MUST_HAVE((bitval != NULL), ret, err);
	ret = nn_check_initialized(in); EG(ret, err);
	MUST_HAVE((bit < NN_MAX_BIT_LEN), ret, err);

	/* bidx is less than WORD_BITS so shift operations below are ok */
	(*bitval) = (u8)((((in->val[widx]) & (WORD(1) << bidx)) >> bidx) & 0x1);

err:
	return ret;
}