On Sun, Oct 1, 2023 at 10:15 PM Michael S. Tsirkin <m...@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é <phi...@linaro.org>
> > Signed-off-by: Albert Esteve <aest...@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
>
>
