objc-shared-cache.h [plain text]
#ifndef _OBJC_SELOPT_H
#define _OBJC_SELOPT_H
#include <stdint.h>
#include <stdlib.h>
#ifdef CLOSURE_SELOPT_WRITE
#include "Array.h"
#include "Map.h"
#endif
#ifdef SELOPT_WRITE
#include <unordered_map>
#endif
#ifndef STATIC_ASSERT
# define STATIC_ASSERT(x) _STATIC_ASSERT2(x, __LINE__)
# define _STATIC_ASSERT2(x, line) _STATIC_ASSERT3(x, line)
# define _STATIC_ASSERT3(x, line) \
typedef struct { \
int _static_assert[(x) ? 0 : -1]; \
} _static_assert_ ## line __attribute__((unavailable))
#endif
#define SELOPT_DEBUG 0
#define S32(x) x = little_endian ? OSSwapHostToLittleInt32(x) : OSSwapHostToBigInt32(x)
#define S64(x) x = little_endian ? OSSwapHostToLittleInt64(x) : OSSwapHostToBigInt64(x)
namespace objc_opt {
typedef int32_t objc_stringhash_offset_t;
typedef uint8_t objc_stringhash_check_t;
static uint64_t lookup8( uint8_t *k, size_t length, uint64_t level);
#if defined(SELOPT_WRITE) || defined(CLOSURE_SELOPT_WRITE)
struct __attribute__((packed)) perfect_hash {
uint32_t capacity;
uint32_t occupied;
uint32_t shift;
uint32_t mask;
uint64_t salt;
uint32_t scramble[256];
dyld3::OverflowSafeArray<uint8_t> tab;
perfect_hash() { }
~perfect_hash() { }
};
struct eqstr {
bool operator()(const char* s1, const char* s2) const {
return strcmp(s1, s2) == 0;
}
};
struct hashstr {
size_t operator()(const char *s) const {
return (size_t)lookup8((uint8_t *)s, strlen(s), 0);
}
};
#endif // defined(SELOPT_WRITE) || defined(CLOSURE_SELOPT_WRITE)
#ifdef SELOPT_WRITE
typedef std::unordered_map<const char *, uint64_t, hashstr, eqstr> string_map;
typedef std::unordered_map<const char *, uint64_t, hashstr, eqstr> legacy_protocol_map;
typedef std::unordered_multimap<const char *, std::pair<uint64_t, uint64_t>, hashstr, eqstr> protocol_map;
typedef std::unordered_multimap<const char *, std::pair<uint64_t, uint64_t>, hashstr, eqstr> class_map;
static void make_perfect(const string_map& strings, perfect_hash& phash);
#endif // defined(SELOPT_WRITE)
struct __attribute__((packed)) objc_stringhash_t {
uint32_t capacity;
uint32_t occupied;
uint32_t shift;
uint32_t mask;
uint32_t unused1; uint32_t unused2; uint64_t salt;
uint32_t scramble[256];
uint8_t tab[0];
objc_stringhash_check_t *checkbytes() { return (objc_stringhash_check_t *)&tab[mask+1]; }
const objc_stringhash_check_t *checkbytes() const { return (const objc_stringhash_check_t *)&tab[mask+1]; }
objc_stringhash_offset_t *offsets() { return (objc_stringhash_offset_t *)&checkbytes()[capacity]; }
const objc_stringhash_offset_t *offsets() const { return (const objc_stringhash_offset_t *)&checkbytes()[capacity]; }
uint32_t hash(const char *key, size_t keylen) const
{
uint64_t val = lookup8((uint8_t*)key, keylen, salt);
uint32_t index = (uint32_t)(val>>shift) ^ scramble[tab[val&mask]];
return index;
}
uint32_t hash(const char *key) const
{
return hash(key, strlen(key));
}
objc_stringhash_check_t checkbyte(const char *key, size_t keylen) const
{
return
((key[0] & 0x7) << 5)
|
((uint8_t)keylen & 0x1f);
}
objc_stringhash_check_t checkbyte(const char *key) const
{
return checkbyte(key, strlen(key));
}
#define INDEX_NOT_FOUND (~(uint32_t)0)
uint32_t getIndex(const char *key) const
{
size_t keylen = strlen(key);
uint32_t h = hash(key, keylen);
objc_stringhash_check_t h_check = checkbytes()[h];
objc_stringhash_check_t key_check = checkbyte(key, keylen);
bool check_fail = (h_check != key_check);
#if ! SELOPT_DEBUG
if (check_fail) return INDEX_NOT_FOUND;
#endif
objc_stringhash_offset_t offset = offsets()[h];
if (offset == 0) return INDEX_NOT_FOUND;
const char *result = (const char *)this + offset;
if (0 != strcmp(key, result)) return INDEX_NOT_FOUND;
#if SELOPT_DEBUG
if (check_fail) abort();
#endif
return h;
}
#ifdef SELOPT_WRITE
size_t size()
{
return sizeof(objc_stringhash_t)
+ mask+1
+ capacity * sizeof(objc_stringhash_check_t)
+ capacity * sizeof(objc_stringhash_offset_t);
}
void byteswap(bool little_endian)
{
for (uint32_t i = 0; i < 256; i++) {
S32(scramble[i]);
}
objc_stringhash_offset_t *o = offsets();
for (uint32_t i = 0; i < capacity; i++) {
S32(o[i]);
}
S32(capacity);
S32(occupied);
S32(shift);
S32(mask);
S64(salt);
}
const char *write(uint64_t base, size_t remaining, string_map& strings)
{
if (sizeof(objc_stringhash_t) > remaining) {
return "selector section too small (metadata not optimized)";
}
if (strings.size() == 0) {
bzero(this, sizeof(objc_stringhash_t));
return NULL;
}
perfect_hash phash;
make_perfect(strings, phash);
if (phash.capacity == 0) {
return "perfect hash failed (metadata not optimized)";
}
capacity = phash.capacity;
occupied = phash.occupied;
shift = phash.shift;
mask = phash.mask;
unused1 = 0;
unused2 = 0;
salt = phash.salt;
if (size() > remaining) {
return "selector section too small (metadata not optimized)";
}
for (uint32_t i = 0; i < 256; i++) {
scramble[i] = phash.scramble[i];
}
for (uint32_t i = 0; i < phash.mask+1; i++) {
tab[i] = phash.tab[i];
}
for (uint32_t i = 0; i < phash.capacity; i++) {
offsets()[i] = 0;
}
for (uint32_t i = 0; i < phash.capacity; i++) {
checkbytes()[i] = 0;
}
# define SHIFT (64 - 8*sizeof(objc_stringhash_offset_t))
string_map::const_iterator s;
for (s = strings.begin(); s != strings.end(); ++s) {
int64_t offset = s->second - base;
if ((offset<<SHIFT)>>SHIFT != offset) {
return "selector offset too big (metadata not optimized)";
}
uint32_t h = hash(s->first);
offsets()[h] = (objc_stringhash_offset_t)offset;
checkbytes()[h] = checkbyte(s->first);
}
# undef SHIFT
return NULL;
}
#endif
};
struct objc_selopt_t : objc_stringhash_t {
const char* getEntryForIndex(uint32_t index) const {
return (const char *)this + offsets()[index];
}
uint32_t getIndexForKey(const char *key) const {
return getIndex(key);
}
uint32_t getSentinelIndex() const {
return INDEX_NOT_FOUND;
}
const char* get(const char *key) const
{
uint32_t h = getIndex(key);
if (h == INDEX_NOT_FOUND) return NULL;
return getEntryForIndex(h);
}
size_t usedCount() const {
return capacity;
}
};
struct objc_classheader_t {
objc_stringhash_offset_t clsOffset;
objc_stringhash_offset_t hiOffset;
bool isDuplicate() const { return clsOffset & 1; }
uint32_t duplicateCount() const { return clsOffset >> 1; }
uint32_t duplicateIndex() const { return hiOffset; }
};
struct objc_clsopt_t : objc_stringhash_t {
objc_classheader_t *classOffsets() { return (objc_classheader_t *)&offsets()[capacity]; }
const objc_classheader_t *classOffsets() const { return (const objc_classheader_t *)&offsets()[capacity]; }
uint32_t& duplicateCount() { return *(uint32_t *)&classOffsets()[capacity]; }
const uint32_t& duplicateCount() const { return *(const uint32_t *)&classOffsets()[capacity]; }
objc_classheader_t *duplicateOffsets() { return (objc_classheader_t *)(&duplicateCount()+1); }
const objc_classheader_t *duplicateOffsets() const { return (const objc_classheader_t *)(&duplicateCount()+1); }
const char* getClassNameForIndex(uint32_t index) const {
return (const char *)this + offsets()[index];
}
void* getClassForIndex(uint32_t index, uint32_t duplicateIndex) const {
const objc_classheader_t& clshi = classOffsets()[index];
if (! clshi.isDuplicate()) {
return (void *)((const char *)this + clshi.clsOffset);
}
else {
const objc_classheader_t *list = &duplicateOffsets()[clshi.duplicateIndex()];
return (void *)((const char *)this + list[duplicateIndex].clsOffset);
}
}
uint32_t getClassHeaderAndIndex(const char *key, void*& cls, void*& hi, uint32_t& index) const
{
uint32_t h = getIndex(key);
if (h == INDEX_NOT_FOUND) {
cls = NULL;
hi = NULL;
index = 0;
return 0;
}
index = h;
const objc_classheader_t& clshi = classOffsets()[h];
if (! clshi.isDuplicate()) {
cls = (void *)((const char *)this + clshi.clsOffset);
hi = (void *)((const char *)this + clshi.hiOffset);
return 1;
}
else {
cls = NULL;
hi = NULL;
return clshi.duplicateCount();
}
}
void getClassesAndHeaders(const char *key, void **cls, void **hi) const
{
uint32_t h = getIndex(key);
if (h == INDEX_NOT_FOUND) return;
const objc_classheader_t& clshi = classOffsets()[h];
if (! clshi.isDuplicate()) {
cls[0] = (void *)((const char *)this + clshi.clsOffset);
hi[0] = (void *)((const char *)this + clshi.hiOffset);
}
else {
uint32_t count = clshi.duplicateCount();
const objc_classheader_t *list =
&duplicateOffsets()[clshi.duplicateIndex()];
for (uint32_t i = 0; i < count; i++) {
cls[i] = (void *)((const char *)this + list[i].clsOffset);
hi[i] = (void *)((const char *)this + list[i].hiOffset);
}
}
}
uint32_t getClassAndHeader(const char *key, void*& cls, void*& hi) const
{
uint32_t unusedIndex = 0;
return getClassHeaderAndIndex(key, cls, hi, unusedIndex);
}
#ifdef SELOPT_WRITE
size_t size()
{
return
objc_stringhash_t::size()
+ capacity * sizeof(objc_classheader_t)
+ sizeof(duplicateCount())
+ duplicateCount() * sizeof(objc_classheader_t);
}
size_t sizeWithoutDups()
{
return
objc_stringhash_t::size()
+ capacity * sizeof(objc_classheader_t);
}
void byteswap(bool little_endian)
{
objc_classheader_t *o;
o = classOffsets();
for (uint32_t i = 0; i < capacity; i++) {
S32(o[i].clsOffset);
S32(o[i].hiOffset);
}
o = duplicateOffsets();
for (uint32_t i = 0; i < duplicateCount(); i++) {
S32(o[i].clsOffset);
S32(o[i].hiOffset);
}
S32(duplicateCount());
objc_stringhash_t::byteswap(little_endian);
}
const char *write(uint64_t base, size_t remaining,
string_map& strings, class_map& classes, bool verbose)
{
const char *err;
err = objc_stringhash_t::write(base, remaining, strings);
if (err) return err;
if (sizeWithoutDups() > remaining) {
return "selector section too small (metadata not optimized)";
}
if (size() > remaining) {
return "selector section too small (metadata not optimized)";
}
for (uint32_t i = 0; i < capacity; i++) {
classOffsets()[i].clsOffset = 0;
classOffsets()[i].hiOffset = 0;
}
# define SHIFT (64 - 8*sizeof(objc_stringhash_offset_t))
class_map::const_iterator c;
for (c = classes.begin(); c != classes.end(); ++c) {
uint32_t h = getIndex(c->first);
if (h == INDEX_NOT_FOUND) {
return "class list busted (metadata not optimized)";
}
if (classOffsets()[h].clsOffset != 0) {
continue;
}
uint32_t count = (uint32_t)classes.count(c->first);
if (count == 1) {
int64_t coff = c->second.first - base;
int64_t hoff = c->second.second - base;
if ((coff<<SHIFT)>>SHIFT != coff) {
return "class offset too big (metadata not optimized)";
}
if ((hoff<<SHIFT)>>SHIFT != hoff) {
return "header offset too big (metadata not optimized)";
}
classOffsets()[h].clsOffset = (objc_stringhash_offset_t)coff;
classOffsets()[h].hiOffset = (objc_stringhash_offset_t)hoff;
}
else {
if (verbose) {
fprintf(stderr, "update_dyld_shared_cache: %u duplicates of Objective-C class %s\n", count, c->first);
}
uint32_t dest = duplicateCount();
duplicateCount() += count;
if (size() > remaining) {
return "selector section too small (metadata not optimized)";
}
classOffsets()[h].clsOffset = count*2 + 1;
classOffsets()[h].hiOffset = dest;
std::pair<class_map::const_iterator, class_map::const_iterator>
duplicates = classes.equal_range(c->first);
class_map::const_iterator dup;
for (dup = duplicates.first; dup != duplicates.second; ++dup) {
int64_t coff = dup->second.first - base;
int64_t hoff = dup->second.second - base;
if ((coff<<SHIFT)>>SHIFT != coff) {
return "class offset too big (metadata not optimized)";
}
if ((hoff<<SHIFT)>>SHIFT != hoff) {
return "header offset too big (metadata not optimized)";
}
duplicateOffsets()[dest].clsOffset = (objc_stringhash_offset_t)coff;
duplicateOffsets()[dest].hiOffset = (objc_stringhash_offset_t)hoff;
dest++;
}
}
}
# undef SHIFT
return NULL;
}
#endif
};
struct objc_protocolopt_t : objc_stringhash_t {
objc_stringhash_offset_t *protocolOffsets() { return (objc_stringhash_offset_t *)&offsets()[capacity]; }
const objc_stringhash_offset_t *protocolOffsets() const { return (const objc_stringhash_offset_t *)&offsets()[capacity]; }
void* getProtocol(const char *key) const
{
uint32_t h = getIndex(key);
if (h == INDEX_NOT_FOUND) {
return NULL;
}
return (void *)((const char *)this + protocolOffsets()[h]);
}
#ifdef SELOPT_WRITE
size_t size()
{
return
objc_stringhash_t::size() + capacity * sizeof(objc_stringhash_offset_t);
}
void byteswap(bool little_endian)
{
objc_stringhash_offset_t *o;
o = protocolOffsets();
for (objc_stringhash_offset_t i = 0; i < (int)capacity; i++) {
S32(o[i]);
}
objc_stringhash_t::byteswap(little_endian);
}
const char *write(uint64_t base, size_t remaining,
string_map& strings, legacy_protocol_map& protocols,
bool verbose)
{
const char *err;
err = objc_stringhash_t::write(base, remaining, strings);
if (err) return err;
if (size() > remaining) {
return "selector section too small (metadata not optimized)";
}
for (uint32_t i = 0; i < capacity; i++) {
protocolOffsets()[i] = 0;
}
# define SHIFT (64 - 8*sizeof(objc_stringhash_offset_t))
legacy_protocol_map::const_iterator c;
for (c = protocols.begin(); c != protocols.end(); ++c) {
uint32_t h = getIndex(c->first);
if (h == INDEX_NOT_FOUND) {
return "protocol list busted (metadata not optimized)";
}
int64_t offset = c->second - base;
if ((offset<<SHIFT)>>SHIFT != offset) {
return "protocol offset too big (metadata not optimized)";
}
protocolOffsets()[h] = (objc_stringhash_offset_t)offset;
}
# undef SHIFT
return NULL;
}
#endif
};
struct objc_protocolopt2_t : objc_clsopt_t {
void* getProtocol(const char *key,
bool (*callback)(const void* header_info)) const
{
uint32_t h = getIndex(key);
if (h == INDEX_NOT_FOUND) {
return NULL;
}
const objc_classheader_t& clshi = classOffsets()[h];
if (! clshi.isDuplicate()) {
void* cls = (void *)((const char *)this + clshi.clsOffset);
void* hi = (void *)((const char *)this + clshi.hiOffset);
return callback(hi) ? cls : NULL;
}
else {
uint32_t count = clshi.duplicateCount();
const objc_classheader_t *list = &duplicateOffsets()[clshi.duplicateIndex()];
for (uint32_t i = 0; i < count; i++) {
void* cls = (void *)((const char *)this + list[i].clsOffset);
void* hi = (void *)((const char *)this + list[i].hiOffset);
if (callback(hi))
return cls;
}
return NULL;
}
}
};
struct objc_headeropt_ro_t;
struct objc_headeropt_rw_t;
struct objc_clsopt_t;
enum { VERSION = 15 };
enum : uint32_t {
IsProduction = (1 << 0), NoMissingWeakSuperclasses = (1 << 1) };
struct alignas(alignof(void*)) objc_opt_t {
uint32_t version;
uint32_t flags;
int32_t selopt_offset;
int32_t headeropt_ro_offset;
int32_t clsopt_offset;
int32_t unused_protocolopt_offset; int32_t headeropt_rw_offset;
int32_t protocolopt_offset;
const objc_selopt_t* selopt() const {
if (selopt_offset == 0) return NULL;
return (objc_selopt_t *)((uint8_t *)this + selopt_offset);
}
objc_selopt_t* selopt() {
if (selopt_offset == 0) return NULL;
return (objc_selopt_t *)((uint8_t *)this + selopt_offset);
}
struct objc_headeropt_ro_t* headeropt_ro() const {
if (headeropt_ro_offset == 0) return NULL;
return (struct objc_headeropt_ro_t *)((uint8_t *)this + headeropt_ro_offset);
}
struct objc_clsopt_t* clsopt() const {
if (clsopt_offset == 0) return NULL;
return (objc_clsopt_t *)((uint8_t *)this + clsopt_offset);
}
struct objc_protocolopt_t* protocolopt() const {
if (unused_protocolopt_offset == 0) return NULL;
return (objc_protocolopt_t *)((uint8_t *)this + unused_protocolopt_offset);
}
struct objc_protocolopt2_t* protocolopt2() const {
if (protocolopt_offset == 0) return NULL;
return (objc_protocolopt2_t *)((uint8_t *)this + protocolopt_offset);
}
struct objc_headeropt_rw_t* headeropt_rw() const {
if (headeropt_rw_offset == 0) return NULL;
return (struct objc_headeropt_rw_t *)((uint8_t *)this + headeropt_rw_offset);
}
};
STATIC_ASSERT(sizeof(objc_opt_t) % sizeof(void*) == 0);
template <typename T>
struct objc_opt_pointerlist_tt {
T protocolClass;
};
typedef struct objc_opt_pointerlist_tt<uintptr_t> objc_opt_pointerlist_t;
#define mix64(a,b,c) \
{ \
a -= b; a -= c; a ^= (c>>43); \
b -= c; b -= a; b ^= (a<<9); \
c -= a; c -= b; c ^= (b>>8); \
a -= b; a -= c; a ^= (c>>38); \
b -= c; b -= a; b ^= (a<<23); \
c -= a; c -= b; c ^= (b>>5); \
a -= b; a -= c; a ^= (c>>35); \
b -= c; b -= a; b ^= (a<<49); \
c -= a; c -= b; c ^= (b>>11); \
a -= b; a -= c; a ^= (c>>12); \
b -= c; b -= a; b ^= (a<<18); \
c -= a; c -= b; c ^= (b>>22); \
}
static uint64_t lookup8( uint8_t *k, size_t length, uint64_t level)
{
uint64_t a,b,c;
size_t len;
len = length;
a = b = level;
c = 0x9e3779b97f4a7c13LL;
while (len >= 24)
{
a += (k[0] +((uint64_t)k[ 1]<< 8)+((uint64_t)k[ 2]<<16)+((uint64_t)k[ 3]<<24)
+((uint64_t)k[4 ]<<32)+((uint64_t)k[ 5]<<40)+((uint64_t)k[ 6]<<48)+((uint64_t)k[ 7]<<56));
b += (k[8] +((uint64_t)k[ 9]<< 8)+((uint64_t)k[10]<<16)+((uint64_t)k[11]<<24)
+((uint64_t)k[12]<<32)+((uint64_t)k[13]<<40)+((uint64_t)k[14]<<48)+((uint64_t)k[15]<<56));
c += (k[16] +((uint64_t)k[17]<< 8)+((uint64_t)k[18]<<16)+((uint64_t)k[19]<<24)
+((uint64_t)k[20]<<32)+((uint64_t)k[21]<<40)+((uint64_t)k[22]<<48)+((uint64_t)k[23]<<56));
mix64(a,b,c);
k += 24; len -= 24;
}
c += length;
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wimplicit-fallthrough"
switch(len)
{
case 23: c+=((uint64_t)k[22]<<56);
case 22: c+=((uint64_t)k[21]<<48);
case 21: c+=((uint64_t)k[20]<<40);
case 20: c+=((uint64_t)k[19]<<32);
case 19: c+=((uint64_t)k[18]<<24);
case 18: c+=((uint64_t)k[17]<<16);
case 17: c+=((uint64_t)k[16]<<8);
case 16: b+=((uint64_t)k[15]<<56);
case 15: b+=((uint64_t)k[14]<<48);
case 14: b+=((uint64_t)k[13]<<40);
case 13: b+=((uint64_t)k[12]<<32);
case 12: b+=((uint64_t)k[11]<<24);
case 11: b+=((uint64_t)k[10]<<16);
case 10: b+=((uint64_t)k[ 9]<<8);
case 9: b+=((uint64_t)k[ 8]);
case 8: a+=((uint64_t)k[ 7]<<56);
case 7: a+=((uint64_t)k[ 6]<<48);
case 6: a+=((uint64_t)k[ 5]<<40);
case 5: a+=((uint64_t)k[ 4]<<32);
case 4: a+=((uint64_t)k[ 3]<<24);
case 3: a+=((uint64_t)k[ 2]<<16);
case 2: a+=((uint64_t)k[ 1]<<8);
case 1: a+=((uint64_t)k[ 0]);
}
#pragma clang diagnostic pop
mix64(a,b,c);
return c;
}
#if defined(SELOPT_WRITE) || defined(CLOSURE_SELOPT_WRITE)
typedef uint64_t ub8;
#define UB8MAXVAL 0xffffffffffffffffLL
#define UB8BITS 64
typedef uint32_t ub4;
#define UB4MAXVAL 0xffffffff
#define UB4BITS 32
typedef uint16_t ub2;
#define UB2MAXVAL 0xffff
#define UB2BITS 16
typedef uint8_t ub1;
#define UB1MAXVAL 0xff
#define UB1BITS 8
#define TRUE 1
#define FALSE 0
#define SCRAMBLE_LEN 256 // ((ub4)1<<16)
#define RETRY_INITKEY 2048
#define RETRY_PERFECT 4
struct key
{
ub1 *name_k;
ub4 len_k;
ub4 hash_k;
ub4 a_k;
ub4 b_k;
struct key *nextb_k;
};
typedef struct key key;
struct bstuff
{
ub2 val_b;
key *list_b;
ub4 listlen_b;
ub4 water_b;
};
typedef struct bstuff bstuff;
struct hstuff
{
key *key_h;
};
typedef struct hstuff hstuff;
struct qstuff
{
bstuff *b_q;
ub4 parent_q;
ub2 newval_q;
ub2 oldval_q;
};
typedef struct qstuff qstuff;
static ub4 log2u(ub4 val)
{
ub4 i;
for (i=0; ((ub4)1<<i) < val; ++i)
;
return i;
}
static ub4 permute(ub4 x, ub4 nbits)
{
int i;
int mask = ((ub4)1<<nbits)-1;
int const2 = 1+nbits/2;
int const3 = 1+nbits/3;
int const4 = 1+nbits/4;
int const5 = 1+nbits/5;
for (i=0; i<20; ++i)
{
x = (x+(x<<const2)) & mask;
x = (x^(x>>const3));
x = (x+(x<<const4)) & mask;
x = (x^(x>>const5));
}
return x;
}
static void scrambleinit(ub4 *scramble, ub4 smax)
{
ub4 i;
for (i=0; i<SCRAMBLE_LEN; ++i)
{
scramble[i] = permute(i, log2u(smax));
}
}
static int inittab(dyld3::OverflowSafeArray<bstuff>& tabb, dyld3::OverflowSafeArray<key>& keys, int complete)
{
int nocollision = TRUE;
ub4 i;
memset((void *)tabb.begin(), 0, (size_t)(sizeof(bstuff)*tabb.maxCount()));
for (i = 0; i < keys.count(); i++) {
key *mykey = &keys[i];
key *otherkey;
for (otherkey=tabb[mykey->b_k].list_b;
otherkey;
otherkey=otherkey->nextb_k)
{
if (mykey->a_k == otherkey->a_k)
{
nocollision = FALSE;
if (!complete)
return FALSE;
}
}
++tabb[mykey->b_k].listlen_b;
mykey->nextb_k = tabb[mykey->b_k].list_b;
tabb[mykey->b_k].list_b = mykey;
}
return nocollision;
}
static void initnorm(dyld3::OverflowSafeArray<key>& keys, ub4 alen, ub4 blen, ub4 smax, ub8 salt)
{
ub4 loga = log2u(alen);
#if BUILDING_CACHE_BUILDER
dispatch_apply(keys.count(), DISPATCH_APPLY_AUTO, ^(size_t index) {
ub4 i = (ub4)index;
key *mykey = &keys[i];
ub8 hash = lookup8(mykey->name_k, mykey->len_k, salt);
mykey->a_k = (loga > 0) ? (ub4)(hash >> (UB8BITS-loga)) : 0;
mykey->b_k = (blen > 1) ? (hash & (blen-1)) : 0;
});
#else
for (size_t index = 0; index != keys.count(); ++index) {
ub4 i = (ub4)index;
key *mykey = &keys[i];
ub8 hash = lookup8(mykey->name_k, mykey->len_k, salt);
mykey->a_k = (loga > 0) ? (ub4)(hash >> (UB8BITS-loga)) : 0;
mykey->b_k = (blen > 1) ? (hash & (blen-1)) : 0;
};
#endif
}
static int apply(dyld3::OverflowSafeArray<bstuff>& tabb,
dyld3::OverflowSafeArray<hstuff>& tabh,
dyld3::OverflowSafeArray<qstuff>& tabq,
ub4 *scramble, ub4 tail, int rollback)
{
ub4 hash;
key *mykey;
bstuff *pb;
ub4 child;
ub4 parent;
ub4 stabb;
for (child=tail-1; child; child=parent)
{
parent = tabq[child].parent_q;
pb = tabq[parent].b_q;
stabb = scramble[pb->val_b];
for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k)
{
hash = mykey->a_k^stabb;
if (mykey == tabh[hash].key_h)
{
tabh[hash].key_h = (key *)0;
}
}
pb->val_b = (rollback ? tabq[child].oldval_q : tabq[child].newval_q);
stabb = scramble[pb->val_b];
for (mykey=pb->list_b; mykey; mykey=mykey->nextb_k)
{
hash = mykey->a_k^stabb;
if (rollback)
{
if (parent == 0) continue;
}
else if (tabh[hash].key_h)
{
apply(tabb, tabh, tabq, scramble, tail, TRUE);
return FALSE;
}
tabh[hash].key_h = mykey;
}
}
return TRUE;
}
static int augment(dyld3::OverflowSafeArray<bstuff>& tabb,
dyld3::OverflowSafeArray<hstuff>& tabh,
dyld3::OverflowSafeArray<qstuff>& tabq,
ub4 *scramble, ub4 smax, bstuff *item, ub4 nkeys,
ub4 highwater)
{
ub4 q;
ub4 tail;
ub4 limit=UB1MAXVAL+1;
ub4 highhash = smax;
tabq[0].b_q = item;
tail = 1;
for (q=0; q<tail; ++q)
{
bstuff *myb = tabq[q].b_q;
ub4 i;
if (q == 1)
break;
for (i=0; i<limit; ++i)
{
bstuff *childb = (bstuff *)0;
key *mykey;
for (mykey = myb->list_b; mykey; mykey=mykey->nextb_k)
{
key *childkey;
ub4 hash = mykey->a_k^scramble[i];
if (hash >= highhash) break;
childkey = tabh[hash].key_h;
if (childkey)
{
bstuff *hitb = &tabb[childkey->b_k];
if (childb)
{
if (childb != hitb) break;
}
else
{
childb = hitb;
if (childb->water_b == highwater) break;
}
}
}
if (mykey) continue;
if (childb) childb->water_b = highwater;
tabq[tail].b_q = childb;
tabq[tail].newval_q = i;
tabq[tail].oldval_q = myb->val_b;
tabq[tail].parent_q = q;
++tail;
if (!childb)
{
if (apply(tabb, tabh, tabq, scramble, tail, FALSE))
return TRUE;
--tail;
}
}
}
return FALSE;
}
static int perfect(dyld3::OverflowSafeArray<bstuff>& tabb,
dyld3::OverflowSafeArray<hstuff>& tabh,
dyld3::OverflowSafeArray<qstuff>& tabq,
ub4 smax, ub4 *scramble, ub4 nkeys)
{
ub4 maxkeys;
ub4 i, j;
const ub4 blen = (ub4)tabb.count();
#if SELOPT_DEBUG
fprintf(stderr, " blen %d smax %d nkeys %d\n", blen, smax, nkeys);
#endif
memset((void *)tabh.begin(), 0, sizeof(hstuff)*smax);
memset((void *)tabq.begin(), 0, sizeof(qstuff)*(blen+1));
for (maxkeys=0,i=0; i<blen; ++i)
if (tabb[i].listlen_b > maxkeys)
maxkeys = tabb[i].listlen_b;
for (j=maxkeys; j>0; --j)
for (i=0; i<blen; ++i)
if (tabb[i].listlen_b == j)
if (!augment(tabb, tabh, tabq, scramble, smax, &tabb[i], nkeys,
i+1))
{
return FALSE;
}
return TRUE;
}
static void initalen(ub4 *alen, ub4 *blen, ub4 smax, ub4 nkeys)
{
*alen = smax;
*blen = ((nkeys <= smax*0.6) ? smax/16 :
(nkeys <= smax*0.8) ? smax/8 : smax/4);
if (*alen < 1) *alen = 1;
if (*blen < 1) *blen = 1;
#if SELOPT_DEBUG
fprintf(stderr, "alen %d blen %d smax %d nkeys %d\n", *alen, *blen, smax, nkeys);
#endif
}
static int findhash(dyld3::OverflowSafeArray<bstuff>& tabb,
ub4 *alen, ub8 *salt,
ub4 *scramble, ub4 smax, dyld3::OverflowSafeArray<key>& keys)
{
ub4 bad_initkey;
ub4 bad_perfect;
ub4 si;
ub4 maxalen;
dyld3::OverflowSafeArray<hstuff>tabh;
dyld3::OverflowSafeArray<qstuff>tabq;
ub4 blen = 0;
initalen(alen, &blen, smax, (ub4)keys.count());
scrambleinit(scramble, smax);
maxalen = smax;
tabb.resize(blen);
tabq.resize(blen+1);
tabh.resize(smax);
*salt = 0;
bad_initkey = 0;
bad_perfect = 0;
for (si=1; ; ++si)
{
ub4 rslinit;
*salt = si * 0x9e3779b97f4a7c13LL;
initnorm(keys, *alen, blen, smax, *salt);
rslinit = inittab(tabb, keys, FALSE);
if (rslinit == 0)
{
if (++bad_initkey >= RETRY_INITKEY)
{
if (*alen < maxalen)
{
*alen *= 2;
}
else if (blen < smax)
{
blen *= 2;
tabb.resize(blen);
tabq.resize(blen+1);
}
bad_initkey = 0;
bad_perfect = 0;
}
continue;
}
if (!perfect(tabb, tabh, tabq, smax, scramble, (ub4)keys.count()))
{
if (++bad_perfect >= RETRY_PERFECT)
{
if (blen < smax)
{
blen *= 2;
tabb.resize(blen);
tabq.resize(blen+1);
--si;
}
else
{
return 0;
}
bad_perfect = 0;
}
continue;
}
break;
}
return 1;
}
static void
make_perfect(dyld3::OverflowSafeArray<key>& keys, perfect_hash& result)
{
dyld3::OverflowSafeArray<bstuff> tab;
ub4 smax;
ub4 alen;
ub8 salt;
ub4 scramble[SCRAMBLE_LEN];
int ok;
uint32_t i;
smax = ((ub4)1<<log2u((ub4)keys.count()));
ok = findhash(tab, &alen, &salt,
scramble, smax, keys);
if (!ok) {
smax = 2 * ((ub4)1<<log2u((ub4)keys.count()));
ok = findhash(tab, &alen, &salt,
scramble, smax, keys);
}
if (!ok) {
bzero(&result, sizeof(result));
} else {
result.capacity = smax;
result.occupied = (ub4)keys.count();
result.shift = UB8BITS - log2u(alen);
result.mask = (ub4)tab.count() - 1;
result.salt = salt;
result.tab.resize(tab.count());
for (i = 0; i < tab.count(); i++) {
result.tab[i] = tab[i].val_b;
}
for (i = 0; i < 256; i++) {
result.scramble[i] = scramble[i];
}
}
}
#endif
#ifdef SELOPT_WRITE
static void
make_perfect(const string_map& strings, perfect_hash& phash)
{
dyld3::OverflowSafeArray<key> keys;
keys.reserve(strings.size());
size_t i;
string_map::const_iterator s;
for (i = 0, s = strings.begin(); s != strings.end(); ++s, ++i) {
key mykey;
mykey.name_k = (ub1 *)s->first;
mykey.len_k = (ub4)strlen(s->first);
keys.push_back(mykey);
}
make_perfect(keys, phash);
}
#endif
#ifdef CLOSURE_SELOPT_WRITE
static void
make_perfect(const dyld3::OverflowSafeArray<const char*>& strings, perfect_hash& phash)
{
dyld3::OverflowSafeArray<key> keys;
keys.reserve(strings.count());
for (const char* s : strings) {
key mykey;
mykey.name_k = (ub1 *)s;
mykey.len_k = (ub4)strlen(s);
keys.push_back(mykey);
}
make_perfect(keys, phash);
}
#endif
};
#undef S32
#undef S64
#endif