1

/* $Id$ */

     2

     3

#include "stdafx.h"

     4

#include "openttd.h"

     5

#include "debug.h"

     6

#include "functions.h"

     7

#include "spritecache.h"

     8

#include "table/sprites.h"

     9

#include "fileio.h"

    10

    11

#define SPRITE_CACHE_SIZE 1024*1024

    12

    13

#define WANT_NEW_LRU

    14

    15

    16

static void* _sprite_ptr[MAX_SPRITES];

    17

static uint32 _sprite_file_pos[MAX_SPRITES];

    18

    19

#if defined(WANT_NEW_LRU)

    20

static int16 _sprite_lru_new[MAX_SPRITES];

    21

#else

    22

static uint16 _sprite_lru[MAX_SPRITES];

    23

static uint16 _sprite_lru_cur[MAX_SPRITES];

    24

#endif

    25

    26

typedef struct MemBlock {

    27

	uint32 size;

    28

	byte data[VARARRAY_SIZE];

    29

} MemBlock;

    30

    31

static uint _sprite_lru_counter;

    32

static MemBlock *_spritecache_ptr;

    33

static int _compact_cache_counter;

    34

    35

static void CompactSpriteCache(void);

    36

    37

static bool ReadSpriteHeaderSkipData(void)

    38

{

    39

	uint16 num = FioReadWord();

    40

	byte type;

    41

    42

	if (num == 0) return false;

    43

    44

	type = FioReadByte();

    45

	if (type == 0xFF) {

    46

		FioSkipBytes(num);

    47

		return true;

    48

	}

    49

    50

	FioSkipBytes(7);

    51

	num -= 8;

    52

	if (num == 0) return true;

    53

    54

	if (type & 2) {

    55

		FioSkipBytes(num);

    56

	} else {

    57

		while (num > 0) {

    58

			int8 i = FioReadByte();

    59

			if (i >= 0) {

    60

				num -= i;

    61

				FioSkipBytes(i);

    62

			} else {

    63

				i = -(i >> 3);

    64

				num -= i;

    65

				FioReadByte();

    66

			}

    67

		}

    68

	}

    69

    70

	return true;

    71

}

    72

    73

static void* AllocSprite(size_t);

    74

    75

static void* ReadSprite(SpriteID id)

    76

{

    77

	uint num;

    78

	byte type;

    79

    80

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

    81

    82

	if (_sprite_file_pos[id] == 0 && id != 0) {

    83

		error(

    84

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

    85

			"Probable cause: Wrong/missing NewGRFs",

    86

			id

    87

		);

    88

	}

    89

    90

	FioSeekToFile(_sprite_file_pos[id]);

    91

    92

	num  = FioReadWord();

    93

	type = FioReadByte();

    94

	if (type == 0xFF) {

    95

		byte* dest = AllocSprite(num);

    96

    97

		_sprite_ptr[id] = dest;

    98

		FioReadBlock(dest, num);

    99

   100

		return dest;

   101

	} else {

   102

		uint height = FioReadByte();

   103

		uint width  = FioReadWord();

   104

		Sprite* sprite;

   105

		byte* dest;

   106

   107

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

   108

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

   109

		_sprite_ptr[id] = sprite;

   110

		sprite->info   = type;

   111

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

   112

		sprite->width  = width;

   113

		sprite->x_offs = FioReadWord();

   114

		sprite->y_offs = FioReadWord();

   115

   116

		dest = sprite->data;

   117

		while (num > 0) {

   118

			int8 i = FioReadByte();

   119

   120

			if (i >= 0) {

   121

				num -= i;

   122

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

   123

			} else {

   124

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

   125

   126

				i = -(i >> 3);

   127

				num -= i;

   128

   129

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

   130

			}

   131

		}

   132

   133

		return sprite;

   134

	}

   135

}

   136

   137

   138

bool LoadNextSprite(int load_index, byte file_index)

   139

{

   140

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

   141

   142

	if (!ReadSpriteHeaderSkipData()) return false;

   143

   144

	_sprite_file_pos[load_index] = file_pos;

   145

   146

	_sprite_ptr[load_index] = NULL;

   147

   148

#if defined(WANT_NEW_LRU)

   149

	_sprite_lru_new[load_index] = 0;

   150

#else

   151

	_sprite_lru[load_index] = 0xFFFF;

   152

	_sprite_lru_cur[load_index] = 0;

   153

#endif

   154

   155

	return true;

   156

}

   157

   158

void SkipSprites(uint count)

   159

{

   160

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

   161

		if (!ReadSpriteHeaderSkipData()) return;

   162

	}

   163

}

   164

   165

   166

#define S_FREE_MASK 1

   167

   168

static inline MemBlock* NextBlock(MemBlock* block)

   169

{

   170

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

   171

}

   172

   173

static uint32 GetSpriteCacheUsage(void)

   174

{

   175

	size_t tot_size = 0;

   176

	MemBlock* s;

   177

   178

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

   179

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

   180

   181

	return tot_size;

   182

}

   183

   184

   185

void IncreaseSpriteLRU(void)

   186

{

   187

	int i;

   188

   189

	// Increase all LRU values

   190

#if defined(WANT_NEW_LRU)

   191

	if (_sprite_lru_counter > 16384) {

   192

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

   193

   194

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

   195

			if (_sprite_ptr[i] != NULL) {

   196

				if (_sprite_lru_new[i] >= 0) {

   197

					_sprite_lru_new[i] = -1;

   198

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

   199

					_sprite_lru_new[i]--;

   200

				}

   201

			}

   202

		_sprite_lru_counter = 0;

   203

	}

   204

#else

   205

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

   206

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

   207

			_sprite_lru[i]++;

   208

	// Reset the lru counter.

   209

	_sprite_lru_counter = 0;

   210

#endif

   211

   212

	// Compact sprite cache every now and then.

   213

	if (++_compact_cache_counter >= 740) {

   214

		CompactSpriteCache();

   215

		_compact_cache_counter = 0;

   216

	}

   217

}

   218

   219

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

   220

// That is accomplished by moving the cached data.

   221

static void CompactSpriteCache(void)

   222

{

   223

	MemBlock *s;

   224

   225

	DEBUG(spritecache, 2) (

   226

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

   227

	);

   228

   229

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

   230

		if (s->size & S_FREE_MASK) {

   231

			MemBlock* next = NextBlock(s);

   232

			MemBlock temp;

   233

			void** i;

   234

   235

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

   236

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

   237

   238

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

   239

			if (next->size == 0)

   240

				break;

   241

   242

			// Locate the sprite belonging to the next pointer.

   243

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

   244

				assert(i != endof(_sprite_ptr));

   245

			}

   246

   247

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

   248

			// Swap this and the next block

   249

			temp = *s;

   250

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

   251

			s = NextBlock(s);

   252

			*s = temp;

   253

   254

			// Coalesce free blocks

   255

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

   256

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

   257

			}

   258

		} else {

   259

			s = NextBlock(s);

   260

		}

   261

	}

   262

}

   263

   264

static void DeleteEntryFromSpriteCache(void)

   265

{

   266

	int i;

   267

	int best = -1;

   268

	MemBlock* s;

   269

	int cur_lru;

   270

   271

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

   272

   273

#if defined(WANT_NEW_LRU)

   274

	cur_lru = 0xffff;

   275

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

   276

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

   277

			cur_lru = _sprite_lru_new[i];

   278

			best = i;

   279

		}

   280

	}

   281

#else

   282

	{

   283

	uint16 cur_lru = 0, cur_lru_cur = 0xffff;

   284

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

   285

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

   286

   287

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

   288

		if (_sprite_lru[i] != cur_lru) {

   289

			cur_lru = _sprite_lru[i];

   290

			best = i;

   291

   292

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

   293

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

   294

			cur_lru_cur = _sprite_lru_cur[i];

   295

			cur_lru = _sprite_lru[i];

   296

			best = i;

   297

		}

   298

	}

   299

	}

   300

#endif

   301

   302

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

   303

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

   304

	if (best == -1)

   305

		error("Out of sprite memory");

   306

   307

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

   308

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

   309

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

   310

	s->size |= S_FREE_MASK;

   311

	_sprite_ptr[best] = NULL;

   312

   313

	// And coalesce adjacent free blocks

   314

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

   315

		if (s->size & S_FREE_MASK) {

   316

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

   317

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

   318

			}

   319

		}

   320

	}

   321

}

   322

   323

static void* AllocSprite(size_t mem_req)

   324

{

   325

	mem_req += sizeof(MemBlock);

   326

   327

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

   328

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

   329

	mem_req = (mem_req + sizeof(uint32) - 1) & ~(sizeof(uint32) - 1);

   330

   331

	for (;;) {

   332

		MemBlock* s;

   333

   334

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

   335

			if (s->size & S_FREE_MASK) {

   336

				size_t cur_size = s->size & ~S_FREE_MASK;

   337

   338

				/* Is the block exactly the size we need or

   339

				 * big enough for an additional free block? */

   340

				if (cur_size == mem_req ||

   341

						cur_size >= mem_req + sizeof(MemBlock)) {

   342

					// Set size and in use

   343

					s->size = mem_req;

   344

   345

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

   346

					if (cur_size != mem_req) {

   347

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

   348

					}

   349

   350

					return s->data;

   351

				}

   352

			}

   353

		}

   354

   355

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

   356

		DeleteEntryFromSpriteCache();

   357

	}

   358

}

   359

   360

#if defined(NEW_ROTATION)

   361

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

   362

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

   363

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

   364

   365

   366

static uint RotateSprite(uint s)

   367

{

   368

	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 };

   369

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

   370

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

   371

   372

	if (0);

   373

	X19(752)

   374

	X15(990-1)

   375

	X19(3924)

   376

	X19(3943)

   377

	X19(3962)

   378

	X19(3981)

   379

	X19(4000)

   380

	X19(4023)

   381

	X19(4042)

   382

	MAP(4061,4069,_coast_map)

   383

	X19(4126)

   384

	X19(4145)

   385

	X19(4164)

   386

	X19(4183)

   387

	X19(4202)

   388

	X19(4221)

   389

	X19(4240)

   390

	X19(4259)

   391

	X19(4259)

   392

	X19(4278)

   393

	MAP(4090, 4095, _fence_map)

   394

	MAP(4096, 4101, _fence_map)

   395

	MAP(4102, 4107, _fence_map)

   396

	MAP(4108, 4113, _fence_map)

   397

	MAP(4114, 4119, _fence_map)

   398

	MAP(4120, 4125, _fence_map)

   399

	return s;

   400

}

   401

#endif

   402

   403

const void *GetRawSprite(SpriteID sprite)

   404

{

   405

	void* p;

   406

   407

	assert(sprite < MAX_SPRITES);

   408

   409

#if defined(NEW_ROTATION)

   410

	sprite = RotateSprite(sprite);

   411

#endif

   412

   413

	// Update LRU

   414

#if defined(WANT_NEW_LRU)

   415

	_sprite_lru_new[sprite] = ++_sprite_lru_counter;

   416

#else

   417

	_sprite_lru_cur[sprite] = ++_sprite_lru_counter;

   418

	_sprite_lru[sprite] = 0;

   419

#endif

   420

   421

	p = _sprite_ptr[sprite];

   422

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

   423

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

   424

	return p;

   425

}

   426

   427

   428

void GfxInitSpriteMem(void)

   429

{

   430

	// initialize sprite cache heap

   431

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

   432

   433

	// A big free block

   434

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

   435

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

   436

	NextBlock(_spritecache_ptr)->size = 0;

   437

   438

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

   439

   440

	_compact_cache_counter = 0;

   441

}