[CSDb] - User Forums - Getting 5-bit data

You are not logged in - nap

CSDb User Forums

Forums > C64 Coding > Getting 5-bit data

2010-12-02 14:30

Shadow
Account closed

Registered: Apr 2002
Posts: 355

Getting 5-bit data

I am working on a little something for a 6502-based system (no, not a C64, but the best coders hang here so... :D)

I have about 200 bytes to store some scrolltext in, and got the bright idea that storing the text as 5-bit data would yield me 320 characters of text instead!

The problem though is that when I started writing the code to actually "unpack" the 5-bit data, I ended up wasting more than the 120 bytes that I won...

Any bit-magician who can figure out a compact way of getting a 5-bit data, and without using self-modifying code (since this is a ROM-based system...)

I would ideally want to do something like this

	lda #$00
	sta SCROLLPOS
	...
	
	
Mainloop:	
	jsr Get5Bit
	...
	
	
Get5Bit:
        ldy SCROLLPOS
	lda scrolltext,y
	// Do magic
	// if necessary increase Y and store in SCROLLPOS	
	..
	rts
	
	
		
scrolltext:
		(5-bit data packed into 8-bit bytes here)

-edit-
Removed unnecessary ZP-inderection stuff

2010-12-02 15:01

JackAsser

Registered: Jun 2002
Posts: 2014

For Eye of the Beholder I use 5 bits per char aswell. Since 8*5 = 40 you can easily store 8 chars in 5 bytes. Now simply store bit0 bitpacked into byte0, bit1 bitpacked into byte1 etc.

To unpack a char in the 8 pre-fetched chars:
lda #0
ldy #4
:
rol zp,y
asl
dey
bpl :-

After you've depacked 8 chars you'll need to reload zp+0..zp+4 with new data from the string stream.

Depending on bitpacking you may need to change rol to ror etc but I hope you get the general idea.

/JackAsser

2010-12-02 15:17

Shadow
Account closed

Registered: Apr 2002
Posts: 355

Oh, that's a nice trick! Hadn't thought of the fact to divide the 5 bits into 5 different bytes like that.
Needs a bit more since you have to do special treatment since you have to move in new bytes every 8 chars.

Here's what I came up with to unpack from a "straight" 5-bit stream, ie. the data looking like this:

11111222 22333334 44445555 etc.

get5bits:
	lda #$00
	sta TMPBYTE1		
	ldx BITCOUNT
	ldy #$05
!loop:	
	cpx #$08
	bne !skip+
	sty TMPBYTE3
	ldy SCROLLPOS
	iny
	sty SCROLLPOS
	lda scrolltext,y
	sta TMPBYTE2
	ldy TMPBYTE3
	ldx #$00
!skip:
	asl TMPBYTE2
	rol TMPBYTE1
	inx
	dey
	bne !loop-
	stx BITCOUNT
	lda TMPBYTE1
	rts

Maybe a bit bloated at 44 bytes, but still I gained 50 characters over the original 8-bit-chars solution!

-edit- DOH! stupid mistakes, forgot that the asl/rol instructions can be used on mem aswell! Even more bytes saved, 40 bytes total now.

2010-12-02 15:39

JackAsser

Registered: Jun 2002
Posts: 2014

Quote: Oh, that's a nice trick! Hadn't thought of the fact to divide the 5 bits into 5 different bytes like that.
Needs a bit more since you have to do special treatment since you have to move in new bytes every 8 chars.

Here's what I came up with to unpack from a "straight" 5-bit stream, ie. the data looking like this:

11111222 22333334 44445555 etc.

get5bits: lda #$00 sta TMPBYTE1 ldx BITCOUNT ldy #$05 !loop: cpx #$08 bne !skip+ sty TMPBYTE3 ldy SCROLLPOS iny sty SCROLLPOS lda scrolltext,y sta TMPBYTE2 ldy TMPBYTE3 ldx #$00 !skip: asl TMPBYTE2 rol TMPBYTE1 inx dey bne !loop- stx BITCOUNT lda TMPBYTE1 rts

Maybe a bit bloated at 44 bytes, but still I gained 50 characters over the original 8-bit-chars solution!

-edit- DOH! stupid mistakes, forgot that the asl/rol instructions can be used on mem aswell! Even more bytes saved, 40 bytes total now.

get5bits:

dec CHARCOUNT
bpl :++
   ldy #4
   ldx scrolltextPos
   :
      lda scrolltext,x
      sta buffer,y
      inx
      dey
   bpl :-
   stx scrollTextPos
   lda #7
   sta CHARCOUNT
:

ldy #4
lda #0
:
   rol buffer,y
   asl
   dey
bpl :-

rts

31 bytes, written from the top of my head. Probably doesn't work... :P

Since you only address 200 bytes I let scrolltext pos be a zp-value holding the relative scroll position.

2010-12-02 15:58

Mace

Registered: May 2002
Posts: 1799

Quoting JackAsser

Now simply store bit0 bitpacked into byte0, bit1 bitpacked into byte1 etc.

This is what I came up with for some other effect too, some weeks ago.
I like these perpendicular directions of sudden insight :-)

2010-12-02 16:13

Shadow
Account closed

Registered: Apr 2002
Posts: 355

JackAsser, I'm too lazy to rewrite my scrolltext-packer to pack in the paralell-5-bit format to verify it, but looking at your code it looks right!
I only managed to get my "linear-5bit-depacker" code down to 38 bytes, but it will be good enough for my needs.
More scrolltext for everyone to read, YAY! :D

2010-12-03 12:54

TNT
Account closed

Registered: Oct 2004
Posts: 189

Init	sta	.ptr+1
	stx	.ptr+2
	lda	#$80
	sta	buf
	rts

Get5	lda	#8
.1	asl	buf
	bne	.3
	pha
.ptr	lda	$1234
	inc	.ptr+1
	bne	.2
	inc	.ptr+2
.2	rol
	sta	buf
	pla
.3	rol
	bcc	.1
	rts

Copy/paste code, you don't need "bne .2; inc .ptr+2" for 200 bytes of text.

2010-12-03 15:55

enthusi

Registered: May 2004
Posts: 677

TNT, yes you do.
If you use pointers like that (and not, i.e. ,X).
Imagine the text start at $10f0.

2010-12-03 16:32

Cruzer

Registered: Dec 2001
Posts: 1048

Nice little depacker, JackAsser! Got it to work with a few modifications (swapping asl/rol and changing addr-mode to asl,x since rol/asl,y isn't supported)...

	dec charCount
	bpl !+
	ldx #4
	ldy scrollTextPos
!loop:	lda scrollText,y
	sta buffer,x
	iny
	dex
	bpl !loop-
	sty scrollTextPos
	lda #7
	sta charCount
!:
	ldx #4
	lda #0
!loop:	asl buffer,x
 	rol
 	dex
 	bpl !loop-

I also did a KickAssembler macro for text packing...

.macro packText(str) {
	.for (var i=0; i<str.size(); i=i+8) {
		.for (var byteNo=0; byteNo<5; byteNo++) {
			.var res = 0
			.for (var bitNo=0; bitNo<8; bitNo++) {
				.var chrVal = 0 + str.charAt(i + 7 - bitNo)
				.var bitVal = chrVal & [$10 >> byteNo]
				.if (bitVal != 0) .eval bitVal = 1
				.eval res = res | [bitVal << bitNo]
			}
			.by res
		}
	}
}

Wonder how many chars it would be possible to sqeeze into a scroller in a 256b demo :)

2010-12-04 23:51

TNT
Account closed

Registered: Oct 2004
Posts: 189

enthusi, no you don't. If you're looking for shortest code you move your text so it doesn't cross page boundary ;) Even if you have to JMP over the text you still save 2 bytes compared against handling high byte of text pointer.

It's worth noting that my code uses only A after init which can help making code around it shorter. You can also set .ptr and buf at assembly time if there's no need to restart the text.

2010-12-05 02:42

White Flame

Registered: Sep 2002
Posts: 136

Here's my over-engineered take on it, with linear packed data, without holding an intermediate transform table.

The format is laid out like this:

00000111 11222223 33334444 45555566 66677777 00000111...

To get the first number on a byte boundary, you need to shift right 3 bits, then 6 bits for the next one, 1 for the next, etc:

3, 6, 1, 4, 7, 2, 5, 0, ....

This follows offset = (offset + 3) & 7. Whenever the offset to shift is greater than 3 bits, you're spanning a byte and need to increment your packed data pointer, rolling from the previous byte into the new current one. However, when going from byte 7 back to byte 0, you also need to increment the pointer 1 byte even though you're never using a 2-byte number. So I say when the shift offset is greater _or equal_ to 3, perform the 2-byte shift which will cover that case.

If you're looking at the current packed byte (.A) and a destructible copy of the previous one (prev) you can make a jump table into this:

pos4:
 lsr prev
 ror
pos1:
 lsr prev
 ror
pos6:
 lsr prev
 ror
pos3:
 lsr prev
 ror
pos0:
 lsr
pos5:
 lsr
pos2:
 lsr
pos7:
 and #%00011111
 rts

For posN, N corresponds to the number in the 00000111 11222223 ...format.

That seems like it could get pretty big, though. Initial ROM-compatible attempts (curse your lack of selfmod branch instructions! ;) ) were over 40 bytes, too. To try to shorten the unrolled code into a loop seems to still take 40 bytes, 38 if you can eliminate the initial ldy #$00:

.zeropage

ptr5bit:  .res 2 ; pointer the byte _before_ your 5-bit compressed data, no page crossings.
                 ; However, initializing this to $c0ff will start reading from $c000
offset:   .res 1 ; initialize to 0 in your setup
prev:     .res 1 ; no init needed, holds the previous byte we're shifting from

.code

get5bit:
 ldy #0     ; seek to eliminate this from the caller
 lda offset
 adc #$03
 and #$07
 sta offset
 beq :+++   ; if offset = 0, skip all the shifting
 tax
 cpx #3     ; if offset >= 3, then we're spanning bytes (the =3 case makes sure we inc between spans)
 lda (zp),y
 bcc :++    ; not spanning bytes, just LSR the current byte

 sta prev   ; shove the current byte into prev for byte-spanning
 inc zp
 lda (zp),y
: lsr prev  ; shift from the prior byte as much as needed
  ror
  dex
  cpx #2
 bne :-
: lsr       ; shift up to the last 3 bytes within the current byte
  dex
 bpl :-
 and #%00011111
:rts

So some random overly clever thoughts about different directions you could try.

EDIT: looking at it again, there is a bug when offset = 3, where it'll shift 1 bit too much, so just take this as ideas to look into, not as a working implementation. Again, it's trying to mash in more complexity than this solution really needs, but it's fun to try. :)

... 10 posts hidden. Click here to view all posts....

Previous - 1 | 2 - Next

Refresh

Subscribe to this thread: