Debian Codegraph @

libkmer/positionDB.C

raw
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <strings.h>
4 #include <new>
5
6 #include "bio++.H"
7 #include "positionDB.H"
8 #include "existDB.H"
9 #include "libmeryl.H"
10
11 #undef ERROR_CHECK_COUNTING
12 #undef ERROR_CHECK_COUNTING_ENCODING
13 #undef ERROR_CHECK_EMPTY_BUCKETS
14
15 // This tests Chunlin Xiao's discovered bug -- if there are a small
16 // number of unique mers, compared to distinct mers (2 * #unique_mers
17 // < #distinct_mers, we would overflow the position pointer in
18 // buckets. This enables a check that it doesn't occur.
19 //
20 // This has a fixed allocation size, and crashes on larger inputs.
21 //
22 #undef TEST_NASTY_BUGS
23
24 // Tests that mers are masked out properly. Doesn't handle canonical
25 // mers though.
26 //
27 #undef MER_REMOVAL_TEST
28
29
30 positionDB::positionDB(char const *filename,
31 uint32 merSize,
32 uint32 merSkip,
33 uint32 maxMismatch,
34 bool loadData) {
35 memset(this, 0, sizeof(positionDB));
36
37 // loadData == false only for driver-posDB.C, and only so it can
38 // dump stats on a posDB file.
39
40 if (loadState(filename, true, false) == false) {
41 fprintf(stderr, "positionDB()-- Tried to read state from '%s', but failed.\n", filename);
42 exit(1);
43 }
44
45 if ((loadData) && (merSize != _merSizeInBases)) {
46 fprintf(stderr, "positionDB()-- Tried to read state from '%s', but mer size is wrong (found "uint32FMT", wanted "uint32FMT").\n",
47 filename, _merSizeInBases, merSize);
48 exit(1);
49 }
50
51 if ((loadData) && (merSkip != _merSkipInBases)) {
52 fprintf(stderr, "positionDB()-- Tried to read state from '%s', but mer skip is wrong (found "uint32FMT", wanted "uint32FMT").\n",
53 filename, _merSkipInBases, merSkip);
54 exit(1);
55 }
56
57 if ((loadData) && (maxMismatch != _nErrorsAllowed)) {
58 fprintf(stderr, "positionDB()-- Tried to read state from '%s', but max number of mismatches is wrong (found "uint32FMT", wanted "uint32FMT").\n",
59 filename, _nErrorsAllowed, maxMismatch);
60 exit(1);
61 }
62
63 if (loadState(filename, true, loadData) == false) {
64 fprintf(stderr, "positionDB()-- Tried to read state from '%s', but failed.\n", filename);
65 exit(1);
66 }
67 }
68
69
70 positionDB::positionDB(merStream *MS,
71 uint32 merSize,
72 uint32 merSkip,
73 existDB *mask,
74 existDB *only,
75 merylStreamReader *counts,
76 uint32 minCount,
77 uint32 maxCount,
78 uint32 maxMismatch,
79 uint32 maxMemory,
80 bool beVerbose) {
81
82 memset(this, 0, sizeof(positionDB));
83
84 // Guesstimate a nice table size based on the number of input mers
85 // and the mersize, unless the user gave us a table size.
86 //
87 // We need to ensure that
88 // 2 * merSize + posnWidth + 1 - 64 <= tblBits <= 2 * merSize - 4
89 //
90 // The catch is that we don't exactly know posnWidth right now. We
91 // can overestimate it, though, based on the size of the sequence
92 // that is backing the merStream.
93 //
94 // The second catch is that we don't want to make tblBits too big
95 // or too small. If too big, we waste a lot of memory in the hash
96 // table pointers, and if too small, we waste even more memory in
97 // the data table (not to mention the algorithm dies because it
98 // assumed buckets in the data table are small).
99 //
100 // The memory size is (roughly):
101 //
102 // 2^tblBits * log(numDistinctMers) +
103 // numDistinctMers * (2*merSize - tblBits + 1 + log(numMers) +
104 // (numMers - numUniqieMers) * log(numMers)
105 //
106 // this is approximately proportional to:
107 //
108 // 2^tblBits * posnWidth +
109 // approxMers * (2*merSize - tblBits + 1 + posnWidth)
110 //
111 uint64 approxMers = MS->approximateNumberOfMers();
112 uint64 posnWidth = logBaseTwo64(approxMers + 1);
113
114 // Find the smallest and largest tblBits we could possibly use.
115 //
116 uint64 sm = 2 * merSize + posnWidth + 1 - 64;
117 uint64 lg = 2 * merSize - 4;
118
119 if (2 * merSize + posnWidth + 1 < 64)
120 sm = 2;
121
122 if (sm < 16)
123 sm = 16;
124
125 if (sm > lg) {
126 fprintf(stderr, "ERROR: too many mers for this mersize!\n");
127 fprintf(stderr, " sm = "uint64FMT"\n", sm);
128 fprintf(stderr, " lg = "uint64FMT"\n", lg);
129 fprintf(stderr, " merSize = "uint32FMT" bits\n", 2 * merSize);
130 fprintf(stderr, " approxMers = "uint64FMT" mers\n", approxMers);
131 fprintf(stderr, " posnWidth = "uint64FMT" bits\n", posnWidth);
132 exit(1);
133 }
134
135
136 // Iterate through all the choices, picking the one with the
137 // smallest expected footprint.
138 //
139 {
140
141 if (beVerbose) {
142 fprintf(stderr, "potential configurations for approximately "uint64FMT" "uint32FMT"-mers (posnW="uint64FMT").\n",
143 approxMers, merSize, posnWidth);
144 }
145
146 uint64 mini = 0; // tblSize of the smallest found
147 uint64 minm = ~mini; // memory size of the smallest found
148 double minw = 0.0; // work of the smallest found
149
150 uint64 memory = 0;
151 double effort = 0;
152
153 if (maxMemory == 0)
154 maxMemory = ~uint32ZERO;
155
156 for (uint64 i=sm; i<=lg; i++) {
157
158 // These are only needed if maxMismatch is set, but it's
159 // simpler to always set.
160 //
161 _merSizeInBases = merSize;
162 _merSizeInBits = 2 * _merSizeInBases;
163 _merSkipInBases = merSkip;
164 _tableSizeInBits = i;
165 _tableSizeInEntries = uint64ONE << _tableSizeInBits;
166 _hashWidth = uint32ZERO;
167 _hashMask = uint64MASK(_tableSizeInBits);
168 _chckWidth = _merSizeInBits - _tableSizeInBits;
169 _posnWidth = uint64ZERO;
170 _sizeWidth = 0;
171
172 _shift1 = _merSizeInBits - _tableSizeInBits;
173 _shift2 = _shift1 / 2;
174 _mask1 = uint64MASK(_tableSizeInBits);
175 _mask2 = uint64MASK(_shift1);
176
177 // Everyone wants to know the memory size (in MB).
178 //
179 memory = ((uint64ONE << i) * posnWidth + approxMers * (2*merSize - i + 1 + posnWidth)) >> 23;
180
181 // If we know we're looking for mismatches, we compute the amount
182 // of work needed per lookup, and use that, instead of strict
183 // memory sizing, to deicde the table size.
184 //
185 if (maxMismatch > 0)
186 effort = setUpMismatchMatcher(maxMismatch, approxMers);
187
188 // If our memory size is smaller than allowed, AND it's the
189 // smallest, or the work is smaller, save the table size.
190 //
191 if ((memory < maxMemory) &&
192 ((memory < minm) ||
193 (effort < minw))) {
194 mini = i;
195 minm = memory;
196 minw = effort;
197 }
198
199 if (beVerbose) {
200 fprintf(stderr, "tblBits="uint64FMTW(2)" shifts="uint32FMTW(02)","uint32FMTW(02)" -- size %8.3fGB -- work %8.3f%s\n",
201 i, _shift1, _shift2, memory / 1024.0, effort, (mini == i) ? " ***" : "");
202 }
203 }
204
205 _tableSizeInBits = mini;
206 }
207
208
209 if (_tableSizeInBits == 0) {
210 fprintf(stderr, "ERROR: No positionDB parameters within allowed memory limit.\n");
211 exit(1);
212 }
213
214
215 if (beVerbose) {
216 uint32 s1 = 2*merSize-_tableSizeInBits;
217 fprintf(stderr, "tblBits="uint32FMT" s1="uint32FMT" s2="uint32FMT" -- merSize="uint32FMT" bits + posnWidth="uint64FMT" bits (est "uint64FMT" mers) FINAL\n",
218 _tableSizeInBits, s1, s1/2, merSize, posnWidth, approxMers);
219 }
220
221
222 _merSizeInBases = merSize;
223 _merSizeInBits = 2 * _merSizeInBases;
224 _merSkipInBases = merSkip;
225 _tableSizeInEntries = uint64ONE << _tableSizeInBits;
226 _hashWidth = uint32ZERO;
227 _hashMask = uint64MASK(_tableSizeInBits);
228 _chckWidth = _merSizeInBits - _tableSizeInBits;
229 _posnWidth = uint64ZERO;
230 _sizeWidth = 0;
231
232 if (maxCount == 0)
233 maxCount = ~uint32ZERO;
234
235 if (counts)
236 _sizeWidth = (maxCount < ~uint32ZERO) ? logBaseTwo64(maxCount+1) : 32;
237
238 _shift1 = _merSizeInBits - _tableSizeInBits;
239 _shift2 = _shift1 / 2;
240 _mask1 = uint64MASK(_tableSizeInBits);
241 _mask2 = uint64MASK(_shift1);
242
243 #if 0
244 fprintf(stderr, "merSizeInBits "uint32FMT"\n", _merSizeInBits);
245 fprintf(stderr, "hashWidth "uint32FMT"\n", _hashWidth);
246 fprintf(stderr, "chckWidth "uint32FMT"\n", _chckWidth);
247 fprintf(stderr, "shift1 "uint32FMT"\n", _shift1);
248 fprintf(stderr, "shift2 "uint32FMT"\n", _shift2);
249 #endif
250
251 if (maxMismatch > 0)
252 setUpMismatchMatcher(maxMismatch, approxMers);
253
254 build(MS, mask, only, counts, minCount, maxCount, beVerbose);
255 }
256
257
258
259 void
260 positionDB::build(merStream *MS,
261 existDB *mask,
262 existDB *only,
263 merylStreamReader *counts,
264 uint32 minCount,
265 uint32 maxCount,
266 bool beVerbose) {
267
268 _bucketSizes = 0L;
269 _countingBuckets = 0L;
270 _hashTable_BP = 0L;
271 _hashTable_FW = 0L;
272 _buckets = 0L;
273 _positions = 0L;
274
275 _wCnt = 0;
276 _wFin = 0;
277
278 // For get/setDecodedValues().
279 uint64 lensC[4] = {~uint64ZERO, ~uint64ZERO, ~uint64ZERO, ~uint64ZERO};
280 uint64 lensF[4] = {~uint64ZERO, ~uint64ZERO, ~uint64ZERO, ~uint64ZERO};
281 uint64 vals[4] = {0};
282 uint64 nval = (_sizeWidth == 0) ? 3 : 4;
283
284 _numberOfMers = uint64ZERO;
285 _numberOfPositions = uint64ZERO;
286 _numberOfDistinct = uint64ZERO;
287 _numberOfUnique = uint64ZERO;
288 _numberOfEntries = uint64ZERO;
289 _maximumEntries = uint64ZERO;
290
291 // We assume later that these are already allocated.
292 _sortedMax = 16384;
293 _sortedChck = new uint64 [_sortedMax];
294 _sortedPosn = new uint64 [_sortedMax];
295
296 if (MS == 0L) {
297 fprintf(stderr, "positionDB()-- ERROR: No merStream? Nothing to build a table with!\n");
298 exit(1);
299 }
300
301 MS->rewind();
302
303
304 ////////////////////////////////////////////////////////////////////////////////
305 //
306 // 1) Count bucket sizes
307 //
308
309 // We'll later want to reuse the _bucketSizes space for storing the
310 // hash table. To make it somewhat safe, we allocate the space as
311 // uint64, then cast it to be uint32.
312 //
313 // bktAllocIsJunk tells us if we should release this memory (if we
314 // need to allocate separate space for the hash table). We'd need
315 // to do this if the hashWidth is more than 32 bits, but we won't
316 // know that for a little bit.
317 //
318 // The _bucketSizes is offset by one from bktAlloc so that we don't
319 // overwrite _bucketSizes when we are constructing hash table.
320 //
321 uint64 *bktAlloc;
322 try {
323 bktAlloc = new uint64 [_tableSizeInEntries / 2 + 4];
324 } catch (std::bad_alloc) {
325 fprintf(stderr, "positionDB()-- caught std::bad_alloc in %s at line %d\n", __FILE__, __LINE__);
326 fprintf(stderr, "positionDB()-- bktAlloc = new uint64 ["uint64FMT"]\n", _tableSizeInEntries / 2 + 4);
327 exit(1);
328 }
329 bool bktAllocIsJunk = false;
330
331 bzero(bktAlloc, sizeof(uint64) * (_tableSizeInEntries / 2 + 4));
332
333 // Why +2? We try to reuse the bktAlloc space for the hash table,
334 // which is constructed from the bucketSizes. The hashTable is
335 // built from the bucketSizes. It definitely needs to be +1, and
336 // so we use +2 just in case the human is being stupid again.
337 //
338 _bucketSizes = (uint32 *)(bktAlloc + 2);
339
340 #ifdef ERROR_CHECK_COUNTING
341 fprintf(stdout, "ERROR_CHECK_COUNTING is defined.\n");
342 uint32 *_errbucketSizes = new uint32 [_tableSizeInEntries + 2];
343 for (uint64 i=0; i<_tableSizeInEntries + 2; i++)
344 _errbucketSizes[i] = uint32ZERO;
345 #endif
346
347 if (beVerbose)
348 fprintf(stderr, " Allocated bucket size counting space with total size "uint64FMT" KB\n", _tableSizeInEntries >> 8);
349
350
351 speedCounter *C = new speedCounter(" %7.2f Mmers -- %5.2f Mmers/second\r", 1000000.0, 0x1fffff, beVerbose);
352
353 // Two choices here
354 //
355 // 1) No masking or onlying is done. Stream the mers and just
356 // count the positions. This is the original behavior.
357 //
358 // 2) Masking or onlying is done. Open the output stream file,
359 // stream the mers by, checking for mask/only of both
360 // forward and reverse mers. If either is found, push
361 // the (forward) mer and position onto the stream.
362 // close the output stream.
363 //
364 // Save the mer if it doesn't exist in the mask (both f and r),
365 // or does exist in the only (either f or r), add it.
366 //
367 // The input databases for mask and only are (currently) made
368 // using canonical mers. We halve the number of exists() by
369 // also using canonical mers here.
370 //
371
372 MS->rewind();
373
374 while (MS->nextMer(_merSkipInBases)) {
375 _bucketSizes[ HASH(MS->theFMer()) ]++;
376
377 #ifdef ERROR_CHECK_COUNTING
378 _errbucketSizes[ HASH(MS->theFMer()) ]++;
379 #endif
380
381 _numberOfMers++;
382 _numberOfPositions = MS->thePositionInStream();
383 assert((_numberOfPositions >> 60) == 0);
384 C->tick();
385 }
386
387
388 delete C;
389 C = 0L;
390
391 if (beVerbose)
392 fprintf(stderr, " Found "uint64FMT" mers (max position = "uint64FMT")\n", _numberOfMers, _numberOfPositions);
393
394 // This caught a nasty bug in merStream rewind(), and it's pretty
395 // cheap, so I left it in. Search for the other DEBUGnumPositions.
396 //
397 uint64 DEBUGnumPositions = _numberOfPositions + 1;
398
399 // This is _numberOfMers+1 because we need to store the first
400 // position after the last mer. That is, if there are two mers, we
401 // will store that the first mer is at position 0, the second mer
402 // is at position 1, and the end of the second mer is at position
403 // 2.
404 //
405 // In reality, it should be the number of distinct mers, not the
406 // total number of mers, but we don't know that yet. And so
407 // occasionally we'll make things too big and waste a bit of
408 // memory.
409 //
410 _hashWidth = logBaseTwo64(_numberOfMers+1);
411 _posnWidth = logBaseTwo64(_numberOfPositions+1);
412
413
414
415 ///////////////////////////////////////////////////////////////////////////////
416 //
417 // 2) Allocate buckets and make bucketSizes be a pointer into them
418 //
419 _wCnt = _chckWidth + _posnWidth + 1 + _sizeWidth;
420
421 lensC[0] = _chckWidth;
422 lensC[1] = _posnWidth;
423 lensC[2] = 1;
424 lensC[3] = _sizeWidth;
425
426 uint64 bucketsSpace = (_numberOfMers+1) * _wCnt / 64 + 1;
427 uint32 endPosition = 0;
428
429 if (beVerbose)
430 fprintf(stderr, " Allocated "uint64FMT"KB for buckets ("uint64FMT" 64-bit words)\n", bucketsSpace >> 7, bucketsSpace);
431 try {
432 _countingBuckets = new uint64 [bucketsSpace];
433 } catch (std::bad_alloc) {
434 fprintf(stderr, "positionDB()-- caught std::bad_alloc in %s at line %d\n", __FILE__, __LINE__);
435 fprintf(stderr, "positionDB()-- _countingBuckets = new uint64 ["uint64FMT"]\n", bucketsSpace);
436 exit(1);
437 }
438
439 for (uint64 i=0; i<bucketsSpace; i++)
440 _countingBuckets[i] = ~uint64ZERO;
441
442 for (uint64 i=0; i<_tableSizeInEntries; i++) {
443 endPosition += _bucketSizes[i];
444 _bucketSizes[i] = endPosition;
445 }
446 _bucketSizes[_tableSizeInEntries] = endPosition;
447
448 #ifdef ERROR_CHECK_COUNTING
449 if (endPosition != _numberOfMers)
450 fprintf(stdout, "ERROR_CHECK_COUNTING: BUCKETSIZE COUNTING PROBLEM -- endPos="uint32FMT" != numMers="uint64FMT"\n",
451 endPosition, _numberOfMers);
452 #endif
453
454
455 ////////////////////////////////////////////////////////////////////////////////
456 //
457 // 3) Build list of mers with positions
458 //
459 if (beVerbose)
460 fprintf(stderr, " Building lists with positions.\n");
461
462 C = new speedCounter(" %7.2f Mmers -- %5.2f Mmers/second\r", 1000000.0, 0x1fffff, beVerbose);
463
464 #ifdef ERROR_CHECK_COUNTING_ENCODING
465 fprintf(stdout, "ERROR_CHECK_COUNTING_ENCODING is defined!\n");
466 #endif
467
468
469 MS->rewind();
470
471 while (MS->nextMer(_merSkipInBases)) {
472 uint64 h = HASH(MS->theFMer());
473
474 #ifdef ERROR_CHECK_COUNTING
475 if (_bucketSizes[h] == 0) {
476 char str[33];
477 fprintf(stderr, "positionDB()-- ERROR_CHECK_COUNTING: Bucket "uint64FMT" ran out of things! '%s'\n", h, MS->theFMer().merToString(str));
478 fprintf(stderr, "positionDB()-- ERROR_CHECK_COUNTING: Stream is at "uint64FMT"\n", MS->thePositionInStream());
479 }
480 #endif
481
482 _bucketSizes[h]--;
483
484 #ifdef ERROR_CHECK_COUNTING
485 _errbucketSizes[h]--;
486 #endif
487
488
489 #ifdef ERROR_CHECK_EMPTY_BUCKETS
490 // Check that everything is empty. Empty is defined as set to all 1's.
491 getDecodedValues(_countingBuckets, (uint64)_bucketSizes[h] * (uint64)_wCnt, nval, lensC, vals);
492
493 if (((~vals[0]) & uint64MASK(lensC[0])) ||
494 ((~vals[1]) & uint64MASK(lensC[1])) ||
495 ((~vals[2]) & uint64MASK(lensC[2])) ||
496 ((lensC[3] > 0) && ((~vals[3]) & uint64MASK(lensC[3]))))
497 fprintf(stdout, "ERROR_CHECK_EMPTY_BUCKETS: countingBucket not empty! pos=%lu 0x%016lx 0x%016lx 0x%016lx 0x%016lx\n",
498 _bucketSizes[h] * _wCnt,
499 (~vals[0]) & uint64MASK(lensC[0]),
500 (~vals[1]) & uint64MASK(lensC[1]),
501 (~vals[2]) & uint64MASK(lensC[2]),
502 (~vals[3]) & uint64MASK(lensC[3]));
503 #endif
504
505 vals[0] = CHECK(MS->theFMer());
506 vals[1] = MS->thePositionInStream();
507 vals[2] = 0;
508 vals[3] = 0;
509
510 setDecodedValues(_countingBuckets, (uint64)_bucketSizes[h] * (uint64)_wCnt, nval, lensC, vals);
511
512 #ifdef ERROR_CHECK_COUNTING_ENCODING
513 getDecodedValues(_countingBuckets, (uint64)_bucketSizes[h] * (uint64)_wCnt, nval, lensC, vals);
514
515 if (vals[0] != CHECK(MS->theFMer()))
516 fprintf(stdout, "ERROR_CHECK_COUNTING_ENCODING error: CHCK corrupted! Wanted "uint64HEX" got "uint64HEX"\n",
517 CHECK(MS->theFMer()), vals[0]);
518 if (vals[1] != MS->thePositionInStream())
519 fprintf(stdout, "ERROR_CHECK_COUNTING_ENCODING error: POSN corrupted! Wanted "uint64HEX" got "uint64HEX"\n",
520 MS->thePositionInStream(), vals[1]);
521 if (vals[2] != 0)
522 fprintf(stdout, "ERROR_CHECK_COUNTING_ENCODING error: UNIQ corrupted.\n");
523 if (vals[3] != 0)
524 fprintf(stdout, "ERROR_CHECK_COUNTING_ENCODING error: SIZE corrupted.\n");
525 #endif
526
527 C->tick();
528 }
529
530
531 delete C;
532 C = 0L;
533
534 #ifdef ERROR_CHECK_COUNTING
535 for (uint64 i=0; i<_tableSizeInEntries; i++)
536 if (_errbucketSizes[i] != 0)
537 fprintf(stdout, "ERROR_CHECK_COUNTING: Bucket "uint32FMT" wasn't filled fully? "uint32FMT" left over.\n", i, _errbucketSizes[i]);
538
539 delete [] _errbucketSizes;
540 _errbucketSizes = 0L;
541 #endif
542
543
544 ////////////////////////////////////////////////////////////////////////////////
545 //
546 // 4) Sort each bucket -- count:
547 // 1) number of distinct mers
548 // 2) number of unique mers
549 // 3) number of entries in position table ( sum mercount+1 for all mercounts > 1)
550 // also need to repack the sorted things
551 //
552 if (beVerbose)
553 fprintf(stderr, " Sorting and repacking buckets ("uint64FMT" buckets).\n", _tableSizeInEntries);
554
555 C = new speedCounter(" %7.2f Mbuckets -- %5.2f Mbuckets/second\r", 1000000.0, 0x1ffffff, beVerbose);
556 for (uint64 i=0; i<_tableSizeInEntries; i++) {
557 sortAndRepackBucket(i);
558 C->tick();
559 }
560 delete C;
561 C = 0L;
562
563 if (beVerbose)
564 fprintf(stderr,
565 " Found "uint64FMTW(12)" total mers\n"
566 " Found "uint64FMTW(12)" distinct mers\n"
567 " Found "uint64FMTW(12)" unique mers\n"
568 " Need "uint64FMT" non-unique position list entries ("uint64FMT" maximum count)\n",
569 _numberOfMers, _numberOfDistinct, _numberOfUnique, _numberOfEntries, _maximumEntries);
570
571
572
573 ////////////////////////////////////////////////////////////////////////////////
574 //
575 // Compute the size of the final bucket position entry. It's
576 // either a position into the sequence, or a pointer into a list of
577 // positions. In rare cases, the pointer is larger than the
578 // sequence position, and we need to do extra work.
579 //
580 // The width of position pointers (in buckets) is the max of
581 // _posnWidth (a pointer to the sequence position) and
582 // _pptrWidth (a pointer to an entry in the positions table).
583 //
584 _pptrWidth = logBaseTwo64(_numberOfEntries+1);
585 if (_pptrWidth < _posnWidth)
586 _pptrWidth = _posnWidth;
587
588 _wFin = _chckWidth + _pptrWidth + 1 + _sizeWidth;
589
590 lensF[0] = _chckWidth;
591 lensF[1] = _pptrWidth;
592 lensF[2] = 1;
593 lensF[3] = _sizeWidth;
594
595 ////////////////////////////////////////////////////////////////////////////////
596 //
597 // 5) Allocate: real hash table, buckets and position table.
598 //
599
600 // XXXX how do we count the number of buckets/positions we never
601 // use because they are masked out??
602 //
603 // If we are just thresholding (ignore things with count > 100)
604 // it's easy, a simple loop over something.
605 //
606 // If we have an exist/only db....are they in the same order? Can
607 // we loop over both at the same time and count that way? That'd
608 // be cool! Mersize is the same, why can the table size be the
609 // same too -- OK, if the existDB has a small number of mers in it,
610 // then we don't need a large table.
611
612 uint64 hs = _tableSizeInEntries * _hashWidth / 64 + 1;
613 uint64 bs = _numberOfDistinct * _wFin / 64 + 1;
614 uint64 ps = _numberOfEntries * _posnWidth / 64 + 1;
615
616 if (_hashWidth <= 32) {
617 if (beVerbose)
618 fprintf(stderr, " Reusing bucket counting space for hash table.\n");
619
620 #ifdef UNCOMPRESS_HASH_TABLE
621 _hashTable_BP = 0L;
622 _hashTable_FW = (uint32 *)bktAlloc;
623 #else
624 _hashTable_BP = bktAlloc;
625 _hashTable_FW = 0L;
626 #endif
627
628 bktAllocIsJunk = false;
629 } else {
630
631 // Can't use the full-width hash table, since the data size is >
632 // 32 bits -- we'd need to allocate 64-bit ints for it, and
633 // that'll likely be too big...and we'd need to have
634 // _hashTable_FW64 or something.
635
636 if (beVerbose)
637 fprintf(stderr, " Allocated "uint64FMTW(10)"KB for hash table ("uint64FMT" 64-bit words)\n", hs >> 7, hs);
638 try {
639 _hashTable_BP = new uint64 [hs];
640 _hashTable_FW = 0L;
641 } catch (std::bad_alloc) {
642 fprintf(stderr, "positionDB()-- caught std::bad_alloc in %s at line %d\n", __FILE__, __LINE__);
643 fprintf(stderr, "positionDB()-- _hashTable_BP = new uint64 ["uint64FMT"]\n", hs);
644 exit(1);
645 }
646 bktAllocIsJunk = true;
647 }
648
649
650 // If we have enough space to reuse the counting space, reuse it.
651 // Else, allocate more space.
652 //
653 // We need to ensure that there are enough bits and that the size
654 // of a bucket didn't increase. If the bucket size did increase,
655 // and we see more unique buckets than total mers (up to some
656 // point) we overwrite data.
657 //
658 // Recall that bucketSpace ~= numberOfMers * wCnt
659 //
660 if ((bs < bucketsSpace) && (_wFin <= _wCnt)) {
661 if (beVerbose)
662 fprintf(stderr, " Reusing bucket space; Have: "uint64FMT" Need: "uint64FMT" (64-bit words)\n", bucketsSpace, bs);
663
664 _buckets = _countingBuckets;
665
666 bs = bucketsSpace; // for output at the end
667 } else {
668 if (beVerbose)
669 fprintf(stderr, " Allocated "uint64FMTW(10)"KB for buckets ("uint64FMT" 64-bit words)\n", bs >> 7, bs);
670 try {
671 _buckets = new uint64 [bs];
672 } catch (std::bad_alloc) {
673 fprintf(stderr, "positionDB()-- caught std::bad_alloc in %s at line %d\n", __FILE__, __LINE__);
674 fprintf(stderr, "positionDB()-- _buckets = new uint64 ["uint64FMT"]\n", bs);
675 exit(1);
676 }
677 }
678
679 if (beVerbose)
680 fprintf(stderr, " Allocated "uint64FMTW(10)"KB for positions ("uint64FMT" 64-bit words)\n", ps >> 7, ps);
681 try {
682 _positions = new uint64 [ps];
683 } catch (std::bad_alloc) {
684 fprintf(stderr, "positionDB()-- caught std::bad_alloc in %s at line %d\n", __FILE__, __LINE__);
685 fprintf(stderr, "positionDB()-- _positions = new uint64 ["uint64FMT"\n", ps);
686 exit(1);
687 }
688
689
690 ////////////////////////////////////////////////////////////////////////////////
691 //
692 // 6) Transfer from the sorted buckets to the hash table.
693 //
694 if (beVerbose)
695 fprintf(stderr, " Transferring to final structure ("uint64FMT" buckets).\n", _tableSizeInEntries);
696
697 uint64 bucketStartPosition = 0;
698
699 // Current positions and bit positions in the buckets and position list.
700 //
701 uint64 currentBbit = uint64ZERO; // Bit position into bucket
702 uint64 currentPbit = uint64ZERO; // Bit position into positions
703 uint64 currentPpos = uint64ZERO; // Value position into positions
704
705 #ifdef TEST_NASTY_BUGS
706 // Save the position array pointer of each bucket for debugging.
707 //
708 uint64 currentBpos = uint64ZERO; // Value position into bucket
709 uint32 *posPtrCheck = new uint32 [65826038];
710 #endif
711
712 // We also take this opportunity to reset some statistics that are
713 // wrong.
714 //
715 _numberOfMers = 0;
716 _numberOfPositions = 0;
717 _numberOfDistinct = 0;
718 _numberOfUnique = 0;
719 _numberOfEntries = 0;
720 _maximumEntries = 0;
721
722 C = new speedCounter(" %7.2f Mbuckets -- %5.2f Mbuckets/second\r", 1000000.0, 0x1ffffff, beVerbose);
723
724 // We need b outside the loop!
725 //
726 uint64 b;
727 for (b=0; b<_tableSizeInEntries; b++) {
728 C->tick();
729
730 // Set the start of the bucket -- we took pains to ensure that
731 // we don't overwrite _bucketSizes[b], if we are reusing that
732 // space for the hash table.
733 //
734 if (_hashTable_BP)
735 setDecodedValue(_hashTable_BP, (uint64)b * (uint64)_hashWidth, _hashWidth, bucketStartPosition);
736 else
737 _hashTable_FW[b] = bucketStartPosition;
738
739 // Get the number of mers in the counting bucket. The error
740 // checking and sizing of _sortedChck and _sortedPosn was already
741 // done in the sort.
742 //
743 uint64 st = _bucketSizes[b];
744 uint64 ed = _bucketSizes[b+1];
745 uint32 le = ed - st;
746
747 // Unpack the check values
748 //
749 for (uint64 i=st, J=st * _wCnt; i<ed; i++, J += _wCnt) {
750 getDecodedValues(_countingBuckets, J, 2, lensC, vals);
751 _sortedChck[i-st] = vals[0];
752 _sortedPosn[i-st] = vals[1];
753 }
754
755
756 // Walk through the counting bucket, adding things to the real
757 // bucket as we see them. Mers with more than one position are
758 // inserted into the bucket, and the positions inserted into the
759 // position list.
760
761 // start and end locations of the mer. For mers with only
762 // one occurrance (unique mers), stM+1 == edM.
763 //
764 uint32 stM = uint32ZERO;
765 uint32 edM = uint32ZERO;
766
767 while (stM < le) {
768
769 // Move to the next mer.
770 //
771 edM++;
772
773 // Keep moving while the two mers are the same.
774 //
775 while ((edM < le) && (_sortedChck[stM] == _sortedChck[edM]))
776 edM++;
777
778 // edM is now the mer after the last. Write all mers from stM
779 // up to edM to the final structure. If there is one mer, put
780 // it in the bucket. If not, put a pointer to the position
781 // array there.
782
783 // We're in bucket b, looking at mer _sortedChck[stM]. Ask the
784 // only/mask if that exists, if so do/do not include the mer.
785 //
786 bool useMer = true;
787
788 if (edM - stM < minCount)
789 useMer = false;
790
791 if (edM - stM > maxCount)
792 useMer = false;
793
794 if ((useMer == true) && (mask || only)) {
795
796 // MER_REMOVAL_DURING_XFER. Great. The existDB has
797 // (usually) the canonical mer. We have the forward mer.
798 // Well, no, we have the forward mers' hash and check. So,
799 // we reconstruct the mer, reverse complement it, and then
800 // throw the mer out if either the forward or reverse exists
801 // (or doesn't exist).
802
803 uint64 m = REBUILD(b, _sortedChck[stM]);
804 uint64 r;
805
806 if (mask) {
807 if (mask->isCanonical()) {
808 r = reverseComplementMer(_merSizeInBases, m);
809 if (r < m)
810 m = r;
811 }
812 if (mask->exists(m))
813 useMer = false;
814 }
815
816 if (only) {
817 if (only->isCanonical()) {
818 r = reverseComplementMer(_merSizeInBases, m);
819 if (r < m)
820 m = r;
821 }
822 if (only->exists(m) == false)
823 useMer = false;
824 }
825 }
826
827 if (useMer) {
828 _numberOfMers += edM - stM;
829 _numberOfPositions += edM - stM;
830 _numberOfDistinct++;
831
832 if (stM+1 == edM) {
833 _numberOfUnique++;
834
835 #ifdef TEST_NASTY_BUGS
836 posPtrCheck[currentBpos++] = _sortedPosn[stM];
837 #endif
838
839 vals[0] = _sortedChck[stM];
840 vals[1] = _sortedPosn[stM];
841 vals[2] = 1;
842 vals[3] = 0;
843
844 currentBbit = setDecodedValues(_buckets, currentBbit, nval, lensF, vals);
845 bucketStartPosition++;
846 } else {
847 _numberOfEntries += edM - stM;
848 if (_maximumEntries < edM - stM)
849 _maximumEntries = edM - stM;
850
851 #ifdef TEST_NASTY_BUGS
852 posPtrCheck[currentBpos++] = currentPpos;
853 #endif
854
855 vals[0] = _sortedChck[stM];
856 vals[1] = currentPpos;
857 vals[2] = 0;
858 vals[3] = 0;
859
860 currentBbit = setDecodedValues(_buckets, currentBbit, nval, lensF, vals);
861 bucketStartPosition++;
862
863 // Store the positions. Store the number of positions
864 // here, then store all positions.
865 //
866 // The positions are in the proper place in _sortedPosn,
867 // and setDecodedValue masks out the extra crap, so no
868 // temporary needed. Probably should be done with
869 // setDecodedValues, but then we need another array telling
870 // the sizes of each piece.
871 //
872 setDecodedValue(_positions, currentPbit, _posnWidth, edM - stM);
873 currentPbit += _posnWidth;
874 currentPpos++;
875
876 for (; stM < edM; stM++) {
877 if (_sortedPosn[stM] >= DEBUGnumPositions) {
878 fprintf(stderr, "positionDB()-- ERROR: Got position "uint64FMT", but only "uint64FMT" available!\n",
879 _sortedPosn[stM], DEBUGnumPositions);
880 abort();
881 }
882 setDecodedValue(_positions, currentPbit, _posnWidth, _sortedPosn[stM]);
883 currentPbit += _posnWidth;
884 currentPpos++;
885 }
886 }
887 } // useMer
888
889 // All done with this mer.
890 //
891 stM = edM;
892 } // while (stM < le)
893 } // for each bucket
894
895 // Set the end of the last bucket
896 //
897 if (_hashTable_BP)
898 setDecodedValue(_hashTable_BP, b * _hashWidth, _hashWidth, bucketStartPosition);
899 else
900 _hashTable_FW[b] = bucketStartPosition;
901
902 delete C;
903
904 // Clear out the end of the arrays -- this is only so that we can
905 // checksum the result.
906 //
907 if (_hashTable_BP) {
908 b = b * _hashWidth + _hashWidth;
909 setDecodedValue(_hashTable_BP, b, 64 - (b % 64), uint64ZERO);
910 }
911 setDecodedValue(_buckets, currentBbit, 64 - (currentBbit % 64), uint64ZERO);
912 setDecodedValue(_positions, currentPbit, 64 - (currentPbit % 64), uint64ZERO);
913
914
915 if (beVerbose) {
916 fprintf(stderr, " Avail: Bucket "uint64FMTW(12)" Position "uint64FMTW(12)" (64-bit words)\n", bs, ps);
917 fprintf(stderr, " Avail: Bucket "uint64FMTW(12)" Position "uint64FMTW(12)" (entries)\n", _numberOfDistinct, _numberOfEntries);
918 fprintf(stderr, " Used: Bucket "uint64FMTW(12)" Position "uint64FMTW(12)" (64-bit words)\n", currentBbit / 64, currentPbit / 64);
919 }
920
921 // Reset the sizes to what we actually found. If we then
922 // dump/reload, we shrink our footprint.
923 //
924 _numberOfDistinct = currentBbit / _wFin;
925 _numberOfEntries = currentPbit / _posnWidth;
926
927 if (beVerbose) {
928 fprintf(stderr, " Used: Bucket "uint64FMTW(12)" Position "uint64FMTW(12)" (entries)\n", _numberOfDistinct, _numberOfEntries);
929 fprintf(stderr,
930 " Found "uint64FMTW(12)" total mers\n"
931 " Found "uint64FMTW(12)" distinct mers\n"
932 " Found "uint64FMTW(12)" unique mers\n"
933 " Need "uint64FMT" non-unique position list entries ("uint64FMT" maximum count)\n",
934 _numberOfMers, _numberOfDistinct, _numberOfUnique, _numberOfEntries, _maximumEntries);
935 }
936
937
938 // If we removed mers, there is a small chance that our hash table
939 // is too big -- we might have removed enoough mers to make the
940 // width smaller. If so, rebuild the hash table.
941 //
942 // Also, hooray, we finally know the number of distinct mers, so we
943 // can make this nice and tight
944 //
945 if (_hashTable_BP) {
946 uint32 newHashWidth = 1;
947 while ((_numberOfDistinct+1) > (uint64ONE << newHashWidth))
948 newHashWidth++;
949
950 if (newHashWidth != _hashWidth) {
951 uint64 npos = 0;
952 uint64 opos = 0;
953
954 if (beVerbose)
955 fprintf(stderr, " Rebuilding the hash table, from "uint32FMT" bits wide to "uint32FMT" bits wide.\n",
956 _hashWidth, newHashWidth);
957
958 for (uint64 z=0; z<_tableSizeInEntries+1; z++) {
959 setDecodedValue(_hashTable_BP,
960 npos,
961 newHashWidth,
962 getDecodedValue(_hashTable_BP, opos, _hashWidth));
963 npos += newHashWidth;
964 opos += _hashWidth;
965 }
966
967 // Clear the end again.
968 setDecodedValue(_hashTable_BP, npos, 64 - (npos % 64), uint64ZERO);
969 }
970
971 _hashWidth = newHashWidth;
972 }
973
974
975 // If supplied, add in any counts. The meryl table is, sadly, in
976 // the wrong order, and we must hash and search.
977 //
978 // Meryl _should_ be storing only forward mers, but we have no way
979 // of checking.
980 //
981 // After all counts are loaded, check if we can compress the counts
982 // space any. Check if the largestMerylCount is much smaller than
983 // the space it is stored in. If so, we can compress the table.
984 //
985 uint64 largestMerylCount = 0;
986 uint64 countsLoaded = 0;
987
988 if (counts) {
989 if (beVerbose)
990 fprintf(stderr, " Loading "uint64FMT" mercounts.\n", counts->numberOfDistinctMers());
991
992 C = new speedCounter(" %7.2f Mmercounts -- %5.2f Mmercounts/second\r", 1000000.0, 0x1fffff, beVerbose);
993
994 while (counts->nextMer()) {
995 kMer k = counts->theFMer();
996 uint64 c = counts->theCount();
997 uint64 f = setCount(k, c);
998 k.reverseComplement();
999 uint64 r = setCount(k, c);
1000
1001 if (f + r > 0) {
1002 countsLoaded++;
1003 if (largestMerylCount < c)
1004 largestMerylCount = c;
1005 }
1006
1007 C->tick();
1008 }
1009
1010 delete C;
1011
1012 if (beVerbose)
1013 fprintf(stderr, " Loaded "uint64FMT" mercounts; largest is "uint64FMT".\n", countsLoaded, largestMerylCount);
1014
1015 if (logBaseTwo64(largestMerylCount + 1) < _sizeWidth) {
1016 if (beVerbose)
1017 fprintf(stderr, " Compress sizes from "uint32FMT" bits to "uint32FMT" bits.\n",
1018 _sizeWidth,
1019 (uint32)logBaseTwo64(largestMerylCount + 1));
1020
1021 uint64 oSiz[4] = { _chckWidth, _pptrWidth, 1, _sizeWidth };
1022 uint64 nSiz[4] = { _chckWidth, _pptrWidth, 1, logBaseTwo64(largestMerylCount + 1) };
1023 uint64 tVal[4] = { 0, 0, 0, 0 };
1024
1025 uint64 oP = 0, oS = oSiz[0] + oSiz[1] + oSiz[2] + oSiz[3];
1026 uint64 nP = 0, nS = nSiz[0] + nSiz[1] + nSiz[2] + nSiz[3];
1027
1028 assert(nS < oS);
1029
1030 C = new speedCounter(" %7.2f Mmercounts -- %5.2f Mmercounts/second\r", 1000000.0, 0x1fffff, beVerbose);
1031
1032 for (uint64 bu=0; bu<_numberOfDistinct; bu++) {
1033 getDecodedValues(_buckets, oP, 4, oSiz, tVal);
1034 setDecodedValues(_buckets, nP, 4, nSiz, tVal);
1035
1036 oP += oS;
1037 nP += nS;
1038
1039 C->tick();
1040 }
1041
1042 delete C;
1043
1044 _sizeWidth = nSiz[3];
1045 _wFin = _chckWidth + _pptrWidth + 1 + _sizeWidth;
1046 }
1047 }
1048
1049
1050 #ifdef TEST_NASTY_BUGS
1051 // Unpack the bucket positions and check. Report the first one
1052 // that is broken.
1053 //
1054 for(uint64 bb=0; bb<currentBpos; bb++)
1055 if (posPtrCheck[bb] != getDecodedValue(_buckets, bb * _wFin + _chckWidth, _pptrWidth))
1056 fprintf(stderr, "Bucket %lu (at bitpos %lu) failed position check (wanted %lu got %lu)\n",
1057 bb,
1058 bb * _wFin,
1059 posPtrCheck[bb],
1060 getDecodedValue(_buckets, bb * _wFin + _chckWidth, _pptrWidth));
1061 delete [] posPtrCheck;
1062 #endif
1063
1064
1065 #ifdef MER_REMOVAL_TEST
1066 #warning MER_REMOVAL_TEST was not updated to deal with canonical mers
1067 if (beVerbose)
1068 fprintf(stderr, "positionDB()-- TESTING MER REMOVAL\n");
1069
1070 MS->rewind();
1071 if (mask) {
1072 C = new speedCounter(" %7.2f Mmers -- %5.2f Mmers/second\r", 1000000.0, 0x1fffff, beVerbose);
1073 uint32 extraMer = 0;
1074 while (MS->nextMer(_merSkipInBases)) {
1075 uint64 mer = MS->theFMer();
1076 if (mask->exists(mer) && exists(mer))
1077 extraMer++;
1078 C->tick();
1079 }
1080 delete C;
1081 fprintf(stderr, "positionDB()-- mask: "uint32FMT" mers extra!\n", extraMer);
1082 } else if (only) {
1083 C = new speedCounter(" %7.2f Mmers -- %5.2f Mmers/second\r", 1000000.0, 0x1fffff, beVerbose);
1084 uint32 missingMer = 0;
1085 while (MS->nextMer(_merSkipInBases)) {
1086 uint64 mer = MS->theFMer();
1087 if (only->exists(mer) && !exists(mer))
1088 missingMer++;
1089 C->tick();
1090 }
1091 delete C;
1092 fprintf(stderr, "positionDB()-- only: "uint32FMT" mers missing!\n", missingMer);
1093 }
1094 #endif
1095
1096 // Free the counting buckets if we aren't using the space for
1097 // something else.
1098 //
1099 if (_buckets != _countingBuckets)
1100 delete [] _countingBuckets;
1101
1102 // In theory, we could move these to be immediately after the data
1103 // is useless.
1104 //
1105 _bucketSizes = 0L;
1106 _countingBuckets = 0L;
1107
1108 delete [] _sortedChck;
1109 delete [] _sortedPosn;
1110
1111 _sortedMax = 0;
1112 _sortedChck = 0L;
1113 _sortedPosn = 0L;
1114
1115 if (bktAllocIsJunk)
1116 delete [] bktAlloc;
1117 }
1118
1119 positionDB::~positionDB() {
1120 delete [] _hashTable_BP;
1121 delete [] _hashTable_FW;
1122 delete [] _buckets;
1123 delete [] _positions;
1124 delete [] _hashedErrors;
1125 }