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

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

Couple modifications to the UCD compiler. Splitting Multiplexing from BDD Minimization.

File size: 20.6 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_codepoint and hi_codepoint
355 ** ------------------------------------------------------------------------------------------------------------- */
356bool UnicodeSet::intersects(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) const {
357    quad_iterator qi = quad_begin() + lo_codepoint / QUAD_BITS;
358    unsigned n = (hi_codepoint - lo_codepoint) / QUAD_BITS;
359    while (n) {
360        if (qi.type() != Empty) {
361            return true;
362        }
363        const auto l = std::min<unsigned>(qi.length(), n);
364        qi += l;
365        n -= l;
366    }
367    // check the remaining portion of this quad
368    unsigned r = (hi_codepoint - lo_codepoint) % QUAD_BITS;
369    if (r == 0 || (++qi).type() == Empty) {
370        return false;
371    }
372    if (qi.type() == Full) {
373        return true;
374    }
375    return (qi.quad() & (FULL_QUAD_MASK << r)) != 0;
376}
377
378/** ------------------------------------------------------------------------------------------------------------- *
379 * @brief UnicodeSet::quad_iterator::advance
380 ** ------------------------------------------------------------------------------------------------------------- */
381void UnicodeSet::quad_iterator::advance(unsigned n) {
382    while (n > 0) {
383        const unsigned remain = lengthOf(*mRunIterator) - mOffset;
384        if (remain > n) {
385            if (typeOf(*mRunIterator) == Mixed) {
386                mQuadIterator += n;
387            }
388            mOffset += n;
389            break;
390        }
391        if (typeOf(*mRunIterator) == Mixed) {
392            mQuadIterator += remain;
393        }
394        ++mRunIterator;
395        mOffset = 0;
396        n -= remain;
397    }
398}
399
400/** ------------------------------------------------------------------------------------------------------------- *
401 * @brief UnicodeSet::iterator::advance
402 ** ------------------------------------------------------------------------------------------------------------- */
403void UnicodeSet::iterator::advance(const unsigned n) {
404
405    assert (n == 1);   
406
407    if (LLVM_UNLIKELY(mMinCodePoint >= 0x110000)) {
408        throw std::runtime_error("UnicodeSet iterator exceeded maximum code point.");
409    }
410
411    bool found = false;
412    // Find the start of our interval
413    while ( mBaseCodePoint < 0x110000 ) {
414        // Find the first non-empty block
415        if (typeOf(*mRunIterator) != Mixed) {           
416            // If we found a full run, this must be the start of our interval.
417            const auto baseCodePoint = mBaseCodePoint;
418            const auto type = typeOf(*mRunIterator);
419            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
420            if (type == Full) {
421                mMinCodePoint = baseCodePoint;
422                found = true;
423                break;
424            }
425        }
426        else { // if (typeOf(t) == Mixed)
427            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
428                const bitquad_t m = (*mQuadIterator) & (FULL_QUAD_MASK << mQuadOffset);
429                // If we found a marker in m, it marks the beginning of our current interval.
430                // Find it and break out of the loop.
431                if (m) {
432                    mQuadOffset = scan_forward_zeroes(m);
433                    mMinCodePoint = mBaseCodePoint + mQuadOffset;
434                    found = true;
435                    break;
436                }
437                mBaseCodePoint += QUAD_BITS;
438                ++mQuadIterator;
439                ++mMixedRunIndex;
440                mQuadOffset = 0;
441            }
442            if (found) break;
443            ++mRunIterator;
444            mQuadOffset = 0;
445            mMixedRunIndex = 0;
446        }
447    }
448
449    if (!found) {
450        assert (mBaseCodePoint == 0x110000);
451        mMinCodePoint = 0x110000;
452        return;
453    }
454
455    // at this stage, the max code point is the previous max code point (initially 0)
456    assert (mMaxCodePoint <= mMinCodePoint);
457    found = false;
458    // Find the end of our interval
459    while ( mBaseCodePoint < 0x110000 ) {
460
461        // Find the first non-Full block
462        if (typeOf(*mRunIterator) != Mixed) {
463            // If this run is Empty, the max code point is the last computed base code point - 1.
464            const auto baseCodePoint = mBaseCodePoint;
465            const auto type = typeOf(*mRunIterator);
466            mBaseCodePoint += lengthOf(*mRunIterator++) * QUAD_BITS;
467            if (type == Empty) {
468                mMaxCodePoint = baseCodePoint - 1;
469                found = true;
470                break;
471            }
472        }
473        else { // if (typeOf(t) == Mixed)
474            while (mMixedRunIndex != lengthOf(*mRunIterator)) {
475                const bitquad_t m = ((~(*mQuadIterator)) & FULL_QUAD_MASK) & (FULL_QUAD_MASK << mQuadOffset);
476
477                // If we found a marker in m, it marks the end of our current interval.
478                // Find it and break out of the loop.
479                if (m) {
480                    mQuadOffset = scan_forward_zeroes(m);
481                    mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
482                    found = true;
483                    break;
484                }
485                mBaseCodePoint += QUAD_BITS;
486                ++mQuadIterator;
487                ++mMixedRunIndex;
488                mQuadOffset = 0;
489            }
490            if (found) break;
491            ++mRunIterator;
492            mQuadOffset = 0;
493            mMixedRunIndex = 0;
494        }
495    }
496    // if the very last block is a mixed block and we go past it, the last code point of the range is 0x10FFFF
497    if (!found) {
498        assert (mBaseCodePoint == 0x110000);
499        mMaxCodePoint = 0x10FFFF;
500    }
501
502    assert (mMinCodePoint <= mMaxCodePoint);
503}
504
505/** ------------------------------------------------------------------------------------------------------------- *
506 * @brief Empty Set Constructor
507 ** ------------------------------------------------------------------------------------------------------------- */
508UnicodeSet::UnicodeSet() : mRuns({{{Empty, UNICODE_QUAD_COUNT}}}) { }
509
510/** ------------------------------------------------------------------------------------------------------------- *
511 * @brief Singleton Set Constructor
512 ** ------------------------------------------------------------------------------------------------------------- */
513UnicodeSet::UnicodeSet(const codepoint_t codepoint) {
514    const codepoint_t quad_no = codepoint / QUAD_BITS;
515    if (quad_no > 0) {
516        append_run(Empty, quad_no, mRuns);
517    }
518    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
519    if (quad_no < UNICODE_QUAD_COUNT - 1) {
520        append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
521    }
522    assert (runLengthSumsUpToUnicodeQuadCount(mRuns));
523}
524
525/** ------------------------------------------------------------------------------------------------------------- *
526 * @brief Range Set Constructor
527 ** ------------------------------------------------------------------------------------------------------------- */
528UnicodeSet::UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) {
529    const codepoint_t lo_quad_no = lo_codepoint / QUAD_BITS;
530    const codepoint_t hi_quad_no = hi_codepoint / QUAD_BITS;
531    const codepoint_t lo_offset = lo_codepoint & MOD_QUAD_BIT_MASK;
532    const codepoint_t hi_offset = hi_codepoint & MOD_QUAD_BIT_MASK;
533    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
534    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
535    append_run(Empty, lo_quad_no, mRuns);
536    if (lo_quad_no == hi_quad_no) {       
537        append_quad(lo_quad & hi_quad, mQuads, mRuns);
538    }
539    else {
540        append_quad(lo_quad, mQuads, mRuns);
541        append_run(Full, hi_quad_no - (lo_quad_no + 1), mRuns);
542        append_quad(hi_quad, mQuads, mRuns);
543    }
544    if (hi_quad_no < UNICODE_QUAD_COUNT - 1) {
545        append_run(Empty, UNICODE_QUAD_COUNT - (hi_quad_no + 1), mRuns);
546    }
547    assert (runLengthSumsUpToUnicodeQuadCount(mRuns));
548}
549
550}
Note: See TracBrowser for help on using the repository browser.