data.cc

功能较全面的反汇编器：反汇编器ht-2.0.15.tar.gz

/*
 *	HT Editor
 *	data.cc
 *
 *	Copyright (C) 2002 Stefan Weyergraf ([e-mail])
 *	Copyright (C) 2002, 2003 Sebastian Biallas ([e-mail])
 *
 *	This program is free software; you can redistribute it and/or modify
 *	it under the terms of the GNU General Public License version 2 as
 *	published by the Free Software Foundation.
 *
 *	This program is distributed in the hope that it will be useful,
 *	but WITHOUT ANY WARRANTY; without even the implied warranty of
 *	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *	GNU General Public License for more details.
 *
 *	You should have received a copy of the GNU General Public License
 *	along with this program; if not, write to the Free Software
 *	Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include <new>
#include <cstring>
#include <cstdlib>
#include <typeinfo>

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include "atom.h"
#include "except.h"

#include "data.h"
#include "htdebug.h"
#include "snprintf.h"
#include "stream.h"
#include "store.h"

int autoCompare(const Object *a, const Object *b)
{
// FIXME: better use instanceOf
// SB: warum auskommentieren?
// SW: weil nicht so gute logik
//     wie gesagt FIXME, aber bin mir unsicher wie genau

/*	uint	ida = a->getObjectID();
	uint idb = b->getObjectID();
	if (ida != idb) return ida-idb;*/
	return a->compareTo(b);
}

/*
 *	Object
 */

int Object::compareTo(const Object *obj) const
{
//	int a=1;
	throw NotImplementedException(HERE);
}

int Object::toString(char *buf, int buflen) const
{
	ObjectID oid = getObjectID();
	unsigned char c[20];
	int l = 4;
	c[0] = (oid >> 24) & 0xff;
	c[1] = (oid >> 16) & 0xff;
	c[2] = (oid >>  8) & 0xff;
	c[3] = oid & 0xff;
	for (int i = 0; i < 4; i++) {
		if (c[i] < 32 || c[i] > 127) {
			c[l] = '\\';
			c[l+1] = "0123456789abcdef"[c[i] >> 4];
			c[l+2] = "0123456789abcdef"[c[i] & 0xf];
			l += 3;
		} else {
			c[l] = c[i];
			l++;
		}
	}
	c[l] = 0;
	return ht_snprintf(buf, buflen, "Object-%s", c+4);
}

Object *Object::clone() const
{
	throw NotImplementedException(HERE);
}

bool	Object::idle()
{
	return false;
}

void Object::load(ObjectStream &s)
{
}

ObjectID Object::getObjectID() const
{
	return OBJID_OBJECT;
}

void	Object::store(ObjectStream &s) const
{
}

/*
 *	Enumerator
 */
/*Object *Enumerator::operator [] (int idx) const
{
	ObjHandle h = findByIdx(idx);
	return (h != invObjHandle) ? get(h) : NULL;
}*/

ObjHandle Enumerator::find(const Object *key) const
{
	ObjHandle h = findFirst();
	while (h != invObjHandle) {
		if (compareObjects(get(h), key) == 0) return h;
		h = findNext(h);
	}
	return invObjHandle;
}

ObjHandle Enumerator::findG(const Object *key) const
{
	ObjHandle h = findFirst();
	ObjHandle best = invObjHandle;
	while (h != invObjHandle) {
		int c = compareObjects(get(h), key);
		if (c > 0) {
			// h is greater than key
			if (best != invObjHandle) {
				if (compareObjects(get(h), get(best)) < 0) best = h;
			} else {
				best = h;
			}
		}
		h = findNext(h);
	}
	return best;
}

ObjHandle Enumerator::findGE(const Object *key) const
{
	ObjHandle h = findFirst();
	ObjHandle best = invObjHandle;
	while (h != invObjHandle) {
		int c = compareObjects(get(h), key);
		if (c == 0) return h;
		if (c > 0) {
			// h is greater than key
			if (best != invObjHandle) {
				if (compareObjects(get(h), get(best)) < 0) best = h;
			} else {
				best = h;
			}
		}
		h = findNext(h);
	}
	return best;
}

ObjHandle Enumerator::findLE(const Object *key) const
{
	ObjHandle h = findFirst();
	ObjHandle best = invObjHandle;
	while (h != invObjHandle) {
		int c = compareObjects(get(h), key);
		if (c == 0) return h;
		if (c < 0) {
			// h is lower than key
			if (best != invObjHandle) {
				if (compareObjects(get(h), get(best)) > 0) best = h;
			} else {
				best = h;
			}
		}
		h = findNext(h);
	}
	return best;
}

ObjHandle Enumerator::findL(const Object *key) const
{
	ObjHandle h = findFirst();
	ObjHandle best = invObjHandle;
	while (h != invObjHandle) {
		int c = compareObjects(get(h), key);
		if (c < 0) {
			// h is lower than key
			if (best != invObjHandle) {
				if (compareObjects(get(h), get(best)) > 0) best = h;
			} else {
				best = h;
			}
		}
		h = findNext(h);
	}
	return best;
}

int Enumerator::toString(char *buf, int buflen) const
{
	ObjHandle h = findFirst();
	int n = 0;
	if (buflen>1) { *buf++ = '('; buflen--; n++; }
	while ((buflen>0) && h) {
		Object *d = get(h);
		int k = d->toString(buf, buflen);
		buflen -= k;
		buf += k;
		n += k;
		bool comma;
		if (buflen>1) { *buf++ = ','; buflen--; n++; comma = true; } else comma = false;
		h = findNext(h);
		if (!h && comma) { buf--; buflen++; n--; }
	}
	if (buflen>1) { *buf++ = ')'; buflen--; n++; }
	if (buflen>0) *buf++ = 0;
	return n;
}

/*
 *	Container
 */
Container::Container()
{
	hom_objid = OBJID_TEMP;
}

bool Container::delObj(Object *sig)
{
	return del(find(sig));
}

ObjHandle Container::findOrInsert(Object *obj, bool &inserted)
{
	ObjHandle h = find(obj);
	if (h == invObjHandle) {
		h = insert(obj);
		inserted = true;
	} else {
		inserted = false;
	}
	return h;
}

void Container::notifyInsertOrSet(const Object *o)
{
	if (!o) return;
	if (hom_objid == OBJID_TEMP) {
		hom_objid = o->getObjectID();
	} else if (hom_objid != OBJID_INVALID) {
		if (hom_objid != o->getObjectID()) hom_objid = OBJID_INVALID;
	}
}

Object *Container::removeObj(const Object *sig)
{
	return remove(find(sig));
}

/*
 *	Array
 */

#define ARRAY_ALLOC_MIN			4

/*
 *	grow array size by factor (ARRAY_ALLOC_GROW_NUM / ARRAY_ALLOC_GROW_DENOM)
 *	but never by more than ARRAY_ALLOC_GROW_ABSMAX.
 */
#define ARRAY_ALLOC_GROW_NUM		3
#define ARRAY_ALLOC_GROW_DENOM	2

#define ARRAY_ALLOC_GROW_ABSMAX	64*1024

Array::Array(bool oo, int prealloc)
{
	own_objects = oo;
	ecount = 0;
	acount = 0;
	elems = NULL;

	realloc(prealloc);
}

Array::~Array()
{
	delAll();
}

void Array::delAll()
{
	// SB: Doppelte ueberpruefung von oo
	if (elems) {
		if (own_objects) {
			for (uint i=0; i<ecount; i++) {
				freeObj(elems[i]);
			}
		}
		free(elems);
	}
	ecount = 0;
	acount = 0;
	elems = NULL;
}

int Array::delRange(int start, int end)
{
	if (!ecount) return 0;
	if (start < 0) start = 0;
	if (start > end) return 0;
	if ((uint)end >= ecount) end = ecount - 1;
	if (own_objects) {
		uint ende = end;
		for (uint i = start; i <= ende; i++) {
			freeObj(elems[i]);
		}
	}
	memmove(elems+start, elems+end+1, sizeof (*elems) * (ecount-end-1));
	ecount -= end-start+1;
	checkShrink();
	return end-start+1;
}

Array *Array::clone() const
{
	Array *a = new Array(own_objects, ecount);
	for (uint i = 0; i<ecount; i++) {
		Object *e = get(findByIdx(i));
		if (own_objects) e = e->clone();
		a->insert(e);
	}
	return a;
}

void Array::load(ObjectStream &s)
{
	own_objects = true;

	GET_INT32D(s, ecount);
	acount = 0;
	elems = NULL;
	realloc(ecount);
	if (ecount) {
		GET_INT32X(s, hom_objid);

		for (uint i=0; i < ecount; i++) {
			Object *obj = s.getObjectInternal("element", hom_objid);
			elems[i] = obj;
		}
	} else {
		hom_objid = OBJID_TEMP;	
	}
}

ObjectID Array::getObjectID() const
{
	return OBJID_ARRAY;
}

void Array::store(ObjectStream &s) const
{
	PUT_INT32D(s, ecount);
	if (ecount) {
		assert(hom_objid != OBJID_TEMP);
		putIDComment(s, hom_objid);
		PUT_INT32X(s, hom_objid);

		for (uint i = 0; i<ecount; i++) {
			s.putObject(elems[i], "element", hom_objid);
		}
	}
}

int Array::calcNewBufferSize(int curbufsize, int min_newbufsize) const
{
	int n = curbufsize;
	if (n < ARRAY_ALLOC_MIN) n = ARRAY_ALLOC_MIN;
	if (n < min_newbufsize) {
		while (n < min_newbufsize) {
			n *= ARRAY_ALLOC_GROW_NUM;
			n /= ARRAY_ALLOC_GROW_DENOM;
		}
	} else {
		while (n > min_newbufsize) {
			n *= ARRAY_ALLOC_GROW_DENOM;
			n /= ARRAY_ALLOC_GROW_NUM;
		}
	}
	if (n-curbufsize > ARRAY_ALLOC_GROW_ABSMAX) {
		n = curbufsize + ARRAY_ALLOC_GROW_ABSMAX;
	}
	if (n < ARRAY_ALLOC_MIN) n = ARRAY_ALLOC_MIN;
	if (n < min_newbufsize) {
		n = min_newbufsize;
	}

	return n;
}

void Array::checkShrink()
{
	// FIXME: implement automatic shrinking
	memset(elems+ecount, 0, (acount-ecount) * sizeof (*elems));
}

void Array::freeObj(Object *obj)
{              	
	if (own_objects && obj) {
		obj->done();
		delete obj;
	}
}

void Array::realloc(int n)
{
	if (n == 0) n = 1;	/* alloc'ing 0 bytes not allowed */
	assert((uint)n >= ecount);
	elems = (Object**)::realloc(elems, sizeof (*elems) * n);
	acount = n;
	memset(elems+ecount, 0, (acount-ecount)*sizeof(*elems));
}

/**
 *	Prepare a write access
 *	@param i position of planned write access
 */
void Array::prepareWriteAccess(int i)
{
	if (i < 0) throw MsgException("data structure too big (Array)");
	uint n = calcNewBufferSize(acount, i+1);
	if (n > acount) realloc(n);
}

/*uint Array::count() const
{
	return ecount;
}*/

int Array::compareObjects(const Object *a, const Object *b) const
{
	return autoCompare(a, b);
}

void Array::forceSetByIdx(int i, Object *obj)
{
	// FIXME: sanity check, better idea ?
	if (i < 0) assert(0);
	prepareWriteAccess(i);
	freeObj(elems[i]);
	elems[i] = obj;
	notifyInsertOrSet(obj);
	if ((uint)i>=ecount) ecount = i+1;
}

Object *Array::get(ObjHandle h) const
{
	uint i = handleToNative(h);
	return validHandle(h) ? elems[i] : NULL;
}

uint Array::getObjIdx(ObjHandle h) const
{
	return invObjHandle ? invIdx : handleToNative(h);
}

ObjHandle Array::findByIdx(int i) const
{
	return validHandle(nativeToHandle(i)) ? nativeToHandle(i) : invObjHandle;
}

ObjHandle Array::findFirst() const
{
	return ecount ? nativeToHandle(0) : invObjHandle;
}

ObjHandle Array::findLast() const
{
	return ecount ? nativeToHandle(ecount-1) : invObjHandle;
}

ObjHandle Array::findNext(ObjHandle h) const
{
	if (!validHandle(h)) return findFirst();
	uint i = handleToNative(h);
	return (i<ecount-1) ? nativeToHandle(i+1) : invObjHandle;
}

ObjHandle Array::findPrev(ObjHandle h) const
{
	if (!validHandle(h)) return findLast();
	uint i = handleToNative(h);
	return (i>0) ? nativeToHandle(i-1) : invObjHandle;
}

ObjHandle Array::insert(Object *obj)
{
	prepareWriteAccess(ecount);
	elems[ecount++] = obj;
	notifyInsertOrSet(obj);
	return nativeToHandle(ecount-1);
}

bool Array::del(ObjHandle h)
{
	if (!validHandle(h)) return false;
	freeObj(remove(h));
	return true;
}

bool Array::moveTo(ObjHandle from, ObjHandle to)
{
	if (!validHandle(from)) return false;
	if (!validHandle(to)) return false;
	uint i = handleToNative(from);
	uint t = handleToNative(to);
	if (i == t) return true;
	Object *o = elems[i];
	if (i < t) {
		memmove(elems+i, elems+i+1, sizeof (*elems) * (t - i));
	} else {
		memmove(elems+t+1, elems+t, sizeof (*elems) * (i - t));
	}
	elems[t] = o;
	return true;
}

Object *Array::remove(ObjHandle h)
{
	if (!validHandle(h)) return NULL;
	uint i = handleToNative(h);
	Object *o = elems[i];
	if (i < ecount) memmove(elems+i, elems+i+1, sizeof (*elems) * (ecount - i - 1));
	ecount--;
	checkShrink();
	return o;
}

bool Array::set(ObjHandle h, Object *obj)
{
	if (!validHandle(h)) return false;
	uint i = handleToNative(h);
	freeObj(elems[i]);
	elems[i] = obj;
	notifyInsertOrSet(obj);
	return true;
}

bool Array::swap(ObjHandle h, ObjHandle i)
{
	if (!validHandle(h)) return false;
	if (!validHandle(i)) return false;
	uint H = handleToNative(h);
	uint I = handleToNative(i);
	Object *t = elems[H];
	elems[H] = elems[I];
	elems[I] = t;
	return true;
}

void Array::insertAt(ObjHandle h, Object *obj)
{
	if (!validHandle(h)) {
		insert(obj);
	} else {
		uint i = handleToNative(h);
		if (i < ecount) {
			prepareWriteAccess(ecount);
			memmove(elems+i+1, elems+i, sizeof (*elems) * (ecount - i));
			ecount++;
		} else {
			prepareWriteAccess(i);
			memset(elems+ecount, 0, sizeof (*elems) * (i - ecount));
			ecount = i+1;
		}
		elems[i] = obj;
		notifyInsertOrSet(obj);
	}
}

/*
 *	Stack
 */
Stack::Stack(bool own_objects) : Array(own_objects)
{
}

void	Stack::push(Object *obj)
{
	insert(obj);
}

Object *Stack::pop()
{
	return remove(findLast());
}

ObjectID Stack::getObjectID() const
{
	return OBJID_STACK;
}

/*
 *	SLinkedList
 */
SLinkedList::SLinkedList(bool oo)
{
	own_objects = oo;
	ecount = 0;
	first = last = NULL;
}

SLinkedList::~SLinkedList()
{
	delAll();
}

void SLinkedList::delAll()
{
	SLinkedListNode *n = first, *m;
	while (n) {
		m = n->next;
		freeObj(n->obj);
		deleteNode(n);
		n = m;
	}
	ecount = 0;
	first = last = NULL;
}

SLinkedListNode *SLinkedList::allocNode() const
{
	return new SLinkedListNode;
}

void SLinkedList::deleteNode(SLinkedListNode *node) const
{
	delete node;
}

void SLinkedList::freeObj(Object *obj) const
{
	if (own_objects && obj) {
		obj->done();
		delete obj;
	}
}

SLinkedList *SLinkedList::clone() const
{
	SLinkedList *l = new SLinkedList(own_objects);
	SLinkedListNode *n = first, *m;
	while (n) {
		m = n->next;
		Object *o = m->obj;
		if (own_objects) o = o->clone();
		l->insert(o);
		n = m;
	}
	return l;
}

void SLinkedList::load(ObjectStream &s)
{
	own_objects = true;
	first = last = NULL;

	ecount = 0;
	int ecount;
	GET_INT32D(s, ecount);
	if (ecount) {
		GET_INT32X(s, hom_objid);
		for (int i=0; i < ecount; i++) {
			Object *obj = s.getObjectInternal("element", hom_objid);
			insert(obj);
		}
	} else {
		hom_objid = OBJID_TEMP;
	}
}

ObjectID SLinkedList::getObjectID() const
{
	return OBJID_SLINKED_LIST;
}

void SLinkedList::store(ObjectStream &s) const
{
	PUT_INT32D(s, ecount);
	if (ecount) {
		putIDComment(s, hom_objid);
		PUT_INT32X(s, hom_objid);

		ObjHandle h = findFirst();
		assert(h == invObjHandle || hom_objid != OBJID_TEMP);