--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/memory.c	Wed Dec 16 15:16:11 2015 +0900
@@ -0,0 +1,359 @@
+/*
+
+    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 */