alloc: implement alloc_visualize().
[ccan] / ccan / crcsync / test / run.c
1 #include <ccan/crcsync/crcsync.h>
2 #include <ccan/crcsync/crcsync.c>
3 #include <ccan/tap/tap.h>
4 #include <stdlib.h>
5 #include <stdbool.h>
6 #include <string.h>
7
8 /* FIXME: ccanize. */
9 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
10
11 struct result {
12         enum {
13                 LITERAL, BLOCK
14         } type;
15         /* Block number, or length of literal. */
16         size_t val;
17 };
18
19 static inline size_t num_blocks(size_t len, size_t block_size)
20 {
21         return (len + block_size - 1) / block_size;
22 }
23
24 static void check_finalized_result(size_t curr_literal,
25                                    const struct result results[],
26                                    size_t num_results,
27                                    size_t *curr_result)
28 {
29         if (curr_literal == 0)
30                 return;
31         ok1(*curr_result < num_results);
32         ok1(results[*curr_result].type == LITERAL);
33         ok1(results[*curr_result].val == curr_literal);
34         (*curr_result)++;
35 }
36
37 static void check_result(long result,
38                          size_t *curr_literal,
39                          const struct result results[], size_t num_results,
40                          size_t *curr_result)
41 {
42         /* We append multiple literals into one. */
43         if (result >= 0) {
44                 *curr_literal += result;
45                 return;
46         }
47
48         /* Check outstanding literals. */
49         if (*curr_literal) {
50                 check_finalized_result(*curr_literal, results, num_results,
51                                        curr_result);
52                 *curr_literal = 0;
53         }
54
55         ok1(*curr_result < num_results);
56         ok1(results[*curr_result].type == BLOCK);
57         ok1(results[*curr_result].val == -result - 1);
58         (*curr_result)++;
59 }
60
61 /* Start with buffer1 and sync to buffer2. */
62 static void test_sync(const char *buffer1, size_t len1,
63                       const char *buffer2, size_t len2,
64                       size_t block_size,
65                       const struct result results[], size_t num_results)
66 {
67         struct crc_context *ctx;
68         size_t used, ret, i, curr_literal, tailsize;
69         long result;
70         uint64_t crcs[num_blocks(len1, block_size)];
71
72         crc_of_blocks(buffer1, len1, block_size, 64, crcs);
73
74         tailsize = len1 % block_size;
75
76         /* Normal method. */
77         ctx = crc_context_new(block_size, 64, crcs, ARRAY_SIZE(crcs),
78                               tailsize);
79
80         curr_literal = 0;
81         for (used = 0, i = 0; used < len2; used += ret) {
82                 ret = crc_read_block(ctx, &result, buffer2+used, len2-used);
83                 check_result(result, &curr_literal, results, num_results, &i);
84         }
85
86         while ((result = crc_read_flush(ctx)) != 0)
87                 check_result(result, &curr_literal, results, num_results, &i);
88
89         check_finalized_result(curr_literal, results, num_results, &i);
90         
91         /* We must have achieved everything we expected. */
92         ok1(i == num_results);
93         crc_context_free(ctx);
94
95         /* Byte-at-a-time method. */
96         ctx = crc_context_new(block_size, 64, crcs, ARRAY_SIZE(crcs),
97                               tailsize);
98
99         curr_literal = 0;
100         for (used = 0, i = 0; used < len2; used += ret) {
101                 ret = crc_read_block(ctx, &result, buffer2+used, 1);
102
103                 check_result(result, &curr_literal, results, num_results, &i);
104         }
105
106         while ((result = crc_read_flush(ctx)) != 0)
107                 check_result(result, &curr_literal, results, num_results, &i);
108
109         check_finalized_result(curr_literal, results, num_results, &i);
110         
111         /* We must have achieved everything we expected. */
112         ok1(i == num_results);
113         crc_context_free(ctx);
114 }
115
116 #define BUFFER_SIZE 512
117 #define BLOCK_SIZE 128
118 #define NUM_BLOCKS (BUFFER_SIZE / BLOCK_SIZE)
119
120 int main(int argc, char *argv[])
121 {
122         char *buffer1, *buffer2;
123         unsigned int i;
124         uint64_t crcs1[NUM_BLOCKS], crcs2[NUM_BLOCKS];
125
126         plan_tests(664);
127
128         buffer1 = calloc(BUFFER_SIZE, 1);
129         buffer2 = calloc(BUFFER_SIZE, 1);
130
131         /* Truncated end block test. */
132         crcs1[ARRAY_SIZE(crcs1)-1] = 0xdeadbeef;
133         crc_of_blocks(buffer1, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 64, crcs1);
134         ok1(crcs1[ARRAY_SIZE(crcs1)-1] == 0xdeadbeef);
135         crc_of_blocks(buffer2, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 64, crcs2);
136         ok1(memcmp(crcs1, crcs2, sizeof(crcs1[0])*(ARRAY_SIZE(crcs1)-1)) == 0);
137
138         /* Fill with non-zero pattern, retest. */
139         for (i = 0; i < BUFFER_SIZE; i++)
140                 buffer1[i] = buffer2[i] = i + i/BLOCK_SIZE;
141
142         crcs1[ARRAY_SIZE(crcs1)-1] = 0xdeadbeef;
143         crc_of_blocks(buffer1, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 64, crcs1);
144         ok1(crcs1[ARRAY_SIZE(crcs1)-1] == 0xdeadbeef);
145         crc_of_blocks(buffer2, BUFFER_SIZE-BLOCK_SIZE-1, BLOCK_SIZE, 64, crcs2);
146         ok1(memcmp(crcs1, crcs2, sizeof(crcs1[0])*(ARRAY_SIZE(crcs1)-1)) == 0);
147
148         /* Check that it correctly masks bits. */
149         crc_of_blocks(buffer1, BUFFER_SIZE, BLOCK_SIZE, 64, crcs1);
150         crc_of_blocks(buffer2, BUFFER_SIZE, BLOCK_SIZE, 8, crcs2);
151         for (i = 0; i < NUM_BLOCKS; i++)
152                 ok1(crcs2[i] == (crcs1[i] & 0xFF00000000000000ULL));
153
154         /* Now test the "exact match" "round blocks" case. */
155         {
156                 struct result res[NUM_BLOCKS];
157
158                 for (i = 0; i < ARRAY_SIZE(res); i++) {
159                         res[i].type = BLOCK;
160                         res[i].val = i;
161                 }
162                 test_sync(buffer1, BUFFER_SIZE, buffer2,
163                           BUFFER_SIZE, BLOCK_SIZE,
164                           res, ARRAY_SIZE(res));
165         }
166
167         /* Now test the "exact match" with end block case. */
168         {
169                 struct result res[NUM_BLOCKS+1];
170                 for (i = 0; i < ARRAY_SIZE(res); i++) {
171                         res[i].type = BLOCK;
172                         res[i].val = i;
173                 }
174                 test_sync(buffer1, BUFFER_SIZE, buffer2,
175                           BUFFER_SIZE, BLOCK_SIZE-1,
176                           res, ARRAY_SIZE(res));
177         }
178
179         /* Now test the "one byte append" "round blocks" case. */
180         {
181                 struct result res[NUM_BLOCKS];
182                 for (i = 0; i < ARRAY_SIZE(res)-1; i++) {
183                         res[i].type = BLOCK;
184                         res[i].val = i;
185                 }
186                 res[i].type = LITERAL;
187                 res[i].val = 1;
188
189                 test_sync(buffer1, BUFFER_SIZE-BLOCK_SIZE,
190                           buffer2, BUFFER_SIZE-BLOCK_SIZE+1, BLOCK_SIZE,
191                           res, ARRAY_SIZE(res));
192         }
193
194         /* Now test the "one byte append" with end block case. */
195         {
196                 struct result res[NUM_BLOCKS+2];
197                 for (i = 0; i < ARRAY_SIZE(res)-1; i++) {
198                         res[i].type = BLOCK;
199                         res[i].val = i;
200                 }
201                 res[i].type = LITERAL;
202                 res[i].val = 1;
203
204                 test_sync(buffer1, BUFFER_SIZE-1,
205                           buffer2, BUFFER_SIZE,
206                           BLOCK_SIZE - 1, res, ARRAY_SIZE(res));
207         }
208
209         /* Now try changing one block at a time, check we get right results. */
210         for (i = 0; i < NUM_BLOCKS; i++) {
211                 unsigned int j;
212                 struct result res[NUM_BLOCKS];
213
214                 /* Mess with block. */
215                 memcpy(buffer2, buffer1, BUFFER_SIZE);
216                 buffer2[i * BLOCK_SIZE]++;
217
218                 for (j = 0; j < ARRAY_SIZE(res); j++) {
219                         if (j == i) {
220                                 res[j].type = LITERAL;
221                                 res[j].val = BLOCK_SIZE;
222                         } else {
223                                 res[j].type = BLOCK;
224                                 res[j].val = j;
225                         }
226                 }
227
228                 test_sync(buffer1, BUFFER_SIZE,
229                           buffer2, BUFFER_SIZE,
230                           BLOCK_SIZE, res, ARRAY_SIZE(res));
231         }
232
233         /* Now try shrinking one block at a time, check we get right results. */
234         for (i = 0; i < NUM_BLOCKS; i++) {
235                 unsigned int j;
236                 struct result res[NUM_BLOCKS];
237
238                 /* Shrink block. */
239                 memcpy(buffer2, buffer1, i * BLOCK_SIZE + BLOCK_SIZE/2);
240                 memcpy(buffer2 + i * BLOCK_SIZE + BLOCK_SIZE/2,
241                        buffer1 + i * BLOCK_SIZE + BLOCK_SIZE/2 + 1,
242                        BUFFER_SIZE - (i * BLOCK_SIZE + BLOCK_SIZE/2 + 1));
243
244                 for (j = 0; j < ARRAY_SIZE(res); j++) {
245                         if (j == i) {
246                                 res[j].type = LITERAL;
247                                 res[j].val = BLOCK_SIZE-1;
248                         } else {
249                                 res[j].type = BLOCK;
250                                 res[j].val = j;
251                         }
252                 }
253
254                 test_sync(buffer1, BUFFER_SIZE,
255                           buffer2, BUFFER_SIZE-1,
256                           BLOCK_SIZE, res, ARRAY_SIZE(res));
257         }
258
259         /* Finally, all possible combinations. */
260         for (i = 0; i < (1 << NUM_BLOCKS); i++) {
261                 unsigned int j, num_res;
262                 struct result res[NUM_BLOCKS];
263
264                 memcpy(buffer2, buffer1, BUFFER_SIZE);
265                 for (j = num_res = 0; j < ARRAY_SIZE(res); j++) {
266                         if (i & (i << j)) {
267                                 res[num_res].type = BLOCK;
268                                 res[num_res].val = j;
269                                 num_res++;
270                         } else {
271                                 /* Mess with block. */
272                                 buffer2[j * BLOCK_SIZE]++;
273                                 if (num_res && res[num_res-1].type == LITERAL)
274                                         res[num_res-1].val += BLOCK_SIZE;
275                                 else {
276                                         res[num_res].type = LITERAL;
277                                         res[num_res].val = BLOCK_SIZE;
278                                         num_res++;
279                                 }
280                         }
281                 }
282
283                 test_sync(buffer1, BUFFER_SIZE,
284                           buffer2, BUFFER_SIZE,
285                           BLOCK_SIZE, res, num_res);
286         }
287
288         return exit_status();
289 }