Towards a smaller encoding for charsets in code

6 files changed, 69 insertions, 28 deletions

diff --git a/lpcode.c b/lpcode.c
index f537904..8dab896 100644
--- a/lpcode.c
+++ b/lpcode.c
@@ -22,6 +22,7 @@ static const Charset fullset_ =
 
 static const Charset *fullset = &fullset_;
 
+
 /*
 ** {======================================================
 ** Analysis and some optimizations
@@ -441,8 +442,8 @@ static int needfollow (TTree *tree) {
 */
 int sizei (const Instruction *i) {
   switch((Opcode)i->i.code) {
-    case ISet: case ISpan: return CHARSETINSTSIZE;
-    case ITestSet: return CHARSETINSTSIZE + 1;
+    case ISet: case ISpan: return 1 + i->i.aux2.set.size;
+    case ITestSet: return 2 + i->i.aux2.set.size;
     case ITestChar: case ITestAny: case IChoice: case IJmp: case ICall:
     case IOpenCall: case ICommit: case IPartialCommit: case IBackCommit:
     case IUTFR:
@@ -585,10 +586,14 @@ static void codechar (CompileState *compst, int c, int tt) {
 /*
 ** Add a charset posfix to an instruction
 */
-static void addcharset (CompileState *compst, const byte *cs) {
+static void addcharset (CompileState *compst, int inst, const byte *cs) {
   int p = gethere(compst);
   int i;
-  for (i = 0; i < (int)CHARSETINSTSIZE - 1; i++)
+  /* for now, all sets use all bits */
+  getinstr(compst, inst).i.aux2.set.offset = 0;
+  getinstr(compst, inst).i.aux2.set.size = instsize(CHARSETSIZE);
+  getinstr(compst, inst).i.aux1 = 0;
+  for (i = 0; i < (int)instsize(CHARSETSIZE); i++)
     nextinstruction(compst);  /* space for buffer */
   /* fill buffer with charset */
   loopset(j, getinstr(compst, p).buff[j] = cs[j]);
@@ -610,8 +615,8 @@ static void codecharset (CompileState *compst, const byte *cs, int tt) {
           cs_equal(cs, getinstr(compst, tt + 2).buff))
         addinstruction(compst, IAny, 0);
       else {
-        addinstruction(compst, ISet, 0);
-        addcharset(compst, cs);
+        int i = addinstruction(compst, ISet, 0);
+        addcharset(compst, i, cs);
       }
       break;
     }
@@ -641,7 +646,7 @@ static int codetestset (CompileState *compst, Charset *cs, int e) {
       }
       case ISet: {
         int i = addoffsetinst(compst, ITestSet);
-        addcharset(compst, cs->cs);
+        addcharset(compst, i, cs->cs);
         return i;
       }
       default: assert(0); return 0;
@@ -793,8 +798,8 @@ static void coderep (CompileState *compst, TTree *tree, int opt,
                      const Charset *fl) {
   Charset st;
   if (tocharset(tree, &st)) {
-    addinstruction(compst, ISpan, 0);
-    addcharset(compst, st.cs);
+    int i = addinstruction(compst, ISpan, 0);
+    addcharset(compst, i, st.cs);
   }
   else {
     int e1 = getfirst(tree, fullset, &st);
diff --git a/lpprint.c b/lpprint.c
index 1b5c488..ed52328 100644
--- a/lpprint.c
+++ b/lpprint.c
@@ -33,6 +33,18 @@ void printcharset (const byte *st) {
 }
 
 
+static void printIcharset (const Instruction *inst, const byte *buff) {
+  byte cs[CHARSETSIZE];
+  int i;
+  loopset(j, cs[j] = 0);
+  for (i = 0; i < CHARSETSIZE << 3; i++) {
+    if (charinset(inst, buff, i))
+      setchar(cs, i);
+  }
+  printcharset(cs);
+}
+
+
 static const char *capkind (int kind) {
   const char *const modes[] = {
     "close", "position", "constant", "backref",
@@ -83,15 +95,15 @@ void printinst (const Instruction *op, const Instruction *p) {
       break;
     }
     case ISet: {
-      printcharset((p+1)->buff);
+      printIcharset(p, (p+1)->buff);
       break;
     }
     case ITestSet: {
-      printcharset((p+2)->buff); printjmp(op, p);
+      printIcharset(p, (p+2)->buff); printjmp(op, p);
       break;
     }
     case ISpan: {
-      printcharset((p+1)->buff);
+      printIcharset(p, (p+1)->buff);
       break;
     }
     case IOpenCall: {
diff --git a/lptypes.h b/lptypes.h
index 81aa61e..d1cd5be 100644
--- a/lptypes.h
+++ b/lptypes.h
@@ -127,19 +127,19 @@ typedef struct Charset {
 #define MAXPATTSIZE     (SHRT_MAX - 10)
 
 
-/* size (in elements) for an instruction plus extra l bytes */
-#define instsize(l)  (((l) + sizeof(Instruction) - 1)/sizeof(Instruction) + 1)
+/* size (in instructions) for l bytes (l > 0) */
+#define instsize(l)  (((l) - 1)/sizeof(Instruction) + 1)
 
 
 /* size (in elements) for a ISet instruction */
-#define CHARSETINSTSIZE         instsize(CHARSETSIZE)
+#define CHARSETINSTSIZE         (1 + instsize(CHARSETSIZE))
 
 /* size (in elements) for a IFunc instruction */
 #define funcinstsize(p)         ((p)->i.aux + 2)
 
 
 
-#define testchar(st,c)  (((int)(st)[((c) >> 3)] & (1 << ((c) & 7))))
+#define testchar(st,c)  ((((unsigned int)(st)[((c) >> 3)]) >> ((c) & 7)) & 1)
 
 
 #endif
diff --git a/lpvm.c b/lpvm.c
index 9ee00a7..f0bb1e7 100644
--- a/lpvm.c
+++ b/lpvm.c
@@ -23,6 +23,16 @@
 static const Instruction giveup = {{IGiveup, 0, {0}}};
 
 
+int charinset (const Instruction *i, const byte *buff, unsigned int c) {
+  c -= (unsigned int)i->i.aux2.set.offset;
+  if (c >= ((unsigned int)i->i.aux2.set.size  /* size in instructions... */
+           * (unsigned int)sizeof(Instruction)  /* in bytes... */
+           * 8u))  /* in bits */
+    return i->i.aux1;  /* out of range */
+  return (testchar(buff, c) != i->i.aux1);
+}
+
+
 /*
 ** Decode one UTF-8 sequence, returning NULL if byte sequence is invalid.
 */
@@ -259,16 +269,16 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
         continue;
       }
       case ISet: {
-        int c = (byte)*s;
-        if (testchar((p+1)->buff, c) && s < e)
-          { p += CHARSETINSTSIZE; s++; }
+        unsigned int c = (byte)*s;
+        if (charinset(p, (p+1)->buff, c) && s < e)
+          { p += 1 + p->i.aux2.set.size; s++; }
         else goto fail;
         continue;
       }
       case ITestSet: {
-        int c = (byte)*s;
-        if (testchar((p + 2)->buff, c) && s < e)
-          p += 1 + CHARSETINSTSIZE;
+        unsigned int c = (byte)*s;
+        if (charinset(p, (p + 2)->buff, c) && s < e)
+          p += 2 + p->i.aux2.set.size;
         else p += getoffset(p);
         continue;
       }
@@ -280,10 +290,10 @@ const char *match (lua_State *L, const char *o, const char *s, const char *e,
       }
       case ISpan: {
         for (; s < e; s++) {
-          int c = (byte)*s;
-          if (!testchar((p+1)->buff, c)) break;
+          unsigned int c = (byte)*s;
+          if (!charinset(p, (p+1)->buff, c)) break;
         }
-        p += CHARSETINSTSIZE;
+        p += 1 + p->i.aux2.set.size;
         continue;
       }
       case IJmp: {
diff --git a/lpvm.h b/lpvm.h
index 607bf48..c02e943 100644
--- a/lpvm.h
+++ b/lpvm.h
@@ -5,15 +5,22 @@
 #include "lpcap.h"
 
 
+/*
+** About Character sets in instructions: a set is a bit map with an
+** initial offset, in bits, and a size, in number of instructions. If
+** aux1 is one, set is inverted (bit == 1 means char is not in set).
+*/
+
+
 /* Virtual Machine's instructions */
 typedef enum Opcode {
   IAny, /* if no char, fail */
   IChar,  /* if char != aux1, fail */
-  ISet,  /* if char not in buff, fail */
+  ISet,  /* if char not in set, fail */
   ITestAny,  /* in no char, jump to 'offset' */
   ITestChar,  /* if char != aux1, jump to 'offset' */
-  ITestSet,  /* if char not in buff, jump to 'offset' */
-  ISpan,  /* read a span of chars in buff */
+  ITestSet,  /* if char not in set, jump to 'offset' */
+  ISpan,  /* read a span of chars in set */
   IUTFR,  /* if codepoint not in range [offset, utf_to], fail */
   IBehind,  /* walk back 'aux1' characters (fail if not possible) */
   IRet,  /* return from a rule */
@@ -43,6 +50,10 @@ typedef union Instruction {
     byte aux1;
     union {
       short key;
+      struct {
+        byte offset;
+        byte size;
+      } set;
     } aux2;
   } i;
   int offset;
@@ -54,6 +65,7 @@ typedef union Instruction {
 #define utf_to(inst)    (((inst)->i.aux2.key << 8) | (inst)->i.aux1)
 
 
+int charinset (const Instruction *i, const byte *buff, unsigned int c);
 void printpatt (Instruction *p, int n);
 const char *match (lua_State *L, const char *o, const char *s, const char *e,
                    Instruction *op, Capture *capture, int ptop);
diff --git a/test.lua b/test.lua
index 439b6cb..d76e3f1 100755
--- a/test.lua
+++ b/test.lua
@@ -117,6 +117,8 @@ eqcharset(m.S"\1\0\2", m.R"\0\2")
 eqcharset(m.S"\1\0\2", m.R"\1\2" + "\0")
 eqcharset(m.S"\1\0\2" - "\0", m.R"\1\2")
 
+eqcharset(m.S("\0\255"), m.P"\0" + "\255")   -- charset extremes
+
 local word = alpha^1 * (1 - alpha)^0
 
 assert((word^0 * -1):match"alo alo")