1	# Input rows a spatial range reads. A window stores rows [first, first + rows)
2	# of every channel contiguously. The first row is a stride multiple, so packing
3	# a window is packing a shorter image with output rows shifted by first / stride.
4	import Base
5	import ./traversal_array.bend as Traversal
6	
7	type Band is Data:
8	  Band{first: U32,rows: U32}
9	
10	def first_row(+stride: U32,+padding: U32,+output_row: U32) -> U32:
11	  +top = (output_row * stride : U32)
12	  Bool.pick(U32,U32.is_le(padding,top),((top - padding) / stride * stride : U32),0)
13	
14	def end_row(+height: U32,+kernel: U32,+stride: U32,+padding: U32,+output_row: U32) -> U32:
15	  +bottom = (output_row * stride + kernel : U32)
16	  Bool.pick(U32,U32.is_le(bottom,padding),0,U32.min(height,(bottom - padding : U32)))
17	
18	# Rows read by output positions [offset, offset + span), kept inside the parent
19	# window [parent_first, parent_first + parent_rows). A band has at least one row,
20	# and its first row stays a stride multiple.
21	def band(+parent_first: U32,+parent_rows: U32,+height: U32,+kernel: U32,+stride: U32,+padding: U32,+output_width: U32,+offset: U32,+span: U32) -> Band:
22	  +parent_end = (parent_first + parent_rows : U32)
23	  +top = ((parent_end - 1) / stride * stride : U32)
24	  +first = U32.max(parent_first,U32.min(first_row(stride,padding,(offset / output_width : U32)),top))
25	  +last = end_row(height,kernel,stride,padding,((offset + span - 1) / output_width : U32))
26	  Band{first,(U32.min(parent_end,U32.max(last,(first + 1 : U32))) - first : U32)}
27	
28	# The checked facts that let a band stand in for its parent over a nonempty
29	# span: rows inside the parent window, a stride-aligned first row that no read
30	# needs above, an end no read needs below (or the image end), and room for the
31	# kernel. The comparisons avoid wrapped sums: rows are bounded by the parent end
32	# minus the first row. Pipelines copy only a band that passes; any other split
33	# keeps a clone of the parent.
34	def covers(+parent_first: U32,+parent_rows: U32,+height: U32,+kernel: U32,+stride: U32,+padding: U32,+output_width: U32,+offset: U32,+span: U32,
35	  +band: Band) -> Bool:
36	  Band{+first,+rows} = band
37	  +parent_end = (parent_first + parent_rows : U32)
38	  +top = (offset / output_width * stride : U32)
39	  +bottom = ((offset + span - 1) / output_width * stride + kernel : U32)
40	  +end = (first + rows : U32)
41	  U32.is_lt(0,span) && U32.is_lt(0,rows) && U32.is_le(parent_first,first) && U32.is_le(first,parent_end) &&
42	    U32.is_le(rows,(parent_end - first : U32)) && U32.is_zero((first % stride : U32)) &&
43	    (U32.is_zero(first) || U32.is_le((first + padding : U32),top)) &&
44	    (U32.is_eq(end,height) || U32.is_le(bottom,(end + padding : U32))) &&
45	    U32.is_le(kernel,(rows + padding + padding : U32))
46	
47	# A fork copies the left child's band only when rows are whole eight-position
48	# blocks and the band passes its coverage check; otherwise it clones the parent.
49	def copies_band(+parent_first: U32,+parent_rows: U32,+height: U32,+kernel: U32,+stride: U32,+padding: U32,+output_width: U32,+offset: U32,+span: U32,
50	  +band: Band) -> Bool:
51	  U32.is_zero((output_width % 8 : U32)) && covers(parent_first,parent_rows,height,kernel,stride,padding,output_width,offset,span,band)
52	
53	# Output positions rounded up to whole eight-position blocks.
54	def padded(positions: U32) -> U32:
55	  ((positions + 7) / 8 * 8 : U32)
56	
57	# Packing start of a window: output rows before its first row move the start
58	# back by first / stride rows. A window that starts at row 0 keeps the offset.
59	def start(+offset: U32,+stride: U32,+output_width: U32,+first: U32) -> U32:
60	  Bool.pick(U32,U32.is_zero(first),offset,(offset - first / stride * output_width : U32))
61	
62	# Channel c copies count values from c * source_stride + source_start to
63	# c * target_stride. Each plane is one contiguous copy.
64	def copy_planes(remaining: Nat,+channel: U32,+count: U32,+source_stride: U32,+source_start: U32,+target_stride: U32,
65	  owners: Array<F32> & Array<F32>) -> Array<F32> & Array<F32>:
66	  match remaining:
67	    case 0n: owners
68	    case 1n+rest:
69	      (source,target) = owners
70	      copy_planes(rest,(channel + 1 : U32),count,source_stride,source_start,target_stride,
71	        Traversal.copy(~F32,U32.to_nat(count),(channel * source_stride + source_start : U32),(channel * target_stride : U32),source,target))