Recently I have been rewriting part of my HexEdit application. One specific area was to properly handle 64bit file sizes (i.e. files that were over 4Gb in size). The problem I faced was not the loading of files this large, but the issue of initializing Win32 scrollbars with 64bit values. Seeing as I found a nice elegant solution to the problem I thought I would share the results of my work.
Scrollbars have always been an integral part any GUI-based application. However in Windows operating systems the supported scrollbar range has always been tied to the native WORD width of the OS - for example Windows 3.1 (a 16bit OS) used 16bit quantities to represent scrollbar metrics. This provided applications with a scrollbar range of -32768 to 32767.
When Microsoft introduced their win32 API model they extended the standard scrollbar range to use LONG values whilst still maintaing compatibility with the older 16bit model. This allowed a scrollbar's to maximum range to increase -2147483648 to 2147483647. This is still way short of the maximum value a 32bit unsigned integer can hold, but for most applications this scrollbar range is more than satisfactory.
Although uncommon, there are some applications which require a scrolling range beyond that which Windows natively provides. Extending a scrollbar's range to a 64bit number system would be very useful especially for hex-editors.
Fortunately Microsoft Visual C++ has a built-in integer type which can represent 64bit numbers - the __int64 type. An unsigned __int64 (or UINT64) variable can hold a maximum value of 18,446,744,073,709,551,615. That's a pretty big number (18 Exa-bytes), considering the the maximum value a 32bit unsigned integer can hold is 4,294,967,295 (4 Giga-bytes).
It is fairly obvious that a 64bit number will not fit into a 32bit variable so the solution is to maintain each scrollbar's range in "external" 64bit variables and scale these numbers down to 32bits whenever we want to access a scrollbar's settings.
As a programmer you don't need to do anything different when dealing with 64bit scrollbar quantities. Most programs will already maintain scrollbar state so the only thing that changes is the size of the variables (32bit -> 64bit) .
To keep things simple we ignore the fact that a scrollbar has a "minimum" value and will make the scrollbar range zero-based - this makes the maths later on much easier. So the only values we need to keep track of are the scrollbar's position, and it's current maximum value:
UINT64 nScrollPos64; UINT64 nScrollMax64;
Of course these variables would normally be stored as C++ class members but thats not really important for this example. Below shows a typical scrollbar sequence of code.
void OnVScroll(HWND hwnd, int nSBPart)
{
switch(nSBPart)
{
case SB_TOP:
nScrollPos64 = 0;
break;
case SB_BOTTOM:
nScrollPos64 = nScrollMax64;
break;
case SB_LINEUP:
nScrollPos64--;
break;
case SB_LINEDOWN:
nScrollPos64++;
break;
case SB_THUMBTRACK:
nScrollPos64 = GetScrollPos64(hwnd, SB_VERT, nScrollMax64);
break;
}
SetScrollInfo64(hwnd, SB_VERT, SIF_ALL, nScrollMax64, nScrollPos64, nScrollPage, TRUE);
}
If you look at the code above you will see there are two function calls highlighted
in bold - GetScrollPos64 and SetScrollInfo64. Of
course, normally a program would call the "normal" Win32 GetScrollPos
and SetScrollInfo but we must do things a little differently
if we are to emulate 64bit scrollbar ranges.
What I have done is to create an interface between our 64bit scrollbar variables and the win32 scrollbar APIs. These two functions act just like the win32 API - and hide the complexity of the 32bit/64bit conversions that must be managed. The idea is to provide a mechanism to support 64bit scrollbars without having to change any scrolling logic.
As mentioned above we must maintain our "64bit" scrollbar range
separately from the Windows scrollbar. The relationship between the two scroll
ranges can be expressed using a simple mathematical formula. For convenience's
sake I will refer to these two ranges using four separate variables - pos32,
max32 (for 32bit scrollbar ranges), and pos64, max64
(for 64bit ranges).
Recall that previously I mentioned there were two new functions to be written
- GetScrollPos64 and SetScrollInfo64. What you must
understand is this:
There are really only two tasks that are commonly performed with scrollbars. The first is to set the scrollbar thumb position programmatically. The second is to retrieve the scrollbar thumb position when it has been modified (dragged) by the user.
Therefore to set the scrollbar position we must call one of the Win32 scrollbar
APIs - SetScrollInfo is the most common for 32bit programs. Before
we call SetScrollInfo we must calculate the real (32bit) thumb
position by performing some kind of mathemetical operation. By
using simple rearrangement of the original formula we can derive our first
equation:
It really is that simple! Now onto the second task, which involves retrieving
the 64bit scrollbar thumb position using the Win32 GetScrollInfo.
The rearrangement below gives us our second equation.
In both of these equations we always know what value two of the variables
will be - but max32 is always an unknown
so we can't solve the equations yet. It actually doesn't matter what this
value is, as long as we set it to some known quantity in order to solve the
equations. MAX32 will therefore be defined as a constant integer
value (something like 0x7ffffffff). With all three variables now known, we
can solve both equations. It's time to put this into code...
So our first task will be to implement a function which can set a scrollbar's range, given two 64bit values and a 32bit constant. In order to work out what to set the scrollbar position to, we use the first equation:
Now before we rewrite this equation in "C" notation you should understand the following concept:
In mathematics, it doesn't matter what order the equation is evaluated in. We could perform the multiplication first then the division, or we could divide first of all then multiply up. It doesn't matter because real maths uses real numbers.
This idea is illustrated below but in "C" notation:
pos32 = (pos64 * MAX32) / max64; pos32 = (pos64 / max64) * MAX32;
The first equation is traditionally the preferred "programmatic" method because there will be less loss of precision. This is because the integer division operation on a CPU will always lose precision - by the very nature of how integer arithmetic works:
By performing the division first of all (the second method) there is the
potential to lose accuracy when pos64 and max64 are
close in value - and when the multiplication is subsequently performed it
is using inaccurate numbers. The first method does not have this problem because
we multiply first of all (maintaining precision) and only lose precision at
the very end resulting in a more accurate answer. This is a common approach
in programming which you are hopefully aware of.
Now ordinarily we would opt for method#1, but there is a problem with this
approach. Because we want to use the full range that the 64bit numbers can
represent, we will suffer from integer overflow when pos64
and max32 are both very large. We could theoretically
use 128bit integers to hold the numbers whilst we calculate the expression
but this would be very difficult without built-in compiler support.
At this point we might have got stuck - but we haven't finished rearranging
our equation yet. If we divide the numerator and demoninator by max32
we end up with:
pos32 = (pos64 * MAX32 / MAX32) / (max64 / MAX32)
This can be simplified and our original formula can now be re-written as:
In "C" notation this looks like:
pos32 = pos64 / (max64 / MAX32)
Now I realise that this probably doesn't look like the ideal way to solve
this problem using integer maths (we have two divisions now) but
I have a trick up my sleeve. With this third rearrangement we can
control the accuracy of the division operator - because we control the value
of max32.
When max64 is very large the result of the division is quite accurate (in integer terms!) - i.e., when max64 is a fair bit larger than max32. However when max64 approaches max32 in value the result will become very inaccurate, as we already know. The trick is to never allow these values to get this close together.
Because we control what max32 will be it is natural to set it
to the maximum value that a 32bit scrollbar can hold - 0x7fffffff (2147483647).
But there is no reason why we couldn't just choose a much lower number - for
example 0x7fff (32767, the maximum value of a 16bit scrollbar!).
Remember that max32 is the value we give the scrollbar maximum
range using SetScrollInfo, and that I am now proposing that we
set this maximum value to 32767 - far less than the maximum number a 32bit
integer can hold. The thing is, it really doesn't matter what we set the scrollbar
maximum to. We are scaling number ranges anyway so we will never be 100% accurate
- and anyway, this scroll range still has to get translated even further when
Windows displays the scrollbars on screen. The point is, noone will ever notice.
The original problem still remains though - when max64 this
time approaches 32767 (i.e. 32768) we still lose precision. However we are
now in the position where we can prevent this from happening. The way we do
this is simple: when max64 happens to be in the range 0x7fffffff to 0x7fff
(i.e. within the range of a regular 32bit number) we can simply revert to
the normal Win32 API because all our numbers will be 32bits!!
if(max64 <= WIN32_SCROLLBAR_MAX)
{
pos32 = pos64;
}
else
{
pos32 = pos64 / (max64 / WIN16_SCROLLBAR_MAX);
}
Simple, no? Well I think so anyway. Anyway let's define these two "maximum" limits as follows:
#define WIN16_SCROLLBAR_MAX 0x7fff #define WIN32_SCROLLBAR_MAX 0x7fffffff
Now we still don't have to use these exact numbers - as long as we choose two numbers which are far enough apart (2147450880 in this case!!) we can ensure that our sums will always be very accurate.
We can now write our first replacement scrollbar API, SetScrollInfo64.
Before you cast your eyes down, be aware that the names of the variables we
are used to (pos32, max32, max64 etc)
have now changed to be more meaningful for a Win32 program.
// // Wrapper around SetScrollInfo, performs scaling to // allow massive 64bit scroll ranges // BOOL SetScrollInfo64( HWND hwnd, int nBar, int fMask, UINT64 nMax64, UINT64 nPos64, int nPage, BOOL fRedraw ) { SCROLLINFO si = { sizeof(si), fMask }; // normal scroll range requires no adjustment if(nMax64 <= WIN32_SCROLLBAR_MAX) { si.nMin = (int)0; si.nMax = (int)nMax64; si.nPage = (int)nPage; si.nPos = (int)nPos64; } // scale the scrollrange down into allowed bounds else { si.nMin = (int)0; si.nMax = (int)WIN16_SCROLLBAR_MAX; si.nPage = (int)nPage; si.nPos = (int)(nPos64 / (nMax64 / WIN16_SCROLLBAR_MAX)); } return SetScrollInfo(hwnd, nBar, &si, fRedraw); }
This function doesn't look exactly the same as the regular SetScrollInfo
because we are passing all of the scrollbar metrics as parameters rather than
using a separate SCROLLINFO structure - or SCROLLINFO64
as it would have to be called. I think it's neater this way so I've
left it as it is.
The second task (calculating the 64bit scrollbar position) is somewhat simpler because we (hopefully!) understand the issues involved now.
Writing this equation in "C" notation yields the following:
pos64 = (pos32 * max64) / MAX32
Of course we have the overflow problem again with the multiplication, but
we now know that the division operation will not produce the inaccuracy we
fear because we can control the values of max64 and max32
just like before. We can therefore safely change the order of evaluation as
shown below.
pos64 = pos32 * (max64 / MAX32);
One thing that we must be careful of is the situation where the scrollbar
thumb is right at the very end of its range (i.e. the thumb position is equal
to the maximum position). The reason is that integer math always rounds down.
Even when the scroll-thumb was at it's maximum value, there would be alot
of cases when pos64 would never equal max64. Therefore
I have a special case for this end-of-scroll-range and force pos64
to be equal to max64 in this situation.
// // Wrapper around GetScrollInfo, returns 64bit scrollbar position // fMask must be either SIF_POS or SIF_TRACKPOS // size_w GetScrollPos64( HWND hwnd, int nBar, int fMask, UINT64 nMax64) { SCROLLINFO si = { sizeof(si), fMask | SIF_PAGE}; UINT64 nPos32; if(!GetScrollInfo(hwnd, nBar, &si)) return 0; nPos32 = (fMask & SIF_TRACKPOS) ? si.nTrackPos : si.nPos; // special-case: scroll position at the very end if(nPos32 == WIN16_SCROLLBAR_MAX - si.nPage + 1) { return nMax64 - si.nPage + 1; } // normal scroll range requires no adjustment else if(nMax64 <= WIN32_SCROLLBAR_MAX) { return nPos32; } // adjust the scroll position to be relative to maximum value else { return nPos32 * (nMax64 / WIN16_SCROLLBAR_MAX); } }
For this second function we require the scrollbar's nPage as
part of the calculations - so have obtained it from the scrollbar rather than
passing it in as a parameter. This is just for neatness as usually you wouldn't
want to worry about this small detail - but be aware that it is happening.
It really isn't any different than what you would do normally!
void example(HWND hwnd)
{
UINT64 max = 0xffffffffffffffff;
UINT64 pos = 0x1234567812345678;
SetScrollInfo64(hwnd, SB_VERT, SIF_ALL, max, pos, 15, TRUE);
// when reacting to a WM_VSCROLL, with SB_THUMBTRACK/SB_THUMBPOS:
pos = GetScrollPos64(hwnd, SB_VERT, SIF_TRACKPOS, max);
}
I mentioned earlier that the numbers we used for max32 and max64
didn't have to be the exact values I chose.
You could in fact set max32 (WIN16_SCROLLBAR_MAX as
it is now known) to be a power-of-2 (i.e. 0x8000, just 1 more than it is now).
This would eliminate one of the divisions because we could use bit-shifts
instead. The reason I stuck with a divide-by-0x7ffff rather than a divide-by-0x8000
(a right-shift-by 15) is this:
I designed these functions for use in a Hex Editor. If we used a right-shift instead of a division the result would be that the scrollbar positions would not be very granular. Every time we scrolled the scroll-thumb up and down, the resulting 64bit position would always be a multiple of 0x8000 (32768). It would look like there is a loss of precision and make the address-column in a hex editor look very "sticky". A divide by 0x7fff (32767) yields much better randomness of the bits and the result is more "natural".
If you decide that this apparent loss of precision is not a problem then go ahead and optimize all you like :-)
You may be wondering why I bothered doing all this work when I could have used floating point arithmetic. Here's why.
doubles will be corrupting
your sleek integer-only program somehow. Hopefully you have found this tutorial useful, or at least interesting as you may not have any immediate use for this subject. Anyway as before I'd appreciate any feedback you may have.
Please send any comments or suggestions to:
Last modified: 05 September 2005 08:32:04