source: proto/u8u16.py @ 296

Last change on this file since 296 was 276, checked in by cameron, 10 years ago

u8u16 python prototype from u8u16.costar.sfu.ca

  • Property svn:executable set to *
File size: 11.1 KB
Line 
1#!/usr/bin/python
2
3# u8u16.py
4#
5# Python prototype implementation
6# Robert D. Cameron
7# revised August 5, 2009 - use generated UTF-8 definitions
8#
9#
10#
11#----------------------------------------------------------------------------
12#
13# We use python's unlimited precision integers for unbounded bit streams.
14# This permits simple logical operations on the entire stream.
15# Assumption: bitstreams are little-endian (e.g., as on x86).
16#
17#----------------------------------------------------------------------------
18#
19
20# Utility functions for demo purposes.  Slowwwww, but simple.
21
22
23#
24def readfile(filename):
25        f = open(filename)
26        contents = f.read()
27        f.close()
28        return contents
29
30
31def count_leading_zeroes(strm):
32        zeroes = 0
33        while (strm & 0xFFFFFFFF) == 0: 
34                zeroes += 32
35                strm >>= 32
36        while (strm & 1) == 0:
37                zeroes += 1
38                strm >>= 1
39        return zeroes
40       
41#
42def transpose_streams(s):
43       
44        b = []
45       
46        mask = 128
47        index = 0
48        while index < 8:
49                current = 0
50                cursor = 1
51                for c in s:
52                       
53                        if isinstance(c,str):
54                                val = ord(c)
55                        else:
56                                val = c
57                        if  (val & mask != 0):
58                                current += cursor
59                        cursor <<= 1
60                       
61                index+=1
62                mask>>=1
63                b.append(current)
64        return b
65
66def inverse_transpose(bitset, len):
67        bytestream=""
68        cursor = 1
69        for i in range(0, len):
70                byteval = 0
71                for j in range(0,8):
72                        if bitset[j] & cursor != 0:
73                                byteval += 128 >> j
74                bytestream += chr(byteval)
75                cursor += cursor
76        return bytestream
77                       
78def filter_bytes(bytestream, delmask):
79        newstream=""
80        cursor = 1
81        for c in bytestream:
82                if delmask & cursor == 0:
83                        newstream += c
84                cursor += cursor
85        return newstream
86                       
87def merge_bytes(stream1, stream2):
88        s = ""
89        for i in range(len(stream1)):
90                s += stream1[i]
91                s += stream2[i]
92        return s
93
94def bitstream2string(stream, lgth):
95        str = ""
96        for i in range(lgth):
97                if stream & 1 == 1: str += '1'
98                else: str += '_'
99                stream >>= 1
100        return str
101#
102# Advance all cursors by one position.
103def Advance(stream):
104        return stream + stream
105
106def ShiftBack(stream):
107        return stream >> 1
108
109
110def u8_streams(u8bit):
111        u8 = {}
112        u8['unibyte'] = ~u8bit[0]
113        u8['prefix'] = u8bit[0] & u8bit[1]
114        u8['suffix'] = u8bit[0] & ~u8bit[1]
115        u8prefix3or4 = u8['prefix'] & u8bit[2]
116        u8['prefix2'] = u8['prefix'] & ~u8bit[2]
117        u8['prefix3'] = u8prefix3or4 & ~u8bit[3]
118        u8['prefix4'] = u8prefix3or4 & u8bit[3]
119        u8['scope22'] = Advance(u8['prefix2'])
120        u8['scope32'] = Advance(u8['prefix3'])
121        u8['scope42'] = Advance(u8['prefix4'])
122        u8['scope33'] = Advance(u8['scope32'])
123        u8['scope43'] = Advance(u8['scope42'])
124        u8['scope44'] = Advance(u8['scope43'])
125       
126        u8lastscope = u8['scope22'] | u8['scope33'] | u8['scope44']
127        u8anyscope = u8lastscope | u8['scope32'] | u8['scope42'] | u8['scope43']
128       
129        # C0-C1 are illegal
130        error_mask = u8['prefix2'] &~ (u8bit[3] | u8bit[4] | u8bit[5] | u8bit[6]) 
131       
132        prefix_E0ED = u8['prefix3'] &~ ((u8bit[6] | (u8bit[4] ^ u8bit[7])) | (u8bit[4] ^ u8bit[5]))
133        E0ED_constraint = Advance(u8bit[5]) ^ u8bit[2]
134        error_mask |= Advance(prefix_E0ED) &~ E0ED_constraint
135       
136        prefix_F5FF = u8['prefix4'] & (u8bit[4] | (u8bit[5] & (u8bit[6] | u8bit[7])))
137        error_mask |= prefix_F5FF
138
139        prefix_F0F4 = u8['prefix4'] &~ (u8bit[4] | u8bit[6] | u8bit[7])
140        F0F4_constraint = Advance(u8bit[5]) ^ (u8bit[2] | u8bit[3])
141        error_mask |= Advance(prefix_F0F4) &~ F0F4_constraint
142       
143        error_mask |= u8anyscope ^ u8['suffix']
144        u8['error'] = error_mask
145        return u8
146
147
148#
149# Generated version using chardeflist2py(DefinitionSet['UTF8'])
150#
151def u8_streams_generated(bit): 
152  unibyte = (~bit[0]);
153  prefix = (bit[0] & bit[1]);
154  prefix2 = (prefix &~ bit[2]);
155  temp1 = (bit[2] &~ bit[3]);
156  prefix3 = (prefix & temp1);
157  temp2 = (bit[2] & bit[3]);
158  prefix4 = (prefix & temp2);
159  suffix = (bit[0] &~ bit[1]);
160  temp3 = (bit[2] | bit[3]);
161  temp4 = (prefix &~ temp3);
162  temp5 = (bit[4] | bit[5]);
163  temp6 = (temp5 | bit[6]);
164  temp7 = (temp4 &~ temp6);
165  temp8 = (bit[6] | bit[7]);
166  temp9 = (bit[5] & temp8);
167  temp10 = (bit[4] | temp9);
168  temp11 = (prefix4 & temp10);
169  badprefix = (temp7 | temp11);
170  temp12 = (temp5 | temp8);
171  xE0 = (prefix3 &~ temp12);
172  temp13 = (bit[4] & bit[5]);
173  temp14 = (bit[7] &~ bit[6]);
174  temp15 = (temp13 & temp14);
175  xED = (prefix3 & temp15);
176  xF0 = (prefix4 &~ temp12);
177  temp16 = (bit[5] &~ bit[4]);
178  temp17 = (temp16 &~ temp8);
179  xF4 = (prefix4 & temp17);
180  xA0_xBF = (suffix & bit[2]);
181  x80_x9F = (suffix &~ bit[2]);
182  x90_xBF = (suffix & temp3);
183  x80_x8F = (suffix &~ temp3);
184
185#
186# End of generated code
187  u8 = {}
188  u8['unibyte'] = unibyte
189  u8['prefix'] = prefix
190  u8['suffix'] = suffix
191  u8['prefix2'] = prefix2
192  u8['prefix3'] = prefix3
193  u8['prefix4'] = prefix4
194  u8['scope22'] = Advance(u8['prefix2'])
195  u8['scope32'] = Advance(u8['prefix3'])
196  u8['scope42'] = Advance(u8['prefix4'])
197  u8['scope33'] = Advance(u8['scope32'])
198  u8['scope43'] = Advance(u8['scope42'])
199  u8['scope44'] = Advance(u8['scope43'])
200       
201  u8lastscope = u8['scope22'] | u8['scope33'] | u8['scope44']
202  u8anyscope = u8lastscope | u8['scope32'] | u8['scope42'] | u8['scope43']
203       
204  # C0-C1 and F5-FF are illegal
205  error_mask = badprefix
206       
207  error_mask |= Advance(xE0) & x80_x9F
208  error_mask |= Advance(xED) & xA0_xBF
209  error_mask |= Advance(xF0) & x80_x8F
210  error_mask |= Advance(xF4) & x90_xBF
211       
212  error_mask |= u8anyscope ^ u8['suffix']
213  u8['error'] = error_mask
214  return u8
215
216
217#
218# The following calculation of UTF-16 bit streams is consistent
219# with the original u8u16, calculating streams at u8scope42 and
220# u8scope44 positions.
221#
222
223def u16_streams(u8, u8bit):
224        u16hi = [0,0,0,0,0,0,0,0]
225        u16lo = [0,0,0,0,0,0,0,0]
226       
227        u8lastscope = u8['scope22'] | u8['scope33'] | u8['scope44']
228        u8lastbyte = u8['unibyte'] | u8lastscope
229        u16lo[2] = u8lastbyte & u8bit[2]
230        u16lo[3] = u8lastbyte & u8bit[3]
231        u16lo[4] = u8lastbyte & u8bit[4]
232        u16lo[5] = u8lastbyte & u8bit[5]
233        u16lo[6] = u8lastbyte & u8bit[6]
234        u16lo[7] = u8lastbyte & u8bit[7]
235        u16lo[1] = (u8['unibyte'] & u8bit[1]) | (u8lastscope & Advance(u8bit[7]))
236        u16lo[0] = u8lastscope & Advance(u8bit[6])
237       
238        u16hi[5] = u8lastscope & Advance(u8bit[3])
239        u16hi[6] = u8lastscope & Advance(u8bit[4])
240        u16hi[7] = u8lastscope & Advance(u8bit[5])
241        u16hi[0] = u8['scope33'] & Advance(Advance(u8bit[4]))
242        u16hi[1] = u8['scope33'] & Advance(Advance(u8bit[5]))
243        u16hi[2] = u8['scope33'] & Advance(Advance(u8bit[6]))
244        u16hi[3] = u8['scope33'] & Advance(Advance(u8bit[7]))
245        u16hi[4] = u8['scope33'] & Advance(u8bit[2])
246
247        u8surrogate = u8['scope42'] | u8['scope44']
248        u16hi[0] = u16hi[0] | u8surrogate       
249        u16hi[1] = u16hi[1] | u8surrogate       
250        u16hi[3] = u16hi[3] | u8surrogate       
251        u16hi[4] = u16hi[4] | u8surrogate       
252        u16hi[5] = u16hi[5] | u8['scope44']
253
254        s42lo1 = ~u8bit[3] # subtract 1
255        u16lo[1] = u16lo[1] | (u8['scope42'] & s42lo1)
256        s42lo0 = u8bit[2] ^ s42lo1 # borrow *
257        u16lo[0] = u16lo[0] | (u8['scope42'] & s42lo0)
258        borrow1 = s42lo1 & ~u8bit[2]
259        s42hi7 = Advance(u8bit[7]) ^ borrow1
260        u16hi[7]= u16hi[7] | (u8['scope42'] & s42hi7)
261        borrow2 = borrow1 & ~Advance(u8bit[7])
262        s42hi6 = Advance(u8bit[6]) ^ borrow2
263        u16hi[6] = u16hi[6] | (u8['scope42'] & s42hi6)
264
265        u16lo[2] = u16lo[2] | (u8['scope42'] & u8bit[4])
266        u16lo[3] = u16lo[3] | (u8['scope42'] & u8bit[5])
267        u16lo[4] = u16lo[4] | (u8['scope42'] & u8bit[6])
268        u16lo[5] = u16lo[5] | (u8['scope42'] & u8bit[7])
269        u16lo[6] = u16lo[6] | (u8['scope42'] & ShiftBack(u8bit[2]))
270        u16lo[7] = u16lo[7] | (u8['scope42'] & ShiftBack(u8bit[3]))
271
272        delmask = u8['prefix'] | u8['scope32'] | u8['scope43']
273        return (u16hi, u16lo, delmask)
274
275
276
277
278#
279# The following calculation of UTF-16 bit streams uses the
280# u8scope43 position rather than the u8scope42 position for
281# the bits of the first UTF-16 code unit of a surrogate pair.
282# This requires more shifting than with the use of u8scope42,
283# but has the advantage that all shifts are in the forward
284# direction only and can hence be implemented using addition
285# on little-endian architecture.
286#
287
288def u16_streams_fwdonly(u8, u8bit):
289        u16hi = [0,0,0,0,0,0,0,0]
290        u16lo = [0,0,0,0,0,0,0,0]
291       
292        u8lastscope = u8['scope22'] | u8['scope33'] | u8['scope44']
293        u8lastbyte = u8['unibyte'] | u8lastscope
294        u16lo[2] = u8lastbyte & u8bit[2]
295        u16lo[3] = u8lastbyte & u8bit[3]
296        u16lo[4] = u8lastbyte & u8bit[4]
297        u16lo[5] = u8lastbyte & u8bit[5]
298        u16lo[6] = u8lastbyte & u8bit[6]
299        u16lo[7] = u8lastbyte & u8bit[7]
300        u16lo[1] = (u8['unibyte'] & u8bit[1]) | (u8lastscope & Advance(u8bit[7]))
301        u16lo[0] = u8lastscope & Advance(u8bit[6])
302       
303        u16hi[5] = u8lastscope & Advance(u8bit[3])
304        u16hi[6] = u8lastscope & Advance(u8bit[4])
305        u16hi[7] = u8lastscope & Advance(u8bit[5])
306        u16hi[0] = u8['scope33'] & Advance(Advance(u8bit[4]))
307        u16hi[1] = u8['scope33'] & Advance(Advance(u8bit[5]))
308        u16hi[2] = u8['scope33'] & Advance(Advance(u8bit[6]))
309        u16hi[3] = u8['scope33'] & Advance(Advance(u8bit[7]))
310        u16hi[4] = u8['scope33'] & Advance(u8bit[2])
311
312        u8surrogate = u8['scope43'] | u8['scope44']
313        u16hi[0] = u16hi[0] | u8surrogate       
314        u16hi[1] = u16hi[1] | u8surrogate       
315        u16hi[3] = u16hi[3] | u8surrogate       
316        u16hi[4] = u16hi[4] | u8surrogate       
317        u16hi[5] = u16hi[5] | u8['scope44']
318
319
320        s42lo1 = ~u8bit[3] # subtract 1
321        u16lo[1] = u16lo[1] | (u8['scope43'] & Advance(s42lo1))
322        s42lo0 = u8bit[2] ^ s42lo1 # borrow *
323        u16lo[0] = u16lo[0] | (u8['scope43'] & Advance(s42lo0))
324        borrow1 = s42lo1 & ~u8bit[2]
325        advance_bit7 = Advance(u8bit[7])
326        s42hi7 = advance_bit7 ^ borrow1
327        u16hi[7]= u16hi[7] | (u8['scope43'] & Advance(s42hi7))
328        borrow2 = borrow1 & ~advance_bit7
329        s42hi6 = Advance(u8bit[6]) ^ borrow2
330        u16hi[6] = u16hi[6] | (u8['scope43'] & Advance(s42hi6))
331
332        u16lo[2] = u16lo[2] | (u8['scope43'] & Advance(u8bit[4]))
333        u16lo[3] = u16lo[3] | (u8['scope43'] & Advance(u8bit[5]))
334        u16lo[4] = u16lo[4] | (u8['scope43'] & Advance(u8bit[6]))
335        u16lo[5] = u16lo[5] | (u8['scope43'] & Advance(u8bit[7]))
336        u16lo[6] = u16lo[6] | (u8['scope43'] & u8bit[2])
337        u16lo[7] = u16lo[7] | (u8['scope43'] & u8bit[3])
338
339        delmask = u8['prefix'] | u8['scope32'] | u8['scope42']
340        return (u16hi, u16lo, delmask)
341
342
343
344#
345# Messages to duplicate u8u16 error reporting.
346#
347def IllegalSequenceMessage(pos):
348        return "Illegal UTF-8 sequence at position %i in source.\n" % pos
349
350def IncompleteSequenceMessage(pos):
351        return "EOF with incomplete UTF-8 sequence at position %i in source.\n" % pos
352
353
354import sys
355def main():
356
357        if len(sys.argv) < 2:
358                sys.stderr.write("Usage: u8u16.py u8file [u16file]\n")
359                exit
360        if len(sys.argv) == 3:
361                outfile = open(sys.argv[2],"w")
362        else: outfile = sys.stdout
363        u8data = readfile(sys.argv[1])
364        u8len = len(u8data)
365        u8bit = transpose_streams(u8data)
366#       u8 = u8_streams(u8bit)
367        u8 = u8_streams_generated(u8bit)
368        if u8['error'] != 0:
369                err_pos = count_leading_zeroes(u8['error'])
370                at_EOF = err_pos == len(u8data)
371                if (err_pos >= 1) and ord(u8data[err_pos-1]) >= 0xC0: err_pos -= 1
372                elif err_pos >= 2 and ord(u8data[err_pos-2]) >= 0xE0: err_pos -= 2
373                elif err_pos >= 3 and ord(u8data[err_pos-3]) >= 0xF0: err_pos -= 3     
374                if at_EOF:
375                        sys.stderr.write(IncompleteSequenceMessage(err_pos))
376                else:
377                        sys.stderr.write(IllegalSequenceMessage(err_pos))
378                u8len = err_pos
379#       Originally, we used the u16_streams version.
380#       (u16hi, u16lo, delmask) = u16_streams(u8, u8bit)
381        (u16hi, u16lo, delmask) = u16_streams_fwdonly(u8, u8bit)
382        U16H = filter_bytes(inverse_transpose(u16hi, u8len), delmask)
383        U16L = filter_bytes(inverse_transpose(u16lo, u8len), delmask)
384        U16final = merge_bytes(U16H, U16L)
385        outfile.write(U16final)
386        outfile.close()
387               
388if __name__ == "__main__": main()
389
390
Note: See TracBrowser for help on using the repository browser.