| 1 |
/* The MIT License |
| 2 |
|
| 3 |
Copyright (c) 2011 by Attractive Chaos <[email protected]> |
| 4 |
|
| 5 |
Permission is hereby granted, free of charge, to any person obtaining |
| 6 |
a copy of this software and associated documentation files (the |
| 7 |
"Software"), to deal in the Software without restriction, including |
| 8 |
without limitation the rights to use, copy, modify, merge, publish, |
| 9 |
distribute, sublicense, and/or sell copies of the Software, and to |
| 10 |
permit persons to whom the Software is furnished to do so, subject to |
| 11 |
the following conditions: |
| 12 |
|
| 13 |
The above copyright notice and this permission notice shall be |
| 14 |
included in all copies or substantial portions of the Software. |
| 15 |
|
| 16 |
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
| 17 |
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
| 18 |
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
| 19 |
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS |
| 20 |
BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN |
| 21 |
ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 22 |
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
| 23 |
SOFTWARE. |
| 24 |
*/ |
| 25 |
|
| 26 |
#include <stdlib.h> |
| 27 |
#include <stdint.h> |
| 28 |
#include <assert.h> |
| 29 |
#if defined __SSE2__ |
| 30 |
#include <emmintrin.h> |
| 31 |
#elif defined __ARM_NEON |
| 32 |
#include "neon_sse.h" |
| 33 |
#else |
| 34 |
#include "scalar_sse.h" |
| 35 |
#endif |
| 36 |
#include "ksw.h" |
| 37 |
|
| 38 |
#ifdef USE_MALLOC_WRAPPERS |
| 39 |
# include "malloc_wrap.h" |
| 40 |
#endif |
| 41 |
|
| 42 |
#ifdef __GNUC__ |
| 43 |
#define LIKELY(x) __builtin_expect((x),1) |
| 44 |
#define UNLIKELY(x) __builtin_expect((x),0) |
| 45 |
#else |
| 46 |
#define LIKELY(x) (x) |
| 47 |
#define UNLIKELY(x) (x) |
| 48 |
#endif |
| 49 |
|
| 50 |
const kswr_t g_defr = { 0, -1, -1, -1, -1, -1, -1 }; |
| 51 |
|
| 52 |
struct _kswq_t { |
| 53 |
int qlen, slen; |
| 54 |
uint8_t shift, mdiff, max, size; |
| 55 |
__m128i *qp, *H0, *H1, *E, *Hmax; |
| 56 |
}; |
| 57 |
|
| 58 |
/** |
| 59 |
* Initialize the query data structure |
| 60 |
* |
| 61 |
* @param size Number of bytes used to store a score; valid valures are 1 or 2 |
| 62 |
* @param qlen Length of the query sequence |
| 63 |
* @param query Query sequence |
| 64 |
* @param m Size of the alphabet |
| 65 |
* @param mat Scoring matrix in a one-dimension array |
| 66 |
* |
| 67 |
* @return Query data structure |
| 68 |
*/ |
| 69 |
kswq_t *ksw_qinit(int size, int qlen, const uint8_t *query, int m, const int8_t *mat) |
| 70 |
{ |
| 71 |
kswq_t *q; |
| 72 |
int slen, a, tmp, p; |
| 73 |
|
| 74 |
size = size > 1? 2 : 1; |
| 75 |
p = 8 * (3 - size); // # values per __m128i |
| 76 |
slen = (qlen + p - 1) / p; // segmented length |
| 77 |
q = (kswq_t*)malloc(sizeof(kswq_t) + 256 + 16 * slen * (m + 4)); // a single block of memory |
| 78 |
q->qp = (__m128i*)(((size_t)q + sizeof(kswq_t) + 15) >> 4 << 4); // align memory |
| 79 |
q->H0 = q->qp + slen * m; |
| 80 |
q->H1 = q->H0 + slen; |
| 81 |
q->E = q->H1 + slen; |
| 82 |
q->Hmax = q->E + slen; |
| 83 |
q->slen = slen; q->qlen = qlen; q->size = size; |
| 84 |
// compute shift |
| 85 |
tmp = m * m; |
| 86 |
for (a = 0, q->shift = 127, q->mdiff = 0; a < tmp; ++a) { // find the minimum and maximum score |
| 87 |
if (mat[a] < (int8_t)q->shift) q->shift = mat[a]; |
| 88 |
if (mat[a] > (int8_t)q->mdiff) q->mdiff = mat[a]; |
| 89 |
} |
| 90 |
q->max = q->mdiff; |
| 91 |
q->shift = 256 - q->shift; // NB: q->shift is uint8_t |
| 92 |
q->mdiff += q->shift; // this is the difference between the min and max scores |
| 93 |
// An example: p=8, qlen=19, slen=3 and segmentation: |
| 94 |
// {{0,3,6,9,12,15,18,-1},{1,4,7,10,13,16,-1,-1},{2,5,8,11,14,17,-1,-1}} |
| 95 |
if (size == 1) { |
| 96 |
int8_t *t = (int8_t*)q->qp; |
| 97 |
for (a = 0; a < m; ++a) { |
| 98 |
int i, k, nlen = slen * p; |
| 99 |
const int8_t *ma = mat + a * m; |
| 100 |
for (i = 0; i < slen; ++i) |
| 101 |
for (k = i; k < nlen; k += slen) // p iterations |
| 102 |
*t++ = (k >= qlen? 0 : ma[query[k]]) + q->shift; |
| 103 |
} |
| 104 |
} else { |
| 105 |
int16_t *t = (int16_t*)q->qp; |
| 106 |
for (a = 0; a < m; ++a) { |
| 107 |
int i, k, nlen = slen * p; |
| 108 |
const int8_t *ma = mat + a * m; |
| 109 |
for (i = 0; i < slen; ++i) |
| 110 |
for (k = i; k < nlen; k += slen) // p iterations |
| 111 |
*t++ = (k >= qlen? 0 : ma[query[k]]); |
| 112 |
} |
| 113 |
} |
| 114 |
return q; |
| 115 |
} |
| 116 |
|
| 117 |
#if defined __ARM_NEON |
| 118 |
// This macro implicitly uses each function's `zero` local variable |
| 119 |
#define _mm_slli_si128(a, n) (vextq_u8(zero, (a), 16 - (n))) |
| 120 |
#endif |
| 121 |
|
| 122 |
kswr_t ksw_u8(kswq_t *q, int tlen, const uint8_t *target, int _o_del, int _e_del, int _o_ins, int _e_ins, int xtra) // the first gap costs -(_o+_e) |
| 123 |
{ |
| 124 |
int slen, i, m_b, n_b, te = -1, gmax = 0, minsc, endsc; |
| 125 |
uint64_t *b; |
| 126 |
__m128i zero, oe_del, e_del, oe_ins, e_ins, shift, *H0, *H1, *E, *Hmax; |
| 127 |
kswr_t r; |
| 128 |
|
| 129 |
#if defined __SSE2__ |
| 130 |
#define __max_16(ret, xx) do { \ |
| 131 |
(xx) = _mm_max_epu8((xx), _mm_srli_si128((xx), 8)); \ |
| 132 |
(xx) = _mm_max_epu8((xx), _mm_srli_si128((xx), 4)); \ |
| 133 |
(xx) = _mm_max_epu8((xx), _mm_srli_si128((xx), 2)); \ |
| 134 |
(xx) = _mm_max_epu8((xx), _mm_srli_si128((xx), 1)); \ |
| 135 |
(ret) = _mm_extract_epi16((xx), 0) & 0x00ff; \ |
| 136 |
} while (0) |
| 137 |
|
| 138 |
// Given entries with arbitrary values, return whether they are all 0x00 |
| 139 |
#define allzero_16(xx) (_mm_movemask_epi8(_mm_cmpeq_epi8((xx), zero)) == 0xffff) |
| 140 |
|
| 141 |
#elif defined __ARM_NEON |
| 142 |
#define __max_16(ret, xx) (ret) = vmaxvq_u8((xx)) |
| 143 |
#define allzero_16(xx) (vmaxvq_u8((xx)) == 0) |
| 144 |
|
| 145 |
#else |
| 146 |
#define __max_16(ret, xx) (ret) = m128i_max_u8((xx)) |
| 147 |
#define allzero_16(xx) (m128i_allzero((xx))) |
| 148 |
#endif |
| 149 |
|
| 150 |
// initialization |
| 151 |
r = g_defr; |
| 152 |
minsc = (xtra&KSW_XSUBO)? xtra&0xffff : 0x10000; |
| 153 |
endsc = (xtra&KSW_XSTOP)? xtra&0xffff : 0x10000; |
| 154 |
m_b = n_b = 0; b = 0; |
| 155 |
zero = _mm_set1_epi32(0); |
| 156 |
oe_del = _mm_set1_epi8(_o_del + _e_del); |
| 157 |
e_del = _mm_set1_epi8(_e_del); |
| 158 |
oe_ins = _mm_set1_epi8(_o_ins + _e_ins); |
| 159 |
e_ins = _mm_set1_epi8(_e_ins); |
| 160 |
shift = _mm_set1_epi8(q->shift); |
| 161 |
H0 = q->H0; H1 = q->H1; E = q->E; Hmax = q->Hmax; |
| 162 |
slen = q->slen; |
| 163 |
for (i = 0; i < slen; ++i) { |
| 164 |
_mm_store_si128(E + i, zero); |
| 165 |
_mm_store_si128(H0 + i, zero); |
| 166 |
_mm_store_si128(Hmax + i, zero); |
| 167 |
} |
| 168 |
// the core loop |
| 169 |
for (i = 0; i < tlen; ++i) { |
| 170 |
int j, k, imax; |
| 171 |
__m128i e, h, t, f = zero, max = zero, *S = q->qp + target[i] * slen; // s is the 1st score vector |
| 172 |
h = _mm_load_si128(H0 + slen - 1); // h={2,5,8,11,14,17,-1,-1} in the above example |
| 173 |
h = _mm_slli_si128(h, 1); // h=H(i-1,-1); << instead of >> because x64 is little-endian |
| 174 |
for (j = 0; LIKELY(j < slen); ++j) { |
| 175 |
/* SW cells are computed in the following order: |
| 176 |
* H(i,j) = max{H(i-1,j-1)+S(i,j), E(i,j), F(i,j)} |
| 177 |
* E(i+1,j) = max{H(i,j)-q, E(i,j)-r} |
| 178 |
* F(i,j+1) = max{H(i,j)-q, F(i,j)-r} |
| 179 |
*/ |
| 180 |
// compute H'(i,j); note that at the beginning, h=H'(i-1,j-1) |
| 181 |
h = _mm_adds_epu8(h, _mm_load_si128(S + j)); |
| 182 |
h = _mm_subs_epu8(h, shift); // h=H'(i-1,j-1)+S(i,j) |
| 183 |
e = _mm_load_si128(E + j); // e=E'(i,j) |
| 184 |
h = _mm_max_epu8(h, e); |
| 185 |
h = _mm_max_epu8(h, f); // h=H'(i,j) |
| 186 |
max = _mm_max_epu8(max, h); // set max |
| 187 |
_mm_store_si128(H1 + j, h); // save to H'(i,j) |
| 188 |
// now compute E'(i+1,j) |
| 189 |
e = _mm_subs_epu8(e, e_del); // e=E'(i,j) - e_del |
| 190 |
t = _mm_subs_epu8(h, oe_del); // h=H'(i,j) - o_del - e_del |
| 191 |
e = _mm_max_epu8(e, t); // e=E'(i+1,j) |
| 192 |
_mm_store_si128(E + j, e); // save to E'(i+1,j) |
| 193 |
// now compute F'(i,j+1) |
| 194 |
f = _mm_subs_epu8(f, e_ins); |
| 195 |
t = _mm_subs_epu8(h, oe_ins); // h=H'(i,j) - o_ins - e_ins |
| 196 |
f = _mm_max_epu8(f, t); |
| 197 |
// get H'(i-1,j) and prepare for the next j |
| 198 |
h = _mm_load_si128(H0 + j); // h=H'(i-1,j) |
| 199 |
} |
| 200 |
// NB: we do not need to set E(i,j) as we disallow adjecent insertion and then deletion |
| 201 |
for (k = 0; LIKELY(k < 16); ++k) { // this block mimics SWPS3; NB: H(i,j) updated in the lazy-F loop cannot exceed max |
| 202 |
f = _mm_slli_si128(f, 1); |
| 203 |
for (j = 0; LIKELY(j < slen); ++j) { |
| 204 |
h = _mm_load_si128(H1 + j); |
| 205 |
h = _mm_max_epu8(h, f); // h=H'(i,j) |
| 206 |
_mm_store_si128(H1 + j, h); |
| 207 |
h = _mm_subs_epu8(h, oe_ins); |
| 208 |
f = _mm_subs_epu8(f, e_ins); |
| 209 |
if (UNLIKELY(allzero_16(_mm_subs_epu8(f, h)))) goto end_loop16; |
| 210 |
} |
| 211 |
} |
| 212 |
end_loop16: |
| 213 |
//int k;for (k=0;k<16;++k)printf("%d ", ((uint8_t*)&max)[k]);printf("\n"); |
| 214 |
__max_16(imax, max); // imax is the maximum number in max |
| 215 |
if (imax >= minsc) { // write the b array; this condition adds branching unfornately |
| 216 |
if (n_b == 0 || (int32_t)b[n_b-1] + 1 != i) { // then append |
| 217 |
if (n_b == m_b) { |
| 218 |
m_b = m_b? m_b<<1 : 8; |
| 219 |
b = (uint64_t*)realloc(b, 8 * m_b); |
| 220 |
} |
| 221 |
b[n_b++] = (uint64_t)imax<<32 | i; |
| 222 |
} else if ((int)(b[n_b-1]>>32) < imax) b[n_b-1] = (uint64_t)imax<<32 | i; // modify the last |
| 223 |
} |
| 224 |
if (imax > gmax) { |
| 225 |
gmax = imax; te = i; // te is the end position on the target |
| 226 |
for (j = 0; LIKELY(j < slen); ++j) // keep the H1 vector |
| 227 |
_mm_store_si128(Hmax + j, _mm_load_si128(H1 + j)); |
| 228 |
if (gmax + q->shift >= 255 || gmax >= endsc) break; |
| 229 |
} |
| 230 |
S = H1; H1 = H0; H0 = S; // swap H0 and H1 |
| 231 |
} |
| 232 |
r.score = gmax + q->shift < 255? gmax : 255; |
| 233 |
r.te = te; |
| 234 |
if (r.score != 255) { // get a->qe, the end of query match; find the 2nd best score |
| 235 |
int max = -1, tmp, low, high, qlen = slen * 16; |
| 236 |
uint8_t *t = (uint8_t*)Hmax; |
| 237 |
for (i = 0; i < qlen; ++i, ++t) |
| 238 |
if ((int)*t > max) max = *t, r.qe = i / 16 + i % 16 * slen; |
| 239 |
else if ((int)*t == max && (tmp = i / 16 + i % 16 * slen) < r.qe) r.qe = tmp; |
| 240 |
//printf("%d,%d\n", max, gmax); |
| 241 |
if (b) { |
| 242 |
i = (r.score + q->max - 1) / q->max; |
| 243 |
low = te - i; high = te + i; |
| 244 |
for (i = 0; i < n_b; ++i) { |
| 245 |
int e = (int32_t)b[i]; |
| 246 |
if ((e < low || e > high) && (int)(b[i]>>32) > r.score2) |
| 247 |
r.score2 = b[i]>>32, r.te2 = e; |
| 248 |
} |
| 249 |
} |
| 250 |
} |
| 251 |
free(b); |
| 252 |
return r; |
| 253 |
} |
| 254 |
|
| 255 |
kswr_t ksw_i16(kswq_t *q, int tlen, const uint8_t *target, int _o_del, int _e_del, int _o_ins, int _e_ins, int xtra) // the first gap costs -(_o+_e) |
| 256 |
{ |
| 257 |
int slen, i, m_b, n_b, te = -1, gmax = 0, minsc, endsc; |
| 258 |
uint64_t *b; |
| 259 |
__m128i zero, oe_del, e_del, oe_ins, e_ins, *H0, *H1, *E, *Hmax; |
| 260 |
kswr_t r; |
| 261 |
|
| 262 |
#if defined __SSE2__ |
| 263 |
#define __max_8(ret, xx) do { \ |
| 264 |
(xx) = _mm_max_epi16((xx), _mm_srli_si128((xx), 8)); \ |
| 265 |
(xx) = _mm_max_epi16((xx), _mm_srli_si128((xx), 4)); \ |
| 266 |
(xx) = _mm_max_epi16((xx), _mm_srli_si128((xx), 2)); \ |
| 267 |
(ret) = _mm_extract_epi16((xx), 0); \ |
| 268 |
} while (0) |
| 269 |
|
| 270 |
// Given entries all either 0x0000 or 0xffff, return whether they are all 0x0000 |
| 271 |
#define allzero_0f_8(xx) (!_mm_movemask_epi8((xx))) |
| 272 |
|
| 273 |
#elif defined __ARM_NEON |
| 274 |
#define __max_8(ret, xx) (ret) = vmaxvq_s16(vreinterpretq_s16_u8((xx))) |
| 275 |
#define allzero_0f_8(xx) (vmaxvq_u16(vreinterpretq_u16_u8((xx))) == 0) |
| 276 |
|
| 277 |
#else |
| 278 |
#define __max_8(ret, xx) (ret) = m128i_max_s16((xx)) |
| 279 |
#define allzero_0f_8(xx) (m128i_allzero((xx))) |
| 280 |
#endif |
| 281 |
|
| 282 |
// initialization |
| 283 |
r = g_defr; |
| 284 |
minsc = (xtra&KSW_XSUBO)? xtra&0xffff : 0x10000; |
| 285 |
endsc = (xtra&KSW_XSTOP)? xtra&0xffff : 0x10000; |
| 286 |
m_b = n_b = 0; b = 0; |
| 287 |
zero = _mm_set1_epi32(0); |
| 288 |
oe_del = _mm_set1_epi16(_o_del + _e_del); |
| 289 |
e_del = _mm_set1_epi16(_e_del); |
| 290 |
oe_ins = _mm_set1_epi16(_o_ins + _e_ins); |
| 291 |
e_ins = _mm_set1_epi16(_e_ins); |
| 292 |
H0 = q->H0; H1 = q->H1; E = q->E; Hmax = q->Hmax; |
| 293 |
slen = q->slen; |
| 294 |
for (i = 0; i < slen; ++i) { |
| 295 |
_mm_store_si128(E + i, zero); |
| 296 |
_mm_store_si128(H0 + i, zero); |
| 297 |
_mm_store_si128(Hmax + i, zero); |
| 298 |
} |
| 299 |
// the core loop |
| 300 |
for (i = 0; i < tlen; ++i) { |
| 301 |
int j, k, imax; |
| 302 |
__m128i e, t, h, f = zero, max = zero, *S = q->qp + target[i] * slen; // s is the 1st score vector |
| 303 |
h = _mm_load_si128(H0 + slen - 1); // h={2,5,8,11,14,17,-1,-1} in the above example |
| 304 |
h = _mm_slli_si128(h, 2); |
| 305 |
for (j = 0; LIKELY(j < slen); ++j) { |
| 306 |
h = _mm_adds_epi16(h, _mm_load_si128(S++)); |
| 307 |
e = _mm_load_si128(E + j); |
| 308 |
h = _mm_max_epi16(h, e); |
| 309 |
h = _mm_max_epi16(h, f); |
| 310 |
max = _mm_max_epi16(max, h); |
| 311 |
_mm_store_si128(H1 + j, h); |
| 312 |
e = _mm_subs_epu16(e, e_del); |
| 313 |
t = _mm_subs_epu16(h, oe_del); |
| 314 |
e = _mm_max_epi16(e, t); |
| 315 |
_mm_store_si128(E + j, e); |
| 316 |
f = _mm_subs_epu16(f, e_ins); |
| 317 |
t = _mm_subs_epu16(h, oe_ins); |
| 318 |
f = _mm_max_epi16(f, t); |
| 319 |
h = _mm_load_si128(H0 + j); |
| 320 |
} |
| 321 |
for (k = 0; LIKELY(k < 16); ++k) { |
| 322 |
f = _mm_slli_si128(f, 2); |
| 323 |
for (j = 0; LIKELY(j < slen); ++j) { |
| 324 |
h = _mm_load_si128(H1 + j); |
| 325 |
h = _mm_max_epi16(h, f); |
| 326 |
_mm_store_si128(H1 + j, h); |
| 327 |
h = _mm_subs_epu16(h, oe_ins); |
| 328 |
f = _mm_subs_epu16(f, e_ins); |
| 329 |
if(UNLIKELY(allzero_0f_8(_mm_cmpgt_epi16(f, h)))) goto end_loop8; |
| 330 |
} |
| 331 |
} |
| 332 |
end_loop8: |
| 333 |
__max_8(imax, max); |
| 334 |
if (imax >= minsc) { |
| 335 |
if (n_b == 0 || (int32_t)b[n_b-1] + 1 != i) { |
| 336 |
if (n_b == m_b) { |
| 337 |
m_b = m_b? m_b<<1 : 8; |
| 338 |
b = (uint64_t*)realloc(b, 8 * m_b); |
| 339 |
} |
| 340 |
b[n_b++] = (uint64_t)imax<<32 | i; |
| 341 |
} else if ((int)(b[n_b-1]>>32) < imax) b[n_b-1] = (uint64_t)imax<<32 | i; // modify the last |
| 342 |
} |
| 343 |
if (imax > gmax) { |
| 344 |
gmax = imax; te = i; |
| 345 |
for (j = 0; LIKELY(j < slen); ++j) |
| 346 |
_mm_store_si128(Hmax + j, _mm_load_si128(H1 + j)); |
| 347 |
if (gmax >= endsc) break; |
| 348 |
} |
| 349 |
S = H1; H1 = H0; H0 = S; |
| 350 |
} |
| 351 |
r.score = gmax; r.te = te; |
| 352 |
{ |
| 353 |
int max = -1, tmp, low, high, qlen = slen * 8; |
| 354 |
uint16_t *t = (uint16_t*)Hmax; |
| 355 |
for (i = 0, r.qe = -1; i < qlen; ++i, ++t) |
| 356 |
if ((int)*t > max) max = *t, r.qe = i / 8 + i % 8 * slen; |
| 357 |
else if ((int)*t == max && (tmp = i / 8 + i % 8 * slen) < r.qe) r.qe = tmp; |
| 358 |
if (b) { |
| 359 |
i = (r.score + q->max - 1) / q->max; |
| 360 |
low = te - i; high = te + i; |
| 361 |
for (i = 0; i < n_b; ++i) { |
| 362 |
int e = (int32_t)b[i]; |
| 363 |
if ((e < low || e > high) && (int)(b[i]>>32) > r.score2) |
| 364 |
r.score2 = b[i]>>32, r.te2 = e; |
| 365 |
} |
| 366 |
} |
| 367 |
} |
| 368 |
free(b); |
| 369 |
return r; |
| 370 |
} |
| 371 |
|
| 372 |
static inline void revseq(int l, uint8_t *s) |
| 373 |
{ |
| 374 |
int i, t; |
| 375 |
for (i = 0; i < l>>1; ++i) |
| 376 |
t = s[i], s[i] = s[l - 1 - i], s[l - 1 - i] = t; |
| 377 |
} |
| 378 |
|
| 379 |
kswr_t ksw_align2(int qlen, uint8_t *query, int tlen, uint8_t *target, int m, const int8_t *mat, int o_del, int e_del, int o_ins, int e_ins, int xtra, kswq_t **qry) |
| 380 |
{ |
| 381 |
int size; |
| 382 |
kswq_t *q; |
| 383 |
kswr_t r, rr; |
| 384 |
kswr_t (*func)(kswq_t*, int, const uint8_t*, int, int, int, int, int); |
| 385 |
|
| 386 |
q = (qry && *qry)? *qry : ksw_qinit((xtra&KSW_XBYTE)? 1 : 2, qlen, query, m, mat); |
| 387 |
if (qry && *qry == 0) *qry = q; |
| 388 |
func = q->size == 2? ksw_i16 : ksw_u8; |
| 389 |
size = q->size; |
| 390 |
r = func(q, tlen, target, o_del, e_del, o_ins, e_ins, xtra); |
| 391 |
if (qry == 0) free(q); |
| 392 |
if ((xtra&KSW_XSTART) == 0 || ((xtra&KSW_XSUBO) && r.score < (xtra&0xffff))) return r; |
| 393 |
revseq(r.qe + 1, query); revseq(r.te + 1, target); // +1 because qe/te points to the exact end, not the position after the end |
| 394 |
q = ksw_qinit(size, r.qe + 1, query, m, mat); |
| 395 |
rr = func(q, tlen, target, o_del, e_del, o_ins, e_ins, KSW_XSTOP | r.score); |
| 396 |
revseq(r.qe + 1, query); revseq(r.te + 1, target); |
| 397 |
free(q); |
| 398 |
if (r.score == rr.score) |
| 399 |
r.tb = r.te - rr.te, r.qb = r.qe - rr.qe; |
| 400 |
return r; |
| 401 |
} |
| 402 |
|
| 403 |
kswr_t ksw_align(int qlen, uint8_t *query, int tlen, uint8_t *target, int m, const int8_t *mat, int gapo, int gape, int xtra, kswq_t **qry) |
| 404 |
{ |
| 405 |
return ksw_align2(qlen, query, tlen, target, m, mat, gapo, gape, gapo, gape, xtra, qry); |
| 406 |
} |
| 407 |
|
| 408 |
/******************** |
| 409 |
*** SW extension *** |
| 410 |
********************/ |
| 411 |
|
| 412 |
typedef struct { |
| 413 |
int32_t h, e; |
| 414 |
} eh_t; |
| 415 |
|
| 416 |
int ksw_extend2(int qlen, const uint8_t *query, int tlen, const uint8_t *target, int m, const int8_t *mat, int o_del, int e_del, int o_ins, int e_ins, int w, int end_bonus, int zdrop, int h0, int *_qle, int *_tle, int *_gtle, int *_gscore, int *_max_off) |
| 417 |
{ |
| 418 |
eh_t *eh; // score array |
| 419 |
int8_t *qp; // query profile |
| 420 |
int i, j, k, oe_del = o_del + e_del, oe_ins = o_ins + e_ins, beg, end, max, max_i, max_j, max_ins, max_del, max_ie, gscore, max_off; |
| 421 |
assert(h0 > 0); |
| 422 |
// allocate memory |
| 423 |
qp = malloc(qlen * m); |
| 424 |
eh = calloc(qlen + 2, 8); |
| 425 |
// generate the query profile |
| 426 |
for (k = i = 0; k < m; ++k) { |
| 427 |
const int8_t *p = &mat[k * m]; |
| 428 |
for (j = 0; j < qlen; ++j) qp[i++] = p[query[j]]; |
| 429 |
} |
| 430 |
// fill the first row |
| 431 |
eh[0].h = h0; eh[1].h = h0 > oe_ins? h0 - oe_ins : 0; |
| 432 |
for (j = 2; j <= qlen && eh[j-1].h > e_ins; ++j) |
| 433 |
eh[j].h = eh[j-1].h - e_ins; |
| 434 |
// adjust $w if it is too large |
| 435 |
k = m * m; |
| 436 |
for (i = 0, max = 0; i < k; ++i) // get the max score |
| 437 |
max = max > mat[i]? max : mat[i]; |
| 438 |
max_ins = (int)((double)(qlen * max + end_bonus - o_ins) / e_ins + 1.); |
| 439 |
max_ins = max_ins > 1? max_ins : 1; |
| 440 |
w = w < max_ins? w : max_ins; |
| 441 |
max_del = (int)((double)(qlen * max + end_bonus - o_del) / e_del + 1.); |
| 442 |
max_del = max_del > 1? max_del : 1; |
| 443 |
w = w < max_del? w : max_del; // TODO: is this necessary? |
| 444 |
// DP loop |
| 445 |
max = h0, max_i = max_j = -1; max_ie = -1, gscore = -1; |
| 446 |
max_off = 0; |
| 447 |
beg = 0, end = qlen; |
| 448 |
for (i = 0; LIKELY(i < tlen); ++i) { |
| 449 |
int t, f = 0, h1, m = 0, mj = -1; |
| 450 |
int8_t *q = &qp[target[i] * qlen]; |
| 451 |
// apply the band and the constraint (if provided) |
| 452 |
if (beg < i - w) beg = i - w; |
| 453 |
if (end > i + w + 1) end = i + w + 1; |
| 454 |
if (end > qlen) end = qlen; |
| 455 |
// compute the first column |
| 456 |
if (beg == 0) { |
| 457 |
h1 = h0 - (o_del + e_del * (i + 1)); |
| 458 |
if (h1 < 0) h1 = 0; |
| 459 |
} else h1 = 0; |
| 460 |
for (j = beg; LIKELY(j < end); ++j) { |
| 461 |
// At the beginning of the loop: eh[j] = { H(i-1,j-1), E(i,j) }, f = F(i,j) and h1 = H(i,j-1) |
| 462 |
// Similar to SSE2-SW, cells are computed in the following order: |
| 463 |
// H(i,j) = max{H(i-1,j-1)+S(i,j), E(i,j), F(i,j)} |
| 464 |
// E(i+1,j) = max{H(i,j)-gapo, E(i,j)} - gape |
| 465 |
// F(i,j+1) = max{H(i,j)-gapo, F(i,j)} - gape |
| 466 |
eh_t *p = &eh[j]; |
| 467 |
int h, M = p->h, e = p->e; // get H(i-1,j-1) and E(i-1,j) |
| 468 |
p->h = h1; // set H(i,j-1) for the next row |
| 469 |
M = M? M + q[j] : 0;// separating H and M to disallow a cigar like "100M3I3D20M" |
| 470 |
h = M > e? M : e; // e and f are guaranteed to be non-negative, so h>=0 even if M<0 |
| 471 |
h = h > f? h : f; |
| 472 |
h1 = h; // save H(i,j) to h1 for the next column |
| 473 |
mj = m > h? mj : j; // record the position where max score is achieved |
| 474 |
m = m > h? m : h; // m is stored at eh[mj+1] |
| 475 |
t = M - oe_del; |
| 476 |
t = t > 0? t : 0; |
| 477 |
e -= e_del; |
| 478 |
e = e > t? e : t; // computed E(i+1,j) |
| 479 |
p->e = e; // save E(i+1,j) for the next row |
| 480 |
t = M - oe_ins; |
| 481 |
t = t > 0? t : 0; |
| 482 |
f -= e_ins; |
| 483 |
f = f > t? f : t; // computed F(i,j+1) |
| 484 |
} |
| 485 |
eh[end].h = h1; eh[end].e = 0; |
| 486 |
if (j == qlen) { |
| 487 |
max_ie = gscore > h1? max_ie : i; |
| 488 |
gscore = gscore > h1? gscore : h1; |
| 489 |
} |
| 490 |
if (m == 0) break; |
| 491 |
if (m > max) { |
| 492 |
max = m, max_i = i, max_j = mj; |
| 493 |
max_off = max_off > abs(mj - i)? max_off : abs(mj - i); |
| 494 |
} else if (zdrop > 0) { |
| 495 |
if (i - max_i > mj - max_j) { |
| 496 |
if (max - m - ((i - max_i) - (mj - max_j)) * e_del > zdrop) break; |
| 497 |
} else { |
| 498 |
if (max - m - ((mj - max_j) - (i - max_i)) * e_ins > zdrop) break; |
| 499 |
} |
| 500 |
} |
| 501 |
// update beg and end for the next round |
| 502 |
for (j = beg; LIKELY(j < end) && eh[j].h == 0 && eh[j].e == 0; ++j); |
| 503 |
beg = j; |
| 504 |
for (j = end; LIKELY(j >= beg) && eh[j].h == 0 && eh[j].e == 0; --j); |
| 505 |
end = j + 2 < qlen? j + 2 : qlen; |
| 506 |
//beg = 0; end = qlen; // uncomment this line for debugging |
| 507 |
} |
| 508 |
free(eh); free(qp); |
| 509 |
if (_qle) *_qle = max_j + 1; |
| 510 |
if (_tle) *_tle = max_i + 1; |
| 511 |
if (_gtle) *_gtle = max_ie + 1; |
| 512 |
if (_gscore) *_gscore = gscore; |
| 513 |
if (_max_off) *_max_off = max_off; |
| 514 |
return max; |
| 515 |
} |
| 516 |
|
| 517 |
int ksw_extend(int qlen, const uint8_t *query, int tlen, const uint8_t *target, int m, const int8_t *mat, int gapo, int gape, int w, int end_bonus, int zdrop, int h0, int *qle, int *tle, int *gtle, int *gscore, int *max_off) |
| 518 |
{ |
| 519 |
return ksw_extend2(qlen, query, tlen, target, m, mat, gapo, gape, gapo, gape, w, end_bonus, zdrop, h0, qle, tle, gtle, gscore, max_off); |
| 520 |
} |
| 521 |
|
| 522 |
/******************** |
| 523 |
* Global alignment * |
| 524 |
********************/ |
| 525 |
|
| 526 |
#define MINUS_INF -0x40000000 |
| 527 |
|
| 528 |
static inline uint32_t *push_cigar(int *n_cigar, int *m_cigar, uint32_t *cigar, int op, int len) |
| 529 |
{ |
| 530 |
if (*n_cigar == 0 || op != (cigar[(*n_cigar) - 1]&0xf)) { |
| 531 |
if (*n_cigar == *m_cigar) { |
| 532 |
*m_cigar = *m_cigar? (*m_cigar)<<1 : 4; |
| 533 |
cigar = realloc(cigar, (*m_cigar) << 2); |
| 534 |
} |
| 535 |
cigar[(*n_cigar)++] = len<<4 | op; |
| 536 |
} else cigar[(*n_cigar)-1] += len<<4; |
| 537 |
return cigar; |
| 538 |
} |
| 539 |
|
| 540 |
int ksw_global2(int qlen, const uint8_t *query, int tlen, const uint8_t *target, int m, const int8_t *mat, int o_del, int e_del, int o_ins, int e_ins, int w, int *n_cigar_, uint32_t **cigar_) |
| 541 |
{ |
| 542 |
eh_t *eh; |
| 543 |
int8_t *qp; // query profile |
| 544 |
int i, j, k, oe_del = o_del + e_del, oe_ins = o_ins + e_ins, score, n_col; |
| 545 |
uint8_t *z; // backtrack matrix; in each cell: f<<4|e<<2|h; in principle, we can halve the memory, but backtrack will be a little more complex |
| 546 |
if (n_cigar_) *n_cigar_ = 0; |
| 547 |
// allocate memory |
| 548 |
n_col = qlen < 2*w+1? qlen : 2*w+1; // maximum #columns of the backtrack matrix |
| 549 |
z = n_cigar_ && cigar_? malloc((long)n_col * tlen) : 0; |
| 550 |
qp = malloc(qlen * m); |
| 551 |
eh = calloc(qlen + 1, 8); |
| 552 |
// generate the query profile |
| 553 |
for (k = i = 0; k < m; ++k) { |
| 554 |
const int8_t *p = &mat[k * m]; |
| 555 |
for (j = 0; j < qlen; ++j) qp[i++] = p[query[j]]; |
| 556 |
} |
| 557 |
// fill the first row |
| 558 |
eh[0].h = 0; eh[0].e = MINUS_INF; |
| 559 |
for (j = 1; j <= qlen && j <= w; ++j) |
| 560 |
eh[j].h = -(o_ins + e_ins * j), eh[j].e = MINUS_INF; |
| 561 |
for (; j <= qlen; ++j) eh[j].h = eh[j].e = MINUS_INF; // everything is -inf outside the band |
| 562 |
// DP loop |
| 563 |
for (i = 0; LIKELY(i < tlen); ++i) { // target sequence is in the outer loop |
| 564 |
int32_t f = MINUS_INF, h1, beg, end, t; |
| 565 |
int8_t *q = &qp[target[i] * qlen]; |
| 566 |
beg = i > w? i - w : 0; |
| 567 |
end = i + w + 1 < qlen? i + w + 1 : qlen; // only loop through [beg,end) of the query sequence |
| 568 |
h1 = beg == 0? -(o_del + e_del * (i + 1)) : MINUS_INF; |
| 569 |
if (n_cigar_ && cigar_) { |
| 570 |
uint8_t *zi = &z[(long)i * n_col]; |
| 571 |
for (j = beg; LIKELY(j < end); ++j) { |
| 572 |
// At the beginning of the loop: eh[j] = { H(i-1,j-1), E(i,j) }, f = F(i,j) and h1 = H(i,j-1) |
| 573 |
// Cells are computed in the following order: |
| 574 |
// M(i,j) = H(i-1,j-1) + S(i,j) |
| 575 |
// H(i,j) = max{M(i,j), E(i,j), F(i,j)} |
| 576 |
// E(i+1,j) = max{M(i,j)-gapo, E(i,j)} - gape |
| 577 |
// F(i,j+1) = max{M(i,j)-gapo, F(i,j)} - gape |
| 578 |
// We have to separate M(i,j); otherwise the direction may not be recorded correctly. |
| 579 |
// However, a CIGAR like "10M3I3D10M" allowed by local() is disallowed by global(). |
| 580 |
// Such a CIGAR may occur, in theory, if mismatch_penalty > 2*gap_ext_penalty + 2*gap_open_penalty/k. |
| 581 |
// In practice, this should happen very rarely given a reasonable scoring system. |
| 582 |
eh_t *p = &eh[j]; |
| 583 |
int32_t h, m = p->h, e = p->e; |
| 584 |
uint8_t d; // direction |
| 585 |
p->h = h1; |
| 586 |
m += q[j]; |
| 587 |
d = m >= e? 0 : 1; |
| 588 |
h = m >= e? m : e; |
| 589 |
d = h >= f? d : 2; |
| 590 |
h = h >= f? h : f; |
| 591 |
h1 = h; |
| 592 |
t = m - oe_del; |
| 593 |
e -= e_del; |
| 594 |
d |= e > t? 1<<2 : 0; |
| 595 |
e = e > t? e : t; |
| 596 |
p->e = e; |
| 597 |
t = m - oe_ins; |
| 598 |
f -= e_ins; |
| 599 |
d |= f > t? 2<<4 : 0; // if we want to halve the memory, use one bit only, instead of two |
| 600 |
f = f > t? f : t; |
| 601 |
zi[j - beg] = d; // z[i,j] keeps h for the current cell and e/f for the next cell |
| 602 |
} |
| 603 |
} else { |
| 604 |
for (j = beg; LIKELY(j < end); ++j) { |
| 605 |
eh_t *p = &eh[j]; |
| 606 |
int32_t h, m = p->h, e = p->e; |
| 607 |
p->h = h1; |
| 608 |
m += q[j]; |
| 609 |
h = m >= e? m : e; |
| 610 |
h = h >= f? h : f; |
| 611 |
h1 = h; |
| 612 |
t = m - oe_del; |
| 613 |
e -= e_del; |
| 614 |
e = e > t? e : t; |
| 615 |
p->e = e; |
| 616 |
t = m - oe_ins; |
| 617 |
f -= e_ins; |
| 618 |
f = f > t? f : t; |
| 619 |
} |
| 620 |
} |
| 621 |
eh[end].h = h1; eh[end].e = MINUS_INF; |
| 622 |
} |
| 623 |
score = eh[qlen].h; |
| 624 |
if (n_cigar_ && cigar_) { // backtrack |
| 625 |
int n_cigar = 0, m_cigar = 0, which = 0; |
| 626 |
uint32_t *cigar = 0, tmp; |
| 627 |
i = tlen - 1; k = (i + w + 1 < qlen? i + w + 1 : qlen) - 1; // (i,k) points to the last cell |
| 628 |
while (i >= 0 && k >= 0) { |
| 629 |
which = z[(long)i * n_col + (k - (i > w? i - w : 0))] >> (which<<1) & 3; |
| 630 |
if (which == 0) cigar = push_cigar(&n_cigar, &m_cigar, cigar, 0, 1), --i, --k; |
| 631 |
else if (which == 1) cigar = push_cigar(&n_cigar, &m_cigar, cigar, 2, 1), --i; |
| 632 |
else cigar = push_cigar(&n_cigar, &m_cigar, cigar, 1, 1), --k; |
| 633 |
} |
| 634 |
if (i >= 0) cigar = push_cigar(&n_cigar, &m_cigar, cigar, 2, i + 1); |
| 635 |
if (k >= 0) cigar = push_cigar(&n_cigar, &m_cigar, cigar, 1, k + 1); |
| 636 |
for (i = 0; i < n_cigar>>1; ++i) // reverse CIGAR |
| 637 |
tmp = cigar[i], cigar[i] = cigar[n_cigar-1-i], cigar[n_cigar-1-i] = tmp; |
| 638 |
*n_cigar_ = n_cigar, *cigar_ = cigar; |
| 639 |
} |
| 640 |
free(eh); free(qp); free(z); |
| 641 |
return score; |
| 642 |
} |
| 643 |
|
| 644 |
int ksw_global(int qlen, const uint8_t *query, int tlen, const uint8_t *target, int m, const int8_t *mat, int gapo, int gape, int w, int *n_cigar_, uint32_t **cigar_) |
| 645 |
{ |
| 646 |
return ksw_global2(qlen, query, tlen, target, m, mat, gapo, gape, gapo, gape, w, n_cigar_, cigar_); |
| 647 |
} |
| 648 |
|
| 649 |
/******************************************* |
| 650 |
* Main function (not compiled by default) * |
| 651 |
*******************************************/ |
| 652 |
|
| 653 |
#ifdef _KSW_MAIN |
| 654 |
|
| 655 |
#include <unistd.h> |
| 656 |
#include <stdio.h> |
| 657 |
#include <zlib.h> |
| 658 |
#include "kseq.h" |
| 659 |
KSEQ_INIT(gzFile, err_gzread) |
| 660 |
|
| 661 |
unsigned char seq_nt4_table[256] = { |
| 662 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 663 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 664 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 665 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 666 |
4, 0, 4, 1, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, |
| 667 |
4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 668 |
4, 0, 4, 1, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, |
| 669 |
4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 670 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 671 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 672 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 673 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 674 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 675 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 676 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, |
| 677 |
4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 |
| 678 |
}; |
| 679 |
|
| 680 |
int main(int argc, char *argv[]) |
| 681 |
{ |
| 682 |
int c, sa = 1, sb = 3, i, j, k, forward_only = 0, max_rseq = 0; |
| 683 |
int8_t mat[25]; |
| 684 |
int gapo = 5, gape = 2, minsc = 0, xtra = KSW_XSTART; |
| 685 |
uint8_t *rseq = 0; |
| 686 |
gzFile fpt, fpq; |
| 687 |
kseq_t *kst, *ksq; |
| 688 |
|
| 689 |
// parse command line |
| 690 |
while ((c = getopt(argc, argv, "a:b:q:r:ft:1")) >= 0) { |
| 691 |
switch (c) { |
| 692 |
case 'a': sa = atoi(optarg); break; |
| 693 |
case 'b': sb = atoi(optarg); break; |
| 694 |
case 'q': gapo = atoi(optarg); break; |
| 695 |
case 'r': gape = atoi(optarg); break; |
| 696 |
case 't': minsc = atoi(optarg); break; |
| 697 |
case 'f': forward_only = 1; break; |
| 698 |
case '1': xtra |= KSW_XBYTE; break; |
| 699 |
} |
| 700 |
} |
| 701 |
if (optind + 2 > argc) { |
| 702 |
fprintf(stderr, "Usage: ksw [-1] [-f] [-a%d] [-b%d] [-q%d] [-r%d] [-t%d] <target.fa> <query.fa>\n", sa, sb, gapo, gape, minsc); |
| 703 |
return 1; |
| 704 |
} |
| 705 |
if (minsc > 0xffff) minsc = 0xffff; |
| 706 |
xtra |= KSW_XSUBO | minsc; |
| 707 |
// initialize scoring matrix |
| 708 |
for (i = k = 0; i < 4; ++i) { |
| 709 |
for (j = 0; j < 4; ++j) |
| 710 |
mat[k++] = i == j? sa : -sb; |
| 711 |
mat[k++] = 0; // ambiguous base |
| 712 |
} |
| 713 |
for (j = 0; j < 5; ++j) mat[k++] = 0; |
| 714 |
// open file |
| 715 |
fpt = xzopen(argv[optind], "r"); kst = kseq_init(fpt); |
| 716 |
fpq = xzopen(argv[optind+1], "r"); ksq = kseq_init(fpq); |
| 717 |
// all-pair alignment |
| 718 |
while (kseq_read(ksq) > 0) { |
| 719 |
kswq_t *q[2] = {0, 0}; |
| 720 |
kswr_t r; |
| 721 |
for (i = 0; i < (int)ksq->seq.l; ++i) ksq->seq.s[i] = seq_nt4_table[(int)ksq->seq.s[i]]; |
| 722 |
if (!forward_only) { // reverse |
| 723 |
if ((int)ksq->seq.m > max_rseq) { |
| 724 |
max_rseq = ksq->seq.m; |
| 725 |
rseq = (uint8_t*)realloc(rseq, max_rseq); |
| 726 |
} |
| 727 |
for (i = 0, j = ksq->seq.l - 1; i < (int)ksq->seq.l; ++i, --j) |
| 728 |
rseq[j] = ksq->seq.s[i] == 4? 4 : 3 - ksq->seq.s[i]; |
| 729 |
} |
| 730 |
gzrewind(fpt); kseq_rewind(kst); |
| 731 |
while (kseq_read(kst) > 0) { |
| 732 |
for (i = 0; i < (int)kst->seq.l; ++i) kst->seq.s[i] = seq_nt4_table[(int)kst->seq.s[i]]; |
| 733 |
r = ksw_align(ksq->seq.l, (uint8_t*)ksq->seq.s, kst->seq.l, (uint8_t*)kst->seq.s, 5, mat, gapo, gape, xtra, &q[0]); |
| 734 |
if (r.score >= minsc) |
| 735 |
err_printf("%s\t%d\t%d\t%s\t%d\t%d\t%d\t%d\t%d\n", kst->name.s, r.tb, r.te+1, ksq->name.s, r.qb, r.qe+1, r.score, r.score2, r.te2); |
| 736 |
if (rseq) { |
| 737 |
r = ksw_align(ksq->seq.l, rseq, kst->seq.l, (uint8_t*)kst->seq.s, 5, mat, gapo, gape, xtra, &q[1]); |
| 738 |
if (r.score >= minsc) |
| 739 |
err_printf("%s\t%d\t%d\t%s\t%d\t%d\t%d\t%d\t%d\n", kst->name.s, r.tb, r.te+1, ksq->name.s, (int)ksq->seq.l - r.qb, (int)ksq->seq.l - 1 - r.qe, r.score, r.score2, r.te2); |
| 740 |
} |
| 741 |
} |
| 742 |
free(q[0]); free(q[1]); |
| 743 |
} |
| 744 |
free(rseq); |
| 745 |
kseq_destroy(kst); err_gzclose(fpt); |
| 746 |
kseq_destroy(ksq); err_gzclose(fpq); |
| 747 |
return 0; |
| 748 |
} |
| 749 |
#endif |