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

[Rybags]

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.

[andym00]

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 ?

[Rybags]

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.

[Crazyace]

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

[Crazyace]

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 )

[Rybags]

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 April 2, 2012 by Rybags

[NRV]

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?

[Rybags]

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

[flashjazzcat]

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.

[Rybags]

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 April 2, 2012 by Rybags

[Crazyace]

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)

[Heaven/TQA]

Jesus... I don't unerstand anything

[deathtrappomegranate]

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.

[Crazyace]

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

[deathtrappomegranate]

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.

[NRV]

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).

[Crazyace]

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.

[Rybags]

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.

[Crazyace]

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

[+5-11under]

I find this page useful at times. There is a section on checking for power of 2:http://graphics.stanford.edu/~seander/bithacks.html

[bogax]

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?

[flashjazzcat]

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.

[bogax]

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.

[Mclaneinc]

My head hurts!!!!

 

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

[Chilly Willy]

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 April 8, 2012 by Chilly Willy