vcl/source/gdi/sallayout.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: sallayout.cxx,v $
  10  * $Revision: 1.94.90.2 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_vcl.hxx"
  33
  34 #include <cstdio>
  35
  36 #define _USE_MATH_DEFINES
  37 #include <math.h>
  38 #include <sal/alloca.h>
  39
  40 #ifndef _SV_SVSYS_HXX
  41 #include <svsys.h>
  42 #endif
  43 #include <vcl/salgdi.hxx>
  44 #include <vcl/sallayout.hxx>
  45 #include <basegfx/polygon/b2dpolypolygon.hxx>
  46 #include <basegfx/matrix/b2dhommatrix.hxx>
  47 #include <i18npool/lang.h>
  48
  49 #ifndef _TL_DEBUG_HXX
  50 #include <tools/debug.hxx>
  51 #endif
  52
  53 #include <limits.h>
  54
  55 #if defined _MSC_VER
  56 #pragma warning(push, 1)
  57 #endif
  58 #include <unicode/ubidi.h>
  59 #include <unicode/uchar.h>
  60 #if defined _MSC_VER
  61 #pragma warning(pop)
  62 #endif
  63
  64 #include <algorithm>
  65
  66 #ifdef DEBUG
  67 //#define MULTI_SL_DEBUG
  68 #endif
  69
  70 #ifdef MULTI_SL_DEBUG
  71 #include <string>
  72 FILE * mslLogFile = NULL;
  73 FILE * mslLog()
  74 {
  75 #ifdef MSC
  76     std::string logFileName(getenv("TEMP"));
  77     logFileName.append("\\msllayout.log");
  78     if (mslLogFile == NULL) mslLogFile = fopen(logFileName.c_str(),"w");
  79     else fflush(mslLogFile);
  80     return mslLogFile;
  81 #else
  82     return stdout;
  83 #endif
  84 }
  85 #endif
  86 // =======================================================================
  87
  88 // TODO: ask the glyph directly, for now we need this method because of #i99367#
  89 // true if a codepoint doesn't influence the logical text width
  90 bool IsDiacritic( sal_UCS4 nChar )
  91 {
  92     // shortcut abvious non-diacritics
  93     if( nChar < 0x0300 )
  94         return false;
  95      if( nChar >= 0x2100 )
  96         return false;
  97
  98     struct DiaRange { sal_UCS4 mnMin, mnEnd;};
  99     static const DiaRange aRanges[] = {
 100         {0x0300, 0x0370},
 101         {0x0590, 0x05C0}, {0x05C1, 0x05C3}, {0x05C3, 0x05C6}, {0x05C7, 0x05C8},
 102         {0x0610, 0x061B}, {0x064B, 0x0660}, {0x0670, 0x0671}, {0x06D6, 0x06DC}, {0x06DF, 0x06EE},
 103         {0x0730, 0x074D}, {0x07A6, 0x07B1}, {0x07EB, 0x07F4},
 104 #if 0 // all known fonts have zero-width diacritics already, so no need to query it
 105         {0x0900, 0x0904}, {0x093C, 0x093D}, {0x0941, 0x0948}, {0x094D, 0x0950}, {0x0951, 0x0958},
 106         {0x0980, 0x0985}, {0x09BC, 0x09BD}, {0x09C1, 0x09C7}, {0x09CD, 0x09CE}, {0x09E2, 0x09E6},
 107         {0x0A00, 0x0A05}, {0x0A3C, 0x0A59}, //...
 108 #endif
 109         {0x1DC0, 0x1E00},
 110         {0x205F, 0x2070}, {0x20D0, 0x2100}
 111     };
 112
 113     // TODO: almost anything is faster than an O(n) search
 114     static const int nCount = sizeof(aRanges) / sizeof(*aRanges);
 115     const DiaRange* pRange = &aRanges[0];
 116     for( int i = nCount; --i >= 0; ++pRange )
 117         if( (pRange->mnMin <= nChar) && (nChar < pRange->mnEnd) )
 118             return true;
 119
 120     return false;
 121 }
 122
 123 // =======================================================================
 124
 125 int GetVerticalFlags( sal_UCS4 nChar )
 126 {
 127     if( (nChar >= 0x1100 && nChar <= 0x11f9)    // Hangul Jamo
 128      || (nChar == 0x2030 || nChar == 0x2031)    // per mille sign
 129      || (nChar >= 0x3000 && nChar <= 0xfaff)    // unified CJK
 130      || (nChar >= 0xfe20 && nChar <= 0xfe6f)    // CJK compatibility
 131      || (nChar >= 0xff00 && nChar <= 0xfffd) )  // other CJK
 132     {
 133         /* #i52932# remember:
 134          nChar == 0x2010 || nChar == 0x2015
 135          nChar == 0x2016 || nChar == 0x2026
 136
 137          are GF_NONE also, but already handled in the first if
 138         */
 139         if((nChar >= 0x3008 && nChar <= 0x301C && nChar != 0x3012)
 140         ||  nChar == 0xFF3B || nChar == 0xFF3D
 141         || (nChar >= 0xFF5B && nChar <= 0xFF9F) // halfwidth forms
 142         ||  nChar == 0xFFE3 )
 143             return GF_NONE; // not rotated
 144         else if( nChar == 0x30fc )
 145             return GF_ROTR; // right
 146         return GF_ROTL;     // left
 147     }
 148
 149     return GF_NONE;
 150 }
 151
 152 // -----------------------------------------------------------------------
 153
 154 sal_UCS4 GetVerticalChar( sal_UCS4 )
 155 {
 156     return 0; // #i14788# input method is responsible vertical char changes
 157
 158 #if 0
 159     int nVert = 0;
 160     switch( nChar )
 161     {
 162         // #104627# special treatment for some unicodes
 163         case 0x002C: nVert = 0x3001; break;
 164         case 0x002E: nVert = 0x3002; break;
 165         /*
 166         // to few fonts have the compatibility forms, using
 167         // them will then cause more trouble than good
 168         // TODO: decide on a font specific basis
 169         case 0x2018: nVert = 0xFE41; break;
 170         case 0x2019: nVert = 0xFE42; break;
 171         case 0x201C: nVert = 0xFE43; break;
 172         case 0x201D: nVert = 0xFE44; break;
 173         // CJK compatibility forms
 174         case 0x2025: nVert = 0xFE30; break;
 175         case 0x2014: nVert = 0xFE31; break;
 176         case 0x2013: nVert = 0xFE32; break;
 177         case 0x005F: nVert = 0xFE33; break;
 178         case 0x0028: nVert = 0xFE35; break;
 179         case 0x0029: nVert = 0xFE36; break;
 180         case 0x007B: nVert = 0xFE37; break;
 181         case 0x007D: nVert = 0xFE38; break;
 182         case 0x3014: nVert = 0xFE39; break;
 183         case 0x3015: nVert = 0xFE3A; break;
 184         case 0x3010: nVert = 0xFE3B; break;
 185         case 0x3011: nVert = 0xFE3C; break;
 186         case 0x300A: nVert = 0xFE3D; break;
 187         case 0x300B: nVert = 0xFE3E; break;
 188         case 0x3008: nVert = 0xFE3F; break;
 189         case 0x3009: nVert = 0xFE40; break;
 190         case 0x300C: nVert = 0xFE41; break;
 191         case 0x300D: nVert = 0xFE42; break;
 192         case 0x300E: nVert = 0xFE43; break;
 193         case 0x300F: nVert = 0xFE44; break;
 194         */
 195     }
 196
 197     return nVert;
 198 #endif
 199 }
 200
 201 // -----------------------------------------------------------------------
 202
 203 VCL_DLLPUBLIC sal_UCS4 GetMirroredChar( sal_UCS4 nChar )
 204 {
 205     nChar = u_charMirror( nChar );
 206     return nChar;
 207 }
 208
 209 // -----------------------------------------------------------------------
 210
 211 // Get simple approximations for unicodes
 212 const char* GetAutofallback( sal_UCS4 nChar )
 213 {
 214     const char* pStr = NULL;
 215     switch( nChar )
 216     {
 217         case 0x01C0:
 218         case 0x2223:
 219         case 0x2758:
 220             pStr = "|"; break;
 221         case 0x02DC:
 222             pStr = "~"; break;
 223         case 0x037E:
 224             pStr = ";"; break;
 225         case 0x2000:
 226         case 0x2001:
 227         case 0x2002:
 228         case 0x2003:
 229         case 0x2004:
 230         case 0x2005:
 231         case 0x2006:
 232         case 0x2007:
 233         case 0x2008:
 234         case 0x2009:
 235         case 0x200A:
 236         case 0x202F:
 237             pStr = " "; break;
 238         case 0x2010:
 239         case 0x2011:
 240         case 0x2012:
 241         case 0x2013:
 242         case 0x2014:
 243             pStr = "-"; break;
 244         case 0x2015:
 245             pStr = "--"; break;
 246         case 0x2016:
 247             pStr = "||"; break;
 248         case 0x2017:
 249             pStr = "_"; break;
 250         case 0x2018:
 251         case 0x2019:
 252         case 0x201B:
 253             pStr = "\'"; break;
 254         case 0x201A:
 255             pStr = ","; break;
 256         case 0x201C:
 257         case 0x201D:
 258         case 0x201E:
 259         case 0x201F:
 260         case 0x2033:
 261             pStr = "\""; break;
 262         case 0x2039:
 263             pStr = "<"; break;
 264         case 0x203A:
 265             pStr = ">"; break;
 266         case 0x203C:
 267             pStr = "!!"; break;
 268         case 0x203D:
 269             pStr = "?"; break;
 270         case 0x2044:
 271         case 0x2215:
 272             pStr = "/"; break;
 273         case 0x2048:
 274             pStr = "?!"; break;
 275         case 0x2049:
 276             pStr = "!?"; break;
 277         case 0x2216:
 278             pStr = "\\"; break;
 279         case 0x2217:
 280             pStr = "*"; break;
 281         case 0x2236:
 282             pStr = ":"; break;
 283         case 0x2264:
 284             pStr = "<="; break;
 285         case 0x2265:
 286             pStr = "<="; break;
 287         case 0x2303:
 288             pStr = "^"; break;
 289     }
 290
 291     return pStr;
 292 }
 293
 294 // -----------------------------------------------------------------------
 295
 296 sal_UCS4 GetLocalizedChar( sal_UCS4 nChar, LanguageType eLang )
 297 {
 298     // currently only conversion from ASCII digits is interesting
 299     if( (nChar < '0') || ('9' < nChar) )
 300         return nChar;
 301
 302     int nOffset;
 303     // eLang & LANGUAGE_MASK_PRIMARY catches language independent of region.
 304     // CAVEAT! To some like Mongolian MS assigned the same primary language
 305     // although the script type is different!
 306     switch( eLang & LANGUAGE_MASK_PRIMARY )
 307     {
 308         default:
 309             nOffset = 0;
 310             break;
 311         case LANGUAGE_ARABIC_SAUDI_ARABIA  & LANGUAGE_MASK_PRIMARY:
 312             nOffset = 0x0660 - '0';  // arabic-indic digits
 313             break;
 314         case LANGUAGE_FARSI         & LANGUAGE_MASK_PRIMARY:
 315         case LANGUAGE_URDU          & LANGUAGE_MASK_PRIMARY:
 316         case LANGUAGE_PUNJABI       & LANGUAGE_MASK_PRIMARY: //???
 317         case LANGUAGE_SINDHI        & LANGUAGE_MASK_PRIMARY:
 318             nOffset = 0x06F0 - '0';  // eastern arabic-indic digits
 319             break;
 320         case LANGUAGE_BENGALI       & LANGUAGE_MASK_PRIMARY:
 321             nOffset = 0x09E6 - '0';  // bengali
 322             break;
 323         case LANGUAGE_HINDI         & LANGUAGE_MASK_PRIMARY:
 324             nOffset = 0x0966 - '0';  // devanagari
 325             break;
 326         case LANGUAGE_AMHARIC_ETHIOPIA & LANGUAGE_MASK_PRIMARY:
 327         case LANGUAGE_TIGRIGNA_ETHIOPIA & LANGUAGE_MASK_PRIMARY:
 328         // TODO case:
 329             nOffset = 0x1369 - '0';  // ethiopic
 330             break;
 331         case LANGUAGE_GUJARATI      & LANGUAGE_MASK_PRIMARY:
 332             nOffset = 0x0AE6 - '0';  // gujarati
 333             break;
 334 #ifdef LANGUAGE_GURMUKHI // TODO case:
 335         case LANGUAGE_GURMUKHI      & LANGUAGE_MASK_PRIMARY:
 336             nOffset = 0x0A66 - '0';  // gurmukhi
 337             break;
 338 #endif
 339         case LANGUAGE_KANNADA       & LANGUAGE_MASK_PRIMARY:
 340             nOffset = 0x0CE6 - '0';  // kannada
 341             break;
 342         case LANGUAGE_KHMER         & LANGUAGE_MASK_PRIMARY:
 343             nOffset = 0x17E0 - '0';  // khmer
 344             break;
 345         case LANGUAGE_LAO           & LANGUAGE_MASK_PRIMARY:
 346             nOffset = 0x0ED0 - '0';  // lao
 347             break;
 348         case LANGUAGE_MALAYALAM     & LANGUAGE_MASK_PRIMARY:
 349             nOffset = 0x0D66 - '0';  // malayalam
 350             break;
 351         case LANGUAGE_MONGOLIAN     & LANGUAGE_MASK_PRIMARY:
 352             if (eLang == LANGUAGE_MONGOLIAN_MONGOLIAN)
 353                 nOffset = 0x1810 - '0';   // mongolian
 354             else
 355                 nOffset = 0;              // mongolian cyrillic
 356             break;
 357         case LANGUAGE_BURMESE       & LANGUAGE_MASK_PRIMARY:
 358             nOffset = 0x1040 - '0';  // myanmar
 359             break;
 360         case LANGUAGE_ORIYA         & LANGUAGE_MASK_PRIMARY:
 361             nOffset = 0x0B66 - '0';  // oriya
 362             break;
 363         case LANGUAGE_TAMIL         & LANGUAGE_MASK_PRIMARY:
 364             nOffset = 0x0BE7 - '0';  // tamil
 365             break;
 366         case LANGUAGE_TELUGU        & LANGUAGE_MASK_PRIMARY:
 367             nOffset = 0x0C66 - '0';  // telugu
 368             break;
 369         case LANGUAGE_THAI          & LANGUAGE_MASK_PRIMARY:
 370             nOffset = 0x0E50 - '0';  // thai
 371             break;
 372         case LANGUAGE_TIBETAN       & LANGUAGE_MASK_PRIMARY:
 373             nOffset = 0x0F20 - '0';  // tibetan
 374             break;
 375 #if 0 // TODO: use language type for these digit substitutions?
 376         // TODO case:
 377             nOffset = 0x2776 - '0';  // dingbat circled
 378             break;
 379         // TODO case:
 380             nOffset = 0x2070 - '0';  // superscript
 381             break;
 382         // TODO case:
 383             nOffset = 0x2080 - '0';  // subscript
 384             break;
 385 #endif
 386     }
 387
 388     nChar += nOffset;
 389     return nChar;
 390 }
 391
 392 // -----------------------------------------------------------------------
 393
 394 inline bool IsControlChar( sal_UCS4 cChar )
 395 {
 396     // C0 control characters
 397     if( (0x0001 <= cChar) && (cChar <= 0x001F) )
 398         return true;
 399     // formatting characters
 400     if( (0x200E <= cChar) && (cChar <= 0x200F) )
 401         return true;
 402     if( (0x2028 <= cChar) && (cChar <= 0x202E) )
 403         return true;
 404     // deprecated formatting characters
 405     if( (0x206A <= cChar) && (cChar <= 0x206F) )
 406         return true;
 407     if( (0x2060 == cChar) )
 408         return true;
 409     // byte order markers and invalid unicode
 410     if( (cChar == 0xFEFF) || (cChar == 0xFFFE) || (cChar == 0xFFFF) )
 411         return true;
 412     return false;
 413 }
 414
 415 // =======================================================================
 416
 417 bool ImplLayoutRuns::AddPos( int nCharPos, bool bRTL )
 418 {
 419     // check if charpos could extend current run
 420     int nIndex = maRuns.size();
 421     if( nIndex >= 2 )
 422     {
 423         int nRunPos0 = maRuns[ nIndex-2 ];
 424         int nRunPos1 = maRuns[ nIndex-1 ];
 425         if( ((nCharPos + bRTL) == nRunPos1)
 426     &&  ((nRunPos0 > nRunPos1) == bRTL) )
 427         {
 428             // extend current run by new charpos
 429             maRuns[ nIndex-1 ] = nCharPos + !bRTL;
 430             return false;
 431         }
 432         // ignore new charpos when it is in current run
 433         if( (nRunPos0 <= nCharPos) && (nCharPos < nRunPos1) )
 434             return false;
 435         if( (nRunPos1 <= nCharPos) && (nCharPos < nRunPos0) )
 436             return false;
 437     }
 438
 439     // else append a new run consisting of the new charpos
 440     maRuns.push_back( nCharPos + (bRTL ? 1 : 0) );
 441     maRuns.push_back( nCharPos + (bRTL ? 0 : 1) );
 442     return true;
 443 }
 444
 445 // -----------------------------------------------------------------------
 446
 447 bool ImplLayoutRuns::AddRun( int nCharPos0, int nCharPos1, bool bRTL )
 448 {
 449     if( nCharPos0 == nCharPos1 )
 450         return false;
 451
 452     // swap if needed
 453     if( bRTL == (nCharPos0 < nCharPos1) )
 454     {
 455         int nTemp = nCharPos0;
 456         nCharPos0 = nCharPos1;
 457         nCharPos1 = nTemp;
 458     }
 459
 460     // append new run
 461     maRuns.push_back( nCharPos0 );
 462     maRuns.push_back( nCharPos1 );
 463     return true;
 464 }
 465
 466 // -----------------------------------------------------------------------
 467
 468 bool ImplLayoutRuns::PosIsInRun( int nCharPos ) const
 469 {
 470     if( mnRunIndex >= (int)maRuns.size() )
 471         return false;
 472
 473     int nMinCharPos = maRuns[ mnRunIndex+0 ];
 474     int nEndCharPos = maRuns[ mnRunIndex+1 ];
 475     if( nMinCharPos > nEndCharPos ) // reversed in RTL case
 476     {
 477         int nTemp = nMinCharPos;
 478         nMinCharPos = nEndCharPos;
 479         nEndCharPos = nTemp;
 480     }
 481
 482     if( nCharPos < nMinCharPos )
 483         return false;
 484     if( nCharPos >= nEndCharPos )
 485         return false;
 486     return true;
 487 }
 488
 489 bool ImplLayoutRuns::PosIsInAnyRun( int nCharPos ) const
 490 {
 491     bool bRet = false;
 492     int nRunIndex = mnRunIndex;
 493
 494     ImplLayoutRuns *pThis = const_cast<ImplLayoutRuns*>(this);
 495
 496     pThis->ResetPos();
 497
 498     for (size_t i = 0; i < maRuns.size(); i+=2)
 499     {
 500         if( (bRet = PosIsInRun( nCharPos )) == true )
 501             break;
 502         pThis->NextRun();
 503     }
 504
 505     pThis->mnRunIndex = nRunIndex;
 506     return bRet;
 507 }
 508
 509
 510 // -----------------------------------------------------------------------
 511
 512 bool ImplLayoutRuns::GetNextPos( int* nCharPos, bool* bRightToLeft )
 513 {
 514     // negative nCharPos => reset to first run
 515     if( *nCharPos < 0 )
 516         mnRunIndex = 0;
 517
 518     // return false when all runs completed
 519     if( mnRunIndex >= (int)maRuns.size() )
 520         return false;
 521
 522     int nRunPos0 = maRuns[ mnRunIndex+0 ];
 523     int nRunPos1 = maRuns[ mnRunIndex+1 ];
 524     *bRightToLeft = (nRunPos0 > nRunPos1);
 525
 526     if( *nCharPos < 0 )
 527     {
 528         // get first valid nCharPos in run
 529         *nCharPos = nRunPos0;
 530     }
 531     else
 532     {
 533         // advance to next nCharPos for LTR case
 534         if( !*bRightToLeft )
 535             ++(*nCharPos);
 536
 537         // advance to next run if current run is completed
 538         if( *nCharPos == nRunPos1 )
 539         {
 540             if( (mnRunIndex += 2) >= (int)maRuns.size() )
 541                 return false;
 542             nRunPos0 = maRuns[ mnRunIndex+0 ];
 543             nRunPos1 = maRuns[ mnRunIndex+1 ];
 544             *bRightToLeft = (nRunPos0 > nRunPos1);
 545             *nCharPos = nRunPos0;
 546         }
 547     }
 548
 549     // advance to next nCharPos for RTL case
 550     if( *bRightToLeft )
 551         --(*nCharPos);
 552
 553     return true;
 554 }
 555
 556 // -----------------------------------------------------------------------
 557
 558 bool ImplLayoutRuns::GetRun( int* nMinRunPos, int* nEndRunPos, bool* bRightToLeft ) const
 559 {
 560     if( mnRunIndex >= (int)maRuns.size() )
 561         return false;
 562
 563     int nRunPos0 = maRuns[ mnRunIndex+0 ];
 564     int nRunPos1 = maRuns[ mnRunIndex+1 ];
 565     *bRightToLeft = (nRunPos1 < nRunPos0) ;
 566     if( !*bRightToLeft )
 567     {
 568         *nMinRunPos = nRunPos0;
 569         *nEndRunPos = nRunPos1;
 570     }
 571     else
 572     {
 573         *nMinRunPos = nRunPos1;
 574         *nEndRunPos = nRunPos0;
 575     }
 576     return true;
 577 }
 578
 579 // =======================================================================
 580
 581 ImplLayoutArgs::ImplLayoutArgs( const xub_Unicode* pStr, int nLen,
 582     int nMinCharPos, int nEndCharPos, int nFlags )
 583 :
 584     mnFlags( nFlags ),
 585     mnLength( nLen ),
 586     mnMinCharPos( nMinCharPos ),
 587     mnEndCharPos( nEndCharPos ),
 588     mpStr( pStr ),
 589     mpDXArray( NULL ),
 590     mnLayoutWidth( 0 ),
 591     mnOrientation( 0 )
 592 {
 593     if( mnFlags & SAL_LAYOUT_BIDI_STRONG )
 594     {
 595         // handle strong BiDi mode
 596
 597         // do not bother to BiDi analyze strong LTR/RTL
 598         // TODO: can we assume these strings do not have unicode control chars?
 599         //       if not remove the control characters from the runs
 600         bool bRTL = ((mnFlags & SAL_LAYOUT_BIDI_RTL) != 0);
 601         AddRun( mnMinCharPos, mnEndCharPos, bRTL );
 602     }
 603     else
 604     {
 605         // handle weak BiDi mode
 606
 607         UBiDiLevel nLevel = UBIDI_DEFAULT_LTR;
 608         if( mnFlags & SAL_LAYOUT_BIDI_RTL )
 609             nLevel = UBIDI_DEFAULT_RTL;
 610
 611         // prepare substring for BiDi analysis
 612         // TODO: reuse allocated pParaBidi
 613         UErrorCode rcI18n = U_ZERO_ERROR;
 614         UBiDi* pParaBidi = ubidi_openSized( mnLength, 0, &rcI18n );
 615         if( !pParaBidi )
 616             return;
 617         ubidi_setPara( pParaBidi, reinterpret_cast<const UChar *>(mpStr), mnLength, nLevel, NULL, &rcI18n );    // UChar != sal_Unicode in MinGW
 618
 619         UBiDi* pLineBidi = pParaBidi;
 620         int nSubLength = mnEndCharPos - mnMinCharPos;
 621         if( nSubLength != mnLength )
 622         {
 623             pLineBidi = ubidi_openSized( nSubLength, 0, &rcI18n );
 624             ubidi_setLine( pParaBidi, mnMinCharPos, mnEndCharPos, pLineBidi, &rcI18n );
 625         }
 626
 627         // run BiDi algorithm
 628         const int nRunCount = ubidi_countRuns( pLineBidi, &rcI18n );
 629         //maRuns.resize( 2 * nRunCount );
 630         for( int i = 0; i < nRunCount; ++i )
 631         {
 632             int32_t nMinPos, nLength;
 633             const UBiDiDirection nDir = ubidi_getVisualRun( pLineBidi, i, &nMinPos, &nLength );
 634             const int nPos0 = nMinPos + mnMinCharPos;
 635             const int nPos1 = nPos0 + nLength;
 636
 637             const bool bRTL = (nDir == UBIDI_RTL);
 638             AddRun( nPos0, nPos1, bRTL );
 639         }
 640
 641         // cleanup BiDi engine
 642         if( pLineBidi != pParaBidi )
 643             ubidi_close( pLineBidi );
 644         ubidi_close( pParaBidi );
 645     }
 646
 647     // prepare calls to GetNextPos/GetNextRun
 648     maRuns.ResetPos();
 649 }
 650
 651 // -----------------------------------------------------------------------
 652
 653 // add a run after splitting it up to get rid of control chars
 654 void ImplLayoutArgs::AddRun( int nCharPos0, int nCharPos1, bool bRTL )
 655 {
 656     DBG_ASSERT( nCharPos0 <= nCharPos1, "ImplLayoutArgs::AddRun() nCharPos0>=nCharPos1" );
 657
 658     // remove control characters from runs by splitting them up
 659     if( !bRTL )
 660     {
 661         for( int i = nCharPos0; i < nCharPos1; ++i )
 662             if( IsControlChar( mpStr[i] ) )
 663             {
 664                 // add run until control char
 665                 maRuns.AddRun( nCharPos0, i, bRTL );
 666                 nCharPos0 = i + 1;
 667             }
 668     }
 669     else
 670     {
 671         for( int i = nCharPos1; --i >= nCharPos0; )
 672             if( IsControlChar( mpStr[i] ) )
 673             {
 674                 // add run until control char
 675                 maRuns.AddRun( i+1, nCharPos1, bRTL );
 676                 nCharPos1 = i;
 677             }
 678     }
 679
 680     // add remainder of run
 681     maRuns.AddRun( nCharPos0, nCharPos1, bRTL );
 682 }
 683
 684 // -----------------------------------------------------------------------
 685
 686 bool ImplLayoutArgs::PrepareFallback()
 687 {
 688     // short circuit if no fallback is needed
 689     if( maReruns.IsEmpty() )
 690     {
 691         maRuns.Clear();
 692         return false;
 693     }
 694
 695     // convert the fallback requests to layout requests
 696     bool bRTL;
 697     int nMin, nEnd;
 698
 699     // get the individual fallback requests
 700     typedef std::vector<int> IntVector;
 701     IntVector aPosVector;
 702     aPosVector.reserve( mnLength );
 703     maReruns.ResetPos();
 704     for(; maReruns.GetRun( &nMin, &nEnd, &bRTL ); maReruns.NextRun() )
 705         for( int i = nMin; i < nEnd; ++i )
 706             aPosVector.push_back( i );
 707     maReruns.Clear();
 708
 709     // sort the individual fallback requests
 710     std::sort( aPosVector.begin(), aPosVector.end() );
 711
 712     // adjust fallback runs to have the same order and limits of the original runs
 713     ImplLayoutRuns aNewRuns;
 714     maRuns.ResetPos();
 715     for(; maRuns.GetRun( &nMin, &nEnd, &bRTL ); maRuns.NextRun() )
 716     {
 717         if( !bRTL) {
 718             IntVector::const_iterator it = std::lower_bound( aPosVector.begin(), aPosVector.end(), nMin );
 719             for(; (it != aPosVector.end()) && (*it < nEnd); ++it )
 720                 aNewRuns.AddPos( *it, bRTL );
 721         } else {
 722             IntVector::const_iterator it = std::upper_bound( aPosVector.begin(), aPosVector.end(), nEnd );
 723             while( (it != aPosVector.begin()) && (*--it >= nMin) )
 724                 aNewRuns.AddPos( *it, bRTL );
 725         }
 726     }
 727
 728     maRuns = aNewRuns;  // TODO: use vector<>::swap()
 729     maRuns.ResetPos();
 730     return true;
 731 }
 732
 733 // -----------------------------------------------------------------------
 734
 735 bool ImplLayoutArgs::GetNextRun( int* nMinRunPos, int* nEndRunPos, bool* bRTL )
 736 {
 737     bool bValid = maRuns.GetRun( nMinRunPos, nEndRunPos, bRTL );
 738     maRuns.NextRun();
 739     return bValid;
 740 }
 741
 742 // =======================================================================
 743
 744 SalLayout::SalLayout()
 745 :   mnMinCharPos( -1 ),
 746     mnEndCharPos( -1 ),
 747     mnLayoutFlags( 0 ),
 748     mnUnitsPerPixel( 1 ),
 749     mnOrientation( 0 ),
 750     mnRefCount( 1 ),
 751     maDrawOffset( 0, 0 )
 752 {}
 753
 754 // -----------------------------------------------------------------------
 755
 756 SalLayout::~SalLayout()
 757 {}
 758
 759 // -----------------------------------------------------------------------
 760
 761 void SalLayout::AdjustLayout( ImplLayoutArgs& rArgs )
 762 {
 763     mnMinCharPos  = rArgs.mnMinCharPos;
 764     mnEndCharPos  = rArgs.mnEndCharPos;
 765     mnLayoutFlags = rArgs.mnFlags;
 766     mnOrientation = rArgs.mnOrientation;
 767 }
 768
 769 // -----------------------------------------------------------------------
 770
 771 void SalLayout::Reference() const
 772 {
 773     // TODO: protect when multiple threads can access this
 774     ++mnRefCount;
 775 }
 776
 777 // -----------------------------------------------------------------------
 778
 779 void SalLayout::Release() const
 780 {
 781     // TODO: protect when multiple threads can access this
 782     if( --mnRefCount > 0 )
 783         return;
 784     // const_cast because some compilers violate ANSI C++ spec
 785     delete const_cast<SalLayout*>(this);
 786 }
 787
 788 // -----------------------------------------------------------------------
 789
 790 Point SalLayout::GetDrawPosition( const Point& rRelative ) const
 791 {
 792     Point aPos = maDrawBase;
 793     Point aOfs = rRelative + maDrawOffset;
 794
 795     if( mnOrientation == 0 )
 796         aPos += aOfs;
 797     else
 798     {
 799         // cache trigonometric results
 800         static int nOldOrientation = 0;
 801         static double fCos = 1.0, fSin = 0.0;
 802         if( nOldOrientation != mnOrientation )
 803         {
 804             nOldOrientation = mnOrientation;
 805             double fRad = mnOrientation * (M_PI / 1800.0);
 806             fCos = cos( fRad );
 807             fSin = sin( fRad );
 808         }
 809
 810         double fX = aOfs.X();
 811         double fY = aOfs.Y();
 812         long nX = static_cast<long>( +fCos * fX + fSin * fY );
 813         long nY = static_cast<long>( +fCos * fY - fSin * fX );
 814         aPos += Point( nX, nY );
 815     }
 816
 817     return aPos;
 818 }
 819
 820 // -----------------------------------------------------------------------
 821
 822 // returns asian kerning values in quarter of character width units
 823 // to enable automatic halfwidth substitution for fullwidth punctuation
 824 // return value is negative for l, positive for r, zero for neutral
 825
 826 // If the range doesn't match in 0x3000 and 0x30FB, please change
 827 // also ImplCalcKerning.
 828
 829 int SalLayout::CalcAsianKerning( sal_UCS4 c, bool bLeft, bool /*TODO:? bVertical*/ )
 830 {
 831     // http://www.asahi-net.or.jp/~sd5a-ucd/freetexts/jis/x4051/1995/appendix.html
 832     static signed char nTable[0x30] =
 833     {
 834          0, -2, -2,  0,   0,  0,  0,  0,  +2, -2, +2, -2,  +2, -2, +2, -2,
 835         +2, -2,  0,  0,  +2, -2, +2, -2,   0,  0,  0,  0,   0, +2, -2, -2,
 836          0,  0,  0,  0,   0,  0,  0,  0,   0,  0, -2, -2,  +2, +2, -2, -2
 837     };
 838
 839     int nResult = 0;
 840     if( (c >= 0x3000) && (c < 0x3030) )
 841         nResult = nTable[ c - 0x3000 ];
 842     else switch( c )
 843     {
 844 #if 0 // TODO: enable it for real-fixed-width fonts?
 845         case ':': case ';': case '!':
 846             if( !bVertical )
 847                 nResult = bLeft ? -1 : +1;  // 25% left and right
 848             break;
 849 #endif
 850         case 0x30FB:
 851             nResult = bLeft ? -1 : +1;      // 25% left/right/top/bottom
 852             break;
 853         case 0x2019: case 0x201D:
 854         case 0xFF01: case 0xFF09: case 0xFF0C:
 855         case 0xFF1A: case 0xFF1B:
 856             nResult = -2;
 857             break;
 858         case 0x2018: case 0x201C:
 859         case 0xFF08:
 860             nResult = +2;
 861             break;
 862         default:
 863             break;
 864     }
 865
 866     return nResult;
 867 }
 868
 869 // -----------------------------------------------------------------------
 870
 871 bool SalLayout::GetOutline( SalGraphics& rSalGraphics,
 872     ::basegfx::B2DPolyPolygonVector& rVector ) const
 873 {
 874     bool bAllOk = true;
 875     bool bOneOk = false;
 876
 877     Point aPos;
 878     ::basegfx::B2DPolyPolygon aGlyphOutline;
 879     for( int nStart = 0;;)
 880     {
 881         sal_GlyphId nLGlyph;
 882         if( !GetNextGlyphs( 1, &nLGlyph, aPos, nStart ) )
 883             break;
 884
 885         // get outline of individual glyph, ignoring "empty" glyphs
 886         bool bSuccess = rSalGraphics.GetGlyphOutline( nLGlyph, aGlyphOutline );
 887         bAllOk &= bSuccess;
 888         bOneOk |= bSuccess;
 889         // only add non-empty outlines
 890         if( bSuccess && (aGlyphOutline.count() > 0) )
 891         {
 892             if( aPos.X() || aPos.Y() )
 893             {
 894                 ::basegfx::B2DHomMatrix aMatrix;
 895         aMatrix.translate( aPos.X(), aPos.Y() );
 896         aGlyphOutline.transform( aMatrix );
 897         }
 898
 899             // insert outline at correct position
 900             rVector.push_back( aGlyphOutline );
 901         }
 902     }
 903
 904     return (bAllOk & bOneOk);
 905 }
 906
 907 // -----------------------------------------------------------------------
 908
 909 bool SalLayout::GetBoundRect( SalGraphics& rSalGraphics, Rectangle& rRect ) const
 910 {
 911     bool bRet = false;
 912     rRect.SetEmpty();
 913
 914     Point aPos;
 915     Rectangle aRectangle;
 916     for( int nStart = 0;;)
 917     {
 918         sal_GlyphId nLGlyph;
 919         if( !GetNextGlyphs( 1, &nLGlyph, aPos, nStart ) )
 920             break;
 921
 922         // get bounding rectangle of individual glyph
 923         if( rSalGraphics.GetGlyphBoundRect( nLGlyph, aRectangle ) )
 924         {
 925             // merge rectangle
 926             aRectangle += aPos;
 927             rRect.Union( aRectangle );
 928             bRet = true;
 929         }
 930     }
 931
 932     return bRet;
 933 }
 934
 935 // -----------------------------------------------------------------------
 936
 937 bool SalLayout::IsSpacingGlyph( sal_GlyphId nGlyph ) const
 938 {
 939     bool bRet = false;
 940     if( nGlyph & GF_ISCHAR )
 941     {
 942         long nChar = nGlyph & GF_IDXMASK;
 943         bRet = (nChar <= 0x0020)                    // blank
 944             //|| (nChar == 0x00A0)                  // non breaking space
 945             || (nChar >= 0x2000 && nChar <= 0x200F) // whitespace
 946             || (nChar == 0x3000);                   // ideographic space
 947     }
 948     else
 949         bRet = ((nGlyph & GF_IDXMASK) == 3);
 950     return bRet;
 951 }
 952
 953 // -----------------------------------------------------------------------
 954
 955 const ImplFontData* SalLayout::GetFallbackFontData( sal_GlyphId /*nGlyphId*/ ) const
 956 {
 957 #if 0
 958     int nFallbackLevel = (nGlyphId & GF_FONTMASK) >> GF_FONTSHIFT
 959     assert( nFallbackLevel == 0 );
 960 #endif
 961     return NULL;
 962 }
 963
 964 // =======================================================================
 965
 966 GenericSalLayout::GenericSalLayout()
 967 :   mpGlyphItems(0),
 968     mnGlyphCount(0),
 969     mnGlyphCapacity(0)
 970 {}
 971
 972 // -----------------------------------------------------------------------
 973
 974 GenericSalLayout::~GenericSalLayout()
 975 {
 976     delete[] mpGlyphItems;
 977 }
 978
 979 // -----------------------------------------------------------------------
 980
 981 void GenericSalLayout::AppendGlyph( const GlyphItem& rGlyphItem )
 982 {
 983     // TODO: use std::list<GlyphItem>
 984     if( mnGlyphCount >= mnGlyphCapacity )
 985     {
 986         mnGlyphCapacity += 16 + 3 * mnGlyphCount;
 987         GlyphItem* pNewGI = new GlyphItem[ mnGlyphCapacity ];
 988         if( mpGlyphItems )
 989         {
 990             for( int i = 0; i < mnGlyphCount; ++i )
 991                 pNewGI[ i ] = mpGlyphItems[ i ];
 992             delete[] mpGlyphItems;
 993         }
 994         mpGlyphItems = pNewGI;
 995     }
 996
 997     mpGlyphItems[ mnGlyphCount++ ] = rGlyphItem;
 998 }
 999
1000 // -----------------------------------------------------------------------
1001
1002 bool GenericSalLayout::GetCharWidths( sal_Int32* pCharWidths ) const
1003 {
1004     // initialize character extents buffer
1005     int nCharCount = mnEndCharPos - mnMinCharPos;
1006     for( int n = 0; n < nCharCount; ++n )
1007         pCharWidths[n] = 0;
1008
1009     // determine cluster extents
1010     const GlyphItem* const pEnd = mpGlyphItems + mnGlyphCount;
1011     for( const GlyphItem* pG = mpGlyphItems; pG < pEnd; ++pG )
1012     {
1013         // use cluster start to get char index
1014         if( !pG->IsClusterStart() )
1015             continue;
1016
1017         int n = pG->mnCharPos;
1018         if( n >= mnEndCharPos )
1019             continue;
1020         n -= mnMinCharPos;
1021         if( n < 0 )
1022             continue;
1023
1024         // left glyph in cluster defines default extent
1025         long nXPosMin = pG->maLinearPos.X();
1026         long nXPosMax = nXPosMin + pG->mnNewWidth;
1027
1028         // calculate right x-position for this glyph cluster
1029         // break if no more glyphs in layout
1030         // break at next glyph cluster start
1031         while( (pG+1 < pEnd) && !pG[1].IsClusterStart() )
1032         {
1033             // advance to next glyph in cluster
1034             ++pG;
1035
1036             if( pG->IsDiacritic() )
1037                 continue; // ignore diacritics
1038             // get leftmost x-extent of this glyph
1039             long nXPos = pG->maLinearPos.X();
1040             if( nXPosMin > nXPos )
1041                 nXPosMin = nXPos;
1042
1043             // get rightmost x-extent of this glyph
1044             nXPos += pG->mnNewWidth;
1045             if( nXPosMax < nXPos )
1046                 nXPosMax = nXPos;
1047         }
1048
1049         // when the current cluster overlaps with the next one assume
1050         // rightmost cluster edge is the leftmost edge of next cluster
1051         // for clusters that do not have x-sorted glyphs
1052         // TODO: avoid recalculation of left bound in next cluster iteration
1053         for( const GlyphItem* pN = pG; ++pN < pEnd; )
1054         {
1055             if( pN->IsClusterStart() )
1056                 break;
1057             if( pN->IsDiacritic() )
1058                 continue;       // ignore diacritics
1059             if( nXPosMax > pN->maLinearPos.X() )
1060                 nXPosMax = pN->maLinearPos.X();
1061         }
1062         if( nXPosMax < nXPosMin )
1063             nXPosMin = nXPosMax = 0;
1064
1065         // character width is sum of glyph cluster widths
1066         pCharWidths[n] += nXPosMax - nXPosMin;
1067     }
1068
1069     // TODO: distribute the cluster width proportionally to the characters
1070     // clusters (e.g. ligatures) correspond to more than one char index,
1071     // so some character widths are still uninitialized. This is solved
1072     // by setting the first charwidth of the cluster to the cluster width
1073
1074     return true;
1075 }
1076
1077 // -----------------------------------------------------------------------
1078
1079 long GenericSalLayout::FillDXArray( sal_Int32* pCharWidths ) const
1080 {
1081     if( pCharWidths )
1082         if( !GetCharWidths( pCharWidths ) )
1083             return 0;
1084
1085     long nWidth = GetTextWidth();
1086     return nWidth;
1087 }
1088
1089 // -----------------------------------------------------------------------
1090
1091 // the text width is the maximum logical extent of all glyphs
1092 long GenericSalLayout::GetTextWidth() const
1093 {
1094     if( mnGlyphCount <= 0 )
1095         return 0;
1096
1097     // initialize the extent
1098     long nMinPos = 0;
1099     long nMaxPos = 0;
1100
1101     const GlyphItem* pG = mpGlyphItems;
1102     for( int i = mnGlyphCount; --i >= 0; ++pG )
1103     {
1104         // update the text extent with the glyph extent
1105         long nXPos = pG->maLinearPos.X();
1106         if( nMinPos > nXPos )
1107             nMinPos = nXPos;
1108         nXPos += pG->mnNewWidth;
1109         if( nMaxPos < nXPos )
1110             nMaxPos = nXPos;
1111     }
1112
1113     long nWidth = nMaxPos - nMinPos;
1114     return nWidth;
1115 }
1116
1117 // -----------------------------------------------------------------------
1118
1119 void GenericSalLayout::AdjustLayout( ImplLayoutArgs& rArgs )
1120 {
1121     SalLayout::AdjustLayout( rArgs );
1122
1123     if( rArgs.mpDXArray )
1124         ApplyDXArray( rArgs );
1125     else if( rArgs.mnLayoutWidth )
1126         Justify( rArgs.mnLayoutWidth );
1127 }
1128
1129 // -----------------------------------------------------------------------
1130
1131 void GenericSalLayout::ApplyDXArray( ImplLayoutArgs& rArgs )
1132 {
1133     if( mnGlyphCount <= 0 )
1134         return;
1135
1136     // determine cluster boundaries and x base offset
1137     const int nCharCount = rArgs.mnEndCharPos - rArgs.mnMinCharPos;
1138     int* pLogCluster = (int*)alloca( nCharCount * sizeof(int) );
1139     int i, n;
1140     long nBasePointX = -1;
1141     if( mnLayoutFlags & SAL_LAYOUT_FOR_FALLBACK )
1142         nBasePointX = 0;
1143     for( i = 0; i < nCharCount; ++i )
1144         pLogCluster[ i ] = -1;
1145     GlyphItem* pG = mpGlyphItems;
1146     for( i = 0; i < mnGlyphCount; ++i, ++pG )
1147     {
1148         n = pG->mnCharPos - rArgs.mnMinCharPos;
1149         if( (n < 0) || (nCharCount <= n) )
1150             continue;
1151         if( pLogCluster[ n ] < 0 )
1152             pLogCluster[ n ] = i;
1153         if( nBasePointX < 0 )
1154             nBasePointX = pG->maLinearPos.X();
1155     }
1156     // retarget unresolved pLogCluster[n] to a glyph inside the cluster
1157     // TODO: better do it while the deleted-glyph markers are still there
1158     for( n = 0; n < nCharCount; ++n )
1159         if( (i = pLogCluster[0]) >= 0 )
1160             break;
1161     if( n >= nCharCount )
1162         return;
1163     for( n = 0; n < nCharCount; ++n )
1164     {
1165         if( pLogCluster[ n ] < 0 )
1166             pLogCluster[ n ] = i;
1167         else
1168             i = pLogCluster[ n ];
1169     }
1170
1171     // calculate adjusted cluster widths
1172     sal_Int32* pNewGlyphWidths = (sal_Int32*)alloca( mnGlyphCount * sizeof(long) );
1173     for( i = 0; i < mnGlyphCount; ++i )
1174         pNewGlyphWidths[ i ] = 0;
1175
1176     bool bRTL;
1177     for( int nCharPos = i = -1; rArgs.GetNextPos( &nCharPos, &bRTL ); )
1178     {
1179         n = nCharPos - rArgs.mnMinCharPos;
1180         if( (n < 0) || (nCharCount <= n) )  continue;
1181
1182         if( pLogCluster[ n ] >= 0 )
1183             i = pLogCluster[ n ];
1184         if( i >= 0 )
1185         {
1186             long nDelta = rArgs.mpDXArray[ n ] ;
1187             if( n > 0 )
1188                 nDelta -= rArgs.mpDXArray[ n-1 ];
1189             pNewGlyphWidths[ i ] += nDelta * mnUnitsPerPixel;
1190         }
1191     }
1192
1193     // move cluster positions using the adjusted widths
1194     long nDelta = 0;
1195     long nNewPos = 0;
1196     pG = mpGlyphItems;
1197     for( i = 0; i < mnGlyphCount; ++i, ++pG )
1198     {
1199         if( pG->IsClusterStart() )
1200         {
1201             // calculate original and adjusted cluster width
1202             int nOldClusterWidth = pG->mnNewWidth;
1203             int nNewClusterWidth = pNewGlyphWidths[i];
1204             GlyphItem* pClusterG = pG + 1;
1205             for( int j = i; ++j < mnGlyphCount; ++pClusterG )
1206             {
1207                 if( pClusterG->IsClusterStart() )
1208                     break;
1209                 if( !pClusterG->IsDiacritic() ) // #i99367# ignore diacritics
1210                     nOldClusterWidth += pClusterG->mnNewWidth;
1211                 nNewClusterWidth += pNewGlyphWidths[j];
1212             }
1213             const int nDiff = nNewClusterWidth - nOldClusterWidth;
1214
1215             // adjust cluster glyph widths and positions
1216             nDelta = nBasePointX + (nNewPos - pG->maLinearPos.X());
1217             if( !pG->IsRTLGlyph() )
1218             {
1219                 // for LTR case extend rightmost glyph in cluster
1220                 pClusterG[-1].mnNewWidth += nDiff;
1221             }
1222             else
1223             {
1224                 // right align cluster in new space for RTL case
1225                 pG->mnNewWidth += nDiff;
1226                 nDelta += nDiff;
1227             }
1228
1229             nNewPos += nNewClusterWidth;
1230         }
1231
1232         pG->maLinearPos.X() += nDelta;
1233     }
1234 }
1235
1236 // -----------------------------------------------------------------------
1237
1238 void GenericSalLayout::Justify( long nNewWidth )
1239 {
1240     nNewWidth *= mnUnitsPerPixel;
1241     int nOldWidth = GetTextWidth();
1242     if( !nOldWidth || nNewWidth==nOldWidth )
1243         return;
1244
1245     // find rightmost glyph, it won't get stretched
1246     GlyphItem* pGRight = mpGlyphItems + mnGlyphCount - 1;
1247
1248     // count stretchable glyphs
1249     GlyphItem* pG;
1250     int nStretchable = 0;
1251     int nMaxGlyphWidth = 0;
1252     for( pG = mpGlyphItems; pG < pGRight; ++pG )
1253     {
1254         if( !pG->IsDiacritic() )
1255             ++nStretchable;
1256         if( nMaxGlyphWidth < pG->mnOrigWidth )
1257             nMaxGlyphWidth = pG->mnOrigWidth;
1258     }
1259
1260     // move rightmost glyph to requested position
1261     nOldWidth -= pGRight->mnOrigWidth;
1262     if( nOldWidth <= 0 )
1263         return;
1264     if( nNewWidth < nMaxGlyphWidth)
1265         nNewWidth = nMaxGlyphWidth;
1266     nNewWidth -= pGRight->mnOrigWidth;
1267     pGRight->maLinearPos.X() = maBasePoint.X() + nNewWidth;
1268
1269     // justify glyph widths and positions
1270     int nDiffWidth = nNewWidth - nOldWidth;
1271     if( nDiffWidth >= 0) // expanded case
1272     {
1273         // expand width by distributing space between glyphs evenly
1274         int nDeltaSum = 0;
1275         for( pG = mpGlyphItems; pG < pGRight; ++pG )
1276         {
1277             // move glyph to justified position
1278             pG->maLinearPos.X() += nDeltaSum;
1279
1280             // do not stretch non-stretchable glyphs
1281             if( pG->IsDiacritic() || (nStretchable <= 0) )
1282                 continue;
1283
1284             // distribute extra space equally to stretchable glyphs
1285             int nDeltaWidth = nDiffWidth / nStretchable--;
1286             nDiffWidth     -= nDeltaWidth;
1287             pG->mnNewWidth += nDeltaWidth;
1288             nDeltaSum      += nDeltaWidth;
1289         }
1290     }
1291     else // condensed case
1292     {
1293         // squeeze width by moving glyphs proportionally
1294         double fSqueeze = (double)nNewWidth / nOldWidth;
1295         for( pG = mpGlyphItems; ++pG < pGRight;)
1296         {
1297             int nX = pG->maLinearPos.X() - maBasePoint.X();
1298             nX = (int)(nX * fSqueeze);
1299             pG->maLinearPos.X() = nX + maBasePoint.X();
1300         }
1301         // adjust glyph widths to new positions
1302         for( pG = mpGlyphItems; pG < pGRight; ++pG )
1303             pG->mnNewWidth = pG[1].maLinearPos.X() - pG[0].maLinearPos.X();
1304     }
1305 }
1306
1307 // -----------------------------------------------------------------------
1308
1309 void GenericSalLayout::ApplyAsianKerning( const sal_Unicode* pStr, int nLength )
1310 {
1311     long nOffset = 0;
1312
1313     GlyphItem* pGEnd = mpGlyphItems + mnGlyphCount;
1314     for( GlyphItem* pG = mpGlyphItems; pG < pGEnd; ++pG )
1315     {
1316         const int n = pG->mnCharPos;
1317         if( n < nLength - 1)
1318         {
1319             // ignore code ranges that are not affected by asian punctuation compression
1320             const sal_Unicode cHere = pStr[n];
1321             if( ((0x3000 != (cHere & 0xFF00)) && (0x2010 != (cHere & 0xFFF0))) || (0xFF00 != (cHere & 0xFF00)) )
1322                 continue;
1323             const sal_Unicode cNext = pStr[n+1];
1324             if( ((0x3000 != (cNext & 0xFF00)) && (0x2010 != (cNext & 0xFFF0))) || (0xFF00 != (cNext & 0xFF00)) )
1325                 continue;
1326
1327             // calculate compression values
1328             const bool bVertical = false;
1329             long nKernFirst = +CalcAsianKerning( cHere, true, bVertical );
1330             long nKernNext  = -CalcAsianKerning( cNext, false, bVertical );
1331
1332             // apply punctuation compression to logical glyph widths
1333             long nDelta = (nKernFirst < nKernNext) ? nKernFirst : nKernNext;
1334             if( nDelta<0 && nKernFirst!=0 && nKernNext!=0 )
1335             {
1336                 int nGlyphWidth = pG->mnOrigWidth;
1337                 nDelta = (nDelta * nGlyphWidth + 2) / 4;
1338                 if( pG+1 == pGEnd )
1339                     pG->mnNewWidth += nDelta;
1340                 nOffset += nDelta;
1341             }
1342         }
1343
1344         // adjust the glyph positions to the new glyph widths
1345         if( pG+1 != pGEnd )
1346             pG->maLinearPos.X() += nOffset;
1347     }
1348 }
1349
1350 // -----------------------------------------------------------------------
1351
1352 void GenericSalLayout::KashidaJustify( long nKashidaIndex, int nKashidaWidth )
1353 {
1354     // TODO: reimplement method when container type for GlyphItems changes
1355
1356     // skip if the kashida glyph in the font looks suspicious
1357     if( nKashidaWidth <= 0 )
1358         return;
1359
1360     // calculate max number of needed kashidas
1361     const GlyphItem* pG1 = mpGlyphItems;
1362     int nKashidaCount = 0, i;
1363     for( i = 0; i < mnGlyphCount; ++i, ++pG1 )
1364     {
1365         // only inject kashidas in RTL contexts
1366         if( !pG1->IsRTLGlyph() )
1367             continue;
1368         // no kashida-injection for blank justified expansion either
1369         if( IsSpacingGlyph( pG1->mnGlyphIndex ) )
1370             continue;
1371
1372         // calculate gap, ignore if too small
1373         const int nGapWidth = pG1->mnNewWidth - pG1->mnOrigWidth;
1374         // worst case is one kashida even for mini-gaps
1375         if( 3 * nGapWidth >= nKashidaWidth )
1376             nKashidaCount += 1 + (nGapWidth / nKashidaWidth);
1377     }
1378
1379     if( !nKashidaCount )
1380         return;
1381
1382     // reallocate glyph array for additional kashidas
1383     // TODO: reuse array if additional glyphs would fit
1384     mnGlyphCapacity = mnGlyphCount + nKashidaCount;
1385     GlyphItem* pNewGlyphItems = new GlyphItem[ mnGlyphCapacity ];
1386     GlyphItem* pG2 = pNewGlyphItems;
1387     pG1 = mpGlyphItems;
1388     for( i = mnGlyphCount; --i >= 0; ++pG1, ++pG2 )
1389     {
1390         // default action is to copy array element
1391         *pG2 = *pG1;
1392
1393         // only inject kashida in RTL contexts
1394         if( !pG1->IsRTLGlyph() )
1395             continue;
1396         // no kashida-injection for blank justified expansion either
1397         if( IsSpacingGlyph( pG1->mnGlyphIndex ) )
1398             continue;
1399
1400         // calculate gap, skip if too small
1401         int nGapWidth = pG1->mnNewWidth - pG1->mnOrigWidth;
1402         if( 3*nGapWidth < nKashidaWidth )
1403             continue;
1404
1405         // fill gap with kashidas
1406         nKashidaCount = 0;
1407         Point aPos = pG1->maLinearPos;
1408         aPos.X() -= nGapWidth; // cluster is already right aligned
1409         for(; nGapWidth > 0; nGapWidth -= nKashidaWidth, ++nKashidaCount )
1410         {
1411             *(pG2++) = GlyphItem( pG1->mnCharPos, nKashidaIndex, aPos,
1412                 GlyphItem::IS_IN_CLUSTER|GlyphItem::IS_RTL_GLYPH, nKashidaWidth );
1413             aPos.X() += nKashidaWidth;
1414         }
1415
1416         // fixup rightmost kashida for gap remainder
1417         if( nGapWidth < 0 )
1418         {
1419             aPos.X() += nGapWidth;
1420             if( nKashidaCount <= 1 )
1421                 nGapWidth /= 2;               // for small gap move kashida to middle
1422             pG2[-1].mnNewWidth += nGapWidth;  // adjust kashida width to gap width
1423             pG2[-1].maLinearPos.X() += nGapWidth;
1424         }
1425
1426         // when kashidas were inserted move the original cluster
1427         // to the right and shrink it to it's original width
1428         *pG2 = *pG1;
1429         pG2->maLinearPos.X() = aPos.X();
1430         pG2->mnNewWidth = pG2->mnOrigWidth;
1431      }
1432
1433     // use the new glyph array
1434     DBG_ASSERT( mnGlyphCapacity >= pG2-pNewGlyphItems, "KashidaJustify overflow" );
1435     delete[] mpGlyphItems;
1436     mpGlyphItems = pNewGlyphItems;
1437     mnGlyphCount = pG2 - pNewGlyphItems;
1438 }
1439
1440 // -----------------------------------------------------------------------
1441
1442 void GenericSalLayout::GetCaretPositions( int nMaxIndex, sal_Int32* pCaretXArray ) const
1443 {
1444     // initialize result array
1445     long nXPos = -1;
1446     int i;
1447     for( i = 0; i < nMaxIndex; ++i )
1448         pCaretXArray[ i ] = nXPos;
1449
1450     // calculate caret positions using glyph array
1451     const GlyphItem* pG = mpGlyphItems;
1452     for( i = mnGlyphCount; --i >= 0; ++pG )
1453     {
1454         nXPos = pG->maLinearPos.X();
1455         long nXRight = nXPos + pG->mnOrigWidth;
1456         int n = pG->mnCharPos;
1457         int nCurrIdx = 2 * (n - mnMinCharPos);
1458         if( !pG->IsRTLGlyph() )
1459         {
1460             // normal positions for LTR case
1461             pCaretXArray[ nCurrIdx ]   = nXPos;
1462             pCaretXArray[ nCurrIdx+1 ] = nXRight;
1463         }
1464         else
1465         {
1466             // reverse positions for RTL case
1467             pCaretXArray[ nCurrIdx ]   = nXRight;
1468             pCaretXArray[ nCurrIdx+1 ] = nXPos;
1469         }
1470     }
1471 }
1472
1473 // -----------------------------------------------------------------------
1474
1475 int GenericSalLayout::GetTextBreak( long nMaxWidth, long nCharExtra, int nFactor ) const
1476 {
1477     int nCharCapacity = mnEndCharPos - mnMinCharPos;
1478     sal_Int32* pCharWidths = (sal_Int32*)alloca( nCharCapacity * sizeof(sal_Int32) );
1479     if( !GetCharWidths( pCharWidths ) )
1480         return STRING_LEN;
1481
1482     long nWidth = 0;
1483     for( int i = mnMinCharPos; i < mnEndCharPos; ++i )
1484     {
1485         nWidth += pCharWidths[ i - mnMinCharPos ] * nFactor;
1486         if( nWidth >= nMaxWidth )
1487             return i;
1488         nWidth += nCharExtra;
1489     }
1490
1491     return STRING_LEN;
1492 }
1493
1494 // -----------------------------------------------------------------------
1495
1496 int GenericSalLayout::GetNextGlyphs( int nLen, sal_GlyphId* pGlyphs, Point& rPos,
1497     int& nStart, sal_Int32* pGlyphAdvAry, int* pCharPosAry ) const
1498 {
1499     const GlyphItem* pG = mpGlyphItems + nStart;
1500
1501     // find next glyph in substring
1502     for(; nStart < mnGlyphCount; ++nStart, ++pG )
1503     {
1504         int n = pG->mnCharPos;
1505         if( (mnMinCharPos <= n) && (n < mnEndCharPos) )
1506             break;
1507     }
1508
1509     // return zero if no more glyph found
1510     if( nStart >= mnGlyphCount )
1511         return 0;
1512
1513     // calculate absolute position in pixel units
1514     Point aRelativePos = pG->maLinearPos - maBasePoint;
1515
1516     // find more glyphs which can be merged into one drawing instruction
1517     int nCount = 0;
1518     long nYPos = pG->maLinearPos.Y();
1519     long nOldFlags = pG->mnGlyphIndex;
1520     for(;;)
1521     {
1522         // update return data with glyph info
1523         ++nCount;
1524         *(pGlyphs++) = pG->mnGlyphIndex;
1525         if( pCharPosAry )
1526             *(pCharPosAry++) = pG->mnCharPos;
1527         if( pGlyphAdvAry )
1528             *pGlyphAdvAry = pG->mnNewWidth;
1529
1530         // break at end of glyph list
1531         if( ++nStart >= mnGlyphCount )
1532             break;
1533         // break when enough glyphs
1534         if( nCount >= nLen )
1535             break;
1536
1537         long nGlyphAdvance = pG[1].maLinearPos.X() - pG->maLinearPos.X();
1538         if( pGlyphAdvAry )
1539         {
1540             // override default advance width with correct value
1541             *(pGlyphAdvAry++) = nGlyphAdvance;
1542         }
1543         else
1544         {
1545             // stop when next x-position is unexpected
1546             if( pG->mnOrigWidth != nGlyphAdvance )
1547                 break;
1548         }
1549
1550         // advance to next glyph
1551         ++pG;
1552
1553         // stop when next y-position is unexpected
1554         if( nYPos != pG->maLinearPos.Y() )
1555             break;
1556
1557         // stop when no longer in string
1558         int n = pG->mnCharPos;
1559         if( (n < mnMinCharPos) || (mnEndCharPos <= n) )
1560             break;
1561
1562         // stop when glyph flags change
1563         if( (nOldFlags ^ pG->mnGlyphIndex) & GF_FLAGMASK )
1564             break;
1565
1566         nOldFlags = pG->mnGlyphIndex; // &GF_FLAGMASK not needed for test above
1567     }
1568
1569     aRelativePos.X() /= mnUnitsPerPixel;
1570     aRelativePos.Y() /= mnUnitsPerPixel;
1571     rPos = GetDrawPosition( aRelativePos );
1572
1573     return nCount;
1574 }
1575
1576 // -----------------------------------------------------------------------
1577
1578 void GenericSalLayout::MoveGlyph( int nStart, long nNewXPos )
1579 {
1580     if( nStart >= mnGlyphCount )
1581         return;
1582
1583     GlyphItem* pG = mpGlyphItems + nStart;
1584     // the nNewXPos argument determines the new cell position
1585     // as RTL-glyphs are right justified in their cell
1586     // the cell position needs to be adjusted to the glyph position
1587     if( pG->IsRTLGlyph() )
1588         nNewXPos += pG->mnNewWidth - pG->mnOrigWidth;
1589     // calculate the x-offset to the old position
1590     long nXDelta = nNewXPos - pG->maLinearPos.X();
1591     // adjust all following glyph positions if needed
1592     if( nXDelta != 0 )
1593     {
1594         GlyphItem* const pGEnd = mpGlyphItems + mnGlyphCount;
1595         for(; pG < pGEnd; ++pG )
1596             pG->maLinearPos.X() += nXDelta;
1597     }
1598 }
1599
1600 // -----------------------------------------------------------------------
1601
1602 void GenericSalLayout::DropGlyph( int nStart )
1603 {
1604     if( nStart >= mnGlyphCount )
1605         return;
1606     GlyphItem* pG = mpGlyphItems + nStart;
1607     pG->mnGlyphIndex = GF_DROPPED;
1608     pG->mnCharPos = -1;
1609 }
1610
1611 // -----------------------------------------------------------------------
1612
1613 void GenericSalLayout::Simplify( bool bIsBase )
1614 {
1615     const sal_GlyphId nDropMarker = bIsBase ? GF_DROPPED : 0;
1616
1617     // remove dropped glyphs inplace
1618     GlyphItem* pGDst = mpGlyphItems;
1619     const GlyphItem* pGSrc = mpGlyphItems;
1620     const GlyphItem* pGEnd = mpGlyphItems + mnGlyphCount;
1621     for(; pGSrc < pGEnd; ++pGSrc )
1622     {
1623         if( pGSrc->mnGlyphIndex == nDropMarker )
1624             continue;
1625         if( pGDst != pGSrc )
1626             *pGDst = *pGSrc;
1627         ++pGDst;
1628     }
1629     mnGlyphCount = pGDst - mpGlyphItems;
1630 }
1631
1632 // -----------------------------------------------------------------------
1633
1634 // make sure GlyphItems are sorted left to right
1635 void GenericSalLayout::SortGlyphItems()
1636 {
1637     // move cluster components behind their cluster start (especially for RTL)
1638     // using insertion sort because the glyph items are "almost sorted"
1639     const GlyphItem* const pGEnd = mpGlyphItems + mnGlyphCount;
1640     for( GlyphItem* pG = mpGlyphItems; pG < pGEnd; ++pG )
1641     {
1642         // find a cluster starting with a diacritic
1643         if( !pG->IsDiacritic() )
1644             continue;
1645         if( !pG->IsClusterStart() )
1646             continue;
1647         for( GlyphItem* pBaseGlyph = pG; ++pBaseGlyph < pGEnd; )
1648         {
1649             // find the base glyph matching to the misplaced diacritic
1650                if( pBaseGlyph->IsClusterStart() )
1651                    break;
1652                if( pBaseGlyph->IsDiacritic() )
1653                    continue;
1654
1655             // found the matching base glyph
1656             // => this base glyph becomes the new cluster start
1657             const GlyphItem aDiacritic = *pG;
1658             *pG = *pBaseGlyph;
1659             *pBaseGlyph = aDiacritic;
1660
1661             // update glyph flags of swapped glyphitems
1662             pG->mnFlags &= ~GlyphItem::IS_IN_CLUSTER;
1663             pBaseGlyph->mnFlags |= GlyphItem::IS_IN_CLUSTER;
1664             // prepare for checking next cluster
1665             pG = pBaseGlyph;
1666             break;
1667         }
1668     }
1669 }
1670
1671 // =======================================================================
1672
1673 MultiSalLayout::MultiSalLayout( SalLayout& rBaseLayout, const ImplFontData* pBaseFont )
1674 :   SalLayout()
1675 ,   mnLevel( 1 )
1676 ,   mbInComplete( false )
1677 {
1678     //maFallbackRuns[0].Clear();
1679     mpFallbackFonts[ 0 ] = pBaseFont;
1680     mpLayouts[ 0 ]  = &rBaseLayout;
1681     mnUnitsPerPixel = rBaseLayout.GetUnitsPerPixel();
1682 }
1683
1684 void MultiSalLayout::SetInComplete(bool bInComplete)
1685 {
1686     mbInComplete = bInComplete;
1687     maFallbackRuns[mnLevel-1] = ImplLayoutRuns();
1688 }
1689
1690 // -----------------------------------------------------------------------
1691
1692 MultiSalLayout::~MultiSalLayout()
1693 {
1694     for( int i = 0; i < mnLevel; ++i )
1695         mpLayouts[ i ]->Release();
1696 }
1697
1698 // -----------------------------------------------------------------------
1699
1700 bool MultiSalLayout::AddFallback( SalLayout& rFallback,
1701     ImplLayoutRuns& rFallbackRuns, const ImplFontData* pFallbackFont )
1702 {
1703     if( mnLevel >= MAX_FALLBACK )
1704         return false;
1705
1706     mpFallbackFonts[ mnLevel ]  = pFallbackFont;
1707     mpLayouts[ mnLevel ]        = &rFallback;
1708     maFallbackRuns[ mnLevel-1 ] = rFallbackRuns;
1709     ++mnLevel;
1710     return true;
1711 }
1712
1713 // -----------------------------------------------------------------------
1714
1715 bool MultiSalLayout::LayoutText( ImplLayoutArgs& rArgs )
1716 {
1717     if( mnLevel <= 1 )
1718         return false;
1719     if (!mbInComplete)
1720         maFallbackRuns[ mnLevel-1 ] = rArgs.maRuns;
1721     return true;
1722 }
1723
1724 // -----------------------------------------------------------------------
1725
1726 void MultiSalLayout::AdjustLayout( ImplLayoutArgs& rArgs )
1727 {
1728     SalLayout::AdjustLayout( rArgs );
1729     ImplLayoutArgs aMultiArgs = rArgs;
1730
1731     if( !rArgs.mpDXArray && rArgs.mnLayoutWidth )
1732     {
1733         // for stretched text in a MultiSalLayout the target width needs to be
1734         // distributed by individually adjusting its virtual character widths
1735         long nTargetWidth = aMultiArgs.mnLayoutWidth;
1736         nTargetWidth *= mnUnitsPerPixel; // convert target width to base font units
1737         aMultiArgs.mnLayoutWidth = 0;
1738
1739         // we need to get the original unmodified layouts ready
1740         for( int n = 0; n < mnLevel; ++n )
1741             mpLayouts[n]->SalLayout::AdjustLayout( aMultiArgs );
1742         // then we can measure the unmodified metrics
1743         int nCharCount = rArgs.mnEndCharPos - rArgs.mnMinCharPos;
1744         sal_Int32* pJustificationArray = (sal_Int32*)alloca( nCharCount * sizeof(sal_Int32) );
1745         FillDXArray( pJustificationArray );
1746         // #i17359# multilayout is not simplified yet, so calculating the
1747         // unjustified width needs handholding; also count the number of
1748         // stretchable virtual char widths
1749         long nOrigWidth = 0;
1750         int nStretchable = 0;
1751         for( int i = 0; i < nCharCount; ++i )
1752         {
1753             // convert array from widths to sum of widths
1754             nOrigWidth += pJustificationArray[i];
1755             if( pJustificationArray[i] > 0 )
1756                 ++nStretchable;
1757         }
1758
1759         // now we are able to distribute the extra width over the virtual char widths
1760         if( nOrigWidth && (nTargetWidth != nOrigWidth) )
1761         {
1762             int nDiffWidth = nTargetWidth - nOrigWidth;
1763             int nWidthSum = 0;
1764             for( int i = 0; i < nCharCount; ++i )
1765             {
1766                 int nJustWidth = pJustificationArray[i];
1767                 if( (nJustWidth > 0) && (nStretchable > 0) )
1768                 {
1769                     int nDeltaWidth = nDiffWidth / nStretchable;
1770                     nJustWidth += nDeltaWidth;
1771                     nDiffWidth -= nDeltaWidth;
1772                     --nStretchable;
1773                 }
1774                 nWidthSum += nJustWidth;
1775                 pJustificationArray[i] = nWidthSum;
1776             }
1777             if( nWidthSum != nTargetWidth )
1778                 pJustificationArray[ nCharCount-1 ] = nTargetWidth;
1779
1780             // the justification array is still in base level units
1781             // => convert it to pixel units
1782             if( mnUnitsPerPixel > 1 )
1783             {
1784                 for( int i = 0; i < nCharCount; ++i )
1785                 {
1786                     sal_Int32 nVal = pJustificationArray[ i ];
1787                     nVal += (mnUnitsPerPixel + 1) / 2;
1788                     pJustificationArray[ i ] = nVal / mnUnitsPerPixel;
1789                 }
1790             }
1791
1792             // change the mpDXArray temporarilly (just for the justification)
1793             aMultiArgs.mpDXArray = pJustificationArray;
1794         }
1795     }
1796
1797     // Compute rtl flags, since in some scripts glyphs/char order can be
1798     // reversed for a few character sequencies e.g. Myanmar
1799     std::vector<bool> vRtl(rArgs.mnEndCharPos - rArgs.mnMinCharPos, false);
1800     rArgs.ResetPos();
1801     bool bRtl;
1802     int nRunStart, nRunEnd;
1803     while (rArgs.GetNextRun(&nRunStart, &nRunEnd, &bRtl))
1804     {
1805         if (bRtl) std::fill(vRtl.begin() + nRunStart - rArgs.mnMinCharPos,
1806                             vRtl.begin() + nRunEnd - rArgs.mnMinCharPos, true);
1807     }
1808     rArgs.ResetPos();
1809
1810     // prepare "merge sort"
1811     int nStartOld[ MAX_FALLBACK ];
1812     int nStartNew[ MAX_FALLBACK ];
1813     int nCharPos[ MAX_FALLBACK ];
1814     sal_Int32 nGlyphAdv[ MAX_FALLBACK ];
1815     int nValid[ MAX_FALLBACK ] = {0};
1816
1817     sal_GlyphId nDummy;
1818     Point aPos;
1819     int nLevel = 0, n;
1820     for( n = 0; n < mnLevel; ++n )
1821     {
1822         // now adjust the individual components
1823         if( n > 0 )
1824         {
1825             aMultiArgs.maRuns = maFallbackRuns[ n-1 ];
1826             aMultiArgs.mnFlags |= SAL_LAYOUT_FOR_FALLBACK;
1827         }
1828         mpLayouts[n]->AdjustLayout( aMultiArgs );
1829
1830         // disable glyph-injection for glyph-fallback SalLayout iteration
1831         mpLayouts[n]->DisableGlyphInjection( true );
1832
1833         // remove unused parts of component
1834         if( n > 0 )
1835         {
1836             if (mbInComplete && (n == mnLevel-1))
1837                 mpLayouts[n]->Simplify( true );
1838             else
1839                 mpLayouts[n]->Simplify( false );
1840         }
1841
1842         // prepare merging components
1843         nStartNew[ nLevel ] = nStartOld[ nLevel ] = 0;
1844         nValid[ nLevel ] = mpLayouts[n]->GetNextGlyphs( 1, &nDummy, aPos,
1845             nStartNew[ nLevel ], &nGlyphAdv[ nLevel ], &nCharPos[ nLevel ] );
1846 #ifdef MULTI_SL_DEBUG
1847         if (nValid[nLevel]) fprintf(mslLog(), "layout[%d]->GetNextGlyphs %d,%d x%d a%d c%d %x\n", n, nStartOld[nLevel], nStartNew[nLevel], aPos.X(), nGlyphAdv[nLevel], nCharPos[nLevel],
1848             rArgs.mpStr[nCharPos[nLevel]]);
1849 #endif
1850         if( (n > 0) && !nValid[ nLevel ] )
1851         {
1852             // an empty fallback layout can be released
1853             mpLayouts[n]->Release();
1854         }
1855         else
1856         {
1857             // reshuffle used fallbacks if needed
1858             if( nLevel != n )
1859             {
1860                 mpLayouts[ nLevel ]         = mpLayouts[ n ];
1861                 mpFallbackFonts[ nLevel ]   = mpFallbackFonts[ n ];
1862                 maFallbackRuns[ nLevel ]    = maFallbackRuns[ n ];
1863             }
1864             ++nLevel;
1865         }
1866     }
1867     mnLevel = nLevel;
1868
1869     // merge the fallback levels
1870     long nXPos = 0;
1871     double fUnitMul = 1.0;
1872     for( n = 0; n < nLevel; ++n )
1873         maFallbackRuns[n].ResetPos();
1874     int nActiveCharPos = nCharPos[0];
1875     int nLastRunEndChar = (vRtl[nActiveCharPos - mnMinCharPos])?
1876         rArgs.mnEndCharPos : rArgs.mnMinCharPos - 1;
1877     int nRunVisibleEndChar = nCharPos[0];
1878     while( nValid[0] && (nLevel > 0))
1879     {
1880         // find best fallback level
1881         for( n = 0; n < nLevel; ++n )
1882             if( nValid[n] && !maFallbackRuns[n].PosIsInAnyRun( nActiveCharPos ) )
1883                 // fallback level n wins when it requested no further fallback
1884                 break;
1885         int nFBLevel = n;
1886
1887         if( n < nLevel )
1888         {
1889             // use base(n==0) or fallback(n>=1) level
1890             fUnitMul = mnUnitsPerPixel;
1891             fUnitMul /= mpLayouts[n]->GetUnitsPerPixel();
1892             long nNewPos = static_cast<long>(nXPos/fUnitMul + 0.5);
1893             mpLayouts[n]->MoveGlyph( nStartOld[n], nNewPos );
1894         }
1895         else
1896         {
1897             n = 0;  // keep NotDef in base level
1898             fUnitMul = 1.0;
1899         }
1900
1901         if( n > 0 )
1902         {
1903             // drop the NotDef glyphs in the base layout run if a fallback run exists
1904             while (
1905                     (maFallbackRuns[ n-1 ].PosIsInRun( nCharPos[0] ) ) &&
1906                     (!maFallbackRuns[ n ].PosIsInAnyRun( nCharPos[0] ) )
1907                   )
1908             {
1909                 mpLayouts[0]->DropGlyph( nStartOld[0] );
1910                 nStartOld[0] = nStartNew[0];
1911                 nValid[0] = mpLayouts[0]->GetNextGlyphs( 1, &nDummy, aPos,
1912                     nStartNew[0], &nGlyphAdv[0], &nCharPos[0] );
1913 #ifdef MULTI_SL_DEBUG
1914                 if (nValid[0]) fprintf(mslLog(), "layout[0]->GetNextGlyphs %d,%d x%d a%d c%d %x\n", nStartOld[0], nStartNew[0], aPos.X(), nGlyphAdv[0], nCharPos[0], rArgs.mpStr[nCharPos[0]]);
1915 #endif
1916                 if( !nValid[0] )
1917                    break;
1918             }
1919         }
1920
1921         // skip to end of layout run and calculate its advance width
1922         int nRunAdvance = 0;
1923         bool bKeepNotDef = (nFBLevel >= nLevel);
1924         for(;;)
1925         {
1926             nRunAdvance += nGlyphAdv[n];
1927
1928             // proceed to next glyph
1929             nStartOld[n] = nStartNew[n];
1930             int nOrigCharPos = nCharPos[n];
1931             nValid[n] = mpLayouts[n]->GetNextGlyphs( 1, &nDummy, aPos,
1932                 nStartNew[n], &nGlyphAdv[n], &nCharPos[n] );
1933 #ifdef MULTI_SL_DEBUG
1934             if (nValid[n]) fprintf(mslLog(), "layout[%d]->GetNextGlyphs %d,%d a%d c%d %x\n", n, nStartOld[n], nStartNew[n], nGlyphAdv[n], nCharPos[n], rArgs.mpStr[nCharPos[n]]);
1935 #endif
1936             // break after last glyph of active layout
1937             if( !nValid[n] )
1938             {
1939                 // performance optimization (when a fallback layout is no longer needed)
1940                 if( n >= nLevel-1 )
1941                     --nLevel;
1942                 break;
1943             }
1944
1945             //If the next character is one which belongs to the next level, then we
1946             //are finished here for now, and we'll pick up after the next level has
1947             //been processed
1948             if ((n+1 < nLevel) && (nCharPos[n] != nOrigCharPos))
1949             {
1950                 if (nOrigCharPos < nCharPos[n])
1951                 {
1952                     if (nCharPos[n+1] > nOrigCharPos && (nCharPos[n+1] < nCharPos[n]))
1953                         break;
1954                 }
1955                 else if (nOrigCharPos > nCharPos[n])
1956                 {
1957                     if (nCharPos[n+1] > nCharPos[n] && (nCharPos[n+1] < nOrigCharPos))
1958                         break;
1959                 }
1960             }
1961
1962             // break at end of layout run
1963             if( n > 0 )
1964             {
1965                 // skip until end of fallback run
1966                 if( !maFallbackRuns[n-1].PosIsInRun( nCharPos[n] ) )
1967                     break;
1968             }
1969             else
1970             {
1971                 // break when a fallback is needed and available
1972                 bool bNeedFallback = maFallbackRuns[0].PosIsInRun( nCharPos[0] );
1973                 if( bNeedFallback )
1974                     if( !maFallbackRuns[ nLevel-1 ].PosIsInRun( nCharPos[0] ) )
1975                         break;
1976                 // break when change from resolved to unresolved base layout run
1977                 if( bKeepNotDef && !bNeedFallback )
1978                     { maFallbackRuns[0].NextRun(); break; }
1979                 bKeepNotDef = bNeedFallback;
1980             }
1981             // check for reordered glyphs
1982             if (aMultiArgs.mpDXArray &&
1983                 nRunVisibleEndChar < mnEndCharPos &&
1984                 nRunVisibleEndChar >= mnMinCharPos &&
1985                 nCharPos[n] < mnEndCharPos &&
1986                 nCharPos[n] >= mnMinCharPos)
1987             {
1988                 if (vRtl[nActiveCharPos - mnMinCharPos])
1989                 {
1990                     if (aMultiArgs.mpDXArray[nRunVisibleEndChar-mnMinCharPos]
1991                         >= aMultiArgs.mpDXArray[nCharPos[n] - mnMinCharPos])
1992                     {
1993                         nRunVisibleEndChar = nCharPos[n];
1994                     }
1995                 }
1996                 else if (aMultiArgs.mpDXArray[nRunVisibleEndChar-mnMinCharPos]
1997                          <= aMultiArgs.mpDXArray[nCharPos[n] - mnMinCharPos])
1998                 {
1999                     nRunVisibleEndChar = nCharPos[n];
2000                 }
2001             }
2002         }
2003
2004         // if a justification array is available
2005         // => use it directly to calculate the corresponding run width
2006         if( aMultiArgs.mpDXArray )
2007         {
2008             // the run advance is the width from the first char
2009             // in the run to the first char in the next run
2010             nRunAdvance = 0;
2011 #ifdef MULTI_SL_DEBUG
2012             const bool bLTR = !(vRtl[nActiveCharPos - mnMinCharPos]);//(nActiveCharPos < nCharPos[0]);
2013             int nOldRunAdv = 0;
2014             int nDXIndex = nCharPos[0] - mnMinCharPos - bLTR;
2015             if( nDXIndex >= 0 )
2016                 nOldRunAdv += aMultiArgs.mpDXArray[ nDXIndex ];
2017             nDXIndex = nActiveCharPos - mnMinCharPos - bLTR;
2018             if( nDXIndex >= 0 )
2019                 nOldRunAdv -= aMultiArgs.mpDXArray[ nDXIndex ];
2020             if( !bLTR )
2021                 nOldRunAdv = -nOldRunAdv;
2022 #endif
2023             if (vRtl[nActiveCharPos - mnMinCharPos])
2024             {
2025               if (nRunVisibleEndChar > mnMinCharPos && nRunVisibleEndChar <= mnEndCharPos)
2026                   nRunAdvance -= aMultiArgs.mpDXArray[nRunVisibleEndChar - 1 - mnMinCharPos];
2027               if (nLastRunEndChar > mnMinCharPos && nLastRunEndChar <= mnEndCharPos)
2028                   nRunAdvance += aMultiArgs.mpDXArray[nLastRunEndChar - 1 - mnMinCharPos];
2029 #ifdef MULTI_SL_DEBUG
2030               fprintf(mslLog(), "rtl visible %d-%d,%d-%d adv%d(%d)\n", nLastRunEndChar-1, nRunVisibleEndChar-1, nActiveCharPos - bLTR, nCharPos[0] - bLTR, nRunAdvance, nOldRunAdv);
2031 #endif
2032             }
2033             else
2034             {
2035                 if (nRunVisibleEndChar >= mnMinCharPos)
2036                   nRunAdvance += aMultiArgs.mpDXArray[nRunVisibleEndChar - mnMinCharPos];
2037                 if (nLastRunEndChar >= mnMinCharPos)
2038                   nRunAdvance -= aMultiArgs.mpDXArray[nLastRunEndChar - mnMinCharPos];
2039 #ifdef MULTI_SL_DEBUG
2040                 fprintf(mslLog(), "visible %d-%d,%d-%d adv%d(%d)\n", nLastRunEndChar, nRunVisibleEndChar, nActiveCharPos - bLTR, nCharPos[0] - bLTR, nRunAdvance, nOldRunAdv);
2041 #endif
2042             }
2043             nLastRunEndChar = nRunVisibleEndChar;
2044             nRunVisibleEndChar = nCharPos[0];
2045             // the requested width is still in pixel units
2046             // => convert it to base level font units
2047             nRunAdvance *= mnUnitsPerPixel;
2048         }
2049         else
2050         {
2051             // the measured width is still in fallback font units
2052             // => convert it to base level font units
2053             if( n > 0 ) // optimization: because (fUnitMul==1.0) for (n==0)
2054                 nRunAdvance = static_cast<long>(nRunAdvance*fUnitMul + 0.5);
2055         }
2056
2057         // calculate new x position (in base level units)
2058         nXPos += nRunAdvance;
2059
2060         // prepare for next fallback run
2061         nActiveCharPos = nCharPos[0];
2062         // it essential that the runs don't get ahead of themselves and in the
2063         // if( bKeepNotDef && !bNeedFallback ) statement above, the next run may
2064         // have already been reached on the base level
2065         for( int i = nFBLevel; --i >= 0;)
2066         {
2067             if (maFallbackRuns[i].GetRun(&nRunStart, &nRunEnd, &bRtl))
2068             {
2069                 if (bRtl)
2070                 {
2071                     if (nRunStart > nActiveCharPos)
2072                         maFallbackRuns[i].NextRun();
2073                 }
2074                 else
2075                 {
2076                     if (nRunEnd <= nActiveCharPos)
2077                         maFallbackRuns[i].NextRun();
2078                 }
2079             }
2080         }
2081 //            if( !maFallbackRuns[i].PosIsInRun( nActiveCharPos ) )
2082 //                maFallbackRuns[i].NextRun();
2083     }
2084
2085     mpLayouts[0]->Simplify( true );
2086
2087     // reenable glyph-injection
2088     for( n = 0; n < mnLevel; ++n )
2089         mpLayouts[n]->DisableGlyphInjection( false );
2090 }
2091
2092 // -----------------------------------------------------------------------
2093
2094 void MultiSalLayout::InitFont() const
2095 {
2096     if( mnLevel > 0 )
2097         mpLayouts[0]->InitFont();
2098 }
2099
2100 // -----------------------------------------------------------------------
2101
2102 const ImplFontData* MultiSalLayout::GetFallbackFontData( sal_GlyphId nGlyphId ) const
2103 {
2104     int nFallbackLevel = (nGlyphId & GF_FONTMASK) >> GF_FONTSHIFT;
2105     return mpFallbackFonts[ nFallbackLevel ];
2106 }
2107
2108 // -----------------------------------------------------------------------
2109
2110 void MultiSalLayout::DrawText( SalGraphics& rGraphics ) const
2111 {
2112     for( int i = mnLevel; --i >= 0; )
2113     {
2114         SalLayout& rLayout = *mpLayouts[ i ];
2115         rLayout.DrawBase() += maDrawBase;
2116         rLayout.DrawOffset() += maDrawOffset;
2117         rLayout.InitFont();
2118         rLayout.DrawText( rGraphics );
2119         rLayout.DrawOffset() -= maDrawOffset;
2120         rLayout.DrawBase() -= maDrawBase;
2121     }
2122     // NOTE: now the baselevel font is active again
2123 }
2124
2125  // -----------------------------------------------------------------------
2126
2127 int MultiSalLayout::GetTextBreak( long nMaxWidth, long nCharExtra, int nFactor ) const
2128 {
2129     if( mnLevel <= 0 )
2130         return STRING_LEN;
2131     if( mnLevel == 1 )
2132         return mpLayouts[0]->GetTextBreak( nMaxWidth, nCharExtra, nFactor );
2133
2134     int nCharCount = mnEndCharPos - mnMinCharPos;
2135     sal_Int32* pCharWidths = (sal_Int32*)alloca( 2*nCharCount * sizeof(sal_Int32) );
2136     mpLayouts[0]->FillDXArray( pCharWidths );
2137
2138     for( int n = 1; n < mnLevel; ++n )
2139     {
2140         SalLayout& rLayout = *mpLayouts[ n ];
2141         rLayout.FillDXArray( pCharWidths + nCharCount );
2142         double fUnitMul = mnUnitsPerPixel;
2143         fUnitMul /= rLayout.GetUnitsPerPixel();
2144         for( int i = 0; i < nCharCount; ++i )
2145         {
2146             long w = pCharWidths[ i + nCharCount ];
2147             w = static_cast<long>(w*fUnitMul + 0.5);
2148             pCharWidths[ i ] += w;
2149         }
2150     }
2151
2152     long nWidth = 0;
2153     for( int i = 0; i < nCharCount; ++i )
2154     {
2155         nWidth += pCharWidths[ i ] * nFactor;
2156         if( nWidth > nMaxWidth )
2157             return (i + mnMinCharPos);
2158         nWidth += nCharExtra;
2159     }
2160
2161     return STRING_LEN;
2162 }
2163
2164 // -----------------------------------------------------------------------
2165
2166 long MultiSalLayout::FillDXArray( sal_Int32* pCharWidths ) const
2167 {
2168     long nMaxWidth = 0;
2169
2170     // prepare merging of fallback levels
2171     sal_Int32* pTempWidths = NULL;
2172     const int nCharCount = mnEndCharPos - mnMinCharPos;
2173     if( pCharWidths )
2174     {
2175         for( int i = 0; i < nCharCount; ++i )
2176             pCharWidths[i] = 0;
2177         pTempWidths = (sal_Int32*)alloca( nCharCount * sizeof(sal_Int32) );
2178     }
2179
2180     for( int n = mnLevel; --n >= 0; )
2181     {
2182         // query every fallback level
2183         long nTextWidth = mpLayouts[n]->FillDXArray( pTempWidths );
2184         if( !nTextWidth )
2185             continue;
2186         // merge results from current level
2187         double fUnitMul = mnUnitsPerPixel;
2188         fUnitMul /= mpLayouts[n]->GetUnitsPerPixel();
2189         nTextWidth = static_cast<long>(nTextWidth * fUnitMul + 0.5);
2190         if( nMaxWidth < nTextWidth )
2191             nMaxWidth = nTextWidth;
2192         if( !pCharWidths )
2193             continue;
2194         // calculate virtual char widths using most probable fallback layout
2195         for( int i = 0; i < nCharCount; ++i )
2196         {
2197             // #i17359# restriction:
2198             // one char cannot be resolved from different fallbacks
2199             if( pCharWidths[i] != 0 )
2200                 continue;
2201             long nCharWidth = pTempWidths[i];
2202             if( !nCharWidth )
2203                 continue;
2204             nCharWidth = static_cast<long>(nCharWidth * fUnitMul + 0.5);
2205             pCharWidths[i] = nCharWidth;
2206         }
2207     }
2208
2209     return nMaxWidth;
2210 }
2211
2212 // -----------------------------------------------------------------------
2213
2214 void MultiSalLayout::GetCaretPositions( int nMaxIndex, sal_Int32* pCaretXArray ) const
2215 {
2216     SalLayout& rLayout = *mpLayouts[ 0 ];
2217     rLayout.GetCaretPositions( nMaxIndex, pCaretXArray );
2218
2219     if( mnLevel > 1 )
2220     {
2221         sal_Int32* pTempPos = (sal_Int32*)alloca( nMaxIndex * sizeof(sal_Int32) );
2222         for( int n = 1; n < mnLevel; ++n )
2223         {
2224             mpLayouts[ n ]->GetCaretPositions( nMaxIndex, pTempPos );
2225             double fUnitMul = mnUnitsPerPixel;
2226             fUnitMul /= mpLayouts[n]->GetUnitsPerPixel();
2227             for( int i = 0; i < nMaxIndex; ++i )
2228                 if( pTempPos[i] >= 0 )
2229                 {
2230                     long w = pTempPos[i];
2231                     w = static_cast<long>(w*fUnitMul + 0.5);
2232                     pCaretXArray[i] = w;
2233                 }
2234         }
2235     }
2236 }
2237
2238 // -----------------------------------------------------------------------
2239
2240 int MultiSalLayout::GetNextGlyphs( int nLen, sal_GlyphId* pGlyphIdxAry, Point& rPos,
2241     int& nStart, sal_Int32* pGlyphAdvAry, int* pCharPosAry ) const
2242 {
2243     // for multi-level fallback only single glyphs should be used
2244     if( mnLevel > 1 && nLen > 1 )
2245         nLen = 1;
2246
2247     // NOTE: nStart is tagged with current font index
2248     int nLevel = static_cast<unsigned>(nStart) >> GF_FONTSHIFT;
2249     nStart &= ~GF_FONTMASK;
2250     for(; nLevel < mnLevel; ++nLevel, nStart=0 )
2251     {
2252         SalLayout& rLayout = *mpLayouts[ nLevel ];
2253         rLayout.InitFont();
2254         int nRetVal = rLayout.GetNextGlyphs( nLen, pGlyphIdxAry, rPos,
2255             nStart, pGlyphAdvAry, pCharPosAry );
2256         if( nRetVal )
2257         {
2258             int nFontTag = nLevel << GF_FONTSHIFT;
2259             nStart |= nFontTag;
2260             double fUnitMul = mnUnitsPerPixel;
2261             fUnitMul /= mpLayouts[nLevel]->GetUnitsPerPixel();
2262             for( int i = 0; i < nRetVal; ++i )
2263             {
2264                 if( pGlyphAdvAry )
2265                 {
2266                     long w = pGlyphAdvAry[i];
2267                     w = static_cast<long>(w * fUnitMul + 0.5);
2268                     pGlyphAdvAry[i] = w;
2269                 }
2270                 pGlyphIdxAry[ i ] |= nFontTag;
2271             }
2272             rPos += maDrawBase;
2273             rPos += maDrawOffset;
2274             return nRetVal;
2275         }
2276     }
2277
2278     // #111016# reset to base level font when done
2279     mpLayouts[0]->InitFont();
2280     return 0;
2281 }
2282
2283 // -----------------------------------------------------------------------
2284
2285 bool MultiSalLayout::GetOutline( SalGraphics& rGraphics,
2286     ::basegfx::B2DPolyPolygonVector& rPPV ) const
2287 {
2288     bool bRet = false;
2289
2290     for( int i = mnLevel; --i >= 0; )
2291     {
2292         SalLayout& rLayout = *mpLayouts[ i ];
2293         rLayout.DrawBase() = maDrawBase;
2294         rLayout.DrawOffset() += maDrawOffset;
2295         rLayout.InitFont();
2296         bRet |= rLayout.GetOutline( rGraphics, rPPV );
2297         rLayout.DrawOffset() -= maDrawOffset;
2298     }
2299
2300     return bRet;
2301 }
2302
2303 // -----------------------------------------------------------------------
2304
2305 bool MultiSalLayout::GetBoundRect( SalGraphics& rGraphics, Rectangle& rRect ) const
2306 {
2307     bool bRet = false;
2308
2309     Rectangle aRectangle;
2310     for( int i = mnLevel; --i >= 0; )
2311     {
2312         SalLayout& rLayout = *mpLayouts[ i ];
2313         rLayout.DrawBase() = maDrawBase;
2314         rLayout.DrawOffset() += maDrawOffset;
2315         rLayout.InitFont();
2316         if( rLayout.GetBoundRect( rGraphics, aRectangle ) )
2317         {
2318             rRect.Union( aRectangle );
2319             bRet = true;
2320         }
2321         rLayout.DrawOffset() -= maDrawOffset;
2322     }
2323
2324     return bRet;
2325 }
2326
2327 // =======================================================================