/*
* Copyright (C) 2017 - This file is part of libecc project
*
* Authors:
* Ryad BENADJILA <ryadbenadjila@gmail.com>
* Arnaud EBALARD <arnaud.ebalard@ssi.gouv.fr>
* Jean-Pierre FLORI <jean-pierre.flori@ssi.gouv.fr>
*
* Contributors:
* Nicolas VIVET <nicolas.vivet@ssi.gouv.fr>
* Karim KHALFALLAH <karim.khalfallah@ssi.gouv.fr>
*
* 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] >> bidx) & 0x1);
err:
return ret;
}