dymokomi/luce-regex
Source of release 0.6.1
0.6.1 / src / unicode / normalize.lucb
#==============================================================================================
#
# normalize - Decomposition, composition and the NFC/NFD/NFKC/NFKD normalization
#
# DESCRIPTION:
# Port of QuickJS libunicode.c lines 761-1243: the decomposition table decoder, the
# composition search, combining classes, canonical ordering and unicode_normalize.
# Normalized text is a buffer of `u32` code points (C uses `int` for the working
# buffer; the values are the same).
#
#==============================================================================================
# mark: Decomposition table ====================================================================
let unicode_decomp_len_max: i32 = 18
enum DecompTypeEnum as u32:
c1 = 0 # 16 bit char
l1 = 1 # 16 bit char table
l2 = 2
l3 = 3
l4 = 4
l5 = 5 # XXX: not used
l6 = 6 # XXX: could remove
l7 = 7 # XXX: could remove
ll1 = 8 # 18 bit char table
ll2 = 9
s1 = 10 # 8 bit char table
s2 = 11
s3 = 12
s4 = 13
s5 = 14
i1 = 15 # increment 16 bit char value
i2_0 = 16
i2_1 = 17
i3_1 = 18
i3_2 = 19
i4_1 = 20
i4_2 = 21
b1 = 22 # 16 bit base + 8 bit offset
b2 = 23
b3 = 24
b4 = 25
b5 = 26
b6 = 27
b7 = 28
b8 = 29
b18 = 30
ls2 = 31
pat3 = 32
s2_ul = 33
ls2_ul = 34
let unicode_short_table: u16[2] = [0x2044, 0x2215]
func unicode_get_short_code(c: u32) -> u32:
if c < 0x80:
return c
elif c < 0x80 + 0x50:
return c - 0x80 + 0x300
else:
return unicode_short_table[c - 0x80 - 0x50]
func unicode_get_lower_simple(c: u32) -> u32:
if c < 0x100 or (c >= 0x410 and c <= 0x42f):
return c + 0x20
else:
return c + 1
func unicode_get16(p: const u8*) -> u16:
let lo: u16 = p[0]
let hi: u16 = p[1]
return lo | (hi << 8)
func unicode_decomp_entry(res: u32[], c: u32, idx: i32, code: u32, len: u32,
decomp_type: u32) -> i32:
if decomp_type == (u32)DecompTypeEnum.c1:
res[0] = unicode_decomp_table2[(usize)idx]
return 1
var d: const u8* = &unicode_decomp_data[unicode_decomp_table2[(usize)idx]]
match (DecompTypeEnum)decomp_type:
.l1, .l2, .l3, .l4, .l5, .l6, .l7:
let l = (i32)(decomp_type - (u32)DecompTypeEnum.l1) + 1
d = d + (usize)((c - code) * (u32)l * 2)
for i in 0..<(usize)l:
res[i] = unicode_get16(d + 2 * i)
if res[i] == 0:
return 0
return l
.ll1, .ll2:
let l = (i32)(decomp_type - (u32)DecompTypeEnum.ll1) + 1
var k: u32 = (c - code) * (u32)l
let p: u32 = len * (u32)l * 2
for i in 0..<(usize)l:
let low: u32 = unicode_get16(d + (usize)(2 * k))
let bits: u32 = d[(usize)(p + (k // 4))]
let c1 = low | (((bits >> ((k % 4) * 2)) & 3) << 16)
if c1 == 0:
return 0
res[i] = c1
k += 1
return l
.s1, .s2, .s3, .s4, .s5:
let l = (i32)(decomp_type - (u32)DecompTypeEnum.s1) + 1
d = d + (usize)((c - code) * (u32)l)
for i in 0..<(usize)l:
res[i] = unicode_get_short_code(d[i])
if res[i] == 0:
return 0
return l
.i1, .i2_0, .i2_1, .i3_1, .i3_2, .i4_1, .i4_2:
# the C `goto decomp_type_i` from DECOMP_TYPE_I1
var l: i32 = 1
var p: i32 = 0
if decomp_type != (u32)DecompTypeEnum.i1:
l = 2 + (i32)((decomp_type - (u32)DecompTypeEnum.i2_0) >> 1)
p = (i32)((decomp_type - (u32)DecompTypeEnum.i2_0) & 1) + (i32)(l > 2)
for i: i32 in 0..<l:
var c1: u32 = unicode_get16(d + 2 * (usize)i)
if i == p:
c1 += c - code
res[(usize)i] = c1
return l
.b1, .b2, .b3, .b4, .b5, .b6, .b7, .b8, .b18:
# the C `goto decomp_type_b` from DECOMP_TYPE_B18
var l: i32 = 18
if decomp_type != (u32)DecompTypeEnum.b18:
l = (i32)(decomp_type - (u32)DecompTypeEnum.b1) + 1
let c_min: u32 = unicode_get16(d)
d = d + 2 + (usize)((c - code) * (u32)l)
for i in 0..<(usize)l:
var c1: u32 = d[i]
if c1 == 0xff:
c1 = 0x20
else:
c1 += c_min
res[i] = c1
return l
.ls2:
d = d + (usize)((c - code) * 3)
res[0] = unicode_get16(d)
if res[0] == 0:
return 0
res[1] = unicode_get_short_code(d[2])
return 2
.pat3:
res[0] = unicode_get16(d)
res[2] = unicode_get16(d + 2)
d = d + 4 + (usize)((c - code) * 2)
res[1] = unicode_get16(d)
return 3
.s2_ul, .ls2_ul:
let c1 = c - code
var c2: u32 = 0
if decomp_type == (u32)DecompTypeEnum.s2_ul:
d = d + (usize)(c1 & ~1u32)
c2 = unicode_get_short_code(*d)
d = d + 1
else:
d = d + (usize)((c1 >> 1) * 3)
c2 = unicode_get16(d)
d = d + 2
if (c1 & 1) != 0:
c2 = unicode_get_lower_simple(c2)
res[0] = c2
res[1] = unicode_get_short_code(*d)
return 2
_:
return 0
# return the length of the decomposition (length <=
# UNICODE_DECOMP_LEN_MAX) or 0 if no decomposition
func unicode_decomp_char(res: u32[], c: u32, is_compat1: bool) -> i32:
var idx_min: i32 = 0
var idx_max: i32 = (i32)unicode_decomp_table1.length - 1
while idx_min <= idx_max:
let idx = (idx_max + idx_min) // 2
let v = unicode_decomp_table1[(usize)idx]
let code = v >> (32 - 18)
let len = (v >> (32 - 18 - 7)) & 0x7f
if c < code:
idx_max = idx - 1
elif c >= code + len:
idx_min = idx + 1
else:
let is_compat = v & 1
if (u32)is_compat1 < is_compat:
break
let decomp_type = (v >> (32 - 18 - 7 - 6)) & 0x3f
return unicode_decomp_entry(res, c, idx, code, len, decomp_type)
return 0
# mark: Composition ============================================================================
# return 0 if no pair found
func unicode_compose_pair(c0: u32, c1: u32) -> i32:
var pair: u32[2]
var idx_min: i32 = 0
var idx_max: i32 = (i32)unicode_comp_table.length - 1
while idx_min <= idx_max:
let idx = (idx_max + idx_min) // 2
let idx1: u32 = unicode_comp_table[(usize)idx]
# idx1 represent an entry of the decomposition table
let d_idx = idx1 >> 6
let d_offset = idx1 & 0x3f
let v = unicode_decomp_table1[d_idx]
let code = v >> (32 - 18)
let len = (v >> (32 - 18 - 7)) & 0x7f
let decomp_type = (v >> (32 - 18 - 7 - 6)) & 0x3f
let ch = code + d_offset
_ = unicode_decomp_entry(pair, ch, (i32)d_idx, code, len, decomp_type)
var d = (i32)(c0 -% pair[0])
if d == 0:
d = (i32)(c1 -% pair[1])
if d < 0:
idx_max = idx - 1
elif d > 0:
idx_min = idx + 1
else:
return (i32)ch
return 0
# mark: Combining classes ======================================================================
# return the combining class of character c (between 0 and 255)
func unicode_get_cc(c: u32) -> i32:
var code: u32 = 0
let pos = get_index_pos(&code, c, unicode_cc_index)
if pos < 0:
return 0
var p: const u8* = &unicode_cc_table[(usize)pos]
# Compressed run length encoding:
# - 2 high order bits are combining class type
# - 0:0, 1:230, 2:extra byte linear progression, 3:extra byte
# - 00..2F: range length (add 1)
# - 30..37: 3-bit range-length + 1 extra byte
# - 38..3F: 3-bit range-length + 2 extra byte
while true:
let b: u32 = *p
p = p + 1
let cc_type = b >> 6
var n = b & 0x3f
# (00..2F: the length is n itself)
if n >= 48 and n < 56:
n = (n - 48) << 8
let e0: u32 = *p
p = p + 1
n |= e0
n += 48
elif n >= 56:
n = (n - 56) << 8
let e0: u32 = *p
p = p + 1
n |= e0 << 8
let e1: u32 = *p
p = p + 1
n |= e1
n += 48 + (1 << 11)
if cc_type <= 1:
p = p + 1
let c1 = code + n + 1
if c < c1:
let prev: u32 = *(p - 1)
match cc_type:
0:
return (i32)prev
1:
return (i32)(prev + c - code)
2:
return 0
_:
return 230
code = c1
func sort_cc(buf: u32[]):
let len = (i32)buf.length
var i: i32 = 0
while i < len:
let cc = unicode_get_cc(buf[(usize)i])
if cc != 0:
let start = i
var j = i + 1
while j < len:
let ch1 = buf[(usize)j]
let cc1 = unicode_get_cc(ch1)
if cc1 == 0:
break
var k = j - 1
while k >= start:
if unicode_get_cc(buf[(usize)k]) <= cc1:
break
buf[(usize)(k + 1)] = buf[(usize)k]
k -= 1
buf[(usize)(k + 1)] = ch1
j += 1
i = j
i += 1
# mark: Normalization ==========================================================================
func to_nfd_rec(dbuf: DynBuf*, src: const u32[], is_compat: bool):
var res: u32[18]
for i in 0..<src.length:
var c = src[i]
if c >= 0xac00 and c < 0xd7a4:
# Hangul decomposition
c -= 0xac00
_ = dbuf_put_u32(dbuf, 0x1100 + c // 588)
_ = dbuf_put_u32(dbuf, 0x1161 + (c % 588) // 28)
let v = c % 28
if v != 0:
_ = dbuf_put_u32(dbuf, 0x11a7 + v)
else:
let l = unicode_decomp_char(res, c, is_compat)
if l != 0:
to_nfd_rec(dbuf, res[0..<(usize)l], is_compat)
else:
_ = dbuf_put_u32(dbuf, c)
# return 0 if not found
func compose_pair(c0: u32, c1: u32) -> i32:
# Hangul composition
if (c0 >= 0x1100 and c0 < 0x1100 + 19 and c1 >= 0x1161 and c1 < 0x1161 + 21):
return (i32)(0xac00 + (c0 - 0x1100) * 588 + (c1 - 0x1161) * 28)
elif (c0 >= 0xac00 and c0 < 0xac00 + 11172 and (c0 - 0xac00) % 28 == 0 and c1 >= 0x11a7 and c1 < 0x11a7 + 28):
return (i32)(c0 + c1 - 0x11a7)
else:
return unicode_compose_pair(c0, c1)
# The code points of a DynBuf as a span (empty when it has no storage).
func dbuf_u32(dbuf: const DynBuf*, count: usize) -> u32[]:
if let b = dbuf.buf:
return u32[]((u32*)b, count)
var empty: u32[]
return empty
# The DynBuf storage as the result pointer (none when it has no storage).
func dbuf_result(dbuf: const DynBuf*) -> u32*?:
if let b = dbuf.buf:
return (u32*)b
return none
## Normalize the code points `src` to the form `n_type` into a buffer allocated with
## `realloc_func(opaque, ...)` (C `realloc` when none), stored in `*pdst`; answer its length
## in code points, or -1 (and `*pdst` none) when memory runs out. The caller frees `*pdst`.
pub func unicode_normalize(pdst: u32*?*, src: const u32[], n_type: UnicodeNormalizationEnum,
opaque: void*?, realloc_func: ReallocFunc?) -> i32:
let src_len = src.length
let is_compat = (n_type >> 1) != 0
var dbuf_s: DynBuf
let dbuf = &dbuf_s
dbuf_init2(dbuf, opaque, realloc_func)
if dbuf_claim(dbuf, memory.size_of(u32) * src_len) != 0:
*pdst = none
return -1
# common case: latin1 is unaffected by NFC
if n_type == unicode_nfc:
var latin1 = true
for i in 0..<src_len:
if src[i] >= 0x100:
latin1 = false
break
if latin1:
if src_len != 0:
let b = dbuf.buf else trap("unicode_normalize: no storage")
_ = memcpy(b, src.data, src_len * memory.size_of(u32))
*pdst = dbuf_result(dbuf)
return (i32)src_len
to_nfd_rec(dbuf, src, is_compat)
if dbuf_error(dbuf):
*pdst = none
return -1
let buf_len = dbuf.size // memory.size_of(u32)
let buf = dbuf_u32(dbuf, buf_len)
sort_cc(buf)
if buf_len <= 1 or (n_type & 1) != 0:
# NFD / NFKD
*pdst = dbuf_result(dbuf)
return (i32)buf_len
var i: usize = 1
var out_len: usize = 1
while i < buf_len:
# find the starter character and test if it is blocked from
# the character at 'i'
var last_cc = unicode_get_cc(buf[i])
var starter_pos = (isize)out_len - 1
var blocked = false # the C `goto next`
while starter_pos >= 0:
let cc = unicode_get_cc(buf[(usize)starter_pos])
if cc == 0:
break
if cc >= last_cc:
blocked = true
break
last_cc = 256
starter_pos -= 1
var p: i32 = 0
if not blocked and starter_pos >= 0:
p = compose_pair(buf[(usize)starter_pos], buf[i])
if p != 0:
buf[(usize)starter_pos] = (u32)p
i += 1
else:
buf[out_len] = buf[i]
out_len += 1
i += 1
*pdst = dbuf_result(dbuf)
return (i32)out_len