File: take_risc.w

package info (click to toggle)
sgb 1:20030623-3
  • links: PTS
  • area: non-free
  • in suites: sarge
  • size: 1,868 kB
  • ctags: 28
  • sloc: makefile: 197; sh: 15
file content (173 lines) | stat: -rw-r--r-- 6,808 bytes parent folder | download | duplicates (6)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
% This file is part of the Stanford GraphBase (c) Stanford University 1993
@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!
@i gb_types.w

\def\title{TAKE\_\,RISC}

\prerequisite{GB\_\,GATES}
@* Introduction. This demonstration program uses graphs
constructed by the |risc| procedure in the {\sc GB\_\,GATES} module to produce
an interactive program called \.{take\_risc}, which multiplies and divides
small numbers the slow way---by simulating the behavior of
a logical circuit, one gate at a time.

The program assumes that \UNIX/ conventions are being used. Some code in
sections listed under `\UNIX/ dependencies' in the index might need to change
if this program is ported to other operating systems.

\def\<#1>{$\langle${\rm#1}$\rangle$}
To run the program under \UNIX/, say `\.{take\_risc} \<trace>', where \<trace>
is nonempty if and only if you want the machine computations to
be printed out.

The program will prompt you for two numbers, and it will use the simulated
RISC machine to compute their product and quotient. Then it will ask
for two more numbers, and so on.

@ Here is the general layout of this program, as seen by the \CEE/ compiler:
@^UNIX dependencies@>

@p
#include "gb_graph.h" /* the standard GraphBase data structures */
#include "gb_gates.h" /* routines for gate graphs */
@h@#
@<Global variables@>@;
main(argc,argv)
  int argc; /* the number of command-line arguments */
  char *argv[]; /* an array of strings containing those arguments */
{
  trace=(argc>1? 8: 0); /* we'll show registers 0--7 if tracing */
  if ((g=risc(8L))==NULL) {
    printf("Sorry, I couldn't generate the graph (trouble code %ld)!\n",
      panic_code);
    return(-1);
  }
  printf("Welcome to the world of microRISC.\n");
  while(1) {
    @<Prompt for two numbers; |break| if unsuccessful@>;
    @<Use the RISC machine to compute the product, |p|@>;
    printf("The product of %ld and %ld is %ld%s.\n",m,n,p,
        o?" (overflow occurred)":"");
    @<Use the RISC machine to compute the quotient and remainder,
        |q| and~|r|@>;
    printf("The quotient is %ld, and the remainder is %ld.\n",q,r);
  }
  return 0; /* normal exit */
}

@ @<Glob...@>=
Graph *g; /* graph that defines a simple RISC machine */
long o,p,q,r; /* overflow, product, quotient, remainder */
long trace; /* number of registers to trace */
long m,n; /* numbers to be multiplied and divided */
char buffer[100]; /* input buffer */

@ @d prompt(s)
    {@+printf(s);@+fflush(stdout); /* make sure the user sees the prompt */
      if (fgets(buffer,99,stdin)==NULL) break;@+}

@<Prompt...@>=
prompt("\nGimme a number: ");
step0:if (sscanf(buffer,"%ld",&m)!=1) break;
step1:if (m<=0) {
  prompt("Excuse me, I meant a positive number: ");
  if (sscanf(buffer,"%ld",&m)!=1) break;
  if (m<=0) break;
}
while (m>0x7fff) {
  prompt("That number's too big; please try again: ");
  if (sscanf(buffer,"%ld",&m)!=1) goto step0; /* |step0| will |break| out */
  if (m<=0) goto step1;
}
@<Now do the same thing for |n| instead of |m|@>;

@ @<Now do the same thing for |n| instead of |m|@>=
prompt("OK, now gimme another: ");
if (sscanf(buffer,"%ld",&n)!=1) break;
step2:if (n<=0) {
  prompt("Excuse me, I meant a positive number: ");
  if (sscanf(buffer,"%ld",&n)!=1) break;
  if (n<=0) break;
}
while (n>0x7fff) {
  prompt("That number's too big; please try again: ");
  if (sscanf(buffer,"%ld",&n)!=1) goto step0; /* |step0| will |break| out */
  if (n<=0) goto step2;
}

@* A RISC program. Here is the little program we will run on the
little computer. It consists mainly of a subroutine called |tri|,
which computes the value of the ternary operation $x\lfloor
y/z\rfloor$, assuming that $y\ge0$ and $z>0$; the inputs $x,y,z$
appear in registers $1,2,3$, respectively, and the exit address is
assumed to be in register~7.  As special cases we can compute the
product $xy$ (letting $z=1$) or the quotient $\lfloor y/z\rfloor$
(letting $x=1$). When the subroutine returns, it leaves the result in
register~4; it also leaves the value $(y\bmod z)-z$ in register~2.
Overflow will be set if and only if the true result was not between
$-2^{15}$ and $2^{15}-1$, inclusive.

It would not be difficult to modify the code to make it work with unsigned
16-bit numbers, or to make it deliver results with 32 or 48 or perhaps
even 64 bits of precision.

@d div 7 /* location `|div|' in the program below */
@d mult 10 /* location `|mult|' in the program below */
@d memry_size 34 /* the number of instructions in the program below */

@<Glob...@>=
unsigned long memry[memry_size]={
           /* a ``read-only memory'' used by |run_risc| */
  0x2ff0, /* |start:| $\\{r2}=m$ (contents of next word) */
  0x1111, /* (we will put the value of |m| here, in |memry[1]|) */
  0x1a30, /* \quad$\\{r1}=n$ (contents of next word) */
  0x3333, /* (we will put the value of |n| here, in |memry[3]|) */
  0x7f70, /* \quad\&{jumpto} (contents of next word),
                        $\\{r7}={}$return address */
  0x5555, /* (we will put either |mult| or |div| here, in |memry[5]|) */
  0x0f8f, /* halt without changing any status bits */
  0x3a21, /* |div:| $\\{r3}=\\{r1}$ */
  0x1a01, /* \quad$\\{r1}=1$ */
  0x0a12, /* \quad|goto tri| (literally, |@t\\{r0}@>+=2|) */
  0x3a01, /* |mult:| $\\{r3}=1$ */
  0x4000, /* |tri:| $\\{r4}=0$ */
  0x5000, /* \quad$\\{r5}=0$ */
  0x6000, /* \quad$\\{r6}=0$ */
  0x2a63, /* \quad|@t\\{r2}@>-=@t\\{r3}@>| */
  0x0f95, /* \quad|goto l2| */
  0x3063, /* |l1:| |@t\\{r3}@><<=1| */
  0x1061, /* \quad|@t\\{r1}@><<=1| */
  0x6ac1, /* \quad|if| (overflow) $\\{r6}=1$ */
  0x5fd1, /* \quad|@t\\{r5}@>++| */
  0x2a63, /* |l2:| |@t\\{r2}@>-=@t\\{r3}@>| */
  0x039b, /* \quad|if| ($\ge0$) |goto l1| */
  0x0843, /* \quad|goto l4| */
  0x3463, /* |l3:| |@t\\{r3}@>>>=1| */
  0x1561, /* \quad|@t\\{r1}@>>>=1| */
  0x2863, /* |l4:| |@t\\{r2}@>+=@t\\{r3}@>| */
  0x0c94, /* \quad|if| ($<0$) |goto l5| */
  0x4861, /* \quad|@t\\{r4}@>+=@t\\{r1}@>| */
  0x6ac1, /* \quad|if| (overflow) $\\{r6}=1$ */
  0x2a63, /* \quad|@t\\{r2}@>-=@t\\{r3}@>| */
  0x5a41, /* |l5:| |@t\\{r5}@>--| */
  0x0398, /* \quad|if| ($\ge0$) |goto l3| */
  0x6666, /* \quad|if| (\\{r6}) force overflow (literally |@t\\{r6}@>>>=4|) */
  0x0fa7}; /* \quad|return|
                 (literally, $\\{r0}=\\{r7}$, preserving overflow) */

@ @<Use the RISC machine to compute the product, |p|@>=
memry[1]=m;
memry[3]=n;
memry[5]=mult;
run_risc(g,memry,memry_size,trace);
p=(long)risc_state[4];
o=(long)risc_state[16]&1; /* the overflow bit */

@ @<Use the RISC machine to compute the quotient and remainder, |q| and~|r|@>=
memry[5]=div;
run_risc(g,memry,memry_size,trace);
q=(long)risc_state[4];
r=((long)(risc_state[2]+n))&0x7fff;

@* Index. Finally, here's a list that shows where the identifiers of this
program are defined and used.