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

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

Bug fix for CC insert_range and UnicodeSet? iterator.

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