tron@2186: /* $Id$ */
tron@2186: 
rubidium@9111: /** @file spritecache.cpp Caching of sprites. */
belugas@6420: 
truelight@0: #include "stdafx.h"
Darkvater@1891: #include "openttd.h"
truelight@6896: #include "variables.h"
tron@1299: #include "debug.h"
tron@1349: #include "spritecache.h"
truelight@0: #include "fileio.h"
truelight@6852: #include "spriteloader/grf.hpp"
rubidium@8130: #include "core/alloc_func.hpp"
rubidium@8131: #include "core/math_func.hpp"
truelight@6901: #ifdef WITH_PNG
truelight@6896: #include "spriteloader/png.hpp"
truelight@6901: #endif /* WITH_PNG */
truelight@6937: #include "blitter/factory.hpp"
peter1138@6803: 
rubidium@8264: #include "table/sprites.h"
rubidium@8264: 
truelight@6852: /* Default of 4MB spritecache */
truelight@6852: uint _sprite_cache_size = 4;
truelight@0: 
truelight@0: 
rubidium@6248: struct SpriteCache {
peter1138@8741: 	void *ptr;
truelight@6896: 	uint32 id;
peter1138@8741: 	uint32 file_pos;
rubidium@8373: 	uint16 file_slot;
peter1138@8741: 	int16 lru;
rubidium@6248: };
peter1138@5504: 
peter1138@5504: 
peter1138@5504: static uint _spritecache_items = 0;
peter1138@5504: static SpriteCache *_spritecache = NULL;
peter1138@5504: 
peter1138@5504: 
peter1138@5504: static inline SpriteCache *GetSpriteCache(uint index)
peter1138@5504: {
peter1138@5504: 	return &_spritecache[index];
peter1138@5504: }
peter1138@5504: 
peter1138@5504: 
peter1138@5504: static SpriteCache *AllocateSpriteCache(uint index)
peter1138@5504: {
peter1138@5504: 	if (index >= _spritecache_items) {
peter1138@5504: 		/* Add another 1024 items to the 'pool' */
skidd13@7927: 		uint items = Align(index + 1, 1024);
peter1138@5504: 
peter1138@5504: 		DEBUG(sprite, 4, "Increasing sprite cache to %d items (%d bytes)", items, items * sizeof(*_spritecache));
peter1138@5504: 
KUDr@5609: 		_spritecache = ReallocT(_spritecache, items);
peter1138@5504: 
peter1138@5504: 		/* Reset the new items and update the count */
peter1138@5504: 		memset(_spritecache + _spritecache_items, 0, (items - _spritecache_items) * sizeof(*_spritecache));
peter1138@5504: 		_spritecache_items = items;
peter1138@5504: 	}
peter1138@5504: 
peter1138@5504: 	return GetSpriteCache(index);
peter1138@5504: }
peter1138@5504: 
truelight@0: 
rubidium@6248: struct MemBlock {
glx@9146: 	size_t size;
tron@1353: 	byte data[VARARRAY_SIZE];
rubidium@6248: };
tron@1353: 
truelight@0: static uint _sprite_lru_counter;
tron@1353: static MemBlock *_spritecache_ptr;
truelight@0: static int _compact_cache_counter;
truelight@0: 
rubidium@6247: static void CompactSpriteCache();
truelight@0: 
rubidium@6247: static bool ReadSpriteHeaderSkipData()
truelight@0: {
tron@2329: 	uint16 num = FioReadWord();
truelight@0: 	byte type;
truelight@0: 
tron@2329: 	if (num == 0) return false;
tron@2329: 
truelight@0: 	type = FioReadByte();
truelight@0: 	if (type == 0xFF) {
tron@2342: 		FioSkipBytes(num);
peter1138@5150: 		/* Some NewGRF files have "empty" pseudo-sprites which are 1
peter1138@5150: 		 * byte long. Catch these so the sprites won't be displayed. */
peter1138@5150: 		return num != 1;
truelight@0: 	}
truelight@184: 
truelight@0: 	FioSkipBytes(7);
truelight@0: 	num -= 8;
tron@2329: 	if (num == 0) return true;
truelight@0: 
truelight@0: 	if (type & 2) {
truelight@0: 		FioSkipBytes(num);
tron@1355: 	} else {
tron@1355: 		while (num > 0) {
tron@1355: 			int8 i = FioReadByte();
tron@1355: 			if (i >= 0) {
tron@1355: 				num -= i;
tron@1355: 				FioSkipBytes(i);
tron@1355: 			} else {
tron@1355: 				i = -(i >> 3);
tron@1355: 				num -= i;
tron@1355: 				FioReadByte();
tron@1355: 			}
truelight@0: 		}
truelight@0: 	}
tron@2329: 
tron@2329: 	return true;
truelight@0: }
truelight@0: 
peter1138@3565: /* Check if the given Sprite ID exists */
peter1138@3565: bool SpriteExists(SpriteID id)
peter1138@3565: {
peter1138@3565: 	/* Special case for Sprite ID zero -- its position is also 0... */
peter1138@5504: 	if (id == 0) return true;
peter1138@5702: 	if (id >= _spritecache_items) return false;
truelight@7576: 	return !(GetSpriteCache(id)->file_pos == 0 && GetSpriteCache(id)->file_slot == 0);
peter1138@3565: }
peter1138@3565: 
truelight@6852: void* AllocSprite(size_t);
tron@2014: 
rubidium@6869: static void* ReadSprite(SpriteCache *sc, SpriteID id, bool real_sprite)
truelight@0: {
truelight@7570: 	uint8 file_slot = sc->file_slot;
peter1138@6799: 	uint32 file_pos = sc->file_pos;
tron@2014: 
Darkvater@5380: 	DEBUG(sprite, 9, "Load sprite %d", id);
truelight@184: 
peter1138@3565: 	if (!SpriteExists(id)) {
rubidium@5962: 		DEBUG(sprite, 1, "Tried to load non-existing sprite #%d. Probable cause: Wrong/missing NewGRFs", id);
rubidium@5962: 
rubidium@5962: 		/* SPR_IMG_QUERY is a BIG FAT RED ? */
rubidium@5962: 		id = SPR_IMG_QUERY;
truelight@7570: 		file_slot = GetSpriteCache(SPR_IMG_QUERY)->file_slot;
truelight@7570: 		file_pos  = GetSpriteCache(SPR_IMG_QUERY)->file_pos;
tron@1378: 	}
tron@1378: 
truelight@6903: 	if (BlitterFactoryBase::GetCurrentBlitter()->GetScreenDepth() == 32) {
truelight@6901: #ifdef WITH_PNG
truelight@6896: 		/* Try loading 32bpp graphics in case we are 32bpp output */
truelight@6896: 		SpriteLoaderPNG sprite_loader;
truelight@6896: 		SpriteLoader::Sprite sprite;
truelight@6896: 
peter1138@8374: 		if (sprite_loader.LoadSprite(&sprite, file_slot, sc->id)) {
truelight@6896: 			sc->ptr = BlitterFactoryBase::GetCurrentBlitter()->Encode(&sprite, &AllocSprite);
truelight@6896: 			free(sprite.data);
truelight@6896: 
truelight@6896: 			return sc->ptr;
truelight@6896: 		}
truelight@6896: 		/* If the PNG couldn't be loaded, fall back to 8bpp grfs */
truelight@6903: #else
truelight@6903: 		static bool show_once = true;
truelight@6903: 		if (show_once) {
truelight@6903: 			DEBUG(misc, 0, "You are running a 32bpp blitter, but this build is without libpng support; falling back to 8bpp graphics");
truelight@6903: 			show_once = false;
truelight@6903: 		}
truelight@6903: #endif /* WITH_PNG */
truelight@6896: 	}
truelight@6896: 
truelight@7570: 	FioSeekToFile(file_slot, file_pos);
tron@1354: 
truelight@6852: 	/* Read the size and type */
truelight@6852: 	int num  = FioReadWord();
truelight@6852: 	byte type = FioReadByte();
truelight@6852: 	/* Type 0xFF indicates either a colormap or some other non-sprite info */
tron@2014: 	if (type == 0xFF) {
rubidium@6869: 		if (real_sprite) {
rubidium@6869: 			static byte warning_level = 0;
rubidium@6869: 			DEBUG(sprite, warning_level, "Tried to load non sprite #%d as a real sprite. Probable cause: NewGRF interference", id);
rubidium@6869: 			warning_level = 6;
rubidium@6869: 			if (id == SPR_IMG_QUERY) error("Uhm, would you be so kind not to load a NewGRF that makes the 'query' sprite a non- sprite?");
rubidium@6869: 			return (void*)GetSprite(SPR_IMG_QUERY);
rubidium@6869: 		}
rubidium@6869: 
truelight@6852: 		byte *dest = (byte *)AllocSprite(num);
tron@2014: 
peter1138@5504: 		sc->ptr = dest;
tron@2014: 		FioReadBlock(dest, num);
tron@2014: 
truelight@6865: 		return sc->ptr;
truelight@6865: 	}
truelight@6865: 	/* Ugly hack to work around the problem that the old landscape
truelight@6865: 	 *  generator assumes that those sprites are stored uncompressed in
truelight@6865: 	 *  the memory, and they are only read directly by the code, never
truelight@6865: 	 *  send to the blitter. So do not send it to the blitter (which will
truelight@6865: 	 *  result in a data array in the format the blitter likes most), but
truelight@6865: 	 *  read the data directly from disk and store that as sprite.
truelight@6865: 	 * Ugly: yes. Other solution: no. Blame the original author or
truelight@6865: 	 *  something ;) The image should really have been a data-stream
truelight@6865: 	 *  (so type = 0xFF basicly). */
truelight@6865: 	if (id >= 4845 && id <= 4881) {
truelight@6865: 		uint height = FioReadByte();
truelight@6865: 		uint width  = FioReadWord();
truelight@6865: 		Sprite *sprite;
truelight@6865: 		byte *dest;
truelight@6865: 
truelight@6865: 		num = width * height;
truelight@6865: 		sprite = (Sprite *)AllocSprite(sizeof(*sprite) + num);
truelight@6865: 		sc->ptr = sprite;
truelight@6865: 		sprite->height = height;
truelight@6865: 		sprite->width  = width;
truelight@6865: 		sprite->x_offs = FioReadWord();
truelight@6865: 		sprite->y_offs = FioReadWord();
truelight@6865: 
truelight@6865: 		dest = sprite->data;
truelight@6865: 		while (num > 0) {
truelight@6865: 			int8 i = FioReadByte();
truelight@6865: 			if (i >= 0) {
truelight@6865: 				num -= i;
truelight@6865: 				for (; i > 0; --i) *dest++ = FioReadByte();
truelight@6865: 			} else {
truelight@6865: 				const byte* rel = dest - (((i & 7) << 8) | FioReadByte());
truelight@6865: 				i = -(i >> 3);
truelight@6865: 				num -= i;
truelight@6865: 				for (; i > 0; --i) *dest++ = *rel++;
truelight@6865: 			}
truelight@6865: 		}
truelight@6865: 
truelight@6865: 		return sc->ptr;
truelight@6852: 	}
tron@2014: 
rubidium@6869: 	if (!real_sprite) {
rubidium@6869: 		static byte warning_level = 0;
rubidium@6869: 		DEBUG(sprite, warning_level, "Tried to load real sprite #%d as a non sprite. Probable cause: NewGRF interference", id);
rubidium@6869: 		warning_level = 6;
rubidium@6869: 	}
rubidium@6869: 
truelight@6852: 	SpriteLoaderGrf sprite_loader;
truelight@6852: 	SpriteLoader::Sprite sprite;
truelight@0: 
peter1138@8374: 	if (!sprite_loader.LoadSprite(&sprite, file_slot, file_pos)) return NULL;
truelight@6852: 	if (id == 142) sprite.height = 10; // Compensate for a TTD bug
truelight@6856: 	sc->ptr = BlitterFactoryBase::GetCurrentBlitter()->Encode(&sprite, &AllocSprite);
truelight@6852: 	free(sprite.data);
truelight@184: 
truelight@6852: 	return sc->ptr;
truelight@0: }
truelight@0: 
truelight@0: 
truelight@7570: bool LoadNextSprite(int load_index, byte file_slot, uint file_sprite_id)
truelight@0: {
peter1138@5504: 	SpriteCache *sc;
truelight@7570: 	uint32 file_pos = FioGetPos();
truelight@0: 
tron@2342: 	if (!ReadSpriteHeaderSkipData()) return false;
darkvater@361: 
peter1138@3591: 	if (load_index >= MAX_SPRITES) {
peter1138@3591: 		error("Tried to load too many sprites (#%d; max %d)", load_index, MAX_SPRITES);
peter1138@3591: 	}
peter1138@3591: 
peter1138@5504: 	sc = AllocateSpriteCache(load_index);
truelight@7570: 	sc->file_slot = file_slot;
peter1138@5504: 	sc->file_pos = file_pos;
peter1138@5504: 	sc->ptr = NULL;
peter1138@5504: 	sc->lru = 0;
truelight@6908: 	sc->id = file_sprite_id;
truelight@6896: 
truelight@0: 	return true;
truelight@0: }
truelight@0: 
tron@2407: 
rubidium@5587: void DupSprite(SpriteID old_spr, SpriteID new_spr)
tron@2407: {
rubidium@8435: 	SpriteCache *scnew = AllocateSpriteCache(new_spr); // may reallocate: so put it first
rubidium@5587: 	SpriteCache *scold = GetSpriteCache(old_spr);
peter1138@5504: 
truelight@7570: 	scnew->file_slot = scold->file_slot;
peter1138@5504: 	scnew->file_pos = scold->file_pos;
peter1138@5504: 	scnew->ptr = NULL;
truelight@6896: 	scnew->id = scold->id;
tron@2407: }
tron@2407: 
tron@2407: 
truelight@0: #define S_FREE_MASK 1
tron@1353: 
tron@1353: static inline MemBlock* NextBlock(MemBlock* block)
tron@1353: {
tron@1353: 	return (MemBlock*)((byte*)block + (block->size & ~S_FREE_MASK));
tron@1353: }
truelight@0: 
rubidium@6247: static uint32 GetSpriteCacheUsage()
truelight@0: {
truelight@4321: 	uint32 tot_size = 0;
tron@1353: 	MemBlock* s;
tron@1353: 
belugas@8562: 	for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
tron@1353: 		if (!(s->size & S_FREE_MASK)) tot_size += s->size;
belugas@8562: 	}
truelight@0: 
truelight@0: 	return tot_size;
truelight@0: }
truelight@0: 
truelight@0: 
rubidium@6247: void IncreaseSpriteLRU()
truelight@0: {
belugas@6420: 	/* Increase all LRU values */
truelight@0: 	if (_sprite_lru_counter > 16384) {
peter1138@5504: 		SpriteID i;
peter1138@5504: 
Darkvater@5380: 		DEBUG(sprite, 3, "Fixing lru %d, inuse=%d", _sprite_lru_counter, GetSpriteCacheUsage());
truelight@0: 
peter1138@5504: 		for (i = 0; i != _spritecache_items; i++) {
peter1138@5504: 			SpriteCache *sc = GetSpriteCache(i);
peter1138@5504: 			if (sc->ptr != NULL) {
peter1138@5504: 				if (sc->lru >= 0) {
peter1138@5504: 					sc->lru = -1;
peter1138@5504: 				} else if (sc->lru != -32768) {
peter1138@5504: 					sc->lru--;
truelight@0: 				}
truelight@0: 			}
peter1138@5504: 		}
truelight@0: 		_sprite_lru_counter = 0;
truelight@0: 	}
truelight@0: 
belugas@6420: 	/* Compact sprite cache every now and then. */
truelight@0: 	if (++_compact_cache_counter >= 740) {
truelight@0: 		CompactSpriteCache();
truelight@0: 		_compact_cache_counter = 0;
truelight@0: 	}
truelight@0: }
truelight@0: 
belugas@6420: /** Called when holes in the sprite cache should be removed.
belugas@6420:  * That is accomplished by moving the cached data. */
rubidium@6247: static void CompactSpriteCache()
truelight@0: {
tron@1353: 	MemBlock *s;
truelight@184: 
Darkvater@5380: 	DEBUG(sprite, 3, "Compacting sprite cache, inuse=%d", GetSpriteCacheUsage());
truelight@184: 
tron@1353: 	for (s = _spritecache_ptr; s->size != 0;) {
tron@1353: 		if (s->size & S_FREE_MASK) {
tron@1353: 			MemBlock* next = NextBlock(s);
tron@1353: 			MemBlock temp;
peter1138@5504: 			SpriteID i;
tron@1353: 
belugas@6420: 			/* Since free blocks are automatically coalesced, this should hold true. */
tron@1353: 			assert(!(next->size & S_FREE_MASK));
truelight@184: 
belugas@6420: 			/* If the next block is the sentinel block, we can safely return */
peter1138@8741: 			if (next->size == 0) break;
truelight@0: 
belugas@6420: 			/* Locate the sprite belonging to the next pointer. */
peter1138@5504: 			for (i = 0; GetSpriteCache(i)->ptr != next->data; i++) {
peter1138@5504: 				assert(i != _spritecache_items);
tron@1353: 			}
truelight@0: 
peter1138@5504: 			GetSpriteCache(i)->ptr = s->data; // Adjust sprite array entry
belugas@6420: 			/* Swap this and the next block */
tron@1353: 			temp = *s;
tron@1353: 			memmove(s, next, next->size);
tron@1353: 			s = NextBlock(s);
tron@1353: 			*s = temp;
tron@1353: 
belugas@6420: 			/* Coalesce free blocks */
tron@1353: 			while (NextBlock(s)->size & S_FREE_MASK) {
tron@1353: 				s->size += NextBlock(s)->size & ~S_FREE_MASK;
truelight@0: 			}
tron@1353: 		} else {
tron@1353: 			s = NextBlock(s);
truelight@0: 		}
truelight@0: 	}
truelight@0: }
truelight@0: 
rubidium@6247: static void DeleteEntryFromSpriteCache()
truelight@0: {
peter1138@5504: 	SpriteID i;
rubidium@5587: 	uint best = UINT_MAX;
tron@1353: 	MemBlock* s;
truelight@0: 	int cur_lru;
truelight@0: 
Darkvater@5380: 	DEBUG(sprite, 3, "DeleteEntryFromSpriteCache, inuse=%d", GetSpriteCacheUsage());
truelight@0: 
truelight@0: 	cur_lru = 0xffff;
peter1138@5504: 	for (i = 0; i != _spritecache_items; i++) {
peter1138@5504: 		SpriteCache *sc = GetSpriteCache(i);
peter1138@5504: 		if (sc->ptr != NULL && sc->lru < cur_lru) {
peter1138@5504: 			cur_lru = sc->lru;
truelight@0: 			best = i;
truelight@0: 		}
truelight@0: 	}
truelight@0: 
belugas@6420: 	/* Display an error message and die, in case we found no sprite at all.
belugas@6420: 	 * This shouldn't really happen, unless all sprites are locked. */
glx@8040: 	if (best == (uint)-1) error("Out of sprite memory");
truelight@0: 
belugas@6420: 	/* Mark the block as free (the block must be in use) */
peter1138@5504: 	s = (MemBlock*)GetSpriteCache(best)->ptr - 1;
tron@1353: 	assert(!(s->size & S_FREE_MASK));
tron@1353: 	s->size |= S_FREE_MASK;
peter1138@5504: 	GetSpriteCache(best)->ptr = NULL;
truelight@0: 
belugas@6420: 	/* And coalesce adjacent free blocks */
tron@1353: 	for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
tron@1353: 		if (s->size & S_FREE_MASK) {
tron@1353: 			while (NextBlock(s)->size & S_FREE_MASK) {
tron@1353: 				s->size += NextBlock(s)->size & ~S_FREE_MASK;
truelight@0: 			}
truelight@0: 		}
truelight@0: 	}
truelight@0: }
truelight@0: 
truelight@6852: void* AllocSprite(size_t mem_req)
truelight@0: {
tron@2014: 	mem_req += sizeof(MemBlock);
truelight@0: 
tron@1353: 	/* Align this to an uint32 boundary. This also makes sure that the 2 least
tron@1353: 	 * bits are not used, so we could use those for other things. */
skidd13@7927: 	mem_req = Align(mem_req, sizeof(uint32));
truelight@0: 
tron@1353: 	for (;;) {
tron@1353: 		MemBlock* s;
truelight@0: 
tron@1353: 		for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
tron@1353: 			if (s->size & S_FREE_MASK) {
tron@1353: 				size_t cur_size = s->size & ~S_FREE_MASK;
truelight@0: 
tron@1353: 				/* Is the block exactly the size we need or
tron@1353: 				 * big enough for an additional free block? */
tron@1353: 				if (cur_size == mem_req ||
tron@1353: 						cur_size >= mem_req + sizeof(MemBlock)) {
belugas@6420: 					/* Set size and in use */
tron@1353: 					s->size = mem_req;
truelight@184: 
belugas@6420: 					/* Do we need to inject a free block too? */
tron@1353: 					if (cur_size != mem_req) {
tron@1353: 						NextBlock(s)->size = (cur_size - mem_req) | S_FREE_MASK;
tron@1353: 					}
truelight@0: 
tron@1353: 					return s->data;
tron@1353: 				}
tron@1353: 			}
truelight@0: 		}
truelight@0: 
belugas@6420: 		/* Reached sentinel, but no block found yet. Delete some old entry. */
tron@1353: 		DeleteEntryFromSpriteCache();
truelight@0: 	}
truelight@0: }
truelight@0: 
truelight@0: 
rubidium@6869: const void *GetRawSprite(SpriteID sprite, bool real_sprite)
truelight@0: {
peter1138@5504: 	SpriteCache *sc;
tron@2014: 	void* p;
truelight@0: 
peter1138@5702: 	assert(sprite < _spritecache_items);
truelight@0: 
peter1138@5504: 	sc = GetSpriteCache(sprite);
truelight@0: 
belugas@6420: 	/* Update LRU */
peter1138@5504: 	sc->lru = ++_sprite_lru_counter;
peter1138@5504: 
peter1138@5504: 	p = sc->ptr;
peter1138@5504: 
belugas@6420: 	/* Load the sprite, if it is not loaded, yet */
rubidium@6869: 	if (p == NULL) p = ReadSprite(sc, sprite, real_sprite);
belugas@8562: 
truelight@184: 	return p;
truelight@0: }
truelight@0: 
dominik@961: 
rubidium@6247: void GfxInitSpriteMem()
truelight@0: {
belugas@6420: 	/* initialize sprite cache heap */
rubidium@8037: 	if (_spritecache_ptr == NULL) _spritecache_ptr = (MemBlock*)MallocT<byte>(_sprite_cache_size * 1024 * 1024);
truelight@0: 
belugas@6420: 	/* A big free block */
peter1138@6803: 	_spritecache_ptr->size = ((_sprite_cache_size * 1024 * 1024) - sizeof(MemBlock)) | S_FREE_MASK;
belugas@6420: 	/* Sentinel block (identified by size == 0) */
tron@1353: 	NextBlock(_spritecache_ptr)->size = 0;
truelight@0: 
peter1138@5504: 	/* Reset the spritecache 'pool' */
peter1138@5504: 	free(_spritecache);
peter1138@5504: 	_spritecache_items = 0;
peter1138@5504: 	_spritecache = NULL;
truelight@0: 
tron@2340: 	_compact_cache_counter = 0;
truelight@0: }