Assembly Language Programming

January 30, 2011

PDP-8 Assembly Language – Part 1

Filed under: Assembly Language, Compilers, JavaScript — Tags: , , , — programmer209 @ 9:47 am

A PDP-8 Assembly Language Simulator – Part 1

This post (in 2 parts) discusses a PDP-8 Assembly Language Simulator that I have written in HTML/Javascript.

The source code for the simulator can be found in Part 2 of this post. In Part 1 (this post), I discuss the PDP-8 assembly language and provide some example PDP-8 assembly language programs.

References

Some good references for the PDP-8 assembly language are:

The MACRO-8 Programming Manual (DEC-08-CMAA-D) and the PAL III Symbolic Assembler Programming Manual (DEC-08-ASAC-D).

The MACRO-8 manual in particular contains a good concise explanation of the PDP-8 assembly language.

The PDP-8

The PDP-8 (Programmed Data Processor) was a 12-bit mini-computer manufactured by DEC (Digital Equipment Corporation) in the mid-to-late 1960’s. 4096 words of core memory were available in the basic model (but this was expandable), the maximum amount of memory that can be addressed using a 12-bit word.

For programming purposes, the PDP-8 had only one register (the accumulator or ACC) and a link bit (LNK). Any data that needed to be manipulated first had to be put into the ACC, while the LNK captured any overflow from operations performed on the data in the ACC.

The PDP-8 also had a Program Counter (PC) register and an Instruction Register (IR). Before executing an instruction the PDP-8 copied it’s address in memory to the PC, while the machine code for the instruction was loaded into the IR. After execution, the PC was incremented to the next instruction.

Octal

For the PDP-8 it was the convention to represent values in Octal. An octal digit represents 3 bits, therfore a 12-bit value was represented by 4 octal digits. My simulator follows this convention, so remember:

Everthing is in Octal.

In particular for the assembly language, my compiler does not support the decimal and octal directives (or pseudo-instruction). Therefore the numbers used within any source code must be in octal

Two’s Complement Numbers

The 12 bit value stored by the ACC behaves according to the rules of 2’s complement arithmetic. This means that instructions such as isz, sma, spa etc will interpret the contents of the ACC according to the rules of the 2’s complement system.

The ACC can store any value between 0 and 7777 (octal). The right-most bit is the sign bit (4000). Therefore the range 0 – 3777 represents positive values, and 4000-7777 negative values. The value 7777 equals -1 (since 7777 = 3777 – 4000 in 2’s complement arithmetic).

However, this doesn’t stop the programmer from manipulating the contents of the ACC as if it were an unsigned bit string. See my big number multiplication program below.

Any overflow from operations performed on the ACC are captured by the LNK bit. In this case the link bit is complemented, so if LNK is 0 it will become 1.

PDP-8 Instruction Set

On the PDP-8, the machine code for an instruction was restricted to 12-bits. These 12-bits had to be capable of storing both an operation code and an address in memory. For this reason the PDP-8 had a minimalist instruction set, since there had to be a balance between the number of bits used to specify an op-code and the number of bits used to specify an address.

The PDP-8 used the first 3 out of the 12 bits for the op-code, thus there were only 8 op-codes:

000 AND ACC = ACC & C(Addr)
001 TAD ACC += C(Addr)
010 ISZ C(Addr)++; if(C(Addr)==0) PC++;
011 DCA C(Addr) = ACC; ACC = 0;
100 JMS C(Addr)=PC+1; PC=Addr+1;
101 JMP PC = Addr
110 IOT Communicate with an IO device
111 OPR Micro-coded Instructions

MRI – Memory Reference Instructions

Only the first six instructions in the table above (the MRI) reference an address in memory. Within these instructions, there are 9 bits available to specify an address in memory. The problem is that 12 bits are needed to fully specify any location within the PDP-8s 4096 words of memory. Thus an MRI is restricted in how much of the core memory it can directly access.

The PDP-8 solves this problem by dividing the main memory into 32 pages of 128 words each. The first 5 bits of a 12 bit address then give the page number, with the remaining 7 bits being the offset within a page. In an MRI, the last 7 bits specify this offset. This leaves 2 bits.

The bit at 0400 (octal) is used to specify indirection. If the indirection bit is 0, then the address referenced by the MRI contains the data to be used by the MRI. If the indirection bit is 1, then the address referenced by the MRI contains not data, but another address. In this way, data from any location in memory can be passed to the MRI.

The bit at 0200 (octal) is the current page bit. If it is 0 the page number is set to 0. If it is 1 the page number is set to the current page, as given by the PC. From this bit, a full 12-bit address can be calculated from the 9 bits provided in the MRI. However, this means that an MRI can only directly reference 2 pages in memory: page 0 and the current page.

IOT – Input Output Transfer

These instructions were used to transfer data to and from external input/output devices. The specific instructions were usually defined by the I/O devices themselves.

My simulator program does not support this class of instructions.

OPR – Operate Instructions

These instructions do not reference an address in memory. Therefore the 9 bits can be used to specify certain actions (hence these instructions are micro-coded). There are 3 groups of OPR instructions. In group 1, the bit at 0400 (octal) is always 0. In group 2, the bit at 0400 is always 1 and the bit at 0001 is always 0. In group 3, the bits at both 0400 and 0001 are always 1. My simulator program does not support the group 3 OPR instructions.

The Group 1 instructions and machine codes are:

NOP 7000 No operation
CLA 7200 ACC = 0
CLL 7100 LNK = 0
CMA 7040 ACC = ~ACC
CML 7020 LNK = ~LNK
IAC 7001 ACC++
RAR 7010 RotR(ACC,LNK,1)
RAL 7004 RotL(ACC,LNK,1)
RTR 7012 RotR(ACC,LNK,2)
RTL 7006 RotL(ACC,LNK,2)
BSW 7002 ByteSwap(ACC)

The Group 2 instructions fall into 2 sub-groups – OR and AND:

OR Sub-Group
NOP 7400 No operation
CLA 7600 ACC = 0
SMA 7500 Skip if ACC < 0
SZA 7440 Skip if ACC == 0
SNL 7420 Skip if LNK != 0
HLT 7402 Halt
AND Sub-Group
CLA 7610 ACC = 0
SPA 7510 Skip if ACC >= 0
SNA 7450 Skip if ACC != 0
SZL 7430 Skip if LNK == 0
SKP 7410 Unconditional Skip

The AND skip instructions are also known as the reverse sense skips.

Within each of the groups, multiple instructions can be combined into the one 12-bit machine code. Instructions cannot be mixed between groups, or between the OR and AND sub-groups.

Some examples of how the ops can and cannot be combined:

(i) cla cll iac rar / there can only be 1 shift op in any one combo

(ii) sma sza snl / evaluated as skip = (sma OR sza OR snl)

(iii) spa sna szl / evaluated as skip = (spa AND sna AND szl)

(iv) sma sza spa szl / WRONG: cannot mix OR and AND ops

(v) skp sma / WRONG: cannot mix the unconditional skip with any other skip

Some combinations of the above ops have their own op id:

CIA 7041 CMA IAC
STL 7120 CLL CML
STA 7240 CLA CMA
GLK 7204 CLA RAL

The group 2 instructions also includes the OSR (7404) instruction which logically ORs the contents of the switch register with the ACC. The contents of the switch register were set by actually setting switches on the front panel of the PDP-8. There were 12 switches, one for each bit. My simulator does not include a switch register, and therefore does not support this instruction.

PDP-8 Assembly Language Simulator

My simulator works by first taking code written in PDP-8 assembler and compiling it to statements in machine code. Each statement is a 12-bit value which is stored at some location in memory. Such a 12-bit value can represent either a data value or an operation. The compiler uses a Location Counter (LC) to keep track of where in memory a 12-bit code should be deposited. The LC can be explicitly set at any point in the code by use of the * directive. The compiler then increments the LC for each valid line of code (i.e. a data value or operation) it encounters.

The compiler executes 2 passes through the code. Pass 1 is used to build the symbol table and check the basic syntax of each line of code (no machine code is generated). The symbol table stores all of the symbolic address tags contained in the code, as well as the address values the tags point to.

The symbol table will also store any tags defined through parameter assignment (see below). The value of any tags defined through parameter assignment are not calculated until pass 2. Therefore in the source code listing, any such tag should be defined before being referenced.

Pass 2 generates the actual machine code for each line containing data or instructions. The symbol table is used to translate tags to address or data values.

The main references I used when writing my simulator were the PAL-III and MACRO-8 pdf manuals. However, my simulator doesn’t support every compiler feature specified in these manuals. I will now outline what features my simulator does actually support.

Symbolic Address Tags (or Labels)

A symbolic address tag is used to label a location in memory. Both instructions and data can be labelled in this way. For example, the entry point to a loop can be labelled as simply “loop”:

loop, cla cll

A data variable, such as a loop counter can be labelled in the same way:

count, 0

The presence of the comma indicates that a label is being used. On the first pass, the compiler will detect all of the labels and add them to the symbol table.

These tags can then be used in the code:

isz count
jmp loop

Tags must start with a letter, but then can contain any combination of letters and numbers. Any tags longer than 6 characters will be truncated by the compiler, to 6 characters.

Comments

The / character indicates the start of a comment. On any given line, the compiler will ignore everything that appears after the /.

End of Line Characters

Each line of source code translates to a 12-bit value in memory, which can either be data or an operation. The compiler recognises the CRLF or LF characters as the end of line terminators. Also recognised is the semi-colon ‘;’. The use of the semi-colon allows multiple statements to be combined on the one line:

cla cll; rar; cma; tad A;

The compiler will see this as 4 separate lines.

Set the LC

The address of the location counter (LC) can be set by using either the * directive or the “page” pseudo-instruction.

* nnnn - sets the LC to the address nnnn.
Page N - sets the LC to offset address 0 within page N.

It is common to have the main body of the code located on page 1 (starting at 0200). Thus the directive *0200 is placed immediately before the first line of code.

$ directive

The $ directive tells the compiler to stop. Therefore it must appear on the very last line, after all the code. In my simulator this directive can also be used to specify the entry point for execution of the code. The argument to the directive can either be a numerical address or an address tag.

$ nnnn - set the entry point to the address nnnn.
$ tag - set the entry point to the address pointed to by tag, which must be defined in the symbol table.
$ - set the entry point to the default : 0200.

In my simulator, it doesn’t matter if the $ directive is missing – the compiler will just stop when the code runs out and the entry point will be set to 0000.

MRI Instructions

These instructions are coded in the form: XXX i Addr. The i indicates indirection is being used, and is optional. Addr is the address being referenced by the instruction. It must be on page 0 or the current page. Addr is an expression in any one of the following formats:

nnnn - a numerical address.
tag - an address tag defined in the symbol table.
tag+n - an address tag plus some numerical offset n.
tag-n - a tag minus a numerical offset n.
. - the dot operator returns the address of the current line (the LC).
.+n - LC plus the offset n.
.-n - LC minus the offset n.

The MRI itself can either be in lower or upper case e.g. tad or TAD.

OPR Instructions

All of the OPR instructions given above are supported. Multiple instructions can be combined, as long as they are compatible. They can be in either lower or upper case.

Expressions and Parameter Assignment

The compiler can handle expressions of the form: A=B=C+D-E. If any equal signs are present, the expression will be treated as a parameter assignment. In this case no code is generated, the compiler just adds any tags that appear to the left of an equals sign to the symbol table. The value assigned to the tag in the symbol table is that of the expression on the right of the equal signs. So for the example, A and B are added to the symbol table and given the value of C+D-E. Since this takes place at compile time, it is not possible to dynamically update the tag values by using parameter assignment.

Note that my simulator does not support the use of parameter assignment to redefine the values of the instruction mnemonics (i.e. tad, isz, cla etc).

If there are no equal signs (e.g. C+D-E) then a 12-bit value is generated and added to the machine code and the LC is incremented. The terms in an expression can either be a tag, a number or the dot operator. Otherwise, the expression can only contain the + and – operators. The unary minus is also supported: e.g. -H, -5.

Apart from the above, any of the other compiler features as described in the PAL-III or MACRO-8 manuals are not supported by my simulator.

Auto-Index Registers

The PDP-8 provides 8 locations in memory (10-17) which, when referenced indirectly by an MRI operation, behave as auto-index registers. If the machine detects that the indirect bit in the MRI op is set, it will increment the data value in the register and then perform the operation. So for example, an auto-index register can be used to iterate through an array. See the Array Copy program just below.

Example Programs

Below are a few programs that I have written and tested using my simulator:

Array Copy

This program makes use of the auto-index registers at memory locations 10 and 11 to copy an array from one location to another. Location 10 (labelled as pArr1), references the array arr1 (the original). Location 11 (pArr1), references arr2 (the copy). Since the auto-index registers increment before being used, pArr1 and pArr2 are initialised to arr1-1 and arr2-1. Thus, when the first iteration of the loop executes, pArr1 and pArr2 will be correctly set to arr1 and arr2.

/ array copy:

*0200
cla cll

/ copy arr1 to arr2

copy,tad i pArr1
dca i pArr2
isz count
jmp copy

/ done

hlt

/ data

count, 7772

/ auto-indexing

*10
pArr1, arr1-1
pArr2, arr2-1

/ the arrays

*220
arr1, 1111;2222;3333;4444;5555
*240
arr2,0;0;0;0;0
$200

Ascii String Reverse

On the PDP-8, Ascii characters (which are usually 8 bits) could be stored in memory in a special 6-bit form, allowing 2 Ascii characters to be packed into each 12-bit word of memory (see appendix 2 of the MACRO-8 manual). The program below reverses such an Ascii string. First a copy of the original array is created, but in reverse order. Then the bsw (byte swap) instruction is used to swap the 6-bit bytes within each 12-bit word of the reversed array.

/ ascii strReverse:

*0200
cla cll

/ negate len
/ and then set: count,len = -len

tad len
cia
dca count
tad count
dca len

/ copy str1 to str2 in reverse order
/ pStr2 starts from the end of str2

revcpy,tad i pStr1
dca i pStr2

/ decrement pStr2

cma
tad pStr2
dca pStr2

isz count
jmp revcpy

/ reset the count

tad len
dca count

/ set pStr2 to the start of str2
 
isz pStr2

/ swap the 6-bit words in str2

swap, tad i pStr2
bsw
dca i pStr2
isz pStr2
isz count
jmp swap

/ done

hlt

/ data

len,4
count,0
pStr2,str2+3

/ auto-index

*10
pStr1,str1-1

/ str1 and str2

*300
str1,1234;5670;1234;5670
*320
str2,0;0;0;0
$0200

Bit String Reverse

Here are 2 ways to reverse the bits in a 12-bit word of memory, a brute force method and then a much more efficient method.

In the first method, a test_bit is initialised to 1 and a set_bit is initialised to 4000 (octal). The word is tested against the test_bit, and if the result is true the set_bit is added to the result. The test_bit is then left shifted and the set_bit right shifted for the next iteration. Each bit in the word is tested in this way, so the loop in the code below executes 12 times.

/ reverse a 12-bit word 

*0200
loop, cla cll

/ Test - ACC = bitstr AND test bit:

tad bitstr
and testbt

/ skip if the ACC is zero:

sna
jmp next

/ set the bit in the result:

cla
tad setbit
tad result
dca result

next, cla cll

/ increment the test bit:

tad testbt
ral
dca testbt

/ decrement the set bit:

tad setbit
rar
dca setbit

/ if the set bit is zero, then exit:

tad setbit
sza
jmp loop

hlt

*0240
bitstr, 3333
result, 0
testbt, 1
setbit, 4000
$200

The second method doesn’t require a loop, and is therefore much more efficient. Various bit masks and shifts are used to first swap the digits. Then the bsw instruction is used to swap the 6-bit bytes within the word. Finally, more bit masks and shifts are used to swap the bits within each digit.

/ reverse a 12-bit string

*0200
cla cll

/ right shift (x3) digits 1 and 3:

tad mask1
and bitstr
rtr;rar
dca result

/ left shift (x3) digits 2 and 4:

tad mask2
and bitstr
rtl;ral
tad result

/ byte swap: 21,43 --> 43,21

bsw
dca result

/ reverse the bits within each digit:

/ the middle bit does not change:

tad mask3
and result
dca temp

/ extract the left most bits and right shift x2:

tad mask4
and result
rtr
tad temp
dca temp

/ extract the right most bits and left shift x2:

tad mask5
and result
rtl
tad temp

/ done - save the result:

dca result
hlt

*240

mask1, 7070
mask2, 707
mask3, 2222
mask4, 4444
mask5, 1111
bitstr, 3451
result, 0
temp, 0

$200

Big Number Multiplication

The program below multiplies 2 big numbers (as unsigned integers). The pseudo-code here gives the algorithm:

Num1 = array[len];

Num2 = array[len];

Product = array[2*len];

Temp = array[2*len];

test_bit=1;

Product=0;

Temp = Num1;

for(i=0;i<len;i++)
{
 for(j=0;j<12;j++)
 {
  flag = Num2[i] & test_bit;  

  if(flag) Product += Temp;

  test_bit = test_bit << 1;

  Temp = Temp << 1;
 }

 test_bit = 1;
}

In words, Num1 is multiplied by Num2 and the result saved in Product. Initially, Num1 is copied to Temp. Then a loop is used to test each bit in Num2. If the test returns true, then Temp is added to the product. At the end of each iteration, Temp is left shifted by 1 bit.

The code below includes: (i) global pointers and data on page 0, (ii) a main loop that does the bit testing and manages the counters on page 1, (iii) storage for the input and output arrays on page 2, and (iv) Add and Shift sub-routines on page 3.

/ ++++++++++++++++++++++++++++++++++++++++++++++

/ Page 0:

*20

/ keep a permanent copy of the array addresses:

addNm1, num1 
addNm2, num2
addTmp, temp
addPrd, prod 

/ array pointers:

pNum1, num1
pNum2, num2
pTemp, temp
pProd, prod

/ sub-routine pointers:

pAdd, Add
pShift, Shift

/ data

size, 20
size2, 40
count, 0
testbt, 1
nbits, 14
bcount, 0
overfl, 0

/ ++++++++++++++++++++++++++++++++++++++++++++++

/ Page 1:

*0200

cla cll

/ copy num1 to temp:

tad size
cia
dca count

copy, tad i pNum1
dca i pTemp
isz pNum1
isz pTemp

isz count
jmp copy

/ reset pNum1 and pTemp:

tad addNm1
dca pNum1

tad addTmp
dca pTemp

/ the main loop to do the multiplication:

/ reset count:

tad size
cia
dca count

/ set the bit counter:

tad nbits
cia
dca bcount

main, tad pNum2
and testbt

/ skip if ACC is non-zero:

sna
jmp, next

/ jump to the Add sub-routine:

jms i pAdd

next,

/ jump to the Shift sub-routine:

jms i pShift

/ left shift the test bit:

cla cll
tad testbt
ral
dca testbt

/ if bcount is zero, set the
/ test bit back to 1:

isz bcount
jmp incr

/ test bit will also be zero, just add 1:

isz testbt

/ reset bcount:

tad nbits
cia
dca bcount

/ loop back to main, or exit if count is zero:

incr, isz count
jmp main

/ done:

hlt

/ ++++++++++++++++++++++++++++++++++++++++++++++

/ Page 2:

*400

num1, 1234;5670;1111;2222;
      1234;5670;3333;4444;
      1234;5670;5555;6666;
      1234;5670;7777;1357;

*420

num2, 1234;5670;1111;2222;
      1234;5670;3333;4444;
      1234;5670;5555;6666;
      1234;5670;7777;1357;

*440

temp, 0;0;0;0;0;0;0;0
      0;0;0;0;0;0;0;0

*500

prod, 0;0;0;0;0;0;0;0
      0;0;0;0;0;0;0;0

/ ++++++++++++++++++++++++++++++++++++++++++++++

/ Page 3:

*600

/ left shift sub-routine:

Shift, 0

cla cll

/ make sure that pTemp points to temp:

tad addTmp
dca pTemp

/ set the counter:

tad size2
cia
dca tcount

/ zero the overflow:

dca overfl

/ add *pTemp to the ACC
/ left shift the ACC
/ add the overflow
/ and save back to *pTemp:

lshift, tad i pTemp
ral
tad overfl
dca i pTemp

/ put the oveflow bit from
/ the LNK into the ACC
/ and save it:

cla
ral
dca overfl
cll

/ next iteration, or exit:

isz pTemp
isz tcount

jmp lshift

/ done:

jmp i Shift

tcount, 0

/ ++++++++++++++++++++++++++++++++++++++++++++++

*640

/ add sub-routine:

Add, 0

cla cll

/ make sure that pTemp points to temp:

tad addTmp
dca pTemp

/ make sure that pProd points to prod:

tad addPrd
dca pProd

/ set the counter:

tad size2
cia
dca acount

/ zero the overflow:

dca overfl

/ add *pTemp and *pProd,
/ add the overflow,
/ save the result to *pProd:

doAdd, tad i pTemp
tad i pProd
tad overfl
dca i pProd

/ put the overflow bit from
/ the LNK into the ACC
/ and save it:

cla
ral
dca overfl
cll

/ next iteration, or exit:

isz pTemp
isz pProd
isz acount

jmp doAdd

/ done:

jmp i Add

acount, 0

/ ++++++++++++++++++++++++++++++++++++++++++++++

$200
Advertisements

Create a free website or blog at WordPress.com.

%d bloggers like this: