一、概要
三进制数值，作为iota 的基础核心，不管是其模型序列化方式、pow 运算 以及 各种hash 算法实现中，都需要用到的数据结构，因此，本章节主要深入iota 的三进制数值 分析。
三进制数值系统有两种：平衡三进制系统， trit取值为 -1, 0, 1； 非对称三进制系统，trit取值为 0, 1, 2，而IOTA 使用的是平衡三进制。trit 是 trinary Digit， 三元数字位， 类似于 bit， trit取值 -1, 0，1；tryte 是 trinary Byte, 类比于 byte, 一个tryte 由3个trit组成，为了使得tryte更好地让用户识别，IOTA创建了 tryte 字母表： 9ABC…XYZ； 包含26个大写字母和数字9，总共27个字符。
题外话，为什么使用三进制，因为三进制架构的电路功耗是较低的，IOTA的创始人认为未来将会是三进制电路的世界，不得不说IOTA确实是走在了前列，包括采用三进制以及抗量子的算法。
二、详细介绍&解析
2.1 trit/tryte 互转
在分析前，我们先来明确一下一些三进制特性，首先是trit(非平衡)转换成10进制的方法为(假设trits 为 [xyz],高位在左，低位在右)：
x * 3^0 + y * 3^1+ z*3^2。
另外，平衡3进制系统的进制比较特殊，它是遇2 进-1，并且在自身运算时，时按照低位在左，高位在右。怎么说，例如
0,0,0 ，
+1 => -1, 0, 0
+1 => -1, 1, 0
+1 => 0, 1, 0
2.1.1 trit 转 tryte
2-1
图2-1 为iota系统中，使用平衡三进制 trit /tryte 字母转换表，一个tryte 用三个 trit 表示，我们接深入trit 转 Tryte的具体实现：
public class Converter {
public static final String TRYTE_ALPHABET = "9ABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static String trytes(final List<Integer> trits) {
return trytes(trits, 0, trits.size());
}
public static String trytes(final List<Integer> trits, final int offset, final int size) {
StringBuilder trytes = new StringBuilder();
// 遍历 trits 列表中的所有位数，高位在前，低位在后
for (int i = 0; i < (size + 3 - 1) / 3; i++) {
//计算10进制数值,等价于x(i)*3^0 + x(i+1)*3^1+ x(i+2)*3^2
int j = trits.get(offset + i * 3) + trits.get(offset + i * 3 + 1) * 3 + trits.get(offset + i * 3 + 2) * 9;
if (j < 0) {
// 代码走到这里，说明该三进制 数转成10进制数时小于0
j += Constants.TRYTE_ALPHABET.length(); //等价于j+= 27
}
//根据计算索引值，从字符表中获取指定字符
trytes.append(Constants.TRYTE_ALPHABET.charAt(j));
}
return trytes.toString();
}
}
上述代码比较简单，核心是遍历所有的三进制按照高位在前，低位在后，每三个 三进制位 先转 10进制数，然后索引字符表TRYTE_ALPHABET中具体的字符。
2.1.2 tryte 转 trit
有了上述tryte 转 trits实现的了解后，trits 转 tryte 就简单多了，在Converter 实现中，直接通过 tryte的字母表 TRYTE_ALPHABET 以及TRYTE->TRITS 的映射表TRYTE_TO_TRITS_MAPPINGS直接完成。
首先， TRYTE_ALPHABET 是一个String 字符串，该字符串按序存放了tryte 中的27个字符；而TRYTE_TO_TRITS_MAPPINGS则是一个二维数组，第一维则长度为27，一一对应了TRYTE_ALPHABET 中的字符索引位置，第二维则存放了大小为3的 trits 数组，即 tryte 字符对应的 trits 值，该映射表TRYTE_TO_TRITS_MAPPINGS 在Converter 类初始化时，作为静态变量 被初始化。
通过TRYTE_ALPHABET以及TRYTE_TO_TRITS_MAPPINGS，可以简单获取tryte 字符中，指定字符的 trits值。其工作原理为，给定一个tryte 字符 ，先定位 给定字符在 TRYTE_ALPHABET 中的 索引位置 index,然后通过index ，直接通过TRYTE_TO_TRITS_MAPPINGS[index] 获取相应的 trits 数组 值(大小为3)。
因此，我们先来深入TRYTE_TO_TRITS_MAPPINGS的初始实现：
public class Converter {
static final byte[][] TRYTE_TO_TRITS_MAPPINGS = new byte[27][];
public static final int NUMBER_OF_TRITS_IN_A_TRYTE = 3;
public static final String TRYTE_ALPHABET = "9ABCDEFGHIJKLMNOPQRSTUVWXYZ";
static {
final byte[] trits = new byte[NUMBER_OF_TRITS_IN_A_BYTE];
//通过遍历27次，求出全部的映射值
for (int i = 0; i < 27; i++) {
//将当前的 i 所对应的trits 值 拷贝到TRYTE_TO_TRITS_MAPPINGS中
TRYTE_TO_TRITS_MAPPINGS[i] = Arrays.copyOf(trits, NUMBER_OF_TRITS_IN_A_TRYTE);
//trits 自增1
increment(trits, NUMBER_OF_TRITS_IN_A_TRYTE);
}
}
private static void increment(final byte[] trits, final int size) {
for (int i = 0; i < size; i++) {
//Converter.MAX_TRIT_VALUE = 1,
//Converter.MIN_TRIT_VALUE = -1,
// 先执行trits[i]++，在进行判断
if (++trits[i] > Converter.MAX_TRIT_VALUE) {
//代码走到这里，说明需要处理满二进一，因此，需要i 需要 trits[i+1] 执行 ++ 操纵
trits[i] = Converter.MIN_TRIT_VALUE;
} else {
// 非 满二进一的情况下，当前的trits[i]++后，立马跳出
break;
}
}
}
}
上述代码为TRYTE_TO_TRITS_MAPPINGS初始化实现，合兴就是 从[000]开始，执行 自增1 运算，执行27 次上述已经描述的其运算机制。
有了这个转换表以后，具体的 tryte 转 trit 实现就简单了：
/**
* 该方法将trytes 转换为byte的结果覆盖到dest 的destOffset 到 end
*/
public static void trits(final String trytes, byte[] dest, int destOffset) {
// 防御式判断，确保结果trytes 的转换结果足以存放于dest当中，NUMBER_OF_TRITS_IN_A_TRYTE = 3
if((dest.length - destOffset) < trytes.length() * NUMBER_OF_TRITS_IN_A_TRYTE) {
throw new IllegalArgumentException("Destination array is not large enough.");
}
// 遍历trytes中所有 字符
for (int i = 0; i < trytes.length(); i++) {
//组个字符转换为trits,并写入到 dest
System.arraycopy(TRYTE_TO_TRITS_MAPPINGS[TRYTE_ALPHABET.indexOf(trytes.charAt(i))], 0, dest,
destOffset + i * NUMBER_OF_TRITS_IN_A_TRYTE, NUMBER_OF_TRITS_IN_A_TRYTE);
}
}
上述代码流程中，主要是遍历trytes ，并作如下转换，先将所遍历到的字符，去tryte 字符表 TRYTE_ALPHABET中,查找 字符所在索引 index，然后在依据index 从 转换表TRYTE_TO_TRITS_MAPPINGS 定位到具体的 三个 三进制 数字，最后写入dest 相应的位置上，直到trytes 遍历完毕。
2.2 trit/byte 互转
trits/byte 实现与 trits/tryte 互转 类似，核心的不同点在于 一个 byte 需要5个trits。
正常来说，一个byte 有256 种组合，5个trits 有 3^5 = 243 种组合，首先，trits 的范围为[-121,121]， 而byte 的范围为[-128,127]，例如，byte 中的127 转成trits 为 [1,0,-1,-1,-1], 但 byte 中 -116 同样也会转成 [1,0,-1,-1,-1],也就是说，iota 中的 trits /byte 互转实现中，byte 的范围只能在[-121,121]，不然，会产生冲突
2.2.1 trit 转 byte
public static final int RADIX = 3;
public static final int NUMBER_OF_TRITS_IN_A_BYTE = 5;
public static void bytes(final byte[] trits, byte[] dest) {
bytes(trits, 0, dest, 0, trits.length);
}
public static void bytes(final byte[] trits, final int srcPos, byte[] dest, int destPos, final int tritsLength) {
// 5个TRITS 组成一个 byte，不足5个 也当一个
final int expectedLength = (tritsLength + NUMBER_OF_TRITS_IN_A_BYTE - 1) / NUMBER_OF_TRITS_IN_A_BYTE;
//防御式判断，确保存储目标的长度足以存放转换结果
if((dest.length - destPos) < expectedLength) {
throw new IllegalArgumentException("Input array not large enough.");
}
for (int i = 0; i < expectedLength; i++) {
int value = 0;
//按照高位在右，低位在左，每五位构成一个byte，最后几位个数不足5的，按照高位补0 计算。
for (int j = (tritsLength - i * NUMBER_OF_TRITS_IN_A_BYTE) < 5 ? (tritsLength - i * NUMBER_OF_TRITS_IN_A_BYTE) : NUMBER_OF_TRITS_IN_A_BYTE; j-- > 0; ) {
value = value * RADIX + trits[srcPos + i * NUMBER_OF_TRITS_IN_A_BYTE + j];
}
dest[destPos + i] = (byte)value;
}
}
上述代码段为 trit 转 byte 的具体实现，核心是按照高位在右，低位在左，每五位构成一个byte，最后几位个数不足5的，按照高位补0 计算，按照 上述转10进制的方式计算其10进制 值(byte)value，然后写入到字节数组dest中。这里需要稍微注意的小技巧是，在第二个for 循环中，求 相应的byte 值时，从里到外，等价于：
(((trits[i+4] * 3 + trits[i+3] ) * 3+trits[i+2] ) * 3 + trits[i+1]) * 3 + trits[i]。
2.2.2 byte 转 trit
byte 转 trits 与 byte 转 tryte 方法基本一致，都是通过 映射表来实现：
public class Converter {
static final byte[][] BYTE_TO_TRITS_MAPPINGS = new byte[243][];
public static final int NUMBER_OF_TRITS_IN_A_BYTE = 5;
static {
final byte[] trits = new byte[NUMBER_OF_TRITS_IN_A_BYTE];
//通过遍历243次，求出全部的映射值
for (int i = 0; i < 243; i++) {
BYTE_TO_TRITS_MAPPINGS[i] = Arrays.copyOf(trits, NUMBER_OF_TRITS_IN_A_BYTE);
increment(trits, NUMBER_OF_TRITS_IN_A_BYTE);
}
...
}
private static void increment(final byte[] trits, final int size) {
for (int i = 0; i < size; i++) {
//Converter.MAX_TRIT_VALUE = 1,
//Converter.MIN_TRIT_VALUE = -1,
// 先执行trits[i]++，在进行判断
if (++trits[i] > Converter.MAX_TRIT_VALUE) {
//代码走到这里，说明需要处理满二进一，因此，需要i 需要 trits[i+1] 执行 ++ 操纵
trits[i] = Converter.MIN_TRIT_VALUE;
} else {
// 非 满二进一的情况下，当前的trits[i]++后，立马跳出
break;
}
}
}
}
上述为byte->trits 映射表BYTE_TO_TRITS_MAPPINGS的构造，与TRYTE_TO_TRITS_MAPPINGS一致，只不过BYTE_TO_TRITS_MAPPINGS的长度为243 二为字节数组，这里就不再赘述。
下面为具体的转换实现：
public static void getTrits(final byte[] bytes, final int[] trits) {
int offset = 0;
// 遍历bytes中所有的字节
for (int i = 0; i < bytes.length && offset < trits.length; i++) {
System.arraycopy(BYTE_TO_TRITS_MAPPINGS[bytes[i] < 0 ? (bytes[i] + BYTE_TO_TRITS_MAPPINGS.length) : bytes[i]], 0, trits, offset, trits.length - offset < NUMBER_OF_TRITS_IN_A_BYTE ? (trits.length - offset) : NUMBER_OF_TRITS_IN_A_BYTE);
offset += NUMBER_OF_TRITS_IN_A_BYTE;
}
while (offset < trits.length) {
// 代码走到这里，说明bytes 遍历完并填充完整trits后，trits 还有剩余容量，则直接填充0.
trits[offset++] = 0;
}
}
上述实现byte 转 trit，核心是遍历bytes中所有元素，直接通过映射表BYTE_TO_TRITS_MAPPINGS 求出其trit 字节数组值，从左到右填充到目标 数组 trits中。
2.3 hex/trit 互转
首先，这里trit 为平衡 三进制，在平衡三进制中-1 可以T表示。
2.3.1hex转trit
我们先从一个用例来分析：
图2-2
上述为 142 转 非平衡三进制的计算方式：
- 142 的非平衡三进制为 12021；
- 然后对12021 反序 的12021;
- 对于反序中的任意trit为2，加1，然后该trit变为T，并给下一位加1，得到最后的平衡三进制为1T1TT1。
当然如果未-142，则先求其平衡三进制 1T1TT1， 将 1变为T, T 变为 1，得到-142(hex) = T1T11T(balanced)。
我们接着深入其源码实现：
static void tritsFromBigInt(final BigInteger value, final byte[] destination, final int offset, final int size) {
// 防御式判断
if (destination.length - offset < size) {
throw new IllegalArgumentException("Destination array has invalid size");
}
// 求符号位，-1 为负数，1为正数，0说明该value为0
final int signum = value.signum();
if (signum == 0) {
//说明value 为0,因此destination 全部填0，然后直接返回
Arrays.fill(destination, offset, size, (byte) 0);
return;
}
// 不管正负，先按正数求
BigInteger absoluteValue = value.abs();
for (int i = 0; i < size; i++) {// 逐个填充
// 上一轮次的 商 除以3，divRemainder 存储 商 和余数
BigInteger[] divRemainder = absoluteValue.divideAndRemainder(RADIX);
//获取商
absoluteValue = divRemainder[0];
//获取余数
byte remainder = divRemainder[1].byteValue();
if (remainder > Converter.MAX_TRIT_VALUE) {
// 代码走到这里，说明当前所求余数为2，根据上述计算规则，将余数置为 -1，然后遇2进1
remainder = Converter.MIN_TRIT_VALUE;
// 因此，将当前商 加 1处理
absoluteValue = absoluteValue.add(BigInteger.ONE);
}
// 当然，如果为负数，则求余数相反数，在将结果写入destination相应的位置中。
destination[offset + i] = signum < 0 ? (byte) -remainder : remainder;
}
}
上述实现与图2-2 的人工流程稍有 不同，代码实现中，则直接在不断 求商取余 的过程中，直接求其平衡三进制。但求取规则一致。到这里，想必读者会明白为什么在平衡三进制的 数组中，低位在左，高位在右。
2.3.1trit转hex
我们直接进入其源码实现：
private static final BigInteger[] RADIX_POWERS = IntStream.range(0, MAX_POWERS_LONG + 1).mapToObj(RADIX::pow).toArray(BigInteger[]::new);
static final int MAX_POWERS_LONG = 40;
static BigInteger bigIntFromTrits(final byte[] trits, final int offset, final int size) {
for (int i = offset; i < offset + size; i++) {
if (trits[i] < -1 || trits[i] > 1) {
throw new IllegalArgumentException("not a trit: " + trits[i]);
}
}
BigInteger value = BigInteger.ZERO;
for (int n = offset + size - 1; n >= offset; ) {
int count = 0;
long num = 0L;
// 每40(MAX_POWERS_LONG) 个 trit为一段
while (n >= offset && count < MAX_POWERS_LONG) {
num = 3 * num + trits[n--];
count++;
}
value = value.multiply(RADIX_POWERS[count]).add(BigInteger.valueOf(num));
}
return value;
}
上述实现中，需要注意的两点是，首先，这里的转换结果需要用BigInteger表示。因为41位trit 就可以超过long 的最大值。整个转换流程与 trit 转byte 的差不多，都是按照高位在右，低位在左，从里到位，求其 hex 值。但这里必须分段处理，即每40个trit 值先用一个临时的long 变量存储，目的是方式溢出，另外，RADIX_POWERS 则是一个BigInteger 数组，其存放的内容为[3^0, 3^1, ...,3^40]，目的是加速 value.multiply(RADIX_POWERS[count]) 的运算。
到这里，全文分析完毕。
网友评论