Answers to exercise from Scrollbars Part 11

Date:September 17, 2003 / year-entry #67
Tags:code
Orig Link:https://blogs.msdn.microsoft.com/oldnewthing/20030917-00/?p=42453
Comments:    0
Summary:Exercise: Why do we use the formula c = a + (b-a)/2 instead of the simpler c = (a+b)/2? Answer: To avoid integer overflow in the computation of a+b. Here, a and b are window coordinates, and the window can be anywhere. If the window were placed at extreme coordinates like (MAXLONG,MAXLONG), then the arithmetic...

Exercise: Why do we use the formula c = a + (b-a)/2 instead of the simpler c = (a+b)/2?

Answer: To avoid integer overflow in the computation of a+b.

Here, a and b are window coordinates, and the window can be anywhere. If the window were placed at extreme coordinates like (MAXLONG,MAXLONG), then the arithmetic would overflow and the "midpoint" would be incorrectly computed.

Note that the alternate formula a+(b-a)/2 is also subject to overflow, this time in the computation of the value b-a. However, in our case, b-a is the width of our window, which is something that we can control.

Integer overflow was one of the Windows 95 application compatibility bugs that I had to deal with. There was a DOS game that wanted to do a binary search, and instead of using indices, they attempted to average the two pointers together: 

BYTE *low = ...;
BYTE *high = ...;
BYTE *mid = ((UINT)low + (UINT)high)/2;

This worked as long as the game was being run under an operating system without virtual memory, because the "low" and "high" pointers would both be comparatively small numbers (nobody had machines with 2GB of RAM), so the sum low+high would not overflow.

Windows 95 ran these DOS games, but under a DPMI server that supported virtual memory. The DPMI specification permits the server to put memory anywhere, and we put our memory at the high end of the address space.

This program then overflowed in its attempt to average the two pointers and crashed.

So be careful how you average two values together. It's harder than you think.


*DISCLAIMER: I DO NOT OWN THIS CONTENT. If you are the owner and would like it removed, please contact me. The content herein is an archived reproduction of entries from Raymond Chen's "Old New Thing" Blog (most recent link is here). It may have slight formatting modifications for consistency and to improve readability.

WHY DID I DUPLICATE THIS CONTENT HERE? Let me first say this site has never had anything to sell and has never shown ads of any kind. I have nothing monetarily to gain by duplicating content here. Because I had made my own local copy of this content throughout the years, for ease of using tools like grep, I decided to put it online after I discovered some of the original content previously and publicly available, had disappeared approximately early to mid 2019. At the same time, I present the content in an easily accessible theme-agnostic way.

The information provided by Raymond's blog is, for all practical purposes, more authoritative on Windows Development than Microsoft's own MSDN documentation and should be considered supplemental reading to that documentation. The wealth of missing details provided by this blog that Microsoft could not or did not document about Windows over the years is vital enough, many would agree an online "backup" of these details is a necessary endeavor. Specifics include:

<-- Back to Old New Thing Archive Index