target/linux/s3c24xx/files-2.6.31/drivers/input/touchscreen/ts_filter_group.c

   1 /*
   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.
   6  *
   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.
  11  *
  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
  15  *
  16  * Copyright (C) 2008,2009 by Openmoko, Inc.
  17  * Author: Nelson Castillo <arhuaco@freaks-unidos.net>
  18  * All rights reserved.
  19  *
  20  *
  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.
  23  *
  24  * 1) We collect S samples.
  25  *
  26  * 2) For each dimension:
  27  *
  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.
  34  *
  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.
  38  *
  39  */
  40
  41 #include <linux/kernel.h>
  42 #include <linux/slab.h>
  43 #include <linux/sort.h>
  44 #include <linux/touchscreen/ts_filter_group.h>
  45
  46 struct ts_filter_group {
  47         /* Private filter configuration. */
  48         struct ts_filter_group_configuration *config;
  49         /* Filter API. */
  50         struct ts_filter tsf;
  51
  52         int N;                  /* How many samples we have. */
  53         int *samples[MAX_TS_FILTER_COORDS];     /* The samples: our input. */
  54
  55         int *group_size;        /* Used for temporal computations. */
  56         int *sorted_samples;    /* Used for temporal computations. */
  57
  58         int range_max[MAX_TS_FILTER_COORDS];    /* Max. computed ranges. */
  59         int range_min[MAX_TS_FILTER_COORDS];    /* Min. computed ranges. */
  60
  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. */
  64 };
  65
  66 #define ts_filter_to_filter_group(f) \
  67         container_of(f, struct ts_filter_group, tsf)
  68
  69
  70 static void ts_filter_group_clear_internal(struct ts_filter_group *tsfg,
  71                                            int attempts)
  72 {
  73         tsfg->N = 0;
  74         tsfg->tries_left = attempts;
  75         tsfg->ready = 0;
  76         tsfg->result = 0;
  77 }
  78
  79 static void ts_filter_group_clear(struct ts_filter *tsf)
  80 {
  81         struct ts_filter_group *tsfg = ts_filter_to_filter_group(tsf);
  82
  83         ts_filter_group_clear_internal(tsfg, tsfg->config->attempts);
  84 }
  85
  86 static struct ts_filter *ts_filter_group_create(
  87         struct platform_device *pdev,
  88         const struct ts_filter_configuration *conf,
  89         int count_coords)
  90 {
  91         struct ts_filter_group *tsfg;
  92         int i;
  93
  94         tsfg = kzalloc(sizeof(struct ts_filter_group), GFP_KERNEL);
  95         if (!tsfg)
  96                 return NULL;
  97
  98         tsfg->config = container_of(conf,
  99                                     struct ts_filter_group_configuration,
 100                                     config);
 101         tsfg->tsf.count_coords = count_coords;
 102
 103         BUG_ON(tsfg->config->attempts <= 0);
 104
 105         tsfg->samples[0] = kmalloc((2 + count_coords) * sizeof(int) *
 106                                    tsfg->config->length, GFP_KERNEL);
 107         if (!tsfg->samples[0]) {
 108                 kfree(tsfg);
 109                 return NULL;
 110         }
 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;
 117
 118         ts_filter_group_clear_internal(tsfg, tsfg->config->attempts);
 119
 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);
 123
 124         return &tsfg->tsf;
 125 }
 126
 127 static void ts_filter_group_destroy(struct ts_filter *tsf)
 128 {
 129         struct ts_filter_group *tsfg = ts_filter_to_filter_group(tsf);
 130
 131         kfree(tsfg->samples[0]); /* first guy has pointer from kmalloc */
 132         kfree(tsf);
 133 }
 134
 135 static int int_cmp(const void *_a, const void *_b)
 136 {
 137         const int *a = _a;
 138         const int *b = _b;
 139
 140         if (*a > *b)
 141                 return 1;
 142         if (*a < *b)
 143                 return -1;
 144         return 0;
 145 }
 146
 147 static void ts_filter_group_prepare_next(struct ts_filter *tsf);
 148
 149 static int ts_filter_group_process(struct ts_filter *tsf, int *coords)
 150 {
 151         struct ts_filter_group *tsfg = ts_filter_to_filter_group(tsf);
 152         int n;
 153         int i;
 154
 155         BUG_ON(tsfg->N >= tsfg->config->length);
 156         BUG_ON(tsfg->ready);
 157
 158         for (n = 0; n < tsf->count_coords; n++)
 159                 tsfg->samples[n][tsfg->N] = coords[n];
 160
 161         if (++tsfg->N < tsfg->config->length)
 162                 return 0;       /* We need more samples. */
 163
 164         for (n = 0; n < tsfg->tsf.count_coords; n++) {
 165                 int *v = tsfg->sorted_samples;
 166                 int ngroups = 0;
 167                 int best_size;
 168                 int best_idx = 0;
 169                 int idx = 0;
 170
 171                 memcpy(v, tsfg->samples[n], tsfg->N * sizeof(int));
 172                 /*
 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
 178                  * dealing with.
 179                  */
 180                 sort(v, tsfg->N, sizeof(int), int_cmp, NULL);
 181
 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]++;
 186                         else
 187                                 tsfg->group_size[++ngroups] = 1;
 188                 }
 189                 ngroups++;
 190
 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];
 196                                 best_idx = idx;
 197                         }
 198                 }
 199
 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. */
 206                                 return 0;
 207                         }
 208                         return 1; /* We give up: error. */
 209                 }
 210
 211                 tsfg->range_min[n] = v[best_idx];
 212                 tsfg->range_max[n] = v[best_idx + best_size - 1];
 213         }
 214
 215         ts_filter_group_prepare_next(tsf);
 216
 217         return 0;
 218 }
 219
 220 /*
 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.
 224  */
 225 static void ts_filter_group_prepare_next(struct ts_filter *tsf)
 226 {
 227         struct ts_filter_group *priv = ts_filter_to_filter_group(tsf);
 228         int n;
 229
 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])
 235                                 break;
 236                 }
 237
 238                 if (n == priv->tsf.count_coords) /* Sample is OK. */
 239                         break;
 240
 241                 priv->result++;
 242         }
 243
 244         if (unlikely(priv->result >= priv->N)) { /* No sample to deliver. */
 245                 ts_filter_group_clear_internal(priv, priv->config->attempts);
 246                 priv->ready = 0;
 247         } else {
 248                 priv->ready = 1;
 249         }
 250 }
 251
 252 static int ts_filter_group_haspoint(struct ts_filter *tsf)
 253 {
 254         struct ts_filter_group *priv = ts_filter_to_filter_group(tsf);
 255
 256         return priv->ready;
 257 }
 258
 259 static void ts_filter_group_getpoint(struct ts_filter *tsf, int *point)
 260 {
 261         struct ts_filter_group *priv = ts_filter_to_filter_group(tsf);
 262         int n;
 263
 264         BUG_ON(!priv->ready);
 265
 266         for (n = 0; n < priv->tsf.count_coords; n++)
 267                 point[n] = priv->samples[n][priv->result];
 268
 269         priv->result++;
 270
 271         /* This call will update priv->ready. */
 272         ts_filter_group_prepare_next(tsf);
 273 }
 274
 275 /*
 276  * Get ready to process the next batch of points, forget
 277  * points we could have delivered.
 278  */
 279 static void ts_filter_group_scale(struct ts_filter *tsf, int *coords)
 280 {
 281         struct ts_filter_group *priv = ts_filter_to_filter_group(tsf);
 282
 283         ts_filter_group_clear_internal(priv, priv->config->attempts);
 284 }
 285
 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,
 294 };
 295 EXPORT_SYMBOL_GPL(ts_filter_group_api);
 296