icuSources/layout/OpenTypeUtilities.cpp

   1 /*
   2  *
   3  * (C) Copyright IBM Corp. 1998-2013 - All Rights Reserved
   4  *
   5  */
   6
   7 #include "LETypes.h"
   8 #include "OpenTypeTables.h"
   9 #include "OpenTypeUtilities.h"
  10 #include "LESwaps.h"
  11
  12 U_NAMESPACE_BEGIN
  13
  14 //
  15 // Finds the high bit by binary searching
  16 // through the bits in n.
  17 //
  18 le_int8 OpenTypeUtilities::highBit(le_int32 value)
  19 {
  20     if (value <= 0) {
  21         return -32;
  22     }
  23
  24     le_uint8 bit = 0;
  25
  26     if (value >= 1 << 16) {
  27         value >>= 16;
  28         bit += 16;
  29     }
  30
  31     if (value >= 1 << 8) {
  32         value >>= 8;
  33         bit += 8;
  34     }
  35
  36     if (value >= 1 << 4) {
  37         value >>= 4;
  38         bit += 4;
  39     }
  40
  41     if (value >= 1 << 2) {
  42         value >>= 2;
  43         bit += 2;
  44     }
  45
  46     if (value >= 1 << 1) {
  47         value >>= 1;
  48         bit += 1;
  49     }
  50
  51     return bit;
  52 }
  53
  54
  55 Offset OpenTypeUtilities::getTagOffset(LETag tag, const LEReferenceToArrayOf<TagAndOffsetRecord> &records, LEErrorCode &success)
  56 {
  57   const TagAndOffsetRecord *r0 = (const TagAndOffsetRecord*)records.getAlias();
  58   if(LE_FAILURE(success)) return 0;
  59
  60   le_uint32 recordCount = records.getCount();
  61   le_uint8 bit = highBit(recordCount);
  62   le_int32 power = 1 << bit;
  63   le_int32 extra = recordCount - power;
  64   le_int32 probe = power;
  65   le_int32 index = 0;
  66
  67   {
  68     const ATag &aTag = (r0+extra)->tag;
  69     if (SWAPT(aTag) <= tag) {
  70       index = extra;
  71     }
  72   }
  73
  74   while (probe > (1 << 0)) {
  75     probe >>= 1;
  76
  77     {
  78       const ATag &aTag = (r0+index+probe)->tag;
  79       if (SWAPT(aTag) <= tag) {
  80         index += probe;
  81       }
  82     }
  83   }
  84
  85   {
  86     const ATag &aTag = (r0+index)->tag;
  87     if (SWAPT(aTag) == tag) {
  88       return SWAPW((r0+index)->offset);
  89     }
  90   }
  91
  92   return 0;
  93 }
  94
  95 le_int32 OpenTypeUtilities::getGlyphRangeIndex(TTGlyphID glyphID, const LEReferenceToArrayOf<GlyphRangeRecord> &records, LEErrorCode &success)
  96 {
  97   if(LE_FAILURE(success)) return -1;
  98
  99     le_uint32 recordCount = records.getCount();
 100     le_uint8 bit = highBit(recordCount);
 101     le_int32 power = 1 << bit;
 102     le_int32 extra = recordCount - power;
 103     le_int32 probe = power;
 104     le_int32 range = 0;
 105
 106     if (recordCount == 0) {
 107       return -1;
 108     }
 109
 110     if (SWAPW(records(extra,success).firstGlyph) <= glyphID) {
 111         range = extra;
 112     }
 113
 114     while (probe > (1 << 0) && LE_SUCCESS(success)) {
 115         probe >>= 1;
 116
 117         if (SWAPW(records(range + probe,success).firstGlyph) <= glyphID) {
 118             range += probe;
 119         }
 120     }
 121
 122     if (SWAPW(records(range,success).firstGlyph) <= glyphID && SWAPW(records(range,success).lastGlyph) >= glyphID) {
 123         return range;
 124     }
 125
 126     return -1;
 127 }
 128
 129 le_int32 OpenTypeUtilities::search(le_uint32 value, const le_uint32 array[], le_int32 count)
 130 {
 131     le_int32 power = 1 << highBit(count);
 132     le_int32 extra = count - power;
 133     le_int32 probe = power;
 134     le_int32 index = 0;
 135
 136     if (value >= array[extra]) {
 137         index = extra;
 138     }
 139
 140     while (probe > (1 << 0)) {
 141         probe >>= 1;
 142
 143         if (value >= array[index + probe]) {
 144             index += probe;
 145         }
 146     }
 147
 148     return index;
 149 }
 150
 151 le_int32 OpenTypeUtilities::search(le_uint16 value, const le_uint16 array[], le_int32 count)
 152 {
 153     le_int32 power = 1 << highBit(count);
 154     le_int32 extra = count - power;
 155     le_int32 probe = power;
 156     le_int32 index = 0;
 157
 158     if (value >= array[extra]) {
 159         index = extra;
 160     }
 161
 162     while (probe > (1 << 0)) {
 163         probe >>= 1;
 164
 165         if (value >= array[index + probe]) {
 166             index += probe;
 167         }
 168     }
 169
 170     return index;
 171 }
 172
 173 //
 174 // Straight insertion sort from Knuth vol. III, pg. 81
 175 //
 176 void OpenTypeUtilities::sort(le_uint16 *array, le_int32 count)
 177 {
 178     for (le_int32 j = 1; j < count; j += 1) {
 179         le_int32 i;
 180         le_uint16 v = array[j];
 181
 182         for (i = j - 1; i >= 0; i -= 1) {
 183             if (v >= array[i]) {
 184                 break;
 185             }
 186
 187             array[i + 1] = array[i];
 188         }
 189
 190         array[i + 1] = v;
 191     }
 192 }
 193
 194 U_NAMESPACE_END
 195
 196 #if LE_ASSERT_BAD_FONT
 197 #include <stdio.h>
 198
 199 static const char *letagToStr(LETag tag, char *str) {
 200   str[0]= 0xFF & (tag>>24);
 201   str[1]= 0xFF & (tag>>16);
 202   str[2]= 0xFF & (tag>>8);
 203   str[3]= 0xFF & (tag>>0);
 204   str[4]= 0;
 205   return str;
 206 }
 207
 208 U_CAPI void U_EXPORT2 _debug_LETableReference(const char *f, int l, const char *msg, const LETableReference *what, const void *ptr, size_t len) {
 209   char tagbuf[5];
 210
 211   fprintf(stderr, "%s:%d: LETableReference@0x%p: ", f, l, what);
 212   fprintf(stderr, msg, ptr, len);
 213   fprintf(stderr, "\n");
 214
 215   for(int depth=0;depth<10&&(what!=NULL);depth++) {
 216     for(int i=0;i<depth;i++) {
 217       fprintf(stderr, " "); // indent
 218     }
 219     if(!what->isValid()) {
 220       fprintf(stderr, "(invalid)");
 221     }
 222     fprintf(stderr, "@%p: tag (%s) font (0x%p), [0x%p+0x%lx]\n", what, letagToStr(what->getTag(), tagbuf), what->getFont(),
 223             what->getAlias(), what->getLength());
 224
 225     what = what->getParent();
 226   }
 227 }
 228 #endif