Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!bbn!gatech!prism!loligo!pepke
From: pepke@loligo (Eric Pepke)
Newsgroups: comp.sys.mac.programmer
Subject: THINK C Array Design Flaw
Message-ID: <664@loligo.cc.fsu.edu>
Date: 3 May 89 20:52:58 GMT
Sender: pepke@loligo.cc.fsu.edu
Reply-To: pepke@gw.scri.fsu.edu (Eric Pepke)
Distribution: na
Organization: Supercomputer Computations Research Institute
Lines: 105

First of all, THINK C is great.  It is a wonderful development environment,
the compiler is fast, the inline assembler works well, and the code is
adequate for most purposes.  However, there is a major design flaw regarding
the use of arrays larger than 32K in version 3.0.

In one of my programs I need to use an array of 32*32*32 short integers,
which is 64K long.  The segment loader problem doesn't bother me.  I am
perfectly happy allocating the memory, passing a pointer into a function,
and declaring it as I want it in the function.  So, I tried something like

AddHist(theHist, r, g, b)
short theHist[32][32][32];

which caused a compiler error, in spite of the fact that the function does
not have to define the array at all.  So, I thought that somebody had just
put the test in the wrong place in the compiler, and I tried

AddHist(theHist, r, g, b)
short theHist[][32][32];

which is perfectly legal C.  It compiled without a complaint.  Fortunately,
I am paranoid, so I checked to see what code it generated.  The code in this
case was correct, but it is generally incorrect when a dimension of the
array is other than a power of two. 

Consider these two functions:

short Access7(array, a, b)
short array[7][7];
short a, b;
{
    register short result;
    result = array[a][b];
}

Access4(array, a, b)
short array[4][4];
short a, b;
{
    register short result;
    result = array[a][b];
}

Here is the code produced:

  ACCESS7
     +0000  00196856   LINK       A6,#$0000          | 4E56 0000 
     +0004  0019685A   MOVE.L     D7,-(A7)           | 2F07 
     +0006  0019685C   MOVE.W     $000C(A6),D0       | 302E 000C 
     +000A  00196860   MULS.W     #$000E,D0          | C1FC 000E 
     +000E  00196864   ADD.L      $0008(A6),D0       | D0AE 0008 
     +0012  00196868   MOVE.W     $000E(A6),D1       | 322E 000E 
     +0016  0019686C   EXT.L      D1                 | 48C1 
     +0018  0019686E   ADD.L      D1,D1              | D281 
     +001A  00196870   ADD.L      D1,D0              | D081 
     +001C  00196872   MOVEA.L    D0,A0              | 2040 
     +001E  00196874   MOVE.W     (A0),D7            | 3E10 
     +0020  00196876   MOVE.L     (A7)+,D7           | 2E1F 
     +0022  00196878   UNLK       A6                 | 4E5E 
     +0024  0019687A   RTS                           | 4E75 

  ACCESS4
     +0000  00196884   LINK       A6,#$0000          | 4E56 0000 
     +0004  00196888   MOVE.L     D7,-(A7)           | 2F07 
     +0006  0019688A   MOVE.W     $000C(A6),D0       | 302E 000C 
     +000A  0019688E   EXT.L      D0                 | 48C0 
     +000C  00196890   ASL.L      #$3,D0             | E780 
     +000E  00196892   ADD.L      $0008(A6),D0       | D0AE 0008 
     +0012  00196896   MOVE.W     $000E(A6),D1       | 322E 000E 
     +0016  0019689A   EXT.L      D1                 | 48C1 
     +0018  0019689C   ADD.L      D1,D1              | D281 
     +001A  0019689E   ADD.L      D1,D0              | D081 
     +001C  001968A0   MOVEA.L    D0,A0              | 2040 
     +001E  001968A2   MOVE.W     (A0),D7            | 3E10 
     +0020  001968A4   MOVE.L     (A7)+,D7           | 2E1F 
     +0022  001968A6   UNLK       A6                 | 4E5E 
     +0024  001968A8   RTS                           | 4E75 

The techniques in both functions generalize to higher order and larger
arrays.  ACCESS4 does an arithmetic shift on a longword, so it can be
expected to work when the array is larger than 32K.  ACCESS7 only does a
single word multiply, so it can be expected to fail on large arrays.  It is
also a *signed* multiply, which makes little sense.

The code from MPW C is much more reasonable.  It does two unsigned word
multiplies, one on the high word and one on the low word of the cumulative
address, and adds the two together.

It would be *trivial* for the THINK people to fix the code generation.  If
they are worried about efficiency, they could install one more check box
into the options dialog.  It would be almost as trivial to fix the parser so
that large arrays could explicitly be declared as function parameters.

As it is, THINK C is useless for my application.  Just because I am
currently using a quantization that is a power of two does not mean that I
always will, and I cannot really trust future releases of THINK C to
generate correct code even for the power of two case.

Eric Pepke                                     ARPA:   pepke@gw.scri.fsu.edu
Supercomputer Computations Research Institute  MFENET: pepke@fsu
Florida State University                       SPAN:   pepke@scri
Tallahassee, FL 32306-4052                     BITNET: pepke@fsu

Disclaimer: My employers seldom even LISTEN to my opinions.
Meta-disclaimer: Any society that needs disclaimers has too many lawyers.