如何将布尔表达式转换为汇编代码
How to convert a boolean expression into assembly code
我对汇编很陌生
考虑以下函数:
其中'+'代表'Or'逻辑门和变量的串联,代表'And'逻辑门。
如何在emu8086中实现这样的功能?鉴于输入参数可能代表寄存器的位
AL,例如,输出会将其值更改为 0 或 1。
更新:
这是我所做的,我知道它写得不好,如果有任何建议或更简单的方法让我知道,它似乎确实有效
感谢大家的帮助,尤其是 peter。
org 100h
mov al, 0A3h pour le test
mov ah, al
and ah, 01h ;ah = x0
shr al, 1
mov bl, al
and bl, 01h ;bl = x1
shr al, 1
mov bh, al
and bh, 01h
not bh
and bh, 01h ;bh = !x2
shr al, 1
mov cl, al
and cl, 01h
not cl
and cl, 01h ;cl = !x3
shr al, 1
mov ch, al
and ch, 01h
not ch
and ch, 01h ;ch = !x4
shr al, 1
mov dl, al
and dl, 01h ;x5 = dl
shr al, 1
mov dh, al
and dh, 01h
not dh
and dh, 01h ;dh = !x6
shr al, 1 ;al = x7
and bh, dl
and bh, cl
and bh, ah ;!x2 and x5 and !x3 and x0
and dh, bl
and dh, ch
and dh, al ;!x6 and x1 and !x4 and x7
or dh, bh
mov ah, dh ;resultat dans ah
ret
您确定具有四个 x_n
值的表达式应该是按位 AND,而不是将它们连接成 4 位值?然后二进制加法?因为我可能已经猜到了。如果是这样,请参阅 https://codegolf.stackexchange.com/a/203610 以了解移位和 rcl reg, 1
在一对寄存器之间拆分位的方法。或者在带有 BMI2 的现代 x86 上,您可以使用 2x pext
和 add
来做到这一点。
表达式在每个组中的位都按特定顺序排列,而不仅仅是升序或降序这一事实可能是他们希望您解压缩字节的线索分成两个 4 位整数并用它做一个正常的 +
。
如果我们假设您的 asm 是正确函数的示例
这个答案的其余部分是关于优化你的 asm 中的操作,它执行两组 AND 和 OR,它们一起产生一个布尔值,在中产生 0
或 1
AL.
您可以对仅分别提取每一位的简单/直接实现进行一些改进。例如您不需要在 之前和 之后进行 AND 操作。第一个 AND 将使高位全为 0,然后 NOT 使它们为 1,然后第二个 AND 使它们再次为零。
mov bh, al
; and bh, 01h ; This is pointless
not bh
and bh, 01h ;bh = !x2
你可以更进一步:你纯粹使用按位运算,只关心每个寄存器中的低位。 你可以在最后 and al, 1
一次隔离你想要的位,所有临时对象都在其高位中携带垃圾。
要翻转 一些 位但不是全部,请使用带有常量掩码的 XOR。例如要翻转 AL 中的位 6、4、3、2 并保持其他位不变,请使用 xor al, 01011100b
1。然后你可以转移和移动到单独的寄存器而不需要任何 NOT 指令。
脚注 1:结尾的 b
表示基数 2 / 二进制。如果 emu8086 支持它,或者如果您必须编写等效的十六进制,它在 MASM syntax、IDK 中有效。
你可以直接进入这些寄存器而不是先提取,所以你只需要两个暂存器。
xor al, 01011100b ; complement bits 6,4,3,2
mov cl, al ; x0, first bit of the 2&5&3&0 group
shr al, 1
mov dl, al ; x1, first bit of the 6&1&4&7 group
shr al, 1
and cl, al ; AND X2 into the first group, X2 & x0
shr al, 1
and cl, al ; cl = X2 & X3 & x0
... ; cl = 2&5&3&0, dl = 6&1&4 with a few more steps
shr al, 1 ; AL = x7
and al, dl ; AL = x6 & x1 & x4 & x7 (reading 6,1,4 from dl)
or al, cl ; logical + apparently is regular (not exclusive) OR
and al, 1 ; clear high garbage
ret
(对于普通的 ASCII 注释,我忽略了 "complement" 部分,因为我们在开始时用一条指令处理了所有内容。)
据我所知,我们采用的是一种直接的实现方式,它只是将位获取到寄存器的底部,并使用单独的 asm 指令执行每个布尔运算(补码除外)。
为了做得更好,我们需要利用我们可以与一条指令并行执行的寄存器中的 8(或 16)位。我们不能轻易地打乱位以使它们彼此对齐,因为模式是不规则的。
IDK 如果有任何巧妙的方法,我们可以左移 AX 以从 AL 获取位到 AH 的底部,以及将一些位分组到 AL 的顶部。嗯,也许交替使用 shl ax
和 rol al
将位发送回 AL 的底部。但这仍然需要 7 次轮班来分隔位。 (shl ax,2
和 rol al,2
对于连在一起的连续位(7,6 和 3,2)仅在 186 上可用,并且在 CL 中计数几乎不值得)。
更可能的攻击角度是FLAGS:大多数ALU操作根据结果更新FLAGS,如果结果中的所有位都为0,则ZF设置为1,否则设置为1。这给了我们一个水平或操作跨位在一个寄存器中。由于 !(a | b)
= !a & !b
,我们可以反转输入中的非互补位,将其用作水平 AND 而不是 OR。 (我将 !
用于单个位反转。在 C 中,!
是一个逻辑非,它将任何非零数字转换为 0,这与 ~
按位 NOT 不同。)
但不幸的是,8086 没有一种简单的方法可以直接将 ZF 变成寄存器中的 0/1。 (386 添加 setcc r/m8
,例如 setz dl
根据 ZF 设置 DL = 0 或 1。)对于 CF, 是 可能的。我们可以通过使用 sub reg, 1
根据寄存器非零设置 CF,如果寄存器为 0(因为借位出现在顶部)则设置 CF。否则它会清除 CF。我们可以根据 CF 使用 sbb al, al
(减去借位)在 reg 中得到 0 / -1。 al-al 部分取消,留下 0 - CF
.
要设置使用 FLAGS,我们可以使用 AND 掩码将位分成两组。
;; UNTESTED, I might have some logic inverted.
xor al, 10100011b ; all bits are the inverse of their state in the original expression.
mov dl, al
and dl, 11010010b ; ~x[7,6,4,1]
and al, 00101101b ; ~x[5,3,2,0]
cmp dl, 1 ; set CF if that group was all zero (i.e. if the original AND was 1), else clear
sbb dl, dl ; dl = -1 or 0 for the first group
cmp al, 1
sbb al, al ; al = -1 or 0 for the second group. Fun fact: undocumented SALC does this
or al, dl ; The + in the original expression
and al, 1 ; keep only the low bit
ret
根据 SBB 在 DL 中的结果,我们可能还可以做更多的事情,例如 and al, dl
是否清除 AL 中的位。或者可能 adc al, -1
而不是 cmp al, 1
来使用 DL 的 CF 结果来影响 CF 如何从 AL 设置。
您可以使用您使用的 AND 掩码 sub dl, 11010010b
而不是减去 1
,因此如果它们都已设置,您将得到 0
,否则它会换行并设置 CF。不知道有没有用。
否定/反转的数量在您的脑海中很快变得棘手,但如果代码大小的每个字节或性能的每个周期都很重要,那么您应该研究一下。 (现在这种情况很少见,当这种情况发生时,您经常使用 SSE2 或 AVX 进行矢量化,因此您不会有标志,只是在矢量元素内按位和打包比较,将匹配变成全一和不匹配变成 0.)
注意用mov/AND拆分后,AL和DL都不能是全1,所以加1
永远不能回零。那么也许 sbb al, -1
可以添加 0 或 1 并可以设置 ZF?
如果你想分支,在 ZF 上分支可以用 jz
或 jnz
。 这甚至可能在 8086 上最好,例如如果第一个 AND 组给出 1
,我们不需要隔离另一个组。所以 xor al, ...
相应地补充位,然后 test al, mask1
/ jnz check_other_group
/ mov al,1
将是通过快速路径的一个很好的下降。
灵感来自Peter Cordes and prl的评论:
int test(char x)
{
return ((x & 0x2d) == 0x21) || ((x & 0xd2) == 0x82);
}
Godbolt (x86 msvc v19.24 /Os) 生成:
_x$ = 8 ; size = 1
int test(char) PROC ; test
mov cl, BYTE PTR _x$[esp-4]
mov al, cl
and al, 45 ; 0000002dH
cmp al, 33 ; 00000021H
je SHORT $LN3@test
and cl, 210 ; 000000d2H
cmp cl, 130 ; 00000082H
je SHORT $LN3@test
xor eax, eax
ret 0
$LN3@test:
mov eax, 1
ret 0
int test(char) ENDP ; test
我对汇编很陌生
考虑以下函数:
其中'+'代表'Or'逻辑门和变量的串联,代表'And'逻辑门。
如何在emu8086中实现这样的功能?鉴于输入参数可能代表寄存器的位
AL,例如,输出会将其值更改为 0 或 1。
更新:
这是我所做的,我知道它写得不好,如果有任何建议或更简单的方法让我知道,它似乎确实有效
感谢大家的帮助,尤其是 peter。
org 100h
mov al, 0A3h pour le test
mov ah, al
and ah, 01h ;ah = x0
shr al, 1
mov bl, al
and bl, 01h ;bl = x1
shr al, 1
mov bh, al
and bh, 01h
not bh
and bh, 01h ;bh = !x2
shr al, 1
mov cl, al
and cl, 01h
not cl
and cl, 01h ;cl = !x3
shr al, 1
mov ch, al
and ch, 01h
not ch
and ch, 01h ;ch = !x4
shr al, 1
mov dl, al
and dl, 01h ;x5 = dl
shr al, 1
mov dh, al
and dh, 01h
not dh
and dh, 01h ;dh = !x6
shr al, 1 ;al = x7
and bh, dl
and bh, cl
and bh, ah ;!x2 and x5 and !x3 and x0
and dh, bl
and dh, ch
and dh, al ;!x6 and x1 and !x4 and x7
or dh, bh
mov ah, dh ;resultat dans ah
ret
您确定具有四个 x_n
值的表达式应该是按位 AND,而不是将它们连接成 4 位值?然后二进制加法?因为我可能已经猜到了。如果是这样,请参阅 https://codegolf.stackexchange.com/a/203610 以了解移位和 rcl reg, 1
在一对寄存器之间拆分位的方法。或者在带有 BMI2 的现代 x86 上,您可以使用 2x pext
和 add
来做到这一点。
表达式在每个组中的位都按特定顺序排列,而不仅仅是升序或降序这一事实可能是他们希望您解压缩字节的线索分成两个 4 位整数并用它做一个正常的 +
。
如果我们假设您的 asm 是正确函数的示例
这个答案的其余部分是关于优化你的 asm 中的操作,它执行两组 AND 和 OR,它们一起产生一个布尔值,在中产生 0
或 1
AL.
您可以对仅分别提取每一位的简单/直接实现进行一些改进。例如您不需要在 之前和 之后进行 AND 操作。第一个 AND 将使高位全为 0,然后 NOT 使它们为 1,然后第二个 AND 使它们再次为零。
mov bh, al
; and bh, 01h ; This is pointless
not bh
and bh, 01h ;bh = !x2
你可以更进一步:你纯粹使用按位运算,只关心每个寄存器中的低位。 你可以在最后 and al, 1
一次隔离你想要的位,所有临时对象都在其高位中携带垃圾。
要翻转 一些 位但不是全部,请使用带有常量掩码的 XOR。例如要翻转 AL 中的位 6、4、3、2 并保持其他位不变,请使用 xor al, 01011100b
1。然后你可以转移和移动到单独的寄存器而不需要任何 NOT 指令。
脚注 1:结尾的 b
表示基数 2 / 二进制。如果 emu8086 支持它,或者如果您必须编写等效的十六进制,它在 MASM syntax、IDK 中有效。
你可以直接进入这些寄存器而不是先提取,所以你只需要两个暂存器。
xor al, 01011100b ; complement bits 6,4,3,2
mov cl, al ; x0, first bit of the 2&5&3&0 group
shr al, 1
mov dl, al ; x1, first bit of the 6&1&4&7 group
shr al, 1
and cl, al ; AND X2 into the first group, X2 & x0
shr al, 1
and cl, al ; cl = X2 & X3 & x0
... ; cl = 2&5&3&0, dl = 6&1&4 with a few more steps
shr al, 1 ; AL = x7
and al, dl ; AL = x6 & x1 & x4 & x7 (reading 6,1,4 from dl)
or al, cl ; logical + apparently is regular (not exclusive) OR
and al, 1 ; clear high garbage
ret
(对于普通的 ASCII 注释,我忽略了 "complement" 部分,因为我们在开始时用一条指令处理了所有内容。)
据我所知,我们采用的是一种直接的实现方式,它只是将位获取到寄存器的底部,并使用单独的 asm 指令执行每个布尔运算(补码除外)。
为了做得更好,我们需要利用我们可以与一条指令并行执行的寄存器中的 8(或 16)位。我们不能轻易地打乱位以使它们彼此对齐,因为模式是不规则的。
IDK 如果有任何巧妙的方法,我们可以左移 AX 以从 AL 获取位到 AH 的底部,以及将一些位分组到 AL 的顶部。嗯,也许交替使用 shl ax
和 rol al
将位发送回 AL 的底部。但这仍然需要 7 次轮班来分隔位。 (shl ax,2
和 rol al,2
对于连在一起的连续位(7,6 和 3,2)仅在 186 上可用,并且在 CL 中计数几乎不值得)。
更可能的攻击角度是FLAGS:大多数ALU操作根据结果更新FLAGS,如果结果中的所有位都为0,则ZF设置为1,否则设置为1。这给了我们一个水平或操作跨位在一个寄存器中。由于 !(a | b)
= !a & !b
,我们可以反转输入中的非互补位,将其用作水平 AND 而不是 OR。 (我将 !
用于单个位反转。在 C 中,!
是一个逻辑非,它将任何非零数字转换为 0,这与 ~
按位 NOT 不同。)
但不幸的是,8086 没有一种简单的方法可以直接将 ZF 变成寄存器中的 0/1。 (386 添加 setcc r/m8
,例如 setz dl
根据 ZF 设置 DL = 0 或 1。)对于 CF, 是 可能的。我们可以通过使用 sub reg, 1
根据寄存器非零设置 CF,如果寄存器为 0(因为借位出现在顶部)则设置 CF。否则它会清除 CF。我们可以根据 CF 使用 sbb al, al
(减去借位)在 reg 中得到 0 / -1。 al-al 部分取消,留下 0 - CF
.
要设置使用 FLAGS,我们可以使用 AND 掩码将位分成两组。
;; UNTESTED, I might have some logic inverted.
xor al, 10100011b ; all bits are the inverse of their state in the original expression.
mov dl, al
and dl, 11010010b ; ~x[7,6,4,1]
and al, 00101101b ; ~x[5,3,2,0]
cmp dl, 1 ; set CF if that group was all zero (i.e. if the original AND was 1), else clear
sbb dl, dl ; dl = -1 or 0 for the first group
cmp al, 1
sbb al, al ; al = -1 or 0 for the second group. Fun fact: undocumented SALC does this
or al, dl ; The + in the original expression
and al, 1 ; keep only the low bit
ret
根据 SBB 在 DL 中的结果,我们可能还可以做更多的事情,例如 and al, dl
是否清除 AL 中的位。或者可能 adc al, -1
而不是 cmp al, 1
来使用 DL 的 CF 结果来影响 CF 如何从 AL 设置。
您可以使用您使用的 AND 掩码 sub dl, 11010010b
而不是减去 1
,因此如果它们都已设置,您将得到 0
,否则它会换行并设置 CF。不知道有没有用。
否定/反转的数量在您的脑海中很快变得棘手,但如果代码大小的每个字节或性能的每个周期都很重要,那么您应该研究一下。 (现在这种情况很少见,当这种情况发生时,您经常使用 SSE2 或 AVX 进行矢量化,因此您不会有标志,只是在矢量元素内按位和打包比较,将匹配变成全一和不匹配变成 0.)
注意用mov/AND拆分后,AL和DL都不能是全1,所以加1
永远不能回零。那么也许 sbb al, -1
可以添加 0 或 1 并可以设置 ZF?
如果你想分支,在 ZF 上分支可以用 jz
或 jnz
。 这甚至可能在 8086 上最好,例如如果第一个 AND 组给出 1
,我们不需要隔离另一个组。所以 xor al, ...
相应地补充位,然后 test al, mask1
/ jnz check_other_group
/ mov al,1
将是通过快速路径的一个很好的下降。
灵感来自Peter Cordes and prl的评论:
int test(char x)
{
return ((x & 0x2d) == 0x21) || ((x & 0xd2) == 0x82);
}
Godbolt (x86 msvc v19.24 /Os) 生成:
_x$ = 8 ; size = 1
int test(char) PROC ; test
mov cl, BYTE PTR _x$[esp-4]
mov al, cl
and al, 45 ; 0000002dH
cmp al, 33 ; 00000021H
je SHORT $LN3@test
and cl, 210 ; 000000d2H
cmp cl, 130 ; 00000082H
je SHORT $LN3@test
xor eax, eax
ret 0
$LN3@test:
mov eax, 1
ret 0
int test(char) ENDP ; test