Translations update

[openttd/fttd.git] / src / gfx.cpp

/* $Id$ */

/*
 * This file is part of OpenTTD.
 * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
 * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
 */

/** @file gfx.cpp Handling of drawing text and other gfx related stuff. */

#include "stdafx.h"
#include "debug.h"
#include "gfx_layout.h"
#include "progress.h"
#include "zoom_func.h"
#include "blitter/blitter.h"
#include "video/video_driver.hpp"
#include "strings_func.h"
#include "settings_type.h"
#include "network/network.h"
#include "network/network_func.h"
#include "window_func.h"
#include "newgrf_debug.h"

#include "table/palettes.h"
#include "table/string_colours.h"
#include "table/sprites.h"
#include "table/control_codes.h"

byte _dirkeys;        ///< 1 = left, 2 = up, 4 = right, 8 = down
bool _fullscreen;
byte _support8bpp;
CursorVars _cursor;
static const AnimCursor *_cursor_animate_list; ///< in case of animated cursor, list of frames
static const AnimCursor *_cursor_animate_cur;  ///< in case of animated cursor, current frame
static uint _cursor_animate_timeout;           ///< in case of animated cursor, number of ticks to show the current cursor

bool _ctrl_pressed;   ///< Is Ctrl pressed?
bool _shift_pressed;  ///< Is Shift pressed?
byte _fast_forward;
bool _left_button_down;     ///< Is left mouse button pressed?
bool _left_button_clicked;  ///< Is left mouse button clicked?
bool _right_button_down;    ///< Is right mouse button pressed?
bool _right_button_clicked; ///< Is right mouse button clicked?

ttd_unique_ptr <Blitter::Surface> _screen_surface;
int _screen_width, _screen_height;

bool _exit_game;
GameMode _game_mode;
SwitchMode _switch_mode;  ///< The next mainloop command.
PauseModeByte _pause_mode;
Palette _cur_palette;
int _cur_palette_first_dirty;
int _cur_palette_count_dirty;

byte _colour_gradient[COLOUR_END][8];

static void GfxCharBlitter (BlitArea *dpi, const Sprite *sprite, int x, int y,
        const byte *remap);

static Blitter::Buffer _cursor_backup;

ZoomLevelByte _gui_zoom; ///< GUI Zoom level

/**
 * The rect for repaint.
 *
 * This rectangle defines the area which should be repaint by the video driver.
 *
 * @ingroup dirty
 */
static Rect _invalid_rect;

static const uint DIRTY_BLOCK_HEIGHT   = 8;
static const uint DIRTY_BLOCK_WIDTH    = 64;

static uint _dirty_bytes_per_line = 0;
static byte *_dirty_blocks = NULL;
extern uint _dirty_block_colour;


/**
 * Applies a certain FillRectMode-operation to a rectangle [left, right] x [top, bottom] on the screen.
 *
 * @pre dpi->zoom == ZOOM_LVL_NORMAL, right >= left, bottom >= top
 * @param dpi Area to blit to
 * @param left Minimum X (inclusive)
 * @param top Minimum Y (inclusive)
 * @param right Maximum X (inclusive)
 * @param bottom Maximum Y (inclusive)
 * @param colour A 8 bit palette index (FILLRECT_OPAQUE and FILLRECT_CHECKER) or a recolour spritenumber (FILLRECT_RECOLOUR)
 * @param mode
 *         FILLRECT_OPAQUE:   Fill the rectangle with the specified colour
 *         FILLRECT_CHECKER:  Like FILLRECT_OPAQUE, but only draw every second pixel (used to grey out things)
 *         FILLRECT_RECOLOUR:  Apply a recolour sprite to every pixel in the rectangle currently on screen
 */
void GfxFillRect (BlitArea *dpi, int left, int top, int right, int bottom, int colour, FillRectMode mode)
{
        void *dst;
        const int otopleft = top + left;

        if (left > right || top > bottom) return;
        if (right < dpi->left || left >= dpi->left + dpi->width) return;
        if (bottom < dpi->top || top >= dpi->top + dpi->height) return;

        if ( (left -= dpi->left) < 0) left = 0;
        right = right - dpi->left + 1;
        if (right > dpi->width) right = dpi->width;
        right -= left;
        assert(right > 0);

        if ( (top -= dpi->top) < 0) top = 0;
        bottom = bottom - dpi->top + 1;
        if (bottom > dpi->height) bottom = dpi->height;
        bottom -= top;
        assert(bottom > 0);

        dst = dpi->surface->move (dpi->dst_ptr, left, top);

        switch (mode) {
                default: // FILLRECT_OPAQUE
                        dpi->surface->draw_rect (dst, right, bottom, (uint8)colour);
                        break;

                case FILLRECT_RECOLOUR:
                        dpi->surface->recolour_rect (dst, right, bottom, GB(colour, 0, PALETTE_WIDTH));
                        break;

                case FILLRECT_CHECKER: {
                        byte bo = (otopleft - left + dpi->left - top + dpi->top) & 1;
                        dpi->surface->draw_checker (dst, right, bottom, colour, bo);
                        break;
                }
        }
}

/**
 * Check line clipping by using a linear equation and draw the visible part of
 * the line given by x/y and x2/y2.
 * @param dpi Area to blit to.
 * @param x X coordinate of first point.
 * @param y Y coordinate of first point.
 * @param x2 X coordinate of second point.
 * @param y2 Y coordinate of second point.
 * @param screen_width With of the screen to check clipping against.
 * @param screen_height Height of the screen to check clipping against.
 * @param colour Colour of the line.
 * @param width Width of the line.
 * @param dash Length of dashes for dashed lines. 0 means solid line.
 */
static inline void GfxDoDrawLine (BlitArea *dpi, int x, int y, int x2, int y2, int screen_width, int screen_height, uint8 colour, int width, int dash = 0)
{
        assert(width > 0);

        if (y2 == y || x2 == x) {
                /* Special case: horizontal/vertical line. All checks already done in GfxPreprocessLine. */
        } else {
                int grade_y = y2 - y;
                int grade_x = x2 - x;

                /* Clipping rectangle. Slightly extended so we can ignore the width of the line. */
                int extra = (int)CeilDiv(3 * width, 4); // not less then "width * sqrt(2) / 2"
                int clip_left  = -extra - x;
                int clip_right = screen_width - 1 + extra - x;

                /* prevent integer overflows. */
                int margin = 1;
                int dinf = max (abs (clip_left), abs (clip_right));
                while (INT_MAX / abs(grade_y) < dinf) {
                        grade_y /= 2;
                        grade_x /= 2;
                        margin  *= 2; // account for rounding errors
                }

                /* Imagine that the line is infinitely long and it intersects
                 * with infinitely long left and right edges of the clipping
                 * rectangle. If both intersection points are outside the
                 * clipping rectangle and both on the same side of it,
                 * we don't need to draw anything. */
                int left_isec_y  = y + clip_left  * grade_y / grade_x;
                int right_isec_y = y + clip_right * grade_y / grade_x;

                int clip_bottom = screen_height - 1 + extra + margin;
                if (left_isec_y > clip_bottom && right_isec_y > clip_bottom) return;

                int clip_top = -extra - margin;
                if (left_isec_y < clip_top && right_isec_y < clip_top) return;

                /* It is possible to use the line equation to further reduce
                 * the amount of work the blitter has to do by shortening the
                 * effective line segment. However, in order to get that right
                 * and prevent the flickering effects of rounding errors so
                 * much additional code has to be run here that in the general
                 * case the effect is not noticable. */
        }

        dpi->surface->draw_line (dpi->dst_ptr, x, y, x2, y2, screen_width, screen_height, colour, width, dash);
}

/**
 * Align parameters of a line to the given DPI and check simple clipping.
 * @param dpi Screen parameters to align with.
 * @param x X coordinate of first point.
 * @param y Y coordinate of first point.
 * @param x2 X coordinate of second point.
 * @param y2 Y coordinate of second point.
 * @param width Width of the line.
 * @return True if the line is likely to be visible, false if it's certainly
 *         invisible.
 */
static inline bool GfxPreprocessLine (BlitArea *dpi, int &x, int &y, int &x2, int &y2, int width)
{
        x -= dpi->left;
        x2 -= dpi->left;
        y -= dpi->top;
        y2 -= dpi->top;

        /* Check simple clipping */
        if (x + width / 2 < 0           && x2 + width / 2 < 0          ) return false;
        if (y + width / 2 < 0           && y2 + width / 2 < 0          ) return false;
        if (x - width / 2 > dpi->width  && x2 - width / 2 > dpi->width ) return false;
        if (y - width / 2 > dpi->height && y2 - width / 2 > dpi->height) return false;
        return true;
}

void GfxDrawLine (BlitArea *dpi, int x, int y, int x2, int y2, int colour, int width, int dash)
{
        if (GfxPreprocessLine(dpi, x, y, x2, y2, width)) {
                GfxDoDrawLine (dpi, x, y, x2, y2, dpi->width, dpi->height, colour, width, dash);
        }
}

static void GfxDrawLineUnscaled (DrawPixelInfo *dpi, int x, int y, int x2, int y2, int colour)
{
        if (GfxPreprocessLine(dpi, x, y, x2, y2, 1)) {
                GfxDoDrawLine (dpi,
                                UnScaleByZoom(x, dpi->zoom), UnScaleByZoom(y, dpi->zoom),
                                UnScaleByZoom(x2, dpi->zoom), UnScaleByZoom(y2, dpi->zoom),
                                UnScaleByZoom(dpi->width, dpi->zoom), UnScaleByZoom(dpi->height, dpi->zoom), colour, 1);
        }
}

/**
 * Draws the projection of a parallelepiped.
 * This can be used to draw boxes in world coordinates.
 * @param dpi Screen parameters to align with.
 * @param x   Screen X-coordinate of top front corner.
 * @param y   Screen Y-coordinate of top front corner.
 * @param dx1 Screen X-length of first edge.
 * @param dy1 Screen Y-length of first edge.
 * @param dx2 Screen X-length of second edge.
 * @param dy2 Screen Y-length of second edge.
 * @param dx3 Screen X-length of third edge.
 * @param dy3 Screen Y-length of third edge.
 */
void DrawBox (DrawPixelInfo *dpi, int x, int y, int dx1, int dy1, int dx2, int dy2, int dx3, int dy3)
{
        /*           ....
         *         ..    ....
         *       ..          ....
         *     ..                ^
         *   <--__(dx1,dy1)    /(dx2,dy2)
         *   :    --__       /   :
         *   :        --__ /     :
         *   :            *(x,y) :
         *   :            |      :
         *   :            |     ..
         *    ....        |(dx3,dy3)
         *        ....    | ..
         *            ....V.
         */

        static const byte colour = PC_WHITE;

        GfxDrawLineUnscaled (dpi, x, y, x + dx1, y + dy1, colour);
        GfxDrawLineUnscaled (dpi, x, y, x + dx2, y + dy2, colour);
        GfxDrawLineUnscaled (dpi, x, y, x + dx3, y + dy3, colour);

        GfxDrawLineUnscaled (dpi, x + dx1, y + dy1, x + dx1 + dx2, y + dy1 + dy2, colour);
        GfxDrawLineUnscaled (dpi, x + dx1, y + dy1, x + dx1 + dx3, y + dy1 + dy3, colour);
        GfxDrawLineUnscaled (dpi, x + dx2, y + dy2, x + dx2 + dx1, y + dy2 + dy1, colour);
        GfxDrawLineUnscaled (dpi, x + dx2, y + dy2, x + dx2 + dx3, y + dy2 + dy3, colour);
        GfxDrawLineUnscaled (dpi, x + dx3, y + dy3, x + dx3 + dx1, y + dy3 + dy1, colour);
        GfxDrawLineUnscaled (dpi, x + dx3, y + dy3, x + dx3 + dx2, y + dy3 + dy2, colour);
}

/**
 * Set the colour remap to be for the given colour.
 * @param remap the remap array.
 * @param colour the new colour of the remap.
 */
static void SetColourRemap (byte (&remap) [3], TextColour colour)
{
        if (colour == TC_INVALID) return;

        /* Black strings have no shading ever; the shading is black, so it
         * would be invisible at best, but it actually makes it illegible. */
        bool no_shade   = (colour & TC_NO_SHADE) != 0 || colour == TC_BLACK;
        bool raw_colour = (colour & TC_IS_PALETTE_COLOUR) != 0;
        colour &= ~(TC_NO_SHADE | TC_IS_PALETTE_COLOUR);

        /* The grf loader ensures that #ST_FONT sprites only use colours 0 to 2. */
        remap[0] = 0;
        remap[1] = raw_colour ? (byte)colour : _string_colourmap[colour];
        remap[2] = no_shade ? 0 : 1;
}

/**
 * Drawing routine for drawing a laid out line of text.
 * @param line      String to draw.
 * @param dpi       The area to draw on.
 * @param y         The top most position to draw on.
 * @param left      The left most position to draw on.
 * @param right     The right most position to draw on.
 * @param align     The alignment of the string when drawing left-to-right. In the
 *                  case a right-to-left language is chosen this is inverted so it
 *                  will be drawn in the right direction.
 * @param underline Whether to underline what has been drawn or not.
 * @param truncation Whether to perform string truncation or not.
 *
 * @return In case of left or center alignment the right most pixel we have drawn to.
 *         In case of right alignment the left most pixel we have drawn to.
 */
static int DrawLayoutLine (const ParagraphLayouter::Line *line,
        BlitArea *dpi, int y, int left, int right,
        StringAlignment align, bool underline, bool truncation)
{
        if (line->CountRuns() == 0) return 0;

        int w = line->GetWidth();
        int h = line->GetLeading();

        /*
         * The following is needed for truncation.
         * Depending on the text direction, we either remove bits at the rear
         * or the front. For this we shift the entire area to draw so it fits
         * within the left/right bounds and the side we do not truncate it on.
         * Then we determine the truncation location, i.e. glyphs that fall
         * outside of the range min_x - max_x will not be drawn; they are thus
         * the truncated glyphs.
         *
         * At a later step we insert the dots.
         */

        int max_w = right - left + 1; // The maximum width.

        int offset_x = 0;  // The offset we need for positioning the glyphs
        int min_x = left;  // The minimum x position to draw normal glyphs on.
        int max_x = right; // The maximum x position to draw normal glyphs on.

        truncation &= max_w < w;         // Whether we need to do truncation.
        int dot_width = 0;               // Cache for the width of the dot.
        const Sprite *dot_sprite = NULL; // Cache for the sprite of the dot.

        if (truncation) {
                /*
                 * Assumption may be made that all fonts of a run are of the same size.
                 * In any case, we'll use these dots for the abbreviation, so even if
                 * another size would be chosen it won't have truncated too little for
                 * the truncation dots.
                 */
                FontCache *fc = line->GetVisualRun(0)->GetFont()->fc;
                GlyphID dot_glyph = fc->MapCharToGlyph('.');
                dot_width = fc->GetGlyphWidth(dot_glyph);
                dot_sprite = fc->GetGlyph(dot_glyph);

                if (_current_text_dir == TD_RTL) {
                        min_x += 3 * dot_width;
                        offset_x = w - 3 * dot_width - max_w;
                } else {
                        max_x -= 3 * dot_width;
                }

                w = max_w;
        }

        /* In case we have a RTL language we swap the alignment. */
        if (!(align & SA_FORCE) && _current_text_dir == TD_RTL && (align & SA_HOR_MASK) != SA_HOR_CENTER) align ^= SA_RIGHT;

        /* right is the right most position to draw on. In this case we want to do
         * calculations with the width of the string. In comparison right can be
         * seen as lastof(todraw) and width as lengthof(todraw). They differ by 1.
         * So most +1/-1 additions are to move from lengthof to 'indices'.
         */
        switch (align & SA_HOR_MASK) {
                case SA_LEFT:
                        /* right + 1 = left + w */
                        right = left + w - 1;
                        break;

                case SA_HOR_CENTER:
                        left  = RoundDivSU(right + 1 + left - w, 2);
                        /* right + 1 = left + w */
                        right = left + w - 1;
                        break;

                case SA_RIGHT:
                        left = right + 1 - w;
                        break;

                default:
                        NOT_REACHED();
        }

        static const byte remap_black[3] = { 0, _string_colourmap[TC_BLACK], 0 };
        byte remap[3];
        memcpy (remap, remap_black, sizeof(remap));
        TextColour colour = TC_BLACK;
        bool draw_shadow = false;
        for (int run_index = 0; run_index < line->CountRuns(); run_index++) {
                const ParagraphLayouter::VisualRun *run = line->GetVisualRun(run_index);
                const FontBase *f = run->GetFont();

                FontCache *fc = f->fc;
                colour = f->colour;
                SetColourRemap (remap, colour);

                int dpi_left  = dpi->left;
                int dpi_right = dpi->left + dpi->width - 1;

                draw_shadow = colour != TC_BLACK && (colour & TC_NO_SHADE) == 0 && fc->GetDrawGlyphShadow();

                for (int i = 0; i < run->GetGlyphCount(); i++) {
                        ParagraphLayouter::GlyphPos gp;
                        /* Not a valid glyph (empty) */
                        if (!run->GetGlyphPos (&gp, i)) continue;

                        int begin_x = gp.x0 + left - offset_x;
                        int end_x   = gp.x1 + left - offset_x  - 1;
                        int top     = gp.y + y;

                        /* Truncated away. */
                        if (truncation && (begin_x < min_x || end_x > max_x)) continue;

                        const Sprite *sprite = fc->GetGlyph (gp.glyph);
                        /* Check clipping (the "+ 1" is for the shadow). */
                        if (begin_x + sprite->x_offs > dpi_right || begin_x + sprite->x_offs + sprite->width /* - 1 + 1 */ < dpi_left) continue;

                        if (draw_shadow && (gp.glyph & SPRITE_GLYPH) == 0) {
                                GfxCharBlitter (dpi, sprite, begin_x + 1, top + 1, remap_black);
                        }
                        GfxCharBlitter (dpi, sprite, begin_x, top, remap);
                }
        }

        if (truncation) {
                int x = (_current_text_dir == TD_RTL) ? left : (right - 3 * dot_width);
                for (int i = 0; i < 3; i++, x += dot_width) {
                        if (draw_shadow) {
                                GfxCharBlitter (dpi, dot_sprite, x + 1, y + 1, remap_black);
                        }
                        GfxCharBlitter (dpi, dot_sprite, x, y, remap);
                }
        }

        if (underline) {
                GfxFillRect (dpi, left, y + h, right, y + h, remap[1]);
        }

        return (align & SA_HOR_MASK) == SA_RIGHT ? left : right;
}

/**
 * Draw string, possibly truncated to make it fit in its allocated space
 *
 * @param dpi    The area to draw on.
 * @param left   The left most position to draw on.
 * @param right  The right most position to draw on.
 * @param top    The top most position to draw on.
 * @param str    String to draw.
 * @param colour Colour used for drawing the string, see DoDrawString() for details
 * @param align  The alignment of the string when drawing left-to-right. In the
 *               case a right-to-left language is chosen this is inverted so it
 *               will be drawn in the right direction.
 * @param underline Whether to underline what has been drawn or not.
 * @param fontsize The size of the initial characters.
 * @return In case of left or center alignment the right most pixel we have drawn to.
 *         In case of right alignment the left most pixel we have drawn to.
 */
int DrawString (BlitArea *dpi, int left, int right, int top,
        const char *str, TextColour colour, StringAlignment align,
        bool underline, FontSize fontsize)
{
        /* The string may contain control chars to change the font, just use the biggest font for clipping. */
        int max_height = max(max(FONT_HEIGHT_SMALL, FONT_HEIGHT_NORMAL), max(FONT_HEIGHT_LARGE, FONT_HEIGHT_MONO));

        /* Funny glyphs may extent outside the usual bounds, so relax the clipping somewhat. */
        int extra = max_height / 2;

        if (dpi->top + dpi->height + extra < top || dpi->top > top + max_height + extra ||
                        dpi->left + dpi->width + extra < left || dpi->left > right + extra) {
                return 0;
        }

        Layouter layout(str, INT32_MAX, colour, fontsize);
        if (layout.empty()) return 0;

        return DrawLayoutLine (layout.front().get(), dpi, top, left, right, align, underline, true);
}

/**
 * Draw string, possibly truncated to make it fit in its allocated space
 *
 * @param dpi    The area to draw on.
 * @param left   The left most position to draw on.
 * @param right  The right most position to draw on.
 * @param top    The top most position to draw on.
 * @param str    String to draw.
 * @param colour Colour used for drawing the string, see DoDrawString() for details
 * @param align  The alignment of the string when drawing left-to-right. In the
 *               case a right-to-left language is chosen this is inverted so it
 *               will be drawn in the right direction.
 * @param underline Whether to underline what has been drawn or not.
 * @param fontsize The size of the initial characters.
 * @return In case of left or center alignment the right most pixel we have drawn to.
 *         In case of right alignment the left most pixel we have drawn to.
 */
int DrawString (BlitArea *dpi, int left, int right, int top,
        StringID str, TextColour colour, StringAlignment align,
        bool underline, FontSize fontsize)
{
        char buffer[DRAW_STRING_BUFFER];
        GetString (buffer, str);
        return DrawString (dpi, left, right, top, buffer, colour, align, underline, fontsize);
}

/**
 * Calculates height of string (in pixels). The string is changed to a multiline string if needed.
 * @param str string to check
 * @param maxw maximum string width
 * @return height of pixels of string when it is drawn
 */
uint GetStringHeight (const char *str, int maxw, FontSize fontsize)
{
        Layouter layout(str, maxw, TC_FROMSTRING, fontsize);
        return layout.GetBounds().height;
}

/**
 * Calculates height of string (in pixels). The string is changed to a multiline string if needed.
 * @param str string to check
 * @param maxw maximum string width
 * @return height of pixels of string when it is drawn
 */
uint GetStringHeight (StringID str, int maxw)
{
        char buffer[DRAW_STRING_BUFFER];
        GetString (buffer, str);
        return GetStringHeight(buffer, maxw);
}

/**
 * Calculates number of lines of string. The string is changed to a multiline string if needed.
 * @param str string to check
 * @param maxw maximum string width
 * @return number of lines of string when it is drawn
 */
int GetStringLineCount(StringID str, int maxw)
{
        char buffer[DRAW_STRING_BUFFER];
        GetString (buffer, str);

        Layouter layout(buffer, maxw);
        return layout.size();
}

/**
 * Draw string, possibly over multiple lines.
 *
 * @param dpi    The area to draw on.
 * @param left   The left most position to draw on.
 * @param right  The right most position to draw on.
 * @param top    The top most position to draw on.
 * @param bottom The bottom most position to draw on.
 * @param str    String to draw.
 * @param colour Colour used for drawing the string, see DoDrawString() for details
 * @param align  The horizontal and vertical alignment of the string.
 * @param underline Whether to underline all strings
 * @param fontsize The size of the initial characters.
 *
 * @return If \a align is #SA_BOTTOM, the top to where we have written, else the bottom to where we have written.
 */
int DrawStringMultiLine (BlitArea *dpi, int left, int right, int top, int bottom,
        const char *str, TextColour colour, StringAlignment align,
        bool underline, FontSize fontsize)
{
        int maxw = right - left + 1;
        int maxh = bottom - top + 1;

        /* It makes no sense to even try if it can't be drawn anyway, or
         * do we really want to support fonts of 0 or less pixels high? */
        if (maxh <= 0) return top;

        Layouter layout(str, maxw, colour, fontsize);
        int total_height = layout.GetBounds().height;
        int y;
        switch (align & SA_VERT_MASK) {
                case SA_TOP:
                        y = top;
                        break;

                case SA_VERT_CENTER:
                        y = RoundDivSU(bottom + top - total_height, 2);
                        break;

                case SA_BOTTOM:
                        y = bottom - total_height;
                        break;

                default: NOT_REACHED();
        }

        int last_line = top;
        int first_line = bottom;

        for (Layouter::const_iterator iter (layout.begin()); iter != layout.end(); iter++) {
                const ParagraphLayouter::Line *line = iter->get();

                int line_height = line->GetLeading();
                if (y >= top && y < bottom) {
                        last_line = y + line_height;
                        if (first_line > y) first_line = y;

                        DrawLayoutLine (line, dpi, y, left, right, align, underline, false);
                }
                y += line_height;
        }

        return ((align & SA_VERT_MASK) == SA_BOTTOM) ? first_line : last_line;
}

/**
 * Draw string, possibly over multiple lines.
 *
 * @param dpi    The area to draw on.
 * @param left   The left most position to draw on.
 * @param right  The right most position to draw on.
 * @param top    The top most position to draw on.
 * @param bottom The bottom most position to draw on.
 * @param str    String to draw.
 * @param colour Colour used for drawing the string, see DoDrawString() for details
 * @param align  The horizontal and vertical alignment of the string.
 * @param underline Whether to underline all strings
 * @param fontsize The size of the initial characters.
 *
 * @return If \a align is #SA_BOTTOM, the top to where we have written, else the bottom to where we have written.
 */
int DrawStringMultiLine (BlitArea *dpi, int left, int right, int top, int bottom,
        StringID str, TextColour colour, StringAlignment align,
        bool underline, FontSize fontsize)
{
        char buffer[DRAW_STRING_BUFFER];
        GetString (buffer, str);
        return DrawStringMultiLine (dpi, left, right, top, bottom, buffer, colour, align, underline, fontsize);
}

/**
 * Return the string dimension in pixels. The height and width are returned
 * in a single Dimension value. TINYFONT, BIGFONT modifiers are only
 * supported as the first character of the string. The returned dimensions
 * are therefore a rough estimation correct for all the current strings
 * but not every possible combination
 * @param str string to calculate pixel-width
 * @param start_fontsize Fontsize to start the text with
 * @return string width and height in pixels
 */
Dimension GetStringBoundingBox(const char *str, FontSize start_fontsize)
{
        Layouter layout(str, INT32_MAX, TC_FROMSTRING, start_fontsize);
        return layout.GetBounds();
}

/**
 * Get bounding box of a string. Uses parameters set by #DParam if needed.
 * Has the same restrictions as #GetStringBoundingBox(const char *str).
 * @param strid String to examine.
 * @return Width and height of the bounding box for the string in pixels.
 */
Dimension GetStringBoundingBox(StringID strid)
{
        char buffer[DRAW_STRING_BUFFER];

        GetString (buffer, strid);
        return GetStringBoundingBox(buffer);
}

/**
 * Draw single character horizontally centered around (x,y)
 * @param dpi         The area to draw on.
 * @param c           Character (glyph) to draw
 * @param x           X position to draw character
 * @param y           Y position to draw character
 * @param colour      Colour to use, see DoDrawString() for details
 */
void DrawCharCentered (BlitArea *dpi, WChar c, int x, int y, TextColour colour)
{
        byte remap[3];
        SetColourRemap (remap, colour);
        FontCache *fc = FontCache::Get (FS_NORMAL);
        GfxCharBlitter (dpi, fc->GetCharGlyph (c),
                        x - fc->GetCharacterWidth(c) / 2, y, remap);
}

/**
 * Get the size of a sprite.
 * @param sprid Sprite to examine.
 * @param [out] offset Optionally returns the sprite position offset.
 * @return Sprite size in pixels.
 * @note The size assumes (0, 0) as top-left coordinate and ignores any part of the sprite drawn at the left or above that position.
 */
Dimension GetSpriteSize(SpriteID sprid, Point *offset, ZoomLevel zoom)
{
        const Sprite *sprite = GetSprite(sprid, ST_NORMAL);

        if (offset != NULL) {
                offset->x = UnScaleByZoom(sprite->x_offs, zoom);
                offset->y = UnScaleByZoom(sprite->y_offs, zoom);
        }

        Dimension d;
        d.width  = max<int>(0, UnScaleByZoom(sprite->x_offs + sprite->width, zoom));
        d.height = max<int>(0, UnScaleByZoom(sprite->y_offs + sprite->height, zoom));
        return d;
}

/**
 * Set up blitter params to draw a sprite.
 * @param bp     The BlitterParams to set up.
 * @param dpi    The area to draw on.
 * @param sprite The sprite to draw.
 * @param x      The X location to draw.
 * @param y      The Y location to draw.
 * @param scaled Whether the X and Y are scaled or unscaled.
 * @param sub    Whether to only draw a sub set of the sprite.
 * @param zoom   The zoom level at which to draw the sprites.
 * @return Whether there is anything to draw (false if sprite is off bounds).
 */
static bool SetupBlitterParams (Blitter::BlitterParams *bp, BlitArea *dpi,
        const Sprite * const sprite, int x, int y, bool scaled,
        const SubSprite * const sub, ZoomLevel zoom)
{
        /* Move to the correct offset */
        x += sprite->x_offs;
        y += sprite->y_offs;

        if (sub == NULL) {
                /* No clipping. */
                bp->skip_left = 0;
                bp->skip_top  = 0;
                bp->width  = UnScaleByZoom (sprite->width,  zoom);
                bp->height = UnScaleByZoom (sprite->height, zoom);
        } else {
                assert (!scaled);

                /* Amount of pixels to clip from the source sprite */
                int clip_left   = max (0,                   -sprite->x_offs +  sub->left        * ZOOM_LVL_BASE );
                int clip_top    = max (0,                   -sprite->y_offs +  sub->top         * ZOOM_LVL_BASE );
                int clip_right  = max (0, sprite->width  - (-sprite->x_offs + (sub->right + 1)  * ZOOM_LVL_BASE));
                int clip_bottom = max (0, sprite->height - (-sprite->y_offs + (sub->bottom + 1) * ZOOM_LVL_BASE));

                if (clip_left + clip_right >= sprite->width)  return false;
                if (clip_top + clip_bottom >= sprite->height) return false;

                bp->skip_left = UnScaleByZoomLower (clip_left, zoom);
                bp->skip_top  = UnScaleByZoomLower (clip_top,  zoom);
                bp->width  = UnScaleByZoom (sprite->width  - clip_left - clip_right,  zoom);
                bp->height = UnScaleByZoom (sprite->height - clip_top  - clip_bottom, zoom);

                x += ScaleByZoom (bp->skip_left, zoom);
                y += ScaleByZoom (bp->skip_top,  zoom);
        }

        /* Copy the main data directly from the sprite */
        bp->sprite = sprite;
        bp->top  = 0;
        bp->left = 0;

        bp->dst = dpi->dst_ptr;
        bp->pitch = dpi->surface->pitch;

        assert(sprite->width > 0);
        assert(sprite->height > 0);

        if (bp->width  <= 0) return false;
        if (bp->height <= 0) return false;

        y -= scaled ? ScaleByZoom (dpi->top, zoom) : dpi->top;
        int y_unscaled = UnScaleByZoom(y, zoom);
        /* Check for top overflow */
        if (y < 0) {
                bp->height -= -y_unscaled;
                if (bp->height <= 0) return false;
                bp->skip_top += -y_unscaled;
                y = 0;
        } else {
                bp->top = y_unscaled;
        }

        /* Check for bottom overflow */
        y += scaled ? ScaleByZoom (bp->height - dpi->height, zoom) : ScaleByZoom (bp->height, zoom) - dpi->height;
        if (y > 0) {
                bp->height -= UnScaleByZoom (y, zoom);
                if (bp->height <= 0) return false;
        }

        x -= scaled ? ScaleByZoom (dpi->left, zoom) : dpi->left;
        int x_unscaled = UnScaleByZoom(x, zoom);
        /* Check for left overflow */
        if (x < 0) {
                bp->width -= -x_unscaled;
                if (bp->width <= 0) return false;
                bp->skip_left += -x_unscaled;
                x = 0;
        } else {
                bp->left = x_unscaled;
        }

        /* Check for right overflow */
        x += scaled ? ScaleByZoom (bp->width - dpi->width, zoom) : ScaleByZoom (bp->width, zoom) - dpi->width;
        if (x > 0) {
                bp->width -= UnScaleByZoom (x, zoom);
                if (bp->width <= 0) return false;
        }

        assert (bp->skip_left + bp->width  <= UnScaleByZoom (sprite->width,  zoom));
        assert (bp->skip_top  + bp->height <= UnScaleByZoom (sprite->height, zoom));

        return true;
}

/**
 * The code for setting up the blitter mode and sprite information before finally drawing the sprite.
 * @param dpi    The area to draw on.
 * @param img    The sprite to draw.
 * @param pal    The palette to use.
 * @param x      The X location to draw.
 * @param y      The Y location to draw.
 * @param scaled Whether the X and Y are scaled or unscaled.
 * @param sub    Whether to only draw a sub set of the sprite.
 * @param zoom   The zoom level at which to draw the sprites.
 */
static void GfxBlitter (BlitArea *dpi, SpriteID img, PaletteID pal,
        int x, int y, bool scaled, const SubSprite * const sub, ZoomLevel zoom)
{
        SpriteID sprite_id = GB(img, 0, SPRITE_WIDTH);
        const Sprite *sprite = GetSprite (sprite_id, ST_NORMAL);

        Blitter::BlitterParams bp;
        if (!SetupBlitterParams (&bp, dpi, sprite, x, y, scaled, sub, zoom)) {
                return;
        }

        /* We do not want to catch the mouse. */
        if (_newgrf_debug_sprite_picker.mode == SPM_REDRAW && sprite_id != SPR_CURSOR_MOUSE) {
                void *topleft = dpi->surface->move (bp.dst, bp.left, bp.top);
                void *bottomright = dpi->surface->move (topleft, bp.width - 1, bp.height - 1);

                void *clicked = _newgrf_debug_sprite_picker.clicked_pixel;

                if (topleft <= clicked && clicked <= bottomright) {
                        uint offset = (((size_t)clicked - (size_t)topleft) / (Blitter::get()->screen_depth / 8)) % bp.pitch;
                        if (offset < (uint)bp.width) {
                                _newgrf_debug_sprite_picker.sprites.Include(sprite_id);
                        }
                }
        }

        byte string_remap[3];
        BlitterMode mode;
        if (HasBit(img, PALETTE_MODIFIER_TRANSPARENT)) {
                bp.remap = GetNonSprite (GB(pal, 0, PALETTE_WIDTH), ST_RECOLOUR) + 1;
                mode = BM_TRANSPARENT;

        } else if (pal == PAL_NONE) {
                mode = BM_NORMAL;

        } else if (HasBit(pal, PALETTE_TEXT_RECOLOUR)) {
                SetColourRemap (string_remap, (TextColour)GB(pal, 0, PALETTE_WIDTH));
                bp.remap = string_remap;
                mode = BM_COLOUR_REMAP;

        } else {
                bp.remap = GetNonSprite (GB(pal, 0, PALETTE_WIDTH), ST_RECOLOUR) + 1;
                switch (pal) {
                        case PALETTE_CRASH:     mode = BM_CRASH_REMAP;  break;
                        case PALETTE_ALL_BLACK: mode = BM_BLACK_REMAP;  break;
                        default:                mode = BM_COLOUR_REMAP; break;
                }
        }

        dpi->surface->draw (&bp, mode, zoom);
}

/**
 * Draw a sprite in a viewport.
 * @param dpi  The area to draw on.
 * @param img  Image number to draw
 * @param pal  Palette to use.
 * @param x    Left coordinate of image in viewport, scaled by zoom
 * @param y    Top coordinate of image in viewport, scaled by zoom
 * @param sub  If available, draw only specified part of the sprite
 */
void DrawSpriteViewport (DrawPixelInfo *dpi, SpriteID img, PaletteID pal,
        int x, int y, const SubSprite *sub)
{
        GfxBlitter (dpi, img, pal, x, y, false, sub, dpi->zoom);
}

/**
 * Draw a sprite, not in a viewport
 * @param dpi  The area to draw on.
 * @param img  Image number to draw
 * @param pal  Palette to use.
 * @param x    Left coordinate of image in pixels
 * @param y    Top coordinate of image in pixels
 */
void DrawSprite (BlitArea *dpi, SpriteID img, PaletteID pal, int x, int y)
{
        x = ScaleByZoom (x, ZOOM_LVL_GUI);
        y = ScaleByZoom (y, ZOOM_LVL_GUI);

        GfxBlitter (dpi, img, pal, x, y, true, NULL, ZOOM_LVL_GUI);
}

static void GfxCharBlitter (BlitArea *dpi, const Sprite *sprite, int x, int y,
        const byte *remap)
{
        Blitter::BlitterParams bp;
        if (SetupBlitterParams (&bp, dpi, sprite, x, y, false, NULL, ZOOM_LVL_NORMAL)) {
                bp.remap = remap;
                dpi->surface->draw (&bp, BM_COLOUR_REMAP, ZOOM_LVL_NORMAL);
        }
}

/**
 * Compute the cycle in an animation.
 * @param x Global animation counter.
 * @param n Number of cycles in the animation.
 * @param s Animation speed factor (higher is slower).
 */
static inline uint get_animation_cycle (uint x, uint n, uint s)
{
        return ((x & ((1 << s) - 1)) * n) >> s;
}

void DoPaletteAnimations()
{
        /* Animation counter for the palette animation. */
        static uint palette_animation_counter = 0;
        palette_animation_counter++;

        const Blitter::Info *blitter = Blitter::get();
        bool noanim = (blitter != NULL) && (blitter->palette_animation == Blitter::PALETTE_ANIMATION_NONE);
        const uint tc = noanim ? 0 : palette_animation_counter;

        const Colour *s;
        const ExtraPaletteValues *ev = &_extra_palette_values;
        Colour old_val[PALETTE_ANIM_SIZE];
        uint i;
        uint j;

        Colour *palette_pos = &_cur_palette[PALETTE_ANIM_START];  // Points to where animations are taking place on the palette
        /* Makes a copy of the current animation palette in old_val,
         * so the work on the current palette could be compared, see if there has been any changes */
        memcpy(old_val, palette_pos, sizeof(old_val));

        /* Fizzy Drink bubbles animation */
        s = ev->fizzy_drink;
        j = get_animation_cycle (~tc, EPV_CYCLES_FIZZY_DRINK, 4);
        for (i = 0; i != EPV_CYCLES_FIZZY_DRINK; i++) {
                *palette_pos++ = s[j];
                j++;
                if (j == EPV_CYCLES_FIZZY_DRINK) j = 0;
        }

        /* Oil refinery fire animation */
        s = ev->oil_refinery;
        j = get_animation_cycle (~tc, EPV_CYCLES_OIL_REFINERY, 4);
        for (i = 0; i != EPV_CYCLES_OIL_REFINERY; i++) {
                *palette_pos++ = s[j];
                j++;
                if (j == EPV_CYCLES_OIL_REFINERY) j = 0;
        }

        /* Radio tower blinking */
        {
                byte v = (((tc & 0x0F) - 0x3) > 0xA) ? 128 : 20;
                bool b = (tc & 0x10) != 0;

                palette_pos->r = b ? v : 255;
                palette_pos->g = 0;
                palette_pos->b = 0;
                palette_pos++;

                palette_pos->r = b ? 255 : v;
                palette_pos->g = 0;
                palette_pos->b = 0;
                palette_pos++;
        }

        /* Handle lighthouse and stadium animation */
        s = ev->lighthouse;
        j = get_animation_cycle (tc, EPV_CYCLES_LIGHTHOUSE, 5);
        for (i = 0; i != EPV_CYCLES_LIGHTHOUSE; i++) {
                *palette_pos++ = s[j];
                j++;
                if (j == EPV_CYCLES_LIGHTHOUSE) j = 0;
        }

        /* Dark blue water */
        s = (_settings_game.game_creation.landscape == LT_TOYLAND) ? ev->dark_water_toyland : ev->dark_water;
        j = get_animation_cycle (tc * 10, EPV_CYCLES_DARK_WATER, 8);
        for (i = 0; i != EPV_CYCLES_DARK_WATER; i++) {
                *palette_pos++ = s[j];
                j++;
                if (j == EPV_CYCLES_DARK_WATER) j = 0;
        }

        /* Glittery water */
        s = (_settings_game.game_creation.landscape == LT_TOYLAND) ? ev->glitter_water_toyland : ev->glitter_water;
        j = get_animation_cycle (tc, EPV_CYCLES_GLITTER_WATER, 6);
        for (i = 0; i != EPV_CYCLES_GLITTER_WATER / 3; i++) {
                *palette_pos++ = s[j];
                j += 3;
                if (j >= EPV_CYCLES_GLITTER_WATER) j -= EPV_CYCLES_GLITTER_WATER;
        }

        if (!noanim && (memcmp (old_val, &_cur_palette[PALETTE_ANIM_START], sizeof(old_val)) != 0)
                        && (_cur_palette_count_dirty == 0)) {
                /* Did we changed anything on the palette? Seems so.  Mark it as dirty */
                _cur_palette_first_dirty = PALETTE_ANIM_START;
                _cur_palette_count_dirty = PALETTE_ANIM_SIZE;
        }
}

void GfxInitPalettes()
{
        assert_compile (sizeof(_cur_palette) == sizeof(_palette));
        memcpy(&_cur_palette, &_palette, sizeof(_cur_palette));
        _cur_palette_first_dirty = 0;
        _cur_palette_count_dirty = 256;
        DoPaletteAnimations();
}

/**
 * Determine a contrasty text colour for a coloured background.
 * @param background Background colour.
 * @return TC_BLACK or TC_WHITE depending on what gives a better contrast.
 */
TextColour GetContrastColour(uint8 background)
{
        Colour c = _cur_palette[background];
        /* Compute brightness according to http://www.w3.org/TR/AERT#color-contrast.
         * The following formula computes 1000 * brightness^2, with brightness being in range 0 to 255. */
        uint sq1000_brightness = c.r * c.r * 299 + c.g * c.g * 587 + c.b * c.b * 114;
        /* Compare with threshold brightness 128 (50%) */
        return sq1000_brightness < 128 * 128 * 1000 ? TC_WHITE : TC_BLACK;
}

/**
 * Initialize the font cache.
 * @param monospace Whether to load the monospace cache or the normal fonts.
 */
void LoadStringWidthTable(bool monospace)
{
        for (FontSize fs = monospace ? FS_MONO : FS_BEGIN; fs < (monospace ? FS_END : FS_MONO); fs++) {
                FontCache::Get(fs)->ClearFontCache();
        }

        ReInitAllWindows();
}

void ScreenSizeChanged()
{
        _dirty_bytes_per_line = CeilDiv (_screen_width, DIRTY_BLOCK_WIDTH);
        _dirty_blocks = xrealloct<byte> (_dirty_blocks, _dirty_bytes_per_line * CeilDiv (_screen_height, DIRTY_BLOCK_HEIGHT));

        /* check the dirty rect */
        if (_invalid_rect.right >= _screen_width) _invalid_rect.right = _screen_width;
        if (_invalid_rect.bottom >= _screen_height) _invalid_rect.bottom = _screen_height;

        /* screen size changed and the old bitmap is invalid now, so we don't want to undraw it */
        _cursor.visible = false;
}

void UndrawMouseCursor()
{
        /* Don't undraw the mouse cursor if the screen is not ready */
        if (!_screen_surface) return;

        if (_cursor.visible) {
                _cursor.visible = false;
                _screen_surface->paste (&_cursor_backup, _cursor.draw_pos.x, _cursor.draw_pos.y);
                VideoDriver::GetActiveDriver()->MakeDirty(_cursor.draw_pos.x, _cursor.draw_pos.y, _cursor.draw_size.x, _cursor.draw_size.y);
        }
}

void DrawMouseCursor()
{
#if defined(WINCE)
        /* Don't ever draw the mouse for WinCE, as we work with a stylus */
        return;
#endif

        /* Don't draw the mouse cursor if the screen is not ready */
        if (!_screen_surface) return;

        /* Redraw mouse cursor but only when it's inside the window */
        if (!_cursor.in_window) return;

        /* Don't draw the mouse cursor if it's already drawn */
        if (_cursor.visible) {
                if (!_cursor.dirty) return;
                UndrawMouseCursor();
        }

        /* Determine visible area */
        int left = _cursor.pos.x + _cursor.total_offs.x;
        int width = _cursor.total_size.x;
        if (left < 0) {
                width += left;
                left = 0;
        }
        if (left + width > _screen_width) {
                width = _screen_width - left;
        }
        if (width <= 0) return;

        int top = _cursor.pos.y + _cursor.total_offs.y;
        int height = _cursor.total_size.y;
        if (top < 0) {
                height += top;
                top = 0;
        }
        if (top + height > _screen_height) {
                height = _screen_height - top;
        }
        if (height <= 0) return;

        _cursor.draw_pos.x = left;
        _cursor.draw_pos.y = top;
        _cursor.draw_size.x = width;
        _cursor.draw_size.y = height;

        /* Make backup of stuff below cursor */
        _screen_surface->copy (&_cursor_backup, _cursor.draw_pos.x, _cursor.draw_pos.y, _cursor.draw_size.x, _cursor.draw_size.y);

        /* Draw cursor on screen */
        BlitArea screen;
        screen.surface = _screen_surface.get();
        screen.dst_ptr = _screen_surface->ptr;
        screen.left = screen.top = 0;
        screen.width  = _screen_width;
        screen.height = _screen_height;
        for (uint i = 0; i < _cursor.sprite_count; ++i) {
                DrawSprite (&screen, _cursor.sprite_seq[i].sprite, _cursor.sprite_seq[i].pal, _cursor.pos.x + _cursor.sprite_seq[i].pos, _cursor.pos.y);
        }

        VideoDriver::GetActiveDriver()->MakeDirty(_cursor.draw_pos.x, _cursor.draw_pos.y, _cursor.draw_size.x, _cursor.draw_size.y);

        _cursor.visible = true;
        _cursor.dirty = false;
}

static void RedrawScreenRect (int left, int top, int right, int bottom)
{
        assert (right <= _screen_width && bottom <= _screen_height);
        if (_cursor.visible) {
                if (right > _cursor.draw_pos.x &&
                                left < _cursor.draw_pos.x + _cursor.draw_size.x &&
                                bottom > _cursor.draw_pos.y &&
                                top < _cursor.draw_pos.y + _cursor.draw_size.y) {
                        UndrawMouseCursor();
                }
        }

#ifdef ENABLE_NETWORK
        if (_networking) NetworkUndrawChatMessage();
#endif /* ENABLE_NETWORK */

        DrawOverlappedWindowForAll(left, top, right, bottom);

        VideoDriver::GetActiveDriver()->MakeDirty(left, top, right - left, bottom - top);
}

void ScrollScreenRect (int left, int top, int width, int height, int dx, int dy)
{
        assert ((dx != 0) || (dy != 0));

        if (abs(dx) >= width || abs(dy) >= height) {
                /* fully_outside */
                RedrawScreenRect (left, top, left + width, top + height);
                return;
        }

        if (_cursor.visible) UndrawMouseCursor();

#ifdef ENABLE_NETWORK
        if (_networking) NetworkUndrawChatMessage();
#endif /* ENABLE_NETWORK */

        _screen_surface->scroll (left, top, width, height, dx, dy);

        int l = left;
        int w = width;
        if (dx > 0) {
                DrawOverlappedWindowForAll (left, top, dx + left, top + height);
                l += dx;
                w -= dx;
        } else if (dx < 0) {
                DrawOverlappedWindowForAll (left + width + dx, top, left + width, top + height);
                w += dx;
        }

        if (dy > 0) {
                DrawOverlappedWindowForAll (l, top, w + l, top + dy);
        } else if (dy < 0) {
                DrawOverlappedWindowForAll (l, top + height + dy, w + l, top + height);
        }

        VideoDriver::GetActiveDriver()->MakeDirty (left, top, width, height);
}

/**
 * Repaints the rectangle blocks which are marked as 'dirty'.
 *
 * @see SetDirtyBlocks
 */
void DrawDirtyBlocks()
{
        byte *b = _dirty_blocks;
        const int w = Align (_screen_width,  DIRTY_BLOCK_WIDTH);
        const int h = Align (_screen_height, DIRTY_BLOCK_HEIGHT);
        int x;
        int y;

        if (HasModalProgress()) {
                /* We are generating the world, so release our rights to the map and
                 * painting while we are waiting a bit. */
                _modal_progress_paint_mutex->EndCritical();
                _modal_progress_work_mutex->EndCritical();

                /* Wait a while and update _realtime_tick so we are given the rights */
                if (!IsFirstModalProgressLoop()) CSleep(MODAL_PROGRESS_REDRAW_TIMEOUT);
                _realtime_tick += MODAL_PROGRESS_REDRAW_TIMEOUT;
                _modal_progress_paint_mutex->BeginCritical();
                _modal_progress_work_mutex->BeginCritical();

                /* When we ended with the modal progress, do not draw the blocks.
                 * Simply let the next run do so, otherwise we would be loading
                 * the new state (and possibly change the blitter) when we hold
                 * the drawing lock, which we must not do. */
                if (_switch_mode != SM_NONE && !HasModalProgress()) return;
        }

        y = 0;
        do {
                x = 0;
                do {
                        if (*b != 0) {
                                int left;
                                int top;
                                int right = x + DIRTY_BLOCK_WIDTH;
                                int bottom = y;
                                byte *p = b;
                                int h2;

                                /* First try coalescing downwards */
                                do {
                                        *p = 0;
                                        p += _dirty_bytes_per_line;
                                        bottom += DIRTY_BLOCK_HEIGHT;
                                } while (bottom != h && *p != 0);

                                /* Try coalescing to the right too. */
                                h2 = (bottom - y) / DIRTY_BLOCK_HEIGHT;
                                assert(h2 > 0);
                                p = b;

                                while (right != w) {
                                        byte *p2 = ++p;
                                        int h = h2;
                                        /* Check if a full line of dirty flags is set. */
                                        do {
                                                if (!*p2) goto no_more_coalesc;
                                                p2 += _dirty_bytes_per_line;
                                        } while (--h != 0);

                                        /* Wohoo, can combine it one step to the right!
                                         * Do that, and clear the bits. */
                                        right += DIRTY_BLOCK_WIDTH;

                                        h = h2;
                                        p2 = p;
                                        do {
                                                *p2 = 0;
                                                p2 += _dirty_bytes_per_line;
                                        } while (--h != 0);
                                }
                                no_more_coalesc:

                                left = x;
                                top = y;

                                if (left   < _invalid_rect.left  ) left   = _invalid_rect.left;
                                if (top    < _invalid_rect.top   ) top    = _invalid_rect.top;
                                if (right  > _invalid_rect.right ) right  = _invalid_rect.right;
                                if (bottom > _invalid_rect.bottom) bottom = _invalid_rect.bottom;

                                if (left < right && top < bottom) {
                                        RedrawScreenRect(left, top, right, bottom);
                                }

                        }
                } while (b++, (x += DIRTY_BLOCK_WIDTH) != w);
        } while (b += -(int)(w / DIRTY_BLOCK_WIDTH) + _dirty_bytes_per_line, (y += DIRTY_BLOCK_HEIGHT) != h);

        ++_dirty_block_colour;
        _invalid_rect.left = w;
        _invalid_rect.top = h;
        _invalid_rect.right = 0;
        _invalid_rect.bottom = 0;
}

/**
 * This function extends the internal _invalid_rect rectangle as it
 * now contains the rectangle defined by the given parameters. Note
 * the point (0,0) is top left.
 *
 * @param left The left edge of the rectangle
 * @param top The top edge of the rectangle
 * @param right The right edge of the rectangle
 * @param bottom The bottom edge of the rectangle
 * @see DrawDirtyBlocks
 *
 * @todo The name of the function should be called like @c AddDirtyBlock as
 *       it neither set a dirty rect nor add several dirty rects although
 *       the function name is in plural. (Progman)
 */
void SetDirtyBlocks(int left, int top, int right, int bottom)
{
        byte *b;
        int width;
        int height;

        if (left < 0) left = 0;
        if (top < 0) top = 0;
        if (right > _screen_width) right = _screen_width;
        if (bottom > _screen_height) bottom = _screen_height;

        if (left >= right || top >= bottom) return;

        if (left   < _invalid_rect.left  ) _invalid_rect.left   = left;
        if (top    < _invalid_rect.top   ) _invalid_rect.top    = top;
        if (right  > _invalid_rect.right ) _invalid_rect.right  = right;
        if (bottom > _invalid_rect.bottom) _invalid_rect.bottom = bottom;

        left /= DIRTY_BLOCK_WIDTH;
        top  /= DIRTY_BLOCK_HEIGHT;

        b = _dirty_blocks + top * _dirty_bytes_per_line + left;

        width  = ((right  - 1) / DIRTY_BLOCK_WIDTH)  - left + 1;
        height = ((bottom - 1) / DIRTY_BLOCK_HEIGHT) - top  + 1;

        assert(width > 0 && height > 0);

        do {
                int i = width;

                do b[--i] = 0xFF; while (i != 0);

                b += _dirty_bytes_per_line;
        } while (--height != 0);
}

/**
 * This function mark the whole screen as dirty. This results in repainting
 * the whole screen. Use this with care as this function will break the
 * idea about marking only parts of the screen as 'dirty'.
 * @ingroup dirty
 */
void MarkWholeScreenDirty()
{
        SetDirtyBlocks (0, 0, _screen_width, _screen_height);
}

/**
 * Set up a clipping area for only drawing into a certain area.
 * @param *o the parent BlitArea
 * @param *n the BlitArea that will be the clipping rectangle box allowed
 * for drawing
 * @param left,top,width,height the relative coordinates of the clipping
 * rectangle relative to the current area. This will most likely be the
 * offset from the calling window coordinates
 * @return return false if the requested rectangle is not possible with the
 * current dpi pointer. Only continue of the return value is true, or you'll
 * get some nasty results
 */
bool InitBlitArea (const BlitArea *o, BlitArea *n,
        int left, int top, int width, int height)
{
        assert(width > 0);
        assert(height > 0);

        if ((left -= o->left) < 0) {
                width += left;
                if (width <= 0) return false;
                n->left = -left;
                left = 0;
        } else {
                n->left = 0;
        }

        if (width > o->width - left) {
                width = o->width - left;
                if (width <= 0) return false;
        }
        n->width = width;

        if ((top -= o->top) < 0) {
                height += top;
                if (height <= 0) return false;
                n->top = -top;
                top = 0;
        } else {
                n->top = 0;
        }

        n->dst_ptr = o->surface->move (o->dst_ptr, left, top);
        n->surface = o->surface;

        if (height > o->height - top) {
                height = o->height - top;
                if (height <= 0) return false;
        }
        n->height = height;

        return true;
}

/**
 * Update cursor dimension.
 * Called when changing cursor sprite resp. reloading grfs.
 */
void UpdateCursorSize()
{
        /* Ignore setting any cursor before the sprites are loaded. */
        if (GetMaxSpriteID() == 0) return;

        assert(_cursor.sprite_count <= lengthof(_cursor.sprite_seq));
        for (uint i = 0; i < _cursor.sprite_count; ++i) {
                const Sprite *p = GetSprite(GB(_cursor.sprite_seq[i].sprite, 0, SPRITE_WIDTH), ST_NORMAL);
                Point offs, size;
                offs.x = UnScaleGUI(p->x_offs) + _cursor.sprite_seq[i].pos;
                offs.y = UnScaleGUI(p->y_offs);
                size.x = UnScaleGUI(p->width);
                size.y = UnScaleGUI(p->height);

                if (i == 0) {
                        _cursor.total_offs = offs;
                        _cursor.total_size = size;
                } else {
                        int right  = max(_cursor.total_offs.x + _cursor.total_size.x, offs.x + size.x);
                        int bottom = max(_cursor.total_offs.y + _cursor.total_size.y, offs.y + size.y);
                        if (offs.x < _cursor.total_offs.x) _cursor.total_offs.x = offs.x;
                        if (offs.y < _cursor.total_offs.y) _cursor.total_offs.y = offs.y;
                        _cursor.total_size.x = right  - _cursor.total_offs.x;
                        _cursor.total_size.y = bottom - _cursor.total_offs.y;
                }
        }

        _cursor.dirty = true;
}

/**
 * Switch cursor to different sprite.
 * @param cursor Sprite to draw for the cursor.
 * @param pal Palette to use for recolouring.
 */
static void SetCursorSprite(CursorID cursor, PaletteID pal)
{
        if (_cursor.sprite_count == 1 && _cursor.sprite_seq[0].sprite == cursor && _cursor.sprite_seq[0].pal == pal) return;

        _cursor.sprite_count = 1;
        _cursor.sprite_seq[0].sprite = cursor;
        _cursor.sprite_seq[0].pal = pal;
        _cursor.sprite_seq[0].pos = 0;

        UpdateCursorSize();
}

static void SwitchAnimatedCursor()
{
        const AnimCursor *cur = _cursor_animate_cur;

        if (cur == NULL || cur->sprite == AnimCursor::LAST) cur = _cursor_animate_list;

        SetCursorSprite(cur->sprite, _cursor.sprite_seq[0].pal);

        _cursor_animate_timeout = cur->display_time;
        _cursor_animate_cur     = cur + 1;
}

void CursorTick()
{
        if (_cursor_animate_timeout != 0 && --_cursor_animate_timeout == 0) {
                SwitchAnimatedCursor();
        }
}

/**
 * Set or unset the ZZZ cursor.
 * @param busy Whether to show the ZZZ cursor.
 */
void SetMouseCursorBusy(bool busy)
{
        if (busy) {
                if (_cursor.sprite_seq[0].sprite == SPR_CURSOR_MOUSE) SetMouseCursor (SPR_CURSOR_ZZZ);
        } else {
                if (_cursor.sprite_seq[0].sprite == SPR_CURSOR_ZZZ) SetMouseCursor (SPR_CURSOR_MOUSE);
        }
}

/**
 * Assign a single non-animated sprite to the cursor.
 * @param sprite Sprite to draw for the cursor.
 * @see SetAnimatedMouseCursor
 */
void SetMouseCursor (CursorID sprite)
{
        /* Turn off animation */
        _cursor_animate_timeout = 0;
        /* Set cursor */
        SetCursorSprite (sprite, PAL_NONE);
}

/**
 * Assign an animation to the cursor.
 * @param table Array of animation states.
 * @see SetMouseCursor
 */
void SetAnimatedMouseCursor(const AnimCursor *table)
{
        _cursor_animate_list = table;
        _cursor_animate_cur = NULL;
        _cursor.sprite_seq[0].pal = PAL_NONE;
        SwitchAnimatedCursor();
}

/**
 * Update cursor position on mouse movement.
 * @param x New X position.
 * @param y New Y position.
 * @param queued True, if the OS queues mouse warps after pending mouse movement events.
 *               False, if the warp applies instantaneous.
 * @return true, if the OS cursor position should be warped back to this->pos.
 */
bool CursorVars::UpdateCursorPosition(int x, int y, bool queued_warp)
{
        /* Detecting relative mouse movement is somewhat tricky.
         *  - There may be multiple mouse move events in the video driver queue (esp. when OpenTTD lags a bit).
         *  - When we request warping the mouse position (return true), a mouse move event is appended at the end of the queue.
         *
         * So, when this->fix_at is active, we use the following strategy:
         *  - The first movement triggers the warp to reset the mouse position.
         *  - Subsequent events have to compute movement relative to the previous event.
         *  - The relative movement is finished, when we receive the event matching the warp.
         */

        if (x == this->pos.x && y == this->pos.y) {
                /* Warp finished. */
                this->queued_warp = false;

                this->delta.x = 0;
                this->delta.y = 0;

                this->last_position.x = x;
                this->last_position.y = y;

                return false;
        }

        this->delta.x = x - (this->queued_warp ? this->last_position.x : this->pos.x);
        this->delta.y = y - (this->queued_warp ? this->last_position.y : this->pos.y);

        this->last_position.x = x;
        this->last_position.y = y;

        bool need_warp = false;
        if (!this->fix_at) {
                this->queued_warp = false; // Cancel warping, we are no longer confining the position.
                this->dirty = true;
                this->pos.x = x;
                this->pos.y = y;
        } else if (this->delta.x != 0 || this->delta.y != 0) {
                /* Trigger warp.
                 * Note: We also trigger warping again, if there is already a pending warp.
                 *       This makes it more tolerant about the OS or other software inbetween
                 *       botchering the warp. */
                this->queued_warp = queued_warp;
                need_warp = true;
        }
        return need_warp;
}

bool ChangeResInGame(int width, int height)
{
        return (_screen_width == width && _screen_height == height) || VideoDriver::GetActiveDriver()->ChangeResolution(width, height);
}

bool ToggleFullScreen(bool fs)
{
        bool result = VideoDriver::GetActiveDriver()->ToggleFullscreen(fs);
        if (_fullscreen != fs && _num_resolutions == 0) {
                DEBUG(driver, 0, "Could not find a suitable fullscreen resolution");
        }
        return result;
}

static int CDECL compare_res(const Dimension *pa, const Dimension *pb)
{
        int x = pa->width - pb->width;
        if (x != 0) return x;
        return pa->height - pb->height;
}

void SortResolutions(int count)
{
        QSortT(_resolutions, count, &compare_res);
}