1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "debug.h"

     6

#include "functions.h"

     7

#include "macros.h"

     8

#include "spritecache.h"

     9

#include "table/sprites.h"

    10

#include "fileio.h"

    11

    12

#define SPRITE_CACHE_SIZE 1024*1024

    13

    14

#define WANT_NEW_LRU

    15

    16

    17

static void* _sprite_ptr[MAX_SPRITES];

    18

static uint32 _sprite_file_pos[MAX_SPRITES];

    19

    20

#if defined(WANT_NEW_LRU)

    21

static int16 _sprite_lru_new[MAX_SPRITES];

    22

#else

    23

static uint16 _sprite_lru[MAX_SPRITES];

    24

static uint16 _sprite_lru_cur[MAX_SPRITES];

    25

#endif

    26

    27

typedef struct MemBlock {

    28

	uint32 size;

    29

	byte data[VARARRAY_SIZE];

    30

} MemBlock;

    31

    32

static uint _sprite_lru_counter;

    33

static MemBlock *_spritecache_ptr;

    34

static int _compact_cache_counter;

    35

    36

static void CompactSpriteCache(void);

    37

    38

static bool ReadSpriteHeaderSkipData(void)

    39

{

    40

	uint16 num = FioReadWord();

    41

	byte type;

    42

    43

	if (num == 0) return false;

    44

    45

	type = FioReadByte();

    46

	if (type == 0xFF) {

    47

		FioSkipBytes(num);

    48

		return true;

    49

	}

    50

    51

	FioSkipBytes(7);

    52

	num -= 8;

    53

	if (num == 0) return true;

    54

    55

	if (type & 2) {

    56

		FioSkipBytes(num);

    57

	} else {

    58

		while (num > 0) {

    59

			int8 i = FioReadByte();

    60

			if (i >= 0) {

    61

				num -= i;

    62

				FioSkipBytes(i);

    63

			} else {

    64

				i = -(i >> 3);

    65

				num -= i;

    66

				FioReadByte();

    67

			}

    68

		}

    69

	}

    70

    71

	return true;

    72

}

    73

    74

/* Check if the given Sprite ID exists */

    75

bool SpriteExists(SpriteID id)

    76

{

    77

	/* Special case for Sprite ID zero -- its position is also 0... */

    78

	return _sprite_file_pos[id] != 0 || id == 0;

    79

}

    80

    81

static void* AllocSprite(size_t);

    82

    83

static void* ReadSprite(SpriteID id)

    84

{

    85

	uint num;

    86

	byte type;

    87

    88

	DEBUG(spritecache, 9) ("load sprite %d", id);

    89

    90

	if (!SpriteExists(id)) {

    91

		error(

    92

			"Tried to load non-existing sprite #%d.\n"

    93

			"Probable cause: Wrong/missing NewGRFs",

    94

			id

    95

		);

    96

	}

    97

    98

	FioSeekToFile(_sprite_file_pos[id]);

    99

   100

	num  = FioReadWord();

   101

	type = FioReadByte();

   102

	if (type == 0xFF) {

   103

		byte* dest = AllocSprite(num);

   104

   105

		_sprite_ptr[id] = dest;

   106

		FioReadBlock(dest, num);

   107

   108

		return dest;

   109

	} else {

   110

		uint height = FioReadByte();

   111

		uint width  = FioReadWord();

   112

		Sprite* sprite;

   113

		byte* dest;

   114

   115

		num = (type & 0x02) ? width * height : num - 8;

   116

		sprite = AllocSprite(sizeof(*sprite) + num);

   117

		_sprite_ptr[id] = sprite;

   118

		sprite->info   = type;

   119

		sprite->height = (id != 142) ? height : 10; // Compensate for a TTD bug

   120

		sprite->width  = width;

   121

		sprite->x_offs = FioReadWord();

   122

		sprite->y_offs = FioReadWord();

   123

   124

		dest = sprite->data;

   125

		while (num > 0) {

   126

			int8 i = FioReadByte();

   127

   128

			if (i >= 0) {

   129

				num -= i;

   130

				for (; i > 0; --i) *dest++ = FioReadByte();

   131

			} else {

   132

				const byte* rel = dest - (((i & 7) << 8) | FioReadByte());

   133

   134

				i = -(i >> 3);

   135

				num -= i;

   136

   137

				for (; i > 0; --i) *dest++ = *rel++;

   138

			}

   139

		}

   140

   141

		return sprite;

   142

	}

   143

}

   144

   145

   146

bool LoadNextSprite(int load_index, byte file_index)

   147

{

   148

	uint32 file_pos = FioGetPos() | (file_index << 24);

   149

   150

	if (!ReadSpriteHeaderSkipData()) return false;

   151

   156

	_sprite_file_pos[load_index] = file_pos;

   157

   158

	_sprite_ptr[load_index] = NULL;

   159

   160

#if defined(WANT_NEW_LRU)

   161

	_sprite_lru_new[load_index] = 0;

   162

#else

   163

	_sprite_lru[load_index] = 0xFFFF;

   164

	_sprite_lru_cur[load_index] = 0;

   165

#endif

   166

   167

	return true;

   168

}

   169

   170

   171

void DupSprite(SpriteID old, SpriteID new)

   172

{

   173

	_sprite_file_pos[new] = _sprite_file_pos[old];

   174

	_sprite_ptr[new] = NULL;

   175

}

   176

   177

   178

void SkipSprites(uint count)

   179

{

   180

	for (; count > 0; --count) {

   181

		if (!ReadSpriteHeaderSkipData()) return;

   182

	}

   183

}

   184

   185

   186

#define S_FREE_MASK 1

   187

   188

static inline MemBlock* NextBlock(MemBlock* block)

   189

{

   190

	return (MemBlock*)((byte*)block + (block->size & ~S_FREE_MASK));

   191

}

   192

   193

static uint32 GetSpriteCacheUsage(void)

   194

{

   195

	size_t tot_size = 0;

   196

	MemBlock* s;

   197

   198

	for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s))

   199

		if (!(s->size & S_FREE_MASK)) tot_size += s->size;

   200

   201

	return tot_size;

   202

}

   203

   204

   205

void IncreaseSpriteLRU(void)

   206

{

   207

	int i;

   208

   209

	// Increase all LRU values

   210

#if defined(WANT_NEW_LRU)

   211

	if (_sprite_lru_counter > 16384) {

   212

		DEBUG(spritecache, 2) ("fixing lru %d, inuse=%d", _sprite_lru_counter, GetSpriteCacheUsage());

   213

   214

		for (i = 0; i != MAX_SPRITES; i++)

   215

			if (_sprite_ptr[i] != NULL) {

   216

				if (_sprite_lru_new[i] >= 0) {

   217

					_sprite_lru_new[i] = -1;

   218

				} else if (_sprite_lru_new[i] != -32768) {

   219

					_sprite_lru_new[i]--;

   220

				}

   221

			}

   222

		_sprite_lru_counter = 0;

   223

	}

   224

#else

   225

	for (i = 0; i != MAX_SPRITES; i++)

   226

		if (_sprite_ptr[i] != NULL && _sprite_lru[i] != 65535)

   227

			_sprite_lru[i]++;

   228

	// Reset the lru counter.

   229

	_sprite_lru_counter = 0;

   230

#endif

   231

   232

	// Compact sprite cache every now and then.

   233

	if (++_compact_cache_counter >= 740) {

   234

		CompactSpriteCache();

   235

		_compact_cache_counter = 0;

   236

	}

   237

}

   238

   239

// Called when holes in the sprite cache should be removed.

   240

// That is accomplished by moving the cached data.

   241

static void CompactSpriteCache(void)

   242

{

   243

	MemBlock *s;

   244

   245

	DEBUG(spritecache, 2) (

   246

		"compacting sprite cache, inuse=%d", GetSpriteCacheUsage()

   247

	);

   248

   249

	for (s = _spritecache_ptr; s->size != 0;) {

   250

		if (s->size & S_FREE_MASK) {

   251

			MemBlock* next = NextBlock(s);

   252

			MemBlock temp;

   253

			void** i;

   254

   255

			// Since free blocks are automatically coalesced, this should hold true.

   256

			assert(!(next->size & S_FREE_MASK));

   257

   258

			// If the next block is the sentinel block, we can safely return

   259

			if (next->size == 0)

   260

				break;

   261

   262

			// Locate the sprite belonging to the next pointer.

   263

			for (i = _sprite_ptr; *i != next->data; ++i) {

   264

				assert(i != endof(_sprite_ptr));

   265

			}

   266

   267

			*i = s->data; // Adjust sprite array entry

   268

			// Swap this and the next block

   269

			temp = *s;

   270

			memmove(s, next, next->size);

   271

			s = NextBlock(s);

   272

			*s = temp;

   273

   274

			// Coalesce free blocks

   275

			while (NextBlock(s)->size & S_FREE_MASK) {

   276

				s->size += NextBlock(s)->size & ~S_FREE_MASK;

   277

			}

   278

		} else {

   279

			s = NextBlock(s);

   280

		}

   281

	}

   282

}

   283

   284

static void DeleteEntryFromSpriteCache(void)

   285

{

   286

	int i;

   287

	int best = -1;

   288

	MemBlock* s;

   289

	int cur_lru;

   290

   291

	DEBUG(spritecache, 2) ("DeleteEntryFromSpriteCache, inuse=%d", GetSpriteCacheUsage());

   292

   293

#if defined(WANT_NEW_LRU)

   294

	cur_lru = 0xffff;

   295

	for (i = 0; i != MAX_SPRITES; i++) {

   296

		if (_sprite_ptr[i] != NULL && _sprite_lru_new[i] < cur_lru) {

   297

			cur_lru = _sprite_lru_new[i];

   298

			best = i;

   299

		}

   300

	}

   301

#else

   302

	{

   303

	uint16 cur_lru = 0, cur_lru_cur = 0xffff;

   304

	for (i = 0; i != MAX_SPRITES; i++) {

   305

		if (_sprite_ptr[i] == NULL || _sprite_lru[i] < cur_lru) continue;

   306

   307

		// Found a sprite with a higher LRU value, then remember it.

   308

		if (_sprite_lru[i] != cur_lru) {

   309

			cur_lru = _sprite_lru[i];

   310

			best = i;

   311

   312

		// Else if both sprites were very recently referenced, compare by the cur value instead.

   313

		} else if (cur_lru == 0 && _sprite_lru_cur[i] <= cur_lru_cur) {

   314

			cur_lru_cur = _sprite_lru_cur[i];

   315

			cur_lru = _sprite_lru[i];

   316

			best = i;

   317

		}

   318

	}

   319

	}

   320

#endif

   321

   322

	// Display an error message and die, in case we found no sprite at all.

   323

	// This shouldn't really happen, unless all sprites are locked.

   324

	if (best == -1)

   325

		error("Out of sprite memory");

   326

   327

	// Mark the block as free (the block must be in use)

   328

	s = (MemBlock*)_sprite_ptr[best] - 1;

   329

	assert(!(s->size & S_FREE_MASK));

   330

	s->size |= S_FREE_MASK;

   331

	_sprite_ptr[best] = NULL;

   332

   333

	// And coalesce adjacent free blocks

   334

	for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {

   335

		if (s->size & S_FREE_MASK) {

   336

			while (NextBlock(s)->size & S_FREE_MASK) {

   337

				s->size += NextBlock(s)->size & ~S_FREE_MASK;

   338

			}

   339

		}

   340

	}

   341

}

   342

   343

static void* AllocSprite(size_t mem_req)

   344

{

   345

	mem_req += sizeof(MemBlock);

   346

   347

	/* Align this to an uint32 boundary. This also makes sure that the 2 least

   348

	 * bits are not used, so we could use those for other things. */

   349

	mem_req = ALIGN(mem_req, sizeof(uint32));

   350

   351

	for (;;) {

   352

		MemBlock* s;

   353

   354

		for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {

   355

			if (s->size & S_FREE_MASK) {

   356

				size_t cur_size = s->size & ~S_FREE_MASK;

   357

   358

				/* Is the block exactly the size we need or

   359

				 * big enough for an additional free block? */

   360

				if (cur_size == mem_req ||

   361

						cur_size >= mem_req + sizeof(MemBlock)) {

   362

					// Set size and in use

   363

					s->size = mem_req;

   364

   365

					// Do we need to inject a free block too?

   366

					if (cur_size != mem_req) {

   367

						NextBlock(s)->size = (cur_size - mem_req) | S_FREE_MASK;

   368

					}

   369

   370

					return s->data;

   371

				}

   372

			}

   373

		}

   374

   375

		// Reached sentinel, but no block found yet. Delete some old entry.

   376

		DeleteEntryFromSpriteCache();

   377

	}

   378

}

   379

   380

#if defined(NEW_ROTATION)

   381

#define X15(x) else if (s >= x && s < (x+15)) { s = _rotate_tile_sprite[s - x] + x; }

   382

#define X19(x) else if (s >= x && s < (x+19)) { s = _rotate_tile_sprite[s - x] + x; }

   383

#define MAP(from,to,map) else if (s >= from && s <= to) { s = map[s - from] + from; }

   384

   385

   386

static uint RotateSprite(uint s)

   387

{

   388

	static const byte _rotate_tile_sprite[19] = { 0,2,4,6,8,10,12,14,1,3,5,7,9,11,13,17,18,16,15 };

   389

	static const byte _coast_map[9] = {0, 4, 3, 1, 2, 6, 8, 5, 7};

   390

	static const byte _fence_map[6] = {1, 0, 5, 4, 3, 2};

   391

   392

	if (0);

   393

	X19(752)

   394

	X15(990-1)

   395

	X19(3924)

   396

	X19(3943)

   397

	X19(3962)

   398

	X19(3981)

   399

	X19(4000)

   400

	X19(4023)

   401

	X19(4042)

   402

	MAP(4061,4069,_coast_map)

   403

	X19(4126)

   404

	X19(4145)

   405

	X19(4164)

   406

	X19(4183)

   407

	X19(4202)

   408

	X19(4221)

   409

	X19(4240)

   410

	X19(4259)

   411

	X19(4259)

   412

	X19(4278)

   413

	MAP(4090, 4095, _fence_map)

   414

	MAP(4096, 4101, _fence_map)

   415

	MAP(4102, 4107, _fence_map)

   416

	MAP(4108, 4113, _fence_map)

   417

	MAP(4114, 4119, _fence_map)

   418

	MAP(4120, 4125, _fence_map)

   419

	return s;

   420

}

   421

#endif

   422

   423

const void *GetRawSprite(SpriteID sprite)

   424

{

   425

	void* p;

   426

   427

	assert(sprite < MAX_SPRITES);

   428

   429

#if defined(NEW_ROTATION)

   430

	sprite = RotateSprite(sprite);

   431

#endif

   432

   433

	// Update LRU

   434

#if defined(WANT_NEW_LRU)

   435

	_sprite_lru_new[sprite] = ++_sprite_lru_counter;

   436

#else

   437

	_sprite_lru_cur[sprite] = ++_sprite_lru_counter;

   438

	_sprite_lru[sprite] = 0;

   439

#endif

   440

   441

	p = _sprite_ptr[sprite];

   442

	// Load the sprite, if it is not loaded, yet

   443

	if (p == NULL) p = ReadSprite(sprite);

   444

	return p;

   445

}

   446

   447

   448

void GfxInitSpriteMem(void)

   449

{

   450

	// initialize sprite cache heap

   451

	if (_spritecache_ptr == NULL) _spritecache_ptr = malloc(SPRITE_CACHE_SIZE);

   452

   453

	// A big free block

   454

	_spritecache_ptr->size = (SPRITE_CACHE_SIZE - sizeof(MemBlock)) | S_FREE_MASK;

   455

	// Sentinel block (identified by size == 0)

   456

	NextBlock(_spritecache_ptr)->size = 0;

   457

   458

	memset(_sprite_ptr, 0, sizeof(_sprite_ptr));

   459

   460

	_compact_cache_counter = 0;

   461

}