/*

    memory fragment management library

    Shinji Kono (2006)

    usage:

    MemoryPtr db = 0;
    add_memory(address,length,&db);

	memory pattern is copyied and stored in a binary tree in db.
	All patterns are shared.

    memory pattern database (binary tree by pattern)


 */

#include <stdio.h>
#include <stdlib.h>
#include "memory.h"
#include "crc32.h"
#include <string.h>

#define MEMORY_REPORT 1

#if MEMORY_REPORT
int    memory_header;
int    memcmp_count;
int    memory_body;
int    restore_count;
int    restore_size;
int    range_count;
int    range_size;
#endif

extern void die_exit(char *);

void 
die_exit(char *msg)
{
    fprintf(stderr,"%s\n",msg);
    exit(1);
}

// static MemoryPtr memory_root;


/*

    make memory fragment as a part of the program state

 */

MemoryPtr
create_memory(void *adr, int length)
{
    MemoryPtr m = (MemoryPtr)malloc(sizeof(Memory));
    if (!m) die_exit("Cann't alloc memory list.");
    m->left = m->right = 0;
    m->length = length;
    m->adr = m->body = adr;
#if MEMORY_REPORT
    memory_header++;
#endif
    return m;
}

/*

    Compute hash value of a memory fragment

 */

void
compute_memory_hash1(MemoryPtr m)
{
    m->hash = Get_CRC((unsigned char *)m->adr,m->length);
}

void
free_memory(MemoryPtr m)
{
    m->left = m->right = 0;
    m->adr = m->body = 0;
    free(m);
}

/*

   Compare memory contents ( doesn't care about its address )

 */

int
cmp_content(MemoryPtr a,MemoryPtr b)
{
    if (a->length != b->length) {
      if (a->length > b->length) {
        return 1;
      } else {
        return -1;
      }
    }
    if (a->hash == b->hash) {
#if MEMORY_REPORT
      memcmp_count ++;
#endif
      return memcmp(a->body,b->body,a->length);
    } else if (a->hash > b->hash) {
        return 1;
    } else {
        return -1;
    }
}

/*

   Compare entire memory contents ( doesn't care about its address )

 */

static int
cmp_memory1(MemoryPtr a,MemoryPtr b)
{
    int r;
    if ((r=cmp_content(a,b))) return r;

    if (a->adr==b->adr) {
      return 0;
    } 
    return (a->adr > b->adr) ? 1 : -1;
}

int
cmp_memory(MemoryPtr a,MemoryPtr b)
{
    int r;
    while(1) {
      if ((r=cmp_memory1(a,b))) return r;
      if (a->left && b->left) {
          if ((r=cmp_memory(a->left,b->left))) return r;
      } else if (a->left || b->left) {
          return (a->left > b->left)? 1 : -1;
      }
      if (a->right && b->right) {
          a = a->right; b = b->right;
          // recursive loop
      } else if (a->right || b->right) {
          return (a->right > b->right)? 1 : -1;
      } else {
          return 0;  // singleton
      }
    }
}

/*
    Make a copy of real memory fragments
 */

MemoryPtr 
copy_memory1(MemoryPtr m)
{
    MemoryPtr new = create_memory(m->adr,m->length);
    void *p = (void *)malloc(m->length);
    if (!p) {
      die_exit("can't alloc memory body");
      return 0;
    }
#if MEMORY_REPORT
    memory_body += m->length;
#endif
    memcpy(p,m->adr,m->length);
    m->body = new->body = p;     // abondon original memory pattern
    new->hash = m->hash;
    return new;
}

MemoryPtr
copy_memory(MemoryPtr m, MemoryPtr *db)
{
    MemoryPtr new, out;
    if (!m) return m;
    new = create_memory(m->adr,m->length);
    new->hash = m->hash;
    // look up is necessary to share its memory pattern
    memory_lookup(new, db, copy_memory1, &out);
    if (m->left)  new->left = copy_memory(m->left, db);
    if (m->right) new->right = copy_memory(m->right, db);
    return new;
}

/*
    restore copied memory save to the original addresses
 */

void
restore_memory(MemoryPtr m)
{
    while (m) {
      memcpy(m->adr,m->body,m->length);
#if MEMORY_REPORT
      restore_count ++;
      restore_size += m->length;
#endif
      if (m->left)  restore_memory(m->left);
      m = m->right;
    }
}


/*
    get hash for all memeory fragments
	initial value of hash should be zero
 */

int
get_memory_hash(MemoryPtr m, int hash)
{
    if (!m) return hash;
    compute_memory_hash1(m);
    if (m->left)  hash = get_memory_hash(m->left, hash);
    if (m->right) return get_memory_hash(m->right, hash);
    return m->hash | hash;
}

/*
    add modified memory fragments to the pattern database
 */

MemoryPtr
add_memory(void *ptr,int length, MemoryPtr *parent)
{
    Memory m, *out;
    m.adr = m.body = ptr;
    m.length = length;
    m.left = m.right = 0;
    compute_memory_hash1(&m);
    
    memory_lookup(&m, parent, copy_memory1, &out);
    return out;
}

int
memory_lookup(MemoryPtr m, MemoryPtr *parent, 
		    MemoryPtr (*new_memory)(MemoryPtr), MemoryPtr *out)
{
    MemoryPtr db;
    int r;

    while(1) {
        db = *parent;
        if (!db) {
	    /* not found */
          if (new_memory && out) {
              db = new_memory(m);
              db->left = db->right = 0;
              *out = *parent = db;
          }
          return 0;
        }
        if(!(r = cmp_memory1(m,db))) {
            /* bingo */
          if (out) {
            *out = db;
          }
          return 1;
        } else if (r>0) {
            parent = &db->left;
        } else if (r<0) {
            parent = &db->right;
        }
    }
    /* !NOT REACHED */
}

/*
    memory range list management for state registration
	this list points the real memory
 */

MemoryPtr
add_memory_range(void *ptr,int length, MemoryPtr *parent)
{
    Memory m, *out;
    m.adr = ptr;
    m.length = length;
    m.left = m.right = 0;
    
    memory_range_lookup(&m, parent, &out);
    return out;
}

static int
cmp_range(MemoryPtr a,MemoryPtr b)
{
    if (a->adr==b->adr) {
      if (a->length != b->length) 
        die_exit("memory range inconsitency");
      return 0;
    }
    return (a->adr > b->adr) ? 1 : -1;
}

int
memory_range_lookup(MemoryPtr m, MemoryPtr *parent, MemoryPtr *out)
{
    MemoryPtr db;
    int r;

    while(1) {
        db = *parent;
        if (!db) {
	    /* not found */
          if (out) {
            db = create_memory(m->adr, m->length);
            *out = *parent = db;
          }
#if MEMORY_REPORT
        range_count++;
        range_size+=m->length;
#endif
        return 0;
      }
      if(!(r = cmp_range(m,db))) {
            /* bingo (actually an error) */
        if (out) {
          *out = db;
        }
        return 1;
      } else if (r>0) {
        parent = &db->left;
      } else if (r<0) {
            parent = &db->right;
      }
  }
    /* !NOT REACHED */
}

/*
 */

void
memory_usage()
{
#if MEMORY_REPORT
    printf("	memory_header %d\n",memory_header);
    printf("	memcmp_count %d\n",memcmp_count);
    printf("	memory_body %d\n",memory_body);
    printf("	restore_count %d\n",restore_count);
    printf("	restore_size %d\n",restore_size);
    printf("	range_count %d\n",range_count);
    printf("	range_size %d\n",range_size);
#endif
}


/* end */