2 #include "tests/arc4.h"
4 #include "tests/main.h"
6 /* This is the max file size for an older version of the Pintos
7 file system that had 126 direct blocks each pointing to a
8 single disk sector. We could raise it now. */
9 #define CHUNK_SIZE (126 * 512)
10 #define CHUNK_CNT 16 /* Number of chunks. */
11 #define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE) /* Buffer size. */
13 unsigned char buf1[DATA_SIZE], buf2[DATA_SIZE];
14 size_t histogram[256];
16 /* Initialize buf1 with random data,
17 then count the number of instances of each value within it. */
26 arc4_init (&arc4, "foobar", 6);
27 arc4_crypt (&arc4, buf1, sizeof buf1);
28 for (i = 0; i < sizeof buf1; i++)
32 /* Sort each chunk of buf1 using a subprocess. */
38 create ("buffer", CHUNK_SIZE);
39 for (i = 0; i < CHUNK_CNT; i++)
44 msg ("sort chunk %zu", i);
46 /* Write this chunk to a file. */
48 CHECK ((handle = open ("buffer")) > 1, "open \"buffer\"");
49 write (handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
52 /* Sort with subprocess. */
53 CHECK ((child = exec ("child-sort buffer")) != -1,
54 "exec \"child-sort buffer\"");
55 CHECK (wait (child) == 123, "wait for child-sort");
57 /* Read chunk back from file. */
58 CHECK ((handle = open ("buffer")) > 1, "open \"buffer\"");
59 read (handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
66 /* Merge the sorted chunks in buf1 into a fully sorted buf2. */
70 unsigned char *mp[CHUNK_CNT];
77 /* Initialize merge pointers. */
79 for (i = 0; i < CHUNK_CNT; i++)
80 mp[i] = buf1 + CHUNK_SIZE * i;
86 /* Find smallest value. */
88 for (i = 1; i < mp_left; i++)
89 if (*mp[i] < *mp[min])
92 /* Append value to buf2. */
95 /* Advance merge pointer.
96 Delete this chunk from the set if it's emptied. */
97 if ((++mp[min] - buf1) % CHUNK_SIZE == 0)
98 mp[min] = mp[--mp_left];
111 for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram;
114 while (histogram[hist_idx]-- > 0)
116 if (buf2[buf_idx] != hist_idx)
117 fail ("bad value %d in byte %zu", buf2[buf_idx], buf_idx);
122 msg ("success, buf_idx=%'zu", buf_idx);