sync

test_sync_ibf.c (6976B)

---

 /*
   This file is part of TALER
   Copyright (C) 2026 Taler Systems SA
 
   TALER is free software; you can redistribute it and/or modify it under the
   terms of the GNU General Public License as published by the Free Software
   Foundation; either version 3, or (at your option) any later version.
 
   TALER is distributed in the hope that it will be useful, but WITHOUT ANY
   WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
   A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
 
   You should have received a copy of the GNU General Public License along with
   TALER; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
 */
 /**
  * @file util/test_sync_ibf.c
  * @brief tests for the sync invertible bloom filter (DD 92)
  * @author Iván Ávalos
  */
 #include "platform.h"
 #include <gnunet/gnunet_util_lib.h>
 #include "sync/sync_ibf.h"
 
 
 #define FAILIF(cond)                            \
         do {                                          \
           if (! (cond)) break;                        \
           GNUNET_break (0);                           \
           return 1;                                   \
         } while (0)
 
 
 /**
  * Deterministic element: nonce and hash filled with distinct bytes
  * derived from @a i.
  *
  * @param i element number
  * @param[out] key set to the element
  */
 static void
 key_of (unsigned int i,
         struct SYNC_IBFKey *key)
 {
   memset (key,
           i + 1,
           sizeof (*key));
   key->nonce[0] = (unsigned char) i;
   key->hash[0] = (unsigned char) (i >> 8);
 }
 
 
 /**
  * Insert and remove leave the filter empty again.
  *
  * @return 0 on success
  */
 static int
 test_insert_remove (void)
 {
   struct SYNC_IBF *ibf;
   struct SYNC_IBFKey key;
   size_t size;
   void *data;
 
   ibf = SYNC_ibf_create (SYNC_IBF_MIN_BUCKETS,
                          SYNC_IBF_HASH_NUM,
                          0);
   FAILIF (NULL == ibf);
   for (unsigned int i = 0; i < 100; i++)
   {
     key_of (i,
             &key);
     SYNC_ibf_insert (ibf,
                      &key);
   }
   for (unsigned int i = 0; i < 100; i++)
   {
     key_of (i,
             &key);
     SYNC_ibf_remove (ibf,
                      &key);
   }
   size = SYNC_ibf_get_serialized_size (ibf);
   data = GNUNET_malloc (size);
   SYNC_ibf_serialize (ibf,
                       data);
   for (size_t i = 0; i < size; i++)
     if (0 != ((const unsigned char *) data)[i])
     {
       GNUNET_break (0);
       GNUNET_free (data);
       SYNC_ibf_destroy (ibf);
       return 1;
     }
   GNUNET_free (data);
   SYNC_ibf_destroy (ibf);
   return 0;
 }
 
 
 /**
  * The symmetric difference of two filters decodes to exactly the
  * differing elements, with the correct side.
  *
  * Sets: A = {0..9} union {20..29}, B = {10..19} union {20..29}.
  * After subtracting B from A, the difference holds 0..9 with side +1
  * and 10..19 with side -1; 20..29 cancel out.
  *
  * @return 0 on success
  */
 static int
 test_decode_difference (void)
 {
   struct SYNC_IBF *ibf_a = SYNC_ibf_create (SYNC_IBF_MIN_BUCKETS,
                                             SYNC_IBF_HASH_NUM,
                                             0);
   struct SYNC_IBF *ibf_b = SYNC_ibf_create (SYNC_IBF_MIN_BUCKETS,
                                             SYNC_IBF_HASH_NUM,
                                             0);
   struct SYNC_IBFKey key;
 
   FAILIF ( (NULL == ibf_a) ||
            (NULL == ibf_b) );
   for (unsigned int i = 0; i < 30; i++)
   {
     key_of (i,
             &key);
     if ( (i < 10) ||
          (i >= 20) )
       SYNC_ibf_insert (ibf_a,
                        &key);
     if ( (i >= 10) )
       SYNC_ibf_insert (ibf_b,
                        &key);
   }
 
   SYNC_ibf_subtract (ibf_a,
                      ibf_b);
   {
     bool have[30] = { false };
     int16_t side[30] = { 0 };
 
     for (;;)
     {
       enum GNUNET_GenericReturnValue res;
       int16_t got_side;
       struct SYNC_IBFKey got_key;
 
       res = SYNC_ibf_decode (ibf_a,
                              &got_side,
                              &got_key);
       if (GNUNET_YES != res)
       {
         FAILIF (GNUNET_NO != res);
         break;
       }
       {
         const unsigned int i = (unsigned int) got_key.nonce[0];
 
         FAILIF (i >= 30);
         FAILIF ((got_side != 1) && (got_side != -1));
         FAILIF (have[i]);
         have[i] = true;
         side[i] = got_side;
       }
     }
     for (unsigned int i = 0; i < 30; i++)
     {
       if (i < 10)
         FAILIF (! have[i] || (1 != side[i]));
       else if (i < 20)
         FAILIF (! have[i] || (-1 != side[i]));
       else
         FAILIF (have[i]);
     }
   }
   SYNC_ibf_destroy (ibf_b);
   SYNC_ibf_destroy (ibf_a);
   return 0;
 }
 
 
 /**
  * The serialized form round-trips, and mismatching parameters are
  * rejected.
  *
  * @return 0 on success
  */
 static int
 test_serialize (void)
 {
   struct SYNC_IBF *ibf;
   struct SYNC_IBF *ibf2;
   struct SYNC_IBFKey key;
   struct SYNC_IBFKey got_key;
   size_t size;
   void *data;
 
   ibf = SYNC_ibf_create (SYNC_IBF_MIN_BUCKETS,
                          SYNC_IBF_HASH_NUM,
                          42);
   FAILIF (NULL == ibf);
   for (unsigned int i = 0; i < 20; i++)
   {
     key_of (i,
             &key);
     SYNC_ibf_insert (ibf,
                      &key);
   }
   size = SYNC_ibf_get_serialized_size (ibf);
   FAILIF (size != ((size_t) SYNC_IBF_MIN_BUCKETS) * SYNC_IBF_BUCKET_SIZE);
   data = GNUNET_malloc (size);
   SYNC_ibf_serialize (ibf,
                       data);
   ibf2 = SYNC_ibf_deserialize (data,
                                SYNC_IBF_MIN_BUCKETS,
                                SYNC_IBF_HASH_NUM,
                                42);
   FAILIF (NULL == ibf2);
   FAILIF (NULL !=
           SYNC_ibf_deserialize (data,
                                 0,
                                 SYNC_IBF_HASH_NUM,
                                 42));
   {
     int16_t side;
     unsigned int got = 0;
 
     for (;;)
     {
       enum GNUNET_GenericReturnValue res;
 
       res = SYNC_ibf_decode (ibf2,
                              &side,
                              &got_key);
       if (GNUNET_YES != res)
       {
         FAILIF (GNUNET_NO != res);
         break;
       }
       got++;
     }
     FAILIF (got != 20);
   }
   SYNC_ibf_destroy (ibf2);
   GNUNET_free (data);
   SYNC_ibf_destroy (ibf);
   return 0;
 }
 
 
 /**
  * Bucket counts are powers of two within the bounds.
  *
  * @return 0 on success
  */
 static int
 test_compute_bucket_count (void)
 {
   FAILIF (SYNC_ibf_compute_bucket_count (0) != SYNC_IBF_MIN_BUCKETS);
   FAILIF (SYNC_ibf_compute_bucket_count (1) != SYNC_IBF_MIN_BUCKETS);
   FAILIF (SYNC_ibf_compute_bucket_count (1000) != 1024);
   FAILIF (SYNC_ibf_compute_bucket_count (100000) != SYNC_IBF_MAX_BUCKETS);
   return 0;
 }
 
 
 int
 main (int argc,
       char **argv)
 {
   (void) argc;
   (void) argv;
   FAILIF (0 != test_insert_remove ());
   FAILIF (0 != test_decode_difference ());
   FAILIF (0 != test_serialize ());
   FAILIF (0 != test_compute_bucket_count ());
   return 0;
 }
 
 
 /* end of test_sync_ibf.c */