mdw@git.distorted.org.uk Git - secnet/blob - qfarith.h

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