bdelta: new module for binary diff/patch
[ccan] / 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 }