-
Notifications
You must be signed in to change notification settings - Fork 403
/
util.ts
145 lines (133 loc) · 3.48 KB
/
util.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
import { CID } from 'multiformats'
import * as uint8arrays from 'uint8arrays'
import { ReadableBlockstore } from '../storage'
import { sha256 } from '@atproto/crypto'
import { MST, Leaf, NodeEntry, NodeData, MstOpts } from './mst'
import { cidForCbor } from '@atproto/common'
export const leadingZerosOnHash = async (key: string | Uint8Array) => {
const hash = await sha256(key)
let leadingZeros = 0
for (let i = 0; i < hash.length; i++) {
const byte = hash[i]
if (byte < 64) leadingZeros++
if (byte < 16) leadingZeros++
if (byte < 4) leadingZeros++
if (byte === 0) {
leadingZeros++
} else {
break
}
}
return leadingZeros
}
export const layerForEntries = async (
entries: NodeEntry[],
): Promise<number | null> => {
const firstLeaf = entries.find((entry) => entry.isLeaf())
if (!firstLeaf || firstLeaf.isTree()) return null
return await leadingZerosOnHash(firstLeaf.key)
}
export const deserializeNodeData = async (
storage: ReadableBlockstore,
data: NodeData,
opts?: Partial<MstOpts>,
): Promise<NodeEntry[]> => {
const { layer } = opts || {}
const entries: NodeEntry[] = []
if (data.l !== null) {
entries.push(
await MST.load(storage, data.l, {
layer: layer ? layer - 1 : undefined,
}),
)
}
let lastKey = ''
for (const entry of data.e) {
const keyStr = uint8arrays.toString(entry.k, 'ascii')
const key = lastKey.slice(0, entry.p) + keyStr
ensureValidMstKey(key)
entries.push(new Leaf(key, entry.v))
lastKey = key
if (entry.t !== null) {
entries.push(
await MST.load(storage, entry.t, {
layer: layer ? layer - 1 : undefined,
}),
)
}
}
return entries
}
export const serializeNodeData = (entries: NodeEntry[]): NodeData => {
const data: NodeData = {
l: null,
e: [],
}
let i = 0
if (entries[0]?.isTree()) {
i++
data.l = entries[0].pointer
}
let lastKey = ''
while (i < entries.length) {
const leaf = entries[i]
const next = entries[i + 1]
if (!leaf.isLeaf()) {
throw new Error('Not a valid node: two subtrees next to each other')
}
i++
let subtree: CID | null = null
if (next?.isTree()) {
subtree = next.pointer
i++
}
ensureValidMstKey(leaf.key)
const prefixLen = countPrefixLen(lastKey, leaf.key)
data.e.push({
p: prefixLen,
k: uint8arrays.fromString(leaf.key.slice(prefixLen), 'ascii'),
v: leaf.value,
t: subtree,
})
lastKey = leaf.key
}
return data
}
export const countPrefixLen = (a: string, b: string): number => {
let i
for (i = 0; i < a.length; i++) {
if (a[i] !== b[i]) {
break
}
}
return i
}
export const cidForEntries = async (entries: NodeEntry[]): Promise<CID> => {
const data = serializeNodeData(entries)
return cidForCbor(data)
}
export const isValidMstKey = (str: string): boolean => {
const split = str.split('/')
return (
str.length <= 256 &&
split.length === 2 &&
split[0].length > 0 &&
split[1].length > 0 &&
isValidChars(split[0]) &&
isValidChars(split[1])
)
}
export const validCharsRegex = /^[a-zA-Z0-9_\-:.]*$/
export const isValidChars = (str: string): boolean => {
return str.match(validCharsRegex) !== null
}
export const ensureValidMstKey = (str: string) => {
if (!isValidMstKey(str)) {
throw new InvalidMstKeyError(str)
}
}
export class InvalidMstKeyError extends Error {
constructor(public key: string) {
super(`Not a valid MST key: ${key}`)
}
}