Re: How is BitBlt implemented - Algorithms Discussion Boards

memcpy is not /that/ fast in most implementations (you can almost always use mmx/sse2 to write a faster one if you want)

consider for one thing that the details of the copy are passed as parameters, it must at least do some work to use them, this is a waste if you already know what they are (the for loop tells the compiler for you)

also when operating on memory some instructions do not need an additional mov, which means they can be as fast, or faster, than a memory copy, others force you to do two movs (mul and div for instance)

I noticed several optimizations that may speed up your algorithm:

1. In the innermost loop, you're recomputing (x&y) even though they don't change for different z values. If you assign (x&y) to a temporary variable before the z loop, it will save time.

2. Computing the address for ROP[x][y][z] every iteration wastes time. If you set a pointer to the first element (ROP[0][0][0]), it can be incremented in one instruction to point to the next element to store your result. This is faster than the several arithmetic operations needed to access an element in a 3D array.

Your second case does this 3D-element-address calculation twice each iteration, and takes the most time.

3. You might try making z a register variable.

4. It's been claimed that ++x is faster than x++ because the pre-incremented value isn't needed.

5. The slow performance in the third case is surprising. One thing you could try to bypass memcpy is the #asm directive to include in-line assembly language to copy the memory block.

Hope this helps...

IIRC ActionScript is basically JavaScript, and like any interpreted language, its very slow. Sure, if you call an inbuilt antialiasing function or drawline routine, they will execute fast - but they are not written in ActionScript, just made avaliable to ActionScript.

There would be no hope of matching a native code implementation with pure ActionScript.

I would start looking for a workaround - does AS provide say a copy-paste between canvas, for example?

Mark Churchill
Director
Dunn & Churchill

Mark Churchill wrote:
There would be no hope of matching a native code implementation with pure ActionScript.

I would start looking for a workaround - does AS provide say a copy-paste between canvas, for example?

Mark Churchill
Director
Dunn & Churchill

They do have a CopyPixels function, which is like BitBlt without ROP codes. AS also offers a number of different things like BlendModes and filters and merges and so on, of bitmaps. What they don't offer is a straightforward bitwise logical combinations, so if you have something very specific you need to do that doesn't match up with their esoteric sounding functions you're evidently out of luck. For example with BlendMode.Add you have "Adds the values of the constituent colors of the display object to the colors of its background, applying a ceiling of 0xFF. This setting is commonly used for animating a lightening dissolve between two objects." In addition you have things like BlendMode.Multiply BlendMode.Screen, etc. There's even a BlendMode.Invert which is a bitwise NOT, but no AND or OR, for some reason - maybe Microsoft holds a copyright on two of the three logical operators, who knows. I'm sure all these operations are plenty fast as well, judging from my experience with other things in AS (Flex actually). With filters, you have things like convolution filters, displacement filters that look somewhat promising if you're able to decipher what they actually do. There's many other things as well - matrices, alpha, etc.

IIRC, it's implemented by the specific device driver (and the real work probably happens on the device hardware itself).

and, there's no way you're going to even approach the speed of something like BitBlt in a scripting language.

image processing toolkits | batch image processing

Force Code wrote:
So I need to find out the algorithms that BitBlt is employing to do what it does and if its possible for me to emulate that (assuming that BitBlt isn't relying primarily on graphics hardware that can't be accessed from a web application.)

did you try googling bitblt.c? Although the current version has gone through some changes over the years, the code is as old as I am. BitBlt operations were done before accelerated graphics cards for memory manipulaton. It was these routines that were used over and over again that became part of hardware operations on the graphics card (2D acceleration), and eventually part of multimedia and extended instruction sets of the CPU itself.

When you find it, you will discover why it was done in hardware to speed it up. I am with the others, you are not going to be happy with the performance. Hardware operations of BitBlt will be nice and smooth, you can achieve the same on a fast processor, but you are wasting a LOT of processor cycles that could be more effectively used on something more important than reinventing the wheel.

_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

El Corazon wrote:
did you try googling bitblt.c? Although the current version has gone through some changes over the years, the code is as old as I am. BitBlt operations were done before accelerated graphics cards for memory manipulaton. It was these routines that were used over and over again that became part of hardware operations on the graphics card (2D acceleration), and eventually part of multimedia and extended instruction sets of the CPU itself.

Thanks - this is useful tip.
If BitBlt is encoded in hardware now, then presumably flash could access it, and probably they already are accessing it, because as I mentioned in a a reply yesterday, they have all sorts of "Blendmodes", filters, merges and so on, that are possible with bitmaps. What they don't have is the ability to specify a logical combination of bitmaps using bitwise operators. The more I think of it, its probably because Microsoft has copyrighted the ROP code concept. The raster op I actually need to use is 00AC0744, which corresponds to the operation (((S ^ D) & P) ^ S), where S,P,D are bitmaps. If anyone knows how to accomplish this using any of the various graphical operations that are a part of the actionscript or flex environment, you would get my sincere thanks.

Force Code wrote:
If BitBlt is encoded in hardware now, then presumably flash could access it, and probably they already are accessing it,

It is in hardware, they are accessing it now through hardware. The primary goal in script languages such as this is to raise the script programmer to a higher level. If you program a low-level routine in script and compare it to a compiled language, the result would always favor the compiled language. So you don't even attempt to compete at that level.

Where a graphic library in C/C++ might use BitBlt() functions to manipulate graphics, in script you operate on a higher level at the object level not at the bitmap level. This might actually employ several low-level routines, precompiled into a higher order function that is called by the script. As you grow the language to a higher level your speed approaches compiled equivalence because you are calling pre-compiled low-level routines from the high-level script language.

So, yes, I although I have not used flash in ages, I am sure they are using BitBlt() functions in their code somewhere. Now flash did undergo an even larger change about 2 years ago, operating in 2D mode as a 3D higher order function. This bypasses the need for BitBlt() functions because of depth buffer access on a 3D graphics card and blend modes. Where a 3D graphics card is not available to use, I am sure the routines are still there to drop back to 2D BitBlt() functions.

Or at least I should say, they intended to change. Since I don't do flash anymore I have no way to verify it. But I was there at the Siggraph presentation talking about the transition from 2D to 3D operations for both speed and additional functionality. The presentation was pretty good since they showed the three phases, reproducing exactly what they had in 2D to 3D (no visible change, only faster drawing), and then they added some "special effects" magic that would be unreasonable under 2D.

Sorry, can't help you with the script language itself, I can help in theory, but not specifics when it comes to flash.

_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

El Corazon wrote:
The primary goal in script languages such as this is to raise the script programmer to a higher level. If you program a low-level routine in script and compare it to a compiled language, the result would always favor the compiled language. So you don't even attempt to compete at that level.

Where a graphic library in C/C++ might use BitBlt() functions to manipulate graphics, in script you operate on a higher level at the object level not at the bitmap level.

Actionscript 3.0, which is what I'm using, nearly duplicates C and C++ syntax with very minor modifications. There is a BitmapData class as well, with a method GetPixels which dumps it into a byte array. So, they certainly give the impression that reasonable speeds might be possible on low-level operations.

Force Code wrote:
So, they certainly give the impression that reasonable speeds might be possible on low-level operations.

no, they provide that functionality especially for read/write operations (I/O) for communication reasons, interface reasons. You don't want to write your whole code in Actionscript, but you might want to interface something else to it, or you might actually want to "get" the result. These are common and assumed, regarless of the level of the language. The verbs, the actions you want to be much higher in level, or rarely used, because coding low-level in a script produces poor performance quality and the assumption is that it is flash's fault, not the programmer for doing something that he should have known would have poor performance.

Good luck.

_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

El Corazon wrote:
You don't want to write your whole code in Actionscript, but you might want to interface something else to it, or you might actually want to "get" the result.

Curious as to what you're alluding to, here. I'm actually using flex with embedded actionscript, but the flex compiler converts everything to actionscript before continuing. Don't know how to interface anything in the flash world to something outside of flash.

El Corazon wrote:
The verbs, the actions you want to be much higher in level, or rarely used, because coding low-level in a script produces poor performance quality and the assumption is that it is flash's fault, not the programmer for doing something that he should have known would have poor performance.

Its better to light a candle than to curse the darkness. Suspicious | :suss:

Force Code wrote:
Don't know how to interface anything in the flash world to something outside of flash.

You are telling me you have NEVER used an image not created by flash to be manipulated by flash, or written an image manipulated by flash as an image to be used outside of flash?

Although that is seemingly a minor usage, it is actually very powerful. In 3D graphics we now carry huge amounts of information in 3D images, even processing vectors, or energy systems through the use of what would normally be image information. You can carry all kinds of information in a bitmap, from state systems to partially computed results of a state machine. You can get very creative. Thus an image may seem only image exchange, but you can save out settings, or lookup a table of precomputed atmospheric turbulence models to use in real-time animation. An image is no longer "just an image" anymore.

Force Code wrote:
Its better to light a candle than to curse the darkness.

They did light you a candle, many of them. But lighting a candle does not make the darkness go away. It is an acceptance that darkness exists and that something must be done about it. No one cursed the darkness: idiot programmers exist, its a fact of life, so you take steps to provide the functionality without allowing the idiots to ruin your reputation. THAT is common sense and a very reasonable business model. Anything else would be suicide.

_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

El Corazon wrote:
You are telling me you have NEVER used an image not created by flash to be manipulated by flash, or written an image manipulated by flash as an image to be used outside of flash?

Although that is seemingly a minor usage, it is actually very powerful. In 3D graphics we now carry huge amounts of information in 3D images, even processing vectors, or energy systems through the use of what would normally be image information. You can carry all kinds of information in a bitmap, from state systems to partially computed results of a state machine. You can get very creative. Thus an image may seem only image exchange, but you can save out settings, or lookup a table of precomputed atmospheric turbulence models to use in real-time animation. An image is no longer "just an image" anymore.

The image formats compatible with flash that I know about are PNG and JPG. As I mentioned previously, I need to perform one operation ((S^D)&P)^S), where S,D, and P are bitmaps. Actually this operation has to be fast as it will be done continuously. If I had access to BitBlt that would certainly work. If the techniques you describe using embedded states in 3D images or whatever could accomplish it, then is there some background material that would explain it.

Thanks.

Tried looking at the theory behind those blend filters, I don't know much about them but I do know that filters on images are nothing more than vector ops, maybe they have one that does the same or a combo that gets you that result you want. Or try and see if you can break down your op into something they have. A bit of math and you should know if you can use their tools or go the brute force way since I doubt a scripting language would give access to base hardware routines, but who knows.

Hi,

I realize your question is old, but just in case it is still open:

- On the algorithm: The Windows BitBlt API is just an interface to the hardware blitter (BLIT = Binary Large Image Transfer) present on the graphics card or other hardware your'e talking to. If the hardware doesn't have a blitter, the algorithm is just a loop (depending on CPU, it may also be a call to a CPU BLIT instruction if one is available - as in MMX/SSE) similar to the one you've written in previous posts in this thread. That you can't find the function in ActionScript is because the language (like most scripting languages) doesn't like exposing stuff that could result in buffer overruns and similar stuff (it blindly assumes that anyone using it is not a "real programmer" - a common but often self-fulfilling misconception held by script language designers).

- On your thoughts about precalculating and looking up ROP results: Memory cycles are (nowadays) several orders of magnitude slower than CPU cycles, while bitwise logical operations (like ROPs) are extremely fast. Precalculating values and retrieving them by index (which calls not only for memory accesses, but also for address calculations that cost *more* than the ROPs themselves) should normally be noticeably slower than doing the ROPs in the loops.

- On optimization: Try making the ROPs using the computers preferred word length (32/64 bits) if it's not fast enough on the individual bytes. An Intel-style CPU will be almost as fast using bytes but RISCs traditionally have a heavy penalty for using bytes instead of words (the compiler has to shift and mask each byte out of words and back like crazy as the CPU usually only has word-length instructions). Also, do any complex offset (pixel coordinate to byte or word offset) calculations outside of the loop (so that the pixel addressing is just a straight increment inside the loop).

Performance-wise, you'll probably do just fine looping over bytes unless the ActionScript interpreter is junk (never tested it). On a modern CPU this kind of approach is surprisingly close to a hardware blitter in performance for moderately-sized images. I've seen stuff written in C# that does substantially heavier math (such as image rotating) on each pixel than simple ROPs, and performs well enough (even in the debugger) for live animation purposes.

Later,
Peter

I have learn about ID3 Algorithm sourcecode form code project, and i want to compare with c4.5 algorithm. Does any body have c4.5 source code?

[sory for my bad english]

Hi,

Please visit the following links:

http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/tutorial.html[^]

http://en.wikipedia.org/wiki/C4.5_algorithm[^]

I hope this helps.

Regards,
John Adams
ComponentOne LLC

I'm trying to figure out how to split a polygon (in the form a C# Point array) into the least number of rectangles. The polygon itself is already limited to only have straight horizontal or vertical lines. So it can always be split into n number of rectangles, I'm just not sure how to go about a) splitting it, and b) figuring out the lowest number of rectangles.

So if someone doesn't mind, could you give me a rough example and the theory behind it?

Hi,

not a formal algorithm, but something to get you started:

given a polygon with straight angles only, you need four points to describe one rectangle.
if you add two points, you can only get an L-shape for which you basically have two
2-rectangle fills (excluding overlapping rectangles).
for every two points you add, you will need one more rectangle.
So: P = 2*R + 2
with R = number of rectangles and P = number of points.

If you allow for overlapping rectangles though, you may be able to cover the same area
with fewer rectangles. Example: form a cross from two rectangles, you'll get 8 points.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google

Unless you have a T shape... you could do it with 2 non-overlapping rectangles but it has 8 points.

Jeff

Can someone please explain to me how assym encryption algs work? It appears that there are two mathmatically related keys, but they are related in some "hard to find" way. My understanding is that you encrypt the data with some public key, then the same data can only be decrypted using both the public and private key. If my understanding is correct, then I am confused as to how the sender encrypts something, but that encryption cannot be undone using only the public key. Can someone please explain this to me? Thanks,

Jeff

Skippums wrote:
Can someone please explain to me how assym encryption algs work?

http://en.wikipedia.org/wiki/Public-key_cryptography[^]

The most common ones [asymmetric key systems] have the property that Alice and Bob each own two keys, one for encryption and one for decryption. In a secure asymmetric key encryption scheme, the decryption key should not be deducible from the encryption key. This is known as public-key encryption, since the encryption key can be published without compromising the security of encrypted messages. In the analogy above, Bob might publish instructions on how to make a lock ("public key"), but the lock is such that it is impossible (so far as is known) to deduce from these instructions how to make a key which will open that lock ("private key"). Those wishing to send messages to Bob use the public key to encrypt the message; Bob uses his private key to decrypt it.<br />

_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)

Hi Jeff,

imagine two large prime numbers, say 50 digits each.
There are encryption algorithms that use two such numbers, needing them both to decrypt, but
only needing their product to do the encryption. So the product is the public key,
and the prime factors constitute the private key. Splitting a 100-digit nhumber in two
huge primes is a big job, not to be solved in a matter of hours...

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google

Man, you are everywhere! Are you paid to contribute to this thing? I think that you have single-handedly answered nearly every question that I have ever posted on this forum. Anyway, I understand how the public and private keys can be generated after looking at wikipedia's encryption page. What I am still confused about is how, given only the public key, you can encrypt something but not decrypt it. How is it that I can take some data, apply some known algorithm, and still not be able to undo that algorithm after I am done? It just doesn't seem possible. Any further insight as to how things get irreversibly encrypted would be appreciated. Thanks again,

Jeff

Well it is not really irreversible, the fact is the cost is several orders of magnitude
larger to decrypt (without the prime factors) than it is to encrypt.

Some operations are just more difficult to undo than they are to do. Example:
what is the value of 1234567 ^ 7 modulo 2^32 is easy
but which number x satisfies x^7 modulo 2^32 = 7654321 is hard.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

this months tips:
- use PRE tags to preserve formatting when showing multi-line code snippets
- before you ask a question here, search CodeProject, then Google