summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lcs.c10
-rw-r--r--lcs_sse.c5
-rw-r--r--runner.c199
3 files changed, 108 insertions, 106 deletions
diff --git a/lcs.c b/lcs.c
index 2ea6f87..17d80e9 100644
--- a/lcs.c
+++ b/lcs.c
@@ -3,7 +3,7 @@
*/
#include <stdlib.h>
#include <string.h>
-
+#include "arpa/inet.h"
unsigned char tbuf[32] __attribute__((aligned(32)));
#if 0
@@ -106,8 +106,7 @@ LCS(uint32, 32, 32)
LCS(uint32, 32, 28)
-#ifdef USE_LCS4
-int lcs_32_rough(unsigned char *str1, unsigned char *str2) {
+int lcs_32_rough_4(unsigned char *str1, unsigned char *str2) {
int max_length = 0;
int max_length_next = 0;
int offset;
@@ -119,7 +118,6 @@ int lcs_32_rough(unsigned char *str1, unsigned char *str2) {
}
return max_length;
}
-#endif
#endif
@@ -157,9 +155,6 @@ int lcs_32_rough(unsigned char *str1, unsigned char *str2) {
}
#endif
-#ifdef USE_PRE_LCS
-#include "arpa/inet.h"
-
int lcs_upper_bound(const uint32_t * const str1_int, const uint32_t * const str2_int) {
static char contains[256] = {0};
const unsigned char * const str1 = (const unsigned char * const)str1_int;
@@ -217,7 +212,6 @@ int lcs_upper_bound(const uint32_t * const str1_int, const uint32_t * const str2
return ret;
}
-#endif
/* Exact lcs implementation */
typedef unsigned char uchar;
diff --git a/lcs_sse.c b/lcs_sse.c
index 487aef2..c8d0675 100644
--- a/lcs_sse.c
+++ b/lcs_sse.c
@@ -36,9 +36,7 @@
"and %%edx, %%ecx\n\t" \
"or %%ecx, %0\n\t" \
-#ifdef USE_LCS5
-
-int lcs_32_rough(const uint32_t * const str1, const uint32_t * const str2) {
+int lcs_32_rough_5(const uint32_t * const str1, const uint32_t * const str2) {
register unsigned int x;
#ifndef __SSE3__
@@ -155,4 +153,3 @@ int lcs_32_rough(const uint32_t * const str1, const uint32_t * const str2) {
return ((x != 0) ? 8 : 0);
}
-#endif
diff --git a/runner.c b/runner.c
index 2960cee..9c763ac 100644
--- a/runner.c
+++ b/runner.c
@@ -8,9 +8,35 @@
#include "md5.c"
#define MD5_DIGEST_LENGTH 16
-#define USE_ROUGH
-//#define TESTING
-//#define SINGLERUN
+#ifndef USE_PRE_LCS
+#define USE_PRE_LCS 1
+#endif
+
+#ifndef USE_ROUGH
+#define USE_ROUGH 1
+#endif
+
+#ifndef SINGLERUN
+# define SINGLERUN 0
+#endif
+
+#ifndef TESTING
+# define TESTING 0
+#endif
+
+#ifndef USE_ROUGH_LCS
+# ifdef USE_LCS4
+# define USE_ROUGH_LCS 4
+# endif
+# ifdef USE_LCS5
+# define USE_ROUGH_LCS 5
+# endif
+
+# ifndef USE_ROUGH_LCS
+# error You need to specify which rough LCS implementation to use with USE_ROUGH_LCS=5 or the like
+# endif
+#endif
+
//#define PEDANTIC
#ifndef BENCH_VAL
#define BENCH_VAL 8000000
@@ -23,13 +49,29 @@
#if BYTE_ORDER == LITTLE_ENDIAN
-#define BE_BYTE_INDEX(i) (i^3)
-#define LE_BYTE_INDEX(i) (i)
+# define BE_BYTE_INDEX(i) (i^3)
+# define LE_BYTE_INDEX(i) (i)
#elif BYTE_ORDER == BIG_ENDIAN
-#define BE_BYTE_INDEX(i) (i)
-#define LE_BYTE_INDEX(i) (i^3)
+# define BE_BYTE_INDEX(i) (i)
+# define LE_BYTE_INDEX(i) (i^3)
+#else
+# error Unknown endianness
+#endif
+
+#ifdef PEDANTIC
+// use similar to "assert(a >= b);"
+# define PEDANTIC_TEST_GTE(a, b) {if ((a) < (b)) printf("Pedantic test failed (%s:%d): %s\n failed: %s (%d) >= %s (%d)\n", __FILE__, __LINE__, input_hex, #a, a, #b, b);}
+#else
+# define PEDANTIC_TEST_GTE(a, b)
+#endif
+
+#ifdef TIMINGS
+ unsigned long long t0, t1;
+# define TIMINGS_START() (t0 = rdtsc())
+# define TIMINGS_END(str) {t1 = rdtsc(); if (i % 1000000 == 0) printf(str "=%llu\n", (t1-t0-63));}
#else
-#error Unknown endianness
+# define TIMINGS_START()
+# define TIMINGS_END(str)
#endif
unsigned char tbl[512];
@@ -166,15 +208,15 @@ int main() {
printf("%p %p %p\n", desttohex, input_hex, tbl);
/* Generate a random start point */
-#ifdef TESTING
- memcpy(input_raw, test_input, MD5_DIGEST_LENGTH);
-#else
- srandomdev();
- for(i=0; i<16; i++) {
- input_raw[i] = random() & 0xff;
+ if (TESTING) {
+ memcpy(input_raw, test_input, MD5_DIGEST_LENGTH);
+ } else {
+ srandomdev();
+ for(i=0; i<16; i++) {
+ input_raw[i] = random() & 0xff;
+ }
+ i = 0;
}
- i = 0;
-#endif
tohex(input_raw);
memcpy((char *)input_hex, (char *)desttohex, 32);
printf("Starting at ");
@@ -188,108 +230,77 @@ int main() {
/* Loop */
start_stopwatch();
while (1) {
-#ifdef TIMINGS
- t0 = rdtsc();
-#endif
+ TIMINGS_START();
raw_MD5_64(input_hex, desttohex);
-#ifdef TIMINGS
- t1 = rdtsc();
- if (i % 1000000 == 0) printf("md5=%llu\n", (t1-t0-63));
-#endif
+ TIMINGS_END("md5");
-#ifdef USE_PRE_LCS
- int pre_n = lcs_upper_bound((uint32_t*)input_raw, (uint32_t*)global_md5.abcd);
- if (pre_n >= MSF) {
+#ifdef PEDANTIC
+ const int pedantic_n = lcs_uchar_32_32(input_hex, desttohex);
#endif
-#ifdef USE_ROUGH
-#ifdef TIMINGS
- t0 = rdtsc();
-#endif
-#ifdef USE_LCS4
- n = lcs_32_rough(input_hex, desttohex);
-#else
- n = lcs_32_rough((uint32_t*)input_raw, (uint32_t*)global_md5.abcd);
-#endif
-#ifdef TIMINGS
- t1 = rdtsc();
- if (i % 1000000 == 0) printf("rough=%llu\n", (t1-t0-63));
-#endif
- /* Based on testing, the 'rough' match may undercount by up to 6
- * characters (for an int32-based implementation). It now returns
- * 1/4th the length of the match it found, so it will return >0 if
- * there is a match of 7 or greater, and sometimes return >0 if there
- * is a match of 4 or greater.
- */
- if (n > 0) {
+ do {
+ if (USE_PRE_LCS) {
+ n = lcs_upper_bound((uint32_t*)input_raw, (uint32_t*)global_md5.abcd);
+ PEDANTIC_TEST_GTE(n, pedantic_n);
+ if (n < MSF)
+ break;
+ }
+
+ if (USE_ROUGH) {
+ TIMINGS_START();
+ if (USE_ROUGH_LCS == 4)
+ n = lcs_32_rough_4(input_hex, desttohex);
+ else if (USE_ROUGH_LCS == 5)
+ n = lcs_32_rough_5((uint32_t*)input_raw, (uint32_t*)global_md5.abcd);
+ else
+ assert(0);
+ TIMINGS_END("rough");
+
+ /* Based on testing, the 'rough' match may undercount by up to 6
+ * characters (for an int32-based implementation). It now returns
+ * 1/4th the length of the match it found, so it will return >0 if
+ * there is a match of 7 or greater, and sometimes return >0 if there
+ * is a match of 4 or greater.
+ */
+ n = n * 4 + 6;
+ PEDANTIC_TEST_GTE(n, pedantic_n);
+ if (n < MSF)
+ break;
+ }
+
possible_matches++;
-#ifdef TIMINGS
- t0 = rdtsc();
-#endif
+ TIMINGS_START();
n = lcs_uchar_32_32(input_hex, desttohex); /* get the exact number */
-#ifdef TIMINGS
- t1 = rdtsc();
-#endif
- if (n >= MSF) {
-#ifndef SINGLERUN
-#ifdef TIMINGS
- printf("full=%llu\n", (t1-t0-63));
-#endif
+ TIMINGS_END("full");
+ if (n < MSF)
+ break;
+
+ matches_found++;
+ if (!SINGLERUN) {
print_input_hex();
printf(" %s %d\n", desttohex, n);
fflush(stdout);
-#endif
- matches_found++;
-#ifdef PEDANTIC
- } else {
- n = lcs_uchar_32_32(input_hex, desttohex);
- if(n >= MSF) {
- print_input_hex();
- printf(" %d FALSE NEGATIVE1\n", n);
- }
-#endif
- }
-
-#ifdef PEDANTIC
- } else {
- n = lcs_uchar_32_32(input_hex, desttohex);
- if(n >= MSF) {
- printf("%s %d FALSE NEGATIVE2\n", input_hex, n);
}
-#endif
- }
-#else
- n = lcs_32(input_hex, desttohex);
- if (n >= MSF) {
- print_input_hex();
- printf(" %s %d\n", desttohex, n);
- fflush(stdout);
- }
-#endif
-
-#ifdef USE_PRE_LCS
- }
-#endif
+ } while (0);
/* keep us updated on speed */
i++;
if (i == BENCH_VAL) {
unsigned long elapsed = stop_stopwatch();
printf("Benchmark: %dK/s (found %d matches and %d false matches in %d processed)\n", (int) ((float)BENCH_VAL * 1000 / elapsed), matches_found, possible_matches - matches_found, i);
-#ifdef SINGLERUN
- printf("%d processed in %ld us\n", BENCH_VAL, elapsed);
-#endif
+ if (SINGLERUN)
+ printf("%d processed in %ld us\n", BENCH_VAL, elapsed);
fflush(stdout);
/* don't include the time it takes us to print out the benchmark */
start_stopwatch();
i = 0;
matches_found = 0;
possible_matches = 0;
-#ifdef SINGLERUN
- return 0;
-#endif
+ if (SINGLERUN)
+ return 0;
}
inc_input();
}
return 0;
}
+
generated by cgit v1.2.3-54-g00ecf (git 2.45.0) at 2024-05-13 06:18:38 +0000