diff options
Diffstat (limited to 'Build/source/texk/dvisvgm/dvisvgm-1.4/src/CMap.cpp')
| -rw-r--r-- | Build/source/texk/dvisvgm/dvisvgm-1.4/src/CMap.cpp | 221 |
1 files changed, 221 insertions, 0 deletions
diff --git a/Build/source/texk/dvisvgm/dvisvgm-1.4/src/CMap.cpp b/Build/source/texk/dvisvgm/dvisvgm-1.4/src/CMap.cpp new file mode 100644 index 00000000000..870962f0714 --- /dev/null +++ b/Build/source/texk/dvisvgm/dvisvgm-1.4/src/CMap.cpp @@ -0,0 +1,221 @@ +/************************************************************************* +** CMap.cpp ** +** ** +** This file is part of dvisvgm -- the DVI to SVG converter ** +** Copyright (C) 2005-2013 Martin Gieseking <martin.gieseking@uos.de> ** +** ** +** This program is free software; you can redistribute it and/or ** +** modify it under the terms of the GNU General Public License as ** +** published by the Free Software Foundation; either version 3 of ** +** the License, or (at your option) any later version. ** +** ** +** This program is distributed in the hope that it will be useful, but ** +** WITHOUT ANY WARRANTY; without even the implied warranty of ** +** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** +** GNU General Public License for more details. ** +** ** +** You should have received a copy of the GNU General Public License ** +** along with this program; if not, see <http://www.gnu.org/licenses/>. ** +*************************************************************************/ + +#include <algorithm> +#include <sstream> +#include <set> +#include <vector> +#include "CMap.h" +#include "FileFinder.h" +#include "InputReader.h" + +using namespace std; + + +const char* CMap::path () const { + return FileFinder::lookup(name(), "cmap", false); +} + + +/** Returns the RO (Registry-Ordering) string of the CMap. */ +string SegmentedCMap::getROString() const { + if (_registry.empty() || _ordering.empty()) + return ""; + return _registry + "-" + _ordering; +} + + +/** Tries to merge range r into this one. This is only possible if the ranges + * touch or overlap and if the assigned CIDs match at the junction points. + * @param[in] r range to join + * @return true if join was successful */ +bool SegmentedCMap::Range::join (const Range &r) { + // check most common cases first + if (_max+1 < r._min || _min-1 > r._max) // disjoint ranges? + return false; + if (r._min-1 == _max) { // does r touch *this on the right? + if (decode(r._min) == r._cid) { + _max = r._max; + return true; + } + return false; + } + if (r._max+1 == _min) { // does r touch *this on the left + if (r.decode(_min) == _cid) { + setMinAndAdaptCID(r._min); + return true; + } + return false; + } + // the following cases should be pretty rare + if (r._min <= _min && r._max >= _max) { // does r overlap *this on both sides? + *this = r; + return true; + } + if (r._min < _min) { // left overlap only? + if (r.decode(_min) == _cid) { + _min = r._min; + _cid = r._cid; + return true; + } + return false; + } + if (r._max > _max) { // right overlap only? + if (decode(r._min) == r._cid) { + _max = r._max; + return true; + } + return false; + } + // r completely inside *this + return decode(r._min) == r._cid; +} + + +/** Adapts the left and right neighbor elements of a newly inserted range. + * The new range could overlap ranges in the neighborhood so that those must be + * adapted or removed. All ranges in the range vector are ordered ascendingly, i.e. + * [min_1, max_1],...,[min_n, max_n] where min_i < min_j for all i < j. + * @param[in,out] ranges range collection to be adapted + * @param[in] it pointer to the newly inserted range */ +void SegmentedCMap::adaptNeighbors (Ranges &ranges, Ranges::iterator it) { + if (it != ranges.end()) { + // adapt left neighbor + SegmentedCMap::Ranges::iterator lit = it-1; // points to left neighbor + if (it != ranges.begin() && it->min() <= lit->max()) { + bool left_neighbor_valid = (it->min() > 0 && it->min()-1 >= lit->min()); + if (left_neighbor_valid) // is adapted left neighbor valid? + lit->_max = it->min()-1; // => assign new max value + if (!left_neighbor_valid || it->join(*lit)) + it = ranges.erase(lit); + } + // remove right neighbors completely overlapped by *it + SegmentedCMap::Ranges::iterator rit = it+1; // points to right neighbor + while (rit != ranges.end() && it->max() >= rit->max()) { // complete overlap? + ranges.erase(rit); + rit = it+1; + } + // adapt rightmost range partially overlapped by *it + if (rit != ranges.end()) { + if (it->max() >= rit->min()) + rit->setMinAndAdaptCID(it->max()+1); + // try to merge right neighbor into *this + if (it->join(*rit)) + ranges.erase(rit); // remove merged neighbor + } + } +} + + +/** Adds a new code range. The range describes a mapping from character codes c to CIDs, where + * c \in [cmin,cmax] and CID(c):=cid+c-cmin. + * @param[in,out] ranges collection the new range is added to + * @param[in] cmin smallest character code in the range + * @param[in] cmax largest character code in the range + * @param[in] cid CID of the smallest character code (cmin) */ +void SegmentedCMap::addRange (Ranges &ranges, UInt32 cmin, UInt32 cmax, UInt32 cid) { + if (cmin > cmax) + swap(cmin, cmax); + + Range range(cmin, cmax, cid); + if (ranges.empty()) + ranges.push_back(range); + else { + // check for simple cases that can be handled pretty fast + Range &lrange = *ranges.begin(); + Range &rrange = *ranges.rbegin(); + if (cmin > rrange.max()) { // non-overlapping range at end of vector? + if (!rrange.join(range)) + ranges.push_back(range); + } + else if (cmax < lrange.min()) { // non-overlapping range at begin of vector? + if (!lrange.join(range)) + ranges.insert(ranges.begin(), range); + } + else { + // ranges overlap and/or must be inserted somewhere inside the vector + Ranges::iterator it = lower_bound(ranges.begin(), ranges.end(), range); + const bool at_end = (it == ranges.end()); + if (at_end) + --it; + if (!it->join(range)) { + if (it->min() < cmin && it->max() > cmax) { // new range completely inside an existing range? + //split existing range + UInt32 itmax = it->max(); + it->_max = cmin-1; + it = ranges.insert(it+1, Range(cmax+1, itmax, it->decode(cmax+1))); + } + else if (at_end) // does new range overlap right side of last range in vector? + it = ranges.end(); // => append new range at end of vector + it = ranges.insert(it, range); + } + adaptNeighbors(ranges, it); // resolve overlaps + } + } +} + + +/** Returns the CID for a given character code. */ +UInt32 SegmentedCMap::cid (UInt32 c) const { + int pos = lookup(_cidranges, c); + if (pos >= 0) + return _cidranges[pos].decode(c); + if (_basemap) + return _basemap->cid(c); + return 0; +} + + +/** Returns the character code of a base font for a given CID. */ +UInt32 SegmentedCMap::bfcode (UInt32 cid) const { + int pos = lookup(_bfranges, cid); + if (pos >= 0) + return _bfranges[pos].decode(cid); + if (_basemap) + return _basemap->bfcode(cid); + return 0; +} + + +/** Finds the index of the range that contains a given value c. + * @param[in] c find range that contains this value + * @return index of the range found, or -1 if range was not found */ +int SegmentedCMap::lookup (const Ranges &ranges, UInt32 c) const { + // simple binary search + int left=0, right=ranges.size()-1; + while (left <= right) { + int mid = (left+right)/2; + if (c < ranges[mid].min()) + right = mid-1; + else if (c > ranges[mid].max()) + left = mid+1; + else + return mid; + } + return -1; +} + + +void SegmentedCMap::write (ostream &os) const { + for (size_t i=0; i < _cidranges.size(); i++) { + const Range &r = _cidranges[i]; + os << '[' << r.min() << ',' << r.max() << "] => " << r.cid() << '\n'; + } +} |