Another square root clipping

This time from Paul Hsieh

---

Begin quoted text

---

A common application in computer graphics, is to work out the distance between two points as √(Δx²+Δy²). However, for performance reasons, the square root operation is a killer, and often, very crude approximations are acceptable. So we examine the metrics (1 / √2)*(|x|+|y|), and max(|x|,|y|):

Notice the octagonal intersection of the area covered by these metrics, that very tightly fits around the ordinary distance metric. The metric that corresponds to this, therefore is simply:

        octagon(x,y) = min ((1 / √2)*(|x|+|y|), max (|x|, |y|))

With a little more work we can bound the distance metric between the following pair of octagonal metrics:

        octagon(x,y) / (4-2*√2) ≤ √(x²+y²) ≤ octagon(x,y)

Where 1/(4-2*√2) ≈ 0.8536, which is not that far from 1. So we can get a crude approximation of the distance metric without a square root with the formula:

        distanceapprox (x, y) = (1 + 1/(4-2*√2))/2 * min((1 / √2)*(|x|+|y|), max (|x|, |y|))

which will deviate from the true answer by at most about 8%. A similar derivation for 3 dimensions leads to:

        distanceapprox (x, y, z) = (1 + 1/⁴√3)/2 * min((1 / √3)*(|x|+|y|+|z|), max (|x|, |y|, |z|))

with a maximum error of about 16%.

However, something that should be pointed out, is that often the distance is only required for comparison purposes. For example, in the classical mandelbrot set (z←z²+c) calculation, the magnitude of a complex number is typically compared to a boundary radius length of 2. In these cases, one can simply drop the square root, by essentially squaring both sides of the comparison (since distances are always non-negative). That is to say:

        √(Δx²+Δy²) < d is equivalent to Δx²+Δy² < d², if d ≥ 0

---

End quoted text

---

Reference: http://www.azillionmonkeys.com/qed/sqroot.html

CORDIC overview

Description

http://opencores.org/project,cordic

As the name suggests the CORDIC algorithm was developed for rotating coordinates, a piece of hardware for doing real-time navigational computations in the 1950's. The CORDIC uses a sequence like successive approximation to reach its results. The nice part is it does this by adding/subtracting and shifting only. Suppose we want to rotate a point(X,Y) by an angle(Z). The coordinates for the new point(X_new, Y_new) are:

X_new = X * cos(Z) - Y * sin(Z)
Y_new = Y * cos(Z) + X * sin(Z)

Or rewritten:

X_new / cos(Z) = X - Y * tan(Z)
Y_new / cos(Z) = Y + X * tan(Z)

It is possible to break the angle into small pieces, such that the tangents of these pieces are always a power of 2. This results in the following equations:

X(n+1) = P(n) * ( X(n) - Y(n) / 2^n) Y(n+1) = P(n) * ( Y(n) + X(n) / 2^n) Z(n) = atan(1/2^n)

The atan(1/2^n) has to be pre-computed, because the algorithm uses it to approximate the angle. The P(n) factor can be eliminated from the equations by pre-computing its final result. If we multiply all P(n)'s together we get the aggregate constant.

P = cos(atan(1/2^0)) * cos(atan(1/2^1)) * cos(atan(1/2^2))....cos(atan(1/2^n))

This is a constant which reaches 0.607... Depending on the number of iterations and the number of bits used. The final equations look like this:

Xnew = 0.607... * sum( X(n) - Y(n) / 2^n) Ynew = 0.607... * sum( Y(n) + X(n) / 2^n)

Now it is clear how we can simply implement this algorithm, it only uses shifts and adds/subs. Or in a program-like style:

for i=0 to n-1
  if (Z(n) >= 0) then
    X(n + 1) := X(n) – (Yn/2^n);
    Y(n + 1) := Y(n) + (Xn/2^n);
    Z(n + 1) := Z(n) – atan(1/2^i);
  else
    X(n + 1) := X(n) + (Yn/2^n);
    Y(n + 1) := Y(n) – (Xn/2^n);
    Z(n + 1) := Z(n) + atan(1/2^i);
  end if;
end for;

Where 'n' represents the number of iterations.

CORDIC implementations in hardware

• A sine computer in MyHDL (a Python-based HDL)
. CORDIC is used within the sine computer.
• A survey of CORDIC algorithms for FPGA based computers (PDF), by Ray Andraka, presented in FPGA 98.
• A very good tutorial overview of CORDIC PDF: CORDIC for Dummies
• Project report PDF of Verilog implementation by two students in George Mason University
  

Removing unneeded Ubuntu kernels

The command line way:

sudo apt-get remove --purge 2.6.2x-xx-*

where x is the old kernel version subversion numbers. Before that you need to give

uname -r

to find the current version and dont remove that.

JPEG Compression Source Code

• a smaller jpg encoder
• JPEGsnoop source code - useful software for reporting many stats inside JPEG files

Useful FFMPEG commands

Get info from media file

ffmpeg -i inputvideo.avi

Extract audio from any video

ffmpeg -i inputvideo.flv -vn audiofile.mp3

or

ffmpeg -i source_video.avi -vn -ar 44100 -ac 2 -ab 192 -f mp3 sound.mp3

Explanation:

• Source video : source_video.avi
• Audio bitrate : 192kb/s
• output format : mp3
• Generated sound : sound.mp3

Convert FLV to MP4

ffmpeg -i inputvideo.flv -vcodec copy -acodec copy outputvideo.mp4

or

ffmpeg -i inputvideo.flv -ar 22050 outputvideo.mp4

If you're lazy to type you can try the following but output video is big and ugly and takes ages to encode:

ffmpeg -i inputvideo.flv  outputvideo.mp4

Create a screencast

ffmpeg -f x11grab -s 800x600 -i :0.0 /tmp/screencast.mpg

Convert to 3gp format

ffmpeg -i input_video.mp4 -s 176x144 -vcodec h263 -r 25 -b 12200 -ab 12200 -ac 1 -ar 8000 output_video.3gp

Mix audio and video to create final video

ffmpeg -vcodec flv -qscale 9.5 -r 25 -ar 22050 -ab 32k -s 320x240 -i 1.mp3 -i Meta.ogv final.flv

Convert video to PSP MP4 format

ffmpeg -i "OriginalFile.avi" -f psp -r 29.97 -b 768k -ar 24000 -ab 64k -s 320x240 "OutputFile.mp4"

Convert video to iPod/iPhone format

ffmpeg -i inputvideo.avi input -acodec aac -ab 128kb -vcodec mpeg4 -b 1200kb -mbd 2 -flags +4mv+trell -aic 2 -cmp 2 -subcmp 2 -s 320x180 -title X outputvideo.mp4

Explanation:

• Source : source_video.avi
• Audio codec : aac
• Audio bitrate : 128kb/s
• Video codec : mpeg4
• Video bitrate : 1200kb/s
• Video size : 320px par 180px
• Generated video : final_video.mp4

Attribution:

• FFMPEG Cheat sheet: http://rodrigopolo.com/ffmpeg/cheats.html
• Complete list of FFMPEG commands: http://www.ffmpeg.org/documentation.html
• Some commands were from http://www.catswhocode.com/blog/19-ffmpeg-commands-for-all-needs
• Certain versions of Ubuntu eg 10.04 has of linker issues: http://brettwalenz.org/2011/08/17/ffmpeg-shared-libraries-relocation-errors-etc/

Hello World in SystemC

Create two files and run it at the Shell prompt.

1. Edit the CPP file first.

// All systemc modules should include systemc.h header file
 #include "systemc.h"
 // Hello_world is module name
 SC_MODULE (hello_world) {
   SC_CTOR (hello_world) {
     // Nothing in constructor 
   }
   void say_hello() {
     //Print "Hello World" to the console.
     cout << "Hello World.\n";
   }
 };
 
 // sc_main in top level function like in C++ main
 int sc_main(int argc, char* argv[]) {
   hello_world hello("HELLO");
   // Print the hello world
   hello.say_hello();
   return(0);
 }

2. Then create a Makefile. This makefile is reusable for all SystemC projects.

SYSTEMC=/usr/local/systemc
LDFLAGS= -L$(SYSTEMC)/lib-linux -lsystemc
CXXFLAGS=-Wno-deprecated -I$(SYSTEMC)/include -fpermissive

all:
 g++ $(CXXFLAGS) *.cpp $(LDFLAGS)
 ./a.out

3. The command "make" compiles and runs the Hello World program.

$ make
g++ -Wno-deprecated -I/usr/local/systemc/include  *.cpp -L/usr/local/systemc/lib-linux -lsystemc
./a.out

             SystemC 2.2.0 --- Aug 25 2011 10:30:16
        Copyright (c) 1996-2006 by all Contributors
                    ALL RIGHTS RESERVED
Hello World.

Install SystemC 2.2.0 on Ubuntu 11.04

Thanks to these tips from http://archive.pfb.no/2010/10/13/systemc-ubuntu-1010/ and http://noxim.sourceforge.net/pub/Noxim_User_Guide.pdf, I was able to install SystemC on 11.04 Natty Narwhal.

---

Begin borrowed material

---

Step 0: Prepare.

Obviously, you need to have a compiler. Do this step in case you haven't done so.

$ sudo apt-get install build-essential

Step 1: Download.

Next: register, and download from http://www.systemc.org using your Web browser then unpack it....but the tgz file has wrong extension. Do these steps to unpack the file:

$ mv systemc-2.2.0.tgz systemc-2.2.0.tar
$ tar xvf systemc-2.2.0.tar

Alternatively, download the file using wget from another site with the correct extension:

$ wget http://panoramis.free.fr/search.systemc.org/?download=sc220/systemc-2.2.0.tgz
$ tar xvfz systemc-2.2.0.tgz

Ooops! Turns out you can't use wget. Copy the URL to your browser location bar, answer a simple a question and the file will be downloaded. In any case, no need to reveal you email for this option!

In any case, create a build directory and enter into it for the following steps:

$ cd systemc-2.2.0
$ sudo mkdir /usr/local/systemc
$ mkdir objdir
$ cd objdir
$ export CXX=g++
$ sudo ../configure --prefix=/usr/local/systemc CPPFLAGS=-fpermissive

Step 2: Patch.

Using new versions of GCC such as GCC 4.4, we will fail to compile because 2 lines of code were left out of systemc-2.2.0/src/sysc/utils/sc_utils_ids.cpp.

Method 1: You can just just open the file and add these includes at the top of the file (after the header comments):

#include "cstdlib"
#include "cstring"
#include "sysc/utils/sc_report.h"

Replace the " signs with less than and greater than signs (because this blog site treats the the pair of characters as HTML tags).

Method 2: You patch it using a prewritten patch file.

$ wget http://www.pfb.no/files/systemc-2.2.0-ubuntu10.10.patch
$ patch -p1 < ../systemc-2.2.0-ubuntu10.10.patch

Method 3: Patch it using sed:

$ sed -i '1 i #include "cstdlib"\n#include "cstring"' ../src/sysc/utils/sc_utils_ids.cpp

Step 3: Compile

$ make
$ sudo make install
$ make check
$ cd ..
$ rm -rf objdir

The command make check is optional. What is does is to compile SystemC source files to see if the files can run. I strongly suggest that you run it.

Step 4: Tell your compiler where to find SystemC

Since we do not install SystemC with a standard location we need to specifically tell the compiler where to look for the libraries. We do this with an environment variable.

$ export SYSTEMC=/usr/local/systemc/

This, however will disappear on the next login. To permanently add it to your environment, alter ~/.profile or ~/.bash_profile if it exists. For system wide changes, edit /etc/environment. (newline with expression: SYSTEMC_HOME=”/usr/local/systemc/“) To compile a systemC program simply use this expression:

$ g++ -I. -I$SYSTEMC/include -L. -L$SYSTEMC/lib-linux -o OUTFILE INPUT.cpp -lsystemc -lm

---

End borrowed material

---

I still could not get SystemC installed in Fedora. :(