MENU

【代码札记】卢恩符文编码 - Proof of concept

March 2, 2020 • 瞎折腾

最近在学习Clojure，我认为学习一门编程语言，只看书不实践是不行的。故决定使用Clojure写一个类似Base64的卢恩符文编码。这里使用Elder Futhark字母表，关于此字母表的更多信息还请移步维基百科。

这篇文章是Proof of Concept性质的，本文将使用Java/Kotlin编写相同功能的代码，以确定具体的实现细节和编码方式。

原理

Base64

关于Base64详细的编解码方式，请移步维基百科。

简单来说就是将要编码的字节按照顺序摆好，然后选定6位为一组算出来对应的数字，再以预先选定好的方式将数字替换成字母。解码时反向操作，通过字母找到对应的数字，按顺序将数字翻译回二进制，按顺序放好便是原来的被编码字节。

卢恩符文

同样按照Base64的思路，将字母换成卢恩符文，并修改一下位数，可以达到目的。这里选用的Elder Futhark字母表具有如下字母：

ᚠᚢᚦᚨᚱᚲᚷᚹᚺᚾᛁᛃᛇᛈᛉᛊᛏᛒᛖᛗᛚᛝᛟᛞ

对应Unicode编码：

\u16A0 \u16A2 \u16A6 \u16A8 \u16B1 \u16B2
\u16B7 \u16B9 \u16BA \u16BE \u16C1 \u16C3
\u16C7 \u16C8 \u16C9 \u16CA \u16CF \u16D2
\u16D6 \u16D7 \u16DA \u16DD \u16DF \u16DE

一共是24个字母。它还具有三种标点：

᛫᛬᛭

对应Unicode编码：

\u16EB \u16EC \u16ED

第一个标点是空格，即单词间的分隔符。中间的是句号，即句子间的分隔符。最后一个不知道，我也没能查到相关的说明。

以下方式只是我选定的一个方式，不唯一，而且很灵活

卢恩符文与Base64首先不一样之处在于字符数量，Base64选了64个字符作为编码字符，他正好是2的6次幂，刚好可以用6个二进制位来表示，这也是为什么要把字节摆好，每六个位一组翻译成数字的原因。而卢恩符文只有24个，加上标点符号也才27个，正好卡在5位和6位二进制数能表达的范围之间，很尴尬，因此这套系统涉及非二进制运算，所以远不及Base64这些利用二进制位操作的方式高效迅速。当然，我写这个东西就是奔着好玩去的，能用就行。

如果换一个角度想，这实际上就是进制转换的问题。Base64是利用64进制表示数据，那么卢恩符文也可以用24进制来表示数据。

对于每一块数据（可以是任意字节），按照字节顺序放好，翻译成数的形式，再按照数制转换的方式操作即可。得到数字之后按照表进行翻译便可得到卢恩符文编码。解码时则反向操作。

以上便是基本原理，当实际实现时还需要有些调整或技巧。下面将分解代码进行介绍。

代码分解

定义常量

首先是定义字母表：

val rawElderFutharkCharacters = charArrayOf(
    'ᚠ', 'ᚢ', 'ᚦ', 'ᚨ', 'ᚱ', 'ᚲ',
    'ᚷ', 'ᚹ', 'ᚺ', 'ᚾ', 'ᛁ', 'ᛃ',
    'ᛇ', 'ᛈ', 'ᛉ', 'ᛊ', 'ᛏ', 'ᛒ',
    'ᛖ', 'ᛗ', 'ᛚ', 'ᛝ', 'ᛟ', 'ᛞ'
).sortedArray()

这里要保证一定是个有序数组，其中原数组的最后两个字母是字母表正确的顺序，但是Unicode编码却是相反的。因为后面解码时要用二分查找确定字符在数组中的位置，所以一定要保证被查找的数组是有序的，否则将不能正确解码。

然后是定义块长度。这里我选了三种不同的长度，实际上大家可以随意选择，只要电脑能跑得动就可以。

const val minBlockSize = 128
const val middleBlockSize = 256
const val maxBlockSize = 512

然后是一些趁手的工具函数。

fun randomBlockSize(): Int {
    return when (Random.nextInt(0, 3)) {
        0 -> minBlockSize
        1 -> middleBlockSize
        2 -> maxBlockSize
        else -> throw IllegalStateException()
    }
}

fun getSpace(blockSize: Int): Char {
    return when (blockSize) {
        minBlockSize -> '᛫' // \u16EB
        middleBlockSize -> '᛬' // \u16EC
        maxBlockSize -> '᛭'// \u16ED
        else -> throw IllegalArgumentException()
    }
}

fun getBlockSize(c: Char): Int {
    return when (c) {
        '᛫' -> minBlockSize // \u16EB
        '᛬' -> middleBlockSize // \u16EC
        '᛭' -> maxBlockSize// \u16ED
        else -> throw IllegalArgumentException()
    }
}

以上分别是随机取一个块长度、按照块长度取一个分隔符和通过分隔符确定块长度。前二者供编码时使用，最后一个则是解码时使用。

编码函数

为了近最大可能保证灵活性，编码函数接收一个字节数组作为参数。

fun encodeRunes(byteArray: ByteArray): String {
    var bytes = byteArray.toList()
    var encodeResult = ""
    while (bytes.isNotEmpty()) {
        ......
    }
    encodeResult += "ᚠᚢᚦᚨᚱᚲ"
    return encodeResult
}

编码函数大体的结构如上。bytes是一个临时变量，encodeResult用来存放编码结果。while循环是对传入数据的循环处理，每次处理一个块的数据量。

最后传出结果时，我加了个后缀，这个是随意选的，我使用了字母表的前五个字母。

对于块的处理如下。首先要确定块长度。

val blockSize = randomBlockSize()

随后是按照长度取出足够数量的字节并进行处理：

//abcdef in raw, use fold right to put in, there will be:
//fedcba, when take out, you take right side bits first
var remainder = bytes.take(blockSize).map { it.toInt() - Byte.MIN_VALUE }.foldRight(BigInteger.ZERO) { t, r -> r.shiftLeft(Byte.SIZE_BITS).add(t.toBigInteger())}

先从bytes中取处定长的数据（.take(length)），然后将他们处理为正数，因为Byte类型范围是-128 ~ +127，如果不做处理，假设第一个字节是+16，第二个字节是-16，由于Java没有无符号类型，所以当进行加法运算时，后面的负数回对前面的正数造成影响。因此这里将每一字节处理成0 ~ 255的范围，随后再进行叠加就是了（map中的部分）。最后要将这些字节按顺序放好翻译成数字。这里使用了Java的BigInteger，它底层是利用整型数组来存储大数，最大范围是整形数最大范围和内存容量二者取最小，通常而言都是内存容量限制住了BigInteger的发挥。

这里使用foldRight来进行求和操作。将字节放进去，左移8位（一个字节的位数），再放另一个，以此类推。而foldRight则是从右向左依次进行处理。例如有如下字节：

a b c d e f

那么处理后存起来的是：

f e d c b a

其中左为高位，右为地位。我们取余数时，位于前面的字节先编码，后来的后编码：

do {
    encodeResult += rawElderFutharkCharacters[remainder.rem((rawElderFutharkCharacters.size).toBigInteger()).intValueExact()]
    remainder = remainder.div((rawElderFutharkCharacters.size).toBigInteger())
} while (remainder.compareTo(BigInteger.ZERO) != 0)

将编码的字符直接写到结果里，然后更新余数，直到除干净。这里要考虑一个问题：

如果当前块待编码的字节是a b c 0 0 0，那么求和后就是0 0 0 c b a，如果处理完前三个有效的之后，后面三个0还没有处理，就提前结束了，如果后面块还有数据，这里丢了三位那不就乱了？

这个问题先放着，解码的时候自然就明白了。

主要的处理完成了，还差一个小尾巴：随机加上分隔符并从bytes里移除处理完的数据：

encodeResult += getSpace(blockSize)
bytes = bytes.drop(blockSize)

解码函数

首先我们要重新定义小米，不是，重新定义一个工具函数：

inline fun CharSequence.indexOfFirst(predicate: (Char) -> Boolean): Int {
    for (index in indices) {
        if (predicate(this[index])) {
            return index
        }
    }
    return Int.MAX_VALUE
}

这个是字符串查找函数，他返回第一个为真的字符，否则返回-1，但是为了方便处理，我们要让他在找不到时返回整型最大值。原因稍后揭晓。

正经的解码函数接收一个编码后的字符串，返回解码的字节数组。

fun decodeRunes(encodedString: String): ByteArray {
    require(encodedString.endsWith("ᚠᚢᚦᚨᚱᚲ")) { "Encoded string should end with ᚠᚢᚦᚨᚱᚲ" }
    var temp = encodedString
    val bytes = mutableListOf<Byte>()
    while (temp != "ᚠᚢᚦᚨᚱᚲ") {
        ......
    }
    return bytes.toByteArray()
}

首先保证编码后的字符串是正确的结尾，然后定义一个临时变量和保存结果的变量。每一次循环处理一个块，直到字符串只剩下一个我们加进去的结尾标记。

每次解码一个块的步骤如下，首先确定这个块的基本信息：

val pivot = minOf(
    temp.indexOfFirst { c -> c == '᛫' },
    temp.indexOfFirst { c -> c == '᛬' },
    temp.indexOfFirst { c -> c == '᛭' }
)
val counter = bytes.size
val blockSize = getBlockSize(temp[pivot])

这里考察这三个分隔符哪个第一个出现，然后根据最先出现的分隔符确定块的长度。同时还记录处理块之前的结果长度，以便后续确定已经解码了多少个字节。

然后按照字符串还原出该块对应的数字：

var accumulator = temp.substring(0, pivot).map {
    rawElderFutharkCharacters.binarySearch(it)
}.foldRightIndexed(BigInteger.ZERO) { index, t, r -> r.add(t.toBigInteger().multiply(rawElderFutharkCharacters.size.toBigInteger().pow(index)))}

这里先取出对应的字符串，然后搜索每个字符在数组中的位置来还原出编码数字，然后按照位置求和。

这里提前更新余下的字符串来判定是不是最后一块：

temp = temp.substring(pivot + 1)
val isLastBlock = temp == "ᚠᚢᚦᚨᚱᚲ"

然后就可以对数字进行处理了：

while (bytes.size - counter < blockSize && (!isLastBlock || accumulator.compareTo(BigInteger.ZERO) != 0)) {
    bytes.add((accumulator.remainder((2.0.pow(Byte.SIZE_BITS).toInt()).toBigInteger()).intValueExact() + Byte.MIN_VALUE).toByte())
    accumulator = accumulator.shiftRight(Byte.SIZE_BITS)
}

循环有两个终止条件：第一个是本块解码出的字节数达到块编码的字节数量，则停止；第二个条件是如果该块是最后一块，则不要求达到数量，只要到0就停，因为后面都是0和后面截止没有区别，反而多余的0会成为脏数据。这样就不必担心中间块有0提前结束编码，会导致数据混乱的问题了。

循环里的内容是取一个字节的数据，还原回字节的范围（还记得一开始我们把字节值从-128 ~ +127移到0 ~ 225吗）并加到结果集里面。然后更新余数。

代码全览

全部代码如下：

import java.lang.IllegalArgumentException
import java.lang.Math.pow
import java.math.BigInteger
import java.nio.charset.StandardCharsets
import kotlin.math.pow
import kotlin.random.Random

// \u16A0 \u16A2 \u16A6 \u16A8 \u16B1 \u16B2
// \u16B7 \u16B9 \u16BA \u16BE \u16C1 \u16C3
// \u16C7 \u16C8 \u16C9 \u16CA \u16CF \u16D2
// \u16D6 \u16D7 \u16DA \u16DD \u16DF \u16DE
// 24 in total
val rawElderFutharkCharacters = charArrayOf(
    'ᚠ', 'ᚢ', 'ᚦ', 'ᚨ', 'ᚱ', 'ᚲ',
    'ᚷ', 'ᚹ', 'ᚺ', 'ᚾ', 'ᛁ', 'ᛃ',
    'ᛇ', 'ᛈ', 'ᛉ', 'ᛊ', 'ᛏ', 'ᛒ',
    'ᛖ', 'ᛗ', 'ᛚ', 'ᛝ', 'ᛟ', 'ᛞ'
).sortedArray()
//note the last two char is reversed in unicode, direct apply binarySearch won't work well with ᛞ

const val minBlockSize = 128
const val middleBlockSize = 256
const val maxBlockSize = 512

fun randomBlockSize(): Int {
    return when (Random.nextInt(0, 3)) {
        0 -> minBlockSize
        1 -> middleBlockSize
        2 -> maxBlockSize
        else -> throw IllegalStateException()
    }
}

fun getSpace(blockSize: Int): Char {
    return when (blockSize) {
        minBlockSize -> '᛫' // \u16EB
        middleBlockSize -> '᛬' // \u16EC
        maxBlockSize -> '᛭'// \u16ED
        else -> throw IllegalArgumentException()
    }
}

fun getBlockSize(c: Char): Int {
    return when (c) {
        '᛫' -> minBlockSize // \u16EB
        '᛬' -> middleBlockSize // \u16EC
        '᛭' -> maxBlockSize// \u16ED
        else -> throw IllegalArgumentException()
    }
}

fun encodeRunes(byteArray: ByteArray): String {
    var bytes = byteArray.toList()
    var encodeResult = ""
    while (bytes.isNotEmpty()) {
        val blockSize = randomBlockSize()
        //abcdef in raw, use fold right to put in, there will be:
        //fedcba, when take out, you take right side bits first
        var remainder = bytes.take(blockSize).map { it.toInt() - Byte.MIN_VALUE }.foldRight(BigInteger.ZERO) { t, r ->
            r.shiftLeft(Byte.SIZE_BITS).add(t.toBigInteger())
        }
        do {
            encodeResult += rawElderFutharkCharacters[remainder.rem((rawElderFutharkCharacters.size).toBigInteger()).intValueExact()]
            remainder = remainder.div((rawElderFutharkCharacters.size).toBigInteger())
        } while (remainder.compareTo(BigInteger.ZERO) != 0)
        encodeResult += getSpace(blockSize)
        bytes = bytes.drop(blockSize)
    }
    encodeResult += "ᚠᚢᚦᚨᚱᚲ"
    return encodeResult
}

inline fun CharSequence.indexOfFirst(predicate: (Char) -> Boolean): Int {
    for (index in indices) {
        if (predicate(this[index])) {
            return index
        }
    }
    return Int.MAX_VALUE
}

fun decodeRunes(encodedString: String): ByteArray {
    require(encodedString.endsWith("ᚠᚢᚦᚨᚱᚲ")) { "Encoded string should end with ᚠᚢᚦᚨᚱᚲ" }
    var temp = encodedString
    val bytes = mutableListOf<Byte>()
    while (temp != "ᚠᚢᚦᚨᚱᚲ") {
        val pivot = minOf(
            temp.indexOfFirst { c -> c == '᛫' },
            temp.indexOfFirst { c -> c == '᛬' },
            temp.indexOfFirst { c -> c == '᛭' }
        )
        val counter = bytes.size
        val blockSize = getBlockSize(temp[pivot])

        var accumulator = temp.substring(0, pivot).map {
            rawElderFutharkCharacters.binarySearch(it)
        }.foldRightIndexed(BigInteger.ZERO) { index, t, r ->
            r.add(t.toBigInteger().multiply(rawElderFutharkCharacters.size.toBigInteger().pow(index)))
        }

        temp = temp.substring(pivot + 1)
        val isLastBlock = temp == "ᚠᚢᚦᚨᚱᚲ"
        //if not the last block, then full of blockSize byte should be filled.
        //if is the last block, then consider the end is 0 => xxx,xxx,0,0,0,0 would be xxx,xxx ,0 after this would be ignore
        while (bytes.size - counter < blockSize && (!isLastBlock || accumulator.compareTo(BigInteger.ZERO) != 0)) {
            bytes.add((accumulator.remainder((2.0.pow(Byte.SIZE_BITS).toInt()).toBigInteger()).intValueExact() + Byte.MIN_VALUE).toByte())
            accumulator = accumulator.shiftRight(Byte.SIZE_BITS)
        }
    }
    return bytes.toByteArray()
}

fun main() {
    val rawString = "天匠染青红，花腰呈嬝娜。袅娜的娜作女子名的时候念钠。\n我看到一片广阔的海岸，在我们面前展现的事物超越头脑所能理解的范畴，沙滩上的每一粒沙子，每一滴水和空气分子都是在讲述一个故事。每个都是要被唱响的歌。他们每个人都充满生机，笑声，苦难和仇恨。他们都是一样的，即使他们都是不同的。"

    println("Raw: " + rawString.length + " character(s).")
    var startTime = System.currentTimeMillis()
    val encodeResult = encodeRunes(rawString.toByteArray(StandardCharsets.UTF_8))
    println("Encode: ${System.currentTimeMillis() - startTime}ms and get " + encodeResult.length + " character(s).")

    startTime = System.currentTimeMillis()
    val decodeResult = decodeRunes(encodeResult)
    val result = (rawString == String(decodeResult, StandardCharsets.UTF_8))
    println("Decode: ${System.currentTimeMillis() - startTime}ms and result is " + result)

    println()

    println("Raw String:")
    println(rawString)
    println()
    println("Encoded:")
    println(encodeResult)
    println()
    println("Decoded:")
    println(String(decodeResult, StandardCharsets.UTF_8))
}

这里有一个例子：

天匠染青红，花腰呈嬝娜。袅娜的娜作女子名的时候念钠。
我看到一片广阔的海岸，在我们面前展现的事物超越头脑所能理解的范畴，沙滩上的每一粒沙子，每一滴水和空气分子都是在讲述一个故事。每个都是要被唱响的歌。他们每个人都充满生机，笑声，苦难和仇恨。他们都是一样的，即使他们都是不同的。

对这段文字编码耗时32毫秒，编码结果如下：

ᚲᚱᚺᛃᛚᛒᛚᚲᚦᚱᛖᛈᛇᚠᛃᚺᛗᛉᚢᛟᛟᛖᛚᚢᛞᛟᛖᚢᚺᚷᛁᛃᛗᛞᛒᛝᚨᛝᚠᛁᛒᛖᛗᛞᚢᛗᚦᚷᚺᚹᚠᛚᚢᛇᚢᚹᛖᛝᚾᛞᚲᛏᚾᚺᚹᛞᚷᛇᛈᛉᛖᛟᛇᛏᛇᛊᛗᛁᛈᛟᚷᛁᛞᚲᚢᚦᛗᛏᛞᛃᛏᚷᛏᚦᛖᛃᚲᚠᛝᛗᚢᛊᛒᛉᛃᛈᚲᛏᛖᛖᚱᚦᛁᛒᚦᛟᚺᛒᛝᛒᛊᛚᛊᚹᛞᚷᛇᚹᛁᚲᛈᚨᛇᚨᛚᚦᛞᚱᛈᛒᚨᚾᚱᚨᛒᛞᚲᚢᛞᚦᚦᚷᛊᚷᛒᛏᚷᛈᛝᛗᛟᚹᛖᚱᚨᛞᚺᛚᛉᛏᚲᛏᚾᛃᚨᛖᚷᛖᚱᛒᚲᚲᚱᛞᚢᛊᛗᚷᚢᛚᛟᛒᛁᛉᚦᚷᛈᚨᚨᚠᛝᛝᚨᛟᚠᛚᛁᚾᛒᛏᛃᛟᛈᚹᛒᛇᛈᛝᛞᛈᚹᛗᚨᚢ᛫ᚾᚹᚦᚠᚢᛇᛚᛝᚺᛁᛃᛞᛝᛃᚱᛟᛚᛖᚹᛖᛈᛟᛈᚨᛟᛞᛁᛃᚢᚠᚠᚱᛇᛝᛟᛟᚲᚨᛒᛃᛏᛞᛁᛗᚢᛒᛖᚦᛝᛗᛒᛞᚨᛈᛖᛁᛗᛟᛉᚠᛈᛗᚦᛉᚲᚾᛟᚦᛟᚦᛉᚨᚾᚢᚦᛗᚠᚾᛊᛝᛒᚺᛗᛇᚨᚺᚹᚦᚾᚹᛊᛏᚲᚠᚢᛇᛊᛟᛈᚢᚠᛇᚱᚱᚨᛗᛖᚾᚢᛊᛗᛖᚾᛏᚠᛁᛊᚠᛝᛚᚷᛏᛒᛊᛏᚠᛊᛒᛒᛊᚹᛇᛗᛊᛟᛒᚺᛇᛖᚹᛊᛉᚦᛈᚾᛝᛝᚨᛃᛒᚲᛃᛞᚢᛏᚦᚱᚲᚦᚾᛇᚦᛏᛇᛖᛉᛟᛏᛁᚨᚷᛒᚲᚾᚷᛒᛉᛊᚱᚠᚢᛚᛟᛗᚱᛃᛁᛞᛒᚺᚢᚠᚨᛏᛇᛗᚲᛉᛏᚺᚢᛃᚱᚱᛞᛃᛗᛟᚨᛈᛞᛗᛏᛈᛈᛊᛈᚠᚠᛇᛗᛉᛃ᛫ᚷᛚᚷᚾᚦᚷᚺᛏᚠᛁᚺᛏᛊᚨᚷᚾᛟᛉᛉᚺᛖᚾᚢᛟᚨᛇᚱᛇᛇᛏᚾᛃᚠᚢᚠᚹᛁᛖᛁᛁᛒᚺᛊᚠᛊᛈᚱᚷᚨᛒᛇᚲᚷᚲᛚᚲᚾᚲᛏᛞᚢᚾᛁᚨᛝᛈᛞᚲᚢᚺᚱᚷᚨᚹᛃᛝᚢᛒᚷᛊᚠᛊᛖᛖᛗᛟᚠᚢᛈᛇᛝᚠᚱᚷᛈᚦᚾᛏᚹᛃᛞᛞᚨᛉᚷᛁᚷᚢᛝᛁᚦᚾᛇᛏᛉᛝᛃᚢᛏᛒᚨᛁᛗᛏᛃᛃᚾᛇᚺᚾᚲᚲᚨᚠᚨᛁᚦᚠᛇᛉᛉᛖᛈᛈᚠᚨᚢᛟᛞᚨᛉᚲᚾᚱᛃᛒᛊᛇᛏᛉᛖᚦᛃᛈᚨᛁᚠᚺᛏᛇᚱᚠᛝᚲᛞᚹᚱᛊᛞᚢᚦᛏᛞᚨᛒᛗᛇᛈᚹᛊᚹᚦᚷᛖᛇᛇᛝᚨᛖᛉᛏᚠᚺᛊᚨᚷᚺᛃᛒᚱᛟᚹᚹᛗᛚᛉᛇᛒᛁᚨᚢᚦᛟᛗᚷᛚᛉᛃᛞᚹᚱᛚᛚᛏᚷᛁᛝᚦᛈᛚᛒᛈᚾᛃᛈᚱᛃᛞᛒᚨᛉᛉᚨᛒᛚᚱᛁᛃᛒᛚᛊᚠᚦᛃᛏᛒᛁᛒᚹᚺᚺ᛬ᚠᚢᚦᚨᚱᚲ

解码上面的卢恩符文耗时12毫秒，解码结果与原文一致。

-全文完-

知识共享许可协议
【代码札记】卢恩符文编码 - Proof of concept 由 天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://skyblond.info/about.html 处获得。

javaKotlin卢恩符文
Archives QR Code
QR Code for this page
Tipping QR Code
Leave a Comment

2 Comments
  1. ᚦᛃᛝᚲᚾᚢ᛭᛬ᚨᛟ ᚦᛃᛝᚲᚾᚢ᛭᛬ᚨᛟ
    Reply

    早上查东西看到好玩的，用python也摸了一个，哦豁 半早上没了@(阴险)

    1. Edden Edden
      Reply

      @ᚦᛃᛝᚲᚾᚢ᛭᛬ᚨᛟ大大，可以分享您的code嗎........我是剛進入python這個領域的新手！