src/apc/ir.h

   1 /*!@file
   2   \brief   Intermediate Representation (IR) between Directory Structure and Engine Grammar
   3   \details The IR serves as a storage structure that is populated during the
   4            parsing of the input directory structure. After parsing is complete,
   5            the IR will be condensed (removed of excess allocated space) and then
   6            output as the Engine Grammar. In this file we describe the semantic actions
   7            that are called at each step, and the memory buffers that they populate.
   8            See parser.y for the description on how the input grammar is constructed,
   9            and where/when semantic actions are called.
  10            TODO: or just write it here.
  11   \author  Jordan Lavatai
  12   \date    Aug 2016
  13   ----------------------------------------------------------------------------*/
  14
  15
  16 #include <stdint.h>
  17 //#include <apc/mem.h>TODO:
  18
  19 #define BUF_SIZE 256
  20 #define MAX_SETS 256
  21 #define MAX_ELES 256
  22 #define MAX_QUADS 256
  23 #define MAX_MODELS 256
  24 #define MAX_POSTS 256
  25 #define MAX_CLASS_DEPTH 256
  26 #define MAX_CLASSES 256
  27 #define MAX_FRAMES 256
  28 /*  All bufs are of pointers to their respective structs. When a buf is full */
  29 /*  (number of data structs pointers >= max number of data struct pointers),        */
  30 /*  we need to allocate a more pointers for that buf. Allocate these       */
  31 /*  pointers a page at a time (1024 = Page bytes (4096)/bytes per pointer(4))   */
  32 /*  TODO: Account for different page sizes in different system                  */
  33 #define PTRS_IN_PAGE 1024
  34
  35 /*  General: All information from the directory structure is stored in        */
  36 /*  five buffers that comprise the IR: cdat_buf, odat_buf, vdat_buf, ref_buf  */
  37 /*  and link_buf. Each buf corresponds to the data structure that it stores.  */
  38 /*  The storage techique for all bufs (except cdat) is the same. Each bufs member first */
  39 /*  populates its struct and then allocates the space for the next member     */
  40 /*  and increments the buf index. This means that we have to allocate the     */
  41 /*  very first member of each buf at ir_init(), so that we don't segfault     */
  42 /*  as the first member attempts to access memory that its previous member    */
  43 /*  didn't allocate (because it doesnt exist). We access the buf members      */
  44 /*  through standard array indexing but conceal the tediousness of array      */
  45 /*  indexing with macros. E.g. without macros, acessing an elements name      */
  46 /*  member would look like (split up to not go over line char limit):         */
  47 /*  (*cdat_stackp)->set_list[(*cdat_stackp)->num_sets] */
  48 /*     .ele_list[(*cdat_stackp)->set_list[(*cdat_stackp->num_sets)].num_ele].name */
  49
  50 /* For cdats in cdat_buf, we allocate the memory for a cdat once a cdat
  51    is recognized in the grammar. Cdat_buf is different from the other bufs
  52    because cdats have a root cdat that all cdats are a subclass of. This root
  53    cdat can have a set_list like other cdats.                                */
  54
  55
  56
  57
  58 /*  Elements: Ele stands for element and has two representations in the IR.   */
  59 /*  In the cdat_buf eles store their name, cdat_idx (their classes index in   */
  60 /*  the cdat_buf) and the ref_id (refer to ref ). In the odat_buf, eles store */
  61 /*  their object data (odat). At output time, the ref_id is dereferenced to   */
  62 /*  determine the elements odat which is the data that the engine expects     */
  63 /*  from an element.                                                          */
  64
  65 struct ele {
  66   char name[32];
  67   uint64_t ref_id;
  68   int cdat_idx;
  69 };
  70
  71 /*  Sets: The set is similar to the ele, but it contains a list of its    */
  72 /*  elements. The set is populated at parse time AFTER the elements are   */
  73 /*  populated, due to the nature of bottom up parsing.                    */
  74
  75 struct set {
  76   char name[32];
  77   uint64_t ref_id;
  78   int cdat_idx;
  79   int num_ele;
  80   struct ele ele_list[MAX_ELES];
  81 };
  82
  83 /*  Cdats: A cdat is a class data structure. Cdats serve as the central       */
  84 /*  data types of the IR. At output, the cdat_buf is iterated through and     */
  85 /*  each is written to the output file. For each cdat, sets and element       */
  86 /*  ref_ids must be dereferenced to determine the odat information. Cdats     */
  87 /*  contain pointers to their subclasses so that the relationship between     */
  88 /*  classes can be determined, but the subclasses are not represented inside  */
  89 /*  of the cdat itself but rather in the subsequent cdats in cdat_buf. We     */
  90 /*  can determine the number of subclasses (the last index into cdat_buf      */
  91 /*  that represents a subclass of some arbitrary cdat) each cdat has by       */
  92 /*  incrementing num_classes during parse time.                               */
  93 /*  TODO: Should classes point to their parent class?                         */
  94
  95 struct cdat {
  96   char name[32];
  97   int idx;
  98   int num_classes;
  99   int num_sets;
 100   struct cdat* class_list[MAX_CLASSES];
 101   struct set set_list[MAX_SETS];
 102 };
 103
 104 /* There are an unknown amount of cdats at compile time, so we maintain    */
 105 /*   a cdat_buf of cdat pointers that can be expanded as needed.           */
 106 struct cdat* cdat_buf[PTRS_IN_PAGE];
 107
 108 /* The cdat_stack is a stack pointers to cdat pointers, the top of which is
 109    the cdat that is currently being parsed. Whenever a new cdat is recognized
 110    by the grammar (CLOPEN), a cdat is pushed onto the cdat_stack, and we refer
 111    to this cdat through the macro CURR_CDAT. By keeping a cdat_stack, we have
 112    access to the current cdat so that the elements and sets can populate themselves
 113    in the cdat accordingly. */
 114
 115 struct cdat* cdat_stack[PTRS_IN_PAGE];
 116 struct cdat** cdat_stackp;
 117
 118 /* Refs: Each set/ele has a reference to its object data (odat) through a ref_id.
 119    Ref_ids are unsigned 64 byte integers that map to the hex values RGBA. During
 120    the construction of the directory structure, users can choose a RGBA value for
 121    each object that any other object can refer to via links (see link). If a user
 122    does not choose an RGBA value, then the object is given one from the system space.
 123    We maintain a doubly linked list of refs in the ref_buf at parse time so that
 124    links can be resolved after the parsing of the directory structure is complete.
 125    For every 16th ref, we create a post so that we can reduce on the search time for
 126    a random access. */
 127
 128 struct ref {
 129   int type;
 130   struct ref* nextref;
 131   struct ref* lastref;
 132   struct odat* odatp;
 133   uint64_t ref_id; //0xFFFFFF->digit
 134 };
 135
 136 /* Like the cdat_buf, ref_buf stores pointers to refs and can
 137    increase in size */
 138 struct ref* ref_buf[PTRS_IN_PAGE];
 139
 140 /* posts for ref_buf */
 141 struct ref* post_buf[PTRS_IN_PAGE];
 142
 143 /* Links: At parse time, a set/ele can include a link in their
 144    grammar representation instead of the actual data and this signifies
 145    to the APC that that set/ele wishes to use the data of another
 146    set/ele, either its video data (vdat) or object data (odat). The link
 147    itself contains the type of link it is, the ref_id OR name, and
 148    which set/ele created the link. During parse time, links can be made
 149    to o/vdats that have yet to be parsed. In order to accomodate for this,
 150    we resolve all links AFTER parse time by iterating through the link_buf,
 151    finding the ref_id that was stored for some object (if the ref_id exists),
 152    and creating a relative pointer from the original object to the data that
 153    was linked */
 154
 155 /* Svlinks stand for short vlink, which is a link to a vdat
 156    TODO: diff btwn vlink*/
 157
 158 struct svlink {
 159   uint64_t ref_id;
 160 };
 161
 162 /* A vlink is what it sounds like, a link to a vdat
 163  TODO: model link? */
 164 struct vlink {
 165   uint64_t ref_id;
 166   char anim_name[32];
 167 };
 168
 169 /* Olinks are links to odats */
 170 struct olink {
 171   uint64_t ref_id;
 172 };
 173
 174 union link_t {
 175   struct olink olink;
 176   struct vlink vlink;
 177   struct svlink svlink;
 178 };
 179
 180 struct link {
 181   int type; //1 = olink, 2 = vlink, 3 = svlink
 182   union link_t link_t;
 183   int cdat_idx;
 184   int set_idx;
 185   int ele_idx;
 186 };
 187 /* link_buf contains all the links that
 188    we encountered during parse time that need
 189    to be resolved to an offset at output time.
 190    This does not include quad refs, because
 191    those are already known to need to be resolved */
 192 struct link* link_buf[PTRS_IN_PAGE];
 193
 194
 195 /* Odats: Odats consist of the object data necessary for
 196    each object. Odats are sometimes referred to as archetypes
 197    at compile-time, in order to distinguish the difference from
 198    a runtime object and a compile-time object.
 199    TODO: Need more info about objects at runtime, to described
 200          the reasoning behind odat structure at compile-time*/
 201
 202 /* Each set has a quad_list or a list of quads. The quad_list
 203    is the ? */
 204 struct quad {
 205   int x, y, z;
 206   uint64_t ref_id; //rgba
 207 };
 208
 209 struct root {
 210   int x, y, z;
 211 };
 212
 213 struct odat {
 214   char name[32];
 215   int vdat_id;
 216   int cdat_idx;
 217   int hitbox;
 218   struct root root;
 219   struct ref* refp; /* pointer to it's ref on ref_list */
 220   int num_quads;
 221   struct quad quad_list[MAX_QUADS];
 222 };
 223
 224 /* Populated and allocated same way as other bufs */
 225 struct odat* odat_buf[PTRS_IN_PAGE];
 226
 227 /* A framesheet is a grouping of animation frames in
 228    a single direction (N,W,S,E) */
 229 struct framesheet {
 230   int width;
 231   int height;
 232   int num_frames;
 233   void* frames[MAX_FRAMES];
 234 };
 235
 236 /* A model is a collection of framesheets for every
 237    direction (N,W,S,E,NW,NE,SW,SE)*/
 238 /* NAMED spritesheet */
 239 struct model {
 240   char name[32];
 241   struct framesheet spritesheet[8]; //one for each
 242 };
 243
 244 /* Vdat: Vdats are the video data of each object. They can not be
 245    created as a stand alone object (because they consist solely
 246    of animation information and not the skeleton on which the
 247    animation manipulates). Vdats have a list of models for every
 248    animation that the vdats odat can do for that vdat*/
 249 struct vdat {
 250   struct odat* creator; //pointer to odat that made this vdat
 251   int num_models;
 252   struct model model_list[MAX_MODELS];
 253 };
 254
 255
 256 struct vdat* vdat_buf[PTRS_IN_PAGE];
 257
 258 /* The initalization function of the IR. Mallocs the
 259    first c/v/odat and the first links and refs and
 260    inits the cdat_stack */
 261 void
 262 ir_init(void);
 263
 264 /* mallocs memory for a new cdat. If the cdat_buf
 265    is full, mallocs another 1024 cdat pointers. */
 266 void
 267 malloc_cdat(void);
 268
 269 /* Called after the cdat open operator has been recognized in grammar. Allocates
 270    the space for a cdat on the cdat_buf, pushes that pointer onto
 271    the cdat_stack */
 272 void
 273 push_cdat(char*);
 274
 275 /* Called after a cdat end operator has been recognized in grammar. Sets
 276    top stack cdat ** to null and decrements stack pointer */
 277 void
 278 pop_cdat(void);
 279
 280 /* Called after an odat has been populated. Allocates memory for
 281    the next odat. */
 282 void
 283 inc_odat(void);
 284
 285 /* Called after an vdat has been populated. Allocates memory for
 286    the next vdat. */
 287 void
 288 inc_vdat(void);
 289
 290 void
 291 inc_link(void);
 292
 293 void
 294 inc_ref(void);
 295
 296 /* Called in the reduction of a set. While both odats (eles and sets)
 297    have identical label terminals, we are unable to give a single grammatical rule
 298    for both due to how we allocate odats in the odat buf. Due to the
 299    nature of bottom up parsing, all the elements will be inserted into the
 300    odat_buf first, and then the set that contains these element is inserted. Since
 301    the sets label comes before the element list in the grammar, we would be giving an element
 302    a set label in its respective odat, which would then be replaced by the
 303    elements label. Instead, we store the label in the sets representation inside
 304    CURR_CDAT and after we are done parsing the element_list and know that the CURR_ODAT
 305    is the set, we populate the sets label members in CURR_ODAT with the values we stored
 306    previously in CURR_CDAT. */
 307 void
 308 insert_set_label(char*, uint64_t);
 309
 310 /* Populate the sets representation in CURR_CDAT with a ref_id and insert a link
 311    into the link_buf that will resolve the ref_id to an actual odat after parse time. */
 312 void
 313 insert_set_olink(uint64_t);
 314
 315 /* Put the vlink in the link_buf to be processed after parsetime */
 316 void
 317 insert_set_vlink(uint64_t, char*);
 318
 319 /* Put svlink in the link_buf to be processed after parsetime */
 320 void
 321 insert_set_svlink(uint64_t);
 322
 323 /* Called for every set reduction except for sets with olinks. Populates the
 324    set data structures in the CDAT and in the ODAT. Uses the name and ref_id
 325    from insert_set_label. Also inserts a ref into the ref_buf with the CURR_ODAT
 326    pointer so that we can also resolve the odat from its ref_id. */
 327 void
 328 insert_set(void);
 329
 330 /* Insertion of eles is practically equivalent to how sets are inserted because both
 331    share the same data type (ODAT). Like sets, eles have links, labels
 332    and odats. Eles have the added notion of a parent set, and so must be inserted
 333    into said parent set, but this is the only place they truly differ from sets. */
 334
 335 void
 336 insert_ele_label(char*, uint64_t);
 337
 338 void
 339 insert_ele_olink(uint64_t);
 340
 341 void
 342 insert_ele_vlink(uint64_t, char*);
 343
 344 void
 345 insert_ele_svlink(uint64_t);
 346
 347 void
 348 insert_ele(void);
 349
 350 /* Created as a seperate function, instead of setting the ODATS vdat_id and
 351    calling inc_vdat() inside of insert_set(), to account for the set reduction
 352    where a vdat is not created (o/v/svlinks). Because insert_set/ele is always
 353    called before insert_vdat, and thus increments the CURR_ODAT to be the next
 354    ODAT to be populated, insert_vdat() targets the last ODAT that was populated,
 355    via PREV_ODAT. */
 356 void
 357 insert_vdat(void);
 358
 359 /* Inserts the hitbox into the CURR_ODAT */
 360 void
 361 insert_hitbox(int);
 362
 363 /* Inserts the root into the CURR_ODAT */
 364 void
 365 insert_root(int, int, int);
 366
 367 /* Inserts a quad into the CURR_ODAT */
 368 void
 369 insert_quad(int, int, int, uint64_t);
 370
 371 void
 372 insert_model(void);
 373
 374 void
 375 insert_framesheet(char, char*, uint64_t, int, int, int);
 376
 377 void
 378 insert_frame_pointer(char, void*);
 379