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