1/*
2
3Copyright 1991, 1998  The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included
12in all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
18OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
19ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
20OTHER DEALINGS IN THE SOFTWARE.
21
22Except as contained in this notice, the name of The Open Group shall
23not be used in advertising or otherwise to promote the sale, use or
24other dealings in this Software without prior written authorization
25from The Open Group.
26
27*/
28
29/*
30 * Author:  Keith Packard, MIT X Consortium
31 */
32
33#ifdef HAVE_CONFIG_H
34#include <config.h>
35#endif
36#include    <X11/fonts/fontmisc.h>
37#include    <X11/fonts/fontstruct.h>
38#include    <X11/fonts/FSproto.h>
39#include    <X11/fonts/fontutil.h>
40
41/* Define global here...  doesn't hurt the servers, and avoids
42   unresolved references in font clients.  */
43
44static int defaultGlyphCachingMode = DEFAULT_GLYPH_CACHING_MODE;
45int glyphCachingMode = DEFAULT_GLYPH_CACHING_MODE;
46
47void
48GetGlyphs(FontPtr font,
49	  unsigned long count,
50	  unsigned char *chars,
51	  FontEncoding fontEncoding,
52	  unsigned long *glyphcount,	/* RETURN */
53	  CharInfoPtr *glyphs)		/* RETURN */
54{
55    (*font->get_glyphs) (font, count, chars, fontEncoding, glyphcount, glyphs);
56}
57
58#define MIN(a,b)    ((a)<(b)?(a):(b))
59#define MAX(a,b)    ((a)>(b)?(a):(b))
60
61void
62QueryGlyphExtents(FontPtr pFont,
63		  CharInfoPtr *charinfo,
64		  unsigned long count,
65		  ExtentInfoRec *info)
66{
67    register unsigned long i;
68    xCharInfo  *pCI;
69
70    info->drawDirection = pFont->info.drawDirection;
71
72    info->fontAscent = pFont->info.fontAscent;
73    info->fontDescent = pFont->info.fontDescent;
74
75    if (count != 0) {
76
77	pCI = &((*charinfo)->metrics); charinfo++;
78	/* ignore nonexisting characters when calculating text extents */
79	if ( !((pCI->characterWidth == 0)
80	       && (pCI->rightSideBearing == 0)
81	       && (pCI->leftSideBearing == 0)
82	       && (pCI->ascent == 0)
83	       && (pCI->descent == 0)) ) {
84	    info->overallAscent = pCI->ascent;
85	    info->overallDescent = pCI->descent;
86	    info->overallLeft = pCI->leftSideBearing;
87	    info->overallRight = pCI->rightSideBearing;
88	    info->overallWidth = pCI->characterWidth;
89	}
90
91	if (pFont->info.constantMetrics && pFont->info.noOverlap) {
92	    info->overallWidth *= count;
93	    info->overallRight += (info->overallWidth -
94				   pCI->characterWidth);
95	} else {
96	    for (i = 1; i < count; i++) {
97		pCI = &((*charinfo)->metrics); charinfo++;
98		/* ignore nonexisting characters when calculating extents */
99		if ( !((pCI->characterWidth == 0)
100		       && (pCI->rightSideBearing == 0)
101		       && (pCI->leftSideBearing == 0)
102		       && (pCI->ascent == 0)
103		       && (pCI->descent == 0)) ) {
104		    info->overallAscent = MAX(
105					      info->overallAscent,
106					      pCI->ascent);
107		    info->overallDescent = MAX(
108					       info->overallDescent,
109					       pCI->descent);
110		    info->overallLeft = MIN(
111					    info->overallLeft,
112					    info->overallWidth + pCI->leftSideBearing);
113		    info->overallRight = MAX(
114					     info->overallRight,
115					     info->overallWidth + pCI->rightSideBearing);
116		    /*
117		     * yes, this order is correct; overallWidth IS incremented
118		     * last
119		     */
120		    info->overallWidth += pCI->characterWidth;
121		}
122	    }
123	}
124    } else {
125	info->overallAscent = 0;
126	info->overallDescent = 0;
127	info->overallWidth = 0;
128	info->overallLeft = 0;
129	info->overallRight = 0;
130    }
131}
132
133Bool
134QueryTextExtents(FontPtr pFont,
135		 unsigned long count,
136		 unsigned char *chars,
137		 ExtentInfoRec *info)
138{
139    xCharInfo     **charinfo;
140    unsigned long   n;
141    FontEncoding    encoding;
142    int             cm;
143    int             i;
144    unsigned long   t;
145    xCharInfo      *defaultChar = 0;
146    unsigned char   defc[2];
147    int             firstReal;
148
149    charinfo = malloc(count * sizeof(xCharInfo *));
150    if (!charinfo)
151	return FALSE;
152    encoding = TwoD16Bit;
153    if (pFont->info.lastRow == 0)
154	encoding = Linear16Bit;
155    (*pFont->get_metrics) (pFont, count, chars, encoding, &n, charinfo);
156
157    /* Do default character substitution as get_metrics doesn't */
158
159#define IsNonExistentChar(ci) (!(ci) || \
160			       ((ci)->ascent == 0 && \
161			       (ci)->descent == 0 && \
162			       (ci)->leftSideBearing == 0 && \
163			       (ci)->rightSideBearing == 0 && \
164			       (ci)->characterWidth == 0))
165
166    firstReal = n;
167    defc[0] = pFont->info.defaultCh >> 8;
168    defc[1] = pFont->info.defaultCh;
169    (*pFont->get_metrics) (pFont, 1, defc, encoding, &t, &defaultChar);
170    if ((IsNonExistentChar (defaultChar)))
171	defaultChar = 0;
172    for (i = 0; i < n; i++)
173    {
174	if ((IsNonExistentChar (charinfo[i])))
175	{
176	    if (!defaultChar)
177		continue;
178	    charinfo[i] = defaultChar;
179	}
180	if (firstReal == n)
181	    firstReal = i;
182    }
183    cm = pFont->info.constantMetrics;
184    pFont->info.constantMetrics = FALSE;
185    QueryGlyphExtents(pFont, (CharInfoPtr*) charinfo + firstReal,
186		      n - firstReal, info);
187    pFont->info.constantMetrics = cm;
188    free(charinfo);
189    return TRUE;
190}
191
192Bool
193ParseGlyphCachingMode(char *str)
194{
195    if (!strcmp(str, "none")) defaultGlyphCachingMode = CACHING_OFF;
196    else if (!strcmp(str, "all")) defaultGlyphCachingMode = CACHE_ALL_GLYPHS;
197    else if (!strcmp(str, "16")) defaultGlyphCachingMode = CACHE_16_BIT_GLYPHS;
198    else return FALSE;
199    return TRUE;
200}
201
202void
203InitGlyphCaching(void)
204{
205    /* Set glyphCachingMode to the mode the server hopes to
206       support.  DDX drivers that do not support the requested level
207       of glyph caching can call SetGlyphCachingMode to lower the
208       level of support.
209     */
210
211    glyphCachingMode = defaultGlyphCachingMode;
212}
213
214/* ddxen can call SetGlyphCachingMode to inform us of what level of glyph
215 * caching they can support.
216 */
217void
218SetGlyphCachingMode(int newmode)
219{
220    if ( (glyphCachingMode > newmode) && (newmode >= 0) )
221	glyphCachingMode = newmode;
222}
223
224#define range_alloc_granularity 16
225#define mincharp(p) ((p)->min_char_low + ((p)->min_char_high << 8))
226#define maxcharp(p) ((p)->max_char_low + ((p)->max_char_high << 8))
227
228/* add_range(): Add range to a list of ranges, with coalescence */
229int
230add_range(fsRange *newrange,
231	  int *nranges,
232	  fsRange **range,
233	  Bool charset_subset)
234{
235    int first, last, middle;
236    unsigned long keymin, keymax;
237    unsigned long ptrmin = 0, ptrmax = 0;
238    fsRange *ptr = NULL, *ptr1, *ptr2, *endptr;
239
240    /* There are two different ways to treat ranges:
241
242       1) Charset subsetting (support of the HP XLFD enhancements), in
243	  which a range of 0x1234,0x3456 means all numbers between
244	  0x1234 and 0x3456, and in which min and max might be swapped.
245
246       2) Row/column ranges, in which a range of 0x1234,0x3456 means the
247	  ranges 0x1234-0x1256, 0x1334-0x1356, ...  , 0x3434-0x3456.
248	  This is for support of glyph caching.
249
250       The choice of treatment is selected with the "charset_subset"
251       flag */
252
253    /* If newrange covers multiple rows; break up the rows */
254    if (!charset_subset && newrange->min_char_high != newrange->max_char_high)
255    {
256	int i, err = 0;
257	fsRange temprange;
258	for (i = newrange->min_char_high;
259	     i <= newrange->max_char_high;
260	     i++)
261	{
262	    temprange.min_char_low = newrange->min_char_low;
263	    temprange.max_char_low = newrange->max_char_low;
264	    temprange.min_char_high = temprange.max_char_high = i;
265	    err = add_range(&temprange, nranges, range, charset_subset);
266	    if (err != Successful) break;
267	}
268	return err;
269    }
270
271    keymin = mincharp(newrange);
272    keymax = maxcharp(newrange);
273
274    if (charset_subset && keymin > keymax)
275    {
276	unsigned long temp = keymin;
277	keymin = keymax;
278	keymax = temp;
279    }
280
281    /* add_range() maintains a sorted list; this makes possible coalescence
282       and binary searches */
283
284    /* Binary search for a range with which the new range can merge */
285
286    first = middle = 0;
287    last = *nranges - 1;
288    while (last >= first)
289    {
290	middle = (first + last) / 2;
291	ptr = (*range) + middle;
292	ptrmin = mincharp(ptr);
293	ptrmax = maxcharp(ptr);
294
295	if (ptrmin > 0 && keymax < ptrmin - 1) last = middle - 1;
296	else if (keymin > ptrmax + 1) first = middle + 1;
297	else if (!charset_subset)
298	{
299	    /* We might have a range with which to merge... IF the
300	       result doesn't cross rows */
301	    if (newrange->min_char_high != ptr->min_char_high)
302		last = first - 1;	/* Force adding a new range */
303	    break;
304	}
305	else break;	/* We have at least one range with which we can merge */
306    }
307
308    if (last < first)
309    {
310	/* Search failed; we need to add a new range to the list. */
311
312	/* Grow the list if necessary */
313	if (*nranges == 0 || *range == (fsRange *)0)
314	{
315	    *range = malloc(range_alloc_granularity * SIZEOF(fsRange));
316	    *nranges = 0;
317	}
318	else if (!(*nranges % range_alloc_granularity))
319	{
320	    *range = realloc(*range, (*nranges + range_alloc_granularity) *
321				      SIZEOF(fsRange));
322	}
323
324	/* If alloc failed, just return a null list */
325	if (*range == (fsRange *)0)
326	{
327	    *nranges = 0;
328	    return AllocError;
329	}
330
331	/* Should new entry go *at* or *after* ptr? */
332	ptr = (*range) + middle;
333	if (middle < *nranges && keymin > ptrmin) ptr++;	/* after */
334
335	/* Open up a space for our new range */
336	memmove((char *)(ptr + 1),
337		(char *)ptr,
338		(char *)(*range + *nranges) - (char *)ptr);
339
340	/* Insert the new range */
341	ptr->min_char_low = keymin & 0xff;
342	ptr->min_char_high = keymin >> 8;
343	ptr->max_char_low = keymax & 0xff;
344	ptr->max_char_high = keymax >> 8;
345
346	/* Update range count */
347	(*nranges)++;
348
349	/* Done */
350	return Successful;
351    }
352
353    /* Join our new range to that pointed to by "ptr" */
354    if (keymin < ptrmin)
355    {
356	ptr->min_char_low = keymin & 0xff;
357	ptr->min_char_high = keymin >> 8;
358    }
359    if (keymax > ptrmax)
360    {
361	ptr->max_char_low = keymax & 0xff;
362	ptr->max_char_high = keymax >> 8;
363    }
364
365    ptrmin = mincharp(ptr);
366    ptrmax = maxcharp(ptr);
367
368    endptr = *range + *nranges;
369
370    for (ptr1 = ptr; ptr1 >= *range; ptr1--)
371    {
372	if (ptrmin <= maxcharp(ptr1) + 1)
373	{
374	    if (!charset_subset && ptr->min_char_high != ptr1->min_char_high)
375		break;
376	    if (ptrmin >= mincharp(ptr1))
377		ptrmin = mincharp(ptr1);
378	}
379	else break;
380    }
381    for (ptr2 = ptr; ptr2 < endptr; ptr2++)
382    {
383	if ((ptr2->min_char_low == 0 && ptr2->min_char_high == 0) ||
384	    ptrmax >= mincharp(ptr2) - 1)
385	{
386	    if (!charset_subset && ptr->min_char_high != ptr2->min_char_high)
387		break;
388	    if (ptrmax <= maxcharp(ptr2))
389		ptrmax = maxcharp(ptr2);
390	}
391	else break;
392    }
393
394    /* We need to coalesce ranges between ptr1 and ptr2 exclusive */
395    ptr1++;
396    ptr2--;
397    if (ptr1 != ptr2)
398    {
399	memmove(ptr1, ptr2, (char *)endptr - (char *)ptr2);
400	*nranges -= (ptr2 - ptr1);
401    }
402
403    /* Write the new range into the range list */
404    ptr1->min_char_low = ptrmin & 0xff;
405    ptr1->min_char_high = ptrmin >> 8;
406    ptr1->max_char_low = ptrmax & 0xff;
407    ptr1->max_char_high = ptrmax >> 8;
408
409    return Successful;
410}
411