fixed

commit 83f91383cdc9db4d73319d95dd38902372188b85
parent 6f67dddf52e9bae312d876d9f0becddd22d034fa
Author: Jared Tobin <jared@jtobin.io>
Date:   Wed, 22 Jan 2025 22:41:31 +0400

lib: bit operations

Diffstat:
M
bench/Main.hs
 | 
49
++++++++++++++++++++++++++++++++++++++++++++++++-
M
lib/Data/Word/Extended.hs
 | 
20
++++++++++++++++++--

2 files changed, 66 insertions(+), 3 deletions(-)
diff --git a/bench/Main.hs b/bench/Main.hs
@@ -3,13 +3,54 @@
 
 module Main where
 
+import Data.Bits ((.|.), (.&.), (.^.))
 import qualified Data.Word.Extended as W
 import Control.DeepSeq
 import Criterion.Main
+import Prelude hiding (or, and)
 
 instance NFData W.Word256
 instance NFData W.Word512
 
+or_baseline :: Benchmark
+or_baseline = bench "or (baseline)" $ nf ((.|.) w0) w1 where
+  w0, w1 :: Integer
+  !w0 = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
+  !w1 = 0x7fffffffffffffffffffffffffffffffffffffffffffffbfffffffffffffffed
+
+or :: Benchmark
+or = bench "or" $ nf (W.or w0) w1 where
+  !w0 = W.to_word256
+    0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
+  !w1 = W.to_word256
+    0x7fffffffffffffffffffffffffffffffffffffffffffffbfffffffffffffffed
+
+and_baseline :: Benchmark
+and_baseline = bench "and (baseline)" $ nf ((.&.) w0) w1 where
+  w0, w1 :: Integer
+  !w0 = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
+  !w1 = 0x7fffffffffffffffffffffffffffffffffffffffffffffbfffffffffffffffed
+
+and :: Benchmark
+and = bench "and" $ nf (W.and w0) w1 where
+  !w0 = W.to_word256
+    0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
+  !w1 = W.to_word256
+    0x7fffffffffffffffffffffffffffffffffffffffffffffbfffffffffffffffed
+
+xor_baseline :: Benchmark
+xor_baseline = bench "xor (baseline)" $ nf ((.^.) w0) w1 where
+  w0, w1 :: Integer
+  !w0 = 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
+  !w1 = 0x7fffffffffffffffffffffffffffffffffffffffffffffbfffffffffffffffed
+
+xor :: Benchmark
+xor = bench "xor" $ nf (W.xor w0) w1 where
+  !w0 = W.to_word256
+    0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed
+  !w1 = W.to_word256
+    0x7fffffffffffffffffffffffffffffffffffffffffffffbfffffffffffffffed
+
 add_baseline :: Benchmark
 add_baseline = bench "add (baseline)" $ nf ((+) w0) w1 where
   w0, w1 :: Integer
@@ -63,7 +104,13 @@ mul128 = bench "mul128" $ nf (W.mul w0) w1 where
 
 main :: IO ()
 main = defaultMain [
-    add_baseline
+    or_baseline
+  , or
+  , and_baseline
+  , and
+  , xor_baseline
+  , xor
+  , add_baseline
   , add
   , sub_baseline
   , sub
diff --git a/lib/Data/Word/Extended.hs b/lib/Data/Word/Extended.hs
@@ -5,7 +5,7 @@
 
 module Data.Word.Extended where
 
-import Data.Bits ((.|.), (.&.), (.<<.), (.>>.))
+import Data.Bits ((.|.), (.&.), (.<<.), (.>>.), (.^.))
 import qualified Data.Bits as B
 import Data.Word (Word64)
 import GHC.Generics
@@ -84,6 +84,20 @@ to_word512 n =
       !w7 = fi ((n .>>. 448) .&. mask64)
   in  Word512 w0 w1 w2 w3 w4 w5 w6 w7
 
+-- bits -----------------------------------------------------------------------
+
+or :: Word256 -> Word256 -> Word256
+or (Word256 a0 a1 a2 a3) (Word256 b0 b1 b2 b3) =
+  Word256 (a0 .|. b0) (a1 .|. b1) (a2 .|. b2) (a3 .|. b3)
+
+and :: Word256 -> Word256 -> Word256
+and (Word256 a0 a1 a2 a3) (Word256 b0 b1 b2 b3) =
+  Word256 (a0 .&. b0) (a1 .&. b1) (a2 .&. b2) (a3 .&. b3)
+
+xor :: Word256 -> Word256 -> Word256
+xor (Word256 a0 a1 a2 a3) (Word256 b0 b1 b2 b3) =
+  Word256 (a0 .^. b0) (a1 .^. b1) (a2 .^. b2) (a3 .^. b3)
+
 -- addition, subtraction ------------------------------------------------------
 
 -- add-with-carry
@@ -232,6 +246,7 @@ mul_512 (Word256 x0 x1 x2 x3) (Word256 y0 y1 y2 y3) =
 
 -- division -------------------------------------------------------------------
 
+-- XX make this work on variable-length x, y
 -- sub_mul x y m = (x - y * m, rem)
 sub_mul :: Word256 -> Word256 -> Word64 -> Word256WithOverflow
 sub_mul (Word256 x0 x1 x2 x3) (Word256 y0 y1 y2 y3) m =
@@ -312,7 +327,7 @@ quotrem_2by1 uh ul d rec =
   let !(P qh_0 ql) = mul_c rec uh
       !(P ql_0 c)  = add_c ql ul 0
       !(P (succ -> qh_1) _)  = add_c qh_0 uh c
-      !r = ul - qh_1 * d -- sub_mul?
+      !r = ul - qh_1 * d
 
       !(P qh_y r_y) | r > ql_0  = P (qh_1 - 1) (r + d)
                     | otherwise = P qh_1 r
@@ -321,6 +336,7 @@ quotrem_2by1 uh ul d rec =
       then P (qh_y + 1) (r_y - d)
       else P qh_y r_y
 
+-- XX make this work on variable-length x, y (udivremBy1)
 quotrem_by1 :: Word256 -> Word64 -> Word256WithOverflow
 quotrem_by1 (Word256 u0 u1 u2 u3) d =
   let !rec = recip_2by1 d