progs/perftest.c: Use from Glibc syscall numbers.

[catacomb] / math / qfarith.h

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