From: lasner@watsun.cc.columbia.edu (Charles Lasner)
Newsgroups: alt.folklore.computers
Subject: Re: Sync Three Times...
Date: 23 Nov 92 19:45:32 GMT
Reply-To: lasner@watsun.cc.columbia.edu (Charles Lasner)
Organization: Columbia University

In article <STEVEV.92Nov22235456@miser.uoregon.edu> stevev@miser.uoregon.edu (Steve VanDevender) writes:
>
>You can get by with just a carry flag in a processor using
>two's-complement arithmetic.  You can test if a number is
>non-zero by adding a word of all ones -- if true, the carry flag
>will be set.  cjl can undoubtedly describe many other tricks,
>including his favorite method of testing for a value in a given
>range using only one conditional branch, which uses only a test
>of the carry flag (of course, this makes it easy to do on a
>PDP-8).

On the PDP-8, just test if a numer is non-zero by testing for AC not=0
(SNA).  Straightforward.  But, yes, if that didn't exist, you could set
the carry flag (called the Link on the PDP-8) to a known state, and when
you add an all-ones word to the AC, the carry would flip unless it was
all zeroes to begin with.

As to the other "trick", yes, this is a method that is general-purpose to
any machine, and doesn't depend on any excess precision trick, etc.  For
any N-bit register, you can test for whether any possible value (between
0 and 2^(N-1) unsigned) is in a range, as long as the range of legal
values is itself 2^(N-1)-1 or smaller.  Only the main arithmetic register
is involved, assuming there is add from memory avaiilable.  Here's a PDP-8
version to segregate out 12-bit values that could be in the range 0000 to
4095 decimal (it's a 12-bit machine) that happen to fall into the range
of 0060 through 0067 octal, or are the ASCII digits "0" thorugh "7".

	*200		/Set a usual origin for a stand-alone program

START,	CLA		/Clean up the accumulator, although start key does it
	TAD	CHAR	/Get the test contents that could be anything
	TAD	(-70)	/Add on -(upper limit of legal values+1)
	CLL		/Clear the carry flag now; the -8 won't auto-do it
	TAD	(10)	/Add on (count of values in desired range)
	SNL		/Skip if carry set
	JMP	NOTDIG	/Go elsewhere if it flunks the test

/	Ac now contains 0000 through 0007, corresponding to "0" through "7"

Note that we even got a nice "frill" in that the residue of the position
within the table is left in the accumulator.

In a "real" program, the initial CLA to clear the accumulator wouldn't exist
because the PDP-8 store instruction DCA stores into memory and clears the AC
afterwards.  Also, all skip conditions can be optionally micro-coded to
also clear the AC as well.  For example, if the residue wasn't needed,
then the SNL could be replaced with SNL CLA which skips if the Link bit is
set, then clears the AC.

Moreover, if the test value is stored with the -70 offset applied, as in
some sort of numerical input routine, then CHAR would already contain
the test value -70.  Note that TAD is two's complement add, and that PDP-8
convention really is that the previous AC contents is usually 0000, thus
the TAD CHAR would effectively be a load operation.

The only overhead is the need for the CLL instruction because the -8 doesn't
automatically reset the carry flag, and we need it in some known state
at the point of the test.  Also, note that if the TAD CHAR and the TAD (-70)
are carried out separately, then this CLL is needed after the adding of the
two together, because for some values, this might flip the carry at that
point, so a routine entry state for the carry isn't good enough.

So, the smallest practical code would be

	TAD	CHARM70		/Get the pre-subtracted test value
	CLL			/Clear the Link now
	TAD	(10)		/Add on the test range
	SNL			/Skip if carry flipped
	JMP	NOTDIG		/Where to go on bad cases

/	Fall through when one of the desired values is found.

Note that the entire routine takes 6 machine cycles assuming the test succeeds
and 7 if it fails. (TAD is two cycle - one to fetch and one to address the
memory location.)

We can even trim down one more cycle - On PDP-8/e, the MQ register is
always implemented, and it's recommended to be used as a fast temporary.
Thus, the test value-70 would likely be stored in the MQ register as a global
parameter if there was much testing involved.  (When you write code for the
entire product line, you have to avoid these extensions, because the MQ
isn't available at all on the 8/l, and is only optional on 8, LINC-8, and 8/i
and -12.)  Thus, the first TAD CHARM70 can be replaced with the one-cycle
MQA which transfers the MQ -> AC.  Moreover, it can be microcoded in one
cycle as CLA MQA to ensure the AC load is certain.

So, the fastest version is 5 instructions and 5 machine cycles if it
succeeds, and 6 if it fails.

cjl
Newsgroups: alt.folklore.computers