CmapCoverage.cpp revision ca8ac8acdad662230ae37998c6c4091bb39402b6 
1/*
2 * Copyright (C) 2013 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17// Determine coverage of font given its raw "cmap" OpenType table
18
19#ifdef PRINTF_DEBUG
20#include <stdio.h>
21#endif
22
23#include <vector>
24using std::vector;
25
26#include <minikin/SparseBitSet.h>
27#include <minikin/CmapCoverage.h>
28
29namespace android {
30
31// These could perhaps be optimized to use __builtin_bswap16 and friends.
32static uint32_t readU16(const uint8_t* data, size_t offset) {
33    return ((uint32_t)data[offset]) << 8 | ((uint32_t)data[offset + 1]);
34}
35
36static uint32_t readU32(const uint8_t* data, size_t offset) {
37    return ((uint32_t)data[offset]) << 24 | ((uint32_t)data[offset + 1]) << 16 |
38        ((uint32_t)data[offset + 2]) << 8 | ((uint32_t)data[offset + 3]);
39}
40
41static void addRange(vector<uint32_t> &coverage, uint32_t start, uint32_t end) {
42#ifdef PRINTF_DEBUG
43    printf("adding range %d-%d\n", start, end);
44#endif
45    if (coverage.empty() || coverage.back() < start) {
46        coverage.push_back(start);
47        coverage.push_back(end);
48    } else {
49        coverage.back() = end;
50    }
51}
52
53// Get the coverage information out of a Format 4 subtable, storing it in the coverage vector
54static bool getCoverageFormat4(vector<uint32_t>& coverage, const uint8_t* data, size_t size) {
55    const size_t kSegCountOffset = 6;
56    const size_t kEndCountOffset = 14;
57    const size_t kHeaderSize = 16;
58    const size_t kSegmentSize = 8;  // total size of array elements for one segment
59    if (kEndCountOffset > size) {
60        return false;
61    }
62    size_t segCount = readU16(data, kSegCountOffset) >> 1;
63    if (kHeaderSize + segCount * kSegmentSize > size) {
64        return false;
65    }
66    for (size_t i = 0; i < segCount; i++) {
67        uint32_t end = readU16(data, kEndCountOffset + 2 * i);
68        uint32_t start = readU16(data, kHeaderSize + 2 * (segCount + i));
69        if (end < start) {
70            // invalid segment range: size must be positive
71            return false;
72        }
73        uint32_t rangeOffset = readU16(data, kHeaderSize + 2 * (3 * segCount + i));
74        if (rangeOffset == 0) {
75            uint32_t delta = readU16(data, kHeaderSize + 2 * (2 * segCount + i));
76            if (((end + delta) & 0xffff) > end - start) {
77                addRange(coverage, start, end + 1);
78            } else {
79                for (uint32_t j = start; j < end + 1; j++) {
80                    if (((j + delta) & 0xffff) != 0) {
81                        addRange(coverage, j, j + 1);
82                    }
83                }
84            }
85        } else {
86            for (uint32_t j = start; j < end + 1; j++) {
87                uint32_t actualRangeOffset = kHeaderSize + 6 * segCount + rangeOffset +
88                    (i + j - start) * 2;
89                if (actualRangeOffset + 2 > size) {
90                    return false;
91                }
92                uint32_t glyphId = readU16(data, actualRangeOffset);
93                if (glyphId != 0) {
94                    addRange(coverage, j, j + 1);
95                }
96            }
97        }
98    }
99    return true;
100}
101
102// Get the coverage information out of a Format 12 subtable, storing it in the coverage vector
103static bool getCoverageFormat12(vector<uint32_t>& coverage, const uint8_t* data, size_t size) {
104    const size_t kNGroupsOffset = 12;
105    const size_t kFirstGroupOffset = 16;
106    const size_t kGroupSize = 12;
107    const size_t kStartCharCodeOffset = 0;
108    const size_t kEndCharCodeOffset = 4;
109    const size_t kMaxNGroups = 0xfffffff0 / kGroupSize;  // protection against overflow
110    // For all values < kMaxNGroups, kFirstGroupOffset + nGroups * kGroupSize fits in 32 bits.
111    if (kFirstGroupOffset > size) {
112        return false;
113    }
114    uint32_t nGroups = readU32(data, kNGroupsOffset);
115    if (nGroups >= kMaxNGroups || kFirstGroupOffset + nGroups * kGroupSize > size) {
116        return false;
117    }
118    for (uint32_t i = 0; i < nGroups; i++) {
119        uint32_t groupOffset = kFirstGroupOffset + i * kGroupSize;
120        uint32_t start = readU32(data, groupOffset + kStartCharCodeOffset);
121        uint32_t end = readU32(data, groupOffset + kEndCharCodeOffset);
122        if (end < start) {
123            // invalid group range: size must be positive
124            return false;
125        }
126        addRange(coverage, start, end + 1);  // file is inclusive, vector is exclusive
127    }
128    return true;
129}
130
131bool CmapCoverage::getCoverage(SparseBitSet& coverage, const uint8_t* cmap_data, size_t cmap_size) {
132    vector<uint32_t> coverageVec;
133    const size_t kHeaderSize = 4;
134    const size_t kNumTablesOffset = 2;
135    const size_t kTableSize = 8;
136    const size_t kPlatformIdOffset = 0;
137    const size_t kEncodingIdOffset = 2;
138    const size_t kOffsetOffset = 4;
139    const uint16_t kMicrosoftPlatformId = 3;
140    const uint16_t kUnicodeBmpEncodingId = 1;
141    const uint16_t kUnicodeUcs4EncodingId = 10;
142    const uint32_t kNoTable = UINT32_MAX;
143    if (kHeaderSize > cmap_size) {
144        return false;
145    }
146    uint32_t numTables = readU16(cmap_data, kNumTablesOffset);
147    if (kHeaderSize + numTables * kTableSize > cmap_size) {
148        return false;
149    }
150    uint32_t bestTable = kNoTable;
151    for (uint32_t i = 0; i < numTables; i++) {
152        uint16_t platformId = readU16(cmap_data, kHeaderSize + i * kTableSize + kPlatformIdOffset);
153        uint16_t encodingId = readU16(cmap_data, kHeaderSize + i * kTableSize + kEncodingIdOffset);
154        if (platformId == kMicrosoftPlatformId && encodingId == kUnicodeUcs4EncodingId) {
155            bestTable = i;
156            break;
157        } else if (platformId == kMicrosoftPlatformId && encodingId == kUnicodeBmpEncodingId) {
158            bestTable = i;
159        }
160    }
161#ifdef PRINTF_DEBUG
162    printf("best table = %d\n", bestTable);
163#endif
164    if (bestTable == kNoTable) {
165        return false;
166    }
167    uint32_t offset = readU32(cmap_data, kHeaderSize + bestTable * kTableSize + kOffsetOffset);
168    if (offset > cmap_size - 2) {
169        return false;
170    }
171    uint16_t format = readU16(cmap_data, offset);
172    bool success = false;
173    const uint8_t* tableData = cmap_data + offset;
174    const size_t tableSize = cmap_size - offset;
175    if (format == 4) {
176        success = getCoverageFormat4(coverageVec, tableData, tableSize);
177    } else if (format == 12) {
178        success = getCoverageFormat12(coverageVec, tableData, tableSize);
179    }
180    if (success) {
181        coverage.initFromRanges(&coverageVec.front(), coverageVec.size() >> 1);
182    }
183#ifdef PRINTF_DEBUG
184    for (int i = 0; i < coverageVec.size(); i += 2) {
185        printf("%x:%x\n", coverageVec[i], coverageVec[i + 1]);
186    }
187#endif
188    return success;
189}
190
191}  // namespace android
192