GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 95.0% 651 / 0 / 685
Functions: 100.0% 7 / 0 / 7
Branches: 90.9% 399 / 0 / 439
libfprint/nbis/bozorth3/bozorth3.c
Line Branch Exec Source
1 /*******************************************************************************
2
3 License:
4 This software and/or related materials was developed at the National Institute
5 of Standards and Technology (NIST) by employees of the Federal Government
6 in the course of their official duties. Pursuant to title 17 Section 105
7 of the United States Code, this software is not subject to copyright
8 protection and is in the public domain.
9
10 This software and/or related materials have been determined to be not subject
11 to the EAR (see Part 734.3 of the EAR for exact details) because it is
12 a publicly available technology and software, and is freely distributed
13 to any interested party with no licensing requirements. Therefore, it is
14 permissible to distribute this software as a free download from the internet.
15
16 Disclaimer:
17 This software and/or related materials was developed to promote biometric
18 standards and biometric technology testing for the Federal Government
19 in accordance with the USA PATRIOT Act and the Enhanced Border Security
20 and Visa Entry Reform Act. Specific hardware and software products identified
21 in this software were used in order to perform the software development.
22 In no case does such identification imply recommendation or endorsement
23 by the National Institute of Standards and Technology, nor does it imply that
24 the products and equipment identified are necessarily the best available
25 for the purpose.
26
27 This software and/or related materials are provided "AS-IS" without warranty
28 of any kind including NO WARRANTY OF PERFORMANCE, MERCHANTABILITY,
29 NO WARRANTY OF NON-INFRINGEMENT OF ANY 3RD PARTY INTELLECTUAL PROPERTY
30 or FITNESS FOR A PARTICULAR PURPOSE or for any purpose whatsoever, for the
31 licensed product, however used. In no event shall NIST be liable for any
32 damages and/or costs, including but not limited to incidental or consequential
33 damages of any kind, including economic damage or injury to property and lost
34 profits, regardless of whether NIST shall be advised, have reason to know,
35 or in fact shall know of the possibility.
36
37 By using this software, you agree to bear all risk relating to quality,
38 use and performance of the software and/or related materials. You agree
39 to hold the Government harmless from any claim arising from your use
40 of the software.
41
42 *******************************************************************************/
43
44 /***********************************************************************
45 LIBRARY: FING - NIST Fingerprint Systems Utilities
46
47 FILE: BOZORTH3.C
48 ALGORITHM: Allan S. Bozorth (FBI)
49 MODIFICATIONS: Michael D. Garris (NIST)
50 Stan Janet (NIST)
51 DATE: 09/21/2004
52
53 Contains the "core" routines responsible for supporting the
54 Bozorth3 fingerprint matching algorithm.
55
56 ***********************************************************************
57
58 ROUTINES:
59 #cat: bz_comp - takes a set of minutiae (probe or gallery) and
60 #cat: compares/measures each minutia's {x,y,t} with every
61 #cat: other minutia's {x,y,t} in the set creating a table
62 #cat: of pairwise comparison entries
63 #cat: bz_find - trims sorted table of pairwise minutia comparisons to
64 #cat: a max distance of 75^2
65 #cat: bz_match - takes the two pairwise minutia comparison tables (a probe
66 #cat: table and a gallery table) and compiles a list of
67 #cat: all relatively "compatible" entries between the two
68 #cat: tables generating a match table
69 #cat: bz_match_score - takes a match table and traverses it looking for
70 #cat: a sufficiently long path (or a cluster of compatible paths)
71 #cat: of "linked" match table entries
72 #cat: the accumulation of which results in a match "score"
73 #cat: bz_sift - main routine handling the path linking and match table
74 #cat: traversal
75 #cat: bz_final_loop - (declared static) a final postprocess after
76 #cat: the main match table traversal which looks to combine
77 #cat: clusters of compatible paths
78
79 ***********************************************************************/
80
81 #include <stdio.h>
82 #include <bozorth.h>
83
84 /***********************************************************************/
85 35 void bz_comp(
86 int npoints, /* INPUT: # of points */
87 int xcol[ MAX_BOZORTH_MINUTIAE ], /* INPUT: x cordinates */
88 int ycol[ MAX_BOZORTH_MINUTIAE ], /* INPUT: y cordinates */
89 int thetacol[ MAX_BOZORTH_MINUTIAE ], /* INPUT: theta values */
90
91 int * ncomparisons, /* OUTPUT: number of pointwise comparisons */
92 int cols[][ COLS_SIZE_2 ], /* OUTPUT: pointwise comparison table */
93 int * colptrs[] /* INPUT and OUTPUT: sorted list of pointers to rows in cols[] */
94 )
95 {
96 35 int i, j, k;
97
98 35 int b;
99 35 int t;
100 35 int n;
101 35 int l;
102
103 35 int table_index;
104
105 35 int dx;
106 35 int dy;
107 35 int distance;
108
109 35 int theta_kj;
110 35 int beta_j;
111 35 int beta_k;
112
113 35 int * c;
114
115
116
117 35 c = &cols[0][0];
118
119 35 table_index = 0;
120
2/2
✓ Branch 48 → 3 taken 3073 times.
✓ Branch 48 → 49 taken 35 times.
 3108 for ( k = 0; k < npoints - 1; k++ ) {
121
2/2
✓ Branch 46 → 4 taken 118174 times.
✓ Branch 46 → 47 taken 1575 times.
 119749 for ( j = k + 1; j < npoints; j++ ) {
122
123
124
2/2
✓ Branch 4 → 5 taken 49350 times.
✓ Branch 4 → 7 taken 68824 times.
 118174 if ( thetacol[j] > 0 ) {
125
126
2/2
✓ Branch 5 → 6 taken 2114 times.
✓ Branch 5 → 9 taken 47236 times.
 49350 if ( thetacol[k] == thetacol[j] - 180 )
127 2114 continue;
128 } else {
129
130
2/2
✓ Branch 7 → 8 taken 2527 times.
✓ Branch 7 → 9 taken 66297 times.
 68824 if ( thetacol[k] == thetacol[j] + 180 )
131 2527 continue;
132 }
133
134
135 113533 dx = xcol[j] - xcol[k];
136 113533 dy = ycol[j] - ycol[k];
137 113533 distance = SQUARED(dx) + SQUARED(dy);
138
2/2
✓ Branch 9 → 10 taken 32669 times.
✓ Branch 9 → 12 taken 80864 times.
 113533 if ( distance > SQUARED(DM) ) {
139
2/2
✓ Branch 10 → 11 taken 31171 times.
✓ Branch 10 → 47 taken 1498 times.
 32669 if ( dx > DM )
140 break;
141 else
142 31171 continue;
143
144 }
145
146 /* The distance is in the range [ 0, 125^2 ] */
147
2/2
✓ Branch 12 → 13 taken 80199 times.
✓ Branch 12 → 17 taken 665 times.
 80864 if ( dx == 0 )
148 theta_kj = 90;
149 else {
150 80199 double dz;
151
152 80199 if ( 0 )
153 dz = ( 180.0F / PI_SINGLE ) * atanf( (float) -dy / (float) dx );
154 else
155 80199 dz = ( 180.0F / PI_SINGLE ) * atanf( (float) dy / (float) dx );
156
2/2
✓ Branch 13 → 14 taken 39816 times.
✓ Branch 13 → 15 taken 40383 times.
 80199 if ( dz < 0.0F )
157 39816 dz -= 0.5F;
158 else
159 40383 dz += 0.5F;
160 80199 theta_kj = (int) dz;
161 }
162
163
164 80864 beta_k = theta_kj - thetacol[k];
165
4/4
✓ Branch 17 → 18 taken 7931 times.
✓ Branch 17 → 19 taken 72933 times.
✓ Branch 19 → 20 taken 3619 times.
✓ Branch 19 → 21 taken 69314 times.
 80864 beta_k = IANGLE180(beta_k);
166
167 80864 beta_j = theta_kj - thetacol[j] + 180;
168
3/4
✓ Branch 21 → 22 taken 44324 times.
✓ Branch 21 → 23 taken 36540 times.
✗ Branch 23 → 24 not taken.
✓ Branch 23 → 25 taken 36540 times.
 80864 beta_j = IANGLE180(beta_j);
169
170
171
2/2
✓ Branch 25 → 26 taken 39886 times.
✓ Branch 25 → 27 taken 40978 times.
 80864 if ( beta_k < beta_j ) {
172 39886 *c++ = distance;
173 39886 *c++ = beta_k;
174 39886 *c++ = beta_j;
175 39886 *c++ = k+1;
176 39886 *c++ = j+1;
177 39886 *c++ = theta_kj;
178 } else {
179 40978 *c++ = distance;
180 40978 *c++ = beta_j;
181 40978 *c++ = beta_k;
182 40978 *c++ = k+1;
183 40978 *c++ = j+1;
184 40978 *c++ = theta_kj + 400;
185
186 }
187
188
189
190
191
192
193 80864 b = 0;
194 80864 t = table_index + 1;
195 80864 l = 1;
196 80864 n = -1; /* Init binary search state ... */
197
198
199
200
201
2/2
✓ Branch 37 → 29 taken 791973 times.
✓ Branch 37 → 38 taken 80864 times.
 872837 while ( t - b > 1 ) {
202 791973 int * midpoint;
203
204 791973 l = ( b + t ) / 2;
205 791973 midpoint = colptrs[l-1];
206
207
208
209
210
1/2
✓ Branch 33 → 30 taken 816907 times.
✗ Branch 33 → 34 not taken.
 816907 for ( i=0; i < 3; i++ ) {
211 816907 int dd, ff;
212
213 816907 dd = cols[table_index][i];
214
215 816907 ff = midpoint[i];
216
217
218
2/2
✓ Branch 30 → 31 taken 426818 times.
✓ Branch 30 → 34 taken 390089 times.
 816907 n = SENSE(dd,ff);
219
220
221 426818 if ( n < 0 ) {
222 t = l;
223 break;
224 }
225
2/2
✓ Branch 31 → 32 taken 24934 times.
✓ Branch 31 → 34 taken 401884 times.
 426818 if ( n > 0 ) {
226 b = l;
227 break;
228 }
229 }
230
231
1/2
✗ Branch 34 → 35 not taken.
✓ Branch 34 → 36 taken 791973 times.
 791973 if ( n == 0 ) {
232 ✗ n = 1;
233 ✗ b = l;
234 }
235 } /* END while */
236
237
2/2
✓ Branch 38 → 39 taken 35252 times.
✓ Branch 38 → 40 taken 45612 times.
 80864 if ( n == 1 )
238 35252 ++l;
239
240
241
242
243
2/2
✓ Branch 42 → 41 taken 52540572 times.
✓ Branch 42 → 43 taken 80864 times.
 52621436 for ( i = table_index; i >= l; --i )
244 52540572 colptrs[i] = colptrs[i-1];
245
246
247 80864 colptrs[l-1] = &cols[table_index][0];
248 80864 ++table_index;
249
250
251
1/2
✗ Branch 43 → 44 not taken.
✓ Branch 43 → 45 taken 80864 times.
 80864 if ( table_index == 19999 ) {
252 #ifndef NOVERBOSE
253 ✗ if ( 0 )
254 printf( "bz_comp(): breaking loop to avoid table overflow\n" );
255 #endif
256 ✗ goto COMP_END;
257 }
258
259 } /* END for j */
260
261 } /* END for k */
262
263 35 COMP_END:
264 35 *ncomparisons = table_index;
265
266 35 }
267
268 /***********************************************************************/
269 35 void bz_find(
270 int * xlim, /* INPUT: number of pointwise comparisons in table */
271 /* OUTPUT: determined insertion location (NOT ALWAYS SET) */
272 int * colpt[] /* INOUT: sorted list of pointers to rows in the pointwise comparison table */
273 )
274 {
275 35 int midpoint;
276 35 int top;
277 35 int bottom;
278 35 int state;
279 35 int distance;
280
281
282
283 /* binary search to locate the insertion location of a predefined distance in list of sorted distances */
284
285
286 35 bottom = 0;
287 35 top = *xlim + 1;
288 35 midpoint = 1;
289 35 state = -1;
290
291
2/2
✓ Branch 6 → 3 taken 413 times.
✓ Branch 6 → 7 taken 35 times.
 448 while ( top - bottom > 1 ) {
292 413 midpoint = ( bottom + top ) / 2;
293 413 distance = *colpt[ midpoint-1 ];
294
2/2
✓ Branch 3 → 4 taken 273 times.
✓ Branch 3 → 5 taken 140 times.
 413 state = SENSE_NEG_POS(FD,distance);
295 if ( state < 0 )
296 top = midpoint;
297 else {
298 273 bottom = midpoint;
299 }
300 }
301
302
2/2
✓ Branch 7 → 8 taken 28 times.
✓ Branch 7 → 9 taken 7 times.
 35 if ( state > -1 )
303 28 ++midpoint;
304
305
1/2
✓ Branch 9 → 10 taken 35 times.
✗ Branch 9 → 11 not taken.
 35 if ( midpoint < *xlim )
306 35 *xlim = midpoint;
307
308
309
310 35 }
311
312 /***********************************************************************/
313 /* Make room in RTP list at insertion point by shifting contents down the
314 list. Then insert the address of the current ROT row into desired
315 location */
316 /***********************************************************************/
317 static
318
319 51958 void rtp_insert( int * rtp[], int l, int idx, int * ptr )
320 {
321 51958 int shiftcount;
322 51958 int ** r1;
323 51958 int ** r2;
324
325
326 51958 r1 = &rtp[idx];
327 51958 r2 = r1 - 1;
328
329 51958 shiftcount = ( idx - l ) + 1;
330
2/2
✓ Branch 4 → 3 taken 30580338 times.
✓ Branch 4 → 5 taken 51958 times.
 30632296 while ( shiftcount-- > 0 ) {
331 30580338 *r1-- = *r2--;
332 }
333 51958 *r1 = ptr;
334 51958 }
335
336 /***********************************************************************/
337 /* Builds list of compatible edge pairs between the 2 Webs. */
338 /* The Edge pair DeltaThetaKJs and endpoints are sorted */
339 /* first on Subject's K, */
340 /* then On-File's J or K (depending), */
341 /* and lastly on Subject's J point index. */
342 /* Return value is the # of compatible edge pairs */
343 /***********************************************************************/
344 26 int bz_match(
345 int probe_ptrlist_len, /* INPUT: pruned length of Subject's pointer list */
346 int gallery_ptrlist_len /* INPUT: pruned length of On-File Record's pointer list */
347 )
348 {
349 26 int i; /* Temp index */
350 26 int ii; /* Temp index */
351 26 int edge_pair_index; /* Compatible edge pair index */
352 26 float dz; /* Delta difference and delta angle stats */
353 26 float fi; /* Distance limit based on factor TK */
354 26 int * ss; /* Subject's comparison stats row */
355 26 int * ff; /* On-File Record's comparison stats row */
356 26 int j; /* On-File Record's row index */
357 26 int k; /* Subject's row index */
358 26 int st; /* Starting On-File Record's row index */
359 26 int p1; /* Adjusted Subject's ThetaKJ, DeltaThetaKJs, K or J point index */
360 26 int p2; /* Adjusted On-File's ThetaKJ, RTP point index */
361 26 int n; /* ThetaKJ and binary search state variable */
362 26 int l; /* Midpoint of binary search */
363 26 int b; /* ThetaKJ state variable, and bottom of search range */
364 26 int t; /* Top of search range */
365
366 26 register int * rotptr;
367
368
369 #define ROT_SIZE_1 20000
370 #define ROT_SIZE_2 5
371
372 26 static int rot[ ROT_SIZE_1 ][ ROT_SIZE_2 ];
373
374
375 26 static int * rtp[ ROT_SIZE_1 ];
376
377
378
379
380 /* These now externally defined in bozorth.h */
381 /* extern int * scolpt[ SCOLPT_SIZE ]; INPUT */
382 /* extern int * fcolpt[ FCOLPT_SIZE ]; INPUT */
383 /* extern int colp[ COLP_SIZE_1 ][ COLP_SIZE_2 ]; OUTPUT */
384 /* extern int 0; */
385 /* extern FILE * stderr; */
386 /* extern char * get_progname( void ); */
387 /* extern char * get_probe_filename( void ); */
388 /* extern char * get_gallery_filename( void ); */
389
390
391
392
393
394 26 st = 1;
395 26 edge_pair_index = 0;
396 26 rotptr = &rot[0][0];
397
398 /* Foreach sorted edge in Subject's Web ... */
399
400
2/2
✓ Branch 43 → 3 taken 23206 times.
✓ Branch 43 → 44 taken 26 times.
 23232 for ( k = 1; k < probe_ptrlist_len; k++ ) {
401 23206 ss = scolpt[k-1];
402
403 /* Foreach sorted edge in On-File Record's Web ... */
404
405
2/2
✓ Branch 41 → 4 taken 4529278 times.
✓ Branch 41 → 42 taken 3916 times.
 4533194 for ( j = st; j <= gallery_ptrlist_len; j++ ) {
406 4529278 ff = fcolpt[j-1];
407 4529278 dz = *ff - *ss;
408
409 4529278 fi = ( 2.0F * TK ) * ( *ff + *ss );
410
411
412
413
414
415
416
417
418
2/2
✓ Branch 4 → 5 taken 4486938 times.
✓ Branch 4 → 6 taken 42340 times.
 4529278 if ( SQUARED(dz) > SQUARED(fi) ) {
419
2/2
✓ Branch 6 → 7 taken 23050 times.
✓ Branch 6 → 42 taken 19290 times.
 42340 if ( dz < 0 ) {
420
421 23050 st = j + 1;
422
423 23050 continue;
424 } else
425 break;
426
427
428 }
429
430
431
432
2/2
✓ Branch 11 → 8 taken 4879442 times.
✓ Branch 11 → 12 taken 51958 times.
 4931400 for ( i = 1; i < 3; i++ ) {
433 4879442 float dz_squared;
434
435 4879442 dz = *(ss+i) - *(ff+i);
436 4879442 dz_squared = SQUARED(dz);
437
438
439
440
441
3/4
✓ Branch 8 → 9 taken 4434980 times.
✓ Branch 8 → 10 taken 444462 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 12 taken 4434980 times.
 4879442 if ( dz_squared > TXS && dz_squared < CTXS )
442 break;
443 }
444
445
2/2
✓ Branch 12 → 13 taken 4434980 times.
✓ Branch 12 → 14 taken 51958 times.
 4486938 if ( i < 3 )
446 4434980 continue;
447
448
449
450
451
452
453
2/2
✓ Branch 14 → 15 taken 27326 times.
✓ Branch 14 → 16 taken 24632 times.
 51958 if ( *(ss+5) >= 220 ) {
454 27326 p1 = *(ss+5) - 580;
455 27326 n = 1;
456 } else {
457 p1 = *(ss+5);
458 n = 0;
459 }
460
461
462
2/2
✓ Branch 16 → 17 taken 27062 times.
✓ Branch 16 → 18 taken 24896 times.
 51958 if ( *(ff+5) >= 220 ) {
463 27062 p2 = *(ff+5) - 580;
464 27062 b = 1;
465 } else {
466 p2 = *(ff+5);
467 b = 0;
468 }
469
470 51958 p1 -= p2;
471
4/4
✓ Branch 18 → 19 taken 5602 times.
✓ Branch 18 → 20 taken 46356 times.
✓ Branch 20 → 21 taken 6256 times.
✓ Branch 20 → 22 taken 40100 times.
 51958 p1 = IANGLE180(p1);
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
2/2
✓ Branch 22 → 23 taken 19932 times.
✓ Branch 22 → 24 taken 32026 times.
 51958 if ( n != b ) {
497
498 19932 *rotptr++ = p1;
499 19932 *rotptr++ = *(ss+3);
500 19932 *rotptr++ = *(ss+4);
501
502 19932 *rotptr++ = *(ff+4);
503 19932 *rotptr++ = *(ff+3);
504 } else {
505 32026 *rotptr++ = p1;
506 32026 *rotptr++ = *(ss+3);
507 32026 *rotptr++ = *(ss+4);
508
509 32026 *rotptr++ = *(ff+3);
510 32026 *rotptr++ = *(ff+4);
511 }
512
513
514
515
516
517
518 51958 n = -1;
519 51958 l = 1;
520 51958 b = 0;
521 51958 t = edge_pair_index + 1;
522
2/2
✓ Branch 34 → 26 taken 502722 times.
✓ Branch 34 → 35 taken 51958 times.
 554680 while ( t - b > 1 ) {
523 502722 l = ( b + t ) / 2;
524
525
2/2
✓ Branch 30 → 27 taken 735932 times.
✓ Branch 30 → 31 taken 3166 times.
 739098 for ( i = 0; i < 3; i++ ) {
526 735932 static int ii_table[] = { 1, 3, 2 };
527
528 /* 1 = Subject's Kth, */
529 /* 3 = On-File's Jth or Kth (depending), */
530 /* 2 = Subject's Jth */
531
532 735932 ii = ii_table[i];
533 735932 p1 = rot[edge_pair_index][ii];
534 735932 p2 = *( rtp[l-1] + ii );
535
536
2/2
✓ Branch 27 → 28 taken 492806 times.
✓ Branch 27 → 31 taken 243126 times.
 735932 n = SENSE(p1,p2);
537
538 492806 if ( n < 0 ) {
539 t = l;
540 break;
541 }
542
2/2
✓ Branch 28 → 29 taken 236376 times.
✓ Branch 28 → 31 taken 256430 times.
 492806 if ( n > 0 ) {
543 b = l;
544 break;
545 }
546 }
547
548
2/2
✓ Branch 31 → 32 taken 3166 times.
✓ Branch 31 → 33 taken 499556 times.
 502722 if ( n == 0 ) {
549 3166 n = 1;
550 3166 b = l;
551 }
552 } /* END while() for binary search */
553
554
555
2/2
✓ Branch 35 → 36 taken 21474 times.
✓ Branch 35 → 37 taken 30484 times.
 51958 if ( n == 1 )
556 21474 ++l;
557
558 51958 rtp_insert( rtp, l, edge_pair_index, &rot[edge_pair_index][0] );
559 51958 ++edge_pair_index;
560
561
1/2
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 40 taken 51958 times.
 51958 if ( edge_pair_index == 19999 ) {
562 #ifndef NOVERBOSE
563 ✗ if ( 0 )
564 fprintf( stderr, "%s: bz_match(): WARNING: list is full, breaking loop early [p=%s; g=%s]\n",
565 get_progname(), get_probe_filename(), get_gallery_filename() );
566 #endif
567 ✗ goto END; /* break out if list exceeded */
568 }
569
570 } /* END FOR On-File (edge) distance */
571
572 } /* END FOR Subject (edge) distance */
573
574
575
576 26 END:
577 {
578 26 int * colp_ptr = &colp[0][0];
579
580
2/2
✓ Branch 50 → 46 taken 51958 times.
✓ Branch 50 → 51 taken 26 times.
 51984 for ( i = 0; i < edge_pair_index; i++ ) {
581
2/2
✓ Branch 48 → 47 taken 259790 times.
✓ Branch 48 → 49 taken 51958 times.
 311748 INT_COPY( colp_ptr, rtp[i], COLP_SIZE_2 );
582
583
584 }
585 }
586
587
588
589 26 return edge_pair_index; /* Return the number of compatible edge pairs stored into colp[][] */
590 }
591
592 /**************************************************************************/
593 /* These global arrays are declared "static" as they are only used */
594 /* between bz_match_score() & bz_final_loop() */
595 /**************************************************************************/
596 static int ct[ CT_SIZE ];
597 static int gct[ GCT_SIZE ];
598 static int ctt[ CTT_SIZE ];
599 static int ctp[ CTP_SIZE_1 ][ CTP_SIZE_2 ];
600 static int yy[ YY_SIZE_1 ][ YY_SIZE_2 ][ YY_SIZE_3 ];
601
602 static int bz_final_loop( int );
603
604 /**************************************************************************/
605 26 int bz_match_score(
606 int np,
607 struct xyt_struct * pstruct,
608 struct xyt_struct * gstruct
609 )
610 {
611 26 int kx, kq;
612 26 int ftt;
613 26 int tot;
614 26 int qh;
615 26 int tp;
616 26 int ll, jj, kk, n, t, b;
617 26 int k, i, j, ii, z;
618 26 int kz, l;
619 26 int p1, p2;
620 26 int dw, ww;
621 26 int match_score;
622 26 int qq_overflow = 0;
623 26 float fi;
624
625 /* These next 3 arrays originally declared global, but moved here */
626 /* locally because they are only used herein */
627 26 int rr[ RR_SIZE ];
628 26 int avn[ AVN_SIZE ];
629 26 int avv[ AVV_SIZE_1 ][ AVV_SIZE_2 ];
630
631 /* These now externally defined in bozorth.h */
632 /* extern FILE * stderr; */
633 /* extern char * get_progname( void ); */
634 /* extern char * get_probe_filename( void ); */
635 /* extern char * get_gallery_filename( void ); */
636
637
638
639
640
641
642
1/2
✓ Branch 2 → 3 taken 26 times.
✗ Branch 2 → 287 not taken.
 26 if ( pstruct->nrows < MIN_COMPUTABLE_BOZORTH_MINUTIAE ) {
643 #ifndef NOVERBOSE
644 if ( gstruct->nrows < MIN_COMPUTABLE_BOZORTH_MINUTIAE ) {
645 if ( 0 )
646 fprintf( stderr, "%s: bz_match_score(): both probe and gallery file have too few minutiae (%d,%d) to compute a real Bozorth match score; min. is %d [p=%s; g=%s]\n",
647 get_progname(),
648 pstruct->nrows, gstruct->nrows, MIN_COMPUTABLE_BOZORTH_MINUTIAE,
649 get_probe_filename(), get_gallery_filename() );
650 } else {
651 if ( 0 )
652 fprintf( stderr, "%s: bz_match_score(): probe file has too few minutiae (%d) to compute a real Bozorth match score; min. is %d [p=%s; g=%s]\n",
653 get_progname(),
654 pstruct->nrows, MIN_COMPUTABLE_BOZORTH_MINUTIAE,
655 get_probe_filename(), get_gallery_filename() );
656 }
657 #endif
658 return ZERO_MATCH_SCORE;
659 }
660
661
662
663
1/2
✓ Branch 3 → 5 taken 26 times.
✗ Branch 3 → 287 not taken.
 26 if ( gstruct->nrows < MIN_COMPUTABLE_BOZORTH_MINUTIAE ) {
664 #ifndef NOVERBOSE
665 if ( 0 )
666 fprintf( stderr, "%s: bz_match_score(): gallery file has too few minutiae (%d) to compute a real Bozorth match score; min. is %d [p=%s; g=%s]\n",
667 get_progname(),
668 gstruct->nrows, MIN_COMPUTABLE_BOZORTH_MINUTIAE,
669 get_probe_filename(), get_gallery_filename() );
670 #endif
671 return ZERO_MATCH_SCORE;
672 }
673
674
675
676
677
678
679
680
681
682 /* initialize tables to 0's */
683
2/2
✓ Branch 5 → 4 taken 104000 times.
✓ Branch 5 → 7 taken 26 times.
 104026 INT_SET( (int *) &yl, YL_SIZE_1 * YL_SIZE_2, 0 );
684
685
686
687
2/2
✓ Branch 7 → 6 taken 520000 times.
✓ Branch 7 → 9 taken 26 times.
 520026 INT_SET( (int *) &sc, SC_SIZE, 0 );
688
2/2
✓ Branch 9 → 8 taken 520000 times.
✓ Branch 9 → 11 taken 26 times.
 520026 INT_SET( (int *) &cp, CP_SIZE, 0 );
689
2/2
✓ Branch 11 → 10 taken 520000 times.
✓ Branch 11 → 13 taken 26 times.
 520026 INT_SET( (int *) &rp, RP_SIZE, 0 );
690
2/2
✓ Branch 13 → 12 taken 520000 times.
✓ Branch 13 → 15 taken 26 times.
 520026 INT_SET( (int *) &tq, TQ_SIZE, 0 );
691
2/2
✓ Branch 15 → 14 taken 520000 times.
✓ Branch 15 → 17 taken 26 times.
 520026 INT_SET( (int *) &rq, RQ_SIZE, 0 );
692
2/2
✓ Branch 17 → 16 taken 520000 times.
✓ Branch 17 → 19 taken 26 times.
 520026 INT_SET( (int *) &zz, ZZ_SIZE, 1000 ); /* zz[] initialized to 1000's */
693
694
2/2
✓ Branch 19 → 18 taken 130 times.
✓ Branch 19 → 20 taken 26 times.
 156 INT_SET( (int *) &avn, AVN_SIZE, 0 ); /* avn[0...4] <== 0; */
695
696
697
698
699
700 26 tp = 0;
701 26 p1 = 0;
702 26 tot = 0;
703 26 ftt = 0;
704 26 match_score = 0;
705
706
2/2
✓ Branch 283 → 21 taken 51932 times.
✓ Branch 283 → 284 taken 26 times.
 51958 for ( k = 0; k < np - 1; k++ ) {
707 /* printf( "compute(): looping with k=%d\n", k ); */
708
709
2/2
✓ Branch 21 → 22 taken 29132 times.
✓ Branch 21 → 23 taken 22800 times.
 51932 if ( sc[k] ) /* If SC counter for current pair already incremented ... */
710 29132 continue; /* Skip to next pair */
711
712
713 22800 i = colp[k][1];
714 22800 t = colp[k][3];
715
716
717
718
719 22800 qq[0] = i;
720 22800 rq[t-1] = i;
721 22800 tq[i-1] = t;
722
723
724 22800 ww = 0;
725 22800 dw = 0;
726
727 48570 do {
728 48570 ftt++;
729 48570 tot = 0;
730 48570 qh = 1;
731 48570 kx = k;
732
733
734
735
736 86532 do {
737
738
739
740
741
742
743
744
745
746 86532 kz = colp[kx][2];
747 86532 l = colp[kx][4];
748 86532 kx++;
749 86532 bz_sift( &ww, kz, &qh, l, kx, ftt, &tot, &qq_overflow );
750
1/2
✗ Branch 26 → 27 not taken.
✓ Branch 26 → 32 taken 86532 times.
 86532 if ( qq_overflow ) {
751 ✗ fprintf( stderr, "%s: WARNING: bz_match_score(): qq[] overflow from bz_sift() #1 [p=%s; g=%s]\n",
752 get_progname(), get_probe_filename(), get_gallery_filename() );
753 ✗ return QQ_OVERFLOW_SCORE;
754 }
755
756 #ifndef NOVERBOSE
757 86532 if ( 0 )
758 printf( "x1 %d %d %d %d %d %d\n", kx, colp[kx][0], colp[kx][1], colp[kx][2], colp[kx][3], colp[kx][4] );
759 #endif
760
761
3/4
✓ Branch 32 → 33 taken 48570 times.
✓ Branch 32 → 34 taken 37962 times.
✓ Branch 34 → 25 taken 37962 times.
✗ Branch 34 → 33 not taken.
 86532 } while ( colp[kx][3] == colp[k][3] && colp[kx][1] == colp[k][1] );
762 /* While the startpoints of lookahead edge pairs are the same as the starting points of the */
763 /* current pair, set KQ to lookahead edge pair index where above bz_sift() loop left off */
764
765 kq = kx;
766
767
2/2
✓ Branch 89 → 58 taken 1670712 times.
✓ Branch 89 → 90 taken 48570 times.
 1719282 for ( j = 1; j < qh; j++ ) {
768 ✗ for ( i = kq; i < np; i++ ) {
769
770 ✗ for ( z = 1; z < 3; z++ ) {
771 ✗ if ( z == 1 ) {
772 ✗ if ( (j+1) > QQ_SIZE ) {
773 ✗ fprintf( stderr, "%s: WARNING: bz_match_score(): qq[] overflow #1 in bozorth3(); j-1 is %d [p=%s; g=%s]\n",
774 get_progname(), j-1, get_probe_filename(), get_gallery_filename() );
775 ✗ return QQ_OVERFLOW_SCORE;
776 }
777 ✗ p1 = qq[j];
778 } else {
779 61951490 p1 = tq[p1-1];
780
781 }
782
783
784
785
786
787
788 ✗ if ( colp[i][2*z] != p1 )
789 break;
790 }
791
792
793 ✗ if ( z == 3 ) {
794 20762344 z = colp[i][1];
795 20762344 l = colp[i][3];
796
797
798
799
4/4
✓ Branch 48 → 49 taken 20725524 times.
✓ Branch 48 → 57 taken 36820 times.
✓ Branch 49 → 50 taken 20450566 times.
✓ Branch 49 → 57 taken 274958 times.
 20762344 if ( z != colp[k][1] && l != colp[k][3] ) {
800 20450566 kx = i + 1;
801 20450566 bz_sift( &ww, z, &qh, l, kx, ftt, &tot, &qq_overflow );
802
1/2
✗ Branch 51 → 52 not taken.
✓ Branch 51 → 57 taken 20450566 times.
 20450566 if ( qq_overflow ) {
803 ✗ fprintf( stderr, "%s: WARNING: bz_match_score(): qq[] overflow from bz_sift() #2 [p=%s; g=%s]\n",
804 get_progname(), get_probe_filename(), get_gallery_filename() );
805 ✗ return QQ_OVERFLOW_SCORE;
806 }
807 }
808 }
809 } /* END for i */
810
811
812
813 /* Done looking ahead for current j */
814
815
816
817
818
819 1670712 t = np + 1;
820 1670712 b = kq;
821
822
2/2
✓ Branch 87 → 60 taken 12565196 times.
✓ Branch 87 → 88 taken 128168 times.
 12693364 while ( t - b > 1 ) {
823 12565196 l = ( b + t ) / 2;
824
825
2/2
✓ Branch 73 → 61 taken 15889750 times.
✓ Branch 73 → 74 taken 1542544 times.
 17432294 for ( i = 1; i < 3; i++ ) {
826
827
2/2
✓ Branch 61 → 62 taken 12565196 times.
✓ Branch 61 → 69 taken 3324554 times.
 15889750 if ( i == 1 ) {
828
1/2
✗ Branch 62 → 63 not taken.
✓ Branch 62 → 68 taken 12565196 times.
 12565196 if ( (j+1) > QQ_SIZE ) {
829 ✗ fprintf( stderr, "%s: WARNING: bz_match_score(): qq[] overflow #2 in bozorth3(); j-1 is %d [p=%s; g=%s]\n",
830 get_progname(), j-1, get_probe_filename(), get_gallery_filename() );
831 ✗ return QQ_OVERFLOW_SCORE;
832 }
833 12565196 p1 = qq[j];
834 } else {
835 3324554 p1 = tq[p1-1];
836 }
837
838
839
840 15889750 p2 = colp[l-1][i*2-1];
841
842
2/2
✓ Branch 70 → 71 taken 11795618 times.
✓ Branch 70 → 74 taken 4094132 times.
 15889750 n = SENSE(p1,p2);
843
844 11795618 if ( n < 0 ) {
845 t = l;
846 break;
847 }
848
2/2
✓ Branch 71 → 72 taken 4867098 times.
✓ Branch 71 → 74 taken 6928520 times.
 11795618 if ( n > 0 ) {
849 b = l;
850 break;
851 }
852 }
853
854
2/2
✓ Branch 74 → 75 taken 1542544 times.
✓ Branch 74 → 87 taken 11022652 times.
 12565196 if ( n == 0 ) {
855
856
857
858
859
860
861 /* Locates the head of consecutive sequence of edge pairs all having the same starting Subject and On-File edgepoints */
862
3/4
✓ Branch 75 → 76 taken 8470262 times.
✓ Branch 75 → 77 taken 1542544 times.
✓ Branch 76 → 75 taken 8470262 times.
✗ Branch 76 → 77 not taken.
 10012806 while ( colp[l-2][3] == p2 && colp[l-2][1] == colp[l-1][1] )
863 l--;
864
865 1542544 kx = l - 1;
866
867
868 18764554 do {
869 18764554 kz = colp[kx][2];
870 18764554 l = colp[kx][4];
871 18764554 kx++;
872 18764554 bz_sift( &ww, kz, &qh, l, kx, ftt, &tot, &qq_overflow );
873
1/2
✗ Branch 79 → 80 not taken.
✓ Branch 79 → 85 taken 18764554 times.
 18764554 if ( qq_overflow ) {
874 ✗ fprintf( stderr, "%s: WARNING: bz_match_score(): qq[] overflow from bz_sift() #3 [p=%s; g=%s]\n",
875 get_progname(), get_probe_filename(), get_gallery_filename() );
876 ✗ return QQ_OVERFLOW_SCORE;
877 }
878
3/4
✓ Branch 85 → 86 taken 17222010 times.
✓ Branch 85 → 88 taken 1542544 times.
✓ Branch 86 → 78 taken 17222010 times.
✗ Branch 86 → 88 not taken.
 18764554 } while ( colp[kx][3] == p2 && colp[kx][1] == colp[kx-1][1] );
879
880 break;
881 } /* END if ( n == 0 ) */
882
883 } /* END while */
884
885 } /* END for j */
886
887
888
889
890
2/2
✓ Branch 90 → 95 taken 17160 times.
✓ Branch 90 → 114 taken 31410 times.
 48570 if ( tot >= MSTR ) {
891 jj = 0;
892 kk = 0;
893 n = 0;
894 l = 0;
895
896
2/2
✓ Branch 95 → 91 taken 1638588 times.
✓ Branch 95 → 96 taken 17160 times.
 1655748 for ( i = 0; i < tot; i++ ) {
897
898
899 1638588 int colp_value = colp[ bz_y[i]-1 ][0];
900
2/2
✓ Branch 91 → 92 taken 123972 times.
✓ Branch 91 → 93 taken 1514616 times.
 1638588 if ( colp_value < 0 ) {
901 123972 kk += colp_value;
902 123972 n++;
903 } else {
904 1514616 jj += colp_value;
905 1514616 l++;
906 }
907 }
908
909
910
2/2
✓ Branch 96 → 97 taken 12218 times.
✓ Branch 96 → 98 taken 4942 times.
 17160 if ( n == 0 ) {
911 n = 1;
912 12218 } else if ( l == 0 ) {
913 l = 1;
914 }
915
916
917
918 17160 fi = (float) jj / (float) l - (float) kk / (float) n;
919
920
2/2
✓ Branch 98 → 99 taken 172 times.
✓ Branch 98 → 101 taken 16988 times.
 17160 if ( fi > 180.0F ) {
921 172 fi = ( jj + kk + n * 360 ) / (float) tot;
922
2/2
✓ Branch 99 → 100 taken 74 times.
✓ Branch 99 → 102 taken 98 times.
 172 if ( fi > 180.0F )
923 74 fi -= 360.0F;
924 } else {
925 16988 fi = ( jj + kk ) / (float) tot;
926 }
927
928
2/2
✓ Branch 102 → 103 taken 9678 times.
✓ Branch 102 → 104 taken 7482 times.
 17160 jj = ROUND(fi);
929
2/2
✓ Branch 105 → 106 taken 14 times.
✓ Branch 105 → 107 taken 17146 times.
 17160 if ( jj <= -180 )
930 14 jj += 360;
931
932
933
934 17160 kk = 0;
935
2/2
✓ Branch 112 → 108 taken 1638588 times.
✓ Branch 112 → 113 taken 17160 times.
 1655748 for ( i = 0; i < tot; i++ ) {
936 1638588 int diff = colp[ bz_y[i]-1 ][0] - jj;
937 1638588 j = SQUARED( diff );
938
939
940
941
942
2/2
✓ Branch 108 → 109 taken 35240 times.
✓ Branch 108 → 110 taken 1603348 times.
 1638588 if ( j > TXS && j < CTXS )
943 35240 kk++;
944 else
945 1603348 bz_y[i-kk] = bz_y[i];
946 } /* END FOR i */
947
948 17160 tot -= kk; /* Adjust the total edge pairs TOT based on # of edge pairs skipped */
949
950 } /* END if ( tot >= MSTR ) */
951
952
953
954
955
2/2
✓ Branch 114 → 115 taken 31898 times.
✓ Branch 114 → 146 taken 16672 times.
 48570 if ( tot < MSTR ) {
956
957
958
959
960
2/2
✓ Branch 119 → 116 taken 32656 times.
✓ Branch 119 → 231 taken 31898 times.
 64554 for ( i = tot-1 ; i >= 0; i-- ) {
961 32656 int idx = bz_y[i] - 1;
962
2/2
✓ Branch 116 → 117 taken 7174 times.
✓ Branch 116 → 118 taken 25482 times.
 32656 if ( rk[idx] == 0 ) {
963 sc[idx] = -1;
964 } else {
965 7174 sc[idx] = rk[idx];
966 }
967 }
968 ftt--;
969
970 } else { /* tot >= MSTR */
971 /* Otherwise size of TOT group (seq. of TOT indices stored in Y) is large enough to analyze */
972
973 int pa = 0;
974 int pb = 0;
975 int pc = 0;
976 int pd = 0;
977
978
2/2
✓ Branch 146 → 120 taken 1602436 times.
✓ Branch 146 → 147 taken 16672 times.
 1619108 for ( i = 0; i < tot; i++ ) {
979 1602436 int idx = bz_y[i] - 1;
980
2/2
✓ Branch 128 → 121 taken 4807308 times.
✓ Branch 128 → 144 taken 1602436 times.
 6409744 for ( ii = 1; ii < 4; ii++ ) {
981
982
983
984
985 4807308 kk = ( SQUARED(ii) - ii + 2 ) / 2 - 1;
986
987
988
989
990 4807308 jj = colp[idx][kk];
991
992
3/3
✓ Branch 121 → 122 taken 1602436 times.
✓ Branch 121 → 125 taken 1602436 times.
✓ Branch 121 → 126 taken 1602436 times.
 4807308 switch ( ii ) {
993 1602436 case 1:
994
2/2
✓ Branch 122 → 123 taken 101626 times.
✓ Branch 122 → 124 taken 1500810 times.
 1602436 if ( colp[idx][0] < 0 ) {
995 101626 pd += colp[idx][0];
996 101626 pb++;
997 } else {
998 1500810 pa += colp[idx][0];
999 1500810 pc++;
1000 }
1001 break;
1002 1602436 case 2:
1003 1602436 avn[ii-1] += pstruct->xcol[jj-1];
1004 1602436 avn[ii] += pstruct->ycol[jj-1];
1005 1602436 break;
1006 1602436 default:
1007 1602436 avn[ii] += gstruct->xcol[jj-1];
1008 1602436 avn[ii+1] += gstruct->ycol[jj-1];
1009 1602436 break;
1010 } /* switch */
1011 } /* END for ii = [1..3] */
1012
1013
2/2
✓ Branch 144 → 142 taken 3204872 times.
✓ Branch 144 → 145 taken 1602436 times.
 4807308 for ( ii = 0; ii < 2; ii++ ) {
1014 n = -1;
1015 l = 1;
1016
1017
2/2
✓ Branch 142 → 129 taken 6409744 times.
✓ Branch 142 → 143 taken 3204872 times.
 9614616 for ( jj = 1; jj < 3; jj++ ) {
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028 6409744 p1 = colp[idx][ 2 * ii + jj ];
1029
1030
1031 6409744 b = 0;
1032 6409744 t = yl[ii][tp] + 1;
1033
1034
2/2
✓ Branch 133 → 130 taken 29604380 times.
✓ Branch 133 → 134 taken 614866 times.
 30219246 while ( t - b > 1 ) {
1035 29604380 l = ( b + t ) / 2;
1036 29604380 p2 = yy[l-1][ii][tp];
1037
2/2
✓ Branch 130 → 131 taken 20013654 times.
✓ Branch 130 → 132 taken 9590726 times.
 29604380 n = SENSE(p1,p2);
1038
1039 20013654 if ( n < 0 ) {
1040 t = l;
1041 } else {
1042
2/2
✓ Branch 131 → 132 taken 14218776 times.
✓ Branch 131 → 134 taken 5794878 times.
 20013654 if ( n > 0 ) {
1043 b = l;
1044 } else {
1045 break;
1046 }
1047 }
1048 } /* END WHILE */
1049
1050
2/2
✓ Branch 134 → 135 taken 614866 times.
✓ Branch 134 → 141 taken 5794878 times.
 6409744 if ( n != 0 ) {
1051
2/2
✓ Branch 135 → 136 taken 310172 times.
✓ Branch 135 → 137 taken 304694 times.
 614866 if ( n == 1 )
1052 310172 ++l;
1053
1054
2/2
✓ Branch 139 → 138 taken 4195068 times.
✓ Branch 139 → 140 taken 614866 times.
 4809934 for ( kk = yl[ii][tp]; kk >= l; --kk ) {
1055 4195068 yy[kk][ii][tp] = yy[kk-1][ii][tp];
1056 }
1057
1058 614866 ++yl[ii][tp];
1059 614866 yy[l-1][ii][tp] = p1;
1060
1061
1062 } /* END if ( n != 0 ) */
1063
1064 /* Otherwise, edgepoint already stored in YY */
1065
1066 } /* END FOR jj in [1,2] */
1067 } /* END FOR ii in [0,1] */
1068 } /* END FOR i */
1069
1070
2/2
✓ Branch 147 → 148 taken 11276 times.
✓ Branch 147 → 149 taken 5396 times.
 16672 if ( pb == 0 ) {
1071 pb = 1;
1072 11276 } else if ( pc == 0 ) {
1073 pc = 1;
1074 }
1075
1076
1077
1078 16672 fi = (float) pa / (float) pc - (float) pd / (float) pb;
1079
2/2
✓ Branch 149 → 150 taken 120 times.
✓ Branch 149 → 152 taken 16552 times.
 16672 if ( fi > 180.0F ) {
1080
1081 120 fi = ( pa + pd + pb * 360 ) / (float) tot;
1082
2/2
✓ Branch 150 → 151 taken 50 times.
✓ Branch 150 → 153 taken 70 times.
 120 if ( fi > 180.0F )
1083 50 fi -= 360.0F;
1084 } else {
1085 16552 fi = ( pa + pd ) / (float) tot;
1086 }
1087
1088
2/2
✓ Branch 153 → 154 taken 9236 times.
✓ Branch 153 → 155 taken 7436 times.
 16672 pa = ROUND(fi);
1089
2/2
✓ Branch 156 → 157 taken 18 times.
✓ Branch 156 → 158 taken 16654 times.
 16672 if ( pa <= -180 )
1090 18 pa += 360;
1091
1092
1093
1094 16672 avv[tp][0] = pa;
1095
1096
2/2
✓ Branch 160 → 159 taken 66688 times.
✓ Branch 160 → 161 taken 16672 times.
 83360 for ( ii = 1; ii < 5; ii++ ) {
1097 66688 avv[tp][ii] = avn[ii] / tot;
1098 66688 avn[ii] = 0;
1099 }
1100
1101 16672 ct[tp] = tot;
1102 16672 gct[tp] = tot;
1103
1104 16672 if ( tot > match_score ) /* If current TOT > match_score ... */
1105 match_score = tot; /* Keep track of max TOT in match_score */
1106
1107 16672 ctt[tp] = 0; /* Init CTT[TP] to 0 */
1108 16672 ctp[tp][0] = tp; /* Store TP into CTP */
1109
1110
2/2
✓ Branch 230 → 162 taken 9619052 times.
✓ Branch 230 → 231 taken 16672 times.
 9635724 for ( ii = 0; ii < tp; ii++ ) {
1111 9619052 int found;
1112 9619052 int diff;
1113
1114 9619052 int * avv_tp_ptr = &avv[tp][0];
1115 9619052 int * avv_ii_ptr = &avv[ii][0];
1116 9619052 diff = *avv_tp_ptr++ - *avv_ii_ptr++;
1117 9619052 j = SQUARED( diff );
1118
1119
1120
1121
1122
1123
1124
2/2
✓ Branch 162 → 163 taken 6995822 times.
✓ Branch 162 → 164 taken 2623230 times.
 9619052 if ( j > TXS && j < CTXS )
1125 6995822 continue;
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135 2623230 ll = *avv_tp_ptr++ - *avv_ii_ptr++;
1136 2623230 jj = *avv_tp_ptr++ - *avv_ii_ptr++;
1137 2623230 kk = *avv_tp_ptr++ - *avv_ii_ptr++;
1138 2623230 j = *avv_tp_ptr++ - *avv_ii_ptr++;
1139
1140 {
1141 2623230 float tt, ai, dz;
1142
1143 2623230 tt = (float) (SQUARED(ll) + SQUARED(jj));
1144 2623230 ai = (float) (SQUARED(j) + SQUARED(kk));
1145
1146 2623230 fi = ( 2.0F * TK ) * ( tt + ai );
1147 2623230 dz = tt - ai;
1148
1149
1150
2/2
✓ Branch 164 → 165 taken 1052268 times.
✓ Branch 164 → 166 taken 1570962 times.
 2623230 if ( SQUARED(dz) > SQUARED(fi) )
1151 1052268 continue;
1152 }
1153
1154
1155
1156
2/2
✓ Branch 166 → 167 taken 1513922 times.
✓ Branch 166 → 176 taken 57040 times.
 1570962 if ( ll ) {
1157
1158 1513922 if ( 0 )
1159 fi = ( 180.0F / PI_SINGLE ) * atanf( (float) -jj / (float) ll );
1160 else
1161 1513922 fi = ( 180.0F / PI_SINGLE ) * atanf( (float) jj / (float) ll );
1162
2/2
✓ Branch 167 → 168 taken 1019062 times.
✓ Branch 167 → 171 taken 494860 times.
 1513922 if ( fi < 0.0F ) {
1163
2/2
✓ Branch 168 → 169 taken 176282 times.
✓ Branch 168 → 170 taken 842780 times.
 1019062 if ( ll < 0 )
1164 176282 fi += 180.5F;
1165 else
1166 842780 fi -= 0.5F;
1167 } else {
1168
2/2
✓ Branch 171 → 172 taken 144696 times.
✓ Branch 171 → 173 taken 350164 times.
 494860 if ( ll < 0 )
1169 144696 fi -= 180.5F;
1170 else
1171 350164 fi += 0.5F;
1172 }
1173 1513922 jj = (int) fi;
1174
2/2
✓ Branch 174 → 175 taken 6702 times.
✓ Branch 174 → 178 taken 1507220 times.
 1513922 if ( jj <= -180 )
1175 6702 jj += 360;
1176 } else {
1177
1178 57040 if ( 0 ) {
1179 if ( jj > 0 )
1180 jj = -90;
1181 else
1182 jj = 90;
1183 } else {
1184
2/2
✓ Branch 176 → 177 taken 31500 times.
✓ Branch 176 → 178 taken 25540 times.
 57040 if ( jj > 0 )
1185 jj = 90;
1186 else
1187 31500 jj = -90;
1188 }
1189 }
1190
1191
1192
1193
2/2
✓ Branch 178 → 179 taken 1519446 times.
✓ Branch 178 → 188 taken 51516 times.
 1570962 if ( kk ) {
1194
1195 1519446 if ( 0 )
1196 fi = ( 180.0F / PI_SINGLE ) * atanf( (float) -j / (float) kk );
1197 else
1198 1519446 fi = ( 180.0F / PI_SINGLE ) * atanf( (float) j / (float) kk );
1199
2/2
✓ Branch 179 → 180 taken 991810 times.
✓ Branch 179 → 183 taken 527636 times.
 1519446 if ( fi < 0.0F ) {
1200
2/2
✓ Branch 180 → 181 taken 214244 times.
✓ Branch 180 → 182 taken 777566 times.
 991810 if ( kk < 0 )
1201 214244 fi += 180.5F;
1202 else
1203 777566 fi -= 0.5F;
1204 } else {
1205
2/2
✓ Branch 183 → 184 taken 208862 times.
✓ Branch 183 → 185 taken 318774 times.
 527636 if ( kk < 0 )
1206 208862 fi -= 180.5F;
1207 else
1208 318774 fi += 0.5F;
1209 }
1210 1519446 j = (int) fi;
1211
2/2
✓ Branch 186 → 187 taken 7010 times.
✓ Branch 186 → 190 taken 1512436 times.
 1519446 if ( j <= -180 )
1212 7010 j += 360;
1213 } else {
1214
1215 51516 if ( 0 ) {
1216 if ( j > 0 )
1217 j = -90;
1218 else
1219 j = 90;
1220 } else {
1221
2/2
✓ Branch 188 → 189 taken 28828 times.
✓ Branch 188 → 190 taken 22688 times.
 51516 if ( j > 0 )
1222 j = 90;
1223 else
1224 28828 j = -90;
1225 }
1226 }
1227
1228
1229
1230
1231
1232 1570962 pa = 0;
1233 1570962 pb = 0;
1234 1570962 pc = 0;
1235 1570962 pd = 0;
1236
1237
2/2
✓ Branch 190 → 191 taken 1423848 times.
✓ Branch 190 → 192 taken 147114 times.
 1570962 if ( avv[tp][0] < 0 ) {
1238 pd += avv[tp][0];
1239 pb++;
1240 } else {
1241 1423848 pa += avv[tp][0];
1242 1423848 pc++;
1243 }
1244
1245
2/2
✓ Branch 192 → 193 taken 148726 times.
✓ Branch 192 → 194 taken 1422236 times.
 1570962 if ( avv[ii][0] < 0 ) {
1246 148726 pd += avv[ii][0];
1247 148726 pb++;
1248 } else {
1249 1422236 pa += avv[ii][0];
1250 1422236 pc++;
1251 }
1252
1253
2/2
✓ Branch 194 → 195 taken 59326 times.
✓ Branch 194 → 196 taken 1362910 times.
 1570962 if ( pb == 0 ) {
1254 pb = 1;
1255 208052 } else if ( pc == 0 ) {
1256 pc = 1;
1257 }
1258
1259
1260
1261 1570962 fi = (float) pa / (float) pc - (float) pd / (float) pb;
1262
1263
2/2
✓ Branch 196 → 197 taken 190 times.
✓ Branch 196 → 199 taken 1570772 times.
 1570962 if ( fi > 180.0F ) {
1264 190 fi = ( pa + pd + pb * 360 ) / 2.0F;
1265
2/2
✓ Branch 197 → 198 taken 166 times.
✓ Branch 197 → 200 taken 24 times.
 190 if ( fi > 180.0F )
1266 166 fi -= 360.0F;
1267 } else {
1268 1570772 fi = ( pa + pd ) / 2.0F;
1269 }
1270
1271
2/2
✓ Branch 200 → 201 taken 205516 times.
✓ Branch 200 → 202 taken 1365446 times.
 1570962 pb = ROUND(fi);
1272
2/2
✓ Branch 203 → 204 taken 30 times.
✓ Branch 203 → 205 taken 1570932 times.
 1570962 if ( pb <= -180 )
1273 30 pb += 360;
1274
1275
1276
1277
1278
1279 1570962 pa = jj - j;
1280
4/4
✓ Branch 205 → 206 taken 9100 times.
✓ Branch 205 → 207 taken 1561862 times.
✓ Branch 207 → 208 taken 6852 times.
✓ Branch 207 → 209 taken 1555010 times.
 1570962 pa = IANGLE180(pa);
1281 1570962 kk = SQUARED(pb-pa);
1282
1283
1284
1285
1286 /* Was: if ( SQUARED(kk) > TXS && kk < CTXS ) : assume typo */
1287
2/2
✓ Branch 209 → 210 taken 269860 times.
✓ Branch 209 → 226 taken 1301102 times.
 1570962 if ( kk > TXS && kk < CTXS )
1288 269860 continue;
1289
1290
1291 found = 0;
1292
2/2
✓ Branch 226 → 213 taken 1305292 times.
✓ Branch 226 → 227 taken 3728 times.
 1309020 for ( kk = 0; kk < 2; kk++ ) {
1293 jj = 0;
1294 ll = 0;
1295
1296 do {
1297
4/4
✓ Branch 213 → 214 taken 1311134 times.
✓ Branch 213 → 215 taken 13175068 times.
✓ Branch 215 → 211 taken 13168290 times.
✓ Branch 215 → 214 taken 6778 times.
 14486202 while ( yy[jj][kk][ii] < yy[ll][kk][tp] && jj < yl[kk][ii] ) {
1298
1299 13168290 jj++;
1300 }
1301
1302
1303
1304
1305
4/4
✓ Branch 217 → 218 taken 152413 times.
✓ Branch 217 → 219 taken 1317611 times.
✓ Branch 218 → 216 taken 152112 times.
✓ Branch 218 → 219 taken 301 times.
 1470024 while ( yy[jj][kk][ii] > yy[ll][kk][tp] && ll < yl[kk][tp] ) {
1306
1307 152112 ll++;
1308 }
1309
1310
1311
1312
1313
5/6
✓ Branch 219 → 220 taken 1298195 times.
✓ Branch 219 → 222 taken 19717 times.
✓ Branch 220 → 221 taken 1297374 times.
✓ Branch 220 → 222 taken 821 times.
✗ Branch 221 → 222 not taken.
✓ Branch 221 → 224 taken 1297374 times.
 1317912 if ( yy[jj][kk][ii] == yy[ll][kk][tp] && jj < yl[kk][ii] && ll < yl[kk][tp] ) {
1314 found = 1;
1315 break;
1316 }
1317
1318
1319
4/4
✓ Branch 222 → 223 taken 12904 times.
✓ Branch 222 → 224 taken 7634 times.
✓ Branch 223 → 212 taken 12620 times.
✓ Branch 223 → 224 taken 284 times.
 20538 } while ( jj < yl[kk][ii] && ll < yl[kk][tp] );
1320
2/2
✓ Branch 224 → 225 taken 7918 times.
✓ Branch 224 → 227 taken 1297374 times.
 1305292 if ( found )
1321 break;
1322 } /* END for kk */
1323
1324
2/2
✓ Branch 227 → 228 taken 3728 times.
✓ Branch 227 → 229 taken 1297374 times.
 1301102 if ( ! found ) { /* If we didn't find what we were searching for ... */
1325 3728 gct[ii] += ct[tp];
1326 3728 if ( gct[ii] > match_score )
1327 match_score = gct[ii];
1328 3728 ++ctt[ii];
1329 3728 ctp[ii][ctt[ii]] = tp;
1330 }
1331
1332 } /* END for ii in [0,TP-1] prior TP group */
1333
1334 tp++; /* Bump TP counter */
1335
1336
1337 } /* END ELSE if ( tot == MSTR ) */
1338
1339
1340
1341
1/2
✗ Branch 231 → 232 not taken.
✓ Branch 231 → 237 taken 48570 times.
 48570 if ( qh > QQ_SIZE ) {
1342 ✗ fprintf( stderr, "%s: WARNING: bz_match_score(): qq[] overflow #3 in bozorth3(); qh-1 is %d [p=%s; g=%s]\n",
1343 get_progname(), qh-1, get_probe_filename(), get_gallery_filename() );
1344 ✗ return QQ_OVERFLOW_SCORE;
1345 }
1346
2/2
✓ Branch 241 → 238 taken 1670712 times.
✓ Branch 241 → 242 taken 48570 times.
 1719282 for ( i = qh - 1; i > 0; i-- ) {
1347 1670712 n = qq[i] - 1;
1348
2/2
✓ Branch 238 → 239 taken 348756 times.
✓ Branch 238 → 240 taken 1321956 times.
 1670712 if ( ( tq[n] - 1 ) >= 0 ) {
1349 348756 rq[tq[n]-1] = 0;
1350 348756 tq[n] = 0;
1351 348756 zz[n] = 1000;
1352 }
1353 }
1354
1355
2/2
✓ Branch 246 → 243 taken 181606 times.
✓ Branch 246 → 247 taken 48570 times.
 230176 for ( i = dw - 1; i >= 0; i-- ) {
1356 181606 n = rr[i] - 1;
1357
2/2
✓ Branch 243 → 244 taken 89668 times.
✓ Branch 243 → 245 taken 91938 times.
 181606 if ( tq[n] ) {
1358 89668 rq[tq[n]-1] = 0;
1359 89668 tq[n] = 0;
1360 }
1361 }
1362
1363 48570 i = 0;
1364 48570 j = ww - 1;
1365
2/2
✓ Branch 271 → 248 taken 813564 times.
✓ Branch 271 → 272 taken 48570 times.
 862134 while ( i >= 0 && j >= 0 ) {
1366
2/2
✓ Branch 248 → 249 taken 416108 times.
✓ Branch 248 → 269 taken 397456 times.
 813564 if ( nn[j] < mm[j] ) {
1367 416108 ++nn[j];
1368
1369
2/2
✓ Branch 262 → 250 taken 2025582 times.
✓ Branch 262 → 263 taken 25770 times.
 2051352 for ( i = ww - 1; i >= 0; i-- ) {
1370 2025582 int rt = rx[i];
1371
2/2
✓ Branch 250 → 251 taken 1261816 times.
✓ Branch 250 → 256 taken 763766 times.
 2025582 if ( rt < 0 ) {
1372 1261816 rt = - rt;
1373 1261816 rt--;
1374 1261816 z = rf[i][nn[i]-1]-1;
1375
1376
1377
1378
8/8
✓ Branch 251 → 252 taken 1224702 times.
✓ Branch 251 → 253 taken 37114 times.
✓ Branch 252 → 253 taken 1058146 times.
✓ Branch 252 → 263 taken 166556 times.
✓ Branch 253 → 254 taken 1058146 times.
✓ Branch 253 → 255 taken 37114 times.
✓ Branch 254 → 255 taken 1021814 times.
✓ Branch 254 → 263 taken 36332 times.
 1261816 if (( tq[z] != (rt+1) && tq[z] ) || ( rq[rt] != (z+1) && rq[rt] ))
1379 break;
1380
1381
1382 1058928 tq[z] = rt+1;
1383 1058928 rq[rt] = z+1;
1384 1058928 rr[i] = z+1;
1385 } else {
1386 763766 rt--;
1387 763766 z = cf[i][nn[i]-1]-1;
1388
1389
1390
8/8
✓ Branch 256 → 257 taken 682926 times.
✓ Branch 256 → 258 taken 80840 times.
✓ Branch 257 → 258 taken 577768 times.
✓ Branch 257 → 263 taken 105158 times.
✓ Branch 258 → 259 taken 577768 times.
✓ Branch 258 → 260 taken 80840 times.
✓ Branch 259 → 260 taken 495476 times.
✓ Branch 259 → 263 taken 82292 times.
 763766 if (( tq[rt] != (z+1) && tq[rt] ) || ( rq[z] != (rt+1) && rq[z] ))
1391 break;
1392
1393
1394 576316 tq[rt] = z+1;
1395 576316 rq[z] = rt+1;
1396 576316 rr[i] = rt+1;
1397 }
1398 } /* END for i */
1399
1400
2/2
✓ Branch 263 → 264 taken 390338 times.
✓ Branch 263 → 270 taken 25770 times.
 416108 if ( i >= 0 ) {
1401
2/2
✓ Branch 268 → 265 taken 1453638 times.
✓ Branch 268 → 270 taken 390338 times.
 1843976 for ( z = i + 1; z < ww; z++) {
1402 1453638 n = rr[z] - 1;
1403
2/2
✓ Branch 265 → 266 taken 1361814 times.
✓ Branch 265 → 267 taken 91824 times.
 1453638 if ( tq[n] - 1 >= 0 ) {
1404 1361814 rq[tq[n]-1] = 0;
1405 1361814 tq[n] = 0;
1406 }
1407 }
1408 j = ww - 1;
1409 }
1410
1411 } else {
1412 397456 nn[j] = 1;
1413 397456 j--;
1414 }
1415
1416 }
1417
1418
1/2
✓ Branch 272 → 273 taken 48570 times.
✗ Branch 272 → 284 not taken.
 48570 if ( tp > 1999 )
1419 break;
1420
1421 48570 dw = ww;
1422
1423
1424
2/2
✓ Branch 273 → 24 taken 25770 times.
✓ Branch 273 → 274 taken 22800 times.
 48570 } while ( j >= 0 ); /* END while endpoint group remain ... */
1425
1426
1427 22800 if ( tp > 1999 )
1428 break;
1429
1430
1431
1432
1433 22800 n = qq[0] - 1;
1434
2/2
✓ Branch 274 → 275 taken 22734 times.
✓ Branch 274 → 276 taken 66 times.
 22800 if ( tq[n] - 1 >= 0 ) {
1435 22734 rq[tq[n]-1] = 0;
1436 22734 tq[n] = 0;
1437 }
1438
1439
2/2
✓ Branch 281 → 277 taken 9430 times.
✓ Branch 281 → 282 taken 22800 times.
 32230 for ( i = ww-1; i >= 0; i-- ) {
1440 9430 n = rx[i];
1441
2/2
✓ Branch 277 → 278 taken 4726 times.
✓ Branch 277 → 279 taken 4704 times.
 9430 if ( n < 0 ) {
1442 4726 n = - n;
1443 4726 rp[n-1] = 0;
1444 } else {
1445 4704 cp[n-1] = 0;
1446 }
1447
1448 }
1449
1450 } /* END FOR each edge pair */
1451
1452
1453
1454
1/2
✓ Branch 284 → 285 taken 26 times.
✗ Branch 284 → 287 not taken.
 26 if ( match_score < MMSTR ) {
1455 return match_score;
1456 }
1457
1458 26 match_score = bz_final_loop( tp );
1459 26 return match_score;
1460 }
1461
1462
1463 /***********************************************************************/
1464 /* These globals signficantly used by bz_sift () */
1465 /* Now externally defined in bozorth.h */
1466 /* extern int sc[ SC_SIZE ]; */
1467 /* extern int rq[ RQ_SIZE ]; */
1468 /* extern int tq[ TQ_SIZE ]; */
1469 /* extern int rf[ RF_SIZE_1 ][ RF_SIZE_2 ]; */
1470 /* extern int cf[ CF_SIZE_1 ][ CF_SIZE_2 ]; */
1471 /* extern int zz[ ZZ_SIZE ]; */
1472 /* extern int rx[ RX_SIZE ]; */
1473 /* extern int mm[ MM_SIZE ]; */
1474 /* extern int nn[ NN_SIZE ]; */
1475 /* extern int qq[ QQ_SIZE ]; */
1476 /* extern int rk[ RK_SIZE ]; */
1477 /* extern int cp[ CP_SIZE ]; */
1478 /* extern int rp[ RP_SIZE ]; */
1479 /* extern int bz_y[ Y_SIZE ]; */
1480
1481 39301652 void bz_sift(
1482 int * ww, /* INPUT and OUTPUT; endpoint groups index; *ww may be bumped by one or by two */
1483 int kz, /* INPUT only; endpoint of lookahead Subject edge */
1484 int * qh, /* INPUT and OUTPUT; the value is an index into qq[] and is stored in zz[]; *qh may be bumped by one */
1485 int l, /* INPUT only; endpoint of lookahead On-File edge */
1486 int kx, /* INPUT only -- index */
1487 int ftt, /* INPUT only */
1488 int * tot, /* OUTPUT -- counter is incremented by one, sometimes */
1489 int * qq_overflow /* OUTPUT -- flag is set only if qq[] overflows */
1490 )
1491 {
1492 39301652 int n;
1493 39301652 int t;
1494
1495 /* These now externally defined in bozorth.h */
1496 /* extern FILE * stderr; */
1497 /* extern char * get_progname( void ); */
1498 /* extern char * get_probe_filename( void ); */
1499 /* extern char * get_gallery_filename( void ); */
1500
1501
1502
1503 39301652 n = tq[ kz - 1]; /* Lookup On-File edgepoint stored in TQ at index of endpoint of lookahead Subject edge */
1504 39301652 t = rq[ l - 1]; /* Lookup Subject edgepoint stored in RQ at index of endpoint of lookahead On-File edge */
1505
1506
2/2
✓ Branch 2 → 3 taken 282882 times.
✓ Branch 2 → 12 taken 39018770 times.
 39301652 if ( n == 0 && t == 0 ) {
1507
1508
1509
2/2
✓ Branch 3 → 4 taken 282426 times.
✓ Branch 3 → 5 taken 456 times.
 282882 if ( sc[kx-1] != ftt ) {
1510 282426 bz_y[ (*tot)++ ] = kx;
1511 282426 rk[kx-1] = sc[kx-1];
1512 282426 sc[kx-1] = ftt;
1513 }
1514
1515
1/2
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 11 taken 282882 times.
 282882 if ( *qh >= QQ_SIZE ) {
1516 ✗ fprintf( stderr, "%s: ERROR: bz_sift(): qq[] overflow #1; the index [*qh] is %d [p=%s; g=%s]\n",
1517 get_progname(),
1518 *qh, get_probe_filename(), get_gallery_filename() );
1519 ✗ *qq_overflow = 1;
1520 ✗ return;
1521 }
1522 282882 qq[ *qh ] = kz;
1523 282882 zz[ kz-1 ] = (*qh)++;
1524
1525
1526 /* The TQ and RQ locations are set, so set them ... */
1527 282882 tq[ kz-1 ] = l;
1528 282882 rq[ l-1 ] = kz;
1529
1530 282882 return;
1531 } /* END if ( n == 0 && t == 0 ) */
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
2/2
✓ Branch 12 → 13 taken 26523164 times.
✓ Branch 12 → 23 taken 12495606 times.
 39018770 if ( n == l ) {
1542
1543
2/2
✓ Branch 13 → 14 taken 1387906 times.
✓ Branch 13 → 44 taken 25135258 times.
 26523164 if ( sc[kx-1] != ftt ) {
1544
2/2
✓ Branch 14 → 15 taken 1387830 times.
✓ Branch 14 → 22 taken 76 times.
 1387906 if ( zz[kx-1] == 1000 ) {
1545
1/2
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 21 taken 1387830 times.
 1387830 if ( *qh >= QQ_SIZE ) {
1546 ✗ fprintf( stderr, "%s: ERROR: bz_sift(): qq[] overflow #2; the index [*qh] is %d [p=%s; g=%s]\n",
1547 get_progname(),
1548 *qh,
1549 get_probe_filename(), get_gallery_filename() );
1550 ✗ *qq_overflow = 1;
1551 ✗ return;
1552 }
1553 1387830 qq[*qh] = kz;
1554 1387830 zz[kz-1] = (*qh)++;
1555 }
1556 1387906 bz_y[(*tot)++] = kx;
1557 1387906 rk[kx-1] = sc[kx-1];
1558 1387906 sc[kx-1] = ftt;
1559 }
1560
1561 return;
1562 } /* END if ( n == l ) */
1563
1564
1565
1566
1567
1568
2/2
✓ Branch 23 → 24 taken 51042 times.
✓ Branch 23 → 44 taken 12444564 times.
 12495606 if ( *ww >= WWIM ) /* This limits the number of endpoint groups that can be constructed */
1569 return;
1570
1571
1572 {
1573 51042 int b;
1574 51042 int b_index;
1575 51042 register int i;
1576 51042 int notfound;
1577 51042 int lim;
1578 51042 register int * lptr;
1579
1580 /* If lookahead Subject endpoint previously assigned to TQ but not paired with lookahead On-File endpoint ... */
1581
1582
2/2
✓ Branch 24 → 25 taken 32752 times.
✓ Branch 24 → 34 taken 18290 times.
 51042 if ( n ) {
1583 32752 b = cp[ kz - 1 ];
1584
2/2
✓ Branch 25 → 26 taken 4704 times.
✓ Branch 25 → 27 taken 28048 times.
 32752 if ( b == 0 ) {
1585 4704 b = ++*ww;
1586 4704 b_index = b - 1;
1587 4704 cp[kz-1] = b;
1588 4704 cf[b_index][0] = n;
1589 4704 mm[b_index] = 1;
1590 4704 nn[b_index] = 1;
1591 4704 rx[b_index] = kz;
1592
1593 } else {
1594 28048 b_index = b - 1;
1595 }
1596
1597 32752 lim = mm[b_index];
1598 32752 lptr = &cf[b_index][0];
1599 32752 notfound = 1;
1600
1601 #ifndef NOVERBOSE
1602 32752 if ( 0 ) {
1603 int * llptr = lptr;
1604 printf( "bz_sift(): n: looking for l=%d in [", l );
1605 for ( i = 0; i < lim; i++ ) {
1606 printf( " %d", *llptr++ );
1607 }
1608 printf( " ]\n" );
1609 }
1610 #endif
1611
1612
2/2
✓ Branch 31 → 29 taken 48520 times.
✓ Branch 31 → 32 taken 5504 times.
 54024 for ( i = 0; i < lim; i++ ) {
1613
2/2
✓ Branch 29 → 30 taken 21272 times.
✓ Branch 29 → 32 taken 27248 times.
 48520 if ( *lptr++ == l ) {
1614 notfound = 0;
1615 break;
1616 }
1617 }
1618
2/2
✓ Branch 32 → 33 taken 5504 times.
✓ Branch 32 → 34 taken 27248 times.
 32752 if ( notfound ) { /* If lookahead On-File endpoint not in list ... */
1619 5504 cf[b_index][i] = l;
1620 5504 ++mm[b_index];
1621 }
1622 } /* END if ( n ) */
1623
1624
1625 /* If lookahead On-File endpoint previously assigned to RQ but not paired with lookahead Subject endpoint... */
1626
1627
2/2
✓ Branch 34 → 35 taken 26520 times.
✓ Branch 34 → 44 taken 24522 times.
 51042 if ( t ) {
1628 26520 b = rp[ l - 1 ];
1629
2/2
✓ Branch 35 → 36 taken 4726 times.
✓ Branch 35 → 37 taken 21794 times.
 26520 if ( b == 0 ) {
1630 4726 b = ++*ww;
1631 4726 b_index = b - 1;
1632 4726 rp[l-1] = b;
1633 4726 rf[b_index][0] = t;
1634 4726 mm[b_index] = 1;
1635 4726 nn[b_index] = 1;
1636 4726 rx[b_index] = -l;
1637
1638
1639 } else {
1640 21794 b_index = b - 1;
1641 }
1642
1643 26520 lim = mm[b_index];
1644 26520 lptr = &rf[b_index][0];
1645 26520 notfound = 1;
1646
1647 #ifndef NOVERBOSE
1648 26520 if ( 0 ) {
1649 int * llptr = lptr;
1650 printf( "bz_sift(): t: looking for kz=%d in [", kz );
1651 for ( i = 0; i < lim; i++ ) {
1652 printf( " %d", *llptr++ );
1653 }
1654 printf( " ]\n" );
1655 }
1656 #endif
1657
1658
2/2
✓ Branch 41 → 39 taken 35018 times.
✓ Branch 41 → 42 taken 5086 times.
 40104 for ( i = 0; i < lim; i++ ) {
1659
2/2
✓ Branch 39 → 40 taken 13584 times.
✓ Branch 39 → 42 taken 21434 times.
 35018 if ( *lptr++ == kz ) {
1660 notfound = 0;
1661 break;
1662 }
1663 }
1664
2/2
✓ Branch 42 → 43 taken 5086 times.
✓ Branch 42 → 44 taken 21434 times.
 26520 if ( notfound ) { /* If lookahead Subject endpoint not in list ... */
1665 5086 rf[b_index][i] = kz;
1666 5086 ++mm[b_index];
1667 }
1668 } /* END if ( t ) */
1669
1670 }
1671
1672 }
1673
1674 /**************************************************************************/
1675
1676 26 static int bz_final_loop( int tp )
1677 {
1678 26 int ii, i, t, b, n, k, j, kk, jj;
1679 26 int lim;
1680 26 int match_score;
1681
1682 /* This array originally declared global, but moved here */
1683 /* locally because it is only used herein. The use of */
1684 /* "static" is required as the array will exceed the */
1685 /* stack allocation on our local systems otherwise. */
1686 26 static int sct[ SCT_SIZE_1 ][ SCT_SIZE_2 ];
1687
1688 26 match_score = 0;
1689
2/2
✓ Branch 48 → 3 taken 16672 times.
✓ Branch 48 → 49 taken 26 times.
 16698 for ( ii = 0; ii < tp; ii++ ) { /* For each index up to the current value of TP ... */
1690
1691
2/2
✓ Branch 3 → 4 taken 16540 times.
✓ Branch 3 → 5 taken 132 times.
 16672 if ( match_score >= gct[ii] ) /* if next group total not bigger than current match_score.. */
1692 16540 continue; /* skip to next TP index */
1693
1694 132 lim = ctt[ii] + 1;
1695
2/2
✓ Branch 7 → 6 taken 3284 times.
✓ Branch 7 → 8 taken 132 times.
 3416 for ( i = 0; i < lim; i++ ) {
1696 3284 sct[i][0] = ctp[ii][i];
1697 }
1698
1699 132 t = 0;
1700 132 bz_y[0] = lim;
1701 132 cp[0] = 1;
1702 132 b = 0;
1703 132 n = 1;
1704 6272 do { /* looping until T < 0 ... */
1705
2/2
✓ Branch 9 → 10 taken 3070 times.
✓ Branch 9 → 30 taken 3202 times.
 6272 if (bz_y[t] - cp[t] > 1 ) {
1706 3070 k = sct[cp[t]][t];
1707 3070 j = ctt[k] + 1;
1708
2/2
✓ Branch 12 → 11 taken 3070 times.
✓ Branch 12 → 13 taken 3070 times.
 6140 for ( i = 0; i < j; i++ ) {
1709 3070 rp[i] = ctp[k][i];
1710 }
1711 k = 0;
1712 kk = cp[t];
1713 jj = 0;
1714
1715 do {
1716
1/4
✗ Branch 16 → 17 not taken.
✓ Branch 16 → 18 taken 3070 times.
✗ Branch 17 → 14 not taken.
✗ Branch 17 → 18 not taken.
 3070 while ( rp[jj] < sct[kk][t] && jj < j )
1717 ✗ jj++;
1718
1/4
✓ Branch 20 → 21 taken 3070 times.
✗ Branch 20 → 22 not taken.
✗ Branch 22 → 19 not taken.
✗ Branch 22 → 21 not taken.
 3070 while ( rp[jj] > sct[kk][t] && kk < bz_y[t] )
1719 ✗ kk++;
1720
4/6
✓ Branch 24 → 25 taken 3070 times.
✓ Branch 24 → 27 taken 3070 times.
✓ Branch 25 → 26 taken 3070 times.
✗ Branch 25 → 27 not taken.
✓ Branch 26 → 23 taken 3070 times.
✗ Branch 26 → 27 not taken.
 6140 while ( rp[jj] == sct[kk][t] && kk < bz_y[t] && jj < j ) {
1721 3070 sct[k][t+1] = sct[kk][t];
1722 3070 k++;
1723 3070 kk++;
1724 3070 jj++;
1725 }
1726
2/4
✓ Branch 27 → 28 taken 3070 times.
✗ Branch 27 → 29 not taken.
✗ Branch 28 → 15 not taken.
✓ Branch 28 → 29 taken 3070 times.
 3070 } while ( kk < bz_y[t] && jj < j );
1727
1728 3070 t++;
1729 3070 cp[t] = 1;
1730 3070 bz_y[t] = k;
1731 3070 b = t;
1732 3070 n = 1;
1733 } else {
1734 3202 int tot = 0;
1735
1736 3202 lim = bz_y[t];
1737
2/2
✓ Branch 32 → 31 taken 3202 times.
✓ Branch 32 → 33 taken 3202 times.
 6404 for ( i = n-1; i < lim; i++ ) {
1738 3202 tot += ct[ sct[i][t] ];
1739 }
1740
1741
2/2
✓ Branch 35 → 34 taken 3152 times.
✓ Branch 35 → 36 taken 3202 times.
 6354 for ( i = 0; i < b; i++ ) {
1742 3152 tot += ct[ sct[0][i] ];
1743 }
1744
1745
2/2
✓ Branch 36 → 37 taken 50 times.
✓ Branch 36 → 43 taken 3152 times.
 3202 if ( tot > match_score ) { /* If the current total is larger than the running total ... */
1746 50 match_score = tot; /* then set match_score to the new total */
1747
1/2
✗ Branch 39 → 38 not taken.
✓ Branch 39 → 40 taken 50 times.
 50 for ( i = 0; i < b; i++ ) {
1748 ✗ rk[i] = sct[0][i];
1749 }
1750
1751 {
1752 int rk_index = b;
1753 100 lim = bz_y[t];
1754
2/2
✓ Branch 42 → 41 taken 50 times.
✓ Branch 42 → 43 taken 50 times.
 100 for ( i = n-1; i < lim; ) {
1755 50 rk[ rk_index++ ] = sct[ i++ ][ t ];
1756 }
1757 }
1758 }
1759 3202 b = t;
1760 3202 t--;
1761
2/2
✓ Branch 43 → 44 taken 3070 times.
✓ Branch 43 → 45 taken 132 times.
 3202 if ( t >= 0 ) {
1762 3070 ++cp[t];
1763 3070 n = bz_y[t];
1764 }
1765 } /* END IF */
1766
1767
2/2
✓ Branch 45 → 46 taken 6140 times.
✓ Branch 45 → 47 taken 132 times.
 6272 } while ( t >= 0 );
1768
1769 } /* END FOR ii */
1770
1771 26 return match_score;
1772
1773 } /* END bz_final_loop() */
1774