Re: How is BitBlt implemented - Algorithms Discussion Boards

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

ahhhhhh! Thanks again for the help!

Jeff

Hi Everyone

I want to post an article containing an implementation of an algorithm. Is there any way to display mathematical equations in articles?

Ryan

Maybe the Equation editor in MS Word, or as a graphics image if you use Latex or Tex...

"Real programmers just throw a bunch of 1s and 0s at the computer to see what sticks" - Pete O'Hanlon

Paul Conrad wrote:
Maybe the Equation editor in MS Word, or as a graphics image if you use Latex or Tex...

The equation editor emits images that would need to be inserted into the article.

Is there any way of embedded Latex into the HTML code and having that automatically generate the images?

Hi, I guess there are lots of equation editors (MS Word has one) that can emit HTML code;
such code could be pasted into an article.

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

Luc Pattyn wrote:
Hi, I guess there are lots of equation editors (MS Word has one) that can emit HTML code;
such code could be pasted into an article.

Thanks for the suggestion. Just tried it and it generates images that would need to be inserted into the article.

I was hoping to find a way to embed something like Latex into the article HTML and automatically generate the images.

There sure are some articles on equations here at CP; this one creates GIF images[^].

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