Bitstuffing in assembly not working as intended

Question

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!

We are not a debugging service. What exactly do you not understand? What is your question? — Dwayne Towell, May 11 '15 at 00:53
@DwayneTowell Sorry o.o I'm pretty tired and forgot to post the specific problems. I'll edit it immediately — Iocust, May 11 '15 at 00:58
Note that standard C calling convention doesn't allow you to destroy `ebx`. That may or may not have anything to do with your immediate problem, though. You should add `push ebx/pop ebx` around your code. — Jester, May 11 '15 at 01:28
@Jester Thank you! Though it didn't have any effect on my problem ^^' — Iocust, May 11 '15 at 01:38

Jester · Accepted Answer · 2015-05-11T22:02:04.117

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.

I see! Though I fail to see a way for me to do it otherwise. Perhaps using masks would help? I have no experience with those though, — Iocust, May 11 '15 at 19:23
The rotate-in-place approach makes it hard. You can just use separate input and output registers, and then you can stuff your bit easily. See updated answer for a possible solution. — Jester, May 11 '15 at 22:02
Thank you very much! That seems to be what I'm looking for, though I admit I wouldn't have thought of doing it that way. Cheers! — Iocust, May 16 '15 at 00:38

Bitstuffing in assembly not working as intended

1 Answers1