1 /*
2 * Copyright © 2019 Manuel Stoeckl
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
11 *
12 * The above copyright notice and this permission notice (including the
13 * next paragraph) shall be included in all copies or substantial
14 * portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
19 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
20 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
21 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 * SOFTWARE.
24 */
25
26 #include "common.h"
27 #include "shadow.h"
28
29 #include <stdio.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <time.h>
33
fill_overcopy_pattern(int Ntotal,int margin,struct ext_interval * data)34 static void fill_overcopy_pattern(
35 int Ntotal, int margin, struct ext_interval *data)
36 {
37 int stride = 100 + margin + 1;
38 for (int i = 0; i < Ntotal; i++) {
39 data[i] = (struct ext_interval){
40 .start = (i) % (Ntotal / 2) * stride,
41 .width = 100 - (i > Ntotal / 2),
42 .rep = 100,
43 .stride = stride,
44 };
45 }
46 }
47
fill_line_crossing_pattern(int Ntotal,int margin,struct ext_interval * data)48 static void fill_line_crossing_pattern(
49 int Ntotal, int margin, struct ext_interval *data)
50 {
51 int step = (margin + 1);
52 int boxsize = ceildiv(Ntotal, 2) * step;
53 for (int i = 0; i < Ntotal; i++) {
54 if (i % 2 == 0) {
55 data[i] = (struct ext_interval){
56 .start = (i / 2) * step,
57 .width = 1,
58 .rep = boxsize,
59 .stride = boxsize,
60 };
61 } else {
62 data[i] = (struct ext_interval){
63 .start = (i / 2) * boxsize,
64 .width = boxsize,
65 .rep = 1,
66 .stride = 0,
67 };
68 }
69 }
70 }
71
fill_vline_pattern(int Ntotal,int margin,struct ext_interval * data)72 static void fill_vline_pattern(
73 int Ntotal, int margin, struct ext_interval *data)
74 {
75 int step = (margin + 2);
76 int stride = Ntotal * step;
77 for (int i = 0; i < Ntotal; i++) {
78 data[i] = (struct ext_interval){
79 .start = i * step,
80 .width = 1,
81 .rep = 2,
82 .stride = stride,
83 };
84 }
85 }
86
randint(int max)87 static int randint(int max)
88 {
89 int cap = RAND_MAX - RAND_MAX % max;
90 while (1) {
91 int x = rand();
92 if (x >= cap) {
93 continue;
94 }
95 return x % max;
96 }
97 }
98
fill_circle_pattern(int Ntotal,int margin,struct ext_interval * data)99 static void fill_circle_pattern(
100 int Ntotal, int margin, struct ext_interval *data)
101 {
102 srand((uint32_t)(Ntotal + 165 * margin));
103
104 int i = 0;
105 int R = (int)((2 * margin + Ntotal) * 0.3);
106 int s = (2 * margin + Ntotal) / 2;
107 while (i < Ntotal) {
108 int x = randint(2 * R);
109 int w = randint(2 * R - x) + 1;
110 int y = randint(2 * R);
111 int h = randint(2 * R - y) + 1;
112 int64_t x2a = (x - R) * (x - R);
113 int64_t x2b = (x + w - R) * (x + w - R);
114 int64_t x2 = x2a < x2b ? x2b : x2a;
115 int64_t y2a = (y - R) * (y - R);
116 int64_t y2b = (y + w - R) * (y + w - R);
117 int64_t y2 = y2a < y2b ? y2b : y2a;
118 if (x2 + y2 >= R * R) {
119 continue;
120 }
121
122 data[i++] = (struct ext_interval){
123 .start = s * y + x,
124 .width = w,
125 .rep = h,
126 .stride = s,
127 };
128 }
129 }
130
fill_snow_pattern(int Ntotal,int margin,struct ext_interval * data)131 static void fill_snow_pattern(int Ntotal, int margin, struct ext_interval *data)
132 {
133 srand((uint32_t)(Ntotal + 165 * margin));
134
135 int size = 4;
136 while (size * size < Ntotal * margin) {
137 size = size + size / 4;
138 }
139
140 for (int i = 0; i < Ntotal; i++) {
141 int x = randint(size);
142 int y = randint(size);
143 data[i] = (struct ext_interval){
144 .start = size * y + x,
145 .width = 1,
146 .rep = 1,
147 .stride = size,
148 };
149 }
150 }
151 struct pattern {
152 const char *name;
153 void (*func)(int Ntotal, int margin, struct ext_interval *data);
154 };
155 static const struct pattern patterns[] = {{"overcopy", fill_overcopy_pattern},
156 {"line-crossing", fill_line_crossing_pattern},
157 {"circle", fill_circle_pattern}, {"snow", fill_snow_pattern},
158 {"vline", fill_vline_pattern}, {NULL, NULL}};
159
eint_low(const struct ext_interval i)160 static inline int eint_low(const struct ext_interval i) { return i.start; }
eint_high(const struct ext_interval i)161 static inline int eint_high(const struct ext_interval i)
162 {
163 return i.start + (i.rep - 1) * i.stride + i.width;
164 }
165
write_eint(struct ext_interval e,char * buf,int minv,uint8_t value)166 static void write_eint(
167 struct ext_interval e, char *buf, int minv, uint8_t value)
168 {
169 for (int k = 0; k < e.rep; k++) {
170 memset(&buf[e.start + e.stride * k - minv], value,
171 (size_t)e.width);
172 }
173 }
174
175 /** Verify that:
176 * - the new set of intervals covers the old
177 * - the new set of intervals is disjoint within margin
178 */
check_solution_properties(int nsub,const struct ext_interval * sub,int nsup,const struct interval * sup,int margin)179 static bool check_solution_properties(int nsub, const struct ext_interval *sub,
180 int nsup, const struct interval *sup, int margin)
181 {
182 int minv = INT32_MAX, maxv = INT32_MIN;
183 for (int i = 0; i < nsup; i++) {
184 minv = min(minv, sup[i].start);
185 maxv = max(maxv, sup[i].end);
186 }
187 for (int i = 0; i < nsub; i++) {
188 minv = min(minv, eint_low(sub[i]));
189 maxv = max(maxv, eint_high(sub[i]));
190 }
191 if (minv > maxv) {
192 return true;
193 }
194 minv -= margin;
195 maxv += margin;
196 char *test = calloc((size_t)(maxv - minv), 1);
197 // Fast & stupid containment test
198 for (int i = 0; i < nsub; i++) {
199 write_eint(sub[i], test, minv, 1);
200 }
201 for (int i = 0; i < nsup; i++) {
202 struct interval e = sup[i];
203 if (memchr(&test[e.start - minv - margin], 2,
204 (size_t)(e.end - e.start + 2 * margin)) !=
205 NULL) {
206 printf("Internal overlap failure\n");
207 free(test);
208 return false;
209 }
210
211 memset(&test[e.start - minv], 2, (size_t)(e.end - e.start));
212 }
213 bool yes = memchr(test, 1, (size_t)(maxv - minv)) == NULL;
214 if (!yes) {
215 int count = 0;
216 for (int i = 0; i < maxv - minv; i++) {
217 count += test[i] == 1;
218 }
219 printf("Fail count: %d/%d\n", count, maxv - minv);
220 if (maxv - minv < 200) {
221 for (int i = 0; i < maxv - minv; i++) {
222 printf("%d", test[i]);
223 }
224 printf("\n");
225 }
226 }
227
228 free(test);
229 return yes;
230 }
231
convert_to_simple(struct interval * vec,int count,const struct ext_interval * ext)232 static int convert_to_simple(
233 struct interval *vec, int count, const struct ext_interval *ext)
234 {
235 int k = 0;
236 for (int i = 0; i < count; i++) {
237 for (int j = 0; j < ext[i].rep; j++) {
238 vec[k].start = ext[i].start + j * ext[i].stride;
239 vec[k].end = vec[k].start + ext[i].width;
240 k++;
241 }
242 }
243 return k;
244 }
simple_lexsort(const void * L,const void * R)245 static int simple_lexsort(const void *L, const void *R)
246 {
247 const struct interval *l = L;
248 const struct interval *r = R;
249 if (l->start != r->start) {
250 return l->start - r->start;
251 }
252 return l->end - r->end;
253 }
254
255 /** A merge operation which reduces the compound intervals to simple intervals,
256 * and then merges them that way. After all, this only expands memory use and
257 * runtime by a factor of screen height... */
258 static void __attribute__((noinline))
merge_simple(const int old_count,struct ext_interval * old_list,const int new_count,const struct ext_interval * const new_list,int * dst_count,struct interval ** dst_list,int merge_margin)259 merge_simple(const int old_count, struct ext_interval *old_list,
260 const int new_count, const struct ext_interval *const new_list,
261 int *dst_count, struct interval **dst_list, int merge_margin)
262 {
263 int nintervals = 0;
264 for (int i = 0; i < old_count; i++) {
265 nintervals += old_list[i].rep;
266 }
267 for (int i = 0; i < new_count; i++) {
268 nintervals += new_list[i].rep;
269 }
270 struct interval *vec =
271 malloc((size_t)nintervals * sizeof(struct interval));
272 int base = convert_to_simple(vec, old_count, old_list);
273 convert_to_simple(&vec[base], new_count, new_list);
274
275 // divide and conquer would be faster here
276 qsort(vec, (size_t)nintervals, sizeof(struct interval), simple_lexsort);
277
278 int r = 0, w = 0;
279 while (r < nintervals) {
280 // inside loop.
281 int end = vec[w].end;
282 r++; // the interval already contains itself
283
284 while (r < nintervals && vec[r].start < end + merge_margin) {
285 end = max(end, vec[r].end);
286 r++;
287 }
288 vec[w].end = end;
289 w++;
290 if (r < nintervals) {
291 vec[w] = vec[r];
292 }
293 }
294
295 *dst_list = vec;
296 *dst_count = w;
297 }
298
get_coverage(const int c,const struct interval * li)299 static int get_coverage(const int c, const struct interval *li)
300 {
301 int n = 0;
302 for (int i = 0; i < c; i++) {
303 n += li[i].end - li[i].start;
304 }
305 return n;
306 }
307
308 log_handler_func_t log_funcs[2] = {test_log_handler, test_log_handler};
main(int argc,char ** argv)309 int main(int argc, char **argv)
310 {
311 (void)argc;
312 (void)argv;
313 bool all_success = true;
314
315 srand(0);
316 // no larger, because e.g. test sizes are (margins*N)^2
317 int margins[] = {2, 11, 32, 1};
318 int nvec[] = {1000, 50, 10, 30};
319
320 for (int z = 0; z < (int)(sizeof(nvec) / sizeof(nvec[0])); z++) {
321 for (int ip = 0; patterns[ip].name; ip++) {
322 /* Pattern tests: we generate a given pattern of damage
323 * rectangles, apply the merge function, and verify that
324 * all the desired result properties hold */
325 struct ext_interval *data = calloc((size_t)nvec[z],
326 sizeof(struct ext_interval));
327
328 printf("\n---- pattern=%s, N=%d, margin=%d\n",
329 patterns[ip].name, nvec[z], margins[z]);
330
331 (*patterns[ip].func)(nvec[z], margins[z], data);
332
333 // check that minv >= 0, maxv is <= 1GB
334 int64_t minv = 0, maxv = 0;
335 for (int i = 0; i < nvec[z]; i++) {
336 int64_t high = data[i].start +
337 ((int64_t)data[i].rep) *
338 data[i].stride +
339 data[i].width;
340 maxv = maxv > high ? maxv : high;
341 minv = minv < data[i].start ? minv
342 : data[i].start;
343 }
344 if (minv < 0) {
345 printf("generated interval set violates lower bound, skipping\n");
346 continue;
347 }
348 if (maxv > 0x40000000LL) {
349 printf("generated interval set would use too much memory to check, skipping\n");
350 continue;
351 }
352
353 const char *names[2] = {"simple", "merges"};
354 for (int k = 0; k < 2; k++) {
355 int dst_count = 0;
356 struct interval *dst_list = NULL;
357
358 int margin = margins[z];
359
360 struct timespec t0, t1;
361 clock_gettime(CLOCK_MONOTONIC, &t0);
362 if (k == 0) {
363 merge_simple(0, NULL, nvec[z], data,
364 &dst_count, &dst_list,
365 margin);
366 } else if (k == 1) {
367 merge_mergesort(0, NULL, nvec[z], data,
368 &dst_count, &dst_list,
369 margin, 0);
370 }
371
372 clock_gettime(CLOCK_MONOTONIC, &t1);
373
374 double elapsed01 =
375 1.0 * (double)(t1.tv_sec -
376 t0.tv_sec) +
377 1e-9 * (double)(t1.tv_nsec -
378 t0.tv_nsec);
379
380 bool pass = check_solution_properties(nvec[z],
381 data, dst_count, dst_list,
382 margins[z]);
383 all_success &= pass;
384
385 int coverage = get_coverage(
386 dst_count, dst_list);
387 printf("%s operation took %9.5f ms, %d intervals, %d bytes, %s\n",
388 names[k], elapsed01 * 1e3,
389 dst_count, coverage,
390 pass ? "pass" : "FAIL");
391 free(dst_list);
392 }
393 free(data);
394 }
395 }
396
397 return all_success ? EXIT_SUCCESS : EXIT_FAILURE;
398 }
399