Splitting An 8bit Variable Into Two 4bit.

[Khatoblepas]

I'm trying to code a sprite loader (of my own invention), and I want to store my sprites in 4bit, to conserve space (half as much as 8bit. If I had 10mb of sprites, it would equate to 5mb of 4bit sprites) and stop wastage... but I still have to think about engine efficiency.

Is it practical to split up an 8bit variable into two, effectively having the upper and lower halves in different variables?

And if so, how do you do it? I know you can split up a 16bit variable into an 8bit variable by using inline assembler to move the higher and lower bytes into different places:

//This x86 ASM is probably very, very wrong. Gonna have to brush up on my inline ASM!
unsigned short var = 32721;
unsigned char varlower;
unsigned char varupper;
asm {
mov a, var;Move var into register a
mov varupper, ah;Move upper byte into variable
mov varlower, al; Same with the lower byte.
}

But I'm stumped as to how to split it further efficiently.

Any suggestions? o.o

 

[shrubberyrobbery]

interesting idea!
by "4-bit sprite" you are talking about a sprite with a 16-colour palette?

i guess you would have to do some bitwise operations to combine/separate the variables, to be able to store two into a byte.

i'm not up on asm but in c++ you would have to do something like:

char a; // first 4-bit var
char b; // second 4-bit var

char c; // one byte of storage to hold a and b

// to STORE a and b into c, a into lower half and b into upper half
// remove uppermost bits of a
// and bitshift b
c = (a && 15) || (b>>4);

// to RETRIVE a from c
a = c && 15;

// to RETRIVE b from c
b = c << 4;

something like that!

the trouble is, you would have to expand the sprites out again every time you wanted to copy them to video ram. it could get complicated!

 

[slygamer]

I think you might have got those shifts the wrong way around, and you want a bitwise or, not a logical or, to join the nybbles (half a byte is a nybble) together.

// Store a and b into c
c = ((a & 0xF) << 4) | (b & 0xF);

// Extract a and b from c
a = (c >> 4) & 0xF;
b = c & 0xF;

I can see this might be helpful, but you would have to expand the sprites to at least 8bit colour before blitting to the screen. This would mean either using a software-only blitter (versatile, but slower), preprocess the sprite into video memory and then use the hardware blitter (may as well just use the software blitter), or use the FIFO of the hardware blitter (faster than a software blitter, but not as flexible).

I see you could have 16 palettes of 16 colours in a 256 colour palette. When you expand the sprites to blit onto the screen, you keep the lower nybble and add the palette bank in the upper nybble.

// This sprite will use palette bank 10
unsigned char bank = 10 << 4;

// Blit first pixel
*screen++ = ((c >> 4) & 0xF) | bank;
// Blit second pixel
*screen++ = (c & 0xF) | bank;

 

[Khatoblepas]

Interesting! It's so simple, why didn't I think of it? Thank you for your help. I never would have realised that bitwise functions were so useful for doing this.

I'll have a look when I get home if on-the-fly conversion would work. I was thinking of using 256 colours with sprites that are 16 colour, so that each sprite would have a 256byte palette of 16 subpalettes. Useful in making sprites different colours (RPG Enemies on the SNES, anyone?). The sprite format itself would be very, very simple, with no compression to ease speed (and my brain. I like programming from the bottom up better than precompiled libraries, and compression is just so fiddly to deal with. Though, for sound samples, I could deltaencode+RLE them.). Maybe the on-the-fly could be implimented for games and programs only using 16 colours? Probably already has, but now I can use it too! =D

I can see this might be helpful, but you would have to expand the sprites to at least 8bit colour before blitting to the screen. This would mean either using a software-only blitter (versatile, but slower), preprocess the sprite into video memory and then use the hardware blitter (may as well just use the software blitter), or use the FIFO of the hardware blitter (faster than a software blitter, but not as flexible).

FIFO of the hardware blitter? What's that? I've never really worked with something that has hardware graphic capabilities. I always used to access it all in software. =x One of the failings of learning on an old PC.


Oh, and in x86 ASM, I think the function would go something like this:

//YAY for masochism!
byte upper;
byte lower;
byte source = 255;
asm {
mov source, ah;Move the variable we need into the higher register (for upper nybble).
mov source, al;Move the variable we need into the lower register. (for lower nybble)
shr 4, ah;Shift higher register right four bytes.
andl ah, 0xF; 'Logical and' 16h on higher register
andl al, 0xF; 'Logical and' 16h on lower register
mov al, lower;Moves the result of h.reg back into a C variable.
mov ah, upper;Moves the result of h.reg back into a C variable.
}

Or something like that, anyway. I think I've still got the syntax wrong. It's simple, so converting to ARM assembler shouldn't be too difficult. No specific registers (al and ah turn into r0 and r1 =P)

 

[Radek]

I think you might have got those shifts the wrong way around, and you want a bitwise or, not a logical or, to join the nybbles (half a byte is a nybble) together.

// Store a and b into c
c = ((a & 0xF) << 4) | (b & 0xF);

// Extract a and b from c
a = (c >> 4) & 0xF;
b = c & 0xF;

I can see this might be helpful, but you would have to expand the sprites to at least 8bit colour before blitting to the screen. This would mean either using a software-only blitter (versatile, but slower), preprocess the sprite into video memory and then use the hardware blitter (may as well just use the software blitter), or use the FIFO of the hardware blitter (faster than a software blitter, but not as flexible).

I see you could have 16 palettes of 16 colours in a 256 colour palette. When you expand the sprites to blit onto the screen, you keep the lower nybble and add the palette bank in the upper nybble.

// This sprite will use palette bank 10
unsigned char bank = 10 << 4;

// Blit first pixel
*screen++ = ((c >> 4) & 0xF) | bank;
// Blit second pixel
*screen++ = (c & 0xF) | bank;

​

I would pack two 4 bit pixel serially in a byte: |3210|3210|
and then use a table with 256 postitions. This byte would be an index for the table and its values could encode two pixels at once. Assuming output is 16bpp the table size is only 1024 bytes so it'd be fit in a cache easily. And it will have benefit of using whole 32bits of bus memory. Should be quick.

 

[gfoot]

You could use the hardware blitter, if you encode two pixels vertically rather than two pixels horizontally. I think it supports palette expansion, i.e. you can specify 8bpp source and 16bpp destination. If you also double the output stride value, you can use two blits with different palettes to write the entire sprite.

I don't know anything about blitting between depths though, other than that the registers are there. It could be really slow.

 

[the_Diabologic]

meh, quite ineffective as there are no native 4bit types in C
also, in arm asm it would look something like this:

@ r0 is the input
@ r1 will contain the upper, r0 the lower nibble
mov r1, r0, lsr #4
and r0, r0, #15

in C like

void split_nibbles(char in, char *upper, char *lower)
{
  *upper=in>>4;
  *lower=in&15;
}

inline arm asm in C iirc:

char in, upper, lower;
asm volatile(
"mov %[H], %[IN], lsr #4\n"
"and %[L], %[IN], #15\n"
:[H]"r"(upper), [L]"r"(lower)
:[IN]"r"(in)
:);

(dunno, wether this will really work)

blitting will be hell, tho =P

 

[gfoot]

If you want to software blit to an 8bpp surface, I'd not store adjacent pixels in adjacent nibbles - store them in adjacent bytes instead, and fill the remaining nibbles with a different part of the sprite. Then you can do a tight loop blitting the low nibbles for the first half of the sprite, then a second loop, identical but for a 4-bit right shift on the loads, to blit the second half of the sprite.

Palette selection is really easy and fast then. If the pixels encoded are ABCDEFGH, ABCD are from the first half and EFGH are from the second half, then store them like this:

HHHHDDDD GGGGCCCC FFFFBBBB EEEEAAAA

Then you can extract the first four pixels all at once, writing the top nibbles of each byte with a palette prefix for the sprite you're blitting:

// Input word in r0
// Palette index in all the high nibbles of r1
and r0, r0, #0x0f0f0f0f
orr r0, r0, r1

and write to the hardware blitter's FIFO (or to video memory if you want it to be slow). Do a tight loop like that to blit half your sprite, and store the second half of the sprite in the high nibbles; then you have another tight loop which has the four bit right shift suffix on its load operations, with the same blitting code as above.

You could actually store the next four pixels to the right of the previous four in the high nibbles, and use a longer loop to do the blit - you'd only need to read the source data once this way...

// Input word in r0 describing pixels ABCDEFGH in bits:
//     HHHHDDDD GGGGCCCC FFFFBBBB EEEEAAAA
// Palette selector in high nibbles of r1:
//     PPPP0000 PPPP0000 PPPP0000 PPPP0000
and r2, r0, #0x0f0f0f0f
orr r2, r2, r1
and r3, r0, #0x0f0f0f0f, lsr #4
orr r3, r3, r1
// .. and write r2 followed by r3 as 32-bit words

Excuse my lousy ARM assembler - I only have a passing familiarity with it, so it might not be correct even for the simple example I gave! I think the principle is right though.

I'm actually trying to remember whether the hardware blitter supports 4bpp. It does support something below 8bpp - I think it's 1bpp though, and not for destination, so you can't even use that to write partial bytes.

 

[theoddbot]

struct twopixels
{
    unsigned first:4;
    unsigned second:4;
};

 

[slygamer]

FIFO of the hardware blitter? What's that? I've never really worked with something that has hardware graphic capabilities. I always used to access it all in software. =x One of the failings of learning on an old PC.

​

If you look at some of the other posts about the hardware blitter, you will find the code to do a blit from video memory to video memory. But another way to do a blit is to tell the hardware that the source data is coming from the FIFO (first in, first out). The CPU writes to the FIFO and the blitter pulls the data out of the FIFO and writes it to the destination. This allows blits from system memory (the first 32MB that Linux manages) rather than video memory (the second 32MB that Linux doesn't know about).