diff options
Diffstat (limited to 'src/Kind.zig')
| -rw-r--r-- | src/Kind.zig | 373 |
1 files changed, 372 insertions, 1 deletions
diff --git a/src/Kind.zig b/src/Kind.zig index 055b17f9..04db2579 100644 --- a/src/Kind.zig +++ b/src/Kind.zig @@ -199,7 +199,7 @@ pub const Slot = struct { /// Collapse Del. tail: Buf(160) = .{}, /// A replica's frame of it, as the authority painted it. - shadow: ?*@import("term/screen_state.zig").Shadow = null, + shadow: ?*Shadow = null, /// Debug: the kind's allocations, which paint must leave as they are /// (the list the page allocator's: a region's first is slow in Debug). used: if (checked) std.ArrayList([]u8) else void = if (checked) .empty else {}, @@ -1186,6 +1186,283 @@ pub fn Buf(comptime n: usize) type { }; } +// ---- a pane of a kind, as a Shadow (architecture ยง16.5) ---- +// +// A replica's core has no code for a library's kind: such a pane is drawn +// from the authority's frame of it, painted at the size the peer's view +// gives it. A frame crosses as its size and the pointer it asks for, each +// row by its hash (with its cells when the peer's row there is another), +// then each placement by its key; its raster's pixels cross before it, as +// strips of rows (`raster` messages, `encodeStrip`), those over its `src` +// the peer was not sent with the frame before. The stream is ordered and +// loses nothing, so what the authority last sent a peer is what the peer +// holds, but for a raster its `Blobs` let go, which it asks for again. + +const ShadowCell = c.pa_cell; +const Place = c.pa_placement; +/// A row's or a frame's content address, as a terminal's rows have one. +const Hash = u64; + +/// A replica's frame of a pane of a kind: what Kind.draw draws for it, its +/// placements' pixels its peer's `Blobs`. +pub const Shadow = struct { + gpu: []const u8 = &.{}, + cols: u16 = 0, + rows: u16 = 0, + cells: []ShadowCell = &.{}, + hashes: []Hash = &.{}, + places: std.ArrayList(Place) = .empty, + pointer: u8 = 0, + /// The raster it last asked for again (`apply`'s): asked once. + wanted: u64 = 0, + + pub fn deinit(sh: *Shadow, gpa: std.mem.Allocator) void { + gpa.free(sh.gpu); + gpa.free(sh.cells); + gpa.free(sh.hashes); + sh.places.deinit(gpa); + gpa.destroy(sh); + } + + /// A frame message applied (`encodeShadow`'s), of the pane `serial`, + /// each placement's pixels from `blobs`: one it lacks is not shown, and + /// its name is what to ask for (once), else 0. + pub fn apply(sh: *Shadow, gpa: std.mem.Allocator, bytes: []const u8, serial: u32, blobs: *Blobs) !u64 { + var r: std.Io.Reader = .fixed(bytes); + const cols = try r.takeInt(u16, .little); + const rows = try r.takeInt(u16, .little); + if (cols != sh.cols or rows != sh.rows) { + gpa.free(sh.cells); + gpa.free(sh.hashes); + sh.cells = try gpa.alloc(ShadowCell, @as(usize, cols) * rows); + sh.hashes = try gpa.alloc(Hash, rows); + @memset(std.mem.sliceAsBytes(sh.cells), 0); + @memset(sh.hashes, 0); + sh.cols = cols; + sh.rows = rows; + } + sh.pointer = try r.takeByte(); + for (0..rows) |y| { + sh.hashes[y] = try r.takeInt(u64, .little); + if (try r.takeByte() == 0) continue; + for (sh.cells[y * cols ..][0..cols]) |*cell| { + @memcpy(&cell.text, try r.take(8)); + cell.fg = try r.takeInt(u32, .little); + cell.bg = try r.takeInt(u32, .little); + cell.attrs = try r.takeInt(u16, .little); + cell.len = try r.takeByte(); + cell.flags = try r.takeByte(); + } + } + sh.places.clearRetainingCapacity(); + var lacking: u64 = 0; + for (0..try r.takeByte()) |_| { + var pl = std.mem.zeroes(Place); + pl.w = try r.takeInt(u32, .little); + pl.h = try r.takeInt(u32, .little); + inline for (.{ &pl.src.x, &pl.src.y, &pl.src.w, &pl.src.h, &pl.at.x, &pl.at.y, &pl.at.w, &pl.at.h }) |f| f.* = try r.takeInt(u32, .little); + inline for (.{ &pl.dst.x, &pl.dst.y, &pl.dst.w, &pl.dst.h }) |f| f.* = try r.takeInt(u16, .little); + pl.key = try r.takeInt(u64, .little); + const name = std.hash.Wyhash.hash(serial, std.mem.asBytes(&pl.key)); + pl.rgba = (blobs.shows(name, &pl) orelse { + lacking = name; + continue; + }).ptr; + try sh.places.append(gpa, pl); + } + // Older frames have no optional GPU tail. + const n = if (r.seek < r.end) try r.takeInt(u32, .little) else 0; + if (n > 4 << 20) return error.BadGpuFrame; + const gpu = try gpa.dupe(u8, try r.take(n)); + gpa.free(sh.gpu); + sh.gpu = gpu; + if (lacking == sh.wanted) return 0; + sh.wanted = lacking; + return lacking; + } +}; + +/// A raster's strip: at most this many bytes of its rows (17.3). +pub const strip_max = 4 << 20; + +/// How many of a `w`-pixel raster's rows a strip holds. +pub fn stripRows(w: u32) u32 { + return @max(1, strip_max / (@as(u32, @max(w, 1)) * 4)); +} + +/// The strips of `pl`'s raster over its `src` rows, a bit each. +fn stripsOver(pl: *const Place) u64 { + const per = stripRows(pl.w); + const lo = @min(pl.src.y, pl.h) / per; + const hi = (@min(pl.src.y +| pl.src.h, pl.h) + per - 1) / per; + var bits: u64 = 0; + for (lo..@min(hi, 64)) |i| bits |= @as(u64, 1) << @intCast(i); + return bits; +} + +/// Strip `i` of `pl`'s raster, a `raster` message's payload: its key, its +/// size, its first row, and its rows' bytes. +pub fn encodeStrip(pl: *const Place, i: u32, w: *std.Io.Writer) !void { + const y0 = i * stripRows(pl.w); + const row = @as(usize, pl.w) * 4; + try w.writeInt(u64, pl.key, .little); + try w.writeInt(u32, pl.w, .little); + try w.writeInt(u32, pl.h, .little); + try w.writeInt(u32, y0, .little); + try w.writeAll(pl.rgba[y0 * row .. @min(pl.h, y0 + stripRows(pl.w)) * row]); +} + +/// A peer's rasters of the panes of a kind, made from their strips by +/// name (the key with its pane's serial), kept to `max` bytes by least +/// recent use but for those a Shadow shows (17.3). +pub const Blobs = struct { + list: std.ArrayList(Blob) = .empty, + clock: u64 = 0, + + pub const max = 64 << 20; + const Blob = struct { name: u64, w: u32, h: u32, bytes: []u8, have: u64 = 0, used: u64 = 0 }; + + pub fn deinit(b: *Blobs, gpa: std.mem.Allocator) void { + for (b.list.items) |x| gpa.free(x.bytes); + b.list.deinit(gpa); + } + + /// A `raster` message's payload (`encodeStrip`'s) into raster `name`, + /// made at its first strip; `shown`, the pixels Shadows show now. + pub fn strip(b: *Blobs, gpa: std.mem.Allocator, name: u64, payload: []const u8, shown: []const [*]const u8) !void { + var r: std.Io.Reader = .fixed(payload); + _ = try r.takeInt(u64, .little); + const w = try r.takeInt(u32, .little); + const h = try r.takeInt(u32, .little); + const y0 = try r.takeInt(u32, .little); + const rows = r.buffered(); + const row = @as(usize, w) * 4; + if (row == 0 or rows.len % row != 0 or y0 % stripRows(w) != 0 or y0 + rows.len / row > h) return error.BadShadow; + const x = for (b.list.items) |*x| { + if (x.name == name) break x; + } else made: { + var held: usize = row * h; + for (b.list.items) |x| held += x.bytes.len; + while (held > max) { + var old: ?usize = null; + for (b.list.items, 0..) |x, i| if (std.mem.indexOfScalar([*]const u8, shown, x.bytes.ptr) == null and (old == null or x.used < b.list.items[old.?].used)) { + old = i; + }; + const i = old orelse break; + held -= b.list.items[i].bytes.len; + gpa.free(b.list.swapRemove(i).bytes); + } + const bytes = try gpa.alloc(u8, row * h); + errdefer gpa.free(bytes); + try b.list.append(gpa, .{ .name = name, .w = w, .h = h, .bytes = bytes }); + break :made &b.list.items[b.list.items.len - 1]; + }; + if (x.w != w or x.h != h) return error.BadShadow; + @memcpy(x.bytes[y0 * row ..][0..rows.len], rows); + x.have |= @as(u64, 1) << @intCast(@min(63, y0 / stripRows(w))); + b.clock += 1; + x.used = b.clock; + } + + /// Raster `name`'s pixels when it has every strip `pl` shows. + fn shows(b: *Blobs, name: u64, pl: *const Place) ?[]u8 { + for (b.list.items) |*x| if (x.name == name and x.w == pl.w and x.h == pl.h and stripsOver(pl) & ~x.have == 0) { + b.clock += 1; + x.used = b.clock; + return x.bytes; + }; + return null; + } +}; + +/// What the authority last sent one peer of a pane of a kind: its rows' +/// hashes, its placements, and which strips of each raster it holds. +pub const ShadowSent = struct { + serial: u32 = 0, + cols: u16 = 0, + hashes: std.ArrayList(Hash) = .empty, + places: Hash = 0, + keys: std.ArrayList(struct { key: u64, have: u64 }) = .empty, + + pub fn deinit(s: *ShadowSent, gpa: std.mem.Allocator) void { + s.hashes.deinit(gpa); + s.keys.deinit(gpa); + s.* = .{}; + } + + /// The strips of `pl`'s raster over its `src` the peer lacks (a bit + /// each, `encodeStrip`'s `i`), counted sent now. + pub fn owed(s: *ShadowSent, gpa: std.mem.Allocator, pl: *const Place) !u64 { + const need = stripsOver(pl); + for (s.keys.items) |*k| if (k.key == pl.key) { + defer k.have |= need; + return need & ~k.have; + }; + try s.keys.append(gpa, .{ .key = pl.key, .have = need }); + return need; + } +}; + +/// Frame `f` of a pane (the pointer its paint asked for) for a peer that +/// was last sent `sent`: false, and nothing written, when it holds this +/// frame already. Its placements cross by key, their pixels as strips +/// before it (`ShadowSent.owed`), so a frame is small whatever it shows. +pub fn encodeShadow(gpa: std.mem.Allocator, sent: *ShadowSent, f: *const Frame, pointer: u8, w: *std.Io.Writer) !bool { + var hashes: std.ArrayList(Hash) = .empty; + errdefer hashes.deinit(gpa); + for (0..f.rows) |y| try hashes.append(gpa, std.hash.Wyhash.hash(0, std.mem.sliceAsBytes(f.cells[y * f.cols ..][0..f.cols]))); + const places = f.places[0..@min(f.n, 64)]; + var ph = std.hash.Wyhash.init(pointer); + for (places) |*pl| inline for (.{ pl.w, pl.h, pl.src, pl.at, pl.dst, pl.key }) |v| ph.update(std.mem.asBytes(&v)); + if (f.gpu.len != 0) ph.update(f.gpu); + const places_hash = ph.final(); + if (sent.cols == f.cols and std.mem.eql(Hash, sent.hashes.items, hashes.items) and sent.places == places_hash) { + hashes.deinit(gpa); + return false; + } + try w.writeInt(u16, f.cols, .little); + try w.writeInt(u16, f.rows, .little); + try w.writeByte(pointer); + for (hashes.items, 0..) |h, y| { + try w.writeInt(u64, h, .little); + // Held only at the same size: a peer's Shadow of another starts afresh. + const held = sent.cols == f.cols and sent.hashes.items.len == f.rows and sent.hashes.items[y] == h; + try w.writeByte(@intFromBool(!held)); + if (!held) for (f.cells[y * f.cols ..][0..f.cols]) |*cell| { + try w.writeAll(&cell.text); + try w.writeInt(u32, cell.fg, .little); + try w.writeInt(u32, cell.bg, .little); + try w.writeInt(u16, cell.attrs, .little); + try w.writeByte(cell.len); + try w.writeByte(cell.flags); + }; + } + try w.writeByte(@intCast(places.len)); + for (places) |pl| { + try w.writeInt(u32, pl.w, .little); + try w.writeInt(u32, pl.h, .little); + inline for (.{ pl.src.x, pl.src.y, pl.src.w, pl.src.h, pl.at.x, pl.at.y, pl.at.w, pl.at.h }) |v| try w.writeInt(u32, v, .little); + inline for (.{ pl.dst.x, pl.dst.y, pl.dst.w, pl.dst.h }) |v| try w.writeInt(u16, v, .little); + try w.writeInt(u64, pl.key, .little); + } + if (f.gpu.len > 4 << 20) return error.BadGpuFrame; + try w.writeInt(u32, @intCast(f.gpu.len), .little); + try w.writeAll(f.gpu); + sent.hashes.deinit(gpa); + sent.hashes = hashes; + sent.cols = f.cols; + sent.places = places_hash; + // The strips of the rasters this frame shows: a key gone is sent whole again. + var i: usize = 0; + while (i < sent.keys.items.len) { + const kept = for (places) |pl| { + if (pl.key == sent.keys.items[i].key) break true; + } else false; + if (kept) i += 1 else _ = sent.keys.swapRemove(i); + } + return true; +} + test "a kind's head is checked before a core takes it, and a core's kinds are its own" { const Fake = struct { fn paint(_: ?*anyopaque, _: [*c]const c.pa_window, _: [*c]c.pa_paint) callconv(.c) void {} @@ -1213,3 +1490,97 @@ const GpuPaint = struct { return 0; } }; + +test "a pane of a kind's frame a row taller or shorter is drawn whole at its peer, never a row it let go" { + const gpa = std.testing.allocator; + var cells: [2 * 3]ShadowCell = @splat(std.mem.zeroes(ShadowCell)); + cells[0] = .{ .text = "a".* ++ @as([7]u8, @splat(0)), .fg = 1, .bg = 2, .attrs = 0, .len = 1, .flags = c.PA_PAINTED }; + var f: Frame = .{ .cells = &cells, .cols = 2, .rows = 2 }; + var sent: ShadowSent = .{}; + defer sent.deinit(gpa); + var blobs: Blobs = .{}; + const sh = try gpa.create(Shadow); + sh.* = .{}; + defer sh.deinit(gpa); + var out: std.Io.Writer.Allocating = .init(gpa); + defer out.deinit(); + for ([_]u16{ 2, 3, 2 }) |rows| { + f.rows = rows; + out.clearRetainingCapacity(); + try std.testing.expect(try encodeShadow(gpa, &sent, &f, 0, &out.writer)); + _ = try sh.apply(gpa, out.written(), 1, &blobs); + try std.testing.expectEqualStrings("a", sh.cells[0].text[0..1]); + } +} + +test "a pane of a kind crosses as its frame, a row the peer holds as its hash, a raster by key after its strips over what it shows" { + const gpa = std.testing.allocator; + var cells: [3 * 2]ShadowCell = @splat(std.mem.zeroes(ShadowCell)); + cells[0] = .{ .text = "a".* ++ @as([7]u8, @splat(0)), .fg = 1, .bg = 2, .attrs = 0, .len = 1, .flags = c.PA_PAINTED }; + // A raster of three strips (4 MiB a strip at 1,024 px), of which it shows the second. + const w: u32 = 1024; + const per = stripRows(w); + const pixels = try gpa.alloc(u8, @as(usize, w) * per * 3 * 4); + defer gpa.free(pixels); + @memset(pixels, 5); + var f: Frame = .{ .cells = &cells, .cols = 3, .rows = 2, .n = 1 }; + f.buf[0] = std.mem.zeroInit(Place, .{ .rgba = pixels.ptr, .w = w, .h = per * 3, .src = .{ .x = 0, .y = per + 1, .w = w, .h = 10 }, .key = 9 }); + f.places = &f.buf; + var sent: ShadowSent = .{}; + defer sent.deinit(gpa); + var blobs: Blobs = .{}; + defer blobs.deinit(gpa); + const sh = try gpa.create(Shadow); + sh.* = .{}; + defer sh.deinit(gpa); + var out: std.Io.Writer.Allocating = .init(gpa); + defer out.deinit(); + const name = std.hash.Wyhash.hash(1, std.mem.asBytes(&f.buf[0].key)); + try std.testing.expectEqual(@as(u64, 0b010), try sent.owed(gpa, &f.buf[0])); + try encodeStrip(&f.buf[0], 1, &out.writer); + try std.testing.expect(out.written().len <= strip_max + 20); + try blobs.strip(gpa, name, out.written(), &.{}); + out.clearRetainingCapacity(); + try std.testing.expect(try encodeShadow(gpa, &sent, &f, 0, &out.writer)); + try std.testing.expectEqual(@as(u64, 0), try sh.apply(gpa, out.written(), 1, &blobs)); + try std.testing.expectEqualStrings("a", sh.cells[0].text[0..1]); + try std.testing.expectEqual(@as(u8, 5), sh.places.items[0].rgba[per * w * 4]); + // The same frame again: nothing to send, no strip owed. + out.clearRetainingCapacity(); + try std.testing.expect(!try encodeShadow(gpa, &sent, &f, 0, &out.writer)); + try std.testing.expectEqual(@as(u64, 0), try sent.owed(gpa, &f.buf[0])); + // Its src moves into the third strip: that one is owed, and a peer + // without it does not show the raster and asks for it, once. + f.buf[0].src.y = 2 * per + 1; + try std.testing.expectEqual(@as(u64, 0b100), try sent.owed(gpa, &f.buf[0])); + out.clearRetainingCapacity(); + try std.testing.expect(try encodeShadow(gpa, &sent, &f, 0, &out.writer)); + try std.testing.expect(out.written().len < 4 + 1 + 2 * 9 + 60 + 8); + try std.testing.expectEqual(name, try sh.apply(gpa, out.written(), 1, &blobs)); + try std.testing.expectEqual(@as(usize, 0), sh.places.items.len); + try std.testing.expectEqual(@as(u64, 0), try sh.apply(gpa, out.written(), 1, &blobs)); +} + +test "optional GPU frames cross shadows, change independently, and disappear" { + const gpa = std.testing.allocator; + var sent: ShadowSent = .{}; + defer sent.deinit(gpa); + const shadow = try gpa.create(Shadow); + shadow.* = .{}; + defer shadow.deinit(gpa); + var blobs: Blobs = .{}; + defer blobs.deinit(gpa); + var cell = std.mem.zeroes(ShadowCell); + var frame: Frame = .{ .cols = 1, .rows = 1, .cells = @as([*]ShadowCell, @ptrCast(&cell))[0..1], .gpu = "first scene" }; + var out: std.Io.Writer.Allocating = .init(gpa); + defer out.deinit(); + for ([_][]const u8{ "first scene", "second scene", "" }) |bytes| { + frame.gpu = bytes; + out.clearRetainingCapacity(); + try std.testing.expect(try encodeShadow(gpa, &sent, &frame, 0, &out.writer)); + _ = try shadow.apply(gpa, out.written(), 1, &blobs); + try std.testing.expectEqualStrings(bytes, shadow.gpu); + out.clearRetainingCapacity(); + try std.testing.expect(!try encodeShadow(gpa, &sent, &frame, 0, &out.writer)); + } +} |
