zzun.net zzun's blog since 2001

[info.]
2004 여름 / 네트워크 프로그래밍(경북대) / 고석주 교수님
using : C / Linux / TCP/IP / Multi-threads / thread-synchronization(mutex)


[Makefile]
all : zchat_serv zchat_clnt

zchat_serv : zchat_serv.c zchat.h
       gcc -o zchat_serv zchat_serv.c -D_REENTRANT -lpthread

zchat_clnt : zchat_clnt.c zchat.h
       gcc -o zchat_clnt zchat_clnt.c -D_REENTRANT -lpthread


[zchat.h]
/**

Z-Chat Header File

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>
#include <sys/socket.h>
#include <arpa/inet.h>
#include <pthread.h>
#include <string.h>

#define BUFSIZE 100
#define IDSIZE 20
#define CLNT_LIMIT 10


[zchat_serv.c]
/**

Z-Chat SERVER

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include "zchat.h"

struct clnt_info
{
       int sock;
       char* id;
};

int clnt_count = 0;
struct clnt_info* clients[CLNT_LIMIT];
pthread_mutex_t mutx;

void error_handler( char* msg )
{
       fputs( msg, stderr );
       fputc( '\n', stderr );
       exit(1);
}

void sendtoall_ex( char* msg, int sender, int len )                // send to all except sender
{
       int i;
       char id_msg[BUFSIZE+IDSIZE+3];
       
       pthread_mutex_lock( &mutx );
       for ( i=0; i<clnt_count; i++ )
               if ( clients[i]->sock == sender )
               {
                       sprintf( id_msg, "[%s] %s", clients[i]->id, msg );        // attach sender's id
                       len += strlen(clients[i]->id) + 3;
                       break;
               }
       for ( i=0; i<clnt_count; i++ )
               if ( clients[i]->sock != sender )
                       write( clients[i]->sock, id_msg, len );
       pthread_mutex_unlock( &mutx );
}

void sendtoone( char* msg, int sender, int len )        // usage : /id msg
{
       int i, target_sock, id_len;
       char id_msg[BUFSIZE+IDSIZE+15];
       char target_id[IDSIZE];

       id_len = strchr(msg, ' ') - msg - 1;
       strncpy( target_id, msg+1, id_len );
       target_id[id_len] = 0;
       msg = msg + id_len + 2;                // detach target id

       pthread_mutex_lock( &mutx );
       for ( i=0; i<clnt_count; i++ )
       {
               if ( clients[i]->sock == sender )        // attach sender's id
               {
                       sprintf( id_msg, "[Secret from:%s] %s", clients[i]->id, msg );
                       len += strlen(clients[i]->id) + 15;
               }
               if ( !strcmp(target_id, clients[i]->id) )
                       target_sock = clients[i]->sock;
       }        
       pthread_mutex_unlock( &mutx );

       write( target_sock, id_msg, len );
}

void* clnt_msg_process(void* arg)
{
       int clnt_sock = (int) arg;
       char msg[BUFSIZE];
       int i, len;

       while ( (len=read(clnt_sock, msg, sizeof(msg))) != 0 )
       {
               if ( msg[0] == '/' )
                       sendtoone( msg, clnt_sock, len );        // whisper
               else
                       sendtoall_ex( msg, clnt_sock, len );
       }

       pthread_mutex_lock( &mutx );
       for ( i=0; i<clnt_count; i++)
               if ( clnt_sock == clients[i]->sock )
               {
                       printf( "%s's connection closed.\n", clients[i]->id );
                       free( clients[i]->id );
                       free( clients[i] );
                       for ( ; i<clnt_count-1; i++)
                               clients[i] = clients[i+1];                        
                       break;
               }
       clnt_count--;
       pthread_mutex_unlock( &mutx );        

       close( clnt_sock );
       return 0;
}

int main( int argc, char** argv )
{
       int serv_sock, clnt_sock;
       struct sockaddr_in serv_addr;
       struct sockaddr_in clnt_addr;
       int clnt_addr_size;
       pthread_t thread;

       if ( argc != 2 )
       {
               printf( "Usage : %s <port>\n", argv[0] );
               exit(1);
       }

       if ( pthread_mutex_init(&mutx, NULL) )
               error_handler( "pthread_mutex_init() error" );

       serv_sock = socket( PF_INET, SOCK_STREAM, 0 );

       memset( &serv_addr, 0, sizeof(serv_addr) );
       serv_addr.sin_family = AF_INET;
       serv_addr.sin_addr.s_addr = htonl( INADDR_ANY );
       serv_addr.sin_port = htons( atoi(argv[1]) );

       if ( bind(serv_sock, (struct sockaddr*) &serv_addr, sizeof(serv_addr)) )
               error_handler( "bind() error" );

       if ( listen(serv_sock, CLNT_LIMIT) )
               error_handler( "listen() error" );

       while (1)
       {
               clnt_addr_size = sizeof(clnt_addr);
               clnt_sock = accept( serv_sock, (struct sockaddr*) &clnt_addr, &clnt_addr_size );

               pthread_mutex_lock( &mutx );
               clients[clnt_count] = (struct clnt_info*) malloc( sizeof(struct clnt_info) );
               clients[clnt_count]->id = (char*) malloc( IDSIZE );
               clients[clnt_count]->sock = clnt_sock;
               read( clnt_sock, clients[clnt_count++]->id, IDSIZE );        // recv clnt's id
               pthread_mutex_unlock( &mutx );

               pthread_create( &thread, NULL, clnt_msg_process, (void*)clnt_sock );
               printf( "new client connected : %s\n", clients[clnt_count-1]->id );
       }

       return 0;
}


[zchat_clnt.c]
/**

Z-Chat CLIENT

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include "zchat.h"

void error_handler( char* err_msg )
{
       fputs( err_msg, stderr );
       fputc( '\n', stderr );
       exit(1);
}

void* send_msg( void* arg )
{
       char msg[BUFSIZE];

       int sock = (int) arg;        
       while (1)
       {
               fgets( msg, BUFSIZE, stdin );
               if ( !strcmp(msg, "q\n") )
               {
                       close( sock );
                       exit(0);
               }
               write( sock, msg, strlen(msg) );
       }
}

void* recv_msg( void* arg )
{
       int sock = (int) arg;
       char recieved[BUFSIZE+IDSIZE+15];
       int len;

       while (1)
       {
               len = read( sock, recieved, BUFSIZE+IDSIZE+14 );
               if ( len == -1 )
                       return (void*)1;
               recieved[len] = 0;
               fputs( recieved, stdout );
       }
}

int main( int argc, char** argv )
{
       int sock;
       struct sockaddr_in serv_addr;
       pthread_t send_thrd, recv_thrd;
       void* thr_rtn_val;
       char id[IDSIZE];

       if ( argc != 4 )
       {
               printf( "Usage : %s <IP> <port> <ID>\n", argv[0] );
               exit(1);
       }

       sprintf( id, "%s", argv[3] );

       sock = socket( PF_INET, SOCK_STREAM, 0 );
       if ( sock == -1 )
               error_handler( "socket() error" );

       memset( &serv_addr, 0, sizeof(serv_addr) );
       serv_addr.sin_family = AF_INET;
       serv_addr.sin_addr.s_addr = inet_addr( argv[1] );
       serv_addr.sin_port = htons( atoi(argv[2]) );

       if ( connect(sock, (struct sockaddr*) &serv_addr, sizeof(serv_addr)) == -1 )
               error_handler( "connect() error" );

       write( sock, id, sizeof(id) );        // send my id

       pthread_create( &send_thrd, NULL, send_msg, (void*) sock );
       pthread_create( &recv_thrd, NULL, recv_msg, (void*) sock );

       pthread_join( send_thrd, &thr_rtn_val );
       pthread_join( recv_thrd, &thr_rtn_val );        // wait until threads die

       close( sock );
       return 0;
}

[info.]
2004 Summer / 네트워크 프로그래밍(경북대) / 고석주 교수님

[rspgame_serv.c]
/**

RSP game SERVER

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>
#include <time.h>
#include <signal.h>
#include <sys/wait.h>
#include <sys/socket.h>
#include <arpa/inet.h>

#define BUFSIZE 5

void err_handler( char* msg )
{
       fputs( msg, stderr );
       exit(1);
}

void z_handler( int sig )        // zombie child process handler
{
       int rtn;
       waitpid( -1, &rtn, WNOHANG );
}

int who_win( int a, int b )                // determine who win
{
       if ( a>2 || b>2 || a<0 || b<0 )
               return -2;
       else if ( a == b)
               return 0;
       else if ( a == (b+1)%3 )
               return 1;
       else
               return -1;
}

int main( int argc, char** argv )
{
       char buffer[BUFSIZE];
       int serv_sock, clnt_sock;
       struct sockaddr_in serv_addr;
       struct sockaddr_in clnt_addr;
       struct sigaction act;
       int str_len, clnt_addr_size, serv_card, result;
       pid_t pid;
       char* RSP[3];
       char* result_print[3];

       result_print[0] = "Win!\n";
       result_print[1] = "Draw! Regame!\n";
       result_print[2] = "Lose!\n";
       RSP[0] = "Rocks";
       RSP[1] = "Scissors";
       RSP[2] = "Papers";

       if ( argc != 2 )
       {
               printf( "Usage : %s <port>\n", argv[0] );
               exit(1);
       }

       act.sa_handler = z_handler;
       sigemptyset( &act.sa_mask );
       act.sa_flags = 0;                // for sigaction()

       if ( sigaction(SIGCHLD, &act, 0) )        // when child dies
               err_handler( "sigaction() error\n" );

       serv_sock = socket( PF_INET, SOCK_STREAM, 0 );
       if ( serv_sock == -1 )
               err_handler( "socket() error\n" );

       memset( &serv_addr, 0, sizeof(serv_addr) );
       serv_addr.sin_family = AF_INET;
       serv_addr.sin_addr.s_addr = htonl( INADDR_ANY );
       serv_addr.sin_port = htons( atoi(argv[1]) );

       if ( bind(serv_sock, (struct sockaddr*) &serv_addr, sizeof(serv_addr)) )
               err_handler( "bind() error\n" );
       if ( listen(serv_sock, 5) )
               err_handler( "listen() error\n" );
       
       while (1)
       {
               clnt_addr_size = sizeof( clnt_addr );
               clnt_sock = accept( serv_sock, (struct sockaddr*) &clnt_addr, &clnt_addr_size );
               if ( clnt_sock == -1 )
                       continue;

               pid = fork();

               switch ( pid )
               {
               case -1 :
                       printf("fork() error : client %s\n", inet_ntoa(clnt_addr.sin_addr) );
                       close( clnt_sock );
                       continue;

               case 0 :        // child
                       close( serv_sock );
                       
                       do
                       {
                               srand((unsigned) time(NULL));
                               serv_card = rand() % 3;
                               printf( "Randomly generated number : %d (%s)\n", serv_card, RSP[serv_card] );
                               read( clnt_sock, buffer, BUFSIZE );                // get client's card

                               result = who_win( serv_card, atoi(buffer) );
                               if ( result == -2 )
                                       err_handler( "client input error" );

                               buffer[0] = '1' + result;
                               buffer[1] = 0;
                               printf( "Game with %s : ", inet_ntoa(clnt_addr.sin_addr) );
                               printf( result_print[result+1] );        // print out the result
                               write( clnt_sock, buffer, 1 );
                       } while ( result == 0 );        // tied! try again

                       printf("connection to %s closed.\n", inet_ntoa(clnt_addr.sin_addr) );
                       close( clnt_sock );
                       exit(0);

               default :        // parent
                       printf("connected to %s\n", inet_ntoa(clnt_addr.sin_addr) );
                       close( clnt_sock );
                       continue;
               }
       }

       return 0;
}







[rspgame_clnt.c]
/**

RSP game CLIENT

zzun
hello82@unitel.co.kr
http://zzun.net

**/

#include <stdio.h>
#include <string.h>
#include <sys/socket.h>
#include <arpa/inet.h>

#define BUFSIZE 10

void err_handler( char* msg )
{
       fputs( msg, stderr );
       exit(1);
}

int main( int argc, char** argv )
{
       int sock, str_len, clnt_card, result;
       struct sockaddr_in serv_addr;
       char buffer[BUFSIZE];
       char* result_print[3];
       char input_msg[] = "input your card (0:Rocks, 1:Scissors, 2:Papers) : ";

       result_print[0] = "You Lose!\n";
       result_print[1] = "Draw! Regame!\n";
       result_print[2] = "You Win!\n";

       if ( argc != 3 )
       {
               printf( "Usage : %s <IP> <port>\n", argv[0] );
               exit(1);
       }

       sock = socket( PF_INET, SOCK_STREAM, 0 );

       memset( &serv_addr, 0, sizeof(serv_addr) );
       serv_addr.sin_family = AF_INET;
       serv_addr.sin_addr.s_addr = inet_addr( argv[1] );
       serv_addr.sin_port = htons( atoi(argv[2]) );

       if ( connect(sock, (struct sockaddr*) &serv_addr, sizeof(serv_addr)) == -1 )
               err_handler( "connect() error\n" );

       printf( "connected.\n" );

       do
       {
               do
               {
                       write( 1, input_msg, strlen(input_msg) );        
                       str_len = read( 0, buffer, BUFSIZE );
                       clnt_card = atoi( buffer );
               } while ( clnt_card<0 || clnt_card>2 );                // input correctness check

               write( sock, buffer, str_len );
               read( sock, buffer, BUFSIZE-1 );
               result = atoi( buffer );
               if ( result<0 || result>2)
                       err_handler( "result error\n" );
               else
                       printf( result_print[result] );                
       } while ( result == 1);

       close( sock );
       printf( "connection closed.\n" );

       return 0;
}

http://online-judge.uva.es/p/v4/453.html

/**

Intersecting Circles

zzun
http://zzun.net

**/

#include <fstream.h>
#include <math.h>
#include <stdio.h>

float pow2( float a )
{
       return pow( a, 2 );
}

int main()
{
       ifstream fin;
       float a[2], b[2], r[2], x[2], y[2], temp;

       fin.open( "test.in" );

       fin >> a[0] >> b[0] >> r[0] >> a[1] >> b[1] >> r[1];

       while ( ! fin.eof() )
       {
               float d = sqrt( pow2(a[0]-a[1]) + pow2(b[0]-b[1]) );        // distance

               if ( a[0]==a[1] && b[0]==b[1] && r[0]==r[1] )
                       printf( "THE CIRCLES ARE THE SAME\n" );

               else if ( d>r[0]+r[1] || d<fabs(r[0]-r[1]) )
                       printf( "NO INTERSECTION\n" );

               else if ( d == r[0]+r[1] )        // circumscription
               {
                       x[0] = ( r[0]*a[1] + r[1]*a[0] ) / ( r[0] + r[1] );
                       y[0] = ( r[0]*b[1] + r[1]*b[0] ) / ( r[0] + r[1] );
                       printf( "(%.3f,%.3f)\n", x[0], y[0] );
               }

               else if ( d == fabs(r[0]-r[1]) )        // inscription
               {
                       x[0] = ( r[0]*a[1] - r[1]*a[0] ) / ( r[0] - r[1] );
                       y[0] = ( r[0]*b[1] - r[1]*b[0] ) / ( r[0] - r[1] );
                       printf( "(%.3f,%.3f)\n", x[0], y[0] );
               }

               else if ( a[0] == a[1] )        // same a, diff b
               {
                       y[0] = ( (b[0]+b[1]) - (r[0]+r[1])*(r[0]-r[1])/(b[0]-b[1]) ) / 2;
                       temp = sqrt( (r[0]-y[0]+b[0])*(r[0]+y[0]-b[0]) );
                       printf( "(%.3f,%.3f)(%.3f,%.3f)\n", a[0]-temp, y[0], a[0]+temp, y[0] );
               }

               else if ( b[0] == b[1] )        // same b, diff a
               {
                       x[0] = ( (a[0]+a[1]) - (r[0]+r[1])*(r[0]-r[1])/(a[0]-a[1]) ) / 2;
                       temp = sqrt( (r[0]-x[0]+a[0])*(r[0]+x[0]-a[0]) );
                       printf( "(%.3f,%.3f)(%.3f,%.3f)\n", x[0], b[0]-temp, x[0], b[0]+temp );
               }

               else        // normal case
               {
                       float ef[3], A, B, C;

                       B = 2 * (b[1]-b[0]);
                       A = 2 * (a[1]-a[0]) / B;
                       C = ( (a[0]+a[1])*(a[0]-a[1]) + (b[0]+b[1])*(b[0]-b[1]) - (r[0]+r[1])*(r[0]-r[1]) ) / B;

                       ef[0] = 1 + pow2(A);
                       ef[1] = 2*b[0]*A - 2*a[0] + 2*A*C;
                       ef[2] = pow2(C) + 2*b[0]*C + pow2(a[0]) + pow2(b[0]) - pow2(r[0]);

                       temp = sqrt( pow2(ef[1]) - 4*ef[0]*ef[2] );        // b^2 - 4ac
                       x[0] = (temp*(-1) - ef[1]) / (2*ef[0]);
                       x[1] = (temp - ef[1]) / (2*ef[0]);

                       for (int i=0; i<2; i++)
                               y[i] = (-1)*C - A*x[i];

                       printf( "(%.3f,%.3f)(%.3f,%.3f)\n", x[0], y[0], x[1], y[1] );
               }

               fin >> a[0] >> b[0] >> r[0] >> a[1] >> b[1] >> r[1];
       }

       fin.close();

       return 0;
}


[test.in]
0.0 0.0 1.0
3.0 0.0 1.0
0.0 0.0 1.0
0.0 0.0 1.0
0.0 0.0 1.0
1.0 0.0 1.0
5.6 6.6 3.2
3.2 4.8 3.5
5.0 5.0 5.0
0.0 0.0 5.0
0.0 0.0 1.0
3.0 0.0 2.0
0.0 0.0 3.0
2.0 0.0 1.0
3.5 8.6 6.3
3.5 0.3 4.2
0.0 0.0 5.0
1.0 0.0 2.0



> time ./n04_circle
NO INTERSECTION
THE CIRCLES ARE THE SAME
(0.500,-0.866)(0.500,0.866)
(2.880,8.285)(6.456,3.517)
(0.000,5.000)(5.000,0.000)
(1.000,0.000)
(3.000,0.000)
(0.389,3.122)(6.611,3.122)
NO INTERSECTION
0.000u 0.000s 0:00.00 0.0%      0+0k 0+0io 164pf+0w

http://acm.uva.es/p/v1/143.html

/**
Orchard Trees
zzun
hello82@unitel.co.kr
http://zzun.net
**/

#include <iostream.h>
#include <fstream.h>

ifstream fin;

void swap(float& a, float& b)
{
       float temp = a; a = b; b = temp;
}

bool read_input(float* x, float* y)
{
       bool rtn = false;
       for (int i=0; i<3; i++)
       {
               fin >> x[i] >> y[i];
               if ( x[i] > 0 || y[i] > 0 )
                       rtn = true;
       }

       return rtn;
}

int main()
{
       fin.open("test.in");
       float* x = new float[3];
       float* y = new float[3];
       int cur_y, count, tx1, tx2;
       float a1, a2, cur_x1, cur_x2;
       bool turn;

       while ( read_input(x, y) )
       {
               if ( y[1] < y[0] && y[1] <= y[2] )
               {
                       swap( x[0], x[1] );
                       swap( y[0], y[1] );
               }
               else if ( y[2] < y[0] && y[2] < y[1] )
               {
                       swap( x[0], x[2] );
                       swap( y[0], y[2] );
               }        // for largest y

               count = 0;
               turn = false;
               cur_y = (int) y[0];

               a1 = (x[1]-x[0])/(y[1]-y[0]);
               a2 = (x[2]-x[0])/(y[2]-y[0]);

               if ( a1 > a2 ) // which is on left side
               {
                       swap( x[1], x[2] );
                       swap( y[1], y[2] );
                       swap( a1, a2 );
               }

               cur_x1 = x[0] + a1*((float)cur_y - y[0]);
               cur_x2 = x[0] + a2*((float)cur_y - y[0]);

               while ( 1 )
               {                        
                       cur_y++;

                       if ( !turn && cur_y > y[1] && cur_y <= y[2] ) // find turning point
                       {
                               a1 = (x[2]-x[1])/(y[2]-y[1]);
                               cur_x1 = x[1] + a1*((float)cur_y - y[1]);
                               cur_x2 += a2;
                               turn = true;
                       }
                       else if ( !turn && cur_y > y[2] && cur_y <= y[1] )
                       {
                               a2 = (x[1]-x[2])/(y[1]-y[2]);
                               cur_x2 = x[2] + a2*((float)cur_y - y[2]);
                               cur_x1 += a1;
                               turn = true;
                       }
                       else
                       {
                               cur_x1 += a1;
                               cur_x2 += a2;
                       }

                       if ( (cur_y<=y[1] || cur_y<=y[2]) && cur_y<100 )
                       {
                               tx1 = ( cur_x1-(int)cur_x1 == 0 ) ? (int)cur_x1 : (int)cur_x1+1;
                               tx1 = ( tx1 == 0 ) ? 1 : tx1;
                               tx2 = ( (int)cur_x2 == 100 ) ? 99 : (int)cur_x2; // no point at 0&100
                               count += tx2 - tx1 + 1;
                       }
                       else
                               break;
               }
               
               cout << count << endl;
       }

       fin.close();
}

[info]
http://acm.uva.es/p/v1/108.html
내림피아드 프로젝트의 첫번째 문제
O(N^3) 알고리즘

[test.in]
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2

[n01_zzun.cpp]
/**

Max-Sum Subrectangle Search

zzun
http://zzun.net
hello82@unitel.co.kr

**/

#include <iostream.h>
#include <fstream.h>
#include <stdio.h>
#include <stdlib.h>

int array_size;
char** num_array;

bool read_input(char* filename)
{
       ifstream fin;
       int buf;

       fin.open( filename );

       fin >> array_size;        // take the array size N
       if ( array_size <= 0 )
       {
               cout << "Error : array size!" << endl;
               return false;
       }

       num_array = new char*[array_size];
       for (int i=0; i<array_size; i++)
               num_array[i] = new char[array_size];        // 2-dim array M-allocate

       for (int i=0; i<array_size; i++)
               for (int j=0; j<array_size; j++)
               {
                       fin >> buf;
                       num_array[i][j] = (char) buf;        // take the values
               }
       
       fin.close();

       return true;
}

int main()
{
       char* input_filename;
       int** sum;
       int max = 1 << 31;
       int local_max, local_max_candi, temp;

       input_filename = "test.in";        

       if ( !read_input(input_filename) )
               return -1;

       sum = new int*[array_size+1];        // 2-dim array for SUM from [0,0] to [x,y]
       for (int i=0; i<array_size+1; i++)
       {
               sum[i] = new int[array_size+1];
               sum[i]++;        // move the pointer to use the -1 index
       }
       sum++;        // move higher pointer too, so we can use sum[-1 ~ array_size][-1 ~ array_size]

       for (int i=-1; i<array_size; i++)
       {
               sum[i][-1] = 0;
               sum[-1][i] = 0;        // init
       }

       for (int i=0; i<array_size*2-1; i++)
               for (int j=0; j<=i; j++)
                       if ( i-j < array_size && j < array_size )
                               sum[j][i-j] = num_array[j][i-j] + sum[j-1][i-j] + sum[j][i-j-1] - sum[j-1][i-j-1];        // calculate sum[][], O(N^2)

       for (int i=0; i<array_size; i++)
               for (int k=0; k<=i; k++)
               {
                       local_max = 1 << 31;
                       local_max_candi = 0;
                       for (int j=0; j<array_size; j++)
                       {
                               temp = sum[i][j] - sum[i][j-1] - sum[k-1][j] + sum[k-1][j-1];
                               local_max_candi += temp;
                               if ( temp > local_max && temp > local_max_candi )
                                       local_max = local_max_candi = temp;
                               else if ( local_max_candi > local_max )
                                       local_max = local_max_candi;
                               else if ( temp > local_max_candi )
                                       local_max_candi = temp;
                       }
                       max = (local_max > max) ? local_max : max;
               }

       cout << max << endl;

       sum--;
       for (int i=0; i<array_size+1; i++)
       {
               sum[i]--;
               delete [] sum[i];
       }
       delete [] sum;        // M de-alloc

       return 0;
}