]> git.wh0rd.org - fontconfig.git/blame - src/fcmatch.c
Add ppc architecture
[fontconfig.git] / src / fcmatch.c
CommitLineData
24330d27 1/*
4bd4418a 2 * $RCSId: xc/lib/fontconfig/src/fcmatch.c,v 1.20 2002/08/31 22:17:32 keithp Exp $
24330d27 3 *
46b51147 4 * Copyright © 2000 Keith Packard
24330d27
KP
5 *
6 * Permission to use, copy, modify, distribute, and sell this software and its
7 * documentation for any purpose is hereby granted without fee, provided that
8 * the above copyright notice appear in all copies and that both that
9 * copyright notice and this permission notice appear in supporting
10 * documentation, and that the name of Keith Packard not be used in
11 * advertising or publicity pertaining to distribution of the software without
12 * specific, written prior permission. Keith Packard makes no
13 * representations about the suitability of this software for any purpose. It
14 * is provided "as is" without express or implied warranty.
15 *
16 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
17 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
18 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
19 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
20 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
21 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
22 * PERFORMANCE OF THIS SOFTWARE.
23 */
24
f045376c 25#include "fcint.h"
24330d27
KP
26#include <string.h>
27#include <ctype.h>
24330d27
KP
28#include <stdio.h>
29
30static double
9ab79bdf 31FcCompareNumber (FcValue *value1, FcValue *value2)
24330d27 32{
2d39321f 33 double v1, v2, v;
24330d27 34
4262e0b3 35 switch (value1->type) {
2d39321f 36 case FcTypeInteger:
4262e0b3 37 v1 = (double) value1->u.i;
2d39321f
KP
38 break;
39 case FcTypeDouble:
4262e0b3 40 v1 = value1->u.d;
2d39321f
KP
41 break;
42 default:
24330d27 43 return -1.0;
2d39321f 44 }
4262e0b3 45 switch (value2->type) {
2d39321f 46 case FcTypeInteger:
4262e0b3 47 v2 = (double) value2->u.i;
2d39321f
KP
48 break;
49 case FcTypeDouble:
4262e0b3 50 v2 = value2->u.d;
2d39321f
KP
51 break;
52 default:
53 return -1.0;
54 }
55 v = v2 - v1;
24330d27
KP
56 if (v < 0)
57 v = -v;
4f8b266f 58 return v;
24330d27
KP
59}
60
61static double
9ab79bdf 62FcCompareString (FcValue *v1, FcValue *v2)
24330d27 63{
1c9fdcca 64 return (double) FcStrCmpIgnoreCase (fc_value_string(v1), fc_value_string(v2)) != 0;
24330d27
KP
65}
66
82f4243f 67static double
9ab79bdf 68FcCompareFamily (FcValue *v1, FcValue *v2)
82f4243f 69{
4f8b266f
PL
70 /* rely on the guarantee in FcPatternAddWithBinding that
71 * families are always FcTypeString. */
4f8b266f
PL
72 const FcChar8* v1_string = fc_value_string(v1);
73 const FcChar8* v2_string = fc_value_string(v2);
74
75 if (FcToLower(*v1_string) != FcToLower(*v2_string))
76 return 1.0;
77
78 return (double) FcStrCmpIgnoreBlanksAndCase (v1_string, v2_string) != 0;
82f4243f
KP
79}
80
81static double
9ab79bdf 82FcCompareLang (FcValue *v1, FcValue *v2)
82f4243f
KP
83{
84 FcLangResult result;
4262e0b3 85 FcValue value1 = FcValueCanonicalize(v1), value2 = FcValueCanonicalize(v2);
82f4243f 86
d8d73958
KP
87 switch (value1.type) {
88 case FcTypeLangSet:
89 switch (value2.type) {
90 case FcTypeLangSet:
4262e0b3 91 result = FcLangSetCompare (value1.u.l, value2.u.l);
d8d73958
KP
92 break;
93 case FcTypeString:
4262e0b3
PL
94 result = FcLangSetHasLang (value1.u.l,
95 value2.u.s);
d8d73958
KP
96 break;
97 default:
98 return -1.0;
99 }
100 break;
101 case FcTypeString:
102 switch (value2.type) {
103 case FcTypeLangSet:
4262e0b3 104 result = FcLangSetHasLang (value2.u.l, value1.u.s);
d8d73958
KP
105 break;
106 case FcTypeString:
4262e0b3
PL
107 result = FcLangCompare (value1.u.s,
108 value2.u.s);
d8d73958
KP
109 break;
110 default:
111 return -1.0;
112 }
113 break;
114 default:
82f4243f 115 return -1.0;
d8d73958 116 }
82f4243f
KP
117 switch (result) {
118 case FcLangEqual:
119 return 0;
120 case FcLangDifferentCountry:
121 return 1;
122 case FcLangDifferentLang:
123 default:
124 return 2;
125 }
126}
127
24330d27 128static double
9ab79bdf 129FcCompareBool (FcValue *v1, FcValue *v2)
24330d27 130{
1c9fdcca 131 if (fc_storage_type(v2) != FcTypeBool || fc_storage_type(v1) != FcTypeBool)
24330d27 132 return -1.0;
1c9fdcca 133 return (double) v2->u.b != v1->u.b;
24330d27
KP
134}
135
136static double
9ab79bdf 137FcCompareCharSet (FcValue *v1, FcValue *v2)
24330d27 138{
1c9fdcca 139 return (double) FcCharSetSubtractCount (fc_value_charset(v1), fc_value_charset(v2));
24330d27
KP
140}
141
142static double
9ab79bdf 143FcCompareSize (FcValue *value1, FcValue *value2)
24330d27
KP
144{
145 double v1, v2, v;
146
4262e0b3 147 switch (value1->type) {
24330d27 148 case FcTypeInteger:
4262e0b3 149 v1 = value1->u.i;
24330d27
KP
150 break;
151 case FcTypeDouble:
4262e0b3 152 v1 = value1->u.d;
24330d27
KP
153 break;
154 default:
155 return -1;
156 }
4262e0b3 157 switch (value2->type) {
24330d27 158 case FcTypeInteger:
4262e0b3 159 v2 = value2->u.i;
24330d27
KP
160 break;
161 case FcTypeDouble:
4262e0b3 162 v2 = value2->u.d;
24330d27
KP
163 break;
164 default:
165 return -1;
166 }
167 if (v2 == 0)
168 return 0;
169 v = v2 - v1;
170 if (v < 0)
171 v = -v;
172 return v;
173}
174
4c003605 175typedef struct _FcMatcher {
67accef4 176 const char *object;
cbe1df81 177 FcObjectPtr objectPtr;
9ab79bdf 178 double (*compare) (FcValue *value1, FcValue *value2);
4c003605
KP
179 int strong, weak;
180} FcMatcher;
181
24330d27
KP
182/*
183 * Order is significant, it defines the precedence of
184 * each value, earlier values are more significant than
185 * later values
186 */
187static FcMatcher _FcMatchers [] = {
cbe1df81 188 { FC_FOUNDRY, 0, FcCompareString, 0, 0 },
4c003605 189#define MATCH_FOUNDRY 0
5cf8c536 190#define MATCH_FOUNDRY_INDEX 0
bc9469ba 191
cbe1df81 192 { FC_CHARSET, 0, FcCompareCharSet, 1, 1 },
4c003605 193#define MATCH_CHARSET 1
5cf8c536 194#define MATCH_CHARSET_INDEX 1
bc9469ba 195
cbe1df81 196 { FC_FAMILY, 0, FcCompareFamily, 2, 4 },
4c003605 197#define MATCH_FAMILY 2
5cf8c536
KP
198#define MATCH_FAMILY_STRONG_INDEX 2
199#define MATCH_FAMILY_WEAK_INDEX 4
bc9469ba 200
cbe1df81 201 { FC_LANG, 0, FcCompareLang, 3, 3 },
4c003605 202#define MATCH_LANG 3
5cf8c536 203#define MATCH_LANG_INDEX 3
bc9469ba 204
cbe1df81 205 { FC_SPACING, 0, FcCompareNumber, 5, 5 },
4c003605 206#define MATCH_SPACING 4
5cf8c536 207#define MATCH_SPACING_INDEX 5
bc9469ba 208
cbe1df81 209 { FC_PIXEL_SIZE, 0, FcCompareSize, 6, 6 },
4c003605 210#define MATCH_PIXEL_SIZE 5
5cf8c536 211#define MATCH_PIXEL_SIZE_INDEX 6
bc9469ba 212
cbe1df81 213 { FC_STYLE, 0, FcCompareString, 7, 7 },
4c003605 214#define MATCH_STYLE 6
5cf8c536 215#define MATCH_STYLE_INDEX 7
bc9469ba 216
cbe1df81 217 { FC_SLANT, 0, FcCompareNumber, 8, 8 },
4c003605 218#define MATCH_SLANT 7
5cf8c536 219#define MATCH_SLANT_INDEX 8
bc9469ba 220
cbe1df81 221 { FC_WEIGHT, 0, FcCompareNumber, 9, 9 },
4c003605 222#define MATCH_WEIGHT 8
5cf8c536 223#define MATCH_WEIGHT_INDEX 9
f534109f 224
cbe1df81 225 { FC_WIDTH, 0, FcCompareNumber, 10, 10 },
81fa16c3 226#define MATCH_WIDTH 9
5cf8c536 227#define MATCH_WIDTH_INDEX 10
bc9469ba 228
cbe1df81 229 { FC_ANTIALIAS, 0, FcCompareBool, 11, 11 },
81fa16c3 230#define MATCH_ANTIALIAS 10
5cf8c536 231#define MATCH_ANTIALIAS_INDEX 11
bc9469ba 232
cbe1df81 233 { FC_RASTERIZER, 0, FcCompareString, 12, 12 },
81fa16c3 234#define MATCH_RASTERIZER 11
5cf8c536
KP
235#define MATCH_RASTERIZER_INDEX 12
236
cbe1df81 237 { FC_OUTLINE, 0, FcCompareBool, 13, 13 },
81fa16c3 238#define MATCH_OUTLINE 12
5cf8c536 239#define MATCH_OUTLINE_INDEX 13
a342e87d 240
cbe1df81 241 { FC_FONTVERSION, 0, FcCompareNumber, 14, 14 },
81fa16c3 242#define MATCH_FONTVERSION 13
5cf8c536 243#define MATCH_FONTVERSION_INDEX 14
24330d27
KP
244};
245
81fa16c3 246#define NUM_MATCH_VALUES 15
24330d27 247
cbe1df81
PL
248static FcBool matchObjectPtrsInit = FcFalse;
249
250static void
251FcMatchObjectPtrsInit (void)
252{
253 _FcMatchers[MATCH_FOUNDRY].objectPtr = FcObjectToPtr(FC_FOUNDRY);
254 _FcMatchers[MATCH_CHARSET].objectPtr = FcObjectToPtr(FC_CHARSET);
255 _FcMatchers[MATCH_FAMILY].objectPtr = FcObjectToPtr(FC_FAMILY);
256 _FcMatchers[MATCH_LANG].objectPtr = FcObjectToPtr(FC_LANG);
257 _FcMatchers[MATCH_SPACING].objectPtr = FcObjectToPtr(FC_SPACING);
258 _FcMatchers[MATCH_PIXEL_SIZE].objectPtr = FcObjectToPtr(FC_PIXEL_SIZE);
259 _FcMatchers[MATCH_STYLE].objectPtr = FcObjectToPtr(FC_STYLE);
260 _FcMatchers[MATCH_SLANT].objectPtr = FcObjectToPtr(FC_SLANT);
261 _FcMatchers[MATCH_WEIGHT].objectPtr = FcObjectToPtr(FC_WEIGHT);
262 _FcMatchers[MATCH_WIDTH].objectPtr = FcObjectToPtr(FC_WIDTH);
263 _FcMatchers[MATCH_ANTIALIAS].objectPtr = FcObjectToPtr(FC_ANTIALIAS);
264 _FcMatchers[MATCH_RASTERIZER].objectPtr = FcObjectToPtr(FC_RASTERIZER);
265 _FcMatchers[MATCH_OUTLINE].objectPtr = FcObjectToPtr(FC_OUTLINE);
266 _FcMatchers[MATCH_FONTVERSION].objectPtr = FcObjectToPtr(FC_FONTVERSION);
267 matchObjectPtrsInit = FcTrue;
268}
269
aa472e5f
PL
270static FcMatcher*
271FcObjectPtrToMatcher (FcObjectPtr o)
24330d27 272{
aa472e5f
PL
273 int i;
274 const char *object = FcObjectPtrU(o);
d854eaf8 275
bc9469ba 276 i = -1;
d854eaf8 277 switch (object[0]) {
bc9469ba 278 case 'f':
d854eaf8 279 switch (object[1]) {
bc9469ba 280 case 'o':
d854eaf8 281 switch (object[2]) {
a342e87d
KP
282 case 'u':
283 i = MATCH_FOUNDRY; break;
284 case 'n':
285 i = MATCH_FONTVERSION; break;
286 }
287 break;
bc9469ba
KP
288 case 'a':
289 i = MATCH_FAMILY; break;
290 }
291 break;
292 case 'c':
293 i = MATCH_CHARSET; break;
294 case 'a':
295 i = MATCH_ANTIALIAS; break;
296 case 'l':
297 i = MATCH_LANG; break;
298 case 's':
d854eaf8 299 switch (object[1]) {
bc9469ba
KP
300 case 'p':
301 i = MATCH_SPACING; break;
302 case 't':
303 i = MATCH_STYLE; break;
304 case 'l':
305 i = MATCH_SLANT; break;
306 }
307 break;
308 case 'p':
309 i = MATCH_PIXEL_SIZE; break;
310 case 'w':
d854eaf8 311 switch (object[1]) {
81fa16c3
KP
312 case 'i':
313 i = MATCH_WIDTH; break;
314 case 'e':
315 i = MATCH_WEIGHT; break;
316 }
317 break;
bc9469ba
KP
318 case 'r':
319 i = MATCH_RASTERIZER; break;
320 case 'o':
321 i = MATCH_OUTLINE; break;
322 }
cbe1df81 323
aa472e5f
PL
324 if (i < 0)
325 return 0;
326
cbe1df81
PL
327 if (!matchObjectPtrsInit)
328 FcMatchObjectPtrsInit();
cbe1df81 329
aa472e5f
PL
330 if (o != _FcMatchers[i].objectPtr)
331 return 0;
332
333 return _FcMatchers+i;
334}
335
336static FcBool
337FcCompareValueList (FcObjectPtr o,
338 FcValueListPtr v1orig, /* pattern */
339 FcValueListPtr v2orig, /* target */
340 FcValue *bestValue,
341 double *value,
342 FcResult *result)
343{
344 FcValueListPtr v1, v2;
345 FcValueList *v1_ptrU, *v2_ptrU;
346 double v, best, bestStrong, bestWeak;
347 int j;
348 const char *object = FcObjectPtrU(o);
349 FcMatcher *match = FcObjectPtrToMatcher(o);
350
351 if (!match)
bc9469ba
KP
352 {
353 if (bestValue)
4262e0b3 354 *bestValue = FcValueCanonicalize(&FcValueListPtrU(v2orig)->value);
bc9469ba
KP
355 return FcTrue;
356 }
aa472e5f 357
24330d27 358 best = 1e99;
4c003605
KP
359 bestStrong = 1e99;
360 bestWeak = 1e99;
24330d27 361 j = 0;
adac22f2 362 for (v1 = v1orig, v1_ptrU = FcValueListPtrU(v1); v1_ptrU;
200a44fe 363 v1 = v1_ptrU->next, v1_ptrU = FcValueListPtrU(v1))
24330d27 364 {
200a44fe
PL
365 for (v2 = v2orig, v2_ptrU = FcValueListPtrU(v2); v2_ptrU;
366 v2 = v2_ptrU->next, v2_ptrU = FcValueListPtrU(v2))
24330d27 367 {
aa472e5f 368 v = (match->compare) (&v1_ptrU->value, &v2_ptrU->value);
24330d27
KP
369 if (v < 0)
370 {
371 *result = FcResultTypeMismatch;
372 return FcFalse;
373 }
24330d27
KP
374 v = v * 100 + j;
375 if (v < best)
376 {
377 if (bestValue)
adac22f2 378 *bestValue = FcValueCanonicalize(&v2_ptrU->value);
24330d27
KP
379 best = v;
380 }
adac22f2 381 if (v1_ptrU->binding == FcValueBindingStrong)
4c003605
KP
382 {
383 if (v < bestStrong)
384 bestStrong = v;
385 }
386 else
387 {
388 if (v < bestWeak)
389 bestWeak = v;
390 }
24330d27
KP
391 }
392 j++;
393 }
394 if (FcDebug () & FC_DBG_MATCHV)
395 {
396 printf (" %s: %g ", object, best);
397 FcValueListPrint (v1orig);
398 printf (", ");
399 FcValueListPrint (v2orig);
400 printf ("\n");
401 }
d0f07b8d 402 if (value)
4c003605 403 {
aa472e5f
PL
404 int weak = match->weak;
405 int strong = match->strong;
4c003605
KP
406 if (weak == strong)
407 value[strong] += best;
408 else
409 {
410 value[weak] += bestWeak;
411 value[strong] += bestStrong;
412 }
413 }
24330d27
KP
414 return FcTrue;
415}
416
417/*
418 * Return a value indicating the distance between the two lists of
419 * values
420 */
421
422static FcBool
423FcCompare (FcPattern *pat,
424 FcPattern *fnt,
425 double *value,
426 FcResult *result)
427{
428 int i, i1, i2;
429
4c003605 430 for (i = 0; i < NUM_MATCH_VALUES; i++)
24330d27
KP
431 value[i] = 0.0;
432
bc9469ba
KP
433 i1 = 0;
434 i2 = 0;
435 while (i1 < pat->num && i2 < fnt->num)
24330d27 436 {
9ab79bdf
PL
437 FcPatternElt *elt_i1 = FcPatternEltU(pat->elts)+i1;
438 FcPatternElt *elt_i2 = FcPatternEltU(fnt->elts)+i2;
439
440 i = FcObjectPtrCompare(elt_i1->object, elt_i2->object);
bc9469ba
KP
441 if (i > 0)
442 i2++;
443 else if (i < 0)
444 i1++;
445 else
24330d27 446 {
d854eaf8 447 if (!FcCompareValueList (elt_i1->object,
9ab79bdf
PL
448 elt_i1->values, elt_i2->values,
449 0, value, result))
bc9469ba
KP
450 return FcFalse;
451 i1++;
452 i2++;
24330d27 453 }
bc9469ba
KP
454 }
455 return FcTrue;
24330d27
KP
456}
457
216fac98
KP
458FcPattern *
459FcFontRenderPrepare (FcConfig *config,
460 FcPattern *pat,
461 FcPattern *font)
462{
463 FcPattern *new;
464 int i;
465 FcPatternElt *fe, *pe;
466 FcValue v;
216fac98
KP
467 FcResult result;
468
469 new = FcPatternCreate ();
470 if (!new)
471 return 0;
472 for (i = 0; i < font->num; i++)
473 {
cd2ec1a9
PL
474 fe = FcPatternEltU(font->elts)+i;
475 pe = FcPatternFindElt (pat, FcObjectPtrU(fe->object));
216fac98
KP
476 if (pe)
477 {
d854eaf8 478 if (!FcCompareValueList (pe->object, pe->values,
938bc633 479 fe->values, &v, 0, &result))
216fac98
KP
480 {
481 FcPatternDestroy (new);
482 return 0;
483 }
484 }
485 else
4262e0b3 486 v = FcValueCanonicalize(&FcValueListPtrU(fe->values)->value);
cd2ec1a9 487 FcPatternAdd (new, FcObjectPtrU(fe->object), v, FcFalse);
216fac98
KP
488 }
489 for (i = 0; i < pat->num; i++)
490 {
cd2ec1a9
PL
491 pe = FcPatternEltU(pat->elts)+i;
492 fe = FcPatternFindElt (font, FcObjectPtrU(pe->object));
216fac98 493 if (!fe)
cd2ec1a9 494 FcPatternAdd (new, FcObjectPtrU(pe->object),
4262e0b3 495 FcValueCanonicalize(&FcValueListPtrU(pe->values)->value), FcTrue);
216fac98 496 }
793154ed 497
fa244f3d 498 FcConfigSubstituteWithPat (config, new, pat, FcMatchFont);
216fac98
KP
499 return new;
500}
501
24330d27 502FcPattern *
80c053b7
KP
503FcFontSetMatch (FcConfig *config,
504 FcFontSet **sets,
505 int nsets,
506 FcPattern *p,
507 FcResult *result)
24330d27 508{
aa472e5f
PL
509 double score;
510 double bestscore;
24330d27
KP
511 int f;
512 FcFontSet *s;
513 FcPattern *best;
aa472e5f 514 int scoring_index;
5576a587 515 int *sets_offset;
216fac98 516 int set;
5576a587
PL
517 int nfonts;
518 int fonts_left;
519 FcMatcher *matcher;
520 FcMatcher *strong_matchers[NUM_MATCH_VALUES];
521 FcMatcher *weak_matchers[NUM_MATCH_VALUES];
522 FcPatternElt *pat_elts[NUM_MATCH_VALUES];
523 int pat_elt;
9e07e0a7 524 int *match_blocked;
5576a587
PL
525 int block_start;
526
527 if (!nsets || !sets || !p)
528 {
529 *result = FcResultNoMatch;
530 return 0;
531 }
24330d27 532
24330d27
KP
533 if (FcDebug () & FC_DBG_MATCH)
534 {
535 printf ("Match ");
536 FcPatternPrint (p);
537 }
538 if (!config)
539 {
540 config = FcConfigGetCurrent ();
541 if (!config)
ec0c740e
KP
542 {
543 *result = FcResultOutOfMemory;
24330d27 544 return 0;
ec0c740e 545 }
24330d27 546 }
5576a587
PL
547
548 sets_offset = (int *)calloc(nsets, sizeof (int));
549
550 nfonts = 0;
551 for (set = 0; set < nsets; ++set)
552 {
553 sets_offset[set] = nfonts;
554 if (sets[set])
555 nfonts += sets[set]->nfont;
556 }
557
558 fonts_left = nfonts;
559
9e07e0a7 560 match_blocked = (int*)calloc(nfonts, sizeof(int));
5576a587
PL
561
562 /* Find out all necessary matchers first, so we don't need to find them
563 * in every loop.
564 */
565
566 memset(strong_matchers, 0, sizeof (FcMatcher*) * NUM_MATCH_VALUES);
567 memset(weak_matchers, 0, sizeof (FcMatcher*) * NUM_MATCH_VALUES);
568 memset(pat_elts, 0, sizeof (FcPatternElt*) * NUM_MATCH_VALUES);
569
570 for (pat_elt = 0; pat_elt < p->num; ++pat_elt)
571 {
572 matcher = FcObjectPtrToMatcher
573 ((FcPatternEltU(p->elts)+pat_elt)->object);
574 if (matcher)
575 {
576 strong_matchers[matcher->strong] = matcher;
577 weak_matchers[matcher->weak] = matcher;
578 pat_elts [matcher->strong] = pat_elts [matcher->weak] =
579 (FcPatternEltU(p->elts)+pat_elt);
580 }
581 }
582
583 /* The old algorithm checked if each font beat 'best',
584 * scanning all of the value lists for all of the pattern elts. */
585 /* This algorithm checks each font on a element-by-element basis
586 * and blocks fonts that have already lost on some element from
587 * further consideration from being best. Basically, we've
588 * swapped the order of loops and short-circuited fonts that
589 * are out of contention right away.
590 * This saves a lot of time! */
591 best = 0;
592 block_start = 0;
593 for (scoring_index = 0; scoring_index < NUM_MATCH_VALUES; ++scoring_index)
24330d27 594 {
5576a587
PL
595 FcValueListPtr v1;
596 FcValueList *v1_ptrU;
597 int v1_offset = 0;
1ed98a0c 598
5576a587 599 if (!strong_matchers [scoring_index] && !weak_matchers [scoring_index])
24330d27 600 continue;
aa472e5f 601
5576a587
PL
602 for (v1 = pat_elts[scoring_index]->values, v1_ptrU = FcValueListPtrU(v1);
603 v1_ptrU;
604 v1 = v1_ptrU->next, v1_ptrU = FcValueListPtrU(v1), ++v1_offset)
605 {
606 matcher = (v1_ptrU->binding == FcValueBindingWeak) ?
607 weak_matchers[scoring_index] : strong_matchers[scoring_index];
608
609 if (!matcher) continue;
610
611 bestscore = 1e99;
612
613 if (FcDebug () & FC_DBG_MATCHV)
614 {
615 printf("Scoring Index %d, Value %d: %d(%d) fonts left\n",
616 scoring_index, v1_offset, fonts_left, nfonts);
24330d27 617 }
aa472e5f 618
5576a587
PL
619 for (set = 0; set < nsets; ++set)
620 {
621 s = sets[set];
622 if (!s) continue;
1ed98a0c 623
5576a587
PL
624 /* All fonts before block_start should have been knocked out. */
625 for (f = (block_start > sets_offset[set]) ? (block_start - sets_offset[set]) : 0;
626 f < s->nfont; ++f)
627 {
628 int cand_elt;
629 FcPatternElt *cand_elts;
aa472e5f 630
9e07e0a7 631 if (match_blocked[f + sets_offset[set]] == 1)
5576a587 632 continue;
aa472e5f 633
5576a587 634 score = 1e99;
aa472e5f 635 cand_elts = FcPatternEltU(s->fonts[f]->elts);
5576a587 636
aa472e5f
PL
637 /* Look for the appropriate element in this candidate
638 * pattern 'f' and evaluate its score wrt 'p'. */
5576a587 639 for (cand_elt = 0; cand_elt < s->fonts[f]->num; ++cand_elt)
aa472e5f 640 {
5576a587
PL
641 if (cand_elts[cand_elt].object == pat_elts[scoring_index]->object)
642 {
aa472e5f 643 FcValueListPtr v2;
5576a587 644 FcValueList *v2_ptrU;
aa472e5f 645
5576a587
PL
646 for (v2 = cand_elts[cand_elt].values, v2_ptrU = FcValueListPtrU(v2);
647 v2_ptrU;
648 v2 = v2_ptrU->next, v2_ptrU = FcValueListPtrU(v2))
aa472e5f 649 {
5576a587 650 double v = (matcher->compare)(&v1_ptrU->value, &v2_ptrU->value);
aa472e5f
PL
651
652 if (v < 0)
653 {
654 *result = FcResultTypeMismatch;
5576a587
PL
655 free (match_blocked);
656 free (sets_offset);
aa472e5f
PL
657 return 0;
658 }
5576a587 659
aa472e5f
PL
660 /* I'm actually kind of surprised that
661 * this isn't v + 100 * v1_offset. -PL */
662 v = v * 100 + v1_offset;
5576a587
PL
663 /* The old patch said score += v, which
664 * seems to be wrong when you have
665 * multiple matchers. This takes the
666 * best score it can find for that font. */
667 if (v < score)
668 score = v;
aa472e5f 669 }
aa472e5f
PL
670 }
671 }
672
f11a1841
PL
673 /* We had no matching, just try the next one */
674 if (score == 1e99)
9e07e0a7
PL
675 {
676 match_blocked[f + sets_offset[set]] = 2;
f11a1841 677 continue;
9e07e0a7
PL
678 }
679 match_blocked[f + sets_offset[set]] = 0;
aa472e5f
PL
680 /* If there's a previous champion, and current score
681 * beats previous best score, on this element, then
682 * knock out the previous champion and anything
683 * else that we would have visited previous to f;
684 * clearly anything previous to f would have been
685 * less than f on this score. */
686 if (!best || score < bestscore)
687 {
688 if (best)
689 {
690 int b;
5576a587
PL
691 for (b = block_start; b < f + sets_offset[set]; ++b)
692 if (!match_blocked[b])
693 {
9e07e0a7 694 match_blocked[b] = 1;
5576a587
PL
695 --fonts_left;
696 }
aa472e5f
PL
697 }
698
699 bestscore = score;
700 best = s->fonts[f];
9e07e0a7
PL
701 /* This kills too many fonts, unfortunately. */
702 /* block_start = f + sets_offset[set]; */
aa472e5f
PL
703 }
704
705 /* If f loses, then it's out too. */
706 if (best && score > bestscore)
5576a587 707 {
9e07e0a7 708 match_blocked[f + sets_offset[set]] = 1;
5576a587
PL
709 --fonts_left;
710 }
711
712 /* If there is only 1 font left and the best is set,
713 * then just return this font
714 */
715 if (fonts_left == 1 && best)
716 goto end;
aa472e5f
PL
717
718 /* Otherwise, f is equal to best on this element.
719 * Carry on to next pattern element. */
24330d27 720 }
5576a587
PL
721 }
722 if ((FcDebug () & FC_DBG_MATCHV) && best)
723 {
724 printf ("Best match (scoring index %d) candidate %d ", scoring_index, block_start);
725 FcPatternPrint (best);
726 }
727 }
24330d27 728 }
5576a587
PL
729
730end:
731 free (match_blocked);
732 free (sets_offset);
733
1ed98a0c
PL
734 if ((FcDebug () & FC_DBG_MATCH) && best)
735 {
5576a587 736 printf ("Best match (scoring index %d) %d ", scoring_index, block_start);
1ed98a0c
PL
737 FcPatternPrint (best);
738 }
24330d27
KP
739 if (!best)
740 {
741 *result = FcResultNoMatch;
742 return 0;
743 }
216fac98 744 return FcFontRenderPrepare (config, p, best);
24330d27 745}
80c053b7
KP
746
747FcPattern *
748FcFontMatch (FcConfig *config,
749 FcPattern *p,
750 FcResult *result)
751{
752 FcFontSet *sets[2];
753 int nsets;
754
755 if (!config)
756 {
757 config = FcConfigGetCurrent ();
758 if (!config)
759 return 0;
760 }
761 nsets = 0;
762 if (config->fonts[FcSetSystem])
763 sets[nsets++] = config->fonts[FcSetSystem];
764 if (config->fonts[FcSetApplication])
765 sets[nsets++] = config->fonts[FcSetApplication];
766 return FcFontSetMatch (config, sets, nsets, p, result);
767}
216fac98 768
216fac98 769typedef struct _FcSortNode {
216fac98 770 FcPattern *pattern;
4c003605 771 double score[NUM_MATCH_VALUES];
216fac98
KP
772} FcSortNode;
773
0ab36ca8
KP
774static int
775FcSortCompare (const void *aa, const void *ab)
216fac98 776{
0ab36ca8
KP
777 FcSortNode *a = *(FcSortNode **) aa;
778 FcSortNode *b = *(FcSortNode **) ab;
bc9469ba
KP
779 double *as = &a->score[0];
780 double *bs = &b->score[0];
88c747e2 781 double ad = 0, bd = 0;
0ab36ca8 782 int i;
216fac98 783
4c003605 784 i = NUM_MATCH_VALUES;
bc9469ba
KP
785 while (i-- && (ad = *as++) == (bd = *bs++))
786 ;
787 return ad < bd ? -1 : ad > bd ? 1 : 0;
216fac98
KP
788}
789
790static FcBool
2f02e383 791FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs, FcCharSet **cs, FcBool trim, FcBool build_cs)
216fac98
KP
792{
793 FcCharSet *ncs;
0ab36ca8
KP
794 FcSortNode *node;
795
796 while (nnode--)
216fac98 797 {
0ab36ca8
KP
798 node = *n++;
799 if (FcPatternGetCharSet (node->pattern, FC_CHARSET, 0, &ncs) ==
800 FcResultMatch)
216fac98 801 {
1412a699
KP
802 /*
803 * If this font isn't a subset of the previous fonts,
804 * add it to the list
805 */
806 if (!trim || !*cs || !FcCharSetIsSubset (ncs, *cs))
216fac98 807 {
55e145b0 808 if (trim || build_cs)
2f02e383
PL
809 {
810 if (*cs)
811 {
812 ncs = FcCharSetUnion (ncs, *cs);
813 if (!ncs)
814 return FcFalse;
815 FcCharSetDestroy (*cs);
816 }
817 else
818 ncs = FcCharSetCopy (ncs);
819 *cs = ncs;
820 }
821
6f6563ed 822 FcPatternReference (node->pattern);
82f4243f
KP
823 if (FcDebug () & FC_DBG_MATCH)
824 {
825 printf ("Add ");
826 FcPatternPrint (node->pattern);
827 }
0ab36ca8 828 if (!FcFontSetAdd (fs, node->pattern))
6f6563ed
KP
829 {
830 FcPatternDestroy (node->pattern);
216fac98 831 return FcFalse;
6f6563ed 832 }
216fac98 833 }
216fac98
KP
834 }
835 }
216fac98
KP
836 return FcTrue;
837}
838
1412a699
KP
839void
840FcFontSetSortDestroy (FcFontSet *fs)
841{
1412a699
KP
842 FcFontSetDestroy (fs);
843}
844
216fac98
KP
845FcFontSet *
846FcFontSetSort (FcConfig *config,
847 FcFontSet **sets,
848 int nsets,
849 FcPattern *p,
850 FcBool trim,
851 FcCharSet **csp,
852 FcResult *result)
853{
854 FcFontSet *ret;
855 FcFontSet *s;
856 FcSortNode *nodes;
0ab36ca8 857 FcSortNode **nodeps, **nodep;
216fac98 858 int nnodes;
216fac98
KP
859 FcSortNode *new;
860 FcCharSet *cs;
861 int set;
862 int f;
863 int i;
5cf8c536
KP
864 int nPatternLang;
865 FcBool *patternLangSat;
866 FcValue patternLang;
216fac98 867
82f4243f
KP
868 if (FcDebug () & FC_DBG_MATCH)
869 {
870 printf ("Sort ");
871 FcPatternPrint (p);
872 }
216fac98
KP
873 nnodes = 0;
874 for (set = 0; set < nsets; set++)
875 {
876 s = sets[set];
877 if (!s)
878 continue;
879 nnodes += s->nfont;
880 }
881 if (!nnodes)
882 goto bail0;
5cf8c536
KP
883
884 for (nPatternLang = 0;
885 FcPatternGet (p, FC_LANG, nPatternLang, &patternLang) == FcResultMatch;
886 nPatternLang++)
887 ;
888
9dac3c59 889 /* freed below */
5cf8c536
KP
890 nodes = malloc (nnodes * sizeof (FcSortNode) +
891 nnodes * sizeof (FcSortNode *) +
892 nPatternLang * sizeof (FcBool));
216fac98
KP
893 if (!nodes)
894 goto bail0;
1412a699 895 nodeps = (FcSortNode **) (nodes + nnodes);
5cf8c536 896 patternLangSat = (FcBool *) (nodeps + nnodes);
216fac98 897
216fac98 898 new = nodes;
0ab36ca8 899 nodep = nodeps;
216fac98
KP
900 for (set = 0; set < nsets; set++)
901 {
902 s = sets[set];
903 if (!s)
904 continue;
905 for (f = 0; f < s->nfont; f++)
906 {
907 if (FcDebug () & FC_DBG_MATCHV)
908 {
909 printf ("Font %d ", f);
910 FcPatternPrint (s->fonts[f]);
911 }
912 new->pattern = s->fonts[f];
913 if (!FcCompare (p, new->pattern, new->score, result))
914 goto bail1;
915 if (FcDebug () & FC_DBG_MATCHV)
916 {
917 printf ("Score");
4c003605 918 for (i = 0; i < NUM_MATCH_VALUES; i++)
216fac98
KP
919 {
920 printf (" %g", new->score[i]);
921 }
922 printf ("\n");
923 }
0ab36ca8 924 *nodep = new;
216fac98 925 new++;
0ab36ca8 926 nodep++;
216fac98
KP
927 }
928 }
929
0ab36ca8
KP
930 nnodes = new - nodes;
931
1412a699 932 qsort (nodeps, nnodes, sizeof (FcSortNode *),
0ab36ca8 933 FcSortCompare);
5cf8c536
KP
934
935 for (i = 0; i < nPatternLang; i++)
936 patternLangSat[i] = FcFalse;
937
938 for (f = 0; f < nnodes; f++)
939 {
940 FcBool satisfies = FcFalse;
941 /*
942 * If this node matches any language, go check
943 * which ones and satisfy those entries
944 */
945 if (nodeps[f]->score[MATCH_LANG_INDEX] < nPatternLang)
946 {
947 for (i = 0; i < nPatternLang; i++)
948 {
949 FcValue nodeLang;
950
951 if (!patternLangSat[i] &&
952 FcPatternGet (p, FC_LANG, i, &patternLang) == FcResultMatch &&
953 FcPatternGet (nodeps[f]->pattern, FC_LANG, 0, &nodeLang) == FcResultMatch)
954 {
9ab79bdf 955 double compare = FcCompareLang (&patternLang, &nodeLang);
5cf8c536
KP
956 if (compare >= 0 && compare < 2)
957 {
958 if (FcDebug () & FC_DBG_MATCHV)
959 {
960 FcChar8 *family;
961 FcChar8 *style;
962
963 if (FcPatternGetString (nodeps[f]->pattern, FC_FAMILY, 0, &family) == FcResultMatch &&
964 FcPatternGetString (nodeps[f]->pattern, FC_STYLE, 0, &style) == FcResultMatch)
965 printf ("Font %s:%s matches language %d\n", family, style, i);
966 }
967 patternLangSat[i] = FcTrue;
968 satisfies = FcTrue;
969 break;
970 }
971 }
972 }
973 }
974 if (!satisfies)
975 nodeps[f]->score[MATCH_LANG_INDEX] = 1000.0;
976 }
977
978 /*
979 * Re-sort once the language issues have been settled
980 */
981 qsort (nodeps, nnodes, sizeof (FcSortNode *),
982 FcSortCompare);
0ab36ca8 983
216fac98
KP
984 ret = FcFontSetCreate ();
985 if (!ret)
986 goto bail1;
987
988 cs = 0;
989
2f02e383 990 if (!FcSortWalk (nodeps, nnodes, ret, &cs, trim, (csp!=0)))
216fac98
KP
991 goto bail2;
992
d0f07b8d
KP
993 if (csp)
994 *csp = cs;
995 else
2f02e383
PL
996 {
997 if (cs)
998 FcCharSetDestroy (cs);
999 }
216fac98 1000
1412a699
KP
1001 free (nodes);
1002
216fac98
KP
1003 return ret;
1004
1005bail2:
1006 if (cs)
1007 FcCharSetDestroy (cs);
1008 FcFontSetDestroy (ret);
1009bail1:
1010 free (nodes);
1011bail0:
1012 return 0;
1013}
20ac65ab
KP
1014
1015FcFontSet *
1016FcFontSort (FcConfig *config,
1017 FcPattern *p,
1018 FcBool trim,
1019 FcCharSet **csp,
1020 FcResult *result)
1021{
1022 FcFontSet *sets[2];
1023 int nsets;
1024
1025 if (!config)
1026 {
1027 config = FcConfigGetCurrent ();
1028 if (!config)
1029 return 0;
1030 }
1031 nsets = 0;
1032 if (config->fonts[FcSetSystem])
1033 sets[nsets++] = config->fonts[FcSetSystem];
1034 if (config->fonts[FcSetApplication])
1035 sets[nsets++] = config->fonts[FcSetApplication];
1036 return FcFontSetSort (config, sets, nsets, p, trim, csp, result);
1037}