| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
Dropping bits
Hmm, I've got a question for all you bitwise math cracks...
What is the best way (read: fastest way) to drop some bits of a group of bytes? And by dropping a bit I mean that the bit is deleted and not set to 0.
So for example:
Byte = 10100101
Dropping bit 2 from byte and reorder to the right, gives:
Byte = 01010001
I came up with a little routine which processes 4 bytes, dropping off bit 0 from every byte...
Example code follows:
-----------------------------------------------------------
B1: B2: B3: B4:
00110011 10100101 10010011 01010101
lsr B1 ;throw away 1 bit from B1
B1: B2: B3: B4:
00011001 10100101 10010011 01010101
lsr B1
ror B2 ;throw away 1 bit from B2
B1: B2: B3: B4:
00001100 11010010 10010011 01010101
lsr B1
ror B2
ror B3 ;throw away 1 bit from B3
B1: B2: B3: B4:
00000110 01101001 01001001 01010101
lsr B1
ror B2
ror B3
ror B4 ;throw away 1 bit from B4
B1: B2: B3: B4:
00000011 00110100 10100100 10101010
-----------------------------------------------------------
lsr B1 ;cc=5 (zp)
lsr B1 ;cc=5
ror B2 ;cc=5 (zp)
lsr B1 ;cc=5
ror B2 ;cc=5
ror B3 ;cc=5
lsr B1 ;cc=5
ror B2 ;cc=5
ror B3 ;cc=5
ror B4 ;cc=5
;-----
;cc=50
-----------------------------------------------------------
The routine only drops the first bit of the byte, not even an other bit (like the 2nd or 3rd) and this allready takes 50CC.
This can not bve the fastest way to do this... I'm missing something. So, does anyone know of a faster way to do this???
|
|
| |
chatGPZ
Registered: Dec 2001
Posts: 11386 |
maybe you should tell what the purpose of that algorithm is...there might be a better way to do it :) |
| |
V-12
Registered: Nov 2003
Posts: 206 |
extreme!
I guess that you need some simply AND, ORA, EOR routines... |
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
Quote: extreme!
I guess that you need some simply AND, ORA, EOR routines...
Would be quite nice.. :-D |
| |
Tch
Account closed
Registered: Sep 2004
Posts: 512 |
Hmm...Starwars scroller? |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
8 lookup tables, one for each bit you wish to remove?
new_byte=remove_bit4_table[old_byte];
Uses 8*256 bytes of memory. This ofcourse only works per byte and does not connect many bytes as in your example. |
| |
TNT
Account closed
Registered: Oct 2004
Posts: 189 |
Quote: 8 lookup tables, one for each bit you wish to remove?
new_byte=remove_bit4_table[old_byte];
Uses 8*256 bytes of memory. This ofcourse only works per byte and does not connect many bytes as in your example.
8*8*2 lookup tables, preshifted to all bit positions. With that you can OR bit patterns together. |
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
Yes, I've thought of Lookup tables too, but there must be a better way.
Maybe a combination of lookup tables and a formula of some kind? |
| |
Frantic
Registered: Mar 2003
Posts: 1648 |
Anway.. some lookup thingy could look like this:
b1:00110011
b2:10100101
b3:10010011
b4:01010101
ldx b1 ;3
lda shift4tab,x ;4* Fetch precalculated byte from table of 4-bit-shifted values.
sta b1 ;3
ldy b2 ;3
lda shift3tab,y ;4* Fetch precalculated byte from table of 3-bit-shifted values.
ora 3lsbmsb,x ;4* Use table to translate b1:XXXXX011 > 01100000, and then ORA it.
sta b2 ;3
ldx b3 ;3
lda shift2tab,x ;4* Fetch precalculated byte from table of 2-bit-shifted values.
ora 2lsbmsb,y ;4* Use table to translate b2:XXXXXX01 > 01000000, and then ORA it.
sta b3 ;3
lda b4 ;3
lsr ;2 Shift down one bit..
ora 1lsbmsb,x ;4* Use table to translate b3:XXXXXXX1 > 10000000, and then ORA it.
sta b4 ;3
It was just something I came up with rather quickly, so I might have overlooked something and I guess there are also the übersmart ways of coding this of coz ;), but it seems to me this would do what you wanted in 50 cycles also, but with the advantage that it could easily be modified to drop 2 or 3 or x bits per byte. (In 52 cycles though for more than one bit per byte. The manipulation code for byte4 would have to be changed to look like the code for byte2 and byte3 then of course). It uses only 6*256 (or 7*256 for more than one bit dropped per byte) bytes of lookup tables. Might be worth it? The method has the advantage that you can drop bits as you want by designing the translation tables for conversion of lsb bits to msb bits as you wish.
...or even a hybrid solution with less tables (but more dependent on the number of bits to be deleted; namely one in this case)?
ldx b1 ;3
lda shift4tab,x ;4* Fetch precalculated byte from table of 4-bit-shifted values.
sta b1 ;3
ldy b2 ;3
lda shift3tab,y ;4* Fetch precalculated byte from table of 3-bit-shifted values.
ora 3lsbmsb,x ;4* Use table to translate b1:XXXXX011 > 01100000, and then ORA it.
sta b2 ;3
lda b3 ;3
lsr ;2 ;shift 1...
lsr ;2 ;shift 1 again.. = 2 in total.
ora 2lsbmsb,y ;4* Use table to translate b2:XXXXXX01 > 01000000, and then ORA it.
sta b3 ;3
ror b4 ;3 Shift down one bit and make use of carry flag..
...in 41 cycles.
|
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
Yeah... Tables are prolly the best.
I want to use it for image resizing. I've seen demos enough which do that and I'm wondering if they all use tables...
Anyone knows this?
|
| |
Ben
Account closed
Registered: Feb 2003
Posts: 163 |
Quote: Yeah... Tables are prolly the best.
I want to use it for image resizing. I've seen demos enough which do that and I'm wondering if they all use tables...
Anyone knows this?
I reckon most are using a dy and dx technique you'd use for drawing a line from (x1,y1) to (x2,y2) so that you know when to draw/drop a particular row or column of bits.. |
| |
MRT
Account closed
Registered: Sep 2005
Posts: 149 |
???
ehr... huh???
What do you mean? and how does drawing a line help me with resizing a bitmap image in a fast manner? |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
MRT: this is done a hundred times less complicated in demos as you could ever imagine.
store your graphics into a charset. lets say your gfx is 32 characters wide. We need to store 4 versions of each char row. Each version is shifted 1 more pixel to the left.
now say we print out the chars normally.
x x x x
abcdabcdabcdabcd
each letter symbolizes a multicolor pixel, so one char is made up of abcd
now lets start the zoom:
x x x x x
abcdabcddabcdabcd
what happened ?
at the 3rd char we plotted a version thats shifted to the right 1 pixel, and so on afterwards.
hope you get the idea. as you have all versions of all chars shifted by 1-1 multi pixel, you can mix out zoomphases on a char basis very fast.
|
| |
Scout
Registered: Dec 2002
Posts: 1570 |
Quote: ???
ehr... huh???
What do you mean? and how does drawing a line help me with resizing a bitmap image in a fast manner?
Bresenham...that's the magic word!
---
-= Silicon Ltd. =-
http://forum.siliconlimited.com
Commodore 64 Scenemusic Podcast
http://8bitmayhem.blogspot.com/ |
| |
Oswald
Registered: Apr 2002
Posts: 5094 |
scout: no, thats metaballs |
