dymokomi/luce-usd
Source of release 0.9.2
0.9.2 / src / usdc / writer / sections.lucb
## The structural sections, the table of contents and the bootstrap
## (CrateFile::_Write and its _Write* helpers), each section integer-
## compressed as files from 0.4.0 are. The path tree is the paths sorted in
## SdfPath order and walked depth first (_BuildCompressedPathDataRecursive):
## each entry's path index, element token (negated for a prim property) and
## jump (-2 leaf, -1 child only, 0 sibling only, n: sibling n entries on).
## A section's name and extent, for the table of contents.
struct Written:
var name: str
var start: u64
var size: u64
extend CrateWriter:
func write_sections() -> !:
var sections: Written[6] = ---
# TOKENS: count, then the NUL-separated texts compressed.
var at = self.tell()
try self.write_tokens()
sections[0] = Written(name = "TOKENS", start = at, size = self.tell() - at)
at = self.tell()
try self.put_u64((u64)self.strings.count)
for index in self.strings.view(): try self.put_u32(index)
sections[1] = Written(name = "STRINGS", start = at, size = self.tell() - at)
at = self.tell()
try self.write_fields()
sections[2] = Written(name = "FIELDS", start = at, size = self.tell() - at)
at = self.tell()
try self.put_u64((u64)self.field_sets.count)
try self.compressed_ints(u8[]((u8*)self.field_sets.items.data, self.field_sets.count * 4), self.field_sets.count, 4)
sections[3] = Written(name = "FIELDSETS", start = at, size = self.tell() - at)
at = self.tell()
try self.write_paths()
sections[4] = Written(name = "PATHS", start = at, size = self.tell() - at)
at = self.tell()
try self.write_specs()
sections[5] = Written(name = "SPECS", start = at, size = self.tell() - at)
# The table of contents, then the bootstrap in the reserved bytes.
let toc = self.tell()
try self.put_u64(6)
for section in sections:
var name: u8[16]
memory.copy(name, section.name.bytes, section.name.length)
try self.put_bytes(name)
try self.put_u64(section.start)
try self.put_u64(section.size)
let boot = self.out.items[self.start..<self.start + 88]
memory.copy(boot, "PXR-USDC".bytes, 8)
boot[8] = 0
boot[9] = self.minor
boot[10] = 0
for index in 11..<16: boot[index] = 0
memory.write[u64]((void*)&boot[16], toc)
for index in 24..<88: boot[index] = 0
func write_tokens() -> !:
var text = Growing[u8]()
defer text.close()
for id in self.tokens.view():
let token = self.names.text_of(id)
try put(&text, token)
try text.push(0)
try self.put_u64((u64)self.tokens.count)
try self.put_u64((u64)text.count)
let packed = try new u8[compression.compressed_bound(text.count)] --- in memory.heap
defer free(packed) in memory.heap
let size = try compression.compress(text.view(), packed)
try self.put_u64((u64)size)
try self.put_bytes(packed[..<size])
func write_fields() -> !:
let count = self.fields.count
try self.put_u64((u64)count)
let tokens = try new u8[count * 4] --- in memory.heap
defer free(tokens) in memory.heap
let reps = try new u8[count * 8] --- in memory.heap
defer free(reps) in memory.heap
for index in 0..<count:
memory.write[u32]((void*)&tokens[index * 4], self.fields.items[index].token)
memory.write[u64]((void*)&reps[index * 8], self.fields.items[index].rep)
try self.compressed_ints(tokens, count, 4)
let packed = try new u8[compression.compressed_bound(reps.length)] --- in memory.heap
defer free(packed) in memory.heap
let size = try compression.compress(reps, packed)
try self.put_u64((u64)size)
try self.put_bytes(packed[..<size])
func write_specs() -> !:
let count = self.specs.count
try self.put_u64((u64)count)
let column = try new u8[count * 4] --- in memory.heap
defer free(column) in memory.heap
for index in 0..<count: memory.write[u32]((void*)&column[index * 4], self.specs.items[index].path)
try self.compressed_ints(column, count, 4)
for index in 0..<count: memory.write[u32]((void*)&column[index * 4], self.specs.items[index].field_set)
try self.compressed_ints(column, count, 4)
for index in 0..<count: memory.write[u32]((void*)&column[index * 4], self.specs.items[index].kind)
try self.compressed_ints(column, count, 4)
## The path table's size, then the tree's three compressed columns.
func write_paths() -> !:
try self.put_u64((u64)self.paths.count)
# The tree holds every non-empty path, in SdfPath order.
var order = Growing[u32]()
defer order.close()
for index in 0..<self.paths.count:
if self.paths.items[index] != empty_path: try order.push((u32)index)
try self.sort_paths(&order)
let count = order.count
try self.put_u64((u64)count)
let indexes = try new u8[count * 4] --- in memory.heap
defer free(indexes) in memory.heap
let elements = try new u8[count * 4] --- in memory.heap
defer free(elements) in memory.heap
let jumps = try new u8[count * 4] --- in memory.heap
defer free(jumps) in memory.heap
var next: usize = 0
_ = try self.build_tree(order.view(), 0, &next, indexes, elements, jumps)
try self.compressed_ints(indexes, count, 4)
try self.compressed_ints(elements, count, 4)
try self.compressed_ints(jumps, count, 4)
## Emit the entries from `cur` on that share its parent, each followed
## by its subtree; the position after them.
func build_tree(order: const u32[], origin: usize, next: usize*, indexes: u8[], elements: u8[], jumps: u8[]) -> usize!:
var cur = origin
while cur < order.length:
let path = self.paths.items[(usize)order[cur]]
# The subtree of `cur` ends at the first path it is not a prefix of.
var subtree_end = cur + 1
while subtree_end < order.length and self.names.has_prefix(self.paths.items[(usize)order[subtree_end]], path): subtree_end += 1
let has_child = cur + 1 < subtree_end and self.names.parent(self.paths.items[(usize)order[cur + 1]]) == path
let has_sibling = subtree_end < order.length and self.names.parent(self.paths.items[(usize)order[subtree_end]]) == self.names.parent(path)
let this_index = *next
*next += 1
memory.write[u32]((void*)&indexes[this_index * 4], order[cur])
let property = self.names.kind(path) == PathKind.property
let token = (i32)try self.token(try self.element_token(path))
memory.write[i32]((void*)&elements[this_index * 4], -token if property else token)
var after = cur + 1
if has_child: after = try self.build_tree(order, cur + 1, next, indexes, elements, jumps)
var jump: i32 = -2
if has_sibling and has_child: jump = (i32)(*next - this_index)
elif has_sibling: jump = 0
elif has_child: jump = -1
memory.write[i32]((void*)&jumps[this_index * 4], jump)
if not has_sibling: return after
cur = after
return order.length
## Sort crate path indexes by SdfPath order.
func sort_paths(order: Growing[u32]*) -> !:
# Merge sort: path tables can be large.
let count = order.count
if count < 2: return
let scratch = try new u32[count] --- in memory.heap
defer free(scratch) in memory.heap
var width: usize = 1
var source = order.items[..<count]
var target = scratch
var in_order = true
while width < count:
var start: usize = 0
while start < count:
let middle = start + width if start + width < count else count
let end = start + width * 2 if start + width * 2 < count else count
var left = start
var right = middle
var at = start
while left < middle and right < end:
if self.names.path_less(self.paths.items[(usize)source[right]], self.paths.items[(usize)source[left]]):
target[at] = source[right]
right += 1
else:
target[at] = source[left]
left += 1
at += 1
while left < middle:
target[at] = source[left]
left += 1
at += 1
while right < end:
target[at] = source[right]
right += 1
at += 1
start = end
let swap = source
source = target
target = swap
in_order = not in_order
width *= 2
if not in_order: memory.copy(order.items[..<count], source, count)
## `count` integers of `width`, encoded and compressed: a u64 size, then
## the bytes (_WriteCompressedInts).
func compressed_ints(values: const u8[], count: usize, width: usize) -> !:
if count == 0:
try self.put_u64(0)
return
let encoded = try new u8[compression.encoded_bound(count, width)] --- in memory.heap
defer free(encoded) in memory.heap
let length = try compression.encode_integers(values, count, width, encoded)
let packed = try new u8[compression.compressed_bound(length)] --- in memory.heap
defer free(packed) in memory.heap
let size = try compression.compress(encoded[..<length], packed)
try self.put_u64((u64)size)
try self.put_bytes(packed[..<size])