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
);