The New Sudoku Players' Forum

[Mathimagics]

I decided to return to a thorny problem I had reported earlier, to see whether I could get dobrichev's fsss2 solver to compile/link under GCC on Win32. I have a particular need for it (although I'm running Win64 mainly which works fine) and was frustrated by this first attempt.

Anyway, my fiddling with compiler versions had created a hernia on my Win32 box, so I binned it all and went looking for a clean GCC build. I got lost in the wilds of SourceForge for some considerable time, but finally hit on this page:

https://sourceforge.net/projects/mingw-w64/files

This guy (and I believe I've come across his work before, on the Mersenne forum) has done a fantastic job, creating stand-alone GCC/G++ compilers that simply work without fuss, without installers, these are as close to "painless installation" as I've ever seen.

Not only that, he has been building these for most major versions of GCC - the latest is 8.2, his builds go back to 4.8 and beyond.

But wait, there's more! He makes builds for Win32, Win64, and some that run on Win64 but can optionally compile/link in Win32 mode!

The procedure to install GCC from these builds is:

• goto the link, scroll down to the appropriate Toolchain area (Win32, Win64, dual target) and follow the chain down to a specific binaries package (this will be a 7Z file)

• download the package, unzip it into some folder. You should now have a "somefolder\mingw32" folder (with subdirectories "bin", "include" etc), which you can now move/rename to some central location, eg C:\GCC or C:\MinGW).

• edit your system-wide PATH environment variable to include a reference to that final location's "bin" folder (eg "C:\MinGW\bin")

That's it, you should be able to enter "gcc --version" in a CMD.exe window and confirm your installation was correct, and away you go.

[Mathimagics]

.
I don't know yet whether my original problem has been solved, but there is strong evidence to suggest that it will be!

The original problem arose when I tried to compile an fsss2-based Sudoku solver on Win32 using GCC. The compiler complained about some of the key 128-bit support functions in t_128.h, saying they weren't available, or couldn't be inlined.

Now then, I don't actually want to use this solver on my Win32 box, what I really want is a version that can be made into a Win32 DLL that can be CALLED from apps running on the Win64 box.

Why? Because I have only one GUI development environment, the venerable but still eminently useful VB6.

And that, along with any apps built with it, can only run in the special 32-bit mode runtime environment (WOW64) that Win64 kindly supports. But this is strictly a closed shop, and you can't call any 64-bit DLL's from there.

So moving to Win64 gave me a big headache. I can't call any of the new solver variants, only those solvers for which I have a 32-bit DLL built. Since I became heavily dependent on these "128-bit solvers", my DLL supply has been abruptly cut off. Like a junkie looking for a fix, I'm now hopelessly dependent on these solvers.

So I've had to resort to writing "emulation" solver functions in VB6 for each new Sudoku variant, a process that involves much pain and grief, debugging etc, and then when they do work they have pretty degraded performance (the 32-bit mode emulation is great, please don't take it away, but it is slow!).

The dual-target GCC compiler looks like being the solution. I have already identified two key t_128 methods that were causing grief (isSubsetOf, to_int64) and have found simple alternatives that work in Win32 mode. I have adjusted my header file so it works whichever compiler mode I select.

That works for a simple test program, now there's only one last hurdle to jump - can I compile a complete 128-bit solver and turn it into 32-bit DLL

We will soon find out!

[Mathimagics]

.
Bingo!

It works like a charm … I can call the solvers directly from my apps, and from the IDE. That is such a relief …

And a big thank you to our man at the Forge!

[tarek]

Hi Mathimagics,

I am also interested in the 128 bit environment as it makes bit-masks working environment more efficient.

Would these work in GCC under windows 64 (int_128 for instance)?

tarek

[Mathimagics]

Yes, that is exactly what the t_128 stuff, that I referred to above, does.

A quick overview of dobrichev's fsss2 solver is in order (and Mladen will surely let me know if I stuff this up!):

• Sudoku cells can be represented as 128-bit masks. 81 bits are used to represent which cells are affected by setting this cell (aka the visible cell list), 27 bits are used to indicate which houses this cell belongs to (rows/cols/boxes)

• Grid state can be represented by 9 128-bit masks. These indicate all current candidate cells for the digits 1 to 9.

t_128 is a header file that defines (for C++) a class of logical operations that uses SSE instructions (MMX registers) wherever possible to make 128-bit mask operations very fast on CPU's that support this instruction set. Some of these operations can be done on pairs of operands (2 MMX registers) particularly fast.

These days SSE (4.1 is the applicable version I think) is available on most (if not all) Intel chips, AMD, and probably many others. You don't actually need Win64, it can work equally well on Win32, it's all about the CPU you have.

So it's not a complete uint128_t implementation for general arithmetic (long long long?), but for bit-masking ops it covers all the bases, and that's all we need to build a very fast solver based on this model.

Our SourceForge guy developed GCC builds that were "tuned" for specific Intel CPU familes (Sandy Bridge etc). His objective (I believe) was to then create similarly "tuned" GMP libraries (compiled with GCC) which in turn allowed "tuned" versions of various open-source Prime Factorisation methods to be produced.

[tarek]

Thanks Mathimagics,

I'll attempt to digest these issues in the near future

tarek

[dobrichev]

Just to mention that 128-bit SSE operations are not GCC specific at all.
In order to use the SSE instructions, non-standard compiler-specific extensions should be used and all compilers have their own.
Porting from one compiler to another is matter of some cosmetic changes (which by the way are already done in my code).

Another non-major problem is handling the differences between the variety of the SSE instruction subsets implemented on different processor models.
My resolution is the use of relatively old (but not ancient) subset, and investigation of compiler-specific instruction names and compilation options case by case.

The differences between 32-bit and 64-bit platform came from non-SSE instructions. Examples are counting the bits set, popcount(), or finding the least significant non-zero bit. On 64-bit platform it is sufficient to split the field to 64-bit pieces and perform your logic, where on 32-bit you should double the operations and complicate the logic.

Repeating what Mathimagics said, SSE isn't 128-bit arithmetic (and recently 256 and 512-bit) but coprocessor capable of execution of limited set of instructions on several data words in parallel.

On the other hand GCC has more or less experimental extensions for 128-bit integer and floating point emulation. I personally wasn't satisfied from their design and implementation. They have much limitations and are slow.

Cheers,
MD