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 by Openmoko, Inc.
  17  * Author: Nelson Castillo <arhuaco@freaks-unidos.net>
  18  * All rights reserved.
  19  *
  20  * This filter is useful to reject samples that are not reliable. We consider
  21  * that a sample is not reliable if it deviates form the Majority.
  22  *
  23  * 1) We collect S samples.
  24  *
  25  * 2) For each dimension:
  26  *
  27  *  - We sort the points.
  28  *  - Points that are "close enough" are considered to be in the same set.
  29  *  - We choose the set with more elements. If more than "threshold"
  30  *    points are in this set we use the first and the last point of the set
  31  *    to define the valid range for this dimension [min, max], otherwise we
  32  *    discard all the points and go to step 1.
  33  *
  34  * 3) We consider the unsorted S samples and try to feed them to the next
  35  *    filter in the chain. If one of the points of each sample
  36  *    is not in the allowed range for its dimension, we discard the sample.
  37  *
  38  */
  39
  40 #include <linux/kernel.h>
  41 #include <linux/slab.h>
  42 #include <linux/sort.h>
  43 #include "ts_filter_group.h"
  44
  45 static void ts_filter_group_clear_internal(struct ts_filter_group *tsfg,
  46                                            int attempts)
  47 {
  48         tsfg->N = 0;
  49         tsfg->tries_left = attempts;
  50 }
  51
  52 static void ts_filter_group_clear(struct ts_filter *tsf)
  53 {
  54         struct ts_filter_group *tsfg = (struct ts_filter_group *)tsf;
  55
  56         ts_filter_group_clear_internal(tsfg, tsfg->config->attempts);
  57
  58         if (tsf->next) /* chain */
  59                 (tsf->next->api->clear)(tsf->next);
  60 }
  61
  62 static struct ts_filter *ts_filter_group_create(struct platform_device *pdev,
  63                                                 void *conf, int count_coords)
  64 {
  65         struct ts_filter_group *tsfg;
  66         int i;
  67
  68         BUG_ON((count_coords < 1) || (count_coords > MAX_TS_FILTER_COORDS));
  69
  70         tsfg = kzalloc(sizeof(struct ts_filter_group), GFP_KERNEL);
  71         if (!tsfg)
  72                 return NULL;
  73
  74         tsfg->config = (struct ts_filter_group_configuration *)conf;
  75         tsfg->tsf.count_coords = count_coords;
  76
  77         BUG_ON(tsfg->config->attempts <= 0);
  78
  79         tsfg->samples[0] = kmalloc((2 + count_coords) * sizeof(int) *
  80                                    tsfg->config->extent, GFP_KERNEL);
  81         if (!tsfg->samples[0]) {
  82                 kfree(tsfg);
  83                 return NULL;
  84         }
  85         for (i = 1; i < count_coords; ++i)
  86                 tsfg->samples[i] = tsfg->samples[0] + i * tsfg->config->extent;
  87         tsfg->sorted_samples = tsfg->samples[0] + count_coords *
  88                                tsfg->config->extent;
  89         tsfg->group_size = tsfg->samples[0] + (1 + count_coords) *
  90                                tsfg->config->extent;
  91
  92         ts_filter_group_clear_internal(tsfg, tsfg->config->attempts);
  93
  94         printk(KERN_INFO"  Created group ts filter len %d depth %d close %d "
  95                         "thresh %d\n", tsfg->config->extent, count_coords,
  96                         tsfg->config->close_enough, tsfg->config->threshold);
  97
  98         return &tsfg->tsf;
  99 }
 100
 101 static void ts_filter_group_destroy(struct platform_device *pdev,
 102                                     struct ts_filter *tsf)
 103 {
 104         struct ts_filter_group *tsfg = (struct ts_filter_group *)tsf;
 105
 106         kfree(tsfg->samples[0]); /* first guy has pointer from kmalloc */
 107         kfree(tsf);
 108 }
 109
 110 static void ts_filter_group_scale(struct ts_filter *tsf, int *coords)
 111 {
 112         if (tsf->next)
 113                 (tsf->next->api->scale)(tsf->next, coords);
 114 }
 115
 116 static int int_cmp(const void *_a, const void *_b)
 117 {
 118         const int *a = _a;
 119         const int *b = _b;
 120
 121         if (*a > *b)
 122                 return 1;
 123         if (*a < *b)
 124                 return -1;
 125         return 0;
 126 }
 127
 128 static int ts_filter_group_process(struct ts_filter *tsf, int *coords)
 129 {
 130         struct ts_filter_group *tsfg = (struct ts_filter_group *)tsf;
 131         int n;
 132         int i;
 133         int ret = 0; /* ask for more samples by default */
 134
 135         BUG_ON(tsfg->N >= tsfg->config->extent);
 136
 137         for (n = 0; n < tsf->count_coords; n++)
 138                 tsfg->samples[n][tsfg->N] = coords[n];
 139
 140         if (++tsfg->N < tsfg->config->extent)
 141                 return 0;       /* we meed more samples */
 142
 143         for (n = 0; n < tsfg->tsf.count_coords; n++) {
 144                 int *v = tsfg->sorted_samples;
 145                 int ngroups = 0;
 146                 int best_size;
 147                 int best_idx = 0;
 148                 int idx = 0;
 149
 150                 memcpy(v, tsfg->samples[n], tsfg->N * sizeof(int));
 151                 sort(v, tsfg->N, sizeof(int), int_cmp, NULL);
 152
 153                 tsfg->group_size[0] = 1;
 154                 for (i = 1; i < tsfg->N; ++i) {
 155                         if (v[i] - v[i - 1] <= tsfg->config->close_enough)
 156                                 tsfg->group_size[ngroups]++;
 157                         else
 158                                 tsfg->group_size[++ngroups] = 1;
 159                 }
 160                 ngroups++;
 161
 162                 best_size = tsfg->group_size[0];
 163                 for (i = 1; i < ngroups; i++) {
 164                         idx += tsfg->group_size[i - 1];
 165                         if (best_size < tsfg->group_size[i]) {
 166                                 best_size = tsfg->group_size[i];
 167                                 best_idx = idx;
 168                         }
 169                 }
 170
 171                 if (best_size < tsfg->config->threshold) {
 172                         /* this set is not good enough for us */
 173                         if (--tsfg->tries_left) {
 174                                 ts_filter_group_clear_internal
 175                                         (tsfg, tsfg->tries_left);
 176                                 return 0; /* ask for more samples */
 177                         }
 178                         return -1; /* we give up */
 179                 }
 180
 181                 tsfg->range_min[n] = v[best_idx];
 182                 tsfg->range_max[n] = v[best_idx + best_size - 1];
 183         }
 184
 185         for (i = 0; i < tsfg->N; ++i) {
 186                 int r;
 187
 188                 for (n = 0; n < tsfg->tsf.count_coords; ++n) {
 189                         coords[n] = tsfg->samples[n][i];
 190                         if (coords[n] < tsfg->range_min[n] ||
 191                             coords[n] > tsfg->range_max[n])
 192                                 break;
 193                 }
 194
 195                 if (n != tsfg->tsf.count_coords) /* sample not OK */
 196                         continue;
 197
 198                 if (tsf->next) {
 199                         r = (tsf->next->api->process)(tsf->next, coords);
 200                         if (r)  {
 201                                 ret = r;
 202                                 break;
 203                         }
 204                 } else if (i == tsfg->N - 1) {
 205                         ret = 1;
 206                 }
 207         }
 208
 209         ts_filter_group_clear_internal(tsfg, tsfg->config->attempts);
 210
 211         return ret;
 212 }
 213
 214 struct ts_filter_api ts_filter_group_api = {
 215         .create = ts_filter_group_create,
 216         .destroy = ts_filter_group_destroy,
 217         .clear = ts_filter_group_clear,
 218         .process = ts_filter_group_process,
 219         .scale = ts_filter_group_scale,
 220 };
 221