/* MD.c

   by Fabbian G. Dufoe, III

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

   This program tests any memory which the operating system will allocate to
   it.  It tests the memory one byte at a time by setting it to 0x00, the
   comparing it to 0x00, setting it to 0xff, and comparing it to 0xff.  If
   the comparison fails it writes the memory address (the pointer value),
   the expected contents, and the actual contents of the memory location to
   standard output.  Standard output may be redirected to a file if it is
   desired to save the report.

*/

#define NULL 0L
#define SIZE 1000
#define VERSION "Version 1.0, 10 January 1989\n\n"

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

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

void
main()
{
   Block block[SIZE];
   unsigned short int count = 0;
   unsigned long int errct = 0;
   unsigned short int high;
   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 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 to seldom 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++;
            }
            *(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++;
         }
      }
   }

   /* 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);
   }
   exit(0);
}