Xref: utzoo comp.arch:17143 comp.lang.misc:5166
Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!samsung!noose.ecn.purdue.edu!mentor.cc.purdue.edu!l.cc.purdue.edu!cik
From: cik@l.cc.purdue.edu (Herman Rubin)
Newsgroups: comp.arch,comp.lang.misc
Subject: An example of a program (long)
Keywords: coding efficiency, use of peculiar instructions.
Message-ID: <2362@l.cc.purdue.edu>
Date: 15 Jul 90 22:44:04 GMT
Reply-To: cik@l.cc.purdue.edu (Herman Rubin)
Followup-To: comp.arch
Organization: Purdue University Statistics Department
Lines: 128


There have been request for me to post a program which points out some 
of the problems with HLLs.  This is written in "sort of" C.  There may
be minor errors.  This program is rather long, and is rather incomplete.
It would have taken me no longer to write this in a reasonable assembler,
but I am writing it this way for easier readability by the audience.
It is not completely optimized, but would do a good job with an optimizing
assembler.  Note also the use of assigns.  If fall-through is faster than
goto, the rather weird arrangement of the code is time-saving.

Each time G is used, a new random variable with probability(G = i) = 2^(-i)
is obtained.  The if(RANBIT == 0) can be any test with probability 1/2
of success, again a new one at each stage.  This program is typical of 
programs requiring these; an assessment of the timing shows that these
can constitute a large part of the operating time, so that there is a
point in making these hardware instructions.

The switch statement should be optimized as suggested.  There is one place
where some code is to be carried out for all subsequent cases; my knowledge
of C is inadequate for this purpose.

The outcome at each stage is either a negative number, or a bit mask, which
may be 0.

for(i = begarray; i <= endarray; i++){
Preliminaries (includes checking that enough G's are available; the
omitted portions, which are uncommon, have additional such checks.)

start:	n = G;
	switch(n){		/* Optimize by test and jump if greater */
	case  1:
a1:	out(i)=0; break;
	case  2:
	if (RANBIT == 0){
		assign a1 to j; goto testm;}
	else
ab:
	out(i)= NEG; break;
	case 3:
a2:	out(i) = b >> G; break;
	case 4:
	out(i)= NEG; break;
	case 5:
	assign a2 to j;
	goto testm;
				/* this next line applies for n >= 6	*/
	mask = 0; q = b;
	case 6:
a3:	m4 = 1;
w3:	.......			/* w code will be written together later, but
				   the blocks should be allocated as shown */
	case 7:
a4:	k = G;
	m4 = k>>1;
	if (ODD(k) { m4 += 2; goto w3;}
w4:	......			/* see above remark about w blocks	*/

	case 8:
	assign a3 to j; goto testm;
	case 9:
	assign a4 to j; goto testm;
	case 10:
	case 11:
	case 13;
	goto ab;
	default:
	if(ODD(n))goto high;
	m16 = (n-8) .. 2;
	if(ODD(n>1)){
	assign w5 to j; goto testm;
	}

w5:	......			/* see above remark about w blocks	*/

high:	m16 = (n-11) .. 2;
	if(EVEN(n>1)){
	assign a6 to j; goto testm;
	}
a6:	nn = G;
	m4 = (nn+1)>>1;
	m = 6;
	if (EVEN(nn)) goto a7;

wh:	......			/* see above remark about w blocks	*/

a7:     ................	/* code omitted; ends up at wh or ab	*/
	}

testm:	n = G;
	if (n == 1) goto *j;
	.............		/* code omitted; ends up at *j or ab	*/

/* 	Now for the w blocks	*/

w1:	out(i) = mask; break;
w2:	out(i) = mask | q >> G; break;

w3:	n + G;
w3a:	q >> m4;
	out(i) = mask | q | q >> (n-1); break;

w4:	n = G;
	mask |= q >> n;
	if (m4 >= n){
	if (RANBIT == 0)goto w1;
	q >> 1; goto w3a;
	}
	out(i)= mask | q>> m4;

w5:	q >>= m16;
	mask |= q;
	n = G;
	if (RANBIT == 0){
	if(ODD(n))goto w2:
	goto w1:
	}
	m4 = (n+1)>>1;
	if(ODD(n))goto w3:
	goto w4:

wh:	.............		/* code omitted; ends up at some w	*/


}
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet)	{purdue,pur-ee}!l.cc!cik(UUCP)