_ Git - BearSSL/blob - src/int/i15_montmul.c

   1 /*
   2  * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 #include "inner.h"
  26
  27 /* see inner.h */
  28 void
  29 br_i15_montymul(uint16_t *d, const uint16_t *x, const uint16_t *y,
  30         const uint16_t *m, uint16_t m0i)
  31 {
  32         size_t len, len4, u, v;
  33         uint32_t dh;
  34
  35         len = (m[0] + 15) >> 4;
  36         len4 = len & ~(size_t)3;
  37         br_i15_zero(d, m[0]);
  38         dh = 0;
  39         for (u = 0; u < len; u ++) {
  40                 uint32_t f, xu, r, zh;
  41
  42                 xu = x[u + 1];
  43                 f = MUL15((d[1] + MUL15(x[u + 1], y[1])) & 0x7FFF, m0i)
  44                         & 0x7FFF;
  45 #if BR_ARMEL_CORTEXM_GCC
  46                 if (len4 != 0) {
  47                         uint16_t *limit;
  48
  49                         limit = d + len4;
  50                         asm volatile (
  51 "\n\
  52         @ carry: r=r2                                              \n\
  53         @ multipliers: xu=r3 f=r4                                  \n\
  54         @ base registers: d+v=r5 y+v=r6 m+v=r7                     \n\
  55         @ r8 contains 0x7FFF                                       \n\
  56         @ r9 contains d+len4                                       \n\
  57         ldr     r0, %[limit]                                       \n\
  58         ldr     r3, %[xu]                                          \n\
  59         mov     r9, r0                                             \n\
  60         ldr     r4, %[f]                                           \n\
  61         eor     r2, r2                                             \n\
  62         ldr     r5, %[d]                                           \n\
  63         sub     r1, r2, #1                                         \n\
  64         ldr     r6, %[y]                                           \n\
  65         lsr     r1, r1, #17                                        \n\
  66         ldr     r7, %[m]                                           \n\
  67         mov     r8, r1                                             \n\
  68 loop%=:                                                            \n\
  69         ldrh    r0, [r6, #2]                                       \n\
  70         ldrh    r1, [r7, #2]                                       \n\
  71         mul     r0, r3                                             \n\
  72         mul     r1, r4                                             \n\
  73         add     r2, r0, r2                                         \n\
  74         ldrh    r0, [r5, #2]                                       \n\
  75         add     r2, r1, r2                                         \n\
  76         mov     r1, r8                                             \n\
  77         add     r2, r0, r2                                         \n\
  78         and     r1, r2                                             \n\
  79         lsr     r2, r2, #15                                        \n\
  80         strh    r1, [r5, #0]                                       \n\
  81                                                                    \n\
  82         ldrh    r0, [r6, #4]                                       \n\
  83         ldrh    r1, [r7, #4]                                       \n\
  84         mul     r0, r3                                             \n\
  85         mul     r1, r4                                             \n\
  86         add     r2, r0, r2                                         \n\
  87         ldrh    r0, [r5, #4]                                       \n\
  88         add     r2, r1, r2                                         \n\
  89         mov     r1, r8                                             \n\
  90         add     r2, r0, r2                                         \n\
  91         and     r1, r2                                             \n\
  92         lsr     r2, r2, #15                                        \n\
  93         strh    r1, [r5, #2]                                       \n\
  94                                                                    \n\
  95         ldrh    r0, [r6, #6]                                       \n\
  96         ldrh    r1, [r7, #6]                                       \n\
  97         mul     r0, r3                                             \n\
  98         mul     r1, r4                                             \n\
  99         add     r2, r0, r2                                         \n\
 100         ldrh    r0, [r5, #6]                                       \n\
 101         add     r2, r1, r2                                         \n\
 102         mov     r1, r8                                             \n\
 103         add     r2, r0, r2                                         \n\
 104         and     r1, r2                                             \n\
 105         lsr     r2, r2, #15                                        \n\
 106         strh    r1, [r5, #4]                                       \n\
 107                                                                    \n\
 108         ldrh    r0, [r6, #8]                                       \n\
 109         ldrh    r1, [r7, #8]                                       \n\
 110         mul     r0, r3                                             \n\
 111         mul     r1, r4                                             \n\
 112         add     r2, r0, r2                                         \n\
 113         ldrh    r0, [r5, #8]                                       \n\
 114         add     r2, r1, r2                                         \n\
 115         mov     r1, r8                                             \n\
 116         add     r2, r0, r2                                         \n\
 117         and     r1, r2                                             \n\
 118         lsr     r2, r2, #15                                        \n\
 119         strh    r1, [r5, #6]                                       \n\
 120                                                                    \n\
 121         add     r5, r5, #8                                         \n\
 122         add     r6, r6, #8                                         \n\
 123         add     r7, r7, #8                                         \n\
 124         cmp     r5, r9                                             \n\
 125         bne     loop%=                                             \n\
 126                                                                    \n\
 127         str     r2, %[carry]                                       \n\
 128 "
 129 : [carry] "=m" (r)
 130 : [xu] "m" (xu), [f] "m" (f), [d] "m" (d), [y] "m" (y),
 131         [m] "m" (m), [limit] "m" (limit)
 132 : "r0", "r1", "r2", "r3", "r4", "r5", "r6", "r7", "r8", "r9" );
 133                 } else {
 134                         r = 0;
 135                 }
 136                 v = len4;
 137 #else
 138                 r = 0;
 139                 for (v = 0; v < len4; v += 4) {
 140                         uint32_t z;
 141
 142                         z = d[v + 1] + MUL15(xu, y[v + 1])
 143                                 + MUL15(f, m[v + 1]) + r;
 144                         r = z >> 15;
 145                         d[v + 0] = z & 0x7FFF;
 146                         z = d[v + 2] + MUL15(xu, y[v + 2])
 147                                 + MUL15(f, m[v + 2]) + r;
 148                         r = z >> 15;
 149                         d[v + 1] = z & 0x7FFF;
 150                         z = d[v + 3] + MUL15(xu, y[v + 3])
 151                                 + MUL15(f, m[v + 3]) + r;
 152                         r = z >> 15;
 153                         d[v + 2] = z & 0x7FFF;
 154                         z = d[v + 4] + MUL15(xu, y[v + 4])
 155                                 + MUL15(f, m[v + 4]) + r;
 156                         r = z >> 15;
 157                         d[v + 3] = z & 0x7FFF;
 158                 }
 159 #endif
 160                 for (; v < len; v ++) {
 161                         uint32_t z;
 162
 163                         z = d[v + 1] + MUL15(xu, y[v + 1])
 164                                 + MUL15(f, m[v + 1]) + r;
 165                         r = z >> 15;
 166                         d[v + 0] = z & 0x7FFF;
 167                 }
 168
 169                 zh = dh + r;
 170                 d[len] = zh & 0x7FFF;
 171                 dh = zh >> 15;
 172         }
 173
 174         /*
 175          * Restore the bit length (it was overwritten in the loop above).
 176          */
 177         d[0] = m[0];
 178
 179         /*
 180          * d[] may be greater than m[], but it is still lower than twice
 181          * the modulus.
 182          */
 183         br_i15_sub(d, m, NEQ(dh, 0) | NOT(br_i15_sub(d, m, 0)));
 184 }