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

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

Temporary check-in.

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