path: root/other/burneye2/ia32/ia32-function.c

/* ia32-function.c - ia32 function abstraction layer
 *
 * by scut
 */

#include <asm/unistd.h>

#include <stdlib.h>
#include <assert.h>
#include <string.h>

#include <common.h>
#include <ia32-debug.h>
#include <ia32-function.h>


/*** static prototypes
 */
static void
ia32_func_copy (ia32_function *target, ia32_function *source, char *name);

static ia32_function **
ia32_func_treeplain_fixreloc (ia32_function *func, elf_reloc_list *rel,
	ia32_function **flist, unsigned int flist_count,
	unsigned int *nfcount);

static ia32_bblock **
ia32_func_br_sp_list_2 (ia32_bblock **btl, unsigned int btl_len,
	ia32_function *func, unsigned int *brl_len,
	ia32_bblock *source, ia32_bblock *dest);

static ia32_bblock *
ia32_func_br_sp_list_3 (ia32_bblock **brl, unsigned int brl_len,
	unsigned int idx, int *sparr);

static void
ia32_func_br_sp_2 (ia32_bblock **brl, unsigned int brl_length,
	unsigned int brl_cur, int *patharray);

static int
ia32_func_breakup_2 (ia32_function *func, ia32_bblock *root,
	ia32_bblock *this, elf_reloc_list *rel_code, elf_reloc_list *rel_rodata,
	ia32_bblock **all, unsigned int all_count);

static void
ia32_graphviz_func_out_2 (FILE *fp, ia32_function **flist,
	unsigned int flist_count, int *flist_consider,
	elf_reloc_list *reloc_text);

static char *
ia32_graphviz_func_out_extern (FILE *fp, ia32_function *func,
	ia32_xref *xr, elf_reloc_list *reloc_text);

static void
ia32_graphviz_func_out_intern (FILE *fp, ia32_function *func, ia32_xref *xr,
	ia32_function **flist, unsigned int flist_count,
	int *flist_consider);

static int
ia32_func_switchtable_is (ia32_instruction *inst);

#ifdef	DUPE_DEBUG
void dupe_alloc (unsigned int max_addr);
void dupe_free (void);
void dupe_check (unsigned int addr);

/* global enable flag. can be used to selectivly drop certain sections
 */
int		dupe_check_enabled = 0;
unsigned int *	addr_arr = NULL;
unsigned int	addr_max = 0;
unsigned int	addr_ac = 1;	/* sequential access counter */
#endif

int	ia32_graphviz_align_undefined = 0;


extern char *	ia32_regs_wide[];

/*** implementation
 */

ia32_xref *
ia32_xref_new (void)
{
	return (xcalloc (1, sizeof (ia32_xref)));
}


ia32_function *
ia32_func_new (void)
{
	return (xcalloc (1, sizeof (ia32_function)));
}


ia32_xref *
ia32_func_xref_add (ia32_function *func, int totype,
	unsigned int at, unsigned int addend, unsigned int to,
	ia32_function *called, Elf32_Rel *rel, int inter_section)
{
	unsigned int	n;
	ia32_xref *	xref;


	ia32_debug (IA32_DEBUG, "ia32_func_xref_add: from 0x%08x to 0x%08x, "
		"type %d\n", at + addend, to, totype);
	/*if (to > 0x08000000)
		ia32_confirm ();*/

	for (n = 0 ; n < func->func_xref_count ; ++n) {
		if ((func->func_xref[n]->from + func->func_xref[n]->addend) ==
			(at + addend))
		{
			ia32_debug (IA32_WARNING,
				"ia32_func_xref_add: double xref at 0x%08x\n",
				to);
		}
	}

	xref = ia32_xref_new ();
	if (rel != NULL) {
		memcpy (&xref->orig, rel, sizeof (Elf32_Rel));
		xref->original_relocation = 1;
	}

	xref->from = at;
	xref->addend = addend;
	xref->to = to;
	xref->to_type = totype;
	xref->to_data = called;
	xref->inter_section = inter_section;

	func->func_xref_count += 1;
	func->func_xref = xrealloc (func->func_xref, func->func_xref_count *
		sizeof (ia32_xref *));
	func->func_xref[func->func_xref_count - 1] = xref;

	return (xref);
}


ia32_xref *
ia32_func_xref_findfrom (ia32_function *func, unsigned int vaddr_from)
{
	unsigned int	xrn;


	for (xrn = 0 ; xrn < func->func_xref_count ; ++xrn) {
		if (func->func_xref[xrn]->from == vaddr_from)
			return (func->func_xref[xrn]);
	}

	return (NULL);
}


unsigned int
ia32_func_xref_count (ia32_function **flist, unsigned int flist_count,
	int xref_type)
{
	unsigned int	fln,
			xrn,
			xref_count = 0;


	for (fln = 0 ; fln < flist_count ; ++fln) {
		for (xrn = 0 ; xrn < flist[fln]->func_xref_count ; ++xrn) {
			if (flist[fln]->func_xref[xrn]->to_type == xref_type)
				xref_count += 1;
		}
	}

	return (xref_count);
}


ia32_bblock *
ia32_func_find_bblock_byrelofs (ia32_function *func, unsigned int relofs)
{
	unsigned int	n;
	unsigned int	brall_count;
	ia32_bblock **	brall;
	ia32_bblock *	br;


	brall = ia32_br_get_all (func->br_root, &brall_count);

	for (n = 0 ; n < brall_count ; ++n) {
		if ((brall[n]->start - func->start) > relofs)
			continue;
		if ((brall[n]->end - func->start) <= relofs)
			continue;

		br = brall[n];
		free (brall);

		return (br);
	}

	free (brall);

	return (NULL);
}


void
ia32_func_list_walk (ia32_function **flist, unsigned int flist_count,
	void (* walk)(ia32_function *))
{
	unsigned int	n;


	for (n = 0 ; n < flist_count ; ++n)
		walk (flist[n]);

	return;
}


/* br_xref_fromfunc
 *
 * sort in all other relocations happening within function `func' into the
 * corresponding bblockes for easier/faster access on bblock level.
 *
 * return in any case
 */

void
ia32_func_oxref_fromfunc (ia32_function *func)
{
	unsigned int	n,
			dst;
	ia32_bblock *	brc;
	ia32_xref **	xrarr;
	ia32_xref *	xrcur;


	if (func->is_copy)
		return;

	/* sort in all other cross references into their corresponding bblockes
	 */
	for (n = 0 ; n < func->other_xref_count ; ++n) {
		assert (func->other_xref[n] != NULL);
		brc = ia32_func_find_bblock_byrelofs (func,
			func->other_xref[n]->from);

		if (brc == NULL) {
			ia32_debug (IA32_WARNING, "WARNING: "
				"(ia32_func_oxref_fromfunc) dangling "
				"relocation in %s:0x%05x, no bblock found\n",
				func->name, func->other_xref[n]->from);
			ia32_debug (IA32_WARNING, "  func: 0x%08x-0x%08x, "
				"no bblock found at 0x%08x\n",
				func->start, func->end,
				func->other_xref[n]->from + func->start);

			/*ia32_debug (IA32_DEBUG, "dumping bblock level\n");
			ia32_br_dump (func->name, func->br_root);
			ia32_debug (IA32_DEBUG, "end of dump\n");*/

			/* leave func->other_xref[n] to non-NULL, so it
			 * at least appears in compressed array below
			 */
			continue;
		}

		assert (brc != NULL);
		brc->other_xref_count += 1;
		brc->other_xref = xrealloc (brc->other_xref,
			brc->other_xref_count * sizeof (ia32_xref *));
		xrarr = brc->other_xref;

		xrcur = func->other_xref[n];
		xrcur->from = (func->start + xrcur->from) - brc->start;
		xrarr[brc->other_xref_count - 1] = xrcur;
		func->other_xref[n] = NULL;
	}

	/* compress now modified func->other_xref array
	 */
	for (dst = 0, n = 0 ; n < func->other_xref_count ; ++n) {
		if (func->other_xref[n] == NULL)
			continue;

		func->other_xref[dst] = func->other_xref[n];
		dst += 1;
	}

	func->other_xref_count = dst;

	/* FIXME: remove this pseudo-assertion once we've found this nasty bug.
	 */
	for (n = 0 ; n < func->other_xref_count ; ++n) {
		assert (func->other_xref[n] != NULL);
	}

	func->other_xref = xrealloc (func->other_xref, func->other_xref_count *
		sizeof (ia32_xref *));

	return;
}


unsigned char *
ia32_func_v2real (ia32_function *func, unsigned int vaddr)
{
	/* kludge: some libraries (e.g. dietlibc) have functions written in
	 *         assembly, that do not have a proper size description and
	 * have their end set to the start address (i.e. zero sized). to work
	 * around this problem, we explicitly check here, and skip all sanity
	 * checking.
	 */
	if (func->start == func->end)
		return (&func->mem[vaddr - func->start]);

	assert (vaddr >= func->start && vaddr < func->end);

	return (&func->mem[vaddr - func->start]);
}


unsigned int
ia32_func_r2virt (ia32_function *func, unsigned int real)
{
	unsigned char *	rptr = (unsigned char *) real;

	/* kludge: see ia32_func_v2real for description
	 */
	if (func->start == func->end)
		return (rptr - func->mem);

	assert (rptr >= func->mem &&
		rptr < (func->mem + (func->end - func->start)));

	return (rptr - func->mem);
}


ia32_function *
ia32_func_findcopy (ia32_function *func,
	ia32_function **flist, unsigned int flist_count)
{
	unsigned int	n;


	ia32_debug (IA32_DEBUG, "DEBUG: (ia32_func_findcopy) checking dupe "
		"between (0x%x-0x%x): %s\n",
		func->start, func->end, func->name);

	for (n = 0 ; n < flist_count ; ++n) {
		if (flist[n]->passed == 0 || flist[n] == func)
			continue;

		if (flist[n]->section_idx != func->section_idx)
			continue;

		if (flist[n]->start == func->start)
			return (flist[n]);

		/* there are situations when two functions are nested, so that
		 * they share the same trailing code. this happens for manually
		 * optimized functions, such as __syscall_error and
		 * __syscall_error_1 within the GNU C library. since they are
		 * exactly the same functions when they have the same starting
		 * address, in case they are nested, it must be a different
		 * address. as we sort the function list before any parsing
		 * operation, we can ensure we have already processed the outer
		 * function.
		 *
		 * the same odd case but reversed: overlapping but not enclosed
		 * functions.
		 *
		 * example: siglongjmp and longjmp within glibc, which both
		 *     have a damaged symbol table entry, something like this:
		 *
		 *    siglongjmp  [0x644b - 0x6491]
		 *    longjmp           [0x6467 - 0x64ad]
		 *
		 * what we do here is that we do not mark the function, but
		 * clear the array of accesses for the overlapping range.
		 * crude solution to an even more crude problem.
		 */
		if ((flist[n]->start > func->start && flist[n]->start < func->end) ||
			(flist[n]->end > func->start && flist[n]->end < func->end) ||
			(flist[n]->start < func->start && flist[n]->end >= func->end))
#if 0
		if ((flist[n]->start < func->start && flist[n]->end >= func->end) ||
			(flist[n]->start < func->start &&
			flist[n]->end <= func->end))
#endif
		{
			func->is_nested = 1;
			ia32_debug (IA32_WARNING, "WARNING: %s is nested\n",
				func->name);

			return (flist[n]);
		}
	}

	return (NULL);
}


/* FIXME: do a deep copy instead of shallowing things
 */
static void
ia32_func_copy (ia32_function *target, ia32_function *source, char *name)
{
	/* since we do not care about memory leaks anyway, just do a shallow
	 * copy and then replace the name
	 */
	memcpy (target, source, sizeof (ia32_function));
	target->name = name;
	target->is_copy = 1;

	return;
}


void
ia32_func_treeplain (ia32_function ***flist, unsigned int *flist_count,
	elf_reloc_list *rel_code, elf_reloc_list *rel_rodata,
	unsigned int code_idx)
{
	unsigned int	n;
	ia32_function *	func;

	ia32_function **	fnl;
	ia32_function *		fcopy;	/* symbolic copy of function */
	unsigned int		fnl_count;


	elf_function_list_sort (*flist, *flist_count);

	/* collect all bblockes of the function
	 */
reparse:
	while ((func = ia32_func_get_unpassed (*flist, *flist_count,
		code_idx)) != NULL)
	{
		ia32_debug (IA32_INFO, "INFO: (ia32_func_treeplain) "
			"breaking up: %s (0x%x-0x%x)\n", func->name,
			func->start, func->end);

		/* try to locate a symbolic copy. for example, in glibc, the
		 * __srandom function is aliased as srand, too. so, only
		 * decode one, and make the other function an alias. note that
		 * we cannot just drop one, because a relocation might refer
		 * to it using its symbol table entry
		 */
		fcopy = ia32_func_findcopy (func, *flist, *flist_count);
		if (fcopy != NULL && func->is_nested == 0) {
			ia32_func_copy (func, fcopy, func->name);
			func->passed = 1;
			ia32_debug (IA32_INFO, "INFO: (ia32_func_treeplain) "
				"\"%s\" is an alias of \"%s\"\n",
				func->name, fcopy->name);

			continue;
		} else if (fcopy != NULL && func->is_nested == 1) {
			ia32_debug (IA32_WARNING, "WARNING: "
				"(ia32_func_treeplain) %s is nested within "
				"%s, address checks disabled\n",
				func->name, fcopy->name);
		}

		func->br_root = ia32_func_breakup (func, rel_code, rel_rodata);
		ia32_debug (IA32_DEBUG, "\t=> %-10u xrefs\n",
			func->func_xref_count);
		func->passed = 1;
	}

	/* fix cross references
	 */
	for (n = 0 ; n < *flist_count ; ++n) {
		/* FIXME:SEC */
		if ((*flist)[n]->section_idx != code_idx)
			continue;

		if ((*flist)[n]->is_copy)
			continue;

		fnl = ia32_func_treeplain_fixreloc ((*flist)[n], rel_code,
			*flist, *flist_count, &fnl_count);

		if (fnl_count == 0)
			continue;

		*flist = xrealloc (*flist, (*flist_count + fnl_count) *
			sizeof (ia32_function *));
		memcpy (&((*flist)[*flist_count]), fnl,
			fnl_count * sizeof (ia32_function *));
		*flist_count += fnl_count;
		free (fnl);

		elf_function_list_sort (*flist, *flist_count);
		ia32_debug (IA32_INFO, "WARNING: (ia32_func_treeplain) "
			"reparsing functions\n");

		goto reparse;
	}

	return;
}


static ia32_function **
ia32_func_treeplain_fixreloc (ia32_function *func, elf_reloc_list *rel,
	ia32_function **flist, unsigned int flist_count,
	unsigned int *nfcount)
{
	unsigned int	xc,
			dst,
			rn;
	ia32_xref *	xref;
	elf_reloc *	reloc;
	unsigned int	rfunc_offset;	/* relative to function offset */

	ia32_function *		fnew;
	ia32_function **	new_flist = NULL;
	unsigned int		new_flist_count = 0,
				fwn;
	int			need_compress = 0;


	assert (func->is_copy == 0);

	for (xc = 0 ; xc < func->func_xref_count ; ++xc) {
		ia32_function *	coverfunc;


		xref = func->func_xref[xc];

		/* in case its refering an external function we cannot provide
		 * the ia32_function pointer, so set it to NULL, humm...
		 */
		if (xref->to_type == IA32_XREF_FUNCEXTERN) {
			ia32_debug (IA32_INFO, "extern function reference from "
				"0x%08x (%s)\n", xref->from, func->name);

			xref->to_data = NULL;

			continue;
		} else if (xref->to_type == IA32_XREF_FUNCTION) {
			/* FIXME:SEC */
			xref->to_data = ia32_func_list_find_bystart (flist,
				flist_count, xref->to);
		} else {
			assert (0);
		}

		if (xref->to_data != NULL)
			continue;

		/* heuristics: when the reference is to within the function it
		 *             is contained in, then we have some complicated
		 * redirection construct, most likely a complicated
		 * switchtable. see _IO_vfprintf code within glibc for an
		 * example:
		 *     0x0001bbc8 b827cd0100     mov     eax, 0x1cd27
		 *     0x0001bbcd e9a71b0000     jmp     0x1d779
		 *     ...
		 *     0x0001d779 ffe0           jmp     eax
		 *
		 * at the time we see the mov, we cannot be sure it is a
		 * function pointer or a in-function address. this is because
		 * the function could be processed in tracing mode, without
		 * known function boundaries. so step back at that time, and
		 * process such references now, after the boundaries are known.
		 *
		 * so, first test whether the reference is to within the own
		 * function. if it is, there are two cross references, added
		 * from ia32_func_breakup_2, one function xref, and one other
		 * xref. we need to remove the function cross reference, but
		 * conserve the other cross reference, but marking it as code
		 * related crossreference.
		 */
		if (ia32_trace_range (func->start, func->end, xref->to)) {
			ia32_xref *	oxf;
			ia32_xref *	carry_tmp;	/* temp. holder */

			ia32_debug (IA32_INFO, "INFO: internal function "
				"reference from %s to %s (0x%x)\n",
				func->name, func->name, xref->to);

			/* remove function crossreference. do the free later,
			 * as 'xref' still references to it.
			 */
			carry_tmp = func->func_xref[xc];
			func->func_xref[xc] = NULL;
			need_compress = 1;

			/* find the related other crossreference, and mark it
			 * as code related. note that other crossreference do
			 * not have addends, function xrefs do. so sum both.
			 */
			oxf = ia32_func_oxref_findfrom (func,
				xref->from + xref->addend);
			assert (oxf != NULL);
			oxf->other_subtype = IA32_XREF_O_FUNCTIONINTERN;

			free (carry_tmp);

			continue;
		}

		/* when the function is within another section, skip over the
		 * hidden function detection.
		 */
		if (xref->inter_section)
			continue;

		/* heuristics: some static functions used only locally within
		 *             an ELF object (eg. getopterror within getopt.c
		 * of dietlibc) have no symbol table entry at all. our idea to
		 * catch those functions also is to trace the calltree for
		 * calls to areas not covered by any function in the list.
		 * this is exactly the case we now check for.
		 */
		coverfunc = ia32_func_list_is_covered (xref->to,
			flist, flist_count);
		if (coverfunc != NULL) {
			ia32_debug (IA32_FATAL, "FATAL: "
				"(ia32_func_treeplain_fixreloc) function "
				"reference from %s:0x%x (0x%08x-0x%08x) "
				"to 0x%08x is covered/misaligned by another "
				"function: %s (0x%08x-0x%08x)\n",
				func->name, xref->from,
				func->start, func->end, xref->to,
				coverfunc->name, coverfunc->start,
				coverfunc->end);

			/*continue;*/
			exit (EXIT_FAILURE);
			/* FIXME: this should not happen, exit (EXIT_FAILURE);
			 */
		}

		ia32_debug (IA32_WARNING, "WARNING: "
			"(ia32_func_treeplain_fixreloc) hidden function "
			"detected due to %s:0x%x, entry point: 0x%08x\n",
			func->name, xref->from, xref->to);

		/* avoid duplicate functions within the new ones
		 */
		for (fwn = 0 ; fwn < new_flist_count ; ++fwn)
			if (new_flist[fwn]->start == xref->to)
				break;

		if (fwn < new_flist_count)
			continue;

		/* lets setup a new function definition for the hidden function
		 * FIXME: the fnew->mem stuff is rather ugly ;), as we assume
		 *        the function memory is all continuous
		 */
		fnew = ia32_func_new ();
		xref->to_data = fnew;	/* patch cross reference properly */
		fnew->name = "";
		fnew->start = fnew->end = xref->to;
		fnew->mem = func->mem - func->start + fnew->start;
		/* TODO: remove this once bugs are squashed */
		assert (fnew->mem >= (unsigned char *) 0x08000000 &&
			fnew->mem <= (unsigned char *) 0x50000000);

		fnew->section_idx = func->section_idx;

		new_flist_count += 1;
		new_flist = xrealloc (new_flist,
			new_flist_count * sizeof (ia32_function *));
		new_flist[new_flist_count - 1] = fnew;

		ia32_debug (IA32_DEBUG, "  ==> scheduled for the tracer\n");
	}

	/* compress func_xref array by removing any NULL entries
	 */
	if (need_compress) {
		for (dst = 0, xc = 0 ; xc < func->func_xref_count ; ++xc) {
			if (func->func_xref[xc] == NULL)
				continue;

			func->func_xref[dst] = func->func_xref[xc];
			dst += 1;
		}

		func->func_xref_count = dst;
		func->func_xref = xrealloc (func->func_xref,
			func->func_xref_count * sizeof (func->func_xref[0]));

		assert (func->func_xref_count == 0 || func->func_xref != NULL);
	}

#if 0
	/* OLD, obsolete version. remove soon when other proved correct.
	 * the new version is order-preserving and simpler and easier to
	 * understand
	 */
	if (need_compress) {
		for (xc = 0 ; xc < func->func_xref_count ; ++xc) {
			if (func->func_xref[xc] != NULL)
				continue;

			/* as its unsorted, take it the easy way
			 */
			func->func_xref[xc] =
				func->func_xref[func->func_xref_count - 1];
			func->func_xref_count -= 1;
			--xc;
		}

		func->func_xref = realloc (func->func_xref,
			func->func_xref_count * sizeof (func->func_xref[0]));

		assert (func->func_xref_count == 0 || func->func_xref != NULL);
	}
#endif

	/* now add the non-directly-control flow function cross references.
	 * for example code like this:
	 *      push   function
	 *      call   otherfunc
	 * then a reloc will be emitted by the linker that will insert the
	 * address of function at the correct place. since we do overlays of
	 * basic blocks, we have to insert the address in runtime and hence
	 * need this info.
	 */
	for (xc = 0 ; xc < rel->reloc_count ; ++xc) {
		reloc = rel->reloc[xc];

		if (reloc->offset_rel < func->start ||
			reloc->offset_rel >= func->end)
			continue;

		/* the crossreferences always refer relative to the function
		 * start
		 */
		rfunc_offset = reloc->offset_rel - func->start;

		/* check whether we already have this xref in the function
		 * references
		 */
		for (rn = 0 ; rn < func->func_xref_count ; ++rn) {
			if ((func->func_xref[rn]->from +
				func->func_xref[rn]->addend) == rfunc_offset)
			{
				break;
			}
		}

		if (rn < func->func_xref_count)
			continue;

		/* now we've found a relocation that is happening within the
		 * function body. we add it, since it is currently missing (it
		 * was not mentioned by any control flow instruction from
		 * within the functions code)
		 */
		ia32_debug (IA32_DEBUG, "DEBUG: _oxref_add "
			"(\"%s\", 0x%08x, 0x%08x)\n", func->name,
			rfunc_offset, (unsigned int) reloc);
		ia32_func_oxref_add (func, rfunc_offset, reloc);
	}

	*nfcount = new_flist_count;

	return (new_flist);
}


ia32_function *
ia32_func_list_is_covered (unsigned int vaddr, ia32_function **flist,
	unsigned int flist_count)
{
	unsigned int	n;


	for (n = 0 ; n < flist_count ; ++n) {
		if (flist[n]->is_copy)
			continue;

		if (vaddr >= flist[n]->start && vaddr < flist[n]->end)
			return (flist[n]);
	}

	return (NULL);
}


/* duplicate code, doh!
 */
ia32_xref *
ia32_func_oxref_findfrom (ia32_function *func, unsigned int vaddr_from)
{
	unsigned int	xrn;


	for (xrn = 0 ; xrn < func->other_xref_count ; ++xrn) {
		if (func->other_xref[xrn]->from == vaddr_from)
			return (func->other_xref[xrn]);
	}

	return (NULL);
}


void
ia32_func_oxref_add (ia32_function *func, unsigned int relofs, elf_reloc *rel)
{
	ia32_xref *	xref = ia32_xref_new ();
	unsigned int	wn;


	/* check for duplicates. this is necessary because _oxref_add may be
	 * called multiple times on the same relocation entry at multiple runs
	 * of ia32_func_treeplain_fixreloc.
	 */
	for (wn = 0 ; wn < func->other_xref_count ; ++wn) {
		if (func->other_xref[wn]->from == relofs) {
			ia32_debug (IA32_DEBUG, "DEBUG: equal (%d): in %s: "
				"0x%08x\n", wn, func->name, relofs);

			return;
		}
	}

	memcpy (&xref->orig, &rel->orig, sizeof (Elf32_Rel));

	/* no addend for other cross references
	 */
	xref->from = relofs;
	xref->addend = 0;
	xref->to_type = IA32_XREF_OTHER;
	xref->to_data = (void *) rel;
	assert (rel != NULL);
	xref->rel_addend = rel->addend;

	/* we once had the addend directly read out of memory. nowadays, we
	 * copy it from a once-read rel structure, as the original code may be
	 * properly relocated already. old behaviour was:
	 *
	 * xref->rel_addend = *((unsigned int *) &func->mem[relofs]);
	 */

	func->other_xref_count += 1;
	func->other_xref = xrealloc (func->other_xref, func->other_xref_count *
		sizeof (ia32_xref *));
	func->other_xref[func->other_xref_count - 1] = xref;

	return;
}


ia32_function *
ia32_func_get_unpassed (ia32_function **flist, unsigned int flist_count,
	unsigned int sidx)
{
	unsigned int	n;


	for (n = 0 ; n < flist_count ; ++n)
		if ((sidx == 0 || flist[n]->section_idx == sidx) &&
			flist[n]->passed == 0)
		{
			return (flist[n]);
		}

	return (NULL);
}


ia32_bblock *
ia32_func_br_end (ia32_function *func)
{
	int		n;
	ia32_bblock *	br_end;
	ia32_bblock **	brl;


	brl = ia32_br_get_all (func->br_root, (unsigned int *) &n);

	for (n = n - 1 ; n >= 0 ; --n) {
		if (brl[n]->endtype == BR_END_RET ||
			brl[n]->endtype == BR_END_CTRL_SYSCALL_END)
		{
			break;
		}
	}

	assert (n >= 0);
	br_end = brl[n];
	free (brl);

	return (br_end);
}


ia32_bblock **
ia32_func_br_mustexec (ia32_function *func, unsigned int *br_count)
{
	unsigned int	n,
			bn;
	ia32_bblock *	br_return;

	ia32_bblock **	br_all;
	unsigned int	br_all_count;

	ia32_bblock **	brl_sp;
	unsigned int	brl_sp_count;

	ia32_bblock **	brl_must = NULL;
	unsigned int	brl_must_count = 0;


	/* 1. bblockes that must be executed on every functions run have to lie
	 * on the shortest path
	 */
	br_return = ia32_func_br_end (func);
	brl_sp = ia32_func_br_sp_list (func, &brl_sp_count,
		func->br_root, br_return);
	assert (brl_sp_count > 0);

	/* the startnode must lie in the list for sure
	 */
	brl_must_count += 1;
	brl_must = xrealloc (brl_must, brl_must_count * sizeof (ia32_bblock));
	brl_must[brl_must_count - 1] = func->br_root;

	/* 2. for the nodes that lie on the shortest path - except the start
	 * and end node, there must be no path around them, else they do not
	 * belong to the must-exec nodes
	 */
	br_all = ia32_br_get_all (func->br_root, &br_all_count);

	for (n = 0 ; n < brl_sp_count ; ++n) {
		ia32_bblock *	br_temp;
		ia32_bblock **	sp_temp;


		/* ignore start and end, they must be executed anytime
		 */
		if (brl_sp[n] == func->br_root || brl_sp[n] == br_return)
			continue;

		/* temporarily remove bblock from the "all bblockes" list,
		 * then check if there is a path now, with the bblock removed
		 */
		for (bn = 0 ; bn < br_all_count ; ++bn)
			if (brl_sp[n] == br_all[bn])
				break;
		assert (bn < br_all_count);

		br_temp = br_all[bn];
/*		assert ((br_all_count - bn - 1) > 0);*/

		br_all_count -= 1;
		memmove (&br_all[bn], &br_all[bn + 1], (br_all_count - n) *
			sizeof (ia32_bblock *));

		/* check whether there is a path
		 */
		sp_temp = ia32_func_br_sp_list_2 (br_all, br_all_count, func,
			NULL, func->br_root, br_return);

		if (sp_temp != NULL)
			free (sp_temp);

		/* no path => the bblock must be travelled in any possible case
		 */
		if (sp_temp == NULL) {
			brl_must_count += 1;
			brl_must = xrealloc (brl_must,
				brl_must_count * sizeof (ia32_bblock));
			brl_must[brl_must_count - 1] = br_temp;
		}

		/* fixup the bblock array by inserting the removed bblock again
		 */
		memmove (&br_all[bn + 1], &br_all[bn], (br_all_count - n) *
			sizeof (ia32_bblock *));
		br_all[bn] = br_temp;
		br_all_count += 1;
	}

	free (brl_sp);
	free (br_all);

	/* the endnode also lies always in the list, in case it is not
	 * identical with the start node
	 */
	if (br_return != func->br_root) {
		brl_must_count += 1;
		brl_must = xrealloc (brl_must, brl_must_count *
			sizeof (ia32_bblock));
		brl_must[brl_must_count - 1] = br_return;
	}

	*br_count = brl_must_count;

	return (brl_must);
}


ia32_bblock **
ia32_func_br_sp_list (ia32_function *func, unsigned int *brl_len,
	ia32_bblock *source, ia32_bblock *dest)
{
	ia32_bblock **	btl;
	unsigned int	btl_len;
	ia32_bblock **	br_ret;

	btl = ia32_br_get_all (func->br_root, &btl_len);
	br_ret = ia32_func_br_sp_list_2 (btl, btl_len, func, brl_len,
		source, dest);

	free (btl);

	return (br_ret);
}


static ia32_bblock **
ia32_func_br_sp_list_2 (ia32_bblock **btl, unsigned int btl_len,
	ia32_function *func, unsigned int *brl_len,
	ia32_bblock *source, ia32_bblock *dest)
{
	unsigned int	source_idx,
			dest_idx;
	int *		sp_arr;

	ia32_bblock **	sp_bra = NULL;
	unsigned int	sp_idx;
	unsigned int	brl_len_dummy;


	if (btl_len == 0)
		return (NULL);

	if (brl_len == NULL)
		brl_len = &brl_len_dummy;

	source_idx = ia32_brl_find (btl, btl_len, source);
	dest_idx = ia32_brl_find (btl, btl_len, dest);
	assert (source_idx != -1 && dest_idx != -1);

	sp_arr = xcalloc (btl_len, sizeof (int));
	ia32_func_br_sp (btl, btl_len, source_idx, sp_arr);

	/* ensure there is a path from source to dest, else bail out
	 */
	if (sp_arr[dest_idx] == -1)
		goto bail;

	sp_bra = xcalloc (btl_len, sizeof (ia32_bblock *));
	sp_idx = btl_len - 1;
	sp_bra[sp_idx] = dest;

	while (sp_bra[sp_idx] != source) {
		sp_idx -= 1;

		sp_bra[sp_idx] = ia32_func_br_sp_list_3 (btl, btl_len,
			dest_idx, sp_arr);

		dest_idx = ia32_brl_find (btl, btl_len, sp_bra[sp_idx]);
		assert (dest_idx != -1);
	}

	*brl_len = btl_len - sp_idx;
	memmove (&sp_bra[0], &sp_bra[sp_idx], *brl_len *
		sizeof (ia32_bblock *));
	sp_bra = xrealloc (sp_bra, *brl_len * sizeof (ia32_bblock *));

bail:
	free (sp_arr);

	return (sp_bra);
}


static ia32_bblock *
ia32_func_br_sp_list_3 (ia32_bblock **brl, unsigned int brl_len,
	unsigned int idx, int *sparr)
{
	unsigned int	n,
			bn;


	for (n = 0 ; n < brl_len ; ++n) {
		if (n == idx)
			continue;

		if ((sparr[n] + 1) != sparr[idx])
	      		continue;

		/* now we have a possible node with a correct stepcount, check
		 * whether our node is a subnode of it
		 */
		for (bn = 0 ; bn < brl[n]->endbr_count ; ++bn)
			if (brl[n]->endbr[bn] == brl[idx])
				return (brl[n]);
	}

	assert (n < brl_len);

	return (NULL);
}


void
ia32_func_br_sp (ia32_bblock **brl, unsigned int brl_length,
	unsigned int brl_source, int *patharray)
{
	unsigned int	n;


	/* use a recursing bellman-ford algorithm with constant edge weight of
	 * one. recursive due to adjascent vertex restriction in original
	 * bellman-ford.
	 *
	 * 1. initialization, -1 denotes infinity
	 */
	for (n = 0 ; n < brl_length ; ++n)
		patharray[n] = -1;
	patharray[brl_source] = 0;

	ia32_func_br_sp_2 (brl, brl_length, brl_source, patharray);
}


static void
ia32_func_br_sp_2 (ia32_bblock **brl, unsigned int brl_length,
	unsigned int brl_cur, int *patharray)
{
	unsigned int	n,
			bidx;
	ia32_bblock *	br = brl[brl_cur];


	for (n = 0 ; n < br->endbr_count ; ++n) {
		bidx = ia32_brl_find (brl, brl_length, br->endbr[n]);
		if (bidx == -1 || bidx == brl_cur)
			continue;

		/* 2. relax for each subnode, then recurse
		 */
		if (patharray[bidx] == -1 ||
			patharray[bidx] > (patharray[brl_cur] + 1))
		{
			ia32_debug (IA32_DEBUG, "relax: 0x%08x from "
				"%2d to %2d\n", brl[bidx]->start,
				patharray[bidx], patharray[brl_cur] + 1);

			patharray[bidx] = patharray[brl_cur] + 1;

			ia32_func_br_sp_2 (brl, brl_length,
				bidx, patharray);
		}
	}
}


static int
ia32_func_switchtable_is (ia32_instruction *inst)
{
	if (OD_TEST (inst->opc.used, OP_CONTROL) == 0 ||
		OD_TEST (inst->opc.used, OP_JUMP) == 0)
	{
		return (0);
	}

	if (OD_TEST (inst->opc.used, OP_TARGET) == 0)
		return (0);

	/* it may be somewhat dangerous, but we treat function pointers as
	 * special cases of one-element switch tables :-)
	 */
	if (inst->opc.target_type == OP_TYPE_REG)
		return (1);

	if (inst->opc.target_type != OP_TYPE_MEM)
		return (0);

	/* we either need a table start through a register or through a
	 * displacement. if both are lost, we are lost.
	 */
	if (inst->opc.base == 0 && OD_TEST (inst->opc.used, OP_DISPLACE) == 0)
		return (0);

	if (OD_TEST (inst->opc.used, OP_SIB))
		return (1);

	return (0);
}


ia32_bblock *
ia32_func_breakup (ia32_function *func, elf_reloc_list *rel_code,
	elf_reloc_list *rel_rodata)
{
	ia32_bblock *		root;
	ia32_bblock *		cur = ia32_br_new ();

	/* since the calls to ia32_br_get_all_2 are very expensive (uncached
	 * they take up >95% of program execution time), we cache the lookups
	 * here
	 */
	ia32_bblock **		all = NULL;
	unsigned int		all_count;
	int			cache_isdirty = 1;

	/* functions with zero size length are almost always the result of
	 * manual mangling with function definitions (when writing functions
	 * in assembly). hence, when we stumble over such a function, enable
	 * the tracer mode, in which we try to identify the function
	 * boundaries much like IDA does (by tracing the control flow)
	 *
	 * XXX: note that complex compiler constructs, such as switchtables,
	 *      require the assistance of function-length information still.
	 * it is technically possible to decode such constructs, too, but its
	 * not worth the effort here. to add such decoding, uncomment the
	 * line below and debug what breaks:
	 *
	 * func->end = func->start;
	 */
	if (func->start == func->end) {
		ia32_debug (IA32_WARNING, "WARNING: (ia32_func_breakup) "
			"broken function bounds (zero-sized), using tracer\n");

		func->traced_bounds = 1;
	} else
		func->traced_bounds = 0;

	cur->start = func->start;
	root = cur;

	/* work until all bblockes are passed
	 */
	do {
		if (cache_isdirty) {
			if (all != NULL)
				free (all);

			all = ia32_br_get_all (root, &all_count);
		}

		cur = ia32_br_get_unpassed (all, all_count);
		if (cur == NULL)
			break;

		if (func->end != func->start && cur->start == func->end &&
			func->is_symdamaged == 0 && func->traced_bounds == 0)
		{
			ia32_debug (IA32_WARNING, "WARNING: "
				"(ia32_func_breakup) function \"%s\" ends "
				"abnormaly\n", func->name);

			func->is_abnormal_end = 1;
		}
#ifdef	DUPE_DEBUG
		else if (func->is_nested == 0) {
			dupe_check (cur->start);
		}
#endif
		cache_isdirty = ia32_func_breakup_2 (func, root, cur,
			rel_code, rel_rodata, all, all_count);

		if (func->traced_bounds == 0 && cur->end > func->end) {
			ia32_debug (IA32_WARNING, "WARNING: invalid function "
				"symbol table entry for \"%s\" (tb = %d), "
				"fixing (end: 0x%x to 0x%x)\n",
				func->name, func->traced_bounds,
				func->end, cur->end);
			/*ia32_confirm ();*/

			func->end = cur->end;
			func->is_symdamaged = func->traced_bounds = 1;
		}
	} while (1);

	if (all != NULL) {
		free (all);
		all = NULL;
	}


	if (func->traced_bounds) {
		ia32_bblock *		br;
		ia32_bblock **		br_all;
		unsigned int		br_all_count,
					fend;

		br_all = ia32_br_get_all (root, &br_all_count);
		for (fend = 0 ; br_all_count > 0 ; --br_all_count) {
			br = br_all[br_all_count - 1];
			if (br->end > fend)
				fend = br->end;
		}
		free (br_all);

		func->end = fend;
		ia32_debug (IA32_INFO, "  traced function boundaries: "
			"0x%x-0x%x\n", func->start, func->end);
	}

	return (root);
}


/* this is the heart of the control flow analyzation engine
 */

static int
ia32_func_breakup_2 (ia32_function *func, ia32_bblock *root,
	ia32_bblock *this, elf_reloc_list *rel_code, elf_reloc_list *rel_rodata,
	ia32_bblock **all, unsigned int all_count)
{
	int			tb;	/* tracing bounds */
	ia32_instruction *	inst,	/* helper pointer for inst_s */
				inst_s;	/* instruction structure */
		/* temporary working bblockes */
	ia32_bblock *		work1;	/* temporary work bblock */
	ia32_bblock *		work2;	/* temporary work bblock */
	unsigned int		vaddr;	/* current virtual address */
	unsigned int		destaddr = 0x0,	/* control flow destination */
				rdaddr;	/* relocation destaddr */
	unsigned char *		cur;	/* memory position of vaddr */
	unsigned int		ilen;	/* instruction length */

	/* flags for a single control flow change */
	int			intra;	/* is within current function? */
	int			cond;	/* is condition-based? */
	int			resume;	/* will the call/jmp will resume? */
	unsigned int		swmask;	/* switchmask */
	int			duesplit;
	int			c_volatile,
				switch_fail;
	int			br_splitted,
				rval = 0;	/* return value, helpervalue */
	char			inst_str[64];	/* string representation */



	tb = func->traced_bounds;
	vaddr = this->end = this->start;
	this->passed = 1;
	ilen = 0;

	while (tb || vaddr < func->end) {
	/*	ia32_br_dump (func->name, root); */
		/* relocate and decode current instruction
		 */
		cur = &func->mem[vaddr - func->start];
		inst = ia32_decode_instruction (cur, &inst_s);

		if (inst == NULL) {
			ia32_debug (IA32_WARNING,
				"WARNING: (ia32_func_breakup_2) failed to "
				"decode instruction at 0x%08x, in function "
				"\"%s\"\n",
				vaddr, func->name == NULL ? "__unknown" :
				func->name);
			this->endtype = BR_END_INVALID;

			return (rval);
		}

		/* optionally dump instruction being analyzed (when verbosity
		 * is greater-equal to DEBUG).
		 */
		ia32_sprint (inst, inst_str, sizeof (inst_str));
		ia32_debug (IA32_DEBUG, "\t\t(0x%08x) 0x%08x: %s\n",
			(unsigned int) cur, vaddr, inst_str);

		if (vaddr >= 0x17fef && vaddr <= 0x180a5)
			printf ("XXXSCUT\n");

		ilen = inst->length;

		this->end = vaddr;

		/* we have hit a control instruction, lets get its target, if
		 * possible.
		 */
		if (OD_TEST (inst->opc.used, OP_CONTROL))
			destaddr = ia32_trace_control (inst, cur, vaddr,
				&resume, &c_volatile);

		/* heuristics: there are function pointers passed as data that
		 *   are invisible in the symbol table (local static
		 *   functions). to catch those we rely on at least a generic
		 *   "relative-to-.text" symbol table entry. a good example
		 *   for such code can be found in dietlibc/libstdio/vfprintf.c
		 *   where "__fwrite" is passed to __vfprintf within a struct.
		 */
		if (strcmp (inst->opc.opcode->name, "mov") == 0 &&
			OD_TEST (inst->opc.used, OP_SOURCE | OP_TARGET |
				OP_IMMEDIATE) &&
			inst->opc.source_type == OP_TYPE_IMM &&
			inst->opc.source_width == IA32_WIDTH_WORD &&
			inst->opc.imm_size == IA32_WIDTH_WORD &&
			inst->opc.target_width == IA32_WIDTH_WORD)
		{
			elf_reloc *	rel_el;

			rel_el = elf_reloc_list_lookup (rel_code,
				vaddr + ia32_has_immediate (inst, NULL));

			/* this is the most important criterion in the
			 * heuristic (since any function is relocateable there
			 * have to be relocation entries for their offsets).
			 */
			if (rel_el == NULL)
				goto no_shadowed_fptr;

			assert (rel_el->sym != NULL);

			/* how to handle SHN_COMMON externs ?
			 * easy: we do not allow any common symbol, so
			 * we just bail out
			 */
			if (rel_el->sym->sent.st_shndx == SHN_COMMON) {
				ia32_debug (IA32_FATAL, "  0x%08x: relocation "
				"to \"common\" symbol %s\n", vaddr,
				rel_el->sym->name);

				assert (0);

				/* if you don't want to bail, go here */
				goto no_shadowed_fptr;
			}

			assert (rel_el->sym->sec != NULL);
			assert (rel_el->sym->sec->name != NULL);

			/* FIXME:SEC */
			if (strcmp (rel_el->sym->sec->name, ".text") != 0)
				goto no_shadowed_fptr;

			if (ELF32_R_TYPE (rel_el->orig.r_info) != R_386_32)
				goto no_shadowed_fptr;

			/* add new function cross reference (which will result
			 * in a new function being traced). the addend is the
			 * destination address
			 */
			ia32_func_xref_add (func, IA32_XREF_FUNCTION,
				vaddr - func->start,
				ia32_has_immediate (inst, NULL),
				rel_el->addend, NULL, &rel_el->orig, 0);

			ia32_func_oxref_add (func, vaddr - func->start +
				ia32_has_immediate (inst, NULL), rel_el);
		}
no_shadowed_fptr:

		if (tb == 0 && (vaddr + ilen) > func->end) {
			ia32_debug (IA32_WARNING, "WARNING: instruction (%d) "
				"in \"%s\" at 0x%x overlaps function end "
				"0x%x, tracing bounds\n",
				ilen, func->name, vaddr, func->end);

			/*ia32_confirm ();*/
			tb = func->traced_bounds = 1;

		/* even more complicated case: the basic block runs against
		 * the function end without a control flow instruction. that
		 * is, it executes beyond the function end. mostly as a result
		 * of fscked up symbol table entries.
		 * XXX: howto handle this?
		 */
		} else if (tb == 0 && (vaddr + ilen) == func->end &&
			OD_TEST (inst->opc.used, OP_CONTROL) == 0)
		{
			ia32_debug (IA32_WARNING, "WARNING: last basic block "
				"in \"%s\" at 0x%x runs into the function end "
				"0x%x\n", func->name, this->start, func->end);
			ia32_debug (IA32_WARNING, "         tracing bounds, "
				"but take care for possible code duplication\n");

			tb = func->traced_bounds = 1;
			/*ia32_confirm ();*/
		}

		if (OD_TEST (inst->opc.used, OP_CONTROL) == 0) {
			vaddr += ilen;

			work1 = ia32_br_find (root, vaddr, all, all_count,
				&br_splitted);

			if (work1 != NULL) {
				this->end = vaddr;
				this->endtype = BR_END_PASS;
				this->endbr = xcalloc (1, sizeof (ia32_bblock *));
				this->endbr[0] = work1;
				this->endbr_count = 1;

				return (br_splitted ? 1 : 0);
			}

			continue;
		}

		/* from now on, everything is a control flow instruction.
		 * the last instruction length is stored to be able to morph
		 * the last bblock instruction (jcc, call, ret, ..) without
		 * having to re-disassemble it
		 */
		this->last_ilen = ilen;

		/* try to detect whether the control flow leaves our function.
		 * for trace-bounds mode, we have to make a guess.
		 */
		intra = 0;
		if (tb && ia32_verbose (IA32_DEBUG))
			ia32_print (inst);

		if (destaddr != 0xffffffff && tb) {
			/* in case the control is within the instruction, its
			 * either a PIC or relocated entry and we decode it
			 * through the "within function" switchcase below.
			 */
			if (destaddr >= vaddr && destaddr <= vaddr + ilen)
				intra = 1;

			/* when its a "return" instruction, make it
			 * inter-function else only intra function instructions
			 * (cond, uncond jumps) are left, and we make it intra
			 * function
			 */
			if (ia32_trace_return_is (inst, cur))
				intra = 0;
			else
				intra = 1;

			if (destaddr < func->start)
				intra = 0;
		} else if (destaddr != 0xffffffff) {
			intra = ia32_trace_range (func->start, func->end,
				destaddr);

			/* special case (e.g. in glibc, "pause" function with
			 * its invalid symbol table entry): the call is right
			 * at the end of a non-traced bound function. happens
			 * only with invalid symbol table entries.
			 */
			if (intra == 0 && destaddr >= func->start &&
				destaddr <= (vaddr + ilen))
			{
				intra = 1;

				ia32_debug (IA32_WARNING, "WARNING: 0x%x in "
					"\"%s\": overhanging instruction\n",
					vaddr, func->name);
			}
		}

		cond = (OD_TEST (inst->opc.used, OP_COND)) ? 1 : 0;
#define	SW_INTRA	1
#define	SW_INTER	0
#define	SW_COND		2
#define	SW_UNCOND	0
#define	SW_RESUME	4
#define	SW_PASS		0
		swmask = (intra ? SW_INTRA : 0) | (cond ? SW_COND : 0) |
			(resume ? SW_RESUME : 0);

		this->end = vaddr + ilen;

		/* control flow instructions that cannot be predicted can be
		 * of two kinds:
		 *
		 *  - switch tables, which do not resume control and are
		 *    decoded by us
		 *  - function pointer calls, which do resume the control flow
		 */
		switch_fail = 0;

		if (c_volatile && resume == 0) {
			/* volatile jumps (switchtables or manual assembly)
			 */
			ia32_switchtable *	stab;
			int			selem;
			/* unsigned int		addr_sw;	*//* walker */


			this->endtype = BR_END_UNPREDICT;
			if (ia32_func_switchtable_is (inst) == 0) {
				ia32_debug (IA32_WARNING, "WARNING: "
					"(ia32_func_breakup_2) weird control "
					"flow at 0x%08x\n", vaddr);

				return (rval);
			}


			/* now we have to decode the switch table. the current
			 * bblock has to be terminated already, which we
			 * ensured above.
			 */
			ia32_debug (IA32_INFO, "  0x%08x: possible "
				"switch table\n", vaddr);

			stab = ia32_func_switchtable_decode (func, root, this,
				vaddr, inst);

			/* TODO: add && ia32_func_list_find_bystart
			 *         (..., vaddr + inst->length)
			 * XXX: if we failed to break up the switch table, try
			 *      as function pointer
			 */
			if (stab == NULL && inst->opc.target_type == OP_TYPE_REG) {
				switch_fail = 1;

				goto try_func_ptr;
			}

			/* TODO: is it necessary to process relocations for
			 *       stab->vaddr_loc here?
			 * FIXME: instead of always using rel_rodata, check
			 * where the relocation stems from and use the proper
			 * relocation table instead
			 */
			assert (stab != NULL);
			stab->mem_start = /*FIXME:RELOC rel_rodata->reloc_modify->data +*/
				(unsigned int *) stab->vaddr_start;

			/* build the bblock end
			 */
			this->endtype = BR_END_SWITCH;
			this->endbr = xcalloc (stab->entries,
				sizeof (ia32_bblock *));

			stab->reloc = rel_rodata;
			if (rel_rodata != NULL) {
				assert ((unsigned char *) stab->mem_start >=
					rel_rodata->reloc_modify->data);
				assert ((unsigned char *) stab->mem_start <
					(rel_rodata->reloc_modify->data +
					rel_rodata->reloc_modify->data_len));

				stab->vaddr_start = (unsigned int) stab->mem_start;
				stab->vaddr_start -=
					(unsigned int) rel_rodata->reloc_modify->data;
			} else
				stab->vaddr_start = 0x0;

			/*addr_sw = stab->vaddr_start;*/
			for (selem = 0 ; selem < stab->entries ; ++selem) {
				unsigned int	daddr,
						bbn;
#if 0
				elf_reloc *	rel_el;

				/* find the corresponding relocation entry
				 * for the switch table entry. then check for
				 * correct reloca type (R_386_32), and add the
				 * case to our internal struct
				 */
				rel_el = elf_reloc_list_lookup (rel_rodata,
					addr_sw);
				addr_sw += 4;

				/* FIXME: ugly heuristics. if we fail to obtain
				 *        a relocation entry, then our size
				 * guess of the table was wrong. lets refine.
				 */
				if (rel_el == NULL) {
					stab->entries = selem - 1;
					ia32_debug (IA32_INFO, "  refined to "
						"%u cases\n", stab->entries);
					continue;
				}
				assert (rel_el != NULL);

				assert (ELF32_R_TYPE (rel_el->orig.r_info) ==
					R_386_32);
				daddr = rel_el->sym->sent.st_value +
					rel_el->addend;
#endif
				daddr = stab->mem_start[selem];

				/* convert from memory to object file address,
				 * as we need to get the basic block
				 * addresses.
				 */
				daddr = daddr - (((unsigned int) func->mem) -
					func->start);

				ia32_debug (IA32_INFO, "    case %d ==> "
					"target: 0x%08x\n", selem, daddr);

				/* note that we rely on basic compiler sanity
				 * so that the switch will not reach into our
				 * current bblock.
				 * when we create a new bblock, mark return
				 * value
				 *
				 * first, try to find a basic block with the
				 * same destaddr within the already processed
				 * switch cases, then fall back on the
				 * function-level basic block search (_br_find)
				 */
				work1 = NULL;
				for (bbn = 0 ; bbn < selem ; ++bbn) {
					if (this->endbr[bbn]->start != daddr)
						continue;

					work1 = this->endbr[bbn];
					break;
				}

				br_splitted = 0;
				if (work1 == NULL)
					work1 = ia32_br_find (root, daddr,
						all, all_count, &br_splitted);

				if (br_splitted || work1 == NULL)
					rval = 1;

				if (work1 == NULL) {
					work1 = ia32_br_new ();
					work1->start = daddr;
				}
				this->endbr[selem] = work1;
			}

			this->endbr_count = stab->entries;
			this->switchtab = stab;

			return (rval);
		}

try_func_ptr:
		if (switch_fail || (c_volatile && resume)) {
			ia32_linux_interrupt *	intdef;

			/* volatile calls (function pointer calls or syscalls)
			 */
			assert (OD_TEST (inst->opc.used, OP_TARGET));

			intdef = ia32_linux_interrupt_decode (func, root,
				this, vaddr, inst);

			/* its a system call that does not resume, so setup an
			 * extra endtype of _END_CTRL_SYSCALL_END. does not return
			 * just means that it may jump elsewhere (like
			 * sigreturn), not that the program is terminated.
			 */
			if (intdef != NULL && intdef->resume == 0) {
				ia32_debug (IA32_WARNING, "WARNING: "
					"(ia32_func_breakup_2) non-returning "
					"system call 0x%x\n", intdef->syscall);

				this->interrupt = intdef;
				this->endtype = BR_END_CTRL_SYSCALL_END;

				return (rval);
			}
#if 1
			/* FIXME: linux centric code
			 */
			if (strcmp (inst->opc.opcode->name, "int") == 0 &&
				inst->opc.target_type == OP_TYPE_IMM &&
				inst->opc.imm_value == IA32_LINUX_SYSCALLINT)
			{
				ia32_debug (IA32_DEBUG, "DEBUG: 0x%x: "
					"generic linux system call\n", vaddr);

				work1 = ia32_br_find (root, vaddr + ilen,
					all, all_count, &br_splitted);

				if (br_splitted)
					rval = 1;

				this->endtype = BR_END_CTRL_SYSCALL;

				this->endbr = xcalloc (1,
					sizeof (ia32_bblock *));
				this->endbr[0] = work1;
				if (this->endbr[0] == NULL) {
					rval = 1;
					this->endbr[0] = ia32_br_new ();
					this->endbr[0]->start = vaddr + ilen;
				}
				this->endbr_count = 1;

				return (rval);
			}
#endif
			/* immediate target is another interrupt call
			 * normally. just go ahead
			 */
			if (inst->opc.target_type == OP_TYPE_IMM) {
				vaddr += ilen;

				work1 = ia32_br_find (root, vaddr,
					all, all_count, &br_splitted);
				if (work1 != NULL) {
					this->end = vaddr;
					this->endtype = BR_END_PASS;
					this->endbr = xcalloc (1,
						sizeof (ia32_bblock *));
					this->endbr[0] = work1;
					this->endbr_count = 1;

					return (br_splitted ? 1 : 0);
				}

				continue;
			}

			/* memory pointer call. (function pointer but stored
			 * in memory). hell, ia32 addressing modes are a mess.
			 * not every function pointer call is spilled through
			 * a register load and register call, but some are
			 * direct-memory calls. this is one, so decode it.
			 * example of such code: second basic block of
			 * __uselocale within glibc.
			 */
			if (inst->opc.target_type == OP_TYPE_MEMABS) {
				/* FIXME: keep this as warning because i am
				 * not yet sure how well this works
				 */
				ia32_debug (IA32_DEBUG, "DEBUG: (%s) 0x%x: "
					"memory indirect call found\n",
					func->name, vaddr);

				ia32_debug (IA32_DEBUG, "   0x%08x: volatile "
					"memory indirect \"%s\" instruction\n",
					vaddr, inst->opc.opcode->name);

				/* we are only interested in memory displaced
				 * calls
				 */
				if (strcmp (inst->opc.opcode->name,
					"call") != 0 ||
					ia32_has_displacement (inst, NULL) == 0)
				{
					assert (0);
				}

				work1 = ia32_br_find (root, vaddr + ilen,
					all, all_count, &br_splitted);

				if (br_splitted)
					rval = 1;

				this->endtype = BR_END_CALL_MEM;
				this->memabs_pos =
					ia32_has_displacement (inst, NULL);

				this->endbr = xcalloc (1,
					sizeof (ia32_bblock *));
				this->endbr[0] = work1;
				if (this->endbr[0] == NULL) {
					rval = 1;
					this->endbr[0] = ia32_br_new ();
					this->endbr[0]->start = vaddr + ilen;
				}
				this->endbr_count = 1;

				return (rval);
			}

			if (inst->opc.target_type == OP_TYPE_MEMREG) {
				ia32_debug (IA32_DEBUG, "DEBUG: 0x%08x: "
					"_MEMREG volatile call\n", vaddr);

				/* _MEMREG should implicit target_reg.
				 * displ_value is optional though.
				 */
				this->memreg_displ = 0;

#if 0
				/* this displacement should never be covered
				 * by a relocation entry.
				 */
				if (ia32_has_displacement (inst, NULL)) {
					elf_reloc *	rel_el;

					rel_el = elf_reloc_list_lookup
						(rel_code, vaddr +
						ia32_has_displacement
						(inst, NULL));

					if (rel_el != NULL) {
						ia32_debug (IA32_FATAL,
							"FATAL: 0x%08x: "
							"_MEMREG call covered "
							"by relocation\n",
							vaddr);

						assert (0);
						exit (EXIT_FAILURE);
					}

					this->memreg_displ = ia32_extend_signed
						(inst->opc.displ_value,
						inst->opc.displ_size);
				}
#endif
				this->memreg_displ = ia32_has_displacement (inst, NULL);
				this->memreg_callreg = inst->opc.target_reg;

				ia32_debug (IA32_DEBUG, "    [reg %d + 0x%08x]\n",
					this->memreg_callreg, this->memreg_displ);

				this->end = vaddr + ilen;
				work1 = ia32_br_find (root, vaddr + ilen,
					all, all_count, &br_splitted);

				if (br_splitted)
					rval = 1;

				this->endtype = BR_END_CALL_MEMREG;

				this->endbr = xcalloc (1,
					sizeof (ia32_bblock *));
				this->endbr[0] = work1;
				if (this->endbr[0] == NULL) {
					rval = 1;
					this->endbr[0] = ia32_br_new ();
					this->endbr[0]->start = vaddr + ilen;
				}
				this->endbr_count = 1;

				return (rval);
			}

			/* SIB addressed calls. the most complicated, but we
			 * just move the complexity to the loaders ;)
			 */
			if (inst->opc.target_type == OP_TYPE_MEM) {
				ia32_debug (IA32_DEBUG, "DEBUG: 0x%08x: SIB "
					"addressing call/jump\n", vaddr);

				assert (strcmp (inst->opc.opcode->name, "call") == 0);

				this->end = vaddr + ilen;
				work1 = ia32_br_find (root, vaddr + ilen,
					all, all_count, &br_splitted);

				if (br_splitted)
					rval = 1;

				this->endtype = BR_END_CALL_MEMSIB;

				this->endbr = xcalloc (1,
					sizeof (ia32_bblock *));
				this->endbr[0] = work1;
				if (this->endbr[0] == NULL) {
					rval = 1;
					this->endbr[0] = ia32_br_new ();
					this->endbr[0]->start = vaddr + ilen;
				}
				this->endbr_count = 1;

				this->memsib_scale = inst->opc.scale;
				this->memsib_index = inst->opc.index;
				this->memsib_indexreg = inst->opc.index_reg;
				this->memsib_base = inst->opc.base;
				this->memsib_basereg = inst->opc.base_reg;
				this->memsib_displpos =
					ia32_has_displacement (inst, NULL);

				return (rval);
			}

			/* the only target type thats left should be a simple
			 * register based jump/call. if its not, bail.
			 */
			if (inst->opc.target_type != OP_TYPE_REG) {
				ia32_debug (IA32_FATAL, "FATAL: 0x%08x: "
					"volatile, unhandled (sib?) call "
					"found, target type %d\n", vaddr,
					inst->opc.target_type);

				assert (0);
				exit (EXIT_FAILURE);
			}

			ia32_debug (IA32_DEBUG, "    0x%08x: volatile %s, "
				"register %s\n", vaddr,
				switch_fail ? "jump" : "call",
				ia32_regs_wide[inst->opc.target_reg]);

			this->end = vaddr + ilen;
			this->call_reg = inst->opc.target_reg;
			work1 = ia32_br_find (root, vaddr + ilen,
				all, all_count, &br_splitted);

			if (br_splitted)
				rval = 1;

			if (switch_fail) {
				this->endtype = BR_END_FUNCPTR_JUMP;
				this->endbr_count = 0;

				return (rval);
			}

			this->endtype = BR_END_FUNCPTR_CALL;
			this->endbr = xcalloc (1, sizeof (ia32_bblock *));

			this->endbr[0] = work1;
			if (this->endbr[0] == NULL) {
				rval = 1;
				this->endbr[0] = ia32_br_new ();
				this->endbr[0]->start = vaddr + ilen;
			}
			this->endbr_count = 1;

			return (rval);
		}

		switch (swmask) {
		/* inter function references
		 */
		/* bblock terminate, "ret" return or a "hlt" instruction, but
		 * we treat them much the same way.
		 */
		case (SW_INTER | SW_UNCOND | SW_PASS):
			this->endtype = BR_END_RET;

			return (rval);

		/* bblock ignore, conditional jump inter-function
		 */
		case (SW_INTER | SW_COND | SW_PASS):
			/* the most common case for this to happen is to share
			 * the same trailing function code (including ret) for
			 * a number of functions (e.g. strcoll in glibc). the
			 * problem with this type of jump is that the code it
			 * jumps to may lead to undiscovered functions which
			 * we have to analyze later. therefore, add a function
			 * reference and the special _END_IF_INTER type.
			 */
			assert (ia32_has_displacement (inst, NULL));
			ia32_func_xref_add (func, IA32_XREF_FUNCTION,
				vaddr - func->start,
				ia32_has_displacement (inst, NULL),
				destaddr, NULL, NULL, 0);

			work1 = ia32_br_find (root, vaddr + ilen,
				all, all_count, &br_splitted);

			if (br_splitted)
				rval = 1;

			this->endtype = BR_END_IF_INTER;
			this->cond = inst->opc.cond;
			this->endbr_count = 1;
			this->endbr = xcalloc (1, sizeof (ia32_bblock *));
			this->endbr[0] = work1;

			if (this->endbr[0] == NULL) {
				rval = 1;
				this->endbr[0] = ia32_br_new ();
				this->endbr[0]->start = vaddr + ilen;
			}

			return (rval);
			break;

		/* bblock call, external function reference
		 * add the special passing bblock type "call".
		 */
		case (SW_INTER | SW_UNCOND | SW_RESUME):
		case (SW_INTER | SW_COND | SW_RESUME):
			/* FIXME: calc correct addend (not just 1)
			 */
			ia32_func_xref_add (func, IA32_XREF_FUNCTION,
				vaddr - func->start, 1,
				destaddr, NULL, NULL, 0);

			this->end = vaddr + ilen;
			work1 = ia32_br_find (root, vaddr + ilen,
				all, all_count, &br_splitted);

			if (br_splitted)
				rval = 1;

			this->endtype = BR_END_CALL;
			this->endbr = xcalloc (1, sizeof (ia32_bblock *));

			this->endbr[0] = work1;
			if (this->endbr[0] == NULL) {
				rval = 1;
				this->endbr[0] = ia32_br_new ();
				this->endbr[0]->start = vaddr + ilen;
			}
			this->endbr_count = 1;

			return (rval);

		/* intra function references
		 */
		/* bblock if, conditional jump
		 */
		case (SW_INTRA | SW_COND | SW_PASS):
			if (destaddr == 0xffffffff)
				break;

			/* when the jcc points to within its own instruction,
			 * we can be sure there will be a relocation offset
			 * inserted at that place. this is rarely used, the
			 * only place i have seen it yet was the handling of
			 * system calls in glibc, where an inter-function jump
			 * to __syscall_error is used.
			 */
			if (ia32_trace_range (vaddr, vaddr + ilen, destaddr)) {
				unsigned int	odaddr = destaddr;


				destaddr = elf_reloc_list_lookup_func (rel_code,
					destaddr);

				ia32_debug (IA32_INFO, "    0x%08x: calljump "
					"to 0x%08x\n", vaddr, destaddr);

				assert (destaddr != 0xffffffff);

				ia32_func_xref_add (func, IA32_XREF_FUNCTION,
					vaddr - func->start, odaddr - vaddr,
					destaddr, NULL, NULL, 0);

				work1 = ia32_br_find (root, vaddr + ilen,
					all, all_count, &br_splitted);

				if (br_splitted)
					rval = 1;

				this->endtype = BR_END_IF_INTER;
				this->cond = inst->opc.cond;
				this->endbr_count = 1;
				this->endbr = xcalloc (1, sizeof (ia32_bblock *));
				this->endbr[0] = work1;

				if (this->endbr[0] == NULL) {
					rval = 1;
					this->endbr[0] = ia32_br_new ();
					this->endbr[0]->start = vaddr + ilen;
				}

				return (rval);
			}

			/* XXX: finding on the vaddr address cannot clash,
			 * since we either find no bblock or an already passed
			 * bblock. finding on the destination address can split
			 * our current bblock (`this'). hence, the first thing
			 * we have to ensure is whether we got a bblock and if
			 * resulted through a split
			 */
			duesplit = ia32_trace_range (this->start, this->end,
				destaddr);
			work1 = ia32_br_find (root, vaddr + ilen,
				all, all_count, &br_splitted);
			if (br_splitted)
				rval = 1;
			work2 = ia32_br_find (root, destaddr, all, all_count,
				&br_splitted);
			if (br_splitted)
				rval = 1;

			if (duesplit) {
				assert (work2 != NULL);
				this = work2;
			}

			/* XXX: set this after ia32_br_find, else clash
			 */
			this->endtype = BR_END_IF;
			this->cond = inst->opc.cond;
			this->endbr_count = 2;
			this->endbr = xcalloc (2, sizeof (ia32_bblock *));
			this->endbr[0] = work1;
			this->endbr[1] = work2;

			if (this->endbr[0] == NULL) {
				rval = 1;
				this->endbr[0] = ia32_br_new ();
				this->endbr[0]->start = vaddr + ilen;
			}

			if (this->endbr[1] == NULL) {
				rval = 1;
				this->endbr[1] = ia32_br_new ();
				this->endbr[1]->start = destaddr;
			}

			return (rval);

		/* bblock transfer, unconditional jump
		 */
		case (SW_INTRA | SW_UNCOND | SW_PASS):
			if (destaddr == 0xffffffff)
				break;

			/* check whether there are relocation information for
			 * the location
			 */
			rdaddr = elf_reloc_list_lookup_func (rel_code,
				vaddr + ia32_has_displacement (inst, NULL));
			ia32_debug (IA32_DEBUG, "    0x%08x: unconditional "
				"jump, reloc lookup: 0x%08x\n", vaddr, rdaddr);

			if (rdaddr != 0xffffffff) {
				unsigned int	rel_displ;

				rel_displ = ia32_has_displacement (inst, NULL);

				ia32_debug (IA32_DEBUG, "      through reloc "
					"at 0x%08x to 0x%08x\n",
					vaddr + rel_displ, rdaddr);

				ia32_func_xref_add (func, IA32_XREF_FUNCTION,
					vaddr - func->start, rel_displ,
					rdaddr, NULL, NULL, 0);

				this->endtype = BR_END_TRANSFER_INTER;
				this->endbr_count = 0;

				return (rval);
			}

			duesplit = ia32_trace_range (this->start, this->end,
				destaddr);
			work1 = ia32_br_find (root, destaddr, all, all_count,
				&br_splitted);
			if (br_splitted)
				rval = 1;

			if (duesplit) {
				assert (work1 != NULL);
				this = work1;
			}

			this->endtype = BR_END_TRANSFER;
			this->endbr = xcalloc (1, sizeof (ia32_bblock *));

			this->endbr[0] = work1;
			if (this->endbr[0] == NULL) {
				rval = 1;
				this->endbr[0] = ia32_br_new ();
				this->endbr[0]->start = destaddr;
			}
			this->endbr_count = 1;

			return (rval);

		/* bblock ignore or failure, relocation or non-conform code
		 * mostly normal calls that get fixed by relocation entries
		 */
		case (SW_INTRA | SW_UNCOND | SW_RESUME):
		case (SW_INTRA | SW_COND | SW_RESUME):
			/* ignore unknown targets
			 */
			if (destaddr == 0xffffffff)
				break;

		        /* for directly-after-instruction calls the call is
			 * used to obtain the current position (in PIC code
			 * before any relocation could take place).  this
			 * might be problematic for some applications, so mark
			 * that odd case within the function object but ignore
			 * otherwise.
			 */
			if (destaddr == vaddr + ilen) {
				ia32_debug (IA32_WARNING, "WARNING: function "
					"\"%s\" is position curious at 0x%x. "
					"marking as such.\n", func->name,
					vaddr);

				func->is_pos_curious = 1;

				break;
			}

			ia32_debug (IA32_INFO, "  0x%08x: call\n", vaddr);

			/* to-be-filled-in relocation positions in ELF object
			 * files have target one after the call instruction
			 * so, look it up in the relocation table.
			 * FIXME: use a more generic "destaddr within
			 *        instruction" approach, ia32_trace_range (..)
			 */
			if (destaddr == vaddr + 1) {
				elf_reloc * rel_item;

				destaddr = elf_reloc_list_lookup_func (rel_code,
					vaddr + 1);

				rel_item = elf_reloc_list_lookup (rel_code,
					vaddr + 1);

				/* still invalid :-/
				 */
				if (destaddr == 0xffffffff) {
					ia32_debug (IA32_DEBUG, "DEBUG: "
						"(ia32_func_breakup_2) failed "
						"to obtain relocation for "
						"0x%08x\n", vaddr);

					elf_reloc_list_debug (rel_code, vaddr + 1);

					ia32_func_xref_add (func,
						IA32_XREF_FUNCEXTERN,
						vaddr - func->start, 1,
						destaddr, NULL, rel_item == NULL ?
							NULL : &rel_item->orig, 0);

					/* XXX ugly hack: step over the call,
					 * create a "ignore instruction"
					 * endtype.
					 * FIXME: find a better way
					 */
					ia32_debug (IA32_DEBUG, "DEBUG: "
						"adding skip branch end type, "
						"danger ahead...\n");

					work1 = ia32_br_find (root, vaddr + ilen,
						all, all_count, &br_splitted);
					if (br_splitted)
						rval = 1;

					this->endtype = BR_END_CALL_EXTERN;
					this->endbr = xcalloc (1,
						sizeof (ia32_bblock *));

					this->endbr[0] = work1;
					if (this->endbr[0] == NULL) {
						rval = 1;
						this->endbr[0] = ia32_br_new ();
						this->endbr[0]->start = vaddr + ilen;
					}
					this->endbr_count = 1;
					/*assert (0); */
					return (rval);
				}

				ia32_debug (IA32_INFO, "    through reloc at "
					"0x%08x to 0x%08x\n", vaddr, destaddr);
				ia32_func_xref_add (func, IA32_XREF_FUNCTION,
					vaddr - func->start, 1, destaddr, NULL,
					rel_item == NULL ?
						NULL : &rel_item->orig, 0);

				work1 = ia32_br_find (root, vaddr + ilen,
					all, all_count, &br_splitted);
				if (br_splitted)
					rval = 1;

				this->endtype = BR_END_CALL;
				this->endbr = xcalloc (1, sizeof (ia32_bblock *));

				this->endbr[0] = work1;
				if (this->endbr[0] == NULL) {
					rval = 1;
					this->endbr[0] = ia32_br_new ();
					this->endbr[0]->start = vaddr + ilen;
				}
				this->endbr_count = 1;

				ia32_debug (IA32_INFO, "    ==> call at 0x%08x "
					"to 0x%08x\n", vaddr, destaddr);

				return (rval);
			}

			/* one legit destaddr is the start of this function,
			 * in case its direct recursive. check this case
			 */
			if (func->start == destaddr) {
				/* do not specify an ia32_function structure
				 * for now, will fill that in later
				 */
				ia32_func_xref_add (func, IA32_XREF_FUNCTION,
					vaddr - func->start, 1, destaddr, NULL,
					NULL, 0);

				break;
			}

			/* in case of inter-section calls (example: _init
			 * calling into .text section), add just the function
			 * address as reference and let it fillin the correct
			 * function object later, when all sections have been
			 * processed.
			 */
			if (ia32_has_displacement (inst, NULL)) {
				/* adress the relocation is done */
				unsigned int	rel_addr;
				elf_reloc *	rel;

				rel_addr = vaddr +
					ia32_has_displacement (inst, NULL);

				rel = elf_reloc_list_lookup (rel_code, rel_addr);
				if (rel != NULL) {
					if (rel->type != ELF_RELOC_SECTION)
						goto complex_func_hierarchy;

					destaddr = rel->addend -
						ia32_has_displacement (inst, NULL) +
						inst->length;

					ia32_debug (IA32_WARNING, "WARNING: 0x%08x: "
						"inter section call from \"%s\" "
						"(%s:0x%x (+%d) -> %s:0x%x)\n",
						vaddr, func->name,
						rel_code->reloc_modify->name, vaddr,
						ia32_has_displacement (inst, NULL),
						rel->sym != NULL ? rel->sym->sec->name :
						"?", destaddr);

				} else {
					/* no relocation entry found, that
					 * means destaddr is already valid
					 */
					ia32_debug (IA32_INFO, "INFO: 0x%x: "
						"displaced non-relocation call\n",
						vaddr);
					ia32_confirm ();
				}

				/* FIXME:SEC: we just pack in the offset of
				 * the function, but do not specify to what
				 * section it refers, doh! :-/
				 */
				ia32_func_xref_add (func, IA32_XREF_FUNCTION,
					vaddr - func->start,
					ia32_has_displacement (inst, NULL),
					destaddr, NULL,
					rel == NULL ? NULL : &rel->orig, 1);

				work1 = ia32_br_find (root, vaddr + ilen,
					all, all_count, &br_splitted);

				if (br_splitted)
					rval = 1;

				this->endtype = BR_END_CALL;
				this->endbr = xcalloc (1, sizeof (ia32_bblock *));

				this->endbr[0] = work1;
				if (this->endbr[0] == NULL) {
					rval = 1;
					this->endbr[0] = ia32_br_new ();
					this->endbr[0]->start = vaddr + ilen;
				}
				this->endbr_count = 1;

				return (rval);
			}

complex_func_hierarchy:
			/* everything else is an error or complex function
			 * unrolling we cannot cope with
			 */
			ia32_debug (IA32_FATAL, "FATAL: (ia32_func_breakup_2) "
				"complex function hierarchy\n");
			ia32_debug (IA32_FATAL, "  func-entry: 0x%08x, "
				"vaddr: 0x%08x, destaddr: 0x%08x",
				func->start, vaddr, destaddr);

			assert (0);
			this->endtype = BR_END_INVALID;

			return (rval);

		default:
			break;
		}
#undef	SW_INTRA
#undef	SW_INTER
#undef	SW_COND
#undef	SW_UNCOND
#undef	SW_RESUME
#undef	SW_PASS
		vaddr += ilen;

		/* examine next instruction, is there already a bblock for it?
		 */
		work1 = ia32_br_find (root, vaddr, all, all_count,
			&br_splitted);
		if (br_splitted)
			rval = 1;

		if (work1 != NULL) {
			this->end = vaddr;
			this->endtype = BR_END_PASS;
			this->endbr = xcalloc (1, sizeof (ia32_bblock *));
			this->endbr[0] = work1;
			this->endbr_count = 1;

			return (rval);
		}
	}

	return (rval);
}


ia32_linux_interrupt *
ia32_linux_interrupt_decode (ia32_function *func, ia32_bblock *root,
	ia32_bblock *this, unsigned int vaddr, ia32_instruction *inst)
{
	ia32_linux_interrupt *	intdef;
	ia32_instruction *	cur;
	ia32_instruction *	ilist;
	int			ilist_count,
				in;	/* ilist walker */
	int			syscall_number = -1;


	if (strcmp (inst->opc.opcode->name, "int") != 0 ||
		inst->opc.target_type != OP_TYPE_IMM ||
		inst->opc.imm_value != IA32_LINUX_SYSCALLINT)
		return (NULL);

	/* decode the instructions leading to the system call. then try to
	 * figure out its system call number.
	 */
	ilist = ia32_func_inst_traceup (4, &ilist_count, func, root,
		this, vaddr);
	assert (ilist != NULL && ilist_count > 0);

	for (in = ilist_count - 1 ; in >= 0 ; --in) {
		cur = &ilist[in];
		if (ia32_verbose (IA32_DEBUG))
			ia32_print (cur);

		if (strcmp (cur->opc.opcode->name, "mov") != 0)
			continue;

		assert (OD_TEST (cur->opc.used, OP_SOURCE | OP_TARGET));

		if (cur->opc.target_type != OP_TYPE_REG ||
			cur->opc.source_type != OP_TYPE_IMM)
			continue;

		if (cur->opc.target_reg != IA32_REG_EAX)
			continue;

		syscall_number = cur->opc.imm_value;
		break;
	}

	if (syscall_number < 0 || syscall_number > IA32_LINUX_MAXSYSCALL) {
		ia32_debug (IA32_FATAL, "FATAL: (ia32_linux_interrupt_decode) "
			"failed to obtain system call number\n");

		return (NULL);
	}

	intdef = xcalloc (1, sizeof (ia32_linux_interrupt));
	intdef->syscall = syscall_number;

	switch (syscall_number) {
	case (__NR_exit):
	case (__NR_sigreturn):
	case (__NR_rt_sigreturn):
		intdef->resume = 0;
		break;
	default:
		intdef->resume = 1;
		break;
	}

	return (intdef);
}

/* we need to decode possible switch tables to do a complete basic block
 * analysis. for the actual native run we do not need one though.
 */

ia32_switchtable *
ia32_func_switchtable_decode (ia32_function *func, ia32_bblock *root,
	ia32_bblock *this, unsigned int vaddr, ia32_instruction *inst)
{
	ia32_instruction *	cur;
	ia32_instruction *	ilist;
	ia32_instruction	inst_s;
	int			ilist_count;

	/* we trace back the use of registers to index and displace into the
	 * switch table. to do this, we keep register indexes.
	 *   stab_idx_reg = register used to relativly index into the table
	 *   disp_reg = table base register
	 *   comb_reg = combined register
	 *
	 * only stab_idx_reg is mandatory, the others are used to fill
	 *   table_start = absolute address of switch table
	 *
	 * our algorithm is to trace back until we have both the table_start
	 * and the stab_idx_reg. then we can emulate the switch table
	 * behaviour and fill in the bblockes.
	 *
	 *   stab_size is optional, and filled in when we see a check for
	 * an upper bound of stab_idx_reg.
	 */
	int			stab_idx_reg = -1,
				stab_idx_scale = -1,
				disp_reg = -1,
				comb_reg = -1;
	unsigned int		table_start = 0xffffffff,
				table_loc_vaddr = 0xffffffff;
	int			in;	/* instruction walker */
	int			stab_size = -1;
	ia32_switchtable *	stab;
	unsigned int		t_rel,
				t_val = 0;


	ilist = ia32_func_inst_traceup (16, &ilist_count, func, root,
		this, vaddr);
	assert (ilist != NULL && ilist_count > 0);

	cur = inst;
	if (ia32_verbose (IA32_DEBUG))
		ia32_print (cur);

	if (cur->opc.target_type == OP_TYPE_REG) {
		comb_reg = cur->opc.target_reg;
	} else if (cur->opc.target_type == OP_TYPE_MEM) {
		unsigned int	displ_rel;


		if (cur->opc.base)
			disp_reg = cur->opc.base_reg;

		/* FIXME: check whether the index reg is already 4*'ed */
		if (cur->opc.index) {
			stab_idx_reg = cur->opc.index_reg;
			stab_idx_scale = cur->opc.scale;
		}

		displ_rel = ia32_has_displacement (cur, NULL);
		if (displ_rel != 0) {
			table_start = inst->opc.displ_value;
			table_loc_vaddr = vaddr + displ_rel;
		}
	}

	for (in = ilist_count - 1 ; in >= 0 ; --in) {
		cur = &ilist[in];
		if (ia32_verbose (IA32_DEBUG))
			ia32_print (cur);

		if (strcmp (cur->opc.opcode->name, "mov") == 0) {
			int *		regp;

			assert (OD_TEST (cur->opc.used, OP_SOURCE | OP_TARGET));

			if (cur->opc.target_type != OP_TYPE_REG)
				continue;

			if (cur->opc.target_reg == disp_reg)
				regp = &disp_reg;
			else if (cur->opc.target_reg == comb_reg)
				regp = &comb_reg;
			else
				continue;


			if (cur->opc.source_type == OP_TYPE_REG) {
				*regp = cur->opc.source_reg;
				continue;
			}

			t_rel = ia32_has_immediate (cur, NULL);
			if (t_rel) {
				t_val = cur->opc.imm_value;
			} else {
				t_rel = ia32_has_displacement (cur, NULL);
				if (t_rel)
					t_val = cur->opc.displ_value;

				/* SIB addressing on combined register almost
				 * always means jumptable access
				 */
				if (cur->opc.source_type == OP_TYPE_MEM &&
					cur->opc.target_reg == comb_reg &&
					cur->opc.index)
				{
					comb_reg = -1;
					stab_idx_reg = cur->opc.index_reg;
					/* FIXME: what to do about
					 * scales != 2 ?
					 */
					stab_idx_scale = cur->opc.scale;
					table_start = cur->opc.displ_value;
				}
			}

			if (t_rel && (cur->opc.source_type == OP_TYPE_IMM ||
				cur->opc.source_type == OP_TYPE_MEMREG))
			{
#ifdef	MAYBE_REWRITE_THIS_HEURISTICS
				ia32_debug (IA32_INFO, "INFO: abort "
					"switchtable search with t_val = "
					"0x%08x\n", t_val);

				return (NULL);
#endif
#if 1
				table_start = t_val;
				table_loc_vaddr = vaddr + t_rel;

				if (cur->opc.source_type == OP_TYPE_MEMREG &&
					regp == &comb_reg)
				{
					comb_reg = -1;
					stab_idx_reg = cur->opc.source_reg;
				}

				goto ccond;
#endif
			}

		} else if (strcmp (cur->opc.opcode->name, "cmp") == 0) {
			/* heuristics to guess the size of the switch table
			 */
			t_rel = ia32_has_immediate (cur, NULL);
			if (t_rel && cur->opc.imm_value > 0 &&
				cur->opc.imm_value < 4096)
			{
				stab_size = cur->opc.imm_value;
			}
		}
#if 1
ccond:
#endif
		if (stab_size != -1 && stab_idx_reg != -1 &&
			table_start != 0xffffffff)
		{
			break;
		}
	}

	/* XXX: ugly heuristics. if we have everything but the table start,
	 *      because one register is kept for the entire function and
	 * there are multiple pathes to the switch block, we just trace the
	 * function from top to bottom and use the first register load to
	 * the disp_reg. ugly, but should work in 90% of the cases.
	 * using a real safe method would require code- and dataflow analysis.
	 * XXX: maybe a dominator tree of the basic blocks is enough, or even
	 *      just _one_ path, since it would suffice to let the register
	 * load
	 */
	if (in < 0 && stab_size != -1 && stab_idx_reg != -1 &&
		disp_reg != -1 && table_start == 0xffffffff)
	{
		for (vaddr = func->start ; table_start == 0xffffffff &&
			vaddr < func->end ; vaddr += cur->length)
		{
			cur = ia32_decode_instruction
				(&func->mem[vaddr - func->start], &inst_s);
			assert (cur != NULL);

			if (strcmp (cur->opc.opcode->name, "mov") != 0)
				continue;

			assert (OD_TEST (cur->opc.used, OP_SOURCE | OP_TARGET));
			if (cur->opc.target_type != OP_TYPE_REG)
				continue;

			if (cur->opc.target_reg != disp_reg)
				continue;

			if (cur->opc.source_type != OP_TYPE_IMM)
				continue;

			t_rel = ia32_has_immediate (cur, NULL);
			if (t_rel) {
				t_val = cur->opc.imm_value;
			} else {
				t_rel = ia32_has_displacement (cur, NULL);
				if (t_rel)
					t_val = cur->opc.displ_value;
			}

			if (t_rel) {
				table_start = t_val;
				table_loc_vaddr = vaddr + t_rel;
			}
		}
	} else if (in < 0) {
		ia32_debug (IA32_WARNING, "WARNING: "
			"(ia32_func_switchtable_decode) failed to extract "
			"switchtable information\n");

		return (NULL);
	}

	ia32_debug (IA32_INFO, "switch table, start: 0x%08x, elements 0-%d, "
		"index reg %d (scale %d)\n",
		table_start, stab_size, stab_idx_reg, stab_idx_scale);

	free (ilist);

	stab = xcalloc (1, sizeof (ia32_switchtable));
	stab->entries = stab_size + 1;
	stab->vaddr_start = table_start;
	stab->vaddr_loc = table_loc_vaddr;	/* used for relocation */
	stab->idx_reg = stab_idx_reg;
	stab->idx_scale = stab_idx_scale;

	return (stab);
}


ia32_instruction *
ia32_func_inst_traceup (int backcount, int *inst_count, ia32_function *func,
	ia32_bblock *root, ia32_bblock *cur, unsigned int end_vaddr)
{
	ia32_instruction *	inst,
				inst_s;
	ia32_instruction *	ilist = NULL;
	unsigned char *		mem;
	unsigned int		icount,
				vaddr,
				skipcount = 0;
	ia32_bblock **		brefs;
	int			brefs_count;
	ia32_instruction *	sub_ilist;
	int			sub_ilist_count;


	*inst_count = 0;

	icount = ia32_func_inst_count (func, cur->start, end_vaddr);
	if (icount > backcount) {
		skipcount = icount - backcount;
		icount = backcount;
	}

	/* create the list in correct order
	 */
	for (vaddr = cur->start ; vaddr < end_vaddr ; vaddr += inst->length) {
		mem = &func->mem[vaddr - func->start];
		inst = ia32_decode_instruction (mem, &inst_s);
		assert (inst != NULL);

		/* skip instructions that are beyond the number we should
		 * collect.
		 */
		if (skipcount > 0) {
			skipcount -= 1;
			continue;
		}

		/* else add the decoded instruction to our list
		 */
		*inst_count += 1;
		ilist = xrealloc (ilist, *inst_count * sizeof (ilist[0]));
		memcpy (&ilist[*inst_count - 1], &inst_s, sizeof (inst_s));
	}

	/* in case we collected enough instructions, return the list, else
	 * trace the bblockes back up when possible. for more than one backref
	 * we cannot tell which lead to here, so return less than the requested
	 * number of instructions
	 */
	if (*inst_count == backcount)
		return (ilist);

	brefs = ia32_func_bblock_backrefs (&brefs_count, root, cur);
	if (brefs_count != 1) {
		if (brefs != NULL)
			free (brefs);

		return (ilist);
	}

	/* recurse to collect the instructions of the last bblock
	 */
	assert (backcount > *inst_count);
	sub_ilist = ia32_func_inst_traceup (backcount - *inst_count,
		&sub_ilist_count, func, root, brefs[0], brefs[0]->end);

	assert (sub_ilist != NULL && sub_ilist_count > 0);
	/* merge the sublist to the front of the main list
	 */
	ilist = xrealloc (ilist,
		(*inst_count + sub_ilist_count) * sizeof (ilist[0]));
	memmove (&ilist[sub_ilist_count], &ilist[0],
		*inst_count * sizeof (ilist[0]));
	memcpy (&ilist[0], sub_ilist, sub_ilist_count * sizeof (ilist[0]));
	free (sub_ilist);

	*inst_count += sub_ilist_count;

	return (ilist);
}


unsigned int
ia32_func_inst_count (ia32_function *func, unsigned int vstart,
	unsigned int vend)
{
	ia32_instruction *	inst,
				inst_s;
	unsigned char *		mem;
	unsigned int		icount,
				cur_vaddr;


	/* exclude traced functions from range checking
	 */
	if (func->start != func->end && func->traced_bounds == 0) {
		assert (vstart >= func->start && vend <= func->end);
	}

	cur_vaddr = vstart;

	for (icount = 0 ; cur_vaddr < vend ; ++icount) {
		mem = &func->mem[cur_vaddr - func->start];
		inst = ia32_decode_instruction (mem, &inst_s);

		assert (inst != NULL);
		cur_vaddr += inst->length;
	}

	return (icount);
}


ia32_bblock **
ia32_func_bblock_backrefs (int *br_count, ia32_bblock *root, ia32_bblock *cur)
{
	ia32_bblock **	btl;	/* list of all bblockes */
	unsigned int	btl_len,/* length of this list */
			n,	/* main walker */
			ebn,	/* end bblock walker */
			aln;	/* add list walker */
	ia32_bblock **	list = NULL;
	ia32_bblock *	add;
	int		dupe;


	btl = ia32_br_get_all (root, &btl_len);
	*br_count = 0;

	/* the basic idea is this: walk all bblockes already processed and
	 * collect all bblockes that have forward references to the current
	 * bblock. avoid dupes, but leave the resulting list unsorted.
	 */
	for (n = 0 ; n < btl_len ; ++n) {
		if (btl[n] == cur)
			continue;

		add = NULL;
		for (ebn = 0 ; ebn < btl[n]->endbr_count ; ++ebn) {
			if (btl[n]->endbr[ebn] == cur) {
				add = btl[n];
				break;
			}
		}

		if (add == NULL)
			continue;

		dupe = 0;
		for (aln = 0 ; aln < *br_count ; ++aln)
			if (list[aln] == add)
				dupe = 1;

		/* when its already in the backref list, skip
		 */
		if (dupe)
			continue;

		*br_count += 1;
		list = xrealloc (list, *br_count * sizeof (ia32_bblock *));
		list[*br_count - 1] = add;
	}

	free (btl);

	return (list);
}


ia32_function *
ia32_func_list_find_bymem (ia32_function **flist, unsigned int flist_count,
	unsigned char *memstart)
{
	unsigned int	n;


	for (n = 0 ; n < flist_count ; ++n) {
		if (flist[n]->mem == memstart && flist[n]->is_copy == 0)
			return (flist[n]);
	}

	return (NULL);
}


ia32_function *
ia32_func_list_find_bystart (ia32_function **flist, unsigned int flist_count,
	unsigned int start)
{
	unsigned int	n;


	for (n = 0 ; n < flist_count ; ++n) {
		if (flist[n]->start == start && flist[n]->is_copy == 0)
			return (flist[n]);
	}

	return (NULL);
}


ia32_function *
ia32_func_list_find_byname (ia32_function **flist, unsigned int flist_count,
	char *fname)
{
	unsigned int	n;


	for (n = 0 ; n < flist_count ; ++n) {
		if (flist[n]->name == NULL)
			continue;

		if (strcmp (fname, flist[n]->name) == 0)
			return (flist[n]);
	}

	return (NULL);
}


int
ia32_func_list_find_index (ia32_function **flist, unsigned int flist_count,
	ia32_function *func)
{
	unsigned int	n;


	for (n = 0 ; n < flist_count ; ++n)
		if (flist[n] == func)
			return (n);

	return (-1);
}


void
ia32_func_list_dump (ia32_function **flist, unsigned int flist_count)
{
	unsigned int	n;


	for (n = 0 ; n < flist_count ; ++n) {
		printf ("%-32s | 0x%08x - 0x%08x | @ 0x%08x\n",
			flist[n]->name, flist[n]->start, flist[n]->end,
			(unsigned int) flist[n]->mem);
	}
}


void
ia32_graphviz_func_out (FILE *fp, ia32_function **flist,
	unsigned int flist_count, elf_reloc_list *reloc_text)
{
	ia32_graphviz_func_out_2 (fp, flist, flist_count, NULL, reloc_text);
}


static void
ia32_graphviz_func_out_2 (FILE *fp, ia32_function **flist,
	unsigned int flist_count, int *flist_consider,
	elf_reloc_list *reloc_text)
{
	char **		ext_list = NULL;
	unsigned int	ext_list_count = 0;
	char *		ext_current;
	unsigned int	ext_wlk;

	unsigned int	n,
			i;


	fprintf (fp, "digraph functiondeps {\n\n");
	fprintf (fp, "\tnode [\n");
	fprintf (fp, "\t\tstyle = filled\n");
	fprintf (fp, "\t\tshape = \"record\"\n");
	fprintf (fp, "\t\tfillcolor = \"lightskyblue\"\n");
	fprintf (fp, "\t];\n\n");

	for (n = 0 ; n < flist_count ; ++n) {
		if (flist_consider != NULL && flist_consider[n] == 0)
			continue;

		fprintf (fp, "\t\"%s\" [\n", flist[n]->name);
		fprintf (fp, "\t\tlabel = \"{ <fi> | %s | <fo> }\"\n",
			flist[n]->name);
		fprintf (fp, "\t];\n");
	}

	for (n = 0 ; n < flist_count ; ++n) {
		if (flist_consider != NULL && flist_consider[n] == 0)
			continue;

		for (i = 0 ; i < flist[n]->func_xref_count ; ++i) {
			ext_current = NULL;

			switch (flist[n]->func_xref[i]->to_type) {
			case (IA32_XREF_FUNCEXTERN):
				ext_current = ia32_graphviz_func_out_extern
					(fp, flist[n],
					flist[n]->func_xref[i],
					reloc_text);
				break;
			case (IA32_XREF_FUNCTION):
				ia32_graphviz_func_out_intern (fp,
					flist[n], flist[n]->func_xref[i],
					flist, flist_count, flist_consider);
				break;
			default:
				break;
			}

			if (ext_current == NULL)
				continue;

			for (ext_wlk = 0 ; ext_wlk < ext_list_count ; ++ext_wlk) {
				if (strcmp (ext_list[ext_wlk], ext_current) == 0)
					break;
			}

			if (ext_wlk < ext_list_count)
				continue;

			ext_list_count += 1;
			ext_list = xrealloc (ext_list,
				ext_list_count * sizeof (char *));
			ext_list[ext_list_count - 1] = ext_current;
		}
	}

	/* output all external references found while dumping normal references
	 */
	if (ext_list_count > 0 && ia32_graphviz_align_undefined)
		fprintf (fp, "\tsubgraph cluster_undefined {\n"
			"\t\tlabel = \"undefined\";\n\n");

	for (ext_wlk = 0 ; ext_wlk < ext_list_count ; ++ext_wlk) {
		fprintf (fp, "\t\t\"%s\" [\n", ext_list[ext_wlk]);
		fprintf (fp, "\t\t\tlabel = \"{ <fi> | %s | <fo> }\"\n",
			ext_list[ext_wlk]);
		fprintf (fp, "\t\t\tfillcolor = \"red\"\n");
		fprintf (fp, "\t\t];\n");
	}

	if (ext_list_count > 0 && ia32_graphviz_align_undefined)
		fprintf (fp, "\t}\n");

	free (ext_list);

	fprintf (fp, "}\n");

	return;
}


static char *
ia32_graphviz_func_out_extern (FILE *fp, ia32_function *func,
	ia32_xref *xr, elf_reloc_list *reloc_text)
{
	unsigned int	from_addr;
	elf_reloc *	rel;
	char *		ext_name;


	if (reloc_text == NULL)
		return (NULL);

	/* look up relocation entry for reference source address, then try
	 * to pull the symbol table entry
	 */
	from_addr = xr->from + xr->addend + func->start;
	rel = elf_reloc_list_lookup (reloc_text, from_addr);
	if (rel == NULL)
		return (NULL);

	ext_name = "???";
	if (rel->sym->name != NULL)
		ext_name = rel->sym->name;

	ia32_debug (IA32_DEBUG, "0x%08x: %s -> %s\n", from_addr,
		func->name, ext_name);
	fprintf (fp, "\t\"%s\":fo -> \"%s\":fi;\n",
		func->name, ext_name);

	return (ext_name);
}


static void
ia32_graphviz_func_out_intern (FILE *fp, ia32_function *func, ia32_xref *xr,
	ia32_function **flist, unsigned int flist_count,
	int *flist_consider)
{
	char *		dname;	/* destination reference */
	ia32_function *	dest_func;


	if (func == NULL)
		return;

	if (flist_consider != NULL &&
		flist_consider[ia32_func_list_find_index (flist,
			flist_count, func)] == 0)
	{
		return;
	}

	dest_func = xr->to_data;
	assert (dest_func != NULL);
	dname = dest_func->name;

	if (dname != NULL) {
		ia32_debug (IA32_DEBUG, "          : %s -> %s\n",
			func->name, dname);
		fprintf (fp, "\t\"%s\":fo -> \"%s\":fi;\n",
			func->name, dname);
	}

	return;
}


void
ia32_graphviz_func_out_calltree (FILE *fp, ia32_function **flist,
	unsigned int flist_count, ia32_function *interest)
{
	int			int_idx;
	int *			int_arr;

	ia32_function *		func;
	unsigned int		n_m,
				n,
				i;


	assert (interest != NULL);
	int_idx = ia32_func_list_find_index (flist, flist_count, interest);
	assert (int_idx != -1);

	int_arr = xcalloc (flist_count, sizeof (int));
	int_arr[int_idx] = 1;

	/* do a little by brute force,
	 * FIXME: use a more elegant way ;)
	 */
#if 0
	for (n_m = 0 ; n_m < (flist_count * flist_count) ; ++n_m) {
#endif
	for (n_m = 0 ; n_m < (32 * flist_count) ; ++n_m) {
		n = n_m % flist_count;

		if (int_arr[n] != 0)
			continue;

		for (i = 0 ; i < flist[n]->func_xref_count ; ++i) {
			unsigned int	sub_idx;

			if (flist[n]->func_xref[i]->to_type !=
				IA32_XREF_FUNCTION)
				continue;

			func = (ia32_function *) flist[n]->func_xref[i]->to_data;
			if (func == NULL)
				continue;

			sub_idx = ia32_func_list_find_index (flist,
				flist_count, func);
			if (int_arr[sub_idx] == 1)
				int_arr[n] = 1;
		}
	}

	ia32_graphviz_func_out_2 (fp, flist, flist_count, int_arr, NULL);

	free (int_arr);
}


#ifdef	DUPE_DEBUG
void
dupe_alloc (unsigned int max_addr)
{
	addr_arr = xcalloc (max_addr, sizeof (unsigned int));
	addr_max = max_addr;
}

void
dupe_free (void)
{
	if (addr_arr != NULL)
		free (addr_arr);

	addr_max = 0;
}


void
dupe_check (unsigned int addr)
{
	/* not to use dupe check for runtime
	 */
	if (dupe_check_enabled == 0 || addr_max == 0)
		return;

	assert (addr < addr_max);
	if (addr_arr[addr] != 0) {
		ia32_debug (IA32_FATAL, "FATAL: (dupe_check) address access "
			"(%d) dupe at 0x%08x, dumping\n", addr_ac, addr);
		ia32_debug (IA32_FATAL, "\t%1d %1d %1d %1d %1d %1d %1d %1d\n",
			addr_arr[addr + 0], addr_arr[addr + 1],
			addr_arr[addr + 2], addr_arr[addr + 3],
			addr_arr[addr + 4], addr_arr[addr + 5],
			addr_arr[addr + 6], addr_arr[addr + 7]);

		assert (0);
	} else
		ia32_debug (IA32_DEBUG, "§ %d access: 0x%08x\n", addr_ac, addr);

	addr_arr[addr] = addr_ac;
	addr_ac += 1;
}
#endif