?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
gdi32/tests: Regenerate ttf files with the official fontforge version.
[wine.git] / dlls / gdi32 / bidi.c
blob18971026395523e102ebd23e5b2a34408fb82026
1 /*
2 * GDI BiDirectional handling
3 *
4 * Copyright 2003 Shachar Shemesh
5 * Copyright 2007 Maarten Lankhorst
6 * Copyright 2010 CodeWeavers, Aric Stewart
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
21 *
22 * Code derived from the modified reference implementation
23 * that was found in revision 17 of http://unicode.org/reports/tr9/
24 * "Unicode Standard Annex #9: THE BIDIRECTIONAL ALGORITHM"
25 *
26 * -- Copyright (C) 1999-2005, ASMUS, Inc.
27 *
28 * Permission is hereby granted, free of charge, to any person obtaining a
29 * copy of the Unicode data files and any associated documentation (the
30 * "Data Files") or Unicode software and any associated documentation (the
31 * "Software") to deal in the Data Files or Software without restriction,
32 * including without limitation the rights to use, copy, modify, merge,
33 * publish, distribute, and/or sell copies of the Data Files or Software,
34 * and to permit persons to whom the Data Files or Software are furnished
35 * to do so, provided that (a) the above copyright notice(s) and this
36 * permission notice appear with all copies of the Data Files or Software,
37 * (b) both the above copyright notice(s) and this permission notice appear
38 * in associated documentation, and (c) there is clear notice in each
39 * modified Data File or in the Software as well as in the documentation
40 * associated with the Data File(s) or Software that the data or software
41 * has been modified.
42 */
43
44 #include <stdarg.h>
45 #include "windef.h"
46 #include "winbase.h"
47 #include "wingdi.h"
48 #include "winnls.h"
49 #include "usp10.h"
50 #include "wine/debug.h"
51 #include "gdi_private.h"
52
53 WINE_DEFAULT_DEBUG_CHANNEL(bidi);
54
55 /* HELPER FUNCTIONS AND DECLARATIONS */
56
57 #define odd(x) ((x) & 1)
58
59 extern const unsigned short bidi_direction_table[] DECLSPEC_HIDDEN;
60
61 /*------------------------------------------------------------------------
62 Bidirectional Character Types
63
64 as defined by the Unicode Bidirectional Algorithm Table 3-7.
65
66 Note:
67
68 The list of bidirectional character types here is not grouped the
69 same way as the table 3-7, since the numeric values for the types
70 are chosen to keep the state and action tables compact.
71 ------------------------------------------------------------------------*/
72 enum directions
73 {
74 /* input types */
75 /* ON MUST be zero, code relies on ON = N = 0 */
76 ON = 0, /* Other Neutral */
77 L, /* Left Letter */
78 R, /* Right Letter */
79 AN, /* Arabic Number */
80 EN, /* European Number */
81 AL, /* Arabic Letter (Right-to-left) */
82 NSM, /* Non-spacing Mark */
83 CS, /* Common Separator */
84 ES, /* European Separator */
85 ET, /* European Terminator (post/prefix e.g. $ and %) */
86
87 /* resolved types */
88 BN, /* Boundary neutral (type of RLE etc after explicit levels) */
89
90 /* input types, */
91 S, /* Segment Separator (TAB) // used only in L1 */
92 WS, /* White space // used only in L1 */
93 B, /* Paragraph Separator (aka as PS) */
94
95 /* types for explicit controls */
96 RLO, /* these are used only in X1-X9 */
97 RLE,
98 LRO,
99 LRE,
100 PDF,
101
102 LRI, /* Isolate formatting characters new with 6.3 */
103 RLI,
104 FSI,
105 PDI,
106
107 /* resolved types, also resolved directions */
108 NI = ON, /* alias, where ON, WS and S are treated the same */
109 };
110
111 /* HELPER FUNCTIONS */
112
113 static inline unsigned short get_table_entry(const unsigned short *table, WCHAR ch)
114 {
115 return table[table[table[ch >> 8] + ((ch >> 4) & 0x0f)] + (ch & 0xf)];
116 }
117
118 /* Convert the libwine information to the direction enum */
119 static void classify(LPCWSTR lpString, WORD *chartype, DWORD uCount)
120 {
121 unsigned i;
122
123 for (i = 0; i < uCount; ++i)
124 chartype[i] = get_table_entry( bidi_direction_table, lpString[i] );
125 }
126
127 /* Set a run of cval values at locations all prior to, but not including */
128 /* iStart, to the new value nval. */
129 static void SetDeferredRun(BYTE *pval, int cval, int iStart, int nval)
130 {
131 int i = iStart - 1;
132 for (; i >= iStart - cval; i--)
133 {
134 pval[i] = nval;
135 }
136 }
137
138 /* THE PARAGRAPH LEVEL */
139
140 /*------------------------------------------------------------------------
141 Function: resolveParagraphs
142
143 Resolves the input strings into blocks over which the algorithm
144 is then applied.
145
146 Implements Rule P1 of the Unicode Bidi Algorithm
147
148 Input: Text string
149 Character count
150
151 Output: revised character count
152
153 Note: This is a very simplistic function. In effect it restricts
154 the action of the algorithm to the first paragraph in the input
155 where a paragraph ends at the end of the first block separator
156 or at the end of the input text.
157
158 ------------------------------------------------------------------------*/
159
160 static int resolveParagraphs(WORD *types, int cch)
161 {
162 /* skip characters not of type B */
163 int ich = 0;
164 for(; ich < cch && types[ich] != B; ich++);
165 /* stop after first B, make it a BN for use in the next steps */
166 if (ich < cch && types[ich] == B)
167 types[ich++] = BN;
168 return ich;
169 }
170
171 /* REORDER */
172 /*------------------------------------------------------------------------
173 Function: resolveLines
174
175 Breaks a paragraph into lines
176
177 Input: Array of line break flags
178 Character count
179 In/Out: Array of characters
180
181 Returns the count of characters on the first line
182
183 Note: This function only breaks lines at hard line breaks. Other
184 line breaks can be passed in. If pbrk[n] is TRUE, then a break
185 occurs after the character in pszInput[n]. Breaks before the first
186 character are not allowed.
187 ------------------------------------------------------------------------*/
188 static int resolveLines(LPCWSTR pszInput, const BOOL * pbrk, int cch)
189 {
190 /* skip characters not of type LS */
191 int ich = 0;
192 for(; ich < cch; ich++)
193 {
194 if (pszInput[ich] == (WCHAR)'\n' || (pbrk && pbrk[ich]))
195 {
196 ich++;
197 break;
198 }
199 }
200
201 return ich;
202 }
203
204 /*------------------------------------------------------------------------
205 Function: resolveWhiteSpace
206
207 Resolves levels for WS and S
208 Implements rule L1 of the Unicode bidi Algorithm.
209
210 Input: Base embedding level
211 Character count
212 Array of direction classes (for one line of text)
213
214 In/Out: Array of embedding levels (for one line of text)
215
216 Note: this should be applied a line at a time. The default driver
217 code supplied in this file assumes a single line of text; for
218 a real implementation, cch and the initial pointer values
219 would have to be adjusted.
220 ------------------------------------------------------------------------*/
221 static void resolveWhitespace(int baselevel, const WORD *pcls, BYTE *plevel, int cch)
222 {
223 int cchrun = 0;
224 BYTE oldlevel = baselevel;
225
226 int ich = 0;
227 for (; ich < cch; ich++)
228 {
229 switch(pcls[ich])
230 {
231 default:
232 cchrun = 0; /* any other character breaks the run */
233 break;
234 case WS:
235 cchrun++;
236 break;
237
238 case RLE:
239 case LRE:
240 case LRO:
241 case RLO:
242 case PDF:
243 case LRI:
244 case RLI:
245 case FSI:
246 case PDI:
247 case BN:
248 plevel[ich] = oldlevel;
249 cchrun++;
250 break;
251
252 case S:
253 case B:
254 /* reset levels for WS before eot */
255 SetDeferredRun(plevel, cchrun, ich, baselevel);
256 cchrun = 0;
257 plevel[ich] = baselevel;
258 break;
259 }
260 oldlevel = plevel[ich];
261 }
262 /* reset level before eot */
263 SetDeferredRun(plevel, cchrun, ich, baselevel);
264 }
265
266 /*------------------------------------------------------------------------
267 Function: BidiLines
268
269 Implements the Line-by-Line phases of the Unicode Bidi Algorithm
270
271 Input: Count of characters
272 Array of character directions
273
274 Inp/Out: Input text
275 Array of levels
276
277 ------------------------------------------------------------------------*/
278 static void BidiLines(int baselevel, LPWSTR pszOutLine, LPCWSTR pszLine, const WORD * pclsLine,
279 BYTE * plevelLine, int cchPara, const BOOL * pbrk)
280 {
281 int cchLine = 0;
282 int done = 0;
283 int *run;
284
285 run = HeapAlloc(GetProcessHeap(), 0, cchPara * sizeof(int));
286 if (!run)
287 {
288 WARN("Out of memory\n");
289 return;
290 }
291
292 do
293 {
294 /* break lines at LS */
295 cchLine = resolveLines(pszLine, pbrk, cchPara);
296
297 /* resolve whitespace */
298 resolveWhitespace(baselevel, pclsLine, plevelLine, cchLine);
299
300 if (pszOutLine)
301 {
302 int i;
303 /* reorder each line in place */
304 ScriptLayout(cchLine, plevelLine, NULL, run);
305 for (i = 0; i < cchLine; i++)
306 pszOutLine[done+run[i]] = pszLine[i];
307 }
308
309 pszLine += cchLine;
310 plevelLine += cchLine;
311 pbrk += pbrk ? cchLine : 0;
312 pclsLine += cchLine;
313 cchPara -= cchLine;
314 done += cchLine;
315
316 } while (cchPara);
317
318 HeapFree(GetProcessHeap(), 0, run);
319 }
320
321 /*************************************************************
322 * BIDI_Reorder
323 *
324 * Returns TRUE if reordering was required and done.
325 */
326 BOOL BIDI_Reorder(
327 HDC hDC, /*[in] Display DC */
328 LPCWSTR lpString, /* [in] The string for which information is to be returned */
329 INT uCount, /* [in] Number of WCHARs in string. */
330 DWORD dwFlags, /* [in] GetCharacterPlacement compatible flags specifying how to process the string */
331 DWORD dwWineGCP_Flags, /* [in] Wine internal flags - Force paragraph direction */
332 LPWSTR lpOutString, /* [out] Reordered string */
333 INT uCountOut, /* [in] Size of output buffer */
334 UINT *lpOrder, /* [out] Logical -> Visual order map */
335 WORD **lpGlyphs, /* [out] reordered, mirrored, shaped glyphs to display */
336 INT *cGlyphs /* [out] number of glyphs generated */
337 )
338 {
339 WORD *chartype;
340 BYTE *levels;
341 INT i, done;
342 unsigned glyph_i;
343 BOOL is_complex;
344
345 int maxItems;
346 int nItems;
347 SCRIPT_CONTROL Control;
348 SCRIPT_STATE State;
349 SCRIPT_ITEM *pItems;
350 HRESULT res;
351 SCRIPT_CACHE psc = NULL;
352 WORD *run_glyphs = NULL;
353 WORD *pwLogClust = NULL;
354 SCRIPT_VISATTR *psva = NULL;
355 DWORD cMaxGlyphs = 0;
356 BOOL doGlyphs = TRUE;
357
358 TRACE("%s, %d, 0x%08x lpOutString=%p, lpOrder=%p\n",
359 debugstr_wn(lpString, uCount), uCount, dwFlags,
360 lpOutString, lpOrder);
361
362 memset(&Control, 0, sizeof(Control));
363 memset(&State, 0, sizeof(State));
364 if (lpGlyphs)
365 *lpGlyphs = NULL;
366
367 if (!(dwFlags & GCP_REORDER))
368 {
369 FIXME("Asked to reorder without reorder flag set\n");
370 return FALSE;
371 }
372
373 if (lpOutString && uCountOut < uCount)
374 {
375 FIXME("lpOutString too small\n");
376 return FALSE;
377 }
378
379 chartype = HeapAlloc(GetProcessHeap(), 0, uCount * sizeof(WORD));
380 if (!chartype)
381 {
382 WARN("Out of memory\n");
383 return FALSE;
384 }
385
386 if (lpOutString)
387 memcpy(lpOutString, lpString, uCount * sizeof(WCHAR));
388
389 is_complex = FALSE;
390 for (i = 0; i < uCount && !is_complex; i++)
391 {
392 if ((lpString[i] >= 0x900 && lpString[i] <= 0xfff) ||
393 (lpString[i] >= 0x1cd0 && lpString[i] <= 0x1cff) ||
394 (lpString[i] >= 0xa840 && lpString[i] <= 0xa8ff))
395 is_complex = TRUE;
396 }
397
398 /* Verify reordering will be required */
399 if ((WINE_GCPW_FORCE_RTL == (dwWineGCP_Flags&WINE_GCPW_DIR_MASK)) ||
400 ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_RTL))
401 State.uBidiLevel = 1;
402 else if (!is_complex)
403 {
404 done = 1;
405 classify(lpString, chartype, uCount);
406 for (i = 0; i < uCount; i++)
407 switch (chartype[i])
408 {
409 case R:
410 case AL:
411 case RLE:
412 case RLO:
413 done = 0;
414 break;
415 }
416 if (done)
417 {
418 HeapFree(GetProcessHeap(), 0, chartype);
419 if (lpOrder)
420 {
421 for (i = 0; i < uCount; i++)
422 lpOrder[i] = i;
423 }
424 return TRUE;
425 }
426 }
427
428 levels = HeapAlloc(GetProcessHeap(), 0, uCount * sizeof(BYTE));
429 if (!levels)
430 {
431 WARN("Out of memory\n");
432 HeapFree(GetProcessHeap(), 0, chartype);
433 return FALSE;
434 }
435
436 maxItems = 5;
437 pItems = HeapAlloc(GetProcessHeap(),0, maxItems * sizeof(SCRIPT_ITEM));
438 if (!pItems)
439 {
440 WARN("Out of memory\n");
441 HeapFree(GetProcessHeap(), 0, chartype);
442 HeapFree(GetProcessHeap(), 0, levels);
443 return FALSE;
444 }
445
446 if (lpGlyphs)
447 {
448 cMaxGlyphs = 1.5 * uCount + 16;
449 run_glyphs = HeapAlloc(GetProcessHeap(),0,sizeof(WORD) * cMaxGlyphs);
450 if (!run_glyphs)
451 {
452 WARN("Out of memory\n");
453 HeapFree(GetProcessHeap(), 0, chartype);
454 HeapFree(GetProcessHeap(), 0, levels);
455 HeapFree(GetProcessHeap(), 0, pItems);
456 return FALSE;
457 }
458 pwLogClust = HeapAlloc(GetProcessHeap(),0,sizeof(WORD) * uCount);
459 if (!pwLogClust)
460 {
461 WARN("Out of memory\n");
462 HeapFree(GetProcessHeap(), 0, chartype);
463 HeapFree(GetProcessHeap(), 0, levels);
464 HeapFree(GetProcessHeap(), 0, pItems);
465 HeapFree(GetProcessHeap(), 0, run_glyphs);
466 return FALSE;
467 }
468 psva = HeapAlloc(GetProcessHeap(),0,sizeof(SCRIPT_VISATTR) * uCount);
469 if (!psva)
470 {
471 WARN("Out of memory\n");
472 HeapFree(GetProcessHeap(), 0, chartype);
473 HeapFree(GetProcessHeap(), 0, levels);
474 HeapFree(GetProcessHeap(), 0, pItems);
475 HeapFree(GetProcessHeap(), 0, run_glyphs);
476 HeapFree(GetProcessHeap(), 0, pwLogClust);
477 return FALSE;
478 }
479 }
480
481 done = 0;
482 glyph_i = 0;
483 while (done < uCount)
484 {
485 INT j;
486 classify(lpString + done, chartype, uCount - done);
487 /* limit text to first block */
488 i = resolveParagraphs(chartype, uCount - done);
489 for (j = 0; j < i; ++j)
490 switch(chartype[j])
491 {
492 case B:
493 case S:
494 case WS:
495 case ON: chartype[j] = NI;
496 default: continue;
497 }
498
499 if ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_RTL)
500 State.uBidiLevel = 1;
501 else if ((dwWineGCP_Flags&WINE_GCPW_DIR_MASK) == WINE_GCPW_LOOSE_LTR)
502 State.uBidiLevel = 0;
503
504 if (dwWineGCP_Flags & WINE_GCPW_LOOSE_MASK)
505 {
506 for (j = 0; j < i; ++j)
507 if (chartype[j] == L)
508 {
509 State.uBidiLevel = 0;
510 break;
511 }
512 else if (chartype[j] == R || chartype[j] == AL)
513 {
514 State.uBidiLevel = 1;
515 break;
516 }
517 }
518
519 res = ScriptItemize(lpString + done, i, maxItems, &Control, &State, pItems, &nItems);
520 while (res == E_OUTOFMEMORY)
521 {
522 maxItems = maxItems * 2;
523 pItems = HeapReAlloc(GetProcessHeap(), 0, pItems, sizeof(SCRIPT_ITEM) * maxItems);
524 if (!pItems)
525 {
526 WARN("Out of memory\n");
527 HeapFree(GetProcessHeap(), 0, chartype);
528 HeapFree(GetProcessHeap(), 0, levels);
529 HeapFree(GetProcessHeap(), 0, run_glyphs);
530 HeapFree(GetProcessHeap(), 0, pwLogClust);
531 HeapFree(GetProcessHeap(), 0, psva);
532 return FALSE;
533 }
534 res = ScriptItemize(lpString + done, i, maxItems, &Control, &State, pItems, &nItems);
535 }
536
537 if (lpOutString || lpOrder)
538 for (j = 0; j < nItems; j++)
539 {
540 int k;
541 for (k = pItems[j].iCharPos; k < pItems[j+1].iCharPos; k++)
542 levels[k] = pItems[j].a.s.uBidiLevel;
543 }
544
545 if (lpOutString)
546 {
547 /* assign directional types again, but for WS, S this time */
548 classify(lpString + done, chartype, i);
549
550 BidiLines(State.uBidiLevel, lpOutString + done, lpString + done,
551 chartype, levels, i, 0);
552 }
553
554 if (lpOrder)
555 {
556 int k, lastgood;
557 for (j = lastgood = 0; j < i; ++j)
558 if (levels[j] != levels[lastgood])
559 {
560 --j;
561 if (odd(levels[lastgood]))
562 for (k = j; k >= lastgood; --k)
563 lpOrder[done + k] = done + j - k;
564 else
565 for (k = lastgood; k <= j; ++k)
566 lpOrder[done + k] = done + k;
567 lastgood = ++j;
568 }
569 if (odd(levels[lastgood]))
570 for (k = j - 1; k >= lastgood; --k)
571 lpOrder[done + k] = done + j - 1 - k;
572 else
573 for (k = lastgood; k < j; ++k)
574 lpOrder[done + k] = done + k;
575 }
576
577 if (lpGlyphs && doGlyphs)
578 {
579 BYTE *runOrder;
580 int *visOrder;
581 SCRIPT_ITEM *curItem;
582
583 runOrder = HeapAlloc(GetProcessHeap(), 0, maxItems * sizeof(*runOrder));
584 visOrder = HeapAlloc(GetProcessHeap(), 0, maxItems * sizeof(*visOrder));
585 if (!runOrder || !visOrder)
586 {
587 WARN("Out of memory\n");
588 HeapFree(GetProcessHeap(), 0, runOrder);
589 HeapFree(GetProcessHeap(), 0, visOrder);
590 HeapFree(GetProcessHeap(), 0, chartype);
591 HeapFree(GetProcessHeap(), 0, levels);
592 HeapFree(GetProcessHeap(), 0, pItems);
593 HeapFree(GetProcessHeap(), 0, psva);
594 HeapFree(GetProcessHeap(), 0, pwLogClust);
595 return FALSE;
596 }
597
598 for (j = 0; j < nItems; j++)
599 runOrder[j] = pItems[j].a.s.uBidiLevel;
600
601 ScriptLayout(nItems, runOrder, visOrder, NULL);
602
603 for (j = 0; j < nItems; j++)
604 {
605 int k;
606 int cChars,cOutGlyphs;
607 curItem = &pItems[visOrder[j]];
608
609 cChars = pItems[visOrder[j]+1].iCharPos - curItem->iCharPos;
610
611 res = ScriptShape(hDC, &psc, lpString + done + curItem->iCharPos, cChars, cMaxGlyphs, &curItem->a, run_glyphs, pwLogClust, psva, &cOutGlyphs);
612 while (res == E_OUTOFMEMORY)
613 {
614 cMaxGlyphs *= 2;
615 run_glyphs = HeapReAlloc(GetProcessHeap(), 0, run_glyphs, sizeof(WORD) * cMaxGlyphs);
616 if (!run_glyphs)
617 {
618 WARN("Out of memory\n");
619 HeapFree(GetProcessHeap(), 0, runOrder);
620 HeapFree(GetProcessHeap(), 0, visOrder);
621 HeapFree(GetProcessHeap(), 0, chartype);
622 HeapFree(GetProcessHeap(), 0, levels);
623 HeapFree(GetProcessHeap(), 0, pItems);
624 HeapFree(GetProcessHeap(), 0, psva);
625 HeapFree(GetProcessHeap(), 0, pwLogClust);
626 HeapFree(GetProcessHeap(), 0, *lpGlyphs);
627 ScriptFreeCache(&psc);
628 *lpGlyphs = NULL;
629 return FALSE;
630 }
631 res = ScriptShape(hDC, &psc, lpString + done + curItem->iCharPos, cChars, cMaxGlyphs, &curItem->a, run_glyphs, pwLogClust, psva, &cOutGlyphs);
632 }
633 if (res)
634 {
635 if (res == USP_E_SCRIPT_NOT_IN_FONT)
636 TRACE("Unable to shape with currently selected font\n");
637 else
638 FIXME("Unable to shape string (%x)\n",res);
639 j = nItems;
640 doGlyphs = FALSE;
641 HeapFree(GetProcessHeap(), 0, *lpGlyphs);
642 *lpGlyphs = NULL;
643 }
644 else
645 {
646 if (*lpGlyphs)
647 *lpGlyphs = HeapReAlloc(GetProcessHeap(), 0, *lpGlyphs, sizeof(WORD) * (glyph_i + cOutGlyphs));
648 else
649 *lpGlyphs = HeapAlloc(GetProcessHeap(), 0, sizeof(WORD) * (glyph_i + cOutGlyphs));
650 for (k = 0; k < cOutGlyphs; k++)
651 (*lpGlyphs)[glyph_i+k] = run_glyphs[k];
652 glyph_i += cOutGlyphs;
653 }
654 }
655 HeapFree(GetProcessHeap(), 0, runOrder);
656 HeapFree(GetProcessHeap(), 0, visOrder);
657 }
658
659 done += i;
660 }
661 if (cGlyphs)
662 *cGlyphs = glyph_i;
663
664 HeapFree(GetProcessHeap(), 0, chartype);
665 HeapFree(GetProcessHeap(), 0, levels);
666 HeapFree(GetProcessHeap(), 0, pItems);
667 HeapFree(GetProcessHeap(), 0, run_glyphs);
668 HeapFree(GetProcessHeap(), 0, pwLogClust);
669 HeapFree(GetProcessHeap(), 0, psva);
670 ScriptFreeCache(&psc);
671 return TRUE;
672 }
Windows API implementation