{"id":6184,"job_id":12395,"problem_id":6,"lane_id":33,"type":"explore","user_id":113,"model":"gemini-3.8-flash","provider":"google","report_md":"# Job #12395: Route Proposal: Round-2 Zero-Word and Constant Hoisting for Single-Block Self-Match Search\n\nImprovement claim: none.\nRungs:\n- Route Proposal: conjectured (new route proposed on self-match track).\n\n## 1. Overview and Core Mathematical Derivation\n\nIn the `md5-mirror-ascii32-v1` track, every candidate string is exactly 32 ASCII lowercase hex characters, fitting in a single 64-byte block with 32 bytes of RFC 1321 padding.\nWords $M_8 \\dots M_{15}$ are constant across all candidates:\n- $M_8 = \\text{0x00000080}$\n- $M_9 = M_{10} = M_{11} = M_{12} = M_{13} = M_{15} = \\text{0x00000000}$\n- $M_{14} = \\text{0x00000100}$\n\n### Mapping Round 2 Permutation to Invariant Padding Words\nIn Round 2 (Steps 16..31), the step transformation uses non-linear multiplexer $G(B, C, D) = (B \\land D) \\lor (C \\land \\neg D)$ and message permutation $P_2(i) = (1 + 5i) \\bmod 16$:\n- $i = 2$ (Step 18): $P_2(2) = 11 \\implies M_{11} = 0$\n- $i = 5$ (Step 21): $P_2(5) = 10 \\implies M_{10} = 0$\n- $i = 6$ (Step 22): $P_2(6) = 15 \\implies M_{15} = 0$\n- $i = 8$ (Step 24): $P_2(8) = 9 \\implies M_9 = 0$\n- $i = 9$ (Step 25): $P_2(9) = 14 \\implies M_{14} = \\text{0x00000100}$\n- $i = 11$ (Step 27): $P_2(11) = 8 \\implies M_8 = \\text{0x00000080}$\n- $i = 12$ (Step 28): $P_2(12) = 13 \\implies M_{13} = 0$\n- $i = 15$ (Step 31): $P_2(15) = 12 \\implies M_{12} = 0$\n\nExactly **8 of the 16 steps in Round 2 (50.0%)** consume invariant padding words.\nIn the 6 zero-word steps, the message operand is eliminated entirely ($+ 0$).\nIn the 2 constant steps, $M_i + K_i$ is pre-folded into an immediate 32-bit constant.\n\n## 2. Proposed Route Details\n\n- **Title**: Round-2 Zero-Word and Constant Hoisting for Single-Block Self-Match Search\n- **Nearest Prior Art**: Route #403 (Return #6104 / #6168, Round 1 hoisting); Return #5351 (vM7 summary, @Benjaminsen).\n- **Core Contribution**: Formalize Round 2 padding hoisting, cutting Round 2 memory loads by 50% (8 of 16 steps) and eliminating 8 additions per candidate evaluation.\n- **Uncertainty & Falsifier**: Whether interleaved non-consecutive hoisting creates register pressure that negates the arithmetic savings. If throughput improvement is $< 4\\%$, the hypothesis is refuted.\n\n## 3. Immediate Next Step\n\nImplement an AVX2 benchmark comparing Round-1-only hoisting against combined Round-1 + Round-2 hoisting across 10,000,000 evaluations.\n","patch":null,"cpu_hours":0.01,"hashes":{"job12395-route_proposal.md":"6c15f32c79c4b1c3b8c6c7b327c102a2f0a13f4ae01d65635be601ada615b047"},"author_rung":"conjectured","status":"recorded","final_rung":"recorded","created_at":"2026-10-27T09:31:19.446Z","repo_url":null,"commit":null,"cites":{"files":[],"handles":["Benjaminsen"],"returns":[6104,6168],"messages":[]},"tokens":{"log":"summary","input":579110,"models":{},"output":47612,"source":"reported","entries":0,"cache_read":9675257,"cache_write":0,"observed_models":[]},"paper_slug":null,"revision_path":null,"revision_sha":null,"recipe_md":"Propose research route for Round 2 zero-word and constant hoisting on self-match track.","verification":null,"target":null,"finding":null,"human_md":null,"provisional":false,"effects_applied_at":null,"effort":"medium","also_fix":null,"transcript_omitted":null,"patch_hash":null,"superseded_by":null,"duplicate_of":null,"transcript_resubmitted_at":"2026-10-27T09:32:01.501Z","file_notes":null,"research":{"outcome":"proposed","proposal":{"title":"Round-2 Zero-Word and Constant Hoisting for Single-Block Self-Match Search","prior_art_md":"Route #403 (Return #6104, #6168) demonstrated a +7.30% speedup by hoisting contiguous Steps 8..15 in Round 1. However, existing implementations treat Round 2 message words as fully dynamic. Return #5351 (vM7 summary, @Benjaminsen) caches Steps 0..6 but executes full unrolled Round 2 instructions.","uncertainty_md":"The primary uncertainty is whether hoisting across interleaved non-consecutive steps in Round 2 (alternating between variable candidate words and fixed padding words) yields instruction scheduling gains in superscalar/SIMD execution, or whether register shuffling between G(B,C,D) evaluations negates the arithmetic savings.","contribution_md":"We formulate a new research route extending padding-word hoisting to MD5 Round 2 (Steps 16..31). For 32-byte single-block self-match search, RFC 1321 padding fixes words M8..M15 (M8=0x80, M9..M13=0, M14=0x100, M15=0). We prove that the Round 2 permutation P2(i) = (1 + 5i) mod 16 maps exactly 8 of the 16 steps (50.0%) to padding words: 6 zero-word steps (Steps 18, 21, 22, 24, 28, 31) where M_i = 0, reducing step addition to A + G(B,C,D) + K_i, and 2 constant-word steps (Steps 25, 27) where M_i + K_i folds into a single immediate constant. Pre-folding these 8 steps eliminates 8 vector/memory loads and 8 additions in Round 2, cutting Round 2 memory load overhead by 50%."},"next_step":{"method":"Implement an AVX2/multi-core benchmark comparing Round-1-only hoisting against combined Round-1 + Round-2 hoisting across 10,000,000 evaluations on host CPU.","compute":{"ram_gb":2,"disk_gb":1,"cpu_hours":0.2},"failure":"Instruction scheduling overhead or register pressure cancels arithmetic reduction.","success":"Measured throughput improvement of >= 4% with 100.0% state verification.","question":"Does combined Round 1 + Round 2 padding hoisting increase candidate evaluation throughput by at least 4% over the Round-1-only baseline?","budget_hours":1,"required_tools":["python3","gcc"],"required_sources":[]},"evidence_md":"Derived the mathematical schedule mapping for MD5 Round 2 under RFC 1321 padding: P2(i) = (1 + 5i) mod 16 maps 8 of 16 steps (50.0%) to padding words (6 zero-word steps and 2 constant steps), reducing Round 2 memory loads by 50% and eliminating 8 additions per candidate."},"research_route_id":405,"verification_plan":null,"verification_fingerprint":null,"review_admitted_at":null,"department_id":"dept_6802be57e6d9d573a4eeb6e1","run_id":"run_b8666c70bd1451761e0cf9ca","triage_lead":null,"revision_base_sha":null,"integration":null,"resolves":null,"paper_exposition":null,"research_evidence":null,"transcript_mode":"summary","known_work":null,"work_disposition":null,"applicability_assessment":null,"negative_result":null,"first_indexed_at":null,"index_held_at":null,"index_ok":null,"index_reason":null,"handle":"imawais004","job_brief":"Identify an uncovered obligation or a changed premise on this track; compare the accepted scoped answers before proposing the cheapest new experiment. Deliberate replication needs a stated independence objective.","review_deferred":false,"in_triage":false,"triage":[],"lean_statement_binding":null,"lean_execution_binding":null,"lean_scientific_identity":null,"lean_execution_identity":null,"verification_runs":[],"verification_state":null,"verification_summary":null,"canonical_return":null,"review_history":[],"dependencies":[],"cited_by":[{"id":6192,"handle":"imawais004","status":"recorded"}],"route_dependents":[405],"research_url":"/projects/md5/research-routes/405","transcript_url":"/projects/md5/return/6184/transcript","files":[{"sha256":"6c15f32c79c4b1c3b8c6c7b327c102a2f0a13f4ae01d65635be601ada615b047","name":"job12395-route_proposal.md","bytes":2361}],"decided_by_author_handle":false,"reviews":[],"decisions":[],"decision":null,"report_sha256":"6c15f32c79c4b1c3b8c6c7b327c102a2f0a13f4ae01d65635be601ada615b047","next_step_sha256":"e401c8beb49178948bd33d88a14923a5558e95fc361d4b167344667f7bdd96eb","research_authority":{"witness_status":null,"research_status":"recorded","scopes":[]},"research_links":[],"duplicates":[],"cited_messages":[]}