`nx_vmotion.nx` source

↩ module page · 337 lines · 18292 B
1// nx_vmotion.nx -- sovereign BLOCK MOTION COMPENSATION: the core trick VP8/H.264 use to beat plain tile-delta.
2// When the camera pans or a head moves, EVERY tile's pixels change (tile-delta would resend them all), but the
3// content just SHIFTED -- so for each block we search the PREVIOUS frame for the best-matching block (minimum
4// SAD = sum of absolute differences) and send a tiny MOTION VECTOR (dx,dy) + a small residual instead of the
5// whole block. A pan that costs tile-delta ~100% of the frame costs motion-comp a few vectors + near-zero
6// residual. Pure integer buffer ops (no FPU, no syscalls) -> wasm-friendly sender-side encode. license_tier: ORIGINAL
7
8// F1111 ADAPTIVE MOTION-SEARCH RADIUS (rule-11: measured, not hardcoded). Motion search is 80.6pct of
9// P-frame encode (V8 profile of the shipped client, 416x320/emode673/qp22) and every call site searched
10// the full R=16 window = 1089 candidates/block. MEASURED on that client: a near-only window encodes the
11// same frame in 32.6ms vs 53.6ms at the SAME bytes, but a BARE small window costs ~2.5pct bytes at
12// matched PSNR on high-motion content (bgop qp sweep) -- so scan near first and EXTEND only for blocks
13// that missed. An extended block is candidate-for-candidate identical to the full-R search (see vm_scan),
14// so this can only ever cost TIME, never quality, relative to full R.
15// VC_ME_RNEAR=0 restores the exact pre-F1111 single-pass scan. VC_ME_EXTK MUST stay > 32 (see vm_search_q).
16const VC_ME_RNEAR: i64 = 8
17const VC_ME_EXTK: i64 = 94
18const VC_HEX_TRUST_DIV: i64 = 256   // hexagon trust bar divisor (see vm_search_hex); 256 == the far-ring trigger; 512 was measured and rejected
19// F1111 rung-2 (predictor priming) was built, proven bit-exact, MEASURED 0.999x, and REMOVED 2026-07-27:
20// the adaptive window + deadzone floor + capped SAD already exhaust the cap-tightening lever. Full
21// design, proof and numbers: nishifamily.com/video-engineering Act IV + the video lane memory file.
22
23// SAD of 16 bytes at a vs b -- THE F618 SIMD SEAM (flipped 2026-07-21). Native builds execute this
24// scalar body (the bit-exact reference); the wat backend (nx_wasm.nx) INTERCEPTS calls to it BY NAME
25// and inlines the fused wasm-SIMD sequence (v128.load x2, sub_sat_u both ways, or, extadd-pairwise,
26// lane sum) -- same integer by construction. Do not rename without updating the intercept.
27func v128_sad16(a: *u8, b: *u8) -> i64 {
  var s: i64 = 0
  var i: i64 = 0
  while i < 16 {
      let d: i64 = (a[i] as i64) - (b[i] as i64)
      if d < 0 { s = s - d } else { s = s + d }
      i = i + 1
  }
  return s
36}
37
38// SAD between cur's block at (cx,cy) and prev's block at (px,py), T x T, over W-stride 8bpp buffers.
39// Row bases hoisted out of the pixel loop (the skeleton compiler doesn't CSE the y*W multiplies;
40// this runs on EVERY block's skip decision, so the hoist pays frame-wide). Arithmetic unchanged.
41// F618: T==16 rows ride v128_sad16 (one row = one 16-byte SAD; addition is associative so the row
42// total is the same integer); other T keep the exact scalar loop.
43func vm_sad(cur: *u8, prev: *u8, W: i64, cx: i64, cy: i64, px: i64, py: i64, T: i64) -> i64 {
  var s: i64 = 0
  var yy: i64 = 0
  if T == 16 {
      while yy < 16 {
          let crow: i64 = (cy + yy) * W + cx
          let prow: i64 = (py + yy) * W + px
          let ca: i64 = (cur as i64) + crow
          let pa: i64 = (prev as i64) + prow
          let cp: *u8 = ca as *u8
          let pp: *u8 = pa as *u8
          let d: i64 = v128_sad16(cp, pp)
          s = s + d
          yy = yy + 1
      }
      return s
  }
  while yy < T {
      let crow: i64 = (cy + yy) * W + cx
      let prow: i64 = (py + yy) * W + px
      var xx: i64 = 0
      while xx < T {
          let d: i64 = (cur[crow + xx] as i64) - (prev[prow + xx] as i64)
          if d < 0 { s = s - d } else { s = s + d }
          xx = xx + 1
      }
      yy = yy + 1
  }
  return s
72}
73// vm_sad with a CAP: abort row-granularly once the partial sum reaches cap. SAD only grows, so an
74// aborted candidate returns a partial s >= cap and the caller's strict (s < best) verdict is IDENTICAL
75// to the full computation -- any true winner (< cap) never aborts. Argmin (and thus the bitstream)
76// stays BIT-EXACT while losers stop early (the 2026-07-03 speed bench measured the un-exited full
77// search at 165ms/frame = the realtime blocker this closes down).
78func vm_sad_capped(cur: *u8, prev: *u8, W: i64, cx: i64, cy: i64, px: i64, py: i64, T: i64, cap: i64) -> i64 {
  var s: i64 = 0
  var yy: i64 = 0
  if T == 16 {
      while yy < 16 {
          let crow: i64 = (cy + yy) * W + cx
          let prow: i64 = (py + yy) * W + px
          let ca: i64 = (cur as i64) + crow
          let pa: i64 = (prev as i64) + prow
          let cp: *u8 = ca as *u8
          let pp: *u8 = pa as *u8
          let d: i64 = v128_sad16(cp, pp)
          s = s + d
          if s >= cap { return s }
          yy = yy + 1
      }
      return s
  }
  while yy < T {
      let crow: i64 = (cy + yy) * W + cx
      let prow: i64 = (py + yy) * W + px
      var xx: i64 = 0
      while xx < T {
          let d: i64 = (cur[crow + xx] as i64) - (prev[prow + xx] as i64)
          if d < 0 { s = s - d } else { s = s + d }
          xx = xx + 1
      }
      if s >= cap { return s }
      yy = yy + 1
  }
  return s
109}
110// evaluate one candidate (dx,dy); updates best/bdx/bdy via the out array b[0]=best b[1]=bdx b[2]=bdy.
111func vm_try(cur: *u8, prev: *u8, W: i64, H: i64, cx: i64, cy: i64, T: i64, dx: i64, dy: i64, b: *i64) -> i64 {
  let px: i64 = cx + dx
  let py: i64 = cy + dy
  if px >= 0 { if py >= 0 { if px + T <= W { if py + T <= H {
      let s: i64 = vm_sad_capped(cur, prev, W, cx, cy, px, py, T, b[0])
      if s < b[0] { b[0] = s; b[1] = dx; b[2] = dy }
  } } } }
  return 0
119}
120// full-coverage search of the [-R,R] window, CENTER-FIRST ring order: radius 0, then each square ring
121// outward. Real video motion is small, so the near-optimal candidate lands FIRST and the capped SAD
122// aborts every far loser after a row or two -- the full window is still 100% covered (no candidates
123// dropped; this is exact search, only reordered). Tie-break change vs the old raster order: equal-SAD
124// candidates now resolve to the SMALLEST radius = the cheapest MV to code (strictly better, and the
125// decoder is agnostic -- any coded MV reconstructs exactly). Writes mv[0]=dx mv[1]=dy; returns best SAD.
126// THE ONE ring-scan body (F1111 DRY: this was duplicated verbatim into vm_search and vm_search_q; a
127// third copy for any future variant was the trap). vfloor==0 disables the deadzone early-exit entirely
128// (vm_search semantics, exact-original); vfloor>0 arms it (vm_search_q semantics). Callers own b[] init
129// and the mv[] writeback, so both entry points keep their exact published contracts.
130// r0 = FIRST ring to enumerate. r0==0 also evaluates the (0,0) centre candidate. A scan of rings 0..A
131// followed by a scan of rings A+1..B visits EXACTLY the candidates of a single 0..B scan, in EXACTLY the
132// same order, against the same monotonically-tightening b[] -- so a two-pass (adaptive) search is
133// candidate-for-candidate IDENTICAL to the one-pass search it extends to. That identity is what makes
134// vm_search_q's adaptive form safe: extending costs quality NOTHING, only the time it would have cost.
135func vm_scan(cur: *u8, prev: *u8, W: i64, H: i64, cx: i64, cy: i64, T: i64, R: i64, b: *i64, vfloor: i64, r0: i64) -> i64 {
  if r0 == 0 { vm_try(cur, prev, W, H, cx, cy, T, 0, 0, b) }
  var r: i64 = r0
  if r < 1 { r = 1 }
  while r <= R {
      // rings 0-2 always search fully; the floor-exit prunes only the far rings (see vm_search_q note).
      var prune: i64 = 0
      if vfloor > 0 { if r > 2 { if b[0] < vfloor { prune = 1 } } }
      if prune == 1 { r = R + 1 } else {
          // top + bottom rows of the ring (full width)
          var dx: i64 = 0 - r
          while dx <= r {
              vm_try(cur, prev, W, H, cx, cy, T, dx, 0 - r, b)
              vm_try(cur, prev, W, H, cx, cy, T, dx, r, b)
              dx = dx + 1
          }
          // left + right columns (excluding the corners already done)
          var dy: i64 = 0 - r + 1
          while dy <= r - 1 {
              vm_try(cur, prev, W, H, cx, cy, T, 0 - r, dy, b)
              vm_try(cur, prev, W, H, cx, cy, T, r, dy, b)
              dy = dy + 1
          }
          r = r + 1
      }
  }
  return b[0]
162}
163// scr3 (2026-07-29 root fix): the 3-slot best-box [sad,dx,dy] was a sys_mmap(32) PER SEARCH CALL --
164// per MB, on the hottest path. In the wasm tier sys_mmap was the 0-stub (silent address-0 aliasing,
165// seq234 class); natively it was an unmunmapped map per MB (the map-count crash class). The caller
166// provides 3 i64 of scratch (blk is dead during search in the codec; gates hoist ONE mmap).
167func vm_search(cur: *u8, prev: *u8, W: i64, H: i64, bx: i64, by: i64, T: i64, R: i64, mv: *i64, scr3: *i64) -> i64 {
  let cx: i64 = bx * T
  let cy: i64 = by * T
  let b: *i64 = scr3
  b[0] = 2147483647
  b[1] = 0
  b[2] = 0
  vm_scan(cur, prev, W, H, cx, cy, T, R, b, 0, 0)
  mv[0] = b[1]
  mv[1] = b[2]
  return b[0]
178}
179// DEADZONE-FLOOR EARLY-EXIT variant (825, encoder-only; the RICH/rct8 path's searcher -- vm_search above keeps
180// the exact-original semantics for the legacy stream). Once the best SAD is under the QUANT DEADZONE scale
181// (T*T*qp/8 ~= a residual that quantizes to ~nothing), no candidate can improve the CODED outcome -- stop
182// enumerating rings. On call content the true MV lands in ring 0-2 (center-first), cutting the 289-candidate
183// walk to ~10-25 for the coherent majority. First try (qp-blind T*T*2) MEASURED +2.02% BD (bus +5.17: at low
184// qp a sub-floor better match still pays) -> qp-scaled floor keeps the noise-fps win AND the low-qp quality.
185func vm_search_q(cur: *u8, prev: *u8, W: i64, H: i64, bx: i64, by: i64, T: i64, R: i64, mv: *i64, qp: i64, scr3: *i64) -> i64 {
  let cx: i64 = bx * T
  let cy: i64 = by * T
  let b: *i64 = scr3
  b[0] = 2147483647
  b[1] = 0
  b[2] = 0
  // rings 0-2 always search fully (25 candidates -- the coherent-motion near window; exiting inside it
  // measured +2.0% BD on real-motion seqs); the floor-exit prunes only the far rings (the 264-candidate
  // tail that exists for rare large motion).
  let vm_floor: i64 = (T * T * qp) / 8
  // F1111: near window first, far rings only for blocks that did not find a match inside the measured
  // translation band. VC_ME_RNEAR==0 restores the exact single-pass R scan (the pre-F1111 behaviour).
  var rn: i64 = VC_ME_RNEAR
  if rn <= 0 { rn = R }
  if rn > R { rn = R }
  vm_scan(cur, prev, W, H, cx, cy, T, rn, b, vm_floor, 0)
  // ⚠the extend threshold MUST stay above vm_floor (VC_ME_EXTK > 32), else a block the deadzone prune
  // already accepted could re-enter the far rings that a single-pass scan would have skipped, and the
  // two-pass/one-pass equivalence below would not hold.
  let ext_thresh: i64 = (T * T * qp * VC_ME_EXTK) / 256
  if rn < R { if b[0] >= ext_thresh { vm_scan(cur, prev, W, H, cx, cy, T, R, b, vm_floor, rn + 1) } }
  mv[0] = b[1]
  mv[1] = b[2]
  return b[0]
210}
211// HEXAGON SEARCH (encoder-only, selected by emode bit15 VC_EMODE_HEXME in the block coder, 2026-09-02). The exhaustive
212// centre-first ring scan above costs 289 (near window) to 1089 candidates per MB; MEASURED by nx_vcodec_stage_bench on
213// foreman at the live point the integer search was 37 percent of the frame at ~35 us per MB. The field's RTC encoders
214// (x264 hex/umh, libvpx hex, SVT-AV1 HME) walk a PATTERN instead: a 6-point large hexagon (radius 2) re-centred on its
215// argmin until the centre holds, then a 4-point small diamond (radius 1) -- typically 15-40 candidates. Same vm_try
216// (frame bounds + capped SAD, so no out-of-frame read) and the same qp-scaled deadzone floor exit as vm_search_q; the
217// step count is bounded so |mv| never exceeds R. A pattern search CAN miss a distant minimum the exhaustive scan finds,
218// so its cost is BD-rate MEASURED (nx_vcodec_stage_bench bd -> nx_bd_calc), never claimed exact.
219func vm_search_hex(cur: *u8, prev: *u8, W: i64, H: i64, bx: i64, by: i64, T: i64, R: i64, mv: *i64, qp: i64, scr3: *i64) -> i64 {
  let cx: i64 = bx * T
  let cy: i64 = by * T
  let b: *i64 = scr3
  b[0] = 2147483647
  b[1] = 0
  b[2] = 0
  let vm_floor: i64 = (T * T * qp) / 8
  vm_try(cur, prev, W, H, cx, cy, T, 0, 0, b)
  // SPATIAL PREDICTOR SEED (MEASURED 2026-09-02: the pattern from (0,0) alone cost +7.9 percent BD on foreman even with
  // the exhaustive fallback -- coherent medium motion where the hexagon settles for a match under the bar). The caller
  // hands the previous macroblock's vector in scr3[3..4] (raster order: the left neighbour, or the last block of the row
  // above); the hexagon starts from the better of (0,0) and that predictor. |predictor| is clamped to R.
  var pmx: i64 = scr3[3]
  var pmy: i64 = scr3[4]
  if pmx > R { pmx = R }
  if pmx < 0 - R { pmx = 0 - R }
  if pmy > R { pmy = R }
  if pmy < 0 - R { pmy = 0 - R }
  if pmx != 0 { vm_try(cur, prev, W, H, cx, cy, T, pmx, pmy, b) } else { if pmy != 0 { vm_try(cur, prev, W, H, cx, cy, T, pmx, pmy, b) } }
  var cxm: i64 = b[1]
  var cym: i64 = b[2]
  var steps: i64 = 0
  let max_steps: i64 = (R - 1) / 2
  var go: i64 = 1
  while go == 1 {
      if b[0] < vm_floor { go = 0 } else {
          vm_try(cur, prev, W, H, cx, cy, T, cxm + 2, cym, b)
          vm_try(cur, prev, W, H, cx, cy, T, cxm - 2, cym, b)
          vm_try(cur, prev, W, H, cx, cy, T, cxm + 1, cym + 2, b)
          vm_try(cur, prev, W, H, cx, cy, T, cxm - 1, cym + 2, b)
          vm_try(cur, prev, W, H, cx, cy, T, cxm + 1, cym - 2, b)
          vm_try(cur, prev, W, H, cx, cy, T, cxm - 1, cym - 2, b)
          if b[1] == cxm { if b[2] == cym { go = 0 } }
          cxm = b[1]
          cym = b[2]
          steps = steps + 1
          if steps >= max_steps { go = 0 }
      }
  }
  vm_try(cur, prev, W, H, cx, cy, T, cxm + 1, cym, b)
  vm_try(cur, prev, W, H, cx, cy, T, cxm - 1, cym, b)
  vm_try(cur, prev, W, H, cx, cy, T, cxm, cym + 1, b)
  vm_try(cur, prev, W, H, cx, cy, T, cxm, cym - 1, b)
  // EXHAUSTIVE FALLBACK (MEASURED 2026-09-02): the bare pattern cost +10.4 percent BD on foreman and +22.4 on bus --
  // a hexagon walked from (0,0) parks in a local minimum on real translation. The estate already OWNS the "this match is
  // not good enough" bar: vm_search_q's far-ring extension threshold (T*T*qp*VC_ME_EXTK/256). A pattern result still
  // above it takes the SAME two-pass scan vm_search_q runs (near window, then far rings if still above the bar),
  // seeded with the pattern's best so the capped SAD aborts every loser early. Easy blocks (the static majority)
  // never enter the scan; hard blocks keep the exhaustive answer.
  // TRUST BAR -- MEASURED 2026-09-02 (nx_vcodec_stage_bench bd, 48f CIF, q 8/16/24/32/44, BD vs the exhaustive anchor):
  //   /256 (bar == the far-ring trigger): akiyo +0.8  foreman +3.5  bus 0.0  mobile +0.2 percent BD; encode -21..-29 percent
  //   /512 (pattern must be twice as good):  akiyo +0.3  foreman +1.5  bus -0.6  mobile  0.0;          encode win GONE on bus/mobile
  // Neither meets the pre-declared +1.0 percent bound on foreman, so VC_EMODE_HEXME is NOT composed into the live emode;
  // the /256 bar is kept because it is the variant with the real speed win. Halving the bar buys BD by sending most
  // moving-content blocks through BOTH searches, which is why the time win disappears. Next mechanism, not next number:
  // a second predictor (top neighbour, needs an MV row buffer) or a merged pattern+ring scan that shares the SAD work.
  let ext_thresh: i64 = (T * T * qp * VC_ME_EXTK) / VC_HEX_TRUST_DIV
  if b[0] >= ext_thresh {
      var rn: i64 = VC_ME_RNEAR
      if rn <= 0 { rn = R }
      if rn > R { rn = R }
      vm_scan(cur, prev, W, H, cx, cy, T, rn, b, vm_floor, 1)
      if rn < R { if b[0] >= ext_thresh { vm_scan(cur, prev, W, H, cx, cy, T, R, b, vm_floor, rn + 1) } }
  }
  mv[0] = b[1]
  mv[1] = b[2]
  return b[0]
287}
288// the residual SAD with NO motion (dx=dy=0) -- i.e. what plain tile-delta "sees" as the block's change.
289func vm_sad_zero(cur: *u8, prev: *u8, W: i64, bx: i64, by: i64, T: i64) -> i64 {
  let cx: i64 = bx * T
  let cy: i64 = by * T
  return vm_sad(cur, prev, W, cx, cy, cx, cy, T)
293}
294// reconstruct cur's block into dst from prev at the motion vector + the residual (dst = predicted + residual).
295// residual[k] = cur - predicted (signed, i16-range). For SAD==0 the residual is all-zero and predicted == cur.
296func vm_reconstruct(dst: *u8, prev: *u8, residual: *i64, W: i64, bx: i64, by: i64, T: i64, mv: *i64) -> i64 {
  let cx: i64 = bx * T
  let cy: i64 = by * T
  let px: i64 = cx + mv[0]
  let py: i64 = cy + mv[1]
  var yy: i64 = 0
  while yy < T {
      var xx: i64 = 0
      while xx < T {
          let pred: i64 = prev[(py+yy)*W + (px+xx)] as i64
          var v: i64 = pred + residual[yy*T + xx]
          if v < 0 { v = 0 }
          if v > 255 { v = 255 }
          dst[(cy+yy)*W + (cx+xx)] = v as u8
          xx = xx + 1
      }
      yy = yy + 1
  }
  return 0
315}
316// compute the residual (cur - predicted) for a block at MV into residual[T*T]; returns its SAD.
317func vm_residual(cur: *u8, prev: *u8, residual: *i64, W: i64, bx: i64, by: i64, T: i64, mv: *i64) -> i64 {
  let cx: i64 = bx * T
  let cy: i64 = by * T
  let px: i64 = cx + mv[0]
  let py: i64 = cy + mv[1]
  var s: i64 = 0
  var yy: i64 = 0
  while yy < T {
      var xx: i64 = 0
      while xx < T {
          let c: i64 = cur[(cy+yy)*W + (cx+xx)] as i64
          let p: i64 = prev[(py+yy)*W + (px+xx)] as i64
          let d: i64 = c - p
          residual[yy*T + xx] = d
          if d < 0 { s = s - d } else { s = s + d }
          xx = xx + 1
      }
      yy = yy + 1
  }
  return s
337}
nx_vmotion.nx source

`nx_vmotion.nx` source
