3 #include "tests/arc4.h"
5 #include "tests/main.h"
7 #define CHUNK_SIZE (128 * 1024)
8 #define CHUNK_CNT 8 /* Number of chunks. */
9 #define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE) /* Buffer size. */
11 unsigned char buf1[DATA_SIZE], buf2[DATA_SIZE];
12 size_t histogram[256];
14 /* Initialize buf1 with random data,
15 then count the number of instances of each value within it. */
24 arc4_init (&arc4, "foobar", 6);
25 arc4_crypt (&arc4, buf1, sizeof buf1);
26 for (i = 0; i < sizeof buf1; i++)
30 /* Sort each chunk of buf1 using a subprocess. */
34 pid_t children[CHUNK_CNT];
37 for (i = 0; i < CHUNK_CNT; i++)
43 msg ("sort chunk %zu", i);
45 /* Write this chunk to a file. */
46 snprintf (fn, sizeof fn, "buf%zu", i);
47 create (fn, CHUNK_SIZE);
49 CHECK ((handle = open (fn)) > 1, "open \"%s\"", fn);
50 write (handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
53 /* Sort with subprocess. */
54 snprintf (cmd, sizeof cmd, "child-sort %s", fn);
55 CHECK ((children[i] = exec (cmd)) != -1, "exec \"%s\"", cmd);
59 for (i = 0; i < CHUNK_CNT; i++)
64 CHECK (wait (children[i]) == 123, "wait for child %zu", i);
66 /* Read chunk back from file. */
68 snprintf (fn, sizeof fn, "buf%zu", i);
69 CHECK ((handle = open (fn)) > 1, "open \"%s\"", fn);
70 read (handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
76 /* Merge the sorted chunks in buf1 into a fully sorted buf2. */
80 unsigned char *mp[CHUNK_CNT];
87 /* Initialize merge pointers. */
89 for (i = 0; i < CHUNK_CNT; i++)
90 mp[i] = buf1 + CHUNK_SIZE * i;
96 /* Find smallest value. */
98 for (i = 1; i < mp_left; i++)
99 if (*mp[i] < *mp[min])
102 /* Append value to buf2. */
105 /* Advance merge pointer.
106 Delete this chunk from the set if it's emptied. */
107 if ((++mp[min] - buf1) % CHUNK_SIZE == 0)
108 mp[min] = mp[--mp_left];
121 for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram;
124 while (histogram[hist_idx]-- > 0)
126 if (buf2[buf_idx] != hist_idx)
127 fail ("bad value %d in byte %zu", buf2[buf_idx], buf_idx);
132 msg ("success, buf_idx=%'zu", buf_idx);