| | 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 |
|
| | 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
|
| | 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. |
| | 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.
|
| | Mace
Registered: May 2002
Posts: 1799 |
Quoting JackAsserNow 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 :-) |
| | 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
|
| | 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. |
| | 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. |
| | 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 :)
|
| | 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. |
| | 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. :) |
| | Shadow
Account closed
Registered: Apr 2002
Posts: 355 |
Here's my final version that I used in the code:
get5bits:
lda #$00
sta TMPBYTE1
ldy #$05
!loop:
lda BITCOUNT
bne !skip+
ldx SCROLLPOS
lda scrolltext,x
sta TMPBYTE2
inx
stx SCROLLPOS
lda #$08
sta BITCOUNT
!skip:
asl TMPBYTE2
rol TMPBYTE1
dec BITCOUNT
dey
bne !loop-
lda TMPBYTE1
rts
36 bytes if I counted it correctly. |
| | JackAsser
Registered: Jun 2002
Posts: 2014 |
get5bits:
lda #$00
ldy #$05
!loop:
asl TMPBYTE2
rol
dec BITCOUNT
bne !skip+
pha
ldx SCROLLPOS
lda scrolltext,x
sta TMPBYTE2
inc SCROLLPOS
lda #$08
sta BITCOUNT
pla
!skip:
dey
bne !loop-
rts
30 bytes... linear bit order. |
| | JackAsser
Registered: Jun 2002
Posts: 2014 |
I'm perhaps a bit too tired now but this might work:
get5bits:
lda #%00001000
!loop:
asl TMPBYTE2
dec BITCOUNT
bne !skip+
ldx SCROLLPOS
ldy scrolltext,x
sty TMPBYTE2
inc SCROLLPOS
ldy #$08
sty BITCOUNT
!skip:
rol
bcc !loop-
rts
25 bytes.
|
| | Slammer
Registered: Feb 2004
Posts: 416 |
15 bytes : 280 Chars Scroll |
| | terric
Account closed
Registered: Feb 2009
Posts: 47 |
Well, now you got me tempted and also you got my brain going for some coding.(Really should study) ;) I did a byterunner attempt, it does benefit from languages using same charachters twice or more, and some spaces in scroller does shrink to a nice size. ;) |
| | enthusi
Registered: May 2004
Posts: 677 |
well, so far the codes can handle generic texts.
Not sure if much could be safed if you know the text in advance. Surely for 1024KB but in 256B? I have my doubts :) |
| | WVL
Registered: Mar 2002
Posts: 902 |
Well.. how short can you write a huffman decoder? :) |
| | Mace
Registered: May 2002
Posts: 1799 |
enthusi, WVL: my thoughts exactly... |
| | Fresh
Registered: Jan 2005
Posts: 101 |
@Slammer
First of all nice routine!
I managed to get room for 8 more characters to play with for a total of 288.
I'm too lazy to regenerate the encoded text so I've only added some dots.
(Updated on 9/12: now 296 chars and free color choice)
*= $0326
packedbytes equ $B9
.word start
.word $F6ED
data=*-1
.byte $5D,$B5,$25,$25,$D5,$DB,$FF,$79,$5B,$FD,$21,$3B,$51,$85,$3B,$E7
.byte $77,$77,$3B,$23,$FF,$CD,$BB,$BB,$CF,$57,$55,$DF,$77,$55,$A9,$FF
.byte $E7,$67,$31,$A1,$ED,$09,$1B,$E5,$F7,$FF,$F5,$D5,$F7,$CD,$9F,$69
.byte $49,$59,$65,$21,$9B,$01,$67,$BB,$3F,$4D,$A5,$91,$29,$6E,$03,$F3
.byte $19,$9B,$69,$AD,$A9,$0B,$3F,$12,$1B,$1B,$3D,$57,$F7,$D7,$4F,$1F
.byte $8F,$2E,$41,$11,$AB,$6D,$FE,$AB,$A7,$31,$63,$6E,$CD,$57,$71,$95
.byte $74,$47,$0C,$F4,$91,$84,$FB,$82,$84,$CC,$29,$E9,$D9,$8C,$79,$4B
.byte $75,$61,$41,$1E,$33,$BB,$3E,$16,$F3,$F2,$45,$61,$44,$3C,$28,$7A
.byte $B9,$2C,$EB,$CC,$83,$83,$E0,$94,$75,$FD,$F6,$14,$7C,$12,$26,$07
.byte $48,$AA,$ED,$F4,$A6,$E1,$FF,$E7,$4F,$4F,$D7,$75,$D4,$88,$80,$29
.byte $5A,$AA,$FF,$72,$02,$80,$2E,$99,$89,$96,$D0,$58,$F9,$C3,$C8,$FF
.byte $00,$FF,$FF,$FF,$FF,$00,$FF,$FF,$FF
start
LDX #packedbytes
SEI
loop
LDA #$07 ; #$87/#$07 slow/fast
waitr
CMP $D012
BNE waitr
SBC #$01
AND #$87
STA $d016
BCS waitr ; BMI/BCS slow/fast
copychar
LDA $05E1,Y
STA $05E0,Y
LDA #$0F ; Selectable color
STA $D9E0,Y
INY
BNE copychar
LDA #$08
inner
ASL data,x
BCC zero
INC data,x
zero
ROL
DEX
BNE skipreset
LDX #packedbytes
skipreset
BCC inner
ADC #$00
CMP #$1E
BNE skipdot
LDA #$2E
STA $D021
skipdot
STA $0607
BNE loop
|
| | Shadow
Account closed
Registered: Apr 2002
Posts: 355 |
Nice to see that a simple question can turn into a good old coders competition! :)
Btw. here is the resulting product for which I originally asked.
Atari VCS, 128 bytes RAM, 4kB ROM cartridge... |
|
