# spritecache.cpp

Go to the documentation of this file.

    00001 /* $Id: spritecache.cpp 16273 2009-05-10 21:33:55Z rubidium $ */
    00002
    00005 #include "stdafx.h"
    00006 #include "gfx_type.h"
    00007 #include "fileio_func.h"
    00008 #include "spriteloader/grf.hpp"
    00009 #include "core/alloc_func.hpp"
    00010 #include "gfx_func.h"
    00011 #ifdef WITH_PNG
    00012 #include "spriteloader/png.hpp"
    00013 #endif /* WITH_PNG */
    00014 #include "blitter/factory.hpp"
    00015 #include "core/math_func.hpp"
    00016
    00017 #include "table/sprites.h"
    00018
    00019 /* Default of 4MB spritecache */
    00020 uint _sprite_cache_size = 4;
    00021
    00022 typedef SimpleTinyEnumT<SpriteType, byte> SpriteTypeByte;
    00023
    00024 struct SpriteCache {
    00025   void *ptr;
    00026   size_t file_pos;
    00027   uint32 id;
    00028   uint16 file_slot;
    00029   int16 lru;
    00030   SpriteTypeByte type;
    00031   bool warned;
    00032 };
    00033
    00034
    00035 static uint _spritecache_items = 0;
    00036 static SpriteCache *_spritecache = NULL;
    00037
    00038
    00039 static inline SpriteCache *GetSpriteCache(uint index)
    00040 {
    00041   return &_spritecache[index];
    00042 }
    00043
    00044 static inline bool IsMapgenSpriteID(SpriteID sprite)
    00045 {
    00046   return IsInsideMM(sprite, 4845, 4882);
    00047 }
    00048
    00049 static SpriteCache *AllocateSpriteCache(uint index)
    00050 {
    00051   if (index >= _spritecache_items) {
    00052     /* Add another 1024 items to the 'pool' */
    00053     uint items = Align(index + 1, 1024);
    00054
    00055     DEBUG(sprite, 4, "Increasing sprite cache to %u items (" PRINTF_SIZE " bytes)", items, items * sizeof(*_spritecache));
    00056
    00057     _spritecache = ReallocT(_spritecache, items);
    00058
    00059     /* Reset the new items and update the count */
    00060     memset(_spritecache + _spritecache_items, 0, (items - _spritecache_items) * sizeof(*_spritecache));
    00061     _spritecache_items = items;
    00062   }
    00063
    00064   return GetSpriteCache(index);
    00065 }
    00066
    00067
    00068 struct MemBlock {
    00069   size_t size;
    00070   byte data[VARARRAY_SIZE];
    00071 };
    00072
    00073 static uint _sprite_lru_counter;
    00074 static MemBlock *_spritecache_ptr;
    00075 static int _compact_cache_counter;
    00076
    00077 static void CompactSpriteCache();
    00078
    00085 bool SkipSpriteData(byte type, uint16 num)
    00086 {
    00087   if (type & 2) {
    00088     FioSkipBytes(num);
    00089   } else {
    00090     while (num > 0) {
    00091       int8 i = FioReadByte();
    00092       if (i >= 0) {
    00093         int size = (i == 0) ? 0x80 : i;
    00094         if (size > num) return false;
    00095         num -= size;
    00096         FioSkipBytes(size);
    00097       } else {
    00098         i = -(i >> 3);
    00099         num -= i;
    00100         FioReadByte();
    00101       }
    00102     }
    00103   }
    00104   return true;
    00105 }
    00106
    00111 static SpriteType ReadSpriteHeaderSkipData()
    00112 {
    00113   uint16 num = FioReadWord();
    00114
    00115   if (num == 0) return ST_INVALID;
    00116
    00117   byte type = FioReadByte();
    00118   if (type == 0xFF) {
    00119     FioSkipBytes(num);
    00120     /* Some NewGRF files have "empty" pseudo-sprites which are 1
    00121      * byte long. Catch these so the sprites won't be displayed. */
    00122     return (num == 1) ? ST_INVALID : ST_RECOLOUR;
    00123   }
    00124
    00125   FioSkipBytes(7);
    00126   return SkipSpriteData(type, num - 8) ? ST_NORMAL : ST_INVALID;
    00127 }
    00128
    00129 /* Check if the given Sprite ID exists */
    00130 bool SpriteExists(SpriteID id)
    00131 {
    00132   /* Special case for Sprite ID zero -- its position is also 0... */
    00133   if (id == 0) return true;
    00134   if (id >= _spritecache_items) return false;
    00135   return !(GetSpriteCache(id)->file_pos == 0 && GetSpriteCache(id)->file_slot == 0);
    00136 }
    00137
    00138 void *AllocSprite(size_t);
    00139
    00140 static void *ReadSprite(SpriteCache *sc, SpriteID id, SpriteType sprite_type)
    00141 {
    00142   uint8 file_slot = sc->file_slot;
    00143   size_t file_pos = sc->file_pos;
    00144
    00145   assert(IsMapgenSpriteID(id) == (sprite_type == ST_MAPGEN));
    00146   assert(sc->type == sprite_type);
    00147
    00148   DEBUG(sprite, 9, "Load sprite %d", id);
    00149
    00150   if (sprite_type == ST_NORMAL && BlitterFactoryBase::GetCurrentBlitter()->GetScreenDepth() == 32) {
    00151 #ifdef WITH_PNG
    00152     /* Try loading 32bpp graphics in case we are 32bpp output */
    00153     SpriteLoaderPNG sprite_loader;
    00154     SpriteLoader::Sprite sprite;
    00155
    00156     if (sprite_loader.LoadSprite(&sprite, file_slot, sc->id, sprite_type)) {
    00157       sc->ptr = BlitterFactoryBase::GetCurrentBlitter()->Encode(&sprite, &AllocSprite);
    00158
    00159       return sc->ptr;
    00160     }
    00161     /* If the PNG couldn't be loaded, fall back to 8bpp grfs */
    00162 #else
    00163     static bool show_once = true;
    00164     if (show_once) {
    00165       DEBUG(misc, 0, "You are running a 32bpp blitter, but this build is without libpng support; falling back to 8bpp graphics");
    00166       show_once = false;
    00167     }
    00168 #endif /* WITH_PNG */
    00169   }
    00170
    00171   FioSeekToFile(file_slot, file_pos);
    00172
    00173   /* Read the size and type */
    00174   int num  = FioReadWord();
    00175   byte type = FioReadByte();
    00176
    00177   /* Type 0xFF indicates either a colourmap or some other non-sprite info */
    00178   assert((type == 0xFF) == (sprite_type == ST_RECOLOUR));
    00179   if (type == 0xFF) {
    00180     /* "Normal" recolour sprites are ALWAYS 257 bytes. Then there is a small
    00181      * number of recolour sprites that are 17 bytes that only exist in DOS
    00182      * GRFs which are the same as 257 byte recolour sprites, but with the last
    00183      * 240 bytes zeroed.  */
    00184     static const int RECOLOUR_SPRITE_SIZE = 257;
    00185     byte *dest = (byte *)AllocSprite(max(RECOLOUR_SPRITE_SIZE, num));
    00186
    00187     sc->ptr = dest;
    00188
    00189     if (_palette_remap_grf[sc->file_slot]) {
    00190       byte *dest_tmp = AllocaM(byte, max(RECOLOUR_SPRITE_SIZE, num));
    00191
    00192       /* Only a few recolour sprites are less than 257 bytes */
    00193       if (num < RECOLOUR_SPRITE_SIZE) memset(dest_tmp, 0, RECOLOUR_SPRITE_SIZE);
    00194       FioReadBlock(dest_tmp, num);
    00195
    00196       /* The data of index 0 is never used; "literal 00" according to the (New)GRF specs. */
    00197       for (int i = 1; i < RECOLOUR_SPRITE_SIZE; i++) {
    00198         dest[i] = _palette_remap[dest_tmp[_palette_reverse_remap[i - 1] + 1]];
    00199       }
    00200     } else {
    00201       FioReadBlock(dest, num);
    00202     }
    00203
    00204     return sc->ptr;
    00205   }
    00206
    00207   /* Ugly hack to work around the problem that the old landscape
    00208    *  generator assumes that those sprites are stored uncompressed in
    00209    *  the memory, and they are only read directly by the code, never
    00210    *  send to the blitter. So do not send it to the blitter (which will
    00211    *  result in a data array in the format the blitter likes most), but
    00212    *  read the data directly from disk and store that as sprite.
    00213    * Ugly: yes. Other solution: no. Blame the original author or
    00214    *  something ;) The image should really have been a data-stream
    00215    *  (so type = 0xFF basicly). */
    00216   if (sprite_type == ST_MAPGEN) {
    00217     uint height = FioReadByte();
    00218     uint width  = FioReadWord();
    00219     Sprite *sprite;
    00220     byte *dest;
    00221
    00222     num = width * height;
    00223     sprite = (Sprite *)AllocSprite(sizeof(*sprite) + num);
    00224     sc->ptr = sprite;
    00225     sprite->height = height;
    00226     sprite->width  = width;
    00227     sprite->x_offs = FioReadWord();
    00228     sprite->y_offs = FioReadWord();
    00229
    00230     dest = sprite->data;
    00231     while (num > 0) {
    00232       int8 i = FioReadByte();
    00233       if (i >= 0) {
    00234         num -= i;
    00235         for (; i > 0; --i) *dest++ = FioReadByte();
    00236       } else {
    00237         const byte *rel = dest - (((i & 7) << 8) | FioReadByte());
    00238         i = -(i >> 3);
    00239         num -= i;
    00240         for (; i > 0; --i) *dest++ = *rel++;
    00241       }
    00242     }
    00243
    00244     sc->type = sprite_type;
    00245
    00246     return sc->ptr;
    00247   }
    00248
    00249   assert(sprite_type == ST_NORMAL || sprite_type == ST_FONT);
    00250
    00251   SpriteLoaderGrf sprite_loader;
    00252   SpriteLoader::Sprite sprite;
    00253
    00254   if (!sprite_loader.LoadSprite(&sprite, file_slot, file_pos, sprite_type)) {
    00255     if (id == SPR_IMG_QUERY) usererror("Okay... something went horribly wrong. I couldn't load the fallback sprite. What should I do?");
    00256     return (void*)GetRawSprite(SPR_IMG_QUERY, ST_NORMAL);
    00257   }
    00258   sc->ptr = BlitterFactoryBase::GetCurrentBlitter()->Encode(&sprite, &AllocSprite);
    00259
    00260   return sc->ptr;
    00261 }
    00262
    00263
    00264 bool LoadNextSprite(int load_index, byte file_slot, uint file_sprite_id)
    00265 {
    00266   size_t file_pos = FioGetPos();
    00267
    00268   SpriteType type = ReadSpriteHeaderSkipData();
    00269
    00270   if (type == ST_INVALID) return false;
    00271
    00272   if (load_index >= MAX_SPRITES) {
    00273     usererror("Tried to load too many sprites (#%d; max %d)", load_index, MAX_SPRITES);
    00274   }
    00275
    00276   bool is_mapgen = IsMapgenSpriteID(load_index);
    00277
    00278   if (is_mapgen) {
    00279     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?");
    00280     type = ST_MAPGEN;
    00281   }
    00282
    00283   SpriteCache *sc = AllocateSpriteCache(load_index);
    00284   sc->file_slot = file_slot;
    00285   sc->file_pos = file_pos;
    00286   sc->ptr = NULL;
    00287   sc->lru = 0;
    00288   sc->id = file_sprite_id;
    00289   sc->type = type;
    00290   sc->warned = false;
    00291
    00292   return true;
    00293 }
    00294
    00295
    00296 void DupSprite(SpriteID old_spr, SpriteID new_spr)
    00297 {
    00298   SpriteCache *scnew = AllocateSpriteCache(new_spr); // may reallocate: so put it first
    00299   SpriteCache *scold = GetSpriteCache(old_spr);
    00300
    00301   scnew->file_slot = scold->file_slot;
    00302   scnew->file_pos = scold->file_pos;
    00303   scnew->ptr = NULL;
    00304   scnew->id = scold->id;
    00305   scnew->type = scold->type;
    00306   scnew->warned = false;
    00307 }
    00308
    00309
    00310 #define S_FREE_MASK 1
    00311
    00312 static inline MemBlock *NextBlock(MemBlock *block)
    00313 {
    00314   return (MemBlock*)((byte*)block + (block->size & ~S_FREE_MASK));
    00315 }
    00316
    00317 static size_t GetSpriteCacheUsage()
    00318 {
    00319   size_t tot_size = 0;
    00320   MemBlock *s;
    00321
    00322   for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
    00323     if (!(s->size & S_FREE_MASK)) tot_size += s->size;
    00324   }
    00325
    00326   return tot_size;
    00327 }
    00328
    00329
    00330 void IncreaseSpriteLRU()
    00331 {
    00332   /* Increase all LRU values */
    00333   if (_sprite_lru_counter > 16384) {
    00334     SpriteID i;
    00335
    00336     DEBUG(sprite, 3, "Fixing lru %u, inuse=" PRINTF_SIZE, _sprite_lru_counter, GetSpriteCacheUsage());
    00337
    00338     for (i = 0; i != _spritecache_items; i++) {
    00339       SpriteCache *sc = GetSpriteCache(i);
    00340       if (sc->ptr != NULL) {
    00341         if (sc->lru >= 0) {
    00342           sc->lru = -1;
    00343         } else if (sc->lru != -32768) {
    00344           sc->lru--;
    00345         }
    00346       }
    00347     }
    00348     _sprite_lru_counter = 0;
    00349   }
    00350
    00351   /* Compact sprite cache every now and then. */
    00352   if (++_compact_cache_counter >= 740) {
    00353     CompactSpriteCache();
    00354     _compact_cache_counter = 0;
    00355   }
    00356 }
    00357
    00360 static void CompactSpriteCache()
    00361 {
    00362   MemBlock *s;
    00363
    00364   DEBUG(sprite, 3, "Compacting sprite cache, inuse=" PRINTF_SIZE, GetSpriteCacheUsage());
    00365
    00366   for (s = _spritecache_ptr; s->size != 0;) {
    00367     if (s->size & S_FREE_MASK) {
    00368       MemBlock *next = NextBlock(s);
    00369       MemBlock temp;
    00370       SpriteID i;
    00371
    00372       /* Since free blocks are automatically coalesced, this should hold true. */
    00373       assert(!(next->size & S_FREE_MASK));
    00374
    00375       /* If the next block is the sentinel block, we can safely return */
    00376       if (next->size == 0) break;
    00377
    00378       /* Locate the sprite belonging to the next pointer. */
    00379       for (i = 0; GetSpriteCache(i)->ptr != next->data; i++) {
    00380         assert(i != _spritecache_items);
    00381       }
    00382
    00383       GetSpriteCache(i)->ptr = s->data; // Adjust sprite array entry
    00384       /* Swap this and the next block */
    00385       temp = *s;
    00386       memmove(s, next, next->size);
    00387       s = NextBlock(s);
    00388       *s = temp;
    00389
    00390       /* Coalesce free blocks */
    00391       while (NextBlock(s)->size & S_FREE_MASK) {
    00392         s->size += NextBlock(s)->size & ~S_FREE_MASK;
    00393       }
    00394     } else {
    00395       s = NextBlock(s);
    00396     }
    00397   }
    00398 }
    00399
    00400 static void DeleteEntryFromSpriteCache()
    00401 {
    00402   SpriteID i;
    00403   uint best = UINT_MAX;
    00404   MemBlock *s;
    00405   int cur_lru;
    00406
    00407   DEBUG(sprite, 3, "DeleteEntryFromSpriteCache, inuse=" PRINTF_SIZE, GetSpriteCacheUsage());
    00408
    00409   cur_lru = 0xffff;
    00410   for (i = 0; i != _spritecache_items; i++) {
    00411     SpriteCache *sc = GetSpriteCache(i);
    00412     if (sc->ptr != NULL && sc->lru < cur_lru) {
    00413       cur_lru = sc->lru;
    00414       best = i;
    00415     }
    00416   }
    00417
    00418   /* Display an error message and die, in case we found no sprite at all.
    00419    * This shouldn't really happen, unless all sprites are locked. */
    00420   if (best == UINT_MAX) error("Out of sprite memory");
    00421
    00422   /* Mark the block as free (the block must be in use) */
    00423   s = (MemBlock*)GetSpriteCache(best)->ptr - 1;
    00424   assert(!(s->size & S_FREE_MASK));
    00425   s->size |= S_FREE_MASK;
    00426   GetSpriteCache(best)->ptr = NULL;
    00427
    00428   /* And coalesce adjacent free blocks */
    00429   for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
    00430     if (s->size & S_FREE_MASK) {
    00431       while (NextBlock(s)->size & S_FREE_MASK) {
    00432         s->size += NextBlock(s)->size & ~S_FREE_MASK;
    00433       }
    00434     }
    00435   }
    00436 }
    00437
    00438 void *AllocSprite(size_t mem_req)
    00439 {
    00440   mem_req += sizeof(MemBlock);
    00441
    00442   /* Align this to an uint32 boundary. This also makes sure that the 2 least
    00443    * bits are not used, so we could use those for other things. */
    00444   mem_req = Align(mem_req, sizeof(uint32));
    00445
    00446   for (;;) {
    00447     MemBlock *s;
    00448
    00449     for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
    00450       if (s->size & S_FREE_MASK) {
    00451         size_t cur_size = s->size & ~S_FREE_MASK;
    00452
    00453         /* Is the block exactly the size we need or
    00454          * big enough for an additional free block? */
    00455         if (cur_size == mem_req ||
    00456             cur_size >= mem_req + sizeof(MemBlock)) {
    00457           /* Set size and in use */
    00458           s->size = mem_req;
    00459
    00460           /* Do we need to inject a free block too? */
    00461           if (cur_size != mem_req) {
    00462             NextBlock(s)->size = (cur_size - mem_req) | S_FREE_MASK;
    00463           }
    00464
    00465           return s->data;
    00466         }
    00467       }
    00468     }
    00469
    00470     /* Reached sentinel, but no block found yet. Delete some old entry. */
    00471     DeleteEntryFromSpriteCache();
    00472   }
    00473 }
    00474
    00482 static const void *HandleInvalidSpriteRequest(SpriteID sprite, SpriteType requested, SpriteCache *sc)
    00483 {
    00484   static const char *sprite_types[] = {
    00485     "normal",        // ST_NORMAL
    00486     "map generator", // ST_MAPGEN
    00487     "character",     // ST_FONT
    00488     "recolour",      // ST_RECOLOUR
    00489   };
    00490
    00491   SpriteType available = sc->type;
    00492   if (requested == ST_FONT && available == ST_NORMAL) {
    00493     if (sc->ptr == NULL) sc->type = ST_FONT;
    00494     return GetRawSprite(sprite, sc->type);
    00495   }
    00496
    00497   byte warning_level = sc->warned ? 6 : 0;
    00498   sc->warned = true;
    00499   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]);
    00500
    00501   switch (requested) {
    00502     case ST_NORMAL:
    00503       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?");
    00504       /* FALLTHROUGH */
    00505     case ST_FONT:
    00506       return GetRawSprite(SPR_IMG_QUERY, ST_NORMAL);
    00507     case ST_RECOLOUR:
    00508       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?");
    00509       return GetRawSprite(PALETTE_TO_DARK_BLUE, ST_RECOLOUR);
    00510     case ST_MAPGEN:
    00511       /* this shouldn't happen, overriding of ST_MAPGEN sprites is checked in LoadNextSprite()
    00512        * (the only case the check fails is when these sprites weren't even loaded...) */
    00513     default:
    00514       NOT_REACHED();
    00515   }
    00516 }
    00517
    00518 const void *GetRawSprite(SpriteID sprite, SpriteType type)
    00519 {
    00520   assert(IsMapgenSpriteID(sprite) == (type == ST_MAPGEN));
    00521   assert(type < ST_INVALID);
    00522
    00523   if (!SpriteExists(sprite)) {
    00524     DEBUG(sprite, 1, "Tried to load non-existing sprite #%d. Probable cause: Wrong/missing NewGRFs", sprite);
    00525
    00526     /* SPR_IMG_QUERY is a BIG FAT RED ? */
    00527     sprite = SPR_IMG_QUERY;
    00528   }
    00529
    00530   SpriteCache *sc = GetSpriteCache(sprite);
    00531
    00532   if (sc->type != type) return HandleInvalidSpriteRequest(sprite, type, sc);
    00533
    00534   /* Update LRU */
    00535   sc->lru = ++_sprite_lru_counter;
    00536
    00537   void *p = sc->ptr;
    00538
    00539   /* Load the sprite, if it is not loaded, yet */
    00540   if (p == NULL) p = ReadSprite(sc, sprite, type);
    00541
    00542   return p;
    00543 }
    00544
    00545
    00546 void GfxInitSpriteMem()
    00547 {
    00548   /* initialize sprite cache heap */
    00549   if (_spritecache_ptr == NULL) _spritecache_ptr = (MemBlock*)MallocT<byte>(_sprite_cache_size * 1024 * 1024);
    00550
    00551   /* A big free block */
    00552   _spritecache_ptr->size = ((_sprite_cache_size * 1024 * 1024) - sizeof(MemBlock)) | S_FREE_MASK;
    00553   /* Sentinel block (identified by size == 0) */
    00554   NextBlock(_spritecache_ptr)->size = 0;
    00555
    00556   /* Reset the spritecache 'pool' */
    00557   free(_spritecache);
    00558   _spritecache_items = 0;
    00559   _spritecache = NULL;
    00560
    00561   _compact_cache_counter = 0;
    00562 }
    00563
    00564 /* static */ ReusableBuffer<SpriteLoader::CommonPixel> SpriteLoader::Sprite::buffer;