bit_utils.cpp

#include "bit_utils.h"

/* return the byte in position n */
template <class byte_iterator>
byte get_byte(byte_iterator begin, int n)
{
    if(n%8==0)
    {
        return begin[n/8] ;
    }
    return (begin[n/8] << (n%8) ) | (begin[n/8 + 1]>>(8-n%8));
};


/* return n bit starting from the bit in start */
template<class byte_iterator>
bits get_bits(byte_iterator begin, int start, int n)
{
    bits a;
    a.size=n;
    int full_b=n/8, rem=n%8;
    for(int i=0; i<full_b; ++i)
    {
        a.b.push_back(get_byte(begin, start + i*8));
    }
    if(rem)
    {
        if(start%8+rem>7)
        {
            a.b.push_back(get_byte(begin, start+n-rem));
        }
        else
        {
            a.b.push_back(begin[start/8+full_b]<<(start%8));
        }
    }
    return a;
};


/* insert n bits in begin at start*/
template<class byte_iterator>
void bits_insert(const bits& b, byte_iterator begin, int start, int n)
{
    int prefix=(8-start%8)%8;
    if(n<prefix)
    {
        byte pre=(begin[start/8]>>(prefix))<<(prefix);
        byte post=( (byte)(begin[start/8]<<(8-prefix+n)) )>>(8-prefix+n);
        begin[start/8]=pre | ((b.b[0]>>(8-n))<<(prefix-n)) | post;
        return;
    }
    int first_byte=start/8;
    if (prefix!=0)
    {
        byte pre=(begin[first_byte]>>(prefix))<<(prefix);
        begin[first_byte]= pre | (b.b[0]>>(8-prefix));
        ++first_byte;
    }
    int center=(n-prefix)/8;
    for (int i=0; i<center; ++i)
    {
        begin[first_byte+i]=get_byte(b.b.begin(), prefix+8*i);
    }
    int post=(n-prefix)%8;
    if (post!=0)
    {
        byte temp=get_byte(b.b.begin(), n-8);
        byte pre=temp<<(8-post);
        begin[(start+n)/8]=pre | ((byte)(begin[(start+n)/8]<<post)>>post);
    }
};


/* return number of bits matching in the two bytes, supposed different */
int bit_compare(byte a, byte b)
{
    int h;
    for (h=1; h<8; ++h)
    {
        if ( (a>>h)==(b>>h) )
            return 8-h;
    }
    return 0;
};