{"thread":{"id":"35301","subject":"[PATCH 1/5] compat/bswap.h: Fix build on cygwin, MinGW and msvc","startedAt":"2013-11-07T21:59:38Z","lastAt":"2013-11-08T22:27:49Z","messageCount":3,"participants":["Ramsay Jones","SZEDER Gábor","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":5},"messages":[{"id":"230222","messageId":"527C0D4A.7070101@ramsay1.demon.co.uk","threadId":"35301","inReplyTo":null,"subject":"[PATCH 1/5] compat/bswap.h: Fix build on cygwin, MinGW and msvc","fromName":"Ramsay Jones","fromEmail":"ramsay@ramsay1.demon.co.uk","sentAt":"2013-11-07T21:59:38Z","receivedAt":"2013-11-07T21:59:38Z","isPatch":true,"sender":{"key":"ramsay@ramsayjones.plus.com","avatar":"https://avatars.githubusercontent.com/u/33702710?v=4"},"body":"\nSigned-off-by: Ramsay Jones <ramsay@ramsay1.demon.co.uk>\n---\n compat/bswap.h | 97 ++++++++++++++++++++++++++++++++++++++++------------------\n 1 file changed, 68 insertions(+), 29 deletions(-)\n\ndiff --git a/compat/bswap.h b/compat/bswap.h\nindex ea1a9ed..c18a78e 100644\n--- a/compat/bswap.h\n+++ b/compat/bswap.h\n@@ -17,7 +17,20 @@ static inline uint32_t default_swab32(uint32_t val)\n \t\t((val & 0x000000ff) << 24));\n }\n \n+static inline uint64_t default_bswap64(uint64_t val)\n+{\n+\treturn (((val & (uint64_t)0x00000000000000ffULL) << 56) |\n+\t\t((val & (uint64_t)0x000000000000ff00ULL) << 40) |\n+\t\t((val & (uint64_t)0x0000000000ff0000ULL) << 24) |\n+\t\t((val & (uint64_t)0x00000000ff000000ULL) <<  8) |\n+\t\t((val & (uint64_t)0x000000ff00000000ULL) >>  8) |\n+\t\t((val & (uint64_t)0x0000ff0000000000ULL) >> 24) |\n+\t\t((val & (uint64_t)0x00ff000000000000ULL) >> 40) |\n+\t\t((val & (uint64_t)0xff00000000000000ULL) >> 56));\n+}\n+\n #undef bswap32\n+#undef bswap64\n \n #if defined(__GNUC__) && (defined(__i386__) || defined(__x86_64__))\n \n@@ -32,54 +45,80 @@ static inline uint32_t git_bswap32(uint32_t x)\n \treturn result;\n }\n \n+#define bswap64 git_bswap64\n+#if defined(__x86_64__)\n+static inline uint64_t git_bswap64(uint64_t x)\n+{\n+\tuint64_t result;\n+\tif (__builtin_constant_p(x))\n+\t\tresult = default_bswap64(x);\n+\telse\n+\t\t__asm__(\"bswap %q0\" : \"=r\" (result) : \"0\" (x));\n+\treturn result;\n+}\n+#else\n+static inline uint64_t git_bswap64(uint64_t x)\n+{\n+\tunion { uint64_t i64; uint32_t i32[2]; } tmp, result;\n+\tif (__builtin_constant_p(x))\n+\t\tresult.i64 = default_bswap64(x);\n+\telse {\n+\t\ttmp.i64 = x;\n+\t\tresult.i32[0] = git_bswap32(tmp.i32[1]);\n+\t\tresult.i32[1] = git_bswap32(tmp.i32[0]);\n+\t}\n+\treturn result.i64;\n+}\n+#endif\n+\n #elif defined(_MSC_VER) && (defined(_M_IX86) || defined(_M_X64))\n \n #include <stdlib.h>\n \n #define bswap32(x) _byteswap_ulong(x)\n+#define bswap64(x) _byteswap_uint64(x)\n \n #endif\n \n-#ifdef bswap32\n+#if defined(bswap32)\n \n #undef ntohl\n #undef htonl\n #define ntohl(x) bswap32(x)\n #define htonl(x) bswap32(x)\n \n-#ifndef __BYTE_ORDER\n-#\tif defined(BYTE_ORDER) && defined(LITTLE_ENDIAN) && defined(BIG_ENDIAN)\n-#\t\tdefine __BYTE_ORDER BYTE_ORDER\n-#\t\tdefine __LITTLE_ENDIAN LITTLE_ENDIAN\n-#\t\tdefine __BIG_ENDIAN BIG_ENDIAN\n-#\telse\n-#\t\terror \"Cannot determine endianness\"\n-#\tendif\n+#endif\n+\n+#if defined(bswap64)\n+\n+#undef ntohll\n+#undef htonll\n+#define ntohll(x) bswap64(x)\n+#define htonll(x) bswap64(x)\n+\n+#else\n+\n+#undef ntohll\n+#undef htonll\n+\n+#if !defined(__BYTE_ORDER)\n+# if defined(BYTE_ORDER) && defined(LITTLE_ENDIAN) && defined(BIG_ENDIAN)\n+#  define __BYTE_ORDER BYTE_ORDER\n+#  define __LITTLE_ENDIAN LITTLE_ENDIAN\n+#  define __BIG_ENDIAN BIG_ENDIAN\n+# endif\n+#endif\n+\n+#if !defined(__BYTE_ORDER)\n+# error \"Cannot determine endianness\"\n #endif\n \n #if __BYTE_ORDER == __BIG_ENDIAN\n # define ntohll(n) (n)\n # define htonll(n) (n)\n-#elif __BYTE_ORDER == __LITTLE_ENDIAN\n-#\tif defined(__GNUC__) && defined(__GLIBC__)\n-#\t\tinclude <byteswap.h>\n-#\telse /* GNUC & GLIBC */\n-static inline uint64_t bswap_64(uint64_t val)\n-{\n-\treturn ((val & (uint64_t)0x00000000000000ffULL) << 56)\n-\t\t| ((val & (uint64_t)0x000000000000ff00ULL) << 40)\n-\t\t| ((val & (uint64_t)0x0000000000ff0000ULL) << 24)\n-\t\t| ((val & (uint64_t)0x00000000ff000000ULL) <<  8)\n-\t\t| ((val & (uint64_t)0x000000ff00000000ULL) >>  8)\n-\t\t| ((val & (uint64_t)0x0000ff0000000000ULL) >> 24)\n-\t\t| ((val & (uint64_t)0x00ff000000000000ULL) >> 40)\n-\t\t| ((val & (uint64_t)0xff00000000000000ULL) >> 56);\n-}\n-#\tendif /* GNUC & GLIBC */\n-#\tdefine ntohll(n) bswap_64(n)\n-#\tdefine htonll(n) bswap_64(n)\n-#else /* __BYTE_ORDER */\n-#\terror \"Can't define htonll or ntohll!\"\n+#else\n+# define ntohll(n) default_bswap64(n)\n+# define htonll(n) default_bswap64(n)\n #endif\n \n #endif\n-- \n1.8.4\n"},{"id":"230229","messageId":"20131108004550.GA16843@goldbirke","threadId":"35301","inReplyTo":"527C0D4A.7070101@ramsay1.demon.co.uk","subject":"Re: [PATCH 1/5] compat/bswap.h: Fix build on cygwin, MinGW and msvc","fromName":"SZEDER Gábor","fromEmail":"szeder@ira.uka.de","sentAt":"2013-11-08T00:45:50Z","receivedAt":"2013-11-08T00:45:50Z","isPatch":true,"sender":{"key":"szeder.dev@gmail.com","avatar":"https://avatars.githubusercontent.com/u/116324?v=4"},"body":"Hi,\n\nOn Thu, Nov 07, 2013 at 09:59:38PM +0000, Ramsay Jones wrote:\n> +static inline uint64_t default_bswap64(uint64_t val)\n> +{\n> +\treturn (((val & (uint64_t)0x00000000000000ffULL) << 56) |\n> +\t\t((val & (uint64_t)0x000000000000ff00ULL) << 40) |\n> +\t\t((val & (uint64_t)0x0000000000ff0000ULL) << 24) |\n> +\t\t((val & (uint64_t)0x00000000ff000000ULL) <<  8) |\n> +\t\t((val & (uint64_t)0x000000ff00000000ULL) >>  8) |\n> +\t\t((val & (uint64_t)0x0000ff0000000000ULL) >> 24) |\n> +\t\t((val & (uint64_t)0x00ff000000000000ULL) >> 40) |\n> +\t\t((val & (uint64_t)0xff00000000000000ULL) >> 56));\n> +}\n\nThis got me thinking.\nTo swap 8 bytes this function performs 8 bitwise shifts, 8 bitwise\nANDs and 7 bitwise ORs plus uses 8 64bit constants.  We could do\nbetter than that:\n\nstatic inline uint64_t hacked_bswap64(uint64_t val)\n{\n\tuint64_t tmp = val << 32 | val >> 32;\n\treturn (((tmp & (uint64_t)0xff000000ff000000ULL) >> 24) |\n\t\t((tmp & (uint64_t)0x00ff000000ff0000ULL) >>  8) |\n\t\t((tmp & (uint64_t)0x0000ff000000ff00ULL) <<  8) |\n\t\t((tmp & (uint64_t)0x000000ff000000ffULL) << 24));\n}\n\nThis performs only 6 shifts, 4 ANDs, 4 ORs and uses 4 64bit constants.\n\nbswap64ing 1000000000 64bit ints with default_bswap64() compiled\nwith -O2 takes:\n\n  real    0m1.808s\n  user    0m1.796s\n  sys     0m0.000s\n\nThe same with hacked_bswap64():\n\n  real    0m0.823s\n  user    0m0.816s\n  sys     0m0.000s\n\nI doubt that in normal usage git would spend enough time bswap64ing to\nmake this noticeable, but it was a fun micro-optimization on a wet\nThursday evening nevertheless :)\n\nBest,\nGábor\n"},{"id":"230250","messageId":"20131108222749.GA19912@sigill.intra.peff.net","threadId":"35301","inReplyTo":"20131108004550.GA16843@goldbirke","subject":"Re: [PATCH 1/5] compat/bswap.h: Fix build on cygwin, MinGW and msvc","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-11-08T22:27:49Z","receivedAt":"2013-11-08T22:27:49Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Nov 08, 2013 at 01:45:50AM +0100, SZEDER Gábor wrote:\n\n> Hi,\n> \n> On Thu, Nov 07, 2013 at 09:59:38PM +0000, Ramsay Jones wrote:\n> > +static inline uint64_t default_bswap64(uint64_t val)\n> > +{\n> > +\treturn (((val & (uint64_t)0x00000000000000ffULL) << 56) |\n> > +\t\t((val & (uint64_t)0x000000000000ff00ULL) << 40) |\n> > +\t\t((val & (uint64_t)0x0000000000ff0000ULL) << 24) |\n> > +\t\t((val & (uint64_t)0x00000000ff000000ULL) <<  8) |\n> > +\t\t((val & (uint64_t)0x000000ff00000000ULL) >>  8) |\n> > +\t\t((val & (uint64_t)0x0000ff0000000000ULL) >> 24) |\n> > +\t\t((val & (uint64_t)0x00ff000000000000ULL) >> 40) |\n> > +\t\t((val & (uint64_t)0xff00000000000000ULL) >> 56));\n> > +}\n> \n> This got me thinking.\n> To swap 8 bytes this function performs 8 bitwise shifts, 8 bitwise\n> ANDs and 7 bitwise ORs plus uses 8 64bit constants.  We could do\n> better than that:\n> \n> static inline uint64_t hacked_bswap64(uint64_t val)\n> {\n> \tuint64_t tmp = val << 32 | val >> 32;\n> \treturn (((tmp & (uint64_t)0xff000000ff000000ULL) >> 24) |\n> \t\t((tmp & (uint64_t)0x00ff000000ff0000ULL) >>  8) |\n> \t\t((tmp & (uint64_t)0x0000ff000000ff00ULL) <<  8) |\n> \t\t((tmp & (uint64_t)0x000000ff000000ffULL) << 24));\n> }\n> \n> This performs only 6 shifts, 4 ANDs, 4 ORs and uses 4 64bit constants.\n\nYou can do better still by using the bswap instruction. :)\n\nI tried timing the program below.\n\nWith -O0, your version is actually _slower_ than the naive version (14s\nversus 13s), and the bswap version is better than either (8s). Oddly, in\nan earlier iteration of my test, your version was faster than naive,\nwith bswap faster still (10s, 8s, 5s, respectively). In that version, I\nwas not assigning the result of the bswap anywhere.\n\nSo I think the timing is highly dependent on the code surrounding the\ncall, but of course the asm instruction seems to always perform better.\n\nIf I turn on -O2, all three take about 1.2s.  Inspecting the generated\nassembly, it's because gcc converts the raw-code cases into a bswap\ninstruction.  We end up with something like:\n\n  .L3:\n          subq $1, %rdx\n          bswap %rax\n          jne .L3\n\nAnd according to perf, we spend all of our time on the jump. The bswap\nhardly registers.\n\n> I doubt that in normal usage git would spend enough time bswap64ing to\n> make this noticeable, but it was a fun micro-optimization on a wet\n> Thursday evening nevertheless :)\n\nWe do a fair number, but it's dwarfed by the real work. And from the\nnumbers above, I think our best bet is to use the system bswap if it's\nthere, and then not worry too hard about micro-optimizing the rest.\n\n-Peff\n\n-- >8 --\n#include <stdint.h>\n#include <stdio.h>\n#include <stdlib.h>\n\n#ifdef NAIVE\nstatic inline uint64_t test(uint64_t val)\n{\n        return ((val & (uint64_t)0x00000000000000ffULL) << 56)\n                | ((val & (uint64_t)0x000000000000ff00ULL) << 40)\n                | ((val & (uint64_t)0x0000000000ff0000ULL) << 24)\n                | ((val & (uint64_t)0x00000000ff000000ULL) <<  8)\n                | ((val & (uint64_t)0x000000ff00000000ULL) >>  8)\n                | ((val & (uint64_t)0x0000ff0000000000ULL) >> 24)\n                | ((val & (uint64_t)0x00ff000000000000ULL) >> 40)\n                | ((val & (uint64_t)0xff00000000000000ULL) >> 56);\n}\n\n#elif defined(OPTIM)\nstatic inline uint64_t test(uint64_t val)\n{\n        uint64_t tmp = val << 32 | val >> 32;\n\treturn (((tmp & (uint64_t)0xff000000ff000000ULL) >> 24) |\n                ((tmp & (uint64_t)0x00ff000000ff0000ULL) >>  8) |\n                ((tmp & (uint64_t)0x0000ff000000ff00ULL) <<  8) |\n                ((tmp & (uint64_t)0x000000ff000000ffULL) << 24));\n}\n\n#elif defined(ASM)\nstatic inline uint64_t test(uint64_t val)\n{\n\tregister uint64_t v, x = val;\n\t__asm__(\"bswap %q0\" : \"=r\" (v) : \"0\" (x));\n\treturn v;\n}\n#endif\n\nint main(int argc, char **argv)\n{\n\tunsigned long i;\n        uint64_t n = strtoull(argv[1], NULL, 10);\n\n\tfor (i = 0; i < 1000000000; i++)\n\t\tn = test(n);\n\t/* convince gcc that we really want the output value, so\n\t * it won't optimize out the whole program */\n        printf(\"%d\\n\", (int)n);\n\treturn 0;\n}\n"}]}