| 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: BZ_SORT.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 sorting routines responsible for supporting the | ||
| 54 | Bozorth3 fingerprint matching algorithm. | ||
| 55 | |||
| 56 | *********************************************************************** | ||
| 57 | |||
| 58 | ROUTINES: | ||
| 59 | #cat: sort_quality_decreasing - comparison function passed to stdlib | ||
| 60 | #cat: qsort() used to sort minutia qualities | ||
| 61 | #cat: sort_x_y - comparison function passed to stdlib qsort() used | ||
| 62 | #cat: to sort minutia coordinates increasing first on x | ||
| 63 | #cat: then on y | ||
| 64 | #cat: sort_order_decreasing - calls a custom quicksort that sorts | ||
| 65 | #cat: a list of integers in decreasing order | ||
| 66 | |||
| 67 | ***********************************************************************/ | ||
| 68 | |||
| 69 | #include <stdio.h> | ||
| 70 | #include <bozorth.h> | ||
| 71 | |||
| 72 | /* These are now externally defined in bozorth.h */ | ||
| 73 | /* extern FILE * stderr; */ | ||
| 74 | /* extern char * get_progname( void ); */ | ||
| 75 | |||
| 76 | /***********************************************************************/ | ||
| 77 | |||
| 78 | /***********************************************************************/ | ||
| 79 | 9302 | int sort_x_y( const void * a, const void * b ) | |
| 80 | { | ||
| 81 | 9302 | struct minutiae_struct * af; | |
| 82 | 9302 | struct minutiae_struct * bf; | |
| 83 | |||
| 84 | 9302 | af = (struct minutiae_struct *) a; | |
| 85 | 9302 | bf = (struct minutiae_struct *) b; | |
| 86 | |||
| 87 |
2/2✓ Branch 0 (2→3) taken 679 times.
✓ Branch 1 (2→7) taken 8623 times.
|
9302 | if ( af->col[0] < bf->col[0] ) |
| 88 | return -1; | ||
| 89 |
1/2✓ Branch 0 (3→4) taken 679 times.
✗ Branch 1 (3→7) not taken.
|
679 | if ( af->col[0] > bf->col[0] ) |
| 90 | return 1; | ||
| 91 | |||
| 92 |
1/2✓ Branch 0 (4→5) taken 679 times.
✗ Branch 1 (4→7) not taken.
|
679 | if ( af->col[1] < bf->col[1] ) |
| 93 | return -1; | ||
| 94 |
1/2✓ Branch 0 (5→6) taken 679 times.
✗ Branch 1 (5→7) not taken.
|
679 | if ( af->col[1] > bf->col[1] ) |
| 95 | 679 | return 1; | |
| 96 | |||
| 97 | return 0; | ||
| 98 | } | ||
| 99 | |||
| 100 | /******************************************************** | ||
| 101 | qsort_decreasing() - quicksort an array of integers in decreasing | ||
| 102 | order [based on multisort.c, by Michael Garris | ||
| 103 | and Ted Zwiesler, 1986] | ||
| 104 | ********************************************************/ | ||
| 105 | /* Used by custom quicksort code below */ | ||
| 106 | |||
| 107 | /***********************************************************************/ | ||
| 108 | /* return values: 0 == successful, 1 == error */ | ||
| 109 | |||
| 110 | /***********************************************************************/ | ||
| 111 | /* return values: 0 == successful, 1 == error */ | ||
| 112 | |||
| 113 | /***********************************************************************/ | ||
| 114 | /******************************************************************* | ||
| 115 | select_pivot() | ||
| 116 | selects a pivot from a list being sorted using the Singleton Method. | ||
| 117 | *******************************************************************/ | ||
| 118 | |||
| 119 | /***********************************************************************/ | ||
| 120 | /******************************************************** | ||
| 121 | partition_dec() | ||
| 122 | Inputs a pivot element making comparisons and swaps with other elements in a list, | ||
| 123 | until pivot resides at its correct position in the list. | ||
| 124 | ********************************************************/ | ||
| 125 | |||
| 126 | /***********************************************************************/ | ||
| 127 | /******************************************************** | ||
| 128 | qsort_decreasing() | ||
| 129 | This procedure inputs a pointer to an index_struct, the subscript of an index array to be | ||
| 130 | sorted, a left subscript pointing to where the sort is to begin in the index array, and a right | ||
| 131 | subscript where to end. This module invokes a decreasing quick-sort sorting the index array from l to r. | ||
| 132 | ********************************************************/ | ||
| 133 | /* return values: 0 == successful, 1 == error */ | ||
| 134 | |||
| 135 | /***********************************************************************/ | ||
| 136 | /* return values: 0 == successful, 1 == error */ | ||
| 137 |