gistfile1.txt

use std::cmp::Ordering;
use std::ops::{Add, Sub, Shl, Shr, Div, Not};

#[derive(Copy, Clone, PartialEq, Eq)]
struct Uint256([u64; 4]);

impl Uint256 {
    fn bits(&self) -> usize {
        for i in 1..4 {
            if self.0[4 - i] > 0 { return (0x40 * (4 - i + 1)) - self.0[4 - i].leading_zeros() as usize; }
        }
        0x40 - self.0[0].leading_zeros() as usize
    }
}

impl PartialOrd for Uint256 {
    fn partial_cmp(&self, other: &Uint256) -> Option<Ordering> {
        Some(self.cmp(&other))
    }
}

impl Ord for Uint256 {
    fn cmp(&self, other: &Uint256) -> Ordering {
        for i in 0..4 {
            if self.0[4 - 1 - i] < other.0[4 - 1 - i] { return Ordering::Less; }
            if self.0[4 - 1 - i] > other.0[4 - 1 - i] { return Ordering::Greater; }
        }
        Ordering::Equal
    }
}

impl Not for Uint256 {
    type Output = Uint256;

    fn not(self) -> Uint256 {
        let Uint256(ref arr) = self;
        let mut ret = [0u64; 4];
        for i in 0..4 {
            ret[i] = !arr[i];
        }
        Uint256(ret)
    }
}

impl Add<Uint256> for Uint256 {
    type Output = Uint256;

    fn add(self, other: Uint256) -> Uint256 {
        let Uint256(ref me) = self;
        let Uint256(ref you) = other;
        let mut ret = [0u64; 4];
        let mut carry = [0u64; 4];
        let mut b_carry = false;
        for i in 0..4 {
            ret[i] = me[i].wrapping_add(you[i]);
            if i < 4 - 1 && ret[i] < me[i] {
                carry[i + 1] = 1;
                b_carry = true;
            }
        }
        if b_carry { Uint256(ret) + Uint256(carry) } else { Uint256(ret) }
    }
}

impl Sub<Uint256> for Uint256 {
    type Output = Uint256;

    fn sub(self, other: Uint256) -> Uint256 {
        self + !other + Uint256([0,0,0,1])
    }
}

impl Shl<usize> for Uint256 {
    type Output = Uint256;

    fn shl(self, shift: usize) -> Uint256 {
        let Uint256(ref original) = self;
        let mut ret = [0u64; 4];
        let word_shift = shift / 64;
        let bit_shift = shift % 64;
        for i in 0..4 {
            // Shift
            if bit_shift < 64 && i + word_shift < 4 {
                ret[i + word_shift] += original[i] << bit_shift;
            }
            // Carry
            if bit_shift > 0 && i + word_shift + 1 < 4 {
                ret[i + word_shift + 1] += original[i] >> (64 - bit_shift);
            }
        }
        Uint256(ret)
    }
}

impl Shr<usize> for Uint256 {
    type Output = Uint256;

    fn shr(self, shift: usize) -> Uint256 {
        let Uint256(ref original) = self;
        let mut ret = [0u64; 4];
        let word_shift = shift / 64;
        let bit_shift = shift % 64;
        for i in word_shift..4 {
            // Shift
            ret[i - word_shift] += original[i] >> bit_shift;
            // Carry
            if bit_shift > 0 && i < 4 - 1 {
                ret[i - word_shift] += original[i + 1] << (64 - bit_shift);
            }
        }
        Uint256(ret)
    }
}


impl Div for Uint256 {
    type Output = Uint256;

    fn div(self, other: Uint256) -> Uint256 {
        let mut sub_copy = self;
        let mut shift_copy = other;
        let mut ret = [0u64; 4];

        let my_bits = self.bits();
        let your_bits = other.bits();

        // Check for division by 0
        assert!(your_bits != 0);

        // Early return in case we are dividing by a larger number than us
        if my_bits < your_bits {
            return Uint256(ret);
        }

        // Bitwise long division
        let mut shift = my_bits - your_bits;
        shift_copy = shift_copy << shift;
        loop {
            if sub_copy >= shift_copy {
                ret[shift / 64] |= 1 << (shift % 64);
                sub_copy = sub_copy - shift_copy;
            }
            shift_copy = shift_copy >> 1;
            if shift == 0 { break; }
            shift -= 1;
        }

        Uint256(ret)
    }
}

fn main() {
    println!("Hello, world!");
}