Port of MicroPython to the mbed platform. See micropython-repl for an interactive program.

Dependents:   micropython-repl

This a port of MicroPython to the mbed Classic platform.

This provides an interpreter running on the board's USB serial connection.

Getting Started

Import the micropython-repl program into your IDE workspace on developer.mbed.org. Compile and download to your board. Connect to the USB serial port in your usual manner. You should get a startup message similar to the following:

  MicroPython v1.7-155-gdddcdd8 on 2016-04-23; K64F with ARM
  Type "help()" for more information.
  >>>

Then you can start using micropython. For example:

  >>> from mbed import DigitalOut
  >>> from pins import LED1
  >>> led = DigitalOut(LED1)
  >>> led.write(1)

Requirements

You need approximately 100K of flash memory, so this will be no good for boards with smaller amounts of storage.

Caveats

This can be considered an alpha release of the port; things may not work; APIs may change in later releases. It is NOT an official part part the micropython project, so if anything doesn't work, blame me. If it does work, most of the credit is due to micropython.

  • Only a few of the mbed classes are available in micropython so far, and not all methods of those that are.
  • Only a few boards have their full range of pin names available; for others, only a few standard ones (USBTX, USBRX, LED1) are implemented.
  • The garbage collector is not yet implemented. The interpreter will gradually consume memory and then fail.
  • Exceptions from the mbed classes are not yet handled.
  • Asynchronous processing (e.g. events on inputs) is not supported.

Credits

  • Damien P. George and other contributors who created micropython.
  • Colin Hogben, author of this port.
Committer:
pythontech
Date:
Sat Apr 16 17:11:56 2016 +0000
Revision:
0:5868e8752d44
Split off library from repl

Who changed what in which revision?

UserRevisionLine numberNew contents of line
pythontech 0:5868e8752d44 1 /*
pythontech 0:5868e8752d44 2 * This file is part of the Micro Python project, http://micropython.org/
pythontech 0:5868e8752d44 3 *
pythontech 0:5868e8752d44 4 * The MIT License (MIT)
pythontech 0:5868e8752d44 5 *
pythontech 0:5868e8752d44 6 * Copyright (c) 2013, 2014 Damien P. George
pythontech 0:5868e8752d44 7 *
pythontech 0:5868e8752d44 8 * Permission is hereby granted, free of charge, to any person obtaining a copy
pythontech 0:5868e8752d44 9 * of this software and associated documentation files (the "Software"), to deal
pythontech 0:5868e8752d44 10 * in the Software without restriction, including without limitation the rights
pythontech 0:5868e8752d44 11 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
pythontech 0:5868e8752d44 12 * copies of the Software, and to permit persons to whom the Software is
pythontech 0:5868e8752d44 13 * furnished to do so, subject to the following conditions:
pythontech 0:5868e8752d44 14 *
pythontech 0:5868e8752d44 15 * The above copyright notice and this permission notice shall be included in
pythontech 0:5868e8752d44 16 * all copies or substantial portions of the Software.
pythontech 0:5868e8752d44 17 *
pythontech 0:5868e8752d44 18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
pythontech 0:5868e8752d44 19 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
pythontech 0:5868e8752d44 20 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
pythontech 0:5868e8752d44 21 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
pythontech 0:5868e8752d44 22 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
pythontech 0:5868e8752d44 23 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
pythontech 0:5868e8752d44 24 * THE SOFTWARE.
pythontech 0:5868e8752d44 25 */
pythontech 0:5868e8752d44 26
pythontech 0:5868e8752d44 27 #include <string.h>
pythontech 0:5868e8752d44 28 #include <assert.h>
pythontech 0:5868e8752d44 29
pythontech 0:5868e8752d44 30 #include "py/mpz.h"
pythontech 0:5868e8752d44 31
pythontech 0:5868e8752d44 32 #if MICROPY_LONGINT_IMPL == MICROPY_LONGINT_IMPL_MPZ
pythontech 0:5868e8752d44 33
pythontech 0:5868e8752d44 34 #define DIG_SIZE (MPZ_DIG_SIZE)
pythontech 0:5868e8752d44 35 #define DIG_MASK ((MPZ_LONG_1 << DIG_SIZE) - 1)
pythontech 0:5868e8752d44 36 #define DIG_MSB (MPZ_LONG_1 << (DIG_SIZE - 1))
pythontech 0:5868e8752d44 37 #define DIG_BASE (MPZ_LONG_1 << DIG_SIZE)
pythontech 0:5868e8752d44 38
pythontech 0:5868e8752d44 39 /*
pythontech 0:5868e8752d44 40 mpz is an arbitrary precision integer type with a public API.
pythontech 0:5868e8752d44 41
pythontech 0:5868e8752d44 42 mpn functions act on non-negative integers represented by an array of generalised
pythontech 0:5868e8752d44 43 digits (eg a word per digit). You also need to specify separately the length of the
pythontech 0:5868e8752d44 44 array. There is no public API for mpn. Rather, the functions are used by mpz to
pythontech 0:5868e8752d44 45 implement its features.
pythontech 0:5868e8752d44 46
pythontech 0:5868e8752d44 47 Integer values are stored little endian (first digit is first in memory).
pythontech 0:5868e8752d44 48
pythontech 0:5868e8752d44 49 Definition of normalise: ?
pythontech 0:5868e8752d44 50 */
pythontech 0:5868e8752d44 51
pythontech 0:5868e8752d44 52 /* compares i with j
pythontech 0:5868e8752d44 53 returns sign(i - j)
pythontech 0:5868e8752d44 54 assumes i, j are normalised
pythontech 0:5868e8752d44 55 */
pythontech 0:5868e8752d44 56 STATIC int mpn_cmp(const mpz_dig_t *idig, mp_uint_t ilen, const mpz_dig_t *jdig, mp_uint_t jlen) {
pythontech 0:5868e8752d44 57 if (ilen < jlen) { return -1; }
pythontech 0:5868e8752d44 58 if (ilen > jlen) { return 1; }
pythontech 0:5868e8752d44 59
pythontech 0:5868e8752d44 60 for (idig += ilen, jdig += ilen; ilen > 0; --ilen) {
pythontech 0:5868e8752d44 61 mpz_dbl_dig_signed_t cmp = (mpz_dbl_dig_t)*(--idig) - (mpz_dbl_dig_t)*(--jdig);
pythontech 0:5868e8752d44 62 if (cmp < 0) { return -1; }
pythontech 0:5868e8752d44 63 if (cmp > 0) { return 1; }
pythontech 0:5868e8752d44 64 }
pythontech 0:5868e8752d44 65
pythontech 0:5868e8752d44 66 return 0;
pythontech 0:5868e8752d44 67 }
pythontech 0:5868e8752d44 68
pythontech 0:5868e8752d44 69 /* computes i = j << n
pythontech 0:5868e8752d44 70 returns number of digits in i
pythontech 0:5868e8752d44 71 assumes enough memory in i; assumes normalised j; assumes n > 0
pythontech 0:5868e8752d44 72 can have i, j pointing to same memory
pythontech 0:5868e8752d44 73 */
pythontech 0:5868e8752d44 74 STATIC mp_uint_t mpn_shl(mpz_dig_t *idig, mpz_dig_t *jdig, mp_uint_t jlen, mp_uint_t n) {
pythontech 0:5868e8752d44 75 mp_uint_t n_whole = (n + DIG_SIZE - 1) / DIG_SIZE;
pythontech 0:5868e8752d44 76 mp_uint_t n_part = n % DIG_SIZE;
pythontech 0:5868e8752d44 77 if (n_part == 0) {
pythontech 0:5868e8752d44 78 n_part = DIG_SIZE;
pythontech 0:5868e8752d44 79 }
pythontech 0:5868e8752d44 80
pythontech 0:5868e8752d44 81 // start from the high end of the digit arrays
pythontech 0:5868e8752d44 82 idig += jlen + n_whole - 1;
pythontech 0:5868e8752d44 83 jdig += jlen - 1;
pythontech 0:5868e8752d44 84
pythontech 0:5868e8752d44 85 // shift the digits
pythontech 0:5868e8752d44 86 mpz_dbl_dig_t d = 0;
pythontech 0:5868e8752d44 87 for (mp_uint_t i = jlen; i > 0; i--, idig--, jdig--) {
pythontech 0:5868e8752d44 88 d |= *jdig;
pythontech 0:5868e8752d44 89 *idig = (d >> (DIG_SIZE - n_part)) & DIG_MASK;
pythontech 0:5868e8752d44 90 d <<= DIG_SIZE;
pythontech 0:5868e8752d44 91 }
pythontech 0:5868e8752d44 92
pythontech 0:5868e8752d44 93 // store remaining bits
pythontech 0:5868e8752d44 94 *idig = (d >> (DIG_SIZE - n_part)) & DIG_MASK;
pythontech 0:5868e8752d44 95 idig -= n_whole - 1;
pythontech 0:5868e8752d44 96 memset(idig, 0, (n_whole - 1) * sizeof(mpz_dig_t));
pythontech 0:5868e8752d44 97
pythontech 0:5868e8752d44 98 // work out length of result
pythontech 0:5868e8752d44 99 jlen += n_whole;
pythontech 0:5868e8752d44 100 while (jlen != 0 && idig[jlen - 1] == 0) {
pythontech 0:5868e8752d44 101 jlen--;
pythontech 0:5868e8752d44 102 }
pythontech 0:5868e8752d44 103
pythontech 0:5868e8752d44 104 // return length of result
pythontech 0:5868e8752d44 105 return jlen;
pythontech 0:5868e8752d44 106 }
pythontech 0:5868e8752d44 107
pythontech 0:5868e8752d44 108 /* computes i = j >> n
pythontech 0:5868e8752d44 109 returns number of digits in i
pythontech 0:5868e8752d44 110 assumes enough memory in i; assumes normalised j; assumes n > 0
pythontech 0:5868e8752d44 111 can have i, j pointing to same memory
pythontech 0:5868e8752d44 112 */
pythontech 0:5868e8752d44 113 STATIC mp_uint_t mpn_shr(mpz_dig_t *idig, mpz_dig_t *jdig, mp_uint_t jlen, mp_uint_t n) {
pythontech 0:5868e8752d44 114 mp_uint_t n_whole = n / DIG_SIZE;
pythontech 0:5868e8752d44 115 mp_uint_t n_part = n % DIG_SIZE;
pythontech 0:5868e8752d44 116
pythontech 0:5868e8752d44 117 if (n_whole >= jlen) {
pythontech 0:5868e8752d44 118 return 0;
pythontech 0:5868e8752d44 119 }
pythontech 0:5868e8752d44 120
pythontech 0:5868e8752d44 121 jdig += n_whole;
pythontech 0:5868e8752d44 122 jlen -= n_whole;
pythontech 0:5868e8752d44 123
pythontech 0:5868e8752d44 124 for (mp_uint_t i = jlen; i > 0; i--, idig++, jdig++) {
pythontech 0:5868e8752d44 125 mpz_dbl_dig_t d = *jdig;
pythontech 0:5868e8752d44 126 if (i > 1) {
pythontech 0:5868e8752d44 127 d |= (mpz_dbl_dig_t)jdig[1] << DIG_SIZE;
pythontech 0:5868e8752d44 128 }
pythontech 0:5868e8752d44 129 d >>= n_part;
pythontech 0:5868e8752d44 130 *idig = d & DIG_MASK;
pythontech 0:5868e8752d44 131 }
pythontech 0:5868e8752d44 132
pythontech 0:5868e8752d44 133 if (idig[-1] == 0) {
pythontech 0:5868e8752d44 134 jlen--;
pythontech 0:5868e8752d44 135 }
pythontech 0:5868e8752d44 136
pythontech 0:5868e8752d44 137 return jlen;
pythontech 0:5868e8752d44 138 }
pythontech 0:5868e8752d44 139
pythontech 0:5868e8752d44 140 /* computes i = j + k
pythontech 0:5868e8752d44 141 returns number of digits in i
pythontech 0:5868e8752d44 142 assumes enough memory in i; assumes normalised j, k; assumes jlen >= klen
pythontech 0:5868e8752d44 143 can have i, j, k pointing to same memory
pythontech 0:5868e8752d44 144 */
pythontech 0:5868e8752d44 145 STATIC mp_uint_t mpn_add(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen) {
pythontech 0:5868e8752d44 146 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 147 mpz_dbl_dig_t carry = 0;
pythontech 0:5868e8752d44 148
pythontech 0:5868e8752d44 149 jlen -= klen;
pythontech 0:5868e8752d44 150
pythontech 0:5868e8752d44 151 for (; klen > 0; --klen, ++idig, ++jdig, ++kdig) {
pythontech 0:5868e8752d44 152 carry += (mpz_dbl_dig_t)*jdig + (mpz_dbl_dig_t)*kdig;
pythontech 0:5868e8752d44 153 *idig = carry & DIG_MASK;
pythontech 0:5868e8752d44 154 carry >>= DIG_SIZE;
pythontech 0:5868e8752d44 155 }
pythontech 0:5868e8752d44 156
pythontech 0:5868e8752d44 157 for (; jlen > 0; --jlen, ++idig, ++jdig) {
pythontech 0:5868e8752d44 158 carry += *jdig;
pythontech 0:5868e8752d44 159 *idig = carry & DIG_MASK;
pythontech 0:5868e8752d44 160 carry >>= DIG_SIZE;
pythontech 0:5868e8752d44 161 }
pythontech 0:5868e8752d44 162
pythontech 0:5868e8752d44 163 if (carry != 0) {
pythontech 0:5868e8752d44 164 *idig++ = carry;
pythontech 0:5868e8752d44 165 }
pythontech 0:5868e8752d44 166
pythontech 0:5868e8752d44 167 return idig - oidig;
pythontech 0:5868e8752d44 168 }
pythontech 0:5868e8752d44 169
pythontech 0:5868e8752d44 170 /* computes i = j - k
pythontech 0:5868e8752d44 171 returns number of digits in i
pythontech 0:5868e8752d44 172 assumes enough memory in i; assumes normalised j, k; assumes j >= k
pythontech 0:5868e8752d44 173 can have i, j, k pointing to same memory
pythontech 0:5868e8752d44 174 */
pythontech 0:5868e8752d44 175 STATIC mp_uint_t mpn_sub(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen) {
pythontech 0:5868e8752d44 176 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 177 mpz_dbl_dig_signed_t borrow = 0;
pythontech 0:5868e8752d44 178
pythontech 0:5868e8752d44 179 jlen -= klen;
pythontech 0:5868e8752d44 180
pythontech 0:5868e8752d44 181 for (; klen > 0; --klen, ++idig, ++jdig, ++kdig) {
pythontech 0:5868e8752d44 182 borrow += (mpz_dbl_dig_t)*jdig - (mpz_dbl_dig_t)*kdig;
pythontech 0:5868e8752d44 183 *idig = borrow & DIG_MASK;
pythontech 0:5868e8752d44 184 borrow >>= DIG_SIZE;
pythontech 0:5868e8752d44 185 }
pythontech 0:5868e8752d44 186
pythontech 0:5868e8752d44 187 for (; jlen > 0; --jlen, ++idig, ++jdig) {
pythontech 0:5868e8752d44 188 borrow += *jdig;
pythontech 0:5868e8752d44 189 *idig = borrow & DIG_MASK;
pythontech 0:5868e8752d44 190 borrow >>= DIG_SIZE;
pythontech 0:5868e8752d44 191 }
pythontech 0:5868e8752d44 192
pythontech 0:5868e8752d44 193 for (--idig; idig >= oidig && *idig == 0; --idig) {
pythontech 0:5868e8752d44 194 }
pythontech 0:5868e8752d44 195
pythontech 0:5868e8752d44 196 return idig + 1 - oidig;
pythontech 0:5868e8752d44 197 }
pythontech 0:5868e8752d44 198
pythontech 0:5868e8752d44 199 STATIC mp_uint_t mpn_remove_trailing_zeros(mpz_dig_t *oidig, mpz_dig_t *idig) {
pythontech 0:5868e8752d44 200 for (--idig; idig >= oidig && *idig == 0; --idig) {
pythontech 0:5868e8752d44 201 }
pythontech 0:5868e8752d44 202 return idig + 1 - oidig;
pythontech 0:5868e8752d44 203 }
pythontech 0:5868e8752d44 204
pythontech 0:5868e8752d44 205 #if MICROPY_OPT_MPZ_BITWISE
pythontech 0:5868e8752d44 206
pythontech 0:5868e8752d44 207 /* computes i = j & k
pythontech 0:5868e8752d44 208 returns number of digits in i
pythontech 0:5868e8752d44 209 assumes enough memory in i; assumes normalised j, k; assumes jlen >= klen (jlen argument not needed)
pythontech 0:5868e8752d44 210 can have i, j, k pointing to same memory
pythontech 0:5868e8752d44 211 */
pythontech 0:5868e8752d44 212 STATIC mp_uint_t mpn_and(mpz_dig_t *idig, const mpz_dig_t *jdig, const mpz_dig_t *kdig, mp_uint_t klen) {
pythontech 0:5868e8752d44 213 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 214
pythontech 0:5868e8752d44 215 for (; klen > 0; --klen, ++idig, ++jdig, ++kdig) {
pythontech 0:5868e8752d44 216 *idig = *jdig & *kdig;
pythontech 0:5868e8752d44 217 }
pythontech 0:5868e8752d44 218
pythontech 0:5868e8752d44 219 return mpn_remove_trailing_zeros(oidig, idig);
pythontech 0:5868e8752d44 220 }
pythontech 0:5868e8752d44 221
pythontech 0:5868e8752d44 222 #endif
pythontech 0:5868e8752d44 223
pythontech 0:5868e8752d44 224 /* i = -((-j) & (-k)) = ~((~j + 1) & (~k + 1)) + 1
pythontech 0:5868e8752d44 225 i = (j & (-k)) = (j & (~k + 1)) = ( j & (~k + 1))
pythontech 0:5868e8752d44 226 i = ((-j) & k) = ((~j + 1) & k) = ((~j + 1) & k )
pythontech 0:5868e8752d44 227 computes general form:
pythontech 0:5868e8752d44 228 i = (im ^ (((j ^ jm) + jc) & ((k ^ km) + kc))) + ic where Xm = Xc == 0 ? 0 : DIG_MASK
pythontech 0:5868e8752d44 229 returns number of digits in i
pythontech 0:5868e8752d44 230 assumes enough memory in i; assumes normalised j, k; assumes length j >= length k
pythontech 0:5868e8752d44 231 can have i, j, k pointing to same memory
pythontech 0:5868e8752d44 232 */
pythontech 0:5868e8752d44 233 STATIC mp_uint_t mpn_and_neg(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen,
pythontech 0:5868e8752d44 234 mpz_dbl_dig_t carryi, mpz_dbl_dig_t carryj, mpz_dbl_dig_t carryk) {
pythontech 0:5868e8752d44 235 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 236 mpz_dig_t imask = (0 == carryi) ? 0 : DIG_MASK;
pythontech 0:5868e8752d44 237 mpz_dig_t jmask = (0 == carryj) ? 0 : DIG_MASK;
pythontech 0:5868e8752d44 238 mpz_dig_t kmask = (0 == carryk) ? 0 : DIG_MASK;
pythontech 0:5868e8752d44 239
pythontech 0:5868e8752d44 240 for (; jlen > 0; ++idig, ++jdig) {
pythontech 0:5868e8752d44 241 carryj += *jdig ^ jmask;
pythontech 0:5868e8752d44 242 carryk += (--klen <= --jlen) ? (*kdig++ ^ kmask) : kmask;
pythontech 0:5868e8752d44 243 carryi += ((carryj & carryk) ^ imask) & DIG_MASK;
pythontech 0:5868e8752d44 244 *idig = carryi & DIG_MASK;
pythontech 0:5868e8752d44 245 carryk >>= DIG_SIZE;
pythontech 0:5868e8752d44 246 carryj >>= DIG_SIZE;
pythontech 0:5868e8752d44 247 carryi >>= DIG_SIZE;
pythontech 0:5868e8752d44 248 }
pythontech 0:5868e8752d44 249
pythontech 0:5868e8752d44 250 if (0 != carryi) {
pythontech 0:5868e8752d44 251 *idig++ = carryi;
pythontech 0:5868e8752d44 252 }
pythontech 0:5868e8752d44 253
pythontech 0:5868e8752d44 254 return mpn_remove_trailing_zeros(oidig, idig);
pythontech 0:5868e8752d44 255 }
pythontech 0:5868e8752d44 256
pythontech 0:5868e8752d44 257 #if MICROPY_OPT_MPZ_BITWISE
pythontech 0:5868e8752d44 258
pythontech 0:5868e8752d44 259 /* computes i = j | k
pythontech 0:5868e8752d44 260 returns number of digits in i
pythontech 0:5868e8752d44 261 assumes enough memory in i; assumes normalised j, k; assumes jlen >= klen
pythontech 0:5868e8752d44 262 can have i, j, k pointing to same memory
pythontech 0:5868e8752d44 263 */
pythontech 0:5868e8752d44 264 STATIC mp_uint_t mpn_or(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen) {
pythontech 0:5868e8752d44 265 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 266
pythontech 0:5868e8752d44 267 jlen -= klen;
pythontech 0:5868e8752d44 268
pythontech 0:5868e8752d44 269 for (; klen > 0; --klen, ++idig, ++jdig, ++kdig) {
pythontech 0:5868e8752d44 270 *idig = *jdig | *kdig;
pythontech 0:5868e8752d44 271 }
pythontech 0:5868e8752d44 272
pythontech 0:5868e8752d44 273 for (; jlen > 0; --jlen, ++idig, ++jdig) {
pythontech 0:5868e8752d44 274 *idig = *jdig;
pythontech 0:5868e8752d44 275 }
pythontech 0:5868e8752d44 276
pythontech 0:5868e8752d44 277 return idig - oidig;
pythontech 0:5868e8752d44 278 }
pythontech 0:5868e8752d44 279
pythontech 0:5868e8752d44 280 #endif
pythontech 0:5868e8752d44 281
pythontech 0:5868e8752d44 282 /* i = -((-j) | (-k)) = ~((~j + 1) | (~k + 1)) + 1
pythontech 0:5868e8752d44 283 i = -(j | (-k)) = -(j | (~k + 1)) = ~( j | (~k + 1)) + 1
pythontech 0:5868e8752d44 284 i = -((-j) | k) = -((~j + 1) | k) = ~((~j + 1) | k ) + 1
pythontech 0:5868e8752d44 285 computes general form:
pythontech 0:5868e8752d44 286 i = ~(((j ^ jm) + jc) | ((k ^ km) + kc)) + 1 where Xm = Xc == 0 ? 0 : DIG_MASK
pythontech 0:5868e8752d44 287 returns number of digits in i
pythontech 0:5868e8752d44 288 assumes enough memory in i; assumes normalised j, k; assumes length j >= length k
pythontech 0:5868e8752d44 289 can have i, j, k pointing to same memory
pythontech 0:5868e8752d44 290 */
pythontech 0:5868e8752d44 291
pythontech 0:5868e8752d44 292 #if MICROPY_OPT_MPZ_BITWISE
pythontech 0:5868e8752d44 293
pythontech 0:5868e8752d44 294 STATIC mp_uint_t mpn_or_neg(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen,
pythontech 0:5868e8752d44 295 mpz_dbl_dig_t carryj, mpz_dbl_dig_t carryk) {
pythontech 0:5868e8752d44 296 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 297 mpz_dbl_dig_t carryi = 1;
pythontech 0:5868e8752d44 298 mpz_dig_t jmask = (0 == carryj) ? 0 : DIG_MASK;
pythontech 0:5868e8752d44 299 mpz_dig_t kmask = (0 == carryk) ? 0 : DIG_MASK;
pythontech 0:5868e8752d44 300
pythontech 0:5868e8752d44 301 for (; jlen > 0; ++idig, ++jdig) {
pythontech 0:5868e8752d44 302 carryj += *jdig ^ jmask;
pythontech 0:5868e8752d44 303 carryk += (--klen <= --jlen) ? (*kdig++ ^ kmask) : kmask;
pythontech 0:5868e8752d44 304 carryi += ((carryj | carryk) ^ DIG_MASK) & DIG_MASK;
pythontech 0:5868e8752d44 305 *idig = carryi & DIG_MASK;
pythontech 0:5868e8752d44 306 carryk >>= DIG_SIZE;
pythontech 0:5868e8752d44 307 carryj >>= DIG_SIZE;
pythontech 0:5868e8752d44 308 carryi >>= DIG_SIZE;
pythontech 0:5868e8752d44 309 }
pythontech 0:5868e8752d44 310
pythontech 0:5868e8752d44 311 if (0 != carryi) {
pythontech 0:5868e8752d44 312 *idig++ = carryi;
pythontech 0:5868e8752d44 313 }
pythontech 0:5868e8752d44 314
pythontech 0:5868e8752d44 315 return mpn_remove_trailing_zeros(oidig, idig);
pythontech 0:5868e8752d44 316 }
pythontech 0:5868e8752d44 317
pythontech 0:5868e8752d44 318 #else
pythontech 0:5868e8752d44 319
pythontech 0:5868e8752d44 320 STATIC mp_uint_t mpn_or_neg(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen,
pythontech 0:5868e8752d44 321 mpz_dbl_dig_t carryi, mpz_dbl_dig_t carryj, mpz_dbl_dig_t carryk) {
pythontech 0:5868e8752d44 322 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 323 mpz_dig_t imask = (0 == carryi) ? 0 : DIG_MASK;
pythontech 0:5868e8752d44 324 mpz_dig_t jmask = (0 == carryj) ? 0 : DIG_MASK;
pythontech 0:5868e8752d44 325 mpz_dig_t kmask = (0 == carryk) ? 0 : DIG_MASK;
pythontech 0:5868e8752d44 326
pythontech 0:5868e8752d44 327 for (; jlen > 0; ++idig, ++jdig) {
pythontech 0:5868e8752d44 328 carryj += *jdig ^ jmask;
pythontech 0:5868e8752d44 329 carryk += (--klen <= --jlen) ? (*kdig++ ^ kmask) : kmask;
pythontech 0:5868e8752d44 330 carryi += ((carryj | carryk) ^ imask) & DIG_MASK;
pythontech 0:5868e8752d44 331 *idig = carryi & DIG_MASK;
pythontech 0:5868e8752d44 332 carryk >>= DIG_SIZE;
pythontech 0:5868e8752d44 333 carryj >>= DIG_SIZE;
pythontech 0:5868e8752d44 334 carryi >>= DIG_SIZE;
pythontech 0:5868e8752d44 335 }
pythontech 0:5868e8752d44 336
pythontech 0:5868e8752d44 337 if (0 != carryi) {
pythontech 0:5868e8752d44 338 *idig++ = carryi;
pythontech 0:5868e8752d44 339 }
pythontech 0:5868e8752d44 340
pythontech 0:5868e8752d44 341 return mpn_remove_trailing_zeros(oidig, idig);
pythontech 0:5868e8752d44 342 }
pythontech 0:5868e8752d44 343
pythontech 0:5868e8752d44 344 #endif
pythontech 0:5868e8752d44 345
pythontech 0:5868e8752d44 346 #if MICROPY_OPT_MPZ_BITWISE
pythontech 0:5868e8752d44 347
pythontech 0:5868e8752d44 348 /* computes i = j ^ k
pythontech 0:5868e8752d44 349 returns number of digits in i
pythontech 0:5868e8752d44 350 assumes enough memory in i; assumes normalised j, k; assumes jlen >= klen
pythontech 0:5868e8752d44 351 can have i, j, k pointing to same memory
pythontech 0:5868e8752d44 352 */
pythontech 0:5868e8752d44 353 STATIC mp_uint_t mpn_xor(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen) {
pythontech 0:5868e8752d44 354 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 355
pythontech 0:5868e8752d44 356 jlen -= klen;
pythontech 0:5868e8752d44 357
pythontech 0:5868e8752d44 358 for (; klen > 0; --klen, ++idig, ++jdig, ++kdig) {
pythontech 0:5868e8752d44 359 *idig = *jdig ^ *kdig;
pythontech 0:5868e8752d44 360 }
pythontech 0:5868e8752d44 361
pythontech 0:5868e8752d44 362 for (; jlen > 0; --jlen, ++idig, ++jdig) {
pythontech 0:5868e8752d44 363 *idig = *jdig;
pythontech 0:5868e8752d44 364 }
pythontech 0:5868e8752d44 365
pythontech 0:5868e8752d44 366 return mpn_remove_trailing_zeros(oidig, idig);
pythontech 0:5868e8752d44 367 }
pythontech 0:5868e8752d44 368
pythontech 0:5868e8752d44 369 #endif
pythontech 0:5868e8752d44 370
pythontech 0:5868e8752d44 371 /* i = (-j) ^ (-k) = ~(j - 1) ^ ~(k - 1) = (j - 1) ^ (k - 1)
pythontech 0:5868e8752d44 372 i = -(j ^ (-k)) = -(j ^ ~(k - 1)) = ~(j ^ ~(k - 1)) + 1 = (j ^ (k - 1)) + 1
pythontech 0:5868e8752d44 373 i = -((-j) ^ k) = -(~(j - 1) ^ k) = ~(~(j - 1) ^ k) + 1 = ((j - 1) ^ k) + 1
pythontech 0:5868e8752d44 374 computes general form:
pythontech 0:5868e8752d44 375 i = ((j - 1 + jc) ^ (k - 1 + kc)) + ic
pythontech 0:5868e8752d44 376 returns number of digits in i
pythontech 0:5868e8752d44 377 assumes enough memory in i; assumes normalised j, k; assumes length j >= length k
pythontech 0:5868e8752d44 378 can have i, j, k pointing to same memory
pythontech 0:5868e8752d44 379 */
pythontech 0:5868e8752d44 380 STATIC mp_uint_t mpn_xor_neg(mpz_dig_t *idig, const mpz_dig_t *jdig, mp_uint_t jlen, const mpz_dig_t *kdig, mp_uint_t klen,
pythontech 0:5868e8752d44 381 mpz_dbl_dig_t carryi, mpz_dbl_dig_t carryj, mpz_dbl_dig_t carryk) {
pythontech 0:5868e8752d44 382 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 383
pythontech 0:5868e8752d44 384 for (; jlen > 0; ++idig, ++jdig) {
pythontech 0:5868e8752d44 385 carryj += *jdig + DIG_MASK;
pythontech 0:5868e8752d44 386 carryk += (--klen <= --jlen) ? (*kdig++ + DIG_MASK) : DIG_MASK;
pythontech 0:5868e8752d44 387 carryi += (carryj ^ carryk) & DIG_MASK;
pythontech 0:5868e8752d44 388 *idig = carryi & DIG_MASK;
pythontech 0:5868e8752d44 389 carryk >>= DIG_SIZE;
pythontech 0:5868e8752d44 390 carryj >>= DIG_SIZE;
pythontech 0:5868e8752d44 391 carryi >>= DIG_SIZE;
pythontech 0:5868e8752d44 392 }
pythontech 0:5868e8752d44 393
pythontech 0:5868e8752d44 394 if (0 != carryi) {
pythontech 0:5868e8752d44 395 *idig++ = carryi;
pythontech 0:5868e8752d44 396 }
pythontech 0:5868e8752d44 397
pythontech 0:5868e8752d44 398 return mpn_remove_trailing_zeros(oidig, idig);
pythontech 0:5868e8752d44 399 }
pythontech 0:5868e8752d44 400
pythontech 0:5868e8752d44 401 /* computes i = i * d1 + d2
pythontech 0:5868e8752d44 402 returns number of digits in i
pythontech 0:5868e8752d44 403 assumes enough memory in i; assumes normalised i; assumes dmul != 0
pythontech 0:5868e8752d44 404 */
pythontech 0:5868e8752d44 405 STATIC mp_uint_t mpn_mul_dig_add_dig(mpz_dig_t *idig, mp_uint_t ilen, mpz_dig_t dmul, mpz_dig_t dadd) {
pythontech 0:5868e8752d44 406 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 407 mpz_dbl_dig_t carry = dadd;
pythontech 0:5868e8752d44 408
pythontech 0:5868e8752d44 409 for (; ilen > 0; --ilen, ++idig) {
pythontech 0:5868e8752d44 410 carry += (mpz_dbl_dig_t)*idig * (mpz_dbl_dig_t)dmul; // will never overflow so long as DIG_SIZE <= 8*sizeof(mpz_dbl_dig_t)/2
pythontech 0:5868e8752d44 411 *idig = carry & DIG_MASK;
pythontech 0:5868e8752d44 412 carry >>= DIG_SIZE;
pythontech 0:5868e8752d44 413 }
pythontech 0:5868e8752d44 414
pythontech 0:5868e8752d44 415 if (carry != 0) {
pythontech 0:5868e8752d44 416 *idig++ = carry;
pythontech 0:5868e8752d44 417 }
pythontech 0:5868e8752d44 418
pythontech 0:5868e8752d44 419 return idig - oidig;
pythontech 0:5868e8752d44 420 }
pythontech 0:5868e8752d44 421
pythontech 0:5868e8752d44 422 /* computes i = j * k
pythontech 0:5868e8752d44 423 returns number of digits in i
pythontech 0:5868e8752d44 424 assumes enough memory in i; assumes i is zeroed; assumes normalised j, k
pythontech 0:5868e8752d44 425 can have j, k point to same memory
pythontech 0:5868e8752d44 426 */
pythontech 0:5868e8752d44 427 STATIC mp_uint_t mpn_mul(mpz_dig_t *idig, mpz_dig_t *jdig, mp_uint_t jlen, mpz_dig_t *kdig, mp_uint_t klen) {
pythontech 0:5868e8752d44 428 mpz_dig_t *oidig = idig;
pythontech 0:5868e8752d44 429 mp_uint_t ilen = 0;
pythontech 0:5868e8752d44 430
pythontech 0:5868e8752d44 431 for (; klen > 0; --klen, ++idig, ++kdig) {
pythontech 0:5868e8752d44 432 mpz_dig_t *id = idig;
pythontech 0:5868e8752d44 433 mpz_dbl_dig_t carry = 0;
pythontech 0:5868e8752d44 434
pythontech 0:5868e8752d44 435 mp_uint_t jl = jlen;
pythontech 0:5868e8752d44 436 for (mpz_dig_t *jd = jdig; jl > 0; --jl, ++jd, ++id) {
pythontech 0:5868e8752d44 437 carry += (mpz_dbl_dig_t)*id + (mpz_dbl_dig_t)*jd * (mpz_dbl_dig_t)*kdig; // will never overflow so long as DIG_SIZE <= 8*sizeof(mpz_dbl_dig_t)/2
pythontech 0:5868e8752d44 438 *id = carry & DIG_MASK;
pythontech 0:5868e8752d44 439 carry >>= DIG_SIZE;
pythontech 0:5868e8752d44 440 }
pythontech 0:5868e8752d44 441
pythontech 0:5868e8752d44 442 if (carry != 0) {
pythontech 0:5868e8752d44 443 *id++ = carry;
pythontech 0:5868e8752d44 444 }
pythontech 0:5868e8752d44 445
pythontech 0:5868e8752d44 446 ilen = id - oidig;
pythontech 0:5868e8752d44 447 }
pythontech 0:5868e8752d44 448
pythontech 0:5868e8752d44 449 return ilen;
pythontech 0:5868e8752d44 450 }
pythontech 0:5868e8752d44 451
pythontech 0:5868e8752d44 452 /* natural_div - quo * den + new_num = old_num (ie num is replaced with rem)
pythontech 0:5868e8752d44 453 assumes den != 0
pythontech 0:5868e8752d44 454 assumes num_dig has enough memory to be extended by 1 digit
pythontech 0:5868e8752d44 455 assumes quo_dig has enough memory (as many digits as num)
pythontech 0:5868e8752d44 456 assumes quo_dig is filled with zeros
pythontech 0:5868e8752d44 457 modifies den_dig memory, but restors it to original state at end
pythontech 0:5868e8752d44 458 */
pythontech 0:5868e8752d44 459
pythontech 0:5868e8752d44 460 STATIC void mpn_div(mpz_dig_t *num_dig, mp_uint_t *num_len, mpz_dig_t *den_dig, mp_uint_t den_len, mpz_dig_t *quo_dig, mp_uint_t *quo_len) {
pythontech 0:5868e8752d44 461 mpz_dig_t *orig_num_dig = num_dig;
pythontech 0:5868e8752d44 462 mpz_dig_t *orig_quo_dig = quo_dig;
pythontech 0:5868e8752d44 463 mpz_dig_t norm_shift = 0;
pythontech 0:5868e8752d44 464 mpz_dbl_dig_t lead_den_digit;
pythontech 0:5868e8752d44 465
pythontech 0:5868e8752d44 466 // handle simple cases
pythontech 0:5868e8752d44 467 {
pythontech 0:5868e8752d44 468 int cmp = mpn_cmp(num_dig, *num_len, den_dig, den_len);
pythontech 0:5868e8752d44 469 if (cmp == 0) {
pythontech 0:5868e8752d44 470 *num_len = 0;
pythontech 0:5868e8752d44 471 quo_dig[0] = 1;
pythontech 0:5868e8752d44 472 *quo_len = 1;
pythontech 0:5868e8752d44 473 return;
pythontech 0:5868e8752d44 474 } else if (cmp < 0) {
pythontech 0:5868e8752d44 475 // numerator remains the same
pythontech 0:5868e8752d44 476 *quo_len = 0;
pythontech 0:5868e8752d44 477 return;
pythontech 0:5868e8752d44 478 }
pythontech 0:5868e8752d44 479 }
pythontech 0:5868e8752d44 480
pythontech 0:5868e8752d44 481 // count number of leading zeros in leading digit of denominator
pythontech 0:5868e8752d44 482 {
pythontech 0:5868e8752d44 483 mpz_dig_t d = den_dig[den_len - 1];
pythontech 0:5868e8752d44 484 while ((d & DIG_MSB) == 0) {
pythontech 0:5868e8752d44 485 d <<= 1;
pythontech 0:5868e8752d44 486 ++norm_shift;
pythontech 0:5868e8752d44 487 }
pythontech 0:5868e8752d44 488 }
pythontech 0:5868e8752d44 489
pythontech 0:5868e8752d44 490 // normalise denomenator (leading bit of leading digit is 1)
pythontech 0:5868e8752d44 491 for (mpz_dig_t *den = den_dig, carry = 0; den < den_dig + den_len; ++den) {
pythontech 0:5868e8752d44 492 mpz_dig_t d = *den;
pythontech 0:5868e8752d44 493 *den = ((d << norm_shift) | carry) & DIG_MASK;
pythontech 0:5868e8752d44 494 carry = d >> (DIG_SIZE - norm_shift);
pythontech 0:5868e8752d44 495 }
pythontech 0:5868e8752d44 496
pythontech 0:5868e8752d44 497 // now need to shift numerator by same amount as denominator
pythontech 0:5868e8752d44 498 // first, increase length of numerator in case we need more room to shift
pythontech 0:5868e8752d44 499 num_dig[*num_len] = 0;
pythontech 0:5868e8752d44 500 ++(*num_len);
pythontech 0:5868e8752d44 501 for (mpz_dig_t *num = num_dig, carry = 0; num < num_dig + *num_len; ++num) {
pythontech 0:5868e8752d44 502 mpz_dig_t n = *num;
pythontech 0:5868e8752d44 503 *num = ((n << norm_shift) | carry) & DIG_MASK;
pythontech 0:5868e8752d44 504 carry = n >> (DIG_SIZE - norm_shift);
pythontech 0:5868e8752d44 505 }
pythontech 0:5868e8752d44 506
pythontech 0:5868e8752d44 507 // cache the leading digit of the denominator
pythontech 0:5868e8752d44 508 lead_den_digit = den_dig[den_len - 1];
pythontech 0:5868e8752d44 509
pythontech 0:5868e8752d44 510 // point num_dig to last digit in numerator
pythontech 0:5868e8752d44 511 num_dig += *num_len - 1;
pythontech 0:5868e8752d44 512
pythontech 0:5868e8752d44 513 // calculate number of digits in quotient
pythontech 0:5868e8752d44 514 *quo_len = *num_len - den_len;
pythontech 0:5868e8752d44 515
pythontech 0:5868e8752d44 516 // point to last digit to store for quotient
pythontech 0:5868e8752d44 517 quo_dig += *quo_len - 1;
pythontech 0:5868e8752d44 518
pythontech 0:5868e8752d44 519 // keep going while we have enough digits to divide
pythontech 0:5868e8752d44 520 while (*num_len > den_len) {
pythontech 0:5868e8752d44 521 mpz_dbl_dig_t quo = ((mpz_dbl_dig_t)*num_dig << DIG_SIZE) | num_dig[-1];
pythontech 0:5868e8752d44 522
pythontech 0:5868e8752d44 523 // get approximate quotient
pythontech 0:5868e8752d44 524 quo /= lead_den_digit;
pythontech 0:5868e8752d44 525
pythontech 0:5868e8752d44 526 // Multiply quo by den and subtract from num to get remainder.
pythontech 0:5868e8752d44 527 // We have different code here to handle different compile-time
pythontech 0:5868e8752d44 528 // configurations of mpz:
pythontech 0:5868e8752d44 529 //
pythontech 0:5868e8752d44 530 // 1. DIG_SIZE is stricly less than half the number of bits
pythontech 0:5868e8752d44 531 // available in mpz_dbl_dig_t. In this case we can use a
pythontech 0:5868e8752d44 532 // slightly more optimal (in time and space) routine that
pythontech 0:5868e8752d44 533 // uses the extra bits in mpz_dbl_dig_signed_t to store a
pythontech 0:5868e8752d44 534 // sign bit.
pythontech 0:5868e8752d44 535 //
pythontech 0:5868e8752d44 536 // 2. DIG_SIZE is exactly half the number of bits available in
pythontech 0:5868e8752d44 537 // mpz_dbl_dig_t. In this (common) case we need to be careful
pythontech 0:5868e8752d44 538 // not to overflow the borrow variable. And the shifting of
pythontech 0:5868e8752d44 539 // borrow needs some special logic (it's a shift right with
pythontech 0:5868e8752d44 540 // round up).
pythontech 0:5868e8752d44 541
pythontech 0:5868e8752d44 542 if (DIG_SIZE < 8 * sizeof(mpz_dbl_dig_t) / 2) {
pythontech 0:5868e8752d44 543 mpz_dbl_dig_signed_t borrow = 0;
pythontech 0:5868e8752d44 544
pythontech 0:5868e8752d44 545 for (mpz_dig_t *n = num_dig - den_len, *d = den_dig; n < num_dig; ++n, ++d) {
pythontech 0:5868e8752d44 546 borrow += (mpz_dbl_dig_t)*n - (mpz_dbl_dig_t)quo * (mpz_dbl_dig_t)*d; // will overflow if DIG_SIZE >= 8*sizeof(mpz_dbl_dig_t)/2
pythontech 0:5868e8752d44 547 *n = borrow & DIG_MASK;
pythontech 0:5868e8752d44 548 borrow >>= DIG_SIZE;
pythontech 0:5868e8752d44 549 }
pythontech 0:5868e8752d44 550 borrow += *num_dig; // will overflow if DIG_SIZE >= 8*sizeof(mpz_dbl_dig_t)/2
pythontech 0:5868e8752d44 551 *num_dig = borrow & DIG_MASK;
pythontech 0:5868e8752d44 552 borrow >>= DIG_SIZE;
pythontech 0:5868e8752d44 553
pythontech 0:5868e8752d44 554 // adjust quotient if it is too big
pythontech 0:5868e8752d44 555 for (; borrow != 0; --quo) {
pythontech 0:5868e8752d44 556 mpz_dbl_dig_t carry = 0;
pythontech 0:5868e8752d44 557 for (mpz_dig_t *n = num_dig - den_len, *d = den_dig; n < num_dig; ++n, ++d) {
pythontech 0:5868e8752d44 558 carry += (mpz_dbl_dig_t)*n + (mpz_dbl_dig_t)*d;
pythontech 0:5868e8752d44 559 *n = carry & DIG_MASK;
pythontech 0:5868e8752d44 560 carry >>= DIG_SIZE;
pythontech 0:5868e8752d44 561 }
pythontech 0:5868e8752d44 562 carry += *num_dig;
pythontech 0:5868e8752d44 563 *num_dig = carry & DIG_MASK;
pythontech 0:5868e8752d44 564 carry >>= DIG_SIZE;
pythontech 0:5868e8752d44 565
pythontech 0:5868e8752d44 566 borrow += carry;
pythontech 0:5868e8752d44 567 }
pythontech 0:5868e8752d44 568 } else { // DIG_SIZE == 8 * sizeof(mpz_dbl_dig_t) / 2
pythontech 0:5868e8752d44 569 mpz_dbl_dig_t borrow = 0;
pythontech 0:5868e8752d44 570
pythontech 0:5868e8752d44 571 for (mpz_dig_t *n = num_dig - den_len, *d = den_dig; n < num_dig; ++n, ++d) {
pythontech 0:5868e8752d44 572 mpz_dbl_dig_t x = (mpz_dbl_dig_t)quo * (mpz_dbl_dig_t)(*d);
pythontech 0:5868e8752d44 573 if (x >= *n || *n - x <= borrow) {
pythontech 0:5868e8752d44 574 borrow += (mpz_dbl_dig_t)x - (mpz_dbl_dig_t)*n;
pythontech 0:5868e8752d44 575 *n = (-borrow) & DIG_MASK;
pythontech 0:5868e8752d44 576 borrow = (borrow >> DIG_SIZE) + ((borrow & DIG_MASK) == 0 ? 0 : 1); // shift-right with round-up
pythontech 0:5868e8752d44 577 } else {
pythontech 0:5868e8752d44 578 *n = ((mpz_dbl_dig_t)*n - (mpz_dbl_dig_t)x - (mpz_dbl_dig_t)borrow) & DIG_MASK;
pythontech 0:5868e8752d44 579 borrow = 0;
pythontech 0:5868e8752d44 580 }
pythontech 0:5868e8752d44 581 }
pythontech 0:5868e8752d44 582 if (borrow >= *num_dig) {
pythontech 0:5868e8752d44 583 borrow -= (mpz_dbl_dig_t)*num_dig;
pythontech 0:5868e8752d44 584 *num_dig = (-borrow) & DIG_MASK;
pythontech 0:5868e8752d44 585 borrow = (borrow >> DIG_SIZE) + ((borrow & DIG_MASK) == 0 ? 0 : 1); // shift-right with round-up
pythontech 0:5868e8752d44 586 } else {
pythontech 0:5868e8752d44 587 *num_dig = (*num_dig - borrow) & DIG_MASK;
pythontech 0:5868e8752d44 588 borrow = 0;
pythontech 0:5868e8752d44 589 }
pythontech 0:5868e8752d44 590
pythontech 0:5868e8752d44 591 // adjust quotient if it is too big
pythontech 0:5868e8752d44 592 for (; borrow != 0; --quo) {
pythontech 0:5868e8752d44 593 mpz_dbl_dig_t carry = 0;
pythontech 0:5868e8752d44 594 for (mpz_dig_t *n = num_dig - den_len, *d = den_dig; n < num_dig; ++n, ++d) {
pythontech 0:5868e8752d44 595 carry += (mpz_dbl_dig_t)*n + (mpz_dbl_dig_t)*d;
pythontech 0:5868e8752d44 596 *n = carry & DIG_MASK;
pythontech 0:5868e8752d44 597 carry >>= DIG_SIZE;
pythontech 0:5868e8752d44 598 }
pythontech 0:5868e8752d44 599 carry += (mpz_dbl_dig_t)*num_dig;
pythontech 0:5868e8752d44 600 *num_dig = carry & DIG_MASK;
pythontech 0:5868e8752d44 601 carry >>= DIG_SIZE;
pythontech 0:5868e8752d44 602
pythontech 0:5868e8752d44 603 //assert(borrow >= carry); // enable this to check the logic
pythontech 0:5868e8752d44 604 borrow -= carry;
pythontech 0:5868e8752d44 605 }
pythontech 0:5868e8752d44 606 }
pythontech 0:5868e8752d44 607
pythontech 0:5868e8752d44 608 // store this digit of the quotient
pythontech 0:5868e8752d44 609 *quo_dig = quo & DIG_MASK;
pythontech 0:5868e8752d44 610 --quo_dig;
pythontech 0:5868e8752d44 611
pythontech 0:5868e8752d44 612 // move down to next digit of numerator
pythontech 0:5868e8752d44 613 --num_dig;
pythontech 0:5868e8752d44 614 --(*num_len);
pythontech 0:5868e8752d44 615 }
pythontech 0:5868e8752d44 616
pythontech 0:5868e8752d44 617 // unnormalise denomenator
pythontech 0:5868e8752d44 618 for (mpz_dig_t *den = den_dig + den_len - 1, carry = 0; den >= den_dig; --den) {
pythontech 0:5868e8752d44 619 mpz_dig_t d = *den;
pythontech 0:5868e8752d44 620 *den = ((d >> norm_shift) | carry) & DIG_MASK;
pythontech 0:5868e8752d44 621 carry = d << (DIG_SIZE - norm_shift);
pythontech 0:5868e8752d44 622 }
pythontech 0:5868e8752d44 623
pythontech 0:5868e8752d44 624 // unnormalise numerator (remainder now)
pythontech 0:5868e8752d44 625 for (mpz_dig_t *num = orig_num_dig + *num_len - 1, carry = 0; num >= orig_num_dig; --num) {
pythontech 0:5868e8752d44 626 mpz_dig_t n = *num;
pythontech 0:5868e8752d44 627 *num = ((n >> norm_shift) | carry) & DIG_MASK;
pythontech 0:5868e8752d44 628 carry = n << (DIG_SIZE - norm_shift);
pythontech 0:5868e8752d44 629 }
pythontech 0:5868e8752d44 630
pythontech 0:5868e8752d44 631 // strip trailing zeros
pythontech 0:5868e8752d44 632
pythontech 0:5868e8752d44 633 while (*quo_len > 0 && orig_quo_dig[*quo_len - 1] == 0) {
pythontech 0:5868e8752d44 634 --(*quo_len);
pythontech 0:5868e8752d44 635 }
pythontech 0:5868e8752d44 636
pythontech 0:5868e8752d44 637 while (*num_len > 0 && orig_num_dig[*num_len - 1] == 0) {
pythontech 0:5868e8752d44 638 --(*num_len);
pythontech 0:5868e8752d44 639 }
pythontech 0:5868e8752d44 640 }
pythontech 0:5868e8752d44 641
pythontech 0:5868e8752d44 642 #define MIN_ALLOC (2)
pythontech 0:5868e8752d44 643
pythontech 0:5868e8752d44 644 STATIC const uint8_t log_base2_floor[] = {
pythontech 0:5868e8752d44 645 0,
pythontech 0:5868e8752d44 646 0, 1, 1, 2,
pythontech 0:5868e8752d44 647 2, 2, 2, 3,
pythontech 0:5868e8752d44 648 3, 3, 3, 3,
pythontech 0:5868e8752d44 649 3, 3, 3, 4,
pythontech 0:5868e8752d44 650 4, 4, 4, 4,
pythontech 0:5868e8752d44 651 4, 4, 4, 4,
pythontech 0:5868e8752d44 652 4, 4, 4, 4,
pythontech 0:5868e8752d44 653 4, 4, 4, 5
pythontech 0:5868e8752d44 654 };
pythontech 0:5868e8752d44 655
pythontech 0:5868e8752d44 656 void mpz_init_zero(mpz_t *z) {
pythontech 0:5868e8752d44 657 z->neg = 0;
pythontech 0:5868e8752d44 658 z->fixed_dig = 0;
pythontech 0:5868e8752d44 659 z->alloc = 0;
pythontech 0:5868e8752d44 660 z->len = 0;
pythontech 0:5868e8752d44 661 z->dig = NULL;
pythontech 0:5868e8752d44 662 }
pythontech 0:5868e8752d44 663
pythontech 0:5868e8752d44 664 void mpz_init_from_int(mpz_t *z, mp_int_t val) {
pythontech 0:5868e8752d44 665 mpz_init_zero(z);
pythontech 0:5868e8752d44 666 mpz_set_from_int(z, val);
pythontech 0:5868e8752d44 667 }
pythontech 0:5868e8752d44 668
pythontech 0:5868e8752d44 669 void mpz_init_fixed_from_int(mpz_t *z, mpz_dig_t *dig, mp_uint_t alloc, mp_int_t val) {
pythontech 0:5868e8752d44 670 z->neg = 0;
pythontech 0:5868e8752d44 671 z->fixed_dig = 1;
pythontech 0:5868e8752d44 672 z->alloc = alloc;
pythontech 0:5868e8752d44 673 z->len = 0;
pythontech 0:5868e8752d44 674 z->dig = dig;
pythontech 0:5868e8752d44 675 mpz_set_from_int(z, val);
pythontech 0:5868e8752d44 676 }
pythontech 0:5868e8752d44 677
pythontech 0:5868e8752d44 678 void mpz_deinit(mpz_t *z) {
pythontech 0:5868e8752d44 679 if (z != NULL && !z->fixed_dig) {
pythontech 0:5868e8752d44 680 m_del(mpz_dig_t, z->dig, z->alloc);
pythontech 0:5868e8752d44 681 }
pythontech 0:5868e8752d44 682 }
pythontech 0:5868e8752d44 683
pythontech 0:5868e8752d44 684 #if 0
pythontech 0:5868e8752d44 685 these functions are unused
pythontech 0:5868e8752d44 686
pythontech 0:5868e8752d44 687 mpz_t *mpz_zero(void) {
pythontech 0:5868e8752d44 688 mpz_t *z = m_new_obj(mpz_t);
pythontech 0:5868e8752d44 689 mpz_init_zero(z);
pythontech 0:5868e8752d44 690 return z;
pythontech 0:5868e8752d44 691 }
pythontech 0:5868e8752d44 692
pythontech 0:5868e8752d44 693 mpz_t *mpz_from_int(mp_int_t val) {
pythontech 0:5868e8752d44 694 mpz_t *z = mpz_zero();
pythontech 0:5868e8752d44 695 mpz_set_from_int(z, val);
pythontech 0:5868e8752d44 696 return z;
pythontech 0:5868e8752d44 697 }
pythontech 0:5868e8752d44 698
pythontech 0:5868e8752d44 699 mpz_t *mpz_from_ll(long long val, bool is_signed) {
pythontech 0:5868e8752d44 700 mpz_t *z = mpz_zero();
pythontech 0:5868e8752d44 701 mpz_set_from_ll(z, val, is_signed);
pythontech 0:5868e8752d44 702 return z;
pythontech 0:5868e8752d44 703 }
pythontech 0:5868e8752d44 704
pythontech 0:5868e8752d44 705 #if MICROPY_PY_BUILTINS_FLOAT
pythontech 0:5868e8752d44 706 mpz_t *mpz_from_float(mp_float_t val) {
pythontech 0:5868e8752d44 707 mpz_t *z = mpz_zero();
pythontech 0:5868e8752d44 708 mpz_set_from_float(z, val);
pythontech 0:5868e8752d44 709 return z;
pythontech 0:5868e8752d44 710 }
pythontech 0:5868e8752d44 711 #endif
pythontech 0:5868e8752d44 712
pythontech 0:5868e8752d44 713 mpz_t *mpz_from_str(const char *str, mp_uint_t len, bool neg, mp_uint_t base) {
pythontech 0:5868e8752d44 714 mpz_t *z = mpz_zero();
pythontech 0:5868e8752d44 715 mpz_set_from_str(z, str, len, neg, base);
pythontech 0:5868e8752d44 716 return z;
pythontech 0:5868e8752d44 717 }
pythontech 0:5868e8752d44 718 #endif
pythontech 0:5868e8752d44 719
pythontech 0:5868e8752d44 720 STATIC void mpz_free(mpz_t *z) {
pythontech 0:5868e8752d44 721 if (z != NULL) {
pythontech 0:5868e8752d44 722 m_del(mpz_dig_t, z->dig, z->alloc);
pythontech 0:5868e8752d44 723 m_del_obj(mpz_t, z);
pythontech 0:5868e8752d44 724 }
pythontech 0:5868e8752d44 725 }
pythontech 0:5868e8752d44 726
pythontech 0:5868e8752d44 727 STATIC void mpz_need_dig(mpz_t *z, mp_uint_t need) {
pythontech 0:5868e8752d44 728 if (need < MIN_ALLOC) {
pythontech 0:5868e8752d44 729 need = MIN_ALLOC;
pythontech 0:5868e8752d44 730 }
pythontech 0:5868e8752d44 731
pythontech 0:5868e8752d44 732 if (z->dig == NULL || z->alloc < need) {
pythontech 0:5868e8752d44 733 if (z->fixed_dig) {
pythontech 0:5868e8752d44 734 // cannot reallocate fixed buffers
pythontech 0:5868e8752d44 735 assert(0);
pythontech 0:5868e8752d44 736 return;
pythontech 0:5868e8752d44 737 }
pythontech 0:5868e8752d44 738 z->dig = m_renew(mpz_dig_t, z->dig, z->alloc, need);
pythontech 0:5868e8752d44 739 z->alloc = need;
pythontech 0:5868e8752d44 740 }
pythontech 0:5868e8752d44 741 }
pythontech 0:5868e8752d44 742
pythontech 0:5868e8752d44 743 STATIC mpz_t *mpz_clone(const mpz_t *src) {
pythontech 0:5868e8752d44 744 mpz_t *z = m_new_obj(mpz_t);
pythontech 0:5868e8752d44 745 z->neg = src->neg;
pythontech 0:5868e8752d44 746 z->fixed_dig = 0;
pythontech 0:5868e8752d44 747 z->alloc = src->alloc;
pythontech 0:5868e8752d44 748 z->len = src->len;
pythontech 0:5868e8752d44 749 if (src->dig == NULL) {
pythontech 0:5868e8752d44 750 z->dig = NULL;
pythontech 0:5868e8752d44 751 } else {
pythontech 0:5868e8752d44 752 z->dig = m_new(mpz_dig_t, z->alloc);
pythontech 0:5868e8752d44 753 memcpy(z->dig, src->dig, src->alloc * sizeof(mpz_dig_t));
pythontech 0:5868e8752d44 754 }
pythontech 0:5868e8752d44 755 return z;
pythontech 0:5868e8752d44 756 }
pythontech 0:5868e8752d44 757
pythontech 0:5868e8752d44 758 /* sets dest = src
pythontech 0:5868e8752d44 759 can have dest, src the same
pythontech 0:5868e8752d44 760 */
pythontech 0:5868e8752d44 761 void mpz_set(mpz_t *dest, const mpz_t *src) {
pythontech 0:5868e8752d44 762 mpz_need_dig(dest, src->len);
pythontech 0:5868e8752d44 763 dest->neg = src->neg;
pythontech 0:5868e8752d44 764 dest->len = src->len;
pythontech 0:5868e8752d44 765 memcpy(dest->dig, src->dig, src->len * sizeof(mpz_dig_t));
pythontech 0:5868e8752d44 766 }
pythontech 0:5868e8752d44 767
pythontech 0:5868e8752d44 768 void mpz_set_from_int(mpz_t *z, mp_int_t val) {
pythontech 0:5868e8752d44 769 if (val == 0) {
pythontech 0:5868e8752d44 770 z->len = 0;
pythontech 0:5868e8752d44 771 return;
pythontech 0:5868e8752d44 772 }
pythontech 0:5868e8752d44 773
pythontech 0:5868e8752d44 774 mpz_need_dig(z, MPZ_NUM_DIG_FOR_INT);
pythontech 0:5868e8752d44 775
pythontech 0:5868e8752d44 776 mp_uint_t uval;
pythontech 0:5868e8752d44 777 if (val < 0) {
pythontech 0:5868e8752d44 778 z->neg = 1;
pythontech 0:5868e8752d44 779 uval = -val;
pythontech 0:5868e8752d44 780 } else {
pythontech 0:5868e8752d44 781 z->neg = 0;
pythontech 0:5868e8752d44 782 uval = val;
pythontech 0:5868e8752d44 783 }
pythontech 0:5868e8752d44 784
pythontech 0:5868e8752d44 785 z->len = 0;
pythontech 0:5868e8752d44 786 while (uval > 0) {
pythontech 0:5868e8752d44 787 z->dig[z->len++] = uval & DIG_MASK;
pythontech 0:5868e8752d44 788 uval >>= DIG_SIZE;
pythontech 0:5868e8752d44 789 }
pythontech 0:5868e8752d44 790 }
pythontech 0:5868e8752d44 791
pythontech 0:5868e8752d44 792 void mpz_set_from_ll(mpz_t *z, long long val, bool is_signed) {
pythontech 0:5868e8752d44 793 mpz_need_dig(z, MPZ_NUM_DIG_FOR_LL);
pythontech 0:5868e8752d44 794
pythontech 0:5868e8752d44 795 unsigned long long uval;
pythontech 0:5868e8752d44 796 if (is_signed && val < 0) {
pythontech 0:5868e8752d44 797 z->neg = 1;
pythontech 0:5868e8752d44 798 uval = -val;
pythontech 0:5868e8752d44 799 } else {
pythontech 0:5868e8752d44 800 z->neg = 0;
pythontech 0:5868e8752d44 801 uval = val;
pythontech 0:5868e8752d44 802 }
pythontech 0:5868e8752d44 803
pythontech 0:5868e8752d44 804 z->len = 0;
pythontech 0:5868e8752d44 805 while (uval > 0) {
pythontech 0:5868e8752d44 806 z->dig[z->len++] = uval & DIG_MASK;
pythontech 0:5868e8752d44 807 uval >>= DIG_SIZE;
pythontech 0:5868e8752d44 808 }
pythontech 0:5868e8752d44 809 }
pythontech 0:5868e8752d44 810
pythontech 0:5868e8752d44 811 #if MICROPY_PY_BUILTINS_FLOAT
pythontech 0:5868e8752d44 812 void mpz_set_from_float(mpz_t *z, mp_float_t src) {
pythontech 0:5868e8752d44 813 #if MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_DOUBLE
pythontech 0:5868e8752d44 814 typedef uint64_t mp_float_int_t;
pythontech 0:5868e8752d44 815 #elif MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_FLOAT
pythontech 0:5868e8752d44 816 typedef uint32_t mp_float_int_t;
pythontech 0:5868e8752d44 817 #endif
pythontech 0:5868e8752d44 818 union {
pythontech 0:5868e8752d44 819 mp_float_t f;
pythontech 0:5868e8752d44 820 #if MP_ENDIANNESS_LITTLE
pythontech 0:5868e8752d44 821 struct { mp_float_int_t frc:MP_FLOAT_FRAC_BITS, exp:MP_FLOAT_EXP_BITS, sgn:1; } p;
pythontech 0:5868e8752d44 822 #else
pythontech 0:5868e8752d44 823 struct { mp_float_int_t sgn:1, exp:MP_FLOAT_EXP_BITS, frc:MP_FLOAT_FRAC_BITS; } p;
pythontech 0:5868e8752d44 824 #endif
pythontech 0:5868e8752d44 825 } u = {src};
pythontech 0:5868e8752d44 826
pythontech 0:5868e8752d44 827 z->neg = u.p.sgn;
pythontech 0:5868e8752d44 828 if (u.p.exp == 0) {
pythontech 0:5868e8752d44 829 // value == 0 || value < 1
pythontech 0:5868e8752d44 830 mpz_set_from_int(z, 0);
pythontech 0:5868e8752d44 831 } else if (u.p.exp == ((1 << MP_FLOAT_EXP_BITS) - 1)) {
pythontech 0:5868e8752d44 832 // u.p.frc == 0 indicates inf, else NaN
pythontech 0:5868e8752d44 833 // should be handled by caller
pythontech 0:5868e8752d44 834 mpz_set_from_int(z, 0);
pythontech 0:5868e8752d44 835 } else {
pythontech 0:5868e8752d44 836 const int adj_exp = (int)u.p.exp - MP_FLOAT_EXP_BIAS;
pythontech 0:5868e8752d44 837 if (adj_exp < 0) {
pythontech 0:5868e8752d44 838 // value < 1 , truncates to 0
pythontech 0:5868e8752d44 839 mpz_set_from_int(z, 0);
pythontech 0:5868e8752d44 840 } else if (adj_exp == 0) {
pythontech 0:5868e8752d44 841 // 1 <= value < 2 , so truncates to 1
pythontech 0:5868e8752d44 842 mpz_set_from_int(z, 1);
pythontech 0:5868e8752d44 843 } else {
pythontech 0:5868e8752d44 844 // 2 <= value
pythontech 0:5868e8752d44 845 const int dig_cnt = (adj_exp + 1 + (DIG_SIZE - 1)) / DIG_SIZE;
pythontech 0:5868e8752d44 846 const unsigned int rem = adj_exp % DIG_SIZE;
pythontech 0:5868e8752d44 847 int dig_ind, shft;
pythontech 0:5868e8752d44 848 mp_float_int_t frc = u.p.frc | ((mp_float_int_t)1 << MP_FLOAT_FRAC_BITS);
pythontech 0:5868e8752d44 849
pythontech 0:5868e8752d44 850 if (adj_exp < MP_FLOAT_FRAC_BITS) {
pythontech 0:5868e8752d44 851 shft = 0;
pythontech 0:5868e8752d44 852 dig_ind = 0;
pythontech 0:5868e8752d44 853 frc >>= MP_FLOAT_FRAC_BITS - adj_exp;
pythontech 0:5868e8752d44 854 } else {
pythontech 0:5868e8752d44 855 shft = (rem - MP_FLOAT_FRAC_BITS) % DIG_SIZE;
pythontech 0:5868e8752d44 856 dig_ind = (adj_exp - MP_FLOAT_FRAC_BITS) / DIG_SIZE;
pythontech 0:5868e8752d44 857 }
pythontech 0:5868e8752d44 858 mpz_need_dig(z, dig_cnt);
pythontech 0:5868e8752d44 859 z->len = dig_cnt;
pythontech 0:5868e8752d44 860 if (dig_ind != 0) {
pythontech 0:5868e8752d44 861 memset(z->dig, 0, dig_ind * sizeof(mpz_dig_t));
pythontech 0:5868e8752d44 862 }
pythontech 0:5868e8752d44 863 if (shft != 0) {
pythontech 0:5868e8752d44 864 z->dig[dig_ind++] = (frc << shft) & DIG_MASK;
pythontech 0:5868e8752d44 865 frc >>= DIG_SIZE - shft;
pythontech 0:5868e8752d44 866 }
pythontech 0:5868e8752d44 867 #if DIG_SIZE < (MP_FLOAT_FRAC_BITS + 1)
pythontech 0:5868e8752d44 868 while (dig_ind != dig_cnt) {
pythontech 0:5868e8752d44 869 z->dig[dig_ind++] = frc & DIG_MASK;
pythontech 0:5868e8752d44 870 frc >>= DIG_SIZE;
pythontech 0:5868e8752d44 871 }
pythontech 0:5868e8752d44 872 #else
pythontech 0:5868e8752d44 873 if (dig_ind != dig_cnt) {
pythontech 0:5868e8752d44 874 z->dig[dig_ind] = frc;
pythontech 0:5868e8752d44 875 }
pythontech 0:5868e8752d44 876 #endif
pythontech 0:5868e8752d44 877 }
pythontech 0:5868e8752d44 878 }
pythontech 0:5868e8752d44 879 }
pythontech 0:5868e8752d44 880 #endif
pythontech 0:5868e8752d44 881
pythontech 0:5868e8752d44 882 // returns number of bytes from str that were processed
pythontech 0:5868e8752d44 883 mp_uint_t mpz_set_from_str(mpz_t *z, const char *str, mp_uint_t len, bool neg, mp_uint_t base) {
pythontech 0:5868e8752d44 884 assert(base < 36);
pythontech 0:5868e8752d44 885
pythontech 0:5868e8752d44 886 const char *cur = str;
pythontech 0:5868e8752d44 887 const char *top = str + len;
pythontech 0:5868e8752d44 888
pythontech 0:5868e8752d44 889 mpz_need_dig(z, len * 8 / DIG_SIZE + 1);
pythontech 0:5868e8752d44 890
pythontech 0:5868e8752d44 891 if (neg) {
pythontech 0:5868e8752d44 892 z->neg = 1;
pythontech 0:5868e8752d44 893 } else {
pythontech 0:5868e8752d44 894 z->neg = 0;
pythontech 0:5868e8752d44 895 }
pythontech 0:5868e8752d44 896
pythontech 0:5868e8752d44 897 z->len = 0;
pythontech 0:5868e8752d44 898 for (; cur < top; ++cur) { // XXX UTF8 next char
pythontech 0:5868e8752d44 899 //mp_uint_t v = char_to_numeric(cur#); // XXX UTF8 get char
pythontech 0:5868e8752d44 900 mp_uint_t v = *cur;
pythontech 0:5868e8752d44 901 if ('0' <= v && v <= '9') {
pythontech 0:5868e8752d44 902 v -= '0';
pythontech 0:5868e8752d44 903 } else if ('A' <= v && v <= 'Z') {
pythontech 0:5868e8752d44 904 v -= 'A' - 10;
pythontech 0:5868e8752d44 905 } else if ('a' <= v && v <= 'z') {
pythontech 0:5868e8752d44 906 v -= 'a' - 10;
pythontech 0:5868e8752d44 907 } else {
pythontech 0:5868e8752d44 908 break;
pythontech 0:5868e8752d44 909 }
pythontech 0:5868e8752d44 910 if (v >= base) {
pythontech 0:5868e8752d44 911 break;
pythontech 0:5868e8752d44 912 }
pythontech 0:5868e8752d44 913 z->len = mpn_mul_dig_add_dig(z->dig, z->len, base, v);
pythontech 0:5868e8752d44 914 }
pythontech 0:5868e8752d44 915
pythontech 0:5868e8752d44 916 return cur - str;
pythontech 0:5868e8752d44 917 }
pythontech 0:5868e8752d44 918
pythontech 0:5868e8752d44 919 bool mpz_is_zero(const mpz_t *z) {
pythontech 0:5868e8752d44 920 return z->len == 0;
pythontech 0:5868e8752d44 921 }
pythontech 0:5868e8752d44 922
pythontech 0:5868e8752d44 923 #if 0
pythontech 0:5868e8752d44 924 these functions are unused
pythontech 0:5868e8752d44 925
pythontech 0:5868e8752d44 926 bool mpz_is_pos(const mpz_t *z) {
pythontech 0:5868e8752d44 927 return z->len > 0 && z->neg == 0;
pythontech 0:5868e8752d44 928 }
pythontech 0:5868e8752d44 929
pythontech 0:5868e8752d44 930 bool mpz_is_neg(const mpz_t *z) {
pythontech 0:5868e8752d44 931 return z->len > 0 && z->neg != 0;
pythontech 0:5868e8752d44 932 }
pythontech 0:5868e8752d44 933
pythontech 0:5868e8752d44 934 bool mpz_is_odd(const mpz_t *z) {
pythontech 0:5868e8752d44 935 return z->len > 0 && (z->dig[0] & 1) != 0;
pythontech 0:5868e8752d44 936 }
pythontech 0:5868e8752d44 937
pythontech 0:5868e8752d44 938 bool mpz_is_even(const mpz_t *z) {
pythontech 0:5868e8752d44 939 return z->len == 0 || (z->dig[0] & 1) == 0;
pythontech 0:5868e8752d44 940 }
pythontech 0:5868e8752d44 941 #endif
pythontech 0:5868e8752d44 942
pythontech 0:5868e8752d44 943 int mpz_cmp(const mpz_t *z1, const mpz_t *z2) {
pythontech 0:5868e8752d44 944 // to catch comparison of -0 with +0
pythontech 0:5868e8752d44 945 if (z1->len == 0 && z2->len == 0) {
pythontech 0:5868e8752d44 946 return 0;
pythontech 0:5868e8752d44 947 }
pythontech 0:5868e8752d44 948 int cmp = (int)z2->neg - (int)z1->neg;
pythontech 0:5868e8752d44 949 if (cmp != 0) {
pythontech 0:5868e8752d44 950 return cmp;
pythontech 0:5868e8752d44 951 }
pythontech 0:5868e8752d44 952 cmp = mpn_cmp(z1->dig, z1->len, z2->dig, z2->len);
pythontech 0:5868e8752d44 953 if (z1->neg != 0) {
pythontech 0:5868e8752d44 954 cmp = -cmp;
pythontech 0:5868e8752d44 955 }
pythontech 0:5868e8752d44 956 return cmp;
pythontech 0:5868e8752d44 957 }
pythontech 0:5868e8752d44 958
pythontech 0:5868e8752d44 959 #if 0
pythontech 0:5868e8752d44 960 // obsolete
pythontech 0:5868e8752d44 961 // compares mpz with an integer that fits within DIG_SIZE bits
pythontech 0:5868e8752d44 962 mp_int_t mpz_cmp_sml_int(const mpz_t *z, mp_int_t sml_int) {
pythontech 0:5868e8752d44 963 mp_int_t cmp;
pythontech 0:5868e8752d44 964 if (z->neg == 0) {
pythontech 0:5868e8752d44 965 if (sml_int < 0) return 1;
pythontech 0:5868e8752d44 966 if (sml_int == 0) {
pythontech 0:5868e8752d44 967 if (z->len == 0) return 0;
pythontech 0:5868e8752d44 968 return 1;
pythontech 0:5868e8752d44 969 }
pythontech 0:5868e8752d44 970 if (z->len == 0) return -1;
pythontech 0:5868e8752d44 971 assert(sml_int < (1 << DIG_SIZE));
pythontech 0:5868e8752d44 972 if (z->len != 1) return 1;
pythontech 0:5868e8752d44 973 cmp = z->dig[0] - sml_int;
pythontech 0:5868e8752d44 974 } else {
pythontech 0:5868e8752d44 975 if (sml_int > 0) return -1;
pythontech 0:5868e8752d44 976 if (sml_int == 0) {
pythontech 0:5868e8752d44 977 if (z->len == 0) return 0;
pythontech 0:5868e8752d44 978 return -1;
pythontech 0:5868e8752d44 979 }
pythontech 0:5868e8752d44 980 if (z->len == 0) return 1;
pythontech 0:5868e8752d44 981 assert(sml_int > -(1 << DIG_SIZE));
pythontech 0:5868e8752d44 982 if (z->len != 1) return -1;
pythontech 0:5868e8752d44 983 cmp = -z->dig[0] - sml_int;
pythontech 0:5868e8752d44 984 }
pythontech 0:5868e8752d44 985 if (cmp < 0) return -1;
pythontech 0:5868e8752d44 986 if (cmp > 0) return 1;
pythontech 0:5868e8752d44 987 return 0;
pythontech 0:5868e8752d44 988 }
pythontech 0:5868e8752d44 989 #endif
pythontech 0:5868e8752d44 990
pythontech 0:5868e8752d44 991 #if 0
pythontech 0:5868e8752d44 992 these functions are unused
pythontech 0:5868e8752d44 993
pythontech 0:5868e8752d44 994 /* returns abs(z)
pythontech 0:5868e8752d44 995 */
pythontech 0:5868e8752d44 996 mpz_t *mpz_abs(const mpz_t *z) {
pythontech 0:5868e8752d44 997 mpz_t *z2 = mpz_clone(z);
pythontech 0:5868e8752d44 998 z2->neg = 0;
pythontech 0:5868e8752d44 999 return z2;
pythontech 0:5868e8752d44 1000 }
pythontech 0:5868e8752d44 1001
pythontech 0:5868e8752d44 1002 /* returns -z
pythontech 0:5868e8752d44 1003 */
pythontech 0:5868e8752d44 1004 mpz_t *mpz_neg(const mpz_t *z) {
pythontech 0:5868e8752d44 1005 mpz_t *z2 = mpz_clone(z);
pythontech 0:5868e8752d44 1006 z2->neg = 1 - z2->neg;
pythontech 0:5868e8752d44 1007 return z2;
pythontech 0:5868e8752d44 1008 }
pythontech 0:5868e8752d44 1009
pythontech 0:5868e8752d44 1010 /* returns lhs + rhs
pythontech 0:5868e8752d44 1011 can have lhs, rhs the same
pythontech 0:5868e8752d44 1012 */
pythontech 0:5868e8752d44 1013 mpz_t *mpz_add(const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1014 mpz_t *z = mpz_zero();
pythontech 0:5868e8752d44 1015 mpz_add_inpl(z, lhs, rhs);
pythontech 0:5868e8752d44 1016 return z;
pythontech 0:5868e8752d44 1017 }
pythontech 0:5868e8752d44 1018
pythontech 0:5868e8752d44 1019 /* returns lhs - rhs
pythontech 0:5868e8752d44 1020 can have lhs, rhs the same
pythontech 0:5868e8752d44 1021 */
pythontech 0:5868e8752d44 1022 mpz_t *mpz_sub(const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1023 mpz_t *z = mpz_zero();
pythontech 0:5868e8752d44 1024 mpz_sub_inpl(z, lhs, rhs);
pythontech 0:5868e8752d44 1025 return z;
pythontech 0:5868e8752d44 1026 }
pythontech 0:5868e8752d44 1027
pythontech 0:5868e8752d44 1028 /* returns lhs * rhs
pythontech 0:5868e8752d44 1029 can have lhs, rhs the same
pythontech 0:5868e8752d44 1030 */
pythontech 0:5868e8752d44 1031 mpz_t *mpz_mul(const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1032 mpz_t *z = mpz_zero();
pythontech 0:5868e8752d44 1033 mpz_mul_inpl(z, lhs, rhs);
pythontech 0:5868e8752d44 1034 return z;
pythontech 0:5868e8752d44 1035 }
pythontech 0:5868e8752d44 1036
pythontech 0:5868e8752d44 1037 /* returns lhs ** rhs
pythontech 0:5868e8752d44 1038 can have lhs, rhs the same
pythontech 0:5868e8752d44 1039 */
pythontech 0:5868e8752d44 1040 mpz_t *mpz_pow(const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1041 mpz_t *z = mpz_zero();
pythontech 0:5868e8752d44 1042 mpz_pow_inpl(z, lhs, rhs);
pythontech 0:5868e8752d44 1043 return z;
pythontech 0:5868e8752d44 1044 }
pythontech 0:5868e8752d44 1045
pythontech 0:5868e8752d44 1046 /* computes new integers in quo and rem such that:
pythontech 0:5868e8752d44 1047 quo * rhs + rem = lhs
pythontech 0:5868e8752d44 1048 0 <= rem < rhs
pythontech 0:5868e8752d44 1049 can have lhs, rhs the same
pythontech 0:5868e8752d44 1050 */
pythontech 0:5868e8752d44 1051 void mpz_divmod(const mpz_t *lhs, const mpz_t *rhs, mpz_t **quo, mpz_t **rem) {
pythontech 0:5868e8752d44 1052 *quo = mpz_zero();
pythontech 0:5868e8752d44 1053 *rem = mpz_zero();
pythontech 0:5868e8752d44 1054 mpz_divmod_inpl(*quo, *rem, lhs, rhs);
pythontech 0:5868e8752d44 1055 }
pythontech 0:5868e8752d44 1056 #endif
pythontech 0:5868e8752d44 1057
pythontech 0:5868e8752d44 1058 /* computes dest = abs(z)
pythontech 0:5868e8752d44 1059 can have dest, z the same
pythontech 0:5868e8752d44 1060 */
pythontech 0:5868e8752d44 1061 void mpz_abs_inpl(mpz_t *dest, const mpz_t *z) {
pythontech 0:5868e8752d44 1062 if (dest != z) {
pythontech 0:5868e8752d44 1063 mpz_set(dest, z);
pythontech 0:5868e8752d44 1064 }
pythontech 0:5868e8752d44 1065 dest->neg = 0;
pythontech 0:5868e8752d44 1066 }
pythontech 0:5868e8752d44 1067
pythontech 0:5868e8752d44 1068 /* computes dest = -z
pythontech 0:5868e8752d44 1069 can have dest, z the same
pythontech 0:5868e8752d44 1070 */
pythontech 0:5868e8752d44 1071 void mpz_neg_inpl(mpz_t *dest, const mpz_t *z) {
pythontech 0:5868e8752d44 1072 if (dest != z) {
pythontech 0:5868e8752d44 1073 mpz_set(dest, z);
pythontech 0:5868e8752d44 1074 }
pythontech 0:5868e8752d44 1075 dest->neg = 1 - dest->neg;
pythontech 0:5868e8752d44 1076 }
pythontech 0:5868e8752d44 1077
pythontech 0:5868e8752d44 1078 /* computes dest = ~z (= -z - 1)
pythontech 0:5868e8752d44 1079 can have dest, z the same
pythontech 0:5868e8752d44 1080 */
pythontech 0:5868e8752d44 1081 void mpz_not_inpl(mpz_t *dest, const mpz_t *z) {
pythontech 0:5868e8752d44 1082 if (dest != z) {
pythontech 0:5868e8752d44 1083 mpz_set(dest, z);
pythontech 0:5868e8752d44 1084 }
pythontech 0:5868e8752d44 1085 if (dest->len == 0) {
pythontech 0:5868e8752d44 1086 mpz_need_dig(dest, 1);
pythontech 0:5868e8752d44 1087 dest->dig[0] = 1;
pythontech 0:5868e8752d44 1088 dest->len = 1;
pythontech 0:5868e8752d44 1089 dest->neg = 1;
pythontech 0:5868e8752d44 1090 } else if (dest->neg) {
pythontech 0:5868e8752d44 1091 dest->neg = 0;
pythontech 0:5868e8752d44 1092 mpz_dig_t k = 1;
pythontech 0:5868e8752d44 1093 dest->len = mpn_sub(dest->dig, dest->dig, dest->len, &k, 1);
pythontech 0:5868e8752d44 1094 } else {
pythontech 0:5868e8752d44 1095 mpz_need_dig(dest, dest->len + 1);
pythontech 0:5868e8752d44 1096 mpz_dig_t k = 1;
pythontech 0:5868e8752d44 1097 dest->len = mpn_add(dest->dig, dest->dig, dest->len, &k, 1);
pythontech 0:5868e8752d44 1098 dest->neg = 1;
pythontech 0:5868e8752d44 1099 }
pythontech 0:5868e8752d44 1100 }
pythontech 0:5868e8752d44 1101
pythontech 0:5868e8752d44 1102 /* computes dest = lhs << rhs
pythontech 0:5868e8752d44 1103 can have dest, lhs the same
pythontech 0:5868e8752d44 1104 */
pythontech 0:5868e8752d44 1105 void mpz_shl_inpl(mpz_t *dest, const mpz_t *lhs, mp_uint_t rhs) {
pythontech 0:5868e8752d44 1106 if (lhs->len == 0 || rhs == 0) {
pythontech 0:5868e8752d44 1107 mpz_set(dest, lhs);
pythontech 0:5868e8752d44 1108 } else {
pythontech 0:5868e8752d44 1109 mpz_need_dig(dest, lhs->len + (rhs + DIG_SIZE - 1) / DIG_SIZE);
pythontech 0:5868e8752d44 1110 dest->len = mpn_shl(dest->dig, lhs->dig, lhs->len, rhs);
pythontech 0:5868e8752d44 1111 dest->neg = lhs->neg;
pythontech 0:5868e8752d44 1112 }
pythontech 0:5868e8752d44 1113 }
pythontech 0:5868e8752d44 1114
pythontech 0:5868e8752d44 1115 /* computes dest = lhs >> rhs
pythontech 0:5868e8752d44 1116 can have dest, lhs the same
pythontech 0:5868e8752d44 1117 */
pythontech 0:5868e8752d44 1118 void mpz_shr_inpl(mpz_t *dest, const mpz_t *lhs, mp_uint_t rhs) {
pythontech 0:5868e8752d44 1119 if (lhs->len == 0 || rhs == 0) {
pythontech 0:5868e8752d44 1120 mpz_set(dest, lhs);
pythontech 0:5868e8752d44 1121 } else {
pythontech 0:5868e8752d44 1122 mpz_need_dig(dest, lhs->len);
pythontech 0:5868e8752d44 1123 dest->len = mpn_shr(dest->dig, lhs->dig, lhs->len, rhs);
pythontech 0:5868e8752d44 1124 dest->neg = lhs->neg;
pythontech 0:5868e8752d44 1125 if (dest->neg) {
pythontech 0:5868e8752d44 1126 // arithmetic shift right, rounding to negative infinity
pythontech 0:5868e8752d44 1127 mp_uint_t n_whole = rhs / DIG_SIZE;
pythontech 0:5868e8752d44 1128 mp_uint_t n_part = rhs % DIG_SIZE;
pythontech 0:5868e8752d44 1129 mpz_dig_t round_up = 0;
pythontech 0:5868e8752d44 1130 for (mp_uint_t i = 0; i < lhs->len && i < n_whole; i++) {
pythontech 0:5868e8752d44 1131 if (lhs->dig[i] != 0) {
pythontech 0:5868e8752d44 1132 round_up = 1;
pythontech 0:5868e8752d44 1133 break;
pythontech 0:5868e8752d44 1134 }
pythontech 0:5868e8752d44 1135 }
pythontech 0:5868e8752d44 1136 if (n_whole < lhs->len && (lhs->dig[n_whole] & ((1 << n_part) - 1)) != 0) {
pythontech 0:5868e8752d44 1137 round_up = 1;
pythontech 0:5868e8752d44 1138 }
pythontech 0:5868e8752d44 1139 if (round_up) {
pythontech 0:5868e8752d44 1140 if (dest->len == 0) {
pythontech 0:5868e8752d44 1141 // dest == 0, so need to add 1 by hand (answer will be -1)
pythontech 0:5868e8752d44 1142 dest->dig[0] = 1;
pythontech 0:5868e8752d44 1143 dest->len = 1;
pythontech 0:5868e8752d44 1144 } else {
pythontech 0:5868e8752d44 1145 // dest > 0, so can use mpn_add to add 1
pythontech 0:5868e8752d44 1146 dest->len = mpn_add(dest->dig, dest->dig, dest->len, &round_up, 1);
pythontech 0:5868e8752d44 1147 }
pythontech 0:5868e8752d44 1148 }
pythontech 0:5868e8752d44 1149 }
pythontech 0:5868e8752d44 1150 }
pythontech 0:5868e8752d44 1151 }
pythontech 0:5868e8752d44 1152
pythontech 0:5868e8752d44 1153 /* computes dest = lhs + rhs
pythontech 0:5868e8752d44 1154 can have dest, lhs, rhs the same
pythontech 0:5868e8752d44 1155 */
pythontech 0:5868e8752d44 1156 void mpz_add_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1157 if (mpn_cmp(lhs->dig, lhs->len, rhs->dig, rhs->len) < 0) {
pythontech 0:5868e8752d44 1158 const mpz_t *temp = lhs;
pythontech 0:5868e8752d44 1159 lhs = rhs;
pythontech 0:5868e8752d44 1160 rhs = temp;
pythontech 0:5868e8752d44 1161 }
pythontech 0:5868e8752d44 1162
pythontech 0:5868e8752d44 1163 if (lhs->neg == rhs->neg) {
pythontech 0:5868e8752d44 1164 mpz_need_dig(dest, lhs->len + 1);
pythontech 0:5868e8752d44 1165 dest->len = mpn_add(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len);
pythontech 0:5868e8752d44 1166 } else {
pythontech 0:5868e8752d44 1167 mpz_need_dig(dest, lhs->len);
pythontech 0:5868e8752d44 1168 dest->len = mpn_sub(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len);
pythontech 0:5868e8752d44 1169 }
pythontech 0:5868e8752d44 1170
pythontech 0:5868e8752d44 1171 dest->neg = lhs->neg;
pythontech 0:5868e8752d44 1172 }
pythontech 0:5868e8752d44 1173
pythontech 0:5868e8752d44 1174 /* computes dest = lhs - rhs
pythontech 0:5868e8752d44 1175 can have dest, lhs, rhs the same
pythontech 0:5868e8752d44 1176 */
pythontech 0:5868e8752d44 1177 void mpz_sub_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1178 bool neg = false;
pythontech 0:5868e8752d44 1179
pythontech 0:5868e8752d44 1180 if (mpn_cmp(lhs->dig, lhs->len, rhs->dig, rhs->len) < 0) {
pythontech 0:5868e8752d44 1181 const mpz_t *temp = lhs;
pythontech 0:5868e8752d44 1182 lhs = rhs;
pythontech 0:5868e8752d44 1183 rhs = temp;
pythontech 0:5868e8752d44 1184 neg = true;
pythontech 0:5868e8752d44 1185 }
pythontech 0:5868e8752d44 1186
pythontech 0:5868e8752d44 1187 if (lhs->neg != rhs->neg) {
pythontech 0:5868e8752d44 1188 mpz_need_dig(dest, lhs->len + 1);
pythontech 0:5868e8752d44 1189 dest->len = mpn_add(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len);
pythontech 0:5868e8752d44 1190 } else {
pythontech 0:5868e8752d44 1191 mpz_need_dig(dest, lhs->len);
pythontech 0:5868e8752d44 1192 dest->len = mpn_sub(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len);
pythontech 0:5868e8752d44 1193 }
pythontech 0:5868e8752d44 1194
pythontech 0:5868e8752d44 1195 if (neg) {
pythontech 0:5868e8752d44 1196 dest->neg = 1 - lhs->neg;
pythontech 0:5868e8752d44 1197 } else {
pythontech 0:5868e8752d44 1198 dest->neg = lhs->neg;
pythontech 0:5868e8752d44 1199 }
pythontech 0:5868e8752d44 1200 }
pythontech 0:5868e8752d44 1201
pythontech 0:5868e8752d44 1202 /* computes dest = lhs & rhs
pythontech 0:5868e8752d44 1203 can have dest, lhs, rhs the same
pythontech 0:5868e8752d44 1204 */
pythontech 0:5868e8752d44 1205 void mpz_and_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1206 // make sure lhs has the most digits
pythontech 0:5868e8752d44 1207 if (lhs->len < rhs->len) {
pythontech 0:5868e8752d44 1208 const mpz_t *temp = lhs;
pythontech 0:5868e8752d44 1209 lhs = rhs;
pythontech 0:5868e8752d44 1210 rhs = temp;
pythontech 0:5868e8752d44 1211 }
pythontech 0:5868e8752d44 1212
pythontech 0:5868e8752d44 1213 #if MICROPY_OPT_MPZ_BITWISE
pythontech 0:5868e8752d44 1214
pythontech 0:5868e8752d44 1215 if ((0 == lhs->neg) && (0 == rhs->neg)) {
pythontech 0:5868e8752d44 1216 mpz_need_dig(dest, lhs->len);
pythontech 0:5868e8752d44 1217 dest->len = mpn_and(dest->dig, lhs->dig, rhs->dig, rhs->len);
pythontech 0:5868e8752d44 1218 dest->neg = 0;
pythontech 0:5868e8752d44 1219 } else {
pythontech 0:5868e8752d44 1220 mpz_need_dig(dest, lhs->len + 1);
pythontech 0:5868e8752d44 1221 dest->len = mpn_and_neg(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len,
pythontech 0:5868e8752d44 1222 lhs->neg == rhs->neg, 0 != lhs->neg, 0 != rhs->neg);
pythontech 0:5868e8752d44 1223 dest->neg = lhs->neg & rhs->neg;
pythontech 0:5868e8752d44 1224 }
pythontech 0:5868e8752d44 1225
pythontech 0:5868e8752d44 1226 #else
pythontech 0:5868e8752d44 1227
pythontech 0:5868e8752d44 1228 mpz_need_dig(dest, lhs->len + (lhs->neg || rhs->neg));
pythontech 0:5868e8752d44 1229 dest->len = mpn_and_neg(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len,
pythontech 0:5868e8752d44 1230 (lhs->neg == rhs->neg) ? lhs->neg : 0, lhs->neg, rhs->neg);
pythontech 0:5868e8752d44 1231 dest->neg = lhs->neg & rhs->neg;
pythontech 0:5868e8752d44 1232
pythontech 0:5868e8752d44 1233 #endif
pythontech 0:5868e8752d44 1234 }
pythontech 0:5868e8752d44 1235
pythontech 0:5868e8752d44 1236 /* computes dest = lhs | rhs
pythontech 0:5868e8752d44 1237 can have dest, lhs, rhs the same
pythontech 0:5868e8752d44 1238 */
pythontech 0:5868e8752d44 1239 void mpz_or_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1240 // make sure lhs has the most digits
pythontech 0:5868e8752d44 1241 if (lhs->len < rhs->len) {
pythontech 0:5868e8752d44 1242 const mpz_t *temp = lhs;
pythontech 0:5868e8752d44 1243 lhs = rhs;
pythontech 0:5868e8752d44 1244 rhs = temp;
pythontech 0:5868e8752d44 1245 }
pythontech 0:5868e8752d44 1246
pythontech 0:5868e8752d44 1247 #if MICROPY_OPT_MPZ_BITWISE
pythontech 0:5868e8752d44 1248
pythontech 0:5868e8752d44 1249 if ((0 == lhs->neg) && (0 == rhs->neg)) {
pythontech 0:5868e8752d44 1250 mpz_need_dig(dest, lhs->len);
pythontech 0:5868e8752d44 1251 dest->len = mpn_or(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len);
pythontech 0:5868e8752d44 1252 dest->neg = 0;
pythontech 0:5868e8752d44 1253 } else {
pythontech 0:5868e8752d44 1254 mpz_need_dig(dest, lhs->len + 1);
pythontech 0:5868e8752d44 1255 dest->len = mpn_or_neg(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len,
pythontech 0:5868e8752d44 1256 0 != lhs->neg, 0 != rhs->neg);
pythontech 0:5868e8752d44 1257 dest->neg = 1;
pythontech 0:5868e8752d44 1258 }
pythontech 0:5868e8752d44 1259
pythontech 0:5868e8752d44 1260 #else
pythontech 0:5868e8752d44 1261
pythontech 0:5868e8752d44 1262 mpz_need_dig(dest, lhs->len + (lhs->neg || rhs->neg));
pythontech 0:5868e8752d44 1263 dest->len = mpn_or_neg(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len,
pythontech 0:5868e8752d44 1264 (lhs->neg || rhs->neg), lhs->neg, rhs->neg);
pythontech 0:5868e8752d44 1265 dest->neg = lhs->neg | rhs->neg;
pythontech 0:5868e8752d44 1266
pythontech 0:5868e8752d44 1267 #endif
pythontech 0:5868e8752d44 1268 }
pythontech 0:5868e8752d44 1269
pythontech 0:5868e8752d44 1270 /* computes dest = lhs ^ rhs
pythontech 0:5868e8752d44 1271 can have dest, lhs, rhs the same
pythontech 0:5868e8752d44 1272 */
pythontech 0:5868e8752d44 1273 void mpz_xor_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1274 // make sure lhs has the most digits
pythontech 0:5868e8752d44 1275 if (lhs->len < rhs->len) {
pythontech 0:5868e8752d44 1276 const mpz_t *temp = lhs;
pythontech 0:5868e8752d44 1277 lhs = rhs;
pythontech 0:5868e8752d44 1278 rhs = temp;
pythontech 0:5868e8752d44 1279 }
pythontech 0:5868e8752d44 1280
pythontech 0:5868e8752d44 1281 #if MICROPY_OPT_MPZ_BITWISE
pythontech 0:5868e8752d44 1282
pythontech 0:5868e8752d44 1283 if (lhs->neg == rhs->neg) {
pythontech 0:5868e8752d44 1284 mpz_need_dig(dest, lhs->len);
pythontech 0:5868e8752d44 1285 if (lhs->neg == 0) {
pythontech 0:5868e8752d44 1286 dest->len = mpn_xor(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len);
pythontech 0:5868e8752d44 1287 } else {
pythontech 0:5868e8752d44 1288 dest->len = mpn_xor_neg(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len, 0, 0, 0);
pythontech 0:5868e8752d44 1289 }
pythontech 0:5868e8752d44 1290 dest->neg = 0;
pythontech 0:5868e8752d44 1291 } else {
pythontech 0:5868e8752d44 1292 mpz_need_dig(dest, lhs->len + 1);
pythontech 0:5868e8752d44 1293 dest->len = mpn_xor_neg(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len, 1,
pythontech 0:5868e8752d44 1294 0 == lhs->neg, 0 == rhs->neg);
pythontech 0:5868e8752d44 1295 dest->neg = 1;
pythontech 0:5868e8752d44 1296 }
pythontech 0:5868e8752d44 1297
pythontech 0:5868e8752d44 1298 #else
pythontech 0:5868e8752d44 1299
pythontech 0:5868e8752d44 1300 mpz_need_dig(dest, lhs->len + (lhs->neg || rhs->neg));
pythontech 0:5868e8752d44 1301 dest->len = mpn_xor_neg(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len,
pythontech 0:5868e8752d44 1302 (lhs->neg != rhs->neg), 0 == lhs->neg, 0 == rhs->neg);
pythontech 0:5868e8752d44 1303 dest->neg = lhs->neg ^ rhs->neg;
pythontech 0:5868e8752d44 1304
pythontech 0:5868e8752d44 1305 #endif
pythontech 0:5868e8752d44 1306 }
pythontech 0:5868e8752d44 1307
pythontech 0:5868e8752d44 1308 /* computes dest = lhs * rhs
pythontech 0:5868e8752d44 1309 can have dest, lhs, rhs the same
pythontech 0:5868e8752d44 1310 */
pythontech 0:5868e8752d44 1311 void mpz_mul_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1312 if (lhs->len == 0 || rhs->len == 0) {
pythontech 0:5868e8752d44 1313 mpz_set_from_int(dest, 0);
pythontech 0:5868e8752d44 1314 return;
pythontech 0:5868e8752d44 1315 }
pythontech 0:5868e8752d44 1316
pythontech 0:5868e8752d44 1317 mpz_t *temp = NULL;
pythontech 0:5868e8752d44 1318 if (lhs == dest) {
pythontech 0:5868e8752d44 1319 lhs = temp = mpz_clone(lhs);
pythontech 0:5868e8752d44 1320 if (rhs == dest) {
pythontech 0:5868e8752d44 1321 rhs = lhs;
pythontech 0:5868e8752d44 1322 }
pythontech 0:5868e8752d44 1323 } else if (rhs == dest) {
pythontech 0:5868e8752d44 1324 rhs = temp = mpz_clone(rhs);
pythontech 0:5868e8752d44 1325 }
pythontech 0:5868e8752d44 1326
pythontech 0:5868e8752d44 1327 mpz_need_dig(dest, lhs->len + rhs->len); // min mem l+r-1, max mem l+r
pythontech 0:5868e8752d44 1328 memset(dest->dig, 0, dest->alloc * sizeof(mpz_dig_t));
pythontech 0:5868e8752d44 1329 dest->len = mpn_mul(dest->dig, lhs->dig, lhs->len, rhs->dig, rhs->len);
pythontech 0:5868e8752d44 1330
pythontech 0:5868e8752d44 1331 if (lhs->neg == rhs->neg) {
pythontech 0:5868e8752d44 1332 dest->neg = 0;
pythontech 0:5868e8752d44 1333 } else {
pythontech 0:5868e8752d44 1334 dest->neg = 1;
pythontech 0:5868e8752d44 1335 }
pythontech 0:5868e8752d44 1336
pythontech 0:5868e8752d44 1337 mpz_free(temp);
pythontech 0:5868e8752d44 1338 }
pythontech 0:5868e8752d44 1339
pythontech 0:5868e8752d44 1340 /* computes dest = lhs ** rhs
pythontech 0:5868e8752d44 1341 can have dest, lhs, rhs the same
pythontech 0:5868e8752d44 1342 */
pythontech 0:5868e8752d44 1343 void mpz_pow_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1344 if (lhs->len == 0 || rhs->neg != 0) {
pythontech 0:5868e8752d44 1345 mpz_set_from_int(dest, 0);
pythontech 0:5868e8752d44 1346 return;
pythontech 0:5868e8752d44 1347 }
pythontech 0:5868e8752d44 1348
pythontech 0:5868e8752d44 1349 if (rhs->len == 0) {
pythontech 0:5868e8752d44 1350 mpz_set_from_int(dest, 1);
pythontech 0:5868e8752d44 1351 return;
pythontech 0:5868e8752d44 1352 }
pythontech 0:5868e8752d44 1353
pythontech 0:5868e8752d44 1354 mpz_t *x = mpz_clone(lhs);
pythontech 0:5868e8752d44 1355 mpz_t *n = mpz_clone(rhs);
pythontech 0:5868e8752d44 1356
pythontech 0:5868e8752d44 1357 mpz_set_from_int(dest, 1);
pythontech 0:5868e8752d44 1358
pythontech 0:5868e8752d44 1359 while (n->len > 0) {
pythontech 0:5868e8752d44 1360 if ((n->dig[0] & 1) != 0) {
pythontech 0:5868e8752d44 1361 mpz_mul_inpl(dest, dest, x);
pythontech 0:5868e8752d44 1362 }
pythontech 0:5868e8752d44 1363 n->len = mpn_shr(n->dig, n->dig, n->len, 1);
pythontech 0:5868e8752d44 1364 if (n->len == 0) {
pythontech 0:5868e8752d44 1365 break;
pythontech 0:5868e8752d44 1366 }
pythontech 0:5868e8752d44 1367 mpz_mul_inpl(x, x, x);
pythontech 0:5868e8752d44 1368 }
pythontech 0:5868e8752d44 1369
pythontech 0:5868e8752d44 1370 mpz_free(x);
pythontech 0:5868e8752d44 1371 mpz_free(n);
pythontech 0:5868e8752d44 1372 }
pythontech 0:5868e8752d44 1373
pythontech 0:5868e8752d44 1374 #if 0
pythontech 0:5868e8752d44 1375 these functions are unused
pythontech 0:5868e8752d44 1376
pythontech 0:5868e8752d44 1377 /* computes dest = (lhs ** rhs) % mod
pythontech 0:5868e8752d44 1378 can have dest, lhs, rhs the same; mod can't be the same as dest
pythontech 0:5868e8752d44 1379 */
pythontech 0:5868e8752d44 1380 void mpz_pow3_inpl(mpz_t *dest, const mpz_t *lhs, const mpz_t *rhs, const mpz_t *mod) {
pythontech 0:5868e8752d44 1381 if (lhs->len == 0 || rhs->neg != 0) {
pythontech 0:5868e8752d44 1382 mpz_set_from_int(dest, 0);
pythontech 0:5868e8752d44 1383 return;
pythontech 0:5868e8752d44 1384 }
pythontech 0:5868e8752d44 1385
pythontech 0:5868e8752d44 1386 if (rhs->len == 0) {
pythontech 0:5868e8752d44 1387 mpz_set_from_int(dest, 1);
pythontech 0:5868e8752d44 1388 return;
pythontech 0:5868e8752d44 1389 }
pythontech 0:5868e8752d44 1390
pythontech 0:5868e8752d44 1391 mpz_t *x = mpz_clone(lhs);
pythontech 0:5868e8752d44 1392 mpz_t *n = mpz_clone(rhs);
pythontech 0:5868e8752d44 1393 mpz_t quo; mpz_init_zero(&quo);
pythontech 0:5868e8752d44 1394
pythontech 0:5868e8752d44 1395 mpz_set_from_int(dest, 1);
pythontech 0:5868e8752d44 1396
pythontech 0:5868e8752d44 1397 while (n->len > 0) {
pythontech 0:5868e8752d44 1398 if ((n->dig[0] & 1) != 0) {
pythontech 0:5868e8752d44 1399 mpz_mul_inpl(dest, dest, x);
pythontech 0:5868e8752d44 1400 mpz_divmod_inpl(&quo, dest, dest, mod);
pythontech 0:5868e8752d44 1401 }
pythontech 0:5868e8752d44 1402 n->len = mpn_shr(n->dig, n->dig, n->len, 1);
pythontech 0:5868e8752d44 1403 if (n->len == 0) {
pythontech 0:5868e8752d44 1404 break;
pythontech 0:5868e8752d44 1405 }
pythontech 0:5868e8752d44 1406 mpz_mul_inpl(x, x, x);
pythontech 0:5868e8752d44 1407 mpz_divmod_inpl(&quo, x, x, mod);
pythontech 0:5868e8752d44 1408 }
pythontech 0:5868e8752d44 1409
pythontech 0:5868e8752d44 1410 mpz_deinit(&quo);
pythontech 0:5868e8752d44 1411 mpz_free(x);
pythontech 0:5868e8752d44 1412 mpz_free(n);
pythontech 0:5868e8752d44 1413 }
pythontech 0:5868e8752d44 1414
pythontech 0:5868e8752d44 1415 /* computes gcd(z1, z2)
pythontech 0:5868e8752d44 1416 based on Knuth's modified gcd algorithm (I think?)
pythontech 0:5868e8752d44 1417 gcd(z1, z2) >= 0
pythontech 0:5868e8752d44 1418 gcd(0, 0) = 0
pythontech 0:5868e8752d44 1419 gcd(z, 0) = abs(z)
pythontech 0:5868e8752d44 1420 */
pythontech 0:5868e8752d44 1421 mpz_t *mpz_gcd(const mpz_t *z1, const mpz_t *z2) {
pythontech 0:5868e8752d44 1422 if (z1->len == 0) {
pythontech 0:5868e8752d44 1423 mpz_t *a = mpz_clone(z2);
pythontech 0:5868e8752d44 1424 a->neg = 0;
pythontech 0:5868e8752d44 1425 return a;
pythontech 0:5868e8752d44 1426 } else if (z2->len == 0) {
pythontech 0:5868e8752d44 1427 mpz_t *a = mpz_clone(z1);
pythontech 0:5868e8752d44 1428 a->neg = 0;
pythontech 0:5868e8752d44 1429 return a;
pythontech 0:5868e8752d44 1430 }
pythontech 0:5868e8752d44 1431
pythontech 0:5868e8752d44 1432 mpz_t *a = mpz_clone(z1);
pythontech 0:5868e8752d44 1433 mpz_t *b = mpz_clone(z2);
pythontech 0:5868e8752d44 1434 mpz_t c; mpz_init_zero(&c);
pythontech 0:5868e8752d44 1435 a->neg = 0;
pythontech 0:5868e8752d44 1436 b->neg = 0;
pythontech 0:5868e8752d44 1437
pythontech 0:5868e8752d44 1438 for (;;) {
pythontech 0:5868e8752d44 1439 if (mpz_cmp(a, b) < 0) {
pythontech 0:5868e8752d44 1440 if (a->len == 0) {
pythontech 0:5868e8752d44 1441 mpz_free(a);
pythontech 0:5868e8752d44 1442 mpz_deinit(&c);
pythontech 0:5868e8752d44 1443 return b;
pythontech 0:5868e8752d44 1444 }
pythontech 0:5868e8752d44 1445 mpz_t *t = a; a = b; b = t;
pythontech 0:5868e8752d44 1446 }
pythontech 0:5868e8752d44 1447 if (!(b->len >= 2 || (b->len == 1 && b->dig[0] > 1))) { // compute b > 0; could be mpz_cmp_small_int(b, 1) > 0
pythontech 0:5868e8752d44 1448 break;
pythontech 0:5868e8752d44 1449 }
pythontech 0:5868e8752d44 1450 mpz_set(&c, b);
pythontech 0:5868e8752d44 1451 do {
pythontech 0:5868e8752d44 1452 mpz_add_inpl(&c, &c, &c);
pythontech 0:5868e8752d44 1453 } while (mpz_cmp(&c, a) <= 0);
pythontech 0:5868e8752d44 1454 c.len = mpn_shr(c.dig, c.dig, c.len, 1);
pythontech 0:5868e8752d44 1455 mpz_sub_inpl(a, a, &c);
pythontech 0:5868e8752d44 1456 }
pythontech 0:5868e8752d44 1457
pythontech 0:5868e8752d44 1458 mpz_deinit(&c);
pythontech 0:5868e8752d44 1459
pythontech 0:5868e8752d44 1460 if (b->len == 1 && b->dig[0] == 1) { // compute b == 1; could be mpz_cmp_small_int(b, 1) == 0
pythontech 0:5868e8752d44 1461 mpz_free(a);
pythontech 0:5868e8752d44 1462 return b;
pythontech 0:5868e8752d44 1463 } else {
pythontech 0:5868e8752d44 1464 mpz_free(b);
pythontech 0:5868e8752d44 1465 return a;
pythontech 0:5868e8752d44 1466 }
pythontech 0:5868e8752d44 1467 }
pythontech 0:5868e8752d44 1468
pythontech 0:5868e8752d44 1469 /* computes lcm(z1, z2)
pythontech 0:5868e8752d44 1470 = abs(z1) / gcd(z1, z2) * abs(z2)
pythontech 0:5868e8752d44 1471 lcm(z1, z1) >= 0
pythontech 0:5868e8752d44 1472 lcm(0, 0) = 0
pythontech 0:5868e8752d44 1473 lcm(z, 0) = 0
pythontech 0:5868e8752d44 1474 */
pythontech 0:5868e8752d44 1475 mpz_t *mpz_lcm(const mpz_t *z1, const mpz_t *z2) {
pythontech 0:5868e8752d44 1476 if (z1->len == 0 || z2->len == 0) {
pythontech 0:5868e8752d44 1477 return mpz_zero();
pythontech 0:5868e8752d44 1478 }
pythontech 0:5868e8752d44 1479
pythontech 0:5868e8752d44 1480 mpz_t *gcd = mpz_gcd(z1, z2);
pythontech 0:5868e8752d44 1481 mpz_t *quo = mpz_zero();
pythontech 0:5868e8752d44 1482 mpz_t *rem = mpz_zero();
pythontech 0:5868e8752d44 1483 mpz_divmod_inpl(quo, rem, z1, gcd);
pythontech 0:5868e8752d44 1484 mpz_mul_inpl(rem, quo, z2);
pythontech 0:5868e8752d44 1485 mpz_free(gcd);
pythontech 0:5868e8752d44 1486 mpz_free(quo);
pythontech 0:5868e8752d44 1487 rem->neg = 0;
pythontech 0:5868e8752d44 1488 return rem;
pythontech 0:5868e8752d44 1489 }
pythontech 0:5868e8752d44 1490 #endif
pythontech 0:5868e8752d44 1491
pythontech 0:5868e8752d44 1492 /* computes new integers in quo and rem such that:
pythontech 0:5868e8752d44 1493 quo * rhs + rem = lhs
pythontech 0:5868e8752d44 1494 0 <= rem < rhs
pythontech 0:5868e8752d44 1495 can have lhs, rhs the same
pythontech 0:5868e8752d44 1496 */
pythontech 0:5868e8752d44 1497 void mpz_divmod_inpl(mpz_t *dest_quo, mpz_t *dest_rem, const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1498 if (rhs->len == 0) {
pythontech 0:5868e8752d44 1499 mpz_set_from_int(dest_quo, 0);
pythontech 0:5868e8752d44 1500 mpz_set_from_int(dest_rem, 0);
pythontech 0:5868e8752d44 1501 return;
pythontech 0:5868e8752d44 1502 }
pythontech 0:5868e8752d44 1503
pythontech 0:5868e8752d44 1504 mpz_need_dig(dest_quo, lhs->len + 1); // +1 necessary?
pythontech 0:5868e8752d44 1505 memset(dest_quo->dig, 0, (lhs->len + 1) * sizeof(mpz_dig_t));
pythontech 0:5868e8752d44 1506 dest_quo->len = 0;
pythontech 0:5868e8752d44 1507 mpz_need_dig(dest_rem, lhs->len + 1); // +1 necessary?
pythontech 0:5868e8752d44 1508 mpz_set(dest_rem, lhs);
pythontech 0:5868e8752d44 1509 //rhs->dig[rhs->len] = 0;
pythontech 0:5868e8752d44 1510 mpn_div(dest_rem->dig, &dest_rem->len, rhs->dig, rhs->len, dest_quo->dig, &dest_quo->len);
pythontech 0:5868e8752d44 1511
pythontech 0:5868e8752d44 1512 if (lhs->neg != rhs->neg) {
pythontech 0:5868e8752d44 1513 dest_quo->neg = 1;
pythontech 0:5868e8752d44 1514 }
pythontech 0:5868e8752d44 1515 }
pythontech 0:5868e8752d44 1516
pythontech 0:5868e8752d44 1517 #if 0
pythontech 0:5868e8752d44 1518 these functions are unused
pythontech 0:5868e8752d44 1519
pythontech 0:5868e8752d44 1520 /* computes floor(lhs / rhs)
pythontech 0:5868e8752d44 1521 can have lhs, rhs the same
pythontech 0:5868e8752d44 1522 */
pythontech 0:5868e8752d44 1523 mpz_t *mpz_div(const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1524 mpz_t *quo = mpz_zero();
pythontech 0:5868e8752d44 1525 mpz_t rem; mpz_init_zero(&rem);
pythontech 0:5868e8752d44 1526 mpz_divmod_inpl(quo, &rem, lhs, rhs);
pythontech 0:5868e8752d44 1527 mpz_deinit(&rem);
pythontech 0:5868e8752d44 1528 return quo;
pythontech 0:5868e8752d44 1529 }
pythontech 0:5868e8752d44 1530
pythontech 0:5868e8752d44 1531 /* computes lhs % rhs ( >= 0)
pythontech 0:5868e8752d44 1532 can have lhs, rhs the same
pythontech 0:5868e8752d44 1533 */
pythontech 0:5868e8752d44 1534 mpz_t *mpz_mod(const mpz_t *lhs, const mpz_t *rhs) {
pythontech 0:5868e8752d44 1535 mpz_t quo; mpz_init_zero(&quo);
pythontech 0:5868e8752d44 1536 mpz_t *rem = mpz_zero();
pythontech 0:5868e8752d44 1537 mpz_divmod_inpl(&quo, rem, lhs, rhs);
pythontech 0:5868e8752d44 1538 mpz_deinit(&quo);
pythontech 0:5868e8752d44 1539 return rem;
pythontech 0:5868e8752d44 1540 }
pythontech 0:5868e8752d44 1541 #endif
pythontech 0:5868e8752d44 1542
pythontech 0:5868e8752d44 1543 // must return actual int value if it fits in mp_int_t
pythontech 0:5868e8752d44 1544 mp_int_t mpz_hash(const mpz_t *z) {
pythontech 0:5868e8752d44 1545 mp_int_t val = 0;
pythontech 0:5868e8752d44 1546 mpz_dig_t *d = z->dig + z->len;
pythontech 0:5868e8752d44 1547
pythontech 0:5868e8752d44 1548 while (d-- > z->dig) {
pythontech 0:5868e8752d44 1549 val = (val << DIG_SIZE) | *d;
pythontech 0:5868e8752d44 1550 }
pythontech 0:5868e8752d44 1551
pythontech 0:5868e8752d44 1552 if (z->neg != 0) {
pythontech 0:5868e8752d44 1553 val = -val;
pythontech 0:5868e8752d44 1554 }
pythontech 0:5868e8752d44 1555
pythontech 0:5868e8752d44 1556 return val;
pythontech 0:5868e8752d44 1557 }
pythontech 0:5868e8752d44 1558
pythontech 0:5868e8752d44 1559 bool mpz_as_int_checked(const mpz_t *i, mp_int_t *value) {
pythontech 0:5868e8752d44 1560 mp_uint_t val = 0;
pythontech 0:5868e8752d44 1561 mpz_dig_t *d = i->dig + i->len;
pythontech 0:5868e8752d44 1562
pythontech 0:5868e8752d44 1563 while (d-- > i->dig) {
pythontech 0:5868e8752d44 1564 if (val > (~(WORD_MSBIT_HIGH) >> DIG_SIZE)) {
pythontech 0:5868e8752d44 1565 // will overflow
pythontech 0:5868e8752d44 1566 return false;
pythontech 0:5868e8752d44 1567 }
pythontech 0:5868e8752d44 1568 val = (val << DIG_SIZE) | *d;
pythontech 0:5868e8752d44 1569 }
pythontech 0:5868e8752d44 1570
pythontech 0:5868e8752d44 1571 if (i->neg != 0) {
pythontech 0:5868e8752d44 1572 val = -val;
pythontech 0:5868e8752d44 1573 }
pythontech 0:5868e8752d44 1574
pythontech 0:5868e8752d44 1575 *value = val;
pythontech 0:5868e8752d44 1576 return true;
pythontech 0:5868e8752d44 1577 }
pythontech 0:5868e8752d44 1578
pythontech 0:5868e8752d44 1579 bool mpz_as_uint_checked(const mpz_t *i, mp_uint_t *value) {
pythontech 0:5868e8752d44 1580 if (i->neg != 0) {
pythontech 0:5868e8752d44 1581 // can't represent signed values
pythontech 0:5868e8752d44 1582 return false;
pythontech 0:5868e8752d44 1583 }
pythontech 0:5868e8752d44 1584
pythontech 0:5868e8752d44 1585 mp_uint_t val = 0;
pythontech 0:5868e8752d44 1586 mpz_dig_t *d = i->dig + i->len;
pythontech 0:5868e8752d44 1587
pythontech 0:5868e8752d44 1588 while (d-- > i->dig) {
pythontech 0:5868e8752d44 1589 if (val > (~(WORD_MSBIT_HIGH) >> (DIG_SIZE - 1))) {
pythontech 0:5868e8752d44 1590 // will overflow
pythontech 0:5868e8752d44 1591 return false;
pythontech 0:5868e8752d44 1592 }
pythontech 0:5868e8752d44 1593 val = (val << DIG_SIZE) | *d;
pythontech 0:5868e8752d44 1594 }
pythontech 0:5868e8752d44 1595
pythontech 0:5868e8752d44 1596 *value = val;
pythontech 0:5868e8752d44 1597 return true;
pythontech 0:5868e8752d44 1598 }
pythontech 0:5868e8752d44 1599
pythontech 0:5868e8752d44 1600 // writes at most len bytes to buf (so buf should be zeroed before calling)
pythontech 0:5868e8752d44 1601 void mpz_as_bytes(const mpz_t *z, bool big_endian, mp_uint_t len, byte *buf) {
pythontech 0:5868e8752d44 1602 byte *b = buf;
pythontech 0:5868e8752d44 1603 if (big_endian) {
pythontech 0:5868e8752d44 1604 b += len;
pythontech 0:5868e8752d44 1605 }
pythontech 0:5868e8752d44 1606 mpz_dig_t *zdig = z->dig;
pythontech 0:5868e8752d44 1607 int bits = 0;
pythontech 0:5868e8752d44 1608 mpz_dbl_dig_t d = 0;
pythontech 0:5868e8752d44 1609 mpz_dbl_dig_t carry = 1;
pythontech 0:5868e8752d44 1610 for (mp_uint_t zlen = z->len; zlen > 0; --zlen) {
pythontech 0:5868e8752d44 1611 bits += DIG_SIZE;
pythontech 0:5868e8752d44 1612 d = (d << DIG_SIZE) | *zdig++;
pythontech 0:5868e8752d44 1613 for (; bits >= 8; bits -= 8, d >>= 8) {
pythontech 0:5868e8752d44 1614 mpz_dig_t val = d;
pythontech 0:5868e8752d44 1615 if (z->neg) {
pythontech 0:5868e8752d44 1616 val = (~val & 0xff) + carry;
pythontech 0:5868e8752d44 1617 carry = val >> 8;
pythontech 0:5868e8752d44 1618 }
pythontech 0:5868e8752d44 1619 if (big_endian) {
pythontech 0:5868e8752d44 1620 *--b = val;
pythontech 0:5868e8752d44 1621 if (b == buf) {
pythontech 0:5868e8752d44 1622 return;
pythontech 0:5868e8752d44 1623 }
pythontech 0:5868e8752d44 1624 } else {
pythontech 0:5868e8752d44 1625 *b++ = val;
pythontech 0:5868e8752d44 1626 if (b == buf + len) {
pythontech 0:5868e8752d44 1627 return;
pythontech 0:5868e8752d44 1628 }
pythontech 0:5868e8752d44 1629 }
pythontech 0:5868e8752d44 1630 }
pythontech 0:5868e8752d44 1631 }
pythontech 0:5868e8752d44 1632 }
pythontech 0:5868e8752d44 1633
pythontech 0:5868e8752d44 1634 #if MICROPY_PY_BUILTINS_FLOAT
pythontech 0:5868e8752d44 1635 mp_float_t mpz_as_float(const mpz_t *i) {
pythontech 0:5868e8752d44 1636 mp_float_t val = 0;
pythontech 0:5868e8752d44 1637 mpz_dig_t *d = i->dig + i->len;
pythontech 0:5868e8752d44 1638
pythontech 0:5868e8752d44 1639 while (d-- > i->dig) {
pythontech 0:5868e8752d44 1640 val = val * DIG_BASE + *d;
pythontech 0:5868e8752d44 1641 }
pythontech 0:5868e8752d44 1642
pythontech 0:5868e8752d44 1643 if (i->neg != 0) {
pythontech 0:5868e8752d44 1644 val = -val;
pythontech 0:5868e8752d44 1645 }
pythontech 0:5868e8752d44 1646
pythontech 0:5868e8752d44 1647 return val;
pythontech 0:5868e8752d44 1648 }
pythontech 0:5868e8752d44 1649 #endif
pythontech 0:5868e8752d44 1650
pythontech 0:5868e8752d44 1651 mp_uint_t mpz_as_str_size(const mpz_t *i, mp_uint_t base, const char *prefix, char comma) {
pythontech 0:5868e8752d44 1652 if (base < 2 || base > 32) {
pythontech 0:5868e8752d44 1653 return 0;
pythontech 0:5868e8752d44 1654 }
pythontech 0:5868e8752d44 1655
pythontech 0:5868e8752d44 1656 mp_uint_t num_digits = i->len * DIG_SIZE / log_base2_floor[base] + 1;
pythontech 0:5868e8752d44 1657 mp_uint_t num_commas = comma ? num_digits / 3: 0;
pythontech 0:5868e8752d44 1658 mp_uint_t prefix_len = prefix ? strlen(prefix) : 0;
pythontech 0:5868e8752d44 1659
pythontech 0:5868e8752d44 1660 return num_digits + num_commas + prefix_len + 2; // +1 for sign, +1 for null byte
pythontech 0:5868e8752d44 1661 }
pythontech 0:5868e8752d44 1662
pythontech 0:5868e8752d44 1663 #if 0
pythontech 0:5868e8752d44 1664 this function is unused
pythontech 0:5868e8752d44 1665 char *mpz_as_str(const mpz_t *i, mp_uint_t base) {
pythontech 0:5868e8752d44 1666 char *s = m_new(char, mpz_as_str_size(i, base, NULL, '\0'));
pythontech 0:5868e8752d44 1667 mpz_as_str_inpl(i, base, NULL, 'a', '\0', s);
pythontech 0:5868e8752d44 1668 return s;
pythontech 0:5868e8752d44 1669 }
pythontech 0:5868e8752d44 1670 #endif
pythontech 0:5868e8752d44 1671
pythontech 0:5868e8752d44 1672 // assumes enough space as calculated by mpz_as_str_size
pythontech 0:5868e8752d44 1673 // returns length of string, not including null byte
pythontech 0:5868e8752d44 1674 mp_uint_t mpz_as_str_inpl(const mpz_t *i, mp_uint_t base, const char *prefix, char base_char, char comma, char *str) {
pythontech 0:5868e8752d44 1675 if (str == NULL || base < 2 || base > 32) {
pythontech 0:5868e8752d44 1676 str[0] = 0;
pythontech 0:5868e8752d44 1677 return 0;
pythontech 0:5868e8752d44 1678 }
pythontech 0:5868e8752d44 1679
pythontech 0:5868e8752d44 1680 mp_uint_t ilen = i->len;
pythontech 0:5868e8752d44 1681
pythontech 0:5868e8752d44 1682 char *s = str;
pythontech 0:5868e8752d44 1683 if (ilen == 0) {
pythontech 0:5868e8752d44 1684 if (prefix) {
pythontech 0:5868e8752d44 1685 while (*prefix)
pythontech 0:5868e8752d44 1686 *s++ = *prefix++;
pythontech 0:5868e8752d44 1687 }
pythontech 0:5868e8752d44 1688 *s++ = '0';
pythontech 0:5868e8752d44 1689 *s = '\0';
pythontech 0:5868e8752d44 1690 return s - str;
pythontech 0:5868e8752d44 1691 }
pythontech 0:5868e8752d44 1692
pythontech 0:5868e8752d44 1693 // make a copy of mpz digits, so we can do the div/mod calculation
pythontech 0:5868e8752d44 1694 mpz_dig_t *dig = m_new(mpz_dig_t, ilen);
pythontech 0:5868e8752d44 1695 memcpy(dig, i->dig, ilen * sizeof(mpz_dig_t));
pythontech 0:5868e8752d44 1696
pythontech 0:5868e8752d44 1697 // convert
pythontech 0:5868e8752d44 1698 char *last_comma = str;
pythontech 0:5868e8752d44 1699 bool done;
pythontech 0:5868e8752d44 1700 do {
pythontech 0:5868e8752d44 1701 mpz_dig_t *d = dig + ilen;
pythontech 0:5868e8752d44 1702 mpz_dbl_dig_t a = 0;
pythontech 0:5868e8752d44 1703
pythontech 0:5868e8752d44 1704 // compute next remainder
pythontech 0:5868e8752d44 1705 while (--d >= dig) {
pythontech 0:5868e8752d44 1706 a = (a << DIG_SIZE) | *d;
pythontech 0:5868e8752d44 1707 *d = a / base;
pythontech 0:5868e8752d44 1708 a %= base;
pythontech 0:5868e8752d44 1709 }
pythontech 0:5868e8752d44 1710
pythontech 0:5868e8752d44 1711 // convert to character
pythontech 0:5868e8752d44 1712 a += '0';
pythontech 0:5868e8752d44 1713 if (a > '9') {
pythontech 0:5868e8752d44 1714 a += base_char - '9' - 1;
pythontech 0:5868e8752d44 1715 }
pythontech 0:5868e8752d44 1716 *s++ = a;
pythontech 0:5868e8752d44 1717
pythontech 0:5868e8752d44 1718 // check if number is zero
pythontech 0:5868e8752d44 1719 done = true;
pythontech 0:5868e8752d44 1720 for (d = dig; d < dig + ilen; ++d) {
pythontech 0:5868e8752d44 1721 if (*d != 0) {
pythontech 0:5868e8752d44 1722 done = false;
pythontech 0:5868e8752d44 1723 break;
pythontech 0:5868e8752d44 1724 }
pythontech 0:5868e8752d44 1725 }
pythontech 0:5868e8752d44 1726 if (comma && (s - last_comma) == 3) {
pythontech 0:5868e8752d44 1727 *s++ = comma;
pythontech 0:5868e8752d44 1728 last_comma = s;
pythontech 0:5868e8752d44 1729 }
pythontech 0:5868e8752d44 1730 }
pythontech 0:5868e8752d44 1731 while (!done);
pythontech 0:5868e8752d44 1732
pythontech 0:5868e8752d44 1733 // free the copy of the digits array
pythontech 0:5868e8752d44 1734 m_del(mpz_dig_t, dig, ilen);
pythontech 0:5868e8752d44 1735
pythontech 0:5868e8752d44 1736 if (prefix) {
pythontech 0:5868e8752d44 1737 const char *p = &prefix[strlen(prefix)];
pythontech 0:5868e8752d44 1738 while (p > prefix) {
pythontech 0:5868e8752d44 1739 *s++ = *--p;
pythontech 0:5868e8752d44 1740 }
pythontech 0:5868e8752d44 1741 }
pythontech 0:5868e8752d44 1742 if (i->neg != 0) {
pythontech 0:5868e8752d44 1743 *s++ = '-';
pythontech 0:5868e8752d44 1744 }
pythontech 0:5868e8752d44 1745
pythontech 0:5868e8752d44 1746 // reverse string
pythontech 0:5868e8752d44 1747 for (char *u = str, *v = s - 1; u < v; ++u, --v) {
pythontech 0:5868e8752d44 1748 char temp = *u;
pythontech 0:5868e8752d44 1749 *u = *v;
pythontech 0:5868e8752d44 1750 *v = temp;
pythontech 0:5868e8752d44 1751 }
pythontech 0:5868e8752d44 1752
pythontech 0:5868e8752d44 1753 *s = '\0'; // null termination
pythontech 0:5868e8752d44 1754
pythontech 0:5868e8752d44 1755 return s - str;
pythontech 0:5868e8752d44 1756 }
pythontech 0:5868e8752d44 1757
pythontech 0:5868e8752d44 1758 #endif // MICROPY_LONGINT_IMPL == MICROPY_LONGINT_IMPL_MPZ