Programming
17 posts
图片来源：Easy Diffusion 生成（参数）， Aseprite 编辑 回文字符串 简单来说就是左右对称的字符串，比如 aba、abba 都是回文字符串。 寻找最长回文子串是很经典的问题，比如 bananas 的最长回文子串就是 anana （LeetCode 上对应的题目 longest-palindromic-substring） 暴力计算（O(n2)） 一个简单的想法是，对于字符串里的一个字符 c： 显然上面的想法会漏掉偶数长度的回文串（比如 cabba ，无论以哪个字符为中心开始找都得不到 abba），我们可以通过插入额外字符来把所有偶数长度的回文串转化为奇数长度，比如我们插入字符 | ，把 cabba 转化为 |c|a|b|b|a| 马拉车算法（O(n)） 马拉车算法其实上面的想法差不多，也是尝试以每一个字符为中心查找局部的最长回文串，不同的是马拉车算法利用来回文串左右对称的特点减少来大量计算 以右边字符串为例子，为方便理解，假设我们已经的计算已经来到了字符 x n m y c v c y c x c y c v c z w 对于 x 左边的任意一个字符，我们都已经计算过并记录了以该字符为中心的最长回文字符串，比如对于 x 左边的第一个 y ，我们知道他的最长回文字符串为 cyc n m y c v c y c x c y c v c z w 现在依次比较 x 两边的字符，经过 6 次比较后，我们确定了以 x 为中心的最长回文字符串 cvcycxcycvc ，为了方便后续说明，我们记作 x回 n m y c v c y c x c y c v c z w 此时如果是暴力计算的话会直接进入下一个循环，但其实可以利用回文字符串的对称性直接算出 x 右边的字符（绿色部分）的最长回文字符串 n m y c v c y c x c y c v c z w （情况 1）对于 x […]
图片来源：Easy Diffusion，参数 在 bittorrent 中， tracker 是组织或个人提供的一个中心化的服务，tracker 服务器 URL 包含在种子文件（.torrent）的 announce 或 announce-list 字段中，bittorrent 客户端通过 HTTP GET 请求向服务端发送本地信息，并从服务器获取其他客户端的信息。 Tracker 请求 以下是 HTTP GET 请求 URL 中的参数： 参数 必要 含义 info_hash 是 种子文件中 info 字段值（bencode编码的字典）的 SHA1 校验和（20字节），种子文件结构查看 这里 peer_id 是 20字节 ，用以识别客户端的唯一 ID，可以是任意值（可见字符或二进制数据），应当在客户端启动时生成 port 是 客户端监听端口号，通常是6881-6889（如果客户端无法在该端口范围内监听，应当主动放弃） event 否 值必须为 started、stopped 或 completed。客户端对 tracker 的第一次请求中应当包含 event=stared ；客户端正常关闭时应当向 tracker 发送 event=stopped ；客户端完成下载时应当向 tracker 发送 event=completed （不要重复发送 event=completed ，tracker 使用该信息统计完成的客户端数量） uploaded 是 使用 ASCII 码表示的十进制数字，表示 event=stared 发送后上传的字节数（官方没标单位，但通常为字节） downloaded 是 使用 ASCII 码表示的十进制数字，表示 event=stared 发送后下载的字节数（官方没标单位，但通常为字节） left 是 使用 ASCII 码表示的十进制数字，未下载的字节数 compact 是 值为 1 时，服务器响应使用更加紧凑的节点格式（6字节 IPv4 地址或 16字节 IPv6 地址，后2字节为端口，均使用网络序）。注意，官方建议 tracker 默认使用 compact 格式，并且该参数对 tracker 服务器来说只是个建议，即使发送 compact=0，tracker 服务器也可以忽略或拒绝响应 no_peer_id 否 指示服务器响应中的 peers 字典不必包含 peer id ，使用 compact=1 时自动忽略该选项 ip 否 客户端所在机器的真实 IP 地址，客户端通过代理与 tracker 服务器连接时需要该参数提供真实 […]
图片来源：https://www.pixiv.net/artworks/113139569 整个 .torrent 文件实际上就是一个包含了约定字段的 bencode 编码字典， bencode 编码规则见 https://blog.geekgo.tech/programming/bencode/ 顶层字段 字段（含空格） 类型 必要 含义 info Dictionary 是 包含文件信息的字典，详细结构见下文 announce String 否 tracker 的 URL announce-list List 否 额外 tracker，列表的每个元素都是一个字符串列表，每个字符串都是一个 tracker 的 URL （另外官方文档里对这些 tracker 的处理顺序有一些要求，详情见 这里） creation date Integer 否 种子创建时间（Unix 时间戳） comment String 否 没有格式要求的文本备注 created by String 否 创建种子的程序名称和版本（实际也可以填任意其他内容） encoding String 否 未在官方文档中找到定义，似乎是字符串编码，值多为 UTF-8，但 The BitTorrent Protocol Specification 已经明确了 “All strings in a .torrent file that contains text must be UTF-8 encoded.”。这里 的解释是 “the string encoding format used to generate the pieces part of the info dictionary in the .torrent metafile ” httpseeds List 否 每个元素是一个 URL，通过在 URL 后添加参数可以直接从这些网站下载需要的 torrent 数据，详见 这里 info 字典结构 info 的结构分为单文件和多文件两种情况 单文件 字段（含空格） 类型 必要 含义 name String 是 文件名 length Integer 是 […]
图片来源：https://www.pixiv.net/artworks/103204899 类型 描述 bencode 原始值 String 以字符串长度为前缀，后跟冒号和字符串 4:spam spam Integer 以 i 为前缀，后跟十进制数字，以 e 为后缀 i3ei-3ei0e 3-30 List 以 l 为前缀，后跟使用 bencode 编码过的元素，以 e 为后缀 l4:spam4:eggse ['spam', 'eggs'] Dictionary 以 d 为前缀，后跟使用 bencode 编码过的元素，每两个元素为一组 key:value，以 e 为后缀（ key 必须为 String 并按原始字符串的字典顺序排列） d3:cow3:moo4:spam4:eggse d4:spaml1:a1:bee {'cow': 'moo', 'spam': 'eggs'} {'spam': ['a', 'b']} 参考：
图片来源：《灵笼》特别篇截图 方案一：继承 std::streambuf 详细解释查看 《C++标准库：第2版》 15.13章节 输出流（没有缓冲区） 在不考虑缓冲区的情况下，继承 std::streambuf 并重写两个函数 ： 输出流（有缓冲区） 考虑缓冲区的话，需要： 输入流 输入流需要考虑支持回退（basic_istream& unget()），重写 virtual int_type underflow () 函数用以从文件描述符中读取数据到缓冲区，缓冲区前 4 字节保存可回退数据 方案二：使用 __gnu_cxx::stdio_filebuf stdio_filebuf 支持使用文件描述符或者C文件指针（std::__c_file * 即 FILE *）构造，部分构造函数： 使用示例： 注意：对于文件描述符，stdio_filebuf 在析构时会主动调用 close ；但对于 FILE * 则不会主动关闭，需要手动调用 fclose 方案三：使用 boost::iostreams::file_descriptor_source 和 boost::iostreams::file_descriptor_sink boost 的 file_descriptor_source 和 file_descriptor_sink 可以使用文件描述符来构造，继而构造出 boost::iostreams::stream ，部分构造函数： 其中 file_descriptor_source 只能从文件描述符读取数据，file_descriptor_sink 则只能写入数据，file_descriptor_flags 用以控制析构时是否自动关闭文件描述符 参考： 《C++标准库：第2版》 __gnu_cxx::stdio_filebuf< _CharT, _Traits >(3) —— man page File Descriptors —— boost
图片来源：https://www.pixiv.net/en/artworks/65883716 TL;DR 语法 含义 const T* 指向 const 对象的指针 T* const 指向对象的 const 指针 const T* const 指向 const 对象的 const 指针 吐槽“指针常量”和“常量指针” 这两个概念本身的含义都很简单，但所谓“指针常量”和“常量指针”的说法却将这两个概念理解和记忆难度成倍提升了。每当只看这两个中文，想要“顾名思义”的时候，我总会陷入混乱： 常量指针： 既可以理解为指向某个常量的指针（const T *），也可以理解为“常量”是对“指针”的修饰（T *const） 指针常量： 这个倒没什么歧义，像“整型常量”一样去理解就行，但定义语法看起来却又和整型常量完全不同：整形常量（const int）, 指针常量（int *const） 当然如果只是以上这样，只要能做到概念统一的话那倒也没什么，权当我自己脑抽了，但好死不死《C++ Primer中文版（第5版）》里对这两个概念的英文直译又和百度百科里的定义完全相反 百度百科的定义 常量指针：const T * 指针常量：T * const 《C++ Primer》里的定义 指向常量的指针（pointer to const）：const T * 常量指针（const pointer）：T * const 另外，如果采用“指针常量”和“常量指针”的说法，当遇到“const T * const”时，是不是该叫“常量指针常量”😅（当然网上看到的说法大多为“指向常量的常指针”、“指向常量的指针常量”） 官方文档里的定义 当前的C++官方文档“指针声明”这一章的中文翻译里并没有上面这两个说法，取而代之的是“指向 const 对象的指针（pointer to constant object）”和“指向对象的 const 指针（constant pointer to object）” 指向 const 对象的指针：指针变量本身可以修改（即可以指向不同对象），但不能修改“指向的对象”里的内容（即对于指针p来说, “p = &a”可行，“*p = a”不可行） 指向对象的 const 指针：指针变量本身初始化后不可再修改（即不能指向其他对象），但可以修改“指向的对象”里的内容（即对于指针p来说, “p = &a”不可行，“*p = a”可行） 语法 含义 const T* 指向 const 对象的指针 T const* 指向 const 对象的指针 T* const 指向对象的 const 指针 const T* const 指向 const 对象的 const 指针 T const* const 指向 const 对象的 const 指针 指针声明语法 […]
图片来源：https://www.pixiv.net/artworks/72641025 Meyer’s Singleton 利用C++11保证静态局部变量初始化线程安全的特性 或许有用的模板实现 相对灵活，能够返回任意类型的固定对象指针，通过重载运算符略微增加复制语句的复杂度，但并不能阻止类型本身对象的复制 可以像这样复制T类型对象内容 参考：
图片来源：https://www.pixiv.net/artworks/101597578 大端序（网络序）：高字节在低地址 小端序：高字节在高地址 判断当前运行环境的字节序 C++ 通过自定义变量值判断 另外，C++标准中对于结构体的非活跃成员的访问属于未定义行为，虽然使用g++编译运行都没问题，但以下代码不能保证运行结果正确 使用GCC宏 C++20标准库已经内置了字节序相关变量 Shell 输出“1”则为小端序，输出“0”则为大端序 查看CPU参数 CPU相关信息里的“Byte Order”字段有字节序信息 转换 Linux函数 Shell 反转字节序，输入输出均为十进制数 参考：
图片来源：https://www.pixiv.net/artworks/81470216 预备知识 算术右移 算术右移会保留符号位（或者填充符号位），这样可以保证左移一位等于除以2 ，算术上符合直觉；但如果只是观察bit位变化，对于负数来说，算术右移看起来就是不断在左边填充“1”，和其他位移操作相比，显得不那么符合直觉（无符号数左移/右移、正数算术左移/右移、负数算术左移都可以理解为填充“0”）。 C++ 20 明确规定了对于有符号数的右移为算术右移，C++ 20 前虽没明确规定，但大多编译器的实现上也是算术右移： For negative a, the value of a >> b is implementation-defined (in most implementations, this performs arithmetic right shift, so that the result remains negative). (until C++20) The value of a >> b is a/2b, rounded down (in other words, right shift on signed a is arithmetic right shift). (since C++20) Arithmetic operators 隐式类型转换 C++ 算术运算符不接受小于“int”的类型，所以位移运算前会把 signed char 转换成 int ，unsigned char 转换成 unsigned int 。观察bit位变化，对于无符号数和有符号正数来说，转换后额外bit位填充的是“0” ，对于负数来说转换后额外bit位填充的是“1”。 循环位移模板实现（C++ 20） 参考：
图片来源：https://www.pixiv.net/artworks/100578118 C 取模 C语言的取模运算符（%）仅支持整数，定义如下： 对于 a/b ， C语言会自动截断计算结果的小数部分， C99规定了”趋零截断”，举个例子 2.14 会截断为 2 ， -2.14 会截断为 -2 。 简单来讲，C语言取模结果的符号（正数还是负数）与 a 的符号相同 Lua 取模 Lua取模操作有两种 % 和 math.fmod() ，稍微有一点区别： “//” 在lua中称为floor除法（floor division），会将运算结果向负无穷取整（rounds the quotient towards minus infinity），举个例子 2.14 会截断为 2.0 ， -2.14 会截断为 -3.0。需要注意的两点： 参考：
图片来源：《魔法使之夜》游戏截图 无互联网指使用VSCode的Windows和Linux未连接互联网，但至少能通过某些途径把下载好的安装包传到Windows里安装 安装官方Git客户端 访问https://git-scm.com/download/windows下载git客户端并安装，安装这个主要是偷懒，要用的是“Git Bash”和SSH相关工具， 安装VSCode Windows客户端安装 访问https://code.visualstudio.com/Download下载VSCode客户端并安装 安装Remote-SSH插件 访问https://marketplace.visualstudio.com/items?itemName=ms-vscode-remote.remote-ssh, 界面右边可以下载插件安装包 进入VSCode的插件界面（左边工具栏第5个），直接用鼠标把插件安装包拖进去安装，或者点击“…”，选择“Install from VSIX…”安装 其他插件 大部分插件到https://marketplace.visualstudio.com/上手动下载安装即可，一些插件的windows端和linux端程序有一定区别（比如微软官方的C/C++插件），请根据需要下载不同版本 Linux服务端安装 在有互联网的情况下，客户端第一次连接会自动给Linux下载服务端程序，但没有互联网的情况下，需要手动完成 获取服务端安装包 首先需要尝试第一次连接，虽然必定会失败，但可以从连接报错信息看到下载服务端程序所需要的“commit id” 按快捷键“Ctrl + Shift + P ”, 搜索“connect”，选择“Remote-SSH:Connect Current Window to Host…” 添加后，再重复一遍操作，按快捷键“Ctrl + Shift + P ”, 搜索“connect”，选择“Remote-SSH:Connect Current Window to Host…” 此时会多一个刚刚添加服务器，选择之后按提示操作即可 第一次连接一定会失败，可以从连接报错信息看到之后所需要的“commit id”, 同时在Linux端生成的用户根目录下生成“.vscode-server”文件夹，“.vscode-server/bin/”下会有一个以“commit id”值为文件名的文件夹，如果没有生成这个文件夹，请把上面的连接步骤重复多试几次 根据刚刚的报错信息，我使用的是stable版，用报错信息里的“commit id”替换下面连接里的“$COMMIT_ID”，直接访问下载服务端程序（vscode-server-linux-x64.tar.gz） https://update.code.visualstudio.com/commit:$COMMIT_ID/server-linux-x64/stable 如果是insider版，把url最后的stable换成insider https://update.code.visualstudio.com/commit:$COMMIT_ID/server-linux-x64/insider 安装服务端程序 打开之前安装git时附带的“Git Bash” 把刚刚下载的服务端程序传到linux上 ssh连接到linux上 在linux上执行 完成后，VSCode再次连接就能连上了 配置使用SSH密钥自动认证 使用密码连接的话，VSCode每次Reload或者打开新窗口都要重新输入密码，比较麻烦，可使用密钥自动认证 打开之前安装git时附带的“Git Bash” 生成密钥 把公钥传到linux服务器 完成后本机所有对该服务器的ssh连接应该都能自动认证 参考：
图片来源：https://www.pixiv.net/artworks/82570722 Lua官方解释器完全使用ANSI C编写，并且提供了C API，使用C/C++和Lua交互相当方便 Lua虚拟栈 C和Lua的交互基于一个栈，这个栈的每个位置都有两个索引值，这里只需要记住这个栈的栈顶索引始终为“-1”，栈底索引始终为“1”即可 基本环境加载 后续的代码示例均基于“test.lua”“main.c”这两个文件 Lua C API的函数大多第一个参数都为“lua_State *L”，即“main.c”中使用“luaL_newstate()”创建的lua住线程，后续不再说明 参考编译命令 C获取Lua变量 Lua的C API提供 “lua_getglobal” 来将指定全局变量压入栈，然后提供一系列“lua_toxxx”函数来将栈中的变量转换为C类型变量，相关函数在使用前 获取布尔值、数值、字符串 布尔值 由于C语言里没有对应布尔类型，会将布尔类型值转换为整形的“1”和“0”。使用“lua_typename”函数可以将表示lua类型的整数转换为对应C字符串 数值 lua脚本中不显式区分整数和浮点数，所以“lua_getglobal”返回的类型都是“LUA_TNUMBER” ，但转换为C变量时需要区分，分别使用“lua_tointeger”和“lua_tonumber” 字符串 获取字符串差不多，“lua_tostring”会在末尾补 '\0' 但如果字符串本身内容也包含 '\0' 的话无法判断真实长度，此时可以使用“lua_tolstring”传递第三个参数保存字符串长度 分别使用“printf”和“fwrite”打印获取到的字符串 要在命令行确认是否有’\0’输出可以将输出通过管道传递给‘cat -v’命令，’\0’会以“^@”的形式显示 获取表中的变量 通过变量名获取 获取表中的变量，需要先将表压入栈，然后把这个表在栈中的位置和要获取的变量名传给“lua_getfield”，“lua_getfield”会将变量压入栈 通过key获取 有时候表中成员没有变量名，比如数组和字典，此时可以先将表压入栈，然后通过“lua_pushxxx”系列函数（或者其他方式）将key压入栈，之后调用“lua_gettable”将table[key]压入栈 遍历数组 操作数组前需要先将数组，压入栈，获取数组长度使用“luaL_len”，该函数会直接返回数组长度。访问数组中的单个值使用“lua_geti”传入数组在栈中的索引和要访问的数组下标 C调用Lua函数 在C中调用Lua函数需要先将函数压入栈，然后依次将函数参数入栈，调用“lua_pcall”设置函数参数数量、返回值数量、错误信息位置即可，函数返回值会依次压入栈中 调用全局函数 调用对象的成员函数 其实和调用全局函数没太大区别，就是需要先获取对象再获取对象的函数，另外成员函数定义时使用“:”语法省略了self参数，但C调用的时候不能省略