From 2db74de1779f4e0689fbb05941f65d06ef248e8c Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 9 Jan 2017 22:48:46 -0800 Subject: [PATCH] dfa: shrink constraints from 4 bits to 3 * lib/dfa.c (newline_constraint, letter_constraint) (other_constraint, prev_newline_dependent) (prev_letter_dependent, NO_CONSTRAINT, BEGLINE_CONSTRAINT) (ENDLINE_CONSTRAINT, BEGWORD_CONSTRAINT, ENDWORD_CONSTRAINT) (LIMWORD_CONSTRAINT, NOTLIMWORD_CONSTRAINT): Constraints need only 3 bits, not 4. Using smaller integers shrinks the code a bit and makes grep a tad faster on x86-64. --- ChangeLog | 9 +++++++++ lib/dfa.c | 32 ++++++++++++++++---------------- 2 files changed, 25 insertions(+), 16 deletions(-) diff --git a/ChangeLog b/ChangeLog index 91cdc6d31e..e0b73b50be 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,14 @@ 2017-01-09 Paul Eggert + dfa: shrink constraints from 4 bits to 3 + * lib/dfa.c (newline_constraint, letter_constraint) + (other_constraint, prev_newline_dependent) + (prev_letter_dependent, NO_CONSTRAINT, BEGLINE_CONSTRAINT) + (ENDLINE_CONSTRAINT, BEGWORD_CONSTRAINT, ENDWORD_CONSTRAINT) + (LIMWORD_CONSTRAINT, NOTLIMWORD_CONSTRAINT): + Constraints need only 3 bits, not 4. Using smaller integers + shrinks the code a bit and makes grep a tad faster on x86-64. + dfa: omit unnecessary ptrdiff_t check * lib/dfa.c (alloc_position_set): Do not worry about ptrdiff_t overflow, since xnmalloc does that now. diff --git a/lib/dfa.c b/lib/dfa.c index 509d6d1cbd..28678c2327 100644 --- a/lib/dfa.c +++ b/lib/dfa.c @@ -137,13 +137,13 @@ enum /* Sometimes characters can only be matched depending on the surrounding context. Such context decisions depend on what the previous character was, and the value of the current (lookahead) character. Context - dependent constraints are encoded as 12-bit integers. Each bit that + dependent constraints are encoded as 9-bit integers. Each bit that is set indicates that the constraint succeeds in the corresponding context. - bit 8-11 - valid contexts when next character is CTX_NEWLINE - bit 4-7 - valid contexts when next character is CTX_LETTER - bit 0-3 - valid contexts when next character is CTX_NONE + bit 6-8 - valid contexts when next character is CTX_NEWLINE + bit 3-5 - valid contexts when next character is CTX_LETTER + bit 0-2 - valid contexts when next character is CTX_NONE succeeds_in_context determines whether a given constraint succeeds in a particular context. Prev is a bitmask of possible @@ -152,17 +152,17 @@ enum static int newline_constraint (int constraint) { - return (constraint >> 8) & 0xf; + return (constraint >> 6) & 7; } static int letter_constraint (int constraint) { - return (constraint >> 4) & 0xf; + return (constraint >> 3) & 7; } static int other_constraint (int constraint) { - return constraint & 0xf; + return constraint & 7; } static bool @@ -178,12 +178,12 @@ succeeds_in_context (int constraint, int prev, int curr) static bool prev_newline_dependent (int constraint) { - return ((constraint ^ constraint >> 2) & 0x111) != 0; + return ((constraint ^ constraint >> 2) & 0111) != 0; } static bool prev_letter_dependent (int constraint) { - return ((constraint ^ constraint >> 1) & 0x111) != 0; + return ((constraint ^ constraint >> 1) & 0111) != 0; } /* Tokens that match the empty string subject to some constraint actually @@ -192,13 +192,13 @@ prev_letter_dependent (int constraint) the constraints corresponding to the special tokens previously defined. */ enum { - NO_CONSTRAINT = 0x777, - BEGLINE_CONSTRAINT = 0x444, - ENDLINE_CONSTRAINT = 0x700, - BEGWORD_CONSTRAINT = 0x050, - ENDWORD_CONSTRAINT = 0x202, - LIMWORD_CONSTRAINT = 0x252, - NOTLIMWORD_CONSTRAINT = 0x525 + NO_CONSTRAINT = 0777, + BEGLINE_CONSTRAINT = 0444, + ENDLINE_CONSTRAINT = 0700, + BEGWORD_CONSTRAINT = 0050, + ENDWORD_CONSTRAINT = 0202, + LIMWORD_CONSTRAINT = 0252, + NOTLIMWORD_CONSTRAINT = 0525 }; /* The regexp is parsed into an array of tokens in postfix form. Some tokens -- 2.39.5