Optimize Regex Circuit Gen

[Divide-By-0]

Decrease repeated computation - 33% savings

Right now, checking if a specific character is in a range is repeated many times in the code. For instance, body hash check has

      lt[7][i] = LessThan(8);
      lt[7][i].in[0] <== in[i];
      lt[7][i].in[1] <== 58;

and

      lt[25][i] = LessThan(8);
      lt[25][i].in[0] <== in[i];
      lt[25][i].in[1] <== 58;

and 2 other occurrences of this check. Thus, if we just did it once and stored it in a shared register referred to by all of these checks, we could probably reduce the remaining lessThan checks by a factor of 4. This would be about 200K constraints, or about a 33% drop in regex.

---

This second suggestion I'm about to say does NOT work since circom considers (p/2, p) as negative numbers. It had intially proposed to decrease double less than checks for 16% savings.

Rn, to check if 47 < x < 52, we do two lessthan checks. We could instead do is x - 47 < 5, which is the same thing right, and we change 2b constraints to b + 1 constraints where b is the bit count (8 in this case). For instance, the body hash check has 13 less than pairs (26 total) for 1024 size header, so we'd save 13 * 7 * 1024 ~= 100K constraints roughly, which out of 600K is about 16%. However this will only work if you can change circoms presets to remove negative numbers.

[Divide-By-0]

This would also allow the option for forwards-backwards regexes to 2x regex cost at the tradeoff of increasing the # of regexes that are allowed, and keep circuits feasible.