From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id D45633841477 for ; Mon, 27 Jun 2022 13:41:10 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D45633841477 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.cz Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id ED8BA1FA72; Mon, 27 Jun 2022 13:41:09 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1656337269; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=sCluhSICChLkoBwymwWcNi9ooWF+CylrjdpLvihfooo=; b=BgoI14otYCnajAEM/8JXYAz/8QDFRyG6v+Gh7q20MA4jA0r1GDlGUDftU62+SVq5OkmPAx NUwAxk0GhuGH5fm6WRQWYpCRFYfROE/TxjTMsFJmNqfQRG9E+61uyD1egB1UhWG6rGhwTz DF258f0nDmeTGIk4LrYDWi8rbmk1htw= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1656337269; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: in-reply-to:in-reply-to:references:references; bh=sCluhSICChLkoBwymwWcNi9ooWF+CylrjdpLvihfooo=; b=qa5lFpRl+M+3vxmiPfRGeHvdvO9qAy9lYWEgPQ3tPyXlxVHJweJMKMUVf77Q/utumuTpOg /6NF82geWzFhbOBQ== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id D51CD13456; Mon, 27 Jun 2022 13:41:09 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id V/rbMnWzuWIwJQAAMHmgww (envelope-from ); Mon, 27 Jun 2022 13:41:09 +0000 Content-Type: multipart/mixed; boundary="------------T7Weww9EVkn66fceU0Wxj8p0" Message-ID: Date: Mon, 27 Jun 2022 15:41:09 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.10.0 Subject: Re: [PATCH] Use xxHash hashing algorithm. Content-Language: en-US To: Mark Wielaard Cc: dwz@sourceware.org References: <20220625194440.GA16194@gnu.wildebeest.org> From: =?UTF-8?Q?Martin_Li=c5=a1ka?= In-Reply-To: <20220625194440.GA16194@gnu.wildebeest.org> X-Spam-Status: No, score=-11.5 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_ASCII_DIVIDERS, NICE_REPLY_A, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: dwz@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Dwz mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 27 Jun 2022 13:41:15 -0000 This is a multi-part message in MIME format. --------------T7Weww9EVkn66fceU0Wxj8p0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit On 6/25/22 21:44, Mark Wielaard wrote: > Hi Martin, Hello. > > Could you resent this patch with git send-email or rebase it against > current master. As is it doesn't apply giving errors when trying to > use it with git am. Sure, rebased and attached to this email. > > BTW. One of the reasons that I haven't reviewed things before is > because I am getting one or more testsuite FAILs with newer Fedora > versions. Which makes checking for regressions somewhat hard. > > On Wed, Jan 05, 2022 at 09:17:37AM +0100, Martin Liška wrote: >> The algorithm provides the following speed-up with -O2: >> >> - 1/5: sysdig (60M) >> dwz_O2 : 9.7 >> dwz_O2_xxhash : 8.5 (87.7%) >> - 2/5: rtags (58M) >> dwz_O2 : 17.6 >> dwz_O2_xxhash : 15.8 (89.5%) >> - 3/5: libetonyek (91M) >> dwz_O2 : 10.8 >> dwz_O2_xxhash : 9.4 (86.7%) >> - 4/5: krita (685M) >> dwz_O2 : 96.0 >> dwz_O2_xxhash : 85.6 (89.1%) >> - 5/5: gcc (1.2G) >> dwz_O2 : 58.6 >> dwz_O2_xxhash : 54.1 (92.4%) > > So a speedup of ~10%. Nice. > >> --- >> Makefile | 4 +- >> dwz.c | 103 +++++++++++++++++++++++----------------- >> hashtab.c | 139 ------------------------------------------------------ >> hashtab.h | 6 ++- >> 4 files changed, 65 insertions(+), 187 deletions(-) > > We probably also need a configure change to detect whether xxhash is > actually available. With my patch, one will see a compilation error. Can you please help me with the configure detection? > >> diff --git a/Makefile b/Makefile >> index 9394ef4..89546c2 100644 >> --- a/Makefile >> +++ b/Makefile >> @@ -8,7 +8,7 @@ CFLAGS = -O2 -g >> DWZ_VERSION := $(shell cat $(srcdir)/VERSION) >> CFLAGS_VERSION = -DDWZ_VERSION='"$(DWZ_VERSION)"' >> CFLAGS_COPYRIGHT = $(shell cat $(srcdir)/COPYRIGHT_YEARS) >> -CFLAGS_COMMON = -Wall -W -D_FILE_OFFSET_BITS=64 >> +CFLAGS_COMMON = -Wall -W -D_FILE_OFFSET_BITS=64 -DXXH_INLINE_ALL=1 >> override CFLAGS += $(CFLAGS_COMMON) $(CFLAGS_VERSION) $(CFLAGS_COPYRIGHT) >> prefix = /usr >> @@ -17,7 +17,7 @@ bindir = $(exec_prefix)/bin >> datarootdir = $(prefix)/share >> mandir = $(datarootdir)/man >> OBJECTS = args.o dwz.o hashtab.o pool.o sha1.o dwarfnames.o >> -LIBS=-lelf >> +LIBS=-lelf -lxxhash >> dwz: $(OBJECTS) >> $(CC) $(LDFLAGS) -o $@ $^ $(LIBS) >> args.o: native.o > > So we use XXH_INLINE_ALL. Do we then still need to link with -lxxhash? Correct, it's not needed. > >> diff --git a/dwz.c b/dwz.c >> index a3b289f..cc68f4a 100644 >> --- a/dwz.c >> +++ b/dwz.c >> @@ -112,6 +112,21 @@ >> # define NT_GNU_BUILD_ID 3 >> #endif >> +/* xxHash state object. */ >> +static XXH64_state_t state; >> + >> +/* Clear xxHash state to zero. */ >> +#define hash_init_state() XXH64_reset(&state, 0) >> + >> +/* Update hash STATE with VALUE. */ >> +#define hash_update_state(value) XXH64_update(&state, &value, sizeof value) >> + >> +/* Update hash STATE with OBJECT that has a provided SIZE. */ >> +#define hash_update_state_object(object, size) XXH64_update(&state, object, size) >> + >> +/* Get digest once we are done with a state. */ >> +#define hash_digest() XXH64_digest(&state) > > Allocating and reusing the global state is convenient, but might make > parellizing dwz somewhat more complicated. Was this design used > deliberately, or can we easily switch to stack allocating the state? Yes, but the alternative approach would be making it a stack variable in each function where we use it. Note right now, processes are used for parallel execution. > > Also I find the naming slightly confusing. We used > iterative_hash_object to update a hash with an integral value, and > iterative_hash to update a hash with a size plus pointer. Now it seems > we swap the meaning. iterative_hash gets replace by > hash_update_state_object. And iterative_hash_object gets replaced by > hash_update_state. Was the meaning of "object" deliberately swapped? No, fixed that. > > Also it seems iterative_hash_object with inital zero value is replaced > by hash, which isn't defined here but in hashtab.h. Why the split in > definitions? All moved to dwz.c right now. > >> /* Print memory amount M (in kb) in both exact and human readable, like so: >> 1382508 (1.3G). */ >> static void >> @@ -1187,16 +1202,18 @@ compute_abbrev_hash (struct abbrev_tag *t) >> { >> unsigned int i; >> - t->hash = iterative_hash_object (t->tag, 0); >> - t->hash = iterative_hash_object (t->nattr, t->hash); >> - t->hash = iterative_hash_object (t->children, t->hash); >> + hash_init_state (); >> + hash_update_state (t->tag); >> + hash_update_state (t->nattr); >> + hash_update_state (t->children); >> for (i = 0; i < t->nattr; i++) >> { >> - t->hash = iterative_hash_object (t->attr[i].attr, t->hash); >> - t->hash = iterative_hash_object (t->attr[i].form, t->hash); >> + hash_update_state (t->attr[i].attr); >> + hash_update_state (t->attr[i].form); >> if (t->attr[i].form == DW_FORM_implicit_const) >> - t->hash = iterative_hash_object (t->values[i], t->hash); >> + hash_update_state (t->values[i]); >> } >> + t->hash = hash_digest (); >> } > > OK. > >> /* Maximum number of attributes in a DIE. */ >> @@ -3402,22 +3419,17 @@ checksum_die (DSO *dso, dw_cu_ref cu, dw_die_ref top_die, dw_die_ref die) >> struct dw_file *cu_file = &cu->cu_files[value - 1]; >> size_t file_len = strlen (cu_file->file); >> s = t->attr[i].attr; >> - die->u.p1.die_hash >> - = iterative_hash_object (s, die->u.p1.die_hash); >> - die->u.p1.die_hash >> - = iterative_hash_object (cu_file->time, >> - die->u.p1.die_hash); >> - die->u.p1.die_hash >> - = iterative_hash_object (cu_file->size, >> - die->u.p1.die_hash); >> - die->u.p1.die_hash >> - = iterative_hash (cu_file->file, file_len + 1, >> - die->u.p1.die_hash); >> + hash_init_state (); >> + hash_update_state (die->u.p1.die_hash); >> + hash_update_state (s); >> + hash_update_state (cu_file->time); >> + hash_update_state (cu_file->size); >> + hash_update_state_object (cu_file->file, file_len + 1); > > OK. > >> if (cu_file->dir) >> - die->u.p1.die_hash >> - = iterative_hash (cu_file->dir, >> - strlen (cu_file->dir) + 1, >> - die->u.p1.die_hash); >> + { >> + hash_update_state_object (cu_file->dir, >> + strlen (cu_file->dir) + 1); >> + } > > OK, assuming the die->u.p1.die_hash below are alwasy done/correct. > But brackets aren't really needed. > >> /* Ignore DW_AT_comp_dir for DW_AT_*_file >> etc. if immediately followed by DW_AT_*_line 0. */ >> else if (cu_file->file_angle_brackets_encapsulated_no_slash >> @@ -3427,7 +3439,13 @@ checksum_die (DSO *dso, dw_cu_ref cu, dw_die_ref top_die, dw_die_ref die) >> ? DW_AT_decl_line : DW_AT_call_line) >> && t->attr[i + 1].form == DW_FORM_data1 >> && *new_ptr == 0) >> - break; >> + { >> + die->u.p1.die_hash = hash_digest (); >> + break; >> + } >> + >> + die->u.p1.die_hash = hash_digest (); > > I find the logic hard to follow here. What makes sure the > die->u.p1.die_hash is always updated? Isn't it updated twice > (redundantly) in the above case? And needless brackets. Yeah, it's hard because the 'break;' means the next call to: die->u.p1.die_hash = hash_digest (); is not executed. And die->u.p1.die_hash is used in the current version as initial hash value (and it's modified in each iterative_hash_object call). > >> if (cu->cu_comp_dir >> && (cu_file->dir ? cu_file->dir[0] >> : cu_file->file[0]) != '/') >> @@ -5541,7 +5559,7 @@ strp_eq2 (const void *p, const void *q) >> static hashval_t >> strp_hash3 (const void *p) >> { >> - return iterative_hash (p, strlen (p), 0); >> + return hash (p, strlen (p)); >> } >> /* Corresponding equality function in strp_htab. */ > > OK. > >> @@ -5571,7 +5589,7 @@ note_strp_offset (unsigned int off) >> p = debug_sections[DEBUG_STR].data + off; >> len = strlen ((char *) p); >> - hash = iterative_hash (p, len, 0); >> + hash = hash (p, len); >> if (alt_strp_htab) >> { >> if (htab_find_with_hash (alt_strp_htab, p, hash)) > > OK. > >> @@ -5653,7 +5671,7 @@ lookup_strp_offset (unsigned int off) >> p = debug_sections[DEBUG_STR].data + off; >> len = strlen ((char *) p); >> - hash = iterative_hash (p, len, 0); >> + hash = hash (p, len); >> if (alt_strp_htab) >> { >> unsigned char *q = (unsigned char *) > > OK. > >> @@ -5694,7 +5712,7 @@ note_strp_offset2 (unsigned int off) >> { >> p = debug_sections[DEBUG_STR].data + off; >> len = strlen ((char *) p); >> - hash = iterative_hash (p, len, 0); >> + hash = hash (p, len); >> if (htab_find_with_hash (alt_strp_htab, p, hash)) >> return dwarf_5 ? DW_FORM_strp_sup : DW_FORM_GNU_strp_alt; >> } > > OK. > >> @@ -5704,7 +5722,7 @@ note_strp_offset2 (unsigned int off) >> return DW_FORM_strp; >> p = debug_sections[DEBUG_STR].data + off; >> q = (unsigned char *) strchr ((char *) p, '\0'); >> - hash = iterative_hash (p, q - p, 0); >> + hash = hash (p, q - p); >> se.off = off; >> se.new_off = hash & ~1U; >> struct strp_entry *s = (struct strp_entry *) > > OK. > >> @@ -5860,7 +5878,7 @@ finalize_strp (bool build_tail_offset_list) >> memcpy (p, debug_sections[DEBUG_STR].data + arr[i]->off, len); >> slot = htab_find_slot_with_hash (strp_htab, p, >> - iterative_hash (p, len - 1, 0), >> + hash (p, len - 1), >> INSERT); >> if (slot == NULL) >> dwz_oom (); > > OK. > >> @@ -5876,7 +5894,7 @@ finalize_strp (bool build_tail_offset_list) >> if (tail_offset_list != NULL) >> tail_offset_list[k++] = arr[j]->new_off; >> slot = htab_find_slot_with_hash (strp_htab, q, >> - iterative_hash (q, l - 1, 0), >> + hash (q, l - 1), >> INSERT); >> if (slot == NULL) >> dwz_oom (); > > OK. > >> @@ -9849,17 +9867,16 @@ line_htab_lookup (dw_cu_ref cu, unsigned int id) >> { >> void **slot; >> struct line_entry le; >> - hashval_t h; >> - >> if (id == 0) >> return 0; >> assert (id <= cu->cu_nfiles); >> le.file = &cu->cu_files[id - 1]; >> - h = iterative_hash_object (le.file->time, 0); >> - h = iterative_hash_object (le.file->size, h); >> - h = iterative_hash (le.file->file, strlen (le.file->file) + 1, h); >> + hash_init_state (); >> + hash_update_state (le.file->time); >> + hash_update_state (le.file->size); >> + hash_update_state_object (le.file->file, strlen (le.file->file) + 1); >> if (le.file->dir) >> - h = iterative_hash (le.file->dir, strlen (le.file->dir) + 1, h); >> + hash_update_state_object (le.file->dir, strlen (le.file->dir) + 1); >> if (line_htab == NULL) >> { >> line_htab = htab_try_create (50, line_hash, line_eq, NULL); >> @@ -9867,15 +9884,15 @@ line_htab_lookup (dw_cu_ref cu, unsigned int id) >> dwz_oom (); >> max_line_id = 1; >> } >> - le.hash = h; >> - slot = htab_find_slot_with_hash (line_htab, &le, h, INSERT); >> + le.hash = hash_digest ();; >> + slot = htab_find_slot_with_hash (line_htab, &le, le.hash, INSERT); > > OK, but double ;; Fixed. > >> if (slot == NULL) >> dwz_oom (); >> if (*slot == NULL) >> { >> struct line_entry *l = pool_alloc (line_entry, sizeof (*l)); >> l->file = le.file; >> - l->hash = h; >> + l->hash = le.hash; >> l->new_id = max_line_id++; >> *slot = (void *) l; >> return l->new_id; > > OK. > >> @@ -10347,7 +10364,7 @@ handle_macro (void) >> /* This should only happen if there were multiple >> same transparent units within a single object file. */ >> && htab_find_with_hash (strp_htab, p, >> - iterative_hash (p, len, 0)) == NULL) >> + hash (p, len)) == NULL) >> can_share = false; >> s = ptr; >> break; > > OK. > >> @@ -15756,7 +15773,7 @@ optimize_multifile (unsigned int *die_count) >> hashval_t hash; >> q = (unsigned char *) strchr ((char *) p, '\0'); >> - hash = iterative_hash (p, q - p, 0); >> + hash = hash (p, q - p); >> se.off = p - debug_sections[DEBUG_STR].data; >> se.new_off = hash & ~1U; >> slot = htab_find_slot_with_hash (strp_htab, &se, se.new_off, INSERT); > > OK. > >> @@ -16076,8 +16093,7 @@ read_multifile (int fd, unsigned int die_count) >> { >> q = (unsigned char *) strchr ((char *) p, '\0') + 1; >> slot = htab_find_slot_with_hash (strp_htab, p, >> - iterative_hash (p, q - p - 1, >> - 0), INSERT); >> + hash (p, q - p - 1), INSERT); >> if (slot == NULL) >> dwz_oom (); >> assert (*slot == NULL); > > OK. > >> @@ -16090,8 +16106,7 @@ read_multifile (int fd, unsigned int die_count) >> p = debug_sections[DEBUG_STR].data + *pi; >> q = (unsigned char *) strchr ((char *) p, '\0'); >> slot = htab_find_slot_with_hash (strp_htab, p, >> - iterative_hash (p, q - p, >> - 0), INSERT); >> + hash (p, q - p), INSERT); >> if (slot == NULL) >> dwz_oom (); >> assert (*slot == NULL); > > OK. > >> diff --git a/hashtab.c b/hashtab.c >> index 41eab30..a9b9d13 100644 >> --- a/hashtab.c >> +++ b/hashtab.c >> @@ -626,142 +626,3 @@ htab_restore (htab, name, restorefn) >> fclose (f); >> } >> #endif >> - >> -/* DERIVED FROM: >> --------------------------------------------------------------------- >> -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. >> --------------------------------------------------------------------- >> -*/ >> - >> -/* >> --------------------------------------------------------------------- >> -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. >> --------------------------------------------------------------------- >> -*/ >> -/* same, but slower, works on systems that might have 8 byte hashval_t's */ >> -#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&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> - >> -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://burtleburtle.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. >> --------------------------------------------------------------------- >> -*/ >> - >> -hashval_t >> -iterative_hash (const void *k_in /* the key */, >> - register size_t length /* the length of the key */, >> - register hashval_t initval /* the previous hash, or >> - an arbitrary value */) >> -{ >> - register const unsigned char *k = (const unsigned char *)k_in; >> - register hashval_t 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 */ >> -#ifndef WORDS_BIGENDIAN >> - /* On a little-endian machine, if the data is 4-byte aligned we can hash >> - by word for better speed. This gives nondeterministic results on >> - big-endian machines. */ >> - if (sizeof (hashval_t) == 4 && (((size_t)k)&3) == 0) >> - while (len >= 12) /* aligned */ >> - { >> - a += *(hashval_t *)(k+0); >> - b += *(hashval_t *)(k+4); >> - c += *(hashval_t *)(k+8); >> - mix(a,b,c); >> - k += 12; len -= 12; >> - } >> - else /* unaligned */ >> -#endif >> - while (len >= 12) >> - { >> - a += (k[0] +((hashval_t)k[1]<<8) +((hashval_t)k[2]<<16) +((hashval_t)k[3]<<24)); >> - b += (k[4] +((hashval_t)k[5]<<8) +((hashval_t)k[6]<<16) +((hashval_t)k[7]<<24)); >> - c += (k[8] +((hashval_t)k[9]<<8) +((hashval_t)k[10]<<16)+((hashval_t)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+=((hashval_t)k[10]<<24); /* fall through */ >> - case 10: c+=((hashval_t)k[9]<<16); /* fall through */ >> - case 9 : c+=((hashval_t)k[8]<<8); /* fall through */ >> - /* the first byte of c is reserved for the length */ >> - case 8 : b+=((hashval_t)k[7]<<24); /* fall through */ >> - case 7 : b+=((hashval_t)k[6]<<16); /* fall through */ >> - case 6 : b+=((hashval_t)k[5]<<8); /* fall through */ >> - case 5 : b+=k[4]; /* fall through */ >> - case 4 : a+=((hashval_t)k[3]<<24); /* fall through */ >> - case 3 : a+=((hashval_t)k[2]<<16); /* fall through */ >> - case 2 : a+=((hashval_t)k[1]<<8); /* fall through */ >> - case 1 : a+=k[0]; >> - /* case 0: nothing left to add */ >> - } >> - mix(a,b,c); >> - /*-------------------------------------------- report the result */ >> - return c; >> -} >> diff --git a/hashtab.h b/hashtab.h >> index cb3da01..509e627 100644 >> --- a/hashtab.h >> +++ b/hashtab.h >> @@ -153,9 +153,11 @@ extern void htab_restore (htab_t, const char *, htab_restorefn); >> #endif >> -/* An iterative hash function for arbitrary data. */ >> -extern hashval_t iterative_hash (const void *, size_t, hashval_t); >> +#include >> + >> /* Shorthand for hashing something with an intrinsic size. */ >> +#define hash(IN,LEN) XXH64(IN, LEN, 0) >> +#define iterative_hash(IN,LEN,INIT) XXH64(IN, LEN, INIT) >> #define iterative_hash_object(OB,INIT) iterative_hash (&OB, sizeof (OB), INIT) >> #ifdef __cplusplus > > See above for the question why everything hash related isn't defined > in the same place. Done. > > How much of hashtab.{c,h} are we still using? wc -l hashtab.[ch] 628 hashtab.c 160 hashtab.h 788 total with my patch. Please take a look at the updated patch. Martin > > Thanks, > > Mark --------------T7Weww9EVkn66fceU0Wxj8p0 Content-Type: text/x-patch; charset=UTF-8; name="0001-Use-xxHash-hashing-algorithm.patch" Content-Disposition: attachment; filename="0001-Use-xxHash-hashing-algorithm.patch" Content-Transfer-Encoding: base64 RnJvbSA1MWRhYmI1NzE1MTNiYmY4ODdjODZlOWViZjFiNGU0M2RlZTZlYmMzIE1vbiBTZXAg MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBNYXJ0aW4gTGlza2EgPG1saXNrYUBzdXNlLmN6PgpE YXRlOiBXZWQsIDIyIERlYyAyMDIxIDE0OjQ1OjQwICswMTAwClN1YmplY3Q6IFtQQVRDSF0g VXNlIHh4SGFzaCBoYXNoaW5nIGFsZ29yaXRobS4KClRoZSBhbGdvcml0aG0gcHJvdmlkZXMg dGhlIGZvbGxvd2luZyBzcGVlZC11cCB3aXRoIC1PMjoKCi0gMS81OiBzeXNkaWcgKDYwTSkK ZHd6X08yICAgICAgICAgICAgICAgIDogOS43CmR3el9PMl94eGhhc2ggICAgICAgICA6IDgu NSAoODcuNyUpCi0gMi81OiBydGFncyAoNThNKQpkd3pfTzIgICAgICAgICAgICAgICAgOiAx Ny42CmR3el9PMl94eGhhc2ggICAgICAgICA6IDE1LjggKDg5LjUlKQotIDMvNTogbGliZXRv bnllayAoOTFNKQpkd3pfTzIgICAgICAgICAgICAgICAgOiAxMC44CmR3el9PMl94eGhhc2gg ICAgICAgICA6IDkuNCAoODYuNyUpCi0gNC81OiBrcml0YSAoNjg1TSkKZHd6X08yICAgICAg ICAgICAgICAgIDogOTYuMApkd3pfTzJfeHhoYXNoICAgICAgICAgOiA4NS42ICg4OS4xJSkK LSA1LzU6IGdjYyAoMS4yRykKZHd6X08yICAgICAgICAgICAgICAgIDogNTguNgpkd3pfTzJf eHhoYXNoICAgICAgICAgOiA1NC4xICg5Mi40JSkKLS0tCiBNYWtlZmlsZSAgfCAgIDIgKy0K IGR3ei5jICAgICB8IDExMCArKysrKysrKysrKysrKysrKysrKysrKysrLS0tLS0tLS0tLS0t LS0tLS0KIGhhc2h0YWIuYyB8IDEzOSAtLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KIGhhc2h0YWIuaCB8ICAgNSAtLQogNCBmaWxlcyBj aGFuZ2VkLCA2NyBpbnNlcnRpb25zKCspLCAxODkgZGVsZXRpb25zKC0pCgpkaWZmIC0tZ2l0 IGEvTWFrZWZpbGUgYi9NYWtlZmlsZQppbmRleCA5Mzk0ZWY0Li5lOTE5M2Y5IDEwMDY0NAot LS0gYS9NYWtlZmlsZQorKysgYi9NYWtlZmlsZQpAQCAtOCw3ICs4LDcgQEAgQ0ZMQUdTID0g LU8yIC1nCiBEV1pfVkVSU0lPTiA6PSAkKHNoZWxsIGNhdCAkKHNyY2RpcikvVkVSU0lPTikK IENGTEFHU19WRVJTSU9OID0gLUREV1pfVkVSU0lPTj0nIiQoRFdaX1ZFUlNJT04pIicKIENG TEFHU19DT1BZUklHSFQgPSAkKHNoZWxsIGNhdCAkKHNyY2RpcikvQ09QWVJJR0hUX1lFQVJT KQotQ0ZMQUdTX0NPTU1PTiA9IC1XYWxsIC1XIC1EX0ZJTEVfT0ZGU0VUX0JJVFM9NjQKK0NG TEFHU19DT01NT04gPSAtV2FsbCAtVyAtRF9GSUxFX09GRlNFVF9CSVRTPTY0IC1EWFhIX0lO TElORV9BTEw9MQogb3ZlcnJpZGUgQ0ZMQUdTICs9ICQoQ0ZMQUdTX0NPTU1PTikgJChDRkxB R1NfVkVSU0lPTikgJChDRkxBR1NfQ09QWVJJR0hUKQogCiBwcmVmaXggPSAvdXNyCmRpZmYg LS1naXQgYS9kd3ouYyBiL2R3ei5jCmluZGV4IGEzYjI4OWYuLjg5NzNhNDIgMTAwNjQ0Ci0t LSBhL2R3ei5jCisrKyBiL2R3ei5jCkBAIC0zOSw2ICszOSw4IEBACiAjaW5jbHVkZSA8b2Jz dGFjay5oPgogCiAjaW5jbHVkZSA8Z2VsZi5oPgorI2luY2x1ZGUgPHh4aGFzaC5oPgorCiAj aW5jbHVkZSAiZHdhcmYyLmgiCiAjaW5jbHVkZSAiaGFzaHRhYi5oIgogI2luY2x1ZGUgInNo YTEuaCIKQEAgLTExMiw2ICsxMTQsMjYgQEAKICMgZGVmaW5lIE5UX0dOVV9CVUlMRF9JRCAz CiAjZW5kaWYKIAorLyogeHhIYXNoIHN0YXRlIG9iamVjdC4gICovCitzdGF0aWMgWFhINjRf c3RhdGVfdCBzdGF0ZTsKKworLyogQ2xlYXIgeHhIYXNoIHN0YXRlIHRvIHplcm8uICAqLwor I2RlZmluZSBoYXNoX2luaXRfc3RhdGUoKSBYWEg2NF9yZXNldCgmc3RhdGUsIDApCisKKy8q IFVwZGF0ZSBoYXNoIFNUQVRFIHdpdGggVkFMVUUuICAqLworI2RlZmluZSBoYXNoX3VwZGF0 ZV9zdGF0ZV9vYmplY3QodmFsdWUpIFhYSDY0X3VwZGF0ZSgmc3RhdGUsICZ2YWx1ZSwgc2l6 ZW9mIHZhbHVlKQorCisvKiBVcGRhdGUgaGFzaCBTVEFURSB3aXRoIE9CSkVDVCB0aGF0IGhh cyBhIHByb3ZpZGVkIFNJWkUuICAqLworI2RlZmluZSBoYXNoX3VwZGF0ZV9zdGF0ZShvYmpl Y3QsIHNpemUpIFhYSDY0X3VwZGF0ZSgmc3RhdGUsIG9iamVjdCwgc2l6ZSkKKworLyogR2V0 IGRpZ2VzdCBvbmNlIHdlIGFyZSBkb25lIHdpdGggYSBzdGF0ZS4gICovCisjZGVmaW5lIGhh c2hfZGlnZXN0KCkgWFhINjRfZGlnZXN0KCZzdGF0ZSkKKworLyogU2hvcnRoYW5kIGZvciBo YXNoaW5nIHNvbWV0aGluZyB3aXRoIGFuIGludHJpbnNpYyBzaXplLiAgKi8KKyNkZWZpbmUg aGFzaChJTixMRU4pIFhYSDY0KElOLCBMRU4sIDApCisjZGVmaW5lIGl0ZXJhdGl2ZV9oYXNo KElOLExFTixJTklUKSBYWEg2NChJTiwgTEVOLCBJTklUKQorI2RlZmluZSBpdGVyYXRpdmVf aGFzaF9vYmplY3QoT0IsSU5JVCkgaXRlcmF0aXZlX2hhc2ggKCZPQiwgc2l6ZW9mIChPQiks IElOSVQpCisKIC8qIFByaW50IG1lbW9yeSBhbW91bnQgTSAoaW4ga2IpIGluIGJvdGggZXhh Y3QgYW5kIGh1bWFuIHJlYWRhYmxlLCBsaWtlIHNvOgogICAgMTM4MjUwOCAoMS4zRykuICAq Lwogc3RhdGljIHZvaWQKQEAgLTExODcsMTYgKzEyMDksMTggQEAgY29tcHV0ZV9hYmJyZXZf aGFzaCAoc3RydWN0IGFiYnJldl90YWcgKnQpCiB7CiAgIHVuc2lnbmVkIGludCBpOwogCi0g IHQtPmhhc2ggPSBpdGVyYXRpdmVfaGFzaF9vYmplY3QgKHQtPnRhZywgMCk7Ci0gIHQtPmhh c2ggPSBpdGVyYXRpdmVfaGFzaF9vYmplY3QgKHQtPm5hdHRyLCB0LT5oYXNoKTsKLSAgdC0+ aGFzaCA9IGl0ZXJhdGl2ZV9oYXNoX29iamVjdCAodC0+Y2hpbGRyZW4sIHQtPmhhc2gpOwor ICBoYXNoX2luaXRfc3RhdGUgKCk7CisgIGhhc2hfdXBkYXRlX3N0YXRlX29iamVjdCAodC0+ dGFnKTsKKyAgaGFzaF91cGRhdGVfc3RhdGVfb2JqZWN0ICh0LT5uYXR0cik7CisgIGhhc2hf dXBkYXRlX3N0YXRlX29iamVjdCAodC0+Y2hpbGRyZW4pOwogICBmb3IgKGkgPSAwOyBpIDwg dC0+bmF0dHI7IGkrKykKICAgICB7Ci0gICAgICB0LT5oYXNoID0gaXRlcmF0aXZlX2hhc2hf b2JqZWN0ICh0LT5hdHRyW2ldLmF0dHIsIHQtPmhhc2gpOwotICAgICAgdC0+aGFzaCA9IGl0 ZXJhdGl2ZV9oYXNoX29iamVjdCAodC0+YXR0cltpXS5mb3JtLCB0LT5oYXNoKTsKKyAgICAg IGhhc2hfdXBkYXRlX3N0YXRlX29iamVjdCAodC0+YXR0cltpXS5hdHRyKTsKKyAgICAgIGhh c2hfdXBkYXRlX3N0YXRlX29iamVjdCAodC0+YXR0cltpXS5mb3JtKTsKICAgICAgIGlmICh0 LT5hdHRyW2ldLmZvcm0gPT0gRFdfRk9STV9pbXBsaWNpdF9jb25zdCkKLQl0LT5oYXNoID0g aXRlcmF0aXZlX2hhc2hfb2JqZWN0ICh0LT52YWx1ZXNbaV0sIHQtPmhhc2gpOworCWhhc2hf dXBkYXRlX3N0YXRlX29iamVjdCAodC0+dmFsdWVzW2ldKTsKICAgICB9CisgIHQtPmhhc2gg PSBoYXNoX2RpZ2VzdCAoKTsKIH0KIAogLyogTWF4aW11bSBudW1iZXIgb2YgYXR0cmlidXRl cyBpbiBhIERJRS4gICovCkBAIC0zNDAyLDIyICszNDI2LDE3IEBAIGNoZWNrc3VtX2RpZSAo RFNPICpkc28sIGR3X2N1X3JlZiBjdSwgZHdfZGllX3JlZiB0b3BfZGllLCBkd19kaWVfcmVm IGRpZSkKIAkJICBzdHJ1Y3QgZHdfZmlsZSAqY3VfZmlsZSA9ICZjdS0+Y3VfZmlsZXNbdmFs dWUgLSAxXTsKIAkJICBzaXplX3QgZmlsZV9sZW4gPSBzdHJsZW4gKGN1X2ZpbGUtPmZpbGUp OwogCQkgIHMgPSB0LT5hdHRyW2ldLmF0dHI7Ci0JCSAgZGllLT51LnAxLmRpZV9oYXNoCi0J CSAgICA9IGl0ZXJhdGl2ZV9oYXNoX29iamVjdCAocywgZGllLT51LnAxLmRpZV9oYXNoKTsK LQkJICBkaWUtPnUucDEuZGllX2hhc2gKLQkJICAgID0gaXRlcmF0aXZlX2hhc2hfb2JqZWN0 IChjdV9maWxlLT50aW1lLAotCQkJCQkgICAgIGRpZS0+dS5wMS5kaWVfaGFzaCk7Ci0JCSAg ZGllLT51LnAxLmRpZV9oYXNoCi0JCSAgICA9IGl0ZXJhdGl2ZV9oYXNoX29iamVjdCAoY3Vf ZmlsZS0+c2l6ZSwKLQkJCQkJICAgICBkaWUtPnUucDEuZGllX2hhc2gpOwotCQkgIGRpZS0+ dS5wMS5kaWVfaGFzaAotCQkgICAgPSBpdGVyYXRpdmVfaGFzaCAoY3VfZmlsZS0+ZmlsZSwg ZmlsZV9sZW4gKyAxLAotCQkJCSAgICAgIGRpZS0+dS5wMS5kaWVfaGFzaCk7CisJCSAgaGFz aF9pbml0X3N0YXRlICgpOworCQkgIGhhc2hfdXBkYXRlX3N0YXRlX29iamVjdCAoZGllLT51 LnAxLmRpZV9oYXNoKTsKKwkJICBoYXNoX3VwZGF0ZV9zdGF0ZV9vYmplY3QgKHMpOworCQkg IGhhc2hfdXBkYXRlX3N0YXRlX29iamVjdCAoY3VfZmlsZS0+dGltZSk7CisJCSAgaGFzaF91 cGRhdGVfc3RhdGVfb2JqZWN0IChjdV9maWxlLT5zaXplKTsKKwkJICBoYXNoX3VwZGF0ZV9z dGF0ZSAoY3VfZmlsZS0+ZmlsZSwgZmlsZV9sZW4gKyAxKTsKIAkJICBpZiAoY3VfZmlsZS0+ ZGlyKQotCQkgICAgZGllLT51LnAxLmRpZV9oYXNoCi0JCSAgICAgID0gaXRlcmF0aXZlX2hh c2ggKGN1X2ZpbGUtPmRpciwKLQkJCQkJc3RybGVuIChjdV9maWxlLT5kaXIpICsgMSwKLQkJ CQkJZGllLT51LnAxLmRpZV9oYXNoKTsKKwkJICAgIHsKKwkJICAgICAgaGFzaF91cGRhdGVf c3RhdGUgKGN1X2ZpbGUtPmRpciwKKwkJCQkJCXN0cmxlbiAoY3VfZmlsZS0+ZGlyKSArIDEp OworCQkgICAgfQogCQkgIC8qIElnbm9yZSBEV19BVF9jb21wX2RpciBmb3IgRFdfQVRfKl9m aWxlIDxidWlsdC1pbj4KIAkJICAgICBldGMuIGlmIGltbWVkaWF0ZWx5IGZvbGxvd2VkIGJ5 IERXX0FUXypfbGluZSAwLiAgKi8KIAkJICBlbHNlIGlmIChjdV9maWxlLT5maWxlX2FuZ2xl X2JyYWNrZXRzX2VuY2Fwc3VsYXRlZF9ub19zbGFzaApAQCAtMzQyNyw3ICszNDQ2LDEzIEBA IGNoZWNrc3VtX2RpZSAoRFNPICpkc28sIGR3X2N1X3JlZiBjdSwgZHdfZGllX3JlZiB0b3Bf ZGllLCBkd19kaWVfcmVmIGRpZSkKIAkJCQkgID8gRFdfQVRfZGVjbF9saW5lIDogRFdfQVRf Y2FsbF9saW5lKQogCQkJICAgJiYgdC0+YXR0cltpICsgMV0uZm9ybSA9PSBEV19GT1JNX2Rh dGExCiAJCQkgICAmJiAqbmV3X3B0ciA9PSAwKQotCQkgICAgYnJlYWs7CisJCSAgICB7CisJ CSAgICAgIGRpZS0+dS5wMS5kaWVfaGFzaCA9IGhhc2hfZGlnZXN0ICgpOworCQkgICAgICBi cmVhazsKKwkJICAgIH0KKworCQkgIGRpZS0+dS5wMS5kaWVfaGFzaCA9IGhhc2hfZGlnZXN0 ICgpOworCiAJCSAgaWYgKGN1LT5jdV9jb21wX2RpcgogCQkgICAgICAmJiAoY3VfZmlsZS0+ ZGlyID8gY3VfZmlsZS0+ZGlyWzBdCiAJCQkJICAgICAgIDogY3VfZmlsZS0+ZmlsZVswXSkg IT0gJy8nKQpAQCAtNTU0MSw3ICs1NTY2LDcgQEAgc3RycF9lcTIgKGNvbnN0IHZvaWQgKnAs IGNvbnN0IHZvaWQgKnEpCiBzdGF0aWMgaGFzaHZhbF90CiBzdHJwX2hhc2gzIChjb25zdCB2 b2lkICpwKQogewotICByZXR1cm4gaXRlcmF0aXZlX2hhc2ggKHAsIHN0cmxlbiAocCksIDAp OworICByZXR1cm4gaGFzaCAocCwgc3RybGVuIChwKSk7CiB9CiAKIC8qIENvcnJlc3BvbmRp bmcgZXF1YWxpdHkgZnVuY3Rpb24gaW4gc3RycF9odGFiLiAgKi8KQEAgLTU1NzEsNyArNTU5 Niw3IEBAIG5vdGVfc3RycF9vZmZzZXQgKHVuc2lnbmVkIGludCBvZmYpCiAKICAgICAgIHAg PSBkZWJ1Z19zZWN0aW9uc1tERUJVR19TVFJdLmRhdGEgKyBvZmY7CiAgICAgICBsZW4gPSBz dHJsZW4gKChjaGFyICopIHApOwotICAgICAgaGFzaCA9IGl0ZXJhdGl2ZV9oYXNoIChwLCBs ZW4sIDApOworICAgICAgaGFzaCA9IGhhc2ggKHAsIGxlbik7CiAgICAgICBpZiAoYWx0X3N0 cnBfaHRhYikKIAl7CiAJICBpZiAoaHRhYl9maW5kX3dpdGhfaGFzaCAoYWx0X3N0cnBfaHRh YiwgcCwgaGFzaCkpCkBAIC01NjUzLDcgKzU2NzgsNyBAQCBsb29rdXBfc3RycF9vZmZzZXQg KHVuc2lnbmVkIGludCBvZmYpCiAKICAgICAgIHAgPSBkZWJ1Z19zZWN0aW9uc1tERUJVR19T VFJdLmRhdGEgKyBvZmY7CiAgICAgICBsZW4gPSBzdHJsZW4gKChjaGFyICopIHApOwotICAg ICAgaGFzaCA9IGl0ZXJhdGl2ZV9oYXNoIChwLCBsZW4sIDApOworICAgICAgaGFzaCA9IGhh c2ggKHAsIGxlbik7CiAgICAgICBpZiAoYWx0X3N0cnBfaHRhYikKIAl7CiAJICB1bnNpZ25l ZCBjaGFyICpxID0gKHVuc2lnbmVkIGNoYXIgKikKQEAgLTU2OTQsNyArNTcxOSw3IEBAIG5v dGVfc3RycF9vZmZzZXQyICh1bnNpZ25lZCBpbnQgb2ZmKQogCXsKIAkgIHAgPSBkZWJ1Z19z ZWN0aW9uc1tERUJVR19TVFJdLmRhdGEgKyBvZmY7CiAJICBsZW4gPSBzdHJsZW4gKChjaGFy ICopIHApOwotCSAgaGFzaCA9IGl0ZXJhdGl2ZV9oYXNoIChwLCBsZW4sIDApOworCSAgaGFz aCA9IGhhc2ggKHAsIGxlbik7CiAJICBpZiAoaHRhYl9maW5kX3dpdGhfaGFzaCAoYWx0X3N0 cnBfaHRhYiwgcCwgaGFzaCkpCiAJICAgIHJldHVybiBkd2FyZl81ID8gRFdfRk9STV9zdHJw X3N1cCA6IERXX0ZPUk1fR05VX3N0cnBfYWx0OwogCX0KQEAgLTU3MDQsNyArNTcyOSw3IEBA IG5vdGVfc3RycF9vZmZzZXQyICh1bnNpZ25lZCBpbnQgb2ZmKQogICAgIHJldHVybiBEV19G T1JNX3N0cnA7CiAgIHAgPSBkZWJ1Z19zZWN0aW9uc1tERUJVR19TVFJdLmRhdGEgKyBvZmY7 CiAgIHEgPSAodW5zaWduZWQgY2hhciAqKSBzdHJjaHIgKChjaGFyICopIHAsICdcMCcpOwot ICBoYXNoID0gaXRlcmF0aXZlX2hhc2ggKHAsIHEgLSBwLCAwKTsKKyAgaGFzaCA9IGhhc2gg KHAsIHEgLSBwKTsKICAgc2Uub2ZmID0gb2ZmOwogICBzZS5uZXdfb2ZmID0gaGFzaCAmIH4x VTsKICAgc3RydWN0IHN0cnBfZW50cnkgKnMgPSAoc3RydWN0IHN0cnBfZW50cnkgKikKQEAg LTU4NjAsNyArNTg4NSw3IEBAIGZpbmFsaXplX3N0cnAgKGJvb2wgYnVpbGRfdGFpbF9vZmZz ZXRfbGlzdCkKIAogCW1lbWNweSAocCwgZGVidWdfc2VjdGlvbnNbREVCVUdfU1RSXS5kYXRh ICsgYXJyW2ldLT5vZmYsIGxlbik7CiAJc2xvdCA9IGh0YWJfZmluZF9zbG90X3dpdGhfaGFz aCAoc3RycF9odGFiLCBwLAotCQkJCQkgaXRlcmF0aXZlX2hhc2ggKHAsIGxlbiAtIDEsIDAp LAorCQkJCQkgaGFzaCAocCwgbGVuIC0gMSksCiAJCQkJCSBJTlNFUlQpOwogCWlmIChzbG90 ID09IE5VTEwpCiAJICBkd3pfb29tICgpOwpAQCAtNTg3Niw3ICs1OTAxLDcgQEAgZmluYWxp emVfc3RycCAoYm9vbCBidWlsZF90YWlsX29mZnNldF9saXN0KQogCSAgICAgIGlmICh0YWls X29mZnNldF9saXN0ICE9IE5VTEwpCiAJCXRhaWxfb2Zmc2V0X2xpc3RbaysrXSA9IGFycltq XS0+bmV3X29mZjsKIAkgICAgICBzbG90ID0gaHRhYl9maW5kX3Nsb3Rfd2l0aF9oYXNoIChz dHJwX2h0YWIsIHEsCi0JCQkJCSAgICAgICBpdGVyYXRpdmVfaGFzaCAocSwgbCAtIDEsIDAp LAorCQkJCQkgICAgICAgaGFzaCAocSwgbCAtIDEpLAogCQkJCQkgICAgICAgSU5TRVJUKTsK IAkgICAgICBpZiAoc2xvdCA9PSBOVUxMKQogCQlkd3pfb29tICgpOwpAQCAtOTg0OSwxNyAr OTg3NCwxNiBAQCBsaW5lX2h0YWJfbG9va3VwIChkd19jdV9yZWYgY3UsIHVuc2lnbmVkIGlu dCBpZCkKIHsKICAgdm9pZCAqKnNsb3Q7CiAgIHN0cnVjdCBsaW5lX2VudHJ5IGxlOwotICBo YXNodmFsX3QgaDsKLQogICBpZiAoaWQgPT0gMCkKICAgICByZXR1cm4gMDsKICAgYXNzZXJ0 IChpZCA8PSBjdS0+Y3VfbmZpbGVzKTsKICAgbGUuZmlsZSA9ICZjdS0+Y3VfZmlsZXNbaWQg LSAxXTsKLSAgaCA9IGl0ZXJhdGl2ZV9oYXNoX29iamVjdCAobGUuZmlsZS0+dGltZSwgMCk7 Ci0gIGggPSBpdGVyYXRpdmVfaGFzaF9vYmplY3QgKGxlLmZpbGUtPnNpemUsIGgpOwotICBo ID0gaXRlcmF0aXZlX2hhc2ggKGxlLmZpbGUtPmZpbGUsIHN0cmxlbiAobGUuZmlsZS0+Zmls ZSkgKyAxLCBoKTsKKyAgaGFzaF9pbml0X3N0YXRlICgpOworICBoYXNoX3VwZGF0ZV9zdGF0 ZV9vYmplY3QgKGxlLmZpbGUtPnRpbWUpOworICBoYXNoX3VwZGF0ZV9zdGF0ZV9vYmplY3Qg KGxlLmZpbGUtPnNpemUpOworICBoYXNoX3VwZGF0ZV9zdGF0ZSAobGUuZmlsZS0+ZmlsZSwg c3RybGVuIChsZS5maWxlLT5maWxlKSArIDEpOwogICBpZiAobGUuZmlsZS0+ZGlyKQotICAg IGggPSBpdGVyYXRpdmVfaGFzaCAobGUuZmlsZS0+ZGlyLCBzdHJsZW4gKGxlLmZpbGUtPmRp cikgKyAxLCBoKTsKKyAgICBoYXNoX3VwZGF0ZV9zdGF0ZSAobGUuZmlsZS0+ZGlyLCBzdHJs ZW4gKGxlLmZpbGUtPmRpcikgKyAxKTsKICAgaWYgKGxpbmVfaHRhYiA9PSBOVUxMKQogICAg IHsKICAgICAgIGxpbmVfaHRhYiA9IGh0YWJfdHJ5X2NyZWF0ZSAoNTAsIGxpbmVfaGFzaCwg bGluZV9lcSwgTlVMTCk7CkBAIC05ODY3LDE1ICs5ODkxLDE1IEBAIGxpbmVfaHRhYl9sb29r dXAgKGR3X2N1X3JlZiBjdSwgdW5zaWduZWQgaW50IGlkKQogCWR3el9vb20gKCk7CiAgICAg ICBtYXhfbGluZV9pZCA9IDE7CiAgICAgfQotICBsZS5oYXNoID0gaDsKLSAgc2xvdCA9IGh0 YWJfZmluZF9zbG90X3dpdGhfaGFzaCAobGluZV9odGFiLCAmbGUsIGgsIElOU0VSVCk7Cisg IGxlLmhhc2ggPSBoYXNoX2RpZ2VzdCAoKTsKKyAgc2xvdCA9IGh0YWJfZmluZF9zbG90X3dp dGhfaGFzaCAobGluZV9odGFiLCAmbGUsIGxlLmhhc2gsIElOU0VSVCk7CiAgIGlmIChzbG90 ID09IE5VTEwpCiAgICAgZHd6X29vbSAoKTsKICAgaWYgKCpzbG90ID09IE5VTEwpCiAgICAg ewogICAgICAgc3RydWN0IGxpbmVfZW50cnkgKmwgPSBwb29sX2FsbG9jIChsaW5lX2VudHJ5 LCBzaXplb2YgKCpsKSk7CiAgICAgICBsLT5maWxlID0gbGUuZmlsZTsKLSAgICAgIGwtPmhh c2ggPSBoOworICAgICAgbC0+aGFzaCA9IGxlLmhhc2g7CiAgICAgICBsLT5uZXdfaWQgPSBt YXhfbGluZV9pZCsrOwogICAgICAgKnNsb3QgPSAodm9pZCAqKSBsOwogICAgICAgcmV0dXJu IGwtPm5ld19pZDsKQEAgLTEwMzQ3LDcgKzEwMzcxLDcgQEAgaGFuZGxlX21hY3JvICh2b2lk KQogCQkgIC8qIFRoaXMgc2hvdWxkIG9ubHkgaGFwcGVuIGlmIHRoZXJlIHdlcmUgbXVsdGlw bGUKIAkJICAgICBzYW1lIHRyYW5zcGFyZW50IHVuaXRzIHdpdGhpbiBhIHNpbmdsZSBvYmpl Y3QgZmlsZS4gICovCiAJCSAgJiYgaHRhYl9maW5kX3dpdGhfaGFzaCAoc3RycF9odGFiLCBw LAotCQkJCQkgIGl0ZXJhdGl2ZV9oYXNoIChwLCBsZW4sIDApKSA9PSBOVUxMKQorCQkJCQkg IGhhc2ggKHAsIGxlbikpID09IE5VTEwpCiAJCWNhbl9zaGFyZSA9IGZhbHNlOwogCSAgICAg IHMgPSBwdHI7CiAJICAgICAgYnJlYWs7CkBAIC0xNTc1Niw3ICsxNTc4MCw3IEBAIG9wdGlt aXplX211bHRpZmlsZSAodW5zaWduZWQgaW50ICpkaWVfY291bnQpCiAJICBoYXNodmFsX3Qg aGFzaDsKIAogCSAgcSA9ICh1bnNpZ25lZCBjaGFyICopIHN0cmNociAoKGNoYXIgKikgcCwg J1wwJyk7Ci0JICBoYXNoID0gaXRlcmF0aXZlX2hhc2ggKHAsIHEgLSBwLCAwKTsKKwkgIGhh c2ggPSBoYXNoIChwLCBxIC0gcCk7CiAJICBzZS5vZmYgPSBwIC0gZGVidWdfc2VjdGlvbnNb REVCVUdfU1RSXS5kYXRhOwogCSAgc2UubmV3X29mZiA9IGhhc2ggJiB+MVU7CiAJICBzbG90 ID0gaHRhYl9maW5kX3Nsb3Rfd2l0aF9oYXNoIChzdHJwX2h0YWIsICZzZSwgc2UubmV3X29m ZiwgSU5TRVJUKTsKQEAgLTE2MDc2LDggKzE2MTAwLDcgQEAgcmVhZF9tdWx0aWZpbGUgKGlu dCBmZCwgdW5zaWduZWQgaW50IGRpZV9jb3VudCkKIAkgICAgewogCSAgICAgIHEgPSAodW5z aWduZWQgY2hhciAqKSBzdHJjaHIgKChjaGFyICopIHAsICdcMCcpICsgMTsKIAkgICAgICBz bG90ID0gaHRhYl9maW5kX3Nsb3Rfd2l0aF9oYXNoIChzdHJwX2h0YWIsIHAsCi0JCQkJCSAg ICAgICBpdGVyYXRpdmVfaGFzaCAocCwgcSAtIHAgLSAxLAotCQkJCQkJCSAgICAgICAwKSwg SU5TRVJUKTsKKwkJCQkJICAgICAgIGhhc2ggKHAsIHEgLSBwIC0gMSksIElOU0VSVCk7CiAJ ICAgICAgaWYgKHNsb3QgPT0gTlVMTCkKIAkJZHd6X29vbSAoKTsKIAkgICAgICBhc3NlcnQg KCpzbG90ID09IE5VTEwpOwpAQCAtMTYwOTAsOCArMTYxMTMsNyBAQCByZWFkX211bHRpZmls ZSAoaW50IGZkLCB1bnNpZ25lZCBpbnQgZGllX2NvdW50KQogCQkgIHAgPSBkZWJ1Z19zZWN0 aW9uc1tERUJVR19TVFJdLmRhdGEgKyAqcGk7CiAJCSAgcSA9ICh1bnNpZ25lZCBjaGFyICop IHN0cmNociAoKGNoYXIgKikgcCwgJ1wwJyk7CiAJCSAgc2xvdCA9IGh0YWJfZmluZF9zbG90 X3dpdGhfaGFzaCAoc3RycF9odGFiLCBwLAotCQkJCQkJICAgaXRlcmF0aXZlX2hhc2ggKHAs IHEgLSBwLAotCQkJCQkJCQkgICAwKSwgSU5TRVJUKTsKKwkJCQkJCSAgIGhhc2ggKHAsIHEg LSBwKSwgSU5TRVJUKTsKIAkJICBpZiAoc2xvdCA9PSBOVUxMKQogCQkgICAgZHd6X29vbSAo KTsKIAkJICBhc3NlcnQgKCpzbG90ID09IE5VTEwpOwpkaWZmIC0tZ2l0IGEvaGFzaHRhYi5j IGIvaGFzaHRhYi5jCmluZGV4IDQxZWFiMzAuLmE5YjlkMTMgMTAwNjQ0Ci0tLSBhL2hhc2h0 YWIuYworKysgYi9oYXNodGFiLmMKQEAgLTYyNiwxNDIgKzYyNiwzIEBAIGh0YWJfcmVzdG9y ZSAoaHRhYiwgbmFtZSwgcmVzdG9yZWZuKQogICBmY2xvc2UgKGYpOwogfQogI2VuZGlmCi0K LS8qIERFUklWRUQgRlJPTToKLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCi1sb29rdXAyLmMsIGJ5IEJvYiBK ZW5raW5zLCBEZWNlbWJlciAxOTk2LCBQdWJsaWMgRG9tYWluLgotaGFzaCgpLCBoYXNoMigp LCBoYXNoMywgYW5kIG1peCgpIGFyZSBleHRlcm5hbGx5IHVzZWZ1bCBmdW5jdGlvbnMuCi1S b3V0aW5lcyB0byB0ZXN0IHRoZSBoYXNoIGFyZSBpbmNsdWRlZCBpZiBTRUxGX1RFU1QgaXMg ZGVmaW5lZC4KLVlvdSBjYW4gdXNlIHRoaXMgZnJlZSBmb3IgYW55IHB1cnBvc2UuICBJdCBo YXMgbm8gd2FycmFudHkuCi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQotKi8KLQotLyoKLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tCi1taXggLS0gbWl4IDMgMzItYml0IHZhbHVlcyByZXZlcnNpYmx5LgotRm9yIGV2ZXJ5 IGRlbHRhIHdpdGggb25lIG9yIHR3byBiaXQgc2V0LCBhbmQgdGhlIGRlbHRhcyBvZiBhbGwg dGhyZWUKLSAgaGlnaCBiaXRzIG9yIGFsbCB0aHJlZSBsb3cgYml0cywgd2hldGhlciB0aGUg b3JpZ2luYWwgdmFsdWUgb2YgYSxiLGMKLSAgaXMgYWxtb3N0IGFsbCB6ZXJvIG9yIGlzIHVu aWZvcm1seSBkaXN0cmlidXRlZCwKLSogSWYgbWl4KCkgaXMgcnVuIGZvcndhcmQgb3IgYmFj a3dhcmQsIGF0IGxlYXN0IDMyIGJpdHMgaW4gYSxiLGMKLSAgaGF2ZSBhdCBsZWFzdCAxLzQg cHJvYmFiaWxpdHkgb2YgY2hhbmdpbmcuCi0qIElmIG1peCgpIGlzIHJ1biBmb3J3YXJkLCBl dmVyeSBiaXQgb2YgYyB3aWxsIGNoYW5nZSBiZXR3ZWVuIDEvMyBhbmQKLSAgMi8zIG9mIHRo ZSB0aW1lLiAgKFdlbGwsIDIyLzEwMCBhbmQgNzgvMTAwIGZvciBzb21lIDItYml0IGRlbHRh cy4pCi1taXgoKSB3YXMgYnVpbHQgb3V0IG9mIDM2IHNpbmdsZS1jeWNsZSBsYXRlbmN5IGlu c3RydWN0aW9ucyBpbiBhIAotICBzdHJ1Y3R1cmUgdGhhdCBjb3VsZCBzdXBwb3J0ZWQgMngg cGFyYWxsZWxpc20sIGxpa2Ugc286Ci0gICAgICBhIC09IGI7IAotICAgICAgYSAtPSBjOyB4 ID0gKGM+PjEzKTsKLSAgICAgIGIgLT0gYzsgYSBePSB4OwotICAgICAgYiAtPSBhOyB4ID0g KGE8PDgpOwotICAgICAgYyAtPSBhOyBiIF49IHg7Ci0gICAgICBjIC09IGI7IHggPSAoYj4+ MTMpOwotICAgICAgLi4uCi0gIFVuZm9ydHVuYXRlbHksIHN1cGVyc2NhbGFyIFBlbnRpdW1z IGFuZCBTcGFyY3MgY2FuJ3QgdGFrZSBhZHZhbnRhZ2UgCi0gIG9mIHRoYXQgcGFyYWxsZWxp c20uICBUaGV5J3ZlIGFsc28gdHVybmVkIHNvbWUgb2YgdGhvc2Ugc2luZ2xlLWN5Y2xlCi0g IGxhdGVuY3kgaW5zdHJ1Y3Rpb25zIGludG8gbXVsdGktY3ljbGUgbGF0ZW5jeSBpbnN0cnVj dGlvbnMuICBTdGlsbCwKLSAgdGhpcyBpcyB0aGUgZmFzdGVzdCBnb29kIGhhc2ggSSBjb3Vs ZCBmaW5kLiAgVGhlcmUgd2VyZSBhYm91dCAyXl42OAotICB0byBjaG9vc2UgZnJvbS4gIEkg b25seSBsb29rZWQgYXQgYSBiaWxsaW9uIG9yIHNvLgotLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KLSovCi0v KiBzYW1lLCBidXQgc2xvd2VyLCB3b3JrcyBvbiBzeXN0ZW1zIHRoYXQgbWlnaHQgaGF2ZSA4 IGJ5dGUgaGFzaHZhbF90J3MgKi8KLSNkZWZpbmUgbWl4KGEsYixjKSBcCi17IFwKLSAgYSAt PSBiOyBhIC09IGM7IGEgXj0gKGM+PjEzKTsgXAotICBiIC09IGM7IGIgLT0gYTsgYiBePSAo YTw8IDgpOyBcCi0gIGMgLT0gYTsgYyAtPSBiOyBjIF49ICgoYiYweGZmZmZmZmZmKT4+MTMp OyBcCi0gIGEgLT0gYjsgYSAtPSBjOyBhIF49ICgoYyYweGZmZmZmZmZmKT4+MTIpOyBcCi0g IGIgLT0gYzsgYiAtPSBhOyBiID0gKGIgXiAoYTw8MTYpKSAmIDB4ZmZmZmZmZmY7IFwKLSAg YyAtPSBhOyBjIC09IGI7IGMgPSAoYyBeIChiPj4gNSkpICYgMHhmZmZmZmZmZjsgXAotICBh IC09IGI7IGEgLT0gYzsgYSA9IChhIF4gKGM+PiAzKSkgJiAweGZmZmZmZmZmOyBcCi0gIGIg LT0gYzsgYiAtPSBhOyBiID0gKGIgXiAoYTw8MTApKSAmIDB4ZmZmZmZmZmY7IFwKLSAgYyAt PSBhOyBjIC09IGI7IGMgPSAoYyBeIChiPj4xNSkpICYgMHhmZmZmZmZmZjsgXAotfQotCi0v KgotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0KLWhhc2goKSAtLSBoYXNoIGEgdmFyaWFibGUtbGVuZ3RoIGtl eSBpbnRvIGEgMzItYml0IHZhbHVlCi0gIGsgICAgIDogdGhlIGtleSAodGhlIHVuYWxpZ25l ZCB2YXJpYWJsZS1sZW5ndGggYXJyYXkgb2YgYnl0ZXMpCi0gIGxlbiAgIDogdGhlIGxlbmd0 aCBvZiB0aGUga2V5LCBjb3VudGluZyBieSBieXRlcwotICBsZXZlbCA6IGNhbiBiZSBhbnkg NC1ieXRlIHZhbHVlCi1SZXR1cm5zIGEgMzItYml0IHZhbHVlLiAgRXZlcnkgYml0IG9mIHRo ZSBrZXkgYWZmZWN0cyBldmVyeSBiaXQgb2YKLXRoZSByZXR1cm4gdmFsdWUuICBFdmVyeSAx LWJpdCBhbmQgMi1iaXQgZGVsdGEgYWNoaWV2ZXMgYXZhbGFuY2hlLgotQWJvdXQgMzYrNmxl biBpbnN0cnVjdGlvbnMuCi0KLVRoZSBiZXN0IGhhc2ggdGFibGUgc2l6ZXMgYXJlIHBvd2Vy cyBvZiAyLiAgVGhlcmUgaXMgbm8gbmVlZCB0byBkbwotbW9kIGEgcHJpbWUgKG1vZCBpcyBz b29vIHNsb3chKS4gIElmIHlvdSBuZWVkIGxlc3MgdGhhbiAzMiBiaXRzLAotdXNlIGEgYml0 bWFzay4gIEZvciBleGFtcGxlLCBpZiB5b3UgbmVlZCBvbmx5IDEwIGJpdHMsIGRvCi0gIGgg PSAoaCAmIGhhc2htYXNrKDEwKSk7Ci1JbiB3aGljaCBjYXNlLCB0aGUgaGFzaCB0YWJsZSBz aG91bGQgaGF2ZSBoYXNoc2l6ZSgxMCkgZWxlbWVudHMuCi0KLUlmIHlvdSBhcmUgaGFzaGlu ZyBuIHN0cmluZ3MgKHViMSAqKilrLCBkbyBpdCBsaWtlIHRoaXM6Ci0gIGZvciAoaT0wLCBo PTA7IGk8bjsgKytpKSBoID0gaGFzaCgga1tpXSwgbGVuW2ldLCBoKTsKLQotQnkgQm9iIEpl bmtpbnMsIDE5OTYuICBib2JfamVua2luc0BidXJ0bGVidXJ0bGUubmV0LiAgWW91IG1heSB1 c2UgdGhpcwotY29kZSBhbnkgd2F5IHlvdSB3aXNoLCBwcml2YXRlLCBlZHVjYXRpb25hbCwg b3IgY29tbWVyY2lhbC4gIEl0J3MgZnJlZS4KLQotU2VlIGh0dHA6Ly9idXJ0bGVidXJ0bGUu bmV0L2JvYi9oYXNoL2V2YWhhc2guaHRtbAotVXNlIGZvciBoYXNoIHRhYmxlIGxvb2t1cCwg b3IgYW55dGhpbmcgd2hlcmUgb25lIGNvbGxpc2lvbiBpbiAyXjMyIGlzCi1hY2NlcHRhYmxl LiAgRG8gTk9UIHVzZSBmb3IgY3J5cHRvZ3JhcGhpYyBwdXJwb3Nlcy4KLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tCi0qLwotCi1oYXNodmFsX3QKLWl0ZXJhdGl2ZV9oYXNoIChjb25zdCB2b2lkICprX2lu IC8qIHRoZSBrZXkgKi8sCi0gICAgICAgICAgICAgICAgcmVnaXN0ZXIgc2l6ZV90ICBsZW5n dGggLyogdGhlIGxlbmd0aCBvZiB0aGUga2V5ICovLAotICAgICAgICAgICAgICAgIHJlZ2lz dGVyIGhhc2h2YWxfdCBpbml0dmFsIC8qIHRoZSBwcmV2aW91cyBoYXNoLCBvcgotICAgICAg ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGFuIGFyYml0cmFyeSB2 YWx1ZSAqLykKLXsKLSAgcmVnaXN0ZXIgY29uc3QgdW5zaWduZWQgY2hhciAqayA9IChjb25z dCB1bnNpZ25lZCBjaGFyICopa19pbjsKLSAgcmVnaXN0ZXIgaGFzaHZhbF90IGEsYixjLGxl bjsKLQotICAvKiBTZXQgdXAgdGhlIGludGVybmFsIHN0YXRlICovCi0gIGxlbiA9IGxlbmd0 aDsKLSAgYSA9IGIgPSAweDllMzc3OWI5OyAgLyogdGhlIGdvbGRlbiByYXRpbzsgYW4gYXJi aXRyYXJ5IHZhbHVlICovCi0gIGMgPSBpbml0dmFsOyAgICAgICAgICAgLyogdGhlIHByZXZp b3VzIGhhc2ggdmFsdWUgKi8KLQotICAvKi0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0gaGFuZGxlIG1vc3Qgb2YgdGhlIGtleSAqLwotI2lmbmRlZiBXT1JEU19C SUdFTkRJQU4KLSAgLyogT24gYSBsaXR0bGUtZW5kaWFuIG1hY2hpbmUsIGlmIHRoZSBkYXRh IGlzIDQtYnl0ZSBhbGlnbmVkIHdlIGNhbiBoYXNoCi0gICAgIGJ5IHdvcmQgZm9yIGJldHRl ciBzcGVlZC4gIFRoaXMgZ2l2ZXMgbm9uZGV0ZXJtaW5pc3RpYyByZXN1bHRzIG9uCi0gICAg IGJpZy1lbmRpYW4gbWFjaGluZXMuICAqLwotICBpZiAoc2l6ZW9mIChoYXNodmFsX3QpID09 IDQgJiYgKCgoc2l6ZV90KWspJjMpID09IDApCi0gICAgd2hpbGUgKGxlbiA+PSAxMikgICAg LyogYWxpZ25lZCAqLwotICAgICAgewotCWEgKz0gKihoYXNodmFsX3QgKikoayswKTsKLQli ICs9ICooaGFzaHZhbF90ICopKGsrNCk7Ci0JYyArPSAqKGhhc2h2YWxfdCAqKShrKzgpOwot CW1peChhLGIsYyk7Ci0JayArPSAxMjsgbGVuIC09IDEyOwotICAgICAgfQotICBlbHNlIC8q IHVuYWxpZ25lZCAqLwotI2VuZGlmCi0gICAgd2hpbGUgKGxlbiA+PSAxMikKLSAgICAgIHsK LQlhICs9IChrWzBdICsoKGhhc2h2YWxfdClrWzFdPDw4KSArKChoYXNodmFsX3Qpa1syXTw8 MTYpICsoKGhhc2h2YWxfdClrWzNdPDwyNCkpOwotCWIgKz0gKGtbNF0gKygoaGFzaHZhbF90 KWtbNV08PDgpICsoKGhhc2h2YWxfdClrWzZdPDwxNikgKygoaGFzaHZhbF90KWtbN108PDI0 KSk7Ci0JYyArPSAoa1s4XSArKChoYXNodmFsX3Qpa1s5XTw8OCkgKygoaGFzaHZhbF90KWtb MTBdPDwxNikrKChoYXNodmFsX3Qpa1sxMV08PDI0KSk7Ci0JbWl4KGEsYixjKTsKLQlrICs9 IDEyOyBsZW4gLT0gMTI7Ci0gICAgICB9Ci0KLSAgLyotLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tIGhhbmRsZSB0aGUgbGFzdCAxMSBieXRlcyAqLwotICBjICs9IGxl bmd0aDsKLSAgc3dpdGNoKGxlbikgICAgICAgICAgICAgIC8qIGFsbCB0aGUgY2FzZSBzdGF0 ZW1lbnRzIGZhbGwgdGhyb3VnaCAqLwotICAgIHsKLSAgICBjYXNlIDExOiBjKz0oKGhhc2h2 YWxfdClrWzEwXTw8MjQpOwkvKiBmYWxsIHRocm91Z2ggKi8KLSAgICBjYXNlIDEwOiBjKz0o KGhhc2h2YWxfdClrWzldPDwxNik7CS8qIGZhbGwgdGhyb3VnaCAqLwotICAgIGNhc2UgOSA6 IGMrPSgoaGFzaHZhbF90KWtbOF08PDgpOwkvKiBmYWxsIHRocm91Z2ggKi8KLSAgICAgIC8q IHRoZSBmaXJzdCBieXRlIG9mIGMgaXMgcmVzZXJ2ZWQgZm9yIHRoZSBsZW5ndGggKi8KLSAg ICBjYXNlIDggOiBiKz0oKGhhc2h2YWxfdClrWzddPDwyNCk7CS8qIGZhbGwgdGhyb3VnaCAq LwotICAgIGNhc2UgNyA6IGIrPSgoaGFzaHZhbF90KWtbNl08PDE2KTsJLyogZmFsbCB0aHJv dWdoICovCi0gICAgY2FzZSA2IDogYis9KChoYXNodmFsX3Qpa1s1XTw8OCk7CS8qIGZhbGwg dGhyb3VnaCAqLwotICAgIGNhc2UgNSA6IGIrPWtbNF07CQkJLyogZmFsbCB0aHJvdWdoICov Ci0gICAgY2FzZSA0IDogYSs9KChoYXNodmFsX3Qpa1szXTw8MjQpOwkvKiBmYWxsIHRocm91 Z2ggKi8KLSAgICBjYXNlIDMgOiBhKz0oKGhhc2h2YWxfdClrWzJdPDwxNik7CS8qIGZhbGwg dGhyb3VnaCAqLwotICAgIGNhc2UgMiA6IGErPSgoaGFzaHZhbF90KWtbMV08PDgpOwkvKiBm YWxsIHRocm91Z2ggKi8KLSAgICBjYXNlIDEgOiBhKz1rWzBdOwotICAgICAgLyogY2FzZSAw OiBub3RoaW5nIGxlZnQgdG8gYWRkICovCi0gICAgfQotICBtaXgoYSxiLGMpOwotICAvKi0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tIHJlcG9ydCB0aGUg cmVzdWx0ICovCi0gIHJldHVybiBjOwotfQpkaWZmIC0tZ2l0IGEvaGFzaHRhYi5oIGIvaGFz aHRhYi5oCmluZGV4IGNiM2RhMDEuLjU5MjBhYmMgMTAwNjQ0Ci0tLSBhL2hhc2h0YWIuaAor KysgYi9oYXNodGFiLmgKQEAgLTE1MywxMSArMTUzLDYgQEAgZXh0ZXJuIHZvaWQJaHRhYl9y ZXN0b3JlIChodGFiX3QsIGNvbnN0IGNoYXIgKiwgaHRhYl9yZXN0b3JlZm4pOwogCiAjZW5k aWYKIAotLyogQW4gaXRlcmF0aXZlIGhhc2ggZnVuY3Rpb24gZm9yIGFyYml0cmFyeSBkYXRh LiAgKi8KLWV4dGVybiBoYXNodmFsX3QgaXRlcmF0aXZlX2hhc2ggKGNvbnN0IHZvaWQgKiwg c2l6ZV90LCBoYXNodmFsX3QpOwotLyogU2hvcnRoYW5kIGZvciBoYXNoaW5nIHNvbWV0aGlu ZyB3aXRoIGFuIGludHJpbnNpYyBzaXplLiAgKi8KLSNkZWZpbmUgaXRlcmF0aXZlX2hhc2hf b2JqZWN0KE9CLElOSVQpIGl0ZXJhdGl2ZV9oYXNoICgmT0IsIHNpemVvZiAoT0IpLCBJTklU KQotCiAjaWZkZWYgX19jcGx1c3BsdXMKIH0KICNlbmRpZiAvKiBfX2NwbHVzcGx1cyAqLwot LSAKMi4zNi4xCgo= --------------T7Weww9EVkn66fceU0Wxj8p0--