3
开源 C 语言库 Melon:数据恢复算法
source link: https://www.v2ex.com/t/910824
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文讲述开源 C 语言库 Melon 中的里德所罗门纠错码的使用。
关于 Melon 库,这是一个开源的 C 语言库,它具有:开箱即用、无第三方依赖、安装部署简单、中英文文档齐全等优势。
里德所罗门编码是一种纠错码技术,常被用于网络传输丢包恢复、磁盘 RAID 等领域。
关于里德所罗门算法原理的详细讲解,可以参考笔者以前的一篇文章《神奇的数据恢复算法》。
本文将主要利用 Melon 库实现的里德所罗门纠错码模块,配以实例代码,给大家直观展示纠错码的恢复能力。
话不多说,我们上代码,然后进行说明:
#include <stdio.h>
#include <stdlib.h>
#include "mln_core.h"
#include "mln_log.h"
#include "mln_string.h"
#include "mln_rs.h"
int main(int argc, char *argv[])
{
mln_rs_result_t *res, *dres;
char origin[] = "AAABBBCCCDDD";
uint8_t *err[6] = {0};
mln_string_t tmp;
struct mln_core_attr cattr;
cattr.argc = argc;
cattr.argv = argv;
cattr.global_init = NULL;
cattr.master_process = NULL;
cattr.worker_process = NULL;
if (mln_core_init(&cattr) < 0) {
fprintf(stderr, "init failed\n");
return -1;
}
res = mln_rs_encode((uint8_t *)origin, 3, 4, 2);
if (res == NULL) {
mln_log(error, "rs encode failed.\n");
return -1;
}
err[0] = NULL;
err[1] = NULL;
err[2] = (uint8_t *)origin+6;
err[3] = (uint8_t *)origin+9;
err[4] = mln_rs_result_get_data_by_index(res, 4);
err[5] = mln_rs_result_get_data_by_index(res, 5);
dres = mln_rs_decode(err, 3, 4, 2);
if (dres == NULL) {
mln_log(error, "rs decode failed.\n");
return -1;
}
mln_string_nset(&tmp, mln_rs_result_get_data_by_index(dres, 1), 3);
mln_log(debug, "%S\n", &tmp);
mln_rs_result_free(res);
mln_rs_result_free(dres);
return 0;
}
main
中的代码行为如下:
- 定义变量,其中包含了原始数据
origin
,这个一围数组将被当作一个四行三列的矩阵使用。 - 初始化 Melon 库。
- 利用
mln_rs_encode
函数对原始数据origin
这个四行三列的数据生成两个补码包。 - 模拟丢包,即丢弃了
AAA
,BBB
,然后保留了CCC
、DDD
以及两个补码包。注意:数据包的排列顺序要与生成数据时保持一致,丢失的数据要在对应的下标处置NULL
。 - 调用
mln_rs_decode
函数对步骤 4
保留的内容进行数据修复,这里需要传入原始数据的行列数及补码包数量。 - 取得修复出的第二行数据,即
BBB
并输出。 - 释放生成和恢复时的结果数据。
可以看到里德所罗门编码有如下特征:
- 参与计算的数据必须都是等长的,如果不一样长,则要在其后补入数据保持等长。
- 数据恢复时的数据顺序必须与初始 encode 时的顺序保持一致,本例中就是
AAA
、BBB
、CCC
、DDD
。 - 假设原始数据有 M 个,补码包生成 N 个,此时总数据包有 M+N 个,修复数据的要求是:这 M+N 个数据中丢失任意 N 个或少于 N 个,原始数据都可以被恢复。
相较于传统异或的纠错码,这种算法支持了丢失多段数据的修复,但计算开销也会比异或要大一些,因此使用者应该针对自身使用场景进行选择。
欢迎各位对 Melon 感兴趣的读者访问其Github 仓库。
感谢阅读!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK