{"id":12533,"date":"2010-10-14T07:00:00","date_gmt":"2010-10-14T07:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2010\/10\/14\/the-memcmp-function-reports-the-result-of-the-comparison-at-the-point-of-the-first-difference-but-it-can-still-read-past-that-point\/"},"modified":"2010-10-14T07:00:00","modified_gmt":"2010-10-14T07:00:00","slug":"the-memcmp-function-reports-the-result-of-the-comparison-at-the-point-of-the-first-difference-but-it-can-still-read-past-that-point","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20101014-00\/?p=12533","title":{"rendered":"The memcmp function reports the result of the comparison at the point of the first difference, but it can still read past that point"},"content":{"rendered":"

\nThis story originally involved a more complex data structure,\nbut that would have required too much explaining (with relatively\nlittle benefit since the data structure was not related to the\nmoral of the story),\nso I’m going to retell it with\n\ndouble null-terminated strings<\/a>\nas the data structure instead.\n<\/p>\n

\nConsider the following code to compare two double-null-terminated\nstrings for equality:\n<\/p>\n

\nsize_t SizeOfDoubleNullTerminatedString(const char *s)\n{\n  const char *start = s;\n  for (; *s; s += strlen(s) + 1) { }\n  return s - start + 1;\n}\nBOOL AreDoubleNullTerminatedStringsEqual(\n    const char *s, const char *t)\n{\n size_t slen = SizeOfDoubleNullTerminatedString(s);\n size_t tlen = SizeOfDoubleNullTerminatedString(t);\n return slen == tlen && memcmp(s, t, slen) == 0;\n}\n<\/pre>\n
\n“Aha, this code is inefficient.\nSince the memcmp<\/code> function stops comparing\nas soon as it finds a difference, I can skip the call\nto\nSizeOfDoubleNullTerminatedString(t)<\/code>\nand simply write\n<\/p>\n
\nBOOL AreDoubleNullTerminatedStringsEqual(\n    const char *s, const char *t)\n{\n return memcmp(s, t, SizeOfDoubleNullTerminatedString(s)) == 0;\n}\n<\/pre>\n
\nbecause we can never read past the end of t<\/code>:\nIf the strings are equal, then tlen<\/code>\nwill be equal to slen<\/code> anyway,\nso the buffer size is correct.\nAnd if the strings are different,\nthe difference will be found at or before the end of t<\/code>,\nsince it is not possible for a double-null-terminated string to be\na prefix of another double-null-terminated string.\nIn both cases, we never read past the end of t<\/code>.”\n<\/p>\n
\nThis analysis is based on a flawed assumption,\nnamely, that memcmp<\/code> compares byte-by-byte\nand does not look at bytes beyond the first point of difference.\nThe memcmp<\/code> function makes no such guarantee.\nIt is permitted to read all the bytes from both buffers\nbefore reporting the result of the comparison.\n<\/p>\n
\nIn fact, most implementations of memcmp<\/code> do<\/i>\nread past the point of first difference.\nYour typical library will try to compare the two buffers\nin register-sized chunks rather than byte-by-byte.\n(This is particularly convenient on x86 thanks to the\nblock comparison instruction rep cmpsd<\/code> which\ncompares two memory blocks in DWORD<\/code>-sized chunks,\nand x64 doubles your fun with rep cmpsq<\/code>.)\nOnce it finds two chunks which differ,\nit then studies the bytes within the chunks to determine what\nthe return value should be.\n<\/p>\n
\n(Indeed,\npeople with free time on their hands or simply enjoy a challenge\nwill\n\ntry to outdo the runtime library<\/a>\nwith\nfancy-pants memcmp<\/code> algorithms which compare\nthe buffers in larger-than-normal chunks by doing things\nlike comparing via SIMD registers.)\n<\/p>\n
\nTo illustrate, consider an implementation of memcmp<\/code>\nwhich uses 4-byte chunks.\nTypically, memory comparison functions do some preliminary work\nto get the buffers aligned, but let’s ignore\nthat part since it isn’t interesting.\nThe inner loop goes like this:<\/p>\n
\nwhile (length >= 4)\n{\n int32 schunk = *(int32*)s;\n int32 tchunk = *(int32*)t;\n if (schunk != tchunk) {\n   -- difference found - calculate and return result\n }\n length -= 4;\n s += 4;\n t += 4;\n}\n<\/pre>\n
Let’s compare the strings s = \"a\\0b\\0\\0\"<\/tt> and t = \"a\\0\\0\"<\/tt>.\nThe size of the double-null-terminated string s<\/code> is 4,\nso the memory comparison goes like this:\nFirst we read four bytes from s<\/code> into schunk<\/code>,\nresulting in (on a little-endian machine) 0x00620061<\/code>.\nNext, we read four bytes from t<\/code> into tchunk<\/code>,\nresulting in 0x??000061<\/code>.\nOops, we read one byte past the end of the buffer.\n<\/p>\n
\nIf t<\/code> happened to sit right at the end of a page, and\nthe next page was uncommitted memory, then you take an access violation\nwhile trying to read tchunk<\/code>.\nYour optimization turned into a crash.\n<\/p>\n
\nRemember, when you say that a buffer is a particular size,\nthe\n\nbasic ground rules of programming<\/a>\nsay that it really has to be that size.<\/p>\n","protected":false},"excerpt":{"rendered":"
This story originally involved a more complex data structure, but that would have required too much explaining (with relatively little benefit since the data structure was not related to the moral of the story), so I’m going to retell it with double null-terminated strings as the data structure instead. Consider the following code to compare […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-12533","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
This story originally involved a more complex data structure, but that would have required too much explaining (with relatively little benefit since the data structure was not related to the moral of the story), so I’m going to retell it with double null-terminated strings as the data structure instead. Consider the following code to compare […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/12533","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=12533"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/12533\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=12533"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=12533"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=12533"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}