| 1 |
#include <stdlib.h> |
| 2 |
#include <string.h> |
| 3 |
#include <stdio.h> |
| 4 |
#include "bwt_lite.h" |
| 5 |
|
| 6 |
#ifdef USE_MALLOC_WRAPPERS |
| 7 |
# include "malloc_wrap.h" |
| 8 |
#endif |
| 9 |
|
| 10 |
int is_sa(const uint8_t *T, int *SA, int n); |
| 11 |
int is_bwt(uint8_t *T, int n); |
| 12 |
|
| 13 |
bwtl_t *bwtl_seq2bwtl(int len, const uint8_t *seq) |
| 14 |
{ |
| 15 |
bwtl_t *b; |
| 16 |
int i; |
| 17 |
b = (bwtl_t*)calloc(1, sizeof(bwtl_t)); |
| 18 |
b->seq_len = len; |
| 19 |
|
| 20 |
{ // calculate b->bwt |
| 21 |
uint8_t *s; |
| 22 |
b->sa = (uint32_t*)calloc(len + 1, 4); |
| 23 |
is_sa(seq, (int*)b->sa, len); |
| 24 |
s = (uint8_t*)calloc(len + 1, 1); |
| 25 |
for (i = 0; i <= len; ++i) { |
| 26 |
if (b->sa[i] == 0) b->primary = i; |
| 27 |
else s[i] = seq[b->sa[i] - 1]; |
| 28 |
} |
| 29 |
for (i = b->primary; i < len; ++i) s[i] = s[i + 1]; |
| 30 |
b->bwt_size = (len + 15) / 16; |
| 31 |
b->bwt = (uint32_t*)calloc(b->bwt_size, 4); |
| 32 |
for (i = 0; i < len; ++i) |
| 33 |
b->bwt[i>>4] |= s[i] << ((15 - (i&15)) << 1); |
| 34 |
free(s); |
| 35 |
} |
| 36 |
{ // calculate b->occ |
| 37 |
uint32_t c[4]; |
| 38 |
b->n_occ = (len + 15) / 16 * 4; |
| 39 |
b->occ = (uint32_t*)calloc(b->n_occ, 4); |
| 40 |
memset(c, 0, 16); |
| 41 |
for (i = 0; i < len; ++i) { |
| 42 |
if (i % 16 == 0) |
| 43 |
memcpy(b->occ + (i/16) * 4, c, 16); |
| 44 |
++c[bwtl_B0(b, i)]; |
| 45 |
} |
| 46 |
memcpy(b->L2+1, c, 16); |
| 47 |
for (i = 2; i < 5; ++i) b->L2[i] += b->L2[i-1]; |
| 48 |
} |
| 49 |
{ // generate cnt_table |
| 50 |
for (i = 0; i != 256; ++i) { |
| 51 |
uint32_t j, x = 0; |
| 52 |
for (j = 0; j != 4; ++j) |
| 53 |
x |= (((i&3) == j) + ((i>>2&3) == j) + ((i>>4&3) == j) + (i>>6 == j)) << (j<<3); |
| 54 |
b->cnt_table[i] = x; |
| 55 |
} |
| 56 |
} |
| 57 |
return b; |
| 58 |
} |
| 59 |
uint32_t bwtl_occ(const bwtl_t *bwt, uint32_t k, uint8_t c) |
| 60 |
{ |
| 61 |
uint32_t n, b; |
| 62 |
if (k == bwt->seq_len) return bwt->L2[c+1] - bwt->L2[c]; |
| 63 |
if (k == (uint32_t)(-1)) return 0; |
| 64 |
if (k >= bwt->primary) --k; // because $ is not in bwt |
| 65 |
n = bwt->occ[k/16<<2|c]; |
| 66 |
b = bwt->bwt[k/16] & ~((1U<<((15-(k&15))<<1)) - 1); |
| 67 |
n += (bwt->cnt_table[b&0xff] + bwt->cnt_table[b>>8&0xff] |
| 68 |
+ bwt->cnt_table[b>>16&0xff] + bwt->cnt_table[b>>24]) >> (c<<3) & 0xff; |
| 69 |
if (c == 0) n -= 15 - (k&15); // corrected for the masked bits |
| 70 |
return n; |
| 71 |
} |
| 72 |
void bwtl_occ4(const bwtl_t *bwt, uint32_t k, uint32_t cnt[4]) |
| 73 |
{ |
| 74 |
uint32_t x, b; |
| 75 |
if (k == (uint32_t)(-1)) { |
| 76 |
memset(cnt, 0, 16); |
| 77 |
return; |
| 78 |
} |
| 79 |
if (k >= bwt->primary) --k; // because $ is not in bwt |
| 80 |
memcpy(cnt, bwt->occ + (k>>4<<2), 16); |
| 81 |
b = bwt->bwt[k>>4] & ~((1U<<((~k&15)<<1)) - 1); |
| 82 |
x = bwt->cnt_table[b&0xff] + bwt->cnt_table[b>>8&0xff] |
| 83 |
+ bwt->cnt_table[b>>16&0xff] + bwt->cnt_table[b>>24]; |
| 84 |
x -= 15 - (k&15); |
| 85 |
cnt[0] += x&0xff; cnt[1] += x>>8&0xff; cnt[2] += x>>16&0xff; cnt[3] += x>>24; |
| 86 |
} |
| 87 |
void bwtl_2occ4(const bwtl_t *bwt, uint32_t k, uint32_t l, uint32_t cntk[4], uint32_t cntl[4]) |
| 88 |
{ |
| 89 |
bwtl_occ4(bwt, k, cntk); |
| 90 |
bwtl_occ4(bwt, l, cntl); |
| 91 |
} |
| 92 |
void bwtl_destroy(bwtl_t *bwt) |
| 93 |
{ |
| 94 |
if (bwt) { |
| 95 |
free(bwt->occ); free(bwt->bwt); free(bwt->sa); |
| 96 |
free(bwt); |
| 97 |
} |
| 98 |
} |