1 /******************************************************************************
2
3 This file is part of the Export Control subset of the United States NIST
4 Biometric Image Software (NBIS) distribution:
5 http://fingerprint.nist.gov/NBIS/index.html
6
7 It is our understanding that this falls within ECCN 3D980, which covers
8 software associated with the development, production or use of certain
9 equipment controlled in accordance with U.S. concerns about crime control
10 practices in specific countries.
11
12 Therefore, this file should not be exported, or made available on fileservers,
13 except as allowed by U.S. export control laws.
14
15 Do not remove this notice.
16
17 ******************************************************************************/
18
19 /* NOTE: Despite the above notice (which I have not removed), this file is
20 * being legally distributed within libfprint; the U.S. Export Administration
21 * Regulations do not place export restrictions upon distribution of
22 * "publicly available technology and software", as stated in EAR section
23 * 734.3(b)(3)(i). libfprint qualifies as publicly available technology as per
24 * the definition in section 734.7(a)(1).
25 *
26 * For further information, see http://reactivated.net/fprint/US_export_control
27 */
28
29 /*******************************************************************************
30
31 License:
32 This software was developed at the National Institute of Standards and
33 Technology (NIST) by employees of the Federal Government in the course
34 of their official duties. Pursuant to title 17 Section 105 of the
35 United States Code, this software is not subject to copyright protection
36 and is in the public domain. NIST assumes no responsibility whatsoever for
37 its use by other parties, and makes no guarantees, expressed or implied,
38 about its quality, reliability, or any other characteristic.
39
40 Disclaimer:
41 This software was developed to promote biometric standards and biometric
42 technology testing for the Federal Government in accordance with the USA
43 PATRIOT Act and the Enhanced Border Security and Visa Entry Reform Act.
44 Specific hardware and software products identified in this software were used
45 in order to perform the software development. In no case does such
46 identification imply recommendation or endorsement by the National Institute
47 of Standards and Technology, nor does it imply that the products and equipment
48 identified are necessarily the best available for the purpose.
49
50 *******************************************************************************/
51
52 /***********************************************************************
53 LIBRARY: FING - NIST Fingerprint Systems Utilities
54
55 FILE: BZ_SORT.C
56 ALGORITHM: Allan S. Bozorth (FBI)
57 MODIFICATIONS: Michael D. Garris (NIST)
58 Stan Janet (NIST)
59 DATE: 09/21/2004
60
61 Contains sorting routines responsible for supporting the
62 Bozorth3 fingerprint matching algorithm.
63
64 ***********************************************************************
65
66 ROUTINES:
67 #cat: sort_quality_decreasing - comparison function passed to stdlib
68 #cat: qsort() used to sort minutia qualities
69 #cat: sort_x_y - comparison function passed to stdlib qsort() used
70 #cat: to sort minutia coordinates increasing first on x
71 #cat: then on y
72 #cat: sort_order_decreasing - calls a custom quicksort that sorts
73 #cat: a list of integers in decreasing order
74
75 ***********************************************************************/
76
77 #include <stdio.h>
78 #include <bozorth.h>
79
80 /* These are now externally defined in bozorth.h */
81 /* extern char * get_progname( void ); */
82
83 /***********************************************************************/
sort_quality_decreasing(const void * a,const void * b)84 int sort_quality_decreasing( const void * a, const void * b )
85 {
86 struct minutiae_struct * af;
87 struct minutiae_struct * bf;
88
89 af = (struct minutiae_struct *) a;
90 bf = (struct minutiae_struct *) b;
91
92 if ( af->col[3] > bf->col[3] )
93 return -1;
94 if ( af->col[3] < bf->col[3] )
95 return 1;
96 return 0;
97 }
98
99 /***********************************************************************/
sort_x_y(const void * a,const void * b)100 int sort_x_y( const void * a, const void * b )
101 {
102 struct minutiae_struct * af;
103 struct minutiae_struct * bf;
104
105 af = (struct minutiae_struct *) a;
106 bf = (struct minutiae_struct *) b;
107
108 if ( af->col[0] < bf->col[0] )
109 return -1;
110 if ( af->col[0] > bf->col[0] )
111 return 1;
112
113 if ( af->col[1] < bf->col[1] )
114 return -1;
115 if ( af->col[1] > bf->col[1] )
116 return 1;
117
118 return 0;
119 }
120
121 /********************************************************
122 qsort_decreasing() - quicksort an array of integers in decreasing
123 order [based on multisort.c, by Michael Garris
124 and Ted Zwiesler, 1986]
125 ********************************************************/
126 /* Used by custom quicksort code below */
127 static int stack[BZ_STACKSIZE];
128 static int * stack_pointer = stack;
129
130 /***********************************************************************/
131 /* return values: 0 == successful, 1 == error */
popstack(int * popval)132 static int popstack( int *popval )
133 {
134 if ( --stack_pointer < stack ) {
135 fprintf( stderr, "%s: ERROR: popstack(): stack underflow\n", get_progname() );
136 return 1;
137 }
138
139 *popval = *stack_pointer;
140 return 0;
141 }
142
143 /***********************************************************************/
144 /* return values: 0 == successful, 1 == error */
pushstack(int position)145 static int pushstack( int position )
146 {
147 *stack_pointer++ = position;
148 if ( stack_pointer > ( stack + BZ_STACKSIZE ) ) {
149 fprintf( stderr, "%s: ERROR: pushstack(): stack overflow\n", get_progname() );
150 return 1;
151 }
152 return 0;
153 }
154
155 /***********************************************************************/
156 /*******************************************************************
157 select_pivot()
158 selects a pivot from a list being sorted using the Singleton Method.
159 *******************************************************************/
select_pivot(struct cell v[],int left,int right)160 static int select_pivot( struct cell v[], int left, int right )
161 {
162 int midpoint;
163
164
165 midpoint = ( left + right ) / 2;
166 if ( v[left].index <= v[midpoint].index ) {
167 if ( v[midpoint].index <= v[right].index ) {
168 return midpoint;
169 } else {
170 if ( v[right].index > v[left].index ) {
171 return right;
172 } else {
173 return left;
174 }
175 }
176 } else {
177 if ( v[left].index < v[right].index ) {
178 return left;
179 } else {
180 if ( v[right].index < v[midpoint].index ) {
181 return midpoint;
182 } else {
183 return right;
184 }
185 }
186 }
187 }
188
189 /***********************************************************************/
190 /********************************************************
191 partition_dec()
192 Inputs a pivot element making comparisons and swaps with other elements in a list,
193 until pivot resides at its correct position in the list.
194 ********************************************************/
partition_dec(struct cell v[],int * llen,int * rlen,int * ll,int * lr,int * rl,int * rr,int p,int l,int r)195 static void partition_dec( struct cell v[], int *llen, int *rlen, int *ll, int *lr, int *rl, int *rr, int p, int l, int r )
196 {
197 #define iswap(a,b) { int itmp = (a); a = (b); b = itmp; }
198
199 *ll = l;
200 *rr = r;
201 while ( 1 ) {
202 if ( l < p ) {
203 if ( v[l].index < v[p].index ) {
204 iswap( v[l].index, v[p].index )
205 iswap( v[l].item, v[p].item )
206 p = l;
207 } else {
208 l++;
209 }
210 } else {
211 if ( r > p ) {
212 if ( v[r].index > v[p].index ) {
213 iswap( v[r].index, v[p].index )
214 iswap( v[r].item, v[p].item )
215 p = r;
216 l++;
217 } else {
218 r--;
219 }
220 } else {
221 *lr = p - 1;
222 *rl = p + 1;
223 *llen = *lr - *ll + 1;
224 *rlen = *rr - *rl + 1;
225 break;
226 }
227 }
228 }
229 }
230
231 /***********************************************************************/
232 /********************************************************
233 qsort_decreasing()
234 This procedure inputs a pointer to an index_struct, the subscript of an index array to be
235 sorted, a left subscript pointing to where the sort is to begin in the index array, and a right
236 subscript where to end. This module invokes a decreasing quick-sort sorting the index array from l to r.
237 ********************************************************/
238 /* return values: 0 == successful, 1 == error */
qsort_decreasing(struct cell v[],int left,int right)239 static int qsort_decreasing( struct cell v[], int left, int right )
240 {
241 int pivot;
242 int llen, rlen;
243 int lleft, lright, rleft, rright;
244
245
246 if ( pushstack( left ))
247 return 1;
248 if ( pushstack( right ))
249 return 2;
250 while ( stack_pointer != stack ) {
251 if (popstack(&right))
252 return 3;
253 if (popstack(&left ))
254 return 4;
255 if ( right - left > 0 ) {
256 pivot = select_pivot( v, left, right );
257 partition_dec( v, &llen, &rlen, &lleft, &lright, &rleft, &rright, pivot, left, right );
258 if ( llen > rlen ) {
259 if ( pushstack( lleft ))
260 return 5;
261 if ( pushstack( lright ))
262 return 6;
263 if ( pushstack( rleft ))
264 return 7;
265 if ( pushstack( rright ))
266 return 8;
267 } else{
268 if ( pushstack( rleft ))
269 return 9;
270 if ( pushstack( rright ))
271 return 10;
272 if ( pushstack( lleft ))
273 return 11;
274 if ( pushstack( lright ))
275 return 12;
276 }
277 }
278 }
279 return 0;
280 }
281
282 /***********************************************************************/
283 /* return values: 0 == successful, 1 == error */
sort_order_decreasing(int values[],int num,int order[])284 int sort_order_decreasing(
285 int values[], /* INPUT: the unsorted values themselves */
286 int num, /* INPUT: the number of values */
287 int order[] /* OUTPUT: the order for each of the values if sorted */
288 )
289 {
290 int i;
291 struct cell * cells;
292
293
294 cells = (struct cell *) malloc( num * sizeof(struct cell) );
295 if ( cells == (struct cell *) NULL ){
296 fprintf( stderr, "%s: ERROR: malloc(): struct cell\n", get_progname() );
297 return 1;
298 }
299
300 for( i = 0; i < num; i++ ) {
301 cells[i].index = values[i];
302 cells[i].item = i;
303 }
304
305 if ( qsort_decreasing( cells, 0, num-1 ) < 0)
306 return 2;
307
308 for( i = 0; i < num; i++ ) {
309 order[i] = cells[i].item;
310 }
311
312 free( (void *) cells );
313
314 return 0;
315 }
316