← Back to branch summary

~ubuntu-branches/ubuntu/trusty/nettle/trusty

« back to all changes in this revision

Viewing changes to ecc-generic-redc.c

  • Committer: Package Import Robot
  • Author(s): Magnus Holmgren
  • Date: 2013-05-07 22:57:14 UTC
  • mfrom: (8.1.8 sid)
  • Revision ID: package-import@ubuntu.com-20130507225714-s331yr8ov53dtt17
Tags: 2.7-2
Tag some (ECC related) symbols that only exist on some architectures.

Show diffs side-by-side

added added

removed removed

Lines of Context:
ecc-generic-redc.c
 
1
/* ecc-generic-redc.c */
 
2
 
 
3
/* nettle, low-level cryptographics library
 
4
 *
 
5
 * Copyright (C) 2013 Niels Möller
 
6
 *  
 
7
 * The nettle library is free software; you can redistribute it and/or modify
 
8
 * it under the terms of the GNU Lesser General Public License as published by
 
9
 * the Free Software Foundation; either version 2.1 of the License, or (at your
 
10
 * option) any later version.
 
11
 * 
 
12
 * The nettle library is distributed in the hope that it will be useful, but
 
13
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 
14
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 
15
 * License for more details.
 
16
 * 
 
17
 * You should have received a copy of the GNU Lesser General Public License
 
18
 * along with the nettle library; see the file COPYING.LIB.  If not, write to
 
19
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 
20
 * MA 02111-1301, USA.
 
21
 */
 
22
 
 
23
/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
 
24
 
 
25
#if HAVE_CONFIG_H
 
26
# include "config.h"
 
27
#endif
 
28
 
 
29
#include <assert.h>
 
30
 
 
31
#include "ecc-internal.h"
 
32
 
 
33
void
 
34
ecc_generic_redc (const struct ecc_curve *ecc, mp_limb_t *rp)
 
35
{
 
36
  unsigned i;
 
37
  mp_limb_t hi, cy;
 
38
  unsigned shift = ecc->size * GMP_NUMB_BITS - ecc->bit_size;
 
39
  mp_size_t k = ecc->redc_size;
 
40
  
 
41
  assert (k != 0);
 
42
  if (k > 0)    
 
43
    {
 
44
      /* Use that 1 = p + 1, and that at least one low limb of p + 1 is zero. */
 
45
      for (i = 0; i < ecc->size; i++)
 
46
        rp[i] = mpn_addmul_1 (rp + i + k,
 
47
                              ecc->redc_ppm1, ecc->size - k, rp[i]);
 
48
      hi = mpn_add_n (rp, rp, rp + ecc->size, ecc->size);
 
49
      if (shift > 0)
 
50
        {
 
51
          hi = (hi << shift) | (rp[ecc->size - 1] >> (GMP_NUMB_BITS - shift));
 
52
          rp[ecc->size - 1] = (rp[ecc->size - 1]
 
53
                               & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
 
54
            + mpn_addmul_1 (rp, ecc->Bmodp_shifted, ecc->size-1, hi);
 
55
          
 
56
        }
 
57
      else
 
58
        {
 
59
          cy = cnd_sub_n (hi, rp, ecc->p, ecc->size);
 
60
          assert (cy == hi);      
 
61
        }
 
62
    }
 
63
  else
 
64
    {
 
65
      /* Use that 1 = - (p - 1), and that at least one low limb of p -
 
66
         1 is zero. */
 
67
      k = -k;
 
68
      for (i = 0; i < ecc->size; i++)
 
69
        rp[i] = mpn_submul_1 (rp + i + k,
 
70
                              ecc->redc_ppm1, ecc->size - k, rp[i]);
 
71
      hi = mpn_sub_n (rp, rp + ecc->size, rp, ecc->size);
 
72
      cy = cnd_add_n (hi, rp, ecc->p, ecc->size);
 
73
      assert (cy == hi);
 
74
 
 
75
      if (shift > 0)
 
76
        {
 
77
          /* Result is always < 2p, provided that
 
78
             2^shift * Bmodp_shifted <= p */
 
79
          hi = (rp[ecc->size - 1] >> (GMP_NUMB_BITS - shift));
 
80
          rp[ecc->size - 1] = (rp[ecc->size - 1]
 
81
                               & (((mp_limb_t) 1 << (GMP_NUMB_BITS - shift)) - 1))
 
82
            + mpn_addmul_1 (rp, ecc->Bmodp_shifted, ecc->size-1, hi);
 
83
        }
 
84
    }
 
85
}