frames

Documentation

Overview

Package frames describes the Frame interface. A set of standard frames are also defined in this package. These are: Fixed, Window, Wild and WildMin.

Index

• Variables
• func NonZero(f Frame) bool
• func TotalLength(f Frame) int
• type Block
  • func (bl *Block) Equals(pat patterns.Pattern) bool
  • func (bl *Block) Length() (int, int)
  • func (bl *Block) NumSequences() int
  • func (bl *Block) Save(ls *persist.LoadSaver)
  • func (bl *Block) Sequences() []patterns.Sequence
  • func (bl *Block) String() string
  • func (bl *Block) Test(b []byte) ([]int, int)
  • func (bl *Block) TestR(b []byte) ([]int, int)
• type Frame
  • func BMHConvert(fs []Frame, rev bool) []Frame
  • func Load(ls *persist.LoadSaver) Frame
  • func NewFrame(typ OffType, pat patterns.Pattern, offsets ...int) Frame
  • func SwitchFrame(f Frame, p patterns.Pattern) Frame
  • func (f Frame) Equals(f1 Frame) bool
  • func (f Frame) Linked(prev Frame, maxDistance, maxRange int) (bool, int, int)
  • func (f Frame) Match(b []byte) []int
  • func (f Frame) MatchN(b []byte, n int) (int, int)
  • func (f Frame) MatchNR(b []byte, n int) (int, int)
  • func (f Frame) MatchR(b []byte) []int
  • func (f Frame) MaxMatches(l int) (int, int, int)
  • func (f Frame) Save(ls *persist.LoadSaver)
  • func (f Frame) String() string
• type Machine
  • func (m Machine) Equals(pat patterns.Pattern) bool
  • func (m Machine) Length() (int, int)
  • func (m Machine) NumSequences() int
  • func (m Machine) Save(ls *persist.LoadSaver)
  • func (m Machine) Sequences() []patterns.Sequence
  • func (m Machine) String() string
  • func (m Machine) Test(b []byte) ([]int, int)
  • func (m Machine) TestR(b []byte) ([]int, int)
• type OffType
  • func (o OffType) Orientation() OffType
  • func (o OffType) SwitchOff() OffType
• type Position
  • func BOFLength(seg Signature, max int) Position
  • func EOFLength(seg Signature, max int) Position
  • func VarLength(seg Signature, max int) Position
  • func (p Position) String() string
• type Sequencer
  • func NewSequencer(rev bool) Sequencer
• type SigType
• type Signature
  • func Blockify(seg Signature) Signature
  • func (seg Signature) Characterise() SigType
  • func (s Signature) Contains(s1 Signature) bool
  • func (s Signature) Equals(s1 Signature) bool
  • func (s Signature) Mirror() Signature
  • func (s Signature) OneEnough() bool
  • func (s Signature) Segment(dist, rng, cost, repetition int) []Signature
  • func (s Signature) String() string

Variables

var OffString = [...]string{"B", "P", "S", "E"}

OffString is an exported array of strings representing each of the four offset types

Functions

func NonZero

func NonZero(f Frame) bool

NonZero checks whether, when converted to simple byte sequences, this frame's pattern is all 0 bytes.

func TotalLength

func TotalLength(f Frame) int

TotalLength is sum of the maximum length of the enclosed pattern and the maximum offset.

Types

type Block

type Block struct {
	L    []Frame
	R    []Frame
	Key  patterns.Pattern
	Le   int // Pattern length
	Off  int // fixed offset of the Key, relative to the first frame in the block
	OffR int // fixed offset of the Key, relative to the last frame in the block
}

Block combines Frames that are linked to each other by a fixed offset into a single Pattern Patterns within a block must have a single length (i.e. no Choice patterns with varying lengths). Blocks are used within the Machine pattern to cluster frames to identify repetitions & optimise searching.

func (*Block) Equals

func (bl *Block) Equals(pat patterns.Pattern) bool

func (*Block) Length

func (bl *Block) Length() (int, int)

func (*Block) NumSequences

func (bl *Block) NumSequences() int

Blocks are used where sequence matching inefficient

func (*Block) Save

func (bl *Block) Save(ls *persist.LoadSaver)

func (*Block) Sequences

func (bl *Block) Sequences() []patterns.Sequence

func (*Block) String

func (bl *Block) String() string

func (*Block) Test

func (bl *Block) Test(b []byte) ([]int, int)

func (*Block) TestR

func (bl *Block) TestR(b []byte) ([]int, int)

type Frame

type Frame struct {
	Min int
	Max int
	OffType
	patterns.Pattern
}

Frame encapsulates a pattern with offset information, mediating between the pattern and the bytestream.

func BMHConvert

func BMHConvert(fs []Frame, rev bool) []Frame

BMHConvert converts the patterns within a slice of frames to BMH sequences if possible.

func Load

func Load(ls *persist.LoadSaver) Frame

func NewFrame

func NewFrame(typ OffType, pat patterns.Pattern, offsets ...int) Frame

NewFrame generates Fixed, Window, Wild and WildMin frames. The offsets argument controls what type of frame is created:

• for a Wild frame, give no offsets or give a max offset of < 0 and a min of < 1
• for a WildMin frame, give one offset, or give a max offset of < 0 and a min of > 0
• for a Fixed frame, give two offsets that are both >= 0 and that are equal to each other
• for a Window frame, give two offsets that are both >= 0 and that are not equal to each other.

func SwitchFrame

func SwitchFrame(f Frame, p patterns.Pattern) Frame

SwitchFrame returns a new frame with a different orientation (for example to allow right-left searching).

func (Frame) Equals

func (f Frame) Equals(f1 Frame) bool

func (Frame) Linked

func (f Frame) Linked(prev Frame, maxDistance, maxRange int) (bool, int, int)

Linked tests whether a frame is linked to a preceding frame (by a preceding or succeding relationship) with an offset and range that is less than the supplied ints. If -1 is given for maxDistance & maxRange, then will check if frame is linked to a preceding frame via a PREV or SUCC relationship. If -1 is given for maxDistance, but not maxRange, then will check if frame linked without regard to distance (only range), this is useful because if give maxRange of 0 you can tell if it is a fixed relationship

func (Frame) Match

func (f Frame) Match(b []byte) []int

Match the enclosed pattern against the byte slice in a L-R direction. Returns a slice of offsets for where a successive match by a related frame should begin.

func (Frame) MatchN

func (f Frame) MatchN(b []byte, n int) (int, int)

For the nth match (per above), return the offset for successive match by related frame and bytes that can advance to make a successive test by this frame.

func (Frame) MatchNR

func (f Frame) MatchNR(b []byte, n int) (int, int)

For the nth match (per above), return the offset for successive match by related frame and bytes that can advance to make a successive test by this frame.

func (Frame) MatchR

func (f Frame) MatchR(b []byte) []int

Match the enclosed pattern against the byte slice in a reverse (R-L) direction. Returns a slice of offsets for where a successive match by a related frame should begin.

func (Frame) MaxMatches

func (f Frame) MaxMatches(l int) (int, int, int)

MaxMatches returns:

• the max number of times a frame can match, given a byte slice of length 'l'
• the maximum remaining slice length
• the minimum length of a successful pattern match

func (Frame) Save

func (f Frame) Save(ls *persist.LoadSaver)

func (Frame) String

func (f Frame) String() string

type Machine

type Machine Signature

A Machine is a segment of a signature that implements the patterns interface

func (Machine) Equals

func (m Machine) Equals(pat patterns.Pattern) bool

func (Machine) Length

func (m Machine) Length() (int, int)

func (Machine) NumSequences

func (m Machine) NumSequences() int

Machines are used where sequence matching inefficient

func (Machine) Save

func (m Machine) Save(ls *persist.LoadSaver)

func (Machine) Sequences

func (m Machine) Sequences() []patterns.Sequence

func (Machine) String

func (m Machine) String() string

func (Machine) Test

func (m Machine) Test(b []byte) ([]int, int)

func (Machine) TestR

func (m Machine) TestR(b []byte) ([]int, int)

type OffType

type OffType uint8

OffType is the type of offset

const (
	BOF  OffType = iota // beginning of file offset
	PREV                // offset from previous frame
	SUCC                // offset from successive frame
	EOF                 // end of file offset
)

Four offset types are supported

func (OffType) Orientation

func (o OffType) Orientation() OffType

Orientation returns the offset type of the frame which must be either BOF, PREV, SUCC or EOF

func (OffType) SwitchOff

func (o OffType) SwitchOff() OffType

SwitchOff returns a new offset type according to a given set of rules. These are:

• PREV -> SUCC
• SUCC and EOF -> PREV

This is helpful when changing the orientation of a frame (for example to allow right-left searching).

type Position

type Position struct {
	Length int
	Start  int
	End    int
}

position of a key frame in a segment: the length (minimum length in bytes), start and end indexes. The keyframe can span multiple frames in the segment (if they are immediately adjacent and can make sequences) which is why there is a start and end index If length is 0, the segment goes to the frame matcher

func BOFLength

func BOFLength(seg Signature, max int) Position

func EOFLength

func EOFLength(seg Signature, max int) Position

func VarLength

func VarLength(seg Signature, max int) Position

func (Position) String

func (p Position) String() string

type Sequencer

type Sequencer func(Frame) [][]byte

Sequencer turns sequential frames into a set of plain byte sequences. The set represents possible choices.

func NewSequencer

func NewSequencer(rev bool) Sequencer

NewSequencer creates a Sequencer (reversed if true).

type SigType

type SigType int

const (
	Unknown   SigType = iota
	BOFZero           // fixed offset, zero length from BOF
	BOFWindow         // offset is a window or fixed value greater than zero from BOF
	BOFWild
	Prev
	Succ
	EOFZero
	EOFWindow
	EOFWild
)

type Signature

type Signature []Frame

Signature is just a slice of frames.

func Blockify

func Blockify(seg Signature) Signature

Blockify takes a signature segment, identifies any blocks within (frames linked by fixed offsets), converts those frames to block patterns within window frames (the window frame of the first frame in the block), but with a new length), and returns a new segment. If no blocks are within a segment, the original segment will be returned.

func (Signature) Characterise

func (seg Signature) Characterise() SigType

Simple characterisation of a segment: is it relative to the BOF, or the EOF, or is it a prev/succ segment.

func (Signature) Contains

func (s Signature) Contains(s1 Signature) bool

Contains tests whether a signature wholly contains the segments of another signature.

func (Signature) Equals

func (s Signature) Equals(s1 Signature) bool

Equals tests equality of two signatures.

func (Signature) Mirror

func (s Signature) Mirror() Signature

Mirror returns a signature in which wildcard previous segments are turned into wildcard succ/eof segments. If no wildcard previous segments are present, nil is returned.

func (Signature) OneEnough

func (s Signature) OneEnough() bool

func (Signature) Segment

func (s Signature) Segment(dist, rng, cost, repetition int) []Signature

func (Signature) String

func (s Signature) String() string