xref: /openbsd-src/sys/dev/wscons/wstpad.c (revision 93ab69426ace0f2c718831e73925aa538b22c5b4)

/* $OpenBSD: wstpad.c,v 1.34 2024/03/25 13:01:49 mvs Exp $ */

/*
 * Copyright (c) 2015, 2016 Ulf Brosziewski
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * touchpad input processing
 */

#include <sys/param.h>
#include <sys/kernel.h>
#include <sys/malloc.h>
#include <sys/proc.h>
#include <sys/systm.h>
#include <sys/signalvar.h>
#include <sys/timeout.h>

#include <dev/wscons/wsconsio.h>
#include <dev/wscons/wsmousevar.h>
#include <dev/wscons/wseventvar.h>
#include <dev/wscons/wsmouseinput.h>

#define BTNMASK(n)		((n) > 0 && (n) <= 32 ? 1 << ((n) - 1) : 0)

#define LEFTBTN			BTNMASK(1)
#define MIDDLEBTN		BTNMASK(2)
#define RIGHTBTN		BTNMASK(3)

#define PRIMARYBTN LEFTBTN

#define PRIMARYBTN_CLICKED(tp) ((tp)->btns_sync & PRIMARYBTN & (tp)->btns)
#define PRIMARYBTN_RELEASED(tp) ((tp)->btns_sync & PRIMARYBTN & ~(tp)->btns)

#define IS_MT(tp) ((tp)->features & WSTPAD_MT)
#define DISABLE(tp) ((tp)->features & WSTPAD_DISABLE)

/*
 * Ratios to the height or width of the touchpad surface, in
 * [*.12] fixed-point format:
 */
#define V_EDGE_RATIO_DEFAULT	205
#define B_EDGE_RATIO_DEFAULT	410
#define T_EDGE_RATIO_DEFAULT	512
#define CENTER_RATIO_DEFAULT	512

#define TAP_MAXTIME_DEFAULT	180
#define TAP_CLICKTIME_DEFAULT	180
#define TAP_LOCKTIME_DEFAULT	0
#define TAP_BTNMAP_SIZE		3

#define CLICKDELAY_MS		20
#define FREEZE_MS		100
#define MATCHINTERVAL_MS	45
#define STOPINTERVAL_MS		55

#define MAG_LOW			(10 << 12)
#define MAG_MEDIUM		(18 << 12)

enum tpad_handlers {
	SOFTBUTTON_HDLR,
	TOPBUTTON_HDLR,
	TAP_HDLR,
	F2SCROLL_HDLR,
	EDGESCROLL_HDLR,
	CLICK_HDLR,
};

enum tap_state {
	TAP_DETECT,
	TAP_IGNORE,
	TAP_LIFTED,
	TAP_LOCKED,
	TAP_LOCKED_DRAG,
};

enum tpad_cmd {
	CLEAR_MOTION_DELTAS,
	SOFTBUTTON_DOWN,
	SOFTBUTTON_UP,
	TAPBUTTON_SYNC,
	TAPBUTTON_DOWN,
	TAPBUTTON_UP,
	VSCROLL,
	HSCROLL,
};

/*
 * tpad_touch.flags:
 */
#define L_EDGE			(1 << 0)
#define R_EDGE			(1 << 1)
#define T_EDGE			(1 << 2)
#define B_EDGE			(1 << 3)
#define THUMB 			(1 << 4)

#define EDGES (L_EDGE | R_EDGE | T_EDGE | B_EDGE)

/*
 * A touch is "centered" if it does not start and remain at the top
 * edge or one of the vertical edges.  Two-finger scrolling and tapping
 * require that at least one touch is centered.
 */
#define CENTERED(t) (((t)->flags & (L_EDGE | R_EDGE | T_EDGE)) == 0)

enum touchstates {
	TOUCH_NONE,
	TOUCH_BEGIN,
	TOUCH_UPDATE,
	TOUCH_END,
};

struct tpad_touch {
	u_int flags;
	enum touchstates state;
	int x;
	int y;
	int dir;
	struct timespec start;
	struct timespec match;
	struct position *pos;
	struct {
		int x;
		int y;
		struct timespec time;
	} orig;
};

/*
 * wstpad.features
 */
#define WSTPAD_SOFTBUTTONS	(1 << 0)
#define WSTPAD_SOFTMBTN		(1 << 1)
#define WSTPAD_TOPBUTTONS	(1 << 2)
#define WSTPAD_TWOFINGERSCROLL	(1 << 3)
#define WSTPAD_EDGESCROLL	(1 << 4)
#define WSTPAD_HORIZSCROLL	(1 << 5)
#define WSTPAD_SWAPSIDES	(1 << 6)
#define WSTPAD_DISABLE		(1 << 7)
#define WSTPAD_MTBUTTONS	(1 << 8)

#define WSTPAD_MT		(1U << 31)


struct wstpad {
	u_int features;
	u_int handlers;

	/*
	 * t always points into the tpad_touches array, which has at
	 * least one element. If there is more than one, t selects
	 * the pointer-controlling touch.
	 */
	struct tpad_touch *t;
	struct tpad_touch *tpad_touches;

	u_int mtcycle;
	u_int ignore;

	int contacts;
	int prev_contacts;
	u_int btns;
	u_int btns_sync;
	int ratio;

	struct timespec time;

	u_int freeze;
	struct timespec freeze_ts;

	/* edge coordinates */
	struct {
		int left;
		int right;
		int top;
		int bottom;
		int center;
		int center_left;
		int center_right;
		int low;
	} edge;

	struct {
		/* ratios to the surface width or height */
		int left_edge;
		int right_edge;
		int top_edge;
		int bottom_edge;
		int center_width;
		/* two-finger contacts */
		int f2pressure;
		int f2width;
		/* MTBUTTONS: distance limit for two-finger clicks */
		int mtbtn_maxdist;
	} params;

	/* handler state and configuration: */

	u_int softbutton;
	u_int sbtnswap;

	struct {
		enum tap_state state;
		int contacts;
		int valid;
		u_int pending;
		u_int button;
		int masked;
		int maxdist;
		struct timeout to;
		/* parameters: */
		struct timespec maxtime;
		int clicktime;
		int locktime;
		u_int btnmap[TAP_BTNMAP_SIZE];
	} tap;

	struct {
		int dz;
		int dw;
		int hdist;
		int vdist;
		int mag;
	} scroll;
};

static const struct timespec match_interval =
    { .tv_sec = 0, .tv_nsec = MATCHINTERVAL_MS * 1000000 };

static const struct timespec stop_interval =
    { .tv_sec = 0, .tv_nsec = STOPINTERVAL_MS * 1000000 };

/*
 * Coordinates in the wstpad struct are "normalized" device coordinates,
 * the orientation is left-to-right and upward.
 */
static inline int
normalize_abs(struct axis_filter *filter, int val)
{
	return (filter->inv ? filter->inv - val : val);
}

static inline int
normalize_rel(struct axis_filter *filter, int val)
{
	return (filter->inv ? -val : val);
}

/*
 * Directions of motion are represented by numbers in the range 0 - 11,
 * corresponding to clockwise counted circle sectors:
 *
 *              11 | 0
 *           10    |    1
 *          9      |      2
 *          -------+-------
 *          8      |      3
 *            7    |    4
 *               6 | 5
 *
 */
/* Tangent constants in [*.12] fixed-point format: */
#define TAN_DEG_60 7094
#define TAN_DEG_30 2365

#define NORTH(d) ((d) == 0 || (d) == 11)
#define SOUTH(d) ((d) == 5 || (d) == 6)
#define EAST(d) ((d) == 2 || (d) == 3)
#define WEST(d) ((d) == 8 || (d) == 9)

static inline int
direction(int dx, int dy, int ratio)
{
	int rdy, dir = -1;

	if (dx || dy) {
		rdy = abs(dy) * ratio;
		if (abs(dx) * TAN_DEG_60 < rdy)
			dir = 0;
		else if (abs(dx) * TAN_DEG_30 < rdy)
			dir = 1;
		else
			dir = 2;
		if ((dx < 0) != (dy < 0))
			dir = 5 - dir;
		if (dx < 0)
			dir += 6;
	}
	return dir;
}

static inline int
dircmp(int dir1, int dir2)
{
	int diff = abs(dir1 - dir2);
	return (diff <= 6 ? diff : 12 - diff);
}

/*
 * Update direction and timespec attributes for a touch.  They are used to
 * determine whether it is moving - or resting - stably.
 *
 * The callers pass touches from the current frame and the touches that are
 * no longer present in the update cycle to this function.  Even though this
 * ensures that pairs of zero deltas do not result from stale coordinates,
 * zero deltas do not reset the state immediately.  A short time span - the
 * "stop interval" - must pass before the state is cleared, which is
 * necessary because some touchpads report intermediate stops when a touch
 * is moving very slowly.
 */
void
wstpad_set_direction(struct wstpad *tp, struct tpad_touch *t, int dx, int dy)
{
	int dir;
	struct timespec ts;

	if (t->state != TOUCH_UPDATE) {
		t->dir = -1;
		memcpy(&t->start, &tp->time, sizeof(struct timespec));
		return;
	}

	dir = direction(dx, dy, tp->ratio);
	if (dir >= 0) {
		if (t->dir < 0 || dircmp(dir, t->dir) > 1) {
			memcpy(&t->start, &tp->time, sizeof(struct timespec));
		}
		t->dir = dir;
		memcpy(&t->match, &tp->time, sizeof(struct timespec));
	} else if (t->dir >= 0) {
		timespecsub(&tp->time, &t->match, &ts);
		if (timespeccmp(&ts, &stop_interval, >=)) {
			t->dir = -1;
			memcpy(&t->start, &t->match, sizeof(struct timespec));
		}
	}
}

/*
 * Make a rough, but quick estimation of the speed of a touch.  Its
 * distance to the previous position is scaled by factors derived
 * from the average update rate and the deceleration parameter
 * (filter.dclr).  The unit of the result is:
 *         (filter.dclr / 100) device units per millisecond
 *
 * Magnitudes are returned in [*.12] fixed-point format.  For purposes
 * of filtering, they are divided into medium and high speeds
 * (> MAG_MEDIUM), low speeds, and very low speeds (< MAG_LOW).
 *
 * The scale factors are not affected if deceleration is turned off.
 */
static inline int
magnitude(struct wsmouseinput *input, int dx, int dy)
{
	int h, v;

	h = abs(dx) * input->filter.h.mag_scale;
	v = abs(dy) * input->filter.v.mag_scale;
	/* Return an "alpha-max-plus-beta-min" approximation: */
	return (h >= v ? h + 3 * v / 8 : v + 3 * h / 8);
}

/*
 * Treat a touch as stable if it is moving at a medium or high speed,
 * if it is moving continuously, or if it has stopped for a certain
 * time span.
 */
int
wstpad_is_stable(struct wsmouseinput *input, struct tpad_touch *t)
{
	struct timespec ts;

	if (t->dir >= 0) {
		if (magnitude(input, t->pos->dx, t->pos->dy) > MAG_MEDIUM)
			return (1);
		timespecsub(&t->match, &t->start, &ts);
	} else {
		timespecsub(&input->tp->time, &t->start, &ts);
	}

	return (timespeccmp(&ts, &match_interval, >=));
}

/*
 * If a touch starts in an edge area, pointer movement will be
 * suppressed as long as it stays in that area.
 */
static inline u_int
edge_flags(struct wstpad *tp, int x, int y)
{
	u_int flags = 0;

	if (x < tp->edge.left)
		flags |= L_EDGE;
	else if (x >= tp->edge.right)
		flags |= R_EDGE;
	if (y < tp->edge.bottom)
		flags |= B_EDGE;
	else if (y >= tp->edge.top)
		flags |= T_EDGE;

	return (flags);
}

static inline struct tpad_touch *
get_2nd_touch(struct wsmouseinput *input)
{
	struct wstpad *tp = input->tp;
	int slot;

	if (IS_MT(tp)) {
		slot = ffs(input->mt.touches & ~(input->mt.ptr | tp->ignore));
		if (slot)
			return &tp->tpad_touches[--slot];
	}
	return NULL;
}

/* Suppress pointer motion for a short period of time. */
static inline void
set_freeze_ts(struct wstpad *tp, int sec, int ms)
{
	tp->freeze_ts.tv_sec = sec;
	tp->freeze_ts.tv_nsec = ms * 1000000;
	timespecadd(&tp->time, &tp->freeze_ts, &tp->freeze_ts);
}


/* Return TRUE if two-finger- or edge-scrolling would be valid. */
int
wstpad_scroll_coords(struct wsmouseinput *input, int *dx, int *dy)
{
	struct wstpad *tp = input->tp;

	if (tp->contacts != tp->prev_contacts || tp->btns || tp->btns_sync) {
		tp->scroll.dz = 0;
		tp->scroll.dw = 0;
		return (0);
	}
	if ((input->motion.sync & SYNC_POSITION) == 0)
		return (0);
	/*
	 * Try to exclude accidental scroll events by checking whether the
	 * pointer-controlling touch is stable.  The check, which may cause
	 * a short delay, is only applied initially, a touch that stops and
	 * resumes scrolling is not affected.
	 */
	if (tp->scroll.dz || tp->scroll.dw || wstpad_is_stable(input, tp->t)) {
		*dx = normalize_rel(&input->filter.h, input->motion.pos.dx);
		*dy = normalize_rel(&input->filter.v, input->motion.pos.dy);
		return (*dx || *dy);
	}

	return (0);
}

void
wstpad_scroll(struct wstpad *tp, int dx, int dy, int mag, u_int *cmds)
{
	int dz, dw, n = 1;

	/*
	 * The function applies strong deceleration, but only to input with
	 * very low speeds.  A higher threshold might make applications
	 * without support for precision scrolling appear unresponsive.
	 */
	mag = tp->scroll.mag = imin(MAG_MEDIUM,
	    (mag + 3 * tp->scroll.mag) / 4);
	if (mag < MAG_LOW)
		n = (MAG_LOW - mag) / 4096 + 1;

	if (dy && tp->scroll.vdist) {
		if (tp->scroll.dw) {
			/*
			 * Before switching the axis, wstpad_scroll_coords()
			 * should check again whether the movement is stable.
			 */
			tp->scroll.dw = 0;
			return;
		}
		dz = -dy * 4096 / (tp->scroll.vdist * n);
		if (tp->scroll.dz) {
			if ((dy < 0) != (tp->scroll.dz > 0))
				tp->scroll.dz = -tp->scroll.dz;
			dz = (dz + 3 * tp->scroll.dz) / 4;
		}
		if (dz) {
			tp->scroll.dz = dz;
			*cmds |= 1 << VSCROLL;
		}

	} else if (dx && tp->scroll.hdist) {
		if (tp->scroll.dz) {
			tp->scroll.dz = 0;
			return;
		}
		dw = dx * 4096 / (tp->scroll.hdist * n);
		if (tp->scroll.dw) {
			if ((dx > 0) != (tp->scroll.dw > 0))
				tp->scroll.dw = -tp->scroll.dw;
			dw = (dw + 3 * tp->scroll.dw) / 4;
		}
		if (dw) {
			tp->scroll.dw = dw;
			*cmds |= 1 << HSCROLL;
		}
	}
}

void
wstpad_f2scroll(struct wsmouseinput *input, u_int *cmds)
{
	struct wstpad *tp = input->tp;
	struct tpad_touch *t2;
	int dir, dx, dy, centered;

	if (tp->ignore == 0) {
		if (tp->contacts != 2)
			return;
	} else if (tp->contacts != 3 || (tp->ignore == input->mt.ptr)) {
		return;
	}

	if (!wstpad_scroll_coords(input, &dx, &dy))
		return;

	dir = tp->t->dir;
	if (!(NORTH(dir) || SOUTH(dir)))
		dy = 0;
	if (!(EAST(dir) || WEST(dir)))
		dx = 0;

	if (dx || dy) {
		centered = CENTERED(tp->t);
		if (IS_MT(tp)) {
			t2 = get_2nd_touch(input);
			if (t2 == NULL)
				return;
			dir = t2->dir;
			if ((dy > 0 && !NORTH(dir)) || (dy < 0 && !SOUTH(dir)))
				return;
			if ((dx > 0 && !EAST(dir)) || (dx < 0 && !WEST(dir)))
				return;
			if (!wstpad_is_stable(input, t2) &&
			    !(tp->scroll.dz || tp->scroll.dw))
				return;
			centered |= CENTERED(t2);
		}
		if (centered) {
			wstpad_scroll(tp, dx, dy,
			    magnitude(input, dx, dy), cmds);
			set_freeze_ts(tp, 0, FREEZE_MS);
		}
	}
}

void
wstpad_edgescroll(struct wsmouseinput *input, u_int *cmds)
{
	struct wstpad *tp = input->tp;
	struct tpad_touch *t = tp->t;
	u_int v_edge, b_edge;
	int dx, dy;

	if (!wstpad_scroll_coords(input, &dx, &dy) || tp->contacts != 1)
		return;

	v_edge = (tp->features & WSTPAD_SWAPSIDES) ? L_EDGE : R_EDGE;
	b_edge = (tp->features & WSTPAD_HORIZSCROLL) ? B_EDGE : 0;

	if ((t->flags & v_edge) == 0)
		dy = 0;
	if ((t->flags & b_edge) == 0)
		dx = 0;

	if (dx || dy)
		wstpad_scroll(tp, dx, dy, magnitude(input, dx, dy), cmds);
}

static inline u_int
sbtn(struct wstpad *tp, int x, int y)
{
	if (y >= tp->edge.bottom)
		return (0);
	if ((tp->features & WSTPAD_SOFTMBTN)
	    && x >= tp->edge.center_left
	    && x < tp->edge.center_right)
		return (MIDDLEBTN);
	return ((x < tp->edge.center ? LEFTBTN : RIGHTBTN) ^ tp->sbtnswap);
}

static inline u_int
top_sbtn(struct wstpad *tp, int x, int y)
{
	if (y < tp->edge.top)
		return (0);
	if (x < tp->edge.center_left)
		return (LEFTBTN ^ tp->sbtnswap);
	return (x > tp->edge.center_right
	    ? (RIGHTBTN ^ tp->sbtnswap) : MIDDLEBTN);
}

u_int
wstpad_get_sbtn(struct wsmouseinput *input, int top)
{
	struct wstpad *tp = input->tp;
	struct tpad_touch *t = tp->t;
	u_int btn;

	btn = 0;
	if (tp->contacts) {
		btn = top ? top_sbtn(tp, t->x, t->y) : sbtn(tp, t->x, t->y);
		/*
		 * If there is no middle-button area, but contacts in both
		 * halves of the edge zone, generate a middle-button event:
		 */
		if (btn && IS_MT(tp) && tp->contacts == 2
		    && !top && !(tp->features & WSTPAD_SOFTMBTN)) {
			if ((t = get_2nd_touch(input)) != NULL)
				btn |= sbtn(tp, t->x, t->y);
			if (btn == (LEFTBTN | RIGHTBTN))
				btn = MIDDLEBTN;
		}
	}
	return (btn != PRIMARYBTN ? btn : 0);
}

int
wstpad_mtbtn_contacts(struct wsmouseinput *input)
{
	struct wstpad *tp = input->tp;
	struct tpad_touch *t;
	int dx, dy, dist, limit;

	if (tp->ignore != 0)
		return (tp->contacts - 1);

	if (tp->contacts == 2 && (t = get_2nd_touch(input)) != NULL) {
		dx = abs(t->x - tp->t->x) << 12;
		dy = abs(t->y - tp->t->y) * tp->ratio;
		dist = (dx >= dy ? dx + 3 * dy / 8 : dy + 3 * dx / 8);
		limit = tp->params.mtbtn_maxdist << 12;
		if (input->mt.ptr_mask != 0)
			limit = limit * 2 / 3;
		if (dist > limit)
			return (1);
	}
	return (tp->contacts);
}

u_int
wstpad_get_mtbtn(struct wsmouseinput *input)
{
	int contacts = wstpad_mtbtn_contacts(input);
	return (contacts == 2 ? RIGHTBTN : (contacts == 3 ? MIDDLEBTN : 0));
}


void
wstpad_softbuttons(struct wsmouseinput *input, u_int *cmds, int hdlr)
{
	struct wstpad *tp = input->tp;
	int top = (hdlr == TOPBUTTON_HDLR);

	if (tp->softbutton && PRIMARYBTN_RELEASED(tp)) {
		*cmds |= 1 << SOFTBUTTON_UP;
		return;
	}

	if (tp->softbutton == 0 && PRIMARYBTN_CLICKED(tp)) {
		tp->softbutton = ((tp->features & WSTPAD_MTBUTTONS)
		    ? wstpad_get_mtbtn(input) : wstpad_get_sbtn(input, top));
		if (tp->softbutton)
			*cmds |= 1 << SOFTBUTTON_DOWN;
	}
}

/* Check whether the duration of t is within the tap limit. */
int
wstpad_is_tap(struct wstpad *tp, struct tpad_touch *t)
{
	struct timespec ts;

	timespecsub(&tp->time, &t->orig.time, &ts);
	return (timespeccmp(&ts, &tp->tap.maxtime, <));
}

/*
 * At least one MT touch must remain close to its origin and end
 * in the main area.  The same conditions apply to one-finger taps
 * on single-touch devices.
 */
void
wstpad_tap_filter(struct wstpad *tp, struct tpad_touch *t)
{
	int dx, dy, dist = 0;

	if (IS_MT(tp) || tp->tap.contacts == 1) {
		dx = abs(t->x - t->orig.x) << 12;
		dy = abs(t->y - t->orig.y) * tp->ratio;
		dist = (dx >= dy ? dx + 3 * dy / 8 : dy + 3 * dx / 8);
	}
	tp->tap.valid = (CENTERED(t) && dist <= (tp->tap.maxdist << 12));
}


/*
 * Return the oldest touch in the TOUCH_END state, or NULL.
 */
struct tpad_touch *
wstpad_tap_touch(struct wsmouseinput *input)
{
	struct wstpad *tp = input->tp;
	struct tpad_touch *s, *t = NULL;
	u_int lifted;
	int slot;

	if (IS_MT(tp)) {
		lifted = (input->mt.sync[MTS_TOUCH] & ~input->mt.touches);
		FOREACHBIT(lifted, slot) {
			s = &tp->tpad_touches[slot];
			if (tp->tap.state == TAP_DETECT && !tp->tap.valid)
				wstpad_tap_filter(tp, s);
			if (t == NULL || timespeccmp(&t->orig.time,
			    &s->orig.time, >))
				t = s;
		}
	} else {
		if (tp->t->state == TOUCH_END) {
			t = tp->t;
			if (tp->tap.state == TAP_DETECT && !tp->tap.valid)
				wstpad_tap_filter(tp, t);
		}
	}

	return (t);
}

/* Determine the "tap button", keep track of whether a touch is masked. */
u_int
wstpad_tap_button(struct wstpad *tp)
{
	int n = tp->tap.contacts - tp->contacts - 1;

	tp->tap.masked = tp->contacts;

	return (n >= 0 && n < TAP_BTNMAP_SIZE ? tp->tap.btnmap[n] : 0);
}

/*
 * In the hold/drag state, do not mask touches if no masking was involved
 * in the preceding tap gesture.
 */
static inline int
tap_unmask(struct wstpad *tp)
{
	return ((tp->tap.button || tp->tap.pending) && tp->tap.masked == 0);
}

/*
 * In the default configuration, this handler maps one-, two-, and
 * three-finger taps to left-button, right-button, and middle-button
 * events, respectively.  Setting the LOCKTIME parameter enables
 * "locked drags", which are finished by a timeout or a tap-to-end
 * gesture.
 */
void
wstpad_tap(struct wsmouseinput *input, u_int *cmds)
{
	struct wstpad *tp = input->tp;
	struct tpad_touch *t;
	int contacts, is_tap, slot, err = 0;

	/* Synchronize the button states, if necessary. */
	if (input->btn.sync)
		*cmds |= 1 << TAPBUTTON_SYNC;

	/*
	 * It is possible to produce a click within the tap timeout.
	 * Wait for a new touch before generating new button events.
	 */
	if (PRIMARYBTN_RELEASED(tp))
		tp->tap.contacts = 0;

	/* Reset the detection state whenever a new touch starts. */
	if (tp->contacts > tp->prev_contacts || (IS_MT(tp) &&
	    (input->mt.touches & input->mt.sync[MTS_TOUCH]))) {
		tp->tap.contacts = tp->contacts;
		tp->tap.valid = 0;
	}

	/*
	 * The filtered number of active touches excludes a masked
	 * touch if its duration exceeds the tap limit.
	 */
	contacts = tp->contacts;
	if ((slot = ffs(input->mt.ptr_mask) - 1) >= 0
	    && !wstpad_is_tap(tp, &tp->tpad_touches[slot])
	    && !tap_unmask(tp)) {
		contacts--;
	}

	switch (tp->tap.state) {
	case TAP_DETECT:
		/* Find the oldest touch in the TOUCH_END state. */
		t = wstpad_tap_touch(input);
		if (t) {
			is_tap = wstpad_is_tap(tp, t);
			if (is_tap && contacts == 0) {
				if (tp->tap.button)
					*cmds |= 1 << TAPBUTTON_UP;
				tp->tap.pending = (tp->tap.valid
				    ? wstpad_tap_button(tp) : 0);
				if (tp->tap.pending) {
					tp->tap.state = TAP_LIFTED;
					err = !timeout_add_msec(&tp->tap.to,
					    CLICKDELAY_MS);
				}
			} else if (!is_tap && tp->tap.locktime == 0) {
				if (contacts == 0 && tp->tap.button)
					*cmds |= 1 << TAPBUTTON_UP;
				else if (contacts)
					tp->tap.state = TAP_IGNORE;
			} else if (!is_tap && tp->tap.button) {
				if (contacts == 0) {
					tp->tap.state = TAP_LOCKED;
					err = !timeout_add_msec(&tp->tap.to,
					    tp->tap.locktime);
				} else {
					tp->tap.state = TAP_LOCKED_DRAG;
				}
			}
		}
		break;
	case TAP_IGNORE:
		if (contacts == 0) {
			tp->tap.state = TAP_DETECT;
			if (tp->tap.button)
				*cmds |= 1 << TAPBUTTON_UP;
		}
		break;
	case TAP_LIFTED:
		if (contacts) {
			timeout_del(&tp->tap.to);
			tp->tap.state = TAP_DETECT;
			if (tp->tap.pending)
				*cmds |= 1 << TAPBUTTON_DOWN;
		}
		break;
	case TAP_LOCKED:
		if (contacts) {
			timeout_del(&tp->tap.to);
			tp->tap.state = TAP_LOCKED_DRAG;
		}
		break;
	case TAP_LOCKED_DRAG:
		if (contacts == 0) {
			t = wstpad_tap_touch(input);
			if (t && wstpad_is_tap(tp, t)) {
				/* "tap-to-end" */
				*cmds |= 1 << TAPBUTTON_UP;
				tp->tap.state = TAP_DETECT;
			} else {
				tp->tap.state = TAP_LOCKED;
				err = !timeout_add_msec(&tp->tap.to,
				    tp->tap.locktime);
			}
		}
		break;
	}

	if (err) { /* Did timeout_add fail? */
		input->sbtn.buttons &= ~tp->tap.button;
		input->sbtn.sync |= tp->tap.button;
		tp->tap.pending = 0;
		tp->tap.button = 0;
		tp->tap.state = TAP_DETECT;
	}
}

int
wstpad_tap_sync(struct wsmouseinput *input) {
	struct wstpad *tp = input->tp;

	return ((tp->tap.button & (input->btn.buttons | tp->softbutton)) == 0
	    || (tp->tap.button == PRIMARYBTN && tp->softbutton));
}

void
wstpad_tap_timeout(void *p)
{
	struct wsmouseinput *input = p;
	struct wstpad *tp = input->tp;
	struct evq_access evq;
	u_int btn;
	int s, ev;

	s = spltty();
	evq.evar = *input->evar;
	if (evq.evar != NULL && tp != NULL) {
		ev = 0;
		if (tp->tap.pending) {
			tp->tap.button = tp->tap.pending;
			tp->tap.pending = 0;
			input->sbtn.buttons |= tp->tap.button;
			timeout_add_msec(&tp->tap.to, tp->tap.clicktime);
			if (wstpad_tap_sync(input)) {
				ev = BTN_DOWN_EV;
				btn = ffs(tp->tap.button) - 1;
			}
		} else {
			if (wstpad_tap_sync(input)) {
				ev = BTN_UP_EV;
				btn = ffs(tp->tap.button) - 1;
			}
			if (tp->tap.button != tp->softbutton)
				input->sbtn.buttons &= ~tp->tap.button;
			tp->tap.button = 0;
			tp->tap.state = TAP_DETECT;
		}
		if (ev) {
			evq.put = evq.evar->ws_put;
			evq.result = EVQ_RESULT_NONE;
			getnanotime(&evq.ts);
			wsmouse_evq_put(&evq, ev, btn);
			wsmouse_evq_put(&evq, SYNC_EV, 0);
			if (evq.result == EVQ_RESULT_SUCCESS) {
				if (input->flags & LOG_EVENTS) {
					wsmouse_log_events(input, &evq);
				}
				evq.evar->ws_put = evq.put;
				WSEVENT_WAKEUP(evq.evar);
			} else {
				input->sbtn.sync |= tp->tap.button;
			}
		}
	}
	splx(s);
}

/*
 * Suppress accidental pointer movements after a click on a clickpad.
 */
void
wstpad_click(struct wsmouseinput *input)
{
	struct wstpad *tp = input->tp;

	if (tp->contacts == 1 &&
	    (PRIMARYBTN_CLICKED(tp) || PRIMARYBTN_RELEASED(tp)))
		set_freeze_ts(tp, 0, FREEZE_MS);
}

/* Translate the "command" bits into the sync-state of wsmouse. */
void
wstpad_cmds(struct wsmouseinput *input, u_int cmds)
{
	struct wstpad *tp = input->tp;
	int n;

	FOREACHBIT(cmds, n) {
		switch (n) {
		case CLEAR_MOTION_DELTAS:
			input->motion.dx = input->motion.dy = 0;
			if (input->motion.dz == 0 && input->motion.dw == 0)
				input->motion.sync &= ~SYNC_DELTAS;
			continue;
		case SOFTBUTTON_DOWN:
			input->btn.sync &= ~PRIMARYBTN;
			input->sbtn.buttons |= tp->softbutton;
			if (tp->softbutton != tp->tap.button)
				input->sbtn.sync |= tp->softbutton;
			continue;
		case SOFTBUTTON_UP:
			input->btn.sync &= ~PRIMARYBTN;
			if (tp->softbutton != tp->tap.button) {
				input->sbtn.buttons &= ~tp->softbutton;
				input->sbtn.sync |= tp->softbutton;
			}
			tp->softbutton = 0;
			continue;
		case TAPBUTTON_SYNC:
			if (tp->tap.button)
				input->btn.sync &= ~tp->tap.button;
			continue;
		case TAPBUTTON_DOWN:
			tp->tap.button = tp->tap.pending;
			tp->tap.pending = 0;
			input->sbtn.buttons |= tp->tap.button;
			if (wstpad_tap_sync(input))
				input->sbtn.sync |= tp->tap.button;
			continue;
		case TAPBUTTON_UP:
			if (tp->tap.button != tp->softbutton)
				input->sbtn.buttons &= ~tp->tap.button;
			if (wstpad_tap_sync(input))
				input->sbtn.sync |= tp->tap.button;
			tp->tap.button = 0;
			continue;
		case HSCROLL:
			input->motion.dw = tp->scroll.dw;
			input->motion.sync |= SYNC_DELTAS;
			continue;
		case VSCROLL:
			input->motion.dz = tp->scroll.dz;
			input->motion.sync |= SYNC_DELTAS;
			continue;
		default:
			printf("[wstpad] invalid cmd %d\n", n);
			break;
		}
	}
}


/*
 * Set the state of touches that have ended. TOUCH_END is a transitional
 * state and will be changed to TOUCH_NONE before process_input() returns.
 */
static inline void
clear_touchstates(struct wsmouseinput *input, enum touchstates state)
{
	u_int touches;
	int slot;

	touches = input->mt.sync[MTS_TOUCH] & ~input->mt.touches;
	FOREACHBIT(touches, slot)
		input->tp->tpad_touches[slot].state = state;
}

void
wstpad_mt_inputs(struct wsmouseinput *input)
{
	struct wstpad *tp = input->tp;
	struct tpad_touch *t;
	int slot, dx, dy;
	u_int touches, inactive;

	/* TOUCH_BEGIN */
	touches = input->mt.touches & input->mt.sync[MTS_TOUCH];
	FOREACHBIT(touches, slot) {
		t = &tp->tpad_touches[slot];
		t->state = TOUCH_BEGIN;
		t->x = normalize_abs(&input->filter.h, t->pos->x);
		t->y = normalize_abs(&input->filter.v, t->pos->y);
		t->orig.x = t->x;
		t->orig.y = t->y;
		memcpy(&t->orig.time, &tp->time, sizeof(struct timespec));
		t->flags = edge_flags(tp, t->x, t->y);
		wstpad_set_direction(tp, t, 0, 0);
	}

	/* TOUCH_UPDATE */
	touches = input->mt.touches & input->mt.frame;
	if (touches & tp->mtcycle) {
		/*
		 * Slot data may be synchronized separately, in any order,
		 * or not at all if there is no delta.  Identify the touches
		 * without deltas.
		 */
		inactive = input->mt.touches & ~tp->mtcycle;
		tp->mtcycle = touches;
	} else {
		inactive = 0;
		tp->mtcycle |= touches;
	}
	touches = input->mt.touches & ~input->mt.sync[MTS_TOUCH];
	FOREACHBIT(touches, slot) {
		t = &tp->tpad_touches[slot];
		t->state = TOUCH_UPDATE;
		if ((1 << slot) & input->mt.frame) {
			dx = normalize_abs(&input->filter.h, t->pos->x) - t->x;
			t->x += dx;
			dy = normalize_abs(&input->filter.v, t->pos->y) - t->y;
			t->y += dy;
			t->flags &= (~EDGES | edge_flags(tp, t->x, t->y));
			if (wsmouse_hysteresis(input, t->pos))
				dx = dy = 0;
			wstpad_set_direction(tp, t, dx, dy);
		} else if ((1 << slot) & inactive) {
			wstpad_set_direction(tp, t, 0, 0);
		}
	}

	clear_touchstates(input, TOUCH_END);
}

/*
 * Identify "thumb" contacts in the bottom area.  The identification
 * has three stages:
 * 1. If exactly one of two or more touches is in the bottom area, it
 * is masked, which means it does not receive pointer control as long
 * as there are alternatives.  Once set, the mask will only be cleared
 * when the touch is released.
 * Tap detection ignores a masked touch if it does not participate in
 * a tap gesture.
 * 2. If the pointer-controlling touch is moving stably while a masked
 * touch in the bottom area is resting, or only moving minimally, the
 * pointer mask is copied to tp->ignore.  In this stage, the masked
 * touch does not block pointer movement, and it is ignored by
 * wstpad_f2scroll().
 * Decisions are made more or less immediately, there may be errors
 * in edge cases.  If a fast or long upward movement is detected,
 * tp->ignore is cleared.  There is no other transition from stage 2
 * to scrolling, or vice versa, for a pair of touches.
 * 3. If tp->ignore is set and the touch is resting, it is marked as
 * thumb, and it will be ignored until it ends.
 */
void
wstpad_mt_masks(struct wsmouseinput *input)
{
	struct wstpad *tp = input->tp;
	struct tpad_touch *t;
	struct position *pos;
	u_int mask;
	int slot;

	tp->ignore &= input->mt.touches;

	if (tp->contacts < 2)
		return;

	if (tp->ignore) {
		slot = ffs(tp->ignore) - 1;
		t = &tp->tpad_touches[slot];
		if (t->flags & THUMB)
			return;
		if (t->dir < 0 && wstpad_is_stable(input, t)) {
			t->flags |= THUMB;
			return;
		}
		/* The edge.low area is a bit larger than the bottom area. */
		if (t->y >= tp->edge.low || (NORTH(t->dir) &&
		    magnitude(input, t->pos->dx, t->pos->dy) >= MAG_MEDIUM))
			tp->ignore = 0;
		return;
	}

	if (input->mt.ptr_mask == 0) {
		mask = ~0;
		FOREACHBIT(input->mt.touches, slot) {
			t = &tp->tpad_touches[slot];
			if (t->flags & B_EDGE) {
				mask &= (1 << slot);
				input->mt.ptr_mask = mask;
			}
		}
	}

	if ((input->mt.ptr_mask & ~input->mt.ptr)
	    && !(tp->scroll.dz || tp->scroll.dw)
	    && tp->t->dir >= 0
	    && wstpad_is_stable(input, tp->t)) {

		slot = ffs(input->mt.ptr_mask) - 1;
		t = &tp->tpad_touches[slot];

		if (t->y >= tp->edge.low)
			return;

		if (!wstpad_is_stable(input, t))
			return;

		/* Default hysteresis limits are low.  Make a strict check. */
		pos = tp->t->pos;
		if (abs(pos->acc_dx) < 3 * input->filter.h.hysteresis
		    && abs(pos->acc_dy) < 3 * input->filter.v.hysteresis)
			return;

		if (t->dir >= 0) {
			/* Treat t as thumb if it is slow while tp->t is fast. */
			if (magnitude(input, t->pos->dx, t->pos->dy) > MAG_LOW
			    || magnitude(input, pos->dx, pos->dy) < MAG_MEDIUM)
				return;
		}

		tp->ignore = input->mt.ptr_mask;
	}
}

void
wstpad_touch_inputs(struct wsmouseinput *input)
{
	struct wstpad *tp = input->tp;
	struct tpad_touch *t;
	int slot, x, y, dx, dy;

	tp->btns = input->btn.buttons;
	tp->btns_sync = input->btn.sync;

	tp->prev_contacts = tp->contacts;
	tp->contacts = input->touch.contacts;

	if (tp->contacts == 1 &&
	    ((tp->params.f2width &&
	    input->touch.width >= tp->params.f2width)
	    || (tp->params.f2pressure &&
	    input->touch.pressure >= tp->params.f2pressure)))
		tp->contacts = 2;

	if (IS_MT(tp)) {
		wstpad_mt_inputs(input);
		if (input->mt.ptr) {
			slot = ffs(input->mt.ptr) - 1;
			tp->t = &tp->tpad_touches[slot];
		}
		wstpad_mt_masks(input);
	} else {
		t = tp->t;
		if (tp->contacts)
			t->state = (tp->prev_contacts ?
			    TOUCH_UPDATE : TOUCH_BEGIN);
		else
			t->state = (tp->prev_contacts ?
			    TOUCH_END : TOUCH_NONE);

		dx = dy = 0;
		x = normalize_abs(&input->filter.h, t->pos->x);
		y = normalize_abs(&input->filter.v, t->pos->y);
		if (t->state == TOUCH_BEGIN) {
			t->x = t->orig.x = x;
			t->y = t->orig.y = y;
			memcpy(&t->orig.time, &tp->time,
			    sizeof(struct timespec));
			t->flags = edge_flags(tp, x, y);
		} else if (input->motion.sync & SYNC_POSITION) {
			if (!wsmouse_hysteresis(input, t->pos)) {
				dx = x - t->x;
				dy = y - t->y;
			}
			t->x = x;
			t->y = y;
			t->flags &= (~EDGES | edge_flags(tp, x, y));
		}
		wstpad_set_direction(tp, t, dx, dy);
	}
}

static inline int
t2_ignore(struct wsmouseinput *input)
{
	/*
	 * If there are two touches, do not block pointer movement if they
	 * perform a click-and-drag action, or if the second touch is
	 * resting in the bottom area.
	 */
	return (input->tp->contacts == 2 && ((input->tp->btns & PRIMARYBTN)
	    || (input->tp->ignore & ~input->mt.ptr)));
}

void
wstpad_process_input(struct wsmouseinput *input, struct evq_access *evq)
{
	struct wstpad *tp = input->tp;
	u_int handlers, hdlr, cmds;

	memcpy(&tp->time, &evq->ts, sizeof(struct timespec));
	wstpad_touch_inputs(input);

	cmds = 0;
	handlers = tp->handlers;
	if (DISABLE(tp))
		handlers &= ((1 << TOPBUTTON_HDLR) | (1 << SOFTBUTTON_HDLR));

	FOREACHBIT(handlers, hdlr) {
		switch (hdlr) {
		case SOFTBUTTON_HDLR:
		case TOPBUTTON_HDLR:
			wstpad_softbuttons(input, &cmds, hdlr);
			continue;
		case TAP_HDLR:
			wstpad_tap(input, &cmds);
			continue;
		case F2SCROLL_HDLR:
			wstpad_f2scroll(input, &cmds);
			continue;
		case EDGESCROLL_HDLR:
			wstpad_edgescroll(input, &cmds);
			continue;
		case CLICK_HDLR:
			wstpad_click(input);
			continue;
		}
	}

	/* Check whether pointer movement should be blocked. */
	if (input->motion.dx || input->motion.dy) {
		if (DISABLE(tp)
		    || (tp->t->flags & tp->freeze)
		    || timespeccmp(&tp->time, &tp->freeze_ts, <)
		    || (tp->contacts > 1 && !t2_ignore(input))) {

			cmds |= 1 << CLEAR_MOTION_DELTAS;
		}
	}

	wstpad_cmds(input, cmds);

	if (IS_MT(tp))
		clear_touchstates(input, TOUCH_NONE);
}

/*
 * Try to determine the average interval between two updates. Various
 * conditions are checked in order to ensure that only valid samples enter
 * into the calculation. Above all, it is restricted to motion events
 * occurring when there is only one contact. MT devices may need more than
 * one packet to transmit their state if there are multiple touches, and
 * the update frequency may be higher in this case.
 */
void
wstpad_track_interval(struct wsmouseinput *input, struct timespec *time)
{
	static const struct timespec limit = { 0, 30 * 1000000L };
	struct timespec ts;
	int samples;

	if (input->motion.sync == 0
	    || (input->touch.sync & SYNC_CONTACTS)
	    || (input->touch.contacts > 1)) {
		input->intv.track = 0;
		return;
	}
	if (input->intv.track) {
		timespecsub(time, &input->intv.ts, &ts);
		if (timespeccmp(&ts, &limit, <)) {
			/* The unit of the sum is 4096 nanoseconds. */
			input->intv.sum += ts.tv_nsec >> 12;
			samples = ++input->intv.samples;
			/*
			 * Make the first calculation quickly and later
			 * a more reliable one:
			 */
			if (samples == 8) {
				input->intv.avg = input->intv.sum << 9;
				wstpad_init_deceleration(input);
			} else if (samples == 128) {
				input->intv.avg = input->intv.sum << 5;
				wstpad_init_deceleration(input);
				input->intv.samples = 0;
				input->intv.sum = 0;
				input->flags &= ~TRACK_INTERVAL;
			}
		}
	}
	memcpy(&input->intv.ts, time, sizeof(struct timespec));
	input->intv.track = 1;
}



/*
 * The default acceleration options of X don't work convincingly with
 * touchpads (the synaptics driver installs its own "acceleration
 * profile" and callback function). As a preliminary workaround, this
 * filter applies a simple deceleration scheme to small deltas, based
 * on the "magnitude" of the delta pair. A magnitude of 8 corresponds,
 * roughly, to a speed of (filter.dclr / 12.5) device units per milli-
 * second. If its magnitude is smaller than 7 a delta will be downscaled
 * by the factor 2/8, deltas with magnitudes from 7 to 11 by factors
 * ranging from 3/8 to 7/8.
 */
int
wstpad_decelerate(struct wsmouseinput *input, int *dx, int *dy)
{
	int mag, n, h, v;

	mag = magnitude(input, *dx, *dy);

	/* Don't change deceleration levels abruptly. */
	mag = (mag + 7 * input->filter.mag) / 8;
	/* Don't use arbitrarily high values. */
	input->filter.mag = imin(mag, 24 << 12);

	n = imax((mag >> 12) - 4, 2);
	if (n < 8) {
		/* Scale by (n / 8). */
		h = *dx * n + input->filter.h.dclr_rmdr;
		v = *dy * n + input->filter.v.dclr_rmdr;
		input->filter.h.dclr_rmdr = (h >= 0 ? h & 7 : -(-h & 7));
		input->filter.v.dclr_rmdr = (v >= 0 ? v & 7 : -(-v & 7));
		*dx = h / 8;
		*dy = v / 8;
		return (1);
	}
	return (0);
}

void
wstpad_filter(struct wsmouseinput *input)
{
	struct axis_filter *h = &input->filter.h;
	struct axis_filter *v = &input->filter.v;
	struct position *pos = &input->motion.pos;
	int strength = input->filter.mode & 7;
	int dx, dy;

	if (!(input->motion.sync & SYNC_POSITION)
	    || (h->dmax && (abs(pos->dx) > h->dmax))
	    || (v->dmax && (abs(pos->dy) > v->dmax))) {
		dx = dy = 0;
	} else {
		dx = pos->dx;
		dy = pos->dy;
	}

	if (wsmouse_hysteresis(input, pos))
		dx = dy = 0;

	if (input->filter.dclr && wstpad_decelerate(input, &dx, &dy))
		/* Strong smoothing may hamper the precision at low speeds. */
		strength = imin(strength, 2);

	if (strength) {
		if ((input->touch.sync & SYNC_CONTACTS)
		    || input->mt.ptr != input->mt.prev_ptr) {
			h->avg = v->avg = 0;
		}
		/* Use a weighted decaying average for smoothing. */
		dx = dx * (8 - strength) + h->avg * strength + h->avg_rmdr;
		dy = dy * (8 - strength) + v->avg * strength + v->avg_rmdr;
		h->avg_rmdr = (dx >= 0 ? dx & 7 : -(-dx & 7));
		v->avg_rmdr = (dy >= 0 ? dy & 7 : -(-dy & 7));
		dx = h->avg = dx / 8;
		dy = v->avg = dy / 8;
	}

	input->motion.dx = dx;
	input->motion.dy = dy;
}


/*
 * Compatibility-mode conversions. wstpad_filter transforms and filters
 * the coordinate inputs, extended functionality is provided by
 * wstpad_process_input.
 */
void
wstpad_compat_convert(struct wsmouseinput *input, struct evq_access *evq)
{
	if (input->flags & TRACK_INTERVAL)
		wstpad_track_interval(input, &evq->ts);

	wstpad_filter(input);

	if ((input->motion.dx || input->motion.dy)
	    && !(input->motion.sync & SYNC_DELTAS)) {
		input->motion.dz = input->motion.dw = 0;
		input->motion.sync |= SYNC_DELTAS;
	}

	if (input->tp != NULL)
		wstpad_process_input(input, evq);

	input->motion.sync &= ~SYNC_POSITION;
	input->touch.sync = 0;
}

int
wstpad_init(struct wsmouseinput *input)
{
	struct wstpad *tp = input->tp;
	int i, slots;

	if (tp != NULL)
		return (0);

	input->tp = tp = malloc(sizeof(struct wstpad),
	    M_DEVBUF, M_WAITOK | M_ZERO);
	if (tp == NULL)
		return (-1);

	slots = imax(input->mt.num_slots, 1);
	tp->tpad_touches = malloc(slots * sizeof(struct tpad_touch),
	    M_DEVBUF, M_WAITOK | M_ZERO);
	if (tp->tpad_touches == NULL) {
		free(tp, M_DEVBUF, sizeof(struct wstpad));
		return (-1);
	}

	tp->t = &tp->tpad_touches[0];
	if (input->mt.num_slots) {
		tp->features |= WSTPAD_MT;
		for (i = 0; i < input->mt.num_slots; i++)
			tp->tpad_touches[i].pos = &input->mt.slots[i].pos;
	} else {
		tp->t->pos = &input->motion.pos;
	}

	timeout_set(&tp->tap.to, wstpad_tap_timeout, input);

	tp->ratio = input->filter.ratio;

	return (0);
}

/*
 * Integer square root (Halleck's method)
 *
 * An adaption of code from John B. Halleck (from
 * http://www.cc.utah.edu/~nahaj/factoring/code.html). This version is
 * used and published under the OpenBSD license terms with his permission.
 *
 * Cf. also Martin Guy's "Square root by abacus" method.
 */
static inline u_int
isqrt(u_int n)
{
	u_int root, sqbit;

	root = 0;
	sqbit = 1 << (sizeof(u_int) * 8 - 2);
	while (sqbit) {
		if (n >= (sqbit | root)) {
			n -= (sqbit | root);
			root = (root >> 1) | sqbit;
		} else {
			root >>= 1;
		}
		sqbit >>= 2;
	}
	return (root);
}

void
wstpad_init_deceleration(struct wsmouseinput *input)
{
	int n, dclr;

	if ((dclr = input->filter.dclr) == 0)
		return;

	dclr = imax(dclr, 4);

	/*
	 * For a standard update rate of about 80Hz, (dclr) units
	 * will be mapped to a magnitude of 8. If the average rate
	 * is significantly higher or lower, adjust the coefficient
	 * accordingly:
	 */
	if (input->intv.avg == 0) {
		n = 8;
	} else {
		n = 8 * 13000000 / input->intv.avg;
		n = imax(imin(n, 32), 4);
	}
	input->filter.h.mag_scale = (n << 12) / dclr;
	input->filter.v.mag_scale = (input->filter.ratio ?
	    n * input->filter.ratio : n << 12) / dclr;
	input->filter.h.dclr_rmdr = 0;
	input->filter.v.dclr_rmdr = 0;
	input->flags |= TRACK_INTERVAL;
}

int
wstpad_configure(struct wsmouseinput *input)
{
	struct wstpad *tp;
	int width, height, diag, offset, h_res, v_res, h_unit, v_unit, i;

	width = abs(input->hw.x_max - input->hw.x_min);
	height = abs(input->hw.y_max - input->hw.y_min);
	if (width == 0 || height == 0)
		return (-1);	/* We can't do anything. */

	if (input->tp == NULL && wstpad_init(input))
		return (-1);
	tp = input->tp;

	if (!(input->flags & CONFIGURED)) {
		/*
		 * The filter parameters are derived from the length of the
		 * diagonal in device units, with some magic constants which
		 * are partly adapted from libinput or synaptics code, or are
		 * based on tests and guess work.  The absolute resolution
		 * values might not be reliable, but if they are present the
	         * settings are adapted to the ratio.
		 */
		h_res = input->hw.h_res;
		v_res = input->hw.v_res;
		if (h_res == 0 || v_res == 0)
			h_res = v_res = 1;
		diag = isqrt(width * width + height * height);
		input->filter.h.scale = (imin(920, diag) << 12) / diag;
		input->filter.v.scale = input->filter.h.scale * h_res / v_res;
		h_unit = imax(diag / 280, 3);
		v_unit = imax((h_unit * v_res + h_res / 2) / h_res, 3);
		input->filter.h.hysteresis = h_unit;
		input->filter.v.hysteresis = v_unit;
		input->filter.mode = FILTER_MODE_DEFAULT;
		input->filter.dclr = h_unit - h_unit / 5;
		wstpad_init_deceleration(input);

		tp->features &= (WSTPAD_MT | WSTPAD_DISABLE);

		if (input->hw.contacts_max != 1)
			tp->features |= WSTPAD_TWOFINGERSCROLL;
		else
			tp->features |= WSTPAD_EDGESCROLL;

		if (input->hw.hw_type == WSMOUSEHW_CLICKPAD) {
			if (input->hw.type == WSMOUSE_TYPE_SYNAP_SBTN) {
				tp->features |= WSTPAD_TOPBUTTONS;
			} else {
				tp->features |= WSTPAD_SOFTBUTTONS;
				tp->features |= WSTPAD_SOFTMBTN;
			}
		}

		tp->params.left_edge = V_EDGE_RATIO_DEFAULT;
		tp->params.right_edge = V_EDGE_RATIO_DEFAULT;
		tp->params.bottom_edge = ((tp->features & WSTPAD_SOFTBUTTONS)
		    ? B_EDGE_RATIO_DEFAULT : 0);
		tp->params.top_edge = ((tp->features & WSTPAD_TOPBUTTONS)
		    ? T_EDGE_RATIO_DEFAULT : 0);
		tp->params.center_width = CENTER_RATIO_DEFAULT;

		tp->tap.maxtime.tv_nsec = TAP_MAXTIME_DEFAULT * 1000000;
		tp->tap.clicktime = TAP_CLICKTIME_DEFAULT;
		tp->tap.locktime = TAP_LOCKTIME_DEFAULT;

		tp->scroll.hdist = 4 * h_unit;
		tp->scroll.vdist = 4 * v_unit;
		tp->tap.maxdist = 4 * h_unit;

		if (IS_MT(tp) && h_res > 1 && v_res > 1 &&
		    input->hw.hw_type == WSMOUSEHW_CLICKPAD &&
		    (width + h_res / 2) / h_res > 100 &&
		    (height + v_res / 2) / v_res > 60) {
			tp->params.mtbtn_maxdist = h_res * 35;
		} else {
			tp->params.mtbtn_maxdist = -1; /* not available */
		}
	}

	/* A touch with a flag set in this mask does not move the pointer. */
	tp->freeze = EDGES;

	offset = width * tp->params.left_edge / 4096;
	tp->edge.left = (offset ? input->hw.x_min + offset : INT_MIN);
	offset = width * tp->params.right_edge / 4096;
	tp->edge.right = (offset ? input->hw.x_max - offset : INT_MAX);
	offset = height * tp->params.bottom_edge / 4096;
	tp->edge.bottom = (offset ? input->hw.y_min + offset : INT_MIN);
	tp->edge.low = tp->edge.bottom + offset / 2;
	offset = height * tp->params.top_edge / 4096;
	tp->edge.top = (offset ? input->hw.y_max - offset : INT_MAX);

	offset = width * abs(tp->params.center_width) / 8192;
	tp->edge.center = input->hw.x_min + width / 2;
	tp->edge.center_left = tp->edge.center - offset;
	tp->edge.center_right = tp->edge.center + offset;

	/*
	 * Make the MTBUTTONS configuration consistent.  A non-negative 'maxdist'
	 * value makes the feature visible in wsconsctl.  0-values are replaced
	 * by a default (one fourth of the length of the touchpad diagonal).
	 */
	if (tp->params.mtbtn_maxdist < 0) {
		tp->features &= ~WSTPAD_MTBUTTONS;
	} else if (tp->params.mtbtn_maxdist == 0) {
		diag = isqrt(width * width + height * height);
		tp->params.mtbtn_maxdist = diag / 4;
	}

	tp->handlers = 0;

	if (tp->features & (WSTPAD_SOFTBUTTONS | WSTPAD_MTBUTTONS))
		tp->handlers |= 1 << SOFTBUTTON_HDLR;
	if (tp->features & WSTPAD_TOPBUTTONS)
		tp->handlers |= 1 << TOPBUTTON_HDLR;
	if (tp->features & WSTPAD_TWOFINGERSCROLL)
		tp->handlers |= 1 << F2SCROLL_HDLR;
	else if (tp->features & WSTPAD_EDGESCROLL)
		tp->handlers |= 1 << EDGESCROLL_HDLR;

	for (i = 0; i < TAP_BTNMAP_SIZE; i++) {
		if (tp->tap.btnmap[i] == 0)
			continue;

		tp->tap.clicktime = imin(imax(tp->tap.clicktime, 80), 350);
		if (tp->tap.locktime)
			tp->tap.locktime =
			    imin(imax(tp->tap.locktime, 150), 5000);
		tp->handlers |= 1 << TAP_HDLR;
		break;
	}

	if (input->hw.hw_type == WSMOUSEHW_CLICKPAD)
		tp->handlers |= 1 << CLICK_HDLR;

	tp->sbtnswap = ((tp->features & WSTPAD_SWAPSIDES)
	    ? (LEFTBTN | RIGHTBTN) : 0);

	return (0);
}

void
wstpad_reset(struct wsmouseinput *input)
{
	struct wstpad *tp = input->tp;

	if (tp != NULL) {
		timeout_del(&tp->tap.to);
		tp->tap.state = TAP_DETECT;
	}

	if (input->sbtn.buttons) {
		input->sbtn.sync = input->sbtn.buttons;
		input->sbtn.buttons = 0;
	}
}

void
wstpad_cleanup(struct wsmouseinput *input)
{
	struct wstpad *tp = input->tp;
	int slots;

	timeout_del(&tp->tap.to);
	slots = imax(input->mt.num_slots, 1);
	free(tp->tpad_touches, M_DEVBUF, slots * sizeof(struct tpad_touch));
	free(tp, M_DEVBUF, sizeof(struct wstpad));
	input->tp = NULL;
}

int
wstpad_set_param(struct wsmouseinput *input, int key, int val)
{
	struct wstpad *tp = input->tp;
	u_int flag;

	if (tp == NULL)
		return (EINVAL);

	switch (key) {
	case WSMOUSECFG_SOFTBUTTONS ... WSMOUSECFG_MTBUTTONS:
		switch (key) {
		case WSMOUSECFG_SOFTBUTTONS:
			flag = WSTPAD_SOFTBUTTONS;
			break;
		case WSMOUSECFG_SOFTMBTN:
			flag = WSTPAD_SOFTMBTN;
			break;
		case WSMOUSECFG_TOPBUTTONS:
			flag = WSTPAD_TOPBUTTONS;
			break;
		case WSMOUSECFG_TWOFINGERSCROLL:
			flag = WSTPAD_TWOFINGERSCROLL;
			break;
		case WSMOUSECFG_EDGESCROLL:
			flag = WSTPAD_EDGESCROLL;
			break;
		case WSMOUSECFG_HORIZSCROLL:
			flag = WSTPAD_HORIZSCROLL;
			break;
		case WSMOUSECFG_SWAPSIDES:
			flag = WSTPAD_SWAPSIDES;
			break;
		case WSMOUSECFG_DISABLE:
			flag = WSTPAD_DISABLE;
			break;
		case WSMOUSECFG_MTBUTTONS:
			flag = WSTPAD_MTBUTTONS;
			break;
		}
		if (val)
			tp->features |= flag;
		else
			tp->features &= ~flag;
		break;
	case WSMOUSECFG_LEFT_EDGE:
		tp->params.left_edge = val;
		break;
	case WSMOUSECFG_RIGHT_EDGE:
		tp->params.right_edge = val;
		break;
	case WSMOUSECFG_TOP_EDGE:
		tp->params.top_edge = val;
		break;
	case WSMOUSECFG_BOTTOM_EDGE:
		tp->params.bottom_edge = val;
		break;
	case WSMOUSECFG_CENTERWIDTH:
		tp->params.center_width = val;
		break;
	case WSMOUSECFG_HORIZSCROLLDIST:
		tp->scroll.hdist = val;
		break;
	case WSMOUSECFG_VERTSCROLLDIST:
		tp->scroll.vdist = val;
		break;
	case WSMOUSECFG_F2WIDTH:
		tp->params.f2width = val;
		break;
	case WSMOUSECFG_F2PRESSURE:
		tp->params.f2pressure = val;
		break;
	case WSMOUSECFG_TAP_MAXTIME:
		tp->tap.maxtime.tv_nsec = imin(val, 999) * 1000000;
		break;
	case WSMOUSECFG_TAP_CLICKTIME:
		tp->tap.clicktime = val;
		break;
	case WSMOUSECFG_TAP_LOCKTIME:
		tp->tap.locktime = val;
		break;
	case WSMOUSECFG_TAP_ONE_BTNMAP:
		tp->tap.btnmap[0] = BTNMASK(val);
		break;
	case WSMOUSECFG_TAP_TWO_BTNMAP:
		tp->tap.btnmap[1] = BTNMASK(val);
		break;
	case WSMOUSECFG_TAP_THREE_BTNMAP:
		tp->tap.btnmap[2] = BTNMASK(val);
		break;
	case WSMOUSECFG_MTBTN_MAXDIST:
		if (IS_MT(tp))
			tp->params.mtbtn_maxdist = val;
		break;
	default:
		return (ENOTSUP);
	}

	return (0);
}

int
wstpad_get_param(struct wsmouseinput *input, int key, int *pval)
{
	struct wstpad *tp = input->tp;
	u_int flag;

	if (tp == NULL)
		return (EINVAL);

	switch (key) {
	case WSMOUSECFG_SOFTBUTTONS ... WSMOUSECFG_MTBUTTONS:
		switch (key) {
		case WSMOUSECFG_SOFTBUTTONS:
			flag = WSTPAD_SOFTBUTTONS;
			break;
		case WSMOUSECFG_SOFTMBTN:
			flag = WSTPAD_SOFTMBTN;
			break;
		case WSMOUSECFG_TOPBUTTONS:
			flag = WSTPAD_TOPBUTTONS;
			break;
		case WSMOUSECFG_TWOFINGERSCROLL:
			flag = WSTPAD_TWOFINGERSCROLL;
			break;
		case WSMOUSECFG_EDGESCROLL:
			flag = WSTPAD_EDGESCROLL;
			break;
		case WSMOUSECFG_HORIZSCROLL:
			flag = WSTPAD_HORIZSCROLL;
			break;
		case WSMOUSECFG_SWAPSIDES:
			flag = WSTPAD_SWAPSIDES;
			break;
		case WSMOUSECFG_DISABLE:
			flag = WSTPAD_DISABLE;
			break;
		case WSMOUSECFG_MTBUTTONS:
			flag = WSTPAD_MTBUTTONS;
			break;
		}
		*pval = !!(tp->features & flag);
		break;
	case WSMOUSECFG_LEFT_EDGE:
		*pval = tp->params.left_edge;
		break;
	case WSMOUSECFG_RIGHT_EDGE:
		*pval = tp->params.right_edge;
		break;
	case WSMOUSECFG_TOP_EDGE:
		*pval = tp->params.top_edge;
		break;
	case WSMOUSECFG_BOTTOM_EDGE:
		*pval = tp->params.bottom_edge;
		break;
	case WSMOUSECFG_CENTERWIDTH:
		*pval = tp->params.center_width;
		break;
	case WSMOUSECFG_HORIZSCROLLDIST:
		*pval = tp->scroll.hdist;
		break;
	case WSMOUSECFG_VERTSCROLLDIST:
		*pval = tp->scroll.vdist;
		break;
	case WSMOUSECFG_F2WIDTH:
		*pval = tp->params.f2width;
		break;
	case WSMOUSECFG_F2PRESSURE:
		*pval = tp->params.f2pressure;
		break;
	case WSMOUSECFG_TAP_MAXTIME:
		*pval = tp->tap.maxtime.tv_nsec / 1000000;
		break;
	case WSMOUSECFG_TAP_CLICKTIME:
		*pval = tp->tap.clicktime;
		break;
	case WSMOUSECFG_TAP_LOCKTIME:
		*pval = tp->tap.locktime;
		break;
	case WSMOUSECFG_TAP_ONE_BTNMAP:
		*pval = ffs(tp->tap.btnmap[0]);
		break;
	case WSMOUSECFG_TAP_TWO_BTNMAP:
		*pval = ffs(tp->tap.btnmap[1]);
		break;
	case WSMOUSECFG_TAP_THREE_BTNMAP:
		*pval = ffs(tp->tap.btnmap[2]);
		break;
	case WSMOUSECFG_MTBTN_MAXDIST:
		*pval = tp->params.mtbtn_maxdist;
		break;
	default:
		return (ENOTSUP);
	}

	return (0);
}