/* MD.c

   by Fabbian G. Dufoe, III

   This is a public domain program.  Use it however you like.

   This program tests all the memory which the operating system will
   allocate to it.  It writes a test value to each address.  Then it reads
   each address and compares the result with the test value.  If the value
   read from memory doesn't match the test value the program writes the
   address (the pointer value), the expected contents, and the actual
   contents of the memory location to standard output.  When all allocated
   memory has been tested against one test value the program moves to the
   next one.  The test values are 0x00, 0xff, 0x55, and 0xaa.

   A command line option directs the program to write a list of bad
   addresses to a file.  The file will contain all the addresses at which an
   error was detected.  The addresses will be listed in ascending order and
   each address will appear only once.  Addresses will be separated by
   newlines.  The addresses will be ASCII characters representing
   hexadecimal values.  The program will not list more than 100 addresses.

   While the program is running it writes status messages to standard error.

   Usage: MD [>reportfile] [-qaddressfile]
*/

#define NULL 0L
#define SIZE 1000
#define VERSION "Version 1.1, 10 April 1989\n\n"
#define USAGE "Usage: MD [>reportfile] [-qaddressfile]\n"

#include <time.h>
#include <stdio.h>

typedef struct
{
   unsigned char *ptr;
   unsigned long int size;
} Block;

unsigned char *Addr[100];
unsigned short int AddrCnt = 0;

void
main(argc, argv)
int argc;
char **argv;
{
   void AddAddr(unsigned char *);
   FILE *AddrFile;
   unsigned short int AddrList = 0;
   Block block[SIZE];
   unsigned short int count = 0;
   unsigned long int errct = 0;
   unsigned short int high;
   unsigned short int i;
   unsigned long int offset;
   unsigned char *ptr;
   unsigned long int size;
   signed long int t;
   static unsigned char TestVal[] = {0, 0xff, 0x55, 0xaa};
   unsigned short int val;

   /* We need to check for command line arguments.  A "-q" directs the
      program to write a file of bad addresses. */
   if (argc == 2 && argv[1][0] == '-' && argv[1][1] == 'q')
   {
      /* If we can't open the file we'll terminate the program with an error
         message. */
      if ((AddrFile = fopen(&argv[1][2], "w")) == NULL)
      {
         fputs(USAGE, stderr);
         fputs("Cannot open output file.\n", stderr);
         exit(30);
      }
      AddrList = 1;
   }
   else if (argc > 1)
   {
      /* If the command line arguments were incorrect we'll terminate the
         program with a usage message. */
      fputs(USAGE, stderr);
      exit(30);
   }

   /* We want to include the time the diagnostic program was run in the
      report.  That requires getting the current system time.
   */
   time(&t);

   /* We'll print a report heading and copyright notice at the beginning.
   */
   printf("MD--Memory Diagnostic.\n");
   printf("by Fabbian G. Dufoe, III\n");
   printf(VERSION);
   printf("Memory tested %s\n\n", ctime(&t));

   /* We'll start by allocating memory in blocks of one megabyte.  The plan
      is to allocate as many one-megabyte blocks as we can.  Then we'll
      halve the block size, allocate as many blocks of that size as we can,
      and repeat the process until (a) all the memory is gone or (b) we've
      filled the array we allocated for keeping track of memory blocks.
   */
   size = 1048576;
   while (size > 0 && count < SIZE)
   {
      fprintf(stderr, "Allocating %ld byte blocks.\n", size);
      while ((ptr = (unsigned char *)malloc(size)) != NULL)
      {
         block[count].ptr = ptr;
         block[count++].size = size;
      }
      if (size == 1)
         size = 0;
      else
         size >>= 1;
   }

   /* Because we expect seldom to use the entire array we've set aside we
      need to save the number of the highest element actually used.
   */
   high = count;

   /* At this point we want to sort the block pointers.  It makes the output
      easier to follow if memory errors are reported in ascending order
      by their address.  We aren't guaranteed that memory will be
      allocated in any particular order.  We'll use an insertion sort and
      we'll sort only that part of the array we used.  That means we'll
      keep the index values between 0 and high.

      An insertion sort works by shifting all the items left of the current
      one right one position until an item is less than the current one.
      Imagine the items to be sorted are laid out from left to right.  Then
      the sort places the current item in the position vacated by the last
      item to be shifted right.  The sort starts with the second item as
      the current one and proceeds to the right until all the items have had
      a turn as the current one.
   */
   fprintf(stderr, "Sorting block list.\n");
   for (count = 1; count < high; count++)
   {
      short int i;

      ptr = block[count].ptr;
      size = block[count].size;
      i = count - 1;
      while (i >=0 && ptr < block[i].ptr)
      {
         block[i+1].ptr = block[i].ptr;
         block[i+1].size = block[i].size;
         i--;
      }
      block[i+1].ptr = ptr;
      block[i+1].size = size;
   }
   fprintf(stderr, "Sort complete.\n");

   /* We'll list the block addresses and size in the report.
   */
   printf("Blocks examined:\n");
   printf("Block #    Address         Size\n\n");
   for (count = 0; count < high; count++)
   {
      printf("%4d      %8lX      %7ld\n", count, block[count].ptr,
             block[count].size);
   }
   printf("\n");

   /* Now that we've sorted our list of blocks we're ready to start testing
      them.  The first step is to initialize all the variables to 0, the
      first test value.
   */
   for (count = 0; count < high; count++)
   {
      fprintf(stderr, "Initializing block %d, %ld bytes.\n", count,
                      block[count].size);
      for (offset = 0; offset < block[count].size; offset++)
         *(block[count].ptr+offset) = TestVal[0];
   }

   /* Next we'll go through all the blocks to see if they contain the test
      value with which they were loaded.  If not we'll identify the address
      that failed, the value it contained, and the value it should have
      contained.  We'll do that for each valid test value.
   */
   for (val = 1; val < 4; val++)
   {
      fprintf(stderr, "Testing value %X.\n", TestVal[val-1]);
      for (count = 0; count < high; count++)
      {
         fprintf(stderr, "Testing block %d, %ld bytes with %X\n", count,
                         block[count].size, TestVal[val-1]);
         for (offset = 0; offset < block[count].size; offset++)
         {
            if (*(block[count].ptr+offset) != TestVal[val-1])
            {
               printf("ERROR! Address: %8lX  found: %2X  expected: %2X\n",
                       block[count].ptr+offset, *(block[count].ptr+offset),
                       TestVal[val-1]);
               errct++;
               AddAddr(block[count].ptr+offset);
            }
            *(block[count].ptr+offset) = TestVal[val];
         }
      }
   }

   /* We've tested for all values except the last one.  It's time to do that
      now.
   */
   val--;
   fprintf(stderr, "Testing value %X.\n", TestVal[val]);
   for (count = 0; count < high; count++)
   {
      fprintf(stderr, "Testing block %d, %ld bytes with %X\n", count,
              block[count].size, TestVal[val]);
      for (offset = 0; offset < block[count].size; offset++)
      {
         if (*(block[count].ptr+offset) != TestVal[val])
         {
            printf("ERROR! Address: %8lX  found: %2X  expected: %2X\n",
                    block[count].ptr+offset, *(block[count].ptr+offset),
                    TestVal[val]);
            errct++;
            AddAddr(block[count].ptr+offset);
         }
      }
   }

   /* The testing is finished so we'll report the number of errors we found.
   */
   printf("\nMD found %d errors.\n", errct);

   /* When we've completed all our tests we free all the memory we allocated
      and exit. */
   for (count = 0; count < high; count++)
   {
      fprintf(stderr, "Freeing block %d.\n", count);
      free(block[count].ptr);
   }

   /* If an address list file was requested we'll write it and close the
      file. */
   if (AddrList == 1)
   {
      for (i = 0; i < AddrCnt; i++)
         fprintf(AddrFile, "%8lX\n", Addr[i]);
      fclose(AddrFile);
   }

   exit(0);
}