Bit deinterleave

[Zoijar]

Ik interleave (om-en-om zetten) nu de bits van twee 16-bit getallen met de volgende functie die ik van het net heb geplukt (met mijn eigen commentaar en uitleg):

C++:

// converts a 16-bit 2D index (x,y) into a 32-bit 1D Morton (Z-curve) index by bit interleaving
inline static quint32 interleave(quint16 x, quint16 y) {
// The idea is to make twice as much space by adding a chunk of n/2 zero bits at the start and in the middle
// so n-bits -> n/2 (0) | n/2 | n/2 (0) | n/2 = 2n bits
// Repeating this for the 2 halves of n/2 bits, discarding the high bits, gives:
// n/4 (0) | n/4 | n/4 (0) | n/4 || n/4 (0) | n/4 | n/4 (0) | n/4
//
// n/8 (0) | n/8 | n/8 (0) | n/8 || n/8 (0) | n/8 | n/8 (0) | n/8 (cntd.)
// n/8 (0) | n/8 | n/8 (0) | n/8 || n/8 (0) | n/8 | n/8 (0) | n/8
//
// n/16 (0) | n/16 | n/16 (0) | n/16 || n/16 (0) | n/16 | n/16 (0) | n/16
// n/16 (0) | n/16 | n/16 (0) | n/16 || n/16 (0) | n/16 | n/16 (0) | n/16
// n/16 (0) | n/16 | n/16 (0) | n/16 || n/16 (0) | n/16 | n/16 (0) | n/16
// n/16 (0) | n/16 | n/16 (0) | n/16 || n/16 (0) | n/16 | n/16 (0) | n/16
// since n/16 = 1 for 16bits, this gives the intended result.
// x and y can be combined by shifting by 1 and or-ing.

// B[0] = 0101 0101 0101 0101 0101 0101 0101 0101
// B[1] = 0011 0011 0011 0011 0011 0011 0011 0011
// B[2] = 0000 1111 0000 1111 0000 1111 0000 1111 
// B[3] = 0000 0000 1111 1111 0000 0000 1111 1111
    static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
    static const unsigned int S[] = {1, 2, 4, 8};

    x = (x | (x << S[3])) & B[3];
    x = (x | (x << S[2])) & B[2];
    x = (x | (x << S[1])) & B[1];
    x = (x | (x << S[0])) & B[0];

    y = (y | (y << S[3])) & B[3];
    y = (y | (y << S[2])) & B[2];
    y = (y | (y << S[1])) & B[1];
    y = (y | (y << S[0])) & B[0];

    return x | (y << 1);
}

En dat werkt prima. Maar nu wil ik de omgekeerde operatie ook doen: een 32-bit getal met de bits om-en-om omzetten naar de twee 16-bit getallen die het vormen. Ik zou het kunnen doen met twee keer vier 8-bit table lookups, maar dat lijkt me niet het meest efficiente. Is er nog een andere slimme manier, zoals die hierboven, om zoiets te doen? Ik kom er even niet uit; dit soort bitmagic is niet mijn sterkste punt...

[Grijze Vos]

Weet je zeker dat die functie werkt voor getallen boven de 8 bit? Lijkt me dat je die bitshifts in 32 bits getallen moet doen.

[Soultaker]

Eerste wat in me opkwam is de volgende O(²log N) aanpak:

C:

int x = z&0x55555555;  // alle even bits selecteren
int y = (z>>1)&0x55555555;  // alle oneven bits selecteren
x = (x & 0x11111111) | ((x & 0x44444444) >> 1);
y = (y & 0x11111111) | ((y & 0x44444444) >> 1);
x = (x & 0x03030303) | ((x & 0x30303030) >> 2);
y = (y & 0x03030303) | ((y & 0x30303030) >> 2);
x = (x & 0x000f000f) | ((x & 0x0f000f00) >> 4);
y = (y & 0x000f000f) | ((y & 0x0f000f00) >> 4);
x = (x & 0x000000ff) | ((x & 0x00ff0000) >> 8);
y = (y & 0x000000ff) | ((y & 0x00ff0000) >> 8);

Het zijn op zich vrij veel operaties (stuk of 40) maar je kunt ze behoorlijk snel uitvoeren omdat elke operatie afzonderlijk simpel is en niet aan geheugen refereert. (Aan de andere kant past je lookup table waarschijnlijk wel in je cache, dus die aanpak hoeft ook niet per se traag te zijn.)

Mocht het nog niet duidelijk zijn: het idee is dat invoer in de volgende stappen getransformeerd wordt:

code:

0p0o0n0m0l0k0j0i0h0g0f0e0d0c0b0a
00po00nm00lk00ji00hg00fe00dc00ba
0000ponm0000lkji0000hgfe0000dcba
00000000ponmlkji00000000hgfedcba
0000000000000000ponmlkjihgfedcba

Het principe lijkt me werkbaar, maar de code zelf heb ik niet getest, dus die moet je zelf nog verifiëren als je 'm wil gebruiken.

[ Voor 50% gewijzigd door Soultaker op 14-04-2010 00:24 ]

[Wolfboy]

Als ik het goed zie dan zou je inverse ongeveer dit moeten zijn:

C++:

inline static quint32 deinterleave(quint32 x) {
  static const unsigned int B[] = {0x33333333, 0X0F0F0F0F, 0X00FF00FF, 0X0000FFFF};
  static const unsigned int S[] = {1, 2, 4, 8};

  x &= 0x55555555;
  x = (x ^ (x >> S[0])) & B[0];
  x = (x ^ (x >> S[1])) & B[1];
  x = (x ^ (x >> S[2])) & B[2];
  x = (x ^ (x >> S[3])) & B[3];
  return x;
}

Eventjes shiften als je de andere 16 bits wil uiteraard

[ Voor 62% gewijzigd door Wolfboy op 14-04-2010 00:59 . Reden: stijl aangepast aan de TS ]

[Soultaker]

Ah ja, dat is wel een aardige optimalisatie, dat scheelt je toch weer een and-operatie per regel. Maar je deinterleave() functie klopt niet echt.

edit:
't Moet nog iets efficienter kunnen door beide waarden tegelijk te deinterleaven... even puzzelen...

[ Voor 28% gewijzigd door Soultaker op 14-04-2010 01:11 ]

[Wolfboy]

Wat klopt er niet?

Ik moet toegeven dat ik de code nog had liggen van een projectje van me. En het 2e deel van m'n deinterleave was eerst dan ook een 3 deling per 10 bits in plaats van een 2 deling per 16 bits.

De huidige code werkt (net getest) prima als je alles (tijdens de conversie iig) 32 bit maakt

C++:

uint32_t x = 12345;
uint32_t y = 23456;
uint32_t xy = interleave(x, y);
x = deinterleave(xy);
y = deinterleave(xy >> 1);

@Zoijar: hoe kan jouw code ooit goed werken eigenlijk? Je bent een 16 bits getal aan het omzetten naar 32 bits zonder het te vergroten? Zodra je in X meer dan 8 bits gebruikt werkt het toch niet meer?

[ Voor 18% gewijzigd door Wolfboy op 14-04-2010 01:46 . Reden: variabelen gerenamed :+ ]

[Soultaker]

@Wolfboy: ik had het over je code vóór je edit.

Na wat gepuzzel kom ik op deze manier om beide waarden tegelijk te deinterleaven:

C:

void deinterleave(uint32_t z, uint16_t *x, uint16_t *y)
{
    z = ((z & 0x0000aaaa) << 15) | (z & 0xaaaa5555) | ((z & 0x55550000) >> 15);
    z = ((z & 0x00aa00aa) <<  7) | (z & 0xaa55aa55) | ((z & 0x55005500) >>  7);
    z = ((z & 0x0a0a0a0a) <<  3) | (z & 0xa5a5a5a5) | ((z & 0x50505050) >>  3);
    z = ((z & 0x22222222) <<  1) | (z & 0x99999999) | ((z & 0x44444444) >>  1);
    *x = z;
    *y = z>>16;
}

Gebaseerd op deze volgorde van operaties:

code:

PpOoNnMmLlKkJjIiHhGgFfEeDdCcBbAa
PHOGNFMELDKCJBIAphognfmeldkcjbia
PLOKNJMIHDGCFBEAploknjmihdgcfbea
PNOMLJKIHFGEDBCApnomljkihfgedbca
PONMLKJIHGFEDCBAponmlkjihgfedcba

Of 't veel sneller is, is natuurlijk de vraag...

[ Voor 15% gewijzigd door Soultaker op 14-04-2010 02:06 ]

[Wolfboy]

Het zou best sneller kunnen zijn, mijn code doet wel een paar xor operaties die toch wel iets zwaarder zijn. Eigenlijk zouden we het moeten benchmarken maar ik ben te lui eigenlijk

Imho komt het vooral op mooier neer, en dan wint jouw optie het imho.

[Soultaker]

Re: efficiëntie: ik roep minder operators aan dus in een scripttaal zal 't wel sneller zijn, maar bij compilatie tellen registertransfers e.d. ook mee, zeker in code zoals deze die geen extern geheugen refereert. Een enkel statement uit jouw lus:

C:

x = (x ^ (x >> <constante>) & <constante>; 

Komt voor x86 code generatie effectief neer op:

C:

a = x
a >>= <constante>
x ^= a
x &= <constante>

Terwijl een regel van mij:

C:

z = ((z & <c>) << <c>) | (z & <c>) | ((z & <c>) >> <c>)

Meer tijdelijke registers nodig heeft:

C:

a = z
a &= <constante>
a <<= <constante>
b = z
b &= <constante>
b >>= <constante>
z &= <constante>
z |= a
z |= b

Daar staat tegenover dat jij de basiscode twee keer moet uitvoeren en nog een keer moet masken per waarde, maar dan nog ontloopt het aantal instructies elkaar niet veel. Het zou me dan ook niet verbazen als jouw simpelere code uiteindelijk net wat sneller is.

[ Voor 4% gewijzigd door Soultaker op 14-04-2010 02:39 ]

[Wolfboy]

Omdat ik nu toch wel benieuwd was...

Compiled met het volgende commando:

g++ -Os -S test.cpp

Assembly van jouw code:

code:

    movl    8(%ebp), %eax
    movl    %eax, %edx
    movl    %eax, %ecx
    andl    $43690, %edx
    andl    $1431633920, %eax
    shrl    $15, %eax
    andl    $-1431677611, %ecx
    sall    $15, %edx
    orl %eax, %edx
    orl %ecx, %edx
    movl    %edx, %eax
    movl    %edx, %ecx
    andl    $11141290, %eax
    andl    $1426085120, %edx
    shrl    $7, %edx
    andl    $-1437226411, %ecx
    sall    $7, %eax
    orl %edx, %eax
    orl %ecx, %eax
    movl    %eax, %edx
    movl    %eax, %ecx
    andl    $168430090, %edx
    andl    $1347440720, %eax
    shrl    $3, %eax
    andl    $-1515870811, %ecx
    sall    $3, %edx
    orl %eax, %edx
    orl %ecx, %edx
    movl    %edx, %eax
    movl    %edx, %ecx
    andl    $572662306, %eax
    andl    $1145324612, %edx
    shrl    %edx
    addl    %eax, %eax
    orl %edx, %eax
    movl    12(%ebp), %edx
    andl    $-1717986919, %ecx
    orl %ecx, %eax
    movzwl  %ax,%ecx
    shrl    $16, %eax
    movl    %ecx, (%edx)
    movl    16(%ebp), %edx
    movl    %eax, (%edx)
    popl    %ebp
    ret

Assembly van mijn code:

code:

    movl    8(%ebp), %ecx
    movl    %ecx, %edx
    shrl    %edx
    andl    $1431655765, %edx
    movl    %edx, %eax
    shrl    %eax
    xorl    %edx, %eax
    andl    $858993459, %eax
    movl    %eax, %edx
    shrl    $2, %edx
    xorl    %eax, %edx
    andl    $252645135, %edx
    movl    %edx, %eax
    shrl    $4, %eax
    xorl    %edx, %eax
    andl    $16711935, %eax
    movl    %eax, %edx
    shrl    $8, %edx
    xorl    %eax, %edx
    movl    16(%ebp), %eax
    andl    $65535, %edx
    movl    %edx, (%eax)
    movl    %ecx, %edx
    andl    $1431655765, %edx
    movl    %edx, %eax
    shrl    %eax
    xorl    %edx, %eax
    andl    $858993459, %eax
    movl    %eax, %edx
    shrl    $2, %edx
    xorl    %eax, %edx
    andl    $252645135, %edx
    movl    %edx, %eax
    shrl    $4, %eax
    xorl    %edx, %eax
    andl    $16711935, %eax
    movl    %eax, %edx
    shrl    $8, %edx
    xorl    %eax, %edx
    movl    12(%ebp), %eax
    andl    $65535, %edx
    movl    %edx, (%eax)
    popl    %ebp
    ret

En de benchmark resultaten bij 10^9 iteraties:
Mijn code: 12.6 seconden (beste van 3 resultaten)
Jouw code: 13.7 seconden (beste van 3 resultaten)

De verschillen zijn klein genoeg om een meetfout te kunnen zijn, en ik heb overal uint32_t's gebruikt om de code drop-in te kunnen vervangen

[Zoijar]

Bedankt voor alle replies! Ik ga het zo allemaal even doornemen en testen

Mijn interleave code moest idd twee 32-bit input ints zijn (met de hoge 16bits 0); foutje. Maar dan werkt het wel.

Ok, beide routines werken idd. Mijn dank

In de praktijk duurt het inladen van een 1 gigapixel plaatje in z-order 57.3s met de methode van soultaker, en 63.8s met die van wolfboy. Uiteraard domineert de disk access tijd hier, maar het is wel een realistisch scenario.

(overigens duurt het 54s zonder z-order, maar dat is omdat ik nu sowieso de hele file inlaadt en het dus altijd sequentieel kan doen)

[ Voor 51% gewijzigd door Zoijar op 14-04-2010 12:20 ]

[Wolfboy]

lol... dat zet dit topic wel in een ander perspectief: [ALG] Ingekleurde vlakken vergelijken

[Zoijar]

haha, ik heb wat zitten optimizen (ik schaalde het plaatje namelijk eerst, dat doe ik nu in machten van 2 door opvolgende z-order indices bij elkaar op te tellen; het hele idee voor een z-order index in dit geval, zodat ik met linear access kan schalen) en hij doet het nu in 18s, en als de file nog gebuffered is door je OS (i.e. als je hem meteen opnieuw nog een keer opent) 8s. (van 32kx32k naar 2kx2k met simpele binning)

[ Voor 5% gewijzigd door Zoijar op 14-04-2010 14:36 ]