Packing a string of digits into an integer quickly
1–10 of 19 posts
Re: Packing a string of digits into an integer quickly
#2I don't understand how this can work: there are 15 (or 7 :-) other characters with the same bottom four bits as each digit. How does it distinguish between, say, '4' and 't'? Space and '0' have the same lower four bits: \0!
Re: Packing a string of digits into an integer quickly
#3I don't understand how this can work: there are 15 (or 7 :-) other characters with the same bottom four bits as each digit. How does it distinguish between, say, '4' and 't'? Space and '0' have the same lower four bits: \0!
I think the author is only concerned with decimal digits (0-9).
Re: Packing a string of digits into an integer quickly
#4Can’t you just search through and remove all the non-digit characters? (Excel user here)
Re: Packing a string of digits into an integer quickly
#5I don't understand how this can work: there are 15 (or 7 :-) other characters with the same bottom four bits as each digit. How does it distinguish between, say, '4' and 't'? Space and '0' have the same lower four bits: \0!
I think the author is only concerned with decimal digits (0-9).
No, he says that the strings can contain spaces and other characters but that he wants them ordered (only) by the decimal digits in them. I don't see how this can work either.
Re: Packing a string of digits into an integer quickly
#6Earlier quoted context omitted.
I think the author is only concerned with decimal digits (0-9).
No, he says that the strings can contain spaces and other characters but that he wants them ordered (only) by the decimal digits in them. I don't see how this can work either.
The bitmasks in the code are adjusted so that it works with that specific pattern of numbers to other letters. Masks only pick bits from digits when the are in those specific positions.
So this solution only works when the digit character places are fixed and known.
It would be possible to generate mask based on the first nibbles so that it would ignore non-digits. Maybe even with some fairly optimized vector instructions. Not sure would it be faster than some naive solution.
Re: Packing a string of digits into an integer quickly
#7I don't understand how this can work: there are 15 (or 7 :-) other characters with the same bottom four bits as each digit. How does it distinguish between, say, '4' and 't'? Space and '0' have the same lower four bits: \0!
It doesn't distinguish, the non-digit character index is hardcoded into the bitmask (note the missing f in the second hex literal):
part1 = _pext_u64(part1, 0x0f0f0f0f0f0f0f0f);
part2 = _pext_u64(part2, 0x0f000f0f0f0f0f0f);
Re: Packing a string of digits into an integer quickly
#8Earlier quoted context omitted.
I think the author is only concerned with decimal digits (0-9).
No, he says that the strings can contain spaces and other characters but that he wants them ordered (only) by the decimal digits in them. I don't see how this can work either.
Looking at the code, it seems like it expects a string of the form "dddddddd?dddddd" where the '?' is any ascii character, and the code assumes the rest of the characters are ascii digits.
Specifically the line: `part2 = _pext_u64(part2, 0x0f000f0f0f0f0f0f);` seems to mask out that character.
Re: Packing a string of digits into an integer quickly
#9Earlier quoted context omitted.
No, he says that the strings can contain spaces and other characters but that he wants them ordered (only) by the decimal digits in them. I don't see how this can work either.
Looking at the code, it seems like it expects a string of the form "dddddddd?dddddd" where the '?' is any ascii character, and the code assumes the rest of the characters are ascii digits. Specifically the line: `part2 = _pext_u64(part2, 0x0f000f0f0f0f0f0f);` seems to mask out that character.
Indeed, I hadn't noticed the 000 (rather than 0f0) in there! Thanks!
Re: Packing a string of digits into an integer quickly
#10It was a fairly common thing to do very similar operations on Apple ][ computers.
6502 had a BCD (binary coded decimal) mode; basically when in BCD mode arithmetic operators carried at 0x9 rather than 0xF, and operations worked nibble-wise rather than byte-wise. So it was common to represent 2 digits in one bye regardless of hex vs decimal.
I actually have been thinking about this lately because of the other half of the problem, ie ASCII native types. On the Apple 2 one really cool speed trick was to store strings directly on the screen. The Apple 2 text screen was memory mapped (0x400 - 0x7FF IIRC). To write strings to the screen in assembly, you wrote the ASCII character codes to the right memory locations. But if you were trying to eke out every single cycle you could, and your strings were fixed length, you didn’t need to store them somewhere and copy them to the screen; you could use the screen as the store for your strings.
I once made a stupid program that counted to one million this way; it ran fast enough to watch it finish.