GCC Code Coverage Report

Directory: ./
File: libfprint/nbis/bozorth3/bozorth3.c
Date: 2024-09-16 14:36:32
Exec Total Coverage
Lines: 664 691 96.1%
Functions: 7 7 100.0%
Branches: 411 445 92.4%
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 0 taken 3073 times.
✓ Branch 1 taken 35 times.
 3108 for ( k = 0; k < npoints - 1; k++ ) {
121
2/2
✓ Branch 0 taken 118174 times.
✓ Branch 1 taken 1575 times.
 119749 for ( j = k + 1; j < npoints; j++ ) {
122
123
124
2/2
✓ Branch 0 taken 49350 times.
✓ Branch 1 taken 68824 times.
 118174 if ( thetacol[j] > 0 ) {
125
126
2/2
✓ Branch 0 taken 2114 times.
✓ Branch 1 taken 47236 times.
 49350 if ( thetacol[k] == thetacol[j] - 180 )
127 2114 continue;
128 } else {
129
130
2/2
✓ Branch 0 taken 2527 times.
✓ Branch 1 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 0 taken 32669 times.
✓ Branch 1 taken 80864 times.
 113533 if ( distance > SQUARED(DM) ) {
139
2/2
✓ Branch 0 taken 31171 times.
✓ Branch 1 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 0 taken 80199 times.
✓ Branch 1 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 0 taken 39816 times.
✓ Branch 1 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 0 taken 7931 times.
✓ Branch 1 taken 72933 times.
✓ Branch 2 taken 3619 times.
✓ Branch 3 taken 69314 times.
 80864 beta_k = IANGLE180(beta_k);
166
167 80864 beta_j = theta_kj - thetacol[j] + 180;
168
3/4
✓ Branch 0 taken 44324 times.
✓ Branch 1 taken 36540 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 36540 times.
 80864 beta_j = IANGLE180(beta_j);
169
170
171
2/2
✓ Branch 0 taken 39886 times.
✓ Branch 1 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 0 taken 791973 times.
✓ Branch 1 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 0 taken 816907 times.
✗ Branch 1 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 0 taken 426818 times.
✓ Branch 1 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 0 taken 24934 times.
✓ Branch 1 taken 401884 times.
 426818 if ( n > 0 ) {
226 b = l;
227 break;
228 }
229 }
230
231
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 791973 times.
 791973 if ( n == 0 ) {
232 ✗ n = 1;
233 ✗ b = l;
234 }
235 } /* END while */
236
237
2/2
✓ Branch 0 taken 35252 times.
✓ Branch 1 taken 45612 times.
 80864 if ( n == 1 )
238 35252 ++l;
239
240
241
242
243
2/2
✓ Branch 0 taken 52540572 times.
✓ Branch 1 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 0 not taken.
✓ Branch 1 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 0 taken 413 times.
✓ Branch 1 taken 35 times.
 448 while ( top - bottom > 1 ) {
292 413 midpoint = ( bottom + top ) / 2;
293 413 distance = *colpt[ midpoint-1 ];
294
2/2
✓ Branch 0 taken 273 times.
✓ Branch 1 taken 140 times.
 413 state = SENSE_NEG_POS(FD,distance);
295 273 if ( state < 0 )
296 top = midpoint;
297 else {
298 273 bottom = midpoint;
299 }
300 }
301
302
2/2
✓ Branch 0 taken 28 times.
✓ Branch 1 taken 7 times.
 35 if ( state > -1 )
303 28 ++midpoint;
304
305
1/2
✓ Branch 0 taken 35 times.
✗ Branch 1 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 0 taken 30580338 times.
✓ Branch 1 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 0 taken 23206 times.
✓ Branch 1 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 0 taken 4529278 times.
✓ Branch 1 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 0 taken 4486938 times.
✓ Branch 1 taken 42340 times.
 4529278 if ( SQUARED(dz) > SQUARED(fi) ) {
419
2/2
✓ Branch 0 taken 23050 times.
✓ Branch 1 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 0 taken 4879442 times.
✓ Branch 1 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 0 taken 4434980 times.
✓ Branch 1 taken 444462 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4434980 times.
 4879442 if ( dz_squared > TXS && dz_squared < CTXS )
442 break;
443 }
444
445
2/2
✓ Branch 0 taken 4434980 times.
✓ Branch 1 taken 51958 times.
 4486938 if ( i < 3 )
446 4434980 continue;
447
448
449
450
451
452
453
2/2
✓ Branch 0 taken 27326 times.
✓ Branch 1 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 0 taken 27062 times.
✓ Branch 1 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 0 taken 5602 times.
✓ Branch 1 taken 46356 times.
✓ Branch 2 taken 6256 times.
✓ Branch 3 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 0 taken 19932 times.
✓ Branch 1 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 0 taken 502722 times.
✓ Branch 1 taken 51958 times.
 554680 while ( t - b > 1 ) {
523 502722 l = ( b + t ) / 2;
524
525
2/2
✓ Branch 0 taken 735932 times.
✓ Branch 1 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 0 taken 492806 times.
✓ Branch 1 taken 243126 times.
 735932 n = SENSE(p1,p2);
537
538 492806 if ( n < 0 ) {
539 t = l;
540 break;
541 }
542
2/2
✓ Branch 0 taken 236376 times.
✓ Branch 1 taken 256430 times.
 492806 if ( n > 0 ) {
543 b = l;
544 break;
545 }
546 }
547
548
2/2
✓ Branch 0 taken 3166 times.
✓ Branch 1 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 0 taken 21474 times.
✓ Branch 1 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 0 not taken.
✓ Branch 1 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 0 taken 51958 times.
✓ Branch 1 taken 26 times.
 51984 for ( i = 0; i < edge_pair_index; i++ ) {
581
2/2
✓ Branch 0 taken 259790 times.
✓ Branch 1 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 0 taken 26 times.
✗ Branch 1 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 0 taken 26 times.
✗ Branch 1 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 0 taken 104000 times.
✓ Branch 1 taken 26 times.
 104026 INT_SET( (int *) &yl, YL_SIZE_1 * YL_SIZE_2, 0 );
684
685
686
687
2/2
✓ Branch 0 taken 520000 times.
✓ Branch 1 taken 26 times.
 520026 INT_SET( (int *) &sc, SC_SIZE, 0 );
688
2/2
✓ Branch 0 taken 520000 times.
✓ Branch 1 taken 26 times.
 520026 INT_SET( (int *) &cp, CP_SIZE, 0 );
689
2/2
✓ Branch 0 taken 520000 times.
✓ Branch 1 taken 26 times.
 520026 INT_SET( (int *) &rp, RP_SIZE, 0 );
690
2/2
✓ Branch 0 taken 520000 times.
✓ Branch 1 taken 26 times.
 520026 INT_SET( (int *) &tq, TQ_SIZE, 0 );
691
2/2
✓ Branch 0 taken 520000 times.
✓ Branch 1 taken 26 times.
 520026 INT_SET( (int *) &rq, RQ_SIZE, 0 );
692
2/2
✓ Branch 0 taken 520000 times.
✓ Branch 1 taken 26 times.
 520026 INT_SET( (int *) &zz, ZZ_SIZE, 1000 ); /* zz[] initialized to 1000's */
693
694
2/2
✓ Branch 0 taken 130 times.
✓ Branch 1 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 0 taken 51932 times.
✓ Branch 1 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 0 taken 29132 times.
✓ Branch 1 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 0 not taken.
✓ Branch 1 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 0 taken 37962 times.
✓ Branch 1 taken 48570 times.
✓ Branch 2 taken 37962 times.
✗ Branch 3 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 0 taken 1670712 times.
✓ Branch 1 taken 48570 times.
 1719282 for ( j = 1; j < qh; j++ ) {
768
2/2
✓ Branch 0 taken 4378286546 times.
✓ Branch 1 taken 1670712 times.
 4379957258 for ( i = kq; i < np; i++ ) {
769
770
2/2
✓ Branch 0 taken 4440238036 times.
✓ Branch 1 taken 20762344 times.
 4461000380 for ( z = 1; z < 3; z++ ) {
771
2/2
✓ Branch 0 taken 4378286546 times.
✓ Branch 1 taken 61951490 times.
 4440238036 if ( z == 1 ) {
772
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 4378286546 times.
 4378286546 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 4378286546 p1 = qq[j];
778 } else {
779 61951490 p1 = tq[p1-1];
780
781 }
782
783
784
785
786
787
788
2/2
✓ Branch 0 taken 82713834 times.
✓ Branch 1 taken 4357524202 times.
 4440238036 if ( colp[i][2*z] != p1 )
789 break;
790 }
791
792
793
2/2
✓ Branch 0 taken 20762344 times.
✓ Branch 1 taken 4357524202 times.
 4378286546 if ( z == 3 ) {
794 20762344 z = colp[i][1];
795 20762344 l = colp[i][3];
796
797
798
799
4/4
✓ Branch 0 taken 20725524 times.
✓ Branch 1 taken 36820 times.
✓ Branch 2 taken 20450566 times.
✓ Branch 3 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 0 not taken.
✓ Branch 1 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 0 taken 12565196 times.
✓ Branch 1 taken 128168 times.
 12693364 while ( t - b > 1 ) {
823 12565196 l = ( b + t ) / 2;
824
825
2/2
✓ Branch 0 taken 15889750 times.
✓ Branch 1 taken 1542544 times.
 17432294 for ( i = 1; i < 3; i++ ) {
826
827
2/2
✓ Branch 0 taken 12565196 times.
✓ Branch 1 taken 3324554 times.
 15889750 if ( i == 1 ) {
828
1/2
✗ Branch 0 not taken.
✓ Branch 1 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 0 taken 11795618 times.
✓ Branch 1 taken 4094132 times.
 15889750 n = SENSE(p1,p2);
843
844 11795618 if ( n < 0 ) {
845 t = l;
846 break;
847 }
848
2/2
✓ Branch 0 taken 4867098 times.
✓ Branch 1 taken 6928520 times.
 11795618 if ( n > 0 ) {
849 b = l;
850 break;
851 }
852 }
853
854
2/2
✓ Branch 0 taken 1542544 times.
✓ Branch 1 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 0 taken 8470262 times.
✓ Branch 1 taken 1542544 times.
✓ Branch 2 taken 8470262 times.
✗ Branch 3 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 0 not taken.
✓ Branch 1 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 0 taken 17222010 times.
✓ Branch 1 taken 1542544 times.
✓ Branch 2 taken 17222010 times.
✗ Branch 3 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 0 taken 17160 times.
✓ Branch 1 taken 31410 times.
 48570 if ( tot >= MSTR ) {
891 jj = 0;
892 kk = 0;
893 n = 0;
894 l = 0;
895
896
2/2
✓ Branch 0 taken 1638588 times.
✓ Branch 1 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 0 taken 123972 times.
✓ Branch 1 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 0 taken 12218 times.
✓ Branch 1 taken 4942 times.
 17160 if ( n == 0 ) {
911 n = 1;
912
2/2
✓ Branch 0 taken 4944 times.
✓ Branch 1 taken 7274 times.
 12218 } else if ( l == 0 ) {
913 4944 l = 1;
914 }
915
916
917
918 17160 fi = (float) jj / (float) l - (float) kk / (float) n;
919
920
2/2
✓ Branch 0 taken 172 times.
✓ Branch 1 taken 16988 times.
 17160 if ( fi > 180.0F ) {
921 172 fi = ( jj + kk + n * 360 ) / (float) tot;
922
2/2
✓ Branch 0 taken 74 times.
✓ Branch 1 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 0 taken 9678 times.
✓ Branch 1 taken 7482 times.
 17160 jj = ROUND(fi);
929
2/2
✓ Branch 0 taken 14 times.
✓ Branch 1 taken 17146 times.
 17160 if ( jj <= -180 )
930 14 jj += 360;
931
932
933
934 17160 kk = 0;
935
2/2
✓ Branch 0 taken 1638588 times.
✓ Branch 1 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 0 taken 35240 times.
✓ Branch 1 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 0 taken 31898 times.
✓ Branch 1 taken 16672 times.
 48570 if ( tot < MSTR ) {
956
957
958
959
960
2/2
✓ Branch 0 taken 32656 times.
✓ Branch 1 taken 31898 times.
 64554 for ( i = tot-1 ; i >= 0; i-- ) {
961 32656 int idx = bz_y[i] - 1;
962
2/2
✓ Branch 0 taken 25482 times.
✓ Branch 1 taken 7174 times.
 32656 if ( rk[idx] == 0 ) {
963 25482 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 0 taken 1602436 times.
✓ Branch 1 taken 16672 times.
 1619108 for ( i = 0; i < tot; i++ ) {
979 1602436 int idx = bz_y[i] - 1;
980
2/2
✓ Branch 0 taken 4807308 times.
✓ Branch 1 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 0 taken 1602436 times.
✓ Branch 1 taken 1602436 times.
✓ Branch 2 taken 1602436 times.
 4807308 switch ( ii ) {
993 1602436 case 1:
994
2/2
✓ Branch 0 taken 101626 times.
✓ Branch 1 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 0 taken 3204872 times.
✓ Branch 1 taken 1602436 times.
 4807308 for ( ii = 0; ii < 2; ii++ ) {
1014 n = -1;
1015 l = 1;
1016
1017
2/2
✓ Branch 0 taken 6409744 times.
✓ Branch 1 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 0 taken 29604380 times.
✓ Branch 1 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 0 taken 20013654 times.
✓ Branch 1 taken 9590726 times.
 29604380 n = SENSE(p1,p2);
1038
1039 20013654 if ( n < 0 ) {
1040 t = l;
1041 } else {
1042
2/2
✓ Branch 0 taken 14218776 times.
✓ Branch 1 taken 5794878 times.
 20013654 if ( n > 0 ) {
1043 b = l;
1044 } else {
1045 break;
1046 }
1047 }
1048 } /* END WHILE */
1049
1050
2/2
✓ Branch 0 taken 614866 times.
✓ Branch 1 taken 5794878 times.
 6409744 if ( n != 0 ) {
1051
2/2
✓ Branch 0 taken 310172 times.
✓ Branch 1 taken 304694 times.
 614866 if ( n == 1 )
1052 310172 ++l;
1053
1054
2/2
✓ Branch 0 taken 4195068 times.
✓ Branch 1 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 0 taken 11276 times.
✓ Branch 1 taken 5396 times.
 16672 if ( pb == 0 ) {
1071 pb = 1;
1072
2/2
✓ Branch 0 taken 5188 times.
✓ Branch 1 taken 6088 times.
 11276 } else if ( pc == 0 ) {
1073 5188 pc = 1;
1074 }
1075
1076
1077
1078 16672 fi = (float) pa / (float) pc - (float) pd / (float) pb;
1079
2/2
✓ Branch 0 taken 120 times.
✓ Branch 1 taken 16552 times.
 16672 if ( fi > 180.0F ) {
1080
1081 120 fi = ( pa + pd + pb * 360 ) / (float) tot;
1082
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 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 0 taken 9236 times.
✓ Branch 1 taken 7436 times.
 16672 pa = ROUND(fi);
1089
2/2
✓ Branch 0 taken 18 times.
✓ Branch 1 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 0 taken 66688 times.
✓ Branch 1 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 0 taken 9619052 times.
✓ Branch 1 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 0 taken 6995822 times.
✓ Branch 1 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 0 taken 1052268 times.
✓ Branch 1 taken 1570962 times.
 2623230 if ( SQUARED(dz) > SQUARED(fi) )
1151 1052268 continue;
1152 }
1153
1154
1155
1156
2/2
✓ Branch 0 taken 1513922 times.
✓ Branch 1 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 0 taken 1019062 times.
✓ Branch 1 taken 494860 times.
 1513922 if ( fi < 0.0F ) {
1163
2/2
✓ Branch 0 taken 176282 times.
✓ Branch 1 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 0 taken 144696 times.
✓ Branch 1 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 0 taken 6702 times.
✓ Branch 1 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 0 taken 31500 times.
✓ Branch 1 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 0 taken 1519446 times.
✓ Branch 1 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 0 taken 991810 times.
✓ Branch 1 taken 527636 times.
 1519446 if ( fi < 0.0F ) {
1200
2/2
✓ Branch 0 taken 214244 times.
✓ Branch 1 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 0 taken 208862 times.
✓ Branch 1 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 0 taken 7010 times.
✓ Branch 1 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 0 taken 28828 times.
✓ Branch 1 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 0 taken 1423848 times.
✓ Branch 1 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 0 taken 148726 times.
✓ Branch 1 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 0 taken 208052 times.
✓ Branch 1 taken 1362910 times.
 1570962 if ( pb == 0 ) {
1254 pb = 1;
1255
2/2
✓ Branch 0 taken 87788 times.
✓ Branch 1 taken 120264 times.
 208052 } else if ( pc == 0 ) {
1256 87788 pc = 1;
1257 }
1258
1259
1260
1261 1570962 fi = (float) pa / (float) pc - (float) pd / (float) pb;
1262
1263
2/2
✓ Branch 0 taken 190 times.
✓ Branch 1 taken 1570772 times.
 1570962 if ( fi > 180.0F ) {
1264 190 fi = ( pa + pd + pb * 360 ) / 2.0F;
1265
2/2
✓ Branch 0 taken 166 times.
✓ Branch 1 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 0 taken 205516 times.
✓ Branch 1 taken 1365446 times.
 1570962 pb = ROUND(fi);
1272
2/2
✓ Branch 0 taken 30 times.
✓ Branch 1 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 0 taken 9100 times.
✓ Branch 1 taken 1561862 times.
✓ Branch 2 taken 6852 times.
✓ Branch 3 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 0 taken 269860 times.
✓ Branch 1 taken 1301102 times.
 1570962 if ( kk > TXS && kk < CTXS )
1288 269860 continue;
1289
1290
1291 found = 0;
1292
2/2
✓ Branch 0 taken 1305292 times.
✓ Branch 1 taken 3728 times.
 1309020 for ( kk = 0; kk < 2; kk++ ) {
1293 jj = 0;
1294 ll = 0;
1295
1296 do {
1297
4/4
✓ Branch 0 taken 1311134 times.
✓ Branch 1 taken 13175068 times.
✓ Branch 2 taken 13168290 times.
✓ Branch 3 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 0 taken 152413 times.
✓ Branch 1 taken 1317611 times.
✓ Branch 2 taken 152112 times.
✓ Branch 3 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 0 taken 1298195 times.
✓ Branch 1 taken 19717 times.
✓ Branch 2 taken 1297374 times.
✓ Branch 3 taken 821 times.
✗ Branch 4 not taken.
✓ Branch 5 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 0 taken 12904 times.
✓ Branch 1 taken 7634 times.
✓ Branch 2 taken 12620 times.
✓ Branch 3 taken 284 times.
 20538 } while ( jj < yl[kk][ii] && ll < yl[kk][tp] );
1320
2/2
✓ Branch 0 taken 7918 times.
✓ Branch 1 taken 1297374 times.
 1305292 if ( found )
1321 break;
1322 } /* END for kk */
1323
1324
2/2
✓ Branch 0 taken 3728 times.
✓ Branch 1 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 0 not taken.
✓ Branch 1 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 0 taken 1670712 times.
✓ Branch 1 taken 48570 times.
 1719282 for ( i = qh - 1; i > 0; i-- ) {
1347 1670712 n = qq[i] - 1;
1348
2/2
✓ Branch 0 taken 348756 times.
✓ Branch 1 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 0 taken 181606 times.
✓ Branch 1 taken 48570 times.
 230176 for ( i = dw - 1; i >= 0; i-- ) {
1356 181606 n = rr[i] - 1;
1357
2/2
✓ Branch 0 taken 89668 times.
✓ Branch 1 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 0 taken 813564 times.
✓ Branch 1 taken 48570 times.
 862134 while ( i >= 0 && j >= 0 ) {
1366
2/2
✓ Branch 0 taken 416108 times.
✓ Branch 1 taken 397456 times.
 813564 if ( nn[j] < mm[j] ) {
1367 416108 ++nn[j];
1368
1369
2/2
✓ Branch 0 taken 2025582 times.
✓ Branch 1 taken 25770 times.
 2051352 for ( i = ww - 1; i >= 0; i-- ) {
1370 2025582 int rt = rx[i];
1371
2/2
✓ Branch 0 taken 1261816 times.
✓ Branch 1 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 0 taken 1224702 times.
✓ Branch 1 taken 37114 times.
✓ Branch 2 taken 1058146 times.
✓ Branch 3 taken 166556 times.
✓ Branch 4 taken 1058146 times.
✓ Branch 5 taken 37114 times.
✓ Branch 6 taken 1021814 times.
✓ Branch 7 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 0 taken 682926 times.
✓ Branch 1 taken 80840 times.
✓ Branch 2 taken 577768 times.
✓ Branch 3 taken 105158 times.
✓ Branch 4 taken 577768 times.
✓ Branch 5 taken 80840 times.
✓ Branch 6 taken 495476 times.
✓ Branch 7 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 0 taken 390338 times.
✓ Branch 1 taken 25770 times.
 416108 if ( i >= 0 ) {
1401
2/2
✓ Branch 0 taken 1453638 times.
✓ Branch 1 taken 390338 times.
 1843976 for ( z = i + 1; z < ww; z++) {
1402 1453638 n = rr[z] - 1;
1403
2/2
✓ Branch 0 taken 1361814 times.
✓ Branch 1 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 0 taken 48570 times.
✗ Branch 1 not taken.
 48570 if ( tp > 1999 )
1419 break;
1420
1421 48570 dw = ww;
1422
1423
1424
2/2
✓ Branch 0 taken 25770 times.
✓ Branch 1 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 0 taken 22734 times.
✓ Branch 1 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 0 taken 9430 times.
✓ Branch 1 taken 22800 times.
 32230 for ( i = ww-1; i >= 0; i-- ) {
1440 9430 n = rx[i];
1441
2/2
✓ Branch 0 taken 4726 times.
✓ Branch 1 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 0 taken 26 times.
✗ Branch 1 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 0 taken 282882 times.
✓ Branch 1 taken 39018770 times.
 39301652 if ( n == 0 && t == 0 ) {
1507
1508
1509
2/2
✓ Branch 0 taken 282426 times.
✓ Branch 1 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 0 not taken.
✓ Branch 1 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 0 taken 26523164 times.
✓ Branch 1 taken 12495606 times.
 39018770 if ( n == l ) {
1542
1543
2/2
✓ Branch 0 taken 1387906 times.
✓ Branch 1 taken 25135258 times.
 26523164 if ( sc[kx-1] != ftt ) {
1544
2/2
✓ Branch 0 taken 1387830 times.
✓ Branch 1 taken 76 times.
 1387906 if ( zz[kx-1] == 1000 ) {
1545
1/2
✗ Branch 0 not taken.
✓ Branch 1 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 26523164 return;
1562 } /* END if ( n == l ) */
1563
1564
1565
1566
1567
1568
2/2
✓ Branch 0 taken 51042 times.
✓ Branch 1 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 0 taken 32752 times.
✓ Branch 1 taken 18290 times.
 51042 if ( n ) {
1583 32752 b = cp[ kz - 1 ];
1584
2/2
✓ Branch 0 taken 4704 times.
✓ Branch 1 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 0 taken 48520 times.
✓ Branch 1 taken 5504 times.
 54024 for ( i = 0; i < lim; i++ ) {
1613
2/2
✓ Branch 0 taken 21272 times.
✓ Branch 1 taken 27248 times.
 48520 if ( *lptr++ == l ) {
1614 notfound = 0;
1615 break;
1616 }
1617 }
1618
2/2
✓ Branch 0 taken 5504 times.
✓ Branch 1 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 0 taken 26520 times.
✓ Branch 1 taken 24522 times.
 51042 if ( t ) {
1628 26520 b = rp[ l - 1 ];
1629
2/2
✓ Branch 0 taken 4726 times.
✓ Branch 1 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 0 taken 35018 times.
✓ Branch 1 taken 5086 times.
 40104 for ( i = 0; i < lim; i++ ) {
1659
2/2
✓ Branch 0 taken 13584 times.
✓ Branch 1 taken 21434 times.
 35018 if ( *lptr++ == kz ) {
1660 notfound = 0;
1661 break;
1662 }
1663 }
1664
2/2
✓ Branch 0 taken 5086 times.
✓ Branch 1 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 0 taken 16672 times.
✓ Branch 1 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 0 taken 16540 times.
✓ Branch 1 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 0 taken 3284 times.
✓ Branch 1 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 0 taken 3070 times.
✓ Branch 1 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 0 taken 3070 times.
✓ Branch 1 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 0 not taken.
✓ Branch 1 taken 3070 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 3070 while ( rp[jj] < sct[kk][t] && jj < j )
1717 ✗ jj++;
1718
1/4
✓ Branch 0 taken 3070 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 3070 while ( rp[jj] > sct[kk][t] && kk < bz_y[t] )
1719 ✗ kk++;
1720
4/6
✓ Branch 0 taken 3070 times.
✓ Branch 1 taken 3070 times.
✓ Branch 2 taken 3070 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 3070 times.
✗ Branch 5 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 0 taken 3070 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 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 0 taken 3202 times.
✓ Branch 1 taken 3202 times.
 6404 for ( i = n-1; i < lim; i++ ) {
1738 3202 tot += ct[ sct[i][t] ];
1739 }
1740
1741
2/2
✓ Branch 0 taken 3152 times.
✓ Branch 1 taken 3202 times.
 6354 for ( i = 0; i < b; i++ ) {
1742 3152 tot += ct[ sct[0][i] ];
1743 }
1744
1745
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 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 0 not taken.
✓ Branch 1 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 0 taken 50 times.
✓ Branch 1 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 0 taken 3070 times.
✓ Branch 1 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 0 taken 6140 times.
✓ Branch 1 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