src/spritecache.cpp

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