/*

  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 */