Jump to content
Rybags

Can it be done, byte transform using only logic and maths

Recommended Posts

This is a VBXE related thing, but might have applications elsewhere.

 

I'm looking into using the blit to transform byte values into either $00 or $FF based upon their initial value, ie 00 remains 00 but 01 changes to FF.

 

The values needing transformation are limited to $80,$40,$20,$10,$08,$04,$02,$01.

 

$01 is easy - just ADD # $FF then XOR # $FF.

 

e.g. 00 + FF = FF XOR FF = 00

01 + FF = 00 XOR FF = FF

 

But it doesn't work with other values.

 

Can other values be done? The only operations we have available are OR, AND, XOR, ADD (subtract can be done too since in effect it's just a 2s complement add)

 

Note the 6502 isn't involved other than setting up/starting the blits.

Share this post


Link to post
Share on other sites

I can't see a clever solution right out, but wouldn't a simple lookup table do the job ? Modify a following blit with the data you've just read in the first, then the next blit does the lookup and destination write ?

Share this post


Link to post
Share on other sites

That was plan A - but when you're talking lots of data it just becomes too slow, almost as slow as having the CPU do it.

ie - an entire blit operation just for one byte, so we're talking around 10-20 times slower than a single blit that can do a block of data.

Share this post


Link to post
Share on other sites

it's impossible using just wrapped binary arithmetic - but I think you might be able to use 3 passes with vbxe ( using $80 example )

 

1: Fill dest with constant $7f

2: Conditionally copy ( and = $80,xor = $80 ) - so 0 pixels are $80 , and $80 pixels are left as $7f

3: Xor dest with const $80

Share this post


Link to post
Share on other sites

or maybe 2 blits if you destroy the original

 

( Again for 0x80 case )

 

Blit with OR constant $7f - ( 0,$80 becomes $7f,$ff )

Blit with conditional ( and $80,xor $80 ) and AND ( $80 AND $7f gives 0 , $ff left unchanged )

Share this post


Link to post
Share on other sites

Cool, I think that's the way. I had a similar idea and was working it in my mind but couldn't quite get it to fit.

 

So, same method, e.g. data 02

 

Fill dest with $FD

Cond. copy AND #02, XOR #02, 0 pixels will be $02, 02 pixels left as $fd

XOR dest with # 02, 0 pixels will be 0, 02 pixels will be FF.

Edited by Rybags

Share this post


Link to post
Share on other sites

I don't know how the blitter works, but..

To know if a value is a power of 2 (your eight values that need conversion) you can use:

 

f = (v AND (v - 1)) .. if this is zero then is a power of 2

The problem is that zero is also a "power of 2" with this method.. maybe you can replace all zeroes with another value, like $FF, before doing this..

 

Then you can use something like f2 = f OR (f XOR $FF) to transform any non zero value to $FF

And finally f3 = f2 XOR $FF to get the result in the format that you want..

 

If you can't use intermediate values maybe you can do more "passes" or use auxiliary buffers?

Share this post


Link to post
Share on other sites

The power of 2 thing isn't really the intention - it's more towards translating legacy packed graphics data into 8bpp.

Share this post


Link to post
Share on other sites

Clever solutions, guys. I spent an hour on this today and came up with zilch.

 

Gary: this is the exact problem I identified a while back with rendering fonts in VBXE modes - i.e. you just want each bit in the source data mapped onto a full byte on the screen.

Share this post


Link to post
Share on other sites

The added advantage of translate to $FF:

 

You can then render the font with a pattern effect, e.g. checkerboard or different colour each scanline. To make it look neater, have a seperate font that's an outline of the first. The $FF/$00 becomes the final AND mask that decides whether the pattern or background appears.

Edited by Rybags

Share this post


Link to post
Share on other sites

I looked quickly at the VBXE doc , and it can be two passes non destructively - allowing you to run 8 times on the same data to get full bit to byte expansion. ( by blitting individual columns )

 

Blitter Copy src->dest , AND (2^Bit), XOR (NOT(2^Bit)

Blitter AND src->dest(conditional) , AND(2^Bit) , XOR (2^Bit)

  • Like 1

Share this post


Link to post
Share on other sites

NRV's (X AND (X-1)) looks like an elegant solution to the problem, but would VBXE's blt_zoom, with the x-zoom nibble set to 8 (decimal) achieve something similar? I can't tell from the docs whether it would work in this way or not.

Share this post


Link to post
Share on other sites

NRV's method wouldn't actually work though - as all the original values are powers of 2 - and it doesn't distinguish between them , as v&(v-1) == v when v=2^x.

I think the bli_zoom would just duplicate the byte value 8 times - it's not working on bits

Share this post


Link to post
Share on other sites
NRV's method wouldn't actually work though - as all the original values are powers of 2 - and it doesn't distinguish between them , as v&(v-1) == v when v=2^x.

 

From the OP, I didn't think that it was necessary to distinguish between them, just to return $FF if one bit was set. It's more complicated if differentiation between the set bits is needed.

 

I think the bli_zoom would just duplicate the byte value 8 times - it's not working on bits

 

Ah, OK, thanks. It would need to be done bitwise to work.

Share this post


Link to post
Share on other sites

NRV's method wouldn't actually work though - as all the original values are powers of 2 - and it doesn't distinguish between them , as v&(v-1) == v when v=2^x.

I think the bli_zoom would just duplicate the byte value 8 times - it's not working on bits

 

I'm still a little confused about what is needed :), but I suppose you mean v&(v-1) == 0 when v=2^x ?

When v is not a power of 2, then the result is different than 0 (could be differents values.. well to be exact "the rightmost bit is cleared" from v).

Share this post


Link to post
Share on other sites

Yes NRV sorry about that - I typed too quickly :) , but testing a power of 2 isnt the problem posed anyway. Rybags wants bit to byte/pixel expansion for graphics.

Share this post


Link to post
Share on other sites

Next problem - I tend to think this one might be impossible.

 

Same rules (blits only) can we transform an array such that if a byte contains a certain value, it's set to $FF, other values get set to $00.

Share this post


Link to post
Share on other sites

Maybe, V=ref

 

Copy blit , XOR with (255 XOR v ) - so dest is FF for V values

Blit dest over itself

Conditional AND blit ( XOR 255 ) to give (NOT dest) AND dest if dest!=255

Share this post


Link to post
Share on other sites

Not sure I understand the problem (or the blitter) so maybe this

will be whacked.

 

The problem is to write 0 if the source byte is 0 and write FF if the

source byte is non 0.

The source just happens to be restricted to powers of 2. (including

0)

 

So do an XOR pass with FF filled destination. to get either 0

or the compliment of the source.

Then do an OR pass between the source and the (now compliment

destination) to get either 0 or the source OR the compliment (ie FF)

 

Am I missing something?

Share this post


Link to post
Share on other sites

Won't the XOR pass give you $FF in the destination for source=0? So you'd basically get $FF for the entire range, including the 0? I have a headache mind you, so I'm probably wrong. ;)

Share this post


Link to post
Share on other sites

Won't the XOR pass give you $FF in the destination for source=0? So you'd basically get $FF for the entire range, including the 0? I have a headache mind you, so I'm probably wrong. ;)

 

oops yes I think you are correct.

I thought it was writing a 0 if the source is 0.

On a closer reading it looks like it doesn't write at all if the source is 0

 

But it looks like it can be done in one pass.

By making the source the destination and using a collision detection mask of FF

and an XOR and AND mask of FF and either arithmetic sum mode

or OR mode

 

the description of OR mode, mode 3:

 

"The written out data dest’ is a result of a bitwise OR of source” and dest.

 

source = ReadSource();

source' = source & blt_and_mask;

source'' = source' ^ blt_xor_mask;

if (source'' != 0)

dest = ReadDest();

if (dest & blt_collision_mask) BLT_COLLISION_CODE = dest;

dest' = dest | source'';

WriteDest(dest');"

 

 

So eg in OR mode if the source is 0 it will stay 0

If the source is not 0 then it will get ANDed with the AND mask ie FF (source')

That will be XORed with the XOR mask ie FF producing the compliment (source")

And that will be ORed with the source producing FF (dest')

Then written to the destination ie written back if the destination is the same

as the source.

Share this post


Link to post
Share on other sites

My head hurts!!!!

 

Nice to see someone went to school and learned something, unlike myself...

Share this post


Link to post
Share on other sites

Can you only ADD immediate values, or can it be added to itself? If it can be ADDed to itself, you can get FF from any of the values you stated, or 0 for 0 this way:

 

starting with v

a = v - 1

b = v + v

c = b + b

d = c + c

e = d + d

f = e + e

g = f + f

h = g + g

final value = v + a + b + c + d + e + f + g + h

 

EDIT: Actually, that first a = v - 1 won't work for 0. :(

 

It would be better if there was a rotate command. That would solve you problems.

Edited by Chilly Willy

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...