GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 96.4% 660 / 0 / 685
Functions: 100.0% 7 / 0 / 7
Branches: 93.2% 409 / 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 3122 times.
✓ Branch 48 → 49 taken 35 times.
 3157 for ( k = 0; k < npoints - 1; k++ ) {
121
2/2
✓ Branch 46 → 4 taken 116529 times.
✓ Branch 46 → 47 taken 1515 times.
 118044 for ( j = k + 1; j < npoints; j++ ) {
122
123
124
2/2
✓ Branch 4 → 5 taken 51769 times.
✓ Branch 4 → 7 taken 64760 times.
 116529 if ( thetacol[j] > 0 ) {
125
126
2/2
✓ Branch 5 → 6 taken 2348 times.
✓ Branch 5 → 9 taken 49421 times.
 51769 if ( thetacol[k] == thetacol[j] - 180 )
127 2348 continue;
128 } else {
129
130
2/2
✓ Branch 7 → 8 taken 2528 times.
✓ Branch 7 → 9 taken 62232 times.
 64760 if ( thetacol[k] == thetacol[j] + 180 )
131 2528 continue;
132 }
133
134
135 111653 dx = xcol[j] - xcol[k];
136 111653 dy = ycol[j] - ycol[k];
137 111653 distance = SQUARED(dx) + SQUARED(dy);
138
2/2
✓ Branch 9 → 10 taken 32940 times.
✓ Branch 9 → 12 taken 78713 times.
 111653 if ( distance > SQUARED(DM) ) {
139
2/2
✓ Branch 10 → 11 taken 31333 times.
✓ Branch 10 → 47 taken 1607 times.
 32940 if ( dx > DM )
140 break;
141 else
142 31333 continue;
143
144 }
145
146 /* The distance is in the range [ 0, 125^2 ] */
147
2/2
✓ Branch 12 → 13 taken 78098 times.
✓ Branch 12 → 17 taken 615 times.
 78713 if ( dx == 0 )
148 theta_kj = 90;
149 else {
150 78098 double dz;
151
152 78098 if ( 0 )
153 dz = ( 180.0F / PI_SINGLE ) * atanf( (float) -dy / (float) dx );
154 else
155 78098 dz = ( 180.0F / PI_SINGLE ) * atanf( (float) dy / (float) dx );
156
2/2
✓ Branch 13 → 14 taken 39485 times.
✓ Branch 13 → 15 taken 38613 times.
 78098 if ( dz < 0.0F )
157 39485 dz -= 0.5F;
158 else
159 38613 dz += 0.5F;
160 78098 theta_kj = (int) dz;
161 }
162
163
164 78713 beta_k = theta_kj - thetacol[k];
165
4/4
✓ Branch 17 → 18 taken 6278 times.
✓ Branch 17 → 19 taken 72435 times.
✓ Branch 19 → 20 taken 3942 times.
✓ Branch 19 → 21 taken 68493 times.
 78713 beta_k = IANGLE180(beta_k);
166
167 78713 beta_j = theta_kj - thetacol[j] + 180;
168
3/4
✓ Branch 21 → 22 taken 41204 times.
✓ Branch 21 → 23 taken 37509 times.
✗ Branch 23 → 24 not taken.
✓ Branch 23 → 25 taken 37509 times.
 78713 beta_j = IANGLE180(beta_j);
169
170
171
2/2
✓ Branch 25 → 26 taken 39354 times.
✓ Branch 25 → 27 taken 39359 times.
 78713 if ( beta_k < beta_j ) {
172 39354 *c++ = distance;
173 39354 *c++ = beta_k;
174 39354 *c++ = beta_j;
175 39354 *c++ = k+1;
176 39354 *c++ = j+1;
177 39354 *c++ = theta_kj;
178 } else {
179 39359 *c++ = distance;
180 39359 *c++ = beta_j;
181 39359 *c++ = beta_k;
182 39359 *c++ = k+1;
183 39359 *c++ = j+1;
184 39359 *c++ = theta_kj + 400;
185
186 }
187
188
189
190
191
192
193 78713 b = 0;
194 78713 t = table_index + 1;
195 78713 l = 1;
196 78713 n = -1; /* Init binary search state ... */
197
198
199
200
201
2/2
✓ Branch 37 → 29 taken 768207 times.
✓ Branch 37 → 38 taken 78713 times.
 846920 while ( t - b > 1 ) {
202 768207 int * midpoint;
203
204 768207 l = ( b + t ) / 2;
205 768207 midpoint = colptrs[l-1];
206
207
208
209
210
2/2
✓ Branch 33 → 30 taken 792661 times.
✓ Branch 33 → 34 taken 26 times.
 792687 for ( i=0; i < 3; i++ ) {
211 792661 int dd, ff;
212
213 792661 dd = cols[table_index][i];
214
215 792661 ff = midpoint[i];
216
217
218
2/2
✓ Branch 30 → 31 taken 416242 times.
✓ Branch 30 → 34 taken 376419 times.
 792661 n = SENSE(dd,ff);
219
220
221 416242 if ( n < 0 ) {
222 t = l;
223 break;
224 }
225
2/2
✓ Branch 31 → 32 taken 24480 times.
✓ Branch 31 → 34 taken 391762 times.
 416242 if ( n > 0 ) {
226 b = l;
227 break;
228 }
229 }
230
231
2/2
✓ Branch 34 → 35 taken 26 times.
✓ Branch 34 → 36 taken 768181 times.
 768207 if ( n == 0 ) {
232 26 n = 1;
233 26 b = l;
234 }
235 } /* END while */
236
237
2/2
✓ Branch 38 → 39 taken 33324 times.
✓ Branch 38 → 40 taken 45389 times.
 78713 if ( n == 1 )
238 33324 ++l;
239
240
241
242
243
2/2
✓ Branch 42 → 41 taken 49428750 times.
✓ Branch 42 → 43 taken 78713 times.
 49507463 for ( i = table_index; i >= l; --i )
244 49428750 colptrs[i] = colptrs[i-1];
245
246
247 78713 colptrs[l-1] = &cols[table_index][0];
248 78713 ++table_index;
249
250
251
1/2
✗ Branch 43 → 44 not taken.
✓ Branch 43 → 45 taken 78713 times.
 78713 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 402 times.
✓ Branch 6 → 7 taken 35 times.
 437 while ( top - bottom > 1 ) {
292 402 midpoint = ( bottom + top ) / 2;
293 402 distance = *colpt[ midpoint-1 ];
294
2/2
✓ Branch 3 → 4 taken 254 times.
✓ Branch 3 → 5 taken 148 times.
 402 state = SENSE_NEG_POS(FD,distance);
295 if ( state < 0 )
296 top = midpoint;
297 else {
298 254 bottom = midpoint;
299 }
300 }
301
302
2/2
✓ Branch 7 → 8 taken 18 times.
✓ Branch 7 → 9 taken 17 times.
 35 if ( state > -1 )
303 18 ++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 45512 void rtp_insert( int * rtp[], int l, int idx, int * ptr )
320 {
321 45512 int shiftcount;
322 45512 int ** r1;
323 45512 int ** r2;
324
325
326 45512 r1 = &rtp[idx];
327 45512 r2 = r1 - 1;
328
329 45512 shiftcount = ( idx - l ) + 1;
330
2/2
✓ Branch 4 → 3 taken 23153680 times.
✓ Branch 4 → 5 taken 45512 times.
 23199192 while ( shiftcount-- > 0 ) {
331 23153680 *r1-- = *r2--;
332 }
333 45512 *r1 = ptr;
334 45512 }
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 23064 times.
✓ Branch 43 → 44 taken 26 times.
 23090 for ( k = 1; k < probe_ptrlist_len; k++ ) {
401 23064 ss = scolpt[k-1];
402
403 /* Foreach sorted edge in On-File Record's Web ... */
404
405
2/2
✓ Branch 41 → 4 taken 4203401 times.
✓ Branch 41 → 42 taken 3830 times.
 4207231 for ( j = st; j <= gallery_ptrlist_len; j++ ) {
406 4203401 ff = fcolpt[j-1];
407 4203401 dz = *ff - *ss;
408
409 4203401 fi = ( 2.0F * TK ) * ( *ff + *ss );
410
411
412
413
414
415
416
417
418
2/2
✓ Branch 4 → 5 taken 4162109 times.
✓ Branch 4 → 6 taken 41292 times.
 4203401 if ( SQUARED(dz) > SQUARED(fi) ) {
419
2/2
✓ Branch 6 → 7 taken 22058 times.
✓ Branch 6 → 42 taken 19234 times.
 41292 if ( dz < 0 ) {
420
421 22058 st = j + 1;
422
423 22058 continue;
424 } else
425 break;
426
427
428 }
429
430
431
432
2/2
✓ Branch 11 → 8 taken 4525176 times.
✓ Branch 11 → 12 taken 45512 times.
 4570688 for ( i = 1; i < 3; i++ ) {
433 4525176 float dz_squared;
434
435 4525176 dz = *(ss+i) - *(ff+i);
436 4525176 dz_squared = SQUARED(dz);
437
438
439
440
441
3/4
✓ Branch 8 → 9 taken 4116597 times.
✓ Branch 8 → 10 taken 408579 times.
✗ Branch 9 → 10 not taken.
✓ Branch 9 → 12 taken 4116597 times.
 4525176 if ( dz_squared > TXS && dz_squared < CTXS )
442 break;
443 }
444
445
2/2
✓ Branch 12 → 13 taken 4116597 times.
✓ Branch 12 → 14 taken 45512 times.
 4162109 if ( i < 3 )
446 4116597 continue;
447
448
449
450
451
452
453
2/2
✓ Branch 14 → 15 taken 23858 times.
✓ Branch 14 → 16 taken 21654 times.
 45512 if ( *(ss+5) >= 220 ) {
454 23858 p1 = *(ss+5) - 580;
455 23858 n = 1;
456 } else {
457 p1 = *(ss+5);
458 n = 0;
459 }
460
461
462
2/2
✓ Branch 16 → 17 taken 23142 times.
✓ Branch 16 → 18 taken 22370 times.
 45512 if ( *(ff+5) >= 220 ) {
463 23142 p2 = *(ff+5) - 580;
464 23142 b = 1;
465 } else {
466 p2 = *(ff+5);
467 b = 0;
468 }
469
470 45512 p1 -= p2;
471
4/4
✓ Branch 18 → 19 taken 5117 times.
✓ Branch 18 → 20 taken 40395 times.
✓ Branch 20 → 21 taken 5529 times.
✓ Branch 20 → 22 taken 34866 times.
 45512 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 19690 times.
✓ Branch 22 → 24 taken 25822 times.
 45512 if ( n != b ) {
497
498 19690 *rotptr++ = p1;
499 19690 *rotptr++ = *(ss+3);
500 19690 *rotptr++ = *(ss+4);
501
502 19690 *rotptr++ = *(ff+4);
503 19690 *rotptr++ = *(ff+3);
504 } else {
505 25822 *rotptr++ = p1;
506 25822 *rotptr++ = *(ss+3);
507 25822 *rotptr++ = *(ss+4);
508
509 25822 *rotptr++ = *(ff+3);
510 25822 *rotptr++ = *(ff+4);
511 }
512
513
514
515
516
517
518 45512 n = -1;
519 45512 l = 1;
520 45512 b = 0;
521 45512 t = edge_pair_index + 1;
522
2/2
✓ Branch 34 → 26 taken 430536 times.
✓ Branch 34 → 35 taken 45512 times.
 476048 while ( t - b > 1 ) {
523 430536 l = ( b + t ) / 2;
524
525
2/2
✓ Branch 30 → 27 taken 617126 times.
✓ Branch 30 → 31 taken 2560 times.
 619686 for ( i = 0; i < 3; i++ ) {
526 617126 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 617126 ii = ii_table[i];
533 617126 p1 = rot[edge_pair_index][ii];
534 617126 p2 = *( rtp[l-1] + ii );
535
536
2/2
✓ Branch 27 → 28 taken 407684 times.
✓ Branch 27 → 31 taken 209442 times.
 617126 n = SENSE(p1,p2);
537
538 407684 if ( n < 0 ) {
539 t = l;
540 break;
541 }
542
2/2
✓ Branch 28 → 29 taken 189150 times.
✓ Branch 28 → 31 taken 218534 times.
 407684 if ( n > 0 ) {
543 b = l;
544 break;
545 }
546 }
547
548
2/2
✓ Branch 31 → 32 taken 2560 times.
✓ Branch 31 → 33 taken 427976 times.
 430536 if ( n == 0 ) {
549 2560 n = 1;
550 2560 b = l;
551 }
552 } /* END while() for binary search */
553
554
555
2/2
✓ Branch 35 → 36 taken 18591 times.
✓ Branch 35 → 37 taken 26921 times.
 45512 if ( n == 1 )
556 18591 ++l;
557
558 45512 rtp_insert( rtp, l, edge_pair_index, &rot[edge_pair_index][0] );
559 45512 ++edge_pair_index;
560
561
1/2
✗ Branch 38 → 39 not taken.
✓ Branch 38 → 40 taken 45512 times.
 45512 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 45512 times.
✓ Branch 50 → 51 taken 26 times.
 45538 for ( i = 0; i < edge_pair_index; i++ ) {
581
2/2
✓ Branch 48 → 47 taken 227560 times.
✓ Branch 48 → 49 taken 45512 times.
 273072 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 43730 times.
✓ Branch 283 → 284 taken 25 times.
 43755 for ( k = 0; k < np - 1; k++ ) {
707 /* printf( "compute(): looping with k=%d\n", k ); */
708
709
2/2
✓ Branch 21 → 22 taken 22345 times.
✓ Branch 21 → 23 taken 21385 times.
 43730 if ( sc[k] ) /* If SC counter for current pair already incremented ... */
710 22345 continue; /* Skip to next pair */
711
712
713 21385 i = colp[k][1];
714 21385 t = colp[k][3];
715
716
717
718
719 21385 qq[0] = i;
720 21385 rq[t-1] = i;
721 21385 tq[i-1] = t;
722
723
724 21385 ww = 0;
725 21385 dw = 0;
726
727 42815 do {
728 42815 ftt++;
729 42815 tot = 0;
730 42815 qh = 1;
731 42815 kx = k;
732
733
734
735
736 76320 do {
737
738
739
740
741
742
743
744
745
746 76320 kz = colp[kx][2];
747 76320 l = colp[kx][4];
748 76320 kx++;
749 76320 bz_sift( &ww, kz, &qh, l, kx, ftt, &tot, &qq_overflow );
750
1/2
✗ Branch 26 → 27 not taken.
✓ Branch 26 → 32 taken 76320 times.
 76320 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 76320 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 42815 times.
✓ Branch 32 → 34 taken 33505 times.
✓ Branch 34 → 25 taken 33505 times.
✗ Branch 34 → 33 not taken.
 76320 } 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 721483 times.
✓ Branch 89 → 90 taken 42815 times.
 764298 for ( j = 1; j < qh; j++ ) {
768
2/2
✓ Branch 58 → 46 taken 1679663873 times.
✓ Branch 58 → 59 taken 721483 times.
 1680385356 for ( i = kq; i < np; i++ ) {
769
770
2/2
✓ Branch 46 → 35 taken 1703315257 times.
✓ Branch 46 → 47 taken 6812531 times.
 1710127788 for ( z = 1; z < 3; z++ ) {
771
2/2
✓ Branch 35 → 36 taken 1679663873 times.
✓ Branch 35 → 43 taken 23651384 times.
 1703315257 if ( z == 1 ) {
772
1/2
✗ Branch 36 → 37 not taken.
✓ Branch 36 → 42 taken 1679663873 times.
 1679663873 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 1679663873 p1 = qq[j];
778 } else {
779 23651384 p1 = tq[p1-1];
780
781 }
782
783
784
785
786
787
788
2/2
✓ Branch 44 → 45 taken 30463915 times.
✓ Branch 44 → 47 taken 1672851342 times.
 1703315257 if ( colp[i][2*z] != p1 )
789 break;
790 }
791
792
793
2/2
✓ Branch 47 → 48 taken 6812531 times.
✓ Branch 47 → 57 taken 1672851342 times.
 1679663873 if ( z == 3 ) {
794 6812531 z = colp[i][1];
795 6812531 l = colp[i][3];
796
797
798
799
4/4
✓ Branch 48 → 49 taken 6789102 times.
✓ Branch 48 → 57 taken 23429 times.
✓ Branch 49 → 50 taken 6704404 times.
✓ Branch 49 → 57 taken 84698 times.
 6812531 if ( z != colp[k][1] && l != colp[k][3] ) {
800 6704404 kx = i + 1;
801 6704404 bz_sift( &ww, z, &qh, l, kx, ftt, &tot, &qq_overflow );
802
1/2
✗ Branch 51 → 52 not taken.
✓ Branch 51 → 57 taken 6704404 times.
 6704404 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 721483 t = np + 1;
820 721483 b = kq;
821
822
2/2
✓ Branch 87 → 60 taken 5701907 times.
✓ Branch 87 → 88 taken 99120 times.
 5801027 while ( t - b > 1 ) {
823 5701907 l = ( b + t ) / 2;
824
825
2/2
✓ Branch 73 → 61 taken 7433727 times.
✓ Branch 73 → 74 taken 622363 times.
 8056090 for ( i = 1; i < 3; i++ ) {
826
827
2/2
✓ Branch 61 → 62 taken 5701907 times.
✓ Branch 61 → 69 taken 1731820 times.
 7433727 if ( i == 1 ) {
828
1/2
✗ Branch 62 → 63 not taken.
✓ Branch 62 → 68 taken 5701907 times.
 5701907 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 5701907 p1 = qq[j];
834 } else {
835 1731820 p1 = tq[p1-1];
836 }
837
838
839
840 7433727 p2 = colp[l-1][i*2-1];
841
842
2/2
✓ Branch 70 → 71 taken 5365747 times.
✓ Branch 70 → 74 taken 2067980 times.
 7433727 n = SENSE(p1,p2);
843
844 5365747 if ( n < 0 ) {
845 t = l;
846 break;
847 }
848
2/2
✓ Branch 71 → 72 taken 2354183 times.
✓ Branch 71 → 74 taken 3011564 times.
 5365747 if ( n > 0 ) {
849 b = l;
850 break;
851 }
852 }
853
854
2/2
✓ Branch 74 → 75 taken 622363 times.
✓ Branch 74 → 87 taken 5079544 times.
 5701907 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 2698162 times.
✓ Branch 75 → 77 taken 622363 times.
✓ Branch 76 → 75 taken 2698162 times.
✗ Branch 76 → 77 not taken.
 3320525 while ( colp[l-2][3] == p2 && colp[l-2][1] == colp[l-1][1] )
863 l--;
864
865 622363 kx = l - 1;
866
867
868 6082805 do {
869 6082805 kz = colp[kx][2];
870 6082805 l = colp[kx][4];
871 6082805 kx++;
872 6082805 bz_sift( &ww, kz, &qh, l, kx, ftt, &tot, &qq_overflow );
873
1/2
✗ Branch 79 → 80 not taken.
✓ Branch 79 → 85 taken 6082805 times.
 6082805 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 5460442 times.
✓ Branch 85 → 88 taken 622363 times.
✓ Branch 86 → 78 taken 5460442 times.
✗ Branch 86 → 88 not taken.
 6082805 } 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 14734 times.
✓ Branch 90 → 114 taken 28081 times.
 42815 if ( tot >= MSTR ) {
891 jj = 0;
892 kk = 0;
893 n = 0;
894 l = 0;
895
896
2/2
✓ Branch 95 → 91 taken 692203 times.
✓ Branch 95 → 96 taken 14734 times.
 706937 for ( i = 0; i < tot; i++ ) {
897
898
899 692203 int colp_value = colp[ bz_y[i]-1 ][0];
900
2/2
✓ Branch 91 → 92 taken 125488 times.
✓ Branch 91 → 93 taken 566715 times.
 692203 if ( colp_value < 0 ) {
901 125488 kk += colp_value;
902 125488 n++;
903 } else {
904 566715 jj += colp_value;
905 566715 l++;
906 }
907 }
908
909
910
2/2
✓ Branch 96 → 97 taken 9669 times.
✓ Branch 96 → 98 taken 5065 times.
 14734 if ( n == 0 ) {
911 n = 1;
912 9669 } else if ( l == 0 ) {
913 l = 1;
914 }
915
916
917
918 14734 fi = (float) jj / (float) l - (float) kk / (float) n;
919
920
2/2
✓ Branch 98 → 99 taken 221 times.
✓ Branch 98 → 101 taken 14513 times.
 14734 if ( fi > 180.0F ) {
921 221 fi = ( jj + kk + n * 360 ) / (float) tot;
922
2/2
✓ Branch 99 → 100 taken 126 times.
✓ Branch 99 → 102 taken 95 times.
 221 if ( fi > 180.0F )
923 126 fi -= 360.0F;
924 } else {
925 14513 fi = ( jj + kk ) / (float) tot;
926 }
927
928
2/2
✓ Branch 102 → 103 taken 7751 times.
✓ Branch 102 → 104 taken 6983 times.
 14734 jj = ROUND(fi);
929
2/2
✓ Branch 105 → 106 taken 19 times.
✓ Branch 105 → 107 taken 14715 times.
 14734 if ( jj <= -180 )
930 19 jj += 360;
931
932
933
934 14734 kk = 0;
935
2/2
✓ Branch 112 → 108 taken 692203 times.
✓ Branch 112 → 113 taken 14734 times.
 706937 for ( i = 0; i < tot; i++ ) {
936 692203 int diff = colp[ bz_y[i]-1 ][0] - jj;
937 692203 j = SQUARED( diff );
938
939
940
941
942
2/2
✓ Branch 108 → 109 taken 38526 times.
✓ Branch 108 → 110 taken 653677 times.
 692203 if ( j > TXS && j < CTXS )
943 38526 kk++;
944 else
945 653677 bz_y[i-kk] = bz_y[i];
946 } /* END FOR i */
947
948 14734 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 28505 times.
✓ Branch 114 → 146 taken 14310 times.
 42815 if ( tot < MSTR ) {
956
957
958
959
960
2/2
✓ Branch 119 → 116 taken 29862 times.
✓ Branch 119 → 231 taken 28505 times.
 58367 for ( i = tot-1 ; i >= 0; i-- ) {
961 29862 int idx = bz_y[i] - 1;
962
2/2
✓ Branch 116 → 117 taken 5582 times.
✓ Branch 116 → 118 taken 24280 times.
 29862 if ( rk[idx] == 0 ) {
963 sc[idx] = -1;
964 } else {
965 5582 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 652919 times.
✓ Branch 146 → 147 taken 14310 times.
 667229 for ( i = 0; i < tot; i++ ) {
979 652919 int idx = bz_y[i] - 1;
980
2/2
✓ Branch 128 → 121 taken 1958757 times.
✓ Branch 128 → 144 taken 652919 times.
 2611676 for ( ii = 1; ii < 4; ii++ ) {
981
982
983
984
985 1958757 kk = ( SQUARED(ii) - ii + 2 ) / 2 - 1;
986
987
988
989
990 1958757 jj = colp[idx][kk];
991
992
3/3
✓ Branch 121 → 122 taken 652919 times.
✓ Branch 121 → 125 taken 652919 times.
✓ Branch 121 → 126 taken 652919 times.
 1958757 switch ( ii ) {
993 652919 case 1:
994
2/2
✓ Branch 122 → 123 taken 104883 times.
✓ Branch 122 → 124 taken 548036 times.
 652919 if ( colp[idx][0] < 0 ) {
995 104883 pd += colp[idx][0];
996 104883 pb++;
997 } else {
998 548036 pa += colp[idx][0];
999 548036 pc++;
1000 }
1001 break;
1002 652919 case 2:
1003 652919 avn[ii-1] += pstruct->xcol[jj-1];
1004 652919 avn[ii] += pstruct->ycol[jj-1];
1005 652919 break;
1006 652919 default:
1007 652919 avn[ii] += gstruct->xcol[jj-1];
1008 652919 avn[ii+1] += gstruct->ycol[jj-1];
1009 652919 break;
1010 } /* switch */
1011 } /* END for ii = [1..3] */
1012
1013
2/2
✓ Branch 144 → 142 taken 1305838 times.
✓ Branch 144 → 145 taken 652919 times.
 1958757 for ( ii = 0; ii < 2; ii++ ) {
1014 n = -1;
1015 l = 1;
1016
1017
2/2
✓ Branch 142 → 129 taken 2611676 times.
✓ Branch 142 → 143 taken 1305838 times.
 3917514 for ( jj = 1; jj < 3; jj++ ) {
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028 2611676 p1 = colp[idx][ 2 * ii + jj ];
1029
1030
1031 2611676 b = 0;
1032 2611676 t = yl[ii][tp] + 1;
1033
1034
2/2
✓ Branch 133 → 130 taken 11299324 times.
✓ Branch 133 → 134 taken 421941 times.
 11721265 while ( t - b > 1 ) {
1035 11299324 l = ( b + t ) / 2;
1036 11299324 p2 = yy[l-1][ii][tp];
1037
2/2
✓ Branch 130 → 131 taken 7747724 times.
✓ Branch 130 → 132 taken 3551600 times.
 11299324 n = SENSE(p1,p2);
1038
1039 7747724 if ( n < 0 ) {
1040 t = l;
1041 } else {
1042
2/2
✓ Branch 131 → 132 taken 5557989 times.
✓ Branch 131 → 134 taken 2189735 times.
 7747724 if ( n > 0 ) {
1043 b = l;
1044 } else {
1045 break;
1046 }
1047 }
1048 } /* END WHILE */
1049
1050
2/2
✓ Branch 134 → 135 taken 421941 times.
✓ Branch 134 → 141 taken 2189735 times.
 2611676 if ( n != 0 ) {
1051
2/2
✓ Branch 135 → 136 taken 215730 times.
✓ Branch 135 → 137 taken 206211 times.
 421941 if ( n == 1 )
1052 215730 ++l;
1053
1054
2/2
✓ Branch 139 → 138 taken 2150163 times.
✓ Branch 139 → 140 taken 421941 times.
 2572104 for ( kk = yl[ii][tp]; kk >= l; --kk ) {
1055 2150163 yy[kk][ii][tp] = yy[kk-1][ii][tp];
1056 }
1057
1058 421941 ++yl[ii][tp];
1059 421941 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 8903 times.
✓ Branch 147 → 149 taken 5407 times.
 14310 if ( pb == 0 ) {
1071 pb = 1;
1072 8903 } else if ( pc == 0 ) {
1073 pc = 1;
1074 }
1075
1076
1077
1078 14310 fi = (float) pa / (float) pc - (float) pd / (float) pb;
1079
2/2
✓ Branch 149 → 150 taken 178 times.
✓ Branch 149 → 152 taken 14132 times.
 14310 if ( fi > 180.0F ) {
1080
1081 178 fi = ( pa + pd + pb * 360 ) / (float) tot;
1082
2/2
✓ Branch 150 → 151 taken 105 times.
✓ Branch 150 → 153 taken 73 times.
 178 if ( fi > 180.0F )
1083 105 fi -= 360.0F;
1084 } else {
1085 14132 fi = ( pa + pd ) / (float) tot;
1086 }
1087
1088
2/2
✓ Branch 153 → 154 taken 7472 times.
✓ Branch 153 → 155 taken 6838 times.
 14310 pa = ROUND(fi);
1089
2/2
✓ Branch 156 → 157 taken 16 times.
✓ Branch 156 → 158 taken 14294 times.
 14310 if ( pa <= -180 )
1090 16 pa += 360;
1091
1092
1093
1094 14310 avv[tp][0] = pa;
1095
1096
2/2
✓ Branch 160 → 159 taken 57240 times.
✓ Branch 160 → 161 taken 14310 times.
 71550 for ( ii = 1; ii < 5; ii++ ) {
1097 57240 avv[tp][ii] = avn[ii] / tot;
1098 57240 avn[ii] = 0;
1099 }
1100
1101 14310 ct[tp] = tot;
1102 14310 gct[tp] = tot;
1103
1104 14310 if ( tot > match_score ) /* If current TOT > match_score ... */
1105 match_score = tot; /* Keep track of max TOT in match_score */
1106
1107 14310 ctt[tp] = 0; /* Init CTT[TP] to 0 */
1108 14310 ctp[tp][0] = tp; /* Store TP into CTP */
1109
1110
2/2
✓ Branch 230 → 162 taken 8271830 times.
✓ Branch 230 → 231 taken 14310 times.
 8286140 for ( ii = 0; ii < tp; ii++ ) {
1111 8271830 int found;
1112 8271830 int diff;
1113
1114 8271830 int * avv_tp_ptr = &avv[tp][0];
1115 8271830 int * avv_ii_ptr = &avv[ii][0];
1116 8271830 diff = *avv_tp_ptr++ - *avv_ii_ptr++;
1117 8271830 j = SQUARED( diff );
1118
1119
1120
1121
1122
1123
1124
2/2
✓ Branch 162 → 163 taken 5849616 times.
✓ Branch 162 → 164 taken 2422214 times.
 8271830 if ( j > TXS && j < CTXS )
1125 5849616 continue;
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135 2422214 ll = *avv_tp_ptr++ - *avv_ii_ptr++;
1136 2422214 jj = *avv_tp_ptr++ - *avv_ii_ptr++;
1137 2422214 kk = *avv_tp_ptr++ - *avv_ii_ptr++;
1138 2422214 j = *avv_tp_ptr++ - *avv_ii_ptr++;
1139
1140 {
1141 2422214 float tt, ai, dz;
1142
1143 2422214 tt = (float) (SQUARED(ll) + SQUARED(jj));
1144 2422214 ai = (float) (SQUARED(j) + SQUARED(kk));
1145
1146 2422214 fi = ( 2.0F * TK ) * ( tt + ai );
1147 2422214 dz = tt - ai;
1148
1149
1150
2/2
✓ Branch 164 → 165 taken 1323000 times.
✓ Branch 164 → 166 taken 1099214 times.
 2422214 if ( SQUARED(dz) > SQUARED(fi) )
1151 1323000 continue;
1152 }
1153
1154
1155
1156
2/2
✓ Branch 166 → 167 taken 1052448 times.
✓ Branch 166 → 176 taken 46766 times.
 1099214 if ( ll ) {
1157
1158 1052448 if ( 0 )
1159 fi = ( 180.0F / PI_SINGLE ) * atanf( (float) -jj / (float) ll );
1160 else
1161 1052448 fi = ( 180.0F / PI_SINGLE ) * atanf( (float) jj / (float) ll );
1162
2/2
✓ Branch 167 → 168 taken 606845 times.
✓ Branch 167 → 171 taken 445603 times.
 1052448 if ( fi < 0.0F ) {
1163
2/2
✓ Branch 168 → 169 taken 167533 times.
✓ Branch 168 → 170 taken 439312 times.
 606845 if ( ll < 0 )
1164 167533 fi += 180.5F;
1165 else
1166 439312 fi -= 0.5F;
1167 } else {
1168
2/2
✓ Branch 171 → 172 taken 151354 times.
✓ Branch 171 → 173 taken 294249 times.
 445603 if ( ll < 0 )
1169 151354 fi -= 180.5F;
1170 else
1171 294249 fi += 0.5F;
1172 }
1173 1052448 jj = (int) fi;
1174
2/2
✓ Branch 174 → 175 taken 5077 times.
✓ Branch 174 → 178 taken 1047371 times.
 1052448 if ( jj <= -180 )
1175 5077 jj += 360;
1176 } else {
1177
1178 46766 if ( 0 ) {
1179 if ( jj > 0 )
1180 jj = -90;
1181 else
1182 jj = 90;
1183 } else {
1184
2/2
✓ Branch 176 → 177 taken 32024 times.
✓ Branch 176 → 178 taken 14742 times.
 46766 if ( jj > 0 )
1185 jj = 90;
1186 else
1187 32024 jj = -90;
1188 }
1189 }
1190
1191
1192
1193
2/2
✓ Branch 178 → 179 taken 1049492 times.
✓ Branch 178 → 188 taken 49722 times.
 1099214 if ( kk ) {
1194
1195 1049492 if ( 0 )
1196 fi = ( 180.0F / PI_SINGLE ) * atanf( (float) -j / (float) kk );
1197 else
1198 1049492 fi = ( 180.0F / PI_SINGLE ) * atanf( (float) j / (float) kk );
1199
2/2
✓ Branch 179 → 180 taken 598615 times.
✓ Branch 179 → 183 taken 450877 times.
 1049492 if ( fi < 0.0F ) {
1200
2/2
✓ Branch 180 → 181 taken 181796 times.
✓ Branch 180 → 182 taken 416819 times.
 598615 if ( kk < 0 )
1201 181796 fi += 180.5F;
1202 else
1203 416819 fi -= 0.5F;
1204 } else {
1205
2/2
✓ Branch 183 → 184 taken 170757 times.
✓ Branch 183 → 185 taken 280120 times.
 450877 if ( kk < 0 )
1206 170757 fi -= 180.5F;
1207 else
1208 280120 fi += 0.5F;
1209 }
1210 1049492 j = (int) fi;
1211
2/2
✓ Branch 186 → 187 taken 4946 times.
✓ Branch 186 → 190 taken 1044546 times.
 1049492 if ( j <= -180 )
1212 4946 j += 360;
1213 } else {
1214
1215 49722 if ( 0 ) {
1216 if ( j > 0 )
1217 j = -90;
1218 else
1219 j = 90;
1220 } else {
1221
2/2
✓ Branch 188 → 189 taken 32837 times.
✓ Branch 188 → 190 taken 16885 times.
 49722 if ( j > 0 )
1222 j = 90;
1223 else
1224 32837 j = -90;
1225 }
1226 }
1227
1228
1229
1230
1231
1232 1099214 pa = 0;
1233 1099214 pb = 0;
1234 1099214 pc = 0;
1235 1099214 pd = 0;
1236
1237
2/2
✓ Branch 190 → 191 taken 568487 times.
✓ Branch 190 → 192 taken 530727 times.
 1099214 if ( avv[tp][0] < 0 ) {
1238 pd += avv[tp][0];
1239 pb++;
1240 } else {
1241 568487 pa += avv[tp][0];
1242 568487 pc++;
1243 }
1244
1245
2/2
✓ Branch 192 → 193 taken 536684 times.
✓ Branch 192 → 194 taken 562530 times.
 1099214 if ( avv[ii][0] < 0 ) {
1246 536684 pd += avv[ii][0];
1247 536684 pb++;
1248 } else {
1249 562530 pa += avv[ii][0];
1250 562530 pc++;
1251 }
1252
1253
2/2
✓ Branch 194 → 195 taken 31232 times.
✓ Branch 194 → 196 taken 531298 times.
 1099214 if ( pb == 0 ) {
1254 pb = 1;
1255 567916 } else if ( pc == 0 ) {
1256 pc = 1;
1257 }
1258
1259
1260
1261 1099214 fi = (float) pa / (float) pc - (float) pd / (float) pb;
1262
1263
2/2
✓ Branch 196 → 197 taken 149 times.
✓ Branch 196 → 199 taken 1099065 times.
 1099214 if ( fi > 180.0F ) {
1264 149 fi = ( pa + pd + pb * 360 ) / 2.0F;
1265
2/2
✓ Branch 197 → 198 taken 122 times.
✓ Branch 197 → 200 taken 27 times.
 149 if ( fi > 180.0F )
1266 122 fi -= 360.0F;
1267 } else {
1268 1099065 fi = ( pa + pd ) / 2.0F;
1269 }
1270
1271
2/2
✓ Branch 200 → 201 taken 562308 times.
✓ Branch 200 → 202 taken 536906 times.
 1099214 pb = ROUND(fi);
1272
2/2
✓ Branch 203 → 204 taken 17 times.
✓ Branch 203 → 205 taken 1099197 times.
 1099214 if ( pb <= -180 )
1273 17 pb += 360;
1274
1275
1276
1277
1278
1279 1099214 pa = jj - j;
1280
4/4
✓ Branch 205 → 206 taken 17725 times.
✓ Branch 205 → 207 taken 1081489 times.
✓ Branch 207 → 208 taken 17140 times.
✓ Branch 207 → 209 taken 1064349 times.
 1099214 pa = IANGLE180(pa);
1281 1099214 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 395582 times.
✓ Branch 209 → 226 taken 703632 times.
 1099214 if ( kk > TXS && kk < CTXS )
1288 395582 continue;
1289
1290
1291 found = 0;
1292
2/2
✓ Branch 226 → 213 taken 708079 times.
✓ Branch 226 → 227 taken 3862 times.
 711941 for ( kk = 0; kk < 2; kk++ ) {
1293 jj = 0;
1294 ll = 0;
1295
1296 do {
1297
4/4
✓ Branch 213 → 214 taken 738243 times.
✓ Branch 213 → 215 taken 4722657 times.
✓ Branch 215 → 211 taken 4716598 times.
✓ Branch 215 → 214 taken 6059 times.
 5460900 while ( yy[jj][kk][ii] < yy[ll][kk][tp] && jj < yl[kk][ii] ) {
1298
1299 4716598 jj++;
1300 }
1301
1302
1303
1304
1305
4/4
✓ Branch 217 → 218 taken 150898 times.
✓ Branch 217 → 219 taken 743992 times.
✓ Branch 218 → 216 taken 150588 times.
✓ Branch 218 → 219 taken 310 times.
 894890 while ( yy[jj][kk][ii] > yy[ll][kk][tp] && ll < yl[kk][tp] ) {
1306
1307 150588 ll++;
1308 }
1309
1310
1311
1312
1313
6/6
✓ Branch 219 → 220 taken 701457 times.
✓ Branch 219 → 222 taken 42845 times.
✓ Branch 220 → 221 taken 699786 times.
✓ Branch 220 → 222 taken 1671 times.
✓ Branch 221 → 222 taken 16 times.
✓ Branch 221 → 224 taken 699770 times.
 744302 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 36613 times.
✓ Branch 222 → 224 taken 7919 times.
✓ Branch 223 → 212 taken 36223 times.
✓ Branch 223 → 224 taken 390 times.
 44532 } while ( jj < yl[kk][ii] && ll < yl[kk][tp] );
1320
2/2
✓ Branch 224 → 225 taken 8309 times.
✓ Branch 224 → 227 taken 699770 times.
 708079 if ( found )
1321 break;
1322 } /* END for kk */
1323
1324
2/2
✓ Branch 227 → 228 taken 3862 times.
✓ Branch 227 → 229 taken 699770 times.
 703632 if ( ! found ) { /* If we didn't find what we were searching for ... */
1325 3862 gct[ii] += ct[tp];
1326 3862 if ( gct[ii] > match_score )
1327 match_score = gct[ii];
1328 3862 ++ctt[ii];
1329 3862 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 42815 times.
 42815 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 721483 times.
✓ Branch 241 → 242 taken 42815 times.
 764298 for ( i = qh - 1; i > 0; i-- ) {
1347 721483 n = qq[i] - 1;
1348
2/2
✓ Branch 238 → 239 taken 250668 times.
✓ Branch 238 → 240 taken 470815 times.
 721483 if ( ( tq[n] - 1 ) >= 0 ) {
1349 250668 rq[tq[n]-1] = 0;
1350 250668 tq[n] = 0;
1351 250668 zz[n] = 1000;
1352 }
1353 }
1354
1355
2/2
✓ Branch 246 → 243 taken 151318 times.
✓ Branch 246 → 247 taken 42815 times.
 194133 for ( i = dw - 1; i >= 0; i-- ) {
1356 151318 n = rr[i] - 1;
1357
2/2
✓ Branch 243 → 244 taken 70950 times.
✓ Branch 243 → 245 taken 80368 times.
 151318 if ( tq[n] ) {
1358 70950 rq[tq[n]-1] = 0;
1359 70950 tq[n] = 0;
1360 }
1361 }
1362
1363 42815 i = 0;
1364 42815 j = ww - 1;
1365
2/2
✓ Branch 271 → 248 taken 700467 times.
✓ Branch 271 → 272 taken 42815 times.
 743282 while ( i >= 0 && j >= 0 ) {
1366
2/2
✓ Branch 248 → 249 taken 361509 times.
✓ Branch 248 → 269 taken 338958 times.
 700467 if ( nn[j] < mm[j] ) {
1367 361509 ++nn[j];
1368
1369
2/2
✓ Branch 262 → 250 taken 1765426 times.
✓ Branch 262 → 263 taken 21431 times.
 1786857 for ( i = ww - 1; i >= 0; i-- ) {
1370 1765426 int rt = rx[i];
1371
2/2
✓ Branch 250 → 251 taken 949594 times.
✓ Branch 250 → 256 taken 815832 times.
 1765426 if ( rt < 0 ) {
1372 949594 rt = - rt;
1373 949594 rt--;
1374 949594 z = rf[i][nn[i]-1]-1;
1375
1376
1377
1378
8/8
✓ Branch 251 → 252 taken 915579 times.
✓ Branch 251 → 253 taken 34015 times.
✓ Branch 252 → 253 taken 820770 times.
✓ Branch 252 → 263 taken 94809 times.
✓ Branch 253 → 254 taken 820770 times.
✓ Branch 253 → 255 taken 34015 times.
✓ Branch 254 → 255 taken 787766 times.
✓ Branch 254 → 263 taken 33004 times.
 949594 if (( tq[z] != (rt+1) && tq[z] ) || ( rq[rt] != (z+1) && rq[rt] ))
1379 break;
1380
1381
1382 821781 tq[z] = rt+1;
1383 821781 rq[rt] = z+1;
1384 821781 rr[i] = z+1;
1385 } else {
1386 815832 rt--;
1387 815832 z = cf[i][nn[i]-1]-1;
1388
1389
1390
8/8
✓ Branch 256 → 257 taken 726115 times.
✓ Branch 256 → 258 taken 89717 times.
✓ Branch 257 → 258 taken 613289 times.
✓ Branch 257 → 263 taken 112826 times.
✓ Branch 258 → 259 taken 613289 times.
✓ Branch 258 → 260 taken 89717 times.
✓ Branch 259 → 260 taken 513850 times.
✓ Branch 259 → 263 taken 99439 times.
 815832 if (( tq[rt] != (z+1) && tq[rt] ) || ( rq[z] != (rt+1) && rq[z] ))
1391 break;
1392
1393
1394 603567 tq[rt] = z+1;
1395 603567 rq[z] = rt+1;
1396 603567 rr[i] = rt+1;
1397 }
1398 } /* END for i */
1399
1400
2/2
✓ Branch 263 → 264 taken 340078 times.
✓ Branch 263 → 270 taken 21431 times.
 361509 if ( i >= 0 ) {
1401
2/2
✓ Branch 268 → 265 taken 1274020 times.
✓ Branch 268 → 270 taken 340078 times.
 1614098 for ( z = i + 1; z < ww; z++) {
1402 1274020 n = rr[z] - 1;
1403
2/2
✓ Branch 265 → 266 taken 1172984 times.
✓ Branch 265 → 267 taken 101036 times.
 1274020 if ( tq[n] - 1 >= 0 ) {
1404 1172984 rq[tq[n]-1] = 0;
1405 1172984 tq[n] = 0;
1406 }
1407 }
1408 j = ww - 1;
1409 }
1410
1411 } else {
1412 338958 nn[j] = 1;
1413 338958 j--;
1414 }
1415
1416 }
1417
1418
2/2
✓ Branch 272 → 273 taken 42814 times.
✓ Branch 272 → 284 taken 1 time.
 42815 if ( tp > 1999 )
1419 break;
1420
1421 42814 dw = ww;
1422
1423
1424
2/2
✓ Branch 273 → 24 taken 21430 times.
✓ Branch 273 → 274 taken 21384 times.
 42814 } while ( j >= 0 ); /* END while endpoint group remain ... */
1425
1426
1427 21384 if ( tp > 1999 )
1428 break;
1429
1430
1431
1432
1433 21384 n = qq[0] - 1;
1434
2/2
✓ Branch 274 → 275 taken 21336 times.
✓ Branch 274 → 276 taken 48 times.
 21384 if ( tq[n] - 1 >= 0 ) {
1435 21336 rq[tq[n]-1] = 0;
1436 21336 tq[n] = 0;
1437 }
1438
1439
2/2
✓ Branch 281 → 277 taken 8090 times.
✓ Branch 281 → 282 taken 21384 times.
 29474 for ( i = ww-1; i >= 0; i-- ) {
1440 8090 n = rx[i];
1441
2/2
✓ Branch 277 → 278 taken 4176 times.
✓ Branch 277 → 279 taken 3914 times.
 8090 if ( n < 0 ) {
1442 4176 n = - n;
1443 4176 rp[n-1] = 0;
1444 } else {
1445 3914 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 12863529 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 12863529 int n;
1493 12863529 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 12863529 n = tq[ kz - 1]; /* Lookup On-File edgepoint stored in TQ at index of endpoint of lookahead Subject edge */
1504 12863529 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 192948 times.
✓ Branch 2 → 12 taken 12670581 times.
 12863529 if ( n == 0 && t == 0 ) {
1507
1508
1509
2/2
✓ Branch 3 → 4 taken 192683 times.
✓ Branch 3 → 5 taken 265 times.
 192948 if ( sc[kx-1] != ftt ) {
1510 192683 bz_y[ (*tot)++ ] = kx;
1511 192683 rk[kx-1] = sc[kx-1];
1512 192683 sc[kx-1] = ftt;
1513 }
1514
1515
1/2
✗ Branch 5 → 6 not taken.
✓ Branch 5 → 11 taken 192948 times.
 192948 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 192948 qq[ *qh ] = kz;
1523 192948 zz[ kz-1 ] = (*qh)++;
1524
1525
1526 /* The TQ and RQ locations are set, so set them ... */
1527 192948 tq[ kz-1 ] = l;
1528 192948 rq[ l-1 ] = kz;
1529
1530 192948 return;
1531 } /* END if ( n == 0 && t == 0 ) */
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
2/2
✓ Branch 12 → 13 taken 8951712 times.
✓ Branch 12 → 23 taken 3718869 times.
 12670581 if ( n == l ) {
1542
1543
2/2
✓ Branch 13 → 14 taken 528624 times.
✓ Branch 13 → 44 taken 8423088 times.
 8951712 if ( sc[kx-1] != ftt ) {
1544
2/2
✓ Branch 14 → 15 taken 528535 times.
✓ Branch 14 → 22 taken 89 times.
 528624 if ( zz[kx-1] == 1000 ) {
1545
1/2
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 21 taken 528535 times.
 528535 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 528535 qq[*qh] = kz;
1554 528535 zz[kz-1] = (*qh)++;
1555 }
1556 528624 bz_y[(*tot)++] = kx;
1557 528624 rk[kx-1] = sc[kx-1];
1558 528624 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 40206 times.
✓ Branch 23 → 44 taken 3678663 times.
 3718869 if ( *ww >= WWIM ) /* This limits the number of endpoint groups that can be constructed */
1569 return;
1570
1571
1572 {
1573 40206 int b;
1574 40206 int b_index;
1575 40206 register int i;
1576 40206 int notfound;
1577 40206 int lim;
1578 40206 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 23943 times.
✓ Branch 24 → 34 taken 16263 times.
 40206 if ( n ) {
1583 23943 b = cp[ kz - 1 ];
1584
2/2
✓ Branch 25 → 26 taken 3916 times.
✓ Branch 25 → 27 taken 20027 times.
 23943 if ( b == 0 ) {
1585 3916 b = ++*ww;
1586 3916 b_index = b - 1;
1587 3916 cp[kz-1] = b;
1588 3916 cf[b_index][0] = n;
1589 3916 mm[b_index] = 1;
1590 3916 nn[b_index] = 1;
1591 3916 rx[b_index] = kz;
1592
1593 } else {
1594 20027 b_index = b - 1;
1595 }
1596
1597 23943 lim = mm[b_index];
1598 23943 lptr = &cf[b_index][0];
1599 23943 notfound = 1;
1600
1601 #ifndef NOVERBOSE
1602 23943 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 34535 times.
✓ Branch 31 → 32 taken 4431 times.
 38966 for ( i = 0; i < lim; i++ ) {
1613
2/2
✓ Branch 29 → 30 taken 15023 times.
✓ Branch 29 → 32 taken 19512 times.
 34535 if ( *lptr++ == l ) {
1614 notfound = 0;
1615 break;
1616 }
1617 }
1618
2/2
✓ Branch 32 → 33 taken 4431 times.
✓ Branch 32 → 34 taken 19512 times.
 23943 if ( notfound ) { /* If lookahead On-File endpoint not in list ... */
1619 4431 cf[b_index][i] = l;
1620 4431 ++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 22403 times.
✓ Branch 34 → 44 taken 17803 times.
 40206 if ( t ) {
1628 22403 b = rp[ l - 1 ];
1629
2/2
✓ Branch 35 → 36 taken 4184 times.
✓ Branch 35 → 37 taken 18219 times.
 22403 if ( b == 0 ) {
1630 4184 b = ++*ww;
1631 4184 b_index = b - 1;
1632 4184 rp[l-1] = b;
1633 4184 rf[b_index][0] = t;
1634 4184 mm[b_index] = 1;
1635 4184 nn[b_index] = 1;
1636 4184 rx[b_index] = -l;
1637
1638
1639 } else {
1640 18219 b_index = b - 1;
1641 }
1642
1643 22403 lim = mm[b_index];
1644 22403 lptr = &rf[b_index][0];
1645 22403 notfound = 1;
1646
1647 #ifndef NOVERBOSE
1648 22403 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 30280 times.
✓ Branch 41 → 42 taken 4470 times.
 34750 for ( i = 0; i < lim; i++ ) {
1659
2/2
✓ Branch 39 → 40 taken 12347 times.
✓ Branch 39 → 42 taken 17933 times.
 30280 if ( *lptr++ == kz ) {
1660 notfound = 0;
1661 break;
1662 }
1663 }
1664
2/2
✓ Branch 42 → 43 taken 4470 times.
✓ Branch 42 → 44 taken 17933 times.
 22403 if ( notfound ) { /* If lookahead Subject endpoint not in list ... */
1665 4470 rf[b_index][i] = kz;
1666 4470 ++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 14310 times.
✓ Branch 48 → 49 taken 26 times.
 14336 for ( ii = 0; ii < tp; ii++ ) { /* For each index up to the current value of TP ... */
1690
1691
2/2
✓ Branch 3 → 4 taken 14103 times.
✓ Branch 3 → 5 taken 207 times.
 14310 if ( match_score >= gct[ii] ) /* if next group total not bigger than current match_score.. */
1692 14103 continue; /* skip to next TP index */
1693
1694 207 lim = ctt[ii] + 1;
1695
2/2
✓ Branch 7 → 6 taken 3569 times.
✓ Branch 7 → 8 taken 207 times.
 3776 for ( i = 0; i < lim; i++ ) {
1696 3569 sct[i][0] = ctp[ii][i];
1697 }
1698
1699 207 t = 0;
1700 207 bz_y[0] = lim;
1701 207 cp[0] = 1;
1702 207 b = 0;
1703 207 n = 1;
1704 6735 do { /* looping until T < 0 ... */
1705
2/2
✓ Branch 9 → 10 taken 3264 times.
✓ Branch 9 → 30 taken 3471 times.
 6735 if (bz_y[t] - cp[t] > 1 ) {
1706 3264 k = sct[cp[t]][t];
1707 3264 j = ctt[k] + 1;
1708
2/2
✓ Branch 12 → 11 taken 3264 times.
✓ Branch 12 → 13 taken 3264 times.
 6528 for ( i = 0; i < j; i++ ) {
1709 3264 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 3264 times.
✗ Branch 17 → 14 not taken.
✗ Branch 17 → 18 not taken.
 3264 while ( rp[jj] < sct[kk][t] && jj < j )
1717 ✗ jj++;
1718
1/4
✓ Branch 20 → 21 taken 3264 times.
✗ Branch 20 → 22 not taken.
✗ Branch 22 → 19 not taken.
✗ Branch 22 → 21 not taken.
 3264 while ( rp[jj] > sct[kk][t] && kk < bz_y[t] )
1719 ✗ kk++;
1720
4/6
✓ Branch 24 → 25 taken 3264 times.
✓ Branch 24 → 27 taken 3264 times.
✓ Branch 25 → 26 taken 3264 times.
✗ Branch 25 → 27 not taken.
✓ Branch 26 → 23 taken 3264 times.
✗ Branch 26 → 27 not taken.
 6528 while ( rp[jj] == sct[kk][t] && kk < bz_y[t] && jj < j ) {
1721 3264 sct[k][t+1] = sct[kk][t];
1722 3264 k++;
1723 3264 kk++;
1724 3264 jj++;
1725 }
1726
2/4
✓ Branch 27 → 28 taken 3264 times.
✗ Branch 27 → 29 not taken.
✗ Branch 28 → 15 not taken.
✓ Branch 28 → 29 taken 3264 times.
 3264 } while ( kk < bz_y[t] && jj < j );
1727
1728 3264 t++;
1729 3264 cp[t] = 1;
1730 3264 bz_y[t] = k;
1731 3264 b = t;
1732 3264 n = 1;
1733 } else {
1734 3471 int tot = 0;
1735
1736 3471 lim = bz_y[t];
1737
2/2
✓ Branch 32 → 31 taken 3471 times.
✓ Branch 32 → 33 taken 3471 times.
 6942 for ( i = n-1; i < lim; i++ ) {
1738 3471 tot += ct[ sct[i][t] ];
1739 }
1740
1741
2/2
✓ Branch 35 → 34 taken 3362 times.
✓ Branch 35 → 36 taken 3471 times.
 6833 for ( i = 0; i < b; i++ ) {
1742 3362 tot += ct[ sct[0][i] ];
1743 }
1744
1745
2/2
✓ Branch 36 → 37 taken 109 times.
✓ Branch 36 → 43 taken 3362 times.
 3471 if ( tot > match_score ) { /* If the current total is larger than the running total ... */
1746 109 match_score = tot; /* then set match_score to the new total */
1747
1/2
✗ Branch 39 → 38 not taken.
✓ Branch 39 → 40 taken 109 times.
 109 for ( i = 0; i < b; i++ ) {
1748 ✗ rk[i] = sct[0][i];
1749 }
1750
1751 {
1752 int rk_index = b;
1753 218 lim = bz_y[t];
1754
2/2
✓ Branch 42 → 41 taken 109 times.
✓ Branch 42 → 43 taken 109 times.
 218 for ( i = n-1; i < lim; ) {
1755 109 rk[ rk_index++ ] = sct[ i++ ][ t ];
1756 }
1757 }
1758 }
1759 3471 b = t;
1760 3471 t--;
1761
2/2
✓ Branch 43 → 44 taken 3264 times.
✓ Branch 43 → 45 taken 207 times.
 3471 if ( t >= 0 ) {
1762 3264 ++cp[t];
1763 3264 n = bz_y[t];
1764 }
1765 } /* END IF */
1766
1767
2/2
✓ Branch 45 → 46 taken 6528 times.
✓ Branch 45 → 47 taken 207 times.
 6735 } while ( t >= 0 );
1768
1769 } /* END FOR ii */
1770
1771 26 return match_score;
1772
1773 } /* END bz_final_loop() */
1774