diff options
Diffstat (limited to 'libraries/integer-gmp')
| -rw-r--r-- | libraries/integer-gmp/cbits/wrappers.c | 77 | ||||
| -rw-r--r-- | libraries/integer-gmp/changelog.md | 7 | ||||
| -rw-r--r-- | libraries/integer-gmp/config.mk.in (renamed from libraries/integer-gmp/gmp/config.mk.in) | 4 | ||||
| -rw-r--r-- | libraries/integer-gmp/configure.ac | 4 | ||||
| -rw-r--r-- | libraries/integer-gmp/gmp/ghc.mk | 12 | ||||
| -rw-r--r-- | libraries/integer-gmp/include/HsIntegerGmp.h.in | 3 | ||||
| -rw-r--r-- | libraries/integer-gmp/integer-gmp.cabal | 22 | ||||
| -rw-r--r-- | libraries/integer-gmp/src/GHC/Integer/GMP/Internals.hs | 4 | ||||
| -rw-r--r-- | libraries/integer-gmp/src/GHC/Integer/Type.hs | 159 |
9 files changed, 257 insertions, 35 deletions
diff --git a/libraries/integer-gmp/cbits/wrappers.c b/libraries/integer-gmp/cbits/wrappers.c index c99c0176a4..11e5179323 100644 --- a/libraries/integer-gmp/cbits/wrappers.c +++ b/libraries/integer-gmp/cbits/wrappers.c @@ -11,6 +11,7 @@ #include "HsFFI.h" #include "MachDeps.h" +#include "HsIntegerGmp.h" #include <assert.h> #include <stdbool.h> @@ -285,9 +286,9 @@ integer_gmp_mpn_gcd(mp_limb_t r[], * reconstructed). * * g must have space for exactly gn=min(xn,yn) limbs. - * s must have space for at least xn limbs. + * s must have space for at least yn limbs. * - * return value: signed 'sn' of {sp,sn} + * return value: signed 'sn' of {sp,sn} where |sn| >= 1 */ mp_size_t integer_gmp_gcdext(mp_limb_t s0[], mp_limb_t g0[], @@ -304,15 +305,25 @@ integer_gmp_gcdext(mp_limb_t s0[], mp_limb_t g0[], mpz_gcdext (g, s, NULL, x, y); + // g must be positive (0 <= gn). + // According to the docs for mpz_gcdext(), we have: + // g < min(|y|/2|s|, |x|/2|t|) + // --> g < min(|y|, |x|) + // --> gn <= min(yn, xn) + // <-> gn <= gn0 const mp_size_t gn = g[0]._mp_size; assert(0 <= gn && gn <= gn0); memset(g0, 0, gn0*sizeof(mp_limb_t)); memcpy(g0, g[0]._mp_d, gn*sizeof(mp_limb_t)); mpz_clear (g); + // According to the docs for mpz_gcdext(), we have: + // |s| < |y| / 2g + // --> |s| < |y| (note g > 0) + // --> sn <= yn const mp_size_t ssn = s[0]._mp_size; const mp_size_t sn = mp_size_abs(ssn); - assert(sn <= xn); + assert(sn <= mp_size_abs(yn)); memcpy(s0, s[0]._mp_d, sn*sizeof(mp_limb_t)); mpz_clear (s); @@ -626,7 +637,7 @@ integer_gmp_powm(mp_limb_t rp[], // result } const mpz_t b = CONST_MPZ_INIT(bp, mp_limb_zero_p(bp,bn) ? 0 : bn); - const mpz_t e = CONST_MPZ_INIT(ep, mp_limb_zero_p(ep,en) ? 0 : en); + const mpz_t e = CONST_MPZ_INIT(ep, en); const mpz_t m = CONST_MPZ_INIT(mp, mn); mpz_t r; @@ -687,6 +698,64 @@ integer_gmp_powm_word(const mp_limb_t b0, // base return integer_gmp_powm1(&b0, !!b0, &e0, !!e0, m0); } +/* version of integer_gmp_powm() based on mpz_powm_sec + * + * With GMP 5.0 or later execution time depends on size of arguments + * and size of result. + * + * 'M' must be odd and 'E' non-negative. + */ +mp_size_t +integer_gmp_powm_sec(mp_limb_t rp[], // result + const mp_limb_t bp[], const mp_size_t bn, // base + const mp_limb_t ep[], const mp_size_t en, // exponent + const mp_limb_t mp[], const mp_size_t mn) // mod +{ + assert(!mp_limb_zero_p(mp,mn)); + assert(mp[0] & 1); + + if ((mn == 1 || mn == -1) && mp[0] == 1) { + rp[0] = 0; + return 1; + } + + if (mp_limb_zero_p(ep,en)) { + rp[0] = 1; + return 1; + } + + assert(en > 0); + + const mpz_t b = CONST_MPZ_INIT(bp, mp_limb_zero_p(bp,bn) ? 0 : bn); + const mpz_t e = CONST_MPZ_INIT(ep, en); + const mpz_t m = CONST_MPZ_INIT(mp, mn); + + mpz_t r; + mpz_init (r); + +#if HAVE_SECURE_POWM == 0 + mpz_powm(r, b, e, m); +#else + mpz_powm_sec(r, b, e, m); +#endif + + const mp_size_t rn = r[0]._mp_size; + + if (rn) { + assert(0 < rn && rn <= mn); + memcpy(rp, r[0]._mp_d, rn*sizeof(mp_limb_t)); + } + + mpz_clear (r); + + if (!rn) { + rp[0] = 0; + return 1; + } + + return rn; +} + /* wrapper around mpz_invert() * diff --git a/libraries/integer-gmp/changelog.md b/libraries/integer-gmp/changelog.md index b817881191..51c84bc047 100644 --- a/libraries/integer-gmp/changelog.md +++ b/libraries/integer-gmp/changelog.md @@ -1,5 +1,12 @@ # Changelog for [`integer-gmp` package](http://hackage.haskell.org/package/integer-gmp) +## 1.0.2.0 *TBA* + + * Bundled with GHC 8.4.2 + + * Define `powModSecInteger`, a "secure" version of `powModInteger` using the + `mpz_powm_sec` function. + ## 1.0.1.0 *July 2017* * Bundled with GHC 8.2.1 diff --git a/libraries/integer-gmp/gmp/config.mk.in b/libraries/integer-gmp/config.mk.in index 93a4f5369b..b66f94c5ad 100644 --- a/libraries/integer-gmp/gmp/config.mk.in +++ b/libraries/integer-gmp/config.mk.in @@ -1,3 +1,7 @@ +# NB: This file lives in the top-level integer-gmp folder, and not in +# the gmp subfolder, because of #14972, where we MUST NOT create a +# folder named 'gmp' in dist/build/ + ifeq "$(HaveLibGmp)" "" HaveLibGmp = @HaveLibGmp@ endif diff --git a/libraries/integer-gmp/configure.ac b/libraries/integer-gmp/configure.ac index c19dbbc4a8..1ccd48e698 100644 --- a/libraries/integer-gmp/configure.ac +++ b/libraries/integer-gmp/configure.ac @@ -1,4 +1,4 @@ -AC_PREREQ(2.60) +AC_PREREQ(2.69) AC_INIT([Haskell integer (GMP)], [1.0], [libraries@haskell.org], [integer]) # Safety check: Ensure that we are in the correct source directory. @@ -106,7 +106,7 @@ AC_SUBST(GhcGmpVerMj) AC_SUBST(GhcGmpVerMi) AC_SUBST(GhcGmpVerPl) -AC_CONFIG_FILES([integer-gmp.buildinfo gmp/config.mk include/HsIntegerGmp.h]) +AC_CONFIG_FILES([integer-gmp.buildinfo config.mk include/HsIntegerGmp.h]) dnl-------------------------------------------------------------------- dnl * Generate output files diff --git a/libraries/integer-gmp/gmp/ghc.mk b/libraries/integer-gmp/gmp/ghc.mk index 8a74f765d0..2a9f3ebfc0 100644 --- a/libraries/integer-gmp/gmp/ghc.mk +++ b/libraries/integer-gmp/gmp/ghc.mk @@ -27,7 +27,6 @@ endif ifneq "$(NO_CLEAN_GMP)" "YES" $(eval $(call clean-target,gmp,,\ libraries/integer-gmp/include/ghc-gmp.h \ - libraries/integer-gmp/gmp/config.mk \ libraries/integer-gmp/gmp/libgmp.a \ libraries/integer-gmp/gmp/gmp.h \ libraries/integer-gmp/gmp/gmpbuild \ @@ -53,10 +52,10 @@ endif ifeq "$(phase)" "final" ifneq "$(CLEANING)" "YES" -# Hack. The file gmp/config.mk doesn't exist yet after running ./configure in +# Hack. The file config.mk doesn't exist yet after running ./configure in # the toplevel (ghc) directory. To let some toplevel make commands such as # sdist go through, right after ./configure, don't consider this an error. --include libraries/integer-gmp/gmp/config.mk +-include libraries/integer-gmp/dist-install/build/config.mk endif gmp_CC_OPTS += $(addprefix -I,$(GMP_INCLUDE_DIRS)) @@ -130,11 +129,8 @@ libraries/integer-gmp/gmp/libgmp.a libraries/integer-gmp/gmp/gmp.h: # Note: We must pass `TARGETPLATFORM` to the `--host` argument of GMP's # `./configure`, not `HOSTPLATFORM`: the 'host' on which GMP will # run is the 'target' platform of the compiler we're building. - cd libraries/integer-gmp/gmp; (set -o igncr 2>/dev/null) && set -o igncr; export SHELLOPTS; \ - PATH=`pwd`:$$PATH; \ - export PATH; \ - cd gmpbuild && \ - CC=$(CCX) NM=$(NM) AR=$(AR_STAGE1) ./configure \ + cd libraries/integer-gmp/gmp/gmpbuild; \ + CC=$(CCX) CXX=$(CCX) NM=$(NM) AR=$(AR_STAGE1) ./configure \ --enable-shared=no \ --host=$(TARGETPLATFORM) --build=$(BUILDPLATFORM) $(MAKE) -C libraries/integer-gmp/gmp/gmpbuild MAKEFLAGS= diff --git a/libraries/integer-gmp/include/HsIntegerGmp.h.in b/libraries/integer-gmp/include/HsIntegerGmp.h.in index 4823841881..08ff8dff5f 100644 --- a/libraries/integer-gmp/include/HsIntegerGmp.h.in +++ b/libraries/integer-gmp/include/HsIntegerGmp.h.in @@ -9,3 +9,6 @@ #define GHC_GMP_VERSION_PL @GhcGmpVerPl@ #define GHC_GMP_VERSION \ (@GhcGmpVerMj@ * 10000 + @GhcGmpVerMi@ * 100 + @GhcGmpVerPl@) + +/* Whether GMP supports mpz_powm_sec */ +#define HAVE_SECURE_POWM @HaveSecurePowm@ diff --git a/libraries/integer-gmp/integer-gmp.cabal b/libraries/integer-gmp/integer-gmp.cabal index 2f32b34627..5d2f89039c 100644 --- a/libraries/integer-gmp/integer-gmp.cabal +++ b/libraries/integer-gmp/integer-gmp.cabal @@ -1,5 +1,7 @@ +cabal-version: 2.0 name: integer-gmp -version: 1.0.1.0 +version: 1.0.2.0 + synopsis: Integer library based on GMP license: BSD3 license-file: LICENSE @@ -7,7 +9,14 @@ author: Herbert Valerio Riedel maintainer: hvr@gnu.org category: Numeric, Algebra build-type: Configure -cabal-version: >=1.10 +description: + This package provides the low-level implementation of the standard + 'Integer' type based on the + <http://gmplib.org/ GNU Multiple Precision Arithmetic Library (GMP)>. + . + This package provides access to the internal representation of + 'Integer' as well as primitive operations with no proper error + handling, and should only be used directly with the utmost care. extra-source-files: aclocal.m4 @@ -17,16 +26,19 @@ extra-source-files: config.sub configure configure.ac - gmp/config.mk.in + config.mk.in include/HsIntegerGmp.h.in install-sh integer-gmp.buildinfo.in +-- NB: Many of these tmp files no longer ever actually get plopped in +-- the root directory post Cabal 2.4, thanks to a change that causes +-- autoconf/configure to get run inside the dist directory. extra-tmp-files: autom4te.cache config.log config.status - gmp/config.mk + config.mk integer-gmp.buildinfo include/HsIntegerGmp.h @@ -46,7 +58,7 @@ library StandaloneDeriving UnboxedTuples UnliftedFFITypes - build-depends: ghc-prim + build-depends: ghc-prim ^>= 0.5.1.0 hs-source-dirs: src/ ghc-options: -this-unit-id integer-gmp -Wall cc-options: -std=c99 -Wall diff --git a/libraries/integer-gmp/src/GHC/Integer/GMP/Internals.hs b/libraries/integer-gmp/src/GHC/Integer/GMP/Internals.hs index 0d8d5720a8..6c7fccf6c3 100644 --- a/libraries/integer-gmp/src/GHC/Integer/GMP/Internals.hs +++ b/libraries/integer-gmp/src/GHC/Integer/GMP/Internals.hs @@ -48,6 +48,7 @@ module GHC.Integer.GMP.Internals , lcmInteger , sqrInteger , powModInteger + , powModSecInteger , recipModInteger -- ** Additional conversion operations to 'Integer' @@ -106,6 +107,9 @@ module GHC.Integer.GMP.Internals , shiftRBigNat , shiftLBigNat , testBitBigNat + , clearBitBigNat + , complementBitBigNat + , setBitBigNat , andBigNat , xorBigNat , popCountBigNat diff --git a/libraries/integer-gmp/src/GHC/Integer/Type.hs b/libraries/integer-gmp/src/GHC/Integer/Type.hs index d5f92b32db..3434df29c4 100644 --- a/libraries/integer-gmp/src/GHC/Integer/Type.hs +++ b/libraries/integer-gmp/src/GHC/Integer/Type.hs @@ -25,6 +25,7 @@ module GHC.Integer.Type where #include "MachDeps.h" +#include "HsIntegerGmp.h" -- Sanity check as CPP defines are implicitly 0-valued when undefined #if !(defined(SIZEOF_LONG) && defined(SIZEOF_HSWORD) \ @@ -149,6 +150,11 @@ data Integer = S# !Int# | Jn# {-# UNPACK #-} !BigNat -- ^ iff value in @]-inf, minBound::'Int'[@ range +-- NOTE: the above representation is baked into the GHCi debugger in +-- compiler/ghci/RtClosureInspect.hs. If you change it here, fixes +-- will be required over there too. Tests for this are in +-- testsuite/tests/ghci.debugger. + -- TODO: experiment with different constructor-ordering instance Eq Integer where @@ -586,15 +592,15 @@ shiftRInteger (Jn# bn) n# -- Even though the shift-amount is expressed as `Int#`, the result is -- undefined for negative shift-amounts. shiftLInteger :: Integer -> Int# -> Integer -shiftLInteger x 0# = x +shiftLInteger x 0# = x shiftLInteger (S# 0#) _ = S# 0# shiftLInteger (S# 1#) n# = bitInteger n# shiftLInteger (S# i#) n# - | isTrue# (i# >=# 0#) = bigNatToInteger (shiftLBigNat - (wordToBigNat (int2Word# i#)) n#) - | True = bigNatToNegInteger (shiftLBigNat - (wordToBigNat (int2Word# - (negateInt# i#))) n#) + | isTrue# (i# >=# 0#) = bigNatToInteger (shiftLBigNat + (wordToBigNat (int2Word# i#)) n#) + | True = bigNatToNegInteger (shiftLBigNat + (wordToBigNat (int2Word# + (negateInt# i#))) n#) shiftLInteger (Jp# bn) n# = Jp# (shiftLBigNat bn n#) shiftLInteger (Jn# bn) n# = Jn# (shiftLBigNat bn n#) {-# CONSTANT_FOLDED shiftLInteger #-} @@ -1059,7 +1065,7 @@ bitBigNat i# mbn@(MBN# mba#) <- newBigNat# (li# +# 1#) -- FIXME: do we really need to zero-init MBAs returned by 'newByteArray#'? -- clear all limbs (except for the most-significant limb) - _ <- svoid (setByteArray# mba# 0# (li# `uncheckedIShiftL#` GMP_LIMB_SHIFT#) 0#) + _ <- svoid (clearWordArray# mba# 0# li#) -- set single bit in most-significant limb _ <- svoid (writeBigNat# mbn li# (uncheckedShiftL# 1## bi#)) unsafeFreezeBigNat# mbn @@ -1090,6 +1096,67 @@ testBitNegBigNat bn i# allZ j | isTrue# (indexBigNat# bn (j -# 1#) `eqWord#` 0##) = allZ (j -# 1#) | True = False + +clearBitBigNat :: BigNat -> Int# -> BigNat +clearBitBigNat bn i# + | not (inline testBitBigNat bn i#) = bn + | isTrue# (nx# ==# 1#) = wordToBigNat (bigNatToWord bn `xor#` bitWord# bi#) + | isTrue# (li# +# 1# ==# nx#) = -- special case, operating on most-sig limb + case indexBigNat# bn li# `xor#` bitWord# bi# of + 0## -> do -- most-sig limb became zero -> result has less limbs + case fmssl bn (li# -# 1#) of + 0# -> zeroBigNat + n# -> runS $ do + mbn <- newBigNat# n# + _ <- copyWordArray bn 0# mbn 0# n# + unsafeFreezeBigNat# mbn + newlimb# -> runS $ do -- no shrinking + mbn <- newBigNat# nx# + _ <- copyWordArray bn 0# mbn 0# li# + _ <- svoid (writeBigNat# mbn li# newlimb#) + unsafeFreezeBigNat# mbn + + | True = runS $ do + mbn <- newBigNat# nx# + _ <- copyWordArray bn 0# mbn 0# nx# + let newlimb# = indexBigNat# bn li# `xor#` bitWord# bi# + _ <- svoid (writeBigNat# mbn li# newlimb#) + unsafeFreezeBigNat# mbn + + where + !(# li#, bi# #) = quotRemInt# i# GMP_LIMB_BITS# + nx# = sizeofBigNat# bn + + + +setBitBigNat :: BigNat -> Int# -> BigNat +setBitBigNat bn i# + | inline testBitBigNat bn i# = bn + | isTrue# (d# ># 0#) = runS $ do -- result BigNat will have more limbs + mbn@(MBN# mba#) <- newBigNat# (li# +# 1#) + _ <- copyWordArray bn 0# mbn 0# nx# + _ <- svoid (clearWordArray# mba# nx# (d# -# 1#)) + _ <- svoid (writeBigNat# mbn li# (bitWord# bi#)) + unsafeFreezeBigNat# mbn + + | True = runS $ do + mbn <- newBigNat# nx# + _ <- copyWordArray bn 0# mbn 0# nx# + _ <- svoid (writeBigNat# mbn li# (indexBigNat# bn li# + `or#` bitWord# bi#)) + unsafeFreezeBigNat# mbn + + where + !(# li#, bi# #) = quotRemInt# i# GMP_LIMB_BITS# + nx# = sizeofBigNat# bn + d# = li# +# 1# -# nx# + + +complementBitBigNat :: BigNat -> Int# -> BigNat +complementBitBigNat bn i# + | testBitBigNat bn i# = clearBitBigNat bn i# + | True = setBitBigNat bn i# + popCountBigNat :: BigNat -> Int# popCountBigNat bn@(BN# ba#) = word2Int# (c_mpn_popcount ba# (sizeofBigNat# bn)) @@ -1327,7 +1394,9 @@ gcdExtSBigNat x y = case runS go of (g,s) -> (# g, s #) where go = do g@(MBN# g#) <- newBigNat# gn0# - s@(MBN# s#) <- newBigNat# (absI# xn#) + -- According to https://gmplib.org/manual/Number-Theoretic-Functions.html#index-mpz_005fgcdext + -- abs(s) < abs(y) / (2 g) + s@(MBN# s#) <- newBigNat# (absI# yn#) I# ssn_# <- liftIO (integer_gmp_gcdext# s# g# x# xn# y# yn#) let ssn# = narrowGmpSize# ssn_# sn# = absI# ssn# @@ -1376,6 +1445,32 @@ powModInteger b e m = case m of b' = integerToSBigNat b e' = integerToSBigNat e +-- | \"@'powModSecInteger' /b/ /e/ /m/@\" computes base @/b/@ raised to +-- exponent @/e/@ modulo @/m/@. It is required that @/e/ >= 0@ and +-- @/m/@ is odd. +-- +-- This is a \"secure\" variant of 'powModInteger' using the +-- @mpz_powm_sec()@ function which is designed to be resilient to side +-- channel attacks and is therefore intended for cryptographic +-- applications. +-- +-- This primitive is only available when the underlying GMP library +-- supports it (GMP >= 5). Otherwise, it internally falls back to +-- @'powModInteger'@, and a warning will be emitted when used. +-- +-- @since 1.0.2.0 +{-# NOINLINE powModSecInteger #-} +powModSecInteger :: Integer -> Integer -> Integer -> Integer +powModSecInteger b e m = bigNatToInteger (powModSecSBigNat b' e' m') + where + b' = integerToSBigNat b + e' = integerToSBigNat e + m' = absSBigNat (integerToSBigNat m) + +#if HAVE_SECURE_POWM == 0 +{-# WARNING powModSecInteger "The underlying GMP library does not support a secure version of powModInteger which is side-channel resistant - you need at least GMP version 5 to support this" #-} +#endif + -- | Version of 'powModInteger' operating on 'BigNat's -- -- @since 1.0.0.0 @@ -1428,6 +1523,27 @@ foreign import ccall unsafe "integer_gmp_powm1" integer_gmp_powm1# :: ByteArray# -> GmpSize# -> ByteArray# -> GmpSize# -> GmpLimb# -> GmpLimb# +-- internal non-exported helper +powModSecSBigNat :: SBigNat -> SBigNat -> BigNat -> BigNat +powModSecSBigNat b e m@(BN# m#) = runS $ do + r@(MBN# r#) <- newBigNat# mn# + I# rn_# <- liftIO (integer_gmp_powm_sec# r# b# bn# e# en# m# mn#) + let rn# = narrowGmpSize# rn_# + case isTrue# (rn# ==# mn#) of + False -> unsafeShrinkFreezeBigNat# r rn# + True -> unsafeFreezeBigNat# r + where + !(BN# b#) = absSBigNat b + !(BN# e#) = absSBigNat e + bn# = ssizeofSBigNat# b + en# = ssizeofSBigNat# e + mn# = sizeofBigNat# m + +foreign import ccall unsafe "integer_gmp_powm_sec" + integer_gmp_powm_sec# :: MutableByteArray# RealWorld + -> ByteArray# -> GmpSize# -> ByteArray# -> GmpSize# + -> ByteArray# -> GmpSize# -> IO GmpSize + -- | \"@'recipModInteger' /x/ /m/@\" computes the inverse of @/x/@ modulo @/m/@. If -- the inverse exists, the return value @/y/@ will satisfy @0 < /y/ < @@ -1746,6 +1862,15 @@ copyWordArray# src src_ofs dst dst_ofs len dst (dst_ofs `uncheckedIShiftL#` GMP_LIMB_SHIFT#) (len `uncheckedIShiftL#` GMP_LIMB_SHIFT#) +copyWordArray :: BigNat -> Int# -> MutBigNat s -> Int# -> Int# -> S s () +copyWordArray (BN# ba#) ofs_ba# (MBN# mba#) ofs_mba# len# + = svoid (copyWordArray# ba# ofs_ba# mba# ofs_mba# len#) + +clearWordArray# :: MutableByteArray# s -> Int# -> Int# -> State# s -> State# s +clearWordArray# mba ofs len + = setByteArray# mba (ofs `uncheckedIShiftL#` GMP_LIMB_SHIFT#) + (len `uncheckedIShiftL#` GMP_LIMB_SHIFT#) 0# + -- | Version of 'normSizeofMutBigNat'#' which scans all allocated 'MutBigNat#' normSizeofMutBigNat# :: MutBigNat s -> State# s -> (# State# s, Int# #) normSizeofMutBigNat# mbn@(MBN# mba) s = normSizeofMutBigNat'# mbn sz# s' @@ -1789,13 +1914,7 @@ byteArrayToBigNat# ba# n0# where !(# baszq#, baszr# #) = quotRemInt# (sizeofByteArray# ba#) GMP_LIMB_BYTES# - n# = fmssl (n0# -# 1#) - - -- find most significant set limb, return normalized size - fmssl i# - | isTrue# (i# <# 0#) = 0# - | isTrue# (neWord# (indexWordArray# ba# i#) 0##) = i# +# 1# - | True = fmssl (i# -# 1#) + n# = fmssl (BN# ba#) (n0# -# 1#) -- | Read 'Integer' (without sign) from memory location at @/addr/@ in -- base-256 representation. @@ -1996,7 +2115,7 @@ intToSBigNat# 0# = PosBN zeroBigNat intToSBigNat# 1# = PosBN oneBigNat intToSBigNat# (-1#) = NegBN oneBigNat intToSBigNat# i# | isTrue# (i# ># 0#) = PosBN (wordToBigNat (int2Word# i#)) - | True = PosBN (wordToBigNat (int2Word# (negateInt# i#))) + | True = NegBN (wordToBigNat (int2Word# (negateInt# i#))) -- | Convert 'Integer' into 'SBigNat' integerToSBigNat :: Integer -> SBigNat @@ -2048,3 +2167,11 @@ cmpI# x# y# = (x# ># y#) -# (x# <# y#) minI# :: Int# -> Int# -> Int# minI# x# y# | isTrue# (x# <=# y#) = x# | True = y# + +-- find most-sig set limb, starting at given index +fmssl :: BigNat -> Int# -> Int# +fmssl !bn i0# = go i0# + where + go i# | isTrue# (i# <# 0#) = 0# + | isTrue# (neWord# (indexBigNat# bn i#) 0##) = i# +# 1# + | True = go (i# -# 1#) |