source: icGREP/icgrep-devel/icgrep/UCD/unicode_set.cpp @ 4797

Last change on this file since 4797 was 4631, checked in by nmedfort, 4 years ago

Fix for SCX and updated property objects.

File size: 20.2 KB
Line 
1//
2// unicode_set.cpp - representing and manipulating sets of Unicode
3// characters, based on data from UCD - the Unicode Character Database
4//
5// Robert D. Cameron
6// September 18, 2014
7//
8// Licensed under Open Software License 3.0.
9//
10// Unicode Sparse Bitset Representation
11//
12// The Unicode Sparse Bitset representation is based on
13// (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
14// (b) Specifying the quads using a run-length encoding, in which each run
15//     is Empty (quads contain no members), Mixed (quads contain some members and
16//     some nonmembers) or Full (all codepoints in each quad are members of the set).
17// (c) Explicitly listing all the quads of Mixed type.
18//
19
20#include "unicode_set.h"
21#include "assert.h"
22#include <string>
23#include <llvm/Support/raw_ostream.h>
24#include <llvm/Support/Format.h>
25#include <include/simd-lib/builtins.hpp>
26
27using namespace re;
28
29namespace UCD {
30
31using bitquad_t = UnicodeSet::bitquad_t;
32using run_t = UnicodeSet::run_t;
33using RunVector = UnicodeSet::RunVector;
34using QuadVector = UnicodeSet::QuadVector;
35
36const size_t QUAD_BITS = (8 * sizeof(bitquad_t));
37const size_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
38const size_t UNICODE_QUAD_COUNT = (CC::UNICODE_MAX + 1) / QUAD_BITS;
39const bitquad_t FULL_QUAD_MASK = -1;
40
41inline run_type_t typeOf(const run_t & run) {
42    return std::get<0>(run);
43}
44
45inline UnicodeSet::length_t lengthOf(const run_t & run) {
46    return std::get<1>(run);
47}
48
49/** ------------------------------------------------------------------------------------------------------------- *
50 * @brief append_run
51 ** ------------------------------------------------------------------------------------------------------------- */
52inline void append_run(const run_type_t type, const unsigned length, RunVector & runs) {
53    if (LLVM_UNLIKELY(length == 0)) {
54        return;
55    }
56    else if (!runs.empty() && typeOf(runs.back()) == type) {
57        std::get<1>(runs.back()) += length;
58        return;
59    }
60    runs.emplace_back(type, length);
61}
62
63/** ------------------------------------------------------------------------------------------------------------- *
64 * @brief append_quad
65 ** ------------------------------------------------------------------------------------------------------------- */
66inline void append_quad(const bitquad_t quad, QuadVector & quads, RunVector & runs) {
67    run_type_t type = Empty;
68    if (LLVM_UNLIKELY(quad == 0)) {
69        type = Empty;
70    }
71    else if (LLVM_UNLIKELY(quad == FULL_QUAD_MASK)) {
72        type = Full;
73    }
74    else {
75        quads.emplace_back(quad);
76        type = Mixed;
77    }
78    append_run(type, 1, runs);
79}
80
81/** ------------------------------------------------------------------------------------------------------------- *
82 * @brief runLengthSumsUpToUnicodeQuadCount
83 *
84 * Sanity check for each function that constructs a new UnicodeSet
85 ** ------------------------------------------------------------------------------------------------------------- */
86inline bool runLengthSumsUpToUnicodeQuadCount(const RunVector & runs) {
87    unsigned sum = 0;
88    for (auto & run : runs) {
89        sum += lengthOf(run);
90    }
91    return sum == UNICODE_QUAD_COUNT;
92}
93
94/** ------------------------------------------------------------------------------------------------------------- *
95 * @brief dump
96 ** ------------------------------------------------------------------------------------------------------------- */
97void UnicodeSet::dump(llvm::raw_ostream & out) const {
98    auto qi = mQuads.cbegin();
99    for (const run_t & run : mRuns) {
100        if (typeOf(run) == Empty) {
101            out << "Empty(" << lengthOf(run) << ")\n";
102        }
103        else if (typeOf(run) == Full) {
104            out << "Full(" << lengthOf(run) << ")\n";
105        }
106        else {
107            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
108                assert (qi != mQuads.cend());
109                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
110            }
111        }
112    }
113}
114
115/** ------------------------------------------------------------------------------------------------------------- *
116 * @brief complement
117 ** ------------------------------------------------------------------------------------------------------------- */
118UnicodeSet UnicodeSet::operator~() const {
119    RunVector runs;
120    QuadVector quads;
121    runs.reserve(mRuns.size());
122    quads.reserve(mQuads.size());
123    auto qi = quads.cbegin();
124    for (const run_t & run : mRuns) {
125        if (typeOf(run) == Empty) {
126            append_run(Full, lengthOf(run), runs);
127        }
128        else if (typeOf(run) == Full) {
129            append_run(Empty, lengthOf(run), runs);
130        }
131        else {
132            for (const auto qi_end = qi + lengthOf(run); qi != qi_end; ++qi) {
133                assert (qi != quads.cend());
134                append_quad(FULL_QUAD_MASK ^ *qi, quads, runs);
135            }
136        }
137    }
138    assert (runLengthSumsUpToUnicodeQuadCount(runs));
139    return UnicodeSet(std::move(runs), std::move(quads));
140}
141
142/** ------------------------------------------------------------------------------------------------------------- *
143 * @brief intersection
144 ** ------------------------------------------------------------------------------------------------------------- */
145UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
146    RunVector runs;
147    QuadVector quads;
148    const auto e1 = quad_end();
149    const auto e2 = other.quad_end();
150    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
151        const auto n = std::min(i1.length(), i2.length());
152        if (i1.type() == i2.type() && i1.type() != Mixed) {
153            append_run(i1.type(), n, runs);
154            i1 += n;
155            i2 += n;
156        }
157        else if (i1.type() == Full) {
158            for (unsigned i = 0; i != n; ++i, ++i2) {
159                append_quad(i2.quad(), quads, runs);
160            }
161            i1 += n;
162        }
163        else if (i2.type() == Full) {
164            for (unsigned i = 0; i != n; ++i, ++i1) {
165                append_quad(i1.quad(), quads, runs);
166            }
167            i2 += n;
168        }
169        else {
170            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
171                append_quad(i1.quad() & i2.quad(), quads, runs);
172            }
173        }
174    }
175    assert (runLengthSumsUpToUnicodeQuadCount(runs));
176    return UnicodeSet(std::move(runs), std::move(quads));
177}
178
179/** ------------------------------------------------------------------------------------------------------------- *
180 * @brief union
181 ** ------------------------------------------------------------------------------------------------------------- */
182UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
183    RunVector runs;
184    QuadVector quads;
185    const auto e1 = quad_end();
186    const auto e2 = other.quad_end();
187    auto i1 = quad_begin(), i2 = other.quad_begin();
188    for (; i1 != e1 && i2 != e2; ) {
189        const auto n = std::min(i1.length(), i2.length());
190        if ((i1.type() == Empty) && (i2.type() == Empty)) {
191            append_run(Empty, n, runs);
192            i1 += n;
193            i2 += n;
194        }
195        else if ((i1.type() == Full) || (i2.type() == Full)) {
196            append_run(Full, n, runs);
197            i1 += n;
198            i2 += n;
199        }
200        else if (i1.type() == Empty) {
201            for (unsigned i = 0; i != n; ++i, ++i2) {
202                append_quad(i2.quad(), quads, runs);
203            }
204            i1 += n;
205        }
206        else if (i2.type() == Empty) {
207            for (unsigned i = 0; i != n; ++i, ++i1) {
208                append_quad(i1.quad(), quads, runs);
209            }
210            i2 += n;
211        }
212        else {
213            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
214                append_quad(i1.quad() | i2.quad(), quads, runs);
215            }
216        }
217    }
218    assert (runLengthSumsUpToUnicodeQuadCount(runs));
219    return UnicodeSet(std::move(runs), std::move(quads));
220}
221
222/** ------------------------------------------------------------------------------------------------------------- *
223 * @brief difference
224 ** ------------------------------------------------------------------------------------------------------------- */
225UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
226    RunVector runs;
227    QuadVector quads;
228    const auto e1 = quad_end();
229    const auto e2 = other.quad_end();
230    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
231        unsigned n = std::min(i1.length(), i2.length());
232        if ((i1.type() == Empty) || (i2.type() == Full) || (i1.type() == Full && i2.type() == Empty)) {
233            append_run(i1.type(), n, runs);
234            i1 += n;
235            i2 += n;
236        }
237        else if (i1.type() == Full) {
238            for (unsigned i = 0; i != n; ++i, ++i2) {
239                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
240            }
241            i1 += n;
242        }
243        else if (i2.type() == Empty) {
244            for (unsigned i = 0; i != n; ++i, ++i1) {
245                append_quad(i1.quad(), quads, runs);
246            }
247            i2 += n;
248        }
249        else {
250            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
251                append_quad(i1.quad() &~ i2.quad(), quads, runs);
252            }
253        }
254    }
255    assert (runLengthSumsUpToUnicodeQuadCount(runs));
256    return UnicodeSet(std::move(runs), std::move(quads));
257}
258
259/** ------------------------------------------------------------------------------------------------------------- *
260 * @brief symmetric difference
261 ** ------------------------------------------------------------------------------------------------------------- */
262UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
263    RunVector runs;
264    QuadVector quads;
265    const auto e1 = quad_end();
266    const auto e2 = other.quad_end();
267    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
268        unsigned n = std::min(i1.length(), i2.length());
269        if (i1.type() != Mixed && i2.type() != Mixed) {
270            append_run(i1.type() == i2.type() ? Empty : Full, n, runs);
271            i1 += n;
272            i2 += n;
273        }
274        else if (i1.type() == Empty) {
275            for (unsigned i = 0; i < n; ++i, ++i2) {
276                append_quad(i2.quad(), quads, runs);
277            }
278            i1 += n;
279        }
280        else if (i2.type() == Empty) {
281            for (unsigned i = 0; i < n; ++i, ++i1) {
282                append_quad(i1.quad(), quads, runs);
283            }
284            i2 += n;
285        }
286        else if (i1.type() == Full) {
287            for (unsigned i = 0; i < n; ++i, ++i2) {
288                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
289            }
290            i1 += n;
291        }
292        else if (i2.type() == Empty) {
293            for (unsigned i = 0; i < n; ++i, ++i1) {
294                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
295            }
296            i2 += n;
297        }
298        else {
299            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
300                append_quad(i1.quad() ^ i2.quad(), quads, runs);
301            }
302        }
303    }
304    assert (runLengthSumsUpToUnicodeQuadCount(runs));
305    return UnicodeSet(std::move(runs), std::move(quads));
306}
307
308/** ------------------------------------------------------------------------------------------------------------- *
309 * @brief equality
310 ** ------------------------------------------------------------------------------------------------------------- */
311UnicodeSet UnicodeSet::operator==(const UnicodeSet & other) const {
312    if (mRuns.size() != other.mRuns.size() || mQuads.size() != other.mQuads.size()) {
313        return false;
314    }
315    for (auto i = mQuads.begin(), j = other.mQuads.begin(); i != mQuads.end(); ++i, ++j) {
316        if (*i != *j) return false;
317    }
318    for (auto i = mRuns.begin(), j = other.mRuns.begin(); i != mRuns.end(); ++i, ++j) {
319        if (*i != *j) return false;
320    }
321    return true;
322}
323
324/** ------------------------------------------------------------------------------------------------------------- *
325 * @brief contains
326 * @param codepoint
327 *
328 * Return whether this UnicodeSet contains the specified code point
329 ** ------------------------------------------------------------------------------------------------------------- */
330bool UnicodeSet::contains(const codepoint_t codepoint) const {
331    auto n = codepoint / QUAD_BITS;
332    auto qi = mQuads.cbegin();
333    for (const auto & r : mRuns) {
334        if (lengthOf(r) >= n) {
335            if (typeOf(r) == Mixed) {
336                qi += n - 1;
337                return (*qi & (static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK))) != 0;
338            }
339            return (typeOf(r) == Full);
340        }
341        if (typeOf(r) == Mixed) {
342            qi += lengthOf(r);
343        }       
344        n -= lengthOf(r);
345    }
346    return false;
347}
348
349/** ------------------------------------------------------------------------------------------------------------- *
350 * @brief intersects
351 * @param lo_codepoint
352 * @param hi_codepoint
353 *
354 * Return true if this UnicodeSet contains any code point(s) between lo and hi (inclusive)
355 ** ------------------------------------------------------------------------------------------------------------- */
356bool UnicodeSet::intersects(const codepoint_t lo, const codepoint_t hi) const {
357    for (auto range : *this) {
358        if (hi_codepoint(range) < lo) {
359            continue;
360        }
361        if (lo_codepoint(range) > hi) {
362            break;
363        }
364        return true;
365    }
366    return false;
367}
368
369/** ------------------------------------------------------------------------------------------------------------- *
370 * @brief UnicodeSet::quad_iterator::advance
371 ** ------------------------------------------------------------------------------------------------------------- */
372void UnicodeSet::quad_iterator::advance(unsigned n) {
373    while (n > 0) {
374        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
375        if (remain > n) {
376            if (typeOf(*mRunIterator) == Mixed) {
377                mQuadIterator += n;
378            }
379            mOffset += n;
380            break;
381        }
382        if (typeOf(*mRunIterator) == Mixed) {
383            mQuadIterator += remain;
384        }
385        ++mRunIterator;
386        mOffset = 0;
387        n -= remain;
388    }
389}
390
391/** ------------------------------------------------------------------------------------------------------------- *
392 * @brief UnicodeSet::iterator::advance
393 ** ------------------------------------------------------------------------------------------------------------- */
394void UnicodeSet::iterator::advance(const unsigned n) {
395
396    assert (n == 1);   
397
398    if (LLVM_UNLIKELY(mMinCodePoint >= 0x110000)) {
399        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
400    }
401
402    bool found = false;
403    // Find the start of our interval
404    while ( mBaseCodePoint < 0x110000 ) {
405        // Find the first non-empty block
406        if (typeOf(*mRunIterator) != Mixed) {           
407            // If we found a full run, this must be the start of our interval.
408            const auto baseCodePoint = mBaseCodePoint;
409            const auto type = typeOf(*mRunIterator);
410            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
411            if (type == Full) {
412                mMinCodePoint = baseCodePoint;
413                found = true;
414                break;
415            }
416        }
417        else { // if (typeOf(t) == Mixed)
418            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
419                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
420                // If we found a marker in m, it marks the beginning of our current interval.
421                // Find it and break out of the loop.
422                if (m) {
423                    mQuadOffset = scan_forward_zeroes(m);
424                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
425                    found = true;
426                    break;
427                }
428                mBaseCodePoint += QUAD_BITS;
429                ++mQuadIterator;
430                ++mMixedRunIndex;
431                mQuadOffset = 0;
432            }
433            if (found) break;
434            ++mRunIterator;
435            mQuadOffset = 0;
436            mMixedRunIndex = 0;
437        }
438    }
439
440    if (!found) {
441        assert (mBaseCodePoint == 0x110000);
442        mMinCodePoint = 0x110000;
443        return;
444    }
445
446    // at this stage, the max code point is the previous max code point (initially 0)
447    assert (mMaxCodePoint <= mMinCodePoint);
448    found = false;
449    // Find the end of our interval
450    while ( mBaseCodePoint < 0x110000 ) {
451
452        // Find the first non-Full block
453        if (typeOf(*mRunIterator) != Mixed) {
454            // If this run is Empty, the max code point is the last computed base code point - 1.
455            const auto baseCodePoint = mBaseCodePoint;
456            const auto type = typeOf(*mRunIterator);
457            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
458            if (type == Empty) {
459                mMaxCodePoint = baseCodePoint - 1;
460                found = true;
461                break;
462            }
463        }
464        else { // if (typeOf(t) == Mixed)
465            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
466                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
467
468                // If we found a marker in m, it marks the end of our current interval.
469                // Find it and break out of the loop.
470                if (m) {
471                    mQuadOffset = scan_forward_zeroes(m);
472                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
473                    found = true;
474                    break;
475                }
476                mBaseCodePoint += QUAD_BITS;
477                ++mQuadIterator;
478                ++mMixedRunIndex;
479                mQuadOffset = 0;
480            }
481            if (found) break;
482            ++mRunIterator;
483            mQuadOffset = 0;
484            mMixedRunIndex = 0;
485        }
486    }
487    // if the very last block is a mixed block and we go past it, the last code point of the range is 0x10FFFF
488    if (!found) {
489        assert (mBaseCodePoint == 0x110000);
490        mMaxCodePoint = 0x10FFFF;
491    }
492
493    assert (mMinCodePoint <= mMaxCodePoint);
494}
495
496/** ------------------------------------------------------------------------------------------------------------- *
497 * @brief Empty Set Constructor
498 ** ------------------------------------------------------------------------------------------------------------- */
499UnicodeSet::UnicodeSet() : mRuns({{{Empty, UNICODE_QUAD_COUNT}}}) { }
500
501/** ------------------------------------------------------------------------------------------------------------- *
502 * @brief Singleton Set Constructor
503 ** ------------------------------------------------------------------------------------------------------------- */
504UnicodeSet::UnicodeSet(const codepoint_t codepoint) {
505    const codepoint_t quad_no = codepoint / QUAD_BITS;
506    if (quad_no > 0) {
507        append_run(Empty, quad_no, mRuns);
508    }
509    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
510    if (quad_no < UNICODE_QUAD_COUNT - 1) {
511        append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
512    }
513    assert (runLengthSumsUpToUnicodeQuadCount(mRuns));
514}
515
516/** ------------------------------------------------------------------------------------------------------------- *
517 * @brief Range Set Constructor
518 ** ------------------------------------------------------------------------------------------------------------- */
519UnicodeSet::UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) {
520    const codepoint_t lo_quad_no = lo_codepoint / QUAD_BITS;
521    const codepoint_t hi_quad_no = hi_codepoint / QUAD_BITS;
522    const codepoint_t lo_offset = lo_codepoint & MOD_QUAD_BIT_MASK;
523    const codepoint_t hi_offset = hi_codepoint & MOD_QUAD_BIT_MASK;
524    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
525    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
526    append_run(Empty, lo_quad_no, mRuns);
527    if (lo_quad_no == hi_quad_no) {       
528        append_quad(lo_quad & hi_quad, mQuads, mRuns);
529    }
530    else {
531        append_quad(lo_quad, mQuads, mRuns);
532        append_run(Full, hi_quad_no - (lo_quad_no + 1), mRuns);
533        append_quad(hi_quad, mQuads, mRuns);
534    }
535    if (hi_quad_no < UNICODE_QUAD_COUNT - 1) {
536        append_run(Empty, UNICODE_QUAD_COUNT - (hi_quad_no + 1), mRuns);
537    }
538    assert (runLengthSumsUpToUnicodeQuadCount(mRuns));
539}
540
541}
Note: See TracBrowser for help on using the repository browser.