CODEWITHSUNDEEP
c++
Moon4u
Moon4u

Reputation: 127

Is there a better way to use bitstreams to decode a file format?

I am trying to make a program that decodes an mp3 file (as an exercise). The important part is not that it is an mp3 file, but the way that the file format is structured. The length (in bits) of some variables depends on previous variables. So, let's say that you read 2 bits for one variable and based on its value, you have to read either 10 bits or 20 bits for the next variable. What makes things worst is that every consecutive read is offset by the same length.

I'm using the following bitstream implementation, which works wonderfully and I'm really happy with the asm that's being generated.

The problem is that this implementation requires to know the offset and length for each bitread during compilation. The variable length of some of the variables makes it really hard to implement.

There are two ideas that come to mind and both of them seems bad. One would be to change the bit reading function so that I pass the offset as a parameter to the function as a regular argument instead of as a template argument. This is obviously awful because we lose the beautiful asm. The bigger point is that this information is already known. This shouldn't happen at runtime when the information is available at compile time. I just need to be able to explain it better to the compiler.

The other idea is to use some weird template metaprogramming (check the second coding example)

The first idea is as follows:

// the function works like the one in the bitstream implementation that I pointed earlier, but the offset is an argument to the function, instead of a template argument.
template<unsigned count>
uint32_t Read(int offset, const uint8_t* src, uint32_t accum = 0);

uint32_t var1 = Read(0, 2, data);
switch(var1) {
  case 0b00: {
    uint32_t var2 = Read(2, 10, data);
    uint32_t var3 = Read(12, 3, data);
    uint32_t var4 = Read(15, 1, data);
    //... etc
    break;
  }

  case 0b01: {
    uint32_t var2 = Read(2, 20, data);
    uint32_t var3 = Read(22,  3, data);
    uint32_t var4 = Read(25,  3, data);
    // ... etc
   break;
  }
  default: 
    break;
}

The second idea is to use the unmodified Read function but move all offsets & lengths to a sperate template class, and have specializations for each case.

template<enum DIFFERENT_CASES T> struct offsets_and_lengths {};

struct BitReads { unsigned offset; unsigned length; };

template<> struct offsets_and_lengths<CASE_1> {
  static constexpr BitReads var2 = { 2, 10 };
  static constexpr BitReads var3 = { 12, 3 };
  static constexpr BitReads var4 = { 15, 1 };
};

template<> struct offsets_and_lengths<CASE_2> {
  static constexpr BitReads var2 = { 2, 20 };
  static constexpr BitReads var3 = { 22, 3 };
  static constexpr BitReads var4 = { 25, 1 };
};

template<enum DIFFERENT_CASES T>
void doDifferentReads(uint8_t* data) {
  using offsets = offsets_and_legnths<T>;
  uint32_t var2 = Read<offsets::var2.offset, offsets.length>(data);
  uint32_t var3 = Read<offsets::var3.offset, offsets.length>(data);
  uint32_t var4 = Read<offsets::var4.offset, offsets.length>(data);
  // ... etc
}


uint32_t var1 = Read(0, 2, data);
switch(var1) {
  case 0b00: {
    doDifferentReads<CASE_1>(data);
    break;
  }

  case 0b01: {
    doDifferentReads<CASE_2>(data);
   break;
  }
  default: 
    break;
}

The problem with the second implementation is that I may end up having another variable with a possible difference in its length. At that point, I'll have to create 4 different specializations. 8 for the next one... etc.

So I guess the big question is: Is there a sane way to do decoding on such formats if I want to use the static data that I know? So that the generate asm would be small.

Upvotes: 2

Views: 196

Answers (1)

Dominique Lorre
Dominique Lorre

Reputation: 1168

You can use bitmasks and shift to perform the extraction:

int32_t bitmask[2][3] = {
    {
         ?, ?, ?
    },
    {
        ?, ?, ?
    }

};
int32_t shift[2][3] = {
    {
         ?, ?, ?
    },
    {
        ?, ?, ?
    }

};


void extraction(int index, uint32_t follow) {

    uint32_t var2 = (follow & bitmask[index][0]) >> shift[index][0];
    uint32_t var3 = (follow & bitmask[index][1]) >> shift[index][1];
    uint32_t var4 = (follow & bitmask[index][2]) >> shift[index][2];

}


int main()
{
    int32_t v = 0;


    uint32_t var1 = Read(0, 2, data);
    int index = 0;
    switch (var1) {
    case 0b00: {
        uint32_t follow = Read(2, 14, data);
        extraction(0, follow);
        break;
    }

    case 0b01: {
        uint32_t follow = Read(2, 26, data);
        extraction(1, follow);
        break;
    }


}

I'm not going to search all the values for mask and shift but I can show you how to calculate the first one. You have Read(2, 10), and we have read 14 bits, so the shift is easy it is 4 since you need to shift by 4 bits. The mask in binary is 0011 1111 1111 0000 so 0x3FF0. Naturally big endian and little endian can interfer here so you have to be careful that the data is in the right order. Notice that you can store the variables in an array for extra efficiency and change extraction() into a for loop.

Upvotes: 1

Related Questions