Krótkie programiki

Ostatnio uaktualniane: 29.10.2011

Strona główna

Treść

Liczby zmiennoprzecinkowe (floating-point)
Algorytmy
Niskopoziomowe
Różności
Grafika
Ocaml
Python [15.06.2007]
Python: Tkinter
PyGTK
TeX/LaTeX
Asembler

Liczby zmiennoprzecinkowe (floating-point)

floor.c: funkcja floor oparta na działaniach całkowitoliczbowych
round.c: funkcja round oparta na działaniach całkowitoliczbowych
range01.c: szybkie stwierdzenie, czy liczba zmiennoprzecinkowa mieści się w przedziale [0, 1]
float2int.c [15.06.2008]: Another appraoch of converting floating point number to integer.
round2.c [15.06.2008]: Different methods of rounding floating point numbers
approx.c [7.04.2004]: Aproksymacja pierwiastka liczby zmiennoprzecinkowej. Działa podobnie do rozkazów SSE (brana jest jakaś liczba starszych bitów, która indeksuje tablice z prekalkulowanymi wartościami).

Algorytmy

parallel_mandelbrot.c [29.10.2011]: Multithread generator of Mandelbrot set images. On system with 2 CPUs speedup is around 1.95 — 1.99.
atoi.c: implementacja funkcji atoi
big_fact.c: silnia z dużych liczb w C
big_fact2.c: silnia z dużych liczb w C (podejście drugie)
gcd.c: największy wspólny dzielnik
lcm.c: największa wspólna wielokrotność
powint.cpp: efektywne potęgowanie

Algorytmy kompresji LZxx

LZ77.py — implementacja algorytmu LZ77 (wolne)

LZSS.py — implementacja algorytmu LZSS (wolne)

LZ77-2.py, LZSS-2.py — modyfikacja powyższych: wyszukiwanie podciągów tylko w obrębie słownika

LZ78.py — implementacja algorytmu LZ78 (szybkie)

LZW.py — implementacja algorytmu LZW (szybkie)

poly_root.py [23.03.2007]: pierwiastki wielomianów 1., 2., 3. stopnia

Niskopoziomowe

count_cpu.c [25.06.2008]: Program returns number of available CPUs or enumerate them.
env.cpp: Dodawanie nowej globalnej zmiennej środowiskowej w DOS-ie (kompilator DJGPP).
sn-bios.c: Program próbuje wyciągnąć numer seryjny BIOS; przesłane na listę asm@hydepark.pl.
termsize.c: Sposób odczytu rozmiaru terminala w Linuxie.
console.tgz: niektóre funkcje z conio.h zrealizowane z użyciem kodów sterujących terminala (man console_codes)
cache_test.c [17.07.2010]: Measure cost of cache misses. First program does sequence scan of large table (fast), then indexes are randomized and table is scanned again (slooow).

Różności

x86linux_smc.c [13.07.2008]

Self modyfing code under x86 Linux. Tested with kernels 2.4 & 2.6.

[pl] Zobacz opis

vargs.c

sposób użycia funkcji o zmiennej liczbie parametrów (ku pamięci)

myassert.c

bardziej rozbudowana funkcja assert korzystająca z dobrodziejstw preprocesora. Np.:

f = fopen(filename, 'w');
Assert(f != NULL, ("File %s not found", filename))

checktex.c [12.07.2004], checktex.py [14.09.2004]

[en]: Simple utility to check placing of curly brackets '{' '}' in a TeX file. The program reports exact places (line, column) where not closed groups are started — TeX says only: "end occured inside a group at [some] level". The program finds also extra closing brackets (TeX says only the line where error occured).

[pl]: Program sprawdza rozmieszczenie nawiasów klamrowych w źródle TeX-a. Podaje dokładne koordynaty (wiersz, kolumna) nadmiarowej klamry zamykającej lub pozycję klamry otwierającej niezamkniętej grupy. Dla pierwszego przypadku TeX podaje tylko wiersz, zaś dla drugiego zaledwie poziom zagnieżdżenia. W przypadku dużych i skomplikowanych dokumentów to może być za mało i wówczas ten mały programik będzie pomocny.

Użycie:

checktex file1.tex file2.tex ...

wordlist2userdic.c [5.08.2004], wordlist2userdic.awk (nie obsługuje „polskich liter”)

[en] Program converts a list of words saved in a text-file into format recognized by OO (tested in OO 1.0 and 1.1.1). It also converts a polish diacritical characters — simply define PL on compilation.

[pl] Program konwertuje listę słów (każde słowo w jednym wierszu) na słownik użytkownika dla programu OpenOffice; testowane na OO 1.0, 1.1. Słownik należy skopiować do katalogu {OO}/user/wordbook i ponownie uruchomić OO.

Użycie:

$ wordlist2userdic lista_słów openoffice.dic
$ wordlist2userdic.awk < lista_słów > openoffice.dic

Kompilacja:

$ gcc wordlist2userdic.c -o wordlist2userdic
$ gcc -DPL wordlist2userdic.c -o wordlist2userdic # polskie litery

sleep.c

program sleep napisany z użyciem funkcji alarm

tail.c

program tail

tee.c [17.07.2010]

tee implementation

conv.c [25.02.2009]

[en] Simple iso-8850-2 to UTF-8 convert. Program is faster around 30-40% then naive approach i.e. char by char — it tries to process 4 chars at the same time. Program is also faster then GNU iconv, speedup depends on file input. On my machnine I've measured speedup from 70% to 270%.

removeemptydirs.py [2.03.2009]

[en] Simple utility to remove empty dirs

Grafika

isconvex.py [1.03.2007]

stwierdzenie czy wielokąt jest wypukły

triangulation.py

triangulacja dowolnego wielokąta

graham.py, graham-tkdemo.py

Algorytm Grahama wyszukiwania otoczki wypukłej + demo

aabb2D.py

biblioteczka: działania na dwuwymiarowych pudełkach otaczających typu AABB

cbezier2D.py

biblioteczka: kubiczne krzywe Beziera:

punkt na krzywej

podział krzywej algorytmem de Casteljau

dokładne pudełko otaczające

przejście na bazę potęgową

adaptywny podział (+ 3 funkcje określające „płaskość” krzywej)

punkty przecięcia z prostą

punkty przecięcia z drugą krzywą

odległość punktu od krzywej (przybliżona)

długość krzywej (przybliżona)

utils2D.py [23.03.2007]

różne działania na wektorach 2D (parach (x, y))

cbezier-as-tkdemo.py

demo: adaptywny podział krzywych Beziera — rysowanie krzywej

cbezier-cc-tkdemo.py

demo: wyznaczanie przecięć dwóch krzywych Beziera 3. stopnia

Cohen_Sutherland.py

demo: Algorytm Cohena-Sutherlanda

demo on-line: SVG + JavaScript

Algorytm Sutherlanda-Hodgmana

demo (PIL): Sutherland-Hodgman.py

demo (Tkinter): polyintersect-tkdemo.py [5.12.2006]

algorytm: polyintersect.py [5.12.2006]

Wielomianowe krzywe Beziera: SVG + Javascipt
refine_polyline.py: Upraszczanie łamanych aproksymujących wykresy funkcji, patrz artykuł

Pudełko otaczające obróconego łuku eliptycznego

opis

implementacja w Pythonie: elarc_aabb.py

demo SVG+JavaScript: elarc_aabb-demo.svg

3d.svg: 3D model of truncated octahedron — Javascript + SVG

Ocaml

myhash.ml: dodatkowe funckje działające na tablicach asocjacyjnych
mylist2.ml: dodatkowe funkcje działające na listach (wzorowane na Heskellu)
mylist.ml: dodatkowe funkcje działające na listach (wzorowane na SML-u)
mystring.ml: dodatkowe funkcje działające na łańcuchach znaków (wzorowane na metodach znanych z Pythona)

Python [15.06.2007]

filter2.py

Funkcja zwraca krotki pasujące do pewnego wzorca, np. takie które na pierwszym miejscu mają liczbę 100, a wartości pozostałych elementów są nieistotne.

unzip.py

odwrotnego działanie do wbudowanej funkcji zip

group_elements.py [14.03.2007]

Funkcja grupuje kolejne elementy list, dla których funkcja value zwróci tę samą wartość.

>>> L = [1, 1, 1, 1, 2, 3, 3, 4, 4, 4, 4]
>>> group_elements(L)
[(1, [1, 1, 1, 1]), (2, [2]), (3, [3, 3]), (4, [4, 4, 4, 4])]
>>>
>>> L = ["aaa", "aab", "bba", "bab", "bca"]
>>> group_elements(L, lambda x: x[0])
[('a', ['aaa', 'aab']), ('b', ['bba', 'bab', 'bca'])]
>>>

Zwraca listę par (wspólny element, lista elementów).

Funkcję fields (z bodajże SML-a), która działa podobnie do split, ale zostawia na liście pola białych znaków można bardzo zgrabnie wyrazić za pomocą group_elements:

def fields(string, pred=lambda x: x.isspace()):
        tmp = group_elements(string, pred)
        return [(p, ”.join(cl)) for p, cl in tmp]

walk_dir.py

W pliku znajdują się dwie funkcje: find_file oraz find_all_files.

Funkcja find_file zwraca pierwszy plik, dla którego predykat pred jest prawdziwy, natomiast find_all_files zwraca listę wszystkich plików spełniających predykat. Funkcja pred przyjmuje dwa argumenty: nazwę bieżącego katalogu oraz nazwę pliku.

Funkcje wyszukują pliki w katalogu, bądź na liście katalogów.

Obie funkcje przechodzą katalogi wszerz; o tym czy katalog zostanie odwiedzony decyduje funkcja enterdir (domyślnie każdy katalog jest odwiedzany). Funkcja enterdir przyjmuje dwa argumenty: nazwę bieżącego katalogu oraz poziom w drzewie katalogów (liczony od zera).

Wyszukanie pliku nie uwzględniając rozmiaru liter:

filename = 'Text.TXT'

def pred(p, f):
        return f.lower() == filename.lower()

f = find_file(['.', '/home/'], pred)

Wyszukanie plików .py we wszystkich katalogach oprócz CVS, .svn i tmp:

def pred(p, f):
        return f.endswith('.py')

def enterdir(p, l):
        return not p.endswith('/CVS')  and \
               not p.endswith('/.svn') and \
               not p.endswith('/tmp')

fl = find_all_files('.',  pred, enterdir)

partition.py

podobne do split, ale zostawia ciągi separujące

msplit.py [1.03.2007]

split na znakach z podanego zbioru (lub dopełnienia zbioru)

trie.py [23.03.2007]

drzewa trie w Pythonie (powstało przy okazji udoskonalania rozszerzeń do reST)

fractions.py

Ułamki zwykłe, bardzo podstawowe działania.

reduce-samples.py [14.03.2007]

Przykłady zastosowań wbudowanej funkcji reduce.

replace.py [15.06.2007]

Funkcja replace z callbackami — zainspirowałem się rozwiązaniem z JavaScript. Zastępowane są albo zwykłe łańcuchy znaków albo wyrażenia regularne.

pred_split.py [15.06.2007]

Podobne do wybudowanej metody split, ale o miejscu podziału decyduje wartość predykatu (funkcji).

Python: Tkinter

tkcolorpicker.py: prosta kontrolka do wyboru 16 kolorów
tk_ebbox.py, tk_ebbox-demo.py: dokładne pudełko otaczające wygładzonych łamanych/wielokątów
tkinter-arrows.py: demo canvas: kształty strzałek
tkinter-attribs.py: demo canvas: atrybuty obiektów zależne od ich stanu, kolejność obiektów
tkinter-eventstate.py: demo canvas: znaczenia bitów w polu event.state
tkinter-pindex.py: demo canvas: najbliższy wierzchołek łamanej
tkinter-scan.py: demo canvas: scanmark, scandragtoo, see
tkinter-tagorid.py: demo canvas: wyrażenia logiczne jako tagOrId
tkinter-vertedit.py: demo canvas: modyfikacja wierzchołków (dodawanie/usuwanie) istniejących łamanych/wielokątów

PyGTK

pythonlistmodel.py [17.07.2010]: TreeModel that encapsulates any python sequence of other seqences of same size
show_rgb.py [17.07.2010]: PyGTK application with own CellRenderers: 1. drawing an arbitrary shape and rendering a text, 2. drawing text rendered from given gobject properties.
gdk-line_attributes.py [17.07.2010]: PyGTK line attributes demo: join, bevel and capjoin styles, and also dashes

TeX/LaTeX

deferredfootnotes.sty [17.02.2011]

This packages defines two commands:

deferredfootnote[number]{text}
deferredfootnotemark[number]

First commands defines footnote text and assigns one to the given number. Second command makes footnote with n-th text note.

This allows to place text of footnotes anywhere in manuscript, for example all at the end of source file.

imageaspage.tex, imageaspage-test.tex

wstawianie całego obrazka na stronę PDF-a + przykład użycia

Asembler

sse4-insertionsort.c [31.08.2008]

PHMINPOSUWB help sorting 8-elements vectors.

sse4-mandelbrot.c [29.06.2008]

Mandelbrot fractal generator — SSE2 & SSE4.1 implementation.

SSE procedure calculates 4 pixels in parallel. SSE4.1 procedure uses PTEST instruction to break loop when lengths of all 4 complex numbers are greater then some threshold. SSE2 version uses PMOVMSKB and x86 TEST.

Average speedup over FPU procedure is around 4.5 times. Measured on Core2 Duo E8200 @ 2.66GHz.

sse-matvecmult.c [28.06.2008]

Multiplication of matrix 4x4 by vector 4x1 — FPU, SSE3 and SSE4 procedures. Program needs sse-aux.c to compile.

mix_32bpp.c [21.06.2008]

Crossfading of 32bpp images — see article for details.

Program contains reference C implementation and two SSE procedures: one using old SSE instructions, and another using new SSE4.1 instruction PMADDUBSW.

sse-uint32-float.c [18.06.2008]

SSE: unsigned 32-bit int to float conversion. Program needs sse-aux.c to compile.

blend_32bpp.c [8.06.2008]

Alpha blending of 32bpp images — see article

Program contains four procedures:

x86 — C implementation (blend_image_inplace, 1 pixel/iteration)
SSSE3 — SIMD reference implementation (ssse3_blend_image_inplace, 4 pixels/iteration)
SSE4 — instruction pmovzx used instead of punpckxbw (sse4_blend_image_inplace, 4 pixels/iteration)
SSE4-2 — unrolled SSE4 variant (sse4_blend_image_inplace_unrolled, 8 pixels/iteration)

lookup_32bpp.c [1.06.2008]

Lookup-based 32bpp pixels transformations — see article

This simple program includes following procedures:

naive — strightforward C implementation
x86 — hand-coded assembler version of naive
SSE2 — SSE2 instructions used
SSE4 — SSE4.1 instructions used

pixconv16bpp-32bpp.c [1.06.2008]

16bpp to 32bpp pixel conversion — see article

This simple program includes following procedures

naive — straightforward conversion that use and, or and shifts 1 pixel/iteration
lookup16 — single, large lookup table, 1 pixel/iteration
lookup8 — two, small lookup tables, 1 pixel/iteration
lookup8(2) — optimized lookup8, 2 pixels/iteration
MMX — naive using MMX instructions, 4 pixels/iteration
SSE2 — naive using SSE2 instructions, 8 pixels/iteration
SSE2(2) — unrolled SSE2, 16 pixels/iteration

sse4_strstr.c [27.05.2008]

Acceleration of strstr using SSE4 instruction MPSADBW — read detailed description.

This program includes one wrapper sse4_strstr around following functions:

sse4_strstr_any — exact comparison is done with built-in function strncmp.c
sse4_strstr_len3, see4_strstr_len4 — optimized for substring of length 3 and 4 chars, no additional comparison is needed
sse4_strstr_max20, sse4_strstr_max36 — optimized for substring of length 4..20 and 20..36, exact comparision is done with few assebler instructions

ssse3_popcount.c [22.10.2011]

Population count of bits strings — see article

This program includes five functions:

lookup — lookup based
ssse3-1 — SSSE3 using PSHUFB and PSADB
ssse3-2 — improved SSSE3 procedure
sse2-1 — SSE2 using bit-parallel algorithm
sse2-2 — improved SSE2 procedure (the same optimization as in ssse3-2)

hexprint.c [23.05.2008]

Bin to hex conversion — for details see article

Four different approaches to dump hex:

lookup[16] (nibble-addressing)
lookup[256] (byte-addressing)
2 x lookup[256]
using SSE3 instruction PSHUFB

Przykłady zastosowań instrukcji SSE [13-15.09.2007]

sse-dotprod.c — iloczyn skalarny
sse-dotprod4.c — iloczyn skalarny 4 par wektorów równolegle
sse-crossprod.c — iloczyn wektorowy
sse-transpose.c — transpozycja macierzy 4x4
sse-matvec-mult.c — mnożenie macierzy 4x4 przez wektor 4x1
sse-vecmat-mult.c — mnożenie wektora 1x4 przez macierz 4x4
sse-matmult.c — mnożenie macierzy 4x4
sse-aux.c [18.06.2008] — funkcje pomocnicze

sse3-dotprod.S [14.09.2007]

Obliczenie 4 iloczynów skalarnych z użyciem rozkazu haddps (SSE3). Patrz artykuł.

sse4-matvec-mult.S [13.09.2007]

Mnożenie macierzy 4x4 przez wektor 4x1 z użyciem rozkazu DPPS Patrz artykuł.

sse4-string-instr.S [xx.09.2007]

Przykład zastosowań rozkazów łańcuchowych z SSE4. Patrz artykuł.

mmx_string.c [24.06.2007]

Funkcje ze string.h: strcmp, strlen i strchr wykorzystujące rozkazy MMX. Więcej w osobnym artykule.

saturated_add.c [4.07.2007]

Demonstracja dwóch metod dodawania z nasyceniem pikseli 16bpp (metody 1: x86 i 3: MMX).

Program możne działać albo wsadowo i wówczas wykonuje wybraną procedurę n razy (profilowanie, pomiar wydajności) albo interaktywnie — ładuje wskazany obrazek PPM, wyświetla w oknie (X Window) i wykonuje dodawanie z nasyceniem. Do kompilacji dla X Window wymaga dodatkowo biblioteczek load_ppm oraz Xscr.

Kompilacja:

gcc -O2 saturated_add.c -o cokolwiek

lub:

gcc -O2 Xscr.o load_ppm.o -DUSE_Xscr saturared_add.c -o cokolwiek

Następnie:

$ ./cokolwiek help

blur.c [17.05.2008]

Demonstracja algorytmu rozmywania obrazów w skali szarości. Zawiera pięć funkcji:

w języku C,
w asemblerze,
w asemblerze z użyciem MMX,
zoptymalizowana MMX2,
w asemblerze z użyciem SSE2.

Program możne działać albo wsadowo i wówczas wykonuje wybraną procedurę n razy (profilowanie, pomiar wydajności) albo interaktywnie — ładuje wskazany obrazek PPM, wyświetla w oknie (X Window) i rozmywa. Do kompilacji dla X Window wymaga dodatkowo biblioteczek load_ppm oraz Xscr.

Kompilacja:

gcc -O2 -lX11 -DUSE_Xscr Xcr.o load_ppm.o blur.c -o blur

lub:

gcc -O2 blur.c -o blur

Użycie:

$ ./blur help

Dokument utworzony przez rozszerzony rst2html.