9.2.2 The HLA SWITCH/CASE Statement

HLA doesn't support a selection statement (SWITCH or CASE statement). Instead, HLA's SWITCH..CASE..DEFAULT..ENDSWITCH statement exists only as a macro in the HLA Standard Library HLL.HHF file. This section discusses HLA's macro implementation of the SWITCH statement.

The SWITCH statement is very complex so it should come as no surprise that the macro implementation is long, involved, and complex. The example appearing in this section is slightly simplified over the standard HLA version, but not by much. This discussion assumes that you're familiar with the low-level implementation of the SWITCH..CASE..DEFAULT..ENDSWITCH statement. If you are not comfortable with that implementation, or feel a little rusty, you may want to take another look at "SWITCH/CASE Statements" on page 776 before attempting to read this section. The discussion in this section is somewhat advanced and assumes a fair amount of programming skill. If you have trouble following this discussion, you may want to skip this section until you gain some more experience.

There are several different ways to implement a SWITCH statement. In this section we will assume that the _switch.._endswitch macro we are writing will implement the SWITCH statement using a jump table. Implementation as a sequence of if..elseif statements is fairly trivial and is left as an exercise. Other schemes are possible as well, this section with not consider them.

A typical SWITCH statement implementation might look like the following:

readonly
 
	JmpTbl:dword[3] := [ &Stmt5, &Stmt6, &Stmt7 ];
 
		 .
 
		 .
 
		 .
 

 
// switch( i )
 

 
	mov( i, eax );              // Check to see if "i" is outside the range
 
	cmp( eax, 5 );              // 5..7 and transfer control directly to the
 
	jb EndCase                  // DEFAULT case if it is.
 
	cmp( eax, 7 );
 
	ja EndCase;
 
	jmp( JmpTbl[ eax*4 - 5*@size(dword)] );

// case( 5 )
 
		Stmt5:
 
			stdout.put( "I=5" );
 
			jmp EndCase;
 

 
// Case( 6 )
 
		Stmt6:
 
			stdout.put( "I=6" );
 
			jmp EndCase;
 

 
// Case( 7 )
 
		Stmt7:
 
			stdout.put( "I=7" );
 

 
	EndCase:

If you study this code carefully, with an eye to writing a macro to implement this statement, you'll discover a couple of major problems. First of all, it is exceedingly difficult to determine how many cases and the range of values those cases cover before actually processing each CASE in the SWITCH statement. Therefore, it is really difficult to emit the range check (for values outside the range 5..7) and the indirect jump before processing all the cases in the SWITCH statement. You can easily solve this problem, however, by moving the checks and the indirect jump to the bottom of the code and inserting a couple of extra JMP instructions. This produces the following implementation:

readonly
 
	JmpTbl:dword[3] := [ &Stmt5, &Stmt6, &Stmt7 ];
 
		 .
 
		 .
 
		 .
 

 
// switch( i )
 

 
	jmp DoSwitch;              // First jump inserted into this code.

// case( 5 )
 
		Stmt5:
 
			stdout.put( "I=5" );
 
			jmp EndCase;
 

 
// Case( 6 )
 
		Stmt6:
 
			stdout.put( "I=6" );
 
			jmp EndCase;
 

 
// Case( 7 )
 
		Stmt7:
 
			stdout.put( "I=7" );
 
			jmp EndCase;         // Second jump inserted into this code.
 

 
DoSwitch:                      // Insert this label and move the range
 
	mov( i, eax );              // checks and indirect jump down here.
 
	cmp( eax, 5 );
 
	jb EndCase
 
	cmp( eax, 7 );
 
	ja EndCase;
 
	jmp( JmpTbl[ eax*4 - 5*@size(dword)] );
 

 
// All the cases (including the default case) jump down here:
 

 
EndCase:

Since the range check code appears after all the cases, the macro can now process those cases and easily determine the bounds on the cases by the time it must emit the CMP instructions above that check the bounds of the SWITCH value. However, this implementation still has a problem. The entries in the JmpTbl table refer to labels that can only be determined by first processing all the cases in the SWITCH statement. Therefore, a macro cannot emit this table in a READONLY section that appears earlier in the source file than the SWITCH statement. Fortunately, HLA lets you embed data in the middle of the code section using the READONLY..ENDREADONLY and STATIC..ENDSTATIC directives¹. Taking advantage of this feature allows use to rewrite the SWITCH implementation as follows:

// switch( i )
 

 
	jmp DoSwitch;              // First jump inserted into this code.

// case( 5 )
 
		Stmt5:
 
			stdout.put( "I=5" );
 
			jmp EndCase;
 

 
// Case( 6 )
 
		Stmt6:
 
			stdout.put( "I=6" );
 
			jmp EndCase;
 

 
// Case( 7 )
 
		Stmt7:
 
			stdout.put( "I=7" );
 
			jmp EndCase;         // Second jump inserted into this code.
 

 
DoSwitch:                      // Insert this label and move the range
 
	mov( i, eax );              // checks and indirect jump down here.
 
	cmp( eax, 5 );
 
	jb EndCase
 
	cmp( eax, 7 );
 
	ja EndCase;
 
	jmp( JmpTbl[ eax*4 - 5*@size(dword)] );
 

 
// All the cases (including the default case) jump down here:
 

 
EndCase:
 

 
readonly
 
	JmpTbl:dword[3] := [ &Stmt5, &Stmt6, &Stmt7 ];
 
endreadonly;

HLA's macros can produce code like this when processing a SWITCH macro. So this is the type of code we will generate with a _switch.._case.._default.._endswitch macro.

Since we're going to need to know the minimum and maximum case values (in order to generate the appropriate operands for the CMP instructions above), the _case #KEYWORD macro needs to compare the current case value(s) against the global minimum and maximum case values for all cases. If the current case value is less than the global minimum or greater than the global maximum, then the _case macro must update these global values accordingly. The _endswitch macro will use these global minimum and maximum values in the two CMP instructions it generates for the range checking sequence.

For each case value appearing in a _switch statement, the _case macros must save the case value and an identifying label for that case value. This is necessary so that the _endswitch macro can generate the jump table. What is really needed is an arbitrary list of records, each record containing a value field and a label field. Unfortunately, the HLA compile-time language does not support arbitrary lists of objects, so we will have to implement the list using a (fixed size) array of record constants. The record declaration will take the following form:

caseRecord:
 
	record
 
		value:uns32;
 
		label:uns32;
 
	endrecord;

The value field will hold the current case value. The label field will hold a unique integer value for the corresponding _case that the macros can use to generate statement labels. The implementation of the _switch macro in this section will use a variant of the trick found in the section on the _if macro; it will convert a local macro symbol to a string and append an integer value to the end of that string to create a unique label. The integer value appended will be the value of the label field in the caseRecord list.

Processing the _case macro becomes fairly easy at this point. All the _case macro has to do is create an entry in the caseRecord list, bump a few counters, and emit an appropriate case label prior to the code emission. The implementation in this section uses Pascal semantics, so all but the first case in the _switch.._endswitch statement must first emit a jump to the statement following the _endswitch so the previous case's code doesn't fall into the current case.

The real work in implementing the _switch.._endswitch statement lies in the generation of the jump table. First of all, there is no requirement that the cases appear in ascending order in the _switch.._endswitch statement. However, the entries in the jump table must appear in ascending order. Second, there is no requirement that the cases in the _switch.._endswitch statement be consecutive. Yet the entries in the jump table must be consecutive case values². The code that emits the jump table must handle these inconsistencies.

The first task is to sort the entries in the caseRecord list in ascending order. This is easily accomplished by writing a little SortCases macro to sort all the caseRecord entries once the _switch.._endswitch macro has processed all the cases. SortCases doesn't have to be fancy. In fact, a bubblesort algorithm is perfect for this because:

Bubble sort is easy to implement
Bubble sort is efficient when sorting small lists and most SWITCH statements only have a few cases.
Bubble sort is especially efficient on nearly sorted data and most programmers put their cases in ascending order.

After sorting the cases, only one problem remains: there may be gaps in the case values. This problem is easily handled by stepping through the caseRecord elements one by one and synthesizing consecutive entries whenever a gap appears in the list. Program 9.4 provides the full _switch.._case.._default.._endswitch macro implementation.


 
/**************************************************/
 
/*                                                */
 
/* switch.hla-                                    */
 
/*                                                */
 
/* This program demonstrates how to implement the */
 
/* _switch.._case.._default.._endswitch statement */
 
/* using macros.                                  */
 
/*                                                */
 
/**************************************************/
 

 
                 
 
program demoSwitch;
 
#include( "stdlib.hhf" )
 

 
const
 

 
    // Because this code uses an array to implement
 
    // the caseRecord list, we have to specify a fixed
 
    // number of cases.  The following constant defines
 
    // the maximum number of possible cases in a 
 
    // _switch statement.
 
    
 
    maxCases := 256;
 

 
type
 

 
    // The following data type hold the case value
 
    // and statement label information for each
 
    // case appearing in a _switch statement.
 
    
 
    caseRecord:
 
        record
 

 
            value:uns32;
 
            lbl:uns32;
 

 
        endrecord;
 

 

 
// SortCases
 
//
 
//  This routine does a bubble sort on an array
 
// of caseRecord objects.  It sorts in ascending
 
// order using the "value" field as the key.
 
//
 
// This is a good old fashioned bubble sort which
 
// turns out to be very efficient because:
 
//
 
//  (1) The list of cases is usually quite small, and
 
//  (2) The data is usually already sorted (or mostly sorted).
 

 
macro SortCases( sort_array, sort_size ):
 
    sort_i, 
 
    sort_bnd, 
 
    sort_didswap, 
 
    sort_temp;
 

 
    ?sort_bnd := sort_size - 1;
 
    ?sort_didswap := true;
 
    #while( sort_didswap )
 
    
 
        ?sort_didswap := false;
 
        ?sort_i := 0;
 
        #while( sort_i < sort_bnd )
 
        
 
            #if
 
            ( 
 
                sort_array[sort_i].value > 
 
                    sort_array[sort_i+1].value 
 
            )
 
            
 
                ?sort_temp := sort_array[sort_i];
 
                ?sort_array[sort_i] := sort_array[sort_i+1];
 
                ?sort_array[sort_i+1] := sort_temp;
 
                ?sort_didswap := true;
 
                
 
            #elseif
 
            ( 
 
                sort_array[sort_i].value = 
 
                    sort_array[sort_i+1].value 
 
            )
 
            
 
                #error
 
                ( 
 
                    "Two cases have the same value: (" +
 
                    string( sort_array[sort_i].value ) +
 
                    ")"
 
                )
 
                
 
            #endif
 
            ?sort_i := sort_i + 1;
 
            
 
        #endwhile
 
        ?sort_bnd := sort_bnd - 1;
 
        
 
    #endwhile;
 
        
 
    
 
endmacro;
 

 

 

 

 
    
 

 

 

 

 
// HLA Macro to implement a C SWITCH statement (using
 
// Pascal semantics). Note that the switch parameter 
 
// must be a 32-bit register.
 

 
macro _switch( switch_reg ): 
 
    switch_minval, 
 
    switch_maxval, 
 
    switch_otherwise,
 
    switch_endcase, 
 
    switch_jmptbl,
 
    switch_cases,
 
    switch_caseIndex,
 
    switch_doCase,
 
    switch_hasotherwise;        // Just used to generate unique names.
 

 

 
    // Verify that we have a register operand.
 
    
 
    #if( !@isReg32( switch_reg ) )
 
    
 
        #error( "Switch operand must be a 32-bit register" )
 
        
 
    #endif
 
    
 
    // Create the switch_cases array.  Allow, at most, 256 cases.
 
    
 
    ?switch_cases:caseRecord[ maxCases ];
 
    
 
    // General initialization for processing cases.
 
    
 
    ?switch_caseIndex := 0;         // Index into switch_cases array.
 
    ?switch_minval := $FFFF_FFFF;   // Minimum case value.
 
    ?switch_maxval := 0;            // Maximum case value.
 
    ?switch_hasotherwise := false;  // Determines if DEFAULT section present.
 

 

 
            
 
    // We need to process the cases to collect information like
 
    // switch_minval prior to emitting the indirect jump.  So move the
 
    // indirect jump to the bottom of the case statement.
 
    
 
    jmp switch_doCase;
 

 

 
    // "case" keyword macro handles each of the cases in the
 
    // case statement.  Note that this syntax allows you to
 
    // specify several cases in the same _case macro, e.g.,
 
    // _case( 2, 3, 4 ).  Such a situation tells this macro
 
    // that these three values all execute the same code.
 
    
 
keyword _case( switch_parms[] ):
 
    switch_parmIndex, 
 
    switch_parmCount, 
 
    switch_constant;
 
    
 
    ?switch_parmCount:uns32;
 
    ?switch_parmCount := @elements( switch_parms );
 

 
    #if( switch_parmCount <= 0 )
 

 
        #error( "Must have at least one case value" );
 
        ?switch_parms:uns32[1] := [0];
 

 
    #endif
 

 
    // If we have at least one case already, terminate
 
    // the previous case by transfering control to the
 
    // first statement after the endcase macro.  Note
 
    // that these semantics match Pascal's CASE statement,
 
    // not C/C++'s SWITCH statement which would simply
 
    // fall through to the next CASE.
 
    
 
    #if( switch_caseIndex <> 0 )
 

 
        jmp switch_endcase;
 

 
    #endif
 

 
    // The following loop processes each case value
 
    // supplied to the _case macro.
 
    
 
    ?switch_parmIndex:uns32;
 
    ?switch_parmIndex := 0;
 
    #while( switch_parmIndex < switch_parmCount )
 
    
 
        ?switch_constant: uns32;
 
        ?switch_constant: uns32 := 
 
            uns32( @text( switch_parms[ switch_parmIndex ]));
 

 
        // Update minimum and maximum values based on the
 
        // current case value.
 
        
 
        #if( switch_constant < switch_minval )
 

 
            ?switch_minval := switch_constant;
 

 
        #endif
 
        #if( switch_constant > switch_maxval )
 

 
            ?switch_maxval := switch_constant;
 

 
        #endif
 

 
        // Emit a unique label to the source code for this case:
 
        
 
        @text
 
        ( 
 
                "_case" 
 
            +   @string:switch_caseIndex 
 
            +   string( switch_caseIndex ) 
 
        ):
 
        
 
        // Save away the case label and the case value so we
 
        // can build the jump table later on.
 
        
 
        ?switch_cases[ switch_caseIndex ].value := switch_constant;
 
        ?switch_cases[ switch_caseIndex ].lbl := switch_caseIndex;
 
        
 
        // Bump switch_caseIndex value because we've just processed
 
        // another case.
 
        
 
        ?switch_caseIndex := switch_caseIndex + 1;
 
        #if( switch_caseIndex >= maxCases )
 

 
            #error( "Too many cases in statement" );
 

 
        #endif
 

 
        ?switch_parmIndex := switch_parmIndex + 1;
 

 
    #endwhile
 

 

 
    
 
    // Handle the default keyword/macro here.
 
    
 
keyword _default;
 

 
    // If there was not a preceding case, this is an error.
 
    // If so, emit a jmp instruction to skip over the
 
    // default case.
 
    
 
    #if( switch_caseIndex < 1 )
 

 
        #error( "Must have at least one case" );
 

 
    #endif
 

 
        jmp switch_endcase;
 

 
    
 
    // Emit the label for this default case and set the
 
    // switch_hasotherwise flag to true.
 
    
 
    switch_otherwise:
 
    ?switch_hasotherwise := true;
 

 

 
    // The endswitch terminator/macro checks to see if
 
    // this is a reasonable switch statement and emits
 
    // the jump table code if it is.
 
    
 
terminator _endswitch:
 
    switch_i_, 
 
    switch_j_, 
 
    switch_curCase_;
 

 

 
    // If the difference between the smallest and
 
    // largest case values is great, the jump table
 
    // is going to be fairly large.  If the difference
 
    // between these two values is greater than 256 but
 
    // less than 1024, warn the user that the table will
 
    // be large.  If it's greater than 1024, generate
 
    // an error.
 
    //
 
    // Note: these are arbitrary limits.  Feel free to
 
    // adjust them if you like.
 
    
 
    #if( (switch_maxval - switch_minval) > 256 )
 

 
        #if( (switch_maxval - switch_minval) > 1024 )
 

 
            // Perhaps in the future, this macro could
 
            // switch to generating an if..elseif..elseif...
 
            // chain if the range between the values is
 
            // too great.
 
            
 
            #error( "Range of cases is too great" );
 

 
        #else
 

 
            #print( "Warning: Range of cases is large" );
 

 
        #endif
 

 
    #endif
 
    
 
    // Table emission algorithm requires that the switch_cases
 
    // array be sorted by the case values.
 
    
 
    SortCases( switch_cases, switch_caseIndex );
 

 
    
 
    // Build a string of the form:
 
    //
 
    //      switch_jmptbl:dword[ xx ] := [&case1, &case2, &case3...&casen];
 
    //
 
    // so we can output the jump table.
 
    
 
    readonly
 
    
 
        switch_jmptbl:dword[ switch_maxval - switch_minval + 2] := [
 

 
        ?switch_i_ := 0;
 
        #while( switch_i_ < switch_caseIndex )
 

 
            ?switch_curCase_ := switch_cases[ switch_i_ ].value;
 
            // Emit the label associated with the current case:
 

 
            @text
 
            ( 
 
                    "&" 
 
                +   "_case"
 
                +   @string:switch_caseIndex 
 
                +   string( switch_cases[ switch_i_ ].lbl ) 
 
                +   ","
 
            )
 
            
 
            // Emit "&switch_otherwise" table entries for any gaps present
 
            // in the table:
 
                
 
            ?switch_j_ := switch_cases[ switch_i_ + 1 ].value;
 
            ?switch_curCase_ := switch_curCase_ + 1;
 

 
            #while( switch_curCase_ < switch_j_ )
 

 
                &switch_otherwise,
 
                ?switch_curCase_ := switch_curCase_ + 1;
 

 
            #endwhile
 
            ?switch_i_ := switch_i_ + 1;
 

 
        #endwhile
 
        
 
        // Emit a dummy entry to terminate the table:
 
        
 
        &switch_otherwise];
 

 

 
    endreadonly;
 
    
 
    #if( switch_caseIndex < 1 )
 

 
        #error( "Must have at least one case" );
 

 
    #endif
 

 
        // After the default case, or after the last
 
        // case entry, jump over the code that does
 
        // the conditional jump.
 

 
        jmp switch_endcase;
 

 
    // Okay, here's the code that does the conditional jump.
 
        
 
    switch_doCase:
 
    
 
        // If the minimum case value is zero, we don't
 
        // need to emit a CMP instruction for it.
 
        
 
        #if( switch_minval <> 0 )
 
        
 
            cmp( switch_reg, switch_minval );
 
            jb switch_otherwise;
 
            
 
        #endif
 
        cmp( switch_reg, switch_maxval );
 
        ja switch_otherwise;
 
        jmp( switch_jmptbl[ switch_reg*4 - switch_minval*4 ] );
 

 

 

 
    // If there was no default case, transfer control
 
    // to the first statement after the "endcase" clause.
 
    
 
    #if( !switch_hasotherwise )
 
    
 
        switch_otherwise:
 
        
 
    #endif
 
    
 
    // When each of the cases complete execution,
 
    // transfer control down here.
 
    
 
    switch_endcase:
 
    
 
    // The following statement deallocates the storage
 
    // assocated with the switch_cases array (this saves
 
    // memory at compile time, it does not affect the
 
    // execution of the resulting machine code).
 
    
 
    ?switch_cases := 0;
 

 

 

 
endmacro;
 

 

 
begin demoSwitch;
 

 

 
    // A simple demonstration of the _switch.._endswitch statement:
 

 
    for( mov( 0, eax ); eax < 8; inc( eax )) do
 
    
 
        _switch( eax )
 
        
 
            _case( 0 )
 
            
 
                stdout.put( "eax = 0" nl );
 
                
 
            _case( 1, 2 )
 
            
 
                stdout.put( "eax = 1 or 2" nl );
 

 
            _case( 3, 4, 5 )
 
            
 
                stdout.put( "eax = 3, 4, or 5" nl );
 
                
 
            _case( 6 )
 
            
 
                stdout.put( "eax = 6" nl );
 
                
 
            _default
 
            
 
                stdout.put( "eax is not in the range 0-6" nl );
 
                
 
        _endswitch;
 
        
 
    endfor;             
 
                
 
end demoSwitch;
 

 
Program 9.4	 Macro Implementation of the SWITCH..ENDSWITCH Statement

¹HLA actually moves the data to the appropriate segment in memory, the data is not stored directly in the CODE section.

²Of course, if there are gaps in the case values, the jump table entries for the missing items should contain the address of the default case.

9.2.2 The HLA SWITCH/CASE Statement

Web Site Hits Since Jan 1, 2000

Web Site Hits Since
Jan 1, 2000