Debian Codegraph @

libkmer/positionDB-mismatch.C

raw
1 #include "positionDB.H"
2 #include "bio++.H"
3
4
5 static
6 int
7 stringscmp(const void *A, const void *B) {
8 uint64 const a = *(uint64 const *)A;
9 uint64 const b = *(uint64 const *)B;
10 if (a < b) return(-1);
11 if (a > b) return(1);
12 return(0);
13 }
14
15
16 static
17 uint32
18 makeUnique(uint64 *strings, uint32 stringsLen) {
19 qsort(strings, stringsLen, sizeof(uint64), stringscmp);
20 uint32 len = 0;
21 uint32 nxt = 1;
22 while (nxt < stringsLen) {
23 if (strings[len] != strings[nxt]) {
24 len++;
25 strings[len] = strings[nxt];
26 }
27 nxt++;
28 }
29 return(len+1);
30 }
31
32
33 #if 0
34 // debug
35 static
36 void
37 dumpPatterns(uint64 *strings, uint32 stringsLen, uint32 ts) {
38 for (uint32 i=0; i<stringsLen; i++) {
39 char str[1024] = {0};
40 uint32 cnt = 0;
41
42 for (uint32 b=0; b<ts; b++) {
43 if (strings[i] & (uint64ONE << b)) {
44 str[b] = '1';
45 cnt++;
46 } else {
47 str[b] = '0';
48 }
49 }
50
51 fprintf(stdout, "%s\t"uint32FMT"\n", str, cnt);
52 }
53 }
54 #endif
55
56
57 double
58 positionDB::setUpMismatchMatcher(uint32 nErrorsAllowed, uint64 approxMers) {
59
60 // Build an xor mask that will generate all errors for a given
61 // mersize.
62
63 _nErrorsAllowed = nErrorsAllowed;
64 _hashedErrorsLen = 0;
65 _hashedErrorsMax = 0;
66 _hashedErrors = 0L;
67
68 uint32 stringsMax = 128 * 1024 * 1024;
69 uint32 stringsLen = 0;
70 uint64 *strings = new uint64 [stringsMax];
71
72 uint64 totpat = 0;
73 uint64 toterr = 0;
74
75 uint64 m1, m2, m3, m4, m5, m6;
76 uint64 *e1, *e2, *e3, *e4, *e5, *e6;
77
78 {
79 // This can be trivially eliminated by replacing e1[x] with the err[] statement.
80 uint32 ne = 3;
81 for (uint32 x=1; x<_nErrorsAllowed; x++)
82 ne *= 3;
83
84 //fprintf(stderr, "Storing ne="uint32FMT" errors.\n", ne);
85
86 e1 = new uint64 [ne];
87 e2 = new uint64 [ne];
88 e3 = new uint64 [ne];
89 e4 = new uint64 [ne];
90 e5 = new uint64 [ne];
91 e6 = new uint64 [ne];
92
93 uint64 err[3] = { 0x5555555555555555llu, 0xaaaaaaaaaaaaaaaallu, 0xffffffffffffffffllu };
94
95 for (uint32 x=0; x<ne; x++) {
96 e1[x] = err[(x/ 1) % 3];
97 e2[x] = err[(x/ 3) % 3];
98 e3[x] = err[(x/ 9) % 3];
99 e4[x] = err[(x/ 27) % 3];
100 e5[x] = err[(x/ 81) % 3];
101 e6[x] = err[(x/243) % 3];
102 }
103 }
104
105
106 // Zero errors
107 strings[stringsLen++] = uint64ZERO;
108
109
110 // One error
111 if (1 <= _nErrorsAllowed) {
112 for (uint32 ai=0; ai<_merSizeInBases; ai++) {
113 totpat++;
114 toterr += 3;
115 m1 = 0x03llu << (ai * 2);
116
117 for (uint32 x=0; x<3; x++)
118 strings[stringsLen++] = HASH((m1 & e1[x]));
119 }
120
121 stringsLen = makeUnique(strings, stringsLen);
122 stringsLen = makeUnique(strings, stringsLen);
123 //dumpPatterns(strings, stringsLen, _tableSizeInBits);
124 //fprintf(stderr, "DONE1 totpat="uint64FMT" toterr="uint64FMT" stringsLen="uint32FMT"\n", totpat, toterr, stringsLen);
125 }
126
127
128 // Two errors
129 if (2 <= _nErrorsAllowed) {
130 for (uint32 ai=0; ai<_merSizeInBases; ai++)
131 for (uint32 bi=0; bi<ai; bi++) {
132 totpat++;
133 toterr += 9;
134 m1 = 0x03llu << (ai * 2);
135 m2 = 0x03llu << (bi * 2);
136
137 for (uint32 x=0; x<9; x++)
138 strings[stringsLen++] = HASH((m1 & e1[x]) ^ (m2 & e2[x]));
139 }
140
141 stringsLen = makeUnique(strings, stringsLen);
142 stringsLen = makeUnique(strings, stringsLen);
143 //dumpPatterns(strings, stringsLen, _tableSizeInBits);
144 //fprintf(stderr, "DONE2 totpat="uint64FMT" toterr="uint64FMT" stringsLen="uint32FMT"\n", totpat, toterr, stringsLen);
145 }
146
147
148 // Three errors
149 if (3 <= _nErrorsAllowed) {
150 for (uint32 ai=0; ai<_merSizeInBases; ai++)
151 for (uint32 bi=0; bi<ai; bi++)
152 for (uint32 ci=0; ci<bi; ci++) {
153 totpat++;
154 toterr += 27;
155 m1 = 0x03llu << (ai * 2);
156 m2 = 0x03llu << (bi * 2);
157 m3 = 0x03llu << (ci * 2);
158
159 for (uint32 x=0; x<27; x++)
160 strings[stringsLen++] = HASH((m1 & e1[x]) ^ (m2 & e2[x]) ^ (m3 & e3[x]));
161 }
162
163 stringsLen = makeUnique(strings, stringsLen);
164 stringsLen = makeUnique(strings, stringsLen);
165 //dumpPatterns(strings, stringsLen, _tableSizeInBits);
166 //fprintf(stderr, "DONE3 totpat="uint64FMT" toterr="uint64FMT" stringsLen="uint32FMT"\n", totpat, toterr, stringsLen);
167 }
168
169
170 // Four errors
171 if (4 <= _nErrorsAllowed) {
172 for (uint32 ai=0; ai<_merSizeInBases; ai++)
173 for (uint32 bi=0; bi<ai; bi++)
174 for (uint32 ci=0; ci<bi; ci++)
175 for (uint32 di=0; di<ci; di++) {
176 totpat++;
177 toterr += 81;
178 m1 = 0x03llu << (ai * 2);
179 m2 = 0x03llu << (bi * 2);
180 m3 = 0x03llu << (ci * 2);
181 m4 = 0x03llu << (di * 2);
182
183 for (uint32 x=0; x<81; x++)
184 strings[stringsLen++] = HASH((m1 & e1[x]) ^ (m2 & e2[x]) ^ (m3 & e3[x]) ^ (m4 & e4[x]));
185 }
186
187 stringsLen = makeUnique(strings, stringsLen);
188 stringsLen = makeUnique(strings, stringsLen);
189 //dumpPatterns(strings, stringsLen, _tableSizeInBits);
190 //fprintf(stderr, "DONE4 totpat="uint64FMT" toterr="uint64FMT" stringsLen="uint32FMT"\n", totpat, toterr, stringsLen);
191 }
192
193
194 // Five errors
195 if (5 <= _nErrorsAllowed) {
196 for (uint32 ai=0; ai<_merSizeInBases; ai++)
197 for (uint32 bi=0; bi<ai; bi++)
198 for (uint32 ci=0; ci<bi; ci++)
199 for (uint32 di=0; di<ci; di++)
200 for (uint32 ei=0; ei<di; ei++) {
201 totpat++;
202 toterr += 243;
203 m1 = 0x03llu << (ai * 2);
204 m2 = 0x03llu << (bi * 2);
205 m3 = 0x03llu << (ci * 2);
206 m4 = 0x03llu << (di * 2);
207 m5 = 0x03llu << (ei * 2);
208
209 if (stringsLen + 32000 >= stringsMax)
210 stringsLen = makeUnique(strings, stringsLen);
211
212 for (uint32 x=0; x<243; x++)
213 strings[stringsLen++] = HASH((m1 & e1[x]) ^ (m2 & e2[x]) ^ (m3 & e3[x]) ^ (m4 & e4[x]) ^ (m5 & e5[x]));
214 }
215
216 stringsLen = makeUnique(strings, stringsLen);
217 stringsLen = makeUnique(strings, stringsLen);
218 //dumpPatterns(strings, stringsLen, _tableSizeInBits);
219 //fprintf(stderr, "DONE5 totpat="uint64FMT" toterr="uint64FMT" stringsLen="uint32FMT"\n", totpat, toterr, stringsLen);
220 }
221
222
223 // Six errors
224 if (6 <= _nErrorsAllowed) {
225 for (uint32 ai=0; ai<_merSizeInBases; ai++)
226 for (uint32 bi=0; bi<ai; bi++)
227 for (uint32 ci=0; ci<bi; ci++)
228 for (uint32 di=0; di<ci; di++)
229 for (uint32 ei=0; ei<di; ei++)
230 for (uint32 fi=0; fi<ei; fi++) {
231 totpat++;
232 toterr += 729;
233 m1 = 0x03llu << (ai * 2);
234 m2 = 0x03llu << (bi * 2);
235 m3 = 0x03llu << (ci * 2);
236 m4 = 0x03llu << (di * 2);
237 m5 = 0x03llu << (ei * 2);
238 m6 = 0x03llu << (fi * 2);
239
240 if (stringsLen + 32000 >= stringsMax)
241 stringsLen = makeUnique(strings, stringsLen);
242
243 for (uint32 x=0; x<729; x++)
244 strings[stringsLen++] = HASH((m1 & e1[x]) ^ (m2 & e2[x]) ^ (m3 & e3[x]) ^ (m4 & e4[x]) ^ (m5 & e5[x]) ^ (m6 & e6[x]));
245 }
246
247 stringsLen = makeUnique(strings, stringsLen);
248 stringsLen = makeUnique(strings, stringsLen);
249 //dumpPatterns(strings, stringsLen, _tableSizeInBits);
250 //fprintf(stderr, "DONE6 totpat="uint64FMT" toterr="uint64FMT" stringsLen="uint32FMT"\n", totpat, toterr, stringsLen);
251 }
252
253
254 if (7 <= _nErrorsAllowed) {
255 fprintf(stderr, "Only 6 errors allowed.\n");
256 exit(1);
257 }
258
259 for (uint32 i=1; i<stringsLen; i++) {
260 assert((strings[i] & ~_hashMask) == 0);
261 assert(strings[i] != 0);
262 }
263
264 delete [] e1;
265 delete [] e2;
266 delete [] e3;
267 delete [] e4;
268 delete [] e5;
269 delete [] e6;
270
271 delete [] _hashedErrors;
272
273 _hashedErrorsLen = stringsLen;
274 _hashedErrorsMax = stringsLen;
275 _hashedErrors = new uint64 [_hashedErrorsLen];
276
277 memcpy(_hashedErrors, strings, sizeof(uint64) * _hashedErrorsLen);
278
279 delete [] strings;
280
281 #ifdef UNCOMPRESS_HASH_TABLE
282 // Cost is just bucket searching.
283 double work = (double)_hashedErrorsLen * approxMers / _tableSizeInEntries;
284 #else
285 // Cost is bucket searching + hash table lookups.
286 double work = (double)_hashedErrorsLen * approxMers / _tableSizeInEntries + 2.0 * _hashedErrorsLen;
287 #endif
288
289 //fprintf(stderr, "Built "uint32FMT" hashed errors at tableSize "uint32FMT" (work=%f.0).\n",
290 // _hashedErrorsLen,
291 // _tableSizeInBits,
292 // work);
293
294 //for (uint32 i=0; i<_hashedErrorsLen; i++)
295 // fprintf(stderr, "he["uint32FMTW(5)"] = "uint64HEX"\n", i, _hashedErrors[i]);
296
297 return(work);
298 }
299
300
301
302 // Returns hits with _AT_MOST_ numMismatches mistakes.
303 bool
304 positionDB::getUpToNMismatches(uint64 mer,
305 uint32 numMismatches,
306 uint64*& posn,
307 uint64& posnMax,
308 uint64& posnLen) {
309
310 PREFETCH(_hashedErrors); // Slightly better.
311
312 posnLen = 0;
313
314 if (_hashedErrors == 0L) {
315 fprintf(stderr, "ERROR: Nobody initialized getUpToNMismatches() by calling setUpMismatchMatcher().\n");
316 exit(1);
317 }
318
319 if (posnMax == 0) {
320 posnMax = 16384;
321 try {
322 posn = new uint64 [posnMax];
323 } catch (...) {
324 fprintf(stderr, "positionDB::getUpToNMismatches()-- Can't allocate space for initial positions, requested "uint64FMT" uint64's.\n", posnMax);
325 abort();
326 }
327 }
328
329 uint64 orig = HASH(mer);
330
331 // Optimization that didn't work. The idea was to compute all the
332 // hashes with errors, then sort to gain better cache locality in
333 // the lookups. The sort dominated.
334 //
335 // Another: Surprisingly, theq two getDecodedValue calls are faster
336 // than a single getDecodedValues.
337
338 for (uint32 e=0; e<_hashedErrorsLen; e++) {
339 uint64 hash = orig ^ _hashedErrors[e];
340 uint64 st, ed;
341
342 if (_hashTable_BP) {
343 st = getDecodedValue(_hashTable_BP, hash * _hashWidth, _hashWidth);
344 ed = getDecodedValue(_hashTable_BP, hash * _hashWidth + _hashWidth, _hashWidth);
345 } else {
346 st = _hashTable_FW[hash];
347 ed = _hashTable_FW[hash+1];
348 }
349
350 assert((_hashedErrors[e] & ~_hashMask) == 0);
351 assert((hash & ~_hashMask) == 0);
352
353 // Rebuild the mer from the hash and its check code.
354 //
355 // Compare the rebuilt mer and the original mer -- if there are
356 // exactly N errors, it's a hit! (if there are fewer than N,
357 // we'll find it when we look for N-1 errors).
358 //
359 // Before rebuilding, compute diffs on the chckBits only -- if
360 // things are wildly different (the usual case) we'll get
361 // enough difference here to abort. Remember, the chck bits
362 // are not encoded, they're an exact copy from the unhashed
363 // mer.
364
365 if (st != ed) {
366 for (uint64 i=ed-st, J=st * _wFin; i--; J += _wFin) {
367 uint64 chck = getDecodedValue(_buckets, J, _chckWidth);
368 uint64 diffs = chck ^ (mer & _mask2);
369 uint64 d1 = diffs & uint64NUMBER(0x5555555555555555);
370 uint64 d2 = diffs & uint64NUMBER(0xaaaaaaaaaaaaaaaa);
371 uint64 err = countNumberOfSetBits64(d1 | (d2 >> 1));
372
373 if (err <= numMismatches) {
374 diffs = REBUILD(hash, chck) ^ mer;
375 d1 = diffs & uint64NUMBER(0x5555555555555555);
376 d2 = diffs & uint64NUMBER(0xaaaaaaaaaaaaaaaa);
377 err = countNumberOfSetBits64(d1 | (d2 >> 1));
378
379 if (err <= numMismatches)
380 // err is junk, just need a parameter here
381 loadPositions(J, posn, posnMax, posnLen, err);
382 }
383 }
384 }
385 }
386
387 return(posnLen > 0);
388 }