Thread: [Algorithms] Byte Swapping

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

I can do the obvious method, but I was wondering if anyone have any 
cool/fast code snippets for byte swapping integers and floats?

Tom

Jumping in late : I'm sure you don't need it now, but
here's a crazy ANSI C byte-swapper :

let x = a 32 bit ulong , ABCD 
then y = DCBA

y = (x = x>>16 | x<<16) ^ (x = (x^x>>8) & 0x00FF00FF) ^ (x<<8);

At 11:45 PM 7/15/2000 -0700, you wrote:
>I can do the obvious method, but I was wondering if anyone have any 
>cool/fast code snippets for byte swapping integers and floats?
>
>Tom
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>
>
--------------------------------------
Charles Bloom           www.cbloom.com

Errr............ you'd better use the BSWAP instruction........ same result
with one line of assembly............

Pierre

----- Original Message -----
From: Charles Bloom <cb...@cb...>
To: <gda...@li...>
Sent: Tuesday, July 18, 2000 12:41 AM
Subject: Re: [Algorithms] Byte Swapping

>
> Jumping in late : I'm sure you don't need it now, but
> here's a crazy ANSI C byte-swapper :
>
> let x = a 32 bit ulong , ABCD
> then y = DCBA
>
> y = (x = x>>16 | x<<16) ^ (x = (x^x>>8) & 0x00FF00FF) ^ (x<<8);
>
> At 11:45 PM 7/15/2000 -0700, you wrote:
> >I can do the obvious method, but I was wondering if anyone have any
> >cool/fast code snippets for byte swapping integers and floats?
> >
> >Tom
> >
> >
> >_______________________________________________
> >GDAlgorithms-list mailing list
> >GDA...@li...
> >http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> >
> >
> --------------------------------------
> Charles Bloom           www.cbloom.com
>
>
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list

> Errr............ you'd better use the BSWAP instruction........ same
result
> with one line of assembly............
>
BSWAP is an x86 instruction :) Not much good if you wanna swap bytes on the
Mac.

Possibly there is a Mac equivelent, but I think it is RISC practice to avoid
such instructions.

Conor Stokes

> From: Charles Bloom <cb...@cb...>
> 
> Jumping in late : I'm sure you don't need it now, but
> here's a crazy ANSI C byte-swapper :
> 
> let x = a 32 bit ulong , ABCD
> then y = DCBA
> 
> y = (x = x>>16 | x<<16) ^ (x = (x^x>>8) & 0x00FF00FF) ^ (x<<8);
> 

wow, I'll say that's crazy...but unfortunately non-functional.  see the
results of this program:

#include <stdio.h>

long swap1(long x)
{
    return (x = x>>16 | x<<16) ^ (x = (x^x>>8) & 0x00FF00FF) ^ (x<<8);
}

long swap2(long x)
{
    return         ((x >> 24) & 0x000000FF)
            |    ((x >> 8 ) & 0x0000FF00)
            |    ((x << 8 ) & 0x00FF0000)
            |    ((x << 24) & 0xFF000000)
            ;
}

int main(int argc, char **argv)
{
    long test = 0x01020304;

    printf("swap1: 0x%08X 0x%08X 0x%08X \n", test, swap1(test),
swap1(swap1(test)));

    printf("swap2: 0x%08X 0x%08X 0x%08X \n", test, swap2(test),
swap2(swap2(test)));
}

swap1: 0x01020304 0x07000300 0x03000700
swap2: 0x01020304 0x04030201 0x01020304

anyway, in case anyone hasn't gotten their fill of this stuff, here is our
comparatively lame byteswapping code that uses those fast swappers on
PowerPC:

#ifndef _MBSWAP_H_
#define _MBSWAP_H_

// swapping macros/inlines
#include <Runtime/MBBase.h>

inline MBint16 MBSwap(const MBint16 & swap)
{
#if defined(MB_MAC) && defined(MB_POWERPC)
    return __lhbrx(const_cast<MBint16 *>(&swap), 0);
#else
    return         ((swap >> 8 ) & 0x00FF)
            |    ((swap << 8 ) & 0xFF00)
            ;
#endif
}

inline MBuint16 MBSwap(const MBuint16 & swap)
{
#if defined(MB_MAC) && defined(MB_POWERPC)
    return __lhbrx(const_cast<MBuint16 *>(&swap), 0);
#else
    return         ((swap >> 8 ) & 0x00FF)
            |    ((swap << 8 ) & 0xFF00)
            ;
#endif
}

inline MBint32 MBSwap(const MBint32 & swap)
{
#if defined(MB_MAC) && defined(MB_POWERPC)
    return __lwbrx(const_cast<MBint32 *>(&swap), 0);
#else
    return         ((swap >> 24) & 0x000000FF)
            |    ((swap >> 8 ) & 0x0000FF00)
            |    ((swap << 8 ) & 0x00FF0000)
            |    ((swap << 24) & 0xFF000000)
            ;
#endif
}

inline MBuint32 MBSwap(const MBuint32 & swap)
{
#if defined(MB_MAC) && defined(MB_POWERPC)
    return __lwbrx(const_cast<MBuint32 *>(&swap), 0);
#else
    return         ((swap >> 24) & 0x000000FF)
            |    ((swap >> 8 ) & 0x0000FF00)
            |    ((swap << 8 ) & 0x00FF0000)
            |    ((swap << 24) & 0xFF000000)
            ;
#endif
}

inline MBfloat MBSwap(const MBfloat & swap)
{
    MBuint32 temp = *(const MBuint32*)&swap;
    temp = MBSwap(temp);
    return *(const MBfloat *)&temp;
}

#ifdef MB_MSB

    #define MBSwapMSBToNative( s ) s
    #define MBSwapNativeToMSB( s ) s

    #define MBSwapLSBToNative MBSwap
    #define MBSwapNativeToLSB MBSwap

#elif defined(MB_LSB)

    #define MBSwapLSBToNative( s ) s
    #define MBSwapNativeToLSB( s ) s

    #define MBSwapMSBToNative MBSwap
    #define MBSwapNativeToMSB MBSwap

#endif

#endif // header guard

I'm (re) building a scene graph and have made some strange choices with
uncertain implications. These are partly motivated by my desire to see the
benefits of a "highly OOP" approach to a scene graph, avoiding for the
moment my knee-jerk tendency to overoptimize immature architectures. At any
rate, I ran into a thorny (and hopefully interesting) architectural decision
recently which I'd like some input on.

The basic approach:

A scene graph is a nodes & arcs data structure used for affecting rendering
state. The screen is considered to be state.

Each node in a scenegraph has any number of incoming arcs. The most basic
level of node has one outgoing arc.

Arcs are directed.

Subgraphs may be cyclic. It is incumbent upon the node to conditionalize
traversal of outgoing arcs to effect loop termination. This is where we
insert culling, including portals and octree neighbors.

Rendering is effected by calling "render" on the root of the graph, which
then recurses on the targets of outgoing arcs.

My First Weird Decision is to make arcs first-class objects. Nodes never
contain pointers (in the C sense) to other nodes, but only pointers to arcs.
	- to provide a point of indirection for loading scenes over the network
(functionality)
	- to allow lazy evaluation of inter-object references (performance)
	- to separate inter-object reference semantics from node semantics
(simplicity)

This brought up an interesting issue. Since the "basic" node has a single
outgoing arc, how do we have a classic one parent/many children
relationship.

The two choices are:
	- a special type of node with multiple outgoing arcs (group nodes)
	- a special type of arc with multiple terminating nodes (multi-arcs)

The advantage of multi-arcs is that nodes don't have to support "groupness,"
simplifying their implementation. Classes designed to support a single
outgoing arc can be fitted with multiple outgoing arcs.

The disadvantage of multi-arcs is that they need to be made aware of the
rendering protocol, thereby conflating "rendering" with "connecting," two
previously orthagonal concepts.

The advantage of group nodes is that arc traversal decisions are centralized
into the node. For example, imagine a cell (as in portals and cells) that's
deciding which of its portal links to traverse. If the number of portals is
"hidden" from the cell, the logic becomes less intuitive.

For these (and other reasons,) I went with the group nodes approach, but not
without some regret for the simple elegance of multi-arcs.

The hard-core among us will, I'm sure, look askance at the cache-pessimizing
effect of having pointers all over creation. My plan for this is a
"graph-crushing" algorithm which will pack a graph into a contiguous chunk
of RAM based on a more-or-less "standard" traversal. This is extremely easy
to effect at load time. I will, however, still have to support fragmentation
and relocation for (hopefully rare) cases of dynamic graph modification.

> My First Weird Decision is to make arcs first-class objects. Nodes never
> contain pointers (in the C sense) to other nodes, but only
> pointers to arcs.
> 	- to provide a point of indirection for loading scenes over
> the network (functionality)
> 	- to allow lazy evaluation of inter-object references (performance)
> 	- to separate inter-object reference semantics from node semantics
> (simplicity)

  Interesting. I have something similar, but effectively in the reverse. In
my scene graph design (inspired by XSG), the interior nodes are typically
all of the same class (XInteriorNode), but can have a "core" node plugged
into it (or a chain of cores, even). The core node modifies the traversal
behaviour, so f.ex. instead of having a dedicated transform or switch node,
we have an interior node with a "Matrix" core or "Switch" core plugged into
it.

       Traditional:

        +-------+                   +--------+    +------+
        | Xform |                   |Interior|<---|Matrix|
        +-------+                   +--------+    +------+
       /    |    \                 /    |    \
 +----+  +----+   +----+     +----+  +----+   +----+
 |Geom|  |Geom|   |Geom|     |Geom|  |Geom|   |Geom|
 +----+  +----+   +----+     +----+  +----+   +----+

  This simplifies and enables you to do a lot of things, but it's kind of
hard to describe everything here. To take one example, imagine having a
scene graph describing a number of different levels-of-detail of a car.
During the game you will want to update the scene graph to rotate the
wheels. Now if you had a graph where the interior nodes themselves stored
the matrix as well as the child node list, you would have to update ALL
transform nodes in each level-of-detail subgraph. Using the plug-in approach
instead, you would only have one transform plugged into all LOD instances,
so you would only have to poke the rotation matrix into one place, without
caring which LOD subgraph is picked at traversal time.

  This is, I think, similar to what you have done -- only different :). The
interior node objects typically only describe the topology and bounding
volumes of the graph, with geometry at the leaf nodes and behaviour
modifiers ("cores") plugged into the interior nodes.

  I don't allow cycles in my scene graphs though. I keep separate node
graphs for higher-level culling and visibility purposes. I like to keep my
graphs "clean" and single-purpose.

  Another thing you may want to look at is using a more generic dispatch
system rather than having virtual functions (I'm assuming that's what you
are doing now) on the nodes themselves. By separating behaviour from data
you gain a lot of power. I use a Action/Node double-dispatch system similar
to the one used in XSG and Inventor. In my previous scene-graph prototype I
used virtual functions and it got messy real quick. I have had no such
problems with the double-dispatch approach. It works incredibly well
actually.

Cheers,
Stefan
--
Stefan Boberg, R&D Manager, Team17 Software Ltd.
bo...@te...

Just for good measure, here's ours

/*
  useful macros for swapping 16 and 32 bit data types
*/
#define MAKE16(l, h)    ((Uint16)(((Byte)(l)) | ((Uint16)((Byte)(h))) << 8))
#define MAKE32(l, h)    ((Uint32)(((Uint16)(l)) | ((Uint32)((Uint16)(h))) << 16))
#define LO16(l)                 ((Uint16)(l))
#define HI16(l)                 ((Uint16)(((Uint32)(l) >> 16) & 0xFFFF))
#define LO8(w)                  ((Byte)(w))
#define HI8(w)                  ((Byte)(((Uint16)(w) >> 8) & 0xFF))

/* these assume that the swapping is from motorola to intel format */
#if __cplusplus
#if NEEDBYTESWAP
        inline Int16 ByteSwap( Int16 &x )
        {
                Uint16 y                = (Uint16)x;
                y       = (Uint16)(y >> 8 | (y << 8 & 0xff00));
                x       = (Int16 &)y;
                return x;
        }
        inline Uint16 ByteSwap( Uint16 &x )
        {
                x       = (Uint16)(x >> 8 | (x << 8 & 0xff00));
                return x;
        }
        inline Int32 ByteSwap( Int32 &x )
        {
                Uint32 y                = (Uint32)x;
                y       = y >> 24 | (y >> 8 & 0xff00) | (y << 8 & 0xff0000) | (y << 24 & 0xff000000);
                x       = (Int32 &)y;
                return x;
        }
        inline Uint32 ByteSwap( Uint32 &x )
        {
                x       = x >> 24 | (x >> 8 & 0xff00) | (x << 8 & 0xff0000) | (x << 24 & 0xff000000);
                return x;
        }
        template<class T> inline T ByteSwap( T &parm )
        {
                Uint32 x        = (Uint32)parm;
                x       = x >> 24 | (x >> 8 & 0xff00) | (x << 8 & 0xff0000) | (x << 24 & 0xff000000);
                parm = (T &)x;
                return parm;
        }
        inline float ByteSwap( float &x )
        {
                Uint32 * pTemp  = (Uint32*)&x;
                Uint32 y                = *pTemp;
                y       = y >> 24 | (y >> 8 & 0xff00) | (y << 8 & 0xff0000) | (y << 24 & 0xff000000);
                pTemp = (Uint32*)&y;
                x       = *((float*)pTemp);
                return x;
        }
        inline double ByteSwap( double &x )
        {
                Uint32 * pParm  = (Uint32*)&x;
                Uint32 nFirst   = pParm[0];
                Uint32 nSecond  = pParm[1];

                ByteSwap( nFirst );
                ByteSwap( nSecond );

                pParm[0] = nSecond;
                pParm[1] = nFirst;

                return x;
        }
#else
        #define ByteSwap(x) (x)
#endif
#endif /* __cplusplus */

At 03:41 PM 7/17/00, you wrote:

>Jumping in late : I'm sure you don't need it now, but
>here's a crazy ANSI C byte-swapper :
>
>let x = a 32 bit ulong , ABCD 
>then y = DCBA
>
>y = (x = x>>16 | x<<16) ^ (x = (x^x>>8) & 0x00FF00FF) ^ (x<<8);
>
>At 11:45 PM 7/15/2000 -0700, you wrote:
>>I can do the obvious method, but I was wondering if anyone have any 
>>cool/fast code snippets for byte swapping integers and floats?
>>
>>Tom
>>
>>
>>_______________________________________________
>>GDAlgorithms-list mailing list
>>GDA...@li...
>>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
>>
>>
>--------------------------------------
>Charles Bloom           www.cbloom.com
>
>
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list 

  ----- Original Message -----=20
  From: Michael S. Harrison=20
  To: gda...@li...=20
  Sent: Tuesday, July 18, 2000 1:17 AM
  Subject: Re: [Algorithms] Byte Swapping

  [ SNIP ]

  /* these assume that the swapping is from motorola to intel format */

  [ SNIP ]

...or vice versa ;-))))

Are,
F

hehe.

True.  That comment reflects the fact that all of our basic data files are in Motorola format and have to be converted when running on the PC

At 10:48 AM 7/18/00, you wrote:
>   
>----- Original Message ----- 
>From: <mailto:mic...@ud...>Michael S. Harrison 
>To: <mailto:gda...@li...>gda...@li... 
>Sent: Tuesday, July 18, 2000 1:17 AM 
>Subject: Re: [Algorithms] Byte Swapping 
>  
>[ SNIP ] 
>/* these assume that the swapping is from motorola to intel format */
>
>[ SNIP ] 
> 
>
>...or vice versa ;-))))
> 
>Are,
>F
> 

If you're writing to the Mac (or even just have the QuickTime SDK
installed), there are some handy endian-swapping macros in Endian.h.
They're of the form (using unsigned longs as an example)

	EndianU32_?to?(value)

where the characters in the question marks are L (for little endian), B (for
big endian), and N (for native format).  Thus, since your data files are in
big endian format you could write

	EndianU32_BtoN(value)

which would do a conversion when compiled for Intel and compile to nothing
for PPC.  Endian.h uses ConditionalMacros.h to figure out whether you're
compiling for big or little endian.

The only problem is that they don't automatically use CodeWarrior's
intrinsic functions mentioned earlier by Jens Ayton.  I've found that
CodeWarrior lets me get away with the following code, which is in my
precompiled header:

#include <Endian.h>
#undef Endian32_Swap
#define Endian32_Swap(value)                 \
        ( *(uint32*)&(value) = __lwbrx( (uint32*)&(value), 0 ) )
#undef Endian16_Swap
#define Endian16_Swap(value)                 \
        ( (value) = __lhbrx( &(value), 0 ) )

-----Original Message-----
From: gda...@li...
[mailto:gda...@li...]On Behalf Of Michael
S. Harrison
Sent: Tuesday, July 18, 2000 5:30 AM
To: gda...@li...
Subject: Re: [Algorithms] Byte Swapping

hehe.

True.  That comment reflects the fact that all of our basic data files are
in Motorola format and have to be converted when running on the PC

At 10:48 AM 7/18/00, you wrote:

----- Original Message -----
From: Michael S. Harrison
To: gda...@li...
Sent: Tuesday, July 18, 2000 1:17 AM
Subject: Re: [Algorithms] Byte Swapping

[ SNIP ]
/* these assume that the swapping is from motorola to intel format */

[ SNIP ]

...or vice versa ;-))))

Are,
F