Programs

English Russian

Printing

My most significant contributions to free software are patches to Ghostscript. Ghostscript is a software suite built around a PostScript interpreter. It is a central part of the Common Unix Printing System (CUPS). Every GNU/Linux system that can print has Ghostscript installed. Ghostscript is also used for file format conversion. Although my patches are only a small part of the Ghostscript code base, and Ghostscript is just one of the thousands of programs that comprise GNU/Linux, out of all my programs, these are the ones that benefit the most people.

The patch for bug 690595 improves the efficiency of the spooling subsystem. When the document mixes black-and-white and color pages, all pages were sent to the spooler as uncompressed true color bitmaps. This patch recognizes images with few colors and reduces their color depth, if possible.

The patch for bug 689451 addresses a special case of arc rendering, when the arc is so big that it overflows the fixed point numbers used in the graphic library. The patch allows the arc to be replaced with a polyline of no more than 9 segments, thus preserving its visual appearance. This line can be further clipped by the graphic library. Although this case may seem artificial, it does occur in practice when an artist draws an arc through 3 points and the points are almost collinear.

The patch for bug 696302 makes a simple user interface improvement: The GL version of the muPDF viewer can now be controlled using the arrow keys.

The patch for bug 696520 fixes a case of bit rot. The old contributed drivers were not updated when the call pattern changed.

Ghostscript is a living program and its maintenance work continues.

Research

I've also been working on a few research projects.

Strongly Regular Graph Search

I've been searching for a strongly regular graph. I'd started with a simple edge-by-edge search, added client-server functionality to allow for distributed computing, and then delegated the job to dedicated pseudo-SAT solvers.

Search for Halftone

I'm searching for an improved set of kernels for error diffusion. To do this, one must be able to gauge the quality of a halftone. One way to do this is to check the power spectrum of a flat, dithered gray square. I wrote a program which uses a FFT library to take the power spectrum of a PPM image of this kind. However, some dithers may have obvious artifacts caused by starting with no error on every cell at the top row, especially for gray levels that are very sparse (either very dark or very light). Thus, to give such dithers a fair advantage, I first dither a rectangle, then use a program to cut off the top to make a square. A good dither's artifacts should thus be removed. I've actually written one unified program to do all this all at once.

Fun

Of course, one can't work all the time. Here are some programs made just for fun, and to relax.

Sudoku solver

My first program; back then, my teacher considered solving Sudoku puzzles as advanced math. Not being advanced at math yet, I outsourced this job to a computer. The program uses an efficient representation of a Sudoku puzzle and a simple backtracking algorithm.

PDP-11 Games

Before the era of widespread game consoles, people found ways to entertain themselves. The few who had computers made a few simple yet captivating text-based games. Now that retro gaming is becoming widespread, there is an excellent opportunity to bring these games back. Since almost nobody has a PDP-11 available nowadays, I have ported the best to Python and ncurses. They run on Linux and Mac OS, and under Windows with cygwin. They do not work on stock Windows because it does not have ncurses. The games are hosted on Savannah, but I have download links below as well.

Super Pacman

A pacman game. You dodge ghosts, eat dots, and eat ghosts if you have a power pellet. It has a scoreboard and ramping difficulty, and was the most popular of the games and the one I did first. The code is somewhat object oriented; the main loop polls all the objects in the game and has them do the appropriate actions. Download it here.

Xonix

A came about staking out bits of area while dodging ghosts. Claim enough area to move onto the next level. It uses a recursive flood fill algorithm to find what area you claimed. Thus, it requires a larger stack than Python allocates by default. Download it here.

Mars War

A simpler game. Fend off martians and protect your own troops. It presents an initial dialog to set the difficulty mode,adjusting the number of martians, their amount of movement and your launcher's defense capabilities. The code is quite object-oriented, with every sprite being an object. A good implementation would use a priority queue, but merely polling all the objects turned out to be sufficient. The original was probably written in a high-level language, because there are numerous variations. I've implemented an unified variant, taking the best parts of all I could find. Download it here.

Display Hacks

Making display hacks, programs to make pretty pictures, is fun; I've made a few. There's a classic display hack, munching squares, which fills the screen with an animated plot of X XOR Y using truecolor SGR codes, a more colorful version, which does the same thing but manipulates hue instead of brightness, thus filling the screen with shifting color, a re-implementation of lolcat (which applies a rainbow effect to standard input) that is aware of line wrapping and uses truecolor, and a general-purpose multi-mode feature-creeped pseudo-graphic image renderer, which uses an improved halftone based on my own set of kernels.

Historic Font

This font has been adapted from character paths designed by Igor Melichev's team for a Digigraph pen plotter circa 1987. The main goal of this program is preservation of computer history but you are free to use it for any purpose according to GNU GPL. Feel free to contact me if you intend to use this file and need any changes.

1966 Snoopy Calendar

Everybody knows that a real programmer doesn't use Pascal, can write a 5-page loop without being confused, and has a 1966 Snoopy Calendar on the wall. The works of real programmers are still with us to cherish and imitate. But where's the calendar? This CGI script recreates the famous calendar from the mainframe era, which is also valid for the given year. Print the calendar and keep it on the wall. It will be useful again and again in the coming years.

Year:

Python

A one-line Python program can solve any problem.