pintos-os.org Git - pintos-anon/blob - grading/vm/page-merge-seq.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #ifdef PINTOS
   4 #include <syscall.h>
   5 #else
   6 #include <unistd.h>
   7 #include <fcntl.h>
   8 #endif
   9 #include "arc4.h"
  10
  11 #define CHUNK_SIZE (63 * 1024)                  /* Max file size. */
  12 #define CHUNK_CNT 16                            /* Number of chunks. */
  13 #define DATA_SIZE (CHUNK_CNT * CHUNK_SIZE)      /* Buffer size. */
  14
  15 unsigned char buf1[DATA_SIZE], buf2[DATA_SIZE];
  16 size_t histogram[256];
  17
  18 /* Initialize buf1 with random data,
  19    then count the number of instances of each value within it. */
  20 static void
  21 init (void)
  22 {
  23   struct arc4 arc4;
  24   size_t i;
  25
  26   printf ("page-merge-seq) init\n");
  27
  28   arc4_init (&arc4, "foobar", 6);
  29   arc4_crypt (&arc4, buf1, sizeof buf1);
  30   for (i = 0; i < sizeof buf1; i++)
  31     histogram[buf1[i]]++;
  32 }
  33
  34 /* Sort each chunk of buf1 using a subprocess. */
  35 static void
  36 sort (void)
  37 {
  38   size_t i;
  39
  40 #ifdef PINTOS
  41   create ("buffer", CHUNK_SIZE);
  42 #endif
  43   for (i = 0; i < CHUNK_CNT; i++)
  44     {
  45       int fd;
  46
  47       printf ("(page-merge-seq) sort chunk %zu\n", i);
  48
  49       /* Write this chunk to a file. */
  50 #ifdef PINTOS
  51       fd = open ("buffer");
  52 #else
  53       fd = open ("buffer", O_WRONLY | O_CREAT, 0660);
  54 #endif
  55       if (fd < 0)
  56         {
  57           printf ("(page-merge-seq) open() failed\n");
  58           exit (1);
  59         }
  60       write (fd, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
  61       close (fd);
  62
  63       /* Sort with subprocess. */
  64 #ifdef PINTOS
  65       pid_t child = exec ("child-sort");
  66       if (child == -1)
  67         {
  68           printf ("(page-merge-seq) exec() failed\n");
  69           exit (1);
  70         }
  71       if (join (child) != 0x123)
  72         {
  73           printf ("(page-merge-seq) join(exec()) returned bad value\n");
  74           exit (1);
  75         }
  76 #else
  77       system ("./child-sort");
  78 #endif
  79
  80       /* Read chunk back from file. */
  81 #ifdef PINTOS
  82       fd = open ("buffer");
  83 #else
  84       fd = open ("buffer", O_RDONLY);
  85 #endif
  86       if (fd < 0)
  87         {
  88           printf ("(page-merge-seq) open() failed\n");
  89           exit (1);
  90         }
  91       read (fd, buf1 + CHUNK_SIZE * i, CHUNK_SIZE);
  92       close (fd);
  93     }
  94 }
  95
  96 /* Merge the sorted chunks in buf1 into a fully sorted buf2. */
  97 static void
  98 merge (void)
  99 {
 100   unsigned char *mp[CHUNK_CNT];
 101   size_t mp_left;
 102   unsigned char *op;
 103   size_t i;
 104
 105   printf ("(page-merge-seq) merge\n");
 106
 107   /* Initialize merge pointers. */
 108   mp_left = CHUNK_CNT;
 109   for (i = 0; i < CHUNK_CNT; i++)
 110     mp[i] = buf1 + CHUNK_SIZE * i;
 111
 112   /* Merge. */
 113   op = buf2;
 114   while (mp_left > 0)
 115     {
 116       /* Find smallest value. */
 117       size_t min = 0;
 118       for (i = 1; i < mp_left; i++)
 119         if (*mp[i] < *mp[min])
 120           min = i;
 121
 122       /* Append value to buf2. */
 123       *op++ = *mp[min];
 124
 125       /* Advance merge pointer.
 126          Delete this chunk from the set if it's emptied. */
 127       if ((++mp[min] - buf1) % CHUNK_SIZE == 0)
 128         mp[min] = mp[--mp_left];
 129     }
 130 }
 131
 132 static void
 133 verify (void)
 134 {
 135   size_t buf_idx;
 136   size_t hist_idx;
 137
 138   printf ("(page-merge-seq) verify\n");
 139
 140   buf_idx = 0;
 141   for (hist_idx = 0; hist_idx < sizeof histogram / sizeof *histogram;
 142        hist_idx++)
 143     {
 144       while (histogram[hist_idx]-- > 0)
 145         {
 146           if (buf2[buf_idx] != hist_idx)
 147             {
 148               printf ("(page-merge-seq) bad value %d in byte %zu\n",
 149                       buf2[buf_idx], buf_idx);
 150               exit (1);
 151             }
 152           buf_idx++;
 153         }
 154     }
 155
 156   printf ("(page-merge-seq) success, buf_idx=%zu\n", buf_idx);
 157 }
 158
 159 int
 160 main (void)
 161 {
 162   printf ("(page-merge-seq) begin\n");
 163   init ();
 164   sort ();
 165   merge ();
 166   verify ();
 167   printf ("(page-merge-seq) end\n");
 168   return 0;
 169 }