![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to adbig.s CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 3BSD / cmd / lisp|
Return to adbig.s CVS log | Up to [CSRG BSD Unix] / 3BSD / cmd / lisp |
1.1 root 1:
2: # bignum add routine
3: # basic data representation is each bigit is a positive number
4: # less than 2^30, except for the leading bigit, which is in
5: # the range -2^30 < x < 2^30.
6:
7: .globl _adbig
8: .globl Bexport
9: .globl backfr
10: #
11: # Initialization section
12: #
13: _adbig: .word 0x0fc0 #save registers 6-11
14: movl 4(ap),r1 #arg1 = addr of 1st bignum
15: movl 8(ap),r2 #arg2 = addr of 2nd bignum
16: clrl r5 #r5 = carry
17: movl $0xC0000000,r4 #r4 = clear constant.
18: movl sp,r10 #save start address of bignum on stack.
19: #note well that this is 4 above the actual
20: #low order word.
21: #
22: # first loop is to waltz through both bignums adding
23: # bigits, pushing them onto stack.
24: #
25: loop1: addl3 (r1),(r2),r0 #add bigits
26: addl2 r5,r0 #add carry
27: bicl3 r4,r0,-(sp) #save sum, no overflow possible
28: extv $30,$2,r0,r5 #sign extend two high order bits
29: #to be next carry.
30: movl 4(r1),r1 #get cdr
31: bleq out1 #negative indicates end of list.
32: movl 4(r2),r2 #get cdr of second bignum
33: bgtr loop1 #if neither list at end, do it again
34: #
35: # second loop propagates carries through higher order words.
36: # It assumes remaining list in r1.
37: #
38: loop2: addl3 (r1),r5,r0 #add bigits and carry
39: bicl3 r4,r0,-(sp) #save sum, no overflow possible
40: extv $30,$2,r0,r5 #sign extend two high order bits
41: #to be next carry.
42: movl 4(r1),r1 #get cdr
43: out2: bgtr loop2 #negative indicates end of list.
44: out2a: pushl r5
45: #
46: # suppress unnecessary leading zeroes and -1's
47: #
48: iexport:movl sp,r11 #more set up for output routine
49: ckloop:
50: Bexport:tstl (r11) #look at leading bigit
51: bgtr copyit #if positive, can allocate storage etc.
52: blss negchk #if neg, still a chance we can get by
53: cmpl r11,r10 #check to see that
54: bgeq copyit #we don't pop everything off of stack
55: tstl (r11)+ #incr r11
56: brb ckloop #examine next
57: negchk:
58: mcoml (r11),r3 #r3 is junk register
59: bneq copyit #short test for -1
60: tstl 4(r11) #examine next bigit
61: beql copyit #if zero must must leave as is.
62: cmpl r11,r10 #check to see that
63: bgeq copyit #we don't pop everything off of stack
64: tstl (r11)+ #incr r11
65: bisl2 r4,(r11) #set high order two bits
66: brb negchk #try to supress more leading -1's
67: #
68: # The following code is an error exit from the first loop
69: # and is out of place to avoid a jump around a jump.
70: #
71: out1: movl 4(r2),r1 #get next addr of list to continue.
72: brb out2 #if second list simult. exhausted, do
73: #right thing.
74: #
75: # loop3 is a faster version of loop2 when carries are no
76: # longer necessary.
77: #
78: loop3a: pushl (r1) #get datum
79: loop3: movl 4(r1),r1 #get cdr
80: bgtr loop3a #if not at end get next cell
81: brb out2a
82:
83: #
84: # create linked list representation of bignum
85: #
86: copyit: subl3 r11,r10,r2 #see if we can get away with allocating an int
87: bneq on1 #test for having popped everything
88: subl3 $4,r10,r11 #if so, fix up pointer to bottom
89: brb intout #and allocate int.
90: on1: cmpl r2,$4 #if = 4, then can do
91: beql intout
92: calls $0,_newsdot #get new cell for new bignum
93: backfr: movl r0,(r6)+ #push address of cell on
94: #arg stack to save from garbage collection.
95: #There is guaranteed to be slop for a least one
96: #push without checking.
97: movl r0,r8 #r8 = result of adbig
98: loop4: movl -(r10),(r0) #save bigit
99: movl r0,r9 #r9 = old cell, to link
100: cmpl r10,r11 #have we copy'ed all the bigits?
101: bleq done
102: calls $0,_newsdot #get new cell for new bignum
103: movl r0,4(r9) #link new cell to old
104: brb loop4
105: done:
106: clrl 4(r9) #indicate end of list with 0
107: movl -(r6),r0 #give resultant address.
108: ret
109: #
110: # export integer
111: #
112: intout: pushl (r11)
113: calls $1,_inewint
114: ret
115: .globl _mulbig
116: #
117: # bignum multiplication routine
118: #
119: # Initialization section
120: #
121: _mulbig:.word 0x0fc0 #save regs 6-11
122: movl 4(ap),r1 #get address of first bignum
123: movl sp,r11 #save top of 1st bignum
124: mloop1: pushl (r1) #get bigit
125: movl 4(r1),r1 #get cdr
126: bgtr mloop1 #repeat if not done
127: movl sp,r10 #save bottom of 1st bignum, top of 2nd bignum
128:
129: movl 8(ap),r1 #get address of 2nd bignum
130: mloop2: pushl (r1) #get bigit
131: movl 4(r1),r1 #get cdr
132: bgtr mloop2 #repeat if not done
133: movl sp,r9 #save bottom of 2nd bignum
134: subl3 r9,r11,r6 #r6 contains sum of lengths of bignums
135: subl2 r6,sp
136: movl sp,r8 #save bottom of product bignum
137: #
138: # Actual multiplication
139: #
140: m1: movc5 $0,(r8),$0,r6,(r8)#zap out stack space
141: movl r9,r7 #r7 = &w[j +n] (+4 for a.d.) through calculation
142: subl3 $4,r10,r4 #r4 = &v[j]
143:
144: m3: movl r7,r5 #r7 = &w[j+n]
145: subl3 $4,r11,r3 #r3 = &u[i]
146: clrl r2 #clear carry.
147:
148: m4: addl2 -(r5),r2 #add w[i + j] to carry (no ofl poss)
149: emul (r3),(r4),r2,r0 #r0 = u[i] * v[j] + sext(carry)
150: extzv $0,$30,r0,(r5) #get new bigit
151: extv $30,$32,r0,r2 #get new carry
152:
153: m5: acbl r10,$-4,r3,m4 #r3 =- 4; if(r3 >= r10) goto m4; r10 = &[u1];
154: movl r2,-(r5) #save w[j] = carry
155:
156: m6: subl2 $4,r7 #add just &w[j+n] (+4 for autodec)
157: acbl r9,$-4,r4,m3 #r4 =- 4; if(r4>=r9) goto m5; r9 = &v[1]
158:
159: movl r9,r10 #set up for output routine
160: movl $0xC0000000,r4 #r4 = clear constant.
161: movq 20(fp),r6 #restor _np and _lbot !
162: brw iexport #do it!
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.