[#3 - Char to int]
A single char
return (uint8_t)(a - '0');
The snippet above illustrates a situation where it is still perfectly acceptable to convert a single character into an (unsigned) integer.
If we assume a is a character between 0 and 9, we can simply subtract the character 0 to immediately retrieve the integer value. Subtracting this value from either the decimal or hexadecimal representation of a character yields the numeric value.
While this approach is ideal for maximum performance, the caller must guarantee that the input is indeed a valid numeric character.
Two chars
uint16_t num10 = (uint16_t)(b - '0') * (uint16_t)10;
uint16_t num1 = (uint16_t)(a - '0');
return num10 + num1;
There is little to add here, as the underlying principle is identical to that of a single character. However, in this scenario, we must multiply b by 10 to account for the tens column before adding the units. This is still very fast because num1 and num10 do not depend on each other.
SWAR (4 - 8 chars)
4 chars:
uint32_t val;
memcpy(&val, cb, 4);
val &= (uint32_t)0x0F0F0F0F;
val = (val * (uint32_t)10) + (val >> 8);
val &= (uint32_t)0x00FF00FF;
val = (val * (uint32_t)100) + (val >> 16);
val &= (uint32_t)0x0000FFFF;
return val;
8 chars:
uint64_t val;
memcpy(&val, cb, 8);
val &= (uint64_t)0x0F0F0F0F0F0F0F0F;
val = (val * (uint64_t)10) + (val >> 8);
val &= (uint64_t)0x00FF00FF00FF00FF;
val = (val * (uint64_t)100) + (val >> 16);
val &= (uint64_t)0x0000FFFF0000FFFF;
val = (val * (uint64_t)10000) + (val >> 32);
val &= (uint64_t)0x00000000FFFFFFFF;
return val;
Unsurprisingly, whilst converting 1-byte and 2-byte character strings using simple multiplication is fast and straightforward, this approach does not scale well as character counts increase. Sequential multiplication can quickly become a bottleneck. SWAR (SIMD Within A Register) is meant to optimise this problem away.
To keep things simple, characters ideally arrive pre-packed in a buffer such as cb. This allows us to load them directly into an underlying integer and perform simultaneous arithmetic across multiple bytes at once. Bitwise masking is then used to clear garbage data between the individual lanes.
I had to work through this manually to properly understand how a string like ‘12345678’ actually becomes an integer. Below is the visual diagram that I frequently return to as a reference:
// Unpacked ASCII chars in memory - '12345678' example
// Memory Addr: [ +0 | +1 | +2 | +3 | +4 | +5 | +6 | +7 ]
// Memory Chars: [ '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' ]
// ASCII Hex: [ 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 ]
//=====================================================================================
// Packed into 64-bit Register
// Little-endian: byte at +0 becomes least-significant byte (far right)
//
// [ 38 | 37 | 36 | 35 | 34 | 33 | 32 | 31 ] &
// [ 0F | 0F | 0F | 0F | 0F | 0F | 0F | 0F ] = Mask ASCII high nibble
// [ 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 ]
//=====================================================================================
// 10x Step
// Combine adjacent bytes: 1,2 -> 12 3,4 -> 34 5,6 -> 56 7,8 -> 78
//
// [ 08 | 07 | 06 | 05 | 04 | 03 | 02 | 01 ] * 10
// [ 50 | 46 | 3C | 32 | 28 | 1E | 14 | 0A ] + Multiply each lane by decimal 10
// [ 00 | 08 | 07 | 06 | 05 | 04 | 03 | 02 ] = Shift right 8 bits
// [ 50 | 4E | 43 | 38 | 2D | 22 | 17 | 0C ] &
// [ 00 | FF | 00 | FF | 00 | FF | 00 | FF ] =
// [ 00 | 4E | 00 | 38 | 00 | 22 | 00 | 0C ]
//
// 16-bit view:
// [ 004E | 0038 | 0022 | 000C ]
// 78 56 34 12 <- decimal values
//=====================================================================================
// 100x Step
// Combine adjacent 16-bit words: 12,34 -> 1234 56,78 -> 5678
//
// [ 004E | 0038 | 0022 | 000C ] * 100
// [ 1E78 | 15E0 | 0D48 | 04B0 ] + Multiply by decimal 100
// [ 0000 | 004E | 0038 | 0022 ] = Shift right 16 bits
// [ 1E78 | 162E | 0D80 | 04D2 ] &
// [ 0000 | FFFF | 0000 | FFFF ] =
// [ 0000 | 162E | 0000 | 04D2 ]
//=====================================================================================
// 32-bit view:
// [ 0000162E | 000004D2 ]
// 5678 1234 <- decimal values
//=====================================================================================
// 10000x Step
// Combine adjacent 32-bit dwords: 1234,5678 -> 12345678
//
// [ 0000162E | 000004D2 ] * 10000
// [ 036264E0 | 00BC4B20 ] + Multiply by decimal 10000
// [ 00000000 | 0000162E ] = Shift right 32 bits
// [ 036264E0 | 00BC614E ] &
// [ 00000000 | FFFFFFFF ] =
// [ 00000000 | 00BC614E ]
//=====================================================================================
// 0x00BC614E == 12345678 decimal