Category: Code

Using Unordered Data Structures on C++ std::pair

Apr 5, 2019

Code

2 minutes
Quantum
qt.ax/udsp
In many situations, it seems fairly natural to use std::unordered_set and std::unordered_map on std::pair. Here’s an example of what you might be tempted to do:
```
#include <unordered_set>

int main(void) {
    std::unordered_set<std::pair<int, int>> test;
}
```
However, std::pair is not hashable by default, so a simple snippet like the above would not work.

There are many proposals online to define a pairhash class and explicitly specify it as the hash function as a template parameter to std::unordered_set and std::unordered_map.

This is not a bad idea. In fact, if you are writing a library, you should probably do this. But we can do better…
(Read more...)
Optimize MySQL/MariaDB Queries with STRAIGHT_JOIN

Nov 4, 2018

Code

3 minutes
Quantum
qt.ax/msj

Recently, I had to deal with an issue on DMOJ, where a page displaying 100 out of around a million elements took over 10 seconds to load. Naturally, I started investigating the issue.

(Note: DMOJ uses MariaDB, but the same problem, as well as the eventual solution, should work the same on MySQL as well.)

The first course of action, of course, was to see what the database was trying to do, by running an EXPLAIN query. For those of you who don’t know, if you have a query of the form SELECT x FROM y WHERE z, running EXPLAIN SELECT x FROM y WHERE z would show what the query is doing, without actually executing the query.

A quick look at the EXPLAIN output showed that MariaDB first did a filter on a 2000 row table, and then joined in the table with a million elements. Then, the 100 wanted rows were filtered out. This query plan was quite horrifying.

(Read more...)
Python 2 on Windows: Unicode Command Lines with subprocess

Jul 26, 2018

Code

8 minutes
Quantum
qt.ax/p2su

On Windows, using Python 2’s subprocess module to launch a process with a unicode command line that is not strictly from the currently active ANSI code page (i.e. encoding mbcs) will be mangled. All characters that cannot be encoded by mbcs will, in fact, be replaced with ?.

Obviously, this is can be resolved by switching to Python 3, but sometimes, converting to Python 3 is not yet an option. A terrifying prospect in 2018, but a problem nonetheless.

I present the module uniprocess, which defines its custom version of Popen and friends to work around the problem. I hope it proves useful to you.

(Read more...)
On the migration to Python 3

Nov 18, 2017

Code

4 minutes
Quantum
qt.ax/p3m

Recently, the DMOJ judge codebase has been migrated to Python 3, thanks to the combined efforts of me, Xyene, and kiritofeng. Many issues, such as unicode handling were exposed in the process.

Since Python 2 is still in heavy use, at least in the deployment of the DMOJ judge, compatibility with it must be maintained. This necessitated writing code in such a fashion as to be compatible with both Python 2 and Python 3. The six library has proved tremendously helpful in abstracting away the differences, some of which highly non-trivial.

For example, six.with_metaclass hides away the difference in metaclass use. In Python 2, the __metaclass__ class member defines the metaclass used for the class, while in Python 3, one would specify it as class Class(metaclass=MetaClass). The latter would be a syntax error in Python 2, and the former has no effect in Python 3. six provides a solution that is highly non-obvious and yet works perfectly.

The most frustrating part is unicode-handling. The DMOJ judge was written somewhat sloppily in regards to unicode handling, dealing mostly with bytestrings and raw bytes. With the separation of bytes and str in Python 3, strings in the judge must be turned into either bytes or str on a case-by-case basis. It is decided that source code and program output will be treated as raw bytes, and textual data that are derived from these will be handled as UTF-8.

(Read more...)
ARM Assembly: ∞ Ways to Return

Oct 19, 2017

Code

4 minutes
Quantum
qt.ax/aar

ARM is unusual among the processors by having the program counter available as a “general purpose” register. Most other processors have the program counter hidden, and its value will only be disclosed as the return address when calling a function. If you want to modify it, a jumping instruction is used.

For example, on the x86, the program counter is called the instruction pointer, and is stored in eip, which is not an accessible register. After a function call, eip is pushed onto the stack, at which point it could be examined. Return is done through the ret instruction which pops the return address off the stack, and jumps there.

Another example: on the MIPS, the program counter is stored into register 31 after executing a JALR instruction, which is used for function calling. The value in there can be examined, and a return is a register jump JR to that register.

ARM’s unusual design allows many, many ways of returning from functions. But first, we must understand how function calls work on the ARM.

(Read more...)
private and final fields: Can you actually hide data in Java?

Oct 12, 2017

Code

4 minutes
Quantum
qt.ax/jpf

Sometimes, after many attempts, you realized that to complete your mission, you must access private fields, or perhaps change final fields.

There are many reasons imaginable: the accessors copy the entire object before returning, and that takes a very long time, the authors forgot to provide an accessor, the library function is highly inefficient and you need to do better, …

Are you out of luck? Fortunately, no.

(Read more...)
Online Judging Sandbox: From Linux to FreeBSD

Oct 7, 2017

Security, Code

7 minutes
Quantum
qt.ax/fbs

As most probably know, DMOJ uses a sandbox to protect itself from potentially malicious user submissions. An overview of the Linux sandbox has been published by my friend Tudor. However, it doesn’t go deep into the implementation details, many of which differ between Linux and FreeBSD.

At its core, the sandbox, cptbox, uses the ptrace(2) API to intercept system calls before and after they are executed, denying access and manipulating results. The core is written in C, hence the name cptbox.

Perhaps the most obvious difference between Linux and FreeBSD is that on Linux, ptrace(2) subfunctions are invoked as ptrace(PTRACE_*), while on FreeBSD, it is ptrace(PT_*). But this difference is rather superficial compared to the significant internal differences.

(Read more...)
Effective Assembly: Bitwise Shifts

Oct 4, 2017

Code

4 minutes
Quantum
qt.ax/abs

Most people, when first starting assembly, still carry over a lot of high level constructs in their assembly programs. A common pattern is to multiply and divide when a bit shift would suffice.

For example, a lot of people would write a program to write out the binary representation of an integer using the divide and modulo operations. This is rather inefficient compared to using shifts. For example, the divide by 2 can be replaced with a right shift by 1, and modulo 2 can be replaced by a bitwise AND with 1.

Aside: interestingly, taking any number modulo a power of two m is equivalent to doing a bitwise AND with m-1. The proof of this is left as an exercise for the reader.

This post will address the basics you need to know about shifts to get up to speed on writing good assembly.

(Read more...)
A new "Hello, World!" for C

Aug 27, 2017

Code

2 minutes
Quantum
qt.ax/chw

Most of us have a good idea how to write a simple “Hello, World!” program in C, but sometimes it feels a little too easy. Luckily, we can always make it more of a challenge!

Consider a hypothetical situation where many symbols are banned, such as ", ', \, #, {, and }, and we aren’t allowed the string Hello, World! as a subsequence in the code. How would we write a “Hello, World!” program then?

Is it impossible, because we can no longer use {} to write a block of code for a function? Is it impossible, because we can’t actually embed the string?

(Read more...)
Build an interactive C++ Jupyter notebook via Cling

Aug 20, 2017

Code

1 minute
Quantum
qt.ax/cling

Jupyter and IPython makes for a very nice notebook, but by default it comes only with Python support. Fortunately, Jupyter supports many kernels, allowing for many languages from R to Redis, Perl to C++ to be supported. Unfortunately though, getting these kernels to run is not exactly an easy business. This time, we will be dealing with cling, a Jupyter kernel for C++.

(Read more...)
Using the Visual C++ compiler on Linux

Aug 11, 2017

Code

6 minutes
Quantum
qt.ax/vcl

It is a fairly common practice to compile Windows application on Linux build servers. However, this is usually done through an approach called cross-compiling. The essence of this approach is using a compiler for Windows applications, but the compiler itself is a Linux application. Usually, the compiler used for this is MinGW (or MinGW-w64 these days), a GCC implementation for Windows.

This works great when porting traditional Unix applications to Windows, since it meshes nicely with the traditional build system on Unix-like systems. But it is rather poor for standalone single .exe applications, which are more common in the Windows world. MinGW has a few DLLs that are needed to run the applications it compiles, and that ruins the single executable experience.

The traditional way to build these simple applications in the Windows world is with the Microsoft compilers, usually in the form of Visual C++. These compilers are fairly nice, but they have one problem: they do not exist as cross compilers. (Well, they can cross compile between different processors, but the compilers themselves will only run on Windows.) What do we do then? Do we resign ourselves into not having single executable applications, or do give up and buy a Windows build machine?

(Read more...)
A polyglot header for Python and cmd.exe

Aug 4, 2017

Code

1 minute
Quantum
qt.ax/pph
After seeing Raymond’s post on polyglot launchers for Perl and JScript with batch files, I decided to present one for Python:
```
@python -x "%~f0" %* & goto :eof
# Your Python code here.
```
This one simply use the special python flag -x to ignore the first line, which is somewhat analogous to the -x Perl flag, but much simpler.

I also have an alternative Perl polyglot header that does not require the special flag -x.
```
@rem = '--*-Perl-*--
@perl "%~f0" %*
@goto :eof
';
undef @rem;
# Your Perl code here.
```
(Read more...)