a bit of an obfuscated operations

Index > Main > a bit of an obfuscated operations

Author

Thread

Ali.Z

Joined: 08 Jan 2018
Posts: 719

Ali.Z 21 Aug 2024, 11:11

https://en.wikipedia.org/wiki/Functional_completeness

they say a functional complete SET is a SET of AND,NOT.

OR(A,B) = NOT(AND(NOT(A),NOT(B)))
XOR(A,B) = AND(NOT(AND(A,B)),NOT(AND(NOT(A),NOT(B))))
ADD(A,B) = (A+B) ;sorry i cannot make addition using and not
SUB(A,B) = NOT(ADD(NOT(A),B))

looking at the disassembly of these can be painful, imagine having more of these for other operations...
like the xor the quite long, i can think of shl being even longer, i wouldnt use the word long tbh.

things like ror, mul, div are extremely complex.

_________________
Asm For Wise Humans

21 Aug 2024, 11:11

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 21 Aug 2024, 11:37

ADD is the same as XOR, and the carry is AND.

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

21 Aug 2024, 11:37

Furs

Joined: 04 Mar 2016
Posts: 2507

Furs 21 Aug 2024, 13:34

Ali.Z wrote:

things like ror, mul, div are extremely complex.

Like everything, there's layers upon layers.

If you factor everything, a single instruction is extremely complex on a modern CPU. But then you look at a software function made up of thousands of these instructions, and that's just a low level function!

A high level function typically just calls a lot of other low level functions and so on. If you were to analyze the high level function in its entire down to the atom you'd go insane at the complexity.

It's all about looking at different layers.

21 Aug 2024, 13:34

macomics

Joined: 26 Jan 2021
Posts: 960
Location: Russia

macomics 21 Aug 2024, 13:53

ADD and SUB are mathematical operations, but the statement that AND and NOT are a complete set refers to logical operations. For functions with two arguments, there are only 16 of them. All 16 can be represented via the AND and NOT operations.

Code:

X, Y = R
{ZERO}
0, 0 = 0
0, 1 = 0
1, 0 = 0
1, 1 = 0
{AND}
0, 0 = 0
0, 1 = 0
1, 0 = 0
1, 1 = 1
{IMPY, AND(X, NOT(Y))}
0, 0 = 0
0, 1 = 0
1, 0 = 1
1, 1 = 0
{EQUX}
0, 0 = 0
0, 1 = 0
1, 0 = 1
1, 1 = 1
{IMPX, AND(NOT(X), Y)}
0, 0 = 0
0, 1 = 1
1, 0 = 0
1, 1 = 0
{EQUY}
0, 0 = 0
0, 1 = 1
1, 0 = 0
1, 1 = 1
{XOR}
0, 0 = 0
0, 1 = 1
1, 0 = 1
1, 1 = 0
{OR}
0, 0 = 0
0, 1 = 1
1, 0 = 1
1, 1 = 1
{NOR}
0, 0 = 1
0, 1 = 0
1, 0 = 0
1, 1 = 0
{EQU, NXOR}
0, 0 = 1
0, 1 = 0
1, 0 = 0
1, 1 = 1
{NOTY}
0, 0 = 1
0, 1 = 0
1, 0 = 1
1, 1 = 0
{NIMPX, NOT(AND(NOT(X), Y))}
0, 0 = 1
0, 1 = 0
1, 0 = 1
1, 1 = 1
{NOTX}
0, 0 = 1
0, 1 = 1
1, 0 = 0
1, 1 = 0
{NIMPY, NOT(AND(X, NOT(Y)))}
0, 0 = 1
0, 1 = 1
1, 0 = 0
1, 1 = 1
{NAND}
0, 0 = 1
0, 1 = 1
1, 0 = 1
1, 1 = 0
{ONE}
0, 0 = 1
0, 1 = 1
1, 0 = 1
1, 1 = 1

21 Aug 2024, 13:53

Ali.Z

Joined: 08 Jan 2018
Posts: 719

Ali.Z 23 Aug 2024, 06:06

bitRAKE wrote:

ADD is the same as XOR, and the carry is AND.

i dont get it, carry is AND?

_________________
Asm For Wise Humans

23 Aug 2024, 06:06

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20344
Location: In your JS exploiting you and your system

revolution 23 Aug 2024, 06:11

If both input bits are 1 then the carry is 1. Therefore carry is the AND of the two bits.

Only works for the least significant bits. If you have more bits, then adding in the carry from the previous stage makes things a bit more complicated.

23 Aug 2024, 06:11

bitRAKE

Joined: 21 Jul 2003
Posts: 4043
Location: vpcmpistri

bitRAKE 23 Aug 2024, 08:06

Ali.Z wrote:

bitRAKE wrote:
ADD is the same as XOR, and the carry is AND.

i dont get it, carry is AND?

Here is another way to look at it ...

Code:

half_adder:
        virtual at rsp+8
                .A      dd ?,?
                .B      dd ?,?
                .param_bytes := $ - $$
        end virtual
        mov eax, [.A]
        mov edx, [.A]
        xor eax, [.B]   ; sum
        and edx, [.B]   ; carry
        retn .param_bytes

full_adder:
        virtual at rsp+8
                .A      dd ?,?
                .B      dd ?,?
                .C      dd ?,? ; carry input
                .param_bytes := $ - $$
        end virtual
        ccall half_adder, [.A], [.B]
        mov ecx, edx    ; partial carry
        ccall half_adder, eax, [.C]
        or edx, ecx     ; carry
        retn .param_bytes

... doing bit additions (x32) in parallel. ccall being a macro that pushes QWORD sized values in reverse order (typical 32-bit c-calling convention in 64-bit).

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

23 Aug 2024, 08:06

Ali.Z

Joined: 08 Jan 2018
Posts: 719

Ali.Z 25 Aug 2024, 06:28

bitRAKE wrote:

Here is another way to look at it ...

thanks, it helped a lot to clear my mind.

_________________
Asm For Wise Humans

25 Aug 2024, 06:28

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum