Debian Codegraph @

bwa-apache2/bwt_lite.c

raw
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 }