/* * Copyright (c) 2008-2020 Stefan Krah. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS "AS IS" AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include "mpdecimal.h" #include <assert.h> #include <stdio.h> #include "basearith.h" #include "constants.h" #include "typearith.h" /*********************************************************************/ /* Calculations in base MPD_RADIX */ /*********************************************************************/ /* * Knuth, TAOCP, Volume 2, 4.3.1: * w := sum of u (len m) and v (len n) * n > 0 and m >= n * The calling function has to handle a possible final carry. */ mpd_uint_t _mpd_baseadd(mpd_uint_t *w, const mpd_uint_t *u, const mpd_uint_t *v, mpd_size_t m, mpd_size_t n) { … } /* * Add the contents of u to w. Carries are propagated further. The caller * has to make sure that w is big enough. */ void _mpd_baseaddto(mpd_uint_t *w, const mpd_uint_t *u, mpd_size_t n) { … } /* * Add v to w (len m). The calling function has to handle a possible * final carry. Assumption: m > 0. */ mpd_uint_t _mpd_shortadd(mpd_uint_t *w, mpd_size_t m, mpd_uint_t v) { … } /* Increment u. The calling function has to handle a possible carry. */ mpd_uint_t _mpd_baseincr(mpd_uint_t *u, mpd_size_t n) { … } /* * Knuth, TAOCP, Volume 2, 4.3.1: * w := difference of u (len m) and v (len n). * number in u >= number in v; */ void _mpd_basesub(mpd_uint_t *w, const mpd_uint_t *u, const mpd_uint_t *v, mpd_size_t m, mpd_size_t n) { … } /* * Subtract the contents of u from w. w is larger than u. Borrows are * propagated further, but eventually w can absorb the final borrow. */ void _mpd_basesubfrom(mpd_uint_t *w, const mpd_uint_t *u, mpd_size_t n) { … } /* w := product of u (len n) and v (single word) */ void _mpd_shortmul(mpd_uint_t *w, const mpd_uint_t *u, mpd_size_t n, mpd_uint_t v) { … } /* * Knuth, TAOCP, Volume 2, 4.3.1: * w := product of u (len m) and v (len n) * w must be initialized to zero */ void _mpd_basemul(mpd_uint_t *w, const mpd_uint_t *u, const mpd_uint_t *v, mpd_size_t m, mpd_size_t n) { … } /* * Knuth, TAOCP Volume 2, 4.3.1, exercise 16: * w := quotient of u (len n) divided by a single word v */ mpd_uint_t _mpd_shortdiv(mpd_uint_t *w, const mpd_uint_t *u, mpd_size_t n, mpd_uint_t v) { … } /* * Knuth, TAOCP Volume 2, 4.3.1: * q, r := quotient and remainder of uconst (len nplusm) * divided by vconst (len n) * nplusm >= n * * If r is not NULL, r will contain the remainder. If r is NULL, the * return value indicates if there is a remainder: 1 for true, 0 for * false. A return value of -1 indicates an error. */ int _mpd_basedivmod(mpd_uint_t *q, mpd_uint_t *r, const mpd_uint_t *uconst, const mpd_uint_t *vconst, mpd_size_t nplusm, mpd_size_t n) { … } /* * Left shift of src by 'shift' digits; src may equal dest. * * dest := area of n mpd_uint_t with space for srcdigits+shift digits. * src := coefficient with length m. * * The case splits in the function are non-obvious. The following * equations might help: * * Let msdigits denote the number of digits in the most significant * word of src. Then 1 <= msdigits <= rdigits. * * 1) shift = q * rdigits + r * 2) srcdigits = qsrc * rdigits + msdigits * 3) destdigits = shift + srcdigits * = q * rdigits + r + qsrc * rdigits + msdigits * = q * rdigits + (qsrc * rdigits + (r + msdigits)) * * The result has q zero words, followed by the coefficient that * is left-shifted by r. The case r == 0 is trivial. For r > 0, it * is important to keep in mind that we always read m source words, * but write m+1 destination words if r + msdigits > rdigits, m words * otherwise. */ void _mpd_baseshiftl(mpd_uint_t *dest, mpd_uint_t *src, mpd_size_t n, mpd_size_t m, mpd_size_t shift) { … } /* * Right shift of src by 'shift' digits; src may equal dest. * Assumption: srcdigits-shift > 0. * * dest := area with space for srcdigits-shift digits. * src := coefficient with length 'slen'. * * The case splits in the function rely on the following equations: * * Let msdigits denote the number of digits in the most significant * word of src. Then 1 <= msdigits <= rdigits. * * 1) shift = q * rdigits + r * 2) srcdigits = qsrc * rdigits + msdigits * 3) destdigits = srcdigits - shift * = qsrc * rdigits + msdigits - (q * rdigits + r) * = (qsrc - q) * rdigits + msdigits - r * * Since destdigits > 0 and 1 <= msdigits <= rdigits: * * 4) qsrc >= q * 5) qsrc == q ==> msdigits > r * * The result has slen-q words if msdigits > r, slen-q-1 words otherwise. */ mpd_uint_t _mpd_baseshiftr(mpd_uint_t *dest, mpd_uint_t *src, mpd_size_t slen, mpd_size_t shift) { … } /*********************************************************************/ /* Calculations in base b */ /*********************************************************************/ /* * Add v to w (len m). The calling function has to handle a possible * final carry. Assumption: m > 0. */ mpd_uint_t _mpd_shortadd_b(mpd_uint_t *w, mpd_size_t m, mpd_uint_t v, mpd_uint_t b) { … } /* w := product of u (len n) and v (single word). Return carry. */ mpd_uint_t _mpd_shortmul_c(mpd_uint_t *w, const mpd_uint_t *u, mpd_size_t n, mpd_uint_t v) { … } /* w := product of u (len n) and v (single word) */ mpd_uint_t _mpd_shortmul_b(mpd_uint_t *w, const mpd_uint_t *u, mpd_size_t n, mpd_uint_t v, mpd_uint_t b) { … } /* * Knuth, TAOCP Volume 2, 4.3.1, exercise 16: * w := quotient of u (len n) divided by a single word v */ mpd_uint_t _mpd_shortdiv_b(mpd_uint_t *w, const mpd_uint_t *u, mpd_size_t n, mpd_uint_t v, mpd_uint_t b) { … }
Codebase Browser
cpython