64bit Scrollbars

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 in Windows

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.

Managing scrollbar variables

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.

Scaling a scrollbar’s range

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…

SetScrollInfo64 first steps

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.

SetScrollInfo64

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.

GetScrollPos64

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.

How to use this new API

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);
}

Possible optimization yields bad results

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 :-)

Conclusion

You may be wondering why I bothered doing all this work when I could have used floating point arithmetic. Here’s why.

• It isn’t necessary!
• Floating point arithmetic in VC++ cannot represent the largest 64bit integer numbers accurately. I couldn’t be bothered to work out if this would be an issue or not.
• Floating point maths requires the use of extra runtime support and introduces bloat that we don’t need.
• I consider floating point math dirty and try to avoid it unless the benefits of simplicity outweigh that dirty, sordid feeling you get when you hit that compile button, knowing that those filthy doubles will be corrupting your sleek integer-only program somehow.
• Did I mention that I don’t like floating point? :-)

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.