[src/trunk]: src/usr.bin/make Add the :hash modifier to compute a 32bit hash ...

[joerg <joerg%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/e930f0350432
branches:  trunk
changeset: 763916:e930f0350432
user:      joerg <joerg%NetBSD.org@localhost>
date:      Thu Apr 07 01:40:01 2011 +0000

description:
Add the :hash modifier to compute a 32bit hash of an variable.
This uses MurmurHash3 to get a reasonable collission-free hash with
small code. The result is endian neutral.

diffstat:

 usr.bin/make/make.1              |   6 +-
 usr.bin/make/unit-tests/Makefile |   3 +-
 usr.bin/make/unit-tests/hash     |  18 +++++++
 usr.bin/make/unit-tests/test.exp |   8 +++
 usr.bin/make/var.c               |  92 ++++++++++++++++++++++++++++++++++++++-
 5 files changed, 121 insertions(+), 6 deletions(-)

diffs (224 lines):

diff -r 3c88e899bb45 -r e930f0350432 usr.bin/make/make.1
--- a/usr.bin/make/make.1       Thu Apr 07 01:20:31 2011 +0000
+++ b/usr.bin/make/make.1       Thu Apr 07 01:40:01 2011 +0000
@@ -1,4 +1,4 @@
-.\"    $NetBSD: make.1,v 1.185 2011/03/27 19:47:46 sjg Exp $
+.\"    $NetBSD: make.1,v 1.186 2011/04/07 01:40:01 joerg Exp $
 .\"
 .\" Copyright (c) 1990, 1993
 .\"    The Regents of the University of California.  All rights reserved.
@@ -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
@@ -1042,6 +1042,8 @@
 .Nm .
 .It Cm \&:R
 Replaces each word in the variable with everything but its suffix.
+.It Cm \&:hash
+Compute a 32bit hash of the value and encode it as hex digits.
 .It Cm \&:tA
 Attempt to convert variable to an absolute path using
 .Xr realpath 3 ,
diff -r 3c88e899bb45 -r e930f0350432 usr.bin/make/unit-tests/Makefile
--- a/usr.bin/make/unit-tests/Makefile  Thu Apr 07 01:20:31 2011 +0000
+++ b/usr.bin/make/unit-tests/Makefile  Thu Apr 07 01:40:01 2011 +0000
@@ -1,4 +1,4 @@
-# $NetBSD: Makefile,v 1.31 2011/03/06 00:02:14 sjg Exp $
+# $NetBSD: Makefile,v 1.32 2011/04/07 01:40:02 joerg Exp $
 #
 # Unit tests for make(1)
 # The main targets are:
@@ -27,6 +27,7 @@
        doterror \
        dotwait \
        forsubst \
+       hash \
        misc \
        moderrs \
        modmatch \
diff -r 3c88e899bb45 -r e930f0350432 usr.bin/make/unit-tests/hash
--- /dev/null   Thu Jan 01 00:00:00 1970 +0000
+++ b/usr.bin/make/unit-tests/hash      Thu Apr 07 01:40:01 2011 +0000
@@ -0,0 +1,18 @@
+STR1=
+STR2=  a
+STR3=  ab
+STR4=  abc
+STR5=  abcd
+STR6=  abcde
+STR7=  abcdef
+STR8=  abcdefghijklmnopqrstuvwxyz
+
+all:
+       @echo ${STR1:hash}
+       @echo ${STR2:hash}
+       @echo ${STR3:hash}
+       @echo ${STR4:hash}
+       @echo ${STR5:hash}
+       @echo ${STR6:hash}
+       @echo ${STR7:hash}
+       @echo ${STR8:hash}
diff -r 3c88e899bb45 -r e930f0350432 usr.bin/make/unit-tests/test.exp
--- a/usr.bin/make/unit-tests/test.exp  Thu Apr 07 01:20:31 2011 +0000
+++ b/usr.bin/make/unit-tests/test.exp  Thu Apr 07 01:40:01 2011 +0000
@@ -81,6 +81,14 @@
 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=
diff -r 3c88e899bb45 -r e930f0350432 usr.bin/make/var.c
--- a/usr.bin/make/var.c        Thu Apr 07 01:20:31 2011 +0000
+++ b/usr.bin/make/var.c        Thu Apr 07 01:40:01 2011 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: var.c,v 1.162 2011/03/06 00:02:15 sjg Exp $    */
+/*     $NetBSD: var.c,v 1.163 2011/04/07 01:40:01 joerg Exp $  */
 
 /*
  * Copyright (c) 1988, 1989, 1990, 1993
@@ -69,14 +69,14 @@
  */
 
 #ifndef MAKE_NATIVE
-static char rcsid[] = "$NetBSD: var.c,v 1.162 2011/03/06 00:02:15 sjg Exp $";
+static char rcsid[] = "$NetBSD: var.c,v 1.163 2011/04/07 01:40:01 joerg Exp $";
 #else
 #include <sys/cdefs.h>
 #ifndef lint
 #if 0
 static char sccsid[] = "@(#)var.c      8.3 (Berkeley) 3/19/94";
 #else
-__RCSID("$NetBSD: var.c,v 1.162 2011/03/06 00:02:15 sjg Exp $");
+__RCSID("$NetBSD: var.c,v 1.163 2011/04/07 01:40:01 joerg Exp $");
 #endif
 #endif /* not lint */
 #endif
@@ -129,6 +129,7 @@
 #include    <regex.h>
 #endif
 #include    <ctype.h>
+#include    <inttypes.h>
 #include    <stdlib.h>
 #include    <limits.h>
 
@@ -302,6 +303,7 @@
                           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 @@
 
 /*-
  *-----------------------------------------------------------------------
+ * 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
  *
@@ -2821,6 +2896,17 @@
                }
 
            }
+       case 'h':
+           cp = tstr + 1;      /* make sure it is set */
+           if (strncmp(tstr, "hash", 4) == 0 &&
+               (tstr[4] == endc || tstr[4] == ':')) {
+               newStr = VarHash(nstr);
+               cp = tstr + 4;
+               termc = *cp;
+           } else {
+               goto bad_modifier;
+           }
+           break;
        case 't':
            {
                cp = tstr + 1;  /* make sure it is set */