most memory efficient way to store an 8 bit color palette?

[Cube_]

Long time no see, been too busy hacking at my game to actually bother posting (been lurking every now and then though), anyway my issue is this:
I am working under a self imposed restraint of not using more than 1024mb of ram (worst case), I'm nearing that limit (again, worst case) and I have yet to implement my coloring system, from a design perspective it's simple.
no textures just primitive colors, specifically 8 bits of them (might increase to 12 or 16 bits later, I know for a fact that I'm not going to use more than that) as for why I do this? aesthetic reasons, I have a plan.
However I'm not quite sure as how to implement it, the naive solution I can think of is to define a struct, bitmask an 8 bit bitfield and pick a value from the struct based on what bits are toggled, the struct itself would contain RGB values such as 0xAA2B33

However this sounds awfully inefficient, perhaps handling colors as 0xA25 would work, I only need 255 colors anyway (at least for my initial design, I'll probably have to extend that to a 12 bit color space or maybe even a 16 bit color space)

anyway, I'm rambling, does anyone have a suggestion as to how I can improve this naive approach? (on an unrelated note I still need to figure out how to cache large sets of volatile data, preferably using instancing so I can save draw calls... perhaps I should add a memory compression routine while at it)

Oh and as for what I'm using the palette for, I'm coloring my world (made of voxels, lots of them, each voxel will have a primitive color)

[hendu]

There is no such way. An 8-bit index takes the same space as a 8-bit value.

[Cube_]

I know that much, I just don't have a clue as to how I'd implement an 8-bit table of colors that isn't riddled with horrible amounts of overhead (theoretically I should be able to have a table of 255 colors and an 8-bit value holding the color id in question, however how to implement that is the question. Excuse me while I go and get my rubber duck, I'll figure this out some way or another...)

[ent1ty]

Well? I think char should be an 8 bit value (theoretically, I guess it's implemented as a 32 bit one these days anyway?), so you can typedef your own type and use that. As for performance though, I doubt it's really necessary. Surprisingly, 32 bit processors are pretty good at handling 32 bit values and the memory overhead really isn't something to think about, even with voxels in question. A million 32-bit encoded color values will take up one megabyte of memory.
Also, when reading data from ram, the processor tends to read in at least 4 byte blocks, probably even more, because it's quite likely you will request more data from the vicinity of the first read. When writing to ram, it can't write 8 bits at a time and might end up reading the surrounding data just to know what to write back in after the initial 8 bits that were originally requested. So it might actually end up being (unnoticeably) slower. But this is purely implementation-specific and i'm not even sure I'm remembering this 100% correctly

[REDDemon]

Do you mean using a CPU or a GPU palette?
CPU:
since you use a 255 colors palette that shoould fit entirely in L1 cache so you don't have to warry about performance (there's one indirection ok, but indirection are costly only when cache misses), A quick test shows I'm just bandwith (BUS) limited on my old core duo.

It is possible that you can encode your images using RLE, (so THIS color for following 30 pixels and you saved 28 bytes ) if you just need to stream images without ability to random access single pixels this could be a great win.

GPU:
Depends how you implement that. If you are going to use a 8 bit texture then it's ok, you just need another "paletteTexture" that is looked up from the 8 bit texture But you should note that you must always use texelfecth or no mipmapping at all wich is more costly unless you are rendering 2d stuff.

If you use 8 bit values in vertices (you still need a palette texture, this time you use texelfecth inside vertex/geometry shader) remember that GPU allocates 32 bits anyway at least for vertices, so you are saving only on client memory not on videocard memory (unless you are using remaining 24 bits for something else)

Note that I really like GPU palettes: allows more control on the world without ever touching other assets, and save a LOT of bandwith wich can turn in performance advantage (if you are bandwith limited of course).

Other possibilities?
Use uniforms as palette. => especially usefull if you have only a bunch of colors.

[Cube_]

I'd probably have to do it on CPU as I'm intending to support multiple platforms with differing GPUs (hence the solution for on the gpu is likely to differ in performance characteristics rather widely)

RLE'ing the texture rendered out from the color palette result once it's applied to the world isn't a bad idea (I was thinking about LZO compression in memory but that might be overkill), as for GPU palettes, I'm not really bandwidth limited as much as draw call limited (around 300-400 draw calls per second for my more limited platform choices, that should be doable if I handle myself carefully)

[REDDemon]

I think best and simplest idea is to use RLE as encoding, and Google's Snappy for compression. go for something heavier than snappy (lzo, gzip) only if snappy is not enough. I never had problems with it. It sshould decompress and decode as fast as light. If you need random access inside texture you could also save pointers(indices) to "lineBegins" inside RLE's array so that instead scannin the whole image, you just scan a single line. (a extra u8/u16 for every line/row and you are done).

I already done something similiar and works pretty well