|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r61801 - in sandbox/hash: boost/hash boost/hash/block_cyphers libs/hash libs/hash/doc/html libs/hash/example
From: me22.ca+boost_at_[hidden]
Date: 2010-05-05 18:07:46
Author: smcmurray
Date: 2010-05-05 18:07:45 EDT (Wed, 05 May 2010)
New Revision: 61801
URL: http://svn.boost.org/trac/boost/changeset/61801
Log:
hash: add documentation, more convenience function overloads, another example, and some missing licenses
Added:
sandbox/hash/libs/hash/doc/html/concepts.html (contents, props changed)
sandbox/hash/libs/hash/doc/html/functions.html (contents, props changed)
sandbox/hash/libs/hash/doc/html/performance.html (contents, props changed)
sandbox/hash/libs/hash/doc/html/quickstart.html (contents, props changed)
sandbox/hash/libs/hash/doc/html/validation.html (contents, props changed)
sandbox/hash/libs/hash/example/quickstart.cpp (contents, props changed)
sandbox/hash/libs/hash/index.html (contents, props changed)
Text files modified:
sandbox/hash/boost/hash/block_cyphers/shacal.hpp | 7 +++----
sandbox/hash/boost/hash/compute_digest.hpp | 39 +++++++++++++++++++++++++++++++++++++++
sandbox/hash/libs/hash/example/hashsum.cpp | 12 ++++++++++++
3 files changed, 54 insertions(+), 4 deletions(-)
Modified: sandbox/hash/boost/hash/block_cyphers/shacal.hpp
==============================================================================
--- sandbox/hash/boost/hash/block_cyphers/shacal.hpp (original)
+++ sandbox/hash/boost/hash/block_cyphers/shacal.hpp 2010-05-05 18:07:45 EDT (Wed, 05 May 2010)
@@ -26,10 +26,9 @@
namespace hash {
namespace block_cyphers {
-// The original FIPS-180 seems to be gone, but according to
-// http://www.derkeiler.com/Newsgroups/sci.crypt/2003-06/0017.html
-// the only difference in SHA(-0) is the lack of a rotation in the
-// key scheduling (which was borne out by test vectors).
+// The original FIPS-180 seems to be gone, but FIPS 180-1
+// (http://www.itl.nist.gov/fipspubs/fip180-1.htm) says the only change
+// in SHA-1 from SHA(-0) is the rotation in the key scheduling.
class shacal : public basic_shacal {
public:
shacal(key_type const &k)
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-05 18:07:45 EDT (Wed, 05 May 2010)
@@ -13,8 +13,10 @@
#include <iterator>
#include <limits>
+#include <string>
#include <cstring>
+#include <cwchar>
namespace boost {
namespace hash {
@@ -49,12 +51,49 @@
return sh.end_message();
}
+template <typename hash_T, typename container_T>
+typename hash_T::digest_type
+compute_digest(container_T const &c) {
+ return compute_digest<hash_T>(c.begin(), c.end());
+}
+
+template <typename hash_T, typename container_T>
+typename hash_T::digest_type
+compute_digest_n(container_T const &c) {
+ return compute_digest_n<hash_T>(c.begin(), c.size());
+}
+
+template <typename hash_T, typename container_T>
+typename hash_T::digest_type
+compute_digest_data(container_T const &c) {
+ return compute_digest_n<hash_T>(c.data(), c.size());
+}
+
+template <typename hash_T,
+ typename Char, typename CharTraits, typename Alloc>
+typename hash_T::digest_type
+compute_digest(std::basic_string<Char, CharTraits, Alloc> const &s) {
+ return compute_digest_data<hash_T>(s);
+}
+template <typename hash_T,
+ typename Char, typename CharTraits, typename Alloc>
+typename hash_T::digest_type
+compute_digest_n(std::basic_string<Char, CharTraits, Alloc> const &s) {
+ return compute_digest_data<hash_T>(s);
+}
+
template <typename hash_T>
typename hash_T::digest_type
compute_digest(char const *p) {
return compute_digest_n<hash_T>(p, std::strlen(p));
}
+template <typename hash_T>
+typename hash_T::digest_type
+compute_digest(wchar_t const *p) {
+ return compute_digest_n<hash_T>(p, std::wcslen(p));
+}
+
} // namespace hash
} // namespace boost
Added: sandbox/hash/libs/hash/doc/html/concepts.html
==============================================================================
--- (empty file)
+++ sandbox/hash/libs/hash/doc/html/concepts.html 2010-05-05 18:07:45 EDT (Wed, 05 May 2010)
@@ -0,0 +1,70 @@
+<html>
+<head>
+<title>The MaybeBoost Hash Library</title>
+<body>
+
+<P STYLE="float:right">Back to Index</P>
+
+<H2>The MaybeBoost Hash Library: Concepts</H2>
+
+<H3 id="hashpolicy"><tt>HashPolicy</tt> Concept</H3>
+
+<P>A type <tt>T</tt> modelling the <tt>HashPolicy</tt> concept must support the following:
+ <DL style="margin-left: 1em">
+ <DT><tt>T::stream_hash<<i>ValueBits</i>>::type</tt>
+ <DD>must model the <tt>StreamHash<<i>ValueBits</i>></tt> concept.
+ <DD>Not all possible values of <i>ValueBits</i> need be accepted. Typically, small powers of 2 (1, 2, 4, 8, 16, 32, 64) are accepted.
+ <DT><tt>T::digest_type</tt>
+ <DD>must model the <tt>MessageDigest</tt> concept
+ <DD>must match the <tt>digest_type</tt> of the <tt>StreamHash<<i>ValueBits</i>></tt> policies mentioned above for any allowed choice of <i>ValueBits</i>.
+ </DL>
+
+<P>Provided models:
+ <UL>
+ <LI>cubehash<<i>h</i>>, cubehash<<i>r</i>, <i>b</i>, <i>h</i>>, 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)
+ <LI>md4, md5
+ <LI>sha (or sha0), sha1
+ <li>sha2<<i>h</i>>, with <i>h</i> in {224, 256, 384, 512}
+ </UL>
+
+<H3 id="streamhash"><tt>StreamHash<<i>ValueBits</i>></tt> Concept</H3>
+
+<P>A type <tt>T</tt> modelling the <tt>StreamHash<<i>ValueBits</i>></tt> concept must support the following (<tt>h</tt> is an object of type <tt>T</tt>, <tt>hc</tt> is an object of type <tt>T const</tt>):
+
+ <DL style="margin-left: 1em">
+ <DT><tt>T::digest_type</tt>
+ <DD>models the <tt>MessageDigest</tt> concept
+ <DT><tt>T::value_type</tt>
+ <DD>an unsigned fundamental integral type that can hold least <i>ValueBits</i> bits
+ <DT><tt>T x;</tt>
+ <DD>default-constructible
+ <DT><tt>T x = h;</tt>
+ <DD>copy-constructible
+ <DT><tt>T x; x = h;</tt>
+ <DD>copy-assignable
+ <DT><tt>h.reset();</tt>
+ <DD>equivalent to <tt>h = T();</tt>
+ <DT><tt>T::digest_type d = h.end_message();</tt>
+ <DD>returns the digest of all input provided since the last reset, then resets
+ <DD>(equivalent to <tt>digest_type d = h.digest(); h.reset();</tt>, though typically more efficient if the hash involves padding or finalization)
+ <DT><tt>T::digest_type d = hc.digest();</tt>
+ <DD>returns the digest of all input provided since the last reset
+ <DD>(equivalent to <tt>digest_type d = T(hc).end_message();</tt>, though typically more efficient if the hash involves neither padding nor finalization)
+ <DT><tt>value_type x; h.update_one(x);</tt>
+ <DD>Feeds the low <i>ValueBits</i> bits of x as input to the hash algorithm
+ <DT><tt>InputIterator b, e; h.update(b, e);</tt>
+ <DD>Equivalent to <tt>for (InputIterator i = b; i != e; ++i) h.update_one(*i);</tt>
+ <DT><tt>InputIterator b; size_t n; h.update_n(b, n);</tt>
+ <DD>Equivalent to <tt>{ InputIterator i = b; for (size_t j = 0; j != n; ++j) h.update_one(*i++); }</tt>
+ </DL>
+
+<P>Provided models are accessible through HashPolicy models.
+
+<HR>
+
+<P>Copyright Scott McMurray 2010</P>
+<P>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).</P>
+
+</body>
+</html>
+
Added: sandbox/hash/libs/hash/doc/html/functions.html
==============================================================================
--- (empty file)
+++ sandbox/hash/libs/hash/doc/html/functions.html 2010-05-05 18:07:45 EDT (Wed, 05 May 2010)
@@ -0,0 +1,48 @@
+<html>
+<head>
+<title>The MaybeBoost Hash Library</title>
+<body>
+
+<P STYLE="float:right">Back to Index</P>
+
+<H2>The MaybeBoost Hash Library: Functions</H2>
+
+<H3 ID="compute_digest">The <tt>compute_digest</tt> Family</H3>
+
+<P>These are convenience functions for calculating the message digest of a single range of data. All versions take a HashPolicy model as an explicit template parameter and return the corresponding <tt><i>HashPolicy</i>::digest_type</tt>. All the bits in the provided values are used (including the sign bit, if present).
+
+<P>There are three ways to provide the range:
+
+<OL>
+<LI>As a pair of iterators
+ <UL>
+ <LI><tt>compute_digest<<i>HashPolicy</i>>(<i>InIter</i> b, <i>InIter</i> e)</tt>
+ </UL>
+<LI>As an iterator and a length
+ <UL>
+ <LI><tt>compute_digest_n<<i>HashPolicy</i>>(<i>InIter</i> b, size_t n)</tt>
+ </UL>
+<LI>As a whole container
+ <UL>
+ <LI><tt>compute_digest<<i>HashPolicy</i>>(<i>Container</i> const &c)</tt><BR>
+ when <tt>c</tt> has <tt>begin()</tt> and <tt>end()</tt> member functions
+ <LI><tt>compute_digest_n<<i>HashPolicy</i>>(<i>Container</i> const &c)</tt><BR>
+ when <tt>c</tt> has <tt>begin()</tt> and <tt>size()</tt> member functions
+ <LI><tt>compute_digest_data<<i>HashPolicy</i>>(<i>Container</i> const &c)</tt><BR>
+ when <tt>c</tt> has <tt>data()</tt> and <tt>size()</tt> member functions
+ </UL>
+ When the <tt>Container</tt> is a <tt>std::basic_string</tt>, <tt>compute_digest</tt> or <tt>compute_digest_n</tt> delegate to <tt>compute_digest_data</tt>.
+</OL>
+
+<P><B>Portability Note:</B> Because the number of bits to use is taken from the size of the iterator's <tt>value_type</tt>, it's best to use the <tt>uint_t<<i>N</i>>::exact</tt> types from Boost.Integer rather than directly use fundamental types. Most users are unlikely to need to worry about this, however, as they will be using ranges of bytes on POSIX-compatible machines (where <tt>CHAR_BIT</tt> is always 8).
+
+<P><B>Alternative:</B> If you need to specify the number of bits to use from each value, then use the StreamHash directly. This can still be done as an expression as follows: <tt><i>HashPolicy</i>::stream_hash<<i>N</i>>::type().update(<i>b</i>, <i>e</i>).end_message()</tt>.
+
+<HR>
+
+<P>Copyright Scott McMurray 2010</P>
+<P>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).</P>
+
+</body>
+</html>
+
Added: sandbox/hash/libs/hash/doc/html/performance.html
==============================================================================
--- (empty file)
+++ sandbox/hash/libs/hash/doc/html/performance.html 2010-05-05 18:07:45 EDT (Wed, 05 May 2010)
@@ -0,0 +1,100 @@
+<html>
+<head>
+<title>The MaybeBoost Hash Library</title>
+<body>
+
+<P STYLE="float:right">Back to Index</P>
+
+<H2>The MaybeBoost Hash Library: Performance</H2>
+
+<P>At this time there are no assembly- or intrinsic-using implementations of any of of the algorithms. There are a few portable changes applied that proved effective for the author, which may or may not help with any particular compiler setup.
+
+<P>Currently the implementations are about half the speed of GNU's coreutils or better. Here are the author's numbers for hashing a 244.25 MiB file (a plasma rendered in GIMP) 8 times using the <tt>example/hashsum.cpp</tt> program:<BR>
+<TABLE BORDER=1>
+<TR>
+<TH>Algorithm
+<TH>GNU coreutils
+<TH>Boost.Hash<sup>1</sup>
+<TH>Slower by
+</TR>
+<TR>
+<TD>SHA-1
+<TD>9.406
+<TD>16.119s
+<TD>73%
+</TR>
+<TR>
+<TD>MD5
+<TD>6.330s
+<TD>7.750s
+<TD>23%
+</TR>
+<TR>
+<TD>SHA-512
+<TD>12.483
+<TD>16.466
+<TD>32%
+</TR>
+</TABLE>
+<small><sup>1</sup> Best time from table below</small>
+
+<P>Here are a few general suggestions if you require high throughput.
+
+<H3>Play with your Optimizer Settings</H3>
+
+<P>Compiler flags make a big difference, and not always in an intuitive way. As shown below, going from -O1 to -O3 can double throughput, but going from -O2 to -O3 can also half it.
+
+<P>Here are the author's numbers for hashing a 244.25 MiB file (a plasma rendered in GIMP) 8 times using the <tt>example/hashsum.cpp</tt> program compiled with a SVN version of g++ 4.5.1:<BR>
+<TABLE BORDER=1>
+<TR>
+<TH>Algorithm
+<TH>-O1
+<TH>-O2
+<TH>-O3
+</TR>
+<TR>
+<TD>SHA-1
+<TD>32.344s
+<TD>18.512s
+<TD>16.119s
+</TR>
+<TR>
+<TD>MD5
+<TD>8.220s
+<TD>7.750s
+<TD BGCOLOR="red">7.890s
+</TR>
+<TR>
+<TD>SHA-512
+<TD>29.121s
+<TD>16.466
+<TD BGCOLOR="red">31.011
+</TR>
+<TR>
+<TD>CubeHash16/32-512
+<TD>39.894s
+<TD BGCOLOR="red">45.487
+<TD BGCOLOR="red">43.747
+</TR>
+</TABLE>
+
+<H3>Try Providing Pointers for Input</H3>
+
+<P>Each hash algorithm defines the endianness used to convert the provided bits into words. When that byte order matches that of the host (Little-Endian for MD4, MD5, and CubeHash; Big-Endian for SHA, SHA-1, and SHA-2) and the input type is sized appropriately, the endianness can be handled with a simple <tt>memcpy</tt>.
+
+<P>For most users (those on x86 or amd64), this means that MD5 will perform best when given a char*s (or unsigned char*s) for input.
+
+<H3>Use Random-Access Iterators or the <tt>_n</tt> Functions</H3>
+
+<P>Because most hash algorithms are block-oriented internally, the preprocessing stage can skip an internal buffering stage if it knows that a full block is available in the input.
+
+<P>Random-access iterators will automatically use the length, but if you're buffering from something else and have the length available, provide it.
+
+<HR>
+
+<P>Copyright Scott McMurray 2010</P>
+<P>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).</P>
+
+</body>
+</html>
+
Added: sandbox/hash/libs/hash/doc/html/quickstart.html
==============================================================================
--- (empty file)
+++ sandbox/hash/libs/hash/doc/html/quickstart.html 2010-05-05 18:07:45 EDT (Wed, 05 May 2010)
@@ -0,0 +1,118 @@
+<html>
+<head>
+<title>The MaybeBoost Hash Library</title>
+<body>
+
+<P STYLE="float:right">Back to Index</P>
+
+<H2>The MaybeBoost Hash Library: Quickstart</H2>
+
+<P>Want to get started without worry about the details? Here's how.</P>
+
+<P><OL>
+
+<LI>Include the <tt>boost/hash.hpp</tt> header. No linking is required.
+
+<LI>Choose the hash algorithm you with to use. The following are provided:<BR>
+ <TABLE BORDER=1>
+
+ <TR>
+ <TH>Name
+ <TH>Digest Bits
+ <TH>HashPolicy Model (in <tt>boost::hash</tt>)
+ <TH>Reference
+ <TH>Notes
+ </TR>
+
+ <TR>
+ <TD>MD4
+ <TD>128
+ <TD><tt>md4</tt>
+ <TD>RFC 1320
+ <TD>Practical attacks exist
+ </TR>
+ <TR>
+ <TD>MD5
+ <TD>128
+ <TD><tt>md5</tt>
+ <TD>RFC 1321
+ <TD>Practical attacks exist
+ </TR>
+
+ <TR>
+ <TD>SHA
+ <TD>160
+ <TD><tt>sha</tt>
+ <TD>FIPS 180
+ <TD>Collisions known; Repealed
+ </TR>
+
+ <TR>
+ <TD>SHA-1
+ <TD>160
+ <TD><tt>sha1</tt>
+ <TD ROWSPAN=5>FIPS 180-3
+ <TD>Some concern
+ </TR>
+
+ <TR>
+ <TD>SHA-224
+ <TD>224
+ <TD><tt>sha2<224></tt>
+ <TD ROWSPAN=4>As of 2010, considered secure by NIST
+ </TR>
+ <TR>
+ <TD>SHA-256
+ <TD>256
+ <TD><tt>sha2<224></tt>
+ </TR>
+ <TR>
+ <TD>SHA-384
+ <TD>384
+ <TD><tt>sha2<384></tt>
+ </TR>
+ <TR>
+ <TD>SHA-512
+ <TD>512
+ <TD><tt>sha2<512></tt>
+ </TR>
+
+ <TR>
+ <TD>CubeHash-<i>h</i> (<i>h</i> in {8, 16, 24, ..., 512})
+ <TD><i>h</i>
+ <TD><tt>cubehash<<i>h</i>></tt>
+ <TD>CubeHash NIST Submission
+ <TD>SHA-3 candidate; Suggest waiting for further cryptanalysis
+ </TR>
+
+ </TABLE>
+
+<LI>With the chosen <i>HashPolicy</i>, call the <tt>boost::hash::compute_digest<<i>HashPolicy</i>></tt> function, passing it a container. That will return the digest as an object of type <tt><i>HashPolicy</i>::digest_type</tt>.
+
+<LI>The resulting message digest may be output to a <tt>std::ostream</tt> or directly converted to a <tt>std::string</tt> for display with the <tt>.str()</tt> member function.
+
+</OL></P>
+
+<P>Here's a sample complete program (<tt>example/quickstart.cpp</tt>):
+<BLOCKQUOTE><PRE>
+#include <boost/hash.hpp>
+
+#include <iostream>
+#include <string>
+
+int main() {
+ std::string s = "Hello World!";
+ typedef boost::hash::sha2<256> HashPolicy;
+ HashPolicy::digest_type digest = boost::hash::compute_digest<HashPolicy>(s);
+ std::cout << digest << "\n";
+}
+</PRE></BLOCKQUOTE>
+
+<HR>
+
+<P>Copyright Scott McMurray 2010</P>
+<P>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).</P>
+
+</body>
+</html>
+
Added: sandbox/hash/libs/hash/doc/html/validation.html
==============================================================================
--- (empty file)
+++ sandbox/hash/libs/hash/doc/html/validation.html 2010-05-05 18:07:45 EDT (Wed, 05 May 2010)
@@ -0,0 +1,31 @@
+<html>
+<head>
+<title>The MaybeBoost Hash Library</title>
+<body>
+
+<P STYLE="float:right">Back to Index</P>
+
+<H2>The MaybeBoost Hash Library: Validation</H2>
+
+<H3>Test Vectors</H3>
+
+<P>The tests include all the test vectors available in the standards, as well as others verified against reference or other well-known implementations.
+
+<P>For MD4 and MD5, these are the test vectors from the RFCs. For SHA-1 and the SHA-2 family, they come from the FIPS standard and the SHAVS examples. SHA-0 is checked against a published collision. CubeHash is tested against answers obtained from the NIST-submitted "reference" implementation.
+
+<P>See <tt>libs/hash/test/</tt> for full details.
+
+<H3>Speed vs Code Clarity</H3>
+
+<P>All implementations were initially written to follow the specs very closely to simplify manual verification by code inspection. These implementations, however, are usually a few hundred percent slower than optimized implementations, and occasionally much worse than that.
+
+<P>In various places, optimizations have been applied, and these are used by default. The original implementations are still accessible, however, by defining <tt>BOOST_HASH_NO_OPTIMIZATION</tt>. This is useful for checking the correctness of the optimizations.
+
+<HR>
+
+<P>Copyright Scott McMurray 2010</P>
+<P>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).</P>
+
+</body>
+</html>
+
Modified: sandbox/hash/libs/hash/example/hashsum.cpp
==============================================================================
--- sandbox/hash/libs/hash/example/hashsum.cpp (original)
+++ sandbox/hash/libs/hash/example/hashsum.cpp 2010-05-05 18:07:45 EDT (Wed, 05 May 2010)
@@ -1,4 +1,16 @@
+//
+// 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)
+//
+
+//
+// Define HASH to one of the models of the HashPolicy concept.
+// Do not include the boost::hash:: namespace qualifier.
+//
+
#ifndef HASH
#define HASH cubehash<80*4>
#endif
Added: sandbox/hash/libs/hash/example/quickstart.cpp
==============================================================================
--- (empty file)
+++ sandbox/hash/libs/hash/example/quickstart.cpp 2010-05-05 18:07:45 EDT (Wed, 05 May 2010)
@@ -0,0 +1,20 @@
+
+//
+// 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)
+//
+
+#include <boost/hash.hpp>
+
+#include <iostream>
+#include <string>
+
+int main() {
+ std::string s = "Hello World!";
+ typedef boost::hash::sha2<256> HashPolicy;
+ HashPolicy::digest_type digest = boost::hash::compute_digest<HashPolicy>(s);
+ std::cout << digest << "\n";
+}
+
Added: sandbox/hash/libs/hash/index.html
==============================================================================
--- (empty file)
+++ sandbox/hash/libs/hash/index.html 2010-05-05 18:07:45 EDT (Wed, 05 May 2010)
@@ -0,0 +1,37 @@
+<html>
+<head>
+<title>The MaybeBoost Hash Library</title>
+<body>
+
+<H2>The MaybeBoost Hash Library</H2>
+
+<P>This library provides for the calculation of message digests using various hash algorithms.</P>
+
+<P><UL>
+<LI>Quickstart
+<LI>Functions
+ <UL>
+ <LI>compute_digest
+ </UL>
+<LI>Concepts
+ <UL>
+ <LI>HashPolicy
+ <LI>StreamHash
+ </UL>
+<LI>Performance
+<LI>Validation
+<LI>Examples
+ <UL>
+ <LI>quickstart.cpp
+ <LI>hashsum.cpp
+ </UL>
+</UL></P>
+
+<HR>
+
+<P>Copyright Scott McMurray 2010</P>
+<P>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).</P>
+
+</body>
+</html>
+
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