Programming, graphics, games, media, C++, Windows, Internet and more...
Entries for tag "algorithms", ordered from most recent. Entry count: 68.
# Resizing Images to Generate Thumbnails in PHP
Fri
06
Jan 2012
Some time ago I came across a problem of calculating an image size for automatically generated thumbnail for gallery script coded in PHP. It required a moment's thought, so I'd like to share this algorithm. In fact there will be two algorithms.
First code scales the image down with following rules: Destination size will not exceed given thumbnail size, but the width or height can be smaller to always preserve aspect ratio. Images smaller than thumbnail size are not magnified.
Inputs:
$src_size_x, $src_size_y - Source image size.
THUMBNAIL_SIZE_X, THUMBNAIL_SIZE_Y - Constants defining thumbnail size.
Outputs:
$dst_size_x, $dst_size_y - Destination thumbnail size.
if( $src_size_x <= THUMBNAIL_SIZE_X && $src_size_y <= THUMBNAIL_SIZE_Y )
{
$dst_size_x = $src_size_x;
$dst_size_y = $src_size_y;
}
else
{
$dst_size_x = THUMBNAIL_SIZE_X;
$dst_size_y = (int)( $src_size_y * THUMBNAIL_SIZE_X / $src_size_x );
if( $dst_size_y > THUMBNAIL_SIZE_Y )
{
$dst_size_x = (int)( $src_size_x * THUMBNAIL_SIZE_Y / $src_size_y );
$dst_size_y = THUMBNAIL_SIZE_Y;
}
}
Second algorithm also helps with generating image thumbnails, but works differently. It assumes that destination image will always be of size (THUMBNAIL_SIZE_X, THUMBNAIL_SIZE_Y), while source iamge can be cropped to select only the center of the image if it has different aspect ratio than the thumbnail.
Inputs to this algorithm are the same, while outputs are:
$src_x, $src_y - Offset in the source image to begin copying from.
$src_w, $src_h - Size of the rectangle to select from cropped source image.
The code that uses this algorithm should then select from the source image a rectangle with left-top position ($src_x, $src_y), size ($src_w, $src_h) and copy it, with scaling and resampling, to the destination image with the size exactly (THUMBNAIL_SIZE_X, THUMBNAIL_SIZE_Y). That's what imagecopyresampled function from GD library can do. This algorithm does not handle cases where source image is smaller than thumbnail.
$src_h = $src_size_y;
$src_w = (int)( $src_h * THUMBNAIL_SIZE_X / THUMBNAIL_SIZE_Y );
if( $src_w <= $src_size_x )
{
$src_x = ( $src_size_x - $src_w ) / 2;
$src_y = 0;
}
else
{
$src_w = $src_size_x;
$src_h = (int)( $src_w * THUMBNAIL_SIZE_Y / THUMBNAIL_SIZE_X );
$src_x = 0;
$src_y = ( $src_size_y - $src_h ) / 2;
}
Comments | #webdev #algorithms #php Share
# Fast, Heuristic Disk Search
Wed
04
Jan 2012
In March 2007 I've written an algorithm which I called "Fast, heuristic disk search" and published it in my article Szybkie, heurystyczne przeszukiwanie dysku (in Polish) on codeguru.pl. Today I went back to it, improved it a bit and I think it is a good opportunity to present it once again, this time in English :)
The problem is about searching hard disk, looking for a file or directory with particular name. Naive approach, which is used by file searching functions in programs like Total Commander, uses depth-first search, so it enters C:\, then C:\Program Files, then C:\Program Files\Adobe etc., spending lots of time in places where it probably won't find the file we are looking for.
Game developers know that searching algorithm can be significantly improved by using some heuristics that will drive algorithm towards (probably) right direction. We do it in A* pathfinding. Does a similar principle could be used also when searching for a file?
My particular problem was configuring a program with path to a console tool, let's say fxc.exe shader compiler from DirectX SDK. We could present a textbox where user has to enter path to this tool. We could also make "Browse" button with an open file dialog to simplify locating it. But wouldn't be great if program tried to locate it automatically on first run? Some installed programs store path in a registry key, but if it doesn't, we have no idea where could it be if we don't look for it among files and directories on hard disk.
My algorithm tries to locate given file or directory in given time limit by searching all given directories and their subdirectories. The improvement I propose here is inteligent management of the order in which we process these directories.
The algorithm uses two collections: a queue of directories to process and a set of already visisted directories. Here is the code in C#:
Comments | #algorithms #.net Share
# Circular Buffer of Raw Binary Data in C++
Fri
21
Oct 2011
Circular Buffer, Cyclic Buffer or Ring Buffer is a data structure that effectively manages a queue of some items. Items can be added at the back and removed from the front. It has limited capacity because it is based on preallocated array. Functionality is implemented using two pointers or indices - pointing to the first and past the last valid element. The Begin pointer is incremented whenever an item is popped from the front so that it "chases" the End pointer, which is incremented whenever a new item is pushed to the back. They can both wrap around the size of the array. Both operations are done very effectively - in constant time O(1) and no reallocations are needed. This makes circular buffers perfect solution for queues of some data streams, like video or audio.
It's not very sophisticated data structure, but there is one problem. Sample codes of circular buffers you can find on the Internet, just like for many other data structures, operate usually on a single object of some user-defined type. What if we need a buffer for raw binary data, stored as array of bytes? We can treat single bytes as data items, but enqueueing and dequeueing single bytes with separate function calls would not be efficient. We can, on the other hand, define some block of data (like 4096 bytes) as the type of item, but this limits us to operating on on such block at a time.
Best solution would be to write an implementation that operates on binary data in form of (const char *bytes, size_t byte_count) and allows writing and reading arbitrary amount of data in a single call, just like functions for writing and reading files do. The only problem that arises in such code is that sometimes the block of data you want to write to or read from the buffer is not in a continuous region of memory, but wraps around to the beginning of the array so we have to process it on two parts - first at the end of the array and the second at the beginning.
Here is my C++ implementation of a circular buffer for raw binary data:
#include <algorithm> // for std::min
class CircularBuffer
{
public:
CircularBuffer(size_t capacity);
~CircularBuffer();
size_t size() const { return size_; }
size_t capacity() const { return capacity_; }
// Return number of bytes written.
size_t write(const char *data, size_t bytes);
// Return number of bytes read.
size_t read(char *data, size_t bytes);
private:
size_t beg_index_, end_index_, size_, capacity_;
char *data_;
};
CircularBuffer::CircularBuffer(size_t capacity)
: beg_index_(0)
, end_index_(0)
, size_(0)
, capacity_(capacity)
{
data_ = new char[capacity];
}
CircularBuffer::~CircularBuffer()
{
delete [] data_;
}
size_t CircularBuffer::write(const char *data, size_t bytes)
{
if (bytes == 0) return 0;
size_t capacity = capacity_;
size_t bytes_to_write = std::min(bytes, capacity - size_);
// Write in a single step
if (bytes_to_write <= capacity - end_index_)
{
memcpy(data_ + end_index_, data, bytes_to_write);
end_index_ += bytes_to_write;
if (end_index_ == capacity) end_index_ = 0;
}
// Write in two steps
else
{
size_t size_1 = capacity - end_index_;
memcpy(data_ + end_index_, data, size_1);
size_t size_2 = bytes_to_write - size_1;
memcpy(data_, data + size_1, size_2);
end_index_ = size_2;
}
size_ += bytes_to_write;
return bytes_to_write;
}
size_t CircularBuffer::read(char *data, size_t bytes)
{
if (bytes == 0) return 0;
size_t capacity = capacity_;
size_t bytes_to_read = std::min(bytes, size_);
// Read in a single step
if (bytes_to_read <= capacity - beg_index_)
{
memcpy(data, data_ + beg_index_, bytes_to_read);
beg_index_ += bytes_to_read;
if (beg_index_ == capacity) beg_index_ = 0;
}
// Read in two steps
else
{
size_t size_1 = capacity - beg_index_;
memcpy(data, data_ + beg_index_, size_1);
size_t size_2 = bytes_to_read - size_1;
memcpy(data + size_1, data_, size_2);
beg_index_ = size_2;
}
size_ -= bytes_to_read;
return bytes_to_read;
}
Similar phenomenon can be observed in API of the FMOD sound library. Just like graphical textures in DirectX, sound samples in FMOD can also be "locked" to get pointer to a raw memory we can read or fill. But DirectX textures lie in the continuous memory region, so we get a single pointer. The only difficult thing in understanding locking textures is the concept of "stride", which can be greater than the width of a single row. Here in FMOD the Sound::lock() method returns two pointers and two lengths, probably because the locked region can wrap over end of internally used circular buffer like the one shown above.
Comments | #c++ #algorithms Share
# Bit Tricks with Modulo
Sat
26
Feb 2011
I like to emphasize that programming is not so similar to maths as some people say. We are used to thinking about numbers in decimal numeral system and the operations that seem most natural for us are arithmetic computations like additions, multiplication and division. On the other hand, computer works with numbers stored in binary system and bitwise operations are most efficient and natural for it. Another difference is modulo operation (the remainder after division) - a function not so frequently used in math classes, but very important in programming. That's what I'd like to talk about here.
Modulo in C++ can be done using % operator, but just as division, it is quite slow. So when doing a common operation of cycling between subsequent numbers from a limited range:
x2 = (x1 + 1) % n;
few alternatives have been developed for some special cases, using bitwise operations.
First, when the divisor is a power of 2, we can use bitwise and (operator &) to mask only least significant bits of the addition result. But this optimization can be done automatically by the compiler (at least my Visual C++ 2010).
// 7 = 0b111, so it masks 3 least significant bits.
// Equal to (x1 + 1) % 8
x2 = (x1 + 1) & 7;
When we only cycle between two values - 0 and 1 - we can use XOR (operator ^):
// Equal to (x1 + 1) % 2, for values 0, 1.
x2 = x1 ^ 1;
Finally, when we cycle between three values - 0, 1, 2 (like when indexing x, y, z components of a 3D vector), we can use the trick invented by Christer Ericson (at the end of the linked page). I came across it recently on Twitter and that's what inspired me to write this article.
// Equal to (x1 + 1) % 3, for values 0, 1, 2.
x2 = (1 << x1) & 3;
Comments | #math #c++ #algorithms Share
# My Implementation of Diff Algorithm
Tue
16
Nov 2010
Algorithm for comparing two sequences of some data is very useful. For example, version control systems like SVN or Git use it to highlight differences between two versions of a text file. But what if you need to code such algorithm from scratch? Today it was my task and it turned out to be not so simple, so I want to share my sample implementation in C++ which I came up with based on some readings from the Internet and my previous experiences with calculating Levenshtein distance.
What we need to compare is sometimes just lines of text files that are equal or not, but I needed something more complex, so let's say an item is defined as follows:
struct Item
{
unsigned ID;
const char *Text;
};
For items from opposite sides to be comparable they must have same ID values. Text may be different, but I'd prefer to match items with same Text (treated as NULL-terminated string) or at least same Text length.
Here are sample data:
const Item items1[] = {
{ 1, "Foo" },
{ 1, "Foo" },
{ 2, "Bar" },
{ 4, "Foobar" },
};
const Item items2[] = {
{ 1, "Foo" },
{ 1, "Firefox" },
{ 1, "Another one" },
{ 2, "Boo" },
{ 5, "Last one" },
};
const unsigned count1 = _countof(items1);
const unsigned count2 = _countof(items2);
The final result may look like this:
1 Foo <-> 1 Foo
-- <-> 1 Firefox
1 Foo <-> 1 Another one
2 Bar <-> 2 Boo
4 Foobar <-> --
-- <-> 5 Last one
# Music Analysis - Spectrogram
Wed
14
Jul 2010
I've started learning about sound analysis. I have some deficiencies in education when it comes to digital signal processing (greetings for the professor who taught this subject at our university ;) but Wikipedia comes to the rescue. As a starting point, here is a spectrogram I've made from one of my recent favourite songs: Sarge Devant feat. Emma Hewitt - Take Me With You.
Now I'm going to exaplain in details how I've done this by showing some C++ code. First I had to figure out how to decode an MP3, OGG or other compressed sound format. FMOD is my favourite sound library and I knew it can play many file formats. It took me some time though to find functions for fast decoding uncompressed PCM data from a song without actually playing it for all 3 minutes. I've found on the FMOD forum that Sound::seekData and Sound::readData can do the job. Finally I've finished with this code (all code shown here is stripped from error checking which I actually do everywhere):
Comments | #math #libraries #music #rendering #dsp #algorithms Share
# Timespan from/to String Conversion
Tue
29
Jun 2010
Today I'd like to show a piece of code I've written today. These are functions for converting between a timespan, stored in a int64 as number of milliseconds and string in for of "HH:MM:SS.MMM" (hours, minutes, seconds, milliseconds). That's IMHO a convenient way of presenting timespan to the user. I'll include these functions in the next version of my CommonLib library, to work with raw millisecond number as well as TIMESPAN and/or GameTime types.
The code is in C++, uses STL string and my own StrToUint and UintToStr functions. All suggestions about how these algorithms could be optimized are welcome.
Comments | #algorithms #c++ Share
# LZMA SDK - How to Use
Sat
08
May 2010
What do you think about when I tell a word "compression"? If you currently study computer science, you probably think about some details of algorithms like RLE, Huffman coding or Burrows-Wheeler transform. If not, then you surely associate compression with archive file formats such as ZIP and RAR. But there is something in between - a kind of libraries that let you compress some data - implement a compression algorithm but do not provide ready file format to pack multiple files and directories into one archive. Such library is useful in gamedev for creating VFS (Virtual File System). Probably the most popular one is zlib - a free C library that implements Deflate algorithm. I've recently discovered another one - LZMA. Its SDK is also free (public domain) and the basic version is a small C library (C++, C# and Java API-s are also available, as well as some additional tools). The library uses LZMA algorithm (Lempel–Ziv–Markov chain algorithm, same as in 7z archive format), which has better compression ratio than Deflate AFAIK. So I've decided to start using it. Here is what I've learned:
If you decide to use only the C API, it's enough to add some C and H files to your project - the ones from LZMASDK\C directory (without subdirectories). Alternatively you can compile them as a static library.
There is a little bit of theory behind the LZMA SDK API. First, the term props means a 5-byte header where the library stores some settings. It must be saved with compressed data to be given to the library before decompression.
Next, the dictionary size. It is the size of a temporary memory block used during compression and decompression. Dictionary size can be set during compression and is then saved inside props. Library uses dictionary of same size during decompression. Default dictionary size is 16 MB so IMHO it's worth changing, especially as I haven't noticed any meaninful drop in compression rate when set it to 64 KB.
And finally, end mark can be saved at the end of compressed data. You can use it so decompression code can determine the end of data. Alternatively you can decide not to use the end mark, but you must remember the exact size of uncompressed data somewhere. I prefer the second method, because remembering data size takes only 4 bytes (for the 4 GB limit) and can be useful anyway, while compressed data finished with end mark are about 6 bytes longer than without it.
Compressing full block of data with single call is simple. You can find appropriate functions in LzmaLib.h header. Here is how you can compress a vector of bytes using LzmaCompress function: