[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

bug in dfa.c

From: Arne Jansen
Subject: bug in dfa.c
Date: Thu, 06 Dec 2007 16:26:07 +0100
User-agent: Thunderbird (Windows/20071031)


the function state_index searches for a state with the same
position set as the given set. The loop which checks for
equality is imho missing the check if the nelem differ.
If one list is a subset of the other, the check might
accidentally match.
This is extremely unlikely for small expressions, but if you
have some 100,000 states it gets quite likely.

Below a proposed fix, though untested:

  for (i = 0; i < s->nelem; ++i)
    hash ^= s->elems[i].index + s->elems[i].constraint;

  /* Try to find a state that exactly matches the proposed one. */
  for (i = 0; i < d->sindex; ++i)
      if (hash != d->states[i].hash || s->nelem !=
          || newline != d->states[i].newline || letter !=
+    if (s->nelem != d->states[i].elems.nelem)
+       continue;
      for (j = 0; j < s->nelem; ++j)
        if (s->elems[j].constraint
            != d->states[i].elems.elems[j].constraint
            || s->elems[j].index != d->states[i].elems.elems[j].index)
      if (j == s->nelem)
        return i;


Telefon: +49 (0)30-39802-214
Telefax: +49 (0)30-39802-222
E-Mail:  address@hidden
Strato Rechenzentrum AG
Pascalstrasse 10
10587 Berlin
Vorsitzender des Aufsichtsrates: Damian Schmidt
Vorstand: Julien Ardisson, Christian Mueller, Christian Negrutiu,
          Christoph Steffens, Rene Wienholtz
Amtsgericht Berlin-Charlottenburg HRB 75629

reply via email to

[Prev in Thread] Current Thread [Next in Thread]