Newsgroups: alt.folklore.computers
Subject: Re: octal to decimal converter?
From: don@zl2tnm.gen.nz (Don Stokes)
Date: 19 Dec 92 09:31:55 GMT
Distribution: world
Organization: The Wolery

lasner@watsun.cc.columbia.edu (Charles Lasner) writes:
> PDP-11 has a "simple move" instruction, but look how many bytes it takes to
> state how to move something from point A to point B, while the PDP-8 uses
> two 12-bit instructions in 4 total cycles to move a 12-bit A to a 12-bit B.
> Are we going to count instructions regardless of how complicated they are
> as *one* each?

	011011	MOV (R0), (R1)

One word.  A bit more if you haven't already got the addresses in registers.

> >A challenge: state the purpose of your 48 word routine in enough detail
> >so I can have a go at implementing it on a pdp11 or VAX (possibly other
> >architectures too).  Let's get objective about this!
> It's not "my" routine, and certainly not my count of length of it; I merely
> took an off-hand count of what someone else proposed, and suggested that I
> could do it shorter than that on the -8 than on the alleged -1 version.  
> Someome else suggested that the -1 could do it in less space also.  I would
> tend to agree, but I make no claims about -1 expertise.

You made the claim that an -8 generally required shorter code, not just 
a PDP-1.  I don't claim PDP-1 expertise, and I don't have one handy to try
things out on, but I do have a VAX right here.  I'd love to see how the -8
stacks up against multiple register multiple operand machines.

> I suppose I could whip up something vaguely similar as long as we could
> define some "ground rules" so that there is a level playing field.

OK, I'll start.  Ground rules are:
     o	Internal representation of strings etc is up to the programmer,
	as long as he/she is consistent.
     o	"Words" are the natural word size of the machine, ie 32bits for
	VAX, 16 for pdp11, 12 for PDP-8, 8 for 6502, 36 for PDP-10 etc
     o	The "operating system" has two system calls -- input & output.
	input reads a single character from the console TTY and places it
	in "the accumulator".  output writes the character in the 
	accumulator onto the console TTY.  Characters are assumed to
	occupy a whole word with bits above bit 6 cleared and are 
	assumed to be ASCII.  The "accumulator" is the lowest numbered
	register on multi-register machines (R0 for pdp11/VAX, D0 on 68k).
	Routines should try not to use clever tricks or special
	instructions.  (If a special instruction would make a dramatic
	difference, demonstrate both.)  System calls use the shortest
	available *subroutine* calling mechanism (again, be consistent).
	The accumulator is always destroyed by a syscall.  <CR> is 
	assumed to do a line feed also.  Input characters echo; you
	don't need to echo yourself.
     o	Routines must return to the "OS" using the same call/return 
	mechanism as the syscalls.

(I think this pretty provides a reasonable baseline for comparing toy
problems on multiple architectures....)

(1) Hello World.  Do whatever is required to put "Hello World!<CR>"
on the console TTY.

	hello:	.byte 13
		.ascii "!dlroW olleH"	; Hello World!<CR> backwards
	routin:	movl #12, R2
	  1$:	movzbl hello(R2), R0
		jsb output
		sobgeq R2, 1$
		rsb

	Instructions:	5
	Code:		18 bytes
	Data:		13 bytes
	Total:		31 bytes, 8 32-bit words


(2) Octal to decimal converter.  Input as many octal digits as 
required until CR.  Assume numbers smaller than word size are input,
don't worry about invalid input.  Output decimal on TTY followed by CR.

	routin:	clrl R2			; Accumulator
	  1$:	jsb input		; Read characters
		cmpb R0, #13		; CR?
		beql 2$
		bicb2 #^xF0, R0		; ASCII -> octal value
		ashl #3, R2, R2		; Shift
		bisb2 R0, R2		;       and add digit
		brb 1$
	  2$:	movl #1000000000, R3	; Magnitude of digit
	  3$:	divl3 R3, R2, R0	; Get digit value
		mull3 R3, R0, R4
		subl2 R4, R2		; Extract remainder
		bisl2 #48, R0		; Convert digit to ASCII
		jsb output
		divl2 #10, R3		; Next digit
		bneq 3$
		movl #13, R0		; Final CR
		jsb output
		rsb

	Instructions:	18
	Code:		71 bytes (18 32-bit words)
	Data:		None

	(This could be shortened using decimal string instructions.)

I worked out how long mechanical translations of these into pdp11 code 
are (the only changes other than opcode for opcode are conversion of
3-operand instructions into a MOV plus equivalent 2-operand instruction,
and allowing for slightly different behavior between the VAX SOBGTR and
pdp11 SOB instructions).  The counts come out to:

(I can't be bothered firing up a pdp11 and I don't have an assembler
within easy reach so the pdp11 code was untested.  It was just a
mechanical translation, so I'm pretty sure it'd work.)

		VAX				pdp11
		Instr	bytes	words(32b)	Instr	bytes	words(16b)
Hello World:
	Code	5	18	4.2		5	16	 8
	Data		13	3.1			14	 7

Octal to Decimal:
	Code	18	71	17.3		21	62	31

So VAX & pdp11 code sizes are fairly close (if measured in bytes) -- VAX
gets blown out by long constants and subroutine call targets, but could
probably make up some lost ground by use of special instructions in real
applications.


It's worth noting that neither of these routines really take advantage of
the VAX.  I haven't used any of the "kitchen sink" instructions that the
VAX is famous for apart from SOBGTR, which has an equivalent instruction
on the pdp11, so is not that special.  I haven't put any effort into bumming
the code either.

Now, how about PDP-8 versions of these, Charles?  Feel free to pose 
different problems.

Anyone else want to show off their favourite architecture?  

--
Don Stokes, ZL2TNM (DS555)                        don@zl2tnm.gen.nz (home)
Network Manager, Computing Services Centre            don@vuw.ac.nz (work)
Victoria University of Wellington, New Zealand              +64-4-495-5052
Newsgroups: alt.folklore.computers
Subject: Re: Apple IIGS being discontinued Dec 1992