In perl.git, the branch smoke-me/khw-anyofh has been created
<https://perl5.git.perl.org/perl.git/commitdiff/c32e7df7a12a3dd8d9af2ff51f039c3c9f7d4bc0?hp=0000000000000000000000000000000000000000>
at c32e7df7a12a3dd8d9af2ff51f039c3c9f7d4bc0 (commit)
- Log -----------------------------------------------------------------
commit c32e7df7a12a3dd8d9af2ff51f039c3c9f7d4bc0
Author: Karl Williamson <[email protected]>
Date: Wed Jun 5 11:15:00 2019 -0600
XXX more regex: Add ANYOFHr regnode
This commit adds a lower bound for the first UTF-8 byte matchable by an
ANYOFH node. The flags field is otherwise unused, and using it for this
purpose allows code to rule out match possibilities without having to
convert from UTF-8 to code point.
It might be better to do the inverse instead, to have the field be an
upper bound. The reason is that the conversion is cheap for smaller
numbers. The commit following mostly addresses this.
This commit adds a new regnode, ANYOFHr, like ANYOFH, but it also has a
loose upper bound for the first UTF-8 byte matchable by the node. It
would be nice to have a tight upper bound, but to do so requires 4 more
bits than are available without changing the node arguments types.
Having a loose bound is better than no bound, and comes essentially
free, by using two bits in the current ANYOFH node that are redundant,
and requiring only a few extra, pipelined, mask, etc instructions at run
time, no extra conditionals. Any ANYOFH nodes that would benefit from
having an upper bound will instead become this node type.
Its used is based on the following observations.
There are 64 possible start bytes, so the full range can be expressed in
6 bits. This means that the flags field in ANYOFH nodes containing the
start byte has two redundant bits that can be used for something else.
An ANYOFH node only happens when there is no matching code point in the
bit map.so the smallest code point that could be is 256. The start byte
for that is C4, so there are actually only 60 possible start bytes.
(perl can be compiled with a larger bit map in which case the minimum
start byte would be even higher.)
A second observation is that knowing the highest start byte is above F0
is no better than knowing it's F0. This is because the highest code
point whose start byte is F0 is U+3FFFF, and all code points above that
that are currently allocated are all very specialized. And there's no
likelihood of that changing anytime soon as there's plenty of
unallocated space below that. So if an ANYOFH node's highest start byte
is F0 or above, leave it ANYOFH, and no harm down.
That means the highest start byte we care about in ANYOFHr is EF. That
cuts the number of start bytes we care about down to 43, still 6 bits
required to represent them, but it allows for the following scheme
Populate the flags field by subtracting C4 from the lowest start byte
and shift left 2 bits. That leaves the the bottom two bits unused.
We use them as follows, where x is the start byte of the lowest code
point in the node:
11 The upper limit of the range can be as much as (EF - x) / 8
10 The upper limit of the range can be as much as (EF - x) / 4
01 The upper limit of the range can be as much as (EF - x) / 2
00 The upper limit of the range can be as much as EF
The possible high bytes for C4 are C9 CE D9 EF
The possible high bytes for D0 are D3 D7 DF EF
The possible high bytes for E0 are E1 E3 E7 EF
Thus we have provided a loose upper bound using two bits. An alternate
scheme could have had the intervals all the same, but this provides a
tighter bound if the range is small, which...
For EBCDIC the range is is from C8 to F4,
l
commit 2c356c1d18ee49320d55c290a779b01c1f7b9438
Author: Karl Williamson <[email protected]>
Date: Tue Jun 4 12:31:03 2019 -0600
White space only in comment
commit 5417f2c0fd020e677e2fd7322182417f021925c8
Author: Karl Williamson <[email protected]>
Date: Tue Jun 4 12:16:10 2019 -0600
regex: Add lower bound to ANYOFH nodes UTF-8 byte
This commit adds a lower bound for the first UTF-8 byte matchable by an
ANYOFH node. The flags field is otherwise unused, and using it for this
purpose allows code to rule out match possibilities without having to
convert from UTF-8 to code point.
It might be better to do the inverse instead, to have the field be an
upper bound. The reason is that the conversion is cheap for smaller
numbers. The commit following mostly addresses this.
commit 11ba487110c57cc5f3d262c727b439a32e367a56
Author: Karl Williamson <[email protected]>
Date: Tue Jun 4 11:43:17 2019 -0600
Use inRANGE for the ANYOFH node types
This is easier to read, especially when a third type is added a few
commits ahead.
commit f8095c096f4c3cf76f394c6563fe5125c3d9c615
Author: Karl Williamson <[email protected]>
Date: Wed Jun 5 11:15:51 2019 -0600
regcomp.sym: Change regnode description
Simplify the description for ANYOFb
-----------------------------------------------------------------------
--
Perl5 Master Repository
