[thirdparty/git.git] / t / helper / test-mergesort.c

#include "test-tool.h"
#include "mem-pool.h"
#include "mergesort.h"
#include "strbuf.h"

static uint32_t minstd_rand(uint32_t *state)
{
	*state = (uint64_t)*state * 48271 % 2147483647;
	return *state;
}

struct line {
	char *text;
	struct line *next;
};

DEFINE_LIST_SORT(static, sort_lines, struct line, next);

static int compare_strings(const struct line *x, const struct line *y)
{
	return strcmp(x->text, y->text);
}

static int sort_stdin(void)
{
	struct line *lines;
	struct line **tail = &lines;
	struct strbuf sb = STRBUF_INIT;
	struct mem_pool lines_pool;
	char *p;

	strbuf_read(&sb, 0, 0);

	/*
	 * Split by newline, but don't create an item
	 * for the empty string after the last separator.
	 */
	if (sb.len && sb.buf[sb.len - 1] == '\n')
		strbuf_setlen(&sb, sb.len - 1);

	mem_pool_init(&lines_pool, 0);
	p = sb.buf;
	for (;;) {
		char *eol = strchr(p, '\n');
		struct line *line = mem_pool_alloc(&lines_pool, sizeof(*line));
		line->text = p;
		*tail = line;
		tail = &line->next;
		if (!eol)
			break;
		*eol = '\0';
		p = eol + 1;
	}
	*tail = NULL;

	sort_lines(&lines, compare_strings);

	while (lines) {
		puts(lines->text);
		lines = lines->next;
	}
	return 0;
}

static void dist_sawtooth(int *arr, int n, int m)
{
	int i;
	for (i = 0; i < n; i++)
		arr[i] = i % m;
}

static void dist_rand(int *arr, int n, int m)
{
	int i;
	uint32_t seed = 1;
	for (i = 0; i < n; i++)
		arr[i] = minstd_rand(&seed) % m;
}

static void dist_stagger(int *arr, int n, int m)
{
	int i;
	for (i = 0; i < n; i++)
		arr[i] = (i * m + i) % n;
}

static void dist_plateau(int *arr, int n, int m)
{
	int i;
	for (i = 0; i < n; i++)
		arr[i] = (i < m) ? i : m;
}

static void dist_shuffle(int *arr, int n, int m)
{
	int i, j, k;
	uint32_t seed = 1;
	for (i = j = 0, k = 1; i < n; i++)
		arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
}

#define DIST(name) { #name, dist_##name }

static struct dist {
	const char *name;
	void (*fn)(int *arr, int n, int m);
} dist[] = {
	DIST(sawtooth),
	DIST(rand),
	DIST(stagger),
	DIST(plateau),
	DIST(shuffle),
};

static const struct dist *get_dist_by_name(const char *name)
{
	int i;
	for (i = 0; i < ARRAY_SIZE(dist); i++) {
	       if (!strcmp(dist[i].name, name))
		       return &dist[i];
	}
	return NULL;
}

static void mode_copy(int *arr, int n)
{
	/* nothing */
}

static void mode_reverse(int *arr, int n)
{
	int i, j;
	for (i = 0, j = n - 1; i < j; i++, j--)
		SWAP(arr[i], arr[j]);
}

static void mode_reverse_1st_half(int *arr, int n)
{
	mode_reverse(arr, n / 2);
}

static void mode_reverse_2nd_half(int *arr, int n)
{
	int half = n / 2;
	mode_reverse(arr + half, n - half);
}

static int compare_ints(const void *av, const void *bv)
{
	const int *ap = av, *bp = bv;
	int a = *ap, b = *bp;
	return (a > b) - (a < b);
}

static void mode_sort(int *arr, int n)
{
	QSORT(arr, n, compare_ints);
}

static void mode_dither(int *arr, int n)
{
	int i;
	for (i = 0; i < n; i++)
		arr[i] += i % 5;
}

static void unriffle(int *arr, int n, int *tmp)
{
	int i, j;
	COPY_ARRAY(tmp, arr, n);
	for (i = j = 0; i < n; i += 2)
		arr[j++] = tmp[i];
	for (i = 1; i < n; i += 2)
		arr[j++] = tmp[i];
}

static void unriffle_recursively(int *arr, int n, int *tmp)
{
	if (n > 1) {
		int half = n / 2;
		unriffle(arr, n, tmp);
		unriffle_recursively(arr, half, tmp);
		unriffle_recursively(arr + half, n - half, tmp);
	}
}

static void mode_unriffle(int *arr, int n)
{
	int *tmp;
	ALLOC_ARRAY(tmp, n);
	unriffle_recursively(arr, n, tmp);
	free(tmp);
}

static unsigned int prev_pow2(unsigned int n)
{
	unsigned int pow2 = 1;
	while (pow2 * 2 < n)
		pow2 *= 2;
	return pow2;
}

static void unriffle_recursively_skewed(int *arr, int n, int *tmp)
{
	if (n > 1) {
		int pow2 = prev_pow2(n);
		int rest = n - pow2;
		unriffle(arr + pow2 - rest, rest * 2, tmp);
		unriffle_recursively_skewed(arr, pow2, tmp);
		unriffle_recursively_skewed(arr + pow2, rest, tmp);
	}
}

static void mode_unriffle_skewed(int *arr, int n)
{
	int *tmp;
	ALLOC_ARRAY(tmp, n);
	unriffle_recursively_skewed(arr, n, tmp);
	free(tmp);
}

#define MODE(name) { #name, mode_##name }

static struct mode {
	const char *name;
	void (*fn)(int *arr, int n);
} mode[] = {
	MODE(copy),
	MODE(reverse),
	MODE(reverse_1st_half),
	MODE(reverse_2nd_half),
	MODE(sort),
	MODE(dither),
	MODE(unriffle),
	MODE(unriffle_skewed),
};

static const struct mode *get_mode_by_name(const char *name)
{
	int i;
	for (i = 0; i < ARRAY_SIZE(mode); i++) {
	       if (!strcmp(mode[i].name, name))
		       return &mode[i];
	}
	return NULL;
}

static int generate(int argc, const char **argv)
{
	const struct dist *dist = NULL;
	const struct mode *mode = NULL;
	int i, n, m, *arr;

	if (argc != 4)
		return 1;

	dist = get_dist_by_name(argv[0]);
	mode = get_mode_by_name(argv[1]);
	n = strtol(argv[2], NULL, 10);
	m = strtol(argv[3], NULL, 10);
	if (!dist || !mode)
		return 1;

	ALLOC_ARRAY(arr, n);
	dist->fn(arr, n, m);
	mode->fn(arr, n);
	for (i = 0; i < n; i++)
		printf("%08x\n", arr[i]);
	free(arr);
	return 0;
}

static struct stats {
	int get_next, set_next, compare;
} stats;

struct number {
	int value, rank;
	struct number *next;
};

DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,
		       stats.get_next++, stats.set_next++);

static int compare_numbers(const struct number *an, const struct number *bn)
{
	int a = an->value, b = bn->value;
	stats.compare++;
	return (a > b) - (a < b);
}

static void clear_numbers(struct number *list)
{
	while (list) {
		struct number *next = list->next;
		free(list);
		list = next;
	}
}

static int test(const struct dist *dist, const struct mode *mode, int n, int m)
{
	int *arr;
	size_t i;
	struct number *curr, *list, **tail;
	int is_sorted = 1;
	int is_stable = 1;
	const char *verdict;
	int result = -1;

	ALLOC_ARRAY(arr, n);
	dist->fn(arr, n, m);
	mode->fn(arr, n);
	for (i = 0, tail = &list; i < n; i++) {
		curr = xmalloc(sizeof(*curr));
		curr->value = arr[i];
		curr->rank = i;
		*tail = curr;
		tail = &curr->next;
	}
	*tail = NULL;

	stats.get_next = stats.set_next = stats.compare = 0;
	sort_numbers(&list, compare_numbers);

	QSORT(arr, n, compare_ints);
	for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
		if (arr[i] != curr->value)
			is_sorted = 0;
		if (curr->next && curr->value == curr->next->value &&
		    curr->rank >= curr->next->rank)
			is_stable = 0;
	}
	if (i < n) {
		verdict = "too short";
	} else if (curr) {
		verdict = "too long";
	} else if (!is_sorted) {
		verdict = "not sorted";
	} else if (!is_stable) {
		verdict = "unstable";
	} else {
		verdict = "OK";
		result = 0;
	}

	printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n",
	       dist->name, mode->name, n, m, stats.get_next, stats.set_next,
	       stats.compare, verdict);

	clear_numbers(list);
	free(arr);

	return result;
}

/*
 * A version of the qsort certification program from "Engineering a Sort
 * Function" by Bentley and McIlroy, Software—Practice and Experience,
 * Volume 23, Issue 11, 1249–1265 (November 1993).
 */
static int run_tests(int argc, const char **argv)
{
	const char *argv_default[] = { "100", "1023", "1024", "1025" };
	if (!argc)
		return run_tests(ARRAY_SIZE(argv_default), argv_default);
	printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n",
	       "distribut", "mode", "n", "m", "get_next", "set_next",
	       "compare", "verdict");
	while (argc--) {
		int i, j, m, n = strtol(*argv++, NULL, 10);
		for (i = 0; i < ARRAY_SIZE(dist); i++) {
			for (j = 0; j < ARRAY_SIZE(mode); j++) {
				for (m = 1; m < 2 * n; m *= 2) {
					if (test(&dist[i], &mode[j], n, m))
						return 1;
				}
			}
		}
	}
	return 0;
}

int cmd__mergesort(int argc, const char **argv)
{
	int i;
	const char *sep;

	if (argc == 6 && !strcmp(argv[1], "generate"))
		return generate(argc - 2, argv + 2);
	if (argc == 2 && !strcmp(argv[1], "sort"))
		return sort_stdin();
	if (argc > 1 && !strcmp(argv[1], "test"))
		return run_tests(argc - 2, argv + 2);
	fprintf(stderr, "usage: test-tool mergesort generate <distribution> <mode> <n> <m>\n");
	fprintf(stderr, "   or: test-tool mergesort sort\n");
	fprintf(stderr, "   or: test-tool mergesort test [<n>...]\n");
	fprintf(stderr, "\n");
	for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ")
		fprintf(stderr, "%s%s", sep, dist[i].name);
	fprintf(stderr, "\n");
	for (i = 0, sep = "modes: "; i < ARRAY_SIZE(mode); i++, sep = ", ")
		fprintf(stderr, "%s%s", sep, mode[i].name);
	fprintf(stderr, "\n");
	return 129;
}
Commit	Line	Data
34889d3c	1	#include "test-tool.h"
5bc07225	2	#include "mem-pool.h"
0db71e0f	3	#include "mergesort.h"
69a63fe6	4	#include "strbuf.h"
0db71e0f	5
c90cfc22 RS	6	static uint32_t minstd_rand(uint32_t *state)
	7	{
	8	state = (uint64_t)state * 48271 % 2147483647;
	9	return *state;
	10	}
	11
0db71e0f RS	12	struct line {
	13	char *text;
	14	struct line *next;
	15	};
	16
b378c2ff	17	DEFINE_LIST_SORT(static, sort_lines, struct line, next);
0db71e0f	18
b378c2ff	19	static int compare_strings(const struct line x, const struct line y)
0db71e0f	20	{
0db71e0f RS	21	return strcmp(x->text, y->text);
	22	}
	23
d536a711	24	static int sort_stdin(void)
0db71e0f	25	{
f3e8ba2e RS	26	struct line *lines;
f3e8ba2e RS	27	struct line **tail = &lines;
0db71e0f	28	struct strbuf sb = STRBUF_INIT;
c333c2ce	29	struct mem_pool lines_pool;
f3e8ba2e	30	char *p;
0db71e0f	31
f3e8ba2e RS	32	strbuf_read(&sb, 0, 0);
	33
	34	/*
	35	* Split by newline, but don't create an item
	36	* for the empty string after the last separator.
	37	*/
	38	if (sb.len && sb.buf[sb.len - 1] == '\n')
	39	strbuf_setlen(&sb, sb.len - 1);
	40
c333c2ce	41	mem_pool_init(&lines_pool, 0);
f3e8ba2e RS	42	p = sb.buf;
	43	for (;;) {
	44	char *eol = strchr(p, '\n');
c333c2ce	45	struct line line = mem_pool_alloc(&lines_pool, sizeof(line));
f3e8ba2e RS	46	line->text = p;
	47	*tail = line;
	48	tail = &line->next;
	49	if (!eol)
	50	break;
	51	*eol = '\0';
	52	p = eol + 1;
0db71e0f	53	}
f3e8ba2e	54	*tail = NULL;
0db71e0f	55
b378c2ff	56	sort_lines(&lines, compare_strings);
0db71e0f RS	57
0db71e0f RS	58	while (lines) {
2e670101	59	puts(lines->text);
0db71e0f RS	60	lines = lines->next;
	61	}
	62	return 0;
	63	}
d536a711	64
e031e971 RS	65	static void dist_sawtooth(int *arr, int n, int m)
	66	{
	67	int i;
	68	for (i = 0; i < n; i++)
	69	arr[i] = i % m;
	70	}
	71
	72	static void dist_rand(int *arr, int n, int m)
	73	{
	74	int i;
c90cfc22	75	uint32_t seed = 1;
e031e971	76	for (i = 0; i < n; i++)
c90cfc22	77	arr[i] = minstd_rand(&seed) % m;
e031e971 RS	78	}
	79
	80	static void dist_stagger(int *arr, int n, int m)
	81	{
	82	int i;
	83	for (i = 0; i < n; i++)
	84	arr[i] = (i * m + i) % n;
	85	}
	86
	87	static void dist_plateau(int *arr, int n, int m)
	88	{
	89	int i;
	90	for (i = 0; i < n; i++)
	91	arr[i] = (i < m) ? i : m;
	92	}
	93
	94	static void dist_shuffle(int *arr, int n, int m)
	95	{
	96	int i, j, k;
c90cfc22	97	uint32_t seed = 1;
e031e971	98	for (i = j = 0, k = 1; i < n; i++)
c90cfc22	99	arr[i] = minstd_rand(&seed) % m ? (j += 2) : (k += 2);
e031e971 RS	100	}
	101
	102	#define DIST(name) { #name, dist_##name }
	103
	104	static struct dist {
	105	const char *name;
	106	void (fn)(int arr, int n, int m);
	107	} dist[] = {
	108	DIST(sawtooth),
	109	DIST(rand),
	110	DIST(stagger),
	111	DIST(plateau),
	112	DIST(shuffle),
	113	};
	114
0cecb755 RS	115	static const struct dist get_dist_by_name(const char name)
	116	{
	117	int i;
	118	for (i = 0; i < ARRAY_SIZE(dist); i++) {
	119	if (!strcmp(dist[i].name, name))
	120	return &dist[i];
	121	}
	122	return NULL;
	123	}
	124
e031e971 RS	125	static void mode_copy(int *arr, int n)
	126	{
	127	/* nothing */
	128	}
	129
	130	static void mode_reverse(int *arr, int n)
	131	{
	132	int i, j;
	133	for (i = 0, j = n - 1; i < j; i++, j--)
	134	SWAP(arr[i], arr[j]);
	135	}
	136
	137	static void mode_reverse_1st_half(int *arr, int n)
	138	{
	139	mode_reverse(arr, n / 2);
	140	}
	141
	142	static void mode_reverse_2nd_half(int *arr, int n)
	143	{
	144	int half = n / 2;
	145	mode_reverse(arr + half, n - half);
	146	}
	147
	148	static int compare_ints(const void av, const void bv)
	149	{
	150	const int ap = av, bp = bv;
	151	int a = ap, b = bp;
	152	return (a > b) - (a < b);
	153	}
	154
	155	static void mode_sort(int *arr, int n)
	156	{
	157	QSORT(arr, n, compare_ints);
	158	}
	159
	160	static void mode_dither(int *arr, int n)
	161	{
	162	int i;
	163	for (i = 0; i < n; i++)
	164	arr[i] += i % 5;
	165	}
	166
1aa58992 RS	167	static void unriffle(int arr, int n, int tmp)
	168	{
	169	int i, j;
	170	COPY_ARRAY(tmp, arr, n);
	171	for (i = j = 0; i < n; i += 2)
	172	arr[j++] = tmp[i];
	173	for (i = 1; i < n; i += 2)
	174	arr[j++] = tmp[i];
	175	}
	176
	177	static void unriffle_recursively(int arr, int n, int tmp)
	178	{
	179	if (n > 1) {
	180	int half = n / 2;
	181	unriffle(arr, n, tmp);
	182	unriffle_recursively(arr, half, tmp);
	183	unriffle_recursively(arr + half, n - half, tmp);
	184	}
	185	}
	186
	187	static void mode_unriffle(int *arr, int n)
	188	{
	189	int *tmp;
	190	ALLOC_ARRAY(tmp, n);
	191	unriffle_recursively(arr, n, tmp);
	192	free(tmp);
	193	}
	194
f1ed4ce9 RS	195	static unsigned int prev_pow2(unsigned int n)
	196	{
	197	unsigned int pow2 = 1;
	198	while (pow2 * 2 < n)
	199	pow2 *= 2;
	200	return pow2;
	201	}
	202
	203	static void unriffle_recursively_skewed(int arr, int n, int tmp)
	204	{
	205	if (n > 1) {
	206	int pow2 = prev_pow2(n);
	207	int rest = n - pow2;
	208	unriffle(arr + pow2 - rest, rest * 2, tmp);
	209	unriffle_recursively_skewed(arr, pow2, tmp);
	210	unriffle_recursively_skewed(arr + pow2, rest, tmp);
	211	}
	212	}
	213
	214	static void mode_unriffle_skewed(int *arr, int n)
	215	{
	216	int *tmp;
	217	ALLOC_ARRAY(tmp, n);
	218	unriffle_recursively_skewed(arr, n, tmp);
	219	free(tmp);
	220	}
	221
e031e971 RS	222	#define MODE(name) { #name, mode_##name }
	223
	224	static struct mode {
	225	const char *name;
	226	void (fn)(int arr, int n);
	227	} mode[] = {
	228	MODE(copy),
	229	MODE(reverse),
	230	MODE(reverse_1st_half),
	231	MODE(reverse_2nd_half),
	232	MODE(sort),
	233	MODE(dither),
1aa58992	234	MODE(unriffle),
f1ed4ce9	235	MODE(unriffle_skewed),
e031e971 RS	236	};
e031e971 RS	237
0cecb755 RS	238	static const struct mode get_mode_by_name(const char name)
	239	{
	240	int i;
	241	for (i = 0; i < ARRAY_SIZE(mode); i++) {
	242	if (!strcmp(mode[i].name, name))
	243	return &mode[i];
	244	}
	245	return NULL;
	246	}
	247
	248	static int generate(int argc, const char **argv)
	249	{
	250	const struct dist *dist = NULL;
	251	const struct mode *mode = NULL;
	252	int i, n, m, *arr;
	253
	254	if (argc != 4)
	255	return 1;
	256
	257	dist = get_dist_by_name(argv[0]);
	258	mode = get_mode_by_name(argv[1]);
	259	n = strtol(argv[2], NULL, 10);
	260	m = strtol(argv[3], NULL, 10);
	261	if (!dist \|\| !mode)
	262	return 1;
	263
	264	ALLOC_ARRAY(arr, n);
	265	dist->fn(arr, n, m);
	266	mode->fn(arr, n);
	267	for (i = 0; i < n; i++)
	268	printf("%08x\n", arr[i]);
	269	free(arr);
	270	return 0;
	271	}
	272
e031e971 RS	273	static struct stats {
	274	int get_next, set_next, compare;
	275	} stats;
	276
	277	struct number {
	278	int value, rank;
	279	struct number *next;
	280	};
	281
f00a0398 RS	282	DEFINE_LIST_SORT_DEBUG(static, sort_numbers, struct number, next,
f00a0398 RS	283	stats.get_next++, stats.set_next++);
e031e971	284
f00a0398	285	static int compare_numbers(const struct number an, const struct number bn)
e031e971	286	{
e031e971 RS	287	int a = an->value, b = bn->value;
	288	stats.compare++;
	289	return (a > b) - (a < b);
	290	}
	291
	292	static void clear_numbers(struct number *list)
	293	{
	294	while (list) {
	295	struct number *next = list->next;
	296	free(list);
	297	list = next;
	298	}
	299	}
	300
	301	static int test(const struct dist dist, const struct mode mode, int n, int m)
	302	{
	303	int *arr;
	304	size_t i;
	305	struct number curr, list, **tail;
	306	int is_sorted = 1;
	307	int is_stable = 1;
	308	const char *verdict;
	309	int result = -1;
	310
	311	ALLOC_ARRAY(arr, n);
	312	dist->fn(arr, n, m);
	313	mode->fn(arr, n);
	314	for (i = 0, tail = &list; i < n; i++) {
	315	curr = xmalloc(sizeof(*curr));
	316	curr->value = arr[i];
	317	curr->rank = i;
	318	*tail = curr;
	319	tail = &curr->next;
	320	}
	321	*tail = NULL;
	322
	323	stats.get_next = stats.set_next = stats.compare = 0;
f00a0398	324	sort_numbers(&list, compare_numbers);
e031e971 RS	325
	326	QSORT(arr, n, compare_ints);
	327	for (i = 0, curr = list; i < n && curr; i++, curr = curr->next) {
	328	if (arr[i] != curr->value)
	329	is_sorted = 0;
	330	if (curr->next && curr->value == curr->next->value &&
	331	curr->rank >= curr->next->rank)
	332	is_stable = 0;
	333	}
	334	if (i < n) {
	335	verdict = "too short";
	336	} else if (curr) {
	337	verdict = "too long";
	338	} else if (!is_sorted) {
	339	verdict = "not sorted";
	340	} else if (!is_stable) {
	341	verdict = "unstable";
	342	} else {
	343	verdict = "OK";
	344	result = 0;
	345	}
	346
	347	printf("%-9s %-16s %8d %8d %8d %8d %8d %s\n",
	348	dist->name, mode->name, n, m, stats.get_next, stats.set_next,
	349	stats.compare, verdict);
	350
	351	clear_numbers(list);
	352	free(arr);
	353
	354	return result;
	355	}
	356
	357	/*
	358	* A version of the qsort certification program from "Engineering a Sort
	359	* Function" by Bentley and McIlroy, Software—Practice and Experience,
	360	* Volume 23, Issue 11, 1249–1265 (November 1993).
	361	*/
	362	static int run_tests(int argc, const char **argv)
	363	{
	364	const char *argv_default[] = { "100", "1023", "1024", "1025" };
	365	if (!argc)
	366	return run_tests(ARRAY_SIZE(argv_default), argv_default);
	367	printf("%-9s %-16s %8s %8s %8s %8s %8s %s\n",
	368	"distribut", "mode", "n", "m", "get_next", "set_next",
	369	"compare", "verdict");
	370	while (argc--) {
	371	int i, j, m, n = strtol(*argv++, NULL, 10);
	372	for (i = 0; i < ARRAY_SIZE(dist); i++) {
	373	for (j = 0; j < ARRAY_SIZE(mode); j++) {
	374	for (m = 1; m < 2 * n; m *= 2) {
	375	if (test(&dist[i], &mode[j], n, m))
	376	return 1;
	377	}
	378	}
	379	}
	380	}
	381	return 0;
	382	}
	383
d536a711 RS	384	int cmd__mergesort(int argc, const char **argv)
d536a711 RS	385	{
0cecb755 RS	386	int i;
	387	const char *sep;
	388
	389	if (argc == 6 && !strcmp(argv[1], "generate"))
	390	return generate(argc - 2, argv + 2);
d536a711 RS	391	if (argc == 2 && !strcmp(argv[1], "sort"))
d536a711 RS	392	return sort_stdin();
e031e971 RS	393	if (argc > 1 && !strcmp(argv[1], "test"))
e031e971 RS	394	return run_tests(argc - 2, argv + 2);
0cecb755 RS	395	fprintf(stderr, "usage: test-tool mergesort generate <distribution> <mode> <n> <m>\n");
0cecb755 RS	396	fprintf(stderr, " or: test-tool mergesort sort\n");
e031e971	397	fprintf(stderr, " or: test-tool mergesort test [<n>...]\n");
0cecb755 RS	398	fprintf(stderr, "\n");
	399	for (i = 0, sep = "distributions: "; i < ARRAY_SIZE(dist); i++, sep = ", ")
	400	fprintf(stderr, "%s%s", sep, dist[i].name);
	401	fprintf(stderr, "\n");
	402	for (i = 0, sep = "modes: "; i < ARRAY_SIZE(mode); i++, sep = ", ")
	403	fprintf(stderr, "%s%s", sep, mode[i].name);
	404	fprintf(stderr, "\n");
e031e971	405	return 129;
d536a711	406	}