{"id":35913,"date":"2005-04-13T08:56:56","date_gmt":"2005-04-13T08:56:56","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/2005\/04\/13\/using-the-powers-of-mathematics-to-simplify-multi-level-comparisons\/"},"modified":"2005-04-13T08:56:56","modified_gmt":"2005-04-13T08:56:56","slug":"using-the-powers-of-mathematics-to-simplify-multi-level-comparisons","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20050413-56\/?p=35913","title":{"rendered":"Using the powers of mathematics to simplify multi-level comparisons"},"content":{"rendered":"<p>\nWhat a boring title.\n<\/p>\n<p>\nOften you&#8217;ll find yourself needing to perform a multi-level comparison.\nThe most common example of this is performing a version check when\nthere are major and minor version numbers involved.\n<a HREF=\"http:\/\/blogs.msdn.com\/oldnewthing\/archive\/2004\/02\/13\/72476.aspx\">\nBad version number checks<\/a> are one of the most common sources\nof errors.\n<\/p>\n<p>\nIf you&#8217;re comparing version numbers, you can use\n<a HREF=\"http:\/\/msdn.microsoft.com\/library\/en-us\/sysinfo\/base\/verifying_the_system_version.asp\">\nthe <code>VerifyVersionInfo<\/code> function<\/a>\nto do the version check for you,\nassuming you don&#8217;t need to\nrun on operating systems prior to Windows&nbsp;2000.\n<\/p>\n<p>\nInstead of writing a multi-level comparison, you can pack the\nvalues into a single comparison.\nConsider:\n<\/p>\n<pre>\ninline unsigned __int64\nMakeUINT64(DWORD Low, DWORD High)\n{\n  ULARGE_INTEGER Value;\n  Value.LowPart = Low;\n  Value.HighPart = High;\n  return Value.QuadPart;\n}\nBOOL IsVersionAtLeast(DWORD Major, DWORD Minor,\n                      DWORD MajorDesired, DWORD MinorDesired)\n{\n  return MakeUINT64(Minor, Major) &gt;= MakeUINT64(MinorDesired, MajorDesired);\n}\n<\/pre>\n<p>\nWhat happened here?\n<\/p>\n<p>\nWe took the two 32-bit values and combined them into a large\n64-bit value, putting the most significant portion in the high-order\npart and the less significant portion in the lower-order part.\n<\/p>\n<p>\nThen we sit back and let the power of mathematics do our work for us.\nIf you remember the rules for comparisons from grade school,\nyou&#8217;ll realize that they exactly match the rules we want to apply\nto our multi-level comparison.  Compare the major values; if different,\nthen that&#8217;s the result. Otherwise, compare the minor values.\n<\/p>\n<p>\nIf you still don&#8217;t believe it, look at the generated code:\n<\/p>\n<pre>\n  00000 8b 44 24 04      mov     eax, DWORD PTR _Major$[esp-4]\n  00004 3b 44 24 0c      cmp     eax, DWORD PTR _MajorDesired$[esp-4]\n  00008 8b 4c 24 08      mov     ecx, DWORD PTR _Minor$[esp-4]\n  0000c 8b 54 24 10      mov     edx, DWORD PTR _MinorDesired$[esp-4]\n  00010 72 0b            jb      SHORT $L48307\n  00012 77 04            ja      SHORT $L48317\n  00014 3b ca            cmp     ecx, edx\n  00016 72 05            jb      SHORT $L48307\n$L48317:\n  00018 33 c0            xor     eax, eax\n  0001a 40               inc     eax\n  0001b eb 02            jmp     SHORT $L48308\n$L48307:\n  0001d 33 c0            xor     eax, eax\n$L48308:\n  0001f c2 10 00         ret     16                     ; 00000010H\n<\/pre>\n<p>\nThe code generated by the compiler is equivalent to\n<\/p>\n<pre>\nBOOL IsVersionAtLeastEquiv(DWORD Major, DWORD Minor,\n                      DWORD MajorDesired, DWORD MinorDesired)\n{\n if (Major &lt; MajorDesired) return FALSE;\n if (Major &gt; MajorDesired) return TRUE;\n if (Minor &lt; MinorDesired) return FALSE;\n return TRUE;\n}\n<\/pre>\n<p>\nIn fact, if you had written the code the (error-prone)\nold-fashioned way, you would have gotten this:\n<\/p>\n<pre>\nBOOL IsVersionAtLeast2(DWORD Major, DWORD Minor,\n                       DWORD MajorDesired, DWORD MinorDesired)\n{\n  return Major &gt; MajorDesired ||\n   (Major == MajorDesired &amp;&amp; Minor &gt;= MinorDesired);\n}\n  00000 55               push    ebp\n  00001 8b ec            mov     ebp, esp\n  00003 8b 45 08         mov     eax, DWORD PTR _Major$[ebp]\n  00006 3b 45 10         cmp     eax, DWORD PTR _MajorDesired$[ebp]\n  00009 77 0e            ja      SHORT $L48329\n  0000b 75 08            jne     SHORT $L48328\n  0000d 8b 45 0c         mov     eax, DWORD PTR _Minor$[ebp]\n  00010 3b 45 14         cmp     eax, DWORD PTR _MinorDesired$[ebp]\n  00013 73 04            jae     SHORT $L48329\n$L48328:\n  00015 33 c0            xor     eax, eax\n  00017 eb 03            jmp     SHORT $L48330\n$L48329:\n  00019 33 c0            xor     eax, eax\n  0001b 40               inc     eax\n$L48330:\n  0001c 5d               pop     ebp\n  0001d c2 10 00         ret     16                     ; 00000010H\n<\/pre>\n<p>\nwhich is, as you can see, functionally identical to both previous\nversions.\n<\/p>\n<p>\nYou can also pack the values into smaller units, provided\nyou know that there will be no overflow or truncation.\nFor example, if you know that the Major and Minor values will\nnever exceed 65535, you could have used the following:\n<\/p>\n<pre>\nBOOL SmallIsVersionAtLeast(WORD Major, WORD Minor,\n                           WORD MajorDesired, WORD MinorDesired)\n{\n return MAKELONG(Minor, Major) &gt;= MAKELONG(MinorDesired, MajorDesired);\n}\n 00000 0f b7 44 24 0c   movzx   eax, WORD PTR _MajorDesired$[esp-4]\n 00005 0f b7 4c 24 10   movzx   ecx, WORD PTR _MinorDesired$[esp-4]\n 0000a 0f b7 54 24 08   movzx   edx, WORD PTR _Minor$[esp-4]\n 0000f c1 e0 10         shl     eax, 16                        ; 00000010H\n 00012 0b c1            or      eax, ecx\n 00014 0f b7 4c 24 04   movzx   ecx, WORD PTR _Major$[esp-4]\n 00019 c1 e1 10         shl     ecx, 16                        ; 00000010H\n 0001c 0b ca            or      ecx, edx\n 0001e 33 d2            xor     edx, edx\n 00020 3b c8            cmp     ecx, eax\n 00022 0f 9d c2         setge   dl\n 00025 8b c2            mov     eax, edx\n 00027 c2 10 00         ret     16                     ; 00000010H\n<\/pre>\n<p>\nAnd if you know that the versions will never exceed 255, then you\ncan go even smaller:\n<\/p>\n<pre>\nBOOL TinyIsVersionAtLeast(BYTE Major, BYTE Minor,\n                          BYTE MajorDesired, BYTE MinorDesired)\n{\n return MAKEWORD(Minor, Major) &gt;= MAKEWORD(MinorDesired, MajorDesired);\n}\n  00000 33 c0            xor     eax, eax\n  00002 8a 64 24 0c      mov     ah, BYTE PTR _MajorDesired$[esp-4]\n  00006 33 c9            xor     ecx, ecx\n  00008 8a 6c 24 04      mov     ch, BYTE PTR _Major$[esp-4]\n  0000c 8a 44 24 10      mov     al, BYTE PTR _MinorDesired$[esp-4]\n  00010 8a 4c 24 08      mov     cl, BYTE PTR _Minor$[esp-4]\n  00014 66 3b c8         cmp     cx, ax\n  00017 1b c0            sbb     eax, eax\n  00019 40               inc     eax\n  0001a c2 10 00         ret     16                     ; 00000010H\n<\/pre>\n<p>\nWhy would you ever need to go smaller if the original version works\nanyway?  Because you might want to make a three-way or four-way\ncomparison, and packing the values smaller allows you to squeeze\nmore keys into the comparison.\n<\/p>\n<pre>\nBOOL IsVersionBuildAtLeast(\n    WORD Major, WORD Minor, DWORD Build,\n    WORD MajorDesired, WORD MinorDesired, DWORD BuildDesired)\n{\n return MakeUINT64(Build, MAKELONG(Minor, Major)) &gt;=\n  MakeUINT64(Build, MAKELONG(MinorDesired, MajorDesired));\n}\n<\/pre>\n<p>\nBy packing the major version, minor version, and build number\ninto a single 64-bit value, a single comparison operation will\ncompare all three at once.  Compare this to the complicated\n(and teetering-towards unreadable) chain of comparisons you would normally\nhave to write:\n<\/p>\n<pre>\n  return Major &gt; MajorDesired ||\n   (Major == MajorDesired &amp;&amp;\n    (Minor &gt;= MinorDesired ||\n     (Minor == MinorDesired &amp;&amp; Build &gt;= BuildDesired)));\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>What a boring title. Often you&#8217;ll find yourself needing to perform a multi-level comparison. The most common example of this is performing a version check when there are major and minor version numbers involved. Bad version number checks are one of the most common sources of errors. If you&#8217;re comparing version numbers, you can use [&hellip;]<\/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-35913","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>What a boring title. Often you&#8217;ll find yourself needing to perform a multi-level comparison. The most common example of this is performing a version check when there are major and minor version numbers involved. Bad version number checks are one of the most common sources of errors. If you&#8217;re comparing version numbers, you can use [&hellip;]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/35913","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=35913"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/35913\/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=35913"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=35913"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=35913"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}