How do I count the occurence of a char in a string in i386?

Question

I'm a newbie to 80386 assembly language. Currently struggling on a school assignment that asks to write a function in assembly language that will be called in a c program.

extern int count(char *string, char c);

I think I have a sense of how this should be done, but still struggling with choosing the right instruction(instruction ends with 'b', 'w' or 'l') and perhaps the "right" register, I know there are some that are reserved to certain purposes.

.text
.global count

count:
    pushl   %ebp        # set up stack frame
    movl    %esp,%ebp   # save %esp in %ebp
    subl    $12, %esp   # automatic variables
    movl    $0, %eax    # initialize %eax to 0
    movl    8(%ebp), %esi   # pointer to s
    movb    12(%ebp), %bh   # pointer to c

check:
    movb    (%esi), %bl # move the first char in s to %bl
    cmp     0, %bl      # if the char is \0 
    je      done        # job is done

    cmp     %bh, %bl    # else compare the char to %bh
    je      found1      # if match increase the counter
    incb    %bl         # else move to next char
    jmp     check

found1:
    addl    $1, %eax    # found a match
    incb    %bl
    jmp     check       # go back to the beginning of check
    
done:
    movl    %ebp, %esp  # restore %esp from %ebp
    popl    %ebp        # restore %ebp
    ret

.end

My understanding of this program is that it should store the address of two values(string and char) into two registers. Then access the string char by char and compare it with the char stored in another register. If a match is found increase the return value in %eax, otherwise goes to the next char in the string until the end\0 is reached.

My program seems to be stuck in a loop as it does not crash either output a result.

Any help will be appreciated.

Try changing `incb %bl` to `incl %esi` (disclaimer: I am not used to AT&T syntax). — 500 - Internal Server Error, Oct 21 '21 at 20:39
this got me out of the loop but dumped me a lot of garbage characters lol @500-InternalServerError — Zhihan L, Oct 21 '21 at 20:51
Make sure your function preserves the value in `ebx` on entry. Push/pop it, or else use e.g. `ecx`(`ch`, `cl` instead). — 500 - Internal Server Error, Oct 21 '21 at 20:55
Please state what calling conventions you are using (or at least the OS that this is to run on, which usually determines those conventions). — Nate Eldredge, Oct 21 '21 at 21:12
You should use your debugger and execute the code step by step. — Jabberwocky, Oct 21 '21 at 21:18
@ZhihanL: Ok, but that doesn't really answer the question. What OS will run in the VM? If it's bare metal, what compiler will be used to build the C code that calls yours? We need to know things like what registers it is expecting you to save. — Nate Eldredge, Oct 21 '21 at 21:26
@NateEldredge, I'm sorry that I don't know exactly what the calling conventions mean. I found this on my given makefile. ``CC = gcc`` ``CFLAGS = -gdwarf-2 -gstrict-dwarf -march=i586 -m32 -fno-builtin -fno-stack-protector -nostdlib -c -Wall -I$(PC_INC)`` ``AS = as --32`` ``NM = nm`` ``LD = ld -m elf_i386`` Is this what you talking about — Zhihan L, Oct 21 '21 at 21:35
[Calling conventions](https://en.wikipedia.org/wiki/Calling_convention). If it's gcc then you are most likely using the [SysV ABI](https://wiki.osdev.org/Calling_Conventions). Your instructor should have explained some of these conventions to you, or given you a reference to follow: how arguments are placed on the stack, what registers must be saved and restored, who is responsible for stack cleanup. You can't write correct code without knowing what conventions it is supposed to follow. — Nate Eldredge, Oct 21 '21 at 21:53
@NateEldredge, I have updated a graph on the post. Would you mind taking a look? does that mean ``esp`` and ``ebp`` should be saved and restored? — Zhihan L, Oct 21 '21 at 21:59
@ZhihanL "My understanding of this program is that it should store the **address** of two values (string and char)" The second argument is not an address. It's not a pointer to a char but rather **it is the char itself**. — Sep Roland, Oct 22 '21 at 22:24

score 5 · Accepted Answer · edited Oct 22 '21 at 22:14

5

I don't think there is a real reason to save %esp to %ebp, or to subtract from %esp. You do need to save %esi. I think the a, b, c, and d registers can be safely lost, but if not (it's been some time since I used assembly), you need to save %ebx as well.
(Update: as @NateEldredge pointed out, %ebx has to be preserved - and I forgot to update the stack pointer. Yes, it has been too long).

count:
    pushl   %esi             # save %esi as we use it
    pushl   %ebx
    # "In assembly language, all the labels and numeric constants used 
    #  as immediate operands (i.e. not in an address calculation like 
    #  3(%eax,%ebx,8)) are always prefixed by a dollar sign."
    #  https://flint.cs.yale.edu/cs421/papers/x86-asm/asm.html
    movl    12(%esp), %esi   # pointer to s
    movb    16(%esp), %bh    # char
    # I think it's more common "xor %eax, %eax"
    movl    $0, %eax         # initialize %eax to 0

check:
    movb    (%esi), %bl      # move the current char in s to %bl
    cmp     $0, %bl          # if the char is \0 
    je      done             # job is done

    cmp     %bh, %bl         # else compare the char to %bh
    je      found1           # if match increase the counter
    # We must increase the pointer to the character, not %bl
    incl    %esi             # else move to next char
    jmp     check
found1:
    addl    $1, %eax         # found a match
    # incb    %bl
    incl    %esi             # move to next char
    jmp     check            # go back to the beginning of check
done:
    popl    %ebx
    popl    %esi             # restore %esi
    ret

.end

You could also invert the test to save some instructions:

    cmp     %bh, %bl         # else compare the char to %bh
    jne     notfound         # if not match, skip incrementing
    addl    $1, %eax         # found a match
notfound:
    incl    %esi             # move to next char
    jmp     check

edited Oct 22 '21 at 22:14

Sep Roland

33,889
7
43
76

answered Oct 21 '21 at 21:08

LSerni

55,617
10
65
107

3

`ebx` is call-preserved in the SysV ABI, so yes, it should be saved. – Nate Eldredge Oct 21 '21 at 21:11
1

And so then your `esp` offsets need to be adjusted. – Nate Eldredge Oct 21 '21 at 21:13
@NateEldredge now *that's* embarrassing. It's really been too long. I must either brush up my assembly or stop answering assembly questions, the damage I make is more than the advantage :-( – LSerni Oct 21 '21 at 21:17
1

ECX and EDX are unused in your function, and it's a leaf function so there's no reason to use call-preserved registers before running out of call-clobbered registers. – Peter Cordes Oct 21 '21 at 21:27
@PeterCordes you are right, of course -- I was just trying to change the original code as little as possible. – LSerni Oct 21 '21 at 21:30
1

Although you probably *do* want to use an extra register so you aren't [creating false dependencies on recent CPUs by merging into the low byte of a register repeatedly](https://stackoverflow.com/questions/41573502/why-doesnt-gcc-use-partial-registers), instead using `movzbl (%esi), %edx` or something, like GCC would normally do with `-O2` or `-O3`. – Peter Cordes Oct 21 '21 at 21:31
@PeterCordes I'm afraid that's too far for my rusty assembly. What's the problem with moving into the lower byte of a register? I frankly don't know what a false dependency even *is*, even if I surmise from the context it must have to do with execution optimization. – LSerni Oct 21 '21 at 21:38
@LSerni Hi, thanks for your help. I just tried it and it runs with no issue except it always output counts as 0. Do you know what could cause that? – Zhihan L Oct 21 '21 at 21:39
@ZhihanL I *think* I do, but as you see, I'm rusty as hell. It's what NateEldredge was telling you in a comment: your C code calls the ASM code, but *the codes must agree on how to talk to each other*. For example, C might say, "If you return me an unsigned int, put it into EAX". But the "agreement" could be different. So your ASM routine is putting the counter in EAX, but *where is the C code reading the expected return value from*? That depends on the ABI (Application Binary Interface). Using EAX is the most convenient choice, but... you're in a VM running we don't know what, so... – LSerni Oct 21 '21 at 21:47
@LSerni I see, will try to figure that out – Zhihan L Oct 21 '21 at 22:00
2

@LSerni: The link in my previous comment explains the performance effect somewhat, if you're curious. An example in [How exactly do partial registers on Haswell/Skylake perform? Writing AL seems to have a false dependency on RAX, and AH is inconsistent](https://stackoverflow.com/q/45660139) illustrates how `mov` into an 8-bit register is *not* independent of the old value on Haswell/Skylake, creating a latency bottleneck where out-of-order exec could overlap iterations on previous CPUs that renamed low-8 registers separately from the full register. – Peter Cordes Oct 21 '21 at 22:17
@ZhihanL: All 32 x86 C calling conventions return 32-bit integers in EAX (same for x86-64), that's not a problem unless your caller is hand-written and expecting something else. This code looks right to me, so if you're finding no matches, single-step in a debugger and check what pointer you actually passed. – Peter Cordes Oct 21 '21 at 22:21
@PeterCordes ...you know, I don't believe I have *ever* had my mind blown quite this much :-O . I do think I'll get back to my flint knapping for a while. – LSerni Oct 21 '21 at 22:26

score -1 · Answer 2 · answered Oct 21 '21 at 20:49

-1

I do not program in assembler so I asked gcc to compile it for me:

int count(const char *str, const char ch)
{
    int count = 0;
    while(*str) 
    {
        if(*str == ch) count++;
        str++;
    }
    return count;
}

count:
        pushl   %ebx
        movl    8(%esp), %edx
        movb    12(%esp), %cl
        movb    (%edx), %al
        xorl    %ebx, %ebx
        testb   %al, %al
        je      .L1
.L4:
        cmpb    %cl, %al
        jne     .L3
        incl    %ebx
.L3:
        incl    %edx
        movb    (%edx), %al
        testb   %al, %al
        jne     .L4
.L1:
        movl    %ebx, %eax
        popl    %ebx
        ret

answered Oct 21 '21 at 20:49

0___________

60,014
4
34
74

What GCC version / options is this? Weird that it's using `movb` loads instead of `movzbl`; normally you only get that at `-Os`, but then it would also be using `-fno-omit-frame-pointer`. https://godbolt.org/z/j65bsvxfz – Peter Cordes Oct 21 '21 at 21:35
@PeterCordes https://godbolt.org/z/MTbz1b8xv – 0___________ Oct 21 '21 at 21:42
1

Oh, you used `-mtune=i386`? That's weird; I think the question is using it as the name of the ISA, not that they actually want to tune for a real 80386 CPU without caring about performance on modern CPUs in 32-bit mode. (Although they do even say 80386 unlike most 32-bit questions, so possibly.) – Peter Cordes Oct 21 '21 at 22:14

How do I count the occurence of a char in a string in i386?

2 Answers2