{"thread":{"id":"8366","subject":"[PATCH] fix signed range problems with hex conversions","startedAt":"2007-05-30T17:09:24Z","lastAt":"2007-05-30T18:20:21Z","messageCount":4,"participants":["Nicolas Pitre","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"43647","messageId":"alpine.LFD.0.99.0705301213450.11491@xanadu.home","threadId":"8366","inReplyTo":null,"subject":"[PATCH] fix signed range problems with hex conversions","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-30T17:09:24Z","receivedAt":"2007-05-30T17:09:24Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"The get_sha1_hex() function is defined as accepting a char array.  \nBecause the char type is signed by default on many architectures, \nget_sha1_hex() can be passed a pointer to negative chars. This can \nhappen with user input containing chars with the top bit set.\n\nThen those chars are passed to hexval() which is defined as accepting an \nunsigned int value. Whenever a signed char is promoted to an int, the \npromotion is always signed and then the result is stored in the unsigned \nint variable.  In the negative char case that means really large \nunsigned int values will result, and then the hexval_table is happily \nindexed with that value.\n\nOn 32-bit architectures the large int value will create a wrap-around \nand a byte located somewhere before the hexval_table array in memory \nwill be fetched.  Depending on that byte value a bogus SHA1 value could \nbe returned.\n\nOn 64-bit architectures the large int value will most probably cause a \nsegmentation fault.\n\nThis patch adds a range test to hexval() in order to prevent this.  Also \nlet's index the hexval_table array directly in get_sha1_hex() using \nexplicitly unsigned chars to avoid the range test producing faster\ncode.\n\nWhile at it, make hexval_table const.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n---\n\ndiff --git a/cache.h b/cache.h\nindex f675223..30fcaa9 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -359,10 +359,10 @@ extern void *map_sha1_file(const unsigned char *sha1, unsigned long *);\n extern int has_pack_file(const unsigned char *sha1);\n extern int has_pack_index(const unsigned char *sha1);\n \n-extern signed char hexval_table[256];\n+extern const signed char hexval_table[256];\n static inline unsigned int hexval(unsigned int c)\n {\n-\treturn hexval_table[c];\n+\treturn (c & ~0xff) ? -1 : hexval_table[c];\n }\n \n /* Convert to/from hex/sha1 representation */\ndiff --git a/sha1_file.c b/sha1_file.c\nindex a3637d7..e10fb4b 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -33,7 +33,7 @@ const unsigned char null_sha1[20];\n \n static unsigned int sha1_file_open_flag = O_NOATIME;\n \n-signed char hexval_table[256] = {\n+const signed char hexval_table[256] = {\n \t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 00-07 */\n \t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 08-0f */\n \t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 10-17 */\n@@ -72,11 +72,12 @@ int get_sha1_hex(const char *hex, unsigned char *sha1)\n {\n \tint i;\n \tfor (i = 0; i < 20; i++) {\n-\t\tunsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);\n+\t\tunsigned char c0 = *hex++;\n+\t\tunsigned char c1 = *hex++;\n+\t\tunsigned int val = (hexval_table[c0] << 4) | hexval_table[c1];\n \t\tif (val & ~0xff)\n \t\t\treturn -1;\n \t\t*sha1++ = val;\n-\t\thex += 2;\n \t}\n \treturn 0;\n }\n"},{"id":"43649","messageId":"alpine.LFD.0.98.0705301025170.26602@woody.linux-foundation.org","threadId":"8366","inReplyTo":"alpine.LFD.0.99.0705301213450.11491@xanadu.home","subject":"Re: [PATCH] fix signed range problems with hex conversions","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-05-30T17:32:19Z","receivedAt":"2007-05-30T17:32:19Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 30 May 2007, Nicolas Pitre wrote:\n> \n> This patch adds a range test to hexval() in order to prevent this.  Also \n> let's index the hexval_table array directly in get_sha1_hex() using \n> explicitly unsigned chars to avoid the range test producing faster\n> code.\n\nPlease just make hexval() take a \"unsigned char\" instead, solving the \nproblem in a manner that makes it much easier for the compiler to realize \nthat it never needs to sign-extend the value or test the end result..\n\nIe I think your patch would be better off something like the following \ninstead (it would be a one-liner, but I agree that marking hexval_table \n\"const\" is also a good idea).\n\nWith this, gcc can just generate:\n\n\tmovzbl  (%rdi), %eax\n\tmovsbl  hexval_table(%rax),%edx\n\tmovzbl  1(%rdi), %eax\n\tmovsbl  hexval_table(%rax),%eax\n\tsall    $4, %edx\n\torl     %eax, %edx\n\nfor the code to generate a byte from two hex characters.\n\n\t\tLinus\n\n----\ndiff --git a/cache.h b/cache.h\nindex ec85d93..0da7070 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -359,8 +359,8 @@ extern void *map_sha1_file(const unsigned char *sha1, unsigned long *);\n extern int has_pack_file(const unsigned char *sha1);\n extern int has_pack_index(const unsigned char *sha1);\n \n-extern signed char hexval_table[256];\n-static inline unsigned int hexval(unsigned int c)\n+extern const signed char hexval_table[256];\n+static inline unsigned int hexval(unsigned char c)\n {\n \treturn hexval_table[c];\n }\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 12d2ef2..f959fe5 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -33,7 +33,7 @@ const unsigned char null_sha1[20];\n \n static unsigned int sha1_file_open_flag = O_NOATIME;\n \n-signed char hexval_table[256] = {\n+const signed char hexval_table[256] = {\n \t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 00-07 */\n \t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 08-0f */\n \t -1, -1, -1, -1, -1, -1, -1, -1,\t\t/* 10-17 */\n"},{"id":"43650","messageId":"alpine.LFD.0.98.0705301038310.26602@woody.linux-foundation.org","threadId":"8366","inReplyTo":"alpine.LFD.0.98.0705301025170.26602@woody.linux-foundation.org","subject":"Re: [PATCH] fix signed range problems with hex conversions","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-05-30T17:42:41Z","receivedAt":"2007-05-30T17:42:41Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 30 May 2007, Linus Torvalds wrote:\n> \n> With this, gcc can just generate:\n> \n> \tmovzbl  (%rdi), %eax\n>\t...\n\nBtw, in the kernel we have a rule for *.c -> *.s files exactly because \nit's nice to be able to easily say \"ok, what does that generate\". \n\nHere's a patch to add such a rule to git too, in case anybody is \ninterested. It makes it much simpler to just do\n\n\tmake sha1_file.s\n\nand look at the compiler-generated output that way, rather than having to \nfire up gdb on the resulting binary.\n\n(Add -fverbose-asm or something if you want to, it can make the result \neven more readable)\n\n\t\tLinus\n\n---\ndiff --git a/Makefile b/Makefile\nindex 7527734..7ffb803 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -846,6 +846,8 @@ git$X git.spec \\\n \n %.o: %.c GIT-CFLAGS\n \t$(QUIET_CC)$(CC) -o $*.o -c $(ALL_CFLAGS) $<\n+%.s: %.c GIT-CFLAGS\n+\t$(QUIET_CC)$(CC) -S $(ALL_CFLAGS) $<\n %.o: %.S\n \t$(QUIET_CC)$(CC) -o $*.o -c $(ALL_CFLAGS) $<\n \n"},{"id":"43653","messageId":"alpine.LFD.0.99.0705301346580.11491@xanadu.home","threadId":"8366","inReplyTo":"alpine.LFD.0.98.0705301025170.26602@woody.linux-foundation.org","subject":"Re: [PATCH] fix signed range problems with hex conversions","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-05-30T18:20:21Z","receivedAt":"2007-05-30T18:20:21Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Wed, 30 May 2007, Linus Torvalds wrote:\n\n> On Wed, 30 May 2007, Nicolas Pitre wrote:\n> > \n> > This patch adds a range test to hexval() in order to prevent this.  Also \n> > let's index the hexval_table array directly in get_sha1_hex() using \n> > explicitly unsigned chars to avoid the range test producing faster\n> > code.\n> \n> Please just make hexval() take a \"unsigned char\" instead, solving the \n> problem in a manner that makes it much easier for the compiler to realize \n> that it never needs to sign-extend the value or test the end result..\n\nWell, I did it the way I did for two reasons, the first being that \nrandom hexval() usage won't mask a bad value if it is passed an int \nwhich happens to be out of range (think EOF, or better yet -208, -207, \netc).\n\nYet gcc appears to be smart enough to skip the test if it is passed a \nvalue that cannot exceed the test range, like an unsigned char.\n\n> Ie I think your patch would be better off something like the following \n> instead (it would be a one-liner, but I agree that marking hexval_table \n> \"const\" is also a good idea).\n> \n> With this, gcc can just generate:\n> \n> \tmovzbl  (%rdi), %eax\n> \tmovsbl  hexval_table(%rax),%edx\n> \tmovzbl  1(%rdi), %eax\n> \tmovsbl  hexval_table(%rax),%eax\n> \tsall    $4, %edx\n> \torl     %eax, %edx\n> \n> for the code to generate a byte from two hex characters.\n\nMy patch already produces code that looks like that for get_sha1_hex() \non i386.  But my second reason for the patch is that on ARM it \nshould becomes:\n\n\t/* r4 = hexval_table, ip = hex */\n\tldrb\tr1, [ip], #1\n\tldrb    r2, [ip], #1\n\tldrsb   r0, [r4, r1]\n\tldrsb   r3, [r4, r2]\n\torr     r0, r3, r0, asl #4\n\nI.e. the compiler has a greater chance to fold the post increment with \nthe load byte instruction as above without the need for an extra\nadd instruction.\n\n\nNicolas\n"}]}