From e0d3e07f0f5eefd13e86154a415405682a8c63c0 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Wed, 22 Oct 2008 11:52:10 +0200 Subject: [PATCH] add isl_set_get_hash --- include/isl_int.h | 18 +++++++++++++ include/isl_seq.h | 3 ++- include/isl_set.h | 2 ++ isl_gmp.c | 12 +++------ isl_map.c | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++--- isl_seq.c | 26 +++++++++++++------ 6 files changed, 116 insertions(+), 21 deletions(-) diff --git a/include/isl_int.h b/include/isl_int.h index 1ca200c..3445e55 100644 --- a/include/isl_int.h +++ b/include/isl_int.h @@ -77,6 +77,24 @@ typedef mpz_t isl_int; uint32_t isl_gmp_hash(mpz_t v, uint32_t hash); #define isl_int_hash(v,h) isl_gmp_hash(v,h) +#define isl_hash_init(h) (h = 2166136261u) +#define isl_hash_byte(h,b) do { \ + h *= 16777619; \ + h ^= b; \ + } while(0) +#define isl_hash_hash(h,h2) \ + do { \ + isl_hash_byte(h, (h2) & 0xFF); \ + isl_hash_byte(h, ((h2) >> 8) & 0xFF); \ + isl_hash_byte(h, ((h2) >> 16) & 0xFF); \ + isl_hash_byte(h, ((h2) >> 24) & 0xFF); \ + } while(0) +#define isl_hash_bits(h,bits) \ + ((bits) == 32) ? (h) : \ + ((bits) >= 16) ? \ + ((h) >> (bits)) ^ ((h) & (((uint32_t)1 << (bits)) - 1)) : \ + (((h) >> (bits)) ^ (h)) & (((uint32_t)1 << (bits)) - 1) + #if defined(__cplusplus) } #endif diff --git a/include/isl_seq.h b/include/isl_seq.h index 84a5ad2..961bafd 100644 --- a/include/isl_seq.h +++ b/include/isl_seq.h @@ -24,6 +24,7 @@ int isl_seq_abs_min_non_zero(isl_int *p, unsigned len); int isl_seq_eq(isl_int *p1, isl_int *p2, unsigned len); int isl_seq_is_neg(isl_int *p1, isl_int *p2, unsigned len); -uint32_t isl_seq_hash(isl_int *p, unsigned len, unsigned bits); +uint32_t isl_seq_get_hash(isl_int *p, unsigned len); +uint32_t isl_seq_get_hash_bits(isl_int *p, unsigned len, unsigned bits); #endif diff --git a/include/isl_set.h b/include/isl_set.h index 2e36a43..3f9e655 100644 --- a/include/isl_set.h +++ b/include/isl_set.h @@ -182,6 +182,8 @@ int isl_basic_set_dim_residue_class(struct isl_basic_set *bset, int isl_set_fast_is_equal(struct isl_set *set1, struct isl_set *set2); int isl_set_fast_is_disjoint(struct isl_set *set1, struct isl_set *set2); +uint32_t isl_set_get_hash(struct isl_set *set); + #if defined(__cplusplus) } #endif diff --git a/isl_gmp.c b/isl_gmp.c index ff04e14..d40d289 100644 --- a/isl_gmp.c +++ b/isl_gmp.c @@ -7,13 +7,9 @@ uint32_t isl_gmp_hash(mpz_t v, uint32_t hash) unsigned char *data = (unsigned char *)v[0]._mp_d; unsigned char *end = data + abs_sa * sizeof(v[0]._mp_d[0]); - if (sa < 0) { - hash *= 16777619; - hash ^= 0xFF; - } - for (; data < end; ++data) { - hash *= 16777619; - hash ^= *data; - } + if (sa < 0) + isl_hash_byte(hash, 0xFF); + for (; data < end; ++data) + isl_hash_byte(hash, *data); return hash; } diff --git a/isl_map.c b/isl_map.c index 9dacf27..1cdc92f 100644 --- a/isl_map.c +++ b/isl_map.c @@ -1044,7 +1044,7 @@ static int hash_index(isl_int ***index, unsigned int size, int bits, { int h; unsigned total = bmap->nparam + bmap->n_in + bmap->n_out + bmap->n_div; - uint32_t hash = isl_seq_hash(bmap->ineq[k]+1, total, bits); + uint32_t hash = isl_seq_get_hash_bits(bmap->ineq[k]+1, total, bits); for (h = hash; index[h]; h = (h+1) % size) if (&bmap->ineq[k] != index[h] && isl_seq_eq(bmap->ineq[k]+1, index[h][0]+1, total)) @@ -1078,7 +1078,7 @@ static struct isl_basic_map *remove_duplicate_constraints( if (!index) return bmap; - index[isl_seq_hash(bmap->ineq[0]+1, total, bits)] = &bmap->ineq[0]; + index[isl_seq_get_hash_bits(bmap->ineq[0]+1, total, bits)] = &bmap->ineq[0]; for (k = 1; k < bmap->n_ineq; ++k) { h = hash_index(index, size, bits, bmap, k); if (!index[h]) { @@ -1312,14 +1312,14 @@ static struct isl_basic_map *remove_duplicate_divs( goto out; isl_seq_clr(eq.data, 1+total); - index[isl_seq_hash(bmap->div[k], 2+total, bits)] = k + 1; + index[isl_seq_get_hash_bits(bmap->div[k], 2+total, bits)] = k + 1; for (--k; k >= 0; --k) { uint32_t hash; if (isl_int_is_zero(bmap->div[k][0])) continue; - hash = isl_seq_hash(bmap->div[k], 2+total, bits); + hash = isl_seq_get_hash_bits(bmap->div[k], 2+total, bits); for (h = hash; index[h]; h = (h+1) % size) if (isl_seq_eq(bmap->div[k], bmap->div[index[h]-1], 2+total)) @@ -4528,6 +4528,12 @@ struct isl_basic_map *isl_basic_map_normalize(struct isl_basic_map *bmap) return bmap; } +struct isl_basic_set *isl_basic_set_normalize(struct isl_basic_set *bset) +{ + return (struct isl_basic_set *)isl_basic_map_normalize( + (struct isl_basic_map *)bset); +} + static int isl_basic_map_fast_cmp(const struct isl_basic_map *bmap1, const struct isl_basic_map *bmap2) { @@ -4753,3 +4759,65 @@ error: isl_basic_set_list_free(list); return NULL; } + +uint32_t isl_basic_set_get_hash(struct isl_basic_set *bset) +{ + int i; + uint32_t hash; + unsigned total; + + if (!bset) + return 0; + bset = isl_basic_set_copy(bset); + bset = isl_basic_set_normalize(bset); + if (!bset) + return 0; + total = bset->nparam + bset->dim + bset->n_div; + isl_hash_byte(hash, bset->n_eq & 0xFF); + for (i = 0; i < bset->n_eq; ++i) { + uint32_t c_hash; + c_hash = isl_seq_get_hash(bset->eq[i], 1 + total); + isl_hash_hash(hash, c_hash); + } + isl_hash_byte(hash, bset->n_ineq & 0xFF); + for (i = 0; i < bset->n_ineq; ++i) { + uint32_t c_hash; + c_hash = isl_seq_get_hash(bset->ineq[i], 1 + total); + isl_hash_hash(hash, c_hash); + } + isl_hash_byte(hash, bset->n_div & 0xFF); + for (i = 0; i < bset->n_div; ++i) { + uint32_t c_hash; + if (isl_int_is_zero(bset->div[i][0])) + continue; + isl_hash_byte(hash, i & 0xFF); + c_hash = isl_seq_get_hash(bset->div[i], 1 + 1 + total); + isl_hash_hash(hash, c_hash); + } + isl_basic_set_free(bset); + return hash; +} + +uint32_t isl_set_get_hash(struct isl_set *set) +{ + int i; + uint32_t hash; + + if (!set) + return 0; + set = isl_set_copy(set); + set = isl_set_normalize(set); + if (!set) + return 0; + + isl_hash_init(hash); + for (i = 0; i < set->n; ++i) { + uint32_t bset_hash; + bset_hash = isl_basic_set_get_hash(set->p[i]); + isl_hash_hash(hash, bset_hash); + } + + isl_set_free(set); + + return hash; +} diff --git a/isl_seq.c b/isl_seq.c index 5b2f174..50c5bd9 100644 --- a/isl_seq.c +++ b/isl_seq.c @@ -177,11 +177,9 @@ void isl_seq_inner_product(isl_int *p1, isl_int *p2, unsigned len, isl_int_addmul(*prod, p1[i], p2[i]); } -uint32_t isl_seq_hash(isl_int *p, unsigned len, unsigned bits) +uint32_t isl_seq_hash(isl_int *p, unsigned len, uint32_t hash) { int i; - uint32_t hash = 2166136261u; - for (i = 0; i < len; ++i) { if (isl_int_is_zero(p[i])) continue; @@ -189,9 +187,21 @@ uint32_t isl_seq_hash(isl_int *p, unsigned len, unsigned bits) hash ^= (i & 0xFF); hash = isl_int_hash(p[i], hash); } - if (bits == 32) - return hash; - if (bits >= 16) - return (hash >> bits) ^ (hash & (((uint32_t)1 << bits) - 1)); - return ((hash >> bits) ^ hash) & (((uint32_t)1 << bits) - 1); + return hash; +} + +uint32_t isl_seq_get_hash(isl_int *p, unsigned len) +{ + uint32_t hash; + isl_hash_init(hash); + + return isl_seq_hash(p, len, hash); +} + +uint32_t isl_seq_get_hash_bits(isl_int *p, unsigned len, unsigned bits) +{ + uint32_t hash; + + hash = isl_seq_get_hash(p, len); + return isl_hash_bits(hash, bits); } -- 2.7.4