src/spritecache.cpp

   1 /*
   2  * This file is part of OpenTTD.
   3  * 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.
   4  * 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.
   5  * 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/>.
   6  */
   7
   8 /** @file spritecache.cpp Caching of sprites. */
   9
  10 #include "stdafx.h"
  11 #include "random_access_file_type.h"
  12 #include "spriteloader/grf.hpp"
  13 #include "gfx_func.h"
  14 #include "error.h"
  15 #include "zoom_func.h"
  16 #include "settings_type.h"
  17 #include "blitter/factory.hpp"
  18 #include "core/math_func.hpp"
  19 #include "core/mem_func.hpp"
  20 #include "video/video_driver.hpp"
  21
  22 #include "table/sprites.h"
  23 #include "table/strings.h"
  24 #include "table/palette_convert.h"
  25
  26 #include "safeguards.h"
  27
  28 /* Default of 4MB spritecache */
  29 uint _sprite_cache_size = 4;
  30
  31 struct SpriteCache {
  32         void *ptr;
  33         size_t file_pos;
  34         SpriteFile *file;    ///< The file the sprite in this entry can be found in.
  35         uint32 id;
  36         int16 lru;
  37         SpriteType type;     ///< In some cases a single sprite is misused by two NewGRFs. Once as real sprite and once as recolour sprite. If the recolour sprite gets into the cache it might be drawn as real sprite which causes enormous trouble.
  38         bool warned;         ///< True iff the user has been warned about incorrect use of this sprite
  39 };
  40
  41
  42 static uint _spritecache_items = 0;
  43 static SpriteCache *_spritecache = nullptr;
  44 static std::vector<std::unique_ptr<SpriteFile>> _sprite_files;
  45
  46 static inline SpriteCache *GetSpriteCache(uint index)
  47 {
  48         return &_spritecache[index];
  49 }
  50
  51 static inline bool IsMapgenSpriteID(SpriteID sprite)
  52 {
  53         return IsInsideMM(sprite, 4845, 4882);
  54 }
  55
  56 static SpriteCache *AllocateSpriteCache(uint index)
  57 {
  58         if (index >= _spritecache_items) {
  59                 /* Add another 1024 items to the 'pool' */
  60                 uint items = Align(index + 1, 1024);
  61
  62                 Debug(sprite, 4, "Increasing sprite cache to {} items ({} bytes)", items, items * sizeof(*_spritecache));
  63
  64                 _spritecache = ReallocT(_spritecache, items);
  65
  66                 /* Reset the new items and update the count */
  67                 memset(_spritecache + _spritecache_items, 0, (items - _spritecache_items) * sizeof(*_spritecache));
  68                 _spritecache_items = items;
  69         }
  70
  71         return GetSpriteCache(index);
  72 }
  73
  74 /**
  75  * Get the cached SpriteFile given the name of the file.
  76  * @param filename The name of the file at the disk.
  77  * @return The SpriteFile or \c null.
  78  */
  79 static SpriteFile *GetCachedSpriteFileByName(const std::string &filename) {
  80         for (auto &f : _sprite_files) {
  81                 if (f->GetFilename() == filename) {
  82                         return f.get();
  83                 }
  84         }
  85         return nullptr;
  86 }
  87
  88 /**
  89  * Open/get the SpriteFile that is cached for use in the sprite cache.
  90  * @param filename      Name of the file at the disk.
  91  * @param subdir        The sub directory to search this file in.
  92  * @param palette_remap Whether a palette remap needs to be performed for this file.
  93  * @return The reference to the SpriteCache.
  94  */
  95 SpriteFile &OpenCachedSpriteFile(const std::string &filename, Subdirectory subdir, bool palette_remap)
  96 {
  97         SpriteFile *file = GetCachedSpriteFileByName(filename);
  98         if (file == nullptr) {
  99                 file = _sprite_files.emplace_back(new SpriteFile(filename, subdir, palette_remap)).get();
 100         } else {
 101                 file->SeekToBegin();
 102         }
 103         return *file;
 104 }
 105
 106 struct MemBlock {
 107         size_t size;
 108         byte data[];
 109 };
 110
 111 static uint _sprite_lru_counter;
 112 static MemBlock *_spritecache_ptr;
 113 static uint _allocated_sprite_cache_size = 0;
 114 static int _compact_cache_counter;
 115
 116 static void CompactSpriteCache();
 117 static void *AllocSprite(size_t mem_req);
 118
 119 /**
 120  * Skip the given amount of sprite graphics data.
 121  * @param type the type of sprite (compressed etc)
 122  * @param num the amount of sprites to skip
 123  * @return true if the data could be correctly skipped.
 124  */
 125 bool SkipSpriteData(SpriteFile &file, byte type, uint16 num)
 126 {
 127         if (type & 2) {
 128                 file.SkipBytes(num);
 129         } else {
 130                 while (num > 0) {
 131                         int8 i = file.ReadByte();
 132                         if (i >= 0) {
 133                                 int size = (i == 0) ? 0x80 : i;
 134                                 if (size > num) return false;
 135                                 num -= size;
 136                                 file.SkipBytes(size);
 137                         } else {
 138                                 i = -(i >> 3);
 139                                 num -= i;
 140                                 file.ReadByte();
 141                         }
 142                 }
 143         }
 144         return true;
 145 }
 146
 147 /* Check if the given Sprite ID exists */
 148 bool SpriteExists(SpriteID id)
 149 {
 150         if (id >= _spritecache_items) return false;
 151
 152         /* Special case for Sprite ID zero -- its position is also 0... */
 153         if (id == 0) return true;
 154         return !(GetSpriteCache(id)->file_pos == 0 && GetSpriteCache(id)->file == nullptr);
 155 }
 156
 157 /**
 158  * Get the sprite type of a given sprite.
 159  * @param sprite The sprite to look at.
 160  * @return the type of sprite.
 161  */
 162 SpriteType GetSpriteType(SpriteID sprite)
 163 {
 164         if (!SpriteExists(sprite)) return ST_INVALID;
 165         return GetSpriteCache(sprite)->type;
 166 }
 167
 168 /**
 169  * Get the SpriteFile of a given sprite.
 170  * @param sprite The sprite to look at.
 171  * @return The SpriteFile.
 172  */
 173 SpriteFile *GetOriginFile(SpriteID sprite)
 174 {
 175         if (!SpriteExists(sprite)) return nullptr;
 176         return GetSpriteCache(sprite)->file;
 177 }
 178
 179 /**
 180  * Get the GRF-local sprite id of a given sprite.
 181  * @param sprite The sprite to look at.
 182  * @return The GRF-local sprite id.
 183  */
 184 uint32 GetSpriteLocalID(SpriteID sprite)
 185 {
 186         if (!SpriteExists(sprite)) return 0;
 187         return GetSpriteCache(sprite)->id;
 188 }
 189
 190 /**
 191  * Count the sprites which originate from a specific file in a range of SpriteIDs.
 192  * @param file The loaded SpriteFile.
 193  * @param begin First sprite in range.
 194  * @param end First sprite not in range.
 195  * @return Number of sprites.
 196  */
 197 uint GetSpriteCountForFile(const std::string &filename, SpriteID begin, SpriteID end)
 198 {
 199         SpriteFile *file = GetCachedSpriteFileByName(filename);
 200         if (file == nullptr) return 0;
 201
 202         uint count = 0;
 203         for (SpriteID i = begin; i != end; i++) {
 204                 if (SpriteExists(i)) {
 205                         SpriteCache *sc = GetSpriteCache(i);
 206                         if (sc->file == file) count++;
 207                 }
 208         }
 209         return count;
 210 }
 211
 212 /**
 213  * Get a reasonable (upper bound) estimate of the maximum
 214  * SpriteID used in OpenTTD; there will be no sprites with
 215  * a higher SpriteID, although there might be up to roughly
 216  * a thousand unused SpriteIDs below this number.
 217  * @note It's actually the number of spritecache items.
 218  * @return maximum SpriteID
 219  */
 220 uint GetMaxSpriteID()
 221 {
 222         return _spritecache_items;
 223 }
 224
 225 static bool ResizeSpriteIn(SpriteLoader::Sprite *sprite, ZoomLevel src, ZoomLevel tgt)
 226 {
 227         uint8 scaled_1 = ScaleByZoom(1, (ZoomLevel)(src - tgt));
 228
 229         /* Check for possible memory overflow. */
 230         if (sprite[src].width * scaled_1 > UINT16_MAX || sprite[src].height * scaled_1 > UINT16_MAX) return false;
 231
 232         sprite[tgt].width  = sprite[src].width  * scaled_1;
 233         sprite[tgt].height = sprite[src].height * scaled_1;
 234         sprite[tgt].x_offs = sprite[src].x_offs * scaled_1;
 235         sprite[tgt].y_offs = sprite[src].y_offs * scaled_1;
 236         sprite[tgt].colours = sprite[src].colours;
 237
 238         sprite[tgt].AllocateData(tgt, sprite[tgt].width * sprite[tgt].height);
 239
 240         SpriteLoader::CommonPixel *dst = sprite[tgt].data;
 241         for (int y = 0; y < sprite[tgt].height; y++) {
 242                 const SpriteLoader::CommonPixel *src_ln = &sprite[src].data[y / scaled_1 * sprite[src].width];
 243                 for (int x = 0; x < sprite[tgt].width; x++) {
 244                         *dst = src_ln[x / scaled_1];
 245                         dst++;
 246                 }
 247         }
 248
 249         return true;
 250 }
 251
 252 static void ResizeSpriteOut(SpriteLoader::Sprite *sprite, ZoomLevel zoom)
 253 {
 254         /* Algorithm based on 32bpp_Optimized::ResizeSprite() */
 255         sprite[zoom].width  = UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].width,  zoom);
 256         sprite[zoom].height = UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].height, zoom);
 257         sprite[zoom].x_offs = UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].x_offs, zoom);
 258         sprite[zoom].y_offs = UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].y_offs, zoom);
 259         sprite[zoom].colours = sprite[ZOOM_LVL_NORMAL].colours;
 260
 261         sprite[zoom].AllocateData(zoom, sprite[zoom].height * sprite[zoom].width);
 262
 263         SpriteLoader::CommonPixel *dst = sprite[zoom].data;
 264         const SpriteLoader::CommonPixel *src = sprite[zoom - 1].data;
 265         [[maybe_unused]] const SpriteLoader::CommonPixel *src_end = src + sprite[zoom - 1].height * sprite[zoom - 1].width;
 266
 267         for (uint y = 0; y < sprite[zoom].height; y++) {
 268                 const SpriteLoader::CommonPixel *src_ln = src + sprite[zoom - 1].width;
 269                 assert(src_ln <= src_end);
 270                 for (uint x = 0; x < sprite[zoom].width; x++) {
 271                         assert(src < src_ln);
 272                         if (src + 1 != src_ln && (src + 1)->a != 0) {
 273                                 *dst = *(src + 1);
 274                         } else {
 275                                 *dst = *src;
 276                         }
 277                         dst++;
 278                         src += 2;
 279                 }
 280                 src = src_ln + sprite[zoom - 1].width;
 281         }
 282 }
 283
 284 static bool PadSingleSprite(SpriteLoader::Sprite *sprite, ZoomLevel zoom, uint pad_left, uint pad_top, uint pad_right, uint pad_bottom)
 285 {
 286         uint width  = sprite->width + pad_left + pad_right;
 287         uint height = sprite->height + pad_top + pad_bottom;
 288
 289         if (width > UINT16_MAX || height > UINT16_MAX) return false;
 290
 291         /* Copy source data and reallocate sprite memory. */
 292         SpriteLoader::CommonPixel *src_data = MallocT<SpriteLoader::CommonPixel>(sprite->width * sprite->height);
 293         MemCpyT(src_data, sprite->data, sprite->width * sprite->height);
 294         sprite->AllocateData(zoom, width * height);
 295
 296         /* Copy with padding to destination. */
 297         SpriteLoader::CommonPixel *src = src_data;
 298         SpriteLoader::CommonPixel *data = sprite->data;
 299         for (uint y = 0; y < height; y++) {
 300                 if (y < pad_top || pad_bottom + y >= height) {
 301                         /* Top/bottom padding. */
 302                         MemSetT(data, 0, width);
 303                         data += width;
 304                 } else {
 305                         if (pad_left > 0) {
 306                                 /* Pad left. */
 307                                 MemSetT(data, 0, pad_left);
 308                                 data += pad_left;
 309                         }
 310
 311                         /* Copy pixels. */
 312                         MemCpyT(data, src, sprite->width);
 313                         src += sprite->width;
 314                         data += sprite->width;
 315
 316                         if (pad_right > 0) {
 317                                 /* Pad right. */
 318                                 MemSetT(data, 0, pad_right);
 319                                 data += pad_right;
 320                         }
 321                 }
 322         }
 323         free(src_data);
 324
 325         /* Update sprite size. */
 326         sprite->width   = width;
 327         sprite->height  = height;
 328         sprite->x_offs -= pad_left;
 329         sprite->y_offs -= pad_top;
 330
 331         return true;
 332 }
 333
 334 static bool PadSprites(SpriteLoader::Sprite *sprite, uint8 sprite_avail, SpriteEncoder *encoder)
 335 {
 336         /* Get minimum top left corner coordinates. */
 337         int min_xoffs = INT32_MAX;
 338         int min_yoffs = INT32_MAX;
 339         for (ZoomLevel zoom = ZOOM_LVL_BEGIN; zoom != ZOOM_LVL_END; zoom++) {
 340                 if (HasBit(sprite_avail, zoom)) {
 341                         min_xoffs = std::min(min_xoffs, ScaleByZoom(sprite[zoom].x_offs, zoom));
 342                         min_yoffs = std::min(min_yoffs, ScaleByZoom(sprite[zoom].y_offs, zoom));
 343                 }
 344         }
 345
 346         /* Get maximum dimensions taking necessary padding at the top left into account. */
 347         int max_width  = INT32_MIN;
 348         int max_height = INT32_MIN;
 349         for (ZoomLevel zoom = ZOOM_LVL_BEGIN; zoom != ZOOM_LVL_END; zoom++) {
 350                 if (HasBit(sprite_avail, zoom)) {
 351                         max_width  = std::max(max_width, ScaleByZoom(sprite[zoom].width + sprite[zoom].x_offs - UnScaleByZoom(min_xoffs, zoom), zoom));
 352                         max_height = std::max(max_height, ScaleByZoom(sprite[zoom].height + sprite[zoom].y_offs - UnScaleByZoom(min_yoffs, zoom), zoom));
 353                 }
 354         }
 355
 356         /* Align height and width if required to match the needs of the sprite encoder. */
 357         uint align = encoder->GetSpriteAlignment();
 358         if (align != 0) {
 359                 max_width  = Align(max_width,  align);
 360                 max_height = Align(max_height, align);
 361         }
 362
 363         /* Pad sprites where needed. */
 364         for (ZoomLevel zoom = ZOOM_LVL_BEGIN; zoom != ZOOM_LVL_END; zoom++) {
 365                 if (HasBit(sprite_avail, zoom)) {
 366                         /* Scaling the sprite dimensions in the blitter is done with rounding up,
 367                          * so a negative padding here is not an error. */
 368                         int pad_left   = std::max(0, sprite[zoom].x_offs - UnScaleByZoom(min_xoffs, zoom));
 369                         int pad_top    = std::max(0, sprite[zoom].y_offs - UnScaleByZoom(min_yoffs, zoom));
 370                         int pad_right  = std::max(0, UnScaleByZoom(max_width, zoom) - sprite[zoom].width - pad_left);
 371                         int pad_bottom = std::max(0, UnScaleByZoom(max_height, zoom) - sprite[zoom].height - pad_top);
 372
 373                         if (pad_left > 0 || pad_right > 0 || pad_top > 0 || pad_bottom > 0) {
 374                                 if (!PadSingleSprite(&sprite[zoom], zoom, pad_left, pad_top, pad_right, pad_bottom)) return false;
 375                         }
 376                 }
 377         }
 378
 379         return true;
 380 }
 381
 382 static bool ResizeSprites(SpriteLoader::Sprite *sprite, uint8 sprite_avail, SpriteEncoder *encoder)
 383 {
 384         /* Create a fully zoomed image if it does not exist */
 385         ZoomLevel first_avail = static_cast<ZoomLevel>(FIND_FIRST_BIT(sprite_avail));
 386         if (first_avail != ZOOM_LVL_NORMAL) {
 387                 if (!ResizeSpriteIn(sprite, first_avail, ZOOM_LVL_NORMAL)) return false;
 388                 SetBit(sprite_avail, ZOOM_LVL_NORMAL);
 389         }
 390
 391         /* Pad sprites to make sizes match. */
 392         if (!PadSprites(sprite, sprite_avail, encoder)) return false;
 393
 394         /* Create other missing zoom levels */
 395         for (ZoomLevel zoom = ZOOM_LVL_OUT_2X; zoom != ZOOM_LVL_END; zoom++) {
 396                 if (HasBit(sprite_avail, zoom)) {
 397                         /* Check that size and offsets match the fully zoomed image. */
 398                         assert(sprite[zoom].width  == UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].width,  zoom));
 399                         assert(sprite[zoom].height == UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].height, zoom));
 400                         assert(sprite[zoom].x_offs == UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].x_offs, zoom));
 401                         assert(sprite[zoom].y_offs == UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].y_offs, zoom));
 402                 }
 403
 404                 /* Zoom level is not available, or unusable, so create it */
 405                 if (!HasBit(sprite_avail, zoom)) ResizeSpriteOut(sprite, zoom);
 406         }
 407
 408         return  true;
 409 }
 410
 411 /**
 412  * Load a recolour sprite into memory.
 413  * @param file GRF we're reading from.
 414  * @param num Size of the sprite in the GRF.
 415  * @return Sprite data.
 416  */
 417 static void *ReadRecolourSprite(SpriteFile &file, uint num)
 418 {
 419         /* "Normal" recolour sprites are ALWAYS 257 bytes. Then there is a small
 420          * number of recolour sprites that are 17 bytes that only exist in DOS
 421          * GRFs which are the same as 257 byte recolour sprites, but with the last
 422          * 240 bytes zeroed.  */
 423         static const uint RECOLOUR_SPRITE_SIZE = 257;
 424         byte *dest = (byte *)AllocSprite(std::max(RECOLOUR_SPRITE_SIZE, num));
 425
 426         if (file.NeedsPaletteRemap()) {
 427                 byte *dest_tmp = AllocaM(byte, std::max(RECOLOUR_SPRITE_SIZE, num));
 428
 429                 /* Only a few recolour sprites are less than 257 bytes */
 430                 if (num < RECOLOUR_SPRITE_SIZE) memset(dest_tmp, 0, RECOLOUR_SPRITE_SIZE);
 431                 file.ReadBlock(dest_tmp, num);
 432
 433                 /* The data of index 0 is never used; "literal 00" according to the (New)GRF specs. */
 434                 for (uint i = 1; i < RECOLOUR_SPRITE_SIZE; i++) {
 435                         dest[i] = _palmap_w2d[dest_tmp[_palmap_d2w[i - 1] + 1]];
 436                 }
 437         } else {
 438                 file.ReadBlock(dest, num);
 439         }
 440
 441         return dest;
 442 }
 443
 444 /**
 445  * Read a sprite from disk.
 446  * @param sc          Location of sprite.
 447  * @param id          Sprite number.
 448  * @param sprite_type Type of sprite.
 449  * @param allocator   Allocator function to use.
 450  * @param encoder     Sprite encoder to use.
 451  * @return Read sprite data.
 452  */
 453 static void *ReadSprite(const SpriteCache *sc, SpriteID id, SpriteType sprite_type, AllocatorProc *allocator, SpriteEncoder *encoder)
 454 {
 455         /* Use current blitter if no other sprite encoder is given. */
 456         if (encoder == nullptr) encoder = BlitterFactory::GetCurrentBlitter();
 457
 458         SpriteFile &file = *sc->file;
 459         size_t file_pos = sc->file_pos;
 460
 461         assert(sprite_type != ST_RECOLOUR);
 462         assert(IsMapgenSpriteID(id) == (sprite_type == ST_MAPGEN));
 463         assert(sc->type == sprite_type);
 464
 465         Debug(sprite, 9, "Load sprite {}", id);
 466
 467         SpriteLoader::Sprite sprite[ZOOM_LVL_COUNT];
 468         uint8 sprite_avail = 0;
 469         sprite[ZOOM_LVL_NORMAL].type = sprite_type;
 470
 471         SpriteLoaderGrf sprite_loader(file.GetContainerVersion());
 472         if (sprite_type != ST_MAPGEN && encoder->Is32BppSupported()) {
 473                 /* Try for 32bpp sprites first. */
 474                 sprite_avail = sprite_loader.LoadSprite(sprite, file, file_pos, sprite_type, true);
 475         }
 476         if (sprite_avail == 0) {
 477                 sprite_avail = sprite_loader.LoadSprite(sprite, file, file_pos, sprite_type, false);
 478         }
 479
 480         if (sprite_avail == 0) {
 481                 if (sprite_type == ST_MAPGEN) return nullptr;
 482                 if (id == SPR_IMG_QUERY) usererror("Okay... something went horribly wrong. I couldn't load the fallback sprite. What should I do?");
 483                 return (void*)GetRawSprite(SPR_IMG_QUERY, ST_NORMAL, allocator, encoder);
 484         }
 485
 486         if (sprite_type == ST_MAPGEN) {
 487                 /* Ugly hack to work around the problem that the old landscape
 488                  *  generator assumes that those sprites are stored uncompressed in
 489                  *  the memory, and they are only read directly by the code, never
 490                  *  send to the blitter. So do not send it to the blitter (which will
 491                  *  result in a data array in the format the blitter likes most), but
 492                  *  extract the data directly and store that as sprite.
 493                  * Ugly: yes. Other solution: no. Blame the original author or
 494                  *  something ;) The image should really have been a data-stream
 495                  *  (so type = 0xFF basically). */
 496                 uint num = sprite[ZOOM_LVL_NORMAL].width * sprite[ZOOM_LVL_NORMAL].height;
 497
 498                 Sprite *s = (Sprite *)allocator(sizeof(*s) + num);
 499                 s->width  = sprite[ZOOM_LVL_NORMAL].width;
 500                 s->height = sprite[ZOOM_LVL_NORMAL].height;
 501                 s->x_offs = sprite[ZOOM_LVL_NORMAL].x_offs;
 502                 s->y_offs = sprite[ZOOM_LVL_NORMAL].y_offs;
 503
 504                 SpriteLoader::CommonPixel *src = sprite[ZOOM_LVL_NORMAL].data;
 505                 byte *dest = s->data;
 506                 while (num-- > 0) {
 507                         *dest++ = src->m;
 508                         src++;
 509                 }
 510
 511                 return s;
 512         }
 513
 514         if (!ResizeSprites(sprite, sprite_avail, encoder)) {
 515                 if (id == SPR_IMG_QUERY) usererror("Okay... something went horribly wrong. I couldn't resize the fallback sprite. What should I do?");
 516                 return (void*)GetRawSprite(SPR_IMG_QUERY, ST_NORMAL, allocator, encoder);
 517         }
 518
 519         if (sprite->type == ST_FONT && ZOOM_LVL_FONT != ZOOM_LVL_NORMAL) {
 520                 /* Make ZOOM_LVL_NORMAL be ZOOM_LVL_FONT */
 521                 sprite[ZOOM_LVL_NORMAL].width  = sprite[ZOOM_LVL_FONT].width;
 522                 sprite[ZOOM_LVL_NORMAL].height = sprite[ZOOM_LVL_FONT].height;
 523                 sprite[ZOOM_LVL_NORMAL].x_offs = sprite[ZOOM_LVL_FONT].x_offs;
 524                 sprite[ZOOM_LVL_NORMAL].y_offs = sprite[ZOOM_LVL_FONT].y_offs;
 525                 sprite[ZOOM_LVL_NORMAL].data   = sprite[ZOOM_LVL_FONT].data;
 526                 sprite[ZOOM_LVL_NORMAL].colours = sprite[ZOOM_LVL_FONT].colours;
 527         }
 528
 529         return encoder->Encode(sprite, allocator);
 530 }
 531
 532
 533 /** Map from sprite numbers to position in the GRF file. */
 534 static std::map<uint32, size_t> _grf_sprite_offsets;
 535
 536 /**
 537  * Get the file offset for a specific sprite in the sprite section of a GRF.
 538  * @param id ID of the sprite to look up.
 539  * @return Position of the sprite in the sprite section or SIZE_MAX if no such sprite is present.
 540  */
 541 size_t GetGRFSpriteOffset(uint32 id)
 542 {
 543         return _grf_sprite_offsets.find(id) != _grf_sprite_offsets.end() ? _grf_sprite_offsets[id] : SIZE_MAX;
 544 }
 545
 546 /**
 547  * Parse the sprite section of GRFs.
 548  * @param container_version Container version of the GRF we're currently processing.
 549  */
 550 void ReadGRFSpriteOffsets(SpriteFile &file)
 551 {
 552         _grf_sprite_offsets.clear();
 553
 554         if (file.GetContainerVersion() >= 2) {
 555                 /* Seek to sprite section of the GRF. */
 556                 size_t data_offset = file.ReadDword();
 557                 size_t old_pos = file.GetPos();
 558                 file.SeekTo(data_offset, SEEK_CUR);
 559
 560                 /* Loop over all sprite section entries and store the file
 561                  * offset for each newly encountered ID. */
 562                 uint32 id, prev_id = 0;
 563                 while ((id = file.ReadDword()) != 0) {
 564                         if (id != prev_id) _grf_sprite_offsets[id] = file.GetPos() - 4;
 565                         prev_id = id;
 566                         file.SkipBytes(file.ReadDword());
 567                 }
 568
 569                 /* Continue processing the data section. */
 570                 file.SeekTo(old_pos, SEEK_SET);
 571         }
 572 }
 573
 574
 575 /**
 576  * Load a real or recolour sprite.
 577  * @param load_index Global sprite index.
 578  * @param file GRF to load from.
 579  * @param file_sprite_id Sprite number in the GRF.
 580  * @param container_version Container version of the GRF.
 581  * @return True if a valid sprite was loaded, false on any error.
 582  */
 583 bool LoadNextSprite(int load_index, SpriteFile &file, uint file_sprite_id)
 584 {
 585         size_t file_pos = file.GetPos();
 586
 587         /* Read sprite header. */
 588         uint32 num = file.GetContainerVersion() >= 2 ? file.ReadDword() : file.ReadWord();
 589         if (num == 0) return false;
 590         byte grf_type = file.ReadByte();
 591
 592         SpriteType type;
 593         void *data = nullptr;
 594         if (grf_type == 0xFF) {
 595                 /* Some NewGRF files have "empty" pseudo-sprites which are 1
 596                  * byte long. Catch these so the sprites won't be displayed. */
 597                 if (num == 1) {
 598                         file.ReadByte();
 599                         return false;
 600                 }
 601                 type = ST_RECOLOUR;
 602                 data = ReadRecolourSprite(file, num);
 603         } else if (file.GetContainerVersion() >= 2 && grf_type == 0xFD) {
 604                 if (num != 4) {
 605                         /* Invalid sprite section include, ignore. */
 606                         file.SkipBytes(num);
 607                         return false;
 608                 }
 609                 /* It is not an error if no sprite with the provided ID is found in the sprite section. */
 610                 file_pos = GetGRFSpriteOffset(file.ReadDword());
 611                 type = ST_NORMAL;
 612         } else {
 613                 file.SkipBytes(7);
 614                 type = SkipSpriteData(file, grf_type, num - 8) ? ST_NORMAL : ST_INVALID;
 615                 /* Inline sprites are not supported for container version >= 2. */
 616                 if (file.GetContainerVersion() >= 2) return false;
 617         }
 618
 619         if (type == ST_INVALID) return false;
 620
 621         if (load_index >= MAX_SPRITES) {
 622                 usererror("Tried to load too many sprites (#%d; max %d)", load_index, MAX_SPRITES);
 623         }
 624
 625         bool is_mapgen = IsMapgenSpriteID(load_index);
 626
 627         if (is_mapgen) {
 628                 if (type != ST_NORMAL) usererror("Uhm, would you be so kind not to load a NewGRF that changes the type of the map generator sprites?");
 629                 type = ST_MAPGEN;
 630         }
 631
 632         SpriteCache *sc = AllocateSpriteCache(load_index);
 633         sc->file = &file;
 634         sc->file_pos = file_pos;
 635         sc->ptr = data;
 636         sc->lru = 0;
 637         sc->id = file_sprite_id;
 638         sc->type = type;
 639         sc->warned = false;
 640
 641         return true;
 642 }
 643
 644
 645 void DupSprite(SpriteID old_spr, SpriteID new_spr)
 646 {
 647         SpriteCache *scnew = AllocateSpriteCache(new_spr); // may reallocate: so put it first
 648         SpriteCache *scold = GetSpriteCache(old_spr);
 649
 650         scnew->file = scold->file;
 651         scnew->file_pos = scold->file_pos;
 652         scnew->ptr = nullptr;
 653         scnew->id = scold->id;
 654         scnew->type = scold->type;
 655         scnew->warned = false;
 656 }
 657
 658 /**
 659  * S_FREE_MASK is used to mask-out lower bits of MemBlock::size
 660  * If they are non-zero, the block is free.
 661  * S_FREE_MASK has to ensure MemBlock is correctly aligned -
 662  * it means 8B (S_FREE_MASK == 7) on 64bit systems!
 663  */
 664 static const size_t S_FREE_MASK = sizeof(size_t) - 1;
 665
 666 /* to make sure nobody adds things to MemBlock without checking S_FREE_MASK first */
 667 static_assert(sizeof(MemBlock) == sizeof(size_t));
 668 /* make sure it's a power of two */
 669 static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
 670
 671 static inline MemBlock *NextBlock(MemBlock *block)
 672 {
 673         return (MemBlock*)((byte*)block + (block->size & ~S_FREE_MASK));
 674 }
 675
 676 static size_t GetSpriteCacheUsage()
 677 {
 678         size_t tot_size = 0;
 679         MemBlock *s;
 680
 681         for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
 682                 if (!(s->size & S_FREE_MASK)) tot_size += s->size;
 683         }
 684
 685         return tot_size;
 686 }
 687
 688
 689 void IncreaseSpriteLRU()
 690 {
 691         /* Increase all LRU values */
 692         if (_sprite_lru_counter > 16384) {
 693                 SpriteID i;
 694
 695                 Debug(sprite, 3, "Fixing lru {}, inuse={}", _sprite_lru_counter, GetSpriteCacheUsage());
 696
 697                 for (i = 0; i != _spritecache_items; i++) {
 698                         SpriteCache *sc = GetSpriteCache(i);
 699                         if (sc->ptr != nullptr) {
 700                                 if (sc->lru >= 0) {
 701                                         sc->lru = -1;
 702                                 } else if (sc->lru != -32768) {
 703                                         sc->lru--;
 704                                 }
 705                         }
 706                 }
 707                 _sprite_lru_counter = 0;
 708         }
 709
 710         /* Compact sprite cache every now and then. */
 711         if (++_compact_cache_counter >= 740) {
 712                 CompactSpriteCache();
 713                 _compact_cache_counter = 0;
 714         }
 715 }
 716
 717 /**
 718  * Called when holes in the sprite cache should be removed.
 719  * That is accomplished by moving the cached data.
 720  */
 721 static void CompactSpriteCache()
 722 {
 723         MemBlock *s;
 724
 725         Debug(sprite, 3, "Compacting sprite cache, inuse={}", GetSpriteCacheUsage());
 726
 727         for (s = _spritecache_ptr; s->size != 0;) {
 728                 if (s->size & S_FREE_MASK) {
 729                         MemBlock *next = NextBlock(s);
 730                         MemBlock temp;
 731                         SpriteID i;
 732
 733                         /* Since free blocks are automatically coalesced, this should hold true. */
 734                         assert(!(next->size & S_FREE_MASK));
 735
 736                         /* If the next block is the sentinel block, we can safely return */
 737                         if (next->size == 0) break;
 738
 739                         /* Locate the sprite belonging to the next pointer. */
 740                         for (i = 0; GetSpriteCache(i)->ptr != next->data; i++) {
 741                                 assert(i != _spritecache_items);
 742                         }
 743
 744                         GetSpriteCache(i)->ptr = s->data; // Adjust sprite array entry
 745                         /* Swap this and the next block */
 746                         temp = *s;
 747                         memmove(s, next, next->size);
 748                         s = NextBlock(s);
 749                         *s = temp;
 750
 751                         /* Coalesce free blocks */
 752                         while (NextBlock(s)->size & S_FREE_MASK) {
 753                                 s->size += NextBlock(s)->size & ~S_FREE_MASK;
 754                         }
 755                 } else {
 756                         s = NextBlock(s);
 757                 }
 758         }
 759 }
 760
 761 /**
 762  * Delete a single entry from the sprite cache.
 763  * @param item Entry to delete.
 764  */
 765 static void DeleteEntryFromSpriteCache(uint item)
 766 {
 767         /* Mark the block as free (the block must be in use) */
 768         MemBlock *s = (MemBlock*)GetSpriteCache(item)->ptr - 1;
 769         assert(!(s->size & S_FREE_MASK));
 770         s->size |= S_FREE_MASK;
 771         GetSpriteCache(item)->ptr = nullptr;
 772
 773         /* And coalesce adjacent free blocks */
 774         for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
 775                 if (s->size & S_FREE_MASK) {
 776                         while (NextBlock(s)->size & S_FREE_MASK) {
 777                                 s->size += NextBlock(s)->size & ~S_FREE_MASK;
 778                         }
 779                 }
 780         }
 781 }
 782
 783 static void DeleteEntryFromSpriteCache()
 784 {
 785         uint best = UINT_MAX;
 786         int cur_lru;
 787
 788         Debug(sprite, 3, "DeleteEntryFromSpriteCache, inuse={}", GetSpriteCacheUsage());
 789
 790         cur_lru = 0xffff;
 791         for (SpriteID i = 0; i != _spritecache_items; i++) {
 792                 SpriteCache *sc = GetSpriteCache(i);
 793                 if (sc->type != ST_RECOLOUR && sc->ptr != nullptr && sc->lru < cur_lru) {
 794                         cur_lru = sc->lru;
 795                         best = i;
 796                 }
 797         }
 798
 799         /* Display an error message and die, in case we found no sprite at all.
 800          * This shouldn't really happen, unless all sprites are locked. */
 801         if (best == UINT_MAX) error("Out of sprite memory");
 802
 803         DeleteEntryFromSpriteCache(best);
 804 }
 805
 806 static void *AllocSprite(size_t mem_req)
 807 {
 808         mem_req += sizeof(MemBlock);
 809
 810         /* Align this to correct boundary. This also makes sure at least one
 811          * bit is not used, so we can use it for other things. */
 812         mem_req = Align(mem_req, S_FREE_MASK + 1);
 813
 814         for (;;) {
 815                 MemBlock *s;
 816
 817                 for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
 818                         if (s->size & S_FREE_MASK) {
 819                                 size_t cur_size = s->size & ~S_FREE_MASK;
 820
 821                                 /* Is the block exactly the size we need or
 822                                  * big enough for an additional free block? */
 823                                 if (cur_size == mem_req ||
 824                                                 cur_size >= mem_req + sizeof(MemBlock)) {
 825                                         /* Set size and in use */
 826                                         s->size = mem_req;
 827
 828                                         /* Do we need to inject a free block too? */
 829                                         if (cur_size != mem_req) {
 830                                                 NextBlock(s)->size = (cur_size - mem_req) | S_FREE_MASK;
 831                                         }
 832
 833                                         return s->data;
 834                                 }
 835                         }
 836                 }
 837
 838                 /* Reached sentinel, but no block found yet. Delete some old entry. */
 839                 DeleteEntryFromSpriteCache();
 840         }
 841 }
 842
 843 /**
 844  * Sprite allocator simply using malloc.
 845  */
 846 void *SimpleSpriteAlloc(size_t size)
 847 {
 848         return MallocT<byte>(size);
 849 }
 850
 851 /**
 852  * Handles the case when a sprite of different type is requested than is present in the SpriteCache.
 853  * For ST_FONT sprites, it is normal. In other cases, default sprite is loaded instead.
 854  * @param sprite ID of loaded sprite
 855  * @param requested requested sprite type
 856  * @param sc the currently known sprite cache for the requested sprite
 857  * @return fallback sprite
 858  * @note this function will do usererror() in the case the fallback sprite isn't available
 859  */
 860 static void *HandleInvalidSpriteRequest(SpriteID sprite, SpriteType requested, SpriteCache *sc, AllocatorProc *allocator)
 861 {
 862         static const char * const sprite_types[] = {
 863                 "normal",        // ST_NORMAL
 864                 "map generator", // ST_MAPGEN
 865                 "character",     // ST_FONT
 866                 "recolour",      // ST_RECOLOUR
 867         };
 868
 869         SpriteType available = sc->type;
 870         if (requested == ST_FONT && available == ST_NORMAL) {
 871                 if (sc->ptr == nullptr) sc->type = ST_FONT;
 872                 return GetRawSprite(sprite, sc->type, allocator);
 873         }
 874
 875         byte warning_level = sc->warned ? 6 : 0;
 876         sc->warned = true;
 877         Debug(sprite, warning_level, "Tried to load {} sprite #{} as a {} sprite. Probable cause: NewGRF interference", sprite_types[available], sprite, sprite_types[requested]);
 878
 879         switch (requested) {
 880                 case ST_NORMAL:
 881                         if (sprite == SPR_IMG_QUERY) usererror("Uhm, would you be so kind not to load a NewGRF that makes the 'query' sprite a non-normal sprite?");
 882                         FALLTHROUGH;
 883                 case ST_FONT:
 884                         return GetRawSprite(SPR_IMG_QUERY, ST_NORMAL, allocator);
 885                 case ST_RECOLOUR:
 886                         if (sprite == PALETTE_TO_DARK_BLUE) usererror("Uhm, would you be so kind not to load a NewGRF that makes the 'PALETTE_TO_DARK_BLUE' sprite a non-remap sprite?");
 887                         return GetRawSprite(PALETTE_TO_DARK_BLUE, ST_RECOLOUR, allocator);
 888                 case ST_MAPGEN:
 889                         /* this shouldn't happen, overriding of ST_MAPGEN sprites is checked in LoadNextSprite()
 890                          * (the only case the check fails is when these sprites weren't even loaded...) */
 891                 default:
 892                         NOT_REACHED();
 893         }
 894 }
 895
 896 /**
 897  * Reads a sprite (from disk or sprite cache).
 898  * If the sprite is not available or of wrong type, a fallback sprite is returned.
 899  * @param sprite Sprite to read.
 900  * @param type Expected sprite type.
 901  * @param allocator Allocator function to use. Set to nullptr to use the usual sprite cache.
 902  * @param encoder Sprite encoder to use. Set to nullptr to use the currently active blitter.
 903  * @return Sprite raw data
 904  */
 905 void *GetRawSprite(SpriteID sprite, SpriteType type, AllocatorProc *allocator, SpriteEncoder *encoder)
 906 {
 907         assert(type != ST_MAPGEN || IsMapgenSpriteID(sprite));
 908         assert(type < ST_INVALID);
 909
 910         if (!SpriteExists(sprite)) {
 911                 Debug(sprite, 1, "Tried to load non-existing sprite #{}. Probable cause: Wrong/missing NewGRFs", sprite);
 912
 913                 /* SPR_IMG_QUERY is a BIG FAT RED ? */
 914                 sprite = SPR_IMG_QUERY;
 915         }
 916
 917         SpriteCache *sc = GetSpriteCache(sprite);
 918
 919         if (sc->type != type) return HandleInvalidSpriteRequest(sprite, type, sc, allocator);
 920
 921         if (allocator == nullptr && encoder == nullptr) {
 922                 /* Load sprite into/from spritecache */
 923
 924                 /* Update LRU */
 925                 sc->lru = ++_sprite_lru_counter;
 926
 927                 /* Load the sprite, if it is not loaded, yet */
 928                 if (sc->ptr == nullptr) sc->ptr = ReadSprite(sc, sprite, type, AllocSprite, nullptr);
 929
 930                 return sc->ptr;
 931         } else {
 932                 /* Do not use the spritecache, but a different allocator. */
 933                 return ReadSprite(sc, sprite, type, allocator, encoder);
 934         }
 935 }
 936
 937
 938 static void GfxInitSpriteCache()
 939 {
 940         /* initialize sprite cache heap */
 941         int bpp = BlitterFactory::GetCurrentBlitter()->GetScreenDepth();
 942         uint target_size = (bpp > 0 ? _sprite_cache_size * bpp / 8 : 1) * 1024 * 1024;
 943
 944         /* Remember 'target_size' from the previous allocation attempt, so we do not try to reach the target_size multiple times in case of failure. */
 945         static uint last_alloc_attempt = 0;
 946
 947         if (_spritecache_ptr == nullptr || (_allocated_sprite_cache_size != target_size && target_size != last_alloc_attempt)) {
 948                 delete[] reinterpret_cast<byte *>(_spritecache_ptr);
 949
 950                 last_alloc_attempt = target_size;
 951                 _allocated_sprite_cache_size = target_size;
 952
 953                 do {
 954                         try {
 955                                 /* Try to allocate 50% more to make sure we do not allocate almost all available. */
 956                                 _spritecache_ptr = reinterpret_cast<MemBlock *>(new byte[_allocated_sprite_cache_size + _allocated_sprite_cache_size / 2]);
 957                         } catch (std::bad_alloc &) {
 958                                 _spritecache_ptr = nullptr;
 959                         }
 960
 961                         if (_spritecache_ptr != nullptr) {
 962                                 /* Allocation succeeded, but we wanted less. */
 963                                 delete[] reinterpret_cast<byte *>(_spritecache_ptr);
 964                                 _spritecache_ptr = reinterpret_cast<MemBlock *>(new byte[_allocated_sprite_cache_size]);
 965                         } else if (_allocated_sprite_cache_size < 2 * 1024 * 1024) {
 966                                 usererror("Cannot allocate spritecache");
 967                         } else {
 968                                 /* Try again to allocate half. */
 969                                 _allocated_sprite_cache_size >>= 1;
 970                         }
 971                 } while (_spritecache_ptr == nullptr);
 972
 973                 if (_allocated_sprite_cache_size != target_size) {
 974                         Debug(misc, 0, "Not enough memory to allocate {} MiB of spritecache. Spritecache was reduced to {} MiB.", target_size / 1024 / 1024, _allocated_sprite_cache_size / 1024 / 1024);
 975
 976                         ErrorMessageData msg(STR_CONFIG_ERROR_OUT_OF_MEMORY, STR_CONFIG_ERROR_SPRITECACHE_TOO_BIG);
 977                         msg.SetDParam(0, target_size);
 978                         msg.SetDParam(1, _allocated_sprite_cache_size);
 979                         ScheduleErrorMessage(msg);
 980                 }
 981         }
 982
 983         /* A big free block */
 984         _spritecache_ptr->size = (_allocated_sprite_cache_size - sizeof(MemBlock)) | S_FREE_MASK;
 985         /* Sentinel block (identified by size == 0) */
 986         NextBlock(_spritecache_ptr)->size = 0;
 987 }
 988
 989 void GfxInitSpriteMem()
 990 {
 991         GfxInitSpriteCache();
 992
 993         /* Reset the spritecache 'pool' */
 994         free(_spritecache);
 995         _spritecache_items = 0;
 996         _spritecache = nullptr;
 997
 998         _compact_cache_counter = 0;
 999         _sprite_files.clear();
1000 }
1001
1002 /**
1003  * Remove all encoded sprites from the sprite cache without
1004  * discarding sprite location information.
1005  */
1006 void GfxClearSpriteCache()
1007 {
1008         /* Clear sprite ptr for all cached items */
1009         for (uint i = 0; i != _spritecache_items; i++) {
1010                 SpriteCache *sc = GetSpriteCache(i);
1011                 if (sc->type != ST_RECOLOUR && sc->ptr != nullptr) DeleteEntryFromSpriteCache(i);
1012         }
1013
1014         VideoDriver::GetInstance()->ClearSystemSprites();
1015 }
1016
1017 /* static */ ReusableBuffer<SpriteLoader::CommonPixel> SpriteLoader::Sprite::buffer[ZOOM_LVL_COUNT];