[PATCH] render: Improve glyph double hashing

Andrea Canciani ranma42 at gmail.com
Mon Aug 1 10:45:14 PDT 2011


Instead of artificially introducing collisions in the step value by
replacing 0 with 1 (which causes the value 1 to have twice the
frequency of any other value), the step value can simply be computed
as an uniformly distributed value in the range [1, rehash], extremes
included.

This is safe because any step value smaller than the hash modulus is
co-prime with it, hence induces an orbit which includes every integer
in [0, tableSize - 1].
---
 render/glyph.c |    6 +-----
 1 files changed, 1 insertions(+), 5 deletions(-)

diff --git a/render/glyph.c b/render/glyph.c
index 7193d47..6ebf790 100644
--- a/render/glyph.c
+++ b/render/glyph.c
@@ -164,11 +164,7 @@ FindGlyphRef (GlyphHashPtr	hash,
 	    break;
 	}
 	if (!step)
-	{
-	    step = signature % hash->hashSet->rehash;
-	    if (!step)
-		step = 1;
-	}
+	    step = 1 + signature % hash->hashSet->rehash;
 	elt += step;
 	if (elt >= tableSize)
 	    elt -= tableSize;
-- 
1.7.1



More information about the xorg-devel mailing list