Debian Codegraph @

bwa-apache2/bwt.h

raw
1 /* The MIT License
2
3 Copyright (c) 2018- Dana-Farber Cancer Institute
4 2009-2018 Broad Institute, Inc.
5 2008-2009 Genome Research Ltd. (GRL)
6
7 Permission is hereby granted, free of charge, to any person obtaining
8 a copy of this software and associated documentation files (the
9 "Software"), to deal in the Software without restriction, including
10 without limitation the rights to use, copy, modify, merge, publish,
11 distribute, sublicense, and/or sell copies of the Software, and to
12 permit persons to whom the Software is furnished to do so, subject to
13 the following conditions:
14
15 The above copyright notice and this permission notice shall be
16 included in all copies or substantial portions of the Software.
17
18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
22 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
23 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
24 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
25 SOFTWARE.
26 */
27
28 /* Contact: Heng Li <[email protected]> */
29
30 #ifndef BWA_BWT_H
31 #define BWA_BWT_H
32
33 #include <stdint.h>
34 #include <stddef.h>
35
36 // requirement: (OCC_INTERVAL%16 == 0); please DO NOT change this line because some part of the code assume OCC_INTERVAL=0x80
37 #define OCC_INTV_SHIFT 7
38 #define OCC_INTERVAL (1LL<<OCC_INTV_SHIFT)
39 #define OCC_INTV_MASK (OCC_INTERVAL - 1)
40
41 #ifndef BWA_UBYTE
42 #define BWA_UBYTE
43 typedef unsigned char ubyte_t;
44 #endif
45
46 typedef uint64_t bwtint_t;
47
48 typedef struct {
49 bwtint_t primary; // S^{-1}(0), or the primary index of BWT
50 bwtint_t L2[5]; // C(), cumulative count
51 bwtint_t seq_len; // sequence length
52 bwtint_t bwt_size; // size of bwt, about seq_len/4
53 uint32_t *bwt; // BWT
54 // occurance array, separated to two parts
55 uint32_t cnt_table[256];
56 // suffix array
57 int sa_intv;
58 bwtint_t n_sa;
59 bwtint_t *sa;
60 } bwt_t;
61
62 typedef struct {
63 bwtint_t x[3], info;
64 } bwtintv_t;
65
66 typedef struct { size_t n, m; bwtintv_t *a; } bwtintv_v;
67
68 /* For general OCC_INTERVAL, the following is correct:
69 #define bwt_bwt(b, k) ((b)->bwt[(k)/OCC_INTERVAL * (OCC_INTERVAL/(sizeof(uint32_t)*8/2) + sizeof(bwtint_t)/4*4) + sizeof(bwtint_t)/4*4 + (k)%OCC_INTERVAL/16])
70 #define bwt_occ_intv(b, k) ((b)->bwt + (k)/OCC_INTERVAL * (OCC_INTERVAL/(sizeof(uint32_t)*8/2) + sizeof(bwtint_t)/4*4)
71 */
72
73 // The following two lines are ONLY correct when OCC_INTERVAL==0x80
74 #define bwt_bwt(b, k) ((b)->bwt[((k)>>7<<4) + sizeof(bwtint_t) + (((k)&0x7f)>>4)])
75 #define bwt_occ_intv(b, k) ((b)->bwt + ((k)>>7<<4))
76
77 /* retrieve a character from the $-removed BWT string. Note that
78 * bwt_t::bwt is not exactly the BWT string and therefore this macro is
79 * called bwt_B0 instead of bwt_B */
80 #define bwt_B0(b, k) (bwt_bwt(b, k)>>((~(k)&0xf)<<1)&3)
81
82 #define bwt_set_intv(bwt, c, ik) ((ik).x[0] = (bwt)->L2[(int)(c)]+1, (ik).x[2] = (bwt)->L2[(int)(c)+1]-(bwt)->L2[(int)(c)], (ik).x[1] = (bwt)->L2[3-(c)]+1, (ik).info = 0)
83
84 #ifdef __cplusplus
85 extern "C" {
86 #endif
87
88 void bwt_dump_bwt(const char *fn, const bwt_t *bwt);
89 void bwt_dump_sa(const char *fn, const bwt_t *bwt);
90
91 bwt_t *bwt_restore_bwt(const char *fn);
92 void bwt_restore_sa(const char *fn, bwt_t *bwt);
93
94 void bwt_destroy(bwt_t *bwt);
95
96 void bwt_bwtgen(const char *fn_pac, const char *fn_bwt); // from BWT-SW
97 void bwt_bwtgen2(const char *fn_pac, const char *fn_bwt, int block_size); // from BWT-SW
98 void bwt_cal_sa(bwt_t *bwt, int intv);
99
100 void bwt_bwtupdate_core(bwt_t *bwt);
101
102 bwtint_t bwt_occ(const bwt_t *bwt, bwtint_t k, ubyte_t c);
103 void bwt_occ4(const bwt_t *bwt, bwtint_t k, bwtint_t cnt[4]);
104 bwtint_t bwt_sa(const bwt_t *bwt, bwtint_t k);
105
106 // more efficient version of bwt_occ/bwt_occ4 for retrieving two close Occ values
107 void bwt_gen_cnt_table(bwt_t *bwt);
108 void bwt_2occ(const bwt_t *bwt, bwtint_t k, bwtint_t l, ubyte_t c, bwtint_t *ok, bwtint_t *ol);
109 void bwt_2occ4(const bwt_t *bwt, bwtint_t k, bwtint_t l, bwtint_t cntk[4], bwtint_t cntl[4]);
110
111 int bwt_match_exact(const bwt_t *bwt, int len, const ubyte_t *str, bwtint_t *sa_begin, bwtint_t *sa_end);
112 int bwt_match_exact_alt(const bwt_t *bwt, int len, const ubyte_t *str, bwtint_t *k0, bwtint_t *l0);
113
114 /**
115 * Extend bi-SA-interval _ik_
116 */
117 void bwt_extend(const bwt_t *bwt, const bwtintv_t *ik, bwtintv_t ok[4], int is_back);
118
119 /**
120 * Given a query _q_, collect potential SMEMs covering position _x_ and store them in _mem_.
121 * Return the end of the longest exact match starting from _x_.
122 */
123 int bwt_smem1(const bwt_t *bwt, int len, const uint8_t *q, int x, int min_intv, bwtintv_v *mem, bwtintv_v *tmpvec[2]);
124 int bwt_smem1a(const bwt_t *bwt, int len, const uint8_t *q, int x, int min_intv, uint64_t max_intv, bwtintv_v *mem, bwtintv_v *tmpvec[2]);
125
126 int bwt_seed_strategy1(const bwt_t *bwt, int len, const uint8_t *q, int x, int min_len, int max_intv, bwtintv_t *mem);
127
128 #ifdef __cplusplus
129 }
130 #endif
131
132 #endif