From 5382b5fde5add82ebd492e97a458a824503fbd8d Mon Sep 17 00:00:00 2001 From: =?utf8?q?Kim=20Nguy=E1=BB=85n?= Date: Wed, 18 Apr 2012 14:56:09 +0200 Subject: [PATCH] Various fixes and cosmetic changes. --- Makefile | 14 ++- bp-core.c | 320 ++++++++++++++++++++++++++-------------------------- bp-darray.c | 29 +++++ bp-darray.h | 1 + bp-utils.h | 21 ++-- bp.c | 66 ++++++++++- bp.h | 13 ++- 7 files changed, 284 insertions(+), 180 deletions(-) diff --git a/Makefile b/Makefile index 3effd67..59e83a1 100644 --- a/Makefile +++ b/Makefile @@ -1,7 +1,7 @@ POPCOUNT=$(shell grep -q popcnt /proc/cpuinfo && echo 1) ifeq ($(POPCOUNT), 1) - POPCOUNT_FLAG=-DHAS_NATIVE_POPCOUNT + POPCOUNT_FLAG=-DHAS_NATIVE_POPCOUNT -mpopcnt -mtune=corei7 -march=corei7 else #POPCOUNT_FLAG=-DHAS_POPCOUNT_TABLE POPCOUNT_FLAG= @@ -16,14 +16,20 @@ endif ifeq ($(DEBUG), true) OPT_FLAGS=-O0 -g $(POPCOUNT_FLAG) -static else - OPT_FLAGS=-O4 $(POPCOUNT_FLAG) -static -flto + OPT_FLAGS=-O3 $(POPCOUNT_FLAG) -static -flto endif +ifeq ($(PROFILE), true) + PROF_FLAGS=-pg -g +else + PROF_FLAGS= +endif + INC_FLAGS=-I. -CFLAGS= $(INC_FLAGS) $(OPT_FLAGS) -CXXFLAGS= $(INC_FLAGS) $(OPT_FLAGS) +CFLAGS= $(INC_FLAGS) $(OPT_FLAGS) $(PROF_FLAGS) +CXXFLAGS= $(INC_FLAGS) $(OPT_FLAGS) $(PROF_FLAGS) CC=g++ diff --git a/bp-core.c b/bp-core.c index 70a0959..67cc780 100644 --- a/bp-core.c +++ b/bp-core.c @@ -119,11 +119,11 @@ int search_SB_r(bp *b, int i, int rel) while (j>0) { w = (x >> (D-ETW)) & ((1<= -ETW && rel <= ETW) { - r = fwdtbl[((rel+ETW)<= n) return NOTFOUND; - return i+r; - } + r = fwdtbl[((rel+ETW)<= n) return NOTFOUND; + return i+r; + } } r = min(j,ETW); rel -= 2*popcount(w)-r; @@ -274,55 +274,55 @@ int degree_SB(bp *b, int i, int t, int rel, int *ans, int ith) w = (x >> (D-ETW)) & ((1< 0) { + if (ith > 0) { #if 0 - for (r = 0; r < ETW; r++) { - if (w & 0x80) { - d++; - } else { - d--; - if (d < rel) break; - if (d == rel) { - ith--; - if (ith == 0) { - *ans = i + r; - return FOUND; - } - } - } - w <<= 1; - } - return NOTFOUND; + for (r = 0; r < ETW; r++) { + if (w & 0x80) { + d++; + } else { + d--; + if (d < rel) break; + if (d == rel) { + ith--; + if (ith == 0) { + *ans = i + r; + return FOUND; + } + } + } + w <<= 1; + } + return NOTFOUND; #else - r = childtbl2[rel-d+ETW][ith-1][w]; - if (r >= 0) { - *ans = i + r; - return FOUND; - } - return NOTFOUND; + r = childtbl2[rel-d+ETW][ith-1][w]; + if (r >= 0) { + *ans = i + r; + return FOUND; + } + return NOTFOUND; #endif - } - r = ETW-1-minmaxtbl_i[0][w | w2]; - w2 = (1< 0) { - if (ith <= r) { - *ans = i + childtbl[((ith-1)< 0) { + if (ith <= r) { + *ans = i + childtbl[((ith-1)< 0) { - if (r == NOTFOUND) return NOTFOUND; - *ans = degtmp; - return FOUND; + if (r == NOTFOUND) return NOTFOUND; + *ans = degtmp; + return FOUND; } else { - *ans = deg + degtmp; - return END; + *ans = deg + degtmp; + return END; } } if (m == td) { if (ith > 0) { - if (ith <= b->sd[SBid(i)]) break; - ith -= b->sd[SBid(i)]; + if (ith <= b->sd[SBid(i)]) break; + ith -= b->sd[SBid(i)]; } deg += b->sd[SBid(i)]; } @@ -386,8 +386,8 @@ int degree_MB(bp *b, int i, int t, int td, int *ans,int ith) if (ith > 0) { if (r == NOTFOUND) return NOTFOUND; if (r == FOUND) { - *ans = degtmp; - return FOUND; + *ans = degtmp; + return FOUND; } } else { deg += degtmp; @@ -407,8 +407,8 @@ static void partition_range(int s,int t) while (s <= t) { if (s & h) { if (s+h-1 <= t) { - printf("[%d,%d] ",s,s+h-1); - s += h; + printf("[%d,%d] ",s,s+h-1); + s += h; } } else { if (s+h > t) break; @@ -474,7 +474,7 @@ int bp_fast_degree(bp *b,int s, int t, int ith) } else { deg += degtmp; if (d == END) { - return deg; + return deg; } } } @@ -493,8 +493,8 @@ int bp_fast_degree(bp *b,int s, int t, int ith) } if (b->mm[i] == td) { if (ith > 0) { - if (ith <= b->md[i]) break; - ith -= b->md[i]; + if (ith <= b->md[i]) break; + ith -= b->md[i]; } deg += b->md[i]; } @@ -515,23 +515,23 @@ int bp_fast_degree(bp *b,int s, int t, int ith) while (sm <= tm) { if (sm & h) { if (sm+h-1 <= tm) { - //printf("[%d,%d] ",sm,sm+h-1); - j = sm / h; - if (b->mm[j] < td) { - h >>= 1; - break; - } - if (b->mm[j] == td) { - if (ith > 0) { - if (ith <= b->md[j]) { - h >>= 1; - break; - } - ith -= b->md[j]; - } - deg += b->md[j]; - } - sm += h; + //printf("[%d,%d] ",sm,sm+h-1); + j = sm / h; + if (b->mm[j] < td) { + h >>= 1; + break; + } + if (b->mm[j] == td) { + if (ith > 0) { + if (ith <= b->md[j]) { + h >>= 1; + break; + } + ith -= b->md[j]; + } + deg += b->md[j]; + } + sm += h; } } else { if (sm+h > tm) break; @@ -543,25 +543,25 @@ int bp_fast_degree(bp *b,int s, int t, int ith) //printf("[%d,%d] ",sm,sm+h-1); j = sm / h; if (ith > 0) { - if (b->mm[j] >= td) { - if (b->mm[j] == td) { - if (ith > b->md[j]) { - ith -= b->md[j]; - sm += h; - } else { - deg += b->md[j]; - } - } else { - sm += h; - } - } + if (b->mm[j] >= td) { + if (b->mm[j] == td) { + if (ith > b->md[j]) { + ith -= b->md[j]; + sm += h; + } else { + deg += b->md[j]; + } + } else { + sm += h; + } + } } else { - if (b->mm[j] >= td) { - if (b->mm[j] == td) { - deg += b->md[j]; - } - sm += h; - } + if (b->mm[j] >= td) { + if (b->mm[j] == td) { + deg += b->md[j]; + } + sm += h; + } } } h >>= 1; @@ -605,11 +605,11 @@ int search_SB_l(bp *b, int i, int rel) while (j>0) { w = x & ((1<= -ETW && rel <= ETW) { - r = bwdtbl[((rel+ETW)<> (D-ETW)) & ((1< ds) { - ds = d + v; - is = i + minmaxtbl_i[op][w & (~w2)]; - } + v = minmaxtbl_v[op][w & (~w2)]; + if (d + v + lr > ds) { + ds = d + v; + is = i + minmaxtbl_i[op][w & (~w2)]; + } } else { - v = minmaxtbl_v[op][w | w2]; - if (d + v < ds +lr) { - ds = d + v; - is = i + minmaxtbl_i[op][w | w2]; - } + v = minmaxtbl_v[op][w | w2]; + if (d + v < ds +lr) { + ds = d + v; + is = i + minmaxtbl_i[op][w | w2]; + } } r = min(j,ETW); @@ -772,16 +772,16 @@ int rmq_SB(bp *b, int s, int t, int opt, int *dm) if (bp_getbit(b->B,i)==OP) { d++; if (op & OPT_MAX) { - if (d + lr > ds) { - ds = d; is = i; - } + if (d + lr > ds) { + ds = d; is = i; + } } } else { d--; if (!(op & OPT_MAX)) { - if (d < ds + lr) { - ds = d; is = i; - } + if (d < ds + lr) { + ds = d; is = i; + } } } i++; @@ -809,12 +809,12 @@ int rmq_MB(bp *b, int s, int t, int opt, int *dm) if (opt & OPT_MAX) { m = d + b->sM[i] - 1; if (m + lr > md) { - md = m; mi = i; + md = m; mi = i; } } else { m = d + b->sm[i] - SB; if (m < md + lr) { - md = m; mi = i; + md = m; mi = i; } } } @@ -896,11 +896,11 @@ int bp_rmq(bp *b, int s, int t, int opt) for (i=sm; i<=tm; i++) { if (opt & OPT_MAX) { if (b->mM[i] + lr > ds) { - ds = b->mM[i]; is = i - m_ofs; ys = 2; + ds = b->mM[i]; is = i - m_ofs; ys = 2; } } else { if (b->mm[i] < ds + lr) { - ds = b->mm[i]; is = i - m_ofs; ys = 2; + ds = b->mm[i]; is = i - m_ofs; ys = 2; } } } @@ -915,63 +915,63 @@ int bp_rmq(bp *b, int s, int t, int opt) if (opt & OPT_MAX) { if (b->mM[sm] + lr > ds) { - ds = b->mM[sm]; is = sm; ys = 2; + ds = b->mM[sm]; is = sm; ys = 2; } for (i=0; i<=h-2; i++) { - j = sm>>i; - if ((j&1) == 0) { - if (b->mM[j+1] + lr > ds) { - ds = b->mM[j+1]; is = j+1; ys = 2; - } - } + j = sm>>i; + if ((j&1) == 0) { + if (b->mM[j+1] + lr > ds) { + ds = b->mM[j+1]; is = j+1; ys = 2; + } + } } for (i=h-2; i>=0; i--) { - j = tm>>i; - if ((j&1)==1) { - if (b->mM[j-1] + lr > ds) { - ds = b->mM[j-1]; is = j-1; ys = 2; - } - } + j = tm>>i; + if ((j&1)==1) { + if (b->mM[j-1] + lr > ds) { + ds = b->mM[j-1]; is = j-1; ys = 2; + } + } } if (b->mM[tm] + lr > ds) { - ds = b->mM[tm]; is = tm; ys = 2; + ds = b->mM[tm]; is = tm; ys = 2; } if (ys == 2) { - while (is < m_ofs) { - is <<= 1; - if (b->mM[is+1] + lr > b->mM[is]) is++; - } - is -= m_ofs; + while (is < m_ofs) { + is <<= 1; + if (b->mM[is+1] + lr > b->mM[is]) is++; + } + is -= m_ofs; } } else { // MIN if (b->mm[sm] < ds + lr) { - ds = b->mm[sm]; is = sm; ys = 2; + ds = b->mm[sm]; is = sm; ys = 2; } for (i=0; i<=h-2; i++) { - j = sm>>i; - if ((j&1) == 0) { - if (b->mm[j+1] < ds + lr) { - ds = b->mm[j+1]; is = j+1; ys = 2; - } - } + j = sm>>i; + if ((j&1) == 0) { + if (b->mm[j+1] < ds + lr) { + ds = b->mm[j+1]; is = j+1; ys = 2; + } + } } for (i=h-2; i>=0; i--) { - j = tm>>i; - if ((j&1)==1) { - if (b->mm[j-1] < ds + lr) { - ds = b->mm[j-1]; is = j-1; ys = 2; - } - } + j = tm>>i; + if ((j&1)==1) { + if (b->mm[j-1] < ds + lr) { + ds = b->mm[j-1]; is = j-1; ys = 2; + } + } } if (b->mm[tm] < ds + lr) { - ds = b->mm[tm]; is = tm; ys = 2; + ds = b->mm[tm]; is = tm; ys = 2; } if (ys == 2) { - while (is < m_ofs) { - is <<= 1; - if (b->mm[is+1] < b->mm[is] + lr) is++; - } - is -= m_ofs; + while (is < m_ofs) { + is <<= 1; + if (b->mm[is+1] < b->mm[is] + lr) is++; + } + is -= m_ofs; } } } diff --git a/bp-darray.c b/bp-darray.c index 800ebb1..866ce6f 100644 --- a/bp-darray.c +++ b/bp-darray.c @@ -58,11 +58,30 @@ static int getpattern(pb *B, int i, int k, pb pat) static int selecttbl[8*256]; static int selecttbl_init = 0; +static void prbin(unsigned int x) +{ + int i; + // for(i = 31; i >= 0; i--){ + for (i = 0 ; i < 32; i ++) { + fprintf(stderr,"%.1u", (x >> i)&1); + if (i % 4 == 3) + fprintf(stderr, " "); + } + +} +int clz(unsigned int x) +{ + if (x == 0) + return -1; + else + __builtin_clz(x); +} static void make_selecttbl(void) { int i,x,r; pb buf[1]; + unsigned int mask; if (selecttbl_init) return; selecttbl_init = 1; @@ -73,11 +92,21 @@ static void make_selecttbl(void) r = 0; for (i=0; i<8; i++) { if (bp_getbit(buf,i)) { + // fprintf(stderr, "Init: setting %i to %i (r= %i, x = %i)\n", (r<<8)+x, i, r, x); selecttbl[(r<<8)+x] = i; r++; } } } + /* + fprintf(stderr, "Select table:\n"); + for (i = 0; i < 8 * 256; i++){ + mask = i / 256 + 1; + x = __builtin_clz((i + (i << 8))); + prbin(i); + fprintf(stderr, " (%.4i): %08i, %08i\n", i, selecttbl[i], x); + }; + */ } diff --git a/bp-darray.h b/bp-darray.h index 4224dba..75808f1 100644 --- a/bp-darray.h +++ b/bp-darray.h @@ -37,6 +37,7 @@ darray * bp_darray_construct(int n, pb *buf,int opt); void bp_darray_free(darray *da); int bp_darray_select(darray *da, int i,int f); + static int bp_darray_rank(darray *da, int i) { int r,j,i_rr, i_rrr; diff --git a/bp-utils.h b/bp-utils.h index 21aa7d3..56f2d73 100644 --- a/bp-utils.h +++ b/bp-utils.h @@ -18,20 +18,21 @@ extern "C" { #define RRR (1< - +#ifdef __GNUC__ +#define UNUSED __attribute__((unused)) +#else +#define UNUSED +#endif #ifdef HAS_NATIVE_POPCOUNT -static inline unsigned int popcount(unsigned int n){ +static inline UNUSED unsigned int popcount(unsigned int n){ asm ("popcnt %1, %0" : "=r" (n) : "0" (n)); return n; } -static inline unsigned int popcount8(unsigned int n) { +static inline UNUSED unsigned int popcount8(unsigned int n) { return popcount(n & 0xff); } @@ -40,12 +41,12 @@ static inline unsigned int popcount8(unsigned int n) { extern unsigned char popCount[256]; -static unsigned int popcount8(unsigned int x) +static UNUSED unsigned int popcount8(unsigned int x) { return (unsigned int) popCount[x & 0xff]; } -static unsigned int popcount(unsigned int x) +static UNUSED unsigned int popcount(unsigned int x) { return popcount8(x) + popcount8((x >> 8)) + @@ -55,7 +56,7 @@ static unsigned int popcount(unsigned int x) #else -static unsigned int popcount8(unsigned int x) +static UNUSED unsigned int popcount8(unsigned int x) { unsigned int r; r = x; @@ -65,7 +66,7 @@ static unsigned int popcount8(unsigned int x) return r; } -static inline unsigned int popcount(unsigned int x) +static inline UNUSED unsigned int popcount(unsigned int x) { unsigned int m1 = 0x55555555; unsigned int m2 = 0xc30c30c3; diff --git a/bp.c b/bp.c index f1aef19..62f4613 100644 --- a/bp.c +++ b/bp.c @@ -1,4 +1,5 @@ #include "bp.h" +#include //#define CHECK #define RANDOM @@ -159,7 +160,7 @@ static void make_matchtbl(void) if (bp_getbit(buf,i)==OP) { r++; if (r > M) { - M = r; + M = r; //maxtbl_li[x] = i; maxtbl_lv[x] = r; minmaxtbl_i[OPT_MAX | OPT_LEFT][x] = i; minmaxtbl_v[OPT_MAX | OPT_LEFT][x] = r; @@ -192,7 +193,7 @@ static void make_matchtbl(void) if (bp_getbit(buf,i)==OP) { r++; if (r >= M) { - M = r; + M = r; //maxtbl_ri[x] = i; maxtbl_rv[x] = r; minmaxtbl_i[OPT_MAX | OPT_RIGHT][x] = i; minmaxtbl_v[OPT_MAX | OPT_RIGHT][x] = r; @@ -457,6 +458,63 @@ void saveTree(bp *b, FILE *fp) { } } +static ssize_t uwrite(int fd, const void* buff, size_t count) +{ + ssize_t written; + char *p = (char *) buff; + do { + written = write(fd, p, count); + p += written; + count -= written; + } while (written > 0); + + return (written == -1); +} + +static ssize_t uread(int fd, const void* buff, size_t count) +{ + ssize_t loaded; + char *p = (char *) buff; + do { + loaded = read(fd, p, count); + p += loaded; + count -= loaded; + } while (loaded > 0); + + return (loaded == -1); +} + +int bp_save(bp *b, int fd) +{ + if (uwrite(fd, &b->n, sizeof(int))) return 1; + if (uwrite(fd, b->B, sizeof(pb) * (b->n+D-1)/D)) return 1; + if (uwrite(fd, &b->opt, sizeof(int))) return 1; + return 0; +} + +bp* bp_load(int fd) +{ + pb *B; + int n, opt; + if (uread(fd, &n, sizeof(int))) return NULL; + bp_xmalloc(B, (n+D-1)/D); + + if (B == NULL) return NULL; + + if (uread(fd, B, sizeof(pb) * (n+D-1)/D)) { + free(B); + return NULL; + }; + + if (uread(fd, &opt, sizeof(int))){ + free(B); + return NULL; + }; + + return bp_construct(n, B, opt); +} + + // loadTree: load parentheses data structure from file // By Diego Arroyuelo bp * loadTree(FILE *fp) { @@ -481,7 +539,7 @@ bp * loadTree(FILE *fp) { exit(1); } - return bp_construct(n, B, opt); + return bp_construct(n, B, opt); } @@ -859,7 +917,7 @@ int bp_child(bp *b, int s, int d) } else { return bp_naive_child(b,s,d); } - + } diff --git a/bp.h b/bp.h index b982430..6177b83 100644 --- a/bp.h +++ b/bp.h @@ -114,7 +114,9 @@ static inline int bp_find_open(bp *b,int s) /////////////////////////////////////////// static inline int bp_parent(bp *b, int s) { - int r = bp_bwd_excess(b,s,-2); + int r; + if (bp_getbit(b->B, s - 1) == OP) return s - 1; + r = bp_bwd_excess(b,s,-2); return (r >= -1) ? r+1 : -1; } @@ -228,7 +230,7 @@ static inline int bp_first_child(bp *b, int s) static inline int bp_next_sibling(bp *b, int s) { int t; - t = bp_find_close(b,s) + 1; + t = bp_find_close(b, s) + 1; return (bp_inspect(b, t) == CP) ? -1 : t; } @@ -288,6 +290,13 @@ int bp_child(bp *b, int s, int d); // new functions for persistence purposes, added by Diego Arroyuelo void saveTree(bp *b, FILE *fp); bp * loadTree(FILE *fp); + +//0: success 1: failure (errno) +int bp_save(bp *b, int fd); + +//non-null: sucess, null: failure (errno) + +bp * bp_load(int fd); void bp_delete(bp *b); -- 2.17.1