Coverage Report

Created: 2023-02-22 06:39

/src/gmp-6.2.1/mpn/toom2_sqr.c
Line
Count
Source (jump to first uncovered line)
1
/* mpn_toom2_sqr -- Square {ap,an}.
2
3
   Contributed to the GNU project by Torbjorn Granlund.
4
5
   THE FUNCTION IN THIS FILE IS INTERNAL WITH A MUTABLE INTERFACE.  IT IS ONLY
6
   SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES.  IN FACT, IT IS ALMOST
7
   GUARANTEED THAT IT WILL CHANGE OR DISAPPEAR IN A FUTURE GNU MP RELEASE.
8
9
Copyright 2006-2010, 2012, 2014, 2018 Free Software Foundation, Inc.
10
11
This file is part of the GNU MP Library.
12
13
The GNU MP Library is free software; you can redistribute it and/or modify
14
it under the terms of either:
15
16
  * the GNU Lesser General Public License as published by the Free
17
    Software Foundation; either version 3 of the License, or (at your
18
    option) any later version.
19
20
or
21
22
  * the GNU General Public License as published by the Free Software
23
    Foundation; either version 2 of the License, or (at your option) any
24
    later version.
25
26
or both in parallel, as here.
27
28
The GNU MP Library is distributed in the hope that it will be useful, but
29
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
30
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
31
for more details.
32
33
You should have received copies of the GNU General Public License and the
34
GNU Lesser General Public License along with the GNU MP Library.  If not,
35
see https://www.gnu.org/licenses/.  */
36
37
38
#include "gmp-impl.h"
39
40
/* Evaluate in: -1, 0, +inf
41
42
  <-s--><--n-->
43
   ____ ______
44
  |_a1_|___a0_|
45
46
  v0  =  a0     ^2  #   A(0)^2
47
  vm1 = (a0- a1)^2  #  A(-1)^2
48
  vinf=      a1 ^2  # A(inf)^2
49
*/
50
51
#if TUNE_PROGRAM_BUILD || WANT_FAT_BINARY
52
#define MAYBE_sqr_toom2   1
53
#else
54
#define MAYBE_sqr_toom2             \
55
25.1k
  (SQR_TOOM3_THRESHOLD >= 2 * SQR_TOOM2_THRESHOLD)
56
#endif
57
58
#define TOOM2_SQR_REC(p, a, n, ws)          \
59
12.5k
  do {                 \
60
12.5k
    if (! MAYBE_sqr_toom2            \
61
12.5k
  || BELOW_THRESHOLD (n, SQR_TOOM2_THRESHOLD))      \
62
12.5k
      mpn_sqr_basecase (p, a, n);         \
63
12.5k
    else                \
64
12.5k
      mpn_toom2_sqr (p, a, n, ws);         \
65
12.5k
  } while (0)
66
67
void
68
mpn_toom2_sqr (mp_ptr pp,
69
         mp_srcptr ap, mp_size_t an,
70
         mp_ptr scratch)
71
4.18k
{
72
4.18k
  const int __gmpn_cpuvec_initialized = 1;
73
4.18k
  mp_size_t n, s;
74
4.18k
  mp_limb_t cy, cy2;
75
4.18k
  mp_ptr asm1;
76
77
10.1k
#define a0  ap
78
6.65k
#define a1  (ap + n)
79
80
4.18k
  s = an >> 1;
81
4.18k
  n = an - s;
82
83
4.18k
  ASSERT (0 < s && s <= n && s >= n - 1);
84
85
4.18k
  asm1 = pp;
86
87
  /* Compute asm1.  */
88
4.18k
  if (s == n)
89
2.42k
    {
90
2.42k
      if (mpn_cmp (a0, a1, n) < 0)
91
440
  {
92
440
    mpn_sub_n (asm1, a1, a0, n);
93
440
  }
94
1.98k
      else
95
1.98k
  {
96
1.98k
    mpn_sub_n (asm1, a0, a1, n);
97
1.98k
  }
98
2.42k
    }
99
1.76k
  else /* n - s == 1 */
100
1.76k
    {
101
1.76k
      if (a0[s] == 0 && mpn_cmp (a0, a1, s) < 0)
102
34
  {
103
34
    mpn_sub_n (asm1, a1, a0, s);
104
34
    asm1[s] = 0;
105
34
  }
106
1.73k
      else
107
1.73k
  {
108
1.73k
    asm1[s] = a0[s] - mpn_sub_n (asm1, a0, a1, s);
109
1.73k
  }
110
1.76k
    }
111
112
8.37k
#define v0  pp        /* 2n */
113
8.37k
#define vinf  (pp + 2 * n)      /* s+s */
114
4.18k
#define vm1 scratch        /* 2n */
115
4.18k
#define scratch_out scratch + 2 * n
116
117
  /* vm1, 2n limbs */
118
4.18k
  TOOM2_SQR_REC (vm1, asm1, n, scratch_out);
119
120
  /* vinf, s+s limbs */
121
4.18k
  TOOM2_SQR_REC (vinf, a1, s, scratch_out);
122
123
  /* v0, 2n limbs */
124
4.18k
  TOOM2_SQR_REC (v0, ap, n, scratch_out);
125
126
  /* H(v0) + L(vinf) */
127
4.18k
  cy = mpn_add_n (pp + 2 * n, v0 + n, vinf, n);
128
129
  /* L(v0) + H(v0) */
130
4.18k
  cy2 = cy + mpn_add_n (pp + n, pp + 2 * n, v0, n);
131
132
  /* L(vinf) + H(vinf) */
133
4.18k
  cy += mpn_add (pp + 2 * n, pp + 2 * n, n, vinf + n, s + s - n);
134
135
4.18k
  cy -= mpn_sub_n (pp + n, pp + n, vm1, 2 * n);
136
137
4.18k
  ASSERT (cy + 1 <= 3);
138
4.18k
  ASSERT (cy2 <= 2);
139
140
4.18k
  if (LIKELY (cy <= 2)) {
141
4.18k
    MPN_INCR_U (pp + 2 * n, s + s, cy2);
142
4.18k
    MPN_INCR_U (pp + 3 * n, s + s - n, cy);
143
4.18k
  } else { /* cy is negative */
144
    /* The total contribution of v0+vinf-vm1 can not be negative. */
145
0
#if WANT_ASSERT
146
    /* The borrow in cy stops the propagation of the carry cy2, */
147
0
    ASSERT (cy2 == 1);
148
0
    cy += mpn_add_1 (pp + 2 * n, pp + 2 * n, n, cy2);
149
0
    ASSERT (cy == 0);
150
#else
151
    /* we simply fill the area with zeros. */
152
    MPN_FILL (pp + 2 * n, n, 0);
153
#endif
154
0
  }
155
4.18k
}