Skip to content
Snippets Groups Projects

Add mod2 gates

Merged Jakob Schneider Villumsen requested to merge ops into main
2 files
+ 49
13
Compare changes
  • Side-by-side
  • Inline
Files
2
+ 33
13
import "util"
import "circuit"
module CircuitMod2 : Circuit = {
type s = u32
type t = {
p1 : u32,
p2 : u32,
p3 : u32
p1 : s,
p2 : s,
p3 : s
}
type s = u32
-- TODO: Rewrite this module using [32]bool for parallelism instead of u32. Maybe we get better performance?
def set_bit (x: u32) (i: u32) (b: u32): u32 =
if (b & 1u32) == 1u32 then x | (1u32 << i) else x & (! (1u32 << i))
def get_bit (x: u32) (i: u32): u32 =
(x >> i) & 1u32
def right_rotate (x: u32) (n: u32): u32 =
(x >> n) | (x << (32u32 - n))
-- | Returns the addition neutral element (zero).
--
def zero : t = { p1 = 0, p2 = 0, p3 = 0 }
def map (f: s -> s) ({p1, p2, p3}: t) =
{
@@ -42,6 +38,30 @@ module CircuitMod2 : Circuit = {
def (!!) = NEG
def and (r: t) (a: t) (b: t): t =
{
p1 = (a.p1 & b.p2) ^ (a.p2 & b.p1) ^ (a.p1 & b.p1) ^ r.p1 ^ r.p2,
p2 = (a.p2 & b.p3) ^ (a.p3 & b.p2) ^ (a.p2 & b.p2) ^ r.p2 ^ r.p3,
p3 = (a.p3 & b.p1) ^ (a.p1 & b.p3) ^ (a.p3 & b.p3) ^ r.p3 ^ r.p1
}
def add_bit_i (((r, a, b), c): ((t, t, t), t)) (idx: i32) =
let i = u32.i32 idx
let a' = map2 (^) a c |> map (get_bit i)
let b' = map2 (^) b c |> map (get_bit i)
let t1 = (a'.p1 & b'.p2) ^ (a'.p2 & b'.p1) ^ (get_bit i r.p2)
let t2 = (a'.p2 & b'.p3) ^ (a'.p3 & b'.p2) ^ (get_bit i r.p3)
let t3 = (a'.p3 & b'.p1) ^ (a'.p1 & b'.p3) ^ (get_bit i r.p1)
let c1 = c.p1 |> set_bit (i + 1) (t1 ^ (a'.p1 & b'.p1) ^ (get_bit i c.p1) ^ get_bit i r.p1)
let c2 = c.p2 |> set_bit (i + 1) (t2 ^ (a'.p2 & b'.p2) ^ (get_bit i c.p2) ^ get_bit i r.p2)
let c3 = c.p3 |> set_bit (i + 1) (t3 ^ (a'.p3 & b'.p3) ^ (get_bit i c.p3) ^ get_bit i r.p3)
let c' = { p1 = c1, p2 = c2, p3 = c3 }
in ((r, a', b), c')
def add (r: t) (a: t) (b: t): t =
let c = foldl add_bit_i ((r, a, b), zero) (0i32..1i32..<32i32) |> snd
in a ^^ b ^^ c
--| Unary addition
def (+) (alpha: s) (a: t) : t = a with p1 = a.p1 + alpha
Loading