Wider.hs (21880B)
1 {-# LANGUAGE BangPatterns #-} 2 {-# LANGUAGE MagicHash #-} 3 {-# LANGUAGE NumericUnderscores #-} 4 {-# LANGUAGE PatternSynonyms #-} 5 {-# LANGUAGE ViewPatterns #-} 6 {-# LANGUAGE UnboxedSums #-} 7 {-# LANGUAGE UnboxedTuples #-} 8 {-# LANGUAGE UnliftedNewtypes #-} 9 10 -- | 11 -- Module: Data.Word.Wider 12 -- Copyright: (c) 2025 Jared Tobin 13 -- License: MIT 14 -- Maintainer: Jared Tobin <jared@ppad.tech> 15 -- 16 -- Wider words, consisting of four 'Limb's. 17 18 module Data.Word.Wider ( 19 -- * Four-limb words 20 Wider(..) 21 , wider 22 , to_vartime 23 , from_vartime 24 25 -- * Comparison 26 , eq_vartime 27 , cmp_vartime 28 , cmp# 29 , eq# 30 , lt 31 , lt# 32 , gt 33 , gt# 34 35 -- * Parity 36 , odd# 37 , odd 38 39 -- * Constant-time selection 40 , select 41 , select# 42 43 -- * Bit manipulation 44 , shl1 45 , shr1 46 , shl1_c 47 , shr1_c 48 , shr_limb 49 , shl_limb 50 , shl1_c# 51 , shr1_c# 52 , shr_limb# 53 , shl_limb# 54 , and 55 , and_w# 56 , or 57 , or_w# 58 , not 59 , not# 60 61 -- * Arithmetic 62 , add_o 63 , add_o# 64 , add 65 , add_w# 66 , add_mod 67 , add_mod# 68 , sub 69 , sub_b 70 , sub_b# 71 , sub_mod 72 , sub_mod# 73 , sub_mod_c# 74 , mul 75 , mul_c 76 , mul_c# 77 , sqr 78 , sqr# 79 ) where 80 81 import Control.DeepSeq 82 import Data.Bits ((.|.), (.&.), (.<<.), (.>>.)) 83 import qualified Data.Bits as B 84 import qualified Data.Choice as C 85 import Data.Word.Limb (Limb(..)) 86 import qualified Data.Word.Limb as L 87 import GHC.Exts (Word(..), Int(..), Word#, Int#) 88 import qualified GHC.Exts as Exts 89 import Prelude hiding (div, mod, or, and, not, quot, rem, recip, odd) 90 91 -- utilities ------------------------------------------------------------------ 92 93 fi :: (Integral a, Num b) => a -> b 94 fi = fromIntegral 95 {-# INLINE fi #-} 96 97 -- wider words ---------------------------------------------------------------- 98 99 pattern Limb4 100 :: Word# -> Word# -> Word# -> Word# 101 -> (# Limb, Limb, Limb, Limb #) 102 pattern Limb4 w0 w1 w2 w3 = (# Limb w0, Limb w1, Limb w2, Limb w3 #) 103 {-# COMPLETE Limb4 #-} 104 105 -- | Little-endian wider words, consisting of four 'Limbs'. 106 -- 107 -- >>> 1 :: Wider 108 -- 1 109 data Wider = Wider !(# Limb, Limb, Limb, Limb #) 110 111 instance Show Wider where 112 show = show . from_vartime 113 114 -- | Note that 'fromInteger' necessarily runs in variable time due 115 -- to conversion from the variable-size, potentially heap-allocated 116 -- 'Integer' type. 117 instance Num Wider where 118 (+) = add 119 (-) = sub 120 (*) = mul 121 abs = id 122 fromInteger = to_vartime 123 negate w = add (not w) (Wider (Limb4 1## 0## 0## 0##)) 124 signum (Wider (# l0, l1, l2, l3 #)) = 125 let !(Limb l) = l0 `L.or#` l1 `L.or#` l2 `L.or#` l3 126 !n = C.from_word_nonzero# l 127 !b = C.to_word# n 128 in Wider (Limb4 b 0## 0## 0##) 129 130 instance NFData Wider where 131 rnf (Wider a) = case a of 132 (# _, _, _, _ #) -> () 133 134 -- comparison ----------------------------------------------------------------- 135 136 eq# 137 :: (# Limb, Limb, Limb, Limb #) 138 -> (# Limb, Limb, Limb, Limb #) 139 -> C.Choice 140 eq# a b = 141 let !(Limb4 a0 a1 a2 a3) = a 142 !(Limb4 b0 b1 b2 b3) = b 143 in C.eq_wider# (# a0, a1, a2, a3 #) (# b0, b1, b2, b3 #) 144 {-# INLINE eq# #-} 145 146 -- | Compare 'Wider' words for equality in variable time. 147 -- 148 -- >>> eq_vartime 1 0 149 -- False 150 -- >>> eq_vartime 1 1 151 -- True 152 eq_vartime :: Wider -> Wider -> Bool 153 eq_vartime a b = 154 let !(Wider (# a0, a1, a2, a3 #)) = a 155 !(Wider (# b0, b1, b2, b3 #)) = b 156 in (L.eq_vartime# a0 b0) 157 && (L.eq_vartime# a1 b1) 158 && (L.eq_vartime# a2 b2) 159 && (L.eq_vartime# a3 b3) 160 161 lt# 162 :: (# Limb, Limb, Limb, Limb #) 163 -> (# Limb, Limb, Limb, Limb #) 164 -> C.Choice 165 lt# a b = 166 let !(# _, Limb bor #) = sub_b# a b 167 in C.from_word_mask# bor 168 {-# INLINE lt# #-} 169 170 -- | Constant-time less-than comparison between 'Wider' values. 171 -- 172 -- >>> import qualified Data.Choice as CT 173 -- >>> CT.decide (lt 1 2) 174 -- True 175 -- >>> CT.decide (lt 1 1) 176 -- False 177 lt :: Wider -> Wider -> C.Choice 178 lt (Wider a) (Wider b) = lt# a b 179 180 gt# 181 :: (# Limb, Limb, Limb, Limb #) 182 -> (# Limb, Limb, Limb, Limb #) 183 -> C.Choice 184 gt# a b = 185 let !(# _, Limb bor #) = sub_b# b a 186 in C.from_word_mask# bor 187 {-# INLINE gt# #-} 188 189 -- | Constant-time greater-than comparison between 'Wider' values. 190 -- 191 -- >>> import qualified Data.Choice as CT 192 -- >>> CT.decide (gt 1 2) 193 -- False 194 -- >>> CT.decide (gt 2 1) 195 -- True 196 gt :: Wider -> Wider -> C.Choice 197 gt (Wider a) (Wider b) = gt# a b 198 199 cmp# 200 :: (# Limb, Limb, Limb, Limb #) 201 -> (# Limb, Limb, Limb, Limb #) 202 -> Int# 203 cmp# (# l0, l1, l2, l3 #) (# r0, r1, r2, r3 #) = 204 let !(# w0, b0 #) = L.sub_b# r0 l0 (Limb 0##) 205 !d0 = L.or# (Limb 0##) w0 206 !(# w1, b1 #) = L.sub_b# r1 l1 b0 207 !d1 = L.or# d0 w1 208 !(# w2, b2 #) = L.sub_b# r2 l2 b1 209 !d2 = L.or# d1 w2 210 !(# w3, b3 #) = L.sub_b# r3 l3 b2 211 !d3 = L.or# d2 w3 212 !(Limb w) = L.and# b3 (Limb 2##) 213 !s = Exts.word2Int# w Exts.-# 1# 214 in (Exts.word2Int# (C.to_word# (L.nonzero# d3))) Exts.*# s 215 {-# INLINE cmp# #-} 216 217 -- | Variable-time comparison between 'Wider' words. 218 -- 219 -- The actual comparison here is performed in constant time, but we must 220 -- branch to return an 'Ordering'. 221 -- 222 -- >>> cmp_vartime 1 2 223 -- LT 224 -- >>> cmp_vartime 2 1 225 -- GT 226 -- >>> cmp_vartime 2 2 227 -- EQ 228 cmp_vartime :: Wider -> Wider -> Ordering 229 cmp_vartime (Wider a) (Wider b) = case cmp# a b of 230 1# -> GT 231 0# -> EQ 232 _ -> LT 233 {-# INLINABLE cmp_vartime #-} 234 235 -- construction / conversion -------------------------------------------------- 236 237 -- | Construct a 'Wider' word from four 'Words', provided in 238 -- little-endian order. 239 -- 240 -- >>> wider 1 0 0 0 241 -- 1 242 wider :: Word -> Word -> Word -> Word -> Wider 243 wider (W# w0) (W# w1) (W# w2) (W# w3) = Wider 244 (# Limb w0, Limb w1, Limb w2, Limb w3 #) 245 246 -- | Convert an 'Integer' to a 'Wider' word. 247 -- 248 -- >>> to_vartime 1 249 -- 1 250 to_vartime :: Integer -> Wider 251 to_vartime n = 252 let !size = B.finiteBitSize (0 :: Word) 253 !mask = fi (maxBound :: Word) :: Integer 254 !(W# w0) = fi (n .&. mask) 255 !(W# w1) = fi ((n .>>. size) .&. mask) 256 !(W# w2) = fi ((n .>>. (2 * size)) .&. mask) 257 !(W# w3) = fi ((n .>>. (3 * size)) .&. mask) 258 in Wider (# Limb w0, Limb w1, Limb w2, Limb w3 #) 259 260 -- | Convert a 'Wider' word to an 'Integer'. 261 -- 262 -- >>> from_vartime 1 263 -- 1 264 from_vartime :: Wider -> Integer 265 from_vartime (Wider (# Limb w0, Limb w1, Limb w2, Limb w3 #)) = 266 fi (W# w3) .<<. (3 * size) 267 .|. fi (W# w2) .<<. (2 * size) 268 .|. fi (W# w1) .<<. size 269 .|. fi (W# w0) 270 where 271 !size = B.finiteBitSize (0 :: Word) 272 273 -- constant-time selection----------------------------------------------------- 274 275 select# 276 :: (# Limb, Limb, Limb, Limb #) -- ^ a 277 -> (# Limb, Limb, Limb, Limb #) -- ^ b 278 -> C.Choice -- ^ c 279 -> (# Limb, Limb, Limb, Limb #) -- ^ result 280 select# a b c = 281 let !(# Limb a0, Limb a1, Limb a2, Limb a3 #) = a 282 !(# Limb b0, Limb b1, Limb b2, Limb b3 #) = b 283 !(# w0, w1, w2, w3 #) = 284 C.select_wider# (# a0, a1, a2, a3 #) (# b0, b1, b2, b3 #) c 285 in (# Limb w0, Limb w1, Limb w2, Limb w3 #) 286 {-# INLINE select# #-} 287 288 -- | Return a if c is truthy, otherwise return b. 289 -- 290 -- >>> import qualified Data.Choice as C 291 -- >>> select 0 1 (C.true# ()) 292 -- 1 293 select 294 :: Wider -- ^ a 295 -> Wider -- ^ b 296 -> C.Choice -- ^ c 297 -> Wider -- ^ result 298 select (Wider a) (Wider b) c = Wider (select# a b c) 299 300 -- bit manipulation ----------------------------------------------------------- 301 302 shr1_c# 303 :: (# Limb, Limb, Limb, Limb #) -- ^ argument 304 -> (# (# Limb, Limb, Limb, Limb #), C.Choice #) -- ^ result, carry 305 shr1_c# (# w0, w1, w2, w3 #) = 306 let !s = case B.finiteBitSize (0 :: Word) of I# m -> m Exts.-# 1# 307 !(# s3, c3 #) = (# L.shr# w3 1#, L.shl# w3 s #) 308 !r3 = L.or# s3 (Limb 0##) 309 !(# s2, c2 #) = (# L.shr# w2 1#, L.shl# w2 s #) 310 !r2 = L.or# s2 c3 311 !(# s1, c1 #) = (# L.shr# w1 1#, L.shl# w1 s #) 312 !r1 = L.or# s1 c2 313 !(# s0, c0 #) = (# L.shr# w0 1#, L.shl# w0 s #) 314 !r0 = L.or# s0 c1 315 !(Limb w) = L.shr# c0 s 316 in (# (# r0, r1, r2, r3 #), C.from_word# w #) 317 {-# INLINE shr1_c# #-} 318 319 -- | Constant-time 1-bit shift-right with carry, with a 'Choice' 320 -- indicating whether the lowest bit was set. 321 shr1_c :: Wider -> (# Wider, C.Choice #) 322 shr1_c (Wider w) = 323 let !(# r, c #) = shr1_c# w 324 in (# Wider r, c #) 325 326 -- | Constant-time 1-bit shift-right. 327 -- 328 -- >>> shr1 2 329 -- 1 330 -- >>> shr1 1 331 -- 0 332 shr1 :: Wider -> Wider 333 shr1 (Wider w) = 334 let !(# r, _ #) = shr1_c# w 335 in Wider r 336 337 shl1_c# 338 :: (# Limb, Limb, Limb, Limb #) -- ^ argument 339 -> (# (# Limb, Limb, Limb, Limb #), C.Choice #) -- ^ result, carry 340 shl1_c# (# w0, w1, w2, w3 #) = 341 let !s = case B.finiteBitSize (0 :: Word) of I# m -> m Exts.-# 1# 342 !(# s0, c0 #) = (# L.shl# w0 1#, L.shr# w0 s #) 343 !r0 = L.or# s0 (Limb 0##) 344 !(# s1, c1 #) = (# L.shl# w1 1#, L.shr# w1 s #) 345 !r1 = L.or# s1 c0 346 !(# s2, c2 #) = (# L.shl# w2 1#, L.shr# w2 s #) 347 !r2 = L.or# s2 c1 348 !(# s3, c3 #) = (# L.shl# w3 1#, L.shr# w3 s #) 349 !r3 = L.or# s3 c2 350 !(Limb w) = L.shl# c3 s 351 in (# (# r0, r1, r2, r3 #), C.from_word# w #) 352 {-# INLINE shl1_c# #-} 353 354 -- | Constant-time 1-bit shift-left with carry, with a 'Choice' indicating 355 -- whether the highest bit was set. 356 shl1_c :: Wider -> (# Wider, C.Choice #) 357 shl1_c (Wider w) = 358 let !(# r, c #) = shl1_c# w 359 in (# Wider r, c #) 360 361 -- | Constant-time 1-bit shift-left. 362 -- 363 -- >>> shl1 1 364 -- 2 365 -- >>> shl1 (2 ^ (255 :: Word)) 366 -- 0 367 shl1 :: Wider -> Wider 368 shl1 (Wider w) = 369 let !(# r, _ #) = shl1_c# w 370 in Wider r 371 372 shr_limb# 373 :: (# Limb, Limb, Limb, Limb #) 374 -> Int# 375 -> (# (# Limb, Limb, Limb, Limb #), Limb #) 376 shr_limb# (# a0, a1, a2, a3 #) rs = 377 let !size = case B.finiteBitSize (0 :: Word) of I# m -> m 378 !ls = size Exts.-# rs 379 !(# l3, c3 #) = (# L.shr# a3 rs, L.shl# a3 ls #) 380 !(# l2, c2 #) = (# L.or# (L.shr# a2 rs) c3, L.shl# a2 ls #) 381 !(# l1, c1 #) = (# L.or# (L.shr# a1 rs) c2, L.shl# a1 ls #) 382 !(# l0, c0 #) = (# L.or# (L.shr# a0 rs) c1, L.shl# a0 ls #) 383 in (# (# l0, l1, l2, l3 #), c0 #) 384 {-# INLINE shr_limb# #-} 385 386 -- | Shift right by less than the number of bits in a 'Limb' (e.g., by 387 -- a maximum of 63 bits on 64-bit architectures). The shift amount is 388 -- unchecked. 389 -- 390 -- >>> shr_limb 2 1 391 -- 1 392 shr_limb 393 :: Wider -- ^ value 394 -> Int -- ^ right-shift amount (0 < s < WORD_SIZE) 395 -> Wider -- ^ right-shifted value 396 shr_limb (Wider w) (I# s) = 397 let !(# r, _ #) = shr_limb# w s 398 in Wider r 399 400 shl_limb# 401 :: (# Limb, Limb, Limb, Limb #) 402 -> Int# 403 -> (# (# Limb, Limb, Limb, Limb #), Limb #) 404 shl_limb# (# a0, a1, a2, a3 #) ls = 405 let !size = case B.finiteBitSize (0 :: Word) of I# m -> m 406 !rs = size Exts.-# ls 407 !(# l0, c0 #) = (# L.shl# a0 ls, L.shr# a0 rs #) 408 !(# l1, c1 #) = (# L.or# (L.shl# a1 ls) c0, L.shr# a1 rs #) 409 !(# l2, c2 #) = (# L.or# (L.shl# a2 ls) c1, L.shr# a2 rs #) 410 !(# l3, c3 #) = (# L.or# (L.shl# a3 ls) c2, L.shr# a3 rs #) 411 in (# (# l0, l1, l2, l3 #), c3 #) 412 {-# INLINE shl_limb# #-} 413 414 -- | Shift left by less than the number of bits in a 'Limb' (e.g., by 415 -- a maximum of 63 bits on 64-bit architectures). The shift amount is 416 -- unchecked. 417 -- 418 -- >>> shl_limb 2 1 419 -- 1 420 -- >>> shl_limb 1 63 421 -- 9223372036854775808 422 shl_limb 423 :: Wider -- ^ value 424 -> Int -- ^ left-shift amount (0 < s < WORD_SIZE) 425 -> Wider -- ^ left-shifted value 426 shl_limb (Wider w) (I# s) = 427 let !(# r, _ #) = shl_limb# w s 428 in Wider r 429 430 and_w# 431 :: (# Limb, Limb, Limb, Limb #) 432 -> (# Limb, Limb, Limb, Limb #) 433 -> (# Limb, Limb, Limb, Limb #) 434 and_w# (# a0, a1, a2, a3 #) (# b0, b1, b2, b3 #) = 435 (# L.and# a0 b0, L.and# a1 b1, L.and# a2 b2, L.and# a3 b3 #) 436 {-# INLINE and_w# #-} 437 438 -- | Binary /and/. 439 -- 440 -- >>> and 1 1 441 -- 1 442 -- >>> and 1 0 443 -- 0 444 and 445 :: Wider -- ^ a 446 -> Wider -- ^ b 447 -> Wider -- ^ a & b 448 and (Wider a) (Wider b) = Wider (and_w# a b) 449 450 or_w# 451 :: (# Limb, Limb, Limb, Limb #) 452 -> (# Limb, Limb, Limb, Limb #) 453 -> (# Limb, Limb, Limb, Limb #) 454 or_w# (# a0, a1, a2, a3 #) (# b0, b1, b2, b3 #) = 455 (# L.or# a0 b0, L.or# a1 b1, L.or# a2 b2, L.or# a3 b3 #) 456 {-# INLINE or_w# #-} 457 458 -- | Binary /or/. 459 -- 460 -- >>> or 1 1 461 -- 1 462 -- >>> or 1 0 463 -- 1 464 or 465 :: Wider -- ^ a 466 -> Wider -- ^ b 467 -> Wider -- ^ a | b 468 or (Wider a) (Wider b) = Wider (or_w# a b) 469 470 not# 471 :: (# Limb, Limb, Limb, Limb #) 472 -> (# Limb, Limb, Limb, Limb #) 473 not# (# l0, l1, l2, l3 #) = (# L.not# l0, L.not# l1, L.not# l2, L.not# l3 #) 474 {-# INLINE not# #-} 475 476 -- | Binary /not/. 477 -- 478 -- >>> not 0 479 -- 115792089237316195423570985008687907853269984665640564039457584007913129639935 480 -- >>> not (not 0) 481 -- 0 482 not 483 :: Wider -- ^ value 484 -> Wider -- ^ not value 485 not (Wider w) = Wider (not# w) 486 487 -- addition, subtraction ------------------------------------------------------ 488 489 add_o# 490 :: (# Limb, Limb, Limb, Limb #) -- ^ augend 491 -> (# Limb, Limb, Limb, Limb #) -- ^ addend 492 -> (# (# Limb, Limb, Limb, Limb #), Limb #) -- ^ (# sum, carry bit #) 493 add_o# (# a0, a1, a2, a3 #) (# b0, b1, b2, b3 #) = 494 let !(# s0, c0 #) = L.add_o# a0 b0 495 !(# s1, c1 #) = L.add_c# a1 b1 c0 496 !(# s2, c2 #) = L.add_c# a2 b2 c1 497 !(# s3, c3 #) = L.add_c# a3 b3 c2 498 in (# (# s0, s1, s2, s3 #), c3 #) 499 {-# INLINE add_o# #-} 500 501 -- | Overflowing addition, computing 'a + b', returning the sum and a 502 -- carry bit. 503 -- 504 -- >>> add_o 1 1 505 -- (2,0) 506 -- >>> add_o 1 (2 ^ (256 :: Word) - 1) 507 -- (0,1) 508 add_o 509 :: Wider 510 -> Wider 511 -> (Wider, Word) 512 add_o (Wider a) (Wider b) = 513 let !(# s, Limb c #) = add_o# a b 514 in (Wider s, W# c) 515 516 add_w# 517 :: (# Limb, Limb, Limb, Limb #) -- ^ augend 518 -> (# Limb, Limb, Limb, Limb #) -- ^ addend 519 -> (# Limb, Limb, Limb, Limb #) -- ^ sum 520 add_w# a b = 521 let !(# c, _ #) = add_o# a b 522 in c 523 {-# INLINE add_w# #-} 524 525 -- | Wrapping addition, computing 'a + b'. 526 -- 527 -- Note that as 'Wider' is an instance of 'Num', you can use '+' to apply 528 -- this function. 529 -- 530 -- >>> add 1 (2 ^ (256 :: Word) - 1) 531 -- 0 532 add 533 :: Wider 534 -> Wider 535 -> Wider 536 add (Wider a) (Wider b) = Wider (add_w# a b) 537 {-# INLINE add #-} 538 539 add_mod# 540 :: (# Limb, Limb, Limb, Limb #) -- ^ augend 541 -> (# Limb, Limb, Limb, Limb #) -- ^ addend 542 -> (# Limb, Limb, Limb, Limb #) -- ^ modulus 543 -> (# Limb, Limb, Limb, Limb #) -- ^ sum 544 add_mod# a b m = 545 let !(# w, c #) = add_o# a b 546 in sub_mod_c# w c m m 547 {-# INLINE add_mod# #-} 548 549 -- | Modular addition. 550 -- 551 -- Assumes that the sum is less than twice the modulus; this is not 552 -- checked. 553 -- 554 -- >>> add_mod 1 1 3 555 -- 2 556 -- >>> add_mod 1 2 3 557 -- 0 558 add_mod 559 :: Wider -- ^ augend 560 -> Wider -- ^ addend 561 -> Wider -- ^ modulus 562 -> Wider -- ^ sum 563 add_mod (Wider a) (Wider b) (Wider m) = Wider (add_mod# a b m) 564 565 sub_b# 566 :: (# Limb, Limb, Limb, Limb #) -- ^ minuend 567 -> (# Limb, Limb, Limb, Limb #) -- ^ subtrahend 568 -> (# (# Limb, Limb, Limb, Limb #), Limb #) -- ^ (# diff, borrow mask #) 569 sub_b# (# a0, a1, a2, a3 #) (# b0, b1, b2, b3 #) = 570 let !(# s0, c0 #) = L.sub_b# a0 b0 (Limb 0##) 571 !(# s1, c1 #) = L.sub_b# a1 b1 c0 572 !(# s2, c2 #) = L.sub_b# a2 b2 c1 573 !(# s3, c3 #) = L.sub_b# a3 b3 c2 574 in (# (# s0, s1, s2, s3 #), c3 #) 575 {-# INLINE sub_b# #-} 576 577 -- | Borrowing subtraction, computing 'a - b' and returning the 578 -- difference with a borrow mask. 579 -- 580 -- >>> sub_b 1 1 581 -- (0,0) 582 -- >>> sub_b 0 (2 ^ (256 :: Word) - 1) 583 -- (1,18446744073709551615) 584 sub_b 585 :: Wider -- ^ minuend 586 -> Wider -- ^ subtrahend 587 -> (Wider, Word) -- ^ (difference, borrow mask) 588 sub_b (Wider l) (Wider r) = 589 let !(# d, Limb b #) = sub_b# l r 590 in (Wider d, W# b) 591 592 -- | Wrapping subtraction, computing 'a - b' and returning the 593 -- difference. 594 -- 595 -- Note that as 'Wider' is an instance of 'Num', you can use '-' to apply 596 -- this function. 597 -- 598 -- >>> sub 1 1 599 -- 0 600 -- >>> sub 0 (2 ^ (256 :: Word) - 1) 601 -- 1 602 sub 603 :: Wider -- ^ minuend 604 -> Wider -- ^ subtrahend 605 -> Wider -- ^ difference 606 sub (Wider a) (Wider b) = 607 let !(# d, _ #) = sub_b# a b 608 in Wider d 609 610 sub_mod# 611 :: (# Limb, Limb, Limb, Limb #) -- ^ minuend 612 -> (# Limb, Limb, Limb, Limb #) -- ^ subtrahend 613 -> (# Limb, Limb, Limb, Limb #) -- ^ modulus 614 -> (# Limb, Limb, Limb, Limb #) -- ^ difference 615 sub_mod# a b (# p0, p1, p2, p3 #) = 616 let !(# o, m #) = sub_b# a b 617 !ba = (# L.and# p0 m, L.and# p1 m, L.and# p2 m, L.and# p3 m #) 618 in add_w# o ba 619 {-# INLINE sub_mod# #-} 620 621 -- | Modular subtraction. Computes a - b mod m. 622 -- 623 -- Assumes that the magnitude of the difference is less than the 624 -- modulus (this is unchecked). 625 -- 626 -- >>> sub_mod 1 1 4 627 -- 0 628 -- >>> sub_mod 2 3 4 629 -- 3 630 sub_mod 631 :: Wider 632 -> Wider 633 -> Wider 634 -> Wider 635 sub_mod (Wider a) (Wider b) (Wider p) = Wider (sub_mod# a b p) 636 637 -- | Modular subtraction with carry. Computes (# a, c #) - b mod m. 638 sub_mod_c# 639 :: (# Limb, Limb, Limb, Limb #) -- ^ minuend 640 -> Limb -- ^ carry bit 641 -> (# Limb, Limb, Limb, Limb #) -- ^ subtrahend 642 -> (# Limb, Limb, Limb, Limb #) -- ^ modulus 643 -> (# Limb, Limb, Limb, Limb #) -- ^ difference 644 sub_mod_c# a c b (# p0, p1, p2, p3 #) = 645 let !(# (# o0, o1, o2, o3 #), bb #) = sub_b# a b 646 !(# _, m #) = L.sub_b# c (Limb 0##) bb 647 !ba = (# L.and# p0 m, L.and# p1 m, L.and# p2 m, L.and# p3 m #) 648 in add_w# (# o0, o1, o2, o3 #) ba 649 {-# INLINE sub_mod_c# #-} 650 651 -- multiplication ------------------------------------------------------------- 652 653 mul_c# 654 :: (# Limb, Limb, Limb, Limb #) 655 -> (# Limb, Limb, Limb, Limb #) 656 -> (# (# Limb, Limb, Limb, Limb #), (# Limb, Limb, Limb, Limb #) #) 657 mul_c# (# x0, x1, x2, x3 #) (# y0, y1, y2, y3 #) = 658 let !(# z0, c0_0 #) = L.mac# x0 y0 (Limb 0##) (Limb 0##) 659 !(# s1_0, c1_0 #) = L.mac# x0 y1 (Limb 0##) c0_0 660 !(# z1, c1_1 #) = L.mac# x1 y0 s1_0 (Limb 0##) 661 !(# s2_0, c2_0 #) = L.mac# x0 y2 (Limb 0##) c1_0 662 !(# s2_1, c2_1 #) = L.mac# x1 y1 s2_0 c1_1 663 !(# z2, c2_2 #) = L.mac# x2 y0 s2_1 (Limb 0##) 664 !(# s3_0, c3_0 #) = L.mac# x0 y3 (Limb 0##) c2_0 665 !(# s3_1, c3_1 #) = L.mac# x1 y2 s3_0 c2_1 666 !(# s3_2, c3_2 #) = L.mac# x2 y1 s3_1 c2_2 667 !(# z3, c3_3 #) = L.mac# x3 y0 s3_2 (Limb 0##) 668 !(# s4_0, c4_0 #) = L.mac# x1 y3 (Limb 0##) c3_0 669 !(# s4_1, c4_1 #) = L.mac# x2 y2 s4_0 c3_1 670 !(# s4_2, c4_2 #) = L.mac# x3 y1 s4_1 c3_2 671 !(# w4, c4_3 #) = L.add_c# s4_2 c3_3 (Limb 0##) 672 !(# s5_0, c5_0 #) = L.mac# x2 y3 (Limb 0##) c4_0 673 !(# s5_1, c5_1 #) = L.mac# x3 y2 s5_0 c4_1 674 !(# w5, c5_2 #) = L.add_c# s5_1 c4_2 (Limb 0##) 675 !(# w5f, c5_3 #) = L.add_c# w5 c4_3 (Limb 0##) 676 !(# s6_0, c6_0 #) = L.mac# x3 y3 (Limb 0##) c5_0 677 !(# w6, c6_1 #) = L.add_c# s6_0 c5_1 (Limb 0##) 678 !(# w6f, c6_2 #) = L.add_c# w6 c5_2 (Limb 0##) 679 !(# w6ff, c6_3 #) = L.add_c# w6f c5_3 (Limb 0##) 680 !(# w7, _ #) = L.add_c# c6_0 c6_1 (Limb 0##) 681 !(# w7f, _ #) = L.add_c# w7 c6_2 (Limb 0##) 682 !(# w7ff, _ #) = L.add_c# w7f c6_3 (Limb 0##) 683 in (# (# z0, z1, z2, z3 #), (# w4, w5f, w6ff, w7ff #) #) 684 {-# INLINE mul_c# #-} 685 686 -- | Widening multiplication. 687 -- 688 -- Returns the low and high 'Wider' words of the product, in that 689 -- order. 690 -- 691 -- >>> mul_c 2 3 692 -- (6,0) 693 -- >>> mul_c (2 ^ (256 :: Word) - 1) 2 694 -- (115792089237316195423570985008687907853269984665640564039457584007913129639934,1) 695 mul_c 696 :: Wider 697 -> Wider 698 -> (Wider, Wider) 699 mul_c (Wider a) (Wider b) = 700 let !(# l, h #) = mul_c# a b 701 in (Wider l, Wider h) 702 703 -- | Wrapping multiplication. 704 -- 705 -- Note that as 'Wider' is an instance of 'Num', you can use '*' to apply 706 -- this function. 707 -- 708 -- >>> mul 1 1 709 -- 1 710 -- >>> mul 1 2 711 -- 2 712 mul 713 :: Wider 714 -> Wider 715 -> Wider 716 mul (Wider a) (Wider b) = 717 let !(# l, _ #) = mul_c# a b 718 in Wider l 719 720 sqr# 721 :: (# Limb, Limb, Limb, Limb #) 722 -> (# (# Limb, Limb, Limb, Limb #), (# Limb, Limb, Limb, Limb #) #) 723 sqr# (# x0, x1, x2, x3 #) = 724 let !sh = case B.finiteBitSize (0 :: Word) of I# m -> m Exts.-# 1# 725 !(# q1_0, c1_0 #) = L.mac# x1 x0 (Limb 0##) (Limb 0##) 726 !r1 = c1_0 727 !(# r2_0, c2_0 #) = L.mac# x2 x0 r1 (Limb 0##) 728 !(# s2_1, c2_1 #) = L.mac# x2 x1 (Limb 0##) c2_0 729 !t2 = c2_1 730 !(# s3_0, c3_0 #) = L.mac# x3 x0 s2_1 (Limb 0##) 731 !(# t3, c3_1 #) = L.mac# x3 x1 t2 c3_0 732 !(# u3, c3_2 #) = L.mac# x3 x2 (Limb 0##) c3_1 733 !v3 = c3_2 734 !(# lo1, car0_1 #) = (# L.shl# q1_0 1#, L.shr# q1_0 sh #) 735 !(# lo2, car0_2 #) = (# L.or# (L.shl# r2_0 1#) car0_1, L.shr# r2_0 sh #) 736 !(# lo3, car0_3 #) = (# L.or# (L.shl# s3_0 1#) car0_2, L.shr# s3_0 sh #) 737 !(# hi0, car1_0 #) = (# L.or# (L.shl# t3 1#) car0_3, L.shr# t3 sh #) 738 !(# hi1, car1_1 #) = (# L.or# (L.shl# u3 1#) car1_0, L.shr# u3 sh #) 739 !(# hi2, car1_2 #) = (# L.or# (L.shl# v3 1#) car1_1, L.shr# v3 sh #) 740 !hi3 = car1_2 741 !(# pf, car2_0 #) = L.mac# x0 x0 (Limb 0##) (Limb 0##) 742 !(# qf, car2_1 #) = L.add_c# lo1 car2_0 (Limb 0##) 743 !(# rf, car2_2 #) = L.mac# x1 x1 lo2 car2_1 744 !(# sf, car2_3 #) = L.add_c# lo3 car2_2 (Limb 0##) 745 !(# tf, car2_4 #) = L.mac# x2 x2 hi0 car2_3 746 !(# uf, car2_5 #) = L.add_c# hi1 car2_4 (Limb 0##) 747 !(# vf, car2_6 #) = L.mac# x3 x3 hi2 car2_5 748 !(# wf, _ #) = L.add_c# hi3 car2_6 (Limb 0##) 749 in (# (# pf, qf, rf, sf #), (# tf, uf, vf, wf #) #) 750 {-# INLINE sqr# #-} 751 752 -- | Widening square. 753 -- 754 -- >>> sqr 2 755 -- (4,0) 756 -- >>> sqr (2 ^ (256 :: Word) - 1) 757 -- (1,115792089237316195423570985008687907853269984665640564039457584007913129639934) 758 sqr :: Wider -> (Wider, Wider) 759 sqr (Wider w) = 760 let !(# l, h #) = sqr# w 761 in (Wider l, Wider h) 762 763 odd# :: (# Limb, Limb, Limb, Limb #) -> C.Choice 764 odd# (# Limb w, _, _, _ #) = C.from_word# (Exts.and# w 1##) 765 {-# INLINE odd# #-} 766 767 -- | Check if a 'Wider' is odd, returning a 'Choice'. 768 odd 769 :: Wider 770 -> C.Choice 771 odd (Wider w) = odd# w 772