1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * Input Multitouch Library
4  *
5  * Copyright (c) 2008-2010 Henrik Rydberg
6  */
7 
8 #include <linux/input/mt.h>
9 #include <linux/export.h>
10 #include <linux/slab.h>
11 #include "input-core-private.h"
12 
13 #define TRKID_SGN	((TRKID_MAX + 1) >> 1)
14 
copy_abs(struct input_dev * dev,unsigned int dst,unsigned int src)15 static void copy_abs(struct input_dev *dev, unsigned int dst, unsigned int src)
16 {
17 	if (dev->absinfo && test_bit(src, dev->absbit)) {
18 		dev->absinfo[dst] = dev->absinfo[src];
19 		dev->absinfo[dst].fuzz = 0;
20 		__set_bit(dst, dev->absbit);
21 	}
22 }
23 
24 /**
25  * input_mt_init_slots() - initialize MT input slots
26  * @dev: input device supporting MT events and finger tracking
27  * @num_slots: number of slots used by the device
28  * @flags: mt tasks to handle in core
29  *
30  * This function allocates all necessary memory for MT slot handling
31  * in the input device, prepares the ABS_MT_SLOT and
32  * ABS_MT_TRACKING_ID events for use and sets up appropriate buffers.
33  * Depending on the flags set, it also performs pointer emulation and
34  * frame synchronization.
35  *
36  * May be called repeatedly. Returns -EINVAL if attempting to
37  * reinitialize with a different number of slots.
38  */
input_mt_init_slots(struct input_dev * dev,unsigned int num_slots,unsigned int flags)39 int input_mt_init_slots(struct input_dev *dev, unsigned int num_slots,
40 			unsigned int flags)
41 {
42 	struct input_mt *mt = dev->mt;
43 	int i;
44 
45 	if (!num_slots)
46 		return 0;
47 	if (mt)
48 		return mt->num_slots != num_slots ? -EINVAL : 0;
49 
50 	mt = kzalloc(struct_size(mt, slots, num_slots), GFP_KERNEL);
51 	if (!mt)
52 		goto err_mem;
53 
54 	mt->num_slots = num_slots;
55 	mt->flags = flags;
56 	input_set_abs_params(dev, ABS_MT_SLOT, 0, num_slots - 1, 0, 0);
57 	input_set_abs_params(dev, ABS_MT_TRACKING_ID, 0, TRKID_MAX, 0, 0);
58 
59 	if (flags & (INPUT_MT_POINTER | INPUT_MT_DIRECT)) {
60 		__set_bit(EV_KEY, dev->evbit);
61 		__set_bit(BTN_TOUCH, dev->keybit);
62 
63 		copy_abs(dev, ABS_X, ABS_MT_POSITION_X);
64 		copy_abs(dev, ABS_Y, ABS_MT_POSITION_Y);
65 		copy_abs(dev, ABS_PRESSURE, ABS_MT_PRESSURE);
66 	}
67 	if (flags & INPUT_MT_POINTER) {
68 		__set_bit(BTN_TOOL_FINGER, dev->keybit);
69 		__set_bit(BTN_TOOL_DOUBLETAP, dev->keybit);
70 		if (num_slots >= 3)
71 			__set_bit(BTN_TOOL_TRIPLETAP, dev->keybit);
72 		if (num_slots >= 4)
73 			__set_bit(BTN_TOOL_QUADTAP, dev->keybit);
74 		if (num_slots >= 5)
75 			__set_bit(BTN_TOOL_QUINTTAP, dev->keybit);
76 		__set_bit(INPUT_PROP_POINTER, dev->propbit);
77 	}
78 	if (flags & INPUT_MT_DIRECT)
79 		__set_bit(INPUT_PROP_DIRECT, dev->propbit);
80 	if (flags & INPUT_MT_SEMI_MT)
81 		__set_bit(INPUT_PROP_SEMI_MT, dev->propbit);
82 	if (flags & INPUT_MT_TRACK) {
83 		unsigned int n2 = num_slots * num_slots;
84 		mt->red = kcalloc(n2, sizeof(*mt->red), GFP_KERNEL);
85 		if (!mt->red)
86 			goto err_mem;
87 	}
88 
89 	/* Mark slots as 'inactive' */
90 	for (i = 0; i < num_slots; i++)
91 		input_mt_set_value(&mt->slots[i], ABS_MT_TRACKING_ID, -1);
92 
93 	/* Mark slots as 'unused' */
94 	mt->frame = 1;
95 
96 	dev->mt = mt;
97 	return 0;
98 err_mem:
99 	kfree(mt);
100 	return -ENOMEM;
101 }
102 EXPORT_SYMBOL(input_mt_init_slots);
103 
104 /**
105  * input_mt_destroy_slots() - frees the MT slots of the input device
106  * @dev: input device with allocated MT slots
107  *
108  * This function is only needed in error path as the input core will
109  * automatically free the MT slots when the device is destroyed.
110  */
input_mt_destroy_slots(struct input_dev * dev)111 void input_mt_destroy_slots(struct input_dev *dev)
112 {
113 	if (dev->mt) {
114 		kfree(dev->mt->red);
115 		kfree(dev->mt);
116 	}
117 	dev->mt = NULL;
118 }
119 EXPORT_SYMBOL(input_mt_destroy_slots);
120 
121 /**
122  * input_mt_report_slot_state() - report contact state
123  * @dev: input device with allocated MT slots
124  * @tool_type: the tool type to use in this slot
125  * @active: true if contact is active, false otherwise
126  *
127  * Reports a contact via ABS_MT_TRACKING_ID, and optionally
128  * ABS_MT_TOOL_TYPE. If active is true and the slot is currently
129  * inactive, or if the tool type is changed, a new tracking id is
130  * assigned to the slot. The tool type is only reported if the
131  * corresponding absbit field is set.
132  *
133  * Returns true if contact is active.
134  */
input_mt_report_slot_state(struct input_dev * dev,unsigned int tool_type,bool active)135 bool input_mt_report_slot_state(struct input_dev *dev,
136 				unsigned int tool_type, bool active)
137 {
138 	struct input_mt *mt = dev->mt;
139 	struct input_mt_slot *slot;
140 	int id;
141 
142 	if (!mt)
143 		return false;
144 
145 	slot = &mt->slots[mt->slot];
146 	slot->frame = mt->frame;
147 
148 	if (!active) {
149 		input_event(dev, EV_ABS, ABS_MT_TRACKING_ID, -1);
150 		return false;
151 	}
152 
153 	id = input_mt_get_value(slot, ABS_MT_TRACKING_ID);
154 	if (id < 0)
155 		id = input_mt_new_trkid(mt);
156 
157 	input_event(dev, EV_ABS, ABS_MT_TRACKING_ID, id);
158 	input_event(dev, EV_ABS, ABS_MT_TOOL_TYPE, tool_type);
159 
160 	return true;
161 }
162 EXPORT_SYMBOL(input_mt_report_slot_state);
163 
164 /**
165  * input_mt_report_finger_count() - report contact count
166  * @dev: input device with allocated MT slots
167  * @count: the number of contacts
168  *
169  * Reports the contact count via BTN_TOOL_FINGER, BTN_TOOL_DOUBLETAP,
170  * BTN_TOOL_TRIPLETAP and BTN_TOOL_QUADTAP.
171  *
172  * The input core ensures only the KEY events already setup for
173  * this device will produce output.
174  */
input_mt_report_finger_count(struct input_dev * dev,int count)175 void input_mt_report_finger_count(struct input_dev *dev, int count)
176 {
177 	input_event(dev, EV_KEY, BTN_TOOL_FINGER, count == 1);
178 	input_event(dev, EV_KEY, BTN_TOOL_DOUBLETAP, count == 2);
179 	input_event(dev, EV_KEY, BTN_TOOL_TRIPLETAP, count == 3);
180 	input_event(dev, EV_KEY, BTN_TOOL_QUADTAP, count == 4);
181 	input_event(dev, EV_KEY, BTN_TOOL_QUINTTAP, count == 5);
182 }
183 EXPORT_SYMBOL(input_mt_report_finger_count);
184 
185 /**
186  * input_mt_report_pointer_emulation() - common pointer emulation
187  * @dev: input device with allocated MT slots
188  * @use_count: report number of active contacts as finger count
189  *
190  * Performs legacy pointer emulation via BTN_TOUCH, ABS_X, ABS_Y and
191  * ABS_PRESSURE. Touchpad finger count is emulated if use_count is true.
192  *
193  * The input core ensures only the KEY and ABS axes already setup for
194  * this device will produce output.
195  */
input_mt_report_pointer_emulation(struct input_dev * dev,bool use_count)196 void input_mt_report_pointer_emulation(struct input_dev *dev, bool use_count)
197 {
198 	struct input_mt *mt = dev->mt;
199 	struct input_mt_slot *oldest;
200 	int oldid, count, i;
201 
202 	if (!mt)
203 		return;
204 
205 	oldest = NULL;
206 	oldid = mt->trkid;
207 	count = 0;
208 
209 	for (i = 0; i < mt->num_slots; ++i) {
210 		struct input_mt_slot *ps = &mt->slots[i];
211 		int id = input_mt_get_value(ps, ABS_MT_TRACKING_ID);
212 
213 		if (id < 0)
214 			continue;
215 		if ((id - oldid) & TRKID_SGN) {
216 			oldest = ps;
217 			oldid = id;
218 		}
219 		count++;
220 	}
221 
222 	input_event(dev, EV_KEY, BTN_TOUCH, count > 0);
223 
224 	if (use_count) {
225 		if (count == 0 &&
226 		    !test_bit(ABS_MT_DISTANCE, dev->absbit) &&
227 		    test_bit(ABS_DISTANCE, dev->absbit) &&
228 		    input_abs_get_val(dev, ABS_DISTANCE) != 0) {
229 			/*
230 			 * Force reporting BTN_TOOL_FINGER for devices that
231 			 * only report general hover (and not per-contact
232 			 * distance) when contact is in proximity but not
233 			 * on the surface.
234 			 */
235 			count = 1;
236 		}
237 
238 		input_mt_report_finger_count(dev, count);
239 	}
240 
241 	if (oldest) {
242 		int x = input_mt_get_value(oldest, ABS_MT_POSITION_X);
243 		int y = input_mt_get_value(oldest, ABS_MT_POSITION_Y);
244 
245 		input_event(dev, EV_ABS, ABS_X, x);
246 		input_event(dev, EV_ABS, ABS_Y, y);
247 
248 		if (test_bit(ABS_MT_PRESSURE, dev->absbit)) {
249 			int p = input_mt_get_value(oldest, ABS_MT_PRESSURE);
250 			input_event(dev, EV_ABS, ABS_PRESSURE, p);
251 		}
252 	} else {
253 		if (test_bit(ABS_MT_PRESSURE, dev->absbit))
254 			input_event(dev, EV_ABS, ABS_PRESSURE, 0);
255 	}
256 }
257 EXPORT_SYMBOL(input_mt_report_pointer_emulation);
258 
__input_mt_drop_unused(struct input_dev * dev,struct input_mt * mt)259 static void __input_mt_drop_unused(struct input_dev *dev, struct input_mt *mt)
260 {
261 	int i;
262 
263 	lockdep_assert_held(&dev->event_lock);
264 
265 	for (i = 0; i < mt->num_slots; i++) {
266 		if (input_mt_is_active(&mt->slots[i]) &&
267 		    !input_mt_is_used(mt, &mt->slots[i])) {
268 			input_handle_event(dev, EV_ABS, ABS_MT_SLOT, i);
269 			input_handle_event(dev, EV_ABS, ABS_MT_TRACKING_ID, -1);
270 		}
271 	}
272 }
273 
274 /**
275  * input_mt_drop_unused() - Inactivate slots not seen in this frame
276  * @dev: input device with allocated MT slots
277  *
278  * Lift all slots not seen since the last call to this function.
279  */
input_mt_drop_unused(struct input_dev * dev)280 void input_mt_drop_unused(struct input_dev *dev)
281 {
282 	struct input_mt *mt = dev->mt;
283 
284 	if (mt) {
285 		unsigned long flags;
286 
287 		spin_lock_irqsave(&dev->event_lock, flags);
288 
289 		__input_mt_drop_unused(dev, mt);
290 		mt->frame++;
291 
292 		spin_unlock_irqrestore(&dev->event_lock, flags);
293 	}
294 }
295 EXPORT_SYMBOL(input_mt_drop_unused);
296 
297 /**
298  * input_mt_release_slots() - Deactivate all slots
299  * @dev: input device with allocated MT slots
300  *
301  * Lift all active slots.
302  */
input_mt_release_slots(struct input_dev * dev)303 void input_mt_release_slots(struct input_dev *dev)
304 {
305 	struct input_mt *mt = dev->mt;
306 
307 	lockdep_assert_held(&dev->event_lock);
308 
309 	if (mt) {
310 		/* This will effectively mark all slots unused. */
311 		mt->frame++;
312 
313 		__input_mt_drop_unused(dev, mt);
314 
315 		if (test_bit(ABS_PRESSURE, dev->absbit))
316 			input_handle_event(dev, EV_ABS, ABS_PRESSURE, 0);
317 
318 		mt->frame++;
319 	}
320 }
321 
322 /**
323  * input_mt_sync_frame() - synchronize mt frame
324  * @dev: input device with allocated MT slots
325  *
326  * Close the frame and prepare the internal state for a new one.
327  * Depending on the flags, marks unused slots as inactive and performs
328  * pointer emulation.
329  */
input_mt_sync_frame(struct input_dev * dev)330 void input_mt_sync_frame(struct input_dev *dev)
331 {
332 	struct input_mt *mt = dev->mt;
333 	bool use_count = false;
334 
335 	if (!mt)
336 		return;
337 
338 	if (mt->flags & INPUT_MT_DROP_UNUSED) {
339 		unsigned long flags;
340 
341 		spin_lock_irqsave(&dev->event_lock, flags);
342 		__input_mt_drop_unused(dev, mt);
343 		spin_unlock_irqrestore(&dev->event_lock, flags);
344 	}
345 
346 	if ((mt->flags & INPUT_MT_POINTER) && !(mt->flags & INPUT_MT_SEMI_MT))
347 		use_count = true;
348 
349 	input_mt_report_pointer_emulation(dev, use_count);
350 
351 	mt->frame++;
352 }
353 EXPORT_SYMBOL(input_mt_sync_frame);
354 
adjust_dual(int * begin,int step,int * end,int eq,int mu)355 static int adjust_dual(int *begin, int step, int *end, int eq, int mu)
356 {
357 	int f, *p, s, c;
358 
359 	if (begin == end)
360 		return 0;
361 
362 	f = *begin;
363 	p = begin + step;
364 	s = p == end ? f + 1 : *p;
365 
366 	for (; p != end; p += step) {
367 		if (*p < f) {
368 			s = f;
369 			f = *p;
370 		} else if (*p < s) {
371 			s = *p;
372 		}
373 	}
374 
375 	c = (f + s + 1) / 2;
376 	if (c == 0 || (c > mu && (!eq || mu > 0)))
377 		return 0;
378 	/* Improve convergence for positive matrices by penalizing overcovers */
379 	if (s < 0 && mu <= 0)
380 		c *= 2;
381 
382 	for (p = begin; p != end; p += step)
383 		*p -= c;
384 
385 	return (c < s && s <= 0) || (f >= 0 && f < c);
386 }
387 
find_reduced_matrix(int * w,int nr,int nc,int nrc,int mu)388 static void find_reduced_matrix(int *w, int nr, int nc, int nrc, int mu)
389 {
390 	int i, k, sum;
391 
392 	for (k = 0; k < nrc; k++) {
393 		for (i = 0; i < nr; i++)
394 			adjust_dual(w + i, nr, w + i + nrc, nr <= nc, mu);
395 		sum = 0;
396 		for (i = 0; i < nrc; i += nr)
397 			sum += adjust_dual(w + i, 1, w + i + nr, nc <= nr, mu);
398 		if (!sum)
399 			break;
400 	}
401 }
402 
input_mt_set_matrix(struct input_mt * mt,const struct input_mt_pos * pos,int num_pos,int mu)403 static int input_mt_set_matrix(struct input_mt *mt,
404 			       const struct input_mt_pos *pos, int num_pos,
405 			       int mu)
406 {
407 	const struct input_mt_pos *p;
408 	struct input_mt_slot *s;
409 	int *w = mt->red;
410 	int x, y;
411 
412 	for (s = mt->slots; s != mt->slots + mt->num_slots; s++) {
413 		if (!input_mt_is_active(s))
414 			continue;
415 		x = input_mt_get_value(s, ABS_MT_POSITION_X);
416 		y = input_mt_get_value(s, ABS_MT_POSITION_Y);
417 		for (p = pos; p != pos + num_pos; p++) {
418 			int dx = x - p->x, dy = y - p->y;
419 			*w++ = dx * dx + dy * dy - mu;
420 		}
421 	}
422 
423 	return w - mt->red;
424 }
425 
input_mt_set_slots(struct input_mt * mt,int * slots,int num_pos)426 static void input_mt_set_slots(struct input_mt *mt,
427 			       int *slots, int num_pos)
428 {
429 	struct input_mt_slot *s;
430 	int *w = mt->red, j;
431 
432 	for (j = 0; j != num_pos; j++)
433 		slots[j] = -1;
434 
435 	for (s = mt->slots; s != mt->slots + mt->num_slots; s++) {
436 		if (!input_mt_is_active(s))
437 			continue;
438 
439 		for (j = 0; j != num_pos; j++) {
440 			if (w[j] < 0) {
441 				slots[j] = s - mt->slots;
442 				break;
443 			}
444 		}
445 
446 		w += num_pos;
447 	}
448 
449 	for (s = mt->slots; s != mt->slots + mt->num_slots; s++) {
450 		if (input_mt_is_active(s))
451 			continue;
452 
453 		for (j = 0; j != num_pos; j++) {
454 			if (slots[j] < 0) {
455 				slots[j] = s - mt->slots;
456 				break;
457 			}
458 		}
459 	}
460 }
461 
462 /**
463  * input_mt_assign_slots() - perform a best-match assignment
464  * @dev: input device with allocated MT slots
465  * @slots: the slot assignment to be filled
466  * @pos: the position array to match
467  * @num_pos: number of positions
468  * @dmax: maximum ABS_MT_POSITION displacement (zero for infinite)
469  *
470  * Performs a best match against the current contacts and returns
471  * the slot assignment list. New contacts are assigned to unused
472  * slots.
473  *
474  * The assignments are balanced so that all coordinate displacements are
475  * below the euclidian distance dmax. If no such assignment can be found,
476  * some contacts are assigned to unused slots.
477  *
478  * Returns zero on success, or negative error in case of failure.
479  */
input_mt_assign_slots(struct input_dev * dev,int * slots,const struct input_mt_pos * pos,int num_pos,int dmax)480 int input_mt_assign_slots(struct input_dev *dev, int *slots,
481 			  const struct input_mt_pos *pos, int num_pos,
482 			  int dmax)
483 {
484 	struct input_mt *mt = dev->mt;
485 	int mu = 2 * dmax * dmax;
486 	int nrc;
487 
488 	if (!mt || !mt->red)
489 		return -ENXIO;
490 	if (num_pos > mt->num_slots)
491 		return -EINVAL;
492 	if (num_pos < 1)
493 		return 0;
494 
495 	nrc = input_mt_set_matrix(mt, pos, num_pos, mu);
496 	find_reduced_matrix(mt->red, num_pos, nrc / num_pos, nrc, mu);
497 	input_mt_set_slots(mt, slots, num_pos);
498 
499 	return 0;
500 }
501 EXPORT_SYMBOL(input_mt_assign_slots);
502 
503 /**
504  * input_mt_get_slot_by_key() - return slot matching key
505  * @dev: input device with allocated MT slots
506  * @key: the key of the sought slot
507  *
508  * Returns the slot of the given key, if it exists, otherwise
509  * set the key on the first unused slot and return.
510  *
511  * If no available slot can be found, -1 is returned.
512  * Note that for this function to work properly, input_mt_sync_frame() has
513  * to be called at each frame.
514  */
input_mt_get_slot_by_key(struct input_dev * dev,int key)515 int input_mt_get_slot_by_key(struct input_dev *dev, int key)
516 {
517 	struct input_mt *mt = dev->mt;
518 	struct input_mt_slot *s;
519 
520 	if (!mt)
521 		return -1;
522 
523 	for (s = mt->slots; s != mt->slots + mt->num_slots; s++)
524 		if (input_mt_is_active(s) && s->key == key)
525 			return s - mt->slots;
526 
527 	for (s = mt->slots; s != mt->slots + mt->num_slots; s++)
528 		if (!input_mt_is_active(s) && !input_mt_is_used(mt, s)) {
529 			s->key = key;
530 			return s - mt->slots;
531 		}
532 
533 	return -1;
534 }
535 EXPORT_SYMBOL(input_mt_get_slot_by_key);
536