crypto/ec/curve448/arch_ref64/f_impl.c

   1 /* Copyright (c) 2014 Cryptography Research, Inc.
   2  * Released under the MIT License.  See LICENSE.txt for license information.
   3  */
   4
   5 #include "f_field.h"
   6
   7 void gf_mul (gf_s *__restrict__ cs, const gf as, const gf bs) {
   8     const uint64_t *a = as->limb, *b = bs->limb;
   9     uint64_t *c = cs->limb;
  10
  11     __uint128_t accum0 = 0, accum1 = 0, accum2;
  12     uint64_t mask = (1ull<<56) - 1;
  13
  14     uint64_t aa[4], bb[4], bbb[4];
  15
  16     unsigned int i;
  17     for (i=0; i<4; i++) {
  18         aa[i]  = a[i] + a[i+4];
  19         bb[i]  = b[i] + b[i+4];
  20         bbb[i] = bb[i] + b[i+4];
  21     }
  22
  23     int I_HATE_UNROLLED_LOOPS = 0;
  24
  25     if (I_HATE_UNROLLED_LOOPS) {
  26         /* The compiler probably won't unroll this,
  27          * so it's like 80% slower.
  28          */
  29         for (i=0; i<4; i++) {
  30             accum2 = 0;
  31
  32             unsigned int j;
  33             for (j=0; j<=i; j++) {
  34                 accum2 += widemul(a[j],   b[i-j]);
  35                 accum1 += widemul(aa[j], bb[i-j]);
  36                 accum0 += widemul(a[j+4], b[i-j+4]);
  37             }
  38             for (; j<4; j++) {
  39                 accum2 += widemul(a[j],   b[i-j+8]);
  40                 accum1 += widemul(aa[j], bbb[i-j+4]);
  41                 accum0 += widemul(a[j+4], bb[i-j+4]);
  42             }
  43
  44             accum1 -= accum2;
  45             accum0 += accum2;
  46
  47             c[i]   = ((uint64_t)(accum0)) & mask;
  48             c[i+4] = ((uint64_t)(accum1)) & mask;
  49
  50             accum0 >>= 56;
  51             accum1 >>= 56;
  52         }
  53     } else {
  54         accum2  = widemul(a[0],  b[0]);
  55         accum1 += widemul(aa[0], bb[0]);
  56         accum0 += widemul(a[4],  b[4]);
  57
  58         accum2 += widemul(a[1],  b[7]);
  59         accum1 += widemul(aa[1], bbb[3]);
  60         accum0 += widemul(a[5],  bb[3]);
  61
  62         accum2 += widemul(a[2],  b[6]);
  63         accum1 += widemul(aa[2], bbb[2]);
  64         accum0 += widemul(a[6],  bb[2]);
  65
  66         accum2 += widemul(a[3],  b[5]);
  67         accum1 += widemul(aa[3], bbb[1]);
  68         accum0 += widemul(a[7],  bb[1]);
  69
  70         accum1 -= accum2;
  71         accum0 += accum2;
  72
  73         c[0] = ((uint64_t)(accum0)) & mask;
  74         c[4] = ((uint64_t)(accum1)) & mask;
  75
  76         accum0 >>= 56;
  77         accum1 >>= 56;
  78
  79         accum2  = widemul(a[0],  b[1]);
  80         accum1 += widemul(aa[0], bb[1]);
  81         accum0 += widemul(a[4],  b[5]);
  82
  83         accum2 += widemul(a[1],  b[0]);
  84         accum1 += widemul(aa[1], bb[0]);
  85         accum0 += widemul(a[5],  b[4]);
  86
  87         accum2 += widemul(a[2],  b[7]);
  88         accum1 += widemul(aa[2], bbb[3]);
  89         accum0 += widemul(a[6],  bb[3]);
  90
  91         accum2 += widemul(a[3],  b[6]);
  92         accum1 += widemul(aa[3], bbb[2]);
  93         accum0 += widemul(a[7],  bb[2]);
  94
  95         accum1 -= accum2;
  96         accum0 += accum2;
  97
  98         c[1] = ((uint64_t)(accum0)) & mask;
  99         c[5] = ((uint64_t)(accum1)) & mask;
 100
 101         accum0 >>= 56;
 102         accum1 >>= 56;
 103
 104         accum2  = widemul(a[0],  b[2]);
 105         accum1 += widemul(aa[0], bb[2]);
 106         accum0 += widemul(a[4],  b[6]);
 107
 108         accum2 += widemul(a[1],  b[1]);
 109         accum1 += widemul(aa[1], bb[1]);
 110         accum0 += widemul(a[5],  b[5]);
 111
 112         accum2 += widemul(a[2],  b[0]);
 113         accum1 += widemul(aa[2], bb[0]);
 114         accum0 += widemul(a[6],  b[4]);
 115
 116         accum2 += widemul(a[3],  b[7]);
 117         accum1 += widemul(aa[3], bbb[3]);
 118         accum0 += widemul(a[7],  bb[3]);
 119
 120         accum1 -= accum2;
 121         accum0 += accum2;
 122
 123         c[2] = ((uint64_t)(accum0)) & mask;
 124         c[6] = ((uint64_t)(accum1)) & mask;
 125
 126         accum0 >>= 56;
 127         accum1 >>= 56;
 128
 129         accum2  = widemul(a[0],  b[3]);
 130         accum1 += widemul(aa[0], bb[3]);
 131         accum0 += widemul(a[4],  b[7]);
 132
 133         accum2 += widemul(a[1],  b[2]);
 134         accum1 += widemul(aa[1], bb[2]);
 135         accum0 += widemul(a[5],  b[6]);
 136
 137         accum2 += widemul(a[2],  b[1]);
 138         accum1 += widemul(aa[2], bb[1]);
 139         accum0 += widemul(a[6],  b[5]);
 140
 141         accum2 += widemul(a[3],  b[0]);
 142         accum1 += widemul(aa[3], bb[0]);
 143         accum0 += widemul(a[7],  b[4]);
 144
 145         accum1 -= accum2;
 146         accum0 += accum2;
 147
 148         c[3] = ((uint64_t)(accum0)) & mask;
 149         c[7] = ((uint64_t)(accum1)) & mask;
 150
 151         accum0 >>= 56;
 152         accum1 >>= 56;
 153     } /* !I_HATE_UNROLLED_LOOPS */
 154
 155     accum0 += accum1;
 156     accum0 += c[4];
 157     accum1 += c[0];
 158     c[4] = ((uint64_t)(accum0)) & mask;
 159     c[0] = ((uint64_t)(accum1)) & mask;
 160
 161     accum0 >>= 56;
 162     accum1 >>= 56;
 163
 164     c[5] += ((uint64_t)(accum0));
 165     c[1] += ((uint64_t)(accum1));
 166 }
 167
 168 void gf_mulw_unsigned (gf_s *__restrict__ cs, const gf as, uint32_t b) {
 169     const uint64_t *a = as->limb;
 170     uint64_t *c = cs->limb;
 171
 172     __uint128_t accum0 = 0, accum4 = 0;
 173     uint64_t mask = (1ull<<56) - 1;
 174
 175     int i;
 176     for (i=0; i<4; i++) {
 177         accum0 += widemul(b, a[i]);
 178         accum4 += widemul(b, a[i+4]);
 179         c[i]   = accum0 & mask; accum0 >>= 56;
 180         c[i+4] = accum4 & mask; accum4 >>= 56;
 181     }
 182
 183     accum0 += accum4 + c[4];
 184     c[4] = accum0 & mask;
 185     c[5] += accum0 >> 56;
 186
 187     accum4 += c[0];
 188     c[0] = accum4 & mask;
 189     c[1] += accum4 >> 56;
 190 }
 191
 192 void gf_sqr (gf_s *__restrict__ cs, const gf as) {
 193     const uint64_t *a = as->limb;
 194     uint64_t *c = cs->limb;
 195
 196     __uint128_t accum0 = 0, accum1 = 0, accum2;
 197     uint64_t mask = (1ull<<56) - 1;
 198
 199     uint64_t aa[4];
 200
 201     /* For some reason clang doesn't vectorize this without prompting? */
 202     unsigned int i;
 203     for (i=0; i<4; i++) {
 204         aa[i] = a[i] + a[i+4];
 205     }
 206
 207     accum2  = widemul(a[0],a[3]);
 208     accum0  = widemul(aa[0],aa[3]);
 209     accum1  = widemul(a[4],a[7]);
 210
 211     accum2 += widemul(a[1], a[2]);
 212     accum0 += widemul(aa[1], aa[2]);
 213     accum1 += widemul(a[5], a[6]);
 214
 215     accum0 -= accum2;
 216     accum1 += accum2;
 217
 218     c[3] = ((uint64_t)(accum1))<<1 & mask;
 219     c[7] = ((uint64_t)(accum0))<<1 & mask;
 220
 221     accum0 >>= 55;
 222     accum1 >>= 55;
 223
 224     accum0 += widemul(2*aa[1],aa[3]);
 225     accum1 += widemul(2*a[5], a[7]);
 226     accum0 += widemul(aa[2], aa[2]);
 227     accum1 += accum0;
 228
 229     accum0 -= widemul(2*a[1], a[3]);
 230     accum1 += widemul(a[6], a[6]);
 231
 232     accum2 = widemul(a[0],a[0]);
 233     accum1 -= accum2;
 234     accum0 += accum2;
 235
 236     accum0 -= widemul(a[2], a[2]);
 237     accum1 += widemul(aa[0], aa[0]);
 238     accum0 += widemul(a[4], a[4]);
 239
 240     c[0] = ((uint64_t)(accum0)) & mask;
 241     c[4] = ((uint64_t)(accum1)) & mask;
 242
 243     accum0 >>= 56;
 244     accum1 >>= 56;
 245
 246     accum2  = widemul(2*aa[2],aa[3]);
 247     accum0 -= widemul(2*a[2], a[3]);
 248     accum1 += widemul(2*a[6], a[7]);
 249
 250     accum1 += accum2;
 251     accum0 += accum2;
 252
 253     accum2  = widemul(2*a[0],a[1]);
 254     accum1 += widemul(2*aa[0], aa[1]);
 255     accum0 += widemul(2*a[4], a[5]);
 256
 257     accum1 -= accum2;
 258     accum0 += accum2;
 259
 260     c[1] = ((uint64_t)(accum0)) & mask;
 261     c[5] = ((uint64_t)(accum1)) & mask;
 262
 263     accum0 >>= 56;
 264     accum1 >>= 56;
 265
 266     accum2  = widemul(aa[3],aa[3]);
 267     accum0 -= widemul(a[3], a[3]);
 268     accum1 += widemul(a[7], a[7]);
 269
 270     accum1 += accum2;
 271     accum0 += accum2;
 272
 273     accum2  = widemul(2*a[0],a[2]);
 274     accum1 += widemul(2*aa[0], aa[2]);
 275     accum0 += widemul(2*a[4], a[6]);
 276
 277     accum2 += widemul(a[1], a[1]);
 278     accum1 += widemul(aa[1], aa[1]);
 279     accum0 += widemul(a[5], a[5]);
 280
 281     accum1 -= accum2;
 282     accum0 += accum2;
 283
 284     c[2] = ((uint64_t)(accum0)) & mask;
 285     c[6] = ((uint64_t)(accum1)) & mask;
 286
 287     accum0 >>= 56;
 288     accum1 >>= 56;
 289
 290     accum0 += c[3];
 291     accum1 += c[7];
 292     c[3] = ((uint64_t)(accum0)) & mask;
 293     c[7] = ((uint64_t)(accum1)) & mask;
 294
 295     /* we could almost stop here, but it wouldn't be stable, so... */
 296
 297     accum0 >>= 56;
 298     accum1 >>= 56;
 299     c[4] += ((uint64_t)(accum0)) + ((uint64_t)(accum1));
 300     c[0] += ((uint64_t)(accum1));
 301 }
 302