third_party_mtdev/test/mtdev-kernel.c

/*****************************************************************************
 *
 * mtdev - Multitouch Protocol Translation Library (MIT license)
 *
 * Copyright (C) 2010 Henrik Rydberg <rydberg@euromail.se>
 * Copyright (C) 2010 Canonical Ltd.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a
 * copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice (including the next
 * paragraph) shall be included in all copies or substantial portions of the
 * Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
 * DEALINGS IN THE SOFTWARE.
 *
 ****************************************************************************/

#include <../src/common.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*
 * Combinatorial formulation
 *
 * x_ij = 1 if slot i and contact j are connected, zero otherwise
 *
 * sum_i x_ij <= 1 for all j; each contact picks at most one slot
 *
 * sum_j x_ij <= 1 for all i; each slot is picked by at most one contact
 *
 * sum_ij x_ij == min(nslot, npos); assign every contact possible
 *
 * Arrange x_ij as a bitmask; x_00 x_01 x_02.. x_10 x_11 x_12...
 *
 * Up to five slots, this is readily enumerable.
 */

#define SLOT_MAX	5
#define SLOT_CNT	(SLOT_MAX + 1)

static int illegal(int nslot, int npos, unsigned x)
{
	int i, j, sum;

	for (j = 0; j < npos; j++) {
		sum = 0;
		for (i = 0; i < nslot; i++)
			sum += GETBIT(x, i * npos + j);
		if (sum > 1)
			return 1;
	}
	for (i = 0; i < nslot; i++) {
		sum = 0;
		for (j = 0; j < npos; j++)
			sum += GETBIT(x, i * npos + j);
		if (sum > 1)
			return 1;
	}

	sum = bitcount(x);
	return sum != minval(nslot, npos);
}

static void get_slots(int *slots, int nslot, int npos, unsigned x)
{
	int i;

	memset(slots, -1, sizeof(slots[0]) * npos);
	for (i = 0; i < nslot * npos; i++)
		if (GETBIT(x, i))
			slots[i % npos] = i / npos;
	for (i = 0; i < npos; i++)
		if (slots[i] < 0)
			slots[i] = nslot++;
}

static int generate_assignments(int nslot, int npos)
{
	static int ncol;
	unsigned x, nx = BITMASK(nslot * npos);
	int slots[SLOT_MAX];
	int i, n = 0;

	for (x = 0; x < nx; x++) {
		if (illegal(nslot, npos, x))
			continue;
		for (i = 0; i < nslot * npos; i++) {
			if (GETBIT(x, i)) {
				if (ncol++ % 16 == 0)
					printf("\n\t%d,", i);
				else
					printf(" %d,", i);
				n++;
			}
		}
		get_slots(slots, nslot, npos, x);
		for (i = 0; i < npos; i++) {
			if (ncol++ % 16 == 0)
				printf("\n\t%d,", slots[i]);
			else
				printf(" %d,", slots[i]);
			n++;
		}
	}

	return n;
}

int main(int argc, char *argv[])
{
	int ix[SLOT_CNT][SLOT_CNT], nix = 0;
	int eslot, i, j;

	if (argc < 2) {
		fprintf(stderr, "usage: %s <num_slots>\n", argv[0]);
		return 1;
	}

	eslot = atoi(argv[1]) + 1;
	if (eslot > SLOT_CNT) {
		fprintf(stderr, "allowed slot range: 2 - %d\n", SLOT_MAX);
		return 1;
	}

	printf("\n/* generated by mtdev-kernel - do not edit */\n");
	printf("static const u8 match_data[] = {");
	for (i = 0; i < eslot; i++) {
		for (j = 0; j < eslot; j++) {
			ix[i][j] = nix;
			nix += generate_assignments(i, j);
		}
	}
	printf("\n};\n");

	printf("\n/* generated by mtdev-kernel - do not edit */\n");
	printf("static const int match_index[][%d] = {\n", eslot);
	for (i = 0; i < eslot; i++) {
		printf("\t{");
		for (j = 0; j < eslot; j++)
			printf(" %d%s", ix[i][j], j < eslot - 1 ? "," : "");
		printf(" },\n");
	}
	printf("\t{ %d }\n", nix);
	printf("};\n");

	return 0;
}