Homework 8

Array Data Structure/Character Strings/C++ Functions

Overview

In software development, it is not uncommon to mix high-level languages such as C++ with the power of assembly language where the added implementation expense of assembly programming is repaid by more efficient execution or access to specialized hardware operations. Operating systems, language compilers, hardware drivers, and other specialized applications often have a mixed high and low-level language component.

In previous discussions we have seen that Assembler, and C may be freely mixed when parameter passing protocols are strictly followed. These protocols require some minor changes to the C++ and the Assembler routines. These changes will be discussed relative to the home work assignment of implementing several common string routines. Unit testing of these routines will be done first using a stand alone C and assembly program. System testing will be done by integrated the routines with an Internet server that plays (badly) a TicTacToe game. The string functions to be implemented are:

These string routines will provide practice using processor-level operations on arrays of strings, and implementing functions that can be called by a variety of high and low-level languages. 

Passing Arrays in Visual C++

Arrays are passed by reference in C++, primarily for efficiency as only the starting address of the array need be passed rather than all variables of the array. Since a reference is a pointer, this fits well with the use of string instructions to implement array operations.  Generally C++ arrays are passed by reference as follows:
C++ Character Array Passing and Use 
char Array[5];

f(Array);

 

             Array   db   5 dup(?)          ;; byte array

            Push Offset Array               ;; Reference to the array
            Call f
            Add  eSp, 4

      Array   db   5 dup(?)      

      invoke f, addr Array

 
void f( char A[] ) {
    A[3] = 'X';
}
 
 
 

 

   f         Proc   Near
            Push   eBp
            Mov   eBp, eSp
            Push   eSi
            Mov   eSi, [eBp+8]
            Mov   [eSi+3], 'X'               ; A[3] = 'X'
            Pop    eSi
            Pop    eBp
            Ret
f           Endp		 f     Proc   Near C, A : near ptr byte
      Push   eSi
      Mov   eSi, A
      Mov   [eSi+3], 'X'        ; A[3] = 'X'
      Pop    eSi
      Ret
f     Endp
     
    C++ Integer Array Passing and Use 
    int Array[5];

    f(Array);

     

    		             Array  dd    5 dup(?)          ;; 32-bit or 4 bytes

                Push Offset Array               ;; Array Reference 
                Call f
                Add  eSp, 4

    		            Array  dd    5 dup(?)       ;; 32-bit or 4 bytes

                invoke f, addr Array
    void f( int A[] ) {
        A[3] = 1234;
    }
     
     
     

     

    		   f         Proc   Near
                Push   eBp
                Mov   eBp, eSp
                Push   eSi
                Mov   eSi, [eBp+8]
                Mov   [eSi+3*4], 1234       ; A[3] = 1234
                Pop    eSi
                Pop    eBp
                Ret
     f          Endp    		   f         Proc   Near C, A : near ptr dword
                Push   eSi
                Mov   eSi, A
                Mov   [eSi+3*4], 1234       ; A[3] = 1234
                Pop    eSi
                Ret
     f          Endp

32 bit Integer Arrays

C++ for 32 bit machines and operating systems such as the Intel Pentium on Windows or NT, Unix, etc. would typically represent integers as 32 bits and would also arrays of integers. The following illustrates the memory representation of an integer array x for either C++ or Assembler. Note that the above example of passing integer arrays uses a 32 bit array also.
32 Bit Integer Array (Note Assembler definition of array x)

Assignment

The homework consists of two parts. Part 1 is to implement several string functions in Assembler that are called by a C++ test program. Part 2 is to use these same string functions in an Internet TicTacToe server program.

The minimum points to be completed is 55, additional work up to 70 points will be extra credit. The point value of each function is listed below in the C++ test program.

  1. The C++ and Assembler Test.Cpp program currently works. The steps to compiling and assembling the test program is given below. Start by following those steps to verify that you can get the basics to work correctly.
  2. 30 to 45 points - Translate the C++ functions into Assembler one at a time. The lower the point value the easier the function should be to write. Generally you will need to do the following for each function.
  3. 10 points - An Internet TicTacToe server that uses the string functions is given in C++. The steps to compiling and assembling the TicTacToe program is given below. Start by following those steps that verify that you can get the basic server to work correctly. Then replace the C++ functions with the Assembler functions that you have written. Verify that it still works the same.
  4. Extra points - Translate other functions or improve the endgame function to check for ties, etc. The server plays a very weak game, moving randomly to any open position, add a function that implements a more successful game playing strategy.

Turn in

  1. Cover page  - Your name, date, and Homework 8. Staple all papers together.
  2. Assembler Program - All functions you've written. Source listing rather than assembler output listing.
  3. Final C++ Test.Cpp program listing.
  4. Final Test.Cpp execution output screen.
  5. Final TicTacToe.Cpp program listing.
  6. Final TicTacToe.Cpp execution output screen (black screen).
  7. Final browser output screen of TicTacToe game.
  8. Fileview of TicTacToe project in Visual C++.

How to do the Homework

Download the software
  1. Download the self expanding file Hw8.exe to your computer.
  2. From DOS, change directory to where Hw8.exe was downloaded and enter Hw8. Or from Windows Explorer, click on the icon .
Compiling, Linking and Execution
A Visual C++ project containing two files, Test.Cpp and STRrev.Asm are in HW8\Test directory. These serve as the starting point for the assignment.
  1. A Visual C++ project file name Test.dsw is located in the HW8\Test directory. In Windows Explorer, click on the icon . Note that Visual Studio .NET will need to convert the VC++ 6.0 Test.dsp file.
  2. Compile and link Test.Cpp and STRrev.obj, enter: Build | Rebuild
  3. Execute
Doing the Assignment
The assignment requires converting some of the C++ functions into Assembler. Examine the Test.Cpp and STRrev.Asm files listed below for an example of using C++ and Assembler together.

The steps below are for adding the STRreverse function to the Test project. Other functions, such as STRlen, etc. would be added similarly. Once the Assembler function is written, it must be assembled, and added to the Test project as described below.

  1. Create a file named  STRrev.Asm in notepad or other text editor.
  2. Copy the assembler listing below and paste into the file named STRrev.Asm. Save the file.
  3. Open a DOS window and change to the directory where the HW8 files are located, such as: cd c:\C335\Hw8
  4. Assemble the STRrev.asm  file by:
      5.  
      ml /coff /c /Zi /Cp STRrev.asm      The /Cp is necessary because C++ is case sensitive, /Cp preserves case.
  5. OBJ: add the STRrev.obj file to the project:
  6. Compile and link Test.Cpp and STRrev.obj, enter: Build | Rebuild
  7. Execute
Adding a function STRlen.
Stopping
Debugging Turn In
C++ and Assembler files for Homework 8 
;;  STRrev.Asm
;;       extern "C" void STRreverse( char s1[], char s2[]);                       
;;       Returns           - s2 the reversal of s1 (s1 and s2 must not be the same)
;;       Registers Altered - eAx, Flags                             
.386
.model flat, C
option casemap :none		 ;; Case sensitive

    STRlen	proto	near C, s : near ptr byte

.code				  ;; void STRreverse(char s1[], char s2[]){
STRreverse Proc  Near C, s1 : near ptr byte, s2 : near ptr byte  
           Push      eSi          ;;     ________
           Push      eDi          ;;	|addr s2 | eBp+12     
 				  ;;	|addr s1 | eBp+8
           Push      s1		  ;;	|ret addr| eBp+4
           Call      STRlen	  ;;	|old eBp | eBp+0
           Add       eSp, 4       ;;	|old eSi |			    
                                  ;;    |old eDi |
           Mov       eDi, s2      ;;    |________|
           Mov       eSi, s1      ;;      char *eSi=s1+STRlen(s1)-1;
           Add       eSi, eAx     ;;      char *eDi=s2;
           Dec       eSi          ;;      int eCx=STRlen(s1);
                                  ;;      char Al;
           Mov       eCx, eAx     ;;      do {            
                                  ;;            Al = *eSi--;
@@do:      Std                    ;;            *eDi++ = Al;
           LodsB                  ;;      } while (--eCx != 0);
           Cld			  ;; }
           StosB
           Loop      @@do
@@endwhile:
           Pop       eDi
	   Pop	     eSi            
           Ret                      
STRreverse Endp 
           End
 
// Test.Cpp
       #include <iostream.h>

       extern "C" void STRreverse(char s[], char d[]);     // Assembly function

       // 15 points
       //   Returns length of string s.
       //   STRlen("abc"); returns 3
       extern "C" int STRlen(char s[]) {
          int c = 0;
          while(*s++ != '\0') c++;
          return c;
       }

       // 30 points
       //   Returns index of pattern p in string s or -1 if not found.
       //   STRindex("456", "01234567"); returns 4
       extern "C" int STRindex( char p[], char s[]) {
           int pl = STRlen(p), sl = STRlen(s);
           int pi = 0, si = 0, last=0;
           do {
               if(p[pi] == s[si]) {
                   pi++;
                   si++;
               }
               else {   pi = 0;
                        last++;
                        si = last;
               }
           } while (pi < pl && si < sl);
           if (pi == pl)
              return si-pl;
           else
              return -1;
       }

       // 15 points
       //   Copies string s1 to string s2, assumes STRlen(s1) <= STRlen(s2);
       //   STRcpy(s1, s2); copies s1 to s2
       extern "C" void STRcpy(char s1[], char s2[]) {
          int i1=0, i2=0;
          while( s1[i1] != '\0') s2[i2++] = s1[i1++];
          s2[i2] = '\0';
       }

       // 15 points
       //   Tests if all 9 positions of TicTacToe board are occupied
       //   endgame("xoxoxoxox"); returns 1
       //   endgame("xoxoxoxo8"); returns 0
       extern "C" int endgame(char board[]) {
           for (int i=0; i<=8; i++) 
               if (board[i]==(char)(i+'0'))
                  return 0;
           return 1;
       }

       extern "C" void INTout(int i) {
          cout << i;
       }

       extern "C" void STRout(char s[]) {
          cout << s;
       }

       void main(void) {
            char newgame[] = "012345678";
            char tiegame[] = "xoxoxoxox";
            char dest[10];

            STRcpy(newgame, dest);
            cout << "STRcpy " << dest << "\n";

            STRreverse(newgame, dest);
            cout << "STRreverse " << dest << "\n";
         
            cout << "STRlen " << STRlen(newgame) << "\n";

            cout << "endgame " << endgame(newgame) << "\n";

            cout << "endgame " << endgame(tiegame) << "\n";

            cout << "STRindex " << STRindex("456", "01234567");

            STRout("\n\n");
       }

Internet TicTacToe Server

An Internet server program that plays a game of TicTacToe uses the string functions you have implemented. The server should run on any Windows 95, 98, NT, ME, W2K, XP workstation that has TCP/IP networking installed (if you can connect to the Internet your machine should work). The string functions that you have already written and tested can be used by the server by linking the functions to the server as described below.

When running, the TicTacToe server appears to a browser like a Web server except the server only will play TicTacToe. A game in progress appears as below on a Netscape broswer. You would be playing X and making the move to position 6 to win the game.

TicTacToe Server Overview

The TicTacToe server appears to a browser (IE, Netscape, etc.) just like any other Web server, except the server is limited to playing TicTacToe. The browser's purpose is to send a URL to a Web server, the URL indicates the name of an HTML (Hypertext Markup Language) file that the Web server should send back., the browser renders or displays the HTML into something we can read. The browser then sends the server a file name, gets back HTML from the server, and displays the HTML so people can read it.

The TicTacToe server is a little different in that it doesn't expect file names from the browser but instead expects a string that encodes the TicTacToe board and the next move. In the illustration above, the browser sends http://localhost/?move=1&board=x12xo567o for a move to position 1 on a board that has x's in position 0 and 3, and o's in positions 4 and 8. The TicTacToe server reads what the browser sends, placing the x move in position 1, picking o's move to 5. The server input from the browser and  HTML output sent back to the browser is below:
 

Browser and TicTacToe Server Interaction and Output 




Server Input

GET /?move=2&board=xx2xoo67o HTTP/1.0
Referer: http://localhost/?move=1&board=x12xo567o
Connection: Keep-Alive
User-Agent: Mozilla/4.7 [en] (Win98; I)
Host: localhost
Accept: image/gif, image/x-xbitmap, image/jpeg, image/pjpeg, image/png, */*
Accept-Encoding: gzip
Accept-Language: en
Accept-Charset: iso-8859-1,*,utf-8





Server Output

<b>TicTacToe
</b><br>Enter Move X.<pre><form action="" method="GET">
        <input type="text" name="move" size=2>

<br>x|x|2
<br>_|_|_
<br>x|o|o
<br>_|_|_
<br>6|7|o
<br></pre>
<input type="hidden" name="board" value="xx2xoo67o"></form>

Ctrl C to stop server









TicTacToe Compiling, Linking and Execution

The server is currently written entirely in C++ . To test that it is working
without your assembly functions do the following steps.

    

  1. 
A Visual C++ project file name TicTacToe.dsw is located in the HW8\TicTacToe
directory. In Windows Explorer, click on the icon .
Note that Visual Studio .NET will need to translate the VC++ 6.0 Test.dsp file.
    2. 


  2. 
Compile and link TicTacToe.Cpp, enter:
Build |
Rebuild
    3. 


  3. 
Execute
    4. 









Doing the Assignment

    



Turn In



Document last modified: