[mLib] / hash / crc-mktab.c

/* -*-c-*-
 *
 * Build CRC tables
 *
 * (c) 2000 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------*
 *
 * This file is part of the mLib utilities library.
 *
 * mLib is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * mLib is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with mLib; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Header files ------------------------------------------------------*/

#include "config.h"

#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "mdwopt.h"
#include "quis.h"
#include "report.h"

/*----- Static variables --------------------------------------------------*/

static unsigned long poly = 0;
static const char *guard = 0;
static unsigned bits = 0;
static unsigned chunk = 8;
static const char *file = 0;
static unsigned flags = 0;
static const char *sym = 0;
static const char *type = 0;
static const char *inc = 0;
static FILE *fp;

#define f_bogus 1u
#define f_ctab 2u
#define f_reverse 4u
#define f_const 8u

#define BSCOL 72

/*----- Main code ---------------------------------------------------------*/

static unsigned long getint(const char *p, unsigned long max,
			    const char *what)
{
  char *pp;
  unsigned long x = strtoul(p, &pp, 0);
  if (*pp || (max && x > max))
    die(EXIT_FAILURE, "bad %s `%s'", what, p);
  return (x);
}

static void version(FILE *fp)
{
  pquis(fp, "$, mLib version " VERSION "\n");
}

static void usage(FILE *fp)
{
  pquis(fp, "Usage: $ [-Ccr] [-o FILE] [-g GUARD] [-s SYM] [-i HEADER]\n\
	[-t TYPE] [-b BITS] [-B BITS] [-p POLY]\n");
}

static void help(FILE *fp)
{
  version(fp);
  putc('\n', stdout);
  usage(fp);
  fputs("\n\
Emits a table containing precomuted values for CRC algorithms.  A number\n\
of options are provided:\n\
\n\
-h, --help		Show this help text.\n\
-v, --version		Show the program's version number.\n\
-u, --usage		Show a terse usage message.\n\
\n\
-c, --c-source		Emit a C source file rather than a header.\n\
-C, --const		Declare table to be `const' (only useful with `-c').\n\
-b, --bits=BITS		Emit a table for a BITS bits-wide CRC.\n\
-B, --bit-chunk=BITS	Emit a table to process BITS bits at a time.\n\
-p, --polynomial=POLY	Use the POLY as the dividing polynomial.\n\
-r, --reverse		Create a `reversed' CRC table.\n\
-g, --guard=GUARD	Use GUARD as a multiple-inclusion guard constant.\n\
-i, --include=HEADER	Include HEADER at top of C source file.\n\
-s, --symbol=SYM	Name the generated table SYM.\n\
-t, --type=TYPE		Give the table entries type TYPE in C source.\n\
-o, --output=FILE	Write the output to FILE.\n\
", stdout);
}

unsigned long reflect(unsigned long x, unsigned b)
{
  unsigned long y = 0;
  unsigned long xm, ym;
  unsigned i;
  if (!(flags & f_reverse))
    return (x);
  xm = 1;
  ym = 1u << (b - 1);
  for (i = 0; i < b; i++) {
    if (x & xm)
      y |= ym;
    xm <<= 1;
    ym >>= 1;
  }
  return (y);
}

int main(int argc, char *argv[])
{
  unsigned n, t, nw;
  unsigned max, i;
  unsigned long mask;

  ego(argv[0]);

  for (;;) {
    static struct option opts[] = {
      { "help",		0,		0,	'h' },
      { "version",	0,		0,	'v' },
      { "usage",	0,		0,	'u' },

      { "output",	OPTF_ARGREQ,	0,	'o' },
      { "c-source",	0,		0,	'c' },
      { "const",	0,		0,	'C' },
      { "symbol",	OPTF_ARGREQ,	0,	's' },
      { "type",		OPTF_ARGREQ,	0,	't' },
      { "include",	OPTF_ARGREQ,	0,	'i' },
      { "guard",	OPTF_ARGREQ,	0,	'g' },

      { "bits",		OPTF_ARGREQ,	0,	'b' },
      { "bit-chunk",	OPTF_ARGREQ,	0,	'B' },
      { "polynomial",	OPTF_ARGREQ,	0,	'p' },
      { "reverse",	0,		0,	'r' },

      { 0,		0,		0,	0 }
    };
    int i = mdwopt(argc, argv, "hvu o:cCs:t:i:g: b:B:p:r", opts, 0, 0, 0);

    if (i < 0)
      break;
    switch (i) {
      case 'h':
	help(stdout);
	exit(0);
      case 'v':
	version(stdout);
	exit(0);
      case 'u':
	usage(stdout);
	exit(0);

      case 'o':
	file = optarg;
	break;
      case 'c':
	flags |= f_ctab;
	break;
      case 'C':
	flags |= f_const;
	break;
      case 's':
	sym = optarg;
	break;
      case 't':
	type = optarg;
	break;
      case 'i':
	inc = optarg;
	break;
      case 'g':
	guard = optarg;
	break;

      case 'b':
	bits = getint(optarg, 32, "CRC width");
	break;
      case 'B':
	chunk = getint(optarg, 32, "chunk size");
	break;
      case 'p':
	poly = getint(optarg, 0xffffffff, "CRC poly");
	break;
      case 'r':
	flags |= f_reverse;
	break;

      default:
	flags |= f_bogus;
	break;
    }
  }
  if ((flags & f_bogus) || optind != argc) {
    usage(stderr);
    exit(EXIT_FAILURE);
  }

  /* --- Sort out the various parameters --- */

  if (!poly) {
    switch (bits) {
      case 16:
	if (flags & f_reverse)
	  poly = 0x8408;
	else
	  poly = 0x1021;
	break;
      case 32:
	poly = 0x04c11db7;
	flags |= f_reverse;
	bits = 32;
	break;
      case 0:
	die(EXIT_FAILURE, "no polynomial or bit width set");
	break;
      default:
	die(EXIT_FAILURE, "no standard polynomials for %u bits", bits);
	break;
    }
  }

  if (!bits) {
    unsigned long x = poly;
    while (x > 1) {
      x >>= 8;
      bits += 8;
    }
  }
  nw = (bits + 3)/4;

  if ((flags & f_ctab) && !type)
    type = bits > 16 ? "unsigned long" : "unsigned short";

  /* --- Start output --- */

  if (!file)
    fp = stdout;
  else {
    if (!(flags & f_ctab) && !guard) {
      char *p;
      const char *q;
      if ((p = malloc(strlen(file) + 1)) == 0)
	die(EXIT_FAILURE, "not enough memory");
      guard = p;
      for (q = file; *q; p++, q++) {
	if (isalnum((unsigned char)*q))
	  *p = toupper((unsigned char)*q);
	else
	  *p = '_';
      }
      *p++ = 0;
    }
    if ((fp = fopen(file, "w")) == 0)
      die(EXIT_FAILURE, "couldn't write `%s': %s", file, strerror(errno));
  }

  if (!sym)
    sym = (flags & f_ctab) ? "crctab" : "CRC_TAB";

  /* --- Dump out the first chunk of the file --- */

  fprintf(fp, "\
/* -*-c-*-\n\
 *\n\
 * CRC table (poly = %0*lx%s) [generated]\n\
 */\n\
\n",
	  nw, poly, flags & f_reverse ? "; reversed" : "");

  if (flags & f_ctab) {
    if (inc)
      fprintf(fp, "#include \"%s\"\n\n", inc);
    fprintf(fp, "%s%s %s[] = {\n",
	    (flags&f_const) ? "const " : "", type, sym);
  } else {
    int n;
    if (guard)
      fprintf(fp, "#ifndef %s\n#define %s\n\n", guard, guard);
    n = fprintf(fp, "#define %s {", sym);
    while (n < BSCOL) {
      fputc('\t', fp);
      n = (n + 8) & ~7;
    }
    fputc('\n', fp);
  }

  /* --- Sort out the line width --- */

  n = 1;
  while (2 + n * (nw + 4) < BSCOL)
    n <<= 1;
  n >>= 1;
  max = 1 << chunk;
  if (n > max)
    n = max;
  t = 0;
  while (((1 + n * (nw + 4)) & ~7) + 8 * t < BSCOL)
    t++;

  /* --- Start grinding --- */

  mask = 0xffffffff >> (32 - bits);
  fputc(' ', fp);
  for (i = 0; i < max; i++) {
    unsigned long x, y, z;
    unsigned j;
    unsigned ni, nn;

    x = reflect(i, chunk);
    y = 0;
    nn = chunk;
    while (nn) {
      ni = bits;
      if (ni > nn)
	ni = nn;
      z = (x >> (nn - ni)) & (0xffffffff >> (32 - ni));
      y ^= z << (bits - ni);
      for (j = 0; j < ni; j++)
	y = ((y << 1) ^ (y & (1 << (bits - 1)) ? poly : 0)) & mask;
      nn -= ni;
    }
    x = reflect(y, bits);

    fprintf(fp, " 0x%0*lx", nw, x);
    if (i == max - 1) {
      if (!(flags & f_ctab) && ((2 + n * (nw + 4)) & ~7) + 8 * t < BSCOL)
	fputc('\t', fp);
    } else
      fputc(',', fp);
    if (i + 1 == max || (i + 1)%n == 0) {
      if (!(flags & f_ctab)) {
	for (j = 0; j < t; j++)
	  fputc('\t', fp);
	fputc('\\', fp);
      }
      fputc('\n', fp);
      if (i + 1 != max)
	fputc(' ', fp);
    }
  }

  /* --- Done --- */

  fputs(flags & f_ctab ? "};\n" : "}\n", fp);
  if (!(flags & f_ctab) && guard)
    fputs("\n#endif\n", fp);

  return (0);
}

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
b7580524	1	/* --c--
b7580524	2	*
b7580524	3	* Build CRC tables
	4	*
	5	* (c) 2000 Straylight/Edgeware
	6	*/
	7
d4efbcd9	8	/----- Licensing notice --------------------------------------------------
b7580524	9	*
	10	* This file is part of the mLib utilities library.
	11	*
	12	* mLib is free software; you can redistribute it and/or modify
	13	* it under the terms of the GNU Library General Public License as
	14	* published by the Free Software Foundation; either version 2 of the
	15	* License, or (at your option) any later version.
d4efbcd9	16	*
b7580524	17	* mLib is distributed in the hope that it will be useful,
	18	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	20	* GNU Library General Public License for more details.
d4efbcd9	21	*
b7580524	22	* You should have received a copy of the GNU Library General Public
	23	* License along with mLib; if not, write to the Free
	24	* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
	25	* MA 02111-1307, USA.
	26	*/
	27
b7580524	28	/----- Header files ------------------------------------------------------/
b7580524	29
a0150d8d MW	30	#include "config.h"
a0150d8d MW	31
b7580524	32	#include <ctype.h>
	33	#include <errno.h>
	34	#include <limits.h>
	35	#include <stdarg.h>
	36	#include <stdio.h>
	37	#include <stdlib.h>
	38	#include <string.h>
	39
	40	#include "mdwopt.h"
	41	#include "quis.h"
	42	#include "report.h"
	43
	44	/----- Static variables --------------------------------------------------/
	45
	46	static unsigned long poly = 0;
	47	static const char *guard = 0;
	48	static unsigned bits = 0;
	49	static unsigned chunk = 8;
	50	static const char *file = 0;
	51	static unsigned flags = 0;
	52	static const char *sym = 0;
	53	static const char *type = 0;
	54	static const char *inc = 0;
	55	static FILE *fp;
	56
393cf1d9	57	#define f_bogus 1u
	58	#define f_ctab 2u
	59	#define f_reverse 4u
3e7267bf	60	#define f_const 8u
b7580524	61
	62	#define BSCOL 72
	63
	64	/----- Main code ---------------------------------------------------------/
	65
	66	static unsigned long getint(const char *p, unsigned long max,
	67	const char *what)
	68	{
	69	char *pp;
	70	unsigned long x = strtoul(p, &pp, 0);
	71	if (*pp \|\| (max && x > max))
	72	die(EXIT_FAILURE, "bad %s `%s'", what, p);
	73	return (x);
	74	}
	75
	76	static void version(FILE *fp)
	77	{
	78	pquis(fp, "$, mLib version " VERSION "\n");
	79	}
	80
	81	static void usage(FILE *fp)
	82	{
3e7267bf	83	pquis(fp, "Usage: $ [-Ccr] [-o FILE] [-g GUARD] [-s SYM] [-i HEADER]\n\
d4efbcd9	84	[-t TYPE] [-b BITS] [-B BITS] [-p POLY]\n");
b7580524	85	}
	86
	87	static void help(FILE *fp)
	88	{
	89	version(fp);
	90	putc('\n', stdout);
	91	usage(fp);
	92	fputs("\n\
	93	Emits a table containing precomuted values for CRC algorithms. A number\n\
	94	of options are provided:\n\
	95	\n\
	96	-h, --help Show this help text.\n\
	97	-v, --version Show the program's version number.\n\
	98	-u, --usage Show a terse usage message.\n\
	99	\n\
	100	-c, --c-source Emit a C source file rather than a header.\n\
3e7267bf	101	-C, --const Declare table to be `const' (only useful with `-c').\n\
b7580524	102	-b, --bits=BITS Emit a table for a BITS bits-wide CRC.\n\
	103	-B, --bit-chunk=BITS Emit a table to process BITS bits at a time.\n\
	104	-p, --polynomial=POLY Use the POLY as the dividing polynomial.\n\
	105	-r, --reverse Create a `reversed' CRC table.\n\
	106	-g, --guard=GUARD Use GUARD as a multiple-inclusion guard constant.\n\
6f444bda	107	-i, --include=HEADER Include HEADER at top of C source file.\n\
6f444bda	108	-s, --symbol=SYM Name the generated table SYM.\n\
b7580524	109	-t, --type=TYPE Give the table entries type TYPE in C source.\n\
	110	-o, --output=FILE Write the output to FILE.\n\
	111	", stdout);
	112	}
	113
	114	unsigned long reflect(unsigned long x, unsigned b)
	115	{
	116	unsigned long y = 0;
	117	unsigned long xm, ym;
	118	unsigned i;
	119	if (!(flags & f_reverse))
	120	return (x);
	121	xm = 1;
c9507812	122	ym = 1u << (b - 1);
b7580524	123	for (i = 0; i < b; i++) {
	124	if (x & xm)
	125	y \|= ym;
	126	xm <<= 1;
	127	ym >>= 1;
	128	}
	129	return (y);
	130	}
	131
	132	int main(int argc, char *argv[])
	133	{
	134	unsigned n, t, nw;
	135	unsigned max, i;
	136	unsigned long mask;
	137
	138	ego(argv[0]);
	139
	140	for (;;) {
	141	static struct option opts[] = {
	142	{ "help", 0, 0, 'h' },
	143	{ "version", 0, 0, 'v' },
	144	{ "usage", 0, 0, 'u' },
	145
	146	{ "output", OPTF_ARGREQ, 0, 'o' },
	147	{ "c-source", 0, 0, 'c' },
3e7267bf	148	{ "const", 0, 0, 'C' },
b7580524	149	{ "symbol", OPTF_ARGREQ, 0, 's' },
	150	{ "type", OPTF_ARGREQ, 0, 't' },
	151	{ "include", OPTF_ARGREQ, 0, 'i' },
	152	{ "guard", OPTF_ARGREQ, 0, 'g' },
	153
	154	{ "bits", OPTF_ARGREQ, 0, 'b' },
	155	{ "bit-chunk", OPTF_ARGREQ, 0, 'B' },
	156	{ "polynomial", OPTF_ARGREQ, 0, 'p' },
	157	{ "reverse", 0, 0, 'r' },
	158
	159	{ 0, 0, 0, 0 }
	160	};
3e7267bf	161	int i = mdwopt(argc, argv, "hvu o:cCs:t:i:g: b:B:p:r", opts, 0, 0, 0);
b7580524	162
	163	if (i < 0)
	164	break;
	165	switch (i) {
	166	case 'h':
	167	help(stdout);
	168	exit(0);
	169	case 'v':
	170	version(stdout);
	171	exit(0);
	172	case 'u':
	173	usage(stdout);
	174	exit(0);
	175
	176	case 'o':
	177	file = optarg;
	178	break;
	179	case 'c':
	180	flags \|= f_ctab;
	181	break;
3e7267bf MW	182	case 'C':
	183	flags \|= f_const;
	184	break;
b7580524	185	case 's':
	186	sym = optarg;
	187	break;
	188	case 't':
	189	type = optarg;
	190	break;
	191	case 'i':
	192	inc = optarg;
	193	break;
	194	case 'g':
	195	guard = optarg;
	196	break;
	197
	198	case 'b':
	199	bits = getint(optarg, 32, "CRC width");
	200	break;
	201	case 'B':
	202	chunk = getint(optarg, 32, "chunk size");
	203	break;
	204	case 'p':
	205	poly = getint(optarg, 0xffffffff, "CRC poly");
	206	break;
	207	case 'r':
	208	flags \|= f_reverse;
	209	break;
	210
	211	default:
	212	flags \|= f_bogus;
	213	break;
	214	}
	215	}
	216	if ((flags & f_bogus) \|\| optind != argc) {
	217	usage(stderr);
	218	exit(EXIT_FAILURE);
	219	}
	220
	221	/* --- Sort out the various parameters --- */
	222
	223	if (!poly) {
	224	switch (bits) {
	225	case 16:
	226	if (flags & f_reverse)
	227	poly = 0x8408;
	228	else
	229	poly = 0x1021;
	230	break;
	231	case 32:
b7580524	232	poly = 0x04c11db7;
	233	flags \|= f_reverse;
	234	bits = 32;
	235	break;
000ba0de	236	case 0:
	237	die(EXIT_FAILURE, "no polynomial or bit width set");
	238	break;
b7580524	239	default:
	240	die(EXIT_FAILURE, "no standard polynomials for %u bits", bits);
	241	break;
	242	}
	243	}
	244
	245	if (!bits) {
	246	unsigned long x = poly;
	247	while (x > 1) {
	248	x >>= 8;
	249	bits += 8;
	250	}
	251	}
0521f473	252	nw = (bits + 3)/4;
b7580524	253
	254	if ((flags & f_ctab) && !type)
	255	type = bits > 16 ? "unsigned long" : "unsigned short";
	256
	257	/* --- Start output --- */
	258
	259	if (!file)
	260	fp = stdout;
	261	else {
	262	if (!(flags & f_ctab) && !guard) {
	263	char *p;
	264	const char *q;
	265	if ((p = malloc(strlen(file) + 1)) == 0)
	266	die(EXIT_FAILURE, "not enough memory");
	267	guard = p;
	268	for (q = file; *q; p++, q++) {
	269	if (isalnum((unsigned char)*q))
0521f473	270	p = toupper((unsigned char)q);
b7580524	271	else
	272	*p = '_';
	273	}
	274	*p++ = 0;
	275	}
	276	if ((fp = fopen(file, "w")) == 0)
	277	die(EXIT_FAILURE, "couldn't write `%s': %s", file, strerror(errno));
	278	}
	279
	280	if (!sym)
	281	sym = (flags & f_ctab) ? "crctab" : "CRC_TAB";
	282
	283	/* --- Dump out the first chunk of the file --- */
	284
	285	fprintf(fp, "\
	286	/* --c--\n\
	287	*\n\
	288	* CRC table (poly = %0*lx%s) [generated]\n\
	289	*/\n\
	290	\n",
	291	nw, poly, flags & f_reverse ? "; reversed" : "");
	292
	293	if (flags & f_ctab) {
	294	if (inc)
	295	fprintf(fp, "#include \"%s\"\n\n", inc);
3e7267bf MW	296	fprintf(fp, "%s%s %s[] = {\n",
3e7267bf MW	297	(flags&f_const) ? "const " : "", type, sym);
b7580524	298	} else {
	299	int n;
	300	if (guard)
	301	fprintf(fp, "#ifndef %s\n#define %s\n\n", guard, guard);
	302	n = fprintf(fp, "#define %s {", sym);
	303	while (n < BSCOL) {
	304	fputc('\t', fp);
	305	n = (n + 8) & ~7;
	306	}
	307	fputc('\n', fp);
	308	}
	309
	310	/* --- Sort out the line width --- */
	311
	312	n = 1;
	313	while (2 + n * (nw + 4) < BSCOL)
	314	n <<= 1;
	315	n >>= 1;
0521f473	316	max = 1 << chunk;
	317	if (n > max)
	318	n = max;
b7580524	319	t = 0;
	320	while (((1 + n * (nw + 4)) & ~7) + 8 * t < BSCOL)
	321	t++;
	322
	323	/* --- Start grinding --- */
	324
b7580524	325	mask = 0xffffffff >> (32 - bits);
	326	fputc(' ', fp);
	327	for (i = 0; i < max; i++) {
0521f473	328	unsigned long x, y, z;
b7580524	329	unsigned j;
0521f473	330	unsigned ni, nn;
	331
	332	x = reflect(i, chunk);
	333	y = 0;
	334	nn = chunk;
	335	while (nn) {
	336	ni = bits;
	337	if (ni > nn)
	338	ni = nn;
	339	z = (x >> (nn - ni)) & (0xffffffff >> (32 - ni));
	340	y ^= z << (bits - ni);
	341	for (j = 0; j < ni; j++)
	342	y = ((y << 1) ^ (y & (1 << (bits - 1)) ? poly : 0)) & mask;
	343	nn -= ni;
	344	}
	345	x = reflect(y, bits);
b7580524	346
	347	fprintf(fp, " 0x%0*lx", nw, x);
	348	if (i == max - 1) {
	349	if (!(flags & f_ctab) && ((2 + n * (nw + 4)) & ~7) + 8 * t < BSCOL)
	350	fputc('\t', fp);
	351	} else
	352	fputc(',', fp);
	353	if (i + 1 == max \|\| (i + 1)%n == 0) {
	354	if (!(flags & f_ctab)) {
	355	for (j = 0; j < t; j++)
	356	fputc('\t', fp);
	357	fputc('\\', fp);
	358	}
	359	fputc('\n', fp);
	360	if (i + 1 != max)
	361	fputc(' ', fp);
	362	}
	363	}
	364
	365	/* --- Done --- */
	366
	367	fputs(flags & f_ctab ? "};\n" : "}\n", fp);
	368	if (!(flags & f_ctab) && guard)
	369	fputs("\n#endif\n", fp);
	370
	371	return (0);
	372	}
	373
	374	/----- That's all, folks -------------------------------------------------/