Discussion:
[PATCH 2/4] dfa: omit unnecessary ptrdiff_t check
(too old to reply)
Paul Eggert
2017-01-10 10:13:30 UTC
Permalink
Raw Message
* lib/dfa.c (alloc_position_set): Do not worry about ptrdiff_t
overflow, since xnmalloc does that now.
---
ChangeLog | 4 ++++
lib/dfa.c | 2 --
2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index beeefb7..91cdc6d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
2017-01-09 Paul Eggert <***@cs.ucla.edu>

+ dfa: omit unnecessary ptrdiff_t check
+ * lib/dfa.c (alloc_position_set): Do not worry about ptrdiff_t
+ overflow, since xnmalloc does that now.
+
dfa: omit unnecessary allocation
* lib/dfa.c (dfaanalyze): Do not allocate follow set, since
an all-zero follow set works just fine.
diff --git a/lib/dfa.c b/lib/dfa.c
index b27bef4..509d6d1 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2007,8 +2007,6 @@ static void
alloc_position_set (position_set *s, size_t size)
{
s->elems = xnmalloc (size, sizeof *s->elems);
- if (PTRDIFF_MAX < SIZE_MAX / sizeof *s->elems && PTRDIFF_MAX < size)
- xalloc_die ();
s->alloc = size;
s->nelem = 0;
}
--
2.9.3
Paul Eggert
2017-01-10 10:13:32 UTC
Permalink
Raw Message
* lib/dfa.c (build_state): Simplify by using emptyset.
---
ChangeLog | 5 +++++
lib/dfa.c | 5 +----
2 files changed, 6 insertions(+), 4 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index e0b73b5..8fda293 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2017-01-10 Paul Eggert <***@cs.ucla.edu>
+
+ dfa: minor simplification with emptyset
+ * lib/dfa.c (build_state): Simplify by using emptyset.
+
2017-01-09 Paul Eggert <***@cs.ucla.edu>

dfa: shrink constraints from 4 bits to 3
diff --git a/lib/dfa.c b/lib/dfa.c
index 28678c2..5df27ea 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2760,10 +2760,7 @@ build_state (state_num s, struct dfa *d, unsigned char uc)
matches.w[j] &= d->syntax.letters.w[j] | d->syntax.newline.w[j];

/* If there are no characters left, there's no point in going on. */
- size_t j;
- for (j = 0; j < CHARCLASS_WORDS && !matches.w[j]; j++)
- continue;
- if (j == CHARCLASS_WORDS)
+ if (emptyset (&matches))
continue;

/* If we have reset the bit that made us declare "matched", reset
--
2.9.3
Paul Eggert
2017-01-10 10:13:31 UTC
Permalink
Raw Message
* 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 91cdc6d..e0b73b5 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,14 @@
2017-01-09 Paul Eggert <***@cs.ucla.edu>

+ 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 509d6d1..28678c2 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.9.3
Loading...