source: icGREP/icgrep-devel/UCD-scripts/unicode_set.py @ 5864

Last change on this file since 5864 was 5749, checked in by nmedfort, 19 months ago

updated UCD python scripts

File size: 13.4 KB
Line 
1#
2# unicode_set.py - representing and manipulating sets of Unicode
3# characters, based on data from UCD - the Unicode Character Database
4#
5# Robert D. Cameron
6# September 8, 2014
7#
8# Licensed under Open Software License 3.0.
9import cformat
10import re
11
12#
13# Unicode Sparse Bitset Representation
14#
15# The Unicode Sparse Bitset representation is based on
16# (a) Dividing the Unicode codepoint space into groups of 2^k codepoints called quads.
17# (b) Specifying the quads using a run-length encoding, in which each run
18#     is Empty (quads contain no members), Mixed (quads contain some members and
19#     some nonmembers) or Full (all codepoints in each quad are members of the set).
20# (c) Explicitly listing all the quads of Mixed type.
21#
22
23Empty = 0
24Full = -1
25Mixed = 1
26
27default_log2_quad_bits = 5
28
29log2_quad_bits = default_log2_quad_bits
30quad_bits = 1 << log2_quad_bits
31mod_quad_bit_mask = quad_bits - 1
32UnicodeQuadCount = int(0x110000 / quad_bits)  # 2**log2_quad_bits codepoints per quad
33FullQuadMask = (1 << (quad_bits)) - 1
34run_bytes = 4
35
36
37class UCset:
38    def __init__(self):
39        self.runs = []
40        self.quads = []
41
42    # internal methods
43    def append_run(self, runtype, runlength):
44        if runlength == 0: return
45        if self.runs == []:
46            self.runs = [(runtype, runlength)]
47        else:
48            (lastruntype, lastrunlength) = self.runs[-1]
49            if lastruntype == runtype:
50                self.runs[-1] = (runtype, lastrunlength + runlength)
51            else:
52                self.runs.append((runtype, runlength))
53
54    def append_quad(self, q):
55        if q == 0:
56            self.append_run(Empty, 1)
57        elif (q & FullQuadMask) == FullQuadMask:
58            self.append_run(Full, 1)
59        else:
60            self.append_run(Mixed, 1)
61            self.quads.append(q)
62
63    # printing
64    def generate(self, propertyName, indent=4):
65        hex_specifier = "%%#0%ix" % (int(quad_bits / 4) + 2)
66        runtype = {-1: "Full", 0: "Empty", 1: "Mixed"}
67
68        str = "\n" + (" " * indent) + "namespace {\n" + \
69              (" " * indent) + "const static UnicodeSet::run_t __%s_runs[] = {\n" % propertyName + \
70              (" " * indent) + cformat.multiline_fill(['{%s, %i}' % (runtype[r[0]], r[1]) for r in self.runs], ',',
71                                                      indent) + \
72              "};\n"
73
74        if len(self.quads) == 0:
75            str += (" " * indent) + "const static UnicodeSet::bitquad_t * const __%s_quads = nullptr;\n" % propertyName
76        else:
77            str += (" " * indent) + "const static UnicodeSet::bitquad_t  __%s_quads[] = {\n" % propertyName + \
78                   (" " * indent) + cformat.multiline_fill([hex_specifier % q for q in self.quads], ',', indent) + \
79                   "};\n"
80
81        # Despite being const_cast below, neither runs nor quads will be modified by the UnicodeSet. If any
82        # modifications are made, they first test the run/quad capacity and will observe that they 0 length
83        # and allocate heap memory to make any changes
84
85        str += (" " * indent) + "}\n\n" + \
86               (" " * indent) + \
87               "const static UnicodeSet %s{const_cast<UnicodeSet::run_t *>(__%s_runs), %i, 0, " \
88               "const_cast<UnicodeSet::bitquad_t *>(__%s_quads), %i, 0};\n\n" \
89               % (propertyName, propertyName, len(self.runs), propertyName, len(self.quads))
90
91        return str
92
93    def bytes(self):
94        return (len(self.runs) * run_bytes) + (len(self.quads) * int(quad_bits / 8))
95
96
97#
98# Set Operations
99#
100def empty_uset():
101    e = UCset()
102    e.runs = [(Empty, UnicodeQuadCount)]
103    e.quads = []
104    return e
105
106
107def singleton_uset(codepoint):
108    e = UCset()
109    quad_no = codepoint >> log2_quad_bits
110    quad_val = 1 << (codepoint & mod_quad_bit_mask)
111    if quad_no > 0: e.append_run(Empty, quad_no)
112    e.append_run(Mixed, 1)
113    e.quads = [quad_val]
114    if quad_no < UnicodeQuadCount - 1:
115        e.append_run(Empty, UnicodeQuadCount - (quad_no + 1))
116    return e
117
118
119def range_uset(lo_codepoint, hi_codepoint):
120    e = UCset()
121    lo_quad_no = lo_codepoint >> log2_quad_bits
122    hi_quad_no = hi_codepoint >> log2_quad_bits
123    lo_offset = lo_codepoint & mod_quad_bit_mask
124    hi_offset = hi_codepoint & mod_quad_bit_mask
125    if lo_quad_no > 0:  e.append_run(Empty, lo_quad_no)
126    if lo_quad_no == hi_quad_no:
127        quad = (FullQuadMask << lo_offset) & (FullQuadMask >> (quad_bits - 1 - hi_offset))
128        e.append_quad(quad)
129    else:
130        e.append_quad((FullQuadMask << lo_offset) & FullQuadMask)
131        e.append_run(Full, hi_quad_no - (lo_quad_no + 1))
132        e.append_quad((FullQuadMask >> (quad_bits - 1 - hi_offset)) & FullQuadMask)
133    if hi_quad_no < UnicodeQuadCount - 1:
134        e.append_run(Empty, UnicodeQuadCount - (hi_quad_no + 1))
135    return e
136
137
138class Uset_Iterator:
139    def __init__(self, uSet):
140        self.uSet = uSet
141        self.run_no = 0
142        self.offset = 0
143        self.quad_no = 0
144
145    def at_end(self):
146        return self.run_no == len(self.uSet.runs)
147
148    def current_run(self):
149        (this_run_type, this_run_length) = self.uSet.runs[self.run_no]
150        return (this_run_type, this_run_length - self.offset)
151
152    def get_quad(self):
153        (this_run_type, this_run_length) = self.uSet.runs[self.run_no]
154        if this_run_type == Empty:
155            return 0
156        elif this_run_type == Full:
157            return FullQuadMask
158        else:
159            return self.uSet.quads[self.quad_no]
160
161    def advance(self, n):
162        while n > 0:
163            (this_run_type, this_run_length) = self.uSet.runs[self.run_no]
164            remain = this_run_length - self.offset
165            if remain > n:
166                self.offset += n
167                if this_run_type == Mixed: self.quad_no += n
168                n = 0
169            elif remain == n:
170                self.run_no += 1
171                self.offset = 0
172                if this_run_type == Mixed: self.quad_no += n
173                n = 0
174            else:
175                self.run_no += 1
176                self.offset = 0
177                if this_run_type == Mixed: self.quad_no += remain
178                n -= remain
179
180
181def uset_member(s, codepoint):
182    quad_no = int(codepoint / quad_bits)
183    quad_val = 1 << (codepoint & mod_quad_bit_mask)
184    it = Uset_Iterator(s)
185    it.advance(quad_no)
186    return (it.get_quad() & quad_val) != 0
187
188
189def uset_popcount(s):
190    popcount = 0
191    it = Uset_Iterator(s)
192    while not it.at_end():
193        (runtype, n) = it.current_run()
194        if runtype == Empty:
195            it.advance(n)
196        elif runtype == Full:
197            popcount += n * quad_bits
198            it.advance(n)
199        else:
200            popcount += popcount_quad(it.get_quad())
201            it.advance(1)
202    return popcount
203
204
205def popcount_quad(q):
206    c = 0
207    while q != 0:
208        q = q & (q - 1)  # clear low bit
209        c += 1
210    return c
211
212
213def uset_complement(s):
214    iset = UCset()
215    it = Uset_Iterator(s)
216    while not it.at_end():
217        (runtype, n) = it.current_run()
218        if runtype == Empty:
219            iset.append_run(Full, n)
220            it.advance(n)
221        elif runtype == Full:
222            iset.append_run(Empty, n)
223            it.advance(n)
224        else:
225            for i in range(n):
226                iset.append_quad(FullQuadMask ^ it.get_quad())
227                it.advance(1)
228    return iset
229
230
231def uset_intersection(s1, s2):
232    iset = UCset()
233    i1 = Uset_Iterator(s1)
234    i2 = Uset_Iterator(s2)
235    while not i1.at_end():
236        (s1_type, s1_length) = i1.current_run()
237        (s2_type, s2_length) = i2.current_run()
238        n = min(s1_length, s2_length)
239        if s1_type == Empty or s2_type == Empty:
240            iset.append_run(Empty, n)
241            i1.advance(n)
242            i2.advance(n)
243        elif s1_type == Full and s2_type == Full:
244            iset.append_run(Full, n)
245            i1.advance(n)
246            i2.advance(n)
247        elif s1_type == Full:
248            for i in range(n):
249                iset.append_quad(i2.get_quad())
250                i2.advance(1)
251            i1.advance(n)
252        elif s2_type == Full:
253            for i in range(n):
254                iset.append_quad(i1.get_quad())
255                i1.advance(1)
256            i2.advance(n)
257        else:  # both s1 and s2 have mixed blocks; form block-by-block intersection
258            for i in range(n):
259                iset.append_quad(i1.get_quad() & i2.get_quad())
260                i1.advance(1)
261                i2.advance(1)
262    return iset
263
264
265def uset_union(s1, s2):
266    iset = UCset()
267    i1 = Uset_Iterator(s1)
268    i2 = Uset_Iterator(s2)
269    while not i1.at_end():
270        (s1_type, s1_length) = i1.current_run()
271        (s2_type, s2_length) = i2.current_run()
272        n = min(s1_length, s2_length)
273        if s1_type == Empty and s2_type == Empty:
274            iset.append_run(Empty, n)
275            i1.advance(n)
276            i2.advance(n)
277        elif s1_type == Full or s2_type == Full:
278            iset.append_run(Full, n)
279            i1.advance(n)
280            i2.advance(n)
281        elif s1_type == Empty:
282            for i in range(n):
283                iset.append_quad(i2.get_quad())
284                i2.advance(1)
285            i1.advance(n)
286        elif s2_type == Empty:
287            for i in range(n):
288                iset.append_quad(i1.get_quad())
289                i1.advance(1)
290            i2.advance(n)
291        else:  # both s1 and s2 have mixed blocks; form block-by-block union
292            for i in range(n):
293                iset.append_quad(i1.get_quad() | i2.get_quad())
294                i1.advance(1)
295                i2.advance(1)
296    return iset
297
298
299def uset_difference(s1, s2):
300    iset = UCset()
301    i1 = Uset_Iterator(s1)
302    i2 = Uset_Iterator(s2)
303    while not i1.at_end():
304        (s1_type, s1_length) = i1.current_run()
305        (s2_type, s2_length) = i2.current_run()
306        n = min(s1_length, s2_length)
307        if s1_type == Empty or s2_type == Full:
308            iset.append_run(Empty, n)
309            i1.advance(n)
310            i2.advance(n)
311        elif s1_type == Full and s2_type == Empty:
312            iset.append_run(Full, n)
313            i1.advance(n)
314            i2.advance(n)
315        elif s1_type == Full:
316            for i in range(n):
317                iset.append_quad(FullQuadMask ^ i2.get_quad())
318                i2.advance(1)
319            i1.advance(n)
320        elif s2_type == Empty:
321            for i in range(n):
322                iset.append_quad(i1.get_quad())
323                i1.advance(1)
324            i2.advance(n)
325        else:  # both s1 and s2 have mixed blocks; form block-by-block union
326            for i in range(n):
327                iset.append_quad(i1.get_quad() & ~ i2.get_quad())
328                i1.advance(1)
329                i2.advance(1)
330    return iset
331
332
333def uset_symmetric_difference(s1, s2):
334    iset = UCset()
335    i1 = Uset_Iterator(s1)
336    i2 = Uset_Iterator(s2)
337    while not i1.at_end():
338        (s1_type, s1_length) = i1.current_run()
339        (s2_type, s2_length) = i2.current_run()
340        n = min(s1_length, s2_length)
341        if s1_type == Empty and s2_type == Full or s1_type == Full and s2_type == Empty:
342            iset.append_run(Full, n)
343            i1.advance(n)
344            i2.advance(n)
345        elif s1_type == Full and s2_type == Full or s1_type == Empty and s2_type == Empty:
346            iset.append_run(Empty, n)
347            i1.advance(n)
348            i2.advance(n)
349        elif s1_type == Empty:
350            for i in range(n):
351                iset.append_quad(i2.get_quad())
352                i2.advance(1)
353            i1.advance(n)
354        elif s2_type == Empty:
355            for i in range(n):
356                iset.append_quad(i1.get_quad())
357                i1.advance(1)
358            i2.advance(n)
359        elif s1_type == Full:
360            for i in range(n):
361                iset.append_quad(FullQuadMask ^ i2.get_quad())
362                i2.advance(1)
363            i1.advance(n)
364        elif s2_type == Full:
365            for i in range(n):
366                iset.append_quad(FullQuadMask ^ i1.get_quad())
367                i1.advance(1)
368            i2.advance(n)
369        else:  # both s1 and s2 have mixed blocks; form block-by-block union
370            for i in range(n):
371                iset.append_quad(i1.get_quad() ^ i2.get_quad())
372                i1.advance(1)
373                i2.advance(1)
374    return iset
375
376
377def uset_to_range_list(s):
378    i = Uset_Iterator(s)
379    rl = []
380    open_range = False
381    range_first = 0
382    pos = 0
383    while not i.at_end():
384        (q_type, q_length) = i.current_run()
385        if q_type == Empty:
386            if open_range:
387                rl.append((range_first, pos - 1))
388                open_range = False
389            pos += q_length * quad_bits
390            i.advance(q_length)
391        elif q_type == Full:
392            if not open_range:
393                range_first = pos
394                open_range = True
395            pos += q_length * quad_bits
396            i.advance(q_length)
397        else:  # mixed quad
398            q = i.get_quad()
399            qpos = pos
400            for qpos in range(pos, pos + quad_bits):
401                if q & 1 == 0:
402                    if open_range:
403                        rl.append((range_first, qpos - 1))
404                        open_range = False
405                else:
406                    if not open_range:
407                        range_first = qpos
408                        open_range = True
409                q >>= 1
410                qpos += 1
411            pos += quad_bits
412            i.advance(1)
413    if open_range:
414        rl.append((range_first, 0x10FFFF))
415    return rl
416
417
418UCD_point_regexp = re.compile("^([0-9A-F]{4,6})\s+;")
419UCD_range_regexp = re.compile("^([0-9A-F]{4,6})[.][.]([0-9A-F]{4,6})\s+;")
Note: See TracBrowser for help on using the repository browser.