arm/ecc-256-redc.asm

   1 C arm/ecc-256-redc.asm
   2
   3 ifelse(<
   4    Copyright (C) 2013 Niels Möller
   5
   6    This file is part of GNU Nettle.
   7
   8    GNU Nettle is free software: you can redistribute it and/or
   9    modify it under the terms of either:
  10
  11      * the GNU Lesser General Public License as published by the Free
  12        Software Foundation; either version 3 of the License, or (at your
  13        option) any later version.
  14
  15    or
  16
  17      * the GNU General Public License as published by the Free
  18        Software Foundation; either version 2 of the License, or (at your
  19        option) any later version.
  20
  21    or both in parallel, as here.
  22
  23    GNU Nettle is distributed in the hope that it will be useful,
  24    but WITHOUT ANY WARRANTY; without even the implied warranty of
  25    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  26    General Public License for more details.
  27
  28    You should have received copies of the GNU General Public License and
  29    the GNU Lesser General Public License along with this program.  If
  30    not, see http://www.gnu.org/licenses/.
  31 >)
  32
  33         .file "ecc-256-redc.asm"
  34         .arm
  35
  36 define(<RP>, <r1>)
  37
  38 define(<T0>, <r0>) C Overlaps unused modulo argument
  39 define(<T1>, <r2>)
  40 define(<T2>, <r3>)
  41 define(<T3>, <r4>)
  42 define(<T4>, <r5>)
  43 define(<T5>, <r6>)
  44 define(<T6>, <r7>)
  45 define(<T7>, <r8>)
  46 define(<F0>, <r10>)
  47 define(<F1>, <r11>)
  48 define(<F2>, <r12>)
  49 define(<F3>, <lr>)
  50
  51         C ecc_256_redc (const struct ecc_modulo *m, mp_limb_t *rp)
  52         .text
  53         .align 2
  54
  55 PROLOGUE(nettle_ecc_256_redc)
  56         push    {r4,r5,r6,r7,r8,r10,r11,lr}
  57
  58         ldm     RP!, {T0,T1,T2,T3,T4,T5,T6,T7}
  59
  60         C Set <F3,F2,F1> to the high 4 limbs of (B^2-B+1)<T2,T1,T0>
  61         C         T2 T1
  62         C   T2 T1 T0
  63         C   -  T2 T1 T0
  64         C -------------
  65         C   F3 F2 F1 F0
  66
  67
  68         adds    F1, T0, T2
  69         adcs    F2, T1, #0
  70         adc     F3, T2, #0
  71
  72         subs    F0, T1, T0
  73         sbcs    F1, F1, T1      C Could also be rsc ?
  74         sbcs    F2, F2, T2
  75         sbc     F3, F3, #0
  76
  77         C Add:
  78         C   T10 T9 T8 T7 T6 T5 T4 T3
  79         C +  F3 F2 F1 F0 T0 T2 T1 T0
  80         C --------------------------
  81         C    T7 T6 T5 T4 T3 T2 T1 T0
  82
  83         adds    T3, T3, T0
  84         adcs    T1, T4, T1
  85         adcs    T2, T5, T2
  86         adcs    T6, T6, T0
  87         mov     T0, T3          C FIXME: Be more clever?
  88         mov     T3, T6
  89         adcs    T4, T7, F0
  90
  91         ldm     RP!, {T5,T6,T7}
  92         adcs    T5, T5, F1
  93         adcs    T6, T6, F2
  94         adcs    T7, T7, F3
  95
  96         C New F3, F2, F1, F0, also adding in carry
  97         adcs    F1, T0, T2
  98         adcs    F2, T1, #0
  99         adc     F3, T2, #0
 100
 101         subs    F0, T1, T0
 102         sbcs    F1, F1, T1      C Could also be rsc ?
 103         sbcs    F2, F2, T2
 104         sbc     F3, F3, #0
 105
 106         C Start adding
 107         adds    T3, T3, T0
 108         adcs    T1, T4, T1
 109         adcs    T2, T5, T2
 110         adcs    T6, T6, T0
 111         mov     T0, T3          C FIXME: Be more clever?
 112         mov     T3, T6
 113         adcs    T4, T7, F0
 114
 115         ldm     RP!, {T5,T6,T7}
 116         adcs    T5, T5, F1
 117         adcs    T6, T6, F2
 118         adcs    T7, T7, F3
 119
 120         C Final iteration, eliminate only T0, T1
 121         C Set <F2, F1, F0> to the high 3 limbs of (B^2-B+1)<T1,T0>
 122
 123         C      T1 T0 T1
 124         C      -  T1 T0
 125         C -------------
 126         C      F2 F1 F0
 127
 128         C First add in carry
 129         adcs    F1, T0, #0
 130         adcs    F2, T1, #0
 131         subs    F0, T1, T0
 132         sbcs    F1, F1, T1
 133         sbc     F2, F2, #0
 134
 135         C Add:
 136         C    T9 T8 T7 T6 T5 T4 T3 T2
 137         C +  F2 F1 F0 T0  0 T1 T0  0
 138         C --------------------------
 139         C    F2 F1 T7 T6 T5 T4 T3 T2
 140
 141         adds    T3, T3, T0
 142         adcs    T4, T4, T1
 143         adcs    T5, T5, #0
 144         adcs    T6, T6, T0
 145         adcs    T7, T7, F0
 146         ldm     RP!, {T0, T1}
 147         mov     F3, #0
 148         adcs    F1, F1, T0
 149         adcs    F2, F2, T1
 150
 151         C Sum is < B^8 + p, so it's enough to fold carry once,
 152         C If carry, add in
 153         C   B^7 - B^6 - B^3 + 1  = <0, B-2, B-1, B-1, B-1, 0, 0, 1>
 154
 155         C Mask from carry flag, leaving carry intact
 156         adc     F3, F3, #0
 157         rsb     F3, F3, #0
 158
 159         adcs    T0, T2, #0
 160         adcs    T1, T3, #0
 161         adcs    T2, T4, #0
 162         adcs    T3, T5, F3
 163         adcs    T4, T6, F3
 164         adcs    T5, T7, F3
 165         and     F3, F3, #-2
 166         adcs    T6, F1, F3
 167         adcs    T7, F2, #0
 168
 169         sub     RP, RP, #64
 170         stm     RP, {T0,T1,T2,T3,T4,T5,T6,T7}
 171
 172         pop     {r4,r5,r6,r7,r8,r10,r11,pc}
 173 EPILOGUE(nettle_ecc_256_redc)