diff options
Diffstat (limited to 'src/bigint.c')
| -rw-r--r-- | src/bigint.c | 149 |
1 files changed, 124 insertions, 25 deletions
diff --git a/src/bigint.c b/src/bigint.c index 240dbb2..c78503d 100644 --- a/src/bigint.c +++ b/src/bigint.c @@ -67,7 +67,7 @@ static size_t bh_bigint_type_log2(BH_BIGINT_TYPE x) tmp = (x >> (BH_BIGINT_BITS - 7)) & 0xFF; if (tmp) return ((BH_BIGINT_BITS + 1) - 8 * (i + 1)) + lookup[tmp]; - + x <<= 8; } @@ -405,7 +405,7 @@ static int bh_bigint_add_base(bh_bigint_t *to, to->size = most->size + 1; else to->size = most->size; - + return BH_OK; } @@ -415,7 +415,7 @@ static int bh_bigint_sub_base(bh_bigint_t *to, { BH_BIGINT_TYPE carry, tmp; size_t size, i; - + /* Clear up result error flag */ to->error = 0; @@ -496,9 +496,14 @@ int bh_bigint_add(bh_bigint_t *to, else code = bh_bigint_sub_base(to, most, least); - /* Set result sign */ if (!code) - to->type = type; + { + /* Set result sign or zero */ + if (to->size) + to->type = type; + else + to->type = 0; + } /* Return result code */ return code; @@ -538,9 +543,14 @@ int bh_bigint_sub(bh_bigint_t *to, else code = bh_bigint_add_base(to, most, least); - /* Set result sign */ if (!code) - to->type = type; + { + /* Set result sign or zero */ + if (to->size) + to->type = type; + else + to->type = 0; + } /* Return result code */ return code; @@ -639,6 +649,73 @@ int bh_bigint_mul(bh_bigint_t *to, return BH_OK; } +int bh_bigint_mul_digit(bh_bigint_t *to, + bh_bigint_t *left, + bh_int16_t right) +{ + BH_BIGINT_TYPE carry; + BH_BIGINT_TMP tmp; + size_t i, size; + + /* Shortcut - one of the arguments has error flag set */ + if (left->error) + { + to->error = 1; + return BH_ERROR; + } + + /* Clear up result error flag */ + to->error = 0; + + /* Shortcut - multiplication by zero */ + if (left->type == 0 || right == 0) + { + to->type = 0; + to->size = 0; + return BH_OK; + } + + /* Reserve space for result */ + if (to->capacity < (left->size + 1)) + { + if (bh_bigint_reserve(to, left->size + 1)) + { + to->error = 1; + return BH_OOM; + } + } + + /* Determine sign */ + if ((left->type > 0 && right < 0) || (left->type < 0 && right > 0)) + to->type = -1; + else + to->type = 1; + + if (right < 0) + right = -right; + + /* Prepare variables */ + carry = 0; + + /* Multiplication loop */ + for (i = 0; i < left->size; i++) + { + tmp = (BH_BIGINT_TMP)left->data[i] * (BH_BIGINT_TMP)right + carry; + carry = tmp >> BH_BIGINT_BITS; + to->data[i] = tmp & BH_BIGINT_MASK; + } + to->data[i] = carry; + + /* Truncate multiplication result size */ + size = left->size + 1; + while (size && !to->data[size - 1]) size--; + + /* Update size */ + to->size = size; + + return BH_OK; +} + int bh_bigint_pow(bh_bigint_t *to, bh_bigint_t *from, bh_uint32_t power) @@ -732,7 +809,7 @@ int bh_bigint_powm(bh_bigint_t *to, code = BH_OK; /* Shortcut - one of the arguments has error flag set */ - if (left->error || right->error) + if (left->error || right->error || mod->error) { to->error = 1; return BH_ERROR; @@ -740,7 +817,7 @@ int bh_bigint_powm(bh_bigint_t *to, /* Clear up result error flag */ to->error = 0; - + /* Shortcut - power is equal to 0 */ if (bh_bigint_is_zero(right)) return bh_bigint_set_int(to, 1); @@ -752,7 +829,7 @@ int bh_bigint_powm(bh_bigint_t *to, /* Shortcut - power is negative */ if (bh_bigint_is_negative(right)) return bh_bigint_clear(to); - + /* Figure out result sign */ if (left->type < 0 && right->data[0] & 0x1) type = -1; @@ -816,7 +893,7 @@ int bh_bigint_powm(bh_bigint_t *to, bh_bigint_mul(base, base, base); bh_bigint_mod(base, base, mod); bh_bigint_rsh(exponent, exponent, 1); - + /* Stop if error occured */ if (base->error || result->error) { @@ -848,14 +925,14 @@ static BH_BIGINT_TYPE bh_bigint_div_guess(bh_bigint_t *left, bh_bigint_t *right) { BH_BIGINT_TMP tmp; - + /* Left is bigger then right */ if (bh_bigint_equal_mod(left, right) < 0) return 0; /* Make a guess */ tmp = left->data[left->size - 1]; - + if (left->size != right->size) tmp = (tmp << BH_BIGINT_BITS) + left->data[left->size - 2]; @@ -959,7 +1036,7 @@ static int bh_bigint_div_base(bh_bigint_t *quotient, } nleft->size--; } - + while (1) { /* Make a guess at what first digit of quotient should be */ @@ -993,7 +1070,8 @@ static int bh_bigint_div_base(bh_bigint_t *quotient, } /* Calculate remainder */ - bh_bigint_sub(remainder, remainder, tmp); + /* Prevent using addition logic and use subtraction */ + bh_bigint_sub_base(remainder, remainder, tmp); if (!nleft->size) break; @@ -1020,6 +1098,9 @@ finish: return code; } +/** + * This follows C99 model (a/b)*b + a%b + */ int bh_bigint_divmod(bh_bigint_t *quotient, bh_bigint_t *remainder, bh_bigint_t *left, @@ -1111,10 +1192,13 @@ int bh_bigint_divmod(bh_bigint_t *quotient, code = bh_bigint_div_base(quotient, tmp, left, right, &shift); if (!code) { + /* Remainder should use sign of the left operand */ + tmp->type = left->type; + /* If remainder required - normilize it */ if (tmp == remainder) bh_bigint_rsh(remainder, remainder, shift); - + /* Fix the sign */ if (quotient) quotient->type = type; @@ -1145,7 +1229,7 @@ int bh_bigint_lsh(bh_bigint_t *to, bh_uint32_t shift) { size_t i, bits, blocks; - BH_BIGINT_TYPE tmp; + BH_BIGINT_TYPE tmp; /* Shortcut - one of the arguments has error flag set */ if (left->error) @@ -1255,7 +1339,7 @@ int bh_bigint_rsh(bh_bigint_t *to, /* Calculate distance in blocks and bits */ blocks = shift / BH_BIGINT_BITS; bits = shift % BH_BIGINT_BITS; - + /* Shortcut - shift is bigger than value or value is 0 */ if (left->type == 0 || left->size < blocks) { @@ -1302,7 +1386,7 @@ int bh_bigint_rsh(bh_bigint_t *to, return BH_OOM; } } - + /* Main loop for aligned shift */ for (i = 0; i < left->size - blocks; i++) to->data[i] = left->data[i + blocks]; @@ -1312,7 +1396,7 @@ int bh_bigint_rsh(bh_bigint_t *to, i = left->size - blocks; while (i && !to->data[i - 1]) i--; - /* Update fields */ + /* Update fields */ to->size = i; to->type = left->type; @@ -1358,10 +1442,16 @@ int bh_bigint_or(bh_bigint_t *to, to->data[i] = tmp; } + /* Shrink size */ + while (size && !to->data[size - 1]) size--; + /* Update fields */ to->type = 1; to->size = size; + if (!size) + to->type = 0; + return BH_OK; } @@ -1401,10 +1491,16 @@ int bh_bigint_and(bh_bigint_t *to, to->data[i] = tmp; } + /* Shrink size */ + while (size && !to->data[size - 1]) size--; + /* Update fields */ to->type = 1; to->size = size; + if (!size) + to->type = 0; + return BH_OK; } @@ -1444,10 +1540,16 @@ int bh_bigint_xor(bh_bigint_t *to, to->data[i] = tmp; } + /* Shrink size */ + while (size && !to->data[size - 1]) size--; + /* Update fields */ to->type = 1; to->size = size; + if (!size) + to->type = 0; + return BH_OK; } @@ -1472,10 +1574,7 @@ int bh_bigint_negate(bh_bigint_t *to, } /* Change the sign */ - if (to->type < 0) - to->type = 1; - else if (to->type > 0) - to->type = -1; + to->type = 0 - to->type; return BH_OK; } @@ -1555,4 +1654,4 @@ size_t bh_bigint_log2(bh_bigint_t *bigint) result = bh_bigint_type_log2(bigint->data[bigint->size - 1]); return result + (bigint->size - 1) * BH_BIGINT_BITS; -}
\ No newline at end of file +} |