git.ozlabs.org Git - ccan/blob - ccan/bdelta/test/common.h

   1 #include <ccan/bdelta/bdelta.h>
   2 #include <ccan/bdelta/bdelta.c>
   3 #include <ccan/tap/tap.h>
   4
   5 #include <stdint.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8
   9 /*
  10  * Finds a pseudorandom 32-bit number from 0 to 2^32-1 .
  11  * Uses the BCPL linear congruential generator method.
  12  *
  13  * Used instead of system RNG to ensure tests are consistent.
  14  */
  15 static uint32_t rand32(void)
  16 {
  17 #if 0
  18         /*
  19          * Tests should be run with a different random function
  20          * from time to time.  I've found that the method below
  21          * sometimes behaves poorly for testing purposes.
  22          * For example, rand32() % N might only return even numbers.
  23          */
  24         assert(RAND_MAX == 2147483647);
  25         return ((random() & 0xFFFF) << 16) | (random() & 0xFFFF);
  26 #else
  27         static uint32_t rand32_state = 0;
  28         rand32_state *= (uint32_t)0x7FF8A3ED;
  29         rand32_state += (uint32_t)0x2AA01D31;
  30         return rand32_state;
  31 #endif
  32 }
  33
  34 #define RSTRING_OK                0  /* Operation succeeded */
  35 #define RSTRING_MEMORY            1  /* Memory allocation failed */
  36 #define RSTRING_ZERO_CARDINALITY  2  /* Cardinality of byte range is zero */
  37 #define RSTRING_RANGE_OVERLAP     3  /* Byte range contains overlapping characters */
  38
  39 struct rstring_byte_range {
  40         unsigned int cardinality;
  41         unsigned int multiplier;
  42         unsigned int offset;
  43 };
  44
  45 static int check_range(const struct rstring_byte_range *range)
  46 {
  47         unsigned int i;
  48         unsigned int c;
  49         char set[256];
  50
  51         if (range == NULL)
  52                 return RSTRING_OK;
  53
  54         if (range->cardinality == 0)
  55                 return RSTRING_ZERO_CARDINALITY;
  56
  57         memset(set, 0, sizeof(set));
  58
  59         c = range->offset & 0xFF;
  60         for (i = 0; i < range->cardinality; i++) {
  61                 if (set[c])
  62                         return RSTRING_RANGE_OVERLAP;
  63                 set[c] = 1;
  64                 c += range->multiplier;
  65                 c &= 0xFF;
  66         }
  67
  68         return RSTRING_OK;
  69 }
  70
  71 /*
  72  * Generate a pseudorandom string of the given length,
  73  * writing it into a user-supplied buffer.
  74  */
  75 static uint8_t *random_string_into(uint8_t *str, uint32_t size, const struct rstring_byte_range *range)
  76 {
  77         uint32_t i;
  78         uint32_t r;
  79
  80         if (range == NULL) {
  81                 for (i = 0; size - i >= 4; ) {
  82                         r = rand32();
  83                         str[i++] = r & 0xFF;
  84                         r >>= 8;
  85                         str[i++] = r & 0xFF;
  86                         r >>= 8;
  87                         str[i++] = r & 0xFF;
  88                         r >>= 8;
  89                         str[i++] = r & 0xFF;
  90                 }
  91
  92                 if (i < size) {
  93                         r = rand32();
  94                         do {
  95                                 str[i++] = r & 0xFF;
  96                                 r >>= 8;
  97                         } while (i < size);
  98                 }
  99         } else {
 100                 for (i = 0; i < size; )
 101                         str[i++] = ((rand32() % range->cardinality) * range->multiplier + range->offset) & 0xFF;
 102         }
 103
 104         return str;
 105 }
 106
 107 /*
 108  * Generate a pseudorandom string of the given length.
 109  */
 110 static uint8_t *random_string(uint32_t size, const struct rstring_byte_range *range)
 111 {
 112         uint8_t *str;
 113
 114         if (check_range(range) != RSTRING_OK) {
 115                 fprintf(stderr, "Invalid byte range for random string generation\n");
 116                 exit(EXIT_FAILURE);
 117         }
 118
 119         str = malloc(size);
 120         if (str == NULL)
 121                 return NULL;
 122
 123         return random_string_into(str, size, range);
 124 }
 125
 126 /*
 127  * Generate two byte strings:
 128  *
 129  *  An "old" string, of length @old_size
 130  *  A "new" string, differing from "old" by at most @diff_size bytes
 131  *  (where modifying a character is considered one change).
 132  *
 133  * Returns RSTRING_OK on success, RSTRING_MEMORY if memory allocation fails.
 134  */
 135 static int random_string_pair(
 136         uint32_t old_size, uint32_t diff_size, const struct rstring_byte_range *range,
 137         uint8_t **old_out, uint8_t **new_out, uint32_t *new_size_out)
 138 {
 139         uint8_t *old;
 140         uint8_t *new_;
 141         uint8_t *nptr;
 142         uint32_t new_size;
 143         uint32_t i;
 144         uint32_t j;
 145
 146         /* insertions[i] is the number of characters to insert before position i. */
 147         uint32_t *insertions;
 148
 149         /*
 150          * changes[i] indicates what to do to the character at position i:
 151          *
 152          *  0: Leave it as-is.
 153          *  1: Delete it.
 154          *  2: Change it to another byte (possibly the same byte).
 155          */
 156         char *changes;
 157
 158         /* String of new bytes to use for insertions and changes. */
 159         uint8_t *new_bytes;
 160         uint8_t *new_bytes_ptr;
 161         uint32_t new_bytes_size;
 162
 163         old = random_string(old_size, range);
 164         if (old == NULL)
 165                 goto oom0;
 166
 167         insertions = calloc(old_size + 1, sizeof(*insertions));
 168         if (insertions == NULL)
 169                 goto oom1;
 170
 171         changes = calloc(old_size, sizeof(*changes));
 172         if (changes == NULL)
 173                 goto oom2;
 174
 175         /*
 176          * Generate a collection of edits, which will be
 177          * applied to the old string "simultaneously".
 178          */
 179         new_size = old_size;
 180         new_bytes_size = 0;
 181         for (i = 0; i < diff_size; i++) {
 182                 uint32_t pos;
 183
 184                 switch (rand32() % 3) {
 185                         case 0: /* Insert a byte. */
 186                                 pos = rand32() % (old_size + 1);
 187                                 insertions[pos]++;
 188                                 new_size++;
 189                                 new_bytes_size++;
 190                                 break;
 191
 192                         case 1: /* Delete a byte. */
 193                                 pos = rand32() % old_size;
 194                                 if (changes[pos]) {
 195                                         /*
 196                                          * This character is already deleted or changed.
 197                                          * Do something else instead.
 198                                          *
 199                                          * For the observative: i will overflow if it's 0.
 200                                          * However, overflow of unsigned integers is well-defined
 201                                          * by the C standard.  i will wrap around to UINT32_MAX,
 202                                          * then the for-loop increment above will wrap it back to 0.
 203                                          */
 204                                         i--;
 205                                 } else {
 206                                         changes[pos] = 1;
 207                                         new_size--;
 208                                 }
 209                                 break;
 210
 211                         default: /* Change a byte. */
 212                                 pos = rand32() % old_size;
 213                                 if (changes[pos]) {
 214                                         /*
 215                                          * This character is already deleted or changed.
 216                                          * Do something else instead.
 217                                          */
 218                                         i--;
 219                                 } else {
 220                                         changes[pos] = 2;
 221                                         new_bytes_size++;
 222                                 }
 223                                 break;
 224                 }
 225         }
 226
 227         new_bytes = malloc(new_bytes_size);
 228         if (new_bytes == NULL)
 229                 goto oom3;
 230         random_string_into(new_bytes, new_bytes_size, range);
 231
 232         new_ = malloc(new_size);
 233         if (new_ == NULL)
 234                 goto oom4;
 235
 236         /* Apply the insertions and changes generated above. */
 237         nptr = new_;
 238         new_bytes_ptr = new_bytes;
 239         for (i = 0; i < old_size; i++) {
 240                 for (j = 0; j < insertions[i]; j++)
 241                         *nptr++ = *new_bytes_ptr++;
 242
 243                 switch (changes[i]) {
 244                         case 0: /* No change */
 245                                 *nptr++ = old[i];
 246                                 break;
 247
 248                         case 1: /* Delete */
 249                                 break;
 250
 251                         default: /* Change value */
 252                                 *nptr++ = *new_bytes_ptr++;
 253                                 break;
 254                 }
 255         }
 256         for (j = 0; j < insertions[i]; j++)
 257                 *nptr++ = *new_bytes_ptr++;
 258         assert((size_t)(nptr - new_) == new_size);
 259         assert((size_t)(new_bytes_ptr - new_bytes) == new_bytes_size);
 260
 261         free(new_bytes);
 262         free(changes);
 263         free(insertions);
 264
 265         if (old_out)
 266                 *old_out = old;
 267         else
 268                 free(old);
 269         if (new_out)
 270                 *new_out = new_;
 271         else
 272                 free(new_);
 273         if (new_size_out)
 274                 *new_size_out = new_size;
 275
 276         return RSTRING_OK;
 277
 278 oom4:
 279         free(new_bytes);
 280 oom3:
 281         free(changes);
 282 oom2:
 283         free(insertions);
 284 oom1:
 285         free(old);
 286 oom0:
 287         if (old_out)
 288                 *old_out = NULL;
 289         if (new_out)
 290                 *new_out = NULL;
 291         if (new_size_out)
 292                 *new_size_out = 0;
 293         return RSTRING_MEMORY;
 294 }