-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.ts
148 lines (140 loc) · 4.58 KB
/
index.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
146
147
148
import { Buffer } from "buffer";
type callback = (isMatch: boolean, data?: Buffer) => void;
class StreamSearch {
private pos!: number;
private lookback!: Buffer[];
needle!: Buffer;
private nLen!: number;
private nLast!: number;
private move!: number[];
private cb!: callback;
constructor(needle: Buffer, cb: callback) {
if (typeof cb !== "function") {
throw new Error("Missing match callback");
}
this.init();
this.setNeedle(needle);
this.cb = cb;
}
init() {
this.pos = 0;
this.lookback = [];
}
setNeedle(needle: Buffer) {
if (!Buffer.isBuffer(needle)) {
throw new Error(`Expected Buffer for needle, got ${typeof needle}`);
}
if (!needle.length) {
throw new Error(`Empty Buffer`);
}
this.needle = needle;
this.nLen = this.needle.length;
this.nLast = this.nLen - 1;
this.move = new Array(256).fill(this.nLen);
for (let i = 0; i < this.nLast; i++) {
this.move[this.needle[i]] = this.nLast - i;
}
}
push(chunk: Buffer) {
if (!chunk) {
return;
}
let offset = 0;
while (this.pos <= chunk.length - this.nLen) {
if (this.pos < 0) {
let i = this.pos;
let j = 0;
// chunk[i] 一定不会溢出,因为 i 最多只会增加 this.nLen - 1 且 this.pos + this.nLen - 1 <= chunk.length - 1(最外层 while 循环的判断条件的变换)
while (j < this.nLen && this.needle[j] === (i < 0 ? this.lookbackAt(i) : chunk[i])) {
i++;
j++;
}
if (j === this.nLen) {
this.lookbackUnload(this.pos);
this.pos += this.nLen;
offset = this.pos;
this.cb(true);
} else {
// chunk[this.pos + this.nLast] 一定不会溢出,因为 this.pos + this.nLen - 1 >=0(断言 this.pos > -this.nLen 的变换,参考底部注释)
this.pos += this.move[chunk[this.pos + this.nLast]];
this.lookbackShift(this.pos);
}
} else {
const idx = chunk.indexOf(this.needle, this.pos);
if (idx !== -1) {
idx !== offset && this.cb(false, chunk.subarray(offset, idx));
this.pos = idx + this.nLen;
offset = this.pos;
this.cb(true);
} else {
const end = chunk.length - 1;
const start = end - this.nLast;
this.pos = start + this.move[chunk[end]];
}
}
}
const remain = chunk.subarray(offset);
if (remain.length) {
// 如果下轮匹配的起点还在 chunk 之中,则把 chunk 放入 lookback 中,否则说明该 chunk 再也用不上了,可以直接回调出去了
this.pos < chunk.length ? this.lookback.push(remain) : this.cb(false, remain);
}
// 能执行到此处,说明上面的 while 循环的判断条件已不满足
// 即: this.pos > chunk.length - this.nLen
// 把 this.pos 减少 chunk.length 后: this.pos > -this.nLen
// 又因为 while 循环中 this.pos 只会增加不会减少,所以 this.pos 的值任何时候都是大于 -this.nLen
this.pos -= chunk.length;
}
end() {
while (this.lookback.length) {
this.cb(false, this.lookback.shift());
}
}
private lookbackAt(idx: number) {
// idx < 0
for (let i = this.lookback.length - 1, offset = 0; i > -1; i--) {
const chunk = this.lookback[i];
offset -= chunk.length;
if (offset <= idx) {
return chunk[idx - offset];
}
}
}
private lookbackShift(idx: number) {
// idx 不一定小于 0
if (idx >= 0) {
while (this.lookback.length) {
this.cb(false, this.lookback.shift());
}
return;
}
for (let i = this.lookback.length - 1, offset = 0, shift = false; i > -1; i--) {
if (shift) {
this.cb(false, this.lookback.shift());
} else {
const chunk = this.lookback[i];
offset -= chunk.length;
shift = offset <= idx;
}
}
}
private lookbackUnload(idx: number) {
// idx < 0
let lastChunk;
for (let i = this.lookback.length - 1, offset = 0, shift = false; i > -1; i--) {
if (shift) {
this.cb(false, this.lookback.shift());
} else {
const chunk = this.lookback[i];
offset -= chunk.length;
shift = offset <= idx;
if (shift && idx !== offset) {
lastChunk = chunk.subarray(0, idx - offset);
}
}
}
lastChunk && this.cb(false, lastChunk);
// 因为 this.pos > -this.nLen,且下一轮匹配的 this.pos 会跳过 needle,所以下轮的 this.pos 必然大于0,所以 lookback 可以清空了
this.lookback = [];
}
}
export = StreamSearch;