sixel: support transparency

Sixel can only represent transparency for fully transparent (alpha
= 0) and fully opaque (alpha = 255) pixels, i.e. we would have to
do blending ourselves to do this "properly". But what do you even
blend? Background color? Images? Clearly you can't do text...

So instead of going down the blending route, we now just approximate
the 8-bit channel with Sixel's 1-bit channel and then patch it up with
dither. It does look a bit weird, but it's not *that* bad, especially
compared to the previous strategy of "blend with some color which
hopefully happens to be the background color" (it rarely was).

Note that this requires us to handle transparent images specially
in term. That is, for opaque ones, we can leave out the "clear cells
affected by image" part, but for transparent ones, we must clear the
entire image every time.

9 files changed, 90 insertions, 74 deletions

diff --git a/adapter/img/sixel.nim b/adapter/img/sixel.nim
index 19c3782d..f813ae77 100644
--- a/adapter/img/sixel.nim
+++ b/adapter/img/sixel.nim
@@ -42,7 +42,7 @@ proc die(s: string) {.noreturn.} =
   os.puts(s)
   quit(1)
 
-const DCSSTART = "\eP"
+const DCS = "\eP"
 const ST = "\e\\"
 
 proc setU32BE(s: var string; n: uint32; at: int) =
@@ -157,16 +157,8 @@ proc trim(trimMap: var TrimMap; K: var uint) =
   )
   K = k
 
-proc getPixel(img: openArray[RGBAColorBE]; m: int; bgcolor: ARGBColor): RGBColor
-    {.inline.} =
-  let c0 = img[m].toARGBColor()
-  if c0.a != 255:
-    let c1 = bgcolor.blend(c0)
-    return RGBColor(uint32(c1).fastmul(100))
-  return RGBColor(uint32(c0).fastmul(100))
-
-proc quantize(img: openArray[RGBAColorBE]; bgcolor: ARGBColor; outk: var uint):
-    NodeChildren =
+proc quantize(img: openArray[RGBAColorBE]; outk: var uint;
+    outTransparent: var bool): NodeChildren =
   var root = default(NodeChildren)
   if outk <= 2: # monochrome; not much we can do with an octree...
     root[0] = cast[Node](alloc0(sizeof(NodeObj)))
@@ -181,12 +173,16 @@ proc quantize(img: openArray[RGBAColorBE]; bgcolor: ARGBColor; outk: var uint):
   # map of non-leaves for each level.
   # (note: somewhat confusingly, this actually starts at level 1.)
   var trimMap: array[7, seq[Node]]
-  for i in 0 ..< img.len:
-    let c = img.getPixel(i, bgcolor)
+  var transparent = false
+  for c0 in img:
+    let c0 = c0.toARGBColor()
+    transparent = transparent or c0.a != 255
+    let c = RGBColor(uint32(c0).fastmul(100))
     K += root.insert(c, trimMap)
     while K > palette:
       trimMap.trim(K)
   outk = K
+  outTransparent = transparent
   return root
 
 proc flatten(children: NodeChildren; cols: var seq[Node]) =
@@ -211,18 +207,19 @@ proc flatten(root: NodeChildren; outs: var string; palette: uint): seq[Node] =
   return cols
 
 type
-  DitherDiff = tuple[r, g, b: int32]
+  DitherDiff = tuple[a, r, g, b: int32]
 
   Dither = object
     d1: seq[DitherDiff]
     d2: seq[DitherDiff]
 
-proc getColor(nodes: seq[Node]; c: RGBColor; diff: var DitherDiff): Node =
+proc getColor(nodes: seq[Node]; c: ARGBColor; diff: var DitherDiff): Node =
   var child: Node = nil
   var minDist = uint32.high
   var mdiff = default(DitherDiff)
   for node in nodes:
     let ic = node.u.leaf.c
+    let ad = int32(c.a) - 100
     let rd = int32(c.r) - int32(ic.r)
     let gd = int32(c.g) - int32(ic.g)
     let bd = int32(c.b) - int32(ic.b)
@@ -230,13 +227,13 @@ proc getColor(nodes: seq[Node]; c: RGBColor; diff: var DitherDiff): Node =
     if d < minDist:
       minDist = d
       child = node
-      mdiff = (rd, gd, bd)
+      mdiff = (ad, rd, gd, bd)
       if ic == c:
         break
   diff = mdiff
   return child
 
-proc getColor(root: var NodeChildren; c: RGBColor; nodes: seq[Node];
+proc getColor(root: var NodeChildren; c: ARGBColor; nodes: seq[Node];
     diff: var DitherDiff): int =
   if nodes.len < 64:
     # Octree-based nearest neighbor search creates really ugly artifacts
@@ -259,7 +256,7 @@ proc getColor(root: var NodeChildren; c: RGBColor; nodes: seq[Node];
   var level = 0
   var children = addr root
   while true:
-    let idx = c.getIdx(level)
+    let idx = RGBColor(c).getIdx(level)
     let child = children[idx]
     if child == nil:
       let child = nodes.getColor(c, diff)
@@ -267,31 +264,34 @@ proc getColor(root: var NodeChildren; c: RGBColor; nodes: seq[Node];
       return child.idx
     if child.idx != -1:
       let ic = child.u.leaf.c
+      let a = int32(c.a) - 100
       let r = int32(c.r) - int32(ic.r)
       let g = int32(c.g) - int32(ic.g)
       let b = int32(c.b) - int32(ic.b)
-      diff = (r, g, b)
+      diff = (a, r, g, b)
       return child.idx
     inc level
     children = addr child.u.children
 
-proc correctDither(c: RGBColor; x: int; dither: Dither): RGBColor =
-  let (rd, gd, bd) = dither.d1[x + 1]
+proc correctDither(c: ARGBColor; x: int; dither: Dither): ARGBColor =
+  let (ad, rd, gd, bd) = dither.d1[x + 1]
+  let pa = (uint32(c) shr 20) and 0xFF0
   let pr = (uint32(c) shr 12) and 0xFF0
   let pg = (uint32(c) shr 4) and 0xFF0
   let pb = (uint32(c) shl 4) and 0xFF0
   {.push overflowChecks: off.}
+  let a = uint8(uint32(clamp(int32(pa) + ad, 0, 1600)) shr 4)
   let r = uint8(uint32(clamp(int32(pr) + rd, 0, 1600)) shr 4)
   let g = uint8(uint32(clamp(int32(pg) + gd, 0, 1600)) shr 4)
   let b = uint8(uint32(clamp(int32(pb) + bd, 0, 1600)) shr 4)
   {.pop.}
-  return rgb(r, g, b)
+  return rgba(r, g, b, a)
 
 proc fs(dither: var Dither; x: int; d: DitherDiff) =
   let x = x + 1 # skip first bounds check
   template at(p, mul: untyped) =
-    var (rd, gd, bd) = p
-    p = (rd + d.r * mul, gd + d.g * mul, bd + d.b * mul)
+    var (ad, rd, gd, bd) = p
+    p = (ad + d.a * mul, rd + d.r * mul, gd + d.g * mul, bd + d.b * mul)
   {.push overflowChecks: off.}
   at(dither.d1[x + 1], 7)
   at(dither.d2[x - 1], 3)
@@ -367,16 +367,18 @@ proc createBands(bands: var seq[SixelBand]; activeChunks: seq[ptr SixelChunk]) =
       bands.add(SixelBand(head: chunk, tail: chunk))
 
 proc encode(img: openArray[RGBAColorBE]; width, height, offx, offy, cropw: int;
-    halfdump: bool; bgcolor: ARGBColor; palette: int) =
+    halfdump: bool; palette: int) =
   var palette = uint(palette)
-  var root = img.quantize(bgcolor, palette)
+  var transparent = false
+  var root = img.quantize(palette, transparent)
   # prelude
   var outs = "Cha-Image-Dimensions: " & $width & 'x' & $height & "\n\n"
   let preludeLenPos = outs.len
   if halfdump: # reserve size for prelude
     outs &= "\0\0\0\0"
+    outs &= char(transparent)
   else:
-    outs &= DCSSTART & 'q'
+    outs &= DCS & 'q'
     # set raster attributes
     outs &= "\"1;1;" & $width & ';' & $height
   let nodes = root.flatten(outs, palette)
@@ -410,9 +412,15 @@ proc encode(img: openArray[RGBAColorBE]; width, height, offx, offy, cropw: int;
       var chunk: ptr SixelChunk = nil
       for j in 0 ..< realw:
         let m = n + offx + j
-        let c0 = img.getPixel(m, bgcolor).correctDither(j, dither)
+        let c0 = img[m].toARGBColor()
+        let c1 = ARGBColor(uint32(c0).fastmul1(100))
+        let c2 = c1.correctDither(j, dither)
+        if c2.a < 50: # transparent
+          let diff = (int32(c2.a), 0i32, 0i32, 0i32)
+          dither.fs(j, diff)
+          continue
         var diff: DitherDiff
-        let c = root.getColor(c0, nodes, diff)
+        let c = root.getColor(c2, nodes, diff)
         dither.fs(j, diff)
         if chunk == nil or chunk.c != c:
           chunk = addr chunkMap[c]
@@ -492,7 +500,6 @@ proc main() =
     var offy = 0
     var halfdump = false
     var palette = -1
-    var bgcolor = rgb(0, 0, 0)
     var cropw = -1
     var quality = -1
     for hdr in getEnv("REQUEST_HEADERS").split('\n'):
@@ -519,8 +526,6 @@ proc main() =
         if q.isNone:
           die("Cha-Control: ConnectionError 1 wrong quality\n")
         quality = int(q.get)
-      of "Cha-Image-Background-Color":
-        bgcolor = parseLegacyColor0(s)
     if cropw == -1:
       cropw = width
     if palette == -1:
@@ -543,7 +548,7 @@ proc main() =
     enterNetworkSandbox() # don't swallow stat
     let p = cast[ptr UncheckedArray[RGBAColorBE]](src.p)
     p.toOpenArray(0, n - 1).encode(width, height, offx, offy, cropw, halfdump,
-      bgcolor, palette)
+      palette)
     dealloc(src)
 
 main()
diff --git a/doc/image.md b/doc/image.md
index e9232686..7a3455ee 100644
--- a/doc/image.md
+++ b/doc/image.md
@@ -47,22 +47,23 @@ to find a terminal that supports it.
 
 Known quirks and implementation details:
 
-* XTerm needs extensive configuration for ideal sixel support. In particular,
-  you will want to set the "decTerminalID", "numColorRegisters",
-  and "maxGraphicSize" attributes. See `man xterm` for details.
-* We assume private color registers are supported. On terminals where they
-  aren't (e.g. SyncTERM or hardware terminals), colors will get messed up with
-  multiple images on screen.
-* We send XTSMGRAPHICS for retrieving the number of color registers; on failure,
-  we fall back to 256. You can override color register count using the
-  `display.sixel-colors` configuration value.
-* For the most efficient sixel display, you will want a cell height that
-  is a multiple of 6. Otherwise, the images will have to be re-coded several
-  times on scroll.
-* Normally, Sixel encoding runs in two passes. On slow computers, you can try
-  setting `display.sixel-colors = 2`, which will skip the first pass.
-* Transparency is currently not supported; you will get strange results with
-  transparent images.
+* XTerm needs extensive configuration for ideal sixel support. In
+  particular, you will want to set the decTerminalID, numColorRegisters,
+  and maxGraphicSize attributes. See `man xterm` for details.
+* We assume private color registers are supported. On terminals where
+  they aren't (e.g. SyncTERM or hardware terminals), colors will get
+  messed up with multiple images on screen.
+* We send XTSMGRAPHICS for retrieving the number of color registers;
+  on failure, we fall back to 256. You can override color register count
+  using the `display.sixel-colors` configuration value.
+* For the most efficient sixel display, you will want a cell height
+  that is a multiple of 6. Otherwise, the images will have to be re-coded
+  several times on scroll.
+* Normally, Sixel encoding runs in two passes. On slow computers, you
+  can try setting `display.sixel-colors = 2`, which will skip the first
+  pass (but will also display everything in monochrome).
+* Transparency *is* supported, but looks weird because we approximate an
+  8-bit alpha channel with Sixel's 1-bit alpha channel.
 
 ### Kitty
 
diff --git a/src/layout/renderdocument.nim b/src/layout/renderdocument.nim
index 76042ae2..9622d305 100644
--- a/src/layout/renderdocument.nim
+++ b/src/layout/renderdocument.nim
@@ -231,7 +231,6 @@ type
     width*: int
     height*: int
     bmp*: NetworkBitmap
-    bgcolor*: RGBColor
 
   AbsolutePos = object
     offset: Offset
@@ -380,8 +379,7 @@ proc renderInlineFragment(grid: var FlexibleGrid; state: var RenderState;
           y: (offset.y div state.attrs.ppl).toInt,
           width: atom.size.w.toInt,
           height: atom.size.h.toInt,
-          bmp: atom.bmp,
-          bgcolor: bgcolor0.toRGBColor()
+          bmp: atom.bmp
         ))
   if fragment.computed{"position"} != PositionStatic:
     if fragment.splitType != {stSplitStart, stSplitEnd}:
diff --git a/src/local/container.nim b/src/local/container.nim
index 6bdfe64b..5632bd88 100644
--- a/src/local/container.nim
+++ b/src/local/container.nim
@@ -122,6 +122,8 @@ type
     offx*: int # same as CanvasImage.offx
     dispw*: int # same as CanvasImage.dispw
     erry*: int # same as CanvasImage.offy % 6
+    # whether the image has transparency, *disregarding the last row*
+    transparent*: bool
 
   Container* = ref object of RootObj
     # note: this is not the same as source.request.url (but should be synced
diff --git a/src/local/pager.nim b/src/local/pager.nim
index ec242472..e8034af7 100644
--- a/src/local/pager.nim
+++ b/src/local/pager.nim
@@ -586,7 +586,6 @@ proc loadCachedImage(pager: Pager; container: Container; image: PosBitmap;
       url = newURL("img-codec+x-sixel:encode").get
       headers.add("Cha-Image-Sixel-Halfdump", "1")
       headers.add("Cha-Image-Sixel-Palette", $pager.term.sixelRegisterNum)
-      headers.add("Cha-Image-Background-Color", $image.bgcolor)
       headers.add("Cha-Image-Offset", $offx & 'x' & $erry)
       headers.add("Cha-Image-Crop-Width", $dispw)
     of imKitty:
@@ -630,6 +629,11 @@ proc loadCachedImage(pager: Pager; container: Container; image: PosBitmap;
       cachedImage.data = blob
       cachedImage.state = cisLoaded
       cachedImage.cacheId = cacheId
+      if imageMode == imSixel and 4 < blob.size:
+        #TODO this should be a response header, but loader can't send us
+        # those yet...
+        let u = cast[ptr UncheckedArray[uint8]](blob.buffer)[4]
+        cachedImage.transparent = u == 1
     )
   )
   container.cachedImages.add(cachedImage)
@@ -660,7 +664,7 @@ proc initImages(pager: Pager; container: Container) =
     let canvasImage = pager.term.loadImage(cached.data, container.process,
       imageId, image.x - container.fromx, image.y - container.fromy,
       image.width, image.height, image.x, image.y, pager.bufWidth,
-      pager.bufHeight, erry, offx, dispw)
+      pager.bufHeight, erry, offx, dispw, cached.transparent)
     if canvasImage != nil:
       newImages.add(canvasImage)
   pager.term.clearImages(pager.bufHeight)
diff --git a/src/local/term.nim b/src/local/term.nim
index 0e245256..3f38193b 100644
--- a/src/local/term.nim
+++ b/src/local/term.nim
@@ -73,6 +73,7 @@ type
     damaged: bool
     marked*: bool
     dead: bool
+    transparent: bool # note: this is only set in outputSixelImage
     kittyId: int
     # 0 if kitty
     erry: int
@@ -735,7 +736,12 @@ proc checkImageDamage*(term: Terminal; maxh: int) =
       let mx = image.x + (image.dispw - image.offx) div term.attrs.ppc
       for y in max(image.y, 0) ..< ey0:
         let od = term.lineDamage[y]
-        if od < mx:
+        if image.transparent and od > image.x:
+          image.damaged = true
+          if od < mx:
+            # damage starts inside this image; move it to its beginning.
+            term.lineDamage[y] = image.x
+        elif not image.transparent and od < mx:
           image.damaged = true
           if y >= ey1:
             break
@@ -752,7 +758,8 @@ proc checkImageDamage*(term: Terminal; maxh: int) =
               term.lineDamage[y] = mx
 
 proc loadImage*(term: Terminal; data: Blob; pid, imageId, x, y, width, height,
-    rx, ry, maxw, maxh, erry, offx, dispw: int): CanvasImage =
+    rx, ry, maxw, maxh, erry, offx, dispw: int; transparent: bool):
+    CanvasImage =
   if (let image = term.findImage(pid, imageId, rx, ry, width, height, erry,
         offx, dispw); image != nil):
     # reuse image on screen
@@ -777,7 +784,8 @@ proc loadImage*(term: Terminal; data: Blob; pid, imageId, x, y, width, height,
     ry: ry,
     width: width,
     height: height,
-    erry: erry
+    erry: erry,
+    transparent: transparent
   )
   if term.positionImage(image, x, y, maxw, maxh):
     return image
@@ -796,26 +804,22 @@ proc outputSixelImage(term: Terminal; x, y: int; image: CanvasImage;
   let offy = image.offy
   let dispw = image.dispw
   let disph = image.disph
-  var outs = term.cursorGoto(x, y)
   let realw = dispw - offx
   let realh = disph - offy
-  # set transparency if we want to draw a non-6-divisible number
-  # of rows; omit it otherwise, for then some terminals (e.g. foot)
-  # handle the image more efficiently
-  let trans = realh mod 6 != 0
-  outs &= DCS & "0;" & $int(trans) & 'q'
-  # set raster attributes
-  outs &= "\"1;1;" & $realw & ';' & $realh
-  if data.len < 4: # bounds check
-    outs &= ST
-    term.write(outs)
+  if data.len < 5: # bounds check
     return
   let sraLen = int(data.getU32BE(0))
-  let preludeLen = sraLen + 4
+  let preludeLen = sraLen + 5
   if preludeLen > data.len:
-    outs &= ST
-    term.write(outs)
     return
+  var outs = term.cursorGoto(x, y)
+  # set transparency if we want to draw a non-6-divisible number
+  # of rows *or* the image is transparent; omit it otherwise, for then
+  # some terminals (e.g. foot) handle the image more efficiently
+  let trans = realh mod 6 != 0 or image.transparent
+  outs &= DCS & "0;" & $int(trans) & "q"
+  # set raster attributes
+  outs &= "\"1;1;" & $realw & ';' & $realh
   term.write(outs)
   term.write(data.toOpenArray(4, preludeLen - 1))
   let lookupTableLen = int(data.getU32BE(data.len - 4))
diff --git a/src/server/buffer.nim b/src/server/buffer.nim
index c5d00655..71eef321 100644
--- a/src/server/buffer.nim
+++ b/src/server/buffer.nim
@@ -1615,8 +1615,10 @@ proc getLines*(buffer: Buffer; w: Slice[int]): GetLinesResult {.proxy.} =
   result.numLines = buffer.lines.len
   result.bgcolor = buffer.bgcolor
   if buffer.config.images:
+    let ppl = buffer.attrs.ppl
     for image in buffer.images:
-      if image.y <= w.b and image.y + image.height >= w.a:
+      let ey = image.y + (image.height + ppl - 1) div ppl # ceil
+      if image.y <= w.b and ey >= w.a:
         result.images.add(image)
 
 proc markURL*(buffer: Buffer; schemes: seq[string]) {.proxy.} =
diff --git a/src/types/color.nim b/src/types/color.nim
index ab8d4984..20de1fcc 100644
--- a/src/types/color.nim
+++ b/src/types/color.nim
@@ -293,7 +293,7 @@ func fastmul*(c, ca: uint32): uint32 =
   return ga or (rb shr 8)
 
 # fastmul, but preserves alpha
-func fastmul1(c, ca: uint32): uint32 =
+func fastmul1*(c, ca: uint32): uint32 =
   let u = c
   var rb = u and 0x00FF00FFu32
   rb *= ca
diff --git a/todo b/todo
index e6b14ece..21e78282 100644
--- a/todo
+++ b/todo
@@ -69,7 +69,7 @@ layout engine:
 - iframe
 - writing-mode, grid, ruby, ... (i.e. cool new stuff)
 images:
-- z order, proper image blending
+- z order
 - animation
 man:
 - add a DOM -> man page converter so that we do not depend on pandoc