From: lasner@watsun.cc.columbia.edu (Charles Lasner)
Subject: Re: octal to decimal converter?
Reply-To: lasner@watsun.cc.columbia.edu (Charles Lasner)
Organization: Columbia University
Date: Mon, 21 Dec 1992 05:58:14 GMT

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

Yes, but it still adds 32 more bits to the instruction to have to fetch all
of those extra bytes in the addresses.  The -8 version is 2 instructions and
24 bits total, 4 machine cycles in all.

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

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

OK, as you said, *real* code.

The usual output routine that is used on the -8 supports upper-lower "text"
mode code that is packed two six-bit bytes per 12-bit word.  The usual 
convention is that % means CR/LF and ^ means case shift with the starting
case of lower.  Usually I prefer locking case, but others might use non-locking
style.  (Of course this means that the specific chars "%" and "^" are not
available to blurb-printing routines, but in theory could be any other 2
similar characters from that "quadrant" of ASCII.

	*200

START,	DCA	MPTR		/SET MESSAGE POINTER
NXTPAIR,ISZ	MPTR		/BUMP TO NEXT PAIR
	TAD I	MPTR		/GET A PAIR
	SNA			/END OF LIST?
	JMP I	(7600)		/YES, GO AWAY
	BSW			/WANT UPPER ONE FIRST
	JMS	OUT6		/OUTPUT IT
	TAD I	MPTR		/GET THE PAIR AGAIN
	JMS	OUT6		/OUTPUT LOWER ONE
	JMP	NXTPAIR		/GO DO ANOTHER ONE

	MPTR=	0		/ANY PAGE ZERO TEMPORARY IS FINE

	*1			/WHERE THE MESSAGE GOES

	TEXT	"^H^ELLO ^W^ORLD!%^";0

Total instructions: 10
Total data: 11

Same total storage, but more useful for longer blurbs.  Also, it would be
12-bits shorter if I used non-locking case shift, but as I indicated earlier,
I really do prefer locking shifts.  Also the 7600 constant is easily bummed
out (see below).  So, the code is 120 bits here also.  Besides, I don't think
much is being served counting the characters in the blurbs, although the VAX
and most other machines have little useful facility to take advantage of
character sets other than the usual because of the 8-bittedness of the
machines.  Only the -8 and -10 really optimize for six-bit data. (The -10
can do any length.)  None-the-less, as the blurb gets longer, the overall
PDP-8 size will tend to get even smaller since blurbs are stored in six-bit
compressed form.  (Of course there are perverse cases where the shift overhead
exceeds the advantages.  This is why we use both locking and non-locking shift
routines, etc.)


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

Irrelevant; the technique applies to the problem as defined.  I could have
also used the longer divide by 10 method to crank out the digits in reverse
order, which I object to in your examples, using tricks to get strings 
outputted by putting them together backwards as in the Hello World program.
At least my character strings are in normal order.  In any case, I can
bum a few more words out of this code, which while not the first-order
thing to do, none-the-less does happen:

        ACCUM=  0011            /ACCUMULATION STORED IN AUTO-INDEX REGISTER
        OUTPUT= 0015            /ADDRESS OF OUTPUT ROUTINE
        INPUT=  0060            /ADDRESS OF INPUT ROUTINE
        XR=     0010            /AUTO-INDEX REGISTER USED AS SUCH

	*200			/HERE WE GO AGAIN

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
        R3L                     /MOVE UP THREE
        TAD     INBUFF          /ADD ON LATEST
        TAD     L7720/(-"0!200) /REMOVE "ZONE" BITS
        DCA     ACCUM           /STORE BACK
        JMP     INLOOP          /KEEP GOING

OUTDECI,DCA     XR              /TABLE IS AT 0001
OUTLUP, TAD I   XR              /GET A POWER
        SPA                     /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     INLOOP/("0&177) /ADD ON ASCII "ZONE" BITS
        JMS     OUTPUT          /OUTPUT THE DIGIT
        JMP     OUTLUP          /GO DO IT AGAIN

        *1                      /WHERE THE TABLE GOES

/       POWERS OF TEN TABLE.

        1750                    /JSB RIP
        144
        12
        1
OUTCR,  JMS     OUTPUT          /OUTPUT A <CR>;ALSO TABLE DELIMITER
        JMP I   L7600/(7600)    /RETURN TO O/S

     	Instructions:	25
     	Code:		26 12-bit words
     	Data:		 5 12-bit words
     	Total:		31 12-bit words

        This version is 372 bits total.  A minor model cheat is that R3L can't
be used on some earlier machines.  The locations marked with Lxxxx are bummed
away locations:

L7600,  CLA!400         /CLEAR THE ACCUMULATOR AND ALSO A GOOD CONSTANT

L7720,  SMA SNL CLA     /CLEAR THE ACCUMULATOR AND IT MIGHT SKIP
L60,    AND     60      /HARMLESS .AND. INSTRUCTION; IT MIGHT BE SKIPPED OVER

These would be used to replace ordinary CLA instructions that are always
needed in numerous places.  (You did ask for *real* examples, well this is
what *really* is done.)

Who's sorry now?  (Connie Francis)

cjl