#include <stdio.h>
#include <string.h>

void swap(void* pa, void* pb, size_t sz)
{
  char *p1 = pa, *p2 = pb;
  while (sz--)
  {
    char tmp = *p1;
    *p1++ = *p2;
    *p2++ = tmp;
  }
}

/*
Want: abcdefgh12345678 -> a1b2c3d4e5f6g7h8

a b c d e f g h
  1 2 3 4 5 6 7 8

  4 1-sized swaps:

a 1 c 3 e 5 g 7
  b 2 d 4 f 6 h 8

a1  c3  e5  g7
    b2  d4  f6  h8

  2 2-sized swaps:

a1  b2  e5  f6
    c3  d4  g7  h8

a1b2  e5f6
      c3d4  g7h8

  1 4-sized swap:

a1b2  c3d4
      e5f6  g7h8

a1b2c3d4
        e5f6g7h8
*/

void interleave(char* s, size_t len)
{
  size_t start, step, i, j;

  if (len <= 2)
    return;

  if (len & (len - 1))
    return; // only power of 2 lengths are supported

  for (start = 1, step = 2;
       step < len;
       start *= 2, step *= 2)
  {
    for (i = start, j = len / 2;
         i < len / 2;
         i += step, j += step)
    {
      swap(s + i,
           s + j,
           step / 2);
    }
  }
}

char testData[][64 + 1] =
{
  { "Aa" },
  { "ABab" },
  { "ABCDabcd" },
  { "ABCDEFGHabcdefgh" },
  { "ABCDEFGHIJKLMNOPabcdefghijklmnop" },
  { "ABCDEFGHIJKLMNOPQRSTUVWXYZ0<({[/abcdefghijklmnopqrstuvwxyz1>)}]\\" },
};

int main(void)
{
  unsigned i;

  for (i = 0; i < sizeof(testData) / sizeof(testData[0]); i++)
  {
    printf("%s -> ", testData[i]);
    interleave(testData[i], strlen(testData[i]));
    printf("%s\n", testData[i]);
  }

  return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmcuaD4KCnZvaWQgc3dhcCh2b2lkKiBwYSwgdm9pZCogcGIsIHNpemVfdCBzeikKewogIGNoYXIgKnAxID0gcGEsICpwMiA9IHBiOwogIHdoaWxlIChzei0tKQogIHsKICAgIGNoYXIgdG1wID0gKnAxOwogICAgKnAxKysgPSAqcDI7CiAgICAqcDIrKyA9IHRtcDsKICB9Cn0KCi8qCldhbnQ6IGFiY2RlZmdoMTIzNDU2NzggLT4gYTFiMmMzZDRlNWY2ZzdoOAoKYSBiIGMgZCBlIGYgZyBoCiAgMSAyIDMgNCA1IDYgNyA4CgogIDQgMS1zaXplZCBzd2FwczoKCmEgMSBjIDMgZSA1IGcgNwogIGIgMiBkIDQgZiA2IGggOAoKYTEgIGMzICBlNSAgZzcKICAgIGIyICBkNCAgZjYgIGg4CgogIDIgMi1zaXplZCBzd2FwczoKCmExICBiMiAgZTUgIGY2CiAgICBjMyAgZDQgIGc3ICBoOAoKYTFiMiAgZTVmNgogICAgICBjM2Q0ICBnN2g4CgogIDEgNC1zaXplZCBzd2FwOgoKYTFiMiAgYzNkNAogICAgICBlNWY2ICBnN2g4CgphMWIyYzNkNAogICAgICAgIGU1ZjZnN2g4CiovCgp2b2lkIGludGVybGVhdmUoY2hhciogcywgc2l6ZV90IGxlbikKewogIHNpemVfdCBzdGFydCwgc3RlcCwgaSwgajsKCiAgaWYgKGxlbiA8PSAyKQogICAgcmV0dXJuOwoKICBpZiAobGVuICYgKGxlbiAtIDEpKQogICAgcmV0dXJuOyAvLyBvbmx5IHBvd2VyIG9mIDIgbGVuZ3RocyBhcmUgc3VwcG9ydGVkCgogIGZvciAoc3RhcnQgPSAxLCBzdGVwID0gMjsKICAgICAgIHN0ZXAgPCBsZW47CiAgICAgICBzdGFydCAqPSAyLCBzdGVwICo9IDIpCiAgewogICAgZm9yIChpID0gc3RhcnQsIGogPSBsZW4gLyAyOwogICAgICAgICBpIDwgbGVuIC8gMjsKICAgICAgICAgaSArPSBzdGVwLCBqICs9IHN0ZXApCiAgICB7CiAgICAgIHN3YXAocyArIGksCiAgICAgICAgICAgcyArIGosCiAgICAgICAgICAgc3RlcCAvIDIpOwogICAgfQogIH0KfQoKY2hhciB0ZXN0RGF0YVtdWzY0ICsgMV0gPQp7CiAgeyAiQWEiIH0sCiAgeyAiQUJhYiIgfSwKICB7ICJBQkNEYWJjZCIgfSwKICB7ICJBQkNERUZHSGFiY2RlZmdoIiB9LAogIHsgIkFCQ0RFRkdISUpLTE1OT1BhYmNkZWZnaGlqa2xtbm9wIiB9LAogIHsgIkFCQ0RFRkdISUpLTE1OT1BRUlNUVVZXWFlaMDwoe1svYWJjZGVmZ2hpamtsbW5vcHFyc3R1dnd4eXoxPil9XVxcIiB9LAp9OwoKaW50IG1haW4odm9pZCkKewogIHVuc2lnbmVkIGk7CgogIGZvciAoaSA9IDA7IGkgPCBzaXplb2YodGVzdERhdGEpIC8gc2l6ZW9mKHRlc3REYXRhWzBdKTsgaSsrKQogIHsKICAgIHByaW50ZigiJXMgLT4gIiwgdGVzdERhdGFbaV0pOwogICAgaW50ZXJsZWF2ZSh0ZXN0RGF0YVtpXSwgc3RybGVuKHRlc3REYXRhW2ldKSk7CiAgICBwcmludGYoIiVzXG4iLCB0ZXN0RGF0YVtpXSk7CiAgfQoKICByZXR1cm4gMDsKfQo=