-
Notifications
You must be signed in to change notification settings - Fork 29
/
keyframes.go
438 lines (411 loc) · 12.1 KB
/
keyframes.go
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
// Copyright 2014 Richard Lehane. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package bytematcher
import (
"fmt"
"github.com/richardlehane/siegfried/config"
"github.com/richardlehane/siegfried/pkg/core/bytematcher/frames"
"github.com/richardlehane/siegfried/pkg/core/persist"
"github.com/richardlehane/siegfried/pkg/core/priority"
)
// positioning information: min/max offsets (in relation to BOF or EOF) and min/max lengths
type keyFramePos struct {
// Minimum and maximum position
pMin int64
pMax int64
// Minimum and maximum length
lMin int
lMax int
}
// Each segment in a signature is represented by a single keyFrame. A slice of keyFrames represents a full signature.
// The keyFrame includes the range of offsets that need to match for a successful hit.
// The segment (Seg) offsets are relative (to preceding/succeding segments or to BOF/EOF if the first or last segment).
// The keyframe (Key) offsets are absolute to the BOF or EOF.
type keyFrame struct {
typ frames.OffType // BOF|PREV|SUCC|EOF
seg keyFramePos // relative positioning info for segment as a whole (min/max length and offset in relation to BOF/EOF/PREV/SUCC)
key keyFramePos // absolute positioning info for keyFrame portion of segment (min/max length and offset in relation to BOF/EOF)
}
func loadKeyFrames(ls *persist.LoadSaver) [][]keyFrame {
kfs := make([][]keyFrame, ls.LoadSmallInt())
for i := range kfs {
kfs[i] = make([]keyFrame, ls.LoadSmallInt())
for j := range kfs[i] {
kfs[i][j].typ = frames.OffType(ls.LoadByte())
kfs[i][j].seg.pMin = int64(ls.LoadInt())
kfs[i][j].seg.pMax = int64(ls.LoadInt())
kfs[i][j].seg.lMin = ls.LoadSmallInt()
kfs[i][j].seg.lMax = ls.LoadSmallInt()
kfs[i][j].key.pMin = int64(ls.LoadInt())
kfs[i][j].key.pMax = int64(ls.LoadInt())
kfs[i][j].key.lMin = ls.LoadSmallInt()
kfs[i][j].key.lMax = ls.LoadSmallInt()
}
}
return kfs
}
func saveKeyFrames(ls *persist.LoadSaver, kfs [][]keyFrame) {
ls.SaveSmallInt(len(kfs))
for _, v := range kfs {
ls.SaveSmallInt(len(v))
for _, kf := range v {
ls.SaveByte(byte(kf.typ))
ls.SaveInt(int(kf.seg.pMin))
ls.SaveInt(int(kf.seg.pMax))
ls.SaveSmallInt(kf.seg.lMin)
ls.SaveSmallInt(kf.seg.lMax)
ls.SaveInt(int(kf.key.pMin))
ls.SaveInt(int(kf.key.pMax))
ls.SaveSmallInt(kf.key.lMin)
ls.SaveSmallInt(kf.key.lMax)
}
}
}
func (kf keyFrame) String() string {
return fmt.Sprintf("%s Seg Min:%d Seg Max:%d; Abs Min:%d Abs Max:%d", frames.OffString[kf.typ], kf.seg.pMin, kf.seg.pMax, kf.key.pMin, kf.key.pMax)
}
// A double index: the first int is for the signature's position within the set of all signatures,
// the second int is for the keyFrames position within the segments of the signature.
type keyFrameID [2]int
func (kf keyFrameID) String() string {
return fmt.Sprintf("[%d:%d]", kf[0], kf[1])
}
type kfFilter struct {
idx int
fdx int
kfs []keyFrameID
nfs []keyFrameID
}
func (k *kfFilter) Next() int {
if k.idx >= len(k.kfs) {
return -1
}
k.idx++
return k.kfs[k.idx-1][0]
}
func (k *kfFilter) Mark(t bool) {
if t {
k.nfs[k.fdx] = k.kfs[k.idx-1]
k.fdx++
}
}
func filterKF(kfs []keyFrameID, ws *priority.WaitSet) []keyFrameID {
f := &kfFilter{kfs: kfs, nfs: make([]keyFrameID, len(kfs))}
ws.ApplyFilter(f)
return f.nfs[:f.fdx]
}
// Turn a signature segment into a keyFrame and left and right frame slices.
// The left and right frame slices are converted into BMH sequences where possible
func toKeyFrame(seg frames.Signature, pos position) (keyFrame, []frames.Frame, []frames.Frame) {
var left, right []frames.Frame
var typ frames.OffType
var segPos, keyPos keyFramePos
segPos.lMin, segPos.lMax = calcLen(seg)
keyPos.lMin, keyPos.lMax = calcLen(seg[pos.start:pos.end])
// BOF and PREV segments
if seg[0].Orientation() < frames.SUCC {
typ, segPos.pMin, segPos.pMax = seg[0].Orientation(), int64(seg[0].Min()), int64(seg[0].Max())
keyPos.pMin, keyPos.pMax = segPos.pMin, segPos.pMax
for i, f := range seg[:pos.start+1] {
if pos.start > i {
min, max := f.Length()
keyPos.pMin += int64(min)
keyPos.pMin += int64(seg[i+1].Min())
if keyPos.pMax > -1 {
keyPos.pMax += int64(max)
keyPos.pMax += int64(seg[i+1].Max())
}
left = append([]frames.Frame{frames.SwitchFrame(seg[i+1], f.Pat())}, left...)
}
}
if pos.end < len(seg) {
right = seg[pos.end:]
}
return keyFrame{typ, segPos, keyPos}, frames.BMHConvert(left, true), frames.BMHConvert(right, false)
}
// EOF and SUCC segments
typ, segPos.pMin, segPos.pMax = seg[len(seg)-1].Orientation(), int64(seg[len(seg)-1].Min()), int64(seg[len(seg)-1].Max())
keyPos.pMin, keyPos.pMax = segPos.pMin, segPos.pMax
if pos.end < len(seg) {
for i, f := range seg[pos.end:] {
min, max := f.Length()
keyPos.pMin += int64(min)
keyPos.pMin += int64(seg[pos.end+i-1].Min())
if keyPos.pMax > -1 {
keyPos.pMax += int64(max)
keyPos.pMax += int64(seg[pos.end+i-1].Max())
}
right = append(right, frames.SwitchFrame(seg[pos.end+i-1], f.Pat()))
}
}
for _, f := range seg[:pos.start] {
left = append([]frames.Frame{f}, left...)
}
return keyFrame{typ, segPos, keyPos}, frames.BMHConvert(left, true), frames.BMHConvert(right, false)
}
// calculate minimum and maximum lengths for a segment (slice of frames)
func calcLen(fs []frames.Frame) (int, int) {
var min, max int
if fs[0].Orientation() < frames.SUCC {
for i, f := range fs {
fmin, fmax := f.Length()
min += fmin
max += fmax
if i > 0 {
min += f.Min()
max += f.Max()
}
}
return min, max
}
for i := len(fs) - 1; i > -1; i-- {
f := fs[i]
fmin, fmax := f.Length()
min += fmin
max += fmax
if i < len(fs)-1 {
min += f.Min()
max += f.Max()
}
}
return min, max
}
func calcMinMax(min, max int64, sp keyFramePos) (int64, int64) {
min = min + sp.pMin + int64(sp.lMin)
if max < 0 || sp.pMax < 0 {
return min, -1
}
max = max + sp.pMax + int64(sp.lMax)
return min, max
}
// update the absolute positional information (distance from the BOF or EOF)
// for keyFrames based on the other keyFrames in the signature
func updatePositions(ks []keyFrame) {
var min, max int64
// first forwards, for BOF and PREV
for i := range ks {
if ks[i].typ == frames.BOF {
min, max = calcMinMax(0, 0, ks[i].seg)
// Apply max bof
if config.MaxBOF() > 0 {
if ks[i].key.pMax < 0 || ks[i].key.pMax > int64(config.MaxBOF()) {
ks[i].key.pMax = int64(config.MaxBOF())
}
}
}
if ks[i].typ == frames.PREV {
ks[i].key.pMin = min + ks[i].key.pMin
if max > -1 && ks[i].key.pMax > -1 {
ks[i].key.pMax = max + ks[i].key.pMax
} else {
ks[i].key.pMax = -1
}
min, max = calcMinMax(min, max, ks[i].seg)
// Apply max bof
if config.MaxBOF() > 0 {
if ks[i].key.pMax < 0 || ks[i].key.pMax > int64(config.MaxBOF()) {
ks[i].key.pMax = int64(config.MaxBOF())
}
}
}
}
// now backwards for EOF and SUCC
min, max = 0, 0
for i := len(ks) - 1; i >= 0; i-- {
if ks[i].typ == frames.EOF {
min, max = calcMinMax(0, 0, ks[i].seg)
// apply max eof
if config.MaxEOF() > 0 {
if ks[i].key.pMax < 0 || ks[i].key.pMax > int64(config.MaxEOF()) {
ks[i].key.pMax = int64(config.MaxEOF())
}
}
}
if ks[i].typ == frames.SUCC {
ks[i].key.pMin = min + ks[i].key.pMin
if max > -1 && ks[i].key.pMax > -1 {
ks[i].key.pMax = max + ks[i].key.pMax
} else {
ks[i].key.pMax = -1
}
min, max = calcMinMax(min, max, ks[i].seg)
// apply max eof
if config.MaxEOF() > 0 {
if ks[i].key.pMax < 0 || ks[i].key.pMax > int64(config.MaxEOF()) {
ks[i].key.pMax = int64(config.MaxEOF())
}
}
}
}
}
// for doing a running total of the firstBOF and firstEOF:
func firstBOFandEOF(bof int, eof int, ks []keyFrame) (int, int) {
if bof < 0 {
return bof, eof
}
b := getMax(-1, func(t frames.OffType) bool { return t == frames.BOF }, ks, true)
if b < 0 || b > bof {
e := getMax(-1, func(t frames.OffType) bool { return t == frames.EOF }, ks, true)
if e < 0 {
if b < 0 {
return -1, -1
}
return b, eof
}
if e > eof {
if b < 0 || b > e {
return bof, e
}
return b, eof
}
}
return bof, eof
}
func getMax(max int, t func(frames.OffType) bool, ks []keyFrame, localMin bool) int {
for _, v := range ks {
if t(v.typ) {
if v.key.pMax < 0 {
if !localMin {
return -1
}
continue
}
this := int(v.key.pMax) + v.key.lMax
if localMin {
if max < 0 || this < max {
max = this
}
} else if this > max {
max = this
}
}
}
return max
}
// for doing a running total of the maxBOF:
// is the maxBOF we already have, further from the BOF than the maxBOF of the current signature?
func maxBOF(max int, ks []keyFrame) int {
if max < 0 {
return max
}
return getMax(max, func(t frames.OffType) bool { return t < frames.SUCC }, ks, false)
}
func maxEOF(max int, ks []keyFrame) int {
if max < 0 {
return max
}
return getMax(max, func(t frames.OffType) bool { return t > frames.PREV }, ks, false)
}
func crossOver(a, b keyFrame) bool {
if a.key.pMax == -1 {
return true
}
if a.key.pMax+int64(a.key.lMax) > b.key.pMin {
return true
}
return false
}
// quick check performed before applying a keyFrame ID
func (kf keyFrame) check(o int64) bool {
if kf.key.pMin > o {
return false
}
if kf.key.pMax == -1 {
return true
}
if kf.key.pMax < o {
return false
}
return true
}
// can we gather just a single hit for this keyframe?
func oneEnough(id int, kfs []keyFrame) bool {
kf := kfs[id]
// if this is a BOF frame or a wild PREV frame we can ...
if kf.typ == frames.BOF || (kf.typ == frames.PREV && kf.seg.pMax == -1 && kf.seg.pMin == 0) {
// unless this isn't the last frame and the next frame is a non-wild PREV frame
if id+1 < len(kfs) {
next := kfs[id+1]
if next.typ == frames.PREV && (next.seg.pMax > -1 || next.seg.pMin > 0) {
return false
}
}
return true
}
// if this is an EOF frame or SUCC frame we can ...
if id > 0 {
// so long as there isn't a previous frame that is a non-wild SUCC frame
prev := kfs[id-1]
if prev.typ == frames.SUCC && (prev.seg.pMax > -1 || prev.seg.pMin > 0) {
return false
}
}
return true
}
// test two key frames (current and previous) to see if they are connected and, if so, at what offsets
func (kf keyFrame) checkRelated(prevKf, nextKf keyFrame, thisOff, prevOff [][2]int64) ([][2]int64, bool) {
switch kf.typ {
case frames.BOF:
return thisOff, true
case frames.EOF, frames.SUCC:
if prevKf.typ == frames.SUCC && !(prevKf.seg.pMax == -1 && prevKf.seg.pMin == 0) {
ret := make([][2]int64, 0, len(thisOff))
success := false
for _, v := range thisOff {
for _, v1 := range prevOff {
dif := v[0] - v1[0] - v1[1]
if dif > -1 {
if dif < prevKf.seg.pMin || (prevKf.seg.pMax > -1 && dif > prevKf.seg.pMax) {
continue
} else {
ret = append(ret, v)
success = true
// if this type is EOF, we only need one match
if kf.typ == frames.EOF {
return ret, success
}
}
}
}
}
return ret, success
} else {
return thisOff, true
}
default:
if kf.seg.pMax == -1 && kf.seg.pMin == 0 {
return thisOff, true
}
ret := make([][2]int64, 0, len(thisOff))
success := false
for _, v := range thisOff {
for _, v1 := range prevOff {
dif := v[0] - v1[0] - v1[1] // current offset, minus previous offset, minus previous length
if dif > -1 {
if dif < kf.seg.pMin || (kf.seg.pMax > -1 && dif > kf.seg.pMax) {
continue
} else {
ret = append(ret, v)
success = true
// if the next type isn't a non-wild PREV, we only need one match
if nextKf.typ != frames.PREV || (nextKf.seg.pMax == -1 && nextKf.seg.pMin == 0) {
return ret, success
}
}
}
}
}
return ret, success
}
}