[core] document algorithm used in lighttpd etag

Donald E. Knuth
The Art Of Computer Programming Volume 3
Chapter 6.4, Topic: Sorting and Search

2 files changed, 18 insertions, 8 deletions

diff --git a/src/etag.c b/src/etag.c
index 69f08485..7f7b7726 100644
--- a/src/etag.c
+++ b/src/etag.c
@@ -172,16 +172,26 @@ int etag_create(buffer *etag, const struct stat *st, int flags) {
 	return 0;
 }
 
-int etag_mutate(buffer *mut, const buffer *etag) {
-	size_t i, len;
-	uint32_t h;
 
-	len = buffer_string_length(etag);
-	for (h=0, i=0; i < len; ++i) h = (h<<5)^(h>>27)^(etag->ptr[i]);
+/* Donald E. Knuth
+ * The Art Of Computer Programming Volume 3
+ * Chapter 6.4, Topic: Sorting and Search */
+__attribute_pure__
+static inline uint32_t
+dekhash (const char *str, const uint32_t len)
+{
+    const unsigned char * const s = (const unsigned char *)str;
+    uint32_t h = len;
+    for (uint32_t i = 0; i < len; ++i) h = (h << 5) ^ (h >> 27) ^ s[i];
+    return h;
+}
+
 
+void
+etag_mutate (buffer * const mut, const buffer * const etag) {
+	/* mut and etag may be the same, so calculate hash before modifying mut */
+	const uint32_t h = dekhash(CONST_BUF_LEN(etag));
 	buffer_copy_string_len(mut, CONST_STR_LEN("\""));
 	buffer_append_int(mut, h);
 	buffer_append_string_len(mut, CONST_STR_LEN("\""));
-
-	return 0;
 }
diff --git a/src/etag.h b/src/etag.h
index 82a7de90..ecceacb3 100644
--- a/src/etag.h
+++ b/src/etag.h
@@ -14,7 +14,7 @@ typedef enum { ETAG_USE_INODE = 1, ETAG_USE_MTIME = 2, ETAG_USE_SIZE = 4 } etag_
 
 int etag_is_equal(const buffer *etag, const char *matches, int weak_ok);
 int etag_create(buffer *etag, const struct stat *st, int flags);
-int etag_mutate(buffer *mut, const buffer *etag);
+void etag_mutate(buffer *mut, const buffer *etag);
 
 
 #endif