1 /*
   2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.  Oracle designates this
   7  * particular file as subject to the "Classpath" exception as provided
   8  * by Oracle in the LICENSE file that accompanied this code.
   9  *
  10  * This code is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13  * version 2 for more details (a copy is included in the LICENSE file that
  14  * accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License version
  17  * 2 along with this work; if not, write to the Free Software Foundation,
  18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  19  *
  20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  21  * or visit www.oracle.com if you need additional information or have any
  22  * questions.
  23  *
  24  */
  25 
  26 /*
  27  *
  28  *
  29  * (C) Copyright IBM Corp. 2004-2010 - All Rights Reserved
  30  *
  31  */
  32 
  33 #include "KernTable.h"
  34 #include "LEFontInstance.h"
  35 #include "LEGlyphStorage.h"
  36 
  37 #include "LESwaps.h"
  38 #include "OpenTypeUtilities.h"
  39 
  40 #include <stdio.h>
  41 
  42 #define DEBUG_KERN_TABLE 0
  43 
  44 U_NAMESPACE_BEGIN
  45 
  46 struct PairInfo {
  47   le_uint32 key;   // sigh, MSVC compiler gags on union here
  48   le_int16  value; // fword, kern value in funits
  49 };
  50 #define KERN_PAIRINFO_SIZE 6
  51 LE_CORRECT_SIZE(PairInfo, KERN_PAIRINFO_SIZE)
  52 struct Subtable_0 {
  53   le_uint16 nPairs;
  54   le_uint16 searchRange;
  55   le_uint16 entrySelector;
  56   le_uint16 rangeShift;
  57 };
  58 #define KERN_SUBTABLE_0_HEADER_SIZE 8
  59 LE_CORRECT_SIZE(Subtable_0, KERN_SUBTABLE_0_HEADER_SIZE)
  60 
  61 // Kern table version 0 only
  62 struct SubtableHeader {
  63   le_uint16 version;
  64   le_uint16 length;
  65   le_uint16 coverage;
  66 };
  67 #define KERN_SUBTABLE_HEADER_SIZE 6
  68 LE_CORRECT_SIZE(SubtableHeader, KERN_SUBTABLE_HEADER_SIZE)
  69 
  70 // Version 0 only, version 1 has different layout
  71 struct KernTableHeader {
  72   le_uint16 version;
  73   le_uint16 nTables;
  74 };
  75 #define KERN_TABLE_HEADER_SIZE 4
  76 LE_CORRECT_SIZE(KernTableHeader, KERN_TABLE_HEADER_SIZE)
  77 
  78 #define COVERAGE_HORIZONTAL 0x1
  79 #define COVERAGE_MINIMUM 0x2
  80 #define COVERAGE_CROSS 0x4
  81 #define COVERAGE_OVERRIDE 0x8
  82 
  83 /*
  84  * This implementation has support for only one subtable, so if the font has
  85  * multiple subtables, only the first will be used.  If this turns out to
  86  * be a problem in practice we should add it.
  87  *
  88  * This also supports only version 0 of the kern table header, only
  89  * Apple supports the latter.
  90  *
  91  * This implementation isn't careful about the kern table flags, and
  92  * might invoke kerning when it is not supposed to.  That too I'm
  93  * leaving for a bug fix.
  94  *
  95  * TODO: support multiple subtables
  96  * TODO: respect header flags
  97  */
  98 KernTable::KernTable(const LETableReference& base, LEErrorCode &success)
  99   : pairsSwapped(NULL), fTable(base)
 100 {
 101   if(LE_FAILURE(success) || (fTable.isEmpty())) {
 102 #if DEBUG_KERN_TABLE
 103     fprintf(stderr, "no kern data\n");
 104 #endif
 105     return;
 106   }
 107   LEReferenceTo<KernTableHeader> header(fTable, success);
 108 
 109 #if DEBUG_KERN_TABLE
 110   // dump first 32 bytes of header
 111   for (int i = 0; i < 64; ++i) {
 112     fprintf(stderr, "%0.2x ", ((const char*)header.getAlias())[i]&0xff);
 113     if (((i+1)&0xf) == 0) {
 114       fprintf(stderr, "\n");
 115     } else if (((i+1)&0x7) == 0) {
 116       fprintf(stderr, "  ");
 117     }
 118   }
 119 #endif
 120 
 121   if(LE_FAILURE(success)) return;
 122 
 123   if (!header.isEmpty() && header->version == 0 && SWAPW(header->nTables) > 0) {
 124     LEReferenceTo<SubtableHeader> subhead(header, success, KERN_TABLE_HEADER_SIZE);
 125 
 126     if (LE_SUCCESS(success) && !subhead.isEmpty() && subhead->version == 0) {
 127       coverage = SWAPW(subhead->coverage);
 128       if (coverage & COVERAGE_HORIZONTAL) { // only handle horizontal kerning
 129         LEReferenceTo<Subtable_0> table(subhead, success, KERN_SUBTABLE_HEADER_SIZE);
 130 
 131         if(table.isEmpty() || LE_FAILURE(success)) return;
 132 
 133         nPairs        = SWAPW(table->nPairs);
 134 
 135 #if 0   // some old fonts have bad values here...
 136         searchRange   = SWAPW(table->searchRange);
 137         entrySelector = SWAPW(table->entrySelector);
 138         rangeShift    = SWAPW(table->rangeShift);
 139 #else
 140         entrySelector = OpenTypeUtilities::highBit(nPairs);
 141         searchRange   = (1 << entrySelector) * KERN_PAIRINFO_SIZE;
 142         rangeShift    = (nPairs * KERN_PAIRINFO_SIZE) - searchRange;
 143 #endif
 144 
 145         if(LE_SUCCESS(success) && nPairs>0) {
 146           // pairsSwapped is an instance member, and table is on the stack.
 147           // set 'pairsSwapped' based on table.getAlias(). This will range check it.
 148 
 149           pairsSwapped = (PairInfo*)(fTable.getFont()->getKernPairs());
 150           if (pairsSwapped == NULL) {
 151             LEReferenceToArrayOf<PairInfo>pairs =
 152               LEReferenceToArrayOf<PairInfo>(fTable, // based on overall table
 153                                              success,
 154                                              (const PairInfo*)table.getAlias(),  // subtable 0 + ..
 155                                              KERN_SUBTABLE_0_HEADER_SIZE,  // .. offset of header size
 156                                              nPairs); // count
 157             if (LE_SUCCESS(success) && pairs.isValid()) {
 158               pairsSwapped =  (PairInfo*)(malloc(nPairs*sizeof(PairInfo)));
 159               PairInfo *p = (PairInfo*)pairsSwapped;
 160               for (int i = 0; LE_SUCCESS(success) && i < nPairs; i++, p++) {
 161                 memcpy(p, pairs.getAlias(i,success), KERN_PAIRINFO_SIZE);
 162                 p->key = SWAPL(p->key);
 163               }
 164               fTable.getFont()->setKernPairs((void*)pairsSwapped); // store it
 165             }
 166           }
 167         }
 168 
 169 #if 0
 170         fprintf(stderr, "coverage: %0.4x nPairs: %d pairs %p\n", coverage, nPairs, pairsSwapped);
 171         fprintf(stderr, "  searchRange: %d entrySelector: %d rangeShift: %d\n", searchRange, entrySelector, rangeShift);
 172         fprintf(stderr, "[[ ignored font table entries: range %d selector %d shift %d ]]\n", SWAPW(table->searchRange), SWAPW(table->entrySelector), SWAPW(table->rangeShift));
 173 #endif
 174 #if DEBUG_KERN_TABLE
 175         fprintf(stderr, "coverage: %0.4x nPairs: %d pairs 0x%x\n", coverage, nPairs, pairsSwapped);
 176         fprintf(stderr,
 177           "  searchRange(pairs): %d entrySelector: %d rangeShift(pairs): %d\n",
 178           searchRange, entrySelector, rangeShift);
 179 
 180         {
 181           // dump part of the pair list
 182           char ids[256];
 183           for (int i = 256; --i >= 0;) {
 184             LEGlyphID id = font->mapCharToGlyph(i);
 185             if (id < 256) {
 186               ids[id] = (char)i;
 187             }
 188           }
 189           PairInfo *p = pairsSwapped;
 190           for (int i = 0; i < nPairs; ++i, p++) {
 191             le_uint32 k = p->key;
 192             le_uint16 left = (k >> 16) & 0xffff;
 193             le_uint16 right = k & 0xffff;
 194             if (left < 256 && right < 256) {
 195               char c = ids[left];
 196               if (c > 0x20 && c < 0x7f) {
 197                 fprintf(stderr, "%c/", c & 0xff);
 198               } else {
 199                 fprintf(stderr, "%0.2x/", c & 0xff);
 200               }
 201               c = ids[right];
 202               if (c > 0x20 && c < 0x7f) {
 203                 fprintf(stderr, "%c ", c & 0xff);
 204               } else {
 205                 fprintf(stderr, "%0.2x ", c & 0xff);
 206               }
 207             }
 208           }
 209         }
 210 #endif
 211       }
 212     }
 213   }
 214 }
 215 
 216 
 217 /*
 218  * Process the glyph positions.  The positions array has two floats for each
 219  * glyph, plus a trailing pair to mark the end of the last glyph.
 220  */
 221 void KernTable::process(LEGlyphStorage& storage, LEErrorCode &success)
 222 {
 223   if(LE_FAILURE(success)) return;
 224 
 225   if (pairsSwapped) {
 226     success = LE_NO_ERROR;
 227 
 228     le_uint32 key = storage[0]; // no need to mask off high bits
 229     float adjust = 0;
 230 
 231     for (int i = 1, e = storage.getGlyphCount(); LE_SUCCESS(success)&&  i < e; ++i) {
 232       key = key << 16 | (storage[i] & 0xffff);
 233 
 234       // argh, to do a binary search, we need to have the pair list in sorted order
 235       // but it is not in sorted order on win32 platforms because of the endianness difference
 236       // so either I have to swap the element each time I examine it, or I have to swap
 237       // all the elements ahead of time and store them in the font
 238 
 239       const PairInfo* p = pairsSwapped;
 240       const PairInfo* tp = (const PairInfo*)(p + (rangeShift/KERN_PAIRINFO_SIZE)); /* rangeshift is in original table bytes */
 241       if (key > tp->key) {
 242         p = tp;
 243       }
 244 
 245 #if DEBUG_KERN_TABLE
 246       fprintf(stderr, "binary search for %0.8x\n", key);
 247 #endif
 248 
 249       le_uint32 probe = searchRange;
 250       while (probe > 1) {
 251         probe >>= 1;
 252         tp = (const PairInfo*)(p + (probe/KERN_PAIRINFO_SIZE));
 253         le_uint32 tkey = tp->key;
 254 #if DEBUG_KERN_TABLE
 255         fprintf(stdout, "   %.3d (%0.8x)\n", (tp - pairsSwapped), tkey);
 256 #endif
 257         if (tkey <= key) {
 258           if (tkey == key) {
 259             le_int16 value = SWAPW(tp->value);
 260 #if DEBUG_KERN_TABLE
 261             fprintf(stdout, "binary found kerning pair %x:%x at %d, value: 0x%x (%g)\n",
 262                     storage[i-1], storage[i], i, value & 0xffff, font->xUnitsToPoints(value));
 263             fflush(stdout);
 264 #endif
 265             // Have to undo the device transform.
 266             // REMIND either find a way to do this only if there is a
 267             // device transform, or a faster way, such as moving the
 268             // entire kern table up to Java.
 269             LEPoint pt;
 270             pt.fX = fTable.getFont()->xUnitsToPoints(value);
 271             pt.fY = 0;
 272 
 273             fTable.getFont()->getKerningAdjustment(pt);
 274             adjust += pt.fX;
 275             break;
 276           }
 277           p = tp;
 278         }
 279       }
 280 
 281       storage.adjustPosition(i, adjust, 0, success);
 282     }
 283     storage.adjustPosition(storage.getGlyphCount(), adjust, 0, success);
 284   }
 285 }
 286 
 287 U_NAMESPACE_END
 288