[PATCH] use gcrypt instead of libssl for hash

[PATCH] use gcrypt instead of libssl for hash

[Junichi Uekawa]

[-- Attachment #1: Type: text/plain, Size: 4691 bytes --]


Hi,

This is the first  time for me to send you a patch; be gentle.
the following patch allows for use of gcrypt.

libssl seems to have a restrictive licensing wrt GPL applications.

This patch adds a requirement for libgcrypt11, and 
removes the requirement for libssl.

I hope I have not overlooked anything.


Signed-off-by: Junichi Uekawa <dancer@debian.org>


Makefile: 770595e02be4a9a55ff98910c53617c3b0f1e145
--- Makefile
+++ Makefile	2005-04-17 19:38:00.000000000 +0900
@@ -7,7 +7,7 @@
 # BREAK YOUR LOCAL DIFFS! show-diff and anything using it will likely randomly
 # break unless your underlying filesystem supports those sub-second times
 # (my ext3 doesn't).
-CFLAGS=-g -O3 -Wall
+CFLAGS=-g -O3 -Wall $(shell libgcrypt-config --cflags)
 
 CC=gcc
 
@@ -21,7 +21,7 @@
 install: $(PROG)
 	install $(PROG) $(HOME)/bin/
 
-LIBS= -lssl -lz
+LIBS= $(shell libgcrypt-config --libs) -lz
 
 init-db: init-db.o
 
cache.h: 5948db759b3f6fb5ade3b027f202330f71a8cb6a
--- cache.h
+++ cache.h	2005-04-17 19:25:40.000000000 +0900
@@ -12,7 +12,7 @@
 #include <sys/mman.h>
 #include <netinet/in.h>
 
-#include <openssl/sha.h>
+#include <gcrypt.h>
 #include <zlib.h>
 
 /*
read-cache.c: 740ffcce7026b268bd4dfe1d0a773ad7e3a24f96
--- read-cache.c
+++ read-cache.c	2005-04-17 19:34:37.000000000 +0900
@@ -116,11 +116,14 @@
 int check_sha1_signature(unsigned char *sha1, void *map, unsigned long size)
 {
 	unsigned char real_sha1[20];
-	SHA_CTX c;
+	gcry_md_hd_t c;
 
-	SHA1_Init(&c);
-	SHA1_Update(&c, map, size);
-	SHA1_Final(real_sha1, &c);
+	gcry_md_open(&c, GCRY_MD_SHA1, 0);
+	gcry_md_write(c, map, size);
+	gcry_md_final(c);
+	memcpy(real_sha1, gcry_md_read(c, 0), 20);
+	gcry_md_close(c);
+	
 	return memcmp(sha1, real_sha1, 20) ? -1 : 0;
 }
 
@@ -203,7 +206,7 @@
 	char *compressed;
 	z_stream stream;
 	unsigned char sha1[20];
-	SHA_CTX c;
+	gcry_md_hd_t c;
 
 	/* Set it up */
 	memset(&stream, 0, sizeof(stream));
@@ -222,9 +225,11 @@
 	size = stream.total_out;
 
 	/* Sha1.. */
-	SHA1_Init(&c);
-	SHA1_Update(&c, compressed, size);
-	SHA1_Final(sha1, &c);
+	gcry_md_open(&c, GCRY_MD_SHA1, 0);
+	gcry_md_write(c, compressed, size);
+	gcry_md_final(c);
+	memcpy(sha1, gcry_md_read(c, 0), 20);
+	gcry_md_close(c);
 
 	if (write_sha1_buffer(sha1, compressed, size) < 0)
 		return -1;
@@ -425,17 +430,20 @@
 
 static int verify_hdr(struct cache_header *hdr, unsigned long size)
 {
-	SHA_CTX c;
+	gcry_md_hd_t c;
 	unsigned char sha1[20];
 
 	if (hdr->hdr_signature != htonl(CACHE_SIGNATURE))
 		return error("bad signature");
 	if (hdr->hdr_version != htonl(1))
 		return error("bad version");
-	SHA1_Init(&c);
-	SHA1_Update(&c, hdr, offsetof(struct cache_header, sha1));
-	SHA1_Update(&c, hdr+1, size - sizeof(*hdr));
-	SHA1_Final(sha1, &c);
+	gcry_md_open(&c, GCRY_MD_SHA1, 0);
+	gcry_md_write(c, hdr, offsetof(struct cache_header, sha1));
+	gcry_md_write(c, hdr+1, size - sizeof(*hdr));
+	gcry_md_final(c);
+	memcpy(sha1, gcry_md_read(c, 0), 20);
+	gcry_md_close(c);
+
 	if (memcmp(sha1, hdr->sha1, 20))
 		return error("bad header sha1");
 	return 0;
@@ -498,7 +506,8 @@
 
 int write_cache(int newfd, struct cache_entry **cache, int entries)
 {
-	SHA_CTX c;
+	gcry_md_hd_t c;
+
 	struct cache_header hdr;
 	int i;
 
@@ -506,14 +515,16 @@
 	hdr.hdr_version = htonl(1);
 	hdr.hdr_entries = htonl(entries);
 
-	SHA1_Init(&c);
-	SHA1_Update(&c, &hdr, offsetof(struct cache_header, sha1));
+	gcry_md_open(&c, GCRY_MD_SHA1, 0);
+	gcry_md_write(c, &hdr, offsetof(struct cache_header, sha1));
 	for (i = 0; i < entries; i++) {
 		struct cache_entry *ce = cache[i];
 		int size = ce_size(ce);
-		SHA1_Update(&c, ce, size);
+		gcry_md_write(c, ce, size);
 	}
-	SHA1_Final(hdr.sha1, &c);
+	gcry_md_final(c);
+	memcpy(hdr.sha1, gcry_md_read(c, 0), 20);
+	gcry_md_close(c);
 
 	if (write(newfd, &hdr, sizeof(hdr)) != sizeof(hdr))
 		return -1;
update-cache.c: 5afecd1a4fd90d2505753ce2d5044d780fe69a7f
--- update-cache.c
+++ update-cache.c	2005-04-17 19:36:40.000000000 +0900
@@ -22,7 +22,7 @@
 	void *out = malloc(max_out_bytes);
 	void *metadata = malloc(namelen + 200);
 	void *in;
-	SHA_CTX c;
+	gcry_md_hd_t c;
 
 	in = "";
 	if (size)
@@ -54,9 +54,11 @@
 
 	deflateEnd(&stream);
 	
-	SHA1_Init(&c);
-	SHA1_Update(&c, out, stream.total_out);
-	SHA1_Final(ce->sha1, &c);
+	gcry_md_open(&c, GCRY_MD_SHA1, 0);
+	gcry_md_write(c, out, stream.total_out);
+	gcry_md_final(c);
+	memcpy(ce->sha1, gcry_md_read(c, 0), 20);
+	gcry_md_close(c);
 
 	return write_sha1_buffer(ce->sha1, out, stream.total_out);
 }
write-tree.c: 34a351b20fb38ea588f34bd9634f101b9dc533cb


regards,
	junichi


-- 
Junichi Uekawa, Debian Developer
17D6 120E 4455 1832 9423  7447 3059 BF92 CD37 56F4
http://www.netfort.gr.jp/~dancer/

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [PATCH] use gcrypt instead of libssl for hash

[Linus Torvalds]

On Sun, 17 Apr 2005, Junichi Uekawa wrote:
> 
> This is the first  time for me to send you a patch; be gentle.
> the following patch allows for use of gcrypt.

Well, libgcrypt seems to be pretty rare out there - I certainly don't have 
it installed on my machine.

> libssl seems to have a restrictive licensing wrt GPL applications.

It does? I really don't read it that way. 

The openssl license is BSD+mention, but it only kicks in if you 
_redistribute_ it (and you're not allowed to market things as being 
openssl based without giving them credit, but that's another thing).

So yes, the openssl license is incompatible with the GPL in the sense that 
you cannot actually _mix_ the openssl source-code with the GPL 
source-code. But that's true of a lot of libraries, the normal system C 
library being just one common example.

The GPL makes explicit mention of the system libraries (which openssl
definitely is by now), so it's ok by the GPL . And I don't see how you'd
claim that the openssl license doesn't allow it. So it all looks ok by me.

That said, if somebody wants to abstract this out, and have a simple "sign 
with sha1" interface that can be used with both openssl and libgcrypt (or 
any other crypt license), then hey, go wild. Or merge the SHA1 code from 
the kernel, even, and make the project entirely self-sufficient.

But requiring libgcrypt seems silly. Especially as the libgcrypt 
interfaces are horribly ugly, much more so than the openssl ones - so even 
if you use libgcrypt, you don't actually want to use it directly, you want 
to have much nicer wrappers around it.

		Linus

Re: [PATCH] use gcrypt instead of libssl for hash

[Junichi Uekawa]

Hi,

Thanks for your comments.

> > This is the first  time for me to send you a patch; be gentle.
> > the following patch allows for use of gcrypt.
> 
> Well, libgcrypt seems to be pretty rare out there - I certainly don't have 
> it installed on my machine.

Hmm... okay. Might be the case if you don't use much of GNOME and other
apps.

> > libssl seems to have a restrictive licensing wrt GPL applications.
> 
> The GPL makes explicit mention of the system libraries (which openssl
> definitely is by now), so it's ok by the GPL . And I don't see how you'd
> claim that the openssl license doesn't allow it. So it all looks ok by me.

>From a standpoint of Debian Developer; it feels not-so-clear;
since Debian will be distributing openssl and git.

openssl guys seem to recommend adding a quote, which might be sufficient.
"This program is released under the GPL with the additional exemption that compiling, linking, and/or using OpenSSL is allowed." 
	http://www.openssl.org/support/faq.html#LEGAL2


> But requiring libgcrypt seems silly. Especially as the libgcrypt 
> interfaces are horribly ugly, much more so than the openssl ones - so even 
> if you use libgcrypt, you don't actually want to use it directly, you want 
> to have much nicer wrappers around it.

I'll consider wrappers approach.


regards,
	junichi

-- 
Junichi Uekawa, Debian Developer
17D6 120E 4455 1832 9423  7447 3059 BF92 CD37 56F4
http://www.netfort.gr.jp/~dancer/

Re: [PATCH] use gcrypt instead of libssl for hash

[Edgar Toernig]

Linus Torvalds wrote:
>
> Well, libgcrypt seems to be pretty rare out there - I certainly don't have 
> it installed on my machine.

Well, I don't even have openssl ...

> Or merge the SHA1 code from the kernel, even, and make the project
> entirely self-sufficient.

... so I took the sha1 code from Firefox (it's MPL or GPL - you choose).

Here's the patch.

diff -ruN git-0.04-orig/Makefile git-0.04/Makefile
--- git-0.04-orig/Makefile	Mon Apr 11 05:48:10 2005
+++ git-0.04/Makefile	Mon Apr 18 05:41:49 2005
@@ -9,42 +9,57 @@
 install: $(PROG)
 	install $(PROG) $(HOME)/bin/
 
-LIBS= -lssl -lz
+LIBS= -lz
 
 init-db: init-db.o
 
-update-cache: update-cache.o read-cache.o
-	$(CC) $(CFLAGS) -o update-cache update-cache.o read-cache.o $(LIBS)
+update-cache: update-cache.o read-cache.o sha1.o
+	$(CC) $(CFLAGS) -o update-cache update-cache.o read-cache.o sha1.o $(LIBS)
 
-show-diff: show-diff.o read-cache.o
-	$(CC) $(CFLAGS) -o show-diff show-diff.o read-cache.o $(LIBS)
+show-diff: show-diff.o read-cache.o sha1.o
+	$(CC) $(CFLAGS) -o show-diff show-diff.o read-cache.o sha1.o $(LIBS)
 
-write-tree: write-tree.o read-cache.o
-	$(CC) $(CFLAGS) -o write-tree write-tree.o read-cache.o $(LIBS)
+write-tree: write-tree.o read-cache.o sha1.o
+	$(CC) $(CFLAGS) -o write-tree write-tree.o read-cache.o sha1.o $(LIBS)
 
-read-tree: read-tree.o read-cache.o
-	$(CC) $(CFLAGS) -o read-tree read-tree.o read-cache.o $(LIBS)
+read-tree: read-tree.o read-cache.o sha1.o
+	$(CC) $(CFLAGS) -o read-tree read-tree.o read-cache.o sha1.o $(LIBS)
 
-commit-tree: commit-tree.o read-cache.o
-	$(CC) $(CFLAGS) -o commit-tree commit-tree.o read-cache.o $(LIBS)
+commit-tree: commit-tree.o read-cache.o sha1.o
+	$(CC) $(CFLAGS) -o commit-tree commit-tree.o read-cache.o sha1.o $(LIBS)
 
-cat-file: cat-file.o read-cache.o
-	$(CC) $(CFLAGS) -o cat-file cat-file.o read-cache.o $(LIBS)
+cat-file: cat-file.o read-cache.o sha1.o
+	$(CC) $(CFLAGS) -o cat-file cat-file.o read-cache.o sha1.o $(LIBS)
 
-fsck-cache: fsck-cache.o read-cache.o
-	$(CC) $(CFLAGS) -o fsck-cache fsck-cache.o read-cache.o $(LIBS)
+fsck-cache: fsck-cache.o read-cache.o sha1.o
+	$(CC) $(CFLAGS) -o fsck-cache fsck-cache.o read-cache.o sha1.o $(LIBS)
 
-checkout-cache: checkout-cache.o read-cache.o
-	$(CC) $(CFLAGS) -o checkout-cache checkout-cache.o read-cache.o $(LIBS)
+checkout-cache: checkout-cache.o read-cache.o sha1.o
+	$(CC) $(CFLAGS) -o checkout-cache checkout-cache.o read-cache.o sha1.o $(LIBS)
 
-diff-tree: diff-tree.o read-cache.o
-	$(CC) $(CFLAGS) -o diff-tree diff-tree.o read-cache.o $(LIBS)
-
-read-cache.o: cache.h
-show-diff.o: cache.h
+diff-tree: diff-tree.o read-cache.o sha1.o
+	$(CC) $(CFLAGS) -o diff-tree diff-tree.o read-cache.o sha1.o $(LIBS)
 
 clean:
 	rm -f *.o $(PROG) temp_git_file_*
 
 backup: clean
 	cd .. ; tar czvf dircache.tar.gz dir-cache
+
+depend:
+	makedepend -Y -- -- *.c 2>/dev/null
+
+# DO NOT DELETE
+
+cat-file.o: cache.h sha1.h
+checkout-cache.o: cache.h sha1.h
+commit-tree.o: cache.h sha1.h
+diff-tree.o: cache.h sha1.h
+fsck-cache.o: cache.h sha1.h
+init-db.o: cache.h sha1.h
+read-cache.o: cache.h sha1.h
+read-tree.o: cache.h sha1.h
+sha1.o: sha1.h
+show-diff.o: cache.h sha1.h
+update-cache.o: cache.h sha1.h
+write-tree.o: cache.h sha1.h
diff -ruN git-0.04-orig/cache.h git-0.04/cache.h
--- git-0.04-orig/cache.h	Sun Apr 10 20:19:02 2005
+++ git-0.04/cache.h	Mon Apr 18 05:46:47 2005
@@ -11,7 +11,7 @@
 #include <errno.h>
 #include <sys/mman.h>
 
-#include <openssl/sha.h>
+#include "sha1.h"
 #include <zlib.h>
 
 /*
diff -ruN git-0.04-orig/sha1.c git-0.04/sha1.c
--- git-0.04-orig/sha1.c	Thu Jan  1 01:00:00 1970
+++ git-0.04/sha1.c	Mon Apr 18 05:40:25 2005
@@ -0,0 +1,152 @@
+/* 
+ * The contents of this file are subject to the Mozilla Public
+ * License Version 1.1 (the "License"); you may not use this file
+ * except in compliance with the License. You may obtain a copy of
+ * the License at http://www.mozilla.org/MPL/
+ * 
+ * Software distributed under the License is distributed on an "AS
+ * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
+ * implied. See the License for the specific language governing
+ * rights and limitations under the License.
+ * 
+ * The Original Code is SHA 180-1 Reference Implementation (Compact version)
+ * 
+ * The Initial Developer of the Original Code is Paul Kocher of
+ * Cryptography Research.  Portions created by Paul Kocher are 
+ * Copyright (C) 1995-9 by Cryptography Research, Inc.  All
+ * Rights Reserved.
+ * 
+ * Contributor(s):
+ *
+ *     Paul Kocher
+ * 
+ * Alternatively, the contents of this file may be used under the
+ * terms of the GNU General Public License Version 2 or later (the
+ * "GPL"), in which case the provisions of the GPL are applicable 
+ * instead of those above.  If you wish to allow use of your 
+ * version of this file only under the terms of the GPL and not to
+ * allow others to use your version of this file under the MPL,
+ * indicate your decision by deleting the provisions above and
+ * replace them with the notice and other provisions required by
+ * the GPL.  If you do not delete the provisions above, a recipient
+ * may use your version of this file under either the MPL or the
+ * GPL.
+ */
+
+#include "sha1.h"
+
+static void shaHashBlock(SHA_CTX *ctx);
+
+void SHA1_Init(SHA_CTX *ctx) {
+  int i;
+
+  ctx->lenW = 0;
+  ctx->sizeHi = ctx->sizeLo = 0;
+
+  /* Initialize H with the magic constants (see FIPS180 for constants)
+   */
+  ctx->H[0] = 0x67452301;
+  ctx->H[1] = 0xefcdab89;
+  ctx->H[2] = 0x98badcfe;
+  ctx->H[3] = 0x10325476;
+  ctx->H[4] = 0xc3d2e1f0;
+
+  for (i = 0; i < 80; i++)
+    ctx->W[i] = 0;
+}
+
+
+void SHA1_Update(SHA_CTX *ctx, void *_dataIn, int len) {
+  unsigned char *dataIn = _dataIn;
+  int i;
+
+  /* Read the data into W and process blocks as they get full
+   */
+  for (i = 0; i < len; i++) {
+    ctx->W[ctx->lenW / 4] <<= 8;
+    ctx->W[ctx->lenW / 4] |= (unsigned int)dataIn[i];
+    if ((++ctx->lenW) % 64 == 0) {
+      shaHashBlock(ctx);
+      ctx->lenW = 0;
+    }
+    ctx->sizeLo += 8;
+    ctx->sizeHi += (ctx->sizeLo < 8);
+  }
+}
+
+
+void SHA1_Final(unsigned char hashout[20], SHA_CTX *ctx) {
+  unsigned char pad0x80 = 0x80;
+  unsigned char pad0x00 = 0x00;
+  unsigned char padlen[8];
+  int i;
+
+  /* Pad with a binary 1 (e.g. 0x80), then zeroes, then length
+   */
+  padlen[0] = (unsigned char)((ctx->sizeHi >> 24) & 255);
+  padlen[1] = (unsigned char)((ctx->sizeHi >> 16) & 255);
+  padlen[2] = (unsigned char)((ctx->sizeHi >> 8) & 255);
+  padlen[3] = (unsigned char)((ctx->sizeHi >> 0) & 255);
+  padlen[4] = (unsigned char)((ctx->sizeLo >> 24) & 255);
+  padlen[5] = (unsigned char)((ctx->sizeLo >> 16) & 255);
+  padlen[6] = (unsigned char)((ctx->sizeLo >> 8) & 255);
+  padlen[7] = (unsigned char)((ctx->sizeLo >> 0) & 255);
+  SHA1_Update(ctx, &pad0x80, 1);
+  while (ctx->lenW != 56)
+    SHA1_Update(ctx, &pad0x00, 1);
+  SHA1_Update(ctx, padlen, 8);
+
+  /* Output hash
+   */
+  for (i = 0; i < 20; i++) {
+    hashout[i] = (unsigned char)(ctx->H[i / 4] >> 24);
+    ctx->H[i / 4] <<= 8;
+  }
+
+  /*
+   *  Re-initialize the context (also zeroizes contents)
+   */
+  SHA1_Init(ctx);
+}
+
+
+#define SHA_ROT(X,n) (((X) << (n)) | ((X) >> (32-(n))))
+
+static void shaHashBlock(SHA_CTX *ctx) {
+  int t;
+  unsigned int A,B,C,D,E,TEMP;
+
+  for (t = 16; t <= 79; t++)
+    ctx->W[t] =
+      SHA_ROT(ctx->W[t-3] ^ ctx->W[t-8] ^ ctx->W[t-14] ^ ctx->W[t-16], 1);
+
+  A = ctx->H[0];
+  B = ctx->H[1];
+  C = ctx->H[2];
+  D = ctx->H[3];
+  E = ctx->H[4];
+
+  for (t = 0; t <= 19; t++) {
+    TEMP = SHA_ROT(A,5) + (((C^D)&B)^D)     + E + ctx->W[t] + 0x5a827999;
+    E = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;
+  }
+  for (t = 20; t <= 39; t++) {
+    TEMP = SHA_ROT(A,5) + (B^C^D)           + E + ctx->W[t] + 0x6ed9eba1;
+    E = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;
+  }
+  for (t = 40; t <= 59; t++) {
+    TEMP = SHA_ROT(A,5) + ((B&C)|(D&(B|C))) + E + ctx->W[t] + 0x8f1bbcdc;
+    E = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;
+  }
+  for (t = 60; t <= 79; t++) {
+    TEMP = SHA_ROT(A,5) + (B^C^D)           + E + ctx->W[t] + 0xca62c1d6;
+    E = D; D = C; C = SHA_ROT(B, 30); B = A; A = TEMP;
+  }
+
+  ctx->H[0] += A;
+  ctx->H[1] += B;
+  ctx->H[2] += C;
+  ctx->H[3] += D;
+  ctx->H[4] += E;
+}
+
diff -ruN git-0.04-orig/sha1.h git-0.04/sha1.h
--- git-0.04-orig/sha1.h	Thu Jan  1 01:00:00 1970
+++ git-0.04/sha1.h	Mon Apr 18 05:40:25 2005
@@ -0,0 +1,45 @@
+/* 
+ * The contents of this file are subject to the Mozilla Public
+ * License Version 1.1 (the "License"); you may not use this file
+ * except in compliance with the License. You may obtain a copy of
+ * the License at http://www.mozilla.org/MPL/
+ * 
+ * Software distributed under the License is distributed on an "AS
+ * IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or
+ * implied. See the License for the specific language governing
+ * rights and limitations under the License.
+ * 
+ * The Original Code is SHA 180-1 Header File
+ * 
+ * The Initial Developer of the Original Code is Paul Kocher of
+ * Cryptography Research.  Portions created by Paul Kocher are 
+ * Copyright (C) 1995-9 by Cryptography Research, Inc.  All
+ * Rights Reserved.
+ * 
+ * Contributor(s):
+ *
+ *     Paul Kocher
+ * 
+ * Alternatively, the contents of this file may be used under the
+ * terms of the GNU General Public License Version 2 or later (the
+ * "GPL"), in which case the provisions of the GPL are applicable 
+ * instead of those above.  If you wish to allow use of your 
+ * version of this file only under the terms of the GPL and not to
+ * allow others to use your version of this file under the MPL,
+ * indicate your decision by deleting the provisions above and
+ * replace them with the notice and other provisions required by
+ * the GPL.  If you do not delete the provisions above, a recipient
+ * may use your version of this file under either the MPL or the
+ * GPL.
+ */
+
+typedef struct {
+  unsigned int H[5];
+  unsigned int W[80];
+  int lenW;
+  unsigned int sizeHi,sizeLo;
+} SHA_CTX;
+
+void SHA1_Init(SHA_CTX *ctx);
+void SHA1_Update(SHA_CTX *ctx, void *dataIn, int len);
+void SHA1_Final(unsigned char hashout[20], SHA_CTX *ctx);


Ciao, ET.

Mozilla SHA1 implementation

[Linus Torvalds]

I've just integrated the Mozilla SHA1 library implementation that Adgar
Toernig sent me into the standard git archive (but I did the integration
differently).

The Mozilla SHA1 code is copyright Paul Kocher and Cryptography Research,
and is released under a dual MPL/GPL license. Git obviously uses it in the
GPL version, but I left the MPL choice there too, so that those two files
(that are in a subdirectory of its own) will continue to be dual-licensed.

NOTE! I left git using the openssl libraries by default, and this is a
built-time choice in the makefile. You can choose the Mozilla SHA1
implementation by doing

	make clean
	MOZILLA_SHA1=1 make
	make install

but I suspect that anybody that has openssl installed and is working on an
x86 is much better off with the i586-optimized openssl version. But if you
don't have openssl by default, or if you don't like openssl for some other
reason, you now have a nice easy choice.

Interestingly, the Mozilla SHA1 code is about twice as fast as the openssl
code on my G5, and judging by the disassembly, it's because it's much
simpler. I think the openssl people have unrolled all the loops totally,
which tends to be a disaster on any half-way modern CPU. But hey, it could
be something as simple as optimization flags too.

			Linus

Re: Mozilla SHA1 implementation

[Edgar Toernig]

Linus Torvalds wrote:
>
> I've just integrated the Mozilla SHA1 library implementation into the
> standard git archive

Thanks.

In the mood for another compatibility hack?  My zlib doesn't have
deflateBound and browsing through the git-ml archive it seems I'm
not the only one.  How about putting this snippet into some header
file?

#if ZLIB_VERNUM < 0x1200
#define deflateBound(c,s) ((s) + (((s) + 7) >> 3) + (((s) + 63) >> 6) + 11)
#endif

The formula is the conservative upper bound from zlib-1.2.2.

Ciao, ET.

Re: Mozilla SHA1 implementation

[Paul Mackerras]

Linus Torvalds writes:

> I've just integrated the Mozilla SHA1 library implementation that Adgar
> Toernig sent me into the standard git archive (but I did the integration
> differently).

Here is a new PPC SHA1 patch that integrates better with this...

> Interestingly, the Mozilla SHA1 code is about twice as fast as the openssl
> code on my G5, and judging by the disassembly, it's because it's much
> simpler. I think the openssl people have unrolled all the loops totally,
> which tends to be a disaster on any half-way modern CPU. But hey, it could
> be something as simple as optimization flags too.

Very interesting.  On my G4 powerbook (since I am at LCA), for a
fsck-cache on a linux-2.6 tree, it takes 6.6 seconds with the openssl
SHA1, 10.7 seconds with the Mozilla SHA1, and ~5.8 seconds with my
SHA1.  I'll test it on a G5 tonight, hopefully.

Paul.

diff -urN git.orig/Makefile git/Makefile
--- git.orig/Makefile	2005-04-22 16:23:44.000000000 +1000
+++ git/Makefile	2005-04-22 16:43:31.000000000 +1000
@@ -34,9 +34,14 @@
   SHA1_HEADER="mozilla-sha1/sha1.h"
   LIB_OBJS += mozilla-sha1/sha1.o
 else
+ifdef PPC_SHA1
+  SHA1_HEADER="ppc/sha1.h"
+  LIB_OBJS += ppc/sha1.o ppc/sha1ppc.o
+else
   SHA1_HEADER=<openssl/sha.h>
   LIBS += -lssl
 endif
+endif
 
 CFLAGS += '-DSHA1_HEADER=$(SHA1_HEADER)'
 
@@ -77,7 +82,7 @@
 write-tree.o: $(LIB_H)
 
 clean:
-	rm -f *.o mozilla-sha1/*.o $(PROG) $(LIB_FILE)
+	rm -f *.o mozilla-sha1/*.o ppc/*.o $(PROG) $(LIB_FILE)
 
 backup: clean
 	cd .. ; tar czvf dircache.tar.gz dir-cache
diff -urN git.orig/ppc/sha1.c git/ppc/sha1.c
--- /dev/null	2005-04-04 12:56:19.000000000 +1000
+++ git/ppc/sha1.c	2005-04-22 16:29:19.000000000 +1000
@@ -0,0 +1,72 @@
+/*
+ * SHA-1 implementation.
+ *
+ * Copyright (C) 2005 Paul Mackerras <paulus@samba.org>
+ *
+ * This version assumes we are running on a big-endian machine.
+ * It calls an external sha1_core() to process blocks of 64 bytes.
+ */
+#include <stdio.h>
+#include <string.h>
+#include "sha1.h"
+
+extern void sha1_core(uint32_t *hash, const unsigned char *p,
+		      unsigned int nblocks);
+
+int SHA1_Init(SHA_CTX *c)
+{
+	c->hash[0] = 0x67452301;
+	c->hash[1] = 0xEFCDAB89;
+	c->hash[2] = 0x98BADCFE;
+	c->hash[3] = 0x10325476;
+	c->hash[4] = 0xC3D2E1F0;
+	c->len = 0;
+	c->cnt = 0;
+	return 0;
+}
+
+int SHA1_Update(SHA_CTX *c, const void *ptr, unsigned long n)
+{
+	unsigned long nb;
+	const unsigned char *p = ptr;
+
+	c->len += n << 3;
+	while (n != 0) {
+		if (c->cnt || n < 64) {
+			nb = 64 - c->cnt;
+			if (nb > n)
+				nb = n;
+			memcpy(&c->buf.b[c->cnt], p, nb);
+			if ((c->cnt += nb) == 64) {
+				sha1_core(c->hash, c->buf.b, 1);
+				c->cnt = 0;
+			}
+		} else {
+			nb = n >> 6;
+			sha1_core(c->hash, p, nb);
+			nb <<= 6;
+		}
+		n -= nb;
+		p += nb;
+	}
+	return 0;
+}	
+
+int SHA1_Final(unsigned char *hash, SHA_CTX *c)
+{
+	unsigned int cnt = c->cnt;
+
+	c->buf.b[cnt++] = 0x80;
+	if (cnt > 56) {
+		if (cnt < 64)
+			memset(&c->buf.b[cnt], 0, 64 - cnt);
+		sha1_core(c->hash, c->buf.b, 1);
+		cnt = 0;
+	}
+	if (cnt < 56)
+		memset(&c->buf.b[cnt], 0, 56 - cnt);
+	c->buf.l[7] = c->len;
+	sha1_core(c->hash, c->buf.b, 1);
+	memcpy(hash, c->hash, 20);
+	return 0;
+}
diff -urN git.orig/ppc/sha1.h git/ppc/sha1.h
--- /dev/null	2005-04-04 12:56:19.000000000 +1000
+++ git/ppc/sha1.h	2005-04-22 16:45:28.000000000 +1000
@@ -0,0 +1,20 @@
+/*
+ * SHA-1 implementation.
+ *
+ * Copyright (C) 2005 Paul Mackerras <paulus@samba.org>
+ */
+#include <stdint.h>
+
+typedef struct sha_context {
+	uint32_t hash[5];
+	uint32_t cnt;
+	uint64_t len;
+	union {
+		unsigned char b[64];
+		uint64_t l[8];
+	} buf;
+} SHA_CTX;
+
+int SHA1_Init(SHA_CTX *c);
+int SHA1_Update(SHA_CTX *c, const void *p, unsigned long n);
+int SHA1_Final(unsigned char *hash, SHA_CTX *c);
diff -urN git.orig/ppc/sha1ppc.S git/ppc/sha1ppc.S
--- /dev/null	2005-04-04 12:56:19.000000000 +1000
+++ git/ppc/sha1ppc.S	2005-04-22 16:29:19.000000000 +1000
@@ -0,0 +1,185 @@
+/*
+ * SHA-1 implementation for PowerPC.
+ *
+ * Copyright (C) 2005 Paul Mackerras.
+ */
+#define FS	80
+
+/*
+ * We roll the registers for T, A, B, C, D, E around on each
+ * iteration; T on iteration t is A on iteration t+1, and so on.
+ * We use registers 7 - 12 for this.
+ */
+#define RT(t)	((((t)+5)%6)+7)
+#define RA(t)	((((t)+4)%6)+7)
+#define RB(t)	((((t)+3)%6)+7)
+#define RC(t)	((((t)+2)%6)+7)
+#define RD(t)	((((t)+1)%6)+7)
+#define RE(t)	((((t)+0)%6)+7)
+
+/* We use registers 16 - 31 for the W values */
+#define W(t)	(((t)%16)+16)
+
+#define STEPD0(t)				\
+	and	%r6,RB(t),RC(t);		\
+	andc	%r0,RD(t),RB(t);		\
+	rotlwi	RT(t),RA(t),5;			\
+	rotlwi	RB(t),RB(t),30;			\
+	or	%r6,%r6,%r0;			\
+	add	%r0,RE(t),%r15;			\
+	add	RT(t),RT(t),%r6;		\
+	add	%r0,%r0,W(t);			\
+	add	RT(t),RT(t),%r0
+
+#define STEPD1(t)				\
+	xor	%r6,RB(t),RC(t);		\
+	rotlwi	RT(t),RA(t),5;			\
+	rotlwi	RB(t),RB(t),30;			\
+	xor	%r6,%r6,RD(t);			\
+	add	%r0,RE(t),%r15;			\
+	add	RT(t),RT(t),%r6;		\
+	add	%r0,%r0,W(t);			\
+	add	RT(t),RT(t),%r0
+
+#define STEPD2(t)				\
+	and	%r6,RB(t),RC(t);		\
+	and	%r0,RB(t),RD(t);		\
+	rotlwi	RT(t),RA(t),5;			\
+	rotlwi	RB(t),RB(t),30;			\
+	or	%r6,%r6,%r0;			\
+	and	%r0,RC(t),RD(t);		\
+	or	%r6,%r6,%r0;			\
+	add	%r0,RE(t),%r15;			\
+	add	RT(t),RT(t),%r6;		\
+	add	%r0,%r0,W(t);			\
+	add	RT(t),RT(t),%r0
+
+#define LOADW(t)				\
+	lwz	W(t),(t)*4(%r4)
+
+#define UPDATEW(t)				\
+	xor	%r0,W((t)-3),W((t)-8);		\
+	xor	W(t),W((t)-16),W((t)-14);	\
+	xor	W(t),W(t),%r0;			\
+	rotlwi	W(t),W(t),1
+
+#define STEP0LD4(t)				\
+	STEPD0(t);   LOADW((t)+4);		\
+	STEPD0((t)+1); LOADW((t)+5);		\
+	STEPD0((t)+2); LOADW((t)+6);		\
+	STEPD0((t)+3); LOADW((t)+7)
+
+#define STEPUP4(t, fn)				\
+	STEP##fn(t);   UPDATEW((t)+4);		\
+	STEP##fn((t)+1); UPDATEW((t)+5);	\
+	STEP##fn((t)+2); UPDATEW((t)+6);	\
+	STEP##fn((t)+3); UPDATEW((t)+7)
+
+#define STEPUP20(t, fn)				\
+	STEPUP4(t, fn);				\
+	STEPUP4((t)+4, fn);			\
+	STEPUP4((t)+8, fn);			\
+	STEPUP4((t)+12, fn);			\
+	STEPUP4((t)+16, fn)
+
+	.globl	sha1_core
+sha1_core:
+	stwu	%r1,-FS(%r1)
+	stw	%r15,FS-68(%r1)
+	stw	%r16,FS-64(%r1)
+	stw	%r17,FS-60(%r1)
+	stw	%r18,FS-56(%r1)
+	stw	%r19,FS-52(%r1)
+	stw	%r20,FS-48(%r1)
+	stw	%r21,FS-44(%r1)
+	stw	%r22,FS-40(%r1)
+	stw	%r23,FS-36(%r1)
+	stw	%r24,FS-32(%r1)
+	stw	%r25,FS-28(%r1)
+	stw	%r26,FS-24(%r1)
+	stw	%r27,FS-20(%r1)
+	stw	%r28,FS-16(%r1)
+	stw	%r29,FS-12(%r1)
+	stw	%r30,FS-8(%r1)
+	stw	%r31,FS-4(%r1)
+
+	/* Load up A - E */
+	lwz	RA(0),0(%r3)	/* A */
+	lwz	RB(0),4(%r3)	/* B */
+	lwz	RC(0),8(%r3)	/* C */
+	lwz	RD(0),12(%r3)	/* D */
+	lwz	RE(0),16(%r3)	/* E */
+
+	mtctr	%r5
+
+1:	LOADW(0)
+	LOADW(1)
+	LOADW(2)
+	LOADW(3)
+
+	lis	%r15,0x5a82	/* K0-19 */
+	ori	%r15,%r15,0x7999
+	STEP0LD4(0)
+	STEP0LD4(4)
+	STEP0LD4(8)
+	STEPUP4(12, D0)
+	STEPUP4(16, D0)
+
+	lis	%r15,0x6ed9	/* K20-39 */
+	ori	%r15,%r15,0xeba1
+	STEPUP20(20, D1)
+
+	lis	%r15,0x8f1b	/* K40-59 */
+	ori	%r15,%r15,0xbcdc
+	STEPUP20(40, D2)
+
+	lis	%r15,0xca62	/* K60-79 */
+	ori	%r15,%r15,0xc1d6
+	STEPUP4(60, D1)
+	STEPUP4(64, D1)
+	STEPUP4(68, D1)
+	STEPUP4(72, D1)
+	STEPD1(76)
+	STEPD1(77)
+	STEPD1(78)
+	STEPD1(79)
+
+	lwz	%r20,16(%r3)
+	lwz	%r19,12(%r3)
+	lwz	%r18,8(%r3)
+	lwz	%r17,4(%r3)
+	lwz	%r16,0(%r3)
+	add	%r20,RE(80),%r20
+	add	RD(0),RD(80),%r19
+	add	RC(0),RC(80),%r18
+	add	RB(0),RB(80),%r17
+	add	RA(0),RA(80),%r16
+	mr	RE(0),%r20
+	stw	RA(0),0(%r3)
+	stw	RB(0),4(%r3)
+	stw	RC(0),8(%r3)
+	stw	RD(0),12(%r3)
+	stw	RE(0),16(%r3)
+
+	addi	%r4,%r4,64
+	bdnz	1b
+
+	lwz	%r15,FS-68(%r1)
+	lwz	%r16,FS-64(%r1)
+	lwz	%r17,FS-60(%r1)
+	lwz	%r18,FS-56(%r1)
+	lwz	%r19,FS-52(%r1)
+	lwz	%r20,FS-48(%r1)
+	lwz	%r21,FS-44(%r1)
+	lwz	%r22,FS-40(%r1)
+	lwz	%r23,FS-36(%r1)
+	lwz	%r24,FS-32(%r1)
+	lwz	%r25,FS-28(%r1)
+	lwz	%r26,FS-24(%r1)
+	lwz	%r27,FS-20(%r1)
+	lwz	%r28,FS-16(%r1)
+	lwz	%r29,FS-12(%r1)
+	lwz	%r30,FS-8(%r1)
+	lwz	%r31,FS-4(%r1)
+	addi	%r1,%r1,FS
+	blr

Re: Mozilla SHA1 implementation

[Paul Mackerras]

Linus Torvalds writes:

> Interestingly, the Mozilla SHA1 code is about twice as fast as the openssl
> code on my G5, and judging by the disassembly, it's because it's much
> simpler. I think the openssl people have unrolled all the loops totally,
> which tends to be a disaster on any half-way modern CPU. But hey, it could
> be something as simple as optimization flags too.

Which gcc version are you using?

I get the opposite result on my 2GHz G5: the Mozilla version does
45MB/s, the openssl version does 135MB/s, and my version does 218MB/s.
The time for a fsck-cache on a linux-2.6 tree (cache hot) is 8.0
seconds for the Mozilla version, 5.2 seconds for the openssl version,
and 4.4 seconds for my version.

Paul.

Re: Mozilla SHA1 implementation

[Linus Torvalds]

On Fri, 22 Apr 2005, Paul Mackerras wrote:
> Linus Torvalds writes:
> 
> > Interestingly, the Mozilla SHA1 code is about twice as fast as the openssl
> > code on my G5, and judging by the disassembly, it's because it's much
> > simpler. I think the openssl people have unrolled all the loops totally,
> > which tends to be a disaster on any half-way modern CPU. But hey, it could
> > be something as simple as optimization flags too.
> 
> Which gcc version are you using?

gcc-3.3.3.

But it's more likely the precompiled libssl. I'm not compiling the openssl
thing myself, but just using the standard 0.9.7a version that comes with
YDL. Which, btw, causes all of 

	/lib/libcrypto.so.4
	/usr/lib/libgssapi_krb5.so.2
	/usr/lib/libkrb5.so.3
	/lib/libcom_err.so.2
	/usr/lib/libk5crypto.so.3
	/lib/libresolv.so.2
	/lib/libdl.so.2

to also be included. Oh, well.

> I get the opposite result on my 2GHz G5: the Mozilla version does
> 45MB/s, the openssl version does 135MB/s, and my version does 218MB/s.
> The time for a fsck-cache on a linux-2.6 tree (cache hot) is 8.0
> seconds for the Mozilla version, 5.2 seconds for the openssl version,
> and 4.4 seconds for my version.

I get 16 seconds for the openssl one, and 8 for the Mozilla one. I'll try 
your version.

		Linus

Re: Mozilla SHA1 implementation

[Linus Torvalds]

On Fri, 22 Apr 2005, Linus Torvalds wrote:
> 
> > I get the opposite result on my 2GHz G5: the Mozilla version does
> > 45MB/s, the openssl version does 135MB/s, and my version does 218MB/s.
> > The time for a fsck-cache on a linux-2.6 tree (cache hot) is 8.0
> > seconds for the Mozilla version, 5.2 seconds for the openssl version,
> > and 4.4 seconds for my version.
> 
> I get 16 seconds for the openssl one, and 8 for the Mozilla one. I'll try 
> your version.

Ok, I get 4.9s on my kernel archive, so this is definitely a big win. 

Can you sign off on the thing, since this is real new code? Let's do it 
right.

		Linus

(anal) Q: Are there any coding styles or development guidelines?

[Klaus Robert Suetterlin]

I'm currently doing a source audit of the git core components.
Mainly I want to check if I can spot some left over memory leaks.

Unfortunately ;) I didn't find any so far (after reading five files).

Still I did find quite a lot of stuff that lint would most likely
complain about.  Like not checking return values.  Should this be
fixed now or isn't it time to do the cleanup, yet?

I also found several literal copies of the same function including
function name, parameter list, etc.  Wouldn't it be better do clean
those up and put them in a utility.{c,h} file?  A similar problem
is the continous reimplementation of linked lists, dynamic memory,
smart strings / vectors, etc.  And then there are some stale files
(i.e. revision.*) that the Changelog already mentions as removed,
but which are still active in HEAD.

I am a little reluctant to do the work, as the code still changes
so fast I do not really know if code I fix will still be there
tomorrow.

Also I do not know if there is any notion of coding style published
somewhere.  I only noticed, that the code does not look like anything
I'd have written and seems to follow some general principle.

Kind regards,

--Robert Suetterlin (robert@mpe.mpg.de)
phone: (+49)89 / 30000-3546   fax: (+49)89 / 30000-3950

Re: (anal) Q: Are there any coding styles or development guidelines?

[Linus Torvalds]

On Fri, 22 Apr 2005, Klaus Robert Suetterlin wrote:
>
> I'm currently doing a source audit of the git core components.
> Mainly I want to check if I can spot some left over memory leaks.
> 
> Unfortunately ;) I didn't find any so far (after reading five files).
> 
> Still I did find quite a lot of stuff that lint would most likely
> complain about.  Like not checking return values.  Should this be
> fixed now or isn't it time to do the cleanup, yet?

I personally don't think we're quite there yet. You'll note that a lot of 
routines just call "die()" when they don't find the data they want etc. 
All things that we probably will need to clean up eventually, but is fine 
for now.

> I also found several literal copies of the same function including
> function name, parameter list, etc.  Wouldn't it be better do clean
> those up and put them in a utility.{c,h} file?

Yes, we can start doing things like that, especially if they really _do_ 
end up making sense in a bigger picture.

Some of that is because I didn't clean up the Makefile until fairly
recently, so it used to be harder than it is now to have a shared object
file. In contrast, now you just add it to the list of library objects, and
off you go.

> A similar problem
> is the continous reimplementation of linked lists, dynamic memory,
> smart strings / vectors, etc.

Sometimes specific duplication is just _easier_ than trying to be clever 
and having some generic shared version. For example, there's a few 
data-specific versions of "insert into sorted array" there, and the fact 
is, they are so simple that it's likely less work to keep them that way 
than it would be to create some "generic" thing that did it and was passed 
in some descriptor of the data. 

Generic routines aren't always good. Sometimes the abstraction ends up 
adding more of a mental burden than just doing the thing in a simple way 
in the first place. 

> And then there are some stale files (i.e. revision.*) that the Changelog
> already mentions as removed, but which are still active in HEAD.

They definitely are _not_ active in HEAD, at least not in my version.

You may have stale copies in your directory, but they should show up as
being stale when you do "show-files --others".

		Linus

Re: Mozilla SHA1 implementation

[Daniel Barkalow]

On Fri, 22 Apr 2005, Linus Torvalds wrote:

> But it's more likely the precompiled libssl. I'm not compiling the openssl
> thing myself, but just using the standard 0.9.7a version that comes with
> YDL. Which, btw, causes all of 
> 
> 	/lib/libcrypto.so.4

This is the one that actually has the SHA1 stuff, not libssl at all. You
can skip at least some of this by just using -lcrypto.

> 	/usr/lib/libgssapi_krb5.so.2
> 	/usr/lib/libkrb5.so.3
> 	/lib/libcom_err.so.2
> 	/usr/lib/libk5crypto.so.3
> 	/lib/libresolv.so.2
> 	/lib/libdl.so.2

	-Daniel
*This .sig left intentionally blank*