source: git/MP/MP/MP_SacBigInt.c @ 1d0eb7

fieker-DuValspielwiese
Last change on this file since 1d0eb7 was 678cfd, checked in by Olaf Bachmann <obachman@…>, 27 years ago
This commit was generated by cvs2svn to compensate for changes in r337, which included commits to RCS files with non-trunk default branches. git-svn-id: file:///usr/local/Singular/svn/trunk@338 2c84dea3-7e68-4137-9b89-c4e89433aadc
  • Property mode set to 100644
File size: 12.2 KB
Line 
1/*******************************************************************
2 *                                                                 
3 *                    MP version 1.1.2:  Multi Protocol
4 *                    Kent State University, Kent, OH
5 *                 Authors:  S. Gray, N. Kajler, P. Wang
6 *          (C) 1993, 1994, 1995, 1996, 1997 All Rights Reserved
7 *
8 *                                 NOTICE
9 *
10 *  Permission to use, copy, modify, and distribute this software and
11 *  its documentation for non-commercial purposes and without fee is
12 *  hereby granted provided that the above copyright notice appear in all
13 *  copies and that both the copyright notice and this permission notice
14 *  appear in supporting documentation.
15 * 
16 *  Neither Kent State University nor the Authors make any representations
17 *  about the suitability of this software for any purpose.  The MP Library
18 *  is distributed in the hope that it will be useful, but is provided  "as
19 *  is" and without any warranty of any kind and without even the implied 
20 *  warranty of merchantability or fitness for a particular purpose.
21 *
22 *
23 *   IMPLEMENTATION FILE:  MP_SacBigInt.c
24 *
25 *      The default BigInt package is the Gnu Multiple Precision
26 *      package.  Here we have the routines to put/get/print a SAC bigint
27 *      and to convert between the SAC and GMP bigints.
28 *
29 *   NOTE: This is a short explanation of the the way MP deals with
30 *         arbtrary precision numbers.  For now this really only applies
31 *         to Big Ints. When the sender and receiver are using the same
32 *         format, we don't want to force them to have to convert to a
33 *         common format to do the exchange.  So we provide conversion
34 *         routines for some common formats (SAC <-> GMP, PARI <-> GMP).
35 *         The BigNum format to be used is characterized by routines to
36 *         Put(), Get(), and Print() these formats.  The routines are
37 *         kept in a BigInt ops struct (see MP_Env.h).  The user may
38 *         replace the default GMP ops in an MP env with those of some
39 *         other format by calling MP_SetEnvBigIntFormat() and sending
40 *         in the address of the struct containing the proper routines
41 *         and the "name" of the format to be used.  It must be one of
42 *         the formats supported (as defined in MP_Types.h).
43 *         In any event, we want the sender to always have at least the
44 *         illusion that it is sending in its "native" format, so all
45 *         necessary conversions between representations are hidden in
46 *         supplied ops structs.  See below for examples!!!  Observe
47 *         that if SAC supported a straightforward conversion to string
48 *         routine, we wouldn't have to do all this messy convert to GMP
49 *         format first.  For TCP connections, the two endpoints negotiate
50 *         which format to use.  If both use the same format (GMP or other-
51 *         wise) then transmission should be "optimal".  But if they use
52 *         different formats, the non-GMP side (may be both sides), must
53 *         do conversions.  For other transport devices (e.g., files,
54 *         PVM, ToolBus), there is no negotiation.  There is no miracle
55 *         here, the programmer must be aware of the needs of the other
56 *         applications involved and know if they all support the same
57 *         format, setting the environment accordingly.
58 *         --> BTW: This approach is consistent with and similar to how
59 *             we deal with new transport devices.
60 *
61 *  Change Log:
62 *      4/22/96 sgray Life begins for this file.
63 *      4/23/96 sgray Completed and tested.  Seems okay. :-)
64 *
65 ************************************************************************/
66
67#ifndef lint
68static char vcid[] = "@(#) $Id: MP_SacBigInt.c,v 1.1.1.1 1997-05-25 20:31:47 obachman Exp $";
69#endif /* lint */
70
71#include "MP.h"
72
73#ifdef MP_HAVE_SAC
74
75/*#define MP_DEBUG */
76
77MP_BigIntOps_t imp_sac_bigint_ops = {
78  IMP_PutSacBigInt,
79  IMP_GetSacBigInt,
80  IMP_SacBigIntToStr,
81  IMP_SacBigIntAsciiSize
82};
83
84#if MP_DEFAULT_APINT_FORMAT == MP_SAC
85MP_BigIntOps_t imp_default_bigint_ops = {
86  IMP_PutSacBigInt,
87  IMP_GetSacBigInt,
88  IMP_SacBigIntToStr,
89  IMP_SacBigIntAsciiSize
90};
91MP_BigNumFormat_t imp_default_bigint_format = MP_SAC;
92#endif
93
94
95/*
96 * macro to determine if the GMP bignum is negative
97 */
98#define mpz_is_neg(mp_int) ((mp_int->_mp_size < 0))
99
100
101/*
102 * sac_to_gmp() assumes that the incoming integer really is a bignum and is
103 * not representable as a machine precision integer.  If the argument sac is
104 * machine precision, the while loop becomes infinite (this is bad).
105 *
106 * On entry I also assume that the caller has initialized gmp_int.
107 */
108static void sac_to_gmp(mpz_ptr gmp_int, Word sac)
109{
110    short set_neg_flag = -1; /* when set, this will be 0 or 1 */
111    MP_INT pwr, temp;
112    Word lsac, d;
113#ifdef MP_DEBUG   
114    fprintf(stderr, "sac_to_gmp: entering, the bignum here is ");
115    IWRITE(sac);printf("\n"); fflush(stderr);
116#endif
117
118    if (ISATOM(sac)) {
119      if (sac < 0) {
120         set_neg_flag = 1;
121         sac = -sac;
122         }
123      else set_neg_flag = 0;
124      mpz_set_si(gmp_int, (int) sac);
125      if (set_neg_flag) mpz_neg(gmp_int, gmp_int);
126      return;
127     }
128    ADV(sac, &d, &lsac);
129    mpz_init(&pwr); mpz_set_si(&pwr, 1);
130   
131    if (d != 0) {
132      set_neg_flag = (d < 0) ? 1 : 0;
133      if (set_neg_flag) d = -d;
134      }
135
136    mpz_set_si(gmp_int, d);
137    mpz_init(&temp);
138    while (!ISNIL(lsac)) {
139        mpz_mul_ui(&pwr, &pwr, BETA);
140        ADV(lsac, &d, &lsac);
141        if (d != 0) {
142            mpz_clear(&temp); 
143            /* Argh!!  We need to keep checking because we may have
144               had all leading zeroes to this point! */
145            if (set_neg_flag == -1) set_neg_flag = (d < 0) ? 1 : 0;
146            if (set_neg_flag) d = -d;
147            mpz_mul_ui(&temp, &pwr, d);
148            mpz_add(gmp_int, gmp_int, &temp);
149        }
150    }
151    if (set_neg_flag) mpz_neg(gmp_int, gmp_int);
152
153#ifdef MP_DEBUG
154    fprintf(stderr,"sac_to_gmp: exiting\n");fflush(stderr);
155#endif
156   return;
157}
158
159
160
161static void gmp_to_sac(Word *sac_int, mpz_ptr gmp_int)
162{
163    MP_INT  n, q, r;
164    Word    i = 0;
165    long    d;
166    short   set_neg_flag = mpz_is_neg(gmp_int);
167
168    if (abs(gmp_int->_mp_size) == 1) {
169      d = mpz_get_si(gmp_int);
170      if (set_neg_flag && (d > 0)) d = -d;
171      if (abs(d) < BETA) {
172        *sac_int = d;
173        return;
174        }
175    }
176    mpz_init(&n); 
177    mpz_set(&n, gmp_int);
178    mpz_init(&q); mpz_init(&r);
179    if (set_neg_flag) n._mp_size = -n._mp_size;
180    *sac_int = NIL;
181    while (1) {
182        d = mpz_fdiv_qr_ui(&q, &r, &n, BETA);
183        if (set_neg_flag && (d > 0)) d = -d;
184        *sac_int =  LEINST(*sac_int, i, d); i++;
185        d = mpz_cmp_si(&q, BETA);
186        if (mpz_cmp_si(&q, BETA) < 0) 
187            break; 
188        mpz_clear(&n);
189        mpz_set(&n, &q);
190    }
191    /*
192     * now get the last value from q
193     */
194    d = mpz_get_si(&q);
195    if (set_neg_flag && (d > 0)) d = -d;
196    *sac_int = LEINST(*sac_int, i, d); 
197}
198
199
200
201/* Generic routine to recursively put a SAC list */
202#ifdef __STDC__
203int IMP_PutSacList(MP_Link_pt link,
204                   Word L)
205#else
206int IMP_PutSacList(link, L)
207    MP_Link_pt link;
208    Word L;
209#endif
210{
211#ifdef MP_DEBUG
212    fprintf(stderr, "IMP_PutSacList: entering\n"); fflush(stderr);
213#endif
214
215    if ( L == NIL || ISATOM(L) ) { /* Packing atom*/
216        if (MP_PutSint32Packet(link, L, 0) != MP_Success)
217            return(-1);
218    }
219    else {                       /* Packing s-exp*/
220        if (MP_PutCommonOperatorPacket(link, MP_BasicDict, 
221                   MP_CopBasicList, 0, 1)
222            != MP_Success)
223            return(-1);
224        if (IMP_PutSacList(link, FIRST(L)) < 0 ) 
225            return(-1);
226        if (IMP_PutSacList(link, RED(L)) < 0 )
227            return(-1);
228    }
229
230#ifdef MP_DEBUG
231   fprintf(stderr, "IMP_PutSacList: exiting\n");  fflush(stderr);
232#endif
233
234    return(0);
235}
236
237
238
239#ifdef __STDC__
240Word IMP_GetSacList(MP_Link_pt link)
241#else
242Word IMP_GetSacList(link)
243    MP_Link_pt link;
244#endif
245{
246    Word a, b;
247    MP_NodeType_t ntype;
248    MP_NumAnnot_t na;
249    MP_NumChild_t nc;
250    MP_DictTag_t  dtag;
251    MP_Common_t   cv;
252#ifdef MP_DEBUG
253     fprintf(stderr, "IMP_GetSacList: entering\n");fflush(stderr); 
254#endif
255
256    if (IMP_GetNodeHeader(link, &ntype, 
257                          &dtag, &cv, &na, &nc) != MP_Success){
258        MP_PrintError(link);
259        return(-1); 
260    }
261    if (ntype == MP_Sint32Type) {  /* Unpack atom */
262        if (IMP_GetSint32(link, (MP_Sint32_t *) &a) != MP_Success) {
263          MP_PrintError(link);
264          return -1;
265          }
266        return(a);
267        }
268    else if (ntype == MP_CommonOperatorType && dtag == MP_BasicDict &&
269                   cv == MP_CopBasicList) { 
270        /* Unpack s-exp */
271        a = IMP_GetSacList(link);
272        b = IMP_GetSacList(link);
273        return(COMP(a,b));
274    } else { /* error */
275        fprintf(stderr, "IMP_GetSacList: invalid s-expression\n");
276        fflush(stderr);
277        return -1;
278      }
279}
280
281
282
283#ifdef __STDC__
284MP_Status_t IMP_PutSacBigInt(MP_Link_pt link, MP_ApInt_t sac_int)
285#else
286MP_Status_t IMP_PutSacBigInt(link, sac_int)
287    MP_Link_pt link;
288    MP_ApInt_t sac_int;
289#endif
290{
291    Word n = *((Word *)sac_int);
292    MP_INT  gmp_int;
293#ifdef MP_DEBUG
294    fprintf(stderr, "IMP_PutSacBigInt: entering, n is \n");fflush(stderr);
295    IWRITE (n); printf("\n"); fflush(stdout);
296#endif
297
298    if (link->link_bigint_format == MP_SAC) 
299        return(IMP_PutSacList(link, n));
300    else {
301        mpz_init(&gmp_int);
302        sac_to_gmp(&gmp_int, n);
303        ERR_CHK(IMP_PutGmpInt(link, (MP_ApInt_t)&gmp_int));
304        mpz_clear(&gmp_int);  /* sloppy, we don't cleanup on failure */
305    }
306    RETURN_OK(link);
307}
308
309
310
311
312#ifdef __STDC__
313MP_Status_t IMP_GetSacBigInt(MP_Link_pt link, MP_ApInt_pt sac_int)
314#else
315MP_Status_t IMP_GetSacBigInt(link, sac_int)
316    MP_Link_pt link;
317    MP_ApInt_pt sac_int;
318#endif
319{
320    mpz_ptr gmp_int = NULL;
321    Word    sac_tmp = 0, *sacptr;
322
323#ifdef MP_DEBUG
324    fprintf(stderr,"IMP_GetSacBigInt: entering\n");
325    fprintf(stderr, "\tbigint_format is %d\n", link->link_bigint_format);
326    fflush(stderr);
327#endif
328
329
330    if (link->link_bigint_format == MP_SAC) {
331        sacptr = (Word *)*sac_int; 
332        *sacptr = IMP_GetSacList(link);
333        if (*sacptr == -1) 
334            return MP_Failure; 
335        else 
336          RETURN_OK(link); 
337    } else {
338        ERR_CHK(IMP_GetGmpInt(link, (MP_ApInt_t *)&gmp_int));
339/*          gmp_to_sac((Word *)sac_int, gmp_int);  */
340         gmp_to_sac((Word)*((Word *)sac_int), gmp_int); 
341        mpz_clear(gmp_int);  /* sloppy, we don't cleanup on failure */
342    }
343
344#ifdef MP_DEBUG
345    fprintf(stderr, "IMP_GetSacBigInt: returning\n");fflush(stderr);
346#endif
347
348    RETURN_OK(link);
349}
350
351
352
353char * 
354#ifdef __STDC__
355IMP_SacBigIntToStr(MP_ApInt_t big_int, char *buffer)
356#else
357IMP_SacBigIntToStr(big_int, buffer)
358MP_ApInt_t  big_int;
359char       *buffer;
360#endif
361{
362    MP_INT gmp_int;
363#ifdef MP_DEBUG
364    fprintf(stderr,"IMP_SacBigIntToStr: entering.\n");
365    fflush(stderr);  fprintf(stderr, "\tthe bignum is ");
366    IWRITE(*(Word*)big_int);fprintf(stderr, "\n");fflush(stdout);
367#endif
368
369    mpz_init(&gmp_int);
370    sac_to_gmp(&gmp_int, *(Word*)big_int); 
371    mpz_get_str(buffer, 10, &gmp_int);
372    mpz_clear(&gmp_int);
373
374#ifdef MP_DEBUG
375    fprintf(stderr,"IMP_SacBigIntToStr: exiting\n");fflush(stderr);
376#endif
377
378    return buffer;
379}
380
381
382#ifdef __STDC__
383long IMP_SacBigIntAsciiSize(MP_ApInt_t mp_apint)
384#else
385long IMP_SacBigIntAsciiSize(mp_apint)
386    MP_ApInt_t mp_apint;
387#endif
388{
389  int len = 0;
390  Word tmp = *((Word *)mp_apint);
391
392  if (ISATOM(tmp)) return 9;
393
394  len = LENGTH(tmp);
395  return len * 9;
396}
397
398
399
400char * OLD_IMP_SacBigIntToStrOriginal(MP_Link_pt link, MP_ApInt_t big_int,
401 int direction)
402{
403    char *str = NULL;
404    mpz_ptr gmp_int = NULL;
405
406
407    fprintf(stderr,"IMP_SacBigIntToStr: entering\n");
408    if (direction == MP_SEND || 
409        link->link_bigint_format == MP_SAC) {
410        fprintf(stderr,"\thave to convert - SAC format\n");
411        mpz_init(gmp_int);
412        sac_to_gmp(gmp_int, *((Word *)big_int));
413        printf("\tdone conversion\n");
414        str = mpz_get_str(NULL, 10, gmp_int);
415        printf("\thave the string, cleaning up\n");
416        mpz_clear(gmp_int);
417    } else {  /* must be receiving in GMP format */
418        fprintf(stderr,"\tdont' have to convert - GMP format\n");
419        str = mpz_get_str(NULL, 10, (mpz_ptr)big_int);
420    }
421    fprintf(stderr,"IMP_SacBigIntToStr: exiting\n");fflush(stderr);
422 
423    return str;
424}
425
426
427#endif /* MP_HAVE_SAC */
Note: See TracBrowser for help on using the repository browser.