java-topology/defects/raylib/patch/raylib-0001-getglyphindex-hashmap.md

UNDF: UNDF-2026-000000259

raylib-0001: GetGlyphIndex — O(T×G) linear scan per character in all text hot paths

CWE-407 — Algorithmic Complexity

Field	Value
ID	raylib-0001
Severity	HIGH
Ecosystem	raylib
Package	rtext
File	src/rtext.c
Lines	1453–1479 (GetGlyphIndex), callers: 1292, 1363, 1420, 1488, 1499
Complexity	O(T × G) per text render/measure call
Hot path	Every DrawText, DrawTextEx, MeasureText, MeasureTextEx, DrawTextCodepoints

Background

raylib exposes a Font struct that holds an array of GlyphInfo[] indexed by position, not by codepoint value. When text is drawn or measured, each character must be converted from its Unicode codepoint to an array index via GetGlyphIndex.

The function is called once per character in every text rendering and measurement operation, making it the innermost operation in all text paths.

Defect

GetGlyphIndex performs a linear scan over the entire glyph array to find the matching codepoint:

// src/rtext.c:1453
int GetGlyphIndex(Font font, int codepoint)
{
    int index = 0;
    if (!IsFontValid(font)) return index;

#define SUPPORT_UNORDERED_CHARSET
#if defined(SUPPORT_UNORDERED_CHARSET)
    int fallbackIndex = 0;      // Get index of fallback glyph '?'

    // Look for character index in the unordered charset
    for (int i = 0; i < font.glyphCount; i++)
    {
        if (font.glyphs[i].value == 63) fallbackIndex = i;

        if (font.glyphs[i].value == codepoint)
        {
            index = i;
            break;
        }
    }

    if ((index == 0) && (font.glyphs[0].value != codepoint)) index = fallbackIndex;
#else
    index = codepoint - 32;
#endif

    return index;
}

The #define SUPPORT_UNORDERED_CHARSET is defined right before the #if check, so this branch always executes and the O(1) fast path is dead code.

Call sites that call GetGlyphIndex inside per-character loops:

Function	File	Hot loop
DrawTextCodepoints	rtext.c:1290	for (int i = 0; i < codepointCount; i++)
MeasureTextEx	rtext.c:1357	for (int i = 0; i < size;)
MeasureTextCodepoints	rtext.c:1417	for (int i = 0; i < length; i++)
DrawTextCodepoint (via DrawText)	rtext.c:1263	called per character

With a font containing G glyphs and a string of T characters, every draw or measure call costs O(T × G) comparisons. A full Unicode font (G ≈ 4000–10000 glyphs) rendering a paragraph (T ≈ 500 chars) performs 2–5 million comparisons per frame just for text layout.

Fix

Build a codepoint→index lookup table at font load time. raylib already has rlHashTable or can use a simple sorted array with binary search. The simplest approach is a hash table keyed by codepoint:

Option A — hash map (O(1) lookup after O(G) build):

// In Font struct (raylib.h), add:
// int *glyphIndex;   // hash table: codepoint → glyph array index

// At font load time (LoadFontData / GenImageFontAtlas):
void BuildGlyphIndex(Font *font)
{
    // Allocate power-of-two hash table sized 2× glyph count
    int tableSize = 1;
    while (tableSize < font->glyphCount * 2) tableSize <<= 1;
    font->glyphIndex = (int *)RL_CALLOC(tableSize, sizeof(int));
    int mask = tableSize - 1;
    // sentinel: -1 = empty slot
    for (int i = 0; i < tableSize; i++) font->glyphIndex[i] = -1;
    for (int i = 0; i < font->glyphCount; i++)
    {
        int h = (font->glyphs[i].value * 2654435761u) & mask;
        while (font->glyphIndex[h] != -1) h = (h + 1) & mask;
        font->glyphIndex[h] = i;
    }
}

// GetGlyphIndex becomes O(1):
int GetGlyphIndex(Font font, int codepoint)
{
    if (!IsFontValid(font)) return 0;
    if (!font.glyphIndex) { /* fallback linear scan */ }
    int tableSize = /* stored in Font or inferred */ ...;
    int mask = tableSize - 1;
    int h = ((unsigned)codepoint * 2654435761u) & mask;
    while (font.glyphIndex[h] != -1)
    {
        int i = font.glyphIndex[h];
        if (font.glyphs[i].value == codepoint) return i;
        h = (h + 1) & mask;
    }
    return 0;  // fallback to '?'
}

Option B — sort glyphs array by codepoint at load time and use binary search (O(log G) lookup, zero additional memory):

// Sort once at load:
int CompareGlyphs(const void *a, const void *b) {
    return ((GlyphInfo *)a)->value - ((GlyphInfo *)b)->value;
}
qsort(font->glyphs, font->glyphCount, sizeof(GlyphInfo), CompareGlyphs);

// Binary search in GetGlyphIndex replaces the #else branch:
// Remove #define SUPPORT_UNORDERED_CHARSET and use binary search always.

Option B is the minimal-change fix and eliminates the SUPPORT_UNORDERED_CHARSET dead-code hazard.

Speedup

G (font glyph count)	T (chars per frame)	Before (ops)	After (ops)	Speedup
95 (ASCII)	500	47,500	500	95×
1000 (extended)	500	500,000	500	1000×
4000 (CJK subset)	500	2,000,000	500	4000×
10,000 (full Unicode)	500	5,000,000	500	10,000×

For ASCII-only games the improvement is ~95× per draw call. For internationalized titles using large Unicode fonts the pathology reaches millions of comparisons per frame, making text rendering a bottleneck even at low scene complexity.

Note

The #define SUPPORT_UNORDERED_CHARSET pragma immediately before the #if check ensures the efficient index = codepoint - 32 path (the #else branch) can never execute. The dead code comment appears to be an old optimization path left behind when the unordered charset support was added. Removing the define and restoring the #else path would only work for fonts built in ASCII order starting at codepoint 32, so the hash map or sorted binary search approach is the correct general fix.