Conference noted::hackers_v1

			; FOR THOSE WITHOUT Z80 BOOKS, BEATS ME
			; ROUTINE
			; A HOLDS COMPARER
			; HL HOLDS ADDRESS OF COMPARAND
			; B HOLDS NUMBER OF LOOPS, 1 < B < 8
LOOP:	CP	(HL)	; A-(HL) COMPARE A AND MEMORY BYTE POINTED BY HL
	RETZ		; RETURN IF ZERO FLAG IS SET (A = (HL))
	RL	L	; <= CARRY <= L7L6L5L4L3L2L1L0 <=, HL POINTS TO NEW LOC
	DJNZ	LOOP	; B<=B-1; IF B<>0 GOTO LOOP; IF B=0 CONTINUE
	LD	L,0	; L <= 0
	RET		; UNCONDITIONALLY RETURN TO CALLING ROUTINE 
			; TOM

	Quite obviously the Towers of Hanoi.
#6	<_Jym_>\
P.S.:  You can make a phase-of-moon program out of it by changing one (1)
       instruction.

Jym, I don't know if you're joking or not. If not, how about explaining how
it would work?

Here's what I've learned:

Compare (CP) will set the carry flag if it needs to borrow when it subtracts
the contents of the memory location from the A register. This seems important
since the rotate goes through the carry (the non-carry circular rotate would
have been chosen otherwise). 

Which means that the table doesn't need to be limited to 8 locations (that was
my first thought too), but probably doesn't exceed 256, because then you'd have
to change the H register. 256 is the maximum number of times through the loop,
since the DJNZ instruction decrements before checking for 0. 

The answer is apparently returned in the L register. L is loaded with 0 if no
match is found for A, but left alone when a match is found. 

Well, that covers most of what I was able to figure out. Can anyone take it
from here?

								Steve

I've seen this one before, so it would be cheating for me to "solve" it,
but for PDP-10 hackers, here's the equivalent code:

loop:	sub	ac,value	; ac := ac - value
	tlnn	ac,-1		; skip if ac left half /= 0
	  popj	p,		; return
	jra	ac,loop		; load ac from address in ac left half, jump

The required data structure is even more arcane than the Z80 equivalent.

Here are the results of posting this to "net.puzzle" on Usenet:
-------------------------------------------------------------------------------
From:	RHEA::DECWRL::"allegra!watmath!watdaisy!ndiamond" 
Regarding the Z80 code puzzle you posted:  is it a binary search?
(Please be kind enough to answer, and I won't post it.  Thank you.)
   Norman Diamond
UUCP:  {decvax|utzoo|ihnp4|allegra}!watmath!watdaisy!ndiamond
CSNET: ndiamond%[email protected]
ARPA:  ndiamond%watdaisy%[email protected]
-------------------------------------------------------------------------------
From:	RHEA::DECWRL::"[email protected]" 
It isn't that hard to figgure out. The code is checking up to 8 memory
locations in the same page of memory for a particular byte. Code very
similar to this is used by my model 1 to scan the keyboard (which works
by shorting address lines to data lines, and software decoding), with
the compare being for any non-zero location => key pressed.
				Michael Gersten
-------------------------------------------------------------------------------
From:	RHEA::DECWRL::"ihnp4!alberta!zaphod!bobd"
This is simply marvelous!  As far as I can tell from my Z80 instruction
manual, what we have is a basic heap search.  Here are my assumptions
about the registers and data structures:

	a) HL points to a table on a 256 byte boundary.
	b) B has log(2) N of the table size (rounded up).
	c) The table is maximum 255 bytes long
	d) The first entry is empty (irrelevant)
	e) HL is initialized to baseOfTable + 1 (L=1, H=??)
	f) The table entries are one byte values ordered in heap
	   formation.  I.e., the first item is the midpoint value of the
	   table.  The entries at 2 and 3 are the midpoints of the upper
	   and lower ranges.

The carry bit from the CP instruction is used to decide whether to use
the upper or lower half of the table.  To do a Knuth style analysis of
the performance, let N be the number of entries in the table, let k be
the ceiling of log2 N,

; A is an 8 bit register (the comparand)
; B is an 8 bit register ( = k )
; HL is a 16 bit register made up of H (the high byte) and L (the low byte)
;  HL = ??01
LOOP:
	CP	(HL)	; 7 cycles
	RET	Z	; 5 cycles or 11 cycles if taken
	RL	L	; 8 cycles
	DJNZ	LOOP	; 8 cycles or 13 cycles if taken
	LD	L,0	; 7 cycles
	RET		; 10 cycles

For the value in A not in the table, the loop time is 28*k + 5*(k-1) +
17 cycles.  Since k is 8 or less, the search will fail in a maximum of 276
cycles.

I do not agree that this is from a narrowly defined constraints;
obviously the constraints must be well defined.  I still the algorithm
is a marvelous implementation of a good data structure algorithm.

Please let me know if there are problems with my analysis, or if there
are other points that people brought up.
-------------------------------------------------------------------------------

DDJ finally printed the answer to the Wot Duzzit Dew problem they printed
back in January. Here is David Tilton's (the puzzle's originator) description:

BTS:	cp	(hl)
	ret	z

	rl	L
	djnz	BTS

	ld	L,0
	ret

"[The routine] actually outperforms the CPIR instruction of the Z80 in 
searching a list of bytes for a match by using a binary rather than a linear
search, but the restrictions on the sequence of the list and its placement
in memory make it less than attractive. 

"On entry, A contains the byte to search for, B contains the number of levels
in the tree, and HL points to the root of the binary tree. One of the 
unfortunate restrictions is that the value of L for the root must be 01H.
Since the value of H remains constant, it is the value of L on return that
indicates the result.

"It is helpful to think of the list as a byte array indexed by L. We start 
with a comparison. If there is a match, the second instruction returns with
L indicating where the match occurred.

"If there was no match, the value in the tree was either too large or too 
small. The carry flag will be set if it was too large. The next instruction
multiplies the contents of L by two and, if the carry flag was set, adds one.
The DJNZ instruction checks for another level in the tree and, if there is
one, loops to check the already-selected node in it. If there is not another
level, L is set to zero to indicate that the byte sought was not in the tree.

"There are many disadvantages to this arrangement. It is inflexible. For
one thing, a full tree must be maintained; that is, the size of the tree 
must always be some power of two less one. It is significantly faster than
CPIR only for the larger trees. Furthermore, if you can spare a full page
of 256 bytes [to hold the tree] then there is an even faster way of doing
the same thing:

BTL:	ld	L,A
	ld	L,(HL)
	ret

This is, of course, simply a byte lookup table. I thought I was being really
clever with my BTS routine, but it turns out to be virtually useless."

Oh, now, cheer up. You got deep into binary trees, right? It's very profound
that the successive carry-bits shifted into L are a record of the path through
a tree to the desired node, where [a] one means "go left" and zero means
"go right." The binary number that defines the path to a node is a unique 
label for that node; it's basically a "Dewey Decimal Number" for the node.

There's a discussion of this in Knuth's Volume 1, Section 2.3 (especially see
the answer to Exercise 15, p. 315). There also is a connection to data 
compression: if the compared values were wider than a byte, their binary node
labels would be a compressed representation of them.