Rollup merge of #40709 - lifthrasiir:leaner-unicode-debug-str, r=alexcrichton

Reduce a table used for `Debug` impl of `str`.

This commit shrinks the size of the aforementioned table from 2,102 bytes to 1,197 bytes. This is achieved by an observation that most `u16` entries are common in its upper byte. Specifically:

- `SINGLETONS` now uses two tables, one for (upper byte, lower count) and another for a series of lower bytes. For each upper byte given number of lower bytes are read and compared.

- `NORMAL` now uses a variable length format for the count of "true" codepoints and "false" codepoints (one byte with MSB unset, or two big-endian bytes with the first MSB set).

The code size and relative performance roughly remains same as this commit tries to optimize for both. The new table and algorithm has been verified for the equivalence to older ones.

In my x86-64 macOS laptop with `rustc 1.17.0-nightly (0aeb9c129 2017-03-15)`, `-C opt-level=3 -C lto` gives the following:

* The old routine compiles to 2,102 bytes of data and 416 bytes of code.
* The new routine compiles to 1,197 bytes of data and 448 bytes of code.

Counting a number of all printable Unicode scalar values (128,003, if you wonder) by filtering `0..0x110000` with `std::char::from_u32` and `is_printable` took 50±7ms for both. This can be surprising as the new routine *has* to do more calculations; this is partly explained by the fact that a linear search of `SINGLETONS` has been replaced by *two* linear searches for upper and lower bytes, which greatly reduces the iteration count.

2 files changed, 565 insertions, 805 deletions

diff --git a/src/etc/char_private.py b/src/etc/char_private.py
index 9d15f98e067..75ab3f1a17b 100644
--- a/src/etc/char_private.py
+++ b/src/etc/char_private.py
@@ -76,6 +76,66 @@ def get_codepoints(f):
     for c in range(prev_codepoint + 1, NUM_CODEPOINTS):
         yield Codepoint(c, None)
 
+def compress_singletons(singletons):
+    uppers = [] # (upper, # items in lowers)
+    lowers = []
+
+    for i in singletons:
+        upper = i >> 8
+        lower = i & 0xff
+        if len(uppers) == 0 or uppers[-1][0] != upper:
+            uppers.append((upper, 1))
+        else:
+            upper, count = uppers[-1]
+            uppers[-1] = upper, count + 1
+        lowers.append(lower)
+
+    return uppers, lowers
+
+def compress_normal(normal):
+    # lengths 0x00..0x7f are encoded as 00, 01, ..., 7e, 7f
+    # lengths 0x80..0x7fff are encoded as 80 80, 80 81, ..., ff fe, ff ff
+    compressed = [] # [truelen, (truelenaux), falselen, (falselenaux)]
+
+    prev_start = 0
+    for start, count in normal:
+        truelen = start - prev_start
+        falselen = count
+        prev_start = start + count
+
+        assert truelen < 0x8000 and falselen < 0x8000
+        entry = []
+        if truelen > 0x7f:
+            entry.append(0x80 | (truelen >> 8))
+            entry.append(truelen & 0xff)
+        else:
+            entry.append(truelen & 0x7f)
+        if falselen > 0x7f:
+            entry.append(0x80 | (falselen >> 8))
+            entry.append(falselen & 0xff)
+        else:
+            entry.append(falselen & 0x7f)
+
+        compressed.append(entry)
+
+    return compressed
+
+def print_singletons(uppers, lowers, uppersname, lowersname):
+    print("const {}: &'static [(u8, u8)] = &[".format(uppersname))
+    for u, c in uppers:
+        print("    ({:#04x}, {}),".format(u, c))
+    print("];")
+    print("const {}: &'static [u8] = &[".format(lowersname))
+    for i in range(0, len(lowers), 8):
+        print("    {}".format(" ".join("{:#04x},".format(l) for l in lowers[i:i+8])))
+    print("];")
+
+def print_normal(normal, normalname):
+    print("const {}: &'static [u8] = &[".format(normalname))
+    for v in normal:
+        print("    {}".format(" ".join("{:#04x},".format(i) for i in v)))
+    print("];")
+
 def main():
     file = get_file("http://www.unicode.org/Public/UNIDATA/UnicodeData.txt")
 
@@ -111,6 +171,11 @@ def main():
             else:
                 normal0.append((a, b - a))
 
+    singletons0u, singletons0l = compress_singletons(singletons0)
+    singletons1u, singletons1l = compress_singletons(singletons1)
+    normal0 = compress_normal(normal0)
+    normal1 = compress_normal(normal1)
+
     print("""\
 // Copyright 2012-2016 The Rust Project Developers. See the COPYRIGHT
 // file at the top-level directory of this distribution and at
@@ -125,38 +190,49 @@ def main():
 // NOTE: The following code was generated by "src/etc/char_private.py",
 //       do not edit directly!
 
-use slice::SliceExt;
-
-fn check(x: u16, singletons: &[u16], normal: &[u16]) -> bool {
-    for &s in singletons {
-        if x == s {
-            return false;
-        } else if x < s {
+fn check(x: u16, singletonuppers: &[(u8, u8)], singletonlowers: &[u8],
+         normal: &[u8]) -> bool {
+    let xupper = (x >> 8) as u8;
+    let mut lowerstart = 0;
+    for &(upper, lowercount) in singletonuppers {
+        let lowerend = lowerstart + lowercount as usize;
+        if xupper == upper {
+            for &lower in &singletonlowers[lowerstart..lowerend] {
+                if lower == x as u8 {
+                    return false;
+                }
+            }
+        } else if xupper < upper {
             break;
         }
+        lowerstart = lowerend;
     }
-    for w in normal.chunks(2) {
-        let start = w[0];
-        let len = w[1];
-        let difference = (x as i32) - (start as i32);
-        if 0 <= difference {
-            if difference < len as i32 {
-                return false;
-            }
+
+    let mut x = x as i32;
+    let mut normal = normal.iter().cloned();
+    let mut current = true;
+    while let Some(v) = normal.next() {
+        let len = if v & 0x80 != 0 {
+            ((v & 0x7f) as i32) << 8 | normal.next().unwrap() as i32
         } else {
+            v as i32
+        };
+        x -= len;
+        if x < 0 {
             break;
         }
+        current = !current;
     }
-    true
+    current
 }
 
 pub fn is_printable(x: char) -> bool {
     let x = x as u32;
     let lower = x as u16;
     if x < 0x10000 {
-        check(lower, SINGLETONS0, NORMAL0)
+        check(lower, SINGLETONS0U, SINGLETONS0L, NORMAL0)
     } else if x < 0x20000 {
-        check(lower, SINGLETONS1, NORMAL1)
+        check(lower, SINGLETONS1U, SINGLETONS1L, NORMAL1)
     } else {\
 """)
     for a, b in extra:
@@ -169,22 +245,10 @@ pub fn is_printable(x: char) -> bool {
 }\
 """)
     print()
-    print("const SINGLETONS0: &'static [u16] = &[")
-    for s in singletons0:
-        print("    0x{:x},".format(s))
-    print("];")
-    print("const SINGLETONS1: &'static [u16] = &[")
-    for s in singletons1:
-        print("    0x{:x},".format(s))
-    print("];")
-    print("const NORMAL0: &'static [u16] = &[")
-    for a, b in normal0:
-        print("    0x{:x}, 0x{:x},".format(a, b))
-    print("];")
-    print("const NORMAL1: &'static [u16] = &[")
-    for a, b in normal1:
-        print("    0x{:x}, 0x{:x},".format(a, b))
-    print("];")
+    print_singletons(singletons0u, singletons0l, 'SINGLETONS0U', 'SINGLETONS0L')
+    print_singletons(singletons1u, singletons1l, 'SINGLETONS1U', 'SINGLETONS1L')
+    print_normal(normal0, 'NORMAL0')
+    print_normal(normal1, 'NORMAL1')
 
 if __name__ == '__main__':
     main()
diff --git a/src/libcore/char_private.rs b/src/libcore/char_private.rs
index ddc473592a2..2c0f449b276 100644
--- a/src/libcore/char_private.rs
+++ b/src/libcore/char_private.rs
@@ -11,38 +11,49 @@
 // NOTE: The following code was generated by "src/etc/char_private.py",
 //       do not edit directly!
 
-use slice::SliceExt;
-
-fn check(x: u16, singletons: &[u16], normal: &[u16]) -> bool {
-    for &s in singletons {
-        if x == s {
-            return false;
-        } else if x < s {
+fn check(x: u16, singletonuppers: &[(u8, u8)], singletonlowers: &[u8],
+         normal: &[u8]) -> bool {
+    let xupper = (x >> 8) as u8;
+    let mut lowerstart = 0;
+    for &(upper, lowercount) in singletonuppers {
+        let lowerend = lowerstart + lowercount as usize;
+        if xupper == upper {
+            for &lower in &singletonlowers[lowerstart..lowerend] {
+                if lower == x as u8 {
+                    return false;
+                }
+            }
+        } else if xupper < upper {
             break;
         }
+        lowerstart = lowerend;
     }
-    for w in normal.chunks(2) {
-        let start = w[0];
-        let len = w[1];
-        let difference = (x as i32) - (start as i32);
-        if 0 <= difference {
-            if difference < len as i32 {
-                return false;
-            }
+
+    let mut x = x as i32;
+    let mut normal = normal.iter().cloned();
+    let mut current = true;
+    while let Some(v) = normal.next() {
+        let len = if v & 0x80 != 0 {
+            ((v & 0x7f) as i32) << 8 | normal.next().unwrap() as i32
         } else {
+            v as i32
+        };
+        x -= len;
+        if x < 0 {
             break;
         }
+        current = !current;
     }
-    true
+    current
 }
 
 pub fn is_printable(x: char) -> bool {
     let x = x as u32;
     let lower = x as u16;
     if x < 0x10000 {
-        check(lower, SINGLETONS0, NORMAL0)
+        check(lower, SINGLETONS0U, SINGLETONS0L, NORMAL0)
     } else if x < 0x20000 {
-        check(lower, SINGLETONS1, NORMAL1)
+        check(lower, SINGLETONS1U, SINGLETONS1L, NORMAL1)
     } else {
         if 0x2a6d7 <= x && x < 0x2a700 {
             return false;
@@ -66,761 +77,446 @@ pub fn is_printable(x: char) -> bool {
     }
 }
 
-const SINGLETONS0: &'static [u16] = &[
-    0xad,
-    0x378,
-    0x379,
-    0x38b,
-    0x38d,
-    0x3a2,
-    0x530,
-    0x557,
-    0x558,
-    0x560,
-    0x588,
-    0x58b,
-    0x58c,
-    0x590,
-    0x61c,
-    0x61d,
-    0x6dd,
-    0x70e,
-    0x70f,
-    0x74b,
-    0x74c,
-    0x82e,
-    0x82f,
-    0x83f,
-    0x85c,
-    0x85d,
-    0x8b5,
-    0x8e2,
-    0x984,
-    0x98d,
-    0x98e,
-    0x991,
-    0x992,
-    0x9a9,
-    0x9b1,
-    0x9ba,
-    0x9bb,
-    0x9c5,
-    0x9c6,
-    0x9c9,
-    0x9ca,
-    0x9de,
-    0x9e4,
-    0x9e5,
-    0xa04,
-    0xa11,
-    0xa12,
-    0xa29,
-    0xa31,
-    0xa34,
-    0xa37,
-    0xa3a,
-    0xa3b,
-    0xa3d,
-    0xa49,
-    0xa4a,
-    0xa5d,
-    0xa84,
-    0xa8e,
-    0xa92,
-    0xaa9,
-    0xab1,
-    0xab4,
-    0xaba,
-    0xabb,
-    0xac6,
-    0xaca,
-    0xace,
-    0xacf,
-    0xae4,
-    0xae5,
-    0xb04,
-    0xb0d,
-    0xb0e,
-    0xb11,
-    0xb12,
-    0xb29,
-    0xb31,
-    0xb34,
-    0xb3a,
-    0xb3b,
-    0xb45,
-    0xb46,
-    0xb49,
-    0xb4a,
-    0xb5e,
-    0xb64,
-    0xb65,
-    0xb84,
-    0xb91,
-    0xb9b,
-    0xb9d,
-    0xbc9,
-    0xbce,
-    0xbcf,
-    0xc04,
-    0xc0d,
-    0xc11,
-    0xc29,
-    0xc45,
-    0xc49,
-    0xc57,
-    0xc64,
-    0xc65,
-    0xc84,
-    0xc8d,
-    0xc91,
-    0xca9,
-    0xcb4,
-    0xcba,
-    0xcbb,
-    0xcc5,
-    0xcc9,
-    0xcdf,
-    0xce4,
-    0xce5,
-    0xcf0,
-    0xd04,
-    0xd0d,
-    0xd11,
-    0xd3b,
-    0xd3c,
-    0xd45,
-    0xd49,
-    0xd64,
-    0xd65,
-    0xd80,
-    0xd81,
-    0xd84,
-    0xdb2,
-    0xdbc,
-    0xdbe,
-    0xdbf,
-    0xdd5,
-    0xdd7,
-    0xdf0,
-    0xdf1,
-    0xe83,
-    0xe85,
-    0xe86,
-    0xe89,
-    0xe8b,
-    0xe8c,
-    0xe98,
-    0xea0,
-    0xea4,
-    0xea6,
-    0xea8,
-    0xea9,
-    0xeac,
-    0xeba,
-    0xebe,
-    0xebf,
-    0xec5,
-    0xec7,
-    0xece,
-    0xecf,
-    0xeda,
-    0xedb,
-    0xf48,
-    0xf98,
-    0xfbd,
-    0xfcd,
-    0x10c6,
-    0x10ce,
-    0x10cf,
-    0x1249,
-    0x124e,
-    0x124f,
-    0x1257,
-    0x1259,
-    0x125e,
-    0x125f,
-    0x1289,
-    0x128e,
-    0x128f,
-    0x12b1,
-    0x12b6,
-    0x12b7,
-    0x12bf,
-    0x12c1,
-    0x12c6,
-    0x12c7,
-    0x12d7,
-    0x1311,
-    0x1316,
-    0x1317,
-    0x135b,
-    0x135c,
-    0x13f6,
-    0x13f7,
-    0x13fe,
-    0x13ff,
-    0x1680,
-    0x170d,
-    0x176d,
-    0x1771,
-    0x17de,
-    0x17df,
-    0x180e,
-    0x180f,
-    0x191f,
-    0x196e,
-    0x196f,
-    0x1a1c,
-    0x1a1d,
-    0x1a5f,
-    0x1a7d,
-    0x1a7e,
-    0x1aae,
-    0x1aaf,
-    0x1cf7,
-    0x1f16,
-    0x1f17,
-    0x1f1e,
-    0x1f1f,
-    0x1f46,
-    0x1f47,
-    0x1f4e,
-    0x1f4f,
-    0x1f58,
-    0x1f5a,
-    0x1f5c,
-    0x1f5e,
-    0x1f7e,
-    0x1f7f,
-    0x1fb5,
-    0x1fc5,
-    0x1fd4,
-    0x1fd5,
-    0x1fdc,
-    0x1ff0,
-    0x1ff1,
-    0x1ff5,
-    0x2072,
-    0x2073,
-    0x208f,
-    0x23ff,
-    0x2b74,
-    0x2b75,
-    0x2b96,
-    0x2b97,
-    0x2bc9,
-    0x2c2f,
-    0x2c5f,
-    0x2d26,
-    0x2d2e,
-    0x2d2f,
-    0x2da7,
-    0x2daf,
-    0x2db7,
-    0x2dbf,
-    0x2dc7,
-    0x2dcf,
-    0x2dd7,
-    0x2ddf,
-    0x2e9a,
-    0x3040,
-    0x3097,
-    0x3098,
-    0x318f,
-    0x321f,
-    0x32ff,
-    0xa7af,
-    0xa8fe,
-    0xa8ff,
-    0xa9ce,
-    0xa9ff,
-    0xaa4e,
-    0xaa4f,
-    0xaa5a,
-    0xaa5b,
-    0xab07,
-    0xab08,
-    0xab0f,
-    0xab10,
-    0xab27,
-    0xab2f,
-    0xabee,
-    0xabef,
-    0xfa6e,
-    0xfa6f,
-    0xfb37,
-    0xfb3d,
-    0xfb3f,
-    0xfb42,
-    0xfb45,
-    0xfd90,
-    0xfd91,
-    0xfdfe,
-    0xfdff,
-    0xfe53,
-    0xfe67,
-    0xfe75,
-    0xffc8,
-    0xffc9,
-    0xffd0,
-    0xffd1,
-    0xffd8,
-    0xffd9,
-    0xffe7,
-    0xfffe,
-    0xffff,
+const SINGLETONS0U: &'static [(u8, u8)] = &[
+    (0x00, 1),
+    (0x03, 5),
+    (0x05, 8),
+    (0x06, 3),
+    (0x07, 4),
+    (0x08, 7),
+    (0x09, 16),
+    (0x0a, 27),
+    (0x0b, 24),
+    (0x0c, 22),
+    (0x0d, 20),
+    (0x0e, 22),
+    (0x0f, 4),
+    (0x10, 3),
+    (0x12, 18),
+    (0x13, 9),
+    (0x16, 1),
+    (0x17, 5),
+    (0x18, 2),
+    (0x19, 3),
+    (0x1a, 7),
+    (0x1c, 1),
+    (0x1f, 22),
+    (0x20, 3),
+    (0x23, 1),
+    (0x2b, 5),
+    (0x2c, 2),
+    (0x2d, 11),
+    (0x2e, 1),
+    (0x30, 3),
+    (0x31, 1),
+    (0x32, 2),
+    (0xa7, 1),
+    (0xa8, 2),
+    (0xa9, 2),
+    (0xaa, 4),
+    (0xab, 8),
+    (0xfa, 2),
+    (0xfb, 5),
+    (0xfd, 4),
+    (0xfe, 3),
+    (0xff, 9),
 ];
-const SINGLETONS1: &'static [u16] = &[
-    0xc,
-    0x27,
-    0x3b,
-    0x3e,
-    0x4e,
-    0x4f,
-    0x18f,
-    0x39e,
-    0x49e,
-    0x49f,
-    0x806,
-    0x807,
-    0x809,
-    0x836,
-    0x83d,
-    0x83e,
-    0x856,
-    0x8f3,
-    0x9d0,
-    0x9d1,
-    0xa04,
-    0xa14,
-    0xa18,
-    0xb56,
-    0xb57,
-    0x10bd,
-    0x1135,
-    0x11ce,
-    0x11cf,
-    0x11e0,
-    0x1212,
-    0x1287,
-    0x1289,
-    0x128e,
-    0x129e,
-    0x1304,
-    0x130d,
-    0x130e,
-    0x1311,
-    0x1312,
-    0x1329,
-    0x1331,
-    0x1334,
-    0x133a,
-    0x133b,
-    0x1345,
-    0x1346,
-    0x1349,
-    0x134a,
-    0x134e,
-    0x134f,
-    0x1364,
-    0x1365,
-    0x145a,
-    0x145c,
-    0x15b6,
-    0x15b7,
-    0x1c09,
-    0x1c37,
-    0x1c90,
-    0x1c91,
-    0x1ca8,
-    0x246f,
-    0x6a5f,
-    0x6aee,
-    0x6aef,
-    0x6b5a,
-    0x6b62,
-    0xbc9a,
-    0xbc9b,
-    0xd127,
-    0xd128,
-    0xd455,
-    0xd49d,
-    0xd4a0,
-    0xd4a1,
-    0xd4a3,
-    0xd4a4,
-    0xd4a7,
-    0xd4a8,
-    0xd4ad,
-    0xd4ba,
-    0xd4bc,
-    0xd4c4,
-    0xd506,
-    0xd50b,
-    0xd50c,
-    0xd515,
-    0xd51d,
-    0xd53a,
-    0xd53f,
-    0xd545,
-    0xd551,
-    0xd6a6,
-    0xd6a7,
-    0xd7cc,
-    0xd7cd,
-    0xdaa0,
-    0xe007,
-    0xe019,
-    0xe01a,
-    0xe022,
-    0xe025,
-    0xe8c5,
-    0xe8c6,
-    0xee04,
-    0xee20,
-    0xee23,
-    0xee25,
-    0xee26,
-    0xee28,
-    0xee33,
-    0xee38,
-    0xee3a,
-    0xee48,
-    0xee4a,
-    0xee4c,
-    0xee50,
-    0xee53,
-    0xee55,
-    0xee56,
-    0xee58,
-    0xee5a,
-    0xee5c,
-    0xee5e,
-    0xee60,
-    0xee63,
-    0xee65,
-    0xee66,
-    0xee6b,
-    0xee73,
-    0xee78,
-    0xee7d,
-    0xee7f,
-    0xee8a,
-    0xeea4,
-    0xeeaa,
-    0xf0af,
-    0xf0b0,
-    0xf0c0,
-    0xf0d0,
-    0xf12f,
-    0xf91f,
-    0xf931,
-    0xf932,
-    0xf93f,
+const SINGLETONS0L: &'static [u8] = &[
+    0xad, 0x78, 0x79, 0x8b, 0x8d, 0xa2, 0x30, 0x57,
+    0x58, 0x60, 0x88, 0x8b, 0x8c, 0x90, 0x1c, 0x1d,
+    0xdd, 0x0e, 0x0f, 0x4b, 0x4c, 0x2e, 0x2f, 0x3f,
+    0x5c, 0x5d, 0xb5, 0xe2, 0x84, 0x8d, 0x8e, 0x91,
+    0x92, 0xa9, 0xb1, 0xba, 0xbb, 0xc5, 0xc6, 0xc9,
+    0xca, 0xde, 0xe4, 0xe5, 0x04, 0x11, 0x12, 0x29,
+    0x31, 0x34, 0x37, 0x3a, 0x3b, 0x3d, 0x49, 0x4a,
+    0x5d, 0x84, 0x8e, 0x92, 0xa9, 0xb1, 0xb4, 0xba,
+    0xbb, 0xc6, 0xca, 0xce, 0xcf, 0xe4, 0xe5, 0x04,
+    0x0d, 0x0e, 0x11, 0x12, 0x29, 0x31, 0x34, 0x3a,
+    0x3b, 0x45, 0x46, 0x49, 0x4a, 0x5e, 0x64, 0x65,
+    0x84, 0x91, 0x9b, 0x9d, 0xc9, 0xce, 0xcf, 0x04,
+    0x0d, 0x11, 0x29, 0x45, 0x49, 0x57, 0x64, 0x65,
+    0x84, 0x8d, 0x91, 0xa9, 0xb4, 0xba, 0xbb, 0xc5,
+    0xc9, 0xdf, 0xe4, 0xe5, 0xf0, 0x04, 0x0d, 0x11,
+    0x3b, 0x3c, 0x45, 0x49, 0x64, 0x65, 0x80, 0x81,
+    0x84, 0xb2, 0xbc, 0xbe, 0xbf, 0xd5, 0xd7, 0xf0,
+    0xf1, 0x83, 0x85, 0x86, 0x89, 0x8b, 0x8c, 0x98,
+    0xa0, 0xa4, 0xa6, 0xa8, 0xa9, 0xac, 0xba, 0xbe,
+    0xbf, 0xc5, 0xc7, 0xce, 0xcf, 0xda, 0xdb, 0x48,
+    0x98, 0xbd, 0xcd, 0xc6, 0xce, 0xcf, 0x49, 0x4e,
+    0x4f, 0x57, 0x59, 0x5e, 0x5f, 0x89, 0x8e, 0x8f,
+    0xb1, 0xb6, 0xb7, 0xbf, 0xc1, 0xc6, 0xc7, 0xd7,
+    0x11, 0x16, 0x17, 0x5b, 0x5c, 0xf6, 0xf7, 0xfe,
+    0xff, 0x80, 0x0d, 0x6d, 0x71, 0xde, 0xdf, 0x0e,
+    0x0f, 0x1f, 0x6e, 0x6f, 0x1c, 0x1d, 0x5f, 0x7d,
+    0x7e, 0xae, 0xaf, 0xf7, 0x16, 0x17, 0x1e, 0x1f,
+    0x46, 0x47, 0x4e, 0x4f, 0x58, 0x5a, 0x5c, 0x5e,
+    0x7e, 0x7f, 0xb5, 0xc5, 0xd4, 0xd5, 0xdc, 0xf0,
+    0xf1, 0xf5, 0x72, 0x73, 0x8f, 0xff, 0x74, 0x75,
+    0x96, 0x97, 0xc9, 0x2f, 0x5f, 0x26, 0x2e, 0x2f,
+    0xa7, 0xaf, 0xb7, 0xbf, 0xc7, 0xcf, 0xd7, 0xdf,
+    0x9a, 0x40, 0x97, 0x98, 0x8f, 0x1f, 0xff, 0xaf,
+    0xfe, 0xff, 0xce, 0xff, 0x4e, 0x4f, 0x5a, 0x5b,
+    0x07, 0x08, 0x0f, 0x10, 0x27, 0x2f, 0xee, 0xef,
+    0x6e, 0x6f, 0x37, 0x3d, 0x3f, 0x42, 0x45, 0x90,
+    0x91, 0xfe, 0xff, 0x53, 0x67, 0x75, 0xc8, 0xc9,
+    0xd0, 0xd1, 0xd8, 0xd9, 0xe7, 0xfe, 0xff,
 ];
-const NORMAL0: &'static [u16] = &[
-    0x0, 0x20,
-    0x7f, 0x22,
-    0x380, 0x4,
-    0x5c8, 0x8,
-    0x5eb, 0x5,
-    0x5f5, 0x11,
-    0x7b2, 0xe,
-    0x7fb, 0x5,
-    0x85f, 0x41,
-    0x8be, 0x16,
-    0x9b3, 0x3,
-    0x9cf, 0x8,
-    0x9d8, 0x4,
-    0x9fc, 0x5,
-    0xa0b, 0x4,
-    0xa43, 0x4,
-    0xa4e, 0x3,
-    0xa52, 0x7,
-    0xa5f, 0x7,
-    0xa76, 0xb,
-    0xad1, 0xf,
-    0xaf2, 0x7,
-    0xafa, 0x7,
-    0xb4e, 0x8,
-    0xb58, 0x4,
-    0xb78, 0xa,
-    0xb8b, 0x3,
-    0xb96, 0x3,
-    0xba0, 0x3,
-    0xba5, 0x3,
-    0xbab, 0x3,
-    0xbba, 0x4,
-    0xbc3, 0x3,
-    0xbd1, 0x6,
-    0xbd8, 0xe,
-    0xbfb, 0x5,
-    0xc3a, 0x3,
-    0xc4e, 0x7,
-    0xc5b, 0x5,
-    0xc70, 0x8,
-    0xcce, 0x7,
-    0xcd7, 0x7,
-    0xcf3, 0xe,
-    0xd50, 0x4,
-    0xd97, 0x3,
-    0xdc7, 0x3,
-    0xdcb, 0x4,
-    0xde0, 0x6,
-    0xdf5, 0xc,
-    0xe3b, 0x4,
-    0xe5c, 0x25,
-    0xe8e, 0x6,
-    0xee0, 0x20,
-    0xf6d, 0x4,
-    0xfdb, 0x25,
-    0x10c8, 0x5,
-    0x137d, 0x3,
-    0x139a, 0x6,
-    0x169d, 0x3,
-    0x16f9, 0x7,
-    0x1715, 0xb,
-    0x1737, 0x9,
-    0x1754, 0xc,
-    0x1774, 0xc,
-    0x17ea, 0x6,
-    0x17fa, 0x6,
-    0x181a, 0x6,
-    0x1878, 0x8,
-    0x18ab, 0x5,
-    0x18f6, 0xa,
-    0x192c, 0x4,
-    0x193c, 0x4,
-    0x1941, 0x3,
-    0x1975, 0xb,
-    0x19ac, 0x4,
-    0x19ca, 0x6,
-    0x19db, 0x3,
-    0x1a8a, 0x6,
-    0x1a9a, 0x6,
-    0x1abf, 0x41,
-    0x1b4c, 0x4,
-    0x1b7d, 0x3,
-    0x1bf4, 0x8,
-    0x1c38, 0x3,
-    0x1c4a, 0x3,
-    0x1c89, 0x37,
-    0x1cc8, 0x8,
-    0x1cfa, 0x6,
-    0x1df6, 0x5,
-    0x1fff, 0x11,
-    0x2028, 0x8,
-    0x205f, 0x11,
-    0x209d, 0x3,
-    0x20bf, 0x11,
-    0x20f1, 0xf,
-    0x218c, 0x4,
-    0x2427, 0x19,
-    0x244b, 0x15,
-    0x2bba, 0x3,
-    0x2bd2, 0x1a,
-    0x2bf0, 0x10,
-    0x2cf4, 0x5,
-    0x2d28, 0x5,
-    0x2d68, 0x7,
-    0x2d71, 0xe,
-    0x2d97, 0x9,
-    0x2e45, 0x3b,
-    0x2ef4, 0xc,
-    0x2fd6, 0x1a,
-    0x2ffc, 0x5,
-    0x3100, 0x5,
-    0x312e, 0x3,
-    0x31bb, 0x5,
-    0x31e4, 0xc,
-    0x4db6, 0xa,
-    0x9fd6, 0x2a,
-    0xa48d, 0x3,
-    0xa4c7, 0x9,
-    0xa62c, 0x14,
-    0xa6f8, 0x8,
-    0xa7b8, 0x3f,
-    0xa82c, 0x4,
-    0xa83a, 0x6,
-    0xa878, 0x8,
-    0xa8c6, 0x8,
-    0xa8da, 0x6,
-    0xa954, 0xb,
-    0xa97d, 0x3,
-    0xa9da, 0x4,
-    0xaa37, 0x9,
-    0xaac3, 0x18,
-    0xaaf7, 0xa,
-    0xab17, 0x9,
-    0xab66, 0xa,
-    0xabfa, 0x6,
-    0xd7a4, 0xc,
-    0xd7c7, 0x4,
-    0xd7fc, 0x2104,
-    0xfada, 0x26,
-    0xfb07, 0xc,
-    0xfb18, 0x5,
-    0xfbc2, 0x11,
-    0xfd40, 0x10,
-    0xfdc8, 0x28,
-    0xfe1a, 0x6,
-    0xfe6c, 0x4,
-    0xfefd, 0x4,
-    0xffbf, 0x3,
-    0xffdd, 0x3,
-    0xffef, 0xd,
+const SINGLETONS1U: &'static [(u8, u8)] = &[
+    (0x00, 6),
+    (0x01, 1),
+    (0x03, 1),
+    (0x04, 2),
+    (0x08, 8),
+    (0x09, 2),
+    (0x0a, 3),
+    (0x0b, 2),
+    (0x10, 1),
+    (0x11, 4),
+    (0x12, 5),
+    (0x13, 18),
+    (0x14, 2),
+    (0x15, 2),
+    (0x1c, 5),
+    (0x24, 1),
+    (0x6a, 3),
+    (0x6b, 2),
+    (0xbc, 2),
+    (0xd1, 2),
+    (0xd4, 12),
+    (0xd5, 9),
+    (0xd6, 2),
+    (0xd7, 2),
+    (0xda, 1),
+    (0xe0, 5),
+    (0xe8, 2),
+    (0xee, 32),
+    (0xf0, 4),
+    (0xf1, 1),
+    (0xf9, 4),
 ];
-const NORMAL1: &'static [u16] = &[
+const SINGLETONS1L: &'static [u8] = &[
+    0x0c, 0x27, 0x3b, 0x3e, 0x4e, 0x4f, 0x8f, 0x9e,
+    0x9e, 0x9f, 0x06, 0x07, 0x09, 0x36, 0x3d, 0x3e,
+    0x56, 0xf3, 0xd0, 0xd1, 0x04, 0x14, 0x18, 0x56,
+    0x57, 0xbd, 0x35, 0xce, 0xcf, 0xe0, 0x12, 0x87,
+    0x89, 0x8e, 0x9e, 0x04, 0x0d, 0x0e, 0x11, 0x12,
+    0x29, 0x31, 0x34, 0x3a, 0x3b, 0x45, 0x46, 0x49,
+    0x4a, 0x4e, 0x4f, 0x64, 0x65, 0x5a, 0x5c, 0xb6,
+    0xb7, 0x09, 0x37, 0x90, 0x91, 0xa8, 0x6f, 0x5f,
+    0xee, 0xef, 0x5a, 0x62, 0x9a, 0x9b, 0x27, 0x28,
+    0x55, 0x9d, 0xa0, 0xa1, 0xa3, 0xa4, 0xa7, 0xa8,
+    0xad, 0xba, 0xbc, 0xc4, 0x06, 0x0b, 0x0c, 0x15,
+    0x1d, 0x3a, 0x3f, 0x45, 0x51, 0xa6, 0xa7, 0xcc,
+    0xcd, 0xa0, 0x07, 0x19, 0x1a, 0x22, 0x25, 0xc5,
+    0xc6, 0x04, 0x20, 0x23, 0x25, 0x26, 0x28, 0x33,
+    0x38, 0x3a, 0x48, 0x4a, 0x4c, 0x50, 0x53, 0x55,
+    0x56, 0x58, 0x5a, 0x5c, 0x5e, 0x60, 0x63, 0x65,
+    0x66, 0x6b, 0x73, 0x78, 0x7d, 0x7f, 0x8a, 0xa4,
+    0xaa, 0xaf, 0xb0, 0xc0, 0xd0, 0x2f, 0x1f, 0x31,
+    0x32, 0x3f,
+];
+const NORMAL0: &'static [u8] = &[
+    0x00, 0x20,
+    0x5f, 0x22,
+    0x82, 0xdf, 0x04,
+    0x82, 0x44, 0x08,
+    0x1b, 0x05,
+    0x05, 0x11,
+    0x81, 0xac, 0x0e,
+    0x3b, 0x05,
+    0x5f, 0x41,
+    0x1e, 0x16,
+    0x80, 0xdf, 0x03,
+    0x19, 0x08,
+    0x01, 0x04,
+    0x20, 0x05,
+    0x0a, 0x04,
+    0x34, 0x04,
+    0x07, 0x03,
+    0x01, 0x07,
+    0x06, 0x07,
+    0x10, 0x0b,
+    0x50, 0x0f,
+    0x12, 0x07,
+    0x01, 0x07,
+    0x4d, 0x08,
+    0x02, 0x04,
+    0x1c, 0x0a,
+    0x09, 0x03,
+    0x08, 0x03,
+    0x07, 0x03,
+    0x02, 0x03,
+    0x03, 0x03,
+    0x0c, 0x04,
+    0x05, 0x03,
+    0x0b, 0x06,
+    0x01, 0x0e,
+    0x15, 0x05,
+    0x3a, 0x03,
+    0x11, 0x07,
+    0x06, 0x05,
+    0x10, 0x08,
+    0x56, 0x07,
+    0x02, 0x07,
+    0x15, 0x0e,
+    0x4f, 0x04,
+    0x43, 0x03,
+    0x2d, 0x03,
+    0x01, 0x04,
+    0x11, 0x06,
+    0x0f, 0x0c,
+    0x3a, 0x04,
+    0x1d, 0x25,
+    0x0d, 0x06,
+    0x4c, 0x20,
+    0x6d, 0x04,
+    0x6a, 0x25,
+    0x80, 0xc8, 0x05,
+    0x82, 0xb0, 0x03,
+    0x1a, 0x06,
+    0x82, 0xfd, 0x03,
+    0x59, 0x07,
+    0x15, 0x0b,
+    0x17, 0x09,
+    0x14, 0x0c,
+    0x14, 0x0c,
+    0x6a, 0x06,
+    0x0a, 0x06,
+    0x1a, 0x06,
+    0x58, 0x08,
+    0x2b, 0x05,
+    0x46, 0x0a,
+    0x2c, 0x04,
+    0x0c, 0x04,
+    0x01, 0x03,
+    0x31, 0x0b,
+    0x2c, 0x04,
+    0x1a, 0x06,
+    0x0b, 0x03,
+    0x80, 0xac, 0x06,
+    0x0a, 0x06,
+    0x1f, 0x41,
+    0x4c, 0x04,
+    0x2d, 0x03,
+    0x74, 0x08,
+    0x3c, 0x03,
+    0x0f, 0x03,
+    0x3c, 0x37,
+    0x08, 0x08,
+    0x2a, 0x06,
+    0x80, 0xf6, 0x05,
+    0x82, 0x04, 0x11,
+    0x18, 0x08,
+    0x2f, 0x11,
+    0x2d, 0x03,
+    0x1f, 0x11,
+    0x21, 0x0f,
+    0x80, 0x8c, 0x04,
+    0x82, 0x97, 0x19,
+    0x0b, 0x15,
+    0x87, 0x5a, 0x03,
+    0x15, 0x1a,
+    0x04, 0x10,
+    0x80, 0xf4, 0x05,
+    0x2f, 0x05,
+    0x3b, 0x07,
+    0x02, 0x0e,
+    0x18, 0x09,
+    0x80, 0xa5, 0x3b,
+    0x74, 0x0c,
+    0x80, 0xd6, 0x1a,
+    0x0c, 0x05,
+    0x80, 0xff, 0x05,
+    0x29, 0x03,
+    0x80, 0x8a, 0x05,
+    0x24, 0x0c,
+    0x9b, 0xc6, 0x0a,
+    0xd2, 0x16, 0x2a,
+    0x84, 0x8d, 0x03,
+    0x37, 0x09,
+    0x81, 0x5c, 0x14,
+    0x80, 0xb8, 0x08,
+    0x80, 0xb8, 0x3f,
+    0x35, 0x04,
+    0x0a, 0x06,
+    0x38, 0x08,
+    0x46, 0x08,
+    0x0c, 0x06,
+    0x74, 0x0b,
+    0x1e, 0x03,
+    0x5a, 0x04,
+    0x59, 0x09,
+    0x80, 0x83, 0x18,
+    0x1c, 0x0a,
+    0x16, 0x09,
+    0x46, 0x0a,
+    0x80, 0x8a, 0x06,
+    0xab, 0xa4, 0x0c,
+    0x17, 0x04,
+    0x31, 0xa1, 0x04,
+    0x81, 0xda, 0x26,
+    0x07, 0x0c,
+    0x05, 0x05,
+    0x80, 0xa5, 0x11,
+    0x81, 0x6d, 0x10,
+    0x78, 0x28,
+    0x2a, 0x06,
+    0x4c, 0x04,
+    0x80, 0x8d, 0x04,
+    0x80, 0xbe, 0x03,
+    0x1b, 0x03,
+    0x0f, 0x0d,
+];
+const NORMAL1: &'static [u8] = &[
+    0x5e, 0x22,
+    0x7b, 0x05,
+    0x03, 0x04,
+    0x2d, 0x03,
+    0x65, 0x04,
+    0x01, 0x2f,
+    0x2e, 0x80, 0x82,
+    0x1d, 0x03,
+    0x31, 0x0f,
+    0x1c, 0x04,
+    0x24, 0x0c,
+    0x1b, 0x05,
+    0x2b, 0x05,
+    0x44, 0x04,
+    0x0e, 0x2a,
+    0x80, 0xaa, 0x06,
+    0x24, 0x04,
+    0x24, 0x04,
+    0x28, 0x08,
+    0x34, 0x0b,
+    0x01, 0x80, 0x90,
+    0x81, 0x37, 0x09,
+    0x16, 0x0a,
+    0x08, 0x80, 0x98,
+    0x39, 0x03,
+    0x63, 0x08,
+    0x09, 0x30,
+    0x16, 0x05,
+    0x21, 0x03,
+    0x1b, 0x05,
+    0x01, 0x40,
+    0x38, 0x04,
+    0x4b, 0x05,
+    0x28, 0x04,
+    0x03, 0x04,
+    0x09, 0x08,
+    0x09, 0x07,
+    0x40, 0x20,
+    0x27, 0x04,
+    0x0c, 0x09,
+    0x36, 0x03,
+    0x3a, 0x05,
+    0x1a, 0x07,
+    0x04, 0x0c,
+    0x07, 0x50,
+    0x49, 0x37,
+    0x33, 0x0d,
+    0x33, 0x07,
+    0x06, 0x81, 0x60,
+    0x1f, 0x81, 0x81,
+    0x4e, 0x04,
+    0x1e, 0x0f,
+    0x43, 0x0e,
+    0x19, 0x07,
+    0x0a, 0x06,
+    0x44, 0x0c,
+    0x27, 0x09,
+    0x75, 0x0b,
+    0x3f, 0x41,
+    0x2a, 0x06,
+    0x3b, 0x05,
+    0x0a, 0x06,
+    0x51, 0x06,
+    0x01, 0x05,
+    0x10, 0x03,
+    0x05, 0x80, 0x8b,
+    0x5e, 0x22,
+    0x48, 0x08,
+    0x0a, 0x80, 0xa6,
     0x5e, 0x22,
-    0xfb, 0x5,
-    0x103, 0x4,
-    0x134, 0x3,
-    0x19c, 0x4,
-    0x1a1, 0x2f,
-    0x1fe, 0x82,
-    0x29d, 0x3,
-    0x2d1, 0xf,
-    0x2fc, 0x4,
-    0x324, 0xc,
-    0x34b, 0x5,
-    0x37b, 0x5,
-    0x3c4, 0x4,
-    0x3d6, 0x2a,
-    0x4aa, 0x6,
-    0x4d4, 0x4,
-    0x4fc, 0x4,
-    0x528, 0x8,
-    0x564, 0xb,
-    0x570, 0x90,
-    0x737, 0x9,
-    0x756, 0xa,
-    0x768, 0x98,
-    0x839, 0x3,
-    0x89f, 0x8,
-    0x8b0, 0x30,
-    0x8f6, 0x5,
-    0x91c, 0x3,
-    0x93a, 0x5,
-    0x940, 0x40,
-    0x9b8, 0x4,
-    0xa07, 0x5,
-    0xa34, 0x4,
-    0xa3b, 0x4,
-    0xa48, 0x8,
-    0xa59, 0x7,
-    0xaa0, 0x20,
-    0xae7, 0x4,
-    0xaf7, 0x9,
-    0xb36, 0x3,
-    0xb73, 0x5,
-    0xb92, 0x7,
-    0xb9d, 0xc,
-    0xbb0, 0x50,
-    0xc49, 0x37,
-    0xcb3, 0xd,
-    0xcf3, 0x7,
-    0xd00, 0x160,
-    0xe7f, 0x181,
-    0x104e, 0x4,
-    0x1070, 0xf,
-    0x10c2, 0xe,
-    0x10e9, 0x7,
-    0x10fa, 0x6,
-    0x1144, 0xc,
-    0x1177, 0x9,
-    0x11f5, 0xb,
-    0x123f, 0x41,
-    0x12aa, 0x6,
-    0x12eb, 0x5,
-    0x12fa, 0x6,
-    0x1351, 0x6,
-    0x1358, 0x5,
-    0x136d, 0x3,
-    0x1375, 0x8b,
-    0x145e, 0x22,
-    0x14c8, 0x8,
-    0x14da, 0xa6,
-    0x15de, 0x22,
-    0x1645, 0xb,
-    0x165a, 0x6,
-    0x166d, 0x13,
-    0x16b8, 0x8,
-    0x16ca, 0x36,
-    0x171a, 0x3,
-    0x172c, 0x4,
-    0x1740, 0x160,
-    0x18f3, 0xc,
-    0x1900, 0x1c0,
-    0x1af9, 0x107,
-    0x1c46, 0xa,
-    0x1c6d, 0x3,
-    0x1cb7, 0x349,
-    0x239a, 0x66,
-    0x2475, 0xb,
-    0x2544, 0xabc,
-    0x342f, 0xfd1,
-    0x4647, 0x21b9,
-    0x6a39, 0x7,
-    0x6a6a, 0x4,
-    0x6a70, 0x60,
-    0x6af6, 0xa,
-    0x6b46, 0xa,
-    0x6b78, 0x5,
-    0x6b90, 0x370,
-    0x6f45, 0xb,
-    0x6f7f, 0x10,
-    0x6fa0, 0x40,
-    0x6fe1, 0x1f,
-    0x87ed, 0x13,
-    0x8af3, 0x250d,
-    0xb002, 0xbfe,
-    0xbc6b, 0x5,
-    0xbc7d, 0x3,
-    0xbc89, 0x7,
-    0xbca0, 0x1360,
-    0xd0f6, 0xa,
-    0xd173, 0x8,
-    0xd1e9, 0x17,
-    0xd246, 0xba,
-    0xd357, 0x9,
-    0xd372, 0x8e,
-    0xd547, 0x3,
-    0xda8c, 0xf,
-    0xdab0, 0x550,
-    0xe02b, 0x7d5,
-    0xe8d7, 0x29,
-    0xe94b, 0x5,
-    0xe95a, 0x4,
-    0xe960, 0x4a0,
-    0xee3c, 0x6,
-    0xee43, 0x4,
-    0xee9c, 0x5,
-    0xeebc, 0x34,
-    0xeef2, 0x10e,
-    0xf02c, 0x4,
-    0xf094, 0xc,
-    0xf0f6, 0xa,
-    0xf10d, 0x3,
-    0xf16c, 0x4,
-    0xf1ad, 0x39,
-    0xf203, 0xd,
-    0xf23c, 0x4,
-    0xf249, 0x7,
-    0xf252, 0xae,
-    0xf6d3, 0xd,
-    0xf6ed, 0x3,
-    0xf6f7, 0x9,
-    0xf774, 0xc,
-    0xf7d5, 0x2b,
-    0xf80c, 0x4,
-    0xf848, 0x8,
-    0xf85a, 0x6,
-    0xf888, 0x8,
-    0xf8ae, 0x62,
-    0xf928, 0x8,
-    0xf94c, 0x4,
-    0xf95f, 0x21,
-    0xf992, 0x2e,
-    0xf9c1, 0x63f,
+    0x45, 0x0b,
+    0x0a, 0x06,
+    0x0d, 0x13,
+    0x38, 0x08,
+    0x0a, 0x36,
+    0x1a, 0x03,
+    0x0f, 0x04,
+    0x10, 0x81, 0x60,
+    0x53, 0x0c,
+    0x01, 0x81, 0xc0,
+    0x39, 0x81, 0x07,
+    0x46, 0x0a,
+    0x1d, 0x03,
+    0x47, 0x83, 0x49,
+    0x83, 0x9a, 0x66,
+    0x75, 0x0b,
+    0x80, 0xc4, 0x8a, 0xbc,
+    0x84, 0x2f, 0x8f, 0xd1,
+    0x82, 0x47, 0xa1, 0xb9,
+    0x82, 0x39, 0x07,
+    0x2a, 0x04,
+    0x02, 0x60,
+    0x26, 0x0a,
+    0x46, 0x0a,
+    0x28, 0x05,
+    0x13, 0x83, 0x70,
+    0x45, 0x0b,
+    0x2f, 0x10,
+    0x11, 0x40,
+    0x01, 0x1f,
+    0x97, 0xed, 0x13,
+    0x82, 0xf3, 0xa5, 0x0d,
+    0x02, 0x8b, 0xfe,
+    0x6b, 0x05,
+    0x0d, 0x03,
+    0x09, 0x07,
+    0x10, 0x93, 0x60,
+    0x80, 0xf6, 0x0a,
+    0x73, 0x08,
+    0x6e, 0x17,
+    0x46, 0x80, 0xba,
+    0x57, 0x09,
+    0x12, 0x80, 0x8e,
+    0x81, 0x47, 0x03,
+    0x85, 0x42, 0x0f,
+    0x15, 0x85, 0x50,
+    0x2b, 0x87, 0xd5,
+    0x80, 0xd7, 0x29,
+    0x4b, 0x05,
+    0x0a, 0x04,
+    0x02, 0x84, 0xa0,
+    0x3c, 0x06,
+    0x01, 0x04,
+    0x55, 0x05,
+    0x1b, 0x34,
+    0x02, 0x81, 0x0e,
+    0x2c, 0x04,
+    0x64, 0x0c,
+    0x56, 0x0a,
+    0x0d, 0x03,
+    0x5c, 0x04,
+    0x3d, 0x39,
+    0x1d, 0x0d,
+    0x2c, 0x04,
+    0x09, 0x07,
+    0x02, 0x80, 0xae,
+    0x83, 0xd3, 0x0d,
+    0x0d, 0x03,
+    0x07, 0x09,
+    0x74, 0x0c,
+    0x55, 0x2b,
+    0x0c, 0x04,
+    0x38, 0x08,
+    0x0a, 0x06,
+    0x28, 0x08,
+    0x1e, 0x62,
+    0x18, 0x08,
+    0x1c, 0x04,
+    0x0f, 0x21,
+    0x12, 0x2e,
+    0x01, 0x86, 0x3f,
 ];