Suggestion for implementing : vector<uint12_t>

Discussion in 'C++' started by mathieu, Feb 19, 2007.

  1. mathieu

    mathieu Guest

    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;
    }
     
    mathieu, Feb 19, 2007
    #1
    1. Advertising

  2. mathieu

    Kai-Uwe Bux Guest

    mathieu wrote:

    > 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
     
    Kai-Uwe Bux, Feb 19, 2007
    #2
    1. Advertising

  3. mathieu

    Kaz Kylheku Guest

    On Feb 18, 4:26 pm, Kai-Uwe Bux <> wrote:
    > mathieu wrote:
    > > 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>?


    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;
    };
     
    Kaz Kylheku, Feb 19, 2007
    #3
  4. mathieu

    Kai-Uwe Bux Guest

    Kaz Kylheku wrote:

    > On Feb 18, 4:26 pm, Kai-Uwe Bux <> wrote:
    >> mathieu wrote:
    >> > 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>?

    >
    > 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
     
    Kai-Uwe Bux, Feb 19, 2007
    #4
  5. mathieu

    mathieu Guest

    On Feb 18, 8:34 pm, Kai-Uwe Bux <> wrote:
    > Kaz Kylheku wrote:
    > > On Feb 18, 4:26 pm, Kai-Uwe Bux <> wrote:
    > >> mathieu wrote:
    > >> > 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>?

    >
    > > 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.


    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
     
    mathieu, Feb 19, 2007
    #5
  6. * mathieu:
    >
    > My goal is to provide a std::vector-like
    > interface to a 12bits unsigned int array (packed storage)


    Pack and unpack.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Feb 19, 2007
    #6
  7. mathieu

    mathieu Guest

    On Feb 18, 11:04 pm, "Alf P. Steinbach" <> wrote:
    > * mathieu:
    >
    >
    >
    > > My goal is to provide a std::vector-like
    > > interface to a 12bits unsigned int array (packed storage)

    >
    > 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
     
    mathieu, Feb 19, 2007
    #7
  8. On 18 Feb 2007 20:26:38 -0800, "mathieu" <> wrote:

    >On Feb 18, 11:04 pm, "Alf P. Steinbach" <> wrote:
    >> * mathieu:
    >>
    >>
    >>
    >> > My goal is to provide a std::vector-like
    >> > interface to a 12bits unsigned int array (packed storage)

    >>
    >> 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


    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
     
    Dave Rahardja, Feb 19, 2007
    #8
  9. mathieu

    peter koch Guest

    On Feb 19, 1:03 am, "mathieu" <> wrote:
    > 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
     
    peter koch, Feb 19, 2007
    #9
  10. mathieu

    s5n Guest

    On Feb 19, 5:26 am, "mathieu" <> wrote:
    > 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".
     
    s5n, Feb 19, 2007
    #10
  11. mathieu

    mathieu Guest

    On Feb 19, 6:32 am, "s5n" <> wrote:
    > On Feb 19, 5:26 am, "mathieu" <> wrote:
    >
    > > 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".


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

    -M
     
    mathieu, Feb 19, 2007
    #11
  12. mathieu

    mathieu Guest

    On Feb 19, 4:32 am, "peter koch" <> wrote:
    > On Feb 19, 1:03 am, "mathieu" <> wrote:> 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.


    Thanks, that's all I needed to know.

    -M
     
    mathieu, Feb 19, 2007
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. pmatos
    Replies:
    6
    Views:
    24,024
  2. Replies:
    8
    Views:
    1,984
    Csaba
    Feb 18, 2006
  3. Javier
    Replies:
    2
    Views:
    602
    James Kanze
    Sep 4, 2007
  4. Barzo
    Replies:
    3
    Views:
    291
  5. Rushikesh Joshi
    Replies:
    0
    Views:
    386
    Rushikesh Joshi
    Jul 10, 2004
Loading...

Share This Page