/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */
#include <sgs.h>
#include <string.h>
#include <stdio.h>
#include <sys/debug.h>

/*
 * Alist manipulation.  An Alist is a list of elements formed into an array.
 * Traversal of the list is an array scan, which because of the locality of
 * each reference is probably more efficient than a link-list traversal.
 *
 * See alist.h for more background information about array lists.
 */

/*
 * Insert a value into an array at a specified index:
 *
 *	alist_insert(): Insert an item into an Alist at the specified index
 *	alist_insert_by_offset(): Insert an item into an Alist at the
 *		specified offset relative to the list address.
 *	aplist_insert() Insert a pointer into an APlist at the specified index
 *
 * entry:
 *	Note: All the arguments for all three routines are listed here.
 *	The routine to which a given argument applies is given with
 *	each description.
 *
 *	llp [all] - Address of a pointer to an Alist/APlist. The pointer should
 *		be initialized to NULL before its first use.
 *	datap [alist_insert / aplist_insert] - Pointer to item data, or
 *		NULL. If non-null the data referenced is copied into the
 *		Alist item. Otherwise, the list item is zeroed, and
 *		further initialization is left to the caller.
 *	ptr [aplist_insert] - Pointer to be inserted.
 *	size [alist_insert / alist_insert_by_offset] - Size of an item
 *		in the array list, in bytes. As with any array, A given
 *		Alist can support any item size, but every item in that
 *		list must have the same size.
 *	init_arritems [all] - Initial allocation size: On the first insertion
 *		into the array list, room for init_arritems items is allocated.
 *	idx [alist_insert / aplist_insert] - Index at which to insert the
 *		new item. This index must lie within the existing list,
 *		or be the next index following.
 *	off [alist_insert_by_offset] - Offset at which  to insert the new
 *		item, based from the start of the Alist. The offset of
 *		the first item is ALIST_OFF_DATA.
 *
 * exit:
 *	The item is inserted at the specified position. This operation
 *	can cause memory for the list to be allocated, or reallocated,
 *	either of which will cause the value of the list pointer
 *	to change.
 *
 *	These routines can only fail if unable to allocate memory,
 *	in which case NULL is returned.
 *
 *	If a pointer list (aplist_insert), then the pointer
 *	is stored in the requested index. On success, the address
 *	of the pointer within the list is returned.
 *
 *	If the list contains arbitrary data (not aplist_insert): If datap
 *	is non-NULL, the data it references is copied into the item at
 *	the index. If datap is NULL, the specified item is zeroed.
 *	On success, a pointer to the inserted item is returned.
 *
 *	The  caller must not retain the returned pointer from this
 *	routine across calls to the list module. It is only safe to use
 *	it until the next call to this module for the given list.
 *
 */
void *
alist_insert(Alist **lpp, const void *datap, size_t size,
    Aliste init_arritems, Aliste idx)
{
	Alist	*lp = *lpp;
	char	*addr;

	/* The size and initial array count need to be non-zero */
	ASSERT(init_arritems != 0);
	ASSERT(size != 0);

	if (lp == NULL) {
		Aliste bsize;

		/*
		 * First time here, allocate a new Alist.  Note that the
		 * Alist al_desc[] entry is defined for 1 element,
		 * but we actually allocate the number we need.
		 */
		bsize = size * init_arritems;
		bsize = S_ROUND(bsize, sizeof (void *));
		bsize = ALIST_OFF_DATA + bsize;
		if ((lp = malloc((size_t)bsize)) == NULL)
			return (NULL);
		lp->al_arritems = init_arritems;
		lp->al_nitems = 0;
		lp->al_next = ALIST_OFF_DATA;
		lp->al_size = size;
		*lpp = lp;
	} else {
		/* We must get the same value for size every time */
		ASSERT(size == lp->al_size);

		if (lp->al_nitems >= lp->al_arritems) {
			/*
			 * The list is full: Increase the memory allocation
			 * by doubling it.
			 */
			Aliste	bsize;

			bsize = lp->al_size * lp->al_arritems * 2;
			bsize = S_ROUND(bsize, sizeof (void *));
			bsize = ALIST_OFF_DATA + bsize;
			if ((lp = realloc(lp, (size_t)bsize)) == NULL)
				return (NULL);
			lp->al_arritems *= 2;
			*lpp = lp;
		}
	}

	/*
	 * The caller is not supposed to use an index that
	 * would introduce a "hole" in the array.
	 */
	ASSERT(idx <= lp->al_nitems);

	addr = (idx * lp->al_size) + (char *)lp->al_data;

	/*
	 * An appended item is added to the next available array element.
	 * An insert at any other spot requires that the data items that
	 * exist at the point of insertion be shifted down to open a slot.
	 */
	if (idx < lp->al_nitems)
		(void) memmove(addr + lp->al_size, addr,
		    (lp->al_nitems - idx) * lp->al_size);

	lp->al_nitems++;
	lp->al_next += lp->al_size;
	if (datap != NULL)
		(void) memcpy(addr, datap, lp->al_size);
	else
		(void) memset(addr, 0, lp->al_size);
	return (addr);
}

void *
alist_insert_by_offset(Alist **lpp, const void *datap, size_t size,
    Aliste init_arritems, Aliste off)
{
	Aliste idx;

	if (*lpp == NULL) {
		ASSERT(off == ALIST_OFF_DATA);
		idx = 0;
	} else {
		idx = (off - ALIST_OFF_DATA) / (*lpp)->al_size;
	}

	return (alist_insert(lpp, datap, size, init_arritems, idx));
}

void *
aplist_insert(APlist **lpp, const void *ptr, Aliste init_arritems, Aliste idx)
{
	APlist	*lp = *lpp;

	/* The initial array count needs to be non-zero */
	ASSERT(init_arritems != 0);

	if (lp == NULL) {
		Aliste bsize;

		/*
		 * First time here, allocate a new APlist.  Note that the
		 * APlist apl_desc[] entry is defined for 1 element,
		 * but we actually allocate the number we need.
		 */
		bsize = APLIST_OFF_DATA + (sizeof (void *) * init_arritems);
		if ((lp = malloc((size_t)bsize)) == NULL)
			return (NULL);
		lp->apl_arritems = init_arritems;
		lp->apl_nitems = 0;
		*lpp = lp;
	} else if (lp->apl_nitems >= lp->apl_arritems) {
		/*
		 * The list is full: Increase the memory allocation
		 * by doubling it.
		 */
		Aliste	bsize;

		bsize = APLIST_OFF_DATA +
		    (2 * sizeof (void *) * lp->apl_arritems);
		if ((lp = realloc(lp, (size_t)bsize)) == NULL)
			return (NULL);
		lp->apl_arritems *= 2;
		*lpp = lp;
	}

	/*
	 * The caller is not supposed to use an index that
	 * would introduce a "hole" in the array.
	 */
	ASSERT(idx <= lp->apl_nitems);

	/*
	 * An appended item is added to the next available array element.
	 * An insert at any other spot requires that the data items that
	 * exist at the point of insertion be shifted down to open a slot.
	 */
	if (idx < lp->apl_nitems)
		(void) memmove((char *)&lp->apl_data[idx + 1],
		    (char *)&lp->apl_data[idx],
		    (lp->apl_nitems - idx) * sizeof (void *));

	lp->apl_nitems++;
	lp->apl_data[idx] = (void *)ptr;
	return (&lp->apl_data[idx]);
}

/*
 * Append a value to a list. These are convenience wrappers on top
 * of the insert operation. See the description of those routine above
 * for details.
 */
void *
alist_append(Alist **lpp, const void *datap, size_t size,
    Aliste init_arritems)
{
	Aliste ndx = ((*lpp) == NULL) ? 0 : (*lpp)->al_nitems;

	return (alist_insert(lpp, datap, size, init_arritems, ndx));
}

void *
aplist_append(APlist **lpp, const void *ptr, Aliste init_arritems)
{
	Aliste ndx = ((*lpp) == NULL) ? 0 : (*lpp)->apl_nitems;

	return (aplist_insert(lpp, ptr, init_arritems, ndx));
}

/*
 * Delete the item at a specified index/offset, and decrement the variable
 * containing the index:
 *
 *	alist_delete - Delete an item from an Alist at the specified
 *		index.
 *	alist_delete_by_offset - Delete an item from an Alist at the
 *		specified offset from the list pointer.
 *	aplist_delete - Delete a pointer from an APlist at the specified
 *		index.
 *
 * entry:
 *	alp - List to delete item from
 *	idxp - Address of variable containing the index of the
 *		item to delete.
 *	offp - Address of variable containing the offset of the
 *		item to delete.
 *
 * exit:
 *	The item at the position given by (*idxp) or (*offp), depending
 *	on the routine, is removed from the list. Then, the position
 *	variable (*idxp or *offp) is decremented by one item. This is done
 *	to facilitate use of this routine within a TRAVERSE loop.
 *
 * note:
 *	Deleting the last element in an array list is cheap, but
 *	deleting any other item causes a memory copy to occur to
 *	move the following items up. If you intend to traverse the
 *	entire list, deleting every item as you go, it will be cheaper
 *	to omit the delete within the traverse, and then call
 *	the reset function reset() afterwards.
 */
void
alist_delete(Alist *lp, Aliste *idxp)
{
	Aliste	idx = *idxp;


	/* The list must be allocated and the index in range */
	ASSERT(lp != NULL);
	ASSERT(idx < lp->al_nitems);

	/*
	 * If the element to be removed is not the last entry of the array,
	 * slide the following elements over the present element.
	 */
	if (idx < --lp->al_nitems) {
		char *addr = (idx * lp->al_size) + (char *)lp->al_data;

		(void) memmove(addr, addr + lp->al_size,
		    (lp->al_nitems - idx) * lp->al_size);
	}
	lp->al_next -= lp->al_size;

	/* Decrement the callers index variable */
	(*idxp)--;
}

void
alist_delete_by_offset(Alist *lp, Aliste *offp)
{
	Aliste idx;

	ASSERT(lp != NULL);
	idx = (*offp - ALIST_OFF_DATA) / lp->al_size;

	alist_delete(lp, &idx);
	*offp -= lp->al_size;
}

void
aplist_delete(APlist *lp, Aliste *idxp)
{
	Aliste	idx = *idxp;


	/* The list must be allocated and the index in range */
	ASSERT(lp != NULL);
	ASSERT(idx < lp->apl_nitems);

	/*
	 * If the element to be removed is not the last entry of the array,
	 * slide the following elements over the present element.
	 */
	if (idx < --lp->apl_nitems)
		(void) memmove(&lp->apl_data[idx], &lp->apl_data[idx + 1],
		    (lp->apl_nitems - idx) * sizeof (void *));

	/* Decrement the callers index variable */
	(*idxp)--;
}

/*
 * Delete the pointer with a specified value from the APlist.
 *
 * entry:
 *	lp - Initialized APlist to delete item from
 *	ptr - Pointer to be deleted.
 *
 * exit:
 *	The list is searched for an item containing the given pointer,
 *	and if a match is found, that item is delted and True (1) returned.
 *	If no match is found, then False (0) is returned.
 *
 * note:
 *	See note for delete operation, above.
 */
int
aplist_delete_value(APlist *lp, const void *ptr)
{
	size_t	idx;

	/*
	 * If the pointer is found in the list, use aplist_delete to
	 * remove it, and we're done.
	 */
	for (idx = 0; idx < lp->apl_nitems; idx++)
		if (ptr == lp->apl_data[idx]) {
			aplist_delete(lp, &idx);
			return (1);
		}

	/* If we get here, the item was not in the list */
	return (0);
}

/*
 * Search the APlist for an element with a given value, and
 * if not found, optionally append the element to the end of the list.
 *
 * entry:
 *	lpp, ptr - As per aplist_insert().
 *	init_arritems - As per aplist_insert() if a non-zero value.
 *		A value of zero is special, and is taken to indicate
 *		that no insert operation should be performed if
 *		the item is not found in the list.
 *
 * exit
 *	The given item is compared to every item in the given APlist.
 *	If it is found, ALE_EXISTS is returned.
 *
 *	If it is not found: If init_arr_items is False (0), then
 *	ALE_NOTFOUND is returned. If init_arr_items is True, then
 *	the item is appended to the list, and ALE_CREATE returned on success.
 *
 *	On failure, which can only occur due to memory allocation failure,
 *	ALE_ALLOCFAIL is returned.
 *
 * note:
 *	The test operation used by this routine is a linear
 *	O(N) operation, and is not efficient for more than a
 *	few items.
 */
aplist_test_t
aplist_test(APlist **lpp, const void *ptr, Aliste init_arritems)
{
	APlist	*lp = *lpp;
	size_t	idx;

	/* Is the pointer already in the list? */
	if (lp != NULL)
		for (idx = 0; idx < lp->apl_nitems; idx++)
			if (ptr == lp->apl_data[idx])
				return (ALE_EXISTS);

	/* Is this a no-insert case? If so, report that the item is not found */
	if (init_arritems == 0)
		return (ALE_NOTFND);

	/* Add it to the end of the list */
	if (aplist_append(lpp, ptr, init_arritems) == NULL)
		return (ALE_ALLOCFAIL);
	return (ALE_CREATE);
}

/*
 * Reset the given list to its empty state. Any memory allocated by the
 * list is preserved, ready for reuse, but the list is set to its
 * empty state, equivalent to having called the delete operation for
 * every item.
 *
 * Note that no cleanup of the discarded items is done. The caller must
 * take care of any necessary cleanup before calling aplist_reset().
 */
void
alist_reset(Alist *lp)
{
	if (lp != NULL) {
		lp->al_nitems = 0;
		lp->al_next = ALIST_OFF_DATA;
	}
}

void
aplist_reset(APlist *lp)
{
	if (lp != NULL)
		lp->apl_nitems = 0;
}
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <stdlib.h>
#include <stdio.h>

/*
 * Provide assfail() for ASSERT() statements,
 * see <sys/debug.h> for further details.
 */
int
assfail(const char *a, const char *f, int l)
{
	(void) printf("assertion failed: %s, file: %s, line: %d\n",
	    a, f, l);
	abort();
	return (0);
}
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <sys/types.h>

/*
 * function that will find a prime'ish number.  Usefull for
 * hashbuckets and related things.
 */
uint_t
findprime(uint_t count)
{
	uint_t	h, f;

	if (count <= 3)
		return (3);


	/*
	 * Check to see if divisible by two, if so
	 * increment.
	 */
	if ((count & 0x1) == 0)
		count++;

	for (h = count, f = 2; f * f <= h; f++)
		if ((h % f) == 0)
			h += f = 1;
	return (h);
}
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <stdio.h>
#include <dwarf.h>
#include <sys/types.h>
#include <sys/elf.h>

/*
 * Little Endian Base 128 (LEB128) numbers.
 * ----------------------------------------
 *
 * LEB128 is a scheme for encoding integers densely that exploits the
 * assumption that most integers are small in magnitude. (This encoding
 * is equally suitable whether the target machine architecture represents
 * data in big-endian or little- endian
 *
 * Unsigned LEB128 numbers are encoded as follows: start at the low order
 * end of an unsigned integer and chop it into 7-bit chunks. Place each
 * chunk into the low order 7 bits of a byte. Typically, several of the
 * high order bytes will be zero; discard them. Emit the remaining bytes in
 * a stream, starting with the low order byte; set the high order bit on
 * each byte except the last emitted byte. The high bit of zero on the last
 * byte indicates to the decoder that it has encountered the last byte.
 * The integer zero is a special case, consisting of a single zero byte.
 *
 * Signed, 2s complement LEB128 numbers are encoded in a similar except
 * that the criterion for discarding high order bytes is not whether they
 * are zero, but whether they consist entirely of sign extension bits.
 * Consider the 32-bit integer -2. The three high level bytes of the number
 * are sign extension, thus LEB128 would represent it as a single byte
 * containing the low order 7 bits, with the high order bit cleared to
 * indicate the end of the byte stream.
 *
 * Note that there is nothing within the LEB128 representation that
 * indicates whether an encoded number is signed or unsigned. The decoder
 * must know what type of number to expect.
 *
 * DWARF Exception Header Encoding
 * -------------------------------
 *
 * The DWARF Exception Header Encoding is used to describe the type of data
 * used in the .eh_frame_hdr section. The upper 4 bits indicate how the
 * value is to be applied. The lower 4 bits indicate the format of the data.
 *
 * DWARF Exception Header value format
 *
 * Name		Value Meaning
 * DW_EH_PE_omit	    0xff No value is present.
 * DW_EH_PE_absptr	    0x00 Value is a void*
 * DW_EH_PE_uleb128	    0x01 Unsigned value is encoded using the
 *				 Little Endian Base 128 (LEB128)
 * DW_EH_PE_udata2	    0x02 A 2 bytes unsigned value.
 * DW_EH_PE_udata4	    0x03 A 4 bytes unsigned value.
 * DW_EH_PE_udata8	    0x04 An 8 bytes unsigned value.
 * DW_EH_PE_signed          0x08 bit on for all signed encodings
 * DW_EH_PE_sleb128	    0x09 Signed value is encoded using the
 *				 Little Endian Base 128 (LEB128)
 * DW_EH_PE_sdata2	    0x0A A 2 bytes signed value.
 * DW_EH_PE_sdata4	    0x0B A 4 bytes signed value.
 * DW_EH_PE_sdata8	    0x0C An 8 bytes signed value.
 *
 * DWARF Exception Header application
 *
 * Name	    Value Meaning
 * DW_EH_PE_absptr	   0x00 Value is used with no modification.
 * DW_EH_PE_pcrel	   0x10 Value is reletive to the location of itself
 * DW_EH_PE_textrel	   0x20
 * DW_EH_PE_datarel	   0x30 Value is reletive to the beginning of the
 *				eh_frame_hdr segment ( segment type
 *			        PT_GNU_EH_FRAME )
 * DW_EH_PE_funcrel        0x40
 * DW_EH_PE_aligned        0x50 value is an aligned void*
 * DW_EH_PE_indirect       0x80 bit to signal indirection after relocation
 * DW_EH_PE_omit	   0xff No value is present.
 *
 */

dwarf_error_t
uleb_extract(unsigned char *data, uint64_t *dotp, size_t len, uint64_t *ret)
{
	uint64_t	dot = *dotp;
	uint64_t	res = 0;
	int		more = 1;
	int		shift = 0;
	int		val;

	data += dot;

	while (more) {
		if (dot > len)
			return (DW_OVERFLOW);

		/*
		 * Pull off lower 7 bits
		 */
		val = (*data) & 0x7f;

		/*
		 * Add prepend value to head of number.
		 */
		res = res | (val << shift);

		/*
		 * Increment shift & dot pointer
		 */
		shift += 7;
		dot++;

		/*
		 * Check to see if hi bit is set - if not, this
		 * is the last byte.
		 */
		more = ((*data++) & 0x80) >> 7;
	}
	*dotp = dot;
	*ret = res;
	return (DW_SUCCESS);
}

dwarf_error_t
sleb_extract(unsigned char *data, uint64_t *dotp, size_t len, int64_t *ret)
{
	uint64_t	dot = *dotp;
	int64_t		res = 0;
	int		more = 1;
	int		shift = 0;
	int		val;

	data += dot;

	while (more) {
		if (dot > len)
			return (DW_OVERFLOW);

		/*
		 * Pull off lower 7 bits
		 */
		val = (*data) & 0x7f;

		/*
		 * Add prepend value to head of number.
		 */
		res = res | (val << shift);

		/*
		 * Increment shift & dot pointer
		 */
		shift += 7;
		dot++;

		/*
		 * Check to see if hi bit is set - if not, this
		 * is the last byte.
		 */
		more = ((*data++) & 0x80) >> 7;
	}
	*dotp = dot;

	/*
	 * Make sure value is properly sign extended.
	 */
	res = (res << (64 - shift)) >> (64 - shift);
	*ret = res;
	return (DW_SUCCESS);
}

/*
 * Extract a DWARF encoded datum
 *
 * entry:
 *	data - Base of data buffer containing encoded bytes
 *	dotp - Address of variable containing index within data
 *		at which the desired datum starts.
 *	ehe_flags - DWARF encoding
 *	eident - ELF header e_ident[] array for object being processed
 *	frame_hdr - Boolean, true if we're extracting from .eh_frame_hdr
 *	sh_base - Base address of ELF section containing desired datum
 *	sh_offset - Offset relative to sh_base of desired datum.
 *	dbase - The base address to which DW_EH_PE_datarel is relative
 *		(if frame_hdr is false)
 */
dwarf_error_t
dwarf_ehe_extract(unsigned char *data, size_t len, uint64_t *dotp,
    uint64_t *ret, uint_t ehe_flags, unsigned char *eident,
    boolean_t frame_hdr, uint64_t sh_base, uint64_t sh_offset,
    uint64_t dbase)
{
	uint64_t    dot = *dotp;
	uint_t	    lsb;
	uint_t	    wordsize;
	uint_t	    fsize;
	uint64_t    result;

	if (eident[EI_DATA] == ELFDATA2LSB)
		lsb = 1;
	else
		lsb = 0;

	if (eident[EI_CLASS] == ELFCLASS64)
		wordsize = 8;
	else
		wordsize = 4;

	switch (ehe_flags & 0x0f) {
	case DW_EH_PE_omit:
		*ret = 0;
		return (DW_SUCCESS);
	case DW_EH_PE_absptr:
		fsize = wordsize;
		break;
	case DW_EH_PE_udata8:
	case DW_EH_PE_sdata8:
		fsize = 8;
		break;
	case DW_EH_PE_udata4:
	case DW_EH_PE_sdata4:
		fsize = 4;
		break;
	case DW_EH_PE_udata2:
	case DW_EH_PE_sdata2:
		fsize = 2;
		break;
	case DW_EH_PE_uleb128:
		return (uleb_extract(data, dotp, len, ret));
	case DW_EH_PE_sleb128:
		return (sleb_extract(data, dotp, len, (int64_t *)ret));
	default:
		*ret = 0;
		return (DW_BAD_ENCODING);
	}

	if (lsb) {
		/*
		 * Extract unaligned LSB formated data
		 */
		uint_t	cnt;

		result = 0;
		for (cnt = 0; cnt < fsize;
		    cnt++, dot++) {
			uint64_t val;

			if (dot > len)
				return (DW_OVERFLOW);
			val = data[dot];
			result |= val << (cnt * 8);
		}
	} else {
		/*
		 * Extract unaligned MSB formated data
		 */
		uint_t	cnt;
		result = 0;
		for (cnt = 0; cnt < fsize;
		    cnt++, dot++) {
			uint64_t val;

			if (dot > len)
				return (DW_OVERFLOW);
			val = data[dot];
			result |= val << ((fsize - cnt - 1) * 8);
		}
	}
	/*
	 * perform sign extension
	 */
	if ((ehe_flags & DW_EH_PE_signed) &&
	    (fsize < sizeof (uint64_t))) {
		int64_t	sresult;
		uint_t	bitshift;
		sresult = result;
		bitshift = (sizeof (uint64_t) - fsize) * 8;
		sresult = (sresult << bitshift) >> bitshift;
		result = sresult;
	}

	/*
	 * If value is relative to a base address, adjust it
	 */
	switch (ehe_flags & 0xf0) {
	case DW_EH_PE_pcrel:
		result += sh_base + sh_offset;
		break;

	/*
	 * datarel is relative to .eh_frame_hdr if within .eh_frame,
	 * but GOT if not.
	 */
	case DW_EH_PE_datarel:
		if (frame_hdr)
			result += sh_base;
		else
			result += dbase;
		break;
	}

	/* Truncate the result to its specified size */
	result = (result << ((sizeof (uint64_t) - fsize) * 8)) >>
	    ((sizeof (uint64_t) - fsize) * 8);

	*dotp = dot;
	*ret = result;
	return (DW_SUCCESS);
}
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License, Version 1.0 only
 * (the "License").  You may not use this file except in compliance
 * with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2003 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <sgs.h>

/*
 * classic Bernstein k=33 hash function
 *
 * This routine is to be used for internal hashing of strings.  It's not
 * to be confused with elf_hash() which is the required ELF hashing
 * tool for ELF structures.
 */
uint_t
sgs_str_hash(const char *str)
{
	uint_t	hash = 5381;
	int		c;

	while ((c = *str++) != 0)
		hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
	return (hash);
}
/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

#include <_string_table.h>
#include <strings.h>
#include <sgs.h>
#include <stdio.h>

/*
 * This file provides the interfaces to build a Str_tbl suitable for use by
 * either the sgsmsg message system, or a standard ELF string table (SHT_STRTAB)
 * as created by ld(1).
 *
 * There are two modes which can be used when constructing a string table:
 *
 *	st_new(0)
 *		standard string table - no compression.  This is the
 *		traditional, fast method.
 *
 *	st_new(FLG_STTAB_COMPRESS)
 *		builds a compressed string table which both eliminates
 *		duplicate strings, and permits strings with common suffixes
 *		(atexit vs. exit) to overlap in the table.  This provides space
 *		savings for many string tables.  Although more work than the
 *		traditional method, the algorithms used are designed to scale
 *		and keep any overhead at a minimum.
 *
 * These string tables are built with a common interface in a two-pass manner.
 * The first pass finds all of the strings required for the string-table and
 * calculates the size required for the final string table.
 *
 * The second pass allocates the string table, populates the strings into the
 * table and returns the offsets the strings have been assigned.
 *
 * The calling sequence to build and populate a string table is:
 *
 *		st_new();		// initialize strtab
 *
 *		st_insert(st1);		// first pass of strings ...
 *					// calculates size required for
 *					// string table
 *
 *		st_delstring(st?);	// remove string previously
 *					// inserted
 *		st_insert(stN);
 *
 *		st_getstrtab_sz();	// freezes strtab and computes
 *					// size of table.
 *
 *		st_setstrbuf();		// associates a final destination
 *					// for the string table
 *
 *		st_setstring(st1);	// populate the string table
 *		...			// offsets are based off of second
 *					// pass	through the string table
 *		st_setstring(stN);
 *
 *		st_destroy();		// tear down string table
 *					// structures.
 *
 * String Suffix Compression Algorithm:
 *
 *   Here's a quick high level overview of the Suffix String
 *   compression algorithm used.  First - the heart of the algorithm
 *   is a Hash table list which represents a dictionary of all unique
 *   strings inserted into the string table.  The hash function for
 *   this table is a standard string hash except that the hash starts
 *   at the last character in the string (&str[n - 1]) and works towards
 *   the first character in the function (&str[0]).  As we compute the
 *   HASH value for a given string, we also compute the hash values
 *   for all of the possible suffix strings for that string.
 *
 *   As we compute the hash - at each character see if the current
 *   suffix string for that hash is already present in the table.  If
 *   it is, and the string is a master string.  Then change that
 *   string to a suffix string of the new string being inserted.
 *
 *   When the final hash value is found (hash for str[0...n]), check
 *   to see if it is in the hash table - if so increment the reference
 *   count for the string.  If it is not yet in the table, insert a
 *   new hash table entry for a master string.
 *
 *   The above method will find all suffixes of a given string given
 *   that the strings are inserted from shortest to longest.  That is
 *   why this is a two phase method, we first collect all of the
 *   strings and store them based off of their length in an AVL tree.
 *   Once all of the strings have been submitted we then start the
 *   hash table build by traversing the AVL tree in order and
 *   inserting the strings from shortest to longest as described
 *   above.
 */

/* LINTLIBRARY */

static int
avl_len_compare(const void *n1, const void *n2)
{
	size_t	len1, len2;

	len1 = ((LenNode *)n1)->ln_strlen;
	len2 = ((LenNode *)n2)->ln_strlen;

	if (len1 == len2)
		return (0);
	if (len2 < len1)
		return (1);
	return (-1);
}

static int
avl_str_compare(const void *n1, const void *n2)
{
	const char	*str1, *str2;
	int		rc;

	str1 = ((StrNode *)n1)->sn_str;
	str2 = ((StrNode *)n2)->sn_str;

	rc = strcmp(str1, str2);
	if (rc > 0)
		return (1);
	if (rc < 0)
		return (-1);
	return (0);
}

/*
 * Return an initialized Str_tbl - returns NULL on failure.
 *
 * flags:
 *	FLG_STTAB_COMPRESS - build a compressed string table
 */
Str_tbl *
st_new(uint_t flags)
{
	Str_tbl	*stp;

	if ((stp = calloc(1, sizeof (*stp))) == NULL)
		return (NULL);

	/*
	 * Start with a leading '\0' - it's tradition.
	 */
	stp->st_strsize = stp->st_fullstrsize = stp->st_nextoff = 1;

	/*
	 * Do we compress this string table?
	 */
	stp->st_flags = flags;
	if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0)
		return (stp);

	if ((stp->st_lentree = calloc(1, sizeof (*stp->st_lentree))) == NULL)
		return (NULL);

	avl_create(stp->st_lentree, &avl_len_compare, sizeof (LenNode),
	    SGSOFFSETOF(LenNode, ln_avlnode));

	return (stp);
}

/*
 * Insert a new string into the Str_tbl.  There are two AVL trees used.
 *
 *  -	The first LenNode AVL tree maintains a tree of nodes based on string
 *	sizes.
 *  -	Each LenNode maintains a StrNode AVL tree for each string.  Large
 *	applications have been known to contribute thousands of strings of
 *	the same size.  Should strings need to be removed (-z ignore), then
 *	the string AVL tree makes this removal efficient and scalable.
 */
int
st_insert(Str_tbl *stp, const char *str)
{
	size_t		len;
	StrNode		*snp, sn = { 0 };
	LenNode		*lnp, ln = { 0 };
	avl_index_t	where;

	/*
	 * String table can't have been cooked
	 */
	assert((stp->st_flags & FLG_STTAB_COOKED) == 0);

	/*
	 * Null strings always point to the head of the string
	 * table - no reason to keep searching.
	 */
	if ((len = strlen(str)) == 0)
		return (0);

	stp->st_fullstrsize += len + 1;
	stp->st_strcnt++;

	if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0)
		return (0);

	/*
	 * From the controlling string table, determine which LenNode AVL node
	 * provides for this string length.  If the node doesn't exist, insert
	 * a new node to represent this string length.
	 */
	ln.ln_strlen = len;
	if ((lnp = avl_find(stp->st_lentree, &ln, &where)) == NULL) {
		if ((lnp = calloc(1, sizeof (*lnp))) == NULL)
			return (-1);

		if ((lnp->ln_strtree = calloc(1, sizeof (*lnp->ln_strtree))) ==
		    NULL) {
			free(lnp);
			return (-1);
		}

		lnp->ln_strlen = len;
		avl_insert(stp->st_lentree, lnp, where);

		avl_create(lnp->ln_strtree, &avl_str_compare, sizeof (StrNode),
		    SGSOFFSETOF(StrNode, sn_avlnode));
	}

	/*
	 * From the string length AVL node determine whether a StrNode AVL node
	 * provides this string.  If the node doesn't exist, insert a new node
	 * to represent this string.
	 */
	sn.sn_str = str;
	if ((snp = avl_find(lnp->ln_strtree, &sn, &where)) == NULL) {
		if ((snp = calloc(1, sizeof (*snp))) == NULL)
			return (-1);
		snp->sn_str = str;
		avl_insert(lnp->ln_strtree, snp, where);
	}
	snp->sn_refcnt++;

	return (0);
}

/*
 * Remove a previously inserted string from the Str_tbl.
 */
int
st_delstring(Str_tbl *stp, const char *str)
{
	size_t		len;
	LenNode		*lnp, ln = { 0 };
	StrNode		*snp, sn = { 0 };

	/*
	 * String table can't have been cooked
	 */
	assert((stp->st_flags & FLG_STTAB_COOKED) == 0);

	len = strlen(str);
	stp->st_fullstrsize -= len + 1;

	if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0)
		return (0);

	/*
	 * Determine which LenNode AVL node provides for this string length.
	 */
	ln.ln_strlen = len;
	if ((lnp = avl_find(stp->st_lentree, &ln, 0)) != NULL) {
		sn.sn_str = str;
		if ((snp = avl_find(lnp->ln_strtree, &sn, 0)) != NULL) {
			/*
			 * Reduce the reference count, and if zero remove the
			 * node.
			 */
			if (--snp->sn_refcnt == 0)
				avl_remove(lnp->ln_strtree, snp);
			return (0);
		}
	}

	/*
	 * No strings of this length, or no string itself - someone goofed.
	 */
	return (-1);
}

/*
 * Tear down a String_Table structure.
 */
void
st_destroy(Str_tbl *stp)
{
	Str_hash	*sthash, *psthash;
	Str_master	*mstr, *pmstr;
	uint_t		i;

	/*
	 * cleanup the master strings
	 */
	for (mstr = stp->st_mstrlist, pmstr = 0; mstr;
	    mstr = mstr->sm_next) {
		if (pmstr)
			free(pmstr);
		pmstr = mstr;
	}
	if (pmstr)
		free(pmstr);

	if (stp->st_hashbcks) {
		for (i = 0; i < stp->st_hbckcnt; i++) {
			for (sthash = stp->st_hashbcks[i], psthash = 0;
			    sthash; sthash = sthash->hi_next) {
				if (psthash)
					free(psthash);
				psthash = sthash;
			}
			if (psthash)
				free(psthash);
		}
		free(stp->st_hashbcks);
	}
	free(stp);
}

/*
 * Hash a single additional character into hashval, separately so we can
 * iteratively get suffix hashes.  See st_string_hash and st_hash_insert
 */
static inline uint_t
st_string_hashround(uint_t hashval, char c)
{
	/* h = ((h * 33) + c) */
	return (((hashval << 5) + hashval) + c);
}

/*
 * We use a classic 'Bernstein k=33' hash function.  But
 * instead of hashing from the start of the string to the
 * end, we do it in reverse.
 *
 * This way we are essentially building all of the
 * suffix hashvalues as we go.  We can check to see if
 * any suffixes already exist in the tree as we generate
 * the hash.
 */
static inline uint_t
st_string_hash(const char *str)
{
	uint_t hashval = HASHSEED;
	size_t stlen = strlen(str);

	/* We should never be hashing the NUL string */
	assert(stlen > 0);

	for (int i = stlen; i >= 0; i--) {
		assert(i <= stlen); /* not unsigned->signed truncated */
		hashval = st_string_hashround(hashval, str[i]);
	}

	return (hashval);
}

/*
 * For a given string - copy it into the buffer associated with the string
 * table - and return the offset it has been assigned in stoff.
 *
 * If a value of '-1' is returned - the string was not found in
 * the Str_tbl.
 */
int
st_setstring(Str_tbl *stp, const char *str, size_t *stoff)
{
	size_t		stlen;
	uint_t		hashval;
	Str_hash	*sthash;
	Str_master	*mstr;

	/*
	 * String table *must* have been previously cooked
	 */
	assert(stp->st_strbuf != NULL);

	assert(stp->st_flags & FLG_STTAB_COOKED);
	stlen = strlen(str);
	/*
	 * Null string always points to head of string table
	 */
	if (stlen == 0) {
		if (stoff != NULL)
			*stoff = 0;
		return (0);
	}

	if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0) {
		size_t		_stoff;

		stlen++;	/* count for trailing '\0' */
		_stoff = stp->st_nextoff;
		/*
		 * Have we overflowed our assigned buffer?
		 */
		if ((_stoff + stlen) > stp->st_fullstrsize)
			return (-1);
		memcpy(stp->st_strbuf + _stoff, str, stlen);
		if (stoff != NULL)
			*stoff = _stoff;
		stp->st_nextoff += stlen;
		return (0);
	}

	/*
	 * Calculate reverse hash for string.
	 */
	hashval = st_string_hash(str);

	for (sthash = stp->st_hashbcks[hashval % stp->st_hbckcnt]; sthash;
	    sthash = sthash->hi_next) {
		const char	*hstr;

		if (sthash->hi_hashval != hashval)
			continue;

		hstr = &sthash->hi_mstr->sm_str[sthash->hi_mstr->sm_strlen -
		    sthash->hi_strlen];
		if (strcmp(str, hstr) == 0)
			break;
	}

	/*
	 * Did we find the string?
	 */
	if (sthash == 0)
		return (-1);

	/*
	 * Has this string been copied into the string table?
	 */
	mstr = sthash->hi_mstr;
	if (mstr->sm_stroff == 0) {
		size_t	mstrlen = mstr->sm_strlen + 1;

		mstr->sm_stroff = stp->st_nextoff;

		/*
		 * Have we overflowed our assigned buffer?
		 */
		if ((mstr->sm_stroff + mstrlen) > stp->st_fullstrsize)
			return (-1);

		(void) memcpy(stp->st_strbuf + mstr->sm_stroff,
		    mstr->sm_str, mstrlen);
		stp->st_nextoff += mstrlen;
	}

	/*
	 * Calculate offset of (sub)string.
	 */
	if (stoff != NULL)
		*stoff = mstr->sm_stroff + mstr->sm_strlen - sthash->hi_strlen;

	return (0);
}

static int
st_hash_insert(Str_tbl *stp, const char *str, size_t len)
{
	int		i;
	uint_t		hashval = HASHSEED;
	uint_t		bckcnt = stp->st_hbckcnt;
	Str_hash	**hashbcks = stp->st_hashbcks;
	Str_hash	*sthash;
	Str_master	*mstr = 0;

	for (i = len; i >= 0; i--) {
		/*
		 * Build up 'hashval' character by character, so we always
		 * have the hash of the current string suffix
		 */
		hashval = st_string_hashround(hashval, str[i]);

		for (sthash = hashbcks[hashval % bckcnt];
		    sthash; sthash = sthash->hi_next) {
			const char	*hstr;
			Str_master	*_mstr;

			if (sthash->hi_hashval != hashval)
				continue;

			_mstr = sthash->hi_mstr;
			hstr = &_mstr->sm_str[_mstr->sm_strlen -
			    sthash->hi_strlen];

			if (strcmp(&str[i], hstr))
				continue;

			if (i == 0) {
				/*
				 * Entry already in table, increment refcnt and
				 * get out.
				 */
				sthash->hi_refcnt++;
				return (0);
			} else {
				/*
				 * If this 'suffix' is presently a 'master
				 * string, then take over it's record.
				 */
				if (sthash->hi_strlen == _mstr->sm_strlen) {
					/*
					 * we should only do this once.
					 */
					assert(mstr == 0);
					mstr = _mstr;
				}
			}
		}
	}

	/*
	 * Do we need a new master string, or can we take over
	 * one we already found in the table?
	 */
	if (mstr == 0) {
		/*
		 * allocate a new master string
		 */
		if ((mstr = calloc(1, sizeof (*mstr))) == NULL)
			return (-1);
		mstr->sm_next = stp->st_mstrlist;
		stp->st_mstrlist = mstr;
		stp->st_strsize += len + 1;
	} else {
		/*
		 * We are taking over a existing master string, the string size
		 * only increments by the difference between the current string
		 * and the previous master.
		 */
		assert(len > mstr->sm_strlen);
		stp->st_strsize += len - mstr->sm_strlen;
	}

	if ((sthash = calloc(1, sizeof (*sthash))) == NULL)
		return (-1);

	mstr->sm_hashval = sthash->hi_hashval = hashval;
	mstr->sm_strlen = sthash->hi_strlen = len;
	mstr->sm_str = str;
	sthash->hi_refcnt = 1;
	sthash->hi_mstr = mstr;

	/*
	 * Insert string element into head of hash list
	 */
	hashval = hashval % bckcnt;
	sthash->hi_next = hashbcks[hashval];
	hashbcks[hashval] = sthash;
	return (0);
}

/*
 * Return amount of space required for the string table.
 */
size_t
st_getstrtab_sz(Str_tbl *stp)
{
	assert(stp->st_fullstrsize > 0);

	if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0) {
		stp->st_flags |= FLG_STTAB_COOKED;
		return (stp->st_fullstrsize);
	}

	if ((stp->st_flags & FLG_STTAB_COOKED) == 0) {
		LenNode		*lnp;
		void		*cookie;

		stp->st_flags |= FLG_STTAB_COOKED;
		/*
		 * allocate a hash table about the size of # of
		 * strings input.
		 */
		stp->st_hbckcnt = findprime(stp->st_strcnt);
		if ((stp->st_hashbcks = calloc(stp->st_hbckcnt,
		    sizeof (*stp->st_hashbcks))) == NULL)
			return (0);

		/*
		 * We now walk all of the strings in the list, from shortest to
		 * longest, and insert them into the hashtable.
		 */
		if ((lnp = avl_first(stp->st_lentree)) == NULL) {
			/*
			 * Is it possible we have an empty string table, if so,
			 * the table still contains '\0', so return the size.
			 */
			if (avl_numnodes(stp->st_lentree) == 0) {
				assert(stp->st_strsize == 1);
				return (stp->st_strsize);
			}
			return (0);
		}

		while (lnp) {
			StrNode	*snp;

			/*
			 * Walk the string lists and insert them into the hash
			 * list.  Once a string is inserted we no longer need
			 * it's entry, so the string can be freed.
			 */
			for (snp = avl_first(lnp->ln_strtree); snp;
			    snp = AVL_NEXT(lnp->ln_strtree, snp)) {
				if (st_hash_insert(stp, snp->sn_str,
				    lnp->ln_strlen) == -1)
					return (0);
			}

			/*
			 * Now that the strings have been copied, walk the
			 * StrNode tree and free all the AVL nodes.  Note,
			 * avl_destroy_nodes() beats avl_remove() as the
			 * latter balances the nodes as they are removed.
			 * We just want to tear the whole thing down fast.
			 */
			cookie = NULL;
			while ((snp = avl_destroy_nodes(lnp->ln_strtree,
			    &cookie)) != NULL)
				free(snp);
			avl_destroy(lnp->ln_strtree);
			free(lnp->ln_strtree);
			lnp->ln_strtree = NULL;

			/*
			 * Move on to the next LenNode.
			 */
			lnp = AVL_NEXT(stp->st_lentree, lnp);
		}

		/*
		 * Now that all of the strings have been freed, walk the
		 * LenNode tree and free all of the AVL nodes.  Note,
		 * avl_destroy_nodes() beats avl_remove() as the latter
		 * balances the nodes as they are removed. We just want to
		 * tear the whole thing down fast.
		 */
		cookie = NULL;
		while ((lnp = avl_destroy_nodes(stp->st_lentree,
		    &cookie)) != NULL)
			free(lnp);
		avl_destroy(stp->st_lentree);
		free(stp->st_lentree);
		stp->st_lentree = 0;
	}

	assert(stp->st_strsize > 0);
	assert(stp->st_fullstrsize >= stp->st_strsize);

	return (stp->st_strsize);
}

const char *
st_getstrbuf(Str_tbl *stp)
{
	return (stp->st_strbuf);
}


/*
 * Associate a buffer with a string table.
 */
int
st_setstrbuf(Str_tbl *stp, char *stbuf, size_t bufsize)
{
	assert(stp->st_flags & FLG_STTAB_COOKED);

	if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0) {
		if (bufsize < stp->st_fullstrsize)
			return (-1);
	} else {
		if (bufsize < stp->st_strsize)
			return (-1);
	}

	stp->st_strbuf = stbuf;
#ifdef	DEBUG
	/*
	 * for debug builds - start with a stringtable filled in
	 * with '0xff'.  This makes it very easy to spot unfilled
	 * holes in the strtab.
	 */
	memset(stbuf, 0xff, bufsize);
	stbuf[0] = '\0';
#else
	memset(stbuf, 0x0, bufsize);
#endif
	return (0);
}

/*
 * Populate the buffer with all strings from stp.
 * The table must be compressed and cooked
 */
void
st_setallstrings(Str_tbl *stp)
{
	assert(stp->st_strbuf != NULL);
	assert((stp->st_flags & FLG_STTAB_COOKED));
	assert((stp->st_flags & FLG_STTAB_COMPRESS));

	for (Str_master *str = stp->st_mstrlist; str != NULL;
	    str = str->sm_next) {
		int res __maybe_unused;

		res = st_setstring(stp, str->sm_str, NULL);
		assert(res == 0);
	}
}

/*
 * Find str in the given table
 * return it's offset, or -1
 */
off_t
st_findstring(Str_tbl *stp, const char *needle)
{
	uint_t hashval;
	Str_hash *sthash;
	Str_master *mstr;

	assert(stp->st_strbuf != NULL);
	assert((stp->st_flags & FLG_STTAB_COOKED));

	/* The NUL string is always first */
	if (needle[0] == '\0')
		return (0);

	/* In the uncompressed case we must linear search */
	if ((stp->st_flags & FLG_STTAB_COMPRESS) == 0) {
		const char *str, *end;

		end = stp->st_strbuf + stp->st_fullstrsize;

		for (str = stp->st_strbuf; str < end;
		    str += strlen(str) + 1) {
			if (strcmp(str, needle) == 0)
				return (str - stp->st_strbuf);
		}

		return (-1);
	}

	hashval = st_string_hash(needle);

	for (sthash = stp->st_hashbcks[hashval % stp->st_hbckcnt];
	    sthash != NULL;
	    sthash = sthash->hi_next) {
		const char	*hstr;

		if (sthash->hi_hashval != hashval)
			continue;

		hstr = &sthash->hi_mstr->sm_str[sthash->hi_mstr->sm_strlen -
		    sthash->hi_strlen];
		if (strcmp(needle, hstr) == 0)
			break;
	}

	/*
	 * Did we find the string?
	 */
	if (sthash == NULL)
		return (-1);

	mstr = sthash->hi_mstr;
	assert(mstr->sm_stroff != 0);

	/*
	 * Calculate offset of (sub)string.
	 */
	return (mstr->sm_stroff + mstr->sm_strlen - sthash->hi_strlen);
}