From 13a01ffb27f58d24dae8dc56c1ef75f1743cca27 Mon Sep 17 00:00:00 2001 From: Stella Lau Date: Wed, 19 Jul 2017 17:24:09 -0700 Subject: [PATCH] Fix off-by-one in size calculations --- contrib/long_distance_matching/circular_buffer_table.c | 3 ++- contrib/long_distance_matching/ldm.c | 6 +++--- contrib/long_distance_matching/ldm.h | 2 +- contrib/long_distance_matching/ldm_with_table.c | 8 ++++---- 4 files changed, 10 insertions(+), 9 deletions(-) diff --git a/contrib/long_distance_matching/circular_buffer_table.c b/contrib/long_distance_matching/circular_buffer_table.c index 9429fbcde..ad7ae9e10 100644 --- a/contrib/long_distance_matching/circular_buffer_table.c +++ b/contrib/long_distance_matching/circular_buffer_table.c @@ -11,7 +11,8 @@ #define HASH_BUCKET_SIZE (1 << (HASH_BUCKET_SIZE_LOG)) // TODO: rename. Number of hash buckets. -#define LDM_HASHLOG ((LDM_MEMORY_USAGE)-4-HASH_BUCKET_SIZE_LOG) +// TODO: Link to HASH_ENTRY_SIZE_LOG +#define LDM_HASHLOG ((LDM_MEMORY_USAGE)-3-(HASH_BUCKET_SIZE_LOG)) //#define ZSTD_SKIP struct LDM_hashTable { diff --git a/contrib/long_distance_matching/ldm.c b/contrib/long_distance_matching/ldm.c index 6e9addf73..9ffbab48d 100644 --- a/contrib/long_distance_matching/ldm.c +++ b/contrib/long_distance_matching/ldm.c @@ -6,12 +6,12 @@ #define LDM_HASHTABLESIZE (1 << (LDM_MEMORY_USAGE)) -//#define LDM_HASH_ENTRY_SIZE 4 +#define LDM_HASH_ENTRY_SIZE_LOG 3 #define LDM_HASHTABLESIZE_U32 ((LDM_HASHTABLESIZE) >> 2) -#define LDM_HASHTABLESIZE_U64 ((LDM_HASHTABLESIZE) >> 4) +#define LDM_HASHTABLESIZE_U64 ((LDM_HASHTABLESIZE) >> 3) // Insert every (HASH_ONLY_EVERY + 1) into the hash table. -#define HASH_ONLY_EVERY_LOG (LDM_WINDOW_SIZE_LOG-((LDM_MEMORY_USAGE) - 4)) +#define HASH_ONLY_EVERY_LOG (LDM_WINDOW_SIZE_LOG-((LDM_MEMORY_USAGE) - (LDM_HASH_ENTRY_SIZE_LOG))) #define HASH_ONLY_EVERY ((1 << HASH_ONLY_EVERY_LOG) - 1) #define ML_BITS 4 diff --git a/contrib/long_distance_matching/ldm.h b/contrib/long_distance_matching/ldm.h index 1d5b2f13b..04b6410c2 100644 --- a/contrib/long_distance_matching/ldm.h +++ b/contrib/long_distance_matching/ldm.h @@ -13,7 +13,7 @@ // Defines the size of the hash table. // Note that this is not the number of buckets. // Currently this should be less than WINDOW_SIZE_LOG + 4? -#define LDM_MEMORY_USAGE 23 +#define LDM_MEMORY_USAGE 22 #define HASH_BUCKET_SIZE_LOG 3 // MAX is 4 for now // Defines the lag in inserting elements into the hash table. diff --git a/contrib/long_distance_matching/ldm_with_table.c b/contrib/long_distance_matching/ldm_with_table.c index 5919d588c..813ead6ae 100644 --- a/contrib/long_distance_matching/ldm_with_table.c +++ b/contrib/long_distance_matching/ldm_with_table.c @@ -7,17 +7,17 @@ #include "ldm.h" #define LDM_HASHTABLESIZE (1 << (LDM_MEMORY_USAGE)) -//#define LDM_HASH_ENTRY_SIZE 4 +#define LDM_HASH_ENTRY_SIZE_LOG 3 #define LDM_HASHTABLESIZE_U32 ((LDM_HASHTABLESIZE) >> 2) -#define LDM_HASHTABLESIZE_U64 ((LDM_HASHTABLESIZE) >> 4) +#define LDM_HASHTABLESIZE_U64 ((LDM_HASHTABLESIZE) >> 3) // Insert every (HASH_ONLY_EVERY + 1) into the hash table. -#define HASH_ONLY_EVERY_LOG (LDM_WINDOW_SIZE_LOG-((LDM_MEMORY_USAGE) - 4)) +#define HASH_ONLY_EVERY_LOG (LDM_WINDOW_SIZE_LOG-((LDM_MEMORY_USAGE) - (LDM_HASH_ENTRY_SIZE_LOG))) #define HASH_ONLY_EVERY ((1 << HASH_ONLY_EVERY_LOG) - 1) /* Hash table stuff. */ #define HASH_BUCKET_SIZE (1 << (HASH_BUCKET_SIZE_LOG)) -#define LDM_HASHLOG ((LDM_MEMORY_USAGE)-4-HASH_BUCKET_SIZE_LOG) +#define LDM_HASHLOG ((LDM_MEMORY_USAGE)-(LDM_HASH_ENTRY_SIZE_LOG)-(HASH_BUCKET_SIZE_LOG)) #define ML_BITS 4 #define ML_MASK ((1U<