Thread: Silent cast to unsigned

  1. #1
    Registered User
    Join Date
    Jul 2008
    Posts
    133

    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...
    Last edited by rasta_freak; 08-06-2008 at 03:01 AM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by matsp View Post
    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...

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by rasta_freak View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by matsp View Post
    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
    Last edited by rasta_freak; 08-06-2008 at 03:19 AM.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    And how is TABLE filled in - by an initializer or by a loop?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by matsp View Post
    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;
        }
    }

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #9
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    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

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by matsp View Post
    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 ???)

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by rasta_freak View Post
    So how come I get same results? Strings are pretty random (it's list of mp3 files on HDD, with at least 20&#37; 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
    Last edited by matsp; 08-06-2008 at 04:51 AM.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by matsp View Post
    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(&#37;ebp), %eax                                                                                     
            movl    TACTL.15685(,%eax,4), %eax                                                                         
            movl    %eax, -8(%ebp)
    Last edited by rasta_freak; 08-06-2008 at 05:10 AM.

  14. #14
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  15. #15
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 12
    Last Post: 08-11-2008, 11:02 PM
  2. Replies: 16
    Last Post: 10-29-2006, 05:04 AM
  3. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  4. Obtaining source & destination IP,details of ICMP Header & each of field of it ???
    By cromologic in forum Networking/Device Communication
    Replies: 1
    Last Post: 04-29-2006, 02:49 PM