package main
/*--------------------------------主要是实现了这三种编码的相互转换，以及一个求取公共前缀的方法。--------------------------*/
/**
encoding.go主要处理trie树中的三种编码格式的相互转换的工作。 三种编码格式分别为下面的三种编码格式。
- KEYBYTES encoding这种编码格式就是原生的key字节数组，大部分的Trie的API都是使用这边编码格式
- HEX encoding 这种编码格式每一个字节包含了Key的一个半字节，尾部接上一个可选的'终结符','终结符'代表这个节点到底是叶子节点还是扩展节点。当节点被加载到内存里面的时候使用的是这种节点，因为它的方便访问。
- COMPACT encoding 这种编码格式就是上面黄皮书里面说到的Hex-Prefix Encoding，这种编码格式可以看成是HEX encoding这种编码格式的另外一种版本，可以在存储到数据库的时候节约磁盘空间。
简单的理解为：将普通的字节序列keybytes编码为带有t标志与奇数个半字节nibble标志位的keybytes
- keybytes为按完整字节（8bit）存储的正常信息
- hex为按照半字节nibble（4bit）储存信息的格式。供compact使用
- 为了便于作黄皮书中Modified Merkle Patricia Tree的节点的key，编码为偶数字节长度的hex格式。其第一个半字节nibble会在低的2个bit位中，由高到低分别存放t标志与奇数标志。经compact编码的keybytes，在增加了hex的t标志与半字节nibble为偶数个（即完整的字节）的情况下，便于存储
*/
// hasTerm returns whether a hex key has the terminator flag.
//参数:字符数组
func hasTerm(s []byte) bool {
//判断数组s的长度是否大于0,并且s数组的最后一位=16(ascii表示向右箭头),如果满足,返回true
//==16的字符表示向右的箭头字符
return len(s) > 0 && s[len(s)-1] == 16
}
func decodeNibbles(nibbles []byte, bytes []byte) {
for bi, ni := 0, 0; ni < len(nibbles); bi, ni = bi+1, ni+2 {
// 按位或运算符 | 是双目运算符 参与运算的两数各对应的二进位相或,只要二进制位有一个1时,结果为就为1
bytes[bi] = nibbles[ni]<<4 | nibbles[ni+1]
}
}
//参数:hex字符数据 返回值
/**
参数:hex字符数组
返回值:字符数组
terminator:终结者
*/
//func main() {
// //hex := []byte{'a','b','c','d'}
// //hex := []byte{'a','b','c',' '}
// //hex := []byte{'1','2','3','4'}
// //compact := hexToCompact(hex)
// //fmt.Println(compact)//[0 114 116] [0 114 48]
// //fmt.Println(string(compact))// ?rt ?r0
// //toHex := keybytesToHex(hex)
// //fmt.Println(toHex)//[6 1 6 2 6 3 2 0 16]
// //fmt.Println(toHex)//[3 1 3 2 3 3 3 4 16]
//
// //for i, ele := range hex {
// // fmt.Println(i)
// // fmt.Println(ele)
// //}
//}
func hexToCompact(hex []byte) []byte {
terminator := byte(0)
if hasTerm(hex) {
//如果hex长度大于0,并且最后一位等于16(ascii表示向右箭头),
terminator = 1
//去掉hex数组的最后一位
hex = hex[:len(hex)-1]
}
//如果hex长度<=0,或者最后一位不等于16
//buf字符数组,长度为hex数组
buf := make([]byte, len(hex)/2+1)
//terminator+00000 二进制形式
buf[0] = terminator << 5 // the flag byte
//如果hex的长度等于1
if len(hex)&1 == 1 {
//buf[0] = 二进制 10000 = 十进制 16
//buf[0]的上半个字节等于 16
buf[0] |= 1 << 4 // odd flag ---> 16
//buf[0]的下半个字节等于 hex[0]
buf[0] |= hex[0] // first nibble is contained in the first byte
//hex将索引为0的元素去掉
hex = hex[1:]
}
decodeNibbles(hex, buf[1:])
return buf
}
func compactToHex(compact []byte) []byte {
//调用keybytesToHex方法对compact字符数组进行运算,获得最后一位=16(ascii表示向右箭头),且长度为compact*2+1的数组base
base := keybytesToHex(compact)
//去掉base数组的最后一位(也就是=16的元素)
base = base[:len(base)-1]
// apply terminator flag
if base[0] >= 2 { // TODO 先将keybytesToHex输出的末尾结束标志删除后，再通过判断头半个字节的标志位t加回去。操作冗余
base = append(base, 16)
}
// apply odd flag
//base[0]与1进行按位与运算
chop := 2 - base[0]&1
return base[chop:]
}
//nibbles 半字节
/**
- 参数 : str字符数组
*/
func keybytesToHex(str []byte) []byte {
l := len(str)*2 + 1
//初始化一个长度为l的nibbles数组
var nibbles = make([]byte, l)
//遍历str数组 i:索引 b:元素数值
for i, b := range str {
nibbles[i*2] = b / 16
nibbles[i*2+1] = b % 16
}
//数组最后一位等于16 对应ascii的空字符
nibbles[l-1] = 16
return nibbles
}
// hexToKeybytes turns hex nibbles into key bytes.
// This can only be used for keys of even(偶数) length.
func hexToKeybytes(hex []byte) []byte {
if hasTerm(hex) {
//去掉hex的最后一位
hex = hex[:len(hex)-1]
}
if len(hex)&1 != 0 {
panic("can't convert hex key of odd length")
}
//???长度+1再除2 需要保证长度为奇数
key := make([]byte, (len(hex)+1)/2) // TODO 对于一个已经判断为偶数的len(hex)在整除2的同时加1，为无效的+1逻辑
decodeNibbles(hex, key)
return key
}
// prefixLen returns the length of the common prefix(字首) of a and b.
//返回a和b共同的首字符(也就是前面相等位数的字符个数)
func prefixLen(a, b []byte) int {
var i, length = 0, len(a)
//将a和b的长度相等
if len(b) < length {
length = len(b)
}
//记录a和b相等元素的个数,不相等就跳出
for ; i < length; i++ {
if a[i] != b[i] {
break
}
}
return i
}
//func main() {
// arr1 := []byte{'a','b','c','d'}
// arr2 := []byte{'a','b','c','f'}
// i := prefixLen(arr1, arr2)
// fmt.Println(i)
//}
网友评论