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