GCC Code Coverage Report

Directory: ./
File: libfprint/fpi-assembling.c
Date: 2024-05-04 14:54:39
Exec Total Coverage
Lines: 200 203 98.5%
Functions: 10 10 100.0%
Branches: 75 92 81.5%
Line Branch Exec Source
1 /*
2 * Image assembling routines
3 * Copyright (C) 2007-2008 Daniel Drake <dsd@gentoo.org>
4 * Copyright (C) 2013 Arseniy Lartsev <arseniy@chalmers.se>
5 * Copyright (C) 2015 Vasily Khoruzhick <anarsoul@gmail.com>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 */
21
22 #define FP_COMPONENT "assembling"
23
24 #include "fpi-log.h"
25 #include "fpi-image.h"
26
27 #include <string.h>
28
29 #include "fpi-assembling.h"
30
31 /**
32 * SECTION:fpi-assembling
33 * @title: Image frame assembly
34 * @short_description: Image frame assembly helpers
35 *
36 * Those are the helpers to manipulate capture data from fingerprint readers
37 * into a uniform image that can be further processed. This is usually used
38 * by drivers for devices which have a small sensor and thus need to capture
39 * data in small stripes.
40 */
41
42 static unsigned int
43 181968 calc_error (struct fpi_frame_asmbl_ctx *ctx,
44 struct fpi_frame *first_frame,
45 struct fpi_frame *second_frame,
46 int dx,
47 int dy)
48 {
49 181968 unsigned int width, height;
50 181968 unsigned int x1, y1, x2, y2, err, i, j;
51
52 181968 width = ctx->frame_width - (dx > 0 ? dx : -dx);
53 181968 height = ctx->frame_height - dy;
54
55
1/2
✓ Branch 0 taken 181968 times.
✗ Branch 1 not taken.
 181968 if (height == 0 || width == 0)
56 return INT_MAX;
57
58 y1 = 0;
59 y2 = dy;
60 i = 0;
61 err = 0;
62 2715120 do
63 {
64 2715120 x1 = dx < 0 ? 0 : dx;
65
2/2
✓ Branch 0 taken 1357560 times.
✓ Branch 1 taken 1357560 times.
 2715120 x2 = dx < 0 ? -dx : 0;
66 j = 0;
67
68 344962368 do
69 {
70 344962368 unsigned char v1, v2;
71
72
73 344962368 v1 = ctx->get_pixel (ctx, first_frame, x1, y1);
74 344962368 v2 = ctx->get_pixel (ctx, second_frame, x2, y2);
75
2/2
✓ Branch 0 taken 136630760 times.
✓ Branch 1 taken 208331608 times.
 344962368 err += v1 > v2 ? v1 - v2 : v2 - v1;
76 344962368 j++;
77 344962368 x1++;
78 344962368 x2++;
79
80 }
81
2/2
✓ Branch 0 taken 342247248 times.
✓ Branch 1 taken 2715120 times.
 344962368 while (j < width);
82 2715120 i++;
83 2715120 y1++;
84 2715120 y2++;
85 }
86
2/2
✓ Branch 0 taken 2533152 times.
✓ Branch 1 taken 181968 times.
 2715120 while (i < height);
87
88 /* Normalize error */
89 181968 err *= (ctx->frame_height * ctx->frame_width);
90 181968 err /= (height * width);
91
92 181968 return err;
93 }
94
95 /* This function is rather CPU-intensive. It's better to use hardware
96 * to detect movement direction when possible.
97 */
98 static void
99 519 find_overlap (struct fpi_frame_asmbl_ctx *ctx,
100 struct fpi_frame *first_frame,
101 struct fpi_frame *second_frame,
102 int *dx_out,
103 int *dy_out,
104 unsigned int *min_error)
105 {
106 519 int dx, dy;
107 519 unsigned int err;
108
109 519 *min_error = 255 * ctx->frame_height * ctx->frame_width;
110
111 /* Seeking in horizontal and vertical dimensions,
112 * for horizontal dimension we'll check only 8 pixels
113 * in both directions. For vertical direction diff is
114 * rarely less than 2, so start with it.
115 */
116
2/2
✓ Branch 0 taken 11373 times.
✓ Branch 1 taken 519 times.
 11892 for (dy = 2; dy < ctx->frame_height; dy++)
117 {
118
2/2
✓ Branch 0 taken 181968 times.
✓ Branch 1 taken 11373 times.
 193341 for (dx = -8; dx < 8; dx++)
119 {
120 181968 err = calc_error (ctx, first_frame, second_frame,
121 dx, dy);
122
2/2
✓ Branch 0 taken 6016 times.
✓ Branch 1 taken 175952 times.
 181968 if (err < *min_error)
123 {
124 6016 *min_error = err;
125 6016 *dx_out = -dx;
126 6016 *dy_out = dy;
127 }
128 }
129 }
130 519 }
131
132 static unsigned int
133 17 do_movement_estimation (struct fpi_frame_asmbl_ctx *ctx,
134 GSList *stripes, gboolean reverse)
135 {
136 17 GSList *l;
137 17 GTimer *timer;
138 17 guint num_frames = 1;
139 17 struct fpi_frame *prev_stripe;
140 17 unsigned int min_error;
141 /* Max error is width * height * 255, for AES2501 which has the largest
142 * sensor its 192*16*255 = 783360. So for 32bit value it's ~5482 frame before
143 * we might get int overflow. Use 64bit value here to prevent integer overflow
144 */
145 17 unsigned long long total_error = 0;
146
147 17 timer = g_timer_new ();
148
149 /* Skip the first frame */
150 17 prev_stripe = stripes->data;
151
152
2/2
✓ Branch 0 taken 519 times.
✓ Branch 1 taken 17 times.
 536 for (l = stripes->next; l != NULL; l = l->next, num_frames++)
153 {
154 519 struct fpi_frame *cur_stripe = l->data;
155
156
2/2
✓ Branch 0 taken 176 times.
✓ Branch 1 taken 343 times.
 519 if (reverse)
157 {
158 176 find_overlap (ctx, prev_stripe, cur_stripe,
159 &cur_stripe->delta_x, &cur_stripe->delta_y,
160 &min_error);
161 176 cur_stripe->delta_y = -cur_stripe->delta_y;
162 176 cur_stripe->delta_x = -cur_stripe->delta_x;
163 }
164 else
165 {
166 343 find_overlap (ctx, cur_stripe, prev_stripe,
167 &cur_stripe->delta_x, &cur_stripe->delta_y,
168 &min_error);
169 }
170 519 total_error += min_error;
171
172 519 prev_stripe = cur_stripe;
173 }
174
175 17 g_timer_stop (timer);
176 17 fp_dbg ("calc delta completed in %f secs", g_timer_elapsed (timer, NULL));
177 17 g_timer_destroy (timer);
178
179 17 return total_error / num_frames;
180 }
181
182 /**
183 * fpi_do_movement_estimation:
184 * @ctx: #fpi_frame_asmbl_ctx - frame assembling context
185 * @stripes: a singly-linked list of #fpi_frame
186 *
187 * fpi_do_movement_estimation() estimates the movement between adjacent
188 * frames, populating @delta_x and @delta_y values for each #fpi_frame.
189 *
190 * This function is used for devices that don't do movement estimation
191 * in hardware. If hardware movement estimation is supported, the driver
192 * should populate @delta_x and @delta_y instead.
193 */
194 void
195 6 fpi_do_movement_estimation (struct fpi_frame_asmbl_ctx *ctx,
196 GSList *stripes)
197 {
198 6 int err, rev_err;
199
200 6 err = do_movement_estimation (ctx, stripes, FALSE);
201 6 rev_err = do_movement_estimation (ctx, stripes, TRUE);
202 6 fp_dbg ("errors: %d rev: %d", err, rev_err);
203
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
 6 if (err < rev_err)
204 5 do_movement_estimation (ctx, stripes, FALSE);
205 6 }
206
207 static inline void
208 182 aes_blit_stripe (struct fpi_frame_asmbl_ctx *ctx,
209 FpImage *img,
210 struct fpi_frame *stripe,
211 int x, int y)
212 {
213 182 unsigned int ix1, iy1;
214 182 unsigned int fx1, fy1;
215 182 unsigned int fx, fy, ix, iy;
216
217 /* Select starting point inside image and frame */
218
2/2
✓ Branch 0 taken 32 times.
✓ Branch 1 taken 150 times.
 182 if (x < 0)
219 {
220 32 ix1 = 0;
221 32 fx1 = -x;
222 }
223 else
224 {
225 150 ix1 = x;
226 150 fx1 = 0;
227 }
228
229
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 182 times.
 182 if (y < 0)
230 {
231 ✗ iy1 = 0;
232 ✗ fy1 = -y;
233 }
234 else
235 {
236 182 iy1 = y;
237 182 fy1 = 0;
238 }
239
240
3/4
✓ Branch 0 taken 4483 times.
✓ Branch 1 taken 182 times.
✓ Branch 2 taken 4483 times.
✗ Branch 3 not taken.
 4665 for (fy = fy1, iy = iy1; fy < ctx->frame_height && iy < img->height; fy++, iy++)
241
4/4
✓ Branch 0 taken 609788 times.
✓ Branch 1 taken 3628 times.
✓ Branch 2 taken 608933 times.
✓ Branch 3 taken 855 times.
 613416 for (fx = fx1, ix = ix1; fx < ctx->frame_width && ix < img->width; fx++, ix++)
242 608933 img->data[ix + (iy * img->width)] = ctx->get_pixel (ctx, stripe, fx, fy);
243 182 }
244
245 /**
246 * fpi_assemble_frames:
247 * @ctx: #fpi_frame_asmbl_ctx - frame assembling context
248 * @stripes: linked list of #fpi_frame
249 *
250 * fpi_assemble_frames() assembles individual frames into a single image.
251 * It expects @delta_x and @delta_y of #fpi_frame to be populated.
252 *
253 * Returns: a newly allocated #fp_img.
254 */
255 FpImage *
256 6 fpi_assemble_frames (struct fpi_frame_asmbl_ctx *ctx,
257 GSList *stripes)
258 {
259 6 GSList *l;
260 6 FpImage *img;
261 6 int height = 0;
262 6 int y, x;
263 6 gboolean reverse = FALSE;
264 6 struct fpi_frame *fpi_frame;
265
266 //FIXME g_return_if_fail
267
1/2
✓ Branch 0 taken 6 times.
✗ Branch 1 not taken.
 6 g_return_val_if_fail (stripes != NULL, NULL);
268
269 /* No offset for 1st image */
270 6 fpi_frame = stripes->data;
271 6 fpi_frame->delta_x = 0;
272 6 fpi_frame->delta_y = 0;
273
2/2
✓ Branch 0 taken 182 times.
✓ Branch 1 taken 6 times.
 188 for (l = stripes; l != NULL; l = l->next)
274 {
275 182 fpi_frame = l->data;
276
277 182 height += fpi_frame->delta_y;
278 }
279
280 6 fp_dbg ("height is %d", height);
281
282
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 5 times.
 6 if (height < 0)
283 {
284 1 reverse = TRUE;
285 1 height = -height;
286 }
287
288 /* For last frame */
289 6 height += ctx->frame_height;
290
291 /* Create buffer big enough for max image */
292 6 img = fp_image_new (ctx->image_width, height);
293 6 img->flags = FPI_IMAGE_COLORS_INVERTED;
294
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 1 times.
 6 img->flags |= reverse ? 0 : FPI_IMAGE_H_FLIPPED | FPI_IMAGE_V_FLIPPED;
295 6 img->width = ctx->image_width;
296 6 img->height = height;
297
298 /* Assemble stripes */
299
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 5 times.
 6 y = reverse ? (height - ctx->frame_height) : 0;
300 6 x = ((int) ctx->image_width - (int) ctx->frame_width) / 2;
301
302
2/2
✓ Branch 0 taken 182 times.
✓ Branch 1 taken 6 times.
 188 for (l = stripes; l != NULL; l = l->next)
303 {
304 182 fpi_frame = l->data;
305
306 182 y += fpi_frame->delta_y;
307 182 x += fpi_frame->delta_x;
308
309 182 aes_blit_stripe (ctx, img, fpi_frame, x, y);
310 }
311
312 return img;
313 }
314
315 static int
316 130402 cmpint (const void *p1, const void *p2, gpointer data)
317 {
318 130402 int a = *((int *) p1);
319 130402 int b = *((int *) p2);
320
321
2/2
✓ Branch 0 taken 102943 times.
✓ Branch 1 taken 27459 times.
 130402 if (a < b)
322 return -1;
323
2/2
✓ Branch 0 taken 67574 times.
✓ Branch 1 taken 35369 times.
 102943 else if (a == b)
324 return 0;
325 else
326 67574 return 1;
327 }
328
329 static void
330 2 median_filter (int *data, int size, int filtersize)
331 {
332 2 int i;
333 2 int *result = (int *) g_malloc0 (size * sizeof (int));
334 2 int *sortbuf = (int *) g_malloc0 (filtersize * sizeof (int));
335
336
2/2
✓ Branch 1 taken 1634 times.
✓ Branch 2 taken 2 times.
 1638 for (i = 0; i < size; i++)
337 {
338 1634 int i1 = i - (filtersize - 1) / 2;
339 1634 int i2 = i + (filtersize - 1) / 2;
340 1634 if (i1 < 0)
341 i1 = 0;
342
2/2
✓ Branch 0 taken 24 times.
✓ Branch 1 taken 1610 times.
 1634 if (i2 >= size)
343 24 i2 = size - 1;
344 1634 memmove (sortbuf, data + i1, (i2 - i1 + 1) * sizeof (int));
345 1634 g_qsort_with_data (sortbuf, i2 - i1 + 1, sizeof (int), cmpint, NULL);
346 1634 result[i] = sortbuf[(i2 - i1 + 1) / 2];
347 }
348 2 memmove (data, result, size * sizeof (int));
349 2 g_free (result);
350 2 g_free (sortbuf);
351 2 }
352
353 static void
354 1485 interpolate_lines (struct fpi_line_asmbl_ctx *ctx,
355 GSList *line1, gint32 y1_f,
356 GSList *line2, gint32 y2_f,
357 unsigned char *output, gint32 yi_f,
358 int size)
359 {
360 1485 int i;
361 1485 unsigned char p1, p2;
362
363
1/2
✓ Branch 0 taken 1485 times.
✗ Branch 1 not taken.
 1485 if (!line1 || !line2)
364 return;
365
366
2/2
✓ Branch 0 taken 168540 times.
✓ Branch 1 taken 1485 times.
 170025 for (i = 0; i < size; i++)
367 {
368 168540 gint unscaled;
369 168540 p1 = ctx->get_pixel (ctx, line1, i);
370 168540 p2 = ctx->get_pixel (ctx, line2, i);
371
372 168540 unscaled = (yi_f - y1_f) * p2 + (y2_f - yi_f) * p1;
373 168540 output[i] = (unscaled) / (y2_f - y1_f);
374 }
375 }
376
377 /**
378 * fpi_assemble_lines:
379 * @ctx: #fpi_frame_asmbl_ctx - frame assembling context
380 * @lines: linked list of lines
381 * @num_lines: number of items in @lines to process
382 *
383 * #fpi_assemble_lines assembles individual lines into a single image.
384 * It also rescales image to account variable swiping speed.
385 *
386 * Note that @num_lines might be shorter than the length of the list,
387 * if some lines should be skipped.
388 *
389 * Returns: a newly allocated #fp_img.
390 */
391 FpImage *
392 2 fpi_assemble_lines (struct fpi_line_asmbl_ctx *ctx,
393 GSList *lines, size_t num_lines)
394 {
395 /* Number of output lines per distance between two scanners */
396 2 int i;
397 2 GSList *row1, *row2;
398 /* The y coordinate is tracked as a 16.16 fixed point number. All
399 * variables postfixed with _f follow this format here and in
400 * interpolate_lines.
401 * We could also use floating point here, but using fixed point means
402 * we get consistent results across architectures.
403 */
404 2 gint32 y_f = 0;
405 2 int line_ind = 0;
406
1/4
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
 2 int *offsets = g_new0 (int, num_lines / 2);
407 2 unsigned char *output = g_malloc0 (ctx->line_width * ctx->max_height);
408 2 FpImage *img;
409
410
1/2
✓ Branch 0 taken 2 times.
✗ Branch 1 not taken.
 2 g_return_val_if_fail (lines != NULL, NULL);
411
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2 times.
 2 g_return_val_if_fail (num_lines >= 2, NULL);
412
413 2 fp_dbg ("%"G_GINT64_FORMAT, g_get_real_time ());
414
415 2 row1 = lines;
416
3/4
✓ Branch 1 taken 1636 times.
✓ Branch 2 taken 2 times.
✓ Branch 3 taken 1636 times.
✗ Branch 4 not taken.
 1640 for (i = 0; (i < num_lines - 1) && row1; i += 2)
417 {
418 1636 int bestmatch = i;
419 1636 int bestdiff = 0;
420 1636 int j, firstrow, lastrow;
421
422 1636 firstrow = i + 1;
423 1636 lastrow = MIN (i + ctx->max_search_offset, num_lines - 1);
424
425 1636 row2 = g_slist_next (row1);
426
2/2
✓ Branch 0 taken 151370 times.
✓ Branch 1 taken 1636 times.
 153006 for (j = firstrow; j <= lastrow; j++)
427 {
428 151370 int diff = ctx->get_deviation (ctx,
429 row1,
430 row2);
431
2/2
✓ Branch 0 taken 15182 times.
✓ Branch 1 taken 136188 times.
 151370 if ((j == firstrow) || (diff < bestdiff))
432 {
433 15182 bestdiff = diff;
434 15182 bestmatch = j;
435 }
436
1/2
✓ Branch 0 taken 151370 times.
✗ Branch 1 not taken.
 151370 row2 = g_slist_next (row2);
437 }
438 1636 offsets[i / 2] = bestmatch - i;
439 1636 fp_dbg ("%d", offsets[i / 2]);
440 1636 row1 = g_slist_next (row1);
441
1/2
✓ Branch 0 taken 1636 times.
✗ Branch 1 not taken.
 1636 if (row1)
442 1636 row1 = g_slist_next (row1);
443 }
444
445 2 median_filter (offsets, (num_lines / 2) - 1, ctx->median_filter_size);
446
447 2 fp_dbg ("offsets_filtered: %"G_GINT64_FORMAT, g_get_real_time ());
448
2/2
✓ Branch 1 taken 1636 times.
✓ Branch 2 taken 2 times.
 1640 for (i = 0; i <= (num_lines / 2) - 1; i++)
449 1636 fp_dbg ("%d", offsets[i]);
450 row1 = lines;
451
3/4
✓ Branch 0 taken 3271 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 3271 times.
✓ Branch 3 taken 2 times.
 6544 for (i = 0; i < num_lines - 1; i++, row1 = g_slist_next (row1))
452 {
453 3271 int offset = offsets[i / 2];
454
1/2
✓ Branch 0 taken 3271 times.
✗ Branch 1 not taken.
 3271 if (offset > 0)
455 {
456 3271 gint32 ynext_f = y_f + (ctx->resolution << 16) / offset;
457
2/2
✓ Branch 0 taken 1485 times.
✓ Branch 1 taken 3271 times.
 4756 while ((line_ind << 16) < ynext_f)
458 {
459
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1485 times.
 1485 if (line_ind > ctx->max_height - 1)
460 ✗ goto out;
461 1485 interpolate_lines (ctx,
462 row1, y_f,
463 g_slist_next (row1),
464 ynext_f,
465 1485 output + line_ind * ctx->line_width,
466 line_ind << 16,
467
1/2
✓ Branch 0 taken 1485 times.
✗ Branch 1 not taken.
 1485 ctx->line_width);
468 1485 line_ind++;
469 }
470 y_f = ynext_f;
471 }
472 }
473 2 out:
474 2 img = fp_image_new (ctx->line_width, line_ind);
475 2 img->height = line_ind;
476 2 img->width = ctx->line_width;
477 2 img->flags = FPI_IMAGE_V_FLIPPED;
478 2 memmove (img->data, output, ctx->line_width * line_ind);
479 2 g_free (offsets);
480 2 g_free (output);
481 2 return img;
482 }
483