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 #define LOG_TAG "Minikin"
20 #include <cutils/log.h>
21 
22 #include <vector>
23 using std::vector;
24 
25 #include <minikin/SparseBitSet.h>
26 #include <minikin/CmapCoverage.h>
27 
28 namespace android {
29 
30 // These could perhaps be optimized to use __builtin_bswap16 and friends.
readU16(const uint8_t * data,size_t offset)31 static uint32_t readU16(const uint8_t* data, size_t offset) {
32     return ((uint32_t)data[offset]) << 8 | ((uint32_t)data[offset + 1]);
33 }
34 
readU32(const uint8_t * data,size_t offset)35 static uint32_t readU32(const uint8_t* data, size_t offset) {
36     return ((uint32_t)data[offset]) << 24 | ((uint32_t)data[offset + 1]) << 16 |
37         ((uint32_t)data[offset + 2]) << 8 | ((uint32_t)data[offset + 3]);
38 }
39 
addRange(vector<uint32_t> & coverage,uint32_t start,uint32_t end)40 static void addRange(vector<uint32_t> &coverage, uint32_t start, uint32_t end) {
41 #ifdef VERBOSE_DEBUG
42     ALOGD("adding range %d-%d\n", start, end);
43 #endif
44     if (coverage.empty() || coverage.back() < start) {
45         coverage.push_back(start);
46         coverage.push_back(end);
47     } else {
48         coverage.back() = end;
49     }
50 }
51 
52 // Get the coverage information out of a Format 4 subtable, storing it in the coverage vector
getCoverageFormat4(vector<uint32_t> & coverage,const uint8_t * data,size_t size)53 static bool getCoverageFormat4(vector<uint32_t>& coverage, const uint8_t* data, size_t size) {
54     const size_t kSegCountOffset = 6;
55     const size_t kEndCountOffset = 14;
56     const size_t kHeaderSize = 16;
57     const size_t kSegmentSize = 8;  // total size of array elements for one segment
58     if (kEndCountOffset > size) {
59         return false;
60     }
61     size_t segCount = readU16(data, kSegCountOffset) >> 1;
62     if (kHeaderSize + segCount * kSegmentSize > size) {
63         return false;
64     }
65     for (size_t i = 0; i < segCount; i++) {
66         uint32_t end = readU16(data, kEndCountOffset + 2 * i);
67         uint32_t start = readU16(data, kHeaderSize + 2 * (segCount + i));
68         if (end < start) {
69             // invalid segment range: size must be positive
70             android_errorWriteLog(0x534e4554, "26413177");
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                     // invalid rangeOffset is considered a "warning" by OpenType Sanitizer
91                     continue;
92                 }
93                 uint32_t glyphId = readU16(data, actualRangeOffset);
94                 if (glyphId != 0) {
95                     addRange(coverage, j, j + 1);
96                 }
97             }
98         }
99     }
100     return true;
101 }
102 
103 // Get the coverage information out of a Format 12 subtable, storing it in the coverage vector
getCoverageFormat12(vector<uint32_t> & coverage,const uint8_t * data,size_t size)104 static bool getCoverageFormat12(vector<uint32_t>& coverage, const uint8_t* data, size_t size) {
105     const size_t kNGroupsOffset = 12;
106     const size_t kFirstGroupOffset = 16;
107     const size_t kGroupSize = 12;
108     const size_t kStartCharCodeOffset = 0;
109     const size_t kEndCharCodeOffset = 4;
110     const size_t kMaxNGroups = 0xfffffff0 / kGroupSize;  // protection against overflow
111     // For all values < kMaxNGroups, kFirstGroupOffset + nGroups * kGroupSize fits in 32 bits.
112     if (kFirstGroupOffset > size) {
113         return false;
114     }
115     uint32_t nGroups = readU32(data, kNGroupsOffset);
116     if (nGroups >= kMaxNGroups || kFirstGroupOffset + nGroups * kGroupSize > size) {
117         android_errorWriteLog(0x534e4554, "25645298");
118         return false;
119     }
120     for (uint32_t i = 0; i < nGroups; i++) {
121         uint32_t groupOffset = kFirstGroupOffset + i * kGroupSize;
122         uint32_t start = readU32(data, groupOffset + kStartCharCodeOffset);
123         uint32_t end = readU32(data, groupOffset + kEndCharCodeOffset);
124         if (end < start) {
125             // invalid group range: size must be positive
126             android_errorWriteLog(0x534e4554, "26413177");
127             return false;
128         }
129         addRange(coverage, start, end + 1);  // file is inclusive, vector is exclusive
130     }
131     return true;
132 }
133 
getCoverage(SparseBitSet & coverage,const uint8_t * cmap_data,size_t cmap_size,bool * has_cmap_format14_subtable)134 bool CmapCoverage::getCoverage(SparseBitSet& coverage, const uint8_t* cmap_data, size_t cmap_size,
135         bool* has_cmap_format14_subtable) {
136     vector<uint32_t> coverageVec;
137     const size_t kHeaderSize = 4;
138     const size_t kNumTablesOffset = 2;
139     const size_t kTableSize = 8;
140     const size_t kPlatformIdOffset = 0;
141     const size_t kEncodingIdOffset = 2;
142     const size_t kOffsetOffset = 4;
143     const uint16_t kUnicodePlatformId = 0;
144     const uint16_t kMicrosoftPlatformId = 3;
145     const uint16_t kUnicodeBmpEncodingId = 1;
146     const uint16_t kVariationSequencesEncodingId = 5;
147     const uint16_t kUnicodeUcs4EncodingId = 10;
148     const uint32_t kNoTable = UINT32_MAX;
149     if (kHeaderSize > cmap_size) {
150         return false;
151     }
152     uint32_t numTables = readU16(cmap_data, kNumTablesOffset);
153     if (kHeaderSize + numTables * kTableSize > cmap_size) {
154         return false;
155     }
156     uint32_t bestTable = kNoTable;
157     bool hasCmapFormat14Subtable = false;
158     for (uint32_t i = 0; i < numTables; i++) {
159         uint16_t platformId = readU16(cmap_data, kHeaderSize + i * kTableSize + kPlatformIdOffset);
160         uint16_t encodingId = readU16(cmap_data, kHeaderSize + i * kTableSize + kEncodingIdOffset);
161         if (platformId == kMicrosoftPlatformId && encodingId == kUnicodeUcs4EncodingId) {
162             bestTable = i;
163             break;
164         } else if (platformId == kMicrosoftPlatformId && encodingId == kUnicodeBmpEncodingId) {
165             bestTable = i;
166         } else if (platformId == kUnicodePlatformId &&
167                 encodingId == kVariationSequencesEncodingId) {
168             uint32_t offset = readU32(cmap_data, kHeaderSize + i * kTableSize + kOffsetOffset);
169             if (offset <= cmap_size - 2 && readU16(cmap_data, offset) == 14) {
170                 hasCmapFormat14Subtable = true;
171             }
172         }
173     }
174     *has_cmap_format14_subtable = hasCmapFormat14Subtable;
175 #ifdef VERBOSE_DEBUG
176     ALOGD("best table = %d\n", bestTable);
177 #endif
178     if (bestTable == kNoTable) {
179         return false;
180     }
181     uint32_t offset = readU32(cmap_data, kHeaderSize + bestTable * kTableSize + kOffsetOffset);
182     if (offset > cmap_size - 2) {
183         return false;
184     }
185     uint16_t format = readU16(cmap_data, offset);
186     bool success = false;
187     const uint8_t* tableData = cmap_data + offset;
188     const size_t tableSize = cmap_size - offset;
189     if (format == 4) {
190         success = getCoverageFormat4(coverageVec, tableData, tableSize);
191     } else if (format == 12) {
192         success = getCoverageFormat12(coverageVec, tableData, tableSize);
193     }
194     if (success) {
195         coverage.initFromRanges(&coverageVec.front(), coverageVec.size() >> 1);
196     }
197 #ifdef VERBOSE_DEBUG
198     for (size_t i = 0; i < coverageVec.size(); i += 2) {
199         ALOGD("%x:%x\n", coverageVec[i], coverageVec[i + 1]);
200     }
201     ALOGD("success = %d", success);
202 #endif
203     return success;
204 }
205 
206 }  // namespace android
207