Sunday, October 7, 2012

Respawning...

Just moved "gatopeich's simple unix tools & hacks" to Blogger.
Many links are broken, if you cannot find something please ask for it.

A BASH prompt that displays running command on Xterm title


In order to have a quite explanatory bash prompt showing current directory and time, and an Xterm title that shows the currently running command or the current directory when idle, use this:


    PS1='\e]0;\W\007\n\[\e[0;35m\]\u@\h: \[\e[1;36m\]\w/\n\[\e[1;33m\]\t $ \[\e[0m\]'
    trap 'echo -ne "\e]0;$BASH_COMMAND\007"' DEBUG
    set +o functrace # Do not inherit traps, to prevent messing with completion 


Compcache: Easy installation


(Very old information, unlikely to be useful anymore, kept here for the sake of history)


Being a happy user of compcache (on a Xubuntu system), I have prepared a very simple patch to have it easily installed on my system, and reinstalled whenever kernel changes or I just want to try a new version. The patch adds an "install" target to compcache's main Makefile, in order to install an LSB-compliant init script, so compcache is loaded and unloaded at the proper system levels.


This is, roughly, the make code:

PWD := $(shell pwd)
KD := /lib/modules/$(shell uname -r)/build
install:
        make -C $(KD) M=$(PWD) INSTALL_MOD_STRIP=1 modules_install
        depmod
        install init-compcache /etc/init.d/compcache
        update-rc.d compcache defaults

 
Here is the init script: init-compcache.

And here is the full patch that you can apply with "patch < compcache_installation.diff " on a fresh compcache-0.5.1 source tree: compcache_installation.diff. After that, build it with "make" and install it with "sudo make install".

USB D2XX driver for Wine (on Linux)


I have a very nice logic analyzer that didn't come with any software for Linux. However, it uses some FTDI chip through its standard driver library 'ftd2xx.dll', which happens to have a Linux version whose API is pretty much the same, called "libftd2xx.so".


So I took the effort to wrap-up a Wine DLL 'ftd2xx.dll.so' which offers the native Linux driver to any Windows application running under Wine. It was a tedious task, but quite straightforward thanks to 'winedump'.

If you want to use your favourite FTDI-based USB devices under Wine too, just install ftd2xx.dll.so on your Wine lib installation, usually /usr/lib/wine/. Source code and detailed instructions are available here. Just don't forget to install FTDI's D2XX drivers for Linux from their site.

My particular device (Ant18e) demonstered some funny behaviour under Linux, somehow it didn't report a correct USB serial number. The strange thing was that it worked flawlessly under windows... I had to reprogram its EEPROM to get a good serial number with MPROG, a standard utility provided by FTDI, and a 'EEPROM template' provided by my device's vendor.

I also built a 'libd2xx_table.so' (ftdi_table-0403.c) that you may want to install right beside your libftd2xx.so (typically at /usr/local/lib/) in order to get all your FTDI-based devices (VendorID=0403) recognised by the driver. Otherwise only a few ProductIDs will be working. More details on D2XX Linux driver package, under "lib_table".

Use this stuff at your own risk! I already risked my brand new logic analyzer in this development :-).

Update for 64-bit systems: I have not been able to compile this on a 64-bit architecture, however the 32 bit binaries work fine when placing ftd2xx.dll.so at /usr/lib32/wine, and libd2xx_table.so (together with 32-bit D2XX drivers) at /usr/lib32/.

OpenGL wrapper or how to run some 3D games on really old 3D chipsets


A library wrapper that downsamples textures as they are dealt to OpenGL system, enabling my old 3D card to bear with some modern Linux games that are unusable otherwise.


Some history: After years of patient waiting, my Savage 3D chipset (an MX/IX that comes with most Thinkpads T2x) is supported in Linux (X11/Xorg/etc.) with direct rendering! (DRI). Just in time, as everything seems to come in 3-D now. Only my card has grown a little bit old (by consumerist standards) -- most software (read "games" here!) come with 'big' textures that just won't fit, while few will even check for errors. So I spent some time studying OpenGL (horrible learning curve!) and found that a simple workaround around "glTexImage2D" could solve the issue. Then coded a wrapper library for that call with 'the ole handy LD_PRELOAD trick'.
  • What does it do?
Checks if a texture passed to OpenGL core is greater than "max_texture_size". If so, downsamples it.

  • How it works?
you just preload it setting LD_PRELOAD=glWrap.so before running your favourite 3D games.

  • Where can you get it?
Here: glWrap.c. Build & run instructions are embedded in the first lines of comments. You may want to comment out the printouts, change "max_texture_size" parameter or whatever. It is just 88 lines of straight-forward code, don't be scared!

  • What if I am too lazy to build it?
Let's see what I can do for you... Have glWrap.so, and run your games with the following command line:
$ LD_PRELOAD=/path_to_wrapper/glWrap.so OpenGL application here
Enjoy!


Graphic Algorithms

This page is about algorithms to rasterize (represent with pixels) graphic objects (lines, circles, textures) using simple integer math.

Some history...

These algorithms I developed in my young coding times (1992~1995) for usage in assembler code routines that conformed a i386-architecture 320x200 resolution graphic library I would use for games & demos.

At that time, Bressenham's line algorithms appealed to me as too 'slow', as it used some non-integer operations. I felt I could do a little bit 'better', specially faster by not using anything else but integers and the simplest integer operations. I must say I had very imperfect knowledge of Bressenham's work.

The original intention in using just integer operations was to speed up the code. Later I discovered that integers can deliver optimal accuracy and nicest results, apart from the best speed in typical PC architectures.

Years later (and ago :-)) I included a few of these algorithms in "4bpp" library (http://fourbpp.sourceforge.net/), aimed at 4 bits-per-pixel (2 pixel pet byte) framebuffers. and several unpublished pieces of work.

Simple Math

The key ideas are:
  • X-Y plane is represented by a 2-dimensional array. Coordinates are integers, corresponding to array indexes. Array elements represent unitary squares in the X-Y plane (or pixels in a screen).
  • Think as the Greek! -- That is, a/b "a divided by b" is "the number of times you can substract b from a". Then don't discard the remainder, it might be useful next time around ;-). Also do as the ancient Greek, work graphically with a compass and you will learn a lot about numbers in the 2-dimensional plane...
  • We are (kind of!) plotting a function x = F(y) in X-Y plane, whose derivative tells how much to move in Y-direction for each unitary step in X-direction.

Line Drawing by Integer Operations

Line drawing is the basic problem in rasterized graphics. It consists of connecting two pixels with those that approximate best the linear segment between them. After much work to obtain nice and symmetric results, I came to the following rationalization of the problem:
  1. The pixels will be chosen from those crossed by an ideal line connecting the centers of the two extremes.
  2. Starting from one extreme, each pixel will be vertically, horizontally, or diagonally adjacent to its predecessor.
  3. Each subsequent pixel will be nearer to the other end. This leaves no more than 3 candidates.
  4. When several candidates are possible, select the one whose center is closer to the ideal line. In the rare case when 2 pixels are equidistant, pick any.

Let's have an example to brighten things up:

11x5 lineThis is a line connecting (0,0) and (10,4), or a "11x5" line. It is worth mentioning that most algorithms out there won't produce this result, as they usually don't follow the centered line, or just don't care about symmetry etc.




Some examples to get it right, for a line 10 pixels wide by 3 pixels high:
The "good":
o o o · · · · · · ·
· · · o o o o · · ·
· · · · · · · o o o
The "bad" ('x' points don't comply condition about distance to ideal line):
o · · · · · · · · ·
· x · · · · · · · ·
· · x x x x o o o o
And the "ugly" (may comply conditions but following a non-centered line, a very commnly found implementation):
o o o o · · · · · ·
· · · · o o o · · ·
· · · · · · · o o o

The algorithm

This algorithm provides a solution for the line between points P1 and P2 with coordinates (x1,y1) and (x2,y2). For the sake of simplicity we'll assume the case where dx = x2 - x1 > 0, dy = y2 - y1 > 0, and dx > dy.

The main idea is to "divide by repeated substraction", that is: For each x-step substract dy from an accumulator (a := a - dy) initialized as (a := dx). Then whenever the accumulator comes to 0 or below "we walked enough in x-direction to have one step in y-direction". At that point, we take that y-step, and 'reload' the accumulator (a := a + dx)...
START of gatopeich's Integer Line Algorithm
1: dx = ( x2 - x1 ) + 1
2: dy = ( y2 - y1 ) + 1
3: x = x1
4: y = y1
5: a = dx - (dy/2)
6: select/draw pixel at (x, y)
7: x = x + 1
8: a = a - dy
9: if ( a > 0 ) go to step #6
10: y = y + 1
11: a = a + dx
12: if ( y <= y2 ) go to step #6
END

Result for the 10x3 case is the "good" one, as shown above.

Notes:
  • All operations are on integers, results are truncated down.
  • At step 5, the substraction of (dy/2) is intended for simmetry. It is like "centering" the accumulator, by substracting 1/2 steps from it, as we don't really start from zero but from the center of the first pixel. Removing it would result in the "ugly" result. Being dy/2 an integer operation it will round down the result. To compensate this I opt for "strict major" comparison at step #9 "( a > 0 )", where "(a >= 0)" renders roughly the same results. I have yet to do more testing to determine if this matters at all.

Similarity with Bresenham's

Though this algorithm was developed 'from scratch', I recently online a very similar one as an optimized version of Bresenham's algorithm (http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Optimisation). This is because of the idea of optimizing Bresenham's by scalating the real numbers and operations in order to work with integers, which on a mathematical plane translates to roughly the same as my 'original' idea.
Thus said, I can hardly claim that my algorithm is 'new' or 'original'. I seem to have "reinvented the wheel" :-).

Performance

This is NOT the fastest line algorithm I have tested, but I still think it is the most elegant.
When implemented in C (gILA.c) and using Po-Han Lin's benchmark code (http://www.edepot.com/algorithm.html), my "integer line algorithm" performs slower than Po-Han's "EFLA Variation E", and roughly faster than the others in his benchmark code: Wu's, Bressenham's or "DDA".

Circle Drawing by Integer Operations

Well, I was all about to explain my 'original' idea about iteratively obtaining square numbers, and the circle algorithm I developed from it in my youth days... Then I found it perfectly explained as a circle variant of Bresenham's line algorithm: http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#Circle_Variant
This makes me see (again) how terribly useful it would have been to have Wikipedia some ten years ago, and the always-recurrent question: Can one come up with anything new anymore?

'gatotray', monitor CPU graphically from your system's tray


Notice to gatotray users!!!

The official gatotray home page is now at http://code.google.com/p/gatotray 
There you will be able to browse the code, download the latest version and request improvements.

gatotray screenshot'gatotray' is a colorful tray icon to watch over CPU status including usage, frequency and temperature.



  • Pseudo-logaritmic time scale: right-most columns reflect last seconds while lefter columns accumulate older measures, providing an idea of cpu usage evolution for up to 30 minutes in a glimpse. It makes a beautiful smoothing effect too.
  • Colors of the usage bars vary with frequency, from green to red.
  • Tooltip shows current usage percentage, frequency and temperature numerically.
  • Instant temperature is shown graphically, in the form of a nice thermometer :-). Thermometer blinks on high temperature (>=85 C).
  • Pops-up a 'top' window with detailed system usage (on click).
  • Preferences dialog allows customization of colors and options.
  • Transparent background (optional).
Screenshot:

Requeriments:
    • Linux.
    • GTK+ v2.10 or later.
    • Any freedesktop.org compliant system tray like that of XFCE, KDE, GNOME, etc.

Download:

Build & install instructions:
$ make
$ sudo make install
     (This will install in /usr/local/bin).

Python prototyping: During an early design stage, gatotray was coded in Python. This allowed me to code & debug interactively, specially useful while coding GTK+ events. Then converting from Python to C was pretty straightforward and the resulting application is very lightweight in resources and dependencies.

'unsort', the missing UNIX filter


The UNIX filter that should have been there since the beginning!

Unsort is the natural opposite to standard 'sort', it takes lines and shuffles them. I wonder how it is not part of every standard UNIX system. How the hell did they test 'sort'?
Sample run:
$ echo -e "1\n2\n3\n4\n5\n6" | unsort
stderr: Using seed: 542941369
6
4
1
5
2
3
stderr: Jumps: 4 left, 4 right, balance: 1.000000
This 'unsort' implementation works as follows:
  1. reads lines from standard input
  2. assigns them random, unique indexes
  3. sorts lines by their random index
  4. when input finishes, lines are dumped as sorted.
The only limitation is on file size, since the whole file is kept in memory during the process.

Download 'unsort' here: unsort-1.0.1.c. Simple build & install instructions are within the file, along with shell script for testing the statistical distribution, like this one:

Statistical test #2 "Permutations of 3 elements":
$ i=9999;while [ $((i--)) -ge 0 ];do echo -e "a\nb\nc"|unsort -q|xargs echo;done|sort|uniq -c
1644 a b c
1681 a c b
1680 b a c
1633 b c a
1709 c a b
1653 c b a