喷泉码与libRaptorQ的编译与调用

前段时间稍微接触了下喷泉吗，并找到了用C++语言实现并兼容C的RaptorQ开源库。由于官方文档对于函数具体行为的说明很不充分，在最开始的使用中遇到了一些困难。不过来回尝试几次后基本对API理解的比较透彻了，库本身的可用性也没什么问题。把整理好的PDF文档编辑了一下放上来。

另外碎碎念一下，对wordpress还不是很了解，排版感觉不是很理想，可读性不是特别好。当前主题对一级标题的处理也有问题。下一步尽量多学习学习WP，争取把这个站点早日调整好。

 

 I.喷泉码简介

1.概论

喷泉码是一种特殊的前向纠错码（FEC），其理论特征十分简单：如果想发送的数据大小为K个数据包的大小，通过喷泉码编码后可以产生并实际发出K+X个数据包，而接收方只需要这其中的任意K个数据包就可以重建原数据。超出原始数据大小的X个数据包理论可以无穷多地生成，因此可以通过调整X的量以适应不同环境不同丢包率的需求。

系统码：RaptorQ（以下简称RQ）作为喷泉码的一种，同时也是系统码（Systematic Code）。这意味着一组数据如果通过RQ进行编码，生成的前K个数据包将与输入数据完全一致。我们称这K个数据包为源码符（source symbols）。而基于源数据额外生成的X个数据包，我们称之为修复码（repair symbols）。修复码被用于恢复在传输过程中丢失的源码符。因此，如果传输过程中没有丢失任何源码符，不需要任何解码运算就可以获重建源数据，可以节省时间与内存占用。这种特性也是系统码的一大优点。

复杂度：RQ的编码与解码算法通常被宣传为有着线性（O(n)）复杂度，但实际情况并非如此。从中间码（intermediate symbols）生成源码符与修复码的过程确实是线性复杂度，但生成中间码的过程实际是立方复杂度（O(n³)）的运算。在2.4GHz酷睿i7 CPU上，生成10个符号（symbol，通常一个生成的符号封入一个数据包发送，与上文提到的数据包的概念相近）需要0.4ms，1000个符号需要280ms，而27000个符号耗时超过一小时。RQ最多支持生成56403个符号。

 

2. 数据区块（Block）与符号（Symbol）

为了使用libRaptorQ（以下简称libRQ），我们首先需要了解RQ是如何处理输入、输出，以及其时间与内存限制条件究竟是怎样的。

输入队列：RQ需要全部待编码的数据才可以开始工作。这也就意味着在流媒体传输等对数据时效性有着较高要求的应用场景下，使用RQ将比较困难。一旦所有待编码数据都被传入内存，RQ会将其切割成数个数据区块（blocks），这些区块之间的编码与解码相互独立。每个区块进而被分割成数个符号（symbols），而每个符号应当被封入独立的数据包分别进行发送。

字长限制：对一次RQ编码而言，数据最多可被分为256个区块，每个区块最多包含56403个符号，每个符号最大可为65535字节。这意味着RQ内部可以处理的最大数据尺寸为946270874880字节，约为881GiB。

符号交叠：RQ的另一个功能是提供符号交叠（Interleaving）。这意味着一个符号不一定代表了某一段连续的传入数据，而更可能是由数个副符号（sub-symbol）拼接而成的。

符号交叠具体由两个参数控制：副符号字长（sub-symbol size）和副区块大小（sub-block size）。其中，副符号字长必须为输入数据对齐长度（input data alignment，下文会提到）的整数倍。将副符号字长与符号字长设定为相同大小会禁用libRQ的符号交叠功能。

副区块大小也会被用于决定如何将输入数据切割为不同的区块，详情请参照RFC6330文档。（下文也会提及）

内存与时间：由于RQ算法需要在K*K大小的矩阵（K为每个区块中源码符的个数）上进行立方复杂度的运算，因此在使用libRQ时需要开发者考虑内存与时间。libRQ需要在内存中占用两个K*K大小的空间，虽然大多数的操作在其中一个矩阵上完成。

 

II. C++接口

libRQ主要由C++编写，并提供了C++接口。通过C++接口调用libRQ库只需要include “RaptorQ.hpp” 头文件，并在编译时链接libRaptorQ动态库与线程库。C++版本的libRQ可以保证多线程安全，并且在编码和解码时允许采用不同的数据对齐长度进行处理。

*该部分略过。保留此节以提示C++接口存在并相对C接口有一定优势。

 

III. C接口

C接口与C++接口十分相近。使用时需要include “cRaptorQ.h”，并在编译时链接libRaptorQ（-lRaptorQ）。如果需要链接为静态程序，还需要在编译时链接C++标准库（GCC中为libstdc++）、线程库（libpthread）与数学库（libm）。

1. C结构体

typedef enum { NONE = 0 ,
               ENC 8 = 1, ENC 16 = 2, ENC 32 = 3, ENC 64 = 4,
               DEC 8 = 5, DEC 16 = 6, DEC 32 = 7, DEC 64 = 8}
RaptorQ_type;

struct RAPTORQ_LOCAL RaptorQ_ptr
{
    void *ptr = nullptr;
    const RaptorQ_type type;
};

RaptorQ_ptr* RaptorQ_Enc( const RaptorQ_type type, void *data,
                          const uint64_t size,
                          const uint16_t min_subsymbol_size,
                          const uint16_t symbol_size,
                          const size_t max_sub_block);

RaptorQ_ptr* RaptorQ_Dec( const RaptorQ_type type,
                          const RaptorQ_OTI_Common_Data common,
                          const RaptorQ_OTI_Scheme_Specific_Data scheme);

libRQ在编码与解码过程中需要维护一块内存空间以供库内部运算使用。在开始编码（解码）前，需要分别调用RaptorQ_Enc（RaptorQ_Dec）进行初始化。调用RaptorQ_Enc与RaptorQ_Dec时提供的参数向libRQ指定了具体的编码/解码方案。每次调用RaptorQ_Enc/RaptorQ_Dec相当于生成了一个新的libRQ运算实例。调用这两个函数，会返回指向对应运算实例的指针。后续的具体操作都需要传入这个指针，以指示libRQ对哪些数据以何种模式进行怎样的处理。

 

1.1 编码结构体初始化（重要）

为合理使用libRQ，正确地调用RaptorQ_Enc是最重要的一步。调用后所有关于编码的参数就已经确定，不可更改了。具体传入参数如下：

const RaptorQ_type type

该值指定了编码运算传入数据对齐长度，可以选择1字节/2字节/4字节/8字节

void *data, const uint64_t size

提供了指向传入数据的指针，以及传入数据长度。传入数据此在此时需全部在内存    可用。注意：Size单位并非为字节，而是多少个对齐长度。

例：传入数据大小为1024 Bytes，对齐方式选择ENC_32，则size应为：

1024×8/32 = 256 个对齐长度

const uint16_t min_subsymbol_size，const uint16_t symbol_size

最小副符号字长、符号字长，单位为字节（Byte）。

副符号字长不得大于符号字长，两者相等时符号交叠功能被禁用。副符号字长与符号 字长应为对齐长度的整数倍，且符号字长为副符号字长的整数倍。

*一般应用场景下符号长度必定比对齐长度大，因此需要遵守上述规则。当符号长度比 对齐长度小时不需要满足上述要求，具体参考test_c.c

const size_t max_sub_block

最大副区块大小。该值指定了副区块的最大长度，单位为字节（Byte）。

通过调整此值可以间接控制数据区块总数，以及单位区块内符号数。具体参见下文

 

通过直接控制上述参数，可以间接控制如下参数：

– 交叠倍率

交叠倍率表明了每个符号实际由多少个副符号构成。倍率 = 符号字长/副符号字长。

– 区块总数 block count

区块总数表明了传入数据在RQ编码中被分成了多少个部分。

区块数 = Ceiling [传入数据大小 / (最大副区块大小 × 交叠倍率)]

– 实际区块大小

一次编码过程分割的区块大小不都相等，但一定是符号字长的整数倍，故也为对齐长度    的整数倍，且区块大小应在（文件大小/区块总数）上下浮动

– 单位区块符号数 symbol per block

单位区块符号数是影响RQ表现的重要指标。单位区块内符号数量越多，libRQ可生成 的修复码总量就越高，从而保证在高丢包网络环境下的数据重建。在调用libRQ进行编码时，应该保证单位区块符号数至少在数百级别，以保证修复码修复效果足够好、粒度足够低。

单位区块符号数的数量级，可以通过计算(平均区块大小/符号字长)进行估算。

根据以上计算还能发现，在其他参数不变时，仅通过改变副符号字长，就可以实现倍增单位区块符号数、倍减区块总数。通过改变副符号字长将交叠倍率变为原来的n倍时，单位区块符号数升为原来的n倍，区块总数变为原来的1/n倍。

 

1.2 解码结构体的初始化

RaptorQ_Dec负责了初始化解码结构体，在接收方调用。与RaptorQ_Enc不同的是，调用解码结构体时不需要手动传入参数。相对的：

const RaptorQ_type type;

type与编码时相同，指定了对齐长度。需要传入编码时指定长度的DEC版。

如：编码时对齐长度使用了ENC_32，则此时应使用DEC_32

解码对齐与编码对齐长度一样，可以选择1字节/2字节/4字节/8字节

const RaptorQ_OTI_Common_Data common,
const RaptorQ_OTI_Scheme_Specific_Data scheme

这两个值由编码方调用API根据当前编码方式自动生成，并发送给解码方。解码方只 有收到了这两个值才可以确定解码参数，开始解码。

注意：调用RaptorQ_Enc时指定的参数，除了具体数据（*data）外全部相同时， 这两个值也将保持不变。因此以同种模式编码相同长度的不同数据时，不需重复发送   common与scheme。如果应用场景编模式始终固定，可以双方约定common与scheme 而不实际传输这两个值。

 

2. 符号、区块、内存

uint16_t RaptorQ_symbol_size (struct RaptorQ_ptr *ptr);
//传入RQ结构体指针；
//返回符号字长，单位为对对齐长度

uint8_t RaptorQ_blocks (struct RaptorQ_ptr *ptr);
//传入RQ结构体指针；
//返回结构体内数据区块总数

uint32_t RaptorQ_block_size (struct RaptorQ_ptr *ptr, const uint8_t sbn);
//传入RQ结构体指针，区块序号；
//返回对应区块序号的区块大小，单位为对齐长度，不含修复码大小

uint16_t RaptorQ_symbols (struct RaptorQ_ptr *ptr, const uint8_t sbn);
//传入RQ结构体指针，区块序号；
//返回对应区块序号的符号总数，不含修复码

void RaptorQ_free (struct RaptorQ_ptr *ptr);
//传入RQ结构体指针;
//清理libRQ运算占用的内存空间。清理整个结构体也会清理结构体下的全部数据区块

void RaptorQ_free_block (struct RaptorQ_ptr *ptr, const uint8_t sbn);
//传入RQ结构体指针，区块序号；
//清理libRQ在该指定数据区块进行运算所占用的内存空间。

 

 

3. 编码(Encoding)专用函数

uint32_t RaptorQ_max_repair (RaptorQ_ptr *enc, const uint8_t sbn);
//传入初始化为编码的RQ结构体指针，区块序号；
//返回指定区块允许生成的最大修复码数量

void RaptorQ_precompute (struct RaptorQ_ptr *enc, const uint8_t threads, const bool background);
//传入初始化为编码的RQ结构体指针，并行运算线程数量，是否允许在后台运算；
//在初始化结构体后可以调用该预计算函数。调用后将开始（在后台）进行编码计算

size_t RaptorQ_precompute_max_memory (struct RaptorQ_ptr *enc);
//传入初始化为编码的RQ结构体指针；
//返回预估占用内存。用于在调用上述预计算函数前估计将要占用的内存。
uint64_t RaptorQ_encode_id (struct RaptorQ_ptr *enc, void **data, 
                            const uint64_t size, const uint32_t id);
//传入初始化为编码的RQ结构体指针,指向用于写入buffer的指针，符号字长（单位为对齐长度），
//要编码的符号id（前8位为符号所在的区块序号，后24位为区块内符号序号）
//返回实际写入buffer的字长，单位为对齐长度。
/*
调用该函数进行一个符号的编码，使用ID指明需要进行编码的到底是哪个符号。
如果之前调用过RaptorQ_precompute进行了预计算，并且该符号的编码已在后台完成计算，
那么调用encode将不会block。
否则，如果没有调用预计算函数，或者在调用encode时欲取得的符号尚未完成计算，
那么该函数将会block直到编码运算完成。
调用后完成编码的符号将会写入**data，**data的偏移将会变为原偏移+写入长度（指向写入符号的后方）
*/

uint64_t RaptorQ_encode (struct RaptorQ_ptr *enc,
                         void **data,
                         const uint64_ size,
                         const uint32_ esi,
                         const uint8_t sbn);

//传入初始化为编码的RQ结构体指针,指向用于写入buffer的指针，符号字长（单位为对齐长度），
//要编码的符号在其区块内的符号序号，要编码的符号所在的区块序号；
//返回实际写入buffer的字长，单位为对齐长度。

/*
功能与上述RaptorQ_encode_id基本相同，只是指定符号的方式不同。
该函数不使用ID指定要编码的符号，而是直接明示符号所在的区块序号以及其在区块内部的符号序号
*/

uint32_t RaptorQ_id (const uint32_t esi, const uint8_t sbn);
//传入符号序号与区块序号；
//返回符号ID

/*
可以使用该函数，基于符号序号和区块序号建立一个符号ID。实际上，符号ID就是两者的拼接。
符号ID长32位，前8位为区块序号，后24位为符号在区块内的序号。
*/

RaptorQ_OTI_Common_Data RaptorQ_OTI_Common (struct RaptorQ_ptr *enc);
RaptorQ_OTI_Scheme_Specific_Data RaptorQ_OTI_Scheme (struct RaptorQ­_ptr *enc);
//传入初始化为编码的RQ结构体指针;
//分别返回两个OTI数据：common和scheme。
//这两个数据表明了具体的编码模式，需要传送给解码方，对方才可以完成解码。

 

4. 解码(Decoding)专用函数

uint64_t RaptorQ_bytes (struct RaptorQ_ptr *dec);
//传入初始化为解码的RQ结构体指针；
//返回解码后预计还原的解密数据的大小，单位为字节

uint64_t RaptorQ_decode (struct RaptorQ_ptr *dec,
                         void **data,
                         const size_t size);
//传入初始化为解码的RQ结构体指针,指向存储输出的解密数据的指针，输出数据的总大小（单位为对齐长度）
//返回实际写出的解码数据长度，单位为对齐长度
/*
调用该函数进行解码，一次性在整个结构体解码，尝试还原所有数据。
如果数据尺寸很大，或者被切割为多个区块，不建议使用此函数进行解码。
因为如果任何一个区块解码失败，即使其他区块可以解码，函数将会返回失败并且不会生成任何解码数据。
*/

uint64_t RaptorQ_decode_block (struct RaptorQ_ptr *dec,
                               void **data,
                               const size_t size,
                               const uint8_t sbn);
//传入初始化为解码的RQ结构体指针,指向存储输出的解密数据的指针，
//输出数据的总大小（单位为对齐长度）,要进行解码的区块序号
//返回实际写出的解码数据长度，单位为对齐长度
/*
与RaptorQ_decode类似，但是只对一个一个区块进行解码。推荐使用该函数对大块数据进行解码。
因为每个区块解码成功与否的可能相互独立，一个区块解码失败并不会影响其他区块的正常解码。
函数调用后该区块的解码数据将写入**data指向的内存空间，
写入后**data指针便宜变为原偏移+写入数据总量，即为指向解码数据尾部。
*/
bool RaptorQ_add_symbol_id (struct RaptorQ_ptr *dec,
                            void **data,
                            const uint32_t size,
                            const uint32_t id);
//传入初始化为解码的RQ结构体指针，指向待加入解码结构体的符号的指针，
//符号字长（单位为对齐长度），符号ID
//返回是否加入成功。
/*
加入失败有两种可能：
a.解码结构体内已经有相同ID的符号。
b.解码结构体内已经存在一个数据区块全部源码符，而此时想要加入同一区块的修复码。
  如果一个区块的所有源码符都成功传达，那么解码必定成功，不需要修复码
*/

bool RaptorQ_add_symbol (struct RaptorQ_ptr *dec,
                         void **data,
                         const uint32_t size,
                         const uinit32_t esi,
                         const uint8_t sbn);
//传入初始化为解码的RQ结构体指针，指向待加入解码结构体的符号的指针，
//符号字长（单位为对齐长度），该符号在其区块内的符号序号，该符号所在的区块序号；
//返回是否加入成功。
/*
与上述RaptorQ_add_symbol_id功能相近，只是指定符号的方式不同。
该函数不使用ID指定要加入解码结构体的符号，而是直接明示符号所在的区块序号
以及其在区块内部的符号序号。
*/

 

IV. 编解码流程概览

1.   编码

1. 将待传输（待编码）数据全部读入内存，并确定编码参数
2. 调用RaptorQ_Enc初始化编码结构体
3. 调用RaptorQ_OTI_Common和RaptorQ_OTI_Scheme，生成并将两个OTI数据传给解码方
4. 调用RaptorQ_precompute开始进行编码预计算
5. 反复调用RaptorQ_encode或者RaptorQ_encode_id调取编码后的源码符及修复码，并与对应的符号ID一并发送给解码方。
6. 重复(5)直至所有数据传输完成。

注意：调用RaptorQ_encode时，如果指定的esi小于RaptorQ_symbols返回的区块内符号总数，生成的即为源码符；

如果指定的esi大于RaptorQ_symbols返回的区块内符号总数，且小于RaptorQ_max_repair返回的最大允许修复码号，生成的即为修复码。

期间每完成一个区块的传输就可以调用RaptorQ_free_block清除该区块占用的内存空间。全部区块传输完成后调用RaptorQ_free清除整个结构体。

 

2.   解码

1. 获取编码方提供的RaptorQ_OTI_Common和RaptorQ_OTI_Scheme
2. 调用RaptorQ_Dec初始化解码结构体
3. 调用RaptorQ_bytes, RaptorQ_symbol_size, RaptorQ_blocks等，获取相关信息，并为解码分配相应的内存空间
4. 接收符号，并调用RaptorQ_add_symbol_id或者RaptorQ_add_symbol，将收到的符号加入解码结构体。

建议期间跟踪ID以获知是否可以尝试对某一区块进行解码。

当收到足够的符号，足以对某一区块进行解码时，调用RaptorQ_decode_block对该区块进行解码。成功后即可RaptorQ_free_block清除该区块占用的内存空间。

当全部区块解码成功后，调用RaptorQ_free清除整个结构体。

 

附录I.  libRaptorQ的编译

libRaptorQ Library

•     Github：https://github.com/LucaFulchir/libRaptorQ
•     项目主页：https://fenrirproject.org/Luker/libRaptorQ
•     依赖：Eigen3 （repo内自带2.8），LZ4（Git内置模块，或安装独立包）

Python Implementation (用于基本测试)

•     Python 2.x
•     https://pypi.python.org/pypi/libraptorq/17.5.2

注意：编译器需要C++ standard 11的支持 （GNU GCC 4.8+）

 

1.获取源代码

$ git clone https://github.com/LucaFulchir/libRaptorQ.git
$ git checkouot v0.1.9

或

 
$ wget https://github.com/LucaFulchir/libRaptorQ/archive/v0.1.9.tar.gz
$ tar xvf libRaptorQ-0.1.9.tar.gz

2.进入repo根目录修改代码

 
$ cd ./src
$ nano ./Interleaver.hpp

编辑153行

const uint8_t *_raw = nullptr;

删除const后保存退出并返回repo根目录

3. 编译库

 
$ mkdir build
$ cd build
$ cmake -DCMAKE_BUILD_TYPE=Release ../
$ make-j 4

由于库内置test程序本身的问题，编译中途进行的sanity check可能不通过，回报“cannot decode…”。此时重新make理论就可以通过测试，继续完成编译

4. 安装库

编译通过后

 
$ make install

并将库安装目录加入环境变量

$ export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH
# 假设 .so安装位置为 /usr/local/lib

5. 利用python框架进行测试

使用python2 的pip安装python的RQ框架

$ pip install libraptorq

即可在命令行调用rq命令进行基于RaptorQ的加密与解密。具体使用方法见python说明页面