GCC Code Coverage Report

Directory: ./
File: libfprint/nbis/mindtct/shape.c
Date: 2024-05-04 14:54:39
Exec Total Coverage
Lines: 46 49 93.9%
Functions: 4 4 100.0%
Branches: 12 14 85.7%
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 /***********************************************************************
46 LIBRARY: LFS - NIST Latent Fingerprint System
47
48 FILE: SHAPE.C
49 AUTHOR: Michael D. Garris
50 DATE: 05/11/1999
51 UPDATED: 03/16/2005 by MDG
52
53 Contains routines responsible for creating and manipulating
54 shape stuctures as part of the NIST Latent Fingerprint System (LFS).
55
56 ***********************************************************************
57 ROUTINES:
58 alloc_shape()
59 free_shape()
60 dump_shape()
61 shape_from_contour()
62 sort_row_on_x()
63 ***********************************************************************/
64
65 #include <stdio.h>
66 #include <lfs.h>
67
68 /*************************************************************************
69 **************************************************************************
70 #cat: alloc_shape - Allocates and initializes a shape structure given the
71 #cat: the X and Y limits of the shape.
72
73 Input:
74 xmin - left-most x-coord in shape
75 ymin - top-most y-coord in shape
76 xmax - right-most x-coord in shape
77 ymax - bottom-most y-coord in shape
78 Output:
79 oshape - pointer to the allocated & initialized shape structure
80 Return Code:
81 Zero - Shape successfully allocated and initialized
82 Negative - System error
83 **************************************************************************/
84 2980 int alloc_shape(SHAPE **oshape, const int xmin, const int ymin,
85 const int xmax, const int ymax)
86 {
87 2980 SHAPE *shape;
88 2980 int alloc_rows, alloc_pts;
89 2980 int i, y;
90
91 /* Compute allocation parameters. */
92 /* First, compute the number of scanlines spanned by the shape. */
93 2980 alloc_rows = ymax - ymin + 1;
94 /* Second, compute the "maximum" number of contour points possible */
95 /* on a row. Here we are allocating the maximum number of contiguous */
96 /* pixels on each row which will be sufficiently larger than the */
97 /* number of actual contour points. */
98 2980 alloc_pts = xmax - xmin + 1;
99
100 /* Allocate the shape structure. */
101 2980 shape = (SHAPE *)g_malloc(sizeof(SHAPE));
102
103 /* Allocate the list of row pointers. We now this number will fit */
104 /* the shape exactly. */
105 2980 shape->rows = (ROW **)g_malloc(alloc_rows * sizeof(ROW *));
106
107 /* Initialize the shape structure's attributes. */
108 2980 shape->ymin = ymin;
109 2980 shape->ymax = ymax;
110 /* The number of allocated rows will be exactly the number of */
111 /* assigned rows for the shape. */
112 2980 shape->alloc = alloc_rows;
113 2980 shape->nrows = alloc_rows;
114
115 /* Foreach row in the shape... */
116
2/2
✓ Branch 0 taken 14050 times.
✓ Branch 1 taken 2980 times.
 17030 for(i = 0, y = ymin; i < alloc_rows; i++, y++){
117 /* Allocate a row structure and store it in its respective position */
118 /* in the shape structure's list of row pointers. */
119 14050 shape->rows[i] = (ROW *)g_malloc(sizeof(ROW));
120
121 /* Allocate the current rows list of x-coords. */
122 14050 shape->rows[i]->xs = (int *)g_malloc(alloc_pts * sizeof(int));
123
124 /* Initialize the current row structure's attributes. */
125 14050 shape->rows[i]->y = y;
126 14050 shape->rows[i]->alloc = alloc_pts;
127 /* There are initially ZERO points assigned to the row. */
128 14050 shape->rows[i]->npts = 0;
129 }
130
131 /* Assign structure to output pointer. */
132 2980 *oshape = shape;
133
134 /* Return normally. */
135 2980 return(0);
136 }
137
138 /*************************************************************************
139 **************************************************************************
140 #cat: free_shape - Deallocates a shape structure and all its allocated
141 #cat: attributes.
142
143 Input:
144 shape - pointer to the shape structure to be deallocated
145 **************************************************************************/
146 2980 void free_shape(SHAPE *shape)
147 {
148 2980 int i;
149
150 /* Foreach allocated row in the shape ... */
151
2/2
✓ Branch 0 taken 14050 times.
✓ Branch 1 taken 2980 times.
 17030 for(i = 0; i < shape->alloc; i++){
152 /* Deallocate the current row's list of x-coords. */
153 14050 g_free(shape->rows[i]->xs);
154 /* Deallocate the current row structure. */
155 14050 g_free(shape->rows[i]);
156 }
157
158 /* Deallocate the list of row pointers. */
159 2980 g_free(shape->rows);
160 /* Deallocate the shape structure. */
161 2980 g_free(shape);
162 2980 }
163
164 /*************************************************************************
165 **************************************************************************
166 #cat: dump_shape - Takes an initialized shape structure and dumps its contents
167 #cat: as formatted text to the specified open file pointer.
168
169 Input:
170 shape - shape structure to be dumped
171 Output:
172 fpout - open file pointer to be written to
173 **************************************************************************/
174
175 /*************************************************************************
176 **************************************************************************
177 #cat: shape_from_contour - Converts a contour list that has been determined
178 #cat: to form a complete loop into a shape representation where
179 #cat: the contour points on each contiguous scanline of the shape
180 #cat: are stored in left-to-right order.
181
182 Input:
183 contour_x - x-coord list for loop's contour points
184 contour_y - y-coord list for loop's contour points
185 ncontour - number of points in contour
186 Output:
187 oshape - points to the resulting shape structure
188 Return Code:
189 Zero - shape successfully derived
190 Negative - system error
191 **************************************************************************/
192 2980 int shape_from_contour(SHAPE **oshape, const int *contour_x,
193 const int *contour_y, const int ncontour)
194 {
195 2980 SHAPE *shape;
196 2980 ROW *row;
197 2980 int ret, i, xmin, ymin, xmax, ymax;
198
199 /* Find xmin, ymin, xmax, ymax on contour. */
200 2980 contour_limits(&xmin, &ymin, &xmax, &ymax,
201 contour_x, contour_y, ncontour);
202
203 /* Allocate and initialize a shape structure. */
204
1/2
✓ Branch 1 taken 2980 times.
✗ Branch 2 not taken.
 2980 if((ret = alloc_shape(&shape, xmin, ymin, xmax, ymax)))
205 /* If system error, then return error code. */
206 return(ret);
207
208 /* Foreach point on contour ... */
209
2/2
✓ Branch 0 taken 41640 times.
✓ Branch 1 taken 2980 times.
 44620 for(i = 0; i < ncontour; i++){
210 /* Add point to corresponding row. */
211 /* First set a pointer to the current row. We need to subtract */
212 /* ymin because the rows are indexed relative to the top-most */
213 /* scanline in the shape. */
214 41640 row = shape->rows[contour_y[i]-ymin];
215
216 /* It is possible with complex shapes to reencounter points */
217 /* already visited on a contour, especially at "pinching" points */
218 /* along the contour. So we need to test to see if a point has */
219 /* already been stored in the row. If not in row list already ... */
220
2/2
✓ Branch 1 taken 41614 times.
✓ Branch 2 taken 26 times.
 41640 if(in_int_list(contour_x[i], row->xs, row->npts) < 0){
221 /* If row is full ... */
222
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 41614 times.
 41614 if(row->npts >= row->alloc){
223 /* This should never happen becuase we have allocated */
224 /* based on shape bounding limits. */
225 ✗ g_free(shape);
226 ✗ fprintf(stderr,
227 "ERROR : shape_from_contour : row overflow\n");
228 ✗ return(-260);
229 }
230 /* Assign the x-coord of the current contour point to the row */
231 /* and bump the row's point counter. All the contour points */
232 /* on the same row share the same y-coord. */
233 41614 row->xs[row->npts++] = contour_x[i];
234 }
235 /* Otherwise, point is already stored in row, so ignore. */
236 }
237
238 /* Foreach row in the shape. */
239
2/2
✓ Branch 0 taken 14050 times.
✓ Branch 1 taken 2980 times.
 17030 for(i = 0; i < shape->nrows; i++)
240 /* Sort row points increasing on their x-coord. */
241 14050 sort_row_on_x(shape->rows[i]);
242
243 /* Assign shape structure to output pointer. */
244 2980 *oshape = shape;
245
246 /* Return normally. */
247 2980 return(0);
248 }
249
250 /*************************************************************************
251 **************************************************************************
252 #cat: sort_row_on_x - Takes a row structure and sorts its points left-to-
253 #cat: right on X.
254
255 Input:
256 row - row structure to be sorted
257 Output:
258 row - row structure with points in sorted order
259 **************************************************************************/
260 14050 void sort_row_on_x(ROW *row)
261 {
262 /* Conduct a simple increasing bubble sort on the x-coords */
263 /* in the given row. A bubble sort is satisfactory as the */
264 /* number of points will be relatively small. */
265 14050 bubble_sort_int_inc(row->xs, row->npts);
266 14050 }
267
268