OpenTTD Source  1.11.2
spritecache.cpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * 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.
4  * 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.
5  * 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/>.
6  */
7 
10 #include "stdafx.h"
11 #include "fileio_func.h"
12 #include "spriteloader/grf.hpp"
13 #include "gfx_func.h"
14 #include "error.h"
15 #include "zoom_func.h"
16 #include "settings_type.h"
17 #include "blitter/factory.hpp"
18 #include "core/math_func.hpp"
19 #include "core/mem_func.hpp"
20 #include "video/video_driver.hpp"
21 
22 #include "table/sprites.h"
23 #include "table/strings.h"
24 #include "table/palette_convert.h"
25 
26 #include "safeguards.h"
27 
28 /* Default of 4MB spritecache */
29 uint _sprite_cache_size = 4;
30 
31 struct SpriteCache {
32  void *ptr;
33  size_t file_pos;
34  uint32 id;
35  uint16 file_slot;
36  int16 lru;
38  bool warned;
40 };
41 
42 
43 static uint _spritecache_items = 0;
44 static SpriteCache *_spritecache = nullptr;
45 
46 
47 static inline SpriteCache *GetSpriteCache(uint index)
48 {
49  return &_spritecache[index];
50 }
51 
52 static inline bool IsMapgenSpriteID(SpriteID sprite)
53 {
54  return IsInsideMM(sprite, 4845, 4882);
55 }
56 
57 static SpriteCache *AllocateSpriteCache(uint index)
58 {
59  if (index >= _spritecache_items) {
60  /* Add another 1024 items to the 'pool' */
61  uint items = Align(index + 1, 1024);
62 
63  DEBUG(sprite, 4, "Increasing sprite cache to %u items (" PRINTF_SIZE " bytes)", items, items * sizeof(*_spritecache));
64 
65  _spritecache = ReallocT(_spritecache, items);
66 
67  /* Reset the new items and update the count */
68  memset(_spritecache + _spritecache_items, 0, (items - _spritecache_items) * sizeof(*_spritecache));
69  _spritecache_items = items;
70  }
71 
72  return GetSpriteCache(index);
73 }
74 
75 
76 struct MemBlock {
77  size_t size;
78  byte data[];
79 };
80 
81 static uint _sprite_lru_counter;
82 static MemBlock *_spritecache_ptr;
83 static uint _allocated_sprite_cache_size = 0;
84 static int _compact_cache_counter;
85 
86 static void CompactSpriteCache();
87 static void *AllocSprite(size_t mem_req);
88 
95 bool SkipSpriteData(byte type, uint16 num)
96 {
97  if (type & 2) {
98  FioSkipBytes(num);
99  } else {
100  while (num > 0) {
101  int8 i = FioReadByte();
102  if (i >= 0) {
103  int size = (i == 0) ? 0x80 : i;
104  if (size > num) return false;
105  num -= size;
106  FioSkipBytes(size);
107  } else {
108  i = -(i >> 3);
109  num -= i;
110  FioReadByte();
111  }
112  }
113  }
114  return true;
115 }
116 
117 /* Check if the given Sprite ID exists */
118 bool SpriteExists(SpriteID id)
119 {
120  if (id >= _spritecache_items) return false;
121 
122  /* Special case for Sprite ID zero -- its position is also 0... */
123  if (id == 0) return true;
124  return !(GetSpriteCache(id)->file_pos == 0 && GetSpriteCache(id)->file_slot == 0);
125 }
126 
133 {
134  if (!SpriteExists(sprite)) return ST_INVALID;
135  return GetSpriteCache(sprite)->type;
136 }
137 
144 {
145  if (!SpriteExists(sprite)) return 0;
146  return GetSpriteCache(sprite)->file_slot;
147 }
148 
155 {
156  if (!SpriteExists(sprite)) return 0;
157  return GetSpriteCache(sprite)->id;
158 }
159 
167 uint GetSpriteCountForSlot(uint file_slot, SpriteID begin, SpriteID end)
168 {
169  uint count = 0;
170  for (SpriteID i = begin; i != end; i++) {
171  if (SpriteExists(i)) {
172  SpriteCache *sc = GetSpriteCache(i);
173  if (sc->file_slot == file_slot) count++;
174  }
175  }
176  return count;
177 }
178 
188 {
189  return _spritecache_items;
190 }
191 
192 static bool ResizeSpriteIn(SpriteLoader::Sprite *sprite, ZoomLevel src, ZoomLevel tgt)
193 {
194  uint8 scaled_1 = ScaleByZoom(1, (ZoomLevel)(src - tgt));
195 
196  /* Check for possible memory overflow. */
197  if (sprite[src].width * scaled_1 > UINT16_MAX || sprite[src].height * scaled_1 > UINT16_MAX) return false;
198 
199  sprite[tgt].width = sprite[src].width * scaled_1;
200  sprite[tgt].height = sprite[src].height * scaled_1;
201  sprite[tgt].x_offs = sprite[src].x_offs * scaled_1;
202  sprite[tgt].y_offs = sprite[src].y_offs * scaled_1;
203  sprite[tgt].colours = sprite[src].colours;
204 
205  sprite[tgt].AllocateData(tgt, sprite[tgt].width * sprite[tgt].height);
206 
207  SpriteLoader::CommonPixel *dst = sprite[tgt].data;
208  for (int y = 0; y < sprite[tgt].height; y++) {
209  const SpriteLoader::CommonPixel *src_ln = &sprite[src].data[y / scaled_1 * sprite[src].width];
210  for (int x = 0; x < sprite[tgt].width; x++) {
211  *dst = src_ln[x / scaled_1];
212  dst++;
213  }
214  }
215 
216  return true;
217 }
218 
219 static void ResizeSpriteOut(SpriteLoader::Sprite *sprite, ZoomLevel zoom)
220 {
221  /* Algorithm based on 32bpp_Optimized::ResizeSprite() */
222  sprite[zoom].width = UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].width, zoom);
223  sprite[zoom].height = UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].height, zoom);
224  sprite[zoom].x_offs = UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].x_offs, zoom);
225  sprite[zoom].y_offs = UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].y_offs, zoom);
226  sprite[zoom].colours = sprite[ZOOM_LVL_NORMAL].colours;
227 
228  sprite[zoom].AllocateData(zoom, sprite[zoom].height * sprite[zoom].width);
229 
230  SpriteLoader::CommonPixel *dst = sprite[zoom].data;
231  const SpriteLoader::CommonPixel *src = sprite[zoom - 1].data;
232 #ifdef WITH_ASSERT
233  const SpriteLoader::CommonPixel *src_end = src + sprite[zoom - 1].height * sprite[zoom - 1].width;
234 #endif
235 
236  for (uint y = 0; y < sprite[zoom].height; y++) {
237  const SpriteLoader::CommonPixel *src_ln = src + sprite[zoom - 1].width;
238  assert(src_ln <= src_end);
239  for (uint x = 0; x < sprite[zoom].width; x++) {
240  assert(src < src_ln);
241  if (src + 1 != src_ln && (src + 1)->a != 0) {
242  *dst = *(src + 1);
243  } else {
244  *dst = *src;
245  }
246  dst++;
247  src += 2;
248  }
249  src = src_ln + sprite[zoom - 1].width;
250  }
251 }
252 
253 static bool PadSingleSprite(SpriteLoader::Sprite *sprite, ZoomLevel zoom, uint pad_left, uint pad_top, uint pad_right, uint pad_bottom)
254 {
255  uint width = sprite->width + pad_left + pad_right;
256  uint height = sprite->height + pad_top + pad_bottom;
257 
258  if (width > UINT16_MAX || height > UINT16_MAX) return false;
259 
260  /* Copy source data and reallocate sprite memory. */
261  SpriteLoader::CommonPixel *src_data = MallocT<SpriteLoader::CommonPixel>(sprite->width * sprite->height);
262  MemCpyT(src_data, sprite->data, sprite->width * sprite->height);
263  sprite->AllocateData(zoom, width * height);
264 
265  /* Copy with padding to destination. */
266  SpriteLoader::CommonPixel *src = src_data;
267  SpriteLoader::CommonPixel *data = sprite->data;
268  for (uint y = 0; y < height; y++) {
269  if (y < pad_top || pad_bottom + y >= height) {
270  /* Top/bottom padding. */
271  MemSetT(data, 0, width);
272  data += width;
273  } else {
274  if (pad_left > 0) {
275  /* Pad left. */
276  MemSetT(data, 0, pad_left);
277  data += pad_left;
278  }
279 
280  /* Copy pixels. */
281  MemCpyT(data, src, sprite->width);
282  src += sprite->width;
283  data += sprite->width;
284 
285  if (pad_right > 0) {
286  /* Pad right. */
287  MemSetT(data, 0, pad_right);
288  data += pad_right;
289  }
290  }
291  }
292  free(src_data);
293 
294  /* Update sprite size. */
295  sprite->width = width;
296  sprite->height = height;
297  sprite->x_offs -= pad_left;
298  sprite->y_offs -= pad_top;
299 
300  return true;
301 }
302 
303 static bool PadSprites(SpriteLoader::Sprite *sprite, uint8 sprite_avail, SpriteEncoder *encoder)
304 {
305  /* Get minimum top left corner coordinates. */
306  int min_xoffs = INT32_MAX;
307  int min_yoffs = INT32_MAX;
308  for (ZoomLevel zoom = ZOOM_LVL_BEGIN; zoom != ZOOM_LVL_END; zoom++) {
309  if (HasBit(sprite_avail, zoom)) {
310  min_xoffs = std::min(min_xoffs, ScaleByZoom(sprite[zoom].x_offs, zoom));
311  min_yoffs = std::min(min_yoffs, ScaleByZoom(sprite[zoom].y_offs, zoom));
312  }
313  }
314 
315  /* Get maximum dimensions taking necessary padding at the top left into account. */
316  int max_width = INT32_MIN;
317  int max_height = INT32_MIN;
318  for (ZoomLevel zoom = ZOOM_LVL_BEGIN; zoom != ZOOM_LVL_END; zoom++) {
319  if (HasBit(sprite_avail, zoom)) {
320  max_width = std::max(max_width, ScaleByZoom(sprite[zoom].width + sprite[zoom].x_offs - UnScaleByZoom(min_xoffs, zoom), zoom));
321  max_height = std::max(max_height, ScaleByZoom(sprite[zoom].height + sprite[zoom].y_offs - UnScaleByZoom(min_yoffs, zoom), zoom));
322  }
323  }
324 
325  /* Align height and width if required to match the needs of the sprite encoder. */
326  uint align = encoder->GetSpriteAlignment();
327  if (align != 0) {
328  max_width = Align(max_width, align);
329  max_height = Align(max_height, align);
330  }
331 
332  /* Pad sprites where needed. */
333  for (ZoomLevel zoom = ZOOM_LVL_BEGIN; zoom != ZOOM_LVL_END; zoom++) {
334  if (HasBit(sprite_avail, zoom)) {
335  /* Scaling the sprite dimensions in the blitter is done with rounding up,
336  * so a negative padding here is not an error. */
337  int pad_left = std::max(0, sprite[zoom].x_offs - UnScaleByZoom(min_xoffs, zoom));
338  int pad_top = std::max(0, sprite[zoom].y_offs - UnScaleByZoom(min_yoffs, zoom));
339  int pad_right = std::max(0, UnScaleByZoom(max_width, zoom) - sprite[zoom].width - pad_left);
340  int pad_bottom = std::max(0, UnScaleByZoom(max_height, zoom) - sprite[zoom].height - pad_top);
341 
342  if (pad_left > 0 || pad_right > 0 || pad_top > 0 || pad_bottom > 0) {
343  if (!PadSingleSprite(&sprite[zoom], zoom, pad_left, pad_top, pad_right, pad_bottom)) return false;
344  }
345  }
346  }
347 
348  return true;
349 }
350 
351 static bool ResizeSprites(SpriteLoader::Sprite *sprite, uint8 sprite_avail, uint32 file_slot, uint32 file_pos, SpriteEncoder *encoder)
352 {
353  /* Create a fully zoomed image if it does not exist */
354  ZoomLevel first_avail = static_cast<ZoomLevel>(FIND_FIRST_BIT(sprite_avail));
355  if (first_avail != ZOOM_LVL_NORMAL) {
356  if (!ResizeSpriteIn(sprite, first_avail, ZOOM_LVL_NORMAL)) return false;
357  SetBit(sprite_avail, ZOOM_LVL_NORMAL);
358  }
359 
360  /* Pad sprites to make sizes match. */
361  if (!PadSprites(sprite, sprite_avail, encoder)) return false;
362 
363  /* Create other missing zoom levels */
364  for (ZoomLevel zoom = ZOOM_LVL_OUT_2X; zoom != ZOOM_LVL_END; zoom++) {
365  if (HasBit(sprite_avail, zoom)) {
366  /* Check that size and offsets match the fully zoomed image. */
367  assert(sprite[zoom].width == UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].width, zoom));
368  assert(sprite[zoom].height == UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].height, zoom));
369  assert(sprite[zoom].x_offs == UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].x_offs, zoom));
370  assert(sprite[zoom].y_offs == UnScaleByZoom(sprite[ZOOM_LVL_NORMAL].y_offs, zoom));
371  }
372 
373  /* Zoom level is not available, or unusable, so create it */
374  if (!HasBit(sprite_avail, zoom)) ResizeSpriteOut(sprite, zoom);
375  }
376 
377  return true;
378 }
379 
386 static void *ReadRecolourSprite(uint16 file_slot, uint num)
387 {
388  /* "Normal" recolour sprites are ALWAYS 257 bytes. Then there is a small
389  * number of recolour sprites that are 17 bytes that only exist in DOS
390  * GRFs which are the same as 257 byte recolour sprites, but with the last
391  * 240 bytes zeroed. */
392  static const uint RECOLOUR_SPRITE_SIZE = 257;
393  byte *dest = (byte *)AllocSprite(std::max(RECOLOUR_SPRITE_SIZE, num));
394 
395  if (_palette_remap_grf[file_slot]) {
396  byte *dest_tmp = AllocaM(byte, std::max(RECOLOUR_SPRITE_SIZE, num));
397 
398  /* Only a few recolour sprites are less than 257 bytes */
399  if (num < RECOLOUR_SPRITE_SIZE) memset(dest_tmp, 0, RECOLOUR_SPRITE_SIZE);
400  FioReadBlock(dest_tmp, num);
401 
402  /* The data of index 0 is never used; "literal 00" according to the (New)GRF specs. */
403  for (uint i = 1; i < RECOLOUR_SPRITE_SIZE; i++) {
404  dest[i] = _palmap_w2d[dest_tmp[_palmap_d2w[i - 1] + 1]];
405  }
406  } else {
407  FioReadBlock(dest, num);
408  }
409 
410  return dest;
411 }
412 
422 static void *ReadSprite(const SpriteCache *sc, SpriteID id, SpriteType sprite_type, AllocatorProc *allocator, SpriteEncoder *encoder)
423 {
424  /* Use current blitter if no other sprite encoder is given. */
425  if (encoder == nullptr) encoder = BlitterFactory::GetCurrentBlitter();
426 
427  uint8 file_slot = sc->file_slot;
428  size_t file_pos = sc->file_pos;
429 
430  assert(sprite_type != ST_RECOLOUR);
431  assert(IsMapgenSpriteID(id) == (sprite_type == ST_MAPGEN));
432  assert(sc->type == sprite_type);
433 
434  DEBUG(sprite, 9, "Load sprite %d", id);
435 
437  uint8 sprite_avail = 0;
438  sprite[ZOOM_LVL_NORMAL].type = sprite_type;
439 
440  SpriteLoaderGrf sprite_loader(sc->container_ver);
441  if (sprite_type != ST_MAPGEN && encoder->Is32BppSupported()) {
442  /* Try for 32bpp sprites first. */
443  sprite_avail = sprite_loader.LoadSprite(sprite, file_slot, file_pos, sprite_type, true);
444  }
445  if (sprite_avail == 0) {
446  sprite_avail = sprite_loader.LoadSprite(sprite, file_slot, file_pos, sprite_type, false);
447  }
448 
449  if (sprite_avail == 0) {
450  if (sprite_type == ST_MAPGEN) return nullptr;
451  if (id == SPR_IMG_QUERY) usererror("Okay... something went horribly wrong. I couldn't load the fallback sprite. What should I do?");
452  return (void*)GetRawSprite(SPR_IMG_QUERY, ST_NORMAL, allocator, encoder);
453  }
454 
455  if (sprite_type == ST_MAPGEN) {
456  /* Ugly hack to work around the problem that the old landscape
457  * generator assumes that those sprites are stored uncompressed in
458  * the memory, and they are only read directly by the code, never
459  * send to the blitter. So do not send it to the blitter (which will
460  * result in a data array in the format the blitter likes most), but
461  * extract the data directly and store that as sprite.
462  * Ugly: yes. Other solution: no. Blame the original author or
463  * something ;) The image should really have been a data-stream
464  * (so type = 0xFF basically). */
465  uint num = sprite[ZOOM_LVL_NORMAL].width * sprite[ZOOM_LVL_NORMAL].height;
466 
467  Sprite *s = (Sprite *)allocator(sizeof(*s) + num);
468  s->width = sprite[ZOOM_LVL_NORMAL].width;
469  s->height = sprite[ZOOM_LVL_NORMAL].height;
470  s->x_offs = sprite[ZOOM_LVL_NORMAL].x_offs;
471  s->y_offs = sprite[ZOOM_LVL_NORMAL].y_offs;
472 
474  byte *dest = s->data;
475  while (num-- > 0) {
476  *dest++ = src->m;
477  src++;
478  }
479 
480  return s;
481  }
482 
483  if (!ResizeSprites(sprite, sprite_avail, file_slot, sc->id, encoder)) {
484  if (id == SPR_IMG_QUERY) usererror("Okay... something went horribly wrong. I couldn't resize the fallback sprite. What should I do?");
485  return (void*)GetRawSprite(SPR_IMG_QUERY, ST_NORMAL, allocator, encoder);
486  }
487 
488  if (sprite->type == ST_FONT && ZOOM_LVL_FONT != ZOOM_LVL_NORMAL) {
489  /* Make ZOOM_LVL_NORMAL be ZOOM_LVL_FONT */
490  sprite[ZOOM_LVL_NORMAL].width = sprite[ZOOM_LVL_FONT].width;
491  sprite[ZOOM_LVL_NORMAL].height = sprite[ZOOM_LVL_FONT].height;
492  sprite[ZOOM_LVL_NORMAL].x_offs = sprite[ZOOM_LVL_FONT].x_offs;
493  sprite[ZOOM_LVL_NORMAL].y_offs = sprite[ZOOM_LVL_FONT].y_offs;
494  sprite[ZOOM_LVL_NORMAL].data = sprite[ZOOM_LVL_FONT].data;
495  sprite[ZOOM_LVL_NORMAL].colours = sprite[ZOOM_LVL_FONT].colours;
496  }
497 
498  return encoder->Encode(sprite, allocator);
499 }
500 
501 
503 static std::map<uint32, size_t> _grf_sprite_offsets;
504 
510 size_t GetGRFSpriteOffset(uint32 id)
511 {
512  return _grf_sprite_offsets.find(id) != _grf_sprite_offsets.end() ? _grf_sprite_offsets[id] : SIZE_MAX;
513 }
514 
519 void ReadGRFSpriteOffsets(byte container_version)
520 {
521  _grf_sprite_offsets.clear();
522 
523  if (container_version >= 2) {
524  /* Seek to sprite section of the GRF. */
525  size_t data_offset = FioReadDword();
526  size_t old_pos = FioGetPos();
527  FioSeekTo(data_offset, SEEK_CUR);
528 
529  /* Loop over all sprite section entries and store the file
530  * offset for each newly encountered ID. */
531  uint32 id, prev_id = 0;
532  while ((id = FioReadDword()) != 0) {
533  if (id != prev_id) _grf_sprite_offsets[id] = FioGetPos() - 4;
534  prev_id = id;
536  }
537 
538  /* Continue processing the data section. */
539  FioSeekTo(old_pos, SEEK_SET);
540  }
541 }
542 
543 
552 bool LoadNextSprite(int load_index, byte file_slot, uint file_sprite_id, byte container_version)
553 {
554  size_t file_pos = FioGetPos();
555 
556  /* Read sprite header. */
557  uint32 num = container_version >= 2 ? FioReadDword() : FioReadWord();
558  if (num == 0) return false;
559  byte grf_type = FioReadByte();
560 
561  SpriteType type;
562  void *data = nullptr;
563  if (grf_type == 0xFF) {
564  /* Some NewGRF files have "empty" pseudo-sprites which are 1
565  * byte long. Catch these so the sprites won't be displayed. */
566  if (num == 1) {
567  FioReadByte();
568  return false;
569  }
570  type = ST_RECOLOUR;
571  data = ReadRecolourSprite(file_slot, num);
572  } else if (container_version >= 2 && grf_type == 0xFD) {
573  if (num != 4) {
574  /* Invalid sprite section include, ignore. */
575  FioSkipBytes(num);
576  return false;
577  }
578  /* It is not an error if no sprite with the provided ID is found in the sprite section. */
579  file_pos = GetGRFSpriteOffset(FioReadDword());
580  type = ST_NORMAL;
581  } else {
582  FioSkipBytes(7);
583  type = SkipSpriteData(grf_type, num - 8) ? ST_NORMAL : ST_INVALID;
584  /* Inline sprites are not supported for container version >= 2. */
585  if (container_version >= 2) return false;
586  }
587 
588  if (type == ST_INVALID) return false;
589 
590  if (load_index >= MAX_SPRITES) {
591  usererror("Tried to load too many sprites (#%d; max %d)", load_index, MAX_SPRITES);
592  }
593 
594  bool is_mapgen = IsMapgenSpriteID(load_index);
595 
596  if (is_mapgen) {
597  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?");
598  type = ST_MAPGEN;
599  }
600 
601  SpriteCache *sc = AllocateSpriteCache(load_index);
602  sc->file_slot = file_slot;
603  sc->file_pos = file_pos;
604  sc->ptr = data;
605  sc->lru = 0;
606  sc->id = file_sprite_id;
607  sc->type = type;
608  sc->warned = false;
609  sc->container_ver = container_version;
610 
611  return true;
612 }
613 
614 
615 void DupSprite(SpriteID old_spr, SpriteID new_spr)
616 {
617  SpriteCache *scnew = AllocateSpriteCache(new_spr); // may reallocate: so put it first
618  SpriteCache *scold = GetSpriteCache(old_spr);
619 
620  scnew->file_slot = scold->file_slot;
621  scnew->file_pos = scold->file_pos;
622  scnew->ptr = nullptr;
623  scnew->id = scold->id;
624  scnew->type = scold->type;
625  scnew->warned = false;
626  scnew->container_ver = scold->container_ver;
627 }
628 
635 static const size_t S_FREE_MASK = sizeof(size_t) - 1;
636 
637 /* to make sure nobody adds things to MemBlock without checking S_FREE_MASK first */
638 static_assert(sizeof(MemBlock) == sizeof(size_t));
639 /* make sure it's a power of two */
640 static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
641 
642 static inline MemBlock *NextBlock(MemBlock *block)
643 {
644  return (MemBlock*)((byte*)block + (block->size & ~S_FREE_MASK));
645 }
646 
647 static size_t GetSpriteCacheUsage()
648 {
649  size_t tot_size = 0;
650  MemBlock *s;
651 
652  for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
653  if (!(s->size & S_FREE_MASK)) tot_size += s->size;
654  }
655 
656  return tot_size;
657 }
658 
659 
660 void IncreaseSpriteLRU()
661 {
662  /* Increase all LRU values */
663  if (_sprite_lru_counter > 16384) {
664  SpriteID i;
665 
666  DEBUG(sprite, 3, "Fixing lru %u, inuse=" PRINTF_SIZE, _sprite_lru_counter, GetSpriteCacheUsage());
667 
668  for (i = 0; i != _spritecache_items; i++) {
669  SpriteCache *sc = GetSpriteCache(i);
670  if (sc->ptr != nullptr) {
671  if (sc->lru >= 0) {
672  sc->lru = -1;
673  } else if (sc->lru != -32768) {
674  sc->lru--;
675  }
676  }
677  }
678  _sprite_lru_counter = 0;
679  }
680 
681  /* Compact sprite cache every now and then. */
682  if (++_compact_cache_counter >= 740) {
684  _compact_cache_counter = 0;
685  }
686 }
687 
692 static void CompactSpriteCache()
693 {
694  MemBlock *s;
695 
696  DEBUG(sprite, 3, "Compacting sprite cache, inuse=" PRINTF_SIZE, GetSpriteCacheUsage());
697 
698  for (s = _spritecache_ptr; s->size != 0;) {
699  if (s->size & S_FREE_MASK) {
700  MemBlock *next = NextBlock(s);
701  MemBlock temp;
702  SpriteID i;
703 
704  /* Since free blocks are automatically coalesced, this should hold true. */
705  assert(!(next->size & S_FREE_MASK));
706 
707  /* If the next block is the sentinel block, we can safely return */
708  if (next->size == 0) break;
709 
710  /* Locate the sprite belonging to the next pointer. */
711  for (i = 0; GetSpriteCache(i)->ptr != next->data; i++) {
712  assert(i != _spritecache_items);
713  }
714 
715  GetSpriteCache(i)->ptr = s->data; // Adjust sprite array entry
716  /* Swap this and the next block */
717  temp = *s;
718  memmove(s, next, next->size);
719  s = NextBlock(s);
720  *s = temp;
721 
722  /* Coalesce free blocks */
723  while (NextBlock(s)->size & S_FREE_MASK) {
724  s->size += NextBlock(s)->size & ~S_FREE_MASK;
725  }
726  } else {
727  s = NextBlock(s);
728  }
729  }
730 }
731 
736 static void DeleteEntryFromSpriteCache(uint item)
737 {
738  /* Mark the block as free (the block must be in use) */
739  MemBlock *s = (MemBlock*)GetSpriteCache(item)->ptr - 1;
740  assert(!(s->size & S_FREE_MASK));
741  s->size |= S_FREE_MASK;
742  GetSpriteCache(item)->ptr = nullptr;
743 
744  /* And coalesce adjacent free blocks */
745  for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
746  if (s->size & S_FREE_MASK) {
747  while (NextBlock(s)->size & S_FREE_MASK) {
748  s->size += NextBlock(s)->size & ~S_FREE_MASK;
749  }
750  }
751  }
752 }
753 
754 static void DeleteEntryFromSpriteCache()
755 {
756  uint best = UINT_MAX;
757  int cur_lru;
758 
759  DEBUG(sprite, 3, "DeleteEntryFromSpriteCache, inuse=" PRINTF_SIZE, GetSpriteCacheUsage());
760 
761  cur_lru = 0xffff;
762  for (SpriteID i = 0; i != _spritecache_items; i++) {
763  SpriteCache *sc = GetSpriteCache(i);
764  if (sc->type != ST_RECOLOUR && sc->ptr != nullptr && sc->lru < cur_lru) {
765  cur_lru = sc->lru;
766  best = i;
767  }
768  }
769 
770  /* Display an error message and die, in case we found no sprite at all.
771  * This shouldn't really happen, unless all sprites are locked. */
772  if (best == UINT_MAX) error("Out of sprite memory");
773 
775 }
776 
777 static void *AllocSprite(size_t mem_req)
778 {
779  mem_req += sizeof(MemBlock);
780 
781  /* Align this to correct boundary. This also makes sure at least one
782  * bit is not used, so we can use it for other things. */
783  mem_req = Align(mem_req, S_FREE_MASK + 1);
784 
785  for (;;) {
786  MemBlock *s;
787 
788  for (s = _spritecache_ptr; s->size != 0; s = NextBlock(s)) {
789  if (s->size & S_FREE_MASK) {
790  size_t cur_size = s->size & ~S_FREE_MASK;
791 
792  /* Is the block exactly the size we need or
793  * big enough for an additional free block? */
794  if (cur_size == mem_req ||
795  cur_size >= mem_req + sizeof(MemBlock)) {
796  /* Set size and in use */
797  s->size = mem_req;
798 
799  /* Do we need to inject a free block too? */
800  if (cur_size != mem_req) {
801  NextBlock(s)->size = (cur_size - mem_req) | S_FREE_MASK;
802  }
803 
804  return s->data;
805  }
806  }
807  }
808 
809  /* Reached sentinel, but no block found yet. Delete some old entry. */
811  }
812 }
813 
817 void *SimpleSpriteAlloc(size_t size)
818 {
819  return MallocT<byte>(size);
820 }
821 
831 static void *HandleInvalidSpriteRequest(SpriteID sprite, SpriteType requested, SpriteCache *sc, AllocatorProc *allocator)
832 {
833  static const char * const sprite_types[] = {
834  "normal", // ST_NORMAL
835  "map generator", // ST_MAPGEN
836  "character", // ST_FONT
837  "recolour", // ST_RECOLOUR
838  };
839 
840  SpriteType available = sc->type;
841  if (requested == ST_FONT && available == ST_NORMAL) {
842  if (sc->ptr == nullptr) sc->type = ST_FONT;
843  return GetRawSprite(sprite, sc->type, allocator);
844  }
845 
846  byte warning_level = sc->warned ? 6 : 0;
847  sc->warned = true;
848  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]);
849 
850  switch (requested) {
851  case ST_NORMAL:
852  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?");
853  FALLTHROUGH;
854  case ST_FONT:
855  return GetRawSprite(SPR_IMG_QUERY, ST_NORMAL, allocator);
856  case ST_RECOLOUR:
857  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?");
858  return GetRawSprite(PALETTE_TO_DARK_BLUE, ST_RECOLOUR, allocator);
859  case ST_MAPGEN:
860  /* this shouldn't happen, overriding of ST_MAPGEN sprites is checked in LoadNextSprite()
861  * (the only case the check fails is when these sprites weren't even loaded...) */
862  default:
863  NOT_REACHED();
864  }
865 }
866 
876 void *GetRawSprite(SpriteID sprite, SpriteType type, AllocatorProc *allocator, SpriteEncoder *encoder)
877 {
878  assert(type != ST_MAPGEN || IsMapgenSpriteID(sprite));
879  assert(type < ST_INVALID);
880 
881  if (!SpriteExists(sprite)) {
882  DEBUG(sprite, 1, "Tried to load non-existing sprite #%d. Probable cause: Wrong/missing NewGRFs", sprite);
883 
884  /* SPR_IMG_QUERY is a BIG FAT RED ? */
885  sprite = SPR_IMG_QUERY;
886  }
887 
888  SpriteCache *sc = GetSpriteCache(sprite);
889 
890  if (sc->type != type) return HandleInvalidSpriteRequest(sprite, type, sc, allocator);
891 
892  if (allocator == nullptr && encoder == nullptr) {
893  /* Load sprite into/from spritecache */
894 
895  /* Update LRU */
896  sc->lru = ++_sprite_lru_counter;
897 
898  /* Load the sprite, if it is not loaded, yet */
899  if (sc->ptr == nullptr) sc->ptr = ReadSprite(sc, sprite, type, AllocSprite, nullptr);
900 
901  return sc->ptr;
902  } else {
903  /* Do not use the spritecache, but a different allocator. */
904  return ReadSprite(sc, sprite, type, allocator, encoder);
905  }
906 }
907 
908 
909 static void GfxInitSpriteCache()
910 {
911  /* initialize sprite cache heap */
913  uint target_size = (bpp > 0 ? _sprite_cache_size * bpp / 8 : 1) * 1024 * 1024;
914 
915  /* Remember 'target_size' from the previous allocation attempt, so we do not try to reach the target_size multiple times in case of failure. */
916  static uint last_alloc_attempt = 0;
917 
918  if (_spritecache_ptr == nullptr || (_allocated_sprite_cache_size != target_size && target_size != last_alloc_attempt)) {
919  delete[] reinterpret_cast<byte *>(_spritecache_ptr);
920 
921  last_alloc_attempt = target_size;
922  _allocated_sprite_cache_size = target_size;
923 
924  do {
925  try {
926  /* Try to allocate 50% more to make sure we do not allocate almost all available. */
927  _spritecache_ptr = reinterpret_cast<MemBlock *>(new byte[_allocated_sprite_cache_size + _allocated_sprite_cache_size / 2]);
928  } catch (std::bad_alloc &) {
929  _spritecache_ptr = nullptr;
930  }
931 
932  if (_spritecache_ptr != nullptr) {
933  /* Allocation succeeded, but we wanted less. */
934  delete[] reinterpret_cast<byte *>(_spritecache_ptr);
935  _spritecache_ptr = reinterpret_cast<MemBlock *>(new byte[_allocated_sprite_cache_size]);
936  } else if (_allocated_sprite_cache_size < 2 * 1024 * 1024) {
937  usererror("Cannot allocate spritecache");
938  } else {
939  /* Try again to allocate half. */
940  _allocated_sprite_cache_size >>= 1;
941  }
942  } while (_spritecache_ptr == nullptr);
943 
944  if (_allocated_sprite_cache_size != target_size) {
945  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);
946 
947  ErrorMessageData msg(STR_CONFIG_ERROR_OUT_OF_MEMORY, STR_CONFIG_ERROR_SPRITECACHE_TOO_BIG);
948  msg.SetDParam(0, target_size);
949  msg.SetDParam(1, _allocated_sprite_cache_size);
951  }
952  }
953 
954  /* A big free block */
955  _spritecache_ptr->size = (_allocated_sprite_cache_size - sizeof(MemBlock)) | S_FREE_MASK;
956  /* Sentinel block (identified by size == 0) */
957  NextBlock(_spritecache_ptr)->size = 0;
958 }
959 
960 void GfxInitSpriteMem()
961 {
962  GfxInitSpriteCache();
963 
964  /* Reset the spritecache 'pool' */
965  free(_spritecache);
966  _spritecache_items = 0;
967  _spritecache = nullptr;
968 
969  _compact_cache_counter = 0;
970 }
971 
977 {
978  /* Clear sprite ptr for all cached items */
979  for (uint i = 0; i != _spritecache_items; i++) {
980  SpriteCache *sc = GetSpriteCache(i);
981  if (sc->type != ST_RECOLOUR && sc->ptr != nullptr) DeleteEntryFromSpriteCache(i);
982  }
983 
985 }
986 
SpriteLoader::CommonPixel::m
uint8 m
Remap-channel.
Definition: spriteloader.hpp:38
factory.hpp
ZOOM_LVL_OUT_2X
@ ZOOM_LVL_OUT_2X
Zoomed 2 times out.
Definition: zoom_type.h:25
FioReadBlock
void FioReadBlock(void *ptr, size_t size)
Read a block.
Definition: fileio.cpp:161
usererror
void CDECL usererror(const char *s,...)
Error handling for fatal user errors.
Definition: openttd.cpp:103
ST_FONT
@ ST_FONT
A sprite used for fonts.
Definition: gfx_type.h:304
ReusableBuffer< SpriteLoader::CommonPixel >
FioReadWord
uint16 FioReadWord()
Read a word (16 bits) from the file (in low endian format).
Definition: fileio.cpp:140
mem_func.hpp
Sprite::data
byte data[]
Sprite data.
Definition: spritecache.h:22
HandleInvalidSpriteRequest
static void * HandleInvalidSpriteRequest(SpriteID sprite, SpriteType requested, SpriteCache *sc, AllocatorProc *allocator)
Handles the case when a sprite of different type is requested than is present in the SpriteCache.
Definition: spritecache.cpp:831
SpriteLoader::Sprite::AllocateData
void AllocateData(ZoomLevel zoom, size_t size)
Allocate the sprite data of this sprite.
Definition: spriteloader.hpp:61
ZOOM_LVL_END
@ ZOOM_LVL_END
End for iteration.
Definition: zoom_type.h:30
Blitter::GetScreenDepth
virtual uint8 GetScreenDepth()=0
Get the screen depth this blitter works for.
math_func.hpp
S_FREE_MASK
static const size_t S_FREE_MASK
S_FREE_MASK is used to mask-out lower bits of MemBlock::size If they are non-zero,...
Definition: spritecache.cpp:635
SpriteLoaderGrf::LoadSprite
uint8 LoadSprite(SpriteLoader::Sprite *sprite, uint8 file_slot, size_t file_pos, SpriteType sprite_type, bool load_32bpp)
Load a sprite from the disk and return a sprite struct which is the same for all loaders.
Definition: grf.cpp:330
ZOOM_LVL_COUNT
@ ZOOM_LVL_COUNT
Number of zoom levels.
Definition: zoom_type.h:32
HasBit
static bool HasBit(const T x, const uint8 y)
Checks if a bit in a value is set.
Definition: bitmath_func.hpp:103
ReadRecolourSprite
static void * ReadRecolourSprite(uint16 file_slot, uint num)
Load a recolour sprite into memory.
Definition: spritecache.cpp:386
Sprite::height
uint16 height
Height of the sprite.
Definition: spritecache.h:18
ReadGRFSpriteOffsets
void ReadGRFSpriteOffsets(byte container_version)
Parse the sprite section of GRFs.
Definition: spritecache.cpp:519
zoom_func.h
Sprite::x_offs
int16 x_offs
Number of pixels to shift the sprite to the right.
Definition: spritecache.h:20
fileio_func.h
ZoomLevel
ZoomLevel
All zoom levels we know.
Definition: zoom_type.h:21
SpriteLoader::Sprite::buffer
static ReusableBuffer< SpriteLoader::CommonPixel > buffer[ZOOM_LVL_COUNT]
Allocated memory to pass sprite data around.
Definition: spriteloader.hpp:64
_palmap_w2d
const byte _palmap_w2d[]
Converting from the Windows palette to the DOS palette.
ST_NORMAL
@ ST_NORMAL
The most basic (normal) sprite.
Definition: gfx_type.h:302
SpriteEncoder::Encode
virtual Sprite * Encode(const SpriteLoader::Sprite *sprite, AllocatorProc *allocator)=0
Convert a sprite from the loader to our own format.
DeleteEntryFromSpriteCache
static void DeleteEntryFromSpriteCache(uint item)
Delete a single entry from the sprite cache.
Definition: spritecache.cpp:736
GetSpriteType
SpriteType GetSpriteType(SpriteID sprite)
Get the sprite type of a given sprite.
Definition: spritecache.cpp:132
VideoDriver::ClearSystemSprites
virtual void ClearSystemSprites()
Clear all cached sprites.
Definition: video_driver.hpp:108
MemCpyT
static void MemCpyT(T *destination, const T *source, size_t num=1)
Type-safe version of memcpy().
Definition: mem_func.hpp:23
grf.hpp
ZOOM_LVL_BEGIN
@ ZOOM_LVL_BEGIN
Begin for iteration.
Definition: zoom_type.h:23
FioReadDword
uint32 FioReadDword()
Read a double word (32 bits) from the file (in low endian format).
Definition: fileio.cpp:150
ST_INVALID
@ ST_INVALID
Pseudosprite or other unusable sprite, used only internally.
Definition: gfx_type.h:306
IsInsideMM
static bool IsInsideMM(const T x, const size_t min, const size_t max)
Checks if a value is in an interval.
Definition: math_func.hpp:204
SpriteID
uint32 SpriteID
The number of a sprite, without mapping bits and colourtables.
Definition: gfx_type.h:17
gfx_func.h
SpriteLoader::Sprite::data
SpriteLoader::CommonPixel * data
The sprite itself.
Definition: spriteloader.hpp:54
FioSkipBytes
void FioSkipBytes(int n)
Skip n bytes ahead in the file.
Definition: fileio.cpp:124
Align
static T Align(const T x, uint n)
Return the smallest multiple of n equal or greater than x.
Definition: math_func.hpp:35
SpriteCache::warned
bool warned
True iff the user has been warned about incorrect use of this sprite.
Definition: spritecache.cpp:38
MAX_SPRITES
@ MAX_SPRITES
Maximum number of sprites that can be loaded at a given time.
Definition: sprites.h:1543
SpriteLoader::Sprite::type
SpriteType type
The sprite type.
Definition: spriteloader.hpp:52
GfxClearSpriteCache
void GfxClearSpriteCache()
Remove all encoded sprites from the sprite cache without discarding sprite location information.
Definition: spritecache.cpp:976
SpriteEncoder::GetSpriteAlignment
virtual uint GetSpriteAlignment()
Get the value which the height and width on a sprite have to be aligned by.
Definition: spriteloader.hpp:101
DEBUG
#define DEBUG(name, level,...)
Output a line of debugging information.
Definition: debug.h:35
SkipSpriteData
bool SkipSpriteData(byte type, uint16 num)
Skip the given amount of sprite graphics data.
Definition: spritecache.cpp:95
GetGRFSpriteOffset
size_t GetGRFSpriteOffset(uint32 id)
Get the file offset for a specific sprite in the sprite section of a GRF.
Definition: spritecache.cpp:510
SpriteLoader::CommonPixel
Definition of a common pixel in OpenTTD's realm.
Definition: spriteloader.hpp:33
BlitterFactory::GetCurrentBlitter
static Blitter * GetCurrentBlitter()
Get the current active blitter (always set by calling SelectBlitter).
Definition: factory.hpp:141
safeguards.h
Sprite::width
uint16 width
Width of the sprite.
Definition: spritecache.h:19
_grf_sprite_offsets
static std::map< uint32, size_t > _grf_sprite_offsets
Map from sprite numbers to position in the GRF file.
Definition: spritecache.cpp:503
SpriteLoader::Sprite::x_offs
int16 x_offs
The x-offset of where the sprite will be drawn.
Definition: spriteloader.hpp:50
SpriteLoaderGrf
Sprite loader for graphics coming from a (New)GRF.
Definition: grf.hpp:16
settings_type.h
ErrorMessageData
The data of the error message.
Definition: error.h:29
sprites.h
error.h
SpriteEncoder
Interface for something that can encode a sprite.
Definition: spriteloader.hpp:82
UnScaleByZoom
static int UnScaleByZoom(int value, ZoomLevel zoom)
Scale by zoom level, usually shift right (when zoom > ZOOM_LVL_NORMAL) When shifting right,...
Definition: zoom_func.h:34
stdafx.h
FioSeekTo
void FioSeekTo(size_t pos, int mode)
Seek in the current file.
Definition: fileio.cpp:79
VideoDriver::GetInstance
static VideoDriver * GetInstance()
Get the currently active instance of the video driver.
Definition: video_driver.hpp:199
SpriteLoader::Sprite::colours
SpriteColourComponent colours
The colour components of the sprite with useful information.
Definition: spriteloader.hpp:53
SpriteCache
Definition: spritecache.cpp:31
FioGetPos
size_t FioGetPos()
Get position in the current file.
Definition: fileio.cpp:59
LoadNextSprite
bool LoadNextSprite(int load_index, byte file_slot, uint file_sprite_id, byte container_version)
Load a real or recolour sprite.
Definition: spritecache.cpp:552
FioReadByte
byte FioReadByte()
Read a byte from the file.
Definition: fileio.cpp:107
palette_convert.h
SpriteEncoder::Is32BppSupported
virtual bool Is32BppSupported()=0
Can the sprite encoder make use of RGBA sprites?
SpriteLoader::Sprite::width
uint16 width
Width of the sprite.
Definition: spriteloader.hpp:49
ScaleByZoom
static int ScaleByZoom(int value, ZoomLevel zoom)
Scale by zoom level, usually shift left (when zoom > ZOOM_LVL_NORMAL) When shifting right,...
Definition: zoom_func.h:22
GetRawSprite
void * GetRawSprite(SpriteID sprite, SpriteType type, AllocatorProc *allocator, SpriteEncoder *encoder)
Reads a sprite (from disk or sprite cache).
Definition: spritecache.cpp:876
video_driver.hpp
GetMaxSpriteID
uint GetMaxSpriteID()
Get a reasonable (upper bound) estimate of the maximum SpriteID used in OpenTTD; there will be no spr...
Definition: spritecache.cpp:187
CompactSpriteCache
static void CompactSpriteCache()
Called when holes in the sprite cache should be removed.
Definition: spritecache.cpp:692
SpriteCache::type
SpriteType type
In some cases a single sprite is misused by two NewGRFs. Once as real sprite and once as recolour spr...
Definition: spritecache.cpp:37
SpriteType
SpriteType
Types of sprites that might be loaded.
Definition: gfx_type.h:301
ScheduleErrorMessage
void ScheduleErrorMessage(const ErrorMessageData &data)
Schedule an error.
Definition: error_gui.cpp:447
GetSpriteLocalID
uint32 GetSpriteLocalID(SpriteID sprite)
Get the GRF-local sprite id of a given sprite.
Definition: spritecache.cpp:154
Sprite::y_offs
int16 y_offs
Number of pixels to shift the sprite downwards.
Definition: spritecache.h:21
ReallocT
static T * ReallocT(T *t_ptr, size_t num_elements)
Simplified reallocation function that allocates the specified number of elements of the given type.
Definition: alloc_func.hpp:111
SpriteLoader::Sprite
Structure for passing information from the sprite loader to the blitter.
Definition: spriteloader.hpp:47
_palette_remap_grf
bool _palette_remap_grf[]
Whether the given NewGRFs must get a palette remap from windows to DOS or not.
Definition: gfxinit.cpp:30
error
void CDECL error(const char *s,...)
Error handling for fatal non-user errors.
Definition: openttd.cpp:132
ReadSprite
static void * ReadSprite(const SpriteCache *sc, SpriteID id, SpriteType sprite_type, AllocatorProc *allocator, SpriteEncoder *encoder)
Read a sprite from disk.
Definition: spritecache.cpp:422
SetBit
static T SetBit(T &x, const uint8 y)
Set a bit in a variable.
Definition: bitmath_func.hpp:121
SpriteCache::container_ver
byte container_ver
Container version of the GRF the sprite is from.
Definition: spritecache.cpp:39
MemSetT
static void MemSetT(T *ptr, byte value, size_t num=1)
Type-safe version of memset().
Definition: mem_func.hpp:49
ZOOM_LVL_NORMAL
@ ZOOM_LVL_NORMAL
The normal zoom level.
Definition: zoom_type.h:24
ST_RECOLOUR
@ ST_RECOLOUR
Recolour sprite.
Definition: gfx_type.h:305
SpriteLoader::Sprite::y_offs
int16 y_offs
The y-offset of where the sprite will be drawn.
Definition: spriteloader.hpp:51
SpriteLoader::Sprite::height
uint16 height
Height of the sprite.
Definition: spriteloader.hpp:48
GetOriginFileSlot
uint GetOriginFileSlot(SpriteID sprite)
Get the (FIOS) file slot of a given sprite.
Definition: spritecache.cpp:143
free
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: stdafx.h:456
SimpleSpriteAlloc
void * SimpleSpriteAlloc(size_t size)
Sprite allocator simply using malloc.
Definition: spritecache.cpp:817
FIND_FIRST_BIT
#define FIND_FIRST_BIT(x)
Returns the first non-zero bit in a 6-bit value (from right).
Definition: bitmath_func.hpp:200
Sprite
Data structure describing a sprite.
Definition: spritecache.h:17
MemBlock
Definition: spritecache.cpp:76
ST_MAPGEN
@ ST_MAPGEN
Special sprite for the map generator.
Definition: gfx_type.h:303
_palmap_d2w
static const byte _palmap_d2w[]
Converting from the DOS palette to the Windows palette.
Definition: palette_convert.h:47
GetSpriteCountForSlot
uint GetSpriteCountForSlot(uint file_slot, SpriteID begin, SpriteID end)
Count the sprites which originate from a specific file slot in a range of SpriteIDs.
Definition: spritecache.cpp:167
AllocaM
#define AllocaM(T, num_elements)
alloca() has to be called in the parent function, so define AllocaM() as a macro
Definition: alloc_func.hpp:132