本文共 4344 字，大约阅读时间需要 14 分钟。

GF-Complete 是一个开源、综合性的伽罗瓦运算库，相应的文章发表在FAST13 中（见参考文献【1】）。作者是大名鼎鼎的Jim Plank 教授，作为开源纠错码库Jerasure 的开发者，在这个伽罗瓦运算库中创新地采用了SSE 指令集来加速纠错码运算的瓶颈---伽罗瓦运算中的乘法运算，并采用了其他运算方法，综合得到GF-Complete。该库可在Plank 主页中下载得到，下面就GF-Complete 库做简要分析，详细可参考文档【2】。   一、文件的组成 GF-Complete 有以下文件： 1. gf_complete.h 是应用程序使用的的头文件，所有的其他源程序将生成各自的 .o 文件，所有的 .o 文件将被打包为gf_complete.a ，供应用程序使用。gf_complete.h 包含了通用的数据类型gf_t （GF(2w) 中所有值得类型）和其他运算接口； 2. gf_general.h 中包含了不同大小w 的伽罗瓦域基础运算，尽力消除不同w 大小带来不同数据类型运算的痛苦。文件gf_wgen.c / gf_w4.c / gf_w16.c / gf_w32.c / gf_w64.c / gf_w128.c 分别对应着w<32 / w=4,8,16,32,64,128 的基础运算（加法，乘法，除法，乘2等）； 3. gf_rand.h 和gf_rand.c 是一个随机数生成器； 4. gf_int.h 定义了gf_w** 需要使用的一些初始化函数和其他类型；   下面几个文件并不是该库所必须的，主要用于测试和例子： 6. gf_mult.c / gf_div.c  / gf_add.c 分别是域上的单个乘法/除法/加法工具； 7. whats_my_sse.c 是用于查看该机器支持哪些指令集，直接通过gcc 可编译； 2. gf_method.h 和 gf_method.c 是用来帮助用户知道自己可以使用的方法（不同处理器支持的指令集不同）； 8. gf_time.c / gf_uint.c / gf_ploy.c 分别用于测试速度，单元测试和域中寻找本原多项式； 9. gf_example_1/2/3/4 分别对应着伽罗瓦域上的单个乘法和除法、一块区域乘以一个常量、w=64 的常用运算，w=128 的常用运算测试；   二、gf_time gf_time 是其中一个最重要的测试速度的工具，命令格式如下： UNIX>gf_time w tests seed buffer-size iterations method 其中w 是位长，大于零小于等于32，或者为64 和128；seed 是用于随机数的种子；buffer-size 为每次运算的区域的大小，iterations 为循环次数（用于测速）；最重要的两个参数是tests 和 method，tests 指测试的选项，有以下几种： ‘M’ 单个乘法计算 ‘D’ 单个除法计算  ‘I’    单个元素转置 ‘G’  一个随机常量乘以一块区域 ‘0’ 零乘以一块区域（等同于bzero()） ‘1’ 一乘以一块区域（等同于memcpy() 和 XOR） ‘2’ 二乘以一块区域，这比一般的乘二运算要快（通过移位实现） ‘S’ 所有三种单个测试‘M’，‘D’，‘I’ ‘R’ 所有四个区域测试‘G’，‘0’，‘1’，‘2’ ‘A’ 所有七个测试 method 是伽罗瓦域上计算采用的技术（取决于机器支持的指令集，现有的伽罗瓦域运算方法和位长w ），通过gf_method 可以查询到对应机器支持的方法，gf_method 有三部分组成：乘法方法，区域乘法方法和除法方法。 乘法对应有以下方法：  ‘TABLE’          乘法表  ‘LOG’              对数表 ‘LOG_ZERO’ 类似于对数表  ‘SHIFT’           通过不可约多项式进行移位乘法，速度很慢，参考【3】  ‘BYTWO_p’    通过循环乘二并选择性异或被乘数得到乘法结果，可以利用到Anvin 乘二的优化  ‘BYTWO_b’    同上  ‘SPLIT’            乘法裂表（比如LR表，或者利用SIMD 的表，详见【1】）分别有wa 和wb 两个参数  ‘GROUP’         使用左右组合表的方法（参考文献【4】）  ‘COMPOSITE’在一个组合域上进行运算，GF((2l)k) 在参考文献【3】、【4】有介绍 区域乘法有以下方法：  ‘-’              使用默认方法  ‘LAZY’      区域乘法前生成查询表  ‘SSE’        如果有SSE4 指令集，则使用 ‘NOSSE’ 不使用SSE4 指令集 ‘SINGLE’ 每次查询一个元素运算的表 ‘DOUBLE’每次查询两个元素运算的表  ‘QUAD’     每次查询四个元素运算的表，‘SINGLE’是一般的查询表，之所以有另外两个表，是为了加速较小w 的运算，达到内存使用和计算的均衡 ‘STDMAP’使用标准字位对其，内存块分割为连续的字 ‘ALTMAP’非标准字位对其，每个字分割在不同的内存块中 ‘CAUCHY’将内存分为w 块且仅进行Cauchy Reed-Solomon 中的异或运算【5】 除法有以下方法选择：  ‘-’               使用默认方法 ‘EUCLID’ 使用欧几里得算法，方法慢，但允许使用乘法进行除法计算 ‘MATRIX’  将每个元素转化为w×w 大小的bit-matrix（像在Cauchy Reed-Solomon 中），然后转置该矩阵得到逆元素 三、字长和选项 w = 4： “BYTWO_b SSE -”是默认的区域运算的一半速度，几乎和乘二一样快，但单个运算慢； “BYTWO_b NOSSE -”是不使用SSE4 指令最快的区域运算方法； “TABLE QUAD -”是不使用SSE 指令，基于查询表最快的方法； w = 8： 默认下速度最快 w = 16： “SPLIT 16 4 SSE,ALTMAP -”这是w = 16时最快的区域乘法，关于这部分算法可以参考【2】 “BYTWO_b SSE -” 这对于区域乘二是最快的选项，但其他乘法就慢了 w = 32： “SPLIT 32 4 SSE,ALTMAP -” 和w = 16一样，这个比默认方法要快 “SPLIT 8 8 - -” 单个乘法最好的选择，但要预分配1.75MB 内存 “BYTWO_b SSE -” 乘二非常快 “SPLIT 32 8 - -” 不使用SSE4 指令集最快的区域乘法，不使用1.75MB 内存 “COMPOSITE 2 1 SPLIT 16 4 SSE,ALTMAP - ALTMAP -” 对于较大的w，组合（composite）操作是最好的方法，但对于单个乘法计算不友好 w = 64： “SPLIT 64 4 SSE,ALTMAP -” 这是最快的区域运算，采用128个不同的查找表，单个运算慢，建议使用默认方法 “COMPOSITE 2 1 SPLIT 32 4 SSE,ALTMAP - ALTMAP -”  区域运算也很快 “BYTWO_b SSE -” 这一直是区域乘二的最快方法 w = 128： “SPLIT 128 4 - -” 方法尚不完善，这是暂时最快的方法 “BYTWO_b - - ”最快的区域乘二   三、源码分析 先看几个 .h头文件（gf_complete.h 包含于gf_general.h 和gf_int.h 中）定义了一些数据结构： gf_general_t  (gf_general.h)代表伽罗瓦域中元素类型，减少w 不同带来不同数据类型运算的痛苦；  1: typedef union {   2: uint32_t w32;   3: uint64_t w64;   4: uint64_t w128[2];   5: } gf_general_t;    gf_internal_t  (gf_int.h)代表伽罗瓦运算，包含了运算指定的类型和参数；  1: typedef struct {   2: int mult_type;   3: int region_type;   4: int divide_type;   5: int w;   6: uint64_t prim_poly;   7: int free_me;   8: int arg1;   9: int arg2;   10: gf_t *base_gf;   11: void *private;   12: } gf_internal_t;    gf_region_data  (gf_int.h)代表一块要进行区域乘法计算的内存块；  1: typedef struct {   2: gf_t *gf;   3: void *src;   4: void *dest;   5: int bytes;   6: uint64_t val;   7: int xor;   8: int align;   9: void *s_start;   10: void *d_start;   11: void *s_top;   12: void *d_top;   13: } gf_region_data;    gf_val_32_t , gf_val_64_t , gf_val_128_t 分别作为w = 32、64、128时伽罗瓦域中的元素类型，是uint32_t，uint64_t 和uint64_t * 的别名。 gf_func_a_b 是两个元素乘法或除法的函数指针，对于不同w 有三种函数指针； gf_func_a     是一个元素求逆的函数指针 gf_func_region 是一个元素乘以一个区域的函数指针 gf_t  是一个伽罗瓦域运算的结构体，某个gf_t的实例（且允许我这么说）代表了一个伽罗瓦域的运算方法  1: typedef struct gf {   2: gf_func_a_b multiply;   3: gf_func_a_b divide;   4: gf_func_a inverse;   5: gf_region multiply_region;   6: gf_extract extract_word;   7: void *scratch;   8: } gf_t;  这些结构通过gf_free 释放空间  但一个应用程序调用这些方法时，需要指定参数进行初始化，比如生成查找表等，这些可以通过gf_init_easy() 和gf_init_hard()，前者是后者的一个默认参数的选择，如果手动选择参数调用后者即可。也可以通过提供的create_gf_from_argv(&gf, w, argc, argv, 6) 通过手动输入参数进行初始化。

转载地址：http://ougmb.baihongyu.com/