Boost logo

Boost :

From: Craig Henderson (cdm.henderson_at_[hidden])
Date: 2002-10-07 08:58:21

"Bohdan" <warever_at_[hidden]> wrote in message
> 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
> 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.
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.

-- Craig

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