Debian Codegraph @

bwa-apache2/is.c

raw
1 /*
2 * sais.c for sais-lite
3 * Copyright (c) 2008 Yuta Mori All Rights Reserved.
4 *
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
12 * conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 */
26
27 #include <stdlib.h>
28
29 #ifdef USE_MALLOC_WRAPPERS
30 # include "malloc_wrap.h"
31 #endif
32
33 typedef unsigned char ubyte_t;
34 #define chr(i) (cs == sizeof(int) ? ((const int *)T)[i]:((const unsigned char *)T)[i])
35
36 /* find the start or end of each bucket */
37 static void getCounts(const unsigned char *T, int *C, int n, int k, int cs)
38 {
39 int i;
40 for (i = 0; i < k; ++i) C[i] = 0;
41 for (i = 0; i < n; ++i) ++C[chr(i)];
42 }
43 static void getBuckets(const int *C, int *B, int k, int end)
44 {
45 int i, sum = 0;
46 if (end) {
47 for (i = 0; i < k; ++i) {
48 sum += C[i];
49 B[i] = sum;
50 }
51 } else {
52 for (i = 0; i < k; ++i) {
53 sum += C[i];
54 B[i] = sum - C[i];
55 }
56 }
57 }
58
59 /* compute SA */
60 static void induceSA(const unsigned char *T, int *SA, int *C, int *B, int n, int k, int cs)
61 {
62 int *b, i, j;
63 int c0, c1;
64 /* compute SAl */
65 if (C == B) getCounts(T, C, n, k, cs);
66 getBuckets(C, B, k, 0); /* find starts of buckets */
67 j = n - 1;
68 b = SA + B[c1 = chr(j)];
69 *b++ = ((0 < j) && (chr(j - 1) < c1)) ? ~j : j;
70 for (i = 0; i < n; ++i) {
71 j = SA[i], SA[i] = ~j;
72 if (0 < j) {
73 --j;
74 if ((c0 = chr(j)) != c1) {
75 B[c1] = b - SA;
76 b = SA + B[c1 = c0];
77 }
78 *b++ = ((0 < j) && (chr(j - 1) < c1)) ? ~j : j;
79 }
80 }
81 /* compute SAs */
82 if (C == B) getCounts(T, C, n, k, cs);
83 getBuckets(C, B, k, 1); /* find ends of buckets */
84 for (i = n - 1, b = SA + B[c1 = 0]; 0 <= i; --i) {
85 if (0 < (j = SA[i])) {
86 --j;
87 if ((c0 = chr(j)) != c1) {
88 B[c1] = b - SA;
89 b = SA + B[c1 = c0];
90 }
91 *--b = ((j == 0) || (chr(j - 1) > c1)) ? ~j : j;
92 } else SA[i] = ~j;
93 }
94 }
95
96 /*
97 * find the suffix array SA of T[0..n-1] in {0..k-1}^n use a working
98 * space (excluding T and SA) of at most 2n+O(1) for a constant alphabet
99 */
100 static int sais_main(const unsigned char *T, int *SA, int fs, int n, int k, int cs)
101 {
102 int *C, *B, *RA;
103 int i, j, c, m, p, q, plen, qlen, name;
104 int c0, c1;
105 int diff;
106
107 /* stage 1: reduce the problem by at least 1/2 sort all the
108 * S-substrings */
109 if (k <= fs) {
110 C = SA + n;
111 B = (k <= (fs - k)) ? C + k : C;
112 } else if ((C = B = (int *) malloc(k * sizeof(int))) == NULL) return -2;
113 getCounts(T, C, n, k, cs);
114 getBuckets(C, B, k, 1); /* find ends of buckets */
115 for (i = 0; i < n; ++i) SA[i] = 0;
116 for (i = n - 2, c = 0, c1 = chr(n - 1); 0 <= i; --i, c1 = c0) {
117 if ((c0 = chr(i)) < (c1 + c)) c = 1;
118 else if (c != 0) SA[--B[c1]] = i + 1, c = 0;
119 }
120 induceSA(T, SA, C, B, n, k, cs);
121 if (fs < k) free(C);
122 /* compact all the sorted substrings into the first m items of SA
123 * 2*m must be not larger than n (proveable) */
124 for (i = 0, m = 0; i < n; ++i) {
125 p = SA[i];
126 if ((0 < p) && (chr(p - 1) > (c0 = chr(p)))) {
127 for (j = p + 1; (j < n) && (c0 == (c1 = chr(j))); ++j);
128 if ((j < n) && (c0 < c1)) SA[m++] = p;
129 }
130 }
131 for (i = m; i < n; ++i) SA[i] = 0; /* init the name array buffer */
132 /* store the length of all substrings */
133 for (i = n - 2, j = n, c = 0, c1 = chr(n - 1); 0 <= i; --i, c1 = c0) {
134 if ((c0 = chr(i)) < (c1 + c)) c = 1;
135 else if (c != 0) {
136 SA[m + ((i + 1) >> 1)] = j - i - 1;
137 j = i + 1;
138 c = 0;
139 }
140 }
141 /* find the lexicographic names of all substrings */
142 for (i = 0, name = 0, q = n, qlen = 0; i < m; ++i) {
143 p = SA[i], plen = SA[m + (p >> 1)], diff = 1;
144 if (plen == qlen) {
145 for (j = 0; (j < plen) && (chr(p + j) == chr(q + j)); j++);
146 if (j == plen) diff = 0;
147 }
148 if (diff != 0) ++name, q = p, qlen = plen;
149 SA[m + (p >> 1)] = name;
150 }
151
152 /* stage 2: solve the reduced problem recurse if names are not yet
153 * unique */
154 if (name < m) {
155 RA = SA + n + fs - m;
156 for (i = n - 1, j = m - 1; m <= i; --i) {
157 if (SA[i] != 0) RA[j--] = SA[i] - 1;
158 }
159 if (sais_main((unsigned char *) RA, SA, fs + n - m * 2, m, name, sizeof(int)) != 0) return -2;
160 for (i = n - 2, j = m - 1, c = 0, c1 = chr(n - 1); 0 <= i; --i, c1 = c0) {
161 if ((c0 = chr(i)) < (c1 + c)) c = 1;
162 else if (c != 0) RA[j--] = i + 1, c = 0; /* get p1 */
163 }
164 for (i = 0; i < m; ++i) SA[i] = RA[SA[i]]; /* get index */
165 }
166 /* stage 3: induce the result for the original problem */
167 if (k <= fs) {
168 C = SA + n;
169 B = (k <= (fs - k)) ? C + k : C;
170 } else if ((C = B = (int *) malloc(k * sizeof(int))) == NULL) return -2;
171 /* put all left-most S characters into their buckets */
172 getCounts(T, C, n, k, cs);
173 getBuckets(C, B, k, 1); /* find ends of buckets */
174 for (i = m; i < n; ++i) SA[i] = 0; /* init SA[m..n-1] */
175 for (i = m - 1; 0 <= i; --i) {
176 j = SA[i], SA[i] = 0;
177 SA[--B[chr(j)]] = j;
178 }
179 induceSA(T, SA, C, B, n, k, cs);
180 if (fs < k) free(C);
181 return 0;
182 }
183
184 /**
185 * Constructs the suffix array of a given string.
186 * @param T[0..n-1] The input string.
187 * @param SA[0..n] The output array of suffixes.
188 * @param n The length of the given string.
189 * @return 0 if no error occurred
190 */
191 int is_sa(const ubyte_t *T, int *SA, int n)
192 {
193 if ((T == NULL) || (SA == NULL) || (n < 0)) return -1;
194 SA[0] = n;
195 if (n <= 1) {
196 if (n == 1) SA[1] = 0;
197 return 0;
198 }
199 return sais_main(T, SA+1, 0, n, 256, 1);
200 }
201
202 /**
203 * Constructs the burrows-wheeler transformed string of a given string.
204 * @param T[0..n-1] The input string.
205 * @param n The length of the given string.
206 * @return The primary index if no error occurred, -1 or -2 otherwise.
207 */
208 int is_bwt(ubyte_t *T, int n)
209 {
210 int *SA, i, primary = 0;
211 SA = (int*)calloc(n+1, sizeof(int));
212
213 if (is_sa(T, SA, n)) return -1;
214
215 for (i = 0; i <= n; ++i) {
216 if (SA[i] == 0) primary = i;
217 else SA[i] = T[SA[i] - 1];
218 }
219 for (i = 0; i < primary; ++i) T[i] = SA[i];
220 for (; i < n; ++i) T[i] = SA[i + 1];
221 free(SA);
222 return primary;
223 }