Improve the SHA-1 implementation

* Rename struct Sha1State to Sha1
* Remove all use of @ types
* Use fixed length vectors
* Move all of the inner functions from inside sha1() to top level, private functions
* Sha1 instances are now created via Sha1::new()
* Update all constant names to uppercase
* Remove unecessary assert_eq!s
* Remove check_vec_eq() helper function; use vec::eq() instead

2 files changed, 206 insertions, 237 deletions

diff --git a/src/libextra/crypto/sha1.rs b/src/libextra/crypto/sha1.rs
index 84b48c87890..01e210803cf 100644
--- a/src/libextra/crypto/sha1.rs
+++ b/src/libextra/crypto/sha1.rs
@@ -25,7 +25,6 @@
 use core::prelude::*;
 
 use core::uint;
-use core::vec;
 
 /*
  * A SHA-1 implementation derived from Paul E. Jones's reference
@@ -33,250 +32,230 @@ use core::vec;
  * point this will want to be rewritten.
  */
 
-/// The SHA-1 interface
-trait Sha1 {
-    /// Provide message input as bytes
-    fn input(&mut self, &[u8]);
-    /// Provide message input as string
-    fn input_str(&mut self, &str);
-    /**
-     * Read the digest as a vector of 20 bytes. After calling this no further
-     * input may be provided until reset is called.
-     */
-    fn result(&mut self) -> ~[u8];
-    /**
-     * Read the digest as a hex string. After calling this no further
-     * input may be provided until reset is called.
-     */
-    fn result_str(&mut self) -> ~str;
-    /// Reset the SHA-1 state for reuse
-    fn reset(&mut self);
-}
-
 // Some unexported constants
-static digest_buf_len: uint = 5u;
-static msg_block_len: uint = 64u;
-static work_buf_len: uint = 80u;
-static k0: u32 = 0x5A827999u32;
-static k1: u32 = 0x6ED9EBA1u32;
-static k2: u32 = 0x8F1BBCDCu32;
-static k3: u32 = 0xCA62C1D6u32;
-
+static DIGEST_BUF_LEN: uint = 5u;
+static MSG_BLOCK_LEN: uint = 64u;
+static WORK_BUF_LEN: uint = 80u;
+static K0: u32 = 0x5A827999u32;
+static K1: u32 = 0x6ED9EBA1u32;
+static K2: u32 = 0x8F1BBCDCu32;
+static K3: u32 = 0xCA62C1D6u32;
 
-/// Construct a `sha` object
-pub fn sha1() -> @Sha1 {
-    struct Sha1State
-        { h: ~[u32],
-          len_low: u32,
-          len_high: u32,
-          msg_block: ~[u8],
-          msg_block_idx: uint,
-          computed: bool,
-          work_buf: @mut ~[u32]};
+/// Structure representing the state of a Sha1 computation
+pub struct Sha1 {
+    priv h: [u32, ..DIGEST_BUF_LEN],
+    priv len_low: u32,
+    priv len_high: u32,
+    priv msg_block: [u8, ..MSG_BLOCK_LEN],
+    priv msg_block_idx: uint,
+    priv computed: bool,
+    priv work_buf: [u32, ..WORK_BUF_LEN]
+}
 
-    fn add_input(st: &mut Sha1State, msg: &[u8]) {
-        assert!((!st.computed));
-        for msg.iter().advance |element| {
-            st.msg_block[st.msg_block_idx] = *element;
-            st.msg_block_idx += 1u;
-            st.len_low += 8u32;
-            if st.len_low == 0u32 {
-                st.len_high += 1u32;
-                if st.len_high == 0u32 {
-                    // FIXME: Need better failure mode (#2346)
-                    fail!();
-                }
+fn add_input(st: &mut Sha1, msg: &[u8]) {
+    assert!((!st.computed));
+    for msg.iter().advance |element| {
+        st.msg_block[st.msg_block_idx] = *element;
+        st.msg_block_idx += 1;
+        st.len_low += 8;
+        if st.len_low == 0 {
+            st.len_high += 1;
+            if st.len_high == 0 {
+                // FIXME: Need better failure mode (#2346)
+                fail!();
             }
-            if st.msg_block_idx == msg_block_len { process_msg_block(st); }
         }
+        if st.msg_block_idx == MSG_BLOCK_LEN { process_msg_block(st); }
     }
-    fn process_msg_block(st: &mut Sha1State) {
-        assert_eq!(st.h.len(), digest_buf_len);
-        assert_eq!(st.work_buf.len(), work_buf_len);
-        let mut t: int; // Loop counter
-        let w = st.work_buf;
+}
 
-        // Initialize the first 16 words of the vector w
-        t = 0;
-        while t < 16 {
-            let mut tmp;
-            tmp = (st.msg_block[t * 4] as u32) << 24u32;
-            tmp = tmp | (st.msg_block[t * 4 + 1] as u32) << 16u32;
-            tmp = tmp | (st.msg_block[t * 4 + 2] as u32) << 8u32;
-            tmp = tmp | (st.msg_block[t * 4 + 3] as u32);
-            w[t] = tmp;
-            t += 1;
-        }
+fn process_msg_block(st: &mut Sha1) {
+    let mut t: int; // Loop counter
+    let mut w = st.work_buf;
 
-        // Initialize the rest of vector w
-        while t < 80 {
-            let val = w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16];
-            w[t] = circular_shift(1u32, val);
-            t += 1;
-        }
-        let mut a = st.h[0];
-        let mut b = st.h[1];
-        let mut c = st.h[2];
-        let mut d = st.h[3];
-        let mut e = st.h[4];
-        let mut temp: u32;
-        t = 0;
-        while t < 20 {
-            temp = circular_shift(5u32, a) + (b & c | !b & d) + e + w[t] + k0;
-            e = d;
-            d = c;
-            c = circular_shift(30u32, b);
-            b = a;
-            a = temp;
-            t += 1;
-        }
-        while t < 40 {
-            temp = circular_shift(5u32, a) + (b ^ c ^ d) + e + w[t] + k1;
-            e = d;
-            d = c;
-            c = circular_shift(30u32, b);
-            b = a;
-            a = temp;
-            t += 1;
-        }
-        while t < 60 {
-            temp =
-                circular_shift(5u32, a) + (b & c | b & d | c & d) + e + w[t] +
-                    k2;
-            e = d;
-            d = c;
-            c = circular_shift(30u32, b);
-            b = a;
-            a = temp;
-            t += 1;
-        }
-        while t < 80 {
-            temp = circular_shift(5u32, a) + (b ^ c ^ d) + e + w[t] + k3;
-            e = d;
-            d = c;
-            c = circular_shift(30u32, b);
-            b = a;
-            a = temp;
-            t += 1;
-        }
-        st.h[0] = st.h[0] + a;
-        st.h[1] = st.h[1] + b;
-        st.h[2] = st.h[2] + c;
-        st.h[3] = st.h[3] + d;
-        st.h[4] = st.h[4] + e;
-        st.msg_block_idx = 0u;
+    // Initialize the first 16 words of the vector w
+    t = 0;
+    while t < 16 {
+        let mut tmp;
+        tmp = (st.msg_block[t * 4] as u32) << 24u32;
+        tmp = tmp | (st.msg_block[t * 4 + 1] as u32) << 16u32;
+        tmp = tmp | (st.msg_block[t * 4 + 2] as u32) << 8u32;
+        tmp = tmp | (st.msg_block[t * 4 + 3] as u32);
+        w[t] = tmp;
+        t += 1;
     }
-    fn circular_shift(bits: u32, word: u32) -> u32 {
-        return word << bits | word >> 32u32 - bits;
+
+    // Initialize the rest of vector w
+    while t < 80 {
+        let val = w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16];
+        w[t] = circular_shift(1, val);
+        t += 1;
     }
-    fn mk_result(st: &mut Sha1State) -> ~[u8] {
-        if !(*st).computed { pad_msg(st); (*st).computed = true; }
-        let mut rs: ~[u8] = ~[];
-        for st.h.mut_iter().advance |ptr_hpart| {
-            let hpart = *ptr_hpart;
-            let a = (hpart >> 24u32 & 0xFFu32) as u8;
-            let b = (hpart >> 16u32 & 0xFFu32) as u8;
-            let c = (hpart >> 8u32 & 0xFFu32) as u8;
-            let d = (hpart & 0xFFu32) as u8;
-            rs = vec::append(copy rs, [a, b, c, d]);
-        }
-        return rs;
+    let mut a = st.h[0];
+    let mut b = st.h[1];
+    let mut c = st.h[2];
+    let mut d = st.h[3];
+    let mut e = st.h[4];
+    let mut temp: u32;
+    t = 0;
+    while t < 20 {
+        temp = circular_shift(5, a) + (b & c | !b & d) + e + w[t] + K0;
+        e = d;
+        d = c;
+        c = circular_shift(30, b);
+        b = a;
+        a = temp;
+        t += 1;
+    }
+    while t < 40 {
+        temp = circular_shift(5, a) + (b ^ c ^ d) + e + w[t] + K1;
+        e = d;
+        d = c;
+        c = circular_shift(30, b);
+        b = a;
+        a = temp;
+        t += 1;
+    }
+    while t < 60 {
+        temp =
+            circular_shift(5, a) + (b & c | b & d | c & d) + e + w[t] +
+                K2;
+        e = d;
+        d = c;
+        c = circular_shift(30, b);
+        b = a;
+        a = temp;
+        t += 1;
+    }
+    while t < 80 {
+        temp = circular_shift(5, a) + (b ^ c ^ d) + e + w[t] + K3;
+        e = d;
+        d = c;
+        c = circular_shift(30, b);
+        b = a;
+        a = temp;
+        t += 1;
+    }
+    st.h[0] = st.h[0] + a;
+    st.h[1] = st.h[1] + b;
+    st.h[2] = st.h[2] + c;
+    st.h[3] = st.h[3] + d;
+    st.h[4] = st.h[4] + e;
+    st.msg_block_idx = 0;
+}
+
+fn circular_shift(bits: u32, word: u32) -> u32 {
+    return word << bits | word >> 32u32 - bits;
+}
+
+fn mk_result(st: &mut Sha1) -> ~[u8] {
+    if !st.computed { pad_msg(st); st.computed = true; }
+    let mut rs: ~[u8] = ~[];
+    for st.h.mut_iter().advance |ptr_hpart| {
+        let hpart = *ptr_hpart;
+        let a = (hpart >> 24u32 & 0xFFu32) as u8;
+        let b = (hpart >> 16u32 & 0xFFu32) as u8;
+        let c = (hpart >> 8u32 & 0xFFu32) as u8;
+        let d = (hpart & 0xFFu32) as u8;
+        rs = vec::append(copy rs, [a, b, c, d]);
     }
+    return rs;
+}
 
+/*
+ * According to the standard, the message must be padded to an even
+ * 512 bits.  The first padding bit must be a '1'.  The last 64 bits
+ * represent the length of the original message.  All bits in between
+ * should be 0.  This function will pad the message according to those
+ * rules by filling the msg_block vector accordingly.  It will also
+ * call process_msg_block() appropriately.  When it returns, it
+ * can be assumed that the message digest has been computed.
+ */
+fn pad_msg(st: &mut Sha1) {
     /*
-     * According to the standard, the message must be padded to an even
-     * 512 bits.  The first padding bit must be a '1'.  The last 64 bits
-     * represent the length of the original message.  All bits in between
-     * should be 0.  This function will pad the message according to those
-     * rules by filling the msg_block vector accordingly.  It will also
-     * call process_msg_block() appropriately.  When it returns, it
-     * can be assumed that the message digest has been computed.
+     * Check to see if the current message block is too small to hold
+     * the initial padding bits and length.  If so, we will pad the
+     * block, process it, and then continue padding into a second block.
      */
-    fn pad_msg(st: &mut Sha1State) {
-        assert_eq!((*st).msg_block.len(), msg_block_len);
-
-        /*
-         * Check to see if the current message block is too small to hold
-         * the initial padding bits and length.  If so, we will pad the
-         * block, process it, and then continue padding into a second block.
-         */
-        if (*st).msg_block_idx > 55u {
-            (*st).msg_block[(*st).msg_block_idx] = 0x80u8;
-            (*st).msg_block_idx += 1u;
-            while (*st).msg_block_idx < msg_block_len {
-                (*st).msg_block[(*st).msg_block_idx] = 0u8;
-                (*st).msg_block_idx += 1u;
-            }
-            process_msg_block(st);
-        } else {
-            (*st).msg_block[(*st).msg_block_idx] = 0x80u8;
-            (*st).msg_block_idx += 1u;
-        }
-        while (*st).msg_block_idx < 56u {
-            (*st).msg_block[(*st).msg_block_idx] = 0u8;
-            (*st).msg_block_idx += 1u;
+    if st.msg_block_idx > 55 {
+        st.msg_block[st.msg_block_idx] = 0x80;
+        st.msg_block_idx += 1;
+        while st.msg_block_idx < MSG_BLOCK_LEN {
+            st.msg_block[st.msg_block_idx] = 0;
+            st.msg_block_idx += 1;
         }
-
-        // Store the message length as the last 8 octets
-        (*st).msg_block[56] = ((*st).len_high >> 24u32 & 0xFFu32) as u8;
-        (*st).msg_block[57] = ((*st).len_high >> 16u32 & 0xFFu32) as u8;
-        (*st).msg_block[58] = ((*st).len_high >> 8u32 & 0xFFu32) as u8;
-        (*st).msg_block[59] = ((*st).len_high & 0xFFu32) as u8;
-        (*st).msg_block[60] = ((*st).len_low >> 24u32 & 0xFFu32) as u8;
-        (*st).msg_block[61] = ((*st).len_low >> 16u32 & 0xFFu32) as u8;
-        (*st).msg_block[62] = ((*st).len_low >> 8u32 & 0xFFu32) as u8;
-        (*st).msg_block[63] = ((*st).len_low & 0xFFu32) as u8;
         process_msg_block(st);
+    } else {
+        st.msg_block[st.msg_block_idx] = 0x80;
+        st.msg_block_idx += 1;
+    }
+    while st.msg_block_idx < 56 {
+        st.msg_block[st.msg_block_idx] = 0u8;
+        st.msg_block_idx += 1;
     }
 
-    impl Sha1 for Sha1State {
-        fn reset(&mut self) {
-            assert_eq!(self.h.len(), digest_buf_len);
-            self.len_low = 0u32;
-            self.len_high = 0u32;
-            self.msg_block_idx = 0u;
-            self.h[0] = 0x67452301u32;
-            self.h[1] = 0xEFCDAB89u32;
-            self.h[2] = 0x98BADCFEu32;
-            self.h[3] = 0x10325476u32;
-            self.h[4] = 0xC3D2E1F0u32;
-            self.computed = false;
-        }
-        fn input(&mut self, msg: &[u8]) { add_input(self, msg); }
-        fn input_str(&mut self, msg: &str) {
-            add_input(self, msg.as_bytes());
-        }
-        fn result(&mut self) -> ~[u8] { return mk_result(self); }
-        fn result_str(&mut self) -> ~str {
-            let rr = mk_result(self);
-            let mut s = ~"";
-            for rr.iter().advance |b| {
-                let hex = uint::to_str_radix(*b as uint, 16u);
-                if hex.len() == 1 {
-                    s += "0";
-                }
-                s += hex;
+    // Store the message length as the last 8 octets
+    st.msg_block[56] = (st.len_high >> 24u32 & 0xFFu32) as u8;
+    st.msg_block[57] = (st.len_high >> 16u32 & 0xFFu32) as u8;
+    st.msg_block[58] = (st.len_high >> 8u32 & 0xFFu32) as u8;
+    st.msg_block[59] = (st.len_high & 0xFFu32) as u8;
+    st.msg_block[60] = (st.len_low >> 24u32 & 0xFFu32) as u8;
+    st.msg_block[61] = (st.len_low >> 16u32 & 0xFFu32) as u8;
+    st.msg_block[62] = (st.len_low >> 8u32 & 0xFFu32) as u8;
+    st.msg_block[63] = (st.len_low & 0xFFu32) as u8;
+    process_msg_block(st);
+}
+
+impl Sha1 {
+    /// Construct a `sha` object
+    pub fn new() -> Sha1 {
+        let mut st = Sha1 {
+            h: [0u32, ..DIGEST_BUF_LEN],
+            len_low: 0u32,
+            len_high: 0u32,
+            msg_block: [0u8, ..MSG_BLOCK_LEN],
+            msg_block_idx: 0,
+            computed: false,
+            work_buf: [0u32, ..WORK_BUF_LEN]
+        };
+        st.reset();
+        return st;
+    }
+    pub fn reset(&mut self) {
+        self.len_low = 0;
+        self.len_high = 0;
+        self.msg_block_idx = 0;
+        self.h[0] = 0x67452301u32;
+        self.h[1] = 0xEFCDAB89u32;
+        self.h[2] = 0x98BADCFEu32;
+        self.h[3] = 0x10325476u32;
+        self.h[4] = 0xC3D2E1F0u32;
+        self.computed = false;
+    }
+    pub fn input(&mut self, msg: &[u8]) { add_input(self, msg); }
+    pub fn input_str(&mut self, msg: &str) {
+        add_input(self, msg.as_bytes());
+    }
+    pub fn result(&mut self) -> ~[u8] { return mk_result(self); }
+    pub fn result_str(&mut self) -> ~str {
+        let rr = mk_result(self);
+        let mut s = ~"";
+        for rr.iter().advance() |b| {
+            let hex = uint::to_str_radix(*b as uint, 16u);
+            if hex.len() == 1 {
+                s += "0";
             }
-            return s;
+            s += hex;
         }
+        return s;
     }
-    let st = Sha1State {
-         h: vec::from_elem(digest_buf_len, 0u32),
-         len_low: 0u32,
-         len_high: 0u32,
-         msg_block: vec::from_elem(msg_block_len, 0u8),
-         msg_block_idx: 0u,
-         computed: false,
-         work_buf: @mut vec::from_elem(work_buf_len, 0u32)
-    };
-    let mut sh = @st as @Sha1;
-    sh.reset();
-    return sh;
 }
 
 #[cfg(test)]
 mod tests {
-    use sha1;
+    use core::vec;
+
+    use sha1::Sha1;
 
     #[test]
     fn test() {
@@ -361,24 +340,14 @@ mod tests {
             },
         ];
         let tests = fips_180_1_tests + wikipedia_tests;
-        fn check_vec_eq(v0: ~[u8], v1: ~[u8]) {
-            assert_eq!(v0.len(), v1.len());
-            let len = v0.len();
-            let mut i = 0u;
-            while i < len {
-                let a = v0[i];
-                let b = v1[i];
-                assert_eq!(a, b);
-                i += 1u;
-            }
-        }
+
         // Test that it works when accepting the message all at once
 
-        let mut sh = sha1::sha1();
+        let mut sh = ~Sha1::new();
         for tests.iter().advance |t| {
             sh.input_str(t.input);
             let out = sh.result();
-            check_vec_eq(copy t.output, out);
+            assert!(vec::eq(t.output, out));
 
             let out_str = sh.result_str();
             assert_eq!(out_str.len(), 40);
@@ -398,7 +367,7 @@ mod tests {
                 left = left - take;
             }
             let out = sh.result();
-            check_vec_eq(copy t.output, out);
+            assert!(vec::eq(t.output, out));
 
             let out_str = sh.result_str();
             assert_eq!(out_str.len(), 40);
diff --git a/src/libextra/workcache.rs b/src/libextra/workcache.rs
index 63c89ebf586..2ebf00c485e 100644
--- a/src/libextra/workcache.rs
+++ b/src/libextra/workcache.rs
@@ -13,7 +13,7 @@
 use core::prelude::*;
 
 use json;
-use sha1;
+use sha1::Sha1;
 use serialize::{Encoder, Encodable, Decoder, Decodable};
 use sort;
 
@@ -248,13 +248,13 @@ fn json_decode<T:Decodable<json::Decoder>>(s: &str) -> T {
 }
 
 fn digest<T:Encodable<json::Encoder>>(t: &T) -> ~str {
-    let mut sha = sha1::sha1();
+    let mut sha = Sha1::new();
     sha.input_str(json_encode(t));
     sha.result_str()
 }
 
 fn digest_file(path: &Path) -> ~str {
-    let mut sha = sha1::sha1();
+    let mut sha = Sha1::new();
     let s = io::read_whole_file_str(path);
     sha.input_str(*s.get_ref());
     sha.result_str()