login
Header Space

 
 

Re: I'm a total push-over..

Score:
Previous message: [thread] [date] [author]
Next message: [thread] [date] [author]
To: Linus Torvalds <torvalds@...>
Cc: Marko Kreen <markokr@...>, Andreas Ericsson <ae@...>, Git Mailing List <git@...>, Junio C Hamano <gitster@...>
Date: Sunday, January 27, 2008 - 4:21 am

On Sat, Jan 26, 2008 at 10:51:18PM -0800, Linus Torvalds wrote:

Let's rename do_folding as something else, because it is not a real
folding, but a preparation step for hash calculation. Keeping these
steps separately simplifies the code, and allows further optimization,
for instance, you do not need this do_folding step on a case-sensitive
filesystem. Though it is certainly possible to mix both steps together,
it bloats the code and makes it less readable. Of course, the idea to
avoid a temporary buffer and do everything at once is very appealing,
so I gave it a try -- and here is a 32-bit version of name_hash(), but
I am not very happy with the result:


#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))

#define mix(a,b,c) \
{ \
	a -= c;  a ^= rot(c, 4);  c += b; \
	b -= a;  b ^= rot(a, 6);  a += c; \
	c -= b;  c ^= rot(b, 8);  b += a; \
	a -= c;  a ^= rot(c,16);  c += b; \
	b -= a;  b ^= rot(a,19);  a += c; \
	c -= b;  c ^= rot(b, 4);  b += a; \
}
#define final(a,b,c) \
{ \
	c ^= b; c -= rot(b,14); \
	a ^= c; a -= rot(c,11); \
	b ^= a; b -= rot(a,25); \
	c ^= b; c -= rot(b,16); \
	a ^= c; a -= rot(c,4);  \
	b ^= a; b -= rot(a,14); \
	c ^= b; c -= rot(b,24); \
}

#define hash_value(x) \
	hs[hp] += (x); \
	if (++hp == 3) { \
		mix (hs[0], hs[1], hs[2]); \
		hp = 0; \
	}
unsigned int name_hash(const char *name, unsigned size)
{
	unsigned hp = 0;
	unsigned hs[3];
	hs[0] = hs[1] = hs[2] = 0xdeadbeef + size;

	do {
		unsigned char c;
		if (size >= sizeof(unsigned)) {
			unsigned val = get_unaligned_uint(name);
			if (!(val & 0x80808080)) {
				val &= ~0x20202020;
				hash_value(val);
				name += sizeof(val);
				size -= sizeof(val);
				continue;
			}
		}

		while (!((c = *name) & 0x80)) {
			hash_value(c & ~0x20);
			name++;
			if (!--size)
				goto done:
		}

		do {
			// TODO: add denormalization for Mac
			unsigned val = towupper (utf8_to_wchar(&name, &size));
			hash_value(val);
		} while (size && (*name & 0x80));

	} while (size);
done:
	if (hp)
		final(a,b,c);
	return hs[2];
}


Dmitry
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Previous message: [thread] [date] [author]
Next message: [thread] [date] [author]

Messages in current thread:
I'm a total push-over.., Linus Torvalds, (Tue Jan 22, 7:37 pm)
Re: I'm a total push-over.., Andreas Ericsson, (Wed Jan 23, 4:32 am)
Re: I'm a total push-over.., Linus Torvalds, (Wed Jan 23, 12:06 pm)
Re: I'm a total push-over.., Dmitry Potapov, (Wed Jan 23, 5:15 am)
Re: I'm a total push-over.., Andreas Ericsson, (Wed Jan 23, 5:31 am)
Re: I'm a total push-over.., Dmitry Potapov, (Wed Jan 23, 1:10 pm)
Re: I'm a total push-over.., Andreas Ericsson, (Thu Jan 24, 6:39 am)
Re: I'm a total push-over.., Marko Kreen, (Wed Jan 23, 10:01 am)
Re: I'm a total push-over.., Andreas Ericsson, (Wed Jan 23, 10:39 am)
Re: I'm a total push-over.., Marko Kreen, (Thu Jan 24, 9:19 am)
Re: I'm a total push-over.., Andreas Ericsson, (Thu Jan 24, 12:00 pm)
Re: I'm a total push-over.., Marko Kreen, (Fri Jan 25, 4:08 pm)
Re: I'm a total push-over.., Dmitry Potapov, (Thu Jan 24, 12:28 pm)
Re: I'm a total push-over.., Linus Torvalds, (Thu Jan 24, 1:15 pm)
Re: I'm a total push-over.., Marko Kreen, (Fri Jan 25, 4:52 pm)
Re: I'm a total push-over.., Linus Torvalds, (Fri Jan 25, 6:16 pm)
Re: I'm a total push-over.., Marko Kreen, (Sat Jan 26, 8:37 am)
Re: I'm a total push-over.., Marko Kreen, (Sat Jan 26, 8:16 am)
Re: I'm a total push-over.., Linus Torvalds, (Sun Jan 27, 2:51 am)
Re: I'm a total push-over.., Marko Kreen, (Sun Jan 27, 5:45 am)
Re: I'm a total push-over.., Dmitry Potapov, (Sun Jan 27, 11:06 am)
Re: I'm a total push-over.., Dmitry Potapov, (Sun Jan 27, 4:21 am)
Re: I'm a total push-over.., Johannes Schindelin, (Sun Jan 27, 10:07 am)
Re: I'm a total push-over.., Dmitry Potapov, (Sun Jan 27, 10:48 am)
Re: I'm a total push-over.., Linus Torvalds, (Fri Jan 25, 6:35 pm)
Re: I'm a total push-over.., Dmitry Potapov, (Thu Jan 24, 2:45 pm)
Re: I'm a total push-over.., Linus Torvalds, (Thu Jan 24, 3:08 pm)
Re: I'm a total push-over.., Marko Kreen, (Thu Jan 24, 12:13 pm)
Re: I'm a total push-over.., Luke Lu, (Thu Jan 24, 2:51 am)
Re: I'm a total push-over.., Andreas Ericsson, (Thu Jan 24, 6:24 am)
Re: I'm a total push-over.., Junio C Hamano, (Tue Jan 22, 10:23 pm)
Re: I'm a total push-over.., Linus Torvalds, (Tue Jan 22, 10:58 pm)
Re: I'm a total push-over.., Junio C Hamano, (Wed Jan 23, 3:23 am)
Re: I'm a total push-over.., Johannes Schindelin, (Wed Jan 23, 8:25 am)
Re: I'm a total push-over.., Linus Torvalds, (Wed Jan 23, 12:25 pm)
Re: I'm a total push-over.., Johannes Schindelin, (Wed Jan 23, 12:34 pm)
Re: I'm a total push-over.., Linus Torvalds, (Wed Jan 23, 1:09 pm)
Re: I'm a total push-over.., Linus Torvalds, (Wed Jan 23, 1:29 pm)
Re: I'm a total push-over.., Jeremy Maitin-Shepard, (Fri Jan 25, 1:21 am)
Re: I'm a total push-over.., Johannes Schindelin, (Fri Jan 25, 8:51 am)
Re: I'm a total push-over.., Jeremy Maitin-Shepard, (Fri Jan 25, 2:19 pm)
Re: I'm a total push-over.., Junio C Hamano, (Fri Jan 25, 3:07 pm)
Re: I'm a total push-over.., Johannes Schindelin, (Fri Jan 25, 2:24 pm)
Re: I'm a total push-over.., Linus Torvalds, (Tue Jan 22, 11:19 pm)
Re: I'm a total push-over.., Junio C Hamano, (Fri Jan 25, 2:50 am)
Re: I'm a total push-over.., Linus Torvalds, (Fri Jan 25, 12:24 pm)
Re: I'm a total push-over.., Junio C Hamano, (Tue Jan 22, 10:36 pm)
Re: I'm a total push-over.., Johannes Schindelin, (Wed Jan 23, 8:24 am)
Re: I'm a total push-over.., David Kastrup, (Wed Jan 23, 8:28 am)
Re: I'm a total push-over.., Theodore Tso, (Wed Jan 23, 8:56 am)
Re: I'm a total push-over.., Kevin Ballard, (Tue Jan 22, 9:35 pm)
speck-geostationary