1 /*-
26 /*-
63 	for ((i) = ffs(v) - 1; (i) != -1; (i) = ffs((v) & (~1 << (i))) - 1)
102 	return (ffs(~slots & ((2U << MAXIMAL_MT_SLOT(evdev)) - 1)) - 1);  in ffc_slot()
109 	size_t size = offsetof(struct evdev_mt, slots);  in evdev_mt_init()  local
110 	int slot, slots;  in evdev_mt_init()  local
113 	type_a = !bit_test(evdev->ev_abs_flags, ABS_MT_SLOT);  in evdev_mt_init()
117 		    ABS_MT_SLOT, 0, MAX_MT_SLOTS - 1, 0, 0, 0);  in evdev_mt_init()
119 		    ABS_MT_TRACKING_ID, -1, MAX_MT_SLOTS - 1, 0, 0, 0);  in evdev_mt_init()
123 	size += sizeof(mt->slots[0]) * slots;  in evdev_mt_init()
124 	if (bit_test(evdev->ev_flags, EVDEV_FLAG_MT_TRACK)) {  in evdev_mt_init()
125 		size += sizeof(mt->match_slots[0]) * slots;  in evdev_mt_init()
126 		size += sizeof(mt->matrix[0]) * (slots + 6) * slots;  in evdev_mt_init()
129 	mt = malloc(size, M_EVDEV, M_WAITOK | M_ZERO);  in evdev_mt_init()
130 	evdev->ev_mt = mt;  in evdev_mt_init()
131 	mt->type_a = type_a;  in evdev_mt_init()
133 	if (bit_test(evdev->ev_flags, EVDEV_FLAG_MT_TRACK)) {  in evdev_mt_init()
134 		mt->match_slots = mt->slots + slots;  in evdev_mt_init()
135 		mt->matrix = (int *)(mt->match_slots + slots);  in evdev_mt_init()
139 	for (slot = 0; slot < slots; slot++)  in evdev_mt_init()
140 		mt->slots[slot].id = -1;  in evdev_mt_init()
142 	if (!bit_test(evdev->ev_flags, EVDEV_FLAG_MT_KEEPID))  in evdev_mt_init()
144 		    ABS_MT_TRACKING_ID, -1, UINT16_MAX, 0, 0, 0);  in evdev_mt_init()
145 	if (bit_test(evdev->ev_flags, EVDEV_FLAG_MT_STCOMPAT))  in evdev_mt_init()
152 	free(evdev->ev_mt, M_EVDEV);  in evdev_mt_free()
158 	if (bit_test(evdev->ev_flags, EVDEV_FLAG_MT_TRACK))  in evdev_mt_sync_frame()
160 	if (bit_test(evdev->ev_flags, EVDEV_FLAG_MT_AUTOREL))  in evdev_mt_sync_frame()
162 	if (evdev->ev_report_opened &&  in evdev_mt_sync_frame()
163 	    bit_test(evdev->ev_flags, EVDEV_FLAG_MT_STCOMPAT))  in evdev_mt_sync_frame()
165 	evdev->ev_mt->frame = 0;  in evdev_mt_sync_frame()
169 evdev_mt_send_slot(struct evdev_dev *evdev, int slot,  in evdev_mt_send_slot()  argument
173 	bool type_a = !bit_test(evdev->ev_abs_flags, ABS_MT_SLOT);  in evdev_mt_send_slot()
176 	MPASS(type_a || (slot >= 0 && slot <= MAXIMAL_MT_SLOT(evdev)));  in evdev_mt_send_slot()
180 		evdev_send_event(evdev, EV_ABS, ABS_MT_SLOT, slot);  in evdev_mt_send_slot()
182 			evdev_send_event(evdev, EV_ABS, ABS_MT_TRACKING_ID, -1);  in evdev_mt_send_slot()
186 	bit_foreach_at(evdev->ev_abs_flags, ABS_MT_FIRST, ABS_MT_LAST + 1, i)  in evdev_mt_send_slot()
188 		    state->val[ABS_MT_INDEX(i)]);  in evdev_mt_send_slot()
194 evdev_mt_push_slot(struct evdev_dev *evdev, int slot,  in evdev_mt_push_slot()  argument
197 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_push_slot()
198 	bool type_a = !bit_test(evdev->ev_abs_flags, ABS_MT_SLOT);  in evdev_mt_push_slot()
200 	if ((type_a || (mt != NULL && mt->type_a)) && state == NULL)  in evdev_mt_push_slot()
202 	if (!type_a && (slot < 0 || slot > MAXIMAL_MT_SLOT(evdev)))  in evdev_mt_push_slot()
206 	if (bit_test(evdev->ev_flags, EVDEV_FLAG_MT_TRACK) && mt->type_a) {  in evdev_mt_push_slot()
207 		mt->match_slots[mt->match_slot] = *state;  in evdev_mt_push_slot()
209 	} else if (bit_test(evdev->ev_flags, EVDEV_FLAG_MT_TRACK)) {  in evdev_mt_push_slot()
210 		evdev_mt_record_event(evdev, EV_ABS, ABS_MT_SLOT, slot);  in evdev_mt_push_slot()
212 			mt->match_slots[mt->match_slot] = *state;  in evdev_mt_push_slot()
215 			    ABS_MT_TRACKING_ID, -1);  in evdev_mt_push_slot()
217 		evdev_mt_send_slot(evdev, slot, state);  in evdev_mt_push_slot()
224  * Find a minimum-weight matching for an m-by-n matrix.
226  * m must be greater than or equal to n. The size of the buffer must be
229  * On return, the first m elements of the buffer contain the row-to-
230  * column mappings, i.e., buffer[i] is the column index for row i, or -1
236  * The function applies the Dinic-Kronrod algorithm. It is not modern or
240  * "virtual" column with the index -1 and zero values. This permits inputs
248 	int *r2c = buffer;	/* row-to-column assignments */  in evdev_mt_matching()
250 	int *mc = red + m;	/* row-wise minimal elements of cs */  in evdev_mt_matching()
252 	int *c2r = cs + n;	/* column-to-row assignments in cs */  in evdev_mt_matching()
255 	for (p = r2c; p < red; *p++ = -1) {}  in evdev_mt_matching()
260 			d = *p - red[i];  in evdev_mt_matching()
275 			mc[row] -= n;  in evdev_mt_matching()
279 					d = p[mc[i]] - cd[mc[i]];  in evdev_mt_matching()
280 					e = p[j] - cd[j];  in evdev_mt_matching()
285 					d -= red[i];  in evdev_mt_matching()
295 				red[c2r[cs[i]]] -= delta;  in evdev_mt_matching()
311  * Set tracking id to -1 for unassigned (new) points.
315     int size)  in evdev_mt_match_frame()  argument
317 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_match_frame()
318 	int i, j, m, n, dx, dy, slot, num_touches;  in evdev_mt_match_frame()  local
322 	MPASS(mt->matrix != NULL);  in evdev_mt_match_frame()
323 	MPASS(size >= 0 && size <= MAXIMAL_MT_SLOT(evdev) + 1);  in evdev_mt_match_frame()
325 	if (size == 0)  in evdev_mt_match_frame()
328 	p = mt->matrix;  in evdev_mt_match_frame()
329 	num_touches = bitcount(mt->touches);  in evdev_mt_match_frame()
330 	if (num_touches >= size) {  in evdev_mt_match_frame()
331 		FOREACHBIT(mt->touches, slot)  in evdev_mt_match_frame()
332 			for (i = 0; i < size; i++) {  in evdev_mt_match_frame()
333 				dx = pt[i].x - mt->slots[slot].x;  in evdev_mt_match_frame()
334 				dy = pt[i].y - mt->slots[slot].y;  in evdev_mt_match_frame()
338 		n = size;  in evdev_mt_match_frame()
340 		for (i = 0; i < size; i++)  in evdev_mt_match_frame()
341 			FOREACHBIT(mt->touches, slot) {  in evdev_mt_match_frame()
342 				dx = pt[i].x - mt->slots[slot].x;  in evdev_mt_match_frame()
343 				dy = pt[i].y - mt->slots[slot].y;  in evdev_mt_match_frame()
346 		m = size;  in evdev_mt_match_frame()
349 	evdev_mt_matching(mt->matrix, m, n, p);  in evdev_mt_match_frame()
357 	p = (n == size ? c2r : r2c);  in evdev_mt_match_frame()
358 	for (i = 0; i < size; i++)  in evdev_mt_match_frame()
360 			pt[i].id = -1;  in evdev_mt_match_frame()
362 	p = (n == size ? r2c : c2r);  in evdev_mt_match_frame()
363 	FOREACHBIT(mt->touches, slot)  in evdev_mt_match_frame()
365 			pt[i].id = mt->tracking_ids[slot];  in evdev_mt_match_frame()
369 evdev_mt_send_frame(struct evdev_dev *evdev, union evdev_mt_slot *pt, int size)  in evdev_mt_send_frame()  argument
371 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_send_frame()
372 	union evdev_mt_slot *slot;  in evdev_mt_send_frame()  local
375 	MPASS(size >= 0 && size <= MAXIMAL_MT_SLOT(evdev) + 1);  in evdev_mt_send_frame()
378 	 * While MT-matching assign tracking IDs of new contacts to be equal  in evdev_mt_send_frame()
379 	 * to a slot number to make things simpler.  in evdev_mt_send_frame()
381 	for (slot = pt; slot < pt + size; slot++) {  in evdev_mt_send_frame()
382 		if (slot->id < 0)  in evdev_mt_send_frame()
383 			slot->id = ffc_slot(evdev, mt->touches | mt->frame);  in evdev_mt_send_frame()
384 		if (slot->id >= 0)  in evdev_mt_send_frame()
385 			evdev_mt_send_slot(evdev, slot->id, slot);  in evdev_mt_send_frame()
390 evdev_mt_push_frame(struct evdev_dev *evdev, union evdev_mt_slot *pt, int size)  in evdev_mt_push_frame()  argument
392 	if (size < 0 || size > MAXIMAL_MT_SLOT(evdev) + 1)  in evdev_mt_push_frame()
396 	evdev_mt_send_frame(evdev, pt, size);  in evdev_mt_push_frame()
406 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_record_event()
414 			KASSERT(mt->type_a, ("Not a MT type A protocol"));  in evdev_mt_record_event()
415 			mt->match_frame |= 1U << mt->match_slot;  in evdev_mt_record_event()
416 			mt->match_slot++;  in evdev_mt_record_event()
423 			KASSERT(!mt->type_a, ("Not a MT type B protocol"));  in evdev_mt_record_event()
424 			KASSERT(value >= 0, ("Negative slot number"));  in evdev_mt_record_event()
425 			mt->match_slot = value;  in evdev_mt_record_event()
426 			mt->match_frame |= 1U << mt->match_slot;  in evdev_mt_record_event()
429 			KASSERT(!mt->type_a, ("Not a MT type B protocol"));  in evdev_mt_record_event()
430 			if (value == -1)  in evdev_mt_record_event()
431 				mt->match_frame &= ~(1U << mt->match_slot);  in evdev_mt_record_event()
434 			KASSERT(mt->match_slot >= 0, ("Negative slot"));  in evdev_mt_record_event()
435 			KASSERT(mt->match_slot <= MAXIMAL_MT_SLOT(evdev),  in evdev_mt_record_event()
436 			    ("Slot number too big"));  in evdev_mt_record_event()
437 			mt->match_slots[mt->match_slot].  in evdev_mt_record_event()
452 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_replay_events()
453 	int slot, size = 0;  in evdev_mt_replay_events()  local
457 	FOREACHBIT(mt->match_frame, slot) {  in evdev_mt_replay_events()
458 		if (slot != size)  in evdev_mt_replay_events()
459 			mt->match_slots[size] = mt->match_slots[slot];  in evdev_mt_replay_events()
460 		size++;  in evdev_mt_replay_events()
462 	evdev_mt_match_frame(evdev, mt->match_slots, size);  in evdev_mt_replay_events()
463 	evdev_mt_send_frame(evdev, mt->match_slots, size);  in evdev_mt_replay_events()
464 	mt->match_slot = 0;  in evdev_mt_replay_events()
465 	mt->match_frame = 0;  in evdev_mt_replay_events()
471 	return (evdev->ev_mt->match_slots);  in evdev_mt_get_match_slots()
477 	return (evdev->ev_mt->last_reported_slot);  in evdev_mt_get_last_slot()
481 evdev_mt_set_last_slot(struct evdev_dev *evdev, int slot)  in evdev_mt_set_last_slot()  argument
483 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_set_last_slot()
485 	MPASS(slot >= 0 && slot <= MAXIMAL_MT_SLOT(evdev));  in evdev_mt_set_last_slot()
487 	mt->frame |= 1U << slot;  in evdev_mt_set_last_slot()
488 	mt->last_reported_slot = slot;  in evdev_mt_set_last_slot()
492 evdev_mt_get_value(struct evdev_dev *evdev, int slot, int16_t code)  in evdev_mt_get_value()  argument
494 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_get_value()
496 	MPASS(slot >= 0 && slot <= MAXIMAL_MT_SLOT(evdev));  in evdev_mt_get_value()
498 	return (mt->slots[slot].val[ABS_MT_INDEX(code)]);  in evdev_mt_get_value()
502 evdev_mt_set_value(struct evdev_dev *evdev, int slot, int16_t code,  in evdev_mt_set_value()  argument
505 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_set_value()
507 	MPASS(slot >= 0 && slot <= MAXIMAL_MT_SLOT(evdev));  in evdev_mt_set_value()
510 		if (value != -1)  in evdev_mt_set_value()
511 			mt->touches |= 1U << slot;  in evdev_mt_set_value()
513 			mt->touches &= ~(1U << slot);  in evdev_mt_set_value()
515 	mt->slots[slot].val[ABS_MT_INDEX(code)] = value;  in evdev_mt_set_value()
521 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_id_to_slot()
522 	int slot;  in evdev_mt_id_to_slot()  local
524 	KASSERT(!mt->type_a, ("Not a MT type B protocol"));  in evdev_mt_id_to_slot()
527 	 * Ignore tracking_id if slot assignment is performed by evdev.  in evdev_mt_id_to_slot()
530 	if (bit_test(evdev->ev_flags, EVDEV_FLAG_MT_TRACK))  in evdev_mt_id_to_slot()
531 		return (ffc_slot(evdev, mt->match_frame));  in evdev_mt_id_to_slot()
533 	FOREACHBIT(mt->touches, slot)  in evdev_mt_id_to_slot()
534 		if (mt->tracking_ids[slot] == tracking_id)  in evdev_mt_id_to_slot()
535 			return (slot);  in evdev_mt_id_to_slot()
537 	 * Do not allow allocation of new slot in a place of just  in evdev_mt_id_to_slot()
540 	return (ffc_slot(evdev, mt->touches | mt->frame));  in evdev_mt_id_to_slot()
544 evdev_mt_reassign_id(struct evdev_dev *evdev, int slot, int32_t id)  in evdev_mt_reassign_id()  argument
546 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_reassign_id()
549 	if (id == -1 || bit_test(evdev->ev_flags, EVDEV_FLAG_MT_KEEPID)) {  in evdev_mt_reassign_id()
550 		mt->tracking_ids[slot] = id;  in evdev_mt_reassign_id()
554 	nid = evdev_mt_get_value(evdev, slot, ABS_MT_TRACKING_ID);  in evdev_mt_reassign_id()
555 	if (nid != -1) {  in evdev_mt_reassign_id()
556 		KASSERT(id == mt->tracking_ids[slot],  in evdev_mt_reassign_id()
557 		    ("MT-slot tracking id has changed"));  in evdev_mt_reassign_id()
561 	mt->tracking_ids[slot] = id;  in evdev_mt_reassign_id()
563 	nid = mt->tracking_id++;  in evdev_mt_reassign_id()
564 	FOREACHBIT(mt->touches, slot)  in evdev_mt_reassign_id()
565 		if (evdev_mt_get_value(evdev, slot, ABS_MT_TRACKING_ID) == nid)  in evdev_mt_reassign_id()
575 		value = (value - mtmin) * stmax / (mtmax - mtmin);  in evdev_mt_normalize()
587 	if (evdev->ev_absinfo == NULL)  in evdev_mt_support_st_compat()
594 	if (!bit_test(evdev->ev_prop_flags, INPUT_PROP_DIRECT))  in evdev_mt_support_st_compat()
597 	/* Echo 0-th MT-slot as ST-slot */  in evdev_mt_support_st_compat()
599 		if (!bit_test(evdev->ev_abs_flags, evdev_mtstmap[i].mt) ||  in evdev_mt_support_st_compat()
600 		     bit_test(evdev->ev_abs_flags, evdev_mtstmap[i].st))  in evdev_mt_support_st_compat()
602 		ai = evdev->ev_absinfo + evdev_mtstmap[i].mt;  in evdev_mt_support_st_compat()
603 		evdev->ev_mt->mtst_events |= 1U << i;  in evdev_mt_support_st_compat()
610 			      ai->flat, 0, ai->maximum, evdev_mtstmap[i].max),  in evdev_mt_support_st_compat()
614 			    ai->minimum,  in evdev_mt_support_st_compat()
615 			    ai->maximum,  in evdev_mt_support_st_compat()
617 			    ai->flat,  in evdev_mt_support_st_compat()
618 			    ai->resolution);  in evdev_mt_support_st_compat()
625 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_send_st_compat()
630 	nfingers = bitcount(mt->touches);  in evdev_mt_send_st_compat()
633 	/* Send first active MT-slot state as single touch report */  in evdev_mt_send_st_compat()
634 	st_slot = ffs(mt->touches) - 1;  in evdev_mt_send_st_compat()
635 	if (st_slot != -1)  in evdev_mt_send_st_compat()
636 		FOREACHBIT(mt->mtst_events, i)  in evdev_mt_send_st_compat()
640 			      evdev->ev_absinfo[evdev_mtstmap[i].mt].minimum,  in evdev_mt_send_st_compat()
641 			      evdev->ev_absinfo[evdev_mtstmap[i].mt].maximum,  in evdev_mt_send_st_compat()
645 	if (!bit_test(evdev->ev_prop_flags, INPUT_PROP_DIRECT))  in evdev_mt_send_st_compat()
655 	struct evdev_mt *mt = evdev->ev_mt;  in evdev_mt_send_autorel()
656 	int slot;  in evdev_mt_send_autorel()  local
659 	KASSERT(mt->match_frame == 0, ("Unmatched events exist"));  in evdev_mt_send_autorel()
661 	FOREACHBIT(mt->touches & ~mt->frame, slot)  in evdev_mt_send_autorel()
662 		evdev_mt_send_slot(evdev, slot, NULL);  in evdev_mt_send_autorel()