[PATCH 0/3] Update sha1dc from upstream & optionally make it a submodule

[PATCH 0/3] Update sha1dc from upstream & optionally make it a submodule

[Ævar Arnfjörð Bjarmason]

This series:

Ævar Arnfjörð Bjarmason (3):
  sha1dc: update from upstream
   
   * Fixes the Big-Endian detection on Solaris SPARC (and probably
     others) which broke the build as of 2.13.0 due to sha1dc being the
     dauflt.
   
   * Includes a patch from upstream fixing unaligned access, which broke
     SPARC even more. This replaces Junio's "[PATCH] sha1dc: fix issues
     with a big endian platform"
     (<xmqq37c4xcr6.fsf_-_@gitster.mtv.corp.google.com>) with something
     which brings in upstream as-is.
   
   * Most importantly: Uses upstream code as-is with no modifications,
     which is possible due to a pull request I sent them.

   * This patch can be picked stand-alone without [23]/3.

  sha1dc: use sha1collisiondetection as a submodule

   * Since we can now use upstream code as-is let's use it as a
     submodule.
   
     Yes there are still (solvable) UX issues with submodules, but
     there's no project better equipped to deal with them than
     git.git.

  sha1dc: remove the unused sha1dc/ directory

   * Sent as a separate patch for readability. Can be squashed into
     2/3.

 .gitmodules            |   4 +
 Makefile               |  13 +-
 hash.h                 |   2 +-
 sha1collisiondetection |   1 +
 sha1dc/LICENSE.txt     |  30 ----
 sha1dc/sha1.c          |  99 +++++++++-----
 sha1dc/sha1.h          | 122 -----------------
 sha1dc/ubc_check.c     | 363 -------------------------------------------------
 sha1dc/ubc_check.h     |  44 ------
 sha1dc_git.c           |  24 ++++
 sha1dc_git.h           |  19 +++
 11 files changed, 124 insertions(+), 597 deletions(-)
 create mode 100644 .gitmodules
 create mode 160000 sha1collisiondetection
 delete mode 100644 sha1dc/LICENSE.txt
 delete mode 100644 sha1dc/sha1.h
 delete mode 100644 sha1dc/ubc_check.c
 delete mode 100644 sha1dc/ubc_check.h
 create mode 100644 sha1dc_git.c
 create mode 100644 sha1dc_git.h

-- 
2.13.0.303.g4ebf302169

[PATCH 1/3] sha1dc: update from upstream

[Ævar Arnfjörð Bjarmason]

Update sha1dc from the latest version by the upstream
maintainer[1].

This version includes a commit of mine which allows for replacing the
local modifications done to the upstream files in git.git with macro
definitions to monkeypatch it in place.

It also brings in a change[2] upstream made for the breakage 2.13.0
introduced on SPARC and other platforms that forbid unaligned
access[3].

This means that the code customizations done since the initial import
in commit 28dc98e343 ("sha1dc: add collision-detecting sha1
implementation", 2017-03-16) can be done purely via Makefile
definitions and by including the content of our own sha1dc_git.[ch] in
sha1dc/sha1.c via a macro.

1. https://github.com/cr-marcstevens/sha1collisiondetection/commit/b45fcefc71270d9a159028c22e6d36c3817da188
2. https://github.com/cr-marcstevens/sha1collisiondetection/commit/33a694a9ee1b79c24be45f9eab5ac0e1aeeaf271
3. "Git 2.13.0 segfaults on Solaris SPARC due to DC_SHA1=YesPlease
   being on by default"
   (https://public-inbox.org/git/CACBZZX6nmKK8af0-UpjCKWV4R+hV-uk2xWXVA5U+_UQ3VXU03g@mail.gmail.com/)

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 Makefile           |  9 ++++-
 sha1dc/sha1.c      | 99 +++++++++++++++++++++++++++++++++++-------------------
 sha1dc/sha1.h      | 92 ++++++++++++++++++++++----------------------------
 sha1dc/ubc_check.c | 13 +++++--
 sha1dc/ubc_check.h | 14 ++++++--
 sha1dc_git.c       | 24 +++++++++++++
 sha1dc_git.h       | 19 +++++++++++
 7 files changed, 178 insertions(+), 92 deletions(-)
 create mode 100644 sha1dc_git.c
 create mode 100644 sha1dc_git.h

diff --git a/Makefile b/Makefile
index e35542e631..ffa6da71b7 100644
--- a/Makefile
+++ b/Makefile
@@ -1414,7 +1414,14 @@ else
 	DC_SHA1 := YesPlease
 	LIB_OBJS += sha1dc/sha1.o
 	LIB_OBJS += sha1dc/ubc_check.o
-	BASIC_CFLAGS += -DSHA1_DC
+	BASIC_CFLAGS += \
+		-DSHA1_DC \
+		-DSHA1DC_NO_STANDARD_INCLUDES \
+		-DSHA1DC_INIT_SAFE_HASH_DEFAULT=0 \
+		-DSHA1DC_CUSTOM_INCLUDE_SHA1_C="\"cache.h\"" \
+		-DSHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_C="\"sha1dc_git.c\"" \
+		-DSHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H="\"sha1dc_git.h\"" \
+		-DSHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C="\"git-compat-util.h\""
 endif
 endif
 endif
diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
index 35e9dd5bf4..26516b102f 100644
--- a/sha1dc/sha1.c
+++ b/sha1dc/sha1.c
@@ -5,12 +5,26 @@
 * https://opensource.org/licenses/MIT
 ***/
 
-#include "cache.h"
-#include "sha1dc/sha1.h"
-#include "sha1dc/ubc_check.h"
+#ifndef SHA1DC_NO_STANDARD_INCLUDES
+#include <string.h>
+#include <memory.h>
+#include <stdio.h>
+#include <stdlib.h>
+#endif
+
+#ifdef SHA1DC_CUSTOM_INCLUDE_SHA1_C
+#include SHA1DC_CUSTOM_INCLUDE_SHA1_C
+#endif
+
+#ifndef SHA1DC_INIT_SAFE_HASH_DEFAULT
+#define SHA1DC_INIT_SAFE_HASH_DEFAULT 1
+#endif
 
+#include "sha1.h"
+#include "ubc_check.h"
 
-/*
+
+/* 
    Because Little-Endian architectures are most common,
    we only set SHA1DC_BIGENDIAN if one of these conditions is met.
    Note that all MSFT platforms are little endian,
@@ -18,16 +32,30 @@
    If you are compiling on a big endian platform and your compiler does not define one of these,
    you will have to add whatever macros your tool chain defines to indicate Big-Endianness.
  */
-#if (defined(__BYTE_ORDER) && (__BYTE_ORDER == __BIG_ENDIAN)) || \
+#ifdef SHA1DC_BIGENDIAN
+#undef SHA1DC_BIGENDIAN
+#endif
+#if (!defined SHA1DC_FORCE_LITTLEENDIAN) && \
+    ((defined(__BYTE_ORDER) && (__BYTE_ORDER == __BIG_ENDIAN)) || \
     (defined(__BYTE_ORDER__) && (__BYTE_ORDER__ == __BIG_ENDIAN__)) || \
-    defined(__BIG_ENDIAN__) || defined(__ARMEB__) || defined(__THUMBEB__) ||  defined(__AARCH64EB__) || \
-    defined(_MIPSEB) || defined(__MIPSEB) || defined(__MIPSEB__)
+    defined(_BIG_ENDIAN) || defined(__BIG_ENDIAN__) || defined(__ARMEB__) || defined(__THUMBEB__) ||  defined(__AARCH64EB__) || \
+    defined(_MIPSEB) || defined(__MIPSEB) || defined(__MIPSEB__) || defined(SHA1DC_FORCE_BIGENDIAN))
+
+#define SHA1DC_BIGENDIAN
 
-#define SHA1DC_BIGENDIAN	1
-#else
-#undef SHA1DC_BIGENDIAN
 #endif /*ENDIANNESS SELECTION*/
 
+#if (defined(__amd64__) || defined(__amd64) || defined(__x86_64__) || defined(__x86_64) || \
+     defined(i386) || defined(__i386) || defined(__i386__) || defined(__i486__)  || \
+     defined(__i586__) || defined(__i686__) || defined(_M_IX86) || defined(__X86__) || \
+     defined(_X86_) || defined(__THW_INTEL__) || defined(__I86__) || defined(__INTEL__) || \
+     defined(__386) || defined(_M_X64) || defined(_M_AMD64))
+
+#define SHA1DC_ALLOW_UNALIGNED_ACCESS
+
+#endif /*UNALIGNMENT DETECTION*/
+
+
 #define rotate_right(x,n) (((x)>>(n))|((x)<<(32-(n))))
 #define rotate_left(x,n)  (((x)<<(n))|((x)>>(32-(n))))
 
@@ -36,11 +64,11 @@
 
 #define sha1_mix(W, t)  (rotate_left(W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16], 1))
 
-#if defined(SHA1DC_BIGENDIAN)
+#ifdef SHA1DC_BIGENDIAN
 	#define sha1_load(m, t, temp)  { temp = m[t]; }
 #else
 	#define sha1_load(m, t, temp)  { temp = m[t]; sha1_bswap32(temp); }
-#endif /* !defined(SHA1DC_BIGENDIAN) */
+#endif
 
 #define sha1_store(W, t, x)	*(volatile uint32_t *)&W[t] = x
 
@@ -869,6 +897,11 @@ static void sha1recompress_fast_ ## t (uint32_t ihvin[5], uint32_t ihvout[5], co
 	ihvout[0] = ihvin[0] + a; ihvout[1] = ihvin[1] + b; ihvout[2] = ihvin[2] + c; ihvout[3] = ihvin[3] + d; ihvout[4] = ihvin[4] + e; \
 }
 
+#ifdef _MSC_VER
+#pragma warning(push)
+#pragma warning(disable: 4127)  /* Complier complains about the checks in the above macro being constant. */
+#endif
+
 #ifdef DOSTORESTATE0
 SHA1_RECOMPRESS(0)
 #endif
@@ -1189,6 +1222,10 @@ SHA1_RECOMPRESS(78)
 SHA1_RECOMPRESS(79)
 #endif
 
+#ifdef _MSC_VER
+#pragma warning(pop)
+#endif
+
 static void sha1_recompression_step(uint32_t step, uint32_t ihvin[5], uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5])
 {
 	switch (step)
@@ -1606,7 +1643,7 @@ static void sha1_process(SHA1_CTX* ctx, const uint32_t block[16])
 	unsigned i, j;
 	uint32_t ubc_dv_mask[DVMASKSIZE] = { 0xFFFFFFFF };
 	uint32_t ihvtmp[5];
-
+	
 	ctx->ihv1[0] = ctx->ihv[0];
 	ctx->ihv1[1] = ctx->ihv[1];
 	ctx->ihv1[2] = ctx->ihv[2];
@@ -1662,7 +1699,7 @@ void SHA1DCInit(SHA1_CTX* ctx)
 	ctx->ihv[3] = 0x10325476;
 	ctx->ihv[4] = 0xC3D2E1F0;
 	ctx->found_collision = 0;
-	ctx->safe_hash = 0;
+	ctx->safe_hash = SHA1DC_INIT_SAFE_HASH_DEFAULT;
 	ctx->ubc_check = 1;
 	ctx->detect_coll = 1;
 	ctx->reduced_round_coll = 0;
@@ -1710,6 +1747,9 @@ void SHA1DCSetCallback(SHA1_CTX* ctx, collision_block_callback callback)
 void SHA1DCUpdate(SHA1_CTX* ctx, const char* buf, size_t len)
 {
 	unsigned left, fill;
+
+    const uint32_t* buffer_to_hash = NULL;
+
 	if (len == 0)
 		return;
 
@@ -1728,7 +1768,14 @@ void SHA1DCUpdate(SHA1_CTX* ctx, const char* buf, size_t len)
 	while (len >= 64)
 	{
 		ctx->total += 64;
-		sha1_process(ctx, (uint32_t*)(buf));
+
+#if defined(SHA1DC_ALLOW_UNALIGNED_ACCESS)
+        buffer_to_hash = (const uint32_t*)buf;
+#else
+        buffer_to_hash = (const uint32_t*)ctx->buffer;
+        memcpy(ctx->buffer, buf, 64);
+#endif /* defined(SHA1DC_ALLOW_UNALIGNED_ACCESS) */
+		sha1_process(ctx, buffer_to_hash);
 		buf += 64;
 		len -= 64;
 	}
@@ -1788,22 +1835,6 @@ int SHA1DCFinal(unsigned char output[20], SHA1_CTX *ctx)
 	return ctx->found_collision;
 }
 
-void git_SHA1DCFinal(unsigned char hash[20], SHA1_CTX *ctx)
-{
-	if (!SHA1DCFinal(hash, ctx))
-		return;
-	die("SHA-1 appears to be part of a collision attack: %s",
-	    sha1_to_hex(hash));
-}
-
-void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *vdata, unsigned long len)
-{
-	const char *data = vdata;
-	/* We expect an unsigned long, but sha1dc only takes an int */
-	while (len > INT_MAX) {
-		SHA1DCUpdate(ctx, data, INT_MAX);
-		data += INT_MAX;
-		len -= INT_MAX;
-	}
-	SHA1DCUpdate(ctx, data, len);
-}
+#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_C
+#include SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_C
+#endif
diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
index bd8bd928fb..dd41b0a5a6 100644
--- a/sha1dc/sha1.h
+++ b/sha1dc/sha1.h
@@ -4,6 +4,7 @@
 * See accompanying file LICENSE.txt or copy at
 * https://opensource.org/licenses/MIT
 ***/
+
 #ifndef SHA1DC_SHA1_H
 #define SHA1DC_SHA1_H
 
@@ -11,36 +12,30 @@
 extern "C" {
 #endif
 
-/* uses SHA-1 message expansion to expand the first 16 words of W[] to 80 words */
-/* void sha1_message_expansion(uint32_t W[80]); */
-
-/* sha-1 compression function; first version takes a message block pre-parsed as 16 32-bit integers, second version takes an already expanded message) */
-/* void sha1_compression(uint32_t ihv[5], const uint32_t m[16]);
-void sha1_compression_W(uint32_t ihv[5], const uint32_t W[80]); */
+#ifndef SHA1DC_NO_STANDARD_INCLUDES
+#include <stdint.h>
+#endif
 
-/* same as sha1_compression_W, but additionally store intermediate states */
+/* sha-1 compression function that takes an already expanded message, and additionally store intermediate states */
 /* only stores states ii (the state between step ii-1 and step ii) when DOSTORESTATEii is defined in ubc_check.h */
 void sha1_compression_states(uint32_t[5], const uint32_t[16], uint32_t[80], uint32_t[80][5]);
 
 /*
-// function type for sha1_recompression_step_T (uint32_t ihvin[5], uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5])
-// where 0 <= T < 80
-//       me2 is an expanded message (the expansion of an original message block XOR'ed with a disturbance vector's message block difference)
-//       state is the internal state (a,b,c,d,e) before step T of the SHA-1 compression function while processing the original message block
-// the function will return:
-//       ihvin: the reconstructed input chaining value
-//       ihvout: the reconstructed output chaining value
+// Function type for sha1_recompression_step_T (uint32_t ihvin[5], uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5]).
+// Where 0 <= T < 80
+//       me2 is an expanded message (the expansion of an original message block XOR'ed with a disturbance vector's message block difference.)
+//       state is the internal state (a,b,c,d,e) before step T of the SHA-1 compression function while processing the original message block.
+// The function will return:
+//       ihvin: The reconstructed input chaining value.
+//       ihvout: The reconstructed output chaining value.
 */
 typedef void(*sha1_recompression_type)(uint32_t*, uint32_t*, const uint32_t*, const uint32_t*);
 
-/* table of sha1_recompression_step_0, ... , sha1_recompression_step_79 */
-/* extern sha1_recompression_type sha1_recompression_step[80];*/
-
-/* a callback function type that can be set to be called when a collision block has been found: */
+/* A callback function type that can be set to be called when a collision block has been found: */
 /* void collision_block_callback(uint64_t byteoffset, const uint32_t ihvin1[5], const uint32_t ihvin2[5], const uint32_t m1[80], const uint32_t m2[80]) */
 typedef void(*collision_block_callback)(uint64_t, const uint32_t*, const uint32_t*, const uint32_t*, const uint32_t*);
 
-/* the SHA-1 context */
+/* The SHA-1 context. */
 typedef struct {
 	uint64_t total;
 	uint32_t ihv[5];
@@ -59,30 +54,34 @@ typedef struct {
 	uint32_t states[80][5];
 } SHA1_CTX;
 
-/* initialize SHA-1 context */
+/* Initialize SHA-1 context. */
 void SHA1DCInit(SHA1_CTX*);
 
 /*
-// function to enable safe SHA-1 hashing:
-// collision attacks are thwarted by hashing a detected near-collision block 3 times
-// think of it as extending SHA-1 from 80-steps to 240-steps for such blocks:
-//   the best collision attacks against SHA-1 have complexity about 2^60,
-//   thus for 240-steps an immediate lower-bound for the best cryptanalytic attacks would 2^180
-//   an attacker would be better off using a generic birthday search of complexity 2^80
-//
-// enabling safe SHA-1 hashing will result in the correct SHA-1 hash for messages where no collision attack was detected
-// but it will result in a different SHA-1 hash for messages where a collision attack was detected
-// this will automatically invalidate SHA-1 based digital signature forgeries
-// enabled by default
+    Function to enable safe SHA-1 hashing:
+    Collision attacks are thwarted by hashing a detected near-collision block 3 times.
+    Think of it as extending SHA-1 from 80-steps to 240-steps for such blocks:
+        The best collision attacks against SHA-1 have complexity about 2^60,
+        thus for 240-steps an immediate lower-bound for the best cryptanalytic attacks would be 2^180.
+        An attacker would be better off using a generic birthday search of complexity 2^80.
+  
+   Enabling safe SHA-1 hashing will result in the correct SHA-1 hash for messages where no collision attack was detected,
+   but it will result in a different SHA-1 hash for messages where a collision attack was detected.
+   This will automatically invalidate SHA-1 based digital signature forgeries.
+   Enabled by default.
 */
 void SHA1DCSetSafeHash(SHA1_CTX*, int);
 
-/* function to disable or enable the use of Unavoidable Bitconditions (provides a significant speed up) */
-/* enabled by default */
+/*
+    Function to disable or enable the use of Unavoidable Bitconditions (provides a significant speed up).
+    Enabled by default
+ */
 void SHA1DCSetUseUBC(SHA1_CTX*, int);
 
-/* function to disable or enable the use of Collision Detection */
-/* enabled by default */
+/*
+    Function to disable or enable the use of Collision Detection.
+    Enabled by default.
+ */
 void SHA1DCSetUseDetectColl(SHA1_CTX*, int);
 
 /* function to disable or enable the detection of reduced-round SHA-1 collisions */
@@ -98,25 +97,14 @@ void SHA1DCUpdate(SHA1_CTX*, const char*, size_t);
 
 /* obtain SHA-1 hash from SHA-1 context */
 /* returns: 0 = no collision detected, otherwise = collision found => warn user for active attack */
-int  SHA1DCFinal(unsigned char[20], SHA1_CTX*);
-
-/*
- * Same as SHA1DCFinal, but convert collision attack case into a verbose die().
- */
-void git_SHA1DCFinal(unsigned char [20], SHA1_CTX *);
-
-/*
- * Same as SHA1DCUpdate, but adjust types to match git's usual interface.
- */
-void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *data, unsigned long len);
-
-#define platform_SHA_CTX SHA1_CTX
-#define platform_SHA1_Init SHA1DCInit
-#define platform_SHA1_Update git_SHA1DCUpdate
-#define platform_SHA1_Final git_SHA1DCFinal
+int  SHA1DCFinal(unsigned char[20], SHA1_CTX*); 
 
 #if defined(__cplusplus)
 }
 #endif
 
-#endif /* SHA1DC_SHA1_H */
+#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H
+#include SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H
+#endif
+
+#endif
diff --git a/sha1dc/ubc_check.c b/sha1dc/ubc_check.c
index 089dd4743d..b3beff2afb 100644
--- a/sha1dc/ubc_check.c
+++ b/sha1dc/ubc_check.c
@@ -24,8 +24,13 @@
 // ubc_check has been verified against ubc_check_verify using the 'ubc_check_test' program in the tools section
 */
 
-#include "git-compat-util.h"
-#include "sha1dc/ubc_check.h"
+#ifndef SHA1DC_NO_STANDARD_INCLUDES
+#include <stdint.h>
+#endif
+#ifdef SHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C
+#include SHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C
+#endif
+#include "ubc_check.h"
 
 static const uint32_t DV_I_43_0_bit 	= (uint32_t)(1) << 0;
 static const uint32_t DV_I_44_0_bit 	= (uint32_t)(1) << 1;
@@ -361,3 +366,7 @@ if (mask) {
 
 	dvmask[0]=mask;
 }
+
+#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_C
+#include SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_C
+#endif
diff --git a/sha1dc/ubc_check.h b/sha1dc/ubc_check.h
index b64c306d77..d7e17dc734 100644
--- a/sha1dc/ubc_check.h
+++ b/sha1dc/ubc_check.h
@@ -20,13 +20,17 @@
 // thus one needs to do the recompression check for each DV that has its bit set
 */
 
-#ifndef UBC_CHECK_H
-#define UBC_CHECK_H
+#ifndef SHA1DC_UBC_CHECK_H
+#define SHA1DC_UBC_CHECK_H
 
 #if defined(__cplusplus)
 extern "C" {
 #endif
 
+#ifndef SHA1DC_NO_STANDARD_INCLUDES
+#include <stdint.h>
+#endif
+
 #define DVMASKSIZE 1
 typedef struct { int dvType; int dvK; int dvB; int testt; int maski; int maskb; uint32_t dm[80]; } dv_info_t;
 extern dv_info_t sha1_dvs[];
@@ -41,4 +45,8 @@ void ubc_check(const uint32_t W[80], uint32_t dvmask[DVMASKSIZE]);
 }
 #endif
 
-#endif /* UBC_CHECK_H */
+#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_H
+#include SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_H
+#endif
+
+#endif
diff --git a/sha1dc_git.c b/sha1dc_git.c
new file mode 100644
index 0000000000..4d32b4f77e
--- /dev/null
+++ b/sha1dc_git.c
@@ -0,0 +1,24 @@
+/*
+ * This code is included at the end of sha1dc/sha1.c with the
+ * SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_C macro.
+ */
+
+void git_SHA1DCFinal(unsigned char hash[20], SHA1_CTX *ctx)
+{
+	if (!SHA1DCFinal(hash, ctx))
+		return;
+	die("SHA-1 appears to be part of a collision attack: %s",
+	    sha1_to_hex(hash));
+}
+
+void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *vdata, unsigned long len)
+{
+	const char *data = vdata;
+	/* We expect an unsigned long, but sha1dc only takes an int */
+	while (len > INT_MAX) {
+		SHA1DCUpdate(ctx, data, INT_MAX);
+		data += INT_MAX;
+		len -= INT_MAX;
+	}
+	SHA1DCUpdate(ctx, data, len);
+}
diff --git a/sha1dc_git.h b/sha1dc_git.h
new file mode 100644
index 0000000000..a8a5c1da16
--- /dev/null
+++ b/sha1dc_git.h
@@ -0,0 +1,19 @@
+/*
+ * This code is included at the end of sha1dc/sha1.h with the
+ * SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H macro.
+ */
+
+/*
+ * Same as SHA1DCFinal, but convert collision attack case into a verbose die().
+ */
+void git_SHA1DCFinal(unsigned char [20], SHA1_CTX *);
+
+/*
+ * Same as SHA1DCUpdate, but adjust types to match git's usual interface.
+ */
+void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *data, unsigned long len);
+
+#define platform_SHA_CTX SHA1_CTX
+#define platform_SHA1_Init SHA1DCInit
+#define platform_SHA1_Update git_SHA1DCUpdate
+#define platform_SHA1_Final git_SHA1DCFinal
-- 
2.13.0.303.g4ebf302169

[PATCH 2/3] sha1dc: use sha1collisiondetection as a submodule

[Ævar Arnfjörð Bjarmason]

Replace the forked sha1dc directory with a copy of the upstream code
imported as a submodule. This is the exact same code as now exists in
the sha1dc/ directory.

The initial reason for copy/pasting the code into sha1dc and locally
modifying it was that it needed to be altered to work with the git
project.

The upstream project has accepted my code changes to allow us to use
their code as-is, see the preceding commit for details. So import the
code as a submodule instead, this will make it easier to keep
up-to-date with any upstream fixes or improvements.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 .gitmodules            | 4 ++++
 Makefile               | 4 ++--
 hash.h                 | 2 +-
 sha1collisiondetection | 1 +
 4 files changed, 8 insertions(+), 3 deletions(-)
 create mode 100644 .gitmodules
 create mode 160000 sha1collisiondetection

diff --git a/.gitmodules b/.gitmodules
new file mode 100644
index 0000000000..cbeebdab7a
--- /dev/null
+++ b/.gitmodules
@@ -0,0 +1,4 @@
+[submodule "sha1collisiondetection"]
+	path = sha1collisiondetection
+	url = https://github.com/cr-marcstevens/sha1collisiondetection.git
+	branch = master
diff --git a/Makefile b/Makefile
index ffa6da71b7..d7f506e790 100644
--- a/Makefile
+++ b/Makefile
@@ -1412,8 +1412,8 @@ ifdef APPLE_COMMON_CRYPTO
 	BASIC_CFLAGS += -DSHA1_APPLE
 else
 	DC_SHA1 := YesPlease
-	LIB_OBJS += sha1dc/sha1.o
-	LIB_OBJS += sha1dc/ubc_check.o
+	LIB_OBJS += sha1collisiondetection/lib/sha1.o
+	LIB_OBJS += sha1collisiondetection/lib/ubc_check.o
 	BASIC_CFLAGS += \
 		-DSHA1_DC \
 		-DSHA1DC_NO_STANDARD_INCLUDES \
diff --git a/hash.h b/hash.h
index a11fc9233f..9d9892ac3e 100644
--- a/hash.h
+++ b/hash.h
@@ -8,7 +8,7 @@
 #elif defined(SHA1_OPENSSL)
 #include <openssl/sha.h>
 #elif defined(SHA1_DC)
-#include "sha1dc/sha1.h"
+#include "sha1collisiondetection/lib/sha1.h"
 #else /* SHA1_BLK */
 #include "block-sha1/sha1.h"
 #endif
diff --git a/sha1collisiondetection b/sha1collisiondetection
new file mode 160000
index 0000000000..b45fcefc71
--- /dev/null
+++ b/sha1collisiondetection
@@ -0,0 +1 @@
+Subproject commit b45fcefc71270d9a159028c22e6d36c3817da188
-- 
2.13.0.303.g4ebf302169

Re: [PATCH 2/3] sha1dc: use sha1collisiondetection as a submodule

[Junio C Hamano]

Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:

> Replace the forked sha1dc directory with a copy of the upstream code
> imported as a submodule. This is the exact same code as now exists in
> the sha1dc/ directory.
>
> The initial reason for copy/pasting the code into sha1dc and locally
> modifying it was that it needed to be altered to work with the git
> project.
>
> The upstream project has accepted my code changes to allow us to use
> their code as-is, see the preceding commit for details. So import the
> code as a submodule instead, this will make it easier to keep
> up-to-date with any upstream fixes or improvements.
>
> Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
> ---
>  .gitmodules            | 4 ++++
>  Makefile               | 4 ++--
>  hash.h                 | 2 +-
>  sha1collisiondetection | 1 +
>  4 files changed, 8 insertions(+), 3 deletions(-)
>  create mode 100644 .gitmodules
>  create mode 160000 sha1collisiondetection

I am not sure how prepared our .travis.yml is to deal with a
submodule, I'd prefer to have this step broken down to two step
process.

That is, [PATCH 2.1/3] first adds an otherwise unused submodule, so
that people can optionally do "git submodule init && git submodule
update" so that they can compare the contents of sha1dc/ that has
been updated by [PATCH 1/3] with the up-to-date upstream.  Then
[PATCH 2.2/3] would update the Makefile and hash.h to use the code
in the submodule.

I actually would want to see us proceed even more cautiously---if
the latter-half, i.e. [PATCH 2.2/3], is arranged so that it uses the
new sha1collisiondetection/ only when the submodule is initialized
and populated, and otherwise it uses sha1dc/ as before, I would feel
a lot safer.  I wouldn't be this paranoid if this "let's start using
submodule ourselves" were done to some optional corner (like compat/
or contrib/ somewhere), but this is the default hash function.  I do
want to have something like this to force us (and submodule folks)
to get any kinks out, but I do not want to see many people not even
be able to build while this new arrangement is eased in.  Once
people are comfortable with the new arrangement to use code from
submodule, we can then take [PATCH 3/3] to remove the old sha1dc/
directory and the migration will be complete.

I also am not very happy with .gitmodules pointing at a single point
of failure.  It would be nice if you can arrange a couple of mirrors
and have a comment in .gitmodules file to tell folks that they can
use these alternates by insteadOf or some other mechanism.

Thanks.

[PATCH v2 0/2] Update sha1dc from upstream & optionally make it a submodule

[Ævar Arnfjörð Bjarmason]

On Sat, May 20, 2017 at 1:13 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:
>
>> Replace the forked sha1dc directory with a copy of the upstream code
>> imported as a submodule. This is the exact same code as now exists in
>> the sha1dc/ directory.
>>
>> The initial reason for copy/pasting the code into sha1dc and locally
>> modifying it was that it needed to be altered to work with the git
>> project.
>>
>> The upstream project has accepted my code changes to allow us to use
>> their code as-is, see the preceding commit for details. So import the
>> code as a submodule instead, this will make it easier to keep
>> up-to-date with any upstream fixes or improvements.
>>
>> Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
>> ---
>>  .gitmodules            | 4 ++++
>>  Makefile               | 4 ++--
>>  hash.h                 | 2 +-
>>  sha1collisiondetection | 1 +
>>  4 files changed, 8 insertions(+), 3 deletions(-)
>>  create mode 100644 .gitmodules
>>  create mode 160000 sha1collisiondetection
>
> I am not sure how prepared our .travis.yml is to deal with a
> submodule, I'd prefer to have this step broken down to two step
> process.
>
> That is, [PATCH 2.1/3] first adds an otherwise unused submodule, so
> that people can optionally do "git submodule init && git submodule
> update" so that they can compare the contents of sha1dc/ that has
> been updated by [PATCH 1/3] with the up-to-date upstream.  Then
> [PATCH 2.2/3] would update the Makefile and hash.h to use the code
> in the submodule.
>
> I actually would want to see us proceed even more cautiously---if
> the latter-half, i.e. [PATCH 2.2/3], is arranged so that it uses the
> new sha1collisiondetection/ only when the submodule is initialized
> and populated, and otherwise it uses sha1dc/ as before, I would feel
> a lot safer.  I wouldn't be this paranoid if this "let's start using
> submodule ourselves" were done to some optional corner (like compat/
> or contrib/ somewhere), but this is the default hash function.  I do
> want to have something like this to force us (and submodule folks)
> to get any kinks out, but I do not want to see many people not even
> be able to build while this new arrangement is eased in.  Once
> people are comfortable with the new arrangement to use code from
> submodule, we can then take [PATCH 3/3] to remove the old sha1dc/
> directory and the migration will be complete.

Makes sense to take it slow. Hopefully this addresses your comments. I
dropped the 3rd patch to remove sha1dc/ and the 2nd patch adds
sha1collisiondetection/ as submodule, but it's not used unless you
specify DC_SHA1_SUBMODULE in addition to DC_SHA1.

Both patches should be safe to include & not cause any disruption, but
now those interested in making the submodule experience in git.git
better can init/update & set DC_SHA1_SUBMODULE=Y to play with it.

Note that both patches update to a newer version of the upstream
code. I sent them another pull request with some cleanups, one of
which is to ignore .depends in their .gitignore file.

> I also am not very happy with .gitmodules pointing at a single point
> of failure.  It would be nice if you can arrange a couple of mirrors
> and have a comment in .gitmodules file to tell folks that they can
> use these alternates by insteadOf or some other mechanism.

I liked the suggestion to make the URL a relative path, but this would
require you to maintain a mirror in the same places you push git.git
to, is that something you'd be willing to do?

For now having no-mirror isn't a big issue with my new 2/2 since it'se
something you have to opt-in to with a build flag, which I suspect
only I/Brandon/Stefan & a few others will use.

Ævar Arnfjörð Bjarmason (2):
  sha1dc: update from upstream
  sha1dc: optionally use sha1collisiondetection as a submodule

 .gitmodules            |  4 +++
 Makefile               | 21 +++++++++++-
 hash.h                 |  4 +++
 sha1collisiondetection |  1 +
 sha1dc/sha1.c          | 91 +++++++++++++++++++++++++++++++++-----------------
 sha1dc/sha1.h          | 90 ++++++++++++++++++++++---------------------------
 sha1dc/ubc_check.c     | 13 ++++++--
 sha1dc/ubc_check.h     | 14 ++++++--
 sha1dc_git.c           | 24 +++++++++++++
 sha1dc_git.h           | 19 +++++++++++
 10 files changed, 193 insertions(+), 88 deletions(-)
 create mode 100644 .gitmodules
 create mode 160000 sha1collisiondetection
 create mode 100644 sha1dc_git.c
 create mode 100644 sha1dc_git.h

-- 
2.13.0.303.g4ebf302169

Re: [PATCH v2 0/2] Update sha1dc from upstream & optionally make it a submodule

[Junio C Hamano]

Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:

> I liked the suggestion to make the URL a relative path, but this would
> require you to maintain a mirror in the same places you push git.git
> to, is that something you'd be willing to do?

After thinking about this a bit more, I know what I think we want a
bit better.

Relative URL (e.g. ../sha1collisiondetection that sits next to the
copy of git.git) may be a good way to go.  I can arrange to create
necessary repository next to git.git on k.org and github.com but I
need to double check about other places

Whether the submodule is referenced by a relative URL from the main
project, the submodule should not come directly from the upstream,
and various mirrors that sit next to git.git should not be blind and
automated "mirrors".  This is because I do not want us to trust the
security measures of https://github.com/cr-marcstevens/ repository.
The consumers already need to trust k.org/pub/scm/git/git.git and by
ensuring k.org/pub/scm/git/sha1dc is managed the same way, they do
not have to trust anything extra.

Another reason is that we want to make sure all commits in the
submodule that we bind to the superproject (i.e. git.git) are always
in the submodule, regardless of what our upstream does, and one way
to do so is to have control over _our_ canonical repository for the
submodule.  In normal times, it will faithfully follow the upstream
without doing anything else, but we'd keep the option of anchoring a
submodule commit that is referenced by the superproject history with
our own tag, if it is ever rewound away in the upstream history for
whatever reason.

Thanks.

Re: [PATCH v2 0/2] Update sha1dc from upstream & optionally make it a submodule

[Stefan Beller]

On Mon, May 22, 2017 at 3:27 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:
>
>> I liked the suggestion to make the URL a relative path, but this would
>> require you to maintain a mirror in the same places you push git.git
>> to, is that something you'd be willing to do?
>
> After thinking about this a bit more, I know what I think we want a
> bit better.
>
> Relative URL (e.g. ../sha1collisiondetection that sits next to the
> copy of git.git) may be a good way to go.  I can arrange to create
> necessary repository next to git.git on k.org and github.com but I
> need to double check about other places

And here we see another deficit with a single URL:
We have to abide by the same scheme at all hosting endpoints.

For example consider the host https://kernel.googlesource.com/pub/scm/git/git
that mirrors from kernel.org. It would be able to bind the
submodule at  https://kernel.googlesource.com/pub/scm/git/git/sha1dc
i.e. it would look like a subdirectory of the main git repo.

This is not an issue for our desired usecase, as all hosts can comply
with the scheme that you outlined (url=../sha1...), but worth noting that
in the long term we may want to have the ability to "configure" each
remote individually by having out-of-history config options. I think we
would want to solve that via a "refs/meta/gitmodules" branch that can be
adapted per remote. (original idea from jrnieder@)

> Whether the submodule is referenced by a relative URL from the main
> project, the submodule should not come directly from the upstream,
> and various mirrors that sit next to git.git should not be blind and
> automated "mirrors".

That sounds reasonable for our sanity.

> This is because I do not want us to trust the
> security measures of https://github.com/cr-marcstevens/ repository.
> The consumers already need to trust k.org/pub/scm/git/git.git and by
> ensuring k.org/pub/scm/git/sha1dc is managed the same way, they do
> not have to trust anything extra.

The trust would be transitive, as the said submodule is referenced via
sha1, so all malicious actions upstream could perform are:
* denial of service: (by remove a commit that we pointed at in our history)
* denial of service 2: add a huge blob to their repo, such that anyone
  obtaining the submodule not carefully is annoyed by a super large repo.
* add additional malicious data (such as illegal numbers and algorithms)
  to a branch, which would be obtained by users cloning the submodule
  carelessly.

> Another reason is that we want to make sure all commits in the
> submodule that we bind to the superproject (i.e. git.git) are always
> in the submodule, regardless of what our upstream does, and one way
> to do so is to have control over _our_ canonical repository for the
> submodule.

By having all repos under one entity of trust, we would not need to discuss
all kinds of possible attacks as above.

>  In normal times, it will faithfully follow the upstream
> without doing anything else, but we'd keep the option of anchoring a
> submodule commit that is referenced by the superproject history with
> our own tag, if it is ever rewound away in the upstream history for
> whatever reason.

That makes sense.

Thanks,
Stefan

Re: [PATCH v2 0/2] Update sha1dc from upstream & optionally make it a submodule

[Junio C Hamano]

Stefan Beller <sbeller@google.com> writes:

> On Mon, May 22, 2017 at 3:27 PM, Junio C Hamano <gitster@pobox.com> wrote:
>> Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:
>>
>>> I liked the suggestion to make the URL a relative path, but this would
>>> require you to maintain a mirror in the same places you push git.git
>>> to, is that something you'd be willing to do?
>>
>> After thinking about this a bit more, I know what I think we want a
>> bit better.
>>
>> Relative URL (e.g. ../sha1collisiondetection that sits next to the
>> copy of git.git) may be a good way to go.  I can arrange to create
>> necessary repository next to git.git on k.org and github.com but I
>> need to double check about other places
>
> And here we see another deficit with a single URL:
> We have to abide by the same scheme at all hosting endpoints.

FWIW, I do not see it a deficit.  It is a price you may or may not
be willing to pay for simplicity, and I think it is a reasonable
trade-off.

The .gitmodules format can be enhanced to list multiple URLs quite
easily.  I think the current users all use the equivalent of "git
config -f .gitmodules submodule.foo.url" to grab one value.  Unless
the user chooses to do anything special, they will continue to get
the same behaviour whensuch an enhancement happens, which is a good
thing.

But then, you need to design what users choose to do that is
"something special".  Should "git clone --recurse-submodules" have a
way to control which one of the not-yet-known-before-cloning URLs
that may be listed in .gitmodules?  Will we have a way to say "For
North American users, we recommend this URL, while Asians may want
to fetch from this other URL" in .gitmodules and then the recursive
clone have a way to say "I want the European option"?  Would the
recursive clone have a way to go interactive?

And from that point of view, "you'll find the submodules relative to
the superproject" convention is one way (not necessarily the only
way) to allow users not to care too much.  The simplicity comes with
price and that is perfectly acceptable.

Also a single URL scheme may still perfectly fine.  .gitmodules may
have new submodule.<name>.alternateURL fields and recursive clone
can be told to optionally go interactive when such fields are
present.

Or README can list alternate URLs and instruct the users to use the
insteadOf if they want to go to mirrors instead.  Those users who do
care about picking particular mirror are likely not favor simplicity
over flexibility, so they would not likely to do a recursive clone
(after all, clone is a single-time operation) and it may be
sufficient if they can clone the top-level, read README and then
decide how and from where they get their submodules.

Re: [PATCH v2 0/2] Update sha1dc from upstream & optionally make it a submodule

[Ævar Arnfjörð Bjarmason]

On Tue, May 23, 2017 at 12:27 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:
>
>> I liked the suggestion to make the URL a relative path, but this would
>> require you to maintain a mirror in the same places you push git.git
>> to, is that something you'd be willing to do?
>
> After thinking about this a bit more, I know what I think we want a
> bit better.
>
> Relative URL (e.g. ../sha1collisiondetection that sits next to the
> copy of git.git) may be a good way to go.  I can arrange to create
> necessary repository next to git.git on k.org and github.com but I
> need to double check about other places

If the URL doesn't point to the canonical upstream how do we review a
patch to update sha1dc here on list? Doesn't change from "'git am'
this and it'll work" to "'git am' this and it'll fail, then do this
submodule config modification dance, and run some other command....".

I haven't tried repointing a submodule temporarily (and locally) to
another URL for such a use, how is that even done?

> Whether the submodule is referenced by a relative URL from the main
> project, the submodule should not come directly from the upstream,
> and various mirrors that sit next to git.git should not be blind and
> automated "mirrors".  This is because I do not want us to trust the
> security measures of https://github.com/cr-marcstevens/ repository.
> The consumers already need to trust k.org/pub/scm/git/git.git and by
> ensuring k.org/pub/scm/git/sha1dc is managed the same way, they do
> not have to trust anything extra.

I had the same comments Stefan pointed out below about this. So I
won't repeat any of that...

> Another reason is that we want to make sure all commits in the
> submodule that we bind to the superproject (i.e. git.git) are always
> in the submodule, regardless of what our upstream does, and one way
> to do so is to have control over _our_ canonical repository for the
> submodule.  In normal times, it will faithfully follow the upstream
> without doing anything else, but we'd keep the option of anchoring a
> submodule commit that is referenced by the superproject history with
> our own tag, if it is ever rewound away in the upstream history for
> whatever reason.

If we were talking about any other project but git.git I'd say "yeah
this makes sense".

But I think in our case we should keep in mind the main point of this
exercise is for us to dogfood submodule usage, not just so we get
whatever trivial benefits from updating the sha1collision/ directory
from upstream, but so that we run into issues with submodules that we
solve for all our users.

In this case you're basically concerned with:

 * We have N mirrors, but the upstream submodule URL is just one URL,
so let's not point to that, but to our N mirrors

Could also be addressed with a combination of 'pullUrl' for submodules
(inverse of pushUrl for push) to list the canonical one & list of
mirrors (or use the relative URL).

 * What if upstream say 5 years in the future rewinds their history,
github shuts down or whatever, can we check out and work with older
versions of git.git?

Seems like it would be useful to have a way to ex-post-facto say "past
history should use these URLs". i.e. if all git.git mirrors go down
and we have to re-host, then you can just clone git.git and off you
go, but the same isn't true of past submodule urls, or is it?

Re: [PATCH v2 0/2] Update sha1dc from upstream & optionally make it a submodule

[Junio C Hamano]

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

> Seems like it would be useful to have a way to ex-post-facto say "past
> history should use these URLs". i.e. if all git.git mirrors go down
> and we have to re-host, then you can just clone git.git and off you
> go, but the same isn't true of past submodule urls, or is it?

I do not know how heavily you are used to use submodules, but I
think submodule's URL is copied to the config of the superproject,
and that URL is what will be used from there on, so "past history or
future history will use that URL" is already the case, no?

Re: [PATCH v2 0/2] Update sha1dc from upstream & optionally make it a submodule

[Ævar Arnfjörð Bjarmason]

On Tue, May 23, 2017 at 3:06 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:
>
>> Seems like it would be useful to have a way to ex-post-facto say "past
>> history should use these URLs". i.e. if all git.git mirrors go down
>> and we have to re-host, then you can just clone git.git and off you
>> go, but the same isn't true of past submodule urls, or is it?
>
> I do not know how heavily you are used to use submodules, but I
> think submodule's URL is copied to the config of the superproject,
> and that URL is what will be used from there on, so "past history or
> future history will use that URL" is already the case, no?

I haven't used them much, just starting to get familiar with them now again.

I thought given your "if it is ever rewound away in the upstream
history..." that if we e.g. pegged upstream to that github URL now
that if that got rewound, anyone working with git.git in the future
would be in for some pain if they needed to check out and test old
tags.

But from what you're saying here that seems like a non-issue, i.e. in
such a scenario we'd just mirror the original repo[1], change the URL
in git.git to that, and then anyone could easily use older history
since it would be pointing to the new mirror.

I.e. in the spirit of my last reply, this seems like deviating from
the default workflow around submodules out of concern for an extremely
unlikely scenario, which, if it happened, would be easily mitigated
for both past & future git.git history.

1. Or likely just ask upstream kindly to push a tag with the old history.

Re: [PATCH v2 0/2] Update sha1dc from upstream & optionally make it a submodule

[Junio C Hamano]

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

> But from what you're saying here that seems like a non-issue, i.e. in
> such a scenario we'd just mirror the original repo[1], change the URL
> in git.git to that, and then anyone could easily use older history
> since it would be pointing to the new mirror.

Those who cloned before such a switch will still have the URL they
chose when they cloned and did "submodule init" on it, I think, so
they need to explicitly choose to switch to the new URL.  So I would
not exactly say "seems like a non-issue"; it certainly is an easy
thing to work around.

[PATCH v2 1/2] sha1dc: update from upstream

[Ævar Arnfjörð Bjarmason]

Update sha1dc from the latest version by the upstream
maintainer[1].

This version includes a commit of mine which allows for replacing the
local modifications done to the upstream files in git.git with macro
definitions to monkeypatch it in place.

It also brings in a change[2] upstream made for the breakage 2.13.0
introduced on SPARC and other platforms that forbid unaligned
access[3].

This means that the code customizations done since the initial import
in commit 28dc98e343 ("sha1dc: add collision-detecting sha1
implementation", 2017-03-16) can be done purely via Makefile
definitions and by including the content of our own sha1dc_git.[ch] in
sha1dc/sha1.c via a macro.

1. https://github.com/cr-marcstevens/sha1collisiondetection/commit/cc465543b310e5f59a1d534381690052e8509b22
2. https://github.com/cr-marcstevens/sha1collisiondetection/commit/33a694a9ee1b79c24be45f9eab5ac0e1aeeaf271
3. "Git 2.13.0 segfaults on Solaris SPARC due to DC_SHA1=YesPlease
   being on by default"
   (https://public-inbox.org/git/CACBZZX6nmKK8af0-UpjCKWV4R+hV-uk2xWXVA5U+_UQ3VXU03g@mail.gmail.com/)

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 Makefile           |  9 +++++-
 sha1dc/sha1.c      | 91 +++++++++++++++++++++++++++++++++++-------------------
 sha1dc/sha1.h      | 90 +++++++++++++++++++++++------------------------------
 sha1dc/ubc_check.c | 13 ++++++--
 sha1dc/ubc_check.h | 14 +++++++--
 sha1dc_git.c       | 24 ++++++++++++++
 sha1dc_git.h       | 19 ++++++++++++
 7 files changed, 172 insertions(+), 88 deletions(-)
 create mode 100644 sha1dc_git.c
 create mode 100644 sha1dc_git.h

diff --git a/Makefile b/Makefile
index e35542e631..ffa6da71b7 100644
--- a/Makefile
+++ b/Makefile
@@ -1414,7 +1414,14 @@ else
 	DC_SHA1 := YesPlease
 	LIB_OBJS += sha1dc/sha1.o
 	LIB_OBJS += sha1dc/ubc_check.o
-	BASIC_CFLAGS += -DSHA1_DC
+	BASIC_CFLAGS += \
+		-DSHA1_DC \
+		-DSHA1DC_NO_STANDARD_INCLUDES \
+		-DSHA1DC_INIT_SAFE_HASH_DEFAULT=0 \
+		-DSHA1DC_CUSTOM_INCLUDE_SHA1_C="\"cache.h\"" \
+		-DSHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_C="\"sha1dc_git.c\"" \
+		-DSHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H="\"sha1dc_git.h\"" \
+		-DSHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C="\"git-compat-util.h\""
 endif
 endif
 endif
diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
index 35e9dd5bf4..3dff80ac72 100644
--- a/sha1dc/sha1.c
+++ b/sha1dc/sha1.c
@@ -5,9 +5,23 @@
 * https://opensource.org/licenses/MIT
 ***/
 
-#include "cache.h"
-#include "sha1dc/sha1.h"
-#include "sha1dc/ubc_check.h"
+#ifndef SHA1DC_NO_STANDARD_INCLUDES
+#include <string.h>
+#include <memory.h>
+#include <stdio.h>
+#include <stdlib.h>
+#endif
+
+#ifdef SHA1DC_CUSTOM_INCLUDE_SHA1_C
+#include SHA1DC_CUSTOM_INCLUDE_SHA1_C
+#endif
+
+#ifndef SHA1DC_INIT_SAFE_HASH_DEFAULT
+#define SHA1DC_INIT_SAFE_HASH_DEFAULT 1
+#endif
+
+#include "sha1.h"
+#include "ubc_check.h"
 
 
 /*
@@ -18,16 +32,31 @@
    If you are compiling on a big endian platform and your compiler does not define one of these,
    you will have to add whatever macros your tool chain defines to indicate Big-Endianness.
  */
-#if (defined(__BYTE_ORDER) && (__BYTE_ORDER == __BIG_ENDIAN)) || \
+#ifdef SHA1DC_BIGENDIAN
+#undef SHA1DC_BIGENDIAN
+#endif
+#if (!defined SHA1DC_FORCE_LITTLEENDIAN) && \
+    ((defined(__BYTE_ORDER) && (__BYTE_ORDER == __BIG_ENDIAN)) || \
     (defined(__BYTE_ORDER__) && (__BYTE_ORDER__ == __BIG_ENDIAN__)) || \
-    defined(__BIG_ENDIAN__) || defined(__ARMEB__) || defined(__THUMBEB__) ||  defined(__AARCH64EB__) || \
-    defined(_MIPSEB) || defined(__MIPSEB) || defined(__MIPSEB__)
+    defined(_BIG_ENDIAN) || defined(__BIG_ENDIAN__) || defined(__ARMEB__) || defined(__THUMBEB__) ||  defined(__AARCH64EB__) || \
+    defined(_MIPSEB) || defined(__MIPSEB) || defined(__MIPSEB__) || defined(SHA1DC_FORCE_BIGENDIAN))
+
+#define SHA1DC_BIGENDIAN
 
-#define SHA1DC_BIGENDIAN	1
-#else
-#undef SHA1DC_BIGENDIAN
 #endif /*ENDIANNESS SELECTION*/
 
+#if (defined SHA1DC_FORCE_UNALIGNED_ACCESS || \
+     defined(__amd64__) || defined(__amd64) || defined(__x86_64__) || defined(__x86_64) || \
+     defined(i386) || defined(__i386) || defined(__i386__) || defined(__i486__)  || \
+     defined(__i586__) || defined(__i686__) || defined(_M_IX86) || defined(__X86__) || \
+     defined(_X86_) || defined(__THW_INTEL__) || defined(__I86__) || defined(__INTEL__) || \
+     defined(__386) || defined(_M_X64) || defined(_M_AMD64))
+
+#define SHA1DC_ALLOW_UNALIGNED_ACCESS
+
+#endif /*UNALIGNMENT DETECTION*/
+
+
 #define rotate_right(x,n) (((x)>>(n))|((x)<<(32-(n))))
 #define rotate_left(x,n)  (((x)<<(n))|((x)>>(32-(n))))
 
@@ -36,11 +65,11 @@
 
 #define sha1_mix(W, t)  (rotate_left(W[t - 3] ^ W[t - 8] ^ W[t - 14] ^ W[t - 16], 1))
 
-#if defined(SHA1DC_BIGENDIAN)
+#ifdef SHA1DC_BIGENDIAN
 	#define sha1_load(m, t, temp)  { temp = m[t]; }
 #else
 	#define sha1_load(m, t, temp)  { temp = m[t]; sha1_bswap32(temp); }
-#endif /* !defined(SHA1DC_BIGENDIAN) */
+#endif
 
 #define sha1_store(W, t, x)	*(volatile uint32_t *)&W[t] = x
 
@@ -869,6 +898,11 @@ static void sha1recompress_fast_ ## t (uint32_t ihvin[5], uint32_t ihvout[5], co
 	ihvout[0] = ihvin[0] + a; ihvout[1] = ihvin[1] + b; ihvout[2] = ihvin[2] + c; ihvout[3] = ihvin[3] + d; ihvout[4] = ihvin[4] + e; \
 }
 
+#ifdef _MSC_VER
+#pragma warning(push)
+#pragma warning(disable: 4127)  /* Complier complains about the checks in the above macro being constant. */
+#endif
+
 #ifdef DOSTORESTATE0
 SHA1_RECOMPRESS(0)
 #endif
@@ -1189,6 +1223,10 @@ SHA1_RECOMPRESS(78)
 SHA1_RECOMPRESS(79)
 #endif
 
+#ifdef _MSC_VER
+#pragma warning(pop)
+#endif
+
 static void sha1_recompression_step(uint32_t step, uint32_t ihvin[5], uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5])
 {
 	switch (step)
@@ -1662,7 +1700,7 @@ void SHA1DCInit(SHA1_CTX* ctx)
 	ctx->ihv[3] = 0x10325476;
 	ctx->ihv[4] = 0xC3D2E1F0;
 	ctx->found_collision = 0;
-	ctx->safe_hash = 0;
+	ctx->safe_hash = SHA1DC_INIT_SAFE_HASH_DEFAULT;
 	ctx->ubc_check = 1;
 	ctx->detect_coll = 1;
 	ctx->reduced_round_coll = 0;
@@ -1710,6 +1748,7 @@ void SHA1DCSetCallback(SHA1_CTX* ctx, collision_block_callback callback)
 void SHA1DCUpdate(SHA1_CTX* ctx, const char* buf, size_t len)
 {
 	unsigned left, fill;
+
 	if (len == 0)
 		return;
 
@@ -1728,7 +1767,13 @@ void SHA1DCUpdate(SHA1_CTX* ctx, const char* buf, size_t len)
 	while (len >= 64)
 	{
 		ctx->total += 64;
+
+#if defined(SHA1DC_ALLOW_UNALIGNED_ACCESS)
 		sha1_process(ctx, (uint32_t*)(buf));
+#else
+		memcpy(ctx->buffer, buf, 64);
+		sha1_process(ctx, (uint32_t*)(ctx->buffer));
+#endif /* defined(SHA1DC_ALLOW_UNALIGNED_ACCESS) */
 		buf += 64;
 		len -= 64;
 	}
@@ -1788,22 +1833,6 @@ int SHA1DCFinal(unsigned char output[20], SHA1_CTX *ctx)
 	return ctx->found_collision;
 }
 
-void git_SHA1DCFinal(unsigned char hash[20], SHA1_CTX *ctx)
-{
-	if (!SHA1DCFinal(hash, ctx))
-		return;
-	die("SHA-1 appears to be part of a collision attack: %s",
-	    sha1_to_hex(hash));
-}
-
-void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *vdata, unsigned long len)
-{
-	const char *data = vdata;
-	/* We expect an unsigned long, but sha1dc only takes an int */
-	while (len > INT_MAX) {
-		SHA1DCUpdate(ctx, data, INT_MAX);
-		data += INT_MAX;
-		len -= INT_MAX;
-	}
-	SHA1DCUpdate(ctx, data, len);
-}
+#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_C
+#include SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_C
+#endif
diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
index bd8bd928fb..1e4e94be54 100644
--- a/sha1dc/sha1.h
+++ b/sha1dc/sha1.h
@@ -4,6 +4,7 @@
 * See accompanying file LICENSE.txt or copy at
 * https://opensource.org/licenses/MIT
 ***/
+
 #ifndef SHA1DC_SHA1_H
 #define SHA1DC_SHA1_H
 
@@ -11,36 +12,30 @@
 extern "C" {
 #endif
 
-/* uses SHA-1 message expansion to expand the first 16 words of W[] to 80 words */
-/* void sha1_message_expansion(uint32_t W[80]); */
-
-/* sha-1 compression function; first version takes a message block pre-parsed as 16 32-bit integers, second version takes an already expanded message) */
-/* void sha1_compression(uint32_t ihv[5], const uint32_t m[16]);
-void sha1_compression_W(uint32_t ihv[5], const uint32_t W[80]); */
+#ifndef SHA1DC_NO_STANDARD_INCLUDES
+#include <stdint.h>
+#endif
 
-/* same as sha1_compression_W, but additionally store intermediate states */
+/* sha-1 compression function that takes an already expanded message, and additionally store intermediate states */
 /* only stores states ii (the state between step ii-1 and step ii) when DOSTORESTATEii is defined in ubc_check.h */
 void sha1_compression_states(uint32_t[5], const uint32_t[16], uint32_t[80], uint32_t[80][5]);
 
 /*
-// function type for sha1_recompression_step_T (uint32_t ihvin[5], uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5])
-// where 0 <= T < 80
-//       me2 is an expanded message (the expansion of an original message block XOR'ed with a disturbance vector's message block difference)
-//       state is the internal state (a,b,c,d,e) before step T of the SHA-1 compression function while processing the original message block
-// the function will return:
-//       ihvin: the reconstructed input chaining value
-//       ihvout: the reconstructed output chaining value
+// Function type for sha1_recompression_step_T (uint32_t ihvin[5], uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5]).
+// Where 0 <= T < 80
+//       me2 is an expanded message (the expansion of an original message block XOR'ed with a disturbance vector's message block difference.)
+//       state is the internal state (a,b,c,d,e) before step T of the SHA-1 compression function while processing the original message block.
+// The function will return:
+//       ihvin: The reconstructed input chaining value.
+//       ihvout: The reconstructed output chaining value.
 */
 typedef void(*sha1_recompression_type)(uint32_t*, uint32_t*, const uint32_t*, const uint32_t*);
 
-/* table of sha1_recompression_step_0, ... , sha1_recompression_step_79 */
-/* extern sha1_recompression_type sha1_recompression_step[80];*/
-
-/* a callback function type that can be set to be called when a collision block has been found: */
+/* A callback function type that can be set to be called when a collision block has been found: */
 /* void collision_block_callback(uint64_t byteoffset, const uint32_t ihvin1[5], const uint32_t ihvin2[5], const uint32_t m1[80], const uint32_t m2[80]) */
 typedef void(*collision_block_callback)(uint64_t, const uint32_t*, const uint32_t*, const uint32_t*, const uint32_t*);
 
-/* the SHA-1 context */
+/* The SHA-1 context. */
 typedef struct {
 	uint64_t total;
 	uint32_t ihv[5];
@@ -59,30 +54,34 @@ typedef struct {
 	uint32_t states[80][5];
 } SHA1_CTX;
 
-/* initialize SHA-1 context */
+/* Initialize SHA-1 context. */
 void SHA1DCInit(SHA1_CTX*);
 
 /*
-// function to enable safe SHA-1 hashing:
-// collision attacks are thwarted by hashing a detected near-collision block 3 times
-// think of it as extending SHA-1 from 80-steps to 240-steps for such blocks:
-//   the best collision attacks against SHA-1 have complexity about 2^60,
-//   thus for 240-steps an immediate lower-bound for the best cryptanalytic attacks would 2^180
-//   an attacker would be better off using a generic birthday search of complexity 2^80
-//
-// enabling safe SHA-1 hashing will result in the correct SHA-1 hash for messages where no collision attack was detected
-// but it will result in a different SHA-1 hash for messages where a collision attack was detected
-// this will automatically invalidate SHA-1 based digital signature forgeries
-// enabled by default
+    Function to enable safe SHA-1 hashing:
+    Collision attacks are thwarted by hashing a detected near-collision block 3 times.
+    Think of it as extending SHA-1 from 80-steps to 240-steps for such blocks:
+        The best collision attacks against SHA-1 have complexity about 2^60,
+        thus for 240-steps an immediate lower-bound for the best cryptanalytic attacks would be 2^180.
+        An attacker would be better off using a generic birthday search of complexity 2^80.
+
+   Enabling safe SHA-1 hashing will result in the correct SHA-1 hash for messages where no collision attack was detected,
+   but it will result in a different SHA-1 hash for messages where a collision attack was detected.
+   This will automatically invalidate SHA-1 based digital signature forgeries.
+   Enabled by default.
 */
 void SHA1DCSetSafeHash(SHA1_CTX*, int);
 
-/* function to disable or enable the use of Unavoidable Bitconditions (provides a significant speed up) */
-/* enabled by default */
+/*
+    Function to disable or enable the use of Unavoidable Bitconditions (provides a significant speed up).
+    Enabled by default
+ */
 void SHA1DCSetUseUBC(SHA1_CTX*, int);
 
-/* function to disable or enable the use of Collision Detection */
-/* enabled by default */
+/*
+    Function to disable or enable the use of Collision Detection.
+    Enabled by default.
+ */
 void SHA1DCSetUseDetectColl(SHA1_CTX*, int);
 
 /* function to disable or enable the detection of reduced-round SHA-1 collisions */
@@ -100,23 +99,12 @@ void SHA1DCUpdate(SHA1_CTX*, const char*, size_t);
 /* returns: 0 = no collision detected, otherwise = collision found => warn user for active attack */
 int  SHA1DCFinal(unsigned char[20], SHA1_CTX*);
 
-/*
- * Same as SHA1DCFinal, but convert collision attack case into a verbose die().
- */
-void git_SHA1DCFinal(unsigned char [20], SHA1_CTX *);
-
-/*
- * Same as SHA1DCUpdate, but adjust types to match git's usual interface.
- */
-void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *data, unsigned long len);
-
-#define platform_SHA_CTX SHA1_CTX
-#define platform_SHA1_Init SHA1DCInit
-#define platform_SHA1_Update git_SHA1DCUpdate
-#define platform_SHA1_Final git_SHA1DCFinal
-
 #if defined(__cplusplus)
 }
 #endif
 
-#endif /* SHA1DC_SHA1_H */
+#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H
+#include SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H
+#endif
+
+#endif
diff --git a/sha1dc/ubc_check.c b/sha1dc/ubc_check.c
index 089dd4743d..b3beff2afb 100644
--- a/sha1dc/ubc_check.c
+++ b/sha1dc/ubc_check.c
@@ -24,8 +24,13 @@
 // ubc_check has been verified against ubc_check_verify using the 'ubc_check_test' program in the tools section
 */
 
-#include "git-compat-util.h"
-#include "sha1dc/ubc_check.h"
+#ifndef SHA1DC_NO_STANDARD_INCLUDES
+#include <stdint.h>
+#endif
+#ifdef SHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C
+#include SHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C
+#endif
+#include "ubc_check.h"
 
 static const uint32_t DV_I_43_0_bit 	= (uint32_t)(1) << 0;
 static const uint32_t DV_I_44_0_bit 	= (uint32_t)(1) << 1;
@@ -361,3 +366,7 @@ if (mask) {
 
 	dvmask[0]=mask;
 }
+
+#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_C
+#include SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_C
+#endif
diff --git a/sha1dc/ubc_check.h b/sha1dc/ubc_check.h
index b64c306d77..d7e17dc734 100644
--- a/sha1dc/ubc_check.h
+++ b/sha1dc/ubc_check.h
@@ -20,13 +20,17 @@
 // thus one needs to do the recompression check for each DV that has its bit set
 */
 
-#ifndef UBC_CHECK_H
-#define UBC_CHECK_H
+#ifndef SHA1DC_UBC_CHECK_H
+#define SHA1DC_UBC_CHECK_H
 
 #if defined(__cplusplus)
 extern "C" {
 #endif
 
+#ifndef SHA1DC_NO_STANDARD_INCLUDES
+#include <stdint.h>
+#endif
+
 #define DVMASKSIZE 1
 typedef struct { int dvType; int dvK; int dvB; int testt; int maski; int maskb; uint32_t dm[80]; } dv_info_t;
 extern dv_info_t sha1_dvs[];
@@ -41,4 +45,8 @@ void ubc_check(const uint32_t W[80], uint32_t dvmask[DVMASKSIZE]);
 }
 #endif
 
-#endif /* UBC_CHECK_H */
+#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_H
+#include SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_H
+#endif
+
+#endif
diff --git a/sha1dc_git.c b/sha1dc_git.c
new file mode 100644
index 0000000000..4d32b4f77e
--- /dev/null
+++ b/sha1dc_git.c
@@ -0,0 +1,24 @@
+/*
+ * This code is included at the end of sha1dc/sha1.c with the
+ * SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_C macro.
+ */
+
+void git_SHA1DCFinal(unsigned char hash[20], SHA1_CTX *ctx)
+{
+	if (!SHA1DCFinal(hash, ctx))
+		return;
+	die("SHA-1 appears to be part of a collision attack: %s",
+	    sha1_to_hex(hash));
+}
+
+void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *vdata, unsigned long len)
+{
+	const char *data = vdata;
+	/* We expect an unsigned long, but sha1dc only takes an int */
+	while (len > INT_MAX) {
+		SHA1DCUpdate(ctx, data, INT_MAX);
+		data += INT_MAX;
+		len -= INT_MAX;
+	}
+	SHA1DCUpdate(ctx, data, len);
+}
diff --git a/sha1dc_git.h b/sha1dc_git.h
new file mode 100644
index 0000000000..a8a5c1da16
--- /dev/null
+++ b/sha1dc_git.h
@@ -0,0 +1,19 @@
+/*
+ * This code is included at the end of sha1dc/sha1.h with the
+ * SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H macro.
+ */
+
+/*
+ * Same as SHA1DCFinal, but convert collision attack case into a verbose die().
+ */
+void git_SHA1DCFinal(unsigned char [20], SHA1_CTX *);
+
+/*
+ * Same as SHA1DCUpdate, but adjust types to match git's usual interface.
+ */
+void git_SHA1DCUpdate(SHA1_CTX *ctx, const void *data, unsigned long len);
+
+#define platform_SHA_CTX SHA1_CTX
+#define platform_SHA1_Init SHA1DCInit
+#define platform_SHA1_Update git_SHA1DCUpdate
+#define platform_SHA1_Final git_SHA1DCFinal
-- 
2.13.0.303.g4ebf302169

[PATCH v2 2/2] sha1dc: optionally use sha1collisiondetection as a submodule

[Ævar Arnfjörð Bjarmason]

Add an option to use the sha1collisiondetection library from the
submodule in sha1collisiondetection/ instead of in the copy in the
sha1dc/ directory.

This allows us to try out the submodule in sha1collisiondetection
without breaking the build for anyone who's not expecting them as we
work out any kinks.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 .gitmodules            |  4 ++++
 Makefile               | 12 ++++++++++++
 hash.h                 |  4 ++++
 sha1collisiondetection |  1 +
 4 files changed, 21 insertions(+)
 create mode 100644 .gitmodules
 create mode 160000 sha1collisiondetection

diff --git a/.gitmodules b/.gitmodules
new file mode 100644
index 0000000000..cbeebdab7a
--- /dev/null
+++ b/.gitmodules
@@ -0,0 +1,4 @@
+[submodule "sha1collisiondetection"]
+	path = sha1collisiondetection
+	url = https://github.com/cr-marcstevens/sha1collisiondetection.git
+	branch = master
diff --git a/Makefile b/Makefile
index ffa6da71b7..6baad1669e 100644
--- a/Makefile
+++ b/Makefile
@@ -144,6 +144,12 @@ all::
 # algorithm. This is slower, but may detect attempted collision attacks.
 # Takes priority over other *_SHA1 knobs.
 #
+# Define DC_SHA1_SUBMODULE in addition to DC_SHA1 to use the
+# sha1collisiondetection shipped as a submodule instead of the
+# non-submodule copy in sha1dc/. This is an experimental option used
+# by the git project to migrate to using sha1collisiondetection as a
+# submodule.
+#
 # Define OPENSSL_SHA1 environment variable when running make to link
 # with the SHA1 routine from openssl library.
 #
@@ -1412,8 +1418,14 @@ ifdef APPLE_COMMON_CRYPTO
 	BASIC_CFLAGS += -DSHA1_APPLE
 else
 	DC_SHA1 := YesPlease
+ifdef DC_SHA1_SUBMODULE
+	LIB_OBJS += sha1collisiondetection/lib/sha1.o
+	LIB_OBJS += sha1collisiondetection/lib/ubc_check.o
+	BASIC_CFLAGS += -DDC_SHA1_SUBMODULE
+else
 	LIB_OBJS += sha1dc/sha1.o
 	LIB_OBJS += sha1dc/ubc_check.o
+endif
 	BASIC_CFLAGS += \
 		-DSHA1_DC \
 		-DSHA1DC_NO_STANDARD_INCLUDES \
diff --git a/hash.h b/hash.h
index a11fc9233f..bef3e630a0 100644
--- a/hash.h
+++ b/hash.h
@@ -8,7 +8,11 @@
 #elif defined(SHA1_OPENSSL)
 #include <openssl/sha.h>
 #elif defined(SHA1_DC)
+#ifdef DC_SHA1_SUBMODULE
+#include "sha1collisiondetection/lib/sha1.h"
+#else
 #include "sha1dc/sha1.h"
+#endif
 #else /* SHA1_BLK */
 #include "block-sha1/sha1.h"
 #endif
diff --git a/sha1collisiondetection b/sha1collisiondetection
new file mode 160000
index 0000000000..cc465543b3
--- /dev/null
+++ b/sha1collisiondetection
@@ -0,0 +1 @@
+Subproject commit cc465543b310e5f59a1d534381690052e8509b22
-- 
2.13.0.303.g4ebf302169

Re: [PATCH v2 2/2] sha1dc: optionally use sha1collisiondetection as a submodule

[Junio C Hamano]

Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:

> +# Define DC_SHA1_SUBMODULE in addition to DC_SHA1 to use the
> +# sha1collisiondetection shipped as a submodule instead of the
> +# non-submodule copy in sha1dc/. This is an experimental option used
> +# by the git project to migrate to using sha1collisiondetection as a
> +# submodule.
> +#

Yup, thanks.

I actually was envisioning something like this instead, though.

diff --git a/Makefile b/Makefile
index 6baad1669e..8d33936a12 100644
--- a/Makefile
+++ b/Makefile
@@ -989,6 +989,10 @@ EXTLIBS =
 
 GIT_USER_AGENT = git/$(GIT_VERSION)
 
+ifeq ($(wildcard sha1collisiondetection/lib/sha1.h),sha1collisiondetection/lib/sha1.h)
+DC_SHA1_SUBMODULE = auto
+endif
+
 include config.mak.uname
 -include config.mak.autogen
 -include config.mak

That way, a user can say "git submodule init/update" it to use it,
and deinit it to use the frozen version.

But when somebody (like me?) feels strongly enough, such a change
can always come on top of this patch, so let's have this
manual-configuration-only version as our first step.

Thanks.

Re: [PATCH v2 2/2] sha1dc: optionally use sha1collisiondetection as a submodule

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> But when somebody (like me?) feels strongly enough, such a change
> can always come on top of this patch, so let's have this
> manual-configuration-only version as our first step.

Just so that I have something I can come back to, here it is with a
log message.

-- >8 --
Subject: [PATCH] sha1collisiondetection: automatically enable when submodule is populated

If a user wants to experiment with the version of collision
detecting sha1 from the submodule, the user needed to not just
populate the submodule but also needed to turn the knob.

A Makefile trick is easy enough to do so, so let's do this.  When
somebody with a copy of the submodule populated wants not to use it,
that can be done by overriding it in config.mak or from the command
line, e.g. "make DC_SHA1_SUBMODULE= all".

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 Makefile | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/Makefile b/Makefile
index 6baad1669e..8d33936a12 100644
--- a/Makefile
+++ b/Makefile
@@ -989,6 +989,10 @@ EXTLIBS =
 
 GIT_USER_AGENT = git/$(GIT_VERSION)
 
+ifeq ($(wildcard sha1collisiondetection/lib/sha1.h),sha1collisiondetection/lib/sha1.h)
+DC_SHA1_SUBMODULE = auto
+endif
+
 include config.mak.uname
 -include config.mak.autogen
 -include config.mak
-- 
2.13.0-440-g3ce6d2d5b8

Re: [PATCH v2 2/2] sha1dc: optionally use sha1collisiondetection as a submodule

[Ævar Arnfjörð Bjarmason]

On Mon, May 22, 2017 at 4:48 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Junio C Hamano <gitster@pobox.com> writes:
>
>> But when somebody (like me?) feels strongly enough, such a change
>> can always come on top of this patch, so let's have this
>> manual-configuration-only version as our first step.
>
> Just so that I have something I can come back to, here it is with a
> log message.
>
> -- >8 --
> Subject: [PATCH] sha1collisiondetection: automatically enable when submodule is populated
>
> If a user wants to experiment with the version of collision
> detecting sha1 from the submodule, the user needed to not just
> populate the submodule but also needed to turn the knob.
>
> A Makefile trick is easy enough to do so, so let's do this.  When
> somebody with a copy of the submodule populated wants not to use it,
> that can be done by overriding it in config.mak or from the command
> line, e.g. "make DC_SHA1_SUBMODULE= all".
>
> Signed-off-by: Junio C Hamano <gitster@pobox.com>
> ---
>  Makefile | 4 ++++
>  1 file changed, 4 insertions(+)
>
> diff --git a/Makefile b/Makefile
> index 6baad1669e..8d33936a12 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -989,6 +989,10 @@ EXTLIBS =
>
>  GIT_USER_AGENT = git/$(GIT_VERSION)
>
> +ifeq ($(wildcard sha1collisiondetection/lib/sha1.h),sha1collisiondetection/lib/sha1.h)
> +DC_SHA1_SUBMODULE = auto
> +endif
> +
>  include config.mak.uname
>  -include config.mak.autogen
>  -include config.mak


I thought this should have something like this:

diff --git a/Makefile b/Makefile
index 8d33936a12..bbcac648a4 100644
--- a/Makefile
+++ b/Makefile
@@ -989,9 +989,11 @@ EXTLIBS =

 GIT_USER_AGENT = git/$(GIT_VERSION)

+ifndef DC_SHA1_SUBMODULE
 ifeq ($(wildcard
sha1collisiondetection/lib/sha1.h),sha1collisiondetection/lib/sha1.h)
 DC_SHA1_SUBMODULE = auto
 endif
+endif

 include config.mak.uname
 -include config.mak.autogen

I.e. so using sha1dc via DC_SHA1_SUBMODULE= even with the submodule
checked-out would work, but experimenting with it now that seems to do
the right thing, even though this is set unconditionally. There must
be some Makefile magic I'm missing here.

But in any case it would make sense to squash something like this into
your patch:

diff --git a/Makefile b/Makefile
index 8d33936a12..4d9c49ae17 100644
--- a/Makefile
+++ b/Makefile
@@ -148,7 +148,8 @@ all::
 # sha1collisiondetection shipped as a submodule instead of the
 # non-submodule copy in sha1dc/. This is an experimental option used
 # by the git project to migrate to using sha1collisiondetection as a
-# submodule.
+# submodule. Supplied implicitly if the sha1collisiondetection/
+# directory is found to be populated.
 #
 # Define OPENSSL_SHA1 environment variable when running make to link
 # with the SHA1 routine from openssl library.

Re: [PATCH v2 2/2] sha1dc: optionally use sha1collisiondetection as a submodule

[Junio C Hamano]

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

> I thought this should have something like this:
> ...
> the right thing, even though this is set unconditionally. There must
> be some Makefile magic I'm missing here.

The magic you are missing is that to ifdef in $(MAKE), a variable
that is not mentioned (undefined) and set to empty string are both
the same.  You'll fall into its else clause.

> But in any case it would make sense to squash something like this into
> your patch:
>
> diff --git a/Makefile b/Makefile
> index 8d33936a12..4d9c49ae17 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -148,7 +148,8 @@ all::
>  # sha1collisiondetection shipped as a submodule instead of the
>  # non-submodule copy in sha1dc/. This is an experimental option used
>  # by the git project to migrate to using sha1collisiondetection as a
> -# submodule.
> +# submodule. Supplied implicitly if the sha1collisiondetection/
> +# directory is found to be populated.

Yeah, if it is populated, defaults to true, if it is not, defaults
to false.  Either case can be overriden from the command line or
config.mak

Re: [PATCH 2/3] sha1dc: use sha1collisiondetection as a submodule

[Ævar Arnfjörð Bjarmason]

On Sat, May 20, 2017 at 1:13 PM, Junio C Hamano <gitster@pobox.com> wrote:
> Ævar Arnfjörð Bjarmason  <avarab@gmail.com> writes:
>
>> Replace the forked sha1dc directory with a copy of the upstream code
>> imported as a submodule. This is the exact same code as now exists in
>> the sha1dc/ directory.
>>
>> The initial reason for copy/pasting the code into sha1dc and locally
>> modifying it was that it needed to be altered to work with the git
>> project.
>>
>> The upstream project has accepted my code changes to allow us to use
>> their code as-is, see the preceding commit for details. So import the
>> code as a submodule instead, this will make it easier to keep
>> up-to-date with any upstream fixes or improvements.
>>
>> Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
>> ---
>>  .gitmodules            | 4 ++++
>>  Makefile               | 4 ++--
>>  hash.h                 | 2 +-
>>  sha1collisiondetection | 1 +
>>  4 files changed, 8 insertions(+), 3 deletions(-)
>>  create mode 100644 .gitmodules
>>  create mode 160000 sha1collisiondetection
>
> I am not sure how prepared our .travis.yml is to deal with a
> submodule, I'd prefer to have this step broken down to two step
> process.

I've since sent a v2 of this which addresses this by being more
careful, but since then I found these Travis docs that seem to
indicate that cloning the submodule will Just Work:
https://docs.travis-ci.com/user/common-build-problems/#Git-Submodules-are-not-updated-correctly

[PATCH 3/3] sha1dc: remove the unused sha1dc/ directory

[Ævar Arnfjörð Bjarmason]

This has been made obsolete by the sha1collisiondetection
submodule. See the preceding change for details.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 sha1dc/LICENSE.txt |  30 -----
 sha1dc/sha1.h      | 110 ----------------
 sha1dc/ubc_check.c | 372 -----------------------------------------------------
 sha1dc/ubc_check.h |  52 --------
 4 files changed, 564 deletions(-)
 delete mode 100644 sha1dc/LICENSE.txt
 delete mode 100644 sha1dc/sha1.h
 delete mode 100644 sha1dc/ubc_check.c
 delete mode 100644 sha1dc/ubc_check.h

diff --git a/sha1dc/LICENSE.txt b/sha1dc/LICENSE.txt
deleted file mode 100644
index 4a3e6a1b15..0000000000
--- a/sha1dc/LICENSE.txt
+++ /dev/null
@@ -1,30 +0,0 @@
-MIT License
-
-Copyright (c) 2017:
-    Marc Stevens
-    Cryptology Group
-    Centrum Wiskunde & Informatica
-    P.O. Box 94079, 1090 GB Amsterdam, Netherlands
-    marc@marc-stevens.nl
-
-    Dan Shumow
-    Microsoft Research
-    danshu@microsoft.com
-
-Permission is hereby granted, free of charge, to any person obtaining a copy
-of this software and associated documentation files (the "Software"), to deal
-in the Software without restriction, including without limitation the rights
-to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the Software is
-furnished to do so, subject to the following conditions:
-
-The above copyright notice and this permission notice shall be included in all
-copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
-AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
-LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
-OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
-SOFTWARE.
diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
deleted file mode 100644
index dd41b0a5a6..0000000000
--- a/sha1dc/sha1.h
+++ /dev/null
@@ -1,110 +0,0 @@
-/***
-* Copyright 2017 Marc Stevens <marc@marc-stevens.nl>, Dan Shumow <danshu@microsoft.com>
-* Distributed under the MIT Software License.
-* See accompanying file LICENSE.txt or copy at
-* https://opensource.org/licenses/MIT
-***/
-
-#ifndef SHA1DC_SHA1_H
-#define SHA1DC_SHA1_H
-
-#if defined(__cplusplus)
-extern "C" {
-#endif
-
-#ifndef SHA1DC_NO_STANDARD_INCLUDES
-#include <stdint.h>
-#endif
-
-/* sha-1 compression function that takes an already expanded message, and additionally store intermediate states */
-/* only stores states ii (the state between step ii-1 and step ii) when DOSTORESTATEii is defined in ubc_check.h */
-void sha1_compression_states(uint32_t[5], const uint32_t[16], uint32_t[80], uint32_t[80][5]);
-
-/*
-// Function type for sha1_recompression_step_T (uint32_t ihvin[5], uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5]).
-// Where 0 <= T < 80
-//       me2 is an expanded message (the expansion of an original message block XOR'ed with a disturbance vector's message block difference.)
-//       state is the internal state (a,b,c,d,e) before step T of the SHA-1 compression function while processing the original message block.
-// The function will return:
-//       ihvin: The reconstructed input chaining value.
-//       ihvout: The reconstructed output chaining value.
-*/
-typedef void(*sha1_recompression_type)(uint32_t*, uint32_t*, const uint32_t*, const uint32_t*);
-
-/* A callback function type that can be set to be called when a collision block has been found: */
-/* void collision_block_callback(uint64_t byteoffset, const uint32_t ihvin1[5], const uint32_t ihvin2[5], const uint32_t m1[80], const uint32_t m2[80]) */
-typedef void(*collision_block_callback)(uint64_t, const uint32_t*, const uint32_t*, const uint32_t*, const uint32_t*);
-
-/* The SHA-1 context. */
-typedef struct {
-	uint64_t total;
-	uint32_t ihv[5];
-	unsigned char buffer[64];
-	int found_collision;
-	int safe_hash;
-	int detect_coll;
-	int ubc_check;
-	int reduced_round_coll;
-	collision_block_callback callback;
-
-	uint32_t ihv1[5];
-	uint32_t ihv2[5];
-	uint32_t m1[80];
-	uint32_t m2[80];
-	uint32_t states[80][5];
-} SHA1_CTX;
-
-/* Initialize SHA-1 context. */
-void SHA1DCInit(SHA1_CTX*);
-
-/*
-    Function to enable safe SHA-1 hashing:
-    Collision attacks are thwarted by hashing a detected near-collision block 3 times.
-    Think of it as extending SHA-1 from 80-steps to 240-steps for such blocks:
-        The best collision attacks against SHA-1 have complexity about 2^60,
-        thus for 240-steps an immediate lower-bound for the best cryptanalytic attacks would be 2^180.
-        An attacker would be better off using a generic birthday search of complexity 2^80.
-  
-   Enabling safe SHA-1 hashing will result in the correct SHA-1 hash for messages where no collision attack was detected,
-   but it will result in a different SHA-1 hash for messages where a collision attack was detected.
-   This will automatically invalidate SHA-1 based digital signature forgeries.
-   Enabled by default.
-*/
-void SHA1DCSetSafeHash(SHA1_CTX*, int);
-
-/*
-    Function to disable or enable the use of Unavoidable Bitconditions (provides a significant speed up).
-    Enabled by default
- */
-void SHA1DCSetUseUBC(SHA1_CTX*, int);
-
-/*
-    Function to disable or enable the use of Collision Detection.
-    Enabled by default.
- */
-void SHA1DCSetUseDetectColl(SHA1_CTX*, int);
-
-/* function to disable or enable the detection of reduced-round SHA-1 collisions */
-/* disabled by default */
-void SHA1DCSetDetectReducedRoundCollision(SHA1_CTX*, int);
-
-/* function to set a callback function, pass NULL to disable */
-/* by default no callback set */
-void SHA1DCSetCallback(SHA1_CTX*, collision_block_callback);
-
-/* update SHA-1 context with buffer contents */
-void SHA1DCUpdate(SHA1_CTX*, const char*, size_t);
-
-/* obtain SHA-1 hash from SHA-1 context */
-/* returns: 0 = no collision detected, otherwise = collision found => warn user for active attack */
-int  SHA1DCFinal(unsigned char[20], SHA1_CTX*); 
-
-#if defined(__cplusplus)
-}
-#endif
-
-#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H
-#include SHA1DC_CUSTOM_TRAILING_INCLUDE_SHA1_H
-#endif
-
-#endif
diff --git a/sha1dc/ubc_check.c b/sha1dc/ubc_check.c
deleted file mode 100644
index b3beff2afb..0000000000
--- a/sha1dc/ubc_check.c
+++ /dev/null
@@ -1,372 +0,0 @@
-/***
-* Copyright 2017 Marc Stevens <marc@marc-stevens.nl>, Dan Shumow <danshu@microsoft.com>
-* Distributed under the MIT Software License.
-* See accompanying file LICENSE.txt or copy at
-* https://opensource.org/licenses/MIT
-***/
-
-/*
-// this file was generated by the 'parse_bitrel' program in the tools section
-// using the data files from directory 'tools/data/3565'
-//
-// sha1_dvs contains a list of SHA-1 Disturbance Vectors (DV) to check
-// dvType, dvK and dvB define the DV: I(K,B) or II(K,B) (see the paper)
-// dm[80] is the expanded message block XOR-difference defined by the DV
-// testt is the step to do the recompression from for collision detection
-// maski and maskb define the bit to check for each DV in the dvmask returned by ubc_check
-//
-// ubc_check takes as input an expanded message block and verifies the unavoidable bitconditions for all listed DVs
-// it returns a dvmask where each bit belonging to a DV is set if all unavoidable bitconditions for that DV have been met
-// thus one needs to do the recompression check for each DV that has its bit set
-//
-// ubc_check is programmatically generated and the unavoidable bitconditions have been hardcoded
-// a directly verifiable version named ubc_check_verify can be found in ubc_check_verify.c
-// ubc_check has been verified against ubc_check_verify using the 'ubc_check_test' program in the tools section
-*/
-
-#ifndef SHA1DC_NO_STANDARD_INCLUDES
-#include <stdint.h>
-#endif
-#ifdef SHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C
-#include SHA1DC_CUSTOM_INCLUDE_UBC_CHECK_C
-#endif
-#include "ubc_check.h"
-
-static const uint32_t DV_I_43_0_bit 	= (uint32_t)(1) << 0;
-static const uint32_t DV_I_44_0_bit 	= (uint32_t)(1) << 1;
-static const uint32_t DV_I_45_0_bit 	= (uint32_t)(1) << 2;
-static const uint32_t DV_I_46_0_bit 	= (uint32_t)(1) << 3;
-static const uint32_t DV_I_46_2_bit 	= (uint32_t)(1) << 4;
-static const uint32_t DV_I_47_0_bit 	= (uint32_t)(1) << 5;
-static const uint32_t DV_I_47_2_bit 	= (uint32_t)(1) << 6;
-static const uint32_t DV_I_48_0_bit 	= (uint32_t)(1) << 7;
-static const uint32_t DV_I_48_2_bit 	= (uint32_t)(1) << 8;
-static const uint32_t DV_I_49_0_bit 	= (uint32_t)(1) << 9;
-static const uint32_t DV_I_49_2_bit 	= (uint32_t)(1) << 10;
-static const uint32_t DV_I_50_0_bit 	= (uint32_t)(1) << 11;
-static const uint32_t DV_I_50_2_bit 	= (uint32_t)(1) << 12;
-static const uint32_t DV_I_51_0_bit 	= (uint32_t)(1) << 13;
-static const uint32_t DV_I_51_2_bit 	= (uint32_t)(1) << 14;
-static const uint32_t DV_I_52_0_bit 	= (uint32_t)(1) << 15;
-static const uint32_t DV_II_45_0_bit 	= (uint32_t)(1) << 16;
-static const uint32_t DV_II_46_0_bit 	= (uint32_t)(1) << 17;
-static const uint32_t DV_II_46_2_bit 	= (uint32_t)(1) << 18;
-static const uint32_t DV_II_47_0_bit 	= (uint32_t)(1) << 19;
-static const uint32_t DV_II_48_0_bit 	= (uint32_t)(1) << 20;
-static const uint32_t DV_II_49_0_bit 	= (uint32_t)(1) << 21;
-static const uint32_t DV_II_49_2_bit 	= (uint32_t)(1) << 22;
-static const uint32_t DV_II_50_0_bit 	= (uint32_t)(1) << 23;
-static const uint32_t DV_II_50_2_bit 	= (uint32_t)(1) << 24;
-static const uint32_t DV_II_51_0_bit 	= (uint32_t)(1) << 25;
-static const uint32_t DV_II_51_2_bit 	= (uint32_t)(1) << 26;
-static const uint32_t DV_II_52_0_bit 	= (uint32_t)(1) << 27;
-static const uint32_t DV_II_53_0_bit 	= (uint32_t)(1) << 28;
-static const uint32_t DV_II_54_0_bit 	= (uint32_t)(1) << 29;
-static const uint32_t DV_II_55_0_bit 	= (uint32_t)(1) << 30;
-static const uint32_t DV_II_56_0_bit 	= (uint32_t)(1) << 31;
-
-dv_info_t sha1_dvs[] =
-{
-  {1,43,0,58,0,0, { 0x08000000,0x9800000c,0xd8000010,0x08000010,0xb8000010,0x98000000,0x60000000,0x00000008,0xc0000000,0x90000014,0x10000010,0xb8000014,0x28000000,0x20000010,0x48000000,0x08000018,0x60000000,0x90000010,0xf0000010,0x90000008,0xc0000000,0x90000010,0xf0000010,0xb0000008,0x40000000,0x90000000,0xf0000010,0x90000018,0x60000000,0x90000010,0x90000010,0x90000000,0x80000000,0x00000010,0xa0000000,0x20000000,0xa0000000,0x20000010,0x00000000,0x20000010,0x20000000,0x00000010,0x20000000,0x00000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000040,0x40000002,0x80000004,0x80000080,0x80000006,0x00000049,0x00000103,0x80000009,0x80000012,0x80000202,0x00000018,0x00000164,0x00000408,0x800000e6,0x8000004c,0x00000803,0x80000161,0x80000599 } }
-, {1,44,0,58,0,1, { 0xb4000008,0x08000000,0x9800000c,0xd8000010,0x08000010,0xb8000010,0x98000000,0x60000000,0x00000008,0xc0000000,0x90000014,0x10000010,0xb8000014,0x28000000,0x20000010,0x48000000,0x08000018,0x60000000,0x90000010,0xf0000010,0x90000008,0xc0000000,0x90000010,0xf0000010,0xb0000008,0x40000000,0x90000000,0xf0000010,0x90000018,0x60000000,0x90000010,0x90000010,0x90000000,0x80000000,0x00000010,0xa0000000,0x20000000,0xa0000000,0x20000010,0x00000000,0x20000010,0x20000000,0x00000010,0x20000000,0x00000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000040,0x40000002,0x80000004,0x80000080,0x80000006,0x00000049,0x00000103,0x80000009,0x80000012,0x80000202,0x00000018,0x00000164,0x00000408,0x800000e6,0x8000004c,0x00000803,0x80000161 } }
-, {1,45,0,58,0,2, { 0xf4000014,0xb4000008,0x08000000,0x9800000c,0xd8000010,0x08000010,0xb8000010,0x98000000,0x60000000,0x00000008,0xc0000000,0x90000014,0x10000010,0xb8000014,0x28000000,0x20000010,0x48000000,0x08000018,0x60000000,0x90000010,0xf0000010,0x90000008,0xc0000000,0x90000010,0xf0000010,0xb0000008,0x40000000,0x90000000,0xf0000010,0x90000018,0x60000000,0x90000010,0x90000010,0x90000000,0x80000000,0x00000010,0xa0000000,0x20000000,0xa0000000,0x20000010,0x00000000,0x20000010,0x20000000,0x00000010,0x20000000,0x00000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000040,0x40000002,0x80000004,0x80000080,0x80000006,0x00000049,0x00000103,0x80000009,0x80000012,0x80000202,0x00000018,0x00000164,0x00000408,0x800000e6,0x8000004c,0x00000803 } }
-, {1,46,0,58,0,3, { 0x2c000010,0xf4000014,0xb4000008,0x08000000,0x9800000c,0xd8000010,0x08000010,0xb8000010,0x98000000,0x60000000,0x00000008,0xc0000000,0x90000014,0x10000010,0xb8000014,0x28000000,0x20000010,0x48000000,0x08000018,0x60000000,0x90000010,0xf0000010,0x90000008,0xc0000000,0x90000010,0xf0000010,0xb0000008,0x40000000,0x90000000,0xf0000010,0x90000018,0x60000000,0x90000010,0x90000010,0x90000000,0x80000000,0x00000010,0xa0000000,0x20000000,0xa0000000,0x20000010,0x00000000,0x20000010,0x20000000,0x00000010,0x20000000,0x00000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000040,0x40000002,0x80000004,0x80000080,0x80000006,0x00000049,0x00000103,0x80000009,0x80000012,0x80000202,0x00000018,0x00000164,0x00000408,0x800000e6,0x8000004c } }
-, {1,46,2,58,0,4, { 0xb0000040,0xd0000053,0xd0000022,0x20000000,0x60000032,0x60000043,0x20000040,0xe0000042,0x60000002,0x80000001,0x00000020,0x00000003,0x40000052,0x40000040,0xe0000052,0xa0000000,0x80000040,0x20000001,0x20000060,0x80000001,0x40000042,0xc0000043,0x40000022,0x00000003,0x40000042,0xc0000043,0xc0000022,0x00000001,0x40000002,0xc0000043,0x40000062,0x80000001,0x40000042,0x40000042,0x40000002,0x00000002,0x00000040,0x80000002,0x80000000,0x80000002,0x80000040,0x00000000,0x80000040,0x80000000,0x00000040,0x80000000,0x00000040,0x80000002,0x00000000,0x80000000,0x80000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000004,0x00000080,0x00000004,0x00000009,0x00000101,0x00000009,0x00000012,0x00000202,0x0000001a,0x00000124,0x0000040c,0x00000026,0x0000004a,0x0000080a,0x00000060,0x00000590,0x00001020,0x0000039a,0x00000132 } }
-, {1,47,0,58,0,5, { 0xc8000010,0x2c000010,0xf4000014,0xb4000008,0x08000000,0x9800000c,0xd8000010,0x08000010,0xb8000010,0x98000000,0x60000000,0x00000008,0xc0000000,0x90000014,0x10000010,0xb8000014,0x28000000,0x20000010,0x48000000,0x08000018,0x60000000,0x90000010,0xf0000010,0x90000008,0xc0000000,0x90000010,0xf0000010,0xb0000008,0x40000000,0x90000000,0xf0000010,0x90000018,0x60000000,0x90000010,0x90000010,0x90000000,0x80000000,0x00000010,0xa0000000,0x20000000,0xa0000000,0x20000010,0x00000000,0x20000010,0x20000000,0x00000010,0x20000000,0x00000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000040,0x40000002,0x80000004,0x80000080,0x80000006,0x00000049,0x00000103,0x80000009,0x80000012,0x80000202,0x00000018,0x00000164,0x00000408,0x800000e6 } }
-, {1,47,2,58,0,6, { 0x20000043,0xb0000040,0xd0000053,0xd0000022,0x20000000,0x60000032,0x60000043,0x20000040,0xe0000042,0x60000002,0x80000001,0x00000020,0x00000003,0x40000052,0x40000040,0xe0000052,0xa0000000,0x80000040,0x20000001,0x20000060,0x80000001,0x40000042,0xc0000043,0x40000022,0x00000003,0x40000042,0xc0000043,0xc0000022,0x00000001,0x40000002,0xc0000043,0x40000062,0x80000001,0x40000042,0x40000042,0x40000002,0x00000002,0x00000040,0x80000002,0x80000000,0x80000002,0x80000040,0x00000000,0x80000040,0x80000000,0x00000040,0x80000000,0x00000040,0x80000002,0x00000000,0x80000000,0x80000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000004,0x00000080,0x00000004,0x00000009,0x00000101,0x00000009,0x00000012,0x00000202,0x0000001a,0x00000124,0x0000040c,0x00000026,0x0000004a,0x0000080a,0x00000060,0x00000590,0x00001020,0x0000039a } }
-, {1,48,0,58,0,7, { 0xb800000a,0xc8000010,0x2c000010,0xf4000014,0xb4000008,0x08000000,0x9800000c,0xd8000010,0x08000010,0xb8000010,0x98000000,0x60000000,0x00000008,0xc0000000,0x90000014,0x10000010,0xb8000014,0x28000000,0x20000010,0x48000000,0x08000018,0x60000000,0x90000010,0xf0000010,0x90000008,0xc0000000,0x90000010,0xf0000010,0xb0000008,0x40000000,0x90000000,0xf0000010,0x90000018,0x60000000,0x90000010,0x90000010,0x90000000,0x80000000,0x00000010,0xa0000000,0x20000000,0xa0000000,0x20000010,0x00000000,0x20000010,0x20000000,0x00000010,0x20000000,0x00000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000040,0x40000002,0x80000004,0x80000080,0x80000006,0x00000049,0x00000103,0x80000009,0x80000012,0x80000202,0x00000018,0x00000164,0x00000408 } }
-, {1,48,2,58,0,8, { 0xe000002a,0x20000043,0xb0000040,0xd0000053,0xd0000022,0x20000000,0x60000032,0x60000043,0x20000040,0xe0000042,0x60000002,0x80000001,0x00000020,0x00000003,0x40000052,0x40000040,0xe0000052,0xa0000000,0x80000040,0x20000001,0x20000060,0x80000001,0x40000042,0xc0000043,0x40000022,0x00000003,0x40000042,0xc0000043,0xc0000022,0x00000001,0x40000002,0xc0000043,0x40000062,0x80000001,0x40000042,0x40000042,0x40000002,0x00000002,0x00000040,0x80000002,0x80000000,0x80000002,0x80000040,0x00000000,0x80000040,0x80000000,0x00000040,0x80000000,0x00000040,0x80000002,0x00000000,0x80000000,0x80000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000004,0x00000080,0x00000004,0x00000009,0x00000101,0x00000009,0x00000012,0x00000202,0x0000001a,0x00000124,0x0000040c,0x00000026,0x0000004a,0x0000080a,0x00000060,0x00000590,0x00001020 } }
-, {1,49,0,58,0,9, { 0x18000000,0xb800000a,0xc8000010,0x2c000010,0xf4000014,0xb4000008,0x08000000,0x9800000c,0xd8000010,0x08000010,0xb8000010,0x98000000,0x60000000,0x00000008,0xc0000000,0x90000014,0x10000010,0xb8000014,0x28000000,0x20000010,0x48000000,0x08000018,0x60000000,0x90000010,0xf0000010,0x90000008,0xc0000000,0x90000010,0xf0000010,0xb0000008,0x40000000,0x90000000,0xf0000010,0x90000018,0x60000000,0x90000010,0x90000010,0x90000000,0x80000000,0x00000010,0xa0000000,0x20000000,0xa0000000,0x20000010,0x00000000,0x20000010,0x20000000,0x00000010,0x20000000,0x00000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000040,0x40000002,0x80000004,0x80000080,0x80000006,0x00000049,0x00000103,0x80000009,0x80000012,0x80000202,0x00000018,0x00000164 } }
-, {1,49,2,58,0,10, { 0x60000000,0xe000002a,0x20000043,0xb0000040,0xd0000053,0xd0000022,0x20000000,0x60000032,0x60000043,0x20000040,0xe0000042,0x60000002,0x80000001,0x00000020,0x00000003,0x40000052,0x40000040,0xe0000052,0xa0000000,0x80000040,0x20000001,0x20000060,0x80000001,0x40000042,0xc0000043,0x40000022,0x00000003,0x40000042,0xc0000043,0xc0000022,0x00000001,0x40000002,0xc0000043,0x40000062,0x80000001,0x40000042,0x40000042,0x40000002,0x00000002,0x00000040,0x80000002,0x80000000,0x80000002,0x80000040,0x00000000,0x80000040,0x80000000,0x00000040,0x80000000,0x00000040,0x80000002,0x00000000,0x80000000,0x80000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000004,0x00000080,0x00000004,0x00000009,0x00000101,0x00000009,0x00000012,0x00000202,0x0000001a,0x00000124,0x0000040c,0x00000026,0x0000004a,0x0000080a,0x00000060,0x00000590 } }
-, {1,50,0,65,0,11, { 0x0800000c,0x18000000,0xb800000a,0xc8000010,0x2c000010,0xf4000014,0xb4000008,0x08000000,0x9800000c,0xd8000010,0x08000010,0xb8000010,0x98000000,0x60000000,0x00000008,0xc0000000,0x90000014,0x10000010,0xb8000014,0x28000000,0x20000010,0x48000000,0x08000018,0x60000000,0x90000010,0xf0000010,0x90000008,0xc0000000,0x90000010,0xf0000010,0xb0000008,0x40000000,0x90000000,0xf0000010,0x90000018,0x60000000,0x90000010,0x90000010,0x90000000,0x80000000,0x00000010,0xa0000000,0x20000000,0xa0000000,0x20000010,0x00000000,0x20000010,0x20000000,0x00000010,0x20000000,0x00000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000040,0x40000002,0x80000004,0x80000080,0x80000006,0x00000049,0x00000103,0x80000009,0x80000012,0x80000202,0x00000018 } }
-, {1,50,2,65,0,12, { 0x20000030,0x60000000,0xe000002a,0x20000043,0xb0000040,0xd0000053,0xd0000022,0x20000000,0x60000032,0x60000043,0x20000040,0xe0000042,0x60000002,0x80000001,0x00000020,0x00000003,0x40000052,0x40000040,0xe0000052,0xa0000000,0x80000040,0x20000001,0x20000060,0x80000001,0x40000042,0xc0000043,0x40000022,0x00000003,0x40000042,0xc0000043,0xc0000022,0x00000001,0x40000002,0xc0000043,0x40000062,0x80000001,0x40000042,0x40000042,0x40000002,0x00000002,0x00000040,0x80000002,0x80000000,0x80000002,0x80000040,0x00000000,0x80000040,0x80000000,0x00000040,0x80000000,0x00000040,0x80000002,0x00000000,0x80000000,0x80000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000004,0x00000080,0x00000004,0x00000009,0x00000101,0x00000009,0x00000012,0x00000202,0x0000001a,0x00000124,0x0000040c,0x00000026,0x0000004a,0x0000080a,0x00000060 } }
-, {1,51,0,65,0,13, { 0xe8000000,0x0800000c,0x18000000,0xb800000a,0xc8000010,0x2c000010,0xf4000014,0xb4000008,0x08000000,0x9800000c,0xd8000010,0x08000010,0xb8000010,0x98000000,0x60000000,0x00000008,0xc0000000,0x90000014,0x10000010,0xb8000014,0x28000000,0x20000010,0x48000000,0x08000018,0x60000000,0x90000010,0xf0000010,0x90000008,0xc0000000,0x90000010,0xf0000010,0xb0000008,0x40000000,0x90000000,0xf0000010,0x90000018,0x60000000,0x90000010,0x90000010,0x90000000,0x80000000,0x00000010,0xa0000000,0x20000000,0xa0000000,0x20000010,0x00000000,0x20000010,0x20000000,0x00000010,0x20000000,0x00000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000040,0x40000002,0x80000004,0x80000080,0x80000006,0x00000049,0x00000103,0x80000009,0x80000012,0x80000202 } }
-, {1,51,2,65,0,14, { 0xa0000003,0x20000030,0x60000000,0xe000002a,0x20000043,0xb0000040,0xd0000053,0xd0000022,0x20000000,0x60000032,0x60000043,0x20000040,0xe0000042,0x60000002,0x80000001,0x00000020,0x00000003,0x40000052,0x40000040,0xe0000052,0xa0000000,0x80000040,0x20000001,0x20000060,0x80000001,0x40000042,0xc0000043,0x40000022,0x00000003,0x40000042,0xc0000043,0xc0000022,0x00000001,0x40000002,0xc0000043,0x40000062,0x80000001,0x40000042,0x40000042,0x40000002,0x00000002,0x00000040,0x80000002,0x80000000,0x80000002,0x80000040,0x00000000,0x80000040,0x80000000,0x00000040,0x80000000,0x00000040,0x80000002,0x00000000,0x80000000,0x80000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000004,0x00000080,0x00000004,0x00000009,0x00000101,0x00000009,0x00000012,0x00000202,0x0000001a,0x00000124,0x0000040c,0x00000026,0x0000004a,0x0000080a } }
-, {1,52,0,65,0,15, { 0x04000010,0xe8000000,0x0800000c,0x18000000,0xb800000a,0xc8000010,0x2c000010,0xf4000014,0xb4000008,0x08000000,0x9800000c,0xd8000010,0x08000010,0xb8000010,0x98000000,0x60000000,0x00000008,0xc0000000,0x90000014,0x10000010,0xb8000014,0x28000000,0x20000010,0x48000000,0x08000018,0x60000000,0x90000010,0xf0000010,0x90000008,0xc0000000,0x90000010,0xf0000010,0xb0000008,0x40000000,0x90000000,0xf0000010,0x90000018,0x60000000,0x90000010,0x90000010,0x90000000,0x80000000,0x00000010,0xa0000000,0x20000000,0xa0000000,0x20000010,0x00000000,0x20000010,0x20000000,0x00000010,0x20000000,0x00000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000040,0x40000002,0x80000004,0x80000080,0x80000006,0x00000049,0x00000103,0x80000009,0x80000012 } }
-, {2,45,0,58,0,16, { 0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b,0x80000107,0x00000089,0x00000014,0x8000024b,0x0000011b,0x8000016d,0x8000041a,0x000002e4,0x80000054,0x00000967 } }
-, {2,46,0,58,0,17, { 0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b,0x80000107,0x00000089,0x00000014,0x8000024b,0x0000011b,0x8000016d,0x8000041a,0x000002e4,0x80000054 } }
-, {2,46,2,58,0,18, { 0x90000070,0xb0000053,0x30000008,0x00000043,0xd0000072,0xb0000010,0xf0000062,0xc0000042,0x00000030,0xe0000042,0x20000060,0xe0000041,0x20000050,0xc0000041,0xe0000072,0xa0000003,0xc0000012,0x60000041,0xc0000032,0x20000001,0xc0000002,0xe0000042,0x60000042,0x80000002,0x00000000,0x00000000,0x80000000,0x00000002,0x00000040,0x00000000,0x80000040,0x80000000,0x00000040,0x80000001,0x00000060,0x80000003,0x40000002,0xc0000040,0xc0000002,0x80000000,0x80000000,0x80000002,0x00000040,0x00000002,0x80000000,0x80000000,0x80000000,0x00000002,0x00000040,0x00000000,0x80000040,0x80000002,0x00000000,0x80000000,0x80000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000004,0x00000080,0x00000004,0x00000009,0x00000105,0x00000089,0x00000016,0x0000020b,0x0000011b,0x0000012d,0x0000041e,0x00000224,0x00000050,0x0000092e,0x0000046c,0x000005b6,0x0000106a,0x00000b90,0x00000152 } }
-, {2,47,0,58,0,19, { 0x20000010,0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b,0x80000107,0x00000089,0x00000014,0x8000024b,0x0000011b,0x8000016d,0x8000041a,0x000002e4 } }
-, {2,48,0,58,0,20, { 0xbc00001a,0x20000010,0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b,0x80000107,0x00000089,0x00000014,0x8000024b,0x0000011b,0x8000016d,0x8000041a } }
-, {2,49,0,58,0,21, { 0x3c000004,0xbc00001a,0x20000010,0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b,0x80000107,0x00000089,0x00000014,0x8000024b,0x0000011b,0x8000016d } }
-, {2,49,2,58,0,22, { 0xf0000010,0xf000006a,0x80000040,0x90000070,0xb0000053,0x30000008,0x00000043,0xd0000072,0xb0000010,0xf0000062,0xc0000042,0x00000030,0xe0000042,0x20000060,0xe0000041,0x20000050,0xc0000041,0xe0000072,0xa0000003,0xc0000012,0x60000041,0xc0000032,0x20000001,0xc0000002,0xe0000042,0x60000042,0x80000002,0x00000000,0x00000000,0x80000000,0x00000002,0x00000040,0x00000000,0x80000040,0x80000000,0x00000040,0x80000001,0x00000060,0x80000003,0x40000002,0xc0000040,0xc0000002,0x80000000,0x80000000,0x80000002,0x00000040,0x00000002,0x80000000,0x80000000,0x80000000,0x00000002,0x00000040,0x00000000,0x80000040,0x80000002,0x00000000,0x80000000,0x80000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000004,0x00000080,0x00000004,0x00000009,0x00000105,0x00000089,0x00000016,0x0000020b,0x0000011b,0x0000012d,0x0000041e,0x00000224,0x00000050,0x0000092e,0x0000046c,0x000005b6 } }
-, {2,50,0,65,0,23, { 0xb400001c,0x3c000004,0xbc00001a,0x20000010,0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b,0x80000107,0x00000089,0x00000014,0x8000024b,0x0000011b } }
-, {2,50,2,65,0,24, { 0xd0000072,0xf0000010,0xf000006a,0x80000040,0x90000070,0xb0000053,0x30000008,0x00000043,0xd0000072,0xb0000010,0xf0000062,0xc0000042,0x00000030,0xe0000042,0x20000060,0xe0000041,0x20000050,0xc0000041,0xe0000072,0xa0000003,0xc0000012,0x60000041,0xc0000032,0x20000001,0xc0000002,0xe0000042,0x60000042,0x80000002,0x00000000,0x00000000,0x80000000,0x00000002,0x00000040,0x00000000,0x80000040,0x80000000,0x00000040,0x80000001,0x00000060,0x80000003,0x40000002,0xc0000040,0xc0000002,0x80000000,0x80000000,0x80000002,0x00000040,0x00000002,0x80000000,0x80000000,0x80000000,0x00000002,0x00000040,0x00000000,0x80000040,0x80000002,0x00000000,0x80000000,0x80000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000004,0x00000080,0x00000004,0x00000009,0x00000105,0x00000089,0x00000016,0x0000020b,0x0000011b,0x0000012d,0x0000041e,0x00000224,0x00000050,0x0000092e,0x0000046c } }
-, {2,51,0,65,0,25, { 0xc0000010,0xb400001c,0x3c000004,0xbc00001a,0x20000010,0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b,0x80000107,0x00000089,0x00000014,0x8000024b } }
-, {2,51,2,65,0,26, { 0x00000043,0xd0000072,0xf0000010,0xf000006a,0x80000040,0x90000070,0xb0000053,0x30000008,0x00000043,0xd0000072,0xb0000010,0xf0000062,0xc0000042,0x00000030,0xe0000042,0x20000060,0xe0000041,0x20000050,0xc0000041,0xe0000072,0xa0000003,0xc0000012,0x60000041,0xc0000032,0x20000001,0xc0000002,0xe0000042,0x60000042,0x80000002,0x00000000,0x00000000,0x80000000,0x00000002,0x00000040,0x00000000,0x80000040,0x80000000,0x00000040,0x80000001,0x00000060,0x80000003,0x40000002,0xc0000040,0xc0000002,0x80000000,0x80000000,0x80000002,0x00000040,0x00000002,0x80000000,0x80000000,0x80000000,0x00000002,0x00000040,0x00000000,0x80000040,0x80000002,0x00000000,0x80000000,0x80000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000004,0x00000080,0x00000004,0x00000009,0x00000105,0x00000089,0x00000016,0x0000020b,0x0000011b,0x0000012d,0x0000041e,0x00000224,0x00000050,0x0000092e } }
-, {2,52,0,65,0,27, { 0x0c000002,0xc0000010,0xb400001c,0x3c000004,0xbc00001a,0x20000010,0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b,0x80000107,0x00000089,0x00000014 } }
-, {2,53,0,65,0,28, { 0xcc000014,0x0c000002,0xc0000010,0xb400001c,0x3c000004,0xbc00001a,0x20000010,0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b,0x80000107,0x00000089 } }
-, {2,54,0,65,0,29, { 0x0400001c,0xcc000014,0x0c000002,0xc0000010,0xb400001c,0x3c000004,0xbc00001a,0x20000010,0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b,0x80000107 } }
-, {2,55,0,65,0,30, { 0x00000010,0x0400001c,0xcc000014,0x0c000002,0xc0000010,0xb400001c,0x3c000004,0xbc00001a,0x20000010,0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046,0x4000004b } }
-, {2,56,0,65,0,31, { 0x2600001a,0x00000010,0x0400001c,0xcc000014,0x0c000002,0xc0000010,0xb400001c,0x3c000004,0xbc00001a,0x20000010,0x2400001c,0xec000014,0x0c000002,0xc0000010,0xb400001c,0x2c000004,0xbc000018,0xb0000010,0x0000000c,0xb8000010,0x08000018,0x78000010,0x08000014,0x70000010,0xb800001c,0xe8000000,0xb0000004,0x58000010,0xb000000c,0x48000000,0xb0000000,0xb8000010,0x98000010,0xa0000000,0x00000000,0x00000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0x20000000,0x00000010,0x60000000,0x00000018,0xe0000000,0x90000000,0x30000010,0xb0000000,0x20000000,0x20000000,0xa0000000,0x00000010,0x80000000,0x20000000,0x20000000,0x20000000,0x80000000,0x00000010,0x00000000,0x20000010,0xa0000000,0x00000000,0x20000000,0x20000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000001,0x00000020,0x00000001,0x40000002,0x40000041,0x40000022,0x80000005,0xc0000082,0xc0000046 } }
-, {0,0,0,0,0,0, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}}
-};
-void ubc_check(const uint32_t W[80], uint32_t dvmask[1])
-{
-	uint32_t mask = ~((uint32_t)(0));
-	mask &= (((((W[44]^W[45])>>29)&1)-1) | ~(DV_I_48_0_bit|DV_I_51_0_bit|DV_I_52_0_bit|DV_II_45_0_bit|DV_II_46_0_bit|DV_II_50_0_bit|DV_II_51_0_bit));
-	mask &= (((((W[49]^W[50])>>29)&1)-1) | ~(DV_I_46_0_bit|DV_II_45_0_bit|DV_II_50_0_bit|DV_II_51_0_bit|DV_II_55_0_bit|DV_II_56_0_bit));
-	mask &= (((((W[48]^W[49])>>29)&1)-1) | ~(DV_I_45_0_bit|DV_I_52_0_bit|DV_II_49_0_bit|DV_II_50_0_bit|DV_II_54_0_bit|DV_II_55_0_bit));
-	mask &= ((((W[47]^(W[50]>>25))&(1<<4))-(1<<4)) | ~(DV_I_47_0_bit|DV_I_49_0_bit|DV_I_51_0_bit|DV_II_45_0_bit|DV_II_51_0_bit|DV_II_56_0_bit));
-	mask &= (((((W[47]^W[48])>>29)&1)-1) | ~(DV_I_44_0_bit|DV_I_51_0_bit|DV_II_48_0_bit|DV_II_49_0_bit|DV_II_53_0_bit|DV_II_54_0_bit));
-	mask &= (((((W[46]>>4)^(W[49]>>29))&1)-1) | ~(DV_I_46_0_bit|DV_I_48_0_bit|DV_I_50_0_bit|DV_I_52_0_bit|DV_II_50_0_bit|DV_II_55_0_bit));
-	mask &= (((((W[46]^W[47])>>29)&1)-1) | ~(DV_I_43_0_bit|DV_I_50_0_bit|DV_II_47_0_bit|DV_II_48_0_bit|DV_II_52_0_bit|DV_II_53_0_bit));
-	mask &= (((((W[45]>>4)^(W[48]>>29))&1)-1) | ~(DV_I_45_0_bit|DV_I_47_0_bit|DV_I_49_0_bit|DV_I_51_0_bit|DV_II_49_0_bit|DV_II_54_0_bit));
-	mask &= (((((W[45]^W[46])>>29)&1)-1) | ~(DV_I_49_0_bit|DV_I_52_0_bit|DV_II_46_0_bit|DV_II_47_0_bit|DV_II_51_0_bit|DV_II_52_0_bit));
-	mask &= (((((W[44]>>4)^(W[47]>>29))&1)-1) | ~(DV_I_44_0_bit|DV_I_46_0_bit|DV_I_48_0_bit|DV_I_50_0_bit|DV_II_48_0_bit|DV_II_53_0_bit));
-	mask &= (((((W[43]>>4)^(W[46]>>29))&1)-1) | ~(DV_I_43_0_bit|DV_I_45_0_bit|DV_I_47_0_bit|DV_I_49_0_bit|DV_II_47_0_bit|DV_II_52_0_bit));
-	mask &= (((((W[43]^W[44])>>29)&1)-1) | ~(DV_I_47_0_bit|DV_I_50_0_bit|DV_I_51_0_bit|DV_II_45_0_bit|DV_II_49_0_bit|DV_II_50_0_bit));
-	mask &= (((((W[42]>>4)^(W[45]>>29))&1)-1) | ~(DV_I_44_0_bit|DV_I_46_0_bit|DV_I_48_0_bit|DV_I_52_0_bit|DV_II_46_0_bit|DV_II_51_0_bit));
-	mask &= (((((W[41]>>4)^(W[44]>>29))&1)-1) | ~(DV_I_43_0_bit|DV_I_45_0_bit|DV_I_47_0_bit|DV_I_51_0_bit|DV_II_45_0_bit|DV_II_50_0_bit));
-	mask &= (((((W[40]^W[41])>>29)&1)-1) | ~(DV_I_44_0_bit|DV_I_47_0_bit|DV_I_48_0_bit|DV_II_46_0_bit|DV_II_47_0_bit|DV_II_56_0_bit));
-	mask &= (((((W[54]^W[55])>>29)&1)-1) | ~(DV_I_51_0_bit|DV_II_47_0_bit|DV_II_50_0_bit|DV_II_55_0_bit|DV_II_56_0_bit));
-	mask &= (((((W[53]^W[54])>>29)&1)-1) | ~(DV_I_50_0_bit|DV_II_46_0_bit|DV_II_49_0_bit|DV_II_54_0_bit|DV_II_55_0_bit));
-	mask &= (((((W[52]^W[53])>>29)&1)-1) | ~(DV_I_49_0_bit|DV_II_45_0_bit|DV_II_48_0_bit|DV_II_53_0_bit|DV_II_54_0_bit));
-	mask &= ((((W[50]^(W[53]>>25))&(1<<4))-(1<<4)) | ~(DV_I_50_0_bit|DV_I_52_0_bit|DV_II_46_0_bit|DV_II_48_0_bit|DV_II_54_0_bit));
-	mask &= (((((W[50]^W[51])>>29)&1)-1) | ~(DV_I_47_0_bit|DV_II_46_0_bit|DV_II_51_0_bit|DV_II_52_0_bit|DV_II_56_0_bit));
-	mask &= ((((W[49]^(W[52]>>25))&(1<<4))-(1<<4)) | ~(DV_I_49_0_bit|DV_I_51_0_bit|DV_II_45_0_bit|DV_II_47_0_bit|DV_II_53_0_bit));
-	mask &= ((((W[48]^(W[51]>>25))&(1<<4))-(1<<4)) | ~(DV_I_48_0_bit|DV_I_50_0_bit|DV_I_52_0_bit|DV_II_46_0_bit|DV_II_52_0_bit));
-	mask &= (((((W[42]^W[43])>>29)&1)-1) | ~(DV_I_46_0_bit|DV_I_49_0_bit|DV_I_50_0_bit|DV_II_48_0_bit|DV_II_49_0_bit));
-	mask &= (((((W[41]^W[42])>>29)&1)-1) | ~(DV_I_45_0_bit|DV_I_48_0_bit|DV_I_49_0_bit|DV_II_47_0_bit|DV_II_48_0_bit));
-	mask &= (((((W[40]>>4)^(W[43]>>29))&1)-1) | ~(DV_I_44_0_bit|DV_I_46_0_bit|DV_I_50_0_bit|DV_II_49_0_bit|DV_II_56_0_bit));
-	mask &= (((((W[39]>>4)^(W[42]>>29))&1)-1) | ~(DV_I_43_0_bit|DV_I_45_0_bit|DV_I_49_0_bit|DV_II_48_0_bit|DV_II_55_0_bit));
-	if (mask & (DV_I_44_0_bit|DV_I_48_0_bit|DV_II_47_0_bit|DV_II_54_0_bit|DV_II_56_0_bit))
-		mask &= (((((W[38]>>4)^(W[41]>>29))&1)-1) | ~(DV_I_44_0_bit|DV_I_48_0_bit|DV_II_47_0_bit|DV_II_54_0_bit|DV_II_56_0_bit));
-	mask &= (((((W[37]>>4)^(W[40]>>29))&1)-1) | ~(DV_I_43_0_bit|DV_I_47_0_bit|DV_II_46_0_bit|DV_II_53_0_bit|DV_II_55_0_bit));
-	if (mask & (DV_I_52_0_bit|DV_II_48_0_bit|DV_II_51_0_bit|DV_II_56_0_bit))
-		mask &= (((((W[55]^W[56])>>29)&1)-1) | ~(DV_I_52_0_bit|DV_II_48_0_bit|DV_II_51_0_bit|DV_II_56_0_bit));
-	if (mask & (DV_I_52_0_bit|DV_II_48_0_bit|DV_II_50_0_bit|DV_II_56_0_bit))
-		mask &= ((((W[52]^(W[55]>>25))&(1<<4))-(1<<4)) | ~(DV_I_52_0_bit|DV_II_48_0_bit|DV_II_50_0_bit|DV_II_56_0_bit));
-	if (mask & (DV_I_51_0_bit|DV_II_47_0_bit|DV_II_49_0_bit|DV_II_55_0_bit))
-		mask &= ((((W[51]^(W[54]>>25))&(1<<4))-(1<<4)) | ~(DV_I_51_0_bit|DV_II_47_0_bit|DV_II_49_0_bit|DV_II_55_0_bit));
-	if (mask & (DV_I_48_0_bit|DV_II_47_0_bit|DV_II_52_0_bit|DV_II_53_0_bit))
-		mask &= (((((W[51]^W[52])>>29)&1)-1) | ~(DV_I_48_0_bit|DV_II_47_0_bit|DV_II_52_0_bit|DV_II_53_0_bit));
-	if (mask & (DV_I_46_0_bit|DV_I_49_0_bit|DV_II_45_0_bit|DV_II_48_0_bit))
-		mask &= (((((W[36]>>4)^(W[40]>>29))&1)-1) | ~(DV_I_46_0_bit|DV_I_49_0_bit|DV_II_45_0_bit|DV_II_48_0_bit));
-	if (mask & (DV_I_52_0_bit|DV_II_48_0_bit|DV_II_49_0_bit))
-		mask &= ((0-(((W[53]^W[56])>>29)&1)) | ~(DV_I_52_0_bit|DV_II_48_0_bit|DV_II_49_0_bit));
-	if (mask & (DV_I_50_0_bit|DV_II_46_0_bit|DV_II_47_0_bit))
-		mask &= ((0-(((W[51]^W[54])>>29)&1)) | ~(DV_I_50_0_bit|DV_II_46_0_bit|DV_II_47_0_bit));
-	if (mask & (DV_I_49_0_bit|DV_I_51_0_bit|DV_II_45_0_bit))
-		mask &= ((0-(((W[50]^W[52])>>29)&1)) | ~(DV_I_49_0_bit|DV_I_51_0_bit|DV_II_45_0_bit));
-	if (mask & (DV_I_48_0_bit|DV_I_50_0_bit|DV_I_52_0_bit))
-		mask &= ((0-(((W[49]^W[51])>>29)&1)) | ~(DV_I_48_0_bit|DV_I_50_0_bit|DV_I_52_0_bit));
-	if (mask & (DV_I_47_0_bit|DV_I_49_0_bit|DV_I_51_0_bit))
-		mask &= ((0-(((W[48]^W[50])>>29)&1)) | ~(DV_I_47_0_bit|DV_I_49_0_bit|DV_I_51_0_bit));
-	if (mask & (DV_I_46_0_bit|DV_I_48_0_bit|DV_I_50_0_bit))
-		mask &= ((0-(((W[47]^W[49])>>29)&1)) | ~(DV_I_46_0_bit|DV_I_48_0_bit|DV_I_50_0_bit));
-	if (mask & (DV_I_45_0_bit|DV_I_47_0_bit|DV_I_49_0_bit))
-		mask &= ((0-(((W[46]^W[48])>>29)&1)) | ~(DV_I_45_0_bit|DV_I_47_0_bit|DV_I_49_0_bit));
-	mask &= ((((W[45]^W[47])&(1<<6))-(1<<6)) | ~(DV_I_47_2_bit|DV_I_49_2_bit|DV_I_51_2_bit));
-	if (mask & (DV_I_44_0_bit|DV_I_46_0_bit|DV_I_48_0_bit))
-		mask &= ((0-(((W[45]^W[47])>>29)&1)) | ~(DV_I_44_0_bit|DV_I_46_0_bit|DV_I_48_0_bit));
-	mask &= (((((W[44]^W[46])>>6)&1)-1) | ~(DV_I_46_2_bit|DV_I_48_2_bit|DV_I_50_2_bit));
-	if (mask & (DV_I_43_0_bit|DV_I_45_0_bit|DV_I_47_0_bit))
-		mask &= ((0-(((W[44]^W[46])>>29)&1)) | ~(DV_I_43_0_bit|DV_I_45_0_bit|DV_I_47_0_bit));
-	mask &= ((0-((W[41]^(W[42]>>5))&(1<<1))) | ~(DV_I_48_2_bit|DV_II_46_2_bit|DV_II_51_2_bit));
-	mask &= ((0-((W[40]^(W[41]>>5))&(1<<1))) | ~(DV_I_47_2_bit|DV_I_51_2_bit|DV_II_50_2_bit));
-	if (mask & (DV_I_44_0_bit|DV_I_46_0_bit|DV_II_56_0_bit))
-		mask &= ((0-(((W[40]^W[42])>>4)&1)) | ~(DV_I_44_0_bit|DV_I_46_0_bit|DV_II_56_0_bit));
-	mask &= ((0-((W[39]^(W[40]>>5))&(1<<1))) | ~(DV_I_46_2_bit|DV_I_50_2_bit|DV_II_49_2_bit));
-	if (mask & (DV_I_43_0_bit|DV_I_45_0_bit|DV_II_55_0_bit))
-		mask &= ((0-(((W[39]^W[41])>>4)&1)) | ~(DV_I_43_0_bit|DV_I_45_0_bit|DV_II_55_0_bit));
-	if (mask & (DV_I_44_0_bit|DV_II_54_0_bit|DV_II_56_0_bit))
-		mask &= ((0-(((W[38]^W[40])>>4)&1)) | ~(DV_I_44_0_bit|DV_II_54_0_bit|DV_II_56_0_bit));
-	if (mask & (DV_I_43_0_bit|DV_II_53_0_bit|DV_II_55_0_bit))
-		mask &= ((0-(((W[37]^W[39])>>4)&1)) | ~(DV_I_43_0_bit|DV_II_53_0_bit|DV_II_55_0_bit));
-	mask &= ((0-((W[36]^(W[37]>>5))&(1<<1))) | ~(DV_I_47_2_bit|DV_I_50_2_bit|DV_II_46_2_bit));
-	if (mask & (DV_I_45_0_bit|DV_I_48_0_bit|DV_II_47_0_bit))
-		mask &= (((((W[35]>>4)^(W[39]>>29))&1)-1) | ~(DV_I_45_0_bit|DV_I_48_0_bit|DV_II_47_0_bit));
-	if (mask & (DV_I_48_0_bit|DV_II_48_0_bit))
-		mask &= ((0-((W[63]^(W[64]>>5))&(1<<0))) | ~(DV_I_48_0_bit|DV_II_48_0_bit));
-	if (mask & (DV_I_45_0_bit|DV_II_45_0_bit))
-		mask &= ((0-((W[63]^(W[64]>>5))&(1<<1))) | ~(DV_I_45_0_bit|DV_II_45_0_bit));
-	if (mask & (DV_I_47_0_bit|DV_II_47_0_bit))
-		mask &= ((0-((W[62]^(W[63]>>5))&(1<<0))) | ~(DV_I_47_0_bit|DV_II_47_0_bit));
-	if (mask & (DV_I_46_0_bit|DV_II_46_0_bit))
-		mask &= ((0-((W[61]^(W[62]>>5))&(1<<0))) | ~(DV_I_46_0_bit|DV_II_46_0_bit));
-	mask &= ((0-((W[61]^(W[62]>>5))&(1<<2))) | ~(DV_I_46_2_bit|DV_II_46_2_bit));
-	if (mask & (DV_I_45_0_bit|DV_II_45_0_bit))
-		mask &= ((0-((W[60]^(W[61]>>5))&(1<<0))) | ~(DV_I_45_0_bit|DV_II_45_0_bit));
-	if (mask & (DV_II_51_0_bit|DV_II_54_0_bit))
-		mask &= (((((W[58]^W[59])>>29)&1)-1) | ~(DV_II_51_0_bit|DV_II_54_0_bit));
-	if (mask & (DV_II_50_0_bit|DV_II_53_0_bit))
-		mask &= (((((W[57]^W[58])>>29)&1)-1) | ~(DV_II_50_0_bit|DV_II_53_0_bit));
-	if (mask & (DV_II_52_0_bit|DV_II_54_0_bit))
-		mask &= ((((W[56]^(W[59]>>25))&(1<<4))-(1<<4)) | ~(DV_II_52_0_bit|DV_II_54_0_bit));
-	if (mask & (DV_II_51_0_bit|DV_II_52_0_bit))
-		mask &= ((0-(((W[56]^W[59])>>29)&1)) | ~(DV_II_51_0_bit|DV_II_52_0_bit));
-	if (mask & (DV_II_49_0_bit|DV_II_52_0_bit))
-		mask &= (((((W[56]^W[57])>>29)&1)-1) | ~(DV_II_49_0_bit|DV_II_52_0_bit));
-	if (mask & (DV_II_51_0_bit|DV_II_53_0_bit))
-		mask &= ((((W[55]^(W[58]>>25))&(1<<4))-(1<<4)) | ~(DV_II_51_0_bit|DV_II_53_0_bit));
-	if (mask & (DV_II_50_0_bit|DV_II_52_0_bit))
-		mask &= ((((W[54]^(W[57]>>25))&(1<<4))-(1<<4)) | ~(DV_II_50_0_bit|DV_II_52_0_bit));
-	if (mask & (DV_II_49_0_bit|DV_II_51_0_bit))
-		mask &= ((((W[53]^(W[56]>>25))&(1<<4))-(1<<4)) | ~(DV_II_49_0_bit|DV_II_51_0_bit));
-	mask &= ((((W[51]^(W[50]>>5))&(1<<1))-(1<<1)) | ~(DV_I_50_2_bit|DV_II_46_2_bit));
-	mask &= ((((W[48]^W[50])&(1<<6))-(1<<6)) | ~(DV_I_50_2_bit|DV_II_46_2_bit));
-	if (mask & (DV_I_51_0_bit|DV_I_52_0_bit))
-		mask &= ((0-(((W[48]^W[55])>>29)&1)) | ~(DV_I_51_0_bit|DV_I_52_0_bit));
-	mask &= ((((W[47]^W[49])&(1<<6))-(1<<6)) | ~(DV_I_49_2_bit|DV_I_51_2_bit));
-	mask &= ((((W[48]^(W[47]>>5))&(1<<1))-(1<<1)) | ~(DV_I_47_2_bit|DV_II_51_2_bit));
-	mask &= ((((W[46]^W[48])&(1<<6))-(1<<6)) | ~(DV_I_48_2_bit|DV_I_50_2_bit));
-	mask &= ((((W[47]^(W[46]>>5))&(1<<1))-(1<<1)) | ~(DV_I_46_2_bit|DV_II_50_2_bit));
-	mask &= ((0-((W[44]^(W[45]>>5))&(1<<1))) | ~(DV_I_51_2_bit|DV_II_49_2_bit));
-	mask &= ((((W[43]^W[45])&(1<<6))-(1<<6)) | ~(DV_I_47_2_bit|DV_I_49_2_bit));
-	mask &= (((((W[42]^W[44])>>6)&1)-1) | ~(DV_I_46_2_bit|DV_I_48_2_bit));
-	mask &= ((((W[43]^(W[42]>>5))&(1<<1))-(1<<1)) | ~(DV_II_46_2_bit|DV_II_51_2_bit));
-	mask &= ((((W[42]^(W[41]>>5))&(1<<1))-(1<<1)) | ~(DV_I_51_2_bit|DV_II_50_2_bit));
-	mask &= ((((W[41]^(W[40]>>5))&(1<<1))-(1<<1)) | ~(DV_I_50_2_bit|DV_II_49_2_bit));
-	if (mask & (DV_I_52_0_bit|DV_II_51_0_bit))
-		mask &= ((((W[39]^(W[43]>>25))&(1<<4))-(1<<4)) | ~(DV_I_52_0_bit|DV_II_51_0_bit));
-	if (mask & (DV_I_51_0_bit|DV_II_50_0_bit))
-		mask &= ((((W[38]^(W[42]>>25))&(1<<4))-(1<<4)) | ~(DV_I_51_0_bit|DV_II_50_0_bit));
-	if (mask & (DV_I_48_2_bit|DV_I_51_2_bit))
-		mask &= ((0-((W[37]^(W[38]>>5))&(1<<1))) | ~(DV_I_48_2_bit|DV_I_51_2_bit));
-	if (mask & (DV_I_50_0_bit|DV_II_49_0_bit))
-		mask &= ((((W[37]^(W[41]>>25))&(1<<4))-(1<<4)) | ~(DV_I_50_0_bit|DV_II_49_0_bit));
-	if (mask & (DV_II_52_0_bit|DV_II_54_0_bit))
-		mask &= ((0-((W[36]^W[38])&(1<<4))) | ~(DV_II_52_0_bit|DV_II_54_0_bit));
-	mask &= ((0-((W[35]^(W[36]>>5))&(1<<1))) | ~(DV_I_46_2_bit|DV_I_49_2_bit));
-	if (mask & (DV_I_51_0_bit|DV_II_47_0_bit))
-		mask &= ((((W[35]^(W[39]>>25))&(1<<3))-(1<<3)) | ~(DV_I_51_0_bit|DV_II_47_0_bit));
-if (mask) {
-
-	if (mask & DV_I_43_0_bit)
-		 if (
-			    !((W[61]^(W[62]>>5)) & (1<<1))
-			 || !(!((W[59]^(W[63]>>25)) & (1<<5)))
-			 || !((W[58]^(W[63]>>30)) & (1<<0))
-		 )  mask &= ~DV_I_43_0_bit;
-	if (mask & DV_I_44_0_bit)
-		 if (
-			    !((W[62]^(W[63]>>5)) & (1<<1))
-			 || !(!((W[60]^(W[64]>>25)) & (1<<5)))
-			 || !((W[59]^(W[64]>>30)) & (1<<0))
-		 )  mask &= ~DV_I_44_0_bit;
-	if (mask & DV_I_46_2_bit)
-		mask &= ((~((W[40]^W[42])>>2)) | ~DV_I_46_2_bit);
-	if (mask & DV_I_47_2_bit)
-		 if (
-			    !((W[62]^(W[63]>>5)) & (1<<2))
-			 || !(!((W[41]^W[43]) & (1<<6)))
-		 )  mask &= ~DV_I_47_2_bit;
-	if (mask & DV_I_48_2_bit)
-		 if (
-			    !((W[63]^(W[64]>>5)) & (1<<2))
-			 || !(!((W[48]^(W[49]<<5)) & (1<<6)))
-		 )  mask &= ~DV_I_48_2_bit;
-	if (mask & DV_I_49_2_bit)
-		 if (
-			    !(!((W[49]^(W[50]<<5)) & (1<<6)))
-			 || !((W[42]^W[50]) & (1<<1))
-			 || !(!((W[39]^(W[40]<<5)) & (1<<6)))
-			 || !((W[38]^W[40]) & (1<<1))
-		 )  mask &= ~DV_I_49_2_bit;
-	if (mask & DV_I_50_0_bit)
-		mask &= ((((W[36]^W[37])<<7)) | ~DV_I_50_0_bit);
-	if (mask & DV_I_50_2_bit)
-		mask &= ((((W[43]^W[51])<<11)) | ~DV_I_50_2_bit);
-	if (mask & DV_I_51_0_bit)
-		mask &= ((((W[37]^W[38])<<9)) | ~DV_I_51_0_bit);
-	if (mask & DV_I_51_2_bit)
-		 if (
-			    !(!((W[51]^(W[52]<<5)) & (1<<6)))
-			 || !(!((W[49]^W[51]) & (1<<6)))
-			 || !(!((W[37]^(W[37]>>5)) & (1<<1)))
-			 || !(!((W[35]^(W[39]>>25)) & (1<<5)))
-		 )  mask &= ~DV_I_51_2_bit;
-	if (mask & DV_I_52_0_bit)
-		mask &= ((((W[38]^W[39])<<11)) | ~DV_I_52_0_bit);
-	if (mask & DV_II_46_2_bit)
-		mask &= ((((W[47]^W[51])<<17)) | ~DV_II_46_2_bit);
-	if (mask & DV_II_48_0_bit)
-		 if (
-			    !(!((W[36]^(W[40]>>25)) & (1<<3)))
-			 || !((W[35]^(W[40]<<2)) & (1<<30))
-		 )  mask &= ~DV_II_48_0_bit;
-	if (mask & DV_II_49_0_bit)
-		 if (
-			    !(!((W[37]^(W[41]>>25)) & (1<<3)))
-			 || !((W[36]^(W[41]<<2)) & (1<<30))
-		 )  mask &= ~DV_II_49_0_bit;
-	if (mask & DV_II_49_2_bit)
-		 if (
-			    !(!((W[53]^(W[54]<<5)) & (1<<6)))
-			 || !(!((W[51]^W[53]) & (1<<6)))
-			 || !((W[50]^W[54]) & (1<<1))
-			 || !(!((W[45]^(W[46]<<5)) & (1<<6)))
-			 || !(!((W[37]^(W[41]>>25)) & (1<<5)))
-			 || !((W[36]^(W[41]>>30)) & (1<<0))
-		 )  mask &= ~DV_II_49_2_bit;
-	if (mask & DV_II_50_0_bit)
-		 if (
-			    !((W[55]^W[58]) & (1<<29))
-			 || !(!((W[38]^(W[42]>>25)) & (1<<3)))
-			 || !((W[37]^(W[42]<<2)) & (1<<30))
-		 )  mask &= ~DV_II_50_0_bit;
-	if (mask & DV_II_50_2_bit)
-		 if (
-			    !(!((W[54]^(W[55]<<5)) & (1<<6)))
-			 || !(!((W[52]^W[54]) & (1<<6)))
-			 || !((W[51]^W[55]) & (1<<1))
-			 || !((W[45]^W[47]) & (1<<1))
-			 || !(!((W[38]^(W[42]>>25)) & (1<<5)))
-			 || !((W[37]^(W[42]>>30)) & (1<<0))
-		 )  mask &= ~DV_II_50_2_bit;
-	if (mask & DV_II_51_0_bit)
-		 if (
-			    !(!((W[39]^(W[43]>>25)) & (1<<3)))
-			 || !((W[38]^(W[43]<<2)) & (1<<30))
-		 )  mask &= ~DV_II_51_0_bit;
-	if (mask & DV_II_51_2_bit)
-		 if (
-			    !(!((W[55]^(W[56]<<5)) & (1<<6)))
-			 || !(!((W[53]^W[55]) & (1<<6)))
-			 || !((W[52]^W[56]) & (1<<1))
-			 || !((W[46]^W[48]) & (1<<1))
-			 || !(!((W[39]^(W[43]>>25)) & (1<<5)))
-			 || !((W[38]^(W[43]>>30)) & (1<<0))
-		 )  mask &= ~DV_II_51_2_bit;
-	if (mask & DV_II_52_0_bit)
-		 if (
-			    !(!((W[59]^W[60]) & (1<<29)))
-			 || !(!((W[40]^(W[44]>>25)) & (1<<3)))
-			 || !(!((W[40]^(W[44]>>25)) & (1<<4)))
-			 || !((W[39]^(W[44]<<2)) & (1<<30))
-		 )  mask &= ~DV_II_52_0_bit;
-	if (mask & DV_II_53_0_bit)
-		 if (
-			    !((W[58]^W[61]) & (1<<29))
-			 || !(!((W[57]^(W[61]>>25)) & (1<<4)))
-			 || !(!((W[41]^(W[45]>>25)) & (1<<3)))
-			 || !(!((W[41]^(W[45]>>25)) & (1<<4)))
-		 )  mask &= ~DV_II_53_0_bit;
-	if (mask & DV_II_54_0_bit)
-		 if (
-			    !(!((W[58]^(W[62]>>25)) & (1<<4)))
-			 || !(!((W[42]^(W[46]>>25)) & (1<<3)))
-			 || !(!((W[42]^(W[46]>>25)) & (1<<4)))
-		 )  mask &= ~DV_II_54_0_bit;
-	if (mask & DV_II_55_0_bit)
-		 if (
-			    !(!((W[59]^(W[63]>>25)) & (1<<4)))
-			 || !(!((W[57]^(W[59]>>25)) & (1<<4)))
-			 || !(!((W[43]^(W[47]>>25)) & (1<<3)))
-			 || !(!((W[43]^(W[47]>>25)) & (1<<4)))
-		 )  mask &= ~DV_II_55_0_bit;
-	if (mask & DV_II_56_0_bit)
-		 if (
-			    !(!((W[60]^(W[64]>>25)) & (1<<4)))
-			 || !(!((W[44]^(W[48]>>25)) & (1<<3)))
-			 || !(!((W[44]^(W[48]>>25)) & (1<<4)))
-		 )  mask &= ~DV_II_56_0_bit;
-}
-
-	dvmask[0]=mask;
-}
-
-#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_C
-#include SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_C
-#endif
diff --git a/sha1dc/ubc_check.h b/sha1dc/ubc_check.h
deleted file mode 100644
index d7e17dc734..0000000000
--- a/sha1dc/ubc_check.h
+++ /dev/null
@@ -1,52 +0,0 @@
-/***
-* Copyright 2017 Marc Stevens <marc@marc-stevens.nl>, Dan Shumow <danshu@microsoft.com>
-* Distributed under the MIT Software License.
-* See accompanying file LICENSE.txt or copy at
-* https://opensource.org/licenses/MIT
-***/
-
-/*
-// this file was generated by the 'parse_bitrel' program in the tools section
-// using the data files from directory 'tools/data/3565'
-//
-// sha1_dvs contains a list of SHA-1 Disturbance Vectors (DV) to check
-// dvType, dvK and dvB define the DV: I(K,B) or II(K,B) (see the paper)
-// dm[80] is the expanded message block XOR-difference defined by the DV
-// testt is the step to do the recompression from for collision detection
-// maski and maskb define the bit to check for each DV in the dvmask returned by ubc_check
-//
-// ubc_check takes as input an expanded message block and verifies the unavoidable bitconditions for all listed DVs
-// it returns a dvmask where each bit belonging to a DV is set if all unavoidable bitconditions for that DV have been met
-// thus one needs to do the recompression check for each DV that has its bit set
-*/
-
-#ifndef SHA1DC_UBC_CHECK_H
-#define SHA1DC_UBC_CHECK_H
-
-#if defined(__cplusplus)
-extern "C" {
-#endif
-
-#ifndef SHA1DC_NO_STANDARD_INCLUDES
-#include <stdint.h>
-#endif
-
-#define DVMASKSIZE 1
-typedef struct { int dvType; int dvK; int dvB; int testt; int maski; int maskb; uint32_t dm[80]; } dv_info_t;
-extern dv_info_t sha1_dvs[];
-void ubc_check(const uint32_t W[80], uint32_t dvmask[DVMASKSIZE]);
-
-#define DOSTORESTATE58
-#define DOSTORESTATE65
-
-#define CHECK_DVMASK(_DVMASK) (0 != _DVMASK[0])
-
-#if defined(__cplusplus)
-}
-#endif
-
-#ifdef SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_H
-#include SHA1DC_CUSTOM_TRAILING_INCLUDE_UBC_CHECK_H
-#endif
-
-#endif
-- 
2.13.0.303.g4ebf302169