8 ms·
Parsing 8-bit integers quickly
- zokier 3y agoThe use of union here is bit confusing (I think its unnecessary?), although I don't imagine it making any difference in the generated code.
- mwkaufma 3y agoThat's the accepted method in c to do well-defined type-punning.
- vinkelhake 3y agoBut the `as_str` field is never used. The type punning (and all the wonderful endian issues) is already happening in the memcpy.
- mwkaufma 3y agoOh yeah, wheee, I'm not carefully reading. Maybe it's vestigial leftovers from a port from c to c++ (major impls handle it in C++ like in C but the standard insists it's UB).
- mike_hock 3y agoMight be leftover from doing type punning through the union, then being told that's UB and using memcpy instead.
- saagarjha 3y agoIt’s one accepted method. Typically it is recommended to use memcpy.
- JonChesterfield 3y agoIs that still the case these days? I thought we lost that ability sometime around C99 (it's now UB to read from the inactive member), and you're now supposed to memcpy all over the place and hope the compiler elides it.
- Denvercoder9 3y agoThat's only in C++, type punning through unions is still legal in C.
- progmetaldev 3y agoAgreed, as someone that isn't very familiar with C, but has used many C-like languages, the names "as_str" and "as_int" threw me off.
- nasretdinov 3y agoI imagine that you are not allowed to allocate a constant array that would contain a mapping between ASCII values of integers and the actual ints :)? The're just 255 of them needed. Or woukd it be slower?
- jstanley 3y agoHow would you actually implement that? The naive approach where you just index with the ASCII values you have would have to contain 16 million elements since it needs to look at 3 bytes. Anything more space efficient than that would probably be slower than TFA.
- kazinator 3y agoHere is a table-driven idea. #include <stdio.h> int bcd2dec[] = { [0x000] = 0, [0x001] = 1, [0x002] = 2, [0x003] = 3, [0x004] = 4, [0x005] = 5, [0x006] = 6, [0x007] = 7, [0x008] = 8, [0x009] = 9, [0x010] = 10, [0x011] = 11, [0x012] = 12, [0x013] = 13, [0x014] = 14, [0x015] = 15, [0x016] = 16, [0x017] = 17, [0x018] = 18, [0x019] = 19, [0x020] = 20, [0x021] = 21, [0x022] = 22, [0x023] = 23, [0x024] = 24, [0x025] = 25, [0x026] = 26, [0x027] = 27, [0x028] = 28, [0x029] = 29, [0x030] = 30, [0x031] = 31, [0x032] = 32, [0x033] = 33, [0x034] = 34, [0x035] = 35, [0x036] = 36, [0x037] = 37, [0x038] = 38, [0x039] = 39, [0x040] = 40, [0x041] = 41, [0x042] = 42, [0x043] = 43, [0x044] = 44, [0x045] = 45, [0x046] = 46, [0x047] = 47, [0x048] = 48, [0x049] = 49, [0x050] = 50, [0x051] = 51, [0x052] = 52, [0x053] = 53, [0x054] = 54, [0x055] = 55, [0x056] = 56, [0x057] = 57, [0x058] = 58, [0x059] = 59, [0x060] = 60, [0x061] = 61, [0x062] = 62, [0x063] = 63, [0x064] = 64, [0x065] = 65, [0x066] = 66, [0x067] = 67, [0x068] = 68, [0x069] = 69, [0x070] = 70, [0x071] = 71, [0x072] = 72, [0x073] = 73, [0x074] = 74, [0x075] = 75, [0x076] = 76, [0x077] = 77, [0x078] = 78, [0x079] = 79, [0x080] = 80, [0x081] = 81, [0x082] = 82, [0x083] = 83, [0x084] = 84, [0x085] = 85, [0x086] = 86, [0x087] = 87, [0x088] = 88, [0x089] = 89, [0x090] = 90, [0x091] = 91, [0x092] = 92, [0x093] = 93, [0x094] = 94, [0x095] = 95, [0x096] = 96, [0x097] = 97, [0x098] = 98, [0x099] = 99, [0x100] = 100, [0x101] = 101, [0x102] = 102, [0x103] = 103, [0x104] = 104, [0x105] = 105, [0x106] = 106, [0x107] = 107, [0x108] = 108, [0x109] = 109, [0x110] = 110, [0x111] = 111, [0x112] = 112, [0x113] = 113, [0x114] = 114, [0x115] = 115, [0x116] = 116, [0x117] = 117, [0x118] = 118, [0x119] = 119, [0x120] = 120, [0x121] = 121, [0x122] = 122, [0x123] = 123, [0x124] = 124, [0x125] = 125, [0x126] = 126, [0x127] = 127, [0x128] = 128, [0x129] = 129, [0x130] = 130, [0x131] = 131, [0x132] = 132, [0x133] = 133, [0x134] = 134, [0x135] = 135, [0x136] = 136, [0x137] = 137, [0x138] = 138, [0x139] = 139, [0x140] = 140, [0x141] = 141, [0x142] = 142, [0x143] = 143, [0x144] = 144, [0x145] = 145, [0x146] = 146, [0x147] = 147, [0x148] = 148, [0x149] = 149, [0x150] = 150, [0x151] = 151, [0x152] = 152, [0x153] = 153, [0x154] = 154, [0x155] = 155, [0x156] = 156, [0x157] = 157, [0x158] = 158, [0x159] = 159, [0x160] = 160, [0x161] = 161, [0x162] = 162, [0x163] = 163, [0x164] = 164, [0x165] = 165, [0x166] = 166, [0x167] = 167, [0x168] = 168, [0x169] = 169, [0x170] = 170, [0x171] = 171, [0x172] = 172, [0x173] = 173, [0x174] = 174, [0x175] = 175, [0x176] = 176, [0x177] = 177, [0x178] = 178, [0x179] = 179, [0x180] = 180, [0x181] = 181, [0x182] = 182, [0x183] = 183, [0x184] = 184, [0x185] = 185, [0x186] = 186, [0x187] = 187, [0x188] = 188, [0x189] = 189, [0x190] = 190, [0x191] = 191, [0x192] = 192, [0x193] = 193, [0x194] = 194, [0x195] = 195, [0x196] = 196, [0x197] = 197, [0x198] = 198, [0x199] = 199, [0x200] = 200, [0x201] = 201, [0x202] = 202, [0x203] = 203, [0x204] = 204, [0x205] = 205, [0x206] = 206, [0x207] = 207, [0x208] = 208, [0x209] = 209, [0x210] = 210, [0x211] = 211, [0x212] = 212, [0x213] = 213, [0x214] = 214, [0x215] = 215, [0x216] = 216, [0x217] = 217, [0x218] = 218, [0x219] = 219, [0x220] = 220, [0x221] = 221, [0x222] = 222, [0x223] = 223, [0x224] = 224, [0x225] = 225, [0x226] = 226, [0x227] = 227, [0x228] = 228, [0x229] = 229, [0x230] = 230, [0x231] = 231, [0x232] = 232, [0x233] = 233, [0x234] = 234, [0x235] = 235, [0x236] = 236, [0x237] = 237, [0x238] = 238, [0x239] = 239, [0x240] = 240, [0x241] = 241, [0x242] = 242, [0x243] = 243, [0x244] = 244, [0x245] = 245, [0x246] = 246, [0x247] = 247, [0x248] = 248, [0x249] = 249, [0x250] = 250, [0x251] = 251, [0x252] = 252, [0x253] = 253, [0x254] = 254, [0x255] = 255, }; /* * If the input is an empty string or a string of length four or more, * we return -1. Other than that, we assume we have digits. */ int parse_uint8_bcd(const char *str) { if (!str[0]) return -1; if (!str[1]) return str[0] & 0xF; if (!str[2]) return bcd2dec[(str[0] & 0xF) << 4 | (str[1] & 0xF)]; if (!str[3]) return bcd2dec[(str[0] & 0xF) << 8 | (str[1] & 0xF) << 4 | (str[2] & 0xF)]; return -1; } int main(int argc, char **argv) { if (argv[1]) printf("value of %s is %d\n", argv[1], parse_uint8_bcd(argv[1])); return 0; }
- kazinator 3y ago$ cat parse256.c #include <stdio.h> #include <stdint.h> #include <string.h> int parse_uint8_fastswar(const char *str, size_t len, uint8_t *num) { union { uint8_t as_str[4]; uint32_t as_int; } digits; memcpy(&digits.as_int, str, sizeof(digits)); digits.as_int ^= 0x30303030lu; digits.as_int <<= (4 - (len & 0x3)) * 8; uint32_t y = ((UINT64_C(0x640a0100) * digits.as_int)>>32)&0xff; *num = (uint8_t)(y); return (digits.as_int & 0xf0f0f0f0) == 0 && y < 256 && len != 0 && len < 4; } int main(int argc, char **argv) { if (argv[1]) { uint8_t val = 0; if (parse_uint8_fastswar(argv[1], strlen(argv[1]), &val)) { printf("value of %s is %d\n", argv[1], (int) val); } else { printf("%s is invalid, value stored %d\n", argv[1], (int) val); } } return 0; } $ ./parse256 123 123 is invalid, value stored 225 $ uname -a Linux gcc1-power7.osuosl.org 3.10.0-862.14.4.el7.ppc64 #1 SMP Wed Sep 26 20:38:32 GMT 2018 ppc64 ppc64 ppc64 GNU/Linux Oops!
- deleted 3y ago[deleted]
- bangonkeyboard 3y agoThese gotchas make keeping a big-endian machine around totally worth it.
- dataflow 3y agoI'm guessing there isn't any way to simulate big endian on x86?
- deleted 3y ago[deleted]
- JonChesterfield 3y agoA compiler could do that - involves inserting bswap on the way to/from memory, might also be a worthwhile flag for big endian machines that want to execute code that assumes little endian load/stores. I don't know of an implementation of such though.
- jstanley 3y agoI tried this out but it parsed the string "123\n" as 32. Also it parses "400" as 144, when the reference implementation considers it not-a-uint8, but I don't mind so much about that. EDIT: Ah, I think it assumes the string contains only a uint8, rather than trying to parse a uint8 from the start of a string. So you need to zero out the "\n" separately, and then it works.
- Sharlin 3y agoLike the article says, it uses SWAR and requires a buffer of at least four bytes, with the trailing bytes zeroed. Your strings were both four bytes which saved you; had you tried with "42" or something, that would've been undefined behavior! Edit: No, wait, the `len` parameter is there to ensure that trailing bytes don't matter. But note that it must be the length of the number-containing prefix part, not the whole input string! > Also it parses "400" as 144 Did you check the return value? If false (as it is in case of overflow), the result is meaningless.
- jstanley 3y agoYes I checked the return value. Example using the program from https://news.ycombinator.com/item?id=38451560 https://news.ycombinator.com/item?id=38451560 $ ./parse256 400 value of 400 is 144
- tom_ 3y ago400 is not an 8-bit integer! This function appears to be for parsing integers you know in advance will fit into 8 bits, rather than arbitrary input.
- jstanley 3y ago> The function returns a Boolean value indicating whether the input string can be parsed into an unsigned 8-bit integer or not. It returns 1 even though 400 is too large.
- firebaze 3y agoLooking forward to "parsing bit sequences in roman literals quickly" https://hn.algolia.com/?q=lemire+parsing https://hn.algolia.com/?q=lemire+parsing
- deleted 3y ago[deleted]
- nvartolomei 3y agodlemire, you note that the read ”overflows”. Why can’t you copy just `len` bytes? Does it slow too much because of the branch/more load/store operations?
- xoranth 3y agoIt is slower since it actually calls `memcpy`, instead of doing a single load. E.g. https://godbolt.org/z/5xa33qbar https://godbolt.org/z/5xa33qbar
- vinkelhake 3y agoThe SWAR algorithm accepts the 6 ASCII characters after '9'. It'll parse ":>" as 114. int res = parse_uint8_fastswar(":>\0", 2, &num); Returns true and num is 114.
- 1letterunixname 3y agoYep ":>" does parse as 114. ";;" parses as 121. "<>" as 134. "999" parses as 231. Lots of work to do and nowhere close to being a magically clever and correct solution. Note: \0 is implicit and redundant in C string literals. There is a fudge factor in some string handling semantics and it sort-of works without it with some UB risks that are platform specific. (It worked on GCC-13 on Linux on AMD EPYC.) #include <stdio.h> #include <stdint.h> #include <string.h> int parse_uint8_fastswar(const char *str, size_t len, uint8_t *num) { union { uint8_t as_str[4]; uint32_t as_int; } digits; memcpy(&digits.as_int, str, sizeof(digits)); digits.as_int ^= 0x30303030lu; digits.as_int <<= (4 - (len & 0x3)) * 8; uint32_t y = ((UINT64_C(0x640a0100) * digits.as_int)>>32)&0xff; *num = (uint8_t)(y); return (digits.as_int & 0xf0f0f0f0) == 0 && y < 256 && len != 0 && len < 4; } int main(int argc, char **argv) { uint8_t num; if (argc != 2 || !parse_uint8_fastswar(argv[1], strlen(argv[1]), &num)) return 1; printf("parsed as %d (%02Xh)\n", num, num); return 0; }
- vinkelhake 3y agoThe literal ":>\0" gives us a 4 byte char array with the last two bytes being 0. I did this since the algorithm always does a 4 byte read from the passed pointer.
- RaisingSpear 3y agoMy attempt to fix it: https://godbolt.org/z/P3e8q45qx https://godbolt.org/z/P3e8q45qx (also removes the 64-bit multiply, which might be slow on 32-bit machines)
- amelius 3y agoFetching the data should be the bottleneck (by far), so why is the naive approach 2x slower than this smarter approach? Sounds like the CPU should be designed in a smarter way, not the code.
- IshKebab 3y agoPresumably this also only works well if the data is 4-byte aligned.
- blacklion 3y agoGuess the site by title :-) Good as usual.
- aunwick 3y agoWow! 1st year digital logic question makes news on YC?
- doubloon 3y agoi am so confused. "you are given a string and it's length".. i dont understand. is the string like "1,1,22,2,189,3,12,2,120,3" ???
- RaisingSpear 3y agoNo, it's like func("22", 2) If you're not familiar with C, you might be unaware that there needs to be some way for code to know where the end of the string is. Supplying the length is a common way to achieve this (this other being a sentinel value (i.e. a null terminator)).
- doubloon 3y agoso there is a program processing a bunch of text containing 8 bit numbers and the way they process it is to have a single call to func() over and over for every small string length 1 to 3?
- RaisingSpear 3y agoYour description is oddly specific. Maybe it's exactly like that, or maybe there's some variation to it, but the problem here has been simplified to make it more approachable.