From 7eaaecf58694345b4e40db9981c0c2ac0f728378 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Tue, 16 Jan 2007 22:09:36 +0000 Subject: [PATCH] genlimits: New program to generate useful limit MPs for C types. Also another fix to mpint.h, to suppress pointless leading zero workds. --- Makefile.m4 | 40 ++++++--- genlimits.c | 282 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ mpint.h | 4 +- 3 files changed, 311 insertions(+), 15 deletions(-) create mode 100644 genlimits.c diff --git a/Makefile.m4 b/Makefile.m4 index a1a6730..6f75ebc 100644 --- a/Makefile.m4 +++ b/Makefile.m4 @@ -89,7 +89,8 @@ _(square) _(rijndael) _(whirlpool) dnl _(safer) _(mars) _(tiger) dnl _(gfshare) _(gfx-sqr)') -autoheaders: addsuffix(`gen_tables', `-tab.h') primetab.h mptypes.h +autoheaders: \ + addsuffix(`gen_tables', `-tab.h') primetab.h mptypes.h mplimits.h define(`emit', ` _item`'-tab.h: _item`'-mktab$(EXEEXT) ./_item`'-mktab >_item`'-tab.h.new @@ -101,11 +102,18 @@ primetab.c: genprimes$(EXEEXT) ./genprimes -h primetab.h -c primetab.c \ -s CATACOMB_PRIMETAB_H -n 256 \ -t "unsigned short" -i primetab -archinclude_HEADERS = mptypes.h +archinclude_HEADERS = mptypes.h mplimits.h mptypes.h: mptypes$(EXEEXT) ./mptypes >mptypes.h.new mv mptypes.h.new mptypes.h +mplimits.h: genlimits$(EXEEXT) + ./genlimits h >mplimits.h.new + mv mplimits.h.new mplimits.h +mplimits.c: genlimits$(EXEEXT) + ./genlimits c >mplimits.c.new + mv mplimits.c.new mplimits.c + ectab.c: ectab.in ec-gentab.awk mpdump$(EXEEXT) $(srcdir)/ec-gentab.awk <$(srcdir)/ectab.in >ectab.c.new mv ectab.c.new ectab.c @@ -174,11 +182,16 @@ pkginclude_HEADERS = \ addsuffix(`cipher_modes', `-def.h') \ addsuffix(`hash_modes', `-def.h') crc32.h +define(`MP_BASE', + `mpx.c mpx-kmul.c mpx-ksqr.c mpscan.c mparena.c \ + mp-misc.c mp-mem.c mp-const.c mp-arith.c mp-io.c \ + mptext.c mptext-string.c') + define(`MP_SOURCES', - `mpx.c mpx-kmul.c mpx-ksqr.c mpscan.c mparena.c qdparse.c \ - mp-misc.c mp-mem.c mp-const.c mp-io.c mp-arith.c mp-test.c \ + `qdparse.c \ + mp-test.c mplimits.c \ mp-sqrt.c mp-gcd.c mp-jacobi.c mp-modsqrt.c mp-exp.c \ - mpint.c mptext.c mptext-file.c mptext-string.c mptext-dstr.c \ + mpint.c mptext-file.c mptext-dstr.c \ mptext-len.c \ exp.c mpcrt.c mpmul.c mprand.c \ mpbarrett.c mpbarrett-exp.c mpbarrett-mexp.c mpbarrett-exp.h \ @@ -223,7 +236,7 @@ libcatacomb_la_SOURCES = \ passphrase.c pixie-common.c lmem.c \ tlsprf.c sslprf.c \ gfshare.c \ - MP_SOURCES karatsuba.h \ + MP_BASE MP_SOURCES karatsuba.h \ gciphertab.c ghashtab.c gmactab.c \ des-base.c des-base.h \ desx-tab.h \ @@ -258,7 +271,7 @@ bin_PROGRAMS = \ noinst_LIBRARIES = libcatcrypt.a bin_SCRIPTS = catacomb-config xpixie noinst_PROGRAMS = \ - genprimes mptypes serpent-check bittest mpdump \ + genprimes mptypes genlimits serpent-check bittest mpdump \ perftest \ addsuffix(`gen_tables', `-mktab') LDADD = libcatcrypt.a libcatacomb.la @@ -267,9 +280,10 @@ define(`LIBCAT_SRC', `cc.h getdate.h dnl cc-sig.c cc-subcmd.c cc-enc.c cc-kem.c cc-list.c') libcatcrypt_a_SOURCES = LIBCAT_SRC getdate.y -patsubst(MP_SOURCES, `\.c\>', `.lo') dsig.o keyutil.o rspit.o \ +patsubst(MP_BASE MP_SOURCES, `\.c\>', `.lo') dsig.o keyutil.o rspit.o \ patsubst(LIBCAT_SRC, `\.c\>', `.o'): \ mptypes.h primetab.h +patsubst(MP_SOURCES, `\.c\>', `.lo'): mplimits.h dsig_SOURCES = dsig.c cookie_SOURCES = cookie.c @@ -301,11 +315,11 @@ genprimes_LDADD = mptypes_SOURCES = mptypes.c mptypes_LDADD = -mpdump_SOURCES = \ - mpdump.c \ - mpx.c mpx-kmul.c mpx-ksqr.c mpscan.c mparena.c \ - mp-misc.c mp-mem.c mp-const.c mp-arith.c mp-io.c \ - mptext.c mptext-string.c +genlimits_SOURCES = genlimits.c MP_BASE +genlimits_LDADD = +genlimits_CFLAGS = $(AM_CFLAGS) + +mpdump_SOURCES = mpdump.c MP_BASE mpdump_LDADD = mpdump_CFLAGS = $(AM_CFLAGS) diff --git a/genlimits.c b/genlimits.c new file mode 100644 index 0000000..fc2d319 --- /dev/null +++ b/genlimits.c @@ -0,0 +1,282 @@ +/* -*-c-*- + * + * $Id$ + * + * Generate limit MPs for C types + * + * (c) 2006 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb 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. + * + * Catacomb 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 Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Header files ------------------------------------------------------*/ + +#define _GNU_SOURCE +#include +#include +#include +#include + +#if __STDC_VERSION__ >= 199900l +# include +# include +#endif + +#include "mp.h" +#include "mpint.h" + +/*----- Data types --------------------------------------------------------*/ + +/* --- Hack for GCC --- * + * + * WG14 in their infinite wisdom decided not to use the GCC constant name. + */ + +#if __GNUC__ > 2 || (__GNUC__ == 2 && __GNUC_MINOR__ >= 91) +# define EXT __extension__ +#else +# define EXT +#endif + +#if defined(LONG_LONG_MIN) && !defined(LLONG_MIN) +# define LLONG_MIN EXT LONG_LONG_MIN +#endif + +#if defined(LONG_LONG_MAX) && !defined(LLONG_MAX) +# define LLONG_MAX EXT LONG_LONG_MAX +#endif + +#if defined(ULONG_LONG_MAX) && !defined(ULLONG_MAX) +# define ULLONG_MAX EXT ULONG_LONG_MAX +#endif + +/* --- Choose the largest integer type --- */ + +#if defined(INTMAX_MAX) + typedef intmax_t imax; +#elif defined(LLONG_MAX) + EXT typedef long long imax; +#else + typedef long imax; +#endif + +#if defined(UINTMAX_MAX) + typedef uintmax_t umax; +#elif defined(ULLONG_MAX) + EXT typedef unsigned long long umax; +#else + typedef unsigned long umax; +#endif + +/*----- Main code ---------------------------------------------------------*/ + +#define TABSZ 64 + +enum { NEG, POS, NSIGN }; + +umax cmap[TABSZ]; +int gmap[TABSZ][NSIGN]; +struct { int g, s; } qmap[TABSZ]; +int dumpp = 0; + +static int n, q; + +static void dump(mp *x) +{ + int i, w, n; + + fputs(" ", stdout); + w = (MPW_BITS + 3)/4; + n = 1; + while (2 + 2 * n * (4 + w) < 72) n <<= 1; + i = 0; + for (;;) { + printf("0x%0*x", w, x->v[i]); + i++; + if (i >= MP_LEN(x)) break; + fputs(",", stdout); + if (i % n) fputs(" ", stdout); else fputs("\n ", stdout); + } + fputs("\n", stdout); +} + +static void doemit(umax c, int s, int *gg, int *qq) +{ + int i; + mp *x = MP_NEW; + + for (i = 0; i < n; i++) { + if (cmap[i] == c) + goto found; + } + + assert(i < TABSZ); + n = i + 1; + cmap[i] = c; + gmap[i][POS] = gmap[i][NEG] = -1; + if (dumpp) { + MP_FROMINT(x, umax, c); + printf("static mpw guts_%d[] = {\n", q); + dump(x); + fputs("};\n\n", stdout); + MP_DROP(x); + } + +found: + *gg = i; + if (gmap[i][s] < 0) { + assert(q < TABSZ); + gmap[i][s] = q; + qmap[q].g = i; + qmap[q].s = s; + q++; + } + *qq = gmap[i][s]; +} + +static void emit(imax c, int *gg, int *qq) +{ + umax uc; + int s; + + if (c >= 0) { uc = c; s = POS; } + else { uc = -c; s = NEG; } + doemit(uc, s, gg, qq); +} + +static void uemit(umax c, int *gg, int *qq) { doemit(c, POS, gg, qq); } + +struct { + const char *name; + imax min; + umax max; + int gmin, gmax; + int qmin, qmax; +} tab[] = { + { "SCHAR", SCHAR_MIN, SCHAR_MAX }, + { "CHAR", CHAR_MIN, CHAR_MAX }, + { "UCHAR", 0, UCHAR_MAX }, + { "UINT8", 0, 0xff }, + { "SHRT", SHRT_MIN, SHRT_MAX }, + { "USHRT", 0, USHRT_MAX }, + { "UINT16", 0, 0xffff }, + { "INT", INT_MIN, INT_MAX }, + { "UINT", 0, UINT_MAX }, + { "LONG", LONG_MIN, LONG_MAX }, + { "ULONG", 0, ULONG_MAX }, + { "UINT32", 0, 0xffffffff }, +#ifdef LLONG_MAX + { "LLONG", LLONG_MIN, LLONG_MAX }, + { "ULLONG", 0, ULLONG_MAX }, +#endif + { "SIZET", 0, ~(size_t)0 }, + { 0 } +}; + +static void dogen(void) +{ + int i; + + for (i = 0; tab[i].name; i++) { + if (tab[i].min) + emit(tab[i].min, &tab[i].gmin, &tab[i].qmin); + uemit(tab[i].max, &tab[i].gmax, &tab[i].qmax); + } +} + +static void cgen(void) +{ + int i; + + fputs("\ +/* -*-c-*-\n\ + *\n\ + * C integer limits [generated]\n\ + */\n\ +\n\ +#include \"mplimits.h\"\n\ +\n\ +#define N(x) (sizeof(x)/sizeof(*x))\n\ +#define MPpos(x) { x, x + N(x), N(x), 0, MP_CONST, 0 }\n\ +#define MPneg(x) { x, x + N(x), N(x), 0, MP_CONST|MP_NEG, 0 }\n\ +\n", + stdout); + dumpp = 1; + dogen(); + + fputs("mp mp_limits[] = {\n", stdout); + for (i = 0; i < q; i++) + printf(" MP%s(guts_%d),\n", qmap[i].s ? "pos" : "neg", qmap[i].g); + fputs("};\n", stdout); +} + +static void hgen(void) +{ + int i; + + fputs("\ +/* -*-c-*-\n\ + *\n\ + * C integer limits [generated]\n\ + */\n\ +\n\ +#ifndef CATACOMB_MPLIMITS_H\n\ +#define CATACOMB_MPLIMITS_H\n\ +\n\ +#ifndef CATACOMB_MP_H\n\ +# include \"mp.h\"\n\ +#endif\n\ +\n\ +extern mp mp_limits[];\n\ +\n", + stdout); + dogen(); + + for (i = 0; tab[i].name; i++) { + if (tab[i].min) { + printf("#define MP_%s_MIN (&mp_limits[%d])\n", + tab[i].name, gmap[tab[i].qmin][NEG]); + } + printf("#define MP_%s_MAX (&mp_limits[%d])\n", + tab[i].name, gmap[tab[i].qmax][POS]); + } + fputs("\n#endif\n", stdout); +} + +int main(int argc, char *argv[]) +{ + const char *what = argc == 2 ? argv[1] : ""; + + switch (what[0]) { + case 'c': cgen(); break; + case 'h': hgen(); break; + default: + fprintf(stderr, "unknown action `%s'\n", what); + exit(1); + } + if (fflush(stdout) || fclose(stdout)) { + fprintf(stderr, "error writing output: %s\n", strerror(errno)); + exit(1); + } + return (0); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/mpint.h b/mpint.h index e44c39e..3bfe36a 100644 --- a/mpint.h +++ b/mpint.h @@ -70,7 +70,7 @@ MP_ENSURE(_d, _sz); \ } \ _d->v[_o++] = MPW(_i); \ - if (_i < MPW_MAX) \ + if (_i <= MPW_MAX) \ break; \ else \ _i /= (type)MPW_MAX + 1; \ @@ -83,7 +83,7 @@ MP_ENSURE(_d, _sz); \ } \ _d->v[_o++] = MPW(-_i); \ - if (_i > -MPW_MAX) \ + if (_i >= -MPW_MAX) \ break; \ else \ _i /= (type)MPW_MAX + 1; \ -- 2.11.0