EXA: Use a single large glyph cache pixmap

Add back exaGlyphs(); the new version copies the glyph images
onto a single large glyph pixmap and draws from their to the
destination surface. This reduces the management of small
offscreen areas and will allow us to avoid texture unit setup
between each glyph.

4 files changed, 796 insertions, 0 deletions

diff --git a/exa/Makefile.am b/exa/Makefile.am
index e2f7ed302..2b3f1e416 100644
--- a/exa/Makefile.am
+++ b/exa/Makefile.am
@@ -18,6 +18,7 @@ libexa_la_SOURCES = \
 	exa.c \
 	exa.h \
 	exa_accel.c \
+	exa_glyphs.c \
 	exa_migration.c \
 	exa_offscreen.c \
 	exa_render.c \
diff --git a/exa/exa.c b/exa/exa.c
index 3a6ad988e..809fb4b00 100644
--- a/exa/exa.c
+++ b/exa/exa.c
@@ -739,6 +739,8 @@ exaCloseScreen(int i, ScreenPtr pScreen)
     PictureScreenPtr	ps = GetPictureScreenIfSet(pScreen);
 #endif
 
+    exaGlyphsFini(pScreen);
+
     pScreen->CreateGC = pExaScr->SavedCreateGC;
     pScreen->CloseScreen = pExaScr->SavedCloseScreen;
     pScreen->GetImage = pExaScr->SavedGetImage;
@@ -752,7 +754,9 @@ exaCloseScreen(int i, ScreenPtr pScreen)
 #ifdef RENDER
     if (ps) {
 	ps->Composite = pExaScr->SavedComposite;
+	ps->Glyphs = pExaScr->SavedGlyphs;
 	ps->Trapezoids = pExaScr->SavedTrapezoids;
+	ps->Triangles = pExaScr->SavedTriangles;
     }
 #endif
 
@@ -914,6 +918,9 @@ exaDriverInit (ScreenPtr		pScreen,
         pExaScr->SavedComposite = ps->Composite;
 	ps->Composite = exaComposite;
 
+	pExaScr->SavedGlyphs = ps->Glyphs;
+	ps->Glyphs = exaGlyphs;
+	
 	pExaScr->SavedTriangles = ps->Triangles;
 	ps->Triangles = exaTriangles;
 
@@ -973,6 +980,8 @@ exaDriverInit (ScreenPtr		pScreen,
 	}
     }
 
+    exaGlyphsInit(pScreen);
+
     LogMessage(X_INFO, "EXA(%d): Driver registered support for the following"
 	       " operations:\n", pScreen->myNum);
     assert(pScreenInfo->PrepareSolid != NULL);
diff --git a/exa/exa_glyphs.c b/exa/exa_glyphs.c
new file mode 100644
index 000000000..3fe433aa7
--- /dev/null
+++ b/exa/exa_glyphs.c
@@ -0,0 +1,745 @@
+/*
+ * Copyright © 2008 Red Hat, Inc.
+ * Partly based on code Copyright © 2000 SuSE, Inc.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of Red Hat not be used in advertising or
+ * publicity pertaining to distribution of the software without specific,
+ * written prior permission.  Red Hat makes no representations about the
+ * suitability of this software for any purpose.  It is provided "as is"
+ * without express or implied warranty.
+ *
+ * Red Hat DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL Red Hat
+ * BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Permission to use, copy, modify, distribute, and sell this software and its
+ * documentation for any purpose is hereby granted without fee, provided that
+ * the above copyright notice appear in all copies and that both that
+ * copyright notice and this permission notice appear in supporting
+ * documentation, and that the name of SuSE not be used in advertising or
+ * publicity pertaining to distribution of the software without specific,
+ * written prior permission.  SuSE makes no representations about the
+ * suitability of this software for any purpose.  It is provided "as is"
+ * without express or implied warranty.
+ *
+ * SuSE DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL SuSE
+ * BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
+ * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 
+ * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ *
+ * Author: Owen Taylor <otaylor@fishsoup.net>
+ * Based on code by: Keith Packard
+ */
+
+#ifdef HAVE_DIX_CONFIG_H
+#include <dix-config.h>
+#endif
+
+#include <stdlib.h>
+
+#include "exa_priv.h"
+
+#include "mipict.h"
+
+#if DEBUG_GLYPH_CACHE
+#define DBG_GLYPH_CACHE(a) ErrorF a
+#else
+#define DBG_GLYPH_CACHE(a)
+#endif
+
+/* Instructions for rendering a single glyph */
+typedef struct {
+    INT16 xSrc;
+    INT16 ySrc;
+    INT16 xDst;
+    INT16 yDst;
+    INT16 width;
+    INT16 height;
+} ExaGlyphRenderRec, *ExaGlyphRenderPtr;
+
+/* Width of the pixmaps we use for the caches; this should be less than
+ * max texture size of the driver; this may need to actually come from
+ * the driver.
+ */
+#define CACHE_PICTURE_WIDTH 1024
+
+/* Maximum number of glyphs we buffer on the stack before flushing
+ * rendering to the mask or destination surface.
+ */
+#define GLYPH_BUFFER_SIZE 256
+
+typedef struct {
+    PicturePtr source;
+    ExaGlyphRenderRec glyphs[GLYPH_BUFFER_SIZE];
+    int count;
+} ExaGlyphBuffer, *ExaGlyphBufferPtr;
+
+typedef enum {
+    ExaGlyphSuccess,    /* Glyph added to render buffer */
+    ExaGlyphFail,       /* out of memory, etc */
+    ExaGlyphNeedFlush,  /* would evict a glyph already in the buffer */
+} ExaGlyphCacheResult;
+
+void
+exaGlyphsInit(ScreenPtr pScreen)
+{
+    ExaScreenPriv(pScreen);
+    int i = 0;
+
+    memset(pExaScr->glyphCaches, 0, sizeof(pExaScr->glyphCaches));
+
+    pExaScr->glyphCaches[i].format = PICT_a8;
+    pExaScr->glyphCaches[i].glyphWidth = pExaScr->glyphCaches[i].glyphHeight = 16;
+    i++;
+    pExaScr->glyphCaches[i].format = PICT_a8;
+    pExaScr->glyphCaches[i].glyphWidth = pExaScr->glyphCaches[i].glyphHeight = 32;
+    i++;
+    pExaScr->glyphCaches[i].format = PICT_a8r8g8b8;
+    pExaScr->glyphCaches[i].glyphWidth = pExaScr->glyphCaches[i].glyphHeight = 16;
+    i++;
+    pExaScr->glyphCaches[i].format = PICT_a8r8g8b8;
+    pExaScr->glyphCaches[i].glyphWidth = pExaScr->glyphCaches[i].glyphHeight = 32;
+    i++;
+
+    assert(i == EXA_NUM_GLYPH_CACHES);
+    
+    for (i = 0; i < EXA_NUM_GLYPH_CACHES; i++) {
+	pExaScr->glyphCaches[i].columns = CACHE_PICTURE_WIDTH / pExaScr->glyphCaches[i].glyphWidth;
+	pExaScr->glyphCaches[i].size = 256;
+	pExaScr->glyphCaches[i].hashSize = 557;
+    }
+}
+
+static void
+exaUnrealizeGlyphCaches(ScreenPtr    pScreen,
+			unsigned int format)
+{
+    ExaScreenPriv(pScreen);
+    int i;
+
+    for (i = 0; i < EXA_NUM_GLYPH_CACHES; i++) {
+	ExaGlyphCachePtr cache = &pExaScr->glyphCaches[i];
+	
+	if (cache->format != format)
+	    continue;
+
+	if (cache->picture) {
+	    FreePicture ((pointer) cache->picture, (XID) 0);
+	    cache->picture = NULL;
+	}
+
+	if (cache->hashEntries) {
+	    xfree(cache->hashEntries);
+	    cache->hashEntries = NULL;
+	}
+	
+	if (cache->glyphs) {
+	    xfree(cache->glyphs);
+	    cache->glyphs = NULL;
+	}
+	cache->glyphCount = 0;
+    }
+}
+
+/* All caches for a single format share a single pixmap for glyph storage,
+ * allowing mixing glyphs of different sizes without paying a penalty
+ * for switching between source pixmaps. (Note that for a size of font
+ * right at the border between two sizes, we might be switching for almost
+ * every glyph.)
+ *
+ * This function allocates the storage pixmap, and then fills in the
+ * rest of the allocated structures for all caches with the given format.
+ */
+static Bool
+exaRealizeGlyphCaches(ScreenPtr    pScreen,
+		      unsigned int format)
+{
+    ExaScreenPriv(pScreen);
+
+    int depth = PIXMAN_FORMAT_DEPTH(format);
+    PictFormatPtr pPictFormat;
+    PixmapPtr pPixmap;
+    PicturePtr pPicture;
+    int height;
+    int i;
+    int	error;
+
+    pPictFormat = PictureMatchFormat(pScreen, depth, format);
+    if (!pPictFormat)
+	return FALSE;
+    
+    /* Compute the total vertical size needed for the format */
+
+    height = 0;
+    for (i = 0; i < EXA_NUM_GLYPH_CACHES; i++) {
+	ExaGlyphCachePtr cache = &pExaScr->glyphCaches[i];
+	int rows;
+	
+	if (cache->format != format)
+	    continue;
+
+	rows = (cache->size + cache->columns - 1) / cache->columns;
+
+	height += rows * cache->glyphHeight;
+    }
+
+    /* Now allocate the pixmap and picture */
+       
+    pPixmap = (*pScreen->CreatePixmap) (pScreen,
+					CACHE_PICTURE_WIDTH,
+					height, depth, 0);
+    if (!pPixmap)
+	return FALSE;
+
+    pPicture = CreatePicture(0, &pPixmap->drawable, pPictFormat,
+			     0, 0, serverClient, &error);
+
+    (*pScreen->DestroyPixmap) (pPixmap); /* picture holds a refcount */
+
+    if (!pPicture)
+	return FALSE;
+
+    /* And store the picture in all the caches for the format */
+    
+    for (i = 0; i < EXA_NUM_GLYPH_CACHES; i++) {
+	ExaGlyphCachePtr cache = &pExaScr->glyphCaches[i];
+	int j;
+
+	if (cache->format != format)
+	    continue;
+
+	cache->picture = pPicture;
+	cache->picture->refcnt++;
+	cache->hashEntries = xalloc(sizeof(int) * cache->hashSize);
+	cache->glyphs = xalloc(sizeof(ExaCachedGlyphRec) * cache->size);
+	cache->glyphCount = 0;
+
+	if (!cache->hashEntries || !cache->glyphs)
+	    goto bail;
+
+	for (j = 0; j < cache->hashSize; j++)
+	    cache->hashEntries[j] = -1;
+	
+	cache->evictionPosition = rand() % cache->size;
+    }
+
+    /* Each cache references the picture individually */
+    FreePicture ((pointer) pPicture, (XID) 0);
+    return TRUE;
+
+bail:
+    exaUnrealizeGlyphCaches(pScreen, format);
+    return FALSE;
+}
+
+void
+exaGlyphsFini (ScreenPtr pScreen)
+{
+    ExaScreenPriv(pScreen);
+    int i;
+
+    for (i = 0; i < EXA_NUM_GLYPH_CACHES; i++) {
+	ExaGlyphCachePtr cache = &pExaScr->glyphCaches[i];
+
+	if (cache->picture)
+	    exaUnrealizeGlyphCaches(pScreen, cache->format);
+    }
+}
+
+static int
+exaGlyphCacheHashLookup(ExaGlyphCachePtr cache,
+			GlyphPtr         pGlyph)
+{
+    int slot;
+
+    slot = (*(CARD32 *) pGlyph->sha1) % cache->hashSize;
+    
+    while (TRUE) { /* hash table can never be full */
+	int entryPos = cache->hashEntries[slot];
+	if (entryPos == -1)
+	    return -1;
+
+	if (memcmp(pGlyph->sha1, cache->glyphs[entryPos].sha1, sizeof(pGlyph->sha1)) == 0){
+	    DBG_GLYPH_CACHE((" found entry at %d\n", slot));
+	    return entryPos;
+	}
+	    
+	DBG_GLYPH_CACHE((" lookup linear probe bumpalong\n"));
+	slot--;
+	if (slot < 0)
+	    slot = cache->hashSize - 1;
+    }
+}
+
+static void
+exaGlyphCacheHashInsert(ExaGlyphCachePtr cache,
+			GlyphPtr         pGlyph,
+			int              pos)
+{
+    int slot;
+
+    memcpy(cache->glyphs[pos].sha1, pGlyph->sha1, sizeof(pGlyph->sha1));
+    
+    slot = (*(CARD32 *) pGlyph->sha1) % cache->hashSize;
+    
+    while (TRUE) { /* hash table can never be full */
+	if (cache->hashEntries[slot] == -1) {
+	    DBG_GLYPH_CACHE((" inserting entry at %d\n", slot));
+	    cache->hashEntries[slot] = pos;
+	    return;
+	}
+	    
+	slot--;
+	if (slot < 0)
+	    slot = cache->hashSize - 1;
+    }
+}
+
+static void
+exaGlyphCacheHashRemove(ExaGlyphCachePtr cache,
+			int              pos)
+{
+    int slot;
+    int emptiedSlot = -1;
+
+    slot = (*(CARD32 *) cache->glyphs[pos].sha1) % cache->hashSize;
+
+    while (TRUE) { /* hash table can never be full */
+	int entryPos = cache->hashEntries[slot];
+	
+	if (entryPos == -1)
+	    return;
+
+	if (entryPos == pos) {
+	    cache->hashEntries[slot] = -1;
+	    emptiedSlot = slot;
+	} else if (emptiedSlot != -1) {
+	    /* See if we can move this entry into the emptied slot, we can't
+	     * do that if if entry would have hashed between the current position
+	     * and the emptied slot. (taking wrapping into account). Bad positions
+	     * are:
+	     *
+	     * |   XXXXXXXXXX             |
+	     *     i         j            
+	     *                            
+	     * |XXX                   XXXX|
+	     *     j                  i
+	     *
+	     * i - slot, j - emptiedSlot
+	     *
+	     * (Knuth 6.4R)
+	     */
+	    
+	    int entrySlot = (*(CARD32 *) cache->glyphs[entryPos].sha1) % cache->hashSize;
+
+	    if (!((entrySlot >= slot && entrySlot < emptiedSlot) ||
+		  (emptiedSlot < slot && (entrySlot < emptiedSlot || entrySlot >= slot)))) 
+	    {
+		cache->hashEntries[emptiedSlot] = entryPos;
+		cache->hashEntries[slot] = -1;
+		emptiedSlot = slot;
+	    }
+	}
+	
+	slot--;
+	if (slot < 0)
+	    slot = cache->hashSize - 1;
+    }
+}
+
+static ExaGlyphCacheResult
+exaGlyphCacheBufferGlyph(ScreenPtr         pScreen,
+			 ExaGlyphCachePtr  cache,
+			 ExaGlyphBufferPtr buffer,
+			 GlyphPtr          pGlyph,
+			 int               xGlyph,
+			 int               yGlyph)
+{
+    ExaGlyphRenderPtr glyphRec;
+    int pos;
+    
+    if (buffer->source && buffer->source != cache->picture)
+	return ExaGlyphNeedFlush;
+
+    if (!cache->picture) {
+	if (!exaRealizeGlyphCaches(pScreen, cache->format))
+	    return ExaGlyphFail;
+    }
+
+    DBG_GLYPH_CACHE(("(%d,%d,%s): buffering glyph %lx\n",
+		     cache->glyphWidth, cache->glyphHeight, cache->format == PICT_a8 ? "A" : "ARGB",
+		     (long)*(CARD32 *) pGlyph->sha1));
+   
+    pos = exaGlyphCacheHashLookup(cache, pGlyph);
+    if (pos != -1) {
+	DBG_GLYPH_CACHE(("  found existing glyph at %d\n", pos));
+    } else {
+	if (cache->glyphCount < cache->size) {
+	    /* Space remaining; we fill from the start */
+	    pos = cache->glyphCount;
+	    cache->glyphCount++;
+	    DBG_GLYPH_CACHE(("  storing glyph in free space at %d\n", pos));
+
+	    exaGlyphCacheHashInsert(cache, pGlyph, pos);
+
+	} else {
+	    /* Need to evict an entry. We have to see if any glyphs
+	     * already in the output buffer were at this position in
+	     * the cache
+	     */
+	    
+	    pos = cache->evictionPosition;
+	    DBG_GLYPH_CACHE(("  evicting glyph at %d\n", pos));
+	    if (buffer->count) {
+		int x, y;
+		int i;
+		
+		x = (pos % cache->columns) * cache->glyphWidth;
+		y = (pos / cache->columns) * cache->glyphHeight;
+
+		for (i = 0; i < buffer->count; i++) {
+		    if (buffer->glyphs[i].xSrc == x && buffer->glyphs[i].ySrc == y) {
+			DBG_GLYPH_CACHE(("  must flush buffer\n"));
+			return ExaGlyphNeedFlush;
+		    }
+		}
+	    }
+
+	    /* OK, we're all set, swap in the new glyph */
+	    exaGlyphCacheHashRemove(cache, pos);
+	    exaGlyphCacheHashInsert(cache, pGlyph, pos);
+
+	    /* And pick a new eviction position */
+	    cache->evictionPosition = rand() % cache->size;
+	}
+
+	/* Now actually upload the glyph into the cache picture */
+
+	CompositePicture (PictOpSrc,
+			  GlyphPicture(pGlyph)[pScreen->myNum],
+			  None,
+			  cache->picture,
+			  0, 0,
+			  0, 0,
+			  (pos % cache->columns) * cache->glyphWidth,
+			  (pos / cache->columns) * cache->glyphHeight,
+			  pGlyph->info.width,
+			  pGlyph->info.height);
+    }
+    
+
+    buffer->source = cache->picture;
+	    
+    glyphRec = &buffer->glyphs[buffer->count];
+    glyphRec->xSrc = (pos % cache->columns) * cache->glyphWidth;
+    glyphRec->ySrc = (pos / cache->columns) * cache->glyphHeight;
+    glyphRec->xDst = xGlyph - pGlyph->info.x;
+    glyphRec->yDst = yGlyph - pGlyph->info.y;
+    glyphRec->width = pGlyph->info.width;
+    glyphRec->height = pGlyph->info.height;
+	    
+    buffer->count++;
+
+    return ExaGlyphSuccess;
+}
+
+static ExaGlyphCacheResult
+exaBufferGlyph(ScreenPtr         pScreen,
+	       ExaGlyphBufferPtr buffer,
+	       GlyphPtr          pGlyph,
+	       int               xGlyph,
+	       int               yGlyph)
+{
+    ExaScreenPriv(pScreen);
+    unsigned int format = (GlyphPicture(pGlyph)[pScreen->myNum])->format;
+    int width = pGlyph->info.width;
+    int height = pGlyph->info.width;
+    ExaGlyphRenderPtr glyphRec;
+    PicturePtr source;
+    int i;
+
+    if (buffer->count == GLYPH_BUFFER_SIZE)
+	return ExaGlyphNeedFlush;
+    
+    for (i = 0; i < EXA_NUM_GLYPH_CACHES; i++) {
+	ExaGlyphCachePtr cache = &pExaScr->glyphCaches[i];
+
+	if (format == cache->format &&
+	    width <= cache->glyphWidth &&
+	    height <= cache->glyphHeight) {
+	    ExaGlyphCacheResult result = exaGlyphCacheBufferGlyph(pScreen, &pExaScr->glyphCaches[i],
+								  buffer,
+								  pGlyph, xGlyph, yGlyph);
+	    switch (result) {
+	    case ExaGlyphFail:
+		break;
+	    case ExaGlyphSuccess:
+	    case ExaGlyphNeedFlush:
+		return result;
+	    }
+	}
+    }
+
+    /* Couldn't find the glyph in the cache, use the glyph picture directly */
+
+    source = GlyphPicture(pGlyph)[pScreen->myNum];
+    if (buffer->source && buffer->source != source)
+	return ExaGlyphNeedFlush;
+
+    buffer->source = source;
+    
+    glyphRec = &buffer->glyphs[buffer->count];
+    glyphRec->xSrc = 0;
+    glyphRec->ySrc = 0;
+    glyphRec->xDst = xGlyph - pGlyph->info.x;
+    glyphRec->yDst = yGlyph - pGlyph->info.y;
+    glyphRec->width = pGlyph->info.width;
+    glyphRec->height = pGlyph->info.height;
+
+    buffer->count++;
+
+    return ExaGlyphSuccess;
+}
+
+static void
+exaGlyphsToMask(PicturePtr        pMask,
+		ExaGlyphBufferPtr buffer)
+{
+    int i;
+
+    for (i = 0; i < buffer->count; i++) {
+	ExaGlyphRenderPtr glyphRec = &buffer->glyphs[i];
+	
+	CompositePicture (PictOpAdd,
+			  buffer->source,
+			  None,
+			  pMask,
+			  glyphRec->xSrc,
+			  glyphRec->ySrc,
+			  0, 0,
+			  glyphRec->xDst,
+			  glyphRec->yDst,
+			  glyphRec->width,
+			  glyphRec->height);
+    }
+    
+    buffer->count = 0;
+    buffer->source = NULL;
+}
+
+static void
+exaGlyphsToDst(CARD8		 op,
+	       PicturePtr	 pSrc,
+	       PicturePtr	 pDst,
+	       ExaGlyphBufferPtr buffer,
+	       INT16		 xSrc,
+	       INT16		 ySrc,
+	       INT16		 xDst,
+	       INT16		 yDst)
+{
+    int i;
+
+    for (i = 0; i < buffer->count; i++) {
+	ExaGlyphRenderPtr glyphRec = &buffer->glyphs[i];
+	
+	CompositePicture (op,
+			  pSrc,
+			  buffer->source,
+			  pDst,
+			  xSrc + glyphRec->xDst - xDst,
+			  ySrc + glyphRec->yDst - yDst,
+			  glyphRec->xSrc,
+			  glyphRec->ySrc,
+			  glyphRec->xDst,
+			  glyphRec->yDst,
+			  glyphRec->width,
+			  glyphRec->height);
+    }
+    
+    buffer->count = 0;
+    buffer->source = NULL;
+}
+
+/* Cut and paste from render/glyph.c - probably should export it instead */
+static void
+GlyphExtents (int		nlist,
+	      GlyphListPtr	list,
+	      GlyphPtr	       *glyphs,
+	      BoxPtr		extents)
+{
+    int		x1, x2, y1, y2;
+    int		n;
+    GlyphPtr	glyph;
+    int		x, y;
+    
+    x = 0;
+    y = 0;
+    extents->x1 = MAXSHORT;
+    extents->x2 = MINSHORT;
+    extents->y1 = MAXSHORT;
+    extents->y2 = MINSHORT;
+    while (nlist--)
+    {
+	x += list->xOff;
+	y += list->yOff;
+	n = list->len;
+	list++;
+	while (n--)
+	{
+	    glyph = *glyphs++;
+	    x1 = x - glyph->info.x;
+	    if (x1 < MINSHORT)
+		x1 = MINSHORT;
+	    y1 = y - glyph->info.y;
+	    if (y1 < MINSHORT)
+		y1 = MINSHORT;
+	    x2 = x1 + glyph->info.width;
+	    if (x2 > MAXSHORT)
+		x2 = MAXSHORT;
+	    y2 = y1 + glyph->info.height;
+	    if (y2 > MAXSHORT)
+		y2 = MAXSHORT;
+	    if (x1 < extents->x1)
+		extents->x1 = x1;
+	    if (x2 > extents->x2)
+		extents->x2 = x2;
+	    if (y1 < extents->y1)
+		extents->y1 = y1;
+	    if (y2 > extents->y2)
+		extents->y2 = y2;
+	    x += glyph->info.xOff;
+	    y += glyph->info.yOff;
+	}
+    }
+}
+
+#define NeedsComponent(f) (PICT_FORMAT_A(f) != 0 && PICT_FORMAT_RGB(f) != 0)
+
+void
+exaGlyphs (CARD8 	 op,
+	   PicturePtr	 pSrc,
+	   PicturePtr	 pDst,
+	   PictFormatPtr maskFormat,
+	   INT16	 xSrc,
+	   INT16	 ySrc,
+	   int		 nlist,
+	   GlyphListPtr	 list,
+	   GlyphPtr	*glyphs)
+{
+    PicturePtr	pPicture;
+    PixmapPtr   pMaskPixmap = 0;
+    PicturePtr  pMask;
+    ScreenPtr   pScreen = pDst->pDrawable->pScreen;
+    int		width = 0, height = 0;
+    int		x, y;
+    int		xDst = list->xOff, yDst = list->yOff;
+    int		n;
+    GlyphPtr	glyph;
+    int		error;
+    BoxRec	extents = {0, 0, 0, 0};
+    CARD32	component_alpha;
+    ExaGlyphBuffer buffer;
+
+    if (maskFormat)
+    {
+	GCPtr	    pGC;
+	xRectangle  rect;
+
+	GlyphExtents (nlist, list, glyphs, &extents);
+
+	if (extents.x2 <= extents.x1 || extents.y2 <= extents.y1)
+	    return;
+	width = extents.x2 - extents.x1;
+	height = extents.y2 - extents.y1;
+	pMaskPixmap = (*pScreen->CreatePixmap) (pScreen, width, height,
+						maskFormat->depth,
+						CREATE_PIXMAP_USAGE_SCRATCH);
+	if (!pMaskPixmap)
+	    return;
+	component_alpha = NeedsComponent(maskFormat->format);
+	pMask = CreatePicture (0, &pMaskPixmap->drawable,
+			       maskFormat, CPComponentAlpha, &component_alpha,
+			       serverClient, &error);
+	if (!pMask)
+	{
+	    (*pScreen->DestroyPixmap) (pMaskPixmap);
+	    return;
+	}
+	pGC = GetScratchGC (pMaskPixmap->drawable.depth, pScreen);
+	ValidateGC (&pMaskPixmap->drawable, pGC);
+	rect.x = 0;
+	rect.y = 0;
+	rect.width = width;
+	rect.height = height;
+	(*pGC->ops->PolyFillRect) (&pMaskPixmap->drawable, pGC, 1, &rect);
+	FreeScratchGC (pGC);
+	x = -extents.x1;
+	y = -extents.y1;
+    }
+    else
+    {
+	pMask = pDst;
+	x = 0;
+	y = 0;
+    }
+    buffer.count = 0;
+    buffer.source = NULL;
+    while (nlist--)
+    {
+	x += list->xOff;
+	y += list->yOff;
+	n = list->len;
+	while (n--)
+	{
+	    glyph = *glyphs++;
+	    pPicture = GlyphPicture (glyph)[pScreen->myNum];
+
+	    if (exaBufferGlyph(pScreen, &buffer, glyph, x, y) == ExaGlyphNeedFlush)
+	    {
+		if (maskFormat)
+		    exaGlyphsToMask(pMask, &buffer);
+		else
+		    exaGlyphsToDst(op, pSrc, pDst, &buffer,
+				   xSrc, ySrc, xDst, yDst);
+
+		exaBufferGlyph(pScreen, &buffer, glyph, x, y);
+	    }
+
+	    x += glyph->info.xOff;
+	    y += glyph->info.yOff;
+	}
+	list++;
+    }
+    
+    if (maskFormat)
+	exaGlyphsToMask(pMask, &buffer);
+    else
+	exaGlyphsToDst(op, pSrc, pDst, &buffer,
+		       xSrc, ySrc, xDst, yDst);
+    
+    if (maskFormat)
+    {
+	x = extents.x1;
+	y = extents.y1;
+	CompositePicture (op,
+			  pSrc,
+			  pMask,
+			  pDst,
+			  xSrc + x - xDst,
+			  ySrc + y - yDst,
+			  0, 0,
+			  x, y,
+			  width, height);
+	FreePicture ((pointer) pMask, (XID) 0);
+	(*pScreen->DestroyPixmap) (pMaskPixmap);
+    }
+}
diff --git a/exa/exa_priv.h b/exa/exa_priv.h
index 0138e4a7d..aaceeb81d 100644
--- a/exa/exa_priv.h
+++ b/exa/exa_priv.h
@@ -61,6 +61,7 @@
 #define DEBUG_MIGRATE		0
 #define DEBUG_PIXMAP		0
 #define DEBUG_OFFSCREEN		0
+#define DEBUG_GLYPH_CACHE	0
 
 #if DEBUG_TRACE_FALL
 #define EXA_FALLBACK(x)     					\
@@ -95,6 +96,37 @@ enum ExaMigrationHeuristic {
     ExaMigrationSmart
 };
 
+typedef struct {
+    unsigned char sha1[20];
+} ExaCachedGlyphRec, *ExaCachedGlyphPtr;
+
+typedef struct {
+    /* The identity of the cache, statically configured at initialization */
+    unsigned int format;
+    int glyphWidth;
+    int glyphHeight;
+
+    int size; /* Size of cache; eventually this should be dynamically determined */
+
+    /* Hash table mapping from glyph sha1 to position in the glyph; we use
+     * open addressing with a hash table size determined based on size and large
+     * enough so that we always have a good amount of free space, so we can
+     * use linear probing. (Linear probing is preferrable to double hashing
+     * here because it allows us to easily remove entries.)
+     */
+    int *hashEntries;
+    int hashSize;
+    
+    ExaCachedGlyphPtr glyphs;
+    int glyphCount; /* Current number of glyphs */
+    
+    PicturePtr picture;   /* Where the glyphs of the cache are stored */
+    int columns;          /* Number of columns the glyphs are layed out in */
+    int evictionPosition; /* Next random position to evict a glyph */
+} ExaGlyphCacheRec, *ExaGlyphCachePtr;
+
+#define EXA_NUM_GLYPH_CACHES 4
+
 typedef void (*EnableDisableFBAccessProcPtr)(int, Bool);
 typedef struct {
     ExaDriverPtr info;
@@ -122,6 +154,8 @@ typedef struct {
     unsigned			 disableFbCount;
     Bool			 optimize_migration;
     unsigned			 offScreenCounter;
+
+    ExaGlyphCacheRec             glyphCaches[EXA_NUM_GLYPH_CACHES];
 } ExaScreenPrivRec, *ExaScreenPrivPtr;
 
 /*
@@ -432,6 +466,13 @@ exaTriangles (CARD8 op, PicturePtr pSrc, PicturePtr pDst,
 	      PictFormatPtr maskFormat, INT16 xSrc, INT16 ySrc,
 	      int ntri, xTriangle *tris);
 
+/* exa_glyph.c */
+void
+exaGlyphsInit(ScreenPtr pScreen);
+
+void
+exaGlyphsFini (ScreenPtr pScreen);
+
 void
 exaGlyphs (CARD8	op,
 	  PicturePtr	pSrc,