Merge branch 'unicode-tiles'

It lacks an actual font yet, but I realized we need to check if drivers
people use actually support sub-textures -- and if not, there'll be some
rethinking needed.

1 files changed, 246 insertions, 133 deletions

diff --git a/crawl-ref/source/fontwrapper-ft.cc b/crawl-ref/source/fontwrapper-ft.cc
index a865450e04..5ff5c19673 100644
--- a/crawl-ref/source/fontwrapper-ft.cc
+++ b/crawl-ref/source/fontwrapper-ft.cc
@@ -18,6 +18,19 @@
 #include "unicode.h"
 #include "options.h"
 
+// maximum number of unique glyphs that can be rendered with this font at once; e.g. 4096, 256, 36
+#define MAX_GLYPHS 256
+// dimensions of glyph grid; GLYPHS_PER_ROWCOL^2 <= MAX_GLYPHS; e.g. 64, 16, 6
+#define GLYPHS_PER_ROWCOL 16
+// char to use if we can't find it in the font (upside-down question mark)
+#define MISSING_CHAR 0xbf
+
+#if 0
+# define dprintf(...) debuglog(__VA_ARGS__)
+#else
+# define dprintf(...) (void)0
+#endif
+
 FontWrapper* FontWrapper::create()
 {
     return (new FTFontWrapper());
@@ -25,8 +38,12 @@ FontWrapper* FontWrapper::create()
 
 FTFontWrapper::FTFontWrapper() :
     m_glyphs(NULL),
+    m_glyphs_lru(0),
+    m_glyphs_mru(0),
+    m_glyphs_top(0),  // reinitialised to 1 in load_font
     m_max_advance(0, 0),
-    m_min_offset(0)
+    m_min_offset(0),
+    charsz(1,1)
 {
     m_buf = GLShapeBuffer::create(true, true);
 }
@@ -34,16 +51,18 @@ FTFontWrapper::FTFontWrapper() :
 FTFontWrapper::~FTFontWrapper()
 {
     delete[] m_glyphs;
+    delete[] pixels;
     delete m_buf;
 }
 
 bool FTFontWrapper::load_font(const char *font_name, unsigned int font_size,
-                              bool outl)
+                              bool outline)
 {
     FT_Library library;
-    FT_Face face;
     FT_Error error;
 
+    outl = outline;
+
     error = FT_Init_FreeType(&library);
     if (error)
         die_noline("Failed to initialise freetype library.\n");
@@ -77,66 +96,21 @@ bool FTFontWrapper::load_font(const char *font_name, unsigned int font_size,
     error = FT_Set_Pixel_Sizes(face, font_size, font_size);
     ASSERT(!error);
 
-    // Get maximum advance
-    m_max_advance = coord_def(0,0);
-    int ascender  = face->ascender >> 6;
-    int min_y     = 100000;
-    int max_y     = 0;
-    int max_width = 0;
-    m_min_offset  = 0;
-    m_glyphs      = new GlyphInfo[256];
-    for (unsigned int c = 0; c < 256; c++)
-    {
-        m_glyphs[c].offset  = 0;
-        m_glyphs[c].advance = 0;
-        m_glyphs[c].renderable = false;
-
-        FT_Int glyph_index = FT_Get_Char_Index(face, c);
-        if (!glyph_index)
-            continue;
-
-        error = FT_Load_Glyph(face, glyph_index, FT_LOAD_RENDER |
-            (Options.tile_font_ft_light ? FT_LOAD_TARGET_LIGHT : 0));
-        ASSERT(!error);
-
-        FT_Bitmap *bmp = &face->glyph->bitmap;
-
-        int advance = face->glyph->advance.x >> 6;
-
-        m_max_advance.x = std::max(m_max_advance.x, advance);
-
-        int bmp_width  = bmp->width;
-        int bmp_top    = ascender - face->glyph->bitmap_top;
-        int bmp_bottom = ascender + bmp->rows - face->glyph->bitmap_top;
-        if (outl)
-        {
-            bmp_width  += 2;
-            bmp_top    -= 1;
-            bmp_bottom += 1;
-        }
-
-        max_width = std::max(max_width, bmp_width);
-        min_y = std::min(min_y, bmp_top);
-        max_y = std::max(max_y, bmp_bottom);
-
-        m_glyphs[c].offset  = face->glyph->bitmap_left;
-        m_glyphs[c].advance = advance;
-        m_glyphs[c].width   = bmp_width;
-
-        m_min_offset = std::min((char)m_min_offset, m_glyphs[c].offset);
-    }
-
-    // The ascender and text height given by FreeType2 is ridiculously large
-    // (e.g. 37 pixels high for 14 pixel font).  Use min and max bounding
-    // heights on the characters we care about to get better values for the
-    // text height and the ascender.
-    m_max_advance.y = max_y - min_y;
-    ascender       -= min_y;
-
+    // Get maximum advance and other global metrics
+    FT_Size_Metrics metrics = face->size->metrics;
+    m_max_advance   = coord_def(0,0);
+    m_max_advance.x = metrics.max_advance >> 6;
+    m_max_advance.y = (metrics.ascender-metrics.descender)>>6;
+    ascender        = (metrics.ascender>>6);
+    int max_width   = (face->bbox.xMax >> 6) - (face->bbox.xMin >> 6);
     int max_height  = m_max_advance.y;
+    m_min_offset    = 0;
+    m_glyphs        = new GlyphInfo[MAX_GLYPHS];
+
+    if (outl)
+        max_width += 2, max_height += 2;
 
     // Grow character size to power of 2
-    coord_def charsz(1,1);
     while (charsz.x < max_width)
         charsz.x *= 2;
     while (charsz.y < max_height)
@@ -146,45 +120,98 @@ bool FTFontWrapper::load_font(const char *font_name, unsigned int font_size,
     // Having to blow out 8-bit alpha values into full 32-bit textures is
     // kind of frustrating, but not all OpenGL implementations support the
     // "esoteric" ALPHA8 format and it's not like this texture is very large.
-    unsigned int   width  = 16 * charsz.x;
-    unsigned int   height = 16 * charsz.y;
-    unsigned char *pixels = new unsigned char[4 * width * height];
-    memset(pixels, 0, sizeof(unsigned char) * 4 * width * height);
+
+    // [frogbotherer] I think we can get memory usage lower by blowing out
+    // the texture as a whole out to a power of 2, instead of each individual
+    // character. Also, whilst GLES baulks at ALPHA8, there might be some
+    // other compression format that we can use to get the size down a bit
+    m_ft_width  = GLYPHS_PER_ROWCOL * charsz.x;
+    m_ft_height = GLYPHS_PER_ROWCOL * charsz.y;
+
+    pixels = new unsigned char[4 * charsz.x * charsz.y];
+    memset(pixels, 0, sizeof(unsigned char) * 4 * charsz.x * charsz.y);
+
+    dprintf("new font tex %d x %d x 4 = %dpx %d bytes\n",
+            m_ft_width, m_ft_height, m_ft_width * m_ft_height,
+            4 * m_ft_width * m_ft_height);
+
+    // initialise empty texture of correct size
+    m_tex.load_texture(NULL, m_ft_width, m_ft_height, MIPMAP_NONE);
 
     // Special case c = 0 for full block.
     {
+        m_glyphmap[0] = 0;
+        m_glyphs_top = 1;
+        m_glyphs_lru = 1; // otherwise LRU algorithm will overwrite 0
+        m_glyphs_mru = 0;
+        m_glyphs[0].offset  = 0;
+        m_glyphs[0].advance = 0;
         m_glyphs[0].renderable = false;
+        m_glyphs[0].uchar   = MISSING_CHAR;
+        m_glyphs[0].prev    = 0;
+        m_glyphs[0].next    = 0;
         for (int x = 0; x < max_width; x++)
             for (int y = 0; y < max_height; y++)
             {
-                unsigned int idx = x + y * width;
+                unsigned int idx = x + y * charsz.x;
                 idx *= 4;
-                pixels[idx] = 255;
+                pixels[idx]     = 255;
                 pixels[idx + 1] = 255;
                 pixels[idx + 2] = 255;
                 pixels[idx + 3] = 255;
             }
+        bool success = m_tex.load_texture(pixels, charsz.x, charsz.y,
+                                          MIPMAP_NONE, 0, 0);
+        ASSERT(success);
     }
 
-    for (unsigned int c = 1; c < 256; c++)
-    {
-        FT_Int glyph_index = FT_Get_Char_Index(face, c);
-        if (!glyph_index)
-        {
-            // If no mapping for this character, leave blank.
-            continue;
-        }
+    // precache common chars
+    for (int i = 0x20; i < 0x7f; i++)
+        map_unicode(i);
+    return true;
+}
+
+void FTFontWrapper::load_glyph(unsigned int c, ucs_t uchar)
+{
+    // get on with rendering the new glyph
+    FT_Error error;
+    m_glyphs[c].offset  = 0;
+    m_glyphs[c].advance = 0;
+    m_glyphs[c].renderable = false;
+
+    FT_Int glyph_index = FT_Get_Char_Index(face, uchar);
+
+    if (!glyph_index)
+        glyph_index = FT_Get_Char_Index(face, MISSING_CHAR);
+
+    error = FT_Load_Glyph(face, glyph_index, FT_LOAD_RENDER |
+        (Options.tile_font_ft_light ? FT_LOAD_TARGET_LIGHT : 0));
+    ASSERT(!error);
+
+    FT_Bitmap *bmp = &face->glyph->bitmap;
+    ASSERT(bmp);
+
+    int advance = face->glyph->advance.x >> 6;
 
-        error = FT_Load_Glyph(face, glyph_index, FT_LOAD_RENDER |
-            (Options.tile_font_ft_light ? FT_LOAD_TARGET_LIGHT : 0));
-        ASSERT(!error);
+    int bmp_width  = bmp->width;
+    int bmp_top    = ascender - face->glyph->bitmap_top;
+    int bmp_bottom = ascender + bmp->rows - face->glyph->bitmap_top;
+    if (outl)
+    {
+        bmp_width  += 2;
+        bmp_top    -= 1;
+        bmp_bottom += 1;
+    }
 
-        FT_Bitmap *bmp = &face->glyph->bitmap;
-        ASSERT(bmp);
-        // Some glyphs (e.g. ' ') don't get a buffer.
-        if (!bmp->buffer)
-            continue;
+    m_glyphs[c].offset  = face->glyph->bitmap_left;
+    m_glyphs[c].advance = advance;
+    m_glyphs[c].width   = bmp_width;
 
+    // Some glyphs (e.g. ' ') don't get a buffer.
+    if (!bmp->buffer)
+        m_glyphs[c].renderable = false;
+    else
+    {
         m_glyphs[c].renderable = true;
 
         int vert_offset = ascender - face->glyph->bitmap_top;
@@ -193,37 +220,34 @@ bool FTFontWrapper::load_font(const char *font_name, unsigned int font_size,
         ASSERT(bmp->num_grays == 256);
 
         // Horizontal offset stored in m_glyphs and handled when drawing
-        unsigned int offset_x = (c % 16) * charsz.x;
-        unsigned int offset_y = (c / 16) * charsz.y + vert_offset;
-
+        const unsigned int offset_x = 0;
+        const unsigned int offset_y = vert_offset;
+        memset(pixels, 0, sizeof(unsigned char) * 4 * charsz.x * charsz.y);
         if (outl)
         {
             const int charw = bmp->width;
-            for (int x = -1; x <= bmp->width; x++)
-                for (int y = -1; y <= bmp->rows; y++)
+            for (int x = 0; x < bmp->width; x++)
+                for (int y = 0; y < bmp->rows; y++)
                 {
-                    bool x_valid = x >= 0 && x < bmp->width;
-                    bool y_valid = y >= 0 && y < bmp->rows;
-                    bool valid   = x_valid && y_valid;
-                    unsigned char orig = valid ? bmp->buffer[x + charw * y] : 0;
+                    unsigned int idx = offset_x+x+1 + (offset_y+y+1) * charsz.x;
+                    idx *= 4;
+
+                    unsigned char orig = bmp->buffer[x + charw * y];
 
                     unsigned char edge = 0;
-                    if (y_valid && x > 0)
+                    if (x > 0)
                         edge = std::max(bmp->buffer[(x-1) + charw * y], edge);
-                    if (x_valid && y > 0)
+                    if (y > 0)
                         edge = std::max(bmp->buffer[x + charw * (y-1)], edge);
-                    if (y_valid && x < bmp->width - 1)
+                    if (x < bmp->width - 1)
                         edge = std::max(bmp->buffer[(x+1) + charw * y], edge);
-                    if (x_valid && y < bmp->rows - 1)
+                    if (y < bmp->rows - 1)
                         edge = std::max(bmp->buffer[x + charw * (y+1)], edge);
 
-                    unsigned int idx = offset_x+x+1 + (offset_y+y+1) * width;
-                    idx *= 4;
-
                     pixels[idx] = orig;
                     pixels[idx + 1] = orig;
                     pixels[idx + 2] = orig;
-                    pixels[idx + 3] = std::min(orig + edge, 255);
+                    pixels[idx + 3] = std::min((int)orig + edge, 255);
                 }
         }
         else
@@ -231,32 +255,107 @@ bool FTFontWrapper::load_font(const char *font_name, unsigned int font_size,
             for (int x = 0; x < bmp->width; x++)
                 for (int y = 0; y < bmp->rows; y++)
                 {
-                    unsigned int idx = offset_x + x + (offset_y + y) * width;
+                    unsigned int idx = offset_x + x + (offset_y + y) * charsz.x;
                     idx *= 4;
-                    unsigned char alpha = bmp->buffer[x + bmp->width * y];
-                    pixels[idx] = 255;
-                    pixels[idx + 1] = 255;
-                    pixels[idx + 2] = 255;
-                    pixels[idx + 3] = alpha;
+                    if (x < bmp->width && y < bmp->rows)
+                    {
+                        unsigned char alpha = bmp->buffer[x + bmp->width * y];
+                        pixels[idx] = 255;
+                        pixels[idx + 1] = 255;
+                        pixels[idx + 2] = 255;
+                        pixels[idx + 3] = alpha;
+                    }
                 }
         }
+        bool success = m_tex.load_texture(pixels, charsz.x, charsz.y,
+                            MIPMAP_NONE,
+                            (c % GLYPHS_PER_ROWCOL) * charsz.x,
+                            (c / GLYPHS_PER_ROWCOL) * charsz.y);
+        ASSERT(success);
     }
+}
 
-    bool success = m_tex.load_texture(pixels, width, height,
-                                      MIPMAP_NONE);
+unsigned int FTFontWrapper::map_unicode(ucs_t uchar)
+{
+    unsigned int c;  // index in m_glyphs
+    if (m_glyphmap.find(uchar) == m_glyphmap.end())
+    {
+        // work out which glyph we can overwrite if we've gone over MAX_GLYPHS
+        if (m_glyphs_top == MAX_GLYPHS)
+        {
+            dprintf("replacing %d (%lc) with %d (%lc)\n",
+                    m_glyphs[m_glyphs_lru].uchar,
+                    m_glyphs[m_glyphs_lru].uchar,
+                    uchar,
+                    uchar);
+            // create a pointer in gmap to the lru entry in gdata
+            c = m_glyphs_lru;
+            // delete lru glyph from map
+            m_glyphmap.erase(m_glyphs[m_glyphs_lru].uchar);
+            // move lru on to next
+            m_glyphs_lru = m_glyphs[c].next;
+            m_glyphs[m_glyphs_lru].prev = 0;
+        }
+        else // glyph data is not full
+        {
+            // create a pointer in m_glyphmap to the top of m_glyphs
+            c = m_glyphs_top;
+            // move top index on
+            m_glyphs_top++;
+        }
 
-    delete[] pixels;
+        // set some default prev/next values
+        m_glyphs[c].prev = m_glyphs_mru;
+        m_glyphs[m_glyphs_mru].next = c;
+        m_glyphs[c].next = 0;
+        // update links between char and map
+        m_glyphs[c].uchar = uchar;
+        m_glyphmap[uchar] = c;
 
-    return success;
-}
+        load_glyph(c, uchar);
+        n_subst++;
 
-// This function should be removed once we can support more than ISO-8859-1.
-static ucs_t _fallback_char(ucs_t c)
-{
-    // Weed out characters we can't draw.
-    if (c > 0xFF) // TODO: try to transliterate
-        c = 0xBF; // reversed question mark
-    return c;
+        dprintf("mapped %d (%x; %lc) to %d\n", uchar, uchar, uchar, c);
+    }
+    else // we found uchar in glyphmap
+    {
+        c = m_glyphmap[uchar];
+        if (m_glyphs_mru != c)
+        {
+            // point the <char previous to this one> to the <char after this one> and vice-versa
+            dprintf("moving %lc: %lc -> %lc; %lc <- %lc",
+                    uchar,
+                    m_glyphs[m_glyphs[m_glyphmap[uchar]].prev].uchar,
+                    m_glyphs[m_glyphs[m_glyphmap[uchar]].next].uchar,
+                    m_glyphs[m_glyphs[m_glyphmap[uchar]].next].uchar,
+                    m_glyphs[m_glyphs[m_glyphmap[uchar]].prev].uchar);
+            m_glyphs[m_glyphs[c].prev].next = m_glyphs[c].next;
+            m_glyphs[m_glyphs[c].next].prev = m_glyphs[c].prev;
+        }
+    }
+
+    // regardless of how we came about 'c'
+    if (m_glyphs_mru != c)
+    {
+        // point the last character we wrote out to the one we're writing
+        dprintf("updating %lc, next = %lc",
+                m_glyphs[m_glyphs_mru].uchar, uchar);
+        m_glyphs[m_glyphs_mru].next = c;
+        m_glyphs[c].prev = m_glyphs_mru;
+    }
+
+    // update the mru to this one
+    m_glyphs_mru = c;
+    // if we've just used the lru glyph, move onto the next one
+    if (m_glyphs_mru == m_glyphs_lru && m_glyphs[m_glyphs_lru].next != 0)
+        m_glyphs_lru = m_glyphs[m_glyphs_lru].next;
+
+    dprintf("rendering %d (%x; <<<<<<%lc>>>>>>); lru is %lc, next lru is %lc\n",
+            uchar, uchar, uchar,
+            m_glyphs[m_glyphs_lru].uchar,
+            m_glyphs[m_glyphs[m_glyphs_lru].next].uchar);
+
+    return m_glyphmap[uchar];
 }
 
 void FTFontWrapper::render_textblock(unsigned int x_pos, unsigned int y_pos,
@@ -273,6 +372,7 @@ void FTFontWrapper::render_textblock(unsigned int x_pos, unsigned int y_pos,
 
     ASSERT(m_buf);
     m_buf->clear();
+    n_subst = 0;
 
     float texcoord_dy = (float)m_max_advance.y / (float)m_tex.height();
 
@@ -280,7 +380,7 @@ void FTFontWrapper::render_textblock(unsigned int x_pos, unsigned int y_pos,
     {
         for (unsigned int x = 0; x < width; x++)
         {
-            ucs_t c = _fallback_char(chars[i]);
+            unsigned int c = map_unicode(chars[i]);
             uint8_t col_bg = colours[i] >> 4;
             uint8_t col_fg = colours[i] & 0xF;
 
@@ -302,8 +402,8 @@ void FTFontWrapper::render_textblock(unsigned int x_pos, unsigned int y_pos,
             {
                 int this_width = m_glyphs[c].width;
 
-                float tex_x = (float)(c % 16) / 16.0f;
-                float tex_y = (float)(c / 16) / 16.0f;
+                float tex_x = (float)(c % GLYPHS_PER_ROWCOL) / (float)GLYPHS_PER_ROWCOL;
+                float tex_y = (float)(c / GLYPHS_PER_ROWCOL) / (float)GLYPHS_PER_ROWCOL;
                 float tex_x2 = tex_x + (float)this_width / (float)m_tex.width();
                 float tex_y2 = tex_y + texcoord_dy;
 
@@ -320,12 +420,26 @@ void FTFontWrapper::render_textblock(unsigned int x_pos, unsigned int y_pos,
 
             i++;
             adv.x += m_glyphs[c].advance - m_glyphs[c].offset;
+
+            // See if we need to flush prematurely.
+            if (n_subst == MAX_GLYPHS - 1)
+            {
+                draw_m_buf(x_pos, y_pos, drop_shadow);
+                m_buf->clear();
+                n_subst = 0;
+            }
         }
 
         adv.x = 0;
         adv.y += m_max_advance.y;
     }
 
+    draw_m_buf(x_pos, y_pos, drop_shadow);
+}
+
+void FTFontWrapper::draw_m_buf(unsigned int x_pos, unsigned int y_pos,
+                               bool drop_shadow)
+{
     if (!m_buf->size())
         return;
 
@@ -399,13 +513,13 @@ unsigned int FTFontWrapper::string_height(const char *text) const
     return char_height() * height;
 }
 
-unsigned int FTFontWrapper::string_width(const formatted_string &str) const
+unsigned int FTFontWrapper::string_width(const formatted_string &str)
 {
     std::string temp = str.tostring();
     return string_width(temp.c_str());
 }
 
-unsigned int FTFontWrapper::string_width(const char *text) const
+unsigned int FTFontWrapper::string_width(const char *text)
 {
     unsigned int base_width = std::max(-m_min_offset, 0);
     unsigned int max_width = 0;
@@ -422,8 +536,9 @@ unsigned int FTFontWrapper::string_width(const char *text) const
         }
         else
         {
-            width += m_glyphs[*itr].advance;
-            adjust = std::max(0, m_glyphs[*itr].width - m_glyphs[*itr].advance);
+            unsigned int c = map_unicode(*itr);
+            width += m_glyphs[c].advance;
+            adjust = std::max(0, m_glyphs[c].width - m_glyphs[c].advance);
         }
     }
 
@@ -437,7 +552,7 @@ int FTFontWrapper::find_index_before_width(const char *text, int max_width)
 
     for (int i = 0; text[i]; i++)
     {
-        unsigned char c = text[i];
+        unsigned int c = map_unicode(text[i]);
         width += m_glyphs[c].advance;
         int adjust = std::max(0, m_glyphs[c].width - m_glyphs[c].advance);
         if (width + adjust > max_width)
@@ -634,9 +749,7 @@ void FTFontWrapper::store(FontBuffer &buf, float &x, float &y,
             y += m_max_advance.y;
         }
         else
-        {
             store(buf, x, y, c, col);
-        }
     }
 }
 
@@ -668,9 +781,9 @@ void FTFontWrapper::store(FontBuffer &buf, float &x, float &y,
 }
 
 void FTFontWrapper::store(FontBuffer &buf, float &x, float &y,
-                          ucs_t c, const VColour &col)
+                          ucs_t ch, const VColour &col)
 {
-    c = _fallback_char(c);
+    unsigned int c = map_unicode(ch);
     if (!m_glyphs[c].renderable)
     {
         x += m_glyphs[c].advance;
@@ -684,10 +797,10 @@ void FTFontWrapper::store(FontBuffer &buf, float &x, float &y,
     float pos_ex = pos_sx + this_width;
     float pos_ey = y + m_max_advance.y;
 
-    float tex_sx = (float)(c % 16) / 16.0f;
-    float tex_sy = (float)(c / 16) / 16.0f;
-    float tex_ex = tex_sx + (float)this_width / (float)m_tex.width();
-    float tex_ey = tex_sy + (float)m_max_advance.y / (float)m_tex.height();
+    float tex_sx = (float)(c % GLYPHS_PER_ROWCOL) / (float)GLYPHS_PER_ROWCOL;
+    float tex_sy = (float)(c / GLYPHS_PER_ROWCOL) / (float)GLYPHS_PER_ROWCOL;
+    float tex_ex = tex_sx + (float)this_width / (float)(GLYPHS_PER_ROWCOL*charsz.x);//(float)m_tex.width();
+    float tex_ey = tex_sy + (float)m_max_advance.y / (float)(GLYPHS_PER_ROWCOL*charsz.y);//(float)m_tex.height();
 
     GLWPrim rect(pos_sx, pos_sy, pos_ex, pos_ey);
     rect.set_tex(tex_sx, tex_sy, tex_ex, tex_ey);