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