/*****************************************************************************
 *                                                                           *
 *  Copyright (c) 1993, 1994, Elan Feingold (elan@tasha.cheme.cornell.edu)   *
 *                                                                           *
 *     PERMISSION TO USE, COPY, MODIFY, AND TO DISTRIBUTE THIS SOFTWARE      *
 *     AND ITS DOCUMENTATION FOR ANY PURPOSE IS HEREBY GRANTED WITHOUT       *
 *     FEE, PROVIDED THAT THE ABOVE COPYRIGHT NOTICE APPEAR IN ALL           *
 *     COPIES AND MODIFIED COPIES AND THAT BOTH THAT COPYRIGHT NOTICE AND    *
 *     THIS PERMISSION NOTICE APPEAR IN SUPPORTING DOCUMENTATION.  THERE     *
 *     IS NO REPRESENTATIONS ABOUT THE SUITABILITY OF THIS SOFTWARE FOR      *
 *     ANY PURPOSE.  THIS SOFTWARE IS PROVIDED "AS IS" WITHOUT EXPRESS       *
 *     OR IMPLIED WARRANTY.                                                  *
 *                                                                           *
 *****************************************************************************/

#ifdef MEM_DEBUG
#include <stdio.h>
#include <string.h>

#include "debug.h"

#define ptrFakeToReal(a) (void *)(&((UInt *)a)[0] - 1)
#define ptrRealToFake(a) (void *)(&((UInt *)a)[0] + 1)

#define MAGIC_COOKIE1 0xab
#define MAGIC_COOKIE2 0xcd
#define MAGIC_COOKIE3 0xef
#define MAGIC_COOKIE4 0x12

#define MEM_FILL 0xCC
#define MAX_DATA 32

#define D_FUNCHEADER "ÌÍ¹"
#define D_FUNCHEADERLENGTH 3

/* Data structure for hashing */
#define HASH_TABLE_SIZE 101

Boolean fBootStrapped = FALSE;

/* Data type for storing line/file info for non stack trace debugging */
typedef struct _Trace
{
  UInt   uiLine;
  Char   szFile[MAX_DATA];
} Trace;

/* A cell object for a singly linked list for the chain in chained hashing */
typedef struct _CELL
{
  UInt           uiKey;       /* pointer to memory */
  size_t         size;        /* amount of memory */
  Trace          trcTrace;    /* trace data */
  struct _CELL  *next;
} Cell;


/* Declare the hash table */
struct
{
  UInt      uiEntries;
  UInt      uiTotalMem;
  UInt      uiRealMem;
  Cell     *ppChain[HASH_TABLE_SIZE];
} HashTable;


/* Here is the magic cookie */
unsigned char MagicCookie[] =
{
 MAGIC_COOKIE1,
 MAGIC_COOKIE2,
 MAGIC_COOKIE3,
 MAGIC_COOKIE4
};

/* Debug output */
FILE *hFile;


/****************************************************************
 * When assert fails, this is called
 ****************************************************************/
void _D_AssertFailed(String strFile, UInt iLine, String strError)
{
  Char szTemp[128];

  MEM_BootStrap();
  sprintf(szTemp, "Assertion Failed (%s, %ld) :: %s\n", strFile, iLine, 
	  strError);
  fprintf(hFile, szTemp);
  printf("%s", szTemp);
  exit(-1);
}

/*********************/
void D_BootStrap(void)
{
  D_MemInitHashTable();
  hFile = fopen("debug.log", "w");
  fBootStrapped = TRUE;
}


/*********************************************************
 *  Allocate 8 bytes more than is called for
 * and use this to check for overflows.  Init it
 * to MAGIC_COOKIE, then it got overwritten.
 * Allocate 8 bytes so that we can put one after the
 * memory region returned, and one before, and 8
 * instead of 1 because some architectures (namely the
 * PA-RISC) barf if we don't.  Also fill the memory with
 * MEM_FILL.
 **********************************************************/
void *D_MemAlloc(size_t size, UInt uiLine, String strFile)
{
  void           *pvTemp;
  Byte           *pbTemp;
  Char            szTemp[256];
  size_t          s;

  MEM_BootStrap();

  /* Are we allocating a >0 size block? */
  D_AssertWhere(size>0, "Trying to allocate 0 or less bytes of memory!", uiLine, strFile);

  /* Allocate the block */
  pvTemp = (void *)malloc(size + 8);
  pbTemp = (Byte *)pvTemp;

  /* Did it work? */
  D_AssertWhere(pbTemp != NULL, "Out of memory!", uiLine, strFile);

  /* Fill the memory with MEM_FILL */
  memset(pvTemp, MEM_FILL, size+8);

  /* Init the safety Fields */
  for(s=0; s!=4; s++)
    pbTemp[s] = pbTemp[size+8-s-1] = MagicCookie[s];

  /* Output debug info */
  sprintf(szTemp, "MEM_Alloc():  Created at (%s, %ld) ==> %d bytes, at 0x%08lx\n", strFile, uiLine, size, (UInt)ptrRealToFake(pbTemp));
  D_PrintStr(szTemp);

  /* Put the new pointer into the hash table and return it */
  D_MemHashNewEntry((UInt)pbTemp, size, uiLine, strFile);
  return((FakePtr)(pbTemp+4));
}


/****************************************************/
void D_MemFree(FakePtr vPtr, UInt uiLine, String strFile)
{
  size_t size;

  MEM_BootStrap();

  D_PrintStrLong("MEM_Free():  Freeing chunk [0x%08lx] in (", (UInt)vPtr);
  D_PrintStr(strFile);
  D_PrintStrLong(", %ld)\n", uiLine);

  /* If the pointer is valid, check it for corruptness */
  D_AssertWhere(D_MemKeyInTable((UInt)ptrFakeToReal(vPtr)),
                "Attempting to free bogus pointer!", uiLine, strFile);
  D_MemCheckPointer(vPtr, uiLine, strFile, 0);

  /* Update the memory usage info */
  size = D_MemGetBlockSize(vPtr);
  HashTable.uiTotalMem -= size;
  HashTable.uiRealMem  -= size - 8;

  /* Fill it with the value we use for new memory */
  /* memset(ptrFakeToReal(vPtr), MEM_FILL, size); */

  /* Take it out of the hash table */
  D_MemDeleteEntry((UInt)ptrFakeToReal(vPtr));

  /* Actually free it */
  free(ptrFakeToReal(vPtr));
}



/*********************************************/
void *D_MemShrink(FakePtr fakePtr, size_t sizeNew)
{
  Byte    *pbPtr;
  size_t   size;

  MEM_BootStrap();

  size = D_MemGetBlockSize(fakePtr);
  D_Assert(size>sizeNew, "Not Shrinking Memory!");

  pbPtr = (Byte *)MEM_Alloc(sizeNew);
  memcpy(pbPtr, ptrFakeToReal(fakePtr), size);
  MEM_Free(fakePtr);
  return (FakePtr)pbPtr;
}


/*******************************************/
void *D_MemGrow(FakePtr fakePtr, size_t sizeNew)
{
  Byte    *pbPtr;
  size_t   size;

  MEM_BootStrap();

  size = D_MemGetBlockSize(fakePtr);
  D_Assert(size<sizeNew, "Not Growing Memory!");

  pbPtr = (Byte *)MEM_Alloc(sizeNew);
  memcpy(pbPtr, ptrFakeToReal(fakePtr), size);
  MEM_Free(fakePtr);
  return (FakePtr)pbPtr;
}


/*************************************************************************/
/* Hashes a key into the hash table using a specified hash function      */
/* a specified index to a primary hashing function.  Uses chained        */
/* hashing to resolve collisions.  Updates length of chain in table.     */
/* Returns the length of the chain collided with (before adding new      */
/* key).                                                                 */
/*                                                                       */
/* key:       the integer to store in the table.                         */
/*************************************************************************/
void D_MemHashNewEntry(UInt uiKey, size_t size, UInt uiLine, String strFile)
{
  UInt   uiIndex;
  Cell  *pCell = (Cell *)malloc(sizeof(Cell));

  /* was there enough memory? */
  D_Assert(pCell!=NULL, "Out of memory!");

  /* stick the new cell on the beginning of the list */
  uiIndex = D_MemHashFunc(uiKey);

  /* Init the fields of the Trace data */
  pCell->trcTrace.uiLine =  uiLine;
  StringCopy(pCell->trcTrace.szFile, strFile, MAX_DATA);

  /* Update the memory usage */
  HashTable.uiEntries ++;
  HashTable.uiTotalMem += size;
  HashTable.uiRealMem  += size + 8;

  /* set up a new cell with the key in it */
  pCell->uiKey = uiKey;
  pCell->next  = HashTable.ppChain[uiIndex];
  pCell->size  = size;

  /* link the new cell onto the old chain */
  HashTable.ppChain[uiIndex] = pCell;
}


/****************************************************************
 * This function should not fail!  Deletes a memory table entry
 * from the hash table.
 ****************************************************************/
void D_MemDeleteEntry(UInt uiKey)
{
  UInt     uiIndex;      /* slot in the hash table that the key is hashed to */
  Cell    *pBob, *pJoe;  /* just your average pointers */

  uiIndex = D_MemHashFunc(uiKey);

  /* searching the chain to find the key, if present */
  for(pJoe=pBob=HashTable.ppChain[uiIndex]; pBob && pBob->uiKey!=uiKey; pJoe=pBob, pBob=pBob->next)
    /* TwiddleThumbs() */;

  D_Assert(pBob && pBob->uiKey == uiKey, "Element not in hash table??!!");

  if(pBob==pJoe)
   {
     HashTable.ppChain[uiIndex] = pBob->next;
     free(pJoe);
   }
  else
   {
     pJoe->next = pJoe->next->next;
     free(pBob);
   }
}


/************************************************************************/
/* Initializes the hash table by setting the keys equal to zero and the */
/* chain pointers to NULL.                                              */
/************************************************************************/
void D_MemInitHashTable(void)
{
  UInt i;

  for(i=0; i!=HASH_TABLE_SIZE; i++)
    HashTable.ppChain[i] = NULL;

  HashTable.uiEntries = 0;
  HashTable.uiTotalMem = HashTable.uiRealMem = (UInt)0;
}


/************************************************************
 * If entry in table, return size.  If not, assert and exit.
 * Should always be in table when we call.
 ************************************************************/
size_t D_MemGetBlockSize(FakePtr fakePtr)
{
  UInt     uiIndex;  /* slot in the hash table that the key is hashed to */
  Cell    *pBob;     /* just your average pointer */
  UInt     uiTemp = (UInt)ptrFakeToReal(fakePtr);

  uiIndex = D_MemHashFunc(uiTemp);

  /* searching the chain to find the key, if present */
  for(pBob=HashTable.ppChain[uiIndex]; pBob && pBob->uiKey!=uiTemp; pBob=pBob->next)
    /* TwiddleThumbs() */ ;

  if(!(pBob && pBob->uiKey == uiTemp))
    return (size_t)0;

  return (size_t)pBob->size;
}


/******************************************************************/
/* Searches in a hash table for a key and returns TRUE is the key */
/* is present and FALSE otherwise.                                */
/*  key:         the key to search for.                           */
/*  hash_scheme: the scheme used to hash the key into the table   */
/*               in the first place.                              */
/*  hash_func:   the hash function used to hash the key into the  */
/*               table in the first place.                        */
/*  j:           the index of the primary hash function.          */
/******************************************************************/
Boolean D_MemKeyInTable(UInt uiKey)
{
  UInt   uiIndex;  /* slot in the hash table that the key is hashed to */
  Cell  *pBob;   /* just your average pointer */

  uiIndex = D_MemHashFunc(uiKey);

  /* searching the chain to find the key, if present */
  for(pBob=HashTable.ppChain[uiIndex]; pBob; pBob=pBob->next)
    if(pBob->uiKey==uiKey)
      return(TRUE);

  return(FALSE);
}


/*********************************************************************
 * Checks a pointer for data overrun.  NOTE!!!!! This is a fake type
 * pointer that is checked, not areal pointer, since it assumes that
 * the region of memory directly after and before one dword is valid!
 *********************************************************************/
void D_MemCheckPointer(FakePtr fakePtr, UInt uiLine, String strFile, Boolean fDisp)
{
  Byte     *bPtr = (Byte *)ptrFakeToReal(fakePtr);
  size_t    size, s;

  MEM_BootStrap();

  if(fDisp)
   {
     D_PrintStrLong("MEM_CheckPointer():  Chunk [0x%08lx] in (", (UInt)fakePtr);
     D_PrintStr(strFile);
     D_PrintStrInt(", %ld) ", uiLine);
   }

  /* Is it even in the hash table */
  D_AssertWhere((size=D_MemGetBlockSize(fakePtr)), "Bogus pointer!", uiLine, strFile);;

  if(fDisp)
    D_PrintStrLong(" [%d bytes]\n", (size_t)size);

  /* Check for the magic cookie */
  for(s=0; s!=4; s++)
   {
     if(bPtr[s] != MagicCookie[s])
      {
        /* Print the cookie */
        D_PrintStr("Lower Cookie: [");
        for(s=0; s!=4; s++)
          D_PrintStrLong("0x%02x|", bPtr[s]);
        D_PrintStr("]\n");

        D_AssertWhere(FALSE, "Corrupt Memory (Underflow)!", uiLine, strFile);
      }

     if(bPtr[size+8-s-1] != MagicCookie[s])
      {
        /* Print the cookie */
        D_PrintStr("Upper Cookie: [");
        for(s=0; s!=4; s++)
          D_PrintStrLong("0x%02x|", bPtr[size+8-s-1]);
        D_PrintStr("]\n");

        D_AssertWhere(FALSE, "Corrupt Memory (Overflow)!", uiLine, strFile);
      }
   }
}


/*****************************************************/
void D_MemCheckAllPointers(UInt uiLine, String strFile)
{
  UInt   i;
  Cell  *pCell;

  MEM_BootStrap();
  D_PrintStr("MEM_CheckAllPointers():  Performing memory check in (");
  D_PrintStr(strFile);
  D_PrintStrLong(", %ld)...\n", uiLine);
  D_PrintStrInt("  Total Memory allocated by client: %d\n", HashTable.uiTotalMem);

  /* Run through the whole hash pointer, dumping and checking the pointers */
  for(i=0; i!=HASH_TABLE_SIZE; i++)
    for(pCell=HashTable.ppChain[i]; pCell; pCell=pCell->next)
     {
       D_PrintStr("  ");
       D_MemCheckPointer(ptrRealToFake(pCell->uiKey), pCell->trcTrace.uiLine,
                         pCell->trcTrace.szFile, 1);
     }
}


/***************************/
void D_MemDumpPointers(void)
{
  UInt   i, uiCount;
  Cell  *pCell;

  MEM_BootStrap();
  D_PrintStr("MEM_DumpPointers():  Dumping all pointers...\n");

  /* Run through the whole hash table */
  for(i=uiCount=0; i!=HASH_TABLE_SIZE; i++)
   {
    D_PrintStrInt("%d: ", i);
    for(pCell=HashTable.ppChain[i]; pCell; pCell=pCell->next, uiCount++)
      D_PrintStrLong("0x%08lx, ", pCell->uiKey);
    D_PrintStr("\n");
   }
  D_PrintStrInt("***** Total Chunks in Hash Table: %d\n", uiCount);
}


/******************************************************/
String StringCopy(String strDst, String strSrc, UShort usNum)
{
  strncpy(strDst, strSrc, usNum-1);
  strDst[usNum-1] = '\0';
  return(strDst);
}


/******************/
void D_TheEnd(void)
{
  UInt   i;
  Cell  *p, *q, *pCell;  /* Mind your P's and Q's... */

  /* Check for memory leaks */
  D_PrintStr("************ Memory Leaks ***********\n");
  D_PrintStrInt("  Total Memory allocated by client: %d\n", HashTable.uiTotalMem);

  /* Run through the whole hash pointer, freeing all of the pointers */
  for(i=0; i!=HASH_TABLE_SIZE; i++)
    for(pCell=HashTable.ppChain[i]; pCell; pCell=pCell->next)
     {
       D_PrintStr("  ");
       D_MemCheckPointer(ptrRealToFake(pCell->uiKey), pCell->trcTrace.uiLine,
                         pCell->trcTrace.szFile, 1);
       /* MEM_Free(ptrRealToFake(pCell->uiKey)); */
     }

  for (i=0; i!=HASH_TABLE_SIZE; i++)
    for (p=HashTable.ppChain[i]; p; p=q)
     {
       q = p->next;
       free(p);
     }
}


/***********************************************************************/
UInt D_MemHashFunc(UInt x) { return(x % (UInt)HASH_TABLE_SIZE); }


#endif
