<<<--- % Author M.Ruckert LOC Data_Segment m IS 3 n IS 2 GREG @ U OCTA 0,0,0,0,1,#FF00FF m + n V OCTA 12,0,#EE00EE n Q OCTA 7,7,7,7,#DD00DD m+1 LOC #100 Main LDA $1,U LDA $2,V LDA $3,Q SET $4,m+n SET $5,n PUSHJ $0,:Classic:Div TRAP 0,Halt,0 PREFIX :LeadingZeros: % Count leading zeros see execise 43. in Section $1.3.1^\prime$ x IS $0 Parameter magic IS $1 Local Variables xm1 IS $2 :LeadingZeros SETL magic,#4080 INCML magic,#1020 INCMH magic,#0408 INCH magic,#0102 MOR x,x,magic; MOR x,magic,x Reverse $x$. SUBU xm1,x,1; SADD $0,xm1,x Count trailing zeros. POP 1,0 PREFIX :ShiftLeft: % Shift left array \.X of \.n octabyte by \.d bit. Return last \.{carry}. X IS $0 Parameter n IS $1 d IS $2 i IS $1 shares register with \.n dm IS $3 $64-d$ carry IS $4 Return value xi IS $5 tmp IS $6 :ShiftLeft NEG dm,64,d Shift $x$ left $d$ bits. SET carry,0 8ADDU X,n,X; SLU i,n,3; NEG i,i 0H LDOU xi,X,i Load $x_i$. SLU tmp,xi,d; OR tmp,tmp,carry Shift and add carry. STOU tmp,X,i Store $x_i$ SRU carry,xi,dm New carry. ADD i,i,8 PBN i,0B SET $0,carry POP 1,0 PREFIX :ShiftRight: % Shift left array \.X of \.n octabyte by \.d bit. Return last \.{carry}. X IS $0 Parameter n IS $1 d IS $2 i IS $1 shares register with \.n dm IS $3 $64-d$ carry IS $4 Return value xi IS $5 tmp IS $6 :ShiftRight NEG dm,64,d Shift $x$ right $d$ bits. SET carry,0 8ADDU X,n,X; SLU i,n,3; NEG i,i $i\is 0$ 0H LDOU xi,X,i Load $x_i$. SRU tmp,xi,d; OR tmp,tmp,carry Shift and add carry. STOU tmp,X,i Store $x_i$ SLU carry,xi,dm New carry. ADD i,i,8 PBN i,0B SET $0,carry POP 1,0 PREFIX :Classic: U IS $0 Parameters. V IS $1 Q IS $2 nu IS $3 m IS $3 Alias for nu n IS $4 return IS $5 vn1 IS $6 Local variables. vn2 IS $7 d IS $8 c IS $9 u IS $10 j IS $11 Uj IS $12 qh IS $13 rh IS $14 p0 IS $15 p1 IS $16 i IS $17 ujn IS $18 t IS $29 rH IS :rH Import rD IS :rD rR IS :rR rJ IS :rJ LeadingZeros IS :LeadingZeros ShiftLeft IS :ShiftLeft ShiftRight IS :ShiftRight --->>> Div GET return,rJ \hfil 1 & SET ujn,0 \hfil 1 &\ul{\sl D1.~Normalize.} SUB t,n,1; SL t,t,3 \hfil 2 & LDOU d+1,V,t \hfil 1 & PUSHJ d,LeadingZeros \hfil 8 &See exercise $1.3.1^\prime$-43. BZ d,2F \hfil 1 & SET t+1,V; SET t+2,n \hfil 2 & SET t+3,d \hfil 1 & PUSHJ t,ShiftLeft &See exercise 25. SET t+1,U; SET t+2,nu \hfil 2 & SET t+3,d \hfil 1 & PUSHJ t,ShiftLeft &See exercise 25. SET ujn,t \hfil 1 &Keep carry. 2H 8ADDU V,n,V \hfil 1 &\ul{\sl D2.~Initialize $j$.} NEG t,8; LDOU vn1,V,t \hfil 2 & NEG t,16; LDOU vn2,V,t \hfil 2 & SUB m,nu,n \hfil 1 &Get $m$ from the size of $u$ and $v$ SET j,m \hfil 1 & 8ADDU Uj,j,U; 8ADDU Uj,n,Uj \hfil 2 &$U_j\is U+8(j+n)$ JMP 0F \hfil 1 &Skip loading $u_{j+n}$. 3H LDOU ujn,Uj,0 \hfil $m$ &\ul{\sl D3.~Calculate $\hat{q}$.} 0H NEG t,8; LDOU u,Uj,t \hfil $2(m+1)$ &Get $u_{j+n-1}$ CMPU t,ujn,vn1 \hfil $m+1$ &If $u_{j+n}\ge v_{n-1}$ then $\hat{q}\ge b$ BN t,Small \hfil $m+1$ & Large SUB ujn,ujn,vn1 \hfil $m+1$ &Case $u_{j+n}\ge v_{n-1}$ PUT rD,ujn \hfil \hfil $m+1$ & DIVU qh,u,vn1; SET qh,0 \hfil $61(m+1)$ &$\hat{q}\is b$ GET rh,rR \hfil $m+1$ & JMP Adjust \hfil $m+1$ & Small PUT rD,ujn \hfil $m+1$ &Case $u_{j+n} < v_{n-1}$ DIVU qh,u,vn1 \hfil $60(m+1)$ &$\hat{q}\is lfloor (u_{j+n}b+u_{j+n-1})/v_{n-1}\rfloor$ GET rh,rR \hfil $m+1$ &$\hat{r}\is \cdots \bmod v_{n-1}$ Test MULU p0,qh,vn2 \hfil $10(m+1)$ &$p_1b+p_0 \is \hat{q}v_{n-2}$ GET p1,rH \hfil $m+1$ & CMPU t,p1,rh \hfil $m+1$ &Compare high 64 bits. BN t,4F; BP t,Adjust \hfil $m+1$ & NEG t,16; LDOU u,Uj,t \hfil $2(m+1)$ &Load $u_{j+n-2}$. CMPU t,p0,u; BN t,4F \hfil $2(m+1)$ &Compare low 64 bits. Adjust SUBU qh,qh,1 \hfil $m+1$ &Decrease $\hat{q}$. ADDU rh,rh,vn1 \hfil $m+1$ &Tentatively add $\hat{r}+ v_{n-1}$ CMPU t,rh,vn1 \hfil $m+1$ &Check if overflow BNN t,Test \hfil $m+1$ &If not, repeat the test. % & \ul{\sl D4.~Multiply and subtract.} 4H SL i,n,3; NEG i,i \hfil $2(m+1)$ &$i \is -8n$ SET c,0 \hfil $m+1$ &$\hbox{carry} \is 0$ 0H LDOU t,Uj,i \hfil $n(m+1)$ & Load $u_{j+i}$. SUBU u,t,c \hfil $n(m+1)$ &$u_{j+i}\is u_{j+i}-\hbox{carry}$ CMPU t,t,c; ZSN c,t,1 \hfil $2n(m+1)$ &Carry? LDOU t,V,i \hfil $n(m+1)$ & MULU p0,t,qh \hfil $10n(m+1)~~$ & CMPU t,u,p0; CSN c,t,1 \hfil $n(m+1)$ &Carry? SUBU u,u,p0 \hfil $n(m+1)$ &$u_{j+i}\is u_{j+i}-\hat{q}v_i$ GET p1,rH; ADDU c,c,p1 \hfil $2n(m+1)$~~ &Carry from the multiplication STOU u,Uj,i \hfil $n(m+1)$ & ADD i,i,8 \hfil $n(m+1)$ & PBN i,0B \hfil $n(m+1)$ &Repeat for $0\le i < n$ SUBU u,ujn,c \hfil $m+1$ & Complete D4 for $i=n$. CMPU t,ujn,c; ZSN c,t,1 \hfil $2(m+1)$ & CMP t,j,m; BNN t,0F \hfil $1(m+1)$ &Store unless $j=m$ STOU u,Uj,i \hfil $m+1$ &$u{j+n}\is u_{j+i}+0+\hbox{carry}$ 0H PBZ c,5F \hfil $m+1$ &\ul{\sl D5.~Test remainder.} SUB qh,qh,1 &\ul{\sl D6.~Add back.} SL t,j,3 & STOU qh,Q,j & SL i,n,3; NEG i,i &$i \is -8n$ SET c,0 &$\hbox{carry} \is 0$ 0H LDOU u,Uj,i; ADDU u,u,c &$u_{j+i}\is u_{j+i}+\hbox{carry}$ ZSZ c,u,c &Carry? LDOU t,V,i; ADDU u,u,t &$u_{j+i}\is u_{j+i}+v_i$ CMPU t,u,t; CSN c,t,1 &Carry? STOU u,Uj,i & ADD i,i,8 & PBN i,0B &Probably $j<0$. LDOU u,Uj,i; ADDU u,u,c & STOU u,Uj,i &$u{j+n}\is u_{j+i}+0+\hbox{carry}$ JMP 7F & 5H SL t,j,3 \hfil $m+1$ &\ul{\sl D5.~Test remainder.} (continued) STOU qh,Q,t \hfil $m+1$ &$q_j\is \hat{q}$ 7H SUB j,j,1 \hfil $m+1$ &\ul{\sl D7.~Loop on $j$.} SUB Uj,Uj,8 \hfil $m+1$ & PBNN j,3B \hfil $m+1$ & BZ d,8F \hfil 1 & SET t+1,U \hfil 1 &\ul{\sl D8.~Unnormalize.} SET t+2,n \hfil 1 & SET t+3,d \hfil 1 & PUSHJ t,ShiftRight \ &See exercise 26. 8H IS @ <<<--- PUT rJ,return POP 0,0