From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/12676 Path: news.gmane.org!.POSTED!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: Efficient case mapping Date: Thu, 5 Apr 2018 13:09:50 -0400 Message-ID: <20180405170950.GB2176@brightrain.aerifal.cx> References: <20180306202741.GK1436@brightrain.aerifal.cx> <20180307034852.GL1436@brightrain.aerifal.cx> <20180307182536.GO1436@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="Qxx1br4bt0+wmkIi" X-Trace: blaine.gmane.org 1522948085 17715 195.159.176.226 (5 Apr 2018 17:08:05 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 5 Apr 2018 17:08:05 +0000 (UTC) User-Agent: Mutt/1.5.21 (2010-09-15) To: musl@lists.openwall.com Original-X-From: musl-return-12690-gllmg-musl=m.gmane.org@lists.openwall.com Thu Apr 05 19:08:00 2018 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by blaine.gmane.org with smtp (Exim 4.84_2) (envelope-from ) id 1f48Mh-0004SO-KA for gllmg-musl@m.gmane.org; Thu, 05 Apr 2018 19:07:59 +0200 Original-Received: (qmail 20165 invoked by uid 550); 5 Apr 2018 17:10:04 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 20143 invoked from network); 5 Apr 2018 17:10:03 -0000 Content-Disposition: inline In-Reply-To: <20180307182536.GO1436@brightrain.aerifal.cx> Original-Sender: Rich Felker Xref: news.gmane.org gmane.linux.lib.musl.general:12676 Archived-At: --Qxx1br4bt0+wmkIi Content-Type: text/plain; charset=us-ascii Content-Disposition: inline On Wed, Mar 07, 2018 at 01:25:36PM -0500, Rich Felker wrote: > On Tue, Mar 06, 2018 at 10:48:52PM -0500, Rich Felker wrote: > > On Tue, Mar 06, 2018 at 03:27:41PM -0500, Rich Felker wrote: > > > Further optimizing: We're not using all the data we already have. Only > > > alphabetic characters can have case mappings, and we already have an > > > iswalpha table; the above tables are highly correlated with it. > > > > > > If we short-circuit out the whole operation with iswalpha, then the > > > "000 - no case mappings" value is no longer common. Instead, "zero is > > > one of the common deltas" can be included or not on a per-block basis. > > > > > > We can also add, along with the per-block common deltas, a table of > > > which cases each delta goes with, and assign new bit meanings: > > > > > > 00 - is case[0] for block, map to ~case[0] via delta[0] > > > 01 - is case[1] for block, map to ~case[1] via delta[1] > > > 10 - is case[2] for block, map to ~case[2] via delta[2] > > > 11 - is exception, map via binary search of exceptions table > > > > > > If needed we could add back a third bit here, but I think we can get > > > by without it. > > > > > > Note that, because iswalpha is now short-circuiting non-alphabetic > > > characters, we can just assign an arbitrary table value (best: 00) to > > > all non-alphabetic (including unassigned) characters. This drops most > > > of the "simple blocks" (blocks with just 0 or a single delta) down to > > > trivial (elided) blocks. > > > > > > These last ideas ("further optimizing:" and beyond) were worked out > > > while writing this email, and I don't yet have any analysis/test code > > > to go with them. Will follow up later with results. With some luck, > > > final version will be barely-larger than current code, extensible, and > > > fast. :) > > > > I now have results for this approach which I'm attaching. The output > > is from my block analysis tool. For each block, it displays case > > mapping rules sorted by decreasing frequency, with characters that > > don't matter (because they're non-alphabetic) merged into the most > > frequent rule. The syntax is: > > > > rule d(t) [f] > > > > where t is the character type (n = no case, u = uppercase, l = > > lowercase, x = exceptional/titlecase), d is the delta to the opposite > > case character, and f is the frequency of the rule (again, counting > > merging of dontcare into the most frequent). > > > > While the vast majority of blocks are fine with 0-2 bits of rule data, > > a few do have more than 3 fairly-frequent rules, the worst being > > blocks 04, 05, and 2C. Having an extra bit would save at least 169 > > exceptions in those, and thus ~676 bytes. The fixed cost of an extra > > table bit is 512 bytes (for the first level), plus 32 bytes per block > > that contains data, so it's pretty close to break-even, but keeping > > the exception table small does help performance too. My leaning would > > be to add the extra bit, but write a cost function so that it's only > > used where the 4th-7th frequencies for the block total more than 8 > > (the number of exceptions to break even at 32 bytes). > > > > With that approach it looks like we have about 220 entries in the > > exception tables, 4-5 blocks with a third bit, 21 blocks with a second > > bit, 24 blocks with a first bit, and 3 table headers. That comes to > > about 880+160+672+768+1536 = 4k. > > > > One thing I haven't accounted for is storing the 3 (or 7) deltas per > > block. The raw deltas are signed 17-bit, but if we assume mappings > > don't cross planes they can be thought of as unsigned 16-bit on the > > low 16 bits of the codepoint. But that's still pretty large -- 3 > > 16-bit numbers by 512 blocks is 3k. Fortunately I think we can do a > > lot better. First, have a table of all the deltas that ever appear > > (about 20). Then, for each block, have 0-7 single-byte indices into > > this table, and a single-byte index to the sequence of indices. Now we > > just have about 2*20+512+5*7+16*3+3*1 = 638 bytes. > > > > 4.6k is a good bit more than I was planning on spending here, so maybe > > there are still improvements to be made... > > And here is a draft of the code that would use the mapping. The > #ifdef'd external tables are to allow compiling the code without > actually having table data yet; otherwise gcc optimizes out the whole > translation unit. :-) Updated with table output, usable. It comes out to about 5.5k of rodata+text, compared to about 1.5k for the awful, slow, manually-maintained code we have now. In terms of performance, it's about 10x faster on average across all characters with case mappings (iterating and mapping them each), and also 10x faster iterating over all characters and mapping them, presumably since the cost of mapping most non-casing characters is cheap either way. In actual numbers, on my S1260, it averages about 50ns for each case mapping with the new code, and about 500ns with the old. Replacing the case mapping functions with the identity function (still an external call), the overhead seems to be 7-10ns per call, so the difference is more like 40ns vs 490 ns. At this point I'm fairly happy with the results except that the size and logical complexit are somewhat higher than I had hoped for. I wonder if it might be comparable (maybe even smaller) size to do away with the variable sized (per-block) table entries and just always have 2-bit or 3-bit entries. It would certainly make the code simpler and faster. I can probably work out the delta-size without actually writing any code. BTW this work seems to have turned up one omission in musl's current case mappings: U+037F/U+03F3. Any ideas if there's a reason it was omitted, or if this is just a mistake? Rich --Qxx1br4bt0+wmkIi Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="casemap.c" #include #include static const unsigned char tab0[]; static const unsigned char tab1[]; static const unsigned char tab2[]; static const unsigned char rulebases[512]; static const int rules[]; static const unsigned char exceptions[][2]; #include "casemap.h" static int casing_delta(unsigned c, int dir) { unsigned b, x, y, v, rt, xb, xn; int r, rd; if (c >= 0x20000) return 0; b = c>>8; c &= 255; x = c>>3; y = c&7; v = (tab0[tab0[b]*32+x]>>y&1) + (tab1[tab1[b]*32+x]>>y&1)*2 + (tab2[tab2[b]*32+x]>>y&1)*4; /* use the bit vector out of the tables as an index into * a block-specific set of rules and decode the rule into * a type and a case-mapping delta. */ r = rules[rulebases[b]+v]; rt = r & 255; rd = r >> 8; /* rules 0/1 are simple lower/upper case with a delta. * apply according to desired mapping direction. */ if (rt < 2) return rd & -(rt^dir); /* binary search. endpoints of the binary search for * this block are stored in the rule delta field. */ xn = rd & 0xff; xb = (unsigned)rd >> 8; while (xn) { unsigned try = exceptions[xb+xn/2][0]; if (try == c) { r = rules[exceptions[xb+xn/2][1]]; rt = r & 255; rd = r >> 8; if (rt < 2) return rd & -(rt^dir); /* Hard-coded for the four exceptional titlecase */ return dir ? -1 : 1; } else if (try > c) { xn /= 2; } else { xb += xn/2; xn -= xn/2; } } return 0; } wint_t towlower(wint_t wc) { return wc + casing_delta(wc, 0); } wint_t towupper(wint_t wc) { return wc + casing_delta(wc, 1); } --Qxx1br4bt0+wmkIi Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="casemap.h" static const unsigned char tab0[] = { 17, 18, 19, 20, 21, 22, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 23, 16, 16, 24, 16, 16, 16, 16, 16, 16, 16, 16, 25, 26, 27, 28, 16, 29, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 30, 31, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 32, 33, 16, 16, 16, 34, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 35, 16, 16, 16, 16, 36, 16, 16, 16, 16, 16, 16, 16, 37, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 38, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 39, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 1, 0, 0, 248, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 223, 255, 0, 0, 128, 0, 255, 255, 255, 127, 85, 85, 85, 85, 85, 85, 84, 171, 170, 86, 85, 85, 85, 85, 85, 42, 148, 40, 2, 9, 149, 156, 40, 93, 15, 160, 170, 74, 85, 85, 17, 85, 170, 170, 170, 170, 170, 170, 250, 19, 132, 170, 32, 229, 148, 96, 217, 223, 118, 224, 251, 159, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 223, 255, 255, 255, 255, 255, 186, 71, 191, 47, 1, 0, 4, 0, 255, 255, 251, 15, 28, 170, 170, 170, 64, 25, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 85, 85, 85, 85, 253, 87, 85, 85, 85, 85, 85, 85, 170, 42, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 254, 255, 255, 255, 127, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 191, 32, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 192, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 254, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 221, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 213, 183, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 255, 0, 255, 192, 255, 0, 255, 0, 255, 192, 255, 85, 255, 0, 0, 192, 255, 0, 255, 0, 255, 0, 247, 160, 247, 224, 255, 240, 223, 224, 247, 224, 255, 255, 255, 255, 191, 243, 251, 255, 255, 191, 255, 255, 0, 0, 255, 255, 231, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 128, 137, 10, 182, 63, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 85, 245, 175, 247, 255, 255, 255, 255, 255, 191, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 85, 85, 85, 85, 85, 21, 0, 0, 85, 85, 85, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 171, 170, 171, 170, 170, 170, 170, 170, 170, 170, 255, 149, 170, 215, 186, 170, 170, 130, 160, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 254, 255, 255, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }; static const unsigned char tab1[] = { 17, 18, 19, 20, 21, 22, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 23, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 24, 25, 16, 26, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 27, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 28, 29, 16, 16, 16, 30, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 31, 16, 16, 16, 16, 32, 16, 16, 16, 16, 16, 16, 16, 33, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 34, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 35, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 254, 255, 255, 7, 254, 255, 255, 7, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 127, 127, 255, 255, 127, 127, 170, 170, 170, 170, 170, 170, 168, 85, 85, 171, 170, 170, 170, 170, 170, 84, 40, 49, 4, 10, 42, 45, 81, 110, 15, 64, 85, 149, 170, 170, 33, 170, 255, 255, 255, 255, 252, 255, 15, 24, 198, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 56, 0, 7, 254, 255, 251, 15, 254, 255, 251, 15, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 0, 0, 0, 0, 255, 255, 170, 170, 170, 170, 254, 171, 170, 170, 170, 170, 170, 170, 84, 85, 170, 170, 170, 170, 170, 170, 85, 85, 85, 85, 85, 85, 0, 0, 0, 0, 0, 0, 254, 255, 255, 255, 127, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 63, 0, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 234, 183, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 0, 255, 192, 255, 0, 255, 0, 255, 192, 255, 85, 255, 0, 255, 0, 192, 0, 255, 0, 255, 0, 255, 244, 163, 247, 224, 252, 243, 220, 227, 247, 224, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 127, 0, 0, 0, 0, 0, 0, 10, 21, 72, 192, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 170, 10, 80, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 170, 170, 170, 170, 170, 42, 0, 0, 170, 170, 170, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 252, 255, 252, 255, 255, 255, 255, 255, 255, 255, 0, 222, 255, 24, 207, 255, 255, 3, 240, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 254, 255, 255, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 255, 0, 0, 0, 0, 0, 0, 0, 0, 252, 255, 255, 255, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }; static const unsigned char tab2[] = { 16, 16, 16, 17, 18, 19, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 20, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 207, 56, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 255, 255, 255, 128, 13, 255, 255, 0, 0, 0, 0, 255, 255, 255, 255, 255, 255, 0, 0, 0, 0, 252, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 170, 170, 170, 170, 170, 170, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128, 255, 255, 255, 255, 255, 255, 8, 0, 146, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 240, 135, 243, 255, }; static const int rules[] = { 0x302, 0x0, 0x2001, -0x2000, 0x2e700, 0x1dbf00, 0x7900, 0x32c02, 0x101, -0x100, 0x0, -0xc6ff, -0xe800, -0x78ff, -0x12c00, 0xc300, 0xd201, 0xce01, 0xcd01, 0x4f01, 0xca01, 0xcb01, 0xcf01, 0x6100, 0xd301, 0xd101, 0xa300, 0xd501, 0x8200, 0xd601, 0xda01, 0xd901, 0xdb01, 0x3800, 0x201, 0x2, -0x200, -0x4f00, -0x60ff, -0x37ff, 0x2f2d02, 0x0, 0x101, -0x100, -0x81ff, 0x2a2b01, -0xa2ff, 0x2a2801, 0x2a3f00, -0xc2ff, 0x4501, 0x4701, 0x2a1f00, 0x2a1c00, 0x2a1e00, -0xd200, -0xce00, -0xcd00, -0xca00, -0xcb00, 0xa54f00, 0xa54b00, -0xcf00, 0xa52800, 0xa54400, -0xd100, -0xd300, 0x29f700, 0xa54100, 0x29fd00, -0xd500, -0xd600, 0x29e700, -0xda00, 0xa52a00, -0x4500, -0xd900, -0x4700, -0xdb00, 0xa51500, 0xa51200, 0x5c1e02, 0x0, 0x2001, -0x2000, 0x101, -0x100, 0x8200, 0x2501, 0x5400, 0x7401, 0x2601, 0x4001, 0x3f01, -0x2600, -0x2500, -0x1f00, -0x4000, -0x3f00, 0x801, -0x3e00, -0x3900, -0x2f00, -0x3600, -0x800, -0x5600, -0x5000, 0x700, -0x7400, -0x3bff, -0x6000, -0x6ff, 0x7a0202, 0x101, -0x100, 0x2001, -0x2000, 0x5001, -0x5000, 0x0, 0xf01, -0xf00, 0x0, 0x3001, -0x3000, 0x101, -0x100, 0x0, 0x1c6001, 0x7c0602, 0x0, 0x97d001, 0x801, 0x820902, 0x0, -0x186e00, -0x186d00, -0x186400, -0x186200, -0x186300, -0x185c00, -0x182500, 0x89c200, 0x8b0202, 0x0, 0x8a0400, 0xee600, 0x8d0202, 0x101, -0x100, 0x0, -0x3b00, -0x1dbeff, 0x8f2502, 0x800, -0x7ff, 0x0, 0x4a00, 0x5600, 0x6400, 0x8000, 0x7000, 0x7e00, 0x900, -0x49ff, -0x8ff, -0x1c2500, -0x55ff, -0x63ff, -0x6fff, -0x7fff, -0x7dff, 0xb40702, 0x0, 0x1001, -0x1000, -0x1d5cff, -0x20beff, -0x2045ff, 0x1c01, -0x1c00, 0xbb0802, 0x101, -0x100, 0x3001, -0x3000, 0x0, -0x2a3eff, -0xee5ff, -0x29f6ff, -0x29e6ff, -0x2a2b00, -0x2a2800, -0x2a1bff, -0x29fcff, -0x2a1eff, -0x2a1dff, 0x0, -0x1c6000, 0x0, 0x101, -0x100, 0xc30b02, 0x0, 0x101, -0x100, -0x8a03ff, -0xa527ff, -0xa543ff, -0xa54eff, -0xa54aff, -0xa540ff, -0xa511ff, -0xa529ff, -0xa514ff, 0x3a001, 0xce0002, 0x0, -0x97d000, -0x3a000, 0x0, 0x2001, -0x2000, 0x0, 0x2801, -0x2800, 0x0, 0x4001, -0x4000, 0x0, 0x2001, -0x2000, 0x0, 0x2201, -0x2200, }; static const unsigned char rulebases[] = { 0, 7, 40, 81, 112, 122, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 127, 1, 1, 129, 1, 1, 1, 1, 1, 1, 1, 1, 133, 143, 147, 153, 1, 172, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 181, 197, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 199, 202, 1, 1, 1, 216, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 220, 1, 1, 1, 1, 223, 1, 1, 1, 1, 1, 1, 1, 226, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 229, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 232, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, }; static const unsigned char exceptions[][2] = { { 181, 4 }, { 223, 5 }, { 255, 6 }, { 48, 11 }, { 49, 12 }, { 120, 13 }, { 127, 14 }, { 128, 15 }, { 129, 16 }, { 134, 17 }, { 137, 18 }, { 138, 18 }, { 142, 19 }, { 143, 20 }, { 144, 21 }, { 147, 18 }, { 148, 22 }, { 149, 23 }, { 150, 24 }, { 151, 25 }, { 154, 26 }, { 156, 24 }, { 157, 27 }, { 158, 28 }, { 159, 29 }, { 166, 30 }, { 169, 30 }, { 174, 30 }, { 177, 31 }, { 178, 31 }, { 183, 32 }, { 191, 33 }, { 196, 34 }, { 197, 35 }, { 198, 36 }, { 199, 34 }, { 200, 35 }, { 201, 36 }, { 202, 34 }, { 203, 35 }, { 204, 36 }, { 221, 37 }, { 241, 34 }, { 242, 35 }, { 243, 36 }, { 246, 38 }, { 247, 39 }, { 32, 44 }, { 58, 45 }, { 61, 46 }, { 62, 47 }, { 63, 48 }, { 64, 48 }, { 67, 49 }, { 68, 50 }, { 69, 51 }, { 80, 52 }, { 81, 53 }, { 82, 54 }, { 83, 55 }, { 84, 56 }, { 86, 57 }, { 87, 57 }, { 89, 58 }, { 91, 59 }, { 92, 60 }, { 96, 57 }, { 97, 61 }, { 99, 62 }, { 101, 63 }, { 102, 64 }, { 104, 65 }, { 105, 66 }, { 106, 64 }, { 107, 67 }, { 108, 68 }, { 111, 66 }, { 113, 69 }, { 114, 70 }, { 117, 71 }, { 125, 72 }, { 128, 73 }, { 131, 73 }, { 135, 74 }, { 136, 73 }, { 137, 75 }, { 138, 76 }, { 139, 76 }, { 140, 77 }, { 146, 78 }, { 157, 79 }, { 158, 80 }, { 69, 89 }, { 127, 90 }, { 134, 91 }, { 140, 92 }, { 142, 93 }, { 143, 93 }, { 172, 94 }, { 173, 95 }, { 174, 95 }, { 175, 95 }, { 194, 96 }, { 204, 97 }, { 205, 98 }, { 206, 98 }, { 207, 99 }, { 208, 100 }, { 209, 101 }, { 213, 102 }, { 214, 103 }, { 215, 104 }, { 240, 105 }, { 241, 106 }, { 242, 107 }, { 243, 108 }, { 244, 109 }, { 245, 110 }, { 249, 111 }, { 253, 44 }, { 254, 44 }, { 255, 44 }, { 192, 120 }, { 207, 121 }, { 248, 104 }, { 249, 104 }, { 250, 104 }, { 251, 104 }, { 252, 104 }, { 253, 104 }, { 128, 135 }, { 129, 136 }, { 130, 137 }, { 131, 138 }, { 132, 138 }, { 133, 139 }, { 134, 140 }, { 135, 141 }, { 136, 142 }, { 121, 145 }, { 125, 146 }, { 155, 151 }, { 158, 152 }, { 112, 157 }, { 113, 157 }, { 114, 158 }, { 115, 158 }, { 116, 158 }, { 117, 158 }, { 118, 159 }, { 119, 159 }, { 120, 160 }, { 121, 160 }, { 122, 161 }, { 123, 161 }, { 124, 162 }, { 125, 162 }, { 179, 163 }, { 186, 164 }, { 187, 164 }, { 188, 165 }, { 190, 166 }, { 195, 163 }, { 200, 167 }, { 201, 167 }, { 202, 167 }, { 203, 167 }, { 204, 165 }, { 218, 168 }, { 219, 168 }, { 229, 107 }, { 234, 169 }, { 235, 169 }, { 236, 111 }, { 243, 163 }, { 248, 170 }, { 249, 170 }, { 250, 171 }, { 251, 171 }, { 252, 165 }, { 38, 176 }, { 42, 177 }, { 43, 178 }, { 50, 179 }, { 78, 180 }, { 131, 8 }, { 132, 9 }, { 98, 189 }, { 100, 190 }, { 101, 191 }, { 102, 192 }, { 109, 193 }, { 110, 194 }, { 111, 195 }, { 112, 196 }, { 125, 206 }, { 141, 207 }, { 170, 208 }, { 171, 209 }, { 172, 210 }, { 173, 211 }, { 174, 208 }, { 176, 212 }, { 177, 213 }, { 178, 214 }, { 179, 215 }, }; --Qxx1br4bt0+wmkIi--