| // SPDX-License-Identifier: BSD-2-Clause | |
| /* | |
| * Copyright (c) 2014, STMicroelectronics International N.V. | |
| */ | |
| #include "mpa.h" | |
| /************************************************************* | |
| * | |
| * HELPER FUNCTIONS | |
| * | |
| *************************************************************/ | |
| /*------------------------------------------------------------ | |
| * | |
| * These functions have ARM assembler implementations | |
| * | |
| */ | |
| #if !defined(USE_ARM_ASM) | |
| static mpa_dword_t __mpa_soft_div(mpa_dword_t num, mpa_word_t den_in, | |
| mpa_word_t *rem) | |
| { | |
| mpa_dword_t quot = 0, qbit = 1; | |
| mpa_dword_t den = den_in; | |
| while ((int64_t) den >= 0) { | |
| den <<= 1; | |
| qbit <<= 1; | |
| } | |
| while (qbit) { | |
| if (den <= num) { | |
| num -= den; | |
| quot += qbit; | |
| } | |
| den >>= 1; | |
| qbit >>= 1; | |
| } | |
| if (rem) | |
| *rem = (mpa_word_t) num; | |
| return quot; | |
| } | |
| /* -------------------------------------------------------------------- | |
| * Function: __mpa_div_dword | |
| * | |
| * Calculates quotient and remainder of (n1*base + n0) / d. | |
| * It is assumed that the quotient is small enough to fit a single word. | |
| */ | |
| mpa_word_t __mpa_div_dword(mpa_word_t n0, | |
| mpa_word_t n1, mpa_word_t d, mpa_word_t *r) | |
| { | |
| #if defined(MPA_SUPPORT_DWORD_T) | |
| mpa_dword_t n; | |
| /* mpa_dword_t tmp_q; */ | |
| n = ((mpa_dword_t) n1 << WORD_SIZE) + n0; | |
| return __mpa_soft_div(n, d, r); | |
| /* tmp_q = n / d; */ | |
| /* *r = (mpa_word_t)(n % d); */ | |
| /* return tmp_q; */ | |
| #else | |
| #error write non-dword code for __mpa_div_dword | |
| #endif | |
| } | |
| #endif /* USE_ARM_ASM */ | |
| /* -------------------------------------------------------------------- | |
| * Function: __mpa_div_q_r_internal | |
| * | |
| * Finds the quotient and remainder when |op1| is divided by |op2|. | |
| * q, r, op1 and op2 must all be distinct and not null. | |
| * E.i. we get q and r such that |op1| = q*|op2| + r, 0<= r < |op2|. | |
| * Assumptions: |op1| >= |op2| and |op2| >= 2^(WORD_SIZE) | |
| * | |
| */ | |
| static void __mpa_div_q_r_internal(mpanum q, | |
| mpanum r, | |
| const mpanum op1, | |
| const mpanum op2, mpa_scratch_mem pool) | |
| { | |
| mpa_word_t normshift; | |
| int base_diff; | |
| int i; | |
| int cmp_same; | |
| mpa_usize_t n; /* size of op1 */ | |
| mpa_usize_t t; /* size of op2 */ | |
| mpa_word_t w1; | |
| mpa_word_t w2; | |
| mpa_word_t w3; | |
| mpa_word_t w4; | |
| mpa_word_t w5; | |
| mpanum p; | |
| mpanum y; | |
| mpanum x; | |
| /* | |
| * get temp storage | |
| */ | |
| mpa_alloc_static_temp_var(&p, pool); | |
| mpa_alloc_static_temp_var(&y, pool); | |
| mpa_copy(y, op2); | |
| /* | |
| * May need a large value for r since op1 may be an "oversized" | |
| * value that is reduced. x is used for that internally and it's | |
| * initial value is op1. | |
| */ | |
| mpa_alloc_static_temp_var(&x, pool); | |
| mpa_copy(x, op1); | |
| __mpanum_set_sign(x, MPA_POS_SIGN); | |
| __mpanum_set_sign(y, MPA_POS_SIGN); | |
| /* | |
| * Normalization | |
| */ | |
| normshift = 0; | |
| w1 = __mpanum_msw(y); | |
| while (w1 < ((mpa_word_t)1 << (WORD_SIZE - 1))) { | |
| normshift++; | |
| w1 <<= 1; | |
| } | |
| if (normshift) { | |
| mpa_shift_left(x, x, normshift); | |
| mpa_shift_left(y, y, normshift); | |
| } | |
| n = x->size; | |
| t = y->size; | |
| base_diff = (int)n - t; | |
| mpa_wipe(q); | |
| /* | |
| * check if op1 >= op2*base^(base_diff) | |
| */ | |
| /* mpa_shift_left(y, y, base_diff * WORD_SIZE); */ | |
| __mpa_shift_words_left(y, base_diff); | |
| i = __mpanum_size(y); | |
| cmp_same = 1; | |
| while (cmp_same != 0 && i > 0) { | |
| i--; | |
| cmp_same = (__mpanum_get_word(i, x) == __mpanum_get_word(i, y)); | |
| } | |
| if (!cmp_same && (__mpanum_get_word(i, x) > __mpanum_get_word(i, y))) { | |
| q->d[base_diff] = 1; | |
| mpa_sub(x, x, y, pool); | |
| } | |
| /* start main division loop */ | |
| i = x->size - 1; | |
| while (i >= (int)t) { | |
| if (__mpanum_get_word(i, x) == | |
| __mpanum_get_word(t + base_diff - 1, y)) { | |
| q->d[i - t] = WORD_ALL_BITS_ONE; | |
| } else { | |
| q->d[i - t] = | |
| __mpa_div_dword(__mpanum_get_word(i - 1, x), | |
| __mpanum_get_word(i, x), | |
| __mpanum_get_word(t + base_diff | |
| - 1, y), | |
| NULL); | |
| } | |
| while (1) { | |
| /* set incoming carry to zero for all three ops */ | |
| w1 = 0; | |
| w3 = 0; | |
| w5 = 0; | |
| __mpa_mul_add_word(q->d[i - t], | |
| __mpanum_get_word(t + base_diff - 1, | |
| y), &w2, &w1); | |
| if (w1 > __mpanum_get_word(i, x)) | |
| goto loop_dec; | |
| __mpa_mul_add_word(q->d[i - t], | |
| __mpanum_get_word(t + base_diff - 2, | |
| y), &w4, &w3); | |
| __mpa_full_adder(w2, w3, &w3, &w5); | |
| w2 = 0; /* used as carry */ | |
| __mpa_full_adder(w1, w5, &w5, &w2); | |
| if (w2 || w5 > __mpanum_get_word(i, x)) | |
| goto loop_dec; | |
| if (w5 < __mpanum_get_word(i, x)) | |
| break; | |
| if (w3 > __mpanum_get_word(i - 1, x)) | |
| goto loop_dec; | |
| if (w3 < __mpanum_get_word(i - 1, x)) | |
| break; | |
| if (w4 > __mpanum_get_word(i - 2, x)) | |
| goto loop_dec; | |
| break; | |
| loop_dec: | |
| q->d[i - t]--; | |
| } | |
| /* mpa_shift_right(y, y, WORD_SIZE); */ | |
| __mpa_shift_words_right(y, 1); | |
| base_diff--; | |
| mpa_mul_word(p, y, q->d[i - t], pool); | |
| mpa_sub(x, x, p, pool); | |
| if (__mpanum_sign(x) == MPA_NEG_SIGN) { | |
| mpa_add(x, x, y, pool); | |
| q->d[i - t]--; | |
| } | |
| i--; | |
| } | |
| /* | |
| * Find size of q | |
| */ | |
| i = n - t; | |
| while (i >= 0 && q->d[i] == 0) | |
| i--; | |
| q->size = i + 1; | |
| /* | |
| * Divide r by the normalization value and copy to output | |
| */ | |
| mpa_shift_right(x, x, normshift); | |
| mpa_copy(r, x); | |
| /* | |
| * release p, y, and x | |
| */ | |
| mpa_free_static_temp_var(&p, pool); | |
| mpa_free_static_temp_var(&y, pool); | |
| mpa_free_static_temp_var(&x, pool); | |
| } | |
| /* -------------------------------------------------------------------- | |
| * Function: __mpa_div_q_r_internal_word | |
| * | |
| * Finds the quotient and remainder when |op1| is divided by |op2|, where | |
| * op2 is a word. | |
| * q, r and op1 must all be distinct and not null. | |
| * E.i. we get q and r such that |op1| = q*|op2| + r, 0<= r < |op2|. | |
| * Assumptions: |op1| >= |op2|. | |
| */ | |
| void __mpa_div_q_r_internal_word(mpanum q, | |
| mpanum r, | |
| const mpanum op1, const mpa_word_t op2) | |
| { | |
| int pos1; | |
| mpa_word_t q_word; | |
| mpa_word_t r_word; | |
| mpa_word_t n1; | |
| mpa_word_t n0; | |
| int i; | |
| if (__mpanum_size(op1) == 1) { | |
| mpa_set_word(q, op1->d[0] / op2); | |
| mpa_set_word(r, op1->d[0] % op2); | |
| return; | |
| } | |
| mpa_copy(r, op1); | |
| mpa_set_word(q, 0); | |
| pos1 = (int)__mpanum_size(r) - 1; | |
| n1 = 0; | |
| n0 = r->d[pos1]; | |
| while (pos1 >= 0) { | |
| q_word = __mpa_div_dword(n0, n1, op2, &r_word); | |
| q->d[pos1] = q_word; | |
| r->d[pos1] = r_word; | |
| n1 = r->d[pos1]; | |
| n0 = r->d[--pos1]; | |
| } | |
| /* set sizes of r and q */ | |
| r->size = (r->d[0] == 0 ? 0 : 1); | |
| i = __mpanum_size(op1) - 1; | |
| while (i >= 0 && q->d[i] == 0) | |
| i--; | |
| q->size = i + 1; | |
| } | |
| /* -------------------------------------------------------------------- | |
| * Function: __mpa_div_q_r | |
| * | |
| * Calculates the quotient and remainder when op1 is divided by op2. | |
| * q, r, op1 and op2 must all be distinct and not null, except that op1 | |
| * may be equal to op2. | |
| * There must be enough space allocated in q and r to handle the results. | |
| * If op2 is zero a division with zero will be executed and the above layers | |
| * can handle that as it pleases. | |
| * The sign of q and r are shown in the table: | |
| * __________________________________ | |
| * | Sign(q/r) | op1 >= 0 | op1 < 0 | | |
| * |--------------------------------| | |
| * | op2 > 0 | +/+ | -/- | | |
| * |--------------------------------| | |
| * | op2 < 0 | -/+ | +/- | | |
| * |________________________________| | |
| */ | |
| void __mpa_div_q_r(mpanum q, | |
| mpanum r, | |
| const mpanum op1, const mpanum op2, mpa_scratch_mem pool) | |
| { | |
| int q_sign; | |
| int cmp; | |
| if (__mpanum_is_zero(op1)) { | |
| mpa_set_word(q, 0); | |
| mpa_set_word(r, 0); | |
| return; | |
| } | |
| if (__mpanum_is_zero(op2)) { | |
| /* generate a divide by zero error */ | |
| q_sign = 42 / op2->size; | |
| return; | |
| } | |
| q_sign = | |
| (__mpanum_sign(op1) != | |
| __mpanum_sign(op2)) ? MPA_NEG_SIGN : MPA_POS_SIGN; | |
| cmp = __mpa_abs_cmp(op1, op2); | |
| if (cmp == 0) { | |
| mpa_set_word(q, 1); | |
| mpa_set_word(r, 0); | |
| return; | |
| } | |
| if (cmp > 0) { /* |op1| > |op2| */ | |
| if (__mpanum_size(op2) > 1) | |
| __mpa_div_q_r_internal(q, r, op1, op2, pool); | |
| else | |
| __mpa_div_q_r_internal_word(q, r, op1, op2->d[0]); | |
| } else { /* |op1| < |op2| */ | |
| mpa_set_word(q, 0); | |
| mpa_copy(r, op1); | |
| return; | |
| } | |
| __mpanum_set_sign(q, q_sign); | |
| __mpanum_set_sign(r, __mpanum_sign(op1)); | |
| } | |
| /************************************************************* | |
| * | |
| * LIB FUNCTIONS | |
| * | |
| *************************************************************/ | |
| /* -------------------------------------------------------------------- | |
| * Function: mpa_div | |
| * | |
| * Returns the quotient and the remainder of op1 divided by op2. | |
| * q and r must be distinct variables. | |
| * This function returns q and r such that | |
| * op1 = q*op2 + r | |
| * where 0 <= r < |op2| | |
| */ | |
| void mpa_div(mpanum q, | |
| mpanum r, const mpanum op1, const mpanum op2, mpa_scratch_mem pool) | |
| { | |
| mpanum tmp_q; | |
| mpanum tmp_r; | |
| char mem_marker_q; | |
| char mem_marker_r; | |
| /* handle the case when q is one of the operands or zero */ | |
| if (q == op1 || q == op2 || q == 0) { | |
| mpa_alloc_static_temp_var(&tmp_q, pool); | |
| mem_marker_q = 1; | |
| } else { | |
| tmp_q = q; | |
| mem_marker_q = 0; | |
| } | |
| /* handle the case when r is one of the operands or zero */ | |
| if (r == op1 || r == op2 || r == 0) { | |
| mpa_alloc_static_temp_var(&tmp_r, pool); | |
| mem_marker_r = 1; | |
| } else { | |
| tmp_r = r; | |
| mem_marker_r = 0; | |
| } | |
| __mpa_div_q_r(tmp_q, tmp_r, op1, op2, pool); | |
| if (q != 0) | |
| mpa_copy(q, tmp_q); | |
| if (mem_marker_q) | |
| mpa_free_static_temp_var(&tmp_q, pool); | |
| if (r != 0) | |
| mpa_copy(r, tmp_r); | |
| if (mem_marker_r) | |
| mpa_free_static_temp_var(&tmp_r, pool); | |
| } |