From ff2d93e1b4ea34ddaa42be5e9c987861849e4b2b Mon Sep 17 00:00:00 2001 From: Eric Anderson Date: Sun, 26 Dec 2010 10:09:03 -0600 Subject: Auto-choose at runtime to do second sum in lcs_upper_bound This has no impact for non-DO_SECOND_SUM, but puts DO_SECOND_SUM less than a percent behind. --- lcs.c | 54 +++++++++++++++++++++++++++--------------------------- 1 file changed, 27 insertions(+), 27 deletions(-) diff --git a/lcs.c b/lcs.c index d296ea7..b971c79 100644 --- a/lcs.c +++ b/lcs.c @@ -170,22 +170,6 @@ int lcs_upper_bound(const uint32_t * const str1_int, const uint32_t * const str2 const unsigned char * const str2 = (const unsigned char * const)str2_int; int first_sum; int ret; -#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 second_sum; - - bo_str2_int[0] = ntohl(str2_int[0]); - bo_str2_int[1] = ntohl(str2_int[1]); - bo_str2_int[2] = ntohl(str2_int[2]); - bo_str2_int[3] = ntohl(str2_int[3]); - - shifted_str2_int[0] = (bo_str2_int[0] << 4) | (bo_str2_int[1] >> 28); - 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]] @@ -201,19 +185,35 @@ 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]]; - - // can be off up to one nibble (e.g., "1110" and "2111") - ret = MAX(first_sum, second_sum) * 2 + 1; -#else // can be off up to two nibbles (e.g., "0110" and "1122") ret = first_sum * 2 + 2; +#ifdef DO_SECOND_SUM + if (ret >= MSF) { + 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 second_sum; + + bo_str2_int[0] = ntohl(str2_int[0]); + bo_str2_int[1] = ntohl(str2_int[1]); + bo_str2_int[2] = ntohl(str2_int[2]); + bo_str2_int[3] = ntohl(str2_int[3]); + + shifted_str2_int[0] = (bo_str2_int[0] << 4) | (bo_str2_int[1] >> 28); + 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); + + 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]]; + + // can be off up to one nibble (e.g., "1110" and "2111") + ret = MAX(first_sum, second_sum) * 2 + 1; + } #endif contains[str1[0]] = contains[str1[1]] = contains[str1[2]] -- cgit v1.2.3-54-g00ecf