firmware/common/diacritic.c

   1 /***************************************************************************
   2  *             __________               __   ___.
   3  *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
   4  *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
   5  *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
   6  *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
   7  *                     \/            \/     \/    \/            \/
   8  * $Id$
   9  *
  10  * Copyright (C) 2009 Phinitnun Chanasabaeng
  11  *     Initial work
  12  * Copyright (C) 2009 Tomer Shalev
  13  *
  14  * Rockbox diacritic positioning
  15  * Based on initial work by Phinitnun Chanasabaeng
  16  *
  17  * This program is free software; you can redistribute it and/or
  18  * modify it under the terms of the GNU General Public License
  19  * as published by the Free Software Foundation; either version 2
  20  * of the License, or (at your option) any later version.
  21  *
  22  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
  23  * KIND, either express or implied.
  24  *
  25  ****************************************************************************/
  26 #include "diacritic.h"
  27 #include "system.h"
  28
  29 #define DIAC_NUM_RANGES      (ARRAYLEN(diac_ranges))
  30
  31 /* Each diac_range_ struct defines a Unicode range that begins with
  32  * N diacritic characters, and continues with non-diacritic characters up to the
  33  * base of the next item in the array */
  34 struct diac_range
  35 {
  36     unsigned base           : 16;
  37     unsigned num_diacritics :  7;
  38     unsigned is_rtl         :  1;
  39 };
  40
  41 #define DIAC_RANGE_ENTRY(first_diac, first_non_diac, is_rtl) \
  42     { first_diac, first_non_diac - first_diac, is_rtl }
  43
  44 /* Sorted by Unicode value */
  45 static const struct diac_range diac_ranges[] =
  46 {
  47     DIAC_RANGE_ENTRY(0x0000, 0x0000, 0),
  48     DIAC_RANGE_ENTRY(0x0300, 0x0370, 0),
  49     DIAC_RANGE_ENTRY(0x0483, 0x048a, 0),
  50     DIAC_RANGE_ENTRY(0x0591, 0x05be, 1),
  51     DIAC_RANGE_ENTRY(0x05bf, 0x05c0, 1),
  52     DIAC_RANGE_ENTRY(0x05c1, 0x05c3, 1),
  53     DIAC_RANGE_ENTRY(0x05c4, 0x05c6, 1),
  54     DIAC_RANGE_ENTRY(0x05c7, 0x05c8, 1),
  55     DIAC_RANGE_ENTRY(0x0610, 0x061b, 1),
  56     DIAC_RANGE_ENTRY(0x064b, 0x065f, 1),
  57     DIAC_RANGE_ENTRY(0x0670, 0x0671, 1),
  58     DIAC_RANGE_ENTRY(0x06d6, 0x06dd, 1),
  59     DIAC_RANGE_ENTRY(0x06df, 0x06e5, 1),
  60     DIAC_RANGE_ENTRY(0x06e7, 0x06e9, 1),
  61     DIAC_RANGE_ENTRY(0x06ea, 0x06ee, 1),
  62     DIAC_RANGE_ENTRY(0x0711, 0x0712, 1),
  63     DIAC_RANGE_ENTRY(0x0730, 0x074b, 1),
  64     DIAC_RANGE_ENTRY(0x07a6, 0x07b1, 1),
  65     DIAC_RANGE_ENTRY(0x07bf, 0x07c0, 0),
  66     DIAC_RANGE_ENTRY(0x07eb, 0x07f4, 0),
  67     DIAC_RANGE_ENTRY(0x0816, 0x081a, 0),
  68     DIAC_RANGE_ENTRY(0x081b, 0x0824, 0),
  69     DIAC_RANGE_ENTRY(0x0825, 0x0828, 0),
  70     DIAC_RANGE_ENTRY(0x0829, 0x082e, 0),
  71     DIAC_RANGE_ENTRY(0x0900, 0x0904, 0),
  72     DIAC_RANGE_ENTRY(0x093c, 0x093d, 0),
  73     DIAC_RANGE_ENTRY(0x093e, 0x094f, 0),
  74     DIAC_RANGE_ENTRY(0x0951, 0x0956, 0),
  75     DIAC_RANGE_ENTRY(0x0962, 0x0964, 0),
  76     DIAC_RANGE_ENTRY(0x0981, 0x0984, 0),
  77     DIAC_RANGE_ENTRY(0x09bc, 0x09bd, 0),
  78     DIAC_RANGE_ENTRY(0x09be, 0x09ce, 0),
  79     DIAC_RANGE_ENTRY(0x09d7, 0x09d8, 0),
  80     DIAC_RANGE_ENTRY(0x09e2, 0x09e4, 0),
  81     DIAC_RANGE_ENTRY(0x0a01, 0x0a04, 0),
  82     DIAC_RANGE_ENTRY(0x0a3c, 0x0a52, 0),
  83     DIAC_RANGE_ENTRY(0x0a70, 0x0a72, 0),
  84     DIAC_RANGE_ENTRY(0x0a75, 0x0a76, 0),
  85     DIAC_RANGE_ENTRY(0x0a81, 0x0a84, 0),
  86     DIAC_RANGE_ENTRY(0x0abc, 0x0abd, 0),
  87     DIAC_RANGE_ENTRY(0x0abe, 0x0ace, 0),
  88     DIAC_RANGE_ENTRY(0x0ae2, 0x0ae4, 0),
  89     DIAC_RANGE_ENTRY(0x0b01, 0x0b04, 0),
  90     DIAC_RANGE_ENTRY(0x0b3c, 0x0b3d, 0),
  91     DIAC_RANGE_ENTRY(0x0b3e, 0x0b58, 0),
  92     DIAC_RANGE_ENTRY(0x0b82, 0x0b83, 0),
  93     DIAC_RANGE_ENTRY(0x0bbe, 0x0bce, 0),
  94     DIAC_RANGE_ENTRY(0x0bd7, 0x0bd8, 0),
  95     DIAC_RANGE_ENTRY(0x0c01, 0x0c04, 0),
  96     DIAC_RANGE_ENTRY(0x0c3e, 0x0c57, 0),
  97     DIAC_RANGE_ENTRY(0x0c62, 0x0c64, 0),
  98     DIAC_RANGE_ENTRY(0x0c82, 0x0c84, 0),
  99     DIAC_RANGE_ENTRY(0x0cbc, 0x0cbd, 0),
 100     DIAC_RANGE_ENTRY(0x0cbe, 0x0cd7, 0),
 101     DIAC_RANGE_ENTRY(0x0ce2, 0x0ce4, 0),
 102     DIAC_RANGE_ENTRY(0x0d02, 0x0d04, 0),
 103     DIAC_RANGE_ENTRY(0x0d3e, 0x0d58, 0),
 104     DIAC_RANGE_ENTRY(0x0d62, 0x0d64, 0),
 105     DIAC_RANGE_ENTRY(0x0d82, 0x0d84, 0),
 106     DIAC_RANGE_ENTRY(0x0dca, 0x0df4, 0),
 107     DIAC_RANGE_ENTRY(0x0e31, 0x0e32, 0),
 108     DIAC_RANGE_ENTRY(0x0e34, 0x0e3b, 0),
 109     DIAC_RANGE_ENTRY(0x0e47, 0x0e4f, 0),
 110     DIAC_RANGE_ENTRY(0x0eb1, 0x0eb2, 0),
 111     DIAC_RANGE_ENTRY(0x0eb4, 0x0ebd, 0),
 112     DIAC_RANGE_ENTRY(0x0ec8, 0x0ece, 0),
 113     DIAC_RANGE_ENTRY(0x0f18, 0x0f1a, 0),
 114     DIAC_RANGE_ENTRY(0x0f35, 0x0f36, 0),
 115     DIAC_RANGE_ENTRY(0x0f37, 0x0f38, 0),
 116     DIAC_RANGE_ENTRY(0x0f39, 0x0f3a, 0),
 117     DIAC_RANGE_ENTRY(0x0f3e, 0x0f40, 0),
 118     DIAC_RANGE_ENTRY(0x0f71, 0x0f85, 0),
 119     DIAC_RANGE_ENTRY(0x0f86, 0x0f88, 0),
 120     DIAC_RANGE_ENTRY(0x0f90, 0x0fbd, 0),
 121     DIAC_RANGE_ENTRY(0x102b, 0x103f, 0),
 122     DIAC_RANGE_ENTRY(0x1056, 0x105a, 0),
 123     DIAC_RANGE_ENTRY(0x105e, 0x1061, 0),
 124     DIAC_RANGE_ENTRY(0x1062, 0x1065, 0),
 125     DIAC_RANGE_ENTRY(0x1067, 0x106e, 0),
 126     DIAC_RANGE_ENTRY(0x1071, 0x1075, 0),
 127     DIAC_RANGE_ENTRY(0x1082, 0x108e, 0),
 128     DIAC_RANGE_ENTRY(0x108f, 0x1090, 0),
 129     DIAC_RANGE_ENTRY(0x109a, 0x109e, 0),
 130     DIAC_RANGE_ENTRY(0x135f, 0x1360, 0),
 131     DIAC_RANGE_ENTRY(0x1712, 0x1715, 0),
 132     DIAC_RANGE_ENTRY(0x1732, 0x1735, 0),
 133     DIAC_RANGE_ENTRY(0x1752, 0x1754, 0),
 134     DIAC_RANGE_ENTRY(0x1772, 0x1774, 0),
 135     DIAC_RANGE_ENTRY(0x17b6, 0x17d4, 0),
 136     DIAC_RANGE_ENTRY(0x17dd, 0x17de, 0),
 137     DIAC_RANGE_ENTRY(0x18a9, 0x18aa, 0),
 138     DIAC_RANGE_ENTRY(0x1920, 0x193c, 0),
 139     DIAC_RANGE_ENTRY(0x19b0, 0x19c1, 0),
 140     DIAC_RANGE_ENTRY(0x19c8, 0x19ca, 0),
 141     DIAC_RANGE_ENTRY(0x1a17, 0x1a1c, 0),
 142     DIAC_RANGE_ENTRY(0x1a55, 0x1a80, 0),
 143     DIAC_RANGE_ENTRY(0x1b00, 0x1b05, 0),
 144     DIAC_RANGE_ENTRY(0x1b34, 0x1b45, 0),
 145     DIAC_RANGE_ENTRY(0x1b6b, 0x1b74, 0),
 146     DIAC_RANGE_ENTRY(0x1b80, 0x1b83, 0),
 147     DIAC_RANGE_ENTRY(0x1ba1, 0x1bab, 0),
 148     DIAC_RANGE_ENTRY(0x1c24, 0x1c38, 0),
 149     DIAC_RANGE_ENTRY(0x1cd0, 0x1cd3, 0),
 150     DIAC_RANGE_ENTRY(0x1cd4, 0x1ce9, 0),
 151     DIAC_RANGE_ENTRY(0x1ced, 0x1cee, 0),
 152     DIAC_RANGE_ENTRY(0x1cf2, 0x1cf3, 0),
 153     DIAC_RANGE_ENTRY(0x1dc0, 0x1e00, 0),
 154     DIAC_RANGE_ENTRY(0x20d0, 0x20f1, 0),
 155     DIAC_RANGE_ENTRY(0x2cef, 0x2cf2, 0),
 156     DIAC_RANGE_ENTRY(0x2de0, 0x2e00, 0),
 157     DIAC_RANGE_ENTRY(0x302a, 0x3030, 0),
 158     DIAC_RANGE_ENTRY(0x3099, 0x309b, 0),
 159     DIAC_RANGE_ENTRY(0xa66f, 0xa673, 0),
 160     DIAC_RANGE_ENTRY(0xa67c, 0xa67e, 0),
 161     DIAC_RANGE_ENTRY(0xa6f0, 0xa6f2, 0),
 162     DIAC_RANGE_ENTRY(0xa802, 0xa803, 0),
 163     DIAC_RANGE_ENTRY(0xa806, 0xa807, 0),
 164     DIAC_RANGE_ENTRY(0xa80b, 0xa80c, 0),
 165     DIAC_RANGE_ENTRY(0xa823, 0xa828, 0),
 166     DIAC_RANGE_ENTRY(0xa880, 0xa882, 0),
 167     DIAC_RANGE_ENTRY(0xa8b4, 0xa8c5, 0),
 168     DIAC_RANGE_ENTRY(0xa8e0, 0xa8f2, 0),
 169     DIAC_RANGE_ENTRY(0xa926, 0xa92e, 0),
 170     DIAC_RANGE_ENTRY(0xa947, 0xa954, 0),
 171     DIAC_RANGE_ENTRY(0xa980, 0xa984, 0),
 172     DIAC_RANGE_ENTRY(0xa9b3, 0xa9c1, 0),
 173     DIAC_RANGE_ENTRY(0xaa29, 0xaa37, 0),
 174     DIAC_RANGE_ENTRY(0xaa43, 0xaa44, 0),
 175     DIAC_RANGE_ENTRY(0xaa4c, 0xaa4e, 0),
 176     DIAC_RANGE_ENTRY(0xaa7b, 0xaa7c, 0),
 177     DIAC_RANGE_ENTRY(0xaab0, 0xaab1, 0),
 178     DIAC_RANGE_ENTRY(0xaab2, 0xaab5, 0),
 179     DIAC_RANGE_ENTRY(0xaab7, 0xaab9, 0),
 180     DIAC_RANGE_ENTRY(0xaabe, 0xaac0, 0),
 181     DIAC_RANGE_ENTRY(0xaac1, 0xaac2, 0),
 182     DIAC_RANGE_ENTRY(0xabe3, 0xabeb, 0),
 183     DIAC_RANGE_ENTRY(0xabec, 0xabee, 0),
 184     DIAC_RANGE_ENTRY(0xfb1e, 0xfb1f, 0),
 185     DIAC_RANGE_ENTRY(0xfe20, 0xfe27, 0),
 186     DIAC_RANGE_ENTRY(0xfe70, 0xfe70, 1),
 187     DIAC_RANGE_ENTRY(0xff00, 0xff00, 0),
 188     DIAC_RANGE_ENTRY(0xffff, 0xffff, 0),
 189 };
 190
 191 #define MRU_MAX_LEN 32
 192
 193 static unsigned short mru_len = 0;
 194 static unsigned short diacritic_mru[MRU_MAX_LEN];
 195
 196 bool is_diacritic(const unsigned short char_code, bool *is_rtl)
 197 {
 198     unsigned short mru, i;
 199     const struct diac_range *diac;
 200
 201     /* Search in MRU */
 202     for (mru = 0; mru < mru_len; mru++)
 203     {
 204         i = diacritic_mru[mru];
 205
 206         /* Found in MRU */
 207         if (diac_ranges[i].base <= char_code &&
 208                 char_code < diac_ranges[i + 1].base)
 209         {
 210             goto Found;
 211         }
 212     }
 213
 214     /* Search in DB */
 215     for (i = 0; i < DIAC_NUM_RANGES - 1; i++)
 216     {
 217         /* Found */
 218         if (char_code < diac_ranges[i + 1].base)
 219             break;
 220     }
 221
 222     /* Add MRU entry, or overwrite LRU if MRU array is full */
 223     if (mru_len < MRU_MAX_LEN)
 224         mru_len++;
 225     else
 226         mru--;
 227
 228 Found:
 229     /* Promote MRU item to top of MRU */
 230     for ( ; mru > 0; mru--)
 231         diacritic_mru[mru] = diacritic_mru[mru - 1];
 232     diacritic_mru[0] = i;
 233
 234     diac = &diac_ranges[i];
 235
 236     /* Update RTL */
 237     if (is_rtl)
 238         *is_rtl = diac->is_rtl;
 239
 240     return (char_code < diac->base + diac->num_diacritics);
 241 }