3 * Utilities for quick field arithmetic
5 * (c) 2017 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 #ifndef CATACOMB_QFARITH_H
29 #define CATACOMB_QFARITH_H
35 /*----- Header files ------------------------------------------------------*/
39 #include <mLib/bits.h>
41 /*----- Signed integer types ----------------------------------------------*/
43 /* See if we can find a suitable 64-bit or wider type. Don't bother if we
44 * don't have a corresponding unsigned type, because we really need both.
47 # if INT_MAX >> 31 == 0xffffffff
50 # elif LONG_MAX >> 31 == 0xffffffff
53 # elif defined(LLONG_MAX)
55 MLIB_BITS_EXTENSION
typedef long long int64
;
59 /* Choose suitable 32- and 16-bit types. */
60 #if INT_MAX >= 0x7fffffff
68 /*----- General bit-hacking utilities -------------------------------------*/
70 /* Individual bits, and masks for low bits. */
71 #define BIT(n) (1ul << (n))
72 #define MASK(n) (BIT(n) - 1)
74 /* Arithmetic right shift. If X is a value of type TY, and N is a
75 * nonnegative integer, then return the value of X shifted right by N bits;
76 * alternatively, this is floor(X/2^N).
78 * GCC manages to compile this into a simple shift operation if one is
79 * available, but it's correct for all C targets.
81 #define ASR(ty, x, n) (((x) - (ty)((u##ty)(x)&MASK(n)))/(ty)BIT(n))
83 /*----- Constant-time utilities -------------------------------------------*/
85 /* The following have better implementations on a two's complement target. */
88 /* If we have two's complement arithmetic then masks are signed; this
89 * avoids a switch to unsigned representation, with the consequent problem
90 * of overflow when we convert back.
94 /* Convert an unsigned mask M into a `mask32'. This is a hairy-looking
95 * no-op on many targets, but, given that we have two's complement
96 * integers, it is free of arithmetic overflow.
98 # define FIX_MASK32(m) \
99 ((mask32)((m)&0x7fffffffu) + (-(mask32)0x7fffffff - 1)*(((m) >> 31)&1u))
101 /* If Z is zero and M has its low 32 bits set, then copy (at least) the low
102 * 32 bits of X to Z; if M is zero, do nothing. Otherwise, scramble Z
105 # define CONDPICK(z, x, m) do { (z) |= (x)&(m); } while (0)
107 /* If M has its low 32 bits set, then return (at least) the low 32 bits of
108 * X in Z; if M is zero, then return (at least) the low 32 bits of Y in Z.
109 * Otherwise, return an unhelful result.
111 # define PICK2(x, y, m) (((x)&(m)) | ((y)&~(m)))
113 /* If M has its low 32 bits set then swap (at least) the low 32 bits of X
114 * and Y; if M is zero, then do nothing. Otherwise, scramble X and Y
117 # define CONDSWAP(x, y, m) \
118 do { mask32 t_ = ((x) ^ (y))&(m); (x) ^= t_; (y) ^= t_; } while (0)
121 /* We don't have two's complement arithmetic. We can't use bithacking at
122 * all: if we try to hack on the bits of signed numbers we'll come unstuck
123 * when we hit the other representation of zero; and if we switch to
124 * unsigned arithmetic then we'll have overflow when we try to convert a
125 * negative number back. So fall back to simple arithmetic.
127 typedef uint32 mask32
;
129 /* Convert an unsigned mask M into a `mask32'. Our masks are unsigned, so
132 # define FIX_MASK32(m) ((mask32)(m))
134 /* If Z is zero and M has its low 32 bits set, then copy (at least) the low
135 * 32 bits of X to Z; if M is zero, do nothing. Otherwise, scramble Z
138 # define CONDPICK(z, x, m) \
139 do { (z) += (x)*(int)((unsigned)(m)&1u); } while (0)
141 /* If M has its low 32 bits set, then return (at least) the low 32 bits of
142 * X in Z; if M is zero, then return (at least) the low 32 bits of Y in Z.
143 * Otherwise, return an unhelful result.
145 # define PICK2(x, y, m) \
146 ((x)*(int)((unsigned)(m)&1u) + (y)*(int)(1 - ((unsigned)(m)&1u)))
148 /* If M has its low 32 bits set then swap (at least) the low 32 bits of X
149 * and Y; if M is zero, then do nothing. Otherwise, scramble X and Y
152 # define CONDSWAP(x, y, m) do { \
153 int32 x_ = PICK2((y), (x), (m)), y_ = PICK2((x), (y), (m)); \
154 (x) = x_; (y) = y_; \
158 /* Return zero if bit 31 of X is clear, or a mask with (at least) the low 32
159 * bits set if bit 31 of X is set.
161 #define SIGN(x) (-(mask32)(((uint32)(x) >> 31)&1))
163 /* Return zero if X is zero, or a mask with (at least) the low 32 bits set if
166 #define NONZEROP(x) SIGN((U32(x) >> 1) - U32(x))
168 /*----- Debugging utilities -----------------------------------------------*/
170 /* Define a debugging function DUMPFN, which will dump an integer represented
171 * modulo M. The integer is represented as a vector of NPIECE pieces of type
172 * PIECETY. The pieces are assembled at possibly irregular offsets: piece i
173 * logically has width PIECEWD(i), but may overhang the next piece. The
174 * pieces may be signed. GETMOD is an expression which calculates and
175 * returns the value of M, as an `mp *'.
177 * The generated function writes the value of such an integer X to the stream
178 * FP, labelled with the string WHAT.
180 * The definition assumes that <stdio.h>, <catacomb/mp.h>, and
181 * <catacomb/mptext.h> have been included.
183 #define DEF_FDUMP(dumpfn, piecety, piecewd, npiece, noctet, getmod) \
184 static void dumpfn(FILE *fp, const char *what, const piecety *x) \
187 mp m, *y = MP_ZERO, *t = MP_NEW, *p; \
192 mp_build(&m, &w, &w + 1); \
193 for (i = o = 0; i < npiece; i++) { \
194 if (x[i] >= 0) { w = x[i]; m.f &= ~MP_NEG; } \
195 else { w = -x[i]; m.f |= MP_NEG; } \
196 t = mp_lsl(t, &m, o); \
197 y = mp_add(y, y, t); \
201 fprintf(fp, "%s = <", what); \
202 for (i = 0; i < npiece; i++) { \
203 if (i) fputs(", ", fp); \
204 fprintf(fp, "%ld", (long)x[i]); \
206 fputs(">\n\t= ", fp); \
207 mp_writefile(y, fp, 10); \
208 fputs("\n\t== ", fp); \
209 mp_div(0, &y, y, p); \
210 mp_writefile(y, fp, 10); \
211 fputs("\n\t= 0x", fp); \
212 mp_writefile(y, fp, 16); \
213 fputs(" (mod 2^255 - 19)\n\t= [", fp); \
214 mp_storel(y, b, sizeof(b)); \
215 for (i = 0; i < 32; i++) { \
216 if (i && !(i%4)) fputc(':', fp); \
217 fprintf(fp, "%02x", b[i]); \
220 mp_drop(y); mp_drop(p); mp_drop(t); \
223 /*----- That's all, folks -------------------------------------------------*/