Annotation of OpenXM_contrib2/asir2000/engine-27/ddN-27.c, Revision 1.2
1.2 ! noro 1: /*
! 2: * Copyright (c) 1994-2000 FUJITSU LABORATORIES LIMITED
! 3: * All rights reserved.
! 4: *
! 5: * FUJITSU LABORATORIES LIMITED ("FLL") hereby grants you a limited,
! 6: * non-exclusive and royalty-free license to use, copy, modify and
! 7: * redistribute, solely for non-commercial and non-profit purposes, the
! 8: * computer program, "Risa/Asir" ("SOFTWARE"), subject to the terms and
! 9: * conditions of this Agreement. For the avoidance of doubt, you acquire
! 10: * only a limited right to use the SOFTWARE hereunder, and FLL or any
! 11: * third party developer retains all rights, including but not limited to
! 12: * copyrights, in and to the SOFTWARE.
! 13: *
! 14: * (1) FLL does not grant you a license in any way for commercial
! 15: * purposes. You may use the SOFTWARE only for non-commercial and
! 16: * non-profit purposes only, such as academic, research and internal
! 17: * business use.
! 18: * (2) The SOFTWARE is protected by the Copyright Law of Japan and
! 19: * international copyright treaties. If you make copies of the SOFTWARE,
! 20: * with or without modification, as permitted hereunder, you shall affix
! 21: * to all such copies of the SOFTWARE the above copyright notice.
! 22: * (3) An explicit reference to this SOFTWARE and its copyright owner
! 23: * shall be made on your publication or presentation in any form of the
! 24: * results obtained by use of the SOFTWARE.
! 25: * (4) In the event that you modify the SOFTWARE, you shall notify FLL by
! 26: * e-mail at risa-admin@flab.fujitsu.co.jp of the detailed specification
! 27: * for such modification or the source code of the modified part of the
! 28: * SOFTWARE.
! 29: *
! 30: * THE SOFTWARE IS PROVIDED AS IS WITHOUT ANY WARRANTY OF ANY KIND. FLL
! 31: * MAKES ABSOLUTELY NO WARRANTIES, EXPRESSED, IMPLIED OR STATUTORY, AND
! 32: * EXPRESSLY DISCLAIMS ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS
! 33: * FOR A PARTICULAR PURPOSE OR NONINFRINGEMENT OF THIRD PARTIES'
! 34: * RIGHTS. NO FLL DEALER, AGENT, EMPLOYEES IS AUTHORIZED TO MAKE ANY
! 35: * MODIFICATIONS, EXTENSIONS, OR ADDITIONS TO THIS WARRANTY.
! 36: * UNDER NO CIRCUMSTANCES AND UNDER NO LEGAL THEORY, TORT, CONTRACT,
! 37: * OR OTHERWISE, SHALL FLL BE LIABLE TO YOU OR ANY OTHER PERSON FOR ANY
! 38: * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, PUNITIVE OR CONSEQUENTIAL
! 39: * DAMAGES OF ANY CHARACTER, INCLUDING, WITHOUT LIMITATION, DAMAGES
! 40: * ARISING OUT OF OR RELATING TO THE SOFTWARE OR THIS AGREEMENT, DAMAGES
! 41: * FOR LOSS OF GOODWILL, WORK STOPPAGE, OR LOSS OF DATA, OR FOR ANY
! 42: * DAMAGES, EVEN IF FLL SHALL HAVE BEEN INFORMED OF THE POSSIBILITY OF
! 43: * SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY. EVEN IF A PART
! 44: * OF THE SOFTWARE HAS BEEN DEVELOPED BY A THIRD PARTY, THE THIRD PARTY
! 45: * DEVELOPER SHALL HAVE NO LIABILITY IN CONNECTION WITH THE USE,
! 46: * PERFORMANCE OR NON-PERFORMANCE OF THE SOFTWARE.
! 47: *
! 48: * $OpenXM: OpenXM_contrib2/asir2000/engine-27/ddN-27.c,v 1.1.1.1 1999/12/03 07:39:08 noro Exp $
! 49: */
1.1 noro 50: #include "ca-27.h"
51: #include "base.h"
52: #include "inline.h"
53:
54: void divn_27(n1,n2,nq,nr)
55: N n1,n2,*nq,*nr;
56: {
57: int tmp;
58: int br;
59: int j,d,d1,d2,dd;
60: int *m1,*m1e,*m2,*mr;
61: N q,r;
62:
63: if ( !n2 )
64: error("divn: division by 0");
65: else if ( !n1 ) {
66: *nq = 0; *nr = 0;
67: } else if ( UNIN(n2) ) {
68: *nq = n1; *nr = 0;
69: } else if ( (d1 = PL(n1)) < (d2 = PL(n2)) ) {
70: *nr = n1; *nq = 0;
71: } else if ( d2 == 1 ) {
72: if ( d1 == 1 ) {
73: DQR(BD(n1)[0],BD(n2)[0],br,tmp)
74: STON(br,*nq); STON(tmp,*nr);
75: } else {
76: tmp = divin_27(n1,BD(n2)[0],nq); STON(tmp,*nr);
77: }
78: return;
79: } else if ( (d1 == d2) && ((tmp = cmpn(n1,n2)) <= 0) )
80: if ( !tmp ) {
81: *nr = 0; *nq = ONEN;
82: } else {
83: *nr = n1; *nq = 0;
84: }
85: else {
86: d = BASE27/(BD(n2)[d2-1] + 1); dd = d1-d2;
87: m1 = W_ALLOC(d1+1); m2 = W_ALLOC(d2+1);
88: mulin_27(n1,d,m1); mulin_27(n2,d,m2);
89: *nq = q = NALLOC(dd+1);
90: divnmain_27(d1,d2,m1,m2,BD(q));
91: PL(q) = (BD(q)[dd]?dd+1:dd);
92: for ( j = d2-1; (j >= 0) && (m1[j] == 0); j--);
93: if ( j == -1 )
94: *nr = 0;
95: else {
96: *nr = r = NALLOC(j+1);
97: for ( br = 0, m1e = m1+j, mr = BD(r)+j;
98: m1e >= m1; m1e--, mr-- ) {
99: DSAB27(d,br,*m1e,*mr,br)
100: }
101: PL(r) = (BD(r)[j]?j+1:j);
102: }
103: }
104: }
105:
106: void divnmain_27(d1,d2,m1,m2,q)
107: int d1,d2;
108: int *m1,*m2,*q;
109: {
110: unsigned int tmp;
111: int *n1,*n2;
112: int i,j;
113: int l,r;
114: int u,qhat;
115: int v1,v2;
116:
117: v1 = m2[d2-1]; v2 = m2[d2-2];
118: for ( j = d1-d2, m1 += j, q += j; j >= 0; j--, q--, m1-- ) {
119: n1 = m1+d2; n2 = m1+d2-1;
120: if ( *n1 == v1 ) {
121: qhat = BASE27 - 1; r = *n1 + *n2;
122: } else {
123: DSAB27(v1,*n1,*n2,qhat,r)
124: }
125: DM27(v2,qhat,u,l)
126: while ( 1 ) {
127: if ((r > u) || ((r == u) && (*(n1-2) >= l)))
128: break;
129: if ( ( l -= v2 ) < 0 ) {
130: l += BASE27; u--;
131: }
132: r += v1; qhat--;
133: }
134: if ( qhat ) {
135: for ( i = d2, u = 0, n1 = m1, n2 = m2; i > 0; i--, n1++, n2++ ) {
136: DMA27(*n2,qhat,u,u,l)
137: if ( (l = *n1 - l) < 0 ) {
138: u++; *n1 = l + BASE27;
139: } else
140: *n1 = l;
141: }
142: if ( *n1 < u ) {
143: for ( i = d2, qhat--, r = 0, n1 = m1, n2 = m2;
144: i > 0; i--, n1++, n2++ ) {
145: l = *n1 + *n2 + r; *n1 = l % BASE27; r = l / BASE27;
146: }
147: }
148: *n1 = 0;
149: }
150: *q = qhat;
151: }
152: }
153:
154: void mulin_27(n,d,p)
155: N n;
156: int d;
157: int *p;
158: {
159: int carry;
160: int *m,*me;
161:
162: bzero((char *)p,(int)((PL(n)+1)*sizeof(int)));
163: for ( carry = 0, m = BD(n), me = m+PL(n); m < me; p++, m++ ) {
164: carry += *p;
165: DMA27(*m,d,carry,carry,*p)
166: }
167: *p = carry;
168: }
169:
170: int divin_27(n,dvr,q)
171: N n;
172: int dvr;
173: N *q;
174: {
175: int up,d;
176: int *m,*mq,*md;
177: N nq;
178:
179: d = PL(n); m = BD(n);
180: if ( ( d == 1 ) && ( dvr > *m ) ) {
181: *q = 0;
182: return( *m );
183: }
184: *q = nq = NALLOC(d);
185: for ( md = m+d-1, mq = BD(nq)+d-1, up = 0; md >= m; md--, mq-- ) {
186: DSAB27(dvr,up,*md,*mq,up)
187: }
188: PL(nq) = (BD(nq)[d-1]?d:d-1);
189: return ( up );
190: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>