urt-rs / docs /research /COLLISION_LOOP.md
nmarshall's picture
Recover entity clipping loop scheduling and sentinel normalization
f0c42d4
|
Raw History Blame Contribute Delete
6.99 kB

Entity-clipping count, scheduling and sentinel normalization

Static/bounded pass, 2026-10-11. Reproduce with python3 scripts/analyze_collision_loop.py; check with python3 scripts/test_collision_loop.py. Generated evidence verifies original and disassembly identities for both Linux ELF64 engines and records 72 entry slices, 20 normalization slices, 360 continuation slices and 70 scheduling compositions. This follows result-copy composition and candidate exclusions.

No original process, area query, entity lookup or collision callee executes. Scheduling compositions skip each candidate body and explicitly supply its resulting current status0. The report retains actual bounded instruction traces for counts through 32; counts 1023/1024 retain all visits, a trace digest/instruction count and the final continuation trace. Those large counts are supplied boundaries, not observed runtime workloads.

LOOP-001: entry count, status and parity gates

After SV_AreaEntities_r, the native code reads candidate count from stack +0x1088 and pass word from clip +0x74. The query setup statically initializes count zero, array pointer stack +0x30 and capacity 1024 at stack +0x108c. Query traversal/order/count production remains unexecuted.

The count gate uses a signed 32-bit testl/jle: counts <=0 return to cleanup. Positive counts next test current clip +0x3c (result status0); any nonzero value returns. These entry checks precede candidate processing, but follow pass/related normalization, so zero count does not prove that pass lookup is skipped.

With positive count and status0 zero, counter r13d becomes zero, array pointer r12 becomes its supplied base, and clip +0x30 is saved as an endpoint pointer. Testing bit zero of the low byte of count-1 selects:

Count First candidate lane Subsequent lane order if status0 stays zero
Positive odd Ordinary lane 0 0, 1, 0, 1, …, 0
Positive even Peeled lane 2 2, 0, 1, 0, …, 0

The 36 entry cases per engine cover raw count bits -1, 0, 1–4, 1023, 1024 and 0x80000000 with status0 0/1/4/0xffffffff. Signed-negative count patterns terminate; noncanonical status values are explicitly synthetic probes.

LOOP-002: three continuations and bounded scheduling invariant

Lane numbers match the preceding merge/copy report. The native continuation rules are:

Completed lane Counter and array advance Next decision
0, ordinary first lane Increment counter; if it is not equal to count, form second pointer = first pointer +4 Equality returns before reading status0; otherwise nonzero status0 returns, zero enters lane 1
1, paired second lane First pointer = second pointer +4; increment counter Nonzero status0 returns; zero enters lane 0
2, initial peel Increment counter; first pointer +=4 Nonzero status0 returns; zero enters lane 0

Only lane 0 has a count comparison, and it checks equality, not >=. Lanes 1 and 2 depend on the parity-established invariant. For positive odd counts, lane 0 completes the final candidate; for positive even counts, the peel advances once, then lane 0 completes the final candidate. Supplied status0 stops are checked after every processed candidate. These continuation slices do not read status4 or the fraction; they do not independently stop on those values.

Each engine has 180 isolated continuation cases: three lanes, counts 1–4, incoming counters 0–4 and status0 0/1/4. Deliberately inconsistent counter/count combinations demonstrate the absence of a >= guard; they do not establish that such combinations are reachable in the game. Tests independently check next lane, counter and pointer movement.

The 35 scheduling compositions per engine cover counts 1–8, 31, 32, 1023 and 1024. Each uses no status stop, a first-candidate stop and a final-candidate stop (duplicates removed for count 1). Every observed visit uses array byte offset 4*i exactly once and follows the parity sequence above; final counter equals visits. The two engines agree for all tested outputs. This proves the bounded scheduling composition under supplied count, unchanged count/counter and injected status assumptions; it does not recover area-query traversal, filtering/intersection results, callee mutation or runtime order.

LOOP-003: pass and related-word sentinel handling

Before the count gate, pass word 1023 skips SV_GentityNum and writes 0xffffffff to stack +0x2c. Other pass words request SV_GentityNum(pass) without an observed range check in this slice. The collector stops before that call and records the requested argument; even invalid-looking supplied values do not execute the lookup.

In separate post-lookup slices, supplied returned-object field +0x200 is copied to stack +0x2c. If that word equals 1023, an out-of-line branch overwrites it with 0xffffffff. Other tested words (0, 7, 1022, 0xffffffff) retain their bits. Thus both sentinel paths converge on a -1-shaped related word, but only pass==1023 bypasses lookup. Negative/invalid pass interpretation, legal entity range and returned-object validity remain open.

This supplies the previously isolated related input in candidate exclusions. It does not prove field +0x200's ownership semantics or establish every producer of pass/related values.

Address correspondence and evaluator scope

Site Linux dedicated Linux client
After area query 0x4155bb 0x47d53b
Pass lookup call / after call 0x4155d2 / 0x4155d7 0x47d552 / 0x47d557
Count gate 0x4155ed 0x47d56d
Lane 0 / 1 / 2 entries 0x41561e / 0x4157a9 / 0x415957 0x47d59e / 0x47d729 / 0x47d8d7
Lane 0 / 1 / 2 continuations 0x41578c / 0x415930 / 0x415acc 0x47d70c / 0x47d8b0 / 0x47da4c
Cleanup stop 0x415945 0x47d8c5

Sites are selected by unique instruction patterns and adjacent call identity, with ambiguous/changed patterns rejected. The byte-addressed evaluator adds signed TEST/CMP-to-JLE, low-byte TEST, simple signed-displacement LEA, ADDQ and optional final register capture. LEA and MOV preserve flags. Signed branches after unmodeled arithmetic flags fail closed. Indexed addressing, original calls, frame unwinding and exceptional float behavior remain unsupported. Existing composition report shape stays unchanged unless register capture is requested.

For Rust collision specifications, preserve stable candidate-order and first-stop semantics in fixtures, separate sentinel normalization from candidate exclusion, and establish a checked count/array/identity contract before choosing an iterator implementation. RE-300 remains open for that full contract, all candidate bodies and collision-result reachability, lookup address arithmetic/bounds, actual geometry and original-runtime/macOS/Windows/Linux32 equivalence. Broad collision and port milestones remain unchecked.