1interface SearchState {
2 readonly needle: Uint8Array
3 readonly needleLength: number
4 readonly indexes: Record<number, ReadonlyArray<number>>
5 readonly firstByte: number
6
7 previousChunk: Uint8Array | undefined
8 previousChunkLength: number
9 matchIndex: number
10}
11
12function makeState(needle_: string): SearchState {
13 const needle = new TextEncoder().encode(needle_)
14 const needleLength = needle.length
15
16 const indexes: Record<number, Array<number>> = {}
17 for (let i = 0; i < needleLength; i++) {
18 const b = needle[i]
19 if (indexes[b] === undefined) indexes[b] = []
20 indexes[b].push(i)
21 }
22
23 return {
24 needle,
25 needleLength,
26 indexes,
27 firstByte: needle[0],
28 previousChunk: undefined,
29 previousChunkLength: 0,
30 matchIndex: 0
31 }
32}
33
34export function make(
35 needle: string,
36 callback: (index: number, chunk: Uint8Array) => void,
37 seed?: Uint8Array,
38 minimumChunkLength?: number
39) {
40 const state = makeState(needle)
41 const minChunkLength = minimumChunkLength ?? state.needleLength
42 if (seed !== undefined) {
43 state.previousChunk = seed
44 state.previousChunkLength = seed.length
45 }
46
47 function makeIndexOf(): (
48 chunk: Uint8Array,
49 needle: Uint8Array,
50 fromIndex: number
51 ) => number {
52 // on node.js use the Buffer api
53 if (
54 "Buffer" in globalThis &&
55 !("Bun" in globalThis || "Deno" in globalThis)
56 ) {
57 return function(chunk, needle, fromIndex) {
58 return Buffer.prototype.indexOf.call(chunk, needle, fromIndex)
59 }
60 }
61
62 const skipTable = new Uint8Array(256).fill(state.needle.length)
63 for (let i = 0, lastIndex = state.needle.length - 1; i < lastIndex; ++i) {
64 skipTable[state.needle[i]] = lastIndex - i
65 }
66
67 return function(chunk, needle, fromIndex) {
68 const lengthTotal = chunk.length
69 let i = fromIndex + state.needleLength - 1
70
71 while (i < lengthTotal) {
72 for (
73 let j = state.needleLength - 1, k = i;
74 j >= 0 && chunk[k] === needle[j];
75 j--, k--
76 ) {
77 if (j === 0) return k
78 }
79 i += skipTable[chunk[i]]
80 }
81
82 return -1
83 }
84 }
85
86 const indexOf = makeIndexOf()
87
88 function write(chunk: Uint8Array): void {
89 let chunkLength = chunk.length
90
91 if (state.previousChunk !== undefined) {
92 const newChunk = new Uint8Array(state.previousChunkLength + chunkLength)
93 newChunk.set(state.previousChunk)
94 newChunk.set(chunk, state.previousChunkLength)
95 chunk = newChunk
96 chunkLength = state.previousChunkLength + chunkLength
97 state.previousChunk = undefined
98 }
99
100 let pos = 0
101 while (pos < chunkLength) {
102 const remaining = chunkLength - pos
103 if (remaining < minChunkLength) {
104 state.previousChunk = chunk.subarray(pos)
105 state.previousChunkLength = remaining
106 return
107 }
108
109 const match = indexOf(chunk, state.needle, pos)
110
111 if (match > -1) {
112 if (match > pos) {
113 callback(state.matchIndex, chunk.subarray(pos, match))
114 }
115 state.matchIndex += 1
116 pos = match + state.needleLength
117 continue
118 } else if (chunk[chunkLength - 1] in state.indexes) {
119 const indexes = state.indexes[chunk[chunkLength - 1]]
120 let earliestIndex = -1
121 for (let i = 0, len = indexes.length; i < len; i++) {
122 const index = indexes[i]
123 if (
124 chunk[chunkLength - 1 - index] === state.firstByte &&
125 i > earliestIndex
126 ) {
127 earliestIndex = index
128 }
129 }
130 if (earliestIndex === -1) {
131 if (pos === 0) {
132 callback(state.matchIndex, chunk)
133 } else {
134 callback(state.matchIndex, chunk.subarray(pos))
135 }
136 } else {
137 if (chunkLength - 1 - earliestIndex > pos) {
138 callback(
139 state.matchIndex,
140 chunk.subarray(pos, chunkLength - 1 - earliestIndex)
141 )
142 }
143 state.previousChunk = chunk.subarray(chunkLength - 1 - earliestIndex)
144 state.previousChunkLength = earliestIndex + 1
145 }
146 } else if (pos === 0) {
147 callback(state.matchIndex, chunk)
148 } else {
149 callback(state.matchIndex, chunk.subarray(pos))
150 }
151
152 break
153 }
154 }
155
156 function end(): void {
157 if (state.previousChunk !== undefined && state.previousChunk !== seed) {
158 callback(state.matchIndex, state.previousChunk)
159 }
160
161 state.previousChunk = seed
162 state.previousChunkLength = seed?.length ?? 0
163 state.matchIndex = 0
164 }
165
166 return { write, end } as const
167}