diff options
| author | Eric Anderson <ejona86@gmail.com> | 2010-12-26 09:40:15 -0600 |
|---|---|---|
| committer | Eric Anderson <ejona86@gmail.com> | 2010-12-26 09:40:15 -0600 |
| commit | 3824e95334e06d9c1309591e7a040dc7b4049ff5 (patch) | |
| tree | cbd8bdb774ba2c467e9a7223ef25d6bf35398452 | |
| parent | fbe623251cc4c8ebcab2cd7c6a4e8e2c9a5f6ed7 (diff) | |
| download | md5game-3824e95334e06d9c1309591e7a040dc7b4049ff5.tar.gz md5game-3824e95334e06d9c1309591e7a040dc7b4049ff5.zip | |
Only add one to lcs_upper_bound or don't do the second sum.
The DO_SECOND_SUM define has reduced false positives, but without it has a
reasonable amount less work. Thus, you must empirically test to find which has
the best boost. Right now, DO_SECOND_SUM is faster.
| -rw-r--r-- | lcs.c | 25 |
1 files changed, 20 insertions, 5 deletions
@@ -158,15 +158,22 @@ int lcs_32_rough(unsigned char *str1, unsigned char *str2) { #endif #ifdef USE_PRE_LCS +#define DO_SECOND_SUM + +#ifdef DO_SECOND_SUM #include "arpa/inet.h" +#endif + int lcs_upper_bound(const uint32_t * const str1_int, const uint32_t * const str2_int) { static char contains[256] = {0}; - uint32_t bo_str2_int[4]; - uint32_t shifted_str2_int[4]; const unsigned char * const str1 = (const unsigned char * const)str1_int; const unsigned char * const str2 = (const unsigned char * const)str2_int; + int first_sum; +#ifdef DO_SECOND_SUM + uint32_t bo_str2_int[4]; + uint32_t shifted_str2_int[4]; const unsigned char * const str2_r = (const unsigned char * const)shifted_str2_int; - int first_sum, second_sum; + int second_sum; bo_str2_int[0] = ntohl(str2_int[0]); bo_str2_int[1] = ntohl(str2_int[1]); @@ -177,6 +184,7 @@ int lcs_upper_bound(const uint32_t * const str1_int, const uint32_t * const str2 shifted_str2_int[1] = (bo_str2_int[1] << 4) | (bo_str2_int[2] >> 28); shifted_str2_int[2] = (bo_str2_int[2] << 4) | (bo_str2_int[3] >> 28); shifted_str2_int[3] = (bo_str2_int[3] << 4) | (bo_str2_int[0] >> 28); +#endif contains[str1[0]] = contains[str1[1]] = contains[str1[2]] = contains[str1[3]] = contains[str1[4]] = contains[str1[5]] @@ -192,12 +200,14 @@ int lcs_upper_bound(const uint32_t * const str1_int, const uint32_t * const str2 + contains[str2[12]] + contains[str2[13]] + contains[str2[14]] + contains[str2[15]]; +#ifdef DO_SECOND_SUM second_sum = contains[str2_r[0]] + contains[str2_r[1]] + contains[str2_r[2]] + contains[str2_r[3]] + contains[str2_r[4]] + contains[str2_r[5]] + contains[str2_r[6]] + contains[str2_r[7]] + contains[str2_r[8]] + contains[str2_r[9]] + contains[str2_r[10]] + contains[str2_r[11]] + contains[str2_r[12]] + contains[str2_r[13]] + contains[str2_r[14]] + contains[str2_r[15]]; +#endif contains[str1[0]] = contains[str1[1]] = contains[str1[2]] = contains[str1[3]] = contains[str1[4]] = contains[str1[5]] @@ -206,8 +216,13 @@ int lcs_upper_bound(const uint32_t * const str1_int, const uint32_t * const str2 = contains[str1[12]] = contains[str1[13]] = contains[str1[14]] = contains[str1[15]] = 0; - // can be off up to two nibbles - return MAX(first_sum, second_sum) * 2 + 2; +#ifdef DO_SECOND_SUM + // can be off up to one nibble (e.g., "1110" and "2111") + return MAX(first_sum, second_sum) * 2 + 1; +#else + // can be off up to two nibbles (e.g., "0110" and "1122") + return first_sum * 2 + 2; +#endif } #endif |