<filename>src/utf8lite/util/gen-casefold.py
#!/usr/bin/env python3

# Copyright 2017 <NAME>.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

import math
import re

CASE_FOLDING = 'data/ucd/CaseFolding.txt'
UNICODE_MAX = 0x10FFFF

# Parse CaseFolding.txt

try:
    file = open(CASE_FOLDING, 'r')
except FileNotFoundError:
    file = open('../' + CASE_FOLDING, 'r')

casefold = []
casefold_map = []

with file:
    for line in file:
        if line[0] != '#' and line[0] != '\n':
            fields = line.split(';')
            code = int(fields[0], 16)
            status = fields[1].strip();

            if status == 'C' or status == 'F':
                while code > len(casefold):
                    casefold.append(None)
                assert code == len(casefold)

                mapping = [int(x,16) for x in fields[2].split()]
                n = len(mapping)
                if n > 1:
                    casefold.append((n, len(casefold_map)))
                    casefold_map.extend(mapping)
                else:
                    casefold.append((1, mapping[0]))

while len(casefold) <= UNICODE_MAX:
    casefold.append(None)


def compute_tables(block_size):
    nblock = (UNICODE_MAX + 1) // block_size
    stage1 = [None] * nblock
    stage2 = []
    stage2_dict = {}
    for i in range(nblock):
        begin = i * block_size
        end = begin + block_size
        block = tuple(casefold[begin:end])
        if block in stage2_dict:
            j = stage2_dict[block]
        else:
            j = len(stage2)
            stage2_dict[block] = j
            stage2.append(block)
        stage1[i] = j
    return (stage1,stage2)


def stage1_item_size(nstage2):
    nbyte = max(1, math.ceil(math.log(nstage2, 2) / 8))
    size = 2**math.ceil(math.log(nbyte, 2))
    return size

page_size = 4096
nbytes = {}

best_block_size = 1
smallest_size = UNICODE_MAX + 1

for i in range(1,17):
    block_size = 2**i
    stage1,stage2 = compute_tables(block_size)

    nbyte1 = len(stage1) * stage1_item_size(len(stage2))
    nbyte2 = len(stage2) * block_size

    nbyte1 = math.ceil(nbyte1 / page_size) * page_size
    nbyte2 = math.ceil(nbyte2 / page_size) * page_size
    nbyte = nbyte1 + nbyte2
    nbytes[block_size] = nbyte

    if nbyte < smallest_size:
        smallest_size = nbyte
        best_block_size = block_size


block_size = best_block_size
stage1,stage2 = compute_tables(block_size)

type1_size = stage1_item_size(len(stage2))
if type1_size == 1:
    type1 = 'uint8_t'
elif type1_size == 2:
    type1 = 'uint16_t'
elif type1_size == 4:
    type1 = 'uint32_t'
else:
    type1 = 'uint64_t'

# Write casefold.h to stdout

print("/* This file is automatically generated. DO NOT EDIT!")
print("   Instead, edit gen-casefold.py and re-run.  */")
print("")
print("/*")
print(" * Case folding properties.")
print(" *")
print(" * Defined in UAX #44 \"Unicode Character Database\"")
print(" *")
print(" *     http://www.unicode.org/reports/tr44/")
print(" *")
print(" * Section 5.6, Case and Case Mapping")
print(" *")
print(" *")
print(" * We use a two-stage lookup strategy as described at")
print(" *")
print(" *     http://www.strchr.com/multi-stage_tables")
print(" *")
print(" */")
print("")
print("#ifndef UNICODE_CASEFOLD_H")
print("#define UNICODE_CASEFOLD_H")
print("")
print("#include <stdint.h>")
print("")
print("/* casefold")
print(" * --------")
print(" * length: the length (in codepoints) of the case fold mapping,")
print(" *         or 0 if there is no case fold")
print(" *")
print(" * data:   the mapped-to codepoint (length = 1), or")
print(" *         an index into the `casefold_mapping` array, pointing")
print(" *         to the first codepoint in the mapping (length > 1)")
print(" */")
print("struct casefold {")
print("\tunsigned length : 8;")
print("\tunsigned data : 24;")
print("};")
print("")
print("#define CASEFOLD_BLOCK_SIZE", block_size)
print("")
print("static const " + type1 + " casefold_stage1[] = {")
for i in range(len(stage1) - 1):
    if i % 16  == 0:
        print("/* U+{:04X} */".format(i * block_size), end="")
    print("{0: >3},".format(stage1[i]), end="")
    if i % 16 == 15:
        print("")
print("{0: >3}".format(stage1[len(stage1) - 1]))
print("};")
print("")
print("static const struct casefold casefold_stage2[][" +
        str(block_size) + "] = {")
for i in range(0,len(stage2)):
    print("  /* block " + str(i) + " */")
    print("  {", end="")
    for j in range(block_size):
        val = stage2[i][j]
        if val is None:
            print("{0,0}", end="")
        else:
            print("{{{0},0x{1:05X}}}".format(val[0], val[1]), end="")

        #print("{0: >3}".format(prop_vals[stage2[i][j]]), end="")
        if j + 1 == block_size:
            print("\n  }", end="")
        else:
            print(",", end="")
            if j % 5 == 4:
                print("\n   ", end="")
    if i + 1 != len(stage2):
        print(",\n")
    else:
        print("")
print("};")
print("")
print("static const int32_t casefold_mapping[] = {")
for i in range(len(casefold_map) - 1):
    if i % 8  == 0:
        print("/* 0x{:04X} */ ".format(i), end="")
    print("0x{0:04X},".format(casefold_map[i]), end="")
    if i % 8 == 7:
        print("")
print("0x{0:04X}".format(casefold_map[len(casefold_map) - 1]))
print("};")
print("")
print("#endif /* UNICODE_CASEFOLD_H */")

<filename>src/utf8lite/util/gen-casefold.py
#!/usr/bin/env python3

# Copyright 2017 <NAME>.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

import math
import re

CASE_FOLDING = 'data/ucd/CaseFolding.txt'
UNICODE_MAX = 0x10FFFF

# Parse CaseFolding.txt

try:
    file = open(CASE_FOLDING, 'r')
except FileNotFoundError:
    file = open('../' + CASE_FOLDING, 'r')

casefold = []
casefold_map = []

with file:
    for line in file:
        if line[0] != '#' and line[0] != '\n':
            fields = line.split(';')
            code = int(fields[0], 16)
            status = fields[1].strip();

            if status == 'C' or status == 'F':
                while code > len(casefold):
                    casefold.append(None)
                assert code == len(casefold)

                mapping = [int(x,16) for x in fields[2].split()]
                n = len(mapping)
                if n > 1:
                    casefold.append((n, len(casefold_map)))
                    casefold_map.extend(mapping)
                else:
                    casefold.append((1, mapping[0]))

while len(casefold) <= UNICODE_MAX:
    casefold.append(None)


def compute_tables(block_size):
    nblock = (UNICODE_MAX + 1) // block_size
    stage1 = [None] * nblock
    stage2 = []
    stage2_dict = {}
    for i in range(nblock):
        begin = i * block_size
        end = begin + block_size
        block = tuple(casefold[begin:end])
        if block in stage2_dict:
            j = stage2_dict[block]
        else:
            j = len(stage2)
            stage2_dict[block] = j
            stage2.append(block)
        stage1[i] = j
    return (stage1,stage2)


def stage1_item_size(nstage2):
    nbyte = max(1, math.ceil(math.log(nstage2, 2) / 8))
    size = 2**math.ceil(math.log(nbyte, 2))
    return size

page_size = 4096
nbytes = {}

best_block_size = 1
smallest_size = UNICODE_MAX + 1

for i in range(1,17):
    block_size = 2**i
    stage1,stage2 = compute_tables(block_size)

    nbyte1 = len(stage1) * stage1_item_size(len(stage2))
    nbyte2 = len(stage2) * block_size

    nbyte1 = math.ceil(nbyte1 / page_size) * page_size
    nbyte2 = math.ceil(nbyte2 / page_size) * page_size
    nbyte = nbyte1 + nbyte2
    nbytes[block_size] = nbyte

    if nbyte < smallest_size:
        smallest_size = nbyte
        best_block_size = block_size


block_size = best_block_size
stage1,stage2 = compute_tables(block_size)

type1_size = stage1_item_size(len(stage2))
if type1_size == 1:
    type1 = 'uint8_t'
elif type1_size == 2:
    type1 = 'uint16_t'
elif type1_size == 4:
    type1 = 'uint32_t'
else:
    type1 = 'uint64_t'

# Write casefold.h to stdout

print("/* This file is automatically generated. DO NOT EDIT!")
print("   Instead, edit gen-casefold.py and re-run.  */")
print("")
print("/*")
print(" * Case folding properties.")
print(" *")
print(" * Defined in UAX #44 \"Unicode Character Database\"")
print(" *")
print(" *     http://www.unicode.org/reports/tr44/")
print(" *")
print(" * Section 5.6, Case and Case Mapping")
print(" *")
print(" *")
print(" * We use a two-stage lookup strategy as described at")
print(" *")
print(" *     http://www.strchr.com/multi-stage_tables")
print(" *")
print(" */")
print("")
print("#ifndef UNICODE_CASEFOLD_H")
print("#define UNICODE_CASEFOLD_H")
print("")
print("#include <stdint.h>")
print("")
print("/* casefold")
print(" * --------")
print(" * length: the length (in codepoints) of the case fold mapping,")
print(" *         or 0 if there is no case fold")
print(" *")
print(" * data:   the mapped-to codepoint (length = 1), or")
print(" *         an index into the `casefold_mapping` array, pointing")
print(" *         to the first codepoint in the mapping (length > 1)")
print(" */")
print("struct casefold {")
print("\tunsigned length : 8;")
print("\tunsigned data : 24;")
print("};")
print("")
print("#define CASEFOLD_BLOCK_SIZE", block_size)
print("")
print("static const " + type1 + " casefold_stage1[] = {")
for i in range(len(stage1) - 1):
    if i % 16  == 0:
        print("/* U+{:04X} */".format(i * block_size), end="")
    print("{0: >3},".format(stage1[i]), end="")
    if i % 16 == 15:
        print("")
print("{0: >3}".format(stage1[len(stage1) - 1]))
print("};")
print("")
print("static const struct casefold casefold_stage2[][" +
        str(block_size) + "] = {")
for i in range(0,len(stage2)):
    print("  /* block " + str(i) + " */")
    print("  {", end="")
    for j in range(block_size):
        val = stage2[i][j]
        if val is None:
            print("{0,0}", end="")
        else:
            print("{{{0},0x{1:05X}}}".format(val[0], val[1]), end="")

        #print("{0: >3}".format(prop_vals[stage2[i][j]]), end="")
        if j + 1 == block_size:
            print("\n  }", end="")
        else:
            print(",", end="")
            if j % 5 == 4:
                print("\n   ", end="")
    if i + 1 != len(stage2):
        print(",\n")
    else:
        print("")
print("};")
print("")
print("static const int32_t casefold_mapping[] = {")
for i in range(len(casefold_map) - 1):
    if i % 8  == 0:
        print("/* 0x{:04X} */ ".format(i), end="")
    print("0x{0:04X},".format(casefold_map[i]), end="")
    if i % 8 == 7:
        print("")
print("0x{0:04X}".format(casefold_map[len(casefold_map) - 1]))
print("};")
print("")
print("#endif /* UNICODE_CASEFOLD_H */")

#!/usr/bin/env python3 # Copyright 2017 <NAME>. # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # #     http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # Parse CaseFolding.txt # Write casefold.h to stdout #44 \"Unicode Character Database\"") #print("{0: >3}".format(prop_vals[stage2[i][j]]), end="")