Silent cast to unsigned

I'm a bit confused about this behaviour (gcc 4.1.2, Linux): i have function that accepts "char*" argument. Function is basicly my version of str(case)cmp() and I'm trying to optimize it for my locale and catch up with str(case)cmp(). I don't want to compile with any optimization flags. I found out that any extra argument given to function slows it down (1 more argument, and there's ~20% slowdown - tested on ~15000 strings comparing with each other). Another thing that causes slowdown is any excplicit cast (like signed to unsigned). As I use tables for fast conversion from uppercase to lowercase when that version is called (case insensitive), i just type: "c=TABLE[c]" (c is current character). Example:

Code:

---

int _f(char *s1, char *s2, int cs)
{
    // cs = case sensitivity (0=off)

    (register?) int i=0;      // index in string(s)
    (register?) int c1, c2;  // current char in 1st and 2nd strings

    for(;;)
    {
        c1 = s1[i];
        ...
        if (!cs) c1=TABLE[c1];
        ...
    }
}

---

(I'll ignore slowdown by "cs" argument for now...)

The thing that bugs me is that c1 CAN become negative (i've checked) and it's EXPECTED as no cast is being done, but then again when doing TABLE[c1] it gets silently cast to unsigned (as no crash occurs) when used as index. Is this normal or am i missing something?

EDIT: Oh yes, TABLE is plain "int TABLE[256]" initialized before _f() call...

I'm pretty sure that a negative (higher than 128 in unsigned value) will lead to a negative index into your table. That may not cause the system to crash, but certainly would address outside of your intended range - it may simply be that there is sufficient global data BEFORE your TABLE variable to allow the index of that large negative range.

--
Mats

Quote:

---

Originally Posted by matsp

I'm pretty sure that a negative (higher than 128 in unsigned value) will lead to a negative index into your table. That may not cause the system to crash, but certainly would address outside of your intended range - it may simply be that there is sufficient global data BEFORE your TABLE variable to allow the index of that large negative range.

--
Mats

---

Thing is, on ~15000 strings i get EXACTLY same number of duplicates doing str(case)cmp and this function (15xx for case insensitive, 14xx for case sentitive), so this _f() thing seems to be working...

Quote:

---

Originally Posted by rasta_freak

Thing is, on ~15000 strings i get EXACTLY same number of duplicates doing str(case)cmp and this function (15xx for case insensitive, 14xx for case sentitive), so this _f() thing seems to be working...

---

And you use strings that have "negative" content in them?

--
Mats

Quote:

---

Originally Posted by matsp

And you use strings that have "negative" content in them?

--
Mats

---

There are locale characters (UTF8 encoding) - Croatian.
(But this version ignores them - treats every char separately)
EDIT: Oh, and locale is set to "C" (on boot), so nobody knows (str...cmp()) where i am ;)

And how is TABLE filled in - by an initializer or by a loop?

--
Mats

Quote:

---

Originally Posted by matsp

And how is TABLE filled in - by an initializer or by a loop?

--
Mats

---

Code:

---

int TABLE[256];
{
    int i;
    for (i=0; i<256; i++)
    {
        if ((i>='A') && (i<='Z'))
            TABLE[i] = i + 32;
        else
            TABLE[i] = i;
    }
}

---

Well, I can certainly say that gcc 3.4 does use the movsbl instruction, which is "mov signed byte to long", and thus does use negative index within the array.

You may want to compile this:

Code:

---

int table[256];

int func(char c)
{
  return table[c];
}

int main()
{
  int i;
  for(i = 0; i < 255; i++)
    func(i);
  return 0;
}

---

Use gcc -S xx.c, then look at xx.s to see if it is using movsbl to produce the index into table.

--
Mats

Couldn't attatch it:

Code:

---

.file        "main.c"
        .text
.globl func
        .type        func, @function
func:
        pushl        %ebp
        movl        %esp, %ebp
        subl        $4, %esp
        movl        8(%ebp), %eax
        movb        %al, -4(%ebp)
        movsbl        -4(%ebp),%eax
        movl        table(,%eax,4), %eax
        leave
        ret
        .size        func, .-func
.globl main
        .type        main, @function
main:
        leal        4(%esp), %ecx
        andl        $-16, %esp
        pushl        -4(%ecx)
        pushl        %ebp
        movl        %esp, %ebp
        pushl        %ecx
        subl        $20, %esp
        movl        $0, -8(%ebp)
        jmp        .L4
.L5:
        movl        -8(%ebp), %eax
        movsbl        %al,%eax
        movl        %eax, (%esp)
        call        func
        addl        $1, -8(%ebp)
.L4:
        cmpl        $254, -8(%ebp)
        jle        .L5
        movl        $0, %eax
        addl        $20, %esp
        popl        %ecx
        popl        %ebp
        leal        -4(%ecx), %esp
        ret
        .size        main, .-main
        .comm        table,1024,32
        .ident        "GCC: (GNU) 4.1.2 (Ubuntu 4.1.2-0ubuntu4)"
        .section        .note.GNU-stack,"",@progbits

---

Code:

---

func:
        pushl        %ebp
        movl        %esp, %ebp
        subl        $4, %esp
        movl        8(%ebp), %eax
        movb        %al, -4(%ebp)
        movsbl        -4(%ebp),%eax
        movl        table(,%eax,4), %eax
        leave
        ret

---

The red line above sign-extends the value of the char, so a negative char will be converted to a negative integer.

--
Mats

Quote:

---

Originally Posted by matsp

Code:

---

func:
        pushl        %ebp
        movl        %esp, %ebp
        subl        $4, %esp
        movl        8(%ebp), %eax
        movb        %al, -4(%ebp)
        movsbl        -4(%ebp),%eax
        movl        table(,%eax,4), %eax
        leave
        ret

---

The red line above sign-extends the value of the char, so a negative char will be converted to a negative integer.

--
Mats

---

So how come I get same results? Strings are pretty random (it's list of mp3 files on HDD, with at least 20% of them having those 'locals'). And if i use explicit cast to unsigned, i see slowdown and same results ! This bugs me whole day... (why did i go "optimize" it ???)

Quote:

---

Originally Posted by rasta_freak

So how come I get same results? Strings are pretty random (it's list of mp3 files on HDD, with at least 20% of them having those 'locals'). And if i use explicit cast to unsigned, i see slowdown and same results ! This bugs me whole day... (why did i go "optimize" it ???)

---

You may want to check your actual code - maybe it does something different there? Just user your usual build options and the -S option.

Edit: Oh, by the way, if you do exactly the same thing for both sides, e.g.

Code:

---

        c1 = s1[i];
        ...
        if (!cs) c1=TABLE[c1];
        ...
        c2 = s1[i];
        ...
        if (!cs) c2=TABLE[c2];
        ...
        if (c2 == c1) ...

---

Then you would read the same incorrect value for both sides, so although you are not reading the CORRECT value, it will still match.


--
Mats

Quote:

---

Originally Posted by matsp

You may want to check your actual code - maybe it does something different there? Just user your usual build options and the -S option.

Edit: Oh, by the way, if you do exactly the same thing for both sides, e.g.

Code:

---

        c1 = s1[i];
        ...
        if (!cs) c1=TABLE[c1];
        ...
        c2 = s1[i];
        ...
        if (!cs) c2=TABLE[c2];
        ...
        if (c2 == c1) ...

---

Then you would read the same incorrect value for both sides, so although you are not reading the CORRECT value, it will still match.


--
Mats

---

It's actually:

Code:

---

for (;;)
{
    c1 = s1[i];
    c2 = s2[i];

    if (c1)
    {
        // second empty ?
        if (!c2) return(1);
    }
    else
    {
        // first empty, second ?
        if (c2) return(-1);
        // both empty:
        return(0);
    }

    if (!cs)
    {
        c1 = TABLE[c1];
        c2 = TABLE[c2];
    }
   
    if (c1==c2) { i++; continue; }
    if (c1 > c2) return(1);
    return(-1);
}

---

This is assembly of table access (table is called TACTL there, it's same thing)

Code:

---

        .loc 1 4305 0                                                                                             
        movl    -8(%ebp), %eax                                                                                   
        movl    TACTL.15685(,%eax,4), %eax                                                                       
        movl    %eax, -8(%ebp)

---

Perhaps you could initialize the table in a way and reference it through a (static) pointer that would allow you to use negative indices (if the signedness of the char type is implementation defined as I suspect you might set it all up at runtime - or may-be at compile time through some tricks).

I also wonder why you are determining the case sensitivity within the function. There is already strcmp which should be good for case sensitive comparisons, so you'd only need to implement the case insensitive version. And if you want a function that makes this choice through a third parameter, that would only call either strcmp or your version.

Also, do you need those ints. If you figure out the correct indexing, it needn't be more complex than

Code:

---

while (*s1 && *s2 && table[*s1] == table[*s2]) {
    ++s1;
    ++s2;
}
return something

---

I would also suggest fixing the function's prototype. It doesn't change the strings, so they should be const char*'s.

It looks like -8(%ebp) already contains a long value, so I suspect there is a conversion from byte to long [with or without sign extension] somewhere else in the code.

Like I said earlier, you will find that c1 and c2 are the same value after the read of the table. You may want to add:

Code:

---

    if ((c1 & ~32) != TABLE[c1] & ~32)
        printf("c1 (%d) does not match TABLE[c1] (%d"), c1, TABLE[c1]);

---

to your code.

--
Mats

Quote:

---

Originally Posted by anon

Perhaps you could initialize the table in a way and reference it through a (static) pointer that would allow you to use negative indices (if the signedness of the char type is implementation defined as I suspect you might set it all up at runtime - or may-be at compile time through some tricks).

I also wonder why you are determining the case sensitivity within the function. There is already strcmp which should be good for case sensitive comparisons, so you'd only need to implement the case insensitive version. And if you want a function that makes this choice through a third parameter, that would only call either strcmp or your version.

Also, do you need those ints. If you figure out the correct indexing, it needn't be more complex than

Code:

---

while (*s1 && *s2 && table[*s1] == table[*s2]) {
    ++s1;
    ++s2;
}
return something

---

I would also suggest fixing the function's prototype. It doesn't change the strings, so they should be const char*'s.

---

Yes, it's now only for testing. Later on i will only have case insensitive version. But thanks for other tips...

EDIT1: deleted.
Yes i get those messages, and they show indexing is wrong, right?

EDIT2:
But what about if c1 is negative, it gets indexed in table OK, but as TABLE[] is initialized with POSITIVE integers - c1 gets converted to positive and that test fails because of that?

EDIT3:
Solved. It gives 0 from "outter space", so it never crashes (as I expected)...

Thanks matsp ;)

EDIT: How can I assure that I get SIGSEGV or anything on such invalid access?

Quote:

---

Originally Posted by rasta_freak

Thanks matsp ;)

EDIT: How can I assure that I get SIGSEGV or anything on such invalid access?

---

Realistically, you can't. The reason being that you can not control where in memory your TABLE ends up, so you can't guarantee that what is before or after it is invalid memory. That is what you have assert and similar functionality for - checking for things that should not matter.

By the way, if you compile with optimization enabled, I suspect there will be no big difference in the form that casts your char to unsigned char for the table access.

--
Mats