Merge branch 'simd' of https://github.com/cr-marcstevens/sha1collisiondetection into simd

4 files changed, 346 insertions, 1 deletions

diff --git a/.gitignore b/.gitignore
index a6ad674..fcf0f50 100644
--- a/.gitignore
+++ b/.gitignore
@@ -31,6 +31,8 @@
 #sha1 collision detection specific config files.
 Makefile.config
 lib/simd/config.h
+lib/simd/dvs_simd.c
+lib/simd/dvs_simd.h
 
 # sha1 collision detection specific build directories
 bin/
diff --git a/Makefile b/Makefile
index df49583..5a719c0 100644
--- a/Makefile
+++ b/Makefile
@@ -32,6 +32,8 @@ endif
 
 LIBCOMPAT=1:0:0
 
+SIMD_MAX_DVS=32
+
 PREFIX ?= /usr/local
 BINDIR=$(PREFIX)/bin
 LIBDIR=$(PREFIX)/lib
@@ -92,7 +94,7 @@ SRC_OBJ_DIR=obj_src
 
 H_DEP:=$(shell find . -type f -name "*.h")
 FS_LIB=$(wildcard $(LIB_DIR)/*.c)
-FS_SRC=$(wildcard $(SRC_DIR)/*.c)
+FS_SRC=$(wildcard $(SRC_DIR)/main.c)
 FS_SIMD_LIB=
 
 ifeq ($(HAVE_SIMD),1)
@@ -235,6 +237,13 @@ bin/sha1dcsum_partialcoll: $(FS_OBJ_SRC) bin/libsha1detectcoll.$(LIB_EXT)
 	$(LD) $(LDFLAGS) $(FS_OBJ_SRC) -Lbin -lsha1detectcoll -o bin/sha1dcsum_partialcoll
 
 
+bin/simd_table_gen: $(SRC_OBJ_DIR)/simd_table_gen.lo
+	$(LD) $(LDFLAGS) $< -o $@
+
+.PHONY: gen_simd_tables
+gen_simd_tables: bin/simd_table_gen
+	$< src/DV_data.txt $(SIMD_MAX_DVS)
+
 $(SRC_DEP_DIR)/%.d: $(SRC_DIR)/%.c
 	$(MKDIR) $(shell dirname $@)
 	$(CC_DEP) $(CFLAGS) -M -MF $@ $<
diff --git a/src/DV_data.txt b/src/DV_data.txt
new file mode 100644
index 0000000..1aa49a9
--- /dev/null
+++ b/src/DV_data.txt
@@ -0,0 +1,32 @@
+I_48_0 : compl=2^64.5138 (prob=2^-71.5138)
+II_46_0 : compl=2^65.0808 (prob=2^-72.0808)
+I_50_0 : compl=2^65.2793 (prob=2^-72.2793)
+I_49_0 : compl=2^65.4313 (prob=2^-72.4313)
+II_51_0 : compl=2^65.7008 (prob=2^-72.7008)
+II_52_0 : compl=2^65.7008 (prob=2^-72.7008)
+I_51_0 : compl=2^66.4313 (prob=2^-73.4313)
+II_50_0 : compl=2^66.8464 (prob=2^-73.8464)
+II_53_0 : compl=2^67.1862 (prob=2^-74.1862)
+I_48_2 : compl=2^67.1887 (prob=2^-74.1887)
+II_54_0 : compl=2^67.5081 (prob=2^-74.5081)
+I_49_2 : compl=2^67.5424 (prob=2^-74.5424)
+II_56_0 : compl=2^68.0342 (prob=2^-75.0342)
+II_45_0 : compl=2^68.2508 (prob=2^-75.2508)
+I_47_0 : compl=2^68.2793 (prob=2^-75.2793)
+I_50_2 : compl=2^68.3904 (prob=2^-75.3904)
+II_49_0 : compl=2^68.4075 (prob=2^-75.4075)
+II_55_0 : compl=2^68.8707 (prob=2^-75.8707)
+II_48_0 : compl=2^68.8788 (prob=2^-75.8788)
+II_47_0 : compl=2^68.9288 (prob=2^-75.9288)
+I_46_0 : compl=2^69.0163 (prob=2^-76.0163)
+I_52_0 : compl=2^69.2938 (prob=2^-76.2938)
+II_50_2 : compl=2^69.8967 (prob=2^-76.8967)
+I_51_2 : compl=2^70.32 (prob=2^-77.32)
+I_47_2 : compl=2^70.3904 (prob=2^-77.3904)
+I_45_0 : compl=2^70.4858 (prob=2^-77.4858)
+I_44_0 : compl=2^70.5424 (prob=2^-77.5424)
+II_51_2 : compl=2^70.5488 (prob=2^-77.5488)
+I_43_0 : compl=2^70.7939 (prob=2^-77.7939)
+II_46_2 : compl=2^71.0834 (prob=2^-78.0834)
+II_49_2 : compl=2^71.4638 (prob=2^-78.4638)
+I_46_2 : compl=2^71.9257 (prob=2^-78.9257)
diff --git a/src/simd_table_gen.c b/src/simd_table_gen.c
new file mode 100644
index 0000000..1c73cbc
--- /dev/null
+++ b/src/simd_table_gen.c
@@ -0,0 +1,302 @@
+/***
+* 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
+***/
+
+#define MAX_SIMD_EXPONENT (4) /* max SIMD width 2^4=16 in words */
+
+#define SIMD_MAX_WORD_ALIGNMENT (4) /* max alignment required is 4 words (even for 16 word vectors) */
+#define SIMD_MAX_CASE_PADDING (0) /* max padding between cases in words to try to improve alignment */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdint.h>
+
+typedef struct
+{
+	int dvType; 
+	int dvK; 
+	int dvB; 
+	int ok58;
+	int ok65;
+	uint32_t dv[80];
+	uint32_t dm[80];
+} DV_info_t;
+
+static uint32_t rotate_left(uint32_t x, unsigned n) { return (x<<n)|(x>>(32-n)); }
+static uint32_t rotate_right(uint32_t x, unsigned n) { return (x>>n)|(x<<(32-n)); }
+
+void expand_me(uint32_t v[80], int offset)
+{
+	int i;
+	for (i = offset - 1; i >= 0; --i)
+		v[i] = rotate_right(v[i+16], 1) ^ v[i+13] ^ v[i+8] ^ v[i+2];
+	for (i = offset + 16; i < 80; ++i)
+		v[i] = rotate_left( v[i-3] ^ v[i-8] ^ v[i-14] ^ v[i-16], 1);
+}
+
+void init_DV(DV_info_t* DV)
+{
+	int i;
+	int K = DV->dvK, B = DV->dvB, T = DV->dvType;
+	uint32_t* dv = DV->dv;
+	uint32_t* dm = DV->dm;
+
+	/* initialize 16 words of dv */
+	for (i = 0; i < 80; ++i)
+		DV->dv[i] = 0;
+	DV->dv[K+15] = 1 << B;
+	if (T == 2)
+	{
+		DV->dv[K+1] = 1 << ((31+B) & 31);
+		DV->dv[K+3] = 1 << ((31+B) & 31);
+	}
+	/* expand to entire dv */
+	expand_me(dv, K);
+
+	/* initialize 16 words of dm */
+	for (i = 16; i < 32; ++i)
+		dm[i] = dv[i-0] ^ rotate_left(dv[i-1],5) ^ dv[i-2]
+			 ^ rotate_left(dv[i-3],30) ^ rotate_left(dv[i-4],30) ^ rotate_left(dv[i-5],30);
+	/* expand to entire dm */
+	expand_me(dm, 16);
+}
+
+int parse_error(char* str)
+{
+	fprintf(stderr, "Parse error: %s", str);
+	return 1;
+}
+
+int eval_align(int off1, int len1, int off2, int len2)
+{
+	int i, j, weight = 0, maxalign;
+	int newoff;
+	for (j = 1; j <= MAX_SIMD_EXPONENT; ++j)
+	{
+		maxalign = (1<<j);
+		if (maxalign > SIMD_MAX_WORD_ALIGNMENT)
+			maxalign = SIMD_MAX_WORD_ALIGNMENT;
+
+		newoff = off1 & ~(maxalign-1);
+		for (i = newoff; i < off1 + len1; i += 1<<j)
+			++weight;
+
+		newoff = off2 & ~(maxalign-1);
+		for (i = newoff; i < off2 + len2; i += 1<<j)
+			++weight;
+	}
+	return weight;
+}
+
+int generate_code(DV_info_t* DVS, int nrdvs)
+{
+	int i,j;
+	int totok58 = 0, totok65 = 0;
+	int overlap, bestoverlap, bestweight, cnt58, cnt65, weight;
+	int best58first = 0, bestpadding = 0, endpadding;
+	FILE* fd;
+
+	/* Compute overlap */
+	for (i = 0; i < nrdvs; ++i)
+	{
+		totok58 += DVS[i].ok58;
+		totok65 += DVS[i].ok65;
+	}
+	printf("totDVs=%i totok58=%i totok65=%i\n", nrdvs, totok58, totok65);
+
+	overlap = totok58 + totok65 - nrdvs;
+	if (overlap < 0) parse_error("overlap negative");
+
+	/* Analyze best division */
+	bestoverlap = 0;
+	bestweight = 1<<20;
+	printf("\nAnalyzing overlap:\n");
+	for (i = 0; i <= overlap; ++i)
+	{
+		cnt58 = totok58 - overlap + i;
+		cnt65 = totok65 - i;
+		weight = 0;
+		for (j = 1; j <= MAX_SIMD_EXPONENT; ++j)
+			weight += ((cnt58+(1<<j)-1)>>j) + ((cnt65+(1<<j)-1)>>j);
+		printf("cnt58=%i cnt65=%i weight=%i\n", cnt58, cnt65, weight);
+		if (weight < bestweight)
+		{
+			bestoverlap = i;
+			bestweight = weight;
+		}
+	}
+	cnt58 = totok58 - overlap + bestoverlap;
+	cnt65 = totok65 - bestoverlap;
+
+	printf("Using cnt58=%i cnt65=%i weight=%i\n", cnt58, cnt65, bestweight);
+
+	/* Apply best division */
+	j = bestoverlap;
+	for (i = 0; i < nrdvs; ++i)
+	{
+		if (DVS[i].ok58 + DVS[i].ok65 == 2)
+		{
+			if (j > 0)
+			{
+				DVS[i].ok65 = 0;
+				--j;
+			}
+			else
+			{
+				DVS[i].ok58 = 0;
+			}
+		}
+	}
+
+	bestweight = 1<<20;
+	best58first = 1;
+	bestpadding = 0;	
+	for (i = 0; i < SIMD_MAX_WORD_ALIGNMENT && i <= SIMD_MAX_CASE_PADDING; ++i)
+	{
+		weight = eval_align(0, cnt58, cnt58+i, cnt65);
+		printf("Eval align %i %i %i = %i\n", cnt58, i, cnt65, weight);
+		if (weight < bestweight)
+		{
+			best58first = 1;
+			bestpadding = i;
+			bestweight = weight;
+		}
+
+		weight = eval_align(0, cnt65, cnt65+i, cnt58);
+		printf("Eval align %i %i %i = %i\n", cnt65, i, cnt58, weight);
+		if (weight < bestweight)
+		{
+			best58first = 0;
+			bestpadding = i;
+			bestweight = weight;
+		}
+	}
+	/* TODO: compute better endpadding based on MAX_SIMD_WORD_ALIGNMENT instead of 1<<MAX_SIMD_EXPONENT */
+	endpadding = ((1<<20) - (cnt58 + cnt65 + bestpadding)) & ((1<<MAX_SIMD_EXPONENT)-1);
+	if (best58first)
+	{
+		printf("Using case58(%i) padding(%i) case65(%i) padding(%i)\n", cnt58, bestpadding, cnt65, endpadding);
+	} else {
+		printf("Using case65(%i) padding(%i) case58(%i) padding(%i)\n", cnt65, bestpadding, cnt58, endpadding);
+	}
+
+	/* Output code */
+	fd = fopen("lib/simd/dvs_simd.h", "w");
+	if (fd == NULL)
+		parse_error("Cannot open output file to write");
+	fprintf(fd, 
+		"/***\n"
+		"* Copyright 2017 Marc Stevens <marc@marc-stevens.nl>, Dan Shumow <danshu@microsoft.com>\n"
+		"* Distributed under the MIT Software License.\n"
+		"* See accompanying file LICENSE.txt or copy at\n"
+		"* https://opensource.org/licenses/MIT\n"
+		"***/\n\n"
+		"#include <stdlib.h>\n"
+		"#include <stdint.h>\n"
+		"#define SHA1DC_SIMD_NRDVS (%i)\n"
+		"#define SHA1DC_SIMD_TABLESIZE (%i)\n"
+		"extern uint32_t sha1_dm_interleaved[80][SHA1DC_SIMD_TABLESIZE];\n"
+		, nrdvs, nrdvs+16);
+
+	fclose(fd);
+	fd = fopen("lib/simd/dvs_simd.c", "w");
+	if (fd == NULL)
+		parse_error("Cannot open output file to write");
+	fprintf(fd, 
+		"/***\n"
+		"* Copyright 2017 Marc Stevens <marc@marc-stevens.nl>, Dan Shumow <danshu@microsoft.com>\n"
+		"* Distributed under the MIT Software License.\n"
+		"* See accompanying file LICENSE.txt or copy at\n"
+		"* https://opensource.org/licenses/MIT\n"
+		"***/\n\n"
+		"#include \"dvs_simd.h\"\n"
+		"#include <stdlib.h>\n"
+		"#include <stdint.h>\n"
+		);
+	fclose(fd);
+	
+	return 0;
+}
+
+int process_dv_list(char* filename, int maxDVs)
+{
+	FILE* fd;
+	char buffer[1<<16];
+	size_t size;
+	char* ptr;
+	char* ptrend;
+	DV_info_t DVS[256];
+	int nrdvs = 0;
+	DV_info_t* DV = DVS+0;
+	char* DVtypestr[3] = { "err", "I", "II" };
+	int K;
+
+	fd = fopen(filename, "r");
+	if (fd == NULL)
+		return parse_error("Cannot open file");
+	size = fread(buffer,1,65536,fd);
+	if (size >= 65536)
+		return parse_error("File larger than 65536 bytes!");
+	printf("Parsing at most %i DVs...\n", maxDVs);
+
+	ptrend = buffer+size;
+	for (ptr = buffer; ptr < ptrend;)
+	{
+		/* I_48_0 : compl=2^64.5138 (prob=2^-71.5138) */
+
+		DV->dvType = 0;
+
+		while (ptr < ptrend && *ptr != 'I')
+			++ptr;
+		if (ptr >= ptrend)
+			break;
+		for (; *ptr == 'I'; ++ptr,++DV->dvType)
+			;
+		if (DV->dvType > 2) return parse_error("there is no DV type III");
+		if (*ptr++ != '_') return parse_error("expected _ after I");
+		K = DV->dvK = atoi(ptr);
+		ptr += 2;
+		if (*ptr++ != '_') return parse_error("expected _ after K");
+		DV->dvB = atoi(ptr);
+
+		/* compute dv and dm tables in DV */
+		init_DV(DV);
+
+                if (DV->dvType == 1)
+                {
+			DV->ok58 = ((58 >= K+5) & (58 <= K+15)) ? 1 : 0;
+			DV->ok65 = ((65 >= K+5) & (65 <= K+15)) ? 1 : 0;
+                }
+                else
+                {
+			DV->ok58 = ((58 >= K+9) & (58 <= K+15)) ? 1 : 0;
+			DV->ok65 = ((65 >= K+9) & (65 <= K+15)) ? 1 : 0;
+                }
+
+		printf("Parsed DV: %s(%i,%i) ok58=%i ok65=%i\n", DVtypestr[DV->dvType], DV->dvK, DV->dvB, DV->ok58, DV->ok65);
+
+		++DV; ++nrdvs;
+		if (DV != DVS+nrdvs)
+			parse_error("huh?!?");
+		if (nrdvs >= maxDVs)
+			break;		
+	}
+	fclose(fd);
+	return generate_code(DVS, nrdvs);
+}
+
+int main(int argc, char** argv)
+{
+	if (argc < 2)
+	{
+		printf("Usage: %s <file> [<nr>]\n", argv[0]);
+		return 1;
+	}
+	if (argc == 2)
+		return process_dv_list(argv[1],256);
+	else
+		return process_dv_list(argv[1],atoi(argv[2]));
+}