优化 GameBoy Z80 中的位操作算法
Optimizing a bit-manipulating algorithm in GameBoy Z80
这不是作业问题，这是我正在开发的游戏。
我有两个 16 位 RGB 颜色，并且想根据其他六个四位数量改变它们的六个通道。该算法简单但乏味；我正在寻找一种通过一次完成更多有用的工作来优化它的方法。
高级概述：
hl指向四个颜色字节。 [hl] = %gggrrrrr、[hl+1] = %0bbbbbgg、[hl+2] = %GGGRRRRR 和 [hl+3] = %0BBBBBGG。 （这是两种颜色，rgb 和 RGB。）bc 指向三个增量字节。 [bc] = %hhhhaaaa、[bc+1] = %ddddssss 和 [bc+2] = %ppppqqqq。 （这是六个增量值，h、a、d、s、p 和 q。）- 因此有六个 5 位颜色通道值和六个 4 位增量值。我想将每个颜色通道 C 与增量值 D[= 配对78=]，然后改变 C，像这样：C' = C + (D & %11 ) − ((D & %1100) >> 2), 但保持 C 在其 5 位边界 [0, 31] 内。我实际上并不关心它们是如何配对的：任何方便的一对一配对都可以。如果 C + ((D & %1100 ) >> 2) − (D & %11) 以某种方式允许更优雅的算法，我会同意的。
如果我在寄存器 d 中隔离颜色通道 C 和增量值 [=寄存器 e 中的 43=]D，则此例程将为该对执行变体：
VaryColorChannelByDV:
; d = color, e = DV
; a <- d + (e & %11) - (e >> 2), clamped to [0, 31]
ld a, e
and %11 ; a <- (e & %11)
add d ; a <- d + (e & %11)
srl e
srl e ; e <- e >> 2
sub e ; a <- d + (e & %11) - (e >> 2)
jr c, .zero ; a < 0, clamp to 0
cp 32
ret c ; 0 <= a < 32
ld a, 31 ; a >= 32, clamp to 31
ret
.zero
xor a
ret
到目前为止，我有一个通用例程，可以将任何 DV 应用于任何颜色通道；然后是隔离红色、绿色或蓝色通道并将给定的 DV 应用于它们的三个例程；最后是一个主例程，它挑选出六个 DV 并用它们调用适当的通道修改例程。这是 "good enough"，但我确信还有改进的余地。执行速度似乎不是问题，但我想减少代码大小（当然删除冗余指令也会提高一点速度）。是否有任何有用的 asm 位操作技巧？
完整代码如下：
GetColorChannelVariedByDV:
; d = color, e = DV
; a <- d + (e & %11) - (e & %1100 >> 2), clamped to [0, 31]
ld a, e
and %11
add d
srl e
srl e
sub e
jr c, .zero
cp 32
ret c
ld a, 31
ret
.zero
xor a
ret
VaryRedByDV:
;;; e = DV
;;; [hl+0] = gggr:rrrr
;;; [hl+1] = 0bbb:bbgg
; store red in d
ld a, [hl]
and %00011111
ld d, a
; vary d according to e
call GetColorChannelVariedByDV
; store a back in red
ld d, a
ld a, [hl]
and %11100000
or d
ld [hl], a
ret
VaryGreenByDV:
;;; e = DV
;;; [hl+0] = gggr:rrrr
;;; [hl+1] = 0bbb:bbgg
; store green in d
ld a, [hli]
and %11100000
srl a
swap a
ld d, a ; d = 00000ggg
ld a, [hld]
and %00000011
swap a
srl a
or d
ld d, a
; vary d according to e
call GetColorChannelVariedByDV
; store a back in green
sla a
swap a
ld d, a
and %11100000
ld e, a
ld a, d
and %00000011
ld d, a
ld a, [hl]
and %00011111
or e
ld [hli], a
ld a, [hl]
and %11111100
or d
ld [hld], a
ret
VaryBlueByDV:
;;; e = DV
;;; [hl+0] = gggr:rrrr
;;; [hl+1] = 0bbb:bbgg
; store blue in d
inc hl
ld a, [hl]
and %01111100
srl a
srl a
ld d, a
; vary d according to e
call GetColorChannelVariedByDV
; store a back in blue
ld d, a
sla d
sla d
ld a, [hl]
and %10000011
or d
ld [hl], a
dec hl
ret
VaryColorsByDVs::
; hl = colors
; [hl+0] = gggr:rrrr
; [hl+1] = 0bbb:bbgg
; [hl+2] = GGGR:RRRR
; [hl+3] = 0BBB:BBGG
; bc = DVs
; [bc+0] = hhhh:aaaa
; [bc+1] = dddd:ssss
; [bc+2] = pppp:qqqq
;;; LiteRed ~ hDV, aka, rrrrr ~ hhhh
; store hDV in e
ld a, [bc]
swap a
and %1111
ld e, a
; vary LiteRed by e
call VaryRedByDV
;;; LiteGrn ~ aDV, aka, ggggg ~ aaaa
; store aDV in e
ld a, [bc]
and %1111
ld e, a
; vary LiteGrn by e
call VaryGreenByDV
;;; move from h/a DV to d/s DV
inc bc
;;; LiteBlu ~ dDV, aka, bbbbb ~ dddd
; store dDV in e
ld a, [bc]
swap a
and %1111
ld e, a
; vary LiteBlu by e
call VaryBlueByDV
;;; Move from Lite color to Dark color
inc hl
inc hl
;;; DarkRed ~ sDV, aka, RRRRR ~ ssss
; store sDV in e
ld a, [bc]
and %1111
ld e, a
; vary DarkRed by e
call VaryRedByDV
;;; move from d/s DV to p/q DV
inc bc
;;; DarkGrn ~ pDV, aka, GGGGG ~ pppp
; store pDV in e
ld a, [bc]
swap a
and %1111
ld e, a
; vary DarkGrn by e
call VaryGreenByDV
;;; DarkBlu ~ qDV, aka, BBBBB ~ qqqq
; store qDV in e
ld a, [bc]
and %1111
ld e, a
; vary DarkBlu by e
call VaryBlueByDV
ret
嗯...你应该给我们更多关于这些数据来自哪里的信息，如果你能进一步预处理它们，因为 +(d&3)-(d>>2) 看起来很不幸，如果可能的话我会尽量避免这种情况。实际上，整个 5:5:5 RGB 东西可能有点超出 Z80 的范围，但如果您知道它适合您，请继续（我说的是我的 ZX Spectrum 体验，3.5MHz 几乎不足以操纵 1 位黑白像素）。
但目前，您已经得到的东西可以通过删除两个 ld 指令立即得到一些简化：
VaryColorChannelByDV:
...
add d
; ld d, a ; d <- d + (e & %11)
srl e
srl e
; ld a, d ;### A didn't change, still contains C + DV&3
sub e ; a <- d + (e & %11) - (e & %1100 >> 2)
...
如果你的内存不短，你可以创建 256B 查找 - table 来限制值，所以例如你会保留 h 或 b table的高地址字节，然后将a中的结果加载到l或c中，并被ld a,(hl/bc)钳位。这是 4+7 t 而不是那些 jr/cp/ret/...。如果我没有计算错误（0 + 0 - 3 是最小值，31 + 3 - 0是最大结果）。因此，您仍然可以使用地址 "inside the page" 35..252 处的字节来存储其他数据或代码。
稍后我会尝试从整体上看一下，尽可能避免一些针对每个组件的通用内容，但我担心更好的输入数据格式可能会给您带来更大的提升，或者了解您的总体目标和所有约束（例如，如果 RGB 中的最高位始终为 0 并且必须为 0，或者作为结果可以是随机的，并且作为输入为 0，等等...每个细节通常会导致另一个被删除指令，在 Z80 上通常价值 4-11 吨）。
我现在能想到的最小的是 57 个字节：
VaryColorsByDVs::
; hl = colors
; [hl+0] = gggr:rrrr
; [hl+1] = 0bbb:bbgg
; [hl+2] = GGGR:RRRR
; [hl+3] = 0BBB:BBGG
; bc = DVs
; [bc+0] = hhhh:aaaa
; [bc+1] = dddd:ssss
; [bc+2] = pppp:qqqq
ld a, 2 ; -floor(0/3)*6 mod 0
.next:
sla [hl]
inc hl
rl [hl]
.loop:
push af
rrca
ld a, [bc]
jr nc, .skip
swap a
inc bc
.skip:
rlca
ld d, a
and %00011000
ld e, a
ld a, d
rlca
rlca
and %00011000
add a, [hl]
jr nc, .noOverflow
or %11111000
.noOverflow:
sub e
jr nc, .noUnderflow
and %00000111
.noUnderflow:
dec hl
ld de, 5
.rotate:
add a, a
rl [hl]
adc a, d
dec e
jr nz, .rotate
inc hl
ld [hl], a
pop af
add a, 85 ; floor(0/3)
jr nc, .loop
ret z
inc hl
jr .next
修复 Ped7g 的注释仅花费 4 个字节，总共 61 个字节：
VaryColorsByDVs::
; hl = colors
; [hl+0] = gggr:rrrr
; [hl+1] = 0bbb:bbgg
; [hl+2] = GGGR:RRRR
; [hl+3] = 0BBB:BBGG
; bc = DVs
; [bc+0] = hhhh:aaaa
; [bc+1] = dddd:ssss
; [bc+2] = pppp:qqqq
ld a, 2 ; -floor(0/3)*6 mod 0
.next:
sla [hl]
inc hl
rl [hl]
.loop:
push af
rrca
ld a, [bc]
jr nc, .skip
swap a
inc bc
.skip:
ld d, a
and %00001100
ld e, a
ld a, d
rlca
rlca
and %00001100
sub e
add a, a
jr nc, .positive
.negative:
add a, [hl]
jr c, .continue
and %00000111
db ; jr c,
.positive:
add a, [hl]
jr nc, .continue
or %11111000
.continue:
dec hl
ld de, 5
.rotate:
add a, a
rl [hl]
adc a, d
dec e
jr nz, .rotate
inc hl
ld [hl], a
pop af
add a, 85 ; floor(0/3)
jr nc, .loop
ret z
inc hl
jr .next
这不是作业问题，这是我正在开发的游戏。
我有两个 16 位 RGB 颜色，并且想根据其他六个四位数量改变它们的六个通道。该算法简单但乏味；我正在寻找一种通过一次完成更多有用的工作来优化它的方法。
高级概述：
hl指向四个颜色字节。[hl] = %gggrrrrr、[hl+1] = %0bbbbbgg、[hl+2] = %GGGRRRRR和[hl+3] = %0BBBBBGG。 （这是两种颜色，rgb和RGB。）bc指向三个增量字节。[bc] = %hhhhaaaa、[bc+1] = %ddddssss和[bc+2] = %ppppqqqq。 （这是六个增量值，h、a、d、s、p和q。）- 因此有六个 5 位颜色通道值和六个 4 位增量值。我想将每个颜色通道 C 与增量值 D[= 配对78=]，然后改变 C，像这样：C' = C + (D & %11 ) − ((D & %1100) >> 2), 但保持 C 在其 5 位边界 [0, 31] 内。我实际上并不关心它们是如何配对的：任何方便的一对一配对都可以。如果 C + ((D & %1100 ) >> 2) − (D & %11) 以某种方式允许更优雅的算法，我会同意的。
如果我在寄存器 d 中隔离颜色通道 C 和增量值 [=寄存器 e 中的 43=]D，则此例程将为该对执行变体：
VaryColorChannelByDV:
; d = color, e = DV
; a <- d + (e & %11) - (e >> 2), clamped to [0, 31]
ld a, e
and %11 ; a <- (e & %11)
add d ; a <- d + (e & %11)
srl e
srl e ; e <- e >> 2
sub e ; a <- d + (e & %11) - (e >> 2)
jr c, .zero ; a < 0, clamp to 0
cp 32
ret c ; 0 <= a < 32
ld a, 31 ; a >= 32, clamp to 31
ret
.zero
xor a
ret
到目前为止，我有一个通用例程，可以将任何 DV 应用于任何颜色通道；然后是隔离红色、绿色或蓝色通道并将给定的 DV 应用于它们的三个例程；最后是一个主例程，它挑选出六个 DV 并用它们调用适当的通道修改例程。这是 "good enough"，但我确信还有改进的余地。执行速度似乎不是问题，但我想减少代码大小（当然删除冗余指令也会提高一点速度）。是否有任何有用的 asm 位操作技巧？
完整代码如下：
GetColorChannelVariedByDV:
; d = color, e = DV
; a <- d + (e & %11) - (e & %1100 >> 2), clamped to [0, 31]
ld a, e
and %11
add d
srl e
srl e
sub e
jr c, .zero
cp 32
ret c
ld a, 31
ret
.zero
xor a
ret
VaryRedByDV:
;;; e = DV
;;; [hl+0] = gggr:rrrr
;;; [hl+1] = 0bbb:bbgg
; store red in d
ld a, [hl]
and %00011111
ld d, a
; vary d according to e
call GetColorChannelVariedByDV
; store a back in red
ld d, a
ld a, [hl]
and %11100000
or d
ld [hl], a
ret
VaryGreenByDV:
;;; e = DV
;;; [hl+0] = gggr:rrrr
;;; [hl+1] = 0bbb:bbgg
; store green in d
ld a, [hli]
and %11100000
srl a
swap a
ld d, a ; d = 00000ggg
ld a, [hld]
and %00000011
swap a
srl a
or d
ld d, a
; vary d according to e
call GetColorChannelVariedByDV
; store a back in green
sla a
swap a
ld d, a
and %11100000
ld e, a
ld a, d
and %00000011
ld d, a
ld a, [hl]
and %00011111
or e
ld [hli], a
ld a, [hl]
and %11111100
or d
ld [hld], a
ret
VaryBlueByDV:
;;; e = DV
;;; [hl+0] = gggr:rrrr
;;; [hl+1] = 0bbb:bbgg
; store blue in d
inc hl
ld a, [hl]
and %01111100
srl a
srl a
ld d, a
; vary d according to e
call GetColorChannelVariedByDV
; store a back in blue
ld d, a
sla d
sla d
ld a, [hl]
and %10000011
or d
ld [hl], a
dec hl
ret
VaryColorsByDVs::
; hl = colors
; [hl+0] = gggr:rrrr
; [hl+1] = 0bbb:bbgg
; [hl+2] = GGGR:RRRR
; [hl+3] = 0BBB:BBGG
; bc = DVs
; [bc+0] = hhhh:aaaa
; [bc+1] = dddd:ssss
; [bc+2] = pppp:qqqq
;;; LiteRed ~ hDV, aka, rrrrr ~ hhhh
; store hDV in e
ld a, [bc]
swap a
and %1111
ld e, a
; vary LiteRed by e
call VaryRedByDV
;;; LiteGrn ~ aDV, aka, ggggg ~ aaaa
; store aDV in e
ld a, [bc]
and %1111
ld e, a
; vary LiteGrn by e
call VaryGreenByDV
;;; move from h/a DV to d/s DV
inc bc
;;; LiteBlu ~ dDV, aka, bbbbb ~ dddd
; store dDV in e
ld a, [bc]
swap a
and %1111
ld e, a
; vary LiteBlu by e
call VaryBlueByDV
;;; Move from Lite color to Dark color
inc hl
inc hl
;;; DarkRed ~ sDV, aka, RRRRR ~ ssss
; store sDV in e
ld a, [bc]
and %1111
ld e, a
; vary DarkRed by e
call VaryRedByDV
;;; move from d/s DV to p/q DV
inc bc
;;; DarkGrn ~ pDV, aka, GGGGG ~ pppp
; store pDV in e
ld a, [bc]
swap a
and %1111
ld e, a
; vary DarkGrn by e
call VaryGreenByDV
;;; DarkBlu ~ qDV, aka, BBBBB ~ qqqq
; store qDV in e
ld a, [bc]
and %1111
ld e, a
; vary DarkBlu by e
call VaryBlueByDV
ret
嗯...你应该给我们更多关于这些数据来自哪里的信息，如果你能进一步预处理它们，因为 +(d&3)-(d>>2) 看起来很不幸，如果可能的话我会尽量避免这种情况。实际上，整个 5:5:5 RGB 东西可能有点超出 Z80 的范围，但如果您知道它适合您，请继续（我说的是我的 ZX Spectrum 体验，3.5MHz 几乎不足以操纵 1 位黑白像素）。
但目前，您已经得到的东西可以通过删除两个 ld 指令立即得到一些简化：
VaryColorChannelByDV:
...
add d
; ld d, a ; d <- d + (e & %11)
srl e
srl e
; ld a, d ;### A didn't change, still contains C + DV&3
sub e ; a <- d + (e & %11) - (e & %1100 >> 2)
...
如果你的内存不短，你可以创建 256B 查找 - table 来限制值，所以例如你会保留 h 或 b table的高地址字节，然后将a中的结果加载到l或c中，并被ld a,(hl/bc)钳位。这是 4+7 t 而不是那些 jr/cp/ret/...。如果我没有计算错误（0 + 0 - 3 是最小值，31 + 3 - 0是最大结果）。因此，您仍然可以使用地址 "inside the page" 35..252 处的字节来存储其他数据或代码。
稍后我会尝试从整体上看一下，尽可能避免一些针对每个组件的通用内容，但我担心更好的输入数据格式可能会给您带来更大的提升，或者了解您的总体目标和所有约束（例如，如果 RGB 中的最高位始终为 0 并且必须为 0，或者作为结果可以是随机的，并且作为输入为 0，等等...每个细节通常会导致另一个被删除指令，在 Z80 上通常价值 4-11 吨）。
我现在能想到的最小的是 57 个字节：
VaryColorsByDVs::
; hl = colors
; [hl+0] = gggr:rrrr
; [hl+1] = 0bbb:bbgg
; [hl+2] = GGGR:RRRR
; [hl+3] = 0BBB:BBGG
; bc = DVs
; [bc+0] = hhhh:aaaa
; [bc+1] = dddd:ssss
; [bc+2] = pppp:qqqq
ld a, 2 ; -floor(0/3)*6 mod 0
.next:
sla [hl]
inc hl
rl [hl]
.loop:
push af
rrca
ld a, [bc]
jr nc, .skip
swap a
inc bc
.skip:
rlca
ld d, a
and %00011000
ld e, a
ld a, d
rlca
rlca
and %00011000
add a, [hl]
jr nc, .noOverflow
or %11111000
.noOverflow:
sub e
jr nc, .noUnderflow
and %00000111
.noUnderflow:
dec hl
ld de, 5
.rotate:
add a, a
rl [hl]
adc a, d
dec e
jr nz, .rotate
inc hl
ld [hl], a
pop af
add a, 85 ; floor(0/3)
jr nc, .loop
ret z
inc hl
jr .next
修复 Ped7g 的注释仅花费 4 个字节，总共 61 个字节：
VaryColorsByDVs::
; hl = colors
; [hl+0] = gggr:rrrr
; [hl+1] = 0bbb:bbgg
; [hl+2] = GGGR:RRRR
; [hl+3] = 0BBB:BBGG
; bc = DVs
; [bc+0] = hhhh:aaaa
; [bc+1] = dddd:ssss
; [bc+2] = pppp:qqqq
ld a, 2 ; -floor(0/3)*6 mod 0
.next:
sla [hl]
inc hl
rl [hl]
.loop:
push af
rrca
ld a, [bc]
jr nc, .skip
swap a
inc bc
.skip:
ld d, a
and %00001100
ld e, a
ld a, d
rlca
rlca
and %00001100
sub e
add a, a
jr nc, .positive
.negative:
add a, [hl]
jr c, .continue
and %00000111
db ; jr c,
.positive:
add a, [hl]
jr nc, .continue
or %11111000
.continue:
dec hl
ld de, 5
.rotate:
add a, a
rl [hl]
adc a, d
dec e
jr nz, .rotate
inc hl
ld [hl], a
pop af
add a, 85 ; floor(0/3)
jr nc, .loop
ret z
inc hl
jr .next