diff mbox series

[v8,1/4] util/uuid: add a hash function

Message ID 20230908154743.809569-2-aesteve@redhat.com (mailing list archive)
State New, archived
Headers show
Series Virtio shared dma-buf | expand

Commit Message

Albert Esteve Sept. 8, 2023, 3:47 p.m. UTC 
Add hash function to uuid module using the
djb2 hash algorithm.

Add a couple simple unit tests for the hash
function, checking collisions for similar UUIDs.

Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org>
Signed-off-by: Albert Esteve <aesteve@redhat.com>
---
 include/qemu/uuid.h    |  2 ++
 tests/unit/test-uuid.c | 27 +++++++++++++++++++++++++++
 util/uuid.c            | 15 +++++++++++++++
 3 files changed, 44 insertions(+)

Comments

Michael S. Tsirkin Oct. 1, 2023, 8:15 p.m. UTC | #1 
On Fri, Sep 08, 2023 at 05:47:40PM +0200, Albert Esteve wrote:
> Add hash function to uuid module using the
> djb2 hash algorithm.
> 
> Add a couple simple unit tests for the hash
> function, checking collisions for similar UUIDs.
> 
> Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org>
> Signed-off-by: Albert Esteve <aesteve@redhat.com>
> ---
>  include/qemu/uuid.h    |  2 ++
>  tests/unit/test-uuid.c | 27 +++++++++++++++++++++++++++
>  util/uuid.c            | 15 +++++++++++++++
>  3 files changed, 44 insertions(+)
> 
> diff --git a/include/qemu/uuid.h b/include/qemu/uuid.h
> index dc40ee1fc9..e24a1099e4 100644
> --- a/include/qemu/uuid.h
> +++ b/include/qemu/uuid.h
> @@ -96,4 +96,6 @@ int qemu_uuid_parse(const char *str, QemuUUID *uuid);
>  
>  QemuUUID qemu_uuid_bswap(QemuUUID uuid);
>  
> +uint32_t qemu_uuid_hash(const void *uuid);
> +
>  #endif
> diff --git a/tests/unit/test-uuid.c b/tests/unit/test-uuid.c
> index c111de5fc1..aedc125ae9 100644
> --- a/tests/unit/test-uuid.c
> +++ b/tests/unit/test-uuid.c
> @@ -171,6 +171,32 @@ static void test_uuid_unparse_strdup(void)
>      }
>  }
>  
> +static void test_uuid_hash(void)
> +{
> +    QemuUUID uuid;
> +    int i;
> +
> +    for (i = 0; i < 100; i++) {
> +        qemu_uuid_generate(&uuid);
> +        /* Obtain the UUID hash */
> +        uint32_t hash_a = qemu_uuid_hash(&uuid);
> +        int data_idx = g_random_int_range(0, 15);
> +        /* Change a single random byte of the UUID */
> +        if (uuid.data[data_idx] < 0xFF) {
> +            uuid.data[data_idx]++;
> +        } else {
> +            uuid.data[data_idx]--;
> +        }
> +        /* Obtain the UUID hash again */
> +        uint32_t hash_b = qemu_uuid_hash(&uuid);
> +        /*
> +         * Both hashes shall be different (avoid collision)
> +         * for any change in the UUID fields
> +         */
> +        g_assert_cmpint(hash_a, !=, hash_b);
> +    }
> +}
> +
>  int main(int argc, char **argv)
>  {
>      g_test_init(&argc, &argv, NULL);
> @@ -179,6 +205,7 @@ int main(int argc, char **argv)
>      g_test_add_func("/uuid/parse", test_uuid_parse);
>      g_test_add_func("/uuid/unparse", test_uuid_unparse);
>      g_test_add_func("/uuid/unparse_strdup", test_uuid_unparse_strdup);
> +    g_test_add_func("/uuid/hash", test_uuid_hash);
>  
>      return g_test_run();
>  }
> diff --git a/util/uuid.c b/util/uuid.c
> index b1108dde78..b366961bc6 100644
> --- a/util/uuid.c
> +++ b/util/uuid.c
> @@ -116,3 +116,18 @@ QemuUUID qemu_uuid_bswap(QemuUUID uuid)
>      bswap16s(&uuid.fields.time_high_and_version);
>      return uuid;
>  }
> +
> +/* djb2 hash algorithm */
> +uint32_t qemu_uuid_hash(const void *uuid)
> +{
> +    QemuUUID *qid = (QemuUUID *) uuid;
> +    uint32_t h = 5381;
> +    int i;
> +
> +    for (i = 0; i < ARRAY_SIZE(qid->data); i++) {
> +        h = (h << 5) + h + qid->data[i];
> +    }
> +
> +    return h;
> +}
> +

whitespace error:

.git/rebase-apply/patch:85: new blank line at EOF.
+
warning: 1 line adds whitespace errors.




> -- 
> 2.41.0
Albert Esteve Oct. 2, 2023, 6:43 a.m. UTC | #2 
On Sun, Oct 1, 2023 at 10:15 PM Michael S. Tsirkin <mst@redhat.com> wrote:

> On Fri, Sep 08, 2023 at 05:47:40PM +0200, Albert Esteve wrote:
> > Add hash function to uuid module using the
> > djb2 hash algorithm.
> >
> > Add a couple simple unit tests for the hash
> > function, checking collisions for similar UUIDs.
> >
> > Reviewed-by: Philippe Mathieu-Daudé <philmd@linaro.org>
> > Signed-off-by: Albert Esteve <aesteve@redhat.com>
> > ---
> >  include/qemu/uuid.h    |  2 ++
> >  tests/unit/test-uuid.c | 27 +++++++++++++++++++++++++++
> >  util/uuid.c            | 15 +++++++++++++++
> >  3 files changed, 44 insertions(+)
> >
> > diff --git a/include/qemu/uuid.h b/include/qemu/uuid.h
> > index dc40ee1fc9..e24a1099e4 100644
> > --- a/include/qemu/uuid.h
> > +++ b/include/qemu/uuid.h
> > @@ -96,4 +96,6 @@ int qemu_uuid_parse(const char *str, QemuUUID *uuid);
> >
> >  QemuUUID qemu_uuid_bswap(QemuUUID uuid);
> >
> > +uint32_t qemu_uuid_hash(const void *uuid);
> > +
> >  #endif
> > diff --git a/tests/unit/test-uuid.c b/tests/unit/test-uuid.c
> > index c111de5fc1..aedc125ae9 100644
> > --- a/tests/unit/test-uuid.c
> > +++ b/tests/unit/test-uuid.c
> > @@ -171,6 +171,32 @@ static void test_uuid_unparse_strdup(void)
> >      }
> >  }
> >
> > +static void test_uuid_hash(void)
> > +{
> > +    QemuUUID uuid;
> > +    int i;
> > +
> > +    for (i = 0; i < 100; i++) {
> > +        qemu_uuid_generate(&uuid);
> > +        /* Obtain the UUID hash */
> > +        uint32_t hash_a = qemu_uuid_hash(&uuid);
> > +        int data_idx = g_random_int_range(0, 15);
> > +        /* Change a single random byte of the UUID */
> > +        if (uuid.data[data_idx] < 0xFF) {
> > +            uuid.data[data_idx]++;
> > +        } else {
> > +            uuid.data[data_idx]--;
> > +        }
> > +        /* Obtain the UUID hash again */
> > +        uint32_t hash_b = qemu_uuid_hash(&uuid);
> > +        /*
> > +         * Both hashes shall be different (avoid collision)
> > +         * for any change in the UUID fields
> > +         */
> > +        g_assert_cmpint(hash_a, !=, hash_b);
> > +    }
> > +}
> > +
> >  int main(int argc, char **argv)
> >  {
> >      g_test_init(&argc, &argv, NULL);
> > @@ -179,6 +205,7 @@ int main(int argc, char **argv)
> >      g_test_add_func("/uuid/parse", test_uuid_parse);
> >      g_test_add_func("/uuid/unparse", test_uuid_unparse);
> >      g_test_add_func("/uuid/unparse_strdup", test_uuid_unparse_strdup);
> > +    g_test_add_func("/uuid/hash", test_uuid_hash);
> >
> >      return g_test_run();
> >  }
> > diff --git a/util/uuid.c b/util/uuid.c
> > index b1108dde78..b366961bc6 100644
> > --- a/util/uuid.c
> > +++ b/util/uuid.c
> > @@ -116,3 +116,18 @@ QemuUUID qemu_uuid_bswap(QemuUUID uuid)
> >      bswap16s(&uuid.fields.time_high_and_version);
> >      return uuid;
> >  }
> > +
> > +/* djb2 hash algorithm */
> > +uint32_t qemu_uuid_hash(const void *uuid)
> > +{
> > +    QemuUUID *qid = (QemuUUID *) uuid;
> > +    uint32_t h = 5381;
> > +    int i;
> > +
> > +    for (i = 0; i < ARRAY_SIZE(qid->data); i++) {
> > +        h = (h << 5) + h + qid->data[i];
> > +    }
> > +
> > +    return h;
> > +}
> > +
>
> whitespace error:
>
> .git/rebase-apply/patch:85: new blank line at EOF.
> +
> warning: 1 line adds whitespace errors.
>

Ok, I will send a new revision.


>
>
>
>
> > --
> > 2.41.0
>
>
diff mbox series

Patch

diff --git a/include/qemu/uuid.h b/include/qemu/uuid.h
index dc40ee1fc9..e24a1099e4 100644
--- a/include/qemu/uuid.h
+++ b/include/qemu/uuid.h
@@ -96,4 +96,6 @@  int qemu_uuid_parse(const char *str, QemuUUID *uuid);
 
 QemuUUID qemu_uuid_bswap(QemuUUID uuid);
 
+uint32_t qemu_uuid_hash(const void *uuid);
+
 #endif
diff --git a/tests/unit/test-uuid.c b/tests/unit/test-uuid.c
index c111de5fc1..aedc125ae9 100644
--- a/tests/unit/test-uuid.c
+++ b/tests/unit/test-uuid.c
@@ -171,6 +171,32 @@  static void test_uuid_unparse_strdup(void)
     }
 }
 
+static void test_uuid_hash(void)
+{
+    QemuUUID uuid;
+    int i;
+
+    for (i = 0; i < 100; i++) {
+        qemu_uuid_generate(&uuid);
+        /* Obtain the UUID hash */
+        uint32_t hash_a = qemu_uuid_hash(&uuid);
+        int data_idx = g_random_int_range(0, 15);
+        /* Change a single random byte of the UUID */
+        if (uuid.data[data_idx] < 0xFF) {
+            uuid.data[data_idx]++;
+        } else {
+            uuid.data[data_idx]--;
+        }
+        /* Obtain the UUID hash again */
+        uint32_t hash_b = qemu_uuid_hash(&uuid);
+        /*
+         * Both hashes shall be different (avoid collision)
+         * for any change in the UUID fields
+         */
+        g_assert_cmpint(hash_a, !=, hash_b);
+    }
+}
+
 int main(int argc, char **argv)
 {
     g_test_init(&argc, &argv, NULL);
@@ -179,6 +205,7 @@  int main(int argc, char **argv)
     g_test_add_func("/uuid/parse", test_uuid_parse);
     g_test_add_func("/uuid/unparse", test_uuid_unparse);
     g_test_add_func("/uuid/unparse_strdup", test_uuid_unparse_strdup);
+    g_test_add_func("/uuid/hash", test_uuid_hash);
 
     return g_test_run();
 }
diff --git a/util/uuid.c b/util/uuid.c
index b1108dde78..b366961bc6 100644
--- a/util/uuid.c
+++ b/util/uuid.c
@@ -116,3 +116,18 @@  QemuUUID qemu_uuid_bswap(QemuUUID uuid)
     bswap16s(&uuid.fields.time_high_and_version);
     return uuid;
 }
+
+/* djb2 hash algorithm */
+uint32_t qemu_uuid_hash(const void *uuid)
+{
+    QemuUUID *qid = (QemuUUID *) uuid;
+    uint32_t h = 5381;
+    int i;
+
+    for (i = 0; i < ARRAY_SIZE(qid->data); i++) {
+        h = (h << 5) + h + qid->data[i];
+    }
+
+    return h;
+}
+