Fixing a small calc.exe bug

tldr; saw a Windows Calculator bug on reddit. Since calc.exe was open-sourced I thought I’d try to find the bug and fix it. Cloned the code, recreated the bug, and found a minimal fix.

I was goofing-off browsing Reddit, as you do on a Sunday. Scrolling past playing puppies and bad programmer humor, one particular post caught my eye.

It was about a bug in calc.exe. “Well that looks like a curious bug, I wonder what could cause it”, I though to myself. The large number of weeks certainly makes it look like some under-/overflow issue or some off-by-one error, you know, the typical causes. But it could always be some flipped bit by some high-energy ray from some friendly cosmic neighbor.

So being curious about the cause, I did what you do in these cases: try it on your machine in giddy anticipation of posting “works for me”. Actually, the exact case in the post “July 31st – December 31st” did actually give the correct result of “5 months” on my machine. But testing around a bit I found that on my machine “July 31st – December 30th” actually causes the bug. Showing the not quite so correct value of “5 months, 613566756 weeks, 3 days”.

I was not done slacking-off and I remembered “Oh, Isn’t calculator one of those things that Microsoft open-sourced?”. It is indeed. This bug couldn’t be this complex, so I thought I’d try and see if I could locate it. Downloading the source was easy enough and adding the required UWP workload to Visual Studio went off without a hitch too.

Navigating code-bases you’re not familiar with is something you get used to after a while. Especially when you like to contribute to open-source projects when you find bugs. But not even being familiar with XAML or WinRT certainly doesn’t make it trivial.
I opened the solution file and looked into the “Calculator” project, searching for any file that seemed related. Found the DateCalculator.xaml and traced the relevant sounding DateDiff_FromDate to DateCalculatorViewModel.cpp and finally DateCalculator.cpp.
While setting a breakpoint and looking at some variables I saw that the value of the final DateDifference was already wrong. So it was not just an error in the conversion to the string, but the actual calculation that was bugged.

The actual calculation looks something like this in simplified pseudo-code:

DateDifference calculate_difference(start_date, end_date) {
    uint[] diff_types = [year, month, week, day]
    uint[] typical_days_in_type = [365, 31, 7, 1]
    uint[] calculated_difference = [0, 0, 0, 0]
    date temp_pivot_date
    date pivot_date = start_date
    uint days_diff = calculate_days_difference(start_date, end_date)

    for(type in differenceTypes) {
        temp_pivot_date = pivot_date
        uint current_guess = days_diff /typicalDaysInType[type] 
        if(current_guess !=0)
            pivot_date = advance_date_by(pivot_date, type, current_guess)
        
        int diff_remaining
        bool best_guess_hit = false
        do{
            diff_remaining = calculate_days_difference(pivot_date, end_date)
            if(diff_remaining < 0) {
                // pivotDate has gone over the end date; start from the beginning of this unit
                current_guess = current_guess - 1
                pivot_date = temp_pivot_date
                pivot_date = advance_date_by(pivot_date, type, current_guess)
                best_guess_hit = true
            } else if(diff_remaining > 0) {
                // pivot_date is still below the end date
                if(best_guess_hit)
                    break;
                current_guess = current_guess + 1
                pivot_date = advance_date_by(pivot_date, type, 1)
            }
        } while(diff_remaining!=0)

        temp_pivot_date = advance_date_by(temp_pivot_date, type, current_guess)
        pivot_date = temp_pivot_date 
        calculated_difference[type] = current_guess
        days_diff = calculate_days_difference(pivot_date, end_date)
    }
    calculcated_difference[day] = days_diff
    return calculcated_difference
}

Looked good to me. Didn’t see an issue in the logic. It’s basically:

  • from the start day step in years towards the end, count years
  • from the last year before the end step in months towards the end, count months
  • from the last month before the end step in weeks towards the end, count weeks
  • set the remaining days from the week before the end

The issue is actually the assumption that running
date = advance_date_by(date, month, somenumber)
date = advance_date_by(date, month, 1)

one after the other is equal to
date = advance_date_by(date, month, somenumber + 1)
which it typically is. But the question is: “If you are at the 31st of a month and you increment to a month that only has 30 days, where do you land?”.
The answer for Windows.Globalization.Calendar.AddMonths(Int32) is apparently “on the 30th”.

This means specifically:
“July 31st + 4 Months = November 30th” and
“November 30th + 1 Month = December 30th”.
However
“July 31st + 5 Months = December 31st”.

So the operation AddMonths is neither distributive (with AddMonth being the multiply) nor commutative or associative. As you would intuitively assume of an “addition” operation. Isn’t it fun working with time and calendars?

Anyway, the reason why this seemingly off-by-one value results in such a huge number is as you might suspect that then days_diff being an unsigned type. It makes the -1 days into a huge number which then gets passed onto the following loop iteration with weeks. Which then tries to correct current_guess downwards. But it tries to correct it once again by decrementing an unsigned variable.

Well this was fun way to spend a part of my weekend. I created a Pull Request on Github with a minimal “fix”. I put fix in quotes because it then results in the following result:

Which I guess is technically correct if you concede that “July 31st + 4 Months = November 30th”. But the complete result does not really mesh with a humans intuition of date-difference. But it’s less wrong in any case.

Lenovo IdeaPad N581 broken WiFi and Windows 10 November Update

I guess I should preface this by saying that Lenovo recommends that you do not install Windows 10 on the N581.

Well this is a little bit of a different post. I just thought I’d document this little hardware issue that I encountered and had to solve.

So the situation was that after I got the November Update for Windows 10 on my Lenovo N581 the Wifi stopped working.

The solution is to update the BIOS.

I got the BIOS Updater from the Lenovo site (they make a habit of changing the URL for their support pages, so if the link is dead just navigate to their support page from lenovo.com).

For reference the device description and hardware IDs on my machine were
Broadcom 802.11n Network Adapter
PCI\VEN_14E4&DEV_4727&SUBSYS_058714E4&REV_01
PCI\VEN_14E4&DEV_4727&SUBSYS_058714E4
PCI\VEN_14E4&DEV_4727&CC_028000
PCI\VEN_14E4&DEV_4727&CC_0280

The updater was called 5ecn96ww.exe and my previous BIOS version was 3.06 and it updated to 9.01.

Just be aware that after it flashes the new version it will reset your settings. I was still using MBR Boot with GRUB, so it didn’t boot anymore after the update. I had to go into the BIOS settings and disable EFI again for the device to boot again.

But after that everything was fine again and the fan seems to kick in a lot less now. So good tidings all around.

Hope I could help someone find the solution to their problem (I know I searched the net fruitlessly for an hour).

GitHub API basic usage with Python 3

If you just need help to solve your problem you’re best off just reading the code-snippets and avoid the rest of this blog entry which merely describes my motivations behind the code.

So this started when I wanted to use the GitHub API to upload automated builds as releases yesterday. I haven’t used REST APIs much before so I read a little from their documentation and it seemed easy enough.

At first I thought I’d just use cmd or Powershell to do the deed. But the logic seemed a little too complex for cmd and I’d need something like curl. The effort to do it in Powershell seemed like a waste, since I might use this for UNIX systems later too. Since other parts of the build required Python anyway I decided to just do it in Python. I perused the web about the basics to use Python as a REST client. This excellent blog post was a helpful starting point: http://isbullsh.it/2012/06/Rest-api-in-python/ . Although it deals with Python 2 and I had Python 3 installed.

I really resented the suggestion that I’d have to add another dependency for this simple task and thought that Python had enough “batteries included” to just do it with the standard libs. So I researched a bit more about urllib2 (or urllib.request in Python 3) and it seemed to suffice for my use-case. It can’t send anything else than POST or GET requests. So if you need to use DELETE or other http methods you’ll likely need to use the http.client module.

So I clobbered together some basic script to dispatch GET and POST requests for the GitHub API for use with personal access tokens as authentication method (which you can generate here: https://github.com/settings/tokens for your account). This doesn’t work if you use two-factor authentication but rewriting the authentication part to work with OAUTH tokens instead shouldn’t be hard and work with two factor auth.

Anyway, long story short, here’s the snippet (sorry for the terrible formatting, you’ll be better off viewing it on GitHub):

import urllib.request
import base64
import sys
import os

def GitHubRequest(repository, credentials, url, data=None, datatype=None, useRawURL=False ):
    """ GitHubRequest(repository, credentials, url, data=None, datatype=None, useRawURL=False ) -> response, returncode
    
    This function is thoroughly unpythonic and you should probably just use it
    as a starting point.
    It dispatches a request to the GitHub API (written with v3 in mind).
    A GET request if data is not specified, a POST request with the string in
    data if datatype is not specified and a POST request with the contents of
    the filename in data if datatype is specified.
    
    Arguments:
        repository  - GitHub with in the format 'User/Repository'
        credentials - GitHub username and personal access token in the format
                      'username:accesstoken'
        url         - the GitHub API url, for example 'issues/3' or a complete
                      url if useRawURL is set to True
        data        - string specifying the data to be send, if datatype is
                      None the string is send, otherwise a file with the name
                      is opened and sent
        datatype    - the type of data to be, if it's a str it will be used as
                      MIME type for the POST request, if it't not a str or 
                      NoneType then the MIME type will be 'application/octet-stream'
        useRawURL   - specify whether the url is the full request URL (when
                      True) or just a partial url to append to 'apiurl/repo/'
    """
    if isinstance(credentials,str):
        credentials = bytes(credentials,'UTF-8')
    if useRawURL == True:
        requesturl = url
    else:
        requesturl = "https://api.github.com/repos/%s/%s" % (repository, url)
    
    print("request: %s" % requesturl)
    #GET request
    if data==None:
        req = urllib.request.Request(requesturl)
    else: #POST request
        if datatype==None:#JSON POST request
            req = urllib.request.Request(requesturl, data=bytes(data,'UTF-8'))
        else: #File POST request
            filehandle = open(data,'rb')
            req = urllib.request.Request(requesturl, data=filehandle)
            filesize = os.path.getsize(data)
            req.add_header("Content-Length", "%d" % filesize)
            if isinstance(datatype,str):
                req.add_header("Content-Type", datatype)
            else:
                req.add_header("Content-Type", "application/octet-stream")
    if credentials!=None:
        base64str = base64.b64encode(credentials)
        req.add_header("Authorization", "Basic %s" % base64str.decode("utf-8"))
    
    try:
        handle = urllib.request.urlopen(req)
    except IOError as e:
        code = -1
        if hasattr(e,'code'):
            code = e.code
        message = str()
        if hasattr(e,'fp'):
            message = e.fp.read()
        if 'filehandle' in locals():
            filehandle.close()
        return message, code
    response = handle.read()
    if 'filehandle' in locals():
        filehandle.close()
    return response, handle.getcode()

And here’s my main usage case (similar version better viewable at GitHub):

#!/usr/bin/env python

from GitHubRequest import GitHubRequest
import urllib.request
import base64
import sys
import os
import json

def main():
    credentials = bytes(sys.argv[1],'UTF-8') #in the format 'User:privateaccesstoken'
    repository  = "Bigpet/rpcs3-buildbot-tools"
    filename    = "some.zip"
    releasename = "sometag"
    commitish   = "3d2659fb20061d43a0057830fca30101c329e06a"
    
    #Check if the tag already exists
    response, code = GitHubRequest(repository,credentials,"releases/tags/%s"%releasename)
    print("code: %d"%code)
    if code == 200: #already a release with this tag there
        #expected
        code = 200 #do nothing
    elif code == 404: #no release with this tag yet
        #Create release
        requestdict = {'tag_name': releasename, 'prerelease': True}
        if commitish != None:
            requestdict['target_commitish'] = commitish
        response, code = GitHubRequest(repository,credentials,'releases',json.dumps(requestdict))
        if code != 201:
            print("got unexpected return code %d while creating a release: %s"%(code,response),file=sys.stderr)
            sys.exit(1)
    else:
        print("got unexpected return code %d while looking for release: %s"%(code,response),file=sys.stderr)
        sys.exit(1)
    
    #Get upload_url
    resdict = json.loads(response.decode('utf-8'))
    upload_url = resdict['upload_url']
    upload_url = upload_url.replace('{?name}',"?name=%s"%filename)
    
    assets = resdict['assets']
    for asset in assets:
        if asset["name"]==filename:
            print("File %s already exists in tag %s"%(filename,releasename),file=sys.stderr)
            sys.exit(1)
    
    #consider just using "application/octet-stream" for generic files
    response, code = GitHubRequest(repository,credentials,upload_url,filename,"application/zip",True)
    if code != 201:
        print("got unexpected return code %d while trying to upload asset to release: %s"%(code,response),file=sys.stderr)
        sys.exit(1)

if __name__ == "__main__":
    main()

Adventures with Emscripten

This is just an account of my first experiences with Emscripten and this is empatically not a tutorial for ,or review of emscripten.

Smooth sailing period

So I started to make a small test-game with SDL2 and thought I’d try to compile with emscripten. So I downloaded the Windows SDK and since I didn’t have a CMake or other unixy compatible Makefile for the project yet I just made a unit-build like *.cpp that includes all *.cpp files to compile.

Just doing the “em++ -I../src unity.cpp” got surprisingly far, it had some issues with some SDL Functions though. I imagine it to be because it presumes SDL1.2 instead of SDL2. So searched for whether it SDL2 was available for emscripten as well.

Some bumps in the road

It was, in source form. After downloading the source my problems started. The build-instructions for SDL-emscripten told me to use “emconfigure ./configure […]” which didn’t work under Windows since it couldn’t find any executable named “configure”.

Alright, so that was a no-go. But there was another suggestion to do the configuration with “emconfigure cmake”. This failed for me because I accidentally tried to execute that inside the source tree, which just gave me an error about it. Since I didn’t want to hunt for all the configuration files to delete, I just unzipped the SDL source tree again and corrected my error.

While CMake now generated project files successfully it was sadly VS2013 project files, which naturally don’t work at all. So I had to switch the CMake generator to “MSYS Makefiles” to hopefully get something useful. CMake again happily obliged to generate Makefiles. Now just to open my MSYS shell and type “make” right? Not quite, the *.bat files to set up the environment variables to get emscripten to run didn’t work in bash for obvious reasons and the *.sh file that was in the emscripten directory just called some other *.sh files that were nowhere to be found. Well that’s enough of that, I got the message. Windows isn’t really suited to run these tools that are primarily designed for UNIX like environments.

“Well, I’ll just try my Linux Laptop then” I thought to myself a little spitefully. There downloading the SDK files wasn’t an issue either, but the installation entails compiling LLVM clang which took a little while. In fact such a while that I started writing this blog post in the meantime.

Back on track?

“Alright, so this should be easier” I told myself. I was not quite without issues though. For some reason it tried to call nodejs by “node” but my Ubuntu distro only had it under the name “nodejs” so I had to install a legacy package that created a symlink (not that I couldn’t make the symlink myself, but this way it gets cleaned up if I ever remove nodejs).

Getting “something” to compile was taken care of after that. It was just linking that was a problem now. Curiously linker errors are just warnings with emscripten (presumably because you can patch those in at runtime in Javascript). It took me quite a while to figure out that using “em++” to link didn’t work. So I had to compile with “em++” and link that resulting obj-file with “emcc” to get it to cooperate.

That was a good waste of a Saturday.

More MSVC Compiler bugs

So recently 2 of my bug-reports to the Microsoft Visual Studio “14” CTP got acknowledged as bugs. I thought I’d recap them here.

The first one is a pretty straight-forward library regression. The local aware character classification functions from <ctype.h> like _isalnum_l now have one argument of the apparently internal type __crt_locale_pointers (_locale_t is typedef’ed to it). This appears to be a remnant/copy&paste-error of using this code in the CRT. This wouldn’t be an issue if the <ctype.h> header would declare that type but it doesn’t. No biggie, this was a straightforward regression from MSVC 2013.

The other bug was a little more C++ language related and a little more confusing too. The minimal code example that crashes is this:

#include <string>

struct Msg
{
  std::string mText;
};

void log(Msg msg){}

int main() {
  log({ "t stuff" });
  return 0;
}

What happens here is that the compiler correctly constructs the Msg object and elides a copy but then calls the destructor twice (once on an invalid location). This of course won’t cause crashes for trivially destructible types but resource owning types like std::string cause this program to crash.

This error happened in both MSVC 2013 and MSVC “14” CTP.

This should be enough to chronicle some more of the bugs I personally encountered, not really much a point beside that to this post.

Windows Touch and Pen disambiguation

So I happened to implement multi-touch for PPSSPP and to do that I consulted the Windows documentation which made me request touch input with RegisterTouchWindow and then handle the resulting WM_TOUCH events, the only issue is that Windows still sends the emulated WM_LBUTTONDOWN WM_MOUSEMOVE and WM_LBUTTONUP, so I needed to filter the events that came from touch to not handle them twice.

The docs recommendeded I filter with

#define MOUSEEVENTF_FROMTOUCH 0xFF515700
#define MOUSEEVENTF_MASK 0xFFFFFF00
//...
//...
case WM_LBUTTONDOWN:
if ((GetMessageExtraInfo() & MOUSEEVENTF_MASK) != MOUSEEVENTF_FROMTOUCH)
{
//handle mouse events here
}
break;
case WM_TOUCH:
//handle touch here

But turns out this silently makes pen inputs disappear in a black hole as they trigger MOUSEEVENTF_FROMTOUCH but don’t generate a WM_TOUCH event. So I added the 0x80 bit to the mask which is 1 when the source is touch and 0 when the source is a pen/stylus.

#define MOUSEEVENTF_FROMTOUCH_NOPEN 0xFF515780 
#define MOUSEEVENTF_MASK_PLUS_PENTOUCH 0xFFFFFF80
//...
//...
case WM_LBUTTONDOWN:
  if ((GetMessageExtraInfo() & MOUSEEVENTF_MASK_PLUS_PENTOUCH) != MOUSEEVENTF_FROMTOUCH_NOPEN)
  {
    //handle mouse events here
  }
  break;
case WM_TOUCH:
  //handle touch here

Internal Compiler Error woes

The nightmare of every programmer are silent compiler bugs. But fortunately I didn’t have to deal with one of those. One of the runner ups for me has to be compiler errors.

The occasion for this post is me recently encountering an internal compiler error in Visual C++ 2013RC. It’s documented¬†here¬†and has apparently been fixed in the full version but I currently don’t have access to it and so I’m trying to work around it without updating my compiler.

The error appears somewhere in the function

static ALWAYS_INLINE void diff(BigInt& c, const BigInt& aRef, const BigInt& bRef)

which is defined in the dtoa.cpp (double to ascii apparently) that as far as I can tell originates from the WebKit project and is used for JavaScript.

Anyway, the error suggests that I simplify the code around the area where the error occurs. So, I did.

After commenting out code until the compilation works and partitioning the function to get to the exact problem area, I found out that it was

do {
  unsigned long long y = (unsigned long long)*xa++ - *xb++ - borrow;
  borrow = y >> 32 & (uint32_t) 1;
  *xc++ = (uint32_t) y & 0xffffffffUL;
} while (xb < xbe);
while (xa < xae) {
  unsigned long long y = *xa++ - borrow;
  borrow = y >> 32 & (uint32_t) 1;
  *xc++ = (uint32_t) y & 0xffffffffUL;
}

Which I “simplified” to this:

do {
  unsigned long long y;
  if (xb < xbe)
    y= (unsigned long long)*xa++ - *xb++ - borrow;
  else
    y = *xa++ - borrow;
  borrow = y >> 32 & (uint32_t) 1;
  *xc++ = (uint32_t) y & 0xffffffffUL;
} while (xb < xbe || xa < xae);

I’m keenly aware of the performance characteristics of this change but I just wanted to make it compile with my current setup and so this did it. I don’t plan on using much JavaScript with QT anyway, so that shouldn’t be an issue for me anyway. Just wanted to archive this for my purposes and to help a few people who are possibly in the same situation. I might post a patch a little later.

MadEdit rocks my socks off

I really don’t have a strong opinion on the text-editor war (I mean Emacs vs Vi[m]). This is due to the fact that I use neither of them. I know that you can be incredibly efficient with them once you learn how to use them. But I just don’t feel comfortable to switch at the moment.

This is mainly due to the fact that I once took the task upon me to use Regular Expressions to reformat an ancient 6,5MB table in .txt format to something that I could import into a MySQL Database.

Well this sounds simple enough, although finding a text editor with decent RegExp support is not. I really searched high and low to find a simple text editor that can deal with multiple-line matches and capturing groups. What I finally found was Notepad RE whose whole reason for existence is using a complete implementation of the Perl Regular Expression standard. It’s a neat little program but lacks some of the other features I needed.

Then I finally stumbled upon MadEdit. It is ancient, not maintained and has a very Windows 98 looking Interface. But nonetheless it’s the best simple to use text editor I have found to date. Why you ask? Well:

  • Syntax Highlighting for most programing and markup languages
  • very good support for regular expressions
  • search/replace using regular expressions on multiple files or even folders
  • multi platform
  • a seamless transition from text-mode to column-mode to Hex-Editor mode
  • Hex search and replace
  • support for ancient encodings like CP 437
  • a pretty strange Icon

Seriously this icon seems to make people curious as to what it is all about. Really there are multiple people who have asked me about the Icon as they saw it in my task-bar or on my desktop.

I am probably going to transition to Vi(m) sooner or later but until then I am going to love every Minute of using MadEdit.

originally posted: 22.06.10 05:39
Edit (20.01.2013): I’ve recently found Sublime Text 2 to be offering some features that I’m missing in MadEdit but I’ll still keep it around for the occasional batch Regex or hex editing job.

STL and DLL don’t mix

If you ever want to write a dll (dynamic linked library) and use STL (Standard Template Library) types as attributes, parameters or return values of function or classes don’t. Unless you really absolutely have to make dll, just compile it into a .lib and statically link it to your executable.

In case it is inevitable to use std::string, std::vector and the like you can refer to the MSDN for help. Or you can write wrappers for each type you use to hide them from the dll interface. But I have to say that I find this solution really ugly. As a whole C++ feels more and more ancient the longer you are exposed to more “modern” languages like Java, C#, python and the like. Circular includes being impossible and templates being very restrictive (if you try to use them like generics) are other pet-peeves I have with this language.

I mean you can hope that C++0x fixes some of the things that make you cringe when you have to write them but I really doubt it.

originally posted: 23.06.10 09:21

That’s what you get for using beta versions (Qt)

I recently used the 4.7 beta version of Qt to start writing a User Interface for a program because I used Visual Studio 2010 for the backend and had higher hopes of getting VS2010 compatibility with Qt 4.7.

I very quickly ran into repainting issues when setting the [int stretch=0] Argument in QStatusBar to 1 or when using [ void addPermanentWidget(QWidget *widget) ]. Strangely I can’t recreate this mistakes on my desktop now (Win 7 64bit). But I fruitlessly spend hours trying to fix this problem on my laptop (Win 7 64bit). Turns out it’s a bug most likely. For one thing I can’t replicate the same behavior on my Desktop and this Problem doesn’t occur on the Laptop when I compile the exact same code against Qt 4.6. I haven’t reported this bug yet because I haven’t used the latest checkout to verify that it hasn’t yet been fixed and I probably won’t as it just takes too much time.

So the lesson learned here is: never use beta versions in production except when it’s just for a test. Even and especially if you’ve never had problems using beta versions before. Because if you’ve never had bugs in a beta you are very unlikely to blame it on a bug.

originally posted: 28.06.10 12:54