revise DHT hashing functions, add test logic

3 files changed, 275 insertions, 116 deletions

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 */