+++ /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