3 ms·

How 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 i

How 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 ago
Here 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
  Table element should be unsigned char, otherwise it's wastefully large. Oversight.
zamadatix 3y ago
For most CPUs you can do multiple lookups at once and have multiple in flight. This would allow you to use 256 bytes which should be able to stay in lower level cache once you start doing any meaningful number of conversions. So not necessarily enormous and dog slow... but the real test is put it with the rest of your real code and see what happens. If you come to a certain answer it may not stay the same for another real bit of code.
nasretdinov 3y ago
Yeah you're right, I didn't consider that. However even if you allocate a 16 mln array you'll only need to access ~26 different cache lines, so it might still be ok? That's assuming that my calculation is correct that numbers will be grouped in tens, e.g. 240-249 would be on the same cache line as their numeric values are different by just 10

kazinator 3y ago

Here 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
Table element should be unsigned char, otherwise it's wastefully large. Oversight.

zamadatix 3y ago

For most CPUs you can do multiple lookups at once and have multiple in flight. This would allow you to use 256 bytes which should be able to stay in lower level cache once you start doing any meaningful number of conversions. So not necessarily enormous and dog slow... but the real test is put it with the rest of your real code and see what happens. If you come to a certain answer it may not stay the same for another real bit of code.

nasretdinov 3y ago

Yeah you're right, I didn't consider that. However even if you allocate a 16 mln array you'll only need to access ~26 different cache lines, so it might still be ok? That's assuming that my calculation is correct that numbers will be grouped in tens, e.g. 240-249 would be on the same cache line as their numeric values are different by just 10