tech-toolchain archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Hashing support for make
Hi all,
the attached patch implements the :th modifier. It is intended to cut
down the output for MKREPRO=yes. This reduces the amount of IO for
verbose builds and also avoids copying data, so it should over all be at
least performance neutral.
The hash function is Murmurhash3, choosen because it is compact, fast and
relatively collision resistent.
Joerg
Index: make.1
===================================================================
RCS file: /home/joerg/repo/netbsd/src/usr.bin/make/make.1,v
retrieving revision 1.185
diff -u -p -r1.185 make.1
--- make.1 27 Mar 2011 19:47:46 -0000 1.185
+++ make.1 2 Apr 2011 01:26:29 -0000
@@ -29,7 +29,7 @@
.\"
.\" from: @(#)make.1 8.4 (Berkeley) 3/19/94
.\"
-.Dd March 27, 2011
+.Dd April 2, 2011
.Dt MAKE 1
.Os
.Sh NAME
@@ -1056,6 +1056,8 @@ If
.Ar c
is omitted, then no separator is used.
The common escapes (including octal numeric codes), work as expected.
+.It Cm \&:th
+Compute a 32bit hash of the value and encode it as hex digits.
.It Cm \&:tu
Converts variable to upper-case letters.
.It Cm \&:tW
Index: var.c
===================================================================
RCS file: /home/joerg/repo/netbsd/src/usr.bin/make/var.c,v
retrieving revision 1.162
diff -u -p -r1.162 var.c
--- var.c 6 Mar 2011 00:02:15 -0000 1.162
+++ var.c 2 Apr 2011 01:24:39 -0000
@@ -129,6 +129,7 @@ __RCSID("$NetBSD: var.c,v 1.162 2011/03/
#include <regex.h>
#endif
#include <ctype.h>
+#include <inttypes.h>
#include <stdlib.h>
#include <limits.h>
@@ -302,6 +303,7 @@ static char *VarGetPattern(GNode *, Var_
VarPattern *);
static char *VarQuote(char *);
static char *VarChangeCase(char *, int);
+static char *VarHash(char *);
static char *VarModify(GNode *, Var_Parse_State *,
const char *,
Boolean (*)(GNode *, Var_Parse_State *, char *, Boolean, Buffer *, void *),
@@ -2262,6 +2264,79 @@ VarQuote(char *str)
/*-
*-----------------------------------------------------------------------
+ * VarHash --
+ * Hash the string using the MurmurHash3 algorithm.
+ * Output is computed using 32bit Little Endian arithmetic.
+ *
+ * Input:
+ * str String to modify
+ *
+ * Results:
+ * Hash value of str, encoded as 8 hex digits.
+ *
+ * Side Effects:
+ * None.
+ *
+ *-----------------------------------------------------------------------
+ */
+static char *
+VarHash(char *str)
+{
+ static const char hexdigits[16] = "0123456789abcdef";
+ Buffer buf;
+ size_t len, len2;
+ unsigned char *ustr = (unsigned char *)str;
+ uint32_t h, k, c1, c2;
+ int done;
+
+ done = 1;
+ h = 0x971e137bU;
+ c1 = 0x95543787U;
+ c2 = 0x2ad7eb25U;
+ len2 = strlen(str);
+
+ for (len = len2; len; ) {
+ k = 0;
+ switch (len) {
+ default:
+ k = (ustr[3] << 24) | (ustr[2] << 16) | (ustr[1] << 8) | ustr[0];
+ len -= 4;
+ ustr += 4;
+ break;
+ case 3:
+ k |= (ustr[2] << 16);
+ case 2:
+ k |= (ustr[1] << 8);
+ case 1:
+ k |= ustr[0];
+ len = 0;
+ }
+ c1 = c1 * 5 + 0x7b7d159cU;
+ c2 = c2 * 5 + 0x6bce6396U;
+ k *= c1;
+ k = (k << 11) ^ (k >> 21);
+ k *= c2;
+ h = (h << 13) ^ (h >> 19);
+ h = h * 5 + 0x52dce729U;
+ h ^= k;
+ } while (!done);
+ h ^= len2;
+ h *= 0x85ebca6b;
+ h ^= h >> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >> 16;
+
+ Buf_Init(&buf, 0);
+ for (len = 0; len < 8; ++len) {
+ Buf_AddByte(&buf, hexdigits[h & 15]);
+ h >>= 4;
+ }
+
+ return Buf_Destroy(&buf, FALSE);
+}
+
+/*-
+ *-----------------------------------------------------------------------
* VarChangeCase --
* Change the string to all uppercase or all lowercase
*
@@ -2906,6 +2981,10 @@ ApplyModifiers(char *nstr, const char *t
newStr = VarChangeCase(nstr, (tstr[1] == 'u'));
cp = tstr + 2;
termc = *cp;
+ } else if (tstr[1] == 'h') {
+ newStr = VarHash(nstr);
+ cp = tstr + 2;
+ termc = *cp;
} else if (tstr[1] == 'W' || tstr[1] == 'w') {
parsestate.oneBigWord = (tstr[1] == 'W');
newStr = nstr;
Index: unit-tests/Makefile
===================================================================
RCS file: /home/joerg/repo/netbsd/src/usr.bin/make/unit-tests/Makefile,v
retrieving revision 1.31
diff -u -p -r1.31 Makefile
--- unit-tests/Makefile 6 Mar 2011 00:02:14 -0000 1.31
+++ unit-tests/Makefile 29 Mar 2011 14:34:55 -0000
@@ -27,6 +27,7 @@ SUBFILES= \
doterror \
dotwait \
forsubst \
+ hash \
misc \
moderrs \
modmatch \
Index: unit-tests/hash
===================================================================
RCS file: unit-tests/hash
diff -N unit-tests/hash
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ unit-tests/hash 29 Mar 2011 14:32:57 -0000
@@ -0,0 +1,18 @@
+STR1=
+STR2= a
+STR3= ab
+STR4= abc
+STR5= abcd
+STR6= abcde
+STR7= abcdef
+STR8= abcdefghijklmnopqrstuvwxyz
+
+all:
+ @echo ${STR1:th}
+ @echo ${STR2:th}
+ @echo ${STR3:th}
+ @echo ${STR4:th}
+ @echo ${STR5:th}
+ @echo ${STR6:th}
+ @echo ${STR7:th}
+ @echo ${STR8:th}
Index: unit-tests/test.exp
===================================================================
RCS file: /home/joerg/repo/netbsd/src/usr.bin/make/unit-tests/test.exp,v
retrieving revision 1.35
diff -u -p -r1.35 test.exp
--- unit-tests/test.exp 6 Mar 2011 00:02:14 -0000 1.35
+++ unit-tests/test.exp 29 Mar 2011 14:37:37 -0000
@@ -81,6 +81,14 @@ make: Graph cycles through `cycle.2.97'
cycle.1.99
cycle.1.99
.for with :S;... OK
+b2af338b
+3360ac65
+7747f046
+9ca87054
+880fe816
+208fcbd3
+d5d376eb
+de41416c
Expect: Unknown modifier 'Z'
make: Unknown modifier 'Z'
VAR:Z=
Home |
Main Index |
Thread Index |
Old Index