天空Blond - 代码札记
type: channel
link: https://www.skyblond.info/tag/%E4%BB%A3%E7%A0%81%E6%9C%AD%E8%AE%B0/
items: 【代码札记】年轻人的第一个Minecraft Data pack
items: 【代码札记】Bencode编解码（Kotlin）
items: 【代码札记】康威生命游戏
items: 【代码札记】在JVM上优雅的使用Lua脚本
items: 【代码札记】基于 Merkle DAG 的文件存储服务 P4 API接口 & SpringBoot初入门
items: 【代码札记】基于 Merkle DAG 的文件存储服务 P2 数据结构
items: 【代码札记】基于Merkle DAG的文件存储服务 P1 铺垫
items: 【代码札记】使用Java ASM替换字符串常量
items: 【代码札记】OpenCL模拟双摆
items: 【代码札记】LWJGL's OpenCL HelloWorld

【代码札记】年轻人的第一个Minecraft Data pack
type: item
date: 2024-03-10T11:10:00+08:00
description: Create mod挺好的，就是配方不太和我心意。怎么办呢？自己动手丰衣足食。本文介绍如何使用Minecraft的Data pack特性来扩展游戏的配方系统。闲白最近看阿里云和腾讯云都在做活动。腾讯云那个轻量游戏主机看着不错，点开却是老用户与狗不得入内。于是只得选购了阿里云的个人99计划，2核心2GB内存3Mbps带宽，年付99元。说实话，没啥诚意，但又转念一想，99一年要啥自行车啊。买了服务器之后就发现，干点啥呢？做网页，那肯定要备案。以我的性格来说：案，狗都不备。所以想来想去，只能开个MC服务器了。但是2GB内存，实在是不够吃，我用尽毕生所学，在1.20.1上打了19个Forge模组。再后来发现内存真的不够用，所以自己加了700多块钱升级了一个2核4GB内存，有点肉疼，但当时也是上头了——我今天一定要让他跑起来。再后来又发现带宽不够，固定3Mbps带宽也就带3个人，所以后来我换成了按量付费，同时把安全组打开，就留下MC服务器的端口免得被打然后账单上天。好在固定带宽改成按量付费的时候还有退费，退的不多，不过还是那句话——99一年，要啥自行车啊。这些Mod都是我自己选的，因为我平时高版本都玩Fabric了，但这些Mod还是以Forge为主，所以就Forge了。这些mod除了优化，基本上都是种田相关的，最后还有个Create用来自动化一些东西。BiomesOPlenty-1.20.1-18.0.0.592.jarBookshelf-Forge-1.20.1-20.1.9.jarBotanyPots-Forge-1.20.1-13.0.24.jarBotanyTrees-Forge-1.20.1-9.0.11.jarChunky-1.3.136.jarFallingTree-1.20.1-4.3.4.jarFarmersDelight-1.20.1-1.2.4.jarKsyxis-1.2.2.jarNoChatReports-FORGE-1.20.1-v2.2.2.jarTerraBlender-forge-1.20.1-3.0.1.4.jarTravelersBackpack-1.20.1-9.1.12.jaralternate_current-mc1.20-1.7.0.jarcanary-mc1.20.1-0.3.3.jarcarryon-forge-1.20.1-2.1.2.7.jarcreate-1.20.1-0.5.1.f.jardynview-1.20.1-3.9.jarferritecore-6.0.1-forge.jarmodernfix-forge-5.13.0+mc1.20.1.jarstarlight-1.1.2+forge.1cda73c.jar其中Chunky是用来预先生成区块的，因为服务器只有两个核心，所以在不玩的时候提前生成好区块，之后跑图探索就会舒服一些。再就是NoChatReports，这个是我在高版本必备的mod。然后还有TravelersBackpack，我个人认为是一款非常强筋甚至有些OP的背包模组。至于BiomesOPlenty这种增加生物群系的模组就更不用说了——我MC正版都买了快10年了，那原版那点东西，能有意思吗（再就是BotanyPots和BotanyTrees这两个花盆模组，我感觉也是非常OP的：自动种田，只占用1格空间，自动兼容mod物品，不需要手动补种，不需要手动收获，放好种子放好土，它会自动收获放进箱子里，连自动化都省了，非常OP最后就是各种优化的mod，性能不够优化来凑。像是dynview，能够自动根据当前服务器的tick耗时来调节渲染距离和模拟距离。如果服务器性能还够吃，那就增大这些距离来提升玩家体验，如果性能不够吃了那就给这两个距离往下调，确保玩家不会因为服务器性能吃紧而卡顿。但玩着玩着，我发现这个Create模组和我看别人玩的不太一样：好像缺点东西。我之前看到Create模组时是在ilmango的ATFC系列，这个整合包针对Create模组增加了许多自定义的合成表，比如你可以从沙子、沙砾和石头这些方块中获得一些碾碎的矿物，然后通过水洗得到更多的矿物。虽然我觉得这些配方非常繁琐（但这也是这个系列的看点所在），但我觉得这种想法还是挺不错的，比起那些种植矿物和动物资源的模组，我觉得Create这种配方既能免去后期重复下矿的麻烦，又可以要求玩家付出一定的努力。可是我打开合成表一看：啊？怎么什么都没有？原来原版的Create只有一些很基础的配方，而我之前在视频中看到的都是整合包作者自己加的。那么问题来了，怎么加的呢？我知道可以通过写Mod来加，但是整合包作者好像也没有因为就单纯要加合成表就自己写Mod。后来我一查，原来从1.13开始Minecraft就有了data pack了…

【代码札记】Bencode编解码（Kotlin）
type: item
date: 2023-04-17T17:49:00+08:00
description: 不知道出于何种原因，我突然决定自己造轮子。索性这个轮子造的好像还不是特别没用。本文将记述我从零开始使用Kotlin实现一个Bencode编解码库。前言Java和Kotlin（JVM）具有比较好的互操作性，即便没有给Kotlin设计的库，如果有相应的Java库，在Kotlin上也是可以直接调用的。在此之前我尝试过com.dampcake:bencode这个库，用起来感觉还不错，但它的操作是类似DOM那种，即所有写入和读出的数据全部存在内存里以供操作。这种操作方式固然简单好用，但是如果你有很多数据的话，你可能更希望采用接近XML SAX的方式。后者是基于流的解析方案，也就是说解析器一边读入数据，一边将解析出来的结果交给你的代码。你可以选择将他们收集起来组装成DOM，也可以选择即时处理然后回收。本文将考虑如何构建一个基于流的Bencode编解码库。BencodeBencode好像是一种不太常见的编码。考虑到早年间的XML，以及现在的Json，好像Bencode并没有什么用武之地？但作为一个P2P爱好者和版权左人，大名鼎鼎的BitTorrent协议就是用Bencode编码数据。这种编码形式以字符为基础，肯定不如ProtocolBuf这种二进制编码高效，同时它的结构比较简单，不太可能像XML或Json在功能上那么丰富（Bencode甚至不支持编码小数）。但从某种意义上来说，Bencode确实是最简单且紧凑的格式。举个例子。在Json中表示一个结构是这样的：{ "number": 1234, "string": "hahaha", "list": [ "string in list", 2345, [ "list in list!" ], { "name": "object in array!" } ], "obj": { "string": "An object", "list": [ "List in object!" ], "dict": { "num": 2345 } } }去掉所有多余的空格，一共是195个字符。如果表示成XML，那就更罗嗦了：<?xml version="1.0" encoding="UTF-8" ?> <root> <number>1234</number> <string>hahaha</string> string in list 2345 <2>list in list!</2> <name>object in array!</name> <obj> <string>An object</string> List in object! <dict> <num>2345</num> </dict> </obj> </root>XML需要295个字符，而且它还没有保留list in list的部分。这可能是我是用的Json到XML转换器有问题，也可能是XML并没有名且规定列表的格式。如果将上述数据转换成Bencode，那就显得紧凑了不少：d4:listl14:string in listi2345el13:list in list!ed4:name16:object in array!ee6:numberi1234e3:objd4:dictd3:numi2345ee4:listl15:List in object!e6:string9:An objecte6:string6:hahahaeBencode只要179个字符。而这段数据的所有文本内容需要125个字符（数字由对应的字符表示，且丢弃了所有结构信息）。当然，如果只从格式上看的话，Bencode不是那么的“人类友好”，但这无伤大雅，我对于Bencode的主要用途是简单地导入和导出结构化数据，而不必考虑给人看。说了这么多，不如我们来看看Bencode的编码规则。Bencode的编码规则比较简单：Bencode使用ASCII字符作为分隔符和元素对于数字，采用i42e的形式来编码，其中42是数字42对应的十进制字符串。数字不允许前导0（即00042是非法的）。负数使用-作为前缀，即i-42e，但不允许负0对于字节串（字节序列，并不一定是字符），采用4:spam的形式来编码。其中4表示这个字节串的长度，采用十进制字符串表示，冒号表示分割，随后spam是字节串的实际内容。Bencode并没有提及数据无法被编码成ASCII时应当如何处理，在一些具体实现中，人们主要采用UTF-8来应对其他字符，或使用ISO 8859-1来编码字节数据，亦或采用Base64等编码将字节串编码为ASCII字符串一个列表由l<content>e表示。一个具有字符串“spam”和数字42的列表应当被表示为l4:spami42ee。其中首个字符是小写字母L，不是数字1。列表内的元素类型不受限制…

【代码札记】康威生命游戏
type: item
date: 2023-02-18T20:41:00+08:00
description: 本文记述我使用Kotlin在JVM上实现Conway's Game of Life。游戏规则康威生命游戏并不是什么新鲜玩意儿了，它可以视作一个二维的棋盘，每一个格子被称为细胞（Cell），每一个细胞有两种状态：死亡或存活。每一轮迭代时，所有细胞同时更新状态，更新的规则如下：若细胞当前存活：当周围的存活细胞数量小于2时，这个细胞在迭代时死亡（因人烟稀少）当周围的存活细胞数量大于3时，这个细胞在迭代时死亡（因人口过剩）当周围有2个或3个存活的细胞时，这个细胞在迭代时继续存活若细胞当前死亡：当周围有且只有3个存活细胞时，这个细胞在迭代时复活（模拟繁殖）其他形况下，细胞继续保持死亡状态这个规则其实还挺简单的，并且它可以使用多线程进行运算。实现思路这个游戏的“世界”可以用一个二维数组表示，数组的元素就是一个布尔值，true表示存活，false表示死亡。每次更新细胞时先统计它周围的存活细胞，然后根据细胞的当前状态使用if else做判断，更新细胞状态。考虑到规则要求所有细胞同时更新，因此我们需要两个“世界”，一个表示当前的细胞状态，计算出下一状态后，将新的状态写入另一个世界，表示未来的状态。当所有细胞都产生了新状态后，交换这两个世界的指针，这样一来，未来的状态就成为了现在的状态，而原来的状态则成为记录未来状态的容器。不论使用什么语言，这种设计还都挺合理的对吧？在JVM上也一样，对吧？整体来说还挺对的，但有一些小问题。首先，JVM标准并没有规定一个布尔值应该占多少内存。可能是1比特，也可能是1字节，这完全取决于JVM的实现。如果JVM使用1比特，那么含有1024个元素的布尔数组的大小就是128字节；如果采用1字节表示一个布尔，那么同样大小的数组就要占用1KB。假如说我们要渲染一个1080P的康威游戏，1920乘以1080，一共是2073600（200万）个细胞，每个细胞占用1字节，这就是2MB的内存，而原本它可以只占用不到256KB的。当然了，好在JVM中其他类型的大小是固定的。你可以选择使用byte作为容器，这样一个byte就有8个bit，但鉴于kotlin的类型系统比较生硬，在做位运算的时候需要将byte转换成int，再将int转换为byte存回去，这样子很麻烦，所以我是用Int作为容器，每个Int可以存储32个比特，即便有浪费，也最多是最后一个Int没有完全使用，浪费的部分不超过4字节。熟悉BitSet的读者可能会说，诶呀，你说的这个不就是BitSet嘛！Java中提供了一个可变长度的BitSet，可以方便地做位运算。但这里还有一个问题：内存一致性。关于这一部分，最开始的构想是使用分段锁来保护不同位置，这样既保证了内存一致性，又保证不同位置的独写互不冲突。但是后来发现一个问题：写入一个状态需要读取九个状态，换句话说，如果读写都加锁（读需要加锁保证线程可以看到之前写的数据），那么更新一个细胞就要竞争10次锁，一旦竞争失败，synchronized关键字就会把竞争失败的线程转变为操作系统的阻塞态。这是非常耗费时间的。谈及多线程和内存一致性，包括我在内，第一反应可能都是用同步锁，无论是synchronized关键字还是同步代码块，总之，正确用锁就能保证安全。但是从性能角度来看，监视器锁可能是性能最差的（字节码中使用了monitorenter和monitorexit），因为它依赖于操作系统将竞争失败的线程阻塞，锁释放时再依赖操作系统唤醒线程。在这里，我们更新一个细胞需要读取9次，而每次都要竞争锁，如果竞争失败则需要在阻塞、唤醒上浪费时间。采用自旋锁（ReentrantLock）则能够避开线程调度。选好了锁，我们再想想，到底哪里需要锁？我们使用锁的目的就是利用它的顺序性，也就是所谓的happen before，即后进入锁的线程一定能够看到先前持有锁进程产生的修改——后来的线程在读取世界状态时，必须能够看到之前由多个线程计算出来的状态。可我们真的需要使用锁来保证这一点吗？除了锁，只读内存也是同步安全的，只读就是所谓的immutable，不可变对象。通过游戏规则可知，所有细胞必须同时更新，因此这不可能是就地更新，也就是说，我们从当前世界读取状态，然后将修改写入其他地方。如果当前世界是不可变的呢？这样一来，读取的时候我们就不需要锁了。读取的时候不需要锁并不意味着不需要锁了。上锁的时机从读取时提前到了创建对象时。计算下一步的状态仍然需要一个可修改的状态，我们仍然需要使用锁来写入，而读取的时候也需要锁来保证我们可以看到其他线程的修改。但如果我们在计算完成后抄写一份，我们只需要在这里上一次锁，然后将抄写的结果作为不可变对象使用，那么之后就不再需要上锁了。实现细节WorldMap“世界”的实现如下：package info.skyblond.pocog im…

【代码札记】在JVM上优雅的使用Lua脚本
type: item
date: 2022-08-04T16:13:50+08:00
description: 本文将记述如何在JVM上使用Lua脚本。众所周知，JVM上运行的都是字节码，而要得到字节码，就离不开编译。而脚本的目的就在于不进行事先编译的情况下提供一个灵活的控制系统。谈及脚本语言，JavaScript和Python算是两个比较火的编程语言了，但是我认为他们都太复杂了，不够优雅。我心目中比较理想的脚本语言是Lua，它比较简单，而且能够面向特定领域。如果说Python是为了解决任何可以通过编程解决的问题而设计的，那么Lua可能就是为了解决某个特定领域中的问而设计的。例如大名鼎鼎的Cheat Engine，他就支持用户使用Lua脚本来操作程序的内存，或者将Lua脚本编译成机器指令插入到源程序中，这可比写汇编容易不少。除了Lua，似乎也可以为某一个特定领域创建一门语言，来自JetBrains的MSP工具就是为此而生。但是为此你需要自定义一套语法规则，相当于为了你的领域而单独创造一门编程语言，即便它非常简单。这对我来说有些因小失大了——引入脚本最初是为了简化开发，同时提供足够的灵活性，而为了达到这个目的要设计一个全新的语言，我想这对开发者、对用户的心智负担都不小。本文将记述我在JVM平台上使用Lua脚本的过程。LuaKLuaK是隶属于KorGE的Lua库，其旨在将LuaJ迁移到Kotlin上。其中KorGE是一个基于Kotlin的游戏引擎。但这个库看起来还在开发中，暂时没有可以使用的文档与制品。我个人比较期待这个库，但是目前还没有完工，只能寻求别的代替品了。Luaj经过一番搜索，我找到了一个有年头的库，LuaJ，有年头到什么程度呢？就是最后一次更新的时候（2019年3月，3.0.2发布），社区开发者没能联系上原作者，进而无法为Maven仓库上的制品进行更新。于是使用时只得将库下载到硬盘上进行使用。这让我想起了早年间我学习Java，还不会用maven、gradle这些工具时，就从网络上下载依赖的jar，让IDEA帮我管理依赖。总之，通过类似implementation(files("lib/luaj-jse-3.0.2.jar"))的语句就可以让gradle使用本地的jar依赖了。这个库在功能上还是比较丰富的：例如执行Lua脚本（使用库的API），提供脚本执行引擎（使用Java Scripting API），Lua解释器（将Lua脚本处理为语法树，使用Java访问语法树），Lua编译器（将Lua脚本编译成LuaVM的字节码），Lua到Java编译器（将LuaVM的字节码翻译成JVM字节码）。而以上所有内容都跟C代码没有任何关系——纯Java实现。当然了，本文的目标很简单：让Java能够为Lua脚本提供新的能力，并且在Lua脚本中调用Java提供的能力。经过一番查阅，LuaJ为扩展提供了较为方便的接口，其中比较重要的就是TwoArgFunction。从名字来看，这个抽象类似乎是描述了一个具有两个参数的函数，但LuaJ将其用作加载库的方式。具体来说，当我们在Lua脚本中require 'MyCustomLib'时，LuaJ会搜索classpath中所有实现了LuaFunction、并且具有默认构造函数（即无参数的构造函数）的类，如果找到了name为MyCustomLib，就把这个类当作一个函数来执行，其中第一个参数是模块名（modname，也就是MyCustomLib），第二个参数就是调用者的环境。通过操作环境可以在环境中注册库，之后的代码便可以调用我们的库了。需要注意的是，前文说的name并不是传统意义上的类名，而是Class.java中getName()返回的类名。因此对于info.skyblond.demo.lua.luaj包中的MyCustomLib类，他的name是info.skyblond.demo.lua.luaj.MyCustomLib。如果仅用MyCustomLib，LuaJ是找不到对应类的。这里我编写了一个简单的例子，展示了LuaJ提供的无参函数、单参函数、双参函数、三参函数和可变参函数：package info.skyblond.demo.lua.luaj import org.luaj.vm2.LuaFunction import org.luaj.vm2.LuaTable import org.luaj.vm2.LuaValue import org.luaj.vm2.Varargs import org.luaj.vm2.lib.* import java.math.BigDecimal import java.math.BigInteger import java.time.Duration class MyCustomLib : TwoArgFunction() { /** * Will be called…

【代码札记】基于 Merkle DAG 的文件存储服务 P4 API接口 & SpringBoot初入门
type: item
date: 2021-10-24T16:55:00+08:00
description: 上文中实现了一个简单的概念原型，但是每次要用都得打开IDEA改代码，给人一种不可靠的感觉。经过一番搜索，我发现IPFS也提供基于HTTP的接口，我决定仿照IPFS也弄一个HTTP API。虽然我是写Java的，可我从来没用过Spring相关的东西（Spring框架是一系列简化开发的库的合集，而当Spring这套框架变得愈加复杂时，人们构建了SpringBoot来简化Spring框架的使用）。我一直觉得对于个人的小项目来说用Spring过于庞大了，所以以前我比较青睐诸如Javalin和Ktor这样的框架，用于快速构建一个HTTP API，但是他们仅仅是一个提供HTTP API的库，当程序需要可配置性的时候，通常需要一个yml（我个人比较青睐这个格式作为配置文件）文件进行配置，于是解析配置、拉起服务等操作都需要我自己写代码。一个两个还行，等项目多了，或者说，一个项目里的配置多了起来，自己维护这一套代码就变得极其繁琐。最近我在考虑为这个系列做一个HTTP API，找了一圈，这些库虽然说小巧好用，但跑不掉自己要做好多铺垫/善后。最终还是找到了Spring，与几年前不同，现在可以直接通过官方的网页版交互式选择你需要的配件，然后自动生成项目模板。我一直不愿意碰Spring的原因之一就是它本身过于庞大，给人一种无从下手的感觉。至少SpringBoot在这方面减轻了我启动项目的痛苦。项目总览经过大约三四天的编码，我成功的将原来的代码迁移到SpringBoot框架中，其中重构了不少东西，并且大部分东西都搞成用Java编写了。SpringBoot对于Kotlin的支持还比较有限，一些东西和Kotlin混合起来之后会引发一些奇怪的问题，所以我比较青睐的做法是大部分基础设施使用Java编写，比如配置和数据库实体什么的，然后一些工具类或者数据模型使用Kotlin，后者在写法上会方便不少（尤其得益于data class及不严格要求一个public class独占一个文件）。通过大约上千次谷歌搜索，我终于让Gradle（with Kotlin DSL）、protobuf、lombok、SpringBoot和Kotlin能够在一个项目中融洽相处。现在的项目中有这么多文件：对比之下，原来的工程全部展开也只有这么一点文件：并且虽然这些组件可以在一个工程中和睦相处，但实际上lombok和Kotlin还是没有办法一起工作。因为Hibernate使用代理类来监测实体，而Kotlin默认的类和成员全都是final，因此使用Kotlin来编写数据库实体就不可避免的要滥用open关键字，同时Hibernate依赖setter来更新数据，因此数据库中具有不可变语义的列被声明为val时将会导致Hibernate无法为查询结果赋值，而声明为var就失去了Kotlin中不可变成员变量的优势。因此最终决定还是使用Java来编写数据库实体类，然后使用Lombok处理Getter和Setter。但是因为Kotlin要先于Java编译（否则Java编译时找不到Kotlin依赖），而此时Lombok的注解处理器来没有开始工作，因此使用@Getter和@Setter标注的类，这时候还没有对应的方法被生成。所以在Kotlin中没办法使用依赖Lombok的Java类。但好在需要Lombok的地方只有数据库实体，而与数据库相关的操作可以封装到由Java实现的服务里，通过巧妙的设计可以让Kotlin和Lombok互不见面，从而避免产生问题。项目结构在切换到SpringBoot之后我发现原来的一些设计并不能直接拿来用。在Spring中引入了控制反转（Invert of Control），即由框架调用你的代码。在传统的编程中都是你的程序调用框架来完成一些事情，比如你的程序调用Jackson或者Gson将一个字符串转换为一个对象，这个是控制。而在处理HTTP请求时，别人的代码调用你的代码，这个就有点反转控制的意思了。控制反转更严格的说法是基于对象的，在Java中所有的数据和操作都封装在对象中，因此当你的代码需要利用Jackson或者Gson做什么的时候，至少需要先实例化一个ObjectMapper或者Gson对象，然后拿着这个对象去做事。这个过程中你的代码控制这个对象如何实例化；在控制反转中，你的代码接受一个对象作为入参，而不必（也无法）控制这个对象在何时何地如何实例化的，只管用就是了。好在原来的程序中我设计了不少接口，所以迁移起来还是比较方便的。反转控制带来的好处就在于程序代码之间只经过接口约定，而不必假定对方是如何实现的。大多数情况下接口是一个相对比较强的约束（但没办法程序化的约定实现效果——程序员只能将要求的实现效果，诸如原子性，写在JavaDoc中并祈祷子类这样实现）。在重构后的设计中一共有三个服务…

【代码札记】基于 Merkle DAG 的文件存储服务 P2 数据结构
type: item
date: 2021-09-20T14:15:00+08:00
description: 上文中讨论了关于Merkle DAG的一些基本概念和原理，本文将记述其具体实现。存储结构结合上文来看，本系列中Merkle DAG的使用方法还是更接近IPFS一些，于是我便参照IPFS的白皮书设计了一下。为了使数据具有统一的序列化标准，我使用了Protobuf。syntax = "proto3"; message AritegObject { // Type of this object AritegObjectType type = 1; // blob data content bytes data = 2; // list, tree and commit links // Note: commit link has fixed name: parent, link, author repeated AritegLink links = 3; // commit data AritegCommitData commit_data = 4; }AritegObject是所有Object的超集，它具有所有Object需要的字段，并且内置了一个type用来描述该Object是何种类型：enum AritegObjectType { BLOB = 0; LIST = 1; TREE = 2; COMMIT = 3; }这里一共设计了4个Object，与前文介绍的IPFS中的Object类型一样。另外IPFS中还定义了加密和签名的Object，用于IPNS，由于本文的目的是一个简单的文件存储服务，所以并不考虑对存储数据的处理（签名、加密等）。即便是要加，可以简单的在程序方面增加， 而不必修改底层设计。对于links，设计与IPFS的类似：message AritegLink { // name of the link string name = 1; // multihash of target bytes multihash = 2; }这里没有记录目标对象的大小，因为与IPFS不同，IPFS获取对象前无法知晓对象的大小，因此必须记录下来以供申请合适大小的缓冲区。而我们的系统将所有数据集中存储，因此给定一个目标的multihash，必定能够知道该对象的字节数目。对于commit类型的Object，使用一个专门的域来存储某次提交的信息，结构如下：message AritegCommitData { // type of committed object AritegObjectType type = 1; // unix timestamp of this uint64 unix_timestamp = 2; // commit message string message = 3; }逻辑结构基于上述存储结构，可以引申出4个逻辑结构，分别对应blob、list、tree和commit。抽象类为了适应Protobuf生成的类与四个逻辑结构能够相互转换，首先定义如下抽象类：package info.skyblond.ariteg.objects import info.skyblond.ariteg.AritegObject import info.skyblond.ariteg.AritegObjectType abstract class AbstractAritegObject { /** * Convert current instance to proto * */ abstract fun toProto(): AritegObject // If bytes are same, then they are same override fun equals(other: Any?): Boolean { if (this === other) return true if (other !is AbstractAritegObject) return false val thisBytes = this.toProto().toByteArray() val otherBytes = this.toProto().toByteArray() if (!thisBytes.contentEquals(otherBytes)) return false return true } // hash is the byte content override fun hashCode(): Int { return this.toProto().toByteArray().contentHashCode() } } abstract class AbstractAritegObjectCompanion<T>( protected…

【代码札记】基于Merkle DAG的文件存储服务 P1 铺垫
type: item
date: 2021-09-15T22:18:00+08:00
description: 本系列将记述使用Merkle DAG实现一个文件存储服务。这个想法并非本人原创，在本文之前，以太坊、IPFS等去中心实现中都用到了类似的想法，但令人惊奇的是，竟然没有纯粹的将这个想法作为文件存储来实现的代码。可能是意义不大吧。本文作为整个系列的铺垫，将阐述这个需求的意义以及一些基本概念。Merkle DAG所谓Merkle DAG，其实分为两个部分：Merkle和DAG。DAG无需多说，是有向无环图的英文缩写。而Merkle是个人名，早年间他给这个东西注册了专利，所以才叫Merkle DAG或者Merkle tree。从技术上讲，Hash tree或者Hash DAG更直观一些。因为在这种有向无环图中使用了Hash来索引节点。最直观的理解就是把传统的DAG或者树中的指针全部替换成Hash。对于指针，它建立了节点（Node）与成员域（Field）之间的联系，即通过域中记录的指针（内存地址）可以找到一个节点，进而对该节点进行访问。但是指针中记录的内存地址与被指向的节点不具有唯一的对应关系，原则上同一个内存地址可以是任何节点，也可以不是节点。而Hash则具有相对唯一的对应关系，某个节点的Hash由其自身的内容决定，并且微小的改变都会使得Hash的计算结果与原来大相径庭（所谓的「雪崩效应」）。一个Merkle DAG节点可以抽象的标识成如下两种格式：public class MerkleNode<T> { final T data; final List<Hash> links; }public class MerkleNode<T> { final T data; final Set<Hash> links; }这两个区别是使用List存储Hash允许节点间维持相对顺序，而Set则不保证顺序。前者适用于表示大块数据（IPFS），后者适用于组织零碎节点（ETH）。其中links存储的是子节点的Hash。基于节点的定义，显而易见，Merkle DAG有三个特点。首先是整个DAG构建完成后即不可变，因为任何节点的改变，都导致自身Hash的变化，进而导致父节点内容改变，从而导致父节点的Hash变化，如此传播下去，最顶层的根节点的Hash也一定会改变（假定不会撞Hash）。第二个特点就是构造时必须自底向上构造，因为父节点要存储子节点的Hash，而子节点的Hash来源于自身的内容。因此构造时只有叶节点可以被最先计算Hash，然后逐级构造。第三个特点就是允许复用。这并非Merkle DAG的特点，一般的DAG也可以通过共享指针来复用节点，但基于Hash的复用允许我们更直接更自信的复用节点——相同的内容产生相同的Hash，考虑到撞Hash的可能性极小（或许压根儿不需要担心碰撞），我们完全可以认为Hash相同即内容相同。这也是基于内容寻址的核心想法。以上是Merkle DAG的原理，以下将利用IPFS和智能合约作为例子说明他们是如何使用这种DAG的。智能合约以太坊最近（一直）比较热门，它与比特币具有本质上的不同。比特币的核心是去中心分布式的账本，它使用节点度为1的Merkle DAG，实际上就退化成了使用Hash寻址的链表（这里省略了比特币的UTXO模型和挖矿的原理）。而以太坊除了要支持传统的交易之外，还希望引入能够根据条件自动执行的代码，即智能合约。简单回忆一下计算机组成原理，冯诺依曼结构的五大组成要素是：运算器、控制器、存储器、输入、输出。对于区块链来说，运算器和控制器由区块链虚拟机提供，存储器有区块链提供，表现为合约的存储区，该存储区为合约专属，本质上是区块链中的一块数据，表示合约的状态。输入输出则表现为调用合约时传入的参数，以及合约正常返回时的返回值。这样我们就可以实现一个简单的支持智能合约的区块链的。在以太坊中，运算器和控制器由EVM提供，即执行时以太坊节点根据实现约定的指令和行为对编译好的合约进行模拟执行（因为合约并不编译为x86或其他机器指令，而是EVM自定义的指令集），在调用合约时提供的参数作为输入，调用前的合约状态（合约存储区）作为存储器，用于存储持久化的数据（比如账户余额等），而合约结束后的返回值则作为输出发送给调用者。对于区块链节点来说，这个过程它只关心两个东西：调用前的合约状态和调用后的合约状态。要保证交易的可验证性，任何节点只要用同样的输入和同样的合约状态执行同样的合约代码，一定会得到同样的调用后的合约状态（假设其中不涉及预言机，Oracle，不是甲骨文）。而调用后的合约状态将在未来作为输入去验证后续的交易，至于输出，区块链节点并不关心。所以以太坊需要一种可靠并高效的机制来记录每个区块中所有合约的状态。于是就该轮到Merkle DAG出场了。在一个区块中，Merkle DAG表现为一个树，即每一个节点表示一个合约的存储区，这…

【代码札记】使用Java ASM替换字符串常量
type: item
date: 2021-08-10T19:52:51+08:00
description: 最近在用Java写智能合约，其中有一个静态字段是合约的管理员地址，这个地址用于鉴权，确保只有该地址能够对合约进行管理操作（升级、销毁等）。但是为了做到自动化测试，这个管理员地址在develop分支上是私链的，而实际部署的时候得换成公链上的另一个地址。前几天升级合约的时候忘记替换地址，直接把私链地址部署到了公开的测试网了。好在是测试网，问题不大，这要是主网就别玩了，重开吧。为了杜绝这样的后顾之忧，本文决定探索一种方法，能够一份代码按照使用情况填入不同的地址来生成合约，避免将地址写死在代码里产生问题。背景具体来说，这个区块链是Neo N3区块链，其中Java的语言支持由Neow3j这个库提供。这个库允许开发者使用任意JVM语言开发合约，并根据最终编译的Java字节码生成Neo的可执行合约。因此上文提到的合约就是使用Java开发的，没有用Kotlin的原因就是怕翻车。典型的合约管理员地址是将其作为一个静态字段实现的：public class TestContract { static Hash160 CONTRACT_OWNER = addressToScriptHash("NR9pwfToFHHYti4RY1dLP3wGr4waSGn7NH"); }其中NR9pwfToFHHYti4RY1dLP3wGr4waSGn7NH是用于测试的地址，其私钥随着代码一并公开到GitHub仓库，显然这种公开的钱包地址并不适宜作为公链的管理地址使用，但对于自动化测试来说，让程序获取到地址的私钥并进行自动调用，这可比手工测试轻松多了。其中的addressToScriptHash函数是Neow3j编译器提供的一个本地方法，它没有具体实现，而是在编译为合约的时候，由编译器将里面的字符串解读为NeoVM能够理解的钱包地址。这种方法最直观，官方的教程也是这样写的。看起来没什么问题，但涉及到实际使用和开发，就如同我所说的，自动化测试要求密钥开放，而实际部署要求密钥必须保密，如果在开发和部署两个分支上频繁修改这个地址，不美观且麻烦，最重要的是一旦忘记，会导致很大的安全隐患。另一个解决方法是在合约中获取当前网络的MagicNumber来判断网络类型，由合约自动决定使用哪一个地址。由于每个网络的魔数都是固定的，并且公共测试网和主网的数字都是固定不变的，这种方法相对可行，但额外的代码会给执行阶段带来额外的手续费（NeoN3的智能合约是按指令收费的），并且同时写两个地址，并不美观，也不优雅。解决为了美观优雅，我决定探索ObjectWeb ASM库，这个库用于直接操作底层的Java字节码。谈及Java，我的印象总是诸如“抽象”、“不关心底层硬件”、“面向Java虚拟机”之类的，所以我们在编写Java的时候只需要关注逻辑上的实现，而不必关心这套代码是否会在不同架构的CPU上有不同的行为。而能够支持这种功能得，正是Java虚拟机和Java字节码的配合，所有运行在Java虚拟机上的语言，包括Java、Kotlin，最终都要编译成Class文件。而这个Class文件中就包含了即将执行的Java字节码，可以理解为面向Java虚拟机的汇编语言。字节码初探以如下类为例：package info.skyblond.jvm.asm; public class ASMTargetClass { static Pair<String, String> target = genPair("Something", "Nothing"); String local = "local"; static String staticDirect = "staticDirect"; private static Pair<String, String> genPair(String s1, String s2) { return new Pair<>(s1, s2); } }其中的Pair<>是这个类：package info.skyblond.jvm.asm; public class Pair <T, U>{ private final T first; private final U second; public Pair(T first, U second) { this.first = first; this.second = second; } public T getFirst() { return first; } public U getSecond() { return second; } }编译ASMTargetClass会得到文件ASMTargetClass.class，和其他可执行文件一样，我们可以直接用16进制编辑器打开它看内容，这种方法可以但是并不推荐。在Linux下我们会使用…

【代码札记】OpenCL模拟双摆
type: item
date: 2021-04-18T19:51:31+08:00
description: 上一篇文章记述了使用LWJGL提供的OpenCL绑定的HelloWorld，之后我尝试使用JOCL重写了代码，获得了翻倍的性能，于是本文使用JOCL模拟双摆。前言双摆是将一根单摆连接在另一个单摆的尾部所构成的系统。双摆同时拥有着简单的构造和复杂的行为。双摆的摆动轨迹表现出对于初始状态的极端敏感：两个初始状态差异极小的双摆在一段时间的运行后表现非常不同。本文将编写程序，使用显卡同时计算多个双摆，并将它们叠加渲染在窗口上，以直观的方式体现出双摆对于初始条件的敏感程度。关于双摆问题的物理描述和数学公式，本文参照这个网页进行实现，值得一提的是本文只注重于数学公式的实现，而非关注数学公式的推导。多个双摆的计算依赖于OpenCL在显卡的多个计算核心上同时计算。通过编写Kernel，使得显卡上的每一个计算核心在一次计算中计算某一个双摆的物理量变化，多个Kernel同时运行即达到了并行计算的目的。程序实现下面我们来说一说程序的整体实现。本文代码目前已经公开到了GitHub Repo中：hurui200320/DoublePendulum。Kernel编写下面先来说一说Kernel编写，在明确了每一个计算核心要做的事情之后，Kernel的编写就很容易实现了。根据参照文献提供个公式，我们可以利用双摆的属性计算出每一个单摆的角加速度。于是Kernel的参数就是双摆的基础属性：__kernel void pendulum( __global float *length1, __global float *length2, __global float *mass1, __global float *mass2, __global float *theta1, __global float *theta2, __global float *omega1, __global float *omega2 )左侧一列分别对应第一个单摆的轻杆长度、小球质量、当前摆角（竖直向下为0，取逆时针为正方向）和当前角速度（同摆角）；类似地，右侧一列表示第二个单摆的。除了双摆本身的属性参与计算，这里还有两个常量：#define G $G_CONSTANT$ #define DT $DT_CONSTANT$第一个常量是重力加速度$g$，由于C语言命名规范中常量要全部大写，所以就不得不写成G，所以需要注意的是这个G不是引力常量，而是双摆所在环境的重力加速度。第二个常量用于计算积分的数值解。在参考文献中，他们使用了龙格-库塔法利用计算出来的角加速度计算出对应的速度变化和角度变化，为了图省事儿（就是懒），我是用普通的矩形法来计算，即直接用角加速度乘以一个非常小的$\Delta T$作为角速度的增量，以此更新角速度；角度值类似。出于灵活性考虑，这里两个常量的值被设定为占位符，目的是能够在程序中读取源程序后进行替换。内核的具体实现可以移步这里。基本上就是公示的实现，以及利用矩形法更新角速度和角度。JOCL加载并执行内核与上文，在使用JOCL之前先要确定要使用的OpenCL设备，与上文中的思路完全一致，这里就不多赘述了，相关的代码在这里。初始化内核能够选择出要使用的设备后，可以开始利用JOCL加载并执行内核了。这里将JOCL相关的操作抽象为PendulumSimulator类，这个类在实例化时需要以下参数：双摆的总数pendulumCount局部核心数量localWorkerNum，这个数量决定了同时在设备中进行计算的核心数，取决于OpenCL设备的不同以及双摆总数的不同，这个值需要用户提供。时间片长度deltaT，对应前面Kernel的DT重力加速度g，对应Kernel里面的G对应Kernel中的参数，每个数组在JVM下有三个变量，以第一个参数length1为例，该参数表示第一个单摆的摆长： private val pendulumLength1 = FloatArray(pendulumCount) private val pendulumLength1Pointer = Pointer.to(pendulumLength1) private val pendulumLength1Buffer: cl_mem // later in init{...} pendulumLength1Buffer = createClMem()pendulumLength1是Float数组，也是在JVM上实际存储数据的变量。pendulumLength1Pointer是指向该数组的指针表示，用于与JOCL交互，在需要拷贝数据时，需要用Pointer来告诉JOCL把数据放到那里。pendulumLength1Buffer是OpenCL在GPU内存中保存数据的一个对象，在拷贝数据时需要通过指定该变量来告…

【代码札记】LWJGL's OpenCL HelloWorld
type: item
date: 2021-04-15T21:47:55+08:00
description: 前几篇文章中简述了OpenGL的入门过程，本文将简述LWJGL提供的OpenCL绑定下，OpenCL的入门过程。OpenCLOpenGL中的GL表示Graphics Library，而OpenCL则是用于通用计算的：Open Computing Language。早期人们使用显卡进行图形渲染，但后来人们逐渐意识到，显卡上每一个运行着色器的单元就如同一个小CPU——它不如正经CPU那么复杂，频率不快，可用内存也少，还缺乏高级的分支预测和乱序执行能力，但它数量多啊。以我新换的雷蛇笔记本为例：CPU是英特尔的i7-10875H，8核16线程，如果在Java中处理CPU密集型的任务，一般会选择17个线程来执行，如果是I/O密集型任务，CPU空闲时间比较多，则选择33个线程来执行。但是GPU呢？对于RTX3070来说，它有5120个CUDA核心，这意味着原则上我们可以同时在GPU中执行5120个代码，即5120个线程。虽然CPU能跑到5.1GHz，而GPU最高1.62GHz，但在需要高并发的任务中，GPU确实脱颖而出。前几天我在Youtube上看到一个视频：「Fully OpenCL accelerated space battle. (rts rpg game)」，视频作者利用OpenCL加速游戏。这个游戏是一个类似太空大战的游戏，是建立在二维平面上的，每艘船的行为使用OpenCL得出，而不再使用CPU遍历处理。这样得到的性能提升是什么呢？可以实时模拟接近7万个实体，游戏没有任何卡顿。但使用OpenCL是有代价的。OpenCL最初设计的目标并非只是为了在GPU上运算，实际上OpenCL的目标是异构计算，即同一段代码可以在CPU、GPU、FPGA中的任意一种上直接运行，而不必做出修改。这意味着OpenCL必须在设计上保证不依赖某一种平台的结构或特性，而提供一种通用的计算结构，因此我们平时习以为常的CPU内存结构和计算结构，在OpenCL中将不复存在。另一方面说，GPU虽然运算快，但是把数据从CPU内存送到GPU内存并不快。普通游戏显卡通常用于渲染游戏画面，即CPU把当前画面的数据送给显卡，显卡进行渲染，随后CPU送来新的一帧数据，数据是只进不出的；而为了实现通用计算，我们必须在运算结束后把数据从GPU内存读回CPU内存，游戏卡并非做不到，但没有经过特殊的设计与优化，会对速度造成一些影响，这一点在文章最后将代码跑起来后能够有所体现。LWJGL's OpenCL由于OpenCL和OpenGL一样是用C写的，因此Java并不能直接调用他们。于是为了拉齐Java与C之间的鸿沟，和OpenGL一样，LWJGL也提供了OpenCL的绑定，使得我们可以像在C语言中那样直接调用对应的函数就可以完成对应的功能。值得一提的是，LWJGL的OpenCL绑定并非最好，也非唯一。实际上隔壁JOCL库做的更加面向对象一些，用起来也更加舒服，而且文档也很丰富。目前LWJGL3看起来正在重构，OpenCL没有任何文档，只能去他们的Github Repo中读一些测试代码，或者参考OpenCL在C语言中的用法，结合OpenGL绑定中与C交互的部分去猜测代码应该如何编写。所以我的建议是，如果不使用LWJGL提供的OpenGL绑定而只需要使用OpenCL，取决于你是否对编写C语言内核（即着色器，实际跑在GPU上的代码）心存芥蒂，你可以使用JOCL来更加面向对象的加载你编写的C内核；或者直接使用Aparapi库将你的Java代码自动翻译成OpenCL需要的形式。本文将使用LWJGL提供的OpenCL绑定，这个绑定更接近原始C接口，用起来更加复杂一些。如无意外，在未来我将使用JOCL进行OpenCL计算，届时会有对应的文章发表。Hello, World闲话少说，书归正传。要使用LWJGL的OpenCL绑定，只需要在其官网配置项目的时候选定OpenCL就可以了。OpenCL内核就一般的开发流程而言，应当是先搭出来程序的架子，然后再去谈什么样的代码跑在GPU上，但是出于演示的目的，这里先给出OpenCL内核：__kernel void demo(__global float *a, __global float *b, __global float *answer) { int xid = get_global_id(0); answer[xid] = cos(a[xid]) + sin(b[xid]); }内核是同时运行在每一个CUDA核心上的程序，因此我们并不能像CPU那样使用循环来完成两个数组的按项求和。正相反，我们要展开这个操作：每一个Cuda核心只负责将数组中的一个索引位置上的数据相加。于是对于每一个核心，我们先要获取OpenGL给这个核心的编号，然后再根据这个编号将对应位…