lib/libmpa/mpa_shift.c

// SPDX-License-Identifier: BSD-2-Clause
/*
 * Copyright (c) 2014, STMicroelectronics International N.V.
 */
#include "mpa.h"

/*************************************************************
 *
 *   HELPER FUNCTIONS
 *
 *************************************************************/

/*------------------------------------------------------------
 *
 *  __mpa_shift_words_left
 *
 */
void __mpa_shift_words_left(mpanum op, mpa_word_t q)
{
	mpa_word_t i;

	if (q == 0 || __mpanum_is_zero(op))
		return;
	for (i = __mpanum_size(op) + q - 1; i > q - 1; i--)
		op->d[i] = op->d[i - q];

	mpa_memset(op->d, 0, BYTES_PER_WORD * q);

	/* update the size of op */
	if (op->size > 0)
		op->size += q;
	else
		op->size -= q;
}

/*------------------------------------------------------------
 *
 *  __mpa_shift_words_right
 *
 */
void __mpa_shift_words_right(mpanum op, mpa_word_t q)
{
	mpa_word_t i;

	if (q == 0 || __mpanum_is_zero(op))
		return;

	if (q >= __mpanum_size(op)) {
		mpa_set_word(op, 0);
		return;
	}

	for (i = 0; i < __mpanum_size(op) - q; i++)
		op->d[i] = op->d[i + q];

	/* update the size of dest */
	if (op->size > 0)
		op->size -= q;
	else
		op->size += q;
}

/*************************************************************
 *
 *   LIB FUNCTIONS
 *
 *************************************************************/

/*  --------------------------------------------------------------------
 *  mpa_shift_left
 *
 *  Shifts src left by "steps" step and put result in dest.
 *  It does not care about signs. Dest will have same sign as src.
 */
void mpa_shift_left(mpanum dest, mpanum src, mpa_word_t steps)
{
	mpa_word_t q;		/* quotient of steps div WORD_SIZE */
	mpa_word_t r;		/* remainder of steps div WORD_SIZE */
	mpa_word_t i;
	/* the bits of the word which will be shifted into another word */
	mpa_word_t rbits;
	mpa_word_t need_extra_word;

	/*
	 *  Copy first, then check, since even a shifted zero should
	 *  be copied.
	 */
	mpa_copy(dest, src);
	__mpa_set_unused_digits_to_zero(dest);
	if (steps == 0 || __mpanum_is_zero(dest))
		return;

	r = steps & (WORD_SIZE - 1);	/* 0 <= r < WORD_SIZE */
	q = steps >> LOG_OF_WORD_SIZE;	/* 0 <= q */

	/*
	 *  The size of dest will always increase by at least q.
	 *  If we're shifting r bits and the r highest bits in
	 *  the MSW of dest is zero, we don't need the extra word
	 *  Note:
	 *  We cannot do
	 *  if (_mpanumMSW(dest) >> (WORD_SIZE - r))
	 *  since some compilers (MS) does not shift the word
	 *  if the shift quantity is larger or equal to the word size...
	 *  Otherwise it would be natural to say that (a >> b) is just zero
	 *  if b is larger than the number of bit of a, but no no...
	 */
	need_extra_word = 0;

	if (r == 0) {		/* and q > 0 */
		/*
		 *  We have a simple shift by words
		 */
		for (i = __mpanum_size(dest) + q - 1; i > q - 1; i--)
			dest->d[i] = dest->d[i - q];
	} else {
		if (__mpanum_msw(dest) &
		    (((((mpa_word_t)1 << r) - 1u)) << (WORD_SIZE - r)))
			need_extra_word = 1;
		/*
		 * We have a combination of word and bit shifting.
		 *
		 * If need_extra_word is 1, the MSW is special and handled
		 * here
		 */
		i = __mpanum_size(dest) + q + need_extra_word;
		if (need_extra_word) {
			rbits = dest->d[i - q - 1] >> (WORD_SIZE - r);
			dest->d[i] ^= rbits;
		}
		i--;
		dest->d[i] = dest->d[i - q] << r;
		while (i > q) {
			rbits = dest->d[i - q - 1] >> (WORD_SIZE - r);
			dest->d[i] ^= rbits;
			i--;
			dest->d[i] = dest->d[i - q] << r;
		}
	}
	mpa_memset(dest->d, 0, BYTES_PER_WORD * q);
	/* update the size of dest */
	if (dest->size > 0)
		dest->size += q + need_extra_word;
	else
		dest->size -= q + need_extra_word;
}

/*------------------------------------------------------------
 *
 *  mpa_shift_right
 *
 *  Shifts src right by "steps" step and put result in dest.
 *  It does not care about signs. Dest will have same sign as src.
 *
 */
void mpa_shift_right(mpanum dest, mpanum src, mpa_word_t steps)
{
	mpa_word_t q;		/* quotient of steps div WORD_SIZE */
	mpa_word_t r;		/* remainder of steps div WORD_SIZE */
	mpa_word_t i;
	/* the bits of the word which will be shifted into another word */
	mpa_word_t rbits;

	/*
	 *  Copy first, then check, since even a shifted zero should
	 *  be copied.
	 */
	mpa_copy(dest, src);
	__mpa_set_unused_digits_to_zero(dest);
	if (steps == 0 || __mpanum_is_zero(dest))
		return;

	r = steps & (WORD_SIZE - 1);	/* 0 <= r < WORD_SIZE */
	q = steps >> LOG_OF_WORD_SIZE;	/* 0 <= q */

	if (q >= __mpanum_size(dest)) {
		mpa_set_word(dest, 0);
		return;
	}

	/*
	 *  Here we have:
	 *      0 <= r < WORD_SIZE - 1
	 *      0 <= q < _mpanumSize(dest)
	 */
	if (r == 0) {		/* and q > 0 */
		/* Simple shift by words */
		for (i = 0; i < __mpanum_size(dest) - q; i++)
			dest->d[i] = dest->d[i + q];
	} else {
		/* combination of word and bit shifting */
		for (i = 0; i < __mpanum_size(dest) - q - 1; i++) {
			dest->d[i] = dest->d[i + q];
			rbits = dest->d[i + q + 1] & ((1UL << r) - 1);
			dest->d[i] =
			    (dest->d[i] >> r) ^ (rbits << (WORD_SIZE - r));
		}
		/* final word is special */
		dest->d[i] = dest->d[i + q] >> r;
	}

	/* update the size of dest */
	if (dest->size > 0)
		dest->size -= q;
	else
		dest->size += q;

	/* Take care of the case when we shifted out all bits from MSW */
	if (__mpanum_msw(dest) == 0) {
		if (dest->size > 0)
			dest->size--;
		else
			dest->size++;
	}
}