Friday, January 25, 2008

[Programming] Quick guide for network programming (2)

Source code for Server's socket:


#include <winsock2.h>
#include <stdio.h>

void main()
{
WORD wVersionRequested;
WSADATA wsaData;
int err;

wVersionRequested = MAKEWORD( 1, 1 );
// call WSAStartup, initialize winsock.dll and negotiate the socket version
err = WSAStartup( wVersionRequested, &wsaData );
if ( err != 0 ) {
// Tell the user that we could not find a usable WinSock DLL.
return;
}


if ( LOBYTE( wsaData.wVersion ) != 1 ||
HIBYTE( wsaData.wVersion ) != 1 ) {
// Tell the user that we could not find a usable WinSock DLL.
WSACleanup( );
return;
}

// a) create a socket
SOCKET sockSrv = socket(AF_INET, SOCK_STREAM, 0);
// b) bind
SOCKADDR_IN addrSrv;
addrSrv.sin_addr.S_un.S_addr = htonl(INADDR_ANY); // INADDR_ANY use any IP address of the host, you can use inet_addr("127.0.0.1"); to designate a specific IP
addrSrv.sin_family = AF_INET;
addrSrv.sin_port = htons(6123); // use a port number larger than 1024
bind(sockSrv, (SOCKADDR *)&addrSrv, sizeof(SOCKADDR));
// c) listen
listen(sockSrv, 5);
// d) accept
SOCKADDR_IN addrClient;
int len = sizeof(SOCKADDR);
while(1) // waiting for requests from clients
{
SOCKET sockConn = accept(sockSrv, (SOCKADDR *)&addrClient, &len); // create a new socket for this connection
// e) send/recv
char sendBuff[100];
sprintf(sendBuff, "Welcome %s to server", inet_ntoa(addrClient.sin_addr));
send(sockConn, sendBuff, strlen(sendBuff)+1, 0);

char recvBuff[100];
recv(sockConn, recvBuff, 100, 0);
printf("%s\n", recvBuff);
// f) close the current socket and wait for another request
closesocket(sockConn); //release the socket for this connection
}

}



Source code for Client's Socket programming:


#include <winsock2.h>
#include <stdio.h>

void main()
{
WORD wVersionRequested;
WSADATA wsaData;
int err;

wVersionRequested = MAKEWORD( 1, 1 );
// call WSAStartup, initialize winsock.dll and negotiate the socket version
err = WSAStartup( wVersionRequested, &wsaData );
if ( err != 0 ) {
// Tell the user that we could not find a usable WinSock DLL.
return;
}


if ( LOBYTE( wsaData.wVersion ) != 1 ||
HIBYTE( wsaData.wVersion ) != 1 ) {
// Tell the user that we could not find a usable WinSock DLL.
WSACleanup( );
return;
}
// a) create a socket
SOCKET sockClient = socket(AF_INET, SOCK_STREAM, 0);
// b) connect
SOCKADDR_IN addrClient;
addrClient.sin_addr.S_un.S_addr = inet_addr("127.0.0.1"); // loopback address
addrClient.sin_family = AF_INET;
addrClient.sin_port = htons(6123);
connect(sockClient, (SOCKADDR *)&addrClient, sizeof(SOCKADDR));
// c) send/recv
char recvBuff[100];
recv(sockClient, recvBuff, 100, 0);
printf("%s\n", recvBuff);
send(sockClient, "This is from client B", strlen("This is from client B")+1, 0);

// d) close
closesocket(sockClient);
WSACleanup();
}

[Programming] Quick guide for network programming (1)



When we talk about network programming, basically it includes two parts: one is the socket programming, another one is the multi-threaded programming.


I'll give a step-by-step guidance for network programming in my blog. We'll first talk about socket programming, then go to the multi-threaded programming. I'll use the windows system as a demonstration. A TCP server will be first started up, then a TCP cilent will communicate with the server from the loopback IP address 127.0.0.1 with port number 6123. (I suppose you have already known the fundamental of network protocols, such as TCP/UDP, IP, port number etc.)

1) What is socket?
Shortly put, a socket is a combination of an IP address and a port number of a two-way communication link between two programs on the network.

2) Types of sockets:
For old version of socket, it provides two types of sockets:
"Stream Socket": provide connection-oriented, reliable data transmission service, use TCP protocol
"Datagram Socket": provide connetionless service, packets may not be received in order, use UDP protocol

Now some new types of sockets have been added, such as: SOCK_RDM (Reliable message datagram), SOCK_SEQPACKET(pseudo-stream packet based on datagrams)

3) Flow of the stream socket communication

On the server side, there are seven steps:
a) create a socket (socket)
b) bind the socket with a local IP address and a port (bind)
c) set socket to 'listen' mode (listen)
d) wait for client's request, when it arrives, accept the request and return
a new socket for the connection (accept)
e) communicate with client using the new returned socket (send/recv)
f) return, wait for another client's request
g) close the socket (close)

On the client side, there are four steps:
a) create a socket (socket)
b) send request to the server ((connect))
c) communicate with server (send/recv)
d) close the socket (close)

4) Step-by-step programming

Follow the steps in 3), we first write the code for a TCP server. We use visual c++. You can find the source codes in the next post. Here is the explanation of the code. It's better to read the code and the following descriptions simultaneously.

<1> create a Win32 Console Application, set project name to TCPServer

<2> write a main function

<3> initialize the win32 socket DLL, call function WSAStartup();

int WSAStartup(
WORD wVersionRequested,
LPWSADATA lpWSAData
);
WSAStartup has two jobs to do:
i) initiates use of Ws2_32.dll: if WinSock.dll or lower network subsystem is not initialized correctly or is not found, will return WSASYSNOTREADY.
ii) negotiate the socket version:
if requested version < MAX version supported by the WinSock.dll, use min(requested version, MAX version)
if requested version < MIN version supported by the WinSock.dll, return WSAVERNOTSUPPORTED, then call function WSACleanUP() to release resource that has been allocated for WSAStartup

The WSADATA or *LPWSADATA used in WSAStartup is a structure, it's defined as
typedef struct WSAData
{
WORD wVersion; // winsock version
WORD wHighVersion; // highest version in the current winsock library
char szDescription[WSADESCRIPTION_LEN+1];// for special use
char szSystemStatus[WSASYS_STATUS_LEN+1];// for special use
unsigned short iMaxSockets; // maximum num of sockets that can be
// opened, don't use it
unsighed short iMaxUdpDg; // maximum length of packet, don't use it
char FAR * lpVendorInfo; // reserved for vendor, never been used
} WSADATA, *LPWSADATA;


<4> create a socket

SOCKET WSAAPI socket(
int af, // for tcp-ip, it must be AF_INET or PF_INET
int type, // for winsock 1.1, only SOCKET_STREAM or SOCKET_DGRAM
int protocol // protocol to be used, is specific to the address family and
// socket type, set to 0 for default
);

If no error occurs, it will return a descriptor referencing the new socket. Otherwise, return INVALID_SOCKET.

<5> bind

int bind(
SOCKET s, // descriptor identifying an unbound socket
const struct sockaddr* name, // the address to assign to the socket,
// it may be varied with different
// address families, so we should use the next
// parameter to indicate the
// length of this address structure
int namelen // length of the value, in bytes
);


The sockaddr is defined as:
struct sockaddr {
u_short sa_family;
char sa_data[14];
};

For different address family, we should use differnt structure to replace this sockaddr.
For TCP/IP, sockaddr_in is used.
The definition of sockaddr_in is:

struct sockaddr_in {
short sin_family; // for IP address, it's AF_INET
u_short sin_port; // port number
struct in_addr sin_addr; // IP address of the host,
// should use "network byte order"
char sin_zero[8]; // padding bytes, to make the length equals to the
// sockaddr structure
};
where the "network byte order" is the same as the well-known big_endian order.

It will return 0, if successful; otherwise, return SOCKET_ERROR

<6> listen

int listen(
SOCKET s, // descriptor identifying a socket
int backlog // max length of the queue of pending connections
);

<7> accept

SOCKET accept(
SOCKET s, // identifying a socket
struct sockaddr* addr, // used to store the client's ip addr and port num
int* addrlen // length of the
);

<8> send/recv
int send(
SOCKET s,
const char* buf,
int len,
int flags
);

<9> Include the header file , add ws2_32.lib to the project, the operation in Visual C++ is:
project -> setting -> link -> Object/library modules, append ws2_32.lib to the end


<10> Then let's go to the client side. First add a new project to the current workspace, name it as "TCPClient".

<11> Similar as the Server code, first call WSAStartup to initialize the ws2_32.dll and negotiate the socket version, then create a socket

<12> connect

int connect(
SOCKET s,
const struct sockaddr* name,
int namelen
);

<13> After connect, call function send/recv, and finnaly call closesocket and WSACleanup as in server side.

<14> Include the header file and add ws2_32.lib to this project too

<15> Compile all files, run TCPServer first, then run TCPClient, we will get the following results, as shown in the figure

5) Some functions are used in the program for the conversion of the address, they are
htons(): converts a u_short from host to TCP/IP network byte order
htonl(): converts a u_long from host to TCP/IP network byte order
ntohs(): converts a u_short from TCP/IP network byte order to host byte order
ntohl(): converts a u_long from TCP/IP network byte order to host byte order
inet_ntoa(): converts an (Ipv4) Internet network address into a string in Internet standard dotted-decimal format
inet_addr(): converts a string containing an (Ipv4) Internet Protocol dotted address into a proper address for the IN_ADDR structure


Thursday, January 24, 2008

[Algorithm] Reverse words in a string

This is an interview problem. Given a string, such as "tell me something", output the string as "something me tell", i.e. reverse every word in the string. Here is a demo program in C code, it's easy to understand with the comments given in the code. The basic idea is, scan the string from the end, find the beginning and the end of each word, then write to a temporary buffer.





#include <iostream.h>
#include <stdlib.h>
#include <string.h>

void ReserveWordsInString(char string1[])
{
// get the length of the input string
int length=0;
while (string1[length]!='\0')
length++;
// allocate memory space for a temporary buffer, used to store the temporary result
char *buffer= (char *)malloc(length+1);

// declare four indicators
// MoveInd: from length to 0, used to traverse the input string
// EndInd: indicate the end of a word that is to be reversed in the input string
// BeginInd: indicate the begin of the word that is to be reversed in the input string
// WriteInd: the indicator of the writing position in the temporary buffer
int MoveInd, BeginInd, EndInd, WriteInd;
// initialize the MoveInd to the end of the input string, WriteInd to the begin of the temporary buffer
MoveInd = length-1;
WriteInd = 0;

while (MoveInd>=0)
{
if (string1[MoveInd]!=' ') // if it's a word charactor
{
EndInd=MoveInd;
// scan the current word, find the next non-word charactor
while(MoveInd>=0 && string1[MoveInd]!=' ')
{
MoveInd--;
}
// copy the word to the temporary buffer
for (BeginInd=MoveInd+1; BeginInd <= EndInd; BeginInd++, WriteInd++)
{
buffer[WriteInd]=string1[BeginInd];
}

}
else
{
// write the non-word charactor directly to the temporary buffer
buffer[WriteInd++]=string1[MoveInd--];
}
}
// it is better to append \0 to the end of the buffer
buffer[length]='\0';

// copy the buffer to the input string for output
for (int i=0; i<length; i++)
string1[i]=buffer[i];

// free the allocated memory for the buffer
free(buffer);
}
void main()
{
char string1[]="This is a C program, for word reverse.";
// this is a tricky method in getting the size of an array, explanation is below the code
int length = sizeof(string1)/sizeof(string1[0]);

// Call the function
ReserveWordsInString(string1);

// output the result
for (int i=0; i<length; i++)
{
cout<<string1[i];
}
cout<<endl;
}





Notes: In this program, we encountered a problem, how to get the length of an array or a string?

A well-known and tricky method is to use "sizeof(array)/sizeof(array[0]);", this works in the main program. However, if the array is the input argument of a function, this one doesn't work. Because in this case, the type of the array identifier "decays" into a pointer to the base type, and its value is set to the address of the first element in the array.
So, my opinion is, always traversing the array from the beginning to the end to get the length, like "for(int i=0; array[i]!='\0'; i++)".

A more decent algorithm is: first reverse the whole string in characters, e.g. reverse "tell me something" to "gnihtemos em llet", then using the similar method as above to locate the beginning and end of each word, then reverse each word in characters, e.g. reverse "gnihtemos" to "something". This is an in-place method, which avoids using the extra temporaray buffer.