← Back to branch summary

~ubuntu-branches/ubuntu/natty/postgresql-8.4/natty-security

« back to all changes in this revision

Viewing changes to contrib/pgcrypto/imath.c

Tags: upstream-8.4.0
Import upstream version 8.4.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/pgcrypto/imath.c
27
27
  CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28
28
  SOFTWARE.
29
29
 */
30
 
/* $PostgreSQL: pgsql/contrib/pgcrypto/imath.c,v 1.7 2007/07/15 22:43:40 tgl Exp $ */
 
30
/* $PostgreSQL: pgsql/contrib/pgcrypto/imath.c,v 1.8 2009/06/11 14:48:52 momjian Exp $ */
31
31
 
32
32
#include "postgres.h"
33
33
#include "px.h"
195
195
static void s_fake(mp_int z, int value, mp_digit vbuf[]);
196
196
 
197
197
/* Compare two runs of digits of given length, returns <0, 0, >0 */
198
 
static int      s_cdig(mp_digit * da, mp_digit * db, mp_size len);
 
198
static int      s_cdig(mp_digit *da, mp_digit *db, mp_size len);
199
199
 
200
200
/* Pack the unsigned digits of v into array t */
201
201
static int      s_vpack(int v, mp_digit t[]);
208
208
 
209
209
/* Unsigned magnitude addition; assumes dc is big enough.
210
210
   Carry out is returned (no memory allocated). */
211
 
static mp_digit s_uadd(mp_digit * da, mp_digit * db, mp_digit * dc,
 
211
static mp_digit s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc,
212
212
           mp_size size_a, mp_size size_b);
213
213
 
214
214
/* Unsigned magnitude subtraction.      Assumes dc is big enough. */
215
 
static void s_usub(mp_digit * da, mp_digit * db, mp_digit * dc,
 
215
static void s_usub(mp_digit *da, mp_digit *db, mp_digit *dc,
216
216
           mp_size size_a, mp_size size_b);
217
217
 
218
218
/* Unsigned recursive multiplication.  Assumes dc is big enough. */
219
 
static int s_kmul(mp_digit * da, mp_digit * db, mp_digit * dc,
 
219
static int s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc,
220
220
           mp_size size_a, mp_size size_b);
221
221
 
222
222
/* Unsigned magnitude multiplication.  Assumes dc is big enough. */
223
 
static void s_umul(mp_digit * da, mp_digit * db, mp_digit * dc,
 
223
static void s_umul(mp_digit *da, mp_digit *db, mp_digit *dc,
224
224
           mp_size size_a, mp_size size_b);
225
225
 
226
226
/* Unsigned recursive squaring.  Assumes dc is big enough. */
227
 
static int      s_ksqr(mp_digit * da, mp_digit * dc, mp_size size_a);
 
227
static int      s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a);
228
228
 
229
229
/* Unsigned magnitude squaring.  Assumes dc is big enough. */
230
 
static void s_usqr(mp_digit * da, mp_digit * dc, mp_size size_a);
 
230
static void s_usqr(mp_digit *da, mp_digit *dc, mp_size size_a);
231
231
 
232
232
/* Single digit addition.  Assumes a is big enough. */
233
233
static void s_dadd(mp_int a, mp_digit b);
236
236
static void s_dmul(mp_int a, mp_digit b);
237
237
 
238
238
/* Single digit multiplication on buffers; assumes dc is big enough. */
239
 
static void s_dbmul(mp_digit * da, mp_digit b, mp_digit * dc,
 
239
static void s_dbmul(mp_digit *da, mp_digit b, mp_digit *dc,
240
240
                mp_size size_a);
241
241
 
242
242
/* Single digit division.  Replaces a with the quotient,
310
310
#if 0
311
311
/* Dump a representation of the mp_int to standard output */
312
312
void            s_print(char *tag, mp_int z);
313
 
void            s_print_buf(char *tag, mp_digit * buf, mp_size num);
 
313
void            s_print_buf(char *tag, mp_digit *buf, mp_size num);
314
314
#endif
315
315
 
316
316
/* {{{ get_default_precision() */
2294
2294
/* {{{ s_realloc(old, num) */
2295
2295
 
2296
2296
static mp_digit *
2297
 
s_realloc(mp_digit * old, mp_size num)
 
2297
s_realloc(mp_digit *old, mp_size num)
2298
2298
{
2299
2299
        mp_digit   *new = px_realloc(old, num * sizeof(mp_digit));
2300
2300
 
2375
2375
/* {{{ s_cdig(da, db, len) */
2376
2376
 
2377
2377
static int
2378
 
s_cdig(mp_digit * da, mp_digit * db, mp_size len)
 
2378
s_cdig(mp_digit *da, mp_digit *db, mp_size len)
2379
2379
{
2380
2380
        mp_digit   *dat = da + len - 1,
2381
2381
                           *dbt = db + len - 1;
2460
2460
/* {{{ s_uadd(da, db, dc, size_a, size_b) */
2461
2461
 
2462
2462
static mp_digit
2463
 
s_uadd(mp_digit * da, mp_digit * db, mp_digit * dc,
 
2463
s_uadd(mp_digit *da, mp_digit *db, mp_digit *dc,
2464
2464
           mp_size size_a, mp_size size_b)
2465
2465
{
2466
2466
        mp_size         pos;
2476
2476
        /* Add corresponding digits until the shorter number runs out */
2477
2477
        for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc)
2478
2478
        {
2479
 
                w = w + (mp_word) * da + (mp_word) * db;
 
2479
                w = w + (mp_word) *da + (mp_word) *db;
2480
2480
                *dc = LOWER_HALF(w);
2481
2481
                w = UPPER_HALF(w);
2482
2482
        }
2499
2499
/* {{{ s_usub(da, db, dc, size_a, size_b) */
2500
2500
 
2501
2501
static void
2502
 
s_usub(mp_digit * da, mp_digit * db, mp_digit * dc,
 
2502
s_usub(mp_digit *da, mp_digit *db, mp_digit *dc,
2503
2503
           mp_size size_a, mp_size size_b)
2504
2504
{
2505
2505
        mp_size         pos;
2512
2512
        for (pos = 0; pos < size_b; ++pos, ++da, ++db, ++dc)
2513
2513
        {
2514
2514
                w = ((mp_word) MP_DIGIT_MAX + 1 +               /* MP_RADIX */
2515
 
                         (mp_word) * da) - w - (mp_word) * db;
 
2515
                         (mp_word) *da) - w - (mp_word) *db;
2516
2516
 
2517
2517
                *dc = LOWER_HALF(w);
2518
2518
                w = (UPPER_HALF(w) == 0);
2522
2522
        for ( /* */ ; pos < size_a; ++pos, ++da, ++dc)
2523
2523
        {
2524
2524
                w = ((mp_word) MP_DIGIT_MAX + 1 +               /* MP_RADIX */
2525
 
                         (mp_word) * da) - w;
 
2525
                         (mp_word) *da) - w;
2526
2526
 
2527
2527
                *dc = LOWER_HALF(w);
2528
2528
                w = (UPPER_HALF(w) == 0);
2537
2537
/* {{{ s_kmul(da, db, dc, size_a, size_b) */
2538
2538
 
2539
2539
static int
2540
 
s_kmul(mp_digit * da, mp_digit * db, mp_digit * dc,
 
2540
s_kmul(mp_digit *da, mp_digit *db, mp_digit *dc,
2541
2541
           mp_size size_a, mp_size size_b)
2542
2542
{
2543
2543
        mp_size         bot_size;
2638
2638
/* {{{ s_umul(da, db, dc, size_a, size_b) */
2639
2639
 
2640
2640
static void
2641
 
s_umul(mp_digit * da, mp_digit * db, mp_digit * dc,
 
2641
s_umul(mp_digit *da, mp_digit *db, mp_digit *dc,
2642
2642
           mp_size size_a, mp_size size_b)
2643
2643
{
2644
2644
        mp_size         a,
2656
2656
                w = 0;
2657
2657
                for (b = 0; b < size_b; ++b, ++dbt, ++dct)
2658
2658
                {
2659
 
                        w = (mp_word) * da * (mp_word) * dbt + w + (mp_word) * dct;
 
2659
                        w = (mp_word) *da * (mp_word) *dbt + w + (mp_word) *dct;
2660
2660
 
2661
2661
                        *dct = LOWER_HALF(w);
2662
2662
                        w = UPPER_HALF(w);
2671
2671
/* {{{ s_ksqr(da, dc, size_a) */
2672
2672
 
2673
2673
static int
2674
 
s_ksqr(mp_digit * da, mp_digit * dc, mp_size size_a)
 
2674
s_ksqr(mp_digit *da, mp_digit *dc, mp_size size_a)
2675
2675
{
2676
2676
        if (multiply_threshold && size_a > multiply_threshold)
2677
2677
        {
2736
2736
/* {{{ s_usqr(da, dc, size_a) */
2737
2737
 
2738
2738
static void
2739
 
s_usqr(mp_digit * da, mp_digit * dc, mp_size size_a)
 
2739
s_usqr(mp_digit *da, mp_digit *dc, mp_size size_a)
2740
2740
{
2741
2741
        mp_size         i,
2742
2742
                                j;
2751
2751
                        continue;
2752
2752
 
2753
2753
                /* Take care of the first digit, no rollover */
2754
 
                w = (mp_word) * dat * (mp_word) * dat + (mp_word) * dct;
 
2754
                w = (mp_word) *dat * (mp_word) *dat + (mp_word) *dct;
2755
2755
                *dct = LOWER_HALF(w);
2756
2756
                w = UPPER_HALF(w);
2757
2757
                ++dat;
2759
2759
 
2760
2760
                for (j = i + 1; j < size_a; ++j, ++dat, ++dct)
2761
2761
                {
2762
 
                        mp_word         t = (mp_word) * da * (mp_word) * dat;
2763
 
                        mp_word         u = w + (mp_word) * dct,
 
2762
                        mp_word         t = (mp_word) *da * (mp_word) *dat;
 
2763
                        mp_word         u = w + (mp_word) *dct,
2764
2764
                                                ov = 0;
2765
2765
 
2766
2766
                        /* Check if doubling t will overflow a word */
2808
2808
        mp_digit   *da = MP_DIGITS(a);
2809
2809
        mp_size         ua = MP_USED(a);
2810
2810
 
2811
 
        w = (mp_word) * da + b;
 
2811
        w = (mp_word) *da + b;
2812
2812
        *da++ = LOWER_HALF(w);
2813
2813
        w = UPPER_HALF(w);
2814
2814
 
2815
2815
        for (ua -= 1; ua > 0; --ua, ++da)
2816
2816
        {
2817
 
                w = (mp_word) * da + w;
 
2817
                w = (mp_word) *da + w;
2818
2818
 
2819
2819
                *da = LOWER_HALF(w);
2820
2820
                w = UPPER_HALF(w);
2840
2840
 
2841
2841
        while (ua > 0)
2842
2842
        {
2843
 
                w = (mp_word) * da * b + w;
 
2843
                w = (mp_word) *da * b + w;
2844
2844
                *da++ = LOWER_HALF(w);
2845
2845
                w = UPPER_HALF(w);
2846
2846
                --ua;
2858
2858
/* {{{ s_dbmul(da, b, dc, size_a) */
2859
2859
 
2860
2860
static void
2861
 
s_dbmul(mp_digit * da, mp_digit b, mp_digit * dc, mp_size size_a)
 
2861
s_dbmul(mp_digit *da, mp_digit b, mp_digit *dc, mp_size size_a)
2862
2862
{
2863
2863
        mp_word         w = 0;
2864
2864
 
2865
2865
        while (size_a > 0)
2866
2866
        {
2867
 
                w = (mp_word) * da++ * (mp_word) b + w;
 
2867
                w = (mp_word) *da++ * (mp_word) b + w;
2868
2868
 
2869
2869
                *dc++ = LOWER_HALF(w);
2870
2870
                w = UPPER_HALF(w);
3085
3085
 
3086
3086
        for (pos = 0, zp = MP_DIGITS(z); pos < tdig; ++pos, ++zp)
3087
3087
        {
3088
 
                w = ((mp_word) MP_DIGIT_MAX + 1) - w - (mp_word) * zp;
 
3088
                w = ((mp_word) MP_DIGIT_MAX + 1) - w - (mp_word) *zp;
3089
3089
 
3090
3090
                *zp = LOWER_HALF(w);
3091
3091
                w = UPPER_HALF(w) ? 0 : 1;
3092
3092
        }
3093
3093
 
3094
 
        w = ((mp_word) MP_DIGIT_MAX + 1 + hi) - w - (mp_word) * zp;
 
3094
        w = ((mp_word) MP_DIGIT_MAX + 1 + hi) - w - (mp_word) *zp;
3095
3095
        *zp = LOWER_HALF(w);
3096
3096
 
3097
3097
        assert(UPPER_HALF(w) != 0); /* no borrow out should be possible */
3663
3663
}
3664
3664
 
3665
3665
void
3666
 
s_print_buf(char *tag, mp_digit * buf, mp_size num)
 
3666
s_print_buf(char *tag, mp_digit *buf, mp_size num)
3667
3667
{
3668
3668
        int                     i;
3669
3669