Suggestion for implementing : vector<uint12_t>

[mathieu]

Hello,

I would like to implement a 'vector<uint12_t>' structure, where
uint12_t is a 12bits unsigned integer. AFAIK I need to completely
duplicate the implementation of let say vector<bool> and adapt the
code to suit my need. I cannot find out if there is way for me to
reuse my vendor std::vector ?

Suggestions welcome,
Mathieu

#include <iostream>

int main(int, char *[])
{
// Let's pretend for a moment those are 6 uint12_t values:
// 0x012 0x345 0x678 0x9ab
const unsigned char in[] = { 0x01, 0x23, 0x45, 0x67, 0x89, 0xab };
// store them on 16bits:
// 0x0012 0x0345 0x0678 0x09ab
const unsigned int Nin = sizeof(in); // sizeof(unsigned char) == 1
const unsigned int Nout = Nin * 2 / 3;
unsigned short out[Nout];
const unsigned char *p_in = in;
for(unsigned short *p_out = out; p_out != out + Nout; /*p_out+=2*/)
{
const unsigned char b0 = *p_in++;
const unsigned char b1 = *p_in++;
const unsigned char b2 = *p_in++;
*p_out++ = ((b0 >> 4) << 8) + ((b0 & 0x0f) << 4) + (b1 >> 4) ;
*p_out++ = ((b1 & 0x0f) << 8) + ((b2 >> 4) << 4) + (b2 & 0x0f);
}

for(unsigned int i=0; i < Nout; ++i)
std::cout << std::hex << out << " ";
std::cout << std::endl;

return 0;
}

 

[Kai-Uwe Bux]

Hello,

I would like to implement a 'vector<uint12_t>' structure, where
uint12_t is a 12bits unsigned integer. AFAIK I need to completely
duplicate the implementation of let say vector<bool> and adapt the
code to suit my need. I cannot find out if there is way for me to
reuse my vendor std::vector ?

I do not yet understand the requirements. Thus, let me just as two
questions:

a) Do you have a uint12_t, or would that have to be implemented, too?

b) If you do have uint12_t already, what is wrong with
std::vector<uint12_t>?


Best

Kai-Uwe Bux

 

[Kaz Kylheku]

I do not yet understand the requirements. Thus, let me just as two
questions:

a) Do you have a uint12_t, or would that have to be implemented, too?

b) If you do have uint12_t already, what is wrong with
std::vector<uint12_t>?

Probably the same thing that is wrong with a naively implemented
vector<bool>, namely taking up sizeof (bool) storage per element.

A uint12_t, if it existed, would not provide packed storage in arrays,
due to the need to align each uint12_t to an addressable boundary.

// wastes at least four bits in arrays:
struct uint12_t {
unsigned value : 12;
};

 

[Kai-Uwe Bux]

Probably the same thing that is wrong with a naively implemented
vector<bool>, namely taking up sizeof (bool) storage per element.

A uint12_t, if it existed, would not provide packed storage in arrays,
due to the need to align each uint12_t to an addressable boundary.

// wastes at least four bits in arrays:
struct uint12_t {
unsigned value : 12;
};

If it is the 25% overhead, I would argue that it's not worth the effort
unless measurement shows that space consumption is innacceptable. Keep in
mind that realizing a specialization vector<uint12_t> is a tradeoff: you
trade time (for both the programmer and the CPU) for space. Unless there is
a compelling reason not to, I would go with the simpler version.

On the other hand, I could imagine that there is a need for the bits to be
contiguous in memory, e.g., if this is part of doing some fancy graphics
stuff. In that case, there would be no choice.

Since those issues are not clear, I just like the OP to clarify.


Best

Kai-Uwe Bux

 

[mathieu]

If it is the 25% overhead, I would argue that it's not worth the effort
unless measurement shows that space consumption is innacceptable. Keep in
mind that realizing a specialization vector<uint12_t> is a tradeoff: you
trade time (for both the programmer and the CPU) for space. Unless there is
a compelling reason not to, I would go with the simpler version.

On the other hand, I could imagine that there is a need for the bits to be
contiguous in memory, e.g., if this is part of doing some fancy graphics
stuff. In that case, there would be no choice.

Since those issues are not clear, I just like the OP to clarify.

Hi,

Sorry for the confusion. My goal is to provide a std::vector-like
interface to a 12bits unsigned int array (packed storage), see small
example attached to my first post. It's really the same problematic as
vector<bool>. In the end I should be able to write transparently.

std::vector<uint12_t> v1 =
std::vector<uint16_t> v2 =
std::copy(v1.begin(), v1.end(), v2.begin());

Actually in the end I need to support multiple 12bits input data,
such as (*). So again I am looking to provide an *interface* for my
users, so they can use all functions from <algorithm> (std::fill,
std::transform...) on those different vectors. I have started
something like:


typedef uint16_t uint12_t;
// TODO: provide UINT12_MAX

template <typename TAlloc>
class vector<uint12_t, TAlloc>
{
std::vector<char, TAlloc> internals;
public:
// copy everything from: http://www.sgi.com/tech/stl/Vector.html
};


Thanks,
-Mathieu
(*)
Bits Allocated = 16
Bits Stored = 12
High Bit = 11

|<------------------ pixel -----------------

|

______________ ______________ ______________
______________
|XXXXXXXXXXXXXX| | |
|
|______________|______________|______________|
______________|
15 12 11 8 7 4 3
0

---------------------------

Bits Allocated = 16
Bits Stored = 12
High Bit = 15

|<------------------ pixel ----------------->|
______________ ______________ ______________
______________
| | | |
XXXXXXXXXXXXXX|
|______________|______________|______________|
______________|
15 12 11 8 7 4 3
0

---------------------------

Bits Allocated = 12
Bits Stored = 12
High Bit = 11

------ 2 ----->|<------------------ pixel 1 ---------------

|

______________ ______________ ______________
______________
| | | |
|
|______________|______________|______________|
______________|
15 12 11 8 7 4 3
0


-------------- 3 ------------>|<------------ 2
--------------
______________ ______________ ______________
______________
| | | |
|
|______________|______________|______________|
______________|
15 12 11 8 7 4 3
0


|<------------------ pixel 4 --------------->|<----- 3
------
______________ ______________ ______________
______________
| | | |
|
|______________|______________|______________|
______________|
15 12 11 8 7 4 3
0

See my previous post for implementation:
[ template and bit-field]
http://groups.google.com/group/comp.lang.c++/browse_thread/thread/93d7be13711933cb

 

[Alf P. Steinbach]

* mathieu:

My goal is to provide a std::vector-like
interface to a 12bits unsigned int array (packed storage)

Pack and unpack.

 

[mathieu]

* mathieu:




Pack and unpack.

The whole idea is that I am trying to use template programming so that
copying a std::vector<uint12_t> into a std::vector<uint12_t> is simply
a memcpy. I should only resolve to pack/unpack when my type are
different (copying into vector<uint16_t>).
I do not believe this is a hard task (simply very tedious), but in the
end it should be extremely flexible. I thought I could reuse some
component (STL, boost) to avoid reinventing the wheel.

-Mathieu

 

[Dave Rahardja]

The whole idea is that I am trying to use template programming so that
copying a std::vector<uint12_t> into a std::vector<uint12_t> is simply
a memcpy. I should only resolve to pack/unpack when my type are
different (copying into vector<uint16_t>).
I do not believe this is a hard task (simply very tedious), but in the
end it should be extremely flexible. I thought I could reuse some
component (STL, boost) to avoid reinventing the wheel.

-Mathieu

You could create a facade: specialize std::vector for your type, define it as
a class that implements the parts of the std::vector interface you're
interested in, and use a std::vector<unsigned char> internally for
implementation. Your iterators will then contain the necessary index increment
and decrement logic to keep the view consistent.

-dr

 

[peter koch]

Hello,

I would like to implement a 'vector<uint12_t>' structure, where
uint12_t is a 12bits unsigned integer. AFAIK I need to completely
duplicate the implementation of let say vector<bool> and adapt the
code to suit my need. I cannot find out if there is way for me to
reuse my vendor std::vector ?

Suggestions welcome,
Mathieu

[snip]
You will not be able to reuse your vendors std::vector except in the
unlikely event that you happen to be in an environment where char has
12 bits. Thus, there is no way out but to create your own container
type (perhaps having a std::vector<char> for storage, but in exactly
your case, I do not believe that it would give you much).
I believe you also need to implement your own std::copy specialisation
if you must optimise copying between two uint_12 containers.

/Peter

 

[s5n]

The whole idea is that I am trying to use template programming so that
copying a std::vector<uint12_t> into a std::vector<uint12_t> is simply
a memcpy. I should only resolve to pack/unpack when my type are

Keep in mind that memcpy works on BYTE addresses and boundaries, not
BIT boundaries, so you would have misalignment problems when using
memcpy. From the memcpy man page:

void *memcpy(void *dest, const void *src, size_t n);

The memcpy() function copies n bytes from memory area src
to memory area dest.

The key word there is "bytes".

 

[mathieu]

Keep in mind that memcpy works on BYTE addresses and boundaries, not
BIT boundaries, so you would have misalignment problems when using
memcpy. From the memcpy man page:

void *memcpy(void *dest, const void *src, size_t n);

The memcpy() function copies n bytes from memory area src
to memory area dest.

The key word there is "bytes".

Very good point ! I will need an additional concept of 'size' is
multiple of two.

-M

 

[mathieu]

I would like to implement a 'vector<uint12_t>' structure, where
uint12_t is a 12bits unsigned integer. AFAIK I need to completely
duplicate the implementation of let say vector<bool> and adapt the
code to suit my need. I cannot find out if there is way for me to
reuse my vendor std::vector ?

Suggestions welcome,
Mathieu

[snip]
You will not be able to reuse your vendors std::vector except in the
unlikely event that you happen to be in an environment where char has
12 bits. Thus, there is no way out but to create your own container
type (perhaps having a std::vector<char> for storage, but in exactly
your case, I do not believe that it would give you much).
I believe you also need to implement your own std::copy specialisation
if you must optimise copying between two uint_12 containers.

Thanks, that's all I needed to know.

-M