Log inRegister an accountBrowse CSDbHelp & documentationFacts & StatisticsThe forumsAvailable RSS-feeds on CSDbSupport CSDb Commodore 64 Scene Database
You are not logged in - nap
CSDb User Forums


Forums > C64 Coding > Dropping bits
2005-11-01 14:57
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???
2005-11-01 16:10
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 :)
2005-11-01 17:30
V-12

Registered: Nov 2003
Posts: 206
extreme!
I guess that you need some simply AND, ORA, EOR routines...
2005-11-01 17:35
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
2005-11-01 17:37
Tch
Account closed

Registered: Sep 2004
Posts: 512
Hmm...Starwars scroller?
2005-11-01 18:53
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.
2005-11-01 20:55
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.
2005-11-02 07:43
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?
2005-11-02 08:10
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.
2005-11-08 09:55
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?
2005-11-08 09:58
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..
 
... 4 posts hidden. Click here to view all posts....
 
Previous - 1 | 2 - Next
RefreshSubscribe to this thread:

You need to be logged in to post in the forum.

Search the forum:
Search   for   in  
All times are CET.
Search CSDb
Advanced
Users Online
tlr
Dr.Science/Atlantis
DeMOSic/MS^LSD^ONS
MCM/ONSLAUGHT
Guests online: 124
Top Demos
1 Next Level  (9.7)
2 13:37  (9.7)
3 Mojo  (9.7)
4 Coma Light 13  (9.6)
5 The Demo Coder  (9.6)
6 Edge of Disgrace  (9.6)
7 What Is The Matrix 2  (9.6)
8 Uncensored  (9.6)
9 Comaland 100%  (9.6)
10 Wonderland XIV  (9.6)
Top onefile Demos
1 No Listen  (9.7)
2 Layers  (9.6)
3 Cubic Dream  (9.6)
4 Party Elk 2  (9.6)
5 Copper Booze  (9.6)
6 X-Mas Demo 2024  (9.5)
7 Dawnfall V1.1  (9.5)
8 Rainbow Connection  (9.5)
9 Onscreen 5k  (9.5)
10 Morph  (9.5)
Top Groups
1 Performers  (9.3)
2 Booze Design  (9.3)
3 Oxyron  (9.3)
4 Censor Design  (9.3)
5 Triad  (9.3)
Top Musicians
1 Rob Hubbard  (9.7)
2 Mutetus  (9.7)
3 Jeroen Tel  (9.7)
4 Linus  (9.6)
5 Stinsen  (9.6)

Home - Disclaimer
Copyright © No Name 2001-2024
Page generated in: 0.074 sec.