[Git][freetype/freetype][master] [bdf, pfr, psnames] Accelarate charmap searches.

[Alexei Podtelezhnikov (@apodtele)]

Alexei Podtelezhnikov pushed to branch master at FreeType / FreeType

Commits:

• 6139f2b6
  by Alexei Podtelezhnikov at 2022-11-06T13:12:47-05:00

  [bdf, pfr, psnames] Accelarate charmap searches.
  
  The binary searches within charmaps can be accelerated because they
  often contain dense continuous blocks of character codes. Within such
  blocks, you can predict matches based on misses.  This method has been
  deployed in `bdf` since 0f122fef34; we only refactor it there.  We now
  use it in `pfr` and `psnames`, which speeds up the unicode charmap
  access by about 50% in PFR and Type 1 fonts.
  
  * src/bdf/bdfdrivr.c (bdf_cmap_char_{index,next}): Refactor.
  * src/pfr/pfrcmap.c (pfr_cmap_char_{index,next}): Predict `mid` based
  on the mismatch distance.
  * src/psnames/psmodule.c (ps_unicodes_char_{index,next}): Ditto.
  

3 changed files:

• src/bdf/bdfdrivr.c
• src/pfr/pfrcmap.c
• src/psnames/psmodule.c

Changes:

src/bdf/bdfdrivr.c

---

...	...	@@ -92,24 +92,18 @@ THE SOFTWARE.
92	92	{
93	93	BDF_CMap cmap = (BDF_CMap)bdfcmap;
94	94	BDF_encoding_el* encodings = cmap->encodings;
95		- FT_ULong min, max, mid; /* num_encodings */
96	95	FT_UShort result = 0; /* encodings->glyph */
97	96
	97	+ FT_ULong min = 0;
	98	+ FT_ULong max = cmap->num_encodings;
	99	+ FT_ULong mid = ( min + max ) >> 1;
98	100
99		- min = 0;
100		- max = cmap->num_encodings;
101		- mid = ( min + max ) >> 1;
102	101
103	102	while ( min < max )
104	103	{
105		- FT_ULong code;
	104	+ FT_ULong code = encodings[mid].enc;
106	105
107	106
108		- if ( mid >= max || mid < min )
109		- mid = ( min + max ) >> 1;
110		-
111		- code = encodings[mid].enc;
112		-
113	107	if ( charcode == code )
114	108	{
115	109	/* increase glyph index by 1 -- */
...	...	@@ -123,8 +117,10 @@ THE SOFTWARE.
123	117	else
124	118	min = mid + 1;
125	119
126		- /* prediction in a continuous block */
	120	+ /* reasonable prediction in a continuous block */
127	121	mid += charcode - code;
	122	+ if ( mid >= max || mid < min )
	123	+ mid = ( min + max ) >> 1;
128	124	}
129	125
130	126	return result;
...	...	@@ -137,25 +133,19 @@ THE SOFTWARE.
137	133	{
138	134	BDF_CMap cmap = (BDF_CMap)bdfcmap;
139	135	BDF_encoding_el* encodings = cmap->encodings;
140		- FT_ULong min, max, mid; /* num_encodings */
141	136	FT_UShort result = 0; /* encodings->glyph */
142	137	FT_ULong charcode = *acharcode + 1;
143	138
	139	+ FT_ULong min = 0;
	140	+ FT_ULong max = cmap->num_encodings;
	141	+ FT_ULong mid = ( min + max ) >> 1;
144	142
145		- min = 0;
146		- max = cmap->num_encodings;
147		- mid = ( min + max ) >> 1;
148	143
149	144	while ( min < max )
150	145	{
151		- FT_ULong code; /* same as BDF_encoding_el.enc */
	146	+ FT_ULong code = encodings[mid].enc;
152	147
153	148
154		- if ( mid >= max || mid < min )
155		- mid = ( min + max ) >> 1;
156		-
157		- code = encodings[mid].enc;
158		-
159	149	if ( charcode == code )
160	150	{
161	151	/* increase glyph index by 1 -- */
...	...	@@ -171,6 +161,8 @@ THE SOFTWARE.
171	161
172	162	/* prediction in a continuous block */
173	163	mid += charcode - code;
	164	+ if ( mid >= max || mid < min )
	165	+ mid = ( min + max ) >> 1;
174	166	}
175	167
176	168	charcode = 0;

src/pfr/pfrcmap.c

---

...	...	@@ -69,17 +69,14 @@
69	69	pfr_cmap_char_index( PFR_CMap cmap,
70	70	FT_UInt32 char_code )
71	71	{
72		- FT_UInt min = 0;
73		- FT_UInt max = cmap->num_chars;
	72	+ FT_UInt min = 0;
	73	+ FT_UInt max = cmap->num_chars;
	74	+ FT_UInt mid = min + ( max - min ) / 2;
	75	+ PFR_Char gchar;
74	76
75	77
76	78	while ( min < max )
77	79	{
78		- PFR_Char gchar;
79		- FT_UInt mid;
80		-
81		-
82		- mid = min + ( max - min ) / 2;
83	80	gchar = cmap->chars + mid;
84	81
85	82	if ( gchar->char_code == char_code )
...	...	@@ -89,6 +86,11 @@
89	86	min = mid + 1;
90	87	else
91	88	max = mid;
	89	+
	90	+ /* reasonable prediction in a continuous block */
	91	+ mid += char_code - gchar->char_code;
	92	+ if ( mid >= max || mid < min )
	93	+ mid = min + ( max - min ) / 2;
92	94	}
93	95	return 0;
94	96	}
...	...	@@ -106,13 +108,12 @@
106	108	{
107	109	FT_UInt min = 0;
108	110	FT_UInt max = cmap->num_chars;
109		- FT_UInt mid;
	111	+ FT_UInt mid = min + ( max - min ) / 2;
110	112	PFR_Char gchar;
111	113
112	114
113	115	while ( min < max )
114	116	{
115		- mid = min + ( ( max - min ) >> 1 );
116	117	gchar = cmap->chars + mid;
117	118
118	119	if ( gchar->char_code == char_code )
...	...	@@ -132,6 +133,11 @@
132	133	min = mid + 1;
133	134	else
134	135	max = mid;
	136	+
	137	+ /* reasonable prediction in a continuous block */
	138	+ mid += char_code - gchar->char_code;
	139	+ if ( mid >= max || mid < min )
	140	+ mid = min + ( max - min ) / 2;
135	141	}
136	142
137	143	/* we didn't find it, but we have a pair just above it */

src/psnames/psmodule.c

---

...	...	@@ -412,21 +412,18 @@
412	412	ps_unicodes_char_index( PS_Unicodes table,
413	413	FT_UInt32 unicode )
414	414	{
415		- PS_UniMap *min, *max, *mid, *result = NULL;
	415	+ PS_UniMap *result = NULL;
	416	+ PS_UniMap *min = table->maps;
	417	+ PS_UniMap *max = min + table->num_maps;
	418	+ PS_UniMap *mid = min + ( ( max - min ) >> 1 );
416	419
417	420
418	421	/* Perform a binary search on the table. */
419		-
420		- min = table->maps;
421		- max = min + table->num_maps - 1;
422		-
423		- while ( min <= max )
	422	+ while ( min < max )
424	423	{
425	424	FT_UInt32 base_glyph;
426	425
427	426
428		- mid = min + ( ( max - min ) >> 1 );
429		-
430	427	if ( mid->unicode == unicode )
431	428	{
432	429	result = mid;
...	...	@@ -438,13 +435,15 @@
438	435	if ( base_glyph == unicode )
439	436	result = mid; /* remember match but continue search for base glyph */
440	437
441		- if ( min == max )
442		- break;
443		-
444	438	if ( base_glyph < unicode )
445	439	min = mid + 1;
446	440	else
447		- max = mid - 1;
	441	+ max = mid;
	442	+
	443	+ /* reasonable prediction in a continuous block */
	444	+ mid += unicode - base_glyph;
	445	+ if ( mid >= max || mid < min )
	446	+ mid = min + ( ( max - min ) >> 1 );
448	447	}
449	448
450	449	if ( result )
...	...	@@ -465,14 +464,13 @@
465	464	{
466	465	FT_UInt min = 0;
467	466	FT_UInt max = table->num_maps;
468		- FT_UInt mid;
	467	+ FT_UInt mid = min + ( ( max - min ) >> 1 );
469	468	PS_UniMap* map;
470	469	FT_UInt32 base_glyph;
471	470
472	471
473	472	while ( min < max )
474	473	{
475		- mid = min + ( ( max - min ) >> 1 );
476	474	map = table->maps + mid;
477	475
478	476	if ( map->unicode == char_code )
...	...	@@ -490,6 +488,11 @@
490	488	min = mid + 1;
491	489	else
492	490	max = mid;
	491	+
	492	+ /* reasonable prediction in a continuous block */
	493	+ mid += char_code - base_glyph;
	494	+ if ( mid >= max || mid < min )
	495	+ mid = min + ( max - min ) / 2;
493	496	}
494	497
495	498	if ( result )

—
View it on GitLab.
You're receiving this email because of your account on gitlab.freedesktop.org. Manage all notifications · Help