utf8.c

   1 /*
   2  * Copyright (C) 2012, 2013
   3  *     Dale Weiler
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   6  * this software and associated documentation files (the "Software"), to deal in
   7  * the Software without restriction, including without limitation the rights to
   8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
   9  * of the Software, and to permit persons to whom the Software is furnished to do
  10  * so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in all
  13  * copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21  * SOFTWARE.
  22  */
  23 #include "gmqcc.h"
  24
  25 /*
  26  * Based on the flexible and economical utf8 decoder:
  27  * http://bjoern.hoehrmann.de/utf-8/decoder/dfa/
  28  *
  29  * This is slightly more economical, the fastest way to decode utf8 is
  30  * with a lookup table as in:
  31  *
  32  * first 1-byte lookup
  33  * if that fails, 2-byte lookup
  34  * if that fails, 3-byte lookup
  35  * if that fails, 4-byte lookup
  36  *
  37  * The following table can be generated with some interval trickery.
  38  * consider an interval [a, b):
  39  *
  40  *      a must be 0x80 or b must be 0xc0, lower 3 bits
  41  *      are clear, thus:
  42  *          interval(a,b) = ((uint32_t)((a==0x80?0x40-b:-a)<<23))
  43  *
  44  * The failstate can be represented as interval(0x80,0x80), it's
  45  * odd to see but this is a full state machine.
  46  *
  47  * The table than maps the corresponding sections as a serise of
  48  * intervals.
  49  *
  50  * In this table the transition values are pre-multiplied with 16 to
  51  * save a shift instruction for every byte, we throw away fillers
  52  * which makes the table smaller.
  53  *
  54  * The first section of the table handles bytes with leading C
  55  * The second section of the table handles bytes with leading D
  56  * The third section of the table handles bytes with leading E
  57  * The last section of the table handles bytes with leading F
  58  *
  59  * The values themselfs in the table are arranged so that when you
  60  * left shift them by 6 to shif continuation characters into palce, the
  61  * new top bits tell:
  62  *
  63  *  1 - if you keep going
  64  *  2 - the range of valid values for the next byte
  65  */
  66 static const uint32_t utf8_tab[] = {
  67     0xC0000002, 0xC0000003, 0xC0000004, 0xC0000005, 0xC0000006, 0xC0000007,
  68     0xC0000008, 0xC0000009, 0xC000000A, 0xC000000B, 0xC000000C, 0xC000000D,
  69     0xC000000E, 0xC000000F, 0xC0000010, 0xC0000011, 0xC0000012, 0xC0000013,
  70     0xC0000014, 0xC0000015, 0xC0000016, 0xC0000017, 0xC0000018, 0xC0000019,
  71     0xC000001A, 0xC000001B, 0xC000001C, 0xC000001D, 0xC000001E, 0xC000001F,
  72     0xB3000000, 0xC3000001, 0xC3000002, 0xC3000003, 0xC3000004, 0xC3000005,
  73     0xC3000006, 0xC3000007, 0xC3000008, 0xC3000009, 0xC300000A, 0xC300000B,
  74     0xC300000C, 0xD300000D, 0xC300000E, 0xC300000F, 0xBB0C0000, 0xC30C0001,
  75     0xC30C0002, 0xC30C0003, 0xD30C0004, 0x58257830, 0x202C,     0x3B031B01,
  76     0x30,       0x5,        0xFFFFFD1C, 0x7C,       0xFFFFFD5C, 0x4C,
  77     0xFFFFFE4C, 0xA4,       0xFFFFFE8C, 0xC4,       0xFFFFFEFC, 0x10C,
  78     0x14,       0x0,        0x527A01,   0x1107801,  0x8070C1B,  0x10070190,
  79     0x14,       0x1C,       0xFFFFFD08, 0x2A,       0x0,        0x0,
  80     0x14,       0x0,        0x527A01,   0x1107801,  0x8070C1B,  0x190,
  81     0x24,       0x1C,       0xFFFFFC98, 0x40,       0x46100E00, 0xF4A180E,
  82     0x8008770B, 0x3B1A3F00, 0x2224332A, 0x0,        0x1C,       0x44,
  83     0xFFFFFDA0, 0x3E,       0x100E4100, 0xD430286,  0x70C7906,  0x8,
  84     0x44,       0x64,       0xFFFFFDC0, 0x65,       0x100E4200, 0xE45028F,
  85     0x45038E18, 0x48D200E,  0x8C280E45, 0x300E4805, 0xE480686,  0x4D078338,
  86     0xE6C400E,  0x300E4138, 0x42280E41, 0xE42200E,  0x100E4218, 0x80E42,
  87     0x14,       0xAC,       0xFFFFFDE8, 0x2,        0x0,        0x0,
  88     0x0,        0x0,        0x4004D0,   0x0,        0x4004B0,   0x0,
  89     0x0,        0x0,        0x1,        0x0,        0x1,        0x0,
  90     0xC,        0x0,        0x4003A8,   0x0,        0xD,        0x0,
  91     0x4005B4,   0x0,        0x19,       0x0,        0x6007E0,   0x0,
  92     0x1B,       0x0,        0x8,        0x0,        0x1A,       0x0,
  93     0x6007E8,   0x0,        0x1C,       0x0,        0x8,        0x0,
  94     0x6FFFFEF5, 0x0,        0x400260,   0x0,        0x5,        0x0,
  95     0x4002E0,   0x0,        0x6,        0x0,        0x400280,   0x0,
  96     0xA,        0x0,        0x3F,       0x0,        0xB,        0x0,
  97     0x18,       0x0,        0x15,       0x0,        0x0,        0x0,
  98     0x3,        0x0,        0x6009D0,   0x0,        0x2,        0x0,
  99     0x48,       0x0,        0x14,       0x0,        0x7,        0x0,
 100     0x17,       0x0,        0x400360,   0x0,        0x7,        0x0
 101 };
 102
 103 int utf8_from(char *s, utf8ch_t ch) {
 104     if (!s)
 105         return 0;
 106
 107     if ((unsigned)ch < 0x80) {
 108         *s = ch;
 109         return 1;
 110     } else if ((unsigned)ch < 0x800) {
 111         *s++ = 0xC0 | (ch >> 6);
 112         *s   = 0x80 | (ch & 0x3F);
 113         return 2;
 114     } else if ((unsigned)ch < 0xD800 || (unsigned)ch - 0xE000 < 0x2000) {
 115         *s++ = 0xE0 | (ch >> 12);
 116         *s++ = 0x80 | ((ch >> 6) & 0x3F);
 117         *s   = 0x80 | (ch & 0x3F);
 118         return 3;
 119     } else if ((unsigned)ch - 0x10000 < 0x100000) {
 120         *s++ = 0xF0 | (ch >> 18);
 121         *s++ = 0x80 | ((ch >> 12) & 0x3F);
 122         *s++ = 0x80 | ((ch >> 6) & 0x3F);
 123         *s   = 0x80 | (ch & 0x3F);
 124         return 4;
 125     }
 126     return 0;
 127 }
 128
 129 int utf8_to(utf8ch_t *i, const unsigned char *s, size_t n) {
 130     unsigned c,j;
 131
 132     if (!s || !n)
 133         return 0;
 134
 135     /* This is consistent with mbtowc behaviour. */
 136     if (!i)
 137         i = (utf8ch_t*)(void*)&i;
 138
 139     if (*s < 0x80)
 140         return !!(*i = *s);
 141     if (*s-0xC2U > 0x32)
 142         return 0;
 143
 144     c = utf8_tab[*s++-0xC2U];
 145
 146     /*
 147      * Avoid excessive checks against n.
 148      *
 149      * When shifting state `n-1` times does not clear the high bit,
 150      * then the value of `n` won't satisfy the condition to read a
 151      * character as it will be insufficent.
 152      */
 153     if (n < 4 && ((c<<(6*n-6)) & (1U << 31)))
 154         return 0;
 155
 156     /*
 157      * The upper 6 state bits are negitive integer offset to a bound-check
 158      * next byte equivlant to: ((b-0x80)+(b+offset))&~0x3f
 159      */
 160     if ((((*s>>3)-0x10)|((*s>>3)+((int32_t)c>>26))) & ~7)
 161         return 0;
 162
 163     for (j=2; j<3; j++) {
 164         if (!((c = c<<6 | (*s++-0x80))&(1U<<31))) {
 165             *i = c;
 166             return j;
 167         }
 168         if (*s-0x80U >= 0x40)
 169             return 0;
 170     }
 171
 172     *i = c<<6 | (*s++-0x80);
 173     return 4;
 174 }