/*
 * Copyright (c) 2006, 2007, 2008, 2009, 2012 Google Inc. All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 * 
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include "core/platform/graphics/chromium/UniscribeHelper.h"

#include <windows.h>
#include "core/platform/graphics/Font.h"
#include "core/platform/graphics/GraphicsContext.h"
#include "core/platform/graphics/chromium/FontUtilsChromiumWin.h"
#include "core/platform/graphics/skia/SkiaFontWin.h"
#include "core/platform/win/HWndDC.h"
#include "third_party/skia/include/core/SkPoint.h"
#include <wtf/Assertions.h>

namespace WebCore {

// The function types for ScriptItemizeOpenType() and ScriptShapeOpenType().
// We want to use these functions for OpenType feature support, but we can't
// call them directly because usp10.dll does not always have them.
// Instead, we use GetProcAddress() to check whether we can actually use these
// function. If we can't use these functions, we substitute ScriptItemze() and
// ScriptShape().
typedef HRESULT (WINAPI *ScriptItemizeOpenTypeFunc)(const WCHAR*, int, int,
                                                    const SCRIPT_CONTROL*,
                                                    const SCRIPT_STATE*,
                                                    SCRIPT_ITEM*,
                                                    OPENTYPE_TAG*, int*);
typedef HRESULT (WINAPI *ScriptShapeOpenTypeFunc)(HDC, SCRIPT_CACHE*,
                                                  SCRIPT_ANALYSIS*,
                                                  OPENTYPE_TAG, OPENTYPE_TAG,
                                                  int*, TEXTRANGE_PROPERTIES**,
                                                  int, const WCHAR*, int, int,
                                                  WORD*, SCRIPT_CHARPROP*,
                                                  WORD*, SCRIPT_GLYPHPROP*,
                                                  int*);

static ScriptItemizeOpenTypeFunc gScriptItemizeOpenTypeFunc = 0;
static ScriptShapeOpenTypeFunc gScriptShapeOpenTypeFunc = 0;
static bool gOpenTypeFunctionsLoaded = false;

static void loadOpenTypeFunctions()
{
    HMODULE hModule = GetModuleHandle(L"usp10");
    if (hModule) {
        gScriptItemizeOpenTypeFunc = reinterpret_cast<ScriptItemizeOpenTypeFunc>(GetProcAddress(hModule, "ScriptItemizeOpenType"));
        gScriptShapeOpenTypeFunc = reinterpret_cast<ScriptShapeOpenTypeFunc>(GetProcAddress(hModule, "ScriptShapeOpenType"));
    }
    if (!gScriptItemizeOpenTypeFunc || !gScriptShapeOpenTypeFunc) {
        gScriptItemizeOpenTypeFunc = 0;
        gScriptShapeOpenTypeFunc = 0;
    }
    gOpenTypeFunctionsLoaded = true;
}

// HFONT is the 'incarnation' of 'everything' about font, but it's an opaque
// handle and we can't directly query it to make a new HFONT sharing
// its characteristics (height, style, etc) except for family name.
// This function uses GetObject to convert HFONT back to LOGFONT,
// resets the fields of LOGFONT and calculates style to use later
// for the creation of a font identical to HFONT other than family name.
static void setLogFontAndStyle(HFONT hfont, LOGFONT *logfont, int *style)
{
    ASSERT(hfont && logfont);
    if (!hfont || !logfont)
        return;

    GetObject(hfont, sizeof(LOGFONT), logfont);
    // We reset these fields to values appropriate for CreateFontIndirect.
    // while keeping lfHeight, which is the most important value in creating
    // a new font similar to hfont.
    logfont->lfWidth = 0;
    logfont->lfEscapement = 0;
    logfont->lfOrientation = 0;
    logfont->lfCharSet = DEFAULT_CHARSET;
    logfont->lfOutPrecision = OUT_TT_ONLY_PRECIS;
    logfont->lfQuality = DEFAULT_QUALITY;  // Honor user's desktop settings.
    logfont->lfPitchAndFamily = DEFAULT_PITCH | FF_DONTCARE;
    if (style)
        *style = getStyleFromLogfont(logfont);
}

// This memory DC will NOT be released but it's OK
// since we want to keep it for the whole life span of the process.
HDC UniscribeHelper::m_cachedDC = 0;

static bool canUseGlyphIndex(const SCRIPT_ITEM& run)
{
    // On early version of Uniscribe, ScriptShape() sets run.a.fNoGlyphIndex
    // to TRUE when it can't shape the run with glyph indexes. This could
    // occur when we use CFF webfonts(See http://crbug.com/39017).
    // We don't use the font in that case and try to use fallback fonts.
    return !run.a.fNoGlyphIndex;
}

UniscribeHelper::UniscribeHelper(const UChar* input,
                                int inputLength,
                                bool isRtl,
                                HFONT hfont,
                                SCRIPT_CACHE* scriptCache,
                                SCRIPT_FONTPROPERTIES* fontProperties,
                                WORD spaceGlyph)
    : m_input(input)
    , m_inputLength(inputLength)
    , m_isRtl(isRtl)
    , m_hfont(hfont)
    , m_scriptCache(scriptCache)
    , m_fontProperties(fontProperties)
    , m_spaceGlyph(spaceGlyph)
    , m_directionalOverride(false)
    , m_inhibitLigate(false)
    , m_letterSpacing(0)
    , m_spaceWidth(0)
    , m_wordSpacing(0)
    , m_ascent(0)
    , m_disableFontFallback(false)

{
    m_logfont.lfFaceName[0] = 0;
    if (!gOpenTypeFunctionsLoaded)
        loadOpenTypeFunctions();
}

UniscribeHelper::~UniscribeHelper()
{
}

void UniscribeHelper::initWithOptionalLengthProtection(bool lengthProtection)
{
    // We cap the input length and just don't do anything. We'll allocate a lot
    // of things of the size of the number of characters, so the allocated
    // memory will be several times the input length. Plus shaping such a large
    // buffer may be a form of denial of service. No legitimate text should be
    // this long.  It also appears that Uniscribe flatly rejects very long
    // strings, so we don't lose anything by doing this.
    //
    // The input length protection may be disabled by the unit tests to cause
    // an error condition.
    static const int kMaxInputLength = 65535;
    if (m_inputLength == 0 || (lengthProtection && m_inputLength > kMaxInputLength))
        return;

    fillRuns();
    fillShapes();
    fillScreenOrder();
}

int UniscribeHelper::width() const
{
    int width = 0;
    for (int itemIndex = 0; itemIndex < static_cast<int>(m_runs.size()); itemIndex++)
        width += advanceForItem(itemIndex);
    return width;
}

void UniscribeHelper::justify(int additionalSpace)
{
    // Count the total number of glyphs we have so we know how big to make the
    // buffers below.
    int totalGlyphs = 0;
    for (size_t run = 0; run < m_runs.size(); run++) {
        int runIndex = m_screenOrder[run];
        totalGlyphs += static_cast<int>(m_shapes[runIndex].glyphLength());
    }
    if (totalGlyphs == 0)
        return;  // Nothing to do.

    // We make one big buffer in screen order of all the glyphs we are drawing
    // across runs so that the justification function will adjust evenly across
    // all glyphs.
    Vector<SCRIPT_VISATTR, 64> visualAttributes;
    visualAttributes.resize(totalGlyphs);
    Vector<int, 64> advances;
    advances.resize(totalGlyphs);
    Vector<int, 64> justify;
    justify.resize(totalGlyphs);

    // Build the packed input.
    int destIndex = 0;
    for (size_t run = 0; run < m_runs.size(); run++) {
        int runIndex = m_screenOrder[run];
        const Shaping& shaping = m_shapes[runIndex];

        for (int i = 0; i < shaping.glyphLength(); i++, destIndex++) {
            memcpy(&visualAttributes[destIndex], &shaping.m_visualAttributes[i],
                   sizeof(SCRIPT_VISATTR));
            advances[destIndex] = shaping.m_advance[i];
        }
    }

    // The documentation for Scriptjustify is wrong, the parameter is the space
    // to add and not the width of the column you want.
    int minKashida;
    // Disable kashida justification based on 
    // http://blogs.msdn.com/b/michkap/archive/2010/08/31/10056140.aspx.
    for (int i = 0; i < totalGlyphs; ++i) {
        if (visualAttributes[i].uJustification == SCRIPT_JUSTIFY_ARABIC_KASHIDA)
            visualAttributes[i].uJustification = SCRIPT_JUSTIFY_NONE;   
    }
    minKashida = 0;
    ScriptJustify(&visualAttributes[0], &advances[0], totalGlyphs,
                  additionalSpace, minKashida, &justify[0]);

    // Now we have to unpack the justification amounts back into the runs so
    // the glyph indices match.
    int globalGlyphIndex = 0;
    for (size_t run = 0; run < m_runs.size(); run++) {
        int runIndex = m_screenOrder[run];
        Shaping& shaping = m_shapes[runIndex];

        shaping.m_justify.resize(shaping.glyphLength());
        for (int i = 0; i < shaping.glyphLength(); i++, globalGlyphIndex++)
            shaping.m_justify[i] = justify[globalGlyphIndex];
    }
}

int UniscribeHelper::characterToX(int offset) const
{
    HRESULT hr;
    ASSERT(offset <= m_inputLength);

    // Our algorithm is to traverse the items in screen order from left to
    // right, adding in each item's screen width until we find the item with
    // the requested character in it.
    int width = 0;
    for (size_t screenIndex = 0; screenIndex < m_runs.size(); screenIndex++) {
        // Compute the length of this run.
        int itemIndex = m_screenOrder[screenIndex];
        const SCRIPT_ITEM& item = m_runs[itemIndex];
        const Shaping& shaping = m_shapes[itemIndex];
        int itemLength = shaping.charLength();

        if (offset >= item.iCharPos && offset <= item.iCharPos + itemLength) {
            // Character offset is in this run.
            int charLength = offset - item.iCharPos;

            int curX = 0;
            hr = ScriptCPtoX(charLength, FALSE, itemLength,
                             shaping.glyphLength(),
                             &shaping.m_logs[0], &shaping.m_visualAttributes[0],
                             shaping.effectiveAdvances(), &item.a, &curX);
            if (FAILED(hr))
                return 0;

            width += curX + shaping.m_prePadding;
            ASSERT(width >= 0);
            return width;
        }

        // Move to the next item.
        width += advanceForItem(itemIndex);
    }
    ASSERT(width >= 0);
    return width;
}

int UniscribeHelper::xToCharacter(int x) const
{
    // We iterate in screen order until we find the item with the given pixel
    // position in it. When we find that guy, we ask Uniscribe for the
    // character index.
    HRESULT hr;
    for (size_t screenIndex = 0; screenIndex < m_runs.size(); screenIndex++) {
        int itemIndex = m_screenOrder[screenIndex];
        int itemAdvance = advanceForItem(itemIndex);

        // Note that the run may be empty if shaping failed, so we want to skip
        // over it.
        const Shaping& shaping = m_shapes[itemIndex];
        int itemLength = shaping.charLength();
        if (x <= itemAdvance && itemLength > 0) {
            // The requested offset is within this item.
            const SCRIPT_ITEM& item = m_runs[itemIndex];

            // Account for the leading space we've added to this run that
            // Uniscribe doesn't know about.
            x -= shaping.m_prePadding;

            int charX = 0;
            int trailing;
            hr = ScriptXtoCP(x, itemLength, shaping.glyphLength(),
                             &shaping.m_logs[0], &shaping.m_visualAttributes[0],
                             shaping.effectiveAdvances(), &item.a, &charX,
                             &trailing);

            // The character offset is within the item. We need to add the
            // item's offset to transform it into the space of the TextRun
            return charX + item.iCharPos;
        }

        // The offset is beyond this item, account for its length and move on.
        x -= itemAdvance;
    }

    // Error condition, we don't know what to do if we don't have that X
    // position in any of our items.
    return 0;
}

void UniscribeHelper::draw(GraphicsContext* graphicsContext, HDC dc,
                           int x, int y,
                           const FloatRect& textRect,
                           int from, int to)
{
    HGDIOBJ oldFont = 0;
    int curX = x;
    bool firstRun = true;

    for (size_t screenIndex = 0; screenIndex < m_runs.size(); screenIndex++) {
        int itemIndex = m_screenOrder[screenIndex];
        const SCRIPT_ITEM& item = m_runs[itemIndex];
        const Shaping& shaping = m_shapes[itemIndex];

        // Character offsets within this run. THESE MAY NOT BE IN RANGE and may
        // be negative, etc. The code below handles this.
        int fromChar = from - item.iCharPos;
        int toChar = to - item.iCharPos;

        // See if we need to draw any characters in this item.
        if (shaping.charLength() == 0 ||
            fromChar >= shaping.charLength() || toChar <= 0) {
            // No chars in this item to display.
            curX += advanceForItem(itemIndex);
            continue;
        }

        // Compute the starting glyph within this span. |from| and |to| are
        // global offsets that may intersect arbitrarily with our local run.
        int fromGlyph, afterGlyph;
        if (item.a.fRTL) {
            // To compute the first glyph when going RTL, we use |to|.
            if (toChar >= shaping.charLength())
                // The end of the text is after (to the left) of us.
                fromGlyph = 0;
            else {
                // Since |to| is exclusive, the first character we draw on the
                // left is actually the one right before (to the right) of
                // |to|.
                fromGlyph = shaping.m_logs[toChar - 1];
            }

            // The last glyph is actually the first character in the range.
            if (fromChar <= 0) {
                // The first character to draw is before (to the right) of this
                // span, so draw all the way to the end.
                afterGlyph = shaping.glyphLength();
            } else {
                // We want to draw everything up until the character to the
                // right of |from|. To the right is - 1, so we look that up
                // (remember our character could be more than one glyph, so we
                // can't look up our glyph and add one).
                afterGlyph = shaping.m_logs[fromChar - 1];
            }
        } else {
            // Easy case, everybody agrees about directions. We only need to
            // handle boundary conditions to get a range inclusive at the
            // beginning, and exclusive at the ending. We have to do some
            // computation to see the glyph one past the end.
            fromGlyph = shaping.m_logs[fromChar < 0 ? 0 : fromChar];
            if (toChar >= shaping.charLength())
                afterGlyph = shaping.glyphLength();
            else
                afterGlyph = shaping.m_logs[toChar];
        }

        // Account for the characters that were skipped in this run. When
        // WebKit asks us to draw a subset of the run, it actually tells us
        // to draw at the X offset of the beginning of the run, since it
        // doesn't know the internal position of any of our characters.
        const int* effectiveAdvances = shaping.effectiveAdvances();
        int innerOffset = 0;
        for (int i = 0; i < fromGlyph; i++)
            innerOffset += effectiveAdvances[i];

        // Actually draw the glyphs we found.
        int glyphCount = afterGlyph - fromGlyph;
        if (fromGlyph >= 0 && glyphCount > 0) {
            // Account for the preceding space we need to add to this run. We
            // don't need to count for the following space because that will be
            // counted in advanceForItem below when we move to the next run.
            innerOffset += shaping.m_prePadding;

            // Pass 0 in when there is no justification.
            const int* justify = shaping.m_justify.size() == 0 ? 0 : &shaping.m_justify[fromGlyph];

            const int* advances = shaping.m_justify.size() ?
                                      &shaping.m_justify[fromGlyph]
                                    : &shaping.m_advance[fromGlyph];

            // Fonts with different ascents can be used to render different
            // runs.  'Across-runs' y-coordinate correction needs to be
            // adjusted for each font.
            bool textOutOk = false;
            for (int executions = 0; executions < 2; ++executions) {
                SkPoint origin;
                origin.fX = curX + + innerOffset;
                origin.fY = y + m_ascent;
                paintSkiaText(graphicsContext,
                              shaping.m_hfont,
                              glyphCount,
                              &shaping.m_glyphs[fromGlyph],
                              advances,
                              &shaping.m_offsets[fromGlyph],
                              origin,
                              textRect);
                textOutOk = true;

                if (!textOutOk && 0 == executions) {
                    // If TextOut is called from the renderer it might fail
                    // because the sandbox is preventing it from opening the
                    // font files.  If we are running in the renderer,
                    // TryToPreloadFont is overridden to ask the browser to
                    // preload the font for us so we can access it.
                    tryToPreloadFont(shaping.m_hfont);
                    continue;
                }
                break;
            }
        }

        curX += advanceForItem(itemIndex);
    }

    if (oldFont)
        SelectObject(dc, oldFont);
}

WORD UniscribeHelper::firstGlyphForCharacter(int charOffset) const
{
    // Find the run for the given character.
    for (int i = 0; i < static_cast<int>(m_runs.size()); i++) {
        int firstChar = m_runs[i].iCharPos;
        const Shaping& shaping = m_shapes[i];
        int localOffset = charOffset - firstChar;
        if (localOffset >= 0 && localOffset < shaping.charLength()) {
            // The character is in this run, return the first glyph for it
            // (should generally be the only glyph). It seems Uniscribe gives
            // glyph 0 for empty, which is what we want to return in the
            // "missing" case.
            size_t glyphIndex = shaping.m_logs[localOffset];
            if (glyphIndex >= shaping.m_glyphs.size()) {
                // The glyph should be in this run, but the run has too few
                // actual characters. This can happen when shaping the run
                // fails, in which case, we should have no data in the logs at
                // all.
                ASSERT(shaping.m_glyphs.size() == 0);
                return 0;
            }
            return shaping.m_glyphs[glyphIndex];
        }
    }

    return 0;
}

void UniscribeHelper::fillRuns()
{
    HRESULT hr;
    m_runs.resize(cUniscribeHelperStackRuns);
    m_scriptTags.resize(cUniscribeHelperStackRuns);

    SCRIPT_STATE inputState;
    inputState.uBidiLevel = m_isRtl;
    inputState.fOverrideDirection = m_directionalOverride;
    inputState.fInhibitSymSwap = false;
    inputState.fCharShape = false;  // Not implemented in Uniscribe
    inputState.fDigitSubstitute = false;  // Do we want this for Arabic?
    inputState.fInhibitLigate = m_inhibitLigate;
    inputState.fDisplayZWG = false;  // Don't draw control characters.
    inputState.fArabicNumContext = m_isRtl;  // Do we want this for Arabic?
    inputState.fGcpClusters = false;
    inputState.fReserved = 0;
    inputState.fEngineReserved = 0;
    // The psControl argument to ScriptItemize should be non-0 for RTL text,
    // per http://msdn.microsoft.com/en-us/library/ms776532.aspx . So use a
    // SCRIPT_CONTROL that is set to all zeros.  Zero as a locale ID means the
    // neutral locale per http://msdn.microsoft.com/en-us/library/ms776294.aspx
    static SCRIPT_CONTROL inputControl = {0, // uDefaultLanguage    :16;
                                           0, // fContextDigits      :1;
                                           0, // fInvertPreBoundDir  :1;
                                           0, // fInvertPostBoundDir :1;
                                           0, // fLinkStringBefore   :1;
                                           0, // fLinkStringAfter    :1;
                                           0, // fNeutralOverride    :1;
                                           0, // fNumericOverride    :1;
                                           0, // fLegacyBidiClass    :1;
                                           0, // fMergeNeutralItems  :1;
                                           0};// fReserved           :7;
    // Calling ScriptApplyDigitSubstitution( 0, &inputControl, &inputState)
    // here would be appropriate if we wanted to set the language ID, and get
    // local digit substitution behavior.  For now, don't do it.

    while (true) {
        int numberOfItems = 0;

        // Ideally, we would have a way to know the runs before and after this
        // one, and put them into the control parameter of ScriptItemize. This
        // would allow us to shape characters properly that cross style
        // boundaries (WebKit bug 6148).
        //
        // We tell ScriptItemize that the output list of items is one smaller
        // than it actually is. According to Mozilla bug 366643, if there is
        // not enough room in the array on pre-SP2 systems, ScriptItemize will
        // write one past the end of the buffer.
        //
        // ScriptItemize is very strange. It will often require a much larger
        // ITEM buffer internally than it will give us as output. For example,
        // it will say a 16-item buffer is not big enough, and will write
        // interesting numbers into all those items. But when we give it a 32
        // item buffer and it succeeds, it only has one item output.
        //
        // It seems to be doing at least two passes, the first where it puts a
        // lot of intermediate data into our items, and the second where it
        // collates them.
        if (gScriptItemizeOpenTypeFunc) {
            hr = gScriptItemizeOpenTypeFunc(m_input, m_inputLength,
                                            static_cast<int>(m_runs.size()) - 1,
                                            &inputControl, &inputState,
                                            &m_runs[0], &m_scriptTags[0],
                                            &numberOfItems);

            if (SUCCEEDED(hr)) {
                // Pack consecutive runs, the script tag of which are
                // SCRIPT_TAG_UNKNOWN, to reduce the number of runs.
                for (int i = 0; i < numberOfItems; ++i) {
                    // Do not pack with whitespace characters at the head.
                    // Otherwise whole the run is rendered as a whitespace.
                    if (m_scriptTags[i] == SCRIPT_TAG_UNKNOWN && !Font::treatAsSpace(m_input[m_runs[i].iCharPos])) {
                        int j = 1;
                        while (i + j < numberOfItems && m_scriptTags[i + j] == SCRIPT_TAG_UNKNOWN)
                            ++j;
                        if (--j) {
                            m_runs.remove(i + 1, j);
                            m_scriptTags.remove(i + 1, j);
                            numberOfItems -= j;
                        }
                    }
                }
                m_scriptTags.resize(numberOfItems);
            }
        } else {
            hr = ScriptItemize(m_input, m_inputLength,
                               static_cast<int>(m_runs.size()) - 1,
                               &inputControl, &inputState, &m_runs[0],
                               &numberOfItems);
        }
        if (SUCCEEDED(hr)) {
            m_runs.resize(numberOfItems);
            break;
        }
        if (hr != E_OUTOFMEMORY) {
            // Some kind of unexpected error.
            m_runs.resize(0);
            break;
        }
        // There was not enough items for it to write into, expand.
        m_runs.resize(m_runs.size() * 2);
        m_scriptTags.resize(m_runs.size());
    }
}

bool UniscribeHelper::shape(const UChar* input,
                            int itemLength,
                            int numGlyphs,
                            SCRIPT_ITEM& run,
                            OPENTYPE_TAG scriptTag,
                            Shaping& shaping)
{
    HFONT hfont = m_hfont;
    SCRIPT_CACHE* scriptCache = m_scriptCache;
    SCRIPT_FONTPROPERTIES* fontProperties = m_fontProperties;
    Vector<SCRIPT_CHARPROP, cUniscribeHelperStackChars> charProps;
    Vector<SCRIPT_GLYPHPROP, cUniscribeHelperStackChars> glyphProps;
    int ascent = m_ascent;
    WORD spaceGlyph = m_spaceGlyph;
    HRESULT hr;
    // When used to fill up glyph pages for simple scripts in non-BMP,
    // we don't want any font fallback in this class. The simple script
    // font path can take care of font fallback.
    bool lastFallbackTried = m_disableFontFallback;
    bool result;

    int generatedGlyphs = 0;

    // In case HFONT passed in ctor cannot render this run, we have to scan
    // other fonts from the beginning of the font list.
    resetFontIndex();

    // Compute shapes.
    while (true) {
        shaping.m_logs.resize(itemLength);
        shaping.m_glyphs.resize(numGlyphs);
        shaping.m_visualAttributes.resize(numGlyphs);
        charProps.resize(itemLength);
        glyphProps.resize(numGlyphs);
        run.a.fNoGlyphIndex = FALSE;

#ifdef PURIFY
        // http://code.google.com/p/chromium/issues/detail?id=5309
        // Purify isn't able to track the assignments that ScriptShape makes to
        // shaping.m_glyphs. Consequently, any bytes with value 0xCD that it
        // writes, will be considered un-initialized data.
        //
        // This hack avoid the false-positive UMRs by marking the buffer as
        // initialized.
        //
        // FIXME: A better solution would be to use Purify's API and mark only
        // the populated range as initialized:
        //
        //     PurifyMarkAsInitialized(
        //         &shaping.m_glyphs[0],
        //         sizeof(shaping.m_glyphs[0] * generatedGlyphs);

        ZeroMemory(&shaping.m_glyphs[0],
                   sizeof(shaping.m_glyphs[0]) * shaping.m_glyphs.size());
#endif
        // If our DC is already created, select the font in it so we can use it now.
        // Otherwise, we'll create it as needed afterward...
        if (m_cachedDC)
            SelectObject(m_cachedDC, hfont);

        // Firefox sets SCRIPT_ANALYSIS.SCRIPT_STATE.fDisplayZWG to true
        // here. Is that what we want? It will display control characters.
        if (gScriptShapeOpenTypeFunc) {
            TEXTRANGE_PROPERTIES* rangeProps = m_featureRecords.size() ? &m_rangeProperties : 0;
            hr = gScriptShapeOpenTypeFunc(m_cachedDC, scriptCache, &run.a,
                                          scriptTag, 0, &itemLength,
                                          &rangeProps, rangeProps ? 1 : 0,
                                          input, itemLength, numGlyphs,
                                          &shaping.m_logs[0], &charProps[0],
                                          &shaping.m_glyphs[0], &glyphProps[0],
                                          &generatedGlyphs);
            if (SUCCEEDED(hr)) {
                // If we use ScriptShapeOpenType(), visual attributes
                // information for each characters are stored in
                // |glyphProps[i].sva|.
                for (int i = 0; i < generatedGlyphs; ++i)
                    memcpy(&shaping.m_visualAttributes[i], &glyphProps[i].sva, sizeof(SCRIPT_VISATTR));
            }
        } else {
            hr = ScriptShape(m_cachedDC, scriptCache, input, itemLength,
                             numGlyphs, &run.a,
                             &shaping.m_glyphs[0], &shaping.m_logs[0],
                             &shaping.m_visualAttributes[0], &generatedGlyphs);
        }
        // We receive E_PENDING when we need to try again with a Drawing Context,
        // but we don't want to retry again if we already tried with non-zero DC.
        if (hr == E_PENDING && !m_cachedDC) {
            EnsureCachedDCCreated();
            continue;
        }
        if (hr == E_OUTOFMEMORY) {
            numGlyphs *= 2;
            continue;
        }
        if (SUCCEEDED(hr) && (lastFallbackTried || !containsMissingGlyphs(shaping, run, fontProperties) && canUseGlyphIndex(run)))
            break;

        // The current font can't render this run, try next font.
        if (!m_disableFontFallback &&
            nextWinFontData(hfont, scriptCache, fontProperties, ascent, spaceGlyph)) {
            // The primary font does not support this run. Try next font.
            // In case of web page rendering, they come from fonts specified in
            // CSS stylesheets.
            continue;
        } else if (!lastFallbackTried) {
            lastFallbackTried = true;

            // Generate a last fallback font based on the script of
            // a character to draw while inheriting size and styles
            // from the primary font
            if (!m_logfont.lfFaceName[0])
                setLogFontAndStyle(m_hfont, &m_logfont, &m_style);

            // TODO(jungshik): generic type should come from webkit for
            // UniscribeHelperTextRun (a derived class used in webkit).
            const UChar *family = getFallbackFamily(input, itemLength,
                FontDescription::StandardFamily, 0, 0);
            bool fontOk = getDerivedFontData(family, m_style, &m_logfont,
                                             &ascent, &hfont, &scriptCache,
                                             &spaceGlyph);
                                              

            if (!fontOk) {
                // If this GetDerivedFontData is called from the renderer it
                // might fail because the sandbox is preventing it from opening
                // the font files.  If we are running in the renderer,
                // TryToPreloadFont is overridden to ask the browser to preload
                // the font for us so we can access it.
                tryToPreloadFont(hfont);

                // Try again.
                fontOk = getDerivedFontData(family, m_style, &m_logfont,
                                            &ascent, &hfont, &scriptCache,
                                            &spaceGlyph);
                ASSERT(fontOk);
            }

            // TODO(jungshik) : Currently GetDerivedHFont always returns a
            // a valid HFONT, but in the future, I may change it to return 0.
            ASSERT(hfont);

            // We don't need a font_properties for the last resort fallback font
            // because we don't have anything more to try and are forced to
            // accept empty glyph boxes. If we tried a series of fonts as
            // 'last-resort fallback', we'd need it, but currently, we don't.
            continue;
        } else if (hr == USP_E_SCRIPT_NOT_IN_FONT) {
            run.a.eScript = SCRIPT_UNDEFINED;
            continue;
        } else if (FAILED(hr)) {
            // Error shaping.
            generatedGlyphs = 0;
            result = false;
            goto cleanup;
        }
    }

    // Sets Windows font data for this run to those corresponding to
    // a font supporting this run. we don't need to store font_properties
    // because it's not used elsewhere.
    shaping.m_hfont = hfont;
    shaping.m_scriptCache = scriptCache;
    shaping.m_spaceGlyph = spaceGlyph;

    // The ascent of a font for this run can be different from
    // that of the primary font so that we need to keep track of
    // the difference per run and take that into account when calling
    // ScriptTextOut in |draw|. Otherwise, different runs rendered by
    // different fonts would not be aligned vertically.
    shaping.m_ascentOffset = m_ascent ? ascent - m_ascent : 0;
    result = true;

  cleanup:
    shaping.m_glyphs.resize(generatedGlyphs);
    shaping.m_visualAttributes.resize(generatedGlyphs);
    shaping.m_advance.resize(generatedGlyphs);
    shaping.m_offsets.resize(generatedGlyphs);

    // On failure, our logs don't mean anything, so zero those out.
    if (!result)
        shaping.m_logs.clear();

    return result;
}

void UniscribeHelper::EnsureCachedDCCreated()
{
    if (m_cachedDC)
        return;
    // Allocate a memory DC that is compatible with the Desktop DC since we don't have any window,
    // and we don't want to use the Desktop DC directly since it can have nasty side effects
    // as identified in Chrome Issue http://crbug.com/59315.
    HWndDC screenDC(0);
    m_cachedDC = ::CreateCompatibleDC(screenDC);
    ASSERT(m_cachedDC);
}

void UniscribeHelper::fillShapes()
{
    m_shapes.resize(m_runs.size());
    for (size_t i = 0; i < m_runs.size(); i++) {
        int startItem = m_runs[i].iCharPos;
        int itemLength = m_inputLength - startItem;
        if (i < m_runs.size() - 1)
            itemLength = m_runs[i + 1].iCharPos - startItem;

        int numGlyphs;
        if (itemLength < cUniscribeHelperStackChars) {
            // We'll start our buffer sizes with the current stack space
            // available in our buffers if the current input fits. As long as
            // it doesn't expand past that we'll save a lot of time mallocing.
            numGlyphs = cUniscribeHelperStackChars;
        } else {
            // When the input doesn't fit, give up with the stack since it will
            // almost surely not be enough room (unless the input actually
            // shrinks, which is unlikely) and just start with the length
            // recommended by the Uniscribe documentation as a "usually fits"
            // size.
            numGlyphs = itemLength * 3 / 2 + 16;
        }

        // Convert a string to a glyph string trying the primary font, fonts in
        // the fallback list and then script-specific last resort font.
        Shaping& shaping = m_shapes[i];
        if (!shape(&m_input[startItem], itemLength, numGlyphs, m_runs[i], m_scriptTags[i], shaping))
            continue;

        // At the moment, the only time m_disableFontFallback is set is
        // when we look up glyph indices for non-BMP code ranges. So,
        // we can skip the glyph placement. When that becomes not the case
        // any more, we have to add a new flag to control glyph placement.
        if (m_disableFontFallback)
          continue;

        // Compute placements. Note that offsets is documented incorrectly
        // and is actually an array.
        EnsureCachedDCCreated();
        SelectObject(m_cachedDC, shaping.m_hfont);
        shaping.m_prePadding = 0;
        if (FAILED(ScriptPlace(m_cachedDC, shaping.m_scriptCache,
                               &shaping.m_glyphs[0],
                               static_cast<int>(shaping.m_glyphs.size()),
                               &shaping.m_visualAttributes[0], &m_runs[i].a,
                               &shaping.m_advance[0], &shaping.m_offsets[0],
                               &shaping.m_abc))) {
            // Some error we don't know how to handle. Nuke all of our data
            // since we can't deal with partially valid data later.
            m_runs.clear();
            m_scriptTags.clear();
            m_shapes.clear();
            m_screenOrder.clear();
        }
    }

    adjustSpaceAdvances();

    if (m_letterSpacing != 0 || m_wordSpacing != 0)
        applySpacing();
}

void UniscribeHelper::fillScreenOrder()
{
    m_screenOrder.resize(m_runs.size());

    // We assume that the input has only one text direction in it.
    // TODO(brettw) are we sure we want to keep this restriction?
    if (m_isRtl) {
        for (int i = 0; i < static_cast<int>(m_screenOrder.size()); i++)
            m_screenOrder[static_cast<int>(m_screenOrder.size()) - i - 1] = i;
    } else {
        for (int i = 0; i < static_cast<int>(m_screenOrder.size()); i++)
            m_screenOrder[i] = i;
    }
}

void UniscribeHelper::adjustSpaceAdvances()
{
    if (m_spaceWidth == 0)
        return;

    int spaceWidthWithoutLetterSpacing = m_spaceWidth - m_letterSpacing;

    // This mostly matches what WebKit's UniscribeController::shapeAndPlaceItem.
    for (size_t run = 0; run < m_runs.size(); run++) {
        Shaping& shaping = m_shapes[run];

        // FIXME: This loop is not UTF-16-safe. Unicode 6.0 has a couple
        // of complex script blocks in Plane 1.
        for (int i = 0; i < shaping.charLength(); i++) {
            UChar c = m_input[m_runs[run].iCharPos + i];
            bool treatAsSpace = Font::treatAsSpace(c);
            if (!treatAsSpace && !Font::treatAsZeroWidthSpaceInComplexScript(c))
                continue;

            int glyphIndex = shaping.m_logs[i];
            int currentAdvance = shaping.m_advance[glyphIndex];

            shaping.m_glyphs[glyphIndex] = shaping.m_spaceGlyph;

            if (treatAsSpace) {
                // currentAdvance does not include additional letter-spacing,
                // but m_spaceWidth does. Here we find out how off we are from
                // the correct width (spaceWidthWithoutLetterSpacing) and
                // just subtract that diff.
                int diff = currentAdvance - spaceWidthWithoutLetterSpacing;
                // The shaping can consist of a run of text, so only subtract
                // the difference in the width of the glyph.
                shaping.m_advance[glyphIndex] -= diff;
                shaping.m_abc.abcB -= diff;
                continue;
            }

            // For characters treated as zero-width space in complex
            // scripts, set the advance width to zero, adjust
            // |abcB| of the current run accordingly and set 
            // the glyph to m_spaceGlyph (invisible).
            shaping.m_advance[glyphIndex] = 0;
            shaping.m_abc.abcB -= currentAdvance;
            shaping.m_offsets[glyphIndex].du = 0;
            shaping.m_offsets[glyphIndex].dv = 0;
        }
    }
}

void UniscribeHelper::applySpacing()
{
    for (size_t run = 0; run < m_runs.size(); run++) {
        Shaping& shaping = m_shapes[run];
        bool isRtl = m_runs[run].a.fRTL;

        if (m_letterSpacing != 0) {
            // RTL text gets padded to the left of each character. We increment
            // the run's advance to make this happen. This will be balanced out
            // by NOT adding additional advance to the last glyph in the run.
            if (isRtl)
                shaping.m_prePadding += m_letterSpacing;

            // Go through all the glyphs in this run and increase the "advance"
            // to account for letter spacing. We adjust letter spacing only on
            // cluster boundaries.
            //
            // This works for most scripts, but may have problems with some
            // indic scripts. This behavior is better than Firefox or IE for
            // Hebrew.
            for (int i = 0; i < shaping.glyphLength(); i++) {
                if (shaping.m_visualAttributes[i].fClusterStart) {
                    // Ick, we need to assign the extra space so that the glyph
                    // comes first, then is followed by the space. This is
                    // opposite for RTL.
                    if (isRtl) {
                        if (i != shaping.glyphLength() - 1) {
                            // All but the last character just get the spacing
                            // applied to their advance. The last character
                            // doesn't get anything,
                            shaping.m_advance[i] += m_letterSpacing;
                            shaping.m_abc.abcB += m_letterSpacing;
                        }
                    } else {
                        // LTR case is easier, we just add to the advance.
                        shaping.m_advance[i] += m_letterSpacing;
                        shaping.m_abc.abcB += m_letterSpacing;
                    }
                }
            }
        }

        // Go through all the characters to find whitespace and insert the
        // extra wordspacing amount for the glyphs they correspond to.
        if (m_wordSpacing != 0) {
            for (int i = 0; i < shaping.charLength(); i++) {
                if (!Font::treatAsSpace(m_input[m_runs[run].iCharPos + i]))
                    continue;

                // The char in question is a word separator...
                int glyphIndex = shaping.m_logs[i];

                // Spaces will not have a glyph in Uniscribe, it will just add
                // additional advance to the character to the left of the
                // space. The space's corresponding glyph will be the character
                // following it in reading order.
                if (isRtl) {
                    // In RTL, the glyph to the left of the space is the same
                    // as the first glyph of the following character, so we can
                    // just increment it.
                    shaping.m_advance[glyphIndex] += m_wordSpacing;
                    shaping.m_abc.abcB += m_wordSpacing;
                } else {
                    // LTR is actually more complex here, we apply it to the
                    // previous character if there is one, otherwise we have to
                    // apply it to the leading space of the run.
                    if (glyphIndex == 0)
                        shaping.m_prePadding += m_wordSpacing;
                    else {
                        shaping.m_advance[glyphIndex - 1] += m_wordSpacing;
                        shaping.m_abc.abcB += m_wordSpacing;
                    }
                }
            }
        }  // m_wordSpacing != 0

        // Loop for next run...
    }
}

// The advance is the ABC width of the run
int UniscribeHelper::advanceForItem(int itemIndex) const
{
    int accum = 0;
    const Shaping& shaping = m_shapes[itemIndex];

    if (shaping.m_justify.size() == 0) {
        // Easy case with no justification, the width is just the ABC width of
        // the run. (The ABC width is the sum of the advances).
        return shaping.m_abc.abcA + shaping.m_abc.abcB +
               shaping.m_abc.abcC + shaping.m_prePadding;
    }

    // With justification, we use the justified amounts instead. The
    // justification array contains both the advance and the extra space
    // added for justification, so is the width we want.
    int justification = 0;
    for (size_t i = 0; i < shaping.m_justify.size(); i++)
        justification += shaping.m_justify[i];

    return shaping.m_prePadding + justification;
}

// SCRIPT_FONTPROPERTIES contains glyph indices for default, invalid
// and blank glyphs. Just because ScriptShape succeeds does not mean
// that a text run is rendered correctly. Some characters may be rendered
// with default/invalid/blank glyphs. Therefore, we need to check if the glyph
// array returned by ScriptShape contains any of those glyphs to make
// sure that the text run is rendered successfully.
// However, we should not subject zero-width characters to this test.

bool UniscribeHelper::containsMissingGlyphs(const Shaping& shaping,
                                            const SCRIPT_ITEM& run,
                                            const SCRIPT_FONTPROPERTIES* properties) const
{
    for (int i = 0; i < shaping.charLength(); i++) {
        UChar c = m_input[run.iCharPos + i];
        // Skip zero-width space characters because they're not considered to
        // be missing in a font.
        if (Font::treatAsZeroWidthSpaceInComplexScript(c))
            continue;
        int glyphIndex = shaping.m_logs[i];
        WORD glyph = shaping.m_glyphs[glyphIndex];
        // Note on the thrid condition: Windows Vista sometimes returns glyphs
        // equal to wgBlank (instead of wgDefault), with fZeroWidth set. Treat
        // such cases as having missing glyphs if the corresponding character
        // is not a zero width whitespace.
        if (glyph == properties->wgDefault
            || (glyph == properties->wgInvalid && glyph != properties->wgBlank)
            || (glyph == properties->wgBlank && shaping.m_visualAttributes[glyphIndex].fZeroWidth))
            return true;
    }
    return false;
}

static OPENTYPE_TAG convertFeatureTag(const String& tag)
{
    return ((tag[0] & 0xFF) | ((tag[1] & 0xFF) << 8) | ((tag[2] & 0xFF) << 16) | ((tag[3] & 0xFF) << 24));
}

void UniscribeHelper::setRangeProperties(const FontFeatureSettings* featureSettings)
{
    if (!featureSettings || !featureSettings->size()) {
        m_featureRecords.resize(0);
        return;
    }

    m_featureRecords.resize(featureSettings->size());
    for (unsigned i = 0; i < featureSettings->size(); ++i) {
        m_featureRecords[i].lParameter = featureSettings->at(i).value();
        m_featureRecords[i].tagFeature = convertFeatureTag(featureSettings->at(i).tag());
    }
    m_rangeProperties.potfRecords = &m_featureRecords[0];
    m_rangeProperties.cotfRecords = m_featureRecords.size();
}

}  // namespace WebCore