Macintosh-Tools
/
executor
mirror of https://github.com/ctm/executor.git
1
0
Fork 0
Code Issues Projects Releases Wiki Activity
executor/src/pef_hash.c

428 lines
10 KiB
C
Raw Permalink Blame History

/* Copyright 2000 by Abacus Research and
* Development, Inc. All rights reserved.
*/
#if !defined (OMIT_RCSID_STRINGS)
char ROMlib_rcsid_pef_hash[] =
"$Id: pef_hash.c 88 2005-05-25 03:59:37Z ctm $";
#endif
#include "rsys/common.h"
#include "MemoryMgr.h"
#include "rsys/pef.h"
#include "rsys/cfm.h"
#include <math.h>
/*
*
* IM 8-43 provides C code that uses a loop to determine the exponent
* for a given number of symbols. This loop is equivalent:
*
* static UInt8
* PEFComputeHashTableExponent (int32 exportCount)
* {
* int exponent;
*
* for (exponent = 0;
* exponent < kExponentLimit;
* ++exponent)
* if ((exportCount / (1 << exponent)) < kAverageChainLimit)
* break;
*
* return exponent;
* }
*
* We get the same values by doing a little math.
*
*/
#if !defined (__USE_ISOC9X)
PRIVATE uint32
floor_log2 (double d)
{
uint32 retval;
if (d <= 1)
retval = 0;
else
{
uint32 u;
u = d;
retval = 31;
while (!(u & 0x80000000))
{
u <<= 1;
--retval;
}
}
return retval;
}
#endif
PRIVATE uint8
PEFComputeHashTableExponent (int32 count)
{
int retval;
if (count < kAverageChainLimit)
retval = 0;
else if (count >= kAverageChainLimit * (1 << kExponentLimit))
retval = kExponentLimit;
else
#if defined (__USE_ISOC9X)
retval = floor (log2 ((double) count / kAverageChainLimit)) + 1;
#else
retval = floor_log2 ((double) count / kAverageChainLimit) + 1;
#endif
return retval;
}
/* 8-41 has a hash-word function that will produce the same values as
the following code */
#define PseudoRotate(x) \
({ \
int32 _x; \
\
_x = (x); \
(_x << 1) - (_x >> 16); \
})
static uint32
PEFComputeHashWord (const unsigned char *orig_p, uint32 namemax)
{
uint32 retval;
const unsigned char *p;
unsigned char c;
int32 val;
val = 0;
for (p = orig_p; (c = *p++) && namemax-- > 0;)
val = PseudoRotate (val) ^ c;
retval = (((p - orig_p - 1) << kPEFHashLengthShift) |
((val ^ (val >> 16)) & kPEFHashValueMask));
return retval;
}
#define PEFHashTableIndex(fullHashWord,hashTablePower) \
({ \
typeof (fullHashWord) _fullHashWord = (fullHashWord); \
typeof (hashTablePower) _hashTablePower = (hashTablePower); \
\
(_fullHashWord^(_fullHashWord >> _hashTablePower)) & \
((1 << _hashTablePower) - 1); \
})
/*
* This is used for pseudo-libraries (MathLib, InterfaceLib)
*/
typedef struct
{
int hash_index;
uint32 hash_word;
uint32 class_and_name_x;
syn68k_addr_t value;
}
sort_entry_t;
PRIVATE int
hash_index_compare (const void *p1, const void *p2)
{
const sort_entry_t *sp1, *sp2;
int retval;
sp1 = p1;
sp2 = p2;
retval = sp1->hash_index - sp2->hash_index;
return retval;
}
PRIVATE void
update_export_hash_table (uint32 *hashp, int hash_index, int first_index,
int run_count)
{
uint32 new_value;
new_value = ((run_count << CHAIN_COUNT_SHIFT) |
(first_index & FIRST_INDEX_MASK));
hashp[hash_index] = CL (new_value);
}
PUBLIC PEFLoaderInfoHeader_t *
ROMlib_build_pef_hash (const map_entry_t table[], int count)
{
PEFLoaderInfoHeader_t *retval;
uint32 hash_power;
int n_hash_entries;
uint32 hash_offset, export_offset, symbol_table_offset, string_table_offset;
int hash_length, export_length, symbol_table_length, string_table_length;
Size n_bytes_needed;
uint32 *hashp;
uint32 *exportp;
PEFExportedSymbol *symbol_tablep;
char *string_tablep;
int i;
hash_power = PEFComputeHashTableExponent (count);
n_hash_entries = 1 << hash_power;
hash_offset = sizeof (PEFLoaderInfoHeader_t);
hash_length = sizeof (*hashp) * n_hash_entries;
export_offset = hash_offset + hash_length;
export_length = sizeof (*exportp) * count;
symbol_table_offset = export_offset + export_length;
symbol_table_length = sizeof (*symbol_tablep) * count;
string_table_offset = symbol_table_offset + symbol_table_length;
string_table_length = 0;
for (i = 0; i < count; ++i)
string_table_length += strlen (table[i].symbol_name);
n_bytes_needed = (string_table_offset + string_table_length);
retval = (typeof (retval)) NewPtrSysClear (n_bytes_needed);
if (retval)
{
sort_entry_t *sorted;
int previous_hash_index;
int run_count;
int previous_index_of_first_element;
uint32 name_offset;
PEFLIH_MAIN_SECTION_X (retval) = CLC (-1);
PEFLIH_MAIN_OFFSET_X (retval) = CLC (-1);
PEFLIH_INIT_SECTION_X (retval) = CLC (-1);
PEFLIH_INIT_OFFSET_X (retval) = CLC (-1);
PEFLIH_TERM_SECTION_X (retval) = CLC (-1);
PEFLIH_TERM_OFFSET_X (retval) = CLC (-1);
/* totalImportedSymbolCount, relocSectionCount, relocInstrOffset
are all already 0 */
PEFLIH_STRINGS_OFFSET_X (retval) = CL (string_table_offset);
PEFLIH_HASH_OFFSET_X (retval) = CL (hash_offset);
PEFLIH_HASH_TABLE_POWER_X (retval) = CL (hash_power);
PEFLIH_SYMBOL_COUNT_X (retval) = CL (count);
hashp = (typeof (hashp)) ((char *) retval + hash_offset);
exportp = (typeof (exportp)) ((char *) retval + export_offset);
symbol_tablep = ((typeof (symbol_tablep))
((char *) retval + symbol_table_offset));
string_tablep = ((typeof (string_tablep))
((char *) retval + string_table_offset));
sorted = alloca (sizeof *sorted * count);
name_offset = 0;
for (i = 0; i < count; ++i)
{
int length;
sorted[i].hash_word =
PEFComputeHashWord ((unsigned char *) table[i].symbol_name,
strlen (table[i].symbol_name));
sorted[i].hash_index = PEFHashTableIndex (sorted[i].hash_word,
hash_power);
sorted[i].class_and_name_x = CL ((kPEFTVectSymbol << 24) |
name_offset);
sorted[i].value = (uint32) RM (&table[i].value);
length = strlen (table[i].symbol_name);
memcpy (string_tablep + name_offset, table[i].symbol_name, length);
name_offset += length;
}
qsort (sorted, count, sizeof *sorted, hash_index_compare);
previous_hash_index = -1;
#if !defined (LETGCCWAIL)
previous_index_of_first_element = 0;
run_count = 0;
#endif
for (i = 0; i < count; ++i)
{
if (sorted[i].hash_index == previous_hash_index)
++run_count;
else
{
if (previous_hash_index >= 0)
update_export_hash_table (hashp, previous_hash_index,
previous_index_of_first_element,
run_count);
run_count = 1;
previous_hash_index = sorted[i].hash_index;
previous_index_of_first_element = i;
}
exportp[i] = sorted[i].hash_word;
PEFEXS_CLASS_AND_NAME_X (&symbol_tablep[i]) =
sorted[i].class_and_name_x;
PEFEXS_SYMBOL_VALUE_X (&symbol_tablep[i]) = sorted[i].value;
PEFEXS_SECTION_INDEX_X (&symbol_tablep[i]) = CWC (-2);
}
update_export_hash_table (hashp, previous_hash_index,
previous_index_of_first_element,
run_count);
}
return retval;
}
#if 0
PEFExportedSymbol *
lookup_by_index (const pef_hash_t *hashp, int index,
const char **namep, int *namelen)
{
PEFExportedSymbol *retval;
if (index >= hashp->n_symbols)
retval = NULL;
else
{
int name_offset;
retval = &hashp->symbol_table[index];
name_offset = CL (retval->classAndName) & NAME_MASK;
*namep = hashp->symbol_names + name_offset;
*namelen = CL (hashp->export_key_table[index]) >> 16;
}
return retval;
}
#endif
#define SYMBOL_NAME(pefexp, str) (str + PEFEXS_NAME (pefexp))
PRIVATE PEFExportedSymbol *
lookup_by_name (const ConnectionID connp,
const char *name, int name_len)
{
uint32 hash_word;
uint32 hash_index;
uint32 chain_count_and_first_index;
int chain_count;
int index;
int past_index;
uint32 hash_word_swapped;
PEFExportedSymbol *retval;
PEFLoaderInfoHeader_t *lihp;
uint32 *hash_entries;
uint32 *export_key_table;
PEFExportedSymbol *symbol_table;
uint32 offset;
const char *string_tablep;
#if 1
#warning get rid of this eventually
if (connp == (ConnectionID) 0x12348765)
return NULL;
#endif
lihp = connp->lihp;
hash_word = PEFComputeHashWord ((unsigned char *) name, name_len);
hash_index = PEFHashTableIndex (hash_word, PEFLIH_HASH_TABLE_POWER (lihp));
offset = PEFLIH_HASH_OFFSET (lihp);
hash_entries = (typeof (hash_entries)) ((char *) lihp + offset);
offset += sizeof *hash_entries * (1 << PEFLIH_HASH_TABLE_POWER (lihp));
export_key_table = (typeof (export_key_table)) ((char *) lihp + offset);
offset += sizeof *export_key_table * PEFLIH_SYMBOL_COUNT (lihp);
symbol_table = (typeof (symbol_table)) ((char *) lihp + offset);
offset = PEFLIH_STRINGS_OFFSET (lihp);
string_tablep = (typeof (string_tablep)) ((char *) lihp + offset);
chain_count_and_first_index = CL (hash_entries[hash_index]);
chain_count = ((chain_count_and_first_index >> CHAIN_COUNT_SHIFT)
& CHAIN_COUNT_MASK);
index = ((chain_count_and_first_index >> FIRST_INDEX_SHIFT)
& FIRST_INDEX_MASK);
hash_word_swapped = CL (hash_word);
for (past_index = index + chain_count;
index < past_index &&
(export_key_table[index] != hash_word_swapped ||
strncmp (name, SYMBOL_NAME(&symbol_table[index], string_tablep),
name_len) != 0);
++index)
;
if (index >= past_index)
retval = NULL;
else
retval = &symbol_table[index];
return retval;
}
P2 (PUBLIC pascal trap, OSErr, CountSymbols, ConnectionID, id,
LONGINT *, countp)
{
OSErr retval;
/* TODO */
warning_unimplemented (NULL_STRING);
retval = paramErr;
return retval;
}
P5 (PUBLIC pascal trap, OSErr, GetIndSymbol, ConnectionID, id,
LONGINT, index, Str255, name, Ptr *, addrp, SymClass *, classp)
{
OSErr retval;
/* TODO */
warning_unimplemented (NULL_STRING);
retval = paramErr;
return retval;
}
P4 (PUBLIC pascal trap, OSErr, FindSymbol, ConnectionID, connID,
Str255, symName, Ptr *, symAddr, SymClass *, symClass)
{
OSErr retval;
PEFExportedSymbol *pefs;
pefs = lookup_by_name (connID, (char *) symName+1, symName[0]);
if (!pefs)
retval = fragSymbolNotFound;
else
{
int section_index;
uint32 val;
if (symClass)
*symClass = *(SymClass *)&PEFEXS_CLASS_AND_NAME_X (pefs);
section_index = PEFEXS_SECTION_INDEX (pefs);
val = PEFEXS_SYMBOL_VALUE (pefs);
switch (section_index)
{
case -2: /* absolute address */
*symAddr = (Ptr) CL (val);
break;
case -3: /* re-exported */
warning_unimplemented ("name = '%.*s', val = 0x%x", symName[0],
symName+1, val);
*symAddr = (Ptr) CL (val);
break;
default:
{
uint32 sect_start;
sect_start = connID->sects[section_index].start;
*symAddr = (Ptr) CL (val + sect_start);
}
break;
}
retval = noErr;
}
return retval;
}
Reference in New Issue View Git Blame Copy Permalink