[Pcre-svn] [1015] code/trunk: Improve extended grapheme clus…

Top Page
Delete this message
Author: Subversion repository
Date:  
To: pcre-svn
Subject: [Pcre-svn] [1015] code/trunk: Improve extended grapheme clusters using a bit table.
Revision: 1015
          http://vcs.pcre.org/viewvc?view=rev&revision=1015
Author:   ph10
Date:     2012-08-26 17:07:14 +0100 (Sun, 26 Aug 2012)


Log Message:
-----------
Improve extended grapheme clusters using a bit table.

Modified Paths:
--------------
    code/trunk/pcre_dfa_exec.c
    code/trunk/pcre_exec.c
    code/trunk/pcre_internal.h
    code/trunk/pcre_jit_compile.c
    code/trunk/pcre_tables.c
    code/trunk/ucp.h


Modified: code/trunk/pcre_dfa_exec.c
===================================================================
--- code/trunk/pcre_dfa_exec.c    2012-08-26 04:53:49 UTC (rev 1014)
+++ code/trunk/pcre_dfa_exec.c    2012-08-26 16:07:14 UTC (rev 1015)
@@ -1384,7 +1384,7 @@
           dlen = 1;
           if (!utf) d = *nptr; else { GETCHARLEN(d, nptr, dlen); }
           rgb = UCD_GRAPHBREAK(d); 
-          if (PRIV(ucp_gbtable)[lgb * ucp_gbCount + rgb] == 0) break;
+          if ((PRIV(ucp_gbtable)[lgb] & (1 << rgb)) == 0) break;
           ncount++;
           lgb = rgb; 
           nptr += dlen;
@@ -1644,7 +1644,7 @@
           dlen = 1;
           if (!utf) d = *nptr; else { GETCHARLEN(d, nptr, dlen); }
           rgb = UCD_GRAPHBREAK(d); 
-          if (PRIV(ucp_gbtable)[lgb * ucp_gbCount + rgb] == 0) break;
+          if ((PRIV(ucp_gbtable)[lgb] & (1 << rgb)) == 0) break;
           ncount++;
           lgb = rgb; 
           nptr += dlen;
@@ -1913,7 +1913,7 @@
           dlen = 1;
           if (!utf) d = *nptr; else { GETCHARLEN(d, nptr, dlen); }
           rgb = UCD_GRAPHBREAK(d); 
-          if (PRIV(ucp_gbtable)[lgb * ucp_gbCount + rgb] == 0) break;
+          if ((PRIV(ucp_gbtable)[lgb] & (1 << rgb)) == 0) break;
           ncount++;
           lgb = rgb; 
           nptr += dlen;
@@ -2132,7 +2132,7 @@
           dlen = 1;
           if (!utf) d = *nptr; else { GETCHARLEN(d, nptr, dlen); }
           rgb = UCD_GRAPHBREAK(d); 
-          if (PRIV(ucp_gbtable)[lgb * ucp_gbCount + rgb] == 0) break;
+          if ((PRIV(ucp_gbtable)[lgb] & (1 << rgb)) == 0) break;
           ncount++;
           lgb = rgb; 
           nptr += dlen;


Modified: code/trunk/pcre_exec.c
===================================================================
--- code/trunk/pcre_exec.c    2012-08-26 04:53:49 UTC (rev 1014)
+++ code/trunk/pcre_exec.c    2012-08-26 16:07:14 UTC (rev 1015)
@@ -2651,7 +2651,7 @@
         int len = 1;
         if (!utf) c = *eptr; else { GETCHARLEN(c, eptr, len); }
         rgb = UCD_GRAPHBREAK(c); 
-        if (PRIV(ucp_gbtable)[lgb * ucp_gbCount + rgb] == 0) break;
+        if ((PRIV(ucp_gbtable)[lgb] & (1 << rgb)) == 0) break;
         lgb = rgb; 
         eptr += len;
         } 
@@ -4242,7 +4242,7 @@
               int len = 1;
               if (!utf) c = *eptr; else { GETCHARLEN(c, eptr, len); }
               rgb = UCD_GRAPHBREAK(c); 
-              if (PRIV(ucp_gbtable)[lgb * ucp_gbCount + rgb] == 0) break;
+              if ((PRIV(ucp_gbtable)[lgb] & (1 << rgb)) == 0) break;
               lgb = rgb; 
               eptr += len;
               } 
@@ -5051,7 +5051,7 @@
               int len = 1;
               if (!utf) c = *eptr; else { GETCHARLEN(c, eptr, len); }
               rgb = UCD_GRAPHBREAK(c); 
-              if (PRIV(ucp_gbtable)[lgb * ucp_gbCount + rgb] == 0) break;
+              if ((PRIV(ucp_gbtable)[lgb] & (1 << rgb)) == 0) break;
               lgb = rgb; 
               eptr += len;
               } 
@@ -5621,7 +5621,7 @@
               int len = 1;
               if (!utf) c = *eptr; else { GETCHARLEN(c, eptr, len); }
               rgb = UCD_GRAPHBREAK(c); 
-              if (PRIV(ucp_gbtable)[lgb * ucp_gbCount + rgb] == 0) break;
+              if ((PRIV(ucp_gbtable)[lgb] & (1 << rgb)) == 0) break;
               lgb = rgb; 
               eptr += len;
               } 


Modified: code/trunk/pcre_internal.h
===================================================================
--- code/trunk/pcre_internal.h    2012-08-26 04:53:49 UTC (rev 1014)
+++ code/trunk/pcre_internal.h    2012-08-26 16:07:14 UTC (rev 1015)
@@ -2324,7 +2324,7 @@
 extern const pcre_uint8  PRIV(ucd_stage1)[];
 extern const pcre_uint16 PRIV(ucd_stage2)[];
 extern const int         PRIV(ucp_gentype)[];
-extern const pcre_uint8  PRIV(ucp_gbtable)[];
+extern const pcre_uint32 PRIV(ucp_gbtable)[];
 #ifdef SUPPORT_JIT
 extern const int         PRIV(ucp_typerange)[];
 #endif


Modified: code/trunk/pcre_jit_compile.c
===================================================================
--- code/trunk/pcre_jit_compile.c    2012-08-26 04:53:49 UTC (rev 1014)
+++ code/trunk/pcre_jit_compile.c    2012-08-26 16:07:14 UTC (rev 1015)
@@ -4232,11 +4232,12 @@
   OP1(SLJIT_MOV, TMP1, 0, SLJIT_IMM, (sljit_w)PRIV(ucd_records) + SLJIT_OFFSETOF(ucd_record, gbprop));
   OP1(SLJIT_MOV_UB, TMP2, 0, SLJIT_MEM2(TMP1, TMP2), 3);


- OP2(SLJIT_MUL, TMP1, 0, STACK_TOP, 0, SLJIT_IMM, ucp_gbCount);
+ OP2(SLJIT_SHL, STACK_TOP, 0, STACK_TOP, 0, SLJIT_IMM, 2);
+ OP1(SLJIT_MOV, TMP1, 0, SLJIT_MEM1(STACK_TOP), (sljit_w)PRIV(ucp_gbtable));
OP1(SLJIT_MOV, STACK_TOP, 0, TMP2, 0);
- OP2(SLJIT_ADD, TMP1, 0, TMP1, 0, TMP2, 0);
- OP1(SLJIT_MOV_UB, TMP1, 0, SLJIT_MEM1(TMP1), (sljit_w)PRIV(ucp_gbtable));
- CMPTO(SLJIT_C_NOT_EQUAL, TMP1, 0, SLJIT_IMM, 0, label);
+ OP2(SLJIT_SHL, TMP2, 0, SLJIT_IMM, 1, TMP2, 0);
+ OP2(SLJIT_AND | SLJIT_SET_E, SLJIT_UNUSED, 0, TMP1, 0, TMP2, 0);
+ JUMPTO(SLJIT_C_NOT_ZERO, label);

OP1(SLJIT_MOV, STR_PTR, 0, TMP3, 0);
JUMPHERE(jump[0]);

Modified: code/trunk/pcre_tables.c
===================================================================
--- code/trunk/pcre_tables.c    2012-08-26 04:53:49 UTC (rev 1014)
+++ code/trunk/pcre_tables.c    2012-08-26 16:07:14 UTC (rev 1015)
@@ -109,61 +109,65 @@
   ucp_Z, ucp_Z, ucp_Z                 /* Zl, Zp, Zs */
 };


-/* This byte table encodes the rules for finding the end of an extended
-grapheme cluster. It could be done with bits instead of bytes, but the saving
-in memory would be small and there would be more computation at runtime.
+/* This table encodes the rules for finding the end of an extended grapheme
+cluster. Every code point has a grapheme break property which is one of the
+ucp_gbXX values defined in ucp.h. The 2-dimensional table is indexed by the
+properties of two adjacent code points. The left property selects a word from
+the table, and the right property selects a bit from that word like this:

-Every code point has a grapheme break property which is one of the ucp_gbXX
-values defined in ucp.h. The number of such properties is ucp_gbCount. The
-2-dimensional table is indexed by the properties of two adjacent code points.
+ ucp_gbtable[left-property] & (1 << right-property)
+
The value is non-zero if a grapheme break is NOT permitted between the relevant
two code points. The breaking rules are as follows:

1. Break at the start and end of text (pretty obviously).

-2. Do not break between a CR and LF: (0,1) is set; otherwise, break before and
- after controls: (x,0), (x,1), (x,2), (0,x), (1,x), and (2,x) are not set,
- except for (0,1).
+2. Do not break between a CR and LF; otherwise, break before and after
+ controls.

-3. Do not break Hangul syllable sequences: (6,6), (6,7), (6,9), (6,10),
- (7,7), (7,8), (8,8), (9,7), (9,8), and (10,8) are set. The rules for Hangul
- sequences are:
+3. Do not break Hangul syllable sequences, the rules for which are:

     L may be followed by L, V, LV or LVT
     LV or V may be followed by V or T
     LVT or T may be followed by T  


-4. Do not break before extending characters: (x,3) is set except for (0,3),
- (1,3), and (2,3).
+4. Do not break before extending characters.

The next two rules are only for extended grapheme clusters (but that's what we
are implementing).

-5. Do not break before SpacingMarks: (x,5) is set except for (0,5), (1,5),
- and (2,5).
+5. Do not break before SpacingMarks.

-6. Do not break after Prepend characters: (4,x) is set except for (4,0), (4,1),
- and (4,2).
+6. Do not break after Prepend characters.

-8. Otherwise, break everywhere.
+7. Otherwise, break everywhere.
*/

-const pcre_uint8 PRIV(ucp_gbtable[]) = {
-/* 0  1  2  3  4  5  6  7  8  9 10 11 */
-   0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,     /*  0 CR */
-   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,     /*  1 LF */
-   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,     /*  2 Control */
-   0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0,     /*  3 Extend */
-   0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,     /*  4 Prepend */
-   0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0,     /*  5 SpacingMark */
-   0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0,     /*  6 L */
-   0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0,     /*  7 V */
-   0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0,     /*  8 T */
-   0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0,     /*  9 LV */
-   0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0,     /* 10 LVT */
-   0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0      /* 11 Other */
-};
+const pcre_uint32 PRIV(ucp_gbtable[]) = {
+   (1<<ucp_gbLF),                                           /*  0 CR */        
+   0,                                                       /*  1 LF */        
+   0,                                                       /*  2 Control */   
+   (1<<ucp_gbExtend)|(1<<ucp_gbSpacingMark),                /*  3 Extend */    
+   (1<<ucp_gbExtend)|(1<<ucp_gbPrepend)|                    /*  4 Prepend */   
+     (1<<ucp_gbSpacingMark)|(1<<ucp_gbL)|                   
+     (1<<ucp_gbV)|(1<<ucp_gbT)|(1<<ucp_gbLV)|               
+     (1<<ucp_gbLVT)|(1<<ucp_gbOther),                       


+   (1<<ucp_gbExtend)|(1<<ucp_gbSpacingMark),                /*  5 SpacingMark */  
+   (1<<ucp_gbExtend)|(1<<ucp_gbSpacingMark)|(1<<ucp_gbL)|   /*  6 L */            
+     (1<<ucp_gbL)|(1<<ucp_gbV)|(1<<ucp_gbLV)|(1<<ucp_gbLVT),
+
+   (1<<ucp_gbExtend)|(1<<ucp_gbSpacingMark)|(1<<ucp_gbV)|   /*  7 V */
+     (1<<ucp_gbT),
+
+   (1<<ucp_gbExtend)|(1<<ucp_gbSpacingMark)|(1<<ucp_gbT),   /*  8 T */  
+   (1<<ucp_gbExtend)|(1<<ucp_gbSpacingMark)|(1<<ucp_gbV)|   /*  9 LV */ 
+     (1<<ucp_gbT),
+
+   (1<<ucp_gbExtend)|(1<<ucp_gbSpacingMark)|(1<<ucp_gbT),   /* 10 LVT */  
+   (1<<ucp_gbExtend)|(1<<ucp_gbSpacingMark)                 /* 11 Other */
+}; 
+    
 #ifdef SUPPORT_JIT
 /* This table reverses PRIV(ucp_gentype). We can save the cost
 of a memory load. */


Modified: code/trunk/ucp.h
===================================================================
--- code/trunk/ucp.h    2012-08-26 04:53:49 UTC (rev 1014)
+++ code/trunk/ucp.h    2012-08-26 16:07:14 UTC (rev 1015)
@@ -76,8 +76,7 @@
   ucp_gbT,              /*  8 Hangul syllable type T */
   ucp_gbLV,             /*  9 Hangul syllable type LV */
   ucp_gbLVT,            /* 10 Hangul syllable type LVT */
-  ucp_gbOther,          /* 11 */
-  ucp_gbCount           /* 12 The number of properties */ 
+  ucp_gbOther           /* 11 */
 };


/* These are the script identifications. */