Rust-consttime (An obsoleted proof of concept; DO NOT USE THIS!)

.gitignore

target
doc

README.md

Rust-consttime

DO NOT USE THIS! This was a proof of concept later obsoleted. If you ever have to use the constant-time operation in Rust, please take a look at nadeko.

Experimental utilities for guaranteed constant time operations.

Quick usages:

use std::int;
use consttime::{ct, ct_bool, ct_int, ct_uint, ct_array};
use consttime::{ConstTime, ConstTimeOrd, ConstTimeArray};

// `ct_*` types provide guaranteed constant time operations.
// they can be constructed via the function of the same name...
let a = ct_int(42);

// or the `ct` generic function.
// this is a bit cumbersome but `ct_array` should be constructed in this way.
let b: ct_int = ct(54);

// the constant-time operations propagate to the return type.
// for this reason, `ct_*` types do not implement some built-in traits.
let a_plus_b: ct_int = a + b;
let a_xor_b: ct_int = a ^ b;
let not_a: ct_int = !a;
//let a_lt_b = a < b;
let a_lt_b: ct_bool = a.clt(&b); // we need ct_bool here, so we can't implement Ord

// use `unwrap` to return the inner value.
// this is the only method which does not implement the propagation.
assert_eq!(a_plus_b.unwrap(), 96);
assert_eq!(a_xor_b.unwrap(), 28);
assert_eq!(not_a.unwrap(), !42);
assert_eq!(a_lt_b.unwrap(), true);

// one should replace `if a {b} else {c}` with `ct_bool::choose`.
// (yes, I know this is really cumbersome...)
let larger = a.cgt(&b).choose(a, b);
assert_eq!(larger.unwrap(), 54);

// `ct_array` is a bit special, as it has to be constructed via `ct`.
// it prevents the cache-timing attacks, and always loads and stores the whole array.
let mut arr: ct_array<[ct_int, ..4]> = ct([64i, 25i, 81i, 16i]);
assert_eq!(arr.get(ct_uint(1)).unwrap(), 25);
arr.put(ct_uint(1), ct_int(49));
assert_eq!(arr.get(ct_uint(1)).unwrap(), 49);

// one should use `ct_array::iter` or `ct_array::mut_iter` to manipulate the array.
let mut max = ct_int(int::MIN);
arr.iter(|_i, v| {
    max = v.clt(&max).choose(max, v);
});
assert_eq!(max.unwrap(), 81);

Warning: While this library tries to avoid branches or input-dependent memory operations, the code optimizer may reintroduce them and you should carefully verify the assembly in order to use this.

Cargo.toml

[package]

name = "consttime"
version = "0.1.0"
authors = ["Kang Seonghoon <public+rust@mearie.org>"]

[dependencies.quickcheck]
git = "https://github.com/BurntSushi/quickcheck"

[dependencies.quickcheck_macros]
git = "https://github.com/BurntSushi/quickcheck"

[[lib]]

name = "consttime"
path = "lib.rs"

lib.rs

// This is rust-consttime.
// Written by Kang Seonghoon, released into the public domain. See UNLICENSE for details.

#![crate_name = "consttime"]
#![crate_type = "lib"]

#![feature(phase, macro_rules)]

#[phase(plugin)] extern crate quickcheck_macros;
extern crate quickcheck;

use std::fmt;
use std::mem::transmute;
use quickcheck::{Arbitrary, Gen, Shrinker};

pub trait ConstTime<T> {
    fn new(value: T) -> Self;
    fn unwrap(self) -> T;
}

#[inline] pub fn ct<T, CT: ConstTime<T>>(value: T) -> CT { ConstTime::new(value) }

pub trait ConstTimeInt: Neg<Self> + Add<Self, Self> + Sub<Self, Self> + Mul<Self, Self>
                      + Shl<ct_uint, Self> + Shr<ct_uint, Self> {
    fn to_u8(&self) -> ct_u8;
    fn to_u16(&self) -> ct_u16;
    fn to_u32(&self) -> ct_u32;
    fn to_u64(&self) -> ct_u64;
    fn to_uint(&self) -> ct_uint;

    fn to_i8(&self) -> ct_i8;
    fn to_i16(&self) -> ct_i16;
    fn to_i32(&self) -> ct_i32;
    fn to_i64(&self) -> ct_i64;
    fn to_int(&self) -> ct_int;

    fn is_zero(&self) -> ct_bool;
    fn is_nonzero(&self) -> ct_bool;
    fn is_positive(&self) -> ct_bool;
    fn is_nonpositive(&self) -> ct_bool;
    fn is_negative(&self) -> ct_bool;
    fn is_nonnegative(&self) -> ct_bool;

    fn msb(&self) -> ct_bool;
    fn lsb(&self) -> ct_bool;
}

pub trait ConstTimeBits: Not<Self> + BitAnd<Self, Self> + BitOr<Self, Self> + BitXor<Self, Self> {
    fn zero_bits() -> Self;
    fn expand_bits(value: bool) -> Self;
}

pub trait ConstTimeOrd {
    fn ceq(&self, rhs: &Self) -> ct_bool;
    fn cne(&self, rhs: &Self) -> ct_bool;
    fn clt(&self, rhs: &Self) -> ct_bool;
    fn cle(&self, rhs: &Self) -> ct_bool;
    fn cgt(&self, rhs: &Self) -> ct_bool;
    fn cge(&self, rhs: &Self) -> ct_bool;
}

pub trait ConstTimeArray<T> {
    fn iter(&self, f: |index: ct_uint, value: T|);
    fn mut_iter(&mut self, f: |index: ct_uint, old_value: T| -> T);
    fn get(&self, index: ct_uint) -> T;
    fn put(&mut self, index: ct_uint, value: T);
}

#[inline]
fn bool_from_u8(value: ct_u8) -> ct_bool {
    debug_assert!(value.unwrap() == 0 || value.unwrap() == 1);
    unsafe {transmute(value)}
}

macro_rules! define_int(
    (
        type=$ty:ty/$cty:ident,
        signed=$sty:ty/$scty:ident, unsigned=$uty:ty/$ucty:ident, maxbits=$maxbits:expr,
        int_impl=|$slf:ident| {
            is_positive: $is_positive:expr, is_nonpositive: $is_nonpositive:expr,
            is_negative: $is_negative:expr, is_nonnegative: $is_nonnegative:expr
        },
        bits_impl=|$value:ident| { expand_bits: $expand_bits:expr },
        ord_impl=|$lhs:ident, $rhs:ident| { clt: $clt:expr, cle: $cle:expr }
    ) => (
        #[deriving(Clone)]
        #[allow(non_camel_case_types)]
        pub struct $cty { value: $ty }

        #[inline] pub fn $cty(value: $ty) -> $cty { ct(value) }

        impl ConstTime<$ty> for $cty {
            #[inline] fn new(value: $ty) -> $cty { $cty { value: value } }
            #[inline] fn unwrap(self) -> $ty { self.value }
        }

        impl $cty {
            #[inline] pub fn to_signed(&self) -> $scty { ct(self.value as $sty) }
            #[inline] pub fn to_unsigned(&self) -> $ucty { ct(self.value as $uty) }
        }

        impl ConstTimeInt for $cty {
            #[inline] fn to_u8(&self) -> ct_u8 { ct_u8(self.value as u8) }
            #[inline] fn to_u16(&self) -> ct_u16 { ct_u16(self.value as u16) }
            #[inline] fn to_u32(&self) -> ct_u32 { ct_u32(self.value as u32) }
            #[inline] fn to_u64(&self) -> ct_u64 { ct_u64(self.value as u64) }
            #[inline] fn to_uint(&self) -> ct_uint { ct_uint(self.value as uint) }

            #[inline] fn to_i8(&self) -> ct_i8 { ct_i8(self.value as i8) }
            #[inline] fn to_i16(&self) -> ct_i16 { ct_i16(self.value as i16) }
            #[inline] fn to_i32(&self) -> ct_i32 { ct_i32(self.value as i32) }
            #[inline] fn to_i64(&self) -> ct_i64 { ct_i64(self.value as i64) }
            #[inline] fn to_int(&self) -> ct_int { ct_int(self.value as int) }

            #[inline] fn is_zero(&self) -> ct_bool { !self.is_nonzero() }
            #[inline] fn is_nonzero(&self) -> ct_bool { (*self | -*self).msb() }
            #[inline] fn is_positive(&self) -> ct_bool { let $slf = self; $is_positive }
            #[inline] fn is_nonpositive(&self) -> ct_bool { let $slf = self; $is_nonpositive }
            #[inline] fn is_negative(&self) -> ct_bool { let $slf = self; $is_negative }
            #[inline] fn is_nonnegative(&self) -> ct_bool { let $slf = self; $is_nonnegative }

            #[inline]
            fn msb(&self) -> ct_bool {
                bool_from_u8((self.to_unsigned() >> ct_uint($maxbits)).to_u8())
            }

            #[inline]
            fn lsb(&self) -> ct_bool {
                bool_from_u8((self.to_unsigned() & $ucty(1)).to_u8())
            }
        }

        impl ConstTimeBits for $cty {
            #[inline] fn zero_bits() -> $cty { ct(0) }
            #[inline] fn expand_bits(value: bool) -> $cty { let $value = value; $expand_bits }
        }

        impl ConstTimeOrd for $cty {
            #[inline] fn ceq(&self, rhs: &$cty) -> ct_bool { !self.cne(rhs) }
            #[inline] fn cne(&self, rhs: &$cty) -> ct_bool {
                ((*self - *rhs) | (*rhs - *self)).msb()
            }
            #[inline] fn clt(&self, rhs: &$cty) -> ct_bool { let $lhs = self; let $rhs = rhs; $clt }
            #[inline] fn cle(&self, rhs: &$cty) -> ct_bool { let $lhs = self; let $rhs = rhs; $cle }
            #[inline] fn cgt(&self, rhs: &$cty) -> ct_bool { rhs.clt(self) }
            #[inline] fn cge(&self, rhs: &$cty) -> ct_bool { rhs.cle(self) }
        }

        impl Neg<$cty> for $cty {
            #[inline]
            #[allow(unsigned_negate)]
            fn neg(&self) -> $cty { ct(-self.value) }
        }

        impl Add<$cty, $cty> for $cty {
            #[inline]
            fn add(&self, rhs: &$cty) -> $cty { ct(self.value + rhs.value) }
        }

        impl Sub<$cty, $cty> for $cty {
            #[inline]
            fn sub(&self, rhs: &$cty) -> $cty { ct(self.value - rhs.value) }
        }

        impl Mul<$cty, $cty> for $cty {
            #[inline]
            fn mul(&self, rhs: &$cty) -> $cty {
                // XXX technically not very constant time in some architectures, need workarounds
                ct(self.value * rhs.value)
            }
        }

        impl Not<$cty> for $cty {
            #[inline]
            fn not(&self) -> $cty { ct(!self.value) }
        }

        impl BitAnd<$cty, $cty> for $cty {
            #[inline]
            fn bitand(&self, rhs: &$cty) -> $cty { ct(self.value & rhs.value) }
        }

        impl BitOr<$cty, $cty> for $cty {
            #[inline]
            fn bitor(&self, rhs: &$cty) -> $cty { ct(self.value | rhs.value) }
        }

        impl BitXor<$cty, $cty> for $cty {
            #[inline]
            fn bitxor(&self, rhs: &$cty) -> $cty { ct(self.value ^ rhs.value) }
        }

        impl Shl<ct_uint, $cty> for $cty {
            #[inline]
            fn shl(&self, rhs: &ct_uint) -> $cty { ct(self.value << rhs.value) }
        }

        impl Shr<ct_uint, $cty> for $cty {
            #[inline]
            fn shr(&self, rhs: &ct_uint) -> $cty { ct(self.value >> rhs.value) }
        }

        impl fmt::Show for $cty {
            fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.value.fmt(f) }
        }

        impl Arbitrary for $cty {
            fn arbitrary<G: Gen>(g: &mut G) -> $cty { $cty(Arbitrary::arbitrary(g)) }
            fn shrink(&self) -> Box<Shrinker<$cty>> {
                box self.value.shrink().map($cty) as Box<Shrinker<$cty>>
            }
        }
    );

    // signed types
    (type=$ty:ty/$cty:ident, signed, unsigned=$uty:ty/$ucty:ident, maxbits=$maxbits:expr) => (
        define_int!(type=$ty/$cty, signed=$ty/$cty, unsigned=$uty/$ucty, maxbits=$maxbits,
                    int_impl=|slf| {
                        is_positive: (-*slf & !*slf).msb(), is_nonpositive: (*slf | !-*slf).msb(),
                        is_negative: slf.msb(), is_nonnegative: (!*slf).msb()
                    },
                    bits_impl=|value| {
                        expand_bits: (-$ucty(ct_bool(value).to_u8().unwrap() as $uty)).to_signed()
                    },
                    ord_impl=|lhs, rhs| {
                        clt: { let diff = *lhs - *rhs;
                               (diff ^ ((*lhs ^ *rhs) & (diff ^ *lhs))).msb() },
                        cle: ((*lhs | !*rhs) & ((*lhs ^ *rhs) | !(*rhs - *lhs))).msb()
                    })
    );

    // unsigned types
    (type=$ty:ty/$cty:ident, signed=$sty:ty/$scty:ident, unsigned, maxbits=$maxbits:expr) => (
        define_int!(type=$ty/$cty, signed=$sty/$scty, unsigned=$ty/$cty, maxbits=$maxbits,
                    int_impl=|_slf| {
                        is_positive: _slf.is_nonzero(), is_nonpositive: _slf.is_zero(),
                        is_negative: ct_bool(false), is_nonnegative: ct_bool(true)
                    },
                    bits_impl=|value| {
                        expand_bits: (-$cty(ct_bool(value).to_u8().unwrap() as $ty))
                    },
                    ord_impl=|lhs, rhs| {
                        clt: ((!*lhs & *rhs) | ((!*lhs | *rhs) & (*lhs - *rhs))).msb(),
                        cle: ((!*lhs | *rhs) & ((*lhs ^ *rhs) | !(*rhs - *lhs))).msb()
                    })
    );
)

define_int!(type=u8/ct_u8,   signed=i8/ct_i8,   unsigned, maxbits=7)
define_int!(type=u16/ct_u16, signed=i16/ct_i16, unsigned, maxbits=15)
define_int!(type=u32/ct_u32, signed=i32/ct_i32, unsigned, maxbits=31)
define_int!(type=u64/ct_u64, signed=i64/ct_i64, unsigned, maxbits=63)
define_int!(type=i8/ct_i8,   signed, unsigned=u8/ct_u8,   maxbits=7)
define_int!(type=i16/ct_i16, signed, unsigned=u16/ct_u16, maxbits=15)
define_int!(type=i32/ct_i32, signed, unsigned=u32/ct_u32, maxbits=31)
define_int!(type=i64/ct_i64, signed, unsigned=u64/ct_u64, maxbits=63)

#[cfg(target_word_size = "32")]
define_int!(type=uint/ct_uint, signed=int/ct_int, unsigned, maxbits=31)
#[cfg(target_word_size = "64")]
define_int!(type=uint/ct_uint, signed=int/ct_int, unsigned, maxbits=63)

#[cfg(target_word_size = "32")]
define_int!(type=int/ct_int, signed, unsigned=uint/ct_uint, maxbits=31)
#[cfg(target_word_size = "64")]
define_int!(type=int/ct_int, signed, unsigned=uint/ct_uint, maxbits=63)

#[deriving(Clone)]
#[allow(non_camel_case_types)]
pub struct ct_bool { value: bool }

#[inline] pub fn ct_bool(value: bool) -> ct_bool { ct(value) }

impl ConstTime<bool> for ct_bool {
    #[inline] fn new(value: bool) -> ct_bool { ct_bool { value: value } }
    #[inline] fn unwrap(self) -> bool { self.value }
}

impl ct_bool {
    #[inline]
    pub fn cswap<T: ConstTimeBits>(&self, (a, b): (T, T)) -> (T, T) {
        let common = (a ^ b) & ConstTimeBits::expand_bits(self.value);
        (a ^ common, b ^ common)
    }

    #[inline]
    pub fn choose<T: ConstTimeBits>(&self, then: T, else_: T) -> T {
        self.cswap((else_, then)).val0()
    }
}

// treat `ct_bool` like an imaginary `C<u1>`
impl ConstTimeInt for ct_bool {
    #[inline] fn to_u8(&self) -> ct_u8 { unsafe {transmute(*self)} }
    #[inline] fn to_u16(&self) -> ct_u16 { self.to_u8().to_u16() }
    #[inline] fn to_u32(&self) -> ct_u32 { self.to_u8().to_u32() }
    #[inline] fn to_u64(&self) -> ct_u64 { self.to_u8().to_u64() }
    #[inline] fn to_uint(&self) -> ct_uint { self.to_u8().to_uint() }

    #[inline] fn to_i8(&self) -> ct_i8 { self.to_u8().to_i8() }
    #[inline] fn to_i16(&self) -> ct_i16 { self.to_u8().to_i16() }
    #[inline] fn to_i32(&self) -> ct_i32 { self.to_u8().to_i32() }
    #[inline] fn to_i64(&self) -> ct_i64 { self.to_u8().to_i64() }
    #[inline] fn to_int(&self) -> ct_int { self.to_u8().to_int() }

    #[inline] fn is_zero(&self) -> ct_bool { !*self }
    #[inline] fn is_nonzero(&self) -> ct_bool { *self }
    #[inline] fn is_positive(&self) -> ct_bool { *self }
    #[inline] fn is_nonpositive(&self) -> ct_bool { !*self }
    #[inline] fn is_negative(&self) -> ct_bool { ct_bool(false) }
    #[inline] fn is_nonnegative(&self) -> ct_bool { ct_bool(true) }

    #[inline] fn msb(&self) -> ct_bool { *self }
    #[inline] fn lsb(&self) -> ct_bool { *self }
}

impl ConstTimeBits for ct_bool {
    #[inline] fn zero_bits() -> ct_bool { ct_bool(false) }
    #[inline] fn expand_bits(value: bool) -> ct_bool { ct_bool(value) }
}

impl ConstTimeOrd for ct_bool {
    #[inline] fn ceq(&self, rhs: &ct_bool) -> ct_bool { !(*self ^  *rhs) }
    #[inline] fn cne(&self, rhs: &ct_bool) -> ct_bool {   *self ^  *rhs  }
    #[inline] fn clt(&self, rhs: &ct_bool) -> ct_bool {  !*self &  *rhs  }
    #[inline] fn cle(&self, rhs: &ct_bool) -> ct_bool {  !*self |  *rhs  }
    #[inline] fn cgt(&self, rhs: &ct_bool) -> ct_bool {   *self & !*rhs  }
    #[inline] fn cge(&self, rhs: &ct_bool) -> ct_bool {   *self | !*rhs  }
}

impl Neg<ct_bool> for ct_bool {
    #[inline] fn neg(&self) -> ct_bool { !*self }
}

impl Add<ct_bool, ct_bool> for ct_bool {
    #[inline] fn add(&self, rhs: &ct_bool) -> ct_bool { *self ^ *rhs }
}

impl Sub<ct_bool, ct_bool> for ct_bool {
    #[inline] fn sub(&self, rhs: &ct_bool) -> ct_bool { *self ^ *rhs }
}

impl Mul<ct_bool, ct_bool> for ct_bool {
    #[inline] fn mul(&self, rhs: &ct_bool) -> ct_bool { *self & *rhs }
}

impl Not<ct_bool> for ct_bool {
    #[inline] fn not(&self) -> ct_bool { *self ^ ct_bool(true) }
}

impl BitAnd<ct_bool, ct_bool> for ct_bool {
    #[inline]
    fn bitand(&self, rhs: &ct_bool) -> ct_bool {
        bool_from_u8(self.to_u8() & rhs.to_u8())
    }
}

impl BitOr<ct_bool, ct_bool> for ct_bool {
    #[inline]
    fn bitor(&self, rhs: &ct_bool) -> ct_bool {
        bool_from_u8(self.to_u8() | rhs.to_u8())
    }
}

impl BitXor<ct_bool, ct_bool> for ct_bool {
    #[inline]
    fn bitxor(&self, rhs: &ct_bool) -> ct_bool {
        bool_from_u8(self.to_u8() ^ rhs.to_u8())
    }
}

impl Shl<ct_uint, ct_bool> for ct_bool {
    #[inline] fn shl(&self, _rhs: &ct_uint) -> ct_bool { *self }
}

impl Shr<ct_uint, ct_bool> for ct_bool {
    #[inline] fn shr(&self, _rhs: &ct_uint) -> ct_bool { *self }
}

impl fmt::Show for ct_bool {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { self.value.fmt(f) }
}

impl Arbitrary for ct_bool {
    fn arbitrary<G: Gen>(g: &mut G) -> ct_bool { ct_bool(Arbitrary::arbitrary(g)) }
    fn shrink(&self) -> Box<Shrinker<ct_bool>> {
        box self.value.shrink().map(ct_bool) as Box<Shrinker<ct_bool>>
    }
}

#[allow(non_camel_case_types)]
pub struct ct_array<Array> { array: Array }

macro_rules! define_array(
    ($n:expr: $($v:ident)*) => (
        impl<T: Copy, CT: ConstTime<T>+Copy> ConstTime<[T, ..$n]> for ct_array<[CT, ..$n]> {
            fn new(array: [T, ..$n]) -> ct_array<[CT, ..$n]> {
                let [$($v),*] = array;
                ct_array { array: [$(ct($v)),*] }
            }

            fn unwrap(self) -> [T, ..$n] {
                let [$($v),*] = self.array;
                [$($v.unwrap()),*]
            }
        }

        impl<T: Clone> Clone for ct_array<[T, ..$n]> {
            fn clone(&self) -> ct_array<[T, ..$n]> {
                let [$(ref $v),*] = self.array;
                ct_array { array: [$($v.clone()),*] }
            }
        }

        impl<T: ConstTimeBits+Clone> ConstTimeArray<T> for ct_array<[T, ..$n]> {
            fn iter(&self, f: |ct_uint, T|) {
                for i in range(0u, $n) {
                    f(ct_uint(i), self.array[i].clone());
                }
            }

            fn mut_iter(&mut self, f: |ct_uint, T| -> T) {
                for i in range(0u, $n) {
                    self.array[i] = f(ct_uint(i), self.array[i].clone());
                }
            }

            fn get(&self, index: ct_uint) -> T {
                let mut value = ConstTimeBits::zero_bits();
                for i in range(0u, $n) {
                    value = ct_uint(i).ceq(&index).choose(self.array[i].clone(), value);
                }
                value
            }

            fn put(&mut self, index: ct_uint, value: T) {
                for i in range(0u, $n) {
                    self.array[i] =
                        ct_uint(i).ceq(&index).choose(value.clone(), self.array[i].clone());
                }
            }
        }

        impl<T: ConstTimeOrd+Clone> ConstTimeOrd for ct_array<[T, ..$n]> {
            fn ceq(&self, rhs: &ct_array<[T, ..$n]>) -> ct_bool {
                let mut ret = ct_bool(true);
                for i in range(0u, $n) {
                    ret = ret & self.array[i].ceq(&rhs.array[i]);
                }
                ret
            }

            fn clt(&self, rhs: &ct_array<[T, ..$n]>) -> ct_bool {
                let mut eq = ct_bool(true);
                let mut lt = ct_bool(false);
                for i in range(0u, $n) {
                    lt = lt | (eq & self.array[i].clt(&rhs.array[i]));
                    eq = eq & self.array[i].ceq(&rhs.array[i]);
                }
                lt
            }

            fn cle(&self, rhs: &ct_array<[T, ..$n]>) -> ct_bool {
                let mut eq = ct_bool(true);
                let mut lt = ct_bool(false);
                for i in range(0u, $n) {
                    lt = lt | (eq & self.array[i].clt(&rhs.array[i]));
                    eq = eq & self.array[i].ceq(&rhs.array[i]);
                }
                lt | eq
            }

            fn cne(&self, rhs: &ct_array<[T, ..$n]>) -> ct_bool { !self.ceq(rhs) }
            fn cgt(&self, rhs: &ct_array<[T, ..$n]>) -> ct_bool { rhs.clt(self) }
            fn cge(&self, rhs: &ct_array<[T, ..$n]>) -> ct_bool { rhs.cle(self) }
        }
    );
)

define_array!(0: )
define_array!(1: v0)
define_array!(2: v0 v1)
define_array!(3: v0 v1 v2)
define_array!(4: v0 v1 v2 v3)
define_array!(5: v0 v1 v2 v3 v4)
define_array!(6: v0 v1 v2 v3 v4 v5)
define_array!(7: v0 v1 v2 v3 v4 v5 v6)
define_array!(8: v0 v1 v2 v3 v4 v5 v6 v7)
define_array!(9: v0 v1 v2 v3 v4 v5 v6 v7 v8)
define_array!(10: v0 v1 v2 v3 v4 v5 v6 v7 v8 v9)
define_array!(11: v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10)
define_array!(12: v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11)
define_array!(13: v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12)
define_array!(14: v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13)
define_array!(15: v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14)
define_array!(16: v0 v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15)

macro_rules! check(
    ($($testname:ident($($arg:ident: $ty:ty),*): $lhs:expr => $rhs:expr;)+) => (
        $(#[quickcheck] fn $testname($($arg: $ty),*) -> bool { ($lhs) == $rhs.unwrap() })+
    )
)

check! {
    test_u8_eq(a: u8, b: u8):        a == b => ct_u8(a).ceq(&ct_u8(b));
    test_u8_ne(a: u8, b: u8):        a != b => ct_u8(a).cne(&ct_u8(b));
    test_u8_lt(a: u8, b: u8):        a <  b => ct_u8(a).clt(&ct_u8(b));
    test_u8_le(a: u8, b: u8):        a <= b => ct_u8(a).cle(&ct_u8(b));
    test_u8_gt(a: u8, b: u8):        a >  b => ct_u8(a).cgt(&ct_u8(b));
    test_u8_ge(a: u8, b: u8):        a >= b => ct_u8(a).cge(&ct_u8(b));
    test_u8_is_zero(a: u8):          a == 0 => ct_u8(a).is_zero();
    test_u8_is_nonzero(a: u8):       a != 0 => ct_u8(a).is_nonzero();

    test_u16_eq(a: u16, b: u16):     a == b => ct_u16(a).ceq(&ct_u16(b));
    test_u16_ne(a: u16, b: u16):     a != b => ct_u16(a).cne(&ct_u16(b));
    test_u16_lt(a: u16, b: u16):     a <  b => ct_u16(a).clt(&ct_u16(b));
    test_u16_le(a: u16, b: u16):     a <= b => ct_u16(a).cle(&ct_u16(b));
    test_u16_gt(a: u16, b: u16):     a >  b => ct_u16(a).cgt(&ct_u16(b));
    test_u16_ge(a: u16, b: u16):     a >= b => ct_u16(a).cge(&ct_u16(b));
    test_u16_is_zero(a: u16):        a == 0 => ct_u16(a).is_zero();
    test_u16_is_nonzero(a: u16):     a != 0 => ct_u16(a).is_nonzero();

    test_u32_eq(a: u32, b: u32):     a == b => ct_u32(a).ceq(&ct_u32(b));
    test_u32_ne(a: u32, b: u32):     a != b => ct_u32(a).cne(&ct_u32(b));
    test_u32_lt(a: u32, b: u32):     a <  b => ct_u32(a).clt(&ct_u32(b));
    test_u32_le(a: u32, b: u32):     a <= b => ct_u32(a).cle(&ct_u32(b));
    test_u32_gt(a: u32, b: u32):     a >  b => ct_u32(a).cgt(&ct_u32(b));
    test_u32_ge(a: u32, b: u32):     a >= b => ct_u32(a).cge(&ct_u32(b));
    test_u32_is_zero(a: u32):        a == 0 => ct_u32(a).is_zero();
    test_u32_is_nonzero(a: u32):     a != 0 => ct_u32(a).is_nonzero();

    test_u64_eq(a: u64, b: u64):     a == b => ct_u64(a).ceq(&ct_u64(b));
    test_u64_ne(a: u64, b: u64):     a != b => ct_u64(a).cne(&ct_u64(b));
    test_u64_lt(a: u64, b: u64):     a <  b => ct_u64(a).clt(&ct_u64(b));
    test_u64_le(a: u64, b: u64):     a <= b => ct_u64(a).cle(&ct_u64(b));
    test_u64_gt(a: u64, b: u64):     a >  b => ct_u64(a).cgt(&ct_u64(b));
    test_u64_ge(a: u64, b: u64):     a >= b => ct_u64(a).cge(&ct_u64(b));
    test_u64_is_zero(a: u64):        a == 0 => ct_u64(a).is_zero();
    test_u64_is_nonzero(a: u64):     a != 0 => ct_u64(a).is_nonzero();

    test_uint_eq(a: uint, b: uint):  a == b => ct_uint(a).ceq(&ct_uint(b));
    test_uint_ne(a: uint, b: uint):  a != b => ct_uint(a).cne(&ct_uint(b));
    test_uint_lt(a: uint, b: uint):  a <  b => ct_uint(a).clt(&ct_uint(b));
    test_uint_le(a: uint, b: uint):  a <= b => ct_uint(a).cle(&ct_uint(b));
    test_uint_gt(a: uint, b: uint):  a >  b => ct_uint(a).cgt(&ct_uint(b));
    test_uint_ge(a: uint, b: uint):  a >= b => ct_uint(a).cge(&ct_uint(b));
    test_uint_is_zero(a: uint):      a == 0 => ct_uint(a).is_zero();
    test_uint_is_nonzero(a: uint):   a != 0 => ct_uint(a).is_nonzero();

    test_i8_eq(a: i8, b: i8):        a == b => ct_i8(a).ceq(&ct_i8(b));
    test_i8_ne(a: i8, b: i8):        a != b => ct_i8(a).cne(&ct_i8(b));
    test_i8_lt(a: i8, b: i8):        a <  b => ct_i8(a).clt(&ct_i8(b));
    test_i8_le(a: i8, b: i8):        a <= b => ct_i8(a).cle(&ct_i8(b));
    test_i8_gt(a: i8, b: i8):        a >  b => ct_i8(a).cgt(&ct_i8(b));
    test_i8_ge(a: i8, b: i8):        a >= b => ct_i8(a).cge(&ct_i8(b));
    test_i8_is_zero(a: i8):          a == 0 => ct_i8(a).is_zero();
    test_i8_is_pos(a: i8):           a >  0 => ct_i8(a).is_positive();
    test_i8_is_neg(a: i8):           a <  0 => ct_i8(a).is_negative();
    test_i8_is_nonzero(a: i8):       a != 0 => ct_i8(a).is_nonzero();
    test_i8_is_nonpos(a: i8):        a <= 0 => ct_i8(a).is_nonpositive();
    test_i8_is_nonneg(a: i8):        a >= 0 => ct_i8(a).is_nonnegative();

    test_i16_eq(a: i16, b: i16):     a == b => ct_i16(a).ceq(&ct_i16(b));
    test_i16_ne(a: i16, b: i16):     a != b => ct_i16(a).cne(&ct_i16(b));
    test_i16_lt(a: i16, b: i16):     a <  b => ct_i16(a).clt(&ct_i16(b));
    test_i16_le(a: i16, b: i16):     a <= b => ct_i16(a).cle(&ct_i16(b));
    test_i16_gt(a: i16, b: i16):     a >  b => ct_i16(a).cgt(&ct_i16(b));
    test_i16_ge(a: i16, b: i16):     a >= b => ct_i16(a).cge(&ct_i16(b));
    test_i16_is_zero(a: i16):        a == 0 => ct_i16(a).is_zero();
    test_i16_is_pos(a: i16):         a >  0 => ct_i16(a).is_positive();
    test_i16_is_neg(a: i16):         a <  0 => ct_i16(a).is_negative();
    test_i16_is_nonzero(a: i16):     a != 0 => ct_i16(a).is_nonzero();
    test_i16_is_nonpos(a: i16):      a <= 0 => ct_i16(a).is_nonpositive();
    test_i16_is_nonneg(a: i16):      a >= 0 => ct_i16(a).is_nonnegative();

    test_i32_eq(a: i32, b: i32):     a == b => ct_i32(a).ceq(&ct_i32(b));
    test_i32_ne(a: i32, b: i32):     a != b => ct_i32(a).cne(&ct_i32(b));
    test_i32_lt(a: i32, b: i32):     a <  b => ct_i32(a).clt(&ct_i32(b));
    test_i32_le(a: i32, b: i32):     a <= b => ct_i32(a).cle(&ct_i32(b));
    test_i32_gt(a: i32, b: i32):     a >  b => ct_i32(a).cgt(&ct_i32(b));
    test_i32_ge(a: i32, b: i32):     a >= b => ct_i32(a).cge(&ct_i32(b));
    test_i32_is_zero(a: i32):        a == 0 => ct_i32(a).is_zero();
    test_i32_is_pos(a: i32):         a >  0 => ct_i32(a).is_positive();
    test_i32_is_neg(a: i32):         a <  0 => ct_i32(a).is_negative();
    test_i32_is_nonzero(a: i32):     a != 0 => ct_i32(a).is_nonzero();
    test_i32_is_nonpos(a: i32):      a <= 0 => ct_i32(a).is_nonpositive();
    test_i32_is_nonneg(a: i32):      a >= 0 => ct_i32(a).is_nonnegative();

    test_i64_eq(a: i64, b: i64):     a == b => ct_i64(a).ceq(&ct_i64(b));
    test_i64_ne(a: i64, b: i64):     a != b => ct_i64(a).cne(&ct_i64(b));
    test_i64_lt(a: i64, b: i64):     a <  b => ct_i64(a).clt(&ct_i64(b));
    test_i64_le(a: i64, b: i64):     a <= b => ct_i64(a).cle(&ct_i64(b));
    test_i64_gt(a: i64, b: i64):     a >  b => ct_i64(a).cgt(&ct_i64(b));
    test_i64_ge(a: i64, b: i64):     a >= b => ct_i64(a).cge(&ct_i64(b));
    test_i64_is_zero(a: i64):        a == 0 => ct_i64(a).is_zero();
    test_i64_is_pos(a: i64):         a >  0 => ct_i64(a).is_positive();
    test_i64_is_neg(a: i64):         a <  0 => ct_i64(a).is_negative();
    test_i64_is_nonzero(a: i64):     a != 0 => ct_i64(a).is_nonzero();
    test_i64_is_nonpos(a: i64):      a <= 0 => ct_i64(a).is_nonpositive();
    test_i64_is_nonneg(a: i64):      a >= 0 => ct_i64(a).is_nonnegative();

    test_int_eq(a: int, b: int):     a == b => ct_int(a).ceq(&ct_int(b));
    test_int_ne(a: int, b: int):     a != b => ct_int(a).cne(&ct_int(b));
    test_int_lt(a: int, b: int):     a <  b => ct_int(a).clt(&ct_int(b));
    test_int_le(a: int, b: int):     a <= b => ct_int(a).cle(&ct_int(b));
    test_int_gt(a: int, b: int):     a >  b => ct_int(a).cgt(&ct_int(b));
    test_int_ge(a: int, b: int):     a >= b => ct_int(a).cge(&ct_int(b));
    test_int_is_zero(a: int):        a == 0 => ct_int(a).is_zero();
    test_int_is_pos(a: int):         a >  0 => ct_int(a).is_positive();
    test_int_is_neg(a: int):         a <  0 => ct_int(a).is_negative();
    test_int_is_nonzero(a: int):     a != 0 => ct_int(a).is_nonzero();
    test_int_is_nonpos(a: int):      a <= 0 => ct_int(a).is_nonpositive();
    test_int_is_nonneg(a: int):      a >= 0 => ct_int(a).is_nonnegative();

    test_bool_not(a: bool):          !a => !ct_bool(a);
    test_bool_and(a: bool, b: bool): a & b => ct_bool(a) & ct_bool(b);
    test_bool_or(a: bool, b: bool):  a | b => ct_bool(a) | ct_bool(b);
    test_bool_xor(a: bool, b: bool): a ^ b => ct_bool(a) ^ ct_bool(b);
    test_bool_choose(a: bool, b: int, c: int):
        if a {b} else {c} => ct_bool(a).choose(ct_int(b), ct_int(c));
}

#[test]
fn test_array3_get() {
    use quickcheck::TestResult;
    fn prop((a, b, c): (int, int, int), i: uint) -> TestResult {
        if i >= 3 { return TestResult::discard(); }
        let v = [a, b, c];
        let cv: ct_array<[ct_int, ..3]> = ct(v);
        TestResult::from_bool(v[i] == cv.get(ct_uint(i)).unwrap())
    }
    quickcheck::quickcheck(prop);
}

#[test]
fn test_array3_put() {
    use quickcheck::TestResult;
    fn prop((a, b, c): (int, int, int), i: uint, x: int) -> TestResult {
        if i >= 3 { return TestResult::discard(); }
        let mut v = [a, b, c];
        let mut cv: ct_array<[ct_int, ..3]> = ct(v);
        v[i] = x;
        cv.put(ct_uint(i), ct_int(x));
        TestResult::from_bool(v == cv.unwrap())
    }
    quickcheck::quickcheck(prop);
}

#[quickcheck]
fn test_array3_ceq((a, b, c): (int, int, int), (d, e, f): (int, int, int)) -> bool {
    let cv: ct_array<[ct_int, ..3]> = ct([a, b, c]);
    let cw: ct_array<[ct_int, ..3]> = ct([d, e, f]);
    ((a, b, c) == (d, e, f)) == (cv.ceq(&cw)).unwrap()
}

#[quickcheck]
fn test_array3_clt((a, b, c): (int, int, int), (d, e, f): (int, int, int)) -> bool {
    let cv: ct_array<[ct_int, ..3]> = ct([a, b, c]);
    let cw: ct_array<[ct_int, ..3]> = ct([d, e, f]);
    ((a, b, c) < (d, e, f)) == (cv.clt(&cw)).unwrap()
}

#[quickcheck]
fn test_array3_cle((a, b, c): (int, int, int), (d, e, f): (int, int, int)) -> bool {
    let cv: ct_array<[ct_int, ..3]> = ct([a, b, c]);
    let cw: ct_array<[ct_int, ..3]> = ct([d, e, f]);
    ((a, b, c) <= (d, e, f)) == (cv.cle(&cw)).unwrap()
}

#[test]
fn test_readme() {
    use std::int;

    // `ct_*` types provide guaranteed constant time operations.
    // they can be constructed via the function of the same name...
    let a = ct_int(42);

    // or the `ct` generic function.
    // this is a bit cumbersome but `ct_array` should be constructed in this way.
    let b: ct_int = ct(54);

    // the constant-time operations propagate to the return type.
    // for this reason, `ct_*` types do not implement some built-in traits.
    let a_plus_b: ct_int = a + b;
    let a_xor_b: ct_int = a ^ b;
    let not_a: ct_int = !a;
    //let a_lt_b = a < b;
    let a_lt_b: ct_bool = a.clt(&b); // we need ct_bool here, so we can't implement Ord

    // use `unwrap` to return the inner value.
    // this is the only method which does not implement the propagation.
    assert_eq!(a_plus_b.unwrap(), 96);
    assert_eq!(a_xor_b.unwrap(), 28);
    assert_eq!(not_a.unwrap(), !42);
    assert_eq!(a_lt_b.unwrap(), true);

    // one should replace `if a {b} else {c}` with `ct_bool::choose`.
    // (yes, I know this is really cumbersome...)
    let larger = a.cgt(&b).choose(a, b);
    assert_eq!(larger.unwrap(), 54);

    // `ct_array` is a bit special, as it has to be constructed via `ct`.
    // it prevents the cache-timing attacks, and always loads and stores the whole array.
    let mut arr: ct_array<[ct_int, ..4]> = ct([64i, 25i, 81i, 16i]);
    assert_eq!(arr.get(ct_uint(1)).unwrap(), 25);
    arr.put(ct_uint(1), ct_int(49));
    assert_eq!(arr.get(ct_uint(1)).unwrap(), 49);

    // one should use `ct_array::iter` or `ct_array::mut_iter` to manipulate the array.
    let mut max = ct_int(int::MIN);
    arr.iter(|_i, v| {
        max = v.clt(&max).choose(max, v);
    });
    assert_eq!(max.unwrap(), 81);
}

UNLICENSE

This is free and unencumbered software released into the public domain.

Anyone is free to copy, modify, publish, use, compile, sell, or
distribute this software, either in source code form or as a compiled
binary, for any purpose, commercial or non-commercial, and by any
means.

In jurisdictions that recognize copyright laws, the author or authors
of this software dedicate any and all copyright interest in the
software to the public domain. We make this dedication for the benefit
of the public at large and to the detriment of our heirs and
successors. We intend this dedication to be an overt act of
relinquishment in perpetuity of all present and future rights to this
software under copyright law.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.