I am currently trying to learn assembly (Intel x86) and I've made a program that simulates bit stuffing on 32bit words -> every 5 consecutive identical bits (5 0's or 5 1's), an opposite bit is inserted. In order to keep the word to its original 32bit size, the less significant bits are truncated if stuffing bits are added.
Here are a few examples:
0000 1111 0000 1111 0000 1111 0000 1111 -> 0000 1111 0000 1111 0000 1111 0000 1111
0000 1111 0000 1111 0000 1111 0000 0000 -> 0000 1111 0000 1111 0000 1111 0000 0100
0000 1111 0000 1111 0000 0000 0000 0000 -> 0000 1111 0000 1111 0000 0100 0001 0000
So this is my C++ program that tests if everything works correctly, but the last two don't work, and I can't figure out why. I ran it several times by following every step the program doesn with the IDE Debugger, and it seems to do exactly what I want it to do, but the results don't follow...
#include <iostream>
using namespace std;
extern "C" {unsigned int bitstuffing(unsigned int a);}
int main () {
unsigned int in = 0xFFFFFFFF;
unsigned int verif = 0xFBEFBEFB;
unsigned int out = bitstuffing(in);
if (out==verif) cout<<endl<<"OK: "<<hex<<out<<dec<<endl;
else cout<<endl<<"ERROR: "<<hex<<out<<dec<<endl;
in = 0x00000000;
verif = 0x04104104;
out = bitstuffing(in);
if (out==verif) cout<<endl<<"OK: "<<hex<<out<<dec<<endl;
else cout<<endl<<"ERROR: "<<hex<<out<<dec<<endl;
in = 0xF0F0F0F; // 0000 1111 0000 1111 0000 1111 0000 1111
verif = 0xF0F0F0F; // 0000 1111 0000 1111 0000 1111 0000 1111
out = bitstuffing(in);
if (out==verif) cout<<endl<<"OK: "<<hex<<out<<dec<<endl;
else cout<<endl<<"ERROR: "<<hex<<out<<dec<<endl;
in = 0xF0F0F00; // 0000 1111 0000 1111 0000 1111 0000 0000
verif = 0xF0F0F04; // 0000 1111 0000 1111 0000 1111 0000 0100
out = bitstuffing(in);
if (out==verif) cout<<endl<<"OK: "<<hex<<out<<dec<<endl;
else cout<<endl<<"ERROR: "<<hex<<out<<dec<<endl;
in = 0xF0F0000; // 0000 1111 0000 1111 0000 0000 0000 0000
verif = 0xF0F0410; // 0000 1111 0000 1111 0000 0100 0001 0000
out = bitstuffing(in);
if (out==verif) cout<<endl<<"OK: "<<hex<<out<<dec<<endl;
else cout<<endl<<"ERROR: "<<hex<<out<<dec<<endl;
in = 0xAAAA0000; // 1010 1010 1010 1010 0000 0000 0000 0000
verif = 0xAAAA0820; // 1010 1010 1010 1010 0000 1000 0010 0000
out = bitstuffing(in);
if (out==verif) cout<<endl<<"OK: "<<hex<<out<<dec<<endl;
else cout<<endl<<"ERROR: "<<hex<<out<<dec<<endl;
in = 0x7878000; // 0000 0111 1000 0111 1000 0000 0000 0000
verif = 0x7C1F041; // 0000 0111 1100 0001 1111 0000 0100 0001
// out = 0000 0111 1100 0111 1101 0000 0100 0001
out = bitstuffing(in);
if (out==verif) cout<<endl<<"OK: "<<hex<<out<<dec<<endl;
else cout<<endl<<"ERROR: "<<hex<<out<<dec<<endl;
return 0;
}
And this is the ASM program, which is the most important
CPU 386
%include "io.inc"
section .text
global CMAIN
;0FFFFFFFFh - 0xFBEFBEFB ok
;000000000h - 0x04104104 ok
;0F0F0F0Fh - 0xF0F0F0F ok
;0F0F0F00h - 0xF0F0F04 ok
;0F0F0000h - 0xF0F0410 ok
;0AAAA0000h - 0xAAAA0820 DOESNT WORK
;07878000h - 0x7878000 DOESNT WORK
CMAIN:
mov ebp, esp; for correct debugging
PUSH EBP
MOV EBP, ESP
MOV EAX, 07878000h;[EBP+8] ; places message (parameter) in EAX
MOV ECX, 32
MOV BL, 0 ; counts number of "0" bits
MOV BH, 0 ; counts number of "1" bits
loop1:
ROL EAX, 1
JC carry
JNC no_carry
carry:
XOR BL, BL ; resets "0" counter to 0
INC BH ; increments "1" counter
CMP BH, 5 ; if we get 5 consecutive bits of the same sign -> bitstuffing
JE stuffing_0
DEC ECX ; Decrementing ECX for loop
JNZ loop1
JZ end
no_carry:
XOR BH, BH ; resets "1" counter to 0
INC BL ; increments "0" counter
CMP BL, 5 ; if we get 5 consecutive bits of the same sign -> bitstuffing
JE stuffing_1
DEC ECX ; Decrementing ECX for loop
JNZ loop1
JZ end
stuffing_0:
XOR EDX, EDX
XOR EBX, EBX
MOV EDX, 2 ; Putting 2 in EDX for MUL operation
MUL EDX ; Multiplying EAX by 2 is like adding a 0 at the end
XOR EDX, EDX ; Resetting EDX register
DEC ECX ; Decrementing ECX twice for loop (in order to truncate bits)
DEC ECX
CMP ECX, 0
JG loop1
JLE end
stuffing_1:
XOR EDX, EDX
XOR EBX, EBX
MOV EDX, 2 ; Putting 2 in EDX for MUL operation
MUL EDX ; Multiplying EAX by 2 is like adding a 0 at the end
ADD EAX, 1 ; Adding 1 to EAX when the last bit is the zero we added is the same is adding 1 instead of zero
XOR EDX, EDX ; Resetting EDX register
DEC ECX ; Decrementing ECX twice for loop (in order to truncate bits)
DEC ECX
CMP ECX, 0
JG loop1
JLE end
end:
LEAVE
RET
So when I run this program, it works very well with the following values (they are all put in EAX)
;0FFFFFFFFh - 0xFBEFBEFB ok
;000000000h - 0x04104104 ok
;0F0F0F0Fh - 0xF0F0F0F ok
;0F0F0F00h - 0xF0F0F04 ok
;0F0F0000h - 0xF0F0410 ok
But doesn't work with the following
;0AAAA0000h - 0xAAAA0820 DOESNT WORK
;07878000h - 0x7878000 DOESNT WORK
If anyone can spot the problem it would be of great help!
To stuff the new bit you multiply by 2 which is just a convoluted way to do a shift left. This will discard the most significant bit, so you are not discarding from the least significant position of the original value, rather, you are basically overwriting the following bit with your stuffed bit.
In short, your code does not do what you say it does :)
A possible solution (gas syntax):
.intel_syntax noprefix
.global main
main:
sub esp, 12
mov [esp + 8], ebx
xor ebx, ebx
test_loop:
mov eax, [in + 4 * ebx]
mov dword ptr [esp], eax
call bitstuffing
mov [esp + 8], eax
cmp eax, [verify + 4 * ebx]
mov dword ptr [esp], offset ok
je got_fmt
mov dword ptr [esp], offset error
got_fmt:
mov eax, [in + 4 * ebx]
mov [esp + 4], eax
call printf
inc ebx
cmp ebx, 7
jb test_loop
mov ebx, [esp + 8]
add esp, 12
xor eax, eax
ret
bitstuffing:
push ebp
mov ebp, esp
push ebx
mov cl, 32 # 32 bits to go
xor eax, eax # the output
mov edx, [ebp + 8] # the input
xor bl, bl # the run count
next_bit:
dec cl # more bits?
js done # no
shl edx, 1 # consume from the input into CF
rcl eax, 1 # copy to output from CF
test bl, bl # first bit always matches
jz match
test al, 3 # do we have 00 or 11 in the low 2 bits?
jnp reset # no, start counting again
match:
inc bl
cmp bl, 5 # did 5 bits match?
jb next_bit # no, keep going
dec cl # space for stuffed bit?
js done # no
mov ebx, eax # make a copy
and ebx, 1 # isolate LSB
xor ebx, 1 # flip it
shl eax, 1 # make space for it
or eax, ebx # stuff it
reset:
mov bl, 1 # already have length 1
jmp next_bit
done:
pop ebx
mov esp, ebp
pop ebp
ret
.data
ok: .string "OK: 0x%08x => 0x%08x\n"
error: .string "ERROR: 0x%08x => 0x%08x\n"
in: .int 0xFFFFFFFF, 0x00000000, 0x0F0F0F0F, 0x0F0F0F00, 0x0F0F0000, 0xAAAA0000, 0x07878000
verify: .int 0xFBEFBEFB, 0x04104104, 0x0F0F0F0F, 0x0F0F0F04, 0x0F0F0410, 0xAAAA0820, 0x07C1F041
See it in operation at ideone.com.