initially checkin
[gnupg.git] / mpi / mpih-add.c
1 /* mpihelp-add.c  -  MPI helper functions
2  *      Copyright (c) 1997 by Werner Koch (dd9jn)
3  *
4  * This file is part of G10.
5  *
6  * G10 is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * G10 is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24
25 #include "mpi-internal.h"
26
27 /****************
28  * Add to S1_PTR with size S1_SIZE the limb S2_LIMB and
29  * store the result in RES_PTR. Return the carry
30  * S1_SIZE must be > 0.
31  */
32 /*_EXTERN_INLINE */
33 mpi_limb_t
34 mpihelp_add_1( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
35                mpi_size_t s1_size, mpi_limb_t s2_limb)
36 {
37     mpi_limb_t x;
38
39     x = *s1_ptr++;
40     s2_limb += x;
41     *res_ptr++ = s2_limb;
42     if( s2_limb < x ) { /* sum is less than the left operand: handle carry */
43         while( --s1_size ) {
44             x = *s1_ptr++ + 1;  /* add carry */
45             *res_ptr++ = x;     /* and store */
46             if( x )             /* not 0 (no overflow): we can stop */
47                 goto leave;
48         }
49         return 1; /* return carry (size of s1 to small) */
50     }
51
52   leave:
53     if( res_ptr != s1_ptr ) { /* not the same variable */
54         mpi_size_t i;          /* copy the rest */
55         for( i=0; i < s1_size-1; i++ )
56             res_ptr[i] = s1_ptr[i];
57     }
58     return 0; /* no carry */
59 }
60
61
62 /* FIXME: this should be done in assembly */
63 mpi_limb_t
64 mpihelp_add_n( mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr,
65                mpi_ptr_t s2_ptr, mpi_size_t size)
66 {
67     mpi_limb_t x, y, cy;
68     mpi_size_t j;
69
70     /* The loop counter and index J goes from -SIZE to -1.  This way
71        the loop becomes faster.  */
72     j = -size;
73
74     /* Offset the base pointers to compensate for the negative indices. */
75     s1_ptr -= j;
76     s2_ptr -= j;
77     res_ptr -= j;
78
79     cy = 0;
80     do {
81         y = s2_ptr[j];
82         x = s1_ptr[j];
83         y += cy;                  /* add previous carry to one addend */
84         cy = y < cy? 1:0;         /* get out carry from that addition */
85         y += x;                   /* add other addend */
86         cy += y < x? 1:0;         /* get out carry from that add, combine */
87         res_ptr[j] = y;
88     } while( ++j );
89
90     return cy;
91 }
92
93
94 /*_EXTERN_INLINE*/
95 mpi_limb_t
96 mpihelp_add(mpi_ptr_t res_ptr, mpi_ptr_t s1_ptr, mpi_size_t s1_size,
97                                mpi_ptr_t s2_ptr, mpi_size_t s2_size)
98 {
99     mpi_limb_t cy = 0;
100
101     if( s2_size )
102         cy = mpihelp_add_n( res_ptr, s1_ptr, s2_ptr, s2_size );
103
104     if( s1_size - s2_size )
105         cy = mpihelp_add_1( res_ptr + s2_size, s1_ptr + s2_size,
106                             s1_size - s2_size, cy);
107     return cy;
108 }
109