Date: Thu, 02 Sep 1993 10:13:36 -0400 (EDT) From: "Edward J. Huff" <HUFF@MCCLB0.MED.NYU.EDU> Subject: Comments for median function
To: wayne@helix.nih.gov
Organization: NYU Medical Center, 550 First Ave., New York, 10016 X-Envelope-To: wayne@helix.nih.gov
X-Vms-To: IN%"wayne@helix.nih.gov"
X-Vms-Cc: HUFF
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; CHARSET=US-ASCII Content-Transfer-Encoding: 7BIT

I would suggest putting these comments in place of the body of the original findMedian function in Utilities.p. The test function, not called, does not consume any room in the built application. The comments were produced from the MPW .a file which was assembled to make the hex. I have an MPW .c file which when linked with a file declaring "decl" and "code" and "endcode" writes the hex to standard output, after copying standard input to output with added braces and other necessary changes like (* to ( *, etc. This code was originally written in assembler, there is no .c file. 

{; find the 5th largest of 9 unsigned shorts } {; in the case of equal values, consider either one smaller } {See Knuth, Vol 3 (Sorting and Searching) Section 5.3.3 exercise 11} { }
{ CASE YES }
{ MACHINE MC68020 }
{decl PROC EXPORT }
{ LEA str,A0 }
{ MOVE.L A0,D0 }
{ RTS }
{ DATA }
{ STRING ASIS }
{str DC.B 'function findMedian(var a: SortArray): integer; inline' } { DC.B 0 }
{ ENDPROC }
{ }
{code PROC EXPORT }
{ EXPORT endcode }
{ MOVE.L (A7)+,A0 }
{ MOVEM.L D3-D7,-(A7) }
{ movem.w (a0)+,d0-d7 }
{ cmp.w d1,d0 }
{ blo.s @1 }
{ exg d1,d0 }
{@1 ;d0 <= d1 }
{ cmp.w d3,d2 }
{ blo.s @2 }
{ exg d3,d2 }
{@2 ;d2 <= d3 }
{ cmp.w d3,d1 }
{ blo.s @3 }
{ exg d2,d0 }
{ exg d3,d1 }
{@3 ;d0 <= d1, d1 <= d3, d2 <= d3 }
{ cmp.w d5,d4 }
{ blo.s @4 }
{ exg d5,d4 }
{@4 ;d4 <= d5 }
{ cmp.w d7,d6 }
{ blo.s @5 }
{ exg d7,d6 }
{@5 ;d6 <= d7 }
{ cmp.w d7,d5 }
{ blo.s @6 }
{ exg d6,d4 }
{ exg d7,d5 }
{@6 ;d4 <= d5, d5 <= d7, d6 <= d7 }
{ cmp.w d5,d1 }
{ blo.s @7 }
{ exg d7,d3 }
{ exg d6,d2 }
{ exg d5,d1 }
{ exg d4,d0 }
{@7 ;d0 <= d1, d1 <= d5, d4 <= d5, d5 <= d7, d6 <= d7 } { ; (also, d1 <= d3, d2 <= d3) }
{ ; hence, d0, d1, d4, d5, and d6 are all <= d7 } { ; hence d7 cannot be the median. }
{ move.w (a0),d7 ;pick up the 9th value into d7 } { cmp.w d7,d6 }
{ blo.s @8 }
{ exg d7,d6 }
{@8 ;d6 <= d7 }
{ cmp.w d7,d5 }
{ blo.s @9 }
{ exg d6,d4 }
{ exg d7,d5 }
{@9 ;d4 <= d5, d5 <= d7, d6 <= d7 }
{ cmp.w d5,d1 }
{ blo.s @10 }
{ exg d7,d3 }
{ exg d6,d2 }
{ exg d5,d1 }
{ exg d4,d0 }
{@10 ;d0 <= d1, d1 <= d5, d4 <= d5, d5 <= d7, d6 <= d7 } { ; (also, d1 <= d3, d2 <= d3) }
{ ; hence, d0, d1, d4, d5, and d6 are all <= d7 } { ; hence 5 values are smaller than d7 } { ; hence d7 cannot be the median. }
{ ; also, d0 <= all of d1, d3, d5, d7, old d7 } { ; hence 5 values are larger than d0 }
{ ; hence d0 cannot be the median. }
{ ; possible medians are d1, d2, d3, d4, d5, d6 } { cmp.w d6,d1 }
{ blo.s medof5 }
{ ; d6 <= d1 }
{ ; hence d6 <= all of d1, d3, d5, d7, old d7 } { ; possible medians are d1, d2, d3, d4, d5 } { ; d1 <= d3, d2 <= d3, d1 <= d5, d4 <= d5 } { cmp.w d2,d1 }
{ blo.s @11 }
{ ; d2 <= all of d1, d3, d5, d7, old d7 } { ; d0, d1, d2, d4, d6 all <= d5 }
{ ; leaving d1, d3, d4 }
{ cmp.w d4,d1 }
{ blo.s @10a }
{ ; d4 <= d1, the median is d1. }
{ ; d4 <= all of d1, d3, d5, d7, old d7 } { ; d0, d1, d2, d4, d6 all <= d3 }
{ move.w d1,d0 }
{ bra.s done }
{ }
{@10a ; d1 < d4 }
{ ; d1 <= all of d3, d4, d5, d7, old d7 } { ; leaving d3, d4 }
{ cmp.w d4,d3 }
{ blo.s @10b }
{ ; d4 <= d3, the median is d4. }
{ ; d0, d1, d2, d4, d6 all <= d3 }
{ move.w d4,d0 }
{ bra.s done }
{ }
{@10b ; d3 < d4, the median is d3. }
{ ; d0, d1, d2, d3, d6 all <= d4 }
{ move.w d3,d0 }
{ bra.s done }
{ }
{@11 ;d1 < d2 }
{ ; d1 <= all of d2, d3, d5, d7, old d7 } { ; leaving d2, d3, d4, d5 }
{ ; d2 <= d3, d4 <= d5 }
{ cmp.w d4,d2 }
{ blo.s @12 }
{ ; d4 <= all of d2, d3, d5, d7, old d7 } { ; leaving d2, d3, d5 }
{ cmp.w d5,d2 }
{ blo.s @11a }
{ ; d5 <= d2 }
{ ; d0, d1, d4, d5, d6 all <= d2 }
{ ; d0, d1, d2, d4, d5, d6 all <= d3 }
{ ; median is d5 }
{ move.w d5,d0 }
{ bra.s done }
{ }
{@11a ; d2 < d5 }
{ ; d0, d1, d2, d4, d6 all <= d5 }
{ ; d0, d1, d2, d4, d6 all <= d3 }
{ ; median is d2 }
{ move.w d2,d0 }
{ bra.s done }
{ }
{@12 ; d2 < d4 }
{ ; d2 <= all of d3, d4, d5, d7, old d7 } { ; d0, d1, d2, d4, d6 all <= d5 }
{ ; leaving d3, d4 }
{ cmp.w d4,d3 }
{ blo.s @12a }
{ ; d4 <= d3 }
{ ; d0, d1, d2, d4, d6 all <= d3 }
{ ; median is d4 }
{ move.w d4,d0 }
{ bra.s done }
{@12a ; d3 < d4 }
{ ; d0, d1, d2, d3, d6 all <= d4 }
{ ; median is d3 }
{ move.w d3,d0 }
{ bra.s done }
{ }
{medof5 ;d1 < d6 }
{ ; d1 <= all of d3, d5, d6, d7, old d7 } { ; leaving d2, d3, d4, d5, d6 }
{ ; and the median is the third largest of these } { ; d2 <= d3, d4 <= d5 }
{ cmp.w d5,d3 }
{ blo.s @1 }
{ exg d4,d2 }
{ exg d5,d3 }
{@1 ;d2 <= d3, d3 <= d5, d4 <= d5 }
{ cmp.w d6,d4 }
{ blo.s @cmp36 }
{ ; d6 <= d4 }
{ cmp.w d4,d3 }
{ blo.s @cmp36a }
{ ; d4 <= d3 }
{ cmp.w d4,d2 }
{ blo.s @med4 }
{ ; d4 <= d2 }
{ move.w d2,d0 }
{ bra.s done }
{@med4 move.w d4,d0 }
{ bra.s done }
{@cmp36a ;d3 < d4 }
{ cmp.w d6,d3 }
{ blo.s @med6 }
{ ; d6 <= d3 }
{ move.w d3,d0 }
{ bra.s done }
{@med6 move.w d6,d0 }
{ bra.s done }
{@cmp36 ;d4 < d6 }
{ cmp.w d6,d3 }
{ blo.s @cmp34 }
{ ; d6 <= d3 }
{ cmp.w d6,d2 }
{ blo.s @med6 }
{ move.w d2,d0 }
{ bra.s done }
{@cmp34 ;d3 < d6 }
{ cmp.w d4,d3 }
{ blo.s @med4 }
{ ; d4 <= d3 }
{ move.w d3,d0 }
{ ; bra.s done }
{done: }
{ MOVEM.L (A7)+,D3-D7 }
{ MOVE.W D0,(A7) }
{endcode: }
{ ENDPROC }
{ END }
{}

{This was used to test the inline code exhaustively} 
procedure testMedian;
var
a: SortArray;
i1, i2, i3, i4, i5, i6, i7, i8, i9: integer; begin
for i1 := 1 to 9 do
a[i1] := 0;
for i1 := 1 to 9 do
if a[i1] = 0 then begin
a[i1] := 1;
for i2 := 1 to 9 do
if a[i2] = 0 then begin
a[i2] := 2;
for i3 := 1 to 9 do
if a[i3] = 0 then begin
a[i3] := 3;
for i4 := 1 to 9 do
if a[i4] = 0 then begin
a[i4] := 4;
for i5 := 1 to 9 do
if a[i5] = 0 then begin
a[i5] := 5;
for i6 := 1 to 9 do
if a[i6] = 0 then begin
a[i6] := 6;
for i7 := 1 to 9 do
if a[i7] = 0 then begin
a[i7] := 7;
for i8 := 1 to 9 do
if a[i8] = 0 then begin
a[i8] := 8;
for i9 := 1 to 9 do
if a[i9] = 0 then begin
a[i9] := 9;
if findMedian(a) <> 5 then
putMessage('bad median');
a[i9] := 0;
end;
a[i8] := 0;
end;
a[i7] := 0;
end;
a[i6] := 0;
end;
a[i5] := 0;
end;
a[i4] := 0;
end;
a[i3] := 0;
end;
a[i2] := 0;
end;
a[i1] := 0;
end;
end;