Hi James,

I've snipped the parts that are off-topic here and replied to them by
mail. Send-button hit (yesterday) with my fingers crossed :-)


On Fri,  6 Oct 2006 09:36:42 CST, "kanze" <kanze@gabi-soft.fr> wrote:

>> >Interestingly enough, I don't have a push_back function,
>> >although I probably should.
>
>> In effect it was called append() in the first place :-) The
>> only reason why I renamed it to push_back is, as you clearly
>> inferred, that I wanted to use a standard back inserter, if
>> possible.
>
>Back inserter or no, the standard idiom for appending a single
>element in the library is push_back.  (I'm not 100% sure that
>either name is really right here, since we aren't really adding
>anything to the sequence, and the size doesn't increase, but I
>don't have any better alternatives.)

Yeah :-) I'm not sure either what the name commonality actually gains;
above all whether it could "gain" some unpleasant gotcha in generic
code (for the rest familiarity with hasher semantics should ensure
that no one would actually think to enlarge a dynamic sequence).

>> That's interesting. In fact I asked here why the standard
>> version is defined in terms of + instead of +=, with no
>> replies.
>
>> Performance-wise my first tests, modeled after the time trial
>> in RFC 1321, show that for MD5 there's quite a difference
>> between calls to push_back and calls to append (Not
>> surprisingly, as push_back has to check if the input buffer is
>> full at each insertion.
>
>My append affectively checks each time anyway.  I suppose I
>could have optimized it for random access iterators, so that it
>would insert the maximum each time around.  (It's probably worth
>it, since I imagine that most of the use is with string
>iterators, which are random access.)

I did the optimization for random access iterators and it was quite
effective. As to accumulate(), my first thought was to go for a
different generalization. I have sketched the code below, posted for
my public shame. Feedback is very appreciated.

    template< typename T >
    class accumulate_traits
    {
    public:

        typedef T init_type;
        typedef T result_type;

        static init_type first()
        {
            return T();
        }

    };

    class accumulate_sum_policy
    {
    public:

        template< typename Iterator, typename First >
        static First accumulate( Iterator begin, Iterator end,
                                 const First & value )
        {
            // use std accumulate, instead??
            //
            for( ; begin != end; ++begin )
                value += *begin;
            return value;
        }

    };


    template<   typename T
              , typename Policy = accumulate_sum_policy
              , typename Traits = accumulate_traits< T >
            >
    class accumulator
    {
    public:

        template< typename Iterator >
        inline typename Traits::result_type
        operator()( Iterator begin, Iterator end,
                    typename Traits::init_type v = Traits::first()
                  ) const
        {
            return Policy::accumulate( begin, end, v );
        }
    };


Now, for a Merkle-Damgard machine I'd do (not tested yet):

    class merkle_damgard_accumulation_policy
    {
    public:
        template< typename It, typename First >
        static inline First accumulate( It begin, It end,
                                        First value )
        {
            return value.append( begin, end );
        }

    };

    accumulator< md5_hasher,
                 merkle_damgard_accumulation_policy > acc;

    md5_hasher h = acc( s.begin(), s.end() );


Thoughts?

--
Gennaro Prota

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Gennaro Prota wrote:

    [...]
> >My append affectively checks each time anyway.  I suppose I
> >could have optimized it for random access iterators, so that
> >it would insert the maximum each time around.  (It's probably
> >worth it, since I imagine that most of the use is with string
> >iterators, which are random access.)

> I did the optimization for random access iterators and it was quite
> effective. As to accumulate(), my first thought was to go for a
> different generalization. I have sketched the code below, posted for
> my public shame. Feedback is very appreciated.

>     template< typename T >
>     class accumulate_traits

And I jump right here.  std::accumulate is a function, and I
like it that way.  I don't think that I'd like to pass it an
additional traits parameter.

>     {
>     public:
>
>         typedef T init_type;
>         typedef T result_type;

>         static init_type first()
>         {
>             return T();
>         }
>
>     };

>     class accumulate_sum_policy
>     {
>     public:
>
>         template< typename Iterator, typename First >
>         static First accumulate( Iterator begin, Iterator end,
>                                  const First & value )
>         {
>             // use std accumulate, instead??
>             //
>             for( ; begin != end; ++begin )
>                 value += *begin;
>             return value;
>         }
>
>     };

>     template<   typename T
>               , typename Policy = accumulate_sum_policy
>               , typename Traits = accumulate_traits< T >
>             >
>     class accumulator
>     {
>     public:
>
>         template< typename Iterator >
>         inline typename Traits::result_type
>         operator()( Iterator begin, Iterator end,
>                     typename Traits::init_type v = Traits::first()
>                   ) const
>         {
>             return Policy::accumulate( begin, end, v );
>         }
>     };

> Now, for a Merkle-Damgard machine I'd do (not tested yet):

>     class merkle_damgard_accumulation_policy
>     {
>     public:
>         template< typename It, typename First >
>         static inline First accumulate( It begin, It end,
>                                         First value )
>         {
>             return value.append( begin, end );
>         }
>     };
>
>     accumulator< md5_hasher,
>                  merkle_damgard_accumulation_policy > acc;

>     md5_hasher h = acc( s.begin(), s.end() );

> Thoughts?

Just that I don't like the extra object, and I'm not too sure
why you want both a policy and traits.  The basic idea seems
reasonable, however, but with a traits on type of the
accumulator type.  The traits would have a default
implementation which makes accumulate work exactly as it now
does; specializations would cause += to be used instead of +.
And I suppose that you could imagine a variant which grabbed
control completely, but to tell the truth, I don't know what
that buys you over an explicit overload of the function.  Which
come to think of it is the simplest solution here---I think I'll
add that to my class.  The only potential problem I see is that
I'm not allowed to introduce the overload into std, and of
course, without that, it won't be found when someone writes
std::accumulate.

I think I'll cheat, and add it to std:: anyway.  Morally, it's
the equivalent of an explicit instantiation of a template class
for a user defined type, so logically, it should be allowed as
well.  Any courageous soul want to come up with the change in
wording for    17.4.3.1?

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Gennaro Prota wrote:

    [...]
> >My append affectively checks each time anyway.  I suppose I
> >could have optimized it for random access iterators, so that
> >it would insert the maximum each time around.  (It's probably
> >worth it, since I imagine that most of the use is with string
> >iterators, which are random access.)

> I did the optimization for random access iterators and it was quite
> effective. As to accumulate(), my first thought was to go for a
> different generalization. I have sketched the code below, posted for
> my public shame. Feedback is very appreciated.

>     template< typename T >
>     class accumulate_traits

And I jump right here.  std::accumulate is a function, and I
like it that way.  I don't think that I'd like to pass it an
additional traits parameter.

>     {
>     public:
>
>         typedef T init_type;
>         typedef T result_type;

>         static init_type first()
>         {
>             return T();
>         }
>
>     };

>     class accumulate_sum_policy
>     {
>     public:
>
>         template< typename Iterator, typename First >
>         static First accumulate( Iterator begin, Iterator end,
>                                  const First & value )
>         {
>             // use std accumulate, instead??
>             //
>             for( ; begin != end; ++begin )
>                 value += *begin;
>             return value;
>         }
>
>     };

>     template<   typename T
>               , typename Policy = accumulate_sum_policy
>               , typename Traits = accumulate_traits< T >
>             >
>     class accumulator
>     {
>     public:
>
>         template< typename Iterator >
>         inline typename Traits::result_type
>         operator()( Iterator begin, Iterator end,
>                     typename Traits::init_type v = Traits::first()
>                   ) const
>         {
>             return Policy::accumulate( begin, end, v );
>         }
>     };

> Now, for a Merkle-Damgard machine I'd do (not tested yet):

>     class merkle_damgard_accumulation_policy
>     {
>     public:
>         template< typename It, typename First >
>         static inline First accumulate( It begin, It end,
>                                         First value )
>         {
>             return value.append( begin, end );
>         }
>     };
>
>     accumulator< md5_hasher,
>                  merkle_damgard_accumulation_policy > acc;

>     md5_hasher h = acc( s.begin(), s.end() );

> Thoughts?

Just that I don't like the extra object, and I'm not too sure
why you want both a policy and traits.  The basic idea seems
reasonable, however, but with a traits on type of the
accumulator type.  The traits would have a default
implementation which makes accumulate work exactly as it now
does; specializations would cause += to be used instead of +.
And I suppose that you could imagine a variant which grabbed
control completely, but to tell the truth, I don't know what
that buys you over an explicit overload of the function.  Which
come to think of it is the simplest solution here---I think I'll
add that to my class.  The only potential problem I see is that
I'm not allowed to introduce the overload into std, and of
course, without that, it won't be found when someone writes
std::accumulate.

I think I'll cheat, and add it to std:: anyway.  Morally, it's
the equivalent of an explicit instantiation of a template class
for a user defined type, so logically, it should be allowed as
well.  Any courageous soul want to come up with the change in
wording for    17.4.3.1?

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Tue, 10 Oct 2006 09:43:42 CST, "kanze" <kanze@gabi-soft.fr> wrote:

>> Now, for a Merkle-Damgard machine I'd do (not tested yet):
>
>>     class merkle_damgard_accumulation_policy
>>     {
>>     public:
>>         template< typename It, typename First >
>>         static inline First accumulate( It begin, It end,
>>                                         First value )
>>         {
>>             return value.append( begin, end );
>>         }
>>     };
>>
>>     accumulator< md5_hasher,
>>                  merkle_damgard_accumulation_policy > acc;
>
>>     md5_hasher h = acc( s.begin(), s.end() );
>
>> Thoughts?
>
>Just that I don't like the extra object, and I'm not too sure
>why you want both a policy and traits.

It was just a sketch :-) (The separation was partly instinctive; I
tend to think of traits as "property mappers" and polices are
"behavior providers" --where there's no behavior involved my instinct
makes me write "traits" :-O)

>The basic idea seems
>reasonable, however, but with a traits on type of the
>accumulator type.  The traits would have a default
>implementation which makes accumulate work exactly as it now
>does; specializations would cause += to be used instead of +.

In my case I wanted an implementation for the hasher which avoided
considering one element at a time; thus neither + or += reached the
goal.

>And I suppose that you could imagine a variant which grabbed
>control completely, but to tell the truth, I don't know what
>that buys you over an explicit overload of the function.

ADL-induced ambiguities was one of the problems I considered. Another
one was the absence of default template parameters for function
templates. Both problems were thoughts of without taking into account
the possibility of adding to the std namespace.

--
Gennaro Prota

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

kanze wrote:
>
> Personally, I like the accumulate idiom, and if I can find time
> (ha!), I'd like to investigate the possibility of writing a
> version of accumulate which uses += if it can find it, and +
> then = otherwise.  If accumulate used +=, there would be no real
> time penalty (unless you called accumulate for a lot of little
> sequences, instead of just once).

boost are clever at doing things like that. I'm not that clever but am
just about clever enough to write my own accumulate that uses +=

template <class InputIterator, class T>
T accumulate(InputIterator start, InputIterator finish,  T init )
{
   while ( start != finish )
   {
        init += *start;
        ++start;
   }
   return init;
}

template <class InputIterator,   class T,  class BinaryOperation >
T accumulate(InputIterator start,  InputIterator finish,  T init,
BinaryOperation binary_op)
{
   while ( start != finish )
   {
       binary_op( init, *start );
       ++start;
   }
  return init;
}

This requires that binary_op takes its first parameter by non-const
reference.

Each makes 2 copies, one on entry to the function and one on exit, the
last of which may be optimised away by RVO so only one is strictly
necessary.

If you force the template parameter to a reference (you can do this by
specificing the template parameters on calling the algorithm instead of
relying on automatic deduction) then you can optimise away even the one
copy. You cannot then however pass in a temporary or a literal.

Of course you'd put these implementations into your own namespace.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Gennaro Prota wrote:
> On Wed, 27 Sep 2006 10:26:24 CST, "kanze" <kanze@gabi-soft.fr> wrote:

> >Gennaro Prota wrote:

> >> I'm currently refining a mini-framework to implement one-way
> >> hash functions. To simplify things a bit let's assume the main
> >> abstractions of the sistem are

> >>     template< typename Engine >
> >>     class hasher;

> >> (where Engine can be MD5, SHA1, etc.) and

> >>     template< class Hasher >
> >>     class digest;

> >See http://kanze.james.neuf.fr/code-en.html. In the Digest
> >component of the IO subsystem, there are template classes
> >Hasher and Digest, as well as policy classes for MD5 and the
> >known (to me) SHA hashes.

> Hmm :-) As I said you a while ago I didn't want to look at
> your code to avoid taking too much inspiration. My classes
> will be released under the GPL. I got no replies when I asked
> you if you agreed to use the same license for your code so I
> gave up.

I'm having connectivity problems again.  Email seems to work in
batch mode---nothing for a week or two, then everything comes
through.

My license is really pretty simple: you can do anything you want
with the code as long as you don't expect me to maintain your
modifications (or even claim that I am responsible for them).
As I think I state at the site, I don't consider much of the
code there as really being "production quality"; it's more a
sounding board for ideas than anything else.  (The actual
licence is a BSD licence.  I'm too lazy to come up with words of
my own, and that seemed to be the most open I'd seen.)

My own code will NOT be released under the GPL---it takes away
too much freedom from the user.  However, it can be incorporated
into other things which are GPL.  As long as you take the
responsibility for the GPL on the copy you are using.  (I don't
think I'm the first to do this, and it certainly isn't unusual
for code to be available under different licences.  At least if
the original sources aren't GPL.)

Note that you probably won't want to copy it verbatim anyway; my
naming conventions are likely different than yours, and it also
depends a bit on my build system for handling portability issues
(e.g. it includes "gb/stdint.hh", from an entirely different
component, to get things like uint32_t in a portable manner).
And copyright only covers literal copying and "derived works";

> From what you say it seems to me we came up with very similar
> solutions which certainly is a good sign :-) For me, of
> course.

> >> The only user-callable functions in class hasher (besides
> >> constructors) are:

> >>     void push_back( byte_type b );

> >>     template< typename InputIter >
> >>     void append( InputIter begin, InputIter end );

> >How do you read the value? :-).

> The digest you mean? There was a create_digest() function
> which just forwarded the work to the digest constructor. In
> the end I removed it; why not writing just md5_digest( h ).

My code actually evolved in the opposite direction.  I
originally provided the functions to read the digest directly in
the hasher, e.g. toString() or an << operator.  After a short
discussion on comp.lang.c++.moderated, I added a Digest class
and an asDigest() function.  (Although you can do it either way:
Digest also has a constructor which takes a Hasher.)

The only real interest of the separate Digest class, I think, is
its support for comparisons (< and ==, particularly) and hash
coding.  In case you want to use it as a key in an std::map or
(soon) in an std::unordered_map.

> >I've also found a reset() function useful.

> I'm still undecided about this. So far I haven't found a usage
> for it.  The digest constructor takes a hasher argument *by
> value*. IOWs its parameter is a copy of the original hasher
> and the finalization is performed on the copy.

It permets reusing the hasher.  Personally, I generally prefer
creating a new object, each time I need it, but I know from
experience that this preference is not universal.   And I can
sort of imagine cases where you might hash sections of a
document separately---when you detect a new section, you output
the digest, and reset the hasher.

But it's more of a convenience function.  The hasher supports
assignment (obviously, if it is to be used with accumulate), so
something like:
    h = MD5Hasher() ;
could also be used.

> >Interestingly enough, I don't have a push_back function,
> >although I probably should.

> In effect it was called append() in the first place :-) The
> only reason why I renamed it to push_back is, as you clearly
> inferred, that I wanted to use a standard back inserter, if
> possible.

Back inserter or no, the standard idiom for appending a single
element in the library is push_back.  (I'm not 100% sure that
either name is really right here, since we aren't really adding
anything to the sequence, and the size doesn't increase, but I
don't have any better alternatives.)

> > The initial design was for the
> >class to be an "accumulator", to be used with std::accumulate,
> >thus:

> >    out << std::accumulate( text.begin(), text.end(), MD5Hasher() ) ;

> >(where MD5Hasher is a typedef for Hasher<MD5Policy>, of course).
> >This ends up resulting in a lot of copying, so I added the
> >append function.  There is a short discussion about this (an my
> >own considerations about using an output iterator) in the
> >documentation:
> >http://kanze.james.neuf.fr/doc/en/IO/html/index.html, then
> >navigate to the class Hasher.

> Ok, I looked at the docs. Yes, accumulate() seems conceptually
> more appropriate (though in general I think along the lines of
> Peter Dimov). I think the "why not just using append" argument
> is a bit weak, in that there can be generic programming
> situations where some of the types you want to instantiate the
> template on don't have an append function but do have an
> operator+. I can't think of any, though :-O.

> >(Note that I was fairly careful to implement the class in a
> >way that copying would take a minimum amount of time.  On the
> >other hand, I haven't really tried to find any means of
> >sharing the state, without copying---operator+ would have to
> >return a temporary which would convert to a Hasher in general
> >case, but for which assignment would be overloaded so that it
> >modified the state in place.)

> Yeah. I mentally went though that route as well. Then
> Sutter/Alexandrescu peeped through my mind :-) (Only add complexity
> when you know you benefit from it)

Actually, it's not a case of more or less complexity.  In my
mind, the implementation would be a lot simpler if I'd used
std::vector, instead of fixed size C style arrays.  But even
without profiling :-), the idea of severall allocations for each
copy scared me off.  Recent postings in it.comp.lang.c++ may
show that using [] on an std::vector is even faster (at least in
some cases) than using it on a C style array, but I' pretty sure
that assigning a class with a char[8] or a uint32_t[16] is a
lot faster than if the class used std::vector for the two.  Like
an order of magnitude or more.

The main reason I didn't go for a solution with shared data is
that I couldn't figure out a simple critera for knowing when to
unshare.  Simple COW doesn't help, because you do end up writing
a large number of the objects which you copy.  And giving the
class reference semantics, with + and += having the same
semantics, just didn't cut it, in my mind.

> In the end it seemed to me the complexity/benefit ratio was
> too high.

> >> [snip]

> >Personally, I like the accumulate idiom, and if I can find time
> >(ha!), I'd like to investigate the possibility of writing a
> >version of accumulate which uses += if it can find it, and +
> >then = otherwise.  If accumulate used +=, there would be no real
> >time penalty (unless you called accumulate for a lot of little
> >sequences, instead of just once).

> That's interesting. In fact I asked here why the standard
> version is defined in terms of + instead of +=, with no
> replies.

> Performance-wise my first tests, modeled after the time trial
> in RFC 1321, show that for MD5 there's quite a difference
> between calls to push_back and calls to append (Not
> surprisingly, as push_back has to check if the input buffer is
> full at each insertion.

My append affectively checks each time anyway.  I suppose I
could have optimized it for random access iterators, so that it
would insert the maximum each time around.  (It's probably worth
it, since I imagine that most of the use is with string
iterators, which are random access.)

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Earl Purple wrote:
> kanze wrote:

> > Personally, I like the accumulate idiom, and if I can find time
> > (ha!), I'd like to investigate the possibility of writing a
> > version of accumulate which uses += if it can find it, and +
> > then = otherwise.  If accumulate used +=, there would be no real
> > time penalty (unless you called accumulate for a lot of little
> > sequences, instead of just once).

> boost are clever at doing things like that. I'm not that
> clever but am just about clever enough to write my own
> accumulate that uses +=

I'd thought about that, but hadn't found the time.  (Although
admittedly, the biggest problem is finding a name for it:-).)

> template <class InputIterator, class T>
> T accumulate(InputIterator start, InputIterator finish,  T init )
> {
>    while ( start != finish )
>    {
>         init += *start;
>         ++start;
>    }
>    return init;
> }

> template <class InputIterator,   class T,  class BinaryOperation >
> T accumulate(InputIterator start,  InputIterator finish,  T init,
> BinaryOperation binary_op)
> {
>    while ( start != finish )
>    {
>        binary_op( init, *start );
>        ++start;
>    }
>   return init;
> }

> This requires that binary_op takes its first parameter by non-const
> reference.

> Each makes 2 copies, one on entry to the function and one on
> exit, the last of which may be optimised away by RVO so only
> one is strictly necessary.

That's about the way I was thinking of.

> If you force the template parameter to a reference (you can do
> this by specificing the template parameters on calling the
> algorithm instead of relying on automatic deduction) then you
> can optimise away even the one copy. You cannot then however
> pass in a temporary or a literal.

> Of course you'd put these implementations into your own namespace.

I'm not sure that helps.  I'd be worried that ADL kicked in, if
ever I chanced to call it with arguments from the standard
library (e.g. std::string::iterator), and there'd be an
ambiguity.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Tue, 26 Sep 2006 22:13:03 CST, "Greg Herlihy" <greghe@pacbell.net>
wrote:

>But why even go to the trouble of converting your hashing container
>class to be a standard container, instead of just using one of the two
>that have already been written? From what I can tell, the two
>requirements for this container are a) a customizable hashing function
>b) standard container conformance. And given those criteria,
>std::tr1::unordered_set and std::tr1::unordered_map have no trouble
>qualifiying.

I think there has been a misunderstanding. My hasher template has
nothing to do with TR1's unordered_map and has no concept of "key" in
itself. It is just a machine for computing digests. Basically you
provide a policy which implements a small number of algorithm-specific
operations and it provides all the scaffolding necessary to obtain a
full fledged Merkle-Damgard construction:

  <http://en.wikipedia.org/wiki/Merkle-Damgard>

(in effect, in my mini-framework it is called merkle_damgard_hasher;
that's not the only possible kind of hasher)

--
Gennaro Prota

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

kanze wrote:

> Because his hasher isn't a container at all, to begin with, at
> least not in the sense of the standard.  He simply wants to fool
> the system into thinking it's one.  Thus, for example, push_back
> doesn't increase the size of container; it just changes some
> internal state.

In some ways, it looks more like a stream than a container.  In
particular, a hasher resembles a stringstream:  you put a bunch of
things into it (via operator <<) , then extract a value from it (via
str()).  If that analogy makes sense, you'd want an ostream_iterator
rather than a back_insert_iterator.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Gennaro Prota wrote:
> Hi all,
>
> I'm currently refining a mini-framework to implement one-way hash
> functions. To simplify things a bit let's assume the main abstractions
> of the sistem are
>
>     template< typename Engine >
>     class hasher;
>
> (where Engine can be MD5, SHA1, etc.) and
>
>     template< class Hasher >
>     class digest;
>
> The only user-callable functions in class hasher (besides
> constructors) are:
>
>     void push_back( byte_type b );
>
>     template< typename InputIter >
>     void append( InputIter begin, InputIter end );
>
> which allow to "enqueue" a byte, or sequence thereof, into an input
> block (merkle damgard tecnique).
>
> Now, what I wonder is: if in addition to the push_back() function my
> hasher just provides
>
>      typedef       byte_type & reference;
>      typedef const byte_type & const_reference;
>
> is it legal/moral to use a standard back_insert_iterator on it even if
> the hasher itself doesn't qualify as a standard container?

My opinion is that:

1. Yes, it is moral to do so, as the only requirements that the
standard explicitly places on the Container template parameter are
const_reference, push_back and unary operator&.

2. If it isn't technically legal to do so (if, for example, a future
concept-aware compiler is technically allowed to reject the code), then
this is a defect in the standard and needs to be fixed.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Wed, 27 Sep 2006 10:26:24 CST, "kanze" <kanze@gabi-soft.fr> wrote:

>Gennaro Prota wrote:
>
>> I'm currently refining a mini-framework to implement one-way
>> hash functions. To simplify things a bit let's assume the main
>> abstractions of the sistem are
>
>>     template< typename Engine >
>>     class hasher;
>
>> (where Engine can be MD5, SHA1, etc.) and
>
>>     template< class Hasher >
>>     class digest;
>
>See http://kanze.james.neuf.fr/code-en.html. In the Digest
>component of the IO subsystem, there are template classes Hasher
>and Digest, as well as policy classes for MD5 and the known (to
>me) SHA hashes.

Hmm :-) As I said you a while ago I didn't want to look at your code
to avoid taking too much inspiration. My classes will be released
under the GPL. I got no replies when I asked you if you agreed to use
the same license for your code so I gave up. From what you say it
seems to me we came up with very similar solutions which certainly is
a good sign :-) For me, of course.


>> The only user-callable functions in class hasher (besides
>> constructors) are:
>
>>     void push_back( byte_type b );
>
>>     template< typename InputIter >
>>     void append( InputIter begin, InputIter end );
>
>How do you read the value? :-).

The digest you mean? There was a create_digest() function which just
forwarded the work to the digest constructor. In the end I removed it;
why not writing just md5_digest( h ).

>I've also found a reset() function useful.

I'm still undecided about this. So far I haven't found a usage for it.
The digest constructor takes a hasher argument *by value*. IOWs its
parameter is a copy of the original hasher and the finalization is
performed on the copy.

>Interestingly enough, I don't have a push_back function,
>although I probably should.

In effect it was called append() in the first place :-) The only
reason why I renamed it to push_back is, as you clearly inferred, that
I wanted to use a standard back inserter, if possible.

> The initial design was for the
>class to be an "accumulator", to be used with std::accumulate,
>thus:
>
>    out << std::accumulate( text.begin(), text.end(), MD5Hasher() ) ;
>
>(where MD5Hasher is a typedef for Hasher<MD5Policy>, of course).
>This ends up resulting in a lot of copying, so I added the
>append function.  There is a short discussion about this (an my
>own considerations about using an output iterator) in the
>documentation:
>http://kanze.james.neuf.fr/doc/en/IO/html/index.html, then
>navigate to the class Hasher.

Ok, I looked at the docs. Yes, accumulate() seems conceptually more
appropriate (though in general I think along the lines of Peter
Dimov). I think the "why not just using append" argument is a bit
weak, in that there can be generic programming situations where some
of the types you want to instantiate the template on don't have an
append function but do have an operator+. I can't think of any, though
:-O.

>(Note that I was fairly careful to implement the class in a way
>that copying would take a minimum amount of time.  On the other
>hand, I haven't really tried to find any means of sharing the
>state, without copying---operator+ would have to return a
>temporary which would convert to a Hasher in general case, but
>for which assignment would be overloaded so that it modified the
>state in place.)

Yeah. I mentally went though that route as well. Then
Sutter/Alexandrescu peeped through my mind :-) (Only add complexity
when you know you benefit from it)

In the end it seemed to me the complexity/benefit ratio was too high.

>> [snip]
>
>Personally, I like the accumulate idiom, and if I can find time
>(ha!), I'd like to investigate the possibility of writing a
>version of accumulate which uses += if it can find it, and +
>then = otherwise.  If accumulate used +=, there would be no real
>time penalty (unless you called accumulate for a lot of little
>sequences, instead of just once).

That's interesting. In fact I asked here why the standard version is
defined in terms of + instead of +=, with no replies. Performance-wise
my first tests, modeled after the time trial in RFC 1321, show that
for MD5 there's quite a difference between calls to push_back and
calls to append (Not surprisingly, as push_back has to check if the
input buffer is full at each insertion. Incidentally, using append
remains around 1.1 Mbit/s on a Pentium 4 2.6 GHz --that's still lower
than what I've read around the Net, though)

Thanks for your detailed reply :-)

--
Gennaro Prota

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

johnchx2@yahoo.com wrote:
> kanze wrote:

> > Because his hasher isn't a container at all, to begin with, at
> > least not in the sense of the standard.  He simply wants to fool
> > the system into thinking it's one.  Thus, for example, push_back
> > doesn't increase the size of container; it just changes some
> > internal state.

> In some ways, it looks more like a stream than a container.  In
> particular, a hasher resembles a stringstream:  you put a bunch of
> things into it (via operator <<) , then extract a value from it (via
> str()).  If that analogy makes sense, you'd want an ostream_iterator
> rather than a back_insert_iterator.

Agreed, although the analogy isn't perfect either.  In both
cases, you expect what you put in to be what you can get out
later, which isn't the case here.  Myself, I would tend toward
a custom output iterator, and leave both ostream_iterator and
back_insert_iterator be.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

johnchx2@yahoo.com wrote:
> kanze wrote:

> > Because his hasher isn't a container at all, to begin with, at
> > least not in the sense of the standard.  He simply wants to fool
> > the system into thinking it's one.  Thus, for example, push_back
> > doesn't increase the size of container; it just changes some
> > internal state.

> In some ways, it looks more like a stream than a container.  In
> particular, a hasher resembles a stringstream:  you put a bunch of
> things into it (via operator <<) , then extract a value from it (via
> str()).  If that analogy makes sense, you'd want an ostream_iterator
> rather than a back_insert_iterator.

Agreed, although the analogy isn't perfect either.  In both
cases, you expect what you put in to be what you can get out
later, which isn't the case here.  Myself, I would tend toward
a custom output iterator, and leave both ostream_iterator and
back_insert_iterator be.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Peter Dimov wrote:
> Gennaro Prota wrote:

> > I'm currently refining a mini-framework to implement one-way
> > hash functions. To simplify things a bit let's assume the
> > main abstractions of the sistem are

> >     template< typename Engine >
> >     class hasher;

> > (where Engine can be MD5, SHA1, etc.) and

> >     template< class Hasher >
> >     class digest;

> > The only user-callable functions in class hasher (besides
> > constructors) are:

> >     void push_back( byte_type b );

> >     template< typename InputIter >
> >     void append( InputIter begin, InputIter end );

> > which allow to "enqueue" a byte, or sequence thereof, into
> > an input block (merkle damgard tecnique).

> > Now, what I wonder is: if in addition to the push_back()
> > function my hasher just provides

> >      typedef       byte_type & reference;
> >      typedef const byte_type & const_reference;

> > is it legal/moral to use a standard back_insert_iterator on
> > it even if the hasher itself doesn't qualify as a standard
> > container?

> My opinion is that:

> 1. Yes, it is moral to do so, as the only requirements that the
> standard explicitly places on the Container template parameter are
> const_reference, push_back and unary operator&.

Where does it say that?  I can't find any requirements per se,
but only a statements along the lines of "An insert iterator is
constructed from a container".  And the only standard definition
for a container is in section 23, which contains the
requirements for standard containers.

Another thing to take into account is the fact that the template
parameter is named Container.  Although it doesn't say so here,
in most, if not all other contexts where the name of a template
paramter corresponds to the name of a concept, the actual
argument must meed the requirements of that concept.

My impression is that the intent is to require a Container,
although I think that the standard is far from clear about it.

> 2. If it isn't technically legal to do so (if, for example, a
> future concept-aware compiler is technically allowed to reject
> the code), then this is a defect in the standard and needs to
> be fixed.

I agree that it is a defect that the standard doesn't specify
the requirements.  And although I think that the intent was to
require a container, period, I would have no problem with looser
requirements, if the experts are sure that they are sufficient
for all reasonable implementations.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

kanze wrote:
> Peter Dimov wrote:
> > Gennaro Prota wrote:
..
> > 1. Yes, it is moral to do so, as the only requirements that the
> > standard explicitly places on the Container template parameter are
> > const_reference, push_back and unary operator&.
>
> Where does it say that?  I can't find any requirements per se,

Those requirements are implicitly deriveable from the fact that the
behavior of std::back_insert_iterator is defined in terms of the
corresponding members of the Container class, whether or not that class
actually meets the container requirements.

> but only a statements along the lines of "An insert iterator is
> constructed from a container".  And the only standard definition
> for a container is in section 23, which contains the
> requirements for standard containers.
>
> Another thing to take into account is the fact that the template
> parameter is named Container.  Although it doesn't say so here,
> in most, if not all other contexts where the name of a template
> paramter corresponds to the name of a concept, the actual
> argument must meed the requirements of that concept.

There are cases where that is true, but it's always the case that the
standard says so explicitly. I can find no such statement which covers
"Container".

> My impression is that the intent is to require a Container,
> although I think that the standard is far from clear about it.

That may have been the intent; but it would certainly be possible to
impose less restrictive requirements, and that may have been the
intent. Clarification would be desireable.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Hi all,

I'm currently refining a mini-framework to implement one-way hash
functions. To simplify things a bit let's assume the main abstractions
of the sistem are

    template< typename Engine >
    class hasher;

(where Engine can be MD5, SHA1, etc.) and

    template< class Hasher >
    class digest;

The only user-callable functions in class hasher (besides
constructors) are:

    void push_back( byte_type b );

    template< typename InputIter >
    void append( InputIter begin, InputIter end );

which allow to "enqueue" a byte, or sequence thereof, into an input
block (merkle damgard tecnique).

Now, what I wonder is: if in addition to the push_back() function my
hasher just provides

     typedef       byte_type & reference;
     typedef const byte_type & const_reference;

is it legal/moral to use a standard back_insert_iterator on it even if
the hasher itself doesn't qualify as a standard container?

Example:

     md5_hasher h;
     std::copy( s.begin(), s.end(), std::back_inserter( h ) );

--
Gennaro Prota

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Gennaro Prota wrote:
> Hi all,
>
> I'm currently refining a mini-framework to implement one-way hash
> functions.

> Now, what I wonder is: if in addition to the push_back() function my
> hasher just provides
>
>      typedef       byte_type & reference;
>      typedef const byte_type & const_reference;
>
> is it legal/moral to use a standard back_insert_iterator on it even if
> the hasher itself doesn't qualify as a standard container?
>
> Example:
>
>      md5_hasher h;
>      std::copy( s.begin(), s.end(), std::back_inserter( h ) );

The insert iterators are adapter class templates that wrap standard
containers. I would certainly interpret "container" to mean a class
that satisifies the container requirements spelled out in Chapter 23.
And judging from the looks of them, there is more to writing a standard
container class than declaring two typedefs.

But why even go to the trouble of converting your hashing container
class to be a standard container, instead of just using one of the two
that have already been written? From what I can tell, the two
requirements for this container are a) a customizable hashing function
b) standard container conformance. And given those criteria,
std::tr1::unordered_set and std::tr1::unordered_map have no trouble
qualifiying.

Greg

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Gennaro Prota wrote:

> I'm currently refining a mini-framework to implement one-way
> hash functions. To simplify things a bit let's assume the main
> abstractions of the sistem are

>     template< typename Engine >
>     class hasher;

> (where Engine can be MD5, SHA1, etc.) and

>     template< class Hasher >
>     class digest;

See http://kanze.james.neuf.fr/code-en.html. In the Digest
component of the IO subsystem, there are template classes Hasher
and Digest, as well as policy classes for MD5 and the known (to
me) SHA hashes.

> The only user-callable functions in class hasher (besides
> constructors) are:

>     void push_back( byte_type b );

>     template< typename InputIter >
>     void append( InputIter begin, InputIter end );

How do you read the value? :-).

I've also found a reset() function useful.

Interestingly enough, I don't have a push_back function,
although I probably should.  The initial design was for the
class to be an "accumulator", to be used with std::accumulate,
thus:

    out << std::accumulate( text.begin(), text.end(), MD5Hasher() ) ;

(where MD5Hasher is a typedef for Hasher<MD5Policy>, of course).
This ends up resulting in a lot of copying, so I added the
append function.  There is a short discussion about this (an my
own considerations about using an output iterator) in the
documentation:
http://kanze.james.neuf.fr/doc/en/IO/html/index.html, then
navigate to the class Hasher.
(Note that I was fairly careful to implement the class in a way
that copying would take a minimum amount of time.  On the other
hand, I haven't really tried to find any means of sharing the
state, without copying---operator+ would have to return a
temporary which would convert to a Hasher in general case, but
for which assignment would be overloaded so that it modified the
state in place.)

> which allow to "enqueue" a byte, or sequence thereof, into an
> input block (merkle damgard tecnique).

> Now, what I wonder is: if in addition to the push_back()
> function my hasher just provides

>      typedef       byte_type & reference;
>      typedef const byte_type & const_reference;

> is it legal/moral to use a standard back_insert_iterator on it
> even if the hasher itself doesn't qualify as a standard
> container?

> Example:

>      md5_hasher h;
>      std::copy( s.begin(), s.end(), std::back_inserter( h ) );

You could probably make it work, but it seems like abuse (and
almost obfuscation) to me.  The route I was considering was to
write my own insertion iterator, and add a function which
returned it, so you could write:

    std::copy( s.begin(), s.end(), h.inserter() ) ;

I haven't yet done so; to quote my documentation:

    I'm not completely sure of this however: it looks almost
    like abuse, and since unlike using std::accumulate, it
    requires an actual instance lasting beyond the end of the
    expression in order to extract the results, I wonder about
    the actual utility. (If you have an instance, there's no
    reason not to use the template form of append.)

Personally, I like the accumulate idiom, and if I can find time
(ha!), I'd like to investigate the possibility of writing a
version of accumulate which uses += if it can find it, and +
then = otherwise.  If accumulate used +=, there would be no real
time penalty (unless you called accumulate for a lot of little
sequences, instead of just once).

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Gennaro Prota wrote:
[trimmed a bit]
> class hasher {
>     public: void push_back( byte_type b );
>
>
> If in addition to the push_back() function my
> hasher just provides
>
>      typedef       byte_type & reference;
>      typedef const byte_type & const_reference;
>
> is it legal/moral to use a standard back_insert_iterator on it even if
> the hasher itself doesn't qualify as a standard container?

No, for the reasons given, but is it really hard to create your own
iterator
in this case? operator* and operator++ are trivial, and you can get the
typedefs by inheriting.

HTH,
Michiel Salters

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

Greg Herlihy wrote:
> Gennaro Prota wrote:

> > I'm currently refining a mini-framework to implement one-way hash
> > functions.

> > Now, what I wonder is: if in addition to the push_back() function my
> > hasher just provides

> >      typedef       byte_type & reference;
> >      typedef const byte_type & const_reference;

> > is it legal/moral to use a standard back_insert_iterator on it even if
> > the hasher itself doesn't qualify as a standard container?

> > Example:

> >      md5_hasher h;
> >      std::copy( s.begin(), s.end(), std::back_inserter( h ) );

> The insert iterators are adapter class templates that wrap standard
> containers. I would certainly interpret "container" to mean a class
> that satisifies the container requirements spelled out in Chapter 23.
> And judging from the looks of them, there is more to writing a standard
> container class than declaring two typedefs.

> But why even go to the trouble of converting your hashing
> container class to be a standard container, instead of just
> using one of the two that have already been written?

Because his hasher isn't a container at all, to begin with, at
least not in the sense of the standard.  He simply wants to fool
the system into thinking it's one.  Thus, for example, push_back
doesn't increase the size of container; it just changes some
internal state.

As I mentionned in my own response to his question, I considered
myself creating an "insertion iterator", an output iterator
which "pushed back" each element into the hasher, and decided
against it.  Somehow, a hasher just doesn't feel like a
container, and copying into it seems almost like obfuscation.
(Logically, I find that a hasher is more of an accumulator: it
has state of constant length, which changes each time you append
an element.  When attempting to make it conform to a "standard"
model or idiom of some sort, the most natural overload to me
seemed +=.  Although it's different enough that I probably
wouldn't have used it except that accumulate uses +, and I
didn't want + without +=.)

> From what I can tell, the two requirements for this container
> are a) a customizable hashing function b) standard container
> conformance. And given those criteria, std::tr1::unordered_set
> and std::tr1::unordered_map have no trouble qualifiying.

Except that he doesn't want standard container conformance.  In
particular, a function like size() doesn't make sense; if there
is a size(), it is a constant, and you certainly cannot meet the
post condition of the default constructor, that size() == 0.  I
can't find any formal requirement that size() == old.size() + 1
is a post-condition of push_back(), but I think it's implicit
from the other requirements, and I think we'd all be pretty
surprised if it wasn't true for something claiming to be a
container.

I think his question is really two questions: given something
that really isn't a container, but can be twisted to sort of
look like one for the sort of things that back_inserters do, is
it legal, and is it moral?  In my mind, the answer to the second
is a resounding no---giving the impression that something is a
container when it isn't will generally lead to the sort of
confusion about it that you seem to have.  The answer to the
first is a bit more complicated.  As you say, the insert
iterators in general seem to have been conceived with the
standard containers in mind.  And while it wouldn't be at all in
the philosophy of the STL if they wouldn't work equally as well
with a user defined container, the standard does seem rather
silent about what parts of the container requirements are really
requirements.  In the absense of any more definite statement, I
would say that to be a legal container argument for an insertion
iterator, a class must meet all of the container requirements
specified in    2.3.1---and as you say, there's a lot more too it
than just a few typedef's.  Logically, I can't imagine any
conceivable reason why an insertion iterator would need a
default constructor which creates an object of size() == 0, but
in the absense of any other specification, I'd say that that is
what the standard requires.

--
James Kanze                                           GABI Software
Conseils en informatique orient   e objet/
                   Beratung in objektorientierter Datenverarbeitung
9 place S   mard, 78210 St.-Cyr-l'   cole, France, +33 (0)1 30 23 00 34


---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]