OpenTypeUtilities.cpp revision 1693
0N/A/*
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
0N/A * published by the Free Software Foundation. Sun designates this
0N/A * particular file as subject to the "Classpath" exception as provided
0N/A * by Sun in the LICENSE file that accompanied this code.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
0N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0N/A * CA 95054 USA or visit www.sun.com if you need additional information or
0N/A * have any questions.
0N/A *
0N/A */
0N/A
0N/A/*
0N/A *
0N/A * (C) Copyright IBM Corp. 1998-2004 - All Rights Reserved
0N/A *
0N/A */
0N/A
0N/A#include "LETypes.h"
0N/A#include "OpenTypeTables.h"
0N/A#include "OpenTypeUtilities.h"
0N/A#include "LESwaps.h"
0N/A
1693N/AU_NAMESPACE_BEGIN
1693N/A
0N/A//
0N/A// Finds the high bit by binary searching
0N/A// through the bits in n.
0N/A//
0N/Ale_int8 OpenTypeUtilities::highBit(le_int32 value)
0N/A{
0N/A if (value <= 0) {
0N/A return -32;
0N/A }
0N/A
0N/A le_uint8 bit = 0;
0N/A
0N/A if (value >= 1 << 16) {
0N/A value >>= 16;
0N/A bit += 16;
0N/A }
0N/A
0N/A if (value >= 1 << 8) {
0N/A value >>= 8;
0N/A bit += 8;
0N/A }
0N/A
0N/A if (value >= 1 << 4) {
0N/A value >>= 4;
0N/A bit += 4;
0N/A }
0N/A
0N/A if (value >= 1 << 2) {
0N/A value >>= 2;
0N/A bit += 2;
0N/A }
0N/A
0N/A if (value >= 1 << 1) {
0N/A value >>= 1;
0N/A bit += 1;
0N/A }
0N/A
0N/A return bit;
0N/A}
0N/A
0N/AOffset OpenTypeUtilities::getTagOffset(LETag tag, const TagAndOffsetRecord *records, le_int32 recordCount)
0N/A{
0N/A le_uint8 bit = highBit(recordCount);
0N/A le_int32 power = 1 << bit;
0N/A le_int32 extra = recordCount - power;
0N/A le_int32 probe = power;
0N/A le_int32 index = 0;
0N/A
0N/A if (SWAPT(records[extra].tag) <= tag) {
0N/A index = extra;
0N/A }
0N/A
0N/A while (probe > (1 << 0)) {
0N/A probe >>= 1;
0N/A
0N/A if (SWAPT(records[index + probe].tag) <= tag) {
0N/A index += probe;
0N/A }
0N/A }
0N/A
0N/A if (SWAPT(records[index].tag) == tag) {
0N/A return SWAPW(records[index].offset);
0N/A }
0N/A
0N/A return 0;
0N/A}
0N/A
0N/Ale_int32 OpenTypeUtilities::getGlyphRangeIndex(TTGlyphID glyphID, const GlyphRangeRecord *records, le_int32 recordCount)
0N/A{
0N/A le_uint8 bit = highBit(recordCount);
0N/A le_int32 power = 1 << bit;
0N/A le_int32 extra = recordCount - power;
0N/A le_int32 probe = power;
0N/A le_int32 range = 0;
0N/A
0N/A if (SWAPW(records[extra].firstGlyph) <= glyphID) {
0N/A range = extra;
0N/A }
0N/A
0N/A while (probe > (1 << 0)) {
0N/A probe >>= 1;
0N/A
0N/A if (SWAPW(records[range + probe].firstGlyph) <= glyphID) {
0N/A range += probe;
0N/A }
0N/A }
0N/A
0N/A if (SWAPW(records[range].firstGlyph) <= glyphID && SWAPW(records[range].lastGlyph) >= glyphID) {
0N/A return range;
0N/A }
0N/A
0N/A return -1;
0N/A}
0N/A
0N/Ale_int32 OpenTypeUtilities::search(le_uint32 value, const le_uint32 array[], le_int32 count)
0N/A{
0N/A le_int32 power = 1 << highBit(count);
0N/A le_int32 extra = count - power;
0N/A le_int32 probe = power;
0N/A le_int32 index = 0;
0N/A
0N/A if (value >= array[extra]) {
0N/A index = extra;
0N/A }
0N/A
0N/A while (probe > (1 << 0)) {
0N/A probe >>= 1;
0N/A
0N/A if (value >= array[index + probe]) {
0N/A index += probe;
0N/A }
0N/A }
0N/A
0N/A return index;
0N/A}
0N/A
0N/Ale_int32 OpenTypeUtilities::search(le_uint16 value, const le_uint16 array[], le_int32 count)
0N/A{
0N/A le_int32 power = 1 << highBit(count);
0N/A le_int32 extra = count - power;
0N/A le_int32 probe = power;
0N/A le_int32 index = 0;
0N/A
0N/A if (value >= array[extra]) {
0N/A index = extra;
0N/A }
0N/A
0N/A while (probe > (1 << 0)) {
0N/A probe >>= 1;
0N/A
0N/A if (value >= array[index + probe]) {
0N/A index += probe;
0N/A }
0N/A }
0N/A
0N/A return index;
0N/A}
0N/A
0N/A//
0N/A// Straight insertion sort from Knuth vol. III, pg. 81
0N/A//
0N/Avoid OpenTypeUtilities::sort(le_uint16 *array, le_int32 count)
0N/A{
0N/A for (le_int32 j = 1; j < count; j += 1) {
0N/A le_int32 i;
0N/A le_uint16 v = array[j];
0N/A
0N/A for (i = j - 1; i >= 0; i -= 1) {
0N/A if (v >= array[i]) {
0N/A break;
0N/A }
0N/A
0N/A array[i + 1] = array[i];
0N/A }
0N/A
0N/A array[i + 1] = v;
0N/A }
0N/A}
1693N/A
1693N/A
1693N/A
1693N/AU_NAMESPACE_END