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