crypto/ec/curve448/arch_ref64/f_impl.c

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