On 01/24/2013 07:22 PM, Seth Arnold wrote: > On Wed, Jan 16, 2013 at 01:28:46PM -0800, John Johansen wrote: >> Default differential encoding stores the current state's transitions as >> the difference of the default state's transitions. So for the current >> match (state and pos) if the state is diffentially encoded, transition to >> the default state without incrementing pos; >> >> Signed-off-by: John Johansen <[email protected]> > Acked-by: Seth Arnold <[email protected]> > >> @@ -154,6 +154,8 @@ static int verify_dfa(struct aa_dfa *dfa, int flags) >> } >> } >> >> + /* TODO: verify diff encode terminates */ >> + > > TODO: solve halting problem :) > > Though some kind of sanity checks would be nice.. > hehe, thankfully this isn't the halting problem, nor do you even have to check every state. A rough description is that the compression creates a DAG of the states and only ancestors are used as part of the diff encode (its a little more than that). This allows us to set a bounds on the number of states that will be used to traverse the differential encode, both for a match and for the verify.
The verify can actually of a bounds M, where M is the number of states. While the match worst case is is 2N+1 state traversals (iirc) where N is the length of the string being matched. However we don't require every state to be differential encoded so our average length is much closer to the optimal traversal of N states, while it gives us an average of about 50% more compression and actually even improving match speed is some cases because of hot paths and cacheline reuse. -- AppArmor mailing list [email protected] Modify settings or unsubscribe at: https://lists.ubuntu.com/mailman/listinfo/apparmor
