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

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

More modifications to UnicodeSet? class.

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