Boost logo

Boost :

From: Bohdan (warever_at_[hidden])
Date: 2002-10-07 11:43:07

"Craig Henderson" <cdm.henderson_at_[hidden]> wrote in message
> "Bohdan" <warever_at_[hidden]> wrote in message
> news:anrvs5$nc4$
> > I have question to your implementation. Line from crc_string.hpp :
> >
> > <code>
> > bool operator==(const crc_string<CharT> &other) const { return crc_ ==
> > other.crc_; }
> > <\code>
> >
> > I'm not expert on CRC, but is it correct ? Does crc equality guarantees
> 100%
> > strinds
> > equality ? I have doubts about it.
> CRC does not have 100% guarantee uniqueness. My implementation is used in a
> scenario where I know that the strings must be unique, and so can get away
> with this. In a generic solution, the case would need to be handled, perhaps
> by comparing the length of the strings and if they are equal, then the
> contents should be compared with a standard memcmp(). This will, of course,
> add overhead to the algorithm, but the obvious no-match cases will be
> handled very efficiently.
> Unforunately your has algorithm does not 100% guaranteed unique either.

Which algorithm ?
     ... If you are talking about hashof_ method than it doesn't
need to give absolutely unique values. And it is not my, i borrowed it from one
of stl implementations. I'm sure there no crc or hash algorithms that give you
100% unique values :o), so you should add "&& <real string comparison>" to make
crc_string correct.
     ... If you are talking about whole immutable_string / value pooling than
you are wrong. It guarantees string equality from references equality since
all used immutable_string values are uniquelly present in values pool.
Again this is not my idea :)

> However, it will (probably) cause less collisions than the CRC value because
> of the size of the hash. I use a 16-bit CRC despite storing it in a 32-bit
> value - this is just an oversight in my code. I suggest you take a look at
> the SAH1 algorithm - this has not, AFAIK, ever been seen to generate a
> duplicate value; unlike MD5.

As i said i'm not expert neither in crc nor in cryptography :( , but using crc
hash code seems interesting. I'll look at SAH1, MD5, boost::crc when i have

Thanks for help/ideas.

> -- Craig
> _______________________________________________
> Unsubscribe & other changes:

Boost list run by bdawes at, gregod at, cpdaniel at, john at