南浦月 发布的文章

循环冗余校验(CRC)算法入门

CRC 算法原理

CRC 算法的基本原理是将数据看作一个大数,与一个预定义的除数使用特殊的除法相除,所得的余数即为数据的 CRC 校验值。

生成多项式

算法的数学原理与多项式相关,用到的除法也基于多项式除法,预定义的除数也叫“生成多项式”,这里的多项式都是只有一个未知数并且各项系数只能是 0 或 1 的多项式(更多的信息可以参考维基百科:有限域算术,这里不多讲)。

我们以 CRC-4/ITU 为例,其生成多项式是 $x^4 + x + 1$,也即:

$$1x^4 + 0x^3 + 0x^2 + 1x^1 + 1x^0$$

如果我们令 $x = 2$,则多项式中每一项的系数可以看作一个二进制数的对应位,即 $(10011)_2$,是一个 5 位的二进制数,那么用它来做除数,最后可以得到 4 位的余数,也就是 CRC-4/ITU 中的 4。由此可见,生成多项式的首位必然是 1,在一般表示生成多项式的时候我们都省略最高位,再写成十六进制就是 0x03

模二多项式除法

我们先看多项式乘法:

$$ (x^4 + x^1 + x^0) \times (x^4 + x^3 + x^0) = x^8 + x^7 + x^4 + x^5 + x^4 + x^1 + x^4 + x^3 + x^0 $$

这里我们没有合并同类项,如果按照常规的方式合并同类项,即

$$ x^8 + x^7 + x^5 + 3x^4 + x^3 + x^1 + x^0 $$

那就是普通的多项式乘法;对于 CRC 算法,加减法采用模二运算,也就是最后的系数除以 2 取余数,不产生进位,所以最后的结果是:

$$ x^8 + x^7 + x^5 + x^4 + x^3 + x^1 + x^0 $$

- 阅读剩余部分 -

SHA-256 的纯 Rust 实现

出于了解 SHA-256 算法及学习 Rust 的目的,用纯 Rust 实现了一个 SHA-256 库。

SHA-256 算法简介

首先简单介绍一下 SHA-256 算法,SHA-256 是 SHA-2 系列算法中的一种,关于 SHA-2 的相关介绍可以查看其维基百科,其中也详细介绍了 SHA-256 的算法。

简单的说, SHA-256 算法分为以下几步:

  1. 对消息进行填充预处理,先附加 bit 1,然后填充可变数量(0-511)的 bit 0,最后附加 u64(big-endian, 64 bits)类型的原始消息长度的 bit 数,使填充后的消息长度为 512 bits 即 64 bytes)的整数倍
  2. 对预处理后的消息进行分片,每 512 bits 为一个分片
  3. 对每个分片进行迭代处理,每次迭代以该分片及 8 个 u32 为输入,并输出 8 个 u32 作为下一个迭代的输入
  4. 最后一个分片处理完成输出的 8 个 u32 既是最后的结果

要用到的两组常量

其中第 3 步对各个分片的迭代处理又要用到两组常量:

一是对第一个分片进行处理时作为输入的 8 个初始的 u32

static H: [u32; 8] = [
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
];

它们是自然数中前 8 个质数 2、3、5、7、11、13、17、19 平方根的小数部分取前 32 bits。

- 阅读剩余部分 -

在 vscode 中使用 gdb 跨平台远程调试 C/C++ 代码

重新编译安装 gdb

要使用 gdb 跨平台远程调试,需要在编译 gdb 的时候开启相关的支持选项,简单的说在 configure 选项中加入 --enable-targets=all

archlinux 用户可以使用 asp 来获取 gdb 的 PKGBUILD,做如下修改:

build() {
  cd gdb-$pkgver
  
  ./configure --prefix=/usr --disable-nls \
    --enable-targets=all \
    --with-system-readline \
    --with-python=/usr/bin/python3 \
    --with-guile=guile-2.0 \
    --with-system-gdbinit=/etc/gdb/gdbinit
  make
}

然后运行 makepkg -si 编译安装,应该会报签名无法验证的错误,这时候需要我们先导入 PGP 公钥:

gpg --keyserver pgp.ustc.edu.cn  --recv-keys 92EDB04BFF325CF3

然后再运行 makepkg -si

- 阅读剩余部分 -

借助 Nginx 搭建带简单认证的直播推流服务器,实现多平台同步直播

原理

使用 nginx-rtmp-module 接收 rtmp 流,然后同时推送到多个直播平台,同时使用 lua-nginx-module 来做简单的身份验证。

安装必须的 nginx 模块

debian 9 用户可以直接使用 apt 安装,需启用 stretch-backports 源:

sudo apt install libnginx-mod-rtmp libnginx-mod-http-lua -t stretch-backports

nginx 配置

Gist: nginx.conf

# file: nginx.conf
# date: 2018-10-13
# license: GPLv3 https://www.gnu.org/licenses/gpl-3.0.txt
# author: nanpuyue <nanpuyue@gmail.com> https://blog.nanpuyue.com

user www-data;
worker_processes auto;
pid /run/nginx.pid;
include /etc/nginx/modules-enabled/*.conf;

events {
    worker_connections 768;
}

rtmp {
    server{
        listen 1935;
        chunk_size 10240;

        application live {
            live on;
            record off;
            on_publish http://127.0.0.1:2080/auth;
            push rtmp://live.twitch.tv/app/xxxxxxxxxx;
            push rtmp://a.rtmp.youtube.com/xxxxxxxxxx;
        }
    }
}  

http {
    server {
        listen 127.0.0.1:2080;
        location /auth {
            rewrite_by_lua '
                ngx.req.read_body()
                local name = ngx.req.get_post_args().name
                if (name == "xxxxxxxxxx") then
                    ngx.status = 200
                    ngx.say("OK")
                    ngx.exit(200)
                else
                    ngx.status = 403
                    ngx.say("Forbidden")
                    ngx.exit(403)
                end
            ';
        }
    }
}

- 阅读剩余部分 -

知道了也没什么用的小知识:终端标题与转义序列

起因

事情的起因是这样的,我在 archlinux (以下简称 arch) 下的端模拟器(以下简称终端)使用 set -x 来调试,发现每次按回车都会一条类似下面这样的输出:

++ printf '\033]0;%s@%s:%s\007' nanpuyue arch '~'

然后我手动执行了这条命令也看不到任何输出和变化,着实令人费解。

OSC 转义序列

一番查找过后在 /etc/bash.bashrc 中找到了源头:

case ${TERM} in
  xterm*|rxvt*|Eterm|aterm|kterm|gnome*)
    PROMPT_COMMAND=${PROMPT_COMMAND:+$PROMPT_COMMAND; }'printf "\033]0;%s@%s:%s\007" "${USER}" "${HOSTNAME%%.*}" "${PWD/#$HOME/\~}"'

    ;;
  screen*)
    PROMPT_COMMAND=${PROMPT_COMMAND:+$PROMPT_COMMAND; }'printf "\033_%s@%s:%s\033\\" "${USER}" "${HOSTNAME%%.*}" "${PWD/#$HOME/\~}"'
    ;;
esac

- 阅读剩余部分 -