| // 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++; | |
| } | |
| } |