chiark - git - mdw - secnet/blob - qfarith.h

   1 /* -*-c-*-
   2  *
   3  * Utilities for quick field arithmetic
   4  *
   5  * (c) 2017 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of secnet.
  11  * See README for full list of copyright holders.
  12  *
  13  * secnet is free software; you can redistribute it and/or modify it
  14  * under the terms of the GNU General Public License as published by
  15  * the Free Software Foundation; either version d of the License, or
  16  * (at your option) any later version.
  17  *
  18  * secnet is distributed in the hope that it will be useful, but
  19  * WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21  * General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU General Public License
  24  * version 3 along with secnet; if not, see
  25  * https://www.gnu.org/licenses/gpl.html.
  26  *
  27  * This file was originally part of Catacomb, but has been automatically
  28  * modified for incorporation into secnet: see `import-catacomb-crypto'
  29  * for details.
  30  *
  31  * Catacomb is free software; you can redistribute it and/or modify
  32  * it under the terms of the GNU Library General Public License as
  33  * published by the Free Software Foundation; either version 2 of the
  34  * License, or (at your option) any later version.
  35  *
  36  * Catacomb is distributed in the hope that it will be useful,
  37  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  38  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  39  * GNU Library General Public License for more details.
  40  *
  41  * You should have received a copy of the GNU Library General Public
  42  * License along with Catacomb; if not, write to the Free
  43  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  44  * MA 02111-1307, USA.
  45  */
  46
  47 #ifndef CATACOMB_QFARITH_H
  48 #define CATACOMB_QFARITH_H
  49
  50 #ifdef __cplusplus
  51   extern "C" {
  52 #endif
  53
  54 /*----- Header files ------------------------------------------------------*/
  55
  56 #include <limits.h>
  57
  58 #include "fake-mLib-bits.h"
  59 /*----- Signed integer types ----------------------------------------------*/
  60
  61 typedef int32_t int32;
  62 typedef int64_t int64;
  63 #define HAVE_INT64 1
  64
  65 /*----- General bit-hacking utilities -------------------------------------*/
  66
  67 /* Individual bits, and masks for low bits. */
  68 #define BIT(n) (1ul << (n))
  69 #define MASK(n) (BIT(n) - 1)
  70
  71 /* Arithmetic right shift.  If X is a value of type TY, and N is a
  72  * nonnegative integer, then return the value of X shifted right by N bits;
  73  * alternatively, this is floor(X/2^N).
  74  *
  75  * GCC manages to compile this into a simple shift operation if one is
  76  * available, but it's correct for all C targets.
  77  */
  78 #define ASR(ty, x, n) (((x) - (ty)((u##ty)(x)&MASK(n)))/(ty)BIT(n))
  79
  80 /*----- Constant-time utilities -------------------------------------------*/
  81
  82 /* The following have better implementations on a two's complement target. */
  83
  84 /* If we have two's complement arithmetic then masks are signed; this
  85  * avoids a switch to unsigned representation, with the consequent problem
  86  * of overflow when we convert back.
  87  */
  88 typedef int32 mask32;
  89
  90 /* Convert an unsigned mask M into a `mask32'.  This is a hairy-looking
  91  * no-op on many targets, but, given that we have two's complement
  92  * integers, it is free of arithmetic overflow.
  93  */
  94 #define FIX_MASK32(m) \
  95   ((mask32)((m)&0x7fffffffu) + (-(mask32)0x7fffffff - 1)*(((m) >> 31)&1u))
  96
  97 /* If Z is zero and M has its low 32 bits set, then copy (at least) the low
  98  * 32 bits of X to Z; if M is zero, do nothing.  Otherwise, scramble Z
  99  * unhelpfully.
 100  */
 101 #define CONDPICK(z, x, m) do { (z) |= (x)&(m); } while (0)
 102
 103 /* If M has its low 32 bits set, then return (at least) the low 32 bits of
 104  * X in Z; if M is zero, then return (at least) the low 32 bits of Y in Z.
 105  * Otherwise, return an unhelful result.
 106  */
 107 #define PICK2(x, y, m) (((x)&(m)) | ((y)&~(m)))
 108
 109 /* If M has its low 32 bits set then swap (at least) the low 32 bits of X
 110  * and Y; if M is zero, then do nothing.  Otherwise, scramble X and Y
 111  * unhelpfully.
 112  */
 113 #define CONDSWAP(x, y, m)                                               \
 114   do { mask32 t_ = ((x) ^ (y))&(m); (x) ^= t_; (y) ^= t_; } while (0)
 115
 116 /* Return zero if bit 31 of X is clear, or a mask with (at least) the low 32
 117  * bits set if bit 31 of X is set.
 118  */
 119 #define SIGN(x) (-(mask32)(((uint32)(x) >> 31)&1))
 120
 121 /* Return zero if X is zero, or a mask with (at least) the low 32 bits set if
 122  * X is nonzero.
 123  */
 124 #define NONZEROP(x) SIGN((U32(x) >> 1) - U32(x))
 125
 126 /*----- Debugging utilities -----------------------------------------------*/
 127
 128 /* Define a debugging function DUMPFN, which will dump an integer represented
 129  * modulo M.  The integer is represented as a vector of NPIECE pieces of type
 130  * PIECETY.  The pieces are assembled at possibly irregular offsets: piece i
 131  * logically has width PIECEWD(i), but may overhang the next piece.  The
 132  * pieces may be signed.  GETMOD is an expression which calculates and
 133  * returns the value of M, as an `mp *'.
 134  *
 135  * The generated function writes the value of such an integer X to the stream
 136  * FP, labelled with the string WHAT.
 137  *
 138  * The definition assumes that <stdio.h>, <catacomb/mp.h>, and
 139  * <catacomb/mptext.h> have been included.
 140  */
 141 #define DEF_FDUMP(dumpfn, piecety, piecewd, npiece, noctet, getmod)     \
 142   static void dumpfn(FILE *fp, const char *what, const piecety *x)      \
 143   {                                                                     \
 144     mpw w;                                                              \
 145     mp m, *y = MP_ZERO, *t = MP_NEW, *p;                                \
 146     octet b[noctet];                                                    \
 147     unsigned i, o;                                                      \
 148                                                                         \
 149     p = getmod;                                                         \
 150     mp_build(&m, &w, &w + 1);                                           \
 151     for (i = o = 0; i < npiece; i++) {                                  \
 152       if (x[i] >= 0) { w = x[i]; m.f &= ~MP_NEG; }                      \
 153       else { w = -x[i]; m.f |= MP_NEG; }                                \
 154       t = mp_lsl(t, &m, o);                                             \
 155       y = mp_add(y, y, t);                                              \
 156       o += piecewd(i);                                                  \
 157     }                                                                   \
 158                                                                         \
 159     fprintf(fp, "%s = <", what);                                        \
 160     for (i = 0; i < npiece; i++) {                                      \
 161       if (i) fputs(", ", fp);                                           \
 162       fprintf(fp, "%ld", (long)x[i]);                                   \
 163     }                                                                   \
 164     fputs(">\n\t= ", fp);                                               \
 165     mp_writefile(y, fp, 10);                                            \
 166     fputs("\n\t== ", fp);                                               \
 167     mp_div(0, &y, y, p);                                                \
 168     mp_writefile(y, fp, 10);                                            \
 169     fputs("\n\t= 0x", fp);                                              \
 170     mp_writefile(y, fp, 16);                                            \
 171     fputs(" (mod 2^255 - 19)\n\t= [", fp);                              \
 172     mp_storel(y, b, sizeof(b));                                         \
 173     for (i = 0; i < 32; i++) {                                          \
 174       if (i && !(i%4)) fputc(':', fp);                                  \
 175       fprintf(fp, "%02x", b[i]);                                        \
 176     }                                                                   \
 177     fputs("]\n", fp);                                                   \
 178     mp_drop(y); mp_drop(p); mp_drop(t);                                 \
 179   }
 180
 181 /*----- That's all, folks -------------------------------------------------*/
 182
 183 #ifdef __cplusplus
 184   }
 185 #endif
 186
 187 #endif