Boost logo

Boost-Commit :

Date view Thread view Subject view Author view

Subject: [Boost-commit] svn:boost r61902 - in sandbox/hash: boost boost/hash boost/hash/detail libs/hash/doc/html libs/hash/test
From: me22.ca+boost_at_[hidden]
Date: 2010-05-11 00:32:14

Author: smcmurray
Date: 2010-05-11 00:32:08 EDT (Tue, 11 May 2010)
New Revision: 61902
URL: http://svn.boost.org/trac/boost/changeset/61902

Log:
hash: Add a wrapper around Boost.CRC
Added:
   sandbox/hash/boost/hash/crc.hpp (contents, props changed)
   sandbox/hash/libs/hash/test/crc.cpp (contents, props changed)
Text files modified:
   sandbox/hash/boost/hash.hpp | 1
   sandbox/hash/boost/hash/adler.hpp | 2 -
   sandbox/hash/boost/hash/compute_digest.hpp | 57 ++++++++++++++++++++++++++++++++++++++++
   sandbox/hash/boost/hash/detail/primes.hpp | 2
   sandbox/hash/libs/hash/doc/html/concepts.html | 5 +++
   sandbox/hash/libs/hash/doc/html/performance.html | 8 ++++
   sandbox/hash/libs/hash/doc/html/quickstart.html | 11 +++++++
   7 files changed, 81 insertions(+), 5 deletions(-)

Modified: sandbox/hash/boost/hash.hpp
==============================================================================
--- sandbox/hash/boost/hash.hpp (original)
+++ sandbox/hash/boost/hash.hpp 2010-05-11 00:32:08 EDT (Tue, 11 May 2010)
@@ -11,6 +11,7 @@
 
 // Checksums
 #include <boost/hash/adler.hpp>
+#include <boost/hash/crc.hpp>
 
 // Cryptographic Hashes
 #include <boost/hash/cubehash.hpp>

Modified: sandbox/hash/boost/hash/adler.hpp
==============================================================================
--- sandbox/hash/boost/hash/adler.hpp (original)
+++ sandbox/hash/boost/hash/adler.hpp 2010-05-11 00:32:08 EDT (Tue, 11 May 2010)
@@ -14,8 +14,6 @@
 #include <boost/hash/pack.hpp>
 #include <boost/static_assert.hpp>
 
-#include <limits>
-
 #ifdef BOOST_HASH_SHOW_PROGRESS
 #include <cstdio>
 #endif

Modified: sandbox/hash/boost/hash/compute_digest.hpp
==============================================================================
--- sandbox/hash/boost/hash/compute_digest.hpp (original)
+++ sandbox/hash/boost/hash/compute_digest.hpp 2010-05-11 00:32:08 EDT (Tue, 11 May 2010)
@@ -96,6 +96,63 @@
     return compute_digest_n<hash_T>(p, std::wcslen(p));
 }
 
+template <typename hash_T>
+struct digest_computer {
+ typedef typename hash_T::digest_type digest_type;
+ template <typename T>
+ digest_type operator()(T const &t) {
+ return compute_digest<hash_T>(t);
+ }
+ template <typename T, typename U>
+ digest_type operator()(T const &t, U const &u) {
+ return compute_digest<hash_T>(t, u);
+ }
+};
+
+template <typename hash_T>
+digest_computer<hash_T>
+compute_digest() {
+ return digest_computer<hash_T>();
+}
+
+template <typename hash_T>
+struct digest_computer_n {
+ typedef typename hash_T::digest_type digest_type;
+ template <typename T>
+ digest_type operator()(T const &t) {
+ return compute_digest_n<hash_T>(t);
+ }
+ template <typename T, typename U>
+ digest_type operator()(T const &t, U const &u) {
+ return compute_digest_n<hash_T>(t, u);
+ }
+};
+
+template <typename hash_T>
+digest_computer_n<hash_T>
+compute_digest_n() {
+ return digest_computer_n<hash_T>();
+}
+
+template <typename hash_T>
+struct digest_computer_data {
+ typedef typename hash_T::digest_type digest_type;
+ template <typename T>
+ digest_type operator()(T const &t) {
+ return compute_digest_data<hash_T>(t);
+ }
+ template <typename T, typename U>
+ digest_type operator()(T const &t, U const &u) {
+ return compute_digest_data<hash_T>(t, u);
+ }
+};
+
+template <typename hash_T>
+digest_computer_data<hash_T>
+compute_digest_data() {
+ return digest_computer_data<hash_T>();
+}
+
 } // namespace hash
 } // namespace boost
 

Added: sandbox/hash/boost/hash/crc.hpp
==============================================================================
--- (empty file)
+++ sandbox/hash/boost/hash/crc.hpp 2010-05-11 00:32:08 EDT (Tue, 11 May 2010)
@@ -0,0 +1,155 @@
+
+//
+// Copyright 2010 Scott McMurray.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+
+#ifndef BOOST_HASH_CRC_HPP
+#define BOOST_HASH_CRC_HPP
+
+#include <boost/crc.hpp>
+#include <boost/hash/detail/primes.hpp>
+#include <boost/hash/digest.hpp>
+#include <boost/hash/pack.hpp>
+#include <boost/static_assert.hpp>
+
+#include <climits>
+
+#ifdef BOOST_HASH_SHOW_PROGRESS
+#include <cstdio>
+#endif
+
+namespace boost {
+namespace hash {
+
+// Boost.CRC undefs this, so re-define it
+#define BOOST_CRC_PARM_TYPE typename ::boost::uint_t<Bits>::fast
+
+template <unsigned Bits, BOOST_CRC_PARM_TYPE TruncPoly = 0u,
+ BOOST_CRC_PARM_TYPE InitRem = 0u, BOOST_CRC_PARM_TYPE FinalXor = 0u,
+ bool ReflectIn = false, bool ReflectRem = false >
+class basic_crc {
+ public:
+ typedef crc_optimal<Bits, TruncPoly,
+ InitRem, FinalXor,
+ ReflectIn, ReflectRem> crc_computer;
+ typedef typename crc_computer::value_type word_type;
+
+ static unsigned const value_bits = CHAR_BIT;
+ typedef uint_t<value_bits>::least value_type;
+
+ BOOST_STATIC_ASSERT(Bits >= value_bits);
+
+ static unsigned const digest_bits = Bits;
+ typedef hash::digest<digest_bits> digest_type;
+
+ public:
+ basic_crc() { reset(); }
+ void reset() { crc_.reset(); }
+
+ digest_type digest() const {
+ word_type x = crc_.checksum();
+ digest_type d;
+ // TODO: Justify bit order
+ pack_n<stream_endian::big_bit,
+ digest_bits,
+ octet_bits>(&x, 1,
+ d.data(), digest_bits/octet_bits);
+ return d;
+ }
+
+ digest_type end_message() {
+ digest_type d = digest();
+ reset();
+ return d;
+ }
+
+ public:
+ basic_crc &
+ update_one(value_type x) {
+#ifdef BOOST_HASH_SHOW_PROGRESS
+printf("%.8lx + %.2x ==> ", (long)crc_.checksum(), (int)x);
+#endif
+ crc_.process_byte(x);
+#ifdef BOOST_HASH_SHOW_PROGRESS
+printf("%.8lx\n", (long)crc_.checksum());
+#endif
+ return *this;
+ }
+
+ template <typename IterT>
+ basic_crc &
+ update_n(IterT p, size_t n) {
+ while (n--) update_one(*p++);
+ return *this;
+ }
+#ifndef BOOST_HASH_NO_OPTIMIZATION
+ template <typename ValT>
+ basic_crc &
+ update_n(ValT const *p, size_t n) {
+ if (sizeof(ValT) == 1) {
+ crc_.process_bytes(p, n);
+ } else {
+ while (n--) update_one(*p++);
+ }
+ return *this;
+ }
+ template <typename ValT>
+ basic_crc &
+ update_n(ValT *p, size_t n) {
+ return update_n((ValT const *)p, n);
+ }
+#endif
+
+ template <typename IterT>
+ basic_crc &
+ update(IterT b, IterT e, std::random_access_iterator_tag) {
+ return update_n(b, e-b);
+ }
+ template <typename IterT, typename Category>
+ basic_crc &
+ update(IterT b, IterT e, Category) {
+ while (b != e) update_one(*b++);
+ return *this;
+ }
+ template <typename IterT>
+ basic_crc &
+ update(IterT b, IterT e) {
+ typedef typename std::iterator_traits<IterT>::iterator_category cat;
+ return update(b, e, cat());
+ }
+
+ private:
+ crc_computer crc_;
+};
+
+template <unsigned Bits, BOOST_CRC_PARM_TYPE TruncPoly = 0u,
+ BOOST_CRC_PARM_TYPE InitRem = 0u, BOOST_CRC_PARM_TYPE FinalXor = 0u,
+ bool ReflectIn = false, bool ReflectRem = false >
+struct crc {
+ private:
+ typedef basic_crc<Bits, TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem>
+ octet_hash_type;
+ public:
+ template <unsigned value_bits>
+ struct stream_hash {
+ BOOST_STATIC_ASSERT(value_bits == CHAR_BIT);
+ typedef octet_hash_type type_;
+#ifdef BOOST_HASH_NO_HIDE_INTERNAL_TYPES
+ typedef type_ type;
+#else
+ struct type : type_ {};
+#endif
+ };
+ typedef typename octet_hash_type::digest_type digest_type;
+};
+
+// http://www.libpng.org/pub/png/spec/1.2/PNG-Structure.html#CRC-algorithm
+typedef crc<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true> crc32_png;
+
+} // namespace hash
+} // namespace boost
+
+#endif // BOOST_HASH_CRC_HPP

Modified: sandbox/hash/boost/hash/detail/primes.hpp
==============================================================================
--- sandbox/hash/boost/hash/detail/primes.hpp (original)
+++ sandbox/hash/boost/hash/detail/primes.hpp 2010-05-11 00:32:08 EDT (Tue, 11 May 2010)
@@ -22,7 +22,7 @@
 };
 template <>
 struct all_ones<0> {
- typedef typename uint_t<0>::least type;
+ typedef uint_t<0>::least type;
     static type const value = 0;
 };
 

Modified: sandbox/hash/libs/hash/doc/html/concepts.html
==============================================================================
--- sandbox/hash/libs/hash/doc/html/concepts.html (original)
+++ sandbox/hash/libs/hash/doc/html/concepts.html 2010-05-11 00:32:08 EDT (Tue, 11 May 2010)
@@ -34,6 +34,11 @@
     <TD>digest&lt;<i>h</i>&gt;</TD>
     </TR>
     <TR>
+ <TD>&lt;boost/hash/crc.hpp&gt;</TD>
+ <TD><tt>crc&lt;<i>h</i>, ...&gt;</tt>, with template arguments as for Boost.CRC's crc_optimal</TD>
+ <TD>digest&lt;<i>h</i>&gt;</TD>
+ </TR>
+ <TR>
     <TD>&lt;boost/hash/cubehash.hpp&gt;</TD>
     <TD><tt>cubehash&lt;<i>h</i>&gt;</tt>, <tt>cubehash&lt;<i>r</i>, <i>b</i>, <i>h</i>&gt;</tt>, with <i>h</i> in {8, 16, 24, ..., 512}, <i>r</i> in {1, 2, 3, ...} (default 16), <i>b</i> in {4, 8, 12, ..., 128} (default 32)</TD>
     <TD>digest&lt;<i>h</i>&gt;</TD>

Modified: sandbox/hash/libs/hash/doc/html/performance.html
==============================================================================
--- sandbox/hash/libs/hash/doc/html/performance.html (original)
+++ sandbox/hash/libs/hash/doc/html/performance.html 2010-05-11 00:32:08 EDT (Tue, 11 May 2010)
@@ -19,7 +19,7 @@
 </TR>
 <TR>
 <TD>SHA-1
-<TD>9.406
+<TD>9.406s
 <TD>16.119s
 <TD>73%
 </TR>
@@ -59,6 +59,12 @@
 <TD BGCOLOR="pink">2.013s
 </TR>
 <TR>
+<TD>CRC-32/PNG
+<TD>12.946s
+<TD>8.050s
+<TD BGCOLOR="pink">8.093s
+</TR>
+<TR>
 <TD>CubeHash16/32-512
 <TD>17.369s
 <TD>16.559s

Modified: sandbox/hash/libs/hash/doc/html/quickstart.html
==============================================================================
--- sandbox/hash/libs/hash/doc/html/quickstart.html (original)
+++ sandbox/hash/libs/hash/doc/html/quickstart.html 2010-05-11 00:32:08 EDT (Tue, 11 May 2010)
@@ -31,7 +31,16 @@
     <TD><tt>adler&lt;<i>h</i>&gt;</tt>
     <TD>RFC 1950
     <TD>Checksum
- <TD>&nbsp;
+ <TD>Only supports octets as input values
+ </TR>
+
+ <TR>
+ <TD>CRC-32/PNG
+ <TD>32
+ <TD><tt>crc32_png</tt>
+ <TD>PNG Specification, Section 3.4
+ <TD>Checksum
+ <TD>Also used by cksfv; Only supports bytes as input values
     </TR>
 
     <TR>

Added: sandbox/hash/libs/hash/test/crc.cpp
==============================================================================
--- (empty file)
+++ sandbox/hash/libs/hash/test/crc.cpp 2010-05-11 00:32:08 EDT (Tue, 11 May 2010)
@@ -0,0 +1,101 @@
+
+#include <boost/hash/crc.hpp>
+#include <boost/hash/compute_digest.hpp>
+#include <boost/hash/digest_io.hpp>
+
+#include <iostream>
+#include <string>
+
+#include <cassert>
+
+void test32() {
+ typedef boost::hash::crc32_png HASH;
+ using boost::hash::compute_digest;
+
+ // Messages from MD4/MD5 test vectors
+
+ {
+ HASH::digest_type d = compute_digest<HASH>("");
+ std::cout << d << "\n";
+ assert(d == "00000000");
+ }
+
+ // All with 1 MiB or less fo input checked against
+ // http://hash.online-convert.com/crc32b-generator
+ // All checked against cksfv utility
+ // http://www.iki.fi/shd/foss/cksfv/
+
+ {
+ HASH::digest_type d = compute_digest<HASH>("a");
+ std::cout << d << "\n";
+ assert(d == "e8b7be43");
+ }
+
+ {
+ HASH::digest_type d = compute_digest<HASH>("abc");
+ std::cout << d << "\n";
+ assert(d == "352441c2");
+ }
+
+ {
+ HASH::digest_type d = compute_digest<HASH>("message digest");
+ std::cout << d << "\n";
+ assert(d == "20159d7f");
+ }
+
+ {
+ HASH::digest_type d = compute_digest<HASH>("abcdefghijklmnopqrstuvwxyz");
+ std::cout << d << "\n";
+ assert(d == "4c2750bd");
+ }
+
+ {
+ HASH::digest_type d = compute_digest<HASH>("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789");
+ std::cout << d << "\n";
+ assert(d == "1fc2e6d2");
+ }
+
+ {
+ HASH::digest_type d = compute_digest<HASH>("12345678901234567890123456789012345678901234567890123456789012345678901234567890");
+ std::cout << d << "\n";
+ assert(d == "7ca94a72");
+ }
+
+#ifndef BOOST_HASH_SHOW_PROGRESS
+ {
+ HASH::stream_hash<8>::type sh;
+ for (unsigned i = 0; i < 1000000; ++i) sh.update_one('a');
+ HASH::digest_type d = sh.end_message();
+ std::cout << d << "\n";
+ assert(d == "dc25bfbc");
+ }
+
+ {
+ HASH::stream_hash<8>::type sh;
+ std::string s(1000, 'a');
+ for (unsigned i = 0; i < 1000000; ++i) sh.update_n(s.data(), s.size());
+ HASH::digest_type d = sh.end_message();
+ std::cout << d << "\n";
+ assert(d == "a7943e77");
+ }
+
+#ifndef QUICK
+ {
+ HASH::stream_hash<8>::type sh;
+ for (unsigned i = 0; i < 1000000000; ++i) sh.update_one('a');
+ HASH::digest_type d = sh.end_message();
+ std::cout << d << "\n";
+ assert(d == "a7943e77");
+ }
+#endif // QUICK
+#endif
+
+}
+
+int main() {
+ using namespace boost::hash;
+
+ test32();
+
+}
+

Date view Thread view Subject view Author view

Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk