From: lasner@watsun.cc.columbia.edu (Charles Lasner)
Newsgroups: alt.folklore.computers
Subject: Re: octal to decimal converter?
Date: 19 Dec 92 15:43:46 GMT
Reply-To: lasner@watsun.cc.columbia.edu (Charles Lasner)
Organization: Columbia University

In article <7766353@zl2tnm.gen.nz> don@zl2tnm.gen.nz (Don Stokes) writes:
>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.

Only valid if both registers are already setup.  That takes two other
MOV instructions to get them setup, and each of those MOV instructions are
16 bits longer than the MOV instruction you show, thus the overhead for
using your 16 bit instruction comes to a total of about 80 bits.  The PDP-8
code was 24 bits total, and 4 machine cycles.  You'd be better off using the
48 bit form of the instruction where each pointer is 16 bits.

[machine-machine challenge stated here]

>
>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
>

    OK, on the PDP-8, we'll assume there's an ASCII output routine.
I'll give it here first, but it's not part of the code:

OUTPUT,	.-.			/OUTPUT SUBROUTINE HEADER
	JMS	COUT		/OUTPUT THE PASSED CHARACTER
	TAD	(-"M!200)	/COMPARE TO <CR>
	SZA CLA			/SKIP IF IT MATCHES
	JMP I	OUT		/RETURN IF NOT A MATCH
	TAD	("J&37)		/GET A <LF>
	JMS	COUT		/OUTPUT IT
	CLA			/CLEAN UP
	JMP I	OUT		/RETURN TO MAIN CALLER

COUT,	.-.			/LOW-LEVEL OUTPUT ROUTINE
	TSF			/FLAG UP?
	JMP	.-1		/NO, WAIT FOR IT
	TLS			/YES, OUTPUT NOW
	JMP I	COUT		/RETURN

    There's also an input routine for those who need an inputted
7-bit ASCII character:

INPUT,	.-.			/INPUT SUBROUTINE HEADER
    	KSF			/FLAG UP?
    	JMP	.-1		/NO, WAIT FOR IT
    	KRB			/YES, READ IT IN
    	DCA	INBUFFER	/SAVE IT FOR LATER
    	TAD	INBUFFER	/GET IT BACK
    	JMP I	INPUT		/RETURN TO CALLER

    Since you want minimal instructions, I'll opt to use unpacked
data.  I could alternatively define a system call that used
packed-format data and use BSW to take the code out two at a time in
the output routine, but that would unfairly bias the -8 to have
stored the message in less space, so I'll stick to right-justified
full ASCII.

	*200			/THE USUAL STARTING PLACE
	
START,	DCA	17		/CLEAR AC, SO AUTO-INDEX POINTS TO THE DATA NOW
LOOP,	TAD I	17		/GET A CHARACTER
	SNA			/SKIP IF END OF MESSAGE
	JMP I	(7600)		/EXIT TO O/S IF DONE
	JMS	OUT		/OUTPUT THE CHARACTER
	JMP	LOOP		/KEEP GOING

	*1			/WHERE THE MESSAGE GOES

	"H;	"E+40;	"L+40	/"HELLO WORLD!" BLURB
    	"L+40;	"O+40;	" 
	"W;	"O+40;	"R+40
    	"L+40;	"D+40;	"!
    	"M&37;	0		/0000 TERMINATES THE MESSAGE

    	Instructions:	 6
    	Code:		 6 12-bit words
    	Data:		15 12-bit words
    	Total:		21 12-bit words

    By assuming an output routine that uses packed upper-lower
case-code text (which I often use) then the data words could be
reduced to 8 words for the blurb and the one literal to exit to the
O/S (same in both examples - 7600) for a grand total of 15 12-bit
words or 180 bits.  Your VAX example occupies about 250 bits.  If you
insist that the output routine be the stated ASCII one I gave, then I
would have to use a BSW instruction and two auto-index registers and
an extra initialize of the second register which would up the
instruction count by 3, still smaller than the VAX version.
Moreover, I could then use a non-auto-index register and use an ISZ
instruction to bump that pointer.  Even if you argue that auto-index
registers are part of the code or I use that pointer location, it's
still shorter than the VAX version.

>
>(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.)

OK, here's the PDP-8 version:

	*200			/THE USUAL PLACE

START,	DCA	ACCUM		/CLEAR ACCUMULATION
INLOOP,	JMS	INPUT		/GET A CHARACTER
	TAD	(-"M!200)	/COMPARE TO <CR>
	SNA CLA			/SKIP IF NOT <CR>
	JMP	OUTDECIMAL	/GO USE ALL PREVIOUS AS WE'RE DONE
	TAD	ACCUM		/GET ACCUMULATION
	CLL RTL;RAL		/MOVE UP THREE
	TAD	INBUFF		/ADD ON LATEST
	TAD	(-"0!200)	/REMOVE "ZONE" BITS
	DCA	ACCUM		/STORE BACK
	JMP	INLOOP		/KEEP GOING

OUTDECI,TAD	(POWERS-1)	/SETUP THE
    	DCA	17		/POWERS-OF-TEN POINTER
OUTLUP,	TAD I	17		/GET A POWER
	SNA			/END OF LIST?
	JMP	OUTCR		/YES, GO DO <CR> THERE
	DCA	DIVARG		/NO, STORE IN-LINE
	TAD	ACCUM		/GET VALUE
	MQL DVI;DIVARG,	.-.	/WILL BE PROPER POWER OF TEN
	DCA	ACCUM		/STORE REMAINDER FOR NEXT TIME
	MQA			/GET QUOTIENT WHICH IS THE LATEST DIGIT
	TAD	("0&177)	/ADD ON ASCII "ZONE" BITS
	JMS	OUTPUT		/OUTPUT THE DIGIT
	JMP	OUTLUP		/GO DO IT AGAIN

OUTCR,	TAD	("M&37)		/GET A <CR>
    	JMS	OUT		/OUTPUT IT
    	JMP I	(7600)		/RETURN TO O/S

/   	POWERS OF TEN TABLE.

POWERS,	1750			/JSB RIP
    	144
    	12
    	1
    	0			/THIS ENDS THE LIST

    	Instructions:	28
    	Code:		29 12-bit words
    	Data:		11 12-bit words
    	Total:		40 12-bit words

Your VAX version occupies about 570 bits while the PDP-8 version
occupies a total of 480 bits.

cjl