added martin's BIGCHARSET patch to SRE 2.1.1. martin reports 2x
speedups for certain unicode character ranges.
diff --git a/Lib/sre_compile.py b/Lib/sre_compile.py
index 44cb23e..539e878 100644
--- a/Lib/sre_compile.py
+++ b/Lib/sre_compile.py
@@ -156,6 +156,8 @@
emit(fixup(av[1]))
elif op is CHARSET:
code.extend(av)
+ elif op is BIGCHARSET:
+ code.extend(av)
elif op is CATEGORY:
if flags & SRE_FLAG_LOCALE:
emit(CHCODES[CH_LOCALE[av]])
@@ -185,7 +187,7 @@
return charset # cannot compress
except IndexError:
# character set contains unicode characters
- return charset
+ return _optimize_unicode(charset, fixup)
# compress character map
i = p = n = 0
runs = []
@@ -211,19 +213,78 @@
return out
else:
# use bitmap
- data = []
- m = 1; v = 0
- for c in charmap:
- if c:
- v = v + m
- m = m << 1
- if m > MAXCODE:
- data.append(v)
- m = 1; v = 0
+ data = _mk_bitmap(charmap)
out.append((CHARSET, data))
return out
return charset
+def _mk_bitmap(bits):
+ data = []
+ m = 1; v = 0
+ for c in bits:
+ if c:
+ v = v + m
+ m = m << 1
+ if m > MAXCODE:
+ data.append(v)
+ m = 1; v = 0
+ return data
+
+# To represent a big charset, first a bitmap of all characters in the
+# set is constructed. Then, this bitmap is sliced into chunks of 256
+# characters, duplicate chunks are eliminitated, and each chunk is
+# given a number. In the compiled expression, the charset is
+# represented by a 16-bit word sequence, consisting of one word for
+# the number of different chunks, a sequence of 256 bytes (128 words)
+# of chunk numbers indexed by their original chunk position, and a
+# sequence of chunks (16 words each).
+
+# Compression is normally good: in a typical charset, large ranges of
+# Unicode will be either completely excluded (e.g. if only cyrillic
+# letters are to be matched), or completely included (e.g. if large
+# subranges of Kanji match). These ranges will be represented by
+# chunks of all one-bits or all zero-bits.
+
+# Matching can be also done efficiently: the more significant byte of
+# the Unicode character is an index into the chunk number, and the
+# less significant byte is a bit index in the chunk (just like the
+# CHARSET matching).
+
+def _optimize_unicode(charset, fixup):
+ charmap = [0]*65536
+ negate = 0
+ for op, av in charset:
+ if op is NEGATE:
+ negate = 1
+ elif op is LITERAL:
+ charmap[fixup(av)] = 1
+ elif op is RANGE:
+ for i in range(fixup(av[0]), fixup(av[1])+1):
+ charmap[i] = 1
+ elif op is CATEGORY:
+ # XXX: could expand category
+ return charset # cannot compress
+ if negate:
+ for i in range(65536):
+ charmap[i] = not charmap[i]
+ comps = {}
+ mapping = [0]*256
+ block = 0
+ data = []
+ for i in range(256):
+ chunk = tuple(charmap[i*256:(i+1)*256])
+ new = comps.setdefault(chunk, block)
+ mapping[i] = new
+ if new == block:
+ block += 1
+ data += _mk_bitmap(chunk)
+ header = [block]
+ assert MAXCODE == 65535
+ for i in range(128):
+ header.append(mapping[2*i]+256*mapping[2*i+1])
+ data[0:0] = header
+ return [(BIGCHARSET, data)]
+
def _simple(av):
# check if av is a "simple" operator
lo, hi = av[2].getwidth()
diff --git a/Lib/sre_constants.py b/Lib/sre_constants.py
index bbe7880..3296b94 100644
--- a/Lib/sre_constants.py
+++ b/Lib/sre_constants.py
@@ -11,7 +11,7 @@
# update when constants are added or removed
-MAGIC = 20010320
+MAGIC = 20010701
# max code word in this release
@@ -33,6 +33,7 @@
ASSERT = "assert"
ASSERT_NOT = "assert_not"
AT = "at"
+BIGCHARSET = "bigcharset"
BRANCH = "branch"
CALL = "call"
CATEGORY = "category"
@@ -103,7 +104,7 @@
BRANCH,
CALL,
CATEGORY,
- CHARSET,
+ CHARSET, BIGCHARSET,
GROUPREF, GROUPREF_IGNORE,
IN, IN_IGNORE,
INFO,
diff --git a/Modules/_sre.c b/Modules/_sre.c
index 3e2d907..51a747a 100644
--- a/Modules/_sre.c
+++ b/Modules/_sre.c
@@ -506,6 +506,19 @@
set += 16;
break;
+ case SRE_OP_BIGCHARSET:
+ /* <BIGCHARSET> <blockcount> <256 blockindices> <blocks> */
+ {
+ int count, block;
+ count = *(set++);
+ block = ((unsigned char*)set)[ch >> 8];
+ set += 128;
+ if (set[block*16 + ((ch & 255)>>4)] & (1 << (ch & 15)))
+ return ok;
+ set += count*16;
+ break;
+ }
+
case SRE_OP_CATEGORY:
/* <CATEGORY> <code> */
if (sre_category(set[0], (int) ch))
diff --git a/Modules/sre_constants.h b/Modules/sre_constants.h
index 73bcb34..ebb9fd0 100644
--- a/Modules/sre_constants.h
+++ b/Modules/sre_constants.h
@@ -11,7 +11,7 @@
* See the _sre.c file for information on usage and redistribution.
*/
-#define SRE_MAGIC 20010320
+#define SRE_MAGIC 20010701
#define SRE_OP_FAILURE 0
#define SRE_OP_SUCCESS 1
#define SRE_OP_ANY 2
@@ -23,24 +23,25 @@
#define SRE_OP_CALL 8
#define SRE_OP_CATEGORY 9
#define SRE_OP_CHARSET 10
-#define SRE_OP_GROUPREF 11
-#define SRE_OP_GROUPREF_IGNORE 12
-#define SRE_OP_IN 13
-#define SRE_OP_IN_IGNORE 14
-#define SRE_OP_INFO 15
-#define SRE_OP_JUMP 16
-#define SRE_OP_LITERAL 17
-#define SRE_OP_LITERAL_IGNORE 18
-#define SRE_OP_MARK 19
-#define SRE_OP_MAX_UNTIL 20
-#define SRE_OP_MIN_UNTIL 21
-#define SRE_OP_NOT_LITERAL 22
-#define SRE_OP_NOT_LITERAL_IGNORE 23
-#define SRE_OP_NEGATE 24
-#define SRE_OP_RANGE 25
-#define SRE_OP_REPEAT 26
-#define SRE_OP_REPEAT_ONE 27
-#define SRE_OP_SUBPATTERN 28
+#define SRE_OP_BIGCHARSET 11
+#define SRE_OP_GROUPREF 12
+#define SRE_OP_GROUPREF_IGNORE 13
+#define SRE_OP_IN 14
+#define SRE_OP_IN_IGNORE 15
+#define SRE_OP_INFO 16
+#define SRE_OP_JUMP 17
+#define SRE_OP_LITERAL 18
+#define SRE_OP_LITERAL_IGNORE 19
+#define SRE_OP_MARK 20
+#define SRE_OP_MAX_UNTIL 21
+#define SRE_OP_MIN_UNTIL 22
+#define SRE_OP_NOT_LITERAL 23
+#define SRE_OP_NOT_LITERAL_IGNORE 24
+#define SRE_OP_NEGATE 25
+#define SRE_OP_RANGE 26
+#define SRE_OP_REPEAT 27
+#define SRE_OP_REPEAT_ONE 28
+#define SRE_OP_SUBPATTERN 29
#define SRE_AT_BEGINNING 0
#define SRE_AT_BEGINNING_LINE 1
#define SRE_AT_BEGINNING_STRING 2