1

so i'm reversing a file format of game. As far as i can understand the file i'm trying to reverse contains compressed textures. I'm already able to locate the textures and decompress them, but i'm not entirely sure if it's compression or some weird encoding.

During the process there's a huge buffer that's accessed a lot of times, giving the information of the current pixel being drawn. The buffer contains 4 byte unsigned integers and is generated through the following function:

for(uint32_t counter = 0; counter<0x400; counter++){

    //unk1 eax
    //unk2 edx
    //unk3 esi
    //unk4 ecx
    //loc_5115EB
    uint32_t unk1 = (counter >> 1) & 0x55555555;
    uint32_t unk3 = (unk1 * 2) ^ counter;
    uint32_t unk4 = ((unk3 >> 2) & 0x33333333) ^ ((counter >> 1) & 0x11111111);

    unk1 ^= unk4;
    unk3 ^= (unk4 << 2);

    unk4 = ((unk3 >> 4) & 0x0F0F0F0F) ^ (unk1 & 0x0F0F0F0F);
    unk1 ^= unk4;
    unk3 ^= (unk4 << 4);

    unk4 = ((unk3 >> 8) & 0x00FF00FF) ^ (unk1 & 0x00FF00FF);

    buffer[counter] = (((unk4 & 0xFF) << 8) ^ (unk3 & 0xFFFF)) | ((unk4 ^ unk1) << 16); 

}

The resulting sequence in hex is:

00 00 00 00 01 00 00 00 04 00 00 00 05 00 00 00 10 00 00 00 11 00 00 00 14 00 00 00 15 00 00 00 40 00 00 00 41 00 00 00 44 00 00 00 45 00 00 00 50 00 00 00 51 00 00 00 54 00 00 00 55 00 00 00 00 01 00 00 01 01 00 00 04 01 00 00 05 01 00 00 10 01 00 00 11 01 00 00 14 01 00 00 15 01 00 00 40 01 00 00 41 01 00 00 44 01 00 00 45 01 00 00 50 01 00 00 51 01 00 00 54 01 00 00 55 01 00 00 00 04 00 00 01 04 00 00 04 04 00 00 05 04 00 00 10 04 00 00 11 04 00 00 14 04 00 00 15 04 00 00

or in decimal 0, 1, 4, 5, 16, 17, 20, 21, 64, 65...

I tried to search it online but couldn't find any info regarding the sequence. But i found 0x55555555 and the others numbers are "magic" numbers, having a wide use.

  • Maybe look at it in binary? The lower end looks like it's normal binary counting but only using every other bit. Not sure where it goes from there. Interesting though! – Rup Jul 8 '17 at 11:27
  • @Rup was the first thing i attempted but no luck. Thankfully was able to find what it really is – krystalgamer Jul 8 '17 at 15:46
  • Actually, from the descriptions of the sequence on the OEIS page I was right. Glad you found a name for it though. – Rup Jul 8 '17 at 22:21
2

Asked this to a person who has more knowledge than me and he was able to answer!

This is the Moser-de Bruijn sequence and looks like it's used for binary interleaving which is really important in this case, since i'm working with image compression.

By the way I have to apologize since i should've posted a more significant decimal representation of the sequence, which is now added to the main post.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.