Yuki Nakata's Blog

One color just reflects another

カテゴリ:プログラミング > C言語

ラズベリーパイでechoサーバーを作ろう の続きです。

引き続きネットワークプログラミングです。ファイルを転送するプログラムです。

普通はftpとかfilezillaを使ってファイルを転送するわけですが、シンプルなものであればプログラミングで作れます。

前回は文字列を送受信するプログラムを作りました。

文字列をファイルに置き換えるとできます。

結局やっていることはソケットを使ってread, writeしているだけです。

ネットワークにつないでしまえば、後はどうにかなります。

サーバー側です。cpserver.c

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <fcntl.h>
#include <sys/stat.h>


#define PORT 9877

int main(){
  
  int i = 0;
  int srcSocket;
  int dstSocket;
  
  struct sockaddr_in srcAddr;
  struct sockaddr_in dstAddr;
  int dstAddrSize = sizeof(dstAddr);
  // 各種パラメータ
  int status;
  int numrcv;
  char buf[1024];
  int len = 0;
  int size = 0;
  char filename[64];
  int fp;
  unsigned long filesize = 0;
  unsigned long totalrcv = 0;

  // sockaddr_in 構造体のセット
  bzero((char *)&srcAddr, sizeof(srcAddr));
  srcAddr.sin_port = htons(PORT);
  srcAddr.sin_family = AF_INET;
  srcAddr.sin_addr.s_addr = INADDR_ANY;
    
  srcSocket = socket(AF_INET, SOCK_STREAM, 0);
  bind(srcSocket, (struct sockaddr *)&srcAddr, sizeof(srcAddr));
  listen(srcSocket, 1);
  // 接続の受付け
  printf("接続を待っています\nクライアントプログラムを動かして下さい\n");
  dstSocket = accept(srcSocket, (struct sockaddr *)&dstAddr, &dstAddrSize);
  printf("%s から接続を受けました\n",inet_ntoa(dstAddr.sin_addr));

  while(1) {
memset(filename, 0, sizeof(filename));
len = read(dstSocket, buf, 2);
if(len < 0) {
 printf("エラー: ファイル名のエラーです。\n");
 return -1;
}

size = buf[0] << 8;      
    size |= buf[1];
len = read(dstSocket, buf, 4);
if(len < 0) {
 printf("エラー: ファイルサイズのエラーです。\n");
 return -1;
}
filesize = buf[0] << 24;
filesize |= buf[1] << 16;
filesize |= buf[2] << 8;
filesize |= buf[3];
printf("filesize = %ld byte\n", filesize);

len = read(dstSocket, filename, size);
if (len < 0) {
 printf("エラー: ファイル名を取得できませんでした。");
 return -1;
} else if (!strcmp(filename, "quit")) {
 printf("プログラムを終了します。\n\n");
 return 0;
}
printf("filename = %s\n", filename);

/* 書き込みファイルを開く */
if ((fp = open (filename, O_WRONLY | O_CREAT | O_TRUNC, 0666)) < 0) {
 printf("エラー ファイルを作成できません");
 return -1;
}

totalrcv = 0;
while(1){
 //パケットの受信
 numrcv = read(dstSocket, buf, 1024);
 //printf("%d %d\n", i, numrcv);
 if(numrcv <= 0 ){
break;
 }

 write(fp, buf, numrcv);
 totalrcv += numrcv;
 if(totalrcv >= filesize) {
printf("%s 転送完了\n\n", filename);
break;
 }
}
close(fp);
  }

  close(srcSocket);
  return(0);
}


クライアント側です。 cpclient.c
 
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <netdb.h>
#include <sys/stat.h>
#include <fcntl.h>

#define PORT 9877 //サーバープログラムとポート番号を合わせてください
char buf[1024];
char filesize[4];

int main(){
  char destination[32] = "192.168.0.10";//サーバーのIPアドレスを入れて下さい。
  //ソケット,sockaddr_in 構造体
  int dstSocket;
  struct sockaddr_in dstAddr;
  struct hostent *hp;
  int    numrcv;
  char filename[100];
  int len = 0;
  int fp;
  int size;
  struct stat statBuf;

  //sockaddr_in 構造体のセット
  bzero((char *)&dstAddr, sizeof(dstAddr));
  dstAddr.sin_family = AF_INET;
  dstAddr.sin_port = htons(PORT);
  
  hp = gethostbyname(destination);
  bcopy(hp->h_addr, &dstAddr.sin_addr, hp->h_length);

  //ソケットの生成
  dstSocket = socket(AF_INET, SOCK_STREAM, 0);
  
  //接続
  if (connect(dstSocket, (struct sockaddr *)&dstAddr, sizeof(dstAddr)) < 0){
    printf("%s に接続できませんでした\n",destination);
    return(-1);
  }
  printf("%s に接続しました\n",destination);
  
  while(1) {
    len = 0;
    memset(filename, 0, sizeof(filename));

    printf("送信するファイル名を入力してください\n");
    printf("quitで終了します\n\n");
    scanf("%s",filename);

    if (!strcmp(filename, "quit")) {
      printf("->bye\n");
      write(dstSocket, "00quit", 6);
      close(dstSocket);
      break;
    }
    while(filename[len] != '\0') {
      len++;
    }
    len++;
    buf[0] = (len >> 8) & 0xFF;
    buf[1] = len & 0xFF;
  
    fp = open(filename, O_RDONLY);
    if (fp < 0) {
      printf("エラー: ファイルを開けません\n");
      return(-1);
    }
    
    
    fstat(fp, &statBuf);
    printf("filesize = %ld byte\n", statBuf.st_size);
    filesize[0] = (statBuf.st_size >> 24 ) & 0xFF;
    filesize[1] = (statBuf.st_size >> 16 ) & 0xFF;
    filesize[2] = (statBuf.st_size >> 8) & 0xFF;
    filesize[3] = statBuf.st_size & 0xFF;
    

    write(dstSocket, buf, 2);
    write(dstSocket, filesize, 4);
    write(dstSocket,filename, len);
    while (1){
      /* ファイルから読み込み */
      size = read (fp, buf, sizeof(buf));
      /* データが無ければループを抜ける */
      if (size <= 0) {
break;
      }
      //パケットの送信
      write(dstSocket, buf, size);
            
    }
    write(dstSocket,"filetransferred", sizeof("filetransferred"));
    printf("%s 転送完了しました\n\n",filename);
    close(fp);
  }
  close(dstSocket);
  return(0);
}

cpclientと同じディレクトリにファイルを置いておきます。
あとは実行してファイル名を指定するとをサーバー側にコピーすることができます。
 
実行例
./cpclient

送信するファイル名を入力してください
quitで終了します

crazy.mp3
filesize = 6211191 byte
crazy.mp3 転送完了しました
 

たまにはプログラミングでもしてみまっか。

linuxユーザーでしたらwgetを使ったことがあると思います。

mywgetを作ってみましょう。30分コースです。

ネットワークプログラミングなわけですが、socketを使います。

普通linuxでファイルを扱うときにはopenしてread, writeします。socketはそのネットワーク版です。

socketを使うとネットワーク越しにread, writeできるわけです。linuxでは何でもファイル扱いです。

ハガキを送ることを考えてみましょう。相手の住所と名前が必要です。

socketの場合にはIPアドレスとポート番号が必要です。

yahoo.co.jpなどのドメインはgethostbyname関数一発でIPアドレスに変換できます。

ポート番号は80で固定です。


あとは普通アドレスはhttp://なんちゃらという形をしています。

これはhttpプロトコルを使うよ、ということです。

httpプロトコルではGETコマンドを送るとデータを返してくれるようになっています。

ネットワークプログラミングといってもこんなもんです。

さっそくソースコードを見てみましょう。
/* mywget

./mywget http://xxx/aaa.html
html, htm, zip, jpg, gifなどのようにファイル名を指定してください。

./mywget http://xxx/aaa/
スラッシュで終わる場合にはファイル名の関係からエラーになるようにしています。

*/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<sys/socket.h>
#include<netdb.h>
#include<unistd.h>
#include<fcntl.h>


#define BUF_LEN 1024

int main(int argc, char *argv[])
{
int fd;
int s;
int i = 0;
long int diff = 0;
char *p;
char host[BUF_LEN];
char path[BUF_LEN];
char filename[BUF_LEN];

char host_path[BUF_LEN];
char send_buf[BUF_LEN];

struct hostent *servhost;
struct sockaddr_in server;
unsigned short port = 80;

if (argc != 2) {
printf("URLを指定してください。\n");

return -1;
}

if (strstr(argv[1], "http://") && sscanf(argv[1], "http://%s", host_path)) {
p = strchr(host_path, '/');

if( p != NULL) {
strcpy(path, p);
*p = '\0';
}

strcpy(host, host_path);

p = strrchr(path, '/');
if(p != NULL) {
strcpy(filename, ++p);
} else {
strcpy(filename, path);
}
} else {
printf("URLはhttp://host/pathの形式で指定してください。\n");
return -1;
}

printf("\nhost = %s\n", host);
printf("path = %s\n", path);
printf("filename = %s\n", filename);

servhost = gethostbyname(host);
if(servhost == NULL) {
printf("[%s]からIPアドレスの変換に失敗しました。\n", host);
return -1; 
}

printf("IP Address %d.%d.%d.%d\n", (u_char)servhost->h_addr[0], (u_char)servhost->h_addr[1], (u_char)servhost->h_addr[2], (u_char)servhost->h_addr[3]);
bzero(&server, sizeof(server));

server.sin_family = AF_INET;

bcopy(servhost->h_addr, &server.sin_addr, servhost->h_length);

server.sin_port = htons(port);
 
/* ソケット生成 */
if ((s = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
printf("ソケットの生成に失敗しました。\n");
return -1;
}

/* サーバーに接続 */
if ( connect(s, (struct sockaddr *)&server, sizeof(server)) == -1) {
printf("connectに失敗しました\n");
return -1;
}

/* httpプロコトル コマンド送信 */
sprintf(send_buf, "GET %s HTTP/1.0\r\n", path);
write(s, send_buf, strlen(send_buf));

sprintf(send_buf, "Host: %s:%d\r\n",  host, port);
write(s, send_buf, strlen(send_buf));

sprintf(send_buf, "\r\n");
write(s, send_buf, strlen(send_buf));

fd = open(filename, O_CREAT|O_WRONLY|O_TRUNC, S_IRWXU|S_IRGRP|S_IXGRP|S_IROTH|S_IXOTH);
if (fd < 0) {
printf("open error\n");
return -1;
}

p = NULL;
while(1) {
char buf[BUF_LEN];
int read_size;

read_size = read(s, buf, BUF_LEN);

if (read_size > 0) {
if( i == 0) {
if(strstr(buf, "200") && strstr(buf, "OK")) {
p = strstr(buf, "\r\n\r\n");
if ( p != NULL) {
diff = p - buf;
p += 4;
write(fd, p, read_size - diff - 4);
}
} else {
break;
printf("http error\n");
}
} else {
write(fd, buf, read_size);
}
} else {
break;
}
i++;
}
close(fd);
close(s);
return 0;


return 0;
}

面倒くさいのがGETコマンドを送るとレスポンスヘッダ(ゴミ)とデータ(これが欲しい)を返してきます。

レスポンスヘッダとは問題ないよ、とか時刻とかファイルサイズとかファイルタイプ(jpgだよー)とかから構成されています。

レスポンスヘッダとデータを一緒に送ってきます。なのでレスポンスヘッダとデータを分離する必要があります。

それがwhile文の中のi = 0のときの処理です。

"\r\n\r\n"がレスポンスヘッダの終わりのしるしなので、それ以前を除去しています。

愛着のあるmywgetを使いましょう、ということです。

ネットワークプログラミング 続きます。



 

OpenMP 並列プログラミング2の続きです。

実際にOpenMPを使いこなしていきましょう。

グレゴリー・ライプニッツ級数でπを求めます。

π / 4 = arctan1 
 = (1 / 1) - (1 / 3) + (1 / 5) - (1 / 7) + (1 /9) - (1 / 11) ...無限に続く
 
グレゴリー・ライプニッツ級数は収束が遅いので実際にπを求める際には使われていません。

式がシンプルなforループで記述できるので並列プログラミング向きなのです。

並列化なし pi-leibniz.c
#include <stdio.h>
#include <time.h>

#define MAX 1000000000

int main()
{
int i;
double is = 1, a = 0;

clock_t start,end;
  start = clock();
for (i = 0; i < MAX; i++) {
if ((i % 2) == 0) {
is = 1;
} else {
is = -1;
}
a += is / (2 * i + 1); 
}
printf("%.15f\n", 4 *a);
end = clock();
  printf(" time [sec.] = %f \n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}

$ gcc pi-leibniz.c -o pi-leibniz
$ ./pi-leibniz
3.141592652588050
 time [sec.] = 6.853473 
6.8秒かかりました。

OpenMPで並列化 pi-leibniz2.c
#include <stdio.h>
#include <time.h>
#include <omp.h>

#define MAX 1000000000

int main()
{
int i;
double is = 1, a = 0;

double start,end;
  start = omp_get_wtime();

#pragma omp parallel for private(is) reduction(+:a)
for (i = 0; i < MAX; i++) {
if ((i % 2) == 0) {
is = 1;
} else {
is = -1;
}
a += is / (2 * i + 1); 
}
printf("%.15f\n", 4 *a);
end = omp_get_wtime();
  printf(" time [sec.] = %lf \n", end - start);

return 0;
}

$ gcc pi-leibniz2.c -o pi-leibniz2 -fopenmp
$ ./pi-leibniz2
3.141592652589210
 time [sec.] = 1.899626 
 
並列化をすると1.8秒。 すごい効果が出ています。コア4つなので、早く終わります。

ところがpiの結果が異なります。

並列なし  3.141592652588050
並列あり  3.141592652589210

微妙に異なります。MAX 10にして調べました。

並列なし ループ毎に加算しています。
0 : 1.000000000000000
1 : 0.666666666666667
2 : 0.866666666666667
3 : 0.723809523809524
4 : 0.834920634920635
5 : 0.744011544011544
6 : 0.820934620934621
7 : 0.754267954267954
8 : 0.813091483679719
9 : 0.760459904732351
3.041839618929403

並列化あり 
6 : 0.076923076923077
7 : -0.073777203188968
8 : 0.135746606334842
9 : -0.126408782136336
3 : -0.007110536522301
4 : -0.015297671025225
5 : -0.106206761934316
0 : 0.893793238065684
1 : 0.560459904732351
2 : 0.760459904732351
3.041839618929402
スレッド毎に加算して最後にまとめ上げています。
当たり前といえば当たり前か。そういう仕組みだからしょうがないのか。

その辺りに誤差の原因がありそうですね。

誤差のレベルなので無視してもいいのかもしれませんが、わかりません。

並列なしと並列ありで突き合せて、確かめた方がいいですね。注意が必要です。

OpenMP 並列プログラミング1の続きです。

for文で並列化してみましょう。

forループの前に#pragma omp parallel forを追加するだけです。

#include <stdio.h>
#include <omp.h>

int main()
{

int i;

#pragma omp parallel for
for (i = 0; i < 5; i++) {
printf("i = %d: thread number = %d\n", i, omp_get_thread_num());
}

return 0;
}
$ ./openmp1
i = 4: thread number = 3
i = 3: thread number = 2
i = 2: thread number = 1
i = 0: thread number = 0
i = 1: thread number = 0 

$ ./openmp1
i = 0: thread number = 0
i = 1: thread number = 0
i = 3: thread number = 2
i = 4: thread number = 3
i = 2: thread number = 1

iの並びがランダムになっています。 


並列プログラミングのサンプルソースを読んでみました。OpenMPのポイントです。

一時的な変数にはprivate, 結果を残す変数にはreductionを変数に付ける。

配列を加算するプログラム。
#include <stdio.h>
#include <stdlib.h>
#include <omp.h>
#define MAX 50000

int *box;

int main()
{
int i, total = 0;

box = malloc(MAX * sizeof(int));
for (i = 0; i <= MAX; i++) {
box[i] = i;
}

#pragma omp parallel
{
printf("thread = %d, %d\n", omp_get_thread_num(), omp_get_num_threads());

#pragma omp for reduction(+:total)
for (i = 0; i <= MAX; i++) {
total += box[i];
}
}
printf("total = %d\n", total);
return 0;
}

$ gcc openmp2.c -o openmp2 -fopenmp
$ ./openmp2
thread = 0, 4
thread = 2, 4
thread = 3, 4
thread = 1, 4
total = 1250025000
 
結果を残すのでtotal変数にはreduction(+:total)を付けています。
変数totalをスレッドで共有する必要があります。

実験でreductionなしにして、 #pragma omp for に変更してみてください。
間違った結果が帰ってきます。

参考サイト
OpenMP チュートリアル 

OpenMP* を使用したワークシェアリング 

素数判定法5 繰り返し二乗法の続きになります。

前回はフェルマーテストの変数をlong long型で宣言していました。

long long型でも巨大な数字になると溢れてしまいます。

巨大な素数に対応するためにフェルマーテストをgmpライブラリーを使ってプログラミングしました。

えらい大変やった。脳みそ使うわ。

fermatgmp.c

#include<stdio.h>
#include<gmp.h>

int main()
{
mpz_t m, n, s, a;
mpz_t one, tmp1, tmp2, tmp3;

printf("数字を入力してください\n");
mpz_init(n);
gmp_scanf("%Zd", n);

mpz_init(m);
mpz_sub_ui(m, n, 1); //m = n - 1;

mpz_init(s);
mpz_set_str(s, "1", 10); // s = 1;

mpz_init(a);
mpz_set_str(a, "2", 10); // a = 2;

mpz_init(one);
mpz_set_str(one, "1", 10);

mpz_init(tmp1);
mpz_init(tmp2);
mpz_init(tmp3);

while(mpz_sgn(m)) { //while(m != 0) {
mpz_and(tmp1, m, one); //if (m & 1) {
if (mpz_sgn(tmp1)) {
mpz_mul(tmp2, s, a); //s = (s * a) % n;
mpz_mod(s, tmp2, n);

}
printf("m = ");
mpz_out_str(stdout, 10, m);
printf(" s = ");
mpz_out_str(stdout, 10, s);
printf(" a = ");
mpz_out_str(stdout, 10, a);
printf("\n");

//printf("m = %lld s = %lld a = %lld\n", m, s, a);

mpz_mul(tmp3, a, a); //a = (a * a) % n;
mpz_mod(a, tmp3, n);

mpz_div_2exp(m, m, 1); //m = m>>1;
}

mpz_out_str(stdout, 10, n);
if(!mpz_cmp_ui(s, 1)) {
printf("は素数です\n");
} else {
printf("は素数じゃないよ\n");
}

mpz_clear(m);
mpz_clear(n);
mpz_clear(s);
mpz_clear(a);
mpz_clear(tmp1);
mpz_clear(tmp2);
mpz_clear(tmp3);
return 0;

}

$ gcc fermatgmp.c -o fermatgmp -lgmp
$ ./fermatgmp
数字を入力してください
26588814640432479998443
26588814640432479998443は素数です

私のMac BookProだと一瞬で計算が終わります。
対応するC言語をコメントで残しています。
検証用に計算過程を表示させています。
邪魔であればコメントアウトしてくださぁい。

フェルマーテストの場合、素数を誤判定する可能性があります。

それで改良されたのがミラーラビン法です。

ミラーラビン法を使うことで誤判定の確率が減ります。

ミラーラビン法へ続く予定。いや続かないかも。多分続きます。
 

素数判定法5 フェルマーテストの続きです。

n が素数であるかを調べるために2 ^ nを計算しなければならない、ということでした。

n = 13のとき本来であれば

2 ^ 13 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2

2を12回掛けなければいけません。

これを簡単にするのが繰り返し二乗法です。

乗数を分解して、

2 ^ 13 = (2 ^ 1) * (2 ^ 4) * (2 ^ 8)  = 2 * 16 * 256 に分解するのが繰り返し二乗法です。

繰り返し二乗法を使えば計算回数を減らすことができます。

フェルマーの小定理を貼り付けておきます。

2 ^ (n - 1) mod n = 1 

c言語プログラム 
#include<stdio.h>

int main()
{
long long m, n;
long long s = 1;
long long a = 2;
printf("数字を入力してください\n");
scanf("%lld", &n);
m = n -1;
while(m != 0) {
if (m & 1) {
s = (s * a) %n;
}
printf("m = %lld s = %lld a = %lld\n", m, s, a);
a = (a * a) % n;
m = m>>1;
}
if (s == 1) {
printf("%lldは素数です\n", n);
} else {
printf("%lldは素数ではありません\n", n);
}
}

$ gcc fermat.c -o fermat

$ ./fermat

数字を入力してください

9999637

9999637は素数です 

素数判定法6 フェルマーテスト GMPライブラリ に続きます。

参考サイト
繰り返し二乗法

素数判定プログラム3 C言語GMPライブラリの続きです。

今までとは違った素数判定プログラムを書いていきます。

前回のgmpプログラムではmpz_probab_prime_p 関数を使いました。

実行すると計算が一瞬で終わります。一体どういう仕組みなのでしょうか。

mpz_probab_prime_p 関数は内部でMiller_Rabin 素数テストを行っています。

では、Miller Rabin素数テストとは何かを調べていきましょう。

Miller Rabin素数テストはフェルマーテストを改良して作られたものです。

というわけでまずはフェルマーテストの説明から。


nが素数の場合、

a ^ (n - 1) ≡ 1 (mod n)

が成立します。 a については 1 <= a < n という条件がついています。 ま、そりゃそうです。

aについては単純にa = 2 と置き換えて問題ありません。

上の式を変換すると

2 ^ (n - 1 ) mod n = 1

計算結果が1となると素数と判定します。

素数3の場合 2 ^ 2= 4,  4 % 3 = 1

素数5の場合 2 ^ 4 = 16, 16 % 5 = 1

素数7の場合 2 ^ 6 = 64, 64 % 7 = 1

素数の場合は必ず計算結果の余りが1 となります。これがフェルマーテストです。

1にならない場合は素数ではないので弾くことができます。

ところが素数でない場合も1 となることがあります。

341 = 11 * 31 は素数ではありませんが2となります。 

(2 ^ 340) % 341 = 1

前回までのプログラムは素数かどうかを割り算をして割り切れるかどうかを調べました。

フェルマーテストの場合は乗数計算となります。

しかも数が爆発します。

41が素数かどうかを調べるには 2 ^ 40です。計算すると1099511627776 になります。

2を40回掛け算しなければいけません。

これは大変、ということで簡単にするアルゴリズムがあります。

繰り返し二乗法です。

素数判定法5 繰り返し二乗法に続きます。

↑このページのトップヘ