source/libs/gmp/gmp-src/mpn/generic/sec_div.c

   1 /* mpn_sec_div_qr, mpn_sec_div_r -- Compute Q = floor(U / V), U = U mod V.
   2    Side-channel silent under the assumption that the used instructions are
   3    side-channel silent.
   4
   5    Contributed to the GNU project by Torbjörn Granlund.
   6
   7 Copyright 2011-2014 Free Software Foundation, Inc.
   8
   9 This file is part of the GNU MP Library.
  10
  11 The GNU MP Library is free software; you can redistribute it and/or modify
  12 it under the terms of either:
  13
  14   * the GNU Lesser General Public License as published by the Free
  15     Software Foundation; either version 3 of the License, or (at your
  16     option) any later version.
  17
  18 or
  19
  20   * the GNU General Public License as published by the Free Software
  21     Foundation; either version 2 of the License, or (at your option) any
  22     later version.
  23
  24 or both in parallel, as here.
  25
  26 The GNU MP Library is distributed in the hope that it will be useful, but
  27 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  28 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  29 for more details.
  30
  31 You should have received copies of the GNU General Public License and the
  32 GNU Lesser General Public License along with the GNU MP Library.  If not,
  33 see https://www.gnu.org/licenses/.  */
  34
  35 #include "gmp.h"
  36 #include "gmp-impl.h"
  37 #include "longlong.h"
  38
  39 #if OPERATION_sec_div_qr
  40 #define FNAME mpn_sec_div_qr
  41 #define FNAME_itch mpn_sec_div_qr_itch
  42 #define Q(q) q,
  43 #define RETTYPE mp_limb_t
  44 #endif
  45 #if OPERATION_sec_div_r
  46 #define FNAME mpn_sec_div_r
  47 #define FNAME_itch mpn_sec_div_r_itch
  48 #define Q(q)
  49 #define RETTYPE void
  50 #endif
  51
  52 mp_size_t
  53 FNAME_itch (mp_size_t nn, mp_size_t dn)
  54 {
  55 #if OPERATION_sec_div_qr
  56 /* Needs (nn + dn + 1) + mpn_sec_pi1_div_qr's needs of (2nn' - dn + 1) for a
  57    total of 3nn + 4 limbs at tp.  Note that mpn_sec_pi1_div_qr's nn is one
  58    greater than ours, therefore +4 and not just +2.  */
  59   return 3 * nn + 4;
  60 #endif
  61 #if OPERATION_sec_div_r
  62 /* Needs (nn + dn + 1) + mpn_sec_pi1_div_r's needs of (dn + 1) for a total of
  63    nn + 2dn + 2 limbs at tp.  */
  64   return nn + 2 * dn + 2;
  65 #endif
  66 }
  67
  68 RETTYPE
  69 FNAME (Q(mp_ptr qp)
  70        mp_ptr np, mp_size_t nn,
  71        mp_srcptr dp, mp_size_t dn,
  72        mp_ptr tp)
  73 {
  74   mp_limb_t d1, d0;
  75   unsigned int cnt;
  76   gmp_pi1_t dinv;
  77   mp_limb_t inv32;
  78
  79   ASSERT (dn >= 1);
  80   ASSERT (nn >= dn);
  81   ASSERT (dp[dn - 1] != 0);
  82
  83   d1 = dp[dn - 1];
  84   count_leading_zeros (cnt, d1);
  85
  86   if (cnt != 0)
  87     {
  88       mp_limb_t qh, cy;
  89       mp_ptr np2, dp2;
  90       dp2 = tp;                                 /* dn limbs */
  91       mpn_lshift (dp2, dp, dn, cnt);
  92
  93       np2 = tp + dn;                            /* (nn + 1) limbs */
  94       cy = mpn_lshift (np2, np, nn, cnt);
  95       np2[nn++] = cy;
  96
  97       d0 = dp2[dn - 1];
  98       d0 += (~d0 != 0);
  99       invert_limb (inv32, d0);
 100
 101       /* We add nn + dn to tp here, not nn + 1 + dn, as expected.  This is
 102          since nn here will have been incremented.  */
 103 #if OPERATION_sec_div_qr
 104       qh = mpn_sec_pi1_div_qr (np2 + dn, np2, nn, dp2, dn, inv32, tp + nn + dn);
 105       ASSERT (qh == 0);         /* FIXME: this indicates inefficiency! */
 106       MPN_COPY (qp, np2 + dn, nn - dn - 1);
 107       qh = np2[nn - 1];
 108 #else
 109       mpn_sec_pi1_div_r (np2, nn, dp2, dn, inv32, tp + nn + dn);
 110 #endif
 111
 112       mpn_rshift (np, np2, dn, cnt);
 113
 114 #if OPERATION_sec_div_qr
 115       return qh;
 116 #endif
 117     }
 118   else
 119     {
 120       /* FIXME: Consider copying np => np2 here, adding a 0-limb at the top.
 121          That would simplify the underlying pi1 function, since then it could
 122          assume nn > dn.  */
 123       d0 = dp[dn - 1];
 124       d0 += (~d0 != 0);
 125       invert_limb (inv32, d0);
 126
 127 #if OPERATION_sec_div_qr
 128       return mpn_sec_pi1_div_qr (qp, np, nn, dp, dn, inv32, tp);
 129 #else
 130       mpn_sec_pi1_div_r (np, nn, dp, dn, inv32, tp);
 131 #endif
 132     }
 133 }