123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623 |
- #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) /* length of *scramble* */
- #define RETRY_INITKEY 2048 /* number of times to try to find distinct (a,b) */
- #define RETRY_PERFECT 4 /* number of times to try to make a perfect hash */
- 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
|