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

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...

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

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

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

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 ???)

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

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