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
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 run1 = i1.run();
152        const auto run2 = i2.run();
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);
156            i1 += n;
157            i2 += n;
158        }
159        else if (typeOf(run1) == Full) {
160            for (unsigned i = 0; i != n; ++i, ++i2) {
161                append_quad(i2.quad(), quads, runs);
162            }
163            i1 += n;
164        }
165        else if (typeOf(run2) == Full) {
166            for (unsigned i = 0; i != n; ++i, ++i1) {
167                append_quad(i1.quad(), quads, runs);
168            }
169            i2 += n;
170        }
171        else {
172            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
173                append_quad(i1.quad() & i2.quad(), quads, runs);
174            }
175        }
176    }
177    assert (runLengthSumsUpToUnicodeQuadCount(runs));
178    return UnicodeSet(std::move(runs), std::move(quads));
179}
180
181/** ------------------------------------------------------------------------------------------------------------- *
182 * @brief union
183 ** ------------------------------------------------------------------------------------------------------------- */
184UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
185    RunVector runs;
186    QuadVector quads;
187    const auto e1 = quad_end();
188    const auto e2 = other.quad_end();
189    auto i1 = quad_begin(), i2 = other.quad_begin();
190    for (; i1 != e1 && i2 != e2; ) {
191        const auto run1 = i1.run();
192        const auto run2 = i2.run();
193        const auto n = std::min(lengthOf(run1), lengthOf(run2));
194        if ((typeOf(run1) == Empty) && (typeOf(run2) == Empty)) {
195            append_run(Empty, n, runs);
196            i1 += n;
197            i2 += n;
198        }
199        else if ((typeOf(run1) == Full) || (typeOf(run2) == Full)) {
200            append_run(Full, n, runs);
201            i1 += n;
202            i2 += n;
203        }
204        else if (typeOf(run1) == Empty) {
205            for (unsigned i = 0; i != n; ++i, ++i2) {
206                append_quad(i2.quad(), quads, runs);
207            }
208            i1 += n;
209        }
210        else if (typeOf(run2) == Empty) {
211            for (unsigned i = 0; i != n; ++i, ++i1) {
212                append_quad(i1.quad(), quads, runs);
213            }
214            i2 += n;
215        }
216        else {
217            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
218                append_quad(i1.quad() | i2.quad(), quads, runs);
219            }
220        }
221    }
222    assert (runLengthSumsUpToUnicodeQuadCount(runs));
223    return UnicodeSet(std::move(runs), std::move(quads));
224}
225
226/** ------------------------------------------------------------------------------------------------------------- *
227 * @brief difference
228 ** ------------------------------------------------------------------------------------------------------------- */
229UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
230    RunVector runs;
231    QuadVector quads;
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; ) {
235        const auto run1 = i1.run();
236        const auto run2 = i2.run();
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);
240            i1 += n;
241            i2 += n;
242        }
243        else if (typeOf(run1) == Full) {
244            for (unsigned i = 0; i != n; ++i, ++i2) {
245                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
246            }
247            i1 += n;
248        }
249        else if (typeOf(run2) == Empty) {
250            for (unsigned i = 0; i != n; ++i, ++i1) {
251                append_quad(i1.quad(), quads, runs);
252            }
253            i2 += n;
254        }
255        else {
256            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
257                append_quad(i1.quad() &~ i2.quad(), quads, runs);
258            }
259        }
260    }
261    assert (runLengthSumsUpToUnicodeQuadCount(runs));
262    return UnicodeSet(std::move(runs), std::move(quads));
263}
264
265/** ------------------------------------------------------------------------------------------------------------- *
266 * @brief symmetric difference
267 ** ------------------------------------------------------------------------------------------------------------- */
268UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
269    RunVector runs;
270    QuadVector quads;
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; ) {
274        const auto run1 = i1.run();
275        const auto run2 = i2.run();
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);
279            i1 += n;
280            i2 += n;
281        }
282        else if (typeOf(run1) == Empty) {
283            for (unsigned i = 0; i < n; ++i, ++i2) {
284                append_quad(i2.quad(), quads, runs);
285            }
286            i1 += n;
287        }
288        else if (typeOf(run2) == Empty) {
289            for (unsigned i = 0; i < n; ++i, ++i1) {
290                append_quad(i1.quad(), quads, runs);
291            }
292            i2 += n;
293        }
294        else if (typeOf(run1) == Full) {
295            for (unsigned i = 0; i < n; ++i, ++i2) {
296                append_quad(FULL_QUAD_MASK ^ i2.quad(), quads, runs);
297            }
298            i1 += n;
299        }
300        else if (typeOf(run2) == Empty) {
301            for (unsigned i = 0; i < n; ++i, ++i1) {
302                append_quad(FULL_QUAD_MASK ^ i1.quad(), quads, runs);
303            }
304            i2 += n;
305        }
306        else {
307            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
308                append_quad(i1.quad() ^ i2.quad(), quads, runs);
309            }
310        }
311    }
312    assert (runLengthSumsUpToUnicodeQuadCount(runs));
313    return UnicodeSet(std::move(runs), std::move(quads));
314}
315
316/** ------------------------------------------------------------------------------------------------------------- *
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/** ------------------------------------------------------------------------------------------------------------- *
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;
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;
346            }
347            return (typeOf(r) == Full);
348        }
349        if (typeOf(r) == Mixed) {
350            qi += n;
351        }       
352        n -= lengthOf(r);
353    }
354    return false;
355}
356
357/** ------------------------------------------------------------------------------------------------------------- *
358 * @brief UnicodeSet::quad_iterator::advance
359 ** ------------------------------------------------------------------------------------------------------------- */
360void UnicodeSet::quad_iterator::advance(unsigned n) {
361    while (n > 0) {
362        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
363        if (remain > n) {
364            if (typeOf(*mRunIterator) == Mixed) {
365                mQuadIterator += n;
366            }
367            mOffset += n;
368            break;
369        }
370        if (typeOf(*mRunIterator) == Mixed) {
371            mQuadIterator += remain;
372        }
373        ++mRunIterator;
374        mOffset = 0;
375        n -= remain;
376    }
377}
378
379/** ------------------------------------------------------------------------------------------------------------- *
380 * @brief UnicodeSet::iterator::advance
381 ** ------------------------------------------------------------------------------------------------------------- */
382void UnicodeSet::iterator::advance(const unsigned n) {
383
384    assert (n == 1);   
385
386    if (LLVM_UNLIKELY(mMinCodePoint >= 0x110000)) {
387        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
388    }
389
390    bool found = false;
391    // Find the start of our interval
392    while ( mBaseCodePoint < 0x110000 ) {
393        // Find the first non-empty block
394        if (typeOf(*mRunIterator) != Mixed) {           
395            // If we found a full run, this must be the start of our interval.
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;
402                break;
403            }
404        }
405        else { // if (typeOf(t) == Mixed)
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;
415                }
416                mBaseCodePoint += QUAD_BITS;
417                ++mQuadIterator;
418                ++mMixedRunIndex;
419                mQuadOffset = 0;
420            }
421            if (found) break;
422            ++mRunIterator;
423            mQuadOffset = 0;
424            mMixedRunIndex = 0;
425        }
426    }
427
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;
437    // Find the end of our interval
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            }
451        }
452        else { // if (typeOf(t) == Mixed)
453            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
454                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
455
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;
463                }
464                mBaseCodePoint += QUAD_BITS;
465                ++mQuadIterator;
466                ++mMixedRunIndex;
467                mQuadOffset = 0;
468            }
469            if (found) break;
470            ++mRunIterator;
471            mQuadOffset = 0;
472            mMixedRunIndex = 0;
473        }
474    }
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    }
480
481    assert (mMinCodePoint <= mMaxCodePoint);
482}
483
484/** ------------------------------------------------------------------------------------------------------------- *
485 * @brief Empty Set Constructor
486 ** ------------------------------------------------------------------------------------------------------------- */
487UnicodeSet::UnicodeSet() : mRuns({{{Empty, UNICODE_QUAD_COUNT}}}) { }
488
489/** ------------------------------------------------------------------------------------------------------------- *
490 * @brief Singleton Set Constructor
491 ** ------------------------------------------------------------------------------------------------------------- */
492UnicodeSet::UnicodeSet(const codepoint_t codepoint) {
493    const codepoint_t quad_no = codepoint / QUAD_BITS;
494    if (quad_no > 0) {
495        append_run(Empty, quad_no, mRuns);
496    }
497    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
498    if (quad_no < UNICODE_QUAD_COUNT - 1) {
499        append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
500    }
501    assert (runLengthSumsUpToUnicodeQuadCount(mRuns));
502}
503
504/** ------------------------------------------------------------------------------------------------------------- *
505 * @brief Range Set Constructor
506 ** ------------------------------------------------------------------------------------------------------------- */
507UnicodeSet::UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) {
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);
517    }
518    else {
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);
522    }
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));
527}
528
529}
Note: See TracBrowser for help on using the repository browser.