This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
regen/regcharclass.pl: Add optimization
authorKarl Williamson <public@khwilliamson.com>
Wed, 5 Sep 2012 21:18:09 +0000 (15:18 -0600)
committerKarl Williamson <public@khwilliamson.com>
Fri, 14 Sep 2012 03:14:04 +0000 (21:14 -0600)
On UTF-8 input known to be valid, continuation bytes must be in the
range 0x80 .. 0x9F.  Therefore, any tests for being within those bounds
will always be true, and may be omitted.

regcharclass.h
regen/regcharclass.pl

index 59b2fdf..840caf1 100644 (file)
     : 0 )                                                                   \
 : ( 0xE2 == ((U8*)s)[0] ) ?                                                 \
     ( ( 0x80 == ((U8*)s)[1] ) ?                                             \
-       ( ( ( 0x80 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0x8A ) || 0xAF == ((U8*)s)[2] ) ? 3 : 0 )\
+       ( ( ( ((U8*)s)[2] <= 0x8A ) || 0xAF == ((U8*)s)[2] ) ? 3 : 0 )      \
     : ( 0x81 == ((U8*)s)[1] ) ?                                             \
        ( ( 0x9F == ((U8*)s)[2] ) ? 3 : 0 )                                 \
     : 0 )                                                                   \
 #define is_GCB_L_utf8(s)                                                    \
 ( ( 0xE1 == ((U8*)s)[0] ) ?                                                 \
     ( ( 0x84 == ((U8*)s)[1] ) ?                                             \
-       ( ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ? 3 : 0 )                      \
+       3                                                                   \
     : ( 0x85 == ((U8*)s)[1] ) ?                                             \
-       ( ( ( ((U8*)s)[2] & 0xE0 ) == 0x80 ) ? 3 : 0 )                      \
+       ( ( ((U8*)s)[2] <= 0x9F ) ? 3 : 0 )                                 \
     : 0 )                                                                   \
 : ( 0xEA == ((U8*)s)[0] ) ?                                                 \
     ( ( ( 0xA5 == ((U8*)s)[1] ) && ( 0xA0 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xBC ) ) ? 3 : 0 )\
 #define is_GCB_LV_LVT_V_utf8(s)                                             \
 ( ( 0xE1 == ((U8*)s)[0] ) ?                                                 \
     ( ( 0x85 == ((U8*)s)[1] ) ?                                             \
-       ( ( ( ((U8*)s)[2] & 0xE0 ) == 0xA0 ) ? 3 : 0 )                      \
+       ( ( ((U8*)s)[2] >= 0xA0 ) ? 3 : 0 )                                 \
     : ( 0x86 == ((U8*)s)[1] ) ?                                             \
-       ( ( 0x80 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xA7 ) ? 3 : 0 )          \
+       ( ( ((U8*)s)[2] <= 0xA7 ) ? 3 : 0 )                                 \
     : 0 )                                                                   \
 : ( 0xEA == ((U8*)s)[0] ) ?                                                 \
-    ( ( ( ( ((U8*)s)[1] & 0xF0 ) == 0xB0 ) && ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ) ? 3 : 0 )\
+    ( ( ((U8*)s)[1] >= 0xB0 ) ?                                             \
+       3                                                                   \
+    : 0 )                                                                   \
 : ( 0xEB == ((U8*)s)[0] || 0xEC == ((U8*)s)[0] ) ?                          \
-    ( ( ( ( ((U8*)s)[1] & 0xC0 ) == 0x80 ) && ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ) ? 3 : 0 )\
+    3                                                                       \
 : ( 0xED == ((U8*)s)[0] ) ?                                                 \
-    ( ( 0x80 <= ((U8*)s)[1] && ((U8*)s)[1] <= 0x9D ) ?                      \
-       ( ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ? 3 : 0 )                      \
+    ( ( ((U8*)s)[1] <= 0x9D ) ?                                             \
+       3                                                                   \
     : ( 0x9E == ((U8*)s)[1] ) ?                                             \
-       ( ( ( 0x80 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xA3 ) || ( ((U8*)s)[2] & 0xF0 ) == 0xB0 ) ? 3 : 0 )\
+       ( ( ( ((U8*)s)[2] <= 0xA3 ) || ( ((U8*)s)[2] >= 0xB0 ) ) ? 3 : 0 )  \
     : ( 0x9F == ((U8*)s)[1] ) ?                                             \
-       ( ( 0x80 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0x86 ) ? 3 : 0 )          \
+       ( ( ((U8*)s)[2] <= 0x86 ) ? 3 : 0 )                                 \
     : 0 )                                                                   \
 : 0 )
 
 */
 /*** GENERATED CODE ***/
 #define is_GCB_RI_utf8(s)                                                   \
-( ( ( ( ( 0xF0 == ((U8*)s)[0] ) && ( 0x9F == ((U8*)s)[1] ) ) && ( 0x87 == ((U8*)s)[2] ) ) && ( 0xA6 <= ((U8*)s)[3] && ((U8*)s)[3] <= 0xBF ) ) ? 4 : 0 )
+( ( ( ( ( 0xF0 == ((U8*)s)[0] ) && ( 0x9F == ((U8*)s)[1] ) ) && ( 0x87 == ((U8*)s)[2] ) ) && ( ((U8*)s)[3] >= 0xA6 ) ) ? 4 : 0 )
 
 /*
        GCB_SPECIAL_BEGIN: Grapheme_Cluster_Break=special_begins
 */
 /*** GENERATED CODE ***/
 #define is_GCB_SPECIAL_BEGIN_utf8(s)                                        \
-( ( ( 0xE1 == ((U8*)s)[0] ) && ( ( ((U8*)s)[1] & 0xFC ) == 0x84 ) ) ? ( ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ? 3 : 0 )\
+( ( 0xE1 == ((U8*)s)[0] ) ?                                                 \
+    ( ( ( ((U8*)s)[1] & 0xFC ) == 0x84 ) ?                                  \
+       3                                                                   \
+    : 0 )                                                                   \
 : ( 0xEA == ((U8*)s)[0] ) ?                                                 \
     ( ( 0xA5 == ((U8*)s)[1] ) ?                                             \
        ( ( 0xA0 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xBC ) ? 3 : 0 )          \
-    : ( ( ((U8*)s)[1] & 0xF0 ) == 0xB0 ) ?                                  \
-       ( ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ? 3 : 0 )                      \
+    : ( ((U8*)s)[1] >= 0xB0 ) ?                                             \
+       3                                                                   \
     : 0 )                                                                   \
 : ( 0xEB == ((U8*)s)[0] || 0xEC == ((U8*)s)[0] ) ?                          \
-    ( ( ( ( ((U8*)s)[1] & 0xC0 ) == 0x80 ) && ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ) ? 3 : 0 )\
+    3                                                                       \
 : ( 0xED == ((U8*)s)[0] ) ?                                                 \
-    ( ( 0x80 <= ((U8*)s)[1] && ((U8*)s)[1] <= 0x9D ) ?                      \
-       ( ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ? 3 : 0 )                      \
+    ( ( ((U8*)s)[1] <= 0x9D ) ?                                             \
+       3                                                                   \
     : ( 0x9E == ((U8*)s)[1] ) ?                                             \
-       ( ( ( 0x80 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xA3 ) || ( ((U8*)s)[2] & 0xF0 ) == 0xB0 ) ? 3 : 0 )\
+       ( ( ( ((U8*)s)[2] <= 0xA3 ) || ( ((U8*)s)[2] >= 0xB0 ) ) ? 3 : 0 )  \
     : ( 0x9F == ((U8*)s)[1] ) ?                                             \
-       ( ( ( 0x80 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0x86 ) || ( 0x8B <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xBB ) ) ? 3 : 0 )\
+       ( ( ( ((U8*)s)[2] <= 0x86 ) || ( 0x8B <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xBB ) ) ? 3 : 0 )\
     : 0 )                                                                   \
 : ( 0xF0 == ((U8*)s)[0] ) ?                                                 \
-    ( ( ( ( 0x9F == ((U8*)s)[1] ) && ( 0x87 == ((U8*)s)[2] ) ) && ( 0xA6 <= ((U8*)s)[3] && ((U8*)s)[3] <= 0xBF ) ) ? 4 : 0 )\
+    ( ( ( ( 0x9F == ((U8*)s)[1] ) && ( 0x87 == ((U8*)s)[2] ) ) && ( ((U8*)s)[3] >= 0xA6 ) ) ? 4 : 0 )\
 : 0 )
 
 /*
 #define is_GCB_T_utf8(s)                                                    \
 ( ( 0xE1 == ((U8*)s)[0] ) ?                                                 \
     ( ( 0x86 == ((U8*)s)[1] ) ?                                             \
-       ( ( 0xA8 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xBF ) ? 3 : 0 )          \
+       ( ( ((U8*)s)[2] >= 0xA8 ) ? 3 : 0 )                                 \
     : ( 0x87 == ((U8*)s)[1] ) ?                                             \
-       ( ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ? 3 : 0 )                      \
+       3                                                                   \
     : 0 )                                                                   \
 : ( 0xED == ((U8*)s)[0] ) ?                                                 \
     ( ( ( 0x9F == ((U8*)s)[1] ) && ( 0x8B <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xBB ) ) ? 3 : 0 )\
 #define is_GCB_V_utf8(s)                                                    \
 ( ( 0xE1 == ((U8*)s)[0] ) ?                                                 \
     ( ( 0x85 == ((U8*)s)[1] ) ?                                             \
-       ( ( ( ((U8*)s)[2] & 0xE0 ) == 0xA0 ) ? 3 : 0 )                      \
+       ( ( ((U8*)s)[2] >= 0xA0 ) ? 3 : 0 )                                 \
     : ( 0x86 == ((U8*)s)[1] ) ?                                             \
-       ( ( 0x80 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xA7 ) ? 3 : 0 )          \
+       ( ( ((U8*)s)[2] <= 0xA7 ) ? 3 : 0 )                                 \
     : 0 )                                                                   \
 : ( 0xED == ((U8*)s)[0] ) ?                                                 \
     ( ( 0x9E == ((U8*)s)[1] ) ?                                             \
-       ( ( ( ((U8*)s)[2] & 0xF0 ) == 0xB0 ) ? 3 : 0 )                      \
+       ( ( ((U8*)s)[2] >= 0xB0 ) ? 3 : 0 )                                 \
     : ( 0x9F == ((U8*)s)[1] ) ?                                             \
-       ( ( 0x80 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0x86 ) ? 3 : 0 )          \
+       ( ( ((U8*)s)[2] <= 0x86 ) ? 3 : 0 )                                 \
     : 0 )                                                                   \
 : 0 )
 
     : 0 )                                                                   \
 : ( 0xE2 == ((U8*)s)[0] ) ?                                                 \
     ( ( 0x80 == ((U8*)s)[1] ) ?                                             \
-       ( ( 0x80 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xBE ) ? 3 : 0 )          \
+       ( ( ((U8*)s)[2] <= 0xBE ) ? 3 : 0 )                                 \
     : ( 0x81 == ((U8*)s)[1] ) ?                                             \
        ( ( ( 0x81 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0x93 ) || ( 0x95 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xAF ) ) ? 3 : 0 )\
     : ( 0x86 == ((U8*)s)[1] ) ?                                             \
-       ( ( 0x90 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xBF ) ? 3 : 0 )          \
+       ( ( ((U8*)s)[2] >= 0x90 ) ? 3 : 0 )                                 \
     : ( 0x87 <= ((U8*)s)[1] && ((U8*)s)[1] <= 0x90 ) ?                      \
-       ( ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ? 3 : 0 )                      \
+       3                                                                   \
     : ( 0x91 == ((U8*)s)[1] ) ?                                             \
-       ( ( ( ((U8*)s)[2] & 0xE0 ) == 0x80 ) ? 3 : 0 )                      \
+       ( ( ((U8*)s)[2] <= 0x9F ) ? 3 : 0 )                                 \
     : ( 0x94 <= ((U8*)s)[1] && ((U8*)s)[1] <= 0x9C ) ?                      \
-       ( ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ? 3 : 0 )                      \
+       3                                                                   \
     : ( 0x9D == ((U8*)s)[1] ) ?                                             \
-       ( ( 0x80 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xB5 ) ? 3 : 0 )          \
+       ( ( ((U8*)s)[2] <= 0xB5 ) ? 3 : 0 )                                 \
     : ( 0x9E == ((U8*)s)[1] ) ?                                             \
-       ( ( 0x94 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xBF ) ? 3 : 0 )          \
+       ( ( ((U8*)s)[2] >= 0x94 ) ? 3 : 0 )                                 \
     : ( ( 0x9F <= ((U8*)s)[1] && ((U8*)s)[1] <= 0xAF ) || ( ((U8*)s)[1] & 0xFE ) == 0xB8 ) ?\
-       ( ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ? 3 : 0 )                      \
+       3                                                                   \
     : 0 )                                                                   \
 : ( 0xE3 == ((U8*)s)[0] ) ?                                                 \
     ( ( 0x80 == ((U8*)s)[1] ) ?                                             \
-       ( ( ( ((U8*)s)[2] & 0xFC ) == 0x80 || ( 0x88 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xA0 ) || 0xB0 == ((U8*)s)[2] ) ? 3 : 0 )\
+       ( ( ( ((U8*)s)[2] <= 0x83 ) || ( 0x88 <= ((U8*)s)[2] && ((U8*)s)[2] <= 0xA0 ) || 0xB0 == ((U8*)s)[2] ) ? 3 : 0 )\
     : ( 0x85 == ((U8*)s)[1] ) ?                                             \
        ( ( 0xA4 == ((U8*)s)[2] ) ? 3 : 0 )                                 \
     : 0 )                                                                   \
 : ( 0xEF == ((U8*)s)[0] ) ?                                                 \
     ( ( 0xB4 == ((U8*)s)[1] ) ?                                             \
-       ( ( ( ((U8*)s)[2] & 0xFE ) == 0xBE ) ? 3 : 0 )                      \
+       ( ( ((U8*)s)[2] >= 0xBE ) ? 3 : 0 )                                 \
     : ( 0xB8 == ((U8*)s)[1] ) ?                                             \
-       ( ( ( ((U8*)s)[2] & 0xF0 ) == 0x80 ) ? 3 : 0 )                      \
+       ( ( ((U8*)s)[2] <= 0x8F ) ? 3 : 0 )                                 \
     : ( 0xB9 == ((U8*)s)[1] ) ?                                             \
        ( ( 0x85 == ((U8*)s)[2] || 0x86 == ((U8*)s)[2] ) ? 3 : 0 )          \
     : ( 0xBB == ((U8*)s)[1] ) ?                                             \
 : ( 0xF0 == ((U8*)s)[0] ) ?                                                 \
     ( ( ( ( 0x9D == ((U8*)s)[1] ) && ( 0x85 == ((U8*)s)[2] ) ) && ( 0xB3 <= ((U8*)s)[3] && ((U8*)s)[3] <= 0xBA ) ) ? 4 : 0 )\
 : ( 0xF3 == ((U8*)s)[0] ) ?                                                 \
-    ( ( ( ( 0xA0 == ((U8*)s)[1] ) && ( ( ((U8*)s)[2] & 0xC0 ) == 0x80 ) ) && ( ( ((U8*)s)[3] & 0xC0 ) == 0x80 ) ) ? 4 : 0 )\
+    ( ( 0xA0 == ((U8*)s)[1] ) ?                                             \
+       4                                                                   \
+    : 0 )                                                                   \
 : 0 )
 
 
index e4133fd..70f46b0 100755 (executable)
@@ -710,12 +710,16 @@ sub _cond_as_str {
 
         return 1 if @$cond == 256;  # If all bytes match, is trivially true
 
+        if (@ranges > 1) {
             # See if the entire set shares optimizable characterstics, and if
-            # so, return the optimization.
+            # so, return the optimization.  We delay checking for this on sets
+            # with just a single range, as there may be better optimizations
+            # available in that case.
             my ($mask, $base) = calculate_mask(@$cond);
             if (defined $mask && defined $base) {
                 return sprintf "( ( $test & $self->{val_fmt} ) == $self->{val_fmt} )", $mask, $base;
             }
+        }
 
         # Here, there was no entire-class optimization.  Look at each range.
         for (my $i = 0; $i < @ranges; $i++) {
@@ -729,10 +733,43 @@ sub _cond_as_str {
             else {
                 my $output = "";
 
-                # See if the number of elements is a power of 2 (only a single
-                # bit in the representation of its count will be set) and if
-                # so, it may be that a mask/compare optimization is possible.
-                if (pop_count($ranges[$i]->[1] - $ranges[$i]->[0] + 1) == 1) {
+                # Well-formed UTF-8 continuation bytes on ascii platforms must
+                # be in the range 0x80 .. 0xBF.  If we know that the input is
+                # well-formed (indicated by not trying to be 'safe'), we can
+                # omit tests that verify that the input is within either of
+                # these bounds.  (No legal UTF-8 character can begin with
+                # anything in this range, so we don't have to worry about this
+                # being a continuation byte or not.)
+                if (ASCII_PLATFORM
+                    && ! $opts_ref->{safe}
+                    && $opts_ref->{type} =~ / ^ (?: utf8 | high ) $ /xi)
+                {
+                    my $lower_limit_is_80 = ($ranges[$i]->[0] == 0x80);
+                    my $upper_limit_is_BF = ($ranges[$i]->[1] == 0xBF);
+
+                    # If the range is the entire legal range, it matches any
+                    # legal byte, so we can omit both tests.  (This should
+                    # happen only if the number of ranges is 1.)
+                    if ($lower_limit_is_80 && $upper_limit_is_BF) {
+                        return 1;
+                    }
+                    elsif ($lower_limit_is_80) { # Just use the upper limit test
+                        $output = sprintf("( $test <= $self->{val_fmt} )",
+                                            $ranges[$i]->[1]);
+                    }
+                    elsif ($upper_limit_is_BF) { # Just use the lower limit test
+                        $output = sprintf("( $test >= $self->{val_fmt} )",
+                                        $ranges[$i]->[0]);
+                    }
+                }
+
+                # If we didn't change to omit a test above, see if the number
+                # of elements is a power of 2 (only a single bit in the
+                # representation of its count will be set) and if so, it may
+                # be that a mask/compare optimization is possible.
+                if ($output eq ""
+                    && pop_count($ranges[$i]->[1] - $ranges[$i]->[0] + 1) == 1)
+                {
                     my @list;
                     push @list, $_  for ($ranges[$i]->[0] .. $ranges[$i]->[1]);
                     my ($mask, $base) = calculate_mask(@list);