3 ms·

I 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, sa

by gumby 3y ago

I 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!

jcparkyn 3y ago
I think the author is only concerned with decimal digits (0-9).
- patrec 3y ago
  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.
  - kukkamario 3y ago
    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.
  - xcvb 3y ago
    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.
    - patrec 3y ago
      Indeed, I hadn't noticed the 000 (rather than 0f0) in there! Thanks!
    - vesinisa 3y ago
      Just noticed this pattern fits a basic ISO 8601 datetime string perfectly. ISO requires using 'T' in place of ?, but using space (0x20) there is pretty common.
n2d4 3y ago
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); You are right that if you were to use a space in an unexpected position, the code wouldn't work.

by gumby 3y ago

jcparkyn 3y ago

I think the author is only concerned with decimal digits (0-9).

patrec 3y ago
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.
- kukkamario 3y ago
  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.
- xcvb 3y ago
  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.
  - patrec 3y ago
    Indeed, I hadn't noticed the 000 (rather than 0f0) in there! Thanks!
  - vesinisa 3y ago
    Just noticed this pattern fits a basic ISO 8601 datetime string perfectly. ISO requires using 'T' in place of ?, but using space (0x20) there is pretty common.

n2d4 3y ago

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); You are right that if you were to use a space in an unexpected position, the code wouldn't work.