[linux.git] / drivers / input / input-mt.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Input Multitouch Library
 *
 * Copyright (c) 2008-2010 Henrik Rydberg
 */

#include <linux/input/mt.h>
#include <linux/export.h>
#include <linux/slab.h>

#define TRKID_SGN	((TRKID_MAX + 1) >> 1)

static void copy_abs(struct input_dev *dev, unsigned int dst, unsigned int src)
{
	if (dev->absinfo && test_bit(src, dev->absbit)) {
		dev->absinfo[dst] = dev->absinfo[src];
		dev->absinfo[dst].fuzz = 0;
		__set_bit(dst, dev->absbit);
	}
}

/**
 * input_mt_init_slots() - initialize MT input slots
 * @dev: input device supporting MT events and finger tracking
 * @num_slots: number of slots used by the device
 * @flags: mt tasks to handle in core
 *
 * This function allocates all necessary memory for MT slot handling
 * in the input device, prepares the ABS_MT_SLOT and
 * ABS_MT_TRACKING_ID events for use and sets up appropriate buffers.
 * Depending on the flags set, it also performs pointer emulation and
 * frame synchronization.
 *
 * May be called repeatedly. Returns -EINVAL if attempting to
 * reinitialize with a different number of slots.
 */
int input_mt_init_slots(struct input_dev *dev, unsigned int num_slots,
			unsigned int flags)
{
	struct input_mt *mt = dev->mt;
	int i;

	if (!num_slots)
		return 0;
	if (mt)
		return mt->num_slots != num_slots ? -EINVAL : 0;

	mt = kzalloc(struct_size(mt, slots, num_slots), GFP_KERNEL);
	if (!mt)
		goto err_mem;

	mt->num_slots = num_slots;
	mt->flags = flags;
	input_set_abs_params(dev, ABS_MT_SLOT, 0, num_slots - 1, 0, 0);
	input_set_abs_params(dev, ABS_MT_TRACKING_ID, 0, TRKID_MAX, 0, 0);

	if (flags & (INPUT_MT_POINTER | INPUT_MT_DIRECT)) {
		__set_bit(EV_KEY, dev->evbit);
		__set_bit(BTN_TOUCH, dev->keybit);

		copy_abs(dev, ABS_X, ABS_MT_POSITION_X);
		copy_abs(dev, ABS_Y, ABS_MT_POSITION_Y);
		copy_abs(dev, ABS_PRESSURE, ABS_MT_PRESSURE);
	}
	if (flags & INPUT_MT_POINTER) {
		__set_bit(BTN_TOOL_FINGER, dev->keybit);
		__set_bit(BTN_TOOL_DOUBLETAP, dev->keybit);
		if (num_slots >= 3)
			__set_bit(BTN_TOOL_TRIPLETAP, dev->keybit);
		if (num_slots >= 4)
			__set_bit(BTN_TOOL_QUADTAP, dev->keybit);
		if (num_slots >= 5)
			__set_bit(BTN_TOOL_QUINTTAP, dev->keybit);
		__set_bit(INPUT_PROP_POINTER, dev->propbit);
	}
	if (flags & INPUT_MT_DIRECT)
		__set_bit(INPUT_PROP_DIRECT, dev->propbit);
	if (flags & INPUT_MT_SEMI_MT)
		__set_bit(INPUT_PROP_SEMI_MT, dev->propbit);
	if (flags & INPUT_MT_TRACK) {
		unsigned int n2 = num_slots * num_slots;
		mt->red = kcalloc(n2, sizeof(*mt->red), GFP_KERNEL);
		if (!mt->red)
			goto err_mem;
	}

	/* Mark slots as 'inactive' */
	for (i = 0; i < num_slots; i++)
		input_mt_set_value(&mt->slots[i], ABS_MT_TRACKING_ID, -1);

	/* Mark slots as 'unused' */
	mt->frame = 1;

	dev->mt = mt;
	return 0;
err_mem:
	kfree(mt);
	return -ENOMEM;
}
EXPORT_SYMBOL(input_mt_init_slots);

/**
 * input_mt_destroy_slots() - frees the MT slots of the input device
 * @dev: input device with allocated MT slots
 *
 * This function is only needed in error path as the input core will
 * automatically free the MT slots when the device is destroyed.
 */
void input_mt_destroy_slots(struct input_dev *dev)
{
	if (dev->mt) {
		kfree(dev->mt->red);
		kfree(dev->mt);
	}
	dev->mt = NULL;
}
EXPORT_SYMBOL(input_mt_destroy_slots);

/**
 * input_mt_report_slot_state() - report contact state
 * @dev: input device with allocated MT slots
 * @tool_type: the tool type to use in this slot
 * @active: true if contact is active, false otherwise
 *
 * Reports a contact via ABS_MT_TRACKING_ID, and optionally
 * ABS_MT_TOOL_TYPE. If active is true and the slot is currently
 * inactive, or if the tool type is changed, a new tracking id is
 * assigned to the slot. The tool type is only reported if the
 * corresponding absbit field is set.
 *
 * Returns true if contact is active.
 */
bool input_mt_report_slot_state(struct input_dev *dev,
				unsigned int tool_type, bool active)
{
	struct input_mt *mt = dev->mt;
	struct input_mt_slot *slot;
	int id;

	if (!mt)
		return false;

	slot = &mt->slots[mt->slot];
	slot->frame = mt->frame;

	if (!active) {
		input_event(dev, EV_ABS, ABS_MT_TRACKING_ID, -1);
		return false;
	}

	id = input_mt_get_value(slot, ABS_MT_TRACKING_ID);
	if (id < 0)
		id = input_mt_new_trkid(mt);

	input_event(dev, EV_ABS, ABS_MT_TRACKING_ID, id);
	input_event(dev, EV_ABS, ABS_MT_TOOL_TYPE, tool_type);

	return true;
}
EXPORT_SYMBOL(input_mt_report_slot_state);

/**
 * input_mt_report_finger_count() - report contact count
 * @dev: input device with allocated MT slots
 * @count: the number of contacts
 *
 * Reports the contact count via BTN_TOOL_FINGER, BTN_TOOL_DOUBLETAP,
 * BTN_TOOL_TRIPLETAP and BTN_TOOL_QUADTAP.
 *
 * The input core ensures only the KEY events already setup for
 * this device will produce output.
 */
void input_mt_report_finger_count(struct input_dev *dev, int count)
{
	input_event(dev, EV_KEY, BTN_TOOL_FINGER, count == 1);
	input_event(dev, EV_KEY, BTN_TOOL_DOUBLETAP, count == 2);
	input_event(dev, EV_KEY, BTN_TOOL_TRIPLETAP, count == 3);
	input_event(dev, EV_KEY, BTN_TOOL_QUADTAP, count == 4);
	input_event(dev, EV_KEY, BTN_TOOL_QUINTTAP, count == 5);
}
EXPORT_SYMBOL(input_mt_report_finger_count);

/**
 * input_mt_report_pointer_emulation() - common pointer emulation
 * @dev: input device with allocated MT slots
 * @use_count: report number of active contacts as finger count
 *
 * Performs legacy pointer emulation via BTN_TOUCH, ABS_X, ABS_Y and
 * ABS_PRESSURE. Touchpad finger count is emulated if use_count is true.
 *
 * The input core ensures only the KEY and ABS axes already setup for
 * this device will produce output.
 */
void input_mt_report_pointer_emulation(struct input_dev *dev, bool use_count)
{
	struct input_mt *mt = dev->mt;
	struct input_mt_slot *oldest;
	int oldid, count, i;

	if (!mt)
		return;

	oldest = NULL;
	oldid = mt->trkid;
	count = 0;

	for (i = 0; i < mt->num_slots; ++i) {
		struct input_mt_slot *ps = &mt->slots[i];
		int id = input_mt_get_value(ps, ABS_MT_TRACKING_ID);

		if (id < 0)
			continue;
		if ((id - oldid) & TRKID_SGN) {
			oldest = ps;
			oldid = id;
		}
		count++;
	}

	input_event(dev, EV_KEY, BTN_TOUCH, count > 0);

	if (use_count) {
		if (count == 0 &&
		    !test_bit(ABS_MT_DISTANCE, dev->absbit) &&
		    test_bit(ABS_DISTANCE, dev->absbit) &&
		    input_abs_get_val(dev, ABS_DISTANCE) != 0) {
			/*
			 * Force reporting BTN_TOOL_FINGER for devices that
			 * only report general hover (and not per-contact
			 * distance) when contact is in proximity but not
			 * on the surface.
			 */
			count = 1;
		}

		input_mt_report_finger_count(dev, count);
	}

	if (oldest) {
		int x = input_mt_get_value(oldest, ABS_MT_POSITION_X);
		int y = input_mt_get_value(oldest, ABS_MT_POSITION_Y);

		input_event(dev, EV_ABS, ABS_X, x);
		input_event(dev, EV_ABS, ABS_Y, y);

		if (test_bit(ABS_MT_PRESSURE, dev->absbit)) {
			int p = input_mt_get_value(oldest, ABS_MT_PRESSURE);
			input_event(dev, EV_ABS, ABS_PRESSURE, p);
		}
	} else {
		if (test_bit(ABS_MT_PRESSURE, dev->absbit))
			input_event(dev, EV_ABS, ABS_PRESSURE, 0);
	}
}
EXPORT_SYMBOL(input_mt_report_pointer_emulation);

static void __input_mt_drop_unused(struct input_dev *dev, struct input_mt *mt)
{
	int i;

	for (i = 0; i < mt->num_slots; i++) {
		if (!input_mt_is_used(mt, &mt->slots[i])) {
			input_mt_slot(dev, i);
			input_event(dev, EV_ABS, ABS_MT_TRACKING_ID, -1);
		}
	}
}

/**
 * input_mt_drop_unused() - Inactivate slots not seen in this frame
 * @dev: input device with allocated MT slots
 *
 * Lift all slots not seen since the last call to this function.
 */
void input_mt_drop_unused(struct input_dev *dev)
{
	struct input_mt *mt = dev->mt;

	if (mt) {
		__input_mt_drop_unused(dev, mt);
		mt->frame++;
	}
}
EXPORT_SYMBOL(input_mt_drop_unused);

/**
 * input_mt_sync_frame() - synchronize mt frame
 * @dev: input device with allocated MT slots
 *
 * Close the frame and prepare the internal state for a new one.
 * Depending on the flags, marks unused slots as inactive and performs
 * pointer emulation.
 */
void input_mt_sync_frame(struct input_dev *dev)
{
	struct input_mt *mt = dev->mt;
	bool use_count = false;

	if (!mt)
		return;

	if (mt->flags & INPUT_MT_DROP_UNUSED)
		__input_mt_drop_unused(dev, mt);

	if ((mt->flags & INPUT_MT_POINTER) && !(mt->flags & INPUT_MT_SEMI_MT))
		use_count = true;

	input_mt_report_pointer_emulation(dev, use_count);

	mt->frame++;
}
EXPORT_SYMBOL(input_mt_sync_frame);

static int adjust_dual(int *begin, int step, int *end, int eq, int mu)
{
	int f, *p, s, c;

	if (begin == end)
		return 0;

	f = *begin;
	p = begin + step;
	s = p == end ? f + 1 : *p;

	for (; p != end; p += step) {
		if (*p < f) {
			s = f;
			f = *p;
		} else if (*p < s) {
			s = *p;
		}
	}

	c = (f + s + 1) / 2;
	if (c == 0 || (c > mu && (!eq || mu > 0)))
		return 0;
	/* Improve convergence for positive matrices by penalizing overcovers */
	if (s < 0 && mu <= 0)
		c *= 2;

	for (p = begin; p != end; p += step)
		*p -= c;

	return (c < s && s <= 0) || (f >= 0 && f < c);
}

static void find_reduced_matrix(int *w, int nr, int nc, int nrc, int mu)
{
	int i, k, sum;

	for (k = 0; k < nrc; k++) {
		for (i = 0; i < nr; i++)
			adjust_dual(w + i, nr, w + i + nrc, nr <= nc, mu);
		sum = 0;
		for (i = 0; i < nrc; i += nr)
			sum += adjust_dual(w + i, 1, w + i + nr, nc <= nr, mu);
		if (!sum)
			break;
	}
}

static int input_mt_set_matrix(struct input_mt *mt,
			       const struct input_mt_pos *pos, int num_pos,
			       int mu)
{
	const struct input_mt_pos *p;
	struct input_mt_slot *s;
	int *w = mt->red;
	int x, y;

	for (s = mt->slots; s != mt->slots + mt->num_slots; s++) {
		if (!input_mt_is_active(s))
			continue;
		x = input_mt_get_value(s, ABS_MT_POSITION_X);
		y = input_mt_get_value(s, ABS_MT_POSITION_Y);
		for (p = pos; p != pos + num_pos; p++) {
			int dx = x - p->x, dy = y - p->y;
			*w++ = dx * dx + dy * dy - mu;
		}
	}

	return w - mt->red;
}

static void input_mt_set_slots(struct input_mt *mt,
			       int *slots, int num_pos)
{
	struct input_mt_slot *s;
	int *w = mt->red, j;

	for (j = 0; j != num_pos; j++)
		slots[j] = -1;

	for (s = mt->slots; s != mt->slots + mt->num_slots; s++) {
		if (!input_mt_is_active(s))
			continue;

		for (j = 0; j != num_pos; j++) {
			if (w[j] < 0) {
				slots[j] = s - mt->slots;
				break;
			}
		}

		w += num_pos;
	}

	for (s = mt->slots; s != mt->slots + mt->num_slots; s++) {
		if (input_mt_is_active(s))
			continue;

		for (j = 0; j != num_pos; j++) {
			if (slots[j] < 0) {
				slots[j] = s - mt->slots;
				break;
			}
		}
	}
}

/**
 * input_mt_assign_slots() - perform a best-match assignment
 * @dev: input device with allocated MT slots
 * @slots: the slot assignment to be filled
 * @pos: the position array to match
 * @num_pos: number of positions
 * @dmax: maximum ABS_MT_POSITION displacement (zero for infinite)
 *
 * Performs a best match against the current contacts and returns
 * the slot assignment list. New contacts are assigned to unused
 * slots.
 *
 * The assignments are balanced so that all coordinate displacements are
 * below the euclidian distance dmax. If no such assignment can be found,
 * some contacts are assigned to unused slots.
 *
 * Returns zero on success, or negative error in case of failure.
 */
int input_mt_assign_slots(struct input_dev *dev, int *slots,
			  const struct input_mt_pos *pos, int num_pos,
			  int dmax)
{
	struct input_mt *mt = dev->mt;
	int mu = 2 * dmax * dmax;
	int nrc;

	if (!mt || !mt->red)
		return -ENXIO;
	if (num_pos > mt->num_slots)
		return -EINVAL;
	if (num_pos < 1)
		return 0;

	nrc = input_mt_set_matrix(mt, pos, num_pos, mu);
	find_reduced_matrix(mt->red, num_pos, nrc / num_pos, nrc, mu);
	input_mt_set_slots(mt, slots, num_pos);

	return 0;
}
EXPORT_SYMBOL(input_mt_assign_slots);

/**
 * input_mt_get_slot_by_key() - return slot matching key
 * @dev: input device with allocated MT slots
 * @key: the key of the sought slot
 *
 * Returns the slot of the given key, if it exists, otherwise
 * set the key on the first unused slot and return.
 *
 * If no available slot can be found, -1 is returned.
 * Note that for this function to work properly, input_mt_sync_frame() has
 * to be called at each frame.
 */
int input_mt_get_slot_by_key(struct input_dev *dev, int key)
{
	struct input_mt *mt = dev->mt;
	struct input_mt_slot *s;

	if (!mt)
		return -1;

	for (s = mt->slots; s != mt->slots + mt->num_slots; s++)
		if (input_mt_is_active(s) && s->key == key)
			return s - mt->slots;

	for (s = mt->slots; s != mt->slots + mt->num_slots; s++)
		if (!input_mt_is_active(s) && !input_mt_is_used(mt, s)) {
			s->key = key;
			return s - mt->slots;
		}

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