Performance issue in font.c

[windows-server-2003]

The function fontGlyphIndexFromCodePoint is called for every character when drawing text with citro2d, for example. The system font seems to handle characters using three mappings: CMAP_TYPE_DIRECT, CMAP_TYPE_TABLE, CMAP_TYPE_SCAN The first two are fine, but for CMAP_TYPE_SCAN libctru currently does a linear search, which may be slow. It seems that the codepoints of the characters in one CMAP_TYPE_SCAN cmap are monotonically increasing, so we can do a binary search to significantly reduce running time. In fact, on my JPN 3ds, the mapping of the default font includes one cmap of type CMAP_TYPE_SCAN with 5811 characters in it. I test on a new 3ds with "龍" (Dragon) which is one of the standard Japanese characters with a large codepoint, and it was only 15k calls/s. This means we can only draw 250 characters if it's 60FPS. On my test implementation of the binary search, it marked 500k calls/s: 8000 characters/frame I am curious if you would accept a PR if I did.

Here is my test implementation to see how simple it would be:

Test implementation

Before:

			int j;
			for (j = 0; j < cmap->nScanEntries; j ++)
				if (cmap->scanEntries[j].code == codePoint)
					break;
			if (j < cmap->nScanEntries)
			{
				ret = cmap->scanEntries[j].glyphIndex;
				break;
			}

After:

			int l = -1;
			int r = cmap->nScanEntries;
			while (r - l > 1)
			{
				int middle = l + (r - l) / 2;
				if (cmap->scanEntries[middle].code > codePoint) r = middle;
				else l = middle; 
			}
			if (l >= 0 && cmap->scanEntries[l].code == codePoint)
			{
				ret = cmap->scanEntries[l].glyphIndex;
				break;
			}

[windows-server-2003]

P.S. Test on old 3DS Current: 4.1k calls/s = 68 characters/frame Binary search: 133k calls/s = 2.2k characters/frame

[mtheall]

You know I thought about this while implementing bcfnt but the format doesn't guarantee that the glyphs are sorted. Can we assume that they are always sorted? Output from bcfnt will be. We could easily check all the official system fonts. Do we care about fonts from anywhere else?

[fincs]

I think we should only care about official system fonts + fonts created by our own mkbcfnt tool.

[piepie62]

Theoretically I could see an argument for caring about game fonts but I find it unlikely that they won't match system fonts; the conversion tool used is very likely the same

[WinterMute]

A PR would be very much appreciated if you're still interested in pursuing this.