95710 - Compress 8Kbyte Font Glyph Maps

Status: RESOLVED DUPLICATE of bug 102706

(Core :: Internationalization, defect)

Description

[kill this account]

Every loaded font has a 64Kbit (8Kbyte) character map indicating which chars
have glyphs.

If we break the 16 bits into ranges and eliminate the space for the unused
parts we can reduce map memory by 80-90%

Assume we use 3 ranges:

   Upper range = bits 15-12
   Mid range   = bits 11-8
   lower range = bits 7-0

Let us call the lower range a "page".

Each page requires 256 bits or 32 bytes.

Each mid range is an array of 16 pointers to pages which
would take 16 * 4 = 64 bytes (assumming a 4 byte pointer).

The one upper range is an array of 16 pointers = 64 bytes.

We can avoid testing for null upper/mid range pointers by adding exactly one
"empty" mid range and exactly one "empty" page and pointing the unused upper
pointer to the empty mid and the unused mid pointer to the empty page.

The Arial font on Windows has 665 chars composing 3 mid ranges and 15 pages. 
It is fairly typical of the fonts I find on my WinNT system (43 of 50 have
fonts with < 680 chars).

Fixed usage:

  64 = 1*64 bytes for the upper range
  64 = 1*64 for the empty mid range
  32 = 1*23 for the empty page

Font specific:

 192 = 3*64 bytes for the non-empty mid range
 480 = 15*32 bytes for the non-empty pages

----
Total:
 832 => 90% reduction from 8192 bytes

Cyberbit, the worst case on my WInNT system has 30732 glyphs and
its map would take 6336 bytes or 23% savings.

  64 = 1*64 bytes for the upper range
  64 = 1*64 for the empty mid range
  32 = 1*23 for the empty page
 896 = 14*64 bytes for the non-empty mid range (estimate)
5280 = 165*64 pages 
----
6336 => 23% reduction from 8192

50*8k = 400k
43*832 + 7*6336 = 80k

400 - 80 = 320K savings
=> 80% memory reduction

(the actual numbers are slightly better since I took the worst case font sizes)

Comment 1

[R.K.Aa.]

in bug 95518 you point out the existance of bug 75260, asking whether it's a dup.
Bug 75260 has the exact same wording as *this* bug. So.. is *this* a dup?

Comment 2

[kill this account]

ftang asked me to open a windows version and a linux version

Comment 3

[Frank Tang]

this is the window version. reassign to shanjian to work on . shanjian, talk to
bstell for details. this is probably a dup of 102706

*** This bug has been marked as a duplicate of 102706 ***