From 43f088652419e08b7426b2c689591b280c0f2330 Mon Sep 17 00:00:00 2001 From: ken Date: Mon, 16 Jan 2017 16:22:49 -0800 Subject: [PATCH 01/16] general debug printing --- src/print.h | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) create mode 100644 src/print.h diff --git a/src/print.h b/src/print.h new file mode 100644 index 0000000..73df046 --- /dev/null +++ b/src/print.h @@ -0,0 +1,33 @@ +/*!@file + \brief Macros for printing unicode to streams + \details Standardized method of handling unicodes in warnings, and errors + \author Jordan Lavatai + \date Aug 2016 + ----------------------------------------------------------------------------*/ +/* u8 print macros */ +#ifndef _PRINT_H_ +#define _PRINT_H_ +#include +#ifndef DEBUG +#define DEBUG 0 +#endif +#define do_warn(...) do { \ + } while (0) +#define wprintf(...) do { \ + ulc_fprintf(stderr, __VA_ARGS__); \ + do_warn(__VA_ARGS__); \ + } while (0) +#define do_error(...) do { \ + } while (0) +#define eprintf(...) do { \ + ulc_fprintf(stderr, __VA_ARGS__); \ + do_error(__VA_ARGS_); \ + } while (0) +#define bprintf(_BOOL,...) do { \ + if (_BOOL) \ + ulc_fprintf(stdout, __VA_ARGS__); \ + } while (0) +#define dprintf(...) do { \ + bprintf(DEBUG, __VA_ARGS__); \ + } while (0) +#endif -- 2.18.0 From 7dae7dc73dfbabdc895a78738f550f56561da644 Mon Sep 17 00:00:00 2001 From: ken Date: Mon, 16 Jan 2017 16:59:58 -0800 Subject: [PATCH 02/16] debug print formatting --- src/ir.c | 44 ++++++++++++++++++++++++++++++++++++++++++-- src/lexer.rl | 13 ++++++------- src/parser.y | 1 + 3 files changed, 49 insertions(+), 9 deletions(-) diff --git a/src/ir.c b/src/ir.c index db97097..a175ef3 100644 --- a/src/ir.c +++ b/src/ir.c @@ -117,11 +117,15 @@ static void ir_free_pagenodes(struct pagenode_t*); static inline int bytes_identical(const uint8_t*,const uint8_t*); +static inline +int classnames_identical(const uint8_t*,const uint8_t*); static void* stack_alloc(size_t); #define struct_alloc(_T) ((struct _T*) stack_alloc(sizeof(struct _T))) static uint8_t* name_alloc(const uint8_t*); +static +uint8_t* classname_alloc(const uint8_t*); extern //apc.c long sys_pagesize; static @@ -209,7 +213,7 @@ struct ir_class_t* ir_class_addchild if (name == NULL) eprintf("Null child added to class %s\n", iter->name); check: - if (bytes_identical(iter->name, name)) + if (classnames_identical(iter->name, name)) return iter; if (iter->nextsib != NULL) { iter = iter->nextsib; @@ -218,7 +222,7 @@ struct ir_class_t* ir_class_addchild alloc: iter = struct_alloc(ir_class_t); iter->nextsib = class->nextchild; - iter->name = name_alloc(name); + iter->name = classname_alloc(name); return class->nextchild = iter; } @@ -325,6 +329,19 @@ int bytes_identical return (ca == cb); } +static inline +int classnames_identical +( const uint8_t* stra, + const uint8_t* strb +) +{ int ca, cb; + do { + ca = *stra++; + cb = *strb++; + } while (ca && ca == cb); + return (ca == cb); +} + /* Assign Setdata to Set */ @@ -549,3 +566,26 @@ uint8_t* name_alloc *(namepages.head->header.head)++ = '\0'; return name; } + +static +uint8_t* classname_alloc +( const uint8_t* name_src ) +{ const uint8_t* iter; + uint8_t* name; + int head_mem; + copy: + name = (uint8_t*)namepages.head->header.head; + iter = name_src; + for (head_mem = PL_HEADMEM(namepages); *iter && head_mem; head_mem--) + *(namepages.head->header.head)++ = *iter++; + if (head_mem == 0) //not enough room + { namepages.head->header.next = (struct pagenode_t*) calloc(namepages.pagesize,1); + if (namepages.head->header.next == NULL) + eprintf("Memory allocation error\n"); + namepages.head = namepages.head->header.next; + namepages.head->header.head = namepages.head->root; + goto copy; + } + *(namepages.head->header.head)++ = '\0'; + return name; +} diff --git a/src/lexer.rl b/src/lexer.rl index c7600ae..920d62d 100644 --- a/src/lexer.rl +++ b/src/lexer.rl @@ -141,18 +141,11 @@ int lexer_lexstring { uint8_t* p, * ts, * pe, * eof; int cs, ntok; YYSTYPE lval; - ntok = 0; p = ts = str; pe = eof = p + size + 1; - - dprintf("\n|---Begin lexstring on p = %U, pe = %p.---|\n",p, pe); - %%write init; %%write exec; - - dprintf("\n|---Ending lexstring of file %U, pushed %d tokens.---|\n",str, ntok); - return ntok; } @@ -177,6 +170,7 @@ int lexer_lexfile // Mark the end of the filename filename_end = iter; // Lex from either the last period, if present, or filename end + dprintf("%U\n\t",filename); ntok = (last_period) ? lexer_lexstring(filename, (int)(last_period - filename)) : lexer_lexstring(filename, (int)(iter - filename)); @@ -185,6 +179,7 @@ int lexer_lexfile if (*iter == '\0') *iter = '_'; PUSHPATH(filename); + dprintf("\n\t[%i Token%s]\n", ntok, (ntok > 1) ? "s" : ""); return ntok + 1; } @@ -192,14 +187,18 @@ int lexer_lexdir ( uint8_t* dirname ) { int ntok; ntok = 0; + if (DEBUG) putchar('\t'); PUSHNAME(dirname); PUSHOP(CLOPEN); + if (DEBUG) putchar('\n'); return ntok; } int lexer_closedir ( void ) { int ntok = 0; + if (DEBUG) putchar('\t'); PUSHOP(CLCLOSE); + if (DEBUG) putchar('\n'); return ntok; } diff --git a/src/parser.y b/src/parser.y index ff2d257..d7a02cd 100644 --- a/src/parser.y +++ b/src/parser.y @@ -129,6 +129,7 @@ frame_spec: NUM NUM { $$ = (struct frame_spec_t) {SFACE,$1,$2}; } | FACING { $$ = (struct frame_spec_t) {$1,0,0}; } | FACING NUM NUM { $$ = (struct frame_spec_t) {$1,$2,$3}; } +| %empty { $$ = (struct frame_spec_t) {SFACE,0,0}; } ; %% -- 2.18.0 From 23d8349fd1086ab2ee644c915e2068dacb6d52c3 Mon Sep 17 00:00:00 2001 From: ken Date: Mon, 16 Jan 2017 17:06:25 -0800 Subject: [PATCH 03/16] debug print formatting --- src/parser.y | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/src/parser.y b/src/parser.y index d7a02cd..9f71a85 100644 --- a/src/parser.y +++ b/src/parser.y @@ -140,9 +140,10 @@ void yyerror char const *s ) { ir_class* iter; + fprintf(stderr, "[class->"); for (iter = cs->class_stack; iter < cs->csp; iter++) fprintf(stderr, "%s/", ir_class_name(*iter)); - fprintf(stderr, "\n\t"); + fprintf(stderr, "]\n\t"); fprintf(stderr, "%s\n", s); } -- 2.18.0 From 1003b482cc65139b25ba503c9918b457cc87aa3d Mon Sep 17 00:00:00 2001 From: Jordan Date: Mon, 16 Jan 2017 17:26:35 -0800 Subject: [PATCH 04/16] filename terminator is now a . --- src/lexer.rl | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/src/lexer.rl b/src/lexer.rl index 920d62d..83915ec 100644 --- a/src/lexer.rl +++ b/src/lexer.rl @@ -113,7 +113,7 @@ uint8_t lval_offs; tok = (name | val | ref | dimensions | map | link | SS | direction); - main := (tok tok_delimiter)* tok [\0]; + main := (tok tok_delimiter)* tok [.]; write data nofinal noerror noprefix; @@ -159,6 +159,7 @@ int lexer_lexfile { uint8_t* last_period,* iter,* filename_end; int ntok; last_period = NULL; + printf("size of file = %d\n", u8_strlen(filename)); for (iter = filename; *iter; iter++) switch (*iter) { // Keep track of the last 'dot' in the name @@ -174,6 +175,7 @@ int lexer_lexfile ntok = (last_period) ? lexer_lexstring(filename, (int)(last_period - filename)) : lexer_lexstring(filename, (int)(iter - filename)); + // Replace nulls with their original '_' for (iter = filename; iter < filename_end; iter++) if (*iter == '\0') -- 2.18.0 From a0158f91cb212534a45c455f1d155fff45f7ff80 Mon Sep 17 00:00:00 2001 From: Jordan Date: Mon, 16 Jan 2017 17:48:30 -0800 Subject: [PATCH 05/16] working? --- src/lexer.rl | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) diff --git a/src/lexer.rl b/src/lexer.rl index 83915ec..ff2fa14 100644 --- a/src/lexer.rl +++ b/src/lexer.rl @@ -113,7 +113,7 @@ uint8_t lval_offs; tok = (name | val | ref | dimensions | map | link | SS | direction); - main := (tok tok_delimiter)* tok [.]; + main := (tok tok_delimiter)* tok ; write data nofinal noerror noprefix; @@ -143,7 +143,7 @@ int lexer_lexstring YYSTYPE lval; ntok = 0; p = ts = str; - pe = eof = p + size + 1; + pe = eof = p + size; %%write init; %%write exec; return ntok; @@ -159,7 +159,6 @@ int lexer_lexfile { uint8_t* last_period,* iter,* filename_end; int ntok; last_period = NULL; - printf("size of file = %d\n", u8_strlen(filename)); for (iter = filename; *iter; iter++) switch (*iter) { // Keep track of the last 'dot' in the name -- 2.18.0 From 5c208623c432fb00194b81b3b024b256349120c2 Mon Sep 17 00:00:00 2001 From: ken Date: Tue, 17 Jan 2017 21:19:07 -0800 Subject: [PATCH 06/16] added xxhash --- xxHash | 1 + 1 file changed, 1 insertion(+) create mode 160000 xxHash diff --git a/xxHash b/xxHash new file mode 160000 index 0000000..7fc5ce8 --- /dev/null +++ b/xxHash @@ -0,0 +1 @@ +Subproject commit 7fc5ce8592f10c68506f4a070bfa6a9ab2004b44 -- 2.18.0 From ee18200a9d3817728d6d09745cd29900649d4508 Mon Sep 17 00:00:00 2001 From: ken Date: Tue, 17 Jan 2017 21:19:42 -0800 Subject: [PATCH 07/16] xxhash integrated --- src/ir.c | 214 ++++++++++++++++++++++++++++++++++++++----------------- src/ir.h | 4 +- 2 files changed, 151 insertions(+), 67 deletions(-) diff --git a/src/ir.c b/src/ir.c index a175ef3..706f677 100644 --- a/src/ir.c +++ b/src/ir.c @@ -21,9 +21,12 @@ #include "ir.h" #undef do_error #define do_error(...) exit(-1) +#define XXH_PRIVATE_API +#include "../xxHash/xxhash.h" /* Public */ int ir_init(void); void ir_quit(void); +void ir_test(void); int ir_linker(void); int ir_condenser(void); /* Memory allocation structures */ @@ -40,7 +43,7 @@ struct pagelist_t { struct pagenode_t* root, * head; size_t pagesize; }; -#define DATA_PAGESIZE (sys_pagesize) +#define SYS_PAGESIZE (sys_pagesize) #define NAME_PAGESIZE (APC_NAME_MAX * 1024) #define PL_HEADERSIZE (sizeof(struct pagenode_header_t)) #define PL_HEADSIZE(_PL) (_PL.head->header.head - _PL.head->root) @@ -100,7 +103,7 @@ struct ir_class_t struct ir_set_t { struct ir_set_t* nextchild, * nextsib; struct ir_class_t* class; - long long ref; + uint32_t ref; uint8_t* name; struct ir_framebox_t* frameboxes; struct ir_simplex_t* audio; @@ -112,10 +115,6 @@ struct ir_framebox_t* ir_set_add_framebox(struct ir_set_t*,const uint8_t*); static inline union ir_setdata_t* ir_framedata (enum dtype,const uint8_t*,apc_facing,int,int); static inline -int init_pagelist(struct pagelist_t*,size_t); -static -void ir_free_pagenodes(struct pagenode_t*); -static inline int bytes_identical(const uint8_t*,const uint8_t*); static inline int classnames_identical(const uint8_t*,const uint8_t*); @@ -126,62 +125,68 @@ static uint8_t* name_alloc(const uint8_t*); static uint8_t* classname_alloc(const uint8_t*); +static inline +void* pagelist_pop(struct pagelist_t*,size_t); +#define pagelist_alloc(pagelist) do { \ + pagelist.head->header.next = (struct pagenode_t*) calloc(pagelist.pagesize,1); \ + if (pagelist.head->header.next == NULL) \ + eprintf("Memory allocation error\n"); \ + pagelist.head = pagelist.head->header.next; \ + pagelist.head->header.head = pagelist.head->root; \ + } while (0) +#define pagelist_init(pagelist,size) do { \ + pagelist.pagesize = size; \ + pagelist.root = (struct pagenode_t*) calloc(size,1); \ + if (pagelist.root == NULL) \ + eprintf("Memory allocation error\n"); \ + pagelist.root->header.head = pagelist.root->root; \ + pagelist.head = pagelist.root; \ + } while (0) +static +void pagenode_free(struct pagenode_t*); +#define REFHASH(ref) (XXH32(&ref, sizeof(uint32_t), 0xCEED) & 0xCFF) + extern //apc.c long sys_pagesize; static -struct pagelist_t datapages, namepages; +struct pagelist_t datapages, namepages, refhashpages; static struct ir_class_t root_class = { .name = (uint8_t*)"." }; /* Init */ int ir_init ( void ) -{ if (init_pagelist(&datapages, (size_t)DATA_PAGESIZE)) - eprintf("Memory allocation error\n"); - if (init_pagelist(&namepages, (size_t)NAME_PAGESIZE)) - eprintf("Memory allocation error\n"); +{ pagelist_init(datapages, (size_t)SYS_PAGESIZE); + pagelist_init(namepages, (size_t)NAME_PAGESIZE); + pagelist_init(refhashpages, (size_t)SYS_PAGESIZE); return 0; } -static inline -int init_pagelist -( struct pagelist_t* pl, - size_t size -) -{ pl->pagesize = size; - pl->root = (struct pagenode_t*) calloc(size,1); - if (pl->root == NULL) - return -1; - pl->root->header.head = pl->root->root; - pl->head = pl->root; - return 0; -} - -/* Quit/Cleanup - Recursively clean pagenode linked list -*/ +/* Quit/Cleanup */ void ir_quit ( void ) -{ ir_free_pagenodes(datapages.root); - ir_free_pagenodes(namepages.root); +{ pagenode_free(datapages.root); + pagenode_free(namepages.root); + pagenode_free(refhashpages.root); } +/* Recursively clean pagenode linked list, freeing last first */ static -void ir_free_pagenodes +void pagenode_free ( struct pagenode_t* pagenode ) { if (pagenode->header.next != NULL) - ir_free_pagenodes(pagenode->header.next); + pagenode_free(pagenode->header.next); free(pagenode); } -/* Link -*/ +/* Link */ int ir_linker ( void ) -{ return 0; } +{ + return 0; +} -/* Condense -*/ +/* Condense */ int ir_condenser ( void ) { return 0; } @@ -256,6 +261,20 @@ struct ir_set_t* ir_class_addset return class->root_set = iter; } +struct ir_set_t* ir_set_from_ref +( uint32_t ref ) +{ uint16_t hash; + struct ir_set_t** iters; + struct pagenode_t* iterp; + iterp = refhashpages.root; + hash = REFHASH(ref); + do + iters = ((struct ir_set_t**) iterp->root) + hash; + while (*iters != NULL && (*iters)->ref != ref && (iterp = iterp->header.next) != NULL); + return *iters; +} + + /* Add a set to a set Attempts to create a new subset of the specified set, returning the child if it already exists @@ -342,9 +361,7 @@ int classnames_identical return (ca == cb); } -/* Assign Setdata to Set - - */ +/* Assign Setdata to Set */ void ir_set_assign_data ( struct ir_set_t* set, union ir_setdata_t* setdata @@ -396,13 +413,37 @@ void ir_set_assign_data void ir_set_assign_ref ( struct ir_set_t* set, - long long ref + uint32_t ref ) -{ if (set->ref != 0) - wprintf("Ref override: 0x%lx -> 0x%lx for set %s\n", - (long unsigned) set->ref, (long unsigned) ref, set->name); +{ uint16_t hash, oldhash; + struct ir_set_t** iters; + struct pagenode_t* iterp; + uint32_t oldref; + oldref = set->ref; + oldhash = 0; + hash = REFHASH(ref); + iterp = refhashpages.root; + check_depth: + iters = ((struct ir_set_t**) iterp->root) + hash; + if (*iters == NULL || *iters == set) + *iters = set; + else + { if (iterp->header.next == NULL) + pagelist_alloc(refhashpages); + iterp = iterp->header.next; + goto check_depth; + } + if (oldref != 0) + { wprintf("Ref override: 0x%x -> 0x%x for set %s\n", oldref, ref, set->name); + if (oldhash != 0) + *iters = NULL; + else + { oldhash = hash; + hash = REFHASH(oldref); + goto check_depth; + } + } set->ref = ref; - //TODO: reflist_add(set); } void ir_data_assign_path @@ -475,7 +516,7 @@ struct ir_classld_t* ir_classld_from_class } struct ir_setld_t* ir_setld_from_ref -( long long ref ) +( uint32_t ref ) { struct ir_setld_t* setld; setld = struct_alloc(ir_setld_t); setld->ref = ref; @@ -527,19 +568,29 @@ union ir_setdata_t* ir_link return (union ir_setdata_t*) link; } +static inline +void* pagelist_pop +( struct pagelist_t* pagelist, + size_t size +) +{ size_t headsize = PL_HEADSIZE((*pagelist)); + if (!headsize) + { free(pagelist->head); + pagelist->head = pagelist->root; + while (pagelist->head->header.next != NULL) + pagelist->head = pagelist->head->header.next; + } + if (headsize < size) + eprintf("Attempted to pop unaligned value from pagelist\n"); + pagelist->head->header.head -= size; + return pagelist->head->header.head; +} static void* stack_alloc ( size_t bytes ) -{ if (!bytes) //valid behavior to attain current head - return datapages.head->header.head; - if (PL_HEADMEM(datapages) < bytes) - { datapages.head->header.next = (struct pagenode_t*) calloc(datapages.pagesize,1); - if (datapages.head->header.next == NULL) - eprintf("Memory allocation error \n"); - datapages.head = datapages.head->header.next; - datapages.head->header.head = datapages.head->root; - } +{ if (PL_HEADMEM(datapages) < bytes) + pagelist_alloc(datapages); datapages.head->header.head += bytes; return (void*) datapages.head->header.head - bytes; } @@ -556,11 +607,7 @@ uint8_t* name_alloc for (head_mem = PL_HEADMEM(namepages); *iter && *iter != '_' && head_mem; head_mem--) *(namepages.head->header.head)++ = *iter++; if (head_mem == 0) //not enough room - { namepages.head->header.next = (struct pagenode_t*) calloc(namepages.pagesize,1); - if (namepages.head->header.next == NULL) - eprintf("Memory allocation error\n"); - namepages.head = namepages.head->header.next; - namepages.head->header.head = namepages.head->root; + { pagelist_alloc(namepages); goto copy; } *(namepages.head->header.head)++ = '\0'; @@ -579,13 +626,50 @@ uint8_t* classname_alloc for (head_mem = PL_HEADMEM(namepages); *iter && head_mem; head_mem--) *(namepages.head->header.head)++ = *iter++; if (head_mem == 0) //not enough room - { namepages.head->header.next = (struct pagenode_t*) calloc(namepages.pagesize,1); - if (namepages.head->header.next == NULL) - eprintf("Memory allocation error\n"); - namepages.head = namepages.head->header.next; - namepages.head->header.head = namepages.head->root; + { pagelist_alloc(namepages); goto copy; } *(namepages.head->header.head)++ = '\0'; return name; } + +#define pdepth() do { for (i = 0; i < depth * 2; i++) putchar(' '); } while (0) +void ir_test(void) +{ struct ir_class_t* class, * classbuf; + struct ir_set_t* set, * set_child; + int depth, i, olddepth; + depth = olddepth = 0; + classbuf = NULL; + for(class = ir_class_root(); class != NULL; class = class->nextchild) + {handle_class: + pdepth(); + uprintf("%U\n",class->name); + old_depth = depth; + set = class->root_set; + handle_set: + while(set != NULL) + { pdepth();uprintf("|"); + pdepth(); + uprintf("-[%U]",set->name); + set_child = set->nextchild; + while (set_child != NULL) + { depth++; + uprintf("--[%U]",set_child->name); + set_child = set_child->nextchild; + } + uprintf("\n"); + set = set->nextsib; + } + if (class->nextsib != NULL) + { if (classbuf == NULL) + classbuf = class; + class = class->nextsib; + goto handle_class; + } + if (classbuf != NULL) + class = classbuf; + classbuf = NULL; + uprintf("\n"); + depth = olddepth + 1; + } +} diff --git a/src/ir.h b/src/ir.h index aec70db..68fcde2 100644 --- a/src/ir.h +++ b/src/ir.h @@ -65,7 +65,7 @@ ir_set ir_set_addchild(ir_set,const uint8_t*); */ enum ltype { OLINK, MLINK, VLINK, ALINK }; void ir_set_assign_data(ir_set,ir_setdata); -void ir_set_assign_ref(ir_set,long long); +void ir_set_assign_ref(ir_set,uint32_t); void ir_data_assign_path(ir_setdata,const uint8_t*); ir_setdata ir_framesheet(const uint8_t*, apc_facing, int,int); ir_setdata ir_mapsheet(const uint8_t*, apc_facing, int,int); @@ -82,7 +82,7 @@ ir_setdata ir_link(enum ltype,ir_setld,const uint8_t*); ir_classld ir_classld_from_class(ir_class); ir_classld ir_classld_from_root(void); ir_classld ir_classld_addchild(ir_classld,const uint8_t*); -ir_setld ir_setld_from_ref(long long); +ir_setld ir_setld_from_ref(uint32_t); ir_setld ir_setld_from_classld(ir_classld,const uint8_t*); ir_setld ir_setld_addchild(ir_setld,const uint8_t*); #endif //_IR_H_ -- 2.18.0 From e957af2c23e57f97591580aff0b7835eb4af1dc2 Mon Sep 17 00:00:00 2001 From: ken Date: Tue, 17 Jan 2017 21:20:32 -0800 Subject: [PATCH 08/16] ir testing --- src/apc.c | 16 +++++++++------- src/parser.y | 5 +++-- src/print.h | 12 +++++++++--- 3 files changed, 21 insertions(+), 12 deletions(-) diff --git a/src/apc.c b/src/apc.c index 5bd6d73..a066765 100644 --- a/src/apc.c +++ b/src/apc.c @@ -41,6 +41,8 @@ extern //ir.c int ir_linker(void); extern //ir.c int ir_condenser(void); +extern +void ir_test(void); /* Main entry from terminal parses the command line and kicks off recursive scanning @@ -62,7 +64,12 @@ int main #define DONE -1 #define SCANPATH (cargs['d'] ? cargs['d'] : "./") { int opt; - + if ((sys_pagesize = sysconf(_SC_PAGESIZE)) == 0) + sys_pagesize = DEFAULT_PAGESIZE; + if (ir_init()) + { perror("init"); + exit(EXIT_FAILURE); + } getopt: switch (opt = getopt(argc, argv, OPTS)) { case 'd' : @@ -82,16 +89,11 @@ int main case DONE: break; } - if ((sys_pagesize = sysconf(_SC_PAGESIZE)) == 0) - sys_pagesize = DEFAULT_PAGESIZE; - if (ir_init()) - { perror("init"); - exit(EXIT_FAILURE); - } if (scanner_scanpath(SCANPATH)) { perror("scanner"); exit(EXIT_FAILURE); } + ir_test(); ir_linker(); ir_condenser(); exit(EXIT_SUCCESS); diff --git a/src/parser.y b/src/parser.y index 9f71a85..881b562 100644 --- a/src/parser.y +++ b/src/parser.y @@ -39,9 +39,9 @@ %define api.push-pull push %parse-param {yycstate* cs} %union { - long long ref; + uint32_t ref; int val; - apc_facing face; + apc_facing face; uint8_t* str; ir_class class; ir_set set; @@ -84,6 +84,7 @@ class: NAME CLOPEN { yyclass_push(cs,ir_class_addchild(yyclass(cs), $1)); } progn CLCLOSE { yyclass_pop(cs); } +| CLCLOSE { yyclass_pop(cs); } ; statement_list: diff --git a/src/print.h b/src/print.h index 73df046..6e1c4ba 100644 --- a/src/print.h +++ b/src/print.h @@ -11,21 +11,27 @@ #ifndef DEBUG #define DEBUG 0 #endif +#define uprintf(...) do { \ + ulc_fprintf(stdout, __VA_ARGS__); \ + } while (0) +#define ufprintf(_STREAM,...) do { \ + ulc_fprintf(_STREAM, __VA_ARGS__); \ + } while (0) #define do_warn(...) do { \ } while (0) #define wprintf(...) do { \ - ulc_fprintf(stderr, __VA_ARGS__); \ + ufprintf(stderr, __VA_ARGS__); \ do_warn(__VA_ARGS__); \ } while (0) #define do_error(...) do { \ } while (0) #define eprintf(...) do { \ - ulc_fprintf(stderr, __VA_ARGS__); \ + ufprintf(stderr, __VA_ARGS__); \ do_error(__VA_ARGS_); \ } while (0) #define bprintf(_BOOL,...) do { \ if (_BOOL) \ - ulc_fprintf(stdout, __VA_ARGS__); \ + ufprintf(stdout, __VA_ARGS__); \ } while (0) #define dprintf(...) do { \ bprintf(DEBUG, __VA_ARGS__); \ -- 2.18.0 From fc6b15eee27f77e01ed4a24bc11e7bfa5a812342 Mon Sep 17 00:00:00 2001 From: ken Date: Thu, 19 Jan 2017 16:27:15 -0800 Subject: [PATCH 09/16] default variant --- src/parser.y | 3 +++ 1 file changed, 3 insertions(+) diff --git a/src/parser.y b/src/parser.y index 881b562..e1fe896 100644 --- a/src/parser.y +++ b/src/parser.y @@ -31,6 +31,7 @@ /* Stack-based class handler */ #define yyclass(CS) (*(CS->csp)) #define yyclassld(CS) (ir_classld_from_class(yyclass(CS))) + #define DEFAULT_VARIANT "default" } %define parse.error verbose %define parse.lac full @@ -100,7 +101,9 @@ statement: data_spec: SS NAME frame_spec { $$ = ir_framesheet($2,$3.d,$3.w,$3.h); } +| SS frame_spec { $$ = ir_framesheet(DEFAULT_VARIANT,$2.d,$2.w,$2.h); } | MAP NAME frame_spec { $$ = ir_mapsheet($2,$3.d,$3.w,$3.h); } +| MAP frame_spec { $$ = ir_mapsheet(DEFAULT_VARIANT,$2.d,$2.w,$2.h); } | AUDIO NAME { $$ = ir_audio($2); } | LINK set_ld { $$ = ir_link(OLINK, $2, NULL); } | LINK set_ld MAP { $$ = ir_link(MLINK, $2,NULL); } -- 2.18.0 From 5f13e2b92707358f5a9a297afdfcbb7851fdc736 Mon Sep 17 00:00:00 2001 From: ken Date: Thu, 19 Jan 2017 16:27:33 -0800 Subject: [PATCH 10/16] ir treewalk fixes --- src/apc.c | 37 +++++++++-- src/ir.c | 187 +++++++++++++++++++++++++++++++++--------------------- 2 files changed, 145 insertions(+), 79 deletions(-) diff --git a/src/apc.c b/src/apc.c index a066765..df4810e 100644 --- a/src/apc.c +++ b/src/apc.c @@ -20,6 +20,7 @@ #include //getopt, sysconf /* Internal */ #include "parser.tab.h" //bison +#include "ir.h" #define DEFAULT_PAGESIZE 4096 const char* cargs['Z'] = {0}; @@ -64,12 +65,6 @@ int main #define DONE -1 #define SCANPATH (cargs['d'] ? cargs['d'] : "./") { int opt; - if ((sys_pagesize = sysconf(_SC_PAGESIZE)) == 0) - sys_pagesize = DEFAULT_PAGESIZE; - if (ir_init()) - { perror("init"); - exit(EXIT_FAILURE); - } getopt: switch (opt = getopt(argc, argv, OPTS)) { case 'd' : @@ -89,10 +84,40 @@ int main case DONE: break; } + if ((sys_pagesize = sysconf(_SC_PAGESIZE)) == 0) + sys_pagesize = DEFAULT_PAGESIZE; + if (ir_init()) + { perror("init"); + exit(EXIT_FAILURE); + } +#if 0 if (scanner_scanpath(SCANPATH)) { perror("scanner"); exit(EXIT_FAILURE); } +#endif + ir_class class; + ir_set set; + int i, j; + char wordbuf[0xFFF]; + for (class = ir_class_root(), i = 0, j = 0; i < 100; i++) + { sprintf(wordbuf,"Class%i",i); + class = ir_class_addchild(class,(uint8_t*)wordbuf); + sprintf(wordbuf,"c%i-s%i",i,j++); + set = ir_class_addset(class, (uint8_t*)wordbuf); + sprintf(wordbuf,"c%i-s%i",i,j++); + ir_class_addset(class, (uint8_t*)wordbuf); + sprintf(wordbuf,"c%i-s%i",i,j++); + ir_class_addset(class, (uint8_t*)wordbuf); + sprintf(wordbuf,"c%i-sc%i",i,j=0); + set = ir_set_addchild(set, (uint8_t*)wordbuf); + sprintf(wordbuf,"c%i-sc%i",i,++j); + ir_set_addchild(set, (uint8_t*)wordbuf); + sprintf(wordbuf,"c%i-sc%i",i,++j); + set = ir_set_addchild(set, (uint8_t*)wordbuf); + sprintf(wordbuf,"c%i-sb%i",i,j=0); + ir_set_addchild(set, (uint8_t*)wordbuf); + } ir_test(); ir_linker(); ir_condenser(); diff --git a/src/ir.c b/src/ir.c index 706f677..e88ac36 100644 --- a/src/ir.c +++ b/src/ir.c @@ -102,7 +102,6 @@ struct ir_class_t }; struct ir_set_t { struct ir_set_t* nextchild, * nextsib; - struct ir_class_t* class; uint32_t ref; uint8_t* name; struct ir_framebox_t* frameboxes; @@ -111,7 +110,7 @@ struct ir_set_t }; /* Functions */ static inline -struct ir_framebox_t* ir_set_add_framebox(struct ir_set_t*,const uint8_t*); +struct ir_framebox_t* ir_set_add_framebox(struct ir_set_t*,uint8_t*); static inline union ir_setdata_t* ir_framedata (enum dtype,const uint8_t*,apc_facing,int,int); static inline @@ -121,26 +120,30 @@ int classnames_identical(const uint8_t*,const uint8_t*); static void* stack_alloc(size_t); #define struct_alloc(_T) ((struct _T*) stack_alloc(sizeof(struct _T))) +#define struct_clear(_S) (memset((_S), 0, sizeof(*(_S)))) static uint8_t* name_alloc(const uint8_t*); static uint8_t* classname_alloc(const uint8_t*); static inline void* pagelist_pop(struct pagelist_t*,size_t); +#define $($)#$ #define pagelist_alloc(pagelist) do { \ - pagelist.head->header.next = (struct pagenode_t*) calloc(pagelist.pagesize,1); \ + pagelist.head->header.next = (struct pagenode_t*) malloc(pagelist.pagesize); \ if (pagelist.head->header.next == NULL) \ eprintf("Memory allocation error\n"); \ + struct_clear(pagelist.head->header.next); \ pagelist.head = pagelist.head->header.next; \ pagelist.head->header.head = pagelist.head->root; \ } while (0) #define pagelist_init(pagelist,size) do { \ pagelist.pagesize = size; \ - pagelist.root = (struct pagenode_t*) calloc(size,1); \ + pagelist.root = (struct pagenode_t*) malloc(size); \ if (pagelist.root == NULL) \ eprintf("Memory allocation error\n"); \ - pagelist.root->header.head = pagelist.root->root; \ + struct_clear(pagelist.root); \ pagelist.head = pagelist.root; \ + pagelist.head->header.head = pagelist.head->root; \ } while (0) static void pagenode_free(struct pagenode_t*); @@ -211,7 +214,11 @@ struct ir_class_t* ir_class_addchild ) { struct ir_class_t* iter; if (class->nextchild == NULL) - goto alloc; + { class->nextchild = struct_alloc(ir_class_t); + struct_clear(class->nextchild); + class->nextchild->name = classname_alloc(name); + return class->nextchild; + } iter = class->nextchild; if (iter->name == NULL) eprintf("Null name pointer in class %p\n", iter); @@ -224,11 +231,10 @@ struct ir_class_t* ir_class_addchild { iter = iter->nextsib; goto check; } - alloc: - iter = struct_alloc(ir_class_t); - iter->nextsib = class->nextchild; - iter->name = classname_alloc(name); - return class->nextchild = iter; + iter->nextsib = struct_alloc(ir_class_t); + struct_clear(iter->nextsib); + iter->nextsib->name = classname_alloc(name); + return iter->nextsib; } /* Add a set to a class @@ -241,7 +247,11 @@ struct ir_set_t* ir_class_addset ) { struct ir_set_t* iter; if (class->root_set == NULL) - goto alloc; + { class->root_set = struct_alloc(ir_set_t); + struct_clear(class->root_set); + class->root_set->name = name_alloc(name); + return class->root_set; + } iter = class->root_set; if (iter->name == NULL) eprintf("Null name pointer in class %p\n", iter); @@ -254,11 +264,10 @@ struct ir_set_t* ir_class_addset { iter = iter->nextsib; goto check; } - alloc: - iter = struct_alloc(ir_set_t); - iter->nextsib = class->root_set; - iter->name = name_alloc(name); - return class->root_set = iter; + iter->nextsib = struct_alloc(ir_set_t); + struct_clear(iter->nextsib); + iter->nextsib->name = name_alloc(name); + return iter->nextsib; } struct ir_set_t* ir_set_from_ref @@ -285,12 +294,16 @@ struct ir_set_t* ir_set_addchild ) { struct ir_set_t* iter; if (set->nextchild == NULL) - goto alloc; + { set->nextchild = struct_alloc(ir_set_t); + struct_clear(set->nextchild); + set->nextchild->name = name_alloc(name); + return set->nextchild; + } iter = set->nextchild; - if (iter->name == NULL) - eprintf("Null name pointer in set %p\n", iter); if (name == NULL) eprintf("Null child added to set %s\n", iter->name); + if (iter->name == NULL) + eprintf("Null name pointer in set %p\n", iter); check: if (bytes_identical(iter->name, name)) return iter; @@ -298,25 +311,30 @@ struct ir_set_t* ir_set_addchild { iter = iter->nextsib; goto check; } - alloc: - iter = struct_alloc(ir_set_t); - iter->nextsib = set->nextchild; - iter->name = name_alloc(name); - return set->nextchild = iter; + iter->nextsib = struct_alloc(ir_set_t); + struct_clear(iter->nextsib); + iter->nextsib->name = name_alloc(name); + return iter->nextsib; } /* Add a framebox to a set Attempts to create a new framebox of the specified set, returning the framebox if it already exists + Name is not allocated, but assigned, unlike other "XXX_add" functions where + name is duplicated into IR's internal array. */ static inline struct ir_framebox_t* ir_set_add_framebox ( struct ir_set_t* set, - const uint8_t* name + uint8_t* name ) { struct ir_framebox_t* iter; if (set->frameboxes == NULL) - goto alloc; + { set->frameboxes = struct_alloc(ir_framebox_t); + struct_clear(set->frameboxes); + set->frameboxes->header.data_name = name; + return set->frameboxes; + } iter = set->frameboxes; check: if (bytes_identical(iter->header.data_name, name)) @@ -325,11 +343,10 @@ struct ir_framebox_t* ir_set_add_framebox { iter = (struct ir_framebox_t*) iter->header.nextsib; goto check; } - alloc: - iter = struct_alloc(ir_framebox_t); - iter->header.nextsib = (union ir_setdata_t*) set->frameboxes; - iter->header.data_name = name_alloc(name); - return set->frameboxes = iter; + iter->header.nextsib = (union ir_setdata_t*) struct_alloc(ir_framebox_t); + struct_clear(iter->header.nextsib); + iter->header.nextsib->header.data_name = name; + return (struct ir_framebox_t*) (iter->header.nextsib); } /* Match two null-terminated bytestrings @@ -483,6 +500,7 @@ union ir_setdata_t* ir_framedata int height ) { struct ir_framedata_t* framedata = struct_alloc(ir_framedata_t); + struct_clear(framedata); if (name == NULL) eprintf("Null name in set allocation\n"); framedata->header.type = type; @@ -496,6 +514,7 @@ union ir_setdata_t* ir_framedata union ir_setdata_t* ir_audio ( const uint8_t* name ) { struct ir_simplex_t* audio = struct_alloc(ir_simplex_t); + struct_clear(audio); if (name == NULL) eprintf("Null audio\n"); audio->header.type = ADAT; @@ -511,6 +530,7 @@ struct ir_classld_t* ir_classld_from_class if (class == NULL) eprintf("Null class in classld\n"); classld = struct_alloc(ir_classld_t); + struct_clear(classld); classld->root_class = class; return classld; } @@ -519,6 +539,7 @@ struct ir_setld_t* ir_setld_from_ref ( uint32_t ref ) { struct ir_setld_t* setld; setld = struct_alloc(ir_setld_t); + struct_clear(setld); setld->ref = ref; return setld; } @@ -529,7 +550,9 @@ struct ir_setld_t* ir_setld_from_classld ) { struct ir_setld_t* setld; setld = struct_alloc(ir_setld_t); + struct_clear(setld); setld->namelist = struct_alloc(ir_namelist_t); + struct_clear(setld->namelist); setld->namelist_head = setld->namelist; setld->namelist_head->name = name_alloc(name); setld->classld = classld; @@ -542,10 +565,12 @@ struct ir_setld_t* ir_setld_addchild ) { if (setld->namelist == NULL) { setld->namelist = struct_alloc(ir_namelist_t); + struct_clear(setld->namelist); setld->namelist_head = setld->namelist; } else { setld->namelist_head->nextsib = struct_alloc(ir_namelist_t); + struct_clear(setld->namelist_head->nextsib); setld->namelist_head = setld->namelist_head->nextsib; } setld->namelist_head->name = name_alloc(name); @@ -559,6 +584,7 @@ union ir_setdata_t* ir_link ) { struct ir_link_t* link; link = struct_alloc(ir_link_t); + struct_clear(link); link->header.type = LDAT; link->type = link_type; link->classld = setld->classld; @@ -589,10 +615,12 @@ void* pagelist_pop static void* stack_alloc ( size_t bytes ) -{ if (PL_HEADMEM(datapages) < bytes) +{ void* p; + if (PL_HEADMEM(datapages) < bytes) pagelist_alloc(datapages); + p = datapages.head->header.head; datapages.head->header.head += bytes; - return (void*) datapages.head->header.head - bytes; + return p; } static @@ -606,7 +634,7 @@ uint8_t* name_alloc iter = name_src; for (head_mem = PL_HEADMEM(namepages); *iter && *iter != '_' && head_mem; head_mem--) *(namepages.head->header.head)++ = *iter++; - if (head_mem == 0) //not enough room + if (head_mem < 1) //not enough room { pagelist_alloc(namepages); goto copy; } @@ -625,7 +653,7 @@ uint8_t* classname_alloc iter = name_src; for (head_mem = PL_HEADMEM(namepages); *iter && head_mem; head_mem--) *(namepages.head->header.head)++ = *iter++; - if (head_mem == 0) //not enough room + if (head_mem < 1) //not enough room { pagelist_alloc(namepages); goto copy; } @@ -633,43 +661,56 @@ uint8_t* classname_alloc return name; } -#define pdepth() do { for (i = 0; i < depth * 2; i++) putchar(' '); } while (0) +static void crawl_class(struct ir_class_t*,int); +static void crawl_set(struct ir_set_t*,int); void ir_test(void) -{ struct ir_class_t* class, * classbuf; - struct ir_set_t* set, * set_child; - int depth, i, olddepth; - depth = olddepth = 0; - classbuf = NULL; - for(class = ir_class_root(); class != NULL; class = class->nextchild) - {handle_class: - pdepth(); - uprintf("%U\n",class->name); - old_depth = depth; - set = class->root_set; - handle_set: - while(set != NULL) - { pdepth();uprintf("|"); - pdepth(); - uprintf("-[%U]",set->name); - set_child = set->nextchild; - while (set_child != NULL) - { depth++; - uprintf("--[%U]",set_child->name); - set_child = set_child->nextchild; - } - uprintf("\n"); - set = set->nextsib; - } - if (class->nextsib != NULL) - { if (classbuf == NULL) - classbuf = class; - class = class->nextsib; - goto handle_class; - } - if (classbuf != NULL) - class = classbuf; - classbuf = NULL; - uprintf("\n"); - depth = olddepth + 1; +{ uprintf("IR From Directory: %s\n",getcwd(NULL,255)); + crawl_class(&root_class,0); +} + +#define pspace(num) for (i = 0; i < (num); i++) putchar(' ') +static +void crawl_class +( struct ir_class_t* class, + int depth +) +{ struct ir_class_t* iter; + /*if(chdir((char*)class->name)) + eprintf("CHDIR %U\n",class->name); + else + wprintf("chdir %U\n",class->name);*/ + if (class->nextchild != NULL) + { iter = class->nextchild; + do { + crawl_class(iter,depth + 1); + /*if (chdir("..")) + eprintf("CHDIR ..\n");*/ + } while ((iter = iter->nextsib) != NULL); + } + wprintf("%U/\n", class->name); + if (class->root_set != NULL) + crawl_set(class->root_set,0); + uprintf("\n%U\\\n",class->name); +} + +static +void crawl_set +( struct ir_set_t* set, + int depth +) +{ struct ir_set_t* iter; + int i = depth * 10; + pspace(i); + i = 0; + for(iter = set->nextchild; iter != NULL; iter = iter->nextchild) + { uprintf("[%8U]", iter->name); + } + for(iter = set->nextchild; iter != NULL; iter = iter->nextchild) + { if (iter->nextsib != NULL) + crawl_set(iter->nextsib, i); + i++; } + for(iter = set->nextchild; iter != NULL; iter = iter->nextchild) + crawl_set(iter, depth + 1); + putchar('\n'); } -- 2.18.0 From 2ca6f20e312ca76816f894aa96fa901dee2aa6bb Mon Sep 17 00:00:00 2001 From: ken Date: Thu, 19 Jan 2017 19:29:24 -0800 Subject: [PATCH 11/16] dynamic allocation of cargs --- src/apc.c | 30 +++++------------------------- 1 file changed, 5 insertions(+), 25 deletions(-) diff --git a/src/apc.c b/src/apc.c index df4810e..4e71155 100644 --- a/src/apc.c +++ b/src/apc.c @@ -23,7 +23,7 @@ #include "ir.h" #define DEFAULT_PAGESIZE 4096 -const char* cargs['Z'] = {0}; +const char** cargs; long sys_pagesize; int main(int, char*[]); @@ -65,6 +65,7 @@ int main #define DONE -1 #define SCANPATH (cargs['d'] ? cargs['d'] : "./") { int opt; + cargs = (const char**) malloc('Z'); getopt: switch (opt = getopt(argc, argv, OPTS)) { case 'd' : @@ -88,38 +89,17 @@ int main sys_pagesize = DEFAULT_PAGESIZE; if (ir_init()) { perror("init"); + free(cargs); exit(EXIT_FAILURE); } -#if 0 if (scanner_scanpath(SCANPATH)) { perror("scanner"); + free(cargs); exit(EXIT_FAILURE); } -#endif - ir_class class; - ir_set set; - int i, j; - char wordbuf[0xFFF]; - for (class = ir_class_root(), i = 0, j = 0; i < 100; i++) - { sprintf(wordbuf,"Class%i",i); - class = ir_class_addchild(class,(uint8_t*)wordbuf); - sprintf(wordbuf,"c%i-s%i",i,j++); - set = ir_class_addset(class, (uint8_t*)wordbuf); - sprintf(wordbuf,"c%i-s%i",i,j++); - ir_class_addset(class, (uint8_t*)wordbuf); - sprintf(wordbuf,"c%i-s%i",i,j++); - ir_class_addset(class, (uint8_t*)wordbuf); - sprintf(wordbuf,"c%i-sc%i",i,j=0); - set = ir_set_addchild(set, (uint8_t*)wordbuf); - sprintf(wordbuf,"c%i-sc%i",i,++j); - ir_set_addchild(set, (uint8_t*)wordbuf); - sprintf(wordbuf,"c%i-sc%i",i,++j); - set = ir_set_addchild(set, (uint8_t*)wordbuf); - sprintf(wordbuf,"c%i-sb%i",i,j=0); - ir_set_addchild(set, (uint8_t*)wordbuf); - } ir_test(); ir_linker(); ir_condenser(); + free(cargs); exit(EXIT_SUCCESS); } -- 2.18.0 From aad17010d4fab99c1583930c98afff0575bcf944 Mon Sep 17 00:00:00 2001 From: ken Date: Thu, 19 Jan 2017 19:29:42 -0800 Subject: [PATCH 12/16] bug fixes, treewalk printing of classes/sets --- src/ir.c | 63 ++++++++++++++++++++++++++++---------------------------- 1 file changed, 31 insertions(+), 32 deletions(-) diff --git a/src/ir.c b/src/ir.c index e88ac36..0e95d7f 100644 --- a/src/ir.c +++ b/src/ir.c @@ -632,7 +632,7 @@ uint8_t* name_alloc copy: name = (uint8_t*)namepages.head->header.head; iter = name_src; - for (head_mem = PL_HEADMEM(namepages); *iter && *iter != '_' && head_mem; head_mem--) + for (head_mem = PL_HEADMEM(namepages); *iter && *iter != '_' && *iter != '.' && head_mem; head_mem--) *(namepages.head->header.head)++ = *iter++; if (head_mem < 1) //not enough room { pagelist_alloc(namepages); @@ -661,36 +661,36 @@ uint8_t* classname_alloc return name; } -static void crawl_class(struct ir_class_t*,int); +static void crawl_class(struct ir_class_t*); static void crawl_set(struct ir_set_t*,int); void ir_test(void) { uprintf("IR From Directory: %s\n",getcwd(NULL,255)); - crawl_class(&root_class,0); + crawl_class(&root_class); } -#define pspace(num) for (i = 0; i < (num); i++) putchar(' ') +#define pspace(num) for (i = 0; i < (num); i++) putchar('.') static void crawl_class -( struct ir_class_t* class, - int depth -) +( struct ir_class_t* class ) { struct ir_class_t* iter; - /*if(chdir((char*)class->name)) - eprintf("CHDIR %U\n",class->name); - else - wprintf("chdir %U\n",class->name);*/ - if (class->nextchild != NULL) - { iter = class->nextchild; - do { - crawl_class(iter,depth + 1); - /*if (chdir("..")) - eprintf("CHDIR ..\n");*/ - } while ((iter = iter->nextsib) != NULL); - } wprintf("%U/\n", class->name); + if(chdir((char*)class->name)) + eprintf("CHDIR %U from %s\n",class->name,getcwd(NULL,255)); + if (class->nextchild != NULL) + crawl_class(class->nextchild); if (class->root_set != NULL) - crawl_set(class->root_set,0); + crawl_set(class->root_set, 0); + if (class->nextsib != NULL) + { if (chdir("..")) + eprintf("CHDIR ..\n"); + for (iter = class->nextsib; iter != NULL; iter = iter->nextsib) + crawl_class(iter); + if(chdir((char*)class->name)) + eprintf("CHDIR %U from %s\n",class->name,getcwd(NULL,255)); + } uprintf("\n%U\\\n",class->name); + if (chdir("..")) + eprintf("CHDIR ..\n"); } static @@ -699,18 +699,17 @@ void crawl_set int depth ) { struct ir_set_t* iter; - int i = depth * 10; - pspace(i); + int i; + pspace(depth * 10); + i = 0; + for(iter = set; iter != NULL; iter = iter->nextchild, ++i) + uprintf("[%8U]", iter->name); + if (i) + putchar('\n'); i = 0; for(iter = set->nextchild; iter != NULL; iter = iter->nextchild) - { uprintf("[%8U]", iter->name); - } - for(iter = set->nextchild; iter != NULL; iter = iter->nextchild) - { if (iter->nextsib != NULL) - crawl_set(iter->nextsib, i); - i++; - } - for(iter = set->nextchild; iter != NULL; iter = iter->nextchild) - crawl_set(iter, depth + 1); - putchar('\n'); + if (iter->nextsib != NULL) + crawl_set(iter->nextsib, ++i); + for(iter = set->nextsib; iter != NULL; iter = iter->nextsib) + crawl_set(iter, depth); } -- 2.18.0 From 8b56606a960d7cbd61dd3031a3ee74b9a61bde31 Mon Sep 17 00:00:00 2001 From: ken Date: Thu, 19 Jan 2017 19:30:02 -0800 Subject: [PATCH 13/16] parser pops yyclass when unexpected CLCLOSE encountered --- src/parser.y | 11 +++++------ 1 file changed, 5 insertions(+), 6 deletions(-) diff --git a/src/parser.y b/src/parser.y index e1fe896..1677c6c 100644 --- a/src/parser.y +++ b/src/parser.y @@ -31,7 +31,7 @@ /* Stack-based class handler */ #define yyclass(CS) (*(CS->csp)) #define yyclassld(CS) (ir_classld_from_class(yyclass(CS))) - #define DEFAULT_VARIANT "default" + #define DEFAULT_VARIANT (uint8_t*)"default" } %define parse.error verbose %define parse.lac full @@ -85,7 +85,6 @@ class: NAME CLOPEN { yyclass_push(cs,ir_class_addchild(yyclass(cs), $1)); } progn CLCLOSE { yyclass_pop(cs); } -| CLCLOSE { yyclass_pop(cs); } ; statement_list: @@ -145,8 +144,10 @@ void yyerror ) { ir_class* iter; fprintf(stderr, "[class->"); - for (iter = cs->class_stack; iter < cs->csp; iter++) + for (iter = cs->class_stack; iter <= cs->csp; iter++) fprintf(stderr, "%s/", ir_class_name(*iter)); + if (strstr(s,"unexpected CLCLOSE") != NULL) + yyclass_pop(cs); fprintf(stderr, "]\n\t"); fprintf(stderr, "%s\n", s); } @@ -167,9 +168,7 @@ yycstate* yycstate_new static inline ir_class yyclass_pop ( yycstate* cs ) -{ cs->csp--; - return *(cs->csp + 1); -} +{ return *cs->csp--; } static inline ir_class yyclass_push -- 2.18.0 From 44b15998f0b17d98b4714e77a89fc90b2a2dc29e Mon Sep 17 00:00:00 2001 From: ken Date: Thu, 19 Jan 2017 21:48:33 -0800 Subject: [PATCH 14/16] fixed tree printing for real --- src/ir.c | 37 +++++++++++++++++++------------------ 1 file changed, 19 insertions(+), 18 deletions(-) diff --git a/src/ir.c b/src/ir.c index 0e95d7f..ab97305 100644 --- a/src/ir.c +++ b/src/ir.c @@ -101,7 +101,7 @@ struct ir_class_t uint8_t* name; }; struct ir_set_t -{ struct ir_set_t* nextchild, * nextsib; +{ struct ir_set_t* nextchild, * nextsib, * p; uint32_t ref; uint8_t* name; struct ir_framebox_t* frameboxes; @@ -672,8 +672,7 @@ void ir_test(void) static void crawl_class ( struct ir_class_t* class ) -{ struct ir_class_t* iter; - wprintf("%U/\n", class->name); +{ wprintf("%U/\n", class->name); if(chdir((char*)class->name)) eprintf("CHDIR %U from %s\n",class->name,getcwd(NULL,255)); if (class->nextchild != NULL) @@ -683,12 +682,11 @@ void crawl_class if (class->nextsib != NULL) { if (chdir("..")) eprintf("CHDIR ..\n"); - for (iter = class->nextsib; iter != NULL; iter = iter->nextsib) - crawl_class(iter); + crawl_class(class->nextsib); if(chdir((char*)class->name)) eprintf("CHDIR %U from %s\n",class->name,getcwd(NULL,255)); } - uprintf("\n%U\\\n",class->name); + uprintf("%U\\\n",class->name); if (chdir("..")) eprintf("CHDIR ..\n"); } @@ -698,18 +696,21 @@ void crawl_set ( struct ir_set_t* set, int depth ) -{ struct ir_set_t* iter; +{ struct ir_set_t* iter, * last; int i; - pspace(depth * 10); - i = 0; - for(iter = set; iter != NULL; iter = iter->nextchild, ++i) - uprintf("[%8U]", iter->name); - if (i) - putchar('\n'); - i = 0; - for(iter = set->nextchild; iter != NULL; iter = iter->nextchild) + pspace(depth * 12); + last = NULL; + i = depth; + for(iter = set; iter != NULL; iter = iter->nextchild) + { uprintf("[%10U]", iter->name); + if (last != NULL) + iter->p = last; + last = iter; + i++; + } + --i; + putchar('\n'); + for(iter = last; iter != NULL; iter = iter->p, --i) if (iter->nextsib != NULL) - crawl_set(iter->nextsib, ++i); - for(iter = set->nextsib; iter != NULL; iter = iter->nextsib) - crawl_set(iter, depth); + crawl_set(iter->nextsib,i); } -- 2.18.0 From c3a0924af9d497624fadd958c0dedead893be587 Mon Sep 17 00:00:00 2001 From: ken Date: Thu, 19 Jan 2017 22:03:49 -0800 Subject: [PATCH 15/16] submodule --- .gitmodules | 3 +++ 1 file changed, 3 insertions(+) create mode 100644 .gitmodules diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..f89b9e8 --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "xxHash"] + path = xxHash + url = ./xxHash -- 2.18.0 From 58d55a7a727ee375c48f0bcd35c142c7dfa60a1b Mon Sep 17 00:00:00 2001 From: ken Date: Thu, 19 Jan 2017 22:24:13 -0800 Subject: [PATCH 16/16] xxhash --- .gitmodules | 3 - xxHash | 1 - xxHash/xxhash.c | 888 ++++++++++++++++++++++++++++++++++++++++++++++++ xxHash/xxhash.h | 293 ++++++++++++++++ 4 files changed, 1181 insertions(+), 4 deletions(-) delete mode 100644 .gitmodules delete mode 160000 xxHash create mode 100644 xxHash/xxhash.c create mode 100644 xxHash/xxhash.h diff --git a/.gitmodules b/.gitmodules deleted file mode 100644 index f89b9e8..0000000 --- a/.gitmodules +++ /dev/null @@ -1,3 +0,0 @@ -[submodule "xxHash"] - path = xxHash - url = ./xxHash diff --git a/xxHash b/xxHash deleted file mode 160000 index 7fc5ce8..0000000 --- a/xxHash +++ /dev/null @@ -1 +0,0 @@ -Subproject commit 7fc5ce8592f10c68506f4a070bfa6a9ab2004b44 diff --git a/xxHash/xxhash.c b/xxHash/xxhash.c new file mode 100644 index 0000000..833b99f --- /dev/null +++ b/xxHash/xxhash.c @@ -0,0 +1,888 @@ +/* +* xxHash - Fast Hash algorithm +* Copyright (C) 2012-2016, Yann Collet +* +* BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) +* +* Redistribution and use in source and binary forms, with or without +* modification, are permitted provided that the following conditions are +* met: +* +* * Redistributions of source code must retain the above copyright +* notice, this list of conditions and the following disclaimer. +* * Redistributions in binary form must reproduce the above +* copyright notice, this list of conditions and the following disclaimer +* in the documentation and/or other materials provided with the +* distribution. +* +* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +* OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +* +* You can contact the author at : +* - xxHash homepage: http://www.xxhash.com +* - xxHash source repository : https://github.com/Cyan4973/xxHash +*/ + + +/* ************************************* +* Tuning parameters +***************************************/ +/*!XXH_FORCE_MEMORY_ACCESS : + * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. + * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. + * The below switch allow to select different access method for improved performance. + * Method 0 (default) : use `memcpy()`. Safe and portable. + * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). + * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. + * Method 2 : direct access. This method doesn't depend on compiler but violate C standard. + * It can generate buggy code on targets which do not support unaligned memory accesses. + * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) + * See http://stackoverflow.com/a/32095106/646947 for details. + * Prefer these methods in priority order (0 > 1 > 2) + */ +#ifndef XXH_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ +# if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) +# define XXH_FORCE_MEMORY_ACCESS 2 +# elif defined(__INTEL_COMPILER) || \ + (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) )) +# define XXH_FORCE_MEMORY_ACCESS 1 +# endif +#endif + +/*!XXH_ACCEPT_NULL_INPUT_POINTER : + * If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer. + * When this option is enabled, xxHash output for null input pointers will be the same as a null-length input. + * By default, this option is disabled. To enable it, uncomment below define : + */ +/* #define XXH_ACCEPT_NULL_INPUT_POINTER 1 */ + +/*!XXH_FORCE_NATIVE_FORMAT : + * By default, xxHash library provides endian-independent Hash values, based on little-endian convention. + * Results are therefore identical for little-endian and big-endian CPU. + * This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format. + * Should endian-independence be of no importance for your application, you may set the #define below to 1, + * to improve speed for Big-endian CPU. + * This option has no impact on Little_Endian CPU. + */ +#ifndef XXH_FORCE_NATIVE_FORMAT /* can be defined externally */ +# define XXH_FORCE_NATIVE_FORMAT 0 +#endif + +/*!XXH_FORCE_ALIGN_CHECK : + * This is a minor performance trick, only useful with lots of very small keys. + * It means : check for aligned/unaligned input. + * The check costs one initial branch per hash; + * set it to 0 when the input is guaranteed to be aligned, + * or when alignment doesn't matter for performance. + */ +#ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */ +# if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64) +# define XXH_FORCE_ALIGN_CHECK 0 +# else +# define XXH_FORCE_ALIGN_CHECK 1 +# endif +#endif + + +/* ************************************* +* Includes & Memory related functions +***************************************/ +/*! Modify the local functions below should you wish to use some other memory routines +* for malloc(), free() */ +#include +static void* XXH_malloc(size_t s) { return malloc(s); } +static void XXH_free (void* p) { free(p); } +/*! and for memcpy() */ +#include +static void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); } + +#define XXH_STATIC_LINKING_ONLY +#include "xxhash.h" + + +/* ************************************* +* Compiler Specific Options +***************************************/ +#ifdef _MSC_VER /* Visual Studio */ +# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ +# define FORCE_INLINE static __forceinline +#else +# if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ +# ifdef __GNUC__ +# define FORCE_INLINE static inline __attribute__((always_inline)) +# else +# define FORCE_INLINE static inline +# endif +# else +# define FORCE_INLINE static +# endif /* __STDC_VERSION__ */ +#endif + + +/* ************************************* +* Basic Types +***************************************/ +#ifndef MEM_MODULE +# if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) +# include + typedef uint8_t BYTE; + typedef uint16_t U16; + typedef uint32_t U32; +# else + typedef unsigned char BYTE; + typedef unsigned short U16; + typedef unsigned int U32; +# endif +#endif + +#if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2)) + +/* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */ +static U32 XXH_read32(const void* memPtr) { return *(const U32*) memPtr; } + +#elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1)) + +/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ +/* currently only defined for gcc and icc */ +typedef union { U32 u32; } __attribute__((packed)) unalign; +static U32 XXH_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } + +#else + +/* portable and safe solution. Generally efficient. + * see : http://stackoverflow.com/a/32095106/646947 + */ +static U32 XXH_read32(const void* memPtr) +{ + U32 val; + memcpy(&val, memPtr, sizeof(val)); + return val; +} + +#endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */ + + +/* **************************************** +* Compiler-specific Functions and Macros +******************************************/ +#define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) + +/* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */ +#if defined(_MSC_VER) +# define XXH_rotl32(x,r) _rotl(x,r) +# define XXH_rotl64(x,r) _rotl64(x,r) +#else +# define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r))) +# define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r))) +#endif + +#if defined(_MSC_VER) /* Visual Studio */ +# define XXH_swap32 _byteswap_ulong +#elif XXH_GCC_VERSION >= 403 +# define XXH_swap32 __builtin_bswap32 +#else +static U32 XXH_swap32 (U32 x) +{ + return ((x << 24) & 0xff000000 ) | + ((x << 8) & 0x00ff0000 ) | + ((x >> 8) & 0x0000ff00 ) | + ((x >> 24) & 0x000000ff ); +} +#endif + + +/* ************************************* +* Architecture Macros +***************************************/ +typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess; + +/* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example on the compiler command line */ +#ifndef XXH_CPU_LITTLE_ENDIAN + static const int g_one = 1; +# define XXH_CPU_LITTLE_ENDIAN (*(const char*)(&g_one)) +#endif + + +/* *************************** +* Memory reads +*****************************/ +typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment; + +FORCE_INLINE U32 XXH_readLE32_align(const void* ptr, XXH_endianess endian, XXH_alignment align) +{ + if (align==XXH_unaligned) + return endian==XXH_littleEndian ? XXH_read32(ptr) : XXH_swap32(XXH_read32(ptr)); + else + return endian==XXH_littleEndian ? *(const U32*)ptr : XXH_swap32(*(const U32*)ptr); +} + +FORCE_INLINE U32 XXH_readLE32(const void* ptr, XXH_endianess endian) +{ + return XXH_readLE32_align(ptr, endian, XXH_unaligned); +} + +static U32 XXH_readBE32(const void* ptr) +{ + return XXH_CPU_LITTLE_ENDIAN ? XXH_swap32(XXH_read32(ptr)) : XXH_read32(ptr); +} + + +/* ************************************* +* Macros +***************************************/ +#define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ +XXH_PUBLIC_API unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER; } + + +/* ******************************************************************* +* 32-bits hash functions +*********************************************************************/ +static const U32 PRIME32_1 = 2654435761U; +static const U32 PRIME32_2 = 2246822519U; +static const U32 PRIME32_3 = 3266489917U; +static const U32 PRIME32_4 = 668265263U; +static const U32 PRIME32_5 = 374761393U; + +static U32 XXH32_round(U32 seed, U32 input) +{ + seed += input * PRIME32_2; + seed = XXH_rotl32(seed, 13); + seed *= PRIME32_1; + return seed; +} + +FORCE_INLINE U32 XXH32_endian_align(const void* input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align) +{ + const BYTE* p = (const BYTE*)input; + const BYTE* bEnd = p + len; + U32 h32; +#define XXH_get32bits(p) XXH_readLE32_align(p, endian, align) + +#ifdef XXH_ACCEPT_NULL_INPUT_POINTER + if (p==NULL) { + len=0; + bEnd=p=(const BYTE*)(size_t)16; + } +#endif + + if (len>=16) { + const BYTE* const limit = bEnd - 16; + U32 v1 = seed + PRIME32_1 + PRIME32_2; + U32 v2 = seed + PRIME32_2; + U32 v3 = seed + 0; + U32 v4 = seed - PRIME32_1; + + do { + v1 = XXH32_round(v1, XXH_get32bits(p)); p+=4; + v2 = XXH32_round(v2, XXH_get32bits(p)); p+=4; + v3 = XXH32_round(v3, XXH_get32bits(p)); p+=4; + v4 = XXH32_round(v4, XXH_get32bits(p)); p+=4; + } while (p<=limit); + + h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18); + } else { + h32 = seed + PRIME32_5; + } + + h32 += (U32) len; + + while (p+4<=bEnd) { + h32 += XXH_get32bits(p) * PRIME32_3; + h32 = XXH_rotl32(h32, 17) * PRIME32_4 ; + p+=4; + } + + while (p> 15; + h32 *= PRIME32_2; + h32 ^= h32 >> 13; + h32 *= PRIME32_3; + h32 ^= h32 >> 16; + + return h32; +} + + +XXH_PUBLIC_API unsigned int XXH32 (const void* input, size_t len, unsigned int seed) +{ +#if 0 + /* Simple version, good for code maintenance, but unfortunately slow for small inputs */ + XXH32_state_t state; + XXH32_reset(&state, seed); + XXH32_update(&state, input, len); + return XXH32_digest(&state); +#else + XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; + + if (XXH_FORCE_ALIGN_CHECK) { + if ((((size_t)input) & 3) == 0) { /* Input is 4-bytes aligned, leverage the speed benefit */ + if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) + return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); + else + return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); + } } + + if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) + return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned); + else + return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); +#endif +} + + + +/*====== Hash streaming ======*/ + +XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void) +{ + return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t)); +} +XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr) +{ + XXH_free(statePtr); + return XXH_OK; +} + +XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* dstState, const XXH32_state_t* srcState) +{ + memcpy(dstState, srcState, sizeof(*dstState)); +} + +XXH_PUBLIC_API XXH_errorcode XXH32_reset(XXH32_state_t* statePtr, unsigned int seed) +{ + XXH32_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */ + memset(&state, 0, sizeof(state)-4); /* do not write into reserved, for future removal */ + state.v1 = seed + PRIME32_1 + PRIME32_2; + state.v2 = seed + PRIME32_2; + state.v3 = seed + 0; + state.v4 = seed - PRIME32_1; + memcpy(statePtr, &state, sizeof(state)); + return XXH_OK; +} + + +FORCE_INLINE XXH_errorcode XXH32_update_endian (XXH32_state_t* state, const void* input, size_t len, XXH_endianess endian) +{ + const BYTE* p = (const BYTE*)input; + const BYTE* const bEnd = p + len; + +#ifdef XXH_ACCEPT_NULL_INPUT_POINTER + if (input==NULL) return XXH_ERROR; +#endif + + state->total_len_32 += (unsigned)len; + state->large_len |= (len>=16) | (state->total_len_32>=16); + + if (state->memsize + len < 16) { /* fill in tmp buffer */ + XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, len); + state->memsize += (unsigned)len; + return XXH_OK; + } + + if (state->memsize) { /* some data left from previous update */ + XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, 16-state->memsize); + { const U32* p32 = state->mem32; + state->v1 = XXH32_round(state->v1, XXH_readLE32(p32, endian)); p32++; + state->v2 = XXH32_round(state->v2, XXH_readLE32(p32, endian)); p32++; + state->v3 = XXH32_round(state->v3, XXH_readLE32(p32, endian)); p32++; + state->v4 = XXH32_round(state->v4, XXH_readLE32(p32, endian)); + } + p += 16-state->memsize; + state->memsize = 0; + } + + if (p <= bEnd-16) { + const BYTE* const limit = bEnd - 16; + U32 v1 = state->v1; + U32 v2 = state->v2; + U32 v3 = state->v3; + U32 v4 = state->v4; + + do { + v1 = XXH32_round(v1, XXH_readLE32(p, endian)); p+=4; + v2 = XXH32_round(v2, XXH_readLE32(p, endian)); p+=4; + v3 = XXH32_round(v3, XXH_readLE32(p, endian)); p+=4; + v4 = XXH32_round(v4, XXH_readLE32(p, endian)); p+=4; + } while (p<=limit); + + state->v1 = v1; + state->v2 = v2; + state->v3 = v3; + state->v4 = v4; + } + + if (p < bEnd) { + XXH_memcpy(state->mem32, p, (size_t)(bEnd-p)); + state->memsize = (unsigned)(bEnd-p); + } + + return XXH_OK; +} + +XXH_PUBLIC_API XXH_errorcode XXH32_update (XXH32_state_t* state_in, const void* input, size_t len) +{ + XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; + + if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) + return XXH32_update_endian(state_in, input, len, XXH_littleEndian); + else + return XXH32_update_endian(state_in, input, len, XXH_bigEndian); +} + + + +FORCE_INLINE U32 XXH32_digest_endian (const XXH32_state_t* state, XXH_endianess endian) +{ + const BYTE * p = (const BYTE*)state->mem32; + const BYTE* const bEnd = (const BYTE*)(state->mem32) + state->memsize; + U32 h32; + + if (state->large_len) { + h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18); + } else { + h32 = state->v3 /* == seed */ + PRIME32_5; + } + + h32 += state->total_len_32; + + while (p+4<=bEnd) { + h32 += XXH_readLE32(p, endian) * PRIME32_3; + h32 = XXH_rotl32(h32, 17) * PRIME32_4; + p+=4; + } + + while (p> 15; + h32 *= PRIME32_2; + h32 ^= h32 >> 13; + h32 *= PRIME32_3; + h32 ^= h32 >> 16; + + return h32; +} + + +XXH_PUBLIC_API unsigned int XXH32_digest (const XXH32_state_t* state_in) +{ + XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; + + if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) + return XXH32_digest_endian(state_in, XXH_littleEndian); + else + return XXH32_digest_endian(state_in, XXH_bigEndian); +} + + +/*====== Canonical representation ======*/ + +/*! Default XXH result types are basic unsigned 32 and 64 bits. +* The canonical representation follows human-readable write convention, aka big-endian (large digits first). +* These functions allow transformation of hash result into and from its canonical format. +* This way, hash values can be written into a file or buffer, and remain comparable across different systems and programs. +*/ + +XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash) +{ + XXH_STATIC_ASSERT(sizeof(XXH32_canonical_t) == sizeof(XXH32_hash_t)); + if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap32(hash); + memcpy(dst, &hash, sizeof(*dst)); +} + +XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src) +{ + return XXH_readBE32(src); +} + + +#ifndef XXH_NO_LONG_LONG + +/* ******************************************************************* +* 64-bits hash functions +*********************************************************************/ + +/*====== Memory access ======*/ + +#ifndef MEM_MODULE +# define MEM_MODULE +# if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) +# include + typedef uint64_t U64; +# else + typedef unsigned long long U64; /* if your compiler doesn't support unsigned long long, replace by another 64-bit type here. Note that xxhash.h will also need to be updated. */ +# endif +#endif + + +#if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2)) + +/* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */ +static U64 XXH_read64(const void* memPtr) { return *(const U64*) memPtr; } + +#elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1)) + +/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ +/* currently only defined for gcc and icc */ +typedef union { U32 u32; U64 u64; } __attribute__((packed)) unalign64; +static U64 XXH_read64(const void* ptr) { return ((const unalign64*)ptr)->u64; } + +#else + +/* portable and safe solution. Generally efficient. + * see : http://stackoverflow.com/a/32095106/646947 + */ + +static U64 XXH_read64(const void* memPtr) +{ + U64 val; + memcpy(&val, memPtr, sizeof(val)); + return val; +} + +#endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */ + +#if defined(_MSC_VER) /* Visual Studio */ +# define XXH_swap64 _byteswap_uint64 +#elif XXH_GCC_VERSION >= 403 +# define XXH_swap64 __builtin_bswap64 +#else +static U64 XXH_swap64 (U64 x) +{ + return ((x << 56) & 0xff00000000000000ULL) | + ((x << 40) & 0x00ff000000000000ULL) | + ((x << 24) & 0x0000ff0000000000ULL) | + ((x << 8) & 0x000000ff00000000ULL) | + ((x >> 8) & 0x00000000ff000000ULL) | + ((x >> 24) & 0x0000000000ff0000ULL) | + ((x >> 40) & 0x000000000000ff00ULL) | + ((x >> 56) & 0x00000000000000ffULL); +} +#endif + +FORCE_INLINE U64 XXH_readLE64_align(const void* ptr, XXH_endianess endian, XXH_alignment align) +{ + if (align==XXH_unaligned) + return endian==XXH_littleEndian ? XXH_read64(ptr) : XXH_swap64(XXH_read64(ptr)); + else + return endian==XXH_littleEndian ? *(const U64*)ptr : XXH_swap64(*(const U64*)ptr); +} + +FORCE_INLINE U64 XXH_readLE64(const void* ptr, XXH_endianess endian) +{ + return XXH_readLE64_align(ptr, endian, XXH_unaligned); +} + +static U64 XXH_readBE64(const void* ptr) +{ + return XXH_CPU_LITTLE_ENDIAN ? XXH_swap64(XXH_read64(ptr)) : XXH_read64(ptr); +} + + +/*====== xxh64 ======*/ + +static const U64 PRIME64_1 = 11400714785074694791ULL; +static const U64 PRIME64_2 = 14029467366897019727ULL; +static const U64 PRIME64_3 = 1609587929392839161ULL; +static const U64 PRIME64_4 = 9650029242287828579ULL; +static const U64 PRIME64_5 = 2870177450012600261ULL; + +static U64 XXH64_round(U64 acc, U64 input) +{ + acc += input * PRIME64_2; + acc = XXH_rotl64(acc, 31); + acc *= PRIME64_1; + return acc; +} + +static U64 XXH64_mergeRound(U64 acc, U64 val) +{ + val = XXH64_round(0, val); + acc ^= val; + acc = acc * PRIME64_1 + PRIME64_4; + return acc; +} + +FORCE_INLINE U64 XXH64_endian_align(const void* input, size_t len, U64 seed, XXH_endianess endian, XXH_alignment align) +{ + const BYTE* p = (const BYTE*)input; + const BYTE* bEnd = p + len; + U64 h64; +#define XXH_get64bits(p) XXH_readLE64_align(p, endian, align) + +#ifdef XXH_ACCEPT_NULL_INPUT_POINTER + if (p==NULL) { + len=0; + bEnd=p=(const BYTE*)(size_t)32; + } +#endif + + if (len>=32) { + const BYTE* const limit = bEnd - 32; + U64 v1 = seed + PRIME64_1 + PRIME64_2; + U64 v2 = seed + PRIME64_2; + U64 v3 = seed + 0; + U64 v4 = seed - PRIME64_1; + + do { + v1 = XXH64_round(v1, XXH_get64bits(p)); p+=8; + v2 = XXH64_round(v2, XXH_get64bits(p)); p+=8; + v3 = XXH64_round(v3, XXH_get64bits(p)); p+=8; + v4 = XXH64_round(v4, XXH_get64bits(p)); p+=8; + } while (p<=limit); + + h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); + h64 = XXH64_mergeRound(h64, v1); + h64 = XXH64_mergeRound(h64, v2); + h64 = XXH64_mergeRound(h64, v3); + h64 = XXH64_mergeRound(h64, v4); + + } else { + h64 = seed + PRIME64_5; + } + + h64 += (U64) len; + + while (p+8<=bEnd) { + U64 const k1 = XXH64_round(0, XXH_get64bits(p)); + h64 ^= k1; + h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4; + p+=8; + } + + if (p+4<=bEnd) { + h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1; + h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; + p+=4; + } + + while (p> 33; + h64 *= PRIME64_2; + h64 ^= h64 >> 29; + h64 *= PRIME64_3; + h64 ^= h64 >> 32; + + return h64; +} + + +XXH_PUBLIC_API unsigned long long XXH64 (const void* input, size_t len, unsigned long long seed) +{ +#if 0 + /* Simple version, good for code maintenance, but unfortunately slow for small inputs */ + XXH64_state_t state; + XXH64_reset(&state, seed); + XXH64_update(&state, input, len); + return XXH64_digest(&state); +#else + XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; + + if (XXH_FORCE_ALIGN_CHECK) { + if ((((size_t)input) & 7)==0) { /* Input is aligned, let's leverage the speed advantage */ + if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) + return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); + else + return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); + } } + + if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) + return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned); + else + return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); +#endif +} + +/*====== Hash Streaming ======*/ + +XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void) +{ + return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t)); +} +XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr) +{ + XXH_free(statePtr); + return XXH_OK; +} + +XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* dstState, const XXH64_state_t* srcState) +{ + memcpy(dstState, srcState, sizeof(*dstState)); +} + +XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t* statePtr, unsigned long long seed) +{ + XXH64_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */ + memset(&state, 0, sizeof(state)-8); /* do not write into reserved, for future removal */ + state.v1 = seed + PRIME64_1 + PRIME64_2; + state.v2 = seed + PRIME64_2; + state.v3 = seed + 0; + state.v4 = seed - PRIME64_1; + memcpy(statePtr, &state, sizeof(state)); + return XXH_OK; +} + +FORCE_INLINE XXH_errorcode XXH64_update_endian (XXH64_state_t* state, const void* input, size_t len, XXH_endianess endian) +{ + const BYTE* p = (const BYTE*)input; + const BYTE* const bEnd = p + len; + +#ifdef XXH_ACCEPT_NULL_INPUT_POINTER + if (input==NULL) return XXH_ERROR; +#endif + + state->total_len += len; + + if (state->memsize + len < 32) { /* fill in tmp buffer */ + XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, len); + state->memsize += (U32)len; + return XXH_OK; + } + + if (state->memsize) { /* tmp buffer is full */ + XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, 32-state->memsize); + state->v1 = XXH64_round(state->v1, XXH_readLE64(state->mem64+0, endian)); + state->v2 = XXH64_round(state->v2, XXH_readLE64(state->mem64+1, endian)); + state->v3 = XXH64_round(state->v3, XXH_readLE64(state->mem64+2, endian)); + state->v4 = XXH64_round(state->v4, XXH_readLE64(state->mem64+3, endian)); + p += 32-state->memsize; + state->memsize = 0; + } + + if (p+32 <= bEnd) { + const BYTE* const limit = bEnd - 32; + U64 v1 = state->v1; + U64 v2 = state->v2; + U64 v3 = state->v3; + U64 v4 = state->v4; + + do { + v1 = XXH64_round(v1, XXH_readLE64(p, endian)); p+=8; + v2 = XXH64_round(v2, XXH_readLE64(p, endian)); p+=8; + v3 = XXH64_round(v3, XXH_readLE64(p, endian)); p+=8; + v4 = XXH64_round(v4, XXH_readLE64(p, endian)); p+=8; + } while (p<=limit); + + state->v1 = v1; + state->v2 = v2; + state->v3 = v3; + state->v4 = v4; + } + + if (p < bEnd) { + XXH_memcpy(state->mem64, p, (size_t)(bEnd-p)); + state->memsize = (unsigned)(bEnd-p); + } + + return XXH_OK; +} + +XXH_PUBLIC_API XXH_errorcode XXH64_update (XXH64_state_t* state_in, const void* input, size_t len) +{ + XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; + + if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) + return XXH64_update_endian(state_in, input, len, XXH_littleEndian); + else + return XXH64_update_endian(state_in, input, len, XXH_bigEndian); +} + +FORCE_INLINE U64 XXH64_digest_endian (const XXH64_state_t* state, XXH_endianess endian) +{ + const BYTE * p = (const BYTE*)state->mem64; + const BYTE* const bEnd = (const BYTE*)state->mem64 + state->memsize; + U64 h64; + + if (state->total_len >= 32) { + U64 const v1 = state->v1; + U64 const v2 = state->v2; + U64 const v3 = state->v3; + U64 const v4 = state->v4; + + h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); + h64 = XXH64_mergeRound(h64, v1); + h64 = XXH64_mergeRound(h64, v2); + h64 = XXH64_mergeRound(h64, v3); + h64 = XXH64_mergeRound(h64, v4); + } else { + h64 = state->v3 + PRIME64_5; + } + + h64 += (U64) state->total_len; + + while (p+8<=bEnd) { + U64 const k1 = XXH64_round(0, XXH_readLE64(p, endian)); + h64 ^= k1; + h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4; + p+=8; + } + + if (p+4<=bEnd) { + h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1; + h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; + p+=4; + } + + while (p> 33; + h64 *= PRIME64_2; + h64 ^= h64 >> 29; + h64 *= PRIME64_3; + h64 ^= h64 >> 32; + + return h64; +} + +XXH_PUBLIC_API unsigned long long XXH64_digest (const XXH64_state_t* state_in) +{ + XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; + + if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) + return XXH64_digest_endian(state_in, XXH_littleEndian); + else + return XXH64_digest_endian(state_in, XXH_bigEndian); +} + + +/*====== Canonical representation ======*/ + +XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash) +{ + XXH_STATIC_ASSERT(sizeof(XXH64_canonical_t) == sizeof(XXH64_hash_t)); + if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap64(hash); + memcpy(dst, &hash, sizeof(*dst)); +} + +XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src) +{ + return XXH_readBE64(src); +} + +#endif /* XXH_NO_LONG_LONG */ diff --git a/xxHash/xxhash.h b/xxHash/xxhash.h new file mode 100644 index 0000000..9d831e0 --- /dev/null +++ b/xxHash/xxhash.h @@ -0,0 +1,293 @@ +/* + xxHash - Extremely Fast Hash algorithm + Header File + Copyright (C) 2012-2016, Yann Collet. + + BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are + met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + copyright notice, this list of conditions and the following disclaimer + in the documentation and/or other materials provided with the + distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + + You can contact the author at : + - xxHash source repository : https://github.com/Cyan4973/xxHash +*/ + +/* Notice extracted from xxHash homepage : + +xxHash is an extremely fast Hash algorithm, running at RAM speed limits. +It also successfully passes all tests from the SMHasher suite. + +Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz) + +Name Speed Q.Score Author +xxHash 5.4 GB/s 10 +CrapWow 3.2 GB/s 2 Andrew +MumurHash 3a 2.7 GB/s 10 Austin Appleby +SpookyHash 2.0 GB/s 10 Bob Jenkins +SBox 1.4 GB/s 9 Bret Mulvey +Lookup3 1.2 GB/s 9 Bob Jenkins +SuperFastHash 1.2 GB/s 1 Paul Hsieh +CityHash64 1.05 GB/s 10 Pike & Alakuijala +FNV 0.55 GB/s 5 Fowler, Noll, Vo +CRC32 0.43 GB/s 9 +MD5-32 0.33 GB/s 10 Ronald L. Rivest +SHA1-32 0.28 GB/s 10 + +Q.Score is a measure of quality of the hash function. +It depends on successfully passing SMHasher test set. +10 is a perfect score. + +A 64-bits version, named XXH64, is available since r35. +It offers much better speed, but for 64-bits applications only. +Name Speed on 64 bits Speed on 32 bits +XXH64 13.8 GB/s 1.9 GB/s +XXH32 6.8 GB/s 6.0 GB/s +*/ + +#ifndef XXHASH_H_5627135585666179 +#define XXHASH_H_5627135585666179 1 + +#if defined (__cplusplus) +extern "C" { +#endif + + +/* **************************** +* Definitions +******************************/ +#include /* size_t */ +typedef enum { XXH_OK=0, XXH_ERROR } XXH_errorcode; + + +/* **************************** +* API modifier +******************************/ +/** XXH_PRIVATE_API +* This is useful to include xxhash functions in `static` mode +* in order to inline them, and remove their symbol from the public list. +* Methodology : +* #define XXH_PRIVATE_API +* #include "xxhash.h" +* `xxhash.c` is automatically included. +* It's not useful to compile and link it as a separate module. +*/ +#ifdef XXH_PRIVATE_API +# ifndef XXH_STATIC_LINKING_ONLY +# define XXH_STATIC_LINKING_ONLY +# endif +# if defined(__GNUC__) +# define XXH_PUBLIC_API static __inline __attribute__((unused)) +# elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) +# define XXH_PUBLIC_API static inline +# elif defined(_MSC_VER) +# define XXH_PUBLIC_API static __inline +# else +# define XXH_PUBLIC_API static /* this version may generate warnings for unused static functions; disable the relevant warning */ +# endif +#else +# define XXH_PUBLIC_API /* do nothing */ +#endif /* XXH_PRIVATE_API */ + +/*!XXH_NAMESPACE, aka Namespace Emulation : + +If you want to include _and expose_ xxHash functions from within your own library, +but also want to avoid symbol collisions with other libraries which may also include xxHash, + +you can use XXH_NAMESPACE, to automatically prefix any public symbol from xxhash library +with the value of XXH_NAMESPACE (therefore, avoid NULL and numeric values). + +Note that no change is required within the calling program as long as it includes `xxhash.h` : +regular symbol name will be automatically translated by this header. +*/ +#ifdef XXH_NAMESPACE +# define XXH_CAT(A,B) A##B +# define XXH_NAME2(A,B) XXH_CAT(A,B) +# define XXH_versionNumber XXH_NAME2(XXH_NAMESPACE, XXH_versionNumber) +# define XXH32 XXH_NAME2(XXH_NAMESPACE, XXH32) +# define XXH32_createState XXH_NAME2(XXH_NAMESPACE, XXH32_createState) +# define XXH32_freeState XXH_NAME2(XXH_NAMESPACE, XXH32_freeState) +# define XXH32_reset XXH_NAME2(XXH_NAMESPACE, XXH32_reset) +# define XXH32_update XXH_NAME2(XXH_NAMESPACE, XXH32_update) +# define XXH32_digest XXH_NAME2(XXH_NAMESPACE, XXH32_digest) +# define XXH32_copyState XXH_NAME2(XXH_NAMESPACE, XXH32_copyState) +# define XXH32_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH32_canonicalFromHash) +# define XXH32_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH32_hashFromCanonical) +# define XXH64 XXH_NAME2(XXH_NAMESPACE, XXH64) +# define XXH64_createState XXH_NAME2(XXH_NAMESPACE, XXH64_createState) +# define XXH64_freeState XXH_NAME2(XXH_NAMESPACE, XXH64_freeState) +# define XXH64_reset XXH_NAME2(XXH_NAMESPACE, XXH64_reset) +# define XXH64_update XXH_NAME2(XXH_NAMESPACE, XXH64_update) +# define XXH64_digest XXH_NAME2(XXH_NAMESPACE, XXH64_digest) +# define XXH64_copyState XXH_NAME2(XXH_NAMESPACE, XXH64_copyState) +# define XXH64_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH64_canonicalFromHash) +# define XXH64_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH64_hashFromCanonical) +#endif + + +/* ************************************* +* Version +***************************************/ +#define XXH_VERSION_MAJOR 0 +#define XXH_VERSION_MINOR 6 +#define XXH_VERSION_RELEASE 2 +#define XXH_VERSION_NUMBER (XXH_VERSION_MAJOR *100*100 + XXH_VERSION_MINOR *100 + XXH_VERSION_RELEASE) +XXH_PUBLIC_API unsigned XXH_versionNumber (void); + + +/*-********************************************************************** +* 32-bits hash +************************************************************************/ +typedef unsigned int XXH32_hash_t; + +/*! XXH32() : + Calculate the 32-bits hash of sequence "length" bytes stored at memory address "input". + The memory between input & input+length must be valid (allocated and read-accessible). + "seed" can be used to alter the result predictably. + Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s */ +XXH_PUBLIC_API XXH32_hash_t XXH32 (const void* input, size_t length, unsigned int seed); + +/*====== Streaming ======*/ +typedef struct XXH32_state_s XXH32_state_t; /* incomplete type */ +XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void); +XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr); +XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* dst_state, const XXH32_state_t* src_state); + +XXH_PUBLIC_API XXH_errorcode XXH32_reset (XXH32_state_t* statePtr, unsigned int seed); +XXH_PUBLIC_API XXH_errorcode XXH32_update (XXH32_state_t* statePtr, const void* input, size_t length); +XXH_PUBLIC_API XXH32_hash_t XXH32_digest (const XXH32_state_t* statePtr); + +/* +These functions generate the xxHash of an input provided in multiple segments. +Note that, for small input, they are slower than single-call functions, due to state management. +For small input, prefer `XXH32()` and `XXH64()` . + +XXH state must first be allocated, using XXH*_createState() . + +Start a new hash by initializing state with a seed, using XXH*_reset(). + +Then, feed the hash state by calling XXH*_update() as many times as necessary. +Obviously, input must be allocated and read accessible. +The function returns an error code, with 0 meaning OK, and any other value meaning there is an error. + +Finally, a hash value can be produced anytime, by using XXH*_digest(). +This function returns the nn-bits hash as an int or long long. + +It's still possible to continue inserting input into the hash state after a digest, +and generate some new hashes later on, by calling again XXH*_digest(). + +When done, free XXH state space if it was allocated dynamically. +*/ + +/*====== Canonical representation ======*/ + +typedef struct { unsigned char digest[4]; } XXH32_canonical_t; +XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash); +XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src); + +/* Default result type for XXH functions are primitive unsigned 32 and 64 bits. +* The canonical representation uses human-readable write convention, aka big-endian (large digits first). +* These functions allow transformation of hash result into and from its canonical format. +* This way, hash values can be written into a file / memory, and remain comparable on different systems and programs. +*/ + + +#ifndef XXH_NO_LONG_LONG +/*-********************************************************************** +* 64-bits hash +************************************************************************/ +typedef unsigned long long XXH64_hash_t; + +/*! XXH64() : + Calculate the 64-bits hash of sequence of length "len" stored at memory address "input". + "seed" can be used to alter the result predictably. + This function runs faster on 64-bits systems, but slower on 32-bits systems (see benchmark). +*/ +XXH_PUBLIC_API XXH64_hash_t XXH64 (const void* input, size_t length, unsigned long long seed); + +/*====== Streaming ======*/ +typedef struct XXH64_state_s XXH64_state_t; /* incomplete type */ +XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void); +XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr); +XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* dst_state, const XXH64_state_t* src_state); + +XXH_PUBLIC_API XXH_errorcode XXH64_reset (XXH64_state_t* statePtr, unsigned long long seed); +XXH_PUBLIC_API XXH_errorcode XXH64_update (XXH64_state_t* statePtr, const void* input, size_t length); +XXH_PUBLIC_API XXH64_hash_t XXH64_digest (const XXH64_state_t* statePtr); + +/*====== Canonical representation ======*/ +typedef struct { unsigned char digest[8]; } XXH64_canonical_t; +XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash); +XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src); +#endif /* XXH_NO_LONG_LONG */ + + +#ifdef XXH_STATIC_LINKING_ONLY + +/* ================================================================================================ + This section contains definitions which are not guaranteed to remain stable. + They may change in future versions, becoming incompatible with a different version of the library. + They shall only be used with static linking. + Never use these definitions in association with dynamic linking ! +=================================================================================================== */ + +/* These definitions are only meant to make possible + static allocation of XXH state, on stack or in a struct for example. + Never use members directly. */ + +struct XXH32_state_s { + unsigned total_len_32; + unsigned large_len; + unsigned v1; + unsigned v2; + unsigned v3; + unsigned v4; + unsigned mem32[4]; /* buffer defined as U32 for alignment */ + unsigned memsize; + unsigned reserved; /* never read nor write, will be removed in a future version */ +}; /* typedef'd to XXH32_state_t */ + +#ifndef XXH_NO_LONG_LONG /* remove 64-bits support */ +struct XXH64_state_s { + unsigned long long total_len; + unsigned long long v1; + unsigned long long v2; + unsigned long long v3; + unsigned long long v4; + unsigned long long mem64[4]; /* buffer defined as U64 for alignment */ + unsigned memsize; + unsigned reserved[2]; /* never read nor write, will be removed in a future version */ +}; /* typedef'd to XXH64_state_t */ +#endif + +#ifdef XXH_PRIVATE_API +# include "xxhash.c" /* include xxhash function bodies as `static`, for inlining */ +#endif + +#endif /* XXH_STATIC_LINKING_ONLY */ + + +#if defined (__cplusplus) +} +#endif + +#endif /* XXHASH_H_5627135585666179 */ -- 2.18.0