X-Git-Url: https://git.distorted.org.uk/~mdw/secnet/blobdiff_plain/ae8cd973b817f81c075ab20e84d3239125146f24..8a7654a695e8ecdc8c14dced445839a7a7e6a8ca:/qfarith.h diff --git a/qfarith.h b/qfarith.h new file mode 100644 index 0000000..f41aa95 --- /dev/null +++ b/qfarith.h @@ -0,0 +1,187 @@ +/* -*-c-*- + * + * Utilities for quick field arithmetic + * + * (c) 2017 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of secnet. + * See README for full list of copyright holders. + * + * secnet is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version d of the License, or + * (at your option) any later version. + * + * secnet 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 + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * version 3 along with secnet; if not, see + * https://www.gnu.org/licenses/gpl.html. + * + * This file was originally part of Catacomb, but has been automatically + * modified for incorporation into secnet: see `import-catacomb-crypto' + * for details. + * + * 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. + */ + +#ifndef CATACOMB_QFARITH_H +#define CATACOMB_QFARITH_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include + +#include "fake-mLib-bits.h" +/*----- Signed integer types ----------------------------------------------*/ + +typedef int32_t int32; +typedef int64_t int64; +#define HAVE_INT64 1 + +/*----- General bit-hacking utilities -------------------------------------*/ + +/* Individual bits, and masks for low bits. */ +#define BIT(n) (1ul << (n)) +#define MASK(n) (BIT(n) - 1) + +/* Arithmetic right shift. If X is a value of type TY, and N is a + * nonnegative integer, then return the value of X shifted right by N bits; + * alternatively, this is floor(X/2^N). + * + * GCC manages to compile this into a simple shift operation if one is + * available, but it's correct for all C targets. + */ +#define ASR(ty, x, n) (((x) - (ty)((u##ty)(x)&MASK(n)))/(ty)BIT(n)) + +/*----- Constant-time utilities -------------------------------------------*/ + +/* The following have better implementations on a two's complement target. */ + +/* If we have two's complement arithmetic then masks are signed; this + * avoids a switch to unsigned representation, with the consequent problem + * of overflow when we convert back. + */ +typedef int32 mask32; + +/* Convert an unsigned mask M into a `mask32'. This is a hairy-looking + * no-op on many targets, but, given that we have two's complement + * integers, it is free of arithmetic overflow. + */ +#define FIX_MASK32(m) \ + ((mask32)((m)&0x7fffffffu) + (-(mask32)0x7fffffff - 1)*(((m) >> 31)&1u)) + +/* If Z is zero and M has its low 32 bits set, then copy (at least) the low + * 32 bits of X to Z; if M is zero, do nothing. Otherwise, scramble Z + * unhelpfully. + */ +#define CONDPICK(z, x, m) do { (z) |= (x)&(m); } while (0) + +/* If M has its low 32 bits set, then return (at least) the low 32 bits of + * X in Z; if M is zero, then return (at least) the low 32 bits of Y in Z. + * Otherwise, return an unhelful result. + */ +#define PICK2(x, y, m) (((x)&(m)) | ((y)&~(m))) + +/* If M has its low 32 bits set then swap (at least) the low 32 bits of X + * and Y; if M is zero, then do nothing. Otherwise, scramble X and Y + * unhelpfully. + */ +#define CONDSWAP(x, y, m) \ + do { mask32 t_ = ((x) ^ (y))&(m); (x) ^= t_; (y) ^= t_; } while (0) + +/* Return zero if bit 31 of X is clear, or a mask with (at least) the low 32 + * bits set if bit 31 of X is set. + */ +#define SIGN(x) (-(mask32)(((uint32)(x) >> 31)&1)) + +/* Return zero if X is zero, or a mask with (at least) the low 32 bits set if + * X is nonzero. + */ +#define NONZEROP(x) SIGN((U32(x) >> 1) - U32(x)) + +/*----- Debugging utilities -----------------------------------------------*/ + +/* Define a debugging function DUMPFN, which will dump an integer represented + * modulo M. The integer is represented as a vector of NPIECE pieces of type + * PIECETY. The pieces are assembled at possibly irregular offsets: piece i + * logically has width PIECEWD(i), but may overhang the next piece. The + * pieces may be signed. GETMOD is an expression which calculates and + * returns the value of M, as an `mp *'. + * + * The generated function writes the value of such an integer X to the stream + * FP, labelled with the string WHAT. + * + * The definition assumes that , , and + * have been included. + */ +#define DEF_FDUMP(dumpfn, piecety, piecewd, npiece, noctet, getmod) \ + static void dumpfn(FILE *fp, const char *what, const piecety *x) \ + { \ + mpw w; \ + mp m, *y = MP_ZERO, *t = MP_NEW, *p; \ + octet b[noctet]; \ + unsigned i, o; \ + \ + p = getmod; \ + mp_build(&m, &w, &w + 1); \ + for (i = o = 0; i < npiece; i++) { \ + if (x[i] >= 0) { w = x[i]; m.f &= ~MP_NEG; } \ + else { w = -x[i]; m.f |= MP_NEG; } \ + t = mp_lsl(t, &m, o); \ + y = mp_add(y, y, t); \ + o += piecewd(i); \ + } \ + \ + fprintf(fp, "%s = <", what); \ + for (i = 0; i < npiece; i++) { \ + if (i) fputs(", ", fp); \ + fprintf(fp, "%ld", (long)x[i]); \ + } \ + fputs(">\n\t= ", fp); \ + mp_writefile(y, fp, 10); \ + fputs("\n\t== ", fp); \ + mp_div(0, &y, y, p); \ + mp_writefile(y, fp, 10); \ + fputs("\n\t= 0x", fp); \ + mp_writefile(y, fp, 16); \ + fputs(" (mod 2^255 - 19)\n\t= [", fp); \ + mp_storel(y, b, sizeof(b)); \ + for (i = 0; i < 32; i++) { \ + if (i && !(i%4)) fputc(':', fp); \ + fprintf(fp, "%02x", b[i]); \ + } \ + fputs("]\n", fp); \ + mp_drop(y); mp_drop(p); mp_drop(t); \ + } + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif