aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorCameron Katri <me@cameronkatri.com>2022-07-06 20:56:15 -0400
committerCameron Katri <me@cameronkatri.com>2022-07-06 20:59:04 -0400
commit672c7c058ee732471bca000744877e4f8db37c1c (patch)
tree2ddd55745bcf2f71b4f85b0ca692a51c5e5460c7
parentc3a24e1bd2ad113499313269d9fc0cfc6a8022d2 (diff)
downloadldid-672c7c058ee732471bca000744877e4f8db37c1c.tar.gz
ldid-672c7c058ee732471bca000744877e4f8db37c1c.tar.zst
ldid-672c7c058ee732471bca000744877e4f8db37c1c.zip
General cleanup
- Remove useless preprocessor directives - Remove -T flag - Remove CommonCrypto dependency (OpenSSL is required anyways)
-rw-r--r--.gitignore2
-rw-r--r--Makefile5
-rw-r--r--docs/ldid.110
-rw-r--r--docs/ldid.zh_CN.111
-rw-r--r--docs/ldid.zh_TW.111
-rw-r--r--ldid.cpp133
-rw-r--r--lookup2.c416
7 files changed, 7 insertions, 581 deletions
diff --git a/.gitignore b/.gitignore
index 5228395..ba6a0f3 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,3 +2,5 @@ ldid
*.o
.DS_Store
.vscode
+compile_commands.json
+.cache
diff --git a/Makefile b/Makefile
index b21f811..55a9c7a 100644
--- a/Makefile
+++ b/Makefile
@@ -14,16 +14,13 @@ PREFIX ?= /usr/local
BINDIR ?= $(PREFIX)/bin
MANDIR ?= $(PREFIX)/share/man
-SRC := $(wildcard *.c) $(wildcard *.cpp)
+SRC := ldid.cpp
LIBS ?= -lcrypto -lplist-2.0
MANPAGE_LANGS := zh_TW zh_CN
all: ldid
-%.c.o: %.c
- $(CC) -c $(CFLAGS) $(CPPFLAGS) -I. $< -o $@
-
%.cpp.o: %.cpp
$(CXX) -c $(CXXFLAGS) $(CPPFLAGS) -I. -DLDID_VERSION=\"$(VERSION)\" $< -o $@
diff --git a/docs/ldid.1 b/docs/ldid.1
index 41b1bc5..2839e1c 100644
--- a/docs/ldid.1
+++ b/docs/ldid.1
@@ -26,7 +26,6 @@
.Op Fl Q Ns Ar requirements.xml
.Op Fl q
.Op Fl r | Fl S Ns Ar file.xml | Fl s
-.Op Fl T Ns Ar timestamp
.Op Fl u
.Op Fl arch Ar arch_type
.Ar
@@ -128,15 +127,6 @@ is specified then the entitlements found in
will be embedded in the Mach-O.
.It Fl s
Resign the Mach-O binaries while keeping the existing entitlements.
-.It Fl T Ns Ar timestamp
-When signing a dylib, set the timestamp to
-.Ar timestamp .
-.Ar timestamp
-should be an UNIX timestamp in seconds, if
-.Ar timestamp
-is a single dash
-.Pq Sq Fl ,
-the timestamp will be set to a hash of the Mach-O header.
.It Fl U Ns Ar password
Use
.Ar password
diff --git a/docs/ldid.zh_CN.1 b/docs/ldid.zh_CN.1
index de24936..713ae27 100644
--- a/docs/ldid.zh_CN.1
+++ b/docs/ldid.zh_CN.1
@@ -26,7 +26,6 @@
.Op Fl Q Ns Ar 需求.xml
.Op Fl q
.Op Fl r | Fl S Ns Ar 档案.xml | Fl s
-.Op Fl T Ns Ar 时间印章
.Op Fl u
.Op Fl arch Ar 架构类型
.Ar
@@ -129,16 +128,6 @@
中的权限会被嵌入到Mach-O中。
.It Fl s
重新签署Mach-O档案但保留现有权限。
-.It Fl T Ns Ar 时间印章
-当签署一个动态链结函式库时,把时间印章设定为
-.Ar 时间印章
-。
-.Ar 时间印章
-应该是一个以秒作为单位的UNIX时间印章,如果
-.Ar
-是一个连字号的话
-.Pq Sq Fl ,
-时间印章会被设定为Mach-O头中的时间印章。
.It Fl U Ns Ar 密码
使用
.Ar 密码
diff --git a/docs/ldid.zh_TW.1 b/docs/ldid.zh_TW.1
index 556e668..492f38c 100644
--- a/docs/ldid.zh_TW.1
+++ b/docs/ldid.zh_TW.1
@@ -26,7 +26,6 @@
.Op Fl Q Ns Ar 需求.xml
.Op Fl q
.Op Fl r | Fl S Ns Ar 檔案.xml | Fl s
-.Op Fl T Ns Ar 時間印章
.Op Fl u
.Op Fl arch Ar 架構類型
.Ar
@@ -129,16 +128,6 @@
中的權限會被嵌入到Mach-O中。
.It Fl s
重新簽署Mach-O檔案但保留現有權限。
-.It Fl T Ns Ar 時間印章
-當簽署一個動態鏈結函式庫時,把時間印章設定為
-.Ar 時間印章
-。
-.Ar 時間印章
-應該是一個以秒作為單位的UNIX時間印章,如果
-.Ar
-是一個連字號的話
-.Pq Sq Fl ,
-時間印章會被設定為Mach-O頭中的時間印章。
.It Fl U Ns Ar 密碼
使用
.Ar 密碼
diff --git a/ldid.cpp b/ldid.cpp
index 9042d87..c2e89cc 100644
--- a/ldid.cpp
+++ b/ldid.cpp
@@ -43,7 +43,6 @@
#include <sys/stat.h>
#include <sys/types.h>
-#ifndef LDID_NOSMIME
#include <openssl/opensslv.h>
# if OPENSSL_VERSION_MAJOR >= 3
# include <openssl/provider.h>
@@ -54,25 +53,7 @@
#include <openssl/pkcs7.h>
#include <openssl/pkcs12.h>
#include <openssl/ui.h>
-#endif
-#ifdef __APPLE__
-#include <CommonCrypto/CommonDigest.h>
-
-#define LDID_SHA1_DIGEST_LENGTH CC_SHA1_DIGEST_LENGTH
-#define LDID_SHA1 CC_SHA1
-#define LDID_SHA1_CTX CC_SHA1_CTX
-#define LDID_SHA1_Init CC_SHA1_Init
-#define LDID_SHA1_Update CC_SHA1_Update
-#define LDID_SHA1_Final CC_SHA1_Final
-
-#define LDID_SHA256_DIGEST_LENGTH CC_SHA256_DIGEST_LENGTH
-#define LDID_SHA256 CC_SHA256
-#define LDID_SHA256_CTX CC_SHA256_CTX
-#define LDID_SHA256_Init CC_SHA256_Init
-#define LDID_SHA256_Update CC_SHA256_Update
-#define LDID_SHA256_Final CC_SHA256_Final
-#else
#include <openssl/sha.h>
#define LDID_SHA1_DIGEST_LENGTH SHA_DIGEST_LENGTH
@@ -88,13 +69,8 @@
#define LDID_SHA256_Init SHA256_Init
#define LDID_SHA256_Update SHA256_Update
#define LDID_SHA256_Final SHA256_Final
-#endif
-#ifndef LDID_NOPLIST
#include <plist/plist.h>
-#elif __APPLE__
-#include <CoreFoundation/CoreFoundation.h>
-#endif
#include "ldid.hpp"
@@ -151,9 +127,7 @@
#define _packed \
__attribute__((packed))
-#ifndef LDID_NOSMIME
std::string password;
-#endif
template <typename Type_>
struct Iterator_ {
@@ -662,7 +636,6 @@ static std::string der(const std::pair<std::string, std::string> &value) {
return data.str();
}
-#ifndef LDID_NOPLIST
static std::string der(plist_t data) {
switch (const auto type = plist_get_node_type(data)) {
case PLIST_BOOLEAN: {
@@ -746,7 +719,6 @@ static std::string der(plist_t data) {
} break;
}
}
-#endif
static inline uint16_t Swap_(uint16_t value) {
return
@@ -1183,9 +1155,6 @@ enum MatchOperation {
#define APPLE_ADS_OID APPLE_OID, 0x64
#define APPLE_EXTENSION_OID APPLE_ADS_OID, 6
-#ifndef LDID_NOFLAGT
-extern "C" uint32_t hash(uint8_t *k, uint32_t length, uint32_t initval);
-#endif
struct Algorithm {
size_t size_;
@@ -1414,13 +1383,11 @@ class Map {
return std::string(static_cast<char *>(data_), size_);
}
};
-#endif
+#endif // LDID_NOTOOLS
namespace ldid {
-#ifndef LDID_NOPLIST
static plist_t plist(const std::string &data);
-#endif
void Analyze(const MachHeader &mach_header, const Functor<void (const char *data, size_t size)> &entitle) {
_foreach (load_command, mach_header.GetLoadCommands())
@@ -1765,7 +1732,6 @@ static size_t put(std::streambuf &output, uint32_t magic, const Blobs &blobs) {
return offset;
}
-#ifndef LDID_NOSMIME
class Buffer {
private:
BIO *bio_;
@@ -1959,7 +1925,6 @@ class Signature {
return value_;
}
};
-#endif
class NullBuffer :
public std::streambuf
@@ -2085,11 +2050,10 @@ static void Commit(const std::string &path, const std::string &temp) {
_syscall(rename(temp.c_str(), path.c_str()));
}
-#endif
+#endif // LDID_NOTOOLS
namespace ldid {
-#ifndef LDID_NOSMIME
static void get(std::string &value, X509_NAME *name, int nid) {
auto index(X509_NAME_get_index_by_NID(name, nid, -1));
_assert(index >= 0);
@@ -2101,7 +2065,6 @@ static void get(std::string &value, X509_NAME *name, int nid) {
_assert(asn != NULL);
value.assign(reinterpret_cast<const char *>(ASN1_STRING_get0_data(asn)), ASN1_STRING_length(asn));
}
-#endif
static void req(std::streambuf &buffer, uint32_t value) {
value = Swap(value);
@@ -2130,7 +2093,6 @@ Hash Sign(const void *idata, size_t isize, std::streambuf &output, const std::st
std::string team;
std::string common;
-#ifndef LDID_NOSMIME
if (!key.empty()) {
Stuff stuff(key);
auto name(X509_get_subject_name(stuff));
@@ -2141,7 +2103,6 @@ Hash Sign(const void *idata, size_t isize, std::streambuf &output, const std::st
get(team, name, NID_organizationalUnitName);
get(common, name, NID_commonName);
}
-#endif
std::stringbuf backing;
@@ -2196,9 +2157,6 @@ Hash Sign(const void *idata, size_t isize, std::streambuf &output, const std::st
alloc += sizeof(struct BlobIndex);
alloc += backing.str().size();
-#ifdef LDID_NOPLIST
- baton.entitlements_ = entitlements;
-#else
if (merge)
Analyze(mach_header, fun([&](const char *data, size_t size) {
baton.entitlements_.assign(data, size);
@@ -2236,7 +2194,6 @@ Hash Sign(const void *idata, size_t isize, std::streambuf &output, const std::st
baton.entitlements_.assign(xml, size);
}
-#endif
if (!baton.entitlements_.empty()) {
special = std::max(special, CSSLOT_ENTITLEMENTS);
@@ -2265,13 +2222,11 @@ Hash Sign(const void *idata, size_t isize, std::streambuf &output, const std::st
for (Algorithm *algorithm : GetAlgorithms())
alloc = Align(alloc + directory + (special + normal) * algorithm->size_, 16);
-#ifndef LDID_NOSMIME
if (!key.empty()) {
alloc += sizeof(struct BlobIndex);
alloc += sizeof(struct Blob);
alloc += certificate;
}
-#endif
return alloc;
}), fun([&](const MachHeader &mach_header, const Baton &baton, std::streambuf &output, size_t limit, size_t left, size_t right, const std::string &overlap, const char *top, const Progress &progress) -> size_t {
@@ -2290,7 +2245,6 @@ Hash Sign(const void *idata, size_t isize, std::streambuf &output, const std::st
put(data, baton.entitlements_.data(), baton.entitlements_.size());
insert(blobs, CSSLOT_ENTITLEMENTS, CSMAGIC_EMBEDDED_ENTITLEMENTS, data);
-#ifndef LDID_NOPLIST
auto entitlements(plist(baton.entitlements_));
_scope({ plist_free(entitlements); });
if (plist_get_node_type(entitlements) != PLIST_DICT) {
@@ -2321,7 +2275,6 @@ Hash Sign(const void *idata, size_t isize, std::streambuf &output, const std::st
execs |= kSecCodeExecSegCanLoadCdHash;
if (entitled("com.apple.private.amfi.can-execute-cdhash"))
execs |= kSecCodeExecSegCanExecCdHash;
-#endif
}
if (!baton.derformat_.empty()) {
@@ -2424,23 +2377,12 @@ Hash Sign(const void *idata, size_t isize, std::streambuf &output, const std::st
++total;
}
-#ifndef LDID_NOSMIME
if (!key.empty()) {
-#ifdef LDID_NOPLIST
- auto plist(CFDictionaryCreateMutable(kCFAllocatorDefault, 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks));
- _scope({ CFRelease(plist); });
-
- auto cdhashes(CFArrayCreateMutable(kCFAllocatorDefault, 0, &kCFTypeArrayCallBacks));
- _scope({ CFRelease(cdhashes); });
-
- CFDictionarySetValue(plist, CFSTR("cdhashes"), cdhashes);
-#else
auto plist(plist_new_dict());
_scope({ plist_free(plist); });
auto cdhashes(plist_new_array());
plist_dict_set_item(plist, "cdhashes", cdhashes);
-#endif
std::vector<char> alternateCDSHA256;
@@ -2461,26 +2403,13 @@ Hash Sign(const void *idata, size_t isize, std::streambuf &output, const std::st
}
-#ifdef LDID_NOPLIST
- auto value(CFDataCreate(kCFAllocatorDefault, reinterpret_cast<const UInt8 *>(hash.data()), hash.size()));
- _scope({ CFRelease(value); });
- CFArrayAppendValue(cdhashes, value);
-#else
plist_array_append_item(cdhashes, plist_new_data(hash.data(), hash.size()));
-#endif
}
-#ifdef LDID_NOPLIST
- auto created(CFPropertyListCreateXMLData(kCFAllocatorDefault, plist));
- _scope({ CFRelease(created); });
- auto xml(reinterpret_cast<const char *>(CFDataGetBytePtr(created)));
- auto size(CFDataGetLength(created));
-#else
char *xml(NULL);
uint32_t size;
plist_to_xml(plist, &xml, &size);
_scope({ free(xml); });
-#endif
std::stringbuf data;
const std::string &sign(blobs[CSSLOT_CODEDIRECTORY]);
@@ -2496,7 +2425,6 @@ Hash Sign(const void *idata, size_t isize, std::streambuf &output, const std::st
const auto &save(insert(blobs, CSSLOT_SIGNATURESLOT, CSMAGIC_BLOBWRAPPER, data));
_assert(save.size() <= certificate);
}
-#endif
return put(output, CSMAGIC_EMBEDDED_SIGNATURE, blobs);
}), progress);
@@ -2623,7 +2551,7 @@ void DiskFolder::Open(const std::string &path, const Functor<void (std::streambu
void DiskFolder::Find(const std::string &path, const Functor<void (const std::string &)> &code, const Functor<void (const std::string &, const Functor<std::string ()> &)> &link) const {
Find(path, "", code, link);
}
-#endif
+#endif // LDID_NOTOOLS
SubFolder::SubFolder(Folder &parent, const std::string &path) :
parent_(parent),
@@ -2733,7 +2661,6 @@ static void copy(std::streambuf &source, std::streambuf &target, size_t length,
}
}
-#ifndef LDID_NOPLIST
static plist_t plist(const std::string &data) {
if (data.empty())
return plist_new_dict();
@@ -2763,7 +2690,6 @@ static std::string plist_s(plist_t node) {
_scope({ free(data); });
return data;
}
-#endif
enum Mode {
NoMode,
@@ -2849,7 +2775,6 @@ struct RuleCode {
}
};
-#ifndef LDID_NOPLIST
static Hash Sign(const uint8_t *prefix, size_t size, std::streambuf &buffer, Hash &hash, std::streambuf &save, const std::string &identifier, const std::string &entitlements, bool merge, const std::string &requirements, const std::string &key, const Slots &slots, size_t length, uint32_t flags, bool platform, const Progress &progress) {
// XXX: this is a miserable fail
std::stringbuf temp;
@@ -3169,7 +3094,6 @@ Bundle Sign(const std::string &root, Folder &folder, const std::string &key, con
State local;
return Sign(root, folder, key, local, requirements, alter, progress);
}
-#endif
#endif
}
@@ -3202,13 +3126,11 @@ static void usage(const char *argv0) {
#ifndef LDID_NOTOOLS
int main(int argc, char *argv[]) {
-#ifndef LDID_NOSMIME
OpenSSL_add_all_algorithms();
# if OPENSSL_VERSION_MAJOR >= 3
OSSL_PROVIDER *legacy = OSSL_PROVIDER_load(NULL, "legacy");
OSSL_PROVIDER *deflt = OSSL_PROVIDER_load(NULL, "default");
# endif
-#endif
union {
uint16_t word;
@@ -3224,9 +3146,6 @@ int main(int argc, char *argv[]) {
bool flag_H(false);
bool flag_h(false);
-#ifndef LDID_NOFLAGT
- bool flag_T(false);
-#endif
bool flag_S(false);
bool flag_s(false);
@@ -3249,10 +3168,6 @@ int main(int argc, char *argv[]) {
const char *flag_I(NULL);
-#ifndef LDID_NOFLAGT
- bool timeh(false);
- uint32_t timev(0);
-#endif
Map entitlements;
Map requirements;
@@ -3432,18 +3347,6 @@ int main(int argc, char *argv[]) {
key.open(argv[argi] + 2, O_RDONLY, PROT_READ, MAP_PRIVATE);
break;
-#ifndef LDID_NOFLAGT
- case 'T': {
- flag_T = true;
- if (argv[argi][2] == '-')
- timeh = true;
- else {
- char *arge;
- timev = strtoul(argv[argi] + 2, &arge, 0);
- _assert(arge == argv[argi] + strlen(argv[argi]));
- }
- } break;
-#endif
case 'u': {
flag_u = true;
@@ -3488,12 +3391,8 @@ int main(int argc, char *argv[]) {
fprintf(stderr, "ldid: Only -S can be used on directories\n");
exit(1);
}
-#ifndef LDID_NOPLIST
ldid::DiskFolder folder(path + "/");
path += "/" + Sign("", folder, key, requirements, ldid::fun([&](const std::string &, const std::string &) -> std::string { return entitlements; }), dummy_).path;
-#else
- _assert(false);
-#endif
} else if (flag_S || flag_r) {
Map input(path, O_RDONLY, PROT_READ, MAP_PRIVATE);
@@ -3512,10 +3411,6 @@ int main(int argc, char *argv[]) {
}
bool modify(false);
-#ifndef LDID_NOFLAGT
- if (flag_T)
- modify = true;
-#endif
if (flag_s)
modify = true;
@@ -3556,24 +3451,6 @@ int main(int argc, char *argv[]) {
}
}
}
-#ifndef LDID_NOFLAGT
- else if (cmd == LC_ID_DYLIB) {
- volatile struct dylib_command *dylib_command(reinterpret_cast<struct dylib_command *>(load_command));
-
- if (flag_T) {
- uint32_t timed;
-
- if (!timeh)
- timed = timev;
- else {
- dylib_command->dylib.timestamp = 0;
- timed = hash(reinterpret_cast<uint8_t *>(mach_header.GetBase()), mach_header.GetSize(), timev);
- }
-
- dylib_command->dylib.timestamp = mach_header.Swap(timed);
- }
- }
-#endif
}
if (flag_d && encryption != NULL) {
@@ -3726,13 +3603,11 @@ int main(int argc, char *argv[]) {
++filei;
}
-#ifndef LDID_NOSMIME
# if OPENSSL_VERSION_MAJOR >= 3
OSSL_PROVIDER_unload(legacy);
OSSL_PROVIDER_unload(deflt);
# endif
-#endif
return filee;
}
-#endif
+#endif // LDID_NOTOOLS
diff --git a/lookup2.c b/lookup2.c
deleted file mode 100644
index cd87c4d..0000000
--- a/lookup2.c
+++ /dev/null
@@ -1,416 +0,0 @@
-/*
---------------------------------------------------------------------
-lookup2.c, by Bob Jenkins, December 1996, Public Domain.
-hash(), hash2(), hash3, and mix() are externally useful functions.
-Routines to test the hash are included if SELF_TEST is defined.
-You can use this free for any purpose. It has no warranty.
---------------------------------------------------------------------
-*/
-#include <stdio.h>
-#include <stddef.h>
-#include <stdlib.h>
-typedef unsigned long int ub4; /* unsigned 4-byte quantities */
-typedef unsigned char ub1;
-
-#define hashsize(n) ((ub4)1<<(n))
-#define hashmask(n) (hashsize(n)-1)
-
-/*
---------------------------------------------------------------------
-mix -- mix 3 32-bit values reversibly.
-For every delta with one or two bit set, and the deltas of all three
- high bits or all three low bits, whether the original value of a,b,c
- is almost all zero or is uniformly distributed,
-* If mix() is run forward or backward, at least 32 bits in a,b,c
- have at least 1/4 probability of changing.
-* If mix() is run forward, every bit of c will change between 1/3 and
- 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.)
-mix() was built out of 36 single-cycle latency instructions in a
- structure that could supported 2x parallelism, like so:
- a -= b;
- a -= c; x = (c>>13);
- b -= c; a ^= x;
- b -= a; x = (a<<8);
- c -= a; b ^= x;
- c -= b; x = (b>>13);
- ...
- Unfortunately, superscalar Pentiums and Sparcs can't take advantage
- of that parallelism. They've also turned some of those single-cycle
- latency instructions into multi-cycle latency instructions. Still,
- this is the fastest good hash I could find. There were about 2^^68
- to choose from. I only looked at a billion or so.
---------------------------------------------------------------------
-*/
-#define mix(a,b,c) \
-{ \
- a -= b; a -= c; a ^= (c>>13); \
- b -= c; b -= a; b ^= (a<<8); \
- c -= a; c -= b; c ^= (b>>13); \
- a -= b; a -= c; a ^= (c>>12); \
- b -= c; b -= a; b ^= (a<<16); \
- c -= a; c -= b; c ^= (b>>5); \
- a -= b; a -= c; a ^= (c>>3); \
- b -= c; b -= a; b ^= (a<<10); \
- c -= a; c -= b; c ^= (b>>15); \
-}
-
-/* same, but slower, works on systems that might have 8 byte ub4's */
-#define mix2(a,b,c) \
-{ \
- a -= b; a -= c; a ^= (c>>13); \
- b -= c; b -= a; b ^= (a<< 8); \
- c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
- a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
- b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
- c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
- a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
- b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
- c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
-}
-
-/*
---------------------------------------------------------------------
-hash() -- hash a variable-length key into a 32-bit value
- k : the key (the unaligned variable-length array of bytes)
- len : the length of the key, counting by bytes
- level : can be any 4-byte value
-Returns a 32-bit value. Every bit of the key affects every bit of
-the return value. Every 1-bit and 2-bit delta achieves avalanche.
-About 36+6len instructions.
-
-The best hash table sizes are powers of 2. There is no need to do
-mod a prime (mod is sooo slow!). If you need less than 32 bits,
-use a bitmask. For example, if you need only 10 bits, do
- h = (h & hashmask(10));
-In which case, the hash table should have hashsize(10) elements.
-
-If you are hashing n strings (ub1 **)k, do it like this:
- for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
-
-By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
-code any way you wish, private, educational, or commercial. It's free.
-
-See http://burlteburtle.net/bob/hash/evahash.html
-Use for hash table lookup, or anything where one collision in 2^32 is
-acceptable. Do NOT use for cryptographic purposes.
---------------------------------------------------------------------
-*/
-
-ub4 hash( k, length, initval)
-register ub1 *k; /* the key */
-register ub4 length; /* the length of the key */
-register ub4 initval; /* the previous hash, or an arbitrary value */
-{
- register ub4 a,b,c,len;
-
- /* Set up the internal state */
- len = length;
- a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
- c = initval; /* the previous hash value */
-
- /*---------------------------------------- handle most of the key */
- while (len >= 12)
- {
- a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
- b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
- c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
- mix(a,b,c);
- k += 12; len -= 12;
- }
-
- /*------------------------------------- handle the last 11 bytes */
- c += length;
- switch(len) /* all the case statements fall through */
- {
- case 11: c+=((ub4)k[10]<<24);
- case 10: c+=((ub4)k[9]<<16);
- case 9 : c+=((ub4)k[8]<<8);
- /* the first byte of c is reserved for the length */
- case 8 : b+=((ub4)k[7]<<24);
- case 7 : b+=((ub4)k[6]<<16);
- case 6 : b+=((ub4)k[5]<<8);
- case 5 : b+=k[4];
- case 4 : a+=((ub4)k[3]<<24);
- case 3 : a+=((ub4)k[2]<<16);
- case 2 : a+=((ub4)k[1]<<8);
- case 1 : a+=k[0];
- /* case 0: nothing left to add */
- }
- mix(a,b,c);
- /*-------------------------------------------- report the result */
- return c;
-}
-
-
-/*
---------------------------------------------------------------------
- This works on all machines. hash2() is identical to hash() on
- little-endian machines, except that the length has to be measured
- in ub4s instead of bytes. It is much faster than hash(). It
- requires
- -- that the key be an array of ub4's, and
- -- that all your machines have the same endianness, and
- -- that the length be the number of ub4's in the key
---------------------------------------------------------------------
-*/
-ub4 hash2( k, length, initval)
-register ub4 *k; /* the key */
-register ub4 length; /* the length of the key, in ub4s */
-register ub4 initval; /* the previous hash, or an arbitrary value */
-{
- register ub4 a,b,c,len;
-
- /* Set up the internal state */
- len = length;
- a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
- c = initval; /* the previous hash value */
-
- /*---------------------------------------- handle most of the key */
- while (len >= 3)
- {
- a += k[0];
- b += k[1];
- c += k[2];
- mix(a,b,c);
- k += 3; len -= 3;
- }
-
- /*-------------------------------------- handle the last 2 ub4's */
- c += length;
- switch(len) /* all the case statements fall through */
- {
- /* c is reserved for the length */
- case 2 : b+=k[1];
- case 1 : a+=k[0];
- /* case 0: nothing left to add */
- }
- mix(a,b,c);
- /*-------------------------------------------- report the result */
- return c;
-}
-
-/*
---------------------------------------------------------------------
- This is identical to hash() on little-endian machines (like Intel
- x86s or VAXen). It gives nondeterministic results on big-endian
- machines. It is faster than hash(), but a little slower than
- hash2(), and it requires
- -- that all your machines be little-endian
---------------------------------------------------------------------
-*/
-
-ub4 hash3( k, length, initval)
-register ub1 *k; /* the key */
-register ub4 length; /* the length of the key */
-register ub4 initval; /* the previous hash, or an arbitrary value */
-{
- register ub4 a,b,c,len;
-
- /* Set up the internal state */
- len = length;
- a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
- c = initval; /* the previous hash value */
-
- /*---------------------------------------- handle most of the key */
- if (((ub4)k)&3)
- {
- while (len >= 12) /* unaligned */
- {
- a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
- b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
- c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
- mix(a,b,c);
- k += 12; len -= 12;
- }
- }
- else
- {
- while (len >= 12) /* aligned */
- {
- a += *(ub4 *)(k+0);
- b += *(ub4 *)(k+4);
- c += *(ub4 *)(k+8);
- mix(a,b,c);
- k += 12; len -= 12;
- }
- }
-
- /*------------------------------------- handle the last 11 bytes */
- c += length;
- switch(len) /* all the case statements fall through */
- {
- case 11: c+=((ub4)k[10]<<24);
- case 10: c+=((ub4)k[9]<<16);
- case 9 : c+=((ub4)k[8]<<8);
- /* the first byte of c is reserved for the length */
- case 8 : b+=((ub4)k[7]<<24);
- case 7 : b+=((ub4)k[6]<<16);
- case 6 : b+=((ub4)k[5]<<8);
- case 5 : b+=k[4];
- case 4 : a+=((ub4)k[3]<<24);
- case 3 : a+=((ub4)k[2]<<16);
- case 2 : a+=((ub4)k[1]<<8);
- case 1 : a+=k[0];
- /* case 0: nothing left to add */
- }
- mix(a,b,c);
- /*-------------------------------------------- report the result */
- return c;
-}
-
-
-
-#ifdef SELF_TEST
-
-/* used for timings */
-void driver1()
-{
- ub4 buf[256];
- ub4 i;
- ub4 h=0;
-
- for (i=0; i<256; ++i)
- {
- h = hash(buf,i,h);
- }
-}
-
-/* check that every input bit changes every output bit half the time */
-#define HASHSTATE 1
-#define HASHLEN 1
-#define MAXPAIR 80
-#define MAXLEN 70
-void driver2()
-{
- ub1 qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
- ub4 c[HASHSTATE], d[HASHSTATE], i, j=0, k, l, m, z;
- ub4 e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
- ub4 x[HASHSTATE],y[HASHSTATE];
- ub4 hlen;
-
- printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
- for (hlen=0; hlen < MAXLEN; ++hlen)
- {
- z=0;
- for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */
- {
- for (j=0; j<8; ++j) /*------------------------ for each input bit, */
- {
- for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */
- {
- for (l=0; l<HASHSTATE; ++l) e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((ub4)0);
-
- /*---- check that every output bit is affected by that input bit */
- for (k=0; k<MAXPAIR; k+=2)
- {
- ub4 finished=1;
- /* keys have one bit different */
- for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (ub1)0;}
- /* have a and b be two keys differing in only one bit */
- a[i] ^= (k<<j);
- a[i] ^= (k>>(8-j));
- c[0] = hash(a, hlen, m);
- b[i] ^= ((k+1)<<j);
- b[i] ^= ((k+1)>>(8-j));
- d[0] = hash(b, hlen, m);
- /* check every bit is 1, 0, set, and not set at least once */
- for (l=0; l<HASHSTATE; ++l)
- {
- e[l] &= (c[l]^d[l]);
- f[l] &= ~(c[l]^d[l]);
- g[l] &= c[l];
- h[l] &= ~c[l];
- x[l] &= d[l];
- y[l] &= ~d[l];
- if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
- }
- if (finished) break;
- }
- if (k>z) z=k;
- if (k==MAXPAIR)
- {
- printf("Some bit didn't change: ");
- printf("%.8lx %.8lx %.8lx %.8lx %.8lx %.8lx ",
- e[0],f[0],g[0],h[0],x[0],y[0]);
- printf("i %ld j %ld m %ld len %ld\n",i,j,m,hlen);
- }
- if (z==MAXPAIR) goto done;
- }
- }
- }
- done:
- if (z < MAXPAIR)
- {
- printf("Mix success %2ld bytes %2ld initvals ",i,m);
- printf("required %ld trials\n",z/2);
- }
- }
- printf("\n");
-}
-
-/* Check for reading beyond the end of the buffer and alignment problems */
-void driver3()
-{
- ub1 buf[MAXLEN+20], *b;
- ub4 len;
- ub1 q[] = "This is the time for all good men to come to the aid of their country";
- ub1 qq[] = "xThis is the time for all good men to come to the aid of their country";
- ub1 qqq[] = "xxThis is the time for all good men to come to the aid of their country";
- ub1 qqqq[] = "xxxThis is the time for all good men to come to the aid of their country";
- ub4 h,i,j,ref,x,y;
-
- printf("Endianness. These should all be the same:\n");
- printf("%.8lx\n", hash(q, sizeof(q)-1, (ub4)0));
- printf("%.8lx\n", hash(qq+1, sizeof(q)-1, (ub4)0));
- printf("%.8lx\n", hash(qqq+2, sizeof(q)-1, (ub4)0));
- printf("%.8lx\n", hash(qqqq+3, sizeof(q)-1, (ub4)0));
- printf("\n");
- for (h=0, b=buf+1; h<8; ++h, ++b)
- {
- for (i=0; i<MAXLEN; ++i)
- {
- len = i;
- for (j=0; j<i; ++j) *(b+j)=0;
-
- /* these should all be equal */
- ref = hash(b, len, (ub4)1);
- *(b+i)=(ub1)~0;
- *(b-1)=(ub1)~0;
- x = hash(b, len, (ub4)1);
- y = hash(b, len, (ub4)1);
- if ((ref != x) || (ref != y))
- {
- printf("alignment error: %.8lx %.8lx %.8lx %ld %ld\n",ref,x,y,h,i);
- }
- }
- }
-}
-
-/* check for problems with nulls */
- void driver4()
-{
- ub1 buf[1];
- ub4 h,i,state[HASHSTATE];
-
-
- buf[0] = ~0;
- for (i=0; i<HASHSTATE; ++i) state[i] = 1;
- printf("These should all be different\n");
- for (i=0, h=0; i<8; ++i)
- {
- h = hash(buf, (ub4)0, h);
- printf("%2ld 0-byte strings, hash is %.8lx\n", i, h);
- }
-}
-
-
-int main()
-{
- driver1(); /* test that the key is hashed: used for timings */
- driver2(); /* test that whole key is hashed thoroughly */
- driver3(); /* test that nothing but the key is hashed */
- driver4(); /* test hashing multiple buffers (all buffers are null) */
- return 1;
-}
-
-#endif /* SELF_TEST */