2020年5月

TCP/IP网络编程,一个简单的并发TCP server


本文在上篇文章的基础上,实现了服务端的并发,支持多个客户端同时连接到服务端上。

实现并发连接的主要技术是利用fork函数为每个客户端连接分配一个单独的进程进行处理。

server.cpp代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <netinet/in.h>
#include <sys/socket.h>
#include <unistd.h>

constexpr uint32_t MAXLEN = 4096;
constexpr uint16_t PORT = 6666;
constexpr uint32_t MAX_CONN_MUN = 10;

inline void PrintErr()
{
    printf("errno = %s\n", strerror(errno));
}

int CreateSocket(uint16_t port, int& listen_fd)
{
    listen_fd = socket(AF_INET, SOCK_STREAM, 0);
    if (listen_fd == -1) {
        PrintErr();
        return -1;
    }

    sockaddr_in serv_addr;
    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(port);

    int ret = bind(listen_fd, reinterpret_cast<sockaddr*>(&serv_addr), sizeof(serv_addr));
    if (ret == -1) {
        PrintErr();
        return -1;
    }

    ret = listen(listen_fd, MAX_CONN_MUN);
    if (ret == -1) {
        PrintErr();
        return -1;
    }

    return 0;
}

void StrEcho(int sock_fd)
{
    char buf[MAXLEN];
    ssize_t n;
again:
    while ((n = read(sock_fd, buf, sizeof(buf))) > 0) {
        printf("rev msg: %s\n", buf);
        write(sock_fd, buf, n);
    }
    if (n < 0 && errno == EINTR) {
        goto again;
    } else if (n < 0) {
        printf("read error\n");
    }
}

int main()
{
    int listen_fd;
    int ret = CreateSocket(PORT, listen_fd);
    if (ret != 0) {
        exit(0);
    }

    sockaddr_in cliaddr;
    socklen_t clilen;
    pid_t child_pid;
    while (true) {
        int conn_fd = accept(listen_fd, reinterpret_cast<sockaddr*>(&cliaddr), &clilen);
        if (conn_fd == -1) {
            PrintErr();
            return -1;
        }
        if ((child_pid = fork()) == 0) {
            printf("rev conn req, start a child proc, pid=%u\n", child_pid);
            close(listen_fd);
            StrEcho(conn_fd);
            exit(0);
        }
        close(conn_fd);
    }

    return 0;
}

client.cpp代码

#include <arpa/inet.h>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <netinet/in.h>
#include <sys/socket.h>
#include <unistd.h>

constexpr uint16_t SERV_PORT = 6666;
constexpr uint32_t MAXLEN = 4096;

inline void PrintErr()
{
    printf("errno = %s\n", strerror(errno));
}

int CreateSocket(const char *ip, uint16_t port, int& sock_fd)
{
    sock_fd = socket(AF_INET, SOCK_STREAM, 0);
    if (sock_fd == -1) {
        PrintErr();
        return -1;
    }

    sockaddr_in serv_addr;
    memset(&serv_addr, 0, sizeof(serv_addr));
    serv_addr.sin_family = AF_INET;
    serv_addr.sin_port = htons(SERV_PORT);
    int ret = inet_pton(AF_INET, ip, &serv_addr.sin_addr);
    if (ret == -1) {
        printf("inet_pton err, argv[1]=%s\n", ip);
        return -1;
    }

    ret = connect(sock_fd, reinterpret_cast<sockaddr*>(&serv_addr), sizeof(serv_addr));
    if (ret == -1) {
        PrintErr();
        return -1;
    }

    return 0;
}

int main(int argc, char** argv)
{
    if (argc != 2) {
        exit(0);
    }

    int sock_fd;
    int ret = CreateSocket(argv[1], SERV_PORT, sock_fd);
    if (ret != 0) {
        exit(0);
    }

    char buf[MAXLEN];
    while (std::cin.getline(buf, MAXLEN)) {
        write(sock_fd, buf, strlen(buf));
        if (read(sock_fd, buf, MAXLEN) == 0) {
            exit(0);
        }
        printf("rev msg: %s\n", buf);
    }

    return 0;
}

makefile代码

all:server client
server:server.o
    g++ -g -o server server.o
client:client.o
    g++ -g -o client client.o
server.o:server.cpp
    g++ -g -c server.cpp
clinet.o:client.cpp
    g++ -g -c client.cpp
clean:all
    rm all

执行make命令,打开两个终端一个执行./server一个执行./client 127.0.0.1


TCP/IP网络编程,一个简单的TCP server


用TCP协议编写一个简单的服务器,客户端,服务器一直监听本机的6666端口。

server.cpp代码

#include <errno.h>
#include <netinet/in.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <unistd.h>

constexpr int MAXLNE = 4096;

int main(int argc, char **argv) 
{
    int listenfd, connfd, n;
    struct sockaddr_in servaddr;
    char buff[MAXLNE];

    if ((listenfd = socket(AF_INET, SOCK_STREAM, 0)) == -1) {
        printf("create socket error: %s(errno: %d)\n", strerror(errno), errno);
        return 0;
    }

    memset(&servaddr, 0, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_addr.s_addr = htonl(INADDR_ANY);
    servaddr.sin_port = htons(6666);

    if (bind(listenfd, (struct sockaddr *)&servaddr, sizeof(servaddr)) == -1) {
        printf("bind socket error: %s(errno: %d)\n", strerror(errno), errno);
        return 0;
    }

    if (listen(listenfd, 10) == -1) {
        printf("listen socket error: %s(errno: %d)\n", strerror(errno), errno);
        return 0;
    }

    printf("========waiting for client's request========\n");
    while (true) {
        if ((connfd = accept(listenfd, (struct sockaddr *)nullptr, nullptr)) == -1) {
            printf("accept socket error: %s(errno: %d)\n", strerror(errno), errno);
            continue;
        }
        n = recv(connfd, buff, MAXLNE, 0);
        buff[n] = '\0';
        printf("recv msg from client: %s\n", buff);
        close(connfd);
    }

    close(listenfd);
    return 0;
}

client.cpp代码

#include <arpa/inet.h>
#include <errno.h>
#include <netinet/in.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <unistd.h>

constexpr int MAXLNE = 4096;

int main(int argc, char **argv) 
{
    int sockfd, n;
    struct sockaddr_in servaddr;
    char sendline[MAXLNE], recvline[MAXLNE];

    if (argc != 2) {
        printf("usage: ./client <ipaddress>\n");
        return 0;
    }

    if ((sockfd = socket(AF_INET, SOCK_STREAM, 0)) < 0) {
        printf("create socket error: %s(errno: %d)\n", strerror(errno), errno);
        return 0;
    }

    memset(&servaddr, 0, sizeof(servaddr));
    servaddr.sin_family = AF_INET;
    servaddr.sin_port = htons(6666);
    if (inet_pton(AF_INET, argv[1], &servaddr.sin_addr) <= 0) {
        printf("inet_pton error for %s\n", argv[1]);
        return 0;
    }

    if (connect(sockfd, (struct sockaddr *)&servaddr, sizeof(servaddr)) < 0) {
        printf("connect error: %s(errno: %d)\n", strerror(errno), errno);
        return 0;
    }

    printf("send msg to server: \n");
    fgets(sendline, MAXLNE, stdin);
    if (send(sockfd, sendline, strlen(sendline), 0) < 0) {
        printf("send msg error: %s(errno: %d)\n", strerror(errno), errno);
        return 0;
    }

    close(sockfd);
    return 0;
}

makefile代码

all:server client
server:server.o
    g++ -g -o server server.o
client:client.o
    g++ -g -o client client.o
server.o:server.cpp
    g++ -g -c server.cpp
clinet.o:client.cpp
    g++ -g -c client.cpp
clean:all
    rm all

执行make命令,打开两个终端一个执行./server一个执行./client 127.0.0.1


快速沃尔什变换(FWT)模板题 CSU 1911 Card Game


题目描述: 给你两个二进制数的集合,给出q次询问,输出两个集合之间元素或的值等于查询值的种数。
题目链接: Card Game

快速沃尔什变换详解请看快速沃尔什变换详解

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
const int maxn = 1 << 18;
LL a[maxn], b[maxn];
int n, m;
char s[20];

void FWT(LL a[], int n)
{
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j + d] = x + y;
            }
        }
    }
}

void UFWT(LL a[], int n)
{
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j + d] = y - x;
            }
        }
    }
}
void solve(LL a[], LL b[], int n)
{
    FWT(a, n);
    FWT(b, n);
    for (int i = 0; i < n; i++) {
        a[i] = a[i] * b[i];
    }
    UFWT(a, n);
}

int main()
{
    int t, q;
    scanf("%d", &t);
    for (int cas = 1; cas <= t; cas++) {
        memset(a, 0, sizeof a);
        memset(b, 0, sizeof b);
        scanf("%d%d", &n, &m);
        int l, x;
        for (int i = 0; i < n; i++) {
            x = 0;
            scanf("%s", s);
            l = strlen(s);
            for (int j = 0; j < l; j++)
                x = (x << 1) + s[j] - '0';
            a[x]++;
        }
        for (int i = 0; i < n; i++) {
            x = 0;
            scanf("%s", s);
            l = strlen(s);
            for (int j = 0; j < l; j++)
                x = (x << 1) + s[j] - '0';
            b[x]++;
        }
        solve(a, b, (1 << m));
        scanf("%d", &q);
        printf("Case #%d:\n", cas);
        while (q--) {
            scanf("%s", s);
            x = 0;
            l = strlen(s);
            for (int i = 0; i < l; i++)
                x = (x << 1) + s[i] - '0';
            printf("%lld\n", a[x]);
        }
    }
    return 0;
}

快速沃尔什变换(FWT)讲解 解决集合卷积的方法


能看到这篇博客的人,一定知道FWT是干什么的。(什么?你不知道?)
没事,这里有pick讲FWT的博客。先点进去看一看。
如果你看懂了,那么恭喜你。如果你跟我一样看不懂,那么请继续往下看。

这里的A和B都是什么呢?其实它们是一个多维的向量(如果你不知道向量是什么,就把它当成数组),下标从0开始。
其中,$ A = <a_{0},a_{1},...,a_{2^{k}-1}> $,$ B = <b_{0},b_{1},...,b_{2^{k}-1}> $,$ C = A\otimes B $
这里我们定义$$ A\pm B = < a_{0}\pm b_{0}, a_{1}\pm b_{1},..., (a_{2^{k}-1})\pm (b_{2^{k}-1}) > $$ 即对应位相加(减)$$ A * B = < a_{0} * b_{0}, a_{1} * b_{1},..., (a_{2^{k}-1}) * (b_{2^{k}-1}) > $$即对应位相乘$ A\otimes B $ 为A和B做卷积之后得到的结果,也是一个和原来大小一样的向量。

注意到FWT做的是二进制上的位运算,所以一定要把A和B补到2的整次幂次(即不足的地方填上0)。

我们要构造一个变换tf,使得$tf(A)*tf(B)=tf(C)$。这个变换的对象是一个大小为$2^{k}$的向量,变换出来的结果也是一个大小为$2^{k}$的向量。

就以异或举例。picks告诉我们$$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$$$$A_{0}=<a_{0},a_{1},...,a_{2^{k-1}-1}>$$$$A_{1}=<a_{2^{k-1}},a_{2^{k-1}+1},...,a_{2^{k}-1}>$$即把A中的下标按照二进制最高位为0或1分成前后两部分(前面的为$A_{0}$,后面的为$A_{1}$),分治下去做。

分治之后得到$tf(A_{0})$和$tf(A_{1})$。然后tf(A)的前半部分(即$[0,2^{k-1}-1]$)为$tf(A_{0})+tf(A_{1})$,后半部分(即$[2^{k-1},2^{k}-1]$)为$tf(A_{0})-tf(A_{1})$。(其实就是已知两个向量,把两个向量做加减运算,加的那个结果填到前一半中,减的那个结果填到后一半中)。

然而,这为什么是对的?
接下来我们来证明它是对的。

我要事先说明(注意不是证明)一个引理:$tf(A+B)=tf(A)+tf(B)$。这个东西看上去挺直观的(一点都不直观好吗。。)。这个东西可以用数学归纳法证。这里略过。。。(有时间的时候再补上)

我们看k=1的时候。根据定义,有$$tf(A)=<a_{0}+a_{1},a_{0}-a_{1}>$$$$tf(B)=<b_{0}+b_{1},b_{0}-b_{1}>$$$$tf(C)=<c_{0}+c_{1},c_{0}-c_{1}>$$$$c_{0}=a_{0}*b_{0}+a_{1}*b_{1},c_{1}=a_{0}*b_{1}+a_{1}*b_{0}$$自己代代看,反正代出来很神奇的的发现$tf(A)*tf(B)=tf(C)$

接下来使用数学归纳法。假设对于大小都为$2^{k}(k\epsilon N)$的向量A和B,满足$C = A\otimes B$,并且$tf(A)*tf(B)=tf(C)$。
考虑当大小为$2^{k+1}$的情况。我们要证明在这种情况下,$tf(A)*tf(B)=tf(C)$。根据定义,有
$$tf(A)=(tf(A_{0})+tf(A_{1}),tf(A_{0})-tf(A_{1}))$$$$tf(B)=(tf(B_{0})+tf(B_{1}),tf(B_{0})-tf(B_{1}))$$$$tf(A)*tf(B)=([tf(A_{0})+tf(A_{1})]*[tf(B_{0})+tf(B_{1})],[tf(A_{0})-tf(A_{1})]*[tf(B_{0})-tf(B_{1})])$$
暴力把式子拆开,有
$tf(A)*tf(B)=$
$$(tf(A_{0})*tf(B_{0})+tf(A_{0})*tf(B_{1})+tf(A_{1})*tf(B_{0})+tf(A_{1})*tf(B_{1}),$$$$tf(A_{0})*tf(B_{0})+tf(A_{1})*tf(B_{1})-tf(A_{0})*tf(B_{1})-tf(A_{1})*tf(B_{0}))$$
注意到这里的$A_{0}$,$A_{1}$,$B_{0}$,$B_{1}$都是大小为$2^{k}$的向量,符合归纳的基础。于是,
$tf(A)*tf(B)=$
$$(tf(A_{0}\otimes B_{0})+tf(A_{0}\otimes B_{1})+tf(A_{1}\otimes B_{0})+tf(A_{1}\otimes B_{1}),$$$$tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1})-tf(A_{1}\otimes B_{0}))$$
由于异或每一位是独立,而这里如果我们把C按照最高位为0或1分成两部分,最高位的异或和其它位不相关。
于是有$$C=(C_{0},C_{1})=(A_{0}\otimes B_{0}+A_{1}\otimes B_{1},A_{0}\otimes B_{1}+A_{1}\otimes B_{0})$$
要证的等式
$$右边=tf(C)=tf(C_{0},C_{1})$$$$=tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1},A_{0}\otimes B_{1}+A_{1}\otimes B_{0})$$$$=(tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1})+tf(A_{0}\otimes B_{1}+A_{1}\otimes B_{0}),tf(A_{0}\otimes B_{0}+A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1}+A_{1}\otimes B_{0}))$$$$=(tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})+tf(A_{0}\otimes B_{1})+tf(A_{1}\otimes B_{0}),tf(A_{0}\otimes B_{0})+tf(A_{1}\otimes B_{1})-tf(A_{0}\otimes B_{1})-tf(A_{1}\otimes B_{0}))$$$$=tf(A)*tf(B)=左边$$
至此,证毕。

然而这只是一个tf,还有一个逆变换utf。这个逆变换的正确性可以用同样的方法证明,即先看k=1的情况,然后一步一步用数归推上去。
证明方法比较简单(真的很简单),这里略过。

至于其它位运算,其证明方法与异或一致,这里不赘述。

说了这么多,其实这个证明并没有什么卵用(只是使得自己相信它是对的)。。大家还是背代码吧。。。

看完的找个模板题练练手感受一下吧,CSU 1911 Card Game

模板

// 题目要求取模时使用mod,否则去除mod
void FWT(int a[], int n)
{
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j] = (x + y) % mod;
                a[i + j + d] = (x - y + mod) % mod;
                // xor: a[i+j]=x+y, a[i+j+d]=x-y;
                // and: a[i+j]=x+y;
                // or: a[i+j+d]=x+y;
            }
        }
    }
}
void UFWT(int a[], int n)
{
    for (int d = 1; d < n; d <<= 1) {
        for (int m = d << 1, i = 0; i < n; i += m) {
            for (int j = 0; j < d; j++) {
                int x = a[i + j];
                int y = a[i + j + d];
                a[i + j] = 1LL * (x + y) * rev % mod;
                a[i + j + d] = (1LL * (x - y) * rev % mod + mod) % mod;
                // xor: a[i+j]=(x+y)/2, a[i+j+d]=(x-y)/2;
                // and: a[i+j]=x-y;
                // or: a[i+j+d]=y-x;
            }
        }
    }
}
void solve(int a[], int b[], int n)
{
    FWT(a, n);
    FWT(b, n);
    for (int i = 0; i < n; i++) {
        a[i] = 1LL * a[i] * b[i] % mod;
    }
    UFWT(a, n);
}

docker一键部署typecho博客网站


首先下载附件上传到服务器目录

使用脚本安装docker

#确保 yum 包更新到最新
sudo yum update

#执行 Docker 安装脚本,执行这个脚本会添加 docker.repo 源并安装 Docker。
curl -fsSL https://get.docker.com/ | sh

#启动 Docker 进程
sudo service docker start

#验证 docker 是否安装成功并在容器中执行一个测试的镜像
sudo docker run hello-world

设置docker开机自启动

sudo systemctl enable docker

安装docker compose

# 下载最新版本的 docker-compose 到 /usr/bin 目录下
curl -L https://github.com/docker/compose/releases/download/1.25.5/docker-compose-`uname -s`-`uname -m` -o /usr/bin/docker-compose

# 给 docker-compose 授权
chmod +x /usr/bin/docker-compose

下载typecho

下载到当前目录,解压到typecho文件夹
修改typecho.conf中的server_name为具体的域名
mysql.env中配置,具体详见mysql.env即可
进入php文件夹,执行docker build -t scofieldpeng/php-fpm:7.2.3-fpm .
返回项目根目录,然后执行docker-compose up -d即可
在宿主机的nginx中新建相应的配置文件,proxy到8080即可
初始化typecho配置
使用HTTPS
由于是采用的proxy到容器的80端口,因此typecho不会知道目前是用的https协议,通过源码可以看到,typecho支持显性告诉当前的域名是https,因此可以在typecho的index.php或者config.inc.php中添加下列代码:

开启https支持

define('__TYPECHO_SECURE__',TRUE);
当然,如果你的服务器只需要跑一个博客,而不需要其他的服务在80或者443端口,直接修改typecho.conf,添加https,再修改docker-compose.yaml文件,暴露出80和443端口即可,这里不做详细阐述。

备份和恢复/迁移

备份很简单,直接将项目目录整个copy下来即可,恢复时整个文件夹上传到新的服务器,然后进入目录执行docker-compose up -d重新跑起来即可,方便快捷

mysql管理

可以看到docker-compose中mysql镜像时暴露出了3306端口到127.0.0.1,可以通过ssh代理登录3306端口进行管理,也可以安装一个phpadmin的容器连接上,看自己方便啦!

一键部署附件
docker-typecho-master.rar