revise DHT hashing functions, add test logic

8 files changed, 358 insertions, 252 deletions

diff --git a/src/dht/gnunet-service-dht_datacache.c b/src/dht/gnunet-service-dht_datacache.c
index 8645ea069..a81cc9993 100644
--- a/src/dht/gnunet-service-dht_datacache.c
+++ b/src/dht/gnunet-service-dht_datacache.c
@@ -65,6 +65,7 @@ GDS_DATACACHE_handle_put (struct GNUNET_TIME_Absolute expiration,
                           size_t data_size,
                           const void *data)
 {
+  struct GNUNET_HashCode xor;
   int r;
 
   if (NULL == datacache)
@@ -83,10 +84,12 @@ GDS_DATACACHE_handle_put (struct GNUNET_TIME_Absolute expiration,
                             gettext_noop ("# ITEMS stored in datacache"),
                             1,
                             GNUNET_NO);
+  GNUNET_CRYPTO_hash_xor (key,
+                          &my_identity_hash,
+                          &xor);
   r = GNUNET_DATACACHE_put (datacache,
                             key,
-                            GNUNET_CRYPTO_hash_matching_bits (key,
-                                                              &my_identity_hash),
+                            GNUNET_CRYPTO_hash_count_leading_zeros (&xor),
                             data_size,
                             data,
                             type,
diff --git a/src/dht/gnunet-service-dht_neighbours.c b/src/dht/gnunet-service-dht_neighbours.c
index d48d2a5df..3cb788a06 100644
--- a/src/dht/gnunet-service-dht_neighbours.c
+++ b/src/dht/gnunet-service-dht_neighbours.c
@@ -430,9 +430,13 @@ static struct GNUNET_ATS_ConnectivityHandle *ats_ch;
 static int
 find_bucket (const struct GNUNET_HashCode *hc)
 {
+  struct GNUNET_HashCode xor;
   unsigned int bits;
 
-  bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash, hc);
+  GNUNET_CRYPTO_hash_xor (hc,
+                          &my_identity_hash,
+                          &xor);
+  bits = GNUNET_CRYPTO_hash_count_leading_zeros (&xor);
   if (bits == MAX_BUCKETS)
   {
     /* How can all bits match? Got my own ID? */
@@ -889,40 +893,6 @@ get_forward_count (uint32_t hop_count,
 
 
 /**
- * Compute the distance between have and target as a 64-bit value.
- * Differences in the lower bits must count stronger than differences
- * in the higher bits.
- *
- * @param target
- * @param have
- * @param bucket up to which offset are @a target and @a have identical and thus those bits should not be considered
- * @return 0 if have==target, otherwise a number
- *           that is larger as the distance between
- *           the two hash codes increases
- */
-static uint64_t
-get_distance (const struct GNUNET_HashCode *target,
-              const struct GNUNET_HashCode *have,
-              unsigned int bucket)
-{
-  uint64_t lsb = 0;
-
-  for (unsigned int i = bucket + 1;
-       (i < sizeof(struct GNUNET_HashCode) * 8) &&
-       (i < bucket + 1 + 64);
-       i++)
-  {
-    if (GNUNET_CRYPTO_hash_get_bit_rtl (target, i) !=
-        GNUNET_CRYPTO_hash_get_bit_rtl (have, i))
-      lsb |= (1LLU << (bucket + 64 - i));      /* first bit set will be 1,
-                                             * last bit set will be 63 -- if
-                                             * i does not reach 512 first... */
-  }
-  return lsb;
-}
-
-
-/**
  * Check whether my identity is closer than any known peers.  If a
  * non-null bloomfilter is given, check if this is the closest peer
  * that hasn't already been routed to.
@@ -936,7 +906,7 @@ enum GNUNET_GenericReturnValue
 GDS_am_closest_peer (const struct GNUNET_HashCode *key,
                      const struct GNUNET_CONTAINER_BloomFilter *bloom)
 {
-  int bits;
+  struct GNUNET_HashCode xor;
   int other_bits;
   int bucket_num;
   struct PeerInfo *pos;
@@ -946,8 +916,6 @@ GDS_am_closest_peer (const struct GNUNET_HashCode *key,
     return GNUNET_YES;
   bucket_num = find_bucket (key);
   GNUNET_assert (bucket_num >= 0);
-  bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
-                                           key);
   pos = k_buckets[bucket_num].head;
   while (NULL != pos)
   {
@@ -959,9 +927,11 @@ GDS_am_closest_peer (const struct GNUNET_HashCode *key,
       pos = pos->next;
       continue;                 /* Skip already checked entries */
     }
-    other_bits = GNUNET_CRYPTO_hash_matching_bits (&pos->phash,
-                                                   key);
-    if (other_bits > bits)
+    GNUNET_CRYPTO_hash_xor (&pos->phash,
+                            key,
+                            &xor);
+    other_bits = GNUNET_CRYPTO_hash_count_leading_zeros (&xor);
+    if (other_bits > bucket_num)
       return GNUNET_NO;
     pos = pos->next;
   }
@@ -1013,14 +983,16 @@ select_peer (const struct GNUNET_HashCode *key,
            (count < bucket_size);
            pos = pos->next)
       {
+        struct GNUNET_HashCode xor;
         unsigned int bucket;
         uint64_t dist;
 
-        bucket = GNUNET_CRYPTO_hash_matching_bits (key,
-                                                   &pos->phash);
-        dist = get_distance (key,
-                             &pos->phash,
-                             bucket);
+        GNUNET_CRYPTO_hash_xor (key,
+                                &pos->phash,
+                                &xor);
+        bucket = GNUNET_CRYPTO_hash_count_leading_zeros (&xor);
+        dist = GNUNET_CRYPTO_hash_bucket_distance (&xor,
+                                                   bucket);
         if (bucket < best_bucket)
           continue;
         if (dist > best_in_bucket)
@@ -1691,7 +1663,15 @@ handle_dht_p2p_put (void *cls,
   {
     char *tmp;
     char *pp;
-
+    struct GNUNET_HashCode mxor;
+    struct GNUNET_HashCode pxor;
+
+    GNUNET_CRYPTO_hash_xor (&my_identity_hash,
+                            &put->key,
+                            &mxor);
+    GNUNET_CRYPTO_hash_xor (&peer->phash,
+                            &put->key,
+                            &pxor);
     pp = GNUNET_STRINGS_pp2s (put_path,
                               putlen);
     tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
@@ -1701,10 +1681,8 @@ handle_dht_p2p_put (void *cls,
                  GNUNET_i2s (peer->id),
                  tmp,
                  ntohl (put->hop_count),
-                 GNUNET_CRYPTO_hash_matching_bits (&peer->phash,
-                                                   &put->key),
-                 GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
-                                                   &put->key),
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&pxor),
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&mxor),
                  pp);
     GNUNET_free (pp);
     GNUNET_free (tmp);
@@ -2070,7 +2048,15 @@ handle_dht_p2p_get (void *cls,
   if (GNUNET_YES == log_route_details_stderr)
   {
     char *tmp;
-
+    struct GNUNET_HashCode mxor;
+    struct GNUNET_HashCode pxor;
+
+    GNUNET_CRYPTO_hash_xor (&my_identity_hash,
+                            &get->key,
+                            &mxor);
+    GNUNET_CRYPTO_hash_xor (&peer->phash,
+                            &get->key,
+                            &pxor);
     tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
     LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
                  "R5N GET %s: %s->%s (%u, %u=>%u) xq: %.*s\n",
@@ -2078,10 +2064,8 @@ handle_dht_p2p_get (void *cls,
                  GNUNET_i2s (peer->id),
                  tmp,
                  ntohl (get->hop_count),
-                 GNUNET_CRYPTO_hash_matching_bits (&peer->phash,
-                                                   &get->key),
-                 GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
-                                                   &get->key),
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&pxor),
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&mxor),
                  ntohl (get->xquery_size),
                  (const char *) xquery);
     GNUNET_free (tmp);
diff --git a/src/include/gnunet_crypto_lib.h b/src/include/gnunet_crypto_lib.h
index bd318ab84..4e26429c9 100644
--- a/src/include/gnunet_crypto_lib.h
+++ b/src/include/gnunet_crypto_lib.h
@@ -1038,61 +1038,53 @@ GNUNET_CRYPTO_hash_xor (const struct GNUNET_HashCode *a,
 
 
 /**
- * @ingroup hash
- * Convert a hashcode into a key.
+ * Count the number of leading 0 bits in @a h.
  *
- * @param hc hash code that serves to generate the key
- * @param skey set to a valid session key
- * @param iv set to a valid initialization vector
+ * @param h a hash
+ * @return number of leading 0 bits in @a h
  */
-void
-GNUNET_CRYPTO_hash_to_aes_key (
-  const struct GNUNET_HashCode *hc,
-  struct GNUNET_CRYPTO_SymmetricSessionKey *skey,
-  struct GNUNET_CRYPTO_SymmetricInitializationVector *iv);
+unsigned int
+GNUNET_CRYPTO_hash_count_leading_zeros (const struct GNUNET_HashCode *h);
 
 
 /**
- * @ingroup hash
- * Obtain a bit from a hashcode.
+ * Count the number of tailing 0 bits in @a h.
  *
- * @param code the `struct GNUNET_HashCode` to index bit-wise
- * @param bit index into the hashcode, [0...159] where 0 is the leftmost bit
- *        (bytes in code interpreted big endian)
- * @return Bit \a bit from hashcode \a code, -1 for invalid index
+ * @param h a hash
+ * @return number of tailing 0 bits in @a h
  */
-int
-GNUNET_CRYPTO_hash_get_bit_ltr (const struct GNUNET_HashCode *code,
-                                unsigned int bit);
+unsigned int
+GNUNET_CRYPTO_hash_count_tailing_zeros (const struct GNUNET_HashCode *h);
 
 
 /**
- * Obtain a bit from a hashcode.
- * @param code the GNUNET_CRYPTO_hash to index bit-wise
- * @param bit index into the hashcode, [0...511] where 0 is the rightmost bit
- *        (bytes in code interpreted little endian)
- * @return Bit \a bit from hashcode \a code, -1 for invalid index
+ * Compute the distance between have and target as a 64-bit value.
+ * Differences in the lower bits must count stronger than differences
+ * in the higher bits.
+ *
+ * @param xor input hash
+ * @param bucket up to which offset we are to ignore @a xor
+ * @return the subsequent 64 bits after @a bucket from @a xor, in
+ *  host byte order.
  */
-int
-GNUNET_CRYPTO_hash_get_bit_rtl (const struct GNUNET_HashCode *code,
-                                unsigned int bit);
+uint64_t
+GNUNET_CRYPTO_hash_bucket_distance (const struct GNUNET_HashCode *xor,
+                                    unsigned int bucket);
 
 
 /**
  * @ingroup hash
- * Determine how many low order bits match in two
- * `struct GNUNET_HashCodes`.  e.g. - 010011 and 011111 share
- * the first two lowest order bits, and therefore the
- * return value is two (NOT XOR distance, nor how many
- * bits match absolutely!).
+ * Convert a hashcode into a key.
  *
- * @param first the first hashcode
- * @param second the hashcode to compare first to
- * @return the number of bits that match
+ * @param hc hash code that serves to generate the key
+ * @param skey set to a valid session key
+ * @param iv set to a valid initialization vector
  */
-unsigned int
-GNUNET_CRYPTO_hash_matching_bits (const struct GNUNET_HashCode *first,
-                                  const struct GNUNET_HashCode *second);
+void
+GNUNET_CRYPTO_hash_to_aes_key (
+  const struct GNUNET_HashCode *hc,
+  struct GNUNET_CRYPTO_SymmetricSessionKey *skey,
+  struct GNUNET_CRYPTO_SymmetricInitializationVector *iv);
 
 
 /**
diff --git a/src/nse/gnunet-service-nse.c b/src/nse/gnunet-service-nse.c
index 972b3a79d..35278db29 100644
--- a/src/nse/gnunet-service-nse.c
+++ b/src/nse/gnunet-service-nse.c
@@ -774,24 +774,6 @@ update_flood_message (void *cls)
 
 
 /**
- * Count the leading zeroes in hash.
- *
- * @param hash to count leading zeros in
- * @return the number of leading zero bits.
- */
-static unsigned int
-count_leading_zeroes (const struct GNUNET_HashCode *hash)
-{
-  unsigned int hash_count;
-
-  hash_count = 0;
-  while (0 == GNUNET_CRYPTO_hash_get_bit_ltr (hash, hash_count))
-    hash_count++;
-  return hash_count;
-}
-
-
-/**
  * Check whether the given public key and integer are a valid proof of
  * work.
  *
@@ -799,7 +781,7 @@ count_leading_zeroes (const struct GNUNET_HashCode *hash)
  * @param val the integer
  * @return #GNUNET_YES if valid, #GNUNET_NO if not
  */
-static int
+static enum GNUNET_GenericReturnValue
 check_proof_of_work (const struct GNUNET_CRYPTO_EddsaPublicKey *pkey,
                      uint64_t val)
 {
@@ -815,8 +797,10 @@ check_proof_of_work (const struct GNUNET_CRYPTO_EddsaPublicKey *pkey,
                           buf,
                           sizeof(buf),
                           &result);
-  return (count_leading_zeroes (&result) >= nse_work_required) ? GNUNET_YES
-         : GNUNET_NO;
+  return (GNUNET_CRYPTO_hash_count_leading_zeroes (&result) >=
+          nse_work_required)
+    ? GNUNET_YES
+    : GNUNET_NO;
 }
 
 
@@ -877,7 +861,8 @@ find_proof (void *cls)
                             buf,
                             sizeof(buf),
                             &result);
-    if (nse_work_required <= count_leading_zeroes (&result))
+    if (nse_work_required <=
+        GNUNET_CRYPTO_hash_count_leading_zeroes (&result))
     {
       my_proof = counter;
       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
diff --git a/src/revocation/revocation_api.c b/src/revocation/revocation_api.c
index f2b95bafa..1032b98f7 100644
--- a/src/revocation/revocation_api.c
+++ b/src/revocation/revocation_api.c
@@ -389,23 +389,6 @@ GNUNET_REVOCATION_revoke_cancel (struct GNUNET_REVOCATION_Handle *h)
 
 
 /**
- * Count the leading zeroes in hash.
- *
- * @param hash to count leading zeros in
- * @return the number of leading zero bits.
- */
-static unsigned int
-count_leading_zeroes (const struct GNUNET_HashCode *hash)
-{
-  unsigned int hash_count;
-  hash_count = 0;
-  while ((0 == GNUNET_CRYPTO_hash_get_bit_ltr (hash, hash_count)))
-    hash_count++;
-  return hash_count;
-}
-
-
-/**
  * Calculate the average zeros in the pows.
  *
  * @param ph the PowHandle
@@ -535,7 +518,7 @@ GNUNET_REVOCATION_check_pow (const struct GNUNET_REVOCATION_PowP *pow,
                             buf,
                             sizeof(buf),
                             &result);
-    tmp_score = count_leading_zeroes (&result);
+    tmp_score = GNUNET_CRYPTO_hash_count_leading_zeroes (&result);
     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                 "Score %u with %" PRIu64 " (#%u)\n",
                 tmp_score, pow_val, i);
diff --git a/src/util/crypto_hash.c b/src/util/crypto_hash.c
index d62ec8012..b51ecd242 100644
--- a/src/util/crypto_hash.c
+++ b/src/util/crypto_hash.c
@@ -135,18 +135,57 @@ GNUNET_CRYPTO_hash_xor (const struct GNUNET_HashCode *a,
                         const struct GNUNET_HashCode *b,
                         struct GNUNET_HashCode *result)
 {
-  for (ssize_t i = (sizeof(struct GNUNET_HashCode) / sizeof(unsigned int)) - 1;
-       i >= 0;
-       i--)
-    result->bits[i] = a->bits[i] ^ b->bits[i];
+  const unsigned long long *lla = (const unsigned long long *) a;
+  const unsigned long long *llb = (const unsigned long long *) b;
+  unsigned long long *llr = (unsigned long long *) result;
+
+  GNUNET_static_assert (8 == sizeof (unsigned long long));
+  GNUNET_static_assert (0 == sizeof (*a) % sizeof (unsigned long long));
+  for (int i = sizeof (*result) / sizeof (*llr) - 1; i>=0; i--)
+    llr[i] = lla[i] ^ llb[i];
+}
+
+
+uint64_t
+GNUNET_CRYPTO_hash_bucket_distance (const struct GNUNET_HashCode *xor,
+                                    unsigned int bucket)
+{
+  const uint64_t *u = (const uint64_t *) xor;
+  unsigned int idx;
+  unsigned int bits;
+  uint64_t rval;
+
+  if (bucket == 8 * sizeof(*xor))
+    return 0;
+  bucket++;
+  idx = bucket / 64;
+  bits = bucket % 64;
+  if (idx >= sizeof (*xor) / sizeof (*u))
+    return 0;
+  if (0 == bits)
+  {
+    /* keeps no bits */
+    rval = 0;
+  }
+  else
+  {
+    /* keeps lowest (64-bits) bits */
+    rval = GNUNET_ntohll (u[idx]) << bits;
+  }
+  if (idx + 1 < sizeof (*xor) / sizeof (*u))
+  {
+    /* discards lowest (bits) bits */
+    rval |= GNUNET_ntohll (u[idx + 1]) >> (64 - bits);
+  }
+  return rval;
 }
 
 
 void
-GNUNET_CRYPTO_hash_to_aes_key (const struct GNUNET_HashCode *hc,
-                               struct GNUNET_CRYPTO_SymmetricSessionKey *skey,
-                               struct
-                               GNUNET_CRYPTO_SymmetricInitializationVector *iv)
+GNUNET_CRYPTO_hash_to_aes_key (
+  const struct GNUNET_HashCode *hc,
+  struct GNUNET_CRYPTO_SymmetricSessionKey *skey,
+  struct GNUNET_CRYPTO_SymmetricInitializationVector *iv)
 {
   GNUNET_assert (GNUNET_YES ==
                  GNUNET_CRYPTO_kdf (
@@ -167,33 +206,47 @@ GNUNET_CRYPTO_hash_to_aes_key (const struct GNUNET_HashCode *hc,
 }
 
 
-int
-GNUNET_CRYPTO_hash_get_bit_ltr (const struct GNUNET_HashCode *code,
-                                unsigned int bit)
+unsigned int
+GNUNET_CRYPTO_hash_count_leading_zeros (const struct GNUNET_HashCode *h)
 {
-  GNUNET_assert (bit < 8 * sizeof(struct GNUNET_HashCode));
-  return (((unsigned char *) code)[bit >> 3] & (128 >> (bit & 7))) > 0;
-}
-
+  const unsigned long long *llp = (const unsigned long long *) h;
+  unsigned int ret = 0;
+  unsigned int i;
 
-int
-GNUNET_CRYPTO_hash_get_bit_rtl (const struct GNUNET_HashCode *code,
-                                unsigned int bit)
-{
-  GNUNET_assert (bit < 8 * sizeof(struct GNUNET_HashCode));
-  return (((unsigned char *) code)[bit >> 3] & (1 << (bit & 7))) > 0;
+  GNUNET_static_assert (8 == sizeof (unsigned long long));
+  GNUNET_static_assert (0 == sizeof (*h) % sizeof (unsigned long long));
+  for (i = 0; i<sizeof (*h) / sizeof (*llp); i++)
+  {
+    if (0LLU != llp[i])
+      break;
+    ret += sizeof (*llp) * 8;
+  }
+  if (ret == 8 * sizeof (*h))
+    return ret;
+  ret += __builtin_clzll (GNUNET_ntohll ((uint64_t) llp[i]));
+  return ret;
 }
 
 
 unsigned int
-GNUNET_CRYPTO_hash_matching_bits (const struct GNUNET_HashCode *first,
-                                  const struct GNUNET_HashCode *second)
+GNUNET_CRYPTO_hash_count_tailing_zeros (const struct GNUNET_HashCode *h)
 {
-  for (unsigned int i = 0; i < sizeof(struct GNUNET_HashCode) * 8; i++)
-    if (GNUNET_CRYPTO_hash_get_bit_rtl (first, i) !=
-        GNUNET_CRYPTO_hash_get_bit_rtl (second, i))
-      return i;
-  return sizeof(struct GNUNET_HashCode) * 8;
+  const unsigned long long *llp = (const unsigned long long *) h;
+  unsigned int ret = 0;
+  int i;
+
+  GNUNET_static_assert (8 == sizeof (unsigned long long));
+  GNUNET_static_assert (0 == sizeof (*h) % sizeof (unsigned long long));
+  for (i = sizeof (*h) / sizeof (*llp) - 1; i>=0; i--)
+  {
+    if (0LLU != llp[i])
+      break;
+    ret += sizeof (*llp) * 8;
+  }
+  if (ret == 8 * sizeof (*h))
+    return ret;
+  ret += __builtin_ctzll (GNUNET_ntohll ((uint64_t) llp[i]));
+  return ret;
 }
 
 
@@ -243,25 +296,30 @@ GNUNET_CRYPTO_hash_xorcmp (const struct GNUNET_HashCode *h1,
 
 
 void
-GNUNET_CRYPTO_hmac_derive_key (struct GNUNET_CRYPTO_AuthKey *key,
-                               const struct
-                               GNUNET_CRYPTO_SymmetricSessionKey *rkey,
-                               const void *salt, size_t salt_len, ...)
+GNUNET_CRYPTO_hmac_derive_key (
+  struct GNUNET_CRYPTO_AuthKey *key,
+  const struct GNUNET_CRYPTO_SymmetricSessionKey *rkey,
+  const void *salt, size_t salt_len,
+  ...)
 {
   va_list argp;
 
-  va_start (argp, salt_len);
-  GNUNET_CRYPTO_hmac_derive_key_v (key, rkey, salt, salt_len, argp);
+  va_start (argp,
+            salt_len);
+  GNUNET_CRYPTO_hmac_derive_key_v (key,
+                                   rkey,
+                                   salt, salt_len,
+                                   argp);
   va_end (argp);
 }
 
 
 void
-GNUNET_CRYPTO_hmac_derive_key_v (struct GNUNET_CRYPTO_AuthKey *key,
-                                 const struct
-                                 GNUNET_CRYPTO_SymmetricSessionKey *rkey,
-                                 const void *salt, size_t salt_len,
-                                 va_list argp)
+GNUNET_CRYPTO_hmac_derive_key_v (
+  struct GNUNET_CRYPTO_AuthKey *key,
+  const struct GNUNET_CRYPTO_SymmetricSessionKey *rkey,
+  const void *salt, size_t salt_len,
+  va_list argp)
 {
   GNUNET_CRYPTO_kdf_v (key->key, sizeof(key->key),
                        salt, salt_len,
@@ -283,7 +341,9 @@ GNUNET_CRYPTO_hmac_raw (const void *key, size_t key_len,
   {
     once = 1;
     GNUNET_assert (GPG_ERR_NO_ERROR ==
-                   gcry_md_open (&md, GCRY_MD_SHA512, GCRY_MD_FLAG_HMAC));
+                   gcry_md_open (&md,
+                                 GCRY_MD_SHA512,
+                                 GCRY_MD_FLAG_HMAC));
   }
   else
   {
@@ -323,15 +383,12 @@ GNUNET_CRYPTO_hash_context_start ()
   struct GNUNET_HashContext *hc;
 
   BENCHMARK_START (hash_context_start);
-
   hc = GNUNET_new (struct GNUNET_HashContext);
   GNUNET_assert (0 ==
                  gcry_md_open (&hc->hd,
                                GCRY_MD_SHA512,
                                0));
-
   BENCHMARK_END (hash_context_start);
-
   return hc;
 }
 
diff --git a/src/util/gnunet-scrypt.c b/src/util/gnunet-scrypt.c
index fe8b6769f..ad46e3f39 100644
--- a/src/util/gnunet-scrypt.c
+++ b/src/util/gnunet-scrypt.c
@@ -78,24 +78,6 @@ shutdown_task (void *cls)
 
 
 /**
- * Count the leading zeroes in hash.
- *
- * @param hash to count leading zeros in
- * @return the number of leading zero bits.
- */
-static unsigned int
-count_leading_zeroes (const struct GNUNET_HashCode *hash)
-{
-  unsigned int hash_count;
-
-  hash_count = 0;
-  while (0 == GNUNET_CRYPTO_hash_get_bit_ltr (hash, hash_count))
-    hash_count++;
-  return hash_count;
-}
-
-
-/**
  * Find our proof of work.
  *
  * @param cls closure (unused)
@@ -131,7 +113,8 @@ find_proof (void *cls)
                             buf,
                             sizeof(buf),
                             &result);
-    if (nse_work_required <= count_leading_zeroes (&result))
+    if (nse_work_required <=
+        GNUNET_CRYPTO_hash_count_leading_zeros (&result))
     {
       proof = counter;
       fprintf (stdout,
diff --git a/src/util/test_crypto_hash.c b/src/util/test_crypto_hash.c
index d22e1f5d3..1fddcfba8 100644
--- a/src/util/test_crypto_hash.c
+++ b/src/util/test_crypto_hash.c
@@ -1,6 +1,6 @@
 /*
      This file is part of GNUnet.
-     Copyright (C) 2002, 2003, 2004, 2006, 2009 GNUnet e.V.
+     Copyright (C) 2002, 2003, 2004, 2006, 2009, 2022 GNUnet e.V.
 
      GNUnet is free software: you can redistribute it and/or modify it
      under the terms of the GNU Affero General Public License as published
@@ -37,25 +37,29 @@ test (int number)
   struct GNUNET_HashCode h2;
   struct GNUNET_CRYPTO_HashAsciiEncoded enc;
 
-  memset (&h1, number, sizeof(struct GNUNET_HashCode));
-  GNUNET_CRYPTO_hash_to_enc (&h1, &enc);
-  if (GNUNET_OK != GNUNET_CRYPTO_hash_from_string ((char *) &enc, &h2))
+  memset (&h1,
+          number,
+          sizeof(struct GNUNET_HashCode));
+  GNUNET_CRYPTO_hash_to_enc (&h1,
+                             &enc);
+  if (GNUNET_OK !=
+      GNUNET_CRYPTO_hash_from_string ((char *) &enc,
+                                      &h2))
   {
     printf ("enc2hash failed!\n");
     return 1;
   }
-  if (0 != memcmp (&h1, &h2, sizeof(struct GNUNET_HashCode)))
+  if (0 != GNUNET_memcmp (&h1,
+                          &h2))
     return 1;
   return 0;
 }
 
 
 static int
-testEncoding ()
+test_encoding (void)
 {
-  int i;
-
-  for (i = 0; i < 255; i++)
+  for (int i = 0; i < 255; i++)
     if (0 != test (i))
       return 1;
   return 0;
@@ -63,7 +67,7 @@ testEncoding ()
 
 
 static int
-testArithmetic ()
+test_arithmetic (void)
 {
   struct GNUNET_HashCode h1;
   struct GNUNET_HashCode h2;
@@ -72,49 +76,150 @@ testArithmetic ()
   struct GNUNET_CRYPTO_SymmetricSessionKey skey;
   struct GNUNET_CRYPTO_SymmetricInitializationVector iv;
 
-  GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_WEAK, &h1);
-  GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_WEAK, &h2);
-  if (GNUNET_CRYPTO_hash_distance_u32 (&h1, &h2) !=
-      GNUNET_CRYPTO_hash_distance_u32 (&h2, &h1))
-    return 1;
-  GNUNET_CRYPTO_hash_difference (&h1, &h2, &d);
-  GNUNET_CRYPTO_hash_sum (&h1, &d, &s);
-  if (0 != GNUNET_CRYPTO_hash_cmp (&s, &h2))
-    return 1;
-  GNUNET_CRYPTO_hash_xor (&h1, &h2, &d);
-  GNUNET_CRYPTO_hash_xor (&h1, &d, &s);
-  if (0 != GNUNET_CRYPTO_hash_cmp (&s, &h2))
-    return 1;
-  if (0 != GNUNET_CRYPTO_hash_xorcmp (&s, &h2, &h1))
-    return 1;
-  if (-1 != GNUNET_CRYPTO_hash_xorcmp (&h1, &h2, &h1))
+  GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_WEAK,
+                                    &h1);
+  GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_WEAK,
+                                    &h2);
+  if (GNUNET_CRYPTO_hash_distance_u32 (&h1,
+                                       &h2) !=
+      GNUNET_CRYPTO_hash_distance_u32 (&h2,
+                                       &h1))
     return 1;
-  if (1 != GNUNET_CRYPTO_hash_xorcmp (&h1, &h2, &h2))
+  GNUNET_CRYPTO_hash_difference (&h1,
+                                 &h2,
+                                 &d);
+  GNUNET_CRYPTO_hash_sum (&h1,
+                          &d,
+                          &s);
+  if (0 !=
+      GNUNET_CRYPTO_hash_cmp (&s,
+                              &h2))
     return 1;
-  memset (&d, 0x40, sizeof(d));
-  if (0 != GNUNET_CRYPTO_hash_get_bit_rtl (&d, 3))
+  GNUNET_CRYPTO_hash_xor (&h1,
+                          &h2,
+                          &d);
+  GNUNET_CRYPTO_hash_xor (&h1,
+                          &d,
+                          &s);
+  if (0 !=
+      GNUNET_CRYPTO_hash_cmp (&s,
+                              &h2))
     return 1;
-  if (1 != GNUNET_CRYPTO_hash_get_bit_rtl (&d, 6))
+  if (0 !=
+      GNUNET_CRYPTO_hash_xorcmp (&s,
+                                 &h2,
+                                 &h1))
     return 1;
-  memset (&d, 0x02, sizeof(d));
-  if (0 != GNUNET_CRYPTO_hash_get_bit_ltr (&d, 3))
+  if (-1 !=
+      GNUNET_CRYPTO_hash_xorcmp (&h1,
+                                 &h2,
+                                 &h1))
     return 1;
-  if (1 != GNUNET_CRYPTO_hash_get_bit_ltr (&d, 6))
+  if (1 !=
+      GNUNET_CRYPTO_hash_xorcmp (&h1,
+                                 &h2,
+                                 &h2))
     return 1;
-  memset (&d, 0, sizeof(d));
-  GNUNET_CRYPTO_hash_to_aes_key (&d, &skey, &iv);
+  memset (&d,
+          0,
+          sizeof(d));
+  GNUNET_CRYPTO_hash_to_aes_key (&d,
+                                 &skey,
+                                 &iv);
+  memset (&h1,
+          0,
+          sizeof (h1));
+  h1.bits[1] = htonl (0x00200000); /* 32 + 8 + 2 = 42 MSB bits cleared */
+  GNUNET_assert (42 ==
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&h1));
+  GNUNET_assert (512 - 42 - 1 ==
+                 GNUNET_CRYPTO_hash_count_tailing_zeros (&h1));
+  memset (&h1,
+          0,
+          sizeof (h1));
+  memset (&h2,
+          0,
+          sizeof (h2));
+  h1.bits[3] = htonl (0x00800011); /* 3*32 + 8 Bits identical */
+  h2.bits[3] = htonl (0x00000101); /* residual delta: 0x000220.. (+1 bit)*/
+  /* Note: XOR:       0x00800110 */
+  h1.bits[4] = htonl (0x14144141);
+  h2.bits[4] = htonl (0x28288282); /* residual delta: 0x3C3CC3.. */
+  /* Note: XOR:       0x3C3CC3C3 */
+  /* Note: XOR<<1:    0x78798786 */
+  GNUNET_assert (104 ==
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&h1));
+  GNUNET_CRYPTO_hash_xor (&h1,
+                          &h2,
+                          &s);
+  GNUNET_assert (104 ==
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&s));
+  GNUNET_assert (0x0002207879878600LLU ==
+                 GNUNET_CRYPTO_hash_bucket_distance (&s,
+                                                     104));
+
+  memset (&h1,
+          0,
+          sizeof (h1));
+  memset (&h2,
+          0,
+          sizeof (h2));
+  h1.bits[4] = htonl (0x00000001); /* 5*32 - 1 Bits identical */
+  h2.bits[4] = htonl (0x00000000);
+  /* Note: XOR:       0x00000001 */
+  h1.bits[5] = htonl (0x14144141);
+  h2.bits[5] = htonl (0x28288282);
+  /* Note: XOR:       0x3C3CC3C3 */
+  GNUNET_assert (159 ==
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&h1));
+  GNUNET_CRYPTO_hash_xor (&h1,
+                          &h2,
+                          &s);
+  GNUNET_assert (159 ==
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&s));
+  GNUNET_assert (0x3C3CC3C300000000 ==
+                 GNUNET_CRYPTO_hash_bucket_distance (&s,
+                                                     159));
+
+  memset (&h1,
+          0,
+          sizeof (h1));
+  memset (&h2,
+          0,
+          sizeof (h2));
+  h1.bits[14] = htonl (0x00000001); /* 15*32 - 1 Bits identical */
+  h2.bits[14] = htonl (0x00000000);
+  /* Note: XOR:       0x00000001 */
+  h1.bits[15] = htonl (0x14144141);
+  h2.bits[15] = htonl (0x28288282);
+  /* Note: XOR:       0x3C3CC3C3 */
+  GNUNET_assert (479 ==
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&h1));
+  GNUNET_CRYPTO_hash_xor (&h1,
+                          &h2,
+                          &s);
+  GNUNET_assert (479 ==
+                 GNUNET_CRYPTO_hash_count_leading_zeros (&s));
+  GNUNET_assert (0x3C3CC3C300000000 ==
+                 GNUNET_CRYPTO_hash_bucket_distance (&s,
+                                                     479));
+
   return 0;
 }
 
 
 static void
-finished_task (void *cls, const struct GNUNET_HashCode *res)
+finished_task (void *cls,
+               const struct GNUNET_HashCode *res)
 {
   int *ret = cls;
   struct GNUNET_HashCode want;
 
-  GNUNET_CRYPTO_hash (block, sizeof(block), &want);
-  if (0 != memcmp (res, &want, sizeof(want)))
+  GNUNET_CRYPTO_hash (block,
+                      sizeof(block),
+                      &want);
+  if (0 != GNUNET_memcmp (res,
+                          &want))
     *ret = 2;
   else
     *ret = 0;
@@ -126,43 +231,57 @@ file_hasher (void *cls)
 {
   GNUNET_assert (NULL !=
                  GNUNET_CRYPTO_hash_file (GNUNET_SCHEDULER_PRIORITY_DEFAULT,
-                                          FILENAME, 1024, &finished_task, cls));
+                                          FILENAME,
+                                          1024,
+                                          &finished_task,
+                                          cls));
 }
 
 
 static int
-testFileHash ()
+test_file_hash (void)
 {
   int ret;
   FILE *f;
 
-  memset (block, 42, sizeof(block) / 2);
-  memset (&block[sizeof(block) / 2], 43, sizeof(block) / 2);
+  memset (block,
+          42,
+          sizeof(block) / 2);
+  memset (&block[sizeof(block) / 2],
+          43,
+          sizeof(block) / 2);
   GNUNET_assert (NULL != (f = fopen (FILENAME, "w+")));
-  GNUNET_break (sizeof(block) == fwrite (block, 1, sizeof(block), f));
+  GNUNET_break (sizeof(block) ==
+                fwrite (block,
+                        1,
+                        sizeof(block),
+                        f));
   GNUNET_break (0 == fclose (f));
   ret = 1;
-  GNUNET_SCHEDULER_run (&file_hasher, &ret);
+  GNUNET_SCHEDULER_run (&file_hasher,
+                        &ret);
   GNUNET_break (0 == unlink (FILENAME));
   return ret;
 }
 
 
 int
-main (int argc, char *argv[])
+main (int argc,
+      char *argv[])
 {
   int failureCount = 0;
-  int i;
-
-  GNUNET_log_setup ("test-crypto-hash", "WARNING", NULL);
-  for (i = 0; i < 10; i++)
-    failureCount += testEncoding ();
-  failureCount += testArithmetic ();
-  failureCount += testFileHash ();
-  if (failureCount != 0)
+
+  GNUNET_log_setup ("test-crypto-hash",
+                    "WARNING",
+                    NULL);
+  for (int i = 0; i < 10; i++)
+    failureCount += test_encoding ();
+  failureCount += test_arithmetic ();
+  failureCount += test_file_hash ();
+  if (0 != failureCount)
     return 1;
   return 0;
 }
 
 
-/* end of hashingtest.c */
+/* end of test_crypto_hash.c */