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

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

Temporary check-in for dynamic unicode class compilation.

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