Sender:	crough45 AT amc DOT de
Date:	Mon, 14 Apr 1997 11:13:52 +0100
From:	Chris Croughton <crough45 AT amc DOT de>
Mime-Version:	1.0
To:	MCLSSAA2 AT fs2 DOT mt DOT umist DOT ac DOT uk
Cc:	djgpp AT delorie DOT com
Subject:	Re: How is switch implemented?
Message-Id:	<97Apr14.121115gmt+0100.21890@internet01.amc.de>

Anthony.Appleyard wrote:

>  What happens if a switch(i){...} contains `case 0:' and also `case 0xffff:'?
>Does it make a jump table 0x10000 elements long, occupying 0x40000 bytes of
>program memory? Or if a jump table would be too big does djgpp use tests and
>jumps?

I would hope it optimises it as test and jump.  If it doesn't then it's
seriously broken, in my opinion.  Unless, of course, you actually have
64K of different cases, in which case there's nothing it can do.

But the worst case is worse than that, because DJGPP ints are 32 bit,
so you could have cases from 0 to 0xFFFFFFFF which would need 16Gb of
jump table.  This is patently ridiculous, so it must optimise at some
point into a series of tests.

Some compilers take it further and will generate a set of jump tables,
or nested tables.  For instance:

  switch (x)
  {
    case 0x0000...0x00FF:
      ...
    case 0x1000...0x107F:
      ...
  }

could generate a two tables, one for the first range of 256 values and
one
for the second with 128 values, with a set of tests to determine which
one 
to use.  Or it could generate one table indexed by (x/256) pointing to a
set
of tables indexed by (x%256) (the pointer could be null if there was
nothing 
in the range).  Or a number of other schemes, including hash tables and
linked lists, depending on what the compiler thought was most efficient.

(Yes, I know C doesn't allow case ranges in switch statements.  In my
opinion it's a serious failure of the language...)

But to see what happens in the specific case you mentioned, write a
short 
program with the switch and compile it with -S to get the assembler
output.
you can then try different optimisation levels to see if that makes any
difference.  Sorry, I'm at work and don't have access to DJGPP here -
I can't read DEC AlphaStation assembler well enough to tell what it's
doing
exactly, but it doesn't seem to be using a jump table if a test and jump
is shorter, but does for cases where a linear jump table makes sense. 
The
following code generates a jump table:

  switch (x)
  {
    case 0:
      y(0);
      break;
    case 1:
      y(1);
      break;
    case 2:
      y(2);
      break;
    case 3:
      y(3);
      break;
    case 4:
      y(4);
      break;
    case 5:
      y(5);
      break;
    case 6:
      y(6);
      break;
    case 7:
      y(7);
      break;
  }

but if I add a case for 0xFFFF then it generates test and jump
sequences.
I'll try it when I get home and post the results if no-one beats me to
it...

Chris

- Raw text -