Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site decwrl.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!mhuxr!mhuxt!houxm!whuxl!whuxlm!akgua!sdcsvax!dcdwest!ittvax!decvax!decwrl!dec-rhea!dec-viking!wasser_1
From: wasser_1@viking.DEC (John A. Wasser)
Newsgroups: net.puzzle
Subject: Z80 Code Puzzle (Revisited)
Message-ID: <1175@decwrl.UUCP>
Date: Tue, 19-Mar-85 16:56:18 EST
Article-I.D.: decwrl.1175
Posted: Tue Mar 19 16:56:18 1985
Date-Received: Thu, 21-Mar-85 04:27:19 EST
Sender: daemon@decwrl.UUCP
Organization: DEC Engineering Network
Lines: 102


	Here are the answers I've gotten for the Z80 code puzzle.
	After each answer are my comments.
-------------------------------------------------------------------------------
> 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%watdaisy@waterloo.csnet
> ARPA:  ndiamond%watdaisy%waterloo.csnet@csnet-relay.arpa

	I don't know what it is... that's why I posted it.  There does
	seem to be a binary search going on, but...  what is being
	searched for?  If there is a resulting L for each A, why not
	use A as an index into a table?
-------------------------------------------------------------------------------
> From:	RHEA::DECWRL::"cc1@UCLA-LOCUS.ARPA" 
> 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
	Which 8 memory locations?  Why L shifted left and why is
	the carry shifted in?  Your answer would be more plausible
	if you could answer these questions.
-------------------------------------------------------------------------------
> 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.

	This is the most thorough guess I've seen.  I'm not sure what
	such a search is good for.  I also don't see why it wouldn't
	be faster to set the table up so it can be indexed directly
	by A. Move A to L, move (HL) to L and you're done.  Is the
	resulting value of B important?
-------------------------------------------------------------------------------

	I think the last answer is best so far... but I still don't
	feel we have the final answer.  If anyone KNOWS the answer
	from previous experience (Dr. Dobb is not talking) please
	post the answer now.  Any explanation must specify the
	contents of the table, the initial contents of A, L and B and
	the expected results in L and B.  Unless the algorithm produces
	different (useful) results for different initial values of
	L or B, or produces useful results in BOTH L and B, it will
	not fit the criteria of being fast because a simple table
	lookup would be faster.

	I hope we get an answer soon!


		-John A. Wasser

Work address:
ARPAnet:	WASSER%VIKING.DEC@decwrl.ARPA
Usenet:		{allegra,Shasta,decvax}!decwrl!dec-rhea!dec-viking!wasser
USPS:		Digital Equipment Corp.
		Mail stop: LJO2/E4
		30 Porter Rd
		Littleton, MA  01460