• Open Menu Close Menu
  • Apple
  • Shopping Bag
  • Apple
  • Mac
  • iPad
  • iPhone
  • Watch
  • TV
  • Music
  • Support
  • Search apple.com
  • Shopping Bag

Lists

Open Menu Close Menu
  • Terms and Conditions
  • Lists hosted on this site
  • Email the Postmaster
  • Tips for posting to public mailing lists
Re: Hex to NSString or NSData
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Hex to NSString or NSData

  • Subject: Re: Hex to NSString or NSData
  • From: Gwynne Raskind <email@hidden>
  • Date: Sat, 9 May 2009 19:05:28 -0400
On May 9, 2009, at 5:20 PM, Marcel Weiher wrote: 
int hexDigitToInt(char d)
{
  int result;
  switch (d) {
      case '0': result = 0; break;
      case '1': result = 1; break;
[snip]
      case 'E': result = 14; break;
      case 'F': result = 15; break;

      default:
          result = 0xFF;
  }

return result;
}
Although it might look ugly, this is one of the fasted methods using standard C that converts a hex digit (nibble) to an int (2 machine instructions).
OK, how do you get it to compile to just two instructions? I've been looking at various optimization options, and as far as I can tell it is at least doing the following (non-contiguous):

00001e67	subl	$0x30,êx
00001e6d	cmpl	$0x36,êx
00001e70	jal	0x00001f67
00001e76	movl	0x00000038(ëx,êx,4),êx
00001e7d	addl	ëx,êx
00001e7f	jmp	*êx

So that's 6 instructions to set up and perform the indexed jump to which the switch/case is being compiled.

At the jump sites, typically another 2 instructions:

00001f60	movl	$0x0000000f,êx
00001f65	jmp	0x00001fd2

So that's a total of 8 instructions, with 2 taken and one typically non-taken jump and one of the taken jumps computed, so probably not predictable. I must be missing something obvious.

The smallest (and likely fastest) would probably be the lookup table version:

char hexCharToNibbleL(char nibble)
{
const char lt[255] = { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF };
return lt[nibble];
}

This compiles down to (gcc 4.0, -Os, i386 arch):
_hexCharToNibbleL:
00001b6e        pushl   ëp
00001b6f        calll   0x00001b74
00001b74        popl    ìx
00001b75        movl    %esp,ëp
00001b77        subl    $0x08,%esp
00001b7a        movsbl  0x08(ëp),êx
00001b7e        movsbl  0x0000038c(ìx,êx),êx
00001b86        leave
00001b87        ret

My original if-elseif-elseif version, minus the exception raising, compiles down to:
_hexCharToNibble:
0000282d pushl ëp
0000282e movl %esp,ëp
00002830 movzbl 0x08(ëp),íx
00002834 leal 0xd0(íx),êx
00002837 cmpb $0x09,%al
00002839 jbe 0x00002856
0000283b leal 0xbf(íx),êx
0000283e cmpb $0x05,%al
00002840 ja 0x00002847
00002842 leal 0xc9(íx),êx
00002845 jmp 0x00002856
00002847 leal 0x9f(íx),êx
0000284a movl $0xffffffff,ìx
0000284f cmpb $0x05,%al
00002851 ja 0x0000285b
00002853 leal 0xa9(íx),êx
00002856 movl êx,ìx
00002858 andl $0x0f,ìx
0000285b leave
0000285c movl ìx,êx
0000285e ret

And the switch-case version compiles to three pages of assembly full of addls, addbs, hlts, jmps, and so forth.

I ran some (very) simple benchmarks (full source code at the end of this message).

Examination of the assembly GCC produced for the code shows that gcc inlined the functions inside the for loops when optimization was turned on (both -O3 and -Os). The results are at the end of this message, after the source code.

Some conclusions:
- Unoptimized, all three versions perform more or less the same: very slowly. This was pretty much a guarantee due to the overhead of all those uninlined function calls. But I tried forcing GCC to inline the functions, but it didn't help much, if at all. Conclusion: GCC produces VERY inefficent code by default.
- Optimized, the lookup table is always the fastest by a factor of about two
- Optimized 64-bit code is slower in GCC 4.0
- Optimized 64-bit code is faster in GCC 4.2
- GCC 4.2's optimizer is noticably better than GCC 4.0's.

Food for thought :).

-- Gwynne, Daughter of the Code
"This whole world is an asylum for the incurable."

char hexCharToNibbleS(char nibble)
{
        int result = 0xFF;
        switch (nibble)
        {
                case '0': result = 0; break;
                case '1': result = 1; break;
                case '2': result = 2; break;
                case '3': result = 3; break;
                case '4': result = 4; break;
                case '5': result = 5; break;
                case '6': result = 6; break;
                case '7': result = 7; break;
                case '8': result = 8; break;
                case '9': result = 9; break;
                case 'A': case 'a': result = 10; break;
                case 'B': case 'b': result = 11; break;
                case 'C': case 'c': result = 12; break;
                case 'D': case 'd': result = 13; break;
                case 'E': case 'e': result = 14; break;
                case 'F': case 'f': result = 15; break;
        }
        return result;
}

char hexCharToNibbleL(char nibble)
{
const char lt[255] = { 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF };
return *(lt + nibble);
}

char hexCharToNibble(char nibble)
{
        // 0 - 9
        if (nibble >= '0' && nibble <= '9')
                return (nibble - '0') & 0x0F;
        // A - F
        else if (nibble >= 'A' && nibble <= 'F')
                return (nibble - 'A' + 10) & 0x0F;
        // a - f
        else if (nibble >= 'a' && nibble <= 'f')
                return (nibble - 'a' + 10) & 0x0F;
        return 0xFF;
}

int     main(int argc, char **argv)
{
        NSAutoreleasePool       *p = [[NSAutoreleasePool alloc] init];
        volatile char c = 0;

        NSDate          *startIF = [NSDate date];
        for (NSUInteger i = 0; i < 100000000; ++i)
        {
                c = hexCharToNibble(i % 255);
        }
        NSDate          *endIF = [NSDate date];

        NSDate          *startS = [NSDate date];
        for (NSUInteger i = 0; i < 100000000; ++i)
        {
                c = hexCharToNibbleS(i % 255);
        }
        NSDate          *endS = [NSDate date];

        NSDate          *startL = [NSDate date];
        for (NSUInteger i =0; i < 100000000; ++i)
        {
                c = hexCharToNibbleL(i % 255);
        }
        NSDate          *endL = [NSDate date];

printf("If-else version: %.5f\n", [endIF timeIntervalSinceDate:startIF]);
printf("Switch version: %.5f\n", [endS timeIntervalSinceDate:startS]);
printf("Lookup version: %.5f\n", [endL timeIntervalSinceDate:startL]);

        [p release];
        return 0;
}

Results:

GCC 4.0, 32-bit, -O0:
If-else version: 2.03375
Switch version: 2.66452
Lookup version: 2.22725

GCC 4.0, 32-bit, -O3:
If-else version: 0.64217
Switch version: 0.60569
Lookup version: 0.41606

GCC 4.0, 32-bit, -Os:
If-else version: 0.70390
Switch version: 0.78775
Lookup version: 0.36639

GCC 4.0, 64-bit, -O0:
If-else version: 4.47304
Switch version: 4.73059
Lookup version: 4.28500

GCC 4.0, 64-bit, -O3:
If-else version: 0.94318
Switch version: 0.99140
Lookup version: 0.50790

GCC 4.0, 64-bit, -Os:
If-else version: 0.95291
Switch version: 0.88173
Lookup version: 0.59685

GCC 4.2, 32-bit, -O0:
If-else version: 2.57359
Switch version: 2.74970
Lookup version: 2.23874

GCC 4.2, 32-bit, -O3:
If-else version: 0.54521
Switch version: 0.59065
Lookup version: 0.42472

GCC 4.2, 32-bit, -Os:
If-else version: 0.71297
Switch version: 0.71112
Lookup version: 0.40114

GCC 4.2, 64-bit, -O0:
If-else version: 4.43196
Switch version: 4.70583
Lookup version: 4.06029

GCC 4.2, 64-bit, -O3:
If-else version: 0.74516
Switch version: 0.70652
Lookup version: 0.33434

GCC 4.2, 64-bit, -Os:
If-else version: 0.81226
Switch version: 0.66370
Lookup version: 0.33090

_______________________________________________

Cocoa-dev mailing list (email@hidden)

Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com

Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden




  • Follow-Ups:

      

    • Re: Hex to NSString or NSData

      • From: Andreas Grosam <email@hidden>
      • 

    • Re: Hex to NSString or NSData

      • From: Clark Cox <email@hidden>
      • 





References: 


 >Hex to NSString or NSData (From: "Mr. Gecko" <email@hidden>)


 >Re: Hex to NSString or NSData (From: Jerry Krinock <email@hidden>)


 >Re: Hex to NSString or NSData (From: "Mr. Gecko" <email@hidden>)


 >Re: Hex to NSString or NSData (From: Gwynne Raskind <email@hidden>)


 >Re: Hex to NSString or NSData (From: Andreas Grosam <email@hidden>)


 >Re: Hex to NSString or NSData (From: Marcel Weiher <email@hidden>)






    

  • Prev by Date:
RE: Subject: detect option key on startup

    • 

  • Next by Date:
Re: Subject: detect option key on startup

    • 

  • Previous by thread:
Re: Hex to NSString or NSData

    • 

  • Next by thread:
Re: Hex to NSString or NSData

    • 

  • Index(es):

      

    • Date
      • 

    • Thread
      • 

    

    •