LCOV - code coverage report
Current view: top level - py - mpz.c (source / functions) Hit Total Coverage
Test: unix_coverage_v1.19.1-724-gfb7d21153.info Lines: 695 695 100.0 %
Date: 2022-12-01 09:37:31 Functions: 49 49 100.0 %
Branches: 344 364 94.5 %

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

Generated by: LCOV version 1.15-5-g462f71d