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

lasner@watsun.cc.columbia.edu (Charles Lasner) writes:
> >	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.

Yes, but it's just one or two more operands to move from memory to memory
if you don't have the registers set up.  It still saves an instruction
decode or two.

> [machine-machine challenge stated here]

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

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

My input and output routines were just jackets around a couple of VMS
$QIOWs (the "operating system" just assigned a channel for the QIOs to
use and JSBed to the routine).  I left them out as uninteresting. 

pdp11 input/output routine is pretty simple.  From memory:

	rcsr	= 177560		; Receiver CSR
	rbuf	= 177562		; Receiver buffer
	xcsr	= 177564		; Transmitter CSR
	xbuf	= 177566		; Transmitter buffer
	lf	= 000012		; Line feed
	cr	= 000015		; Carriage return

	input:	tstb rcsr		; Wait for RECV DONE (bit 7 in RCSR)
		bpl input
		movb rbuf, R0		; Get character
		jsr R7, output		; Echo it
		rts R7

	output:	tstb xcsr		; Wait for XMIT RDY (bit 7 in XCSR)
		bpl output
		movb R0, xbuf		; Write to console
		cmpb R0, #cr		; CR?
		bne 2$			; No, done
	  1$:	tstb xcsr		; Yes, repeat performance to send
		bpl 1$			;      a LF as well.
		movb #lf, xbuf
	  2$:	rts R7

The VAX equivalent would look much the same but using MTPR & MFPR to
write to the console CSRs & buffers -- the console port(s) registyers
are mapped onto processor register rather than into I/O space.
		

>     Since you want minimal instructions, I'll opt to use unpacked
> data.  I could alternatively define a system call that used

I'm really looking for minimal everything....

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

I "insisted" that a standard calling convention be used so that it would
more accurately emulate real code.  In any case, I could have used BSBs
to get to my "operating system", which would have cut the code by 32 bits
per syscall.  (BSB is just a byte opcode plus byte offset, JSB is a byte
opcode, byte operand specifier, and in this case a 32 bit address;
I felt that using small PC-relative offsets in a 32 bit address space
was cheating.)  That would bring things down to 216 bits (inc data); your
routine is 21*12=396 bits.  Code would be 120 bits if I pulled this
trick; 

Care to post your compressed data code?


I put in Hello World for purely traditional reasons.  8-)
The real test (and the topic of this thread) is....

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

Old joke, Charles.  8-)

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

OK, so I wrote crap (actually, I wrote code that would work on a pdp11
with very little modification -- well, that's my excuse anyway 8-).  Here's
a better try, using a VAX as a VAX instead of a big pdp11:

	routin:	clro R0			; Clears R0-R3
					; R0 clear nullifes next two insts
					; R3 is high order longword of 64bit R2
					;    in EDIV, so needs to be clear
	  1$:	mull2 #8, R2		; Equiv to ASHL, but a byte shorter 8-)
		bisl2 R0, R2		; Insert digit
		jsb input		; Get character
		subl2 #48, R0		; Convert character to octal digit
		bgeq 1$			; CR < '0'

		movl #1000000000, R1	; Maximum magnitude of digit
	  2$:	ediv R1, R2, R0, R2	; Divide R2/R1, quotient (digit) in R0,
					;               remainder back into R2
		addl2 #48, R0		; Convert digit to character
		jsb output		; Output to TTY
		divl2 #10, R1		; Next digit
		bneq 2$

		movl #13, R0		; Final CR
		jsb output		; Could save RSB by using JMP here
		rsb			; ... but was too honest  8-)

	Code: 38 bytes, 9.5 32 bit words or 448 bits.  No data.
	                                    ^^^
Sorry, Charles.  8-)

Also, your algorithm using a lookup table doesn't scale nicely on long 
word machines -- imagine a hypothetical 32 bit PDP-8.... 8-)  'course
EDIV on the VAX helps a LOT here.

And again, I could have used BSB to get to my syscalls and saved another
96 bits....


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