src/gui/text/qfontengine.cpp

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
   4 ** All rights reserved.
   5 ** Contact: Nokia Corporation (qt-info@nokia.com)
   6 **
   7 ** This file is part of the QtGui module of the Qt Toolkit.
   8 **
   9 ** $QT_BEGIN_LICENSE:LGPL$
  10 ** GNU Lesser General Public License Usage
  11 ** This file may be used under the terms of the GNU Lesser General Public
  12 ** License version 2.1 as published by the Free Software Foundation and
  13 ** appearing in the file LICENSE.LGPL included in the packaging of this
  14 ** file. Please review the following information to ensure the GNU Lesser
  15 ** General Public License version 2.1 requirements will be met:
  16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  17 **
  18 ** In addition, as a special exception, Nokia gives you certain additional
  19 ** rights. These rights are described in the Nokia Qt LGPL Exception
  20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  21 **
  22 ** GNU General Public License Usage
  23 ** Alternatively, this file may be used under the terms of the GNU General
  24 ** Public License version 3.0 as published by the Free Software Foundation
  25 ** and appearing in the file LICENSE.GPL included in the packaging of this
  26 ** file. Please review the following information to ensure the GNU General
  27 ** Public License version 3.0 requirements will be met:
  28 ** http://www.gnu.org/copyleft/gpl.html.
  29 **
  30 ** Other Usage
  31 ** Alternatively, this file may be used in accordance with the terms and
  32 ** conditions contained in a signed written agreement between you and Nokia.
  33 **
  34 **
  35 **
  36 **
  37 **
  38 ** $QT_END_LICENSE$
  39 **
  40 ****************************************************************************/
  41
  42 #include <qdebug.h>
  43 #include <private/qfontengine_p.h>
  44
  45 #include "qbitmap.h"
  46 #include "qpainter.h"
  47 #include "qpainterpath.h"
  48 #include "qvarlengtharray.h"
  49 #include <qmath.h>
  50 #include <qendian.h>
  51 #include <private/qharfbuzz_p.h>
  52
  53 QT_BEGIN_NAMESPACE
  54
  55 static inline bool qtransform_equals_no_translate(const QTransform &a, const QTransform &b)
  56 {
  57     if (a.type() <= QTransform::TxTranslate && b.type() <= QTransform::TxTranslate) {
  58         return true;
  59     } else {
  60         // We always use paths for perspective text anyway, so no
  61         // point in checking the full matrix...
  62         Q_ASSERT(a.type() < QTransform::TxProject);
  63         Q_ASSERT(b.type() < QTransform::TxProject);
  64
  65         return a.m11() == b.m11()
  66             && a.m12() == b.m12()
  67             && a.m21() == b.m21()
  68             && a.m22() == b.m22();
  69     }
  70 }
  71
  72 // Harfbuzz helper functions
  73
  74 static HB_Bool hb_stringToGlyphs(HB_Font font, const HB_UChar16 *string, hb_uint32 length, HB_Glyph *glyphs, hb_uint32 *numGlyphs, HB_Bool rightToLeft)
  75 {
  76     QFontEngine *fe = (QFontEngine *)font->userData;
  77
  78     QVarLengthGlyphLayoutArray qglyphs(*numGlyphs);
  79
  80     QTextEngine::ShaperFlags shaperFlags(QTextEngine::GlyphIndicesOnly);
  81     if (rightToLeft)
  82         shaperFlags |= QTextEngine::RightToLeft;
  83
  84     int nGlyphs = *numGlyphs;
  85     bool result = fe->stringToCMap(reinterpret_cast<const QChar *>(string), length, &qglyphs, &nGlyphs, shaperFlags);
  86     *numGlyphs = nGlyphs;
  87     if (!result)
  88         return false;
  89
  90     for (hb_uint32 i = 0; i < *numGlyphs; ++i)
  91         glyphs[i] = qglyphs.glyphs[i];
  92
  93     return true;
  94 }
  95
  96 static void hb_getAdvances(HB_Font font, const HB_Glyph *glyphs, hb_uint32 numGlyphs, HB_Fixed *advances, int flags)
  97 {
  98     QFontEngine *fe = (QFontEngine *)font->userData;
  99
 100     QVarLengthGlyphLayoutArray qglyphs(numGlyphs);
 101
 102     for (hb_uint32 i = 0; i < numGlyphs; ++i)
 103         qglyphs.glyphs[i] = glyphs[i];
 104
 105     fe->recalcAdvances(&qglyphs, flags & HB_ShaperFlag_UseDesignMetrics ? QFlags<QTextEngine::ShaperFlag>(QTextEngine::DesignMetrics) : QFlags<QTextEngine::ShaperFlag>(0));
 106
 107     for (hb_uint32 i = 0; i < numGlyphs; ++i)
 108         advances[i] = qglyphs.advances_x[i].value();
 109 }
 110
 111 static HB_Bool hb_canRender(HB_Font font, const HB_UChar16 *string, hb_uint32 length)
 112 {
 113     QFontEngine *fe = (QFontEngine *)font->userData;
 114     return fe->canRender(reinterpret_cast<const QChar *>(string), length);
 115 }
 116
 117 static void hb_getGlyphMetrics(HB_Font font, HB_Glyph glyph, HB_GlyphMetrics *metrics)
 118 {
 119     QFontEngine *fe = (QFontEngine *)font->userData;
 120     glyph_metrics_t m = fe->boundingBox(glyph);
 121     metrics->x = m.x.value();
 122     metrics->y = m.y.value();
 123     metrics->width = m.width.value();
 124     metrics->height = m.height.value();
 125     metrics->xOffset = m.xoff.value();
 126     metrics->yOffset = m.yoff.value();
 127 }
 128
 129 static HB_Fixed hb_getFontMetric(HB_Font font, HB_FontMetric metric)
 130 {
 131     if (metric == HB_FontAscent) {
 132         QFontEngine *fe = (QFontEngine *)font->userData;
 133         return fe->ascent().value();
 134     }
 135     return 0;
 136 }
 137
 138 HB_Error QFontEngine::getPointInOutline(HB_Glyph glyph, int flags, hb_uint32 point, HB_Fixed *xpos, HB_Fixed *ypos, hb_uint32 *nPoints)
 139 {
 140     Q_UNUSED(glyph)
 141     Q_UNUSED(flags)
 142     Q_UNUSED(point)
 143     Q_UNUSED(xpos)
 144     Q_UNUSED(ypos)
 145     Q_UNUSED(nPoints)
 146     return HB_Err_Not_Covered;
 147 }
 148
 149 static HB_Error hb_getPointInOutline(HB_Font font, HB_Glyph glyph, int flags, hb_uint32 point, HB_Fixed *xpos, HB_Fixed *ypos, hb_uint32 *nPoints)
 150 {
 151     QFontEngine *fe = (QFontEngine *)font->userData;
 152     return fe->getPointInOutline(glyph, flags, point, xpos, ypos, nPoints);
 153 }
 154
 155 static const HB_FontClass hb_fontClass = {
 156     hb_stringToGlyphs, hb_getAdvances, hb_canRender, hb_getPointInOutline,
 157     hb_getGlyphMetrics, hb_getFontMetric
 158 };
 159
 160 static HB_Error hb_getSFntTable(void *font, HB_Tag tableTag, HB_Byte *buffer, HB_UInt *length)
 161 {
 162     QFontEngine *fe = (QFontEngine *)font;
 163     if (!fe->getSfntTableData(tableTag, buffer, length))
 164         return HB_Err_Invalid_Argument;
 165     return HB_Err_Ok;
 166 }
 167
 168 // QFontEngine
 169
 170 QFontEngine::QFontEngine()
 171     : QObject()
 172 {
 173     ref = 0;
 174     cache_count = 0;
 175     fsType = 0;
 176     symbol = false;
 177     memset(&hbFont, 0, sizeof(hbFont));
 178     hbFont.klass = &hb_fontClass;
 179     hbFont.userData = this;
 180
 181     hbFace = 0;
 182     glyphFormat = -1;
 183 }
 184
 185 QFontEngine::~QFontEngine()
 186 {
 187     m_glyphCaches.clear();
 188     qHBFreeFace(hbFace);
 189 }
 190
 191 QFixed QFontEngine::lineThickness() const
 192 {
 193     // ad hoc algorithm
 194     int score = fontDef.weight * fontDef.pixelSize;
 195     int lw = score / 700;
 196
 197     // looks better with thicker line for small pointsizes
 198     if (lw < 2 && score >= 1050) lw = 2;
 199     if (lw == 0) lw = 1;
 200
 201     return lw;
 202 }
 203
 204 QFixed QFontEngine::underlinePosition() const
 205 {
 206     return ((lineThickness() * 2) + 3) / 6;
 207 }
 208
 209 HB_Font QFontEngine::harfbuzzFont() const
 210 {
 211     if (!hbFont.x_ppem) {
 212         QFixed emSquare = emSquareSize();
 213         hbFont.x_ppem = fontDef.pixelSize;
 214         hbFont.y_ppem = fontDef.pixelSize * fontDef.stretch / 100;
 215         hbFont.x_scale = (QFixed(hbFont.x_ppem * (1 << 16)) / emSquare).value();
 216         hbFont.y_scale = (QFixed(hbFont.y_ppem * (1 << 16)) / emSquare).value();
 217     }
 218     return &hbFont;
 219 }
 220
 221 HB_Face QFontEngine::harfbuzzFace() const
 222 {
 223     if (!hbFace) {
 224         hbFace = qHBNewFace(const_cast<QFontEngine *>(this), hb_getSFntTable);
 225         Q_CHECK_PTR(hbFace);
 226     }
 227     return hbFace;
 228 }
 229
 230 glyph_metrics_t QFontEngine::boundingBox(glyph_t glyph, const QTransform &matrix)
 231 {
 232     glyph_metrics_t metrics = boundingBox(glyph);
 233
 234     if (matrix.type() > QTransform::TxTranslate) {
 235         return metrics.transformed(matrix);
 236     }
 237     return metrics;
 238 }
 239
 240 QFixed QFontEngine::xHeight() const
 241 {
 242     QGlyphLayoutArray<8> glyphs;
 243     int nglyphs = 7;
 244     QChar x((ushort)'x');
 245     stringToCMap(&x, 1, &glyphs, &nglyphs, QTextEngine::GlyphIndicesOnly);
 246
 247     glyph_metrics_t bb = const_cast<QFontEngine *>(this)->boundingBox(glyphs.glyphs[0]);
 248     return bb.height;
 249 }
 250
 251 QFixed QFontEngine::averageCharWidth() const
 252 {
 253     QGlyphLayoutArray<8> glyphs;
 254     int nglyphs = 7;
 255     QChar x((ushort)'x');
 256     stringToCMap(&x, 1, &glyphs, &nglyphs, QTextEngine::GlyphIndicesOnly);
 257
 258     glyph_metrics_t bb = const_cast<QFontEngine *>(this)->boundingBox(glyphs.glyphs[0]);
 259     return bb.xoff;
 260 }
 261
 262
 263 void QFontEngine::getGlyphPositions(const QGlyphLayout &glyphs, const QTransform &matrix, QTextItem::RenderFlags flags,
 264                                     QVarLengthArray<glyph_t> &glyphs_out, QVarLengthArray<QFixedPoint> &positions)
 265 {
 266     QFixed xpos;
 267     QFixed ypos;
 268
 269     const bool transform = matrix.m11() != 1.
 270                            || matrix.m12() != 0.
 271                            || matrix.m21() != 0.
 272                            || matrix.m22() != 1.;
 273     if (!transform) {
 274         xpos = QFixed::fromReal(matrix.dx());
 275         ypos = QFixed::fromReal(matrix.dy());
 276     }
 277
 278     int current = 0;
 279     if (flags & QTextItem::RightToLeft) {
 280         int i = glyphs.numGlyphs;
 281         int totalKashidas = 0;
 282         while(i--) {
 283             if (glyphs.attributes[i].dontPrint)
 284                 continue;
 285             xpos += glyphs.advances_x[i] + QFixed::fromFixed(glyphs.justifications[i].space_18d6);
 286             ypos += glyphs.advances_y[i];
 287             totalKashidas += glyphs.justifications[i].nKashidas;
 288         }
 289         positions.resize(glyphs.numGlyphs+totalKashidas);
 290         glyphs_out.resize(glyphs.numGlyphs+totalKashidas);
 291
 292         i = 0;
 293         while(i < glyphs.numGlyphs) {
 294             if (glyphs.attributes[i].dontPrint) {
 295                 ++i;
 296                 continue;
 297             }
 298             xpos -= glyphs.advances_x[i];
 299             ypos -= glyphs.advances_y[i];
 300
 301             QFixed gpos_x = xpos + glyphs.offsets[i].x;
 302             QFixed gpos_y = ypos + glyphs.offsets[i].y;
 303             if (transform) {
 304                 QPointF gpos(gpos_x.toReal(), gpos_y.toReal());
 305                 gpos = gpos * matrix;
 306                 gpos_x = QFixed::fromReal(gpos.x());
 307                 gpos_y = QFixed::fromReal(gpos.y());
 308             }
 309             positions[current].x = gpos_x;
 310             positions[current].y = gpos_y;
 311             glyphs_out[current] = glyphs.glyphs[i];
 312             ++current;
 313             if (glyphs.justifications[i].nKashidas) {
 314                 QChar ch(0x640); // Kashida character
 315                 QGlyphLayoutArray<8> g;
 316                 int nglyphs = 7;
 317                 stringToCMap(&ch, 1, &g, &nglyphs, 0);
 318                 for (uint k = 0; k < glyphs.justifications[i].nKashidas; ++k) {
 319                     xpos -= g.advances_x[0];
 320                     ypos -= g.advances_y[0];
 321
 322                     QFixed gpos_x = xpos + glyphs.offsets[i].x;
 323                     QFixed gpos_y = ypos + glyphs.offsets[i].y;
 324                     if (transform) {
 325                         QPointF gpos(gpos_x.toReal(), gpos_y.toReal());
 326                         gpos = gpos * matrix;
 327                         gpos_x = QFixed::fromReal(gpos.x());
 328                         gpos_y = QFixed::fromReal(gpos.y());
 329                     }
 330                     positions[current].x = gpos_x;
 331                     positions[current].y = gpos_y;
 332                     glyphs_out[current] = g.glyphs[0];
 333                     ++current;
 334                 }
 335             } else {
 336                 xpos -= QFixed::fromFixed(glyphs.justifications[i].space_18d6);
 337             }
 338             ++i;
 339         }
 340     } else {
 341         positions.resize(glyphs.numGlyphs);
 342         glyphs_out.resize(glyphs.numGlyphs);
 343         int i = 0;
 344         if (!transform) {
 345             while (i < glyphs.numGlyphs) {
 346                 if (!glyphs.attributes[i].dontPrint) {
 347                     positions[current].x = xpos + glyphs.offsets[i].x;
 348                     positions[current].y = ypos + glyphs.offsets[i].y;
 349                     glyphs_out[current] = glyphs.glyphs[i];
 350                     xpos += glyphs.advances_x[i] + QFixed::fromFixed(glyphs.justifications[i].space_18d6);
 351                     ypos += glyphs.advances_y[i];
 352                     ++current;
 353                 }
 354                 ++i;
 355             }
 356         } else {
 357             while (i < glyphs.numGlyphs) {
 358                 if (!glyphs.attributes[i].dontPrint) {
 359                     QFixed gpos_x = xpos + glyphs.offsets[i].x;
 360                     QFixed gpos_y = ypos + glyphs.offsets[i].y;
 361                     QPointF gpos(gpos_x.toReal(), gpos_y.toReal());
 362                     gpos = gpos * matrix;
 363                     positions[current].x = QFixed::fromReal(gpos.x());
 364                     positions[current].y = QFixed::fromReal(gpos.y());
 365                     glyphs_out[current] = glyphs.glyphs[i];
 366                     xpos += glyphs.advances_x[i] + QFixed::fromFixed(glyphs.justifications[i].space_18d6);
 367                     ypos += glyphs.advances_y[i];
 368                     ++current;
 369                 }
 370                 ++i;
 371             }
 372         }
 373     }
 374     positions.resize(current);
 375     glyphs_out.resize(current);
 376     Q_ASSERT(positions.size() == glyphs_out.size());
 377 }
 378
 379 void QFontEngine::getGlyphBearings(glyph_t glyph, qreal *leftBearing, qreal *rightBearing)
 380 {
 381     glyph_metrics_t gi = boundingBox(glyph);
 382     bool isValid = gi.isValid();
 383     if (leftBearing != 0)
 384         *leftBearing = isValid ? gi.x.toReal() : 0.0;
 385     if (rightBearing != 0)
 386         *rightBearing = isValid ? (gi.xoff - gi.x - gi.width).toReal() : 0.0;
 387 }
 388
 389 glyph_metrics_t QFontEngine::tightBoundingBox(const QGlyphLayout &glyphs)
 390 {
 391     glyph_metrics_t overall;
 392
 393     QFixed ymax = 0;
 394     QFixed xmax = 0;
 395     for (int i = 0; i < glyphs.numGlyphs; i++) {
 396         glyph_metrics_t bb = boundingBox(glyphs.glyphs[i]);
 397         QFixed x = overall.xoff + glyphs.offsets[i].x + bb.x;
 398         QFixed y = overall.yoff + glyphs.offsets[i].y + bb.y;
 399         overall.x = qMin(overall.x, x);
 400         overall.y = qMin(overall.y, y);
 401         xmax = qMax(xmax, x + bb.width);
 402         ymax = qMax(ymax, y + bb.height);
 403         overall.xoff += bb.xoff;
 404         overall.yoff += bb.yoff;
 405     }
 406     overall.height = qMax(overall.height, ymax - overall.y);
 407     overall.width = xmax - overall.x;
 408
 409     return overall;
 410 }
 411
 412
 413 void QFontEngine::addOutlineToPath(qreal x, qreal y, const QGlyphLayout &glyphs, QPainterPath *path,
 414                                    QTextItem::RenderFlags flags)
 415 {
 416     if (!glyphs.numGlyphs)
 417         return;
 418
 419     QVarLengthArray<QFixedPoint> positions;
 420     QVarLengthArray<glyph_t> positioned_glyphs;
 421     QTransform matrix = QTransform::fromTranslate(x, y);
 422     getGlyphPositions(glyphs, matrix, flags, positioned_glyphs, positions);
 423     addGlyphsToPath(positioned_glyphs.data(), positions.data(), positioned_glyphs.size(), path, flags);
 424 }
 425
 426 #define GRID(x, y) grid[(y)*(w+1) + (x)]
 427 #define SET(x, y) (*(image_data + (y)*bpl + ((x) >> 3)) & (0x80 >> ((x) & 7)))
 428
 429 enum { EdgeRight = 0x1,
 430        EdgeDown = 0x2,
 431        EdgeLeft = 0x4,
 432        EdgeUp = 0x8
 433 };
 434
 435 static void collectSingleContour(qreal x0, qreal y0, uint *grid, int x, int y, int w, int h, QPainterPath *path)
 436 {
 437     Q_UNUSED(h);
 438
 439     path->moveTo(x + x0, y + y0);
 440     while (GRID(x, y)) {
 441         if (GRID(x, y) & EdgeRight) {
 442             while (GRID(x, y) & EdgeRight) {
 443                 GRID(x, y) &= ~EdgeRight;
 444                 ++x;
 445             }
 446             Q_ASSERT(x <= w);
 447             path->lineTo(x + x0, y + y0);
 448             continue;
 449         }
 450         if (GRID(x, y) & EdgeDown) {
 451             while (GRID(x, y) & EdgeDown) {
 452                 GRID(x, y) &= ~EdgeDown;
 453                 ++y;
 454             }
 455             Q_ASSERT(y <= h);
 456             path->lineTo(x + x0, y + y0);
 457             continue;
 458         }
 459         if (GRID(x, y) & EdgeLeft) {
 460             while (GRID(x, y) & EdgeLeft) {
 461                 GRID(x, y) &= ~EdgeLeft;
 462                 --x;
 463             }
 464             Q_ASSERT(x >= 0);
 465             path->lineTo(x + x0, y + y0);
 466             continue;
 467         }
 468         if (GRID(x, y) & EdgeUp) {
 469             while (GRID(x, y) & EdgeUp) {
 470                 GRID(x, y) &= ~EdgeUp;
 471                 --y;
 472             }
 473             Q_ASSERT(y >= 0);
 474             path->lineTo(x + x0, y + y0);
 475             continue;
 476         }
 477     }
 478     path->closeSubpath();
 479 }
 480
 481 Q_GUI_EXPORT void qt_addBitmapToPath(qreal x0, qreal y0, const uchar *image_data, int bpl, int w, int h, QPainterPath *path)
 482 {
 483     uint *grid = new uint[(w+1)*(h+1)];
 484     // set up edges
 485     for (int y = 0; y <= h; ++y) {
 486         for (int x = 0; x <= w; ++x) {
 487             bool topLeft = (x == 0)|(y == 0) ? false : SET(x - 1, y - 1);
 488             bool topRight = (x == w)|(y == 0) ? false : SET(x, y - 1);
 489             bool bottomLeft = (x == 0)|(y == h) ? false : SET(x - 1, y);
 490             bool bottomRight = (x == w)|(y == h) ? false : SET(x, y);
 491
 492             GRID(x, y) = 0;
 493             if ((!topRight) & bottomRight)
 494                 GRID(x, y) |= EdgeRight;
 495             if ((!bottomRight) & bottomLeft)
 496                 GRID(x, y) |= EdgeDown;
 497             if ((!bottomLeft) & topLeft)
 498                 GRID(x, y) |= EdgeLeft;
 499             if ((!topLeft) & topRight)
 500                 GRID(x, y) |= EdgeUp;
 501         }
 502     }
 503
 504     // collect edges
 505     for (int y = 0; y < h; ++y) {
 506         for (int x = 0; x < w; ++x) {
 507             if (!GRID(x, y))
 508                 continue;
 509             // found start of a contour, follow it
 510             collectSingleContour(x0, y0, grid, x, y, w, h, path);
 511         }
 512     }
 513     delete [] grid;
 514 }
 515
 516 #undef GRID
 517 #undef SET
 518
 519
 520 void QFontEngine::addBitmapFontToPath(qreal x, qreal y, const QGlyphLayout &glyphs,
 521                                       QPainterPath *path, QTextItem::RenderFlags flags)
 522 {
 523 // TODO what to do with 'flags' ??
 524     Q_UNUSED(flags);
 525     QFixed advanceX = QFixed::fromReal(x);
 526     QFixed advanceY = QFixed::fromReal(y);
 527     for (int i=0; i < glyphs.numGlyphs; ++i) {
 528         glyph_metrics_t metrics = boundingBox(glyphs.glyphs[i]);
 529         if (metrics.width.value() == 0 || metrics.height.value() == 0) {
 530             advanceX += glyphs.advances_x[i];
 531             advanceY += glyphs.advances_y[i];
 532             continue;
 533         }
 534         const QImage alphaMask = alphaMapForGlyph(glyphs.glyphs[i]);
 535
 536         const int w = alphaMask.width();
 537         const int h = alphaMask.height();
 538         const int srcBpl = alphaMask.bytesPerLine();
 539         QImage bitmap;
 540         if (alphaMask.depth() == 1) {
 541             bitmap = alphaMask;
 542         } else {
 543             bitmap = QImage(w, h, QImage::Format_Mono);
 544             const uchar *imageData = alphaMask.bits();
 545             const int destBpl = bitmap.bytesPerLine();
 546             uchar *bitmapData = bitmap.bits();
 547
 548             for (int yi = 0; yi < h; ++yi) {
 549                 const uchar *src = imageData + yi*srcBpl;
 550                 uchar *dst = bitmapData + yi*destBpl;
 551                 for (int xi = 0; xi < w; ++xi) {
 552                     const int byte = xi / 8;
 553                     const int bit = xi % 8;
 554                     if (bit == 0)
 555                         dst[byte] = 0;
 556                     if (src[xi])
 557                         dst[byte] |= 128 >> bit;
 558                 }
 559             }
 560         }
 561         const uchar *bitmap_data = bitmap.bits();
 562         QFixedPoint offset = glyphs.offsets[i];
 563         advanceX += offset.x;
 564         advanceY += offset.y;
 565         qt_addBitmapToPath((advanceX + metrics.x).toReal(), (advanceY + metrics.y).toReal(), bitmap_data, bitmap.bytesPerLine(), w, h, path);
 566         advanceX += glyphs.advances_x[i];
 567         advanceY += glyphs.advances_y[i];
 568     }
 569 }
 570
 571 void QFontEngine::addGlyphsToPath(glyph_t *glyphs, QFixedPoint *positions, int nGlyphs,
 572                                   QPainterPath *path, QTextItem::RenderFlags flags)
 573 {
 574     qreal x = positions[0].x.toReal();
 575     qreal y = positions[0].y.toReal();
 576     QVarLengthGlyphLayoutArray g(nGlyphs);
 577
 578     for (int i = 0; i < nGlyphs; ++i) {
 579         g.glyphs[i] = glyphs[i];
 580         if (i < nGlyphs - 1) {
 581             g.advances_x[i] = positions[i+1].x - positions[i].x;
 582             g.advances_y[i] = positions[i+1].y - positions[i].y;
 583         } else {
 584             g.advances_x[i] = QFixed::fromReal(maxCharWidth());
 585             g.advances_y[i] = 0;
 586         }
 587     }
 588
 589     addBitmapFontToPath(x, y, g, path, flags);
 590 }
 591
 592 QImage QFontEngine::alphaMapForGlyph(glyph_t glyph, QFixed /*subPixelPosition*/)
 593 {
 594     // For font engines don't support subpixel positioning
 595     return alphaMapForGlyph(glyph);
 596 }
 597
 598 QImage QFontEngine::alphaMapForGlyph(glyph_t glyph, const QTransform &t)
 599 {
 600     QImage i = alphaMapForGlyph(glyph);
 601     if (t.type() > QTransform::TxTranslate)
 602         i = i.transformed(t).convertToFormat(QImage::Format_Indexed8);
 603     Q_ASSERT(i.depth() <= 8); // To verify that transformed didn't change the format...
 604
 605     return i;
 606 }
 607
 608 QImage QFontEngine::alphaMapForGlyph(glyph_t glyph, QFixed subPixelPosition, const QTransform &t)
 609 {
 610     if (! supportsSubPixelPositions())
 611         return alphaMapForGlyph(glyph, t);
 612
 613     QImage i = alphaMapForGlyph(glyph, subPixelPosition);
 614     if (t.type() > QTransform::TxTranslate)
 615         i = i.transformed(t).convertToFormat(QImage::Format_Indexed8);
 616     Q_ASSERT(i.depth() <= 8); // To verify that transformed didn't change the format...
 617
 618     return i;
 619 }
 620
 621 QImage QFontEngine::alphaRGBMapForGlyph(glyph_t glyph, QFixed /*subPixelPosition*/, int /* margin */, const QTransform &t)
 622 {
 623     QImage alphaMask = alphaMapForGlyph(glyph, t);
 624     QImage rgbMask(alphaMask.width(), alphaMask.height(), QImage::Format_RGB32);
 625
 626     QVector<QRgb> colorTable = alphaMask.colorTable();
 627     for (int y=0; y<alphaMask.height(); ++y) {
 628         uint *dst = (uint *) rgbMask.scanLine(y);
 629         uchar *src = (uchar *) alphaMask.scanLine(y);
 630         for (int x=0; x<alphaMask.width(); ++x) {
 631             int val = qAlpha(colorTable.at(src[x]));
 632             dst[x] = qRgb(val, val, val);
 633         }
 634     }
 635
 636     return rgbMask;
 637 }
 638
 639 QFixed QFontEngine::subPixelPositionForX(QFixed x)
 640 {
 641     int m_subPixelPositionCount = 4;
 642     if (!supportsSubPixelPositions())
 643         return 0;
 644
 645     QFixed subPixelPosition;
 646     if (x != 0) {
 647         subPixelPosition = x - x.floor();
 648         QFixed fraction = (subPixelPosition / QFixed::fromReal(1.0 / m_subPixelPositionCount)).floor();
 649         subPixelPosition = fraction / QFixed(m_subPixelPositionCount);
 650     }
 651     return subPixelPosition;
 652 }
 653
 654 QImage *QFontEngine::lockedAlphaMapForGlyph(glyph_t glyph, QFixed subPixelPosition,
 655                                             QFontEngine::GlyphFormat neededFormat,
 656                                             const QTransform &t, QPoint *offset)
 657 {
 658     Q_ASSERT(currentlyLockedAlphaMap.isNull());
 659     if (neededFormat == Format_None)
 660         neededFormat = Format_A32;
 661
 662     if (neededFormat != Format_A32)
 663         currentlyLockedAlphaMap = alphaMapForGlyph(glyph, subPixelPosition, t);
 664     else
 665         currentlyLockedAlphaMap = alphaRGBMapForGlyph(glyph, subPixelPosition, 0, t);
 666
 667     if (offset != 0)
 668         *offset = QPoint(0, 0);
 669
 670     return &currentlyLockedAlphaMap;
 671 }
 672
 673 void QFontEngine::unlockAlphaMapForGlyph()
 674 {
 675     Q_ASSERT(!currentlyLockedAlphaMap.isNull());
 676     currentlyLockedAlphaMap = QImage();
 677 }
 678
 679 QImage QFontEngine::alphaMapForGlyph(glyph_t glyph)
 680 {
 681     glyph_metrics_t gm = boundingBox(glyph);
 682     int glyph_x = qFloor(gm.x.toReal());
 683     int glyph_y = qFloor(gm.y.toReal());
 684     int glyph_width = qCeil((gm.x + gm.width).toReal()) -  glyph_x;
 685     int glyph_height = qCeil((gm.y + gm.height).toReal()) - glyph_y;
 686
 687     if (glyph_width <= 0 || glyph_height <= 0)
 688         return QImage();
 689     QFixedPoint pt;
 690     pt.x = -glyph_x;
 691     pt.y = -glyph_y; // the baseline
 692     QPainterPath path;
 693     QImage im(glyph_width + 4, glyph_height, QImage::Format_ARGB32_Premultiplied);
 694     im.fill(Qt::transparent);
 695     QPainter p(&im);
 696     p.setRenderHint(QPainter::Antialiasing);
 697     addGlyphsToPath(&glyph, &pt, 1, &path, 0);
 698     p.setPen(Qt::NoPen);
 699     p.setBrush(Qt::black);
 700     p.drawPath(path);
 701     p.end();
 702
 703     QImage indexed(im.width(), im.height(), QImage::Format_Indexed8);
 704     QVector<QRgb> colors(256);
 705     for (int i=0; i<256; ++i)
 706         colors[i] = qRgba(0, 0, 0, i);
 707     indexed.setColorTable(colors);
 708
 709     for (int y=0; y<im.height(); ++y) {
 710         uchar *dst = (uchar *) indexed.scanLine(y);
 711         uint *src = (uint *) im.scanLine(y);
 712         for (int x=0; x<im.width(); ++x)
 713             dst[x] = qAlpha(src[x]);
 714     }
 715
 716     return indexed;
 717 }
 718
 719 void QFontEngine::removeGlyphFromCache(glyph_t)
 720 {
 721 }
 722
 723 QFontEngine::Properties QFontEngine::properties() const
 724 {
 725     Properties p;
 726     QByteArray psname = QFontEngine::convertToPostscriptFontFamilyName(fontDef.family.toUtf8());
 727     psname += '-';
 728     psname += QByteArray::number(fontDef.style);
 729     psname += '-';
 730     psname += QByteArray::number(fontDef.weight);
 731
 732     p.postscriptName = psname;
 733     p.ascent = ascent();
 734     p.descent = descent();
 735     p.leading = leading();
 736     p.emSquare = p.ascent;
 737     p.boundingBox = QRectF(0, -p.ascent.toReal(), maxCharWidth(), (p.ascent + p.descent).toReal());
 738     p.italicAngle = 0;
 739     p.capHeight = p.ascent;
 740     p.lineWidth = lineThickness();
 741     return p;
 742 }
 743
 744 void QFontEngine::getUnscaledGlyph(glyph_t glyph, QPainterPath *path, glyph_metrics_t *metrics)
 745 {
 746     *metrics = boundingBox(glyph);
 747     QFixedPoint p;
 748     p.x = 0;
 749     p.y = 0;
 750     addGlyphsToPath(&glyph, &p, 1, path, QFlag(0));
 751 }
 752
 753 QByteArray QFontEngine::getSfntTable(uint tag) const
 754 {
 755     QByteArray table;
 756     uint len = 0;
 757     if (!getSfntTableData(tag, 0, &len))
 758         return table;
 759     if (!len)
 760         return table;
 761     table.resize(len);
 762     if (!getSfntTableData(tag, reinterpret_cast<uchar *>(table.data()), &len))
 763         return QByteArray();
 764     return table;
 765 }
 766
 767 void QFontEngine::setGlyphCache(void *key, QFontEngineGlyphCache *data)
 768 {
 769     Q_ASSERT(data);
 770
 771     GlyphCacheEntry entry;
 772     entry.context = key;
 773     entry.cache = data;
 774     if (m_glyphCaches.contains(entry))
 775         return;
 776
 777     // Limit the glyph caches to 4. This covers all 90 degree rotations and limits
 778     // memory use when there is continuous or random rotation
 779     if (m_glyphCaches.size() == 4)
 780         m_glyphCaches.removeLast();
 781
 782     m_glyphCaches.push_front(entry);
 783
 784 }
 785
 786 QFontEngineGlyphCache *QFontEngine::glyphCache(void *key, QFontEngineGlyphCache::Type type, const QTransform &transform) const
 787 {
 788     for (QLinkedList<GlyphCacheEntry>::const_iterator it = m_glyphCaches.constBegin(), end = m_glyphCaches.constEnd(); it != end; ++it) {
 789         QFontEngineGlyphCache *c = it->cache.data();
 790         if (key == it->context
 791             && type == c->cacheType()
 792             && qtransform_equals_no_translate(c->m_transform, transform)) {
 793             return c;
 794         }
 795     }
 796     return 0;
 797 }
 798
 799 #if defined(Q_WS_WIN) || defined(Q_WS_X11) || defined(Q_WS_QWS) || defined(Q_WS_QPA) || defined(Q_OS_SYMBIAN)
 800 static inline QFixed kerning(int left, int right, const QFontEngine::KernPair *pairs, int numPairs)
 801 {
 802     uint left_right = (left << 16) + right;
 803
 804     left = 0, right = numPairs - 1;
 805     while (left <= right) {
 806         int middle = left + ( ( right - left ) >> 1 );
 807
 808         if(pairs[middle].left_right == left_right)
 809             return pairs[middle].adjust;
 810
 811         if (pairs[middle].left_right < left_right)
 812             left = middle + 1;
 813         else
 814             right = middle - 1;
 815     }
 816     return 0;
 817 }
 818
 819 void QFontEngine::doKerning(QGlyphLayout *glyphs, QTextEngine::ShaperFlags flags) const
 820 {
 821     int numPairs = kerning_pairs.size();
 822     if(!numPairs)
 823         return;
 824
 825     const KernPair *pairs = kerning_pairs.constData();
 826
 827     if(flags & QTextEngine::DesignMetrics) {
 828         for(int i = 0; i < glyphs->numGlyphs - 1; ++i)
 829             glyphs->advances_x[i] += kerning(glyphs->glyphs[i], glyphs->glyphs[i+1] , pairs, numPairs);
 830     } else {
 831         for(int i = 0; i < glyphs->numGlyphs - 1; ++i)
 832             glyphs->advances_x[i] += qRound(kerning(glyphs->glyphs[i], glyphs->glyphs[i+1] , pairs, numPairs));
 833     }
 834 }
 835
 836 void QFontEngine::loadKerningPairs(QFixed scalingFactor)
 837 {
 838     kerning_pairs.clear();
 839
 840     QByteArray tab = getSfntTable(MAKE_TAG('k', 'e', 'r', 'n'));
 841     if (tab.isEmpty())
 842         return;
 843
 844     const uchar *table = reinterpret_cast<const uchar *>(tab.constData());
 845
 846     unsigned short version = qFromBigEndian<quint16>(table);
 847     if (version != 0) {
 848 //        qDebug("wrong version");
 849        return;
 850     }
 851
 852     unsigned short numTables = qFromBigEndian<quint16>(table + 2);
 853     {
 854         int offset = 4;
 855         for(int i = 0; i < numTables; ++i) {
 856             if (offset + 6 > tab.size()) {
 857 //                qDebug("offset out of bounds");
 858                 goto end;
 859             }
 860             const uchar *header = table + offset;
 861
 862             ushort version = qFromBigEndian<quint16>(header);
 863             ushort length = qFromBigEndian<quint16>(header+2);
 864             ushort coverage = qFromBigEndian<quint16>(header+4);
 865 //            qDebug("subtable: version=%d, coverage=%x",version, coverage);
 866             if(version == 0 && coverage == 0x0001) {
 867                 if (offset + length > tab.size()) {
 868 //                    qDebug("length ouf ot bounds");
 869                     goto end;
 870                 }
 871                 const uchar *data = table + offset + 6;
 872
 873                 ushort nPairs = qFromBigEndian<quint16>(data);
 874                 if(nPairs * 6 + 8 > length - 6) {
 875 //                    qDebug("corrupt table!");
 876                     // corrupt table
 877                     goto end;
 878                 }
 879
 880                 int off = 8;
 881                 for(int i = 0; i < nPairs; ++i) {
 882                     QFontEngine::KernPair p;
 883                     p.left_right = (((uint)qFromBigEndian<quint16>(data+off)) << 16) + qFromBigEndian<quint16>(data+off+2);
 884                     p.adjust = QFixed(((int)(short)qFromBigEndian<quint16>(data+off+4))) / scalingFactor;
 885                     kerning_pairs.append(p);
 886                     off += 6;
 887                 }
 888             }
 889             offset += length;
 890         }
 891     }
 892 end:
 893     qSort(kerning_pairs);
 894 //    for (int i = 0; i < kerning_pairs.count(); ++i)
 895 //        qDebug() << 'i' << i << "left_right" << hex << kerning_pairs.at(i).left_right;
 896 }
 897
 898 #else
 899 void QFontEngine::doKerning(QGlyphLayout *, QTextEngine::ShaperFlags) const
 900 {
 901 }
 902 #endif
 903
 904 int QFontEngine::glyphCount() const
 905 {
 906     QByteArray maxpTable = getSfntTable(MAKE_TAG('m', 'a', 'x', 'p'));
 907     if (maxpTable.size() < 6)
 908         return 0;
 909     return qFromBigEndian<quint16>(reinterpret_cast<const uchar *>(maxpTable.constData() + 4));
 910 }
 911
 912 const uchar *QFontEngine::getCMap(const uchar *table, uint tableSize, bool *isSymbolFont, int *cmapSize)
 913 {
 914     const uchar *header = table;
 915     if (tableSize < 4)
 916         return 0;
 917
 918     const uchar *endPtr = table + tableSize;
 919
 920     // version check
 921     if (qFromBigEndian<quint16>(header) != 0)
 922         return 0;
 923
 924     unsigned short numTables = qFromBigEndian<quint16>(header + 2);
 925     const uchar *maps = table + 4;
 926     if (maps + 8 * numTables > endPtr)
 927         return 0;
 928
 929     enum {
 930         Invalid,
 931         AppleRoman,
 932         Symbol,
 933         Unicode11,
 934         Unicode,
 935         MicrosoftUnicode,
 936         MicrosoftUnicodeExtended
 937     };
 938
 939     int symbolTable = -1;
 940     int tableToUse = -1;
 941     int score = Invalid;
 942     for (int n = 0; n < numTables; ++n) {
 943         const quint16 platformId = qFromBigEndian<quint16>(maps + 8 * n);
 944         const quint16 platformSpecificId = qFromBigEndian<quint16>(maps + 8 * n + 2);
 945         switch (platformId) {
 946         case 0: // Unicode
 947             if (score < Unicode &&
 948                 (platformSpecificId == 0 ||
 949                  platformSpecificId == 2 ||
 950                  platformSpecificId == 3)) {
 951                 tableToUse = n;
 952                 score = Unicode;
 953             } else if (score < Unicode11 && platformSpecificId == 1) {
 954                 tableToUse = n;
 955                 score = Unicode11;
 956             }
 957             break;
 958         case 1: // Apple
 959             if (score < AppleRoman && platformSpecificId == 0) { // Apple Roman
 960                 tableToUse = n;
 961                 score = AppleRoman;
 962             }
 963             break;
 964         case 3: // Microsoft
 965             switch (platformSpecificId) {
 966             case 0:
 967                 symbolTable = n;
 968                 if (score < Symbol) {
 969                     tableToUse = n;
 970                     score = Symbol;
 971                 }
 972                 break;
 973             case 1:
 974                 if (score < MicrosoftUnicode) {
 975                     tableToUse = n;
 976                     score = MicrosoftUnicode;
 977                 }
 978                 break;
 979             case 0xa:
 980                 if (score < MicrosoftUnicodeExtended) {
 981                     tableToUse = n;
 982                     score = MicrosoftUnicodeExtended;
 983                 }
 984                 break;
 985             default:
 986                 break;
 987             }
 988         default:
 989             break;
 990         }
 991     }
 992     if(tableToUse < 0)
 993         return 0;
 994
 995 resolveTable:
 996     *isSymbolFont = (symbolTable > -1);
 997
 998     unsigned int unicode_table = qFromBigEndian<quint32>(maps + 8*tableToUse + 4);
 999
1000     if (!unicode_table || unicode_table + 8 > tableSize)
1001         return 0;
1002
1003     // get the header of the unicode table
1004     header = table + unicode_table;
1005
1006     unsigned short format = qFromBigEndian<quint16>(header);
1007     unsigned int length;
1008     if(format < 8)
1009         length = qFromBigEndian<quint16>(header + 2);
1010     else
1011         length = qFromBigEndian<quint32>(header + 4);
1012
1013     if (table + unicode_table + length > endPtr)
1014         return 0;
1015     *cmapSize = length;
1016
1017     // To support symbol fonts that contain a unicode table for the symbol area
1018     // we check the cmap tables and fall back to symbol font unless that would
1019     // involve losing information from the unicode table
1020     if (symbolTable > -1 && ((score == Unicode) || (score == Unicode11))) {
1021         const uchar *selectedTable = table + unicode_table;
1022
1023         // Check that none of the latin1 range are in the unicode table
1024         bool unicodeTableHasLatin1 = false;
1025         for (int uc=0x00; uc<0x100; ++uc) {
1026             if (getTrueTypeGlyphIndex(selectedTable, uc) != 0) {
1027                 unicodeTableHasLatin1 = true;
1028                 break;
1029             }
1030         }
1031
1032         // Check that at least one symbol char is in the unicode table
1033         bool unicodeTableHasSymbols = false;
1034         if (!unicodeTableHasLatin1) {
1035             for (int uc=0xf000; uc<0xf100; ++uc) {
1036                 if (getTrueTypeGlyphIndex(selectedTable, uc) != 0) {
1037                     unicodeTableHasSymbols = true;
1038                     break;
1039                 }
1040             }
1041         }
1042
1043         // Fall back to symbol table
1044         if (!unicodeTableHasLatin1 && unicodeTableHasSymbols) {
1045             tableToUse = symbolTable;
1046             score = Symbol;
1047             goto resolveTable;
1048         }
1049     }
1050
1051     return table + unicode_table;
1052 }
1053
1054 quint32 QFontEngine::getTrueTypeGlyphIndex(const uchar *cmap, uint unicode)
1055 {
1056     unsigned short format = qFromBigEndian<quint16>(cmap);
1057     if (format == 0) {
1058         if (unicode < 256)
1059             return (int) *(cmap+6+unicode);
1060     } else if (format == 4) {
1061         /* some fonts come with invalid cmap tables, where the last segment
1062            specified end = start = rangeoffset = 0xffff, delta = 0x0001
1063            Since 0xffff is never a valid Unicode char anyway, we just get rid of the issue
1064            by returning 0 for 0xffff
1065         */
1066         if(unicode >= 0xffff)
1067             return 0;
1068         quint16 segCountX2 = qFromBigEndian<quint16>(cmap + 6);
1069         const unsigned char *ends = cmap + 14;
1070         int i = 0;
1071         for (; i < segCountX2/2 && qFromBigEndian<quint16>(ends + 2*i) < unicode; i++) {}
1072
1073         const unsigned char *idx = ends + segCountX2 + 2 + 2*i;
1074         quint16 startIndex = qFromBigEndian<quint16>(idx);
1075
1076         if (startIndex > unicode)
1077             return 0;
1078
1079         idx += segCountX2;
1080         qint16 idDelta = (qint16)qFromBigEndian<quint16>(idx);
1081         idx += segCountX2;
1082         quint16 idRangeoffset_t = (quint16)qFromBigEndian<quint16>(idx);
1083
1084         quint16 glyphIndex;
1085         if (idRangeoffset_t) {
1086             quint16 id = qFromBigEndian<quint16>(idRangeoffset_t + 2*(unicode - startIndex) + idx);
1087             if (id)
1088                 glyphIndex = (idDelta + id) % 0x10000;
1089             else
1090                 glyphIndex = 0;
1091         } else {
1092             glyphIndex = (idDelta + unicode) % 0x10000;
1093         }
1094         return glyphIndex;
1095     } else if (format == 6) {
1096         quint16 tableSize = qFromBigEndian<quint16>(cmap + 2);
1097
1098         quint16 firstCode6 = qFromBigEndian<quint16>(cmap + 6);
1099         if (unicode < firstCode6)
1100             return 0;
1101
1102         quint16 entryCount6 = qFromBigEndian<quint16>(cmap + 8);
1103         if (entryCount6 * 2 + 10 > tableSize)
1104             return 0;
1105
1106         quint16 sentinel6 = firstCode6 + entryCount6;
1107         if (unicode >= sentinel6)
1108             return 0;
1109
1110         quint16 entryIndex6 = unicode - firstCode6;
1111         return qFromBigEndian<quint16>(cmap + 10 + (entryIndex6 * 2));
1112     } else if (format == 12) {
1113         quint32 nGroups = qFromBigEndian<quint32>(cmap + 12);
1114
1115         cmap += 16; // move to start of groups
1116
1117         int left = 0, right = nGroups - 1;
1118         while (left <= right) {
1119             int middle = left + ( ( right - left ) >> 1 );
1120
1121             quint32 startCharCode = qFromBigEndian<quint32>(cmap + 12*middle);
1122             if(unicode < startCharCode)
1123                 right = middle - 1;
1124             else {
1125                 quint32 endCharCode = qFromBigEndian<quint32>(cmap + 12*middle + 4);
1126                 if(unicode <= endCharCode)
1127                     return qFromBigEndian<quint32>(cmap + 12*middle + 8) + unicode - startCharCode;
1128                 left = middle + 1;
1129             }
1130         }
1131     } else {
1132         qDebug("cmap table of format %d not implemented", format);
1133     }
1134
1135     return 0;
1136 }
1137
1138 QByteArray QFontEngine::convertToPostscriptFontFamilyName(const QByteArray &family)
1139 {
1140     QByteArray f = family;
1141     f.replace(' ', "");
1142     f.replace('(', "");
1143     f.replace(')', "");
1144     f.replace('<', "");
1145     f.replace('>', "");
1146     f.replace('[', "");
1147     f.replace(']', "");
1148     f.replace('{', "");
1149     f.replace('}', "");
1150     f.replace('/', "");
1151     f.replace('%', "");
1152     return f;
1153 }
1154
1155 class QRgbGreyPalette: public QVector<QRgb>
1156 {
1157 public:
1158     QRgbGreyPalette()
1159     {
1160         resize(256);
1161         QRgb *it = data();
1162         for (int i = 0; i < size(); ++i, ++it)
1163             *it = 0xff000000 | i | (i<<8) | (i<<16);
1164     }
1165 };
1166
1167 Q_GLOBAL_STATIC(QVector<QRgb>, qt_grayPalette)
1168
1169 const QVector<QRgb> &QFontEngine::grayPalette()
1170 {
1171     return *qt_grayPalette();
1172 }
1173
1174 QFixed QFontEngine::lastRightBearing(const QGlyphLayout &glyphs, bool round)
1175 {
1176     if (glyphs.numGlyphs >= 1) {
1177         glyph_t glyph = glyphs.glyphs[glyphs.numGlyphs - 1];
1178         glyph_metrics_t gi = boundingBox(glyph);
1179         if (gi.isValid())
1180             return round ? QFixed(qRound(gi.xoff - gi.x - gi.width))
1181                          : QFixed(gi.xoff - gi.x - gi.width);
1182     }
1183     return 0;
1184 }
1185
1186 // ------------------------------------------------------------------
1187 // The box font engine
1188 // ------------------------------------------------------------------
1189
1190 QFontEngineBox::QFontEngineBox(int size)
1191     : _size(size)
1192 {
1193     cache_cost = sizeof(QFontEngineBox);
1194 }
1195
1196 QFontEngineBox::~QFontEngineBox()
1197 {
1198 }
1199
1200 bool QFontEngineBox::stringToCMap(const QChar *, int len, QGlyphLayout *glyphs, int *nglyphs, QTextEngine::ShaperFlags) const
1201 {
1202     if (*nglyphs < len) {
1203         *nglyphs = len;
1204         return false;
1205     }
1206
1207     for (int i = 0; i < len; i++) {
1208         glyphs->glyphs[i] = 0;
1209         glyphs->advances_x[i] = _size;
1210         glyphs->advances_y[i] = 0;
1211     }
1212
1213     *nglyphs = len;
1214     glyphs->numGlyphs = len;
1215     return true;
1216 }
1217
1218 void QFontEngineBox::recalcAdvances(QGlyphLayout *glyphs, QTextEngine::ShaperFlags) const
1219 {
1220     for (int i = 0; i < glyphs->numGlyphs; i++) {
1221         glyphs->advances_x[i] = _size;
1222         glyphs->advances_y[i] = 0;
1223     }
1224 }
1225
1226 void QFontEngineBox::addOutlineToPath(qreal x, qreal y, const QGlyphLayout &glyphs, QPainterPath *path, QTextItem::RenderFlags flags)
1227 {
1228     if (!glyphs.numGlyphs)
1229         return;
1230
1231     QVarLengthArray<QFixedPoint> positions;
1232     QVarLengthArray<glyph_t> positioned_glyphs;
1233     QTransform matrix = QTransform::fromTranslate(x, y - _size);
1234     getGlyphPositions(glyphs, matrix, flags, positioned_glyphs, positions);
1235
1236     QSize s(_size - 3, _size - 3);
1237     for (int k = 0; k < positions.size(); k++)
1238         path->addRect(QRectF(positions[k].toPointF(), s));
1239 }
1240
1241 glyph_metrics_t QFontEngineBox::boundingBox(const QGlyphLayout &glyphs)
1242 {
1243     glyph_metrics_t overall;
1244     overall.width = _size*glyphs.numGlyphs;
1245     overall.height = _size;
1246     overall.xoff = overall.width;
1247     return overall;
1248 }
1249
1250 #if defined(Q_WS_QWS) || defined(Q_WS_QPA)
1251 void QFontEngineBox::draw(QPaintEngine *p, qreal x, qreal y, const QTextItemInt &ti)
1252 {
1253     if (!ti.glyphs.numGlyphs)
1254         return;
1255
1256     // any fixes here should probably also be done in QPaintEnginePrivate::drawBoxTextItem
1257     QSize s(_size - 3, _size - 3);
1258
1259     QVarLengthArray<QFixedPoint> positions;
1260     QVarLengthArray<glyph_t> glyphs;
1261     QTransform matrix = QTransform::fromTranslate(x, y - _size);
1262     ti.fontEngine->getGlyphPositions(ti.glyphs, matrix, ti.flags, glyphs, positions);
1263     if (glyphs.size() == 0)
1264         return;
1265
1266
1267     QPainter *painter = p->painter();
1268     painter->save();
1269     painter->setBrush(Qt::NoBrush);
1270     QPen pen = painter->pen();
1271     pen.setWidthF(lineThickness().toReal());
1272     painter->setPen(pen);
1273     for (int k = 0; k < positions.size(); k++)
1274         painter->drawRect(QRectF(positions[k].toPointF(), s));
1275     painter->restore();
1276 }
1277 #endif
1278
1279 glyph_metrics_t QFontEngineBox::boundingBox(glyph_t)
1280 {
1281     return glyph_metrics_t(0, -_size, _size, _size, _size, 0);
1282 }
1283
1284
1285
1286 QFixed QFontEngineBox::ascent() const
1287 {
1288     return _size;
1289 }
1290
1291 QFixed QFontEngineBox::descent() const
1292 {
1293     return 0;
1294 }
1295
1296 QFixed QFontEngineBox::leading() const
1297 {
1298     QFixed l = _size * QFixed::fromReal(qreal(0.15));
1299     return l.ceil();
1300 }
1301
1302 qreal QFontEngineBox::maxCharWidth() const
1303 {
1304     return _size;
1305 }
1306
1307 #ifdef Q_WS_X11
1308 int QFontEngineBox::cmap() const
1309 {
1310     return -1;
1311 }
1312 #endif
1313
1314 const char *QFontEngineBox::name() const
1315 {
1316     return "null";
1317 }
1318
1319 bool QFontEngineBox::canRender(const QChar *, int)
1320 {
1321     return true;
1322 }
1323
1324 QFontEngine::Type QFontEngineBox::type() const
1325 {
1326     return Box;
1327 }
1328
1329 QImage QFontEngineBox::alphaMapForGlyph(glyph_t)
1330 {
1331     QImage image(_size, _size, QImage::Format_Indexed8);
1332     QVector<QRgb> colors(256);
1333     for (int i=0; i<256; ++i)
1334         colors[i] = qRgba(0, 0, 0, i);
1335     image.setColorTable(colors);
1336     image.fill(0);
1337
1338     // can't use qpainter for index8; so use setPixel to draw our rectangle.
1339     for (int i=2; i <= _size-3; ++i) {
1340         image.setPixel(i, 2, 255);
1341         image.setPixel(i, _size-3, 255);
1342         image.setPixel(2, i, 255);
1343         image.setPixel(_size-3, i, 255);
1344     }
1345     return image;
1346 }
1347
1348 // ------------------------------------------------------------------
1349 // Multi engine
1350 // ------------------------------------------------------------------
1351
1352 static inline uchar highByte(glyph_t glyph)
1353 { return glyph >> 24; }
1354
1355 // strip high byte from glyph
1356 static inline glyph_t stripped(glyph_t glyph)
1357 { return glyph & 0x00ffffff; }
1358
1359 QFontEngineMulti::QFontEngineMulti(int engineCount)
1360 {
1361     engines.fill(0, engineCount);
1362     cache_cost = 0;
1363 }
1364
1365 QFontEngineMulti::~QFontEngineMulti()
1366 {
1367     for (int i = 0; i < engines.size(); ++i) {
1368         QFontEngine *fontEngine = engines.at(i);
1369         if (fontEngine) {
1370             fontEngine->ref.deref();
1371             if (fontEngine->cache_count == 0 && fontEngine->ref == 0)
1372                 delete fontEngine;
1373         }
1374     }
1375 }
1376
1377 bool QFontEngineMulti::stringToCMap(const QChar *str, int len,
1378                                     QGlyphLayout *glyphs, int *nglyphs,
1379                                     QTextEngine::ShaperFlags flags) const
1380 {
1381     int ng = *nglyphs;
1382     if (!engine(0)->stringToCMap(str, len, glyphs, &ng, flags))
1383         return false;
1384
1385     int glyph_pos = 0;
1386     for (int i = 0; i < len; ++i) {
1387         bool surrogate = (str[i].isHighSurrogate() && i < len-1 && str[i+1].isLowSurrogate());
1388
1389         if (glyphs->glyphs[glyph_pos] == 0 && str[i].category() != QChar::Separator_Line) {
1390             QGlyphLayoutInstance tmp = glyphs->instance(glyph_pos);
1391             for (int x = 1; x < engines.size(); ++x) {
1392                 QFontEngine *engine = engines.at(x);
1393                 if (!engine) {
1394                     const_cast<QFontEngineMulti *>(this)->loadEngine(x);
1395                     engine = engines.at(x);
1396                 }
1397                 Q_ASSERT(engine != 0);
1398                 if (engine->type() == Box)
1399                     continue;
1400                 glyphs->advances_x[glyph_pos] = glyphs->advances_y[glyph_pos] = 0;
1401                 glyphs->offsets[glyph_pos] = QFixedPoint();
1402                 int num = 2;
1403                 QGlyphLayout offs = glyphs->mid(glyph_pos, num);
1404                 engine->stringToCMap(str + i, surrogate ? 2 : 1, &offs, &num, flags);
1405                 Q_ASSERT(num == 1); // surrogates only give 1 glyph
1406                 if (glyphs->glyphs[glyph_pos]) {
1407                     // set the high byte to indicate which engine the glyph came from
1408                     glyphs->glyphs[glyph_pos] |= (x << 24);
1409                     break;
1410                 }
1411             }
1412             // ensure we use metrics from the 1st font when we use the fallback image.
1413             if (!glyphs->glyphs[glyph_pos]) {
1414                 glyphs->setInstance(glyph_pos, tmp);
1415             }
1416         }
1417         if (surrogate)
1418             ++i;
1419         ++glyph_pos;
1420     }
1421
1422     *nglyphs = ng;
1423     glyphs->numGlyphs = ng;
1424     return true;
1425 }
1426
1427 glyph_metrics_t QFontEngineMulti::boundingBox(const QGlyphLayout &glyphs)
1428 {
1429     if (glyphs.numGlyphs <= 0)
1430         return glyph_metrics_t();
1431
1432     glyph_metrics_t overall;
1433
1434     int which = highByte(glyphs.glyphs[0]);
1435     int start = 0;
1436     int end, i;
1437     for (end = 0; end < glyphs.numGlyphs; ++end) {
1438         const int e = highByte(glyphs.glyphs[end]);
1439         if (e == which)
1440             continue;
1441
1442         // set the high byte to zero
1443         for (i = start; i < end; ++i)
1444             glyphs.glyphs[i] = stripped(glyphs.glyphs[i]);
1445
1446         // merge the bounding box for this run
1447         const glyph_metrics_t gm = engine(which)->boundingBox(glyphs.mid(start, end - start));
1448
1449         overall.x = qMin(overall.x, gm.x);
1450         overall.y = qMin(overall.y, gm.y);
1451         overall.width = overall.xoff + gm.width;
1452         overall.height = qMax(overall.height + overall.y, gm.height + gm.y) -
1453                          qMin(overall.y, gm.y);
1454         overall.xoff += gm.xoff;
1455         overall.yoff += gm.yoff;
1456
1457         // reset the high byte for all glyphs
1458         const int hi = which << 24;
1459         for (i = start; i < end; ++i)
1460             glyphs.glyphs[i] = hi | glyphs.glyphs[i];
1461
1462         // change engine
1463         start = end;
1464         which = e;
1465     }
1466
1467     // set the high byte to zero
1468     for (i = start; i < end; ++i)
1469         glyphs.glyphs[i] = stripped(glyphs.glyphs[i]);
1470
1471     // merge the bounding box for this run
1472     const glyph_metrics_t gm = engine(which)->boundingBox(glyphs.mid(start, end - start));
1473
1474     overall.x = qMin(overall.x, gm.x);
1475     overall.y = qMin(overall.y, gm.y);
1476     overall.width = overall.xoff + gm.width;
1477     overall.height = qMax(overall.height + overall.y, gm.height + gm.y) -
1478                      qMin(overall.y, gm.y);
1479     overall.xoff += gm.xoff;
1480     overall.yoff += gm.yoff;
1481
1482     // reset the high byte for all glyphs
1483     const int hi = which << 24;
1484     for (i = start; i < end; ++i)
1485         glyphs.glyphs[i] = hi | glyphs.glyphs[i];
1486
1487     return overall;
1488 }
1489
1490 void QFontEngineMulti::getGlyphBearings(glyph_t glyph, qreal *leftBearing, qreal *rightBearing)
1491 {
1492     int which = highByte(glyph);
1493     engine(which)->getGlyphBearings(stripped(glyph), leftBearing, rightBearing);
1494 }
1495
1496 void QFontEngineMulti::addOutlineToPath(qreal x, qreal y, const QGlyphLayout &glyphs,
1497                                         QPainterPath *path, QTextItem::RenderFlags flags)
1498 {
1499     if (glyphs.numGlyphs <= 0)
1500         return;
1501
1502     int which = highByte(glyphs.glyphs[0]);
1503     int start = 0;
1504     int end, i;
1505     if (flags & QTextItem::RightToLeft) {
1506         for (int gl = 0; gl < glyphs.numGlyphs; gl++) {
1507             x += glyphs.advances_x[gl].toReal();
1508             y += glyphs.advances_y[gl].toReal();
1509         }
1510     }
1511     for (end = 0; end < glyphs.numGlyphs; ++end) {
1512         const int e = highByte(glyphs.glyphs[end]);
1513         if (e == which)
1514             continue;
1515
1516         if (flags & QTextItem::RightToLeft) {
1517             for (i = start; i < end; ++i) {
1518                 x -= glyphs.advances_x[i].toReal();
1519                 y -= glyphs.advances_y[i].toReal();
1520             }
1521         }
1522
1523         // set the high byte to zero
1524         for (i = start; i < end; ++i)
1525             glyphs.glyphs[i] = stripped(glyphs.glyphs[i]);
1526         engine(which)->addOutlineToPath(x, y, glyphs.mid(start, end - start), path, flags);
1527         // reset the high byte for all glyphs and update x and y
1528         const int hi = which << 24;
1529         for (i = start; i < end; ++i)
1530             glyphs.glyphs[i] = hi | glyphs.glyphs[i];
1531
1532         if (!(flags & QTextItem::RightToLeft)) {
1533             for (i = start; i < end; ++i) {
1534                 x += glyphs.advances_x[i].toReal();
1535                 y += glyphs.advances_y[i].toReal();
1536             }
1537         }
1538
1539         // change engine
1540         start = end;
1541         which = e;
1542     }
1543
1544     if (flags & QTextItem::RightToLeft) {
1545         for (i = start; i < end; ++i) {
1546             x -= glyphs.advances_x[i].toReal();
1547             y -= glyphs.advances_y[i].toReal();
1548         }
1549     }
1550
1551     // set the high byte to zero
1552     for (i = start; i < end; ++i)
1553         glyphs.glyphs[i] = stripped(glyphs.glyphs[i]);
1554
1555     engine(which)->addOutlineToPath(x, y, glyphs.mid(start, end - start), path, flags);
1556
1557     // reset the high byte for all glyphs
1558     const int hi = which << 24;
1559     for (i = start; i < end; ++i)
1560         glyphs.glyphs[i] = hi | glyphs.glyphs[i];
1561 }
1562
1563 void QFontEngineMulti::recalcAdvances(QGlyphLayout *glyphs, QTextEngine::ShaperFlags flags) const
1564 {
1565     if (glyphs->numGlyphs <= 0)
1566         return;
1567
1568     int which = highByte(glyphs->glyphs[0]);
1569     int start = 0;
1570     int end, i;
1571     for (end = 0; end < glyphs->numGlyphs; ++end) {
1572         const int e = highByte(glyphs->glyphs[end]);
1573         if (e == which)
1574             continue;
1575
1576         // set the high byte to zero
1577         for (i = start; i < end; ++i)
1578             glyphs->glyphs[i] = stripped(glyphs->glyphs[i]);
1579
1580         QGlyphLayout offs = glyphs->mid(start, end - start);
1581         engine(which)->recalcAdvances(&offs, flags);
1582
1583         // reset the high byte for all glyphs and update x and y
1584         const int hi = which << 24;
1585         for (i = start; i < end; ++i)
1586             glyphs->glyphs[i] = hi | glyphs->glyphs[i];
1587
1588         // change engine
1589         start = end;
1590         which = e;
1591     }
1592
1593     // set the high byte to zero
1594     for (i = start; i < end; ++i)
1595         glyphs->glyphs[i] = stripped(glyphs->glyphs[i]);
1596
1597     QGlyphLayout offs = glyphs->mid(start, end - start);
1598     engine(which)->recalcAdvances(&offs, flags);
1599
1600     // reset the high byte for all glyphs
1601     const int hi = which << 24;
1602     for (i = start; i < end; ++i)
1603         glyphs->glyphs[i] = hi | glyphs->glyphs[i];
1604 }
1605
1606 void QFontEngineMulti::doKerning(QGlyphLayout *glyphs, QTextEngine::ShaperFlags flags) const
1607 {
1608     if (glyphs->numGlyphs <= 0)
1609         return;
1610
1611     int which = highByte(glyphs->glyphs[0]);
1612     int start = 0;
1613     int end, i;
1614     for (end = 0; end < glyphs->numGlyphs; ++end) {
1615         const int e = highByte(glyphs->glyphs[end]);
1616         if (e == which)
1617             continue;
1618
1619         // set the high byte to zero
1620         for (i = start; i < end; ++i)
1621             glyphs->glyphs[i] = stripped(glyphs->glyphs[i]);
1622
1623         QGlyphLayout offs = glyphs->mid(start, end - start);
1624         engine(which)->doKerning(&offs, flags);
1625
1626         // reset the high byte for all glyphs and update x and y
1627         const int hi = which << 24;
1628         for (i = start; i < end; ++i)
1629             glyphs->glyphs[i] = hi | glyphs->glyphs[i];
1630
1631         // change engine
1632         start = end;
1633         which = e;
1634     }
1635
1636     // set the high byte to zero
1637     for (i = start; i < end; ++i)
1638         glyphs->glyphs[i] = stripped(glyphs->glyphs[i]);
1639
1640     QGlyphLayout offs = glyphs->mid(start, end - start);
1641     engine(which)->doKerning(&offs, flags);
1642
1643     // reset the high byte for all glyphs
1644     const int hi = which << 24;
1645     for (i = start; i < end; ++i)
1646         glyphs->glyphs[i] = hi | glyphs->glyphs[i];
1647 }
1648
1649 glyph_metrics_t QFontEngineMulti::boundingBox(glyph_t glyph)
1650 {
1651     const int which = highByte(glyph);
1652     Q_ASSERT(which < engines.size());
1653     return engine(which)->boundingBox(stripped(glyph));
1654 }
1655
1656 QFixed QFontEngineMulti::ascent() const
1657 { return engine(0)->ascent(); }
1658
1659 QFixed QFontEngineMulti::descent() const
1660 { return engine(0)->descent(); }
1661
1662 QFixed QFontEngineMulti::leading() const
1663 {
1664     return engine(0)->leading();
1665 }
1666
1667 QFixed QFontEngineMulti::xHeight() const
1668 {
1669     return engine(0)->xHeight();
1670 }
1671
1672 QFixed QFontEngineMulti::averageCharWidth() const
1673 {
1674     return engine(0)->averageCharWidth();
1675 }
1676
1677 QFixed QFontEngineMulti::lineThickness() const
1678 {
1679     return engine(0)->lineThickness();
1680 }
1681
1682 QFixed QFontEngineMulti::underlinePosition() const
1683 {
1684     return engine(0)->underlinePosition();
1685 }
1686
1687 qreal QFontEngineMulti::maxCharWidth() const
1688 {
1689     return engine(0)->maxCharWidth();
1690 }
1691
1692 qreal QFontEngineMulti::minLeftBearing() const
1693 {
1694     return engine(0)->minLeftBearing();
1695 }
1696
1697 qreal QFontEngineMulti::minRightBearing() const
1698 {
1699     return engine(0)->minRightBearing();
1700 }
1701
1702 bool QFontEngineMulti::canRender(const QChar *string, int len)
1703 {
1704     if (engine(0)->canRender(string, len))
1705         return true;
1706
1707     QVarLengthGlyphLayoutArray glyphs(len);
1708     int nglyphs = len;
1709     if (stringToCMap(string, len, &glyphs, &nglyphs, QTextEngine::GlyphIndicesOnly) == false) {
1710         glyphs.resize(nglyphs);
1711         stringToCMap(string, len, &glyphs, &nglyphs, QTextEngine::GlyphIndicesOnly);
1712     }
1713
1714     bool allExist = true;
1715     for (int i = 0; i < nglyphs; i++) {
1716         if (!glyphs.glyphs[i]) {
1717             allExist = false;
1718             break;
1719         }
1720     }
1721
1722     return allExist;
1723 }
1724
1725 /* Implement alphaMapForGlyph() which is called by Lighthouse/Windows code.
1726  * Ideally, that code should be fixed to correctly handle QFontEngineMulti. */
1727
1728 QImage QFontEngineMulti::alphaMapForGlyph(glyph_t glyph)
1729 {
1730     const int which = highByte(glyph);
1731     Q_ASSERT(which < engines.size());
1732     return engine(which)->alphaMapForGlyph(stripped(glyph));
1733 }
1734
1735 QImage QFontEngineMulti::alphaMapForGlyph(glyph_t glyph, QFixed subPixelPosition)
1736 {
1737     const int which = highByte(glyph);
1738     Q_ASSERT(which < engines.size());
1739     return engine(which)->alphaMapForGlyph(stripped(glyph), subPixelPosition);
1740 }
1741
1742 QImage QFontEngineMulti::alphaMapForGlyph(glyph_t glyph, const QTransform &t)
1743 {
1744     const int which = highByte(glyph);
1745     Q_ASSERT(which < engines.size());
1746     return engine(which)->alphaMapForGlyph(stripped(glyph), t);
1747 }
1748
1749 QImage QFontEngineMulti::alphaMapForGlyph(glyph_t glyph, QFixed subPixelPosition, const QTransform &t)
1750 {
1751     const int which = highByte(glyph);
1752     Q_ASSERT(which < engines.size());
1753     return engine(which)->alphaMapForGlyph(stripped(glyph), subPixelPosition, t);
1754 }
1755
1756 QImage QFontEngineMulti::alphaRGBMapForGlyph(glyph_t glyph, QFixed subPixelPosition, int margin, const QTransform &t)
1757 {
1758     const int which = highByte(glyph);
1759     Q_ASSERT(which < engines.size());
1760     return engine(which)->alphaRGBMapForGlyph(stripped(glyph), subPixelPosition, margin, t);
1761 }
1762
1763 QT_END_NAMESPACE