MENU

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

March 2, 2020 • Read: 552 • 瞎折腾

最近在学习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://www.skyblond.info/about.html 处获得。

生活不易,亿点广告

Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 1 条评论
  1. ᚦᛃᛝᚲᚾᚢ᛭᛬ᚨᛟ ᚦᛃᛝᚲᚾᚢ᛭᛬ᚨᛟ

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

0:00