Debian Codegraph @

bwa-apache2/bwt_gen.c

raw
1 /*
2
3 BWTConstruct.c BWT-Index Construction
4
5 This module constructs BWT and auxiliary data structures.
6
7 Copyright (C) 2004, Wong Chi Kwong.
8
9 This program is free software; you can redistribute it and/or
10 modify it under the terms of the GNU General Public License
11 as published by the Free Software Foundation; either version 2
12 of the License, or (at your option) any later version.
13
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with this program; if not, write to the Free Software
21 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
22
23 */
24
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <string.h>
28 #include <assert.h>
29 #include <stdint.h>
30 #include <errno.h>
31 #include "QSufSort.h"
32
33 #ifdef USE_MALLOC_WRAPPERS
34 # include "malloc_wrap.h"
35 #endif
36
37 typedef uint64_t bgint_t;
38 typedef int64_t sbgint_t;
39
40 #define ALPHABET_SIZE 4
41 #define BIT_PER_CHAR 2
42 #define CHAR_PER_WORD 16
43 #define CHAR_PER_BYTE 4
44
45 #define BITS_IN_WORD 32
46 #define BITS_IN_BYTE 8
47 #define BYTES_IN_WORD 4
48
49 #define ALL_ONE_MASK 0xFFFFFFFF
50 #define DNA_OCC_CNT_TABLE_SIZE_IN_WORD 65536
51
52 #define BITS_PER_OCC_VALUE 16
53 #define OCC_VALUE_PER_WORD 2
54 #define OCC_INTERVAL 256
55 #define OCC_INTERVAL_MAJOR 65536
56
57 #define TRUE 1
58 #define FALSE 0
59
60 #define BWTINC_INSERT_SORT_NUM_ITEM 7
61
62 #define MIN_AVAILABLE_WORD 0x10000
63
64 #define average(value1, value2) ( ((value1) & (value2)) + ((value1) ^ (value2)) / 2 )
65 #define min(value1, value2) ( ((value1) < (value2)) ? (value1) : (value2) )
66 #define max(value1, value2) ( ((value1) > (value2)) ? (value1) : (value2) )
67 #define med3(a, b, c) ( a<b ? (b<c ? b : a<c ? c : a) : (b>c ? b : a>c ? c : a))
68 #define swap(a, b, t); t = a; a = b; b = t;
69 #define truncateLeft(value, offset) ( (value) << (offset) >> (offset) )
70 #define truncateRight(value, offset) ( (value) >> (offset) << (offset) )
71 #define DNA_OCC_SUM_EXCEPTION(sum) ((sum & 0xfefefeff) == 0)
72
73 typedef struct BWT {
74 bgint_t textLength; // length of the text
75 bgint_t inverseSa0; // SA-1[0]
76 bgint_t *cumulativeFreq; // cumulative frequency
77 unsigned int *bwtCode; // BWT code
78 unsigned int *occValue; // Occurrence values stored explicitly
79 bgint_t *occValueMajor; // Occurrence values stored explicitly
80 unsigned int *decodeTable; // For decoding BWT by table lookup
81 bgint_t bwtSizeInWord; // Temporary variable to hold the memory allocated
82 bgint_t occSizeInWord; // Temporary variable to hold the memory allocated
83 bgint_t occMajorSizeInWord; // Temporary variable to hold the memory allocated
84 } BWT;
85
86 typedef struct BWTInc {
87 BWT *bwt;
88 unsigned int numberOfIterationDone;
89 bgint_t *cumulativeCountInCurrentBuild;
90 bgint_t availableWord;
91 bgint_t buildSize;
92 bgint_t initialMaxBuildSize;
93 bgint_t incMaxBuildSize;
94 unsigned int firstCharInLastIteration;
95 unsigned int *workingMemory;
96 unsigned int *packedText;
97 unsigned char *textBuffer;
98 unsigned int *packedShift;
99 } BWTInc;
100
101 static bgint_t TextLengthFromBytePacked(bgint_t bytePackedLength, unsigned int bitPerChar,
102 unsigned int lastByteLength)
103 {
104 return (bytePackedLength - 1) * (BITS_IN_BYTE / bitPerChar) + lastByteLength;
105 }
106
107 static void initializeVAL(unsigned int *startAddr, const bgint_t length, const unsigned int initValue)
108 {
109 bgint_t i;
110 for (i=0; i<length; i++) startAddr[i] = initValue;
111 }
112
113 static void initializeVAL_bg(bgint_t *startAddr, const bgint_t length, const bgint_t initValue)
114 {
115 bgint_t i;
116 for (i=0; i<length; i++) startAddr[i] = initValue;
117 }
118
119 static void GenerateDNAOccCountTable(unsigned int *dnaDecodeTable)
120 {
121 unsigned int i, j, c, t;
122
123 for (i=0; i<DNA_OCC_CNT_TABLE_SIZE_IN_WORD; i++) {
124 dnaDecodeTable[i] = 0;
125 c = i;
126 for (j=0; j<8; j++) {
127 t = c & 0x00000003;
128 dnaDecodeTable[i] += 1 << (t * 8);
129 c >>= 2;
130 }
131 }
132
133 }
134 // for BWTIncCreate()
135 static bgint_t BWTOccValueMajorSizeInWord(const bgint_t numChar)
136 {
137 bgint_t numOfOccValue;
138 unsigned numOfOccIntervalPerMajor;
139 numOfOccValue = (numChar + OCC_INTERVAL - 1) / OCC_INTERVAL + 1; // Value at both end for bi-directional encoding
140 numOfOccIntervalPerMajor = OCC_INTERVAL_MAJOR / OCC_INTERVAL;
141 return (numOfOccValue + numOfOccIntervalPerMajor - 1) / numOfOccIntervalPerMajor * ALPHABET_SIZE;
142 }
143 // for BWTIncCreate()
144 static bgint_t BWTOccValueMinorSizeInWord(const bgint_t numChar)
145 {
146 bgint_t numOfOccValue;
147 numOfOccValue = (numChar + OCC_INTERVAL - 1) / OCC_INTERVAL + 1; // Value at both end for bi-directional encoding
148 return (numOfOccValue + OCC_VALUE_PER_WORD - 1) / OCC_VALUE_PER_WORD * ALPHABET_SIZE;
149 }
150 // for BWTIncCreate()
151 static bgint_t BWTResidentSizeInWord(const bgint_t numChar) {
152
153 bgint_t numCharRoundUpToOccInterval;
154
155 // The $ in BWT at the position of inverseSa0 is not encoded
156 numCharRoundUpToOccInterval = (numChar + OCC_INTERVAL - 1) / OCC_INTERVAL * OCC_INTERVAL;
157
158 return (numCharRoundUpToOccInterval + CHAR_PER_WORD - 1) / CHAR_PER_WORD;
159
160 }
161
162 static void BWTIncSetBuildSizeAndTextAddr(BWTInc *bwtInc)
163 {
164 bgint_t maxBuildSize;
165
166 if (bwtInc->bwt->textLength == 0) {
167 // initial build
168 // Minus 2 because n+1 entries of seq and rank needed for n char
169 maxBuildSize = (bwtInc->availableWord - (2 + OCC_INTERVAL / CHAR_PER_WORD) * (sizeof(bgint_t) / 4))
170 / (2 * CHAR_PER_WORD + 1) * CHAR_PER_WORD / (sizeof(bgint_t) / 4);
171 if (bwtInc->initialMaxBuildSize > 0) {
172 bwtInc->buildSize = min(bwtInc->initialMaxBuildSize, maxBuildSize);
173 } else {
174 bwtInc->buildSize = maxBuildSize;
175 }
176 } else {
177 // Minus 3 because n+1 entries of sorted rank, seq and rank needed for n char
178 // Minus numberOfIterationDone because bwt slightly shift to left in each iteration
179 maxBuildSize = (bwtInc->availableWord - bwtInc->bwt->bwtSizeInWord - bwtInc->bwt->occSizeInWord
180 - (3 + bwtInc->numberOfIterationDone * OCC_INTERVAL / BIT_PER_CHAR) * (sizeof(bgint_t) / 4))
181 / 3 / (sizeof(bgint_t) / 4);
182 if (maxBuildSize < CHAR_PER_WORD) {
183 fprintf(stderr, "BWTIncSetBuildSizeAndTextAddr(): Not enough space allocated to continue construction!\n");
184 exit(1);
185 }
186 if (bwtInc->incMaxBuildSize > 0) {
187 bwtInc->buildSize = min(bwtInc->incMaxBuildSize, maxBuildSize);
188 } else {
189 bwtInc->buildSize = maxBuildSize;
190 }
191 if (bwtInc->buildSize < CHAR_PER_WORD)
192 bwtInc->buildSize = CHAR_PER_WORD;
193 }
194
195 if (bwtInc->buildSize < CHAR_PER_WORD) {
196 fprintf(stderr, "BWTIncSetBuildSizeAndTextAddr(): Not enough space allocated to continue construction!\n");
197 exit(1);
198 }
199
200 bwtInc->buildSize = bwtInc->buildSize / CHAR_PER_WORD * CHAR_PER_WORD;
201
202 bwtInc->packedText = bwtInc->workingMemory + 2 * (bwtInc->buildSize + 1) * (sizeof(bgint_t) / 4);
203 bwtInc->textBuffer = (unsigned char*)(bwtInc->workingMemory + (bwtInc->buildSize + 1) * (sizeof(bgint_t) / 4));
204 }
205
206 // for ceilLog2()
207 unsigned int leadingZero(const unsigned int input)
208 {
209 unsigned int l;
210 const static unsigned int leadingZero8bit[256] = {8,7,6,6,5,5,5,5,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
211 2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
212 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
213 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
214 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
215 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
216 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
217 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
218
219 if (input & 0xFFFF0000) {
220 if (input & 0xFF000000) {
221 l = leadingZero8bit[input >> 24];
222 } else {
223 l = 8 + leadingZero8bit[input >> 16];
224 }
225 } else {
226 if (input & 0x0000FF00) {
227 l = 16 + leadingZero8bit[input >> 8];
228 } else {
229 l = 24 + leadingZero8bit[input];
230 }
231 }
232 return l;
233
234 }
235 // for BitPerBytePackedChar()
236 static unsigned int ceilLog2(const unsigned int input)
237 {
238 if (input <= 1) return 0;
239 return BITS_IN_WORD - leadingZero(input - 1);
240
241 }
242 // for ConvertBytePackedToWordPacked()
243 static unsigned int BitPerBytePackedChar(const unsigned int alphabetSize)
244 {
245 unsigned int bitPerChar;
246 bitPerChar = ceilLog2(alphabetSize);
247 // Return the largest number of bit that does not affect packing efficiency
248 if (BITS_IN_BYTE / (BITS_IN_BYTE / bitPerChar) > bitPerChar)
249 bitPerChar = BITS_IN_BYTE / (BITS_IN_BYTE / bitPerChar);
250 return bitPerChar;
251 }
252 // for ConvertBytePackedToWordPacked()
253 static unsigned int BitPerWordPackedChar(const unsigned int alphabetSize)
254 {
255 return ceilLog2(alphabetSize);
256 }
257
258 static void ConvertBytePackedToWordPacked(const unsigned char *input, unsigned int *output, const unsigned int alphabetSize,
259 const bgint_t textLength)
260 {
261 bgint_t i;
262 unsigned int j, k, c;
263 unsigned int bitPerBytePackedChar;
264 unsigned int bitPerWordPackedChar;
265 unsigned int charPerWord;
266 unsigned int charPerByte;
267 unsigned int bytePerIteration;
268 bgint_t byteProcessed = 0;
269 bgint_t wordProcessed = 0;
270 unsigned int mask, shift;
271
272 unsigned int buffer[BITS_IN_WORD];
273
274 bitPerBytePackedChar = BitPerBytePackedChar(alphabetSize);
275 bitPerWordPackedChar = BitPerWordPackedChar(alphabetSize);
276 charPerByte = BITS_IN_BYTE / bitPerBytePackedChar;
277 charPerWord = BITS_IN_WORD / bitPerWordPackedChar;
278
279 bytePerIteration = charPerWord / charPerByte;
280 mask = truncateRight(ALL_ONE_MASK, BITS_IN_WORD - bitPerWordPackedChar);
281 shift = BITS_IN_WORD - BITS_IN_BYTE + bitPerBytePackedChar - bitPerWordPackedChar;
282
283 while ((wordProcessed + 1) * charPerWord < textLength) {
284
285 k = 0;
286 for (i=0; i<bytePerIteration; i++) {
287 c = (unsigned int)input[byteProcessed] << shift;
288 for (j=0; j<charPerByte; j++) {
289 buffer[k] = c & mask;
290 c <<= bitPerBytePackedChar;
291 k++;
292 }
293 byteProcessed++;
294 }
295
296 c = 0;
297 for (i=0; i<charPerWord; i++) {
298 c |= buffer[i] >> bitPerWordPackedChar * i;
299 }
300 output[wordProcessed] = c;
301 wordProcessed++;
302
303 }
304
305 k = 0;
306 for (i=0; i < (textLength - wordProcessed * charPerWord - 1) / charPerByte + 1; i++) {
307 c = (unsigned int)input[byteProcessed] << shift;
308 for (j=0; j<charPerByte; j++) {
309 buffer[k] = c & mask;
310 c <<= bitPerBytePackedChar;
311 k++;
312 }
313 byteProcessed++;
314 }
315
316 c = 0;
317 for (i=0; i<textLength - wordProcessed * charPerWord; i++) {
318 c |= buffer[i] >> bitPerWordPackedChar * i;
319 }
320 output[wordProcessed] = c;
321 }
322
323 BWT *BWTCreate(const bgint_t textLength, unsigned int *decodeTable)
324 {
325 BWT *bwt;
326
327 bwt = (BWT*)calloc(1, sizeof(BWT));
328
329 bwt->textLength = 0;
330
331 bwt->cumulativeFreq = (bgint_t*)calloc((ALPHABET_SIZE + 1), sizeof(bgint_t));
332 initializeVAL_bg(bwt->cumulativeFreq, ALPHABET_SIZE + 1, 0);
333
334 bwt->bwtSizeInWord = 0;
335
336 // Generate decode tables
337 if (decodeTable == NULL) {
338 bwt->decodeTable = (unsigned*)calloc(DNA_OCC_CNT_TABLE_SIZE_IN_WORD, sizeof(unsigned int));
339 GenerateDNAOccCountTable(bwt->decodeTable);
340 } else {
341 // FIXME Prevent BWTFree() from freeing decodeTable in this case
342 bwt->decodeTable = decodeTable;
343 }
344
345 bwt->occMajorSizeInWord = BWTOccValueMajorSizeInWord(textLength);
346 bwt->occValueMajor = (bgint_t*)calloc(bwt->occMajorSizeInWord, sizeof(bgint_t));
347
348 bwt->occSizeInWord = 0;
349 bwt->occValue = NULL;
350
351 return bwt;
352 }
353
354 BWTInc *BWTIncCreate(const bgint_t textLength, unsigned int initialMaxBuildSize, unsigned int incMaxBuildSize)
355 {
356 BWTInc *bwtInc;
357 unsigned int i, n_iter;
358
359 if (textLength < incMaxBuildSize) incMaxBuildSize = textLength;
360 if (textLength < initialMaxBuildSize) initialMaxBuildSize = textLength;
361
362 bwtInc = (BWTInc*)calloc(1, sizeof(BWTInc));
363 bwtInc->numberOfIterationDone = 0;
364 bwtInc->bwt = BWTCreate(textLength, NULL);
365 bwtInc->initialMaxBuildSize = initialMaxBuildSize;
366 bwtInc->incMaxBuildSize = incMaxBuildSize;
367 bwtInc->cumulativeCountInCurrentBuild = (bgint_t*)calloc((ALPHABET_SIZE + 1), sizeof(bgint_t));
368 initializeVAL_bg(bwtInc->cumulativeCountInCurrentBuild, ALPHABET_SIZE + 1, 0);
369
370 // Build frequently accessed data
371 bwtInc->packedShift = (unsigned*)calloc(CHAR_PER_WORD, sizeof(unsigned int));
372 for (i=0; i<CHAR_PER_WORD; i++)
373 bwtInc->packedShift[i] = BITS_IN_WORD - (i+1) * BIT_PER_CHAR;
374
375 n_iter = (textLength - initialMaxBuildSize) / incMaxBuildSize + 1;
376 bwtInc->availableWord = BWTResidentSizeInWord(textLength) + BWTOccValueMinorSizeInWord(textLength) // minimal memory requirement
377 + OCC_INTERVAL / BIT_PER_CHAR * n_iter * 2 * (sizeof(bgint_t) / 4) // buffer at the end of occ array
378 + incMaxBuildSize/5 * 3 * (sizeof(bgint_t) / 4); // space for the 3 temporary arrays in each iteration
379 if (bwtInc->availableWord < MIN_AVAILABLE_WORD) bwtInc->availableWord = MIN_AVAILABLE_WORD; // lh3: otherwise segfaul when availableWord is too small
380 fprintf(stderr, "[%s] textLength=%ld, availableWord=%ld\n", __func__, (long)textLength, (long)bwtInc->availableWord);
381 bwtInc->workingMemory = (unsigned*)calloc(bwtInc->availableWord, BYTES_IN_WORD);
382
383 return bwtInc;
384 }
385 // for BWTIncConstruct()
386 static void BWTIncPutPackedTextToRank(const unsigned int *packedText, bgint_t* __restrict rank,
387 bgint_t* __restrict cumulativeCount, const bgint_t numChar)
388 {
389 bgint_t i;
390 unsigned int j;
391 unsigned int c, t;
392 unsigned int packedMask;
393 bgint_t rankIndex;
394 bgint_t lastWord;
395 unsigned int numCharInLastWord;
396
397 lastWord = (numChar - 1) / CHAR_PER_WORD;
398 numCharInLastWord = numChar - lastWord * CHAR_PER_WORD;
399
400 packedMask = ALL_ONE_MASK >> (BITS_IN_WORD - BIT_PER_CHAR);
401 rankIndex = numChar - 1;
402
403 t = packedText[lastWord] >> (BITS_IN_WORD - numCharInLastWord * BIT_PER_CHAR);
404 for (i=0; i<numCharInLastWord; i++) {
405 c = t & packedMask;
406 cumulativeCount[c+1]++;
407 rank[rankIndex] = c;
408 rankIndex--;
409 t >>= BIT_PER_CHAR;
410 }
411
412 for (i=lastWord; i--;) { // loop from lastWord - 1 to 0
413 t = packedText[i];
414 for (j=0; j<CHAR_PER_WORD; j++) {
415 c = t & packedMask;
416 cumulativeCount[c+1]++;
417 rank[rankIndex] = c;
418 rankIndex--;
419 t >>= BIT_PER_CHAR;
420 }
421 }
422
423 // Convert occurrence to cumulativeCount
424 cumulativeCount[2] += cumulativeCount[1];
425 cumulativeCount[3] += cumulativeCount[2];
426 cumulativeCount[4] += cumulativeCount[3];
427 }
428
429
430 static void ForwardDNAAllOccCountNoLimit(const unsigned int* dna, const bgint_t index,
431 bgint_t* __restrict occCount, const unsigned int* dnaDecodeTable)
432 {
433 static const unsigned int truncateRightMask[16] = { 0x00000000, 0xC0000000, 0xF0000000, 0xFC000000,
434 0xFF000000, 0xFFC00000, 0xFFF00000, 0xFFFC0000,
435 0xFFFF0000, 0xFFFFC000, 0xFFFFF000, 0xFFFFFC00,
436 0xFFFFFF00, 0xFFFFFFC0, 0xFFFFFFF0, 0xFFFFFFFC };
437
438 bgint_t iteration, i;
439 unsigned int wordToCount, charToCount;
440 unsigned int j, c, sum;
441
442 occCount[0] = 0;
443 occCount[1] = 0;
444 occCount[2] = 0;
445 occCount[3] = 0;
446
447 iteration = index / 256;
448 wordToCount = (index - iteration * 256) / 16;
449 charToCount = index - iteration * 256 - wordToCount * 16;
450
451 for (i=0; i<iteration; i++) {
452
453 sum = 0;
454 for (j=0; j<16; j++) {
455 sum += dnaDecodeTable[*dna >> 16];
456 sum += dnaDecodeTable[*dna & 0x0000FFFF];
457 dna++;
458 }
459 if (!DNA_OCC_SUM_EXCEPTION(sum)) {
460 occCount[0] += sum & 0x000000FF; sum >>= 8;
461 occCount[1] += sum & 0x000000FF; sum >>= 8;
462 occCount[2] += sum & 0x000000FF; sum >>= 8;
463 occCount[3] += sum;
464 } else {
465 // only some or all of the 3 bits are on
466 // in reality, only one of the four cases are possible
467 if (sum == 0x00000100) {
468 occCount[0] += 256;
469 } else if (sum == 0x00010000) {
470 occCount[1] += 256;
471 } else if (sum == 0x01000000) {
472 occCount[2] += 256;
473 } else if (sum == 0x00000000) {
474 occCount[3] += 256;
475 } else {
476 fprintf(stderr, "ForwardDNAAllOccCountNoLimit(): DNA occ sum exception!\n");
477 exit(1);
478 }
479 }
480
481 }
482
483 sum = 0;
484 for (j=0; j<wordToCount; j++) {
485 sum += dnaDecodeTable[*dna >> 16];
486 sum += dnaDecodeTable[*dna & 0x0000FFFF];
487 dna++;
488 }
489
490 if (charToCount > 0) {
491 c = *dna & truncateRightMask[charToCount]; // increase count of 'a' by 16 - c;
492 sum += dnaDecodeTable[c >> 16];
493 sum += dnaDecodeTable[c & 0xFFFF];
494 sum += charToCount - 16; // decrease count of 'a' by 16 - positionToProcess
495 }
496
497 occCount[0] += sum & 0x000000FF; sum >>= 8;
498 occCount[1] += sum & 0x000000FF; sum >>= 8;
499 occCount[2] += sum & 0x000000FF; sum >>= 8;
500 occCount[3] += sum;
501 }
502
503 static void BWTIncBuildPackedBwt(const bgint_t *relativeRank, unsigned int* __restrict bwt, const bgint_t numChar,
504 const bgint_t *cumulativeCount, const unsigned int *packedShift) {
505
506 bgint_t i, r;
507 unsigned int c;
508 bgint_t previousRank, currentRank;
509 bgint_t wordIndex, charIndex;
510 bgint_t inverseSa0;
511
512 inverseSa0 = previousRank = relativeRank[0];
513
514 for (i=1; i<=numChar; i++) {
515 currentRank = relativeRank[i];
516 // previousRank > cumulativeCount[c] because $ is one of the char
517 c = (previousRank > cumulativeCount[1]) + (previousRank > cumulativeCount[2])
518 + (previousRank > cumulativeCount[3]);
519 // set bwt for currentRank
520 if (c > 0) {
521 // c <> 'a'
522 r = currentRank;
523 if (r > inverseSa0) {
524 // - 1 because $ at inverseSa0 is not encoded
525 r--;
526 }
527 wordIndex = r / CHAR_PER_WORD;
528 charIndex = r - wordIndex * CHAR_PER_WORD;
529 bwt[wordIndex] |= c << packedShift[charIndex];
530 }
531 previousRank = currentRank;
532 }
533 }
534
535 static inline bgint_t BWTOccValueExplicit(const BWT *bwt, const bgint_t occIndexExplicit,
536 const unsigned int character)
537 {
538 bgint_t occIndexMajor;
539
540 occIndexMajor = occIndexExplicit * OCC_INTERVAL / OCC_INTERVAL_MAJOR;
541
542 if (occIndexExplicit % OCC_VALUE_PER_WORD == 0) {
543 return bwt->occValueMajor[occIndexMajor * ALPHABET_SIZE + character] +
544 (bwt->occValue[occIndexExplicit / OCC_VALUE_PER_WORD * ALPHABET_SIZE + character] >> 16);
545
546 } else {
547 return bwt->occValueMajor[occIndexMajor * ALPHABET_SIZE + character] +
548 (bwt->occValue[occIndexExplicit / OCC_VALUE_PER_WORD * ALPHABET_SIZE + character] & 0x0000FFFF);
549 }
550 }
551
552
553 static unsigned int ForwardDNAOccCount(const unsigned int* dna, const unsigned int index, const unsigned int character,
554 const unsigned int* dnaDecodeTable)
555 {
556 static const unsigned int truncateRightMask[16] = { 0x00000000, 0xC0000000, 0xF0000000, 0xFC000000,
557 0xFF000000, 0xFFC00000, 0xFFF00000, 0xFFFC0000,
558 0xFFFF0000, 0xFFFFC000, 0xFFFFF000, 0xFFFFFC00,
559 0xFFFFFF00, 0xFFFFFFC0, 0xFFFFFFF0, 0xFFFFFFFC };
560
561 unsigned int wordToCount, charToCount;
562 unsigned int i, c;
563 unsigned int sum = 0;
564
565 wordToCount = index / 16;
566 charToCount = index - wordToCount * 16;
567
568 for (i=0; i<wordToCount; i++) {
569 sum += dnaDecodeTable[dna[i] >> 16];
570 sum += dnaDecodeTable[dna[i] & 0x0000FFFF];
571 }
572
573 if (charToCount > 0) {
574 c = dna[i] & truncateRightMask[charToCount]; // increase count of 'a' by 16 - c;
575 sum += dnaDecodeTable[c >> 16];
576 sum += dnaDecodeTable[c & 0xFFFF];
577 sum += charToCount - 16; // decrease count of 'a' by 16 - positionToProcess
578 }
579
580 return (sum >> (character * 8)) & 0x000000FF;
581
582 }
583
584 static unsigned int BackwardDNAOccCount(const unsigned int* dna, const unsigned int index, const unsigned int character,
585 const unsigned int* dnaDecodeTable)
586 {
587 static const unsigned int truncateLeftMask[16] = { 0x00000000, 0x00000003, 0x0000000F, 0x0000003F,
588 0x000000FF, 0x000003FF, 0x00000FFF, 0x00003FFF,
589 0x0000FFFF, 0x0003FFFF, 0x000FFFFF, 0x003FFFFF,
590 0x00FFFFFF, 0x03FFFFFF, 0x0FFFFFFF, 0x3FFFFFFF };
591
592 unsigned int wordToCount, charToCount;
593 unsigned int i, c;
594 unsigned int sum = 0;
595
596 wordToCount = index / 16;
597 charToCount = index - wordToCount * 16;
598
599 dna -= wordToCount + 1;
600
601 if (charToCount > 0) {
602 c = *dna & truncateLeftMask[charToCount]; // increase count of 'a' by 16 - c;
603 sum += dnaDecodeTable[c >> 16];
604 sum += dnaDecodeTable[c & 0xFFFF];
605 sum += charToCount - 16; // decrease count of 'a' by 16 - positionToProcess
606 }
607
608 for (i=0; i<wordToCount; i++) {
609 dna++;
610 sum += dnaDecodeTable[*dna >> 16];
611 sum += dnaDecodeTable[*dna & 0x0000FFFF];
612 }
613
614 return (sum >> (character * 8)) & 0x000000FF;
615
616 }
617
618 bgint_t BWTOccValue(const BWT *bwt, bgint_t index, const unsigned int character)
619 {
620 bgint_t occValue;
621 bgint_t occExplicitIndex, occIndex;
622
623 // $ is supposed to be positioned at inverseSa0 but it is not encoded
624 // therefore index is subtracted by 1 for adjustment
625 if (index > bwt->inverseSa0)
626 index--;
627
628 occExplicitIndex = (index + OCC_INTERVAL / 2 - 1) / OCC_INTERVAL; // Bidirectional encoding
629 occIndex = occExplicitIndex * OCC_INTERVAL;
630 occValue = BWTOccValueExplicit(bwt, occExplicitIndex, character);
631
632 if (occIndex == index)
633 return occValue;
634
635 if (occIndex < index) {
636 return occValue + ForwardDNAOccCount(bwt->bwtCode + occIndex / CHAR_PER_WORD, index - occIndex, character, bwt->decodeTable);
637 } else {
638 return occValue - BackwardDNAOccCount(bwt->bwtCode + occIndex / CHAR_PER_WORD, occIndex - index, character, bwt->decodeTable);
639 }
640 }
641
642 static bgint_t BWTIncGetAbsoluteRank(BWT *bwt, bgint_t* __restrict absoluteRank, bgint_t* __restrict seq,
643 const unsigned int *packedText, const bgint_t numChar,
644 const bgint_t* cumulativeCount, const unsigned int firstCharInLastIteration)
645 {
646 bgint_t saIndex;
647 bgint_t lastWord;
648 unsigned int packedMask;
649 bgint_t i;
650 unsigned int c, t, j;
651 bgint_t rankIndex;
652 unsigned int shift;
653 bgint_t seqIndexFromStart[ALPHABET_SIZE];
654 bgint_t seqIndexFromEnd[ALPHABET_SIZE];
655
656 for (i=0; i<ALPHABET_SIZE; i++) {
657 seqIndexFromStart[i] = cumulativeCount[i];
658 seqIndexFromEnd[i] = cumulativeCount[i+1] - 1;
659 }
660
661 shift = BITS_IN_WORD - BIT_PER_CHAR;
662 packedMask = ALL_ONE_MASK >> shift;
663 saIndex = bwt->inverseSa0;
664 rankIndex = numChar - 1;
665
666 lastWord = numChar / CHAR_PER_WORD;
667 for (i=lastWord; i--;) { // loop from lastWord - 1 to 0
668 t = packedText[i];
669 for (j=0; j<CHAR_PER_WORD; j++) {
670 c = t & packedMask;
671 saIndex = bwt->cumulativeFreq[c] + BWTOccValue(bwt, saIndex, c) + 1;
672 // A counting sort using the first character of suffix is done here
673 // If rank > inverseSa0 -> fill seq from end, otherwise fill seq from start -> to leave the right entry for inverseSa0
674 if (saIndex > bwt->inverseSa0) {
675 seq[seqIndexFromEnd[c]] = rankIndex;
676 absoluteRank[seqIndexFromEnd[c]] = saIndex;
677 seqIndexFromEnd[c]--;
678 } else {
679 seq[seqIndexFromStart[c]] = rankIndex;
680 absoluteRank[seqIndexFromStart[c]] = saIndex;
681 seqIndexFromStart[c]++;
682 }
683 rankIndex--;
684 t >>= BIT_PER_CHAR;
685 }
686 }
687
688 absoluteRank[seqIndexFromStart[firstCharInLastIteration]] = bwt->inverseSa0; // representing the substring of all preceding characters
689 seq[seqIndexFromStart[firstCharInLastIteration]] = numChar;
690
691 return seqIndexFromStart[firstCharInLastIteration];
692 }
693
694 static void BWTIncSortKey(bgint_t* __restrict key, bgint_t* __restrict seq, const bgint_t numItem)
695 {
696 #define EQUAL_KEY_THRESHOLD 4 // Partition for equal key if data array size / the number of data with equal value with pivot < EQUAL_KEY_THRESHOLD
697
698 int64_t lowIndex, highIndex, midIndex;
699 int64_t lowPartitionIndex, highPartitionIndex;
700 int64_t lowStack[32], highStack[32];
701 int stackDepth;
702 int64_t i, j;
703 bgint_t tempSeq, tempKey;
704 int64_t numberOfEqualKey;
705
706 if (numItem < 2) return;
707
708 stackDepth = 0;
709
710 lowIndex = 0;
711 highIndex = numItem - 1;
712
713 for (;;) {
714
715 for (;;) {
716
717 // Sort small array of data
718 if (highIndex - lowIndex < BWTINC_INSERT_SORT_NUM_ITEM) { // Insertion sort on smallest arrays
719 for (i=lowIndex+1; i<=highIndex; i++) {
720 tempSeq = seq[i];
721 tempKey = key[i];
722 for (j = i; j > lowIndex && key[j-1] > tempKey; j--) {
723 seq[j] = seq[j-1];
724 key[j] = key[j-1];
725 }
726 if (j != i) {
727 seq[j] = tempSeq;
728 key[j] = tempKey;
729 }
730 }
731 break;
732 }
733
734 // Choose pivot as median of the lowest, middle, and highest data; sort the three data
735
736 midIndex = average(lowIndex, highIndex);
737 if (key[lowIndex] > key[midIndex]) {
738 tempSeq = seq[lowIndex];
739 tempKey = key[lowIndex];
740 seq[lowIndex] = seq[midIndex];
741 key[lowIndex] = key[midIndex];
742 seq[midIndex] = tempSeq;
743 key[midIndex] = tempKey;
744 }
745 if (key[lowIndex] > key[highIndex]) {
746 tempSeq = seq[lowIndex];
747 tempKey = key[lowIndex];
748 seq[lowIndex] = seq[highIndex];
749 key[lowIndex] = key[highIndex];
750 seq[highIndex] = tempSeq;
751 key[highIndex] = tempKey;
752 }
753 if (key[midIndex] > key[highIndex]) {
754 tempSeq = seq[midIndex];
755 tempKey = key[midIndex];
756 seq[midIndex] = seq[highIndex];
757 key[midIndex] = key[highIndex];
758 seq[highIndex] = tempSeq;
759 key[highIndex] = tempKey;
760 }
761
762 // Partition data
763
764 numberOfEqualKey = 0;
765
766 lowPartitionIndex = lowIndex + 1;
767 highPartitionIndex = highIndex - 1;
768
769 for (;;) {
770 while (lowPartitionIndex <= highPartitionIndex && key[lowPartitionIndex] <= key[midIndex]) {
771 numberOfEqualKey += (key[lowPartitionIndex] == key[midIndex]);
772 lowPartitionIndex++;
773 }
774 while (lowPartitionIndex < highPartitionIndex) {
775 if (key[midIndex] >= key[highPartitionIndex]) {
776 numberOfEqualKey += (key[midIndex] == key[highPartitionIndex]);
777 break;
778 }
779 highPartitionIndex--;
780 }
781 if (lowPartitionIndex >= highPartitionIndex) {
782 break;
783 }
784 tempSeq = seq[lowPartitionIndex];
785 tempKey = key[lowPartitionIndex];
786 seq[lowPartitionIndex] = seq[highPartitionIndex];
787 key[lowPartitionIndex] = key[highPartitionIndex];
788 seq[highPartitionIndex] = tempSeq;
789 key[highPartitionIndex] = tempKey;
790 if (highPartitionIndex == midIndex) {
791 // partition key has been moved
792 midIndex = lowPartitionIndex;
793 }
794 lowPartitionIndex++;
795 highPartitionIndex--;
796 }
797
798 // Adjust the partition index
799 highPartitionIndex = lowPartitionIndex;
800 lowPartitionIndex--;
801
802 // move the partition key to end of low partition
803 tempSeq = seq[midIndex];
804 tempKey = key[midIndex];
805 seq[midIndex] = seq[lowPartitionIndex];
806 key[midIndex] = key[lowPartitionIndex];
807 seq[lowPartitionIndex] = tempSeq;
808 key[lowPartitionIndex] = tempKey;
809
810 if (highIndex - lowIndex + BWTINC_INSERT_SORT_NUM_ITEM <= EQUAL_KEY_THRESHOLD * numberOfEqualKey) {
811
812 // Many keys = partition key; separate the equal key data from the lower partition
813
814 midIndex = lowIndex;
815
816 for (;;) {
817 while (midIndex < lowPartitionIndex && key[midIndex] < key[lowPartitionIndex]) {
818 midIndex++;
819 }
820 while (midIndex < lowPartitionIndex && key[lowPartitionIndex] == key[lowPartitionIndex - 1]) {
821 lowPartitionIndex--;
822 }
823 if (midIndex >= lowPartitionIndex) {
824 break;
825 }
826 tempSeq = seq[midIndex];
827 tempKey = key[midIndex];
828 seq[midIndex] = seq[lowPartitionIndex - 1];
829 key[midIndex] = key[lowPartitionIndex - 1];
830 seq[lowPartitionIndex - 1] = tempSeq;
831 key[lowPartitionIndex - 1] = tempKey;
832 midIndex++;
833 lowPartitionIndex--;
834 }
835
836 }
837
838 if (lowPartitionIndex - lowIndex > highIndex - highPartitionIndex) {
839 // put the larger partition to stack
840 lowStack[stackDepth] = lowIndex;
841 highStack[stackDepth] = lowPartitionIndex - 1;
842 stackDepth++;
843 // sort the smaller partition first
844 lowIndex = highPartitionIndex;
845 } else {
846 // put the larger partition to stack
847 lowStack[stackDepth] = highPartitionIndex;
848 highStack[stackDepth] = highIndex;
849 stackDepth++;
850 // sort the smaller partition first
851 if (lowPartitionIndex > lowIndex) {
852 highIndex = lowPartitionIndex - 1;
853 } else {
854 // all keys in the partition equals to the partition key
855 break;
856 }
857 }
858 continue;
859 }
860
861 // Pop a range from stack
862 if (stackDepth > 0) {
863 stackDepth--;
864 lowIndex = lowStack[stackDepth];
865 highIndex = highStack[stackDepth];
866 continue;
867 } else return;
868 }
869 }
870
871
872 static void BWTIncBuildRelativeRank(bgint_t* __restrict sortedRank, bgint_t* __restrict seq,
873 bgint_t* __restrict relativeRank, const bgint_t numItem,
874 bgint_t oldInverseSa0, const bgint_t *cumulativeCount)
875 {
876 bgint_t i, c;
877 bgint_t s, r;
878 bgint_t lastRank, lastIndex;
879 bgint_t freq;
880
881 lastIndex = numItem;
882 lastRank = sortedRank[numItem];
883 if (lastRank > oldInverseSa0) {
884 sortedRank[numItem]--; // to prepare for merging; $ is not encoded in bwt
885 }
886 s = seq[numItem];
887 relativeRank[s] = numItem;
888 if (lastRank == oldInverseSa0) {
889 oldInverseSa0++; // so that this segment of code is not run again
890 lastRank++; // so that oldInverseSa0 become a sorted group with 1 item
891 }
892
893 c = ALPHABET_SIZE - 1;
894 freq = cumulativeCount[c];
895
896 for (i=numItem; i--;) { // from numItem - 1 to 0
897 r = sortedRank[i];
898 if (r > oldInverseSa0)
899 sortedRank[i]--; // to prepare for merging; $ is not encoded in bwt
900 s = seq[i];
901 if (i < freq) {
902 if (lastIndex >= freq)
903 lastRank++; // to trigger the group across alphabet boundary to be split
904 c--;
905 freq = cumulativeCount[c];
906 }
907 if (r == lastRank) {
908 relativeRank[s] = lastIndex;
909 } else {
910 if (i == lastIndex - 1) {
911 if (lastIndex < numItem && (sbgint_t)seq[lastIndex + 1] < 0) {
912 seq[lastIndex] = seq[lastIndex + 1] - 1;
913 } else {
914 seq[lastIndex] = (bgint_t)-1;
915 }
916 }
917 lastIndex = i;
918 lastRank = r;
919 relativeRank[s] = i;
920 if (r == oldInverseSa0) {
921 oldInverseSa0++; // so that this segment of code is not run again
922 lastRank++; // so that oldInverseSa0 become a sorted group with 1 item
923 }
924 }
925 }
926
927 }
928
929 static void BWTIncBuildBwt(unsigned int* insertBwt, const bgint_t *relativeRank, const bgint_t numChar,
930 const bgint_t *cumulativeCount)
931 {
932 unsigned int c;
933 bgint_t i;
934 bgint_t previousRank, currentRank;
935
936 previousRank = relativeRank[0];
937
938 for (i=1; i<=numChar; i++) {
939 currentRank = relativeRank[i];
940 c = (previousRank >= cumulativeCount[1]) + (previousRank >= cumulativeCount[2])
941 + (previousRank >= cumulativeCount[3]);
942 insertBwt[currentRank] = c;
943 previousRank = currentRank;
944 }
945 }
946
947 static void BWTIncMergeBwt(const bgint_t *sortedRank, const unsigned int* oldBwt, const unsigned int *insertBwt,
948 unsigned int* __restrict mergedBwt, const bgint_t numOldBwt, const bgint_t numInsertBwt)
949 {
950 bgint_t leftShift, rightShift;
951 bgint_t o;
952 bgint_t oIndex, iIndex, mIndex;
953 bgint_t mWord, mChar, oWord, oChar;
954 bgint_t numInsert;
955
956 oIndex = 0;
957 iIndex = 0;
958 mIndex = 0;
959
960 mWord = 0;
961 mChar = 0;
962
963 mergedBwt[0] = 0; // this can be cleared as merged Bwt slightly shift to the left in each iteration
964
965 while (oIndex < numOldBwt) {
966
967 // copy from insertBwt
968 while (iIndex <= numInsertBwt && sortedRank[iIndex] <= oIndex) {
969 if (sortedRank[iIndex] != 0) { // special value to indicate that this is for new inverseSa0
970 mergedBwt[mWord] |= insertBwt[iIndex] << (BITS_IN_WORD - (mChar + 1) * BIT_PER_CHAR);
971 mIndex++;
972 mChar++;
973 if (mChar == CHAR_PER_WORD) {
974 mChar = 0;
975 mWord++;
976 mergedBwt[mWord] = 0; // no need to worry about crossing mergedBwt boundary
977 }
978 }
979 iIndex++;
980 }
981
982 // Copy from oldBwt to mergedBwt
983 if (iIndex <= numInsertBwt) {
984 o = sortedRank[iIndex];
985 } else {
986 o = numOldBwt;
987 }
988 numInsert = o - oIndex;
989
990 oWord = oIndex / CHAR_PER_WORD;
991 oChar = oIndex - oWord * CHAR_PER_WORD;
992 if (oChar > mChar) {
993 leftShift = (oChar - mChar) * BIT_PER_CHAR;
994 rightShift = (CHAR_PER_WORD + mChar - oChar) * BIT_PER_CHAR;
995 mergedBwt[mWord] = mergedBwt[mWord]
996 | (oldBwt[oWord] << (oChar * BIT_PER_CHAR) >> (mChar * BIT_PER_CHAR))
997 | (oldBwt[oWord+1] >> rightShift);
998 oIndex += min(numInsert, CHAR_PER_WORD - mChar);
999 while (o > oIndex) {
1000 oWord++;
1001 mWord++;
1002 mergedBwt[mWord] = (oldBwt[oWord] << leftShift) | (oldBwt[oWord+1] >> rightShift);
1003 oIndex += CHAR_PER_WORD;
1004 }
1005 } else if (oChar < mChar) {
1006 rightShift = (mChar - oChar) * BIT_PER_CHAR;
1007 leftShift = (CHAR_PER_WORD + oChar - mChar) * BIT_PER_CHAR;
1008 mergedBwt[mWord] = mergedBwt[mWord]
1009 | (oldBwt[oWord] << (oChar * BIT_PER_CHAR) >> (mChar * BIT_PER_CHAR));
1010 oIndex += min(numInsert, CHAR_PER_WORD - mChar);
1011 while (o > oIndex) {
1012 oWord++;
1013 mWord++;
1014 mergedBwt[mWord] = (oldBwt[oWord-1] << leftShift) | (oldBwt[oWord] >> rightShift);
1015 oIndex += CHAR_PER_WORD;
1016 }
1017 } else { // oChar == mChar
1018 mergedBwt[mWord] = mergedBwt[mWord] | truncateLeft(oldBwt[oWord], mChar * BIT_PER_CHAR);
1019 oIndex += min(numInsert, CHAR_PER_WORD - mChar);
1020 while (o > oIndex) {
1021 oWord++;
1022 mWord++;
1023 mergedBwt[mWord] = oldBwt[oWord];
1024 oIndex += CHAR_PER_WORD;
1025 }
1026 }
1027 oIndex = o;
1028 mIndex += numInsert;
1029
1030 // Clear the trailing garbage in mergedBwt
1031 mWord = mIndex / CHAR_PER_WORD;
1032 mChar = mIndex - mWord * CHAR_PER_WORD;
1033 if (mChar == 0) {
1034 mergedBwt[mWord] = 0;
1035 } else {
1036 mergedBwt[mWord] = truncateRight(mergedBwt[mWord], (BITS_IN_WORD - mChar * BIT_PER_CHAR));
1037 }
1038
1039 }
1040
1041 // copy from insertBwt
1042 while (iIndex <= numInsertBwt) {
1043 if (sortedRank[iIndex] != 0) {
1044 mergedBwt[mWord] |= insertBwt[iIndex] << (BITS_IN_WORD - (mChar + 1) * BIT_PER_CHAR);
1045 mIndex++;
1046 mChar++;
1047 if (mChar == CHAR_PER_WORD) {
1048 mChar = 0;
1049 mWord++;
1050 mergedBwt[mWord] = 0; // no need to worry about crossing mergedBwt boundary
1051 }
1052 }
1053 iIndex++;
1054 }
1055 }
1056
1057 void BWTClearTrailingBwtCode(BWT *bwt)
1058 {
1059 bgint_t bwtResidentSizeInWord;
1060 bgint_t wordIndex, offset;
1061 bgint_t i;
1062
1063 bwtResidentSizeInWord = BWTResidentSizeInWord(bwt->textLength);
1064
1065 wordIndex = bwt->textLength / CHAR_PER_WORD;
1066 offset = (bwt->textLength - wordIndex * CHAR_PER_WORD) * BIT_PER_CHAR;
1067 if (offset > 0) {
1068 bwt->bwtCode[wordIndex] = truncateRight(bwt->bwtCode[wordIndex], BITS_IN_WORD - offset);
1069 } else {
1070 if (wordIndex < bwtResidentSizeInWord) {
1071 bwt->bwtCode[wordIndex] = 0;
1072 }
1073 }
1074
1075 for (i=wordIndex+1; i<bwtResidentSizeInWord; i++) {
1076 bwt->bwtCode[i] = 0;
1077 }
1078 }
1079
1080
1081 void BWTGenerateOccValueFromBwt(const unsigned int* bwt, unsigned int* __restrict occValue,
1082 bgint_t* __restrict occValueMajor,
1083 const bgint_t textLength, const unsigned int* decodeTable)
1084 {
1085 bgint_t numberOfOccValueMajor, numberOfOccValue;
1086 unsigned int wordBetweenOccValue;
1087 bgint_t numberOfOccIntervalPerMajor;
1088 unsigned int c;
1089 bgint_t i, j;
1090 bgint_t occMajorIndex;
1091 bgint_t occIndex, bwtIndex;
1092 bgint_t sum; // perhaps unsigned is big enough
1093 bgint_t tempOccValue0[ALPHABET_SIZE], tempOccValue1[ALPHABET_SIZE];
1094
1095 wordBetweenOccValue = OCC_INTERVAL / CHAR_PER_WORD;
1096
1097 // Calculate occValue
1098 numberOfOccValue = (textLength + OCC_INTERVAL - 1) / OCC_INTERVAL + 1; // Value at both end for bi-directional encoding
1099 numberOfOccIntervalPerMajor = OCC_INTERVAL_MAJOR / OCC_INTERVAL;
1100 numberOfOccValueMajor = (numberOfOccValue + numberOfOccIntervalPerMajor - 1) / numberOfOccIntervalPerMajor;
1101
1102 tempOccValue0[0] = 0;
1103 tempOccValue0[1] = 0;
1104 tempOccValue0[2] = 0;
1105 tempOccValue0[3] = 0;
1106 occValueMajor[0] = 0;
1107 occValueMajor[1] = 0;
1108 occValueMajor[2] = 0;
1109 occValueMajor[3] = 0;
1110
1111 occIndex = 0;
1112 bwtIndex = 0;
1113 for (occMajorIndex=1; occMajorIndex<numberOfOccValueMajor; occMajorIndex++) {
1114
1115 for (i=0; i<numberOfOccIntervalPerMajor/2; i++) {
1116
1117 sum = 0;
1118 tempOccValue1[0] = tempOccValue0[0];
1119 tempOccValue1[1] = tempOccValue0[1];
1120 tempOccValue1[2] = tempOccValue0[2];
1121 tempOccValue1[3] = tempOccValue0[3];
1122
1123 for (j=0; j<wordBetweenOccValue; j++) {
1124 c = bwt[bwtIndex];
1125 sum += decodeTable[c >> 16];
1126 sum += decodeTable[c & 0x0000FFFF];
1127 bwtIndex++;
1128 }
1129 if (!DNA_OCC_SUM_EXCEPTION(sum)) {
1130 tempOccValue1[0] += (sum & 0x000000FF); sum >>= 8;
1131 tempOccValue1[1] += (sum & 0x000000FF); sum >>= 8;
1132 tempOccValue1[2] += (sum & 0x000000FF); sum >>= 8;
1133 tempOccValue1[3] += sum;
1134 } else {
1135 if (sum == 0x00000100) {
1136 tempOccValue1[0] += 256;
1137 } else if (sum == 0x00010000) {
1138 tempOccValue1[1] += 256;
1139 } else if (sum == 0x01000000) {
1140 tempOccValue1[2] += 256;
1141 } else {
1142 tempOccValue1[3] += 256;
1143 }
1144 }
1145 occValue[occIndex * 4 + 0] = (tempOccValue0[0] << 16) | tempOccValue1[0];
1146 occValue[occIndex * 4 + 1] = (tempOccValue0[1] << 16) | tempOccValue1[1];
1147 occValue[occIndex * 4 + 2] = (tempOccValue0[2] << 16) | tempOccValue1[2];
1148 occValue[occIndex * 4 + 3] = (tempOccValue0[3] << 16) | tempOccValue1[3];
1149 tempOccValue0[0] = tempOccValue1[0];
1150 tempOccValue0[1] = tempOccValue1[1];
1151 tempOccValue0[2] = tempOccValue1[2];
1152 tempOccValue0[3] = tempOccValue1[3];
1153 sum = 0;
1154
1155 occIndex++;
1156
1157 for (j=0; j<wordBetweenOccValue; j++) {
1158 c = bwt[bwtIndex];
1159 sum += decodeTable[c >> 16];
1160 sum += decodeTable[c & 0x0000FFFF];
1161 bwtIndex++;
1162 }
1163 if (!DNA_OCC_SUM_EXCEPTION(sum)) {
1164 tempOccValue0[0] += (sum & 0x000000FF); sum >>= 8;
1165 tempOccValue0[1] += (sum & 0x000000FF); sum >>= 8;
1166 tempOccValue0[2] += (sum & 0x000000FF); sum >>= 8;
1167 tempOccValue0[3] += sum;
1168 } else {
1169 if (sum == 0x00000100) {
1170 tempOccValue0[0] += 256;
1171 } else if (sum == 0x00010000) {
1172 tempOccValue0[1] += 256;
1173 } else if (sum == 0x01000000) {
1174 tempOccValue0[2] += 256;
1175 } else {
1176 tempOccValue0[3] += 256;
1177 }
1178 }
1179 }
1180
1181 occValueMajor[occMajorIndex * 4 + 0] = occValueMajor[(occMajorIndex - 1) * 4 + 0] + tempOccValue0[0];
1182 occValueMajor[occMajorIndex * 4 + 1] = occValueMajor[(occMajorIndex - 1) * 4 + 1] + tempOccValue0[1];
1183 occValueMajor[occMajorIndex * 4 + 2] = occValueMajor[(occMajorIndex - 1) * 4 + 2] + tempOccValue0[2];
1184 occValueMajor[occMajorIndex * 4 + 3] = occValueMajor[(occMajorIndex - 1) * 4 + 3] + tempOccValue0[3];
1185 tempOccValue0[0] = 0;
1186 tempOccValue0[1] = 0;
1187 tempOccValue0[2] = 0;
1188 tempOccValue0[3] = 0;
1189
1190 }
1191
1192 while (occIndex < (numberOfOccValue-1)/2) {
1193 sum = 0;
1194 tempOccValue1[0] = tempOccValue0[0];
1195 tempOccValue1[1] = tempOccValue0[1];
1196 tempOccValue1[2] = tempOccValue0[2];
1197 tempOccValue1[3] = tempOccValue0[3];
1198 for (j=0; j<wordBetweenOccValue; j++) {
1199 c = bwt[bwtIndex];
1200 sum += decodeTable[c >> 16];
1201 sum += decodeTable[c & 0x0000FFFF];
1202 bwtIndex++;
1203 }
1204 if (!DNA_OCC_SUM_EXCEPTION(sum)) {
1205 tempOccValue1[0] += (sum & 0x000000FF); sum >>= 8;
1206 tempOccValue1[1] += (sum & 0x000000FF); sum >>= 8;
1207 tempOccValue1[2] += (sum & 0x000000FF); sum >>= 8;
1208 tempOccValue1[3] += sum;
1209 } else {
1210 if (sum == 0x00000100) {
1211 tempOccValue1[0] += 256;
1212 } else if (sum == 0x00010000) {
1213 tempOccValue1[1] += 256;
1214 } else if (sum == 0x01000000) {
1215 tempOccValue1[2] += 256;
1216 } else {
1217 tempOccValue1[3] += 256;
1218 }
1219 }
1220 occValue[occIndex * 4 + 0] = (tempOccValue0[0] << 16) | tempOccValue1[0];
1221 occValue[occIndex * 4 + 1] = (tempOccValue0[1] << 16) | tempOccValue1[1];
1222 occValue[occIndex * 4 + 2] = (tempOccValue0[2] << 16) | tempOccValue1[2];
1223 occValue[occIndex * 4 + 3] = (tempOccValue0[3] << 16) | tempOccValue1[3];
1224 tempOccValue0[0] = tempOccValue1[0];
1225 tempOccValue0[1] = tempOccValue1[1];
1226 tempOccValue0[2] = tempOccValue1[2];
1227 tempOccValue0[3] = tempOccValue1[3];
1228 sum = 0;
1229 occIndex++;
1230
1231 for (j=0; j<wordBetweenOccValue; j++) {
1232 c = bwt[bwtIndex];
1233 sum += decodeTable[c >> 16];
1234 sum += decodeTable[c & 0x0000FFFF];
1235 bwtIndex++;
1236 }
1237 if (!DNA_OCC_SUM_EXCEPTION(sum)) {
1238 tempOccValue0[0] += (sum & 0x000000FF); sum >>= 8;
1239 tempOccValue0[1] += (sum & 0x000000FF); sum >>= 8;
1240 tempOccValue0[2] += (sum & 0x000000FF); sum >>= 8;
1241 tempOccValue0[3] += sum;
1242 } else {
1243 if (sum == 0x00000100) {
1244 tempOccValue0[0] += 256;
1245 } else if (sum == 0x00010000) {
1246 tempOccValue0[1] += 256;
1247 } else if (sum == 0x01000000) {
1248 tempOccValue0[2] += 256;
1249 } else {
1250 tempOccValue0[3] += 256;
1251 }
1252 }
1253 }
1254
1255 sum = 0;
1256 tempOccValue1[0] = tempOccValue0[0];
1257 tempOccValue1[1] = tempOccValue0[1];
1258 tempOccValue1[2] = tempOccValue0[2];
1259 tempOccValue1[3] = tempOccValue0[3];
1260
1261 if (occIndex * 2 < numberOfOccValue - 1) {
1262 for (j=0; j<wordBetweenOccValue; j++) {
1263 c = bwt[bwtIndex];
1264 sum += decodeTable[c >> 16];
1265 sum += decodeTable[c & 0x0000FFFF];
1266 bwtIndex++;
1267 }
1268 if (!DNA_OCC_SUM_EXCEPTION(sum)) {
1269 tempOccValue1[0] += (sum & 0x000000FF); sum >>= 8;
1270 tempOccValue1[1] += (sum & 0x000000FF); sum >>= 8;
1271 tempOccValue1[2] += (sum & 0x000000FF); sum >>= 8;
1272 tempOccValue1[3] += sum;
1273 } else {
1274 if (sum == 0x00000100) {
1275 tempOccValue1[0] += 256;
1276 } else if (sum == 0x00010000) {
1277 tempOccValue1[1] += 256;
1278 } else if (sum == 0x01000000) {
1279 tempOccValue1[2] += 256;
1280 } else {
1281 tempOccValue1[3] += 256;
1282 }
1283 }
1284 }
1285
1286 occValue[occIndex * 4 + 0] = (tempOccValue0[0] << 16) | tempOccValue1[0];
1287 occValue[occIndex * 4 + 1] = (tempOccValue0[1] << 16) | tempOccValue1[1];
1288 occValue[occIndex * 4 + 2] = (tempOccValue0[2] << 16) | tempOccValue1[2];
1289 occValue[occIndex * 4 + 3] = (tempOccValue0[3] << 16) | tempOccValue1[3];
1290
1291 }
1292
1293 static void BWTIncConstruct(BWTInc *bwtInc, const bgint_t numChar)
1294 {
1295 unsigned int i;
1296 bgint_t mergedBwtSizeInWord, mergedOccSizeInWord;
1297 unsigned int firstCharInThisIteration;
1298
1299 bgint_t *relativeRank, *seq, *sortedRank;
1300 unsigned int *insertBwt, *mergedBwt;
1301 bgint_t newInverseSa0RelativeRank, oldInverseSa0RelativeRank, newInverseSa0;
1302
1303 mergedBwtSizeInWord = BWTResidentSizeInWord(bwtInc->bwt->textLength + numChar);
1304 mergedOccSizeInWord = BWTOccValueMinorSizeInWord(bwtInc->bwt->textLength + numChar);
1305
1306 initializeVAL_bg(bwtInc->cumulativeCountInCurrentBuild, ALPHABET_SIZE + 1, 0);
1307
1308 if (bwtInc->bwt->textLength == 0) { // Initial build
1309
1310 // Set address
1311 seq = (bgint_t*)bwtInc->workingMemory;
1312 relativeRank = seq + bwtInc->buildSize + 1;
1313 // mergedBwt and packedTex may share memory
1314 mergedBwt = insertBwt = bwtInc->workingMemory + bwtInc->availableWord - mergedBwtSizeInWord; // build in place
1315
1316 assert((void*)(relativeRank + bwtInc->buildSize + 1) <= (void*)bwtInc->packedText);
1317 assert((void*)(relativeRank + bwtInc->buildSize + 1) <= (void*)mergedBwt);
1318
1319 // ->packedText is not used any more and may be overwritten by mergedBwt
1320 BWTIncPutPackedTextToRank(bwtInc->packedText, relativeRank, bwtInc->cumulativeCountInCurrentBuild, numChar);
1321
1322 firstCharInThisIteration = relativeRank[0];
1323 relativeRank[numChar] = 0;
1324
1325 // Sort suffix
1326 QSufSortSuffixSort((qsint_t*)relativeRank, (qsint_t*)seq, (qsint_t)numChar, (qsint_t)ALPHABET_SIZE - 1, 0, FALSE);
1327 newInverseSa0 = relativeRank[0];
1328
1329 // Clear BWT area
1330 initializeVAL(insertBwt, mergedBwtSizeInWord, 0);
1331
1332 // Build BWT
1333 BWTIncBuildPackedBwt(relativeRank, insertBwt, numChar, bwtInc->cumulativeCountInCurrentBuild, bwtInc->packedShift);
1334
1335 // so that the cumulativeCount is not deducted
1336 bwtInc->firstCharInLastIteration = ALPHABET_SIZE;
1337
1338 } else { // Incremental build
1339 // Set address
1340 sortedRank = (bgint_t*)bwtInc->workingMemory;
1341 seq = sortedRank + bwtInc->buildSize + 1;
1342 insertBwt = (unsigned*)seq; // insertBwt and seq share memory
1343 // relativeRank and ->packedText may share memory
1344 relativeRank = seq + bwtInc->buildSize + 1;
1345
1346 assert((void*)relativeRank <= (void*)bwtInc->packedText);
1347
1348 // Store the first character of this iteration
1349 firstCharInThisIteration = bwtInc->packedText[0] >> (BITS_IN_WORD - BIT_PER_CHAR);
1350
1351 // Count occurrence of input text
1352 ForwardDNAAllOccCountNoLimit(bwtInc->packedText, numChar, bwtInc->cumulativeCountInCurrentBuild + 1, bwtInc->bwt->decodeTable);
1353 // Add the first character of the previous iteration to represent the inverseSa0 of the previous iteration
1354 bwtInc->cumulativeCountInCurrentBuild[bwtInc->firstCharInLastIteration + 1]++;
1355 bwtInc->cumulativeCountInCurrentBuild[2] += bwtInc->cumulativeCountInCurrentBuild[1];
1356 bwtInc->cumulativeCountInCurrentBuild[3] += bwtInc->cumulativeCountInCurrentBuild[2];
1357 bwtInc->cumulativeCountInCurrentBuild[4] += bwtInc->cumulativeCountInCurrentBuild[3];
1358
1359 // Get rank of new suffix among processed suffix
1360 // The seq array is built into ALPHABET_SIZE + 2 groups; ALPHABET_SIZE groups + 1 group divided into 2 by inverseSa0 + inverseSa0 as 1 group
1361 // ->packedText is not used any more and will be overwritten by relativeRank
1362 oldInverseSa0RelativeRank = BWTIncGetAbsoluteRank(bwtInc->bwt, sortedRank, seq, bwtInc->packedText,
1363 numChar, bwtInc->cumulativeCountInCurrentBuild, bwtInc->firstCharInLastIteration);
1364
1365 // Sort rank by ALPHABET_SIZE + 2 groups (or ALPHABET_SIZE + 1 groups when inverseSa0 sit on the border of a group)
1366 for (i=0; i<ALPHABET_SIZE; i++) {
1367 if (bwtInc->cumulativeCountInCurrentBuild[i] > oldInverseSa0RelativeRank ||
1368 bwtInc->cumulativeCountInCurrentBuild[i+1] <= oldInverseSa0RelativeRank) {
1369 BWTIncSortKey(sortedRank + bwtInc->cumulativeCountInCurrentBuild[i], seq + bwtInc->cumulativeCountInCurrentBuild[i], bwtInc->cumulativeCountInCurrentBuild[i+1] - bwtInc->cumulativeCountInCurrentBuild[i]);
1370 } else {
1371 if (bwtInc->cumulativeCountInCurrentBuild[i] < oldInverseSa0RelativeRank) {
1372 BWTIncSortKey(sortedRank + bwtInc->cumulativeCountInCurrentBuild[i], seq + bwtInc->cumulativeCountInCurrentBuild[i], oldInverseSa0RelativeRank - bwtInc->cumulativeCountInCurrentBuild[i]);
1373 }
1374 if (bwtInc->cumulativeCountInCurrentBuild[i+1] > oldInverseSa0RelativeRank + 1) {
1375 BWTIncSortKey(sortedRank + oldInverseSa0RelativeRank + 1, seq + oldInverseSa0RelativeRank + 1, bwtInc->cumulativeCountInCurrentBuild[i+1] - oldInverseSa0RelativeRank - 1);
1376 }
1377 }
1378 }
1379
1380 // build relative rank; sortedRank is updated for merging to cater for the fact that $ is not encoded in bwt
1381 // the cumulative freq information is used to make sure that inverseSa0 and suffix beginning with different characters are kept in different unsorted groups)
1382 BWTIncBuildRelativeRank(sortedRank, seq, relativeRank, numChar, bwtInc->bwt->inverseSa0, bwtInc->cumulativeCountInCurrentBuild);
1383 assert(relativeRank[numChar] == oldInverseSa0RelativeRank);
1384
1385 // Sort suffix
1386 QSufSortSuffixSort((qsint_t*)relativeRank, (qsint_t*)seq, (qsint_t)numChar, (qsint_t)numChar, 1, TRUE);
1387
1388 newInverseSa0RelativeRank = relativeRank[0];
1389 newInverseSa0 = sortedRank[newInverseSa0RelativeRank] + newInverseSa0RelativeRank;
1390
1391 sortedRank[newInverseSa0RelativeRank] = 0; // a special value so that this is skipped in the merged bwt
1392
1393 // Build BWT; seq is overwritten by insertBwt
1394 BWTIncBuildBwt(insertBwt, relativeRank, numChar, bwtInc->cumulativeCountInCurrentBuild);
1395
1396 // Merge BWT; relativeRank may be overwritten by mergedBwt
1397 mergedBwt = bwtInc->workingMemory + bwtInc->availableWord - mergedBwtSizeInWord
1398 - bwtInc->numberOfIterationDone * OCC_INTERVAL / BIT_PER_CHAR * (sizeof(bgint_t) / 4); // minus numberOfIteration * occInterval to create a buffer for merging
1399 assert(mergedBwt >= insertBwt + numChar);
1400 BWTIncMergeBwt(sortedRank, bwtInc->bwt->bwtCode, insertBwt, mergedBwt, bwtInc->bwt->textLength, numChar);
1401 }
1402
1403 // Build auxiliary structure and update info and pointers in BWT
1404 bwtInc->bwt->textLength += numChar;
1405 bwtInc->bwt->bwtCode = mergedBwt;
1406 bwtInc->bwt->bwtSizeInWord = mergedBwtSizeInWord;
1407 bwtInc->bwt->occSizeInWord = mergedOccSizeInWord;
1408 assert(mergedBwt >= bwtInc->workingMemory + mergedOccSizeInWord);
1409
1410 bwtInc->bwt->occValue = mergedBwt - mergedOccSizeInWord;
1411
1412 BWTClearTrailingBwtCode(bwtInc->bwt);
1413 BWTGenerateOccValueFromBwt(bwtInc->bwt->bwtCode, bwtInc->bwt->occValue, bwtInc->bwt->occValueMajor,
1414 bwtInc->bwt->textLength, bwtInc->bwt->decodeTable);
1415
1416 bwtInc->bwt->inverseSa0 = newInverseSa0;
1417
1418 bwtInc->bwt->cumulativeFreq[1] += bwtInc->cumulativeCountInCurrentBuild[1] - (bwtInc->firstCharInLastIteration <= 0);
1419 bwtInc->bwt->cumulativeFreq[2] += bwtInc->cumulativeCountInCurrentBuild[2] - (bwtInc->firstCharInLastIteration <= 1);
1420 bwtInc->bwt->cumulativeFreq[3] += bwtInc->cumulativeCountInCurrentBuild[3] - (bwtInc->firstCharInLastIteration <= 2);
1421 bwtInc->bwt->cumulativeFreq[4] += bwtInc->cumulativeCountInCurrentBuild[4] - (bwtInc->firstCharInLastIteration <= 3);
1422
1423 bwtInc->firstCharInLastIteration = firstCharInThisIteration;
1424
1425 // Set build size and text address for the next build
1426 BWTIncSetBuildSizeAndTextAddr(bwtInc);
1427 bwtInc->numberOfIterationDone++;
1428
1429 }
1430
1431 BWTInc *BWTIncConstructFromPacked(const char *inputFileName, bgint_t initialMaxBuildSize, bgint_t incMaxBuildSize)
1432 {
1433
1434 FILE *packedFile;
1435 bgint_t packedFileLen;
1436 bgint_t totalTextLength;
1437 bgint_t textToLoad, textSizeInByte;
1438 bgint_t processedTextLength;
1439 unsigned char lastByteLength;
1440
1441 BWTInc *bwtInc;
1442
1443 packedFile = (FILE*)fopen(inputFileName, "rb");
1444
1445 if (packedFile == NULL) {
1446 fprintf(stderr, "BWTIncConstructFromPacked() : Cannot open %s : %s\n",
1447 inputFileName, strerror(errno));
1448 exit(1);
1449 }
1450
1451 if (fseek(packedFile, -1, SEEK_END) != 0) {
1452 fprintf(stderr, "BWTIncConstructFromPacked() : Can't seek on %s : %s\n",
1453 inputFileName, strerror(errno));
1454 exit(1);
1455 }
1456 packedFileLen = ftell(packedFile);
1457 if (packedFileLen == -1) {
1458 fprintf(stderr, "BWTIncConstructFromPacked() : Can't ftell on %s : %s\n",
1459 inputFileName, strerror(errno));
1460 exit(1);
1461 }
1462 if (fread(&lastByteLength, sizeof(unsigned char), 1, packedFile) != 1) {
1463 fprintf(stderr,
1464 "BWTIncConstructFromPacked() : Can't read from %s : %s\n",
1465 inputFileName,
1466 ferror(packedFile)? strerror(errno) : "Unexpected end of file");
1467 exit(1);
1468 }
1469 totalTextLength = TextLengthFromBytePacked(packedFileLen, BIT_PER_CHAR, lastByteLength);
1470
1471 bwtInc = BWTIncCreate(totalTextLength, initialMaxBuildSize, incMaxBuildSize);
1472
1473 BWTIncSetBuildSizeAndTextAddr(bwtInc);
1474
1475 if (bwtInc->buildSize > totalTextLength) {
1476 textToLoad = totalTextLength;
1477 } else {
1478 textToLoad = totalTextLength - ((totalTextLength - bwtInc->buildSize + CHAR_PER_WORD - 1) / CHAR_PER_WORD * CHAR_PER_WORD);
1479 }
1480 textSizeInByte = textToLoad / CHAR_PER_BYTE; // excluded the odd byte
1481
1482 if (fseek(packedFile, -((long)textSizeInByte + 2), SEEK_CUR) != 0) {
1483 fprintf(stderr, "BWTIncConstructFromPacked() : Can't seek on %s : %s\n",
1484 inputFileName, strerror(errno));
1485 exit(1);
1486 }
1487 if (fread(bwtInc->textBuffer, sizeof(unsigned char), textSizeInByte + 1, packedFile) != textSizeInByte + 1) {
1488 fprintf(stderr,
1489 "BWTIncConstructFromPacked() : Can't read from %s : %s\n",
1490 inputFileName,
1491 ferror(packedFile)? strerror(errno) : "Unexpected end of file");
1492 exit(1);
1493 }
1494 if (fseek(packedFile, -((long)textSizeInByte + 1), SEEK_CUR) != 0) {
1495 fprintf(stderr, "BWTIncConstructFromPacked() : Can't seek on %s : %s\n",
1496 inputFileName, strerror(errno));
1497 exit(1);
1498 }
1499
1500 ConvertBytePackedToWordPacked(bwtInc->textBuffer, bwtInc->packedText, ALPHABET_SIZE, textToLoad);
1501 BWTIncConstruct(bwtInc, textToLoad);
1502
1503 processedTextLength = textToLoad;
1504
1505 while (processedTextLength < totalTextLength) {
1506 textToLoad = bwtInc->buildSize / CHAR_PER_WORD * CHAR_PER_WORD;
1507 if (textToLoad > totalTextLength - processedTextLength) {
1508 textToLoad = totalTextLength - processedTextLength;
1509 }
1510 textSizeInByte = textToLoad / CHAR_PER_BYTE;
1511 if (fseek(packedFile, -((long)textSizeInByte), SEEK_CUR) != 0) {
1512 fprintf(stderr, "BWTIncConstructFromPacked() : Can't seek on %s : %s\n",
1513 inputFileName, strerror(errno));
1514 exit(1);
1515 }
1516 if (fread(bwtInc->textBuffer, sizeof(unsigned char), textSizeInByte, packedFile) != textSizeInByte) {
1517 fprintf(stderr,
1518 "BWTIncConstructFromPacked() : Can't read from %s : %s\n",
1519 inputFileName,
1520 ferror(packedFile)? strerror(errno) : "Unexpected end of file");
1521 exit(1);
1522 }
1523 if (fseek(packedFile, -((long)textSizeInByte), SEEK_CUR) != 0) {
1524 fprintf(stderr, "BWTIncConstructFromPacked() : Can't seek on %s : %s\n",
1525 inputFileName, strerror(errno));
1526 exit(1);
1527 }
1528 ConvertBytePackedToWordPacked(bwtInc->textBuffer, bwtInc->packedText, ALPHABET_SIZE, textToLoad);
1529 BWTIncConstruct(bwtInc, textToLoad);
1530 processedTextLength += textToLoad;
1531 if (bwtInc->numberOfIterationDone % 10 == 0) {
1532 fprintf(stderr, "[BWTIncConstructFromPacked] %lu iterations done. %lu characters processed.\n",
1533 (long)bwtInc->numberOfIterationDone, (long)processedTextLength);
1534 }
1535 }
1536
1537 fclose(packedFile);
1538 return bwtInc;
1539 }
1540
1541 void BWTIncFree(BWTInc *bwtInc)
1542 {
1543 if (bwtInc == 0) return;
1544 free(bwtInc->bwt->cumulativeFreq);
1545 free(bwtInc->bwt->occValueMajor);
1546 free(bwtInc->bwt->decodeTable);
1547 free(bwtInc->bwt);
1548 free(bwtInc->workingMemory);
1549 free(bwtInc->cumulativeCountInCurrentBuild);
1550 free(bwtInc->packedShift);
1551 free(bwtInc);
1552 }
1553
1554 static bgint_t BWTFileSizeInWord(const bgint_t numChar)
1555 {
1556 // The $ in BWT at the position of inverseSa0 is not encoded
1557 return (numChar + CHAR_PER_WORD - 1) / CHAR_PER_WORD;
1558 }
1559
1560 void BWTSaveBwtCodeAndOcc(const BWT *bwt, const char *bwtFileName, const char *occValueFileName)
1561 {
1562 FILE *bwtFile;
1563 /* FILE *occValueFile; */
1564 bgint_t bwtLength;
1565
1566 bwtFile = (FILE*)fopen(bwtFileName, "wb");
1567 if (bwtFile == NULL) {
1568 fprintf(stderr,
1569 "BWTSaveBwtCodeAndOcc(): Cannot open %s for writing: %s\n",
1570 bwtFileName, strerror(errno));
1571 exit(1);
1572 }
1573
1574 bwtLength = BWTFileSizeInWord(bwt->textLength);
1575
1576 if (fwrite(&bwt->inverseSa0, sizeof(bgint_t), 1, bwtFile) != 1
1577 || fwrite(bwt->cumulativeFreq + 1,
1578 sizeof(bgint_t), ALPHABET_SIZE, bwtFile) != ALPHABET_SIZE
1579 || fwrite(bwt->bwtCode,
1580 sizeof(unsigned int), bwtLength, bwtFile) != bwtLength) {
1581 fprintf(stderr, "BWTSaveBwtCodeAndOcc(): Error writing to %s : %s\n",
1582 bwtFileName, strerror(errno));
1583 exit(1);
1584 }
1585 if (fclose(bwtFile) != 0) {
1586 fprintf(stderr, "BWTSaveBwtCodeAndOcc(): Error on closing %s : %s\n",
1587 bwtFileName, strerror(errno));
1588 exit(1);
1589 }
1590 }
1591
1592 void bwt_bwtgen2(const char *fn_pac, const char *fn_bwt, int block_size)
1593 {
1594 BWTInc *bwtInc;
1595 bwtInc = BWTIncConstructFromPacked(fn_pac, block_size, block_size);
1596 fprintf(stderr, "[bwt_gen] Finished constructing BWT in %u iterations.\n", bwtInc->numberOfIterationDone);
1597 BWTSaveBwtCodeAndOcc(bwtInc->bwt, fn_bwt, 0);
1598 BWTIncFree(bwtInc);
1599 }
1600
1601 void bwt_bwtgen(const char *fn_pac, const char *fn_bwt)
1602 {
1603 bwt_bwtgen2(fn_pac, fn_bwt, 10000000);
1604 }
1605
1606 int bwt_bwtgen_main(int argc, char *argv[])
1607 {
1608 if (argc < 3) {
1609 fprintf(stderr, "Usage: bwtgen <in.pac> <out.bwt>\n");
1610 return 1;
1611 }
1612 bwt_bwtgen(argv[1], argv[2]);
1613 return 0;
1614 }
1615
1616 #ifdef MAIN_BWT_GEN
1617
1618 int main(int argc, char *argv[])
1619 {
1620 return bwt_bwtgen_main(argc, argv);
1621 }
1622
1623 #endif