--- /dev/null
+/* -*-c-*-
+ *
+ * Utilities for quick field arithmetic
+ *
+ * (c) 2017 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.
+ */
+
+#ifndef CATACOMB_QFARITH_H
+#define CATACOMB_QFARITH_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <limits.h>
+
+#include <mLib/bits.h>
+
+/*----- Signed integer types ----------------------------------------------*/
+
+/* See if we can find a suitable 64-bit or wider type. Don't bother if we
+ * don't have a corresponding unsigned type, because we really need both.
+ */
+#ifdef HAVE_UINT64
+# if INT_MAX >> 31 == 0xffffffff
+# define HAVE_INT64
+ typedef int int64;
+# elif LONG_MAX >> 31 == 0xffffffff
+# define HAVE_INT64
+ typedef long int64;
+# elif defined(LLONG_MAX)
+# define HAVE_INT64
+ MLIB_BITS_EXTENSION typedef long long int64;
+# endif
+#endif
+
+/* Choose suitable 32- and 16-bit types. */
+#if INT_MAX >= 0x7fffffff
+ typedef int int32;
+#else
+ typedef long int32;
+#endif
+
+typedef short int16;
+
+/*----- 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. */
+#ifdef NEG_TWOC
+
+ /* 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)
+#else
+
+ /* We don't have two's complement arithmetic. We can't use bithacking at
+ * all: if we try to hack on the bits of signed numbers we'll come unstuck
+ * when we hit the other representation of zero; and if we switch to
+ * unsigned arithmetic then we'll have overflow when we try to convert a
+ * negative number back. So fall back to simple arithmetic.
+ */
+ typedef uint32 mask32;
+
+ /* Convert an unsigned mask M into a `mask32'. Our masks are unsigned, so
+ * this does nothing.
+ */
+# define FIX_MASK32(m) ((mask32)(m))
+
+ /* 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)*(int)((unsigned)(m)&1u); } 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)*(int)((unsigned)(m)&1u) + (y)*(int)(1 - ((unsigned)(m)&1u)))
+
+ /* 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 { \
+ int32 x_ = PICK2((y), (x), (m)), y_ = PICK2((x), (y), (m)); \
+ (x) = x_; (y) = y_; \
+ } while (0)
+#endif
+
+/* 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 <stdio.h>, <catacomb/mp.h>, and
+ * <catacomb/mptext.h> 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
~mdw / secnet / blobdiff