Update pattern cache to cope with hash collision for 2 'locked' tiles.

Currently, the pattern cache has a table of possible entries,
'num_entries' in size. For any given pattern A, it will go into
the tile[A.id % num_entries].

This works fine while we're only ever using 1 pattern at a time. If 2
patterns collide, then the first is just evicted.

Sadly, with fill_strokes using patterns, we can now need 2 at a time.
To ensure that pattern A is not evicted to keep the pattern cache
small enough when pattern N is introduced, we allow pattern A to be
locked.

At worst we'll have 2 locked patterns at once, and we'll only ever
insert a new pattern while 1 pattern there might be locked.

This works fine, until we have A.id and B.id both mapping to the same
place in the table. With the current code there is no way for both A
and B to live in the table at the same time.

We therefore tweak the pattern cache so that A can go into 2 places
in the cache. Either at tile[A.id % num_entries] or
tile[(A.id+1) % num_entries].

We provide a helper function to lookup an appropriate location for
A tile, allowing for whether an existing tile is locked or not, and
use that.

3 files changed, 45 insertions, 9 deletions

diff --git a/base/gsptype1.c b/base/gsptype1.c
index 60baeecbc..75f6b9529 100644
--- a/base/gsptype1.c
+++ b/base/gsptype1.c
@@ -1615,7 +1615,7 @@ gx_pattern_cache_lookup(gx_device_color * pdevc, const gs_gstate * pgs,
         return true;
     }
     if (pcache != 0) {
-        gx_color_tile *ctile = &pcache->tiles[id % pcache->num_tiles];
+        gx_color_tile *ctile = gx_pattern_cache_find_tile_for_id(pcache, id);
         bool internal_accum = true;
         if (pgs->have_pattern_streams) {
             int code = dev_proc(dev, dev_spec_op)(dev, gxdso_pattern_load, &id, sizeof(gx_bitmap_id));
diff --git a/base/gxpcmap.c b/base/gxpcmap.c
index a85aafd72..43682e03f 100644
--- a/base/gxpcmap.c
+++ b/base/gxpcmap.c
@@ -980,6 +980,41 @@ gx_pattern_cache_free_entry(gx_pattern_cache * pcache, gx_color_tile * ctile)
     }
 }
 
+/*
+    Historically, the pattern cache has used a very simple hashing
+    scheme whereby pattern A goes into slot idx = (A.id % num_tiles).
+    Unfortunately, now we allow tiles to be 'locked' into the
+    pattern cache, we might run into the case where we want both
+    tiles A and B to be in the cache at once where:
+      (A.id % num_tiles) == (B.id % num_tiles).
+
+    We have a maximum of 2 locked tiles, and one of those can be
+    placed while the other one is locked. So we only need to cope
+    with a single 'collision'.
+
+    We therefore allow tiles to either go in at idx or at
+    (idx + 1) % num_tiles. This means we need to be prepared to
+    search a bit further for them, hence we now have 2 helper
+    functions to do this.
+*/
+
+/* We can have at most 1 locked tile while looking for a place to
+ * put another tile. */
+gx_color_tile *
+gx_pattern_cache_find_tile_for_id(gx_pattern_cache *pcache, gs_id id)
+{
+    gx_color_tile *ctile  = &pcache->tiles[id % pcache->num_tiles];
+    gx_color_tile *ctile2 = &pcache->tiles[(id+1) % pcache->num_tiles];
+    if (ctile->id == id || ctile->id == gs_no_id)
+        return ctile;
+    if (ctile2->id == id || ctile2->id == gs_no_id)
+        return ctile2;
+    if (!ctile->is_locked)
+        return ctile;
+    return ctile2;
+}
+
+
 /* Given the size of a new pattern tile, free entries from the cache until  */
 /* enough space is available (or nothing left to free).                     */
 /* This will allow 1 oversized entry                                        */
@@ -1124,7 +1159,7 @@ gx_pattern_cache_add_entry(gs_gstate * pgs,
         used = size_b + size_c;
     }
     id = pinst->id;
-    ctile = &pcache->tiles[id % pcache->num_tiles];
+    ctile = gx_pattern_cache_find_tile_for_id(pcache, id);
     gx_pattern_cache_free_entry(pcache, ctile);         /* ensure that this cache slot is empty */
     ctile->id = id;
     ctile->is_planar = pinst->is_planar;
@@ -1194,15 +1229,13 @@ gx_pattern_cache_add_entry(gs_gstate * pgs,
 int
 gx_pattern_cache_entry_set_lock(gs_gstate *pgs, gs_id id, bool new_lock_value)
 {
-    gx_pattern_cache *pcache;
     gx_color_tile *ctile;
     int code = ensure_pattern_cache(pgs);
 
     if (code < 0)
         return code;
-    pcache = pgs->pattern_cache;
-    ctile = &pcache->tiles[id % pcache->num_tiles];
-    if (ctile->id != id)
+    ctile = gx_pattern_cache_find_tile_for_id(pgs->pattern_cache, id);
+    if (ctile == NULL)
         return_error(gs_error_undefined);
     ctile->is_locked = new_lock_value;
     return 0;
@@ -1219,7 +1252,7 @@ gx_pattern_cache_get_entry(gs_gstate * pgs, gs_id id, gx_color_tile ** pctile)
     if (code < 0)
         return code;
     pcache = pgs->pattern_cache;
-    ctile = &pcache->tiles[id % pcache->num_tiles];
+    ctile = gx_pattern_cache_find_tile_for_id(pcache, id);
     gx_pattern_cache_free_entry(pgs->pattern_cache, ctile);
     ctile->id = id;
     *pctile = ctile;
@@ -1246,7 +1279,7 @@ gx_pattern_cache_add_dummy_entry(gs_gstate *pgs,
     if (code < 0)
         return code;
     pcache = pgs->pattern_cache;
-    ctile = &pcache->tiles[id % pcache->num_tiles];
+    ctile = gx_pattern_cache_find_tile_for_id(pcache, id);
     gx_pattern_cache_free_entry(pcache, ctile);
     ctile->id = id;
     ctile->depth = depth;
diff --git a/base/gxpcolor.h b/base/gxpcolor.h
index 197b75321..043a296ef 100644
--- a/base/gxpcolor.h
+++ b/base/gxpcolor.h
@@ -1,4 +1,4 @@
-/* Copyright (C) 2001-2021 Artifex Software, Inc.
+/* Copyright (C) 2001-2022 Artifex Software, Inc.
    All Rights Reserved.
 
    This software is provided AS-IS with no warranty, either express or
@@ -296,6 +296,9 @@ bool gx_device_is_pattern_accum(gx_device *dev);
 /* This will allow 1 oversized entry					    */
 void gx_pattern_cache_ensure_space(gs_gstate * pgs, size_t needed);
 
+gx_color_tile *
+gx_pattern_cache_find_tile_for_id(gx_pattern_cache *pcache, gs_id id);
+
 void gx_pattern_cache_update_used(gs_gstate *pgs, size_t used);
 
 /* Update cache tile space */