V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
monkeyNik
V2EX  ›  C

开源 C 语言库 Melon:数据恢复算法

  •  
  •   monkeyNik · 2023-01-27 11:18:17 +08:00 · 914 次点击
    这是一个创建于 426 天前的主题,其中的信息可能已经有所发展或是发生改变。

    本文讲述开源 C 语言库 Melon 中的里德所罗门纠错码的使用。

    关于 Melon 库,这是一个开源的 C 语言库,它具有:开箱即用、无第三方依赖、安装部署简单、中英文文档齐全等优势。

    Github repo

    简介

    里德所罗门编码是一种纠错码技术,常被用于网络传输丢包恢复、磁盘 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中的代码行为如下:

    1. 定义变量,其中包含了原始数据origin,这个一围数组将被当作一个四行三列的矩阵使用。
    2. 初始化 Melon 库。
    3. 利用mln_rs_encode函数对原始数据origin这个四行三列的数据生成两个补码包。
    4. 模拟丢包,即丢弃了AAA, BBB,然后保留了CCCDDD以及两个补码包。注意:数据包的排列顺序要与生成数据时保持一致,丢失的数据要在对应的下标处置NULL
    5. 调用mln_rs_decode函数对步骤 4保留的内容进行数据修复,这里需要传入原始数据的行列数及补码包数量。
    6. 取得修复出的第二行数据,即BBB并输出。
    7. 释放生成和恢复时的结果数据。

    结语

    可以看到里德所罗门编码有如下特征:

    1. 参与计算的数据必须都是等长的,如果不一样长,则要在其后补入数据保持等长。
    2. 数据恢复时的数据顺序必须与初始 encode 时的顺序保持一致,本例中就是AAABBBCCCDDD
    3. 假设原始数据有 M 个,补码包生成 N 个,此时总数据包有 M+N 个,修复数据的要求是:这 M+N 个数据中丢失任意 N 个或少于 N 个,原始数据都可以被恢复。

    相较于传统异或的纠错码,这种算法支持了丢失多段数据的修复,但计算开销也会比异或要大一些,因此使用者应该针对自身使用场景进行选择。

    欢迎各位对 Melon 感兴趣的读者访问其Github 仓库

    感谢阅读!

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3265 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 11:29 · PVG 19:29 · LAX 04:29 · JFK 07:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.