Re: specification of cluts tests - code or/and data?

[Solar Designer <solar@openwall.com>]

[-- Attachment #1: Type: text/plain, Size: 1856 bytes --]

Luka, Rich -

On Mon, Jun 13, 2011 at 06:22:31AM +0400, Solar Designer wrote:
> Rather than write a piece of code for testing every property of every
> function, we could consider implementing interpreters or wrapper
> functions for common tests, or tables (arrays of structs) listing similar
> tests.  A problem here is that call to a string function via a function
> pointer might not invoke the same implementation that direct use would
> (there could be a macro or a C compiler builtin).  On the other hand,
> this also means that whatever approach to program structure we choose,
> we could want to test both kinds of uses of string functions (direct and
> via function pointer), to test both implementations (which might be
> present).

I wrote some code to illustrate this.  As written, it tests only some
trivial properties of a handful of string functions, but it is
extensible.  Please see attached.

Functions to test are specified like this:

static void *i_memcpy(void *dst, const void *src, size_t n)
{ return memcpy(dst, src, n); /* might use inlined code */ }

static fspec funcs[] = {
	{memcpy, {F_PTR | F_DST, F_DST, F_SRC, F_N}},
	{i_memcpy, {F_PTR | F_DST, F_DST, F_SRC, F_N}},
	{strcpy, {F_PTR | F_DST | F_NUL, F_DST, F_SRC}},
	{strncpy, {F_PTR | F_DST | F_PAD, F_DST, F_SRC, F_N}},
	{strcat, {F_PTR | F_DST | F_NUL, F_DST | F_SRC, F_SRC}},
	{strncat, {F_PTR | F_DST | F_NUL, F_DST | F_SRC, F_SRC, F_N}},
	{strchr, {F_PTR | F_IN_A1 | F_NUL, F_SRC, F_C}},
	{strstr, {F_PTR | F_IN_A1 | F_NUL, F_SRC, F_SRC}},
	{NULL}
};

As written, arg_next() tries to test all values in a range, but it will
need to be adjusted to skip ranges of string lengths for long strings.

As you can see, deeply nested loops seen in Luka's code are avoided
here.  Even with 8-char tabs (my preference), everything comfortably
fits in under 80 chars.

Alexander

[-- Attachment #2: str.c --]
[-- Type: text/plain, Size: 3749 bytes --]

/*
 * Copyright (c) 2011 Solar Designer <solar at openwall.com>
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted.
 *
 * There's ABSOLUTELY NO WARRANTY, express or implied.
 */

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define STR_SIZE			100
#define MIN_C				'a'
#define MAX_C				'z'

#define F_DST				0x00000001
#define F_SRC				0x00000002
#define F_PTR				0x00000004
#define F_IS_PTR			(F_DST | F_SRC | F_PTR)
#define F_N				0x00000008
#define F_C				0x00000010
#define F_NUL				0x00000100
#define F_PAD				0x00000200
#define F_IN_A1				0x00000400

typedef struct {
	void *f;
	unsigned int a[4]; /* a0 = f(a1, a2, a3) */
} fspec;

static void *i_memcpy(void *dst, const void *src, size_t n)
{ return memcpy(dst, src, n); /* might use inlined code */ }

static fspec funcs[] = {
	{memcpy, {F_PTR | F_DST, F_DST, F_SRC, F_N}},
	{i_memcpy, {F_PTR | F_DST, F_DST, F_SRC, F_N}},
	{strcpy, {F_PTR | F_DST | F_NUL, F_DST, F_SRC}},
	{strncpy, {F_PTR | F_DST | F_PAD, F_DST, F_SRC, F_N}},
	{strcat, {F_PTR | F_DST | F_NUL, F_DST | F_SRC, F_SRC}},
	{strncat, {F_PTR | F_DST | F_NUL, F_DST | F_SRC, F_SRC, F_N}},
	{strchr, {F_PTR | F_IN_A1 | F_NUL, F_SRC, F_C}},
	{strstr, {F_PTR | F_IN_A1 | F_NUL, F_SRC, F_SRC}},
	{NULL}
};

typedef struct {
	enum {A_DST, A_SRC, A_N, A_C} t;
	union {
		struct {
			char *s;
			size_t len;
		} s;
		size_t n;
		int c;
	} v;
} arg;

static void arg_reset(arg *a)
{
	switch (a->t) {
	case A_DST:
		break;
	case A_SRC:
		a->v.s.s[0] = '\0';
		a->v.s.len = 0;
		break;
	case A_N:
		a->v.n = 0;
		break;
	case A_C:
		a->v.c = MIN_C;
		break;
	default:
		abort();
	}
}

static int arg_next(arg *a)
{
	switch (a->t) {
	case A_DST:
		return 1;
	case A_SRC:
		a->v.s.s[a->v.s.len] =
		    MIN_C + (a->v.s.len % (MAX_C - MIN_C + 1));
		if (++a->v.s.len >= STR_SIZE) {
			arg_reset(a);
			return 1;
		}
		a->v.s.s[a->v.s.len] = '\0';
		return 0;
	case A_N:
		if (++a->v.n >= STR_SIZE) {
			arg_reset(a);
			return 1;
		}
		return 0;
	case A_C:
		if (++a->v.c > MAX_C) {
			arg_reset(a);
			return 1;
		}
		return 0;
	default:
		abort();
	}
}

static void arg_alloc(arg *a, unsigned int flags)
{
	if (flags & F_IS_PTR) {
		a->t = (flags & F_SRC) ? A_SRC : A_DST;
		a->v.s.s = malloc(STR_SIZE * 2); /* consider strcat() */
		assert(a->v.s.s != NULL);
	} else if (flags & F_N)
		a->t = A_N;
	else if (flags & F_C)
		a->t = A_C;
	else
		abort();
	arg_reset(a);
}

static void arg_free(arg *a)
{
	if (a->t == A_DST || a->t == A_SRC)
		free(a->v.s.s);
}

static void test_one(fspec *f)
{
	arg a[3];
	int ia, na;

	na = 1;
	while (f->a[na] && na < 4)
		na++;
	na--;

	for (ia = 0; ia < na; ia++)
		arg_alloc(&a[ia], f->a[ia + 1]);

	do {
		const char *r = NULL;

		/* (ptr, ptr, n) or (ptr, ptr) */
		if ((f->a[1] & F_IS_PTR) && (f->a[2] & F_IS_PTR) &&
		    !(f->a[3] & ~F_N)) {
			r = ((char * (*)(char *, char *, size_t))f->f)
			    (a[0].v.s.s, a[1].v.s.s, a[2].v.n);
		} else
		/* (ptr, c) */
		if ((f->a[1] & F_IS_PTR) && (f->a[2] & F_C) && !f->a[3]) {
			r = ((char * (*)(char *, int))f->f)
			    (a[0].v.s.s, a[1].v.c);
		}

		if (((f->a[0] & F_DST) && r != a[0].v.s.s) ||
		    ((f->a[0] & F_IN_A1) &&
		    r && (r < a[0].v.s.s || r > a[0].v.s.s + a[0].v.s.len)))
			fprintf(stderr, "Wrong return value: %p '%s'\n", r, r);

/*
 * Should perform other checks here: for proper NUL termination or padding (as
 * indicated by F_NUL or F_PAD), etc. (need to add more flags).
 */

		ia = 0;
		while (ia < na && arg_next(&a[ia]))
			ia++;
	} while (ia < na);

	for (ia = 0; ia < na; ia++)
		arg_free(&a[ia]);
}

static void test_all(void)
{
	fspec *f;

	for (f = funcs; f->f; f++)
		test_one(f);
}

int main(void)
{
	test_all();

	return 0;
}