2 * This program is free software; you can redistribute it and/or modify
3 * it under the terms of the GNU General Public License as published by
4 * the Free Software Foundation; either version 2 of the License, or
5 * (at your option) any later version.
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software
14 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
16 * Copyright (C) 2008,2009 by Openmoko, Inc.
17 * Author: Nelson Castillo <arhuaco@freaks-unidos.net>
18 * All rights reserved.
21 * This filter is useful to reject samples that are not reliable. We consider
22 * that a sample is not reliable if it deviates form the Majority.
24 * 1) We collect S samples.
26 * 2) For each dimension:
28 * - We sort the points.
29 * - Points that are "close enough" are considered to be in the same set.
30 * - We choose the set with more elements. If more than "threshold"
31 * points are in this set we use the first and the last point of the set
32 * to define the valid range for this dimension [min, max], otherwise we
33 * discard all the points and go to step 1.
35 * 3) We consider the unsorted S samples and try to feed them to the next
36 * filter in the chain. If one of the points of each sample
37 * is not in the allowed range for its dimension, we discard the sample.
41 #include <linux/kernel.h>
42 #include <linux/slab.h>
43 #include <linux/sort.h>
44 #include <linux/touchscreen/ts_filter_group.h>
46 struct ts_filter_group {
47 /* Private filter configuration. */
48 struct ts_filter_group_configuration *config;
52 int N; /* How many samples we have. */
53 int *samples[MAX_TS_FILTER_COORDS]; /* The samples: our input. */
55 int *group_size; /* Used for temporal computations. */
56 int *sorted_samples; /* Used for temporal computations. */
58 int range_max[MAX_TS_FILTER_COORDS]; /* Max. computed ranges. */
59 int range_min[MAX_TS_FILTER_COORDS]; /* Min. computed ranges. */
61 int tries_left; /* We finish if we don't get enough samples. */
62 int ready; /* If we are ready to deliver samples. */
63 int result; /* Index of the point being returned. */
66 #define ts_filter_to_filter_group(f) \
67 container_of(f, struct ts_filter_group, tsf)
70 static void ts_filter_group_clear_internal(struct ts_filter_group *tsfg,
74 tsfg->tries_left = attempts;
79 static void ts_filter_group_clear(struct ts_filter *tsf)
81 struct ts_filter_group *tsfg = ts_filter_to_filter_group(tsf);
83 ts_filter_group_clear_internal(tsfg, tsfg->config->attempts);
86 static struct ts_filter *ts_filter_group_create(
87 struct platform_device *pdev,
88 const struct ts_filter_configuration *conf,
91 struct ts_filter_group *tsfg;
94 tsfg = kzalloc(sizeof(struct ts_filter_group), GFP_KERNEL);
98 tsfg->config = container_of(conf,
99 struct ts_filter_group_configuration,
101 tsfg->tsf.count_coords = count_coords;
103 BUG_ON(tsfg->config->attempts <= 0);
105 tsfg->samples[0] = kmalloc((2 + count_coords) * sizeof(int) *
106 tsfg->config->length, GFP_KERNEL);
107 if (!tsfg->samples[0]) {
111 for (i = 1; i < count_coords; ++i)
112 tsfg->samples[i] = tsfg->samples[0] + i * tsfg->config->length;
113 tsfg->sorted_samples = tsfg->samples[0] + count_coords *
114 tsfg->config->length;
115 tsfg->group_size = tsfg->samples[0] + (1 + count_coords) *
116 tsfg->config->length;
118 ts_filter_group_clear_internal(tsfg, tsfg->config->attempts);
120 dev_info(&pdev->dev, "Created Group filter len:%d coords:%d close:%d "
121 "thresh:%d\n", tsfg->config->length, count_coords,
122 tsfg->config->close_enough, tsfg->config->threshold);
127 static void ts_filter_group_destroy(struct ts_filter *tsf)
129 struct ts_filter_group *tsfg = ts_filter_to_filter_group(tsf);
131 kfree(tsfg->samples[0]); /* first guy has pointer from kmalloc */
135 static int int_cmp(const void *_a, const void *_b)
147 static void ts_filter_group_prepare_next(struct ts_filter *tsf);
149 static int ts_filter_group_process(struct ts_filter *tsf, int *coords)
151 struct ts_filter_group *tsfg = ts_filter_to_filter_group(tsf);
155 BUG_ON(tsfg->N >= tsfg->config->length);
158 for (n = 0; n < tsf->count_coords; n++)
159 tsfg->samples[n][tsfg->N] = coords[n];
161 if (++tsfg->N < tsfg->config->length)
162 return 0; /* We need more samples. */
164 for (n = 0; n < tsfg->tsf.count_coords; n++) {
165 int *v = tsfg->sorted_samples;
171 memcpy(v, tsfg->samples[n], tsfg->N * sizeof(int));
173 * FIXME: Remove this sort call. We already have the
174 * algorithm for this modification. The filter will
175 * need less points (about half) if there is not a
176 * lot of noise. Right now we are doing a constant
177 * amount of work no matter how much noise we are
180 sort(v, tsfg->N, sizeof(int), int_cmp, NULL);
182 tsfg->group_size[0] = 1;
183 for (i = 1; i < tsfg->N; ++i) {
184 if (v[i] - v[i - 1] <= tsfg->config->close_enough)
185 tsfg->group_size[ngroups]++;
187 tsfg->group_size[++ngroups] = 1;
191 best_size = tsfg->group_size[0];
192 for (i = 1; i < ngroups; i++) {
193 idx += tsfg->group_size[i - 1];
194 if (best_size < tsfg->group_size[i]) {
195 best_size = tsfg->group_size[i];
200 if (best_size < tsfg->config->threshold) {
201 /* This set is not good enough for us. */
202 if (--tsfg->tries_left) {
203 ts_filter_group_clear_internal
204 (tsfg, tsfg->tries_left);
205 /* No errors but we need more samples. */
208 return 1; /* We give up: error. */
211 tsfg->range_min[n] = v[best_idx];
212 tsfg->range_max[n] = v[best_idx + best_size - 1];
215 ts_filter_group_prepare_next(tsf);
221 * This private function prepares a point that will be returned
222 * in ts_filter_group_getpoint if it is available. It updates
223 * the priv->ready state also.
225 static void ts_filter_group_prepare_next(struct ts_filter *tsf)
227 struct ts_filter_group *priv = ts_filter_to_filter_group(tsf);
230 while (priv->result < priv->N) {
231 for (n = 0; n < priv->tsf.count_coords; ++n) {
232 if (priv->samples[n][priv->result] <
233 priv->range_min[n] ||
234 priv->samples[n][priv->result] > priv->range_max[n])
238 if (n == priv->tsf.count_coords) /* Sample is OK. */
244 if (unlikely(priv->result >= priv->N)) { /* No sample to deliver. */
245 ts_filter_group_clear_internal(priv, priv->config->attempts);
252 static int ts_filter_group_haspoint(struct ts_filter *tsf)
254 struct ts_filter_group *priv = ts_filter_to_filter_group(tsf);
259 static void ts_filter_group_getpoint(struct ts_filter *tsf, int *point)
261 struct ts_filter_group *priv = ts_filter_to_filter_group(tsf);
264 BUG_ON(!priv->ready);
266 for (n = 0; n < priv->tsf.count_coords; n++)
267 point[n] = priv->samples[n][priv->result];
271 /* This call will update priv->ready. */
272 ts_filter_group_prepare_next(tsf);
276 * Get ready to process the next batch of points, forget
277 * points we could have delivered.
279 static void ts_filter_group_scale(struct ts_filter *tsf, int *coords)
281 struct ts_filter_group *priv = ts_filter_to_filter_group(tsf);
283 ts_filter_group_clear_internal(priv, priv->config->attempts);
286 const struct ts_filter_api ts_filter_group_api = {
287 .create = ts_filter_group_create,
288 .destroy = ts_filter_group_destroy,
289 .clear = ts_filter_group_clear,
290 .process = ts_filter_group_process,
291 .haspoint = ts_filter_group_haspoint,
292 .getpoint = ts_filter_group_getpoint,
293 .scale = ts_filter_group_scale,
295 EXPORT_SYMBOL_GPL(ts_filter_group_api);