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

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

More modifications to the UnicodeSet? class. Default iterator computes code point range intervals as expected by the UCD compiler.

File size: 17.5 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#include <iomanip>
28
29const size_t QUAD_BITS = (8 * sizeof(bitquad_t));
30const size_t MOD_QUAD_BIT_MASK = QUAD_BITS - 1;
31const size_t UNICODE_QUAD_COUNT = 0x110000 / QUAD_BITS;
32const bitquad_t FULL_QUAD_MASK = -1;
33
34std::string run_type_name(const run_type_t type) {
35    if (type == Empty) {
36        return "Empty";
37    }
38    if (type == Full) {
39        return "Full";
40    }
41    if (type == Mixed) {
42        return "Mixed";
43    }
44    return "???";
45}
46
47using RunVector = UnicodeSet::RunVector;
48using QuadVector = UnicodeSet::QuadVector;
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() && runs.back().mType == type) {
58        runs.back().mRunLength += 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 dump
84 ** ------------------------------------------------------------------------------------------------------------- */
85void UnicodeSet::dump(llvm::raw_ostream & out) const {
86    auto qi = mQuads.cbegin();
87    for (const RunStructure & run : mRuns) {
88        if (run.mType == Empty) {
89            out << "Empty(" << run.mRunLength << ")\n";
90        }
91        else if (run.mType == Full) {
92            out << "Full(" << run.mRunLength << ")\n";
93        }
94        else {
95            for (const auto qi_end = qi + run.mRunLength; qi != qi_end; ++qi) {
96                assert (qi != mQuads.cend());
97                out << "Mixed(" << llvm::format("%08x", *qi) << ")\n";
98            }
99        }
100    }
101    out.flush();
102}
103
104/** ------------------------------------------------------------------------------------------------------------- *
105 * @brief complement
106 ** ------------------------------------------------------------------------------------------------------------- */
107UnicodeSet UnicodeSet::complement() const {
108    RunVector runs;
109    QuadVector quads;
110    runs.reserve(mRuns.size());
111    quads.reserve(mQuads.size());
112    auto qi = quads.cbegin();
113    for (const RunStructure & run : mRuns) {
114        if (run.mType == Empty) {
115            append_run(Full, run.mRunLength, runs);
116        }
117        else if (run.mType == Full) {
118            append_run(Empty, run.mRunLength, runs);
119        }
120        else {
121            for (const auto qi_end = qi + run.mRunLength; qi != qi_end; ++qi) {
122                assert (qi != quads.cend());
123                append_quad(FULL_QUAD_MASK ^ *qi, quads, runs);
124            }
125        }
126    }
127    return UnicodeSet(std::move(runs), std::move(quads));
128}
129
130/** ------------------------------------------------------------------------------------------------------------- *
131 * @brief intersection
132 ** ------------------------------------------------------------------------------------------------------------- */
133UnicodeSet UnicodeSet::operator&(const UnicodeSet & other) const {
134    RunVector runs;
135    QuadVector quads;
136    const auto e1 = quad_end();
137    const auto e2 = other.quad_end();
138    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
139        const auto run1 = i1.getRun();
140        const auto run2 = i2.getRun();
141        const auto n = std::min(run1.mRunLength, run2.mRunLength);
142        if (run1.mType == run2.mType && run1.mType != Mixed) {
143            append_run(run1.mType, n, runs);
144            i1 += n;
145            i2 += n;
146        }
147        else if (run1.mType == Full) {
148            for (unsigned i = 0; i != n; ++i, ++i2) {
149                append_quad(i2.getQuad(), quads, runs);
150            }
151            i1 += n;
152        }
153        else if (run2.mType == Full) {
154            for (unsigned i = 0; i != n; ++i, ++i1) {
155                append_quad(i1.getQuad(), quads, runs);
156            }
157            i2 += n;
158        }
159        else {
160            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
161                append_quad(i1.getQuad() & i2.getQuad(), quads, runs);
162            }
163        }
164    }
165    return UnicodeSet(std::move(runs), std::move(quads));
166}
167
168/** ------------------------------------------------------------------------------------------------------------- *
169 * @brief union
170 ** ------------------------------------------------------------------------------------------------------------- */
171UnicodeSet UnicodeSet::operator+(const UnicodeSet & other) const {
172    RunVector runs;
173    QuadVector quads;
174    const auto e1 = quad_end();
175    const auto e2 = other.quad_end();
176    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
177        const auto run1 = i1.getRun();
178        const auto run2 = i2.getRun();
179
180        const auto n = std::min(run1.mRunLength, run2.mRunLength);
181        if ((run1.mType == Empty) && (run2.mType == Empty)) {
182            append_run(Empty, n, runs);
183            i1 += n;
184            i2 += n;
185        }
186        else if ((run1.mType == Full) || (run2.mType == Full)) {
187            append_run(Full, n, runs);
188            i1 += n;
189            i2 += n;
190        }
191        else if (run1.mType == Empty) {
192            for (unsigned i = 0; i != n; ++i, ++i2) {
193                append_quad(i2.getQuad(), quads, runs);
194            }
195            i1 += n;
196        }
197        else if (run2.mType == Empty) {
198            for (unsigned i = 0; i != n; ++i, ++i1) {
199                append_quad(i1.getQuad(), quads, runs);
200            }
201            i2 += n;
202        }
203        else {
204            for (unsigned i = 0; i < n; ++i, ++i1, ++i2) {
205                append_quad(i1.getQuad() | i2.getQuad(), quads, runs);
206            }
207        }
208    }
209    return UnicodeSet(std::move(runs), std::move(quads));
210}
211
212/** ------------------------------------------------------------------------------------------------------------- *
213 * @brief difference
214 ** ------------------------------------------------------------------------------------------------------------- */
215UnicodeSet UnicodeSet::operator-(const UnicodeSet & other) const {
216    RunVector runs;
217    QuadVector quads;
218    const auto e1 = quad_end();
219    const auto e2 = other.quad_end();
220    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
221        const auto run1 = i1.getRun();
222        const auto run2 = i2.getRun();
223        unsigned n = std::min(run1.mRunLength, run2.mRunLength);
224        if ((run1.mType == Empty) || (run2.mType == Full) || (run1.mType == Full && run2.mType == Empty)) {
225            append_run(run1.mType, n, runs);
226            i1 += n;
227            i2 += n;
228        }
229        else if (run1.mType == Full) {
230            for (unsigned i = 0; i != n; ++i, ++i2) {
231                append_quad(FULL_QUAD_MASK ^ i2.getQuad(), quads, runs);
232            }
233            i1 += n;
234        }
235        else if (run2.mType == Empty) {
236            for (unsigned i = 0; i != n; ++i, ++i1) {
237                append_quad(i1.getQuad(), quads, runs);
238            }
239            i2 += n;
240        }
241        else {
242            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
243                append_quad(i1.getQuad() &~ i2.getQuad(), quads, runs);
244            }
245        }
246    }
247    return UnicodeSet(std::move(runs), std::move(quads));
248}
249
250/** ------------------------------------------------------------------------------------------------------------- *
251 * @brief symmetric difference
252 ** ------------------------------------------------------------------------------------------------------------- */
253UnicodeSet UnicodeSet::operator^(const UnicodeSet & other) const {
254    RunVector runs;
255    QuadVector quads;
256    const auto e1 = quad_end();
257    const auto e2 = other.quad_end();
258    for (auto i1 = quad_begin(), i2 = other.quad_begin(); i1 != e1 && i2 != e2; ) {
259        const auto run1 = i1.getRun();
260        const auto run2 = i2.getRun();
261        unsigned n = std::min(run1.mRunLength, run2.mRunLength);
262        if (run1.mType != Mixed && run2.mType != Mixed) {
263            append_run(run1.mType == run2.mType ? Empty : Full, n, runs);
264            i1 += n;
265            i2 += n;
266        }
267        else if (run1.mType == Empty) {
268            for (unsigned i = 0; i < n; ++i, ++i2) {
269                append_quad(i2.getQuad(), quads, runs);
270            }
271            i1 += n;
272        }
273        else if (run2.mType == Empty) {
274            for (unsigned i = 0; i < n; ++i, ++i1) {
275                append_quad(i1.getQuad(), quads, runs);
276            }
277            i2 += n;
278        }
279        else if (run1.mType == Full) {
280            for (unsigned i = 0; i < n; ++i, ++i2) {
281                append_quad(FULL_QUAD_MASK ^ i2.getQuad(), quads, runs);
282            }
283            i1 += n;
284        }
285        else if (run2.mType == Empty) {
286            for (unsigned i = 0; i < n; ++i, ++i1) {
287                append_quad(FULL_QUAD_MASK ^ i1.getQuad(), quads, runs);
288            }
289            i2 += n;
290        }
291        else {
292            for (unsigned i = 0; i != n; ++i, ++i1, ++i2) {
293                append_quad(i1.getQuad() ^ i2.getQuad(), quads, runs);
294            }
295        }
296    }
297    return UnicodeSet(std::move(runs), std::move(quads));
298}
299
300/** ------------------------------------------------------------------------------------------------------------- *
301 * @brief contains
302 * @param codepoint
303 *
304 * Return whether this UnicodeSet contains the specified code point
305 ** ------------------------------------------------------------------------------------------------------------- */
306bool UnicodeSet::contains(const codepoint_t codepoint) const {
307
308    auto n = codepoint / QUAD_BITS;
309    unsigned runIndex = 0;
310    unsigned quadIndex = 0;
311
312    for (;;) {
313        const RunStructure & t = mRuns[runIndex];
314        if (t.mRunLength >= n) {
315            if (t.mType == Mixed) {
316                return (mQuads[quadIndex + n - 1] & (static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK))) != 0;
317            }
318            return (t.mType == Full);
319        }
320        if (t.mType == Mixed) {
321            quadIndex += n;
322        }
323        ++runIndex;
324        n -= t.mRunLength;
325    }
326
327}
328
329/** ------------------------------------------------------------------------------------------------------------- *
330 * @brief UnicodeSet::quad_iterator::advance
331 ** ------------------------------------------------------------------------------------------------------------- */
332void UnicodeSet::quad_iterator::advance(unsigned n) {
333    while (n > 0) {
334        const unsigned remain = mRunIterator->mRunLength - mOffset;
335        if (remain > n) {
336            if (mRunIterator->mType == Mixed) {
337                mQuadIterator += n;
338            }
339            mOffset += n;
340            break;
341        }
342        if (mRunIterator->mType == Mixed) {
343            mQuadIterator += remain;
344        }
345        ++mRunIterator;
346        mOffset = 0;
347        n -= remain;
348    }
349}
350
351/** ------------------------------------------------------------------------------------------------------------- *
352 * @brief UnicodeSet::iterator::advance
353 ** ------------------------------------------------------------------------------------------------------------- */
354void UnicodeSet::iterator::advance(const unsigned n) {
355
356    assert (n == 1);
357
358    // Find the start of our interval
359    for ( ; mBaseCodePoint <= re::CC::UNICODE_MAX; ++mRunIterator) {
360        // Find the first non-empty block
361        const RunStructure & run = *mRunIterator;
362        if (run.mType != Mixed) {
363            mMinCodePoint = mBaseCodePoint;
364            mBaseCodePoint += run.mRunLength * QUAD_BITS;
365            mQuadOffset = 0;
366            mQuadPosition = 0;
367            if (run.mType == Full) {
368                break;
369            }
370        }
371        else { // if (left.mType == Mixed)
372            while (mQuadPosition != run.mRunLength) {
373                const bitquad_t q = *mQuadIterator;
374                const bitquad_t M = (FULL_QUAD_MASK << mQuadOffset);
375                const bitquad_t m = q & M;
376                // Nothing left in this quad to add; skip to the next one.
377                if (m == 0) {
378                    mBaseCodePoint += QUAD_BITS;
379                    ++mQuadPosition;
380                    ++mQuadIterator;
381                    continue;
382                }
383                mQuadOffset = scan_forward_zeroes(m);
384                mMinCodePoint = mBaseCodePoint + mQuadOffset;
385                break;
386            }
387            // If we found nothing in the quad, restart the loop.
388            if (mQuadPosition != run.mRunLength) {
389                break;
390            }
391        }
392    }
393
394    // Find the end of our interval
395    for ( ; mBaseCodePoint <= re::CC::UNICODE_MAX; ++mRunIterator) {
396        const RunStructure & run = *mRunIterator;
397        // If the next run is empty, we already know the max code point.
398        if (run.mType == Empty) {
399            mMaxCodePoint = mBaseCodePoint;
400            break;
401        }
402        // If the next run is Full, increment the base code point.
403        else if (run.mType == Full) {
404            mBaseCodePoint += run.mRunLength * QUAD_BITS;
405            mMaxCodePoint = mBaseCodePoint;
406            mQuadOffset = 0;
407            mQuadPosition = 0;
408            continue;
409        }
410        else { // if (left.mType == Mixed)
411            while (mQuadPosition != run.mRunLength) {
412
413                const bitquad_t q = *mQuadIterator;
414                const bitquad_t M = (FULL_QUAD_MASK << mQuadOffset);
415                const bitquad_t m = ~q & M;
416
417                // Nothing left in this quad to add; skip to the next one.
418                if (m == 0) {
419                    mBaseCodePoint += QUAD_BITS;
420                    mMaxCodePoint = mBaseCodePoint;
421                    ++mQuadPosition;
422                    ++mQuadIterator;
423                    continue;
424                }
425
426                mQuadOffset = scan_forward_zeroes(m);
427                mMaxCodePoint = mBaseCodePoint + mQuadOffset - 1;
428                break;
429            }
430            // If we found nothing in the quad, restart the loop.
431            if (mQuadPosition != run.mRunLength) {
432                break;
433            }
434        }
435    }
436
437
438}
439
440/** ------------------------------------------------------------------------------------------------------------- *
441 * @brief Empty Set Constructor
442 ** ------------------------------------------------------------------------------------------------------------- */
443UnicodeSet::UnicodeSet() : mRuns({{{Empty, UNICODE_QUAD_COUNT}}}) { }
444
445/** ------------------------------------------------------------------------------------------------------------- *
446 * @brief Singleton Set Constructor
447 ** ------------------------------------------------------------------------------------------------------------- */
448UnicodeSet::UnicodeSet(const codepoint_t codepoint) {
449    const codepoint_t quad_no = codepoint / QUAD_BITS;
450    append_run(Empty, quad_no, mRuns);
451    append_quad(static_cast<bitquad_t>(1) << (codepoint & MOD_QUAD_BIT_MASK), mQuads, mRuns);
452    append_run(Empty, UNICODE_QUAD_COUNT - (quad_no + 1), mRuns);
453}
454
455/** ------------------------------------------------------------------------------------------------------------- *
456 * @brief Range Set Constructor
457 ** ------------------------------------------------------------------------------------------------------------- */
458UnicodeSet::UnicodeSet(const codepoint_t lo_codepoint, const codepoint_t hi_codepoint) {
459    const codepoint_t lo_quad_no = lo_codepoint / QUAD_BITS;
460    const codepoint_t hi_quad_no = hi_codepoint / QUAD_BITS;
461    const codepoint_t lo_offset = lo_codepoint & MOD_QUAD_BIT_MASK;
462    const codepoint_t hi_offset = hi_codepoint & MOD_QUAD_BIT_MASK;
463    const bitquad_t lo_quad = (FULL_QUAD_MASK << lo_offset);
464    const bitquad_t hi_quad = (FULL_QUAD_MASK >> (QUAD_BITS - 1 - hi_offset));
465    append_run(Empty, lo_quad_no, mRuns);
466    if (lo_quad_no == hi_quad_no) {       
467        append_quad(lo_quad & hi_quad, mQuads, mRuns);
468    }
469    else {
470        append_quad(lo_quad, mQuads, mRuns);
471        append_run(Full, hi_quad_no - (lo_quad_no + 1), mRuns);
472        append_quad(hi_quad, mQuads, mRuns);
473    }
474    append_run(Empty, UNICODE_QUAD_COUNT - (hi_quad_no + 1), mRuns);
475}
476
Note: See TracBrowser for help on using the repository browser.