Fast Hexadecimal Encode and Decode

In Easy String Encryption Using CryptoAPI in C++ I described how to encrypt text and recommended that the encrypted text be stored as a series of hexadecimal digits -- because cyphertext may contain embedded NULLs or other characters that can cause processing problems.

Since then I've worked on an application in which large blocks of binary data must be encoded into hexadecimal rapidly, and when needed, decoded back to binary just as rapidly.  In the earlier article, I provided a sort of "throw-away" hex encoder/decoder, but I felt that I needed something that was more efficient for production work.

In this article, I'll explore some hex encode/decode options, including the one supported by the CryptoAPI, and at the end of the article, I'll present the ultra-fast functions that ended up in my production code.

Observe the ordering of characters in an ASCII Table The only real issue with hex encoding is that there is a gap between the 9 and the A.  Most of the complications come when dealing with that.

How to Encode to Hexadecimal
Your binary source byte is 8 bits.  Take the data 4 bits at a time (values 0-15).  If that value is 0-9, then just add '0' (0x30).  If the value is 10-15, then add 0x37 instead.  That gives you a hex digit ('0', '1',...,'9','A',..., 'F').  Output the resulting high hex digit followed by the low hex digit.

void ToHexManual( BYTE* pSrc, int nSrcLen, CString& sDest )
                      {
                      	sDest="";
                      	for ( int j=0; j<nSrcLen; j++ ) {
                      		BYTE b1= *pSrc >> 4;   // hi nybble
                      		BYTE b2= *pSrc & 0x0f; // lo nybble
                      		b1+='0'; if (b1>'9') b1 += 7;  // gap between '9' and 'A'
                      		b2+='0'; if (b2>'9') b2 += 7;  
                      		sDest += b1; 
                      		sDest += b2; 
                      		pSrc++;
                      	}
                      }
                      

Select all Open in new window

Here's a more concise (but slower) version that uses a printf-type tool:

void ToHexSlow( BYTE* pSrc, int nSrcLen, CString& sDest )
                      {
                      	sDest="";
                      	for ( int j=0; j<nSrcLen; j++ ) {
                      		sDest.AppendFormat( "%02x", int(*pSrc) );
                      		pSrc++;
                      	}
                      }
                      

Select all Open in new window

Both of these are usable, but not as efficient as I'd like.  The former requires calculations and conditional tests twice for each byte.  The latter makes a function call for each byte.  Both versions append the output to an ever-growing CString object, and that can be a significant problem when the output is large.  Let me explain...

Significant Problem with Long Strings
Each time you concatenate to an existing CString (or an STL string object), the code must check to see if that current allocation is large enough.  If not, it must allocate a new chunk that is larger, and copy the existing contents to that location before appending the new text.  Imagine how clumsy that gets when the string is about 1MB long!

We'll look at the efficient version that avoids these problems in a minute.  

How to Decode from Hexadecimal
Your textual source data is composed of pairs of hex digits, for instance "72" or "0F' or "D3".  Take  the first digit and subtract '0' (0x30).  If the result is greater than 9 (it's 'A','B',...,'F'), then subtract 7, resulting in a value between 0 and 15.  Do the same for the second digit.  Multiply the first by 16 and add it to the second.  Output the resulting 8-bit value.

void FromHexManual( LPCSTR pSrc, int nSrcLen, BYTE* pDest )
                      {
                      	for ( int j=0; j<nSrcLen; j+=2 ) {
                      		BYTE b1= pSrc[j]   -'0'; if (b1>9) b1 -= 7;
                      		BYTE b2= pSrc[j+1] -'0'; if (b2>9) b2 -= 7;
                      		*pDest++ = (b1<<4) + b2;  // <<4 multiplies by 16
                      	}
                      }
                      

Select all Open in new window

Here's another try that uses sscanf from the C runtime library:

void FromHexSlow( LPCSTR pSrc, int nSrcLen, BYTE* pDest )
                      {
                      	char sTmp[3]="xx";
                      	int n;
                      	for ( int j=0; j<nSrcLen; j += 2 ) {
                      		sTmp[0]= pSrc[0];
                      		sTmp[1]= pSrc[1];
                      		sscanf( sTmp, "%x", &n );
                      		pSrc += 2;
                      		*pDest++ = (BYTE)n;
                      	}
                      }
                      

Select all Open in new window

The CryptoAPI Hex Conversion Functions
None of the above routines provided the kind of speed that I was hoping to achieve.   After some research, I found a couple of functions in the CryptoAPI toolkit that convert to and from hex:
    CryptBinaryToString  and   CryptStringToBinary
and I tried them:

#pragma comment( lib, "Crypt32.lib" )
                      #include <Wincrypt.h>
                      void ToHexCryptoAPI( BYTE* pSrc, int nSrcLen, CString& sDest )
                      {
                          DWORD nOutLen= (nSrcLen*3)+4; // xx<space> + etc/
                          char* pBuf= new char[nOutLen];
                          BOOL fRet= CryptBinaryToString( pSrc,nSrcLen, CRYPT_STRING_HEX, pBuf, &nOutLen ); 
                          sDest= pBuf;
                          delete pBuf;
                      }
                      int FromHexCryptoAPI( LPCSTR pSrc, int nSrcLen, BYTE* pDest )
                      {
                          DWORD nOutLen= nSrcLen/2;
                          BOOL fRet= CryptStringToBinary( pSrc, nSrcLen, CRYPT_STRING_HEX, pDest, &nOutLen, 0, 0);
                          return( (int)nOutLen );
                      }
                      

Select all Open in new window

Oddly, the only useful option is CRYPT_STRING_HEX -- the CRYPT_STRING_HEXRAW option is no longer supported.  The output from CryptBinaryToString appears to be formatted for screen output -- spaces between each pair of hex digits, embedded tab characters, CRLF at the end, etc.  The two functions above do work, and there certainly is value in using standard API functions, but the performance was lackluster, and I didn't want the overhead of the extra embedded characters.

[step="" title="Finally --  The Ultra-Fast Code I Promised!"][/step] Lookup Tables Rather Than Calculations
If you look at the assembly-language output from any of the above routines, you will see conditional jumps and a significant number of calculations.   Modern processors are fast, using multiple pipelines to handle conditionals, but there is nothing faster than using a lookup table -- especially when the table is in L1 processor cache... the table access is nearly as fast as register access!

So...
For binary-to-hex, I used a table that contains all possible output values for any byte of data.  This is very straightforward -- the data itself is the index into the table.  I use a WORD pointer to grab 16 bits (two hex digits) at a time.

For hex-to-binary, I realized that I could use a lookup table that contains all possible hexadecimal digit values.   Rather than compensate for the "gap" between '9'' and 'A', I just left empty spots in the table.   As a bonus, I left an extra gap between "F" and "a" -- so that the same routine could convert the hexadecimal data regardless of whether it contains A,B,C,D,E,F or a,b,c,d,e,f.

BYTE HexLookup[513]= {
                      	"000102030405060708090a0b0c0d0e0f"
                      	"101112131415161718191a1b1c1d1e1f"
                      	"202122232425262728292a2b2c2d2e2f"
                      	"303132333435363738393a3b3c3d3e3f"
                      	"404142434445464748494a4b4c4d4e4f"
                      	"505152535455565758595a5b5c5d5e5f"
                      	"606162636465666768696a6b6c6d6e6f"
                      	"707172737475767778797a7b7c7d7e7f"
                      	"808182838485868788898a8b8c8d8e8f"
                      	"909192939495969798999a9b9c9d9e9f"
                      	"a0a1a2a3a4a5a6a7a8a9aaabacadaeaf"
                      	"b0b1b2b3b4b5b6b7b8b9babbbcbdbebf"
                      	"c0c1c2c3c4c5c6c7c8c9cacbcccdcecf"
                      	"d0d1d2d3d4d5d6d7d8d9dadbdcdddedf"
                      	"e0e1e2e3e4e5e6e7e8e9eaebecedeeef"
                      	"f0f1f2f3f4f5f6f7f8f9fafbfcfdfeff"
                      };
                      void ToHex( BYTE* pSrc, int nSrcLen, CString& sDest )
                      {
                      	WORD* pwHex=  (WORD*)HexLookup;
                      	WORD* pwDest= (WORD*)sDest.GetBuffer((nSrcLen*2)+1);
                      
                      	for (int j=0; j<nSrcLen; j++ ) {
                      		*pwDest= pwHex[*pSrc];
                      		pwDest++; pSrc++;
                      	}
                      	*((BYTE*)pwDest)= 0;  // terminate the string
                      	sDest.ReleaseBuffer((nSrcLen*2)+1);
                      }
                      

Select all Open in new window

BYTE DecLookup[] = {
                      	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, // gap before first hex digit
                      	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 
                      	0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 
                      	0,1,2,3,4,5,6,7,8,9,       // 0123456789
                      	0,0,0,0,0,0,0,             // :;<=>?@ (gap)
                      	10,11,12,13,14,15,         // ABCDEF 
                      	0,0,0,0,0,0,0,0,0,0,0,0,0, // GHIJKLMNOPQRS (gap)
                      	0,0,0,0,0,0,0,0,0,0,0,0,0, // TUVWXYZ[/]^_` (gap)
                      	10,11,12,13,14,15          // abcdef 
                      };
                      void FromHex( BYTE* pSrc, int nSrcLen, BYTE* pDest )
                      {
                      	for (int j=0; j<nSrcLen; j += 2 ) {
                      		int d =  DecLookup[*pSrc++ ] << 4;
                      		    d |= DecLookup[*pSrc++ ];
                      		*pDest++ = (BYTE)d;
                      	}
                      }
                      

Select all Open in new window

Notes:

[i] References:[/i]

CryptBinaryToString Function
http://msdn.microsoft.com/en-us/library/aa379887(VS.85).aspx

CryptStringToBinary Function
http://msdn.microsoft.com/en-us/library/aa380285(VS.85).aspx

How fast is your ASM hex converter?
https://www.experts-exchange.com/questions/20272901/How-fast-is-your-ASM-hex-converter.html
This Experts-Exchange "question" was really a challenge to create a particular kind of hexadecimal output in intel ASM.  The lookup table technique won out easily... until some smarty pants!!! figured out how to use MMX opcodes and handle larger chunks of data.   Interesting reading, and a lot of fun for the participants!

=-=-=-=-=-=-=-=-=-=-=-=-=- =-=-=-=-=- =-=-=-=-=- =-=-=-=-=- =-=-=-=-=- =-=-=-=-=- =-=-=-=
If you liked this article and want to see more from this author,  please click the Yes button near the:
      Was this article helpful?
label that is just below and to the right of this text.   Thanks!
=-=-=-=-=-=-=-=-=-=-=-=-=- =-=-=-=-=- =-=-=-=-=- =-=-=-=-=- =-=-=-=-=- =-=-=-=-=- =-=-=-=