1 /* Generates about 1 MB of random data that is then divided into
2 16 chunks. A separate subprocess sorts each chunk in
3 sequence. Then we merge the chunks and verify that the result
4 is what it should be. */
7 #include "tests/arc4.h"
9 #include "tests/main.h"
11 /* This is the max file size for an older version of the Pintos
12 file system that had 126 direct blocks each pointing to a
13 single disk sector. We could raise it now. */
14 #define CHUNK_SIZE (126 * 512)
15 #define CHUNK_CNT 16 /* Number of chunks. */
16 #define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE) /* Buffer size. */
18 unsigned char buf1[DATA_SIZE], buf2[DATA_SIZE];
19 size_t histogram[256];
21 /* Initialize buf1 with random data,
22 then count the number of instances of each value within it. */
31 arc4_init (&arc4, "foobar", 6);
32 arc4_crypt (&arc4, buf1, sizeof buf1);
33 for (i = 0; i < sizeof buf1; i++)
37 /* Sort each chunk of buf1 using a subprocess. */
43 create ("buffer", CHUNK_SIZE);
44 for (i = 0; i < CHUNK_CNT; i++)
49 msg ("sort chunk %zu", i);
51 /* Write this chunk to a file. */
53 CHECK ((handle = open ("buffer")) > 1, "open \"buffer\"");
54 write (handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
57 /* Sort with subprocess. */
58 CHECK ((child = exec ("child-sort buffer")) != -1,
59 "exec \"child-sort buffer\"");
60 CHECK (wait (child) == 123, "wait for child-sort");
62 /* Read chunk back from file. */
63 CHECK ((handle = open ("buffer")) > 1, "open \"buffer\"");
64 read (handle, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
71 /* Merge the sorted chunks in buf1 into a fully sorted buf2. */
75 unsigned char *mp[CHUNK_CNT];
82 /* Initialize merge pointers. */
84 for (i = 0; i < CHUNK_CNT; i++)
85 mp[i] = buf1 + CHUNK_SIZE * i;
91 /* Find smallest value. */
93 for (i = 1; i < mp_left; i++)
94 if (*mp[i] < *mp[min])
97 /* Append value to buf2. */
100 /* Advance merge pointer.
101 Delete this chunk from the set if it's emptied. */
102 if ((++mp[min] - buf1) % CHUNK_SIZE == 0)
103 mp[min] = mp[--mp_left];
116 for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram;
119 while (histogram[hist_idx]-- > 0)
121 if (buf2[buf_idx] != hist_idx)
122 fail ("bad value %d in byte %zu", buf2[buf_idx], buf_idx);
127 msg ("success, buf_idx=%'zu", buf_idx);