湘潭做网站价格 磐石网络,seo专员简历,易烊千玺个人网站入口,工程交易服务主页目录#xff1a; 目录#xff1a; 一、base58(58进制) 1.1 什么是base58#xff1f; 1.2 辗转相除法 1.3 base58输出字节数#xff1a; 二、源码分析#xff1a; 2.1源代码#xff1a; 2.2 算法思路介绍#xff1a; 2.2.1 Base58编码过程#xff1a; 2.1.2 Base58解码过… 目录 目录 一、base58(58进制) 1.1 什么是base58 1.2 辗转相除法 1.3 base58输出字节数 二、源码分析 2.1源代码 2.2 算法思路介绍 2.2.1 Base58编码过程 2.1.2 Base58解码过程 2.1.3 Base58Check编码过程 2.1.4 Base58Check解码过程 三、Base58编解码 3.1 Base58 编码函数 encodeBase58 3.2 Base58 解码函数 decodeBase58 3.3 主函数 main 一、base58(58进制)
1.1 什么是base58
Base58编码是在Base64字符集基础上为了避免混淆而进行的优化。它去除了在Base64中可能引起混淆的字符包括数字0、大写字母O、小写字母l、大写字母I以及“”和“/”两个符号。这样的设计使得Base58在视觉上更为清晰减少错误。 Base58采用了一种相当别致的处理方法它并未像Base16或Base64那样规律性的按位处理。相反我们采用了一种称为辗转相除法的处理方式。这种方法虽然与传统方式不同但却同样有效进一步增强了编码的清晰度和可读性。
1.2 辗转相除法
欧几里得算法也称为辗转相除法是一种高效求解两个数最大公约数的方法。这种算法的核心思想在于两个数的最大公约数等于其中较小的数与它们的差的最大公约数。这个算法不仅简洁而且在数学和计算机科学中应用广泛。
Base58编码中字符从1开始映射其中1代表数字02代表数字1一直到z代表数字57。这种映射策略有助于在编码时减少混淆并保持数据的清晰易读。
对于将一个数字转换为Base58编码我们用辗转相除法这可以通过以下步骤来说明
以数字1234为例转换为58进制的过程如下 将1234除以58得到商21和余数16。根据Base58的编码表余数16对应字符H。接着将商21除以58得到商0和余数21。根据Base58的编码表余数21对应字符N。 因此1234在Base58编码中表示为“NH”。
对于数字前有一个或多个0的情况按Base58的编码规则每一个0都直接转换为字符1。例如如果数字是001234那么在Base58编码中它将表示为“11NH”。这里前面的两个0分别转换为两个1紧接着是由1234转换来的“NH”。
1.3 base58输出字节数
在Base58编码中每个字符来自58个可选字符因此每个字符需要表示的位数是log2(58)也即每个字符携带的信息量为log2(58)位。
对于输入的字节数据其长度为(length * 8)位。所以需要预留的字符数量就是(length * 8) / log2(58)。
换句话说为了表示一个字节8位的信息Base58编码需要的字符长度为1 / log2(58)即大约1.38个字符。这意味着每个Base58字符能够表示的信息比二进制编码要多从而提高了编码效率。
二、源码分析
2.1源代码
实现了Base58编码与解码的相关功能包括对输入的字节序列进行Base58编码、对Base58编码的字符串进行解码并且包含了对Base58Check编码的支持这是一种在Base58编码的基础上添加了校验和的编码方式用于提高数据的传输可靠性。
//版权信息 (c) 2014-2022 比特币核心开发者
//在MIT软件许可下分发参见附带的
//复制文件或http://www.opensource.org/licenses/mit-license.php.#include base58.h
#include hash.h
#include uint256.h
#include util/strencodings.h
#include util/string.h
#include assert.h
#include string.h
#include limits// 使用无NUL包含的工具
using util::ContainsNoNUL;/** 所有的字母数字除了 0, I, O, 和 l */
//定义一个Base58编码表
static const char* pszBase58 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz; //定义一个映射表将输入字符映射为对应的整数值
static const int8_t mapBase58[256] { -1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1, 0, 1, 2, 3, 4, 5, 6, 7, 8,-1,-1,-1,-1,-1,-1,-1, 9,10,11,12,13,14,15, 16,-1,17,18,19,20,21,-1,22,23,24,25,26,27,28,29, 30,31,32,-1,-1,-1,-1,-1,-1,33,34,35,36,37,38,39, 40,41,42,43,-1,44,45,46,47,48,49,50,51,52,53,54, 55,56,57,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1, -1,-1,-1,-1,-1,-1,-1,-1,
};// 定义一个函数DecodeBase58用于解码输入的Base58字符串返回转换后的字节序列
[[nodiscard]] static bool DecodeBase58(const char* psz, std::vectorunsigned char vch, int max_ret_len)
{// 跳过前导空格while (*psz IsSpace(*psz))psz;// 跳过并计数前导的1sint zeroes 0;int length 0;while (*psz 1) {zeroes;if (zeroes max_ret_len) return false;psz;}// 在大端base256表示中分配足够的空间int size strlen(psz) * 733 /1000 1; // log(58) / log(256), 向上取整std::vectorunsigned char b256(size);// 处理字符static_assert(std::size(mapBase58) 256, mapBase58.size() should be 256); // 保证不超出范围while (*psz !IsSpace(*psz)) {// 解码base58字符int carry mapBase58[(uint8_t)*psz];if (carry -1) // 无效的b58字符return false;int i 0;for (std::vectorunsigned char::reverse_iterator it b256.rbegin(); (carry ! 0 || i length) (it ! b256.rend()); it, i) {carry 58 * (*it);*it carry % 256;carry / 256;}assert(carry 0);length i;if (length zeroes max_ret_len) return false;psz;}// 跳过后导空格while (IsSpace(*psz))psz;if (*psz ! 0)return false;// 跳过b256中的前导零std::vectorunsigned char::iterator it b256.begin() (size - length);// 将结果复制到输出向量vch.reserve(zeroes (b256.end() - it));vch.assign(zeroes, 0x00);while (it ! b256.end())vch.push_back(*(it));return true;
}// 定义一个函数EncodeBase58用于将输入的字节序列编码为Base58字符串
std::string EncodeBase58(Spanconst unsigned char input)
{// 跳过和计数前导零int zeroes 0;int length 0;while (input.size() 0 input[0] 0) {input input.subspan(1);zeroes;}// 在大端base58表示中分配足够的空间int size input.size() * 138 / 100 1; // log(256) / log(58), 向上取整std::vectorunsigned char b58(size);// 处理字节while (input.size() 0) {int carry input[0];int i 0;// 应用 b58 b58 * 256 ch for (std::vectorunsigned char::reverse_iterator it b58.rbegin(); (carry ! 0 || i length) (it ! b58.rend()); it, i) {carry 256 * (*it);*it carry % 58;carry / 58;}assert(carry 0);length i;input input.subspan(1);}// 在base58结果中跳过前导零std::vectorunsigned char::iterator it b58.begin() (size - length);while (it ! b58.end() *it 0)it;// 将结果转化为字符串std::string str;str.reserve(zeroes (b58.end() - it));str.assign(zeroes, 1);while (it ! b58.end())str pszBase58[*(it)];return str;
}// 定义一个函数DecodeBase58用于解码输入的Base58字符串返回转换后的字节序列
bool DecodeBase58(const std::string str, std::vectorunsigned char vchRet, int max_ret_len)
{if (!ContainsNoNUL(str)) {return false;}return DecodeBase58(str.c_str(), vchRet, max_ret_len);
}// 定义一个函数EncodeBase58Check用于将输入的字节序列编码为添加了4字节hash校验的Base58字符串
std::string EncodeBase58Check(Spanconst unsigned char input)
{// 在结束处添加4字节的hash校验std::vectorunsigned char vch(input.begin(), input.end());uint256 hash Hash(vch);vch.insert(vch.end(), (unsigned char*)hash, (unsigned char*)hash 4);return EncodeBase58(vch);
}[[nodiscard]] static bool DecodeBase58Check(const char* psz, std::vectorunsigned char vchRet, int max_ret_len)
{if (!DecodeBase58(psz, vchRet, max_ret_len std::numeric_limitsint::max() - 4 ? std::numeric_limitsint::max() : max_ret_len 4) ||(vchRet.size() 4)) {vchRet.clear();return false;}// 重新计算校验和确保它匹配包含的4字节校验和uint256 hash Hash(Span{vchRet}.first(vchRet.size() - 4));if (memcmp(hash, vchRet[vchRet.size() - 4], 4) ! 0) {vchRet.clear();return false;}vchRet.resize(vchRet.size() - 4);return true;
}bool DecodeBase58Check(const std::string str, std::vectorunsigned char vchRet, int max_ret)
{if (!ContainsNoNUL(str)) {return false;}return DecodeBase58Check(str.c_str(), vchRet, max_ret);
}2.2 算法思路介绍
Base58编码是一种常用于加密货币地址和某些区块链应用中的编码方式它使用了58个字符排除了容易混淆的字符如0零、O大写的o、I大写的i和l小写的L以提供一种相对于Base64更容易人工阅读和手写的编码系统。
2.2.1 Base58编码过程
计算输入数据的大小输入数据通常是一串字节首先被评估以确定其长度和所需的编码空间大小。处理前导零Base58编码保留了输入数据中的前导零字节0x00每个前导零字节在编码字符串中用字符1表示。转换为Base58剩余的输入数据被转换为一个大整数然后这个大整数被转换成Base58表示即通过不断除以58并取余数的方式获得一系列的Base58字符。拼接结果最终的编码字符串由步骤2中处理的前导零每个零用1表示和步骤3的转换结果组成。
2.1.2 Base58解码过程
校验并移除前导1解码首先会检查编码字符串中前导的1字符并记录其数量因为每个1代表一个前导零字节。Base58到大整数然后将Base58编码字符串转换回一个大整数即通过对每个Base58字符进行查表操作获取对应的数值并将这些数值以58为基数合并成一个大整数。转换为字节序列这个大整数随后被转换回原始的字节序列。重建前导零根据步骤1中记录的前导1的数量在解码后的字节序列前加上相应数量的零字节。
2.1.3 Base58Check编码过程
Base58Check是在Base58的基础上增加了错误检测的能力。它通常包括以下几个步骤
计算校验和对输入数据计算校验和如通过SHA-256算法计算两次取前四个字节作为校验和。添加校验和将这个校验和添加到原始数据的末尾。Base58编码将步骤2得到的字节序列进行Base58编码。
2.1.4 Base58Check解码过程
Base58解码首先对编码字符串进行Base58解码。验证校验和从解码结果中提取末尾四个字节作为校验和与剩余数据重新计算的校验和进行比较。提取数据如果校验和匹配说明数据未被篡改去掉末尾四个字节的校验和返回剩余的数据部分。
这些步骤中对前导零的特殊处理编码中的1字符和解码时的零字节是Base58和Base58Check编码的一个重要特性确保了编码结果的唯一性和解码的准确性。
三、Base58编解码
Base58编码和解码的实现。Base58是一种用于比特币等加密货币中的编码方案它避开了某些视觉上容易混淆的字符比如0数字零、O大写字母O、I大写字母I和l小写字母L。
#include iostream
#include string
#include vector
#include algorithm// 定义Base58编码的字符集
static const std::string BASE58_ALPHABET 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz;// Base58编码函数
std::string encodeBase58(const unsigned char* input, size_t len) {std::vectorunsigned int digits(40, 0); // 用于存储Base58表示的向量初始全为0size_t digits_len 1; // 有效位数长度初始为1// 对输入数据的每个字节进行处理for (size_t i 0; i len; i) {unsigned int carry input[i]; // 当前字节值for (size_t j 0; j digits_len; j) {carry digits[j] * 256; // 将当前值加到之前的结果digits[j] carry % 58; // 计算Base58的当前位carry / 58; // 更新进位}// 处理剩余的进位while (carry) {digits[digits_len] carry % 58;carry / 58;}}std::string output;// 处理前导0的特殊情况Base58用1表示前导0for (int i 0; i len input[i] 0; i) {output 1;}// 将计算得到的Base58位数转换为字符for (size_t i 0; i digits_len; i) {output BASE58_ALPHABET[digits[digits_len - 1 - i]];}return output; // 返回编码后的字符串
}// Base58解码函数
std::vectorunsigned char decodeBase58(const std::string input) {std::vectorunsigned char output; // 初始化输出向量// 对输入的每个字符进行处理for (size_t i 0; i input.length(); i) {int value BASE58_ALPHABET.find(input[i]); // 查找字符在Base58字符集中的位置if (value std::string::npos) {// 如果字符不在Base58字符集中返回空向量表示解码失败return {};}for (size_t j 0; j output.size(); j) {value output[j] * 58; // 更新当前位output[j] value % 256; // 计算当前位的值value / 256; // 更新进位}// 处理剩余的进位while (value) {output.push_back(value % 256);value / 256;}}// 处理前导1的特殊情况对应前导0字节for (size_t i 0; i input.length() input[i] 1; i) {output.push_back(0);}// 逆转输出向量以匹配原始输入的顺序std::reverse(output.begin(), output.end());return output; // 返回解码后的字节向量
}int main() {const std::string input_data Hello, world!; // 要编码的输入数据std::cout 原始数据 input_data \n;// 调用编码函数std::string encoded encodeBase58(reinterpret_castconst unsigned char*(input_data.data()), input_data.size());std::cout Encoded编码后: encoded \n;// 调用解码函数std::vectorunsigned char decoded decodeBase58(encoded);std::string decodedStr(decoded.begin(), decoded.end());std::cout Decoded解码后: decodedStr \n;return 0; // 返回0表示程序成功执行
}3.1 Base58 编码函数 encodeBase58
这个函数用于将字节数组编码为Base58字符串。
输入: const unsigned char* input, size_t len表示输入的字节数组及其长度。处理: 使用一个vectorunsigned int来临时存储计算的数字这个向量的长度被初始化为40足以处理常见的输入长度。通过多重循环将输入的字节转换为Base58编码。内部逻辑处理了进位这对于任何基数的转换都是必需的。处理前导0因为Base58编码中前导0用1字符表示。
3.2 Base58 解码函数 decodeBase58
这个函数用于将Base58编码的字符串解码回原始的字节数据。
输入: const std::string inputBase58编码的字符串。处理: 初始化一个动态大小的vectorunsigned char用于存储解码的结果。遍历输入的每一个字符找出其在Base58字符集中的索引这个索引值代表了其对应的数值。通过计算和处理进位将Base58编码转换回字节。处理Base58编码中的前导1这些1在解码时应转换为前导0字节。最后由于解码过程中字节被逆向存储需要将结果向量反转以恢复初始的字节顺序。
3.3 主函数 main
功能: 测试encodeBase58和decodeBase58函数使用字符串Hello, world!作为输入。输出: 显示原始数据。显示编码后的Base58字符串。显示解码后的字符串应与原始输入相同。
