0
$\begingroup$

I came across this implementation of PJW and it seems incorrect:

  h = ( h << 4 ) + ( k );
  if( ( g = ( h & 0xf0000000 ) ) != 0 )
  {
    h = ( h ^ ( g >> 24 ) ) ^ g;
  }

In a more readable form:

  h = ( h << 4 ) + k;
  g = h & 0xf0000000;
  if( g != 0 )
      h = h ^ ( g >> 24 ) ^ g;

(Syntax: << and >> are bit shift operators, & is bitwise and, | is bitwise or, ^ is bitwise xor, ~ is bitwise negation, = is assignment, != is not-equal.)

Should it resemble this instead?

    h = ( h << 4 ) + s;
    s = s + 1;
    high = h & 0xF0000000;
    if ( high != 0 )
        h = h ^ (high >> 24);
    h = h & ~high;

A DrDobbs article says "Unfortunately, Holub's version contains an error that was picked up in subsequent texts (including the first printing of Practical Algorithms for Programmers, by John Rex and myself). The bug does not prevent the code from working, it simply gives suboptimal hashes." and I'm wondering if the difference between the top and bottom (edited) is that misprint.

$\endgroup$
  • 1
    $\begingroup$ You can find the correct implementation on Wikipedia: en.wikipedia.org/wiki/PJW_hash_function. $\endgroup$ – Yuval Filmus Jul 25 '18 at 15:12
  • $\begingroup$ This question seems off-topic here. I'm not sure where it would be on-topic. Perhaps Cryptography? $\endgroup$ – Yuval Filmus Jul 25 '18 at 15:13
  • $\begingroup$ It's not a cryptographic hash function. I have yet to compare the two implementations, thought I could find a quick answer here. $\endgroup$ – H464 Jul 25 '18 at 15:17
  • $\begingroup$ @YuvalFilmus While the question is formulated with C code, it's about the algorithm, so it's on-topic here. I've edited it to make it readable without having to know C syntax. $\endgroup$ – Gilles Jul 25 '18 at 20:51
  • $\begingroup$ It's like asking whether 54978945 is the correct magic constant, or should it actually be 97983475. $\endgroup$ – Yuval Filmus Jul 25 '18 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.