src/ir.c

   1 /*!@file
   2   \brief   IR Memory Implementation
   3   \details Intermediary memory management
   4   \author  Jordan Lavatai
   5   \date    Aug 2016
   6   ----------------------------------------------------------------------------*/
   7 /* Standard */
   8 #include <stdlib.h> //exit, malloc
   9 #include <stdio.h>  //print
  10 #include <stdarg.h> //va_args
  11 #include <stdint.h> //uint64_t
  12 #include <string.h> //memset, str*
  13 /* Unicode */
  14 #include <unistd.h>   //u8_* functions
  15 #include <unitypes.h> //uint8_t as a char
  16 #include <unistr.h>   //u32_cpy
  17 #include <unistdio.h> //ulc_fprintf
  18 /* Local */
  19 #include "print.h"
  20 #include "apc.h"
  21 #include "ir.h"
  22 #undef  do_error
  23 #define do_error(...) exit(-1)
  24 #define XXH_PRIVATE_API
  25 #include "../xxHash/xxhash.h"
  26 /* Public */
  27 int      ir_init(void);
  28 void     ir_quit(void);
  29 void     ir_test(void);
  30 int      ir_linker(void);
  31 int      ir_condenser(void);
  32 /* Memory allocation structures */
  33 struct pagenode_t;
  34 struct pagenode_header_t {
  35   struct pagenode_t* next;
  36   char*              head;
  37 };
  38 struct pagenode_t {
  39   struct pagenode_header_t header;
  40   char                     root[];
  41 };
  42 struct pagelist_t {
  43   struct pagenode_t* root, * head;
  44   size_t             pagesize;
  45 };
  46 #define SYS_PAGESIZE     (sys_pagesize)
  47 #define NAME_PAGESIZE    (APC_NAME_MAX * 1024)
  48 #define PL_HEADERSIZE    (sizeof(struct pagenode_header_t))
  49 #define PL_HEADSIZE(_PL) (_PL.head->header.head - _PL.head->root)
  50 #define PL_HEADMEM(_PL)  (_PL.pagesize - PL_HEADERSIZE - PL_HEADSIZE(_PL))
  51 /* Set data mem */
  52 enum dtype { FSDAT, MSDAT, ADAT, LDAT, FBDAT };
  53 struct ir_namelist_t;
  54 struct ir_namelist_t
  55 { struct ir_namelist_t* nextsib;
  56   uint8_t*              name;
  57 };
  58 struct ir_classld_t
  59 { struct ir_class_t*    root_class;
  60   struct ir_namelist_t* namelist, * namelist_head;
  61 };
  62 struct ir_setld_t
  63 { struct ir_classld_t*  classld;
  64   long long             ref;
  65   struct ir_namelist_t* namelist, * namelist_head;
  66 };
  67 struct ir_setdata_header_t
  68 { enum dtype          type;
  69   uint8_t*            src_filename, * data_name;
  70   union ir_setdata_t* nextsib;
  71 };
  72 struct ir_frameinfo_t
  73 { int facing, w, h; };
  74 struct ir_framedata_t
  75 { struct ir_setdata_header_t header;
  76   struct ir_frameinfo_t      frameinfo;
  77 };
  78 struct ir_framebox_t
  79 { struct ir_setdata_header_t header;
  80   struct ir_framedata_t      framesheets[FACING_MAX];
  81   struct ir_framedata_t      mapsheets[FACING_MAX];
  82 };
  83 struct ir_simplex_t { struct ir_setdata_header_t header; };
  84 struct ir_link_t
  85 { struct ir_setdata_header_t header;
  86   struct ir_classld_t*       classld;
  87   struct ir_setld_t*         setld;
  88   enum ltype                 type;
  89 };
  90 union ir_setdata_t
  91 { struct ir_setdata_header_t  header;
  92   struct ir_framebox_t        framebox;
  93   struct ir_framedata_t       framesheet;
  94   struct ir_framedata_t       mapsheet;
  95   struct ir_simplex_t         audio;
  96   struct ir_link_t            link;
  97 };
  98 struct ir_class_t
  99 { struct ir_class_t* nextchild, * nextsib;
 100   struct ir_set_t*   root_set;
 101   uint8_t*           name;
 102 };
 103 struct ir_set_t
 104 { struct ir_set_t*      nextchild, * nextsib;
 105   struct ir_class_t*    class;
 106   uint32_t              ref;
 107   uint8_t*              name;
 108   struct ir_framebox_t* frameboxes;
 109   struct ir_simplex_t*  audio;
 110   struct ir_link_t*     links;
 111 };
 112 /* Functions */
 113 static inline
 114 struct ir_framebox_t* ir_set_add_framebox(struct ir_set_t*,const uint8_t*);
 115 static inline
 116 union ir_setdata_t*   ir_framedata (enum dtype,const uint8_t*,apc_facing,int,int);
 117 static inline
 118 int      bytes_identical(const uint8_t*,const uint8_t*);
 119 static inline
 120 int      classnames_identical(const uint8_t*,const uint8_t*);
 121 static
 122 void*    stack_alloc(size_t);
 123 #define  struct_alloc(_T) ((struct _T*) stack_alloc(sizeof(struct _T)))
 124 static
 125 uint8_t* name_alloc(const uint8_t*);
 126 static
 127 uint8_t* classname_alloc(const uint8_t*);
 128 static inline
 129 void*    pagelist_pop(struct pagelist_t*,size_t);
 130 #define  pagelist_alloc(pagelist) do {                                  \
 131     pagelist.head->header.next = (struct pagenode_t*) calloc(pagelist.pagesize,1); \
 132     if (pagelist.head->header.next == NULL)                             \
 133       eprintf("Memory allocation error\n");                             \
 134     pagelist.head = pagelist.head->header.next;                         \
 135     pagelist.head->header.head = pagelist.head->root;                   \
 136   } while (0)
 137 #define  pagelist_init(pagelist,size) do {                      \
 138     pagelist.pagesize = size;                                   \
 139     pagelist.root = (struct pagenode_t*) calloc(size,1);        \
 140     if (pagelist.root == NULL)                                  \
 141       eprintf("Memory allocation error\n");                     \
 142     pagelist.root->header.head = pagelist.root->root;           \
 143     pagelist.head = pagelist.root;                              \
 144   } while (0)
 145 static
 146 void     pagenode_free(struct pagenode_t*);
 147 #define  REFHASH(ref) (XXH32(&ref, sizeof(uint32_t), 0xCEED) & 0xCFF)
 148
 149 extern //apc.c
 150 long     sys_pagesize;
 151 static
 152 struct pagelist_t datapages, namepages, refhashpages;
 153 static
 154 struct ir_class_t root_class = { .name = (uint8_t*)"." };
 155
 156 /* Init */
 157 int ir_init
 158 ( void )
 159 { pagelist_init(datapages, (size_t)SYS_PAGESIZE);
 160   pagelist_init(namepages, (size_t)NAME_PAGESIZE);
 161   pagelist_init(refhashpages, (size_t)SYS_PAGESIZE);
 162   return 0;
 163 }
 164
 165 /* Quit/Cleanup */
 166 void ir_quit
 167 ( void )
 168 { pagenode_free(datapages.root);
 169   pagenode_free(namepages.root);
 170   pagenode_free(refhashpages.root);
 171 }
 172
 173 /* Recursively clean pagenode linked list, freeing last first */
 174 static
 175 void pagenode_free
 176 ( struct pagenode_t* pagenode )
 177 { if (pagenode->header.next != NULL)
 178     pagenode_free(pagenode->header.next);
 179   free(pagenode);
 180 }
 181
 182 /* Link */
 183 int ir_linker
 184 ( void )
 185 {
 186   return 0;
 187 }
 188
 189 /* Condense */
 190 int ir_condenser
 191 ( void )
 192 { return 0; }
 193
 194 /* Return the class's name string */
 195 uint8_t* ir_class_name
 196 ( struct ir_class_t* class )
 197 { return class->name; }
 198
 199 /* Return a pointer to the root class */
 200 struct ir_class_t* ir_class_root
 201 ( void )
 202 { return &root_class; }
 203
 204 /* Add a subclass to a class
 205    Attempts to create a new subclass in the provided class, returning
 206    the class if it already exists
 207 */
 208 struct ir_class_t* ir_class_addchild
 209 ( struct ir_class_t* class,
 210   const uint8_t*     name
 211 )
 212 { struct ir_class_t* iter;
 213   if (class->nextchild == NULL)
 214     goto alloc;
 215   iter = class->nextchild;
 216   if (iter->name == NULL)
 217     eprintf("Null name pointer in class %p\n", iter);
 218   if (name == NULL)
 219     eprintf("Null child added to class %s\n", iter->name);
 220  check:
 221   if (classnames_identical(iter->name, name))
 222     return iter;
 223   if (iter->nextsib != NULL)
 224     { iter = iter->nextsib;
 225       goto check;
 226     }
 227  alloc:
 228   iter = struct_alloc(ir_class_t);
 229   iter->nextsib = class->nextchild;
 230   iter->name = classname_alloc(name);
 231   return class->nextchild = iter;
 232 }
 233
 234 /* Add a set to a class
 235    Attempts to create a new root set in the specified class, returning
 236    the set if it already exists
 237 */
 238 struct ir_set_t* ir_class_addset
 239 ( struct ir_class_t* class,
 240   const uint8_t*     name
 241 )
 242 { struct ir_set_t* iter;
 243   if (class->root_set == NULL)
 244     goto alloc;
 245   iter = class->root_set;
 246   if (iter->name == NULL)
 247     eprintf("Null name pointer in class %p\n", iter);
 248   if (name == NULL)
 249     eprintf("Null set added to class %U\n", iter->name);
 250  check:
 251   if (bytes_identical(iter->name, name))
 252     return iter;
 253   if (iter->nextsib != NULL)
 254     { iter = iter->nextsib;
 255       goto check;
 256     }
 257  alloc:
 258   iter = struct_alloc(ir_set_t);
 259   iter->nextsib = class->root_set;
 260   iter->name = name_alloc(name);
 261   return class->root_set = iter;
 262 }
 263
 264 struct ir_set_t* ir_set_from_ref
 265 ( uint32_t ref )
 266 { uint16_t hash;
 267   struct ir_set_t** iters;
 268   struct pagenode_t* iterp;
 269   iterp = refhashpages.root;
 270   hash = REFHASH(ref);
 271   do
 272     iters = ((struct ir_set_t**) iterp->root) + hash;
 273   while (*iters != NULL && (*iters)->ref != ref && (iterp = iterp->header.next) != NULL);
 274   return *iters;
 275 }
 276
 277
 278 /* Add a set to a set
 279    Attempts to create a new subset of the specified set, returning the
 280    child if it already exists
 281 */
 282 struct ir_set_t* ir_set_addchild
 283 ( struct ir_set_t* set,
 284   const uint8_t*   name
 285 )
 286 { struct ir_set_t* iter;
 287   if (set->nextchild == NULL)
 288     goto alloc;
 289   iter = set->nextchild;
 290   if (iter->name == NULL)
 291     eprintf("Null name pointer in set %p\n", iter);
 292   if (name == NULL)
 293     eprintf("Null child added to set %s\n", iter->name);
 294  check:
 295   if (bytes_identical(iter->name, name))
 296     return iter;
 297   if (iter->nextsib != NULL)
 298     { iter = iter->nextsib;
 299       goto check;
 300     }
 301  alloc:
 302   iter = struct_alloc(ir_set_t);
 303   iter->nextsib = set->nextchild;
 304   iter->name = name_alloc(name);
 305   return set->nextchild = iter;
 306 }
 307
 308 /* Add a framebox to a set
 309    Attempts to create a new framebox of the specified set, returning
 310    the framebox if it already exists
 311 */
 312 static inline
 313 struct ir_framebox_t* ir_set_add_framebox
 314 ( struct ir_set_t* set,
 315   const uint8_t*   name
 316 )
 317 { struct ir_framebox_t* iter;
 318   if (set->frameboxes == NULL)
 319     goto alloc;
 320   iter = set->frameboxes;
 321  check:
 322   if (bytes_identical(iter->header.data_name, name))
 323     return iter;
 324   if (iter->header.nextsib != NULL)
 325     { iter = (struct ir_framebox_t*) iter->header.nextsib;
 326       goto check;
 327     }
 328  alloc:
 329   iter = struct_alloc(ir_framebox_t);
 330   iter->header.nextsib = (union ir_setdata_t*) set->frameboxes;
 331   iter->header.data_name = name_alloc(name);
 332   return set->frameboxes = iter;
 333 }
 334
 335 /* Match two null-terminated bytestrings
 336    Return 1 if the two bytestrings are identical, else 0
 337 */
 338 static inline
 339 int bytes_identical
 340 ( const uint8_t* stra,
 341   const uint8_t* strb
 342 )
 343 { int ca, cb;
 344   do {
 345     ca = *stra++;
 346     cb = *strb++;
 347   } while (ca && ca != '_' && ca == cb);
 348   return (ca == cb);
 349 }
 350
 351 static inline
 352 int classnames_identical
 353 ( const uint8_t* stra,
 354   const uint8_t* strb
 355 )
 356 { int ca, cb;
 357   do {
 358     ca = *stra++;
 359     cb = *strb++;
 360   } while (ca && ca == cb);
 361   return (ca == cb);
 362 }
 363
 364 /* Assign Setdata to Set  */
 365 void ir_set_assign_data
 366 ( struct ir_set_t*      set,
 367   union  ir_setdata_t*  setdata
 368 )
 369 { struct ir_framebox_t* framebox;
 370   struct ir_simplex_t*  simplex;
 371   switch (setdata->header.type)
 372     { case FSDAT:
 373         framebox = ir_set_add_framebox(set, setdata->header.data_name);
 374         if (framebox->framesheets[setdata->framesheet.frameinfo.facing].header.data_name != NULL)
 375           wprintf("Duplicate framesheet [%i] %s\n",
 376                   setdata->framesheet.frameinfo.facing, setdata->header.data_name);
 377         framebox->framesheets[setdata->framesheet.frameinfo.facing] = setdata->framesheet;
 378         break;
 379       case MSDAT:
 380         framebox = ir_set_add_framebox(set, setdata->header.data_name);
 381         if (framebox->mapsheets[setdata->mapsheet.frameinfo.facing].header.data_name != NULL)
 382           wprintf("Duplicate mapsheet [%i] %s\n",
 383                   setdata->mapsheet.frameinfo.facing, setdata->header.data_name);
 384         framebox->mapsheets[setdata->mapsheet.frameinfo.facing] = setdata->mapsheet;
 385         break;
 386       case ADAT:
 387         if (set->audio == NULL)
 388           { set->audio = (struct ir_simplex_t*) setdata;
 389             return;
 390           }
 391         simplex = set->audio;
 392         while (simplex->header.nextsib != NULL)
 393           if (bytes_identical(simplex->header.data_name, setdata->header.data_name))
 394             { wprintf("Duplicate audio %s\n", setdata->header.data_name);
 395               *simplex = setdata->audio;
 396               //setdata is now a pointer to redundant, unused memory.
 397               return;
 398             }
 399           else
 400             simplex = (struct ir_simplex_t*) simplex->header.nextsib;
 401         setdata->audio.header.nextsib = (union ir_setdata_t*) set->audio;
 402         set->audio = (struct ir_simplex_t*) setdata;
 403         break;
 404       case LDAT:
 405         setdata->link.header.nextsib = (union ir_setdata_t*) set->links;
 406         set->links = (struct ir_link_t*) setdata;
 407         break;
 408       default:
 409         fprintf(stderr, "Unknown setdata type %x\n", setdata->header.type);
 410         exit(-1);
 411     }
 412 }
 413
 414 void ir_set_assign_ref
 415 ( struct ir_set_t* set,
 416   uint32_t         ref
 417 )
 418 { uint16_t hash, oldhash;
 419   struct ir_set_t** iters;
 420   struct pagenode_t* iterp;
 421   uint32_t           oldref;
 422   oldref = set->ref;
 423   oldhash = 0;
 424   hash = REFHASH(ref);
 425   iterp = refhashpages.root;
 426  check_depth:
 427   iters = ((struct ir_set_t**) iterp->root) + hash;
 428   if (*iters == NULL || *iters == set)
 429     *iters = set;
 430   else
 431     { if (iterp->header.next == NULL)
 432         pagelist_alloc(refhashpages);
 433       iterp = iterp->header.next;
 434       goto check_depth;
 435     }
 436   if (oldref != 0)
 437     { wprintf("Ref override: 0x%x -> 0x%x for set %s\n", oldref, ref, set->name);
 438       if (oldhash != 0)
 439         *iters = NULL;
 440       else
 441         { oldhash = hash;
 442           hash = REFHASH(oldref);
 443           goto check_depth;
 444         }
 445     }
 446   set->ref = ref;
 447 }
 448
 449 void ir_data_assign_path
 450 ( union ir_setdata_t* setdata,
 451   const uint8_t*      path
 452 )
 453 { if (path == NULL)
 454     eprintf("Null path in data %s\n", setdata->header.data_name);
 455   if (setdata->header.src_filename != NULL)
 456     wprintf("Path override: %s -> %s for setdata %s\n",
 457             setdata->header.src_filename, path, setdata->header.data_name);
 458   setdata->header.src_filename = name_alloc(path);
 459 }
 460
 461 union ir_setdata_t* ir_framesheet
 462 ( const uint8_t* name,
 463   apc_facing     d,
 464   int            width,
 465   int            height
 466 )
 467 { return ir_framedata(FSDAT, name, d, width, height); }
 468
 469 union ir_setdata_t* ir_mapsheet
 470 ( const uint8_t* name,
 471   apc_facing     d,
 472   int            width,
 473   int            height
 474 )
 475 { return ir_framedata(MSDAT, name, d, width, height); }
 476
 477 static inline
 478 union ir_setdata_t* ir_framedata
 479 ( enum dtype     type,
 480   const uint8_t* name,
 481   apc_facing     d,
 482   int            width,
 483   int            height
 484 )
 485 { struct ir_framedata_t* framedata = struct_alloc(ir_framedata_t);
 486   if (name == NULL)
 487     eprintf("Null name in set allocation\n");
 488   framedata->header.type = type;
 489   framedata->header.data_name = name_alloc(name);
 490   framedata->frameinfo.facing = d;
 491   framedata->frameinfo.w = width;
 492   framedata->frameinfo.h = height;
 493   return (union ir_setdata_t*) framedata;
 494 }
 495
 496 union ir_setdata_t* ir_audio
 497 ( const uint8_t* name )
 498 { struct ir_simplex_t* audio = struct_alloc(ir_simplex_t);
 499   if (name == NULL)
 500     eprintf("Null audio\n");
 501   audio->header.type = ADAT;
 502   audio->header.data_name = name_alloc(name);
 503   return (union ir_setdata_t*) audio;
 504 }
 505
 506
 507 /* Create classld that points to a class */
 508 struct ir_classld_t* ir_classld_from_class
 509 ( struct ir_class_t* class )
 510 { struct ir_classld_t* classld;
 511   if (class == NULL)
 512     eprintf("Null class in classld\n");
 513   classld = struct_alloc(ir_classld_t);
 514   classld->root_class = class;
 515   return classld;
 516 }
 517
 518 struct ir_setld_t* ir_setld_from_ref
 519 ( uint32_t ref )
 520 { struct ir_setld_t* setld;
 521   setld = struct_alloc(ir_setld_t);
 522   setld->ref = ref;
 523   return setld;
 524 }
 525
 526 struct ir_setld_t* ir_setld_from_classld
 527 ( struct ir_classld_t* classld,
 528   const uint8_t*       name
 529 )
 530 { struct ir_setld_t* setld;
 531   setld = struct_alloc(ir_setld_t);
 532   setld->namelist = struct_alloc(ir_namelist_t);
 533   setld->namelist_head = setld->namelist;
 534   setld->namelist_head->name = name_alloc(name);
 535   setld->classld = classld;
 536   return setld;
 537 }
 538
 539 struct ir_setld_t* ir_setld_addchild
 540 ( struct ir_setld_t* setld,
 541   const uint8_t*     name
 542 )
 543 { if (setld->namelist == NULL)
 544     { setld->namelist = struct_alloc(ir_namelist_t);
 545       setld->namelist_head = setld->namelist;
 546     }
 547   else
 548     { setld->namelist_head->nextsib = struct_alloc(ir_namelist_t);
 549       setld->namelist_head = setld->namelist_head->nextsib;
 550     }
 551   setld->namelist_head->name = name_alloc(name);
 552   return setld;
 553 }
 554
 555 union ir_setdata_t* ir_link
 556 ( enum ltype         link_type,
 557   struct ir_setld_t* setld,
 558   const uint8_t*     name
 559 )
 560 { struct ir_link_t* link;
 561   link = struct_alloc(ir_link_t);
 562   link->header.type = LDAT;
 563   link->type = link_type;
 564   link->classld = setld->classld;
 565   link->setld = setld;
 566   if (link_type != OLINK && name != NULL)
 567     link->header.data_name = name_alloc(name);
 568   return (union ir_setdata_t*) link;
 569 }
 570
 571 static inline
 572 void* pagelist_pop
 573 ( struct pagelist_t* pagelist,
 574   size_t             size
 575 )
 576 { size_t headsize = PL_HEADSIZE((*pagelist));
 577   if (!headsize)
 578     { free(pagelist->head);
 579       pagelist->head = pagelist->root;
 580       while (pagelist->head->header.next != NULL)
 581         pagelist->head = pagelist->head->header.next;
 582     }
 583   if (headsize < size)
 584     eprintf("Attempted to pop unaligned value from pagelist\n");
 585   pagelist->head->header.head -= size;
 586   return pagelist->head->header.head;
 587 }
 588
 589 static
 590 void* stack_alloc
 591 ( size_t bytes )
 592 { if (PL_HEADMEM(datapages) < bytes)
 593     pagelist_alloc(datapages);
 594   datapages.head->header.head += bytes;
 595   return (void*) datapages.head->header.head - bytes;
 596 }
 597
 598 static
 599 uint8_t* name_alloc
 600 ( const uint8_t* name_src )
 601 { const uint8_t* iter;
 602   uint8_t*       name;
 603   int            head_mem;
 604  copy:
 605   name = (uint8_t*)namepages.head->header.head;
 606   iter = name_src;
 607   for (head_mem = PL_HEADMEM(namepages); *iter && *iter != '_' && head_mem; head_mem--)
 608     *(namepages.head->header.head)++ = *iter++;
 609   if (head_mem == 0) //not enough room
 610     { pagelist_alloc(namepages);
 611       goto copy;
 612     }
 613   *(namepages.head->header.head)++ = '\0';
 614   return name;
 615 }
 616
 617 static
 618 uint8_t* classname_alloc
 619 ( const uint8_t* name_src )
 620 { const uint8_t* iter;
 621   uint8_t*       name;
 622   int            head_mem;
 623  copy:
 624   name = (uint8_t*)namepages.head->header.head;
 625   iter = name_src;
 626   for (head_mem = PL_HEADMEM(namepages); *iter && head_mem; head_mem--)
 627     *(namepages.head->header.head)++ = *iter++;
 628   if (head_mem == 0) //not enough room
 629     { pagelist_alloc(namepages);
 630       goto copy;
 631     }
 632   *(namepages.head->header.head)++ = '\0';
 633   return name;
 634 }
 635
 636 #define pdepth() do { for (i = 0; i < depth * 2; i++) putchar(' '); } while (0)
 637 void     ir_test(void)
 638 { struct ir_class_t* class, * classbuf;
 639   struct ir_set_t* set, * set_child;
 640   int depth, i, olddepth;
 641   depth = olddepth = 0;
 642   classbuf = NULL;
 643   for(class = ir_class_root(); class != NULL; class = class->nextchild)
 644     {handle_class:
 645       pdepth();
 646       uprintf("%U\n",class->name);
 647       old_depth = depth;
 648       set = class->root_set;
 649     handle_set:
 650       while(set != NULL)
 651         { pdepth();uprintf("|");
 652           pdepth();
 653           uprintf("-[%U]",set->name);
 654           set_child = set->nextchild;
 655           while (set_child != NULL)
 656             { depth++;
 657               uprintf("--[%U]",set_child->name);
 658               set_child = set_child->nextchild;
 659             }
 660           uprintf("\n");
 661           set = set->nextsib;
 662         }
 663       if (class->nextsib != NULL)
 664         { if (classbuf == NULL)
 665             classbuf = class;
 666           class = class->nextsib;
 667           goto handle_class;
 668         }
 669       if (classbuf != NULL)
 670         class = classbuf;
 671       classbuf = NULL;
 672       uprintf("\n");
 673       depth = olddepth + 1;
 674     }
 675 }