| # This is a part of rust-encoding. |
| # Copyright (c) 2013-2015, Kang Seonghoon. |
| # See README.md and LICENSE.txt for details. |
| |
| import urllib |
| import sys |
| import os.path |
| |
| def whatwg_index(name, comments): |
| for line in urllib.urlopen('http://encoding.spec.whatwg.org/index-%s.txt' % name): |
| line = line.strip() |
| if not line: continue |
| if line.startswith('#'): |
| comments.append('//' + line[1:]) |
| continue |
| parts = line.split(None, 2) |
| key = int(parts[0], 0) |
| value = int(parts[1], 0) |
| yield key, value |
| |
| def mkdir_and_open(crate, name): |
| dirname = os.path.join(os.path.dirname(__file__), crate) |
| try: |
| os.mkdir(dirname) |
| except Exception: |
| pass |
| return open(os.path.join(dirname, '%s.rs' % name.replace('-', '_')), 'wb') |
| |
| def write_header(f, name, comments): |
| print >>f, '// AUTOGENERATED FROM index-%s.txt, ORIGINAL COMMENT FOLLOWS:' % name |
| print >>f, '//' |
| for line in comments: |
| print >>f, line |
| |
| def write_comma_separated(f, prefix, l, width=80): |
| buffered = '' |
| for i in l: |
| i = str(i) |
| if len(prefix) + len(buffered) + len(i) <= width: |
| buffered += i |
| else: |
| print >>f, prefix + buffered.rstrip() |
| buffered = i |
| if buffered: |
| print >>f, prefix + buffered.rstrip() |
| |
| def make_minimal_trie(invdata, lowerlimit=0x10000): |
| maxvalue = max(invdata.keys()) + 1 |
| best = 0xffffffff |
| besttrie = None |
| for triebits in xrange(21): |
| lower = [None] * (1<<triebits) |
| upper = [] |
| lowermap = {tuple(lower): 0} |
| for i in xrange(0, maxvalue, 1<<triebits): |
| blk = [invdata.get(j) for j in xrange(i, i + (1<<triebits))] |
| loweridx = lowermap.get(tuple(blk)) |
| if loweridx is None: |
| loweridx = len(lower) |
| lowermap[tuple(blk)] = loweridx |
| lower += blk |
| upper.append(loweridx) |
| if len(lower) < lowerlimit and best >= len(lower) + len(upper): |
| best = len(lower) + len(upper) |
| besttrie = (triebits, lower, upper) |
| return besttrie |
| |
| def generate_single_byte_index(crate, name): |
| modname = name.replace('-', '_') |
| |
| data = [None] * 128 |
| invdata = {} |
| comments = [] |
| for key, value in whatwg_index(name, comments): |
| assert 0 <= key < 128 and 0 <= value < 0xffff and data[key] is None and value not in invdata |
| data[key] = value |
| invdata[value] = key |
| |
| # generate a trie with a minimal amount of data |
| triebits, lower, upper = make_minimal_trie(invdata, lowerlimit=0x10000) |
| |
| with mkdir_and_open(crate, name) as f: |
| write_header(f, name, comments) |
| print >>f |
| print >>f, "static FORWARD_TABLE: &'static [u16] = &[" |
| write_comma_separated(f, ' ', |
| ['%d, ' % (0xffff if value is None else value) for value in data]) |
| print >>f, '];' |
| print >>f |
| print >>f, '/// Returns the index code point for pointer `code` in this index.' |
| print >>f, '#[inline]' |
| print >>f, 'pub fn forward(code: u8) -> u16 {' |
| print >>f, ' FORWARD_TABLE[(code - 0x80) as usize]' |
| print >>f, '}' |
| print >>f |
| print >>f, "static BACKWARD_TABLE_LOWER: &'static [u8] = &[" |
| write_comma_separated(f, ' ', ['%d, ' % (0 if v is None else v+0x80) for v in lower]) |
| print >>f, '];' |
| print >>f |
| print >>f, "static BACKWARD_TABLE_UPPER: &'static [u16] = &[" |
| write_comma_separated(f, ' ', ['%d, ' % v for v in upper]) |
| print >>f, '];' |
| print >>f |
| print >>f, '/// Returns the index pointer for code point `code` in this index.' |
| print >>f, '#[inline]' |
| print >>f, 'pub fn backward(code: u32) -> u8 {' |
| print >>f, ' let offset = (code >> %d) as usize;' % triebits |
| print >>f, ' let offset = if offset < %d {BACKWARD_TABLE_UPPER[offset] as usize} else {0};' % len(upper) |
| print >>f, ' BACKWARD_TABLE_LOWER[offset + ((code & %d) as usize)]' % ((1<<triebits)-1) |
| print >>f, '}' |
| print >>f |
| print >>f, '#[cfg(test)]' |
| print >>f, 'single_byte_tests!(' |
| print >>f, ' mod = %s' % modname |
| print >>f, ');' |
| |
| return 2 * len(data) + len(lower) + 2 * len(upper) |
| |
| def generate_multi_byte_index(crate, name): |
| modname = name.replace('-', '_') |
| |
| data = {} |
| invdata = {} |
| dups = [] |
| comments = [] |
| morebits = False |
| for key, value in whatwg_index(name, comments): |
| assert 0 <= key < 0xffff and 0 <= value < 0x110000 and value != 0xffff and key not in data |
| if value >= 0x10001: |
| assert (value >> 16) == 2 |
| morebits = True |
| data[key] = value |
| if value not in invdata: |
| invdata[value] = key |
| else: |
| dups.append(key) |
| |
| # Big5 has four two-letter forward mappings, we use special entries for them |
| if name == 'big5': |
| specialidx = [1133, 1135, 1164, 1166] |
| assert all(key not in data for key in specialidx) |
| assert all(value not in invdata for value in xrange(len(specialidx))) |
| for value, key in enumerate(specialidx): |
| data[key] = value |
| dups.append(key) # no consistency testing for them |
| |
| # generate a trie with a minimal amount of data |
| triebits, lower, upper = make_minimal_trie(invdata, lowerlimit=0x10000) |
| |
| # JIS X 0208 index has two ranges [8272,8836) and [8836,11280) to support two slightly |
| # different encodings EUC-JP and Shift_JIS; the default backward function would favor |
| # the former, so we need a separate mapping for the latter. |
| # |
| # fortunately for us, all allocated codes in [8272,8836) have counterparts in others, |
| # so we only need a smaller remapping from [8272,8836) to other counterparts. |
| remap = None |
| if name == 'jis0208': |
| REMAP_MIN = 8272 |
| REMAP_MAX = 8835 |
| |
| invdataminusremap = {} |
| for key, value in data.items(): |
| if value not in invdataminusremap and not REMAP_MIN <= key <= REMAP_MAX: |
| invdataminusremap[value] = key |
| |
| remap = [] |
| for i in xrange(REMAP_MIN, REMAP_MAX+1): |
| if i in data: |
| assert data[i] in invdataminusremap |
| value = invdataminusremap[data[i]] |
| assert value < 0x10000 |
| remap.append(value) |
| else: |
| remap.append(0xffff) |
| |
| minkey = min(data) |
| maxkey = max(data) + 1 |
| with mkdir_and_open(crate, name) as f: |
| write_header(f, name, comments) |
| print >>f |
| print >>f, "static FORWARD_TABLE: &'static [u16] = &[" |
| write_comma_separated(f, ' ', |
| ['%d, ' % (data.get(key, 0xffff) & 0xffff) for key in xrange(minkey, maxkey)]) |
| print >>f, '];' |
| if morebits: |
| print >>f |
| print >>f, "static FORWARD_TABLE_MORE: &'static [u32] = &[" |
| bits = [] |
| for i in xrange(minkey, maxkey, 32): |
| v = 0 |
| for j in xrange(32): |
| v |= (data.get(i+j, 0) >= 0x10000) << j |
| bits.append(v) |
| write_comma_separated(f, ' ', ['%d, ' % v for v in bits]) |
| print >>f, '];' |
| print >>f |
| print >>f, '/// Returns the index code point for pointer `code` in this index.' |
| print >>f, '#[inline]' |
| print >>f, 'pub fn forward(code: u16) -> u32 {' |
| if minkey != 0: |
| print >>f, ' let code = (code as usize).wrapping_sub(%d);' % minkey |
| else: |
| print >>f, ' let code = code as usize;' |
| print >>f, ' if code < %d {' % (maxkey - minkey) |
| if morebits: |
| print >>f, ' (FORWARD_TABLE[code] as u32) | ' + \ |
| '(((FORWARD_TABLE_MORE[code >> 5] >> (code & 31)) & 1) << 17)' |
| else: |
| print >>f, ' FORWARD_TABLE[code] as u32' |
| print >>f, ' } else {' |
| print >>f, ' 0xffff' |
| print >>f, ' }' |
| print >>f, '}' |
| print >>f |
| print >>f, "static BACKWARD_TABLE_LOWER: &'static [u16] = &[" |
| write_comma_separated(f, ' ', ['%d, ' % (0xffff if v is None else v) for v in lower]) |
| print >>f, '];' |
| print >>f |
| print >>f, "static BACKWARD_TABLE_UPPER: &'static [u16] = &[" |
| write_comma_separated(f, ' ', ['%d, ' % v for v in upper]) |
| print >>f, '];' |
| if remap: |
| print >>f |
| print >>f, "static BACKWARD_TABLE_REMAPPED: &'static [u16] = &[" |
| write_comma_separated(f, ' ', ['%d, ' % v for v in remap]) |
| print >>f, '];' |
| print >>f |
| print >>f, '/// Returns the index pointer for code point `code` in this index.' |
| print >>f, '#[inline]' |
| print >>f, 'pub fn backward(code: u32) -> u16 {' |
| print >>f, ' let offset = (code >> %d) as usize;' % triebits |
| print >>f, ' let offset = if offset < %d {BACKWARD_TABLE_UPPER[offset] as usize} else {0};' % len(upper) |
| print >>f, ' BACKWARD_TABLE_LOWER[offset + ((code & %d) as usize)]' % ((1<<triebits)-1) |
| print >>f, '}' |
| if remap: |
| print >>f |
| assert name == 'jis0208' |
| print >>f, '/// Returns the index shift_jis pointer for code point `code`.' |
| print >>f, '#[inline]' |
| print >>f, 'pub fn backward_remapped(code: u32) -> u16 {' |
| print >>f, ' let value = backward(code);' |
| print >>f, ' if %d <= value && value <= %d {' % (REMAP_MIN, REMAP_MAX) |
| print >>f, ' BACKWARD_TABLE_REMAPPED[(value - %d) as usize]' % REMAP_MIN |
| print >>f, ' } else {' |
| print >>f, ' value' |
| print >>f, ' }' |
| print >>f, '}' |
| print >>f |
| print >>f, '#[cfg(test)]' |
| print >>f, 'multi_byte_tests!(' |
| print >>f, ' mod = %s,' % modname |
| if remap: |
| print >>f, ' remap = [%d, %d],' % (REMAP_MIN, REMAP_MAX) |
| if dups: |
| print >>f, ' dups = [' |
| write_comma_separated(f, ' ', ['%d, ' % v for v in sorted(dups)]) |
| print >>f, ' ]' |
| else: |
| print >>f, ' dups = []' |
| print >>f, ');' |
| |
| tablesz = 2 * (maxkey - minkey) + 2 * len(lower) + 2 * len(upper) |
| if morebits: tablesz += 4 * ((maxkey - minkey + 31) // 32) |
| if remap: tablesz += 2 * len(remap) |
| return tablesz |
| |
| def generate_multi_byte_range_lbound_index(crate, name): |
| modname = name.replace('-', '_') |
| |
| data = [] |
| comments = [] |
| for key, value in whatwg_index(name, comments): |
| data.append((key, value)) |
| assert data and data == sorted(data) |
| |
| minkey, minvalue = data[0] |
| maxkey, maxvalue = data[-1] |
| if data[0] != (0, 0): |
| data.insert(0, (0, 0)) |
| maxlog2 = 0 |
| while 2**(maxlog2 + 1) <= len(data): |
| maxlog2 += 1 |
| |
| if name == 'gb18030-ranges': |
| keyubound = 0x110000 |
| valueubound = 126 * 10 * 126 * 10 |
| else: |
| keyubound = maxkey + 1 |
| valueubound = maxvalue + 1 |
| |
| with mkdir_and_open(crate, name) as f: |
| write_header(f, name, comments) |
| print >>f |
| print >>f, "static FORWARD_TABLE: &'static [u32] = &[" |
| write_comma_separated(f, ' ', ['%d, ' % value for key, value in data]) |
| print >>f, '];' |
| print >>f |
| print >>f, "static BACKWARD_TABLE: &'static [u32] = &[" |
| write_comma_separated(f, ' ', ['%d, ' % key for key, value in data]) |
| print >>f, '];' |
| print >>f |
| print >>f, '/// Returns the index code point for pointer `code` in this index.' |
| print >>f, '#[inline]' |
| print >>f, 'pub fn forward(code: u32) -> u32 {' |
| if minkey > 0: |
| print >>f, ' if code < %d { return 0xffffffff; }' % minkey |
| if name == 'gb18030-ranges': # has "invalid" region inside |
| print >>f, ' if (code > 39419 && code < 189000) || code > 1237575 { return 0xffffffff; }' |
| print >>f, ' let mut i = if code >= BACKWARD_TABLE[%d] {%d} else {0};' % \ |
| (2**maxlog2 - 1, len(data) - 2**maxlog2 + 1) |
| for i in xrange(maxlog2-1, -1, -1): |
| print >>f, ' if code >= BACKWARD_TABLE[i%s] { i += %d; }' % \ |
| ('+%d' % (2**i-1) if i > 0 else '', 2**i) |
| print >>f, ' (code - BACKWARD_TABLE[i-1]) + FORWARD_TABLE[i-1]' |
| print >>f, '}' |
| print >>f |
| print >>f, '/// Returns the index pointer for code point `code` in this index.' |
| print >>f, '#[inline]' |
| print >>f, 'pub fn backward(code: u32) -> u32 {' |
| if minvalue > 0: |
| print >>f, ' if code < %d { return 0xffffffff; }' % minvalue |
| print >>f, ' let mut i = if code >= FORWARD_TABLE[%d] {%d} else {0};' % \ |
| (2**maxlog2 - 1, len(data) - 2**maxlog2 + 1) |
| for i in xrange(maxlog2-1, -1, -1): |
| print >>f, ' if code >= FORWARD_TABLE[i%s] { i += %d; }' % \ |
| ('+%d' % (2**i-1) if i > 0 else '', 2**i) |
| print >>f, ' (code - FORWARD_TABLE[i-1]) + BACKWARD_TABLE[i-1]' |
| print >>f, '}' |
| print >>f |
| print >>f, '#[cfg(test)]' |
| print >>f, 'multi_byte_range_tests!(' |
| print >>f, ' mod = %s,' % modname |
| print >>f, ' key = [%d, %d], key < %d,' % (minkey, maxkey, keyubound) |
| print >>f, ' value = [%d, %d], value < %d' % (minvalue, maxvalue, valueubound) |
| print >>f, ');' |
| |
| return 8 * len(data) |
| |
| INDICES = { |
| 'singlebyte/ibm866': generate_single_byte_index, |
| 'singlebyte/iso-8859-2': generate_single_byte_index, |
| 'singlebyte/iso-8859-3': generate_single_byte_index, |
| 'singlebyte/iso-8859-4': generate_single_byte_index, |
| 'singlebyte/iso-8859-5': generate_single_byte_index, |
| 'singlebyte/iso-8859-6': generate_single_byte_index, |
| 'singlebyte/iso-8859-7': generate_single_byte_index, |
| 'singlebyte/iso-8859-8': generate_single_byte_index, |
| 'singlebyte/iso-8859-10': generate_single_byte_index, |
| 'singlebyte/iso-8859-13': generate_single_byte_index, |
| 'singlebyte/iso-8859-14': generate_single_byte_index, |
| 'singlebyte/iso-8859-15': generate_single_byte_index, |
| 'singlebyte/iso-8859-16': generate_single_byte_index, |
| 'singlebyte/koi8-r': generate_single_byte_index, |
| 'singlebyte/koi8-u': generate_single_byte_index, |
| 'singlebyte/macintosh': generate_single_byte_index, |
| 'singlebyte/windows-874': generate_single_byte_index, |
| 'singlebyte/windows-1250': generate_single_byte_index, |
| 'singlebyte/windows-1251': generate_single_byte_index, |
| 'singlebyte/windows-1252': generate_single_byte_index, |
| 'singlebyte/windows-1253': generate_single_byte_index, |
| 'singlebyte/windows-1254': generate_single_byte_index, |
| 'singlebyte/windows-1255': generate_single_byte_index, |
| 'singlebyte/windows-1256': generate_single_byte_index, |
| 'singlebyte/windows-1257': generate_single_byte_index, |
| 'singlebyte/windows-1258': generate_single_byte_index, |
| 'singlebyte/x-mac-cyrillic': generate_single_byte_index, |
| |
| 'tradchinese/big5': generate_multi_byte_index, |
| 'korean/euc-kr': generate_multi_byte_index, |
| 'simpchinese/gb18030': generate_multi_byte_index, |
| 'japanese/jis0208': generate_multi_byte_index, |
| 'japanese/jis0212': generate_multi_byte_index, |
| |
| 'simpchinese/gb18030-ranges': generate_multi_byte_range_lbound_index, |
| } |
| |
| if __name__ == '__main__': |
| import sys |
| filter = sys.argv[1] if len(sys.argv) > 1 else '' |
| for index, generate in INDICES.items(): |
| crate, _, index = index.partition('/') |
| if filter not in index: continue |
| print >>sys.stderr, 'generating index %s...' % index, |
| tablesz = generate(crate, index) |
| print >>sys.stderr, '%d bytes.' % tablesz |
| |
