dymokomi/luce-usd
Source of release 0.9.4
0.9.4 / src / usda / reader / arrays.lucb
## Numeric arrays, the bulk of geometry layers, without the general value
## machinery: a first pass finds the array's end and counts its elements,
## noting a split point every `chunk_bytes`; the elements are then parsed
## straight into their column, in parallel on luce-geocore's pool when the
## array is large. Anything unusual (comments, strings, inf and nan, a
## malformed element) sends the array back to the general parser, which
## reads it the same way and reports any error.
from luce_std import parallel
import strings
## Text per parallel chunk.
let chunk_bytes: usize = 262144
## Arrays of less text parse on this thread.
let parallel_bytes: usize = 524288
## The most chunks one array splits into.
let most_chunks: usize = 4096
## Where a chunk starts: its byte offset and first element.
struct Split:
var at: usize
var element: usize
## One parallel array parse.
struct ArrayParse:
var data: const u8[]
var kind: ValueKind
var size: usize
var splits: const Split[]
var end: usize
var out: u8[]
var failed: @bool
## Whether arrays of `kind` take the fast path.
func fast_kind(kind: ValueKind) -> bool:
match kind:
.uchar, .int, .uint, .int64, .uint64, .half, .float, .double, .time_code: return true
.vec2d, .vec3d, .vec4d, .vec2f, .vec3f, .vec4f, .vec2h, .vec3h, .vec4h, .vec2i, .vec3i, .vec4i: return true
.quatd, .quatf, .quath: return true
_: return false
## One parallel element count: per split, its elements (a tuple's '(' or
## a number's first character), and whether the text holds anything the
## fast path does not take.
struct ArrayCount:
var data: const u8[]
var tuples: bool
var splits: Split[]
var end: usize
var failed: @bool
extend Reader:
## The numeric array at the cursor (at its '['), or none to use the
## general parser (the cursor unchanged).
func fast_array(kind: ValueKind) -> Value?!:
if not fast_kind(kind): return none
let start = self.at
let data = self.data
# A numeric array holds no other ']': the first one ends it.
let found = memchr((const void*)&data[start], 93, data.length - start) else return none
let end = start + (usize)((u8*)found - (u8*)&data[start])
let tuples = components(kind) > 1
# Split points: every chunk_bytes, moved to the next element start.
var splits = Growing[Split]()
defer splits.close()
try splits.push(Split(at = start + 1, element = 0))
var at = start + 1 + chunk_bytes
while at < end and splits.count < most_chunks:
if tuples:
while at < end and data[at] != '(': at += 1
else:
while at < end and data[at] != ',': at += 1
if at < end: at += 1
if at >= end: break
try splits.push(Split(at = at, element = 0))
at += chunk_bytes
var count = ArrayCount(data = data, tuples = tuples, splits = splits.items[..<splits.count], end = end, failed = false)
if end - start < parallel_bytes:
for index in 0..<splits.count: count_chunk((void*)&count, index, 0)
else:
try parallel.for_each(splits.count, (void*)&count, count_chunk)
if count.failed.load(): return none
# Prefix sums turn each split's count into its first element.
var elements: usize = 0
for index in 0..<splits.count:
let here = splits.items[index].element
splits.items[index].element = elements
elements += here
let size = element_bytes(kind)
var column = try Column[u8].allocate(elements * size)
var job = ArrayParse(data = data, kind = kind, size = size, splits = splits.view(), end = end, out = column.span(), failed = false)
if end - start < parallel_bytes:
for index in 0..<splits.count: parse_chunk((void*)&job, index, 0)
else:
try parallel.for_each(splits.count, (void*)&job, parse_chunk)
if job.failed.load():
column.release()
return none
self.at = end + 1
return Value.of_array(kind, elements, column)
extern func memchr(text: const void*, byte: i32, count: usize) -> void*?
## Count split `index`'s elements into its `element`; flag text the fast
## path does not take.
func count_chunk(context: void*, index: usize, worker: usize):
let raw = context
let job = (ArrayCount*)raw
let first = job.splits[index].at
let stop = job.splits[index + 1].at if index + 1 < job.splits.length else job.end
let bytes = job.data.data
var elements: usize = 0
var previous: u8 = ','
for at in first..<stop:
let byte = bytes[at]
let numeric = (byte >= '0' and byte <= '9') or byte == '-' or byte == '+' or byte == '.' or byte == 'e' or byte == 'E'
if job.tuples:
if byte == '(': elements += 1
elif not numeric and byte != ')' and byte != ',' and byte != ' ' and byte != '\t' and byte != '\n' and byte != '\r':
job.failed.store(true)
return
else:
if numeric:
let before = (previous >= '0' and previous <= '9') or previous == '-' or previous == '+' or previous == '.' or previous == 'e' or previous == 'E'
if not before: elements += 1
elif byte != ',' and byte != ' ' and byte != '\t' and byte != '\n' and byte != '\r':
job.failed.store(true)
return
previous = byte
job.splits[index].element = elements
## Parse split `index`'s elements into the column; flag a failure.
func parse_chunk(context: void*, index: usize, worker: usize):
let raw = context
let job = (ArrayParse*)raw
let split = job.splits[index]
let stop = job.splits[index + 1].at if index + 1 < job.splits.length else job.end
let last = job.splits[index + 1].element if index + 1 < job.splits.length else (job.out.length // job.size)
var at = split.at
var element = split.element
let data = job.data
let components_count = components(job.kind)
let scalar = scalar_of(job.kind)
let scalar_size = element_bytes(scalar)
let quaternion = job.kind == ValueKind.quatd or job.kind == ValueKind.quatf or job.kind == ValueKind.quath
while element < last:
at = skip_blanks(data, at, stop)
let base = &job.out[element * job.size]
if components_count == 1:
at = number_into(data, at, stop, scalar, base)
if at == 0:
job.failed.store(true)
return
else:
if at >= stop or data[at] != '(':
job.failed.store(true)
return
at += 1
for index_in_tuple in 0..<components_count:
at = skip_blanks(data, at, stop)
let target = (index_in_tuple + 3) % 4 if quaternion else index_in_tuple
at = number_into(data, at, stop, scalar, base + target * scalar_size)
if at == 0:
job.failed.store(true)
return
# No line end before a comma (the grammar's ListOf).
at = skip_inline_blanks(data, at, stop)
if index_in_tuple + 1 < components_count:
if at >= stop or data[at] != ',':
job.failed.store(true)
return
at += 1
else:
at = skip_blanks(data, at, stop)
if at >= stop or data[at] != ')':
job.failed.store(true)
return
at += 1
element += 1
at = skip_inline_blanks(data, at, stop)
if at < stop and data[at] == ',': at += 1
elif element < last:
job.failed.store(true)
return
if skip_blanks(data, at, stop) != stop:
job.failed.store(true)
func skip_inline_blanks(data: const u8[], origin: usize, stop: usize) -> usize:
var at = origin
while at < stop and (data[at] == ' ' or data[at] == '\t'): at += 1
return at
func skip_blanks(data: const u8[], origin: usize, stop: usize) -> usize:
var at = origin
while at < stop and (data[at] == ' ' or data[at] == '\t' or data[at] == '\n' or data[at] == '\r'): at += 1
return at
## Parse the number at `at` into a scalar of `kind` at `out`; the offset
## after it, or 0 when the text is not a number the fast path takes.
## Numbers read as the general parser reads them: with '.', 'e' or 'E' as
## a double (std's scan_f64, then narrowed), otherwise as an integer.
func number_into(data: const u8[], origin: usize, stop: usize, kind: ValueKind, out: u8*) -> usize:
var at = origin
let negative = at < stop and data[at] == '-'
if negative: at += 1
let digits_start = at
var mantissa: u64 = 0
var digits: usize = 0
while at < stop and data[at] >= '0' and data[at] <= '9':
if digits == 19: return 0
mantissa = mantissa * 10 + (u64)(data[at] - '0')
if mantissa != 0: digits += 1
at += 1
if at < stop and (data[at] == '.' or data[at] == 'e' or data[at] == 'E'):
if at == digits_start and data[at] != '.': return 0
let (value, length) = strings.scan_f64(data[origin..<stop]) catch failure:
return 0
at = origin + length
if not ended(data, at, stop): return 0
store_real(kind, value, out) else return 0
return at
if at == digits_start or not ended(data, at, stop): return 0
# An integer: "-0" reads as the double -0.
if negative and mantissa == 0:
store_real(kind, -0.0, out) else return 0
return at
store_integer(kind, mantissa, negative, out) else return 0
return at
## Whether a number ending at `at` ends there: at the end or a delimiter.
func ended(data: const u8[], at: usize, stop: usize) -> bool:
return at == stop or data[at] == ',' or data[at] == ')' or data[at] == ' ' or data[at] == '\t' or data[at] == '\n' or data[at] == '\r' or data[at] == ']'
## Store a double as `kind` (floats narrow, integers truncate in range).
func store_real(kind: ValueKind, value: f64, out: u8*) -> unit?:
match kind:
.double, .time_code: memory.write[f64]((void*)out, value)
.float: memory.write[f32]((void*)out, (f32)value)
.half: memory.write[u16]((void*)out, ((f16)(f32)value).bits())
_:
if not (value == value) or value >= 9223372036854775808.0 or value < -9223372036854775808.0: return none
let whole = (i64)value
if whole < 0: return store_integer(kind, (u64)(-%whole), true, out)
return store_integer(kind, (u64)whole, false, out)
return ()
## Store an integer as `kind`, range-checked; none out of range.
func store_integer(kind: ValueKind, magnitude: u64, negative: bool, out: u8*) -> unit?:
if negative and magnitude > 9223372036854775808: return none
let signed: i64 = -%(i64)magnitude if negative else 0
match kind:
.double, .time_code:
memory.write[f64]((void*)out, -(f64)magnitude if negative else (f64)magnitude)
.float:
memory.write[f32]((void*)out, (f32)signed if negative else (f32)magnitude)
.half:
let value: f32 = (f32)signed if negative else (f32)magnitude
memory.write[u16]((void*)out, ((f16)value).bits())
.int:
if negative:
if magnitude > 2147483648: return none
memory.write[i32]((void*)out, (i32)signed)
else:
if magnitude > 2147483647: return none
memory.write[i32]((void*)out, (i32)magnitude)
.uint:
if negative and magnitude != 0: return none
if magnitude > 4294967295: return none
memory.write[u32]((void*)out, (u32)magnitude)
.uchar:
if negative and magnitude != 0: return none
if magnitude > 255: return none
memory.write[u8]((void*)out, (u8)magnitude)
.int64:
if negative: memory.write[i64]((void*)out, signed)
else:
if magnitude > 9223372036854775807: return none
memory.write[i64]((void*)out, (i64)magnitude)
.uint64:
if negative and magnitude != 0: return none
memory.write[u64]((void*)out, magnitude)
_: return none
return ()