#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
using Blob = vector<uint8_t>;

Blob toPrefix(Blob p) {
	Blob out(ceil(p.size() / 2.)); // Output is on 1 bit instead of 2 for each data
		
	for ( int i = 0; i < p.size(); i++ ) {
    	if ( (p[i] | 0x55) != 0xFF )
    		throw std::domain_error("Can not convert to prefix with undefine bits"); 

    	uint8_t mask = 0x40;          // Mqsk for extracting bit a pos x               
    	int shift = ( i % 2 ) ? 3 : 1; // For first uin8_t need to move shift bit to left
    	                           // and to right for second uint8_t
    							   // First : 0101 0000 - Second : 1111 0111
    	                           // First : Bit pos 1 move to pos 0 - Second : Bit pos 1 move to pos 4

    	for ( int b = 1; b < 8; b += 2, mask >>= 2) { // for each bit of the uint8_t ( jump 1 of 2) and shift j mask
    		out[i / 2] ^= (
    						( i % 2 ) ? 
    							( p[i] & mask ) >> shift  // Get bit pos l, move it to position by shifting of k
    					  	  : ( p[i] & mask ) << shift
    					  );

    		( i % 2 ) ? --shift : ++shift; // Next shift to do
    	}
    }
    
    return out;
}

// http://stackoverflow.com/questions/29547628/convert-uint8-t-hex-value-to-binary
void toBinary(uint8_t a) {
	int tmp = 0;
    for(uint8_t i=0x80;i!=0;i>>=1) {
    	if ( tmp++ % 4 == 0 ) 
    		cout << " ";

        cout << ((a&i)?'1':'0');
    }
}

void toBinary(Blob p) {
	for (int i = 0; i < p.size(); i++ )
		toBinary(p[i]);
}

int main() {
	
	Blob p; // Test Blob	
	p.push_back(0xBA); // 1011 1010
	
	Blob out(2 * p.size()); // ceil(p.size_ * 2. / 8.);

    cout << "Prefix with unknown value :" ;
    toBinary(p);
	for ( int i = 0; i < p.size(); i++ ) {
    	for ( int b = 0; b < 8; b++) {
    		;
    	}
	}
	cout << endl << "Output : ";
	toBinary(toPrefix(p));
    cout << endl;
    
    exit(0);
}